Changes in libcfa/src/concurrency/ready_queue.cfa [75c7252:1f45c7d]

File:

• libcfa/src/concurrency/ready_queue.cfa (modified) (30 diffs)

libcfa/src/concurrency/ready_queue.cfa

@@ -67 +67 @@
 #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 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);
 
@@ -100 +100 @@
         #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);
+        void __kernel_raw_rseq_register  (void);
+        void __kernel_raw_rseq_unregister(void);
 
         #define __kernel_rseq_register __kernel_raw_rseq_register
@@ -246 +246 @@
 // Cforall Ready Queue used for scheduling
 //=======================================================================
-unsigned long long moving_average(unsigned long long nval, unsigned long long oval) {
-        const unsigned long long tw = 16;
-        const unsigned long long nw = 4;
-        const unsigned long long ow = tw - nw;
-        return ((nw * nval) + (ow * oval)) / tw;
-}
-
 void ?{}(__ready_queue_t & this) with (this) {
         #if defined(USE_CPU_WORK_STEALING)
@@ -258 +251 @@
                 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.help  = 0p;
                 lanes.count = 0;
         #endif
@@ -285 +270 @@
         free(lanes.data);
         free(lanes.tscs);
-        free(lanes.help);
 }
 
 //-----------------------------------------------------------------------
 #if defined(USE_CPU_WORK_STEALING)
-        __attribute__((hot)) void push(struct cluster * cltr, struct thread$ * thrd, unpark_hint hint) with (cltr->ready_queue) {
+        __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd, bool push_local) 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 bool external = !push_local || (!proc) || (cltr != proc->cltr);
+
                 const int cpu = __kernel_getcpu();
                 /* paranoid */ verify(cpu >= 0);
@@ -302 +285 @@
                 /* 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];
-                }
+                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);
@@ -323 +296 @@
                         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);
-                        }
+                        i = start + (r % READYQ_SHARD_FACTOR);
                         // If we can't lock it retry
                 } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
@@ -346 +316 @@
 
         // Pop from the ready queue from a given cluster
-        __attribute__((hot)) thread$ * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
+        __attribute__((hot)) $thread * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
                 /* paranoid */ verify( lanes.count > 0 );
                 /* paranoid */ verify( kernelTLS().this_processor );
@@ -362 +332 @@
                 processor * const proc = kernelTLS().this_processor;
                 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 == -1u) {
-                        unsigned long long max = 0;
+                        // if We don't have a
+                        unsigned long long min = ts(lanes.data[start]);
                         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;
+                                unsigned long long tsc = ts(lanes.data[start + i]);
+                                if(tsc < min) min = tsc;
+                        }
+                        proc->rdq.cutoff = min;
+
                         /* 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)) {
+                        if(0 == (__tls_rand() % 10_000)) {
                                 proc->rdq.target = __tls_rand() % lanes.count;
                         } else {
@@ -387 +358 @@
                 }
                 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;
+                        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;
                         {
                                 unsigned target = proc->rdq.target;
                                 proc->rdq.target = -1u;
-                                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));
+                                if(lanes.tscs[target].tv < cutoff && ts(lanes.data[target]) < cutoff) {
+                                        $thread * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
                                         proc->rdq.last = target;
                                         if(t) return t;
-                                        else proc->rdq.target = -1u;
                                 }
-                                else proc->rdq.target = -1u;
                         }
 
                         unsigned last = proc->rdq.last;
                         if(last != -1u && lanes.tscs[last].tv < cutoff && ts(lanes.data[last]) < cutoff) {
-                                thread$ * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.help));
+                                $thread * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.help));
                                 if(t) return t;
                         }
@@ -418 +382 @@
                 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;
+                        if($thread * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t;
                 }
 
@@ -425 +389 @@
         }
 
-        __attribute__((hot)) struct thread$ * pop_slow(struct cluster * cltr) with (cltr->ready_queue) {
+        __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 != -1u) {
-                        struct thread$ * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.steal));
+                        struct $thread * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.steal));
                         if(t) return t;
                         proc->rdq.last = -1u;
@@ -437 +401 @@
                 return try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.steal));
         }
-        __attribute__((hot)) struct thread$ * pop_search(struct cluster * cltr) {
+        __attribute__((hot)) struct $thread * pop_search(struct cluster * cltr) {
                 return search(cltr);
         }
@@ -464 +428 @@
         }
 
-        __attribute__((hot)) void push(struct cluster * cltr, struct thread$ * thrd, unpark_hint hint) with (cltr->ready_queue) {
+        __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd, bool push_local) 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);
+                const bool external = !push_local || (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
                 /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
 
@@ -511 +475 @@
 
         // Pop from the ready queue from a given cluster
-        __attribute__((hot)) thread$ * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
+        __attribute__((hot)) $thread * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
                 /* paranoid */ verify( lanes.count > 0 );
                 /* paranoid */ verify( kernelTLS().this_processor );
