source: libcfa/src/concurrency/ready_subqueue.hfa @ 42cd451e

#pragma once

#define __CFA_NO_SCHED_STATS__

// Intrusives lanes which are used by the relaxed ready queue
struct __attribute__((aligned(128))) __intrusive_lane_t {

        // anchor for the head and the tail of the queue
        __attribute__((aligned(128))) struct __sentinel_t {
                // Link lists fields
                // instrusive link field for threads
                // must be exactly as in $thread
                __thread_desc_link link;
        } before, after;

        // spin lock protecting the queue
        volatile bool lock;

        // Optional statistic counters
        #if !defined(__CFA_NO_SCHED_STATS__)
                struct __attribute__((aligned(64))) {
                        // difference between number of push and pops
                        ssize_t diff;

                        // total number of pushes and pops
                        size_t  push;
                        size_t  pop ;
                } stat;
        #endif
};

void  ?{}(__intrusive_lane_t & this);
void ^?{}(__intrusive_lane_t & this);

// Get the head pointer (one before the first element) from the anchor
static inline $thread * head(const __intrusive_lane_t & this) {
        $thread * rhead = ($thread *)(
                (uintptr_t)( &this.before ) - offsetof( $thread, link )
        );
        /* paranoid */ verify(rhead);
        return rhead;
}

// Get the tail pointer (one after the last element) from the anchor
static inline $thread * tail(const __intrusive_lane_t & this) {
        $thread * rtail = ($thread *)(
                (uintptr_t)( &this.after ) - offsetof( $thread, link )
        );
        /* paranoid */ verify(rtail);
        return rtail;
}

// Ctor
void ?{}( __intrusive_lane_t & this ) {
        this.lock = false;

        this.before.link.prev = 0p;
        this.before.link.next = tail(this);
        this.before.link.ts   = 0;

        this.after .link.prev = head(this);
        this.after .link.next = 0p;
        this.after .link.ts   = 0;

        #if !defined(__CFA_NO_SCHED_STATS__)
                this.stat.diff = 0;
                this.stat.push = 0;
                this.stat.pop  = 0;
        #endif

        // We add a boat-load of assertions here because the anchor code is very fragile
        /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
        /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
        /* paranoid */ verify(head(this)->link.prev == 0p );
        /* paranoid */ verify(head(this)->link.next == tail(this) );
        /* paranoid */ verify(tail(this)->link.next == 0p );
        /* paranoid */ verify(tail(this)->link.prev == head(this) );
        /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
        /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
        /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
        /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
        /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
        /* paranoid */ verify(__alignof__(this) == 128);
        /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
}

// Dtor is trivial
void ^?{}( __intrusive_lane_t & this ) {
        // Make sure the list is empty
        /* paranoid */ verify(head(this)->link.prev == 0p );
        /* paranoid */ verify(head(this)->link.next == tail(this) );
        /* paranoid */ verify(tail(this)->link.next == 0p );
        /* paranoid */ verify(tail(this)->link.prev == head(this) );
}

// Push a thread onto this lane
// returns true of lane was empty before push, false otherwise
bool push(__intrusive_lane_t & this, $thread * node) {
        #if defined(__CFA_WITH_VERIFY__)
                /* paranoid */ verify(this.lock);
                /* paranoid */ verify(node->link.ts != 0);
                /* paranoid */ verify(node->link.next == 0p);
                /* paranoid */ verify(node->link.prev == 0p);
                /* paranoid */ verify(tail(this)->link.next == 0p);
                /* paranoid */ verify(head(this)->link.prev == 0p);

                if(this.before.link.ts == 0l) {
                        /* paranoid */ verify(tail(this)->link.prev == head(this));
                        /* paranoid */ verify(head(this)->link.next == tail(this));
                } else {
                        /* paranoid */ verify(tail(this)->link.prev != head(this));
                        /* paranoid */ verify(head(this)->link.next != tail(this));
                }
        #endif

        // Get the relevant nodes locally
        $thread * tail = tail(this);
        $thread * prev = tail->link.prev;

        // Do the push
        node->link.next = tail;
        node->link.prev = prev;
        prev->link.next = node;
        tail->link.prev = node;

        // Update stats
        #if !defined(__CFA_NO_SCHED_STATS__)
                this.stat.diff++;
                this.stat.push++;
        #endif

        verify(node->link.next == tail(this));

        // Check if the queue used to be empty
        if(this.before.link.ts == 0l) {
                this.before.link.ts = node->link.ts;
                /* paranoid */ verify(node->link.prev == head(this));
                return true;
        }
        return false;
}

// Pop a thread from this lane (must be non-empty)
// returns popped
// returns true of lane was empty before push, false otherwise
[$thread *, bool] pop(__intrusive_lane_t & this) {
        /* paranoid */ verify(this.lock);
        /* paranoid */ verify(this.before.link.ts != 0ul);

        // Get anchors locally
        $thread * head = head(this);
        $thread * tail = tail(this);

        // Get the relevant nodes locally
        $thread * node = head->link.next;
        $thread * next = node->link.next;

        /* paranoid */ verify(node != tail);
        /* paranoid */ verify(node);

        // Do the pop
        head->link.next = next;
        next->link.prev = head;
        node->link.[next, prev] = 0p;

        // Update head time stamp
        this.before.link.ts = next->link.ts;

        // Update stats
        #ifndef __CFA_NO_SCHED_STATS__
                this.stat.diff--;
                this.stat.pop ++;
        #endif

        // Check if we emptied list and return accordingly
        /* paranoid */ verify(tail(this)->link.next == 0p);
        /* paranoid */ verify(head(this)->link.prev == 0p);
        if(next == tail) {
                /* paranoid */ verify(this.before.link.ts == 0);
                /* paranoid */ verify(tail(this)->link.prev == head(this));
                /* paranoid */ verify(head(this)->link.next == tail(this));
                return [node, true];
        }
        else {
                /* paranoid */ verify(next->link.ts != 0);
                /* paranoid */ verify(tail(this)->link.prev != head(this));
                /* paranoid */ verify(head(this)->link.next != tail(this));
                /* paranoid */ verify(this.before.link.ts != 0);
                return [node, false];
        }
}

// Check whether or not list is empty
static inline bool is_empty(__intrusive_lane_t & this) {
        // Cannot verify here since it may not be locked
        return this.before.link.ts == 0;
}

// Return the timestamp
static inline unsigned long long ts(__intrusive_lane_t & this) {
        // Cannot verify here since it may not be locked
        return this.before.link.ts;
}