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

Last change on this file since 610 was 610, checked in by alain, 7 years ago

Fix several bugs in VFS to support the following
ksh commandis : cp, mv, rm, mkdir, cd, pwd
File size: 17.8 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///////////////////////////////////////////////////////////////////////////////////////////
45// @ key      : local pointer on name.
46// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
47///////////////////////////////////////////////////////////////////////////////////////////
48static uint32_t xhtab_dentry_index_from_key( void * key )
49{
50        char     * name  = key;
51        uint32_t   index = 0;
52        while( *name )
53    {
54        index = index + (*(name++) ^ index);
55    }
56        return index % XHASHTAB_SIZE;
57} 
58
59///////////////////////////////////////////////////////////////////////////////////////////
60// XHTAB_DENTRY_TYPE
61// This functions returns the extended pointer on the item, from the extended pointer
62// on xlist contained in the item.
63///////////////////////////////////////////////////////////////////////////////////////////
64// @ xlist_xp      : extended pointer on embedded xlist entry.
65// @ return the extended pointer on the dentry containing this xlist entry.
66///////////////////////////////////////////////////////////////////////////////////////////
67static xptr_t xhtab_dentry_item_from_xlist( xptr_t xlist_xp )
68{
69    return XLIST_ELEMENT( xlist_xp , vfs_dentry_t , children );
70}
71
72////////////////////////////////////////////////////////////////////////////////////////////
73// XHTAB_DENTRY_TYPE
74// This function compares the identifier of an item to a given <key>.
75// it returns true when the directory name matches the name pointed by the <key> argument.
76////////////////////////////////////////////////////////////////////////////////////////////
77// @ item_xp   : extended pointer on item.
78// @ key       : pointer on searched item identifier.
79// returns true if given name matches directory entry name.
80////////////////////////////////////////////////////////////////////////////////////////////
81static bool_t xhtab_dentry_item_match_key( xptr_t    item_xp,
82                                           void    * key )
83{
84    char name[CONFIG_VFS_MAX_NAME_LENGTH];
85
86    // get dentry cluster and local pointer
87    cxy_t          dentry_cxy = GET_CXY( item_xp );
88    vfs_dentry_t * dentry_ptr = GET_PTR( item_xp );
89
90    // make a local copy of directory entry name
91    hal_remote_strcpy( XPTR( local_cxy , name ) ,
92                       XPTR( dentry_cxy , &dentry_ptr->name ) );
93
94    return( strcmp( name , (char*)key ) == 0 );
95}
96
97////////////////////////////////////////////////////////////////////////////////////////////
98// XHTAB_DENTRY_TYPE
99// This function print the item key, that is the name for a vfs_dentry_t.
100////////////////////////////////////////////////////////////////////////////////////////////
101// @ item_xp   : extended pointer on item.
102////////////////////////////////////////////////////////////////////////////////////////////
103static void xhtab_dentry_item_print_key( xptr_t item_xp )
104{
105    char name[CONFIG_VFS_MAX_NAME_LENGTH];
106
107    // get dentry cluster and local pointer
108    cxy_t          dentry_cxy = GET_CXY( item_xp );
109    vfs_dentry_t * dentry_ptr = GET_PTR( item_xp );
110   
111    // make a local copy of directory entry name
112    hal_remote_strcpy( XPTR( local_cxy , name ) ,
113                       XPTR( dentry_cxy , &dentry_ptr->name ) );
114
115    // print dentry name
116    printk("%s , ", name );
117}                       
118
119////////////////////////////////////////////////////////////////////////////////////////
120//         Generic access functions
121////////////////////////////////////////////////////////////////////////////////////////
122
123//////////////////////////////////////////
124void xhtab_init( xhtab_t          * xhtab,
125                 xhtab_item_type_t  type )
126{
127        uint32_t i;
128
129    // initialize readlock
130    remote_busylock_init( XPTR( local_cxy , &xhtab->lock), LOCK_XHTAB_STATE );
131
132    xhtab->items            = 0;
133    xhtab->current_index    = 0;
134    xhtab->current_xlist_xp = XPTR_NULL;
135
136    if( type == XHTAB_DENTRY_TYPE )
137    {
138        xhtab->item_match_key  = &xhtab_dentry_item_match_key;
139        xhtab->index_from_key  = &xhtab_dentry_index_from_key;
140        xhtab->item_from_xlist = &xhtab_dentry_item_from_xlist;
141        xhtab->item_print_key  = &xhtab_dentry_item_print_key;
142    }
143    else
144    {
145        assert( false , "illegal item type\n" );
146    }
147
148        for( i=0 ; i < XHASHTAB_SIZE ; i++ )
149    {
150                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
151    } 
152
153#if DEBUG_XHTAB
154printk("\n@@@ %s for xhtab (%x,%x)\n"
155" - index_from_key  = %x (@ %x)\n"
156" - item_match_key  = %x (@ %x)\n"
157" - item_from_xlist = %x (@ %x)\n",
158__FUNCTION__, local_cxy, xhtab,
159xhtab->index_from_key , &xhtab->index_from_key,
160xhtab->item_match_key , &xhtab->item_match_key,
161xhtab->item_from_xlist, &xhtab->item_from_xlist );
162#endif
163
164}  // end xhtab_init()
165
166//////////////////////////////////////
167xptr_t xhtab_scan( xptr_t    xhtab_xp,
168                   uint32_t  index,
169                   void    * key )
170{
171    xptr_t              xlist_xp;           // xlist_entry_t (iterator)
172    xptr_t              item_xp;            // associated item
173    xhtab_t           * xhtab_ptr;          // hash table local pointer
174    cxy_t               xhtab_cxy;          // hash table cluster
175    item_from_xlist_t * item_from_xlist;    // function pointer
176    item_match_key_t  * item_match_key;     // function pointer
177
178    // get hash table cluster and local pointer
179    xhtab_cxy = GET_CXY( xhtab_xp );
180    xhtab_ptr = GET_PTR( xhtab_xp );
181
182    // get pointer on "item_from_xlist" function
183    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
184                                                           &xhtab_ptr->item_from_xlist ) );
185    // get pointer on "item_match_key" function
186    item_match_key = (item_match_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
187                                                         &xhtab_ptr->item_match_key ) );
188
189    // scan sub-list[index]
190    XLIST_FOREACH( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp )
191    {
192        // get extended pointer on item containing the xlist entry
193            item_xp = item_from_xlist( xlist_xp );
194
195        // check matching
196        if( item_match_key( item_xp , key ) ) return item_xp;
197    }
198
199    // No matching item found
200    return XPTR_NULL;
201
202}  // end xhtab_scan()
203
204///////////////////////////////////////
205error_t xhtab_insert( xptr_t   xhtab_xp,
206                      void   * key,
207                      xptr_t   xlist_xp )
208{
209    xptr_t             item_xp;
210    uint32_t           index;
211    cxy_t              xhtab_cxy;
212    xhtab_t          * xhtab_ptr;
213    index_from_key_t * index_from_key;     // function pointer
214   
215#if DEBUG_XHTAB
216printk("\n[%s] enter / key %s\n", __FUNCTION__, key );
217#endif
218
219    // get xhtab cluster and local pointer
220    xhtab_cxy = GET_CXY( xhtab_xp );
221    xhtab_ptr = GET_PTR( xhtab_xp );
222
223    // get pointer on "index_from_key" function
224    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
225                                                         &xhtab_ptr->index_from_key ) );
226    // compute index from key
227        index = index_from_key( key );
228
229    // take the lock protecting hash table
230    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
231
232    // search a matching item
233    item_xp = xhtab_scan( xhtab_xp , index , key );
234
235    if( item_xp != XPTR_NULL )    // error if found
236    {
237        // release the lock protecting hash table
238        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
239
240        return EINVAL;
241    }
242    else                          // insert item if not found
243    {
244        // register item in hash table
245            xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp );
246
247        // update number of registered items
248        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 );
249
250        // release the lock protecting hash table
251        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
252   
253#if DEBUG_XHTAB
254printk("\n[%s] success / %s\n", __FUNCTION__, key );
255#endif
256
257        return 0;
258    }
259}  // end xhtab_insert()
260
261///////////////////////////////////////
262bool_t xhtab_remove( xptr_t   xhtab_xp,
263                     void   * key,
264                     xptr_t   xlist_entry_xp )
265{
266    xptr_t             item_xp;
267    uint32_t           index;
268    cxy_t              xhtab_cxy;
269    xhtab_t          * xhtab_ptr;
270    index_from_key_t * index_from_key;     // function pointer
271
272    // get xhtab cluster and local pointer
273    xhtab_cxy = GET_CXY( xhtab_xp );
274    xhtab_ptr = GET_PTR( xhtab_xp );
275
276    // get pointer on "index_from_key" function
277    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
278                                                         &xhtab_ptr->index_from_key ) );
279    // compute index from key
280        index = index_from_key( key );
281
282    // take the lock protecting hash table
283    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
284
285    // get extended pointer on item to remove
286    item_xp = xhtab_scan( xhtab_xp , index , key );
287
288    if( item_xp == XPTR_NULL )    // return error if not found
289    {
290        // release the lock protecting hash table
291        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
292
293        return false;
294    }
295    else                          // remove item if found
296    {
297        // remove item from hash table <=> unlink xlist_entry_t
298        xlist_unlink( xlist_entry_xp );
299
300        // update number of registered items
301        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 );
302
303        // release the lock protecting hash table
304        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
305
306        return true;
307    }
308}  // end xhtab_remove()
309
310/////////////////////////////////////////
311xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
312                      void    * key )
313{
314    xptr_t             item_xp;
315    uint32_t           index;
316    cxy_t              xhtab_cxy;
317    xhtab_t          * xhtab_ptr;
318    index_from_key_t * index_from_key;     // function pointer
319
320    // get xhtab cluster and local pointer
321    xhtab_cxy = GET_CXY( xhtab_xp );
322    xhtab_ptr = GET_PTR( xhtab_xp );
323
324    // get pointer on "index_from_key" function
325    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
326                                                         &xhtab_ptr->index_from_key ) );
327    // compute index from key
328        index = index_from_key( key );
329   
330#if DEBUG_XHTAB
331printk("\n[%s] enter / %s\n", __FUNCTION__, key );
332#endif
333
334    // take the lock protecting hash table
335    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
336   
337#if DEBUG_XHTAB
338printk("\n[%s] after lock acquire / %s\n", __FUNCTION__, key );
339#endif
340
341    // scan sub-list
342    item_xp = xhtab_scan( xhtab_xp , index , key );
343
344#if DEBUG_XHTAB
345printk("\n[%s] after xhtab scan / %s\n", __FUNCTION__, key );
346#endif
347
348    // release the lock protecting hash table
349    remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
350
351#if DEBUG_XHTAB
352printk("\n[%s] after lock release / %s\n", __FUNCTION__, key );
353#endif
354
355    return item_xp;
356
357}  // end xhtab_lookup()
358
359//////////////////////////////////
360void xhtab_lock( xptr_t xhtab_xp )
361{
362    // get xhtab cluster and local pointer
363    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
364    xhtab_t * xhtab_ptr = GET_PTR( xhtab_xp );
365
366    // take the lock protecting hash table
367    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
368}
369
370////////////////////////////////////
371void xhtab_unlock( xptr_t xhtab_xp )
372{
373    // get xhtab cluster and local pointer
374    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
375    xhtab_t * xhtab_ptr = GET_PTR( xhtab_xp );
376
377    // release the lock protecting hash table
378    remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
379}
380
381/////////////////////////////////////////
382xptr_t xhtab_get_first( xptr_t xhtab_xp )
383{
384    uint32_t            index;
385    cxy_t               xhtab_cxy;
386    xhtab_t           * xhtab_ptr;
387    xptr_t              xlist_xp;
388    xptr_t              item_xp;
389    xptr_t              root_xp;
390    item_from_xlist_t * item_from_xlist;   // function pointer
391
392    // get xhtab cluster and local pointer
393    xhtab_cxy = GET_CXY( xhtab_xp );
394    xhtab_ptr = GET_PTR( xhtab_xp );
395
396    // get pointer on "item_from_xlist" function
397    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
398                                                           &xhtab_ptr->item_from_xlist ) );
399    //loop on subsets
400    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
401    {
402        // get root of subset
403        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
404
405        // get first item
406        xlist_xp = xlist_next( root_xp , root_xp );
407
408        if( xlist_xp != XPTR_NULL )  // first item found
409        {
410            // get extended pointer on item containing the xlist entry
411                item_xp = item_from_xlist( xlist_xp );
412
413            // register item in hash table header
414            hal_remote_s32 ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
415            hal_remote_s64( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
416
417            return item_xp;
418        }
419    }
420           
421    // item not found
422    return XPTR_NULL;
423
424} // end xhtab_get_first()
425   
426////////////////////////////////////////
427xptr_t xhtab_get_next( xptr_t xhtab_xp )
428{
429    uint32_t            index;
430    cxy_t               xhtab_cxy;
431    xhtab_t           * xhtab_ptr;
432    xptr_t              xlist_xp;
433    xptr_t              item_xp;
434    xptr_t              root_xp;
435    item_from_xlist_t * item_from_xlist;   // function pointer
436
437    uint32_t current_index;
438    xptr_t   current_xlist_xp;
439
440    // get xhtab cluster and local pointer
441    xhtab_cxy = GET_CXY( xhtab_xp );
442    xhtab_ptr = GET_PTR( xhtab_xp );
443
444    // get current item pointers
445    current_index    = hal_remote_l32 ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) ); 
446    current_xlist_xp = hal_remote_l64( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) ); 
447
448    // get pointer on "item_from_xlist" function
449    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
450                                                           &xhtab_ptr->item_from_xlist ) );
451    //loop on subsets
452    for( index = current_index ; index < XHASHTAB_SIZE ; index++ )
453    {
454        // get root of subset
455        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
456
457        // get next item
458        if( index == current_index ) xlist_xp = xlist_next( root_xp , current_xlist_xp );
459        else                         xlist_xp = xlist_next( root_xp , root_xp );
460
461        if( xlist_xp != XPTR_NULL )  // next item found
462        {
463            // get extended pointer on item containing the xlist entry
464                item_xp = item_from_xlist( xlist_xp );
465
466            // register item in hash table header
467            hal_remote_s32 ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
468            hal_remote_s64( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );
469
470            return item_xp;
471        }
472    }
473           
474    // item not found
475    return XPTR_NULL;
476
477} // end xhtab_get_next()
478
479/////////////////////////////////////
480void xhtab_display( xptr_t xhtab_xp )
481{
482    uint32_t            index;
483    cxy_t               xhtab_cxy;
484    xhtab_t           * xhtab_ptr;
485    xptr_t              root_xp;
486    xptr_t              iter_xp;
487    xptr_t              item_xp;
488    item_from_xlist_t * item_from_xlist;   // function pointer
489    item_print_key_t  * item_print_key;    // function pointer
490
491    // get xhtab cluster and local pointer
492    xhtab_cxy = GET_CXY( xhtab_xp );
493    xhtab_ptr = GET_PTR( xhtab_xp );
494
495    // get pointer on "item_from_xlist" function
496    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
497                                                           &xhtab_ptr->item_from_xlist ) );
498    // get pointer on "item_print_key" function
499    item_print_key = (item_print_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
500                                                         &xhtab_ptr->item_print_key ) );
501    //loop on subsets
502    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
503    {
504        printk(" index = %d : ", index );
505
506        // get root of subset
507        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );
508
509        // loop on xlist
510        XLIST_FOREACH( root_xp , iter_xp )
511        {
512            // get item from xlist
513            item_xp = item_from_xlist( iter_xp );
514           
515            // print item identifier
516            item_print_key( item_xp );
517        }
518
519        printk("\n");
520    }
521}  // end xhtab_display()
Note: See TracBrowser for help on using the repository browser.