runtime/src/kmp_lock.cpp

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