source: libcfa/src/concurrency/ready_subqueue.hfa

Last change on this file was 15c93d8, checked in by Thierry Delisle <tdelisle@…>, 6 weeks ago

Renamed ready-queue link fields to rdy_link

  • Property mode set to 100644
File size: 3.8 KB
Line 
1#pragma once
2
3#define __CFA_NO_SCHED_STATS__
4
5#include "limits.hfa"
6
7// Intrusives lanes which are used by the relaxed ready queue
8union __attribute__((aligned(64))) __intrusive_lane_t {
9        struct {
10                struct thread$ * prev;
11
12                // spin lock protecting the queue
13                volatile bool lock;
14
15                __thread_desc_link anchor;
16
17                #if !defined(__CFA_NO_STATISTICS__)
18                        unsigned cnt;
19                #endif
20        } l;
21        char __padding[192];
22};
23
24// Get the head pointer (one before the first element) from the anchor
25static inline thread$ * mock_head(const __intrusive_lane_t & this) {
26        thread$ * rhead = (thread$ *)(
27                (uintptr_t)( &this.l.anchor ) - __builtin_offsetof( thread$, rdy_link )
28        );
29        return rhead;
30}
31
32// Push a thread onto this lane
33// returns true of lane was empty before push, false otherwise
34static inline void push( __intrusive_lane_t & this, thread$ * node ) {
35        /* paranoid */ verify( this.l.lock );
36        /* paranoid */ verify( node->rdy_link.next == 0p );
37        /* paranoid */ verify( __atomic_load_n(&node->rdy_link.ts, __ATOMIC_RELAXED) == MAX  );
38        /* paranoid */ verify( this.l.prev->rdy_link.next == 0p );
39        /* paranoid */ verify( __atomic_load_n(&this.l.prev->rdy_link.ts, __ATOMIC_RELAXED)   == MAX  );
40        if( this.l.anchor.next == 0p ) {
41                /* paranoid */ verify( this.l.anchor.next == 0p );
42                /* paranoid */ verify( __atomic_load_n(&this.l.anchor.ts, __ATOMIC_RELAXED) == MAX );
43                /* paranoid */ verify( __atomic_load_n(&this.l.anchor.ts, __ATOMIC_RELAXED) != 0  );
44                /* paranoid */ verify( this.l.prev == mock_head( this ) );
45        } else {
46                /* paranoid */ verify( this.l.anchor.next != 0p );
47                /* paranoid */ verify( __atomic_load_n(&this.l.anchor.ts, __ATOMIC_RELAXED) != MAX );
48                /* paranoid */ verify( __atomic_load_n(&this.l.anchor.ts, __ATOMIC_RELAXED) != 0  );
49                /* paranoid */ verify( this.l.prev != mock_head( this ) );
50        }
51
52        // Get the relevant nodes locally
53        this.l.prev->rdy_link.next = node;
54        __atomic_store_n(&this.l.prev->rdy_link.ts, rdtscl(), __ATOMIC_RELAXED);
55        this.l.prev = node;
56        #if !defined(__CFA_NO_STATISTICS__)
57                this.l.cnt++;
58        #endif
59}
60
61// Pop a thread from this lane (must be non-empty)
62// returns popped
63// returns true of lane was empty before push, false otherwise
64static inline [* thread$, unsigned long long] pop( __intrusive_lane_t & this ) {
65        /* paranoid */ verify( this.l.lock );
66        /* paranoid */ verify( this.l.anchor.next != 0p );
67        /* paranoid */ verify( __atomic_load_n(&this.l.anchor.ts, __ATOMIC_RELAXED) != MAX );
68        /* paranoid */ verify( __atomic_load_n(&this.l.anchor.ts, __ATOMIC_RELAXED) != 0   );
69
70        // Get the relevant nodes locally
71        thread$ * node = this.l.anchor.next;
72        this.l.anchor.next = node->rdy_link.next;
73        __atomic_store_n(&this.l.anchor.ts, __atomic_load_n(&node->rdy_link.ts, __ATOMIC_RELAXED), __ATOMIC_RELAXED);
74        bool is_empty = this.l.anchor.next == 0p;
75        node->rdy_link.next = 0p;
76        __atomic_store_n(&node->rdy_link.ts, ULLONG_MAX, __ATOMIC_RELAXED);
77        #if !defined(__CFA_NO_STATISTICS__)
78                this.l.cnt--;
79        #endif
80
81        // Update head time stamp
82        if(is_empty) this.l.prev = mock_head( this );
83
84        unsigned long long ats = __atomic_load_n(&this.l.anchor.ts, __ATOMIC_RELAXED);
85        /* paranoid */ verify( node->rdy_link.next == 0p );
86        /* paranoid */ verify( __atomic_load_n(&node->rdy_link.ts , __ATOMIC_RELAXED) == MAX );
87        /* paranoid */ verify( __atomic_load_n(&node->rdy_link.ts , __ATOMIC_RELAXED) != 0   );
88        /* paranoid */ verify( ats != 0 );
89        /* paranoid */ verify( (ats == MAX) == is_empty );
90        return [node, ats];
91}
92
93// Check whether or not list is empty
94static inline bool is_empty(__intrusive_lane_t & this) {
95        return this.l.anchor.next == 0p;
96}
97
98// Return the timestamp
99static inline unsigned long long ts(__intrusive_lane_t & this) {
100        // Cannot verify 'emptiness' here since it may not be locked
101        /* paranoid */ verify(this.l.anchor.ts != 0);
102        /* paranoid */ static_assert(__atomic_always_lock_free(sizeof(this.l.anchor.ts), &this.l.anchor.ts));
103        return __atomic_load_n(&this.l.anchor.ts, __ATOMIC_RELAXED);
104}
Note: See TracBrowser for help on using the repository browser.