source: doc/theses/thierry_delisle_PhD/code/snzm.hpp @ 47a541d

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

Add first draft of SNZI + MASK approach

  • Property mode set to 100644
File size: 3.9 KB
Line 
1#pragma once
2
3#include "utils.hpp"
4
5
6class snzm_t {
7        class node;
8public:
9        const unsigned depth;
10        const unsigned mask;
11        const int root;
12        std::unique_ptr<snzm_t::node[]> nodes;
13
14        snzm_t(unsigned numLists);
15
16        void arrive(int idx) {
17                int i = idx & mask;
18                nodes[i].arrive( idx >> depth);
19        }
20
21        void depart(int idx) {
22                int i = idx & mask;
23                nodes[i].depart( idx >> depth );
24        }
25
26        bool query() const {
27                return nodes[root].query();
28        }
29
30        size_t masks( unsigned node ) {
31                /* paranoid */ assert( (node & mask) == node );
32                return nodes[node].mask;
33        }
34
35private:
36        class __attribute__((aligned(64))) node {
37                friend class snzm_t;
38        private:
39
40                union val_t {
41                        static constexpr char Half = -1;
42
43                        uint64_t _all;
44                        struct __attribute__((packed)) {
45                                char cnt;
46                                uint64_t ver:56;
47                        };
48
49                        bool cas(val_t & exp, char _cnt, uint64_t _ver) volatile {
50                                val_t t;
51                                t.ver = _ver;
52                                t.cnt = _cnt;
53                                /* paranoid */ assert(t._all == ((_ver << 8) | ((unsigned char)_cnt)));
54                                return __atomic_compare_exchange_n(&this->_all, &exp._all, t._all, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
55                        }
56
57                        bool cas(val_t & exp, const val_t & tar) volatile {
58                                return __atomic_compare_exchange_n(&this->_all, &exp._all, tar._all, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
59                        }
60
61                        val_t() : _all(0) {}
62                        val_t(const volatile val_t & o) : _all(o._all) {}
63                };
64
65                //--------------------------------------------------
66                // Hierarchical node
67                void arrive_h() {
68                        int undoArr = 0;
69                        bool success = false;
70                        while(!success) {
71                                auto x{ value };
72                                /* paranoid */ assert(x.cnt <= 120);
73                                if( x.cnt >= 1 ) {
74                                        if( value.cas(x, x.cnt + 1, x.ver ) ) {
75                                                success = true;
76                                        }
77                                }
78                                /* paranoid */ assert(x.cnt <= 120);
79                                if( x.cnt == 0 ) {
80                                        if( value.cas(x, val_t::Half, x.ver + 1) ) {
81                                                success = true;
82                                                x.cnt = val_t::Half;
83                                                x.ver = x.ver + 1;
84                                        }
85                                }
86                                /* paranoid */ assert(x.cnt <= 120);
87                                if( x.cnt == val_t::Half ) {
88                                        /* paranoid */ assert(parent);
89                                        parent->arrive();
90                                        if( !value.cas(x, 1, x.ver) ) {
91                                                undoArr = undoArr + 1;
92                                        }
93                                }
94                        }
95
96                        for(int i = 0; i < undoArr; i++) {
97                                /* paranoid */ assert(parent);
98                                parent->depart();
99                        }
100                }
101
102                void depart_h() {
103                        while(true) {
104                                auto x = (const val_t)value;
105                                /* paranoid */ assertf(x.cnt >= 1, "%d", x.cnt);
106                                if( value.cas( x, x.cnt - 1, x.ver ) ) {
107                                        if( x.cnt == 1 ) {
108                                                /* paranoid */ assert(parent);
109                                                parent->depart();
110                                        }
111                                        return;
112                                }
113                        }
114                }
115
116                //--------------------------------------------------
117                // Root node
118                void arrive_r() {
119                        __atomic_fetch_add(&value._all, 1, __ATOMIC_SEQ_CST);
120                }
121
122                void depart_r() {
123                        __atomic_fetch_sub(&value._all, 1, __ATOMIC_SEQ_CST);
124                }
125
126                //--------------------------------------------------
127                // Interface node
128                void arrive() {
129                        /* paranoid */ assert(!is_leaf);
130                        if(is_root()) arrive_r();
131                        else arrive_h();
132                }
133
134                void depart() {
135                        /* paranoid */ assert(!is_leaf);
136                        if(is_root()) depart_r();
137                        else depart_h();
138                }
139
140        private:
141                volatile val_t value;
142                volatile size_t mask = 0;
143                class node * parent = nullptr;
144                bool is_leaf = false;
145
146                bool is_root() {
147                        return parent == nullptr;
148                }
149
150        public:
151                void arrive( int bit ) {
152                        /* paranoid */ assert( is_leaf );
153                        /* paranoid */ assert( (mask & ( 1 << bit )) == 0 );
154
155                        __atomic_fetch_add( &mask, 1 << bit, __ATOMIC_RELAXED );
156                        arrive_h();
157
158                }
159
160                void depart( int bit ) {
161                        /* paranoid */ assert( is_leaf );
162                        /* paranoid */ assert( (mask & ( 1 << bit )) != 0 );
163
164                        depart_h();
165                        __atomic_fetch_sub( &mask, 1 << bit, __ATOMIC_RELAXED );
166                }
167
168                bool query() {
169                        /* paranoid */ assert(is_root());
170                        return value._all > 0;
171                }
172        };
173};
174
175snzm_t::snzm_t(unsigned numLists)
176        : depth( std::log2( numLists / 8 ) )
177        , mask( (1 << depth) - 1 )
178        , root( (1 << (depth + 1)) - 2 )
179        , nodes(new node[ root + 1 ]())
180{
181        int width = 1 << depth;
182        for(int i = 0; i < root; i++) {
183                nodes[i].is_leaf = i < width;
184                nodes[i].parent = &nodes[(i / 2) + width ];
185        }
186}
Note: See TracBrowser for help on using the repository browser.