- File:
-
- 1 edited
-
libcfa/src/concurrency/ready_queue.cfa (modified) (20 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/concurrency/ready_queue.cfa
rfd9b524 r772411a 17 17 // #define __CFA_DEBUG_PRINT_READY_QUEUE__ 18 18 19 // #define USE_SNZI 20 19 21 #include "bits/defs.hfa" 20 22 #include "kernel_private.hfa" … … 148 150 // queues or removing them. 149 151 uint_fast32_t ready_mutate_lock( void ) with(*__scheduler_lock) { 152 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled ); 153 150 154 // Step 1 : lock global lock 151 155 // It is needed to avoid processors that register mid Critical-Section … … 162 166 } 163 167 168 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled ); 164 169 return s; 165 170 } 166 171 167 172 void ready_mutate_unlock( uint_fast32_t last_s ) with(*__scheduler_lock) { 173 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled ); 174 168 175 // Step 1 : release local locks 169 176 // This must be done while the global lock is held to avoid … … 180 187 /*paranoid*/ assert(true == lock); 181 188 __atomic_store_n(&lock, (bool)false, __ATOMIC_RELEASE); 189 190 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled ); 182 191 } 183 192 … … 192 201 void ^?{}(__ready_queue_t & this) with (this) { 193 202 verify( 1 == lanes.count ); 194 verify( !query( snzi ) ); 203 #ifdef USE_SNZI 204 verify( !query( snzi ) ); 205 #endif 195 206 free(lanes.data); 196 207 } … … 198 209 //----------------------------------------------------------------------- 199 210 __attribute__((hot)) bool query(struct cluster * cltr) { 200 return query(cltr->ready_queue.snzi); 211 #ifdef USE_SNZI 212 return query(cltr->ready_queue.snzi); 213 #endif 214 return true; 215 } 216 217 static inline [unsigned, bool] idx_from_r(unsigned r, unsigned preferred) { 218 unsigned i; 219 bool local; 220 #if defined(BIAS) 221 unsigned rlow = r % BIAS; 222 unsigned rhigh = r / BIAS; 223 if((0 != rlow) && preferred >= 0) { 224 // (BIAS - 1) out of BIAS chances 225 // Use perferred queues 226 i = preferred + (rhigh % 4); 227 local = true; 228 } 229 else { 230 // 1 out of BIAS chances 231 // Use all queues 232 i = rhigh; 233 local = false; 234 } 235 #else 236 i = r; 237 local = false; 238 #endif 239 return [i, local]; 201 240 } 202 241 … … 208 247 thrd->link.ts = rdtscl(); 209 248 210 #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__) 211 bool local = false; 212 int preferred = 249 __attribute__((unused)) bool local; 250 __attribute__((unused)) int preferred; 251 #if defined(BIAS) 252 preferred = 213 253 //* 214 254 kernelTLS.this_processor ? kernelTLS.this_processor->id * 4 : -1; … … 216 256 thrd->link.preferred * 4; 217 257 //*/ 218 219 220 258 #endif 221 259 … … 224 262 do { 225 263 // Pick the index of a lane 226 #if defined(BIAS) 227 unsigned r = __tls_rand(); 228 unsigned rlow = r % BIAS; 229 unsigned rhigh = r / BIAS; 230 if((0 != rlow) && preferred >= 0) { 231 // (BIAS - 1) out of BIAS chances 232 // Use perferred queues 233 i = preferred + (rhigh % 4); 234 235 #if !defined(__CFA_NO_STATISTICS__) 236 local = true; 237 __tls_stats()->ready.pick.push.local++; 238 #endif 239 } 240 else { 241 // 1 out of BIAS chances 242 // Use all queues 243 i = rhigh; 244 local = false; 245 } 246 #else 247 i = __tls_rand(); 264 unsigned r = __tls_rand(); 265 [i, local] = idx_from_r(r, preferred); 266 267 #if !defined(__CFA_NO_STATISTICS__) 268 if(local) { 269 __tls_stats()->ready.pick.push.local++; 270 } 248 271 #endif 249 272 … … 262 285 bool lane_first = push(lanes.data[i], thrd); 263 286 264 // If this lane used to be empty we need to do more 265 if(lane_first) { 266 // Check if the entire queue used to be empty 267 first = !query(snzi); 268 269 // Update the snzi 270 arrive( snzi, i ); 271 } 287 #ifdef USE_SNZI 288 // If this lane used to be empty we need to do more 289 if(lane_first) { 290 // Check if the entire queue used to be empty 291 first = !query(snzi); 292 293 // Update the snzi 294 arrive( snzi, i ); 295 } 296 #endif 272 297 273 298 // Unlock and return … … 294 319 __attribute__((hot)) $thread * pop(struct cluster * cltr) with (cltr->ready_queue) { 295 320 /* paranoid */ verify( lanes.count > 0 ); 321 unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); 322 int preferred; 296 323 #if defined(BIAS) 297 324 // Don't bother trying locally too much 298 325 int local_tries = 8; 299 #endif 326 preferred = kernelTLS.this_processor->id * 4; 327 #endif 328 300 329 301 330 // As long as the list is not empty, try finding a lane that isn't empty and pop from it 302 while( query(snzi) ) { 331 #ifdef USE_SNZI 332 while( query(snzi) ) { 333 #else 334 for(25) { 335 #endif 303 336 // Pick two lists at random 304 unsigned i,j; 305 #if defined(BIAS) 306 #if !defined(__CFA_NO_STATISTICS__) 307 bool local = false; 308 #endif 309 uint64_t r = __tls_rand(); 310 unsigned rlow = r % BIAS; 311 uint64_t rhigh = r / BIAS; 312 if(local_tries && 0 != rlow) { 313 // (BIAS - 1) out of BIAS chances 314 // Use perferred queues 315 unsigned pid = kernelTLS.this_processor->id * 4; 316 i = pid + (rhigh % 4); 317 j = pid + ((rhigh >> 32ull) % 4); 318 319 // count the tries 320 local_tries--; 321 322 #if !defined(__CFA_NO_STATISTICS__) 323 local = true; 324 __tls_stats()->ready.pick.pop.local++; 325 #endif 326 } 327 else { 328 // 1 out of BIAS chances 329 // Use all queues 330 i = rhigh; 331 j = rhigh >> 32ull; 332 } 333 #else 334 i = __tls_rand(); 335 j = __tls_rand(); 336 #endif 337 338 i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); 339 j %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); 337 unsigned ri = __tls_rand(); 338 unsigned rj = __tls_rand(); 339 340 unsigned i, j; 341 __attribute__((unused)) bool locali, localj; 342 [i, locali] = idx_from_r(ri, preferred); 343 [j, localj] = idx_from_r(rj, preferred); 344 345 #if !defined(__CFA_NO_STATISTICS__) 346 if(locali) { 347 __tls_stats()->ready.pick.pop.local++; 348 } 349 if(localj) { 350 __tls_stats()->ready.pick.pop.local++; 351 } 352 #endif 353 354 i %= count; 355 j %= count; 340 356 341 357 // try popping from the 2 picked lists … … 343 359 if(thrd) { 344 360 #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__) 345 if( local ) __tls_stats()->ready.pick.pop.lsuccess++;361 if( locali || localj ) __tls_stats()->ready.pick.pop.lsuccess++; 346 362 #endif 347 363 return thrd; … … 352 368 return 0p; 353 369 } 370 371 __attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr) with (cltr->ready_queue) { 372 /* paranoid */ verify( lanes.count > 0 ); 373 unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); 374 unsigned offset = __tls_rand(); 375 for(i; count) { 376 unsigned idx = (offset + i) % count; 377 struct $thread * thrd = try_pop(cltr, idx); 378 if(thrd) { 379 return thrd; 380 } 381 } 382 383 // All lanes where empty return 0p 384 return 0p; 385 } 386 354 387 355 388 //----------------------------------------------------------------------- … … 388 421 // Actually pop the list 389 422 struct $thread * thrd; 390 bool emptied; 391 [thrd, emptied] = pop(lane); 423 thrd = pop(lane); 392 424 393 425 /* paranoid */ verify(thrd); 394 426 /* paranoid */ verify(lane.lock); 395 427 396 // If this was the last element in the lane 397 if(emptied) { 398 depart( snzi, w ); 399 } 428 #ifdef USE_SNZI 429 // If this was the last element in the lane 430 if(emptied) { 431 depart( snzi, w ); 432 } 433 #endif 400 434 401 435 // Unlock and return … … 424 458 if(head(lane)->link.next == thrd) { 425 459 $thread * pthrd; 426 bool emptied; 427 [pthrd, emptied] = pop(lane); 460 pthrd = pop(lane); 428 461 429 462 /* paranoid */ verify( pthrd == thrd ); 430 463 431 464 removed = true; 432 if(emptied) { 433 depart( snzi, i ); 434 } 465 #ifdef USE_SNZI 466 if(emptied) { 467 depart( snzi, i ); 468 } 469 #endif 435 470 } 436 471 __atomic_unlock(&lane.lock); … … 494 529 // grow the ready queue 495 530 with( cltr->ready_queue ) { 496 ^(snzi){}; 531 #ifdef USE_SNZI 532 ^(snzi){}; 533 #endif 497 534 498 535 // Find new count … … 516 553 lanes.count = ncount; 517 554 518 // Re-create the snzi 519 snzi{ log2( lanes.count / 8 ) }; 520 for( idx; (size_t)lanes.count ) { 521 if( !is_empty(lanes.data[idx]) ) { 522 arrive(snzi, idx); 523 } 524 } 555 #ifdef USE_SNZI 556 // Re-create the snzi 557 snzi{ log2( lanes.count / 8 ) }; 558 for( idx; (size_t)lanes.count ) { 559 if( !is_empty(lanes.data[idx]) ) { 560 arrive(snzi, idx); 561 } 562 } 563 #endif 525 564 } 526 565 … … 542 581 543 582 with( cltr->ready_queue ) { 544 ^(snzi){}; 583 #ifdef USE_SNZI 584 ^(snzi){}; 585 #endif 545 586 546 587 // Remember old count … … 567 608 while(!is_empty(lanes.data[idx])) { 568 609 struct $thread * thrd; 569 __attribute__((unused)) bool _; 570 [thrd, _] = pop(lanes.data[idx]); 610 thrd = pop(lanes.data[idx]); 571 611 572 612 push(cltr, thrd); … … 596 636 } 597 637 598 // Re-create the snzi 599 snzi{ log2( lanes.count / 8 ) }; 600 for( idx; (size_t)lanes.count ) { 601 if( !is_empty(lanes.data[idx]) ) { 602 arrive(snzi, idx); 603 } 604 } 638 #ifdef USE_SNZI 639 // Re-create the snzi 640 snzi{ log2( lanes.count / 8 ) }; 641 for( idx; (size_t)lanes.count ) { 642 if( !is_empty(lanes.data[idx]) ) { 643 arrive(snzi, idx); 644 } 645 } 646 #endif 605 647 } 606 648
Note: See TracChangeset
for help on using the changeset viewer.
