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

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

Complete restructuration of kernel spinlocks.

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