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

Last change on this file since 640 was 635, checked in by alain, 5 years ago

This version is a major evolution: The physical memory allocators,
defined in the kmem.c, ppm.c, and kcm.c files have been modified
to support remote accesses. The RPCs that were previously user
to allocate physical memory in a remote cluster have been removed.
This has been done to cure a dead-lock in case of concurrent page-faults.

This version 2.2 has been tested on a (4 clusters / 2 cores per cluster)
TSAR architecture, for both the "sort" and the "fft" applications.

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