- File:
-
- 1 edited
-
libcfa/src/concurrency/ready_queue.cfa (modified) (20 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/concurrency/ready_queue.cfa
r772411a rfd9b524 17 17 // #define __CFA_DEBUG_PRINT_READY_QUEUE__ 18 18 19 // #define USE_SNZI20 21 19 #include "bits/defs.hfa" 22 20 #include "kernel_private.hfa" … … 150 148 // queues or removing them. 151 149 uint_fast32_t ready_mutate_lock( void ) with(*__scheduler_lock) { 152 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );153 154 150 // Step 1 : lock global lock 155 151 // It is needed to avoid processors that register mid Critical-Section … … 166 162 } 167 163 168 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );169 164 return s; 170 165 } 171 166 172 167 void ready_mutate_unlock( uint_fast32_t last_s ) with(*__scheduler_lock) { 173 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );174 175 168 // Step 1 : release local locks 176 169 // This must be done while the global lock is held to avoid … … 187 180 /*paranoid*/ assert(true == lock); 188 181 __atomic_store_n(&lock, (bool)false, __ATOMIC_RELEASE); 189 190 /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );191 182 } 192 183 … … 201 192 void ^?{}(__ready_queue_t & this) with (this) { 202 193 verify( 1 == lanes.count ); 203 #ifdef USE_SNZI 204 verify( !query( snzi ) ); 205 #endif 194 verify( !query( snzi ) ); 206 195 free(lanes.data); 207 196 } … … 209 198 //----------------------------------------------------------------------- 210 199 __attribute__((hot)) bool query(struct cluster * cltr) { 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]; 200 return query(cltr->ready_queue.snzi); 240 201 } 241 202 … … 247 208 thrd->link.ts = rdtscl(); 248 209 249 __attribute__((unused)) bool local; 250 __attribute__((unused)) int preferred; 251 #if defined(BIAS) 252 preferred = 210 #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__) 211 bool local = false; 212 int preferred = 253 213 //* 254 214 kernelTLS.this_processor ? kernelTLS.this_processor->id * 4 : -1; … … 256 216 thrd->link.preferred * 4; 257 217 //*/ 218 219 258 220 #endif 259 221 … … 262 224 do { 263 225 // Pick the index of a lane 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 } 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(); 271 248 #endif 272 249 … … 285 262 bool lane_first = push(lanes.data[i], thrd); 286 263 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 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 } 297 272 298 273 // Unlock and return … … 319 294 __attribute__((hot)) $thread * pop(struct cluster * cltr) with (cltr->ready_queue) { 320 295 /* paranoid */ verify( lanes.count > 0 ); 321 unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );322 int preferred;323 296 #if defined(BIAS) 324 297 // Don't bother trying locally too much 325 298 int local_tries = 8; 326 preferred = kernelTLS.this_processor->id * 4;327 299 #endif 328 300 329 330 301 // As long as the list is not empty, try finding a lane that isn't empty and pop from it 331 #ifdef USE_SNZI 332 while( query(snzi) ) { 333 #else 334 for(25) { 335 #endif 302 while( query(snzi) ) { 336 303 // Pick two lists at random 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 } 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(); 352 336 #endif 353 337 354 i %= count;355 j %= count;338 i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); 339 j %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); 356 340 357 341 // try popping from the 2 picked lists … … 359 343 if(thrd) { 360 344 #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__) 361 if( local i || localj) __tls_stats()->ready.pick.pop.lsuccess++;345 if( local ) __tls_stats()->ready.pick.pop.lsuccess++; 362 346 #endif 363 347 return thrd; … … 368 352 return 0p; 369 353 } 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 0p384 return 0p;385 }386 387 354 388 355 //----------------------------------------------------------------------- … … 421 388 // Actually pop the list 422 389 struct $thread * thrd; 423 thrd = pop(lane); 390 bool emptied; 391 [thrd, emptied] = pop(lane); 424 392 425 393 /* paranoid */ verify(thrd); 426 394 /* paranoid */ verify(lane.lock); 427 395 428 #ifdef USE_SNZI 429 // If this was the last element in the lane 430 if(emptied) { 431 depart( snzi, w ); 432 } 433 #endif 396 // If this was the last element in the lane 397 if(emptied) { 398 depart( snzi, w ); 399 } 434 400 435 401 // Unlock and return … … 458 424 if(head(lane)->link.next == thrd) { 459 425 $thread * pthrd; 460 pthrd = pop(lane); 426 bool emptied; 427 [pthrd, emptied] = pop(lane); 461 428 462 429 /* paranoid */ verify( pthrd == thrd ); 463 430 464 431 removed = true; 465 #ifdef USE_SNZI 466 if(emptied) { 467 depart( snzi, i ); 468 } 469 #endif 432 if(emptied) { 433 depart( snzi, i ); 434 } 470 435 } 471 436 __atomic_unlock(&lane.lock); … … 529 494 // grow the ready queue 530 495 with( cltr->ready_queue ) { 531 #ifdef USE_SNZI 532 ^(snzi){}; 533 #endif 496 ^(snzi){}; 534 497 535 498 // Find new count … … 553 516 lanes.count = ncount; 554 517 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 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 } 564 525 } 565 526 … … 581 542 582 543 with( cltr->ready_queue ) { 583 #ifdef USE_SNZI 584 ^(snzi){}; 585 #endif 544 ^(snzi){}; 586 545 587 546 // Remember old count … … 608 567 while(!is_empty(lanes.data[idx])) { 609 568 struct $thread * thrd; 610 thrd = pop(lanes.data[idx]); 569 __attribute__((unused)) bool _; 570 [thrd, _] = pop(lanes.data[idx]); 611 571 612 572 push(cltr, thrd); … … 636 596 } 637 597 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 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 } 647 605 } 648 606
Note:
See TracChangeset
for help on using the changeset viewer.