@@ -535 +499 @@
 
                         // 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)));
+                        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;
@@ -545 +509 @@
         }
 
-        __attribute__((hot)) struct thread$ * pop_slow(struct cluster * cltr) { return pop_fast(cltr); }
-        __attribute__((hot)) struct thread$ * pop_search(struct cluster * cltr) {
+        __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) {
+        __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd, bool push_local) 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);
+                const bool external = !push_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 == -1u || thrd->curr_cluster != cltr;
+                        const bool external = push_local || (!kernelTLS().this_processor) || preferred == -1u || thrd->curr_cluster != cltr;
                         /* paranoid */ verifyf(external || preferred < lanes.count, "Invalid preferred queue %u for %u lanes", preferred, lanes.count );
 
@@ -605 +569 @@
 
         // Pop from the ready queue from a given cluster
-        __attribute__((hot)) thread$ * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
+        __attribute__((hot)) $thread * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
                 /* paranoid */ verify( lanes.count > 0 );
                 /* paranoid */ verify( kernelTLS().this_processor );
@@ -627 +591 @@
                         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) {
-                                thread$ * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
+                                $thread * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
                                 if(t) return t;
                         }
@@ -634 +598 @@
                 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;
+                        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) {
+        __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) {
+        __attribute__((hot)) struct $thread * pop_search(struct cluster * cltr) with (cltr->ready_queue) {
                 return search(cltr);
         }
@@ -657 +621 @@
 //-----------------------------------------------------------------------
 // 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) {
+static inline struct $thread * try_pop(struct cluster * cltr, unsigned w __STATS(, __stats_readyQ_pop_t & stats)) with (cltr->ready_queue) {
         __STATS( stats.attempt++; )
 
@@ -680 +644 @@
 
         // Actually pop the list
-        struct thread$ * thrd;
-        unsigned long long tsc_before = ts(lane);
+        struct $thread * thrd;
         unsigned long long tsv;
         [thrd, tsv] = pop(lane);
@@ -695 +658 @@
         __STATS( stats.success++; )
 
-        #if defined(USE_WORK_STEALING) || defined(USE_CPU_WORK_STEALING)
-                unsigned long long now = rdtscl();
+        #if defined(USE_WORK_STEALING)
                 lanes.tscs[w].tv = tsv;
-                lanes.tscs[w].ma = moving_average(now > tsc_before ? now - tsc_before : 0, lanes.tscs[w].ma);
         #endif
 
-        #if defined(USE_CPU_WORK_STEALING)
-                thrd->preferred = w / READYQ_SHARD_FACTOR;
-        #else
-                thrd->preferred = w;
-        #endif
+        thrd->preferred = w;
 
         // return the popped thread
@@ -714 +671 @@
 // 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) {
+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 );
@@ -720 +677 @@
         for(i; count) {
                 unsigned idx = (offset + i) % count;
-                struct thread$ * thrd = try_pop(cltr, idx __STATS(, __tls_stats()->ready.pop.search));
+                struct $thread * thrd = try_pop(cltr, idx __STATS(, __tls_stats()->ready.pop.search));
                 if(thrd) {
                         return thrd;
@@ -728 +685 @@
         // All lanes where empty return 0p
         return 0p;
-}
-
-//-----------------------------------------------------------------------
-// get preferred ready for new thread
-unsigned ready_queue_new_preferred() {
-        unsigned pref = 0;
-        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;
 }
 
@@ -776 +712 @@
 //-----------------------------------------------------------------------
 // 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->ready_queue) {
         // Pick the bet list
         int w = i;
@@ -911 +847 @@
                                 // 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;
+                                        struct $thread * thrd;
                                         unsigned long long _;
                                         [thrd, _] = pop(lanes.data[idx]);
@@ -979 +915 @@
         extern void __enable_interrupts_hard();
 
-        static void __kernel_raw_rseq_register  (void) {
+        void __kernel_raw_rseq_register  (void) {
                 /* paranoid */ verify( __cfaabi_rseq.cpu_id == RSEQ_CPU_ID_UNINITIALIZED );
 
@@ -997 +933 @@
         }
 
-        static void __kernel_raw_rseq_unregister(void) {
+        void __kernel_raw_rseq_unregister(void) {
                 /* paranoid */ verify( __cfaabi_rseq.cpu_id >= 0 );