source: libcfa/src/concurrency/snzi.hfa @ 1d17939

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

Changed ready_queue_(grow/shrink) to take a target instead of going incrementing

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