source: trunk/kernel/libk/xhtab.c

Last change on this file was 671, checked in by alain, 3 years ago

Cosmetic.

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