1 /* 2 * kmp_lock.cpp -- lock-related functions 3 */ 4 5 //===----------------------------------------------------------------------===// 6 // 7 // The LLVM Compiler Infrastructure 8 // 9 // This file is dual licensed under the MIT and the University of Illinois Open 10 // Source Licenses. See LICENSE.txt for details. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include <stddef.h> 15 #include <atomic> 16 17 #include "kmp.h" 18 #include "kmp_i18n.h" 19 #include "kmp_io.h" 20 #include "kmp_itt.h" 21 #include "kmp_lock.h" 22 #include "kmp_wait_release.h" 23 #include "kmp_wrapper_getpid.h" 24 25 #include "tsan_annotations.h" 26 27 #if KMP_USE_FUTEX 28 #include <sys/syscall.h> 29 #include <unistd.h> 30 // We should really include <futex.h>, but that causes compatibility problems on 31 // different Linux* OS distributions that either require that you include (or 32 // break when you try to include) <pci/types.h>. Since all we need is the two 33 // macros below (which are part of the kernel ABI, so can't change) we just 34 // define the constants here and don't include <futex.h> 35 #ifndef FUTEX_WAIT 36 #define FUTEX_WAIT 0 37 #endif 38 #ifndef FUTEX_WAKE 39 #define FUTEX_WAKE 1 40 #endif 41 #endif 42 43 /* Implement spin locks for internal library use. */ 44 /* The algorithm implemented is Lamport's bakery lock [1974]. */ 45 46 void __kmp_validate_locks(void) { 47 int i; 48 kmp_uint32 x, y; 49 50 /* Check to make sure unsigned arithmetic does wraps properly */ 51 x = ~((kmp_uint32)0) - 2; 52 y = x - 2; 53 54 for (i = 0; i < 8; ++i, ++x, ++y) { 55 kmp_uint32 z = (x - y); 56 KMP_ASSERT(z == 2); 57 } 58 59 KMP_ASSERT(offsetof(kmp_base_queuing_lock, tail_id) % 8 == 0); 60 } 61 62 /* ------------------------------------------------------------------------ */ 63 /* test and set locks */ 64 65 // For the non-nested locks, we can only assume that the first 4 bytes were 66 // allocated, since gcc only allocates 4 bytes for omp_lock_t, and the Intel 67 // compiler only allocates a 4 byte pointer on IA-32 architecture. On 68 // Windows* OS on Intel(R) 64, we can assume that all 8 bytes were allocated. 69 // 70 // gcc reserves >= 8 bytes for nested locks, so we can assume that the 71 // entire 8 bytes were allocated for nested locks on all 64-bit platforms. 72 73 static kmp_int32 __kmp_get_tas_lock_owner(kmp_tas_lock_t *lck) { 74 return KMP_LOCK_STRIP(KMP_ATOMIC_LD_RLX(&lck->lk.poll)) - 1; 75 } 76 77 static inline bool __kmp_is_tas_lock_nestable(kmp_tas_lock_t *lck) { 78 return lck->lk.depth_locked != -1; 79 } 80 81 __forceinline static int 82 __kmp_acquire_tas_lock_timed_template(kmp_tas_lock_t *lck, kmp_int32 gtid) { 83 KMP_MB(); 84 85 #ifdef USE_LOCK_PROFILE 86 kmp_uint32 curr = KMP_LOCK_STRIP(lck->lk.poll); 87 if ((curr != 0) && (curr != gtid + 1)) 88 __kmp_printf("LOCK CONTENTION: %p\n", lck); 89 /* else __kmp_printf( "." );*/ 90 #endif /* USE_LOCK_PROFILE */ 91 92 kmp_int32 tas_free = KMP_LOCK_FREE(tas); 93 kmp_int32 tas_busy = KMP_LOCK_BUSY(gtid + 1, tas); 94 95 if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == tas_free && 96 __kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) { 97 KMP_FSYNC_ACQUIRED(lck); 98 return KMP_LOCK_ACQUIRED_FIRST; 99 } 100 101 kmp_uint32 spins; 102 KMP_FSYNC_PREPARE(lck); 103 KMP_INIT_YIELD(spins); 104 if (TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) { 105 KMP_YIELD(TRUE); 106 } else { 107 KMP_YIELD_SPIN(spins); 108 } 109 110 kmp_backoff_t backoff = __kmp_spin_backoff_params; 111 while (KMP_ATOMIC_LD_RLX(&lck->lk.poll) != tas_free || 112 !__kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) { 113 __kmp_spin_backoff(&backoff); 114 if (TCR_4(__kmp_nth) > 115 (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) { 116 KMP_YIELD(TRUE); 117 } else { 118 KMP_YIELD_SPIN(spins); 119 } 120 } 121 KMP_FSYNC_ACQUIRED(lck); 122 return KMP_LOCK_ACQUIRED_FIRST; 123 } 124 125 int __kmp_acquire_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { 126 int retval = __kmp_acquire_tas_lock_timed_template(lck, gtid); 127 ANNOTATE_TAS_ACQUIRED(lck); 128 return retval; 129 } 130 131 static int __kmp_acquire_tas_lock_with_checks(kmp_tas_lock_t *lck, 132 kmp_int32 gtid) { 133 char const *const func = "omp_set_lock"; 134 if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) && 135 __kmp_is_tas_lock_nestable(lck)) { 136 KMP_FATAL(LockNestableUsedAsSimple, func); 137 } 138 if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) == gtid)) { 139 KMP_FATAL(LockIsAlreadyOwned, func); 140 } 141 return __kmp_acquire_tas_lock(lck, gtid); 142 } 143 144 int __kmp_test_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { 145 kmp_int32 tas_free = KMP_LOCK_FREE(tas); 146 kmp_int32 tas_busy = KMP_LOCK_BUSY(gtid + 1, tas); 147 if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == tas_free && 148 __kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) { 149 KMP_FSYNC_ACQUIRED(lck); 150 return TRUE; 151 } 152 return FALSE; 153 } 154 155 static int __kmp_test_tas_lock_with_checks(kmp_tas_lock_t *lck, 156 kmp_int32 gtid) { 157 char const *const func = "omp_test_lock"; 158 if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) && 159 __kmp_is_tas_lock_nestable(lck)) { 160 KMP_FATAL(LockNestableUsedAsSimple, func); 161 } 162 return __kmp_test_tas_lock(lck, gtid); 163 } 164 165 int __kmp_release_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { 166 KMP_MB(); /* Flush all pending memory write invalidates. */ 167 168 KMP_FSYNC_RELEASING(lck); 169 ANNOTATE_TAS_RELEASED(lck); 170 KMP_ATOMIC_ST_REL(&lck->lk.poll, KMP_LOCK_FREE(tas)); 171 KMP_MB(); /* Flush all pending memory write invalidates. */ 172 173 KMP_YIELD(TCR_4(__kmp_nth) > 174 (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); 175 return KMP_LOCK_RELEASED; 176 } 177 178 static int __kmp_release_tas_lock_with_checks(kmp_tas_lock_t *lck, 179 kmp_int32 gtid) { 180 char const *const func = "omp_unset_lock"; 181 KMP_MB(); /* in case another processor initialized lock */ 182 if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) && 183 __kmp_is_tas_lock_nestable(lck)) { 184 KMP_FATAL(LockNestableUsedAsSimple, func); 185 } 186 if (__kmp_get_tas_lock_owner(lck) == -1) { 187 KMP_FATAL(LockUnsettingFree, func); 188 } 189 if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) >= 0) && 190 (__kmp_get_tas_lock_owner(lck) != gtid)) { 191 KMP_FATAL(LockUnsettingSetByAnother, func); 192 } 193 return __kmp_release_tas_lock(lck, gtid); 194 } 195 196 void __kmp_init_tas_lock(kmp_tas_lock_t *lck) { 197 lck->lk.poll = KMP_LOCK_FREE(tas); 198 } 199 200 void __kmp_destroy_tas_lock(kmp_tas_lock_t *lck) { lck->lk.poll = 0; } 201 202 static void __kmp_destroy_tas_lock_with_checks(kmp_tas_lock_t *lck) { 203 char const *const func = "omp_destroy_lock"; 204 if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) && 205 __kmp_is_tas_lock_nestable(lck)) { 206 KMP_FATAL(LockNestableUsedAsSimple, func); 207 } 208 if (__kmp_get_tas_lock_owner(lck) != -1) { 209 KMP_FATAL(LockStillOwned, func); 210 } 211 __kmp_destroy_tas_lock(lck); 212 } 213 214 // nested test and set locks 215 216 int __kmp_acquire_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { 217 KMP_DEBUG_ASSERT(gtid >= 0); 218 219 if (__kmp_get_tas_lock_owner(lck) == gtid) { 220 lck->lk.depth_locked += 1; 221 return KMP_LOCK_ACQUIRED_NEXT; 222 } else { 223 __kmp_acquire_tas_lock_timed_template(lck, gtid); 224 ANNOTATE_TAS_ACQUIRED(lck); 225 lck->lk.depth_locked = 1; 226 return KMP_LOCK_ACQUIRED_FIRST; 227 } 228 } 229 230 static int __kmp_acquire_nested_tas_lock_with_checks(kmp_tas_lock_t *lck, 231 kmp_int32 gtid) { 232 char const *const func = "omp_set_nest_lock"; 233 if (!__kmp_is_tas_lock_nestable(lck)) { 234 KMP_FATAL(LockSimpleUsedAsNestable, func); 235 } 236 return __kmp_acquire_nested_tas_lock(lck, gtid); 237 } 238 239 int __kmp_test_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { 240 int retval; 241 242 KMP_DEBUG_ASSERT(gtid >= 0); 243 244 if (__kmp_get_tas_lock_owner(lck) == gtid) { 245 retval = ++lck->lk.depth_locked; 246 } else if (!__kmp_test_tas_lock(lck, gtid)) { 247 retval = 0; 248 } else { 249 KMP_MB(); 250 retval = lck->lk.depth_locked = 1; 251 } 252 return retval; 253 } 254 255 static int __kmp_test_nested_tas_lock_with_checks(kmp_tas_lock_t *lck, 256 kmp_int32 gtid) { 257 char const *const func = "omp_test_nest_lock"; 258 if (!__kmp_is_tas_lock_nestable(lck)) { 259 KMP_FATAL(LockSimpleUsedAsNestable, func); 260 } 261 return __kmp_test_nested_tas_lock(lck, gtid); 262 } 263 264 int __kmp_release_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { 265 KMP_DEBUG_ASSERT(gtid >= 0); 266 267 KMP_MB(); 268 if (--(lck->lk.depth_locked) == 0) { 269 __kmp_release_tas_lock(lck, gtid); 270 return KMP_LOCK_RELEASED; 271 } 272 return KMP_LOCK_STILL_HELD; 273 } 274 275 static int __kmp_release_nested_tas_lock_with_checks(kmp_tas_lock_t *lck, 276 kmp_int32 gtid) { 277 char const *const func = "omp_unset_nest_lock"; 278 KMP_MB(); /* in case another processor initialized lock */ 279 if (!__kmp_is_tas_lock_nestable(lck)) { 280 KMP_FATAL(LockSimpleUsedAsNestable, func); 281 } 282 if (__kmp_get_tas_lock_owner(lck) == -1) { 283 KMP_FATAL(LockUnsettingFree, func); 284 } 285 if (__kmp_get_tas_lock_owner(lck) != gtid) { 286 KMP_FATAL(LockUnsettingSetByAnother, func); 287 } 288 return __kmp_release_nested_tas_lock(lck, gtid); 289 } 290 291 void __kmp_init_nested_tas_lock(kmp_tas_lock_t *lck) { 292 __kmp_init_tas_lock(lck); 293 lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks 294 } 295 296 void __kmp_destroy_nested_tas_lock(kmp_tas_lock_t *lck) { 297 __kmp_destroy_tas_lock(lck); 298 lck->lk.depth_locked = 0; 299 } 300 301 static void __kmp_destroy_nested_tas_lock_with_checks(kmp_tas_lock_t *lck) { 302 char const *const func = "omp_destroy_nest_lock"; 303 if (!__kmp_is_tas_lock_nestable(lck)) { 304 KMP_FATAL(LockSimpleUsedAsNestable, func); 305 } 306 if (__kmp_get_tas_lock_owner(lck) != -1) { 307 KMP_FATAL(LockStillOwned, func); 308 } 309 __kmp_destroy_nested_tas_lock(lck); 310 } 311 312 #if KMP_USE_FUTEX 313 314 /* ------------------------------------------------------------------------ */ 315 /* futex locks */ 316 317 // futex locks are really just test and set locks, with a different method 318 // of handling contention. They take the same amount of space as test and 319 // set locks, and are allocated the same way (i.e. use the area allocated by 320 // the compiler for non-nested locks / allocate nested locks on the heap). 321 322 static kmp_int32 __kmp_get_futex_lock_owner(kmp_futex_lock_t *lck) { 323 return KMP_LOCK_STRIP((TCR_4(lck->lk.poll) >> 1)) - 1; 324 } 325 326 static inline bool __kmp_is_futex_lock_nestable(kmp_futex_lock_t *lck) { 327 return lck->lk.depth_locked != -1; 328 } 329 330 __forceinline static int 331 __kmp_acquire_futex_lock_timed_template(kmp_futex_lock_t *lck, kmp_int32 gtid) { 332 kmp_int32 gtid_code = (gtid + 1) << 1; 333 334 KMP_MB(); 335 336 #ifdef USE_LOCK_PROFILE 337 kmp_uint32 curr = KMP_LOCK_STRIP(TCR_4(lck->lk.poll)); 338 if ((curr != 0) && (curr != gtid_code)) 339 __kmp_printf("LOCK CONTENTION: %p\n", lck); 340 /* else __kmp_printf( "." );*/ 341 #endif /* USE_LOCK_PROFILE */ 342 343 KMP_FSYNC_PREPARE(lck); 344 KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d entering\n", 345 lck, lck->lk.poll, gtid)); 346 347 kmp_int32 poll_val; 348 349 while ((poll_val = KMP_COMPARE_AND_STORE_RET32( 350 &(lck->lk.poll), KMP_LOCK_FREE(futex), 351 KMP_LOCK_BUSY(gtid_code, futex))) != KMP_LOCK_FREE(futex)) { 352 353 kmp_int32 cond = KMP_LOCK_STRIP(poll_val) & 1; 354 KA_TRACE( 355 1000, 356 ("__kmp_acquire_futex_lock: lck:%p, T#%d poll_val = 0x%x cond = 0x%x\n", 357 lck, gtid, poll_val, cond)); 358 359 // NOTE: if you try to use the following condition for this branch 360 // 361 // if ( poll_val & 1 == 0 ) 362 // 363 // Then the 12.0 compiler has a bug where the following block will 364 // always be skipped, regardless of the value of the LSB of poll_val. 365 if (!cond) { 366 // Try to set the lsb in the poll to indicate to the owner 367 // thread that they need to wake this thread up. 368 if (!KMP_COMPARE_AND_STORE_REL32(&(lck->lk.poll), poll_val, 369 poll_val | KMP_LOCK_BUSY(1, futex))) { 370 KA_TRACE( 371 1000, 372 ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d can't set bit 0\n", 373 lck, lck->lk.poll, gtid)); 374 continue; 375 } 376 poll_val |= KMP_LOCK_BUSY(1, futex); 377 378 KA_TRACE(1000, 379 ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d bit 0 set\n", lck, 380 lck->lk.poll, gtid)); 381 } 382 383 KA_TRACE( 384 1000, 385 ("__kmp_acquire_futex_lock: lck:%p, T#%d before futex_wait(0x%x)\n", 386 lck, gtid, poll_val)); 387 388 kmp_int32 rc; 389 if ((rc = syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAIT, poll_val, NULL, 390 NULL, 0)) != 0) { 391 KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p, T#%d futex_wait(0x%x) " 392 "failed (rc=%d errno=%d)\n", 393 lck, gtid, poll_val, rc, errno)); 394 continue; 395 } 396 397 KA_TRACE(1000, 398 ("__kmp_acquire_futex_lock: lck:%p, T#%d after futex_wait(0x%x)\n", 399 lck, gtid, poll_val)); 400 // This thread has now done a successful futex wait call and was entered on 401 // the OS futex queue. We must now perform a futex wake call when releasing 402 // the lock, as we have no idea how many other threads are in the queue. 403 gtid_code |= 1; 404 } 405 406 KMP_FSYNC_ACQUIRED(lck); 407 KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d exiting\n", lck, 408 lck->lk.poll, gtid)); 409 return KMP_LOCK_ACQUIRED_FIRST; 410 } 411 412 int __kmp_acquire_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { 413 int retval = __kmp_acquire_futex_lock_timed_template(lck, gtid); 414 ANNOTATE_FUTEX_ACQUIRED(lck); 415 return retval; 416 } 417 418 static int __kmp_acquire_futex_lock_with_checks(kmp_futex_lock_t *lck, 419 kmp_int32 gtid) { 420 char const *const func = "omp_set_lock"; 421 if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) && 422 __kmp_is_futex_lock_nestable(lck)) { 423 KMP_FATAL(LockNestableUsedAsSimple, func); 424 } 425 if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) == gtid)) { 426 KMP_FATAL(LockIsAlreadyOwned, func); 427 } 428 return __kmp_acquire_futex_lock(lck, gtid); 429 } 430 431 int __kmp_test_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { 432 if (KMP_COMPARE_AND_STORE_ACQ32(&(lck->lk.poll), KMP_LOCK_FREE(futex), 433 KMP_LOCK_BUSY((gtid + 1) << 1, futex))) { 434 KMP_FSYNC_ACQUIRED(lck); 435 return TRUE; 436 } 437 return FALSE; 438 } 439 440 static int __kmp_test_futex_lock_with_checks(kmp_futex_lock_t *lck, 441 kmp_int32 gtid) { 442 char const *const func = "omp_test_lock"; 443 if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) && 444 __kmp_is_futex_lock_nestable(lck)) { 445 KMP_FATAL(LockNestableUsedAsSimple, func); 446 } 447 return __kmp_test_futex_lock(lck, gtid); 448 } 449 450 int __kmp_release_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { 451 KMP_MB(); /* Flush all pending memory write invalidates. */ 452 453 KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d entering\n", 454 lck, lck->lk.poll, gtid)); 455 456 KMP_FSYNC_RELEASING(lck); 457 ANNOTATE_FUTEX_RELEASED(lck); 458 459 kmp_int32 poll_val = KMP_XCHG_FIXED32(&(lck->lk.poll), KMP_LOCK_FREE(futex)); 460 461 KA_TRACE(1000, 462 ("__kmp_release_futex_lock: lck:%p, T#%d released poll_val = 0x%x\n", 463 lck, gtid, poll_val)); 464 465 if (KMP_LOCK_STRIP(poll_val) & 1) { 466 KA_TRACE(1000, 467 ("__kmp_release_futex_lock: lck:%p, T#%d futex_wake 1 thread\n", 468 lck, gtid)); 469 syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAKE, KMP_LOCK_BUSY(1, futex), 470 NULL, NULL, 0); 471 } 472 473 KMP_MB(); /* Flush all pending memory write invalidates. */ 474 475 KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d exiting\n", lck, 476 lck->lk.poll, gtid)); 477 478 KMP_YIELD(TCR_4(__kmp_nth) > 479 (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); 480 return KMP_LOCK_RELEASED; 481 } 482 483 static int __kmp_release_futex_lock_with_checks(kmp_futex_lock_t *lck, 484 kmp_int32 gtid) { 485 char const *const func = "omp_unset_lock"; 486 KMP_MB(); /* in case another processor initialized lock */ 487 if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) && 488 __kmp_is_futex_lock_nestable(lck)) { 489 KMP_FATAL(LockNestableUsedAsSimple, func); 490 } 491 if (__kmp_get_futex_lock_owner(lck) == -1) { 492 KMP_FATAL(LockUnsettingFree, func); 493 } 494 if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) >= 0) && 495 (__kmp_get_futex_lock_owner(lck) != gtid)) { 496 KMP_FATAL(LockUnsettingSetByAnother, func); 497 } 498 return __kmp_release_futex_lock(lck, gtid); 499 } 500 501 void __kmp_init_futex_lock(kmp_futex_lock_t *lck) { 502 TCW_4(lck->lk.poll, KMP_LOCK_FREE(futex)); 503 } 504 505 void __kmp_destroy_futex_lock(kmp_futex_lock_t *lck) { lck->lk.poll = 0; } 506 507 static void __kmp_destroy_futex_lock_with_checks(kmp_futex_lock_t *lck) { 508 char const *const func = "omp_destroy_lock"; 509 if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) && 510 __kmp_is_futex_lock_nestable(lck)) { 511 KMP_FATAL(LockNestableUsedAsSimple, func); 512 } 513 if (__kmp_get_futex_lock_owner(lck) != -1) { 514 KMP_FATAL(LockStillOwned, func); 515 } 516 __kmp_destroy_futex_lock(lck); 517 } 518 519 // nested futex locks 520 521 int __kmp_acquire_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { 522 KMP_DEBUG_ASSERT(gtid >= 0); 523 524 if (__kmp_get_futex_lock_owner(lck) == gtid) { 525 lck->lk.depth_locked += 1; 526 return KMP_LOCK_ACQUIRED_NEXT; 527 } else { 528 __kmp_acquire_futex_lock_timed_template(lck, gtid); 529 ANNOTATE_FUTEX_ACQUIRED(lck); 530 lck->lk.depth_locked = 1; 531 return KMP_LOCK_ACQUIRED_FIRST; 532 } 533 } 534 535 static int __kmp_acquire_nested_futex_lock_with_checks(kmp_futex_lock_t *lck, 536 kmp_int32 gtid) { 537 char const *const func = "omp_set_nest_lock"; 538 if (!__kmp_is_futex_lock_nestable(lck)) { 539 KMP_FATAL(LockSimpleUsedAsNestable, func); 540 } 541 return __kmp_acquire_nested_futex_lock(lck, gtid); 542 } 543 544 int __kmp_test_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { 545 int retval; 546 547 KMP_DEBUG_ASSERT(gtid >= 0); 548 549 if (__kmp_get_futex_lock_owner(lck) == gtid) { 550 retval = ++lck->lk.depth_locked; 551 } else if (!__kmp_test_futex_lock(lck, gtid)) { 552 retval = 0; 553 } else { 554 KMP_MB(); 555 retval = lck->lk.depth_locked = 1; 556 } 557 return retval; 558 } 559 560 static int __kmp_test_nested_futex_lock_with_checks(kmp_futex_lock_t *lck, 561 kmp_int32 gtid) { 562 char const *const func = "omp_test_nest_lock"; 563 if (!__kmp_is_futex_lock_nestable(lck)) { 564 KMP_FATAL(LockSimpleUsedAsNestable, func); 565 } 566 return __kmp_test_nested_futex_lock(lck, gtid); 567 } 568 569 int __kmp_release_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { 570 KMP_DEBUG_ASSERT(gtid >= 0); 571 572 KMP_MB(); 573 if (--(lck->lk.depth_locked) == 0) { 574 __kmp_release_futex_lock(lck, gtid); 575 return KMP_LOCK_RELEASED; 576 } 577 return KMP_LOCK_STILL_HELD; 578 } 579 580 static int __kmp_release_nested_futex_lock_with_checks(kmp_futex_lock_t *lck, 581 kmp_int32 gtid) { 582 char const *const func = "omp_unset_nest_lock"; 583 KMP_MB(); /* in case another processor initialized lock */ 584 if (!__kmp_is_futex_lock_nestable(lck)) { 585 KMP_FATAL(LockSimpleUsedAsNestable, func); 586 } 587 if (__kmp_get_futex_lock_owner(lck) == -1) { 588 KMP_FATAL(LockUnsettingFree, func); 589 } 590 if (__kmp_get_futex_lock_owner(lck) != gtid) { 591 KMP_FATAL(LockUnsettingSetByAnother, func); 592 } 593 return __kmp_release_nested_futex_lock(lck, gtid); 594 } 595 596 void __kmp_init_nested_futex_lock(kmp_futex_lock_t *lck) { 597 __kmp_init_futex_lock(lck); 598 lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks 599 } 600 601 void __kmp_destroy_nested_futex_lock(kmp_futex_lock_t *lck) { 602 __kmp_destroy_futex_lock(lck); 603 lck->lk.depth_locked = 0; 604 } 605 606 static void __kmp_destroy_nested_futex_lock_with_checks(kmp_futex_lock_t *lck) { 607 char const *const func = "omp_destroy_nest_lock"; 608 if (!__kmp_is_futex_lock_nestable(lck)) { 609 KMP_FATAL(LockSimpleUsedAsNestable, func); 610 } 611 if (__kmp_get_futex_lock_owner(lck) != -1) { 612 KMP_FATAL(LockStillOwned, func); 613 } 614 __kmp_destroy_nested_futex_lock(lck); 615 } 616 617 #endif // KMP_USE_FUTEX 618 619 /* ------------------------------------------------------------------------ */ 620 /* ticket (bakery) locks */ 621 622 static kmp_int32 __kmp_get_ticket_lock_owner(kmp_ticket_lock_t *lck) { 623 return std::atomic_load_explicit(&lck->lk.owner_id, 624 std::memory_order_relaxed) - 625 1; 626 } 627 628 static inline bool __kmp_is_ticket_lock_nestable(kmp_ticket_lock_t *lck) { 629 return std::atomic_load_explicit(&lck->lk.depth_locked, 630 std::memory_order_relaxed) != -1; 631 } 632 633 static kmp_uint32 __kmp_bakery_check(void *now_serving, kmp_uint32 my_ticket) { 634 return std::atomic_load_explicit((std::atomic<unsigned> *)now_serving, 635 std::memory_order_acquire) == my_ticket; 636 } 637 638 __forceinline static int 639 __kmp_acquire_ticket_lock_timed_template(kmp_ticket_lock_t *lck, 640 kmp_int32 gtid) { 641 kmp_uint32 my_ticket = std::atomic_fetch_add_explicit( 642 &lck->lk.next_ticket, 1U, std::memory_order_relaxed); 643 644 #ifdef USE_LOCK_PROFILE 645 if (std::atomic_load_explicit(&lck->lk.now_serving, 646 std::memory_order_relaxed) != my_ticket) 647 __kmp_printf("LOCK CONTENTION: %p\n", lck); 648 /* else __kmp_printf( "." );*/ 649 #endif /* USE_LOCK_PROFILE */ 650 651 if (std::atomic_load_explicit(&lck->lk.now_serving, 652 std::memory_order_acquire) == my_ticket) { 653 return KMP_LOCK_ACQUIRED_FIRST; 654 } 655 KMP_WAIT_YIELD_PTR(&lck->lk.now_serving, my_ticket, __kmp_bakery_check, lck); 656 return KMP_LOCK_ACQUIRED_FIRST; 657 } 658 659 int __kmp_acquire_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { 660 int retval = __kmp_acquire_ticket_lock_timed_template(lck, gtid); 661 ANNOTATE_TICKET_ACQUIRED(lck); 662 return retval; 663 } 664 665 static int __kmp_acquire_ticket_lock_with_checks(kmp_ticket_lock_t *lck, 666 kmp_int32 gtid) { 667 char const *const func = "omp_set_lock"; 668 669 if (!std::atomic_load_explicit(&lck->lk.initialized, 670 std::memory_order_relaxed)) { 671 KMP_FATAL(LockIsUninitialized, func); 672 } 673 if (lck->lk.self != lck) { 674 KMP_FATAL(LockIsUninitialized, func); 675 } 676 if (__kmp_is_ticket_lock_nestable(lck)) { 677 KMP_FATAL(LockNestableUsedAsSimple, func); 678 } 679 if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) == gtid)) { 680 KMP_FATAL(LockIsAlreadyOwned, func); 681 } 682 683 __kmp_acquire_ticket_lock(lck, gtid); 684 685 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1, 686 std::memory_order_relaxed); 687 return KMP_LOCK_ACQUIRED_FIRST; 688 } 689 690 int __kmp_test_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { 691 kmp_uint32 my_ticket = std::atomic_load_explicit(&lck->lk.next_ticket, 692 std::memory_order_relaxed); 693 694 if (std::atomic_load_explicit(&lck->lk.now_serving, 695 std::memory_order_relaxed) == my_ticket) { 696 kmp_uint32 next_ticket = my_ticket + 1; 697 if (std::atomic_compare_exchange_strong_explicit( 698 &lck->lk.next_ticket, &my_ticket, next_ticket, 699 std::memory_order_acquire, std::memory_order_acquire)) { 700 return TRUE; 701 } 702 } 703 return FALSE; 704 } 705 706 static int __kmp_test_ticket_lock_with_checks(kmp_ticket_lock_t *lck, 707 kmp_int32 gtid) { 708 char const *const func = "omp_test_lock"; 709 710 if (!std::atomic_load_explicit(&lck->lk.initialized, 711 std::memory_order_relaxed)) { 712 KMP_FATAL(LockIsUninitialized, func); 713 } 714 if (lck->lk.self != lck) { 715 KMP_FATAL(LockIsUninitialized, func); 716 } 717 if (__kmp_is_ticket_lock_nestable(lck)) { 718 KMP_FATAL(LockNestableUsedAsSimple, func); 719 } 720 721 int retval = __kmp_test_ticket_lock(lck, gtid); 722 723 if (retval) { 724 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1, 725 std::memory_order_relaxed); 726 } 727 return retval; 728 } 729 730 int __kmp_release_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { 731 kmp_uint32 distance = std::atomic_load_explicit(&lck->lk.next_ticket, 732 std::memory_order_relaxed) - 733 std::atomic_load_explicit(&lck->lk.now_serving, 734 std::memory_order_relaxed); 735 736 ANNOTATE_TICKET_RELEASED(lck); 737 std::atomic_fetch_add_explicit(&lck->lk.now_serving, 1U, 738 std::memory_order_release); 739 740 KMP_YIELD(distance > 741 (kmp_uint32)(__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); 742 return KMP_LOCK_RELEASED; 743 } 744 745 static int __kmp_release_ticket_lock_with_checks(kmp_ticket_lock_t *lck, 746 kmp_int32 gtid) { 747 char const *const func = "omp_unset_lock"; 748 749 if (!std::atomic_load_explicit(&lck->lk.initialized, 750 std::memory_order_relaxed)) { 751 KMP_FATAL(LockIsUninitialized, func); 752 } 753 if (lck->lk.self != lck) { 754 KMP_FATAL(LockIsUninitialized, func); 755 } 756 if (__kmp_is_ticket_lock_nestable(lck)) { 757 KMP_FATAL(LockNestableUsedAsSimple, func); 758 } 759 if (__kmp_get_ticket_lock_owner(lck) == -1) { 760 KMP_FATAL(LockUnsettingFree, func); 761 } 762 if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) >= 0) && 763 (__kmp_get_ticket_lock_owner(lck) != gtid)) { 764 KMP_FATAL(LockUnsettingSetByAnother, func); 765 } 766 std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed); 767 return __kmp_release_ticket_lock(lck, gtid); 768 } 769 770 void __kmp_init_ticket_lock(kmp_ticket_lock_t *lck) { 771 lck->lk.location = NULL; 772 lck->lk.self = lck; 773 std::atomic_store_explicit(&lck->lk.next_ticket, 0U, 774 std::memory_order_relaxed); 775 std::atomic_store_explicit(&lck->lk.now_serving, 0U, 776 std::memory_order_relaxed); 777 std::atomic_store_explicit( 778 &lck->lk.owner_id, 0, 779 std::memory_order_relaxed); // no thread owns the lock. 780 std::atomic_store_explicit( 781 &lck->lk.depth_locked, -1, 782 std::memory_order_relaxed); // -1 => not a nested lock. 783 std::atomic_store_explicit(&lck->lk.initialized, true, 784 std::memory_order_release); 785 } 786 787 void __kmp_destroy_ticket_lock(kmp_ticket_lock_t *lck) { 788 std::atomic_store_explicit(&lck->lk.initialized, false, 789 std::memory_order_release); 790 lck->lk.self = NULL; 791 lck->lk.location = NULL; 792 std::atomic_store_explicit(&lck->lk.next_ticket, 0U, 793 std::memory_order_relaxed); 794 std::atomic_store_explicit(&lck->lk.now_serving, 0U, 795 std::memory_order_relaxed); 796 std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed); 797 std::atomic_store_explicit(&lck->lk.depth_locked, -1, 798 std::memory_order_relaxed); 799 } 800 801 static void __kmp_destroy_ticket_lock_with_checks(kmp_ticket_lock_t *lck) { 802 char const *const func = "omp_destroy_lock"; 803 804 if (!std::atomic_load_explicit(&lck->lk.initialized, 805 std::memory_order_relaxed)) { 806 KMP_FATAL(LockIsUninitialized, func); 807 } 808 if (lck->lk.self != lck) { 809 KMP_FATAL(LockIsUninitialized, func); 810 } 811 if (__kmp_is_ticket_lock_nestable(lck)) { 812 KMP_FATAL(LockNestableUsedAsSimple, func); 813 } 814 if (__kmp_get_ticket_lock_owner(lck) != -1) { 815 KMP_FATAL(LockStillOwned, func); 816 } 817 __kmp_destroy_ticket_lock(lck); 818 } 819 820 // nested ticket locks 821 822 int __kmp_acquire_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { 823 KMP_DEBUG_ASSERT(gtid >= 0); 824 825 if (__kmp_get_ticket_lock_owner(lck) == gtid) { 826 std::atomic_fetch_add_explicit(&lck->lk.depth_locked, 1, 827 std::memory_order_relaxed); 828 return KMP_LOCK_ACQUIRED_NEXT; 829 } else { 830 __kmp_acquire_ticket_lock_timed_template(lck, gtid); 831 ANNOTATE_TICKET_ACQUIRED(lck); 832 std::atomic_store_explicit(&lck->lk.depth_locked, 1, 833 std::memory_order_relaxed); 834 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1, 835 std::memory_order_relaxed); 836 return KMP_LOCK_ACQUIRED_FIRST; 837 } 838 } 839 840 static int __kmp_acquire_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck, 841 kmp_int32 gtid) { 842 char const *const func = "omp_set_nest_lock"; 843 844 if (!std::atomic_load_explicit(&lck->lk.initialized, 845 std::memory_order_relaxed)) { 846 KMP_FATAL(LockIsUninitialized, func); 847 } 848 if (lck->lk.self != lck) { 849 KMP_FATAL(LockIsUninitialized, func); 850 } 851 if (!__kmp_is_ticket_lock_nestable(lck)) { 852 KMP_FATAL(LockSimpleUsedAsNestable, func); 853 } 854 return __kmp_acquire_nested_ticket_lock(lck, gtid); 855 } 856 857 int __kmp_test_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { 858 int retval; 859 860 KMP_DEBUG_ASSERT(gtid >= 0); 861 862 if (__kmp_get_ticket_lock_owner(lck) == gtid) { 863 retval = std::atomic_fetch_add_explicit(&lck->lk.depth_locked, 1, 864 std::memory_order_relaxed) + 865 1; 866 } else if (!__kmp_test_ticket_lock(lck, gtid)) { 867 retval = 0; 868 } else { 869 std::atomic_store_explicit(&lck->lk.depth_locked, 1, 870 std::memory_order_relaxed); 871 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1, 872 std::memory_order_relaxed); 873 retval = 1; 874 } 875 return retval; 876 } 877 878 static int __kmp_test_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck, 879 kmp_int32 gtid) { 880 char const *const func = "omp_test_nest_lock"; 881 882 if (!std::atomic_load_explicit(&lck->lk.initialized, 883 std::memory_order_relaxed)) { 884 KMP_FATAL(LockIsUninitialized, func); 885 } 886 if (lck->lk.self != lck) { 887 KMP_FATAL(LockIsUninitialized, func); 888 } 889 if (!__kmp_is_ticket_lock_nestable(lck)) { 890 KMP_FATAL(LockSimpleUsedAsNestable, func); 891 } 892 return __kmp_test_nested_ticket_lock(lck, gtid); 893 } 894 895 int __kmp_release_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { 896 KMP_DEBUG_ASSERT(gtid >= 0); 897 898 if ((std::atomic_fetch_add_explicit(&lck->lk.depth_locked, -1, 899 std::memory_order_relaxed) - 900 1) == 0) { 901 std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed); 902 __kmp_release_ticket_lock(lck, gtid); 903 return KMP_LOCK_RELEASED; 904 } 905 return KMP_LOCK_STILL_HELD; 906 } 907 908 static int __kmp_release_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck, 909 kmp_int32 gtid) { 910 char const *const func = "omp_unset_nest_lock"; 911 912 if (!std::atomic_load_explicit(&lck->lk.initialized, 913 std::memory_order_relaxed)) { 914 KMP_FATAL(LockIsUninitialized, func); 915 } 916 if (lck->lk.self != lck) { 917 KMP_FATAL(LockIsUninitialized, func); 918 } 919 if (!__kmp_is_ticket_lock_nestable(lck)) { 920 KMP_FATAL(LockSimpleUsedAsNestable, func); 921 } 922 if (__kmp_get_ticket_lock_owner(lck) == -1) { 923 KMP_FATAL(LockUnsettingFree, func); 924 } 925 if (__kmp_get_ticket_lock_owner(lck) != gtid) { 926 KMP_FATAL(LockUnsettingSetByAnother, func); 927 } 928 return __kmp_release_nested_ticket_lock(lck, gtid); 929 } 930 931 void __kmp_init_nested_ticket_lock(kmp_ticket_lock_t *lck) { 932 __kmp_init_ticket_lock(lck); 933 std::atomic_store_explicit(&lck->lk.depth_locked, 0, 934 std::memory_order_relaxed); 935 // >= 0 for nestable locks, -1 for simple locks 936 } 937 938 void __kmp_destroy_nested_ticket_lock(kmp_ticket_lock_t *lck) { 939 __kmp_destroy_ticket_lock(lck); 940 std::atomic_store_explicit(&lck->lk.depth_locked, 0, 941 std::memory_order_relaxed); 942 } 943 944 static void 945 __kmp_destroy_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck) { 946 char const *const func = "omp_destroy_nest_lock"; 947 948 if (!std::atomic_load_explicit(&lck->lk.initialized, 949 std::memory_order_relaxed)) { 950 KMP_FATAL(LockIsUninitialized, func); 951 } 952 if (lck->lk.self != lck) { 953 KMP_FATAL(LockIsUninitialized, func); 954 } 955 if (!__kmp_is_ticket_lock_nestable(lck)) { 956 KMP_FATAL(LockSimpleUsedAsNestable, func); 957 } 958 if (__kmp_get_ticket_lock_owner(lck) != -1) { 959 KMP_FATAL(LockStillOwned, func); 960 } 961 __kmp_destroy_nested_ticket_lock(lck); 962 } 963 964 // access functions to fields which don't exist for all lock kinds. 965 966 static const ident_t *__kmp_get_ticket_lock_location(kmp_ticket_lock_t *lck) { 967 return lck->lk.location; 968 } 969 970 static void __kmp_set_ticket_lock_location(kmp_ticket_lock_t *lck, 971 const ident_t *loc) { 972 lck->lk.location = loc; 973 } 974 975 static kmp_lock_flags_t __kmp_get_ticket_lock_flags(kmp_ticket_lock_t *lck) { 976 return lck->lk.flags; 977 } 978 979 static void __kmp_set_ticket_lock_flags(kmp_ticket_lock_t *lck, 980 kmp_lock_flags_t flags) { 981 lck->lk.flags = flags; 982 } 983 984 /* ------------------------------------------------------------------------ */ 985 /* queuing locks */ 986 987 /* First the states 988 (head,tail) = 0, 0 means lock is unheld, nobody on queue 989 UINT_MAX or -1, 0 means lock is held, nobody on queue 990 h, h means lock held or about to transition, 991 1 element on queue 992 h, t h <> t, means lock is held or about to 993 transition, >1 elements on queue 994 995 Now the transitions 996 Acquire(0,0) = -1 ,0 997 Release(0,0) = Error 998 Acquire(-1,0) = h ,h h > 0 999 Release(-1,0) = 0 ,0 1000 Acquire(h,h) = h ,t h > 0, t > 0, h <> t 1001 Release(h,h) = -1 ,0 h > 0 1002 Acquire(h,t) = h ,t' h > 0, t > 0, t' > 0, h <> t, h <> t', t <> t' 1003 Release(h,t) = h',t h > 0, t > 0, h <> t, h <> h', h' maybe = t 1004 1005 And pictorially 1006 1007 +-----+ 1008 | 0, 0|------- release -------> Error 1009 +-----+ 1010 | ^ 1011 acquire| |release 1012 | | 1013 | | 1014 v | 1015 +-----+ 1016 |-1, 0| 1017 +-----+ 1018 | ^ 1019 acquire| |release 1020 | | 1021 | | 1022 v | 1023 +-----+ 1024 | h, h| 1025 +-----+ 1026 | ^ 1027 acquire| |release 1028 | | 1029 | | 1030 v | 1031 +-----+ 1032 | h, t|----- acquire, release loopback ---+ 1033 +-----+ | 1034 ^ | 1035 | | 1036 +------------------------------------+ 1037 */ 1038 1039 #ifdef DEBUG_QUEUING_LOCKS 1040 1041 /* Stuff for circular trace buffer */ 1042 #define TRACE_BUF_ELE 1024 1043 static char traces[TRACE_BUF_ELE][128] = {0}; 1044 static int tc = 0; 1045 #define TRACE_LOCK(X, Y) \ 1046 KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s\n", X, Y); 1047 #define TRACE_LOCK_T(X, Y, Z) \ 1048 KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s%d\n", X, Y, Z); 1049 #define TRACE_LOCK_HT(X, Y, Z, Q) \ 1050 KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s %d,%d\n", X, Y, \ 1051 Z, Q); 1052 1053 static void __kmp_dump_queuing_lock(kmp_info_t *this_thr, kmp_int32 gtid, 1054 kmp_queuing_lock_t *lck, kmp_int32 head_id, 1055 kmp_int32 tail_id) { 1056 kmp_int32 t, i; 1057 1058 __kmp_printf_no_lock("\n__kmp_dump_queuing_lock: TRACE BEGINS HERE! \n"); 1059 1060 i = tc % TRACE_BUF_ELE; 1061 __kmp_printf_no_lock("%s\n", traces[i]); 1062 i = (i + 1) % TRACE_BUF_ELE; 1063 while (i != (tc % TRACE_BUF_ELE)) { 1064 __kmp_printf_no_lock("%s", traces[i]); 1065 i = (i + 1) % TRACE_BUF_ELE; 1066 } 1067 __kmp_printf_no_lock("\n"); 1068 1069 __kmp_printf_no_lock("\n__kmp_dump_queuing_lock: gtid+1:%d, spin_here:%d, " 1070 "next_wait:%d, head_id:%d, tail_id:%d\n", 1071 gtid + 1, this_thr->th.th_spin_here, 1072 this_thr->th.th_next_waiting, head_id, tail_id); 1073 1074 __kmp_printf_no_lock("\t\thead: %d ", lck->lk.head_id); 1075 1076 if (lck->lk.head_id >= 1) { 1077 t = __kmp_threads[lck->lk.head_id - 1]->th.th_next_waiting; 1078 while (t > 0) { 1079 __kmp_printf_no_lock("-> %d ", t); 1080 t = __kmp_threads[t - 1]->th.th_next_waiting; 1081 } 1082 } 1083 __kmp_printf_no_lock("; tail: %d ", lck->lk.tail_id); 1084 __kmp_printf_no_lock("\n\n"); 1085 } 1086 1087 #endif /* DEBUG_QUEUING_LOCKS */ 1088 1089 static kmp_int32 __kmp_get_queuing_lock_owner(kmp_queuing_lock_t *lck) { 1090 return TCR_4(lck->lk.owner_id) - 1; 1091 } 1092 1093 static inline bool __kmp_is_queuing_lock_nestable(kmp_queuing_lock_t *lck) { 1094 return lck->lk.depth_locked != -1; 1095 } 1096 1097 /* Acquire a lock using a the queuing lock implementation */ 1098 template <bool takeTime> 1099 /* [TLW] The unused template above is left behind because of what BEB believes 1100 is a potential compiler problem with __forceinline. */ 1101 __forceinline static int 1102 __kmp_acquire_queuing_lock_timed_template(kmp_queuing_lock_t *lck, 1103 kmp_int32 gtid) { 1104 kmp_info_t *this_thr = __kmp_thread_from_gtid(gtid); 1105 volatile kmp_int32 *head_id_p = &lck->lk.head_id; 1106 volatile kmp_int32 *tail_id_p = &lck->lk.tail_id; 1107 volatile kmp_uint32 *spin_here_p; 1108 kmp_int32 need_mf = 1; 1109 1110 #if OMPT_SUPPORT 1111 ompt_state_t prev_state = ompt_state_undefined; 1112 #endif 1113 1114 KA_TRACE(1000, 1115 ("__kmp_acquire_queuing_lock: lck:%p, T#%d entering\n", lck, gtid)); 1116 1117 KMP_FSYNC_PREPARE(lck); 1118 KMP_DEBUG_ASSERT(this_thr != NULL); 1119 spin_here_p = &this_thr->th.th_spin_here; 1120 1121 #ifdef DEBUG_QUEUING_LOCKS 1122 TRACE_LOCK(gtid + 1, "acq ent"); 1123 if (*spin_here_p) 1124 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); 1125 if (this_thr->th.th_next_waiting != 0) 1126 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); 1127 #endif 1128 KMP_DEBUG_ASSERT(!*spin_here_p); 1129 KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0); 1130 1131 /* The following st.rel to spin_here_p needs to precede the cmpxchg.acq to 1132 head_id_p that may follow, not just in execution order, but also in 1133 visibility order. This way, when a releasing thread observes the changes to 1134 the queue by this thread, it can rightly assume that spin_here_p has 1135 already been set to TRUE, so that when it sets spin_here_p to FALSE, it is 1136 not premature. If the releasing thread sets spin_here_p to FALSE before 1137 this thread sets it to TRUE, this thread will hang. */ 1138 *spin_here_p = TRUE; /* before enqueuing to prevent race */ 1139 1140 while (1) { 1141 kmp_int32 enqueued; 1142 kmp_int32 head; 1143 kmp_int32 tail; 1144 1145 head = *head_id_p; 1146 1147 switch (head) { 1148 1149 case -1: { 1150 #ifdef DEBUG_QUEUING_LOCKS 1151 tail = *tail_id_p; 1152 TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail); 1153 #endif 1154 tail = 0; /* to make sure next link asynchronously read is not set 1155 accidentally; this assignment prevents us from entering the 1156 if ( t > 0 ) condition in the enqueued case below, which is not 1157 necessary for this state transition */ 1158 1159 need_mf = 0; 1160 /* try (-1,0)->(tid,tid) */ 1161 enqueued = KMP_COMPARE_AND_STORE_ACQ64((volatile kmp_int64 *)tail_id_p, 1162 KMP_PACK_64(-1, 0), 1163 KMP_PACK_64(gtid + 1, gtid + 1)); 1164 #ifdef DEBUG_QUEUING_LOCKS 1165 if (enqueued) 1166 TRACE_LOCK(gtid + 1, "acq enq: (-1,0)->(tid,tid)"); 1167 #endif 1168 } break; 1169 1170 default: { 1171 tail = *tail_id_p; 1172 KMP_DEBUG_ASSERT(tail != gtid + 1); 1173 1174 #ifdef DEBUG_QUEUING_LOCKS 1175 TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail); 1176 #endif 1177 1178 if (tail == 0) { 1179 enqueued = FALSE; 1180 } else { 1181 need_mf = 0; 1182 /* try (h,t) or (h,h)->(h,tid) */ 1183 enqueued = KMP_COMPARE_AND_STORE_ACQ32(tail_id_p, tail, gtid + 1); 1184 1185 #ifdef DEBUG_QUEUING_LOCKS 1186 if (enqueued) 1187 TRACE_LOCK(gtid + 1, "acq enq: (h,t)->(h,tid)"); 1188 #endif 1189 } 1190 } break; 1191 1192 case 0: /* empty queue */ 1193 { 1194 kmp_int32 grabbed_lock; 1195 1196 #ifdef DEBUG_QUEUING_LOCKS 1197 tail = *tail_id_p; 1198 TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail); 1199 #endif 1200 /* try (0,0)->(-1,0) */ 1201 1202 /* only legal transition out of head = 0 is head = -1 with no change to 1203 * tail */ 1204 grabbed_lock = KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1); 1205 1206 if (grabbed_lock) { 1207 1208 *spin_here_p = FALSE; 1209 1210 KA_TRACE( 1211 1000, 1212 ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: no queuing\n", 1213 lck, gtid)); 1214 #ifdef DEBUG_QUEUING_LOCKS 1215 TRACE_LOCK_HT(gtid + 1, "acq exit: ", head, 0); 1216 #endif 1217 1218 #if OMPT_SUPPORT 1219 if (ompt_enabled.enabled && prev_state != ompt_state_undefined) { 1220 /* change the state before clearing wait_id */ 1221 this_thr->th.ompt_thread_info.state = prev_state; 1222 this_thr->th.ompt_thread_info.wait_id = 0; 1223 } 1224 #endif 1225 1226 KMP_FSYNC_ACQUIRED(lck); 1227 return KMP_LOCK_ACQUIRED_FIRST; /* lock holder cannot be on queue */ 1228 } 1229 enqueued = FALSE; 1230 } break; 1231 } 1232 1233 #if OMPT_SUPPORT 1234 if (ompt_enabled.enabled && prev_state == ompt_state_undefined) { 1235 /* this thread will spin; set wait_id before entering wait state */ 1236 prev_state = this_thr->th.ompt_thread_info.state; 1237 this_thr->th.ompt_thread_info.wait_id = (uint64_t)lck; 1238 this_thr->th.ompt_thread_info.state = ompt_state_wait_lock; 1239 } 1240 #endif 1241 1242 if (enqueued) { 1243 if (tail > 0) { 1244 kmp_info_t *tail_thr = __kmp_thread_from_gtid(tail - 1); 1245 KMP_ASSERT(tail_thr != NULL); 1246 tail_thr->th.th_next_waiting = gtid + 1; 1247 /* corresponding wait for this write in release code */ 1248 } 1249 KA_TRACE(1000, 1250 ("__kmp_acquire_queuing_lock: lck:%p, T#%d waiting for lock\n", 1251 lck, gtid)); 1252 1253 /* ToDo: May want to consider using __kmp_wait_sleep or something that 1254 sleeps for throughput only here. */ 1255 KMP_MB(); 1256 KMP_WAIT_YIELD(spin_here_p, FALSE, KMP_EQ, lck); 1257 1258 #ifdef DEBUG_QUEUING_LOCKS 1259 TRACE_LOCK(gtid + 1, "acq spin"); 1260 1261 if (this_thr->th.th_next_waiting != 0) 1262 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); 1263 #endif 1264 KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0); 1265 KA_TRACE(1000, ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: after " 1266 "waiting on queue\n", 1267 lck, gtid)); 1268 1269 #ifdef DEBUG_QUEUING_LOCKS 1270 TRACE_LOCK(gtid + 1, "acq exit 2"); 1271 #endif 1272 1273 #if OMPT_SUPPORT 1274 /* change the state before clearing wait_id */ 1275 this_thr->th.ompt_thread_info.state = prev_state; 1276 this_thr->th.ompt_thread_info.wait_id = 0; 1277 #endif 1278 1279 /* got lock, we were dequeued by the thread that released lock */ 1280 return KMP_LOCK_ACQUIRED_FIRST; 1281 } 1282 1283 /* Yield if number of threads > number of logical processors */ 1284 /* ToDo: Not sure why this should only be in oversubscription case, 1285 maybe should be traditional YIELD_INIT/YIELD_WHEN loop */ 1286 KMP_YIELD(TCR_4(__kmp_nth) > 1287 (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); 1288 #ifdef DEBUG_QUEUING_LOCKS 1289 TRACE_LOCK(gtid + 1, "acq retry"); 1290 #endif 1291 } 1292 KMP_ASSERT2(0, "should not get here"); 1293 return KMP_LOCK_ACQUIRED_FIRST; 1294 } 1295 1296 int __kmp_acquire_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { 1297 KMP_DEBUG_ASSERT(gtid >= 0); 1298 1299 int retval = __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid); 1300 ANNOTATE_QUEUING_ACQUIRED(lck); 1301 return retval; 1302 } 1303 1304 static int __kmp_acquire_queuing_lock_with_checks(kmp_queuing_lock_t *lck, 1305 kmp_int32 gtid) { 1306 char const *const func = "omp_set_lock"; 1307 if (lck->lk.initialized != lck) { 1308 KMP_FATAL(LockIsUninitialized, func); 1309 } 1310 if (__kmp_is_queuing_lock_nestable(lck)) { 1311 KMP_FATAL(LockNestableUsedAsSimple, func); 1312 } 1313 if (__kmp_get_queuing_lock_owner(lck) == gtid) { 1314 KMP_FATAL(LockIsAlreadyOwned, func); 1315 } 1316 1317 __kmp_acquire_queuing_lock(lck, gtid); 1318 1319 lck->lk.owner_id = gtid + 1; 1320 return KMP_LOCK_ACQUIRED_FIRST; 1321 } 1322 1323 int __kmp_test_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { 1324 volatile kmp_int32 *head_id_p = &lck->lk.head_id; 1325 kmp_int32 head; 1326 #ifdef KMP_DEBUG 1327 kmp_info_t *this_thr; 1328 #endif 1329 1330 KA_TRACE(1000, ("__kmp_test_queuing_lock: T#%d entering\n", gtid)); 1331 KMP_DEBUG_ASSERT(gtid >= 0); 1332 #ifdef KMP_DEBUG 1333 this_thr = __kmp_thread_from_gtid(gtid); 1334 KMP_DEBUG_ASSERT(this_thr != NULL); 1335 KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here); 1336 #endif 1337 1338 head = *head_id_p; 1339 1340 if (head == 0) { /* nobody on queue, nobody holding */ 1341 /* try (0,0)->(-1,0) */ 1342 if (KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1)) { 1343 KA_TRACE(1000, 1344 ("__kmp_test_queuing_lock: T#%d exiting: holding lock\n", gtid)); 1345 KMP_FSYNC_ACQUIRED(lck); 1346 ANNOTATE_QUEUING_ACQUIRED(lck); 1347 return TRUE; 1348 } 1349 } 1350 1351 KA_TRACE(1000, 1352 ("__kmp_test_queuing_lock: T#%d exiting: without lock\n", gtid)); 1353 return FALSE; 1354 } 1355 1356 static int __kmp_test_queuing_lock_with_checks(kmp_queuing_lock_t *lck, 1357 kmp_int32 gtid) { 1358 char const *const func = "omp_test_lock"; 1359 if (lck->lk.initialized != lck) { 1360 KMP_FATAL(LockIsUninitialized, func); 1361 } 1362 if (__kmp_is_queuing_lock_nestable(lck)) { 1363 KMP_FATAL(LockNestableUsedAsSimple, func); 1364 } 1365 1366 int retval = __kmp_test_queuing_lock(lck, gtid); 1367 1368 if (retval) { 1369 lck->lk.owner_id = gtid + 1; 1370 } 1371 return retval; 1372 } 1373 1374 int __kmp_release_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { 1375 kmp_info_t *this_thr; 1376 volatile kmp_int32 *head_id_p = &lck->lk.head_id; 1377 volatile kmp_int32 *tail_id_p = &lck->lk.tail_id; 1378 1379 KA_TRACE(1000, 1380 ("__kmp_release_queuing_lock: lck:%p, T#%d entering\n", lck, gtid)); 1381 KMP_DEBUG_ASSERT(gtid >= 0); 1382 this_thr = __kmp_thread_from_gtid(gtid); 1383 KMP_DEBUG_ASSERT(this_thr != NULL); 1384 #ifdef DEBUG_QUEUING_LOCKS 1385 TRACE_LOCK(gtid + 1, "rel ent"); 1386 1387 if (this_thr->th.th_spin_here) 1388 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); 1389 if (this_thr->th.th_next_waiting != 0) 1390 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); 1391 #endif 1392 KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here); 1393 KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0); 1394 1395 KMP_FSYNC_RELEASING(lck); 1396 ANNOTATE_QUEUING_RELEASED(lck); 1397 1398 while (1) { 1399 kmp_int32 dequeued; 1400 kmp_int32 head; 1401 kmp_int32 tail; 1402 1403 head = *head_id_p; 1404 1405 #ifdef DEBUG_QUEUING_LOCKS 1406 tail = *tail_id_p; 1407 TRACE_LOCK_HT(gtid + 1, "rel read: ", head, tail); 1408 if (head == 0) 1409 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail); 1410 #endif 1411 KMP_DEBUG_ASSERT(head != 1412 0); /* holding the lock, head must be -1 or queue head */ 1413 1414 if (head == -1) { /* nobody on queue */ 1415 /* try (-1,0)->(0,0) */ 1416 if (KMP_COMPARE_AND_STORE_REL32(head_id_p, -1, 0)) { 1417 KA_TRACE( 1418 1000, 1419 ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: queue empty\n", 1420 lck, gtid)); 1421 #ifdef DEBUG_QUEUING_LOCKS 1422 TRACE_LOCK_HT(gtid + 1, "rel exit: ", 0, 0); 1423 #endif 1424 1425 #if OMPT_SUPPORT 1426 /* nothing to do - no other thread is trying to shift blame */ 1427 #endif 1428 return KMP_LOCK_RELEASED; 1429 } 1430 dequeued = FALSE; 1431 } else { 1432 KMP_MB(); 1433 tail = *tail_id_p; 1434 if (head == tail) { /* only one thread on the queue */ 1435 #ifdef DEBUG_QUEUING_LOCKS 1436 if (head <= 0) 1437 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail); 1438 #endif 1439 KMP_DEBUG_ASSERT(head > 0); 1440 1441 /* try (h,h)->(-1,0) */ 1442 dequeued = KMP_COMPARE_AND_STORE_REL64( 1443 RCAST(volatile kmp_int64 *, tail_id_p), KMP_PACK_64(head, head), 1444 KMP_PACK_64(-1, 0)); 1445 #ifdef DEBUG_QUEUING_LOCKS 1446 TRACE_LOCK(gtid + 1, "rel deq: (h,h)->(-1,0)"); 1447 #endif 1448 1449 } else { 1450 volatile kmp_int32 *waiting_id_p; 1451 kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1); 1452 KMP_DEBUG_ASSERT(head_thr != NULL); 1453 waiting_id_p = &head_thr->th.th_next_waiting; 1454 1455 /* Does this require synchronous reads? */ 1456 #ifdef DEBUG_QUEUING_LOCKS 1457 if (head <= 0 || tail <= 0) 1458 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail); 1459 #endif 1460 KMP_DEBUG_ASSERT(head > 0 && tail > 0); 1461 1462 /* try (h,t)->(h',t) or (t,t) */ 1463 KMP_MB(); 1464 /* make sure enqueuing thread has time to update next waiting thread 1465 * field */ 1466 *head_id_p = KMP_WAIT_YIELD((volatile kmp_uint32 *)waiting_id_p, 0, 1467 KMP_NEQ, NULL); 1468 #ifdef DEBUG_QUEUING_LOCKS 1469 TRACE_LOCK(gtid + 1, "rel deq: (h,t)->(h',t)"); 1470 #endif 1471 dequeued = TRUE; 1472 } 1473 } 1474 1475 if (dequeued) { 1476 kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1); 1477 KMP_DEBUG_ASSERT(head_thr != NULL); 1478 1479 /* Does this require synchronous reads? */ 1480 #ifdef DEBUG_QUEUING_LOCKS 1481 if (head <= 0 || tail <= 0) 1482 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail); 1483 #endif 1484 KMP_DEBUG_ASSERT(head > 0 && tail > 0); 1485 1486 /* For clean code only. Thread not released until next statement prevents 1487 race with acquire code. */ 1488 head_thr->th.th_next_waiting = 0; 1489 #ifdef DEBUG_QUEUING_LOCKS 1490 TRACE_LOCK_T(gtid + 1, "rel nw=0 for t=", head); 1491 #endif 1492 1493 KMP_MB(); 1494 /* reset spin value */ 1495 head_thr->th.th_spin_here = FALSE; 1496 1497 KA_TRACE(1000, ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: after " 1498 "dequeuing\n", 1499 lck, gtid)); 1500 #ifdef DEBUG_QUEUING_LOCKS 1501 TRACE_LOCK(gtid + 1, "rel exit 2"); 1502 #endif 1503 return KMP_LOCK_RELEASED; 1504 } 1505 /* KMP_CPU_PAUSE(); don't want to make releasing thread hold up acquiring 1506 threads */ 1507 1508 #ifdef DEBUG_QUEUING_LOCKS 1509 TRACE_LOCK(gtid + 1, "rel retry"); 1510 #endif 1511 1512 } /* while */ 1513 KMP_ASSERT2(0, "should not get here"); 1514 return KMP_LOCK_RELEASED; 1515 } 1516 1517 static int __kmp_release_queuing_lock_with_checks(kmp_queuing_lock_t *lck, 1518 kmp_int32 gtid) { 1519 char const *const func = "omp_unset_lock"; 1520 KMP_MB(); /* in case another processor initialized lock */ 1521 if (lck->lk.initialized != lck) { 1522 KMP_FATAL(LockIsUninitialized, func); 1523 } 1524 if (__kmp_is_queuing_lock_nestable(lck)) { 1525 KMP_FATAL(LockNestableUsedAsSimple, func); 1526 } 1527 if (__kmp_get_queuing_lock_owner(lck) == -1) { 1528 KMP_FATAL(LockUnsettingFree, func); 1529 } 1530 if (__kmp_get_queuing_lock_owner(lck) != gtid) { 1531 KMP_FATAL(LockUnsettingSetByAnother, func); 1532 } 1533 lck->lk.owner_id = 0; 1534 return __kmp_release_queuing_lock(lck, gtid); 1535 } 1536 1537 void __kmp_init_queuing_lock(kmp_queuing_lock_t *lck) { 1538 lck->lk.location = NULL; 1539 lck->lk.head_id = 0; 1540 lck->lk.tail_id = 0; 1541 lck->lk.next_ticket = 0; 1542 lck->lk.now_serving = 0; 1543 lck->lk.owner_id = 0; // no thread owns the lock. 1544 lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks. 1545 lck->lk.initialized = lck; 1546 1547 KA_TRACE(1000, ("__kmp_init_queuing_lock: lock %p initialized\n", lck)); 1548 } 1549 1550 void __kmp_destroy_queuing_lock(kmp_queuing_lock_t *lck) { 1551 lck->lk.initialized = NULL; 1552 lck->lk.location = NULL; 1553 lck->lk.head_id = 0; 1554 lck->lk.tail_id = 0; 1555 lck->lk.next_ticket = 0; 1556 lck->lk.now_serving = 0; 1557 lck->lk.owner_id = 0; 1558 lck->lk.depth_locked = -1; 1559 } 1560 1561 static void __kmp_destroy_queuing_lock_with_checks(kmp_queuing_lock_t *lck) { 1562 char const *const func = "omp_destroy_lock"; 1563 if (lck->lk.initialized != lck) { 1564 KMP_FATAL(LockIsUninitialized, func); 1565 } 1566 if (__kmp_is_queuing_lock_nestable(lck)) { 1567 KMP_FATAL(LockNestableUsedAsSimple, func); 1568 } 1569 if (__kmp_get_queuing_lock_owner(lck) != -1) { 1570 KMP_FATAL(LockStillOwned, func); 1571 } 1572 __kmp_destroy_queuing_lock(lck); 1573 } 1574 1575 // nested queuing locks 1576 1577 int __kmp_acquire_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { 1578 KMP_DEBUG_ASSERT(gtid >= 0); 1579 1580 if (__kmp_get_queuing_lock_owner(lck) == gtid) { 1581 lck->lk.depth_locked += 1; 1582 return KMP_LOCK_ACQUIRED_NEXT; 1583 } else { 1584 __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid); 1585 ANNOTATE_QUEUING_ACQUIRED(lck); 1586 KMP_MB(); 1587 lck->lk.depth_locked = 1; 1588 KMP_MB(); 1589 lck->lk.owner_id = gtid + 1; 1590 return KMP_LOCK_ACQUIRED_FIRST; 1591 } 1592 } 1593 1594 static int 1595 __kmp_acquire_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck, 1596 kmp_int32 gtid) { 1597 char const *const func = "omp_set_nest_lock"; 1598 if (lck->lk.initialized != lck) { 1599 KMP_FATAL(LockIsUninitialized, func); 1600 } 1601 if (!__kmp_is_queuing_lock_nestable(lck)) { 1602 KMP_FATAL(LockSimpleUsedAsNestable, func); 1603 } 1604 return __kmp_acquire_nested_queuing_lock(lck, gtid); 1605 } 1606 1607 int __kmp_test_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { 1608 int retval; 1609 1610 KMP_DEBUG_ASSERT(gtid >= 0); 1611 1612 if (__kmp_get_queuing_lock_owner(lck) == gtid) { 1613 retval = ++lck->lk.depth_locked; 1614 } else if (!__kmp_test_queuing_lock(lck, gtid)) { 1615 retval = 0; 1616 } else { 1617 KMP_MB(); 1618 retval = lck->lk.depth_locked = 1; 1619 KMP_MB(); 1620 lck->lk.owner_id = gtid + 1; 1621 } 1622 return retval; 1623 } 1624 1625 static int __kmp_test_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck, 1626 kmp_int32 gtid) { 1627 char const *const func = "omp_test_nest_lock"; 1628 if (lck->lk.initialized != lck) { 1629 KMP_FATAL(LockIsUninitialized, func); 1630 } 1631 if (!__kmp_is_queuing_lock_nestable(lck)) { 1632 KMP_FATAL(LockSimpleUsedAsNestable, func); 1633 } 1634 return __kmp_test_nested_queuing_lock(lck, gtid); 1635 } 1636 1637 int __kmp_release_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { 1638 KMP_DEBUG_ASSERT(gtid >= 0); 1639 1640 KMP_MB(); 1641 if (--(lck->lk.depth_locked) == 0) { 1642 KMP_MB(); 1643 lck->lk.owner_id = 0; 1644 __kmp_release_queuing_lock(lck, gtid); 1645 return KMP_LOCK_RELEASED; 1646 } 1647 return KMP_LOCK_STILL_HELD; 1648 } 1649 1650 static int 1651 __kmp_release_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck, 1652 kmp_int32 gtid) { 1653 char const *const func = "omp_unset_nest_lock"; 1654 KMP_MB(); /* in case another processor initialized lock */ 1655 if (lck->lk.initialized != lck) { 1656 KMP_FATAL(LockIsUninitialized, func); 1657 } 1658 if (!__kmp_is_queuing_lock_nestable(lck)) { 1659 KMP_FATAL(LockSimpleUsedAsNestable, func); 1660 } 1661 if (__kmp_get_queuing_lock_owner(lck) == -1) { 1662 KMP_FATAL(LockUnsettingFree, func); 1663 } 1664 if (__kmp_get_queuing_lock_owner(lck) != gtid) { 1665 KMP_FATAL(LockUnsettingSetByAnother, func); 1666 } 1667 return __kmp_release_nested_queuing_lock(lck, gtid); 1668 } 1669 1670 void __kmp_init_nested_queuing_lock(kmp_queuing_lock_t *lck) { 1671 __kmp_init_queuing_lock(lck); 1672 lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks 1673 } 1674 1675 void __kmp_destroy_nested_queuing_lock(kmp_queuing_lock_t *lck) { 1676 __kmp_destroy_queuing_lock(lck); 1677 lck->lk.depth_locked = 0; 1678 } 1679 1680 static void 1681 __kmp_destroy_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) { 1682 char const *const func = "omp_destroy_nest_lock"; 1683 if (lck->lk.initialized != lck) { 1684 KMP_FATAL(LockIsUninitialized, func); 1685 } 1686 if (!__kmp_is_queuing_lock_nestable(lck)) { 1687 KMP_FATAL(LockSimpleUsedAsNestable, func); 1688 } 1689 if (__kmp_get_queuing_lock_owner(lck) != -1) { 1690 KMP_FATAL(LockStillOwned, func); 1691 } 1692 __kmp_destroy_nested_queuing_lock(lck); 1693 } 1694 1695 // access functions to fields which don't exist for all lock kinds. 1696 1697 static const ident_t *__kmp_get_queuing_lock_location(kmp_queuing_lock_t *lck) { 1698 return lck->lk.location; 1699 } 1700 1701 static void __kmp_set_queuing_lock_location(kmp_queuing_lock_t *lck, 1702 const ident_t *loc) { 1703 lck->lk.location = loc; 1704 } 1705 1706 static kmp_lock_flags_t __kmp_get_queuing_lock_flags(kmp_queuing_lock_t *lck) { 1707 return lck->lk.flags; 1708 } 1709 1710 static void __kmp_set_queuing_lock_flags(kmp_queuing_lock_t *lck, 1711 kmp_lock_flags_t flags) { 1712 lck->lk.flags = flags; 1713 } 1714 1715 #if KMP_USE_ADAPTIVE_LOCKS 1716 1717 /* RTM Adaptive locks */ 1718 1719 #if (KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300) || \ 1720 (KMP_COMPILER_MSVC && _MSC_VER >= 1700) || \ 1721 (KMP_COMPILER_CLANG && KMP_MSVC_COMPAT) 1722 1723 #include <immintrin.h> 1724 #define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT) 1725 1726 #else 1727 1728 // Values from the status register after failed speculation. 1729 #define _XBEGIN_STARTED (~0u) 1730 #define _XABORT_EXPLICIT (1 << 0) 1731 #define _XABORT_RETRY (1 << 1) 1732 #define _XABORT_CONFLICT (1 << 2) 1733 #define _XABORT_CAPACITY (1 << 3) 1734 #define _XABORT_DEBUG (1 << 4) 1735 #define _XABORT_NESTED (1 << 5) 1736 #define _XABORT_CODE(x) ((unsigned char)(((x) >> 24) & 0xFF)) 1737 1738 // Aborts for which it's worth trying again immediately 1739 #define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT) 1740 1741 #define STRINGIZE_INTERNAL(arg) #arg 1742 #define STRINGIZE(arg) STRINGIZE_INTERNAL(arg) 1743 1744 // Access to RTM instructions 1745 /*A version of XBegin which returns -1 on speculation, and the value of EAX on 1746 an abort. This is the same definition as the compiler intrinsic that will be 1747 supported at some point. */ 1748 static __inline int _xbegin() { 1749 int res = -1; 1750 1751 #if KMP_OS_WINDOWS 1752 #if KMP_ARCH_X86_64 1753 _asm { 1754 _emit 0xC7 1755 _emit 0xF8 1756 _emit 2 1757 _emit 0 1758 _emit 0 1759 _emit 0 1760 jmp L2 1761 mov res, eax 1762 L2: 1763 } 1764 #else /* IA32 */ 1765 _asm { 1766 _emit 0xC7 1767 _emit 0xF8 1768 _emit 2 1769 _emit 0 1770 _emit 0 1771 _emit 0 1772 jmp L2 1773 mov res, eax 1774 L2: 1775 } 1776 #endif // KMP_ARCH_X86_64 1777 #else 1778 /* Note that %eax must be noted as killed (clobbered), because the XSR is 1779 returned in %eax(%rax) on abort. Other register values are restored, so 1780 don't need to be killed. 1781 1782 We must also mark 'res' as an input and an output, since otherwise 1783 'res=-1' may be dropped as being dead, whereas we do need the assignment on 1784 the successful (i.e., non-abort) path. */ 1785 __asm__ volatile("1: .byte 0xC7; .byte 0xF8;\n" 1786 " .long 1f-1b-6\n" 1787 " jmp 2f\n" 1788 "1: movl %%eax,%0\n" 1789 "2:" 1790 : "+r"(res)::"memory", "%eax"); 1791 #endif // KMP_OS_WINDOWS 1792 return res; 1793 } 1794 1795 /* Transaction end */ 1796 static __inline void _xend() { 1797 #if KMP_OS_WINDOWS 1798 __asm { 1799 _emit 0x0f 1800 _emit 0x01 1801 _emit 0xd5 1802 } 1803 #else 1804 __asm__ volatile(".byte 0x0f; .byte 0x01; .byte 0xd5" ::: "memory"); 1805 #endif 1806 } 1807 1808 /* This is a macro, the argument must be a single byte constant which can be 1809 evaluated by the inline assembler, since it is emitted as a byte into the 1810 assembly code. */ 1811 // clang-format off 1812 #if KMP_OS_WINDOWS 1813 #define _xabort(ARG) _asm _emit 0xc6 _asm _emit 0xf8 _asm _emit ARG 1814 #else 1815 #define _xabort(ARG) \ 1816 __asm__ volatile(".byte 0xC6; .byte 0xF8; .byte " STRINGIZE(ARG):::"memory"); 1817 #endif 1818 // clang-format on 1819 #endif // KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300 1820 1821 // Statistics is collected for testing purpose 1822 #if KMP_DEBUG_ADAPTIVE_LOCKS 1823 1824 // We accumulate speculative lock statistics when the lock is destroyed. We 1825 // keep locks that haven't been destroyed in the liveLocks list so that we can 1826 // grab their statistics too. 1827 static kmp_adaptive_lock_statistics_t destroyedStats; 1828 1829 // To hold the list of live locks. 1830 static kmp_adaptive_lock_info_t liveLocks; 1831 1832 // A lock so we can safely update the list of locks. 1833 static kmp_bootstrap_lock_t chain_lock = 1834 KMP_BOOTSTRAP_LOCK_INITIALIZER(chain_lock); 1835 1836 // Initialize the list of stats. 1837 void __kmp_init_speculative_stats() { 1838 kmp_adaptive_lock_info_t *lck = &liveLocks; 1839 1840 memset(CCAST(kmp_adaptive_lock_statistics_t *, &(lck->stats)), 0, 1841 sizeof(lck->stats)); 1842 lck->stats.next = lck; 1843 lck->stats.prev = lck; 1844 1845 KMP_ASSERT(lck->stats.next->stats.prev == lck); 1846 KMP_ASSERT(lck->stats.prev->stats.next == lck); 1847 1848 __kmp_init_bootstrap_lock(&chain_lock); 1849 } 1850 1851 // Insert the lock into the circular list 1852 static void __kmp_remember_lock(kmp_adaptive_lock_info_t *lck) { 1853 __kmp_acquire_bootstrap_lock(&chain_lock); 1854 1855 lck->stats.next = liveLocks.stats.next; 1856 lck->stats.prev = &liveLocks; 1857 1858 liveLocks.stats.next = lck; 1859 lck->stats.next->stats.prev = lck; 1860 1861 KMP_ASSERT(lck->stats.next->stats.prev == lck); 1862 KMP_ASSERT(lck->stats.prev->stats.next == lck); 1863 1864 __kmp_release_bootstrap_lock(&chain_lock); 1865 } 1866 1867 static void __kmp_forget_lock(kmp_adaptive_lock_info_t *lck) { 1868 KMP_ASSERT(lck->stats.next->stats.prev == lck); 1869 KMP_ASSERT(lck->stats.prev->stats.next == lck); 1870 1871 kmp_adaptive_lock_info_t *n = lck->stats.next; 1872 kmp_adaptive_lock_info_t *p = lck->stats.prev; 1873 1874 n->stats.prev = p; 1875 p->stats.next = n; 1876 } 1877 1878 static void __kmp_zero_speculative_stats(kmp_adaptive_lock_info_t *lck) { 1879 memset(CCAST(kmp_adaptive_lock_statistics_t *, &lck->stats), 0, 1880 sizeof(lck->stats)); 1881 __kmp_remember_lock(lck); 1882 } 1883 1884 static void __kmp_add_stats(kmp_adaptive_lock_statistics_t *t, 1885 kmp_adaptive_lock_info_t *lck) { 1886 kmp_adaptive_lock_statistics_t volatile *s = &lck->stats; 1887 1888 t->nonSpeculativeAcquireAttempts += lck->acquire_attempts; 1889 t->successfulSpeculations += s->successfulSpeculations; 1890 t->hardFailedSpeculations += s->hardFailedSpeculations; 1891 t->softFailedSpeculations += s->softFailedSpeculations; 1892 t->nonSpeculativeAcquires += s->nonSpeculativeAcquires; 1893 t->lemmingYields += s->lemmingYields; 1894 } 1895 1896 static void __kmp_accumulate_speculative_stats(kmp_adaptive_lock_info_t *lck) { 1897 __kmp_acquire_bootstrap_lock(&chain_lock); 1898 1899 __kmp_add_stats(&destroyedStats, lck); 1900 __kmp_forget_lock(lck); 1901 1902 __kmp_release_bootstrap_lock(&chain_lock); 1903 } 1904 1905 static float percent(kmp_uint32 count, kmp_uint32 total) { 1906 return (total == 0) ? 0.0 : (100.0 * count) / total; 1907 } 1908 1909 static FILE *__kmp_open_stats_file() { 1910 if (strcmp(__kmp_speculative_statsfile, "-") == 0) 1911 return stdout; 1912 1913 size_t buffLen = KMP_STRLEN(__kmp_speculative_statsfile) + 20; 1914 char buffer[buffLen]; 1915 KMP_SNPRINTF(&buffer[0], buffLen, __kmp_speculative_statsfile, 1916 (kmp_int32)getpid()); 1917 FILE *result = fopen(&buffer[0], "w"); 1918 1919 // Maybe we should issue a warning here... 1920 return result ? result : stdout; 1921 } 1922 1923 void __kmp_print_speculative_stats() { 1924 kmp_adaptive_lock_statistics_t total = destroyedStats; 1925 kmp_adaptive_lock_info_t *lck; 1926 1927 for (lck = liveLocks.stats.next; lck != &liveLocks; lck = lck->stats.next) { 1928 __kmp_add_stats(&total, lck); 1929 } 1930 kmp_adaptive_lock_statistics_t *t = &total; 1931 kmp_uint32 totalSections = 1932 t->nonSpeculativeAcquires + t->successfulSpeculations; 1933 kmp_uint32 totalSpeculations = t->successfulSpeculations + 1934 t->hardFailedSpeculations + 1935 t->softFailedSpeculations; 1936 if (totalSections <= 0) 1937 return; 1938 1939 FILE *statsFile = __kmp_open_stats_file(); 1940 1941 fprintf(statsFile, "Speculative lock statistics (all approximate!)\n"); 1942 fprintf(statsFile, " Lock parameters: \n" 1943 " max_soft_retries : %10d\n" 1944 " max_badness : %10d\n", 1945 __kmp_adaptive_backoff_params.max_soft_retries, 1946 __kmp_adaptive_backoff_params.max_badness); 1947 fprintf(statsFile, " Non-speculative acquire attempts : %10d\n", 1948 t->nonSpeculativeAcquireAttempts); 1949 fprintf(statsFile, " Total critical sections : %10d\n", 1950 totalSections); 1951 fprintf(statsFile, " Successful speculations : %10d (%5.1f%%)\n", 1952 t->successfulSpeculations, 1953 percent(t->successfulSpeculations, totalSections)); 1954 fprintf(statsFile, " Non-speculative acquires : %10d (%5.1f%%)\n", 1955 t->nonSpeculativeAcquires, 1956 percent(t->nonSpeculativeAcquires, totalSections)); 1957 fprintf(statsFile, " Lemming yields : %10d\n\n", 1958 t->lemmingYields); 1959 1960 fprintf(statsFile, " Speculative acquire attempts : %10d\n", 1961 totalSpeculations); 1962 fprintf(statsFile, " Successes : %10d (%5.1f%%)\n", 1963 t->successfulSpeculations, 1964 percent(t->successfulSpeculations, totalSpeculations)); 1965 fprintf(statsFile, " Soft failures : %10d (%5.1f%%)\n", 1966 t->softFailedSpeculations, 1967 percent(t->softFailedSpeculations, totalSpeculations)); 1968 fprintf(statsFile, " Hard failures : %10d (%5.1f%%)\n", 1969 t->hardFailedSpeculations, 1970 percent(t->hardFailedSpeculations, totalSpeculations)); 1971 1972 if (statsFile != stdout) 1973 fclose(statsFile); 1974 } 1975 1976 #define KMP_INC_STAT(lck, stat) (lck->lk.adaptive.stats.stat++) 1977 #else 1978 #define KMP_INC_STAT(lck, stat) 1979 1980 #endif // KMP_DEBUG_ADAPTIVE_LOCKS 1981 1982 static inline bool __kmp_is_unlocked_queuing_lock(kmp_queuing_lock_t *lck) { 1983 // It is enough to check that the head_id is zero. 1984 // We don't also need to check the tail. 1985 bool res = lck->lk.head_id == 0; 1986 1987 // We need a fence here, since we must ensure that no memory operations 1988 // from later in this thread float above that read. 1989 #if KMP_COMPILER_ICC 1990 _mm_mfence(); 1991 #else 1992 __sync_synchronize(); 1993 #endif 1994 1995 return res; 1996 } 1997 1998 // Functions for manipulating the badness 1999 static __inline void 2000 __kmp_update_badness_after_success(kmp_adaptive_lock_t *lck) { 2001 // Reset the badness to zero so we eagerly try to speculate again 2002 lck->lk.adaptive.badness = 0; 2003 KMP_INC_STAT(lck, successfulSpeculations); 2004 } 2005 2006 // Create a bit mask with one more set bit. 2007 static __inline void __kmp_step_badness(kmp_adaptive_lock_t *lck) { 2008 kmp_uint32 newBadness = (lck->lk.adaptive.badness << 1) | 1; 2009 if (newBadness > lck->lk.adaptive.max_badness) { 2010 return; 2011 } else { 2012 lck->lk.adaptive.badness = newBadness; 2013 } 2014 } 2015 2016 // Check whether speculation should be attempted. 2017 static __inline int __kmp_should_speculate(kmp_adaptive_lock_t *lck, 2018 kmp_int32 gtid) { 2019 kmp_uint32 badness = lck->lk.adaptive.badness; 2020 kmp_uint32 attempts = lck->lk.adaptive.acquire_attempts; 2021 int res = (attempts & badness) == 0; 2022 return res; 2023 } 2024 2025 // Attempt to acquire only the speculative lock. 2026 // Does not back off to the non-speculative lock. 2027 static int __kmp_test_adaptive_lock_only(kmp_adaptive_lock_t *lck, 2028 kmp_int32 gtid) { 2029 int retries = lck->lk.adaptive.max_soft_retries; 2030 2031 // We don't explicitly count the start of speculation, rather we record the 2032 // results (success, hard fail, soft fail). The sum of all of those is the 2033 // total number of times we started speculation since all speculations must 2034 // end one of those ways. 2035 do { 2036 kmp_uint32 status = _xbegin(); 2037 // Switch this in to disable actual speculation but exercise at least some 2038 // of the rest of the code. Useful for debugging... 2039 // kmp_uint32 status = _XABORT_NESTED; 2040 2041 if (status == _XBEGIN_STARTED) { 2042 /* We have successfully started speculation. Check that no-one acquired 2043 the lock for real between when we last looked and now. This also gets 2044 the lock cache line into our read-set, which we need so that we'll 2045 abort if anyone later claims it for real. */ 2046 if (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) { 2047 // Lock is now visibly acquired, so someone beat us to it. Abort the 2048 // transaction so we'll restart from _xbegin with the failure status. 2049 _xabort(0x01); 2050 KMP_ASSERT2(0, "should not get here"); 2051 } 2052 return 1; // Lock has been acquired (speculatively) 2053 } else { 2054 // We have aborted, update the statistics 2055 if (status & SOFT_ABORT_MASK) { 2056 KMP_INC_STAT(lck, softFailedSpeculations); 2057 // and loop round to retry. 2058 } else { 2059 KMP_INC_STAT(lck, hardFailedSpeculations); 2060 // Give up if we had a hard failure. 2061 break; 2062 } 2063 } 2064 } while (retries--); // Loop while we have retries, and didn't fail hard. 2065 2066 // Either we had a hard failure or we didn't succeed softly after 2067 // the full set of attempts, so back off the badness. 2068 __kmp_step_badness(lck); 2069 return 0; 2070 } 2071 2072 // Attempt to acquire the speculative lock, or back off to the non-speculative 2073 // one if the speculative lock cannot be acquired. 2074 // We can succeed speculatively, non-speculatively, or fail. 2075 static int __kmp_test_adaptive_lock(kmp_adaptive_lock_t *lck, kmp_int32 gtid) { 2076 // First try to acquire the lock speculatively 2077 if (__kmp_should_speculate(lck, gtid) && 2078 __kmp_test_adaptive_lock_only(lck, gtid)) 2079 return 1; 2080 2081 // Speculative acquisition failed, so try to acquire it non-speculatively. 2082 // Count the non-speculative acquire attempt 2083 lck->lk.adaptive.acquire_attempts++; 2084 2085 // Use base, non-speculative lock. 2086 if (__kmp_test_queuing_lock(GET_QLK_PTR(lck), gtid)) { 2087 KMP_INC_STAT(lck, nonSpeculativeAcquires); 2088 return 1; // Lock is acquired (non-speculatively) 2089 } else { 2090 return 0; // Failed to acquire the lock, it's already visibly locked. 2091 } 2092 } 2093 2094 static int __kmp_test_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck, 2095 kmp_int32 gtid) { 2096 char const *const func = "omp_test_lock"; 2097 if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) { 2098 KMP_FATAL(LockIsUninitialized, func); 2099 } 2100 2101 int retval = __kmp_test_adaptive_lock(lck, gtid); 2102 2103 if (retval) { 2104 lck->lk.qlk.owner_id = gtid + 1; 2105 } 2106 return retval; 2107 } 2108 2109 // Block until we can acquire a speculative, adaptive lock. We check whether we 2110 // should be trying to speculate. If we should be, we check the real lock to see 2111 // if it is free, and, if not, pause without attempting to acquire it until it 2112 // is. Then we try the speculative acquire. This means that although we suffer 2113 // from lemmings a little (because all we can't acquire the lock speculatively 2114 // until the queue of threads waiting has cleared), we don't get into a state 2115 // where we can never acquire the lock speculatively (because we force the queue 2116 // to clear by preventing new arrivals from entering the queue). This does mean 2117 // that when we're trying to break lemmings, the lock is no longer fair. However 2118 // OpenMP makes no guarantee that its locks are fair, so this isn't a real 2119 // problem. 2120 static void __kmp_acquire_adaptive_lock(kmp_adaptive_lock_t *lck, 2121 kmp_int32 gtid) { 2122 if (__kmp_should_speculate(lck, gtid)) { 2123 if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) { 2124 if (__kmp_test_adaptive_lock_only(lck, gtid)) 2125 return; 2126 // We tried speculation and failed, so give up. 2127 } else { 2128 // We can't try speculation until the lock is free, so we pause here 2129 // (without suspending on the queueing lock, to allow it to drain, then 2130 // try again. All other threads will also see the same result for 2131 // shouldSpeculate, so will be doing the same if they try to claim the 2132 // lock from now on. 2133 while (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) { 2134 KMP_INC_STAT(lck, lemmingYields); 2135 __kmp_yield(TRUE); 2136 } 2137 2138 if (__kmp_test_adaptive_lock_only(lck, gtid)) 2139 return; 2140 } 2141 } 2142 2143 // Speculative acquisition failed, so acquire it non-speculatively. 2144 // Count the non-speculative acquire attempt 2145 lck->lk.adaptive.acquire_attempts++; 2146 2147 __kmp_acquire_queuing_lock_timed_template<FALSE>(GET_QLK_PTR(lck), gtid); 2148 // We have acquired the base lock, so count that. 2149 KMP_INC_STAT(lck, nonSpeculativeAcquires); 2150 ANNOTATE_QUEUING_ACQUIRED(lck); 2151 } 2152 2153 static void __kmp_acquire_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck, 2154 kmp_int32 gtid) { 2155 char const *const func = "omp_set_lock"; 2156 if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) { 2157 KMP_FATAL(LockIsUninitialized, func); 2158 } 2159 if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == gtid) { 2160 KMP_FATAL(LockIsAlreadyOwned, func); 2161 } 2162 2163 __kmp_acquire_adaptive_lock(lck, gtid); 2164 2165 lck->lk.qlk.owner_id = gtid + 1; 2166 } 2167 2168 static int __kmp_release_adaptive_lock(kmp_adaptive_lock_t *lck, 2169 kmp_int32 gtid) { 2170 if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR( 2171 lck))) { // If the lock doesn't look claimed we must be speculating. 2172 // (Or the user's code is buggy and they're releasing without locking; 2173 // if we had XTEST we'd be able to check that case...) 2174 _xend(); // Exit speculation 2175 __kmp_update_badness_after_success(lck); 2176 } else { // Since the lock *is* visibly locked we're not speculating, 2177 // so should use the underlying lock's release scheme. 2178 __kmp_release_queuing_lock(GET_QLK_PTR(lck), gtid); 2179 } 2180 return KMP_LOCK_RELEASED; 2181 } 2182 2183 static int __kmp_release_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck, 2184 kmp_int32 gtid) { 2185 char const *const func = "omp_unset_lock"; 2186 KMP_MB(); /* in case another processor initialized lock */ 2187 if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) { 2188 KMP_FATAL(LockIsUninitialized, func); 2189 } 2190 if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == -1) { 2191 KMP_FATAL(LockUnsettingFree, func); 2192 } 2193 if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != gtid) { 2194 KMP_FATAL(LockUnsettingSetByAnother, func); 2195 } 2196 lck->lk.qlk.owner_id = 0; 2197 __kmp_release_adaptive_lock(lck, gtid); 2198 return KMP_LOCK_RELEASED; 2199 } 2200 2201 static void __kmp_init_adaptive_lock(kmp_adaptive_lock_t *lck) { 2202 __kmp_init_queuing_lock(GET_QLK_PTR(lck)); 2203 lck->lk.adaptive.badness = 0; 2204 lck->lk.adaptive.acquire_attempts = 0; // nonSpeculativeAcquireAttempts = 0; 2205 lck->lk.adaptive.max_soft_retries = 2206 __kmp_adaptive_backoff_params.max_soft_retries; 2207 lck->lk.adaptive.max_badness = __kmp_adaptive_backoff_params.max_badness; 2208 #if KMP_DEBUG_ADAPTIVE_LOCKS 2209 __kmp_zero_speculative_stats(&lck->lk.adaptive); 2210 #endif 2211 KA_TRACE(1000, ("__kmp_init_adaptive_lock: lock %p initialized\n", lck)); 2212 } 2213 2214 static void __kmp_destroy_adaptive_lock(kmp_adaptive_lock_t *lck) { 2215 #if KMP_DEBUG_ADAPTIVE_LOCKS 2216 __kmp_accumulate_speculative_stats(&lck->lk.adaptive); 2217 #endif 2218 __kmp_destroy_queuing_lock(GET_QLK_PTR(lck)); 2219 // Nothing needed for the speculative part. 2220 } 2221 2222 static void __kmp_destroy_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck) { 2223 char const *const func = "omp_destroy_lock"; 2224 if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) { 2225 KMP_FATAL(LockIsUninitialized, func); 2226 } 2227 if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != -1) { 2228 KMP_FATAL(LockStillOwned, func); 2229 } 2230 __kmp_destroy_adaptive_lock(lck); 2231 } 2232 2233 #endif // KMP_USE_ADAPTIVE_LOCKS 2234 2235 /* ------------------------------------------------------------------------ */ 2236 /* DRDPA ticket locks */ 2237 /* "DRDPA" means Dynamically Reconfigurable Distributed Polling Area */ 2238 2239 static kmp_int32 __kmp_get_drdpa_lock_owner(kmp_drdpa_lock_t *lck) { 2240 return lck->lk.owner_id - 1; 2241 } 2242 2243 static inline bool __kmp_is_drdpa_lock_nestable(kmp_drdpa_lock_t *lck) { 2244 return lck->lk.depth_locked != -1; 2245 } 2246 2247 __forceinline static int 2248 __kmp_acquire_drdpa_lock_timed_template(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { 2249 kmp_uint64 ticket = KMP_ATOMIC_INC(&lck->lk.next_ticket); 2250 kmp_uint64 mask = lck->lk.mask; // atomic load 2251 std::atomic<kmp_uint64> *polls = lck->lk.polls; 2252 2253 #ifdef USE_LOCK_PROFILE 2254 if (polls[ticket & mask] != ticket) 2255 __kmp_printf("LOCK CONTENTION: %p\n", lck); 2256 /* else __kmp_printf( "." );*/ 2257 #endif /* USE_LOCK_PROFILE */ 2258 2259 // Now spin-wait, but reload the polls pointer and mask, in case the 2260 // polling area has been reconfigured. Unless it is reconfigured, the 2261 // reloads stay in L1 cache and are cheap. 2262 // 2263 // Keep this code in sync with KMP_WAIT_YIELD, in kmp_dispatch.cpp !!! 2264 // 2265 // The current implementation of KMP_WAIT_YIELD doesn't allow for mask 2266 // and poll to be re-read every spin iteration. 2267 kmp_uint32 spins; 2268 2269 KMP_FSYNC_PREPARE(lck); 2270 KMP_INIT_YIELD(spins); 2271 while (polls[ticket & mask] < ticket) { // atomic load 2272 // If we are oversubscribed, 2273 // or have waited a bit (and KMP_LIBRARY=turnaround), then yield. 2274 // CPU Pause is in the macros for yield. 2275 // 2276 KMP_YIELD(TCR_4(__kmp_nth) > 2277 (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); 2278 KMP_YIELD_SPIN(spins); 2279 2280 // Re-read the mask and the poll pointer from the lock structure. 2281 // 2282 // Make certain that "mask" is read before "polls" !!! 2283 // 2284 // If another thread picks reconfigures the polling area and updates their 2285 // values, and we get the new value of mask and the old polls pointer, we 2286 // could access memory beyond the end of the old polling area. 2287 mask = lck->lk.mask; // atomic load 2288 polls = lck->lk.polls; // atomic load 2289 } 2290 2291 // Critical section starts here 2292 KMP_FSYNC_ACQUIRED(lck); 2293 KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld acquired lock %p\n", 2294 ticket, lck)); 2295 lck->lk.now_serving = ticket; // non-volatile store 2296 2297 // Deallocate a garbage polling area if we know that we are the last 2298 // thread that could possibly access it. 2299 // 2300 // The >= check is in case __kmp_test_drdpa_lock() allocated the cleanup 2301 // ticket. 2302 if ((lck->lk.old_polls != NULL) && (ticket >= lck->lk.cleanup_ticket)) { 2303 __kmp_free(lck->lk.old_polls); 2304 lck->lk.old_polls = NULL; 2305 lck->lk.cleanup_ticket = 0; 2306 } 2307 2308 // Check to see if we should reconfigure the polling area. 2309 // If there is still a garbage polling area to be deallocated from a 2310 // previous reconfiguration, let a later thread reconfigure it. 2311 if (lck->lk.old_polls == NULL) { 2312 bool reconfigure = false; 2313 std::atomic<kmp_uint64> *old_polls = polls; 2314 kmp_uint32 num_polls = TCR_4(lck->lk.num_polls); 2315 2316 if (TCR_4(__kmp_nth) > 2317 (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) { 2318 // We are in oversubscription mode. Contract the polling area 2319 // down to a single location, if that hasn't been done already. 2320 if (num_polls > 1) { 2321 reconfigure = true; 2322 num_polls = TCR_4(lck->lk.num_polls); 2323 mask = 0; 2324 num_polls = 1; 2325 polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls * 2326 sizeof(*polls)); 2327 polls[0] = ticket; 2328 } 2329 } else { 2330 // We are in under/fully subscribed mode. Check the number of 2331 // threads waiting on the lock. The size of the polling area 2332 // should be at least the number of threads waiting. 2333 kmp_uint64 num_waiting = TCR_8(lck->lk.next_ticket) - ticket - 1; 2334 if (num_waiting > num_polls) { 2335 kmp_uint32 old_num_polls = num_polls; 2336 reconfigure = true; 2337 do { 2338 mask = (mask << 1) | 1; 2339 num_polls *= 2; 2340 } while (num_polls <= num_waiting); 2341 2342 // Allocate the new polling area, and copy the relevant portion 2343 // of the old polling area to the new area. __kmp_allocate() 2344 // zeroes the memory it allocates, and most of the old area is 2345 // just zero padding, so we only copy the release counters. 2346 polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls * 2347 sizeof(*polls)); 2348 kmp_uint32 i; 2349 for (i = 0; i < old_num_polls; i++) { 2350 polls[i].store(old_polls[i]); 2351 } 2352 } 2353 } 2354 2355 if (reconfigure) { 2356 // Now write the updated fields back to the lock structure. 2357 // 2358 // Make certain that "polls" is written before "mask" !!! 2359 // 2360 // If another thread picks up the new value of mask and the old polls 2361 // pointer , it could access memory beyond the end of the old polling 2362 // area. 2363 // 2364 // On x86, we need memory fences. 2365 KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld reconfiguring " 2366 "lock %p to %d polls\n", 2367 ticket, lck, num_polls)); 2368 2369 lck->lk.old_polls = old_polls; 2370 lck->lk.polls = polls; // atomic store 2371 2372 KMP_MB(); 2373 2374 lck->lk.num_polls = num_polls; 2375 lck->lk.mask = mask; // atomic store 2376 2377 KMP_MB(); 2378 2379 // Only after the new polling area and mask have been flushed 2380 // to main memory can we update the cleanup ticket field. 2381 // 2382 // volatile load / non-volatile store 2383 lck->lk.cleanup_ticket = lck->lk.next_ticket; 2384 } 2385 } 2386 return KMP_LOCK_ACQUIRED_FIRST; 2387 } 2388 2389 int __kmp_acquire_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { 2390 int retval = __kmp_acquire_drdpa_lock_timed_template(lck, gtid); 2391 ANNOTATE_DRDPA_ACQUIRED(lck); 2392 return retval; 2393 } 2394 2395 static int __kmp_acquire_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, 2396 kmp_int32 gtid) { 2397 char const *const func = "omp_set_lock"; 2398 if (lck->lk.initialized != lck) { 2399 KMP_FATAL(LockIsUninitialized, func); 2400 } 2401 if (__kmp_is_drdpa_lock_nestable(lck)) { 2402 KMP_FATAL(LockNestableUsedAsSimple, func); 2403 } 2404 if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) == gtid)) { 2405 KMP_FATAL(LockIsAlreadyOwned, func); 2406 } 2407 2408 __kmp_acquire_drdpa_lock(lck, gtid); 2409 2410 lck->lk.owner_id = gtid + 1; 2411 return KMP_LOCK_ACQUIRED_FIRST; 2412 } 2413 2414 int __kmp_test_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { 2415 // First get a ticket, then read the polls pointer and the mask. 2416 // The polls pointer must be read before the mask!!! (See above) 2417 kmp_uint64 ticket = lck->lk.next_ticket; // atomic load 2418 std::atomic<kmp_uint64> *polls = lck->lk.polls; 2419 kmp_uint64 mask = lck->lk.mask; // atomic load 2420 if (polls[ticket & mask] == ticket) { 2421 kmp_uint64 next_ticket = ticket + 1; 2422 if (__kmp_atomic_compare_store_acq(&lck->lk.next_ticket, ticket, 2423 next_ticket)) { 2424 KMP_FSYNC_ACQUIRED(lck); 2425 KA_TRACE(1000, ("__kmp_test_drdpa_lock: ticket #%lld acquired lock %p\n", 2426 ticket, lck)); 2427 lck->lk.now_serving = ticket; // non-volatile store 2428 2429 // Since no threads are waiting, there is no possibility that we would 2430 // want to reconfigure the polling area. We might have the cleanup ticket 2431 // value (which says that it is now safe to deallocate old_polls), but 2432 // we'll let a later thread which calls __kmp_acquire_lock do that - this 2433 // routine isn't supposed to block, and we would risk blocks if we called 2434 // __kmp_free() to do the deallocation. 2435 return TRUE; 2436 } 2437 } 2438 return FALSE; 2439 } 2440 2441 static int __kmp_test_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, 2442 kmp_int32 gtid) { 2443 char const *const func = "omp_test_lock"; 2444 if (lck->lk.initialized != lck) { 2445 KMP_FATAL(LockIsUninitialized, func); 2446 } 2447 if (__kmp_is_drdpa_lock_nestable(lck)) { 2448 KMP_FATAL(LockNestableUsedAsSimple, func); 2449 } 2450 2451 int retval = __kmp_test_drdpa_lock(lck, gtid); 2452 2453 if (retval) { 2454 lck->lk.owner_id = gtid + 1; 2455 } 2456 return retval; 2457 } 2458 2459 int __kmp_release_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { 2460 // Read the ticket value from the lock data struct, then the polls pointer and 2461 // the mask. The polls pointer must be read before the mask!!! (See above) 2462 kmp_uint64 ticket = lck->lk.now_serving + 1; // non-atomic load 2463 std::atomic<kmp_uint64> *polls = lck->lk.polls; // atomic load 2464 kmp_uint64 mask = lck->lk.mask; // atomic load 2465 KA_TRACE(1000, ("__kmp_release_drdpa_lock: ticket #%lld released lock %p\n", 2466 ticket - 1, lck)); 2467 KMP_FSYNC_RELEASING(lck); 2468 ANNOTATE_DRDPA_RELEASED(lck); 2469 polls[ticket & mask] = ticket; // atomic store 2470 return KMP_LOCK_RELEASED; 2471 } 2472 2473 static int __kmp_release_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, 2474 kmp_int32 gtid) { 2475 char const *const func = "omp_unset_lock"; 2476 KMP_MB(); /* in case another processor initialized lock */ 2477 if (lck->lk.initialized != lck) { 2478 KMP_FATAL(LockIsUninitialized, func); 2479 } 2480 if (__kmp_is_drdpa_lock_nestable(lck)) { 2481 KMP_FATAL(LockNestableUsedAsSimple, func); 2482 } 2483 if (__kmp_get_drdpa_lock_owner(lck) == -1) { 2484 KMP_FATAL(LockUnsettingFree, func); 2485 } 2486 if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) >= 0) && 2487 (__kmp_get_drdpa_lock_owner(lck) != gtid)) { 2488 KMP_FATAL(LockUnsettingSetByAnother, func); 2489 } 2490 lck->lk.owner_id = 0; 2491 return __kmp_release_drdpa_lock(lck, gtid); 2492 } 2493 2494 void __kmp_init_drdpa_lock(kmp_drdpa_lock_t *lck) { 2495 lck->lk.location = NULL; 2496 lck->lk.mask = 0; 2497 lck->lk.num_polls = 1; 2498 lck->lk.polls = (std::atomic<kmp_uint64> *)__kmp_allocate( 2499 lck->lk.num_polls * sizeof(*(lck->lk.polls))); 2500 lck->lk.cleanup_ticket = 0; 2501 lck->lk.old_polls = NULL; 2502 lck->lk.next_ticket = 0; 2503 lck->lk.now_serving = 0; 2504 lck->lk.owner_id = 0; // no thread owns the lock. 2505 lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks. 2506 lck->lk.initialized = lck; 2507 2508 KA_TRACE(1000, ("__kmp_init_drdpa_lock: lock %p initialized\n", lck)); 2509 } 2510 2511 void __kmp_destroy_drdpa_lock(kmp_drdpa_lock_t *lck) { 2512 lck->lk.initialized = NULL; 2513 lck->lk.location = NULL; 2514 if (lck->lk.polls.load() != NULL) { 2515 __kmp_free(lck->lk.polls.load()); 2516 lck->lk.polls = NULL; 2517 } 2518 if (lck->lk.old_polls != NULL) { 2519 __kmp_free(lck->lk.old_polls); 2520 lck->lk.old_polls = NULL; 2521 } 2522 lck->lk.mask = 0; 2523 lck->lk.num_polls = 0; 2524 lck->lk.cleanup_ticket = 0; 2525 lck->lk.next_ticket = 0; 2526 lck->lk.now_serving = 0; 2527 lck->lk.owner_id = 0; 2528 lck->lk.depth_locked = -1; 2529 } 2530 2531 static void __kmp_destroy_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) { 2532 char const *const func = "omp_destroy_lock"; 2533 if (lck->lk.initialized != lck) { 2534 KMP_FATAL(LockIsUninitialized, func); 2535 } 2536 if (__kmp_is_drdpa_lock_nestable(lck)) { 2537 KMP_FATAL(LockNestableUsedAsSimple, func); 2538 } 2539 if (__kmp_get_drdpa_lock_owner(lck) != -1) { 2540 KMP_FATAL(LockStillOwned, func); 2541 } 2542 __kmp_destroy_drdpa_lock(lck); 2543 } 2544 2545 // nested drdpa ticket locks 2546 2547 int __kmp_acquire_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { 2548 KMP_DEBUG_ASSERT(gtid >= 0); 2549 2550 if (__kmp_get_drdpa_lock_owner(lck) == gtid) { 2551 lck->lk.depth_locked += 1; 2552 return KMP_LOCK_ACQUIRED_NEXT; 2553 } else { 2554 __kmp_acquire_drdpa_lock_timed_template(lck, gtid); 2555 ANNOTATE_DRDPA_ACQUIRED(lck); 2556 KMP_MB(); 2557 lck->lk.depth_locked = 1; 2558 KMP_MB(); 2559 lck->lk.owner_id = gtid + 1; 2560 return KMP_LOCK_ACQUIRED_FIRST; 2561 } 2562 } 2563 2564 static void __kmp_acquire_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, 2565 kmp_int32 gtid) { 2566 char const *const func = "omp_set_nest_lock"; 2567 if (lck->lk.initialized != lck) { 2568 KMP_FATAL(LockIsUninitialized, func); 2569 } 2570 if (!__kmp_is_drdpa_lock_nestable(lck)) { 2571 KMP_FATAL(LockSimpleUsedAsNestable, func); 2572 } 2573 __kmp_acquire_nested_drdpa_lock(lck, gtid); 2574 } 2575 2576 int __kmp_test_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { 2577 int retval; 2578 2579 KMP_DEBUG_ASSERT(gtid >= 0); 2580 2581 if (__kmp_get_drdpa_lock_owner(lck) == gtid) { 2582 retval = ++lck->lk.depth_locked; 2583 } else if (!__kmp_test_drdpa_lock(lck, gtid)) { 2584 retval = 0; 2585 } else { 2586 KMP_MB(); 2587 retval = lck->lk.depth_locked = 1; 2588 KMP_MB(); 2589 lck->lk.owner_id = gtid + 1; 2590 } 2591 return retval; 2592 } 2593 2594 static int __kmp_test_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, 2595 kmp_int32 gtid) { 2596 char const *const func = "omp_test_nest_lock"; 2597 if (lck->lk.initialized != lck) { 2598 KMP_FATAL(LockIsUninitialized, func); 2599 } 2600 if (!__kmp_is_drdpa_lock_nestable(lck)) { 2601 KMP_FATAL(LockSimpleUsedAsNestable, func); 2602 } 2603 return __kmp_test_nested_drdpa_lock(lck, gtid); 2604 } 2605 2606 int __kmp_release_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { 2607 KMP_DEBUG_ASSERT(gtid >= 0); 2608 2609 KMP_MB(); 2610 if (--(lck->lk.depth_locked) == 0) { 2611 KMP_MB(); 2612 lck->lk.owner_id = 0; 2613 __kmp_release_drdpa_lock(lck, gtid); 2614 return KMP_LOCK_RELEASED; 2615 } 2616 return KMP_LOCK_STILL_HELD; 2617 } 2618 2619 static int __kmp_release_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, 2620 kmp_int32 gtid) { 2621 char const *const func = "omp_unset_nest_lock"; 2622 KMP_MB(); /* in case another processor initialized lock */ 2623 if (lck->lk.initialized != lck) { 2624 KMP_FATAL(LockIsUninitialized, func); 2625 } 2626 if (!__kmp_is_drdpa_lock_nestable(lck)) { 2627 KMP_FATAL(LockSimpleUsedAsNestable, func); 2628 } 2629 if (__kmp_get_drdpa_lock_owner(lck) == -1) { 2630 KMP_FATAL(LockUnsettingFree, func); 2631 } 2632 if (__kmp_get_drdpa_lock_owner(lck) != gtid) { 2633 KMP_FATAL(LockUnsettingSetByAnother, func); 2634 } 2635 return __kmp_release_nested_drdpa_lock(lck, gtid); 2636 } 2637 2638 void __kmp_init_nested_drdpa_lock(kmp_drdpa_lock_t *lck) { 2639 __kmp_init_drdpa_lock(lck); 2640 lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks 2641 } 2642 2643 void __kmp_destroy_nested_drdpa_lock(kmp_drdpa_lock_t *lck) { 2644 __kmp_destroy_drdpa_lock(lck); 2645 lck->lk.depth_locked = 0; 2646 } 2647 2648 static void __kmp_destroy_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) { 2649 char const *const func = "omp_destroy_nest_lock"; 2650 if (lck->lk.initialized != lck) { 2651 KMP_FATAL(LockIsUninitialized, func); 2652 } 2653 if (!__kmp_is_drdpa_lock_nestable(lck)) { 2654 KMP_FATAL(LockSimpleUsedAsNestable, func); 2655 } 2656 if (__kmp_get_drdpa_lock_owner(lck) != -1) { 2657 KMP_FATAL(LockStillOwned, func); 2658 } 2659 __kmp_destroy_nested_drdpa_lock(lck); 2660 } 2661 2662 // access functions to fields which don't exist for all lock kinds. 2663 2664 static const ident_t *__kmp_get_drdpa_lock_location(kmp_drdpa_lock_t *lck) { 2665 return lck->lk.location; 2666 } 2667 2668 static void __kmp_set_drdpa_lock_location(kmp_drdpa_lock_t *lck, 2669 const ident_t *loc) { 2670 lck->lk.location = loc; 2671 } 2672 2673 static kmp_lock_flags_t __kmp_get_drdpa_lock_flags(kmp_drdpa_lock_t *lck) { 2674 return lck->lk.flags; 2675 } 2676 2677 static void __kmp_set_drdpa_lock_flags(kmp_drdpa_lock_t *lck, 2678 kmp_lock_flags_t flags) { 2679 lck->lk.flags = flags; 2680 } 2681 2682 // Time stamp counter 2683 #if KMP_ARCH_X86 || KMP_ARCH_X86_64 2684 #define __kmp_tsc() __kmp_hardware_timestamp() 2685 // Runtime's default backoff parameters 2686 kmp_backoff_t __kmp_spin_backoff_params = {1, 4096, 100}; 2687 #else 2688 // Use nanoseconds for other platforms 2689 extern kmp_uint64 __kmp_now_nsec(); 2690 kmp_backoff_t __kmp_spin_backoff_params = {1, 256, 100}; 2691 #define __kmp_tsc() __kmp_now_nsec() 2692 #endif 2693 2694 // A useful predicate for dealing with timestamps that may wrap. 2695 // Is a before b? Since the timestamps may wrap, this is asking whether it's 2696 // shorter to go clockwise from a to b around the clock-face, or anti-clockwise. 2697 // Times where going clockwise is less distance than going anti-clockwise 2698 // are in the future, others are in the past. e.g. a = MAX-1, b = MAX+1 (=0), 2699 // then a > b (true) does not mean a reached b; whereas signed(a) = -2, 2700 // signed(b) = 0 captures the actual difference 2701 static inline bool before(kmp_uint64 a, kmp_uint64 b) { 2702 return ((kmp_int64)b - (kmp_int64)a) > 0; 2703 } 2704 2705 // Truncated binary exponential backoff function 2706 void __kmp_spin_backoff(kmp_backoff_t *boff) { 2707 // We could flatten this loop, but making it a nested loop gives better result 2708 kmp_uint32 i; 2709 for (i = boff->step; i > 0; i--) { 2710 kmp_uint64 goal = __kmp_tsc() + boff->min_tick; 2711 do { 2712 KMP_CPU_PAUSE(); 2713 } while (before(__kmp_tsc(), goal)); 2714 } 2715 boff->step = (boff->step << 1 | 1) & (boff->max_backoff - 1); 2716 } 2717 2718 #if KMP_USE_DYNAMIC_LOCK 2719 2720 // Direct lock initializers. It simply writes a tag to the low 8 bits of the 2721 // lock word. 2722 static void __kmp_init_direct_lock(kmp_dyna_lock_t *lck, 2723 kmp_dyna_lockseq_t seq) { 2724 TCW_4(*lck, KMP_GET_D_TAG(seq)); 2725 KA_TRACE( 2726 20, 2727 ("__kmp_init_direct_lock: initialized direct lock with type#%d\n", seq)); 2728 } 2729 2730 #if KMP_USE_TSX 2731 2732 // HLE lock functions - imported from the testbed runtime. 2733 #define HLE_ACQUIRE ".byte 0xf2;" 2734 #define HLE_RELEASE ".byte 0xf3;" 2735 2736 static inline kmp_uint32 swap4(kmp_uint32 volatile *p, kmp_uint32 v) { 2737 __asm__ volatile(HLE_ACQUIRE "xchg %1,%0" : "+r"(v), "+m"(*p) : : "memory"); 2738 return v; 2739 } 2740 2741 static void __kmp_destroy_hle_lock(kmp_dyna_lock_t *lck) { TCW_4(*lck, 0); } 2742 2743 static void __kmp_destroy_hle_lock_with_checks(kmp_dyna_lock_t *lck) { 2744 TCW_4(*lck, 0); 2745 } 2746 2747 static void __kmp_acquire_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) { 2748 // Use gtid for KMP_LOCK_BUSY if necessary 2749 if (swap4(lck, KMP_LOCK_BUSY(1, hle)) != KMP_LOCK_FREE(hle)) { 2750 int delay = 1; 2751 do { 2752 while (*(kmp_uint32 volatile *)lck != KMP_LOCK_FREE(hle)) { 2753 for (int i = delay; i != 0; --i) 2754 KMP_CPU_PAUSE(); 2755 delay = ((delay << 1) | 1) & 7; 2756 } 2757 } while (swap4(lck, KMP_LOCK_BUSY(1, hle)) != KMP_LOCK_FREE(hle)); 2758 } 2759 } 2760 2761 static void __kmp_acquire_hle_lock_with_checks(kmp_dyna_lock_t *lck, 2762 kmp_int32 gtid) { 2763 __kmp_acquire_hle_lock(lck, gtid); // TODO: add checks 2764 } 2765 2766 static int __kmp_release_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) { 2767 __asm__ volatile(HLE_RELEASE "movl %1,%0" 2768 : "=m"(*lck) 2769 : "r"(KMP_LOCK_FREE(hle)) 2770 : "memory"); 2771 return KMP_LOCK_RELEASED; 2772 } 2773 2774 static int __kmp_release_hle_lock_with_checks(kmp_dyna_lock_t *lck, 2775 kmp_int32 gtid) { 2776 return __kmp_release_hle_lock(lck, gtid); // TODO: add checks 2777 } 2778 2779 static int __kmp_test_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) { 2780 return swap4(lck, KMP_LOCK_BUSY(1, hle)) == KMP_LOCK_FREE(hle); 2781 } 2782 2783 static int __kmp_test_hle_lock_with_checks(kmp_dyna_lock_t *lck, 2784 kmp_int32 gtid) { 2785 return __kmp_test_hle_lock(lck, gtid); // TODO: add checks 2786 } 2787 2788 static void __kmp_init_rtm_lock(kmp_queuing_lock_t *lck) { 2789 __kmp_init_queuing_lock(lck); 2790 } 2791 2792 static void __kmp_destroy_rtm_lock(kmp_queuing_lock_t *lck) { 2793 __kmp_destroy_queuing_lock(lck); 2794 } 2795 2796 static void __kmp_destroy_rtm_lock_with_checks(kmp_queuing_lock_t *lck) { 2797 __kmp_destroy_queuing_lock_with_checks(lck); 2798 } 2799 2800 static void __kmp_acquire_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { 2801 unsigned retries = 3, status; 2802 do { 2803 status = _xbegin(); 2804 if (status == _XBEGIN_STARTED) { 2805 if (__kmp_is_unlocked_queuing_lock(lck)) 2806 return; 2807 _xabort(0xff); 2808 } 2809 if ((status & _XABORT_EXPLICIT) && _XABORT_CODE(status) == 0xff) { 2810 // Wait until lock becomes free 2811 while (!__kmp_is_unlocked_queuing_lock(lck)) 2812 __kmp_yield(TRUE); 2813 } else if (!(status & _XABORT_RETRY)) 2814 break; 2815 } while (retries--); 2816 2817 // Fall-back non-speculative lock (xchg) 2818 __kmp_acquire_queuing_lock(lck, gtid); 2819 } 2820 2821 static void __kmp_acquire_rtm_lock_with_checks(kmp_queuing_lock_t *lck, 2822 kmp_int32 gtid) { 2823 __kmp_acquire_rtm_lock(lck, gtid); 2824 } 2825 2826 static int __kmp_release_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { 2827 if (__kmp_is_unlocked_queuing_lock(lck)) { 2828 // Releasing from speculation 2829 _xend(); 2830 } else { 2831 // Releasing from a real lock 2832 __kmp_release_queuing_lock(lck, gtid); 2833 } 2834 return KMP_LOCK_RELEASED; 2835 } 2836 2837 static int __kmp_release_rtm_lock_with_checks(kmp_queuing_lock_t *lck, 2838 kmp_int32 gtid) { 2839 return __kmp_release_rtm_lock(lck, gtid); 2840 } 2841 2842 static int __kmp_test_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { 2843 unsigned retries = 3, status; 2844 do { 2845 status = _xbegin(); 2846 if (status == _XBEGIN_STARTED && __kmp_is_unlocked_queuing_lock(lck)) { 2847 return 1; 2848 } 2849 if (!(status & _XABORT_RETRY)) 2850 break; 2851 } while (retries--); 2852 2853 return (__kmp_is_unlocked_queuing_lock(lck)) ? 1 : 0; 2854 } 2855 2856 static int __kmp_test_rtm_lock_with_checks(kmp_queuing_lock_t *lck, 2857 kmp_int32 gtid) { 2858 return __kmp_test_rtm_lock(lck, gtid); 2859 } 2860 2861 #endif // KMP_USE_TSX 2862 2863 // Entry functions for indirect locks (first element of direct lock jump tables) 2864 static void __kmp_init_indirect_lock(kmp_dyna_lock_t *l, 2865 kmp_dyna_lockseq_t tag); 2866 static void __kmp_destroy_indirect_lock(kmp_dyna_lock_t *lock); 2867 static int __kmp_set_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32); 2868 static int __kmp_unset_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32); 2869 static int __kmp_test_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32); 2870 static int __kmp_set_indirect_lock_with_checks(kmp_dyna_lock_t *lock, 2871 kmp_int32); 2872 static int __kmp_unset_indirect_lock_with_checks(kmp_dyna_lock_t *lock, 2873 kmp_int32); 2874 static int __kmp_test_indirect_lock_with_checks(kmp_dyna_lock_t *lock, 2875 kmp_int32); 2876 2877 // Lock function definitions for the union parameter type 2878 #define KMP_FOREACH_LOCK_KIND(m, a) m(ticket, a) m(queuing, a) m(drdpa, a) 2879 2880 #define expand1(lk, op) \ 2881 static void __kmp_##op##_##lk##_##lock(kmp_user_lock_p lock) { \ 2882 __kmp_##op##_##lk##_##lock(&lock->lk); \ 2883 } 2884 #define expand2(lk, op) \ 2885 static int __kmp_##op##_##lk##_##lock(kmp_user_lock_p lock, \ 2886 kmp_int32 gtid) { \ 2887 return __kmp_##op##_##lk##_##lock(&lock->lk, gtid); \ 2888 } 2889 #define expand3(lk, op) \ 2890 static void __kmp_set_##lk##_##lock_flags(kmp_user_lock_p lock, \ 2891 kmp_lock_flags_t flags) { \ 2892 __kmp_set_##lk##_lock_flags(&lock->lk, flags); \ 2893 } 2894 #define expand4(lk, op) \ 2895 static void __kmp_set_##lk##_##lock_location(kmp_user_lock_p lock, \ 2896 const ident_t *loc) { \ 2897 __kmp_set_##lk##_lock_location(&lock->lk, loc); \ 2898 } 2899 2900 KMP_FOREACH_LOCK_KIND(expand1, init) 2901 KMP_FOREACH_LOCK_KIND(expand1, init_nested) 2902 KMP_FOREACH_LOCK_KIND(expand1, destroy) 2903 KMP_FOREACH_LOCK_KIND(expand1, destroy_nested) 2904 KMP_FOREACH_LOCK_KIND(expand2, acquire) 2905 KMP_FOREACH_LOCK_KIND(expand2, acquire_nested) 2906 KMP_FOREACH_LOCK_KIND(expand2, release) 2907 KMP_FOREACH_LOCK_KIND(expand2, release_nested) 2908 KMP_FOREACH_LOCK_KIND(expand2, test) 2909 KMP_FOREACH_LOCK_KIND(expand2, test_nested) 2910 KMP_FOREACH_LOCK_KIND(expand3, ) 2911 KMP_FOREACH_LOCK_KIND(expand4, ) 2912 2913 #undef expand1 2914 #undef expand2 2915 #undef expand3 2916 #undef expand4 2917 2918 // Jump tables for the indirect lock functions 2919 // Only fill in the odd entries, that avoids the need to shift out the low bit 2920 2921 // init functions 2922 #define expand(l, op) 0, __kmp_init_direct_lock, 2923 void (*__kmp_direct_init[])(kmp_dyna_lock_t *, kmp_dyna_lockseq_t) = { 2924 __kmp_init_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, init)}; 2925 #undef expand 2926 2927 // destroy functions 2928 #define expand(l, op) 0, (void (*)(kmp_dyna_lock_t *))__kmp_##op##_##l##_lock, 2929 static void (*direct_destroy[])(kmp_dyna_lock_t *) = { 2930 __kmp_destroy_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, destroy)}; 2931 #undef expand 2932 #define expand(l, op) \ 2933 0, (void (*)(kmp_dyna_lock_t *))__kmp_destroy_##l##_lock_with_checks, 2934 static void (*direct_destroy_check[])(kmp_dyna_lock_t *) = { 2935 __kmp_destroy_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, destroy)}; 2936 #undef expand 2937 2938 // set/acquire functions 2939 #define expand(l, op) \ 2940 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock, 2941 static int (*direct_set[])(kmp_dyna_lock_t *, kmp_int32) = { 2942 __kmp_set_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, acquire)}; 2943 #undef expand 2944 #define expand(l, op) \ 2945 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock_with_checks, 2946 static int (*direct_set_check[])(kmp_dyna_lock_t *, kmp_int32) = { 2947 __kmp_set_indirect_lock_with_checks, 0, 2948 KMP_FOREACH_D_LOCK(expand, acquire)}; 2949 #undef expand 2950 2951 // unset/release and test functions 2952 #define expand(l, op) \ 2953 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock, 2954 static int (*direct_unset[])(kmp_dyna_lock_t *, kmp_int32) = { 2955 __kmp_unset_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, release)}; 2956 static int (*direct_test[])(kmp_dyna_lock_t *, kmp_int32) = { 2957 __kmp_test_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, test)}; 2958 #undef expand 2959 #define expand(l, op) \ 2960 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock_with_checks, 2961 static int (*direct_unset_check[])(kmp_dyna_lock_t *, kmp_int32) = { 2962 __kmp_unset_indirect_lock_with_checks, 0, 2963 KMP_FOREACH_D_LOCK(expand, release)}; 2964 static int (*direct_test_check[])(kmp_dyna_lock_t *, kmp_int32) = { 2965 __kmp_test_indirect_lock_with_checks, 0, KMP_FOREACH_D_LOCK(expand, test)}; 2966 #undef expand 2967 2968 // Exposes only one set of jump tables (*lock or *lock_with_checks). 2969 void (*(*__kmp_direct_destroy))(kmp_dyna_lock_t *) = 0; 2970 int (*(*__kmp_direct_set))(kmp_dyna_lock_t *, kmp_int32) = 0; 2971 int (*(*__kmp_direct_unset))(kmp_dyna_lock_t *, kmp_int32) = 0; 2972 int (*(*__kmp_direct_test))(kmp_dyna_lock_t *, kmp_int32) = 0; 2973 2974 // Jump tables for the indirect lock functions 2975 #define expand(l, op) (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock, 2976 void (*__kmp_indirect_init[])(kmp_user_lock_p) = { 2977 KMP_FOREACH_I_LOCK(expand, init)}; 2978 #undef expand 2979 2980 #define expand(l, op) (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock, 2981 static void (*indirect_destroy[])(kmp_user_lock_p) = { 2982 KMP_FOREACH_I_LOCK(expand, destroy)}; 2983 #undef expand 2984 #define expand(l, op) \ 2985 (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock_with_checks, 2986 static void (*indirect_destroy_check[])(kmp_user_lock_p) = { 2987 KMP_FOREACH_I_LOCK(expand, destroy)}; 2988 #undef expand 2989 2990 // set/acquire functions 2991 #define expand(l, op) \ 2992 (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock, 2993 static int (*indirect_set[])(kmp_user_lock_p, 2994 kmp_int32) = {KMP_FOREACH_I_LOCK(expand, acquire)}; 2995 #undef expand 2996 #define expand(l, op) \ 2997 (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock_with_checks, 2998 static int (*indirect_set_check[])(kmp_user_lock_p, kmp_int32) = { 2999 KMP_FOREACH_I_LOCK(expand, acquire)}; 3000 #undef expand 3001 3002 // unset/release and test functions 3003 #define expand(l, op) \ 3004 (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock, 3005 static int (*indirect_unset[])(kmp_user_lock_p, kmp_int32) = { 3006 KMP_FOREACH_I_LOCK(expand, release)}; 3007 static int (*indirect_test[])(kmp_user_lock_p, 3008 kmp_int32) = {KMP_FOREACH_I_LOCK(expand, test)}; 3009 #undef expand 3010 #define expand(l, op) \ 3011 (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock_with_checks, 3012 static int (*indirect_unset_check[])(kmp_user_lock_p, kmp_int32) = { 3013 KMP_FOREACH_I_LOCK(expand, release)}; 3014 static int (*indirect_test_check[])(kmp_user_lock_p, kmp_int32) = { 3015 KMP_FOREACH_I_LOCK(expand, test)}; 3016 #undef expand 3017 3018 // Exposes only one jump tables (*lock or *lock_with_checks). 3019 void (*(*__kmp_indirect_destroy))(kmp_user_lock_p) = 0; 3020 int (*(*__kmp_indirect_set))(kmp_user_lock_p, kmp_int32) = 0; 3021 int (*(*__kmp_indirect_unset))(kmp_user_lock_p, kmp_int32) = 0; 3022 int (*(*__kmp_indirect_test))(kmp_user_lock_p, kmp_int32) = 0; 3023 3024 // Lock index table. 3025 kmp_indirect_lock_table_t __kmp_i_lock_table; 3026 3027 // Size of indirect locks. 3028 static kmp_uint32 __kmp_indirect_lock_size[KMP_NUM_I_LOCKS] = {0}; 3029 3030 // Jump tables for lock accessor/modifier. 3031 void (*__kmp_indirect_set_location[KMP_NUM_I_LOCKS])(kmp_user_lock_p, 3032 const ident_t *) = {0}; 3033 void (*__kmp_indirect_set_flags[KMP_NUM_I_LOCKS])(kmp_user_lock_p, 3034 kmp_lock_flags_t) = {0}; 3035 const ident_t *(*__kmp_indirect_get_location[KMP_NUM_I_LOCKS])( 3036 kmp_user_lock_p) = {0}; 3037 kmp_lock_flags_t (*__kmp_indirect_get_flags[KMP_NUM_I_LOCKS])( 3038 kmp_user_lock_p) = {0}; 3039 3040 // Use different lock pools for different lock types. 3041 static kmp_indirect_lock_t *__kmp_indirect_lock_pool[KMP_NUM_I_LOCKS] = {0}; 3042 3043 // User lock allocator for dynamically dispatched indirect locks. Every entry of 3044 // the indirect lock table holds the address and type of the allocated indrect 3045 // lock (kmp_indirect_lock_t), and the size of the table doubles when it is 3046 // full. A destroyed indirect lock object is returned to the reusable pool of 3047 // locks, unique to each lock type. 3048 kmp_indirect_lock_t *__kmp_allocate_indirect_lock(void **user_lock, 3049 kmp_int32 gtid, 3050 kmp_indirect_locktag_t tag) { 3051 kmp_indirect_lock_t *lck; 3052 kmp_lock_index_t idx; 3053 3054 __kmp_acquire_lock(&__kmp_global_lock, gtid); 3055 3056 if (__kmp_indirect_lock_pool[tag] != NULL) { 3057 // Reuse the allocated and destroyed lock object 3058 lck = __kmp_indirect_lock_pool[tag]; 3059 if (OMP_LOCK_T_SIZE < sizeof(void *)) 3060 idx = lck->lock->pool.index; 3061 __kmp_indirect_lock_pool[tag] = (kmp_indirect_lock_t *)lck->lock->pool.next; 3062 KA_TRACE(20, ("__kmp_allocate_indirect_lock: reusing an existing lock %p\n", 3063 lck)); 3064 } else { 3065 idx = __kmp_i_lock_table.next; 3066 // Check capacity and double the size if it is full 3067 if (idx == __kmp_i_lock_table.size) { 3068 // Double up the space for block pointers 3069 int row = __kmp_i_lock_table.size / KMP_I_LOCK_CHUNK; 3070 kmp_indirect_lock_t **new_table = (kmp_indirect_lock_t **)__kmp_allocate( 3071 2 * row * sizeof(kmp_indirect_lock_t *)); 3072 KMP_MEMCPY(new_table, __kmp_i_lock_table.table, 3073 row * sizeof(kmp_indirect_lock_t *)); 3074 kmp_indirect_lock_t **old_table = __kmp_i_lock_table.table; 3075 __kmp_i_lock_table.table = new_table; 3076 __kmp_free(old_table); 3077 // Allocate new objects in the new blocks 3078 for (int i = row; i < 2 * row; ++i) 3079 *(__kmp_i_lock_table.table + i) = (kmp_indirect_lock_t *)__kmp_allocate( 3080 KMP_I_LOCK_CHUNK * sizeof(kmp_indirect_lock_t)); 3081 __kmp_i_lock_table.size = 2 * idx; 3082 } 3083 __kmp_i_lock_table.next++; 3084 lck = KMP_GET_I_LOCK(idx); 3085 // Allocate a new base lock object 3086 lck->lock = (kmp_user_lock_p)__kmp_allocate(__kmp_indirect_lock_size[tag]); 3087 KA_TRACE(20, 3088 ("__kmp_allocate_indirect_lock: allocated a new lock %p\n", lck)); 3089 } 3090 3091 __kmp_release_lock(&__kmp_global_lock, gtid); 3092 3093 lck->type = tag; 3094 3095 if (OMP_LOCK_T_SIZE < sizeof(void *)) { 3096 *((kmp_lock_index_t *)user_lock) = idx 3097 << 1; // indirect lock word must be even 3098 } else { 3099 *((kmp_indirect_lock_t **)user_lock) = lck; 3100 } 3101 3102 return lck; 3103 } 3104 3105 // User lock lookup for dynamically dispatched locks. 3106 static __forceinline kmp_indirect_lock_t * 3107 __kmp_lookup_indirect_lock(void **user_lock, const char *func) { 3108 if (__kmp_env_consistency_check) { 3109 kmp_indirect_lock_t *lck = NULL; 3110 if (user_lock == NULL) { 3111 KMP_FATAL(LockIsUninitialized, func); 3112 } 3113 if (OMP_LOCK_T_SIZE < sizeof(void *)) { 3114 kmp_lock_index_t idx = KMP_EXTRACT_I_INDEX(user_lock); 3115 if (idx >= __kmp_i_lock_table.size) { 3116 KMP_FATAL(LockIsUninitialized, func); 3117 } 3118 lck = KMP_GET_I_LOCK(idx); 3119 } else { 3120 lck = *((kmp_indirect_lock_t **)user_lock); 3121 } 3122 if (lck == NULL) { 3123 KMP_FATAL(LockIsUninitialized, func); 3124 } 3125 return lck; 3126 } else { 3127 if (OMP_LOCK_T_SIZE < sizeof(void *)) { 3128 return KMP_GET_I_LOCK(KMP_EXTRACT_I_INDEX(user_lock)); 3129 } else { 3130 return *((kmp_indirect_lock_t **)user_lock); 3131 } 3132 } 3133 } 3134 3135 static void __kmp_init_indirect_lock(kmp_dyna_lock_t *lock, 3136 kmp_dyna_lockseq_t seq) { 3137 #if KMP_USE_ADAPTIVE_LOCKS 3138 if (seq == lockseq_adaptive && !__kmp_cpuinfo.rtm) { 3139 KMP_WARNING(AdaptiveNotSupported, "kmp_lockseq_t", "adaptive"); 3140 seq = lockseq_queuing; 3141 } 3142 #endif 3143 #if KMP_USE_TSX 3144 if (seq == lockseq_rtm && !__kmp_cpuinfo.rtm) { 3145 seq = lockseq_queuing; 3146 } 3147 #endif 3148 kmp_indirect_locktag_t tag = KMP_GET_I_TAG(seq); 3149 kmp_indirect_lock_t *l = 3150 __kmp_allocate_indirect_lock((void **)lock, __kmp_entry_gtid(), tag); 3151 KMP_I_LOCK_FUNC(l, init)(l->lock); 3152 KA_TRACE( 3153 20, ("__kmp_init_indirect_lock: initialized indirect lock with type#%d\n", 3154 seq)); 3155 } 3156 3157 static void __kmp_destroy_indirect_lock(kmp_dyna_lock_t *lock) { 3158 kmp_uint32 gtid = __kmp_entry_gtid(); 3159 kmp_indirect_lock_t *l = 3160 __kmp_lookup_indirect_lock((void **)lock, "omp_destroy_lock"); 3161 KMP_I_LOCK_FUNC(l, destroy)(l->lock); 3162 kmp_indirect_locktag_t tag = l->type; 3163 3164 __kmp_acquire_lock(&__kmp_global_lock, gtid); 3165 3166 // Use the base lock's space to keep the pool chain. 3167 l->lock->pool.next = (kmp_user_lock_p)__kmp_indirect_lock_pool[tag]; 3168 if (OMP_LOCK_T_SIZE < sizeof(void *)) { 3169 l->lock->pool.index = KMP_EXTRACT_I_INDEX(lock); 3170 } 3171 __kmp_indirect_lock_pool[tag] = l; 3172 3173 __kmp_release_lock(&__kmp_global_lock, gtid); 3174 } 3175 3176 static int __kmp_set_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) { 3177 kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock); 3178 return KMP_I_LOCK_FUNC(l, set)(l->lock, gtid); 3179 } 3180 3181 static int __kmp_unset_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) { 3182 kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock); 3183 return KMP_I_LOCK_FUNC(l, unset)(l->lock, gtid); 3184 } 3185 3186 static int __kmp_test_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) { 3187 kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock); 3188 return KMP_I_LOCK_FUNC(l, test)(l->lock, gtid); 3189 } 3190 3191 static int __kmp_set_indirect_lock_with_checks(kmp_dyna_lock_t *lock, 3192 kmp_int32 gtid) { 3193 kmp_indirect_lock_t *l = 3194 __kmp_lookup_indirect_lock((void **)lock, "omp_set_lock"); 3195 return KMP_I_LOCK_FUNC(l, set)(l->lock, gtid); 3196 } 3197 3198 static int __kmp_unset_indirect_lock_with_checks(kmp_dyna_lock_t *lock, 3199 kmp_int32 gtid) { 3200 kmp_indirect_lock_t *l = 3201 __kmp_lookup_indirect_lock((void **)lock, "omp_unset_lock"); 3202 return KMP_I_LOCK_FUNC(l, unset)(l->lock, gtid); 3203 } 3204 3205 static int __kmp_test_indirect_lock_with_checks(kmp_dyna_lock_t *lock, 3206 kmp_int32 gtid) { 3207 kmp_indirect_lock_t *l = 3208 __kmp_lookup_indirect_lock((void **)lock, "omp_test_lock"); 3209 return KMP_I_LOCK_FUNC(l, test)(l->lock, gtid); 3210 } 3211 3212 kmp_dyna_lockseq_t __kmp_user_lock_seq = lockseq_queuing; 3213 3214 // This is used only in kmp_error.cpp when consistency checking is on. 3215 kmp_int32 __kmp_get_user_lock_owner(kmp_user_lock_p lck, kmp_uint32 seq) { 3216 switch (seq) { 3217 case lockseq_tas: 3218 case lockseq_nested_tas: 3219 return __kmp_get_tas_lock_owner((kmp_tas_lock_t *)lck); 3220 #if KMP_USE_FUTEX 3221 case lockseq_futex: 3222 case lockseq_nested_futex: 3223 return __kmp_get_futex_lock_owner((kmp_futex_lock_t *)lck); 3224 #endif 3225 case lockseq_ticket: 3226 case lockseq_nested_ticket: 3227 return __kmp_get_ticket_lock_owner((kmp_ticket_lock_t *)lck); 3228 case lockseq_queuing: 3229 case lockseq_nested_queuing: 3230 #if KMP_USE_ADAPTIVE_LOCKS 3231 case lockseq_adaptive: 3232 #endif 3233 return __kmp_get_queuing_lock_owner((kmp_queuing_lock_t *)lck); 3234 case lockseq_drdpa: 3235 case lockseq_nested_drdpa: 3236 return __kmp_get_drdpa_lock_owner((kmp_drdpa_lock_t *)lck); 3237 default: 3238 return 0; 3239 } 3240 } 3241 3242 // Initializes data for dynamic user locks. 3243 void __kmp_init_dynamic_user_locks() { 3244 // Initialize jump table for the lock functions 3245 if (__kmp_env_consistency_check) { 3246 __kmp_direct_set = direct_set_check; 3247 __kmp_direct_unset = direct_unset_check; 3248 __kmp_direct_test = direct_test_check; 3249 __kmp_direct_destroy = direct_destroy_check; 3250 __kmp_indirect_set = indirect_set_check; 3251 __kmp_indirect_unset = indirect_unset_check; 3252 __kmp_indirect_test = indirect_test_check; 3253 __kmp_indirect_destroy = indirect_destroy_check; 3254 } else { 3255 __kmp_direct_set = direct_set; 3256 __kmp_direct_unset = direct_unset; 3257 __kmp_direct_test = direct_test; 3258 __kmp_direct_destroy = direct_destroy; 3259 __kmp_indirect_set = indirect_set; 3260 __kmp_indirect_unset = indirect_unset; 3261 __kmp_indirect_test = indirect_test; 3262 __kmp_indirect_destroy = indirect_destroy; 3263 } 3264 // If the user locks have already been initialized, then return. Allow the 3265 // switch between different KMP_CONSISTENCY_CHECK values, but do not allocate 3266 // new lock tables if they have already been allocated. 3267 if (__kmp_init_user_locks) 3268 return; 3269 3270 // Initialize lock index table 3271 __kmp_i_lock_table.size = KMP_I_LOCK_CHUNK; 3272 __kmp_i_lock_table.table = 3273 (kmp_indirect_lock_t **)__kmp_allocate(sizeof(kmp_indirect_lock_t *)); 3274 *(__kmp_i_lock_table.table) = (kmp_indirect_lock_t *)__kmp_allocate( 3275 KMP_I_LOCK_CHUNK * sizeof(kmp_indirect_lock_t)); 3276 __kmp_i_lock_table.next = 0; 3277 3278 // Indirect lock size 3279 __kmp_indirect_lock_size[locktag_ticket] = sizeof(kmp_ticket_lock_t); 3280 __kmp_indirect_lock_size[locktag_queuing] = sizeof(kmp_queuing_lock_t); 3281 #if KMP_USE_ADAPTIVE_LOCKS 3282 __kmp_indirect_lock_size[locktag_adaptive] = sizeof(kmp_adaptive_lock_t); 3283 #endif 3284 __kmp_indirect_lock_size[locktag_drdpa] = sizeof(kmp_drdpa_lock_t); 3285 #if KMP_USE_TSX 3286 __kmp_indirect_lock_size[locktag_rtm] = sizeof(kmp_queuing_lock_t); 3287 #endif 3288 __kmp_indirect_lock_size[locktag_nested_tas] = sizeof(kmp_tas_lock_t); 3289 #if KMP_USE_FUTEX 3290 __kmp_indirect_lock_size[locktag_nested_futex] = sizeof(kmp_futex_lock_t); 3291 #endif 3292 __kmp_indirect_lock_size[locktag_nested_ticket] = sizeof(kmp_ticket_lock_t); 3293 __kmp_indirect_lock_size[locktag_nested_queuing] = sizeof(kmp_queuing_lock_t); 3294 __kmp_indirect_lock_size[locktag_nested_drdpa] = sizeof(kmp_drdpa_lock_t); 3295 3296 // Initialize lock accessor/modifier 3297 #define fill_jumps(table, expand, sep) \ 3298 { \ 3299 table[locktag##sep##ticket] = expand(ticket); \ 3300 table[locktag##sep##queuing] = expand(queuing); \ 3301 table[locktag##sep##drdpa] = expand(drdpa); \ 3302 } 3303 3304 #if KMP_USE_ADAPTIVE_LOCKS 3305 #define fill_table(table, expand) \ 3306 { \ 3307 fill_jumps(table, expand, _); \ 3308 table[locktag_adaptive] = expand(queuing); \ 3309 fill_jumps(table, expand, _nested_); \ 3310 } 3311 #else 3312 #define fill_table(table, expand) \ 3313 { \ 3314 fill_jumps(table, expand, _); \ 3315 fill_jumps(table, expand, _nested_); \ 3316 } 3317 #endif // KMP_USE_ADAPTIVE_LOCKS 3318 3319 #define expand(l) \ 3320 (void (*)(kmp_user_lock_p, const ident_t *)) __kmp_set_##l##_lock_location 3321 fill_table(__kmp_indirect_set_location, expand); 3322 #undef expand 3323 #define expand(l) \ 3324 (void (*)(kmp_user_lock_p, kmp_lock_flags_t)) __kmp_set_##l##_lock_flags 3325 fill_table(__kmp_indirect_set_flags, expand); 3326 #undef expand 3327 #define expand(l) \ 3328 (const ident_t *(*)(kmp_user_lock_p)) __kmp_get_##l##_lock_location 3329 fill_table(__kmp_indirect_get_location, expand); 3330 #undef expand 3331 #define expand(l) \ 3332 (kmp_lock_flags_t(*)(kmp_user_lock_p)) __kmp_get_##l##_lock_flags 3333 fill_table(__kmp_indirect_get_flags, expand); 3334 #undef expand 3335 3336 __kmp_init_user_locks = TRUE; 3337 } 3338 3339 // Clean up the lock table. 3340 void __kmp_cleanup_indirect_user_locks() { 3341 kmp_lock_index_t i; 3342 int k; 3343 3344 // Clean up locks in the pools first (they were already destroyed before going 3345 // into the pools). 3346 for (k = 0; k < KMP_NUM_I_LOCKS; ++k) { 3347 kmp_indirect_lock_t *l = __kmp_indirect_lock_pool[k]; 3348 while (l != NULL) { 3349 kmp_indirect_lock_t *ll = l; 3350 l = (kmp_indirect_lock_t *)l->lock->pool.next; 3351 KA_TRACE(20, ("__kmp_cleanup_indirect_user_locks: freeing %p from pool\n", 3352 ll)); 3353 __kmp_free(ll->lock); 3354 ll->lock = NULL; 3355 } 3356 __kmp_indirect_lock_pool[k] = NULL; 3357 } 3358 // Clean up the remaining undestroyed locks. 3359 for (i = 0; i < __kmp_i_lock_table.next; i++) { 3360 kmp_indirect_lock_t *l = KMP_GET_I_LOCK(i); 3361 if (l->lock != NULL) { 3362 // Locks not destroyed explicitly need to be destroyed here. 3363 KMP_I_LOCK_FUNC(l, destroy)(l->lock); 3364 KA_TRACE( 3365 20, 3366 ("__kmp_cleanup_indirect_user_locks: destroy/freeing %p from table\n", 3367 l)); 3368 __kmp_free(l->lock); 3369 } 3370 } 3371 // Free the table 3372 for (i = 0; i < __kmp_i_lock_table.size / KMP_I_LOCK_CHUNK; i++) 3373 __kmp_free(__kmp_i_lock_table.table[i]); 3374 __kmp_free(__kmp_i_lock_table.table); 3375 3376 __kmp_init_user_locks = FALSE; 3377 } 3378 3379 enum kmp_lock_kind __kmp_user_lock_kind = lk_default; 3380 int __kmp_num_locks_in_block = 1; // FIXME - tune this value 3381 3382 #else // KMP_USE_DYNAMIC_LOCK 3383 3384 static void __kmp_init_tas_lock_with_checks(kmp_tas_lock_t *lck) { 3385 __kmp_init_tas_lock(lck); 3386 } 3387 3388 static void __kmp_init_nested_tas_lock_with_checks(kmp_tas_lock_t *lck) { 3389 __kmp_init_nested_tas_lock(lck); 3390 } 3391 3392 #if KMP_USE_FUTEX 3393 static void __kmp_init_futex_lock_with_checks(kmp_futex_lock_t *lck) { 3394 __kmp_init_futex_lock(lck); 3395 } 3396 3397 static void __kmp_init_nested_futex_lock_with_checks(kmp_futex_lock_t *lck) { 3398 __kmp_init_nested_futex_lock(lck); 3399 } 3400 #endif 3401 3402 static int __kmp_is_ticket_lock_initialized(kmp_ticket_lock_t *lck) { 3403 return lck == lck->lk.self; 3404 } 3405 3406 static void __kmp_init_ticket_lock_with_checks(kmp_ticket_lock_t *lck) { 3407 __kmp_init_ticket_lock(lck); 3408 } 3409 3410 static void __kmp_init_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck) { 3411 __kmp_init_nested_ticket_lock(lck); 3412 } 3413 3414 static int __kmp_is_queuing_lock_initialized(kmp_queuing_lock_t *lck) { 3415 return lck == lck->lk.initialized; 3416 } 3417 3418 static void __kmp_init_queuing_lock_with_checks(kmp_queuing_lock_t *lck) { 3419 __kmp_init_queuing_lock(lck); 3420 } 3421 3422 static void 3423 __kmp_init_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) { 3424 __kmp_init_nested_queuing_lock(lck); 3425 } 3426 3427 #if KMP_USE_ADAPTIVE_LOCKS 3428 static void __kmp_init_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck) { 3429 __kmp_init_adaptive_lock(lck); 3430 } 3431 #endif 3432 3433 static int __kmp_is_drdpa_lock_initialized(kmp_drdpa_lock_t *lck) { 3434 return lck == lck->lk.initialized; 3435 } 3436 3437 static void __kmp_init_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) { 3438 __kmp_init_drdpa_lock(lck); 3439 } 3440 3441 static void __kmp_init_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) { 3442 __kmp_init_nested_drdpa_lock(lck); 3443 } 3444 3445 /* user locks 3446 * They are implemented as a table of function pointers which are set to the 3447 * lock functions of the appropriate kind, once that has been determined. */ 3448 3449 enum kmp_lock_kind __kmp_user_lock_kind = lk_default; 3450 3451 size_t __kmp_base_user_lock_size = 0; 3452 size_t __kmp_user_lock_size = 0; 3453 3454 kmp_int32 (*__kmp_get_user_lock_owner_)(kmp_user_lock_p lck) = NULL; 3455 int (*__kmp_acquire_user_lock_with_checks_)(kmp_user_lock_p lck, 3456 kmp_int32 gtid) = NULL; 3457 3458 int (*__kmp_test_user_lock_with_checks_)(kmp_user_lock_p lck, 3459 kmp_int32 gtid) = NULL; 3460 int (*__kmp_release_user_lock_with_checks_)(kmp_user_lock_p lck, 3461 kmp_int32 gtid) = NULL; 3462 void (*__kmp_init_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL; 3463 void (*__kmp_destroy_user_lock_)(kmp_user_lock_p lck) = NULL; 3464 void (*__kmp_destroy_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL; 3465 int (*__kmp_acquire_nested_user_lock_with_checks_)(kmp_user_lock_p lck, 3466 kmp_int32 gtid) = NULL; 3467 3468 int (*__kmp_test_nested_user_lock_with_checks_)(kmp_user_lock_p lck, 3469 kmp_int32 gtid) = NULL; 3470 int (*__kmp_release_nested_user_lock_with_checks_)(kmp_user_lock_p lck, 3471 kmp_int32 gtid) = NULL; 3472 void (*__kmp_init_nested_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL; 3473 void (*__kmp_destroy_nested_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL; 3474 3475 int (*__kmp_is_user_lock_initialized_)(kmp_user_lock_p lck) = NULL; 3476 const ident_t *(*__kmp_get_user_lock_location_)(kmp_user_lock_p lck) = NULL; 3477 void (*__kmp_set_user_lock_location_)(kmp_user_lock_p lck, 3478 const ident_t *loc) = NULL; 3479 kmp_lock_flags_t (*__kmp_get_user_lock_flags_)(kmp_user_lock_p lck) = NULL; 3480 void (*__kmp_set_user_lock_flags_)(kmp_user_lock_p lck, 3481 kmp_lock_flags_t flags) = NULL; 3482 3483 void __kmp_set_user_lock_vptrs(kmp_lock_kind_t user_lock_kind) { 3484 switch (user_lock_kind) { 3485 case lk_default: 3486 default: 3487 KMP_ASSERT(0); 3488 3489 case lk_tas: { 3490 __kmp_base_user_lock_size = sizeof(kmp_base_tas_lock_t); 3491 __kmp_user_lock_size = sizeof(kmp_tas_lock_t); 3492 3493 __kmp_get_user_lock_owner_ = 3494 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_tas_lock_owner); 3495 3496 if (__kmp_env_consistency_check) { 3497 KMP_BIND_USER_LOCK_WITH_CHECKS(tas); 3498 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(tas); 3499 } else { 3500 KMP_BIND_USER_LOCK(tas); 3501 KMP_BIND_NESTED_USER_LOCK(tas); 3502 } 3503 3504 __kmp_destroy_user_lock_ = 3505 (void (*)(kmp_user_lock_p))(&__kmp_destroy_tas_lock); 3506 3507 __kmp_is_user_lock_initialized_ = (int (*)(kmp_user_lock_p))NULL; 3508 3509 __kmp_get_user_lock_location_ = (const ident_t *(*)(kmp_user_lock_p))NULL; 3510 3511 __kmp_set_user_lock_location_ = 3512 (void (*)(kmp_user_lock_p, const ident_t *))NULL; 3513 3514 __kmp_get_user_lock_flags_ = (kmp_lock_flags_t(*)(kmp_user_lock_p))NULL; 3515 3516 __kmp_set_user_lock_flags_ = 3517 (void (*)(kmp_user_lock_p, kmp_lock_flags_t))NULL; 3518 } break; 3519 3520 #if KMP_USE_FUTEX 3521 3522 case lk_futex: { 3523 __kmp_base_user_lock_size = sizeof(kmp_base_futex_lock_t); 3524 __kmp_user_lock_size = sizeof(kmp_futex_lock_t); 3525 3526 __kmp_get_user_lock_owner_ = 3527 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_futex_lock_owner); 3528 3529 if (__kmp_env_consistency_check) { 3530 KMP_BIND_USER_LOCK_WITH_CHECKS(futex); 3531 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(futex); 3532 } else { 3533 KMP_BIND_USER_LOCK(futex); 3534 KMP_BIND_NESTED_USER_LOCK(futex); 3535 } 3536 3537 __kmp_destroy_user_lock_ = 3538 (void (*)(kmp_user_lock_p))(&__kmp_destroy_futex_lock); 3539 3540 __kmp_is_user_lock_initialized_ = (int (*)(kmp_user_lock_p))NULL; 3541 3542 __kmp_get_user_lock_location_ = (const ident_t *(*)(kmp_user_lock_p))NULL; 3543 3544 __kmp_set_user_lock_location_ = 3545 (void (*)(kmp_user_lock_p, const ident_t *))NULL; 3546 3547 __kmp_get_user_lock_flags_ = (kmp_lock_flags_t(*)(kmp_user_lock_p))NULL; 3548 3549 __kmp_set_user_lock_flags_ = 3550 (void (*)(kmp_user_lock_p, kmp_lock_flags_t))NULL; 3551 } break; 3552 3553 #endif // KMP_USE_FUTEX 3554 3555 case lk_ticket: { 3556 __kmp_base_user_lock_size = sizeof(kmp_base_ticket_lock_t); 3557 __kmp_user_lock_size = sizeof(kmp_ticket_lock_t); 3558 3559 __kmp_get_user_lock_owner_ = 3560 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_owner); 3561 3562 if (__kmp_env_consistency_check) { 3563 KMP_BIND_USER_LOCK_WITH_CHECKS(ticket); 3564 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(ticket); 3565 } else { 3566 KMP_BIND_USER_LOCK(ticket); 3567 KMP_BIND_NESTED_USER_LOCK(ticket); 3568 } 3569 3570 __kmp_destroy_user_lock_ = 3571 (void (*)(kmp_user_lock_p))(&__kmp_destroy_ticket_lock); 3572 3573 __kmp_is_user_lock_initialized_ = 3574 (int (*)(kmp_user_lock_p))(&__kmp_is_ticket_lock_initialized); 3575 3576 __kmp_get_user_lock_location_ = 3577 (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_location); 3578 3579 __kmp_set_user_lock_location_ = (void (*)( 3580 kmp_user_lock_p, const ident_t *))(&__kmp_set_ticket_lock_location); 3581 3582 __kmp_get_user_lock_flags_ = 3583 (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_flags); 3584 3585 __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))( 3586 &__kmp_set_ticket_lock_flags); 3587 } break; 3588 3589 case lk_queuing: { 3590 __kmp_base_user_lock_size = sizeof(kmp_base_queuing_lock_t); 3591 __kmp_user_lock_size = sizeof(kmp_queuing_lock_t); 3592 3593 __kmp_get_user_lock_owner_ = 3594 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_owner); 3595 3596 if (__kmp_env_consistency_check) { 3597 KMP_BIND_USER_LOCK_WITH_CHECKS(queuing); 3598 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(queuing); 3599 } else { 3600 KMP_BIND_USER_LOCK(queuing); 3601 KMP_BIND_NESTED_USER_LOCK(queuing); 3602 } 3603 3604 __kmp_destroy_user_lock_ = 3605 (void (*)(kmp_user_lock_p))(&__kmp_destroy_queuing_lock); 3606 3607 __kmp_is_user_lock_initialized_ = 3608 (int (*)(kmp_user_lock_p))(&__kmp_is_queuing_lock_initialized); 3609 3610 __kmp_get_user_lock_location_ = 3611 (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_location); 3612 3613 __kmp_set_user_lock_location_ = (void (*)( 3614 kmp_user_lock_p, const ident_t *))(&__kmp_set_queuing_lock_location); 3615 3616 __kmp_get_user_lock_flags_ = 3617 (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_flags); 3618 3619 __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))( 3620 &__kmp_set_queuing_lock_flags); 3621 } break; 3622 3623 #if KMP_USE_ADAPTIVE_LOCKS 3624 case lk_adaptive: { 3625 __kmp_base_user_lock_size = sizeof(kmp_base_adaptive_lock_t); 3626 __kmp_user_lock_size = sizeof(kmp_adaptive_lock_t); 3627 3628 __kmp_get_user_lock_owner_ = 3629 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_owner); 3630 3631 if (__kmp_env_consistency_check) { 3632 KMP_BIND_USER_LOCK_WITH_CHECKS(adaptive); 3633 } else { 3634 KMP_BIND_USER_LOCK(adaptive); 3635 } 3636 3637 __kmp_destroy_user_lock_ = 3638 (void (*)(kmp_user_lock_p))(&__kmp_destroy_adaptive_lock); 3639 3640 __kmp_is_user_lock_initialized_ = 3641 (int (*)(kmp_user_lock_p))(&__kmp_is_queuing_lock_initialized); 3642 3643 __kmp_get_user_lock_location_ = 3644 (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_location); 3645 3646 __kmp_set_user_lock_location_ = (void (*)( 3647 kmp_user_lock_p, const ident_t *))(&__kmp_set_queuing_lock_location); 3648 3649 __kmp_get_user_lock_flags_ = 3650 (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_flags); 3651 3652 __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))( 3653 &__kmp_set_queuing_lock_flags); 3654 3655 } break; 3656 #endif // KMP_USE_ADAPTIVE_LOCKS 3657 3658 case lk_drdpa: { 3659 __kmp_base_user_lock_size = sizeof(kmp_base_drdpa_lock_t); 3660 __kmp_user_lock_size = sizeof(kmp_drdpa_lock_t); 3661 3662 __kmp_get_user_lock_owner_ = 3663 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_owner); 3664 3665 if (__kmp_env_consistency_check) { 3666 KMP_BIND_USER_LOCK_WITH_CHECKS(drdpa); 3667 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(drdpa); 3668 } else { 3669 KMP_BIND_USER_LOCK(drdpa); 3670 KMP_BIND_NESTED_USER_LOCK(drdpa); 3671 } 3672 3673 __kmp_destroy_user_lock_ = 3674 (void (*)(kmp_user_lock_p))(&__kmp_destroy_drdpa_lock); 3675 3676 __kmp_is_user_lock_initialized_ = 3677 (int (*)(kmp_user_lock_p))(&__kmp_is_drdpa_lock_initialized); 3678 3679 __kmp_get_user_lock_location_ = 3680 (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_location); 3681 3682 __kmp_set_user_lock_location_ = (void (*)( 3683 kmp_user_lock_p, const ident_t *))(&__kmp_set_drdpa_lock_location); 3684 3685 __kmp_get_user_lock_flags_ = 3686 (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_flags); 3687 3688 __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))( 3689 &__kmp_set_drdpa_lock_flags); 3690 } break; 3691 } 3692 } 3693 3694 // ---------------------------------------------------------------------------- 3695 // User lock table & lock allocation 3696 3697 kmp_lock_table_t __kmp_user_lock_table = {1, 0, NULL}; 3698 kmp_user_lock_p __kmp_lock_pool = NULL; 3699 3700 // Lock block-allocation support. 3701 kmp_block_of_locks *__kmp_lock_blocks = NULL; 3702 int __kmp_num_locks_in_block = 1; // FIXME - tune this value 3703 3704 static kmp_lock_index_t __kmp_lock_table_insert(kmp_user_lock_p lck) { 3705 // Assume that kmp_global_lock is held upon entry/exit. 3706 kmp_lock_index_t index; 3707 if (__kmp_user_lock_table.used >= __kmp_user_lock_table.allocated) { 3708 kmp_lock_index_t size; 3709 kmp_user_lock_p *table; 3710 // Reallocate lock table. 3711 if (__kmp_user_lock_table.allocated == 0) { 3712 size = 1024; 3713 } else { 3714 size = __kmp_user_lock_table.allocated * 2; 3715 } 3716 table = (kmp_user_lock_p *)__kmp_allocate(sizeof(kmp_user_lock_p) * size); 3717 KMP_MEMCPY(table + 1, __kmp_user_lock_table.table + 1, 3718 sizeof(kmp_user_lock_p) * (__kmp_user_lock_table.used - 1)); 3719 table[0] = (kmp_user_lock_p)__kmp_user_lock_table.table; 3720 // We cannot free the previous table now, since it may be in use by other 3721 // threads. So save the pointer to the previous table in in the first 3722 // element of the new table. All the tables will be organized into a list, 3723 // and could be freed when library shutting down. 3724 __kmp_user_lock_table.table = table; 3725 __kmp_user_lock_table.allocated = size; 3726 } 3727 KMP_DEBUG_ASSERT(__kmp_user_lock_table.used < 3728 __kmp_user_lock_table.allocated); 3729 index = __kmp_user_lock_table.used; 3730 __kmp_user_lock_table.table[index] = lck; 3731 ++__kmp_user_lock_table.used; 3732 return index; 3733 } 3734 3735 static kmp_user_lock_p __kmp_lock_block_allocate() { 3736 // Assume that kmp_global_lock is held upon entry/exit. 3737 static int last_index = 0; 3738 if ((last_index >= __kmp_num_locks_in_block) || (__kmp_lock_blocks == NULL)) { 3739 // Restart the index. 3740 last_index = 0; 3741 // Need to allocate a new block. 3742 KMP_DEBUG_ASSERT(__kmp_user_lock_size > 0); 3743 size_t space_for_locks = __kmp_user_lock_size * __kmp_num_locks_in_block; 3744 char *buffer = 3745 (char *)__kmp_allocate(space_for_locks + sizeof(kmp_block_of_locks)); 3746 // Set up the new block. 3747 kmp_block_of_locks *new_block = 3748 (kmp_block_of_locks *)(&buffer[space_for_locks]); 3749 new_block->next_block = __kmp_lock_blocks; 3750 new_block->locks = (void *)buffer; 3751 // Publish the new block. 3752 KMP_MB(); 3753 __kmp_lock_blocks = new_block; 3754 } 3755 kmp_user_lock_p ret = (kmp_user_lock_p)(&( 3756 ((char *)(__kmp_lock_blocks->locks))[last_index * __kmp_user_lock_size])); 3757 last_index++; 3758 return ret; 3759 } 3760 3761 // Get memory for a lock. It may be freshly allocated memory or reused memory 3762 // from lock pool. 3763 kmp_user_lock_p __kmp_user_lock_allocate(void **user_lock, kmp_int32 gtid, 3764 kmp_lock_flags_t flags) { 3765 kmp_user_lock_p lck; 3766 kmp_lock_index_t index; 3767 KMP_DEBUG_ASSERT(user_lock); 3768 3769 __kmp_acquire_lock(&__kmp_global_lock, gtid); 3770 3771 if (__kmp_lock_pool == NULL) { 3772 // Lock pool is empty. Allocate new memory. 3773 3774 // ANNOTATION: Found no good way to express the syncronisation 3775 // between allocation and usage, so ignore the allocation 3776 ANNOTATE_IGNORE_WRITES_BEGIN(); 3777 if (__kmp_num_locks_in_block <= 1) { // Tune this cutoff point. 3778 lck = (kmp_user_lock_p)__kmp_allocate(__kmp_user_lock_size); 3779 } else { 3780 lck = __kmp_lock_block_allocate(); 3781 } 3782 ANNOTATE_IGNORE_WRITES_END(); 3783 3784 // Insert lock in the table so that it can be freed in __kmp_cleanup, 3785 // and debugger has info on all allocated locks. 3786 index = __kmp_lock_table_insert(lck); 3787 } else { 3788 // Pick up lock from pool. 3789 lck = __kmp_lock_pool; 3790 index = __kmp_lock_pool->pool.index; 3791 __kmp_lock_pool = __kmp_lock_pool->pool.next; 3792 } 3793 3794 // We could potentially differentiate between nested and regular locks 3795 // here, and do the lock table lookup for regular locks only. 3796 if (OMP_LOCK_T_SIZE < sizeof(void *)) { 3797 *((kmp_lock_index_t *)user_lock) = index; 3798 } else { 3799 *((kmp_user_lock_p *)user_lock) = lck; 3800 } 3801 3802 // mark the lock if it is critical section lock. 3803 __kmp_set_user_lock_flags(lck, flags); 3804 3805 __kmp_release_lock(&__kmp_global_lock, gtid); // AC: TODO move this line upper 3806 3807 return lck; 3808 } 3809 3810 // Put lock's memory to pool for reusing. 3811 void __kmp_user_lock_free(void **user_lock, kmp_int32 gtid, 3812 kmp_user_lock_p lck) { 3813 KMP_DEBUG_ASSERT(user_lock != NULL); 3814 KMP_DEBUG_ASSERT(lck != NULL); 3815 3816 __kmp_acquire_lock(&__kmp_global_lock, gtid); 3817 3818 lck->pool.next = __kmp_lock_pool; 3819 __kmp_lock_pool = lck; 3820 if (OMP_LOCK_T_SIZE < sizeof(void *)) { 3821 kmp_lock_index_t index = *((kmp_lock_index_t *)user_lock); 3822 KMP_DEBUG_ASSERT(0 < index && index <= __kmp_user_lock_table.used); 3823 lck->pool.index = index; 3824 } 3825 3826 __kmp_release_lock(&__kmp_global_lock, gtid); 3827 } 3828 3829 kmp_user_lock_p __kmp_lookup_user_lock(void **user_lock, char const *func) { 3830 kmp_user_lock_p lck = NULL; 3831 3832 if (__kmp_env_consistency_check) { 3833 if (user_lock == NULL) { 3834 KMP_FATAL(LockIsUninitialized, func); 3835 } 3836 } 3837 3838 if (OMP_LOCK_T_SIZE < sizeof(void *)) { 3839 kmp_lock_index_t index = *((kmp_lock_index_t *)user_lock); 3840 if (__kmp_env_consistency_check) { 3841 if (!(0 < index && index < __kmp_user_lock_table.used)) { 3842 KMP_FATAL(LockIsUninitialized, func); 3843 } 3844 } 3845 KMP_DEBUG_ASSERT(0 < index && index < __kmp_user_lock_table.used); 3846 KMP_DEBUG_ASSERT(__kmp_user_lock_size > 0); 3847 lck = __kmp_user_lock_table.table[index]; 3848 } else { 3849 lck = *((kmp_user_lock_p *)user_lock); 3850 } 3851 3852 if (__kmp_env_consistency_check) { 3853 if (lck == NULL) { 3854 KMP_FATAL(LockIsUninitialized, func); 3855 } 3856 } 3857 3858 return lck; 3859 } 3860 3861 void __kmp_cleanup_user_locks(void) { 3862 // Reset lock pool. Don't worry about lock in the pool--we will free them when 3863 // iterating through lock table (it includes all the locks, dead or alive). 3864 __kmp_lock_pool = NULL; 3865 3866 #define IS_CRITICAL(lck) \ 3867 ((__kmp_get_user_lock_flags_ != NULL) && \ 3868 ((*__kmp_get_user_lock_flags_)(lck)&kmp_lf_critical_section)) 3869 3870 // Loop through lock table, free all locks. 3871 // Do not free item [0], it is reserved for lock tables list. 3872 // 3873 // FIXME - we are iterating through a list of (pointers to) objects of type 3874 // union kmp_user_lock, but we have no way of knowing whether the base type is 3875 // currently "pool" or whatever the global user lock type is. 3876 // 3877 // We are relying on the fact that for all of the user lock types 3878 // (except "tas"), the first field in the lock struct is the "initialized" 3879 // field, which is set to the address of the lock object itself when 3880 // the lock is initialized. When the union is of type "pool", the 3881 // first field is a pointer to the next object in the free list, which 3882 // will not be the same address as the object itself. 3883 // 3884 // This means that the check (*__kmp_is_user_lock_initialized_)(lck) will fail 3885 // for "pool" objects on the free list. This must happen as the "location" 3886 // field of real user locks overlaps the "index" field of "pool" objects. 3887 // 3888 // It would be better to run through the free list, and remove all "pool" 3889 // objects from the lock table before executing this loop. However, 3890 // "pool" objects do not always have their index field set (only on 3891 // lin_32e), and I don't want to search the lock table for the address 3892 // of every "pool" object on the free list. 3893 while (__kmp_user_lock_table.used > 1) { 3894 const ident *loc; 3895 3896 // reduce __kmp_user_lock_table.used before freeing the lock, 3897 // so that state of locks is consistent 3898 kmp_user_lock_p lck = 3899 __kmp_user_lock_table.table[--__kmp_user_lock_table.used]; 3900 3901 if ((__kmp_is_user_lock_initialized_ != NULL) && 3902 (*__kmp_is_user_lock_initialized_)(lck)) { 3903 // Issue a warning if: KMP_CONSISTENCY_CHECK AND lock is initialized AND 3904 // it is NOT a critical section (user is not responsible for destroying 3905 // criticals) AND we know source location to report. 3906 if (__kmp_env_consistency_check && (!IS_CRITICAL(lck)) && 3907 ((loc = __kmp_get_user_lock_location(lck)) != NULL) && 3908 (loc->psource != NULL)) { 3909 kmp_str_loc_t str_loc = __kmp_str_loc_init(loc->psource, 0); 3910 KMP_WARNING(CnsLockNotDestroyed, str_loc.file, str_loc.line); 3911 __kmp_str_loc_free(&str_loc); 3912 } 3913 3914 #ifdef KMP_DEBUG 3915 if (IS_CRITICAL(lck)) { 3916 KA_TRACE( 3917 20, 3918 ("__kmp_cleanup_user_locks: free critical section lock %p (%p)\n", 3919 lck, *(void **)lck)); 3920 } else { 3921 KA_TRACE(20, ("__kmp_cleanup_user_locks: free lock %p (%p)\n", lck, 3922 *(void **)lck)); 3923 } 3924 #endif // KMP_DEBUG 3925 3926 // Cleanup internal lock dynamic resources (for drdpa locks particularly). 3927 __kmp_destroy_user_lock(lck); 3928 } 3929 3930 // Free the lock if block allocation of locks is not used. 3931 if (__kmp_lock_blocks == NULL) { 3932 __kmp_free(lck); 3933 } 3934 } 3935 3936 #undef IS_CRITICAL 3937 3938 // delete lock table(s). 3939 kmp_user_lock_p *table_ptr = __kmp_user_lock_table.table; 3940 __kmp_user_lock_table.table = NULL; 3941 __kmp_user_lock_table.allocated = 0; 3942 3943 while (table_ptr != NULL) { 3944 // In the first element we saved the pointer to the previous 3945 // (smaller) lock table. 3946 kmp_user_lock_p *next = (kmp_user_lock_p *)(table_ptr[0]); 3947 __kmp_free(table_ptr); 3948 table_ptr = next; 3949 } 3950 3951 // Free buffers allocated for blocks of locks. 3952 kmp_block_of_locks_t *block_ptr = __kmp_lock_blocks; 3953 __kmp_lock_blocks = NULL; 3954 3955 while (block_ptr != NULL) { 3956 kmp_block_of_locks_t *next = block_ptr->next_block; 3957 __kmp_free(block_ptr->locks); 3958 // *block_ptr itself was allocated at the end of the locks vector. 3959 block_ptr = next; 3960 } 3961 3962 TCW_4(__kmp_init_user_locks, FALSE); 3963 } 3964 3965 #endif // KMP_USE_DYNAMIC_LOCK 3966