Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/concurrency/ready_subqueue.hfa

    r353aaba r9cc3a18  
    77// Intrusives lanes which are used by the relaxed ready queue
    88struct __attribute__((aligned(128))) __intrusive_lane_t {
    9         struct $thread * prev;
     9
     10        #if defined(USE_MPSC)
     11                mpsc_queue($thread) queue;
     12                __attribute__((aligned(128)))
     13        #else
     14                // anchor for the head and the tail of the queue
     15                __attribute__((aligned(128))) struct __sentinel_t {
     16                        // Link lists fields
     17                        // instrusive link field for threads
     18                        // must be exactly as in $thread
     19                        __thread_desc_link link;
     20                } before, after;
     21        #endif
    1022
    1123        // spin lock protecting the queue
    1224        volatile bool lock;
    1325
    14         __thread_desc_link anchor;
    15 
    16         #if !defined(__CFA_NO_STATISTICS__)
    17                 unsigned cnt;
     26        // Optional statistic counters
     27        #if !defined(__CFA_NO_SCHED_STATS__)
     28                struct __attribute__((aligned(64))) {
     29                        // difference between number of push and pops
     30                        ssize_t diff;
     31
     32                        // total number of pushes and pops
     33                        size_t  push;
     34                        size_t  pop ;
     35                } stat;
    1836        #endif
    1937};
    2038
     39void  ?{}(__intrusive_lane_t & this);
     40void ^?{}(__intrusive_lane_t & this);
     41
    2142// Get the head pointer (one before the first element) from the anchor
    22 static 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;
     43static inline $thread * head(const __intrusive_lane_t & this) {
     44        #if defined(USE_MPSC)
     45                return this.queue.head;
     46        #else
     47                $thread * rhead = ($thread *)(
     48                        (uintptr_t)( &this.before ) - offsetof( $thread, link )
     49                );
     50                /* paranoid */ verify(rhead);
     51                return rhead;
     52        #endif
     53}
     54
     55// Get the tail pointer (one after the last element) from the anchor
     56static inline $thread * tail(const __intrusive_lane_t & this) {
     57        #if defined(USE_MPSC)
     58                return this.queue.tail;
     59        #else
     60                $thread * rtail = ($thread *)(
     61                        (uintptr_t)( &this.after ) - offsetof( $thread, link )
     62                );
     63                /* paranoid */ verify(rtail);
     64                return rtail;
     65        #endif
    2766}
    2867
    … …  
    3069void ?{}( __intrusive_lane_t & this ) {
    3170        this.lock = false;
    32         this.prev = mock_head(this);
    33         this.anchor.next = 0p;
    34         this.anchor.ts   = 0;
    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   == 0  );
    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) );
     71
     72        #if !defined(USE_MPSC)
     73                this.before.link.prev = 0p;
     74                this.before.link.next = tail(this);
     75                this.before.link.ts   = 0;
     76
     77                this.after .link.prev = head(this);
     78                this.after .link.next = 0p;
     79                this.after .link.ts   = 0;
     80
     81                #if !defined(__CFA_NO_SCHED_STATS__)
     82                        this.stat.diff = 0;
     83                        this.stat.push = 0;
     84                        this.stat.pop  = 0;
     85                #endif
     86
     87                // We add a boat-load of assertions here because the anchor code is very fragile
     88                /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
     89                /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
     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                /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
     95                /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
     96                /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
     97                /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
     98                /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
     99                /* paranoid */ verify(__alignof__(this) == 128);
     100                /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
     101        #endif
    51102}
    52103
    53104// Dtor is trivial
    54105void ^?{}( __intrusive_lane_t & this ) {
    55         // Make sure the list is empty
    56         /* paranoid */ verify( this.anchor.next == 0p );
    57         /* paranoid */ verify( this.anchor.ts   == 0  );
    58         /* paranoid */ verify( mock_head(this)  == this.prev );
     106        #if !defined(USE_MPSC)
     107                // Make sure the list is empty
     108                /* paranoid */ verify(head(this)->link.prev == 0p );
     109                /* paranoid */ verify(head(this)->link.next == tail(this) );
     110                /* paranoid */ verify(tail(this)->link.next == 0p );
     111                /* paranoid */ verify(tail(this)->link.prev == head(this) );
     112        #endif
    59113}
    60114
    61115// Push a thread onto this lane
    62116// returns true of lane was empty before push, false otherwise
    63 static 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   == 0  );
    67         /* paranoid */ verify( this.prev->link.next == 0p );
    68         /* paranoid */ verify( this.prev->link.ts   == 0  );
    69         if( this.anchor.next == 0p ) {
    70                 /* paranoid */ verify( this.anchor.next == 0p );
    71                 /* paranoid */ verify( this.anchor.ts   == 0  );
    72                 /* paranoid */ verify( this.prev == mock_head( this ) );
    73         } else {
    74                 /* paranoid */ verify( this.anchor.next != 0p );
    75                 /* paranoid */ verify( this.anchor.ts   != 0  );
    76                 /* paranoid */ verify( this.prev != mock_head( this ) );
    77         }
    78 
    79         // Get the relevant nodes locally
    80         this.prev->link.next = node;
    81         this.prev->link.ts   = rdtscl();
    82         this.prev = node;
    83         #if !defined(__CFA_NO_STATISTICS__)
    84                 this.cnt++;
     117bool push(__intrusive_lane_t & this, $thread * node) {
     118        #if defined(USE_MPSC)
     119                inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
     120                        return this->link.next;
     121                }
     122                push(this.queue, node);
     123        #else
     124                #if defined(__CFA_WITH_VERIFY__)
     125                        /* paranoid */ verify(this.lock);
     126                        /* paranoid */ verify(node->link.ts != 0);
     127                        /* paranoid */ verify(node->link.next == 0p);
     128                        /* paranoid */ verify(node->link.prev == 0p);
     129                        /* paranoid */ verify(tail(this)->link.next == 0p);
     130                        /* paranoid */ verify(head(this)->link.prev == 0p);
     131
     132                        if(this.before.link.ts == 0l) {
     133                                /* paranoid */ verify(tail(this)->link.prev == head(this));
     134                                /* paranoid */ verify(head(this)->link.next == tail(this));
     135                        } else {
     136                                /* paranoid */ verify(tail(this)->link.prev != head(this));
     137                                /* paranoid */ verify(head(this)->link.next != tail(this));
     138                        }
     139                #endif
     140
     141                // Get the relevant nodes locally
     142                $thread * tail = tail(this);
     143                $thread * prev = tail->link.prev;
     144
     145                // Do the push
     146                node->link.next = tail;
     147                node->link.prev = prev;
     148                prev->link.next = node;
     149                tail->link.prev = node;
     150
     151                // Update stats
     152                #if !defined(__CFA_NO_SCHED_STATS__)
     153                        this.stat.diff++;
     154                        this.stat.push++;
     155                #endif
     156
     157                verify(node->link.next == tail(this));
     158
     159                // Check if the queue used to be empty
     160                if(this.before.link.ts == 0l) {
     161                        this.before.link.ts = node->link.ts;
     162                        /* paranoid */ verify(node->link.prev == head(this));
     163                        return true;
     164                }
     165                return false;
    85166        #endif
    86167}
    … …  
    89170// returns popped
    90171// returns true of lane was empty before push, false otherwise
    91 static inline [* $thread, unsigned long long] pop( __intrusive_lane_t & this ) {
    92         /* paranoid */ verify( this.lock );
    93         /* paranoid */ verify( this.anchor.next != 0p );
    94         /* paranoid */ verify( this.anchor.ts   != 0  );
    95 
    96         // Get the relevant nodes locally
    97         unsigned long long ts = this.anchor.ts;
    98         $thread * node = this.anchor.next;
    99         this.anchor.next = node->link.next;
    100         this.anchor.ts   = node->link.ts;
    101         bool is_empty = this.anchor.ts == 0;
    102         node->link.next = 0p;
    103         node->link.ts   = 0;
    104         #if !defined(__CFA_NO_STATISTICS__)
    105                 this.cnt--;
    106         #endif
    107 
    108         // Update head time stamp
    109         if(is_empty) this.prev = mock_head( this );
    110 
    111         /* paranoid */ verify( node->link.next == 0p );
    112         /* paranoid */ verify( node->link.ts   == 0  );
    113         return [node, ts];
     172$thread * pop(__intrusive_lane_t & this) {
     173        /* paranoid */ verify(this.lock);
     174        #if defined(USE_MPSC)
     175                inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
     176                        return this->link.next;
     177                }
     178                return pop(this.queue);
     179        #else
     180                /* paranoid */ verify(this.before.link.ts != 0ul);
     181
     182                // Get anchors locally
     183                $thread * head = head(this);
     184                $thread * tail = tail(this);
     185
     186                // Get the relevant nodes locally
     187                $thread * node = head->link.next;
     188                $thread * next = node->link.next;
     189
     190                /* paranoid */ verify(node != tail);
     191                /* paranoid */ verify(node);
     192
     193                // Do the pop
     194                head->link.next = next;
     195                next->link.prev = head;
     196                node->link.next = 0p;
     197                node->link.prev = 0p;
     198
     199                // Update head time stamp
     200                this.before.link.ts = next->link.ts;
     201
     202                // Update stats
     203                #ifndef __CFA_NO_SCHED_STATS__
     204                        this.stat.diff--;
     205                        this.stat.pop ++;
     206                #endif
     207
     208                // Check if we emptied list and return accordingly
     209                /* paranoid */ verify(tail(this)->link.next == 0p);
     210                /* paranoid */ verify(head(this)->link.prev == 0p);
     211                if(next == tail) {
     212                        /* paranoid */ verify(this.before.link.ts == 0);
     213                        /* paranoid */ verify(tail(this)->link.prev == head(this));
     214                        /* paranoid */ verify(head(this)->link.next == tail(this));
     215                        return node;
     216                }
     217                else {
     218                        /* paranoid */ verify(next->link.ts != 0);
     219                        /* paranoid */ verify(tail(this)->link.prev != head(this));
     220                        /* paranoid */ verify(head(this)->link.next != tail(this));
     221                        /* paranoid */ verify(this.before.link.ts != 0);
     222                        return node;
     223                }
     224        #endif
    114225}
    115226
    116227// Check whether or not list is empty
    117228static inline bool is_empty(__intrusive_lane_t & this) {
    118         return this.anchor.ts == 0;
     229        #if defined(USE_MPSC)
     230                return this.queue.head == 0p;
     231        #else
     232                // Cannot verify here since it may not be locked
     233                return this.before.link.ts == 0;
     234        #endif
    119235}
    120236
    121237// Return the timestamp
    122238static inline unsigned long long ts(__intrusive_lane_t & this) {
    123         // Cannot verify here since it may not be locked
    124         return this.anchor.ts;
    125 }
     239        #if defined(USE_MPSC)
     240                $thread * tl = this.queue.head;
     241                if(!tl) return -1ull;
     242                return tl->link.ts;
     243        #else
     244                // Cannot verify here since it may not be locked
     245                return this.before.link.ts;
     246        #endif
     247}
     248
     249// Aligned timestamps which are used by the relaxed ready queue
     250struct __attribute__((aligned(128))) __timestamp_t {
     251        volatile unsigned long long tv;
     252};
     253
     254void  ?{}(__timestamp_t & this) { this.tv = 0; }
     255void ^?{}(__timestamp_t & this) {}
Note: See TracChangeset for help on using the changeset viewer.