Changeset 23 for trunk/kernel/libk
- Timestamp:
- Jun 18, 2017, 10:06:41 PM (8 years ago)
- Location:
- trunk/kernel/libk
- Files:
-
- 4 added
- 13 edited
- 2 moved
-
bits.c (modified) (1 diff)
-
bits.h (modified) (2 diffs)
-
elf.c (modified) (13 diffs)
-
htab.c (modified) (3 diffs)
-
htab.h (modified) (3 diffs)
-
remote_barrier.c (modified) (3 diffs)
-
remote_barrier.h (modified) (3 diffs)
-
remote_condvar.c (added)
-
remote_condvar.h (added)
-
remote_mutex.c (added)
-
remote_mutex.h (added)
-
remote_rwlock.c (modified) (3 diffs)
-
remote_rwlock.h (modified) (2 diffs)
-
remote_sem.c (moved) (moved from trunk/kernel/kern/remote_sem.c) (12 diffs)
-
remote_sem.h (moved) (moved from trunk/kernel/kern/remote_sem.h) (5 diffs)
-
rwlock.c (modified) (1 diff)
-
string.h (modified) (2 diffs)
-
xhtab.c (modified) (9 diffs)
-
xhtab.h (modified) (7 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/kernel/libk/bits.c
r11 r23 25 25 #include <hal_types.h> 26 26 #include <bits.h> 27 28 //////////////////////////////////// 29 void 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() 27 39 28 40 ////////////////////////////////////////// -
trunk/kernel/libk/bits.h
r14 r23 78 78 79 79 /********************************************************************************************** 80 * This macro returns the number of 32 bits words required to register sizeentries.80 * This macro returns the number of 32 bits words required to register <size> entries. 81 81 *********************************************************************************************/ 82 82 83 83 #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)]91 84 92 85 typedef uint32_t bitmap_t; 93 86 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 ********************************************************************************************/ 93 void bitmap_init( bitmap_t * bitmap, 94 uint32_t len ); 95 96 /********************************************************************************************* 95 97 * This function set a specific bit in a bitmap. 96 ********************************************************************************************* *98 ********************************************************************************************* 97 99 * @ bitmap : pointer on the bitmap 98 100 * @ index : bit index in the bitmap 99 ******************************************************************************************** */101 ********************************************************************************************/ 100 102 extern inline void bitmap_set( bitmap_t * bitmap, 101 103 uint32_t index ); 102 104 103 /********************************************************************************************* *105 /********************************************************************************************* 104 106 * This function clear a specific bit in a bitmap. 105 ********************************************************************************************* *107 ********************************************************************************************* 106 108 * @ bitmap : pointer on the bitmap 107 109 * @ index : bit index in the bitmap 108 ******************************************************************************************** */110 ********************************************************************************************/ 109 111 extern inline void bitmap_clear( bitmap_t * bitmap, 110 112 uint32_t index ); 111 113 112 /********************************************************************************************* *114 /********************************************************************************************* 113 115 * This function returns a specific bit in a bitmap. 114 ********************************************************************************************* *116 ********************************************************************************************* 115 117 * @ bitmap : pointer on the bitmap 116 118 * @ index : bit index in the bitmap 117 * @ returns tru if bitmap[index] is set118 ******************************************************************************************** */119 * @ returns true if bitmap[index] is set 120 ********************************************************************************************/ 119 121 extern inline bool_t bitmap_state( bitmap_t * bitmap, 120 122 uint32_t index ); 121 123 122 /********************************************************************************************* *124 /********************************************************************************************* 123 125 * This function set a range of bits in a bitmap : [index ... (index + len)[ 124 ********************************************************************************************* *126 ********************************************************************************************* 125 127 * @ bitmap : pointer on the bitmap 126 128 * @ index : first bit index in the bitmap 127 129 * @ len : number of bits to set 128 ******************************************************************************************** */130 ********************************************************************************************/ 129 131 extern void bitmap_set_range( bitmap_t * bitmap, 130 132 uint32_t index, 131 133 uint32_t len ); 132 134 133 /********************************************************************************************* *135 /********************************************************************************************* 134 136 * This function reset a range of bits in a bitmap : [index ... (index + len)[ 135 ********************************************************************************************* *137 ********************************************************************************************* 136 138 * @ bitmap : pointer on the bitmap 137 139 * @ index : first bit index in the bitmap 138 140 * @ len : number of bits to clear 139 ******************************************************************************************** */141 ********************************************************************************************/ 140 142 extern void bitmap_clear_range( bitmap_t * bitmap, 141 143 uint32_t index, 142 144 uint32_t len ); 143 145 144 /********************************************************************************************* *146 /********************************************************************************************* 145 147 * This function returns the index of first bit set in a bitmap, starting from index. 146 ********************************************************************************************* *148 ********************************************************************************************* 147 149 * @ bitmap : pointer on the bitmap 148 150 * @ index : first bit to analyse in the bitmap 149 151 * @ size : number of bits to analyse in bitmap 150 152 * @ returns index if found / returns 0xFFFFFFFF if bit not found 151 ******************************************************************************************** */153 ********************************************************************************************/ 152 154 extern uint32_t bitmap_ffs2( bitmap_t * bitmap, 153 155 uint32_t index, 154 156 uint32_t size ); 155 157 156 /********************************************************************************************* *158 /********************************************************************************************* 157 159 * This function returns the index of first bit cleared in a bitmap, starting from index. 158 ********************************************************************************************* *160 ********************************************************************************************* 159 161 * @ bitmap : pointer on the bitmap 160 162 * @ index : first bit to analyse in the bitmap 161 163 * @ size : number of bits to analyse in bitmap 162 164 * @ returns index if found / returns 0xFFFFFFFF if bit not found 163 ******************************************************************************************** */165 ********************************************************************************************/ 164 166 extern uint32_t bitmap_ffc2( bitmap_t * bitmap, 165 167 uint32_t index, 166 168 uint32_t size ); 167 169 168 /********************************************************************************************* *170 /********************************************************************************************* 169 171 * This function returns the index of first bit set in a bitmap, starting from bit 0. 170 ********************************************************************************************* *172 ********************************************************************************************* 171 173 * @ bitmap : pointer on the bitmap 172 174 * @ size : number of bits to analyse in bitmap 173 175 * @ returns index if found / returns 0xFFFFFFFF if bit not found 174 ******************************************************************************************** */176 ********************************************************************************************/ 175 177 extern uint32_t bitmap_ffs( bitmap_t * bitmap, 176 178 uint32_t size ); 177 179 178 /********************************************************************************************* *180 /********************************************************************************************* 179 181 * This function returns the index of first bit cleared in a bitmap, starting from bit 0. 180 ********************************************************************************************* *182 ********************************************************************************************* 181 183 * @ bitmap : pointer on the bitmap 182 184 * @ size : number of bits to alalyse in bitmap 183 185 * @ returns index if found / returns 0xFFFFFFFF if bit not found 184 ******************************************************************************************** */186 ********************************************************************************************/ 185 187 extern uint32_t bitmap_ffc( bitmap_t * bitmap, 186 188 uint32_t size ); 187 189 188 /********************************************************************************************* *190 /********************************************************************************************* 189 191 * This function returns the number of bits to code a non-zero unsigned integer value. 190 ********************************************************************************************* *192 ********************************************************************************************* 191 193 * @ val : value to analyse 192 194 * @ returns number of bits 193 ******************************************************************************************** */195 ********************************************************************************************/ 194 196 static inline uint32_t bits_nr( uint32_t val ) 195 197 { … … 202 204 } 203 205 204 /********************************************************************************************* *206 /********************************************************************************************* 205 207 * This function takes an unsigned integer value as input argument, and returns another 206 208 * unsigned integer, that is the (base 2) logarithm of the smallest power of 2 contained 207 209 * in the input value. 208 ********************************************************************************************* *210 ********************************************************************************************* 209 211 * @ val : value to analyse 210 212 * @ returns logarithm value 211 ******************************************************************************************** */213 ********************************************************************************************/ 212 214 static inline uint32_t bits_log2( uint32_t val ) 213 215 { -
trunk/kernel/libk/elf.c
r14 r23 31 31 #include <vfs.h> 32 32 #include <elf.h> 33 #include <syscalls.h> 33 34 34 35 … … 85 86 86 87 // load .elf header 87 count = vfs_read( file_xp , buffer , size ); 88 count = vfs_move( true , 89 file_xp, 90 buffer, 91 size ); 88 92 89 93 if( count != size ) … … 163 167 164 168 // 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 ); 166 173 167 174 if( error ) … … 210 217 process_t * process) 211 218 { 219 char path_copy[CONFIG_VFS_MAX_PATH_LENGTH]; 212 220 kmem_req_t req; // kmem request for program header 213 char path_copy[256]; // local copy of pathname214 221 uint32_t length; // actual path length 215 222 Elf32_Ehdr header; // local buffer for .elf header … … 217 224 uint32_t segs_size; // size of buffer for segment descriptors array 218 225 xptr_t file_xp; // extended pointer on created file descriptor 226 uint32_t file_id; // file descriptor index (unused) 219 227 uint32_t count; // bytes counter 220 228 error_t error; … … 223 231 length = hal_strlen_from_uspace( pathname ); 224 232 225 if( length > 255)233 if( length >= CONFIG_VFS_MAX_PATH_LENGTH ) 226 234 { 227 235 printk("\n[ERROR] in %s : pathname length too long\n", __FUNCTION__ ); … … 234 242 // open file 235 243 file_xp = XPTR_NULL; // avoid GCC warning 244 file_id = -1; 236 245 237 246 error = vfs_open( process->vfs_cwd_xp, 238 247 path_copy, 239 VFS_O_RDONLY, 240 &file_xp ); 248 O_RDONLY, 249 0, 250 &file_xp, 251 &file_id ); 241 252 if( error ) 242 253 { … … 252 263 if( error ) 253 264 { 254 vfs_close( file_xp , &count);265 vfs_close( file_xp , file_id ); 255 266 return -1; 256 267 } … … 261 272 { 262 273 printk("\n[ERROR] in %s : no segments found\n", __FUNCTION__ ); 263 vfs_close( file_xp , &count);274 vfs_close( file_xp , file_id ); 264 275 return -1; 265 276 } … … 277 288 { 278 289 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 ); 280 291 return -1; 281 292 } 282 293 283 294 // 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 ); 285 296 286 297 if( error ) 287 298 { 288 299 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 ); 290 301 req.ptr = segs_base; 291 302 kmem_free( &req ); … … 294 305 295 306 // load seg descriptors array to local buffer 296 count = vfs_read( file_xp, 307 count = vfs_move( true, 308 file_xp, 297 309 segs_base, 298 310 segs_size ); … … 301 313 { 302 314 printk("\n[ERROR] in %s : cannot read segments descriptors\n", __FUNCTION__ ); 303 vfs_close( file_xp , &count);315 vfs_close( file_xp , file_id ); 304 316 req.ptr = segs_base; 305 317 kmem_free( &req ); … … 316 328 if( error ) 317 329 { 318 vfs_close( file_xp , &count);330 vfs_close( file_xp , file_id ); 319 331 req.ptr = segs_base; 320 332 kmem_free( &req ); -
trunk/kernel/libk/htab.c
r1 r23 2 2 * htable.c - Generic, embedded hash table implementation. 3 3 * 4 * Author Ghassan Almalles (2008,2009,2010,2011,2012) 5 * Mohamed Lamine Karaoui (2015) 6 * Alain Greiner (2016) 4 * Author Alain Greiner (2016,2017) 7 5 * 8 6 * Copyright (c) UPMC Sorbonne Universites … … 10 8 * This file is part of ALMOS-MKH. 11 9 * 12 * ALMOS-MKH .is free software; you can redistribute it and/or modify it10 * ALMOS-MKH is free software; you can redistribute it and/or modify it 13 11 * under the terms of the GNU General Public License as published by 14 12 * the Free Software Foundation; version 2.0 of the License. 15 13 * 16 * ALMOS-MKH .is distributed in the hope that it will be useful, but14 * ALMOS-MKH is distributed in the hope that it will be useful, but 17 15 * WITHOUT ANY WARRANTY; without even the implied warranty of 18 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU … … 20 18 * 21 19 * 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, 23 21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 24 22 */ 25 23 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 45 static 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 62 static 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 //////////////////////////////////////// 84 void htab_init( htab_t * htab, 85 htab_item_type_t type ) 34 86 { 35 87 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 ///////////////////////////////////////// 113 error_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 ///////////////////////////////////////// 149 error_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 ////////////////////////////////// 185 void * 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 2 2 * htab.h - Generic embedded hash table definition. 3 3 * 4 * Author Ghassan Almalles (2008,2009,2010,2011,2012) 5 * Mohamed Lamine Karaoui (2015) 6 * Alain Greiner (2016) 4 * Authors Alain Greiner (2016,2017) 7 5 * 8 6 * Copyright (c) UPMC Sorbonne Universites … … 29 27 30 28 #include <hal_types.h> 29 #include <rwlock.h> 31 30 #include <list.h> 32 31 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 33 56 /**************************************************************************************** 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. 49 58 ***************************************************************************************/ 50 59 60 struct htab_s; 61 62 typedef void * htab_scan_t( struct htab_s * htab , uint32_t index , void * key ); 63 64 typedef uint32_t htab_index_t( void * key ); 65 51 66 /**************************************************************************************** 52 * This define the generic, user defined, functiontypes.67 * This define the supported item types. 53 68 ***************************************************************************************/ 54 69 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 ); 70 typedef enum 71 { 72 HTAB_INODE_TYPE = 1, /*! item is a vfs_inode_t */ 73 } 74 htab_item_type_t; 59 75 60 76 /**************************************************************************************** 61 * This structure defines the hash table header.77 * This structure defines the the root of a local hash table. 62 78 ***************************************************************************************/ 63 79 64 typedef struct ht _header_s80 typedef struct htab_s 65 81 { 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 */ 70 87 } 71 ht _header_t;88 htab_t; 72 89 73 90 /**************************************************************************************** 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. 75 95 ***************************************************************************************/ 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; 96 void htab_init( htab_t * htab, 97 htab_item_type_t type ); 83 98 84 99 /**************************************************************************************** 85 * This function initialises one hash table node.100 * This function register a new item in the hash table. 86 101 **************************************************************************************** 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. 88 106 ***************************************************************************************/ 89 void ht_node_init( ht_node_t * node ); 107 error_t htab_insert( htab_t * htab, 108 void * key, 109 list_entry_t * list_entry ); 90 110 91 111 /**************************************************************************************** 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. 94 113 **************************************************************************************** 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 E NOMEM 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. 99 118 ***************************************************************************************/ 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 ); 119 error_t htab_remove( htab_t * htab, 120 void * key, 121 list_entry_t * list_entry ); 115 122 116 123 /**************************************************************************************** … … 118 125 * identified by its key. 119 126 **************************************************************************************** 120 * @ h eader : pointer on the hash table header.121 * @ key 122 * @ return pointer on nodeif 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. 123 130 ***************************************************************************************/ 124 ht_node_t * ht_find( ht_header_t * header,125 void* key);131 void * htab_lookup( htab_t * htab, 132 void * key); 126 133 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 );136 134 137 #endif /* _HTAB LE_H_ */135 #endif /* _HTAB_H_ */ -
trunk/kernel/libk/remote_barrier.c
r14 r23 1 1 /* 2 * remote_barrier.c - distributed kernel barrier implementaion2 * remote_barrier.c - Access a POSIX barrier. 3 3 * 4 * Author Alain Greiner (2016 )4 * Author Alain Greiner (2016,2017) 5 5 * 6 6 * Copyright (c) UPMC Sorbonne Universites … … 24 24 #include <hal_types.h> 25 25 #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> 26 33 #include <remote_barrier.h> 27 34 28 ///////////////////////////////////////// 29 inline void remote_barrier( xptr_t xp,35 ///////////////////////////////////////////////// 36 inline void remote_barrier( xptr_t barrier_xp, 30 37 uint32_t count ) 31 38 { 32 39 uint32_t expected; 33 40 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 ); 36 43 37 44 // get barrier sense value … … 57 64 } 58 65 59 66 /////////////////////////////////////////////////// 67 xptr_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 ////////////////////////////////////////////// 109 error_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 //////////////////////////////////////////////// 163 void 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 ///////////////////////////////////////////// 200 void 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 1 1 /* 2 * remote_barrier.h - distributed kernel barrier definition2 * remote_barrier.h - Access a POSIX barrier. 3 3 * 4 4 * Author Alain Greiner (2016) … … 10 10 * ALMOS-MKH is free software; you can redistribute it and/or modify it 11 11 * 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. 13 13 * 14 14 * ALMOS-MKH is distributed in the hope that it will be useful, but … … 27 27 #include <kernel_config.h> 28 28 #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 * **************************************************************************************/ 29 58 30 59 /***************************************************************************************** 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. 36 64 ****************************************************************************************/ 37 65 38 66 typedef struct remote_barrier_s 39 67 { 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 */ 43 75 } 44 76 remote_barrier_t; 45 77 46 78 /***************************************************************************************** 47 * This blocking function implements a toggle barrier. It returns only when all48 * expected threads reach the barrier. It can be used several times without49 * specific initialisation.50 * It is portable, as it uses the remote_lw() & remote_sw() access functions.51 * @ xp : extended pointer on barrier in remote cluster52 * @ count : number of expected thread79 * 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. 53 85 ****************************************************************************************/ 54 inline void remote_barrier( xptr_t xp,86 inline void remote_barrier( xptr_t barrier_xp, 55 87 uint32_t count ); 56 88 57 89 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 ****************************************************************************************/ 98 xptr_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 ****************************************************************************************/ 110 error_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 ****************************************************************************************/ 120 void 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 ****************************************************************************************/ 129 void remote_barrier_wait( xptr_t barrier_xp ); 130 131 58 132 #endif /* _REMOTE_BARRIER_H_ */ -
trunk/kernel/libk/remote_rwlock.c
r1 r23 2 2 * remote_rwlock.c - kernel remote rwlock implementation. 3 3 * 4 * Authors Mohamed Karaoui (2015) 5 * Alain Greiner (2016) 4 * Authors Alain Greiner (2016,2017) 6 5 * 7 6 * Copyright (c) UPMC Sorbonne Universites … … 67 66 68 67 // get next free ticket 69 ticket = hal_remote_ lw( ticket_xp);70 71 // loop to take the lock68 ticket = hal_remote_atomic_add( ticket_xp , 1 ); 69 70 // busy waiting loop to take the lock 72 71 while( ticket != hal_remote_lw( current_xp ) ) 73 72 { … … 147 146 148 147 // get next free ticket 149 ticket = hal_remote_ lw( ticket_xp);148 ticket = hal_remote_atomic_add( ticket_xp , 1 ); 150 149 151 150 // loop to take the lock -
trunk/kernel/libk/remote_rwlock.h
r14 r23 30 30 31 31 /*************************************************************************************** 32 * This structure defines a remote rwdlock,that supports several simultaneous read32 * This file defines a remote kernel lock, that supports several simultaneous read 33 33 * accesses, but only one write access. It implements a ticket based allocation policy. 34 34 * It can be used to synchronize threads running in different clusters, because … … 41 41 * When the lock is taken by another thread, the new-comers use a busy waiting policy. 42 42 * 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. 46 44 **************************************************************************************/ 47 45 -
trunk/kernel/libk/remote_sem.c
r15 r23 23 23 24 24 #include <hal_types.h> 25 #include <hal_remote.h> 25 26 #include <thread.h> 26 27 #include <kmem.h> … … 35 36 { 36 37 // get pointer on local process_descriptor 37 process_t * process = CURRENT_ PROCESS;38 process_t * process = CURRENT_THREAD->process; 38 39 39 40 // get extended pointer on reference process … … 57 58 XLIST_FOREACH( root_xp , iter_xp ) 58 59 { 59 sem_xp = XLIST_ELEMENT( iter_xp , remote_sem_t , sem_list );60 sem_xp = XLIST_ELEMENT( iter_xp , remote_sem_t , list ); 60 61 sem_cxy = GET_CXY( sem_xp ); 61 62 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 ) ); 63 64 if( ident == vaddr ) 64 65 { … … 73 74 } // end remote_sem_from_vaddr() 74 75 75 ///////////////////////////////////////// 76 error_t remote_sem_ init( intptr_t vaddr,77 uint32_t value )76 /////////////////////////////////////////// 77 error_t remote_sem_create( intptr_t vaddr, 78 uint32_t value ) 78 79 { 79 80 xptr_t sem_xp; … … 81 82 82 83 // get pointer on local process descriptor 83 process_t * process = CURRENT_ PROCESS;84 process_t * process = CURRENT_THREAD->process; 84 85 85 86 // get extended pointer on reference process 86 87 xptr_t ref_xp = process->ref_xp; 87 88 89 // get reference process cluster and local pointer 88 90 cxy_t ref_cxy = GET_CXY( ref_xp ); 89 91 process_t * ref_ptr = (process_t *)GET_PTR( ref_xp ); … … 100 102 else // reference is remote 101 103 { 102 rpc_ semaphore_alloc_client( ref_cxy, &sem_xp );104 rpc_kcm_alloc_client( ref_cxy , KMEM_SEM , &sem_xp ); 103 105 sem_ptr = (remote_sem_t *)GET_PTR( sem_xp ); 104 106 } … … 106 108 if( sem_xp == XPTR_NULL ) return ENOMEM; 107 109 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 109 114 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 121 119 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 ) ); 123 123 xlist_add_first( root_xp , xp_list ); 124 remote_spinlock_unlock( XPTR( ref_cxy , &ref_ptr->sync_lock ) ); 124 125 125 126 return 0; … … 127 128 } // en remote_sem_init() 128 129 130 //////////////////////////////////////// 131 void 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 129 186 ////////////////////////////////// 130 187 void remote_sem_wait( xptr_t sem_xp ) … … 153 210 154 211 // 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 ) ); 156 213 xptr_t thread_xp = XPTR( local_cxy , this ); 157 214 xlist_add_last( root_xp , thread_xp ); … … 177 234 178 235 // 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 thread236 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 182 239 { 183 240 // get semaphore current value … … 190 247 { 191 248 // 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 ); 193 250 194 251 // get thread cluster and local poiner … … 206 263 } // end remote_sem_post() 207 264 208 ////////////////////////////////////////209 void remote_sem_destroy( xptr_t sem_xp )210 {211 // get semaphore cluster and local pointer212 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 semaphore216 remote_spinlock_lock( XPTR( sem_cxy , &sem_ptr->lock ) );217 218 // get remote pointer on waiting queue219 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 error222 {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 count229 hal_remote_sw( XPTR( sem_cxy , &sem_ptr->count ) , 0 );230 231 // remove semaphore from process232 xptr_t xp_list = (xptr_t)hal_remote_lwd( XPTR( sem_cxy , &sem_ptr->sem_list ) );233 xlist_unlink( xp_list );234 235 // release lock236 remote_spinlock_unlock( XPTR( sem_cxy , &sem_ptr->lock ) );237 238 // release memory allocated239 if( sem_cxy == local_cxy ) // reference is local240 {241 kmem_req_t req;242 req.type = KMEM_SEM;243 req.ptr = sem_ptr;244 kmem_free( &req );245 }246 else // reference is remote247 {248 rpc_semaphore_free_client( sem_cxy , sem_ptr );249 }250 251 } // end remote_sem_destroy()252 265 253 266 ////////////////////////////////////////////// -
trunk/kernel/libk/remote_sem.h
r15 r23 30 30 31 31 /********************************************************************************************* 32 * This file defines the thePOSIX compliant unnamed semaphore.32 * This file defines a POSIX compliant unnamed semaphore. 33 33 * 34 34 * A semaphore is declared by a given user process as a "sem_t" global variable. … … 46 46 47 47 /********************************************************************************************* 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. 52 52 ********************************************************************************************/ 53 53 … … 57 57 uint32_t count; /*! current value */ 58 58 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 */ 61 61 } 62 62 remote_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 enum70 {71 SEM_INIT,72 SEM_GETVALUE,73 SEM_WAIT,74 SEM_POST,75 SEM_DESTROY76 }77 sem_operation_t;78 79 63 80 64 81 65 /********************************************************************************************* 82 66 * 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, scanning84 * 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. 85 69 ********************************************************************************************* 86 70 * @ process : pointer on local process descriptor. … … 99 83 * @ returns 0 if success / returns ENOMEM if error. 100 84 ********************************************************************************************/ 101 error_t remote_sem_ init( intptr_t vaddr,102 uint32_t value );85 error_t remote_sem_create( intptr_t vaddr, 86 uint32_t value ); 103 87 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 ********************************************************************************************/ 95 void remote_sem_destroy( xptr_t sem_xp ); 96 104 97 /****************************yy*************************************************************** 105 98 * This blocking function implements the SEM_WAIT operation. … … 123 116 124 117 /****************************yy*************************************************************** 125 * This function implements the SEM_DESTROY operation.126 * It desactivates the semaphore, and releases the physical memory allocated in the127 * 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***************************************************************134 118 * This function implements the SEM_GETVALUE operation. 135 119 * It returns in the <data> buffer the semaphore current value. -
trunk/kernel/libk/rwlock.c
r14 r23 86 86 87 87 // decrement number of readers 88 hal_atomic_ dec( &lock->count);88 hal_atomic_add( &lock->count , -1 ); 89 89 this->local_locks--; 90 90 -
trunk/kernel/libk/string.h
r1 r23 83 83 84 84 /******************************************************************************************** 85 * TODO85 * this function copies the <src> buffer to the <dst> buffer, including the terminating NUL. 86 86 ******************************************************************************************** 87 * @ dst : pointer on destination buffer. 88 * @ src : pointer on source buffer. 87 89 *******************************************************************************************/ 88 char * strcpy ( char * d est,90 char * strcpy ( char * dst, 89 91 char * src ); 90 92 91 93 /******************************************************************************************** 92 * T ODO94 * This function copies <n> characters from the <sr> buffer to the <dst> buffer. 93 95 ******************************************************************************************** 96 * @ dst : pointer on destination buffer. 97 * @ src : pointer on source buffer. 98 * @ n : number of characters to be copied. 94 99 *******************************************************************************************/ 95 char * strncpy ( char * d est,100 char * strncpy ( char * dst, 96 101 char * src, 97 102 uint32_t n ); 98 103 99 104 /******************************************************************************************** 100 * T ODO105 * This function locates the first occurence of the <c> character in the <s> string. 101 106 ******************************************************************************************** 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. 102 110 *******************************************************************************************/ 103 111 char * strchr ( const char * s, … … 105 113 106 114 /******************************************************************************************** 107 * T ODO115 * This function locates the last occurence of the <c> character in the <s> string. 108 116 ******************************************************************************************** 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. 109 120 *******************************************************************************************/ 110 121 char * strrchr ( const char * t, -
trunk/kernel/libk/xhtab.c
r14 r23 2 2 * xhtab.c - Remote access embedded hash table implementation. 3 3 * 4 * Author Alain Greiner (2016 )4 * Author Alain Greiner (2016,2017) 5 5 * 6 6 * Copyright (c) UPMC Sorbonne Universites … … 34 34 35 35 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 ///////////////////////////////////////// 49 uint32_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>. 40 63 // 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. 44 66 // @ index : index of sub-list to be scanned. 45 67 // @ 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 //////////////////////////////////////////////////// 72 static 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 ); 54 94 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; 63 106 } 64 107 65 ///////////////////////////////// 66 void xhtab_init( xhtab_t * xhtab, 67 uint32_t type ) 108 //////////////////////////////////////////////////////////////////////////////////////// 109 // Generic access functions 110 //////////////////////////////////////////////////////////////////////////////////////// 111 112 ////////////////////////////////////////// 113 void xhtab_init( xhtab_t * xhtab, 114 xhtab_item_type_t type ) 68 115 { 69 116 uint32_t i; … … 76 123 if( type == XHTAB_DENTRY_TYPE ) 77 124 { 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; 80 127 } 81 128 else … … 92 139 93 140 /////////////////////////////////////// 94 void xhtab_register( xptr_t xhtab_xp, 95 void * key, 96 xptr_t xlist_xp ) 97 { 141 error_t xhtab_insert( xptr_t xhtab_xp, 142 void * key, 143 xptr_t xlist_xp ) 144 { 145 146 printk("\n @@@ xhtab_insert : 0 / name = %s / xhtab_xp = %l / xlist_xp = %l\n", 147 key , xhtab_xp , xlist_xp ); 148 98 149 // get xhtab cluster and local pointer 99 150 cxy_t xhtab_cxy = GET_CXY( xhtab_xp ); … … 103 154 uint32_t index = xhtab_ptr->index( key ); 104 155 156 printk("\n @@@ xhtab_insert : 1 / name = %s / index = %d\n", 157 key , index ); 158 105 159 // take the lock protecting hash table 106 160 remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); 107 161 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 170 printk("\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 186 printk("\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() 118 192 119 193 ///////////////////////////////////// 120 void xhtab_remove( xptr_t xhtab_xp, 121 void * key ) 194 error_t xhtab_remove( xptr_t xhtab_xp, 195 void * key, 196 xptr_t xlist_entry_xp ) 122 197 { 123 198 // get xhtab cluster and local pointer … … 125 200 xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp ); 126 201 202 // compute index from key 203 uint32_t index = xhtab_ptr->index( key ); 204 127 205 // take the lock protecting hash table 128 206 remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); 129 207 130 // compute index from key131 uint32_t index = xhtab_ptr->index( key );132 133 208 // 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; 140 217 } 141 218 else // remove item if found 142 219 { 143 // get item cluster and local pointer144 cxy_t item_cxy = GET_CXY( item_xp );145 vfs_dentry_t * item_ptr = (vfs_dentry_t *)GET_PTR( item_xp );146 147 220 // remove item from hash table <=> unlink xlist_entry_t 148 xlist_unlink( XPTR( item_cxy , &item_ptr->xlist ));221 xlist_unlink( xlist_entry_xp ); 149 222 150 223 // update number of registered items … … 153 226 // release the lock protecting hash table 154 227 remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) ); 155 } 156 } // end xhtab_unregister() 228 229 return 0; 230 } 231 } // end xhtab_remove() 157 232 158 233 ///////////////////////////////////////// … … 173 248 174 249 // scan sub-list 175 item_xp = xhtab_ scan( xhtab_cxy , xhtab_ptr, index , key );250 item_xp = xhtab_ptr->scan( xhtab_xp , index , key ); 176 251 177 252 // release the lock protecting hash table … … 183 258 184 259 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 table203 204 char * searched_name = key; // local pointer on searched name205 206 // compute name length207 uint32_t length = strlen( searched_name );208 209 // get extended pointer on dentry containing the xlist_entry_t210 xptr_t dentry_xp = XLIST_ELEMENT( xlist_xp , vfs_dentry_t , xlist );211 212 // get dentry cluster and local pointer213 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 name217 hal_remote_memcpy( XPTR( local_cxy , tested_name ) ,218 XPTR( dentry_cxy , dentry_ptr->name ) , length );219 220 // check matching / return if match221 if( strcmp( tested_name , searched_name ) == 0 )222 {223 return true;224 *item_xp = dentry_xp;225 }226 else227 {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_t251 xptr_t inode_xp = XLIST_ELEMENT( xlist_xp , vfs_inode_t , xlist );252 253 // get inode cluster and local pointer254 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 inum258 tested_inum = hal_remote_lw( XPTR( inode_cxy , &inode_ptr->inum ) );259 260 // check matching / return if match261 if( tested_inum == *searched_inum )262 {263 return true;264 *item_xp = inode_xp;265 }266 else267 {268 return false;269 }270 }271 -
trunk/kernel/libk/xhtab.h
r14 r23 2 2 * xhtab.h - Remote access embedded hash table definition. 3 3 * 4 * Author Alain Greiner (2016)4 * Author Alain Greiner (2016,2017) 5 5 * 6 6 * Copyright (c) UPMC Sorbonne Universites … … 31 31 32 32 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 /////////////////////////////////////////////////////////////////////////////////////////// 55 54 56 55 #define HASHTAB_SIZE 64 // number of subsets 57 56 58 57 /****************************************************************************************** 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. 64 59 *****************************************************************************************/ 65 60 66 typedef bool_t xhtab_compare_t( xptr_t entry_xp , void * key , xptr_t * item_xp ); 61 typedef xptr_t xhtab_scan_t( xptr_t xhtab_xp , uint32_t index , void * key ); 62 67 63 typedef uint32_t xhtab_index_t( void * key ); 68 64 … … 73 69 typedef enum 74 70 { 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 */ 77 72 } 78 73 xhtab_item_type_t; 79 74 80 75 /****************************************************************************************** 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. 82 77 *****************************************************************************************/ 83 78 … … 85 80 { 86 81 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 */ 89 84 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 */ 91 86 } 92 87 xhtab_t; 93 88 94 89 /****************************************************************************************** 95 * This function initializes an empty hash table (zero children).90 * This function initializes an empty hash table (zero registered item). 96 91 * The initialisation must be done by a thread running in cluster containing the table. 97 92 ****************************************************************************************** … … 99 94 * @ type : item type (see above). 100 95 *****************************************************************************************/ 101 void xhtab_init( xhtab_t * xhtab,102 uint32_ttype );96 void xhtab_init( xhtab_t * xhtab, 97 xhtab_item_type_t type ); 103 98 104 99 /****************************************************************************************** … … 108 103 * @ key : local pointer on item identifier. 109 104 * @ 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. 110 106 *****************************************************************************************/ 111 void xhtab_register( xptr_t xhtab_xp,112 void * key,113 xptr_t xlist_xp );107 error_t xhtab_insert( xptr_t xhtab_xp, 108 void * key, 109 xptr_t xlist_xp ); 114 110 115 111 /****************************************************************************************** 116 112 * This function safely remove an item from the hash table, using the lock protecting it. 117 113 ****************************************************************************************** 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. 120 118 *****************************************************************************************/ 121 void xhtab_remove( xptr_t xhtab_xp, 122 void * key ); 119 error_t xhtab_remove( xptr_t xhtab_xp, 120 void * key, 121 xptr_t xlist_entry_xp ); 123 122 124 123 /****************************************************************************************** … … 133 132 134 133 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 178 134 #endif /* _XHTAB_H_ */
Note: See TracChangeset
for help on using the changeset viewer.
