1 | #pragma once |
---|
2 | |
---|
3 | #define __CFA_NO_SCHED_STATS__ |
---|
4 | |
---|
5 | #include "containers/queueLockFree.hfa" |
---|
6 | |
---|
7 | // Intrusives lanes which are used by the relaxed ready queue |
---|
8 | struct __attribute__((aligned(128))) __intrusive_lane_t { |
---|
9 | struct $thread * prev; |
---|
10 | |
---|
11 | // spin lock protecting the queue |
---|
12 | volatile bool lock; |
---|
13 | |
---|
14 | __thread_desc_link anchor; |
---|
15 | |
---|
16 | #if !defined(__CFA_NO_STATISTICS__) |
---|
17 | unsigned cnt; |
---|
18 | #endif |
---|
19 | }; |
---|
20 | |
---|
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; |
---|
34 | this.anchor.ts = -1llu; |
---|
35 | #if !defined(__CFA_NO_STATISTICS__) |
---|
36 | this.cnt = 0; |
---|
37 | #endif |
---|
38 | |
---|
39 | // We add a boat-load of assertions here because the anchor code is very fragile |
---|
40 | /* paranoid */ _Static_assert( offsetof( $thread, link ) == offsetof(__intrusive_lane_t, anchor) ); |
---|
41 | /* paranoid */ verify( offsetof( $thread, link ) == offsetof(__intrusive_lane_t, anchor) ); |
---|
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 ); |
---|
46 | /* paranoid */ verify( mock_head(this)->link.ts == -1llu ); |
---|
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 ); |
---|
57 | /* paranoid */ verify( this.anchor.ts == -1llu ); |
---|
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 |
---|
63 | static inline void push( __intrusive_lane_t & this, $thread * node ) { |
---|
64 | /* paranoid */ verify( this.lock ); |
---|
65 | /* paranoid */ verify( node->link.next == 0p ); |
---|
66 | /* paranoid */ verify( node->link.ts == -1llu ); |
---|
67 | /* paranoid */ verify( this.prev->link.next == 0p ); |
---|
68 | /* paranoid */ verify( this.prev->link.ts == -1llu ); |
---|
69 | if( this.anchor.next == 0p ) { |
---|
70 | /* paranoid */ verify( this.anchor.next == 0p ); |
---|
71 | /* paranoid */ verify( this.anchor.ts == -1llu ); |
---|
72 | /* paranoid */ verify( this.anchor.ts != 0 ); |
---|
73 | /* paranoid */ verify( this.prev == mock_head( this ) ); |
---|
74 | } else { |
---|
75 | /* paranoid */ verify( this.anchor.next != 0p ); |
---|
76 | /* paranoid */ verify( this.anchor.ts != -1llu ); |
---|
77 | /* paranoid */ verify( this.anchor.ts != 0 ); |
---|
78 | /* paranoid */ verify( this.prev != mock_head( this ) ); |
---|
79 | } |
---|
80 | |
---|
81 | // Get the relevant nodes locally |
---|
82 | this.prev->link.next = node; |
---|
83 | this.prev->link.ts = rdtscl(); |
---|
84 | this.prev = node; |
---|
85 | #if !defined(__CFA_NO_STATISTICS__) |
---|
86 | this.cnt++; |
---|
87 | #endif |
---|
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 |
---|
93 | static inline [* $thread, unsigned long long] pop( __intrusive_lane_t & this ) { |
---|
94 | /* paranoid */ verify( this.lock ); |
---|
95 | /* paranoid */ verify( this.anchor.next != 0p ); |
---|
96 | /* paranoid */ verify( this.anchor.ts != -1llu ); |
---|
97 | /* paranoid */ verify( this.anchor.ts != 0 ); |
---|
98 | |
---|
99 | // Get the relevant nodes locally |
---|
100 | unsigned long long ts = this.anchor.ts; |
---|
101 | $thread * node = this.anchor.next; |
---|
102 | this.anchor.next = node->link.next; |
---|
103 | this.anchor.ts = node->link.ts; |
---|
104 | bool is_empty = this.anchor.next == 0p; |
---|
105 | node->link.next = 0p; |
---|
106 | node->link.ts = -1llu; |
---|
107 | #if !defined(__CFA_NO_STATISTICS__) |
---|
108 | this.cnt--; |
---|
109 | #endif |
---|
110 | |
---|
111 | // Update head time stamp |
---|
112 | if(is_empty) this.prev = mock_head( this ); |
---|
113 | |
---|
114 | /* paranoid */ verify( node->link.next == 0p ); |
---|
115 | /* paranoid */ verify( node->link.ts == -1llu ); |
---|
116 | /* paranoid */ verify( node->link.ts != 0 ); |
---|
117 | /* paranoid */ verify( this.anchor.ts != 0 ); |
---|
118 | return [node, ts]; |
---|
119 | } |
---|
120 | |
---|
121 | // Check whether or not list is empty |
---|
122 | static inline bool is_empty(__intrusive_lane_t & this) { |
---|
123 | return this.anchor.next == 0p; |
---|
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 |
---|
129 | /* paranoid */ verify(this.anchor.ts != 0); |
---|
130 | return this.anchor.ts; |
---|
131 | } |
---|