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

/*
 * xhtab.c - Remote access embedded hash table implementation.
 * 
 * Author     Alain Greiner   (2016,2017,2018,2019)
 *
 * 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 <kernel_config.h>
#include <hal_kernel_types.h>
#include <hal_special.h>
#include <hal_remote.h>
#include <xlist.h>
#include <remote_busylock.h>
#include <string.h>
#include <printk.h>
#include <xhtab.h>
#include <vfs.h>


///////////////////////////////////////////////////////////////////////////////////////////
// Item type specific functions (four functions for each item type).
// Example below is for <vfs_dentry_t> where the identifier is the dentry name.
///////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////
// XHTAB_DENTRY_TYPE
// This functions compute the hash index from the key, that is the directory entry name.
// In this implementation, the index value is simply the ASCII code of the first
// character, to provide an approximate lexicographic order. 
///////////////////////////////////////////////////////////////////////////////////////////
// @ key      : local pointer on name.
// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
///////////////////////////////////////////////////////////////////////////////////////////
static uint32_t xhtab_dentry_index_from_key( void * key )
{
        char     * name  = key;

        return (name[0] % XHASHTAB_SIZE);
/*
    uint32_t   index = 0;
        while( *name )
    {
        index = index + (*(name++) ^ index);
    }
        return index % XHASHTAB_SIZE;
*/

} 

///////////////////////////////////////////////////////////////////////////////////////////
// XHTAB_DENTRY_TYPE
// This functions returns the extended pointer on the item, from the extended pointer 
// on xlist contained in the item.
///////////////////////////////////////////////////////////////////////////////////////////
// @ xlist_xp      : extended pointer on embedded xlist entry.
// @ return the extended pointer on the dentry containing this xlist entry.
///////////////////////////////////////////////////////////////////////////////////////////
static xptr_t xhtab_dentry_item_from_xlist( xptr_t xlist_xp )
{
    return XLIST_ELEMENT( xlist_xp , vfs_dentry_t , children );
}

////////////////////////////////////////////////////////////////////////////////////////////
// XHTAB_DENTRY_TYPE
// This function compares the identifier of an item to a given <key>. 
// it returns true when the directory name matches the name pointed by the <key> argument.
////////////////////////////////////////////////////////////////////////////////////////////
// @ item_xp   : extended pointer on item.
// @ key       : pointer on searched item identifier.
// returns true if given name matches directory entry name.
////////////////////////////////////////////////////////////////////////////////////////////
static bool_t xhtab_dentry_item_match_key( xptr_t    item_xp,
                                           void    * key )
{
    char name[CONFIG_VFS_MAX_NAME_LENGTH];

    // get dentry cluster and local pointer
    cxy_t          dentry_cxy = GET_CXY( item_xp );
    vfs_dentry_t * dentry_ptr = GET_PTR( item_xp );

    // make a local copy of directory entry name
    hal_remote_strcpy( XPTR( local_cxy , name ) ,
                       XPTR( dentry_cxy , &dentry_ptr->name ) );

    return( strcmp( name , (char*)key ) == 0 );
}

////////////////////////////////////////////////////////////////////////////////////////////
// XHTAB_DENTRY_TYPE
// This function print the item key, that is the name for a vfs_dentry_t.
////////////////////////////////////////////////////////////////////////////////////////////
// @ item_xp   : extended pointer on item.
////////////////////////////////////////////////////////////////////////////////////////////
static void xhtab_dentry_item_print_key( xptr_t item_xp )
{
    char name[CONFIG_VFS_MAX_NAME_LENGTH];

    // get dentry cluster and local pointer
    cxy_t          dentry_cxy = GET_CXY( item_xp );
    vfs_dentry_t * dentry_ptr = GET_PTR( item_xp );
    
    // make a local copy of directory entry name
    hal_remote_strcpy( XPTR( local_cxy , name ) ,
                       XPTR( dentry_cxy , &dentry_ptr->name ) );

    // print dentry name
    printk("%s , ", name );
}                       

