[13c5e19] | 1 | #pragma once
|
---|
| 2 |
|
---|
| 3 | #define __CFA_NO_SCHED_STATS__
|
---|
| 4 |
|
---|
| 5 | // Intrusives lanes which are used by the relaxed ready queue
|
---|
| 6 | struct __attribute__((aligned(128))) __intrusive_lane_t {
|
---|
| 7 |
|
---|
| 8 | // anchor for the head and the tail of the queue
|
---|
| 9 | __attribute__((aligned(128))) struct __sentinel_t {
|
---|
| 10 | // Link lists fields
|
---|
| 11 | // instrusive link field for threads
|
---|
| 12 | // must be exactly as in $thread
|
---|
| 13 | __thread_desc_link link;
|
---|
| 14 | } before, after;
|
---|
| 15 |
|
---|
| 16 | // spin lock protecting the queue
|
---|
| 17 | volatile bool lock;
|
---|
| 18 |
|
---|
| 19 | // Optional statistic counters
|
---|
| 20 | #if !defined(__CFA_NO_SCHED_STATS__)
|
---|
| 21 | struct __attribute__((aligned(64))) {
|
---|
| 22 | // difference between number of push and pops
|
---|
| 23 | ssize_t diff;
|
---|
| 24 |
|
---|
| 25 | // total number of pushes and pops
|
---|
| 26 | size_t push;
|
---|
| 27 | size_t pop ;
|
---|
| 28 | } stat;
|
---|
| 29 | #endif
|
---|
| 30 | };
|
---|
| 31 |
|
---|
| 32 | void ?{}(__intrusive_lane_t & this);
|
---|
| 33 | void ^?{}(__intrusive_lane_t & this);
|
---|
| 34 |
|
---|
| 35 | // Get the head pointer (one before the first element) from the anchor
|
---|
| 36 | static inline $thread * head(const __intrusive_lane_t & this) {
|
---|
| 37 | $thread * rhead = ($thread *)(
|
---|
| 38 | (uintptr_t)( &this.before ) - offsetof( $thread, link )
|
---|
| 39 | );
|
---|
| 40 | /* paranoid */ verify(rhead);
|
---|
| 41 | return rhead;
|
---|
| 42 | }
|
---|
| 43 |
|
---|
| 44 | // Get the tail pointer (one after the last element) from the anchor
|
---|
| 45 | static inline $thread * tail(const __intrusive_lane_t & this) {
|
---|
| 46 | $thread * rtail = ($thread *)(
|
---|
| 47 | (uintptr_t)( &this.after ) - offsetof( $thread, link )
|
---|
| 48 | );
|
---|
| 49 | /* paranoid */ verify(rtail);
|
---|
| 50 | return rtail;
|
---|
| 51 | }
|
---|
| 52 |
|
---|
| 53 | // Ctor
|
---|
| 54 | void ?{}( __intrusive_lane_t & this ) {
|
---|
| 55 | this.lock = false;
|
---|
| 56 |
|
---|
| 57 | this.before.link.prev = 0p;
|
---|
| 58 | this.before.link.next = tail(this);
|
---|
| 59 | this.before.link.ts = 0;
|
---|
| 60 |
|
---|
| 61 | this.after .link.prev = head(this);
|
---|
| 62 | this.after .link.next = 0p;
|
---|
| 63 | this.after .link.ts = 0;
|
---|
| 64 |
|
---|
| 65 | #if !defined(__CFA_NO_SCHED_STATS__)
|
---|
| 66 | this.stat.diff = 0;
|
---|
| 67 | this.stat.push = 0;
|
---|
| 68 | this.stat.pop = 0;
|
---|
| 69 | #endif
|
---|
| 70 |
|
---|
| 71 | // We add a boat-load of assertions here because the anchor code is very fragile
|
---|
| 72 | /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
|
---|
| 73 | /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
|
---|
| 74 | /* paranoid */ verify(head(this)->link.prev == 0p );
|
---|
| 75 | /* paranoid */ verify(head(this)->link.next == tail(this) );
|
---|
| 76 | /* paranoid */ verify(tail(this)->link.next == 0p );
|
---|
| 77 | /* paranoid */ verify(tail(this)->link.prev == head(this) );
|
---|
| 78 | /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
|
---|
| 79 | /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
|
---|
| 80 | /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
|
---|
| 81 | /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
|
---|
| 82 | /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
|
---|
| 83 | /* paranoid */ verify(__alignof__(this) == 128);
|
---|
| 84 | /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
|
---|
| 85 | }
|
---|
| 86 |
|
---|
| 87 | // Dtor is trivial
|
---|
| 88 | void ^?{}( __intrusive_lane_t & this ) {
|
---|
| 89 | // Make sure the list is empty
|
---|
| 90 | /* paranoid */ verify(head(this)->link.prev == 0p );
|
---|
| 91 | /* paranoid */ verify(head(this)->link.next == tail(this) );
|
---|
| 92 | /* paranoid */ verify(tail(this)->link.next == 0p );
|
---|
| 93 | /* paranoid */ verify(tail(this)->link.prev == head(this) );
|
---|
| 94 | }
|
---|
| 95 |
|
---|
| 96 | // Push a thread onto this lane
|
---|
| 97 | // returns true of lane was empty before push, false otherwise
|
---|
| 98 | bool push(__intrusive_lane_t & this, $thread * node) {
|
---|
| 99 | #if defined(__CFA_WITH_VERIFY__)
|
---|
| 100 | /* paranoid */ verify(this.lock);
|
---|
| 101 | /* paranoid */ verify(node->link.ts != 0);
|
---|
| 102 | /* paranoid */ verify(node->link.next == 0p);
|
---|
| 103 | /* paranoid */ verify(node->link.prev == 0p);
|
---|
| 104 | /* paranoid */ verify(tail(this)->link.next == 0p);
|
---|
| 105 | /* paranoid */ verify(head(this)->link.prev == 0p);
|
---|
| 106 |
|
---|
| 107 | if(this.before.link.ts == 0l) {
|
---|
| 108 | /* paranoid */ verify(tail(this)->link.prev == head(this));
|
---|
| 109 | /* paranoid */ verify(head(this)->link.next == tail(this));
|
---|
| 110 | } else {
|
---|
| 111 | /* paranoid */ verify(tail(this)->link.prev != head(this));
|
---|
| 112 | /* paranoid */ verify(head(this)->link.next != tail(this));
|
---|
| 113 | }
|
---|
| 114 | #endif
|
---|
| 115 |
|
---|
| 116 | // Get the relevant nodes locally
|
---|
| 117 | $thread * tail = tail(this);
|
---|
| 118 | $thread * prev = tail->link.prev;
|
---|
| 119 |
|
---|
| 120 | // Do the push
|
---|
| 121 | node->link.next = tail;
|
---|
| 122 | node->link.prev = prev;
|
---|
| 123 | prev->link.next = node;
|
---|
| 124 | tail->link.prev = node;
|
---|
| 125 |
|
---|
| 126 | // Update stats
|
---|
| 127 | #if !defined(__CFA_NO_SCHED_STATS__)
|
---|
| 128 | this.stat.diff++;
|
---|
| 129 | this.stat.push++;
|
---|
| 130 | #endif
|
---|
| 131 |
|
---|
| 132 | verify(node->link.next == tail(this));
|
---|
| 133 |
|
---|
| 134 | // Check if the queue used to be empty
|
---|
| 135 | if(this.before.link.ts == 0l) {
|
---|
| 136 | this.before.link.ts = node->link.ts;
|
---|
| 137 | /* paranoid */ verify(node->link.prev == head(this));
|
---|
| 138 | return true;
|
---|
| 139 | }
|
---|
| 140 | return false;
|
---|
| 141 | }
|
---|
| 142 |
|
---|
| 143 | // Pop a thread from this lane (must be non-empty)
|
---|
| 144 | // returns popped
|
---|
| 145 | // returns true of lane was empty before push, false otherwise
|
---|
| 146 | [$thread *, bool] pop(__intrusive_lane_t & this) {
|
---|
| 147 | /* paranoid */ verify(this.lock);
|
---|
| 148 | /* paranoid */ verify(this.before.link.ts != 0ul);
|
---|
| 149 |
|
---|
| 150 | // Get anchors locally
|
---|
| 151 | $thread * head = head(this);
|
---|
| 152 | $thread * tail = tail(this);
|
---|
| 153 |
|
---|
| 154 | // Get the relevant nodes locally
|
---|
| 155 | $thread * node = head->link.next;
|
---|
| 156 | $thread * next = node->link.next;
|
---|
| 157 |
|
---|
| 158 | /* paranoid */ verify(node != tail);
|
---|
| 159 | /* paranoid */ verify(node);
|
---|
| 160 |
|
---|
| 161 | // Do the pop
|
---|
| 162 | head->link.next = next;
|
---|
| 163 | next->link.prev = head;
|
---|
| 164 | node->link.[next, prev] = 0p;
|
---|
| 165 |
|
---|
| 166 | // Update head time stamp
|
---|
| 167 | this.before.link.ts = next->link.ts;
|
---|
| 168 |
|
---|
| 169 | // Update stats
|
---|
| 170 | #ifndef __CFA_NO_SCHED_STATS__
|
---|
| 171 | this.stat.diff--;
|
---|
| 172 | this.stat.pop ++;
|
---|
| 173 | #endif
|
---|
| 174 |
|
---|
| 175 | // Check if we emptied list and return accordingly
|
---|
| 176 | /* paranoid */ verify(tail(this)->link.next == 0p);
|
---|
| 177 | /* paranoid */ verify(head(this)->link.prev == 0p);
|
---|
| 178 | if(next == tail) {
|
---|
| 179 | /* paranoid */ verify(this.before.link.ts == 0);
|
---|
| 180 | /* paranoid */ verify(tail(this)->link.prev == head(this));
|
---|
| 181 | /* paranoid */ verify(head(this)->link.next == tail(this));
|
---|
| 182 | return [node, true];
|
---|
| 183 | }
|
---|
| 184 | else {
|
---|
| 185 | /* paranoid */ verify(next->link.ts != 0);
|
---|
| 186 | /* paranoid */ verify(tail(this)->link.prev != head(this));
|
---|
| 187 | /* paranoid */ verify(head(this)->link.next != tail(this));
|
---|
| 188 | /* paranoid */ verify(this.before.link.ts != 0);
|
---|
| 189 | return [node, false];
|
---|
| 190 | }
|
---|
| 191 | }
|
---|
| 192 |
|
---|
| 193 | // Check whether or not list is empty
|
---|
| 194 | static inline bool is_empty(__intrusive_lane_t & this) {
|
---|
| 195 | // Cannot verify here since it may not be locked
|
---|
| 196 | return this.before.link.ts == 0;
|
---|
| 197 | }
|
---|
| 198 |
|
---|
| 199 | // Return the timestamp
|
---|
| 200 | static inline unsigned long long ts(__intrusive_lane_t & this) {
|
---|
| 201 | // Cannot verify here since it may not be locked
|
---|
| 202 | return this.before.link.ts;
|
---|
| 203 | }
|
---|