Changeset 2d95a2d


Ignore:
Timestamp:
Mar 26, 2021, 5:57:52 PM (7 months ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
cd26abf
Parents:
bd0bdd37
Message:

Small fixes to lock free queues.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • libcfa/src/containers/queueLockFree.hfa

    rbd0bdd37 r2d95a2d  
    2020                // Adds an element to the list
    2121                // Multi-Thread Safe, Lock-Free
    22                 T * push(mcs_queue(T) & this, T & elem) {
    23                         /* paranoid */ verify(!(&elem)`next);
     22                T * push(mcs_queue(T) & this, T * elem) __attribute__((artificial));
     23                T * push(mcs_queue(T) & this, T * elem) {
     24                        /* paranoid */ verify(!(elem`next));
    2425                        // Race to add to the tail
    25                         T * prev = __atomic_exchange_n(&this.tail, &elem, __ATOMIC_SEQ_CST);
     26                        T * prev = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST);
    2627                        // If we aren't the first, we need to tell the person before us
    2728                        // No need to
    28                         if (prev) prev`next = &elem;
     29                        if (prev) prev`next = elem;
    2930                        return prev;
    3031                }
     
    3334                // Passing an element that is not the head is undefined behavior
    3435                // NOT Multi-Thread Safe, concurrent pushes are safe
    35                 T * advance(mcs_queue(T) & this, T & elem) {
    36                         T * expected = &elem;
     36                T * advance(mcs_queue(T) & this, T * elem) __attribute__((artificial));
     37                T * advance(mcs_queue(T) & this, T * elem) {
     38                        T * expected = elem;
    3739                        // Check if this is already the last item
    3840                        if (__atomic_compare_exchange_n(&this.tail, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) return 0p;
    3941
    40                         // If not wait for next item to show-up
    41                         // added by push
    42                         while (!(&elem)`next) Pause();
    43                         return (&elem)`next;
     42                        // If not wait for next item to show-up, filled by push
     43                        while (!(elem`next)) Pause();
     44
     45                        // we need to return if the next link was empty
     46                        T * ret = elem`next;
     47
     48                        // invalidate link to reset to initial state
     49                        elem`next = 0p;
     50                        return ret;
    4451                }
    4552        }
     
    6471                // Added a new element to the queue
    6572                // Multi-Thread Safe, Lock-Free
    66                 T * push(mpsc_queue(T) & this, T & elem) {
     73                T * push(mpsc_queue(T) & this, T * elem) __attribute__((artificial));
     74                T * push(mpsc_queue(T) & this, T * elem) {
    6775                        T * prev = push((mcs_queue(T)&)this, elem);
    68                         if (!prev) this.head = &elem;
     76                        if (!prev) this.head = elem;
    6977                        return prev;
    7078                }
     
    7482                // next is set to the new head of the queue
    7583                // NOT Multi-Thread Safe
     84                T * pop(mpsc_queue(T) & this, T *& next) __attribute__((artificial));
    7685                T * pop(mpsc_queue(T) & this, T *& next) {
    7786                        T * elem = this.head;
     
    8493                                // force memory sync
    8594                                __atomic_thread_fence(__ATOMIC_SEQ_CST);
     95
     96                                // invalidate link to reset to initial state
     97                                elem`next = 0p;
    8698                        }
    8799                        // Otherwise, there might be a race where it only looks but someone is enqueuing
     
    91103                                // after that point, it could overwrite the write in push
    92104                                this.head = 0p;
    93                                 next = advance((mcs_queue(T)&)this, (*elem));
     105                                next = advance((mcs_queue(T)&)this, elem);
    94106
    95107                                // Only write to the head if there is a next element
     
    98110                                if (next) this.head = next;
    99111                        }
    100 
    101                         // invalidate link
    102                         elem`next = 0p;
    103112
    104113                        // return removed element
Note: See TracChangeset for help on using the changeset viewer.