////////////////////////////////////////////////////////////////////////////////////////
//         Generic access functions
////////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////
void xhtab_init( xhtab_t          * xhtab,
                 xhtab_item_type_t  type )
{
        uint32_t i;

    // initialize lock
    remote_busylock_init( XPTR( local_cxy , &xhtab->lock), LOCK_XHTAB_STATE );

    xhtab->items            = 0;
    xhtab->current_index    = 0;
    xhtab->current_xlist_xp = XPTR_NULL;

    if( type == XHTAB_DENTRY_TYPE )
    {
        xhtab->item_match_key  = &xhtab_dentry_item_match_key;
        xhtab->index_from_key  = &xhtab_dentry_index_from_key;
        xhtab->item_from_xlist = &xhtab_dentry_item_from_xlist;
        xhtab->item_print_key  = &xhtab_dentry_item_print_key;
    }
    else
    {
        assert( false , "illegal item type\n" );
    }

#if DEBUG_XHTAB
printk("\n[%s] for xhtab (%x,%x)\n"
" - index_from_key  = %x (@ %x)\n"
" - item_match_key  = %x (@ %x)\n"
" - item_from_xlist = %x (@ %x)\n",
__FUNCTION__, local_cxy, xhtab,
xhtab->index_from_key , &xhtab->index_from_key,
xhtab->item_match_key , &xhtab->item_match_key,
xhtab->item_from_xlist, &xhtab->item_from_xlist );
#endif

        for( i=0 ; i < XHASHTAB_SIZE ; i++ )
    {
                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );

#if (DEBUG_XHTAB & 1)
printk("\n - initialize root[%d] / %x\n", i , &xhtab->roots[i] ); 
#endif

    }  

}  // end xhtab_init()

/////////////////////////////////////////////////////////////////////////////////////////////
// This static function traverse the subset identified by the <index> argument
// to find an item identified by the <key> argument.
/////////////////////////////////////////////////////////////////////////////////////////////
// @ xhtab_xp  : extended pointer on the xhtab descriptor.
// @ index     : subset index.
// @ key       : searched key value.
// @ return  extended pointer on the found item if success / return XPTR_NULL if not found.
/////////////////////////////////////////////////////////////////////////////////////////////
static xptr_t xhtab_scan( xptr_t    xhtab_xp,
                          uint32_t  index,
                          void    * key )
{
    xptr_t              xlist_xp;           // xlist_entry_t (iterator)
    xptr_t              item_xp;            // associated item
    xhtab_t           * xhtab_ptr;          // hash table local pointer
    cxy_t               xhtab_cxy;          // hash table cluster
    item_from_xlist_t * item_from_xlist;    // function pointer
    item_match_key_t  * item_match_key;     // function pointer

    // get hash table cluster and local pointer
    xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_ptr = GET_PTR( xhtab_xp );

    // get pointer on "item_from_xlist" function
    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
                                                           &xhtab_ptr->item_from_xlist ) );
    // get pointer on "item_match_key" function
    item_match_key = (item_match_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
                                                         &xhtab_ptr->item_match_key ) );

    // scan sub-list[index]
    XLIST_FOREACH( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp )
    {
        // get extended pointer on item containing the xlist entry
            item_xp = item_from_xlist( xlist_xp );

        // check matching
        if( item_match_key( item_xp , key ) ) return item_xp;
    }

    // No matching item found
    return XPTR_NULL;

}  // end xhtab_scan()

///////////////////////////////////////
error_t xhtab_insert( xptr_t   xhtab_xp,
                      void   * key,
                      xptr_t   xlist_xp )
{
    xptr_t             item_xp;
    uint32_t           index;
    cxy_t              xhtab_cxy;
    xhtab_t          * xhtab_ptr;
    index_from_key_t * index_from_key;     // function pointer
    
    // get xhtab cluster and local pointer 
    xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_ptr = GET_PTR( xhtab_xp );

#if DEBUG_XHTAB
printk("\n[%s] enter / xhtab (%x,%x) / key = <%s> / cycle %d\n",
__FUNCTION__, xhtab_cxy, xhtab_ptr, key, (uint32_t)hal_get_cycles() );
#endif

    // build extended pointer on xhtab lock
    xptr_t lock_xp = XPTR( xhtab_cxy , &xhtab_ptr->lock );

    // get pointer on "index_from_key" function
    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
                                                         &xhtab_ptr->index_from_key ) );
