Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/concurrency/ready_subqueue.hfa

    r9cc3a18 r343d10e  
    22
    33#define __CFA_NO_SCHED_STATS__
    4 
    5 #include "containers/queueLockFree.hfa"
    64
    75// Intrusives lanes which are used by the relaxed ready queue
    86struct __attribute__((aligned(128))) __intrusive_lane_t {
    97
    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
     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;
    2215
    2316        // spin lock protecting the queue
    … …  
    4235// Get the head pointer (one before the first element) from the anchor
    4336static 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
     37        $thread * rhead = ($thread *)(
     38                (uintptr_t)( &this.before ) - offsetof( $thread, link )
     39        );
     40        /* paranoid */ verify(rhead);
     41        return rhead;
    5342}
    5443
    5544// Get the tail pointer (one after the last element) from the anchor
    5645static 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
     46        $thread * rtail = ($thread *)(
     47                (uintptr_t)( &this.after ) - offsetof( $thread, link )
     48        );
     49        /* paranoid */ verify(rtail);
     50        return rtail;
    6651}
    6752
    … …  
    7055        this.lock = false;
    7156
    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
     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));
    10285}
    10386
    10487// Dtor is trivial
    10588void ^?{}( __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
     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) );
    11394}
    11495
    … …  
    11697// returns true of lane was empty before push, false otherwise
    11798bool 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;
     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
     107                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));
    121113                }
    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;
    166         #endif
     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;
    167141}
    168142
    … …  
    172146$thread * pop(__intrusive_lane_t & this) {
    173147        /* 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
     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        }
    225192}
    226193
    227194// Check whether or not list is empty
    228195static 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
     196        // Cannot verify here since it may not be locked
     197        return this.before.link.ts == 0;
    235198}
    236199
    237200// Return the timestamp
    238201static 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 }
    248 
    249 // Aligned timestamps which are used by the relaxed ready queue
    250 struct __attribute__((aligned(128))) __timestamp_t {
    251         volatile unsigned long long tv;
    252 };
    253 
    254 void  ?{}(__timestamp_t & this) { this.tv = 0; }
    255 void ^?{}(__timestamp_t & this) {}
     202        // Cannot verify here since it may not be locked
     203        return this.before.link.ts;
     204}
Note: See TracChangeset for help on using the changeset viewer.