source: libcfa/src/concurrency/ready_subqueue.hfa @ 0d070ca

arm-ehjacob/cs343-translationnew-astnew-ast-unique-expr
Last change on this file since 0d070ca was 13c5e19, checked in by Thierry Delisle <tdelisle@…>, 16 months ago
  • Moved snzi and subqueues outside of ready_queue.cfa.
  • Added random.hfa with multiple prng.
  • Minor optimizations to ready-queue
  • Stats now track number of local pops( bias pops )
  • Fixed stats for io
  • Fixed calculaton of nprocessors
  • Fixed IO to work with new ready-queue
  • 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 *, bool] 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, prev] = 0p;
165
166        // Update head time stamp
167        this.before.link.ts = next->link.ts;
168
169        // Update stats
170        #ifndef __CFA_NO_SCHED_STATS__
171                this.stat.diff--;
172                this.stat.pop ++;
173        #endif
174
175        // Check if we emptied list and return accordingly
176        /* paranoid */ verify(tail(this)->link.next == 0p);
177        /* paranoid */ verify(head(this)->link.prev == 0p);
178        if(next == tail) {
179                /* paranoid */ verify(this.before.link.ts == 0);
180                /* paranoid */ verify(tail(this)->link.prev == head(this));
181                /* paranoid */ verify(head(this)->link.next == tail(this));
182                return [node, true];
183        }
184        else {
185                /* paranoid */ verify(next->link.ts != 0);
186                /* paranoid */ verify(tail(this)->link.prev != head(this));
187                /* paranoid */ verify(head(this)->link.next != tail(this));
188                /* paranoid */ verify(this.before.link.ts != 0);
189                return [node, false];
190        }
191}
192
193// Check whether or not list is empty
194static inline bool is_empty(__intrusive_lane_t & this) {
195        // Cannot verify here since it may not be locked
196        return this.before.link.ts == 0;
197}
198
199// Return the timestamp
200static inline unsigned long long ts(__intrusive_lane_t & this) {
201        // Cannot verify here since it may not be locked
202        return this.before.link.ts;
203}
Note: See TracBrowser for help on using the repository browser.