Changeset 7a2972b9


Ignore:
Timestamp:
Apr 1, 2021, 9:02:57 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
7ee3c87
Parents:
c426b03
Message:

ready queue can now toggle between

  • lock-based queue
  • mpsc_queue a.k.a. nemesis queue

slightly messy implementation, some clean up needed.

Location:
libcfa/src/concurrency
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/concurrency/ready_queue.cfa

    rc426b03 r7a2972b9  
    1818
    1919// #define USE_SNZI
     20// #define USE_MPSC
    2021
    2122#include "bits/defs.hfa"
    … …  
    284285                #endif
    285286
     287        #if defined(USE_MPSC)
     288                // mpsc always succeeds
     289        } while( false );
     290        #else
    286291                // If we can't lock it retry
    287292        } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
     293        #endif
    288294
    289295        // Actually push it
    … …  
    305311        #endif
    306312
    307         // Unlock and return
    308         __atomic_unlock( &lanes.data[i].lock );
     313        #if !defined(USE_MPSC)
     314                // Unlock and return
     315                __atomic_unlock( &lanes.data[i].lock );
     316        #endif
    309317
    310318        // Mark the current index in the tls rng instance as having an item
    … …  
    493501
    494502static void check( __ready_queue_t & q ) with (q) {
    495         #if defined(__CFA_WITH_VERIFY__)
     503        #if defined(__CFA_WITH_VERIFY__) && !defined(USE_MPSC)
    496504                {
    497505                        for( idx ; lanes.count ) {
    … …  
    504512                                assert(tail(sl)->link.prev->link.next == tail(sl) );
    505513
    506                                 if(sl.before.link.ts == 0l) {
     514                                if(is_empty(sl)) {
    507515                                        assert(tail(sl)->link.prev == head(sl));
    508516                                        assert(head(sl)->link.next == tail(sl));
    … …  
    519527// fixes the list so that the pointers back to anchors aren't left dangling
    520528static inline void fix(__intrusive_lane_t & ll) {
    521         // if the list is not empty then follow he pointer and fix its reverse
    522         if(!is_empty(ll)) {
    523                 head(ll)->link.next->link.prev = head(ll);
    524                 tail(ll)->link.prev->link.next = tail(ll);
    525         }
    526         // Otherwise just reset the list
    527         else {
    528                 verify(tail(ll)->link.next == 0p);
    529                 tail(ll)->link.prev = head(ll);
    530                 head(ll)->link.next = tail(ll);
    531                 verify(head(ll)->link.prev == 0p);
    532         }
     529        #if !defined(USE_MPSC)
     530                // if the list is not empty then follow he pointer and fix its reverse
     531                if(!is_empty(ll)) {
     532                        head(ll)->link.next->link.prev = head(ll);
     533                        tail(ll)->link.prev->link.next = tail(ll);
     534                }
     535                // Otherwise just reset the list
     536                else {
     537                        verify(tail(ll)->link.next == 0p);
     538                        tail(ll)->link.prev = head(ll);
     539                        head(ll)->link.next = tail(ll);
     540                        verify(head(ll)->link.prev == 0p);
     541                }
     542        #endif
    533543}
    534544

  • libcfa/src/concurrency/ready_subqueue.hfa

    rc426b03 r7a2972b9  
    22
    33#define __CFA_NO_SCHED_STATS__
     4
     5#include "containers/queueLockFree.hfa"
    46
    57// Intrusives lanes which are used by the relaxed ready queue
    68struct __attribute__((aligned(128))) __intrusive_lane_t {
    79
    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;
     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
    1522
    1623        // spin lock protecting the queue
    … …  
    3542// Get the head pointer (one before the first element) from the anchor
    3643static 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;
     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
    4253}
    4354
    4455// Get the tail pointer (one after the last element) from the anchor
    4556static 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;
     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
    5166}
    5267
    … …  
    5570        this.lock = false;
    5671
    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));
     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
    85102}
    86103
    87104// Dtor is trivial
    88105void ^?{}( __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) );
     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
    94113}
    95114
    … …  
    97116// returns true of lane was empty before push, false otherwise
    98117bool 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 
     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
    107160                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;
     161                        this.before.link.ts = node->link.ts;
     162                        /* paranoid */ verify(node->link.prev == head(this));
     163                        return true;
     164                }
     165                return false;
     166        #endif
    141167}
    142168
    … …  
    146172$thread * pop(__intrusive_lane_t & this) {
    147173        /* 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 = 0p;
    165         node->link.prev = 0p;
    166 
    167         // Update head time stamp
    168         this.before.link.ts = next->link.ts;
    169 
    170         // Update stats
    171         #ifndef __CFA_NO_SCHED_STATS__
    172                 this.stat.diff--;
    173                 this.stat.pop ++;
    174         #endif
    175 
    176         // Check if we emptied list and return accordingly
    177         /* paranoid */ verify(tail(this)->link.next == 0p);
    178         /* paranoid */ verify(head(this)->link.prev == 0p);
    179         if(next == tail) {
    180                 /* paranoid */ verify(this.before.link.ts == 0);
    181                 /* paranoid */ verify(tail(this)->link.prev == head(this));
    182                 /* paranoid */ verify(head(this)->link.next == tail(this));
    183                 return node;
    184         }
    185         else {
    186                 /* paranoid */ verify(next->link.ts != 0);
    187                 /* paranoid */ verify(tail(this)->link.prev != head(this));
    188                 /* paranoid */ verify(head(this)->link.next != tail(this));
    189                 /* paranoid */ verify(this.before.link.ts != 0);
    190                 return node;
    191         }
     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
    192225}
    193226
    194227// Check whether or not list is empty
    195228static inline bool is_empty(__intrusive_lane_t & this) {
    196         // Cannot verify here since it may not be locked
    197         return this.before.link.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
    198235}
    199236
    200237// Return the timestamp
    201238static inline unsigned long long ts(__intrusive_lane_t & this) {
    202         // Cannot verify here since it may not be locked
    203         return this.before.link.ts;
    204 }
     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}
Note: See TracChangeset for help on using the changeset viewer.