Changeset 619 for trunk/kernel/libk/remote_barrier.h
- Timestamp:
- Feb 12, 2019, 1:15:47 PM (5 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/kernel/libk/remote_barrier.h
r581 r619 2 2 * remote_barrier.h - POSIX barrier definition. 3 3 * 4 * Author Alain Greiner (2016,2017,2018 )4 * Author Alain Greiner (2016,2017,2018,2019) 5 5 * 6 6 * Copyright (c) UPMC Sorbonne Universites … … 29 29 #include <remote_busylock.h> 30 30 #include <xlist.h> 31 #include <shared_pthread.h> 31 32 32 33 /*************************************************************************************** 33 * This file definesa POSIX compliant barrier.34 * This file defines two implementations for a POSIX compliant barrier. 34 35 * 35 36 * It is used by multi-threaded user applications to synchronise threads running in 36 * different clusters, as all access functions uses hal_remote_l32() / hal_remote_s32() 37 * 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. 37 * different clusters. Access functions use RPCs for barrier creation/destruction, 38 * and use remote access primitives for actual synchronisation (wait function). 39 * 40 * A barrier is declared by a given user process as a "pthread_barrier_t" user variable. 41 * This user type is implemented in user space as an unsigned long, but the value is not 42 * used by the kernel. ALMOS-MKH uses only the barrier virtual address as an identifier. 43 * For each user barrier, ALMOS-MKH creates a kernel structure, dynamically allocated 44 * by the "generic_barrier_create()" function, destroyed by the "remote_barrier_destroy()" 45 * function, and used by the "generic_barrier_wait()" function. 46 * 47 * Implementation note: 48 * ALMOS-MKH supports two barrier implementations: 49 * 50 * 1) simple_barrier_t 51 * If the pointer on the barrier attributes is NULL, the barrier is implemented as 52 * a shared variable localized in the reference process cluster. 53 * There is a risk of contention when the number of synchronizing threads is large. 54 * 55 * 2) dqt_barrier_t 56 * If the (x_size, y_size, nthreads) arguments are defined in the barrier attributes, 57 * the barrier is implemented as a hierarchical quad-tree covering all clusters in the 58 * (x_size * ysize) mesh, including cluster (0,0), with nthreads per cluster, and called 59 * DQT : Distributed Quad Tree. This DQT implementation supposes a regular architecture, 60 * and a strong contraint on the threads placement: exactly "nthreads" threads per 61 * cluster in the (x_size * y_size) mesh. 62 * 63 * For both implementations, the blocking "generic_barrier_wait()" function implements 64 * a descheduling policy when the calling thread is not the last expected thread: 65 * the calling thread is registered in a waiting queue, rooted in the barrier structure, 66 * and the the calling thread is blocked on the THREAD_BLOCKED_USERSYNC condition. 67 * The last arrived thread unblocks all registered waiting threads. 52 68 * **************************************************************************************/ 53 69 54 /***************************************************************************************** 55 * This structure defines the barrier descriptor. 56 * - It contains an xlist of all barriers dynamically created by a given process, 57 * rooted in the reference process descriptor. 58 * - It contains the root of another xlist to register all arrived threads. 59 ****************************************************************************************/ 60 61 typedef struct remote_barrier_s 62 { 63 remote_busylock_t lock; /*! lock protecting list of waiting threads */ 64 intptr_t ident; /*! virtual address in user space == identifier */ 65 uint32_t current; /*! number of arrived threads */ 66 uint32_t sense; /*! barrier state (toggle) */ 67 uint32_t nb_threads; /*! number of expected threads */ 68 xlist_entry_t list; /*! member of list of barriers in same process */ 69 xlist_entry_t root; /*! root of list of waiting threads */ 70 71 72 /***************************************************************************************** 73 * generic barrier descriptor and access functions 74 ***************************************************************************************** 75 * This generic structure is used by both the simple and the QOT implementations. 76 * It is implemented in the reference process cluster, and contains 77 * - the barrier identifier, 78 * - the implementation type (simple or QDT), 79 * - an xlist implementing the set of barriers dynamically created by a given process, 80 * - a pointer on the implementation specific descriptor (simple_barrier / sqt_barrier). 81 ****************************************************************************************/ 82 83 typedef struct generic_barrier_s 84 { 85 intptr_t ident; /*! virtual address in user space == identifier */ 86 xlist_entry_t list; /*! member of list of barriers in same process */ 87 bool_t is_dqt; /*! DQT implementation when true */ 88 void * extend; /*! implementation specific barrier descriptor */ 70 89 } 71 remote_barrier_t; 72 90 generic_barrier_t; 73 91 74 92 /***************************************************************************************** … … 76 94 * by its virtual address in a given user process. It makes an associative search, 77 95 * scanning the list of barriers rooted in the reference process descriptor. 96 * It can be used for both simple and DQT barriers, registered in the same list. 78 97 ***************************************************************************************** 79 98 * @ ident : barrier virtual address, used as identifier. 80 99 * @ returns extended pointer on barrier if success / returns XPTR_NULL if not found. 81 100 ****************************************************************************************/ 82 xptr_t remote_barrier_from_ident( intptr_t ident ); 83 84 /***************************************************************************************** 85 * This function implement the pthread_barrier_init() syscall. 86 * It allocates memory for the barrier descriptor in the reference cluster for 87 * the calling process, it initializes the barrier state, and register it in the 88 * list of barriers owned by the reference process. 89 ***************************************************************************************** 90 * @ count : number of expected threads. 91 * @ ident : barrier identifier (virtual address in user space). 92 * @ return 0 if success / return ENOMEM if failure. 93 ****************************************************************************************/ 94 error_t remote_barrier_create( intptr_t ident, 95 uint32_t count ); 96 97 /***************************************************************************************** 98 * This function implement the pthread_barrier_destroy() syscall. 99 * It releases thr memory allocated for the barrier descriptor, and remove the barrier 100 * from the list of barriers owned by the reference process. 101 ***************************************************************************************** 102 * @ barrier_xp : extended pointer on barrier descriptor. 103 ****************************************************************************************/ 104 void remote_barrier_destroy( xptr_t barrier_xp ); 105 106 /***************************************************************************************** 107 * This function implement the pthread_barrier_wait() syscall. 108 * It returns only when the number of expected threads (registered in the barrier 109 * dexcriptor) reach the barrier. 110 ***************************************************************************************** 111 * @ barrier_xp : extended pointer on barrier descriptor. 112 ****************************************************************************************/ 113 void remote_barrier_wait( xptr_t barrier_xp ); 101 xptr_t generic_barrier_from_ident( intptr_t ident ); 102 103 /***************************************************************************************** 104 * This function implements the pthread_barrier_init() syscall. 105 * It allocates and initialises the generic barrier descriptor in the reference process 106 * cluster, and - depending on the <attr> argument, calls the relevant (simple or DQT) 107 * function to allocate and initialize the implementation dependant barrier descriptor. 108 * Finally, it registers the barrier in the reference process xlist of user barriers. 109 * It can be called by a thread running in any cluster, as it use RPC if required. 110 ***************************************************************************************** 111 * @ ident : barrier virtual address, used as identifier. 112 * @ count : number of expected threads. 113 * @ attr : barrier attributes (x_size,y_size,nthreads), used by QDT implementation. 114 * @ returns 0 if success / returns -1 if not found. 115 ****************************************************************************************/ 116 error_t generic_barrier_create( intptr_t ident, 117 uint32_t count, 118 pthread_barrierattr_t * attr ); 119 120 /***************************************************************************************** 121 * This function implements the pthread_barrier_destroy() syscall. 122 * It calls the relevant function (simple or DQT) to release the memory allocated for 123 * the implementation specific barrier descriptor, and releases the memory allocated 124 * for the generic barrier descriptor. 125 * It removes the barrier from the list of barriers rooted in the reference process. 126 * It can be called by a thread running in any cluster, as it use RPC if required. 127 ***************************************************************************************** 128 * @ gen_barrier_xp : extended pointer on generic barrier descriptor. 129 ****************************************************************************************/ 130 void generic_barrier_destroy( xptr_t gen_barrier_xp ); 131 132 /***************************************************************************************** 133 * This blocking function implements the pthread_barrier_wait() syscall. 134 * It calls the relevant function (simple or DQT) depending on the implementation, 135 * and returns only when all expected threads reach the barrier. 136 * It can be called by a thread running in any cluster, as it use remote accesses. 137 ***************************************************************************************** 138 * @ gen_barrier_xp : extended pointer on generic barrier descriptor. 139 ****************************************************************************************/ 140 void generic_barrier_wait( xptr_t gen_barrier_xp ); 141 142 143 144 145 146 147 /***************************************************************************************** 148 * simple barrier descriptor 149 ***************************************************************************************** 150 * This structure defines the simple barrier descriptor. It is localized in the process 151 * reference cluster, as an extension of the generic barrier descriptor. 152 * It implements a toggle barrier remotely accessed by all threads. 153 * It contains the root of the xlist registering all arrived threads. 154 ****************************************************************************************/ 155 156 typedef struct simple_barrier_s 157 { 158 remote_busylock_t lock; /*! lock protecting list of waiting threads */ 159 uint32_t current; /*! number of arrived threads */ 160 uint32_t sense; /*! barrier state (toggle) */ 161 uint32_t arity; /*! number of expected threads */ 162 xlist_entry_t root; /*! root of list of waiting threads */ 163 } 164 simple_barrier_t; 165 166 /***************************************************************************************** 167 * This function allocates memory for the simple barrier descriptor in the reference 168 * cluster of the calling process. It initializes the barrier state and returns 169 * a local pointer on the created simple barrier descriptor in reference cluster. 170 * It can be called by a thread running in any cluster, as it use RPC if required. 171 ***************************************************************************************** 172 * @ count : [in] number of expected threads. 173 * @ return Local pointer on barrier descriptor if success / return NULL if failure. 174 ****************************************************************************************/ 175 simple_barrier_t * simple_barrier_create( uint32_t count ); 176 177 /***************************************************************************************** 178 * This function releases the memory allocated for the simple barrier descriptor. 179 * It can be called by a thread running in any cluster, as it use RPC if required. 180 ***************************************************************************************** 181 * @ barrier_xp : extended pointer on simple barrier descriptor. 182 ****************************************************************************************/ 183 void simple_barrier_destroy( xptr_t barrier_xp ); 184 185 /***************************************************************************************** 186 * This blocking function returns only when all expected threads reach the barrier. 187 * It can be called by a thread running in any cluster, as it use remote accesses. 188 * Waiting threads use a descheduling policy. 189 ***************************************************************************************** 190 * @ barrier_xp : extended pointer on simple barrier descriptor. 191 ****************************************************************************************/ 192 void simple_barrier_wait( xptr_t barrier_xp ); 193 194 195 196 197 198 /***************************************************************************************** 199 * dqt_barrier 200 ***************************************************************************************** 201 * These structuree define the hierarchical DQT barrier, physically distributed in a 202 * mesh of clusters defined by the (x_size, y_size, nthreads) arguments: 203 * . The involved clusters form a mesh [x_size * y_size] 204 * . The lower left involved cluster is cluster(0,0) 205 * . The number of threads per cluster is the same in all clusters. 206 * 207 * Implementation note: 208 * - The quad three is implemented as a three dimensions array of node[x][y][l] 209 * . [x][y] are the cluster coordinates / max values are (DQT_XMAX-1), (DQT_YMAX-1) 210 * . [l] is the node level / 0 for terminal nodes / (DQT_LMAX-1) for the root node 211 * - The dqt_barrier_t is the global barrier descriptor, allocated in the reference 212 * process cluster as an extension of the generic barrier descriptor. It contains a 213 * 3D array of extended pointers on all DQT nodes implementing the DQT barrier. 214 * - The dqt_node_t is a local barrier implementing a togle barrier between all threads 215 * of a given cluster (for a terminal node), or between all representatives of the four 216 * children nodes (for a non terminal node). 217 ****************************************************************************************/ 218 219 #define DQT_XMAX 16 // max number of clusters in a row 220 #define DQT_YMAX 16 // max number of clusters in a column 221 #define DQT_LMAX 5 // max depth of the quad tree 222 223 typedef struct dqt_node_s 224 { 225 remote_busylock_t lock; /*! lock protecting list of waiting threads */ 226 volatile uint32_t sense; /*! barrier state (toggle) */ 227 volatile uint32_t current; /*! number of locally arrived threads */ 228 uint32_t arity; /*! total number of locally expected threads */ 229 uint32_t level; /*! hierarchical level (0 is bottom) */ 230 xptr_t parent_xp; /*! x_pointer on parent node (NULL for root) */ 231 xptr_t child_xp[4]; /*! x_pointer on children node (NULL for bottom) */ 232 xlist_entry_t root; /*! root of list of waiting threads */ 233 } 234 dqt_node_t; 235 236 typedef struct dqt_barrier_s 237 { 238 xptr_t node_xp[DQT_XMAX][DQT_YMAX][DQT_LMAX]; /*! array of xptr on DQT nodes */ 239 240 uint32_t x_size; /*! number of clusters in one row of DQT mesh */ 241 uint32_t y_size; /*! number of clusters in one column of DQT mesh */ 242 uint32_t nthreads; /*! number of expected threads in one cluster */ 243 } 244 dqt_barrier_t; 245 246 /***************************************************************************************** 247 * This function allocates memory for the DQT barrier descriptor in the reference cluster 248 * of the calling process. It allocates also memory in all clusters of the QDT mesh, 249 * to store up to 5 QDT nodes per cluster. 250 * It initializes the barrier descriptor, including initialisation of the parent/children 251 * extended pointers in the distributed QDT nodes. 252 * It returns a local pointer on the QDT barrier descriptor in reference cluster. 253 * It can be called by a thread running in any cluster, as it use RPCs for memory 254 * allocation, and remote access for QDT initialisation. 255 ***************************************************************************************** 256 * @ x_size : [in] number of clusters in a line of DQT mesh. 257 * @ y_size : [in] number of clusters in a column of DQT mesh. 258 * @ nthreads : [in] number of threads per cluster. 259 * @ return Local pointer on barrier descriptor if success / return NULL if failure. 260 ****************************************************************************************/ 261 dqt_barrier_t * dqt_barrier_create( uint32_t x_size, 262 uint32_t y_size, 263 uint32_t nthreads ); 264 265 /***************************************************************************************** 266 * This function releases all memory allocated for the QDT barrier descriptor. 267 * It removes the barrier from the list of barriers rooted in the reference process. 268 * It can be called by a thread running in any cluster, as it use RPCs. 269 ***************************************************************************************** 270 * @ barrier_xp : extended pointer on DQT barrier descriptor. 271 ****************************************************************************************/ 272 void dqt_barrier_destroy( xptr_t barrier_xp ); 273 274 /***************************************************************************************** 275 * This blocking function returns only when all expected threads reach the barrier. 276 * It can be called by a thread running in any cluster, as it use remote accesses. 277 * Waiting threads use a descheduling policy. 278 ***************************************************************************************** 279 * @ barrier_xp : extended pointer on DQT barrier descriptor. 280 ****************************************************************************************/ 281 void dqt_barrier_wait( xptr_t barrier_xp ); 282 114 283 115 284
Note: See TracChangeset
for help on using the changeset viewer.