source: libcfa/src/concurrency/ready_subqueue.hfa @ 7ee3c87

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 7ee3c87 was 7a2972b, checked in by Thierry Delisle <tdelisle@…>, 7 months ago

ready queue can now toggle between

  • lock-based queue
  • mpsc_queue a.k.a. nemesis queue

slightly messy implementation, some clean up needed.

  • Property mode set to 100644
File size: 7.1 KB
Line 
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
8struct __attribute__((aligned(128))) __intrusive_lane_t {
9
10        #if defined(USE_MPSC)
11                mpsc_queue($thread) queue;
12                __attribute__((aligned(128)))
13        #else
14                // anchor for the head and the tail of the queue
15                __attribute__((aligned(128))) struct __sentinel_t {
16                        // Link lists fields
17                        // instrusive link field for threads
18                        // must be exactly as in $thread
19                        __thread_desc_link link;
20                } before, after;
21        #endif
22
23        // spin lock protecting the queue
24        volatile bool lock;
25
26        // Optional statistic counters
27        #if !defined(__CFA_NO_SCHED_STATS__)
28                struct __attribute__((aligned(64))) {
29                        // difference between number of push and pops
30                        ssize_t diff;
31
32                        // total number of pushes and pops
33                        size_t  push;
34                        size_t  pop ;
35                } stat;
36        #endif
37};
38
39void  ?{}(__intrusive_lane_t & this);
40void ^?{}(__intrusive_lane_t & this);
41
42// Get the head pointer (one before the first element) from the anchor
43static inline $thread * head(const __intrusive_lane_t & this) {
44        #if defined(USE_MPSC)
45                return this.queue.head;
46        #else
47                $thread * rhead = ($thread *)(
48                        (uintptr_t)( &this.before ) - offsetof( $thread, link )
49                );
50                /* paranoid */ verify(rhead);
51                return rhead;
52        #endif
53}
54
55// Get the tail pointer (one after the last element) from the anchor
56static inline $thread * tail(const __intrusive_lane_t & this) {
57        #if defined(USE_MPSC)
58                return this.queue.tail;
59        #else
60                $thread * rtail = ($thread *)(
61                        (uintptr_t)( &this.after ) - offsetof( $thread, link )
62                );
63                /* paranoid */ verify(rtail);
64                return rtail;
65        #endif
66}
67
68// Ctor
69void ?{}( __intrusive_lane_t & this ) {
70        this.lock = false;
71
72        #if !defined(USE_MPSC)
73                this.before.link.prev = 0p;
74                this.before.link.next = tail(this);
75                this.before.link.ts   = 0;
76
77                this.after .link.prev = head(this);
78                this.after .link.next = 0p;
79                this.after .link.ts   = 0;
80
81                #if !defined(__CFA_NO_SCHED_STATS__)
82                        this.stat.diff = 0;
83                        this.stat.push = 0;
84                        this.stat.pop  = 0;
85                #endif
86
87                // We add a boat-load of assertions here because the anchor code is very fragile
88                /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
89                /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
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                /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
95                /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
96                /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
97                /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
98                /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
99                /* paranoid */ verify(__alignof__(this) == 128);
100                /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
101        #endif
102}
103
104// Dtor is trivial
105void ^?{}( __intrusive_lane_t & this ) {
106        #if !defined(USE_MPSC)
107                // Make sure the list is empty
108                /* paranoid */ verify(head(this)->link.prev == 0p );
109                /* paranoid */ verify(head(this)->link.next == tail(this) );
110                /* paranoid */ verify(tail(this)->link.next == 0p );
111                /* paranoid */ verify(tail(this)->link.prev == head(this) );
112        #endif
113}
114
115// Push a thread onto this lane
116// returns true of lane was empty before push, false otherwise
117bool push(__intrusive_lane_t & this, $thread * node) {
118        #if defined(USE_MPSC)
119                inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
120                        return this->link.next;
121                }
122                push(this.queue, node);
123        #else
124                #if defined(__CFA_WITH_VERIFY__)
125                        /* paranoid */ verify(this.lock);
126                        /* paranoid */ verify(node->link.ts != 0);
127                        /* paranoid */ verify(node->link.next == 0p);
128                        /* paranoid */ verify(node->link.prev == 0p);
129                        /* paranoid */ verify(tail(this)->link.next == 0p);
130                        /* paranoid */ verify(head(this)->link.prev == 0p);
131
132                        if(this.before.link.ts == 0l) {
133                                /* paranoid */ verify(tail(this)->link.prev == head(this));
134                                /* paranoid */ verify(head(this)->link.next == tail(this));
135                        } else {
136                                /* paranoid */ verify(tail(this)->link.prev != head(this));
137                                /* paranoid */ verify(head(this)->link.next != tail(this));
138                        }
139                #endif
140
141                // Get the relevant nodes locally
142                $thread * tail = tail(this);
143                $thread * prev = tail->link.prev;
144
145                // Do the push
146                node->link.next = tail;
147                node->link.prev = prev;
148                prev->link.next = node;
149                tail->link.prev = node;
150
151                // Update stats
152                #if !defined(__CFA_NO_SCHED_STATS__)
153                        this.stat.diff++;
154                        this.stat.push++;
155                #endif
156
157                verify(node->link.next == tail(this));
158
159                // Check if the queue used to be empty
160                if(this.before.link.ts == 0l) {
161                        this.before.link.ts = node->link.ts;
162                        /* paranoid */ verify(node->link.prev == head(this));
163                        return true;
164                }
165                return false;
166        #endif
167}
168
169// Pop a thread from this lane (must be non-empty)
170// returns popped
171// returns true of lane was empty before push, false otherwise
172$thread * pop(__intrusive_lane_t & this) {
173        /* paranoid */ verify(this.lock);
174        #if defined(USE_MPSC)
175                inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
176                        return this->link.next;
177                }
178                return pop(this.queue);
179        #else
180                /* paranoid */ verify(this.before.link.ts != 0ul);
181
182                // Get anchors locally
183                $thread * head = head(this);
184                $thread * tail = tail(this);
185
186                // Get the relevant nodes locally
187                $thread * node = head->link.next;
188                $thread * next = node->link.next;
189
190                /* paranoid */ verify(node != tail);
191                /* paranoid */ verify(node);
192
193                // Do the pop
194                head->link.next = next;
195                next->link.prev = head;
196                node->link.next = 0p;
197                node->link.prev = 0p;
198
199                // Update head time stamp
200                this.before.link.ts = next->link.ts;
201
202                // Update stats
203                #ifndef __CFA_NO_SCHED_STATS__
204                        this.stat.diff--;
205                        this.stat.pop ++;
206                #endif
207
208                // Check if we emptied list and return accordingly
209                /* paranoid */ verify(tail(this)->link.next == 0p);
210                /* paranoid */ verify(head(this)->link.prev == 0p);
211                if(next == tail) {
212                        /* paranoid */ verify(this.before.link.ts == 0);
213                        /* paranoid */ verify(tail(this)->link.prev == head(this));
214                        /* paranoid */ verify(head(this)->link.next == tail(this));
215                        return node;
216                }
217                else {
218                        /* paranoid */ verify(next->link.ts != 0);
219                        /* paranoid */ verify(tail(this)->link.prev != head(this));
220                        /* paranoid */ verify(head(this)->link.next != tail(this));
221                        /* paranoid */ verify(this.before.link.ts != 0);
222                        return node;
223                }
224        #endif
225}
226
227// Check whether or not list is empty
228static inline bool is_empty(__intrusive_lane_t & this) {
229        #if defined(USE_MPSC)
230                return this.queue.head == 0p;
231        #else
232                // Cannot verify here since it may not be locked
233                return this.before.link.ts == 0;
234        #endif
235}
236
237// Return the timestamp
238static inline unsigned long long ts(__intrusive_lane_t & this) {
239        #if defined(USE_MPSC)
240                $thread * tl = this.queue.head;
241                if(!tl) return -1ull;
242                return tl->link.ts;
243        #else
244                // Cannot verify here since it may not be locked
245                return this.before.link.ts;
246        #endif
247}
Note: See TracBrowser for help on using the repository browser.