[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] | 26 | struct thread$;
|
---|
[e660761] | 27 | struct processor;
|
---|
| 28 | struct cluster;
|
---|
| 29 |
|
---|
[3e2b9c9] | 30 | enum __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
|
---|
| 35 | extern "C" {
|
---|
[3e2b9c9] | 36 | extern "Cforall" {
|
---|
[e660761] | 37 | extern __attribute__((aligned(128))) thread_local 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 |
|
---|
| 48 | #if defined(__SIZEOF_INT128__)
|
---|
| 49 | __uint128_t rand_seed;
|
---|
| 50 | #else
|
---|
| 51 | uint64_t rand_seed;
|
---|
| 52 | #endif
|
---|
[f2384c9a] | 53 | struct {
|
---|
| 54 | uint64_t fwd_seed;
|
---|
| 55 | uint64_t bck_seed;
|
---|
| 56 | } ready_rng;
|
---|
[c993b15] | 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
|
---|
[8fc652e0] | 66 | } __cfaabi_tls __attribute__ ((tls_model ( "initial-exec" )));
|
---|
[3e2b9c9] | 67 |
|
---|
[8fc652e0] | 68 | extern bool __preemption_enabled();
|
---|
[f2384c9a] | 69 |
|
---|
[8fc652e0] | 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 );
|
---|
[82a2fed] | 76 | #define publicTLS_get( member ) ((typeof(__cfaabi_tls.member))__cfatls_get( __builtin_offsetof(KernelThreadData, member) ))
|
---|
[f2384c9a] | 77 |
|
---|
[3e2b9c9] | 78 | static inline uint64_t __tls_rand() {
|
---|
| 79 | #if defined(__SIZEOF_INT128__)
|
---|
[8fc652e0] | 80 | return __lehmer64( kernelTLS().rand_seed );
|
---|
[3e2b9c9] | 81 | #else
|
---|
[8fc652e0] | 82 | return __xorshift64( kernelTLS().rand_seed );
|
---|
[3e2b9c9] | 83 | #endif
|
---|
| 84 | }
|
---|
[f2384c9a] | 85 |
|
---|
| 86 | #define M (1_l64u << 48_l64u)
|
---|
| 87 | #define A (25214903917_l64u)
|
---|
| 88 | #define AI (18446708753438544741_l64u)
|
---|
| 89 | #define C (11_l64u)
|
---|
| 90 | #define D (16_l64u)
|
---|
| 91 |
|
---|
| 92 | static inline unsigned __tls_rand_fwd() {
|
---|
| 93 |
|
---|
[8fc652e0] | 94 | kernelTLS().ready_rng.fwd_seed = (A * kernelTLS().ready_rng.fwd_seed + C) & (M - 1);
|
---|
| 95 | return kernelTLS().ready_rng.fwd_seed >> D;
|
---|
[f2384c9a] | 96 | }
|
---|
| 97 |
|
---|
| 98 | static inline unsigned __tls_rand_bck() {
|
---|
[8fc652e0] | 99 | unsigned int r = kernelTLS().ready_rng.bck_seed >> D;
|
---|
| 100 | kernelTLS().ready_rng.bck_seed = AI * (kernelTLS().ready_rng.bck_seed - C) & (M - 1);
|
---|
[f2384c9a] | 101 | return r;
|
---|
| 102 | }
|
---|
| 103 |
|
---|
| 104 | #undef M
|
---|
| 105 | #undef A
|
---|
| 106 | #undef AI
|
---|
| 107 | #undef C
|
---|
| 108 | #undef D
|
---|
| 109 |
|
---|
| 110 | static inline void __tls_rand_advance_bck(void) {
|
---|
[8fc652e0] | 111 | kernelTLS().ready_rng.bck_seed = kernelTLS().ready_rng.fwd_seed;
|
---|
[f2384c9a] | 112 | }
|
---|
[e660761] | 113 | }
|
---|
| 114 |
|
---|
[8fc652e0] | 115 |
|
---|
[3e2b9c9] | 116 |
|
---|
| 117 | extern void disable_interrupts();
|
---|
[a3821fa] | 118 | extern void enable_interrupts( bool poll = false );
|
---|
[e660761] | 119 |
|
---|
[3e2b9c9] | 120 | extern "Cforall" {
|
---|
[24e321c] | 121 | enum unpark_hint { UNPARK_LOCAL, UNPARK_REMOTE };
|
---|
| 122 |
|
---|
[e235429] | 123 | extern void park( void );
|
---|
[24e321c] | 124 | extern void unpark( struct thread$ *, unpark_hint );
|
---|
| 125 | static inline void unpark( struct thread$ * thrd ) { unpark(thrd, UNPARK_LOCAL); }
|
---|
[e84ab3d] | 126 | static inline struct thread$ * active_thread () {
|
---|
| 127 | struct thread$ * t = publicTLS_get( this_thread );
|
---|
[8fc652e0] | 128 | /* paranoid */ verify( t );
|
---|
| 129 | return t;
|
---|
| 130 | }
|
---|
[3e2b9c9] | 131 |
|
---|
| 132 | extern bool force_yield( enum __Preemption_Reason );
|
---|
[e660761] | 133 |
|
---|
[3e2b9c9] | 134 | static inline void yield() {
|
---|
| 135 | force_yield(__MANUAL_PREEMPTION);
|
---|
| 136 | }
|
---|
[e660761] | 137 |
|
---|
[3e2b9c9] | 138 | // Yield: yield N times
|
---|
| 139 | static inline void yield( unsigned times ) {
|
---|
| 140 | for( times ) {
|
---|
| 141 | yield();
|
---|
| 142 | }
|
---|
| 143 | }
|
---|
| 144 |
|
---|
[fe9468e2] | 145 | extern uint64_t thread_rand();
|
---|
| 146 |
|
---|
[454f478] | 147 | // Semaphore which only supports a single thread
|
---|
| 148 | struct single_sem {
|
---|
[e84ab3d] | 149 | struct thread$ * volatile ptr;
|
---|
[454f478] | 150 | };
|
---|
| 151 |
|
---|
| 152 | static inline {
|
---|
| 153 | void ?{}(single_sem & this) {
|
---|
| 154 | this.ptr = 0p;
|
---|
| 155 | }
|
---|
| 156 |
|
---|
| 157 | void ^?{}(single_sem &) {}
|
---|
| 158 |
|
---|
| 159 | bool wait(single_sem & this) {
|
---|
| 160 | for() {
|
---|
[e84ab3d] | 161 | struct thread$ * expected = this.ptr;
|
---|
[454f478] | 162 | if(expected == 1p) {
|
---|
| 163 | if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
|
---|
| 164 | return false;
|
---|
| 165 | }
|
---|
| 166 | }
|
---|
| 167 | else {
|
---|
| 168 | /* paranoid */ verify( expected == 0p );
|
---|
| 169 | if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
|
---|
| 170 | park();
|
---|
| 171 | return true;
|
---|
| 172 | }
|
---|
| 173 | }
|
---|
| 174 |
|
---|
| 175 | }
|
---|
| 176 | }
|
---|
| 177 |
|
---|
| 178 | bool post(single_sem & this) {
|
---|
| 179 | for() {
|
---|
[e84ab3d] | 180 | struct thread$ * expected = this.ptr;
|
---|
[454f478] | 181 | if(expected == 1p) return false;
|
---|
| 182 | if(expected == 0p) {
|
---|
| 183 | if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
|
---|
| 184 | return false;
|
---|
| 185 | }
|
---|
| 186 | }
|
---|
| 187 | else {
|
---|
| 188 | if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
|
---|
| 189 | unpark( expected );
|
---|
| 190 | return true;
|
---|
| 191 | }
|
---|
| 192 | }
|
---|
| 193 | }
|
---|
| 194 | }
|
---|
| 195 | }
|
---|
| 196 |
|
---|
| 197 | // Synchronozation primitive which only supports a single thread and one post
|
---|
| 198 | // Similar to a binary semaphore with a 'one shot' semantic
|
---|
| 199 | // is expected to be discarded after each party call their side
|
---|
| 200 | struct oneshot {
|
---|
| 201 | // Internal state :
|
---|
| 202 | // 0p : is initial state (wait will block)
|
---|
| 203 | // 1p : fulfilled (wait won't block)
|
---|
| 204 | // any thread : a thread is currently waiting
|
---|
[e84ab3d] | 205 | struct thread$ * volatile ptr;
|
---|
[454f478] | 206 | };
|
---|
| 207 |
|
---|
| 208 | static inline {
|
---|
| 209 | void ?{}(oneshot & this) {
|
---|
| 210 | this.ptr = 0p;
|
---|
| 211 | }
|
---|
| 212 |
|
---|
| 213 | void ^?{}(oneshot &) {}
|
---|
| 214 |
|
---|
| 215 | // Wait for the post, return immidiately if it already happened.
|
---|
| 216 | // return true if the thread was parked
|
---|
| 217 | bool wait(oneshot & this) {
|
---|
| 218 | for() {
|
---|
[e84ab3d] | 219 | struct thread$ * expected = this.ptr;
|
---|
[454f478] | 220 | if(expected == 1p) return false;
|
---|
| 221 | /* paranoid */ verify( expected == 0p );
|
---|
| 222 | if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
|
---|
| 223 | park();
|
---|
| 224 | /* paranoid */ verify( this.ptr == 1p );
|
---|
| 225 | return true;
|
---|
| 226 | }
|
---|
| 227 | }
|
---|
| 228 | }
|
---|
| 229 |
|
---|
| 230 | // Mark as fulfilled, wake thread if needed
|
---|
| 231 | // return true if a thread was unparked
|
---|
[e84ab3d] | 232 | thread$ * post(oneshot & this, bool do_unpark = true) {
|
---|
| 233 | struct thread$ * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
|
---|
[a76efc8] | 234 | if( got == 0p ) return 0p;
|
---|
| 235 | if(do_unpark) unpark( got );
|
---|
| 236 | return got;
|
---|
[454f478] | 237 | }
|
---|
| 238 | }
|
---|
| 239 |
|
---|
| 240 | // base types for future to build upon
|
---|
| 241 | // It is based on the 'oneshot' type to allow multiple futures
|
---|
| 242 | // to block on the same instance, permitting users to block a single
|
---|
| 243 | // thread on "any of" [a given set of] futures.
|
---|
| 244 | // does not support multiple threads waiting on the same future
|
---|
| 245 | struct future_t {
|
---|
| 246 | // Internal state :
|
---|
| 247 | // 0p : is initial state (wait will block)
|
---|
| 248 | // 1p : fulfilled (wait won't block)
|
---|
| 249 | // 2p : in progress ()
|
---|
| 250 | // 3p : abandoned, server should delete
|
---|
| 251 | // any oneshot : a context has been setup to wait, a thread could wait on it
|
---|
| 252 | struct oneshot * volatile ptr;
|
---|
| 253 | };
|
---|
| 254 |
|
---|
| 255 | static inline {
|
---|
| 256 | void ?{}(future_t & this) {
|
---|
| 257 | this.ptr = 0p;
|
---|
| 258 | }
|
---|
| 259 |
|
---|
| 260 | void ^?{}(future_t &) {}
|
---|
| 261 |
|
---|
| 262 | void reset(future_t & this) {
|
---|
| 263 | // needs to be in 0p or 1p
|
---|
| 264 | __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);
|
---|
| 265 | }
|
---|
| 266 |
|
---|
| 267 | // check if the future is available
|
---|
| 268 | bool available( future_t & this ) {
|
---|
| 269 | return this.ptr == 1p;
|
---|
| 270 | }
|
---|
| 271 |
|
---|
| 272 | // Prepare the future to be waited on
|
---|
| 273 | // intented to be use by wait, wait_any, waitfor, etc. rather than used directly
|
---|
| 274 | bool setup( future_t & this, oneshot & wait_ctx ) {
|
---|
| 275 | /* paranoid */ verify( wait_ctx.ptr == 0p );
|
---|
| 276 | // The future needs to set the wait context
|
---|
| 277 | for() {
|
---|
| 278 | struct oneshot * expected = this.ptr;
|
---|
| 279 | // Is the future already fulfilled?
|
---|
| 280 | if(expected == 1p) return false; // Yes, just return false (didn't block)
|
---|
| 281 |
|
---|
| 282 | // The future is not fulfilled, try to setup the wait context
|
---|
| 283 | /* paranoid */ verify( expected == 0p );
|
---|
| 284 | if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
|
---|
| 285 | return true;
|
---|
| 286 | }
|
---|
| 287 | }
|
---|
| 288 | }
|
---|
| 289 |
|
---|
| 290 | // Stop waiting on a future
|
---|
| 291 | // When multiple futures are waited for together in "any of" pattern
|
---|
| 292 | // futures that weren't fulfilled before the thread woke up
|
---|
| 293 | // should retract the wait ctx
|
---|
| 294 | // intented to be use by wait, wait_any, waitfor, etc. rather than used directly
|
---|
| 295 | void retract( future_t & this, oneshot & wait_ctx ) {
|
---|
| 296 | // Remove the wait context
|
---|
| 297 | struct oneshot * got = __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);
|
---|
| 298 |
|
---|
| 299 | // got == 0p: future was never actually setup, just return
|
---|
| 300 | if( got == 0p ) return;
|
---|
| 301 |
|
---|
| 302 | // got == wait_ctx: since fulfil does an atomic_swap,
|
---|
| 303 | // if we got back the original then no one else saw context
|
---|
| 304 | // It is safe to delete (which could happen after the return)
|
---|
| 305 | if( got == &wait_ctx ) return;
|
---|
| 306 |
|
---|
| 307 | // got == 1p: the future is ready and the context was fully consumed
|
---|
| 308 | // the server won't use the pointer again
|
---|
| 309 | // It is safe to delete (which could happen after the return)
|
---|
| 310 | if( got == 1p ) return;
|
---|
| 311 |
|
---|
| 312 | // got == 2p: the future is ready but the context hasn't fully been consumed
|
---|
| 313 | // spin until it is safe to move on
|
---|
| 314 | if( got == 2p ) {
|
---|
| 315 | while( this.ptr != 1p ) Pause();
|
---|
| 316 | return;
|
---|
| 317 | }
|
---|
| 318 |
|
---|
| 319 | // got == any thing else, something wen't wrong here, abort
|
---|
| 320 | abort("Future in unexpected state");
|
---|
| 321 | }
|
---|
| 322 |
|
---|
| 323 | // Mark the future as abandoned, meaning it will be deleted by the server
|
---|
| 324 | bool abandon( future_t & this ) {
|
---|
| 325 | /* paranoid */ verify( this.ptr != 3p );
|
---|
| 326 |
|
---|
| 327 | // Mark the future as abandonned
|
---|
| 328 | struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST);
|
---|
| 329 |
|
---|
| 330 | // If the future isn't already fulfilled, let the server delete it
|
---|
| 331 | if( got == 0p ) return false;
|
---|
| 332 |
|
---|
| 333 | // got == 2p: the future is ready but the context hasn't fully been consumed
|
---|
| 334 | // spin until it is safe to move on
|
---|
| 335 | if( got == 2p ) {
|
---|
| 336 | while( this.ptr != 1p ) Pause();
|
---|
| 337 | got = 1p;
|
---|
| 338 | }
|
---|
| 339 |
|
---|
| 340 | // The future is completed delete it now
|
---|
| 341 | /* paranoid */ verify( this.ptr != 1p );
|
---|
| 342 | free( &this );
|
---|
| 343 | return true;
|
---|
| 344 | }
|
---|
| 345 |
|
---|
| 346 | // from the server side, mark the future as fulfilled
|
---|
| 347 | // delete it if needed
|
---|
[e84ab3d] | 348 | thread$ * fulfil( future_t & this, bool do_unpark = true ) {
|
---|
[454f478] | 349 | for() {
|
---|
| 350 | struct oneshot * expected = this.ptr;
|
---|
| 351 | // was this abandoned?
|
---|
| 352 | #if defined(__GNUC__) && __GNUC__ >= 7
|
---|
| 353 | #pragma GCC diagnostic push
|
---|
| 354 | #pragma GCC diagnostic ignored "-Wfree-nonheap-object"
|
---|
| 355 | #endif
|
---|
[a76efc8] | 356 | if( expected == 3p ) { free( &this ); return 0p; }
|
---|
[454f478] | 357 | #if defined(__GNUC__) && __GNUC__ >= 7
|
---|
| 358 | #pragma GCC diagnostic pop
|
---|
| 359 | #endif
|
---|
| 360 |
|
---|
| 361 | /* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen
|
---|
| 362 | /* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case.
|
---|
| 363 |
|
---|
| 364 | // If there is a wait context, we need to consume it and mark it as consumed after
|
---|
| 365 | // If there is no context then we can skip the in progress phase
|
---|
| 366 | struct oneshot * want = expected == 0p ? 1p : 2p;
|
---|
| 367 | if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
|
---|
[a76efc8] | 368 | if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return 0p; }
|
---|
[e84ab3d] | 369 | thread$ * ret = post( *expected, do_unpark );
|
---|
[454f478] | 370 | __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST);
|
---|
| 371 | return ret;
|
---|
| 372 | }
|
---|
| 373 | }
|
---|
| 374 |
|
---|
| 375 | }
|
---|
| 376 |
|
---|
| 377 | // Wait for the future to be fulfilled
|
---|
| 378 | bool wait( future_t & this ) {
|
---|
| 379 | oneshot temp;
|
---|
| 380 | if( !setup(this, temp) ) return false;
|
---|
| 381 |
|
---|
| 382 | // Wait context is setup, just wait on it
|
---|
| 383 | bool ret = wait( temp );
|
---|
| 384 |
|
---|
| 385 | // Wait for the future to tru
|
---|
| 386 | while( this.ptr == 2p ) Pause();
|
---|
| 387 | // Make sure the state makes sense
|
---|
| 388 | // Should be fulfilled, could be in progress but it's out of date if so
|
---|
| 389 | // since if that is the case, the oneshot was fulfilled (unparking this thread)
|
---|
| 390 | // and the oneshot should not be needed any more
|
---|
| 391 | __attribute__((unused)) struct oneshot * was = this.ptr;
|
---|
| 392 | /* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was );
|
---|
| 393 |
|
---|
| 394 | // Mark the future as fulfilled, to be consistent
|
---|
| 395 | // with potential calls to avail
|
---|
| 396 | // this.ptr = 1p;
|
---|
| 397 | return ret;
|
---|
| 398 | }
|
---|
| 399 | }
|
---|
| 400 |
|
---|
[3e2b9c9] | 401 | //-----------------------------------------------------------------------
|
---|
| 402 | // Statics call at the end of each thread to register statistics
|
---|
| 403 | #if !defined(__CFA_NO_STATISTICS__)
|
---|
| 404 | static inline struct __stats_t * __tls_stats() {
|
---|
[8fc652e0] | 405 | /* paranoid */ verify( ! __preemption_enabled() );
|
---|
| 406 | /* paranoid */ verify( kernelTLS().this_stats );
|
---|
| 407 | return kernelTLS().this_stats;
|
---|
[3e2b9c9] | 408 | }
|
---|
| 409 |
|
---|
| 410 | #define __STATS__(in_kernel, ...) { \
|
---|
| 411 | if( !(in_kernel) ) disable_interrupts(); \
|
---|
| 412 | with( *__tls_stats() ) { \
|
---|
| 413 | __VA_ARGS__ \
|
---|
| 414 | } \
|
---|
[a3821fa] | 415 | if( !(in_kernel) ) enable_interrupts(); \
|
---|
[3e2b9c9] | 416 | }
|
---|
| 417 | #else
|
---|
| 418 | #define __STATS__(in_kernel, ...)
|
---|
| 419 | #endif
|
---|
| 420 | }
|
---|
[e660761] | 421 | }
|
---|
[442b624] | 422 | #endif
|
---|