source: libcfa/src/concurrency/ready_queue.cfa@ 76c94bf

//
// Cforall Version 1.0.0 Copyright (C) 2019 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// ready_queue.cfa --
//
// Author           : Thierry Delisle
// Created On       : Mon Nov dd 16:29:18 2019
// Last Modified By :
// Last Modified On :
// Update Count     :
//

#define __cforall_thread__
// #define __CFA_DEBUG_PRINT_READY_QUEUE__

// #define USE_SNZI
// #define USE_MPSC

#include "bits/defs.hfa"
#include "kernel_private.hfa"

#define _GNU_SOURCE
#include "stdlib.hfa"
#include "math.hfa"

#include <unistd.h>

#include "snzi.hfa"
#include "ready_subqueue.hfa"

static const size_t cache_line_size = 64;

// No overriden function, no environment variable, no define
// fall back to a magic number
#ifndef __CFA_MAX_PROCESSORS__
        #define __CFA_MAX_PROCESSORS__ 1024
#endif

#define BIAS 4

// returns the maximum number of processors the RWLock support
__attribute__((weak)) unsigned __max_processors() {
        const char * max_cores_s = getenv("CFA_MAX_PROCESSORS");
        if(!max_cores_s) {
                __cfadbg_print_nolock(ready_queue, "No CFA_MAX_PROCESSORS in ENV\n");
                return __CFA_MAX_PROCESSORS__;
        }

        char * endptr = 0p;
        long int max_cores_l = strtol(max_cores_s, &endptr, 10);
        if(max_cores_l < 1 || max_cores_l > 65535) {
                __cfadbg_print_nolock(ready_queue, "CFA_MAX_PROCESSORS out of range : %ld\n", max_cores_l);
                return __CFA_MAX_PROCESSORS__;
        }
        if('\0' != *endptr) {
                __cfadbg_print_nolock(ready_queue, "CFA_MAX_PROCESSORS not a decimal number : %s\n", max_cores_s);
                return __CFA_MAX_PROCESSORS__;
        }

        return max_cores_l;
}

//=======================================================================
// Cluster wide reader-writer lock
//=======================================================================
void  ?{}(__scheduler_RWLock_t & this) {
        this.max   = __max_processors();
        this.alloc = 0;
        this.ready = 0;
        this.lock  = false;
        this.data  = alloc(this.max);

        /*paranoid*/ verify( 0 == (((uintptr_t)(this.data    )) % 64) );
        /*paranoid*/ verify( 0 == (((uintptr_t)(this.data + 1)) % 64) );
        /*paranoid*/ verify(__atomic_is_lock_free(sizeof(this.alloc), &this.alloc));
        /*paranoid*/ verify(__atomic_is_lock_free(sizeof(this.ready), &this.ready));

}
void ^?{}(__scheduler_RWLock_t & this) {
        free(this.data);
}

void ?{}( __scheduler_lock_id_t & this, __processor_id_t * proc ) {
        this.handle = proc;
        this.lock   = false;
        #ifdef __CFA_WITH_VERIFY__
                this.owned  = false;
        #endif
}

