Changeset d672350 for libcfa

Timestamp:

Mar 21, 2022, 1:44:06 PM (4 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, ast-experimental, enum, master, pthread-emulation, qualifiedEnum

Children:

a76202d

Parents:

ef3c383 (diff), dbe2533 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:

libcfa/src

Files:

• Makefile.am (modified) (3 diffs)
• concurrency/coroutine.cfa (modified) (1 diff)
• concurrency/io.cfa (modified) (12 diffs)
• concurrency/io/setup.cfa (modified) (7 diffs)
• concurrency/io/types.hfa (modified) (3 diffs)
• concurrency/iofwd.hfa (modified) (5 diffs)
• concurrency/kernel.cfa (modified) (17 diffs)
• concurrency/kernel.hfa (modified) (6 diffs)
• concurrency/kernel/cluster.cfa (added)
• concurrency/kernel/cluster.hfa (added)
• concurrency/kernel/fwd.hfa (modified) (1 diff)
• concurrency/kernel/private.hfa (moved) (moved from libcfa/src/concurrency/kernel_private.hfa ) (5 diffs)
• concurrency/kernel/startup.cfa (modified) (13 diffs)
• concurrency/locks.cfa (modified) (1 diff)
• concurrency/locks.hfa (modified) (3 diffs)
• concurrency/monitor.cfa (modified) (1 diff)
• concurrency/mutex.cfa (modified) (1 diff)
• concurrency/mutex_stmt.hfa (modified) (2 diffs)
• concurrency/preemption.cfa (modified) (5 diffs)
• concurrency/ready_queue.cfa (modified) (8 diffs)
• concurrency/ready_subqueue.hfa (modified) (1 diff)
• concurrency/thread.cfa (modified) (1 diff)
• containers/string.cfa (modified) (2 diffs)
• containers/string.hfa (modified) (2 diffs)
• containers/string_res.cfa (modified) (37 diffs)
• containers/string_res.hfa (modified) (8 diffs)
• containers/string_sharectx.hfa (added)
• math.trait.hfa (modified) (4 diffs)

libcfa/src/Makefile.am

@@ -63 +63 @@
         containers/queueLockFree.hfa \
         containers/stackLockFree.hfa \
+        containers/string_sharectx.hfa \
         containers/vector2.hfa \
         vec/vec.hfa \
@@ -118 +119 @@
         concurrency/exception.hfa \
         concurrency/kernel.hfa \
+        concurrency/kernel/cluster.hfa \
         concurrency/locks.hfa \
         concurrency/monitor.hfa \
@@ -133 +135 @@
         concurrency/io/call.cfa \
         concurrency/iofwd.hfa \
-        concurrency/kernel_private.hfa \
+        concurrency/kernel/private.hfa \
         concurrency/kernel/startup.cfa \
         concurrency/preemption.cfa \

libcfa/src/concurrency/coroutine.cfa

@@ -27 +27 @@
 #include <unwind.h>
 
-#include "kernel_private.hfa"
+#include "kernel/private.hfa"
 #include "exception.hfa"
 #include "math.hfa"

libcfa/src/concurrency/io.cfa

@@ -41 +41 @@
         #include "kernel.hfa"
         #include "kernel/fwd.hfa"
-        #include "kernel_private.hfa"
+        #include "kernel/private.hfa"
         #include "io/types.hfa"
 
@@ -93 +93 @@
         extern void __kernel_unpark( thread$ * thrd, unpark_hint );
 
-        bool __cfa_io_drain( processor * proc ) {
+        bool __cfa_io_drain( $io_context * ctx ) {
                 /* paranoid */ verify( ! __preemption_enabled() );
                 /* paranoid */ verify( ready_schedule_islocked() );
-                /* paranoid */ verify( proc );
-                /* paranoid */ verify( proc->io.ctx );
+                /* paranoid */ verify( ctx );
 
                 // Drain the queue
-                $io_context * ctx = proc->io.ctx;
                 unsigned head = *ctx->cq.head;
                 unsigned tail = *ctx->cq.tail;
@@ -110 +108 @@
                 if(count == 0) return false;
 
+                if(!__atomic_try_acquire(&ctx->cq.lock)) {
+                        return false;
+                }
+
                 for(i; count) {
                         unsigned idx = (head + i) & mask;
@@ -130 +132 @@
                 /* paranoid */ verify( ready_schedule_islocked() );
                 /* paranoid */ verify( ! __preemption_enabled() );
+
+                __atomic_unlock(&ctx->cq.lock);
 
                 return true;
@@ -175 +179 @@
                         /* paranoid */ verify( ! __preemption_enabled() );
 
-                        ctx.proc->io.pending = false;
+                        __atomic_store_n(&ctx.proc->io.pending, false, __ATOMIC_RELAXED);
                 }
 
                 ready_schedule_lock();
-                bool ret = __cfa_io_drain( proc );
+                bool ret = __cfa_io_drain( &ctx );
                 ready_schedule_unlock();
                 return ret;
@@ -287 +291 @@
         //=============================================================================================
         // submission
-        static inline void __submit( struct $io_context * ctx, __u32 idxs[], __u32 have, bool lazy) {
+        static inline void __submit_only( struct $io_context * ctx, __u32 idxs[], __u32 have) {
                 // We can proceed to the fast path
                 // Get the right objects
@@ -304 +308 @@
                 sq.to_submit += have;
 
-                ctx->proc->io.pending = true;
-                ctx->proc->io.dirty   = true;
+                __atomic_store_n(&ctx->proc->io.pending, true, __ATOMIC_RELAXED);
+                __atomic_store_n(&ctx->proc->io.dirty  , true, __ATOMIC_RELAXED);
+        }
+
+        static inline void __submit( struct $io_context * ctx, __u32 idxs[], __u32 have, bool lazy) {
+                __sub_ring_t & sq = ctx->sq;
+                __submit_only(ctx, idxs, have);
+
                 if(sq.to_submit > 30) {
                         __tls_stats()->io.flush.full++;
@@ -402 +412 @@
 // I/O Arbiter
 //=============================================================================================
-        static inline void block(__outstanding_io_queue & queue, __outstanding_io & item) {
+        static inline bool enqueue(__outstanding_io_queue & queue, __outstanding_io & item) {
+                bool was_empty;
+
                 // Lock the list, it's not thread safe
                 lock( queue.lock __cfaabi_dbg_ctx2 );
                 {
+                        was_empty = empty(queue.queue);
+
                         // Add our request to the list
                         add( queue.queue, item );
@@ -414 +428 @@
                 unlock( queue.lock );
 
-                wait( item.sem );
+                return was_empty;
         }
 
@@ -432 +446 @@
                 pa.want = want;
 
-                block(this.pending, (__outstanding_io&)pa);
+                enqueue(this.pending, (__outstanding_io&)pa);
+
+                wait( pa.sem );
 
                 return pa.ctx;
@@ -485 +501 @@
                 ei.lazy = lazy;
 
-                block(ctx->ext_sq, (__outstanding_io&)ei);
+                bool we = enqueue(ctx->ext_sq, (__outstanding_io&)ei);
+
+                __atomic_store_n(&ctx->proc->io.pending, true, __ATOMIC_SEQ_CST);
+
+                if( we ) {
+                        sigval_t value = { PREEMPT_IO };
+                        pthread_sigqueue(ctx->proc->kernel_thread, SIGUSR1, value);
+                }
+
+                wait( ei.sem );
 
                 __cfadbg_print_safe(io, "Kernel I/O : %u submitted from arbiter\n", have);
@@ -501 +526 @@
                                         __external_io & ei = (__external_io&)drop( ctx.ext_sq.queue );
 
-                                        __submit(&ctx, ei.idxs, ei.have, ei.lazy);
+                                        __submit_only(&ctx, ei.idxs, ei.have);
 
                                         post( ei.sem );

libcfa/src/concurrency/io/setup.cfa

@@ -39 +39 @@
 
 #else
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Waddress-of-packed-member"
         #include <errno.h>
         #include <stdint.h>
@@ -56 +58 @@
 
         #include "bitmanip.hfa"
-        #include "kernel_private.hfa"
+        #include "fstream.hfa"
+        #include "kernel/private.hfa"
         #include "thread.hfa"
+#pragma GCC diagnostic pop
 
         void ?{}(io_context_params & this) {
@@ -111 +115 @@
                 this.ext_sq.empty = true;
                 (this.ext_sq.queue){};
-                __io_uring_setup( this, cl.io.params, proc->idle_fd );
+                __io_uring_setup( this, cl.io.params, proc->idle_wctx.evfd );
                 __cfadbg_print_safe(io_core, "Kernel I/O : Created ring for io_context %u (%p)\n", this.fd, &this);
         }
@@ -121 +125 @@
                 __cfadbg_print_safe(io_core, "Kernel I/O : Destroyed ring for io_context %u\n", this.fd);
         }
-
-        extern void __disable_interrupts_hard();
-        extern void __enable_interrupts_hard();
 
         static void __io_uring_setup( $io_context & this, const io_context_params & params_in, int procfd ) {
@@ -213 +214 @@
 
                 // completion queue
+                cq.lock      = 0;
                 cq.head      = (volatile __u32 *)(((intptr_t)cq.ring_ptr) + params.cq_off.head);
                 cq.tail      = (volatile __u32 *)(((intptr_t)cq.ring_ptr) + params.cq_off.tail);
@@ -226 +228 @@
                         __cfadbg_print_safe(io_core, "Kernel I/O : registering %d for completion with ring %d\n", procfd, fd);
 
-                        __disable_interrupts_hard();
-
                         int ret = syscall( __NR_io_uring_register, fd, IORING_REGISTER_EVENTFD, &procfd, 1);
                         if (ret < 0) {
                                 abort("KERNEL ERROR: IO_URING EVENTFD REGISTER - %s\n", strerror(errno));
                         }
-
-                        __enable_interrupts_hard();
 
                         __cfadbg_print_safe(io_core, "Kernel I/O : registered %d for completion with ring %d\n", procfd, fd);
@@ -258 +256 @@
                 struct __sub_ring_t & sq = this.sq;
                 struct __cmp_ring_t & cq = this.cq;
+                {
+                        __u32 fhead = sq.free_ring.head;
+                        __u32 ftail = sq.free_ring.tail;
+
+                        __u32 total = *sq.num;
+                        __u32 avail = ftail - fhead;
+
+                        if(avail != total) abort | "Processor (" | (void*)this.proc | ") tearing down ring with" | (total - avail) | "entries allocated but not submitted, out of" | total;
+                }
 
                 // unmap the submit queue entries

libcfa/src/concurrency/io/types.hfa

@@ -23 +23 @@
 #include "bits/locks.hfa"
 #include "bits/queue.hfa"
+#include "iofwd.hfa"
 #include "kernel/fwd.hfa"
 
@@ -77 +78 @@
 
         struct __cmp_ring_t {
+                volatile bool lock;
+
                 // Head and tail of the ring
                 volatile __u32 * head;
@@ -170 +173 @@
         // void __ioctx_prepare_block($io_context & ctx);
 #endif
-
-//-----------------------------------------------------------------------
-// IO user data
-struct io_future_t {
-        future_t self;
-        __s32 result;
-};
-
-static inline {
-        thread$ * fulfil( io_future_t & this, __s32 result, bool do_unpark = true ) {
-                this.result = result;
-                return fulfil(this.self, do_unpark);
-        }
-
-        // Wait for the future to be fulfilled
-        bool wait     ( io_future_t & this ) { return wait     (this.self); }
-        void reset    ( io_future_t & this ) { return reset    (this.self); }
-        bool available( io_future_t & this ) { return available(this.self); }
-}

libcfa/src/concurrency/iofwd.hfa

@@ -19 +19 @@
 extern "C" {
         #include <asm/types.h>
+        #include <sys/stat.h> // needed for mode_t
         #if CFA_HAVE_LINUX_IO_URING_H
                 #include <linux/io_uring.h>
@@ -24 +25 @@
 }
 #include "bits/defs.hfa"
+#include "kernel/fwd.hfa"
 #include "time.hfa"
 
@@ -47 +49 @@
 
 struct cluster;
-struct io_future_t;
 struct $io_context;
 
@@ -57 +58 @@
 
 struct io_uring_sqe;
+
+//-----------------------------------------------------------------------
+// IO user data
+struct io_future_t {
+        future_t self;
+        __s32 result;
+};
+
+static inline {
+        thread$ * fulfil( io_future_t & this, __s32 result, bool do_unpark = true ) {
+                this.result = result;
+                return fulfil(this.self, do_unpark);
+        }
+
+        // Wait for the future to be fulfilled
+        bool wait     ( io_future_t & this ) { return wait     (this.self); }
+        void reset    ( io_future_t & this ) { return reset    (this.self); }
+        bool available( io_future_t & this ) { return available(this.self); }
+}
 
 //----------
@@ -133 +153 @@
 // Check if a function is blocks a only the user thread
 bool has_user_level_blocking( fptr_t func );
+
+#if CFA_HAVE_LINUX_IO_URING_H
+        static inline void zero_sqe(struct io_uring_sqe * sqe) {
+                sqe->flags = 0;
+                sqe->ioprio = 0;
+                sqe->fd = 0;
+                sqe->off = 0;
+                sqe->addr = 0;
+                sqe->len = 0;
+                sqe->fsync_flags = 0;
+                sqe->__pad2[0] = 0;
+                sqe->__pad2[1] = 0;
+                sqe->__pad2[2] = 0;
+                sqe->fd = 0;
+                sqe->off = 0;
+                sqe->addr = 0;
+                sqe->len = 0;
+        }
+#endif

libcfa/src/concurrency/kernel.cfa

@@ -19 +19 @@
 // #define __CFA_DEBUG_PRINT_RUNTIME_CORE__
 
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Waddress-of-packed-member"
+
 //C Includes
 #include <errno.h>
@@ -25 +28 @@
 #include <signal.h>
 #include <unistd.h>
+
 extern "C" {
         #include <sys/eventfd.h>
@@ -31 +35 @@
 
 //CFA Includes
-#include "kernel_private.hfa"
+#include "kernel/private.hfa"
 #include "preemption.hfa"
 #include "strstream.hfa"
@@ -40 +44 @@
 #define __CFA_INVOKE_PRIVATE__
 #include "invoke.h"
+#pragma GCC diagnostic pop
 
 #if !defined(__CFA_NO_STATISTICS__)
@@ -131 +136 @@
 static void mark_awake(__cluster_proc_list & idles, processor & proc);
 
-extern void __cfa_io_start( processor * );
-extern bool __cfa_io_drain( processor * );
+extern bool __cfa_io_drain( $io_context * );
 extern bool __cfa_io_flush( processor *, int min_comp );
-extern void __cfa_io_stop ( processor * );
 static inline bool __maybe_io_drain( processor * );
 
@@ -159 +162 @@
         verify(this);
 
-        io_future_t future; // used for idle sleep when io_uring is present
-        future.self.ptr = 1p;  // mark it as already fulfilled so we know if there is a pending request or not
-        eventfd_t idle_val;
-        iovec idle_iovec = { &idle_val, sizeof(idle_val) };
-
-        __cfa_io_start( this );
+        /* paranoid */ verify( this->idle_wctx.ftr   != 0p );
+        /* paranoid */ verify( this->idle_wctx.rdbuf != 0p );
+
+        // used for idle sleep when io_uring is present
+        // mark it as already fulfilled so we know if there is a pending request or not
+        this->idle_wctx.ftr->self.ptr = 1p;
+        iovec idle_iovec = { this->idle_wctx.rdbuf, sizeof(eventfd_t) };
 
         __cfadbg_print_safe(runtime_core, "Kernel : core %p starting\n", this);
@@ -231 +235 @@
                                 }
 
-                                idle_sleep( this, future, idle_iovec );
+                                idle_sleep( this, *this->idle_wctx.ftr, idle_iovec );
 
                                 // We were woken up, remove self from idle
@@ -251 +255 @@
                         if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
 
-                        if(this->io.pending && !this->io.dirty) {
+                        if(__atomic_load_n(&this->io.pending, __ATOMIC_RELAXED) && !__atomic_load_n(&this->io.dirty, __ATOMIC_RELAXED)) {
                                 __IO_STATS__(true, io.flush.dirty++; )
                                 __cfa_io_flush( this, 0 );
@@ -259 +263 @@
                 __cfadbg_print_safe(runtime_core, "Kernel : core %p stopping\n", this);
         }
-
-        for(int i = 0; !available(future); i++) {
-                if(i > 1000) __cfaabi_dbg_write( "ERROR: kernel has bin spinning on a flush after exit loop.\n", 60);
-                __cfa_io_flush( this, 1 );
-        }
-
-        __cfa_io_stop( this );
 
         post( this->terminated );
@@ -634 +631 @@
 
         int fd = 1;
-        if( __atomic_load_n(&fdp->fd, __ATOMIC_SEQ_CST) != 1 ) {
-                fd = __atomic_exchange_n(&fdp->fd, 1, __ATOMIC_RELAXED);
+        if( __atomic_load_n(&fdp->sem, __ATOMIC_SEQ_CST) != 1 ) {
+                fd = __atomic_exchange_n(&fdp->sem, 1, __ATOMIC_RELAXED);
         }
 
@@ -677 +674 @@
         __cfadbg_print_safe(runtime_core, "Kernel : waking Processor %p\n", this);
 
-        this->idle_wctx.fd = 1;
+        this->idle_wctx.sem = 1;
 
         eventfd_t val;
         val = 1;
-        eventfd_write( this->idle_fd, val );
+        eventfd_write( this->idle_wctx.evfd, val );
 
         /* paranoid */ verify( ! __preemption_enabled() );
@@ -689 +686 @@
         // Tell everyone we are ready to go do sleep
         for() {
-                int expected = this->idle_wctx.fd;
+                int expected = this->idle_wctx.sem;
 
                 // Someone already told us to wake-up! No time for a nap.
@@ -695 +692 @@
 
                 // Try to mark that we are going to sleep
-                if(__atomic_compare_exchange_n(&this->idle_wctx.fd, &expected, this->idle_fd, false,  __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ) {
+                if(__atomic_compare_exchange_n(&this->idle_wctx.sem, &expected, this->idle_wctx.evfd, false,  __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) ) {
                         // Every one agreed, taking a nap
                         break;
@@ -713 +710 @@
                 {
                         eventfd_t val;
-                        ssize_t ret = read( this->idle_fd, &val, sizeof(val) );
+                        ssize_t ret = read( this->idle_wctx.evfd, &val, sizeof(val) );
                         if(ret < 0) {
                                 switch((int)errno) {
@@ -740 +737 @@
                         reset(future);
 
-                        __kernel_read(this, future, iov, this->idle_fd );
+                        __kernel_read(this, future, iov, this->idle_wctx.evfd );
                 }
 
@@ -750 +747 @@
         __STATS__(true, ready.sleep.halts++; )
 
-        proc.idle_wctx.fd = 0;
+        proc.idle_wctx.sem = 0;
 
         /* paranoid */ verify( ! __preemption_enabled() );
@@ -842 +839 @@
                 if(head == tail) return false;
                 ready_schedule_lock();
-                ret = __cfa_io_drain( proc );
+                ret = __cfa_io_drain( ctx );
                 ready_schedule_unlock();
         #endif

libcfa/src/concurrency/kernel.hfa

@@ -48 +48 @@
 extern struct cluster * mainCluster;
 
-// Processor id, required for scheduling threads
-
-
+// Coroutine used py processors for the 2-step context switch
 coroutine processorCtx_t {
         struct processor * proc;
 };
 
-
+struct io_future_t;
+
+// Information needed for idle sleep
 struct __fd_waitctx {
-        volatile int fd;
+        // semaphore/future like object
+        // values can be 0, 1 or some file descriptor.
+        // 0 - is the default state
+        // 1 - means the proc should wake-up immediately
+        // FD - means the proc is going asleep and should be woken by writing to the FD.
+        volatile int sem;
+
+        // The event FD that corresponds to this processor
+        int evfd;
+
+        // buffer into which the proc will read from evfd
+        // unused if not using io_uring for idle sleep
+        void * rdbuf;
+
+        // future use to track the read of the eventfd
+        // unused if not using io_uring for idle sleep
+        io_future_t * ftr;
 };
 
@@ -92 +108 @@
         struct {
                 $io_context * ctx;
-                bool pending;
-                bool dirty;
+                unsigned id;
+                unsigned target;
+                volatile bool pending;
+                volatile bool dirty;
         } io;
 
@@ -103 +121 @@
         bool pending_preemption;
 
-        // Idle lock (kernel semaphore)
-        int idle_fd;
-
-        // Idle waitctx
+        // context for idle sleep
         struct __fd_waitctx idle_wctx;
 
@@ -155 +170 @@
 void ^?{}(__intrusive_lane_t & this);
 
-// Aligned timestamps which are used by the relaxed ready queue
+// Aligned timestamps which are used by the ready queue and io subsystem
 struct __attribute__((aligned(128))) __timestamp_t {
         volatile unsigned long long tv;
@@ -161 +176 @@
 };
 
+static inline void  ?{}(__timestamp_t & this) { this.tv = 0; this.ma = 0; }
+static inline void ^?{}(__timestamp_t &) {}
+
+
 struct __attribute__((aligned(16))) __cache_id_t {
         volatile unsigned id;
 };
-
-// Aligned timestamps which are used by the relaxed ready queue
-struct __attribute__((aligned(128))) __help_cnts_t {
-        volatile unsigned long long src;
-        volatile unsigned long long dst;
-        volatile unsigned long long tri;
-};
-
-static inline void  ?{}(__timestamp_t & this) { this.tv = 0; this.ma = 0; }
-static inline void ^?{}(__timestamp_t &) {}
-
-struct __attribute__((aligned(128))) __ready_queue_caches_t;
-void  ?{}(__ready_queue_caches_t & this);
-void ^?{}(__ready_queue_caches_t & this);
-
-//TODO adjust cache size to ARCHITECTURE
-// Structure holding the ready queue
-struct __ready_queue_t {
-        // Data tracking the actual lanes
-        // On a seperate cacheline from the used struct since
-        // used can change on each push/pop but this data
-        // only changes on shrink/grow
-        struct {
-                // Arary of lanes
-                __intrusive_lane_t * volatile data;
-
-                // Array of times
-                __timestamp_t * volatile tscs;
-
-                __cache_id_t * volatile caches;
-
-                // Array of stats
-                __help_cnts_t * volatile help;
-
-                // Number of lanes (empty or not)
-                volatile size_t count;
-        } lanes;
-};
-
-void  ?{}(__ready_queue_t & this);
-void ^?{}(__ready_queue_t & this);
-#if !defined(__CFA_NO_STATISTICS__)
-        unsigned cnt(const __ready_queue_t & this, unsigned idx);
-#endif
 
 // Idle Sleep
@@ -233 +208 @@
 // Cluster
 struct __attribute__((aligned(128))) cluster {
-        // Ready queue for threads
-        __ready_queue_t ready_queue;
+        struct {
+                struct {
+                        // Arary of subqueues
+                        __intrusive_lane_t * data;
+
+                        // Time since subqueues were processed
+                        __timestamp_t * tscs;
+
+                        // Number of subqueue / timestamps
+                        size_t count;
+                } readyQ;
+
+                struct {
+                        // Array of $io_
+                        $io_context ** data;
+
+                        // Time since subqueues were processed
+                        __timestamp_t * tscs;
+
+                        // Number of I/O subqueues
+                        size_t count;
+                } io;
+
+                // Cache each kernel thread belongs to
+                __cache_id_t * caches;
+        } sched;
+
+        // // Ready queue for threads
+        // __ready_queue_t ready_queue;
 
         // Name of the cluster

libcfa/src/concurrency/kernel/fwd.hfa

@@ -347 +347 @@
                                         struct oneshot * want = expected == 0p ? 1p : 2p;
                                         if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
-                                                if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return 0p; }
+                                                if( expected == 0p ) { return 0p; }
                                                 thread$ * ret = post( *expected, do_unpark );
                                                 __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);

libcfa/src/concurrency/kernel/private.hfa

@@ -5 +5 @@
 // file "LICENCE" distributed with Cforall.
 //
-// kernel_private.hfa --
+// kernel/private.hfa --
 //
 // Author           : Thierry Delisle
@@ -17 +17 @@
 
 #if !defined(__cforall_thread__)
-        #error kernel_private.hfa should only be included in libcfathread source
+        #error kernel/private.hfa should only be included in libcfathread source
 #endif
 
@@ -33 +33 @@
 #else
         #ifndef _GNU_SOURCE
-        #error kernel_private requires gnu_source
+        #error kernel/private requires gnu_source
         #endif
         #include <sched.h>
@@ -59 +59 @@
 
 extern bool __preemption_enabled();
+
+enum {
+        PREEMPT_NORMAL    = 0,
+        PREEMPT_TERMINATE = 1,
+        PREEMPT_IO = 2,
+};
 
 static inline void __disable_interrupts_checked() {
@@ -359 +365 @@
 void ready_queue_shrink(struct cluster * cltr);
 
+//-----------------------------------------------------------------------
+// Decrease the width of the ready queue (number of lanes) by 4
+void ready_queue_close(struct cluster * cltr);
 
 // Local Variables: //

libcfa/src/concurrency/kernel/startup.cfa

@@ -18 +18 @@
 
 // C Includes
-#include <errno.h>                                                                              // errno
+#include <errno.h>                                      // errno
 #include <signal.h>
-#include <string.h>                                                                             // strerror
-#include <unistd.h>                                                                             // sysconf
+#include <string.h>                                     // strerror
+#include <unistd.h>                                     // sysconf
 
 extern "C" {
-        #include <limits.h>                                                                     // PTHREAD_STACK_MIN
-        #include <unistd.h>                                                                     // syscall
-        #include <sys/eventfd.h>                                                        // eventfd
-        #include <sys/mman.h>                                                           // mprotect
-        #include <sys/resource.h>                                                       // getrlimit
+        #include <limits.h>                             // PTHREAD_STACK_MIN
+        #include <unistd.h>                             // syscall
+        #include <sys/eventfd.h>                        // eventfd
+        #include <sys/mman.h>                           // mprotect
+        #include <sys/resource.h>                       // getrlimit
 }
 
 // CFA Includes
-#include "kernel_private.hfa"
-#include "startup.hfa"                                                                  // STARTUP_PRIORITY_XXX
+#include "kernel/private.hfa"
+#include "iofwd.hfa"
+#include "startup.hfa"                                  // STARTUP_PRIORITY_XXX
 #include "limits.hfa"
 #include "math.hfa"
@@ -97 +98 @@
 extern void __kernel_alarm_startup(void);
 extern void __kernel_alarm_shutdown(void);
+extern void __cfa_io_start( processor * );
+extern void __cfa_io_stop ( processor * );
 
 //-----------------------------------------------------------------------------
@@ -111 +114 @@
 KERNEL_STORAGE(__stack_t,            mainThreadCtx);
 KERNEL_STORAGE(__scheduler_RWLock_t, __scheduler_lock);
+KERNEL_STORAGE(eventfd_t,            mainIdleEventFd);
+KERNEL_STORAGE(io_future_t,          mainIdleFuture);
 #if !defined(__CFA_NO_STATISTICS__)
 KERNEL_STORAGE(__stats_t, mainProcStats);
@@ -224 +229 @@
         (*mainProcessor){};
 
+        mainProcessor->idle_wctx.rdbuf = &storage_mainIdleEventFd;
+        mainProcessor->idle_wctx.ftr   = (io_future_t*)&storage_mainIdleFuture;
+        /* paranoid */ verify( sizeof(storage_mainIdleEventFd) == sizeof(eventfd_t) );
+
         register_tls( mainProcessor );
+        __cfa_io_start( mainProcessor );
 
         // Start by initializing the main thread
@@ -304 +314 @@
         mainProcessor->local_data = 0p;
 
+        __cfa_io_stop( mainProcessor );
         unregister_tls( mainProcessor );
 
@@ -355 +366 @@
         register_tls( proc );
 
+        __cfa_io_start( proc );
+
+        // used for idle sleep when io_uring is present
+        io_future_t future;
+        eventfd_t idle_buf;
+        proc->idle_wctx.ftr = &future;
+        proc->idle_wctx.rdbuf = &idle_buf;
+
+
         // SKULLDUGGERY: We want to create a context for the processor coroutine
         // which is needed for the 2-step context switch. However, there is no reason
@@ -381 +401 @@
         // Main routine of the core returned, the core is now fully terminated
         __cfadbg_print_safe(runtime_core, "Kernel : core %p main ended (%p)\n", proc, &proc->runner);
+
+        __cfa_io_stop( proc );
 
         #if !defined(__CFA_NO_STATISTICS__)
@@ -515 +537 @@
         this.rdq.its = 0;
         this.rdq.itr = 0;
-        this.rdq.id  = MAX;
+        this.rdq.id  = 0;
         this.rdq.target = MAX;
         this.rdq.last = MAX;
@@ -532 +554 @@
         this.local_data = 0p;
 
-        this.idle_fd = eventfd(0, 0);
-        if (idle_fd < 0) {
+        idle_wctx.evfd = eventfd(0, 0);
+        if (idle_wctx.evfd < 0) {
                 abort("KERNEL ERROR: PROCESSOR EVENTFD - %s\n", strerror(errno));
         }
 
-        this.idle_wctx.fd = 0;
+        idle_wctx.sem = 0;
 
         // I'm assuming these two are reserved for standard input and output
         // so I'm using them as sentinels with idle_wctx.
-        /* paranoid */ verify( this.idle_fd != 0 );
-        /* paranoid */ verify( this.idle_fd != 1 );
+        /* paranoid */ verify( idle_wctx.evfd != 0 );
+        /* paranoid */ verify( idle_wctx.evfd != 1 );
 
         #if !defined(__CFA_NO_STATISTICS__)
@@ -554 +576 @@
 // Not a ctor, it just preps the destruction but should not destroy members
 static void deinit(processor & this) {
-        close(this.idle_fd);
+        close(this.idle_wctx.evfd);
 }
 
@@ -605 +627 @@
         this.name = name;
         this.preemption_rate = preemption_rate;
-        ready_queue{};
+        this.sched.readyQ.data = 0p;
+        this.sched.readyQ.tscs = 0p;
+        this.sched.readyQ.count = 0;
+        this.sched.io.tscs = 0p;
+        this.sched.caches = 0p;
 
         #if !defined(__CFA_NO_STATISTICS__)
@@ -644 +670 @@
         // Unlock the RWlock
         ready_mutate_unlock( last_size );
+
+        ready_queue_close( &this );
+        /* paranoid */ verify( this.sched.readyQ.data == 0p );
+        /* paranoid */ verify( this.sched.readyQ.tscs == 0p );
+        /* paranoid */ verify( this.sched.readyQ.count == 0 );
+        /* paranoid */ verify( this.sched.io.tscs == 0p );
+        /* paranoid */ verify( this.sched.caches == 0p );
+
         enable_interrupts( false ); // Don't poll, could be in main cluster
+
 
         #if !defined(__CFA_NO_STATISTICS__)
@@ -736 +771 @@
         check( pthread_attr_init( &attr ), "pthread_attr_init" ); // initialize attribute
 
-        size_t stacksize = DEFAULT_STACK_SIZE;
+        size_t stacksize = max( PTHREAD_STACK_MIN, DEFAULT_STACK_SIZE );
 
         void * stack;

libcfa/src/concurrency/locks.cfa

@@ -19 +19 @@
 
 #include "locks.hfa"
-#include "kernel_private.hfa"
+#include "kernel/private.hfa"
 
 #include <kernel.hfa>

libcfa/src/concurrency/locks.hfa

@@ -164 +164 @@
 }
 
-static inline bool lock(linear_backoff_then_block_lock & this) with(this) {
+static inline void lock(linear_backoff_then_block_lock & this) with(this) {
         // if owner just return
-        if (active_thread() == owner) return true;
+        if (active_thread() == owner) return;
         size_t compare_val = 0;
         int spin = spin_start;
@@ -172 +172 @@
         for( ;; ) {
                 compare_val = 0;
-                if (internal_try_lock(this, compare_val)) return true;
+                if (internal_try_lock(this, compare_val)) return;
                 if (2 == compare_val) break;
                 for (int i = 0; i < spin; i++) Pause();
@@ -179 +179 @@
         }
 
-        if(2 != compare_val && try_lock_contention(this)) return true;
+        if(2 != compare_val && try_lock_contention(this)) return;
         // block until signalled
-        while (block(this)) if(try_lock_contention(this)) return true;
-
-        // this should never be reached as block(this) always returns true
-        return false;
+        while (block(this)) if(try_lock_contention(this)) return;
 }
 

libcfa/src/concurrency/monitor.cfa

@@ -22 +22 @@
 #include <inttypes.h>
 
-#include "kernel_private.hfa"
+#include "kernel/private.hfa"
 
 #include "bits/algorithm.hfa"

libcfa/src/concurrency/mutex.cfa

@@ -21 +21 @@
 #include "mutex.hfa"
 
-#include "kernel_private.hfa"
+#include "kernel/private.hfa"
 
 //-----------------------------------------------------------------------------

libcfa/src/concurrency/mutex_stmt.hfa

@@ -12 +12 @@
 };
 
+
+struct __mutex_stmt_lock_guard {
+    void ** lockarr;
+    __lock_size_t count;
+};
+
+static inline void ?{}( __mutex_stmt_lock_guard & this, void * lockarr [], __lock_size_t count  ) {
+    this.lockarr = lockarr;
+    this.count = count;
+
+    // Sort locks based on address
+    __libcfa_small_sort(this.lockarr, count);
+
+    // acquire locks in order
+    // for ( size_t i = 0; i < count; i++ ) {
+    //     lock(*this.lockarr[i]);
+    // }
+}
+
+static inline void ^?{}( __mutex_stmt_lock_guard & this ) with(this) {
+    // for ( size_t i = count; i > 0; i-- ) {
+    //     unlock(*lockarr[i - 1]);
+    // }
+}
+
 forall(L & | is_lock(L)) {
-
-    struct __mutex_stmt_lock_guard {
-        L ** lockarr;
-        __lock_size_t count;
-    };
-    
-    static inline void ?{}( __mutex_stmt_lock_guard(L) & this, L * lockarr [], __lock_size_t count  ) {
-        this.lockarr = lockarr;
-        this.count = count;
-
-        // Sort locks based on address
-        __libcfa_small_sort(this.lockarr, count);
-
-        // acquire locks in order
-        for ( size_t i = 0; i < count; i++ ) {
-            lock(*this.lockarr[i]);
-        }
-    }
-    
-    static inline void ^?{}( __mutex_stmt_lock_guard(L) & this ) with(this) {
-        for ( size_t i = count; i > 0; i-- ) {
-            unlock(*lockarr[i - 1]);
-        }
-    }
 
     struct scoped_lock {
@@ -51 +52 @@
     }
 
-    static inline L * __get_ptr( L & this ) {
+    static inline void * __get_mutexstmt_lock_ptr( L & this ) {
         return &this;
     }
 
-    static inline L __get_type( L & this );
+    static inline L __get_mutexstmt_lock_type( L & this );
 
-    static inline L __get_type( L * this );
+    static inline L __get_mutexstmt_lock_type( L * this );
 }

libcfa/src/concurrency/preemption.cfa

@@ -10 +10 @@
 // Created On       : Mon Jun 5 14:20:42 2017
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Fri Nov  6 07:42:13 2020
-// Update Count     : 54
+// Last Modified On : Thu Feb 17 11:18:57 2022
+// Update Count     : 59
 //
 
@@ -31 +31 @@
 #include "bits/debug.hfa"
 #include "bits/signal.hfa"
-#include "kernel_private.hfa"
+#include "kernel/private.hfa"
 
 
@@ -97 +97 @@
 }
 
-enum {
-        PREEMPT_NORMAL    = 0,
-        PREEMPT_TERMINATE = 1,
-};
-
 //=============================================================================================
 // Kernel Preemption logic
@@ -243 +238 @@
 //----------
 // special case for preemption since used often
-bool __preemption_enabled() {
+__attribute__((optimize("no-reorder-blocks"))) bool __preemption_enabled() {
         // create a assembler label before
         // marked as clobber all to avoid movement
@@ -664 +659 @@
         choose(sfp->si_value.sival_int) {
                 case PREEMPT_NORMAL   : ;// Normal case, nothing to do here
+                case PREEMPT_IO       : ;// I/O asked to stop spinning, nothing to do here
                 case PREEMPT_TERMINATE: verify( __atomic_load_n( &__cfaabi_tls.this_processor->do_terminate, __ATOMIC_SEQ_CST ) );
                 default:

libcfa/src/concurrency/ready_queue.cfa

@@ -20 +20 @@
 
 
-// #define USE_RELAXED_FIFO
-// #define USE_WORK_STEALING
-// #define USE_CPU_WORK_STEALING
 #define USE_AWARE_STEALING
 
 #include "bits/defs.hfa"
 #include "device/cpu.hfa"
-#include "kernel_private.hfa"
-
-#include "stdlib.hfa"
+#include "kernel/cluster.hfa"
+#include "kernel/private.hfa"
+
 #include "limits.hfa"
-#include "math.hfa"
-
-#include <errno.h>
-#include <unistd.h>
-
-extern "C" {
-        #include <sys/syscall.h>  // __NR_xxx
-}
+
+// #include <errno.h>
+// #include <unistd.h>
 
 #include "ready_subqueue.hfa"
@@ -50 +42 @@
 #endif
 
-// No overriden function, no environment variable, no define
-// fall back to a magic number
-#ifndef __CFA_MAX_PROCESSORS__
-        #define __CFA_MAX_PROCESSORS__ 1024
-#endif
-
-#if   defined(USE_AWARE_STEALING)
-        #define READYQ_SHARD_FACTOR 2
-        #define SEQUENTIAL_SHARD 2
-#elif defined(USE_CPU_WORK_STEALING)
-        #define READYQ_SHARD_FACTOR 2
-#elif defined(USE_RELAXED_FIFO)
-        #define BIAS 4
-        #define READYQ_SHARD_FACTOR 4
-        #define SEQUENTIAL_SHARD 1
-#elif defined(USE_WORK_STEALING)
-        #define READYQ_SHARD_FACTOR 2
-        #define SEQUENTIAL_SHARD 2
-#else
-        #error no scheduling strategy selected
-#endif
-
 static inline struct thread$ * try_pop(struct cluster * cltr, unsigned w __STATS(, __stats_readyQ_pop_t & stats));
 static inline struct thread$ * try_pop(struct cluster * cltr, unsigned i, unsigned j __STATS(, __stats_readyQ_pop_t & stats));
 static inline struct thread$ * search(struct cluster * cltr);
-static inline [unsigned, bool] idx_from_r(unsigned r, unsigned preferred);
-
-
-// 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;
-}
-
-#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
-        // No forward declaration needed
-        #define __kernel_rseq_register rseq_register_current_thread
-        #define __kernel_rseq_unregister rseq_unregister_current_thread
-#elif defined(CFA_HAVE_LINUX_RSEQ_H)
-        static void __kernel_raw_rseq_register  (void);
-        static void __kernel_raw_rseq_unregister(void);
-
-        #define __kernel_rseq_register __kernel_raw_rseq_register
-        #define __kernel_rseq_unregister __kernel_raw_rseq_unregister
-#else
-        // No forward declaration needed
-        // No initialization needed
-        static inline void noop(void) {}
-
-        #define __kernel_rseq_register noop
-        #define __kernel_rseq_unregister noop
-#endif
-
-//=======================================================================
-// Cluster wide reader-writer lock
-//=======================================================================
-void  ?{}(__scheduler_RWLock_t & this) {
-        this.max   = __max_processors();
-        this.alloc = 0;
-        this.ready = 0;
-        this.data  = alloc(this.max);
-        this.write_lock  = false;
-
-        /*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);
-}
-
-
-//=======================================================================
-// Lock-Free registering/unregistering of threads
-unsigned register_proc_id( void ) with(*__scheduler_lock) {
-        __kernel_rseq_register();
-
-        bool * handle = (bool *)&kernelTLS().sched_lock;
-
-        // 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++) {
-                bool * volatile * cell = (bool * volatile *)&data[i]; // Cforall is bugged and the double volatiles causes problems
-                /* paranoid */ verify( handle != *cell );
-
-                bool * null = 0p; // Re-write every loop since compare thrashes it
-                if( __atomic_load_n(cell, (int)__ATOMIC_RELAXED) == null
-                        && __atomic_compare_exchange_n( cell, &null, handle, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
-                        /* paranoid */ verify(i < ready);
-                        /* paranoid */ verify( (kernelTLS().sched_id = i, true) );
-                        return 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.
-        data[n] = handle;
-        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();
-        }
-
-        // Return new spot.
-        /* paranoid */ verify(n < ready);
-        /* paranoid */ verify( (kernelTLS().sched_id = n, true) );
-        return n;
-}
-
-void unregister_proc_id( unsigned id ) with(*__scheduler_lock) {
-        /* paranoid */ verify(id < ready);
-        /* paranoid */ verify(id == kernelTLS().sched_id);
-        /* paranoid */ verify(data[id] == &kernelTLS().sched_lock);
-
-        bool * volatile * cell = (bool * volatile *)&data[id]; // Cforall is bugged and the double volatiles causes problems
-
-        __atomic_store_n(cell, 0p, __ATOMIC_RELEASE);
-
-        __kernel_rseq_unregister();
-}
-
-//-----------------------------------------------------------------------
-// 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( &write_lock );
-
-        // Make sure we won't deadlock ourself
-        // Checking before acquiring the writer lock isn't safe
-        // because someone else could have locked us.
-        /* paranoid */ verify( ! kernelTLS().sched_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++) {
-                volatile bool * llock = data[i];
-                if(llock) __atomic_acquire( llock );
-        }
-
-        /* 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++) {
-                volatile bool * llock = data[i];
-                if(llock) __atomic_store_n(llock, (bool)false, __ATOMIC_RELEASE);
-        }
-
-        // Step 2 : release global lock
-        /*paranoid*/ assert(true == write_lock);
-        __atomic_store_n(&write_lock, (bool)false, __ATOMIC_RELEASE);
-
-        /* paranoid */ verify( ! __preemption_enabled() );
-}
-
-//=======================================================================
-// caches handling
-
-struct __attribute__((aligned(128))) __ready_queue_caches_t {
-        // Count States:
-        // - 0  : No one is looking after this cache
-        // - 1  : No one is looking after this cache, BUT it's not empty
-        // - 2+ : At least one processor is looking after this cache
-        volatile unsigned count;
-};
-
-void  ?{}(__ready_queue_caches_t & this) { this.count = 0; }
-void ^?{}(__ready_queue_caches_t & this) {}
-
-static inline void depart(__ready_queue_caches_t & cache) {
-        /* paranoid */ verify( cache.count > 1);
-        __atomic_fetch_add(&cache.count, -1, __ATOMIC_SEQ_CST);
-        /* paranoid */ verify( cache.count != 0);
-        /* paranoid */ verify( cache.count < 65536 ); // This verify assumes no cluster will have more than 65000 kernel threads mapped to a single cache, which could be correct but is super weird.
-}
-
-static inline void arrive(__ready_queue_caches_t & cache) {
-        // for() {
-        //      unsigned expected = cache.count;
-        //      unsigned desired  = 0 == expected ? 2 : expected + 1;
-        // }
-}
 
 //=======================================================================
 // Cforall Ready Queue used for scheduling
 //=======================================================================
-unsigned long long moving_average(unsigned long long currtsc, unsigned long long instsc, unsigned long long old_avg) {
-        /* paranoid */ verifyf( currtsc < 45000000000000000, "Suspiciously large current time: %'llu (%llx)\n", currtsc, currtsc );
-        /* paranoid */ verifyf( instsc  < 45000000000000000, "Suspiciously large insert time: %'llu (%llx)\n", instsc, instsc );
-        /* paranoid */ verifyf( old_avg < 15000000000000, "Suspiciously large previous average: %'llu (%llx)\n", old_avg, old_avg );
-
-        const unsigned long long new_val = currtsc > instsc ? currtsc - instsc : 0;
-        const unsigned long long total_weight = 16;
-        const unsigned long long new_weight   = 4;
-        const unsigned long long old_weight = total_weight - new_weight;
-        const unsigned long long ret = ((new_weight * new_val) + (old_weight * old_avg)) / total_weight;
-        return ret;
-}
-
-void ?{}(__ready_queue_t & this) with (this) {
-        #if defined(USE_CPU_WORK_STEALING)
-                lanes.count = cpu_info.hthrd_count * READYQ_SHARD_FACTOR;
-                lanes.data = alloc( lanes.count );
-                lanes.tscs = alloc( lanes.count );
-                lanes.help = alloc( cpu_info.hthrd_count );
-
-                for( idx; (size_t)lanes.count ) {
-                        (lanes.data[idx]){};
-                        lanes.tscs[idx].tv = rdtscl();
-                        lanes.tscs[idx].ma = rdtscl();
-                }
-                for( idx; (size_t)cpu_info.hthrd_count ) {
-                        lanes.help[idx].src = 0;
-                        lanes.help[idx].dst = 0;
-                        lanes.help[idx].tri = 0;
-                }
-        #else
-                lanes.data   = 0p;
-                lanes.tscs   = 0p;
-                lanes.caches = 0p;
-                lanes.help   = 0p;
-                lanes.count  = 0;
-        #endif
-}
-
-void ^?{}(__ready_queue_t & this) with (this) {
-        #if !defined(USE_CPU_WORK_STEALING)
-                verify( SEQUENTIAL_SHARD == lanes.count );
-        #endif
-
-        free(lanes.data);
-        free(lanes.tscs);
-        free(lanes.caches);
-        free(lanes.help);
-}
-
-//-----------------------------------------------------------------------
-#if defined(USE_AWARE_STEALING)
-        __attribute__((hot)) void push(struct cluster * cltr, struct thread$ * thrd, unpark_hint hint) with (cltr->ready_queue) {
-                processor * const proc = kernelTLS().this_processor;
-                const bool external = (!proc) || (cltr != proc->cltr);
-                const bool remote   = hint == UNPARK_REMOTE;
-
-                unsigned i;
-                if( external || remote ) {
-                        // Figure out where thread was last time and make sure it's valid
-                        /* paranoid */ verify(thrd->preferred >= 0);
-                        if(thrd->preferred * READYQ_SHARD_FACTOR < lanes.count) {
-                                /* paranoid */ verify(thrd->preferred * READYQ_SHARD_FACTOR < lanes.count);
-                                unsigned start = thrd->preferred * READYQ_SHARD_FACTOR;
-                                do {
-                                        unsigned r = __tls_rand();
-                                        i = start + (r % READYQ_SHARD_FACTOR);
-                                        /* paranoid */ verify( i < lanes.count );
-                                        // If we can't lock it retry
-                                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
-                        } else {
-                                do {
-                                        i = __tls_rand() % lanes.count;
-                                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
-                        }
+// void ?{}(__ready_queue_t & this) with (this) {
+//      lanes.data   = 0p;
+//      lanes.tscs   = 0p;
+//      lanes.caches = 0p;
+//      lanes.count  = 0;
+// }
+
+// void ^?{}(__ready_queue_t & this) with (this) {
+//      free(lanes.data);
+//      free(lanes.tscs);
+//      free(lanes.caches);
+// }
+
+//-----------------------------------------------------------------------
+__attribute__((hot)) void push(struct cluster * cltr, struct thread$ * thrd, unpark_hint hint) with (cltr->sched) {
+        processor * const proc = kernelTLS().this_processor;
+        const bool external = (!proc) || (cltr != proc->cltr);
+        const bool remote   = hint == UNPARK_REMOTE;
+        const size_t lanes_count = readyQ.count;
+
+        /* paranoid */ verify( __shard_factor.readyq > 0 );
+        /* paranoid */ verify( lanes_count > 0 );
+
+        unsigned i;
+        if( external || remote ) {
+                // Figure out where thread was last time and make sure it's valid
+                /* paranoid */ verify(thrd->preferred >= 0);
+                unsigned start = thrd->preferred * __shard_factor.readyq;
+                if(start < lanes_count) {
+                        do {
+                                unsigned r = __tls_rand();
+                                i = start + (r % __shard_factor.readyq);
+                                /* paranoid */ verify( i < lanes_count );
+                                // If we can't lock it retry
+                        } while( !__atomic_try_acquire( &readyQ.data[i].lock ) );
                 } else {
                         do {
-                                unsigned r = proc->rdq.its++;
-                                i = proc->rdq.id + (r % READYQ_SHARD_FACTOR);
-                                /* paranoid */ verify( i < lanes.count );
-                                // If we can't lock it retry
-                        } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
-                }
-
-                // Actually push it
-                push(lanes.data[i], thrd);
-
-                // Unlock and return
-                __atomic_unlock( &lanes.data[i].lock );
-
-                #if !defined(__CFA_NO_STATISTICS__)
-                        if(unlikely(external || remote)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.success, 1, __ATOMIC_RELAXED);
-                        else __tls_stats()->ready.push.local.success++;
-                #endif
-        }
-
-        static inline unsigned long long calc_cutoff(const unsigned long long ctsc, const processor * proc, __ready_queue_t & rdq) {
-                unsigned start = proc->rdq.id;
-                unsigned long long max = 0;
-                for(i; READYQ_SHARD_FACTOR) {
-                        unsigned long long ptsc = ts(rdq.lanes.data[start + i]);
-                        if(ptsc != -1ull) {
-                                /* paranoid */ verify( start + i < rdq.lanes.count );
-                                unsigned long long tsc = moving_average(ctsc, ptsc, rdq.lanes.tscs[start + i].ma);
-                                if(tsc > max) max = tsc;
-                        }
-                }
-                return (max + 2 * max) / 2;
-        }
-
-        __attribute__((hot)) struct thread$ * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
-                /* paranoid */ verify( lanes.count > 0 );
-                /* paranoid */ verify( kernelTLS().this_processor );
-                /* paranoid */ verify( kernelTLS().this_processor->rdq.id < lanes.count );
-
-                processor * const proc = kernelTLS().this_processor;
-                unsigned this = proc->rdq.id;
-                /* paranoid */ verify( this < lanes.count );
-                __cfadbg_print_safe(ready_queue, "Kernel : pop from %u\n", this);
-
-                // Figure out the current cpu and make sure it is valid
-                const int cpu = __kernel_getcpu();
-                /* paranoid */ verify(cpu >= 0);
-                /* paranoid */ verify(cpu < cpu_info.hthrd_count);
-                unsigned this_cache = cpu_info.llc_map[cpu].cache;
-
-                // Super important: don't write the same value over and over again
-                // We want to maximise our chances that his particular values stays in cache
-                if(lanes.caches[this / READYQ_SHARD_FACTOR].id != this_cache)
-                        __atomic_store_n(&lanes.caches[this / READYQ_SHARD_FACTOR].id, this_cache, __ATOMIC_RELAXED);
-
-                const unsigned long long ctsc = rdtscl();
-
-                if(proc->rdq.target == MAX) {
-                        uint64_t chaos = __tls_rand();
-                        unsigned ext = chaos & 0xff;
-                        unsigned other  = (chaos >> 8) % (lanes.count);
-
-                        if(ext < 3 || __atomic_load_n(&lanes.caches[other / READYQ_SHARD_FACTOR].id, __ATOMIC_RELAXED) == this_cache) {
-                                proc->rdq.target = other;
-                        }
-                }
-                else {
-                        const unsigned target = proc->rdq.target;
-                        __cfadbg_print_safe(ready_queue, "Kernel : %u considering helping %u, tcsc %llu\n", this, target, lanes.tscs[target].tv);
-                        /* paranoid */ verify( lanes.tscs[target].tv != MAX );
-                        if(target < lanes.count) {
-                                const unsigned long long cutoff = calc_cutoff(ctsc, proc, cltr->ready_queue);
-                                const unsigned long long age = moving_average(ctsc, lanes.tscs[target].tv, lanes.tscs[target].ma);
-                                __cfadbg_print_safe(ready_queue, "Kernel : Help attempt on %u from %u, age %'llu vs cutoff %'llu, %s\n", target, this, age, cutoff, age > cutoff ? "yes" : "no");
-                                if(age > cutoff) {
-                                        thread$ * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
-                                        if(t) return t;
-                                }
-                        }
-                        proc->rdq.target = MAX;
-                }
-
-                for(READYQ_SHARD_FACTOR) {
-                        unsigned i = this + (proc->rdq.itr++ % READYQ_SHARD_FACTOR);
-                        if(thread$ * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t;
-                }
-
-                // All lanes where empty return 0p
-                return 0p;
-
-        }
-        __attribute__((hot)) struct thread$ * pop_slow(struct cluster * cltr) with (cltr->ready_queue) {
-                unsigned i = __tls_rand() % lanes.count;
-                return try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.steal));
-        }
-        __attribute__((hot)) struct thread$ * pop_search(struct cluster * cltr) {
-                return search(cltr);
-        }
-#endif
-#if defined(USE_CPU_WORK_STEALING)
-        __attribute__((hot)) void push(struct cluster * cltr, struct thread$ * thrd, unpark_hint hint) with (cltr->ready_queue) {
-                __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
-
-                processor * const proc = kernelTLS().this_processor;
-                const bool external = (!proc) || (cltr != proc->cltr);
-
-                // Figure out the current cpu and make sure it is valid
-                const int cpu = __kernel_getcpu();
-                /* paranoid */ verify(cpu >= 0);
-                /* paranoid */ verify(cpu < cpu_info.hthrd_count);
-                /* paranoid */ verify(cpu * READYQ_SHARD_FACTOR < lanes.count);
-
-                // Figure out where thread was last time and make sure it's
-                /* paranoid */ verify(thrd->preferred >= 0);
-                /* paranoid */ verify(thrd->preferred < cpu_info.hthrd_count);
-                /* paranoid */ verify(thrd->preferred * READYQ_SHARD_FACTOR < lanes.count);
-                const int prf = thrd->preferred * READYQ_SHARD_FACTOR;
-
-                const cpu_map_entry_t & map;
-                choose(hint) {
-                        case UNPARK_LOCAL : &map = &cpu_info.llc_map[cpu];
-                        case UNPARK_REMOTE: &map = &cpu_info.llc_map[prf];
-                }
-                /* paranoid */ verify(map.start * READYQ_SHARD_FACTOR < lanes.count);
-                /* paranoid */ verify(map.self * READYQ_SHARD_FACTOR < lanes.count);
-                /* paranoid */ verifyf((map.start + map.count) * READYQ_SHARD_FACTOR <= lanes.count, "have %zu lanes but map can go up to %u", lanes.count, (map.start + map.count) * READYQ_SHARD_FACTOR);
-
-                const int start = map.self * READYQ_SHARD_FACTOR;
-                unsigned i;
+                                i = __tls_rand() % lanes_count;
+                        } while( !__atomic_try_acquire( &readyQ.data[i].lock ) );
+                }
+        } else {
                 do {
-                        unsigned r;
-                        if(unlikely(external)) { r = __tls_rand(); }
-                        else { r = proc->rdq.its++; }
-                        choose(hint) {
-                                case UNPARK_LOCAL : i = start + (r % READYQ_SHARD_FACTOR);
-                                case UNPARK_REMOTE: i = prf   + (r % READYQ_SHARD_FACTOR);
-                        }
+                        unsigned r = proc->rdq.its++;
+                        i = proc->rdq.id + (r % __shard_factor.readyq);
+                        /* paranoid */ verify( i < lanes_count );
                         // If we can't lock it retry
-                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
-
-                // Actually push it
-                push(lanes.data[i], thrd);
-
-                // Unlock and return
-                __atomic_unlock( &lanes.data[i].lock );
-
-                #if !defined(__CFA_NO_STATISTICS__)
-                        if(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.success, 1, __ATOMIC_RELAXED);
-                        else __tls_stats()->ready.push.local.success++;
-                #endif
-
-                __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);
-
-        }
-
-        // Pop from the ready queue from a given cluster
-        __attribute__((hot)) thread$ * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
-                /* paranoid */ verify( lanes.count > 0 );
-                /* paranoid */ verify( kernelTLS().this_processor );
-
-                processor * const proc = kernelTLS().this_processor;
-                const int cpu = __kernel_getcpu();
-                /* paranoid */ verify(cpu >= 0);
-                /* paranoid */ verify(cpu < cpu_info.hthrd_count);
-                /* paranoid */ verify(cpu * READYQ_SHARD_FACTOR < lanes.count);
-
-                const cpu_map_entry_t & map = cpu_info.llc_map[cpu];
-                /* paranoid */ verify(map.start * READYQ_SHARD_FACTOR < lanes.count);
-                /* paranoid */ verify(map.self * READYQ_SHARD_FACTOR < lanes.count);
-                /* paranoid */ verifyf((map.start + map.count) * READYQ_SHARD_FACTOR <= lanes.count, "have %zu lanes but map can go up to %u", lanes.count, (map.start + map.count) * READYQ_SHARD_FACTOR);
-
-                const int start = map.self * READYQ_SHARD_FACTOR;
-                const unsigned long long ctsc = rdtscl();
-
-                // Did we already have a help target
-                if(proc->rdq.target == MAX) {
-                        unsigned long long max = 0;
-                        for(i; READYQ_SHARD_FACTOR) {
-                                unsigned long long tsc = moving_average(ctsc, ts(lanes.data[start + i]), lanes.tscs[start + i].ma);
-                                if(tsc > max) max = tsc;
-                        }
-                        //  proc->rdq.cutoff = (max + 2 * max) / 2;
-                        /* paranoid */ verify(lanes.count < 65536); // The following code assumes max 65536 cores.
-                        /* paranoid */ verify(map.count < 65536); // The following code assumes max 65536 cores.
-
-                        if(0 == (__tls_rand() % 100)) {
-                                proc->rdq.target = __tls_rand() % lanes.count;
-                        } else {
-                                unsigned cpu_chaos = map.start + (__tls_rand() % map.count);
-                                proc->rdq.target = (cpu_chaos * READYQ_SHARD_FACTOR) + (__tls_rand() % READYQ_SHARD_FACTOR);
-                                /* paranoid */ verify(proc->rdq.target >= (map.start * READYQ_SHARD_FACTOR));
-                                /* paranoid */ verify(proc->rdq.target <  ((map.start + map.count) * READYQ_SHARD_FACTOR));
-                        }
-
-                        /* paranoid */ verify(proc->rdq.target != MAX);
-                }
-                else {
-                        unsigned long long max = 0;
-                        for(i; READYQ_SHARD_FACTOR) {
-                                unsigned long long tsc = moving_average(ctsc, ts(lanes.data[start + i]), lanes.tscs[start + i].ma);
-                                if(tsc > max) max = tsc;
-                        }
-                        const unsigned long long cutoff = (max + 2 * max) / 2;
-                        {
-                                unsigned target = proc->rdq.target;
-                                proc->rdq.target = MAX;
-                                lanes.help[target / READYQ_SHARD_FACTOR].tri++;
-                                if(moving_average(ctsc, lanes.tscs[target].tv, lanes.tscs[target].ma) > cutoff) {
-                                        thread$ * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
-                                        proc->rdq.last = target;
-                                        if(t) return t;
-                                }
-                                proc->rdq.target = MAX;
-                        }
-
-                        unsigned last = proc->rdq.last;
-                        if(last != MAX && moving_average(ctsc, lanes.tscs[last].tv, lanes.tscs[last].ma) > cutoff) {
-                                thread$ * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.help));
-                                if(t) return t;
-                        }
-                        else {
-                                proc->rdq.last = MAX;
-                        }
-                }
-
-                for(READYQ_SHARD_FACTOR) {
-                        unsigned i = start + (proc->rdq.itr++ % READYQ_SHARD_FACTOR);
-                        if(thread$ * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t;
-                }
-
-                // All lanes where empty return 0p
-                return 0p;
-        }
-
-        __attribute__((hot)) struct thread$ * pop_slow(struct cluster * cltr) with (cltr->ready_queue) {
-                processor * const proc = kernelTLS().this_processor;
-                unsigned last = proc->rdq.last;
-                if(last != MAX) {
-                        struct thread$ * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.steal));
-                        if(t) return t;
-                        proc->rdq.last = MAX;
-                }
-
-                unsigned i = __tls_rand() % lanes.count;
-                return try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.steal));
-        }
-        __attribute__((hot)) struct thread$ * pop_search(struct cluster * cltr) {
-                return search(cltr);
-        }
-#endif
-#if defined(USE_RELAXED_FIFO)
-        //-----------------------------------------------------------------------
-        // get index from random number with or without bias towards queues
-        static inline [unsigned, bool] idx_from_r(unsigned r, unsigned preferred) {
-                unsigned i;
-                bool local;
-                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 % READYQ_SHARD_FACTOR);
-                        local = true;
-                }
-                else {
-                        // 1 out of BIAS chances
-                        // Use all queues
-                        i = rhigh;
-                        local = false;
-                }
-                return [i, local];
-        }
-
-        __attribute__((hot)) void push(struct cluster * cltr, struct thread$ * thrd, unpark_hint hint) with (cltr->ready_queue) {
-                __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
-
-                const bool external = (hint != UNPARK_LOCAL) || (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
-                /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
-
-                bool local;
-                int preferred = external ? -1 : kernelTLS().this_processor->rdq.id;
-
-                // Try to pick a lane and lock it
-                unsigned i;
-                do {
-                        // Pick the index of a lane
-                        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(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.attempt, 1, __ATOMIC_RELAXED);
-                                else if(local) __tls_stats()->ready.push.local.attempt++;
-                                else __tls_stats()->ready.push.share.attempt++;
-                        #endif
-
-                        // If we can't lock it retry
-                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
-
-                // Actually push it
-                push(lanes.data[i], thrd);
-
-                // Unlock and return
-                __atomic_unlock( &lanes.data[i].lock );
-
-                // 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(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.success, 1, __ATOMIC_RELAXED);
-                        else if(local) __tls_stats()->ready.push.local.success++;
-                        else __tls_stats()->ready.push.share.success++;
-                #endif
-        }
-
-        // Pop from the ready queue from a given cluster
-        __attribute__((hot)) thread$ * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
-                /* paranoid */ verify( lanes.count > 0 );
-                /* paranoid */ verify( kernelTLS().this_processor );
-                /* paranoid */ verify( kernelTLS().this_processor->rdq.id < lanes.count );
-
-                unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
-                int preferred = kernelTLS().this_processor->rdq.id;
-
-
-                // As long as the list is not empty, try finding a lane that isn't empty and pop from it
-                for(25) {
-                        // Pick two lists at random
-                        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);
-
-                        i %= count;
-                        j %= count;
-
-                        // try popping from the 2 picked lists
-                        struct thread$ * thrd = try_pop(cltr, i, j __STATS(, *(locali || localj ? &__tls_stats()->ready.pop.local : &__tls_stats()->ready.pop.help)));
-                        if(thrd) {
-                                return thrd;
-                        }
-                }
-
-                // All lanes where empty return 0p
-                return 0p;
-        }
-
-        __attribute__((hot)) struct thread$ * pop_slow(struct cluster * cltr) { return pop_fast(cltr); }
-        __attribute__((hot)) struct thread$ * pop_search(struct cluster * cltr) {
-                return search(cltr);
-        }
-#endif
-#if defined(USE_WORK_STEALING)
-        __attribute__((hot)) void push(struct cluster * cltr, struct thread$ * thrd, unpark_hint hint) with (cltr->ready_queue) {
-                __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
-
-                // #define USE_PREFERRED
-                #if !defined(USE_PREFERRED)
-                const bool external = (hint != UNPARK_LOCAL) || (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
-                /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
-                #else
-                        unsigned preferred = thrd->preferred;
-                        const bool external = (hint != UNPARK_LOCAL) || (!kernelTLS().this_processor) || preferred == MAX || thrd->curr_cluster != cltr;
-                        /* paranoid */ verifyf(external || preferred < lanes.count, "Invalid preferred queue %u for %u lanes", preferred, lanes.count );
-
-                        unsigned r = preferred % READYQ_SHARD_FACTOR;
-                        const unsigned start = preferred - r;
-                #endif
-
-                // Try to pick a lane and lock it
-                unsigned i;
-                do {
-                        #if !defined(__CFA_NO_STATISTICS__)
-                                if(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.attempt, 1, __ATOMIC_RELAXED);
-                                else __tls_stats()->ready.push.local.attempt++;
-                        #endif
-
-                        if(unlikely(external)) {
-                                i = __tls_rand() % lanes.count;
-                        }
-                        else {
-                                #if !defined(USE_PREFERRED)
-                                        processor * proc = kernelTLS().this_processor;
-                                        unsigned r = proc->rdq.its++;
-                                        i =  proc->rdq.id + (r % READYQ_SHARD_FACTOR);
-                                #else
-                                        i = start + (r++ % READYQ_SHARD_FACTOR);
-                                #endif
-                        }
-                        // If we can't lock it retry
-                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
-
-                // Actually push it
-                push(lanes.data[i], thrd);
-
-                // Unlock and return
-                __atomic_unlock( &lanes.data[i].lock );
-
-                #if !defined(__CFA_NO_STATISTICS__)
-                        if(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.success, 1, __ATOMIC_RELAXED);
-                        else __tls_stats()->ready.push.local.success++;
-                #endif
-
-                __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);
-        }
-
-        // Pop from the ready queue from a given cluster
-        __attribute__((hot)) thread$ * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
-                /* paranoid */ verify( lanes.count > 0 );
-                /* paranoid */ verify( kernelTLS().this_processor );
-                /* paranoid */ verify( kernelTLS().this_processor->rdq.id < lanes.count );
-
-                processor * proc = kernelTLS().this_processor;
-
-                if(proc->rdq.target == MAX) {
-                        unsigned long long min = ts(lanes.data[proc->rdq.id]);
-                        for(int i = 0; i < READYQ_SHARD_FACTOR; i++) {
-                                unsigned long long tsc = ts(lanes.data[proc->rdq.id + i]);
-                                if(tsc < min) min = tsc;
-                        }
-                        proc->rdq.cutoff = min;
-                        proc->rdq.target = __tls_rand() % lanes.count;
-                }
-                else {
-                        unsigned target = proc->rdq.target;
-                        proc->rdq.target = MAX;
-                        const unsigned long long bias = 0; //2_500_000_000;
-                        const unsigned long long cutoff = proc->rdq.cutoff > bias ? proc->rdq.cutoff - bias : proc->rdq.cutoff;
-                        if(lanes.tscs[target].tv < cutoff && ts(lanes.data[target]) < cutoff) {
+                } while( !__atomic_try_acquire( &readyQ.data[i].lock ) );
+        }
+
+        // Actually push it
+        push(readyQ.data[i], thrd);
+
+        // Unlock and return
+        __atomic_unlock( &readyQ.data[i].lock );
+
+        #if !defined(__CFA_NO_STATISTICS__)
+                if(unlikely(external || remote)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.success, 1, __ATOMIC_RELAXED);
+                else __tls_stats()->ready.push.local.success++;
+        #endif
+}
+
+__attribute__((hot)) struct thread$ * pop_fast(struct cluster * cltr) with (cltr->sched) {
+        const size_t lanes_count = readyQ.count;
+
+        /* paranoid */ verify( __shard_factor.readyq > 0 );
+        /* paranoid */ verify( lanes_count > 0 );
+        /* paranoid */ verify( kernelTLS().this_processor );
+        /* paranoid */ verify( kernelTLS().this_processor->rdq.id < lanes_count );
+
+        processor * const proc = kernelTLS().this_processor;
+        unsigned this = proc->rdq.id;
+        /* paranoid */ verify( this < lanes_count );
+        __cfadbg_print_safe(ready_queue, "Kernel : pop from %u\n", this);
+
+        // Figure out the current cache is
+        const unsigned this_cache = cache_id(cltr, this / __shard_factor.readyq);
+        const unsigned long long ctsc = rdtscl();
+
+        if(proc->rdq.target == MAX) {
+                uint64_t chaos = __tls_rand();
+                unsigned ext = chaos & 0xff;
+                unsigned other  = (chaos >> 8) % (lanes_count);
+
+                if(ext < 3 || __atomic_load_n(&caches[other / __shard_factor.readyq].id, __ATOMIC_RELAXED) == this_cache) {
+                        proc->rdq.target = other;
+                }
+        }
+        else {
+                const unsigned target = proc->rdq.target;
+                __cfadbg_print_safe(ready_queue, "Kernel : %u considering helping %u, tcsc %llu\n", this, target, readyQ.tscs[target].tv);
+                /* paranoid */ verify( readyQ.tscs[target].tv != MAX );
+                if(target < lanes_count) {
+                        const unsigned long long cutoff = calc_cutoff(ctsc, proc, lanes_count, cltr->sched.readyQ.data, cltr->sched.readyQ.tscs, __shard_factor.readyq);
+                        const unsigned long long age = moving_average(ctsc, readyQ.tscs[target].tv, readyQ.tscs[target].ma);
+                        __cfadbg_print_safe(ready_queue, "Kernel : Help attempt on %u from %u, age %'llu vs cutoff %'llu, %s\n", target, this, age, cutoff, age > cutoff ? "yes" : "no");
+                        if(age > cutoff) {
                                 thread$ * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
                                 if(t) return t;
                         }
                 }
-
-                for(READYQ_SHARD_FACTOR) {
-                        unsigned i = proc->rdq.id + (proc->rdq.itr++ % READYQ_SHARD_FACTOR);
-                        if(thread$ * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t;
-                }
-                return 0p;
-        }
-
-        __attribute__((hot)) struct thread$ * pop_slow(struct cluster * cltr) with (cltr->ready_queue) {
-                unsigned i = __tls_rand() % lanes.count;
-                return try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.steal));
-        }
-
-        __attribute__((hot)) struct thread$ * pop_search(struct cluster * cltr) with (cltr->ready_queue) {
-                return search(cltr);
-        }
-#endif
+                proc->rdq.target = MAX;
+        }
+
+        for(__shard_factor.readyq) {
+                unsigned i = this + (proc->rdq.itr++ % __shard_factor.readyq);
+                if(thread$ * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t;
+        }
+
+        // All lanes where empty return 0p
+        return 0p;
+
+}
+__attribute__((hot)) struct thread$ * pop_slow(struct cluster * cltr) {
+        unsigned i = __tls_rand() % (cltr->sched.readyQ.count);
+        return try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.steal));
+}
+__attribute__((hot)) struct thread$ * pop_search(struct cluster * cltr) {
+        return search(cltr);
+}
 
 //=======================================================================
@@ -820 +177 @@
 //-----------------------------------------------------------------------
 // try to pop from a lane given by index w
-static inline struct thread$ * try_pop(struct cluster * cltr, unsigned w __STATS(, __stats_readyQ_pop_t & stats)) with (cltr->ready_queue) {
-        /* paranoid */ verify( w < lanes.count );
+static inline struct thread$ * try_pop(struct cluster * cltr, unsigned w __STATS(, __stats_readyQ_pop_t & stats)) with (cltr->sched) {
+        /* paranoid */ verify( w < readyQ.count );
         __STATS( stats.attempt++; )
 
         // Get relevant elements locally
-        __intrusive_lane_t & lane = lanes.data[w];
+        __intrusive_lane_t & lane = readyQ.data[w];
 
         // If list looks empty retry
@@ -845 +202 @@
         // Actually pop the list
         struct thread$ * thrd;
-        #if defined(USE_AWARE_STEALING) || defined(USE_WORK_STEALING) || defined(USE_CPU_WORK_STEALING)
-                unsigned long long tsc_before = ts(lane);
-        #endif
+        unsigned long long tsc_before = ts(lane);
         unsigned long long tsv;
         [thrd, tsv] = pop(lane);
@@ -861 +216 @@
         __STATS( stats.success++; )
 
-        #if defined(USE_AWARE_STEALING) || defined(USE_WORK_STEALING) || defined(USE_CPU_WORK_STEALING)
-                if (tsv != MAX) {
-                        unsigned long long now = rdtscl();
-                        unsigned long long pma = __atomic_load_n(&lanes.tscs[w].ma, __ATOMIC_RELAXED);
-                        __atomic_store_n(&lanes.tscs[w].tv, tsv, __ATOMIC_RELAXED);
-                        __atomic_store_n(&lanes.tscs[w].ma, moving_average(now, tsc_before, pma), __ATOMIC_RELAXED);
-                }
-        #endif
-
-        #if defined(USE_AWARE_STEALING) || defined(USE_CPU_WORK_STEALING)
-                thrd->preferred = w / READYQ_SHARD_FACTOR;
-        #else
-                thrd->preferred = w;
-        #endif
+        if (tsv != MAX) {
+                unsigned long long now = rdtscl();
+                unsigned long long pma = __atomic_load_n(&readyQ.tscs[w].ma, __ATOMIC_RELAXED);
+                __atomic_store_n(&readyQ.tscs[w].tv, tsv, __ATOMIC_RELAXED);
+                __atomic_store_n(&readyQ.tscs[w].ma, moving_average(now, tsc_before, pma), __ATOMIC_RELAXED);
+        }
+
+        thrd->preferred = w / __shard_factor.readyq;
 
         // return the popped thread
@@ -883 +232 @@
 // try to pop from any lanes making sure you don't miss any threads push
 // before the start of the function
-static inline struct thread$ * search(struct cluster * cltr) with (cltr->ready_queue) {
-        /* paranoid */ verify( lanes.count > 0 );
-        unsigned count = __atomic_load_n( &lanes.count, __ATOMIC_RELAXED );
+static inline struct thread$ * search(struct cluster * cltr) {
+        const size_t lanes_count = cltr->sched.readyQ.count;
+        /* paranoid */ verify( lanes_count > 0 );
+        unsigned count = __atomic_load_n( &lanes_count, __ATOMIC_RELAXED );
         unsigned offset = __tls_rand();
         for(i; count) {
@@ -902 +252 @@
 // get preferred ready for new thread
 unsigned ready_queue_new_preferred() {
-        unsigned pref = 0;
+        unsigned pref = MAX;
         if(struct thread$ * thrd = publicTLS_get( this_thread )) {
                 pref = thrd->preferred;
         }
-        else {
-                #if defined(USE_CPU_WORK_STEALING)
-                        pref = __kernel_getcpu();
-                #endif
-        }
-
-        #if defined(USE_CPU_WORK_STEALING)
-                /* paranoid */ verify(pref >= 0);
-                /* paranoid */ verify(pref < cpu_info.hthrd_count);
-        #endif
 
         return pref;
@@ -921 +261 @@
 
 //-----------------------------------------------------------------------
-// Check that all the intrusive queues in the data structure are still consistent
-static void check( __ready_queue_t & q ) with (q) {
-        #if defined(__CFA_WITH_VERIFY__)
-                {
-                        for( idx ; lanes.count ) {
-                                __intrusive_lane_t & sl = lanes.data[idx];
-                                assert(!lanes.data[idx].lock);
-
-                                        if(is_empty(sl)) {
-                                                assert( sl.anchor.next == 0p );
-                                                assert( sl.anchor.ts   == -1llu );
-                                                assert( mock_head(sl)  == sl.prev );
-                                        } else {
-                                                assert( sl.anchor.next != 0p );
-                                                assert( sl.anchor.ts   != -1llu );
-                                                assert( mock_head(sl)  != sl.prev );
-                                        }
-                        }
-                }
-        #endif
-}
-
-//-----------------------------------------------------------------------
 // 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 __STATS(, __stats_readyQ_pop_t & stats)) with (cltr->ready_queue) {
+static inline struct thread$ * try_pop(struct cluster * cltr, unsigned i, unsigned j __STATS(, __stats_readyQ_pop_t & stats)) with (cltr->sched) {
         // 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;
+        if( __builtin_expect(!is_empty(readyQ.data[j]), true) ) {
+                w = (ts(readyQ.data[i]) < ts(readyQ.data[j])) ? i : j;
         }
 
         return try_pop(cltr, w __STATS(, stats));
 }
-
-// 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(is_empty(ll)) {
-                                verify(ll.anchor.next == 0p);
-                                ll.prev = mock_head(ll);
-                        }
-}
-
-static void assign_list(unsigned & value, dlist(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->rdq.id = value;
-                it->rdq.target = MAX;
-                value += READYQ_SHARD_FACTOR;
-                it = &(*it)`next;
-        }
-}
-
-static void reassign_cltr_id(struct cluster * cltr) {
-        unsigned preferred = 0;
-        assign_list(preferred, cltr->procs.actives, cltr->procs.total - cltr->procs.idle);
-        assign_list(preferred, cltr->procs.idles  , cltr->procs.idle );
-}
-
-static void fix_times( struct cluster * cltr ) with( cltr->ready_queue ) {
-        #if defined(USE_AWARE_STEALING) || defined(USE_WORK_STEALING)
-                lanes.tscs = alloc(lanes.count, lanes.tscs`realloc);
-                for(i; lanes.count) {
-                        lanes.tscs[i].tv = rdtscl();
-                        lanes.tscs[i].ma = 0;
-                }
-        #endif
-}
-
-#if defined(USE_CPU_WORK_STEALING)
-        // ready_queue size is fixed in this case
-        void ready_queue_grow(struct cluster * cltr) {}
-        void ready_queue_shrink(struct cluster * cltr) {}
-#else
-        // 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 ) {
-                        // Find new count
-                        // Make sure we always have atleast 1 list
-                        if(target >= 2) {
-                                ncount = target * READYQ_SHARD_FACTOR;
-                        } else {
-                                ncount = SEQUENTIAL_SHARD;
-                        }
-
-                        // 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;
-
-                        lanes.caches = alloc( target, lanes.caches`realloc );
-                }
-
-                fix_times(cltr);
-
-                reassign_cltr_id(cltr);
-
-                // 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 ) {
-                        // Remember old count
-                        size_t ocount = lanes.count;
-
-                        // Find new count
-                        // Make sure we always have atleast 1 list
-                        lanes.count = target >= 2 ? target * READYQ_SHARD_FACTOR: SEQUENTIAL_SHARD;
-                        /* paranoid */ verify( ocount >= lanes.count );
-                        /* paranoid */ verify( lanes.count == target * READYQ_SHARD_FACTOR || 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;
-                                        unsigned long long _;
-                                        [thrd, _] = pop(lanes.data[idx]);
-
-                                        push(cltr, thrd, true);
-
-                                        // 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]);
-                        }
-
-                        lanes.caches = alloc( target, lanes.caches`realloc );
-                }
-
-                fix_times(cltr);
-
-
-                reassign_cltr_id(cltr);
-
-                // 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() );
-        }
-#endif
-
-#if !defined(__CFA_NO_STATISTICS__)
-        unsigned cnt(const __ready_queue_t & this, unsigned idx) {
-                /* paranoid */ verify(this.lanes.count > idx);
-                return this.lanes.data[idx].cnt;
-        }
-#endif
-
-
-#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
-        // No definition needed
-#elif defined(CFA_HAVE_LINUX_RSEQ_H)
-
-        #if defined( __x86_64 ) || defined( __i386 )
-                #define RSEQ_SIG        0x53053053
-        #elif defined( __ARM_ARCH )
-                #ifdef __ARMEB__
-                #define RSEQ_SIG    0xf3def5e7      /* udf    #24035    ; 0x5de3 (ARMv6+) */
-                #else
-                #define RSEQ_SIG    0xe7f5def3      /* udf    #24035    ; 0x5de3 */
-                #endif
-        #endif
-
-        extern void __disable_interrupts_hard();
-        extern void __enable_interrupts_hard();
-
-        static void __kernel_raw_rseq_register  (void) {
-                /* paranoid */ verify( __cfaabi_rseq.cpu_id == RSEQ_CPU_ID_UNINITIALIZED );
-
-                // int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), 0, (sigset_t *)0p, _NSIG / 8);
-                int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), 0, RSEQ_SIG);
-                if(ret != 0) {
-                        int e = errno;
-                        switch(e) {
-                        case EINVAL: abort("KERNEL ERROR: rseq register invalid argument");
-                        case ENOSYS: abort("KERNEL ERROR: rseq register no supported");
-                        case EFAULT: abort("KERNEL ERROR: rseq register with invalid argument");
-                        case EBUSY : abort("KERNEL ERROR: rseq register already registered");
-                        case EPERM : abort("KERNEL ERROR: rseq register sig  argument  on unregistration does not match the signature received on registration");
-                        default: abort("KERNEL ERROR: rseq register unexpected return %d", e);
-                        }
-                }
-        }
-
-        static void __kernel_raw_rseq_unregister(void) {
-                /* paranoid */ verify( __cfaabi_rseq.cpu_id >= 0 );
-
-                // int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), RSEQ_FLAG_UNREGISTER, (sigset_t *)0p, _NSIG / 8);
-                int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), RSEQ_FLAG_UNREGISTER, RSEQ_SIG);
-                if(ret != 0) {
-                        int e = errno;
-                        switch(e) {
-                        case EINVAL: abort("KERNEL ERROR: rseq unregister invalid argument");
-                        case ENOSYS: abort("KERNEL ERROR: rseq unregister no supported");
-                        case EFAULT: abort("KERNEL ERROR: rseq unregister with invalid argument");
-                        case EBUSY : abort("KERNEL ERROR: rseq unregister already registered");
-                        case EPERM : abort("KERNEL ERROR: rseq unregister sig  argument  on unregistration does not match the signature received on registration");
-                        default: abort("KERNEL ERROR: rseq unregisteunexpected return %d", e);
-                        }
-                }
-        }
-#else
-        // No definition needed
-#endif

libcfa/src/concurrency/ready_subqueue.hfa

@@ -25 +25 @@
         );
         return rhead;
-}
-
-// Ctor
-void ?{}( __intrusive_lane_t & this ) {
-        this.lock = false;
-        this.prev = mock_head(this);
-        this.anchor.next = 0p;
-        this.anchor.ts   = -1llu;
-        #if !defined(__CFA_NO_STATISTICS__)
-                this.cnt  = 0;
-        #endif
-
-        // We add a boat-load of assertions here because the anchor code is very fragile
-        /* paranoid */ _Static_assert( offsetof( thread$, link ) == offsetof(__intrusive_lane_t, anchor) );
-        /* paranoid */ verify( offsetof( thread$, link ) == offsetof(__intrusive_lane_t, anchor) );
-        /* paranoid */ verify( ((uintptr_t)( mock_head(this) ) + offsetof( thread$, link )) == (uintptr_t)(&this.anchor) );
-        /* paranoid */ verify( &mock_head(this)->link.next == &this.anchor.next );
-        /* paranoid */ verify( &mock_head(this)->link.ts   == &this.anchor.ts   );
-        /* paranoid */ verify( mock_head(this)->link.next == 0p );
-        /* paranoid */ verify( mock_head(this)->link.ts   == -1llu  );
-        /* paranoid */ verify( mock_head(this) == this.prev );
-        /* 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( this.anchor.next == 0p );
-        /* paranoid */ verify( this.anchor.ts   == -1llu );
-        /* paranoid */ verify( mock_head(this)  == this.prev );
 }
 

libcfa/src/concurrency/thread.cfa

@@ -19 +19 @@
 #include "thread.hfa"
 
-#include "kernel_private.hfa"
+#include "kernel/private.hfa"
 #include "exception.hfa"
 

libcfa/src/containers/string.cfa

@@ -92 +92 @@
 }
 
-string ?=?(string & this, string other) {
+string & ?=?(string & this, string & other) { //// <---- straw man change
     (*this.inner) = (*other.inner);
     return this;
@@ -235 +235 @@
 int find(const string &s, const char* search, size_t searchsize) {
     return find( *s.inner, search, searchsize);
+}
+
+int findFrom(const string &s, size_t fromPos, char search) {
+    return findFrom( *s.inner, fromPos, search );
+}
+
+int findFrom(const string &s, size_t fromPos, const string &search) {
+    return findFrom( *s.inner, fromPos, *search.inner );
+}
+
+int findFrom(const string &s, size_t fromPos, const char* search) {
+    return findFrom( *s.inner, fromPos, search );
+}
+
+int findFrom(const string &s, size_t fromPos, const char* search, size_t searchsize) {
+    return findFrom( *s.inner, fromPos, search, searchsize );
 }
 

libcfa/src/containers/string.hfa

@@ -41 +41 @@
 void ?=?(string &s, const string &other);
 void ?=?(string &s, char other);
-string ?=?(string &s, string other);  // string tolerates memcpys; still saw calls to autogen 
-
+string & ?=?(string &s, string &other);  // surprising ret seems to help avoid calls to autogen
+//string ?=?( string &, string ) = void;
 void ^?{}(string &s);
 
@@ -93 +93 @@
 int find(const string &s, const char* search, size_t searchsize);
 
+int findFrom(const string &s, size_t fromPos, char search);
+int findFrom(const string &s, size_t fromPos, const string &search);
+int findFrom(const string &s, size_t fromPos, const char* search);
+int findFrom(const string &s, size_t fromPos, const char* search, size_t searchsize);
+
 bool includes(const string &s, const string &search);
 bool includes(const string &s, const char* search);

libcfa/src/containers/string_res.cfa

@@ -15 +15 @@
 
 #include "string_res.hfa"
-#include <stdlib.hfa>  // e.g. malloc
-#include <string.h>    // e.g. strlen
+#include "string_sharectx.hfa"
+#include "stdlib.hfa"
+
+// Workaround for observed performance penalty from calling CFA's alloc.
+// Workaround is:  EndVbyte = TEMP_ALLOC(char, CurrSize)
+// Should be:      EndVbyte = alloc(CurrSize)
+#define TEMP_ALLOC(T, n) (( T* ) malloc( n * sizeof( T ) ))
+
+#include <assert.h>
 
 //######################### VbyteHeap "header" #########################
-
-
-
-
-
-
-
-
-// DON'T COMMIT:
-// #define VbyteDebug
-
-
-
-
 
 #ifdef VbyteDebug
@@ -54 +47 @@
 
     
-static inline void compaction( VbyteHeap & );                           // compaction of the byte area
-static inline void garbage( VbyteHeap & );                              // garbage collect the byte area
-static inline void extend( VbyteHeap &, int );                  // extend the size of the byte area
-static inline void reduce( VbyteHeap &, int );                  // reduce the size of the byte area
-
-static inline void ?{}( VbyteHeap &, int = 1000 );
-static inline void ^?{}( VbyteHeap & );
-static inline void ByteCopy( VbyteHeap &, char *, int, int, char *, int, int ); // copy a block of bytes from one location in the heap to another
-static inline int ByteCmp( VbyteHeap &, char *, int, int, char *, int, int );   // compare 2 blocks of bytes
-static inline char *VbyteAlloc( VbyteHeap &, int );                     // allocate a block bytes in the heap
-
-
-static inline void AddThisAfter( HandleNode &, HandleNode & );
-static inline void DeleteNode( HandleNode & );
-static inline void MoveThisAfter( HandleNode &, const HandleNode & );           // move current handle after parameter handle
+static void compaction( VbyteHeap & );                          // compaction of the byte area
+static void garbage( VbyteHeap &, int );                                // garbage collect the byte area
+static void extend( VbyteHeap &, int );                 // extend the size of the byte area
+static void reduce( VbyteHeap &, int );                 // reduce the size of the byte area
+
+static void ?{}( VbyteHeap &, size_t = 1000 );
+static void ^?{}( VbyteHeap & );
+
+static int ByteCmp( char *, int, int, char *, int, int );       // compare 2 blocks of bytes
+static char *VbyteAlloc( VbyteHeap &, int );                    // allocate a block bytes in the heap
+static char *VbyteTryAdjustLast( VbyteHeap &, int );
+
+static void AddThisAfter( HandleNode &, HandleNode & );
+static void DeleteNode( HandleNode & );
+static void MoveThisAfter( HandleNode &, const HandleNode & );          // move current handle after parameter handle
 
 
 // Allocate the storage for the variable sized area and intialize the heap variables.
 
-static inline void ?{}( VbyteHeap & this, int Size ) with(this) {
+static void ?{}( VbyteHeap & this, size_t Size ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:VbyteHeap::VbyteHeap, this:" | &this | " Size:" | Size;
@@ -79 +72 @@
     NoOfCompactions = NoOfExtensions = NoOfReductions = 0;
     InitSize = CurrSize = Size;
-    StartVbyte = EndVbyte = alloc(CurrSize);
+    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
     ExtVbyte = (void *)( StartVbyte + CurrSize );
     Header.flink = Header.blink = &Header;
+    Header.ulink = & this;
 #ifdef VbyteDebug
     HeaderPtr = &Header;
@@ -91 +85 @@
 // Release the dynamically allocated storage for the byte area.
 
-static inline void ^?{}( VbyteHeap & this ) with(this) {
+static void ^?{}( VbyteHeap & this ) with(this) {
     free( StartVbyte );
 } // ~VbyteHeap
@@ -102 +96 @@
 // creator.
 
-void ?{}( HandleNode & this ) with(this) {
+static void ?{}( HandleNode & this ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:HandleNode::HandleNode, this:" | &this;
@@ -117 +111 @@
 // collection.
 
-void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) {
+static void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:HandleNode::HandleNode, this:" | &this;
@@ -123 +117 @@
     s = 0;
     lnth = 0;
+    ulink = &vh;
     AddThisAfter( this, *vh.Header.blink );
 #ifdef VbyteDebug
@@ -133 +128 @@
 // is the responsibility of the creator to destroy it.
 
-void ^?{}( HandleNode & this ) with(this) {
+static void ^?{}( HandleNode & this ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:HandleNode::~HandleNode, this:" | & this;
@@ -149 +144 @@
 } // ~HandleNode
 
+
+//######################### String Sharing Context #########################
+
+static string_sharectx * ambient_string_sharectx;               // fickle top of stack
+static string_sharectx default_string_sharectx = {NEW_SHARING}; // stable bottom of stack
+
+void ?{}( string_sharectx & this, StringSharectx_Mode mode ) with( this ) {
+    (older){ ambient_string_sharectx };
+    if ( mode == NEW_SHARING ) {
+        (activeHeap){ new( (size_t) 1000 ) };
+    } else {
+        verify( mode == NO_SHARING );
+        (activeHeap){ 0p };
+    }
+    ambient_string_sharectx = & this;
+}
+
+void ^?{}( string_sharectx & this ) with( this ) {
+    if ( activeHeap ) delete( activeHeap );
+
+    // unlink this from older-list starting from ambient_string_sharectx
+    // usually, this==ambient_string_sharectx and the loop runs zero times
+    string_sharectx *& c = ambient_string_sharectx;
+    while ( c != &this ) &c = &c->older;              // find this
+    c = this.older;                                   // unlink
+}
+
 //######################### String Resource #########################
 
 
-VbyteHeap HeapArea;
-
-VbyteHeap * DEBUG_string_heap = & HeapArea;
+VbyteHeap * DEBUG_string_heap() {
+    assert( ambient_string_sharectx->activeHeap && "No sharing context is active" );
+    return ambient_string_sharectx->activeHeap;
+}
 
 size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ) {
@@ -160 +183 @@
 }
 
+size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ) {
+    return heap->CurrSize;
+}
+
 const char * DEBUG_string_heap_start( VbyteHeap * heap ) {
     return heap->StartVbyte;
 }
-
 
 // Returns the size of the string in bytes
@@ -187 +213 @@
     // Store auto-newline state so it can be restored
     bool anl = getANL$(out);
-    nlOff(out);
-    for (size_t i = 0; i < s.Handle.lnth; i++) {
-        // Need to re-apply on the last output operator, for whole-statement version
-        if (anl && i == s.Handle.lnth-1) nlOn(out);
-        out | s[i];
-    }
-    return out;
+    if( s.Handle.lnth == 0 ) {
+        sout | "";
+    } else {
+        nlOff(out);
+        for (size_t i = 0; i < s.Handle.lnth; i++) {
+            // Need to re-apply on the last output operator, for whole-statement version
+            if (anl && i == s.Handle.lnth-1) nlOn(out);
+            out | s[i];
+        }
+    }
 }
 
 // Empty constructor
 void ?{}(string_res &s) with(s) {
-    (Handle){ HeapArea };
+    if( ambient_string_sharectx->activeHeap ) {
+        (Handle){ * ambient_string_sharectx->activeHeap };
+        (shareEditSet_owns_ulink){ false };
+        verify( Handle.s == 0p && Handle.lnth == 0 );
+    } else {
+        (Handle){ * new( (size_t) 10 ) };  // TODO: can I lazily avoid allocating for empty string
+        (shareEditSet_owns_ulink){ true };
+        Handle.s = Handle.ulink->StartVbyte;
+        verify( Handle.lnth == 0 );
+    }
     s.shareEditSet_prev = &s;
     s.shareEditSet_next = &s;
 }
 
+static void eagerCopyCtorHelper(string_res &s, const char* rhs, size_t rhslnth) with(s) {
+    if( ambient_string_sharectx->activeHeap ) {
+        (Handle){ * ambient_string_sharectx->activeHeap };
+        (shareEditSet_owns_ulink){ false };
+    } else {
+        (Handle){ * new( rhslnth ) };
+        (shareEditSet_owns_ulink){ true };
+    }
+    Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
+    Handle.lnth = rhslnth;
+    memmove( Handle.s, rhs, rhslnth );
+    s.shareEditSet_prev = &s;
+    s.shareEditSet_next = &s;
+}
+
 // Constructor from a raw buffer and size
 void ?{}(string_res &s, const char* rhs, size_t rhslnth) with(s) {
-    (Handle){ HeapArea };
-    Handle.s = VbyteAlloc(HeapArea, rhslnth);
+    eagerCopyCtorHelper(s, rhs, rhslnth);
+}
+
+// private ctor (not in header): use specified heap (ignore ambient) and copy chars in
+void ?{}( string_res &s, VbyteHeap & heap, const char* rhs, size_t rhslnth ) with(s) {
+    (Handle){ heap };
+    Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
     Handle.lnth = rhslnth;
-    for ( int i = 0; i < rhslnth; i += 1 ) {            // copy characters
-        Handle.s[i] = rhs[i];
-    } // for
+    (s.shareEditSet_owns_ulink){ false };
+    memmove( Handle.s, rhs, rhslnth );
     s.shareEditSet_prev = &s;
     s.shareEditSet_next = &s;
 }
 
-// String literal constructor
-void ?{}(string_res &s, const char* rhs) {
-    (s){ rhs, strlen(rhs) };
-}
-
 // General copy constructor
 void ?{}(string_res &s, const string_res & s2, StrResInitMode mode, size_t start, size_t end ) {
 
-    (s.Handle){ HeapArea };
-    s.Handle.s = s2.Handle.s + start;
-    s.Handle.lnth = end - start;
-    MoveThisAfter(s.Handle, s2.Handle );                        // insert this handle after rhs handle
-    // ^ bug?  skip others at early point in string
-    
-    if (mode == COPY_VALUE) {
-        // make s alone in its shareEditSet
-        s.shareEditSet_prev = &s;
-        s.shareEditSet_next = &s;
+    verify( start <= end && end <= s2.Handle.lnth );
+
+    if (s2.Handle.ulink != ambient_string_sharectx->activeHeap && mode == COPY_VALUE) {
+        // crossing heaps (including private): copy eagerly
+        eagerCopyCtorHelper(s, s2.Handle.s + start, end - start);
+        verify(s.shareEditSet_prev == &s);
+        verify(s.shareEditSet_next == &s);
     } else {
-        assert( mode == SHARE_EDITS );
-
-        // s2 is logically const but not implementation const
-        string_res & s2mod = (string_res &) s2;
-
-        // insert s after s2 on shareEditSet
-        s.shareEditSet_next = s2mod.shareEditSet_next;
-        s.shareEditSet_prev = &s2mod;
-        s.shareEditSet_next->shareEditSet_prev = &s;
-        s.shareEditSet_prev->shareEditSet_next = &s;
-    }
-}
-
-void assign(string_res &this, const char* buffer, size_t bsize) {
-
-    // traverse the incumbent share-edit set (SES) to recover the range of a base string to which `this` belongs
-    string_res * shareEditSetStartPeer = & this;
-    string_res * shareEditSetEndPeer = & this;
-    for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) {
-        if ( editPeer->Handle.s < shareEditSetStartPeer->Handle.s ) {
-            shareEditSetStartPeer = editPeer;
+        (s.Handle){};
+        s.Handle.s = s2.Handle.s + start;
+        s.Handle.lnth = end - start;
+        s.Handle.ulink = s2.Handle.ulink;
+
+        AddThisAfter(s.Handle, s2.Handle );                     // insert this handle after rhs handle
+        // ^ bug?  skip others at early point in string
+
+        if (mode == COPY_VALUE) {
+            verify(s2.Handle.ulink == ambient_string_sharectx->activeHeap);
+            // requested logical copy in same heap: defer copy until write
+
+            (s.shareEditSet_owns_ulink){ false };
+
+            // make s alone in its shareEditSet
+            s.shareEditSet_prev = &s;
+            s.shareEditSet_next = &s;
+        } else {
+            verify( mode == SHARE_EDITS );
+            // sharing edits with source forces same heap as source (ignore context)
+
+            (s.shareEditSet_owns_ulink){ s2.shareEditSet_owns_ulink };
+
+            // s2 is logically const but not implementation const
+            string_res & s2mod = (string_res &) s2;
+
+            // insert s after s2 on shareEditSet
+            s.shareEditSet_next = s2mod.shareEditSet_next;
+            s.shareEditSet_prev = &s2mod;
+            s.shareEditSet_next->shareEditSet_prev = &s;
+            s.shareEditSet_prev->shareEditSet_next = &s;
         }
-        if ( shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) {
-            shareEditSetEndPeer = editPeer;
-        }
-    }
-
-    // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer
-    // `this` occurs in the middle of it, to be replaced
-    // build up the new text in `pasting`
-
-    string_res pasting = {
-        shareEditSetStartPeer->Handle.s,                   // start of SES
-        this.Handle.s - shareEditSetStartPeer->Handle.s }; // length of SES, before this
-    append( pasting,
-        buffer,                                            // start of replacement for this
-        bsize );                                           // length of replacement for this
-    append( pasting,
-        this.Handle.s + this.Handle.lnth,                  // start of SES after this
-        shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth -
-        (this.Handle.s + this.Handle.lnth) );              // length of SES, after this
-
-    // The above string building can trigger compaction.
-    // The reference points (that are arguments of the string building) may move during that building.
-    // From this point on, they are stable.
-    // So now, capture their values for use in the overlap cases, below.
-    // Do not factor these definitions with the arguments used above.
+    }
+}
+
+static void assignEditSet(string_res & this, string_res * shareEditSetStartPeer, string_res * shareEditSetEndPeer,
+    char * resultSesStart,
+    size_t resultSesLnth,
+    HandleNode * resultPadPosition, size_t bsize ) {
 
     char * beforeBegin = shareEditSetStartPeer->Handle.s;
@@ -290 +331 @@
     size_t oldLnth = this.Handle.lnth;
 
-    this.Handle.s = pasting.Handle.s + beforeLen;
+    this.Handle.s = resultSesStart + beforeLen;
     this.Handle.lnth = bsize;
-    MoveThisAfter( this.Handle, pasting.Handle );
+    if (resultPadPosition)
+        MoveThisAfter( this.Handle, *resultPadPosition );
 
     // adjust all substring string and handle locations, and check if any substring strings are outside the new base string
-    char *limit = pasting.Handle.s + pasting.Handle.lnth;
+    char *limit = resultSesStart + resultSesLnth;
     for (string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next) {
-        assert (p->Handle.s >= beforeBegin);
+        verify (p->Handle.s >= beforeBegin);
         if ( p->Handle.s >= afterBegin ) {
-            assert ( p->Handle.s <= afterBegin + afterLen );
-            assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
+            verify ( p->Handle.s <= afterBegin + afterLen );
+            verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
             // p starts after the edit
             // take start and end as end-anchored
@@ -318 +360 @@
             } else {
                 // p ends after the edit
-                assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
+                verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
                 // take end as end-anchored
                 // stretch-shrink p according to the edit
@@ -326 +368 @@
             // take start as start-anchored
             size_t startOffsetFromStart = p->Handle.s - beforeBegin;
-            p->Handle.s = pasting.Handle.s + startOffsetFromStart;
+            p->Handle.s = resultSesStart + startOffsetFromStart;
         } else {
-            assert ( p->Handle.s < afterBegin );
+            verify ( p->Handle.s < afterBegin );
             // p starts during the edit
-            assert( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
+            verify( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
             if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
                 // p ends during the edit; p does not include the last character replaced
@@ -344 +386 @@
             }
         }
-        MoveThisAfter( p->Handle, pasting.Handle );     // move substring handle to maintain sorted order by string position
-    }
-}
-
-void ?=?(string_res &s, const char* other) {
-    assign(s, other, strlen(other));
-}
-
-void ?=?(string_res &s, char other) {
-    assign(s, &other, 1);
+        if (resultPadPosition)
+            MoveThisAfter( p->Handle, *resultPadPosition );     // move substring handle to maintain sorted order by string position
+    }
+}
+
+static string_res & assign_(string_res &this, const char* buffer, size_t bsize, const string_res & valSrc) {
+
+    // traverse the incumbent share-edit set (SES) to recover the range of a base string to which `this` belongs
+    string_res * shareEditSetStartPeer = & this;
+    string_res * shareEditSetEndPeer = & this;
+    for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) {
+        if ( editPeer->Handle.s < shareEditSetStartPeer->Handle.s ) {
+            shareEditSetStartPeer = editPeer;
+        }
+        if ( shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) {
+            shareEditSetEndPeer = editPeer;
+        }
+    }
+
+    verify( shareEditSetEndPeer->Handle.s >= shareEditSetStartPeer->Handle.s );
+    size_t origEditSetLength = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - shareEditSetStartPeer->Handle.s;
+    verify( origEditSetLength >= this.Handle.lnth );
+
+    if ( this.shareEditSet_owns_ulink ) {                 // assigning to private context
+        // ok to overwrite old value within LHS
+        char * prefixStartOrig = shareEditSetStartPeer->Handle.s;
+        int prefixLen = this.Handle.s - prefixStartOrig;
+        char * suffixStartOrig = this.Handle.s + this.Handle.lnth;
+        int suffixLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - suffixStartOrig;
+
+        int delta = bsize - this.Handle.lnth;
+        if ( char * oldBytes = VbyteTryAdjustLast( *this.Handle.ulink, delta ) ) {
+            // growing: copy from old to new
+            char * dest = VbyteAlloc( *this.Handle.ulink, origEditSetLength + delta );
+            char *destCursor = dest;  memcpy(destCursor, prefixStartOrig, prefixLen);
+            destCursor += prefixLen;  memcpy(destCursor, buffer         , bsize    );
+            destCursor += bsize;      memcpy(destCursor, suffixStartOrig, suffixLen);
+            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+                dest,
+                origEditSetLength + delta,
+                0p, bsize);
+            free( oldBytes );
+        } else {
+            // room is already allocated in-place: bubble suffix and overwite middle
+            memmove( suffixStartOrig + delta, suffixStartOrig, suffixLen );
+            memcpy( this.Handle.s, buffer, bsize );
+
+            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+                shareEditSetStartPeer->Handle.s,
+                origEditSetLength + delta,
+                0p, bsize);
+        }
+
+    } else if (                                           // assigning to shared context
+        this.Handle.lnth == origEditSetLength &&          // overwriting entire run of SES
+        & valSrc &&                                       // sourcing from a managed string
+        valSrc.Handle.ulink == this.Handle.ulink  ) {     // sourcing from same heap
+
+        // SES's result will only use characters from the source string => reuse source
+        assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+            valSrc.Handle.s,
+            valSrc.Handle.lnth,
+            &((string_res&)valSrc).Handle, bsize);
+        
+    } else {
+        // overwriting a proper substring of some string: mash characters from old and new together (copy on write)
+        // OR we are importing characters: need to copy eagerly (can't refer to source)
+
+        // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer
+        // `this` occurs in the middle of it, to be replaced
+        // build up the new text in `pasting`
+
+        string_res pasting = {
+            * this.Handle.ulink,                               // maintain same heap, regardless of context
+            shareEditSetStartPeer->Handle.s,                   // start of SES
+            this.Handle.s - shareEditSetStartPeer->Handle.s }; // length of SES, before this
+        append( pasting,
+            buffer,                                            // start of replacement for this
+            bsize );                                           // length of replacement for this
+        append( pasting,
+            this.Handle.s + this.Handle.lnth,                  // start of SES after this
+            shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth -
+            (this.Handle.s + this.Handle.lnth) );              // length of SES, after this
+
+        // The above string building can trigger compaction.
+        // The reference points (that are arguments of the string building) may move during that building.
+        // From this point on, they are stable.
+
+        assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+            pasting.Handle.s,
+            pasting.Handle.lnth,
+            &pasting.Handle, bsize);
+    }
+
+    return this;
+}
+
+string_res & assign(string_res &this, const char* buffer, size_t bsize) {
+    return assign_(this, buffer, bsize, *0p);
+}
+
+string_res & ?=?(string_res &s, char other) {
+    return assign(s, &other, 1);
 }
 
 // Copy assignment operator
-void ?=?(string_res & this, const string_res & rhs) with( this ) {
-    assign(this, rhs.Handle.s, rhs.Handle.lnth);
-}
-
-void ?=?(string_res & this, string_res & rhs) with( this ) {
+string_res & ?=?(string_res & this, const string_res & rhs) with( this ) {
+    return assign_(this, rhs.Handle.s, rhs.Handle.lnth, rhs);
+}
+
+string_res & ?=?(string_res & this, string_res & rhs) with( this ) {
     const string_res & rhs2 = rhs;
-    this = rhs2;
+    return this = rhs2;
 }
 
@@ -374 +509 @@
     s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next;
     s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev;
-    s.shareEditSet_next = &s;
-    s.shareEditSet_prev = &s;
+    // s.shareEditSet_next = &s;
+    // s.shareEditSet_prev = &s;
+
+    if (shareEditSet_owns_ulink && s.shareEditSet_next == &s) { // last one out
+        delete( s.Handle.ulink );
+    }
 }
 
@@ -387 +526 @@
 }
 
+void assignAt(const string_res &s, size_t index, char val) {
+    string_res editZone = { s, SHARE_EDITS, index, index+1 };
+    assign(editZone, &val, 1);
+}
+
 
 ///////////////////////////////////////////////////////////////////
@@ -392 +536 @@
 
 void append(string_res &str1, const char * buffer, size_t bsize) {
-    size_t clnth = size(str1) + bsize;
-    if ( str1.Handle.s + size(str1) == buffer ) { // already juxtapose ?
+    size_t clnth = str1.Handle.lnth + bsize;
+    if ( str1.Handle.s + str1.Handle.lnth == buffer ) { // already juxtapose ?
         // no-op
     } else {                                            // must copy some text
-        if ( str1.Handle.s + size(str1) == VbyteAlloc(HeapArea, 0) ) { // str1 at end of string area ?
-            VbyteAlloc(HeapArea, bsize); // create room for 2nd part at the end of string area
+        if ( str1.Handle.s + str1.Handle.lnth == VbyteAlloc(*str1.Handle.ulink, 0) ) { // str1 at end of string area ?
+            VbyteAlloc( *str1.Handle.ulink, bsize ); // create room for 2nd part at the end of string area
         } else {                                        // copy the two parts
-            char * str1oldBuf = str1.Handle.s;
-            str1.Handle.s = VbyteAlloc( HeapArea, clnth );
-            ByteCopy( HeapArea, str1.Handle.s, 0, str1.Handle.lnth, str1oldBuf, 0, str1.Handle.lnth);
+            char * str1newBuf = VbyteAlloc( *str1.Handle.ulink, clnth );
+            char * str1oldBuf = str1.Handle.s;  // must read after VbyteAlloc call in case it gs's
+            str1.Handle.s = str1newBuf;
+            memcpy( str1.Handle.s, str1oldBuf,  str1.Handle.lnth );
         } // if
-        ByteCopy( HeapArea, str1.Handle.s, str1.Handle.lnth, bsize, (char*)buffer, 0, (int)bsize);
-        //       VbyteHeap & this, char *Dst, int DstStart, int DstLnth, char *Src, int SrcStart, int SrcLnth 
+        memcpy( str1.Handle.s + str1.Handle.lnth, buffer, bsize );
     } // if
     str1.Handle.lnth = clnth;
@@ -417 +561 @@
 }
 
-void ?+=?(string_res &s, const char* other) {
-    append( s, other, strlen(other) );
-}
 
 
@@ -429 +570 @@
 
 bool ?==?(const string_res &s1, const string_res &s2) {
-    return ByteCmp( HeapArea, s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
+    return ByteCmp( s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
 }
 
@@ -455 +596 @@
 
 int find(const string_res &s, char search) {
-    for (i; size(s)) {
-        if (s[i] == search) return i;
-    }
-    return size(s);
-}
+    return findFrom(s, 0, search);
+}
+
+int findFrom(const string_res &s, size_t fromPos, char search) {
+    // FIXME: This paricular overload (find of single char) is optimized to use memchr.
+    // The general overload (find of string, memchr applying to its first character) and `contains` should be adjusted to match.
+    char * searchFrom = s.Handle.s + fromPos;
+    size_t searchLnth = s.Handle.lnth - fromPos;
+    int searchVal = search;
+    char * foundAt = (char *) memchr(searchFrom, searchVal, searchLnth);
+    if (foundAt == 0p) return s.Handle.lnth;
+    else return foundAt - s.Handle.s;
+}
+
+int find(const string_res &s, const string_res &search) {
+    return findFrom(s, 0, search);
+}
+
+int findFrom(const string_res &s, size_t fromPos, const string_res &search) {
+    return findFrom(s, fromPos, search.Handle.s, search.Handle.lnth);
+}
+
+int find(const string_res &s, const char* search) {
+    return findFrom(s, 0, search);
+}
+int findFrom(const string_res &s, size_t fromPos, const char* search) {
+    return findFrom(s, fromPos, search, strlen(search));
+}
+
+int find(const string_res &s, const char* search, size_t searchsize) {
+    return findFrom(s, 0, search, searchsize);
+}
+
+int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize) {
 
     /* Remaining implementations essentially ported from Sunjay's work */
 
-int find(const string_res &s, const string_res &search) {
-    return find(s, search.Handle.s, search.Handle.lnth);
-}
-
-int find(const string_res &s, const char* search) {
-    return find(s, search, strlen(search));
-}
-
-int find(const string_res &s, const char* search, size_t searchsize) {
+
     // FIXME: This is a naive algorithm. We probably want to switch to someting
     // like Boyer-Moore in the future.
@@ -481 +643 @@
     }
 
-    for (size_t i = 0; i < s.Handle.lnth; i++) {
+    for (size_t i = fromPos; i < s.Handle.lnth; i++) {
         size_t remaining = s.Handle.lnth - i;
         // Never going to find the search string if the remaining string is
@@ -596 +758 @@
 // Add a new HandleNode node n after the current HandleNode node.
 
-static inline void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
+static void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:AddThisAfter, this:" | &this | " n:" | &n;
 #endif // VbyteDebug
+    // Performance note: we are on the critical path here. MB has ensured that the verifies don't contribute to runtime (are compiled away, like they're supposed to be).
+    verify( n.ulink != 0p );
+    verify( this.ulink == n.ulink );
     flink = n.flink;
     blink = &n;
@@ -624 +789 @@
 // Delete the current HandleNode node.
 
-static inline void DeleteNode( HandleNode & this ) with(this) {
+static void DeleteNode( HandleNode & this ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:DeleteNode, this:" | &this;
@@ -638 +803 @@
 
 // Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
-// allocation, the garbage collection routine is called and a second attempt is made to allocate the space. If the
-// second attempt fails, a further attempt is made to create a new, larger byte-string area.
-
-static inline char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
+// allocation, the garbage collection routine is called.
+
+static char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:VbyteAlloc, size:" | size;
@@ -650 +814 @@
     NoBytes = ( uintptr_t )EndVbyte + size;
     if ( NoBytes > ( uintptr_t )ExtVbyte ) {            // enough room for new byte-string ?
-                garbage( this );                                        // firer up the garbage collector
-                NoBytes = ( uintptr_t )EndVbyte + size;         // try again
-                if ( NoBytes > ( uintptr_t )ExtVbyte ) {        // enough room for new byte-string ?
-assert( 0 && "need to implement actual growth" );
-                        // extend( size );                              // extend the byte-string area
-                } // if
+                garbage( this, size );                                  // firer up the garbage collector
+                verify( (( uintptr_t )EndVbyte + size) <= ( uintptr_t )ExtVbyte  && "garbage run did not free up required space" );
     } // if
     r = EndVbyte;
@@ -666 +826 @@
 
 
+// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer
+// new allocations of its original size + delta bytes. Positive delta means bigger;
+// negative means smaller.  A null return indicates that the original heap location has room for
+// the requested growth.  A non-null return indicates that copying to a new location is required
+// but has not been done; the returned value is the old heap storage location; `this` heap is
+// modified to reference the new location.  In the copy-requred case, the caller should use
+// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old.
+
+static char * VbyteTryAdjustLast( VbyteHeap & this, int delta ) with(this) {
+
+    if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) {
+        // room available
+        EndVbyte += delta;
+        return 0p;
+    }
+
+    char *oldBytes = StartVbyte;
+
+    NoOfExtensions += 1;
+    CurrSize *= 2;
+    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
+    ExtVbyte = StartVbyte + CurrSize;
+
+    return oldBytes;
+}
+
+
 // Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
 // the address in the byte string area.
 
-static inline void MoveThisAfter( HandleNode & this, const HandleNode  & h ) with(this) {
+static void MoveThisAfter( HandleNode & this, const HandleNode  & h ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:MoveThisAfter, this:" | & this | " h:" | & h;
 #endif // VbyteDebug
+    verify( h.ulink != 0p );
+    verify( this.ulink == h.ulink );
     if ( s < h.s ) {                                    // check argument values
                 // serr | "VbyteSM: Error - Cannot move byte string starting at:" | s | " after byte string starting at:"
                 //      | ( h->s ) | " and keep handles in ascending order";
                 // exit(-1 );
-                assert( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
+                verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
     } // if
 
@@ -709 +898 @@
 //######################### VbyteHeap #########################
 
-// Move characters from one location in the byte-string area to another. The routine handles the following situations:
-//
-// if the |Src| > |Dst| => truncate
-// if the |Dst| > |Src| => pad Dst with blanks
-
-void ByteCopy( VbyteHeap & this, char *Dst, int DstStart, int DstLnth, char *Src, int SrcStart, int SrcLnth ) {
-    for ( int i = 0; i < DstLnth; i += 1 ) {
-      if ( i == SrcLnth ) {                             // |Dst| > |Src|
-            for ( ; i < DstLnth; i += 1 ) {             // pad Dst with blanks
-                Dst[DstStart + i] = ' ';
-            } // for
-            break;
-        } // exit
-        Dst[DstStart + i] = Src[SrcStart + i];
-    } // for
-} // ByteCopy
-
 // Compare two byte strings in the byte-string area. The routine returns the following values:
 //
@@ -732 +904 @@
 // -1 => Src1-byte-string < Src2-byte-string
 
-int ByteCmp( VbyteHeap & this, char *Src1, int Src1Start, int Src1Lnth, char *Src2, int Src2Start, int Src2Lnth )  with(this) {
+int ByteCmp( char *Src1, int Src1Start, int Src1Lnth, char *Src2, int Src2Start, int Src2Lnth )  {
 #ifdef VbyteDebug
     serr | "enter:ByteCmp, Src1Start:" | Src1Start | " Src1Lnth:" | Src1Lnth | " Src2Start:" | Src2Start | " Src2Lnth:" | Src2Lnth;
@@ -789 +961 @@
     h = Header.flink;                                   // ignore header node
     for (;;) {
-                ByteCopy( this, EndVbyte, 0, h->lnth, h->s, 0, h->lnth );
+                memmove( EndVbyte, h->s, h->lnth );
                 obase = h->s;
                 h->s = EndVbyte;
@@ -810 +982 @@
 
 
+static double heap_expansion_freespace_threshold = 0.1;  // default inherited from prior work: expand heap when less than 10% "free" (i.e. garbage)
+                                                         // probably an unreasonable default, but need to assess early-round tests on changing it
+
+void TUNING_set_string_heap_liveness_threshold( double val ) {
+    heap_expansion_freespace_threshold = 1.0 - val;
+}
+
+
 // Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
 // the heap.  The heap is then compacted in the existing heap or into the newly allocated heap.
 
-void garbage(VbyteHeap & this ) with(this) {
+void garbage(VbyteHeap & this, int minreq ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:garbage";
@@ -837 +1017 @@
     AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
     
-    if ( AmountFree < ( int )( CurrSize * 0.1 )) {      // free space less than 10% ?
-
-assert( 0 && "need to implement actual growth" );
-//              extend( CurrSize );                             // extend the heap
+    if ( ( double ) AmountFree < ( CurrSize * heap_expansion_freespace_threshold ) || AmountFree < minreq ) {   // free space less than threshold or not enough to serve cur request
+
+                extend( this, max( CurrSize, minreq ) );                                // extend the heap
 
                         //  Peter says, "This needs work before it should be used."
@@ -846 +1025 @@
                         //              reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory
 
-    } // if
-    compaction(this);                                   // compact the byte area, in the same or new heap area
+        // `extend` implies a `compaction` during the copy
+
+    } else {
+        compaction(this);                                       // in-place
+    }// if
 #ifdef VbyteDebug
     {
@@ -867 +1049 @@
 #undef VbyteDebug
 
-//WIP
-#if 0
 
 
@@ -874 +1054 @@
 // area is deleted.
 
-void VbyteHeap::extend( int size ) {
+void extend( VbyteHeap & this, int size ) with (this) {
 #ifdef VbyteDebug
     serr | "enter:extend, size:" | size;
@@ -884 +1064 @@
     
     CurrSize += size > InitSize ? size : InitSize;      // minimum extension, initial size
-    StartVbyte = EndVbyte = new char[CurrSize];
+    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
     ExtVbyte = (void *)( StartVbyte + CurrSize );
-    compaction();                                       // copy from old heap to new & adjust pointers to new heap
-    delete OldStartVbyte;                               // release old heap
+    compaction(this);                                   // copy from old heap to new & adjust pointers to new heap
+    free( OldStartVbyte );                              // release old heap
 #ifdef VbyteDebug
     serr | "exit:extend, CurrSize:" | CurrSize;
@@ -893 +1073 @@
 } // extend
 
+//WIP
+#if 0
 
 // Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string

libcfa/src/containers/string_res.hfa

@@ -17 +17 @@
 
 #include <fstream.hfa>
+#include <string.h>    // e.g. strlen
 
     
@@ -27 +28 @@
     HandleNode *flink;                                  // forward link
     HandleNode *blink;                                  // backward link
+    VbyteHeap *ulink;                   // upward link
 
     char *s;                                            // pointer to byte string
@@ -32 +34 @@
 }; // HandleNode
 
-void ?{}( HandleNode & );                       // constructor for header node
-
-void ?{}( HandleNode &, VbyteHeap & );          // constructor for nodes in the handle list
-void ^?{}( HandleNode & );                      // destructor for handle nodes
-
-extern VbyteHeap * DEBUG_string_heap;
+VbyteHeap * DEBUG_string_heap();
+size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap );
 size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap );
 const char * DEBUG_string_heap_start( VbyteHeap * heap );
 
+void TUNING_set_string_heap_liveness_threshold( double val );
 
 //######################### String #########################
@@ -47 +46 @@
 struct string_res {
     HandleNode Handle; // chars, start, end, global neighbours
+    bool shareEditSet_owns_ulink;
     string_res * shareEditSet_prev;
     string_res * shareEditSet_next;
@@ -74 +74 @@
 // Constructors, Assignment Operators, Destructor
 void ?{}(string_res &s); // empty string
-void ?{}(string_res &s, const char* initial); // copy from string literal (NULL-terminated)
 void ?{}(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer
+static inline void ?{}(string_res &s, const char* rhs) { // copy from string literal (NULL-terminated)
+    (s){ rhs, strlen(rhs) };
+}
 
 void ?{}(string_res &s, const string_res & s2) = void;
@@ -86 +88 @@
 }
 
-void assign(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer
-void ?=?(string_res &s, const char* other); // copy from string literal (NULL-terminated)
-void ?=?(string_res &s, const string_res &other);
-void ?=?(string_res &s, string_res &other);
-void ?=?(string_res &s, char other);
+string_res & assign(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer
+static inline string_res & ?=?(string_res &s, const char* other) {  // copy from string literal (NULL-terminated)
+    return assign(s, other, strlen(other));
+}
+string_res & ?=?(string_res &s, const string_res &other);
+string_res & ?=?(string_res &s, string_res &other);
+string_res & ?=?(string_res &s, char other);
 
 void ^?{}(string_res &s);
@@ -99 +103 @@
 
 // Concatenation
+void append(string_res &s, const char* buffer, size_t bsize);
 void ?+=?(string_res &s, char other); // append a character
 void ?+=?(string_res &s, const string_res &s2); // append-concatenate to first string
-void ?+=?(string_res &s, const char* other);
-void append(string_res &s, const char* buffer, size_t bsize);
+static inline void ?+=?(string_res &s, const char* other) {
+    append( s, other, strlen(other) );
+}
 
 // Character access
+void assignAt(const string_res &s, size_t index, char val);
 char ?[?](const string_res &s, size_t index); // Mike changed to ret by val from Sunjay's ref, to match Peter's
 //char codePointAt(const string_res &s, size_t index); // revisit under Unicode
@@ -121 +128 @@
 int find(const string_res &s, const char* search);
 int find(const string_res &s, const char* search, size_t searchsize);
+
+int findFrom(const string_res &s, size_t fromPos, char search);
+int findFrom(const string_res &s, size_t fromPos, const string_res &search);
+int findFrom(const string_res &s, size_t fromPos, const char* search);
+int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize);
 
 bool includes(const string_res &s, const string_res &search);

libcfa/src/math.trait.hfa

@@ -16 +16 @@
 #pragma once
 
-trait Not( T ) {
-        void ?{}( T &, zero_t );
-        int !?( T );
+trait Not( U ) {
+        void ?{}( U &, zero_t );
+        int !?( U );
 }; // Not
 
@@ -26 +26 @@
 }; // Equality
 
-trait Relational( T | Equality( T ) ) {
-        int ?<?( T, T );
-        int ?<=?( T, T );
-        int ?>?( T, T );
-        int ?>=?( T, T );
+trait Relational( U | Equality( U ) ) {
+        int ?<?( U, U );
+        int ?<=?( U, U );
+        int ?>?( U, U );
+        int ?>=?( U, U );
 }; // Relational
 
@@ -39 +39 @@
 }; // Signed
 
-trait Additive( T | Signed( T ) ) {
-        T ?+?( T, T );
-        T ?-?( T, T );
-        T ?+=?( T &, T );
-        T ?-=?( T &, T );
+trait Additive( U | Signed( U ) ) {
+        U ?+?( U, U );
+        U ?-?( U, U );
+        U ?+=?( U &, U );
+        U ?-=?( U &, U );
 }; // Additive
 
@@ -49 +49 @@
         void ?{}( T &, one_t );
         // T ?++( T & );
-        // T ++?( T &);
+        // T ++?( T & );
         // T ?--( T & );
         // T --?( T & );
 }; // Incdec
 
-trait Multiplicative( T | Incdec( T ) ) {
-        T ?*?( T, T );
-        T ?/?( T, T );
-        T ?%?( T, T );
-        T ?/=?( T &, T );
+trait Multiplicative( U | Incdec( U ) ) {
+        U ?*?( U, U );
+        U ?/?( U, U );
+        U ?%?( U, U );
+        U ?/=?( U &, U );
 }; // Multiplicative