[ea7d2b0] | 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 | // |
---|
[73abe95] | 7 | // bits/locks.hfa -- Fast internal locks. |
---|
[ea7d2b0] | 8 | // |
---|
| 9 | // Author : Thierry Delisle |
---|
| 10 | // Created On : Tue Oct 31 15:14:38 2017 |
---|
[b158d8f] | 11 | // Last Modified By : Peter A. Buhr |
---|
[fd9b524] | 12 | // Last Modified On : Wed Aug 12 14:18:07 2020 |
---|
| 13 | // Update Count : 13 |
---|
[ea7d2b0] | 14 | // |
---|
| 15 | |
---|
| 16 | #pragma once |
---|
| 17 | |
---|
[73abe95] | 18 | #include "bits/debug.hfa" |
---|
| 19 | #include "bits/defs.hfa" |
---|
[ea8b2f7] | 20 | #include <assert.h> |
---|
| 21 | |
---|
| 22 | #ifdef __cforall |
---|
| 23 | extern "C" { |
---|
| 24 | #include <pthread.h> |
---|
| 25 | } |
---|
| 26 | #endif |
---|
[ea7d2b0] | 27 | |
---|
| 28 | // pause to prevent excess processor bus usage |
---|
[fd9b524] | 29 | #if defined( __i386 ) || defined( __x86_64 ) |
---|
[ea7d2b0] | 30 | #define Pause() __asm__ __volatile__ ( "pause" : : : ) |
---|
[b158d8f] | 31 | #elif defined( __ARM_ARCH ) |
---|
[fd9b524] | 32 | #define Pause() __asm__ __volatile__ ( "YIELD" : : : ) |
---|
[ea7d2b0] | 33 | #else |
---|
| 34 | #error unsupported architecture |
---|
| 35 | #endif |
---|
| 36 | |
---|
| 37 | struct __spinlock_t { |
---|
[13073be] | 38 | // Wrap in struct to prevent false sharing with debug info |
---|
[3aeee3c] | 39 | volatile bool lock; |
---|
[ea7d2b0] | 40 | #ifdef __CFA_DEBUG__ |
---|
[13073be] | 41 | // previous function to acquire the lock |
---|
[ea7d2b0] | 42 | const char * prev_name; |
---|
[13073be] | 43 | // previous thread to acquire the lock |
---|
[ea7d2b0] | 44 | void* prev_thrd; |
---|
| 45 | #endif |
---|
[3aeee3c] | 46 | }; |
---|
[ea7d2b0] | 47 | |
---|
[0cf5b79] | 48 | #ifdef __cforall |
---|
[dbe9b08] | 49 | extern "C" { |
---|
[2026bb6] | 50 | extern void disable_interrupts() OPTIONAL_THREAD; |
---|
| 51 | extern void enable_interrupts_noPoll() OPTIONAL_THREAD; |
---|
[1997b4e] | 52 | |
---|
| 53 | #ifdef __CFA_DEBUG__ |
---|
[ae66348] | 54 | void __cfaabi_dbg_record_lock(__spinlock_t & this, const char prev_name[]); |
---|
[1997b4e] | 55 | #else |
---|
[ae66348] | 56 | #define __cfaabi_dbg_record_lock(x, y) |
---|
[1997b4e] | 57 | #endif |
---|
[dbe9b08] | 58 | } |
---|
| 59 | |
---|
[ea7d2b0] | 60 | static inline void ?{}( __spinlock_t & this ) { |
---|
| 61 | this.lock = 0; |
---|
| 62 | } |
---|
| 63 | |
---|
| 64 | // Lock the spinlock, return false if already acquired |
---|
[93c2e0a] | 65 | static inline bool try_lock ( __spinlock_t & this __cfaabi_dbg_ctx_param2 ) { |
---|
[3381ed7] | 66 | disable_interrupts(); |
---|
[93c2e0a] | 67 | bool result = (this.lock == 0) && (__atomic_test_and_set( &this.lock, __ATOMIC_ACQUIRE ) == 0); |
---|
[dbe9b08] | 68 | if( result ) { |
---|
[ae66348] | 69 | __cfaabi_dbg_record_lock( this, caller ); |
---|
[3381ed7] | 70 | } else { |
---|
| 71 | enable_interrupts_noPoll(); |
---|
[dbe9b08] | 72 | } |
---|
[ea7d2b0] | 73 | return result; |
---|
| 74 | } |
---|
| 75 | |
---|
| 76 | // Lock the spinlock, spin if already acquired |
---|
[36982fc] | 77 | static inline void lock( __spinlock_t & this __cfaabi_dbg_ctx_param2 ) { |
---|
[ea7d2b0] | 78 | #ifndef NOEXPBACK |
---|
| 79 | enum { SPIN_START = 4, SPIN_END = 64 * 1024, }; |
---|
| 80 | unsigned int spin = SPIN_START; |
---|
| 81 | #endif |
---|
| 82 | |
---|
[3381ed7] | 83 | disable_interrupts(); |
---|
[ea7d2b0] | 84 | for ( unsigned int i = 1;; i += 1 ) { |
---|
[13073be] | 85 | if ( (this.lock == 0) && (__atomic_test_and_set( &this.lock, __ATOMIC_ACQUIRE ) == 0) ) break; |
---|
[ea7d2b0] | 86 | #ifndef NOEXPBACK |
---|
| 87 | // exponential spin |
---|
| 88 | for ( volatile unsigned int s = 0; s < spin; s += 1 ) Pause(); |
---|
| 89 | |
---|
| 90 | // slowly increase by powers of 2 |
---|
| 91 | if ( i % 64 == 0 ) spin += spin; |
---|
| 92 | |
---|
| 93 | // prevent overflow |
---|
| 94 | if ( spin > SPIN_END ) spin = SPIN_START; |
---|
| 95 | #else |
---|
| 96 | Pause(); |
---|
| 97 | #endif |
---|
| 98 | } |
---|
[ae66348] | 99 | __cfaabi_dbg_record_lock( this, caller ); |
---|
[ea7d2b0] | 100 | } |
---|
| 101 | |
---|
| 102 | static inline void unlock( __spinlock_t & this ) { |
---|
[13073be] | 103 | __atomic_clear( &this.lock, __ATOMIC_RELEASE ); |
---|
[3381ed7] | 104 | enable_interrupts_noPoll(); |
---|
[ea7d2b0] | 105 | } |
---|
[ea8b2f7] | 106 | |
---|
| 107 | |
---|
| 108 | #ifdef __CFA_WITH_VERIFY__ |
---|
| 109 | extern bool __cfaabi_dbg_in_kernel(); |
---|
| 110 | #endif |
---|
| 111 | |
---|
[c66f6cb] | 112 | extern "C" { |
---|
| 113 | char * strerror(int); |
---|
| 114 | } |
---|
[6ec07e5] | 115 | #define CHECKED(x) { int err = x; if( err != 0 ) abort("KERNEL ERROR: Operation \"" #x "\" return error %d - %s\n", err, strerror(err)); } |
---|
[c66f6cb] | 116 | |
---|
[ea8b2f7] | 117 | struct __bin_sem_t { |
---|
[85b1deb] | 118 | pthread_mutex_t lock; |
---|
| 119 | pthread_cond_t cond; |
---|
[4069faad] | 120 | int val; |
---|
[ea8b2f7] | 121 | }; |
---|
| 122 | |
---|
| 123 | static inline void ?{}(__bin_sem_t & this) with( this ) { |
---|
[c66f6cb] | 124 | // Create the mutex with error checking |
---|
| 125 | pthread_mutexattr_t mattr; |
---|
| 126 | pthread_mutexattr_init( &mattr ); |
---|
| 127 | pthread_mutexattr_settype( &mattr, PTHREAD_MUTEX_ERRORCHECK_NP); |
---|
| 128 | pthread_mutex_init(&lock, &mattr); |
---|
| 129 | |
---|
[b81fd95] | 130 | pthread_cond_init (&cond, (const pthread_condattr_t *)0p); // workaround trac#208: cast should not be required |
---|
[4069faad] | 131 | val = 0; |
---|
[ea8b2f7] | 132 | } |
---|
| 133 | |
---|
| 134 | static inline void ^?{}(__bin_sem_t & this) with( this ) { |
---|
[c66f6cb] | 135 | CHECKED( pthread_mutex_destroy(&lock) ); |
---|
| 136 | CHECKED( pthread_cond_destroy (&cond) ); |
---|
[ea8b2f7] | 137 | } |
---|
| 138 | |
---|
| 139 | static inline void wait(__bin_sem_t & this) with( this ) { |
---|
| 140 | verify(__cfaabi_dbg_in_kernel()); |
---|
[c66f6cb] | 141 | CHECKED( pthread_mutex_lock(&lock) ); |
---|
[4069faad] | 142 | while(val < 1) { |
---|
[85b1deb] | 143 | pthread_cond_wait(&cond, &lock); |
---|
| 144 | } |
---|
[4069faad] | 145 | val -= 1; |
---|
[c66f6cb] | 146 | CHECKED( pthread_mutex_unlock(&lock) ); |
---|
[ea8b2f7] | 147 | } |
---|
| 148 | |
---|
[92e7631] | 149 | static inline bool post(__bin_sem_t & this) with( this ) { |
---|
[4069faad] | 150 | bool needs_signal = false; |
---|
| 151 | |
---|
[c66f6cb] | 152 | CHECKED( pthread_mutex_lock(&lock) ); |
---|
[4069faad] | 153 | if(val < 1) { |
---|
| 154 | val += 1; |
---|
| 155 | pthread_cond_signal(&cond); |
---|
| 156 | needs_signal = true; |
---|
| 157 | } |
---|
[c66f6cb] | 158 | CHECKED( pthread_mutex_unlock(&lock) ); |
---|
[85b1deb] | 159 | |
---|
[92e7631] | 160 | return needs_signal; |
---|
[85b1deb] | 161 | } |
---|
[c66f6cb] | 162 | |
---|
| 163 | #undef CHECKED |
---|
[e0f93e0] | 164 | |
---|
| 165 | struct $thread; |
---|
| 166 | extern void park( __cfaabi_dbg_ctx_param ); |
---|
| 167 | extern void unpark( struct $thread * this __cfaabi_dbg_ctx_param2 ); |
---|
| 168 | static inline struct $thread * active_thread (); |
---|
| 169 | |
---|
| 170 | // Semaphore which only supports a single thread |
---|
| 171 | struct single_sem { |
---|
| 172 | struct $thread * volatile ptr; |
---|
| 173 | }; |
---|
| 174 | |
---|
| 175 | static inline { |
---|
| 176 | void ?{}(single_sem & this) { |
---|
| 177 | this.ptr = 0p; |
---|
| 178 | } |
---|
| 179 | |
---|
| 180 | void ^?{}(single_sem & this) {} |
---|
| 181 | |
---|
| 182 | bool wait(single_sem & this) { |
---|
| 183 | for() { |
---|
| 184 | struct $thread * expected = this.ptr; |
---|
| 185 | if(expected == 1p) { |
---|
| 186 | if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { |
---|
| 187 | return false; |
---|
| 188 | } |
---|
| 189 | } |
---|
| 190 | else { |
---|
| 191 | /* paranoid */ verify( expected == 0p ); |
---|
| 192 | if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { |
---|
| 193 | park( __cfaabi_dbg_ctx ); |
---|
| 194 | return true; |
---|
| 195 | } |
---|
| 196 | } |
---|
| 197 | |
---|
| 198 | } |
---|
| 199 | } |
---|
| 200 | |
---|
| 201 | bool post(single_sem & this) { |
---|
| 202 | for() { |
---|
| 203 | struct $thread * expected = this.ptr; |
---|
| 204 | if(expected == 1p) return false; |
---|
| 205 | if(expected == 0p) { |
---|
| 206 | if(__atomic_compare_exchange_n(&this.ptr, &expected, 1p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { |
---|
| 207 | return false; |
---|
| 208 | } |
---|
| 209 | } |
---|
| 210 | else { |
---|
| 211 | if(__atomic_compare_exchange_n(&this.ptr, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { |
---|
| 212 | unpark( expected __cfaabi_dbg_ctx2 ); |
---|
| 213 | return true; |
---|
| 214 | } |
---|
| 215 | } |
---|
| 216 | } |
---|
| 217 | } |
---|
| 218 | } |
---|
[b353a49] | 219 | |
---|
[a77496cb] | 220 | // Synchronozation primitive which only supports a single thread and one post |
---|
| 221 | // Similar to a binary semaphore with a 'one shot' semantic |
---|
| 222 | // is expected to be discarded after each party call their side |
---|
[b353a49] | 223 | struct oneshot { |
---|
[a77496cb] | 224 | // Internal state : |
---|
| 225 | // 0p : is initial state (wait will block) |
---|
| 226 | // 1p : fulfilled (wait won't block) |
---|
| 227 | // any thread : a thread is currently waiting |
---|
[b353a49] | 228 | struct $thread * volatile ptr; |
---|
| 229 | }; |
---|
| 230 | |
---|
| 231 | static inline { |
---|
| 232 | void ?{}(oneshot & this) { |
---|
| 233 | this.ptr = 0p; |
---|
| 234 | } |
---|
| 235 | |
---|
| 236 | void ^?{}(oneshot & this) {} |
---|
| 237 | |
---|
[a77496cb] | 238 | // Wait for the post, return immidiately if it already happened. |
---|
| 239 | // return true if the thread was parked |
---|
[b353a49] | 240 | bool wait(oneshot & this) { |
---|
| 241 | for() { |
---|
| 242 | struct $thread * expected = this.ptr; |
---|
| 243 | if(expected == 1p) return false; |
---|
| 244 | /* paranoid */ verify( expected == 0p ); |
---|
| 245 | if(__atomic_compare_exchange_n(&this.ptr, &expected, active_thread(), false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { |
---|
| 246 | park( __cfaabi_dbg_ctx ); |
---|
| 247 | /* paranoid */ verify( this.ptr == 1p ); |
---|
| 248 | return true; |
---|
| 249 | } |
---|
| 250 | } |
---|
| 251 | } |
---|
| 252 | |
---|
[a77496cb] | 253 | // Mark as fulfilled, wake thread if needed |
---|
| 254 | // return true if a thread was unparked |
---|
[b353a49] | 255 | bool post(oneshot & this) { |
---|
| 256 | struct $thread * got = __atomic_exchange_n( &this.ptr, 1p, __ATOMIC_SEQ_CST); |
---|
| 257 | if( got == 0p ) return false; |
---|
| 258 | unpark( got __cfaabi_dbg_ctx2 ); |
---|
| 259 | return true; |
---|
| 260 | } |
---|
| 261 | } |
---|
[a77496cb] | 262 | |
---|
| 263 | // base types for future to build upon |
---|
| 264 | // It is based on the 'oneshot' type to allow multiple futures |
---|
| 265 | // to block on the same instance, permitting users to block a single |
---|
| 266 | // thread on "any of" [a given set of] futures. |
---|
| 267 | // does not support multiple threads waiting on the same future |
---|
| 268 | struct future_t { |
---|
| 269 | // Internal state : |
---|
| 270 | // 0p : is initial state (wait will block) |
---|
| 271 | // 1p : fulfilled (wait won't block) |
---|
| 272 | // 2p : in progress () |
---|
| 273 | // 3p : abandoned, server should delete |
---|
| 274 | // any oneshot : a context has been setup to wait, a thread could wait on it |
---|
| 275 | struct oneshot * volatile ptr; |
---|
| 276 | }; |
---|
| 277 | |
---|
| 278 | static inline { |
---|
| 279 | void ?{}(future_t & this) { |
---|
| 280 | this.ptr = 0p; |
---|
| 281 | } |
---|
| 282 | |
---|
| 283 | void ^?{}(future_t & this) {} |
---|
| 284 | |
---|
| 285 | // check if the future is available |
---|
| 286 | bool available( future_t & this ) { |
---|
| 287 | return this.ptr == 1p; |
---|
| 288 | } |
---|
| 289 | |
---|
| 290 | // Prepare the future to be waited on |
---|
| 291 | // intented to be use by wait, wait_any, waitfor, etc. rather than used directly |
---|
| 292 | bool setup( future_t & this, oneshot & wait_ctx ) { |
---|
| 293 | /* paranoid */ verify( wait_ctx.ptr == 0p ); |
---|
| 294 | // The future needs to set the wait context |
---|
| 295 | for() { |
---|
| 296 | struct oneshot * expected = this.ptr; |
---|
| 297 | // Is the future already fulfilled? |
---|
| 298 | if(expected == 1p) return false; // Yes, just return false (didn't block) |
---|
| 299 | |
---|
| 300 | // The future is not fulfilled, try to setup the wait context |
---|
| 301 | /* paranoid */ verify( expected == 0p ); |
---|
| 302 | if(__atomic_compare_exchange_n(&this.ptr, &expected, &wait_ctx, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { |
---|
| 303 | return true; |
---|
| 304 | } |
---|
| 305 | } |
---|
| 306 | } |
---|
| 307 | |
---|
| 308 | // Stop waiting on a future |
---|
| 309 | // When multiple futures are waited for together in "any of" pattern |
---|
| 310 | // futures that weren't fulfilled before the thread woke up |
---|
| 311 | // should retract the wait ctx |
---|
| 312 | // intented to be use by wait, wait_any, waitfor, etc. rather than used directly |
---|
| 313 | void retract( future_t & this, oneshot & wait_ctx ) { |
---|
| 314 | // Remove the wait context |
---|
| 315 | struct oneshot * got = __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST); |
---|
| 316 | |
---|
| 317 | // got == 0p: future was never actually setup, just return |
---|
| 318 | if( got == 0p ) return; |
---|
| 319 | |
---|
| 320 | // got == wait_ctx: since fulfil does an atomic_swap, |
---|
| 321 | // if we got back the original then no one else saw context |
---|
| 322 | // It is safe to delete (which could happen after the return) |
---|
| 323 | if( got == &wait_ctx ) return; |
---|
| 324 | |
---|
| 325 | // got == 1p: the future is ready and the context was fully consumed |
---|
| 326 | // the server won't use the pointer again |
---|
| 327 | // It is safe to delete (which could happen after the return) |
---|
| 328 | if( got == 1p ) return; |
---|
| 329 | |
---|
| 330 | // got == 2p: the future is ready but the context hasn't fully been consumed |
---|
| 331 | // spin until it is safe to move on |
---|
| 332 | if( got == 2p ) { |
---|
| 333 | while( this.ptr != 1p ) Pause(); |
---|
| 334 | return; |
---|
| 335 | } |
---|
| 336 | |
---|
| 337 | // got == any thing else, something wen't wrong here, abort |
---|
| 338 | abort("Future in unexpected state"); |
---|
| 339 | } |
---|
| 340 | |
---|
| 341 | // Mark the future as abandoned, meaning it will be deleted by the server |
---|
| 342 | void abandon( future_t & this ) { |
---|
| 343 | struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST); |
---|
| 344 | |
---|
| 345 | // got == 2p: the future is ready but the context hasn't fully been consumed |
---|
| 346 | // spin until it is safe to move on |
---|
| 347 | if( got == 2p ) { |
---|
| 348 | while( this.ptr != 1p ) Pause(); |
---|
| 349 | } |
---|
| 350 | return; |
---|
| 351 | } |
---|
| 352 | |
---|
| 353 | // from the server side, mark the future as fulfilled |
---|
| 354 | // delete it if needed |
---|
| 355 | bool fulfil( future_t & this ) { |
---|
| 356 | for() { |
---|
| 357 | struct oneshot * expected = this.ptr; |
---|
| 358 | // was this abandoned? |
---|
[ace2e92] | 359 | #if defined(__GNUC__) && __GNUC__ >= 7 |
---|
| 360 | #pragma GCC diagnostic push |
---|
| 361 | #pragma GCC diagnostic ignored "-Wfree-nonheap-object" |
---|
| 362 | #endif |
---|
| 363 | if( expected == 3p ) { free( &this ); return false; } |
---|
| 364 | #if defined(__GNUC__) && __GNUC__ >= 7 |
---|
| 365 | #pragma GCC diagnostic pop |
---|
| 366 | #endif |
---|
[a77496cb] | 367 | |
---|
| 368 | /* paranoid */ verify( expected != 1p ); // Future is already fulfilled, should not happen |
---|
| 369 | /* paranoid */ verify( expected != 2p ); // Future is bein fulfilled by someone else, this is even less supported then the previous case. |
---|
| 370 | |
---|
| 371 | // If there is a wait context, we need to consume it and mark it as consumed after |
---|
| 372 | // If there is no context then we can skip the in progress phase |
---|
| 373 | struct oneshot * want = expected == 0p ? 1p : 2p; |
---|
| 374 | if(__atomic_compare_exchange_n(&this.ptr, &expected, want, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) { |
---|
| 375 | if( expected == 0p ) { /* paranoid */ verify( this.ptr == 1p); return false; } |
---|
| 376 | bool ret = post( *expected ); |
---|
| 377 | __atomic_store_n( &this.ptr, 1p, __ATOMIC_SEQ_CST); |
---|
| 378 | return ret; |
---|
| 379 | } |
---|
| 380 | } |
---|
| 381 | |
---|
| 382 | } |
---|
| 383 | |
---|
| 384 | // Wait for the future to be fulfilled |
---|
| 385 | bool wait( future_t & this ) { |
---|
| 386 | oneshot temp; |
---|
| 387 | if( !setup(this, temp) ) return false; |
---|
| 388 | |
---|
| 389 | // Wait context is setup, just wait on it |
---|
| 390 | bool ret = wait( temp ); |
---|
| 391 | |
---|
| 392 | // Wait for the future to tru |
---|
| 393 | while( this.ptr == 2p ) Pause(); |
---|
| 394 | // Make sure the state makes sense |
---|
| 395 | // Should be fulfilled, could be in progress but it's out of date if so |
---|
| 396 | // since if that is the case, the oneshot was fulfilled (unparking this thread) |
---|
| 397 | // and the oneshot should not be needed any more |
---|
| 398 | __attribute__((unused)) struct oneshot * was = this.ptr; |
---|
| 399 | /* paranoid */ verifyf( was == 1p, "Expected this.ptr to be 1p, was %p\n", was ); |
---|
| 400 | |
---|
| 401 | // Mark the future as fulfilled, to be consistent |
---|
| 402 | // with potential calls to avail |
---|
| 403 | // this.ptr = 1p; |
---|
| 404 | return ret; |
---|
| 405 | } |
---|
| 406 | } |
---|
[b158d8f] | 407 | #endif |
---|