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

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

Bug fix in kernel_init
-This line, and those below, will be ignored--

M params.mk
M kernel_config.h
M Makefile
M hdd/virt_hdd.dmg
M tools/bootloader_tsar/boot.c
M kernel/libk/bits.h
M kernel/libk/elf.c
M kernel/libk/xhtab.c
M kernel/libk/elf.h
M kernel/libk/xhtab.h
M kernel/devices/dev_pic.c
M kernel/mm/vmm.c
M kernel/mm/mapper.c
M kernel/mm/mapper.h
M kernel/vfs/devfs.h
M kernel/vfs/vfs.c
M kernel/vfs/vfs.h
M kernel/vfs/devfs.c
M kernel/kern/chdev.h
M kernel/kern/kernel_init.c
M kernel/kern/process.c
M kernel/kern/process.h
M hal/tsar_mips32/core/hal_remote.c
M hal/tsar_mips32/drivers/soclib_pic.c

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