Changeset 504a7dc for libcfa/src/concurrency/ready_queue.cfa
- Timestamp:
- May 12, 2020, 1:32:45 PM (4 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 4fa44e7
- Parents:
- 6a490b2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/concurrency/ready_queue.cfa
r6a490b2 r504a7dc 15 15 16 16 #define __cforall_thread__ 17 #define __CFA_DEBUG_PRINT_READY_QUEUE__ 17 18 18 19 #include "bits/defs.hfa" … … 34 35 const char * max_cores_s = getenv("CFA_MAX_PROCESSORS"); 35 36 if(!max_cores_s) { 36 __cfa abi_dbg_print_nolock("No CFA_MAX_PROCESSORS in ENV");37 __cfadbg_print_nolock(ready_queue, "No CFA_MAX_PROCESSORS in ENV\n"); 37 38 return __CFA_MAX_PROCESSORS__; 38 39 } … … 41 42 long int max_cores_l = strtol(max_cores_s, &endptr, 10); 42 43 if(max_cores_l < 1 || max_cores_l > 65535) { 43 __cfa abi_dbg_print_nolock("CFA_MAX_PROCESSORS out of range : %ld", max_cores_l);44 __cfadbg_print_nolock(ready_queue, "CFA_MAX_PROCESSORS out of range : %ld\n", max_cores_l); 44 45 return __CFA_MAX_PROCESSORS__; 45 46 } 46 47 if('\0' != *endptr) { 47 __cfa abi_dbg_print_nolock("CFA_MAX_PROCESSORS not a decimal number : %s", max_cores_s);48 __cfadbg_print_nolock(ready_queue, "CFA_MAX_PROCESSORS not a decimal number : %s\n", max_cores_s); 48 49 return __CFA_MAX_PROCESSORS__; 49 50 } … … 152 153 //======================================================================= 153 154 // Lock-Free registering/unregistering of threads 154 unsigned doregister( struct cluster * cltr, struct processor * proc ) with(cltr->ready_lock) { 155 unsigned doregister2( struct cluster * cltr, struct processor * proc ) with(cltr->ready_lock) { 156 __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p with cluster %p\n", proc, cltr); 157 155 158 // Step - 1 : check if there is already space in the data 156 159 uint_fast32_t s = ready; … … 185 188 } 186 189 190 __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p done, id %u\n", proc, n); 191 187 192 // Return new spot. 188 193 /*paranoid*/ verify(n < ready); … … 192 197 } 193 198 194 void unregister ( struct cluster * cltr, struct processor * proc ) with(cltr->ready_lock) {199 void unregister2( struct cluster * cltr, struct processor * proc ) with(cltr->ready_lock) { 195 200 unsigned id = proc->id; 196 201 /*paranoid*/ verify(id < ready); 197 202 /*paranoid*/ verify(proc == __atomic_load_n(&data[id].handle, __ATOMIC_RELAXED)); 198 203 __atomic_store_n(&data[id].handle, 0p, __ATOMIC_RELEASE); 204 205 __cfadbg_print_safe(ready_queue, "Kernel : Unregister proc %p\n", proc); 199 206 } 200 207 … … 241 248 //======================================================================= 242 249 // Get the head pointer (one before the first element) from the anchor 243 static inline thread_desc* head(const __intrusive_lane_t & this) {244 thread_desc * rhead = (thread_desc*)(245 (uintptr_t)( &this.before ) - offsetof( thread_desc, link )250 static inline $thread * head(const __intrusive_lane_t & this) { 251 $thread * rhead = ($thread *)( 252 (uintptr_t)( &this.before ) - offsetof( $thread, link ) 246 253 ); 247 254 /* paranoid */ verify(rhead); … … 250 257 251 258 // Get the tail pointer (one after the last element) from the anchor 252 static inline thread_desc* tail(const __intrusive_lane_t & this) {253 thread_desc * rtail = (thread_desc*)(254 (uintptr_t)( &this.after ) - offsetof( thread_desc, link )259 static inline $thread * tail(const __intrusive_lane_t & this) { 260 $thread * rtail = ($thread *)( 261 (uintptr_t)( &this.after ) - offsetof( $thread, link ) 255 262 ); 256 263 /* paranoid */ verify(rtail); … … 261 268 void ?{}( __intrusive_lane_t & this ) { 262 269 this.lock = false; 263 this.last_id = -1u; 264 this.count = 0u; 270 #if defined(__CFA_WITH_VERIFY__) 271 this.last_id = -1u; 272 this.count = 0u; 273 #endif 265 274 266 275 this.before.link.prev = 0p; … … 279 288 280 289 // We add a boat-load of assertions here because the anchor code is very fragile 281 /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( thread_desc, link )) == (uintptr_t)(&this.before));282 /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( thread_desc, link )) == (uintptr_t)(&this.after ));290 /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before)); 291 /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after )); 283 292 /* paranoid */ verify(head(this)->link.prev == 0p ); 284 293 /* paranoid */ verify(head(this)->link.next == tail(this) ); … … 311 320 // Push a thread onto this lane 312 321 // returns true of lane was empty before push, false otherwise 313 bool push(__intrusive_lane_t & this, thread_desc* node) {322 bool push(__intrusive_lane_t & this, $thread * node) { 314 323 #if defined(__CFA_WITH_VERIFY__) 315 324 /* paranoid */ verify(this.lock); … … 317 326 /* paranoid */ verify(node->link.next == 0p); 318 327 /* paranoid */ verify(node->link.prev == 0p); 328 /* paranoid */ verify(tail(this)->link.next == 0p); 329 /* paranoid */ verify(head(this)->link.prev == 0p); 319 330 320 331 this.count++; 321 332 322 333 if(this.before.link.ts == 0l) { 323 /* paranoid */ verify(tail(this)->link.next == 0p);324 334 /* paranoid */ verify(tail(this)->link.prev == head(this)); 325 335 /* paranoid */ verify(head(this)->link.next == tail(this)); 326 /* paranoid */ verify(head(this)->link.prev == 0p); 336 } else { 337 /* paranoid */ verify(tail(this)->link.prev != head(this)); 338 /* paranoid */ verify(head(this)->link.next != tail(this)); 327 339 } 328 340 #endif 329 341 330 342 // Get the relevant nodes locally 331 thread_desc* tail = tail(this);332 thread_desc* prev = tail->link.prev;343 $thread * tail = tail(this); 344 $thread * prev = tail->link.prev; 333 345 334 346 // Do the push … … 358 370 // returns popped 359 371 // returns true of lane was empty before push, false otherwise 360 [ thread_desc*, bool] pop(__intrusive_lane_t & this) {372 [$thread *, bool] pop(__intrusive_lane_t & this) { 361 373 /* paranoid */ verify(this.lock); 362 374 /* paranoid */ verify(this.before.link.ts != 0ul); 363 375 364 376 // Get anchors locally 365 thread_desc* head = head(this);366 thread_desc* tail = tail(this);377 $thread * head = head(this); 378 $thread * tail = tail(this); 367 379 368 380 // Get the relevant nodes locally 369 thread_desc* node = head->link.next;370 thread_desc* next = node->link.next;381 $thread * node = head->link.next; 382 $thread * next = node->link.next; 371 383 372 384 #if defined(__CFA_WITH_VERIFY__) … … 391 403 392 404 // Check if we emptied list and return accordingly 405 /* paranoid */ verify(tail(this)->link.next == 0p); 406 /* paranoid */ verify(head(this)->link.prev == 0p); 393 407 if(next == tail) { 394 408 /* paranoid */ verify(this.before.link.ts == 0); 395 /* paranoid */ verify(tail(this)->link.next == 0p);396 409 /* paranoid */ verify(tail(this)->link.prev == head(this)); 397 410 /* paranoid */ verify(head(this)->link.next == tail(this)); 398 /* paranoid */ verify(head(this)->link.prev == 0p);399 411 return [node, true]; 400 412 } 401 413 else { 402 414 /* paranoid */ verify(next->link.ts != 0); 415 /* paranoid */ verify(tail(this)->link.prev != head(this)); 416 /* paranoid */ verify(head(this)->link.next != tail(this)); 403 417 /* paranoid */ verify(this.before.link.ts != 0); 404 418 return [node, false]; … … 508 522 // Conditional check 509 523 verifyf( 510 strict == STRICT &&// Conditional check if it was expected to be cleared524 strict != STRICT || // Conditional check if it was expected to be cleared 511 525 ((mask[word] & (1ull << bit)) == 0), 512 526 "Before set %llu:%llu (%u), %llx & %llx", word, bit, index, mask[word], (1ull << bit) … … 518 532 // Conditional check 519 533 verifyf( 520 strict == STRICT &&// Conditional check if it was expected to be cleared534 strict != STRICT || // Conditional check if it was expected to be cleared 521 535 !ret, 522 536 "Bit was not set but bts returned true" … … 561 575 562 576 //----------------------------------------------------------------------- 563 __attribute__((hot)) bool push(struct cluster * cltr, struct thread_desc* thrd) with (cltr->ready_queue) {577 __attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) { 564 578 // write timestamp 565 579 thrd->link.ts = rdtscl(); … … 569 583 do { 570 584 // Pick the index of a lane 571 unsigned i =tls_rand() % lanes.count;585 i = __tls_rand() % lanes.count; 572 586 573 587 #if !defined(__CFA_NO_STATISTICS__) … … 594 608 size_t ret = __atomic_fetch_add( &used.count, 1z, __ATOMIC_SEQ_CST); 595 609 596 // Check if the entire qu ue used to be empty610 // Check if the entire queue used to be empty 597 611 first = (ret == 0); 598 612 … … 624 638 //----------------------------------------------------------------------- 625 639 // Given 2 indexes, pick the list with the oldest push an try to pop from it 626 static struct thread_desc* try_pop(struct cluster * cltr, unsigned i, unsigned j) with (cltr->ready_queue) {640 static struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j) with (cltr->ready_queue) { 627 641 #if !defined(__CFA_NO_STATISTICS__) 628 642 tls.pick.pop.attempt++; … … 662 676 663 677 // Actually pop the list 664 struct thread_desc* thrd;678 struct $thread * thrd; 665 679 bool emptied; 666 680 [thrd, emptied] = pop(lane); … … 704 718 705 719 // Pop from the ready queue from a given cluster 706 __attribute__((hot)) thread_desc* pop(struct cluster * cltr) with (cltr->ready_queue) {720 __attribute__((hot)) $thread * pop(struct cluster * cltr) with (cltr->ready_queue) { 707 721 /* paranoid */ verify( lanes.count > 0 ); 708 722 … … 716 730 717 731 // Pick two lists at random 718 unsigned ri = tls_rand();719 unsigned rj = tls_rand();732 unsigned ri = __tls_rand(); 733 unsigned rj = __tls_rand(); 720 734 721 735 // Find which __cfa_readyQ_mask_t the two lists belong … … 748 762 749 763 // try popping from the 2 picked lists 750 struct thread_desc* thrd = try_pop(cltr, i, j);764 struct $thread * thrd = try_pop(cltr, i, j); 751 765 if(thrd) return thrd; 752 766 #else 753 767 // Pick two lists at random 754 int i = tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );755 int j = tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );768 int i = __tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); 769 int j = __tls_rand() % __atomic_load_n( &lanes.count, __ATOMIC_RELAXED ); 756 770 757 771 // try popping from the 2 picked lists 758 struct thread_desc* thrd = try_pop(cltr, i, j);772 struct $thread * thrd = try_pop(cltr, i, j); 759 773 if(thrd) return thrd; 760 774 #endif … … 825 839 uint_fast32_t last_size = ready_mutate_lock( *cltr ); 826 840 827 __cfa abi_dbg_print_safe("Kernel : Growing ready queue\n");841 __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n"); 828 842 829 843 // Make sure that everything is consistent … … 862 876 /* paranoid */ check( cltr->ready_queue ); 863 877 864 __cfa abi_dbg_print_safe("Kernel : Growing ready queue done\n");878 __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue done\n"); 865 879 866 880 // Unlock the RWlock … … 873 887 uint_fast32_t last_size = ready_mutate_lock( *cltr ); 874 888 875 __cfa abi_dbg_print_safe("Kernel : Shrinking ready queue\n");889 __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n"); 876 890 877 891 // Make sure that everything is consistent … … 896 910 897 911 // for printing count the number of displaced threads 898 #if defined(__CFA_DEBUG_PRINT__) 912 #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__) 899 913 __attribute__((unused)) size_t displaced = 0; 900 914 #endif … … 908 922 // As long as we can pop from this lane to push the threads somewhere else in the queue 909 923 while(!is_empty(lanes.data[idx])) { 910 struct thread_desc* thrd;924 struct $thread * thrd; 911 925 __attribute__((unused)) bool _; 912 926 [thrd, _] = pop(lanes.data[idx]); … … 915 929 916 930 // for printing count the number of displaced threads 917 #if defined(__CFA_DEBUG_PRINT__) 931 #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__) 918 932 displaced++; 919 933 #endif … … 930 944 } 931 945 932 __cfa abi_dbg_print_safe("Kernel : Shrinking ready queue displaced %zu threads\n", displaced);946 __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue displaced %zu threads\n", displaced); 933 947 934 948 // recompute the used.count instead of maintaining it … … 958 972 /* paranoid */ check( cltr->ready_queue ); 959 973 960 __cfa abi_dbg_print_safe("Kernel : Shrinking ready queue done\n");974 __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue done\n"); 961 975 962 976 // Unlock the RWlock
Note: See TracChangeset
for help on using the changeset viewer.