source: doc/theses/thierry_delisle_PhD/code/readyQ_proto/snzi.hpp @ f9f3775

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

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

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