Changeset 23 for trunk/kernel/libk


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

Introduce syscalls.

Location:
trunk/kernel/libk
Files:
4 added
13 edited
2 moved

Legend:

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

    r11 r23  
    2525#include <hal_types.h>
    2626#include <bits.h>
     27
     28////////////////////////////////////
     29void bitmap_init( bitmap_t * bitmap,
     30                  uint32_t   len )
     31{
     32    uint32_t word;
     33    uint32_t nwords = BITMAP_SIZE( len );
     34    for( word = 0 ; word < nwords ; word++ )
     35    {
     36        bitmap[word] = 0;
     37    }
     38}  // end bitmap_init()
    2739
    2840//////////////////////////////////////////
  • trunk/kernel/libk/bits.h

    r14 r23  
    7878
    7979/**********************************************************************************************
    80  * This macro returns the number of 32 bits words required to register size entries.
     80 * This macro returns the number of 32 bits words required to register <size> entries.
    8181 *********************************************************************************************/
    8282
    8383#define BITMAP_SIZE(size) ( ((size) & 31) ? (((size)>>5) + 1) : ((size)>>5) )
    84  
    85 /**********************************************************************************************
    86  * This macro declare a bitmap data structure. It is actually an array of uint32_t.
    87  * size is the total number of entries in the bitmap.
    88  *********************************************************************************************/
    89 
    90 #define BITMAP( name , size )     uint32_t name[BITMAP_SIZE(size)]
    9184
    9285typedef uint32_t    bitmap_t;
    9386
    94 /**********************************************************************************************
     87/*********************************************************************************************
     88 * This function reset all bits in a bitmap. (array ot 32 bits words).
     89 *********************************************************************************************
     90 * @ bitmap  : pointer on first word in the bitmap.
     91 * @ len     : number of bits to reset.
     92 ********************************************************************************************/
     93void bitmap_init( bitmap_t * bitmap,
     94                  uint32_t   len );
     95
     96/*********************************************************************************************
    9597 * This function set a specific bit in a bitmap.
    96  **********************************************************************************************
     98 *********************************************************************************************
    9799 * @ bitmap  : pointer on the bitmap
    98100 * @ index   : bit index in the bitmap
    99  *********************************************************************************************/
     101 ********************************************************************************************/
    100102extern inline void bitmap_set( bitmap_t * bitmap,
    101103                               uint32_t   index );
    102104
    103 /**********************************************************************************************
     105/*********************************************************************************************
    104106 * This function clear a specific bit in a bitmap.
    105  **********************************************************************************************
     107 *********************************************************************************************
    106108 * @ bitmap  : pointer on the bitmap
    107109 * @ index   : bit index in the bitmap
    108  *********************************************************************************************/
     110 ********************************************************************************************/
    109111extern inline void bitmap_clear( bitmap_t * bitmap,
    110112                                 uint32_t   index );
    111113
    112 /**********************************************************************************************
     114/*********************************************************************************************
    113115 * This function returns a specific bit in a bitmap.
    114  **********************************************************************************************
     116 *********************************************************************************************
    115117 * @ bitmap  : pointer on the bitmap
    116118 * @ index   : bit index in the bitmap
    117  * @ returns tru if bitmap[index] is set
    118  *********************************************************************************************/
     119 * @ returns true if bitmap[index] is set
     120 ********************************************************************************************/
    119121extern inline bool_t bitmap_state( bitmap_t * bitmap,
    120122                                   uint32_t   index );
    121123
    122 /**********************************************************************************************
     124/*********************************************************************************************
    123125 * This function set a range of bits in a bitmap : [index ... (index + len)[
    124  **********************************************************************************************
     126 *********************************************************************************************
    125127 * @ bitmap  : pointer on the bitmap
    126128 * @ index   : first bit index in the bitmap
    127129 * @ len     : number of bits to set
    128  *********************************************************************************************/
     130 ********************************************************************************************/
    129131extern void bitmap_set_range( bitmap_t * bitmap,
    130132                              uint32_t   index,
    131133                              uint32_t   len );
    132134
    133 /**********************************************************************************************
     135/*********************************************************************************************
    134136 * This function reset a range of bits in a bitmap : [index ... (index + len)[
    135  **********************************************************************************************
     137 *********************************************************************************************
    136138 * @ bitmap  : pointer on the bitmap
    137139 * @ index   : first bit index in the bitmap
    138140 * @ len     : number of bits to clear
    139  *********************************************************************************************/
     141 ********************************************************************************************/
    140142extern void bitmap_clear_range( bitmap_t * bitmap,
    141143                                uint32_t   index,
    142144                                uint32_t   len );
    143145
    144 /**********************************************************************************************
     146/*********************************************************************************************
    145147 * This function returns the index of first bit set in a bitmap, starting from index.
    146  **********************************************************************************************
     148 *********************************************************************************************
    147149 * @ bitmap  : pointer on the bitmap
    148150 * @ index   : first bit to analyse in the bitmap
    149151 * @ size    : number of bits to analyse in bitmap
    150152 * @ returns index if found / returns 0xFFFFFFFF if bit not found
    151  *********************************************************************************************/
     153 ********************************************************************************************/
    152154extern uint32_t bitmap_ffs2( bitmap_t * bitmap,
    153155                             uint32_t   index,
    154156                             uint32_t   size );
    155157
    156 /**********************************************************************************************
     158/*********************************************************************************************
    157159 * This function returns the index of first bit cleared in a bitmap, starting from index.
    158  **********************************************************************************************
     160 *********************************************************************************************
    159161 * @ bitmap  : pointer on the bitmap
    160162 * @ index   : first bit to analyse in the bitmap
    161163 * @ size    : number of bits to analyse in bitmap
    162164 * @ returns index if found / returns 0xFFFFFFFF if bit not found
    163  *********************************************************************************************/
     165 ********************************************************************************************/
    164166extern uint32_t bitmap_ffc2( bitmap_t * bitmap,
    165167                             uint32_t   index,
    166168                             uint32_t   size );
    167169
    168 /**********************************************************************************************
     170/*********************************************************************************************
    169171 * This function returns the index of first bit set in a bitmap, starting from bit 0.
    170  **********************************************************************************************
     172 *********************************************************************************************
    171173 * @ bitmap  : pointer on the bitmap
    172174 * @ size    : number of bits to analyse in bitmap
    173175 * @ returns index if found / returns 0xFFFFFFFF if bit not found
    174  *********************************************************************************************/
     176 ********************************************************************************************/
    175177extern uint32_t bitmap_ffs( bitmap_t * bitmap,
    176178                            uint32_t   size );
    177179
    178 /**********************************************************************************************
     180/*********************************************************************************************
    179181 * This function returns the index of first bit cleared in a bitmap, starting from bit 0.
    180  **********************************************************************************************
     182 *********************************************************************************************
    181183 * @ bitmap  : pointer on the bitmap
    182184 * @ size    : number of bits to alalyse in bitmap
    183185 * @ returns index if found / returns 0xFFFFFFFF if bit not found
    184  *********************************************************************************************/
     186 ********************************************************************************************/
    185187extern uint32_t bitmap_ffc( bitmap_t * bitmap,
    186188                            uint32_t   size );
    187189
    188 /**********************************************************************************************
     190/*********************************************************************************************
    189191 * This function returns the number of bits to code a non-zero unsigned integer value.
    190  **********************************************************************************************
     192 *********************************************************************************************
    191193 * @ val   : value to analyse
    192194 * @ returns number of bits
    193  *********************************************************************************************/
     195 ********************************************************************************************/
    194196static inline uint32_t bits_nr( uint32_t val )
    195197{
     
    202204}
    203205
    204 /**********************************************************************************************
     206/*********************************************************************************************
    205207 * This function takes an unsigned integer value as input argument, and returns another
    206208 * unsigned integer, that is the (base 2) logarithm of the smallest power of 2 contained
    207209 * in the input value.
    208  **********************************************************************************************
     210 *********************************************************************************************
    209211 * @ val   : value to analyse
    210212 * @ returns logarithm value
    211  *********************************************************************************************/
     213 ********************************************************************************************/
    212214static inline uint32_t bits_log2( uint32_t val )
    213215{
  • trunk/kernel/libk/elf.c

    r14 r23  
    3131#include <vfs.h>
    3232#include <elf.h>
     33#include <syscalls.h>
    3334
    3435
     
    8586
    8687    // load .elf header
    87         count = vfs_read( file_xp , buffer , size );
     88        count = vfs_move( true ,
     89                      file_xp,
     90                      buffer,
     91                      size );
    8892
    8993        if( count != size )
     
    163167
    164168        // set seek on segment base in file
    165                 error = vfs_lseek( file_xp , offset , VFS_SEEK_SET , NULL );
     169                error = vfs_lseek( file_xp,
     170                           offset,
     171                           SEEK_SET,
     172                           NULL );
    166173
    167174                if( error )
     
    210217                          process_t * process)
    211218{
     219    char         path_copy[CONFIG_VFS_MAX_PATH_LENGTH];
    212220        kmem_req_t   req;              // kmem request for program header
    213     char         path_copy[256];   // local copy of pathname
    214221        uint32_t     length;           // actual path length
    215222        Elf32_Ehdr   header;           // local buffer for .elf header
     
    217224    uint32_t     segs_size;        // size of buffer for segment descriptors array 
    218225        xptr_t       file_xp;          // extended pointer on created file descriptor
     226    uint32_t     file_id;          // file descriptor index (unused)
    219227    uint32_t     count;            // bytes counter
    220228        error_t      error;
     
    223231        length = hal_strlen_from_uspace( pathname );
    224232
    225     if( length > 255 )
     233    if( length >= CONFIG_VFS_MAX_PATH_LENGTH )
    226234    {
    227235        printk("\n[ERROR] in %s : pathname length too long\n", __FUNCTION__ );
     
    234242    // open file
    235243    file_xp = XPTR_NULL;  // avoid GCC warning
     244    file_id = -1;
    236245
    237246        error = vfs_open( process->vfs_cwd_xp,
    238247                      path_copy,
    239                       VFS_O_RDONLY,
    240                       &file_xp );
     248                      O_RDONLY,
     249                      0,
     250                      &file_xp,
     251                      &file_id );
    241252        if( error )
    242253        {
     
    252263        if( error )
    253264    {
    254         vfs_close( file_xp , &count );
     265        vfs_close( file_xp , file_id );
    255266        return -1;
    256267    }
     
    261272        {
    262273                printk("\n[ERROR] in %s : no segments found\n", __FUNCTION__ );
    263         vfs_close( file_xp , &count );
     274        vfs_close( file_xp , file_id );
    264275                return -1;
    265276        }
     
    277288    {
    278289                printk("\n[ERROR] in %s : no memory for segment descriptors\n", __FUNCTION__ );
    279         vfs_close( file_xp , &count );
     290        vfs_close( file_xp , file_id );
    280291        return -1;
    281292    }
    282293
    283294    // set seek pointer in file descriptor to access segment descriptors array
    284         error = vfs_lseek( file_xp , header.e_phoff, VFS_SEEK_SET , NULL );
     295        error = vfs_lseek( file_xp , header.e_phoff, SEEK_SET , NULL );
    285296
    286297        if( error )
    287298        {
    288299                printk("\n[ERROR] in %s : cannot seek for descriptors array\n", __FUNCTION__ );
    289         vfs_close( file_xp , &count );
     300        vfs_close( file_xp , file_id );
    290301            req.ptr = segs_base;
    291302            kmem_free( &req );
     
    294305
    295306    // load seg descriptors array to local buffer
    296         count = vfs_read( file_xp,
     307        count = vfs_move( true,
     308                      file_xp,
    297309                      segs_base,
    298310                      segs_size );
     
    301313        {
    302314                printk("\n[ERROR] in %s : cannot read segments descriptors\n", __FUNCTION__ );
    303         vfs_close( file_xp , &count );
     315        vfs_close( file_xp , file_id );
    304316            req.ptr = segs_base;
    305317            kmem_free( &req );
     
    316328        if( error )
    317329    {
    318         vfs_close( file_xp , &count );
     330        vfs_close( file_xp , file_id );
    319331            req.ptr = segs_base;
    320332            kmem_free( &req );
  • trunk/kernel/libk/htab.c

    r1 r23  
    22 * htable.c - Generic, embedded hash table implementation.
    33 *
    4  * Author     Ghassan Almalles (2008,2009,2010,2011,2012)
    5  *            Mohamed Lamine Karaoui (2015)
    6  *            Alain Greiner (2016)
     4 * Author      Alain Greiner (2016,2017)
    75 *
    86 * Copyright (c) UPMC Sorbonne Universites
     
    108 * This file is part of ALMOS-MKH.
    119 *
    12  * ALMOS-MKH.is free software; you can redistribute it and/or modify it
     10 * ALMOS-MKH is free software; you can redistribute it and/or modify it
    1311 * under the terms of the GNU General Public License as published by
    1412 * the Free Software Foundation; version 2.0 of the License.
    1513 *
    16  * ALMOS-MKH.is distributed in the hope that it will be useful, but
     14 * ALMOS-MKH is distributed in the hope that it will be useful, but
    1715 * WITHOUT ANY WARRANTY; without even the implied warranty of
    1816 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     
    2018 *
    2119 * You should have received a copy of the GNU General Public License
    22  * along with ALMOS-MKH.; if not, write to the Free Software Foundation,
     20 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
    2321 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
    2422 */
    2523
    26 #include <htable.h>
    27 #include <kmem.h>
    28 #include <ppm.h>
    29 
    30 ///////////////////////////////////////////////
    31 error_t ht_header_init( ht_header_t  * header,
    32                         ht_hash_t    * hash,
    33                         ht_compare_t * compare )
     24#include <kernel_config.h>
     25#include <hal_types.h>
     26#include <hal_special.h>
     27#include <htab.h>
     28#include <rwlock.h>
     29#include <list.h>
     30#include <printk.h>
     31#include <vfs.h>
     32
     33///////////////////////////////////////////////////////////////////////////////////////////
     34//    Item type specific (static) functions (two functions for each item type).
     35// Example below if for <vhs_inode_t>, where the identifier is the inum field.
     36///////////////////////////////////////////////////////////////////////////////////////////
     37
     38///////////////////////////////////////////////////////////////////////////////////////////
     39// These static functions compute the hash index from the key.
     40///////////////////////////////////////////////////////////////////////////////////////////
     41// @ key      : local pointer on key.
     42// @ return the index value, from 0 to (HASHTAB_SIZE - 1)
     43///////////////////////////////////////////////////////////////////////////////////////////
     44
     45static uint32_t htab_inode_index( void * key )
     46{
     47        uint32_t * inum = key;
     48        return (((*inum) >> 16) ^ ((*inum) & 0xFFFF)) % HASHTAB_SIZE;
     49}
     50
     51///////////////////////////////////////////////////////////////////////////////////////
     52// These static functions are used by htab_lookup(), htab_insert(), and htab_remove().
     53// They scan one sub-list identified by  <index> to find an item  identified by <key>.
     54// The sub-list is not modified, but the lock must have been taken by the caller.
     55///////////////////////////////////////////////////////////////////////////////////////
     56// @ htab    : pointer on hash table.
     57// @ index   : index of sub-list to be scanned.
     58// @ key     : pointer on item identifier.
     59// @ return pointer on item if found / return NULL if not found.
     60///////////////////////////////////////////////////////////////////////////////////////
     61
     62static void * htab_inode_scan( htab_t  * htab,
     63                               uint32_t  index,
     64                               void    * key )
     65{
     66    list_entry_t * list_entry;   // pointer on list_entry_t (iterator)
     67    vfs_inode_t  * inode;        // pointer on item
     68   
     69        LIST_FOREACH( &htab->roots[index] , list_entry )
     70        {
     71        inode = (vfs_inode_t *)LIST_ELEMENT( list_entry , vfs_inode_t , list );
     72        if( inode->inum == *(uint32_t *)key ) return inode;
     73    }
     74
     75    // no matching item found
     76        return NULL;
     77}
     78
     79////////////////////////////////////////////////////////////////////////////////////////
     80//         Generic access functions
     81////////////////////////////////////////////////////////////////////////////////////////
     82
     83////////////////////////////////////////
     84void htab_init( htab_t           * htab,
     85                htab_item_type_t   type )
    3486{
    3587        uint32_t     i;
    36         kmem_req_t   req;
    37         page_t     * page;
    38 
    39         req.type  = KMEM_PAGE;
    40         req.size  = 0;
    41         req.flags = AF_ZERO;
    42         page      = kmem_alloc( &req );
    43        
    44         if( page == NULL ) return ENOMEM;
    45 
    46         header->nb_buckets = CONFIG_PPM_PAGE_SIZE/sizeof( list_entry_t );
    47         header->buckets    = ppm_page2base( page );
    48         header->hash       = hash;
    49         header->compare    = compare;
    50 
    51         for( i=0 ; i < header->nb_buckets ; i++ )
    52         {
    53                 list_root_init( &header->buckets[i] );
    54         }
    55 
    56         return 0;
    57 }
    58 
    59 ////////////////////////////////////////
    60 error_t ht_node_init( ht_node_t * node )
    61 {
    62         node->index = (uint32_t) -1;
    63         list_entry_init( &node->list );
    64 
    65         return 0;
    66 }
    67 
    68 /////////////////////////////////////////////////
    69 static ht_node_t * __hfind( ht_header_t * header,
    70                             uint32_t      index,
    71                             void        * key)
    72 {
    73         ht_node_t    * node;
    74         list_entry_t * root,
    75     list_entry_t * iter;
    76 
    77         root = &header->buckets[index % header->nb_buckets];
    78 
    79         LIST_FOREACH( root , iter )
    80         {
    81                 node = LIST_ELEMENT( iter , ht_node_t , list );
    82                 if( node->index == index )
    83                 {
    84                         if( header->compare( node , key ) ) return node;
    85                 }
    86         }
    87 
    88         return NULL;
    89 }
    90 
    91 //////////////////////////////////////////
    92 ht_node_t * ht_find( ht_header_t * header,
    93                      void        * key )
    94 {
    95         uint32_t index = header->hash( key );
    96 
    97         return __ht_find( header , index , key );
    98 }
    99 
    100 ////////////////////////////////////////
    101 error_t ht_insert( ht_header_t * header,
    102                    ht_node_t   * node,
    103                    void        * key )
    104 {
    105         uint32_t index = header->hash( key );
    106 
    107         ht_node_t * node = __ht_find( header , index , key );
    108 
    109         if( node != NULL ) return EINVAL;
    110 
    111         list_entry_t * root = &header->buckets[index % header->nb_buckets];
    112 
    113         list_add_first( root , &node->list);
    114 
    115         node->index = index;
    116 
    117         return 0;
    118 }
    119 
    120 ////////////////////////////////////////
    121 error_t ht_remove( ht_header_t * header,
    122                    void        * key )
    123 {
    124         uint32_t index = header->hash( key );
    125 
    126         ht_node_t * node = __ht_find( header , index , key );
    127 
    128         if( node == NULL ) return EINVAL;
    129 
    130         list_unlink( &node->list );
    131 
    132         return 0;
    133 }
    134 
     88
     89    // initialize readlock
     90    rwlock_init( &htab->lock );
     91
     92    htab->items = 0;
     93
     94    if( type == HTAB_INODE_TYPE )
     95    {
     96        htab->scan    = &htab_inode_scan;
     97        htab->index   = &htab_inode_index;
     98    }
     99    else
     100    {
     101        printk("\n[PANIC] in %s : undefined item type\n", __FUNCTION__ );
     102        hal_core_sleep();
     103    }
     104
     105    // initialize partial lists
     106    for( i = 0 ; i < HASHTAB_SIZE ; i++ )
     107    {
     108        list_root_init( &htab->roots[i] );
     109    }
     110}
     111
     112/////////////////////////////////////////
     113error_t htab_insert( htab_t       * htab,
     114                     void         * key,
     115                     list_entry_t * list_entry )
     116{
     117    // compute index from key
     118    uint32_t index = htab->index( key );
     119
     120    // take the lock in write mode
     121    rwlock_wr_lock( &htab->lock );
     122
     123    // scan sub-list to check if item exist
     124    void * item = htab->scan( htab , index , key );
     125
     126    if( item != NULL ) // item exist => return error
     127    {
     128        // release lock
     129        rwlock_wr_unlock( &htab->lock );
     130
     131        return -1;
     132    }
     133    else               // item doesn't exist => register
     134    {
     135        // register item in hash table
     136        list_add_last( &htab->roots[index] , list_entry );
     137
     138        // update items number
     139        htab->items++;
     140
     141        // release lock
     142        rwlock_wr_unlock( &htab->lock );
     143
     144        return 0;
     145    }
     146}
     147
     148/////////////////////////////////////////
     149error_t htab_remove( htab_t       * htab,
     150                     void         * key,
     151                     list_entry_t * list_entry )
     152{
     153    // compute index from key
     154    uint32_t index = htab->index( key );
     155
     156    // take the lock in write mode
     157    rwlock_wr_lock( &htab->lock );
     158
     159    // scan sub-list to chek if item exist
     160    void * item = htab->scan( htab , index , key );
     161
     162    if( item == NULL ) // item doesn't exist
     163    {
     164        // release lock
     165        rwlock_wr_unlock( &htab->lock );
     166
     167        return -1;
     168    }
     169    else               // item exist => remove it
     170    {
     171        // remove item from hash table
     172        list_unlink( list_entry );
     173
     174        // update items number
     175        htab->items--;
     176
     177        // release lock
     178        rwlock_wr_unlock( &htab->lock );
     179
     180        return 0;
     181    }
     182}
     183
     184//////////////////////////////////
     185void * htab_lookup( htab_t * htab,
     186                    void   * key )
     187{
     188    // compute index from key
     189    uint32_t index = htab->index( key );
     190
     191    // take the lock in read mode
     192    rwlock_rd_lock( &htab->lock );
     193
     194    // scan sub-list
     195    void * item = htab->scan( htab , index , key );
     196
     197    // release lock
     198    rwlock_rd_unlock( &htab->lock );
     199
     200        return item;
     201}
     202
     203
     204
  • trunk/kernel/libk/htab.h

    r1 r23  
    22 * htab.h - Generic embedded hash table definition.
    33 *
    4  * Author     Ghassan Almalles (2008,2009,2010,2011,2012)
    5  *            Mohamed Lamine Karaoui (2015)
    6  *            Alain Greiner (2016)
     4 * Authors  Alain Greiner (2016,2017)
    75 *
    86 * Copyright (c) UPMC Sorbonne Universites
     
    2927
    3028#include <hal_types.h>
     29#include <rwlock.h>
    3130#include <list.h>
    3231
     32/////////////////////////////////////////////////////////////////////////////////////////
     33// This file define a generic, embedded, hash table.
     34//
     35// It can only be accessed by threads running in the local cluster.
     36// It is generic as it can be used to register various types of items.
     37// The main goal is to provide fast retrieval for a large number of items of same type.
     38// For this purpose the set of all registered items is split in several subsets.
     39// Each subset is organised as a double linked lists.
     40// - an item is uniquely identified by a <key>, that can be a single uint32_t,
     41//   a character string, or a more complex structure.
     42// - From the pointer on <key>, we use an item type specific htab_index() function,
     43//   to compute an <index> value, defining a subset of registered items.
     44// - As several items can have the same <index>, we use the item type specific defined
     45//   htab_scan() function for a final associative search on the subset.
     46// - Each registered item is a structure, that must contain an embedded list_entry_t,
     47//   that is part of a rooted double linked list.
     48//
     49// Implementation Note: for each supported item type ***, you must define the two
     50//                      htab_***_index() and htab_***_scan() functions, and
     51//                      update the htab_init() function.
     52/////////////////////////////////////////////////////////////////////////////////////////
     53
     54#define HASHTAB_SIZE    64   // number of subsets
     55
    3356/****************************************************************************************
    34  * This file define a generic, embedded, hash table.
    35  * The main goal is to provide fast retrieval for a large number of items of same type
    36  * in a given cluster. For this purpose the set of all registered items is split
    37  * in several subsets. Each subset is organised as a double linked lists.
    38  * - an item is uniquely identified by a <key>, that can be a single uint32_t,
    39  *   a character string, or a more complex structure.
    40  * - From the pointer on the <key>, the hash table uses an user defined ht_hash()
    41  *   function, to compute an <index> value, defining a subset of registered
    42  *   items, to restrict the associative search.
    43  * - As several items can have the same <index>, the hash table uses the user defined
    44  *   ht_compare() function for a final associative search on the subset.
    45  * - Each registered item is a structure, that must contain an embedded ht_node_t,
    46  *   This ht_node_t is part of a rooted double linked list, and contains the <index>.
    47  * - Finally, the hash table returns a pointer on the embedded ht_node_t, and the
    48  *   pointer on the searched item can be obtained by a simple offset.
     57 * These typedef define the two item type specific function prototypes.
    4958 ***************************************************************************************/
    5059
     60struct htab_s;
     61
     62typedef void *     htab_scan_t( struct htab_s * htab , uint32_t index , void * key );
     63
     64typedef uint32_t   htab_index_t( void * key );
     65
    5166/****************************************************************************************
    52  * This define the generic, user defined, function types.
     67 * This define the supported item types.
    5368 ***************************************************************************************/
    5469
    55 struct ht_node_s;
    56 
    57 typedef bool_t     ht_compare_t( struct ht_node_s * node , void * key );
    58 typedef uint32_t   ht_hash_t( void * key );
     70typedef enum
     71{
     72    HTAB_INODE_TYPE = 1,                     /*! item is a vfs_inode_t                 */
     73}
     74htab_item_type_t;
    5975
    6076/****************************************************************************************
    61  * This structure defines the hash table header.
     77 * This structure defines the the root of a local hash table.
    6278 ***************************************************************************************/
    6379
    64 typedef struct ht_header_s
     80typedef struct htab_s
    6581{
    66         uint32_t        nb_buckets;   /*! number of subsets (one linked list per subset)   */
    67         ht_hash_t     * hash;         /*! user defined hash function                       */
    68         ht_compare_t  * compare;      /*! user defined compare function                    */
    69         list_entry_t  * buckets;      /*! array of root of partial lists of ht_node_t      */
     82        list_entry_t      roots[HASHTAB_SIZE];  /*! array of roots of partial lists        */
     83        htab_index_t    * index;                /*! item type  specific function           */
     84        htab_scan_t     * scan;                 /*! item type specific function            */
     85    uint32_t          items;                /*! number of registered items             */
     86    rwlock_t          lock;                 /*! lock protecting hash table accesses    */
    7087}
    71 ht_header_t;
     88htab_t;
    7289
    7390/****************************************************************************************
    74  * This structure defines one hash table node.
     91 * This function initialises an empty hash table (zero registered item).
     92 ****************************************************************************************
     93 * @ htab       : pointer on hash table.
     94 * @ type       : item type.
    7595 ***************************************************************************************/
    76 
    77 typedef struct ht_node_s
    78 {
    79         uint32_t     index;           /*! integer value computed from the key              */
    80         list_entry_t list;                /*! member of list of all nodes in same bucket       */
    81 }
    82 ht_node_t;
     96void htab_init( htab_t           * htab,
     97                htab_item_type_t   type );
    8398
    8499/****************************************************************************************
    85  * This function initialises one hash table node.
     100 * This function register a new item in the hash table.
    86101 ****************************************************************************************
    87 ccccc
     102 * @ htab       : pointer on the hash table.
     103 * @ key        : pointer on the item identifier.
     104 * @ list_entry : pointer on list_entry_t embedded in item to be registered.
     105 * @ return 0 if success / return EINVAL if item already registered.
    88106 ***************************************************************************************/
    89 void ht_node_init( ht_node_t * node );
     107error_t htab_insert( htab_t       * htab,
     108                     void         * key,
     109                     list_entry_t * list_entry );
    90110
    91111/****************************************************************************************
    92  * This function allocates memory for the buckets array, and initializes the header.
    93  * The number of buckets (number of subsets) is PAGE_SIZE / sizeof(list_entry_t)
     112 * This function remove an item from the hash table.
    94113 ****************************************************************************************
    95  * @ header     : pointer on the hash table header.
    96  * @ ht_hash    : pointer on the user defined hash function.
    97  * @ ht_compare : pointer on the user defined compare function.
    98  * @ return 0 if success / return ENOMEM if error.
     114 * @ header     : pointer on the hash table.
     115 * @ key        : pointer on the item identifier.
     116 * @ list_entry : pointer on list_entry_t embedded in item to be removed.
     117 * @ return 0 if success / return EINVAL if item not found.
    99118 ***************************************************************************************/
    100 error_t ht_header_init( ht_header_t  * header,
    101                         ht_hash_t    * ht_hash,
    102                         ht_compare_t * ht_compare );
    103 
    104 /****************************************************************************************
    105  * This function register a new node in the hash table.
    106  ****************************************************************************************
    107  * @ header     : pointer on the hash table header.
    108  * @ node       : pointer on the node to be registered (embedded in item).
    109  * @ key        : pointer on the item identifier.
    110  * @ return 0 if success / return EINVAL if node already registered...
    111  ***************************************************************************************/
    112 error_t ht_insert( ht_header_t * header,
    113                    ht_node_t   * node,
    114                    void        * key );
     119error_t htab_remove( htab_t       * htab,
     120                     void         * key,
     121                     list_entry_t * list_entry );
    115122
    116123/****************************************************************************************
     
    118125 * identified by its key.
    119126 ****************************************************************************************
    120  * @ header     : pointer on the hash table header.
    121  * @ key        : pointer on the item identifier.
    122  * @ return pointer on node if found / return NULL if not found.
     127 * @ htab      : pointer on the hash table.
     128 * @ key       : pointer on the item identifier.
     129 * @ return pointer on item if found / return NULL if not found.
    123130 ***************************************************************************************/
    124 ht_node_t * ht_find( ht_header_t * header,
    125                      void        * key);
     131void * htab_lookup( htab_t * htab,
     132                    void   * key);
    126133
    127 /****************************************************************************************
    128  * This function remove an item from the hash table.
    129  ****************************************************************************************
    130  * @ header     : pointer on the hash table header.
    131  * @ key        : pointer on the item identifier.
    132  * @ return 0 if success / return EINVAL if not found.
    133  ***************************************************************************************/
    134 error_t ht_remove( ht_header_t * header,
    135                    void        * key );
    136134
    137 #endif /* _HTABLE_H_ */
     135#endif /* _HTAB_H_ */
  • trunk/kernel/libk/remote_barrier.c

    r14 r23  
    11/*
    2  * remote_barrier.c - distributed kernel barrier implementaion
     2 * remote_barrier.c - Access a POSIX barrier.
    33 *
    4  * Author   Alain Greiner (2016)
     4 * Author   Alain Greiner (2016,2017)
    55 *
    66 * Copyright (c) UPMC Sorbonne Universites
     
    2424#include <hal_types.h>
    2525#include <hal_remote.h>
     26#include <hal_irqmask.h>
     27#include <remote_spinlock.h>
     28#include <thread.h>
     29#include <kmem.h>
     30#include <printk.h>
     31#include <process.h>
     32#include <vmm.h>
    2633#include <remote_barrier.h>
    2734
    28 /////////////////////////////////////////
    29 inline void remote_barrier( xptr_t    xp,
     35/////////////////////////////////////////////////
     36inline void remote_barrier( xptr_t    barrier_xp,
    3037                            uint32_t  count )
    3138{
    3239    uint32_t  expected;
    3340
    34     remote_barrier_t * ptr = (remote_barrier_t *)GET_PTR( xp );
    35     cxy_t              cxy = GET_CXY( xp );
     41    remote_barrier_t * ptr = (remote_barrier_t *)GET_PTR( barrier_xp );
     42    cxy_t              cxy = GET_CXY( barrier_xp );
    3643
    3744    // get barrier sense value
     
    5764}
    5865
    59 
     66///////////////////////////////////////////////////
     67xptr_t remote_barrier_from_ident( intptr_t  ident )
     68{
     69    // get pointer on local process_descriptor
     70    process_t * process = CURRENT_THREAD->process;
     71
     72    // get extended pointer on reference process
     73    xptr_t      ref_xp = process->ref_xp;
     74
     75    // get cluster and local pointer on reference process
     76    cxy_t          ref_cxy = GET_CXY( ref_xp );
     77    process_t    * ref_ptr = (process_t *)GET_PTR( ref_xp );
     78
     79    // get extended pointer on root of barriers list
     80    xptr_t root_xp = XPTR( ref_cxy , &ref_ptr->barrier_root );
     81   
     82    // scan reference process barriers list
     83    xptr_t             iter_xp;
     84    xptr_t             barrier_xp;
     85    cxy_t              barrier_cxy;
     86    remote_barrier_t * barrier_ptr;
     87    intptr_t           current;
     88    bool_t             found = false;
     89           
     90    XLIST_FOREACH( root_xp , iter_xp )
     91    {
     92        barrier_xp  = XLIST_ELEMENT( iter_xp , remote_barrier_t , list );
     93        barrier_cxy = GET_CXY( barrier_xp );
     94        barrier_ptr = (remote_barrier_t *)GET_PTR( barrier_xp );
     95        current     = (intptr_t)hal_remote_lpt( XPTR( barrier_cxy , &barrier_ptr->ident ) );   
     96        if( ident == current )
     97        {
     98            found = true;
     99            break;
     100        }
     101    }
     102
     103    if( found == false )  return XPTR_NULL;
     104    else                  return barrier_xp;
     105
     106}  // end remote_barrier_from_ident()
     107
     108//////////////////////////////////////////////
     109error_t remote_barrier_create( intptr_t ident,
     110                               uint32_t count )
     111{
     112    xptr_t             barrier_xp;
     113    remote_barrier_t * barrier_ptr;
     114
     115    // get pointer on local process descriptor
     116    process_t * process = CURRENT_THREAD->process;
     117
     118    // get extended pointer on reference process
     119    xptr_t      ref_xp = process->ref_xp;
     120
     121    // get reference process cluster and local pointer
     122    cxy_t       ref_cxy = GET_CXY( ref_xp );
     123    process_t * ref_ptr = (process_t *)GET_PTR( ref_xp );
     124
     125    // allocate memory for barrier descriptor
     126    if( ref_cxy == local_cxy )                  // local cluster is the reference
     127    {
     128        kmem_req_t req;   
     129        req.type      = KMEM_BARRIER;
     130        req.flags     = AF_ZERO;
     131        barrier_ptr   = kmem_alloc( &req );
     132        barrier_xp    = XPTR( local_cxy , barrier_ptr );
     133    }
     134    else                                       // reference is remote
     135    {
     136        rpc_kcm_alloc_client( ref_cxy , KMEM_BARRIER , &barrier_xp );
     137        barrier_ptr = (remote_barrier_t *)GET_PTR( barrier_xp );
     138    }
     139
     140    if( barrier_ptr == NULL ) return ENOMEM;
     141
     142    // initialise barrier
     143    hal_remote_sw ( XPTR( ref_cxy , &barrier_ptr->nb_threads ) , count );
     144    hal_remote_sw ( XPTR( ref_cxy , &barrier_ptr->current    ) , 0 );
     145    hal_remote_sw ( XPTR( ref_cxy , &barrier_ptr->sense      ) , 0 );
     146    hal_remote_spt( XPTR( ref_cxy , &barrier_ptr->ident      ) , (void*)ident );
     147
     148    xlist_entry_init( XPTR( ref_cxy , &barrier_ptr->list ) );
     149
     150    // register  barrier in reference process xlist
     151    xptr_t root_xp  = XPTR( ref_cxy , &ref_ptr->barrier_root );
     152    xptr_t entry_xp = XPTR( ref_cxy , &barrier_ptr->list );
     153
     154    remote_spinlock_lock( XPTR( ref_cxy , &ref_ptr->sync_lock ) );
     155    xlist_add_first( root_xp , entry_xp );
     156    remote_spinlock_unlock( XPTR( ref_cxy , &ref_ptr->sync_lock ) );
     157
     158    return 0;
     159
     160}  // end remote_barrier_create()
     161
     162////////////////////////////////////////////////
     163void remote_barrier_destroy( xptr_t barrier_xp )
     164{
     165    // get pointer on local process descriptor
     166    process_t * process = CURRENT_THREAD->process;
     167
     168    // get extended pointer on reference process
     169    xptr_t      ref_xp = process->ref_xp;
     170
     171    // get reference process cluster and local pointer
     172    cxy_t       ref_cxy = GET_CXY( ref_xp );
     173    process_t * ref_ptr = (process_t *)GET_PTR( ref_xp );
     174
     175    // get barrier cluster and local pointer
     176    cxy_t              barrier_cxy = GET_CXY( barrier_xp );
     177    remote_barrier_t * barrier_ptr = (remote_barrier_t *)GET_PTR( barrier_xp );
     178
     179    // remove barrier from reference process xlist
     180    remote_spinlock_lock( XPTR( ref_cxy , &ref_ptr->sync_lock ) );
     181    xlist_unlink( XPTR( barrier_cxy , &barrier_ptr->list ) );
     182    remote_spinlock_unlock( XPTR( ref_cxy , &ref_ptr->sync_lock ) );
     183
     184    // release memory allocated for barrier descriptor
     185    if( barrier_cxy == local_cxy )                        // reference is local
     186    {
     187        kmem_req_t  req;
     188        req.type = KMEM_BARRIER;
     189        req.ptr  = barrier_ptr;
     190        kmem_free( &req );
     191    }
     192    else                                                  // reference is remote
     193    {
     194        rpc_kcm_free_client( barrier_cxy , barrier_ptr , KMEM_BARRIER );
     195    }
     196
     197}  // end remote_barrier_destroy()
     198
     199/////////////////////////////////////////////
     200void remote_barrier_wait( xptr_t barrier_xp )
     201{
     202    uint32_t  expected;
     203    uint32_t  current;
     204    uint32_t  count;
     205    uint32_t  sense;
     206    uint32_t  irq_state;
     207    xptr_t    root_xp;
     208
     209    // get cluster and local pointer on calling thread
     210    cxy_t              thread_cxy = local_cxy;
     211    thread_t         * thread_ptr = CURRENT_THREAD;
     212
     213    // get cluster and local pointer on remote barrier
     214    remote_barrier_t * barrier_ptr = (remote_barrier_t *)GET_PTR( barrier_xp );
     215    cxy_t              barrier_cxy = GET_CXY( barrier_xp );
     216
     217    // get count and root fields from barrier descriptor
     218    count   = hal_remote_lw ( XPTR( barrier_cxy , &barrier_ptr->nb_threads ) );
     219    root_xp = hal_remote_lwd( XPTR( barrier_cxy , &barrier_ptr->root ) );
     220
     221    // get barrier sense value
     222    sense = hal_remote_lw( XPTR( barrier_cxy , &barrier_ptr->sense ) );
     223
     224        // compute expected value
     225    if ( sense == 0 ) expected = 1;
     226    else              expected = 0;
     227
     228    // atomically increment current
     229    current = hal_remote_atomic_add( XPTR( barrier_cxy , &barrier_ptr->current ) , 1 );
     230
     231    // last thread reset current, toggle sense, and activate all waiting threads
     232    // other threads block, register in queue, and deschedule
     233
     234    if( current == (count-1) )                       // last thread
     235    {
     236        hal_remote_sw( XPTR( barrier_cxy , &barrier_ptr->current) , 0 ); 
     237        hal_remote_sw( XPTR( barrier_cxy , &barrier_ptr->sense  ) , expected ); 
     238
     239        // activate waiting threads if required
     240        if( xlist_is_empty( root_xp ) == false ) 
     241        {
     242            // disable interrupts
     243                hal_disable_irq( &irq_state );
     244 
     245            xptr_t  iter_xp;
     246            xptr_t  thread_xp;
     247            XLIST_FOREACH( root_xp , iter_xp )
     248            {
     249                // get extended pointer on waiting thread
     250                thread_xp = XLIST_ELEMENT( iter_xp , thread_t , wait_list );
     251       
     252                // remove waiting thread from queue
     253                remote_spinlock_lock( XPTR( barrier_cxy , &barrier_ptr->lock ) );
     254                xlist_unlink( XPTR( barrier_cxy , &barrier_ptr->list ) );
     255                remote_spinlock_unlock( XPTR( barrier_cxy , &barrier_ptr->lock ) );
     256
     257                // unblock waiting thread
     258                thread_unblock( thread_xp , THREAD_BLOCKED_USERSYNC );
     259            }
     260
     261            // restore interrupts
     262            hal_restore_irq( irq_state );
     263        }
     264    }
     265    else                                             // not the last thread 
     266    {
     267        // disable interrupts
     268            hal_disable_irq( &irq_state );
     269 
     270        // register calling thread in barrier waiting queue
     271        xptr_t entry_xp = XPTR( thread_cxy , &thread_ptr->wait_list );
     272
     273        remote_spinlock_lock( XPTR( barrier_cxy , &barrier_ptr->lock ) );
     274        xlist_add_last( root_xp , entry_xp );
     275        remote_spinlock_unlock( XPTR( barrier_cxy , &barrier_ptr->lock ) );
     276
     277        // block & deschedule the calling thread   
     278        thread_block( thread_ptr , THREAD_BLOCKED_USERSYNC );
     279        sched_yield();
     280
     281        // restore interrupts
     282        hal_restore_irq( irq_state );
     283    }
     284}  // end remote_barrier_wait()
  • trunk/kernel/libk/remote_barrier.h

    r14 r23  
    11/*
    2  * remote_barrier.h - distributed kernel barrier definition
     2 * remote_barrier.h - Access a POSIX barrier.               
    33 *
    44 * Author  Alain Greiner (2016)
     
    1010 * ALMOS-MKH is free software; you can redistribute it and/or modify it
    1111 * under the terms of the GNU General Public License as published by
    12 err* the Free Software Foundation; version 2.0 of the License.
     12 * the Free Software Foundation; version 2.0 of the License.
    1313 *
    1414 * ALMOS-MKH is distributed in the hope that it will be useful, but
     
    2727#include <kernel_config.h>
    2828#include <hal_types.h>
     29#include <remote_spinlock.h>
     30#include <xlist.h>
     31
     32/***************************************************************************************
     33 *          This file defines a POSIX compliant barrier.
     34 *
     35 * It is used by multi-threaded applications to synchronise threads running in
     36 * different clusters, as all access functions uses hal_remote_lw() / hal_remote_sw()
     37 * portable remote access primitives.
     38 *
     39 * A barrier is declared by a given user process as a "pthread_barrier_t" global variable.
     40 * This user type is implemented as an unsigned long, but the value is not used by the
     41 * kernel. ALMOS-MKH uses only the barrier virtual address as an identifier.
     42 * For each user barrier, ALMOS-MKH creates a kernel "remote_barrier_t" structure,
     43 * dynamically allocated in the reference cluster by the remote_barrier_create() function,
     44 * and destroyed by the remote_barrier_destroy() function, using RPC if the calling thread
     45 * is not running in the reference cluster.
     46 *
     47 * The blocking "remote_barrier_wait()" function implements a descheduling policy when
     48 * the calling thread is not the last expected thread: the calling thread is registered
     49 * in a waiting queue, rooted in the barrier structure, and the the calling thread
     50 * is blocked on the THREAD_BLOCKED_USERSYNC condition. The last arrived thread
     51 * unblocks all registtered waiting threads.
     52 *
     53 * Implementation note:
     54 * This barrier is also used by the kernel in the parallel kernel_init phase, as the
     55 * remote_barrier() function does not require barrier initialisation, when the barrier
     56 * is statically allocated by the compiler in the kdata segment.
     57 * **************************************************************************************/
    2958
    3059/*****************************************************************************************
    31  * This structure defines a distributed "rendez-vous" barrier, that can be used
    32  * to synchronise several kernel threads running in different clusters
    33  * It is used in the parallel kernel_init phase.
    34  * It does not need to be initialised, but it must be statically allocated
    35  * in the KDATA segment to be properly initialised by the compiler/loader.
     60 * This structure defines the barrier descriptor.
     61 * - It contains an xlist of all barriers dynamically created by a given process,
     62 *   rooted in the reference process descriptor.
     63 * - It contains the root of another xlist to register all arrived threads.
    3664 ****************************************************************************************/
    3765
    3866typedef struct remote_barrier_s
    3967{
    40     uint32_t   current;   // number of arrived threads
    41     uint32_t   sense;     // barrier state (toggle)
    42     uint32_t   pad[(CONFIG_CACHE_LINE_SIZE>>2)-2];
     68    remote_spinlock_t  lock;          /*! lock protecting list of arrived threads       */
     69    intptr_t           ident;         /*! virtual address in user space == identifier   */
     70    uint32_t           current;       /*! number of arrived threads                     */
     71    uint32_t           sense;         /*! barrier state (toggle)                        */
     72    uint32_t           nb_threads;    /*! number of expected threads                    */
     73    xlist_entry_t      list;          /*! member of list of barriers in same process    */
     74    xlist_entry_t      root;          /*! root of list of arrived threads               */
    4375}
    4476remote_barrier_t;
    4577
    4678/*****************************************************************************************
    47  * This blocking function implements a toggle barrier. It returns only when all
    48  * expected threads reach the barrier. It can be used several times without
    49  * specific initialisation.
    50  * It is portable, as it uses the remote_lw() & remote_sw() access functions.
    51  * @ xp      : extended pointer on barrier in remote cluster
    52  * @ count   : number of expected thread
     79 * This function is directly used by the kernel in the kernel_init phase,
     80 * because it does not require barrier state initialisation.
     81 * It returns only when the <count> expected threads reach the barrier.
     82 *****************************************************************************************
     83 * @ barrier_xp  : extended pointer on barrier descriptor.
     84 * @ count       : number of expected threads.
    5385 ****************************************************************************************/
    54 inline void remote_barrier( xptr_t   xp, 
     86inline void remote_barrier( xptr_t   barrier_xp, 
    5587                            uint32_t count );
    5688
    5789
     90/*****************************************************************************************
     91 * This function returns an extended pointer on the remote barrier identified
     92 * by its virtual address in a given user process. It makes an associative search,
     93 * scanning the list of barriers rooted in the reference process descriptor.
     94 *****************************************************************************************
     95 * @ ident    : barrier virtual address, used as identifier.
     96 * @ returns extended pointer on barrier if success / returns XPTR_NULL if not found.
     97 ****************************************************************************************/
     98xptr_t remote_barrier_from_ident( intptr_t  ident );
     99
     100/*****************************************************************************************
     101 * This function implement the pthread_barrier_init() syscall.
     102 * It allocates memory for the barrier descriptor in the reference cluster for
     103 * the calling process, it initializes the barrier state, and register it in the
     104 * list of barriers owned by the reference process.
     105 *****************************************************************************************
     106 * @ count       : number of expected threads.
     107 * @ ident       : barrier identifier (virtual address in user space).
     108 * @ return 0 if success / return ENOMEM if failure.
     109 ****************************************************************************************/
     110error_t remote_barrier_create( intptr_t ident,
     111                               uint32_t count );
     112
     113/*****************************************************************************************
     114 * This function implement the pthread_barrier_destroy() syscall.
     115 * It releases thr memory allocated for the barrier descriptor, and remove the barrier
     116 * from the list of barriers owned by the reference process.
     117 *****************************************************************************************
     118 * @ barrier_xp  : extended pointer on barrier descriptor.
     119 ****************************************************************************************/
     120void remote_barrier_destroy( xptr_t   barrier_xp );
     121
     122/*****************************************************************************************
     123 * This function implement the pthread_barrier_wait() syscall.
     124 * It returns only when the number of expected threads (registered in the barrier
     125 * dexcriptor) reach the barrier.
     126 *****************************************************************************************
     127 * @ barrier_xp   : extended pointer on barrier descriptor.
     128 ****************************************************************************************/
     129void remote_barrier_wait( xptr_t   barrier_xp );
     130
     131
    58132#endif  /* _REMOTE_BARRIER_H_ */
  • trunk/kernel/libk/remote_rwlock.c

    r1 r23  
    22 * remote_rwlock.c - kernel remote rwlock implementation.
    33 *
    4  * Authors  Mohamed Karaoui (2015)
    5  *          Alain   Greiner (2016)
     4 * Authors    Alain   Greiner (2016,2017)
    65 *
    76 * Copyright (c) UPMC Sorbonne Universites
     
    6766
    6867    // get next free ticket
    69     ticket = hal_remote_lw( ticket_xp );
    70 
    71     // loop to take the lock
     68    ticket = hal_remote_atomic_add( ticket_xp , 1 );
     69
     70    // busy waiting loop to take the lock
    7271        while( ticket != hal_remote_lw( current_xp ) )
    7372        {
     
    147146
    148147    // get next free ticket
    149     ticket = hal_remote_lw( ticket_xp );
     148    ticket = hal_remote_atomic_add( ticket_xp , 1 );
    150149
    151150    // loop to take the lock
  • trunk/kernel/libk/remote_rwlock.h

    r14 r23  
    3030
    3131/***************************************************************************************
    32  * This structure defines a remote rwdlock,that supports several simultaneous read
     32 * This file defines a remote kernel lock, that supports several simultaneous read
    3333 * accesses, but only one write access. It implements a ticket based allocation policy.
    3434 * It can be used to synchronize threads running in different clusters, because
     
    4141 * When the lock is taken by another thread, the new-comers use a busy waiting policy.
    4242 *
    43  * TODO This could be replaced by a descheduling policy and a threads waiting queue
    44  * implemented in the lock itself: each thread releasing the lock (i.e. incrementing
    45  * the current field) activates the first waiting thread...
     43 * It uses a busy-waiting policy if the lock is already allocated to another thread.
    4644 **************************************************************************************/
    4745
  • trunk/kernel/libk/remote_sem.c

    r15 r23  
    2323
    2424#include <hal_types.h>
     25#include <hal_remote.h>
    2526#include <thread.h>
    2627#include <kmem.h>
     
    3536{
    3637    // get pointer on local process_descriptor
    37     process_t * process = CURRENT_PROCESS;
     38    process_t * process = CURRENT_THREAD->process;
    3839
    3940    // get extended pointer on reference process
     
    5758    XLIST_FOREACH( root_xp , iter_xp )
    5859    {
    59         sem_xp  = XLIST_ELEMENT( iter_xp , remote_sem_t , sem_list );
     60        sem_xp  = XLIST_ELEMENT( iter_xp , remote_sem_t , list );
    6061        sem_cxy = GET_CXY( sem_xp );
    6162        sem_ptr = (remote_sem_t *)GET_PTR( sem_xp );
    62         ident   = hal_remote_lw( XPTR( sem_cxy , &sem_ptr->ident ) );   
     63        ident   = (intptr_t)hal_remote_lpt( XPTR( sem_cxy , &sem_ptr->ident ) );   
    6364        if( ident == vaddr )
    6465        {
     
    7374}  // end remote_sem_from_vaddr()
    7475
    75 /////////////////////////////////////////
    76 error_t remote_sem_init( intptr_t  vaddr,
    77                          uint32_t  value )
     76///////////////////////////////////////////
     77error_t remote_sem_create( intptr_t  vaddr,
     78                           uint32_t  value )
    7879{
    7980    xptr_t         sem_xp;
     
    8182
    8283    // get pointer on local process descriptor
    83     process_t * process = CURRENT_PROCESS;
     84    process_t * process = CURRENT_THREAD->process;
    8485
    8586    // get extended pointer on reference process
    8687    xptr_t      ref_xp = process->ref_xp;
    8788
     89    // get reference process cluster and local pointer
    8890    cxy_t       ref_cxy = GET_CXY( ref_xp );
    8991    process_t * ref_ptr = (process_t *)GET_PTR( ref_xp );
     
    100102    else                         // reference is remote
    101103    {
    102         rpc_semaphore_alloc_client( ref_cxy , &sem_xp );
     104        rpc_kcm_alloc_client( ref_cxy , KMEM_SEM , &sem_xp );
    103105        sem_ptr = (remote_sem_t *)GET_PTR( sem_xp );
    104106    }
     
    106108    if( sem_xp == XPTR_NULL ) return ENOMEM;
    107109
    108     // initialise semaphore lock
     110    // initialise semaphore
     111    hal_remote_sw ( XPTR( ref_cxy , &sem_ptr->count ) , value );
     112        hal_remote_spt( XPTR( ref_cxy , &sem_ptr->ident ) , (void *)vaddr );
     113
    109114    remote_spinlock_init( XPTR( ref_cxy , &sem_ptr->lock ) );
    110 
    111     // initialise semaphore count
    112     hal_remote_sw( XPTR( ref_cxy , &sem_ptr->count ) , value );
    113 
    114     // initialise vaddr
    115         hal_remote_spt( XPTR( ref_cxy , &sem_ptr->ident ) , (void *)vaddr );
    116 
    117     // initialise waiting threads queue
    118         xlist_root_init( XPTR( ref_cxy , &sem_ptr->wait_queue ) );
    119 
    120     // register new semaphore in reference process xlist
     115        xlist_root_init( XPTR( ref_cxy , &sem_ptr->root ) );
     116        xlist_entry_init( XPTR( ref_cxy , &sem_ptr->list ) );
     117
     118    // register semaphore in reference process xlist
    121119    xptr_t root_xp = XPTR( ref_cxy , &ref_ptr->sem_root );
    122     xptr_t xp_list = XPTR( ref_cxy , &sem_ptr->sem_list );
     120    xptr_t xp_list = XPTR( ref_cxy , &sem_ptr->list );
     121
     122    remote_spinlock_lock( XPTR( ref_cxy , &ref_ptr->sync_lock ) );
    123123    xlist_add_first( root_xp , xp_list );
     124    remote_spinlock_unlock( XPTR( ref_cxy , &ref_ptr->sync_lock ) );
    124125
    125126    return 0;
     
    127128}  // en remote_sem_init()
    128129 
     130////////////////////////////////////////
     131void remote_sem_destroy( xptr_t sem_xp )
     132{
     133    // get pointer on local process descriptor
     134    process_t * process = CURRENT_THREAD->process;
     135
     136    // get extended pointer on reference process
     137    xptr_t      ref_xp = process->ref_xp;
     138
     139    // get reference process cluster and local pointer
     140    cxy_t       ref_cxy = GET_CXY( ref_xp );
     141    process_t * ref_ptr = (process_t *)GET_PTR( ref_xp );
     142
     143    // get semaphore cluster and local pointer
     144    cxy_t          sem_cxy = GET_CXY( sem_xp );
     145    remote_sem_t * sem_ptr = (remote_sem_t *)GET_PTR( sem_xp );
     146
     147    // get lock protecting semaphore
     148    remote_spinlock_lock( XPTR( sem_cxy , &sem_ptr->lock ) );
     149 
     150    // get remote pointer on waiting queue
     151    xptr_t root_xp = (xptr_t)hal_remote_lwd( XPTR( sem_cxy , &sem_ptr->root ) );
     152 
     153    if( !xlist_is_empty( root_xp ) )   // user error
     154    {
     155        printk("WARNING in %s for thread %x in process %x : "
     156               "destroy semaphore, but  waiting threads queue not empty\n",
     157               __FUNCTION__ , CURRENT_THREAD->trdid , CURRENT_THREAD->process->pid );
     158    }
     159
     160    // reset semaphore count
     161    hal_remote_sw( XPTR( sem_cxy , &sem_ptr->count ) , 0 );
     162
     163    // remove semaphore from reference process xlist
     164    remote_spinlock_lock( XPTR( ref_cxy , &ref_ptr->sync_lock ) );
     165    xlist_unlink( XPTR( sem_cxy , &sem_ptr->list ) );
     166    remote_spinlock_unlock( XPTR( ref_cxy , &ref_ptr->sync_lock ) );
     167
     168    // release lock
     169    remote_spinlock_unlock( XPTR( sem_cxy , &sem_ptr->lock ) );
     170
     171    // release memory allocated for semaphore descriptor
     172    if( sem_cxy == local_cxy )                            // reference is local
     173    {
     174        kmem_req_t  req;
     175        req.type = KMEM_SEM;
     176        req.ptr  = sem_ptr;
     177        kmem_free( &req );
     178    }
     179    else                                                  // reference is remote
     180    {
     181        rpc_kcm_free_client( sem_cxy , sem_ptr , KMEM_SEM );
     182    }
     183
     184}  // end remote_sem_destroy()
     185
    129186//////////////////////////////////
    130187void remote_sem_wait( xptr_t sem_xp )
     
    153210
    154211        // register thread in waiting queue
    155         xptr_t root_xp   = (xptr_t)hal_remote_lwd( XPTR( sem_cxy , &sem_ptr->wait_queue ) );
     212        xptr_t root_xp   = (xptr_t)hal_remote_lwd( XPTR( sem_cxy , &sem_ptr->root ) );
    156213        xptr_t thread_xp = XPTR( local_cxy , this );
    157214                xlist_add_last( root_xp , thread_xp );
     
    177234 
    178235    // get remote pointer on waiting queue root
    179     xptr_t queue_xp = (xptr_t)hal_remote_lwd( XPTR( sem_cxy , &sem_ptr->wait_queue ) );
    180  
    181         if( xlist_is_empty( queue_xp ) )   // no waiting thread
     236    xptr_t root_xp = (xptr_t)hal_remote_lwd( XPTR( sem_cxy , &sem_ptr->root ) );
     237 
     238        if( xlist_is_empty( root_xp ) )   // no waiting thread
    182239    {
    183240        // get semaphore current value
     
    190247    {
    191248        // get first waiting thread from queue
    192         xptr_t thread_xp = XLIST_FIRST_ELEMENT( queue_xp , thread_t , wait_list );
     249        xptr_t thread_xp = XLIST_FIRST_ELEMENT( root_xp , thread_t , wait_list );
    193250
    194251        // get thread cluster and local poiner
     
    206263}  // end remote_sem_post()
    207264
    208 ////////////////////////////////////////
    209 void remote_sem_destroy( xptr_t sem_xp )
    210 {
    211     // get semaphore cluster and local pointer
    212     cxy_t          sem_cxy = GET_CXY( sem_xp );
    213     remote_sem_t * sem_ptr = (remote_sem_t *)GET_PTR( sem_xp );
    214 
    215     // get lock protecting semaphore
    216     remote_spinlock_lock( XPTR( sem_cxy , &sem_ptr->lock ) );
    217  
    218     // get remote pointer on waiting queue
    219     xptr_t queue_xp = (xptr_t)hal_remote_lwd( XPTR( sem_cxy , &sem_ptr->wait_queue ) );
    220  
    221     if( !xlist_is_empty( queue_xp ) )   // user error
    222     {
    223         printk("WARNING in %s for thread %x in process %x : "
    224                "destroy semaphore, but  waiting threads queue not empty\n",
    225                __FUNCTION__ , CURRENT_THREAD->trdid , CURRENT_PROCESS->pid );
    226     }
    227 
    228     // reset semaphore count
    229     hal_remote_sw( XPTR( sem_cxy , &sem_ptr->count ) , 0 );
    230 
    231     // remove semaphore from process
    232     xptr_t xp_list = (xptr_t)hal_remote_lwd( XPTR( sem_cxy , &sem_ptr->sem_list ) );
    233     xlist_unlink( xp_list );
    234 
    235     // release lock
    236     remote_spinlock_unlock( XPTR( sem_cxy , &sem_ptr->lock ) );
    237 
    238     // release memory allocated
    239     if( sem_cxy == local_cxy )         // reference is local
    240     {
    241         kmem_req_t  req;
    242         req.type = KMEM_SEM;
    243         req.ptr  = sem_ptr;
    244         kmem_free( &req );
    245     }
    246     else                                // reference is remote
    247     {
    248         rpc_semaphore_free_client( sem_cxy , sem_ptr );
    249     }
    250 
    251 }  // end remote_sem_destroy()
    252265
    253266//////////////////////////////////////////////
  • trunk/kernel/libk/remote_sem.h

    r15 r23  
    3030
    3131/*********************************************************************************************
    32  *      This file defines the the POSIX compliant unnamed semaphore.
     32 *      This file defines a POSIX compliant unnamed semaphore.
    3333 *
    3434 * A semaphore is declared by a given user process as a "sem_t" global variable.
     
    4646
    4747/*********************************************************************************************
    48  * This structure defines the kernel remote_sem_t structure.
    49  * It contains the root of a waiting threads queue, implemented as a distributed xlist.
    50  * It contains an xlist of all semaphores, rooted in the reference process descriptor.
    51  * It contains a lock protecting both the semaphore value and the waiting queue.
     48 * This structure defines the kernel semaphore descriptor.
     49 * - It contains the root of a waiting threads queue, implemented as a distributed xlist.
     50 * - It contains an xlist of all semaphores, rooted in the reference process descriptor.
     51 * - It contains a lock protecting both the semaphore value and the waiting queue.
    5252 ********************************************************************************************/
    5353
     
    5757        uint32_t          count;         /*! current value                                      */
    5858    intptr_t          ident;         /*! virtual address in user space == identifier        */
    59     xlist_entry_t     wait_queue;    /*! root of waiting thread queue                       */
    60     xlist_entry_t     sem_list;      /*! member of list of semaphores in same process       */
     59    xlist_entry_t     root;          /*! root of waiting thread queue                       */
     60    xlist_entry_t     list;          /*! member of list of semaphores in same process       */
    6161}
    6262remote_sem_t;
    63 
    64 /*********************************************************************************************
    65  * This enum defines the semaphore operation types supported by the sys_sem() function.
    66  * It must be consistent with the values defined in the semaphore.c file (user library).
    67  ********************************************************************************************/
    68 
    69 typedef enum
    70 {
    71         SEM_INIT,
    72         SEM_GETVALUE,
    73         SEM_WAIT,
    74         SEM_POST,
    75         SEM_DESTROY
    76 }
    77 sem_operation_t;
    78 
    7963
    8064
    8165/*********************************************************************************************
    8266 * This function returns an extended pointer on the remote semaphore identified
    83  * by its virtual address in a given user process. It makes an associative search, scanning
    84  * the list of semaphores rooted in the reference process descriptor.
     67 * by its virtual address in a given user process. It makes an associative search,
     68 * scanning the list of semaphores rooted in the reference process descriptor.
    8569 *********************************************************************************************
    8670 * @ process  : pointer on local process descriptor.
     
    9983 * @ returns 0 if success / returns ENOMEM if error.
    10084 ********************************************************************************************/
    101 error_t remote_sem_init( intptr_t  vaddr,
    102                          uint32_t  value );
     85error_t remote_sem_create( intptr_t  vaddr,
     86                           uint32_t  value );
    10387 
     88/****************************yy***************************************************************
     89 * This function implements the SEM_DESTROY operation.
     90 * It desactivates the semaphore, and releases the physical memory allocated in the
     91 * reference cluster, using a RPC if required.
     92 *********************************************************************************************
     93 * @ sem_xp   : extended pointer on semaphore.
     94 ********************************************************************************************/
     95void remote_sem_destroy( xptr_t sem_xp );
     96
    10497/****************************yy***************************************************************
    10598 * This blocking function implements the SEM_WAIT operation.
     
    123116
    124117/****************************yy***************************************************************
    125  * This function implements the SEM_DESTROY operation.
    126  * It desactivates the semaphore, and releases the physical memory allocated in the
    127  * reference cluster, using a RPC if required.
    128  *********************************************************************************************
    129  * @ sem_xp   : extended pointer on semaphore.
    130  ********************************************************************************************/
    131 void remote_sem_destroy( xptr_t sem_xp );
    132 
    133 /****************************yy***************************************************************
    134118 * This function implements the SEM_GETVALUE operation.
    135119 * It returns in the <data> buffer the semaphore current value.
  • trunk/kernel/libk/rwlock.c

    r14 r23  
    8686 
    8787    // decrement number of readers
    88     hal_atomic_dec( &lock->count );
     88    hal_atomic_add( &lock->count , -1 );
    8989    this->local_locks--;
    9090
  • trunk/kernel/libk/string.h

    r1 r23  
    8383
    8484/********************************************************************************************
    85  * TODO
     85 * this function copies the <src> buffer to the <dst> buffer, including the terminating NUL.
    8686 ********************************************************************************************
     87 * @ dst   : pointer on destination buffer.
     88 * @ src   : pointer on source buffer.
    8789 *******************************************************************************************/
    88 char * strcpy ( char * dest,
     90char * strcpy ( char * dst,
    8991                char * src );
    9092
    9193/********************************************************************************************
    92  * TODO
     94 * This function copies <n> characters from the <sr> buffer to the <dst> buffer.
    9395 ********************************************************************************************
     96 * @ dst   : pointer on destination buffer.
     97 * @ src   : pointer on source buffer.
     98 * @ n     : number of characters to be copied.
    9499 *******************************************************************************************/
    95 char * strncpy ( char    * dest,
     100char * strncpy ( char    * dst,
    96101                 char    * src,
    97102                 uint32_t  n );
    98103
    99104/********************************************************************************************
    100  * TODO
     105 * This function locates the first occurence of the <c> character in the <s> string.
    101106 ********************************************************************************************
     107 * @ s     : string to be analysed.
     108 * @ c     : searched character value (casted to a char)
     109 * @ return pointer on the found character / return NULL if not found.
    102110 *******************************************************************************************/
    103111char * strchr ( const char * s,
     
    105113
    106114/********************************************************************************************
    107  * TODO
     115 * This function locates the last occurence of the <c> character in the <s> string.
    108116 ********************************************************************************************
     117 * @ s     : string to be analysed.
     118 * @ c     : searched character value (casted to a char)
     119 * @ return pointer on the found character / return NULL if not found.
    109120 *******************************************************************************************/
    110121char * strrchr ( const char * t,
  • 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 
  • trunk/kernel/libk/xhtab.h

    r14 r23  
    22 * xhtab.h - Remote access embedded hash table definition.
    33 *
    4  * Author     Alain Greiner          (2016)
     4 * Author     Alain Greiner  (2016,2017)
    55 *
    66 * Copyright (c) UPMC Sorbonne Universites
     
    3131
    3232
    33 /******************************************************************************************
    34  * This file define a generic, embedded, hash table that can be remotely accessed by
    35  * any thread running in any cluster.
    36  * The main goal is to speedup search by key in a set of items identified by their key.
    37  * For this purpose the set of all registered items is split in several subsets:
    38  * Each subset is organised an embedded double linked lists.
    39  * - an item is uniquely identified by a <key>, that can be a single uint32_t,
    40  *   a name (character string), or a more complex structure.
    41  * - From the <key>, the hash table uses an item type specific "xhtab_index()" function,
    42  *   to compute an <index> value, defining a subset of registered items.
    43  * - to discriminate between items that have the same <index>, the hash table uses another
    44  *   item type specific "xhtab_compare()" function for the associative search in subset.
    45  * - Each registered item is a structure, that must contain an embedded xlist_entry,
    46  *   that is part of the xlist implementing the subset.
    47  * - The xhtab header contains an array indexed by <index> and containing the roots
    48  *   of the various xlists implementing the subsets.
    49  *   pointer on the searched item can be obtained by a simple offset.
    50  * Implementation note:
    51  * to use this generic infrastructure for a new type of item, you must define a new
    52  * type in the xhtan_item_type_t" below, and to define the two  associated
    53  * "xhtab_compare() and xhtab_index().
    54  *****************************************************************************************/
     33///////////////////////////////////////////////////////////////////////////////////////////
     34// This file define a generic, embedded, remotely accessible hash table.
     35//
     36// It can be accessed by any thread, running in any cluster.
     37// It is generic as it can be used to register various types of items.
     38// The main goal is to speedup search by key for a large number of items of same type.
     39// For this purpose the set of all registered items is split in several subsets.
     40// Each subset is organised an embedded double linked lists.
     41// - an item is uniquely identified by a <key>, that can be a single uint32_t,
     42//   a name (character string), or a more complex structure.
     43// - From the pointer on <key>, we use an item type specific xhtab_index() function,
     44//   to compute an <index> value, defining a subset of registered items.
     45// - to discriminate between items that have the same <index>, the hash table uses another
     46//   item type specific "xhtab_scan()" function for the associative search in subset.
     47// - Each registered item is a structure, that must contain an embedded xlist_entry,
     48//   that is part of the xlist implementing the subset.
     49//
     50// Implementation Note: for each supported item type ***, you must define the two
     51//                      xhtab_***_index() and xhtab_***_scan() functions, and
     52//                      update the xhtab_init() function.
     53///////////////////////////////////////////////////////////////////////////////////////////
    5554
    5655#define HASHTAB_SIZE    64   // number of subsets
    5756
    5857/******************************************************************************************
    59  * These typedef define the generic xhtab_compare() and xhtab_index() function prototypes.
    60  * It must exist a specific couple of functions for each item type.
    61  * @ entry_xp : extended pointer on an xlist_entry_t in a partial xlist.
    62  * @ key      : local pointer on the searched item key.
    63  * @ item_xp  : buffer to store extended pointer on found item.
     58 * These typedef define the two item type specific function prototypes.
    6459 *****************************************************************************************/
    6560
    66 typedef  bool_t    xhtab_compare_t( xptr_t entry_xp , void * key , xptr_t * item_xp );
     61typedef  xptr_t    xhtab_scan_t( xptr_t xhtab_xp , uint32_t index , void * key );
     62
    6763typedef  uint32_t  xhtab_index_t( void * key );
    6864
     
    7369typedef enum
    7470{
    75     XHTAB_DENTRY_TYPE = 1,                   /*! item is a vfs_dentry_t                  */
    76     XHTAB_INODE_TYPE  = 2,                   /*! item is a vfs_inode_t                   */
     71    XHTAB_DENTRY_TYPE = 0,                    /*! item is a vfs_dentry_t                 */
    7772}
    7873xhtab_item_type_t;
    7974
    8075/******************************************************************************************
    81  * This structure define the root of a generic, remote accessible, hash table.
     76 * This structure define the root of the remote accessible hash table.
    8277 *****************************************************************************************/
    8378
     
    8580{
    8681        xlist_entry_t      roots[HASHTAB_SIZE];   /*! array of roots of xlist                */
    87     xhtab_compare_t  * compare;               /*! item specific index function           */
    88     xhtab_index_t    * index;                 /*! item specific compare function         */
     82    xhtab_index_t    * index;                 /*! item specific function                 */
     83    xhtab_scan_t     * scan;                  /*! item specific function                 */
    8984    uint32_t           items;                 /*! number of registered items             */
    90     remote_rwlock_t  lock;                  /*! lock protecting hash table modifs      */
     85    remote_rwlock_t    lock;                  /*! lock protecting hash table accesses    */
    9186}
    9287xhtab_t;
    9388
    9489/******************************************************************************************
    95  * This function initializes an empty hash table (zero children).
     90 * This function initializes an empty hash table (zero registered item).
    9691 * The initialisation must be done by a thread running in cluster containing the table.
    9792 ******************************************************************************************
     
    9994 * @ type    : item type (see above).
    10095 *****************************************************************************************/
    101 void xhtab_init( xhtab_t * xhtab,
    102                  uint32_t  type );
     96void xhtab_init( xhtab_t           * xhtab,
     97                 xhtab_item_type_t   type );
    10398
    10499/******************************************************************************************
     
    108103 * @ key        : local pointer on item identifier.
    109104 * @ xlist_xp   : extended pointer on xlist_entry_t embedded in item to be registered.
     105 * @ return 0 if success / return EINVAL if item already registered.
    110106 *****************************************************************************************/
    111 void xhtab_register( xptr_t   xhtab_xp,
    112                      void   * key,
    113                      xptr_t   xlist_xp );
     107error_t xhtab_insert( xptr_t   xhtab_xp,
     108                      void   * key,
     109                      xptr_t   xlist_xp );
    114110
    115111/******************************************************************************************
    116112 * This function safely remove an item from the hash table, using the lock protecting it.
    117113 ******************************************************************************************
    118  * @ xhtab_xp : extended pointer on hash table.
    119  * @ key      : local pointer on item identifier.
     114 * @ xhtab_xp       : extended pointer on hash table.
     115 * @ key            : local pointer on item identifier.
     116 * @ xlist_entry_xp : extended pointer on xlist_entry embedded in item to be removed.
     117 * @ return 0 if success / return EINVAL if item not found.
    120118 *****************************************************************************************/
    121 void xhtab_remove( xptr_t   xhtab_xp,
    122                    void   * key );
     119error_t xhtab_remove( xptr_t   xhtab_xp,
     120                      void   * key,
     121                      xptr_t   xlist_entry_xp );
    123122
    124123/******************************************************************************************
     
    133132
    134133
    135 /************************  vfs_dentry_t specific functions  ******************************/
    136 
    137 /******************************************************************************************
    138  * This function compute the hash index from the key, when the item is a vhs_dentry_t.
    139  ******************************************************************************************
    140  * @ key      : local pointer on dentry name.
    141  * @ return the index value, from 0 to (HASHTAB_SIZE - 1)
    142  *****************************************************************************************/
    143 uint32_t xhtab_dentry_index( void * key );
    144 
    145 /******************************************************************************************
    146  * This function check the key value for a given item, when the item is a vhs_dentry_t.
    147  ******************************************************************************************
    148  * @ xlist_xp : extended pointer on xlist_entry_t contained in a vfs_dentry_t.
    149  * @ key      : local pointer on searched dentry name.
    150  * @ return true if the item name matches the searched name.
    151  *****************************************************************************************/
    152 bool_t xhtab_dentry_compare( xptr_t   xlist_xp,
    153                              void   * key,
    154                              xptr_t * item_xp );
    155 
    156 
    157 /************************  vfs_inode_t specific functions  *******************************/
    158 
    159 /******************************************************************************************
    160  * This function compute the hash index from the key, when the item is a vhs_inode_t.
    161  ******************************************************************************************
    162  * @ key      : local pointer on dentry name.
    163  * @ return the index value, from 0 to (HASHTAB_SIZE - 1)
    164  *****************************************************************************************/
    165 uint32_t xhtab_inode_index( void * key );
    166 
    167 /******************************************************************************************
    168  * This function check the key value for a given item, when the item is a vhs_inode_t.
    169  ******************************************************************************************
    170  * @ xlist_xp : extended pointer on xlist_entry_t contained in a vfs_dentry_t.
    171  * @ key      : local pointer on searched dentry name.
    172  * @ return true if the item name matches the searched name.
    173  *****************************************************************************************/
    174 bool_t xhtab_inode_compare( xptr_t   xlist_xp,
    175                             void   * key,
    176                             xptr_t * item_xp );
    177 
    178134#endif  /* _XHTAB_H_ */
Note: See TracChangeset for help on using the changeset viewer.