source: libcfa/src/concurrency/kernel_private.hfa @ a017ee7

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since a017ee7 was a017ee7, checked in by Thierry Delisle <tdelisle@…>, 3 years ago

Ready-queue grow/shrink now reassigns the id of all processors.

  • Property mode set to 100644
File size: 10.6 KB
RevLine 
[75f3522]1//
2// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
[73abe95]7// kernel_private.hfa --
[75f3522]8//
9// Author           : Thierry Delisle
10// Created On       : Mon Feb 13 12:27:26 2017
[6b0b624]11// Last Modified By : Peter A. Buhr
[fd9b524]12// Last Modified On : Wed Aug 12 08:21:33 2020
13// Update Count     : 9
[75f3522]14//
15
[6b0b624]16#pragma once
[75f3522]17
[58b6d1b]18#include "kernel.hfa"
19#include "thread.hfa"
[75f3522]20
[73abe95]21#include "alarm.hfa"
[8834751]22#include "stats.hfa"
[fa21ac9]23
[75f3522]24//-----------------------------------------------------------------------------
25// Scheduler
[1c273d0]26
[37ba662]27struct __attribute__((aligned(128))) __scheduler_lock_id_t;
[9b1dcc2]28
[1c273d0]29extern "C" {
[2026bb6]30        void disable_interrupts() OPTIONAL_THREAD;
[969b3fe]31        void enable_interrupts_noPoll();
[36982fc]32        void enable_interrupts( __cfaabi_dbg_ctx_param );
[1c273d0]33}
34
[e873838]35void __schedule_thread( $thread * )
[efc171d1]36#if defined(NDEBUG) || (!defined(__CFA_DEBUG__) && !defined(__CFA_VERIFY__))
[e873838]37        __attribute__((nonnull (1)))
[efc171d1]38#endif
39;
[75f3522]40
[8fc652e0]41extern bool __preemption_enabled();
42
[5afb49a]43//release/wake-up the following resources
44void __thread_finish( $thread * thrd );
[db6f06a]45
[75f3522]46//-----------------------------------------------------------------------------
47// Processor
48void main(processorCtx_t *);
[85b1deb]49
[8c50aed]50void * __create_pthread( pthread_t *, void * (*)(void *), void * );
[bfcf6b9]51void __destroy_pthread( pthread_t pthread, void * stack, void ** retval );
[1805b1b]52
[85b1deb]53
[75f3522]54
[6502a2b]55extern cluster * mainCluster;
56
[75f3522]57//-----------------------------------------------------------------------------
58// Threads
59extern "C" {
[c7a900a]60      void __cfactx_invoke_thread(void (*main)(void *), void * this);
[75f3522]61}
62
[f7d6bb0]63__cfaabi_dbg_debug_do(
[ac2b598]64        extern void __cfaabi_dbg_thread_register  ( $thread * thrd );
65        extern void __cfaabi_dbg_thread_unregister( $thread * thrd );
[f7d6bb0]66)
67
[6a77224]68#define TICKET_BLOCKED (-1) // thread is blocked
69#define TICKET_RUNNING ( 0) // thread is running
70#define TICKET_UNBLOCK ( 1) // thread should ignore next block
71
[969b3fe]72//-----------------------------------------------------------------------------
73// Utils
[ac2b598]74void doregister( struct cluster * cltr, struct $thread & thrd );
75void unregister( struct cluster * cltr, struct $thread & thrd );
[de94a60]76
[f00b26d4]77//-----------------------------------------------------------------------------
78// I/O
[78da4ab]79$io_arbiter * create(void);
80void destroy($io_arbiter *);
[f00b26d4]81
[7768b8d]82//=======================================================================
83// Cluster lock API
84//=======================================================================
85// Lock-Free registering/unregistering of threads
86// Register a processor to a given cluster and get its unique id in return
[a33c113]87void register_proc_id( struct __processor_id_t * );
[7768b8d]88
89// Unregister a processor from a given cluster using its id, getting back the original pointer
[a33c113]90void unregister_proc_id( struct __processor_id_t * proc );
[7768b8d]91
92//=======================================================================
93// Reader-writer lock implementation
94// Concurrent with doregister/unregister,
95//    i.e., threads can be added at any point during or between the entry/exit
[dca5802]96
97//-----------------------------------------------------------------------
98// simple spinlock underlying the RWLock
99// Blocking acquire
[7768b8d]100static inline void __atomic_acquire(volatile bool * ll) {
101        while( __builtin_expect(__atomic_exchange_n(ll, (bool)true, __ATOMIC_SEQ_CST), false) ) {
102                while(__atomic_load_n(ll, (int)__ATOMIC_RELAXED))
[fd9b524]103                        Pause();
[7768b8d]104        }
105        /* paranoid */ verify(*ll);
106}
107
[dca5802]108// Non-Blocking acquire
[7768b8d]109static inline bool __atomic_try_acquire(volatile bool * ll) {
[b798713]110        return !__atomic_exchange_n(ll, (bool)true, __ATOMIC_SEQ_CST);
[7768b8d]111}
112
[dca5802]113// Release
[7768b8d]114static inline void __atomic_unlock(volatile bool * ll) {
115        /* paranoid */ verify(*ll);
116        __atomic_store_n(ll, (bool)false, __ATOMIC_RELEASE);
117}
118
[a33c113]119// Cells use by the reader writer lock
120// while not generic it only relies on a opaque pointer
121struct __attribute__((aligned(128))) __scheduler_lock_id_t {
122        // Spin lock used as the underlying lock
123        volatile bool lock;
124
125        // Handle pointing to the proc owning this cell
126        // Used for allocating cells and debugging
127        __processor_id_t * volatile handle;
128
129        #ifdef __CFA_WITH_VERIFY__
130                // Debug, check if this is owned for reading
131                bool owned;
132        #endif
133};
134
135static_assert( sizeof(struct __scheduler_lock_id_t) <= __alignof(struct __scheduler_lock_id_t));
136
[b388ee81]137//-----------------------------------------------------------------------
138// Reader-Writer lock protecting the ready-queues
139// while this lock is mostly generic some aspects
140// have been hard-coded to for the ready-queue for
141// simplicity and performance
142struct __scheduler_RWLock_t {
143        // total cachelines allocated
144        unsigned int max;
145
146        // cachelines currently in use
147        volatile unsigned int alloc;
148
149        // cachelines ready to itereate over
150        // (!= to alloc when thread is in second half of doregister)
151        volatile unsigned int ready;
152
153        // writer lock
154        volatile bool lock;
155
156        // data pointer
[9b1dcc2]157        __scheduler_lock_id_t * data;
[b388ee81]158};
159
160void  ?{}(__scheduler_RWLock_t & this);
161void ^?{}(__scheduler_RWLock_t & this);
162
163extern __scheduler_RWLock_t * __scheduler_lock;
164
[7768b8d]165//-----------------------------------------------------------------------
166// Reader side : acquire when using the ready queue to schedule but not
167//  creating/destroying queues
[e873838]168static inline void ready_schedule_lock(void) with(*__scheduler_lock) {
[8fc652e0]169        /* paranoid */ verify( ! __preemption_enabled() );
170        /* paranoid */ verify( kernelTLS().this_proc_id );
[e873838]171
[8fc652e0]172        unsigned iproc = kernelTLS().this_proc_id->id;
173        /*paranoid*/ verify(data[iproc].handle == kernelTLS().this_proc_id);
[7768b8d]174        /*paranoid*/ verify(iproc < ready);
175
176        // Step 1 : make sure no writer are in the middle of the critical section
177        while(__atomic_load_n(&lock, (int)__ATOMIC_RELAXED))
[fd9b524]178                Pause();
[7768b8d]179
180        // Fence needed because we don't want to start trying to acquire the lock
181        // before we read a false.
182        // Not needed on x86
183        // std::atomic_thread_fence(std::memory_order_seq_cst);
184
185        // Step 2 : acquire our local lock
186        __atomic_acquire( &data[iproc].lock );
187        /*paranoid*/ verify(data[iproc].lock);
[64a7146]188
189        #ifdef __CFA_WITH_VERIFY__
190                // Debug, check if this is owned for reading
191                data[iproc].owned = true;
192        #endif
[7768b8d]193}
194
[e873838]195static inline void ready_schedule_unlock(void) with(*__scheduler_lock) {
[8fc652e0]196        /* paranoid */ verify( ! __preemption_enabled() );
197        /* paranoid */ verify( kernelTLS().this_proc_id );
[e873838]198
[8fc652e0]199        unsigned iproc = kernelTLS().this_proc_id->id;
200        /*paranoid*/ verify(data[iproc].handle == kernelTLS().this_proc_id);
[7768b8d]201        /*paranoid*/ verify(iproc < ready);
202        /*paranoid*/ verify(data[iproc].lock);
[64a7146]203        /*paranoid*/ verify(data[iproc].owned);
204        #ifdef __CFA_WITH_VERIFY__
205                // Debug, check if this is owned for reading
206                data[iproc].owned = false;
207        #endif
[dca5802]208        __atomic_unlock(&data[iproc].lock);
[7768b8d]209}
210
[64a7146]211#ifdef __CFA_WITH_VERIFY__
[e873838]212        static inline bool ready_schedule_islocked(void) {
[8fc652e0]213                /* paranoid */ verify( ! __preemption_enabled() );
214                /*paranoid*/ verify( kernelTLS().this_proc_id );
215                __processor_id_t * proc = kernelTLS().this_proc_id;
[64a7146]216                return __scheduler_lock->data[proc->id].owned;
217        }
218
219        static inline bool ready_mutate_islocked() {
220                return __scheduler_lock->lock;
221        }
222#endif
223
[7768b8d]224//-----------------------------------------------------------------------
225// Writer side : acquire when changing the ready queue, e.g. adding more
226//  queues or removing them.
[b388ee81]227uint_fast32_t ready_mutate_lock( void );
[7768b8d]228
[b388ee81]229void ready_mutate_unlock( uint_fast32_t /* value returned by lock */ );
[7768b8d]230
[a33c113]231//-----------------------------------------------------------------------
232// Lock-Free registering/unregistering of threads
233// Register a processor to a given cluster and get its unique id in return
234// For convenience, also acquires the lock
235static inline uint_fast32_t ready_mutate_register( struct __processor_id_t * proc ) {
236        register_proc_id( proc );
237        return ready_mutate_lock();
238}
239
240// Unregister a processor from a given cluster using its id, getting back the original pointer
241// assumes the lock is acquired
242static inline void ready_mutate_unregister( struct __processor_id_t * proc, uint_fast32_t last_s ) {
243        ready_mutate_unlock( last_s );
244        unregister_proc_id( proc );
245}
246
[a7504db]247//-----------------------------------------------------------------------
248// Cluster idle lock/unlock
[6a9b12b]249static inline void lock(__cluster_proc_list & this) {
[a7504db]250        /* paranoid */ verify( ! __preemption_enabled() );
251
252        // Start by locking the global RWlock so that we know no-one is
253        // adding/removing processors while we mess with the idle lock
254        ready_schedule_lock();
255
256        // Simple counting lock, acquired, acquired by incrementing the counter
257        // to an odd number
258        for() {
259                uint64_t l = this.lock;
260                if(
261                        (0 == (l % 2))
262                        && __atomic_compare_exchange_n(&this.lock, &l, l + 1, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
263                ) return;
264                Pause();
265        }
266
267        /* paranoid */ verify( ! __preemption_enabled() );
268}
269
[6a9b12b]270static inline void unlock(__cluster_proc_list & this) {
[a7504db]271        /* paranoid */ verify( ! __preemption_enabled() );
272
273        /* paranoid */ verify( 1 == (this.lock % 2) );
274        // Simple couting lock, release by incrementing to an even number
275        __atomic_fetch_add( &this.lock, 1, __ATOMIC_SEQ_CST );
276
277        // Release the global lock, which we acquired when locking
278        ready_schedule_unlock();
279
280        /* paranoid */ verify( ! __preemption_enabled() );
281}
282
[b798713]283//=======================================================================
284// Ready-Queue API
[64a7146]285//-----------------------------------------------------------------------
286// pop thread from the ready queue of a cluster
287// returns 0p if empty
288__attribute__((hot)) bool query(struct cluster * cltr);
289
[dca5802]290//-----------------------------------------------------------------------
291// push thread onto a ready queue for a cluster
292// returns true if the list was previously empty, false otherwise
[504a7dc]293__attribute__((hot)) bool push(struct cluster * cltr, struct $thread * thrd);
[dca5802]294
295//-----------------------------------------------------------------------
296// pop thread from the ready queue of a cluster
297// returns 0p if empty
[1eb239e4]298// May return 0p spuriously
[504a7dc]299__attribute__((hot)) struct $thread * pop(struct cluster * cltr);
[dca5802]300
[1eb239e4]301//-----------------------------------------------------------------------
302// pop thread from the ready queue of a cluster
303// returns 0p if empty
304// guaranteed to find any threads added before this call
305__attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr);
306
[13c5e19]307//-----------------------------------------------------------------------
308// remove thread from the ready queue of a cluster
309// returns bool if it wasn't found
310bool remove_head(struct cluster * cltr, struct $thread * thrd);
311
[dca5802]312//-----------------------------------------------------------------------
313// Increase the width of the ready queue (number of lanes) by 4
[a017ee7]314void ready_queue_grow  (struct cluster * cltr);
[dca5802]315
316//-----------------------------------------------------------------------
317// Decrease the width of the ready queue (number of lanes) by 4
[a017ee7]318void ready_queue_shrink(struct cluster * cltr);
[b798713]319
[de94a60]320
[75f3522]321// Local Variables: //
322// mode: c //
323// tab-width: 4 //
[4aa2fb2]324// End: //
Note: See TracBrowser for help on using the repository browser.