Changes in libcfa/src/concurrency/kernel_private.hfa [dd4e2d7:13c5e19]

File:

• libcfa/src/concurrency/kernel_private.hfa (modified) (5 diffs)

libcfa/src/concurrency/kernel_private.hfa

@@ -20 +20 @@
 
 #include "alarm.hfa"
+#include "stats.hfa"
+
+#include "bits/random.hfa"
 
 
 //-----------------------------------------------------------------------------
 // Scheduler
+
+struct __attribute__((aligned(128))) __scheduler_lock_id_t;
 
 extern "C" {
@@ -31 +36 @@
 }
 
-void __schedule_thread( $thread * ) __attribute__((nonnull (1)));
+void __schedule_thread( struct __processor_id_t *, $thread * ) __attribute__((nonnull (2)));
 
 //Block current thread and release/wake-up the following resources
@@ -73 +78 @@
 
 // KERNEL ONLY unpark with out disabling interrupts
-void __unpark( $thread * thrd __cfaabi_dbg_ctx_param2 );
+void __unpark( struct __processor_id_t *, $thread * thrd __cfaabi_dbg_ctx_param2 );
 
 //-----------------------------------------------------------------------------
@@ -84 +89 @@
 //-----------------------------------------------------------------------------
 // Utils
-#define KERNEL_STORAGE(T,X) static char storage_##X[sizeof(T)]
-
-static inline uint32_t __tls_rand() {
-        kernelTLS.rand_seed ^= kernelTLS.rand_seed << 6;
-        kernelTLS.rand_seed ^= kernelTLS.rand_seed >> 21;
-        kernelTLS.rand_seed ^= kernelTLS.rand_seed << 7;
-        return kernelTLS.rand_seed;
+#define KERNEL_STORAGE(T,X) __attribute((aligned(__alignof__(T)))) static char storage_##X[sizeof(T)]
+
+static inline uint64_t __tls_rand() {
+        // kernelTLS.rand_seed ^= kernelTLS.rand_seed << 6;
+        // kernelTLS.rand_seed ^= kernelTLS.rand_seed >> 21;
+        // kernelTLS.rand_seed ^= kernelTLS.rand_seed << 7;
+        // return kernelTLS.rand_seed;
+        return __lehmer64( kernelTLS.rand_seed );
 }
 
@@ -100 +106 @@
 void unregister( struct cluster * cltr, struct $thread & thrd );
 
-void doregister( struct cluster * cltr, struct processor * proc );
-void unregister( struct cluster * cltr, struct processor * proc );
+//=======================================================================
+// Cluster lock API
+//=======================================================================
+// Cells use by the reader writer lock
+// while not generic it only relies on a opaque pointer
+struct __attribute__((aligned(128))) __scheduler_lock_id_t {
+        // Spin lock used as the underlying lock
+        volatile bool lock;
+
+        // Handle pointing to the proc owning this cell
+        // Used for allocating cells and debugging
+        __processor_id_t * volatile handle;
+
+        #ifdef __CFA_WITH_VERIFY__
+                // Debug, check if this is owned for reading
+                bool owned;
+        #endif
+};
+
+static_assert( sizeof(struct __scheduler_lock_id_t) <= __alignof(struct __scheduler_lock_id_t));
+
+// Lock-Free registering/unregistering of threads
+// Register a processor to a given cluster and get its unique id in return
+unsigned doregister( struct __processor_id_t * proc );
+
+// Unregister a processor from a given cluster using its id, getting back the original pointer
+void     unregister( struct __processor_id_t * proc );
+
+//=======================================================================
+// Reader-writer lock implementation
+// Concurrent with doregister/unregister,
+//    i.e., threads can be added at any point during or between the entry/exit
+
+//-----------------------------------------------------------------------
+// simple spinlock underlying the RWLock
+// Blocking acquire
+static inline void __atomic_acquire(volatile bool * ll) {
+        while( __builtin_expect(__atomic_exchange_n(ll, (bool)true, __ATOMIC_SEQ_CST), false) ) {
+                while(__atomic_load_n(ll, (int)__ATOMIC_RELAXED))
+                        asm volatile("pause");
+        }
+        /* paranoid */ verify(*ll);
+}
+
+// Non-Blocking acquire
+static inline bool __atomic_try_acquire(volatile bool * ll) {
+        return !__atomic_exchange_n(ll, (bool)true, __ATOMIC_SEQ_CST);
+}
+
+// Release
+static inline void __atomic_unlock(volatile bool * ll) {
+        /* paranoid */ verify(*ll);
+        __atomic_store_n(ll, (bool)false, __ATOMIC_RELEASE);
+}
+
+//-----------------------------------------------------------------------
+// Reader-Writer lock protecting the ready-queues
+// while this lock is mostly generic some aspects
+// have been hard-coded to for the ready-queue for
+// simplicity and performance
+struct __scheduler_RWLock_t {
+        // total cachelines allocated
+        unsigned int max;
+
+        // cachelines currently in use
+        volatile unsigned int alloc;
+
+        // cachelines ready to itereate over
+        // (!= to alloc when thread is in second half of doregister)
+        volatile unsigned int ready;
+
+        // writer lock
+        volatile bool lock;
+
+        // data pointer
+        __scheduler_lock_id_t * data;
+};
+
+void  ?{}(__scheduler_RWLock_t & this);
+void ^?{}(__scheduler_RWLock_t & this);
+
+extern __scheduler_RWLock_t * __scheduler_lock;
+
+//-----------------------------------------------------------------------
+// Reader side : acquire when using the ready queue to schedule but not
+//  creating/destroying queues
+static inline void ready_schedule_lock( struct __processor_id_t * proc) with(*__scheduler_lock) {
+        unsigned iproc = proc->id;
+        /*paranoid*/ verify(data[iproc].handle == proc);
+        /*paranoid*/ verify(iproc < ready);
+
+        // Step 1 : make sure no writer are in the middle of the critical section
+        while(__atomic_load_n(&lock, (int)__ATOMIC_RELAXED))
+                asm volatile("pause");
+
+        // Fence needed because we don't want to start trying to acquire the lock
+        // before we read a false.
+        // Not needed on x86
+        // std::atomic_thread_fence(std::memory_order_seq_cst);
+
+        // Step 2 : acquire our local lock
+        __atomic_acquire( &data[iproc].lock );
+        /*paranoid*/ verify(data[iproc].lock);
+
+        #ifdef __CFA_WITH_VERIFY__
+                // Debug, check if this is owned for reading
+                data[iproc].owned = true;
+        #endif
+}
+
+static inline void ready_schedule_unlock( struct __processor_id_t * proc) with(*__scheduler_lock) {
+        unsigned iproc = proc->id;
+        /*paranoid*/ verify(data[iproc].handle == proc);
+        /*paranoid*/ verify(iproc < ready);
+        /*paranoid*/ verify(data[iproc].lock);
+        /*paranoid*/ verify(data[iproc].owned);
+        #ifdef __CFA_WITH_VERIFY__
+                // Debug, check if this is owned for reading
+                data[iproc].owned = false;
+        #endif
+        __atomic_unlock(&data[iproc].lock);
+}
+
+#ifdef __CFA_WITH_VERIFY__
+        static inline bool ready_schedule_islocked( struct __processor_id_t * proc) {
+                return __scheduler_lock->data[proc->id].owned;
+        }
+
+        static inline bool ready_mutate_islocked() {
+                return __scheduler_lock->lock;
+        }
+#endif
+
+//-----------------------------------------------------------------------
+// Writer side : acquire when changing the ready queue, e.g. adding more
+//  queues or removing them.
+uint_fast32_t ready_mutate_lock( void );
+
+void ready_mutate_unlock( uint_fast32_t /* value returned by lock */ );
+
+//=======================================================================
+// Ready-Queue API
+//-----------------------------------------------------------------------
+// pop thread from the ready queue of a cluster
+// returns 0p if empty
+__attribute__((hot)) bool query(struct cluster * cltr);
+
+//-----------------------------------------------------------------------
+// push thread onto a ready queue for a cluster
+// returns true if the list was previously empty, false otherwise
+__attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd);
+
+//-----------------------------------------------------------------------
+// pop thread from the ready queue of a cluster
+// returns 0p if empty
+__attribute__((hot)) struct $thread * pop(struct cluster * cltr);
+
+//-----------------------------------------------------------------------
+// remove thread from the ready queue of a cluster
+// returns bool if it wasn't found
+bool remove_head(struct cluster * cltr, struct $thread * thrd);
+
+//-----------------------------------------------------------------------
+// Increase the width of the ready queue (number of lanes) by 4
+void ready_queue_grow  (struct cluster * cltr);
+
+//-----------------------------------------------------------------------
+// Decrease the width of the ready queue (number of lanes) by 4
+void ready_queue_shrink(struct cluster * cltr);
+
+//-----------------------------------------------------------------------
+// Statics call at the end of each thread to register statistics
+#if !defined(__CFA_NO_STATISTICS__)
+static inline struct __stats_t * __tls_stats() {
+        /* paranoid */ verify( ! kernelTLS.preemption_state.enabled );
+        /* paranoid */ verify( kernelTLS.this_stats );
+        return kernelTLS.this_stats;
+}
+#endif
 
 // Local Variables: //