/* * xhtab.c - Remote access embedded hash table implementation. * * Author Alain Greiner (2016) * * Copyright (c) UPMC Sorbonne Universites * * This file is part of ALMOS-MKH. * * ALMOS-MKH is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation; version 2.0 of the License. * * ALMOS-MKH is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with ALMOS-MKH; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #include #include #include #include #include #include #include #include #include #include /////////////////////////////////////////////////////////////////////////////////////// // This static function s called by the xhtab_lookup() and xhtab_register() functions. // It scan one sub-list identified by to find an item identified by . // The hash table is identified by and local pointer . // The sub-list is not modified, but the readlock must have been taken by the caller. /////////////////////////////////////////////////////////////////////////////////////// // @ cxy : hash table cluster. // @ xhtab_xp : hash table local pointer. // @ index : index of sub-list to be scanned. // @ key : local pointer on item identifier. /////////////////////////////////////////////////////////////////////////////////////// static xptr_t xhtab_scan( cxy_t cxy, xhtab_t * xhtab, uint32_t index, void * key ) { xptr_t xlist_xp; // extended pointer on xlist_entry_t (iterator) xptr_t item_xp; // extended pointer on found item (return value) // scan the sub-list[index] XLIST_FOREACH( XPTR( cxy , &xhtab->roots[index] ) , xlist_xp ) { if ( xhtab->compare( xlist_xp , key , &item_xp ) ) return item_xp; } // no matching item found return XPTR_NULL; } ///////////////////////////////// void xhtab_init( xhtab_t * xhtab, uint32_t type ) { uint32_t i; // initialize readlock remote_rwlock_init( XPTR( local_cxy , &xhtab->lock) ); xhtab->items = 0; if( type == XHTAB_DENTRY_TYPE ) { hal_remote_spt( XPTR( local_cxy , &xhtab->compare ) , &xhtab_dentry_compare ); hal_remote_spt( XPTR( local_cxy , &xhtab->index ) , &xhtab_dentry_index ); } else { printk("\n[PANIC] in %s : illegal item type\n", __FUNCTION__ ); hal_core_sleep(); } for( i=0 ; i < HASHTAB_SIZE ; i++ ) { xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) ); } } /////////////////////////////////////// void xhtab_register( xptr_t xhtab_xp, void * key, xptr_t xlist_xp ) { // get xhtab cluster and local pointer cxy_t xhtab_cxy = GET_CXY( xhtab_xp ); xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp ); // compute index from key uint32_t index = xhtab_ptr->index( key ); // take the lock protecting hash table remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); // register item in hash table xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp ); // update number of registered items hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 ); // release the lock protecting hash table remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); } // end xhtab_register() ///////////////////////////////////// void xhtab_remove( xptr_t xhtab_xp, void * key ) { // get xhtab cluster and local pointer cxy_t xhtab_cxy = GET_CXY( xhtab_xp ); xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp ); // take the lock protecting hash table remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); // compute index from key uint32_t index = xhtab_ptr->index( key ); // get extended pointer on item to remove xptr_t item_xp = xhtab_scan( xhtab_cxy , xhtab_ptr , index , key ); if( item_xp == XPTR_NULL ) // do nothing if not found { // release the lock protecting hash table remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); } else // remove item if found { // get item cluster and local pointer cxy_t item_cxy = GET_CXY( item_xp ); vfs_dentry_t * item_ptr = (vfs_dentry_t *)GET_PTR( item_xp ); // remove item from hash table <=> unlink xlist_entry_t xlist_unlink( XPTR( item_cxy , &item_ptr->xlist ) ); // update number of registered items hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 ); // release the lock protecting hash table remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); } } // end xhtab_unregister() ///////////////////////////////////////// xptr_t xhtab_lookup( xptr_t xhtab_xp, void * key ) { xptr_t item_xp; // get xhtab cluster and local pointer cxy_t xhtab_cxy = GET_CXY( xhtab_xp ); xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp ); // compute index from key uint32_t index = xhtab_ptr->index( key ); // take the lock protecting hash table remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); // scan sub-list item_xp = xhtab_scan( xhtab_cxy , xhtab_ptr , index , key ); // release the lock protecting hash table remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); return item_xp; } // end xhtab_lookup() ///////////////////////////////////////// uint32_t xhtab_dentry_index( void * key ) { char * str = key; uint32_t index = 0; while( *str ) index = index + (*(str++) ^ index); return index % HASHTAB_SIZE; } /////////////////////////////////////////////// bool_t xhtab_dentry_compare( xptr_t xlist_xp, void * key, xptr_t * item_xp ) { char tested_name[256]; // local copy of name stored in remote hash table char * searched_name = key; // local pointer on searched name // compute name length uint32_t length = strlen( searched_name ); // get extended pointer on dentry containing the xlist_entry_t xptr_t dentry_xp = XLIST_ELEMENT( xlist_xp , vfs_dentry_t , xlist ); // get dentry cluster and local pointer cxy_t dentry_cxy = GET_CXY( dentry_xp ); vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( dentry_xp ); // make a local copy of remote dentry name hal_remote_memcpy( XPTR( local_cxy , tested_name ) , XPTR( dentry_cxy , dentry_ptr->name ) , length ); // check matching / return if match if( strcmp( tested_name , searched_name ) == 0 ) { return true; *item_xp = dentry_xp; } else { return false; } } //////////////////////////////////////// uint32_t xhtab_inode_index( void * key ) { uint32_t * inum = key; return (((*inum) >> 16) ^ ((*inum) & 0xFFFF)) % HASHTAB_SIZE; } /////////////////////////////////////////////// bool_t xhtab_inode_compare( xptr_t xlist_xp, void * key, xptr_t * item_xp ) { uint32_t * searched_inum = key; uint32_t tested_inum; // get extended pointer on inode containing the xlist_entry_t xptr_t inode_xp = XLIST_ELEMENT( xlist_xp , vfs_inode_t , xlist ); // get inode cluster and local pointer cxy_t inode_cxy = GET_CXY( inode_xp ); vfs_inode_t * inode_ptr = (vfs_inode_t *)GET_PTR( inode_xp ); // get tested inode inum tested_inum = hal_remote_lw( XPTR( inode_cxy , &inode_ptr->inum ) ); // check matching / return if match if( tested_inum == *searched_inum ) { return true; *item_xp = inode_xp; } else { return false; } }