source: libcfa/src/concurrency/ready_subqueue.hfa @ a77257be

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

Removed code broken in new-ast out of libcfa

  • Property mode set to 100644
File size: 6.1 KB
Line 
1#pragma once
2
3#define __CFA_NO_SCHED_STATS__
4
5// Intrusives lanes which are used by the relaxed ready queue
6struct __attribute__((aligned(128))) __intrusive_lane_t {
7
8        // anchor for the head and the tail of the queue
9        __attribute__((aligned(128))) struct __sentinel_t {
10                // Link lists fields
11                // instrusive link field for threads
12                // must be exactly as in $thread
13                __thread_desc_link link;
14        } before, after;
15
16        // spin lock protecting the queue
17        volatile bool lock;
18
19        // Optional statistic counters
20        #if !defined(__CFA_NO_SCHED_STATS__)
21                struct __attribute__((aligned(64))) {
22                        // difference between number of push and pops
23                        ssize_t diff;
24
25                        // total number of pushes and pops
26                        size_t  push;
27                        size_t  pop ;
28                } stat;
29        #endif
30};
31
32void  ?{}(__intrusive_lane_t & this);
33void ^?{}(__intrusive_lane_t & this);
34
35// Get the head pointer (one before the first element) from the anchor
36static inline $thread * head(const __intrusive_lane_t & this) {
37        $thread * rhead = ($thread *)(
38                (uintptr_t)( &this.before ) - offsetof( $thread, link )
39        );
40        /* paranoid */ verify(rhead);
41        return rhead;
42}
43
44// Get the tail pointer (one after the last element) from the anchor
45static inline $thread * tail(const __intrusive_lane_t & this) {
46        $thread * rtail = ($thread *)(
47                (uintptr_t)( &this.after ) - offsetof( $thread, link )
48        );
49        /* paranoid */ verify(rtail);
50        return rtail;
51}
52
53// Ctor
54void ?{}( __intrusive_lane_t & this ) {
55        this.lock = false;
56
57        this.before.link.prev = 0p;
58        this.before.link.next = tail(this);
59        this.before.link.ts   = 0;
60
61        this.after .link.prev = head(this);
62        this.after .link.next = 0p;
63        this.after .link.ts   = 0;
64
65        #if !defined(__CFA_NO_SCHED_STATS__)
66                this.stat.diff = 0;
67                this.stat.push = 0;
68                this.stat.pop  = 0;
69        #endif
70
71        // We add a boat-load of assertions here because the anchor code is very fragile
72        /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
73        /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
74        /* paranoid */ verify(head(this)->link.prev == 0p );
75        /* paranoid */ verify(head(this)->link.next == tail(this) );
76        /* paranoid */ verify(tail(this)->link.next == 0p );
77        /* paranoid */ verify(tail(this)->link.prev == head(this) );
78        /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
79        /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
80        /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
81        /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
82        /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
83        /* paranoid */ verify(__alignof__(this) == 128);
84        /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
85}
86
87// Dtor is trivial
88void ^?{}( __intrusive_lane_t & this ) {
89        // Make sure the list is empty
90        /* paranoid */ verify(head(this)->link.prev == 0p );
91        /* paranoid */ verify(head(this)->link.next == tail(this) );
92        /* paranoid */ verify(tail(this)->link.next == 0p );
93        /* paranoid */ verify(tail(this)->link.prev == head(this) );
94}
95
96// Push a thread onto this lane
97// returns true of lane was empty before push, false otherwise
98bool push(__intrusive_lane_t & this, $thread * node) {
99        #if defined(__CFA_WITH_VERIFY__)
100                /* paranoid */ verify(this.lock);
101                /* paranoid */ verify(node->link.ts != 0);
102                /* paranoid */ verify(node->link.next == 0p);
103                /* paranoid */ verify(node->link.prev == 0p);
104                /* paranoid */ verify(tail(this)->link.next == 0p);
105                /* paranoid */ verify(head(this)->link.prev == 0p);
106
107                if(this.before.link.ts == 0l) {
108                        /* paranoid */ verify(tail(this)->link.prev == head(this));
109                        /* paranoid */ verify(head(this)->link.next == tail(this));
110                } else {
111                        /* paranoid */ verify(tail(this)->link.prev != head(this));
112                        /* paranoid */ verify(head(this)->link.next != tail(this));
113                }
114        #endif
115
116        // Get the relevant nodes locally
117        $thread * tail = tail(this);
118        $thread * prev = tail->link.prev;
119
120        // Do the push
121        node->link.next = tail;
122        node->link.prev = prev;
123        prev->link.next = node;
124        tail->link.prev = node;
125
126        // Update stats
127        #if !defined(__CFA_NO_SCHED_STATS__)
128                this.stat.diff++;
129                this.stat.push++;
130        #endif
131
132        verify(node->link.next == tail(this));
133
134        // Check if the queue used to be empty
135        if(this.before.link.ts == 0l) {
136                this.before.link.ts = node->link.ts;
137                /* paranoid */ verify(node->link.prev == head(this));
138                return true;
139        }
140        return false;
141}
142
143// Pop a thread from this lane (must be non-empty)
144// returns popped
145// returns true of lane was empty before push, false otherwise
146$thread * pop(__intrusive_lane_t & this) {
147        /* paranoid */ verify(this.lock);
148        /* paranoid */ verify(this.before.link.ts != 0ul);
149
150        // Get anchors locally
151        $thread * head = head(this);
152        $thread * tail = tail(this);
153
154        // Get the relevant nodes locally
155        $thread * node = head->link.next;
156        $thread * next = node->link.next;
157
158        /* paranoid */ verify(node != tail);
159        /* paranoid */ verify(node);
160
161        // Do the pop
162        head->link.next = next;
163        next->link.prev = head;
164        node->link.next = 0p;
165        node->link.prev = 0p;
166
167        // Update head time stamp
168        this.before.link.ts = next->link.ts;
169
170        // Update stats
171        #ifndef __CFA_NO_SCHED_STATS__
172                this.stat.diff--;
173                this.stat.pop ++;
174        #endif
175
176        // Check if we emptied list and return accordingly
177        /* paranoid */ verify(tail(this)->link.next == 0p);
178        /* paranoid */ verify(head(this)->link.prev == 0p);
179        if(next == tail) {
180                /* paranoid */ verify(this.before.link.ts == 0);
181                /* paranoid */ verify(tail(this)->link.prev == head(this));
182                /* paranoid */ verify(head(this)->link.next == tail(this));
183                return node;
184        }
185        else {
186                /* paranoid */ verify(next->link.ts != 0);
187                /* paranoid */ verify(tail(this)->link.prev != head(this));
188                /* paranoid */ verify(head(this)->link.next != tail(this));
189                /* paranoid */ verify(this.before.link.ts != 0);
190                return node;
191        }
192}
193
194// Check whether or not list is empty
195static inline bool is_empty(__intrusive_lane_t & this) {
196        // Cannot verify here since it may not be locked
197        return this.before.link.ts == 0;
198}
199
200// Return the timestamp
201static inline unsigned long long ts(__intrusive_lane_t & this) {
202        // Cannot verify here since it may not be locked
203        return this.before.link.ts;
204}
Note: See TracBrowser for help on using the repository browser.