source: doc/theses/thierry_delisle_PhD/code/snzm.hpp @ 0aec496

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 0aec496 was 8c60d59, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Fixed alignment of both SNZI and SNZM.
Fixed SNZM with bmi2

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