Changeset 2b96031


Ignore:
Timestamp:
May 3, 2021, 3:39:24 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:
f04a3df6
Parents:
a049412
Message:

Added new subqueue implementation.
Seems faster will test on another machine before full replacement.

Location:
libcfa/src/concurrency
Files:
4 edited

Legend:

Unmodified
Added
Removed

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

    ra049412 r2b96031  
    462462        link.next = 0p;
    463463        link.prev = 0p;
     464        link.ts   = 0;
    464465        link.preferred = -1u;
    465466        last_proc = 0p;

  • libcfa/src/concurrency/ready_queue.cfa

    ra049412 r2b96031  
    257257
    258258                // write timestamp
    259                 thrd->link.ts = rdtscl();
     259                #if !defined(USE_NEW_SUBQUEUE)
     260                        thrd->link.ts = rdtscl();
     261                #endif
    260262
    261263                bool local;
    … …  
    354356
    355357                // write timestamp
    356                 thrd->link.ts = rdtscl();
     358                #if !defined(USE_NEW_SUBQUEUE)
     359                        thrd->link.ts = rdtscl();
     360                #endif
    357361
    358362                // Try to pick a lane and lock it
    … …  
    525529                                assert(!lanes.data[idx].lock);
    526530
    527                                 assert(head(sl)->link.prev == 0p );
    528                                 assert(head(sl)->link.next->link.prev == head(sl) );
    529                                 assert(tail(sl)->link.next == 0p );
    530                                 assert(tail(sl)->link.prev->link.next == tail(sl) );
    531 
    532                                 if(is_empty(sl)) {
    533                                         assert(tail(sl)->link.prev == head(sl));
    534                                         assert(head(sl)->link.next == tail(sl));
    535                                 } else {
    536                                         assert(tail(sl)->link.prev != head(sl));
    537                                         assert(head(sl)->link.next != tail(sl));
    538                                 }
     531                                #if defined(USE_NEW_SUBQUEUE)
     532                                        if(is_empty(sl)) {
     533                                                assert( sl.anchor.next == 0p );
     534                                                assert( sl.anchor.ts   == 0  );
     535                                                assert( mock_head(sl)  == sl.prev );
     536                                        } else {
     537                                                assert( sl.anchor.next != 0p );
     538                                                assert( sl.anchor.ts   != 0  );
     539                                                assert( mock_head(sl)  != sl.prev );
     540                                        }
     541                                #else
     542                                        assert(head(sl)->link.prev == 0p );
     543                                        assert(head(sl)->link.next->link.prev == head(sl) );
     544                                        assert(tail(sl)->link.next == 0p );
     545                                        assert(tail(sl)->link.prev->link.next == tail(sl) );
     546
     547                                        if(is_empty(sl)) {
     548                                                assert(tail(sl)->link.prev == head(sl));
     549                                                assert(head(sl)->link.next == tail(sl));
     550                                        } else {
     551                                                assert(tail(sl)->link.prev != head(sl));
     552                                                assert(head(sl)->link.next != tail(sl));
     553                                        }
     554                                #endif
    539555                        }
    540556                }
    … …  
    558574static inline void fix(__intrusive_lane_t & ll) {
    559575        #if !defined(USE_MPSC)
    560                 // if the list is not empty then follow he pointer and fix its reverse
    561                 if(!is_empty(ll)) {
    562                         head(ll)->link.next->link.prev = head(ll);
    563                         tail(ll)->link.prev->link.next = tail(ll);
    564                 }
    565                 // Otherwise just reset the list
    566                 else {
    567                         verify(tail(ll)->link.next == 0p);
    568                         tail(ll)->link.prev = head(ll);
    569                         head(ll)->link.next = tail(ll);
    570                         verify(head(ll)->link.prev == 0p);
    571                 }
     576                #if defined(USE_NEW_SUBQUEUE)
     577                        if(is_empty(ll)) {
     578                                verify(ll.anchor.next == 0p);
     579                                ll.prev = mock_head(ll);
     580                        }
     581                #else
     582                        // if the list is not empty then follow he pointer and fix its reverse
     583                        if(!is_empty(ll)) {
     584                                head(ll)->link.next->link.prev = head(ll);
     585                                tail(ll)->link.prev->link.next = tail(ll);
     586                        }
     587                        // Otherwise just reset the list
     588                        else {
     589                                verify(tail(ll)->link.next == 0p);
     590                                tail(ll)->link.prev = head(ll);
     591                                head(ll)->link.next = tail(ll);
     592                                verify(head(ll)->link.prev == 0p);
     593                        }
     594                #endif
    572595        #endif
    573596}

  • libcfa/src/concurrency/ready_subqueue.hfa

    ra049412 r2b96031  
    55#include "containers/queueLockFree.hfa"
    66
    7 // Intrusives lanes which are used by the relaxed ready queue
    8 struct __attribute__((aligned(128))) __intrusive_lane_t {
    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
    22 
    23         // spin lock protecting the queue
    24         volatile bool lock;
    25 
    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;
    36         #endif
    37 };
    38 
    39 void  ?{}(__intrusive_lane_t & this);
    40 void ^?{}(__intrusive_lane_t & this);
    41 
    42 // Get the head pointer (one before the first element) from the anchor
    43 static inline $thread * head(const __intrusive_lane_t & this) {
    44         #if defined(USE_MPSC)
    45                 return this.queue.head;
    46         #else
     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;
     12
     13                // spin lock protecting the queue
     14                volatile bool lock;
     15
     16                __thread_desc_link anchor;
     17        };
     18
     19        // Get the head pointer (one before the first element) from the anchor
     20        static inline $thread * mock_head(const __intrusive_lane_t & this) {
    4721                $thread * rhead = ($thread *)(
    48                         (uintptr_t)( &this.before ) - offsetof( $thread, link )
     22                        (uintptr_t)( &this.anchor ) - __builtin_offsetof( $thread, link )
    4923                );
    50                 /* paranoid */ verify(rhead);
    5124                return rhead;
    52         #endif
    53 }
    54 
    55 // Get the tail pointer (one after the last element) from the anchor
    56 static 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
    66 }
    67 
    68 // Ctor
    69 void ?{}( __intrusive_lane_t & this ) {
    70         this.lock = false;
    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 
     25        }
     26
     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;
     33
     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        }
     45
     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        }
     53
     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                }
     70
     71                // Get the relevant nodes locally
     72                this.prev->link.next = node;
     73                this.prev->link.ts   = rdtscl();
     74                this.prev = node;
     75        }
     76
     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  );
     83
     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
    81131                #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
    102 }
    103 
    104 // Dtor is trivial
    105 void ^?{}( __intrusive_lane_t & 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
    113 }
    114 
    115 // Push a thread onto this lane
    116 // returns true of lane was empty before push, false otherwise
    117 bool 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);
     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
    129313                        /* paranoid */ verify(tail(this)->link.next == 0p);
    130314                        /* paranoid */ verify(head(this)->link.prev == 0p);
    131 
    132                         if(this.before.link.ts == 0l) {
     315                        if(next == tail) {
     316                                /* paranoid */ verify(this.before.link.ts == 0);
    133317                                /* paranoid */ verify(tail(this)->link.prev == head(this));
    134318                                /* paranoid */ verify(head(this)->link.next == tail(this));
    135                         } else {
     319                                return node;
     320                        }
     321                        else {
     322                                /* paranoid */ verify(next->link.ts != 0);
    136323                                /* paranoid */ verify(tail(this)->link.prev != head(this));
    137324                                /* 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;
    166         #endif
    167 }
    168 
    169 // Pop a thread from this lane (must be non-empty)
    170 // returns popped
    171 // returns true of lane was empty before push, false otherwise
    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
    225 }
    226 
    227 // Check whether or not list is empty
    228 static inline bool is_empty(__intrusive_lane_t & this) {
    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
    235 }
    236 
    237 // Return the timestamp
    238 static inline unsigned long long ts(__intrusive_lane_t & this) {
    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 }
     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
    248353
    249354// Aligned timestamps which are used by the relaxed ready queue

  • libcfa/src/concurrency/thread.cfa

    ra049412 r2b96031  
    3939        link.next = 0p;
    4040        link.prev = 0p;
     41        link.ts   = 0;
    4142        link.preferred = -1u;
    4243        last_proc = 0p;
Note: See TracChangeset for help on using the changeset viewer.