LLVM OpenMP* Runtime Library
kmp_lock.cpp
1 /*
2  * kmp_lock.cpp -- lock-related functions
3  */
4 
5 //===----------------------------------------------------------------------===//
6 //
7 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
8 // See https://llvm.org/LICENSE.txt for license information.
9 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include <stddef.h>
14 #include <atomic>
15 
16 #include "kmp.h"
17 #include "kmp_i18n.h"
18 #include "kmp_io.h"
19 #include "kmp_itt.h"
20 #include "kmp_lock.h"
21 #include "kmp_wait_release.h"
22 #include "kmp_wrapper_getpid.h"
23 
24 #include "tsan_annotations.h"
25 
26 #if KMP_USE_FUTEX
27 #include <sys/syscall.h>
28 #include <unistd.h>
29 // We should really include <futex.h>, but that causes compatibility problems on
30 // different Linux* OS distributions that either require that you include (or
31 // break when you try to include) <pci/types.h>. Since all we need is the two
32 // macros below (which are part of the kernel ABI, so can't change) we just
33 // define the constants here and don't include <futex.h>
34 #ifndef FUTEX_WAIT
35 #define FUTEX_WAIT 0
36 #endif
37 #ifndef FUTEX_WAKE
38 #define FUTEX_WAKE 1
39 #endif
40 #endif
41 
42 /* Implement spin locks for internal library use. */
43 /* The algorithm implemented is Lamport's bakery lock [1974]. */
44 
45 void __kmp_validate_locks(void) {
46  int i;
47  kmp_uint32 x, y;
48 
49  /* Check to make sure unsigned arithmetic does wraps properly */
50  x = ~((kmp_uint32)0) - 2;
51  y = x - 2;
52 
53  for (i = 0; i < 8; ++i, ++x, ++y) {
54  kmp_uint32 z = (x - y);
55  KMP_ASSERT(z == 2);
56  }
57 
58  KMP_ASSERT(offsetof(kmp_base_queuing_lock, tail_id) % 8 == 0);
59 }
60 
61 /* ------------------------------------------------------------------------ */
62 /* test and set locks */
63 
64 // For the non-nested locks, we can only assume that the first 4 bytes were
65 // allocated, since gcc only allocates 4 bytes for omp_lock_t, and the Intel
66 // compiler only allocates a 4 byte pointer on IA-32 architecture. On
67 // Windows* OS on Intel(R) 64, we can assume that all 8 bytes were allocated.
68 //
69 // gcc reserves >= 8 bytes for nested locks, so we can assume that the
70 // entire 8 bytes were allocated for nested locks on all 64-bit platforms.
71 
72 static kmp_int32 __kmp_get_tas_lock_owner(kmp_tas_lock_t *lck) {
73  return KMP_LOCK_STRIP(KMP_ATOMIC_LD_RLX(&lck->lk.poll)) - 1;
74 }
75 
76 static inline bool __kmp_is_tas_lock_nestable(kmp_tas_lock_t *lck) {
77  return lck->lk.depth_locked != -1;
78 }
79 
80 __forceinline static int
81 __kmp_acquire_tas_lock_timed_template(kmp_tas_lock_t *lck, kmp_int32 gtid) {
82  KMP_MB();
83 
84 #ifdef USE_LOCK_PROFILE
85  kmp_uint32 curr = KMP_LOCK_STRIP(lck->lk.poll);
86  if ((curr != 0) && (curr != gtid + 1))
87  __kmp_printf("LOCK CONTENTION: %p\n", lck);
88 /* else __kmp_printf( "." );*/
89 #endif /* USE_LOCK_PROFILE */
90 
91  kmp_int32 tas_free = KMP_LOCK_FREE(tas);
92  kmp_int32 tas_busy = KMP_LOCK_BUSY(gtid + 1, tas);
93 
94  if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == tas_free &&
95  __kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) {
96  KMP_FSYNC_ACQUIRED(lck);
97  return KMP_LOCK_ACQUIRED_FIRST;
98  }
99 
100  kmp_uint32 spins;
101  KMP_FSYNC_PREPARE(lck);
102  KMP_INIT_YIELD(spins);
103  kmp_backoff_t backoff = __kmp_spin_backoff_params;
104  do {
105  __kmp_spin_backoff(&backoff);
106  KMP_YIELD_OVERSUB_ELSE_SPIN(spins);
107  } while (KMP_ATOMIC_LD_RLX(&lck->lk.poll) != tas_free ||
108  !__kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy));
109  KMP_FSYNC_ACQUIRED(lck);
110  return KMP_LOCK_ACQUIRED_FIRST;
111 }
112 
113 int __kmp_acquire_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
114  int retval = __kmp_acquire_tas_lock_timed_template(lck, gtid);
115  ANNOTATE_TAS_ACQUIRED(lck);
116  return retval;
117 }
118 
119 static int __kmp_acquire_tas_lock_with_checks(kmp_tas_lock_t *lck,
120  kmp_int32 gtid) {
121  char const *const func = "omp_set_lock";
122  if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) &&
123  __kmp_is_tas_lock_nestable(lck)) {
124  KMP_FATAL(LockNestableUsedAsSimple, func);
125  }
126  if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) == gtid)) {
127  KMP_FATAL(LockIsAlreadyOwned, func);
128  }
129  return __kmp_acquire_tas_lock(lck, gtid);
130 }
131 
132 int __kmp_test_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
133  kmp_int32 tas_free = KMP_LOCK_FREE(tas);
134  kmp_int32 tas_busy = KMP_LOCK_BUSY(gtid + 1, tas);
135  if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == tas_free &&
136  __kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) {
137  KMP_FSYNC_ACQUIRED(lck);
138  return TRUE;
139  }
140  return FALSE;
141 }
142 
143 static int __kmp_test_tas_lock_with_checks(kmp_tas_lock_t *lck,
144  kmp_int32 gtid) {
145  char const *const func = "omp_test_lock";
146  if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) &&
147  __kmp_is_tas_lock_nestable(lck)) {
148  KMP_FATAL(LockNestableUsedAsSimple, func);
149  }
150  return __kmp_test_tas_lock(lck, gtid);
151 }
152 
153 int __kmp_release_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
154  KMP_MB(); /* Flush all pending memory write invalidates. */
155 
156  KMP_FSYNC_RELEASING(lck);
157  ANNOTATE_TAS_RELEASED(lck);
158  KMP_ATOMIC_ST_REL(&lck->lk.poll, KMP_LOCK_FREE(tas));
159  KMP_MB(); /* Flush all pending memory write invalidates. */
160 
161  KMP_YIELD_OVERSUB();
162  return KMP_LOCK_RELEASED;
163 }
164 
165 static int __kmp_release_tas_lock_with_checks(kmp_tas_lock_t *lck,
166  kmp_int32 gtid) {
167  char const *const func = "omp_unset_lock";
168  KMP_MB(); /* in case another processor initialized lock */
169  if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) &&
170  __kmp_is_tas_lock_nestable(lck)) {
171  KMP_FATAL(LockNestableUsedAsSimple, func);
172  }
173  if (__kmp_get_tas_lock_owner(lck) == -1) {
174  KMP_FATAL(LockUnsettingFree, func);
175  }
176  if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) >= 0) &&
177  (__kmp_get_tas_lock_owner(lck) != gtid)) {
178  KMP_FATAL(LockUnsettingSetByAnother, func);
179  }
180  return __kmp_release_tas_lock(lck, gtid);
181 }
182 
183 void __kmp_init_tas_lock(kmp_tas_lock_t *lck) {
184  lck->lk.poll = KMP_LOCK_FREE(tas);
185 }
186 
187 void __kmp_destroy_tas_lock(kmp_tas_lock_t *lck) { lck->lk.poll = 0; }
188 
189 static void __kmp_destroy_tas_lock_with_checks(kmp_tas_lock_t *lck) {
190  char const *const func = "omp_destroy_lock";
191  if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) &&
192  __kmp_is_tas_lock_nestable(lck)) {
193  KMP_FATAL(LockNestableUsedAsSimple, func);
194  }
195  if (__kmp_get_tas_lock_owner(lck) != -1) {
196  KMP_FATAL(LockStillOwned, func);
197  }
198  __kmp_destroy_tas_lock(lck);
199 }
200 
201 // nested test and set locks
202 
203 int __kmp_acquire_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
204  KMP_DEBUG_ASSERT(gtid >= 0);
205 
206  if (__kmp_get_tas_lock_owner(lck) == gtid) {
207  lck->lk.depth_locked += 1;
208  return KMP_LOCK_ACQUIRED_NEXT;
209  } else {
210  __kmp_acquire_tas_lock_timed_template(lck, gtid);
211  ANNOTATE_TAS_ACQUIRED(lck);
212  lck->lk.depth_locked = 1;
213  return KMP_LOCK_ACQUIRED_FIRST;
214  }
215 }
216 
217 static int __kmp_acquire_nested_tas_lock_with_checks(kmp_tas_lock_t *lck,
218  kmp_int32 gtid) {
219  char const *const func = "omp_set_nest_lock";
220  if (!__kmp_is_tas_lock_nestable(lck)) {
221  KMP_FATAL(LockSimpleUsedAsNestable, func);
222  }
223  return __kmp_acquire_nested_tas_lock(lck, gtid);
224 }
225 
226 int __kmp_test_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
227  int retval;
228 
229  KMP_DEBUG_ASSERT(gtid >= 0);
230 
231  if (__kmp_get_tas_lock_owner(lck) == gtid) {
232  retval = ++lck->lk.depth_locked;
233  } else if (!__kmp_test_tas_lock(lck, gtid)) {
234  retval = 0;
235  } else {
236  KMP_MB();
237  retval = lck->lk.depth_locked = 1;
238  }
239  return retval;
240 }
241 
242 static int __kmp_test_nested_tas_lock_with_checks(kmp_tas_lock_t *lck,
243  kmp_int32 gtid) {
244  char const *const func = "omp_test_nest_lock";
245  if (!__kmp_is_tas_lock_nestable(lck)) {
246  KMP_FATAL(LockSimpleUsedAsNestable, func);
247  }
248  return __kmp_test_nested_tas_lock(lck, gtid);
249 }
250 
251 int __kmp_release_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
252  KMP_DEBUG_ASSERT(gtid >= 0);
253 
254  KMP_MB();
255  if (--(lck->lk.depth_locked) == 0) {
256  __kmp_release_tas_lock(lck, gtid);
257  return KMP_LOCK_RELEASED;
258  }
259  return KMP_LOCK_STILL_HELD;
260 }
261 
262 static int __kmp_release_nested_tas_lock_with_checks(kmp_tas_lock_t *lck,
263  kmp_int32 gtid) {
264  char const *const func = "omp_unset_nest_lock";
265  KMP_MB(); /* in case another processor initialized lock */
266  if (!__kmp_is_tas_lock_nestable(lck)) {
267  KMP_FATAL(LockSimpleUsedAsNestable, func);
268  }
269  if (__kmp_get_tas_lock_owner(lck) == -1) {
270  KMP_FATAL(LockUnsettingFree, func);
271  }
272  if (__kmp_get_tas_lock_owner(lck) != gtid) {
273  KMP_FATAL(LockUnsettingSetByAnother, func);
274  }
275  return __kmp_release_nested_tas_lock(lck, gtid);
276 }
277 
278 void __kmp_init_nested_tas_lock(kmp_tas_lock_t *lck) {
279  __kmp_init_tas_lock(lck);
280  lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
281 }
282 
283 void __kmp_destroy_nested_tas_lock(kmp_tas_lock_t *lck) {
284  __kmp_destroy_tas_lock(lck);
285  lck->lk.depth_locked = 0;
286 }
287 
288 static void __kmp_destroy_nested_tas_lock_with_checks(kmp_tas_lock_t *lck) {
289  char const *const func = "omp_destroy_nest_lock";
290  if (!__kmp_is_tas_lock_nestable(lck)) {
291  KMP_FATAL(LockSimpleUsedAsNestable, func);
292  }
293  if (__kmp_get_tas_lock_owner(lck) != -1) {
294  KMP_FATAL(LockStillOwned, func);
295  }
296  __kmp_destroy_nested_tas_lock(lck);
297 }
298 
299 #if KMP_USE_FUTEX
300 
301 /* ------------------------------------------------------------------------ */
302 /* futex locks */
303 
304 // futex locks are really just test and set locks, with a different method
305 // of handling contention. They take the same amount of space as test and
306 // set locks, and are allocated the same way (i.e. use the area allocated by
307 // the compiler for non-nested locks / allocate nested locks on the heap).
308 
309 static kmp_int32 __kmp_get_futex_lock_owner(kmp_futex_lock_t *lck) {
310  return KMP_LOCK_STRIP((TCR_4(lck->lk.poll) >> 1)) - 1;
311 }
312 
313 static inline bool __kmp_is_futex_lock_nestable(kmp_futex_lock_t *lck) {
314  return lck->lk.depth_locked != -1;
315 }
316 
317 __forceinline static int
318 __kmp_acquire_futex_lock_timed_template(kmp_futex_lock_t *lck, kmp_int32 gtid) {
319  kmp_int32 gtid_code = (gtid + 1) << 1;
320 
321  KMP_MB();
322 
323 #ifdef USE_LOCK_PROFILE
324  kmp_uint32 curr = KMP_LOCK_STRIP(TCR_4(lck->lk.poll));
325  if ((curr != 0) && (curr != gtid_code))
326  __kmp_printf("LOCK CONTENTION: %p\n", lck);
327 /* else __kmp_printf( "." );*/
328 #endif /* USE_LOCK_PROFILE */
329 
330  KMP_FSYNC_PREPARE(lck);
331  KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d entering\n",
332  lck, lck->lk.poll, gtid));
333 
334  kmp_int32 poll_val;
335 
336  while ((poll_val = KMP_COMPARE_AND_STORE_RET32(
337  &(lck->lk.poll), KMP_LOCK_FREE(futex),
338  KMP_LOCK_BUSY(gtid_code, futex))) != KMP_LOCK_FREE(futex)) {
339 
340  kmp_int32 cond = KMP_LOCK_STRIP(poll_val) & 1;
341  KA_TRACE(
342  1000,
343  ("__kmp_acquire_futex_lock: lck:%p, T#%d poll_val = 0x%x cond = 0x%x\n",
344  lck, gtid, poll_val, cond));
345 
346  // NOTE: if you try to use the following condition for this branch
347  //
348  // if ( poll_val & 1 == 0 )
349  //
350  // Then the 12.0 compiler has a bug where the following block will
351  // always be skipped, regardless of the value of the LSB of poll_val.
352  if (!cond) {
353  // Try to set the lsb in the poll to indicate to the owner
354  // thread that they need to wake this thread up.
355  if (!KMP_COMPARE_AND_STORE_REL32(&(lck->lk.poll), poll_val,
356  poll_val | KMP_LOCK_BUSY(1, futex))) {
357  KA_TRACE(
358  1000,
359  ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d can't set bit 0\n",
360  lck, lck->lk.poll, gtid));
361  continue;
362  }
363  poll_val |= KMP_LOCK_BUSY(1, futex);
364 
365  KA_TRACE(1000,
366  ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d bit 0 set\n", lck,
367  lck->lk.poll, gtid));
368  }
369 
370  KA_TRACE(
371  1000,
372  ("__kmp_acquire_futex_lock: lck:%p, T#%d before futex_wait(0x%x)\n",
373  lck, gtid, poll_val));
374 
375  kmp_int32 rc;
376  if ((rc = syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAIT, poll_val, NULL,
377  NULL, 0)) != 0) {
378  KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p, T#%d futex_wait(0x%x) "
379  "failed (rc=%d errno=%d)\n",
380  lck, gtid, poll_val, rc, errno));
381  continue;
382  }
383 
384  KA_TRACE(1000,
385  ("__kmp_acquire_futex_lock: lck:%p, T#%d after futex_wait(0x%x)\n",
386  lck, gtid, poll_val));
387  // This thread has now done a successful futex wait call and was entered on
388  // the OS futex queue. We must now perform a futex wake call when releasing
389  // the lock, as we have no idea how many other threads are in the queue.
390  gtid_code |= 1;
391  }
392 
393  KMP_FSYNC_ACQUIRED(lck);
394  KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d exiting\n", lck,
395  lck->lk.poll, gtid));
396  return KMP_LOCK_ACQUIRED_FIRST;
397 }
398 
399 int __kmp_acquire_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
400  int retval = __kmp_acquire_futex_lock_timed_template(lck, gtid);
401  ANNOTATE_FUTEX_ACQUIRED(lck);
402  return retval;
403 }
404 
405 static int __kmp_acquire_futex_lock_with_checks(kmp_futex_lock_t *lck,
406  kmp_int32 gtid) {
407  char const *const func = "omp_set_lock";
408  if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) &&
409  __kmp_is_futex_lock_nestable(lck)) {
410  KMP_FATAL(LockNestableUsedAsSimple, func);
411  }
412  if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) == gtid)) {
413  KMP_FATAL(LockIsAlreadyOwned, func);
414  }
415  return __kmp_acquire_futex_lock(lck, gtid);
416 }
417 
418 int __kmp_test_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
419  if (KMP_COMPARE_AND_STORE_ACQ32(&(lck->lk.poll), KMP_LOCK_FREE(futex),
420  KMP_LOCK_BUSY((gtid + 1) << 1, futex))) {
421  KMP_FSYNC_ACQUIRED(lck);
422  return TRUE;
423  }
424  return FALSE;
425 }
426 
427 static int __kmp_test_futex_lock_with_checks(kmp_futex_lock_t *lck,
428  kmp_int32 gtid) {
429  char const *const func = "omp_test_lock";
430  if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) &&
431  __kmp_is_futex_lock_nestable(lck)) {
432  KMP_FATAL(LockNestableUsedAsSimple, func);
433  }
434  return __kmp_test_futex_lock(lck, gtid);
435 }
436 
437 int __kmp_release_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
438  KMP_MB(); /* Flush all pending memory write invalidates. */
439 
440  KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d entering\n",
441  lck, lck->lk.poll, gtid));
442 
443  KMP_FSYNC_RELEASING(lck);
444  ANNOTATE_FUTEX_RELEASED(lck);
445 
446  kmp_int32 poll_val = KMP_XCHG_FIXED32(&(lck->lk.poll), KMP_LOCK_FREE(futex));
447 
448  KA_TRACE(1000,
449  ("__kmp_release_futex_lock: lck:%p, T#%d released poll_val = 0x%x\n",
450  lck, gtid, poll_val));
451 
452  if (KMP_LOCK_STRIP(poll_val) & 1) {
453  KA_TRACE(1000,
454  ("__kmp_release_futex_lock: lck:%p, T#%d futex_wake 1 thread\n",
455  lck, gtid));
456  syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAKE, KMP_LOCK_BUSY(1, futex),
457  NULL, NULL, 0);
458  }
459 
460  KMP_MB(); /* Flush all pending memory write invalidates. */
461 
462  KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d exiting\n", lck,
463  lck->lk.poll, gtid));
464 
465  KMP_YIELD_OVERSUB();
466  return KMP_LOCK_RELEASED;
467 }
468 
469 static int __kmp_release_futex_lock_with_checks(kmp_futex_lock_t *lck,
470  kmp_int32 gtid) {
471  char const *const func = "omp_unset_lock";
472  KMP_MB(); /* in case another processor initialized lock */
473  if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) &&
474  __kmp_is_futex_lock_nestable(lck)) {
475  KMP_FATAL(LockNestableUsedAsSimple, func);
476  }
477  if (__kmp_get_futex_lock_owner(lck) == -1) {
478  KMP_FATAL(LockUnsettingFree, func);
479  }
480  if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) >= 0) &&
481  (__kmp_get_futex_lock_owner(lck) != gtid)) {
482  KMP_FATAL(LockUnsettingSetByAnother, func);
483  }
484  return __kmp_release_futex_lock(lck, gtid);
485 }
486 
487 void __kmp_init_futex_lock(kmp_futex_lock_t *lck) {
488  TCW_4(lck->lk.poll, KMP_LOCK_FREE(futex));
489 }
490 
491 void __kmp_destroy_futex_lock(kmp_futex_lock_t *lck) { lck->lk.poll = 0; }
492 
493 static void __kmp_destroy_futex_lock_with_checks(kmp_futex_lock_t *lck) {
494  char const *const func = "omp_destroy_lock";
495  if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) &&
496  __kmp_is_futex_lock_nestable(lck)) {
497  KMP_FATAL(LockNestableUsedAsSimple, func);
498  }
499  if (__kmp_get_futex_lock_owner(lck) != -1) {
500  KMP_FATAL(LockStillOwned, func);
501  }
502  __kmp_destroy_futex_lock(lck);
503 }
504 
505 // nested futex locks
506 
507 int __kmp_acquire_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
508  KMP_DEBUG_ASSERT(gtid >= 0);
509 
510  if (__kmp_get_futex_lock_owner(lck) == gtid) {
511  lck->lk.depth_locked += 1;
512  return KMP_LOCK_ACQUIRED_NEXT;
513  } else {
514  __kmp_acquire_futex_lock_timed_template(lck, gtid);
515  ANNOTATE_FUTEX_ACQUIRED(lck);
516  lck->lk.depth_locked = 1;
517  return KMP_LOCK_ACQUIRED_FIRST;
518  }
519 }
520 
521 static int __kmp_acquire_nested_futex_lock_with_checks(kmp_futex_lock_t *lck,
522  kmp_int32 gtid) {
523  char const *const func = "omp_set_nest_lock";
524  if (!__kmp_is_futex_lock_nestable(lck)) {
525  KMP_FATAL(LockSimpleUsedAsNestable, func);
526  }
527  return __kmp_acquire_nested_futex_lock(lck, gtid);
528 }
529 
530 int __kmp_test_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
531  int retval;
532 
533  KMP_DEBUG_ASSERT(gtid >= 0);
534 
535  if (__kmp_get_futex_lock_owner(lck) == gtid) {
536  retval = ++lck->lk.depth_locked;
537  } else if (!__kmp_test_futex_lock(lck, gtid)) {
538  retval = 0;
539  } else {
540  KMP_MB();
541  retval = lck->lk.depth_locked = 1;
542  }
543  return retval;
544 }
545 
546 static int __kmp_test_nested_futex_lock_with_checks(kmp_futex_lock_t *lck,
547  kmp_int32 gtid) {
548  char const *const func = "omp_test_nest_lock";
549  if (!__kmp_is_futex_lock_nestable(lck)) {
550  KMP_FATAL(LockSimpleUsedAsNestable, func);
551  }
552  return __kmp_test_nested_futex_lock(lck, gtid);
553 }
554 
555 int __kmp_release_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
556  KMP_DEBUG_ASSERT(gtid >= 0);
557 
558  KMP_MB();
559  if (--(lck->lk.depth_locked) == 0) {
560  __kmp_release_futex_lock(lck, gtid);
561  return KMP_LOCK_RELEASED;
562  }
563  return KMP_LOCK_STILL_HELD;
564 }
565 
566 static int __kmp_release_nested_futex_lock_with_checks(kmp_futex_lock_t *lck,
567  kmp_int32 gtid) {
568  char const *const func = "omp_unset_nest_lock";
569  KMP_MB(); /* in case another processor initialized lock */
570  if (!__kmp_is_futex_lock_nestable(lck)) {
571  KMP_FATAL(LockSimpleUsedAsNestable, func);
572  }
573  if (__kmp_get_futex_lock_owner(lck) == -1) {
574  KMP_FATAL(LockUnsettingFree, func);
575  }
576  if (__kmp_get_futex_lock_owner(lck) != gtid) {
577  KMP_FATAL(LockUnsettingSetByAnother, func);
578  }
579  return __kmp_release_nested_futex_lock(lck, gtid);
580 }
581 
582 void __kmp_init_nested_futex_lock(kmp_futex_lock_t *lck) {
583  __kmp_init_futex_lock(lck);
584  lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
585 }
586 
587 void __kmp_destroy_nested_futex_lock(kmp_futex_lock_t *lck) {
588  __kmp_destroy_futex_lock(lck);
589  lck->lk.depth_locked = 0;
590 }
591 
592 static void __kmp_destroy_nested_futex_lock_with_checks(kmp_futex_lock_t *lck) {
593  char const *const func = "omp_destroy_nest_lock";
594  if (!__kmp_is_futex_lock_nestable(lck)) {
595  KMP_FATAL(LockSimpleUsedAsNestable, func);
596  }
597  if (__kmp_get_futex_lock_owner(lck) != -1) {
598  KMP_FATAL(LockStillOwned, func);
599  }
600  __kmp_destroy_nested_futex_lock(lck);
601 }
602 
603 #endif // KMP_USE_FUTEX
604 
605 /* ------------------------------------------------------------------------ */
606 /* ticket (bakery) locks */
607 
608 static kmp_int32 __kmp_get_ticket_lock_owner(kmp_ticket_lock_t *lck) {
609  return std::atomic_load_explicit(&lck->lk.owner_id,
610  std::memory_order_relaxed) -
611  1;
612 }
613 
614 static inline bool __kmp_is_ticket_lock_nestable(kmp_ticket_lock_t *lck) {
615  return std::atomic_load_explicit(&lck->lk.depth_locked,
616  std::memory_order_relaxed) != -1;
617 }
618 
619 static kmp_uint32 __kmp_bakery_check(void *now_serving, kmp_uint32 my_ticket) {
620  return std::atomic_load_explicit((std::atomic<unsigned> *)now_serving,
621  std::memory_order_acquire) == my_ticket;
622 }
623 
624 __forceinline static int
625 __kmp_acquire_ticket_lock_timed_template(kmp_ticket_lock_t *lck,
626  kmp_int32 gtid) {
627  kmp_uint32 my_ticket = std::atomic_fetch_add_explicit(
628  &lck->lk.next_ticket, 1U, std::memory_order_relaxed);
629 
630 #ifdef USE_LOCK_PROFILE
631  if (std::atomic_load_explicit(&lck->lk.now_serving,
632  std::memory_order_relaxed) != my_ticket)
633  __kmp_printf("LOCK CONTENTION: %p\n", lck);
634 /* else __kmp_printf( "." );*/
635 #endif /* USE_LOCK_PROFILE */
636 
637  if (std::atomic_load_explicit(&lck->lk.now_serving,
638  std::memory_order_acquire) == my_ticket) {
639  return KMP_LOCK_ACQUIRED_FIRST;
640  }
641  KMP_WAIT_PTR(&lck->lk.now_serving, my_ticket, __kmp_bakery_check, lck);
642  return KMP_LOCK_ACQUIRED_FIRST;
643 }
644 
645 int __kmp_acquire_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
646  int retval = __kmp_acquire_ticket_lock_timed_template(lck, gtid);
647  ANNOTATE_TICKET_ACQUIRED(lck);
648  return retval;
649 }
650 
651 static int __kmp_acquire_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
652  kmp_int32 gtid) {
653  char const *const func = "omp_set_lock";
654 
655  if (!std::atomic_load_explicit(&lck->lk.initialized,
656  std::memory_order_relaxed)) {
657  KMP_FATAL(LockIsUninitialized, func);
658  }
659  if (lck->lk.self != lck) {
660  KMP_FATAL(LockIsUninitialized, func);
661  }
662  if (__kmp_is_ticket_lock_nestable(lck)) {
663  KMP_FATAL(LockNestableUsedAsSimple, func);
664  }
665  if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) == gtid)) {
666  KMP_FATAL(LockIsAlreadyOwned, func);
667  }
668 
669  __kmp_acquire_ticket_lock(lck, gtid);
670 
671  std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
672  std::memory_order_relaxed);
673  return KMP_LOCK_ACQUIRED_FIRST;
674 }
675 
676 int __kmp_test_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
677  kmp_uint32 my_ticket = std::atomic_load_explicit(&lck->lk.next_ticket,
678  std::memory_order_relaxed);
679 
680  if (std::atomic_load_explicit(&lck->lk.now_serving,
681  std::memory_order_relaxed) == my_ticket) {
682  kmp_uint32 next_ticket = my_ticket + 1;
683  if (std::atomic_compare_exchange_strong_explicit(
684  &lck->lk.next_ticket, &my_ticket, next_ticket,
685  std::memory_order_acquire, std::memory_order_acquire)) {
686  return TRUE;
687  }
688  }
689  return FALSE;
690 }
691 
692 static int __kmp_test_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
693  kmp_int32 gtid) {
694  char const *const func = "omp_test_lock";
695 
696  if (!std::atomic_load_explicit(&lck->lk.initialized,
697  std::memory_order_relaxed)) {
698  KMP_FATAL(LockIsUninitialized, func);
699  }
700  if (lck->lk.self != lck) {
701  KMP_FATAL(LockIsUninitialized, func);
702  }
703  if (__kmp_is_ticket_lock_nestable(lck)) {
704  KMP_FATAL(LockNestableUsedAsSimple, func);
705  }
706 
707  int retval = __kmp_test_ticket_lock(lck, gtid);
708 
709  if (retval) {
710  std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
711  std::memory_order_relaxed);
712  }
713  return retval;
714 }
715 
716 int __kmp_release_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
717  kmp_uint32 distance = std::atomic_load_explicit(&lck->lk.next_ticket,
718  std::memory_order_relaxed) -
719  std::atomic_load_explicit(&lck->lk.now_serving,
720  std::memory_order_relaxed);
721 
722  ANNOTATE_TICKET_RELEASED(lck);
723  std::atomic_fetch_add_explicit(&lck->lk.now_serving, 1U,
724  std::memory_order_release);
725 
726  KMP_YIELD(distance >
727  (kmp_uint32)(__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc));
728  return KMP_LOCK_RELEASED;
729 }
730 
731 static int __kmp_release_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
732  kmp_int32 gtid) {
733  char const *const func = "omp_unset_lock";
734 
735  if (!std::atomic_load_explicit(&lck->lk.initialized,
736  std::memory_order_relaxed)) {
737  KMP_FATAL(LockIsUninitialized, func);
738  }
739  if (lck->lk.self != lck) {
740  KMP_FATAL(LockIsUninitialized, func);
741  }
742  if (__kmp_is_ticket_lock_nestable(lck)) {
743  KMP_FATAL(LockNestableUsedAsSimple, func);
744  }
745  if (__kmp_get_ticket_lock_owner(lck) == -1) {
746  KMP_FATAL(LockUnsettingFree, func);
747  }
748  if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) >= 0) &&
749  (__kmp_get_ticket_lock_owner(lck) != gtid)) {
750  KMP_FATAL(LockUnsettingSetByAnother, func);
751  }
752  std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed);
753  return __kmp_release_ticket_lock(lck, gtid);
754 }
755 
756 void __kmp_init_ticket_lock(kmp_ticket_lock_t *lck) {
757  lck->lk.location = NULL;
758  lck->lk.self = lck;
759  std::atomic_store_explicit(&lck->lk.next_ticket, 0U,
760  std::memory_order_relaxed);
761  std::atomic_store_explicit(&lck->lk.now_serving, 0U,
762  std::memory_order_relaxed);
763  std::atomic_store_explicit(
764  &lck->lk.owner_id, 0,
765  std::memory_order_relaxed); // no thread owns the lock.
766  std::atomic_store_explicit(
767  &lck->lk.depth_locked, -1,
768  std::memory_order_relaxed); // -1 => not a nested lock.
769  std::atomic_store_explicit(&lck->lk.initialized, true,
770  std::memory_order_release);
771 }
772 
773 void __kmp_destroy_ticket_lock(kmp_ticket_lock_t *lck) {
774  std::atomic_store_explicit(&lck->lk.initialized, false,
775  std::memory_order_release);
776  lck->lk.self = NULL;
777  lck->lk.location = NULL;
778  std::atomic_store_explicit(&lck->lk.next_ticket, 0U,
779  std::memory_order_relaxed);
780  std::atomic_store_explicit(&lck->lk.now_serving, 0U,
781  std::memory_order_relaxed);
782  std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed);
783  std::atomic_store_explicit(&lck->lk.depth_locked, -1,
784  std::memory_order_relaxed);
785 }
786 
787 static void __kmp_destroy_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
788  char const *const func = "omp_destroy_lock";
789 
790  if (!std::atomic_load_explicit(&lck->lk.initialized,
791  std::memory_order_relaxed)) {
792  KMP_FATAL(LockIsUninitialized, func);
793  }
794  if (lck->lk.self != lck) {
795  KMP_FATAL(LockIsUninitialized, func);
796  }
797  if (__kmp_is_ticket_lock_nestable(lck)) {
798  KMP_FATAL(LockNestableUsedAsSimple, func);
799  }
800  if (__kmp_get_ticket_lock_owner(lck) != -1) {
801  KMP_FATAL(LockStillOwned, func);
802  }
803  __kmp_destroy_ticket_lock(lck);
804 }
805 
806 // nested ticket locks
807 
808 int __kmp_acquire_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
809  KMP_DEBUG_ASSERT(gtid >= 0);
810 
811  if (__kmp_get_ticket_lock_owner(lck) == gtid) {
812  std::atomic_fetch_add_explicit(&lck->lk.depth_locked, 1,
813  std::memory_order_relaxed);
814  return KMP_LOCK_ACQUIRED_NEXT;
815  } else {
816  __kmp_acquire_ticket_lock_timed_template(lck, gtid);
817  ANNOTATE_TICKET_ACQUIRED(lck);
818  std::atomic_store_explicit(&lck->lk.depth_locked, 1,
819  std::memory_order_relaxed);
820  std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
821  std::memory_order_relaxed);
822  return KMP_LOCK_ACQUIRED_FIRST;
823  }
824 }
825 
826 static int __kmp_acquire_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
827  kmp_int32 gtid) {
828  char const *const func = "omp_set_nest_lock";
829 
830  if (!std::atomic_load_explicit(&lck->lk.initialized,
831  std::memory_order_relaxed)) {
832  KMP_FATAL(LockIsUninitialized, func);
833  }
834  if (lck->lk.self != lck) {
835  KMP_FATAL(LockIsUninitialized, func);
836  }
837  if (!__kmp_is_ticket_lock_nestable(lck)) {
838  KMP_FATAL(LockSimpleUsedAsNestable, func);
839  }
840  return __kmp_acquire_nested_ticket_lock(lck, gtid);
841 }
842 
843 int __kmp_test_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
844  int retval;
845 
846  KMP_DEBUG_ASSERT(gtid >= 0);
847 
848  if (__kmp_get_ticket_lock_owner(lck) == gtid) {
849  retval = std::atomic_fetch_add_explicit(&lck->lk.depth_locked, 1,
850  std::memory_order_relaxed) +
851  1;
852  } else if (!__kmp_test_ticket_lock(lck, gtid)) {
853  retval = 0;
854  } else {
855  std::atomic_store_explicit(&lck->lk.depth_locked, 1,
856  std::memory_order_relaxed);
857  std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
858  std::memory_order_relaxed);
859  retval = 1;
860  }
861  return retval;
862 }
863 
864 static int __kmp_test_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
865  kmp_int32 gtid) {
866  char const *const func = "omp_test_nest_lock";
867 
868  if (!std::atomic_load_explicit(&lck->lk.initialized,
869  std::memory_order_relaxed)) {
870  KMP_FATAL(LockIsUninitialized, func);
871  }
872  if (lck->lk.self != lck) {
873  KMP_FATAL(LockIsUninitialized, func);
874  }
875  if (!__kmp_is_ticket_lock_nestable(lck)) {
876  KMP_FATAL(LockSimpleUsedAsNestable, func);
877  }
878  return __kmp_test_nested_ticket_lock(lck, gtid);
879 }
880 
881 int __kmp_release_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
882  KMP_DEBUG_ASSERT(gtid >= 0);
883 
884  if ((std::atomic_fetch_add_explicit(&lck->lk.depth_locked, -1,
885  std::memory_order_relaxed) -
886  1) == 0) {
887  std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed);
888  __kmp_release_ticket_lock(lck, gtid);
889  return KMP_LOCK_RELEASED;
890  }
891  return KMP_LOCK_STILL_HELD;
892 }
893 
894 static int __kmp_release_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
895  kmp_int32 gtid) {
896  char const *const func = "omp_unset_nest_lock";
897 
898  if (!std::atomic_load_explicit(&lck->lk.initialized,
899  std::memory_order_relaxed)) {
900  KMP_FATAL(LockIsUninitialized, func);
901  }
902  if (lck->lk.self != lck) {
903  KMP_FATAL(LockIsUninitialized, func);
904  }
905  if (!__kmp_is_ticket_lock_nestable(lck)) {
906  KMP_FATAL(LockSimpleUsedAsNestable, func);
907  }
908  if (__kmp_get_ticket_lock_owner(lck) == -1) {
909  KMP_FATAL(LockUnsettingFree, func);
910  }
911  if (__kmp_get_ticket_lock_owner(lck) != gtid) {
912  KMP_FATAL(LockUnsettingSetByAnother, func);
913  }
914  return __kmp_release_nested_ticket_lock(lck, gtid);
915 }
916 
917 void __kmp_init_nested_ticket_lock(kmp_ticket_lock_t *lck) {
918  __kmp_init_ticket_lock(lck);
919  std::atomic_store_explicit(&lck->lk.depth_locked, 0,
920  std::memory_order_relaxed);
921  // >= 0 for nestable locks, -1 for simple locks
922 }
923 
924 void __kmp_destroy_nested_ticket_lock(kmp_ticket_lock_t *lck) {
925  __kmp_destroy_ticket_lock(lck);
926  std::atomic_store_explicit(&lck->lk.depth_locked, 0,
927  std::memory_order_relaxed);
928 }
929 
930 static void
931 __kmp_destroy_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
932  char const *const func = "omp_destroy_nest_lock";
933 
934  if (!std::atomic_load_explicit(&lck->lk.initialized,
935  std::memory_order_relaxed)) {
936  KMP_FATAL(LockIsUninitialized, func);
937  }
938  if (lck->lk.self != lck) {
939  KMP_FATAL(LockIsUninitialized, func);
940  }
941  if (!__kmp_is_ticket_lock_nestable(lck)) {
942  KMP_FATAL(LockSimpleUsedAsNestable, func);
943  }
944  if (__kmp_get_ticket_lock_owner(lck) != -1) {
945  KMP_FATAL(LockStillOwned, func);
946  }
947  __kmp_destroy_nested_ticket_lock(lck);
948 }
949 
950 // access functions to fields which don't exist for all lock kinds.
951 
952 static const ident_t *__kmp_get_ticket_lock_location(kmp_ticket_lock_t *lck) {
953  return lck->lk.location;
954 }
955 
956 static void __kmp_set_ticket_lock_location(kmp_ticket_lock_t *lck,
957  const ident_t *loc) {
958  lck->lk.location = loc;
959 }
960 
961 static kmp_lock_flags_t __kmp_get_ticket_lock_flags(kmp_ticket_lock_t *lck) {
962  return lck->lk.flags;
963 }
964 
965 static void __kmp_set_ticket_lock_flags(kmp_ticket_lock_t *lck,
966  kmp_lock_flags_t flags) {
967  lck->lk.flags = flags;
968 }
969 
970 /* ------------------------------------------------------------------------ */
971 /* queuing locks */
972 
973 /* First the states
974  (head,tail) = 0, 0 means lock is unheld, nobody on queue
975  UINT_MAX or -1, 0 means lock is held, nobody on queue
976  h, h means lock held or about to transition,
977  1 element on queue
978  h, t h <> t, means lock is held or about to
979  transition, >1 elements on queue
980 
981  Now the transitions
982  Acquire(0,0) = -1 ,0
983  Release(0,0) = Error
984  Acquire(-1,0) = h ,h h > 0
985  Release(-1,0) = 0 ,0
986  Acquire(h,h) = h ,t h > 0, t > 0, h <> t
987  Release(h,h) = -1 ,0 h > 0
988  Acquire(h,t) = h ,t' h > 0, t > 0, t' > 0, h <> t, h <> t', t <> t'
989  Release(h,t) = h',t h > 0, t > 0, h <> t, h <> h', h' maybe = t
990 
991  And pictorially
992 
993  +-----+
994  | 0, 0|------- release -------> Error
995  +-----+
996  | ^
997  acquire| |release
998  | |
999  | |
1000  v |
1001  +-----+
1002  |-1, 0|
1003  +-----+
1004  | ^
1005  acquire| |release
1006  | |
1007  | |
1008  v |
1009  +-----+
1010  | h, h|
1011  +-----+
1012  | ^
1013  acquire| |release
1014  | |
1015  | |
1016  v |
1017  +-----+
1018  | h, t|----- acquire, release loopback ---+
1019  +-----+ |
1020  ^ |
1021  | |
1022  +------------------------------------+
1023  */
1024 
1025 #ifdef DEBUG_QUEUING_LOCKS
1026 
1027 /* Stuff for circular trace buffer */
1028 #define TRACE_BUF_ELE 1024
1029 static char traces[TRACE_BUF_ELE][128] = {0};
1030 static int tc = 0;
1031 #define TRACE_LOCK(X, Y) \
1032  KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s\n", X, Y);
1033 #define TRACE_LOCK_T(X, Y, Z) \
1034  KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s%d\n", X, Y, Z);
1035 #define TRACE_LOCK_HT(X, Y, Z, Q) \
1036  KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s %d,%d\n", X, Y, \
1037  Z, Q);
1038 
1039 static void __kmp_dump_queuing_lock(kmp_info_t *this_thr, kmp_int32 gtid,
1040  kmp_queuing_lock_t *lck, kmp_int32 head_id,
1041  kmp_int32 tail_id) {
1042  kmp_int32 t, i;
1043 
1044  __kmp_printf_no_lock("\n__kmp_dump_queuing_lock: TRACE BEGINS HERE! \n");
1045 
1046  i = tc % TRACE_BUF_ELE;
1047  __kmp_printf_no_lock("%s\n", traces[i]);
1048  i = (i + 1) % TRACE_BUF_ELE;
1049  while (i != (tc % TRACE_BUF_ELE)) {
1050  __kmp_printf_no_lock("%s", traces[i]);
1051  i = (i + 1) % TRACE_BUF_ELE;
1052  }
1053  __kmp_printf_no_lock("\n");
1054 
1055  __kmp_printf_no_lock("\n__kmp_dump_queuing_lock: gtid+1:%d, spin_here:%d, "
1056  "next_wait:%d, head_id:%d, tail_id:%d\n",
1057  gtid + 1, this_thr->th.th_spin_here,
1058  this_thr->th.th_next_waiting, head_id, tail_id);
1059 
1060  __kmp_printf_no_lock("\t\thead: %d ", lck->lk.head_id);
1061 
1062  if (lck->lk.head_id >= 1) {
1063  t = __kmp_threads[lck->lk.head_id - 1]->th.th_next_waiting;
1064  while (t > 0) {
1065  __kmp_printf_no_lock("-> %d ", t);
1066  t = __kmp_threads[t - 1]->th.th_next_waiting;
1067  }
1068  }
1069  __kmp_printf_no_lock("; tail: %d ", lck->lk.tail_id);
1070  __kmp_printf_no_lock("\n\n");
1071 }
1072 
1073 #endif /* DEBUG_QUEUING_LOCKS */
1074 
1075 static kmp_int32 __kmp_get_queuing_lock_owner(kmp_queuing_lock_t *lck) {
1076  return TCR_4(lck->lk.owner_id) - 1;
1077 }
1078 
1079 static inline bool __kmp_is_queuing_lock_nestable(kmp_queuing_lock_t *lck) {
1080  return lck->lk.depth_locked != -1;
1081 }
1082 
1083 /* Acquire a lock using a the queuing lock implementation */
1084 template <bool takeTime>
1085 /* [TLW] The unused template above is left behind because of what BEB believes
1086  is a potential compiler problem with __forceinline. */
1087 __forceinline static int
1088 __kmp_acquire_queuing_lock_timed_template(kmp_queuing_lock_t *lck,
1089  kmp_int32 gtid) {
1090  kmp_info_t *this_thr = __kmp_thread_from_gtid(gtid);
1091  volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1092  volatile kmp_int32 *tail_id_p = &lck->lk.tail_id;
1093  volatile kmp_uint32 *spin_here_p;
1094  kmp_int32 need_mf = 1;
1095 
1096 #if OMPT_SUPPORT
1097  ompt_state_t prev_state = ompt_state_undefined;
1098 #endif
1099 
1100  KA_TRACE(1000,
1101  ("__kmp_acquire_queuing_lock: lck:%p, T#%d entering\n", lck, gtid));
1102 
1103  KMP_FSYNC_PREPARE(lck);
1104  KMP_DEBUG_ASSERT(this_thr != NULL);
1105  spin_here_p = &this_thr->th.th_spin_here;
1106 
1107 #ifdef DEBUG_QUEUING_LOCKS
1108  TRACE_LOCK(gtid + 1, "acq ent");
1109  if (*spin_here_p)
1110  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1111  if (this_thr->th.th_next_waiting != 0)
1112  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1113 #endif
1114  KMP_DEBUG_ASSERT(!*spin_here_p);
1115  KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1116 
1117  /* The following st.rel to spin_here_p needs to precede the cmpxchg.acq to
1118  head_id_p that may follow, not just in execution order, but also in
1119  visibility order. This way, when a releasing thread observes the changes to
1120  the queue by this thread, it can rightly assume that spin_here_p has
1121  already been set to TRUE, so that when it sets spin_here_p to FALSE, it is
1122  not premature. If the releasing thread sets spin_here_p to FALSE before
1123  this thread sets it to TRUE, this thread will hang. */
1124  *spin_here_p = TRUE; /* before enqueuing to prevent race */
1125 
1126  while (1) {
1127  kmp_int32 enqueued;
1128  kmp_int32 head;
1129  kmp_int32 tail;
1130 
1131  head = *head_id_p;
1132 
1133  switch (head) {
1134 
1135  case -1: {
1136 #ifdef DEBUG_QUEUING_LOCKS
1137  tail = *tail_id_p;
1138  TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1139 #endif
1140  tail = 0; /* to make sure next link asynchronously read is not set
1141  accidentally; this assignment prevents us from entering the
1142  if ( t > 0 ) condition in the enqueued case below, which is not
1143  necessary for this state transition */
1144 
1145  need_mf = 0;
1146  /* try (-1,0)->(tid,tid) */
1147  enqueued = KMP_COMPARE_AND_STORE_ACQ64((volatile kmp_int64 *)tail_id_p,
1148  KMP_PACK_64(-1, 0),
1149  KMP_PACK_64(gtid + 1, gtid + 1));
1150 #ifdef DEBUG_QUEUING_LOCKS
1151  if (enqueued)
1152  TRACE_LOCK(gtid + 1, "acq enq: (-1,0)->(tid,tid)");
1153 #endif
1154  } break;
1155 
1156  default: {
1157  tail = *tail_id_p;
1158  KMP_DEBUG_ASSERT(tail != gtid + 1);
1159 
1160 #ifdef DEBUG_QUEUING_LOCKS
1161  TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1162 #endif
1163 
1164  if (tail == 0) {
1165  enqueued = FALSE;
1166  } else {
1167  need_mf = 0;
1168  /* try (h,t) or (h,h)->(h,tid) */
1169  enqueued = KMP_COMPARE_AND_STORE_ACQ32(tail_id_p, tail, gtid + 1);
1170 
1171 #ifdef DEBUG_QUEUING_LOCKS
1172  if (enqueued)
1173  TRACE_LOCK(gtid + 1, "acq enq: (h,t)->(h,tid)");
1174 #endif
1175  }
1176  } break;
1177 
1178  case 0: /* empty queue */
1179  {
1180  kmp_int32 grabbed_lock;
1181 
1182 #ifdef DEBUG_QUEUING_LOCKS
1183  tail = *tail_id_p;
1184  TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1185 #endif
1186  /* try (0,0)->(-1,0) */
1187 
1188  /* only legal transition out of head = 0 is head = -1 with no change to
1189  * tail */
1190  grabbed_lock = KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1);
1191 
1192  if (grabbed_lock) {
1193 
1194  *spin_here_p = FALSE;
1195 
1196  KA_TRACE(
1197  1000,
1198  ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: no queuing\n",
1199  lck, gtid));
1200 #ifdef DEBUG_QUEUING_LOCKS
1201  TRACE_LOCK_HT(gtid + 1, "acq exit: ", head, 0);
1202 #endif
1203 
1204 #if OMPT_SUPPORT
1205  if (ompt_enabled.enabled && prev_state != ompt_state_undefined) {
1206  /* change the state before clearing wait_id */
1207  this_thr->th.ompt_thread_info.state = prev_state;
1208  this_thr->th.ompt_thread_info.wait_id = 0;
1209  }
1210 #endif
1211 
1212  KMP_FSYNC_ACQUIRED(lck);
1213  return KMP_LOCK_ACQUIRED_FIRST; /* lock holder cannot be on queue */
1214  }
1215  enqueued = FALSE;
1216  } break;
1217  }
1218 
1219 #if OMPT_SUPPORT
1220  if (ompt_enabled.enabled && prev_state == ompt_state_undefined) {
1221  /* this thread will spin; set wait_id before entering wait state */
1222  prev_state = this_thr->th.ompt_thread_info.state;
1223  this_thr->th.ompt_thread_info.wait_id = (uint64_t)lck;
1224  this_thr->th.ompt_thread_info.state = ompt_state_wait_lock;
1225  }
1226 #endif
1227 
1228  if (enqueued) {
1229  if (tail > 0) {
1230  kmp_info_t *tail_thr = __kmp_thread_from_gtid(tail - 1);
1231  KMP_ASSERT(tail_thr != NULL);
1232  tail_thr->th.th_next_waiting = gtid + 1;
1233  /* corresponding wait for this write in release code */
1234  }
1235  KA_TRACE(1000,
1236  ("__kmp_acquire_queuing_lock: lck:%p, T#%d waiting for lock\n",
1237  lck, gtid));
1238 
1239  KMP_MB();
1240  // ToDo: Use __kmp_wait_sleep or similar when blocktime != inf
1241  KMP_WAIT(spin_here_p, FALSE, KMP_EQ, lck);
1242  // Synchronize writes to both runtime thread structures
1243  // and writes in user code.
1244  KMP_MB();
1245 
1246 #ifdef DEBUG_QUEUING_LOCKS
1247  TRACE_LOCK(gtid + 1, "acq spin");
1248 
1249  if (this_thr->th.th_next_waiting != 0)
1250  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1251 #endif
1252  KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1253  KA_TRACE(1000, ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: after "
1254  "waiting on queue\n",
1255  lck, gtid));
1256 
1257 #ifdef DEBUG_QUEUING_LOCKS
1258  TRACE_LOCK(gtid + 1, "acq exit 2");
1259 #endif
1260 
1261 #if OMPT_SUPPORT
1262  /* change the state before clearing wait_id */
1263  this_thr->th.ompt_thread_info.state = prev_state;
1264  this_thr->th.ompt_thread_info.wait_id = 0;
1265 #endif
1266 
1267  /* got lock, we were dequeued by the thread that released lock */
1268  return KMP_LOCK_ACQUIRED_FIRST;
1269  }
1270 
1271  /* Yield if number of threads > number of logical processors */
1272  /* ToDo: Not sure why this should only be in oversubscription case,
1273  maybe should be traditional YIELD_INIT/YIELD_WHEN loop */
1274  KMP_YIELD_OVERSUB();
1275 
1276 #ifdef DEBUG_QUEUING_LOCKS
1277  TRACE_LOCK(gtid + 1, "acq retry");
1278 #endif
1279  }
1280  KMP_ASSERT2(0, "should not get here");
1281  return KMP_LOCK_ACQUIRED_FIRST;
1282 }
1283 
1284 int __kmp_acquire_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1285  KMP_DEBUG_ASSERT(gtid >= 0);
1286 
1287  int retval = __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid);
1288  ANNOTATE_QUEUING_ACQUIRED(lck);
1289  return retval;
1290 }
1291 
1292 static int __kmp_acquire_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1293  kmp_int32 gtid) {
1294  char const *const func = "omp_set_lock";
1295  if (lck->lk.initialized != lck) {
1296  KMP_FATAL(LockIsUninitialized, func);
1297  }
1298  if (__kmp_is_queuing_lock_nestable(lck)) {
1299  KMP_FATAL(LockNestableUsedAsSimple, func);
1300  }
1301  if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1302  KMP_FATAL(LockIsAlreadyOwned, func);
1303  }
1304 
1305  __kmp_acquire_queuing_lock(lck, gtid);
1306 
1307  lck->lk.owner_id = gtid + 1;
1308  return KMP_LOCK_ACQUIRED_FIRST;
1309 }
1310 
1311 int __kmp_test_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1312  volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1313  kmp_int32 head;
1314 #ifdef KMP_DEBUG
1315  kmp_info_t *this_thr;
1316 #endif
1317 
1318  KA_TRACE(1000, ("__kmp_test_queuing_lock: T#%d entering\n", gtid));
1319  KMP_DEBUG_ASSERT(gtid >= 0);
1320 #ifdef KMP_DEBUG
1321  this_thr = __kmp_thread_from_gtid(gtid);
1322  KMP_DEBUG_ASSERT(this_thr != NULL);
1323  KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here);
1324 #endif
1325 
1326  head = *head_id_p;
1327 
1328  if (head == 0) { /* nobody on queue, nobody holding */
1329  /* try (0,0)->(-1,0) */
1330  if (KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1)) {
1331  KA_TRACE(1000,
1332  ("__kmp_test_queuing_lock: T#%d exiting: holding lock\n", gtid));
1333  KMP_FSYNC_ACQUIRED(lck);
1334  ANNOTATE_QUEUING_ACQUIRED(lck);
1335  return TRUE;
1336  }
1337  }
1338 
1339  KA_TRACE(1000,
1340  ("__kmp_test_queuing_lock: T#%d exiting: without lock\n", gtid));
1341  return FALSE;
1342 }
1343 
1344 static int __kmp_test_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1345  kmp_int32 gtid) {
1346  char const *const func = "omp_test_lock";
1347  if (lck->lk.initialized != lck) {
1348  KMP_FATAL(LockIsUninitialized, func);
1349  }
1350  if (__kmp_is_queuing_lock_nestable(lck)) {
1351  KMP_FATAL(LockNestableUsedAsSimple, func);
1352  }
1353 
1354  int retval = __kmp_test_queuing_lock(lck, gtid);
1355 
1356  if (retval) {
1357  lck->lk.owner_id = gtid + 1;
1358  }
1359  return retval;
1360 }
1361 
1362 int __kmp_release_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1363  kmp_info_t *this_thr;
1364  volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1365  volatile kmp_int32 *tail_id_p = &lck->lk.tail_id;
1366 
1367  KA_TRACE(1000,
1368  ("__kmp_release_queuing_lock: lck:%p, T#%d entering\n", lck, gtid));
1369  KMP_DEBUG_ASSERT(gtid >= 0);
1370  this_thr = __kmp_thread_from_gtid(gtid);
1371  KMP_DEBUG_ASSERT(this_thr != NULL);
1372 #ifdef DEBUG_QUEUING_LOCKS
1373  TRACE_LOCK(gtid + 1, "rel ent");
1374 
1375  if (this_thr->th.th_spin_here)
1376  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1377  if (this_thr->th.th_next_waiting != 0)
1378  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1379 #endif
1380  KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here);
1381  KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1382 
1383  KMP_FSYNC_RELEASING(lck);
1384  ANNOTATE_QUEUING_RELEASED(lck);
1385 
1386  while (1) {
1387  kmp_int32 dequeued;
1388  kmp_int32 head;
1389  kmp_int32 tail;
1390 
1391  head = *head_id_p;
1392 
1393 #ifdef DEBUG_QUEUING_LOCKS
1394  tail = *tail_id_p;
1395  TRACE_LOCK_HT(gtid + 1, "rel read: ", head, tail);
1396  if (head == 0)
1397  __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1398 #endif
1399  KMP_DEBUG_ASSERT(head !=
1400  0); /* holding the lock, head must be -1 or queue head */
1401 
1402  if (head == -1) { /* nobody on queue */
1403  /* try (-1,0)->(0,0) */
1404  if (KMP_COMPARE_AND_STORE_REL32(head_id_p, -1, 0)) {
1405  KA_TRACE(
1406  1000,
1407  ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: queue empty\n",
1408  lck, gtid));
1409 #ifdef DEBUG_QUEUING_LOCKS
1410  TRACE_LOCK_HT(gtid + 1, "rel exit: ", 0, 0);
1411 #endif
1412 
1413 #if OMPT_SUPPORT
1414 /* nothing to do - no other thread is trying to shift blame */
1415 #endif
1416  return KMP_LOCK_RELEASED;
1417  }
1418  dequeued = FALSE;
1419  } else {
1420  KMP_MB();
1421  tail = *tail_id_p;
1422  if (head == tail) { /* only one thread on the queue */
1423 #ifdef DEBUG_QUEUING_LOCKS
1424  if (head <= 0)
1425  __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1426 #endif
1427  KMP_DEBUG_ASSERT(head > 0);
1428 
1429  /* try (h,h)->(-1,0) */
1430  dequeued = KMP_COMPARE_AND_STORE_REL64(
1431  RCAST(volatile kmp_int64 *, tail_id_p), KMP_PACK_64(head, head),
1432  KMP_PACK_64(-1, 0));
1433 #ifdef DEBUG_QUEUING_LOCKS
1434  TRACE_LOCK(gtid + 1, "rel deq: (h,h)->(-1,0)");
1435 #endif
1436 
1437  } else {
1438  volatile kmp_int32 *waiting_id_p;
1439  kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1);
1440  KMP_DEBUG_ASSERT(head_thr != NULL);
1441  waiting_id_p = &head_thr->th.th_next_waiting;
1442 
1443 /* Does this require synchronous reads? */
1444 #ifdef DEBUG_QUEUING_LOCKS
1445  if (head <= 0 || tail <= 0)
1446  __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1447 #endif
1448  KMP_DEBUG_ASSERT(head > 0 && tail > 0);
1449 
1450  /* try (h,t)->(h',t) or (t,t) */
1451  KMP_MB();
1452  /* make sure enqueuing thread has time to update next waiting thread
1453  * field */
1454  *head_id_p =
1455  KMP_WAIT((volatile kmp_uint32 *)waiting_id_p, 0, KMP_NEQ, NULL);
1456 #ifdef DEBUG_QUEUING_LOCKS
1457  TRACE_LOCK(gtid + 1, "rel deq: (h,t)->(h',t)");
1458 #endif
1459  dequeued = TRUE;
1460  }
1461  }
1462 
1463  if (dequeued) {
1464  kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1);
1465  KMP_DEBUG_ASSERT(head_thr != NULL);
1466 
1467 /* Does this require synchronous reads? */
1468 #ifdef DEBUG_QUEUING_LOCKS
1469  if (head <= 0 || tail <= 0)
1470  __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1471 #endif
1472  KMP_DEBUG_ASSERT(head > 0 && tail > 0);
1473 
1474  /* For clean code only. Thread not released until next statement prevents
1475  race with acquire code. */
1476  head_thr->th.th_next_waiting = 0;
1477 #ifdef DEBUG_QUEUING_LOCKS
1478  TRACE_LOCK_T(gtid + 1, "rel nw=0 for t=", head);
1479 #endif
1480 
1481  KMP_MB();
1482  /* reset spin value */
1483  head_thr->th.th_spin_here = FALSE;
1484 
1485  KA_TRACE(1000, ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: after "
1486  "dequeuing\n",
1487  lck, gtid));
1488 #ifdef DEBUG_QUEUING_LOCKS
1489  TRACE_LOCK(gtid + 1, "rel exit 2");
1490 #endif
1491  return KMP_LOCK_RELEASED;
1492  }
1493 /* KMP_CPU_PAUSE(); don't want to make releasing thread hold up acquiring
1494  threads */
1495 
1496 #ifdef DEBUG_QUEUING_LOCKS
1497  TRACE_LOCK(gtid + 1, "rel retry");
1498 #endif
1499 
1500  } /* while */
1501  KMP_ASSERT2(0, "should not get here");
1502  return KMP_LOCK_RELEASED;
1503 }
1504 
1505 static int __kmp_release_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1506  kmp_int32 gtid) {
1507  char const *const func = "omp_unset_lock";
1508  KMP_MB(); /* in case another processor initialized lock */
1509  if (lck->lk.initialized != lck) {
1510  KMP_FATAL(LockIsUninitialized, func);
1511  }
1512  if (__kmp_is_queuing_lock_nestable(lck)) {
1513  KMP_FATAL(LockNestableUsedAsSimple, func);
1514  }
1515  if (__kmp_get_queuing_lock_owner(lck) == -1) {
1516  KMP_FATAL(LockUnsettingFree, func);
1517  }
1518  if (__kmp_get_queuing_lock_owner(lck) != gtid) {
1519  KMP_FATAL(LockUnsettingSetByAnother, func);
1520  }
1521  lck->lk.owner_id = 0;
1522  return __kmp_release_queuing_lock(lck, gtid);
1523 }
1524 
1525 void __kmp_init_queuing_lock(kmp_queuing_lock_t *lck) {
1526  lck->lk.location = NULL;
1527  lck->lk.head_id = 0;
1528  lck->lk.tail_id = 0;
1529  lck->lk.next_ticket = 0;
1530  lck->lk.now_serving = 0;
1531  lck->lk.owner_id = 0; // no thread owns the lock.
1532  lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks.
1533  lck->lk.initialized = lck;
1534 
1535  KA_TRACE(1000, ("__kmp_init_queuing_lock: lock %p initialized\n", lck));
1536 }
1537 
1538 void __kmp_destroy_queuing_lock(kmp_queuing_lock_t *lck) {
1539  lck->lk.initialized = NULL;
1540  lck->lk.location = NULL;
1541  lck->lk.head_id = 0;
1542  lck->lk.tail_id = 0;
1543  lck->lk.next_ticket = 0;
1544  lck->lk.now_serving = 0;
1545  lck->lk.owner_id = 0;
1546  lck->lk.depth_locked = -1;
1547 }
1548 
1549 static void __kmp_destroy_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
1550  char const *const func = "omp_destroy_lock";
1551  if (lck->lk.initialized != lck) {
1552  KMP_FATAL(LockIsUninitialized, func);
1553  }
1554  if (__kmp_is_queuing_lock_nestable(lck)) {
1555  KMP_FATAL(LockNestableUsedAsSimple, func);
1556  }
1557  if (__kmp_get_queuing_lock_owner(lck) != -1) {
1558  KMP_FATAL(LockStillOwned, func);
1559  }
1560  __kmp_destroy_queuing_lock(lck);
1561 }
1562 
1563 // nested queuing locks
1564 
1565 int __kmp_acquire_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1566  KMP_DEBUG_ASSERT(gtid >= 0);
1567 
1568  if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1569  lck->lk.depth_locked += 1;
1570  return KMP_LOCK_ACQUIRED_NEXT;
1571  } else {
1572  __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid);
1573  ANNOTATE_QUEUING_ACQUIRED(lck);
1574  KMP_MB();
1575  lck->lk.depth_locked = 1;
1576  KMP_MB();
1577  lck->lk.owner_id = gtid + 1;
1578  return KMP_LOCK_ACQUIRED_FIRST;
1579  }
1580 }
1581 
1582 static int
1583 __kmp_acquire_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1584  kmp_int32 gtid) {
1585  char const *const func = "omp_set_nest_lock";
1586  if (lck->lk.initialized != lck) {
1587  KMP_FATAL(LockIsUninitialized, func);
1588  }
1589  if (!__kmp_is_queuing_lock_nestable(lck)) {
1590  KMP_FATAL(LockSimpleUsedAsNestable, func);
1591  }
1592  return __kmp_acquire_nested_queuing_lock(lck, gtid);
1593 }
1594 
1595 int __kmp_test_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1596  int retval;
1597 
1598  KMP_DEBUG_ASSERT(gtid >= 0);
1599 
1600  if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1601  retval = ++lck->lk.depth_locked;
1602  } else if (!__kmp_test_queuing_lock(lck, gtid)) {
1603  retval = 0;
1604  } else {
1605  KMP_MB();
1606  retval = lck->lk.depth_locked = 1;
1607  KMP_MB();
1608  lck->lk.owner_id = gtid + 1;
1609  }
1610  return retval;
1611 }
1612 
1613 static int __kmp_test_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1614  kmp_int32 gtid) {
1615  char const *const func = "omp_test_nest_lock";
1616  if (lck->lk.initialized != lck) {
1617  KMP_FATAL(LockIsUninitialized, func);
1618  }
1619  if (!__kmp_is_queuing_lock_nestable(lck)) {
1620  KMP_FATAL(LockSimpleUsedAsNestable, func);
1621  }
1622  return __kmp_test_nested_queuing_lock(lck, gtid);
1623 }
1624 
1625 int __kmp_release_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1626  KMP_DEBUG_ASSERT(gtid >= 0);
1627 
1628  KMP_MB();
1629  if (--(lck->lk.depth_locked) == 0) {
1630  KMP_MB();
1631  lck->lk.owner_id = 0;
1632  __kmp_release_queuing_lock(lck, gtid);
1633  return KMP_LOCK_RELEASED;
1634  }
1635  return KMP_LOCK_STILL_HELD;
1636 }
1637 
1638 static int
1639 __kmp_release_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1640  kmp_int32 gtid) {
1641  char const *const func = "omp_unset_nest_lock";
1642  KMP_MB(); /* in case another processor initialized lock */
1643  if (lck->lk.initialized != lck) {
1644  KMP_FATAL(LockIsUninitialized, func);
1645  }
1646  if (!__kmp_is_queuing_lock_nestable(lck)) {
1647  KMP_FATAL(LockSimpleUsedAsNestable, func);
1648  }
1649  if (__kmp_get_queuing_lock_owner(lck) == -1) {
1650  KMP_FATAL(LockUnsettingFree, func);
1651  }
1652  if (__kmp_get_queuing_lock_owner(lck) != gtid) {
1653  KMP_FATAL(LockUnsettingSetByAnother, func);
1654  }
1655  return __kmp_release_nested_queuing_lock(lck, gtid);
1656 }
1657 
1658 void __kmp_init_nested_queuing_lock(kmp_queuing_lock_t *lck) {
1659  __kmp_init_queuing_lock(lck);
1660  lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
1661 }
1662 
1663 void __kmp_destroy_nested_queuing_lock(kmp_queuing_lock_t *lck) {
1664  __kmp_destroy_queuing_lock(lck);
1665  lck->lk.depth_locked = 0;
1666 }
1667 
1668 static void
1669 __kmp_destroy_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
1670  char const *const func = "omp_destroy_nest_lock";
1671  if (lck->lk.initialized != lck) {
1672  KMP_FATAL(LockIsUninitialized, func);
1673  }
1674  if (!__kmp_is_queuing_lock_nestable(lck)) {
1675  KMP_FATAL(LockSimpleUsedAsNestable, func);
1676  }
1677  if (__kmp_get_queuing_lock_owner(lck) != -1) {
1678  KMP_FATAL(LockStillOwned, func);
1679  }
1680  __kmp_destroy_nested_queuing_lock(lck);
1681 }
1682 
1683 // access functions to fields which don't exist for all lock kinds.
1684 
1685 static const ident_t *__kmp_get_queuing_lock_location(kmp_queuing_lock_t *lck) {
1686  return lck->lk.location;
1687 }
1688 
1689 static void __kmp_set_queuing_lock_location(kmp_queuing_lock_t *lck,
1690  const ident_t *loc) {
1691  lck->lk.location = loc;
1692 }
1693 
1694 static kmp_lock_flags_t __kmp_get_queuing_lock_flags(kmp_queuing_lock_t *lck) {
1695  return lck->lk.flags;
1696 }
1697 
1698 static void __kmp_set_queuing_lock_flags(kmp_queuing_lock_t *lck,
1699  kmp_lock_flags_t flags) {
1700  lck->lk.flags = flags;
1701 }
1702 
1703 #if KMP_USE_ADAPTIVE_LOCKS
1704 
1705 /* RTM Adaptive locks */
1706 
1707 #if (KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300) || \
1708  (KMP_COMPILER_MSVC && _MSC_VER >= 1700) || \
1709  (KMP_COMPILER_CLANG && (KMP_MSVC_COMPAT || __MINGW32__)) || \
1710  (KMP_COMPILER_GCC && __MINGW32__)
1711 
1712 #include <immintrin.h>
1713 #define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT)
1714 
1715 #else
1716 
1717 // Values from the status register after failed speculation.
1718 #define _XBEGIN_STARTED (~0u)
1719 #define _XABORT_EXPLICIT (1 << 0)
1720 #define _XABORT_RETRY (1 << 1)
1721 #define _XABORT_CONFLICT (1 << 2)
1722 #define _XABORT_CAPACITY (1 << 3)
1723 #define _XABORT_DEBUG (1 << 4)
1724 #define _XABORT_NESTED (1 << 5)
1725 #define _XABORT_CODE(x) ((unsigned char)(((x) >> 24) & 0xFF))
1726 
1727 // Aborts for which it's worth trying again immediately
1728 #define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT)
1729 
1730 #define STRINGIZE_INTERNAL(arg) #arg
1731 #define STRINGIZE(arg) STRINGIZE_INTERNAL(arg)
1732 
1733 // Access to RTM instructions
1734 /*A version of XBegin which returns -1 on speculation, and the value of EAX on
1735  an abort. This is the same definition as the compiler intrinsic that will be
1736  supported at some point. */
1737 static __inline int _xbegin() {
1738  int res = -1;
1739 
1740 #if KMP_OS_WINDOWS
1741 #if KMP_ARCH_X86_64
1742  _asm {
1743  _emit 0xC7
1744  _emit 0xF8
1745  _emit 2
1746  _emit 0
1747  _emit 0
1748  _emit 0
1749  jmp L2
1750  mov res, eax
1751  L2:
1752  }
1753 #else /* IA32 */
1754  _asm {
1755  _emit 0xC7
1756  _emit 0xF8
1757  _emit 2
1758  _emit 0
1759  _emit 0
1760  _emit 0
1761  jmp L2
1762  mov res, eax
1763  L2:
1764  }
1765 #endif // KMP_ARCH_X86_64
1766 #else
1767  /* Note that %eax must be noted as killed (clobbered), because the XSR is
1768  returned in %eax(%rax) on abort. Other register values are restored, so
1769  don't need to be killed.
1770 
1771  We must also mark 'res' as an input and an output, since otherwise
1772  'res=-1' may be dropped as being dead, whereas we do need the assignment on
1773  the successful (i.e., non-abort) path. */
1774  __asm__ volatile("1: .byte 0xC7; .byte 0xF8;\n"
1775  " .long 1f-1b-6\n"
1776  " jmp 2f\n"
1777  "1: movl %%eax,%0\n"
1778  "2:"
1779  : "+r"(res)::"memory", "%eax");
1780 #endif // KMP_OS_WINDOWS
1781  return res;
1782 }
1783 
1784 /* Transaction end */
1785 static __inline void _xend() {
1786 #if KMP_OS_WINDOWS
1787  __asm {
1788  _emit 0x0f
1789  _emit 0x01
1790  _emit 0xd5
1791  }
1792 #else
1793  __asm__ volatile(".byte 0x0f; .byte 0x01; .byte 0xd5" ::: "memory");
1794 #endif
1795 }
1796 
1797 /* This is a macro, the argument must be a single byte constant which can be
1798  evaluated by the inline assembler, since it is emitted as a byte into the
1799  assembly code. */
1800 // clang-format off
1801 #if KMP_OS_WINDOWS
1802 #define _xabort(ARG) _asm _emit 0xc6 _asm _emit 0xf8 _asm _emit ARG
1803 #else
1804 #define _xabort(ARG) \
1805  __asm__ volatile(".byte 0xC6; .byte 0xF8; .byte " STRINGIZE(ARG):::"memory");
1806 #endif
1807 // clang-format on
1808 #endif // KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300
1809 
1810 // Statistics is collected for testing purpose
1811 #if KMP_DEBUG_ADAPTIVE_LOCKS
1812 
1813 // We accumulate speculative lock statistics when the lock is destroyed. We
1814 // keep locks that haven't been destroyed in the liveLocks list so that we can
1815 // grab their statistics too.
1816 static kmp_adaptive_lock_statistics_t destroyedStats;
1817 
1818 // To hold the list of live locks.
1819 static kmp_adaptive_lock_info_t liveLocks;
1820 
1821 // A lock so we can safely update the list of locks.
1822 static kmp_bootstrap_lock_t chain_lock =
1823  KMP_BOOTSTRAP_LOCK_INITIALIZER(chain_lock);
1824 
1825 // Initialize the list of stats.
1826 void __kmp_init_speculative_stats() {
1827  kmp_adaptive_lock_info_t *lck = &liveLocks;
1828 
1829  memset(CCAST(kmp_adaptive_lock_statistics_t *, &(lck->stats)), 0,
1830  sizeof(lck->stats));
1831  lck->stats.next = lck;
1832  lck->stats.prev = lck;
1833 
1834  KMP_ASSERT(lck->stats.next->stats.prev == lck);
1835  KMP_ASSERT(lck->stats.prev->stats.next == lck);
1836 
1837  __kmp_init_bootstrap_lock(&chain_lock);
1838 }
1839 
1840 // Insert the lock into the circular list
1841 static void __kmp_remember_lock(kmp_adaptive_lock_info_t *lck) {
1842  __kmp_acquire_bootstrap_lock(&chain_lock);
1843 
1844  lck->stats.next = liveLocks.stats.next;
1845  lck->stats.prev = &liveLocks;
1846 
1847  liveLocks.stats.next = lck;
1848  lck->stats.next->stats.prev = lck;
1849 
1850  KMP_ASSERT(lck->stats.next->stats.prev == lck);
1851  KMP_ASSERT(lck->stats.prev->stats.next == lck);
1852 
1853  __kmp_release_bootstrap_lock(&chain_lock);
1854 }
1855 
1856 static void __kmp_forget_lock(kmp_adaptive_lock_info_t *lck) {
1857  KMP_ASSERT(lck->stats.next->stats.prev == lck);
1858  KMP_ASSERT(lck->stats.prev->stats.next == lck);
1859 
1860  kmp_adaptive_lock_info_t *n = lck->stats.next;
1861  kmp_adaptive_lock_info_t *p = lck->stats.prev;
1862 
1863  n->stats.prev = p;
1864  p->stats.next = n;
1865 }
1866 
1867 static void __kmp_zero_speculative_stats(kmp_adaptive_lock_info_t *lck) {
1868  memset(CCAST(kmp_adaptive_lock_statistics_t *, &lck->stats), 0,
1869  sizeof(lck->stats));
1870  __kmp_remember_lock(lck);
1871 }
1872 
1873 static void __kmp_add_stats(kmp_adaptive_lock_statistics_t *t,
1874  kmp_adaptive_lock_info_t *lck) {
1875  kmp_adaptive_lock_statistics_t volatile *s = &lck->stats;
1876 
1877  t->nonSpeculativeAcquireAttempts += lck->acquire_attempts;
1878  t->successfulSpeculations += s->successfulSpeculations;
1879  t->hardFailedSpeculations += s->hardFailedSpeculations;
1880  t->softFailedSpeculations += s->softFailedSpeculations;
1881  t->nonSpeculativeAcquires += s->nonSpeculativeAcquires;
1882  t->lemmingYields += s->lemmingYields;
1883 }
1884 
1885 static void __kmp_accumulate_speculative_stats(kmp_adaptive_lock_info_t *lck) {
1886  __kmp_acquire_bootstrap_lock(&chain_lock);
1887 
1888  __kmp_add_stats(&destroyedStats, lck);
1889  __kmp_forget_lock(lck);
1890 
1891  __kmp_release_bootstrap_lock(&chain_lock);
1892 }
1893 
1894 static float percent(kmp_uint32 count, kmp_uint32 total) {
1895  return (total == 0) ? 0.0 : (100.0 * count) / total;
1896 }
1897 
1898 static FILE *__kmp_open_stats_file() {
1899  if (strcmp(__kmp_speculative_statsfile, "-") == 0)
1900  return stdout;
1901 
1902  size_t buffLen = KMP_STRLEN(__kmp_speculative_statsfile) + 20;
1903  char buffer[buffLen];
1904  KMP_SNPRINTF(&buffer[0], buffLen, __kmp_speculative_statsfile,
1905  (kmp_int32)getpid());
1906  FILE *result = fopen(&buffer[0], "w");
1907 
1908  // Maybe we should issue a warning here...
1909  return result ? result : stdout;
1910 }
1911 
1912 void __kmp_print_speculative_stats() {
1913  kmp_adaptive_lock_statistics_t total = destroyedStats;
1914  kmp_adaptive_lock_info_t *lck;
1915 
1916  for (lck = liveLocks.stats.next; lck != &liveLocks; lck = lck->stats.next) {
1917  __kmp_add_stats(&total, lck);
1918  }
1919  kmp_adaptive_lock_statistics_t *t = &total;
1920  kmp_uint32 totalSections =
1921  t->nonSpeculativeAcquires + t->successfulSpeculations;
1922  kmp_uint32 totalSpeculations = t->successfulSpeculations +
1923  t->hardFailedSpeculations +
1924  t->softFailedSpeculations;
1925  if (totalSections <= 0)
1926  return;
1927 
1928  FILE *statsFile = __kmp_open_stats_file();
1929 
1930  fprintf(statsFile, "Speculative lock statistics (all approximate!)\n");
1931  fprintf(statsFile, " Lock parameters: \n"
1932  " max_soft_retries : %10d\n"
1933  " max_badness : %10d\n",
1934  __kmp_adaptive_backoff_params.max_soft_retries,
1935  __kmp_adaptive_backoff_params.max_badness);
1936  fprintf(statsFile, " Non-speculative acquire attempts : %10d\n",
1937  t->nonSpeculativeAcquireAttempts);
1938  fprintf(statsFile, " Total critical sections : %10d\n",
1939  totalSections);
1940  fprintf(statsFile, " Successful speculations : %10d (%5.1f%%)\n",
1941  t->successfulSpeculations,
1942  percent(t->successfulSpeculations, totalSections));
1943  fprintf(statsFile, " Non-speculative acquires : %10d (%5.1f%%)\n",
1944  t->nonSpeculativeAcquires,
1945  percent(t->nonSpeculativeAcquires, totalSections));
1946  fprintf(statsFile, " Lemming yields : %10d\n\n",
1947  t->lemmingYields);
1948 
1949  fprintf(statsFile, " Speculative acquire attempts : %10d\n",
1950  totalSpeculations);
1951  fprintf(statsFile, " Successes : %10d (%5.1f%%)\n",
1952  t->successfulSpeculations,
1953  percent(t->successfulSpeculations, totalSpeculations));
1954  fprintf(statsFile, " Soft failures : %10d (%5.1f%%)\n",
1955  t->softFailedSpeculations,
1956  percent(t->softFailedSpeculations, totalSpeculations));
1957  fprintf(statsFile, " Hard failures : %10d (%5.1f%%)\n",
1958  t->hardFailedSpeculations,
1959  percent(t->hardFailedSpeculations, totalSpeculations));
1960 
1961  if (statsFile != stdout)
1962  fclose(statsFile);
1963 }
1964 
1965 #define KMP_INC_STAT(lck, stat) (lck->lk.adaptive.stats.stat++)
1966 #else
1967 #define KMP_INC_STAT(lck, stat)
1968 
1969 #endif // KMP_DEBUG_ADAPTIVE_LOCKS
1970 
1971 static inline bool __kmp_is_unlocked_queuing_lock(kmp_queuing_lock_t *lck) {
1972  // It is enough to check that the head_id is zero.
1973  // We don't also need to check the tail.
1974  bool res = lck->lk.head_id == 0;
1975 
1976 // We need a fence here, since we must ensure that no memory operations
1977 // from later in this thread float above that read.
1978 #if KMP_COMPILER_ICC
1979  _mm_mfence();
1980 #else
1981  __sync_synchronize();
1982 #endif
1983 
1984  return res;
1985 }
1986 
1987 // Functions for manipulating the badness
1988 static __inline void
1989 __kmp_update_badness_after_success(kmp_adaptive_lock_t *lck) {
1990  // Reset the badness to zero so we eagerly try to speculate again
1991  lck->lk.adaptive.badness = 0;
1992  KMP_INC_STAT(lck, successfulSpeculations);
1993 }
1994 
1995 // Create a bit mask with one more set bit.
1996 static __inline void __kmp_step_badness(kmp_adaptive_lock_t *lck) {
1997  kmp_uint32 newBadness = (lck->lk.adaptive.badness << 1) | 1;
1998  if (newBadness > lck->lk.adaptive.max_badness) {
1999  return;
2000  } else {
2001  lck->lk.adaptive.badness = newBadness;
2002  }
2003 }
2004 
2005 // Check whether speculation should be attempted.
2006 static __inline int __kmp_should_speculate(kmp_adaptive_lock_t *lck,
2007  kmp_int32 gtid) {
2008  kmp_uint32 badness = lck->lk.adaptive.badness;
2009  kmp_uint32 attempts = lck->lk.adaptive.acquire_attempts;
2010  int res = (attempts & badness) == 0;
2011  return res;
2012 }
2013 
2014 // Attempt to acquire only the speculative lock.
2015 // Does not back off to the non-speculative lock.
2016 static int __kmp_test_adaptive_lock_only(kmp_adaptive_lock_t *lck,
2017  kmp_int32 gtid) {
2018  int retries = lck->lk.adaptive.max_soft_retries;
2019 
2020  // We don't explicitly count the start of speculation, rather we record the
2021  // results (success, hard fail, soft fail). The sum of all of those is the
2022  // total number of times we started speculation since all speculations must
2023  // end one of those ways.
2024  do {
2025  kmp_uint32 status = _xbegin();
2026  // Switch this in to disable actual speculation but exercise at least some
2027  // of the rest of the code. Useful for debugging...
2028  // kmp_uint32 status = _XABORT_NESTED;
2029 
2030  if (status == _XBEGIN_STARTED) {
2031  /* We have successfully started speculation. Check that no-one acquired
2032  the lock for real between when we last looked and now. This also gets
2033  the lock cache line into our read-set, which we need so that we'll
2034  abort if anyone later claims it for real. */
2035  if (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) {
2036  // Lock is now visibly acquired, so someone beat us to it. Abort the
2037  // transaction so we'll restart from _xbegin with the failure status.
2038  _xabort(0x01);
2039  KMP_ASSERT2(0, "should not get here");
2040  }
2041  return 1; // Lock has been acquired (speculatively)
2042  } else {
2043  // We have aborted, update the statistics
2044  if (status & SOFT_ABORT_MASK) {
2045  KMP_INC_STAT(lck, softFailedSpeculations);
2046  // and loop round to retry.
2047  } else {
2048  KMP_INC_STAT(lck, hardFailedSpeculations);
2049  // Give up if we had a hard failure.
2050  break;
2051  }
2052  }
2053  } while (retries--); // Loop while we have retries, and didn't fail hard.
2054 
2055  // Either we had a hard failure or we didn't succeed softly after
2056  // the full set of attempts, so back off the badness.
2057  __kmp_step_badness(lck);
2058  return 0;
2059 }
2060 
2061 // Attempt to acquire the speculative lock, or back off to the non-speculative
2062 // one if the speculative lock cannot be acquired.
2063 // We can succeed speculatively, non-speculatively, or fail.
2064 static int __kmp_test_adaptive_lock(kmp_adaptive_lock_t *lck, kmp_int32 gtid) {
2065  // First try to acquire the lock speculatively
2066  if (__kmp_should_speculate(lck, gtid) &&
2067  __kmp_test_adaptive_lock_only(lck, gtid))
2068  return 1;
2069 
2070  // Speculative acquisition failed, so try to acquire it non-speculatively.
2071  // Count the non-speculative acquire attempt
2072  lck->lk.adaptive.acquire_attempts++;
2073 
2074  // Use base, non-speculative lock.
2075  if (__kmp_test_queuing_lock(GET_QLK_PTR(lck), gtid)) {
2076  KMP_INC_STAT(lck, nonSpeculativeAcquires);
2077  return 1; // Lock is acquired (non-speculatively)
2078  } else {
2079  return 0; // Failed to acquire the lock, it's already visibly locked.
2080  }
2081 }
2082 
2083 static int __kmp_test_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck,
2084  kmp_int32 gtid) {
2085  char const *const func = "omp_test_lock";
2086  if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2087  KMP_FATAL(LockIsUninitialized, func);
2088  }
2089 
2090  int retval = __kmp_test_adaptive_lock(lck, gtid);
2091 
2092  if (retval) {
2093  lck->lk.qlk.owner_id = gtid + 1;
2094  }
2095  return retval;
2096 }
2097 
2098 // Block until we can acquire a speculative, adaptive lock. We check whether we
2099 // should be trying to speculate. If we should be, we check the real lock to see
2100 // if it is free, and, if not, pause without attempting to acquire it until it
2101 // is. Then we try the speculative acquire. This means that although we suffer
2102 // from lemmings a little (because all we can't acquire the lock speculatively
2103 // until the queue of threads waiting has cleared), we don't get into a state
2104 // where we can never acquire the lock speculatively (because we force the queue
2105 // to clear by preventing new arrivals from entering the queue). This does mean
2106 // that when we're trying to break lemmings, the lock is no longer fair. However
2107 // OpenMP makes no guarantee that its locks are fair, so this isn't a real
2108 // problem.
2109 static void __kmp_acquire_adaptive_lock(kmp_adaptive_lock_t *lck,
2110  kmp_int32 gtid) {
2111  if (__kmp_should_speculate(lck, gtid)) {
2112  if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) {
2113  if (__kmp_test_adaptive_lock_only(lck, gtid))
2114  return;
2115  // We tried speculation and failed, so give up.
2116  } else {
2117  // We can't try speculation until the lock is free, so we pause here
2118  // (without suspending on the queueing lock, to allow it to drain, then
2119  // try again. All other threads will also see the same result for
2120  // shouldSpeculate, so will be doing the same if they try to claim the
2121  // lock from now on.
2122  while (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) {
2123  KMP_INC_STAT(lck, lemmingYields);
2124  KMP_YIELD(TRUE);
2125  }
2126 
2127  if (__kmp_test_adaptive_lock_only(lck, gtid))
2128  return;
2129  }
2130  }
2131 
2132  // Speculative acquisition failed, so acquire it non-speculatively.
2133  // Count the non-speculative acquire attempt
2134  lck->lk.adaptive.acquire_attempts++;
2135 
2136  __kmp_acquire_queuing_lock_timed_template<FALSE>(GET_QLK_PTR(lck), gtid);
2137  // We have acquired the base lock, so count that.
2138  KMP_INC_STAT(lck, nonSpeculativeAcquires);
2139  ANNOTATE_QUEUING_ACQUIRED(lck);
2140 }
2141 
2142 static void __kmp_acquire_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck,
2143  kmp_int32 gtid) {
2144  char const *const func = "omp_set_lock";
2145  if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2146  KMP_FATAL(LockIsUninitialized, func);
2147  }
2148  if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == gtid) {
2149  KMP_FATAL(LockIsAlreadyOwned, func);
2150  }
2151 
2152  __kmp_acquire_adaptive_lock(lck, gtid);
2153 
2154  lck->lk.qlk.owner_id = gtid + 1;
2155 }
2156 
2157 static int __kmp_release_adaptive_lock(kmp_adaptive_lock_t *lck,
2158  kmp_int32 gtid) {
2159  if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(
2160  lck))) { // If the lock doesn't look claimed we must be speculating.
2161  // (Or the user's code is buggy and they're releasing without locking;
2162  // if we had XTEST we'd be able to check that case...)
2163  _xend(); // Exit speculation
2164  __kmp_update_badness_after_success(lck);
2165  } else { // Since the lock *is* visibly locked we're not speculating,
2166  // so should use the underlying lock's release scheme.
2167  __kmp_release_queuing_lock(GET_QLK_PTR(lck), gtid);
2168  }
2169  return KMP_LOCK_RELEASED;
2170 }
2171 
2172 static int __kmp_release_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck,
2173  kmp_int32 gtid) {
2174  char const *const func = "omp_unset_lock";
2175  KMP_MB(); /* in case another processor initialized lock */
2176  if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2177  KMP_FATAL(LockIsUninitialized, func);
2178  }
2179  if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == -1) {
2180  KMP_FATAL(LockUnsettingFree, func);
2181  }
2182  if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != gtid) {
2183  KMP_FATAL(LockUnsettingSetByAnother, func);
2184  }
2185  lck->lk.qlk.owner_id = 0;
2186  __kmp_release_adaptive_lock(lck, gtid);
2187  return KMP_LOCK_RELEASED;
2188 }
2189 
2190 static void __kmp_init_adaptive_lock(kmp_adaptive_lock_t *lck) {
2191  __kmp_init_queuing_lock(GET_QLK_PTR(lck));
2192  lck->lk.adaptive.badness = 0;
2193  lck->lk.adaptive.acquire_attempts = 0; // nonSpeculativeAcquireAttempts = 0;
2194  lck->lk.adaptive.max_soft_retries =
2195  __kmp_adaptive_backoff_params.max_soft_retries;
2196  lck->lk.adaptive.max_badness = __kmp_adaptive_backoff_params.max_badness;
2197 #if KMP_DEBUG_ADAPTIVE_LOCKS
2198  __kmp_zero_speculative_stats(&lck->lk.adaptive);
2199 #endif
2200  KA_TRACE(1000, ("__kmp_init_adaptive_lock: lock %p initialized\n", lck));
2201 }
2202 
2203 static void __kmp_destroy_adaptive_lock(kmp_adaptive_lock_t *lck) {
2204 #if KMP_DEBUG_ADAPTIVE_LOCKS
2205  __kmp_accumulate_speculative_stats(&lck->lk.adaptive);
2206 #endif
2207  __kmp_destroy_queuing_lock(GET_QLK_PTR(lck));
2208  // Nothing needed for the speculative part.
2209 }
2210 
2211 static void __kmp_destroy_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck) {
2212  char const *const func = "omp_destroy_lock";
2213  if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2214  KMP_FATAL(LockIsUninitialized, func);
2215  }
2216  if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != -1) {
2217  KMP_FATAL(LockStillOwned, func);
2218  }
2219  __kmp_destroy_adaptive_lock(lck);
2220 }
2221 
2222 #endif // KMP_USE_ADAPTIVE_LOCKS
2223 
2224 /* ------------------------------------------------------------------------ */
2225 /* DRDPA ticket locks */
2226 /* "DRDPA" means Dynamically Reconfigurable Distributed Polling Area */
2227 
2228 static kmp_int32 __kmp_get_drdpa_lock_owner(kmp_drdpa_lock_t *lck) {
2229  return lck->lk.owner_id - 1;
2230 }
2231 
2232 static inline bool __kmp_is_drdpa_lock_nestable(kmp_drdpa_lock_t *lck) {
2233  return lck->lk.depth_locked != -1;
2234 }
2235 
2236 __forceinline static int
2237 __kmp_acquire_drdpa_lock_timed_template(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2238  kmp_uint64 ticket = KMP_ATOMIC_INC(&lck->lk.next_ticket);
2239  kmp_uint64 mask = lck->lk.mask; // atomic load
2240  std::atomic<kmp_uint64> *polls = lck->lk.polls;
2241 
2242 #ifdef USE_LOCK_PROFILE
2243  if (polls[ticket & mask] != ticket)
2244  __kmp_printf("LOCK CONTENTION: %p\n", lck);
2245 /* else __kmp_printf( "." );*/
2246 #endif /* USE_LOCK_PROFILE */
2247 
2248  // Now spin-wait, but reload the polls pointer and mask, in case the
2249  // polling area has been reconfigured. Unless it is reconfigured, the
2250  // reloads stay in L1 cache and are cheap.
2251  //
2252  // Keep this code in sync with KMP_WAIT, in kmp_dispatch.cpp !!!
2253  // The current implementation of KMP_WAIT doesn't allow for mask
2254  // and poll to be re-read every spin iteration.
2255  kmp_uint32 spins;
2256  KMP_FSYNC_PREPARE(lck);
2257  KMP_INIT_YIELD(spins);
2258  while (polls[ticket & mask] < ticket) { // atomic load
2259  KMP_YIELD_OVERSUB_ELSE_SPIN(spins);
2260  // Re-read the mask and the poll pointer from the lock structure.
2261  //
2262  // Make certain that "mask" is read before "polls" !!!
2263  //
2264  // If another thread picks reconfigures the polling area and updates their
2265  // values, and we get the new value of mask and the old polls pointer, we
2266  // could access memory beyond the end of the old polling area.
2267  mask = lck->lk.mask; // atomic load
2268  polls = lck->lk.polls; // atomic load
2269  }
2270 
2271  // Critical section starts here
2272  KMP_FSYNC_ACQUIRED(lck);
2273  KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld acquired lock %p\n",
2274  ticket, lck));
2275  lck->lk.now_serving = ticket; // non-volatile store
2276 
2277  // Deallocate a garbage polling area if we know that we are the last
2278  // thread that could possibly access it.
2279  //
2280  // The >= check is in case __kmp_test_drdpa_lock() allocated the cleanup
2281  // ticket.
2282  if ((lck->lk.old_polls != NULL) && (ticket >= lck->lk.cleanup_ticket)) {
2283  __kmp_free(lck->lk.old_polls);
2284  lck->lk.old_polls = NULL;
2285  lck->lk.cleanup_ticket = 0;
2286  }
2287 
2288  // Check to see if we should reconfigure the polling area.
2289  // If there is still a garbage polling area to be deallocated from a
2290  // previous reconfiguration, let a later thread reconfigure it.
2291  if (lck->lk.old_polls == NULL) {
2292  bool reconfigure = false;
2293  std::atomic<kmp_uint64> *old_polls = polls;
2294  kmp_uint32 num_polls = TCR_4(lck->lk.num_polls);
2295 
2296  if (TCR_4(__kmp_nth) >
2297  (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) {
2298  // We are in oversubscription mode. Contract the polling area
2299  // down to a single location, if that hasn't been done already.
2300  if (num_polls > 1) {
2301  reconfigure = true;
2302  num_polls = TCR_4(lck->lk.num_polls);
2303  mask = 0;
2304  num_polls = 1;
2305  polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls *
2306  sizeof(*polls));
2307  polls[0] = ticket;
2308  }
2309  } else {
2310  // We are in under/fully subscribed mode. Check the number of
2311  // threads waiting on the lock. The size of the polling area
2312  // should be at least the number of threads waiting.
2313  kmp_uint64 num_waiting = TCR_8(lck->lk.next_ticket) - ticket - 1;
2314  if (num_waiting > num_polls) {
2315  kmp_uint32 old_num_polls = num_polls;
2316  reconfigure = true;
2317  do {
2318  mask = (mask << 1) | 1;
2319  num_polls *= 2;
2320  } while (num_polls <= num_waiting);
2321 
2322  // Allocate the new polling area, and copy the relevant portion
2323  // of the old polling area to the new area. __kmp_allocate()
2324  // zeroes the memory it allocates, and most of the old area is
2325  // just zero padding, so we only copy the release counters.
2326  polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls *
2327  sizeof(*polls));
2328  kmp_uint32 i;
2329  for (i = 0; i < old_num_polls; i++) {
2330  polls[i].store(old_polls[i]);
2331  }
2332  }
2333  }
2334 
2335  if (reconfigure) {
2336  // Now write the updated fields back to the lock structure.
2337  //
2338  // Make certain that "polls" is written before "mask" !!!
2339  //
2340  // If another thread picks up the new value of mask and the old polls
2341  // pointer , it could access memory beyond the end of the old polling
2342  // area.
2343  //
2344  // On x86, we need memory fences.
2345  KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld reconfiguring "
2346  "lock %p to %d polls\n",
2347  ticket, lck, num_polls));
2348 
2349  lck->lk.old_polls = old_polls;
2350  lck->lk.polls = polls; // atomic store
2351 
2352  KMP_MB();
2353 
2354  lck->lk.num_polls = num_polls;
2355  lck->lk.mask = mask; // atomic store
2356 
2357  KMP_MB();
2358 
2359  // Only after the new polling area and mask have been flushed
2360  // to main memory can we update the cleanup ticket field.
2361  //
2362  // volatile load / non-volatile store
2363  lck->lk.cleanup_ticket = lck->lk.next_ticket;
2364  }
2365  }
2366  return KMP_LOCK_ACQUIRED_FIRST;
2367 }
2368 
2369 int __kmp_acquire_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2370  int retval = __kmp_acquire_drdpa_lock_timed_template(lck, gtid);
2371  ANNOTATE_DRDPA_ACQUIRED(lck);
2372  return retval;
2373 }
2374 
2375 static int __kmp_acquire_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2376  kmp_int32 gtid) {
2377  char const *const func = "omp_set_lock";
2378  if (lck->lk.initialized != lck) {
2379  KMP_FATAL(LockIsUninitialized, func);
2380  }
2381  if (__kmp_is_drdpa_lock_nestable(lck)) {
2382  KMP_FATAL(LockNestableUsedAsSimple, func);
2383  }
2384  if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) == gtid)) {
2385  KMP_FATAL(LockIsAlreadyOwned, func);
2386  }
2387 
2388  __kmp_acquire_drdpa_lock(lck, gtid);
2389 
2390  lck->lk.owner_id = gtid + 1;
2391  return KMP_LOCK_ACQUIRED_FIRST;
2392 }
2393 
2394 int __kmp_test_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2395  // First get a ticket, then read the polls pointer and the mask.
2396  // The polls pointer must be read before the mask!!! (See above)
2397  kmp_uint64 ticket = lck->lk.next_ticket; // atomic load
2398  std::atomic<kmp_uint64> *polls = lck->lk.polls;
2399  kmp_uint64 mask = lck->lk.mask; // atomic load
2400  if (polls[ticket & mask] == ticket) {
2401  kmp_uint64 next_ticket = ticket + 1;
2402  if (__kmp_atomic_compare_store_acq(&lck->lk.next_ticket, ticket,
2403  next_ticket)) {
2404  KMP_FSYNC_ACQUIRED(lck);
2405  KA_TRACE(1000, ("__kmp_test_drdpa_lock: ticket #%lld acquired lock %p\n",
2406  ticket, lck));
2407  lck->lk.now_serving = ticket; // non-volatile store
2408 
2409  // Since no threads are waiting, there is no possibility that we would
2410  // want to reconfigure the polling area. We might have the cleanup ticket
2411  // value (which says that it is now safe to deallocate old_polls), but
2412  // we'll let a later thread which calls __kmp_acquire_lock do that - this
2413  // routine isn't supposed to block, and we would risk blocks if we called
2414  // __kmp_free() to do the deallocation.
2415  return TRUE;
2416  }
2417  }
2418  return FALSE;
2419 }
2420 
2421 static int __kmp_test_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2422  kmp_int32 gtid) {
2423  char const *const func = "omp_test_lock";
2424  if (lck->lk.initialized != lck) {
2425  KMP_FATAL(LockIsUninitialized, func);
2426  }
2427  if (__kmp_is_drdpa_lock_nestable(lck)) {
2428  KMP_FATAL(LockNestableUsedAsSimple, func);
2429  }
2430 
2431  int retval = __kmp_test_drdpa_lock(lck, gtid);
2432 
2433  if (retval) {
2434  lck->lk.owner_id = gtid + 1;
2435  }
2436  return retval;
2437 }
2438 
2439 int __kmp_release_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2440  // Read the ticket value from the lock data struct, then the polls pointer and
2441  // the mask. The polls pointer must be read before the mask!!! (See above)
2442  kmp_uint64 ticket = lck->lk.now_serving + 1; // non-atomic load
2443  std::atomic<kmp_uint64> *polls = lck->lk.polls; // atomic load
2444  kmp_uint64 mask = lck->lk.mask; // atomic load
2445  KA_TRACE(1000, ("__kmp_release_drdpa_lock: ticket #%lld released lock %p\n",
2446  ticket - 1, lck));
2447  KMP_FSYNC_RELEASING(lck);
2448  ANNOTATE_DRDPA_RELEASED(lck);
2449  polls[ticket & mask] = ticket; // atomic store
2450  return KMP_LOCK_RELEASED;
2451 }
2452 
2453 static int __kmp_release_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2454  kmp_int32 gtid) {
2455  char const *const func = "omp_unset_lock";
2456  KMP_MB(); /* in case another processor initialized lock */
2457  if (lck->lk.initialized != lck) {
2458  KMP_FATAL(LockIsUninitialized, func);
2459  }
2460  if (__kmp_is_drdpa_lock_nestable(lck)) {
2461  KMP_FATAL(LockNestableUsedAsSimple, func);
2462  }
2463  if (__kmp_get_drdpa_lock_owner(lck) == -1) {
2464  KMP_FATAL(LockUnsettingFree, func);
2465  }
2466  if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) >= 0) &&
2467  (__kmp_get_drdpa_lock_owner(lck) != gtid)) {
2468  KMP_FATAL(LockUnsettingSetByAnother, func);
2469  }
2470  lck->lk.owner_id = 0;
2471  return __kmp_release_drdpa_lock(lck, gtid);
2472 }
2473 
2474 void __kmp_init_drdpa_lock(kmp_drdpa_lock_t *lck) {
2475  lck->lk.location = NULL;
2476  lck->lk.mask = 0;
2477  lck->lk.num_polls = 1;
2478  lck->lk.polls = (std::atomic<kmp_uint64> *)__kmp_allocate(
2479  lck->lk.num_polls * sizeof(*(lck->lk.polls)));
2480  lck->lk.cleanup_ticket = 0;
2481  lck->lk.old_polls = NULL;
2482  lck->lk.next_ticket = 0;
2483  lck->lk.now_serving = 0;
2484  lck->lk.owner_id = 0; // no thread owns the lock.
2485  lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks.
2486  lck->lk.initialized = lck;
2487 
2488  KA_TRACE(1000, ("__kmp_init_drdpa_lock: lock %p initialized\n", lck));
2489 }
2490 
2491 void __kmp_destroy_drdpa_lock(kmp_drdpa_lock_t *lck) {
2492  lck->lk.initialized = NULL;
2493  lck->lk.location = NULL;
2494  if (lck->lk.polls.load() != NULL) {
2495  __kmp_free(lck->lk.polls.load());
2496  lck->lk.polls = NULL;
2497  }
2498  if (lck->lk.old_polls != NULL) {
2499  __kmp_free(lck->lk.old_polls);
2500  lck->lk.old_polls = NULL;
2501  }
2502  lck->lk.mask = 0;
2503  lck->lk.num_polls = 0;
2504  lck->lk.cleanup_ticket = 0;
2505  lck->lk.next_ticket = 0;
2506  lck->lk.now_serving = 0;
2507  lck->lk.owner_id = 0;
2508  lck->lk.depth_locked = -1;
2509 }
2510 
2511 static void __kmp_destroy_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) {
2512  char const *const func = "omp_destroy_lock";
2513  if (lck->lk.initialized != lck) {
2514  KMP_FATAL(LockIsUninitialized, func);
2515  }
2516  if (__kmp_is_drdpa_lock_nestable(lck)) {
2517  KMP_FATAL(LockNestableUsedAsSimple, func);
2518  }
2519  if (__kmp_get_drdpa_lock_owner(lck) != -1) {
2520  KMP_FATAL(LockStillOwned, func);
2521  }
2522  __kmp_destroy_drdpa_lock(lck);
2523 }
2524 
2525 // nested drdpa ticket locks
2526 
2527 int __kmp_acquire_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2528  KMP_DEBUG_ASSERT(gtid >= 0);
2529 
2530  if (__kmp_get_drdpa_lock_owner(lck) == gtid) {
2531  lck->lk.depth_locked += 1;
2532  return KMP_LOCK_ACQUIRED_NEXT;
2533  } else {
2534  __kmp_acquire_drdpa_lock_timed_template(lck, gtid);
2535  ANNOTATE_DRDPA_ACQUIRED(lck);
2536  KMP_MB();
2537  lck->lk.depth_locked = 1;
2538  KMP_MB();
2539  lck->lk.owner_id = gtid + 1;
2540  return KMP_LOCK_ACQUIRED_FIRST;
2541  }
2542 }
2543 
2544 static void __kmp_acquire_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2545  kmp_int32 gtid) {
2546  char const *const func = "omp_set_nest_lock";
2547  if (lck->lk.initialized != lck) {
2548  KMP_FATAL(LockIsUninitialized, func);
2549  }
2550  if (!__kmp_is_drdpa_lock_nestable(lck)) {
2551  KMP_FATAL(LockSimpleUsedAsNestable, func);
2552  }
2553  __kmp_acquire_nested_drdpa_lock(lck, gtid);
2554 }
2555 
2556 int __kmp_test_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2557  int retval;
2558 
2559  KMP_DEBUG_ASSERT(gtid >= 0);
2560 
2561  if (__kmp_get_drdpa_lock_owner(lck) == gtid) {
2562  retval = ++lck->lk.depth_locked;
2563  } else if (!__kmp_test_drdpa_lock(lck, gtid)) {
2564  retval = 0;
2565  } else {
2566  KMP_MB();
2567  retval = lck->lk.depth_locked = 1;
2568  KMP_MB();
2569  lck->lk.owner_id = gtid + 1;
2570  }
2571  return retval;
2572 }
2573 
2574 static int __kmp_test_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2575  kmp_int32 gtid) {
2576  char const *const func = "omp_test_nest_lock";
2577  if (lck->lk.initialized != lck) {
2578  KMP_FATAL(LockIsUninitialized, func);
2579  }
2580  if (!__kmp_is_drdpa_lock_nestable(lck)) {
2581  KMP_FATAL(LockSimpleUsedAsNestable, func);
2582  }
2583  return __kmp_test_nested_drdpa_lock(lck, gtid);
2584 }
2585 
2586 int __kmp_release_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2587  KMP_DEBUG_ASSERT(gtid >= 0);
2588 
2589  KMP_MB();
2590  if (--(lck->lk.depth_locked) == 0) {
2591  KMP_MB();
2592  lck->lk.owner_id = 0;
2593  __kmp_release_drdpa_lock(lck, gtid);
2594  return KMP_LOCK_RELEASED;
2595  }
2596  return KMP_LOCK_STILL_HELD;