source: trunk/kernel/libk/xhtab.c @ 617

Last change on this file since 617 was 614, checked in by alain, 6 years ago

1) introduce a dev_ioc_sync_write() function in IOC API,

to improve the DEVFS synchronous update.

2) fix a big bug in both the user_dir_create() and user_dir_destroy()

functions: add an extended pointer on the reference client process
in the function's arguments.
File size: 18.0 KB
Line 
1/*
2 * xhtab.c - Remote access embedded hash table implementation.
3 *
4 * Author     Alain Greiner          (2016,2017)
5 *
6 * Copyright (c) UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
10 * ALMOS-MKH is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; version 2.0 of the License.
13 *
14 * ALMOS-MKH is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#include <kernel_config.h>
25#include <hal_kernel_types.h>
26#include <hal_special.h>
27#include <hal_remote.h>
28#include <xlist.h>
29#include <remote_busylock.h>
30#include <string.h>
31#include <printk.h>
32#include <xhtab.h>
33#include <vfs.h>
34
35
36///////////////////////////////////////////////////////////////////////////////////////////
37// Item type specific functions (four functions for each item type).
38// Example below is for <vfs_dentry_t> where the identifier is the dentry name.
39///////////////////////////////////////////////////////////////////////////////////////////
40
41///////////////////////////////////////////////////////////////////////////////////////////
42// XHTAB_DENTRY_TYPE
43// This functions compute the hash index from the key, that is the directory entry name.
44// In this implementation, the index value is simply the ASCII code of the first
45// character, to provide an approximate lexicographic order.
46///////////////////////////////////////////////////////////////////////////////////////////
47// @ key      : local pointer on name.
48// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
49///////////////////////////////////////////////////////////////////////////////////////////
50static uint32_t xhtab_dentry_index_from_key( void * key )
51{
52        char     * name  = key;
53
54        return (name[0] % XHASHTAB_SIZE);
55/*
56    uint32_t   index = 0;
57        while( *name )
58    {
59        index = index + (*(name++) ^ index);
60    }
61        return index % XHASHTAB_SIZE;
62*/
63
64} 
65
66///////////////////////////////////////////////////////////////////////////////////////////
67// XHTAB_DENTRY_TYPE
68// This functions returns the extended pointer on the item, from the extended pointer
69// on xlist contained in the item.
70///////////////////////////////////////////////////////////////////////////////////////////
71// @ xlist_xp      : extended pointer on embedded xlist entry.
72// @ return the extended pointer on the dentry containing this xlist entry.
73///////////////////////////////////////////////////////////////////////////////////////////
74static xptr_t xhtab_dentry_item_from_xlist( xptr_t xlist_xp )
75{
76    return XLIST_ELEMENT( xlist_xp , vfs_dentry_t , children );
77}
78
79////////////////////////////////////////////////////////////////////////////////////////////
80// XHTAB_DENTRY_TYPE
81// This function compares the identifier of an item to a given <key>.
82// it returns true when the directory name matches the name pointed by the <key> argument.
83////////////////////////////////////////////////////////////////////////////////////////////
84// @ item_xp   : extended pointer on item.
85// @ key       : pointer on searched item identifier.
86// returns true if given name matches directory entry name.
87////////////////////////////////////////////////////////////////////////////////////////////
88static bool_t xhtab_dentry_item_match_key( xptr_t    item_xp,
89                                           void    * key )
90{
91    char name[CONFIG_VFS_MAX_NAME_LENGTH];
92
93    // get dentry cluster and local pointer
94    cxy_t          dentry_cxy = GET_CXY( item_xp );
95    vfs_dentry_t * dentry_ptr = GET_PTR( item_xp );
96
97    // make a local copy of directory entry name
98    hal_remote_strcpy( XPTR( local_cxy , name ) ,
99                       XPTR( dentry_cxy , &dentry_ptr->name ) );
100
101    return( strcmp( name , (char*)key ) == 0 );
102}
103
104////////////////////////////////////////////////////////////////////////////////////////////
105// XHTAB_DENTRY_TYPE
106// This function print the item key, that is the name for a vfs_dentry_t.
107////////////////////////////////////////////////////////////////////////////////////////////
108// @ item_xp   : extended pointer on item.
109////////////////////////////////////////////////////////////////////////////////////////////
110static void xhtab_dentry_item_print_key( xptr_t item_xp )
111{
112    char name[CONFIG_VFS_MAX_NAME_LENGTH];
113
114    // get dentry cluster and local pointer
115    cxy_t          dentry_cxy = GET_CXY( item_xp );
116    vfs_dentry_t * dentry_ptr = GET_PTR( item_xp );
117   
118    // make a local copy of directory entry name
119    hal_remote_strcpy( XPTR( local_cxy , name ) ,
120                       XPTR( dentry_cxy , &dentry_ptr->name ) );
121
122    // print dentry name
123    printk("%s , ", name );
124}                       
125
126////////////////////////////////////////////////////////////////////////////////////////
127//         Generic access functions
128////////////////////////////////////////////////////////////////////////////////////////
129
130//////////////////////////////////////////
131void xhtab_init( xhtab_t          * xhtab,
132                 xhtab_item_type_t  type )
133{
134        uint32_t i;
135
136    // initialize readlock
137    remote_busylock_init( XPTR( local_cxy , &xhtab->lock), LOCK_XHTAB_STATE );
138
139    xhtab->items            = 0;
140    xhtab->current_index    = 0;
141    xhtab->current_xlist_xp = XPTR_NULL;
142
143    if( type == XHTAB_DENTRY_TYPE )
144    {
145        xhtab->item_match_key  = &xhtab_dentry_item_match_key;
146        xhtab->index_from_key  = &xhtab_dentry_index_from_key;
147        xhtab->item_from_xlist = &xhtab_dentry_item_from_xlist;
148        xhtab->item_print_key  = &xhtab_dentry_item_print_key;
149    }
150    else
151    {
152        assert( false , "illegal item type\n" );
153    }
154
155        for( i=0 ; i < XHASHTAB_SIZE ; i++ )
156    {
157                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
158    } 
159
160#if DEBUG_XHTAB
161printk("\n@@@ %s for xhtab (%x,%x)\n"
162" - index_from_key  = %x (@ %x)\n"
163" - item_match_key  = %x (@ %x)\n"
164" - item_from_xlist = %x (@ %x)\n",
165__FUNCTION__, local_cxy, xhtab,
166xhtab->index_from_key , &xhtab->index_from_key,
167xhtab->item_match_key , &xhtab->item_match_key,
168xhtab->item_from_xlist, &xhtab->item_from_xlist );
169#endif
170
171}  // end xhtab_init()
172
173//////////////////////////////////////
174xptr_t xhtab_scan( xptr_t    xhtab_xp,
175                   uint32_t  index,
176                   void    * key )
177{
178    xptr_t              xlist_xp;           // xlist_entry_t (iterator)
179    xptr_t              item_xp;            // associated item
180    xhtab_t           * xhtab_ptr;          // hash table local pointer
181    cxy_t               xhtab_cxy;          // hash table cluster
182    item_from_xlist_t * item_from_xlist;    // function pointer
183    item_match_key_t  * item_match_key;     // function pointer
184
185    // get hash table cluster and local pointer
186    xhtab_cxy = GET_CXY( xhtab_xp );
187    xhtab_ptr = GET_PTR( xhtab_xp );
188
189    // get pointer on "item_from_xlist" function
190    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
191                                                           &xhtab_ptr->item_from_xlist ) );
192    // get pointer on "item_match_key" function
193    item_match_key = (item_match_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
194                                                         &xhtab_ptr->item_match_key ) );
195
196    // scan sub-list[index]
197    XLIST_FOREACH( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp )
198    {
199        // get extended pointer on item containing the xlist entry
200            item_xp = item_from_xlist( xlist_xp );
201
202        // check matching
203        if( item_match_key( item_xp , key ) ) return item_xp;
204    }
205
206    // No matching item found
207    return XPTR_NULL;
208
209}  // end xhtab_scan()
210
211///////////////////////////////////////
212error_t xhtab_insert( xptr_t   xhtab_xp,
213                      void   * key,
214                      xptr_t   xlist_xp )
215{
216    xptr_t             item_xp;
217    uint32_t           index;
218    cxy_t              xhtab_cxy;
219    xhtab_t          * xhtab_ptr;
220    index_from_key_t * index_from_key;     // function pointer
221   
222#if DEBUG_XHTAB
223printk("\n[%s] enter / key %s\n", __FUNCTION__, key );
224#endif
225
226    // get xhtab cluster and local pointer
227    xhtab_cxy = GET_CXY( xhtab_xp );
228    xhtab_ptr = GET_PTR( xhtab_xp );
229
230    // get pointer on "index_from_key" function
231    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
232                                                         &xhtab_ptr->index_from_key ) );
233    // compute index from key
234        index = index_from_key( key );
235
236    // take the lock protecting hash table
237    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
238
239    // search a matching item
240    item_xp = xhtab_scan( xhtab_xp , index , key );
241
242    if( item_xp != XPTR_NULL )    // error if found
243    {
244        // release the lock protecting hash table
245        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
246
247        return -1;
248    }
249    else                          // insert item if not found
250    {
251        // register item in hash table
252            xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp );
253
254        // update number of registered items
255        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 );
256
257        // release the lock protecting hash table
258        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
259   
260#if DEBUG_XHTAB
261printk("\n[%s] success / %s\n", __FUNCTION__, key );
262#endif
263
264        return 0;
265    }
266}  // end xhtab_insert()
267
268///////////////////////////////////////
269bool_t xhtab_remove( xptr_t   xhtab_xp,
270                     void   * key,
271                     xptr_t   xlist_entry_xp )
272{
273    xptr_t             item_xp;
274    uint32_t           index;
275    cxy_t              xhtab_cxy;
276    xhtab_t          * xhtab_ptr;
277    index_from_key_t * index_from_key;     // function pointer
278
279    // get xhtab cluster and local pointer
280    xhtab_cxy = GET_CXY( xhtab_xp );
281    xhtab_ptr = GET_PTR( xhtab_xp );
282
283    // get pointer on "index_from_key" function
284    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
285                                                         &xhtab_ptr->index_from_key ) );
286    // compute index from key
287        index = index_from_key( key );
288
289    // take the lock protecting hash table
290    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
291
292    // get extended pointer on item to remove
293    item_xp = xhtab_scan( xhtab_xp , index , key );
294
295    if( item_xp == XPTR_NULL )    // return error if not found
296    {
297        // release the lock protecting hash table
298        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
299
300        return false;
301    }
302    else                          // remove item if found
303    {
304        // remove item from hash table <=> unlink xlist_entry_t
305        xlist_unlink( xlist_entry_xp );
306
307        // update number of registered items
308        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 );
309
310        // release the lock protecting hash table
311        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
312
313        return true;
314    }
315}  // end xhtab_remove()
316
317/////////////////////////////////////////
318xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
319                      void    * key )
320{
321    xptr_t             item_xp;
322    uint32_t           index;
323    cxy_t              xhtab_cxy;
324    xhtab_t          * xhtab_ptr;
325    index_from_key_t * index_from_key;     // function pointer
326
327    // get xhtab cluster and local pointer
328    xhtab_cxy = GET_CXY( xhtab_xp );
329    xhtab_ptr = GET_PTR( xhtab_xp );
330
331    // get pointer on "index_from_key" function
332    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
333                                                         &xhtab_ptr->index_from_key ) );
334    // compute index from key
335        index = index_from_key( key );
336   
337#if DEBUG_XHTAB
338printk("\n[%s] enter / %s\n", __FUNCTION__, key );
339#endif
340
341    // take the lock protecting hash table
342    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
343   
344#if DEBUG_XHTAB
345printk("\n[%s] after lock acquire / %s\n", __FUNCTION__, key );
346#endif
347
348    // scan sub-list
349    item_xp = xhtab_scan( xhtab_xp , index , key );
350
351#if DEBUG_XHTAB
352printk("\n[%s] after xhtab scan / %s\n", __FUNCTION__, key );
353#endif
354
355    // release the lock protecting hash table
356    remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
357
358#if DEBUG_XHTAB
359printk("\n[%s] after lock release / %s\n", __FUNCTION__, key );
360#endif
361
362    return item_xp;
363
364}  // end xhtab_lookup()
365
366//////////////////////////////////
367void xhtab_lock( xptr_t xhtab_xp )
368{
369    // get xhtab cluster and local pointer
370    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
371    xhtab_t * xhtab_ptr = GET_PTR( xhtab_xp );
372
373    // take the lock protecting hash table
374    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
375}
376
377////////////////////////////////////
378void xhtab_unlock( xptr_t xhtab_xp )
379{
380    // get xhtab cluster and local pointer
381    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
382    xhtab_t * xhtab_ptr = GET_PTR( xhtab_xp );
383
384    // release the lock protecting hash table
385    remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
386}
387
388/////////////////////////////////////////
389xptr_t xhtab_get_first( xptr_t xhtab_xp )
390{
391    uint32_t            index;
392    cxy_t               xhtab_cxy;
393    xhtab_t           * xhtab_ptr;
394    xptr_t              xlist_xp;
395    xptr_t              item_xp;
396    xptr_t              root_xp;
397    item_from_xlist_t * item_from_xlist;   // function pointer
398
399    // get xhtab cluster and local pointer
400    xhtab_cxy = GET_CXY( xhtab_xp );
401    xhtab_ptr = GET_PTR( xhtab_xp );
402
403    // get pointer on "item_from_xlist" function
404    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
405                                                           &xhtab_ptr->item_from_xlist ) );
406    //loop on subsets
407    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
408    {
409        // get root of subset
410        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
411
412        // get first item
413        xlist_xp = xlist_next( root_xp , root_xp );
414
415        if( xlist_xp != XPTR_NULL )  // first item found
416        {
417            // get extended pointer on item containing the xlist entry
418                item_xp = item_from_xlist( xlist_xp );
419
420            // register item in hash table header
421            hal_remote_s32 ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
422            hal_remote_s64( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
423
424            return item_xp;
425        }
426    }
427           
428    // item not found
429    return XPTR_NULL;
430
431} // end xhtab_get_first()
432   
433////////////////////////////////////////
434xptr_t xhtab_get_next( xptr_t xhtab_xp )
435{
436    uint32_t            index;
437    cxy_t               xhtab_cxy;
438    xhtab_t           * xhtab_ptr;
439    xptr_t              xlist_xp;
440    xptr_t              item_xp;
441    xptr_t              root_xp;
442    item_from_xlist_t * item_from_xlist;   // function pointer
443
444    uint32_t current_index;
445    xptr_t   current_xlist_xp;
446
447    // get xhtab cluster and local pointer
448    xhtab_cxy = GET_CXY( xhtab_xp );
449    xhtab_ptr = GET_PTR( xhtab_xp );
450
451    // get current item pointers
452    current_index    = hal_remote_l32 ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) ); 
453    current_xlist_xp = hal_remote_l64( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) ); 
454
455    // get pointer on "item_from_xlist" function
456    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
457                                                           &xhtab_ptr->item_from_xlist ) );
458    //loop on subsets
459    for( index = current_index ; index < XHASHTAB_SIZE ; index++ )
460    {
461        // get root of subset
462        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
463
464        // get next item
465        if( index == current_index ) xlist_xp = xlist_next( root_xp , current_xlist_xp );
466        else                         xlist_xp = xlist_next( root_xp , root_xp );
467
468        if( xlist_xp != XPTR_NULL )  // next item found
469        {
470            // get extended pointer on item containing the xlist entry
471                item_xp = item_from_xlist( xlist_xp );
472
473            // register item in hash table header
474            hal_remote_s32 ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
475            hal_remote_s64( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
476
477            return item_xp;
478        }
479    }
480           
481    // item not found
482    return XPTR_NULL;
483
484} // end xhtab_get_next()
485
486/////////////////////////////////////
487void xhtab_display( xptr_t xhtab_xp )
488{
489    uint32_t            index;
490    cxy_t               xhtab_cxy;
491    xhtab_t           * xhtab_ptr;
492    xptr_t              root_xp;
493    xptr_t              iter_xp;
494    xptr_t              item_xp;
495    item_from_xlist_t * item_from_xlist;   // function pointer
496    item_print_key_t  * item_print_key;    // function pointer
497
498    // get xhtab cluster and local pointer
499    xhtab_cxy = GET_CXY( xhtab_xp );
500    xhtab_ptr = GET_PTR( xhtab_xp );
501
502    // get pointer on "item_from_xlist" function
503    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
504                                                           &xhtab_ptr->item_from_xlist ) );
505    // get pointer on "item_print_key" function
506    item_print_key = (item_print_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
507                                                         &xhtab_ptr->item_print_key ) );
508    //loop on subsets
509    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
510    {
511        printk(" index = %d : ", index );
512
513        // get root of subset
514        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
515
516        // loop on xlist
517        XLIST_FOREACH( root_xp , iter_xp )
518        {
519            // get item from xlist
520            item_xp = item_from_xlist( iter_xp );
521           
522            // print item identifier
523            item_print_key( item_xp );
524        }
525
526        printk("\n");
527    }
528}  // end xhtab_display()
Note: See TracBrowser for help on using the repository browser.