source: doc/theses/thierry_delisle_PhD/code/relaxed_list.hpp @ b2a37b0

arm-ehjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since b2a37b0 was b2a37b0, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

Initial drafts in C++ of the CFA scheduler

  • Property mode set to 100644
File size: 6.7 KB
Line 
1#pragma once
2
3#include <iostream>
4#include <memory>
5#include <mutex>
6#include <type_traits>
7
8#include "assert.hpp"
9#include "utils.hpp"
10
11using namespace std;
12
13extern bool enable_stats;
14
15
16struct pick_stat {
17        size_t attempt = 0;
18        size_t success = 0;
19};
20
21extern __attribute__((aligned(64))) thread_local pick_stat local_pick;
22
23template<typename node_t>
24struct _LinksFields_t {
25        node_t * prev = nullptr;
26        node_t * next = nullptr;
27        unsigned long long ts = 0;
28};
29
30struct spinlock_t {
31        std::atomic_bool ll = { false };
32
33        inline void lock() {
34                while( __builtin_expect(ll.exchange(true),false) ) {
35                        while(ll.load(std::memory_order_relaxed))
36                                asm volatile("pause");
37                }
38        }
39
40        inline void unlock() {
41                ll.store(false, std::memory_order_release);
42        }
43};
44
45template<typename node_t>
46class relaxed_list {
47        static_assert(std::is_same<decltype(node_t::_links), _LinksFields_t<node_t>>::value, "Node must have a links field");
48
49
50public:
51        relaxed_list(unsigned numLists)
52                : numLists(numLists)
53                , lists(new intrusive_queue_t[numLists])
54                , numNonEmpty(0)
55        {}
56
57        void push(node_t * node) {
58                int i = rng_g.next() % numLists;
59                lists[i].push(node, numNonEmpty);
60        }
61
62        node_t * pop() {
63                int i = pickRandomly(-1);
64                int j = pickRandomly(i);
65
66                if(i == -1) {
67                        return nullptr;
68                }
69
70                auto guard = lock(i, j);
71                auto & list = best(i, j);
72                return list.pop(numNonEmpty);
73        }
74
75        node_t * pop2() {
76                int i = pickRandomly(-1);
77                int j = pickRandomly(i);
78
79                if(i == -1) {
80                        return nullptr;
81                }
82
83                auto & list = best2(i, j);
84                return list.pop2(numNonEmpty);
85        }
86
87private:
88
89        class intrusive_queue_t {
90        public:
91                typedef spinlock_t lock_t;
92
93                friend class relaxed_list<node_t>;
94
95        private:
96                struct sentinel_t {
97                        _LinksFields_t<node_t> _links;
98                };
99
100                struct stat {
101                        size_t push = 0;
102                        size_t pop  = 0;
103                };
104
105                __attribute__((aligned(64))) lock_t lock;
106                __attribute__((aligned(64))) bool empty;
107                stat s;
108                sentinel_t before;
109                sentinel_t after;
110
111                static constexpr auto fields_offset = offsetof( node_t, _links );
112        public:
113                intrusive_queue_t()
114                        : empty(true)
115                        , before{{ nullptr, tail() }}
116                        , after {{ head(), nullptr }}
117                {
118                        assert((reinterpret_cast<uintptr_t>( head() ) + fields_offset) == reinterpret_cast<uintptr_t>(&before));
119                        assert((reinterpret_cast<uintptr_t>( tail() ) + fields_offset) == reinterpret_cast<uintptr_t>(&after ));
120                        assert(head()->_links.prev == nullptr);
121                        assert(head()->_links.next == tail() );
122                        assert(tail()->_links.next == nullptr);
123                        assert(tail()->_links.prev == head() );
124                }
125
126                ~intrusive_queue_t() {
127                        std::cout << " Push: " << s.push << "\tPop: " << s.pop << "\t(this: " << this << ")" << std::endl;
128                }
129
130                node_t * head() const {
131                        return reinterpret_cast<node_t *>(
132                                reinterpret_cast<uintptr_t>( &before ) - fields_offset
133                        );
134                }
135
136                node_t * tail() const {
137                        return reinterpret_cast<node_t *>(
138                                reinterpret_cast<uintptr_t>( &after ) - fields_offset
139                        );
140                }
141
142                void push(node_t * node, volatile int & nonEmpty) {
143                        node_t * tail = this->tail();
144                        std::lock_guard<lock_t> guard(lock);
145                        node->_links.ts = rdtscl();
146
147                        node_t * prev = tail->_links.prev;
148                        // assertf(node->_links.ts >= prev->_links.ts,
149                        // "New node has smaller timestamp: %llu < %llu", node->_links.ts, prev->_links.ts);
150                        node->_links.next = tail;
151                        node->_links.prev = prev;
152                        prev->_links.next = node;
153                        tail->_links.prev = node;
154                        if(empty) {
155                                __atomic_fetch_add(&nonEmpty, 1, __ATOMIC_SEQ_CST);
156                                empty = false;
157                        }
158                        if(enable_stats) s.push++;
159                }
160
161                node_t * pop(volatile int & nonEmpty) {
162                        node_t * head = this->head();
163                        node_t * tail = this->tail();
164
165                        node_t * node = head->_links.next;
166                        node_t * next = node->_links.next;
167                        if(node == tail) return nullptr;
168
169                        head->_links.next = next;
170                        next->_links.prev = head;
171
172                        if(next == tail) {
173                                empty = true;
174                                __atomic_fetch_sub(&nonEmpty, 1, __ATOMIC_SEQ_CST);
175                        }
176                        if(enable_stats) s.pop++;
177                        return node;
178                }
179
180                node_t * pop2(volatile int & nonEmpty) {
181                        node_t * head = this->head();
182                        node_t * tail = this->tail();
183
184                        std::lock_guard<lock_t> guard(lock);
185                        node_t * node = head->_links.next;
186                        node_t * next = node->_links.next;
187                        if(node == tail) return nullptr;
188
189                        head->_links.next = next;
190                        next->_links.prev = head;
191
192                        if(next == tail) {
193                                empty = true;
194                                __atomic_fetch_sub(&nonEmpty, 1, __ATOMIC_SEQ_CST);
195                        }
196                        if(enable_stats) s.pop++;
197                        return node;
198                }
199
200                static intrusive_queue_t & best(intrusive_queue_t & lhs, intrusive_queue_t & rhs) {
201                        bool lhs_empty = lhs.empty;
202                        bool rhs_empty = rhs.empty;
203
204                        if(lhs_empty && rhs_empty) return lhs;
205                        if(!lhs_empty && rhs_empty) return lhs;
206                        if(lhs_empty && !rhs_empty) return rhs;
207                        node_t * lhs_head = lhs.head()->_links.next;
208                        node_t * rhs_head = rhs.head()->_links.next;
209
210                        assert(lhs_head != lhs.tail());
211                        assert(rhs_head != rhs.tail());
212
213                        if(lhs_head->_links.ts < lhs_head->_links.ts) {
214                                return lhs;
215                        } else {
216                                return rhs;
217                        }
218                }
219
220                static intrusive_queue_t & best2(intrusive_queue_t & lhs, intrusive_queue_t & rhs) {
221                        node_t * lhs_head = lhs.head()->_links.next;
222                        node_t * rhs_head = rhs.head()->_links.next;
223
224                        bool lhs_empty = lhs_head != lhs.tail();
225                        bool rhs_empty = rhs_head != rhs.tail();
226                        if(lhs_empty && rhs_empty) return lhs;
227                        if(!lhs_empty && rhs_empty) return lhs;
228                        if(lhs_empty && !rhs_empty) return rhs;
229
230                        if(lhs_head->_links.ts < lhs_head->_links.ts) {
231                                return lhs;
232                        } else {
233                                return rhs;
234                        }
235                }
236        };
237
238
239private:
240
241        static thread_local Random rng_g;
242        __attribute__((aligned(64))) const unsigned numLists;
243        std::unique_ptr<intrusive_queue_t []> lists;
244        __attribute__((aligned(64))) volatile int numNonEmpty; // number of non-empty lists
245
246
247private:
248
249
250
251private:
252        int pickRandomly(const int avoid) {
253                int j;
254                do {
255                        local_pick.attempt++;
256                        j = rng_g.next() % numLists;
257                        if (numNonEmpty < 1 + (avoid != -1)) return -1;
258                } while (j == avoid || lists[j].empty);
259                local_pick.success++;
260                return j;
261        }
262
263private:
264
265        struct queue_guard {
266                intrusive_queue_t * lists;
267                int i, j;
268
269                queue_guard(intrusive_queue_t * lists, int i, int j)
270                        : lists(lists), i(i), j(j)
271                {
272                        if(i >= 0) lists[i].lock.lock();
273                        if(j >= 0) lists[j].lock.lock();
274                }
275
276                queue_guard(const queue_guard &) = delete;
277                queue_guard(queue_guard &&) = default;
278
279                ~queue_guard() {
280                        if(i >= 0) lists[i].lock.unlock();
281                        if(j >= 0) lists[j].lock.unlock();
282                }
283        };
284
285        auto lock(int i, int j) {
286                assert(i >= 0);
287                assert(i != j);
288                if(j < i) return queue_guard(lists.get(), j, i);
289                return queue_guard(lists.get(), i, j);
290        }
291
292        intrusive_queue_t & best(int i, int j) {
293                assert(i != -1);
294                if(j == -1) return lists[i];
295                return intrusive_queue_t::best(lists[i], lists[j]);
296        }
297
298        intrusive_queue_t & best2(int i, int j) {
299                assert(i != -1);
300                if(j == -1) return lists[i];
301                return intrusive_queue_t::best2(lists[i], lists[j]);
302        }
303};
Note: See TracBrowser for help on using the repository browser.