Changeset f6fdfb14


Ignore:
Timestamp:
May 3, 2021, 4:31:15 PM (2 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
eeb9f9f
Parents:
f04a3df6
Message:

Removed old sub-queue

Location:
libcfa/src/concurrency
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/concurrency/invoke.h

    rf04a3df6 rf6fdfb14  
    146146        struct __thread_desc_link {
    147147                struct $thread * next;
    148                 struct $thread * prev;
    149148                volatile unsigned long long ts;
    150                 unsigned preferred;
    151149        };
    152150

  • libcfa/src/concurrency/kernel/startup.cfa

    rf04a3df6 rf6fdfb14  
    461461        self_mon_p = &self_mon;
    462462        link.next = 0p;
    463         link.prev = 0p;
    464463        link.ts   = 0;
    465464        link.preferred = -1u;

  • libcfa/src/concurrency/ready_queue.cfa

    rf04a3df6 rf6fdfb14  
    255255                const bool external = (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
    256256                /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
    257 
    258                 // write timestamp
    259                 #if !defined(USE_NEW_SUBQUEUE)
    260                         thrd->link.ts = rdtscl();
    261                 #endif
    262257
    263258                bool local;

  • libcfa/src/concurrency/ready_subqueue.hfa

    rf04a3df6 rf6fdfb14  
    55#include "containers/queueLockFree.hfa"
    66
    7 // #define USE_NEW_SUBQUEUE
    8 #if defined(USE_NEW_SUBQUEUE)
    9         // Intrusives lanes which are used by the relaxed ready queue
    10         struct __attribute__((aligned(128))) __intrusive_lane_t {
    11                 struct $thread * prev;
     7// Intrusives lanes which are used by the relaxed ready queue
     8struct __attribute__((aligned(128))) __intrusive_lane_t {
     9        struct $thread * prev;
    1210
    13                 // spin lock protecting the queue
    14                 volatile bool lock;
     11        // spin lock protecting the queue
     12        volatile bool lock;
    1513
    16                 __thread_desc_link anchor;
    17         };
     14        __thread_desc_link anchor;
     15};
    1816
    19         // Get the head pointer (one before the first element) from the anchor
    20         static inline $thread * mock_head(const __intrusive_lane_t & this) {
    21                 $thread * rhead = ($thread *)(
    22                         (uintptr_t)( &this.anchor ) - __builtin_offsetof( $thread, link )
    23                 );
    24                 return rhead;
     17// Get the head pointer (one before the first element) from the anchor
     18static inline $thread * mock_head(const __intrusive_lane_t & this) {
     19        $thread * rhead = ($thread *)(
     20                (uintptr_t)( &this.anchor ) - __builtin_offsetof( $thread, link )
     21        );
     22        return rhead;
     23}
     24
     25// Ctor
     26void ?{}( __intrusive_lane_t & this ) {
     27        this.lock = false;
     28        this.prev = mock_head(this);
     29        this.anchor.next = 0p;
     30        this.anchor.ts   = 0;
     31
     32        // We add a boat-load of assertions here because the anchor code is very fragile
     33        /* paranoid */ verify( ((uintptr_t)( mock_head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.anchor) );
     34        /* paranoid */ verify( &mock_head(this)->link.next == &this.anchor.next );
     35        /* paranoid */ verify( &mock_head(this)->link.ts   == &this.anchor.ts   );
     36        /* paranoid */ verify( mock_head(this)->link.next == 0p );
     37        /* paranoid */ verify( mock_head(this)->link.ts   == 0  );
     38        /* paranoid */ verify( mock_head(this) == this.prev );
     39        /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 );
     40        /* paranoid */ verify( __alignof__(this) == 128 );
     41        /* paranoid */ verifyf( ((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128) );
     42}
     43
     44// Dtor is trivial
     45void ^?{}( __intrusive_lane_t & this ) {
     46        // Make sure the list is empty
     47        /* paranoid */ verify( this.anchor.next == 0p );
     48        /* paranoid */ verify( this.anchor.ts   == 0  );
     49        /* paranoid */ verify( mock_head(this)  == this.prev );
     50}
     51
     52// Push a thread onto this lane
     53// returns true of lane was empty before push, false otherwise
     54void push( __intrusive_lane_t & this, $thread * node ) {
     55        /* paranoid */ verify( node->link.next == 0p );
     56        /* paranoid */ verify( node->link.ts   == 0  );
     57        /* paranoid */ verify( this.prev->link.next == 0p );
     58        /* paranoid */ verify( this.prev->link.ts   == 0  );
     59        if( this.anchor.next == 0p ) {
     60                /* paranoid */ verify( this.anchor.next == 0p );
     61                /* paranoid */ verify( this.anchor.ts   == 0  );
     62                /* paranoid */ verify( this.prev == mock_head( this ) );
     63        } else {
     64                /* paranoid */ verify( this.anchor.next != 0p );
     65                /* paranoid */ verify( this.anchor.ts   != 0  );
     66                /* paranoid */ verify( this.prev != mock_head( this ) );
    2567        }
    2668
    27         // Ctor
    28         void ?{}( __intrusive_lane_t & this ) {
    29                 this.lock = false;
    30                 this.prev = mock_head(this);
    31                 this.anchor.next = 0p;
    32                 this.anchor.ts   = 0;
     69        // Get the relevant nodes locally
     70        this.prev->link.next = node;
     71        this.prev->link.ts   = rdtscl();
     72        this.prev = node;
     73}
    3374
    34                 // We add a boat-load of assertions here because the anchor code is very fragile
    35                 /* paranoid */ verify( ((uintptr_t)( mock_head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.anchor) );
    36                 /* paranoid */ verify( &mock_head(this)->link.next == &this.anchor.next );
    37                 /* paranoid */ verify( &mock_head(this)->link.ts   == &this.anchor.ts   );
    38                 /* paranoid */ verify( mock_head(this)->link.next == 0p );
    39                 /* paranoid */ verify( mock_head(this)->link.ts   == 0  );
    40                 /* paranoid */ verify( mock_head(this) == this.prev );
    41                 /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 );
    42                 /* paranoid */ verify( __alignof__(this) == 128 );
    43                 /* paranoid */ verifyf( ((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128) );
    44         }
     75// Pop a thread from this lane (must be non-empty)
     76// returns popped
     77// returns true of lane was empty before push, false otherwise
     78$thread * pop( __intrusive_lane_t & this ) {
     79        /* paranoid */ verify( this.anchor.next != 0p );
     80        /* paranoid */ verify( this.anchor.ts   != 0  );
    4581
    46         // Dtor is trivial
    47         void ^?{}( __intrusive_lane_t & this ) {
    48                 // Make sure the list is empty
    49                 /* paranoid */ verify( this.anchor.next == 0p );
    50                 /* paranoid */ verify( this.anchor.ts   == 0  );
    51                 /* paranoid */ verify( mock_head(this)  == this.prev );
    52         }
     82        // Get the relevant nodes locally
     83        $thread * node = this.anchor.next;
     84        this.anchor.next = node->link.next;
     85        this.anchor.ts   = node->link.ts;
     86        bool is_empty = this.anchor.ts == 0;
     87        node->link.next = 0p;
     88        node->link.ts   = 0;
    5389
    54         // Push a thread onto this lane
    55         // returns true of lane was empty before push, false otherwise
    56         void push( __intrusive_lane_t & this, $thread * node ) {
    57                 /* paranoid */ verify( node->link.next == 0p );
    58                 /* paranoid */ verify( node->link.ts   == 0  );
    59                 /* paranoid */ verify( this.prev->link.next == 0p );
    60                 /* paranoid */ verify( this.prev->link.ts   == 0  );
    61                 if( this.anchor.next == 0p ) {
    62                         /* paranoid */ verify( this.anchor.next == 0p );
    63                         /* paranoid */ verify( this.anchor.ts   == 0  );
    64                         /* paranoid */ verify( this.prev == mock_head( this ) );
    65                 } else {
    66                         /* paranoid */ verify( this.anchor.next != 0p );
    67                         /* paranoid */ verify( this.anchor.ts   != 0  );
    68                         /* paranoid */ verify( this.prev != mock_head( this ) );
    69                 }
     90        // Update head time stamp
     91        if(is_empty) this.prev = mock_head( this );
    7092
    71                 // Get the relevant nodes locally
    72                 this.prev->link.next = node;
    73                 this.prev->link.ts   = rdtscl();
    74                 this.prev = node;
    75         }
     93        /* paranoid */ verify( node->link.next == 0p );
     94        /* paranoid */ verify( node->link.ts   == 0  );
     95        return node;
     96}
    7697
    77         // Pop a thread from this lane (must be non-empty)
    78         // returns popped
    79         // returns true of lane was empty before push, false otherwise
    80         $thread * pop( __intrusive_lane_t & this ) {
    81                 /* paranoid */ verify( this.anchor.next != 0p );
    82                 /* paranoid */ verify( this.anchor.ts   != 0  );
     98// Check whether or not list is empty
     99static inline bool is_empty(__intrusive_lane_t & this) {
     100        return this.anchor.ts == 0;
     101}
    83102
    84                 // Get the relevant nodes locally
    85                 $thread * node = this.anchor.next;
    86                 this.anchor.next = node->link.next;
    87                 this.anchor.ts   = node->link.ts;
    88                 bool is_empty = this.anchor.ts == 0;
    89                 node->link.next = 0p;
    90                 node->link.ts   = 0;
    91 
    92                 // Update head time stamp
    93                 if(is_empty) this.prev = mock_head( this );
    94 
    95                 /* paranoid */ verify( node->link.next == 0p );
    96                 /* paranoid */ verify( node->link.ts   == 0  );
    97                 return node;
    98         }
    99 
    100         // Check whether or not list is empty
    101         static inline bool is_empty(__intrusive_lane_t & this) {
    102                 return this.anchor.ts == 0;
    103         }
    104 
    105         // Return the timestamp
    106         static inline unsigned long long ts(__intrusive_lane_t & this) {
    107                 // Cannot verify here since it may not be locked
    108                 return this.anchor.ts;
    109         }
    110 #else
    111         // Intrusives lanes which are used by the relaxed ready queue
    112         struct __attribute__((aligned(128))) __intrusive_lane_t {
    113 
    114                 #if defined(USE_MPSC)
    115                         mpsc_queue($thread) queue;
    116                         __attribute__((aligned(128)))
    117                 #else
    118                         // anchor for the head and the tail of the queue
    119                         __attribute__((aligned(128))) struct __sentinel_t {
    120                                 // Link lists fields
    121                                 // instrusive link field for threads
    122                                 // must be exactly as in $thread
    123                                 __thread_desc_link link;
    124                         } before, after;
    125 
    126                         // spin lock protecting the queue
    127                         volatile bool lock;
    128                 #endif
    129 
    130                 // Optional statistic counters
    131                 #if !defined(__CFA_NO_SCHED_STATS__)
    132                         struct __attribute__((aligned(64))) {
    133                                 // difference between number of push and pops
    134                                 ssize_t diff;
    135 
    136                                 // total number of pushes and pops
    137                                 size_t  push;
    138                                 size_t  pop ;
    139                         } stat;
    140                 #endif
    141         };
    142 
    143         void  ?{}(__intrusive_lane_t & this);
    144         void ^?{}(__intrusive_lane_t & this);
    145 
    146         // Get the head pointer (one before the first element) from the anchor
    147         static inline $thread * head(const __intrusive_lane_t & this) {
    148                 #if defined(USE_MPSC)
    149                         return this.queue.head;
    150                 #else
    151                         $thread * rhead = ($thread *)(
    152                                 (uintptr_t)( &this.before ) - offsetof( $thread, link )
    153                         );
    154                         /* paranoid */ verify(rhead);
    155                         return rhead;
    156                 #endif
    157         }
    158 
    159         // Get the tail pointer (one after the last element) from the anchor
    160         static inline $thread * tail(const __intrusive_lane_t & this) {
    161                 #if defined(USE_MPSC)
    162                         return this.queue.tail;
    163                 #else
    164                         $thread * rtail = ($thread *)(
    165                                 (uintptr_t)( &this.after ) - offsetof( $thread, link )
    166                         );
    167                         /* paranoid */ verify(rtail);
    168                         return rtail;
    169                 #endif
    170         }
    171 
    172         // Ctor
    173         void ?{}( __intrusive_lane_t & this ) {
    174                 this.lock = false;
    175 
    176                 #if !defined(USE_MPSC)
    177                         this.before.link.prev = 0p;
    178                         this.before.link.next = tail(this);
    179                         this.before.link.ts   = 0;
    180 
    181                         this.after .link.prev = head(this);
    182                         this.after .link.next = 0p;
    183                         this.after .link.ts   = 0;
    184 
    185                         #if !defined(__CFA_NO_SCHED_STATS__)
    186                                 this.stat.diff = 0;
    187                                 this.stat.push = 0;
    188                                 this.stat.pop  = 0;
    189                         #endif
    190 
    191                         // We add a boat-load of assertions here because the anchor code is very fragile
    192                         /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
    193                         /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
    194                         /* paranoid */ verify(head(this)->link.prev == 0p );
    195                         /* paranoid */ verify(head(this)->link.next == tail(this) );
    196                         /* paranoid */ verify(tail(this)->link.next == 0p );
    197                         /* paranoid */ verify(tail(this)->link.prev == head(this) );
    198                         /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
    199                         /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
    200                         /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
    201                         /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
    202                         /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
    203                         /* paranoid */ verify(__alignof__(this) == 128);
    204                         /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
    205                 #endif
    206         }
    207 
    208         // Dtor is trivial
    209         void ^?{}( __intrusive_lane_t & this ) {
    210                 #if !defined(USE_MPSC)
    211                         // Make sure the list is empty
    212                         /* paranoid */ verify(head(this)->link.prev == 0p );
    213                         /* paranoid */ verify(head(this)->link.next == tail(this) );
    214                         /* paranoid */ verify(tail(this)->link.next == 0p );
    215                         /* paranoid */ verify(tail(this)->link.prev == head(this) );
    216                 #endif
    217         }
    218 
    219         // Push a thread onto this lane
    220         // returns true of lane was empty before push, false otherwise
    221         bool push(__intrusive_lane_t & this, $thread * node) {
    222                 #if defined(USE_MPSC)
    223                         inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
    224                                 return this->link.next;
    225                         }
    226                         push(this.queue, node);
    227                 #else
    228                         #if defined(__CFA_WITH_VERIFY__)
    229                                 /* paranoid */ verify(this.lock);
    230                                 /* paranoid */ verify(node->link.ts != 0);
    231                                 /* paranoid */ verify(node->link.next == 0p);
    232                                 /* paranoid */ verify(node->link.prev == 0p);
    233                                 /* paranoid */ verify(tail(this)->link.next == 0p);
    234                                 /* paranoid */ verify(head(this)->link.prev == 0p);
    235 
    236                                 if(this.before.link.ts == 0l) {
    237                                         /* paranoid */ verify(tail(this)->link.prev == head(this));
    238                                         /* paranoid */ verify(head(this)->link.next == tail(this));
    239                                 } else {
    240                                         /* paranoid */ verify(tail(this)->link.prev != head(this));
    241                                         /* paranoid */ verify(head(this)->link.next != tail(this));
    242                                 }
    243                         #endif
    244 
    245                         // Get the relevant nodes locally
    246                         $thread * tail = tail(this);
    247                         $thread * prev = tail->link.prev;
    248 
    249                         // Do the push
    250                         node->link.next = tail;
    251                         node->link.prev = prev;
    252                         prev->link.next = node;
    253                         tail->link.prev = node;
    254 
    255                         // Update stats
    256                         #if !defined(__CFA_NO_SCHED_STATS__)
    257                                 this.stat.diff++;
    258                                 this.stat.push++;
    259                         #endif
    260 
    261                         verify(node->link.next == tail(this));
    262 
    263                         // Check if the queue used to be empty
    264                         if(this.before.link.ts == 0l) {
    265                                 this.before.link.ts = node->link.ts;
    266                                 /* paranoid */ verify(node->link.prev == head(this));
    267                                 return true;
    268                         }
    269                         return false;
    270                 #endif
    271         }
    272 
    273         // Pop a thread from this lane (must be non-empty)
    274         // returns popped
    275         // returns true of lane was empty before push, false otherwise
    276         $thread * pop(__intrusive_lane_t & this) {
    277                 /* paranoid */ verify(this.lock);
    278                 #if defined(USE_MPSC)
    279                         inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
    280                                 return this->link.next;
    281                         }
    282                         return pop(this.queue);
    283                 #else
    284                         /* paranoid */ verify(this.before.link.ts != 0ul);
    285 
    286                         // Get anchors locally
    287                         $thread * head = head(this);
    288                         $thread * tail = tail(this);
    289 
    290                         // Get the relevant nodes locally
    291                         $thread * node = head->link.next;
    292                         $thread * next = node->link.next;
    293 
    294                         /* paranoid */ verify(node != tail);
    295                         /* paranoid */ verify(node);
    296 
    297                         // Do the pop
    298                         head->link.next = next;
    299                         next->link.prev = head;
    300                         node->link.next = 0p;
    301                         node->link.prev = 0p;
    302 
    303                         // Update head time stamp
    304                         this.before.link.ts = next->link.ts;
    305 
    306                         // Update stats
    307                         #ifndef __CFA_NO_SCHED_STATS__
    308                                 this.stat.diff--;
    309                                 this.stat.pop ++;
    310                         #endif
    311 
    312                         // Check if we emptied list and return accordingly
    313                         /* paranoid */ verify(tail(this)->link.next == 0p);
    314                         /* paranoid */ verify(head(this)->link.prev == 0p);
    315                         if(next == tail) {
    316                                 /* paranoid */ verify(this.before.link.ts == 0);
    317                                 /* paranoid */ verify(tail(this)->link.prev == head(this));
    318                                 /* paranoid */ verify(head(this)->link.next == tail(this));
    319                                 return node;
    320                         }
    321                         else {
    322                                 /* paranoid */ verify(next->link.ts != 0);
    323                                 /* paranoid */ verify(tail(this)->link.prev != head(this));
    324                                 /* paranoid */ verify(head(this)->link.next != tail(this));
    325                                 /* paranoid */ verify(this.before.link.ts != 0);
    326                                 return node;
    327                         }
    328                 #endif
    329         }
    330 
    331         // Check whether or not list is empty
    332         static inline bool is_empty(__intrusive_lane_t & this) {
    333                 #if defined(USE_MPSC)
    334                         return this.queue.head == 0p;
    335                 #else
    336                         // Cannot verify here since it may not be locked
    337                         return this.before.link.ts == 0;
    338                 #endif
    339         }
    340 
    341         // Return the timestamp
    342         static inline unsigned long long ts(__intrusive_lane_t & this) {
    343                 #if defined(USE_MPSC)
    344                         $thread * tl = this.queue.head;
    345                         if(!tl) return -1ull;
    346                         return tl->link.ts;
    347                 #else
    348                         // Cannot verify here since it may not be locked
    349                         return this.before.link.ts;
    350                 #endif
    351         }
    352 #endif
     103// Return the timestamp
     104static inline unsigned long long ts(__intrusive_lane_t & this) {
     105        // Cannot verify here since it may not be locked
     106        return this.anchor.ts;
     107}
    353108
    354109// Aligned timestamps which are used by the relaxed ready queue

  • libcfa/src/concurrency/thread.cfa

    rf04a3df6 rf6fdfb14  
    3838        curr_cluster = &cl;
    3939        link.next = 0p;
    40         link.prev = 0p;
    4140        link.ts   = 0;
    4241        link.preferred = -1u;
Note: See TracChangeset for help on using the changeset viewer.