Changeset df6cc9d for libcfa/src/concurrency/kernel

Timestamp:

Oct 19, 2022, 4:43:26 PM (2 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, ast-experimental, master

Children:

1a45263

Parents:

9cd5bd2 (diff), 135143b (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' into pthread-emulation

Location:

libcfa/src/concurrency/kernel

Files:

• cluster.cfa (modified) (3 diffs)
• cluster.hfa (modified) (3 diffs)
• fwd.hfa (modified) (1 diff)
• private.hfa (modified) (2 diffs)
• startup.cfa (modified) (3 diffs)

libcfa/src/concurrency/kernel/cluster.cfa

@@ -221 +221 @@
 static const unsigned __readyq_single_shard = 2;
 
+void  ?{}(__timestamp_t & this) { this.t.tv = 0; this.t.ma = 0; }
+void ^?{}(__timestamp_t &) {}
+
 //-----------------------------------------------------------------------
 // Check that all the intrusive queues in the data structure are still consistent
@@ -254 +257 @@
 }
 
-static void assign_list(unsigned & valrq, unsigned & valio, dlist(processor) & list, unsigned count) {
-        processor * it = &list`first;
+static void assign_list(unsigned & valrq, unsigned & valio, dlist(struct processor) & list, unsigned count) {
+        struct 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);
@@ -278 +281 @@
 
 #if defined(CFA_HAVE_LINUX_IO_URING_H)
-        static void assign_io(io_context$ ** data, size_t count, dlist(processor) & list) {
-                processor * it = &list`first;
+        static void assign_io(io_context$ ** data, size_t count, dlist(struct processor) & list) {
+                struct processor * it = &list`first;
                 while(it) {
                         /* paranoid */ verifyf( it, "Unexpected null iterator\n");

libcfa/src/concurrency/kernel/cluster.hfa

@@ -18 +18 @@
 #include "device/cpu.hfa"
 #include "kernel/private.hfa"
+#include "math.hfa"
 
 #include <limits.h>
+#include <inttypes.h>
+
+#include "clock.hfa"
+
+#if   defined(READYQ_USE_LINEAR_AVG)
+
+// no conversion needed in this case
+static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { return intsc; }
+
+// warn normally all ints
+#define warn_large_before warnf( !strict || old_avg < 33_000_000_000, "Suspiciously large previous average: %'llu (%llx), %'" PRId64 "ms \n", old_avg, old_avg, program()`ms )
+#define warn_large_after warnf( !strict || ret < 33_000_000_000, "Suspiciously large new average after %'" PRId64 "ms cputime: %'llu (%llx) from %'llu-%'llu (%'llu, %'llu) and %'llu\n", program()`ms, ret, ret, currtsc, intsc, new_val, new_val / 1000000, old_avg )
+
+// 8X linear factor is just 8 * x
+#define AVG_FACTOR( x ) (8 * (x))
+
+#elif defined(READYQ_USE_LOGDBL_AVG)
+
+// convert to log2 scale but using double
+static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { if(unlikely(0 == intsc)) return 0.0; else return log2(intsc); }
+
+#define warn_large_before warnf( !strict || old_avg < 35.0, "Suspiciously large previous average: %'lf, %'" PRId64 "ms \n", old_avg, program()`ms )
+#define warn_large_after warnf( !strict || ret < 35.3, "Suspiciously large new average after %'" PRId64 "ms cputime: %'lf from %'llu-%'llu (%'llu, %'llu) and %'lf\n", program()`ms, ret, currtsc, intsc, new_val, new_val / 1000000, old_avg ); \
+verify(ret >= 0)
+
+// 8X factor in logscale is log2(8X) = log2(8) + log2(X) = 3 + log2(X)
+#define AVG_FACTOR( x ) (3.0 + (x))
+
+// we need to overload the __atomic_load_n because they don't support double
+static inline double __atomic_load_n(volatile double * ptr, int mem) {
+        volatile uint64_t * uptr = (volatile uint64_t *)ptr;
+        _Static_assert(sizeof(*uptr) == sizeof(*ptr));
+        uint64_t ret = 0;
+        ret = __atomic_load_n(uptr, mem);
+        uint64_t *rp = &ret;
+        double ret = *(volatile double *)rp;
+        /* paranoid */ verify( ret == 0 || ret > 3e-100 );
+        return ret;
+}
+
+// we need to overload the __atomic_store_n because they don't support double
+static inline void __atomic_store_n(volatile double * ptr, double val, int mem) {
+        /* paranoid */ verify( val == 0 || val > 3e-100 );
+        volatile uint64_t * uptr = (volatile uint64_t *)ptr;
+        _Static_assert(sizeof(*uptr) == sizeof(*ptr));
+        uint64_t * valp = (uint64_t *)&val;
+        __atomic_store_n(uptr, *valp, mem);
+}
+
+#elif defined(READYQ_USE_LOGDBL_AVG)
+
+//convert to log2 scale but with fix point u32.32 values
+static inline __readyQ_avg_t __to_readyQ_avg(unsigned long long intsc) { return ulog2_32_32(tsc); }
+
+// 8X factor, +3 in logscale (see above) is + 0x3.00000000
+#define AVG_FACTOR( x ) (0x3_00000000ull + (x))
+
+#else
+#error must pick a scheme for averaging
+#endif
 
 //-----------------------------------------------------------------------
 // Calc moving average based on existing average, before and current time.
-static inline unsigned long long moving_average(unsigned long long currtsc, unsigned long long instsc, unsigned long long old_avg) {
-        /* paranoid */ verifyf( old_avg < 15000000000000, "Suspiciously large previous average: %'llu (%llx)\n", old_avg, old_avg );
+static inline __readyQ_avg_t moving_average(unsigned long long currtsc, unsigned long long intsc, __readyQ_avg_t old_avg, bool strict) {
+        (void)strict; // disable the warning around the fact this is unused in release.
+        /* paranoid */ warn_large_before;
 
-        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;
+        const unsigned long long new_val = currtsc > intsc ? currtsc - intsc : 0;
+        const __readyQ_avg_t total_weight = 16;
+        const __readyQ_avg_t new_weight   = 12;
+        const __readyQ_avg_t old_weight = total_weight - new_weight;
+        const __readyQ_avg_t ret = ((new_weight * __to_readyQ_avg(new_val)) + (old_weight * old_avg)) / total_weight;
+
+        /* paranoid */ warn_large_after;
         return ret;
 }
 
-static inline void touch_tsc(__timestamp_t * tscs, size_t idx, unsigned long long ts_prev, unsigned long long ts_next) {
+static inline void touch_tsc(__timestamp_t * tscs, size_t idx, unsigned long long ts_prev, unsigned long long ts_next, bool strict) {
         if (ts_next == ULLONG_MAX) return;
         unsigned long long now = rdtscl();
-        unsigned long long pma = __atomic_load_n(&tscs[ idx ].t.ma, __ATOMIC_RELAXED);
+        __readyQ_avg_t pma = __atomic_load_n(&tscs[ idx ].t.ma, __ATOMIC_RELAXED);
         __atomic_store_n(&tscs[ idx ].t.tv, ts_next, __ATOMIC_RELAXED);
-        __atomic_store_n(&tscs[ idx ].t.ma, moving_average(now, ts_prev, pma), __ATOMIC_RELAXED);
+        __atomic_store_n(&tscs[ idx ].t.ma, moving_average(now, ts_prev, pma, strict), __ATOMIC_RELAXED);
 }
 
@@ -45 +109 @@
 // Calc age a timestamp should be before needing help.
 forall(Data_t * | { unsigned long long ts(Data_t & this); })
-static inline unsigned long long calc_cutoff(
+static inline __readyQ_avg_t calc_cutoff(
         const unsigned long long ctsc,
         unsigned procid,
@@ -51 +115 @@
         Data_t * data,
         __timestamp_t * tscs,
-        const unsigned shard_factor
+        const unsigned shard_factor,
+        bool strict
 ) {
         unsigned start = procid;
-        unsigned long long max = 0;
+        __readyQ_avg_t max = 0;
         for(i; shard_factor) {
                 unsigned long long ptsc = ts(data[start + i]);
                 if(ptsc != ULLONG_MAX) {
                         /* paranoid */ verify( start + i < count );
-                        unsigned long long tsc = moving_average(ctsc, ptsc, tscs[start + i].t.ma);
-                        if(tsc > max) max = tsc;
+                        __readyQ_avg_t avg = moving_average(ctsc, ptsc, tscs[start + i].t.ma, strict);
+                        if(avg > max) max = avg;
                 }
         }
-        return 8 * max;
+        return AVG_FACTOR( max );
 }
 

libcfa/src/concurrency/kernel/fwd.hfa

@@ -276 +276 @@
                         // intented to be use by wait, wait_any, waitfor, etc. rather than used directly
                         bool retract( future_t & this, oneshot & wait_ctx ) {
-                                struct oneshot * expected = this.ptr;
+                                struct oneshot * expected = &wait_ctx;
 
                                 // attempt to remove the context so it doesn't get consumed.

libcfa/src/concurrency/kernel/private.hfa

@@ -50 +50 @@
         #endif
 #endif
+// #define READYQ_USE_LINEAR_AVG
+#define READYQ_USE_LOGDBL_AVG
+// #define READYQ_USE_LOGINT_AVG
+
+#if   defined(READYQ_USE_LINEAR_AVG)
+typedef unsigned long long __readyQ_avg_t;
+#elif defined(READYQ_USE_LOGDBL_AVG)
+typedef double __readyQ_avg_t;
+#elif defined(READYQ_USE_LOGDBL_AVG)
+typedef unsigned long long __readyQ_avg_t;
+#else
+#error must pick a scheme for averaging
+#endif
 
 extern "C" {
@@ -65 +78 @@
 //-----------------------------------------------------------------------------
 // Scheduler
+union __attribute__((aligned(64))) __timestamp_t {
+        struct {
+                volatile unsigned long long tv;
+                volatile __readyQ_avg_t ma;
+        } t;
+        char __padding[192];
+};
+
 extern "C" {
         void disable_interrupts() OPTIONAL_THREAD;

libcfa/src/concurrency/kernel/startup.cfa

@@ -184 +184 @@
 
 
+extern void heapManagerCtor();
+extern void heapManagerDtor();
+
 //=============================================================================================
 // Kernel Setup logic
@@ -374 +377 @@
         proc->local_data = &__cfaabi_tls;
 
+        heapManagerCtor();                                                                      // initialize heap
+
         __cfa_io_start( proc );
         register_tls( proc );
@@ -425 +430 @@
         unregister_tls( proc );
         __cfa_io_stop( proc );
+
+        heapManagerDtor();                                                                      // de-initialize heap
 
         return 0p;