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

Last change on this file since 26 was 23, checked in by alain, 7 years ago

Introduce syscalls.

File size: 8.8 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>
[1]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
[23]36///////////////////////////////////////////////////////////////////////////////////////////
37// Item type specific (static) functions (two functions for each item type).
38// - for type <vfs_dentry_t>, identifier is the name field.
39///////////////////////////////////////////////////////////////////////////////////////////
40
41///////////////////////////////////////////////////////////////////////////////////////////
42// These static functions compute the hash index from the key.
43///////////////////////////////////////////////////////////////////////////////////////////
44// @ key      : local pointer on key.
45// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
46///////////////////////////////////////////////////////////////////////////////////////////
47
48/////////////////////////////////////////
49uint32_t xhtab_dentry_index( void * key )
50{
51        char     * name  = key;
52        uint32_t   index = 0;
53        while( *name )
54    {
55        index = index + (*(name++) ^ index);
56    }
57        return index % HASHTAB_SIZE;
58} 
59
60////////////////////////////////////////////////////////////////////////////////////////////
61// These static function are used by xhtab_lookup(), xhtab_insert(), xhtab_remove().
62// They scan one sub-list identified by  <index> to find an item  identified by <key>.
[1]63// The sub-list is not modified, but the readlock must have been taken by the caller.
[23]64////////////////////////////////////////////////////////////////////////////////////////////
65// @ xhtab_xp  : extended pointer on hash table.
[1]66// @ index     : index of sub-list to be scanned.
67// @ key       : local pointer on item identifier.
[23]68// return an extended pointer on item if found / return XPTR_NULL if not found.
69////////////////////////////////////////////////////////////////////////////////////////////
70
71////////////////////////////////////////////////////
72static xptr_t xhtab_dentry_scan( xptr_t    xhtab_xp,
73                                 uint32_t  index,
74                                 void    * key )
[1]75{
[23]76    xptr_t    xlist_xp;                                 // xlist_entry_t (iterator)
77    xhtab_t * xhtab_ptr;                                // hash table local pointer
78    cxy_t     xhtab_cxy;                                // hash table cluster
79    char      local_name[CONFIG_VFS_MAX_NAME_LENGTH];   // local copy of dentry name
80
81    // get hash table cluster and local pointer
82    xhtab_cxy = GET_CXY( xhtab_xp );
83    xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
84
85    // scan sub-list[index]
86    XLIST_FOREACH( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp )
87    {
88        // get extended pointer on dentry containing the xlist_entry_t
89            xptr_t dentry_xp = XLIST_ELEMENT( xlist_xp , vfs_dentry_t , xlist );
90
91        // get dentry cluster and local pointer
92        cxy_t          dentry_cxy = GET_CXY( dentry_xp );
93        vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( dentry_xp );
[1]94   
[23]95        // make a local copy of dentry name
96        hal_remote_memcpy( XPTR( local_cxy  , local_name ) ,
97                           XPTR( dentry_cxy , dentry_ptr->name ),
98                           CONFIG_VFS_MAX_NAME_LENGTH  );
99
100        // check matching
101        if( strcmp( local_name , (char *)key ) == 0 ) return dentry_xp; 
[1]102    }
103
[23]104    // No matching item found
105    return XPTR_NULL;
[1]106}
107
[23]108////////////////////////////////////////////////////////////////////////////////////////
109//         Generic access functions
110////////////////////////////////////////////////////////////////////////////////////////
111
112//////////////////////////////////////////
113void xhtab_init( xhtab_t          * xhtab,
114                 xhtab_item_type_t  type )
[1]115{
116        uint32_t i;
117
118    // initialize readlock
119    remote_rwlock_init( XPTR( local_cxy , &xhtab->lock) );
120
121    xhtab->items  = 0;
122
123    if( type == XHTAB_DENTRY_TYPE )
124    {
[23]125        xhtab->scan  = &xhtab_dentry_scan;
126        xhtab->index = &xhtab_dentry_index;
[1]127    }
128    else
129    {
130        printk("\n[PANIC] in %s : illegal item type\n", __FUNCTION__ );
131        hal_core_sleep();
132    }
133
134        for( i=0 ; i < HASHTAB_SIZE ; i++ )
135    {
136                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
137    } 
138}
139
140///////////////////////////////////////
[23]141error_t xhtab_insert( xptr_t   xhtab_xp,
142                      void   * key,
143                      xptr_t   xlist_xp )
[1]144{
[23]145
146printk("\n                @@@ xhtab_insert : 0 / name = %s / xhtab_xp = %l / xlist_xp = %l\n",
147       key , xhtab_xp , xlist_xp );
148
[1]149    // get xhtab cluster and local pointer
150    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
151    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
152
153    // compute index from key
154        uint32_t index = xhtab_ptr->index( key );
155
[23]156printk("\n                @@@ xhtab_insert : 1 / name = %s / index = %d\n",
157       key , index );
158
[1]159    // take the lock protecting hash table
160    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
161
[23]162    // search a matching item
163    xptr_t item_xp = xhtab_ptr->scan( xhtab_xp , index , key );
[1]164
[23]165    if( item_xp != XPTR_NULL )    // error if found
166    {
167        // release the lock protecting hash table
168        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
[1]169
[23]170printk("\n                @@@ xhtab_insert : 2 / name = %s / item_xp = %l\n",
171       key , item_xp );
[1]172
[23]173        return EINVAL;
174    }
175    else                          // insert item if not found
176    {
177        // register item in hash table
178            xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp );
[1]179
[23]180        // update number of registered items
181        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 );
182
183        // release the lock protecting hash table
184        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
185
186printk("\n                @@@ xhtab_insert : 3 / name = %s / item_xp = %l\n",
187       key , xhtab_ptr->scan( xhtab_xp , index , key ) );
188
189        return 0;
190    }
191}  // end xhtab_insert()
192
[1]193/////////////////////////////////////
[23]194error_t xhtab_remove( xptr_t   xhtab_xp,
195                      void   * key,
196                      xptr_t   xlist_entry_xp )
[1]197{
198    // get xhtab cluster and local pointer
199    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
200    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
201
[23]202    // compute index from key
203        uint32_t index = xhtab_ptr->index( key );
204
[1]205    // take the lock protecting hash table
206    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
207
208    // get extended pointer on item to remove
[23]209    xptr_t item_xp = xhtab_ptr->scan( xhtab_xp , index , key );
[1]210
[23]211    if( item_xp == XPTR_NULL )    // error if not found
[1]212    {
213        // release the lock protecting hash table
214        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
[23]215
216        return EINVAL;
[1]217    }
218    else                          // remove item if found
219    {
220        // remove item from hash table <=> unlink xlist_entry_t
[23]221        xlist_unlink( xlist_entry_xp );
[1]222
223        // update number of registered items
224        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 );
225
226        // release the lock protecting hash table
227        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
[23]228
229        return 0;
[1]230    }
[23]231}  // end xhtab_remove()
[1]232
233/////////////////////////////////////////
234xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
235                      void    * key )
236{
237    xptr_t  item_xp;
238
239    // get xhtab cluster and local pointer
240    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
241    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
242
243    // compute index from key
244        uint32_t index = xhtab_ptr->index( key );
245
246    // take the lock protecting hash table
247    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
248
249    // scan sub-list
[23]250    item_xp = xhtab_ptr->scan( xhtab_xp , index , key );
[1]251
252    // release the lock protecting hash table
253    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
254
255    return item_xp;
256
257}  // end xhtab_lookup()
258
259
Note: See TracBrowser for help on using the repository browser.