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