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

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since c993b15 was c993b15, checked in by Thierry Delisle <tdelisle@…>, 7 months ago

Changed RW lock to avoid hitting the global array on schedule.

  • Property mode set to 100644
File size: 9.7 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#include "kernel.hfa"
19#include "thread.hfa"
20
21#include "alarm.hfa"
22#include "stats.hfa"
23
24//-----------------------------------------------------------------------------
25// Scheduler
26
27
28extern "C" {
29        void disable_interrupts() OPTIONAL_THREAD;
30        void enable_interrupts( bool poll = true );
31}
32
33void schedule_thread$( $thread * ) __attribute__((nonnull (1)));
34
35extern bool __preemption_enabled();
36
37//release/wake-up the following resources
38void __thread_finish( $thread * thrd );
39
40//-----------------------------------------------------------------------------
41// Processor
42void main(processorCtx_t *);
43
44void * __create_pthread( pthread_t *, void * (*)(void *), void * );
45void __destroy_pthread( pthread_t pthread, void * stack, void ** retval );
46
47
48
49extern cluster * mainCluster;
50
51//-----------------------------------------------------------------------------
52// Threads
53extern "C" {
54      void __cfactx_invoke_thread(void (*main)(void *), void * this);
55}
56
57__cfaabi_dbg_debug_do(
58        extern void __cfaabi_dbg_thread_register  ( $thread * thrd );
59        extern void __cfaabi_dbg_thread_unregister( $thread * thrd );
60)
61
62#define TICKET_BLOCKED (-1) // thread is blocked
63#define TICKET_RUNNING ( 0) // thread is running
64#define TICKET_UNBLOCK ( 1) // thread should ignore next block
65
66//-----------------------------------------------------------------------------
67// Utils
68void doregister( struct cluster * cltr, struct $thread & thrd );
69void unregister( struct cluster * cltr, struct $thread & thrd );
70
71//-----------------------------------------------------------------------------
72// I/O
73$io_arbiter * create(void);
74void destroy($io_arbiter *);
75
76//=======================================================================
77// Cluster lock API
78//=======================================================================
79// Lock-Free registering/unregistering of threads
80// Register a processor to a given cluster and get its unique id in return
81unsigned register_proc_id( void );
82
83// Unregister a processor from a given cluster using its id, getting back the original pointer
84void unregister_proc_id( unsigned );
85
86//=======================================================================
87// Reader-writer lock implementation
88// Concurrent with doregister/unregister,
89//    i.e., threads can be added at any point during or between the entry/exit
90
91//-----------------------------------------------------------------------
92// simple spinlock underlying the RWLock
93// Blocking acquire
94static inline void __atomic_acquire(volatile bool * ll) {
95        while( __builtin_expect(__atomic_exchange_n(ll, (bool)true, __ATOMIC_SEQ_CST), false) ) {
96                while(__atomic_load_n(ll, (int)__ATOMIC_RELAXED))
97                        Pause();
98        }
99        /* paranoid */ verify(*ll);
100}
101
102// Non-Blocking acquire
103static inline bool __atomic_try_acquire(volatile bool * ll) {
104        return !__atomic_exchange_n(ll, (bool)true, __ATOMIC_SEQ_CST);
105}
106
107// Release
108static inline void __atomic_unlock(volatile bool * ll) {
109        /* paranoid */ verify(*ll);
110        __atomic_store_n(ll, (bool)false, __ATOMIC_RELEASE);
111}
112
113
114
115
116
117//-----------------------------------------------------------------------
118// Reader-Writer lock protecting the ready-queues
119// while this lock is mostly generic some aspects
120// have been hard-coded to for the ready-queue for
121// simplicity and performance
122struct __scheduler_RWLock_t {
123        // total cachelines allocated
124        unsigned int max;
125
126        // cachelines currently in use
127        volatile unsigned int alloc;
128
129        // cachelines ready to itereate over
130        // (!= to alloc when thread is in second half of doregister)
131        volatile unsigned int ready;
132
133        // writer lock
134        volatile bool write_lock;
135
136        // data pointer
137        volatile bool * volatile * data;
138};
139
140void  ?{}(__scheduler_RWLock_t & this);
141void ^?{}(__scheduler_RWLock_t & this);
142
143extern __scheduler_RWLock_t * __scheduler_lock;
144
145//-----------------------------------------------------------------------
146// Reader side : acquire when using the ready queue to schedule but not
147//  creating/destroying queues
148static inline void ready_schedule_lock(void) with(*__scheduler_lock) {
149        /* paranoid */ verify( ! __preemption_enabled() );
150        /* paranoid */ verify( ! kernelTLS().in_sched_lock );
151        /* paranoid */ verify( data[kernelTLS().sched_id] == &kernelTLS().sched_lock );
152        /* paranoid */ verify( !kernelTLS().this_processor || kernelTLS().this_processor->unique_id == kernelTLS().sched_id );
153
154        // Step 1 : make sure no writer are in the middle of the critical section
155        while(__atomic_load_n(&write_lock, (int)__ATOMIC_RELAXED))
156                Pause();
157
158        // Fence needed because we don't want to start trying to acquire the lock
159        // before we read a false.
160        // Not needed on x86
161        // std::atomic_thread_fence(std::memory_order_seq_cst);
162
163        // Step 2 : acquire our local lock
164        __atomic_acquire( &kernelTLS().sched_lock );
165        /*paranoid*/ verify(kernelTLS().sched_lock);
166
167        #ifdef __CFA_WITH_VERIFY__
168                // Debug, check if this is owned for reading
169                kernelTLS().in_sched_lock = true;
170        #endif
171}
172
173static inline void ready_schedule_unlock(void) with(*__scheduler_lock) {
174        /* paranoid */ verify( ! __preemption_enabled() );
175        /* paranoid */ verify( data[kernelTLS().sched_id] == &kernelTLS().sched_lock );
176        /* paranoid */ verify( !kernelTLS().this_processor || kernelTLS().this_processor->unique_id == kernelTLS().sched_id );
177        /* paranoid */ verify( kernelTLS().sched_lock );
178        /* paranoid */ verify( kernelTLS().in_sched_lock );
179        #ifdef __CFA_WITH_VERIFY__
180                // Debug, check if this is owned for reading
181                kernelTLS().in_sched_lock = false;
182        #endif
183        __atomic_unlock(&kernelTLS().sched_lock);
184}
185
186#ifdef __CFA_WITH_VERIFY__
187        static inline bool ready_schedule_islocked(void) {
188                /* paranoid */ verify( ! __preemption_enabled() );
189                /* paranoid */ verify( (!kernelTLS().in_sched_lock) || kernelTLS().sched_lock );
190                return kernelTLS().sched_lock;
191        }
192
193        static inline bool ready_mutate_islocked() {
194                return __scheduler_lock->write_lock;
195        }
196#endif
197
198//-----------------------------------------------------------------------
199// Writer side : acquire when changing the ready queue, e.g. adding more
200//  queues or removing them.
201uint_fast32_t ready_mutate_lock( void );
202
203void ready_mutate_unlock( uint_fast32_t /* value returned by lock */ );
204
205//-----------------------------------------------------------------------
206// Lock-Free registering/unregistering of threads
207// Register a processor to a given cluster and get its unique id in return
208// For convenience, also acquires the lock
209static inline [unsigned, uint_fast32_t] ready_mutate_register() {
210        unsigned id = register_proc_id();
211        uint_fast32_t last = ready_mutate_lock();
212        return [id, last];
213}
214
215// Unregister a processor from a given cluster using its id, getting back the original pointer
216// assumes the lock is acquired
217static inline void ready_mutate_unregister( unsigned id, uint_fast32_t last_s ) {
218        ready_mutate_unlock( last_s );
219        unregister_proc_id( id );
220}
221
222//-----------------------------------------------------------------------
223// Cluster idle lock/unlock
224static inline void lock(__cluster_proc_list & this) {
225        /* paranoid */ verify( ! __preemption_enabled() );
226
227        // Start by locking the global RWlock so that we know no-one is
228        // adding/removing processors while we mess with the idle lock
229        ready_schedule_lock();
230
231        // Simple counting lock, acquired, acquired by incrementing the counter
232        // to an odd number
233        for() {
234                uint64_t l = this.lock;
235                if(
236                        (0 == (l % 2))
237                        && __atomic_compare_exchange_n(&this.lock, &l, l + 1, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
238                ) return;
239                Pause();
240        }
241
242        /* paranoid */ verify( ! __preemption_enabled() );
243}
244
245static inline void unlock(__cluster_proc_list & this) {
246        /* paranoid */ verify( ! __preemption_enabled() );
247
248        /* paranoid */ verify( 1 == (this.lock % 2) );
249        // Simple couting lock, release by incrementing to an even number
250        __atomic_fetch_add( &this.lock, 1, __ATOMIC_SEQ_CST );
251
252        // Release the global lock, which we acquired when locking
253        ready_schedule_unlock();
254
255        /* paranoid */ verify( ! __preemption_enabled() );
256}
257
258//=======================================================================
259// Ready-Queue API
260//-----------------------------------------------------------------------
261// push thread onto a ready queue for a cluster
262// returns true if the list was previously empty, false otherwise
263__attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd);
264
265//-----------------------------------------------------------------------
266// pop thread from the local queues of a cluster
267// returns 0p if empty
268// May return 0p spuriously
269__attribute__((hot)) struct $thread * pop_fast(struct cluster * cltr);
270
271//-----------------------------------------------------------------------
272// pop thread from any ready queue of a cluster
273// returns 0p if empty
274// May return 0p spuriously
275__attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr);
276
277//-----------------------------------------------------------------------
278// search all ready queues of a cluster for any thread
279// returns 0p if empty
280// guaranteed to find any threads added before this call
281__attribute__((hot)) struct $thread * pop_search(struct cluster * cltr);
282
283//-----------------------------------------------------------------------
284// Increase the width of the ready queue (number of lanes) by 4
285void ready_queue_grow  (struct cluster * cltr);
286
287//-----------------------------------------------------------------------
288// Decrease the width of the ready queue (number of lanes) by 4
289void ready_queue_shrink(struct cluster * cltr);
290
291
292// Local Variables: //
293// mode: c //
294// tab-width: 4 //
295// End: //
Note: See TracBrowser for help on using the repository browser.