source: libcfa/src/concurrency/kernel/fwd.hfa@ cd3fc46

ADT ast-experimental pthread-emulation
Last change on this file since cd3fc46 was 2af1943, checked in by Thierry Delisle <tdelisle@…>, 3 years ago

Small improvements to some of the alignment requirements in CFA runtime.
  • Property mode set to 100644
File size: 13.1 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
22#ifdef __cforall
23#include "bits/random.hfa"
24#endif
25
26struct thread$;
27struct processor;
28struct cluster;
29
30enum __Preemption_Reason { __NO_PREEMPTION, __ALARM_PREEMPTION, __POLL_PREEMPTION, __MANUAL_PREEMPTION };
31
32#define KERNEL_STORAGE(T,X) __attribute((aligned(__alignof__(T)))) static char storage_##X[sizeof(T)]
33
34#ifdef __cforall
35extern "C" {
36 extern "Cforall" {
37 extern __attribute__((aligned(64))) thread_local struct KernelThreadData {
38 struct thread$ * volatile this_thread;
39 struct processor * volatile this_processor;
40 volatile bool sched_lock;
41
42 struct {
43 volatile unsigned short disable_count;
44 volatile bool enabled;
45 volatile bool in_progress;
46 } preemption_state;
47
48 #if defined(__SIZEOF_INT128__)
49 __uint128_t rand_seed;
50 #else
51 uint64_t rand_seed;
52 #endif
53 struct {
54 uint64_t fwd_seed;
55 uint64_t bck_seed;
56 } ready_rng;
57
58 struct __stats_t * volatile this_stats;
59
60
61 #ifdef __CFA_WITH_VERIFY__
62 // Debug, check if the rwlock is owned for reading
63 bool in_sched_lock;
64 unsigned sched_id;
65 #endif
66 } __cfaabi_tls __attribute__ ((tls_model ( "initial-exec" )));
67
68 extern bool __preemption_enabled();
69
70 static inline KernelThreadData & kernelTLS( void ) {
71 /* paranoid */ verify( ! __preemption_enabled() );
72 return __cfaabi_tls;
73 }
74
75 extern uintptr_t __cfatls_get( unsigned long int member );
76 #define publicTLS_get( member ) ((typeof(__cfaabi_tls.member))__cfatls_get( __builtin_offsetof(KernelThreadData, member) ))
77
78 static inline uint64_t __tls_rand() {
79 return
80 #if defined(__SIZEOF_INT128__)
81 lehmer64( kernelTLS().rand_seed );
82 #else
83 xorshift_13_7_17( kernelTLS().rand_seed );
84 #endif
85 }
86
87 static inline unsigned __tls_rand_fwd() {
88 return LCGBI_fwd( kernelTLS().ready_rng.fwd_seed );
89 }
90
91 static inline unsigned __tls_rand_bck() {
92 return LCGBI_bck( kernelTLS().ready_rng.bck_seed );
93 }
94
95 static inline void __tls_rand_advance_bck(void) {
96 kernelTLS().ready_rng.bck_seed = kernelTLS().ready_rng.fwd_seed;
97 }
98 }
99
100 extern void disable_interrupts();
101 extern void enable_interrupts( bool poll = false );
102
103 extern "Cforall" {
104 enum unpark_hint { UNPARK_LOCAL, UNPARK_REMOTE };
105
106 extern void park( void );
107 extern void unpark( struct thread$ *, unpark_hint );
108 static inline void unpark( struct thread$ * thrd ) { unpark(thrd, UNPARK_LOCAL); }
109 static inline struct thread$ * active_thread () {
110 struct thread$ * t = publicTLS_get( this_thread );
111 /* paranoid */ verify( t );
112 return t;
113 }
114
115 extern bool force_yield( enum __Preemption_Reason );
116
117 static inline void yield() {
118 force_yield(__MANUAL_PREEMPTION);
119 }
120
121 // Yield: yield N times
122 static inline void yield( unsigned times ) {
123 for( times ) {
124 yield();
125 }
126 }
127
128 // Semaphore which only supports a single thread
129 struct single_sem {
130 struct thread$ * volatile ptr;
131 };
132
133 static inline {
134 void ?{}(single_sem & this) {
135 this.ptr = 0p;
136 }
137
138 void ^?{}(single_sem &) {}
139
140 bool wait(single_sem & this) {
141 for() {
142 struct thread$ * expected = this.ptr;
143 if(expected == 1p) {
144 if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
145 return false;
146 }
147 }
148 else {
149 /* paranoid */ verify( expected == 0p );
150 if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
151 park();
152 return true;
153 }
154 }
155
156 }
157 }
158
159 bool post(single_sem & this) {
160 for() {
161 struct thread$ * expected = this.ptr;
162 if(expected == 1p) return false;
163 if(expected == 0p) {
164 if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
165 return false;
166 }
167 }
168 else {
169 if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
170 unpark( expected );
171 return true;
172 }
173 }
174 }
175 }
176 }
177
178 // Synchronozation primitive which only supports a single thread and one post
179 // Similar to a binary semaphore with a 'one shot' semantic
180 // is expected to be discarded after each party call their side
181 struct oneshot {
182 // Internal state :
183 // 0p : is initial state (wait will block)
184 // 1p : fulfilled (wait won't block)
185 // any thread : a thread is currently waiting
186 struct thread$ * volatile ptr;
187 };
188
189 static inline {
190 void ?{}(oneshot & this) {
191 this.ptr = 0p;
192 }
193
194 void ^?{}(oneshot &) {}
195
196 // Wait for the post, return immidiately if it already happened.
197 // return true if the thread was parked
198 bool wait(oneshot & this) {
199 for() {
200 struct thread$ * expected = this.ptr;
201 if(expected == 1p) return false;
202 if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
203 park();
204 /* paranoid */ verify( this.ptr == 1p );
205 return true;
206 }
207 }
208 }
209
210 // Mark as fulfilled, wake thread if needed
211 // return true if a thread was unparked
212 thread$ * post(oneshot & this, bool do_unpark = true) {
213 struct thread$ * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
214 if( got == 0p || got == 1p ) return 0p;
215 if(do_unpark) unpark( got );
216 return got;
217 }
218 }
219
220 // base types for future to build upon
221 // It is based on the 'oneshot' type to allow multiple futures
222 // to block on the same instance, permitting users to block a single
223 // thread on "any of" [a given set of] futures.
224 // does not support multiple threads waiting on the same future
225 struct future_t {
226 // Internal state :
227 // 0p : is initial state (wait will block)
228 // 1p : fulfilled (wait won't block)
229 // 2p : in progress ()
230 // 3p : abandoned, 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 = 0p;
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, 0p, __ATOMIC_SEQ_CST);
245 }
246
247 // check if the future is available
248 bool available( future_t & this ) {
249 while( this.ptr == 2p ) Pause();
250 return this.ptr == 1p;
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 == 0p || wait_ctx.ptr == 1p );
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 == 1p) 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 = this.ptr;
277
278 // attempt to remove the context so it doesn't get consumed.
279 if(__atomic_compare_exchange_n( &this.ptr, &expected, 0p, 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 == 0p: future was never actually setup, just return
285 if( expected == 0p ) return false;
286
287 // expected == 1p: 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 == 1p ) return true;
291
292 // expected == 2p: the future is ready but the context hasn't fully been consumed
293 // spin until it is safe to move on
294 if( expected == 2p ) {
295 while( this.ptr != 1p ) Pause();
296 /* paranoid */ verify( this.ptr == 1p );
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 != 3p );
308
309 // Mark the future as abandonned
310 struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST);
311
312 // If the future isn't already fulfilled, let the server delete it
313 if( got == 0p ) return false;
314
315 // got == 2p: the future is ready but the context hasn't fully been consumed
316 // spin until it is safe to move on
317 if( got == 2p ) {
318 while( this.ptr != 1p ) Pause();
319 got = 1p;
320 }
321
322 // The future is completed delete it now
323 /* paranoid */ verify( this.ptr != 1p );
324 free( &this );
325 return true;
326 }
327
328 // from the server side, mark the future as fulfilled
329 // delete it if needed
330 thread$ * fulfil( future_t & this, bool do_unpark = true ) {
331 for() {
332 struct oneshot * expected = this.ptr;
333 // was this abandoned?
334 #if defined(__GNUC__) && __GNUC__ >= 7
335 #pragma GCC diagnostic push
336 #pragma GCC diagnostic ignored "-Wfree-nonheap-object"
337 #endif
338 if( expected == 3p ) { free( &this ); return 0p; }
339 #if defined(__GNUC__) && __GNUC__ >= 7
340 #pragma GCC diagnostic pop
341 #endif
342
343 /* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen
344 /* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case.
345
346 // If there is a wait context, we need to consume it and mark it as consumed after
347 // If there is no context then we can skip the in progress phase
348 struct oneshot * want = expected == 0p ? 1p : 2p;
349 if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
350 if( expected == 0p ) { return 0p; }
351 thread$ * ret = post( *expected, do_unpark );
352 __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
353 return ret;
354 }
355 }
356
357 }
358
359 // Wait for the future to be fulfilled
360 bool wait( future_t & this ) {
361 oneshot temp;
362 if( !setup(this, temp) ) return false;
363
364 // Wait context is setup, just wait on it
365 bool ret = wait( temp );
366
367 // Wait for the future to tru
368 while( this.ptr == 2p ) Pause();
369 // Make sure the state makes sense
370 // Should be fulfilled, could be in progress but it's out of date if so
371 // since if that is the case, the oneshot was fulfilled (unparking this thread)
372 // and the oneshot should not be needed any more
373 __attribute__((unused)) struct oneshot * was = this.ptr;
374 /* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was );
375
376 // Mark the future as fulfilled, to be consistent
377 // with potential calls to avail
378 // this.ptr = 1p;
379 return ret;
380 }
381
382 // Wait for any future to be fulfilled
383 forall(T& | sized(T) | { bool setup( T&, oneshot & ); bool retract( T&, oneshot & ); })
384 T & wait_any( T * futures, size_t num_futures ) {
385 oneshot temp;
386
387 // setup all futures
388 // if any are already satisfied return
389 for ( i; num_futures ) {
390 if( !setup(futures[i], temp) ) return futures[i];
391 }
392
393 // Wait context is setup, just wait on it
394 wait( temp );
395
396 size_t ret;
397 // attempt to retract all futures
398 for ( i; num_futures ) {
399 if ( retract( futures[i], temp ) ) ret = i;
400 }
401
402 return futures[ret];
403 }
404 }
405
406 //-----------------------------------------------------------------------
407 // Statics call at the end of each thread to register statistics
408 #if !defined(__CFA_NO_STATISTICS__)
409 static inline struct __stats_t * __tls_stats() {
410 /* paranoid */ verify( ! __preemption_enabled() );
411 /* paranoid */ verify( kernelTLS().this_stats );
412 return kernelTLS().this_stats;
413 }
414
415 #define __STATS__(in_kernel, ...) { \
416 if( !(in_kernel) ) disable_interrupts(); \
417 with( *__tls_stats() ) { \
418 __VA_ARGS__ \
419 } \
420 if( !(in_kernel) ) enable_interrupts(); \
421 }
422 #if defined(CFA_HAVE_LINUX_IO_URING_H)
423 #define __IO_STATS__(in_kernel, ...) { \
424 if( !(in_kernel) ) disable_interrupts(); \
425 with( *__tls_stats() ) { \
426 __VA_ARGS__ \
427 } \
428 if( !(in_kernel) ) enable_interrupts(); \
429 }
430 #else
431 #define __IO_STATS__(in_kernel, ...)
432 #endif
433 #else
434 #define __STATS__(in_kernel, ...)
435 #define __IO_STATS__(in_kernel, ...)
436 #endif
437 }
438}
439#endif
Note: See TracBrowser for help on using the repository browser.