#if DEBUG_XHTAB
printk("\n[%s] remote = %x / direct = %x / @ = %x\n",
__FUNCTION__, index_from_key, xhtab_ptr->index_from_key, &xhtab_ptr->index_from_key );
#endif

    // compute index from key
        index = index_from_key( key );

#if DEBUG_XHTAB
printk("\n[%s] index = %x\n", __FUNCTION__, index );
#endif

    // take the lock protecting hash table
    remote_busylock_acquire( lock_xp );

    // search a matching item in subset
    item_xp = xhtab_scan( xhtab_xp , index , key );

    if( item_xp != XPTR_NULL )    // error if item already registered
    {
        // release the lock protecting hash table
        remote_busylock_release( lock_xp );

        return -1;
    }
    else                          // insert item if not found
    {
        // 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_busylock_release( lock_xp );
    
#if DEBUG_XHTAB
printk("\n[%s] success / <%s>\n", __FUNCTION__, key );
#endif

        return 0;
    }
}  // end xhtab_insert()

///////////////////////////////////////
bool_t xhtab_remove( xptr_t   xhtab_xp,
                     void   * key,
                     xptr_t   xlist_entry_xp )
{
    xptr_t             item_xp;
    uint32_t           index;
    cxy_t              xhtab_cxy;
    xhtab_t          * xhtab_ptr;
    index_from_key_t * index_from_key;     // function pointer

    // get xhtab cluster and local pointer 
    xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_ptr = GET_PTR( xhtab_xp );

    // get pointer on "index_from_key" function
    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
                                                         &xhtab_ptr->index_from_key ) );
    // compute index from key
        index = index_from_key( key );

    // take the lock protecting hash table
    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );

    // get extended pointer on item to remove
    item_xp = xhtab_scan( xhtab_xp , index , key );

    if( item_xp == XPTR_NULL )    // return error if not found
    {
        // release the lock protecting hash table
        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );

        return false;
    }
    else                          // remove item if found
    {
        // remove item from hash table <=> unlink xlist_entry_t
        xlist_unlink( xlist_entry_xp );

        // update number of registered items
        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 );

        // release the lock protecting hash table
        remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );

        return true;
    }
}  // end xhtab_remove()

/////////////////////////////////////////
xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
                      void    * key )
{
    xptr_t             item_xp;
    uint32_t           index;
    cxy_t              xhtab_cxy;
    xhtab_t          * xhtab_ptr;
    index_from_key_t * index_from_key;     // function pointer

    // get xhtab cluster and local pointer 
    xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_ptr = GET_PTR( xhtab_xp );

    // get pointer on "index_from_key" function
    index_from_key = (index_from_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
                                                         &xhtab_ptr->index_from_key ) );
    // compute index from key
        index = index_from_key( key );
    
#if DEBUG_XHTAB
printk("\n[%s] enter / %s\n", __FUNCTION__, key );
#endif

    // take the lock protecting hash table
    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
    
#if DEBUG_XHTAB
printk("\n[%s] after lock acquire / %s\n", __FUNCTION__, key );
#endif

    // scan sub-list
    item_xp = xhtab_scan( xhtab_xp , index , key );

#if DEBUG_XHTAB
printk("\n[%s] after xhtab scan / %s\n", __FUNCTION__, key );
#endif

    // release the lock protecting hash table
    remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );

#if DEBUG_XHTAB
printk("\n[%s] after lock release / %s\n", __FUNCTION__, key );
#endif

    return item_xp;

}  // end xhtab_lookup()

