[f07e037] | 1 | // |
---|
| 2 | // Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo |
---|
| 3 | // |
---|
| 4 | // The contents of this file are covered under the licence agreement in the |
---|
| 5 | // file "LICENCE" distributed with Cforall. |
---|
| 6 | // |
---|
[84c52a8] | 7 | // monitor_desc.c -- |
---|
[f07e037] | 8 | // |
---|
| 9 | // Author : Thierry Delisle |
---|
| 10 | // Created On : Thd Feb 23 12:27:26 2017 |
---|
[6b0b624] | 11 | // Last Modified By : Peter A. Buhr |
---|
[38ef0de] | 12 | // Last Modified On : Mon Jul 31 14:59:05 2017 |
---|
| 13 | // Update Count : 3 |
---|
[f07e037] | 14 | // |
---|
| 15 | |
---|
| 16 | #include "monitor" |
---|
| 17 | |
---|
[a933dcf4] | 18 | #include <stdlib> |
---|
| 19 | |
---|
[5ea06d6] | 20 | #include "libhdr.h" |
---|
[2ac095d] | 21 | #include "kernel_private.h" |
---|
[f07e037] | 22 | |
---|
[0c78741] | 23 | //----------------------------------------------------------------------------- |
---|
| 24 | // Forward declarations |
---|
| 25 | static inline void set_owner( monitor_desc * this, thread_desc * owner ); |
---|
| 26 | static inline thread_desc * next_thread( monitor_desc * this ); |
---|
[97e3296] | 27 | static inline int is_accepted( thread_desc * owner, monitor_desc * this, monitor_desc ** group, int group_cnt, void (*func)() ); |
---|
[0c78741] | 28 | |
---|
| 29 | static inline void lock_all( spinlock ** locks, unsigned short count ); |
---|
| 30 | static inline void lock_all( monitor_desc ** source, spinlock ** /*out*/ locks, unsigned short count ); |
---|
| 31 | static inline void unlock_all( spinlock ** locks, unsigned short count ); |
---|
| 32 | static inline void unlock_all( monitor_desc ** locks, unsigned short count ); |
---|
| 33 | |
---|
| 34 | static inline void save_recursion ( monitor_desc ** ctx, unsigned int * /*out*/ recursions, unsigned short count ); |
---|
| 35 | static inline void restore_recursion( monitor_desc ** ctx, unsigned int * /*in */ recursions, unsigned short count ); |
---|
| 36 | |
---|
[97e3296] | 37 | static inline void init ( int count, monitor_desc ** monitors, __condition_node_t * waiter, __condition_criterion_t * criteria ); |
---|
| 38 | static inline void init_push( int count, monitor_desc ** monitors, __condition_node_t * waiter, __condition_criterion_t * criteria ); |
---|
| 39 | |
---|
[0c78741] | 40 | static inline thread_desc * check_condition( __condition_criterion_t * ); |
---|
| 41 | static inline void brand_condition( condition * ); |
---|
| 42 | static inline unsigned short insert_unique( thread_desc ** thrds, unsigned short end, thread_desc * val ); |
---|
| 43 | |
---|
[97e3296] | 44 | static inline thread_desc * search_entry_queue( __acceptable_t * acceptables, int acc_count, monitor_desc ** monitors, int count ); |
---|
| 45 | |
---|
| 46 | //----------------------------------------------------------------------------- |
---|
| 47 | // Useful defines |
---|
| 48 | #define wait_ctx(thrd, user_info) /* Create the necessary information to use the signaller stack */ \ |
---|
| 49 | __condition_node_t waiter = { thrd, count, user_info }; /* Create the node specific to this wait operation */ \ |
---|
| 50 | __condition_criterion_t criteria[count]; /* Create the creteria this wait operation needs to wake up */ \ |
---|
| 51 | init( count, monitors, &waiter, criteria ); /* Link everything together */ \ |
---|
| 52 | |
---|
| 53 | #define wait_ctx_primed(thrd, user_info) /* Create the necessary information to use the signaller stack */ \ |
---|
| 54 | __condition_node_t waiter = { thrd, count, user_info }; /* Create the node specific to this wait operation */ \ |
---|
| 55 | __condition_criterion_t criteria[count]; /* Create the creteria this wait operation needs to wake up */ \ |
---|
| 56 | init_push( count, monitors, &waiter, criteria ); /* Link everything together and push it to the AS-Stack */ \ |
---|
| 57 | |
---|
| 58 | #define monitor_ctx( mons, cnt ) /* Define that create the necessary struct for internal/external scheduling operations */ \ |
---|
| 59 | monitor_desc ** monitors = mons; /* Save the targeted monitors */ \ |
---|
| 60 | unsigned short count = cnt; /* Save the count to a local variable */ \ |
---|
| 61 | unsigned int recursions[ count ]; /* Save the current recursion levels to restore them later */ \ |
---|
| 62 | spinlock * locks [ count ]; /* We need to pass-in an array of locks to BlockInternal */ \ |
---|
| 63 | |
---|
[0c78741] | 64 | //----------------------------------------------------------------------------- |
---|
| 65 | // Enter/Leave routines |
---|
[690f13c] | 66 | |
---|
| 67 | |
---|
[cb0e6de] | 68 | extern "C" { |
---|
[97e3296] | 69 | // Enter single monitor |
---|
| 70 | static void __enter_monitor_desc( monitor_desc * this, monitor_desc ** group, int group_cnt, void (*func)() ) { |
---|
| 71 | // Lock the monitor spinlock, lock_yield to reduce contention |
---|
[b227f68] | 72 | lock_yield( &this->lock DEBUG_CTX2 ); |
---|
[1c273d0] | 73 | thread_desc * thrd = this_thread; |
---|
[f07e037] | 74 | |
---|
[90c4df0] | 75 | LIB_DEBUG_PRINT_SAFE("Kernel : %10p Entering mon %p (%p)\n", thrd, this, this->owner); |
---|
| 76 | |
---|
[97e3296] | 77 | this->accepted_index = -1; |
---|
[cb0e6de] | 78 | if( !this->owner ) { |
---|
[97e3296] | 79 | // No one has the monitor, just take it |
---|
[cd348e7] | 80 | set_owner( this, thrd ); |
---|
[90c4df0] | 81 | |
---|
| 82 | LIB_DEBUG_PRINT_SAFE("Kernel : mon is free \n"); |
---|
[cb0e6de] | 83 | } |
---|
| 84 | else if( this->owner == thrd) { |
---|
[97e3296] | 85 | // We already have the monitor, just not how many times we took it |
---|
[4aa2fb2] | 86 | verify( this->recursion > 0 ); |
---|
[cb0e6de] | 87 | this->recursion += 1; |
---|
[90c4df0] | 88 | |
---|
| 89 | LIB_DEBUG_PRINT_SAFE("Kernel : mon already owned \n"); |
---|
[cb0e6de] | 90 | } |
---|
[97e3296] | 91 | else if( (this->accepted_index = is_accepted( thrd, this, group, group_cnt, func)) >= 0 ) { |
---|
| 92 | // Some one was waiting for us, enter |
---|
| 93 | set_owner( this, thrd ); |
---|
[90c4df0] | 94 | |
---|
| 95 | LIB_DEBUG_PRINT_SAFE("Kernel : mon accepts \n"); |
---|
[97e3296] | 96 | } |
---|
[cb0e6de] | 97 | else { |
---|
[90c4df0] | 98 | LIB_DEBUG_PRINT_SAFE("Kernel : blocking \n"); |
---|
| 99 | |
---|
[97e3296] | 100 | // Some one else has the monitor, wait in line for it |
---|
[cb0e6de] | 101 | append( &this->entry_queue, thrd ); |
---|
[82ff5845] | 102 | BlockInternal( &this->lock ); |
---|
[cc7f4b1] | 103 | |
---|
[90c4df0] | 104 | LIB_DEBUG_PRINT_SAFE("Kernel : %10p Entered mon %p\n", thrd, this); |
---|
| 105 | |
---|
[97e3296] | 106 | // BlockInternal will unlock spinlock, no need to unlock ourselves |
---|
[2ac095d] | 107 | return; |
---|
[cb0e6de] | 108 | } |
---|
[f07e037] | 109 | |
---|
[90c4df0] | 110 | LIB_DEBUG_PRINT_SAFE("Kernel : %10p Entered mon %p\n", thrd, this); |
---|
| 111 | |
---|
[97e3296] | 112 | // Release the lock and leave |
---|
[cb0e6de] | 113 | unlock( &this->lock ); |
---|
[5ea06d6] | 114 | return; |
---|
[cb0e6de] | 115 | } |
---|
[f07e037] | 116 | |
---|
[97e3296] | 117 | // Leave single monitor |
---|
[1c273d0] | 118 | void __leave_monitor_desc( monitor_desc * this ) { |
---|
[97e3296] | 119 | // Lock the monitor spinlock, lock_yield to reduce contention |
---|
[b227f68] | 120 | lock_yield( &this->lock DEBUG_CTX2 ); |
---|
[f07e037] | 121 | |
---|
[1c273d0] | 122 | verifyf( this_thread == this->owner, "Expected owner to be %p, got %p (r: %i)", this_thread, this->owner, this->recursion ); |
---|
[cc7f4b1] | 123 | |
---|
[97e3296] | 124 | // Leaving a recursion level, decrement the counter |
---|
[cb0e6de] | 125 | this->recursion -= 1; |
---|
[f07e037] | 126 | |
---|
[97e3296] | 127 | // If we haven't left the last level of recursion |
---|
| 128 | // it means we don't need to do anything |
---|
[690f13c] | 129 | if( this->recursion != 0) { |
---|
| 130 | unlock( &this->lock ); |
---|
| 131 | return; |
---|
| 132 | } |
---|
[f07e037] | 133 | |
---|
[97e3296] | 134 | // Get the next thread, will be null on low contention monitor |
---|
[0c78741] | 135 | thread_desc * new_owner = next_thread( this ); |
---|
[5ea06d6] | 136 | |
---|
[97e3296] | 137 | // We can now let other threads in safely |
---|
[cb0e6de] | 138 | unlock( &this->lock ); |
---|
[51f3798] | 139 | |
---|
[690f13c] | 140 | //We need to wake-up the thread |
---|
[1c273d0] | 141 | WakeThread( new_owner ); |
---|
| 142 | } |
---|
| 143 | |
---|
[97e3296] | 144 | // Leave the thread monitor |
---|
| 145 | // last routine called by a thread. |
---|
| 146 | // Should never return |
---|
[1c273d0] | 147 | void __leave_thread_monitor( thread_desc * thrd ) { |
---|
| 148 | monitor_desc * this = &thrd->mon; |
---|
[97e3296] | 149 | |
---|
| 150 | // Lock the monitor now |
---|
[b227f68] | 151 | lock_yield( &this->lock DEBUG_CTX2 ); |
---|
[1c273d0] | 152 | |
---|
| 153 | disable_interrupts(); |
---|
| 154 | |
---|
| 155 | thrd->cor.state = Halted; |
---|
| 156 | |
---|
| 157 | verifyf( thrd == this->owner, "Expected owner to be %p, got %p (r: %i)", thrd, this->owner, this->recursion ); |
---|
| 158 | |
---|
[97e3296] | 159 | // Leaving a recursion level, decrement the counter |
---|
[1c273d0] | 160 | this->recursion -= 1; |
---|
| 161 | |
---|
[97e3296] | 162 | // If we haven't left the last level of recursion |
---|
| 163 | // it must mean there is an error |
---|
| 164 | if( this->recursion != 0) { abortf("Thread internal monitor has unbalanced recursion"); } |
---|
[1c273d0] | 165 | |
---|
[97e3296] | 166 | // Fetch the next thread, can be null |
---|
[1c273d0] | 167 | thread_desc * new_owner = next_thread( this ); |
---|
| 168 | |
---|
[97e3296] | 169 | // Leave the thread, this will unlock the spinlock |
---|
| 170 | // Use leave thread instead of BlockInternal which is |
---|
| 171 | // specialized for this case and supports null new_owner |
---|
[f2b12406] | 172 | LeaveThread( &this->lock, new_owner ); |
---|
[97e3296] | 173 | |
---|
| 174 | // Control flow should never reach here! |
---|
[cc7f4b1] | 175 | } |
---|
[2781e65] | 176 | } |
---|
| 177 | |
---|
[97e3296] | 178 | // Enter multiple monitor |
---|
| 179 | // relies on the monitor array being sorted |
---|
| 180 | static inline void enter(monitor_desc ** monitors, int count, void (*func)() ) { |
---|
[0c78741] | 181 | for(int i = 0; i < count; i++) { |
---|
[97e3296] | 182 | __enter_monitor_desc( monitors[i], monitors, count, func ); |
---|
| 183 | } |
---|
[2781e65] | 184 | } |
---|
| 185 | |
---|
[97e3296] | 186 | // Leave multiple monitor |
---|
| 187 | // relies on the monitor array being sorted |
---|
[5ea06d6] | 188 | static inline void leave(monitor_desc ** monitors, int count) { |
---|
[0c78741] | 189 | for(int i = count - 1; i >= 0; i--) { |
---|
| 190 | __leave_monitor_desc( monitors[i] ); |
---|
[2781e65] | 191 | } |
---|
[5ea06d6] | 192 | } |
---|
| 193 | |
---|
[97e3296] | 194 | // Ctor for monitor guard |
---|
| 195 | // Sorts monitors before entering |
---|
[6b224a52] | 196 | void ?{}( monitor_guard_t & this, monitor_desc ** m, int count, void (*func)() ) { |
---|
[97e3296] | 197 | // Store current array |
---|
[242a902] | 198 | this.m = m; |
---|
| 199 | this.count = count; |
---|
[97e3296] | 200 | |
---|
| 201 | // Sort monitors based on address -> TODO use a sort specialized for small numbers |
---|
[242a902] | 202 | qsort(this.m, count); |
---|
[5ea06d6] | 203 | |
---|
[97e3296] | 204 | // Save previous thread context |
---|
[242a902] | 205 | this.prev_mntrs = this_thread->current_monitors; |
---|
| 206 | this.prev_count = this_thread->current_monitor_count; |
---|
[6b224a52] | 207 | this.prev_func = this_thread->current_monitor_func; |
---|
[5ea06d6] | 208 | |
---|
[97e3296] | 209 | // Update thread context (needed for conditions) |
---|
[1c273d0] | 210 | this_thread->current_monitors = m; |
---|
| 211 | this_thread->current_monitor_count = count; |
---|
[90c4df0] | 212 | this_thread->current_monitor_func = func; |
---|
| 213 | |
---|
| 214 | // Enter the monitors in order |
---|
[6b224a52] | 215 | enter( this.m, this.count, func ); |
---|
[5ea06d6] | 216 | } |
---|
| 217 | |
---|
[6b224a52] | 218 | |
---|
[97e3296] | 219 | // Dtor for monitor guard |
---|
[242a902] | 220 | void ^?{}( monitor_guard_t & this ) { |
---|
[97e3296] | 221 | // Leave the monitors in order |
---|
[242a902] | 222 | leave( this.m, this.count ); |
---|
[5ea06d6] | 223 | |
---|
[97e3296] | 224 | // Restore thread context |
---|
[242a902] | 225 | this_thread->current_monitors = this.prev_mntrs; |
---|
| 226 | this_thread->current_monitor_count = this.prev_count; |
---|
[6b224a52] | 227 | this_thread->current_monitor_func = this.prev_func; |
---|
[5ea06d6] | 228 | } |
---|
| 229 | |
---|
[97e3296] | 230 | //----------------------------------------------------------------------------- |
---|
| 231 | // Internal scheduling types |
---|
[242a902] | 232 | void ?{}(__condition_node_t & this, thread_desc * waiting_thread, unsigned short count, uintptr_t user_info ) { |
---|
| 233 | this.waiting_thread = waiting_thread; |
---|
| 234 | this.count = count; |
---|
| 235 | this.next = NULL; |
---|
| 236 | this.user_info = user_info; |
---|
[be3d020] | 237 | } |
---|
| 238 | |
---|
[242a902] | 239 | void ?{}(__condition_criterion_t & this ) { |
---|
| 240 | this.ready = false; |
---|
| 241 | this.target = NULL; |
---|
| 242 | this.owner = NULL; |
---|
| 243 | this.next = NULL; |
---|
[be3d020] | 244 | } |
---|
| 245 | |
---|
[242a902] | 246 | void ?{}(__condition_criterion_t & this, monitor_desc * target, __condition_node_t * owner ) { |
---|
| 247 | this.ready = false; |
---|
| 248 | this.target = target; |
---|
| 249 | this.owner = owner; |
---|
| 250 | this.next = NULL; |
---|
[ad1a8dd] | 251 | } |
---|
| 252 | |
---|
[5ea06d6] | 253 | //----------------------------------------------------------------------------- |
---|
| 254 | // Internal scheduling |
---|
[be3d020] | 255 | void wait( condition * this, uintptr_t user_info = 0 ) { |
---|
[0c78741] | 256 | brand_condition( this ); |
---|
[5ea06d6] | 257 | |
---|
[97e3296] | 258 | // Check that everything is as expected |
---|
[0c78741] | 259 | assertf( this->monitors != NULL, "Waiting with no monitors (%p)", this->monitors ); |
---|
[4aa2fb2] | 260 | verifyf( this->monitor_count != 0, "Waiting with 0 monitors (%i)", this->monitor_count ); |
---|
| 261 | verifyf( this->monitor_count < 32u, "Excessive monitor count (%i)", this->monitor_count ); |
---|
[5ea06d6] | 262 | |
---|
[97e3296] | 263 | // Create storage for monitor context |
---|
| 264 | monitor_ctx( this->monitors, this->monitor_count ); |
---|
[0c78741] | 265 | |
---|
[97e3296] | 266 | // Create the node specific to this wait operation |
---|
| 267 | wait_ctx( this_thread, user_info ); |
---|
[0c78741] | 268 | |
---|
[97e3296] | 269 | // Append the current wait operation to the ones already queued on the condition |
---|
| 270 | // We don't need locks for that since conditions must always be waited on inside monitor mutual exclusion |
---|
| 271 | append( &this->blocked, &waiter ); |
---|
[0c78741] | 272 | |
---|
[97e3296] | 273 | // Lock all monitors (aggregates the lock them as well) |
---|
| 274 | lock_all( monitors, locks, count ); |
---|
[5ea06d6] | 275 | |
---|
[97e3296] | 276 | // DON'T unlock, ask the kernel to do it |
---|
[5ea06d6] | 277 | |
---|
[97e3296] | 278 | // Save monitor state |
---|
| 279 | save_recursion( monitors, recursions, count ); |
---|
[5ea06d6] | 280 | |
---|
[97e3296] | 281 | // Find the next thread(s) to run |
---|
[ad1a8dd] | 282 | unsigned short thread_count = 0; |
---|
[0c78741] | 283 | thread_desc * threads[ count ]; |
---|
[ad1a8dd] | 284 | for(int i = 0; i < count; i++) { |
---|
| 285 | threads[i] = 0; |
---|
| 286 | } |
---|
| 287 | |
---|
[97e3296] | 288 | // Remove any duplicate threads |
---|
[0c78741] | 289 | for( int i = 0; i < count; i++) { |
---|
[97e3296] | 290 | thread_desc * new_owner = next_thread( monitors[i] ); |
---|
[ad1a8dd] | 291 | thread_count = insert_unique( threads, thread_count, new_owner ); |
---|
[5ea06d6] | 292 | } |
---|
| 293 | |
---|
[9c59cd4] | 294 | // Everything is ready to go to sleep |
---|
[82ff5845] | 295 | BlockInternal( locks, count, threads, thread_count ); |
---|
[5ea06d6] | 296 | |
---|
[c81ebf9] | 297 | |
---|
[97e3296] | 298 | // WE WOKE UP |
---|
[5ea06d6] | 299 | |
---|
| 300 | |
---|
[97e3296] | 301 | // We are back, restore the owners and recursions |
---|
[9c59cd4] | 302 | lock_all( locks, count ); |
---|
[97e3296] | 303 | restore_recursion( monitors, recursions, count ); |
---|
[9c59cd4] | 304 | unlock_all( locks, count ); |
---|
[5ea06d6] | 305 | } |
---|
| 306 | |
---|
[be3d020] | 307 | bool signal( condition * this ) { |
---|
[97e3296] | 308 | if( is_empty( this ) ) { return false; } |
---|
[5ea06d6] | 309 | |
---|
| 310 | //Check that everything is as expected |
---|
[4aa2fb2] | 311 | verify( this->monitors ); |
---|
| 312 | verify( this->monitor_count != 0 ); |
---|
[0c78741] | 313 | |
---|
[44264c5] | 314 | //Some more checking in debug |
---|
[5ea06d6] | 315 | LIB_DEBUG_DO( |
---|
[1c273d0] | 316 | thread_desc * this_thrd = this_thread; |
---|
[0c78741] | 317 | if ( this->monitor_count != this_thrd->current_monitor_count ) { |
---|
| 318 | abortf( "Signal on condition %p made with different number of monitor(s), expected %i got %i", this, this->monitor_count, this_thrd->current_monitor_count ); |
---|
[97e3296] | 319 | } |
---|
[0c78741] | 320 | |
---|
| 321 | for(int i = 0; i < this->monitor_count; i++) { |
---|
| 322 | if ( this->monitors[i] != this_thrd->current_monitors[i] ) { |
---|
| 323 | abortf( "Signal on condition %p made with different monitor, expected %p got %i", this, this->monitors[i], this_thrd->current_monitors[i] ); |
---|
[97e3296] | 324 | } |
---|
[0c78741] | 325 | } |
---|
[5ea06d6] | 326 | ); |
---|
| 327 | |
---|
[97e3296] | 328 | unsigned short count = this->monitor_count; |
---|
| 329 | |
---|
| 330 | // Lock all monitors |
---|
[0c78741] | 331 | lock_all( this->monitors, NULL, count ); |
---|
| 332 | |
---|
[44264c5] | 333 | //Pop the head of the waiting queue |
---|
[0c78741] | 334 | __condition_node_t * node = pop_head( &this->blocked ); |
---|
[44264c5] | 335 | |
---|
| 336 | //Add the thread to the proper AS stack |
---|
[0c78741] | 337 | for(int i = 0; i < count; i++) { |
---|
| 338 | __condition_criterion_t * crit = &node->criteria[i]; |
---|
| 339 | assert( !crit->ready ); |
---|
| 340 | push( &crit->target->signal_stack, crit ); |
---|
[5ea06d6] | 341 | } |
---|
[0c78741] | 342 | |
---|
[44264c5] | 343 | //Release |
---|
[0c78741] | 344 | unlock_all( this->monitors, count ); |
---|
[be3d020] | 345 | |
---|
| 346 | return true; |
---|
[5ea06d6] | 347 | } |
---|
| 348 | |
---|
[be3d020] | 349 | bool signal_block( condition * this ) { |
---|
[97e3296] | 350 | if( !this->blocked.head ) { return false; } |
---|
[44264c5] | 351 | |
---|
| 352 | //Check that everything is as expected |
---|
[4aa2fb2] | 353 | verifyf( this->monitors != NULL, "Waiting with no monitors (%p)", this->monitors ); |
---|
| 354 | verifyf( this->monitor_count != 0, "Waiting with 0 monitors (%i)", this->monitor_count ); |
---|
[44264c5] | 355 | |
---|
[97e3296] | 356 | // Create storage for monitor context |
---|
| 357 | monitor_ctx( this->monitors, this->monitor_count ); |
---|
[44264c5] | 358 | |
---|
[97e3296] | 359 | // Lock all monitors (aggregates the locks them as well) |
---|
| 360 | lock_all( monitors, locks, count ); |
---|
[44264c5] | 361 | |
---|
[97e3296] | 362 | // Create the node specific to this wait operation |
---|
| 363 | wait_ctx_primed( this_thread, 0 ) |
---|
[44264c5] | 364 | |
---|
| 365 | //save contexts |
---|
[97e3296] | 366 | save_recursion( monitors, recursions, count ); |
---|
[44264c5] | 367 | |
---|
| 368 | //Find the thread to run |
---|
| 369 | thread_desc * signallee = pop_head( &this->blocked )->waiting_thread; |
---|
| 370 | for(int i = 0; i < count; i++) { |
---|
[97e3296] | 371 | set_owner( monitors[i], signallee ); |
---|
[44264c5] | 372 | } |
---|
| 373 | |
---|
| 374 | //Everything is ready to go to sleep |
---|
[82ff5845] | 375 | BlockInternal( locks, count, &signallee, 1 ); |
---|
[44264c5] | 376 | |
---|
[c81ebf9] | 377 | |
---|
[97e3296] | 378 | // WE WOKE UP |
---|
[c81ebf9] | 379 | |
---|
| 380 | |
---|
[44264c5] | 381 | //We are back, restore the owners and recursions |
---|
| 382 | lock_all( locks, count ); |
---|
[97e3296] | 383 | restore_recursion( monitors, recursions, count ); |
---|
[44264c5] | 384 | unlock_all( locks, count ); |
---|
[be3d020] | 385 | |
---|
| 386 | return true; |
---|
| 387 | } |
---|
| 388 | |
---|
[97e3296] | 389 | // Access the user_info of the thread waiting at the front of the queue |
---|
[be3d020] | 390 | uintptr_t front( condition * this ) { |
---|
[2ac095d] | 391 | verifyf( !is_empty(this), |
---|
[4aa2fb2] | 392 | "Attempt to access user data on an empty condition.\n" |
---|
| 393 | "Possible cause is not checking if the condition is empty before reading stored data." |
---|
[be3d020] | 394 | ); |
---|
| 395 | return this->blocked.head->user_info; |
---|
[44264c5] | 396 | } |
---|
| 397 | |
---|
[c81ebf9] | 398 | //----------------------------------------------------------------------------- |
---|
| 399 | // Internal scheduling |
---|
[97e3296] | 400 | int __accept_internal( unsigned short acc_count, __acceptable_t * acceptables ) { |
---|
| 401 | thread_desc * thrd = this_thread; |
---|
| 402 | |
---|
| 403 | // Create storage for monitor context |
---|
| 404 | monitor_ctx( acceptables->monitors, acceptables->count ); |
---|
[c81ebf9] | 405 | |
---|
[97e3296] | 406 | // Lock all monitors (aggregates the lock them as well) |
---|
| 407 | lock_all( monitors, locks, count ); |
---|
[c81ebf9] | 408 | |
---|
[97e3296] | 409 | // Create the node specific to this wait operation |
---|
| 410 | wait_ctx_primed( thrd, 0 ); |
---|
[c81ebf9] | 411 | |
---|
[97e3296] | 412 | // Check if the entry queue |
---|
| 413 | thread_desc * next = search_entry_queue( acceptables, acc_count, monitors, count ); |
---|
[c81ebf9] | 414 | |
---|
[90c4df0] | 415 | LIB_DEBUG_PRINT_SAFE("Owner(s) :"); |
---|
| 416 | for(int i = 0; i < count; i++) { |
---|
| 417 | LIB_DEBUG_PRINT_SAFE(" %p", monitors[i]->owner ); |
---|
| 418 | } |
---|
| 419 | LIB_DEBUG_PRINT_SAFE("\n"); |
---|
| 420 | |
---|
| 421 | LIB_DEBUG_PRINT_SAFE("Passing mon to %p\n", next); |
---|
| 422 | |
---|
[97e3296] | 423 | if( !next ) { |
---|
| 424 | // Update acceptables on the current monitors |
---|
| 425 | for(int i = 0; i < count; i++) { |
---|
| 426 | monitors[i]->acceptables = acceptables; |
---|
| 427 | monitors[i]->acceptable_count = acc_count; |
---|
| 428 | } |
---|
| 429 | } |
---|
[90c4df0] | 430 | else { |
---|
| 431 | for(int i = 0; i < count; i++) { |
---|
| 432 | set_owner( monitors[i], next ); |
---|
| 433 | } |
---|
| 434 | } |
---|
| 435 | |
---|
[c81ebf9] | 436 | |
---|
[97e3296] | 437 | save_recursion( monitors, recursions, count ); |
---|
[c81ebf9] | 438 | |
---|
[90c4df0] | 439 | |
---|
[97e3296] | 440 | // Everything is ready to go to sleep |
---|
| 441 | BlockInternal( locks, count, &next, next ? 1 : 0 ); |
---|
[c81ebf9] | 442 | |
---|
| 443 | |
---|
[97e3296] | 444 | //WE WOKE UP |
---|
[c81ebf9] | 445 | |
---|
| 446 | |
---|
[97e3296] | 447 | //We are back, restore the owners and recursions |
---|
| 448 | lock_all( locks, count ); |
---|
| 449 | restore_recursion( monitors, recursions, count ); |
---|
| 450 | int acc_idx = monitors[0]->accepted_index; |
---|
| 451 | unlock_all( locks, count ); |
---|
[c81ebf9] | 452 | |
---|
[97e3296] | 453 | return acc_idx; |
---|
[c81ebf9] | 454 | } |
---|
| 455 | |
---|
[0c78741] | 456 | //----------------------------------------------------------------------------- |
---|
| 457 | // Utilities |
---|
| 458 | |
---|
| 459 | static inline void set_owner( monitor_desc * this, thread_desc * owner ) { |
---|
| 460 | //Pass the monitor appropriately |
---|
| 461 | this->owner = owner; |
---|
| 462 | |
---|
| 463 | //We are passing the monitor to someone else, which means recursion level is not 0 |
---|
| 464 | this->recursion = owner ? 1 : 0; |
---|
| 465 | } |
---|
| 466 | |
---|
| 467 | static inline thread_desc * next_thread( monitor_desc * this ) { |
---|
| 468 | //Check the signaller stack |
---|
| 469 | __condition_criterion_t * urgent = pop( &this->signal_stack ); |
---|
| 470 | if( urgent ) { |
---|
| 471 | //The signaller stack is not empty, |
---|
| 472 | //regardless of if we are ready to baton pass, |
---|
| 473 | //we need to set the monitor as in use |
---|
| 474 | set_owner( this, urgent->owner->waiting_thread ); |
---|
| 475 | |
---|
| 476 | return check_condition( urgent ); |
---|
| 477 | } |
---|
| 478 | |
---|
| 479 | // No signaller thread |
---|
| 480 | // Get the next thread in the entry_queue |
---|
| 481 | thread_desc * new_owner = pop_head( &this->entry_queue ); |
---|
| 482 | set_owner( this, new_owner ); |
---|
| 483 | |
---|
| 484 | return new_owner; |
---|
| 485 | } |
---|
| 486 | |
---|
[97e3296] | 487 | static inline int is_accepted( thread_desc * owner, monitor_desc * this, monitor_desc ** group, int group_cnt, void (*func)() ) { |
---|
| 488 | __acceptable_t* accs = this->acceptables; // Optim |
---|
| 489 | int acc_cnt = this->acceptable_count; |
---|
| 490 | |
---|
| 491 | // Check if there are any acceptable functions |
---|
| 492 | if( !accs ) return -1; |
---|
| 493 | |
---|
| 494 | // If this isn't the first monitor to test this, there is no reason to repeat the test. |
---|
| 495 | if( this != group[0] ) return group[0]->accepted_index; |
---|
| 496 | |
---|
| 497 | // For all acceptable functions check if this is the current function. |
---|
| 498 | OUT_LOOP: |
---|
| 499 | for( int i = 0; i < acc_cnt; i++ ) { |
---|
| 500 | __acceptable_t * acc = &accs[i]; |
---|
| 501 | |
---|
| 502 | // if function matches, check the monitors |
---|
| 503 | if( acc->func == func ) { |
---|
| 504 | |
---|
| 505 | // If the group count is different then it can't be a match |
---|
| 506 | if( acc->count != group_cnt ) return -1; |
---|
| 507 | |
---|
| 508 | // Check that all the monitors match |
---|
| 509 | for( int j = 0; j < group_cnt; j++ ) { |
---|
| 510 | // If not a match, check next function |
---|
| 511 | if( acc->monitors[j] != group[j] ) continue OUT_LOOP; |
---|
| 512 | } |
---|
| 513 | |
---|
| 514 | // It's a complete match, accept the call |
---|
| 515 | return i; |
---|
| 516 | } |
---|
| 517 | } |
---|
| 518 | |
---|
| 519 | // No function matched |
---|
| 520 | return -1; |
---|
| 521 | } |
---|
| 522 | |
---|
| 523 | static inline void init( int count, monitor_desc ** monitors, __condition_node_t * waiter, __condition_criterion_t * criteria ) { |
---|
| 524 | for(int i = 0; i < count; i++) { |
---|
[6b224a52] | 525 | (criteria[i]){ monitors[i], waiter }; |
---|
[97e3296] | 526 | } |
---|
| 527 | |
---|
| 528 | waiter->criteria = criteria; |
---|
| 529 | } |
---|
| 530 | |
---|
| 531 | static inline void init_push( int count, monitor_desc ** monitors, __condition_node_t * waiter, __condition_criterion_t * criteria ) { |
---|
| 532 | for(int i = 0; i < count; i++) { |
---|
[6b224a52] | 533 | (criteria[i]){ monitors[i], waiter }; |
---|
[97e3296] | 534 | push( &criteria[i].target->signal_stack, &criteria[i] ); |
---|
| 535 | } |
---|
| 536 | |
---|
| 537 | waiter->criteria = criteria; |
---|
| 538 | } |
---|
| 539 | |
---|
[0c78741] | 540 | static inline void lock_all( spinlock ** locks, unsigned short count ) { |
---|
| 541 | for( int i = 0; i < count; i++ ) { |
---|
[b227f68] | 542 | lock_yield( locks[i] DEBUG_CTX2 ); |
---|
[0c78741] | 543 | } |
---|
| 544 | } |
---|
| 545 | |
---|
| 546 | static inline void lock_all( monitor_desc ** source, spinlock ** /*out*/ locks, unsigned short count ) { |
---|
| 547 | for( int i = 0; i < count; i++ ) { |
---|
| 548 | spinlock * l = &source[i]->lock; |
---|
[b227f68] | 549 | lock_yield( l DEBUG_CTX2 ); |
---|
[0c78741] | 550 | if(locks) locks[i] = l; |
---|
| 551 | } |
---|
| 552 | } |
---|
| 553 | |
---|
| 554 | static inline void unlock_all( spinlock ** locks, unsigned short count ) { |
---|
| 555 | for( int i = 0; i < count; i++ ) { |
---|
| 556 | unlock( locks[i] ); |
---|
| 557 | } |
---|
| 558 | } |
---|
| 559 | |
---|
| 560 | static inline void unlock_all( monitor_desc ** locks, unsigned short count ) { |
---|
| 561 | for( int i = 0; i < count; i++ ) { |
---|
| 562 | unlock( &locks[i]->lock ); |
---|
| 563 | } |
---|
| 564 | } |
---|
| 565 | |
---|
| 566 | |
---|
| 567 | static inline void save_recursion ( monitor_desc ** ctx, unsigned int * /*out*/ recursions, unsigned short count ) { |
---|
| 568 | for( int i = 0; i < count; i++ ) { |
---|
| 569 | recursions[i] = ctx[i]->recursion; |
---|
| 570 | } |
---|
| 571 | } |
---|
| 572 | |
---|
| 573 | static inline void restore_recursion( monitor_desc ** ctx, unsigned int * /*in */ recursions, unsigned short count ) { |
---|
| 574 | for( int i = 0; i < count; i++ ) { |
---|
| 575 | ctx[i]->recursion = recursions[i]; |
---|
| 576 | } |
---|
| 577 | } |
---|
| 578 | |
---|
| 579 | // Function has 2 different behavior |
---|
| 580 | // 1 - Marks a monitors as being ready to run |
---|
| 581 | // 2 - Checks if all the monitors are ready to run |
---|
| 582 | // if so return the thread to run |
---|
| 583 | static inline thread_desc * check_condition( __condition_criterion_t * target ) { |
---|
| 584 | __condition_node_t * node = target->owner; |
---|
| 585 | unsigned short count = node->count; |
---|
| 586 | __condition_criterion_t * criteria = node->criteria; |
---|
| 587 | |
---|
| 588 | bool ready2run = true; |
---|
| 589 | |
---|
| 590 | for( int i = 0; i < count; i++ ) { |
---|
[44264c5] | 591 | |
---|
[b227f68] | 592 | // LIB_DEBUG_PRINT_SAFE( "Checking %p for %p\n", &criteria[i], target ); |
---|
[0c78741] | 593 | if( &criteria[i] == target ) { |
---|
| 594 | criteria[i].ready = true; |
---|
[b227f68] | 595 | // LIB_DEBUG_PRINT_SAFE( "True\n" ); |
---|
[0c78741] | 596 | } |
---|
| 597 | |
---|
| 598 | ready2run = criteria[i].ready && ready2run; |
---|
| 599 | } |
---|
| 600 | |
---|
[b227f68] | 601 | // LIB_DEBUG_PRINT_SAFE( "Runing %i\n", ready2run ); |
---|
[0c78741] | 602 | return ready2run ? node->waiting_thread : NULL; |
---|
| 603 | } |
---|
| 604 | |
---|
| 605 | static inline void brand_condition( condition * this ) { |
---|
[1c273d0] | 606 | thread_desc * thrd = this_thread; |
---|
[0c78741] | 607 | if( !this->monitors ) { |
---|
[b227f68] | 608 | // LIB_DEBUG_PRINT_SAFE("Branding\n"); |
---|
[38ef0de] | 609 | assertf( thrd->current_monitors != NULL, "No current monitor to brand condition %p", thrd->current_monitors ); |
---|
[0c78741] | 610 | this->monitor_count = thrd->current_monitor_count; |
---|
[a933dcf4] | 611 | |
---|
| 612 | this->monitors = malloc( this->monitor_count * sizeof( *this->monitors ) ); |
---|
| 613 | for( int i = 0; i < this->monitor_count; i++ ) { |
---|
| 614 | this->monitors[i] = thrd->current_monitors[i]; |
---|
| 615 | } |
---|
[0c78741] | 616 | } |
---|
| 617 | } |
---|
| 618 | |
---|
| 619 | static inline unsigned short insert_unique( thread_desc ** thrds, unsigned short end, thread_desc * val ) { |
---|
[ad1a8dd] | 620 | if( !val ) return end; |
---|
| 621 | |
---|
| 622 | for(int i = 0; i <= end; i++) { |
---|
[0c78741] | 623 | if( thrds[i] == val ) return end; |
---|
| 624 | } |
---|
| 625 | |
---|
| 626 | thrds[end] = val; |
---|
| 627 | return end + 1; |
---|
| 628 | } |
---|
| 629 | |
---|
[6b224a52] | 630 | |
---|
[90c4df0] | 631 | static inline bool match( __acceptable_t * acc, thread_desc * thrd ) { |
---|
| 632 | verify( thrd ); |
---|
| 633 | verify( acc ); |
---|
| 634 | if( acc->func != thrd->current_monitor_func ) return false; |
---|
| 635 | |
---|
| 636 | return true; |
---|
| 637 | } |
---|
| 638 | |
---|
[97e3296] | 639 | static inline thread_desc * search_entry_queue( __acceptable_t * acceptables, int acc_count, monitor_desc ** monitors, int count ) { |
---|
[90c4df0] | 640 | |
---|
| 641 | __thread_queue_t * entry_queue = &monitors[0]->entry_queue; |
---|
| 642 | |
---|
| 643 | // For each thread in the entry-queue |
---|
| 644 | for( thread_desc ** thrd_it = &entry_queue->head; |
---|
| 645 | *thrd_it; |
---|
| 646 | thrd_it = &(*thrd_it)->next) |
---|
| 647 | { |
---|
| 648 | // For each acceptable check if it matches |
---|
| 649 | __acceptable_t * acc_end = acceptables + acc_count; |
---|
| 650 | for( __acceptable_t * acc_it = acceptables; acc_it != acc_end; acc_it++ ) { |
---|
| 651 | // Check if we have a match |
---|
| 652 | if( match( acc_it, *thrd_it ) ) { |
---|
| 653 | |
---|
| 654 | // If we have a match return it |
---|
| 655 | // after removeing it from the entry queue |
---|
| 656 | return remove( entry_queue, thrd_it ); |
---|
| 657 | } |
---|
| 658 | } |
---|
| 659 | } |
---|
| 660 | |
---|
[97e3296] | 661 | return NULL; |
---|
| 662 | } |
---|
[242a902] | 663 | void ?{}( __condition_blocked_queue_t & this ) { |
---|
| 664 | this.head = NULL; |
---|
| 665 | this.tail = &this.head; |
---|
[0c78741] | 666 | } |
---|
| 667 | |
---|
| 668 | void append( __condition_blocked_queue_t * this, __condition_node_t * c ) { |
---|
[4aa2fb2] | 669 | verify(this->tail != NULL); |
---|
[0c78741] | 670 | *this->tail = c; |
---|
| 671 | this->tail = &c->next; |
---|
| 672 | } |
---|
| 673 | |
---|
| 674 | __condition_node_t * pop_head( __condition_blocked_queue_t * this ) { |
---|
| 675 | __condition_node_t * head = this->head; |
---|
| 676 | if( head ) { |
---|
| 677 | this->head = head->next; |
---|
| 678 | if( !head->next ) { |
---|
| 679 | this->tail = &this->head; |
---|
| 680 | } |
---|
| 681 | head->next = NULL; |
---|
| 682 | } |
---|
| 683 | return head; |
---|
[4aa2fb2] | 684 | } |
---|
[6b0b624] | 685 | |
---|
| 686 | // Local Variables: // |
---|
| 687 | // mode: c // |
---|
| 688 | // tab-width: 4 // |
---|
| 689 | // End: // |
---|