source: libcfa/src/concurrency/kernel/private.hfa @ 5f6b2c2

ADTast-experimental
Last change on this file since 5f6b2c2 was 31c967b, checked in by Thierry Delisle <tdelisle@…>, 21 months ago

Changed ready-queue so I can easily change the averaging algorithm.
Changed averaging to use logscale.
  • Property mode set to 100644
File size: 13.1 KB
Line 
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//
7// kernel/private.hfa --
8//
9// Author           : Thierry Delisle
10// Created On       : Mon Feb 13 12:27:26 2017
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Wed Aug 12 08:21:33 2020
13// Update Count     : 9
14//
15
16#pragma once
17
18#if !defined(__cforall_thread__)
19        #error kernel/private.hfa should only be included in libcfathread source
20#endif
21
22#include "kernel.hfa"
23#include "thread.hfa"
24
25#include "alarm.hfa"
26#include "stats.hfa"
27
28extern "C" {
29#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
30        #include <rseq/rseq.h>
31#elif defined(CFA_HAVE_LINUX_RSEQ_H)
32        #include <linux/rseq.h>
33#else
34        #ifndef _GNU_SOURCE
35        #error kernel/private requires gnu_source
36        #endif
37        #include <sched.h>
38#endif
39}
40
41// Defines whether or not we *want* to use io_uring_enter as the idle_sleep blocking call
42// #define CFA_WANT_IO_URING_IDLE
43
44// Defines whether or not we *can* use io_uring_enter as the idle_sleep blocking call
45#if defined(CFA_WANT_IO_URING_IDLE) && defined(CFA_HAVE_LINUX_IO_URING_H)
46        #if defined(CFA_HAVE_IORING_OP_READ) || (defined(CFA_HAVE_READV) && defined(CFA_HAVE_IORING_OP_READV))
47                #define CFA_WITH_IO_URING_IDLE
48        #endif
49#endif
50
51// #define READYQ_USE_LINEAR_AVG
52#define READYQ_USE_LOGDBL_AVG
53// #define READYQ_USE_LOGINT_AVG
54
55#if   defined(READYQ_USE_LINEAR_AVG)
56typedef unsigned long long __readyQ_avg_t;
57#elif defined(READYQ_USE_LOGDBL_AVG)
58typedef double __readyQ_avg_t;
59#elif defined(READYQ_USE_LOGDBL_AVG)
60typedef unsigned long long __readyQ_avg_t;
61#else
62#error must pick a scheme for averaging
63#endif
64
65//-----------------------------------------------------------------------------
66// Scheduler
67union __attribute__((aligned(64))) __timestamp_t {
68        struct {
69                volatile unsigned long long tv;
70                volatile __readyQ_avg_t ma;
71        } t;
72        char __padding[192];
73};
74
75extern "C" {
76        void disable_interrupts() OPTIONAL_THREAD;
77        void enable_interrupts( bool poll = true );
78}
79
80void schedule_thread$( thread$ *, unpark_hint hint ) __attribute__((nonnull (1)));
81
82extern bool __preemption_enabled();
83
84enum {
85        PREEMPT_NORMAL    = 0,
86        PREEMPT_TERMINATE = 1,
87        PREEMPT_IO = 2,
88};
89
90static inline void __disable_interrupts_checked() {
91        /* paranoid */ verify( __preemption_enabled() );
92        disable_interrupts();
93        /* paranoid */ verify( ! __preemption_enabled() );
94}
95
96static inline void __enable_interrupts_checked( bool poll = true ) {
97        /* paranoid */ verify( ! __preemption_enabled() );
98        enable_interrupts( poll );
99        /* paranoid */ verify( __preemption_enabled() );
100}
101
102//release/wake-up the following resources
103void __thread_finish( thread$ * thrd );
104
105//-----------------------------------------------------------------------------
106// Hardware
107
108#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
109        // No data needed
110#elif defined(CFA_HAVE_LINUX_RSEQ_H)
111        extern "Cforall" {
112                extern __attribute__((aligned(64))) __thread volatile struct rseq __cfaabi_rseq;
113        }
114#else
115        // No data needed
116#endif
117
118static inline int __kernel_getcpu() {
119        /* paranoid */ verify( ! __preemption_enabled() );
120#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
121        return rseq_current_cpu();
122#elif defined(CFA_HAVE_LINUX_RSEQ_H)
123        int r = __cfaabi_rseq.cpu_id;
124        /* paranoid */ verify( r >= 0 );
125        return r;
126#else
127        return sched_getcpu();
128#endif
129}
130
131//-----------------------------------------------------------------------------
132// Processor
133void main(processorCtx_t &);
134static inline coroutine$* get_coroutine(processorCtx_t & this) { return &this.self; }
135
136void * __create_pthread( pthread_t *, void * (*)(void *), void * );
137void __destroy_pthread( pthread_t pthread, void * stack, void ** retval );
138
139extern cluster * mainCluster;
140
141//-----------------------------------------------------------------------------
142// Threads
143extern "C" {
144      void __cfactx_invoke_thread(void (*main)(void *), void * this);
145}
146
147__cfaabi_dbg_debug_do(
148        extern void __cfaabi_dbg_thread_register  ( thread$ * thrd );
149        extern void __cfaabi_dbg_thread_unregister( thread$ * thrd );
150)
151
152#define TICKET_BLOCKED (-1) // thread is blocked
153#define TICKET_RUNNING ( 0) // thread is running
154#define TICKET_UNBLOCK ( 1) // thread should ignore next block
155
156//-----------------------------------------------------------------------------
157// Utils
158void doregister( struct cluster * cltr, struct thread$ & thrd );
159void unregister( struct cluster * cltr, struct thread$ & thrd );
160
161//-----------------------------------------------------------------------------
162// I/O
163io_arbiter$ * create(void);
164void destroy(io_arbiter$ *);
165
166//=======================================================================
167// Cluster lock API
168//=======================================================================
169// Lock-Free registering/unregistering of threads
170// Register a processor to a given cluster and get its unique id in return
171unsigned register_proc_id( void );
172
173// Unregister a processor from a given cluster using its id, getting back the original pointer
174void unregister_proc_id( unsigned );
175
176//=======================================================================
177// Reader-writer lock implementation
178// Concurrent with doregister/unregister,
179//    i.e., threads can be added at any point during or between the entry/exit
180
181//-----------------------------------------------------------------------
182// simple spinlock underlying the RWLock
183// Blocking acquire
184static inline void __atomic_acquire(volatile bool * ll) {
185        /* paranoid */ verify( ! __preemption_enabled() );
186        /* paranoid */ verify(ll);
187
188        while( __builtin_expect(__atomic_exchange_n(ll, (bool)true, __ATOMIC_SEQ_CST), false) ) {
189                while(__atomic_load_n(ll, (int)__ATOMIC_RELAXED))
190                        Pause();
191        }
192        /* paranoid */ verify(*ll);
193        /* paranoid */ verify( ! __preemption_enabled() );
194}
195
196// Non-Blocking acquire
197static inline bool __atomic_try_acquire(volatile bool * ll) {
198        /* paranoid */ verify( ! __preemption_enabled() );
199        /* paranoid */ verify(ll);
200
201        return !__atomic_exchange_n(ll, (bool)true, __ATOMIC_SEQ_CST);
202}
203
204// Release
205static inline void __atomic_unlock(volatile bool * ll) {
206        /* paranoid */ verify( ! __preemption_enabled() );
207        /* paranoid */ verify(ll);
208        /* paranoid */ verify(*ll);
209        __atomic_store_n(ll, (bool)false, __ATOMIC_RELEASE);
210}
211
212//-----------------------------------------------------------------------
213// Reader-Writer lock protecting the ready-queues
214// while this lock is mostly generic some aspects
215// have been hard-coded to for the ready-queue for
216// simplicity and performance
217union __attribute__((aligned(64))) __scheduler_RWLock_t {
218        struct {
219                __attribute__((aligned(64))) char padding;
220
221                // total cachelines allocated
222                __attribute__((aligned(64))) unsigned int max;
223
224                // cachelines currently in use
225                volatile unsigned int alloc;
226
227                // cachelines ready to itereate over
228                // (!= to alloc when thread is in second half of doregister)
229                volatile unsigned int ready;
230
231                // writer lock
232                volatile bool write_lock;
233
234                // data pointer
235                volatile bool * volatile * data;
236        } lock;
237        char pad[192];
238};
239
240void  ?{}(__scheduler_RWLock_t & this);
241void ^?{}(__scheduler_RWLock_t & this);
242
243extern __scheduler_RWLock_t __scheduler_lock;
244
245//-----------------------------------------------------------------------
246// Reader side : acquire when using the ready queue to schedule but not
247//  creating/destroying queues
248static inline void ready_schedule_lock(void) with(__scheduler_lock.lock) {
249        /* paranoid */ verify( ! __preemption_enabled() );
250        /* paranoid */ verify( ! kernelTLS().in_sched_lock );
251        /* paranoid */ verify( data[kernelTLS().sched_id] == &kernelTLS().sched_lock );
252        /* paranoid */ verify( !kernelTLS().this_processor || kernelTLS().this_processor->unique_id == kernelTLS().sched_id );
253
254        // Step 1 : make sure no writer are in the middle of the critical section
255        while(__atomic_load_n(&write_lock, (int)__ATOMIC_RELAXED))
256                Pause();
257
258        // Fence needed because we don't want to start trying to acquire the lock
259        // before we read a false.
260        // Not needed on x86
261        // std::atomic_thread_fence(std::memory_order_seq_cst);
262
263        // Step 2 : acquire our local lock
264        __atomic_acquire( &kernelTLS().sched_lock );
265        /*paranoid*/ verify(kernelTLS().sched_lock);
266
267        #ifdef __CFA_WITH_VERIFY__
268                // Debug, check if this is owned for reading
269                kernelTLS().in_sched_lock = true;
270        #endif
271}
272
273static inline void ready_schedule_unlock(void) with(__scheduler_lock.lock) {
274        /* paranoid */ verify( ! __preemption_enabled() );
275        /* paranoid */ verify( data[kernelTLS().sched_id] == &kernelTLS().sched_lock );
276        /* paranoid */ verify( !kernelTLS().this_processor || kernelTLS().this_processor->unique_id == kernelTLS().sched_id );
277        /* paranoid */ verify( kernelTLS().sched_lock );
278        /* paranoid */ verify( kernelTLS().in_sched_lock );
279        #ifdef __CFA_WITH_VERIFY__
280                // Debug, check if this is owned for reading
281                kernelTLS().in_sched_lock = false;
282        #endif
283        __atomic_unlock(&kernelTLS().sched_lock);
284}
285
286#ifdef __CFA_WITH_VERIFY__
287        static inline bool ready_schedule_islocked(void) {
288                /* paranoid */ verify( ! __preemption_enabled() );
289                /* paranoid */ verify( (!kernelTLS().in_sched_lock) || kernelTLS().sched_lock );
290                return kernelTLS().sched_lock;
291        }
292
293        static inline bool ready_mutate_islocked() {
294                return __scheduler_lock.lock.write_lock;
295        }
296#endif
297
298//-----------------------------------------------------------------------
299// Writer side : acquire when changing the ready queue, e.g. adding more
300//  queues or removing them.
301uint_fast32_t ready_mutate_lock( void );
302
303void ready_mutate_unlock( uint_fast32_t /* value returned by lock */ );
304
305//-----------------------------------------------------------------------
306// Lock-Free registering/unregistering of threads
307// Register a processor to a given cluster and get its unique id in return
308// For convenience, also acquires the lock
309static inline [unsigned, uint_fast32_t] ready_mutate_register() {
310        unsigned id = register_proc_id();
311        uint_fast32_t last = ready_mutate_lock();
312        return [id, last];
313}
314
315// Unregister a processor from a given cluster using its id, getting back the original pointer
316// assumes the lock is acquired
317static inline void ready_mutate_unregister( unsigned id, uint_fast32_t last_s ) {
318        ready_mutate_unlock( last_s );
319        unregister_proc_id( id );
320}
321
322//-----------------------------------------------------------------------
323// Cluster idle lock/unlock
324static inline void lock(__cluster_proc_list & this) {
325        /* paranoid */ verify( ! __preemption_enabled() );
326
327        // Start by locking the global RWlock so that we know no-one is
328        // adding/removing processors while we mess with the idle lock
329        ready_schedule_lock();
330
331        lock( this.lock __cfaabi_dbg_ctx2 );
332
333        /* paranoid */ verify( ! __preemption_enabled() );
334}
335
336static inline bool try_lock(__cluster_proc_list & this) {
337        /* paranoid */ verify( ! __preemption_enabled() );
338
339        // Start by locking the global RWlock so that we know no-one is
340        // adding/removing processors while we mess with the idle lock
341        ready_schedule_lock();
342
343        if(try_lock( this.lock __cfaabi_dbg_ctx2 )) {
344                // success
345                /* paranoid */ verify( ! __preemption_enabled() );
346                return true;
347        }
348
349        // failed to lock
350        ready_schedule_unlock();
351
352        /* paranoid */ verify( ! __preemption_enabled() );
353        return false;
354}
355
356static inline void unlock(__cluster_proc_list & this) {
357        /* paranoid */ verify( ! __preemption_enabled() );
358
359        unlock(this.lock);
360
361        // Release the global lock, which we acquired when locking
362        ready_schedule_unlock();
363
364        /* paranoid */ verify( ! __preemption_enabled() );
365}
366
367//=======================================================================
368// Ready-Queue API
369//-----------------------------------------------------------------------
370// push thread onto a ready queue for a cluster
371// returns true if the list was previously empty, false otherwise
372__attribute__((hot)) void push(struct cluster * cltr, struct thread$ * thrd, unpark_hint hint);
373
374//-----------------------------------------------------------------------
375// pop thread from the local queues of a cluster
376// returns 0p if empty
377// May return 0p spuriously
378__attribute__((hot)) struct thread$ * pop_fast(struct cluster * cltr);
379
380//-----------------------------------------------------------------------
381// pop thread from any ready queue of a cluster
382// returns 0p if empty
383// May return 0p spuriously
384__attribute__((hot)) struct thread$ * pop_slow(struct cluster * cltr);
385
386//-----------------------------------------------------------------------
387// search all ready queues of a cluster for any thread
388// returns 0p if empty
389// guaranteed to find any threads added before this call
390__attribute__((hot)) struct thread$ * pop_search(struct cluster * cltr);
391
392//-----------------------------------------------------------------------
393// get preferred ready for new thread
394unsigned ready_queue_new_preferred();
395
396//-----------------------------------------------------------------------
397// Increase the width of the ready queue (number of lanes) by 4
398void ready_queue_grow  (struct cluster * cltr);
399
400//-----------------------------------------------------------------------
401// Decrease the width of the ready queue (number of lanes) by 4
402void ready_queue_shrink(struct cluster * cltr);
403
404//-----------------------------------------------------------------------
405// Decrease the width of the ready queue (number of lanes) by 4
406void ready_queue_close(struct cluster * cltr);
407
408// Local Variables: //
409// mode: c //
410// tab-width: 4 //
411// End: //
Note: See TracBrowser for help on using the repository browser.