//=======================================================================
// Lock-Free registering/unregistering of threads
void register_proc_id( struct __processor_id_t * proc ) with(*__scheduler_lock) {
        __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p for RW-Lock\n", proc);

        // Step - 1 : check if there is already space in the data
        uint_fast32_t s = ready;

        // Check among all the ready
        for(uint_fast32_t i = 0; i < s; i++) {
                __processor_id_t * null = 0p; // Re-write every loop since compare thrashes it
                if( __atomic_load_n(&data[i].handle, (int)__ATOMIC_RELAXED) == null
                        && __atomic_compare_exchange_n( &data[i].handle, &null, proc, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
                        /*paranoid*/ verify(i < ready);
                        /*paranoid*/ verify(0 == (__alignof__(data[i]) % cache_line_size));
                        /*paranoid*/ verify((((uintptr_t)&data[i]) % cache_line_size) == 0);
                        proc->id = i;
                }
        }

        if(max <= alloc) abort("Trying to create more than %ud processors", __scheduler_lock->max);

        // Step - 2 : F&A to get a new spot in the array.
        uint_fast32_t n = __atomic_fetch_add(&alloc, 1, __ATOMIC_SEQ_CST);
        if(max <= n) abort("Trying to create more than %ud processors", __scheduler_lock->max);

        // Step - 3 : Mark space as used and then publish it.
        __scheduler_lock_id_t * storage = (__scheduler_lock_id_t *)&data[n];
        (*storage){ proc };
        while() {
                unsigned copy = n;
                if( __atomic_load_n(&ready, __ATOMIC_RELAXED) == n
                        && __atomic_compare_exchange_n(&ready, &copy, n + 1, true, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))
                        break;
                Pause();
        }

        __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p done, id %lu\n", proc, n);

        // Return new spot.
        /*paranoid*/ verify(n < ready);
        /*paranoid*/ verify(__alignof__(data[n]) == (2 * cache_line_size));
        /*paranoid*/ verify((((uintptr_t)&data[n]) % cache_line_size) == 0);
        proc->id = n;
}

void unregister_proc_id( struct __processor_id_t * proc ) with(*__scheduler_lock) {
        unsigned id = proc->id;
        /*paranoid*/ verify(id < ready);
        /*paranoid*/ verify(proc == __atomic_load_n(&data[id].handle, __ATOMIC_RELAXED));
        __atomic_store_n(&data[id].handle, 0p, __ATOMIC_RELEASE);

        __cfadbg_print_safe(ready_queue, "Kernel : Unregister proc %p\n", proc);
}

//-----------------------------------------------------------------------
// Writer side : acquire when changing the ready queue, e.g. adding more
//  queues or removing them.
uint_fast32_t ready_mutate_lock( void ) with(*__scheduler_lock) {
        /* paranoid */ verify( ! __preemption_enabled() );

        // Step 1 : lock global lock
        // It is needed to avoid processors that register mid Critical-Section
        //   to simply lock their own lock and enter.
        __atomic_acquire( &lock );

        // Step 2 : lock per-proc lock
        // Processors that are currently being registered aren't counted
        //   but can't be in read_lock or in the critical section.
        // All other processors are counted
        uint_fast32_t s = ready;
        for(uint_fast32_t i = 0; i < s; i++) {
                __atomic_acquire( &data[i].lock );
        }

        /* paranoid */ verify( ! __preemption_enabled() );
        return s;
}

void ready_mutate_unlock( uint_fast32_t last_s ) with(*__scheduler_lock) {
        /* paranoid */ verify( ! __preemption_enabled() );

        // Step 1 : release local locks
        // This must be done while the global lock is held to avoid
        //   threads that where created mid critical section
        //   to race to lock their local locks and have the writer
        //   immidiately unlock them
        // Alternative solution : return s in write_lock and pass it to write_unlock
        for(uint_fast32_t i = 0; i < last_s; i++) {
                verify(data[i].lock);
                __atomic_store_n(&data[i].lock, (bool)false, __ATOMIC_RELEASE);
        }

        // Step 2 : release global lock
        /*paranoid*/ assert(true == lock);
        __atomic_store_n(&lock, (bool)false, __ATOMIC_RELEASE);

        /* paranoid */ verify( ! __preemption_enabled() );
}

//=======================================================================
// Cforall Reqdy Queue used for scheduling
//=======================================================================
void ?{}(__ready_queue_t & this) with (this) {
        lanes.data  = 0p;
        lanes.count = 0;
}

void ^?{}(__ready_queue_t & this) with (this) {
        verify( 1 == lanes.count );
        #ifdef USE_SNZI
                verify( !query( snzi ) );
        #endif
        free(lanes.data);
}

//-----------------------------------------------------------------------
__attribute__((hot)) bool query(struct cluster * cltr) {
        #ifdef USE_SNZI
                return query(cltr->ready_queue.snzi);
        #endif
        return true;
}

static inline [unsigned, bool] idx_from_r(unsigned r, unsigned preferred) {
        unsigned i;
        bool local;
        #if defined(BIAS)
                unsigned rlow  = r % BIAS;
                unsigned rhigh = r / BIAS;
                if((0 != rlow) && preferred >= 0) {
                        // (BIAS - 1) out of BIAS chances
                        // Use perferred queues
                        i = preferred + (rhigh % 4);
                        local = true;
                }
                else {
                        // 1 out of BIAS chances
                        // Use all queues
                        i = rhigh;
                        local = false;
                }
        #else
                i = r;
                local = false;
        #endif
        return [i, local];
}

//-----------------------------------------------------------------------
__attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
        __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);

        const bool external = (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);

        // write timestamp
        thrd->link.ts = rdtscl();

        bool first = false;
        __attribute__((unused)) bool local;
        __attribute__((unused)) int preferred;
        #if defined(BIAS)
                /* paranoid */ verify(external || kernelTLS().this_processor->cltr_id < lanes.count );
                preferred =
                        //*
                        external ? -1 : kernelTLS().this_processor->cltr_id;
                        /*/
                        thrd->link.preferred * 4;
                        //*/
        #endif

        // Try to pick a lane and lock it
        unsigned i;
        do {
                // Pick the index of a lane
                // unsigned r = __tls_rand();
                unsigned r = __tls_rand_fwd();
                [i, local] = idx_from_r(r, preferred);

                i %= __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );

                #if !defined(__CFA_NO_STATISTICS__)
                        if(external) {
                                if(local) __atomic_fetch_add(&cltr->stats->ready.pick.ext.local, 1, __ATOMIC_RELAXED);
                                __atomic_fetch_add(&cltr->stats->ready.pick.ext.attempt, 1, __ATOMIC_RELAXED);
                        }
                        else {
                                if(local) __tls_stats()->ready.pick.push.local++;
                                __tls_stats()->ready.pick.push.attempt++;
                        }
                #endif

        #if defined(USE_MPSC)
                // mpsc always succeeds
        } while( false );
        #else
                // If we can't lock it retry
        } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
        #endif

        // Actually push it
        #ifdef USE_SNZI
                bool lane_first =
        #endif

        push(lanes.data[i], thrd);

        #ifdef USE_SNZI
                // If this lane used to be empty we need to do more
                if(lane_first) {
                        // Check if the entire queue used to be empty
                        first = !query(snzi);

                        // Update the snzi
                        arrive( snzi, i );
                }
        #endif

        #if !defined(USE_MPSC)
                // Unlock and return
                __atomic_unlock( &lanes.data[i].lock );
        #endif

        // Mark the current index in the tls rng instance as having an item
        __tls_rand_advance_bck();

        __cfadbg_print_safe(ready_queue, "Kernel : Pushed %p on cluster %p (idx: %u, mask %llu, first %d)\n", thrd, cltr, i, used.mask[0], lane_first);

        // Update statistics
        #if !defined(__CFA_NO_STATISTICS__)
                if(external) {
                        if(local) __atomic_fetch_add(&cltr->stats->ready.pick.ext.lsuccess, 1, __ATOMIC_RELAXED);
                        __atomic_fetch_add(&cltr->stats->ready.pick.ext.success, 1, __ATOMIC_RELAXED);
                }
                else {
                        if(local) __tls_stats()->ready.pick.push.lsuccess++;
                        __tls_stats()->ready.pick.push.success++;
                }
        #endif

        // return whether or not the list was empty before this push
        return first;
}

static struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j);
static struct $thread * try_pop(struct cluster * cltr, unsigned i);

// Pop from the ready queue from a given cluster
__attribute__((hot)) $thread * pop(struct cluster * cltr) with (cltr->ready_queue) {
        /* paranoid */ verify( lanes.count > 0 );
        unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
        int preferred;
        #if defined(BIAS)
                /* paranoid */ verify(kernelTLS().this_processor->cltr_id < lanes.count );
                preferred = kernelTLS().this_processor->cltr_id;
        #endif


        // As long as the list is not empty, try finding a lane that isn't empty and pop from it
        #ifdef USE_SNZI
                while( query(snzi) ) {
        #else
                for(25) {
        #endif
                // Pick two lists at random
                // unsigned ri = __tls_rand();
                // unsigned rj = __tls_rand();
                unsigned ri = __tls_rand_bck();
                unsigned rj = __tls_rand_bck();

                unsigned i, j;
                __attribute__((unused)) bool locali, localj;
                [i, locali] = idx_from_r(ri, preferred);
                [j, localj] = idx_from_r(rj, preferred);

                #if !defined(__CFA_NO_STATISTICS__)
                        if(locali && localj) {
                                __tls_stats()->ready.pick.pop.local++;
                        }
                #endif

                i %= count;
                j %= count;

                // try popping from the 2 picked lists
                struct $thread * thrd = try_pop(cltr, i, j);
                if(thrd) {
                        #if defined(BIAS) && !defined(__CFA_NO_STATISTICS__)
                                if( locali || localj ) __tls_stats()->ready.pick.pop.lsuccess++;
                        #endif
                        return thrd;
                }
        }

        // All lanes where empty return 0p
        return 0p;
}

__attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr) with (cltr->ready_queue) {
        /* paranoid */ verify( lanes.count > 0 );
        unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
        unsigned offset = __tls_rand();
        for(i; count) {
                unsigned idx = (offset + i) % count;
                struct $thread * thrd = try_pop(cltr, idx);
                if(thrd) {
                        return thrd;
                }
        }

        // All lanes where empty return 0p
        return 0p;
}