//////////////////////////////////
void xhtab_lock( xptr_t xhtab_xp )
{
    // get xhtab cluster and local pointer 
    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_t * xhtab_ptr = GET_PTR( xhtab_xp );

    // take the lock protecting hash table
    remote_busylock_acquire( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
}

////////////////////////////////////
void xhtab_unlock( xptr_t xhtab_xp )
{
    // get xhtab cluster and local pointer 
    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_t * xhtab_ptr = GET_PTR( xhtab_xp );

    // release the lock protecting hash table
    remote_busylock_release( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
}

/////////////////////////////////////////
xptr_t xhtab_get_first( xptr_t xhtab_xp )
{
    uint32_t            index;
    cxy_t               xhtab_cxy;
    xhtab_t           * xhtab_ptr;
    xptr_t              xlist_xp;
    xptr_t              item_xp;
    xptr_t              root_xp;
    item_from_xlist_t * item_from_xlist;   // function pointer

    // get xhtab cluster and local pointer 
    xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_ptr = GET_PTR( xhtab_xp );

    // get pointer on "item_from_xlist" function
    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
                                                           &xhtab_ptr->item_from_xlist ) );
    //loop on subsets
    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
    {
        // get root of subset
        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );

        // get first item
        xlist_xp = xlist_next( root_xp , root_xp );

        if( xlist_xp != XPTR_NULL )  // first item found
        {
            // get extended pointer on item containing the xlist entry
                item_xp = item_from_xlist( xlist_xp );

            // register item in hash table header
            hal_remote_s32 ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
            hal_remote_s64( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );

            return item_xp;
        }
    }
            
    // item not found
    return XPTR_NULL;

} // end xhtab_get_first()
    
////////////////////////////////////////
xptr_t xhtab_get_next( xptr_t xhtab_xp )
{
    uint32_t            index;
    cxy_t               xhtab_cxy;
    xhtab_t           * xhtab_ptr;
    xptr_t              xlist_xp;
    xptr_t              item_xp;
    xptr_t              root_xp;
    item_from_xlist_t * item_from_xlist;   // function pointer

    uint32_t current_index;
    xptr_t   current_xlist_xp;

    // get xhtab cluster and local pointer 
    xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_ptr = GET_PTR( xhtab_xp );

    // get current item pointers
    current_index    = hal_remote_l32 ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) ); 
    current_xlist_xp = hal_remote_l64( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) ); 

    // get pointer on "item_from_xlist" function
    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
                                                           &xhtab_ptr->item_from_xlist ) );
    //loop on subsets
    for( index = current_index ; index < XHASHTAB_SIZE ; index++ )
    {
        // get root of subset 
        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );

        // get next item
        if( index == current_index ) xlist_xp = xlist_next( root_xp , current_xlist_xp );
        else                         xlist_xp = xlist_next( root_xp , root_xp );

        if( xlist_xp != XPTR_NULL )  // next item found
        {
            // get extended pointer on item containing the xlist entry
                item_xp = item_from_xlist( xlist_xp );

            // register item in hash table header
            hal_remote_s32 ( XPTR( xhtab_cxy , &xhtab_ptr->current_index ) , index );
            hal_remote_s64( XPTR( xhtab_cxy , &xhtab_ptr->current_xlist_xp ) , xlist_xp );

            return item_xp;
        }
    }
            
    // item not found
    return XPTR_NULL;

} // end xhtab_get_next()

/////////////////////////////////////
void xhtab_display( xptr_t xhtab_xp )
{
    uint32_t            index;
    cxy_t               xhtab_cxy;
    xhtab_t           * xhtab_ptr;
    xptr_t              root_xp;
    xptr_t              iter_xp;
    xptr_t              item_xp;
    item_from_xlist_t * item_from_xlist;   // function pointer
    item_print_key_t  * item_print_key;    // function pointer

    // get xhtab cluster and local pointer 
    xhtab_cxy = GET_CXY( xhtab_xp );
    xhtab_ptr = GET_PTR( xhtab_xp );

    // get pointer on "item_from_xlist" function
    item_from_xlist = (item_from_xlist_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
                                                           &xhtab_ptr->item_from_xlist ) );
    // get pointer on "item_print_key" function
    item_print_key = (item_print_key_t *)hal_remote_lpt( XPTR( xhtab_cxy , 
                                                         &xhtab_ptr->item_print_key ) );
    //loop on subsets
    for( index = 0 ; index < XHASHTAB_SIZE ; index++ )
    {
        printk(" index = %d : ", index );

        // get root of subset 
        root_xp = XPTR( xhtab_cxy , &xhtab_ptr->roots[index] );

        // loop on xlist
        XLIST_FOREACH( root_xp , iter_xp )
        {
            // get item from xlist
            item_xp = item_from_xlist( iter_xp );
            
            // print item identifier
            item_print_key( item_xp );
        }

        printk("\n");
    }
}  // end xhtab_display()