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

ADT ast-experimental pthread-emulation qualifiedEnum
Last change on this file since e5d9274 was 5024df4, checked in by Thierry Delisle <tdelisle@…>, 3 years ago

Changed ready-queue to atomically read/write timestamps, no effect on x64. + whitespace

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