//-----------------------------------------------------------------------
// Given 2 indexes, pick the list with the oldest push an try to pop from it
static inline struct $thread * try_pop(struct cluster * cltr, unsigned i, unsigned j) with (cltr->ready_queue) {
        #if !defined(__CFA_NO_STATISTICS__)
                __tls_stats()->ready.pick.pop.attempt++;
        #endif

        // Pick the bet list
        int w = i;
        if( __builtin_expect(!is_empty(lanes.data[j]), true) ) {
                w = (ts(lanes.data[i]) < ts(lanes.data[j])) ? i : j;
        }

        return try_pop(cltr, w);
}

static inline struct $thread * try_pop(struct cluster * cltr, unsigned w) with (cltr->ready_queue) {
        // Get relevant elements locally
        __intrusive_lane_t & lane = lanes.data[w];

        // If list looks empty retry
        if( is_empty(lane) ) return 0p;

        // If we can't get the lock retry
        if( !__atomic_try_acquire(&lane.lock) ) return 0p;


        // If list is empty, unlock and retry
        if( is_empty(lane) ) {
                __atomic_unlock(&lane.lock);
                return 0p;
        }

        // Actually pop the list
        struct $thread * thrd;
        thrd = pop(lane);

        /* paranoid */ verify(thrd);
        /* paranoid */ verify(lane.lock);

        #ifdef USE_SNZI
                // If this was the last element in the lane
                if(emptied) {
                        depart( snzi, w );
                }
        #endif

        // Unlock and return
        __atomic_unlock(&lane.lock);

        // Update statistics
        #if !defined(__CFA_NO_STATISTICS__)
                __tls_stats()->ready.pick.pop.success++;
        #endif

        // Update the thread bias
        thrd->link.preferred = w / 4;

        // return the popped thread
        return thrd;
}
//-----------------------------------------------------------------------

bool remove_head(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
        for(i; lanes.count) {
                __intrusive_lane_t & lane = lanes.data[i];

                bool removed = false;

                __atomic_acquire(&lane.lock);
                        if(head(lane)->link.next == thrd) {
                                $thread * pthrd;
                                pthrd = pop(lane);

                                /* paranoid */ verify( pthrd == thrd );

                                removed = true;
                                #ifdef USE_SNZI
                                        if(emptied) {
                                                depart( snzi, i );
                                        }
                                #endif
                        }
                __atomic_unlock(&lane.lock);

                if( removed ) return true;
        }
        return false;
}

//-----------------------------------------------------------------------

static void check( __ready_queue_t & q ) with (q) {
        #if defined(__CFA_WITH_VERIFY__) && !defined(USE_MPSC)
                {
                        for( idx ; lanes.count ) {
                                __intrusive_lane_t & sl = lanes.data[idx];
                                assert(!lanes.data[idx].lock);

                                assert(head(sl)->link.prev == 0p );
                                assert(head(sl)->link.next->link.prev == head(sl) );
                                assert(tail(sl)->link.next == 0p );
                                assert(tail(sl)->link.prev->link.next == tail(sl) );

                                if(is_empty(sl)) {
                                        assert(tail(sl)->link.prev == head(sl));
                                        assert(head(sl)->link.next == tail(sl));
                                } else {
                                        assert(tail(sl)->link.prev != head(sl));
                                        assert(head(sl)->link.next != tail(sl));
                                }
                        }
                }
        #endif
}

// Call this function of the intrusive list was moved using memcpy
// fixes the list so that the pointers back to anchors aren't left dangling
static inline void fix(__intrusive_lane_t & ll) {
        #if !defined(USE_MPSC)
                // if the list is not empty then follow he pointer and fix its reverse
                if(!is_empty(ll)) {
                        head(ll)->link.next->link.prev = head(ll);
                        tail(ll)->link.prev->link.next = tail(ll);
                }
                // Otherwise just reset the list
                else {
                        verify(tail(ll)->link.next == 0p);
                        tail(ll)->link.prev = head(ll);
                        head(ll)->link.next = tail(ll);
                        verify(head(ll)->link.prev == 0p);
                }
        #endif
}

static void assign_list(unsigned & value, const int inc, dlist(processor, processor) & list, unsigned count) {
        processor * it = &list`first;
        for(unsigned i = 0; i < count; i++) {
                /* paranoid */ verifyf( it, "Unexpected null iterator, at index %u of %u\n", i, count);
                it->cltr_id = value;
                value += inc;
                it = &(*it)`next;
        }
}

