source: libcfa/src/concurrency/kernel/fwd.hfa@ 34d194c

Last change on this file since 34d194c was 34d194c, checked in by Peter A. Buhr <pabuhr@…>, 4 days ago

move libcfa/src/concurrency/atomic.hfa to libcfa/src/bits/atomic.hfa, and update all the atomic operations
  • Property mode set to 100644
File size: 13.9 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2020 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/fwd.hfa -- PUBLIC
8// Fundamental code needed to implement threading M.E.S. algorithms.
9//
10// Author : Thierry Delisle
11// Created On : Thu Jul 30 16:46:41 2020
12// Last Modified By :
13// Last Modified On :
14// Update Count :
15//
16
17#pragma once
18
19#include "bits/defs.hfa"
20#include "bits/debug.hfa"
21#include "bits/atomic.hfa" // Pause
22
23#ifdef __cforall
24#include "bits/random.hfa"
25#endif
26
27struct thread$;
28struct processor;
29struct cluster;
30
31enum __Preemption_Reason { __NO_PREEMPTION, __ALARM_PREEMPTION, __POLL_PREEMPTION, __MANUAL_PREEMPTION };
32
33#define KERNEL_STORAGE(T,X) __attribute((aligned(__alignof__(T)))) static char storage_##X[sizeof(T)]
34
35#ifdef __cforall
36extern "C" {
37 extern "Cforall" {
38 extern __attribute__((aligned(64))) __thread struct KernelThreadData {
39 struct thread$ * volatile this_thread;
40 struct processor * volatile this_processor;
41 volatile bool sched_lock;
42
43 struct {
44 volatile unsigned short disable_count;
45 volatile bool enabled;
46 volatile bool in_progress;
47 } preemption_state;
48
49 PRNG_STATE_T random_state;
50
51 struct {
52 uint64_t fwd_seed;
53 uint64_t bck_seed;
54 } ready_rng;
55
56 struct __stats_t * volatile this_stats;
57
58 #ifdef __CFA_WITH_VERIFY__
59 // Debug, check if the rwlock is owned for reading
60 bool in_sched_lock;
61 unsigned sched_id;
62 #endif
63 } __cfaabi_tls __attribute__ ((tls_model ( "initial-exec" )));
64
65 extern bool __preemption_enabled();
66
67 static inline KernelThreadData & kernelTLS( void ) {
68 /* paranoid */ verify( ! __preemption_enabled() );
69 return __cfaabi_tls;
70 }
71
72 extern uintptr_t __cfatls_get( unsigned long int member );
73 #define publicTLS_get( member ) ((typeof(__cfaabi_tls.member))__cfatls_get( __builtin_offsetof(KernelThreadData, member) ))
74
75 static inline
76 #ifdef __x86_64__ // 64-bit architecture
77 uint64_t
78 #else // 32-bit architecture
79 uint32_t
80 #endif // __x86_64__
81 __tls_rand() {
82 return PRNG_NAME( kernelTLS().random_state );
83 }
84
85 static inline unsigned __tls_rand_fwd() {
86 return LCGBI_fwd( kernelTLS().ready_rng.fwd_seed );
87 }
88
89 static inline unsigned __tls_rand_bck() {
90 return LCGBI_bck( kernelTLS().ready_rng.bck_seed );
91 }
92
93 static inline void __tls_rand_advance_bck(void) {
94 kernelTLS().ready_rng.bck_seed = kernelTLS().ready_rng.fwd_seed;
95 }
96 }
97
98 extern void disable_interrupts();
99 extern void enable_interrupts( bool poll = false );
100
101 extern "Cforall" {
102 enum unpark_hint { UNPARK_LOCAL, UNPARK_REMOTE };
103
104 extern void park( void );
105 extern void unpark( struct thread$ *, unpark_hint );
106 static inline void unpark( struct thread$ * thrd ) { unpark(thrd, UNPARK_LOCAL); }
107 static inline struct thread$ * active_thread () {
108 struct thread$ * t = publicTLS_get( this_thread );
109 /* paranoid */ verify( t );
110 return t;
111 }
112
113 extern bool force_yield( enum __Preemption_Reason );
114
115 static inline void yield() {
116 force_yield(__MANUAL_PREEMPTION);
117 }
118
119 // Yield: yield N times
120 static inline void yield( size_t times ) {
121 for ( times ) {
122 yield();
123 }
124 }
125
126 // Semaphore which only supports a single thread
127 struct single_sem {
128 struct thread$ * volatile ptr;
129 };
130
131 static inline {
132 void ?{}(single_sem & this) {
133 this.ptr = 0p;
134 }
135
136 void ^?{}(single_sem &) {}
137
138 bool wait(single_sem & this) {
139 for () {
140 struct thread$ * expected = this.ptr;
141 if (expected == 1p) {
142 if (__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
143 return false;
144 }
145 }
146 else {
147 /* paranoid */ verify( expected == 0p );
148 if (__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
149 park();
150 return true;
151 }
152 }
153
154 }
155 }
156
157 bool post(single_sem & this) {
158 for () {
159 struct thread$ * expected = this.ptr;
160 if (expected == 1p) return false;
161 if (expected == 0p) {
162 if (__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
163 return false;
164 }
165 }
166 else {
167 if (__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
168 unpark( expected );
169 return true;
170 }
171 }
172 }
173 }
174 }
175
176 // Synchronozation primitive which only supports a single thread and one post
177 // Similar to a binary semaphore with a 'one shot' semantic
178 // is expected to be discarded after each party call their side
179 enum(struct thread$ *) { oneshot_ARMED = 0p, oneshot_FULFILLED = 1p };
180 struct oneshot {
181 // Internal state :
182 // armed : initial state, wait will block
183 // fulfilled : wait won't block
184 // any thread : a thread is currently waiting
185 struct thread$ * volatile ptr;
186 };
187
188 static inline {
189 void ?{}(oneshot & this) {
190 this.ptr = oneshot_ARMED;
191 }
192
193 void ^?{}(oneshot &) {}
194
195 // Wait for the post, return immidiately if it already happened.
196 // return true if the thread was parked
197 bool wait(oneshot & this) {
198 for () {
199 struct thread$ * expected = this.ptr;
200 if (expected == oneshot_FULFILLED) return false;
201 if (__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
202 park();
203 /* paranoid */ verify( this.ptr == oneshot_FULFILLED );
204 return true;
205 }
206 }
207 }
208
209 // Mark as fulfilled, wake thread if needed
210 // return true if a thread was unparked
211 thread$ * post(oneshot & this, bool do_unpark = true) {
212 struct thread$ * got = __atomic_exchange_n( &this.ptr, oneshot_FULFILLED, __ATOMIC_SEQ_CST);
213 if ( got == oneshot_ARMED || got == oneshot_FULFILLED ) return 0p;
214 if (do_unpark) unpark( got );
215 return got;
216 }
217 }
218
219 // base types for future to build upon
220 // It is based on the 'oneshot' type to allow multiple futures
221 // to block on the same instance, permitting users to block a single
222 // thread on "any of" [a given set of] futures.
223 // does not support multiple threads waiting on the same future
224 enum(struct oneshot *) { future_ARMED = 0p, future_FULFILLED = 1p, future_PROGRESS = 2p, future_ABANDONED = 3p };
225 struct future_t {
226 // Internal state :
227 // armed : initial state, wait will block
228 // fulfilled : result is ready, wait won't block
229 // progress : someone else is in the process of fulfilling this
230 // abandoned : client no longer cares, server should delete
231 // any oneshot : a context has been setup to wait, a thread could wait on it
232 struct oneshot * volatile ptr;
233 };
234
235 static inline {
236 void ?{}(future_t & this) {
237 this.ptr = future_ARMED;
238 }
239
240 void ^?{}(future_t &) {}
241
242 void reset(future_t & this) {
243 // needs to be in 0p or 1p
244 __atomic_exchange_n( &this.ptr, future_ARMED, __ATOMIC_SEQ_CST);
245 }
246
247 // check if the future is available
248 bool available( future_t & this ) {
249 while( this.ptr == future_PROGRESS ) Pause();
250 return this.ptr == future_FULFILLED;
251 }
252
253 // Prepare the future to be waited on
254 // intented to be use by wait, wait_any, waitfor, etc. rather than used directly
255 bool setup( future_t & this, oneshot & wait_ctx ) {
256 /* paranoid */ verify( wait_ctx.ptr == oneshot_ARMED || wait_ctx.ptr == oneshot_FULFILLED );
257 // The future needs to set the wait context
258 for () {
259 struct oneshot * expected = this.ptr;
260 // Is the future already fulfilled?
261 if (expected == future_FULFILLED) return false; // Yes, just return false (didn't block)
262
263 // The future is not fulfilled, try to setup the wait context
264 if (__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
265 return true;
266 }
267 }
268 }
269
270 // Stop waiting on a future
271 // When multiple futures are waited for together in "any of" pattern
272 // futures that weren't fulfilled before the thread woke up
273 // should retract the wait ctx
274 // intented to be use by wait, wait_any, waitfor, etc. rather than used directly
275 bool retract( future_t & this, oneshot & wait_ctx ) {
276 struct oneshot * expected = &wait_ctx;
277
278 // attempt to remove the context so it doesn't get consumed.
279 if (__atomic_compare_exchange_n( &this.ptr, &expected, future_ARMED, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
280 // we still have the original context, then no one else saw it
281 return false;
282 }
283
284 // expected == ARMED: future was never actually setup, just return
285 if ( expected == future_ARMED ) return false;
286
287 // expected == FULFILLED: the future is ready and the context was fully consumed
288 // the server won't use the pointer again
289 // It is safe to delete (which could happen after the return)
290 if ( expected == future_FULFILLED ) return true;
291
292 // expected == PROGRESS: the future is ready but the context hasn't fully been consumed
293 // spin until it is safe to move on
294 if ( expected == future_PROGRESS ) {
295 while( this.ptr != future_FULFILLED ) Pause();
296 /* paranoid */ verify( this.ptr == future_FULFILLED );
297 return true;
298 }
299
300 // anything else: the future was setup with a different context ?!?!
301 // something went wrong here, abort
302 abort("Future in unexpected state");
303 }
304
305 // Mark the future as abandoned, meaning it will be deleted by the server
306 bool abandon( future_t & this ) {
307 /* paranoid */ verify( this.ptr != future_ABANDONED );
308
309 // Mark the future as abandonned
310 struct oneshot * got = __atomic_exchange_n( &this.ptr, future_ABANDONED, __ATOMIC_SEQ_CST);
311
312 // If the future isn't already fulfilled, let the server delete it
313 if ( got == future_ARMED ) return false;
314
315 // got == PROGRESS: the future is ready but the context hasn't fully been consumed
316 // spin until it is safe to move on
317 if ( got == future_PROGRESS ) {
318 while( this.ptr != future_FULFILLED ) Pause();
319 got = future_FULFILLED;
320 }
321
322 // The future is completed delete it now
323 /* paranoid */ verify( this.ptr != future_FULFILLED );
324 free( &this );
325 return true;
326 }
327
328 // from the server side, mark the future as fulfilled
329 // delete it if needed
330
331 thread$ * fulfil( future_t & this, bool do_unpark = true ) {
332 for () {
333 struct oneshot * expected = this.ptr;
334
335 #if defined(__GNUC__) && __GNUC__ >= 7
336 // SKULLDUGGERY: gcc bug does not handle push/pop for -Wfree-nonheap-object
337 //#pragma GCC diagnostic push
338 #pragma GCC diagnostic ignored "-Wfree-nonheap-object"
339 #endif
340
341 if ( expected == future_ABANDONED ) { free( &this ); return 0p; }
342
343 #if defined(__GNUC__) && __GNUC__ >= 7
344 //#pragma GCC diagnostic pop
345 #endif
346
347 /* paranoid */ verify( expected != future_FULFILLED ); // Future is already fulfilled, should not happen
348 /* paranoid */ verify( expected != future_PROGRESS ); // Future is bein fulfilled by someone else, this is even less supported then the previous case.
349
350 // If there is a wait context, we need to consume it and mark it as consumed after
351 // If there is no context then we can skip the in progress phase
352 struct oneshot * want = expected == future_ARMED ? future_FULFILLED : future_PROGRESS;
353 if (__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
354 if ( expected == future_ARMED ) { return 0p; }
355 thread$ * ret = post( *expected, do_unpark );
356 __atomic_store_n( &this.ptr, future_FULFILLED, __ATOMIC_SEQ_CST);
357 return ret;
358 }
359 }
360
361 }
362
363 // Wait for the future to be fulfilled
364 bool wait( future_t & this ) {
365 oneshot temp;
366 if ( !setup(this, temp) ) return false;
367
368 // Wait context is setup, just wait on it
369 bool ret = wait( temp );
370
371 // Wait for the future to tru
372 while( this.ptr == future_PROGRESS ) Pause();
373 // Make sure the state makes sense
374 // Should be fulfilled, could be in progress but it's out of date if so
375 // since if that is the case, the oneshot was fulfilled (unparking this thread)
376 // and the oneshot should not be needed any more
377 struct oneshot * was __attribute__((unused)) = this.ptr; // used in option verify
378 /* paranoid */ verifyf( was == future_FULFILLED, "Expected this.ptr to be 1p, was %p\n", was );
379
380 // Mark the future as fulfilled, to be consistent
381 // with potential calls to avail
382 // this.ptr = 1p;
383 return ret;
384 }
385
386 // Wait for any future to be fulfilled
387 forall(T& | sized(T) | { bool setup( T&, oneshot & ); bool retract( T&, oneshot & ); })
388 T & wait_any( T * futures, size_t num_futures ) {
389 oneshot temp;
390
391 // setup all futures
392 // if any are already satisfied return
393 for ( i; num_futures ) {
394 if ( !setup(futures[i], temp) ) return futures[i];
395 }
396
397 // Wait context is setup, just wait on it
398 wait( temp );
399
400 size_t ret;
401 // attempt to retract all futures
402 for ( i; num_futures ) {
403 if ( retract( futures[i], temp ) ) ret = i;
404 }
405
406 return futures[ret];
407 }
408 }
409
410 //-----------------------------------------------------------------------
411 // Statics call at the end of each thread to register statistics
412 #if !defined(__CFA_NO_STATISTICS__)
413 static inline struct __stats_t * __tls_stats() {
414 /* paranoid */ verify( ! __preemption_enabled() );
415 /* paranoid */ verify( kernelTLS().this_stats );
416 return kernelTLS().this_stats;
417 }
418
419 #define __STATS__(in_kernel, ...) { \
420 if ( !(in_kernel) ) disable_interrupts(); \
421 with ( *__tls_stats() ) { \
422 __VA_ARGS__ \
423 } \
424 if ( !(in_kernel) ) enable_interrupts(); \
425 }
426 #if defined(CFA_HAVE_LINUX_IO_URING_H)
427 #define __IO_STATS__(in_kernel, ...) { \
428 if ( !(in_kernel) ) disable_interrupts(); \
429 with ( *__tls_stats() ) { \
430 __VA_ARGS__ \
431 } \
432 if ( !(in_kernel) ) enable_interrupts(); \
433 }
434 #else
435 #define __IO_STATS__(in_kernel, ...)
436 #endif
437 #else
438 #define __STATS__(in_kernel, ...)
439 #define __IO_STATS__(in_kernel, ...)
440 #endif
441 }
442}
443#endif // #endif
Note: See TracBrowser for help on using the repository browser.