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

ADTast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since ef94ae7 was ef94ae7, checked in by Thierry Delisle <tdelisle@…>, 3 years ago

Changed ready-queue to use -1 for empty ts.

  • Property mode set to 100644
File size: 4.4 KB
Line 
1#pragma once
2
3#define __CFA_NO_SCHED_STATS__
4
5#include "containers/queueLockFree.hfa"
6
7// Intrusives lanes which are used by the relaxed ready queue
8struct __attribute__((aligned(128))) __intrusive_lane_t {
9        struct $thread * prev;
10
11        // spin lock protecting the queue
12        volatile bool lock;
13
14        __thread_desc_link anchor;
15
16        #if !defined(__CFA_NO_STATISTICS__)
17                unsigned cnt;
18        #endif
19};
20
21// Get the head pointer (one before the first element) from the anchor
22static inline $thread * mock_head(const __intrusive_lane_t & this) {
23        $thread * rhead = ($thread *)(
24                (uintptr_t)( &this.anchor ) - __builtin_offsetof( $thread, link )
25        );
26        return rhead;
27}
28
29// Ctor
30void ?{}( __intrusive_lane_t & this ) {
31        this.lock = false;
32        this.prev = mock_head(this);
33        this.anchor.next = 0p;
34        this.anchor.ts   = -1llu;
35        #if !defined(__CFA_NO_STATISTICS__)
36                this.cnt  = 0;
37        #endif
38
39        // We add a boat-load of assertions here because the anchor code is very fragile
40        /* paranoid */ _Static_assert( offsetof( $thread, link ) == offsetof(__intrusive_lane_t, anchor) );
41        /* paranoid */ verify( offsetof( $thread, link ) == offsetof(__intrusive_lane_t, anchor) );
42        /* paranoid */ verify( ((uintptr_t)( mock_head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.anchor) );
43        /* paranoid */ verify( &mock_head(this)->link.next == &this.anchor.next );
44        /* paranoid */ verify( &mock_head(this)->link.ts   == &this.anchor.ts   );
45        /* paranoid */ verify( mock_head(this)->link.next == 0p );
46        /* paranoid */ verify( mock_head(this)->link.ts   == -1llu  );
47        /* paranoid */ verify( mock_head(this) == this.prev );
48        /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 );
49        /* paranoid */ verify( __alignof__(this) == 128 );
50        /* paranoid */ verifyf( ((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128) );
51}
52
53// Dtor is trivial
54void ^?{}( __intrusive_lane_t & this ) {
55        // Make sure the list is empty
56        /* paranoid */ verify( this.anchor.next == 0p );
57        /* paranoid */ verify( this.anchor.ts   == -1llu );
58        /* paranoid */ verify( mock_head(this)  == this.prev );
59}
60
61// Push a thread onto this lane
62// returns true of lane was empty before push, false otherwise
63static inline void push( __intrusive_lane_t & this, $thread * node ) {
64        /* paranoid */ verify( this.lock );
65        /* paranoid */ verify( node->link.next == 0p );
66        /* paranoid */ verify( node->link.ts   == -1llu  );
67        /* paranoid */ verify( this.prev->link.next == 0p );
68        /* paranoid */ verify( this.prev->link.ts   == -1llu  );
69        if( this.anchor.next == 0p ) {
70                /* paranoid */ verify( this.anchor.next == 0p );
71                /* paranoid */ verify( this.anchor.ts   == -1llu );
72                /* paranoid */ verify( this.anchor.ts   != 0  );
73                /* paranoid */ verify( this.prev == mock_head( this ) );
74        } else {
75                /* paranoid */ verify( this.anchor.next != 0p );
76                /* paranoid */ verify( this.anchor.ts   != -1llu );
77                /* paranoid */ verify( this.anchor.ts   != 0  );
78                /* paranoid */ verify( this.prev != mock_head( this ) );
79        }
80
81        // Get the relevant nodes locally
82        this.prev->link.next = node;
83        this.prev->link.ts   = rdtscl();
84        this.prev = node;
85        #if !defined(__CFA_NO_STATISTICS__)
86                this.cnt++;
87        #endif
88}
89
90// Pop a thread from this lane (must be non-empty)
91// returns popped
92// returns true of lane was empty before push, false otherwise
93static inline [* $thread, unsigned long long] pop( __intrusive_lane_t & this ) {
94        /* paranoid */ verify( this.lock );
95        /* paranoid */ verify( this.anchor.next != 0p );
96        /* paranoid */ verify( this.anchor.ts   != -1llu );
97        /* paranoid */ verify( this.anchor.ts   != 0  );
98
99        // Get the relevant nodes locally
100        unsigned long long ts = this.anchor.ts;
101        $thread * node = this.anchor.next;
102        this.anchor.next = node->link.next;
103        this.anchor.ts   = node->link.ts;
104        bool is_empty = this.anchor.next == 0p;
105        node->link.next = 0p;
106        node->link.ts   = -1llu;
107        #if !defined(__CFA_NO_STATISTICS__)
108                this.cnt--;
109        #endif
110
111        // Update head time stamp
112        if(is_empty) this.prev = mock_head( this );
113
114        /* paranoid */ verify( node->link.next == 0p );
115        /* paranoid */ verify( node->link.ts   == -1llu  );
116        /* paranoid */ verify( node->link.ts   != 0  );
117        /* paranoid */ verify( this.anchor.ts  != 0  );
118        return [node, ts];
119}
120
121// Check whether or not list is empty
122static inline bool is_empty(__intrusive_lane_t & this) {
123        return this.anchor.next == 0p;
124}
125
126// Return the timestamp
127static inline unsigned long long ts(__intrusive_lane_t & this) {
128        // Cannot verify here since it may not be locked
129        /* paranoid */ verify(this.anchor.ts != 0);
130        return this.anchor.ts;
131}
Note: See TracBrowser for help on using the repository browser.