static void reassign_cltr_id(struct cluster * cltr, const int inc) {
        unsigned preferred = 0;
        assign_list(preferred, inc, cltr->procs.actives, cltr->procs.total - cltr->procs.idle);
        assign_list(preferred, inc, cltr->procs.idles  , cltr->procs.idle );
}

// Grow the ready queue
void ready_queue_grow(struct cluster * cltr) {
        size_t ncount;
        int target = cltr->procs.total;

        /* paranoid */ verify( ready_mutate_islocked() );
        __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n");

        // Make sure that everything is consistent
        /* paranoid */ check( cltr->ready_queue );

        // grow the ready queue
        with( cltr->ready_queue ) {
                #ifdef USE_SNZI
                        ^(snzi){};
                #endif

                // Find new count
                // Make sure we always have atleast 1 list
                if(target >= 2) {
                        ncount = target * 4;
                } else {
                        ncount = 1;
                }

                // Allocate new array (uses realloc and memcpies the data)
                lanes.data = alloc( ncount, lanes.data`realloc );

                // Fix the moved data
                for( idx; (size_t)lanes.count ) {
                        fix(lanes.data[idx]);
                }

                // Construct new data
                for( idx; (size_t)lanes.count ~ ncount) {
                        (lanes.data[idx]){};
                }

                // Update original
                lanes.count = ncount;

                #ifdef USE_SNZI
                        // Re-create the snzi
                        snzi{ log2( lanes.count / 8 ) };
                        for( idx; (size_t)lanes.count ) {
                                if( !is_empty(lanes.data[idx]) ) {
                                        arrive(snzi, idx);
                                }
                        }
                #endif
        }

        reassign_cltr_id(cltr, 4);

        // Make sure that everything is consistent
        /* paranoid */ check( cltr->ready_queue );

        __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue done\n");

        /* paranoid */ verify( ready_mutate_islocked() );
}

// Shrink the ready queue
void ready_queue_shrink(struct cluster * cltr) {
        /* paranoid */ verify( ready_mutate_islocked() );
        __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n");

        // Make sure that everything is consistent
        /* paranoid */ check( cltr->ready_queue );

        int target = cltr->procs.total;

        with( cltr->ready_queue ) {
                #ifdef USE_SNZI
                        ^(snzi){};
                #endif

                // Remember old count
                size_t ocount = lanes.count;

                // Find new count
                // Make sure we always have atleast 1 list
                lanes.count = target >= 2 ? target * 4: 1;
                /* paranoid */ verify( ocount >= lanes.count );
                /* paranoid */ verify( lanes.count == target * 4 || target < 2 );

                // for printing count the number of displaced threads
                #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
                        __attribute__((unused)) size_t displaced = 0;
                #endif

                // redistribute old data
                for( idx; (size_t)lanes.count ~ ocount) {
                        // Lock is not strictly needed but makes checking invariants much easier
                        __attribute__((unused)) bool locked = __atomic_try_acquire(&lanes.data[idx].lock);
                        verify(locked);

                        // As long as we can pop from this lane to push the threads somewhere else in the queue
                        while(!is_empty(lanes.data[idx])) {
                                struct $thread * thrd;
                                thrd = pop(lanes.data[idx]);

                                push(cltr, thrd);

                                // for printing count the number of displaced threads
                                #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
                                        displaced++;
                                #endif
                        }

                        // Unlock the lane
                        __atomic_unlock(&lanes.data[idx].lock);

                        // TODO print the queue statistics here

                        ^(lanes.data[idx]){};
                }

                __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue displaced %zu threads\n", displaced);

                // Allocate new array (uses realloc and memcpies the data)
                lanes.data = alloc( lanes.count, lanes.data`realloc );

                // Fix the moved data
                for( idx; (size_t)lanes.count ) {
                        fix(lanes.data[idx]);
                }

                #ifdef USE_SNZI
                        // Re-create the snzi
                        snzi{ log2( lanes.count / 8 ) };
                        for( idx; (size_t)lanes.count ) {
                                if( !is_empty(lanes.data[idx]) ) {
                                        arrive(snzi, idx);
                                }
                        }
                #endif
        }

        reassign_cltr_id(cltr, 4);

        // Make sure that everything is consistent
        /* paranoid */ check( cltr->ready_queue );

        __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue done\n");
        /* paranoid */ verify( ready_mutate_islocked() );
}