[13c5e19] | 1 | #pragma once |
---|
| 2 | |
---|
| 3 | #define __CFA_NO_SCHED_STATS__ |
---|
| 4 | |
---|
[7a2972b9] | 5 | #include "containers/queueLockFree.hfa" |
---|
| 6 | |
---|
[f6fdfb14] | 7 | // Intrusives lanes which are used by the relaxed ready queue |
---|
| 8 | struct __attribute__((aligned(128))) __intrusive_lane_t { |
---|
| 9 | struct $thread * prev; |
---|
[2b96031] | 10 | |
---|
[f6fdfb14] | 11 | // spin lock protecting the queue |
---|
| 12 | volatile bool lock; |
---|
[13c5e19] | 13 | |
---|
[353aaba] | 14 | __thread_desc_link anchor; |
---|
| 15 | |
---|
[16fd826] | 16 | #if !defined(__CFA_NO_STATISTICS__) |
---|
| 17 | unsigned cnt; |
---|
| 18 | #endif |
---|
[f6fdfb14] | 19 | }; |
---|
[2b96031] | 20 | |
---|
[f6fdfb14] | 21 | // Get the head pointer (one before the first element) from the anchor |
---|
| 22 | static inline $thread * mock_head(const __intrusive_lane_t & this) { |
---|
| 23 | $thread * rhead = ($thread *)( |
---|
| 24 | (uintptr_t)( &this.anchor ) - __builtin_offsetof( $thread, link ) |
---|
| 25 | ); |
---|
| 26 | return rhead; |
---|
| 27 | } |
---|
| 28 | |
---|
| 29 | // Ctor |
---|
| 30 | void ?{}( __intrusive_lane_t & this ) { |
---|
| 31 | this.lock = false; |
---|
| 32 | this.prev = mock_head(this); |
---|
| 33 | this.anchor.next = 0p; |
---|
[ef94ae7] | 34 | this.anchor.ts = -1llu; |
---|
[16fd826] | 35 | #if !defined(__CFA_NO_STATISTICS__) |
---|
| 36 | this.cnt = 0; |
---|
| 37 | #endif |
---|
[f6fdfb14] | 38 | |
---|
| 39 | // We add a boat-load of assertions here because the anchor code is very fragile |
---|
[16fd826] | 40 | /* paranoid */ _Static_assert( offsetof( $thread, link ) == offsetof(__intrusive_lane_t, anchor) ); |
---|
[d3ba775] | 41 | /* paranoid */ verify( offsetof( $thread, link ) == offsetof(__intrusive_lane_t, anchor) ); |
---|
[f6fdfb14] | 42 | /* paranoid */ verify( ((uintptr_t)( mock_head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.anchor) ); |
---|
| 43 | /* paranoid */ verify( &mock_head(this)->link.next == &this.anchor.next ); |
---|
| 44 | /* paranoid */ verify( &mock_head(this)->link.ts == &this.anchor.ts ); |
---|
| 45 | /* paranoid */ verify( mock_head(this)->link.next == 0p ); |
---|
[ef94ae7] | 46 | /* paranoid */ verify( mock_head(this)->link.ts == -1llu ); |
---|
[f6fdfb14] | 47 | /* paranoid */ verify( mock_head(this) == this.prev ); |
---|
| 48 | /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 ); |
---|
| 49 | /* paranoid */ verify( __alignof__(this) == 128 ); |
---|
| 50 | /* paranoid */ verifyf( ((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128) ); |
---|
| 51 | } |
---|
| 52 | |
---|
| 53 | // Dtor is trivial |
---|
| 54 | void ^?{}( __intrusive_lane_t & this ) { |
---|
| 55 | // Make sure the list is empty |
---|
| 56 | /* paranoid */ verify( this.anchor.next == 0p ); |
---|
[ef94ae7] | 57 | /* paranoid */ verify( this.anchor.ts == -1llu ); |
---|
[f6fdfb14] | 58 | /* paranoid */ verify( mock_head(this) == this.prev ); |
---|
| 59 | } |
---|
| 60 | |
---|
| 61 | // Push a thread onto this lane |
---|
| 62 | // returns true of lane was empty before push, false otherwise |
---|
[f302d80] | 63 | static inline void push( __intrusive_lane_t & this, $thread * node ) { |
---|
[16fd826] | 64 | /* paranoid */ verify( this.lock ); |
---|
[f6fdfb14] | 65 | /* paranoid */ verify( node->link.next == 0p ); |
---|
[ef94ae7] | 66 | /* paranoid */ verify( node->link.ts == -1llu ); |
---|
[f6fdfb14] | 67 | /* paranoid */ verify( this.prev->link.next == 0p ); |
---|
[ef94ae7] | 68 | /* paranoid */ verify( this.prev->link.ts == -1llu ); |
---|
[f6fdfb14] | 69 | if( this.anchor.next == 0p ) { |
---|
[2b96031] | 70 | /* paranoid */ verify( this.anchor.next == 0p ); |
---|
[ef94ae7] | 71 | /* paranoid */ verify( this.anchor.ts == -1llu ); |
---|
| 72 | /* paranoid */ verify( this.anchor.ts != 0 ); |
---|
[f6fdfb14] | 73 | /* paranoid */ verify( this.prev == mock_head( this ) ); |
---|
| 74 | } else { |
---|
[2b96031] | 75 | /* paranoid */ verify( this.anchor.next != 0p ); |
---|
[ef94ae7] | 76 | /* paranoid */ verify( this.anchor.ts != -1llu ); |
---|
[2b96031] | 77 | /* paranoid */ verify( this.anchor.ts != 0 ); |
---|
[f6fdfb14] | 78 | /* paranoid */ verify( this.prev != mock_head( this ) ); |
---|
[2b96031] | 79 | } |
---|
| 80 | |
---|
[f6fdfb14] | 81 | // Get the relevant nodes locally |
---|
| 82 | this.prev->link.next = node; |
---|
| 83 | this.prev->link.ts = rdtscl(); |
---|
| 84 | this.prev = node; |
---|
[16fd826] | 85 | #if !defined(__CFA_NO_STATISTICS__) |
---|
| 86 | this.cnt++; |
---|
| 87 | #endif |
---|
[f6fdfb14] | 88 | } |
---|
| 89 | |
---|
| 90 | // Pop a thread from this lane (must be non-empty) |
---|
| 91 | // returns popped |
---|
| 92 | // returns true of lane was empty before push, false otherwise |
---|
[f302d80] | 93 | static inline [* $thread, unsigned long long] pop( __intrusive_lane_t & this ) { |
---|
[16fd826] | 94 | /* paranoid */ verify( this.lock ); |
---|
[f6fdfb14] | 95 | /* paranoid */ verify( this.anchor.next != 0p ); |
---|
[ef94ae7] | 96 | /* paranoid */ verify( this.anchor.ts != -1llu ); |
---|
[f6fdfb14] | 97 | /* paranoid */ verify( this.anchor.ts != 0 ); |
---|
| 98 | |
---|
| 99 | // Get the relevant nodes locally |
---|
[f302d80] | 100 | unsigned long long ts = this.anchor.ts; |
---|
[f6fdfb14] | 101 | $thread * node = this.anchor.next; |
---|
| 102 | this.anchor.next = node->link.next; |
---|
| 103 | this.anchor.ts = node->link.ts; |
---|
[ef94ae7] | 104 | bool is_empty = this.anchor.next == 0p; |
---|
[f6fdfb14] | 105 | node->link.next = 0p; |
---|
[ef94ae7] | 106 | node->link.ts = -1llu; |
---|
[16fd826] | 107 | #if !defined(__CFA_NO_STATISTICS__) |
---|
| 108 | this.cnt--; |
---|
| 109 | #endif |
---|
[f6fdfb14] | 110 | |
---|
| 111 | // Update head time stamp |
---|
| 112 | if(is_empty) this.prev = mock_head( this ); |
---|
| 113 | |
---|
| 114 | /* paranoid */ verify( node->link.next == 0p ); |
---|
[ef94ae7] | 115 | /* paranoid */ verify( node->link.ts == -1llu ); |
---|
| 116 | /* paranoid */ verify( node->link.ts != 0 ); |
---|
| 117 | /* paranoid */ verify( this.anchor.ts != 0 ); |
---|
[f302d80] | 118 | return [node, ts]; |
---|
[f6fdfb14] | 119 | } |
---|
| 120 | |
---|
| 121 | // Check whether or not list is empty |
---|
| 122 | static inline bool is_empty(__intrusive_lane_t & this) { |
---|
[ef94ae7] | 123 | return this.anchor.next == 0p; |
---|
[f6fdfb14] | 124 | } |
---|
| 125 | |
---|
| 126 | // Return the timestamp |
---|
| 127 | static inline unsigned long long ts(__intrusive_lane_t & this) { |
---|
| 128 | // Cannot verify here since it may not be locked |
---|
[ef94ae7] | 129 | /* paranoid */ verify(this.anchor.ts != 0); |
---|
[f6fdfb14] | 130 | return this.anchor.ts; |
---|
[8cd40bf] | 131 | } |
---|