source: tests/zombies/linked-list-perf/thierry-subqueue-old-rip.hfa @ 221c542e

Last change on this file since 221c542e was 3c2c2f0, checked in by Michael Brooks <mlbrooks@…>, 3 years ago

The cheap and chearful linked-list performance test

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