source: doc/theses/thierry_delisle_PhD/code/readyQ_proto/snzi-packed.hpp @ d0cd933

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

Moved phd code for the readQ prototype to it's own folder

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