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

Last change on this file since 666 was 657, checked in by alain, 5 years ago

Introduce remote_buf.c/.h & socket.c/.h files.
Update dev_nic.c/.h files.
File size: 18.9 KB
Line 
1/*
2 * xhtab.c - Remote access embedded hash table implementation.
3 *
4 * Author     Alain Greiner   (2016,2017,2018,2019)
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
57///////////////////////////////////////////////////////////////////////////////////////////
58// XHTAB_DENTRY_TYPE
59// This functions returns the extended pointer on the item, from the extended pointer
60// on xlist contained in the item.
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{
67    return XLIST_ELEMENT( xlist_xp , vfs_dentry_t , children );
68}
69
70////////////////////////////////////////////////////////////////////////////////////////////
71// XHTAB_DENTRY_TYPE
72// This function compares the identifier of an item to a given <key>.
73// it returns true when the directory name matches the name pointed by the <key> argument.
74////////////////////////////////////////////////////////////////////////////////////////////
75// @ item_xp   : extended pointer on item.
76// @ key       : pointer on searched item identifier.
77// returns true if given name matches directory entry name.
78////////////////////////////////////////////////////////////////////////////////////////////
79static bool_t xhtab_dentry_item_match_key( xptr_t    item_xp,
80                                           void    * key )
81{
82    char name[CONFIG_VFS_MAX_NAME_LENGTH];
83
84    // get dentry cluster and local pointer
85    cxy_t          dentry_cxy = GET_CXY( item_xp );
86    vfs_dentry_t * dentry_ptr = GET_PTR( item_xp );
87
88    // make a local copy of directory entry name
89    hal_remote_strcpy( XPTR( local_cxy , name ) ,
90                       XPTR( dentry_cxy , &dentry_ptr->name ) );
91
92    return( strcmp( name , (char*)key ) == 0 );
93}
94
95////////////////////////////////////////////////////////////////////////////////////////////
96// XHTAB_DENTRY_TYPE
97// This function print the item key, that is the name for a vfs_dentry_t.
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 );
107    vfs_dentry_t * dentry_ptr = GET_PTR( item_xp );
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
117////////////////////////////////////////////////////////////////////////////////////////
118//         Generic access functions
119////////////////////////////////////////////////////////////////////////////////////////
120
121/////////////////////////////////////////////
122void xhtab_init( xptr_t             xhtab_xp,
123                 xhtab_item_type_t  type )
124{
125    uint32_t i;
126
127    // get cluster and local pointer
128    xhtab_t * ptr = GET_PTR( xhtab_xp );
129    cxy_t     cxy = GET_CXY( xhtab_xp );
130
131    // initialize lock
132    remote_busylock_init( XPTR( cxy , &ptr->lock), LOCK_XHTAB_STATE );
133
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
140    if( type == XHTAB_DENTRY_TYPE )
141    {
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 );
146    }
147    else
148    {
149        assert( false , "illegal item type\n" );
150    }
151
152    // initialize all lists
153    for( i=0 ; i < XHASHTAB_SIZE ; i++ )
154    {
155        xlist_root_init( XPTR( cxy , &ptr->roots[i] ) );
156    }
157 
158#if DEBUG_XHTAB
159printk("\n[%s] for xhtab (%x,%x)\n"
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 ) ) ); 
167#endif
168
169}  // end xhtab_init()
170
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 )
183{
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
190
191    // get hash table cluster and local pointer
192    xhtab_cxy = GET_CXY( xhtab_xp );
193    xhtab_ptr = GET_PTR( xhtab_xp );
194
195#if DEBUG_XHTAB
196printk("\n[%s] enter : index = %d / key = %s\n", __FUNCTION__ , index , key );
197#endif
198
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 ) );
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
209            item_xp = item_from_xlist( xlist_xp );
210
211        // check matching
212        if( item_match_key( item_xp , key ) ) return item_xp;
213    }
214
215#if DEBUG_XHTAB
216printk("\n[%s] exit\n", __FUNCTION__ );
217#endif
218
219
220    // No matching item found
221    return XPTR_NULL;
222
223}  // end xhtab_scan()
224
225///////////////////////////////////////
226error_t xhtab_insert( xptr_t   xhtab_xp,
227                      void   * key,
228                      xptr_t   xlist_xp )
229{
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   
236    // get xhtab cluster and local pointer
237    xhtab_cxy = GET_CXY( xhtab_xp );
238    xhtab_ptr = GET_PTR( xhtab_xp );
239
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
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 ) );
251    // compute index from key
252        index = index_from_key( key );
253
254    // take the lock protecting hash table
255    remote_busylock_acquire( lock_xp );
256
257    // search a matching item in subset
258    item_xp = xhtab_scan( xhtab_xp , index , key );
259
260    if( item_xp != XPTR_NULL )    // error if item already registered
261    {
262        // release the lock protecting hash table
263        remote_busylock_release( lock_xp );
264
265        return -1;
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 );
271
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
276        remote_busylock_release( lock_xp );
277   
278#if DEBUG_XHTAB
279printk("\n[%s] success for <%s>\n", __FUNCTION__, key );
280#endif
281
282        return 0;
283    }
284}  // end xhtab_insert()
285
286///////////////////////////////////////
287bool_t xhtab_remove( xptr_t   xhtab_xp,
288                     void   * key,
289                     xptr_t   xlist_entry_xp )
290{
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
297    // get xhtab cluster and local pointer
298    xhtab_cxy = GET_CXY( xhtab_xp );
299    xhtab_ptr = GET_PTR( xhtab_xp );
300
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 ) );
304    // compute index from key
305        index = index_from_key( key );
306
307    // take the lock protecting hash table
308    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
309
310    // get extended pointer on item to remove
311    item_xp = xhtab_scan( xhtab_xp , index , key );
312
313    if( item_xp == XPTR_NULL )    // return error if not found
314    {
315        // release the lock protecting hash table
316        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
317
318        return false;
319    }
320    else                          // remove item if found
321    {
322        // remove item from hash table <=> unlink xlist_entry_t
323        xlist_unlink( xlist_entry_xp );
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
329        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
330
331        return true;
332    }
333}  // end xhtab_remove()
334
335/////////////////////////////////////////
336xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
337                      void    * key )
338{
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
344
345    // get xhtab cluster and local pointer
346    xhtab_cxy = GET_CXY( xhtab_xp );
347    xhtab_ptr = GET_PTR( xhtab_xp );
348
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 ) );
352    // compute index from key
353        index = index_from_key( key );
354   
355#if DEBUG_XHTAB
356printk("\n[%s] enter\n", __FUNCTION__ );
357#endif
358
359    // take the lock protecting hash table
360    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
361   
362    // scan sub-list
363    item_xp = xhtab_scan( xhtab_xp , index , key );
364
365    // release the lock protecting hash table
366    remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
367
368#if DEBUG_XHTAB
369printk("\n[%s] exit\n", __FUNCTION__ );
370#endif
371
372    return item_xp;
373
374}  // end xhtab_lookup()
375
376//////////////////////////////////
377void xhtab_lock( xptr_t xhtab_xp )
378{
379    // get xhtab cluster and local pointer
380    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
381    xhtab_t * xhtab_ptr = GET_PTR( xhtab_xp );
382
383    // take the lock protecting hash table
384    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
385}
386
387////////////////////////////////////
388void xhtab_unlock( xptr_t xhtab_xp )
389{
390    // get xhtab cluster and local pointer
391    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
392    xhtab_t * xhtab_ptr = GET_PTR( xhtab_xp );
393
394    // release the lock protecting hash table
395    remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
396}
397
398/////////////////////////////////////////
399xptr_t xhtab_get_first( xptr_t xhtab_xp )
400{
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
408
409    // get xhtab cluster and local pointer
410    xhtab_cxy = GET_CXY( xhtab_xp );
411    xhtab_ptr = GET_PTR( xhtab_xp );
412
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 ) );
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
428                item_xp = item_from_xlist( xlist_xp );
429
430            // register item in hash table header
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 );
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{
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
453
454    uint32_t current_index;
455    xptr_t   current_xlist_xp;
456
457    // get xhtab cluster and local pointer
458    xhtab_cxy = GET_CXY( xhtab_xp );
459    xhtab_ptr = GET_PTR( xhtab_xp );
460
461    // get current item pointers
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 ) ); 
464
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 ) );
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
475        if( index == current_index ) xlist_xp = xlist_next( root_xp , current_xlist_xp );
476        else                         xlist_xp = xlist_next( root_xp , root_xp );
477
478        if( xlist_xp != XPTR_NULL )  // next item found
479        {
480            // get extended pointer on item containing the xlist entry
481                item_xp = item_from_xlist( xlist_xp );
482
483            // register item in hash table header
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 );
486
487            return item_xp;
488        }
489    }
490           
491    // item not found
492    return XPTR_NULL;
493
494} // end xhtab_get_next()
495
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
507
508    // get xhtab cluster and local pointer
509    xhtab_cxy = GET_CXY( xhtab_xp );
510    xhtab_ptr = GET_PTR( xhtab_xp );
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.