source: libcfa/src/concurrency/ready_subqueue.hfa @ 2b96031

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulation
Last change on this file since 2b96031 was 2b96031, checked in by Thierry Delisle <tdelisle@…>, 16 months ago

Added new subqueue implementation.
Seems faster will test on another machine before full replacement.

  • Property mode set to 100644
File size: 11.1 KB
Line 
1#pragma once
2
3#define __CFA_NO_SCHED_STATS__
4
5#include "containers/queueLockFree.hfa"
6
7// #define USE_NEW_SUBQUEUE
8#if defined(USE_NEW_SUBQUEUE)
9        // Intrusives lanes which are used by the relaxed ready queue
10        struct __attribute__((aligned(128))) __intrusive_lane_t {
11                struct $thread * prev;
12
13                // spin lock protecting the queue
14                volatile bool lock;
15
16                __thread_desc_link anchor;
17        };
18
19        // Get the head pointer (one before the first element) from the anchor
20        static inline $thread * mock_head(const __intrusive_lane_t & this) {
21                $thread * rhead = ($thread *)(
22                        (uintptr_t)( &this.anchor ) - __builtin_offsetof( $thread, link )
23                );
24                return rhead;
25        }
26
27        // Ctor
28        void ?{}( __intrusive_lane_t & this ) {
29                this.lock = false;
30                this.prev = mock_head(this);
31                this.anchor.next = 0p;
32                this.anchor.ts   = 0;
33
34                // We add a boat-load of assertions here because the anchor code is very fragile
35                /* paranoid */ verify( ((uintptr_t)( mock_head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.anchor) );
36                /* paranoid */ verify( &mock_head(this)->link.next == &this.anchor.next );
37                /* paranoid */ verify( &mock_head(this)->link.ts   == &this.anchor.ts   );
38                /* paranoid */ verify( mock_head(this)->link.next == 0p );
39                /* paranoid */ verify( mock_head(this)->link.ts   == 0  );
40                /* paranoid */ verify( mock_head(this) == this.prev );
41                /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 );
42                /* paranoid */ verify( __alignof__(this) == 128 );
43                /* paranoid */ verifyf( ((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128) );
44        }
45
46        // Dtor is trivial
47        void ^?{}( __intrusive_lane_t & this ) {
48                // Make sure the list is empty
49                /* paranoid */ verify( this.anchor.next == 0p );
50                /* paranoid */ verify( this.anchor.ts   == 0  );
51                /* paranoid */ verify( mock_head(this)  == this.prev );
52        }
53
54        // Push a thread onto this lane
55        // returns true of lane was empty before push, false otherwise
56        void push( __intrusive_lane_t & this, $thread * node ) {
57                /* paranoid */ verify( node->link.next == 0p );
58                /* paranoid */ verify( node->link.ts   == 0  );
59                /* paranoid */ verify( this.prev->link.next == 0p );
60                /* paranoid */ verify( this.prev->link.ts   == 0  );
61                if( this.anchor.next == 0p ) {
62                        /* paranoid */ verify( this.anchor.next == 0p );
63                        /* paranoid */ verify( this.anchor.ts   == 0  );
64                        /* paranoid */ verify( this.prev == mock_head( this ) );
65                } else {
66                        /* paranoid */ verify( this.anchor.next != 0p );
67                        /* paranoid */ verify( this.anchor.ts   != 0  );
68                        /* paranoid */ verify( this.prev != mock_head( this ) );
69                }
70
71                // Get the relevant nodes locally
72                this.prev->link.next = node;
73                this.prev->link.ts   = rdtscl();
74                this.prev = node;
75        }
76
77        // Pop a thread from this lane (must be non-empty)
78        // returns popped
79        // returns true of lane was empty before push, false otherwise
80        $thread * pop( __intrusive_lane_t & this ) {
81                /* paranoid */ verify( this.anchor.next != 0p );
82                /* paranoid */ verify( this.anchor.ts   != 0  );
83
84                // Get the relevant nodes locally
85                $thread * node = this.anchor.next;
86                this.anchor.next = node->link.next;
87                this.anchor.ts   = node->link.ts;
88                bool is_empty = this.anchor.ts == 0;
89                node->link.next = 0p;
90                node->link.ts   = 0;
91
92                // Update head time stamp
93                if(is_empty) this.prev = mock_head( this );
94
95                /* paranoid */ verify( node->link.next == 0p );
96                /* paranoid */ verify( node->link.ts   == 0  );
97                return node;
98        }
99
100        // Check whether or not list is empty
101        static inline bool is_empty(__intrusive_lane_t & this) {
102                return this.anchor.ts == 0;
103        }
104
105        // Return the timestamp
106        static inline unsigned long long ts(__intrusive_lane_t & this) {
107                // Cannot verify here since it may not be locked
108                return this.anchor.ts;
109        }
110#else
111        // Intrusives lanes which are used by the relaxed ready queue
112        struct __attribute__((aligned(128))) __intrusive_lane_t {
113
114                #if defined(USE_MPSC)
115                        mpsc_queue($thread) queue;
116                        __attribute__((aligned(128)))
117                #else
118                        // anchor for the head and the tail of the queue
119                        __attribute__((aligned(128))) struct __sentinel_t {
120                                // Link lists fields
121                                // instrusive link field for threads
122                                // must be exactly as in $thread
123                                __thread_desc_link link;
124                        } before, after;
125
126                        // spin lock protecting the queue
127                        volatile bool lock;
128                #endif
129
130                // Optional statistic counters
131                #if !defined(__CFA_NO_SCHED_STATS__)
132                        struct __attribute__((aligned(64))) {
133                                // difference between number of push and pops
134                                ssize_t diff;
135
136                                // total number of pushes and pops
137                                size_t  push;
138                                size_t  pop ;
139                        } stat;
140                #endif
141        };
142
143        void  ?{}(__intrusive_lane_t & this);
144        void ^?{}(__intrusive_lane_t & this);
145
146        // Get the head pointer (one before the first element) from the anchor
147        static inline $thread * head(const __intrusive_lane_t & this) {
148                #if defined(USE_MPSC)
149                        return this.queue.head;
150                #else
151                        $thread * rhead = ($thread *)(
152                                (uintptr_t)( &this.before ) - offsetof( $thread, link )
153                        );
154                        /* paranoid */ verify(rhead);
155                        return rhead;
156                #endif
157        }
158
159        // Get the tail pointer (one after the last element) from the anchor
160        static inline $thread * tail(const __intrusive_lane_t & this) {
161                #if defined(USE_MPSC)
162                        return this.queue.tail;
163                #else
164                        $thread * rtail = ($thread *)(
165                                (uintptr_t)( &this.after ) - offsetof( $thread, link )
166                        );
167                        /* paranoid */ verify(rtail);
168                        return rtail;
169                #endif
170        }
171
172        // Ctor
173        void ?{}( __intrusive_lane_t & this ) {
174                this.lock = false;
175
176                #if !defined(USE_MPSC)
177                        this.before.link.prev = 0p;
178                        this.before.link.next = tail(this);
179                        this.before.link.ts   = 0;
180
181                        this.after .link.prev = head(this);
182                        this.after .link.next = 0p;
183                        this.after .link.ts   = 0;
184
185                        #if !defined(__CFA_NO_SCHED_STATS__)
186                                this.stat.diff = 0;
187                                this.stat.push = 0;
188                                this.stat.pop  = 0;
189                        #endif
190
191                        // We add a boat-load of assertions here because the anchor code is very fragile
192                        /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
193                        /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
194                        /* paranoid */ verify(head(this)->link.prev == 0p );
195                        /* paranoid */ verify(head(this)->link.next == tail(this) );
196                        /* paranoid */ verify(tail(this)->link.next == 0p );
197                        /* paranoid */ verify(tail(this)->link.prev == head(this) );
198                        /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
199                        /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
200                        /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
201                        /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
202                        /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
203                        /* paranoid */ verify(__alignof__(this) == 128);
204                        /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
205                #endif
206        }
207
208        // Dtor is trivial
209        void ^?{}( __intrusive_lane_t & this ) {
210                #if !defined(USE_MPSC)
211                        // Make sure the list is empty
212                        /* paranoid */ verify(head(this)->link.prev == 0p );
213                        /* paranoid */ verify(head(this)->link.next == tail(this) );
214                        /* paranoid */ verify(tail(this)->link.next == 0p );
215                        /* paranoid */ verify(tail(this)->link.prev == head(this) );
216                #endif
217        }
218
219        // Push a thread onto this lane
220        // returns true of lane was empty before push, false otherwise
221        bool push(__intrusive_lane_t & this, $thread * node) {
222                #if defined(USE_MPSC)
223                        inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
224                                return this->link.next;
225                        }
226                        push(this.queue, node);
227                #else
228                        #if defined(__CFA_WITH_VERIFY__)
229                                /* paranoid */ verify(this.lock);
230                                /* paranoid */ verify(node->link.ts != 0);
231                                /* paranoid */ verify(node->link.next == 0p);
232                                /* paranoid */ verify(node->link.prev == 0p);
233                                /* paranoid */ verify(tail(this)->link.next == 0p);
234                                /* paranoid */ verify(head(this)->link.prev == 0p);
235
236                                if(this.before.link.ts == 0l) {
237                                        /* paranoid */ verify(tail(this)->link.prev == head(this));
238                                        /* paranoid */ verify(head(this)->link.next == tail(this));
239                                } else {
240                                        /* paranoid */ verify(tail(this)->link.prev != head(this));
241                                        /* paranoid */ verify(head(this)->link.next != tail(this));
242                                }
243                        #endif
244
245                        // Get the relevant nodes locally
246                        $thread * tail = tail(this);
247                        $thread * prev = tail->link.prev;
248
249                        // Do the push
250                        node->link.next = tail;
251                        node->link.prev = prev;
252                        prev->link.next = node;
253                        tail->link.prev = node;
254
255                        // Update stats
256                        #if !defined(__CFA_NO_SCHED_STATS__)
257                                this.stat.diff++;
258                                this.stat.push++;
259                        #endif
260
261                        verify(node->link.next == tail(this));
262
263                        // Check if the queue used to be empty
264                        if(this.before.link.ts == 0l) {
265                                this.before.link.ts = node->link.ts;
266                                /* paranoid */ verify(node->link.prev == head(this));
267                                return true;
268                        }
269                        return false;
270                #endif
271        }
272
273        // Pop a thread from this lane (must be non-empty)
274        // returns popped
275        // returns true of lane was empty before push, false otherwise
276        $thread * pop(__intrusive_lane_t & this) {
277                /* paranoid */ verify(this.lock);
278                #if defined(USE_MPSC)
279                        inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
280                                return this->link.next;
281                        }
282                        return pop(this.queue);
283                #else
284                        /* paranoid */ verify(this.before.link.ts != 0ul);
285
286                        // Get anchors locally
287                        $thread * head = head(this);
288                        $thread * tail = tail(this);
289
290                        // Get the relevant nodes locally
291                        $thread * node = head->link.next;
292                        $thread * next = node->link.next;
293
294                        /* paranoid */ verify(node != tail);
295                        /* paranoid */ verify(node);
296
297                        // Do the pop
298                        head->link.next = next;
299                        next->link.prev = head;
300                        node->link.next = 0p;
301                        node->link.prev = 0p;
302
303                        // Update head time stamp
304                        this.before.link.ts = next->link.ts;
305
306                        // Update stats
307                        #ifndef __CFA_NO_SCHED_STATS__
308                                this.stat.diff--;
309                                this.stat.pop ++;
310                        #endif
311
312                        // Check if we emptied list and return accordingly
313                        /* paranoid */ verify(tail(this)->link.next == 0p);
314                        /* paranoid */ verify(head(this)->link.prev == 0p);
315                        if(next == tail) {
316                                /* paranoid */ verify(this.before.link.ts == 0);
317                                /* paranoid */ verify(tail(this)->link.prev == head(this));
318                                /* paranoid */ verify(head(this)->link.next == tail(this));
319                                return node;
320                        }
321                        else {
322                                /* paranoid */ verify(next->link.ts != 0);
323                                /* paranoid */ verify(tail(this)->link.prev != head(this));
324                                /* paranoid */ verify(head(this)->link.next != tail(this));
325                                /* paranoid */ verify(this.before.link.ts != 0);
326                                return node;
327                        }
328                #endif
329        }
330
331        // Check whether or not list is empty
332        static inline bool is_empty(__intrusive_lane_t & this) {
333                #if defined(USE_MPSC)
334                        return this.queue.head == 0p;
335                #else
336                        // Cannot verify here since it may not be locked
337                        return this.before.link.ts == 0;
338                #endif
339        }
340
341        // Return the timestamp
342        static inline unsigned long long ts(__intrusive_lane_t & this) {
343                #if defined(USE_MPSC)
344                        $thread * tl = this.queue.head;
345                        if(!tl) return -1ull;
346                        return tl->link.ts;
347                #else
348                        // Cannot verify here since it may not be locked
349                        return this.before.link.ts;
350                #endif
351        }
352#endif
353
354// Aligned timestamps which are used by the relaxed ready queue
355struct __attribute__((aligned(128))) __timestamp_t {
356        volatile unsigned long long tv;
357};
358
359void  ?{}(__timestamp_t & this) { this.tv = 0; }
360void ^?{}(__timestamp_t & this) {}
Note: See TracBrowser for help on using the repository browser.