Ignore:
Timestamp:
Jun 18, 2017, 10:06:41 PM (4 years ago)
Author:
alain
Message:

Introduce syscalls.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/kernel/libk/xhtab.c

    r14 r23  
    22 * xhtab.c - Remote access embedded hash table implementation.
    33 *
    4  * Author     Alain Greiner          (2016)
     4 * Author     Alain Greiner          (2016,2017)
    55 *
    66 * Copyright (c) UPMC Sorbonne Universites
     
    3434
    3535
    36 ///////////////////////////////////////////////////////////////////////////////////////
    37 // This static function s called by the xhtab_lookup() and xhtab_register() functions.
    38 // It scan one sub-list identified by  <index> to find an item  identified by <key>.
    39 // The hash table is identified by <cxy> and local pointer <xhtab>.
     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>.
    4063// The sub-list is not modified, but the readlock must have been taken by the caller.
    41 ///////////////////////////////////////////////////////////////////////////////////////
    42 // @ cxy       : hash table cluster.
    43 // @ xhtab_xp  : hash table local pointer.
     64////////////////////////////////////////////////////////////////////////////////////////////
     65// @ xhtab_xp  : extended pointer on hash table.
    4466// @ index     : index of sub-list to be scanned.
    4567// @ key       : local pointer on item identifier.
    46 ///////////////////////////////////////////////////////////////////////////////////////
    47 static xptr_t xhtab_scan( cxy_t     cxy,
    48                           xhtab_t * xhtab,
    49                           uint32_t  index,
    50                           void    * key )
    51 {
    52     xptr_t   xlist_xp;    // extended pointer on xlist_entry_t (iterator)
    53     xptr_t   item_xp;     // extended pointer on found item (return value)
     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 )
     75{
     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 );
    5494   
    55     // scan the sub-list[index]
    56         XLIST_FOREACH( XPTR( cxy , &xhtab->roots[index] ) , xlist_xp )
    57         {
    58         if ( xhtab->compare( xlist_xp , key , &item_xp ) ) return item_xp;
    59     }
    60 
    61     // no matching item found
    62         return XPTR_NULL;
     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;
     102    }
     103
     104    // No matching item found
     105    return XPTR_NULL;
    63106}
    64107
    65 /////////////////////////////////
    66 void xhtab_init( xhtab_t * xhtab,
    67                  uint32_t  type )
     108////////////////////////////////////////////////////////////////////////////////////////
     109//         Generic access functions
     110////////////////////////////////////////////////////////////////////////////////////////
     111
     112//////////////////////////////////////////
     113void xhtab_init( xhtab_t          * xhtab,
     114                 xhtab_item_type_t  type )
    68115{
    69116        uint32_t i;
     
    76123    if( type == XHTAB_DENTRY_TYPE )
    77124    {
    78         hal_remote_spt( XPTR( local_cxy , &xhtab->compare ) , &xhtab_dentry_compare );
    79         hal_remote_spt( XPTR( local_cxy , &xhtab->index   ) , &xhtab_dentry_index   );
     125        xhtab->scan  = &xhtab_dentry_scan;
     126        xhtab->index = &xhtab_dentry_index;
    80127    }
    81128    else
     
    92139
    93140///////////////////////////////////////
    94 void xhtab_register( xptr_t   xhtab_xp,
    95                      void   * key,
    96                      xptr_t   xlist_xp )
    97 {
     141error_t xhtab_insert( xptr_t   xhtab_xp,
     142                      void   * key,
     143                      xptr_t   xlist_xp )
     144{
     145
     146printk("\n                @@@ xhtab_insert : 0 / name = %s / xhtab_xp = %l / xlist_xp = %l\n",
     147       key , xhtab_xp , xlist_xp );
     148
    98149    // get xhtab cluster and local pointer
    99150    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
     
    103154        uint32_t index = xhtab_ptr->index( key );
    104155
     156printk("\n                @@@ xhtab_insert : 1 / name = %s / index = %d\n",
     157       key , index );
     158
    105159    // take the lock protecting hash table
    106160    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
    107161
    108     // register item in hash table
    109         xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp );
    110 
    111     // update number of registered items
    112     hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 );
    113 
    114     // release the lock protecting hash table
    115     remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
    116 
    117 }  // end xhtab_register()
     162    // search a matching item
     163    xptr_t item_xp = xhtab_ptr->scan( xhtab_xp , index , key );
     164
     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 ) );
     169
     170printk("\n                @@@ xhtab_insert : 2 / name = %s / item_xp = %l\n",
     171       key , item_xp );
     172
     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 );
     179
     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()
    118192
    119193/////////////////////////////////////
    120 void xhtab_remove( xptr_t   xhtab_xp,
    121                    void   * key )
     194error_t xhtab_remove( xptr_t   xhtab_xp,
     195                      void   * key,
     196                      xptr_t   xlist_entry_xp )
    122197{
    123198    // get xhtab cluster and local pointer
     
    125200    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
    126201
     202    // compute index from key
     203        uint32_t index = xhtab_ptr->index( key );
     204
    127205    // take the lock protecting hash table
    128206    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
    129207
    130     // compute index from key
    131         uint32_t index = xhtab_ptr->index( key );
    132 
    133208    // get extended pointer on item to remove
    134     xptr_t item_xp = xhtab_scan( xhtab_cxy , xhtab_ptr , index , key );
    135 
    136     if( item_xp == XPTR_NULL )    // do nothing if not found
    137     {
    138         // release the lock protecting hash table
    139         remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
     209    xptr_t item_xp = xhtab_ptr->scan( xhtab_xp , index , key );
     210
     211    if( item_xp == XPTR_NULL )    // error if not found
     212    {
     213        // release the lock protecting hash table
     214        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
     215
     216        return EINVAL;
    140217    }
    141218    else                          // remove item if found
    142219    {
    143         // get item cluster and local pointer
    144         cxy_t          item_cxy = GET_CXY( item_xp );
    145         vfs_dentry_t * item_ptr = (vfs_dentry_t *)GET_PTR( item_xp );
    146 
    147220        // remove item from hash table <=> unlink xlist_entry_t
    148         xlist_unlink( XPTR( item_cxy , &item_ptr->xlist ) );
     221        xlist_unlink( xlist_entry_xp );
    149222
    150223        // update number of registered items
     
    153226        // release the lock protecting hash table
    154227        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
    155     }
    156 }  // end xhtab_unregister()
     228
     229        return 0;
     230    }
     231}  // end xhtab_remove()
    157232
    158233/////////////////////////////////////////
     
    173248
    174249    // scan sub-list
    175     item_xp = xhtab_scan( xhtab_cxy , xhtab_ptr , index , key );
     250    item_xp = xhtab_ptr->scan( xhtab_xp , index , key );
    176251
    177252    // release the lock protecting hash table
     
    183258
    184259
    185 
    186 /////////////////////////////////////////
    187 uint32_t xhtab_dentry_index( void * key )
    188 {
    189         char    * str   = key;
    190         uint32_t  index = 0;
    191  
    192         while( *str ) index = index + (*(str++) ^ index);
    193 
    194         return index % HASHTAB_SIZE;
    195 }
    196 
    197 ///////////////////////////////////////////////
    198 bool_t xhtab_dentry_compare( xptr_t   xlist_xp,
    199                              void   * key,
    200                              xptr_t * item_xp )
    201 {
    202     char   tested_name[256];      // local copy of name stored in remote hash table
    203 
    204     char * searched_name = key;   // local pointer on searched name
    205 
    206     // compute name length
    207     uint32_t length = strlen( searched_name );
    208 
    209     // get extended pointer on dentry containing the xlist_entry_t
    210         xptr_t dentry_xp = XLIST_ELEMENT( xlist_xp , vfs_dentry_t , xlist );
    211 
    212     // get dentry cluster and local pointer
    213     cxy_t          dentry_cxy = GET_CXY( dentry_xp );
    214     vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( dentry_xp );
    215    
    216     // make a local copy of remote dentry name
    217     hal_remote_memcpy( XPTR( local_cxy  , tested_name ) ,
    218                        XPTR( dentry_cxy , dentry_ptr->name ) , length );
    219 
    220     // check matching / return if match
    221     if( strcmp( tested_name , searched_name ) == 0 )
    222     {
    223         return true;
    224         *item_xp = dentry_xp;
    225     }
    226     else
    227     {
    228         return false;
    229     }
    230 }
    231 
    232 
    233  
    234 ////////////////////////////////////////
    235 uint32_t xhtab_inode_index( void * key )
    236 {
    237         uint32_t * inum = key;
    238 
    239         return (((*inum) >> 16) ^ ((*inum) & 0xFFFF)) % HASHTAB_SIZE;
    240 }
    241 
    242 ///////////////////////////////////////////////
    243 bool_t xhtab_inode_compare( xptr_t   xlist_xp,
    244                             void   * key,
    245                             xptr_t * item_xp )
    246 {
    247     uint32_t * searched_inum = key;
    248     uint32_t   tested_inum;   
    249 
    250     // get extended pointer on inode containing the xlist_entry_t
    251         xptr_t inode_xp = XLIST_ELEMENT( xlist_xp , vfs_inode_t , xlist );
    252 
    253     // get inode cluster and local pointer
    254     cxy_t         inode_cxy = GET_CXY( inode_xp );
    255     vfs_inode_t * inode_ptr = (vfs_inode_t *)GET_PTR( inode_xp );
    256    
    257     // get tested inode inum
    258     tested_inum = hal_remote_lw( XPTR( inode_cxy , &inode_ptr->inum ) );
    259 
    260     // check matching / return if match
    261     if( tested_inum == *searched_inum )
    262     {
    263         return true;
    264         *item_xp = inode_xp;
    265     }
    266     else
    267     {
    268         return false;
    269     }
    270 }
    271 
Note: See TracChangeset for help on using the changeset viewer.