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

Last change on this file since e172f42 was dd46fd3, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago

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