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  long 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=%ld 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 
1095 #if OMPT_SUPPORT
1096  ompt_state_t prev_state = ompt_state_undefined;
1097 #endif
1098 
1099  KA_TRACE(1000,
1100  ("__kmp_acquire_queuing_lock: lck:%p, T#%d entering\n", lck, gtid));
1101 
1102  KMP_FSYNC_PREPARE(lck);
1103  KMP_DEBUG_ASSERT(this_thr != NULL);
1104  spin_here_p = &this_thr->th.th_spin_here;
1105 
1106 #ifdef DEBUG_QUEUING_LOCKS
1107  TRACE_LOCK(gtid + 1, "acq ent");
1108  if (*spin_here_p)
1109  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1110  if (this_thr->th.th_next_waiting != 0)
1111  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1112 #endif
1113  KMP_DEBUG_ASSERT(!*spin_here_p);
1114  KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1115 
1116  /* The following st.rel to spin_here_p needs to precede the cmpxchg.acq to
1117  head_id_p that may follow, not just in execution order, but also in
1118  visibility order. This way, when a releasing thread observes the changes to
1119  the queue by this thread, it can rightly assume that spin_here_p has
1120  already been set to TRUE, so that when it sets spin_here_p to FALSE, it is
1121  not premature. If the releasing thread sets spin_here_p to FALSE before
1122  this thread sets it to TRUE, this thread will hang. */
1123  *spin_here_p = TRUE; /* before enqueuing to prevent race */
1124 
1125  while (1) {
1126  kmp_int32 enqueued;
1127  kmp_int32 head;
1128  kmp_int32 tail;
1129 
1130  head = *head_id_p;
1131 
1132  switch (head) {
1133 
1134  case -1: {
1135 #ifdef DEBUG_QUEUING_LOCKS
1136  tail = *tail_id_p;
1137  TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1138 #endif
1139  tail = 0; /* to make sure next link asynchronously read is not set
1140  accidentally; this assignment prevents us from entering the
1141  if ( t > 0 ) condition in the enqueued case below, which is not
1142  necessary for this state transition */
1143 
1144  /* try (-1,0)->(tid,tid) */
1145  enqueued = KMP_COMPARE_AND_STORE_ACQ64((volatile kmp_int64 *)tail_id_p,
1146  KMP_PACK_64(-1, 0),
1147  KMP_PACK_64(gtid + 1, gtid + 1));
1148 #ifdef DEBUG_QUEUING_LOCKS
1149  if (enqueued)
1150  TRACE_LOCK(gtid + 1, "acq enq: (-1,0)->(tid,tid)");
1151 #endif
1152  } break;
1153 
1154  default: {
1155  tail = *tail_id_p;
1156  KMP_DEBUG_ASSERT(tail != gtid + 1);
1157 
1158 #ifdef DEBUG_QUEUING_LOCKS
1159  TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1160 #endif
1161 
1162  if (tail == 0) {
1163  enqueued = FALSE;
1164  } else {
1165  /* try (h,t) or (h,h)->(h,tid) */
1166  enqueued = KMP_COMPARE_AND_STORE_ACQ32(tail_id_p, tail, gtid + 1);
1167 
1168 #ifdef DEBUG_QUEUING_LOCKS
1169  if (enqueued)
1170  TRACE_LOCK(gtid + 1, "acq enq: (h,t)->(h,tid)");
1171 #endif
1172  }
1173  } break;
1174 
1175  case 0: /* empty queue */
1176  {
1177  kmp_int32 grabbed_lock;
1178 
1179 #ifdef DEBUG_QUEUING_LOCKS
1180  tail = *tail_id_p;
1181  TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1182 #endif
1183  /* try (0,0)->(-1,0) */
1184 
1185  /* only legal transition out of head = 0 is head = -1 with no change to
1186  * tail */
1187  grabbed_lock = KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1);
1188 
1189  if (grabbed_lock) {
1190 
1191  *spin_here_p = FALSE;
1192 
1193  KA_TRACE(
1194  1000,
1195  ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: no queuing\n",
1196  lck, gtid));
1197 #ifdef DEBUG_QUEUING_LOCKS
1198  TRACE_LOCK_HT(gtid + 1, "acq exit: ", head, 0);
1199 #endif
1200 
1201 #if OMPT_SUPPORT
1202  if (ompt_enabled.enabled && prev_state != ompt_state_undefined) {
1203  /* change the state before clearing wait_id */
1204  this_thr->th.ompt_thread_info.state = prev_state;
1205  this_thr->th.ompt_thread_info.wait_id = 0;
1206  }
1207 #endif
1208 
1209  KMP_FSYNC_ACQUIRED(lck);
1210  return KMP_LOCK_ACQUIRED_FIRST; /* lock holder cannot be on queue */
1211  }
1212  enqueued = FALSE;
1213  } break;
1214  }
1215 
1216 #if OMPT_SUPPORT
1217  if (ompt_enabled.enabled && prev_state == ompt_state_undefined) {
1218  /* this thread will spin; set wait_id before entering wait state */
1219  prev_state = this_thr->th.ompt_thread_info.state;
1220  this_thr->th.ompt_thread_info.wait_id = (uint64_t)lck;
1221  this_thr->th.ompt_thread_info.state = ompt_state_wait_lock;
1222  }
1223 #endif
1224 
1225  if (enqueued) {
1226  if (tail > 0) {
1227  kmp_info_t *tail_thr = __kmp_thread_from_gtid(tail - 1);
1228  KMP_ASSERT(tail_thr != NULL);
1229  tail_thr->th.th_next_waiting = gtid + 1;
1230  /* corresponding wait for this write in release code */
1231  }
1232  KA_TRACE(1000,
1233  ("__kmp_acquire_queuing_lock: lck:%p, T#%d waiting for lock\n",
1234  lck, gtid));
1235 
1236  KMP_MB();
1237  // ToDo: Use __kmp_wait_sleep or similar when blocktime != inf
1238  KMP_WAIT(spin_here_p, FALSE, KMP_EQ, lck);
1239  // Synchronize writes to both runtime thread structures
1240  // and writes in user code.
1241  KMP_MB();
1242 
1243 #ifdef DEBUG_QUEUING_LOCKS
1244  TRACE_LOCK(gtid + 1, "acq spin");
1245 
1246  if (this_thr->th.th_next_waiting != 0)
1247  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1248 #endif
1249  KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1250  KA_TRACE(1000, ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: after "
1251  "waiting on queue\n",
1252  lck, gtid));
1253 
1254 #ifdef DEBUG_QUEUING_LOCKS
1255  TRACE_LOCK(gtid + 1, "acq exit 2");
1256 #endif
1257 
1258 #if OMPT_SUPPORT
1259  /* change the state before clearing wait_id */
1260  this_thr->th.ompt_thread_info.state = prev_state;
1261  this_thr->th.ompt_thread_info.wait_id = 0;
1262 #endif
1263 
1264  /* got lock, we were dequeued by the thread that released lock */
1265  return KMP_LOCK_ACQUIRED_FIRST;
1266  }
1267 
1268  /* Yield if number of threads > number of logical processors */
1269  /* ToDo: Not sure why this should only be in oversubscription case,
1270  maybe should be traditional YIELD_INIT/YIELD_WHEN loop */
1271  KMP_YIELD_OVERSUB();
1272 
1273 #ifdef DEBUG_QUEUING_LOCKS
1274  TRACE_LOCK(gtid + 1, "acq retry");
1275 #endif
1276  }
1277  KMP_ASSERT2(0, "should not get here");
1278  return KMP_LOCK_ACQUIRED_FIRST;
1279 }
1280 
1281 int __kmp_acquire_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1282  KMP_DEBUG_ASSERT(gtid >= 0);
1283 
1284  int retval = __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid);
1285  ANNOTATE_QUEUING_ACQUIRED(lck);
1286  return retval;
1287 }
1288 
1289 static int __kmp_acquire_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1290  kmp_int32 gtid) {
1291  char const *const func = "omp_set_lock";
1292  if (lck->lk.initialized != lck) {
1293  KMP_FATAL(LockIsUninitialized, func);
1294  }
1295  if (__kmp_is_queuing_lock_nestable(lck)) {
1296  KMP_FATAL(LockNestableUsedAsSimple, func);
1297  }
1298  if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1299  KMP_FATAL(LockIsAlreadyOwned, func);
1300  }
1301 
1302  __kmp_acquire_queuing_lock(lck, gtid);
1303 
1304  lck->lk.owner_id = gtid + 1;
1305  return KMP_LOCK_ACQUIRED_FIRST;
1306 }
1307 
1308 int __kmp_test_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1309  volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1310  kmp_int32 head;
1311 #ifdef KMP_DEBUG
1312  kmp_info_t *this_thr;
1313 #endif
1314 
1315  KA_TRACE(1000, ("__kmp_test_queuing_lock: T#%d entering\n", gtid));
1316  KMP_DEBUG_ASSERT(gtid >= 0);
1317 #ifdef KMP_DEBUG
1318  this_thr = __kmp_thread_from_gtid(gtid);
1319  KMP_DEBUG_ASSERT(this_thr != NULL);
1320  KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here);
1321 #endif
1322 
1323  head = *head_id_p;
1324 
1325  if (head == 0) { /* nobody on queue, nobody holding */
1326  /* try (0,0)->(-1,0) */
1327  if (KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1)) {
1328  KA_TRACE(1000,
1329  ("__kmp_test_queuing_lock: T#%d exiting: holding lock\n", gtid));
1330  KMP_FSYNC_ACQUIRED(lck);
1331  ANNOTATE_QUEUING_ACQUIRED(lck);
1332  return TRUE;
1333  }
1334  }
1335 
1336  KA_TRACE(1000,
1337  ("__kmp_test_queuing_lock: T#%d exiting: without lock\n", gtid));
1338  return FALSE;
1339 }
1340 
1341 static int __kmp_test_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1342  kmp_int32 gtid) {
1343  char const *const func = "omp_test_lock";
1344  if (lck->lk.initialized != lck) {
1345  KMP_FATAL(LockIsUninitialized, func);
1346  }
1347  if (__kmp_is_queuing_lock_nestable(lck)) {
1348  KMP_FATAL(LockNestableUsedAsSimple, func);
1349  }
1350 
1351  int retval = __kmp_test_queuing_lock(lck, gtid);
1352 
1353  if (retval) {
1354  lck->lk.owner_id = gtid + 1;
1355  }
1356  return retval;
1357 }
1358 
1359 int __kmp_release_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1360  kmp_info_t *this_thr;
1361  volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1362  volatile kmp_int32 *tail_id_p = &lck->lk.tail_id;
1363 
1364  KA_TRACE(1000,
1365  ("__kmp_release_queuing_lock: lck:%p, T#%d entering\n", lck, gtid));
1366  KMP_DEBUG_ASSERT(gtid >= 0);
1367  this_thr = __kmp_thread_from_gtid(gtid);
1368  KMP_DEBUG_ASSERT(this_thr != NULL);
1369 #ifdef DEBUG_QUEUING_LOCKS
1370  TRACE_LOCK(gtid + 1, "rel ent");
1371 
1372  if (this_thr->th.th_spin_here)
1373  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1374  if (this_thr->th.th_next_waiting != 0)
1375  __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1376 #endif
1377  KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here);
1378  KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1379 
1380  KMP_FSYNC_RELEASING(lck);
1381  ANNOTATE_QUEUING_RELEASED(lck);
1382 
1383  while (1) {
1384  kmp_int32 dequeued;
1385  kmp_int32 head;
1386  kmp_int32 tail;
1387 
1388  head = *head_id_p;
1389 
1390 #ifdef DEBUG_QUEUING_LOCKS
1391  tail = *tail_id_p;
1392  TRACE_LOCK_HT(gtid + 1, "rel read: ", head, tail);
1393  if (head == 0)
1394  __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1395 #endif
1396  KMP_DEBUG_ASSERT(head !=
1397  0); /* holding the lock, head must be -1 or queue head */
1398 
1399  if (head == -1) { /* nobody on queue */
1400  /* try (-1,0)->(0,0) */
1401  if (KMP_COMPARE_AND_STORE_REL32(head_id_p, -1, 0)) {
1402  KA_TRACE(
1403  1000,
1404  ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: queue empty\n",
1405  lck, gtid));
1406 #ifdef DEBUG_QUEUING_LOCKS
1407  TRACE_LOCK_HT(gtid + 1, "rel exit: ", 0, 0);
1408 #endif
1409 
1410 #if OMPT_SUPPORT
1411 /* nothing to do - no other thread is trying to shift blame */
1412 #endif
1413  return KMP_LOCK_RELEASED;
1414  }
1415  dequeued = FALSE;
1416  } else {
1417  KMP_MB();
1418  tail = *tail_id_p;
1419  if (head == tail) { /* only one thread on the queue */
1420 #ifdef DEBUG_QUEUING_LOCKS
1421  if (head <= 0)
1422  __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1423 #endif
1424  KMP_DEBUG_ASSERT(head > 0);
1425 
1426  /* try (h,h)->(-1,0) */
1427  dequeued = KMP_COMPARE_AND_STORE_REL64(
1428  RCAST(volatile kmp_int64 *, tail_id_p), KMP_PACK_64(head, head),
1429  KMP_PACK_64(-1, 0));
1430 #ifdef DEBUG_QUEUING_LOCKS
1431  TRACE_LOCK(gtid + 1, "rel deq: (h,h)->(-1,0)");
1432 #endif
1433 
1434  } else {
1435  volatile kmp_int32 *waiting_id_p;
1436  kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1);
1437  KMP_DEBUG_ASSERT(head_thr != NULL);
1438  waiting_id_p = &head_thr->th.th_next_waiting;
1439 
1440 /* Does this require synchronous reads? */
1441 #ifdef DEBUG_QUEUING_LOCKS
1442  if (head <= 0 || tail <= 0)
1443  __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1444 #endif
1445  KMP_DEBUG_ASSERT(head > 0 && tail > 0);
1446 
1447  /* try (h,t)->(h',t) or (t,t) */
1448  KMP_MB();
1449  /* make sure enqueuing thread has time to update next waiting thread
1450  * field */
1451  *head_id_p =
1452  KMP_WAIT((volatile kmp_uint32 *)waiting_id_p, 0, KMP_NEQ, NULL);
1453 #ifdef DEBUG_QUEUING_LOCKS
1454  TRACE_LOCK(gtid + 1, "rel deq: (h,t)->(h',t)");
1455 #endif
1456  dequeued = TRUE;
1457  }
1458  }
1459 
1460  if (dequeued) {
1461  kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1);
1462  KMP_DEBUG_ASSERT(head_thr != NULL);
1463 
1464 /* Does this require synchronous reads? */
1465 #ifdef DEBUG_QUEUING_LOCKS
1466  if (head <= 0 || tail <= 0)
1467  __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1468 #endif
1469  KMP_DEBUG_ASSERT(head > 0 && tail > 0);
1470 
1471  /* For clean code only. Thread not released until next statement prevents
1472  race with acquire code. */
1473  head_thr->th.th_next_waiting = 0;
1474 #ifdef DEBUG_QUEUING_LOCKS
1475  TRACE_LOCK_T(gtid + 1, "rel nw=0 for t=", head);
1476 #endif
1477 
1478  KMP_MB();
1479  /* reset spin value */
1480  head_thr->th.th_spin_here = FALSE;
1481 
1482  KA_TRACE(1000, ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: after "
1483  "dequeuing\n",
1484  lck, gtid));
1485 #ifdef DEBUG_QUEUING_LOCKS
1486  TRACE_LOCK(gtid + 1, "rel exit 2");
1487 #endif
1488  return KMP_LOCK_RELEASED;
1489  }
1490  /* KMP_CPU_PAUSE(); don't want to make releasing thread hold up acquiring
1491  threads */
1492 
1493 #ifdef DEBUG_QUEUING_LOCKS
1494  TRACE_LOCK(gtid + 1, "rel retry");
1495 #endif
1496 
1497  } /* while */
1498  KMP_ASSERT2(0, "should not get here");
1499  return KMP_LOCK_RELEASED;
1500 }
1501 
1502 static int __kmp_release_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1503  kmp_int32 gtid) {
1504  char const *const func = "omp_unset_lock";
1505  KMP_MB(); /* in case another processor initialized lock */
1506  if (lck->lk.initialized != lck) {
1507  KMP_FATAL(LockIsUninitialized, func);
1508  }
1509  if (__kmp_is_queuing_lock_nestable(lck)) {
1510  KMP_FATAL(LockNestableUsedAsSimple, func);
1511  }
1512  if (__kmp_get_queuing_lock_owner(lck) == -1) {
1513  KMP_FATAL(LockUnsettingFree, func);
1514  }
1515  if (__kmp_get_queuing_lock_owner(lck) != gtid) {
1516  KMP_FATAL(LockUnsettingSetByAnother, func);
1517  }
1518  lck->lk.owner_id = 0;
1519  return __kmp_release_queuing_lock(lck, gtid);
1520 }
1521 
1522 void __kmp_init_queuing_lock(kmp_queuing_lock_t *lck) {
1523  lck->lk.location = NULL;
1524  lck->lk.head_id = 0;
1525  lck->lk.tail_id = 0;
1526  lck->lk.next_ticket = 0;
1527  lck->lk.now_serving = 0;
1528  lck->lk.owner_id = 0; // no thread owns the lock.
1529  lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks.
1530  lck->lk.initialized = lck;
1531 
1532  KA_TRACE(1000, ("__kmp_init_queuing_lock: lock %p initialized\n", lck));
1533 }
1534 
1535 void __kmp_destroy_queuing_lock(kmp_queuing_lock_t *lck) {
1536  lck->lk.initialized = NULL;
1537  lck->lk.location = NULL;
1538  lck->lk.head_id = 0;
1539  lck->lk.tail_id = 0;
1540  lck->lk.next_ticket = 0;
1541  lck->lk.now_serving = 0;
1542  lck->lk.owner_id = 0;
1543  lck->lk.depth_locked = -1;
1544 }
1545 
1546 static void __kmp_destroy_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
1547  char const *const func = "omp_destroy_lock";
1548  if (lck->lk.initialized != lck) {
1549  KMP_FATAL(LockIsUninitialized, func);
1550  }
1551  if (__kmp_is_queuing_lock_nestable(lck)) {
1552  KMP_FATAL(LockNestableUsedAsSimple, func);
1553  }
1554  if (__kmp_get_queuing_lock_owner(lck) != -1) {
1555  KMP_FATAL(LockStillOwned, func);
1556  }
1557  __kmp_destroy_queuing_lock(lck);
1558 }
1559 
1560 // nested queuing locks
1561 
1562 int __kmp_acquire_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1563  KMP_DEBUG_ASSERT(gtid >= 0);
1564 
1565  if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1566  lck->lk.depth_locked += 1;
1567  return KMP_LOCK_ACQUIRED_NEXT;
1568  } else {
1569  __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid);
1570  ANNOTATE_QUEUING_ACQUIRED(lck);
1571  KMP_MB();
1572  lck->lk.depth_locked = 1;
1573  KMP_MB();
1574  lck->lk.owner_id = gtid + 1;
1575  return KMP_LOCK_ACQUIRED_FIRST;
1576  }
1577 }
1578 
1579 static int
1580 __kmp_acquire_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1581  kmp_int32 gtid) {
1582  char const *const func = "omp_set_nest_lock";
1583  if (lck->lk.initialized != lck) {
1584  KMP_FATAL(LockIsUninitialized, func);
1585  }
1586  if (!__kmp_is_queuing_lock_nestable(lck)) {
1587  KMP_FATAL(LockSimpleUsedAsNestable, func);
1588  }
1589  return __kmp_acquire_nested_queuing_lock(lck, gtid);
1590 }
1591 
1592 int __kmp_test_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1593  int retval;
1594 
1595  KMP_DEBUG_ASSERT(gtid >= 0);
1596 
1597  if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1598  retval = ++lck->lk.depth_locked;
1599  } else if (!__kmp_test_queuing_lock(lck, gtid)) {
1600  retval = 0;
1601  } else {
1602  KMP_MB();
1603  retval = lck->lk.depth_locked = 1;
1604  KMP_MB();
1605  lck->lk.owner_id = gtid + 1;
1606  }
1607  return retval;
1608 }
1609 
1610 static int __kmp_test_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1611  kmp_int32 gtid) {
1612  char const *const func = "omp_test_nest_lock";
1613  if (lck->lk.initialized != lck) {
1614  KMP_FATAL(LockIsUninitialized, func);
1615  }
1616  if (!__kmp_is_queuing_lock_nestable(lck)) {
1617  KMP_FATAL(LockSimpleUsedAsNestable, func);
1618  }
1619  return __kmp_test_nested_queuing_lock(lck, gtid);
1620 }
1621 
1622 int __kmp_release_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1623  KMP_DEBUG_ASSERT(gtid >= 0);
1624 
1625  KMP_MB();
1626  if (--(lck->lk.depth_locked) == 0) {
1627  KMP_MB();
1628  lck->lk.owner_id = 0;
1629  __kmp_release_queuing_lock(lck, gtid);
1630  return KMP_LOCK_RELEASED;
1631  }
1632  return KMP_LOCK_STILL_HELD;
1633 }
1634 
1635 static int
1636 __kmp_release_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1637  kmp_int32 gtid) {
1638  char const *const func = "omp_unset_nest_lock";
1639  KMP_MB(); /* in case another processor initialized lock */
1640  if (lck->lk.initialized != lck) {
1641  KMP_FATAL(LockIsUninitialized, func);
1642  }
1643  if (!__kmp_is_queuing_lock_nestable(lck)) {
1644  KMP_FATAL(LockSimpleUsedAsNestable, func);
1645  }
1646  if (__kmp_get_queuing_lock_owner(lck) == -1) {
1647  KMP_FATAL(LockUnsettingFree, func);
1648  }
1649  if (__kmp_get_queuing_lock_owner(lck) != gtid) {
1650  KMP_FATAL(LockUnsettingSetByAnother, func);
1651  }
1652  return __kmp_release_nested_queuing_lock(lck, gtid);
1653 }
1654 
1655 void __kmp_init_nested_queuing_lock(kmp_queuing_lock_t *lck) {
1656  __kmp_init_queuing_lock(lck);
1657  lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
1658 }
1659 
1660 void __kmp_destroy_nested_queuing_lock(kmp_queuing_lock_t *lck) {
1661  __kmp_destroy_queuing_lock(lck);
1662  lck->lk.depth_locked = 0;
1663 }
1664 
1665 static void
1666 __kmp_destroy_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
1667  char const *const func = "omp_destroy_nest_lock";
1668  if (lck->lk.initialized != lck) {
1669  KMP_FATAL(LockIsUninitialized, func);
1670  }
1671  if (!__kmp_is_queuing_lock_nestable(lck)) {
1672  KMP_FATAL(LockSimpleUsedAsNestable, func);
1673  }
1674  if (__kmp_get_queuing_lock_owner(lck) != -1) {
1675  KMP_FATAL(LockStillOwned, func);
1676  }
1677  __kmp_destroy_nested_queuing_lock(lck);
1678 }
1679 
1680 // access functions to fields which don't exist for all lock kinds.
1681 
1682 static const ident_t *__kmp_get_queuing_lock_location(kmp_queuing_lock_t *lck) {
1683  return lck->lk.location;
1684 }
1685 
1686 static void __kmp_set_queuing_lock_location(kmp_queuing_lock_t *lck,
1687  const ident_t *loc) {
1688  lck->lk.location = loc;
1689 }
1690 
1691 static kmp_lock_flags_t __kmp_get_queuing_lock_flags(kmp_queuing_lock_t *lck) {
1692  return lck->lk.flags;
1693 }
1694 
1695 static void __kmp_set_queuing_lock_flags(kmp_queuing_lock_t *lck,
1696  kmp_lock_flags_t flags) {
1697  lck->lk.flags = flags;
1698 }
1699 
1700 #if KMP_USE_ADAPTIVE_LOCKS
1701 
1702 /* RTM Adaptive locks */
1703 
1704 #if KMP_HAVE_RTM_INTRINSICS
1705 #include <immintrin.h>
1706 #define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT)
1707 
1708 #else
1709 
1710 // Values from the status register after failed speculation.
1711 #define _XBEGIN_STARTED (~0u)
1712 #define _XABORT_EXPLICIT (1 << 0)
1713 #define _XABORT_RETRY (1 << 1)
1714 #define _XABORT_CONFLICT (1 << 2)
1715 #define _XABORT_CAPACITY (1 << 3)
1716 #define _XABORT_DEBUG (1 << 4)
1717 #define _XABORT_NESTED (1 << 5)
1718 #define _XABORT_CODE(x) ((unsigned char)(((x) >> 24) & 0xFF))
1719 
1720 // Aborts for which it's worth trying again immediately
1721 #define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT)
1722 
1723 #define STRINGIZE_INTERNAL(arg) #arg
1724 #define STRINGIZE(arg) STRINGIZE_INTERNAL(arg)
1725 
1726 // Access to RTM instructions
1727 /*A version of XBegin which returns -1 on speculation, and the value of EAX on
1728  an abort. This is the same definition as the compiler intrinsic that will be
1729  supported at some point. */
1730 static __inline int _xbegin() {
1731  int res = -1;
1732 
1733 #if KMP_OS_WINDOWS
1734 #if KMP_ARCH_X86_64
1735  _asm {
1736  _emit 0xC7
1737  _emit 0xF8
1738  _emit 2
1739  _emit 0
1740  _emit 0
1741  _emit 0
1742  jmp L2
1743  mov res, eax
1744  L2:
1745  }
1746 #else /* IA32 */
1747  _asm {
1748  _emit 0xC7
1749  _emit 0xF8
1750  _emit 2
1751  _emit 0
1752  _emit 0
1753  _emit 0
1754  jmp L2
1755  mov res, eax
1756  L2:
1757  }
1758 #endif // KMP_ARCH_X86_64
1759 #else
1760  /* Note that %eax must be noted as killed (clobbered), because the XSR is
1761  returned in %eax(%rax) on abort. Other register values are restored, so
1762  don't need to be killed.
1763 
1764  We must also mark 'res' as an input and an output, since otherwise
1765  'res=-1' may be dropped as being dead, whereas we do need the assignment on
1766  the successful (i.e., non-abort) path. */
1767  __asm__ volatile("1: .byte 0xC7; .byte 0xF8;\n"
1768  " .long 1f-1b-6\n"
1769  " jmp 2f\n"
1770  "1: movl %%eax,%0\n"
1771  "2:"
1772  : "+r"(res)::"memory", "%eax");
1773 #endif // KMP_OS_WINDOWS
1774  return res;
1775 }
1776 
1777 /* Transaction end */
1778 static __inline void _xend() {
1779 #if KMP_OS_WINDOWS
1780  __asm {
1781  _emit 0x0f
1782  _emit 0x01
1783  _emit 0xd5
1784  }
1785 #else
1786  __asm__ volatile(".byte 0x0f; .byte 0x01; .byte 0xd5" ::: "memory");
1787 #endif
1788 }
1789 
1790 /* This is a macro, the argument must be a single byte constant which can be
1791  evaluated by the inline assembler, since it is emitted as a byte into the
1792  assembly code. */
1793 // clang-format off
1794 #if KMP_OS_WINDOWS
1795 #define _xabort(ARG) _asm _emit 0xc6 _asm _emit 0xf8 _asm _emit ARG
1796 #else
1797 #define _xabort(ARG) \
1798  __asm__ volatile(".byte 0xC6; .byte 0xF8; .byte " STRINGIZE(ARG):::"memory");
1799 #endif
1800 // clang-format on
1801 #endif // KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300
1802 
1803 // Statistics is collected for testing purpose
1804 #if KMP_DEBUG_ADAPTIVE_LOCKS
1805 
1806 // We accumulate speculative lock statistics when the lock is destroyed. We
1807 // keep locks that haven't been destroyed in the liveLocks list so that we can
1808 // grab their statistics too.
1809 static kmp_adaptive_lock_statistics_t destroyedStats;
1810 
1811 // To hold the list of live locks.
1812 static kmp_adaptive_lock_info_t liveLocks;
1813 
1814 // A lock so we can safely update the list of locks.
1815 static kmp_bootstrap_lock_t chain_lock =
1816  KMP_BOOTSTRAP_LOCK_INITIALIZER(chain_lock);
1817 
1818 // Initialize the list of stats.
1819 void __kmp_init_speculative_stats() {
1820  kmp_adaptive_lock_info_t *lck = &liveLocks;
1821 
1822  memset(CCAST(kmp_adaptive_lock_statistics_t *, &(lck->stats)), 0,
1823  sizeof(lck->stats));
1824  lck->stats.next = lck;
1825  lck->stats.prev = lck;
1826 
1827  KMP_ASSERT(lck->stats.next->stats.prev == lck);
1828  KMP_ASSERT(lck->stats.prev->stats.next == lck);
1829 
1830  __kmp_init_bootstrap_lock(&chain_lock);
1831 }
1832 
1833 // Insert the lock into the circular list
1834 static void __kmp_remember_lock(kmp_adaptive_lock_info_t *lck) {
1835  __kmp_acquire_bootstrap_lock(&chain_lock);
1836 
1837  lck->stats.next = liveLocks.stats.next;
1838  lck->stats.prev = &liveLocks;
1839 
1840  liveLocks.stats.next = lck;
1841  lck->stats.next->stats.prev = lck;
1842 
1843  KMP_ASSERT(lck->stats.next->stats.prev == lck);
1844  KMP_ASSERT(lck->stats.prev->stats.next == lck);
1845 
1846  __kmp_release_bootstrap_lock(&chain_lock);
1847 }
1848 
1849 static void __kmp_forget_lock(kmp_adaptive_lock_info_t *lck) {
1850  KMP_ASSERT(lck->stats.next->stats.prev == lck);
1851  KMP_ASSERT(lck->stats.prev->stats.next == lck);
1852 
1853  kmp_adaptive_lock_info_t *n = lck->stats.next;
1854  kmp_adaptive_lock_info_t *p = lck->stats.prev;
1855 
1856  n->stats.prev = p;
1857  p->stats.next = n;
1858 }
1859 
1860 static void __kmp_zero_speculative_stats(kmp_adaptive_lock_info_t *lck) {
1861  memset(CCAST(kmp_adaptive_lock_statistics_t *, &lck->stats), 0,
1862  sizeof(lck->stats));
1863  __kmp_remember_lock(lck);
1864 }
1865 
1866 static void __kmp_add_stats(kmp_adaptive_lock_statistics_t *t,
1867  kmp_adaptive_lock_info_t *lck) {
1868  kmp_adaptive_lock_statistics_t volatile *s = &lck->stats;
1869 
1870  t->nonSpeculativeAcquireAttempts += lck->acquire_attempts;
1871  t->successfulSpeculations += s->successfulSpeculations;
1872  t->hardFailedSpeculations += s->hardFailedSpeculations;
1873  t->softFailedSpeculations += s->softFailedSpeculations;
1874  t->nonSpeculativeAcquires += s->nonSpeculativeAcquires;
1875  t->lemmingYields += s->lemmingYields;
1876 }
1877 
1878 static void __kmp_accumulate_speculative_stats(kmp_adaptive_lock_info_t *lck) {
1879  __kmp_acquire_bootstrap_lock(&chain_lock);
1880 
1881  __kmp_add_stats(&destroyedStats, lck);
1882  __kmp_forget_lock(lck);
1883 
1884  __kmp_release_bootstrap_lock(&chain_lock);
1885 }
1886 
1887 static float percent(kmp_uint32 count, kmp_uint32 total) {
1888  return (total == 0) ? 0.0 : (100.0 * count) / total;
1889 }
1890 
1891 void __kmp_print_speculative_stats() {
1892  kmp_adaptive_lock_statistics_t total = destroyedStats;
1893  kmp_adaptive_lock_info_t *lck;
1894 
1895  for (lck = liveLocks.stats.next; lck != &liveLocks; lck = lck->stats.next) {
1896  __kmp_add_stats(&total, lck);
1897  }
1898  kmp_adaptive_lock_statistics_t *t = &total;
1899  kmp_uint32 totalSections =
1900  t->nonSpeculativeAcquires + t->successfulSpeculations;
1901  kmp_uint32 totalSpeculations = t->successfulSpeculations +
1902  t->hardFailedSpeculations +
1903  t->softFailedSpeculations;
1904  if (totalSections <= 0)
1905  return;
1906 
1907  kmp_safe_raii_file_t statsFile;
1908  if (strcmp(__kmp_speculative_statsfile, "-") == 0) {
1909  statsFile.set_stdout();
1910  } else {
1911  size_t buffLen = KMP_STRLEN(__kmp_speculative_statsfile) + 20;
1912  char buffer[buffLen];
1913  KMP_SNPRINTF(&buffer[0], buffLen, __kmp_speculative_statsfile,
1914  (kmp_int32)getpid());
1915  statsFile.open(buffer, "w");
1916  }
1917 
1918  fprintf(statsFile, "Speculative lock statistics (all approximate!)\n");
1919  fprintf(statsFile,
1920  " Lock parameters: \n"
1921  " max_soft_retries : %10d\n"
1922  " max_badness : %10d\n",
1923  __kmp_adaptive_backoff_params.max_soft_retries,
1924  __kmp_adaptive_backoff_params.max_badness);
1925  fprintf(statsFile, " Non-speculative acquire attempts : %10d\n",
1926  t->nonSpeculativeAcquireAttempts);
1927  fprintf(statsFile, " Total critical sections : %10d\n",
1928  totalSections);
1929  fprintf(statsFile, " Successful speculations : %10d (%5.1f%%)\n",
1930  t->successfulSpeculations,
1931  percent(t->successfulSpeculations, totalSections));
1932  fprintf(statsFile, " Non-speculative acquires : %10d (%5.1f%%)\n",
1933  t->nonSpeculativeAcquires,
1934  percent(t->nonSpeculativeAcquires, totalSections));
1935  fprintf(statsFile, " Lemming yields : %10d\n\n",
1936  t->lemmingYields);
1937 
1938  fprintf(statsFile, " Speculative acquire attempts : %10d\n",
1939  totalSpeculations);
1940  fprintf(statsFile, " Successes : %10d (%5.1f%%)\n",
1941  t->successfulSpeculations,
1942  percent(t->successfulSpeculations, totalSpeculations));
1943  fprintf(statsFile, " Soft failures : %10d (%5.1f%%)\n",
1944  t->softFailedSpeculations,
1945  percent(t->softFailedSpeculations, totalSpeculations));
1946  fprintf(statsFile, " Hard failures : %10d (%5.1f%%)\n",
1947  t->hardFailedSpeculations,
1948  percent(t->hardFailedSpeculations, totalSpeculations));
1949 }
1950 
1951 #define KMP_INC_STAT(lck, stat) (lck->lk.adaptive.stats.stat++)
1952 #else
1953 #define KMP_INC_STAT(lck, stat)
1954 
1955 #endif // KMP_DEBUG_ADAPTIVE_LOCKS
1956 
1957 static inline bool __kmp_is_unlocked_queuing_lock(kmp_queuing_lock_t *lck) {
1958  // It is enough to check that the head_id is zero.
1959  // We don't also need to check the tail.
1960  bool res = lck->lk.head_id == 0;
1961 
1962 // We need a fence here, since we must ensure that no memory operations
1963 // from later in this thread float above that read.
1964 #if KMP_COMPILER_ICC
1965  _mm_mfence();
1966 #else
1967  __sync_synchronize();
1968 #endif
1969 
1970  return res;
1971 }
1972 
1973 // Functions for manipulating the badness
1974 static __inline void
1975 __kmp_update_badness_after_success(kmp_adaptive_lock_t *lck) {
1976  // Reset the badness to zero so we eagerly try to speculate again
1977  lck->lk.adaptive.badness = 0;
1978  KMP_INC_STAT(lck, successfulSpeculations);
1979 }
1980 
1981 // Create a bit mask with one more set bit.
1982 static __inline void __kmp_step_badness(kmp_adaptive_lock_t *lck) {
1983  kmp_uint32 newBadness = (lck->lk.adaptive.badness << 1) | 1;
1984  if (newBadness > lck->lk.adaptive.max_badness) {
1985  return;
1986  } else {
1987  lck->lk.adaptive.badness = newBadness;
1988  }
1989 }
1990 
1991 // Check whether speculation should be attempted.
1992 KMP_ATTRIBUTE_TARGET_RTM
1993 static __inline int __kmp_should_speculate(kmp_adaptive_lock_t *lck,
1994  kmp_int32 gtid) {
1995  kmp_uint32 badness = lck->lk.adaptive.badness;
1996  kmp_uint32 attempts = lck->lk.adaptive.acquire_attempts;
1997  int res = (attempts & badness) == 0;
1998  return res;
1999 }
2000 
2001 // Attempt to acquire only the speculative lock.
2002 // Does not back off to the non-speculative lock.
2003 KMP_ATTRIBUTE_TARGET_RTM
2004 static int __kmp_test_adaptive_lock_only(kmp_adaptive_lock_t *lck,
2005  kmp_int32 gtid) {
2006  int retries = lck->lk.adaptive.max_soft_retries;
2007 
2008  // We don't explicitly count the start of speculation, rather we record the
2009  // results (success, hard fail, soft fail). The sum of all of those is the
2010  // total number of times we started speculation since all speculations must
2011  // end one of those ways.
2012  do {
2013  kmp_uint32 status = _xbegin();
2014  // Switch this in to disable actual speculation but exercise at least some
2015  // of the rest of the code. Useful for debugging...
2016  // kmp_uint32 status = _XABORT_NESTED;
2017 
2018  if (status == _XBEGIN_STARTED) {
2019  /* We have successfully started speculation. Check that no-one acquired
2020  the lock for real between when we last looked and now. This also gets
2021  the lock cache line into our read-set, which we need so that we'll
2022  abort if anyone later claims it for real. */
2023  if (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) {
2024  // Lock is now visibly acquired, so someone beat us to it. Abort the
2025  // transaction so we'll restart from _xbegin with the failure status.
2026  _xabort(0x01);
2027  KMP_ASSERT2(0, "should not get here");
2028  }
2029  return 1; // Lock has been acquired (speculatively)
2030  } else {
2031  // We have aborted, update the statistics
2032  if (status & SOFT_ABORT_MASK) {
2033  KMP_INC_STAT(lck, softFailedSpeculations);
2034  // and loop round to retry.
2035  } else {
2036  KMP_INC_STAT(lck, hardFailedSpeculations);
2037  // Give up if we had a hard failure.
2038  break;
2039  }
2040  }
2041  } while (retries--); // Loop while we have retries, and didn't fail hard.
2042 
2043  // Either we had a hard failure or we didn't succeed softly after
2044  // the full set of attempts, so back off the badness.
2045  __kmp_step_badness(lck);
2046  return 0;
2047 }
2048 
2049 // Attempt to acquire the speculative lock, or back off to the non-speculative
2050 // one if the speculative lock cannot be acquired.
2051 // We can succeed speculatively, non-speculatively, or fail.
2052 static int __kmp_test_adaptive_lock(kmp_adaptive_lock_t *lck, kmp_int32 gtid) {
2053  // First try to acquire the lock speculatively
2054  if (__kmp_should_speculate(lck, gtid) &&
2055  __kmp_test_adaptive_lock_only(lck, gtid))
2056  return 1;
2057 
2058  // Speculative acquisition failed, so try to acquire it non-speculatively.
2059  // Count the non-speculative acquire attempt
2060  lck->lk.adaptive.acquire_attempts++;
2061 
2062  // Use base, non-speculative lock.
2063  if (__kmp_test_queuing_lock(GET_QLK_PTR(lck), gtid)) {
2064  KMP_INC_STAT(lck, nonSpeculativeAcquires);
2065  return 1; // Lock is acquired (non-speculatively)
2066  } else {
2067  return 0; // Failed to acquire the lock, it's already visibly locked.
2068  }
2069 }
2070 
2071 static int __kmp_test_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck,
2072  kmp_int32 gtid) {
2073  char const *const func = "omp_test_lock";
2074  if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2075  KMP_FATAL(LockIsUninitialized, func);
2076  }
2077 
2078  int retval = __kmp_test_adaptive_lock(lck, gtid);
2079 
2080  if (retval) {
2081  lck->lk.qlk.owner_id = gtid + 1;
2082  }
2083  return retval;
2084 }
2085 
2086 // Block until we can acquire a speculative, adaptive lock. We check whether we
2087 // should be trying to speculate. If we should be, we check the real lock to see
2088 // if it is free, and, if not, pause without attempting to acquire it until it
2089 // is. Then we try the speculative acquire. This means that although we suffer
2090 // from lemmings a little (because all we can't acquire the lock speculatively
2091 // until the queue of threads waiting has cleared), we don't get into a state
2092 // where we can never acquire the lock speculatively (because we force the queue
2093 // to clear by preventing new arrivals from entering the queue). This does mean
2094 // that when we're trying to break lemmings, the lock is no longer fair. However
2095 // OpenMP makes no guarantee that its locks are fair, so this isn't a real
2096 // problem.
2097 static void __kmp_acquire_adaptive_lock(kmp_adaptive_lock_t *lck,
2098  kmp_int32 gtid) {
2099  if (__kmp_should_speculate(lck, gtid)) {
2100  if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) {
2101  if (__kmp_test_adaptive_lock_only(lck, gtid))
2102  return;
2103  // We tried speculation and failed, so give up.
2104  } else {
2105  // We can't try speculation until the lock is free, so we pause here
2106  // (without suspending on the queueing lock, to allow it to drain, then
2107  // try again. All other threads will also see the same result for
2108  // shouldSpeculate, so will be doing the same if they try to claim the
2109  // lock from now on.
2110  while (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) {
2111  KMP_INC_STAT(lck, lemmingYields);
2112  KMP_YIELD(TRUE);
2113  }
2114 
2115  if (__kmp_test_adaptive_lock_only(lck, gtid))
2116  return;
2117  }
2118  }
2119 
2120  // Speculative acquisition failed, so acquire it non-speculatively.
2121  // Count the non-speculative acquire attempt
2122  lck->lk.adaptive.acquire_attempts++;
2123 
2124  __kmp_acquire_queuing_lock_timed_template<FALSE>(GET_QLK_PTR(lck), gtid);
2125  // We have acquired the base lock, so count that.
2126  KMP_INC_STAT(lck, nonSpeculativeAcquires);
2127  ANNOTATE_QUEUING_ACQUIRED(lck);
2128 }
2129 
2130 static void __kmp_acquire_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck,
2131  kmp_int32 gtid) {
2132  char const *const func = "omp_set_lock";
2133  if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2134  KMP_FATAL(LockIsUninitialized, func);
2135  }
2136  if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == gtid) {
2137  KMP_FATAL(LockIsAlreadyOwned, func);
2138  }
2139 
2140  __kmp_acquire_adaptive_lock(lck, gtid);
2141 
2142  lck->lk.qlk.owner_id = gtid + 1;
2143 }
2144 
2145 KMP_ATTRIBUTE_TARGET_RTM
2146 static int __kmp_release_adaptive_lock(kmp_adaptive_lock_t *lck,
2147  kmp_int32 gtid) {
2148  if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(
2149  lck))) { // If the lock doesn't look claimed we must be speculating.
2150  // (Or the user's code is buggy and they're releasing without locking;
2151  // if we had XTEST we'd be able to check that case...)
2152  _xend(); // Exit speculation
2153  __kmp_update_badness_after_success(lck);
2154  } else { // Since the lock *is* visibly locked we're not speculating,
2155  // so should use the underlying lock's release scheme.
2156  __kmp_release_queuing_lock(GET_QLK_PTR(lck), gtid);
2157  }
2158  return KMP_LOCK_RELEASED;
2159 }
2160 
2161 static int __kmp_release_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck,
2162  kmp_int32 gtid) {
2163  char const *const func = "omp_unset_lock";
2164  KMP_MB(); /* in case another processor initialized lock */
2165  if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2166  KMP_FATAL(LockIsUninitialized, func);
2167  }
2168  if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == -1) {
2169  KMP_FATAL(LockUnsettingFree, func);
2170  }
2171  if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != gtid) {
2172  KMP_FATAL(LockUnsettingSetByAnother, func);
2173  }
2174  lck->lk.qlk.owner_id = 0;
2175  __kmp_release_adaptive_lock(lck, gtid);
2176  return KMP_LOCK_RELEASED;
2177 }
2178 
2179 static void __kmp_init_adaptive_lock(kmp_adaptive_lock_t *lck) {
2180  __kmp_init_queuing_lock(GET_QLK_PTR(lck));
2181  lck->lk.adaptive.badness = 0;
2182  lck->lk.adaptive.acquire_attempts = 0; // nonSpeculativeAcquireAttempts = 0;
2183  lck->lk.adaptive.max_soft_retries =
2184  __kmp_adaptive_backoff_params.max_soft_retries;
2185  lck->lk.adaptive.max_badness = __kmp_adaptive_backoff_params.max_badness;
2186 #if KMP_DEBUG_ADAPTIVE_LOCKS
2187  __kmp_zero_speculative_stats(&lck->lk.adaptive);
2188 #endif
2189  KA_TRACE(1000, ("__kmp_init_adaptive_lock: lock %p initialized\n", lck));
2190 }
2191 
2192 static void __kmp_destroy_adaptive_lock(kmp_adaptive_lock_t *lck) {
2193 #if KMP_DEBUG_ADAPTIVE_LOCKS
2194  __kmp_accumulate_speculative_stats(&lck->lk.adaptive);
2195 #endif
2196  __kmp_destroy_queuing_lock(GET_QLK_PTR(lck));
2197  // Nothing needed for the speculative part.
2198 }
2199 
2200 static void __kmp_destroy_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck) {
2201  char const *const func = "omp_destroy_lock";
2202  if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2203  KMP_FATAL(LockIsUninitialized, func);
2204  }
2205  if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != -1) {
2206  KMP_FATAL(LockStillOwned, func);
2207  }
2208  __kmp_destroy_adaptive_lock(lck);
2209 }
2210 
2211 #endif // KMP_USE_ADAPTIVE_LOCKS
2212 
2213 /* ------------------------------------------------------------------------ */
2214 /* DRDPA ticket locks */
2215 /* "DRDPA" means Dynamically Reconfigurable Distributed Polling Area */
2216 
2217 static kmp_int32 __kmp_get_drdpa_lock_owner(kmp_drdpa_lock_t *lck) {
2218  return lck->lk.owner_id - 1;
2219 }
2220 
2221 static inline bool __kmp_is_drdpa_lock_nestable(kmp_drdpa_lock_t *lck) {
2222  return lck->lk.depth_locked != -1;
2223 }
2224 
2225 __forceinline static int
2226 __kmp_acquire_drdpa_lock_timed_template(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2227  kmp_uint64 ticket = KMP_ATOMIC_INC(&lck->lk.next_ticket);
2228  kmp_uint64 mask = lck->lk.mask; // atomic load
2229  std::atomic<kmp_uint64> *polls = lck->lk.polls;
2230 
2231 #ifdef USE_LOCK_PROFILE
2232  if (polls[ticket & mask] != ticket)
2233  __kmp_printf("LOCK CONTENTION: %p\n", lck);
2234 /* else __kmp_printf( "." );*/
2235 #endif /* USE_LOCK_PROFILE */
2236 
2237  // Now spin-wait, but reload the polls pointer and mask, in case the
2238  // polling area has been reconfigured. Unless it is reconfigured, the
2239  // reloads stay in L1 cache and are cheap.
2240  //
2241  // Keep this code in sync with KMP_WAIT, in kmp_dispatch.cpp !!!
2242  // The current implementation of KMP_WAIT doesn't allow for mask
2243  // and poll to be re-read every spin iteration.
2244  kmp_uint32 spins;
2245  KMP_FSYNC_PREPARE(lck);
2246  KMP_INIT_YIELD(spins);
2247  while (polls[ticket & mask] < ticket) { // atomic load
2248  KMP_YIELD_OVERSUB_ELSE_SPIN(spins);
2249  // Re-read the mask and the poll pointer from the lock structure.
2250  //
2251  // Make certain that "mask" is read before "polls" !!!
2252  //
2253  // If another thread picks reconfigures the polling area and updates their
2254  // values, and we get the new value of mask and the old polls pointer, we
2255  // could access memory beyond the end of the old polling area.
2256  mask = lck->lk.mask; // atomic load
2257  polls = lck->lk.polls; // atomic load
2258  }
2259 
2260  // Critical section starts here
2261  KMP_FSYNC_ACQUIRED(lck);
2262  KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld acquired lock %p\n",
2263  ticket, lck));
2264  lck->lk.now_serving = ticket; // non-volatile store
2265 
2266  // Deallocate a garbage polling area if we know that we are the last
2267  // thread that could possibly access it.
2268  //
2269  // The >= check is in case __kmp_test_drdpa_lock() allocated the cleanup
2270  // ticket.
2271  if ((lck->lk.old_polls != NULL) && (ticket >= lck->lk.cleanup_ticket)) {
2272  __kmp_free(lck->lk.old_polls);
2273  lck->lk.old_polls = NULL;
2274  lck->lk.cleanup_ticket = 0;
2275  }
2276 
2277  // Check to see if we should reconfigure the polling area.
2278  // If there is still a garbage polling area to be deallocated from a
2279  // previous reconfiguration, let a later thread reconfigure it.
2280  if (lck->lk.old_polls == NULL) {
2281  bool reconfigure = false;
2282  std::atomic<kmp_uint64> *old_polls = polls;
2283  kmp_uint32 num_polls = TCR_4(lck->lk.num_polls);
2284 
2285  if (TCR_4(__kmp_nth) >
2286  (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) {
2287  // We are in oversubscription mode. Contract the polling area
2288  // down to a single location, if that hasn't been done already.
2289  if (num_polls > 1) {
2290  reconfigure = true;
2291  num_polls = TCR_4(lck->lk.num_polls);
2292  mask = 0;
2293  num_polls = 1;
2294  polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls *
2295  sizeof(*polls));
2296  polls[0] = ticket;
2297  }
2298  } else {
2299  // We are in under/fully subscribed mode. Check the number of
2300  // threads waiting on the lock. The size of the polling area
2301  // should be at least the number of threads waiting.
2302  kmp_uint64 num_waiting = TCR_8(lck->lk.next_ticket) - ticket - 1;
2303  if (num_waiting > num_polls) {
2304  kmp_uint32 old_num_polls = num_polls;
2305  reconfigure = true;
2306  do {
2307  mask = (mask << 1) | 1;
2308  num_polls *= 2;
2309  } while (num_polls <= num_waiting);
2310 
2311  // Allocate the new polling area, and copy the relevant portion
2312  // of the old polling area to the new area. __kmp_allocate()
2313  // zeroes the memory it allocates, and most of the old area is
2314  // just zero padding, so we only copy the release counters.
2315  polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls *
2316  sizeof(*polls));
2317  kmp_uint32 i;
2318  for (i = 0; i < old_num_polls; i++) {
2319  polls[i].store(old_polls[i]);
2320  }
2321  }
2322  }
2323 
2324  if (reconfigure) {
2325  // Now write the updated fields back to the lock structure.
2326  //
2327  // Make certain that "polls" is written before "mask" !!!
2328  //
2329  // If another thread picks up the new value of mask and the old polls
2330  // pointer , it could access memory beyond the end of the old polling
2331  // area.
2332  //
2333  // On x86, we need memory fences.
2334  KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld reconfiguring "
2335  "lock %p to %d polls\n",
2336  ticket, lck, num_polls));
2337 
2338  lck->lk.old_polls = old_polls;
2339  lck->lk.polls = polls; // atomic store
2340 
2341  KMP_MB();
2342 
2343  lck->lk.num_polls = num_polls;
2344  lck->lk.mask = mask; // atomic store
2345 
2346  KMP_MB();
2347 
2348  // Only after the new polling area and mask have been flushed
2349  // to main memory can we update the cleanup ticket field.
2350  //
2351  // volatile load / non-volatile store
2352  lck->lk.cleanup_ticket = lck->lk.next_ticket;
2353  }
2354  }
2355  return KMP_LOCK_ACQUIRED_FIRST;
2356 }
2357 
2358 int __kmp_acquire_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2359  int retval = __kmp_acquire_drdpa_lock_timed_template(lck, gtid);
2360  ANNOTATE_DRDPA_ACQUIRED(lck);
2361  return retval;
2362 }
2363 
2364 static int __kmp_acquire_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2365  kmp_int32 gtid) {
2366  char const *const func = "omp_set_lock";
2367  if (lck->lk.initialized != lck) {
2368  KMP_FATAL(LockIsUninitialized, func);
2369  }
2370  if (__kmp_is_drdpa_lock_nestable(lck)) {
2371  KMP_FATAL(LockNestableUsedAsSimple, func);
2372  }
2373  if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) == gtid)) {
2374  KMP_FATAL(LockIsAlreadyOwned, func);
2375  }
2376 
2377  __kmp_acquire_drdpa_lock(lck, gtid);
2378 
2379  lck->lk.owner_id = gtid + 1;
2380  return KMP_LOCK_ACQUIRED_FIRST;
2381 }
2382 
2383 int __kmp_test_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2384  // First get a ticket, then read the polls pointer and the mask.
2385  // The polls pointer must be read before the mask!!! (See above)
2386  kmp_uint64 ticket = lck->lk.next_ticket; // atomic load
2387  std::atomic<kmp_uint64> *polls = lck->lk.polls;
2388  kmp_uint64 mask = lck->lk.mask; // atomic load
2389  if (polls[ticket & mask] == ticket) {
2390  kmp_uint64 next_ticket = ticket + 1;
2391  if (__kmp_atomic_compare_store_acq(&lck->lk.next_ticket, ticket,
2392  next_ticket)) {
2393  KMP_FSYNC_ACQUIRED(lck);
2394  KA_TRACE(1000, ("__kmp_test_drdpa_lock: ticket #%lld acquired lock %p\n",
2395  ticket, lck));
2396  lck->lk.now_serving = ticket; // non-volatile store
2397 
2398  // Since no threads are waiting, there is no possibility that we would
2399  // want to reconfigure the polling area. We might have the cleanup ticket
2400  // value (which says that it is now safe to deallocate old_polls), but
2401  // we'll let a later thread which calls __kmp_acquire_lock do that - this
2402  // routine isn't supposed to block, and we would risk blocks if we called
2403  // __kmp_free() to do the deallocation.
2404  return TRUE;
2405  }
2406  }
2407  return FALSE;
2408 }
2409 
2410 static int __kmp_test_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2411  kmp_int32 gtid) {
2412  char const *const func = "omp_test_lock";
2413  if (lck->lk.initialized != lck) {
2414  KMP_FATAL(LockIsUninitialized, func);
2415  }
2416  if (__kmp_is_drdpa_lock_nestable(lck)) {
2417  KMP_FATAL(LockNestableUsedAsSimple, func);
2418  }
2419 
2420  int retval = __kmp_test_drdpa_lock(lck, gtid);
2421 
2422  if (retval) {
2423  lck->lk.owner_id = gtid + 1;
2424  }
2425  return retval;
2426 }
2427 
2428 int __kmp_release_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2429  // Read the ticket value from the lock data struct, then the polls pointer and
2430  // the mask. The polls pointer must be read before the mask!!! (See above)
2431  kmp_uint64 ticket = lck->lk.now_serving + 1; // non-atomic load
2432  std::atomic<kmp_uint64> *polls = lck->lk.polls; // atomic load
2433  kmp_uint64 mask = lck->lk.mask; // atomic load
2434  KA_TRACE(1000, ("__kmp_release_drdpa_lock: ticket #%lld released lock %p\n",
2435  ticket - 1, lck));
2436  KMP_FSYNC_RELEASING(lck);
2437  ANNOTATE_DRDPA_RELEASED(lck);
2438  polls[ticket & mask] = ticket; // atomic store
2439  return KMP_LOCK_RELEASED;
2440 }
2441 
2442 static int __kmp_release_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2443  kmp_int32 gtid) {
2444  char const *const func = "omp_unset_lock";
2445  KMP_MB(); /* in case another processor initialized lock */
2446  if (lck->lk.initialized != lck) {
2447  KMP_FATAL(LockIsUninitialized, func);
2448  }
2449  if (__kmp_is_drdpa_lock_nestable(lck)) {
2450  KMP_FATAL(LockNestableUsedAsSimple, func);
2451  }
2452  if (__kmp_get_drdpa_lock_owner(lck) == -1) {
2453  KMP_FATAL(LockUnsettingFree, func);
2454  }
2455  if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) >= 0) &&
2456  (__kmp_get_drdpa_lock_owner(lck) != gtid)) {
2457  KMP_FATAL(LockUnsettingSetByAnother, func);
2458  }
2459  lck->lk.owner_id = 0;
2460  return __kmp_release_drdpa_lock(lck, gtid);
2461 }
2462 
2463 void __kmp_init_drdpa_lock(kmp_drdpa_lock_t *lck) {
2464  lck->lk.location = NULL;
2465  lck->lk.mask = 0;
2466  lck->lk.num_polls = 1;
2467  lck->lk.polls = (std::atomic<kmp_uint64> *)__kmp_allocate(
2468  lck->lk.num_polls * sizeof(*(lck->lk.polls)));
2469  lck->lk.cleanup_ticket = 0;
2470  lck->lk.old_polls = NULL;
2471  lck->lk.next_ticket = 0;
2472  lck->lk.now_serving = 0;
2473  lck->lk.owner_id = 0; // no thread owns the lock.
2474  lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks.
2475  lck->lk.initialized = lck;
2476 
2477  KA_TRACE(1000, ("__kmp_init_drdpa_lock: lock %p initialized\n", lck));
2478 }
2479 
2480 void __kmp_destroy_drdpa_lock(kmp_drdpa_lock_t *lck) {
2481  lck->lk.initialized = NULL;
2482  lck->lk.location = NULL;
2483  if (lck->lk.polls.load() != NULL) {
2484  __kmp_free(lck->lk.polls.load());
2485  lck->lk.polls = NULL;
2486  }
2487  if (lck->lk.old_polls != NULL) {
2488  __kmp_free(lck->lk.old_polls);
2489  lck->lk.old_polls = NULL;
2490  }
2491  lck->lk.mask = 0;
2492  lck->lk.num_polls = 0;
2493  lck->lk.cleanup_ticket = 0;
2494  lck->lk.next_ticket = 0;
2495  lck->lk.now_serving = 0;
2496  lck->lk.owner_id = 0;
2497  lck->lk.depth_locked = -1;
2498 }
2499 
2500 static void __kmp_destroy_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) {
2501  char const *const func = "omp_destroy_lock";
2502  if (lck->lk.initialized != lck) {
2503  KMP_FATAL(LockIsUninitialized, func);
2504  }
2505  if (__kmp_is_drdpa_lock_nestable(lck)) {
2506  KMP_FATAL(LockNestableUsedAsSimple, func);
2507  }
2508  if (__kmp_get_drdpa_lock_owner(lck) != -1) {
2509  KMP_FATAL(LockStillOwned, func);
2510  }
2511  __kmp_destroy_drdpa_lock(lck);
2512 }
2513 
2514 // nested drdpa ticket locks
2515 
2516 int __kmp_acquire_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2517  KMP_DEBUG_ASSERT(gtid >= 0);
2518 
2519  if (__kmp_get_drdpa_lock_owner(lck) == gtid) {
2520  lck->lk.depth_locked += 1;
2521  return KMP_LOCK_ACQUIRED_NEXT;
2522  } else {
2523  __kmp_acquire_drdpa_lock_timed_template(lck, gtid);
2524  ANNOTATE_DRDPA_ACQUIRED(lck);
2525  KMP_MB();
2526  lck->lk.depth_locked = 1;
2527  KMP_MB();
2528  lck->lk.owner_id = gtid + 1;
2529  return KMP_LOCK_ACQUIRED_FIRST;
2530  }
2531 }
2532 
2533 static void __kmp_acquire_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2534  kmp_int32 gtid) {
2535  char const *const func = "omp_set_nest_lock";
2536  if (lck->lk.initialized != lck) {
2537  KMP_FATAL(LockIsUninitialized, func);
2538  }
2539  if (!__kmp_is_drdpa_lock_nestable(lck)) {
2540  KMP_FATAL(LockSimpleUsedAsNestable, func);
2541  }
2542  __kmp_acquire_nested_drdpa_lock(lck, gtid);
2543 }
2544 
2545 int __kmp_test_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2546  int retval;
2547 
2548  KMP_DEBUG_ASSERT(gtid >= 0);
2549 
2550  if (__kmp_get_drdpa_lock_owner(lck) == gtid) {
2551  retval = ++lck->lk.depth_locked;
2552  } else if (!__kmp_test_drdpa_lock(lck, gtid)) {
2553  retval = 0;
2554  } else {
2555  KMP_MB();
2556  retval = lck->lk.depth_locked = 1;
2557  KMP_MB();
2558  lck->lk.owner_id = gtid + 1;
2559  }
2560  return retval;
2561 }
2562 
2563 static int __kmp_test_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2564  kmp_int32 gtid) {
2565  char const *const func = "omp_test_nest_lock";
2566  if (lck->lk.initialized != lck) {
2567  KMP_FATAL(LockIsUninitialized, func);
2568  }
2569  if (!__kmp_is_drdpa_lock_nestable(lck)) {
2570  KMP_FATAL(LockSimpleUsedAsNestable, func);
2571  }
2572  return __kmp_test_nested_drdpa_lock(lck, gtid);
2573 }
2574 
2575 int __kmp_release_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2576  KMP_DEBUG_ASSERT(gtid >= 0);
2577 
2578  KMP_MB();
2579  if (--(lck->lk.depth_locked) == 0) {
2580  KMP_MB();
2581  lck->lk.owner_id = 0;
2582  __kmp_release_drdpa_lock(lck, gtid);
2583  return KMP_LOCK_RELEASED;
2584  }
2585  return KMP_LOCK_STILL_HELD;
2586 }
2587 
2588 static int __kmp_release_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2589  kmp_int32 gtid) {
2590  char const *const func = "omp_unset_nest_lock";
2591  KMP_MB(); /* in case another processor initialized lock */
2592  if (lck->lk.initialized != lck) {
2593  KMP_FATAL(LockIsUninitialized, func);
2594  }
2595  if (!__kmp_is_drdpa_lock_nestable(lck)) {
2596  KMP_FATAL(LockSimpleUsedAsNestable, func);
2597  }
2598  if (__kmp_get_drdpa_lock_owner(lck) == -1) {
2599  KMP_FATAL(LockUnsettingFree, func);
2600  }
2601  if (__kmp_get_drdpa_lock_owner(lck) != gtid) {
2602  KMP_FATAL(LockUnsettingSetByAnother, func);
2603  }
2604  return __kmp_release_nested_drdpa_lock(lck, gtid);
2605 }
2606 
2607 void __kmp_init_nested_drdpa_lock(kmp_drdpa_lock_t *lck) {
2608  __kmp_init_drdpa_lock(lck);
2609  lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
2610 }
2611 
2612 void __kmp_destroy_nested_drdpa_lock(kmp_drdpa_lock_t *lck) {
2613  __kmp_destroy_drdpa_lock(lck);
2614  lck->lk.depth_locked = 0;
2615 }
2616 
2617 static void __kmp_destroy_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) {
2618  char const *const func = "omp_destroy_nest_lock";
2619  if (lck->lk.initialized != lck) {
2620  KMP_FATAL(LockIsUninitialized, func);
2621  }
2622  if (!__kmp_is_drdpa_lock_nestable(lck)) {
2623  KMP_FATAL(LockSimpleUsedAsNestable, func);
2624  }
2625  if (__kmp_get_drdpa_lock_owner(lck) != -1) {
2626  KMP_FATAL(LockStillOwned, func);
2627  }
2628  __kmp_destroy_nested_drdpa_lock(lck);
2629 }
2630 
2631 // access functions to fields which don't exist for all lock kinds.
2632 
2633 static const ident_t *__kmp_get_drdpa_lock_location(kmp_drdpa_lock_t *lck) {
2634  return lck->lk.location;
2635 }
2636 
2637 static void __kmp_set_drdpa_lock_location(kmp_drdpa_lock_t *lck,
2638  const ident_t *loc) {
2639  lck->lk.location = loc;
2640 }
2641 
2642 static kmp_lock_flags_t __kmp_get_drdpa_lock_flags(kmp_drdpa_lock_t *lck) {
2643  return lck->lk.flags;
2644 }
2645 
2646 static void __kmp_set_drdpa_lock_flags(kmp_drdpa_lock_t *lck,
2647  kmp_lock_flags_t flags) {
2648  lck->lk.flags = flags;
2649 }
2650 
2651 // Time stamp counter
2652 #if KMP_ARCH_X86 || KMP_ARCH_X86_64
2653 #define __kmp_tsc() __kmp_hardware_timestamp()
2654 // Runtime's default backoff parameters
2655 kmp_backoff_t __kmp_spin_backoff_params = {1, 4096, 100};
2656 #else
2657 // Use nanoseconds for other platforms
2658 extern kmp_uint64 __kmp_now_nsec();
2659 kmp_backoff_t __kmp_spin_backoff_params = {1, 256, 100};
2660 #define __kmp_tsc() __kmp_now_nsec()
2661 #endif
2662 
2663 // A useful predicate for dealing with timestamps that may wrap.
2664 // Is a before b? Since the timestamps may wrap, this is asking whether it's
2665 // shorter to go clockwise from a to b around the clock-face, or anti-clockwise.
2666 // Times where going clockwise is less distance than going anti-clockwise
2667 // are in the future, others are in the past. e.g. a = MAX-1, b = MAX+1 (=0),
2668 // then a > b (true) does not mean a reached b; whereas signed(a) = -2,
2669 // signed(b) = 0 captures the actual difference
2670 static inline bool before(kmp_uint64 a, kmp_uint64 b) {
2671  return ((kmp_int64)b - (kmp_int64)a) > 0;
2672 }
2673 
2674 // Truncated binary exponential backoff function
2675 void __kmp_spin_backoff(kmp_backoff_t *boff) {
2676  // We could flatten this loop, but making it a nested loop gives better result
2677  kmp_uint32 i;
2678  for (i = boff->step; i > 0; i--) {
2679  kmp_uint64 goal = __kmp_tsc() + boff->min_tick;
2680  do {
2681  KMP_CPU_PAUSE();
2682  } while (before(__kmp_tsc(), goal));
2683  }
2684  boff->step = (boff->step << 1 | 1) & (boff->max_backoff - 1);
2685 }
2686 
2687 #if KMP_USE_DYNAMIC_LOCK
2688 
2689 // Direct lock initializers. It simply writes a tag to the low 8 bits of the
2690 // lock word.
2691 static void __kmp_init_direct_lock(kmp_dyna_lock_t *lck,
2692  kmp_dyna_lockseq_t seq) {
2693  TCW_4(*lck, KMP_GET_D_TAG(seq));
2694  KA_TRACE(
2695  20,
2696  ("__kmp_init_direct_lock: initialized direct lock with type#%d\n", seq));
2697 }
2698 
2699 #if KMP_USE_TSX
2700 
2701 // HLE lock functions - imported from the testbed runtime.
2702 #define HLE_ACQUIRE ".byte 0xf2;"
2703 #define HLE_RELEASE ".byte 0xf3;"
2704 
2705 static inline kmp_uint32 swap4(kmp_uint32 volatile *p, kmp_uint32 v) {
2706  __asm__ volatile(HLE_ACQUIRE "xchg %1,%0" : "+r"(v), "+m"(*p) : : "memory");
2707  return v;
2708 }
2709 
2710 static void __kmp_destroy_hle_lock(kmp_dyna_lock_t *lck) { TCW_4(*lck, 0); }
2711 
2712 static void __kmp_destroy_hle_lock_with_checks(kmp_dyna_lock_t *lck) {
2713  TCW_4(*lck, 0);
2714 }
2715 
2716 static void __kmp_acquire_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) {
2717  // Use gtid for KMP_LOCK_BUSY if necessary
2718  if (swap4(lck, KMP_LOCK_BUSY(1, hle)) != KMP_LOCK_FREE(hle)) {
2719  int delay = 1;
2720  do {
2721  while (*(kmp_uint32 volatile *)lck != KMP_LOCK_FREE(hle)) {
2722  for (int i = delay; i != 0; --i)
2723  KMP_CPU_PAUSE();
2724  delay = ((delay << 1) | 1) & 7;
2725  }
2726  } while (swap4(lck, KMP_LOCK_BUSY(1, hle)) != KMP_LOCK_FREE(hle));
2727  }
2728 }
2729 
2730 static void __kmp_acquire_hle_lock_with_checks(kmp_dyna_lock_t *lck,
2731  kmp_int32 gtid) {
2732  __kmp_acquire_hle_lock(lck, gtid); // TODO: add checks
2733 }
2734 
2735 static int __kmp_release_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) {
2736  __asm__ volatile(HLE_RELEASE "movl %1,%0"
2737  : "=m"(*lck)
2738  : "r"(KMP_LOCK_FREE(hle))
2739  : "memory");
2740  return KMP_LOCK_RELEASED;
2741 }
2742 
2743 static int __kmp_release_hle_lock_with_checks(kmp_dyna_lock_t *lck,
2744  kmp_int32 gtid) {
2745  return __kmp_release_hle_lock(lck, gtid); // TODO: add checks
2746 }
2747 
2748 static int __kmp_test_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) {
2749  return swap4(lck, KMP_LOCK_BUSY(1, hle)) == KMP_LOCK_FREE(hle);
2750 }
2751 
2752 static int __kmp_test_hle_lock_with_checks(kmp_dyna_lock_t *lck,
2753  kmp_int32 gtid) {
2754  return __kmp_test_hle_lock(lck, gtid); // TODO: add checks
2755 }
2756 
2757 static void __kmp_init_rtm_queuing_lock(kmp_queuing_lock_t *lck) {
2758  __kmp_init_queuing_lock(lck);
2759 }
2760 
2761 static void __kmp_destroy_rtm_queuing_lock(kmp_queuing_lock_t *lck) {
2762  __kmp_destroy_queuing_lock(lck);
2763 }
2764 
2765 static void
2766 __kmp_destroy_rtm_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
2767  __kmp_destroy_queuing_lock_with_checks(lck);
2768 }
2769 
2770 KMP_ATTRIBUTE_TARGET_RTM
2771 static void __kmp_acquire_rtm_queuing_lock(kmp_queuing_lock_t *lck,
2772  kmp_int32 gtid) {
2773  unsigned retries = 3, status;
2774  do {
2775  status = _xbegin();
2776  if (status == _XBEGIN_STARTED) {
2777  if (__kmp_is_unlocked_queuing_lock(lck))
2778  return;
2779  _xabort(0xff);
2780  }
2781  if ((status & _XABORT_EXPLICIT) && _XABORT_CODE(status) == 0xff) {
2782  // Wait until lock becomes free
2783  while (!__kmp_is_unlocked_queuing_lock(lck)) {
2784  KMP_YIELD(TRUE);
2785  }
2786  } else if (!(status & _XABORT_RETRY))
2787  break;
2788  } while (retries--);
2789 
2790  // Fall-back non-speculative lock (xchg)
2791  __kmp_acquire_queuing_lock(lck, gtid);
2792 }
2793 
2794 static void __kmp_acquire_rtm_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
2795  kmp_int32 gtid) {
2796  __kmp_acquire_rtm_queuing_lock(lck, gtid);
2797 }
2798 
2799 KMP_ATTRIBUTE_TARGET_RTM
2800 static int __kmp_release_rtm_queuing_lock(kmp_queuing_lock_t *lck,
2801  kmp_int32 gtid) {
2802  if (__kmp_is_unlocked_queuing_lock(lck)) {
2803  // Releasing from speculation
2804  _xend();
2805  } else {
2806  // Releasing from a real lock
2807  __kmp_release_queuing_lock(lck, gtid);
2808  }
2809  return KMP_LOCK_RELEASED;
2810 }
2811 
2812 static int __kmp_release_rtm_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
2813  kmp_int32 gtid) {
2814  return __kmp_release_rtm_queuing_lock(lck, gtid);
2815 }
2816 
2817 KMP_ATTRIBUTE_TARGET_RTM
2818 static int __kmp_test_rtm_queuing_lock(kmp_queuing_lock_t *lck,
2819  kmp_int32 gtid) {
2820  unsigned retries = 3, status;
2821  do {
2822  status = _xbegin();
2823  if (status == _XBEGIN_STARTED && __kmp_is_unlocked_queuing_lock(lck)) {
2824  return 1;
2825  }
2826  if (!(status & _XABORT_RETRY))
2827  break;
2828  } while (retries--);
2829 
2830  return __kmp_test_queuing_lock(lck, gtid);
2831 }
2832 
2833 static int __kmp_test_rtm_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
2834  kmp_int32 gtid) {
2835  return __kmp_test_rtm_queuing_lock(lck, gtid);
2836 }
2837 
2838 // Reuse kmp_tas_lock_t for TSX lock which use RTM with fall-back spin lock.
2839 typedef kmp_tas_lock_t kmp_rtm_spin_lock_t;
2840 
2841 static void __kmp_destroy_rtm_spin_lock(kmp_rtm_spin_lock_t *lck) {
2842  KMP_ATOMIC_ST_REL(&lck->lk.poll, 0);
2843 }
2844 
2845 static void __kmp_destroy_rtm_spin_lock_with_checks(kmp_rtm_spin_lock_t *lck) {
2846  __kmp_destroy_rtm_spin_lock(lck);
2847 }
2848 
2849 KMP_ATTRIBUTE_TARGET_RTM
2850 static int __kmp_acquire_rtm_spin_lock(kmp_rtm_spin_lock_t *lck,
2851  kmp_int32 gtid) {
2852  unsigned retries = 3, status;
2853  kmp_int32 lock_free = KMP_LOCK_FREE(rtm_spin);
2854  kmp_int32 lock_busy = KMP_LOCK_BUSY(1, rtm_spin);
2855  do {
2856  status = _xbegin();
2857  if (status == _XBEGIN_STARTED) {
2858  if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == lock_free)
2859  return KMP_LOCK_ACQUIRED_FIRST;
2860  _xabort(0xff);
2861  }
2862  if ((status & _XABORT_EXPLICIT) && _XABORT_CODE(status) == 0xff) {
2863  // Wait until lock becomes free
2864  while (KMP_ATOMIC_LD_RLX(&lck->lk.poll) != lock_free) {
2865  KMP_YIELD(TRUE);
2866  }
2867  } else if (!(status & _XABORT_RETRY))
2868  break;
2869  } while (retries--);
2870 
2871  // Fall-back spin lock
2872  KMP_FSYNC_PREPARE(lck);
2873  kmp_backoff_t backoff = __kmp_spin_backoff_params;
2874  while (KMP_ATOMIC_LD_RLX(&lck->lk.poll) != lock_free ||
2875  !__kmp_atomic_compare_store_acq(&lck->lk.poll, lock_free, lock_busy)) {
2876  __kmp_spin_backoff(&backoff);
2877  }
2878  KMP_FSYNC_ACQUIRED(lck);
2879  return KMP_LOCK_ACQUIRED_FIRST;
2880 }
2881 
2882 static int __kmp_acquire_rtm_spin_lock_with_checks(kmp_rtm_spin_lock_t *lck,
2883  kmp_int32 gtid) {
2884  return __kmp_acquire_rtm_spin_lock(lck, gtid);
2885 }
2886 
2887 KMP_ATTRIBUTE_TARGET_RTM
2888 static int __kmp_release_rtm_spin_lock(kmp_rtm_spin_lock_t *lck,
2889  kmp_int32 gtid) {
2890  if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == KMP_LOCK_FREE(rtm_spin)) {
2891  // Releasing from speculation
2892  _xend();
2893  } else {
2894  // Releasing from a real lock
2895  KMP_FSYNC_RELEASING(lck);
2896  KMP_ATOMIC_ST_REL(&lck->lk.poll, KMP_LOCK_FREE(rtm_spin));
2897  }
2898  return KMP_LOCK_RELEASED;
2899 }
2900 
2901 static int __kmp_release_rtm_spin_lock_with_checks(kmp_rtm_spin_lock_t *lck,
2902  kmp_int32 gtid) {
2903  return __kmp_release_rtm_spin_lock(lck, gtid);
2904 }
2905 
2906 KMP_ATTRIBUTE_TARGET_RTM
2907 static int __kmp_test_rtm_spin_lock(kmp_rtm_spin_lock_t *lck, kmp_int32 gtid) {
2908  unsigned retries = 3, status;
2909  kmp_int32 lock_free = KMP_LOCK_FREE(rtm_spin);
2910  kmp_int32 lock_busy = KMP_LOCK_BUSY(1, rtm_spin);
2911  do {
2912  status = _xbegin();
2913  if (status == _XBEGIN_STARTED &&
2914  KMP_ATOMIC_LD_RLX(&lck->lk.poll) == lock_free) {
2915  return TRUE;
2916  }
2917  if (!(status & _XABORT_RETRY))
2918  break;
2919  } while (retries--);
2920 
2921  if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == lock_free &&
2922  __kmp_atomic_compare_store_acq(&lck->lk.poll, lock_free, lock_busy)) {
2923  KMP_FSYNC_ACQUIRED(lck);
2924  return TRUE;
2925  }
2926  return FALSE;
2927 }
2928 
2929 static int __kmp_test_rtm_spin_lock_with_checks(kmp_rtm_spin_lock_t *lck,
2930  kmp_int32 gtid) {
2931  return __kmp_test_rtm_spin_lock(lck, gtid);
2932 }
2933 
2934 #endif // KMP_USE_TSX
2935 
2936 // Entry functions for indirect locks (first element of direct lock jump tables)
2937 static void __kmp_init_indirect_lock(kmp_dyna_lock_t *l,
2938  kmp_dyna_lockseq_t tag);
2939 static void __kmp_destroy_indirect_lock(kmp_dyna_lock_t *lock);
2940 static int __kmp_set_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32);
2941 static int __kmp_unset_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32);
2942 static int __kmp_test_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32);
2943 static int __kmp_set_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
2944  kmp_int32);
2945 static int __kmp_unset_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
2946  kmp_int32);
2947 static int __kmp_test_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
2948  kmp_int32);
2949 
2950 // Lock function definitions for the union parameter type
2951 #define KMP_FOREACH_LOCK_KIND(m, a) m(ticket, a) m(queuing, a) m(drdpa, a)
2952 
2953 #define expand1(lk, op) \
2954  static void __kmp_##op##_##lk##_##lock(kmp_user_lock_p lock) { \
2955  __kmp_##op##_##lk##_##lock(&lock->lk); \
2956  }
2957 #define expand2(lk, op) \
2958  static int __kmp_##op##_##lk##_##lock(kmp_user_lock_p lock, \
2959  kmp_int32 gtid) { \
2960  return __kmp_##op##_##lk##_##lock(&lock->lk, gtid); \
2961  }
2962 #define expand3(lk, op) \
2963  static void __kmp_set_##lk##_##lock_flags(kmp_user_lock_p lock, \
2964  kmp_lock_flags_t flags) { \
2965  __kmp_set_##lk##_lock_flags(&lock->lk, flags); \
2966  }
2967 #define expand4(lk, op) \
2968  static void __kmp_set_##lk##_##lock_location(kmp_user_lock_p lock, \
2969  const ident_t *loc) { \
2970  __kmp_set_##lk##_lock_location(&lock->lk, loc); \
2971  }
2972 
2973 KMP_FOREACH_LOCK_KIND(expand1, init)
2974 KMP_FOREACH_LOCK_KIND(expand1, init_nested)
2975 KMP_FOREACH_LOCK_KIND(expand1, destroy)
2976 KMP_FOREACH_LOCK_KIND(expand1, destroy_nested)
2977 KMP_FOREACH_LOCK_KIND(expand2, acquire)
2978 KMP_FOREACH_LOCK_KIND(expand2, acquire_nested)
2979 KMP_FOREACH_LOCK_KIND(expand2, release)
2980 KMP_FOREACH_LOCK_KIND(expand2, release_nested)
2981 KMP_FOREACH_LOCK_KIND(expand2, test)
2982 KMP_FOREACH_LOCK_KIND(expand2, test_nested)
2983 KMP_FOREACH_LOCK_KIND(expand3, )
2984 KMP_FOREACH_LOCK_KIND(expand4, )
2985 
2986 #undef expand1
2987 #undef expand2
2988 #undef expand3
2989 #undef expand4
2990 
2991 // Jump tables for the indirect lock functions
2992 // Only fill in the odd entries, that avoids the need to shift out the low bit
2993 
2994 // init functions
2995 #define expand(l, op) 0, __kmp_init_direct_lock,
2996 void (*__kmp_direct_init[])(kmp_dyna_lock_t *, kmp_dyna_lockseq_t) = {
2997  __kmp_init_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, init)};
2998 #undef expand
2999 
3000 // destroy functions
3001 #define expand(l, op) 0, (void (*)(kmp_dyna_lock_t *))__kmp_##op##_##l##_lock,
3002 static void (*direct_destroy[])(kmp_dyna_lock_t *) = {
3003  __kmp_destroy_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, destroy)};
3004 #undef expand
3005 #define expand(l, op) \
3006  0, (void (*)(kmp_dyna_lock_t *))__kmp_destroy_##l##_lock_with_checks,
3007 static void (*direct_destroy_check[])(kmp_dyna_lock_t *) = {
3008  __kmp_destroy_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, destroy)};
3009 #undef expand
3010 
3011 // set/acquire functions
3012 #define expand(l, op) \
3013  0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock,
3014 static int (*direct_set[])(kmp_dyna_lock_t *, kmp_int32) = {
3015  __kmp_set_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, acquire)};
3016 #undef expand
3017 #define expand(l, op) \
3018  0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock_with_checks,
3019 static int (*direct_set_check[])(kmp_dyna_lock_t *, kmp_int32) = {
3020  __kmp_set_indirect_lock_with_checks, 0,
3021  KMP_FOREACH_D_LOCK(expand, acquire)};
3022 #undef expand
3023 
3024 // unset/release and test functions
3025 #define expand(l, op) \
3026  0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock,
3027 static int (*direct_unset[])(kmp_dyna_lock_t *, kmp_int32) = {
3028  __kmp_unset_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, release)};
3029 static int (*direct_test[])(kmp_dyna_lock_t *, kmp_int32) = {
3030  __kmp_test_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, test)};
3031 #undef expand
3032 #define expand(l, op) \
3033  0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock_with_checks,
3034 static int (*direct_unset_check[])(kmp_dyna_lock_t *, kmp_int32) = {
3035  __kmp_unset_indirect_lock_with_checks, 0,
3036  KMP_FOREACH_D_LOCK(expand, release)};
3037 static int (*direct_test_check[])(kmp_dyna_lock_t *, kmp_int32) = {
3038  __kmp_test_indirect_lock_with_checks, 0, KMP_FOREACH_D_LOCK(expand, test)};
3039 #undef expand
3040 
3041 // Exposes only one set of jump tables (*lock or *lock_with_checks).
3042 void (**__kmp_direct_destroy)(kmp_dyna_lock_t *) = 0;
3043 int (**__kmp_direct_set)(kmp_dyna_lock_t *, kmp_int32) = 0;
3044 int (**__kmp_direct_unset)(kmp_dyna_lock_t *, kmp_int32) = 0;
3045 int (**__kmp_direct_test)(kmp_dyna_lock_t *, kmp_int32) = 0;
3046 
3047 // Jump tables for the indirect lock functions
3048 #define expand(l, op) (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock,
3049 void (*__kmp_indirect_init[])(kmp_user_lock_p) = {
3050  KMP_FOREACH_I_LOCK(expand, init)};
3051 #undef expand
3052 
3053 #define expand(l, op) (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock,
3054 static void (*indirect_destroy[])(kmp_user_lock_p) = {
3055  KMP_FOREACH_I_LOCK(expand, destroy)};
3056 #undef expand
3057 #define expand(l, op) \
3058  (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock_with_checks,
3059 static void (*indirect_destroy_check[])(kmp_user_lock_p) = {
3060  KMP_FOREACH_I_LOCK(expand, destroy)};
3061 #undef expand
3062 
3063 // set/acquire functions
3064 #define expand(l, op) \
3065  (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock,
3066 static int (*indirect_set[])(kmp_user_lock_p,
3067  kmp_int32) = {KMP_FOREACH_I_LOCK(expand, acquire)};
3068 #undef expand
3069 #define expand(l, op) \
3070  (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock_with_checks,
3071 static int (*indirect_set_check[])(kmp_user_lock_p, kmp_int32) = {
3072  KMP_FOREACH_I_LOCK(expand, acquire)};
3073 #undef expand
3074 
3075 // unset/release and test functions
3076 #define expand(l, op) \
3077  (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock,
3078 static int (*indirect_unset[])(kmp_user_lock_p, kmp_int32) = {
3079  KMP_FOREACH_I_LOCK(expand, release)};
3080 static int (*indirect_test[])(kmp_user_lock_p,
3081  kmp_int32) = {KMP_FOREACH_I_LOCK(expand, test)};
3082 #undef expand
3083 #define expand(l, op) \
3084  (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock_with_checks,
3085 static int (*indirect_unset_check[])(kmp_user_lock_p, kmp_int32) = {
3086  KMP_FOREACH_I_LOCK(expand, release)};
3087 static int (*indirect_test_check[])(kmp_user_lock_p, kmp_int32) = {
3088  KMP_FOREACH_I_LOCK(expand, test)};
3089 #undef expand
3090 
3091 // Exposes only one jump tables (*lock or *lock_with_checks).
3092 void (**__kmp_indirect_destroy)(kmp_user_lock_p) = 0;
3093 int (**__kmp_indirect_set)(kmp_user_lock_p, kmp_int32) = 0;
3094 int (**__kmp_indirect_unset)(kmp_user_lock_p, kmp_int32) = 0;
3095 int (**__kmp_indirect_test)(kmp_user_lock_p, kmp_int32) = 0;
3096 
3097 // Lock index table.
3098 kmp_indirect_lock_table_t __kmp_i_lock_table;
3099 
3100 // Size of indirect locks.
3101 static kmp_uint32 __kmp_indirect_lock_size[KMP_NUM_I_LOCKS] = {0};
3102 
3103 // Jump tables for lock accessor/modifier.
3104 void (*__kmp_indirect_set_location[KMP_NUM_I_LOCKS])(kmp_user_lock_p,
3105  const ident_t *) = {0};
3106 void (*__kmp_indirect_set_flags[KMP_NUM_I_LOCKS])(kmp_user_lock_p,
3107  kmp_lock_flags_t) = {0};
3108 const ident_t *(*__kmp_indirect_get_location[KMP_NUM_I_LOCKS])(
3109  kmp_user_lock_p) = {0};
3110 kmp_lock_flags_t (*__kmp_indirect_get_flags[KMP_NUM_I_LOCKS])(
3111  kmp_user_lock_p) = {0};
3112 
3113 // Use different lock pools for different lock types.
3114 static kmp_indirect_lock_t *__kmp_indirect_lock_pool[KMP_NUM_I_LOCKS] = {0};
3115 
3116 // User lock allocator for dynamically dispatched indirect locks. Every entry of
3117 // the indirect lock table holds the address and type of the allocated indirect
3118 // lock (kmp_indirect_lock_t), and the size of the table doubles when it is
3119 // full. A destroyed indirect lock object is returned to the reusable pool of
3120 // locks, unique to each lock type.
3121 kmp_indirect_lock_t *__kmp_allocate_indirect_lock(void **user_lock,
3122  kmp_int32 gtid,
3123  kmp_indirect_locktag_t tag) {
3124  kmp_indirect_lock_t *lck;
3125  kmp_lock_index_t idx;
3126 
3127  __kmp_acquire_lock(&__kmp_global_lock, gtid);
3128 
3129  if (__kmp_indirect_lock_pool[tag] != NULL) {
3130  // Reuse the allocated and destroyed lock object
3131  lck = __kmp_indirect_lock_pool[tag];
3132  if (OMP_LOCK_T_SIZE < sizeof(void *))
3133  idx = lck->lock->pool.index;
3134  __kmp_indirect_lock_pool[tag] = (kmp_indirect_lock_t *)lck->lock->pool.next;
3135  KA_TRACE(20, ("__kmp_allocate_indirect_lock: reusing an existing lock %p\n",
3136  lck));
3137  } else {
3138  idx = __kmp_i_lock_table.next;
3139  // Check capacity and double the size if it is full
3140  if (idx == __kmp_i_lock_table.size) {
3141  // Double up the space for block pointers
3142  int row = __kmp_i_lock_table.size / KMP_I_LOCK_CHUNK;
3143  kmp_indirect_lock_t **new_table = (kmp_indirect_lock_t **)__kmp_allocate(
3144  2 * row * sizeof(kmp_indirect_lock_t *));
3145  KMP_MEMCPY(new_table, __kmp_i_lock_table.table,
3146  row * sizeof(kmp_indirect_lock_t *));
3147  kmp_indirect_lock_t **old_table = __kmp_i_lock_table.table;
3148  __kmp_i_lock_table.table = new_table;
3149  __kmp_free(old_table);
3150  // Allocate new objects in the new blocks
3151  for (int i = row; i < 2 * row; ++i)
3152  *(__kmp_i_lock_table.table + i) = (kmp_indirect_lock_t *)__kmp_allocate(
3153  KMP_I_LOCK_CHUNK * sizeof(kmp_indirect_lock_t));
3154  __kmp_i_lock_table.size = 2 * idx;
3155  }
3156  __kmp_i_lock_table.next++;
3157  lck = KMP_GET_I_LOCK(idx);
3158  // Allocate a new base lock object
3159  lck->lock = (kmp_user_lock_p)__kmp_allocate(__kmp_indirect_lock_size[tag]);
3160  KA_TRACE(20,
3161  ("__kmp_allocate_indirect_lock: allocated a new lock %p\n", lck));
3162  }
3163 
3164  __kmp_release_lock(&__kmp_global_lock, gtid);
3165 
3166  lck->type = tag;
3167 
3168  if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3169  *((kmp_lock_index_t *)user_lock) = idx
3170  << 1; // indirect lock word must be even
3171  } else {
3172  *((kmp_indirect_lock_t **)user_lock) = lck;
3173  }
3174 
3175  return lck;
3176 }
3177 
3178 // User lock lookup for dynamically dispatched locks.
3179 static __forceinline kmp_indirect_lock_t *
3180 __kmp_lookup_indirect_lock(void **user_lock, const char *func) {
3181  if (__kmp_env_consistency_check) {
3182  kmp_indirect_lock_t *lck = NULL;
3183  if (user_lock == NULL) {
3184  KMP_FATAL(LockIsUninitialized, func);
3185  }
3186  if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3187  kmp_lock_index_t idx = KMP_EXTRACT_I_INDEX(user_lock);
3188  if (idx >= __kmp_i_lock_table.size) {
3189  KMP_FATAL(LockIsUninitialized, func);
3190  }
3191  lck = KMP_GET_I_LOCK(idx);
3192  } else {
3193  lck = *((kmp_indirect_lock_t **)user_lock);
3194  }
3195  if (lck == NULL) {
3196  KMP_FATAL(LockIsUninitialized, func);
3197  }
3198  return lck;
3199  } else {
3200  if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3201  return KMP_GET_I_LOCK(KMP_EXTRACT_I_INDEX(user_lock));
3202  } else {
3203  return *((kmp_indirect_lock_t **)user_lock);
3204  }
3205  }
3206 }
3207 
3208 static void __kmp_init_indirect_lock(kmp_dyna_lock_t *lock,
3209  kmp_dyna_lockseq_t seq) {
3210 #if KMP_USE_ADAPTIVE_LOCKS
3211  if (seq == lockseq_adaptive && !__kmp_cpuinfo.rtm) {
3212  KMP_WARNING(AdaptiveNotSupported, "kmp_lockseq_t", "adaptive");
3213  seq = lockseq_queuing;
3214  }
3215 #endif
3216 #if KMP_USE_TSX
3217  if (seq == lockseq_rtm_queuing && !__kmp_cpuinfo.rtm) {
3218  seq = lockseq_queuing;
3219  }
3220 #endif
3221  kmp_indirect_locktag_t tag = KMP_GET_I_TAG(seq);
3222  kmp_indirect_lock_t *l =
3223  __kmp_allocate_indirect_lock((void **)lock, __kmp_entry_gtid(), tag);
3224  KMP_I_LOCK_FUNC(l, init)(l->lock);
3225  KA_TRACE(
3226  20, ("__kmp_init_indirect_lock: initialized indirect lock with type#%d\n",
3227  seq));
3228 }
3229 
3230 static void __kmp_destroy_indirect_lock(kmp_dyna_lock_t *lock) {
3231  kmp_uint32 gtid = __kmp_entry_gtid();
3232  kmp_indirect_lock_t *l =
3233  __kmp_lookup_indirect_lock((void **)lock, "omp_destroy_lock");
3234  KMP_I_LOCK_FUNC(l, destroy)(l->lock);
3235  kmp_indirect_locktag_t tag = l->type;
3236 
3237  __kmp_acquire_lock(&__kmp_global_lock, gtid);
3238 
3239  // Use the base lock's space to keep the pool chain.
3240  l->lock->pool.next = (kmp_user_lock_p)__kmp_indirect_lock_pool[tag];
3241  if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3242  l->lock->pool.index = KMP_EXTRACT_I_INDEX(lock);
3243  }
3244  __kmp_indirect_lock_pool[tag] = l;
3245 
3246  __kmp_release_lock(&__kmp_global_lock, gtid);
3247 }
3248 
3249 static int __kmp_set_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) {
3250  kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock);
3251  return KMP_I_LOCK_FUNC(l, set)(l->lock, gtid);
3252 }
3253 
3254 static int __kmp_unset_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) {
3255  kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock);
3256  return KMP_I_LOCK_FUNC(l, unset)(l->lock, gtid);
3257 }
3258 
3259 static int __kmp_test_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) {
3260  kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock);
3261  return KMP_I_LOCK_FUNC(l, test)(l->lock, gtid);
3262 }
3263 
3264 static int __kmp_set_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
3265  kmp_int32 gtid) {
3266  kmp_indirect_lock_t *l =
3267  __kmp_lookup_indirect_lock((void **)lock, "omp_set_lock");
3268  return KMP_I_LOCK_FUNC(l, set)(l->lock, gtid);
3269 }
3270 
3271 static int __kmp_unset_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
3272  kmp_int32 gtid) {
3273  kmp_indirect_lock_t *l =
3274  __kmp_lookup_indirect_lock((void **)lock, "omp_unset_lock");
3275  return KMP_I_LOCK_FUNC(l, unset)(l->lock, gtid);
3276 }
3277 
3278 static int __kmp_test_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
3279  kmp_int32 gtid) {
3280  kmp_indirect_lock_t *l =
3281  __kmp_lookup_indirect_lock((void **)lock, "omp_test_lock");
3282  return KMP_I_LOCK_FUNC(l, test)(l->lock, gtid);
3283 }
3284 
3285 kmp_dyna_lockseq_t __kmp_user_lock_seq = lockseq_queuing;
3286 
3287 // This is used only in kmp_error.cpp when consistency checking is on.
3288 kmp_int32 __kmp_get_user_lock_owner(kmp_user_lock_p lck, kmp_uint32 seq) {
3289  switch (seq) {
3290  case lockseq_tas:
3291  case lockseq_nested_tas:
3292  return __kmp_get_tas_lock_owner((kmp_tas_lock_t *)lck);
3293 #if KMP_USE_FUTEX
3294  case lockseq_futex:
3295  case lockseq_nested_futex:
3296  return __kmp_get_futex_lock_owner((kmp_futex_lock_t *)lck);
3297 #endif
3298  case lockseq_ticket:
3299  case lockseq_nested_ticket:
3300  return __kmp_get_ticket_lock_owner((kmp_ticket_lock_t *)lck);
3301  case lockseq_queuing:
3302  case lockseq_nested_queuing:
3303 #if KMP_USE_ADAPTIVE_LOCKS
3304  case lockseq_adaptive:
3305 #endif
3306  return __kmp_get_queuing_lock_owner((kmp_queuing_lock_t *)lck);
3307  case lockseq_drdpa:
3308  case lockseq_nested_drdpa:
3309  return __kmp_get_drdpa_lock_owner((kmp_drdpa_lock_t *)lck);
3310  default:
3311  return 0;
3312  }
3313 }
3314 
3315 // Initializes data for dynamic user locks.
3316 void __kmp_init_dynamic_user_locks() {
3317  // Initialize jump table for the lock functions
3318  if (__kmp_env_consistency_check) {
3319  __kmp_direct_set = direct_set_check;
3320  __kmp_direct_unset = direct_unset_check;
3321  __kmp_direct_test = direct_test_check;
3322  __kmp_direct_destroy = direct_destroy_check;
3323  __kmp_indirect_set = indirect_set_check;
3324  __kmp_indirect_unset = indirect_unset_check;
3325  __kmp_indirect_test = indirect_test_check;
3326  __kmp_indirect_destroy = indirect_destroy_check;
3327  } else {
3328  __kmp_direct_set = direct_set;
3329  __kmp_direct_unset = direct_unset;
3330  __kmp_direct_test = direct_test;
3331  __kmp_direct_destroy = direct_destroy;
3332  __kmp_indirect_set = indirect_set;
3333  __kmp_indirect_unset = indirect_unset;
3334  __kmp_indirect_test = indirect_test;
3335  __kmp_indirect_destroy = indirect_destroy;
3336  }
3337  // If the user locks have already been initialized, then return. Allow the
3338  // switch between different KMP_CONSISTENCY_CHECK values, but do not allocate
3339  // new lock tables if they have already been allocated.
3340  if (__kmp_init_user_locks)
3341  return;
3342 
3343  // Initialize lock index table
3344  __kmp_i_lock_table.size = KMP_I_LOCK_CHUNK;
3345  __kmp_i_lock_table.table =
3346  (kmp_indirect_lock_t **)__kmp_allocate(sizeof(kmp_indirect_lock_t *));
3347  *(__kmp_i_lock_table.table) = (kmp_indirect_lock_t *)__kmp_allocate(
3348  KMP_I_LOCK_CHUNK * sizeof(kmp_indirect_lock_t));
3349  __kmp_i_lock_table.next = 0;
3350 
3351  // Indirect lock size
3352  __kmp_indirect_lock_size[locktag_ticket] = sizeof(kmp_ticket_lock_t);
3353  __kmp_indirect_lock_size[locktag_queuing] = sizeof(kmp_queuing_lock_t);
3354 #if KMP_USE_ADAPTIVE_LOCKS
3355  __kmp_indirect_lock_size[locktag_adaptive] = sizeof(kmp_adaptive_lock_t);
3356 #endif
3357  __kmp_indirect_lock_size[locktag_drdpa] = sizeof(kmp_drdpa_lock_t);
3358 #if KMP_USE_TSX
3359  __kmp_indirect_lock_size[locktag_rtm_queuing] = sizeof(kmp_queuing_lock_t);
3360 #endif
3361  __kmp_indirect_lock_size[locktag_nested_tas] = sizeof(kmp_tas_lock_t);
3362 #if KMP_USE_FUTEX
3363  __kmp_indirect_lock_size[locktag_nested_futex] = sizeof(kmp_futex_lock_t);
3364 #endif
3365  __kmp_indirect_lock_size[locktag_nested_ticket] = sizeof(kmp_ticket_lock_t);
3366  __kmp_indirect_lock_size[locktag_nested_queuing] = sizeof(kmp_queuing_lock_t);
3367  __kmp_indirect_lock_size[locktag_nested_drdpa] = sizeof(kmp_drdpa_lock_t);
3368 
3369 // Initialize lock accessor/modifier
3370 #define fill_jumps(table, expand, sep) \
3371  { \
3372  table[locktag##sep##ticket] = expand(ticket); \
3373  table[locktag##sep##queuing] = expand(queuing); \
3374  table[locktag##sep##drdpa] = expand(drdpa); \
3375  }
3376 
3377 #if KMP_USE_ADAPTIVE_LOCKS
3378 #define fill_table(table, expand) \
3379  { \
3380  fill_jumps(table, expand, _); \
3381  table[locktag_adaptive] = expand(queuing); \
3382  fill_jumps(table, expand, _nested_); \
3383  }
3384 #else
3385 #define fill_table(table, expand) \
3386  { \
3387  fill_jumps(table, expand, _); \
3388  fill_jumps(table, expand, _nested_); \
3389  }
3390 #endif // KMP_USE_ADAPTIVE_LOCKS
3391 
3392 #define expand(l) \
3393  (void (*)(kmp_user_lock_p, const ident_t *)) __kmp_set_##l##_lock_location
3394  fill_table(__kmp_indirect_set_location, expand);
3395 #undef expand
3396 #define expand(l) \
3397  (void (*)(kmp_user_lock_p, kmp_lock_flags_t)) __kmp_set_##l##_lock_flags
3398  fill_table(__kmp_indirect_set_flags, expand);
3399 #undef expand
3400 #define expand(l) \
3401  (const ident_t *(*)(kmp_user_lock_p)) __kmp_get_##l##_lock_location
3402  fill_table(__kmp_indirect_get_location, expand);
3403 #undef expand
3404 #define expand(l) \
3405  (kmp_lock_flags_t(*)(kmp_user_lock_p)) __kmp_get_##l##_lock_flags
3406  fill_table(__kmp_indirect_get_flags, expand);
3407 #undef expand
3408 
3409  __kmp_init_user_locks = TRUE;
3410 }
3411 
3412 // Clean up the lock table.
3413 void __kmp_cleanup_indirect_user_locks() {
3414  kmp_lock_index_t i;
3415  int k;
3416 
3417  // Clean up locks in the pools first (they were already destroyed before going
3418  // into the pools).
3419  for (k = 0; k < KMP_NUM_I_LOCKS; ++k) {
3420  kmp_indirect_lock_t *l = __kmp_indirect_lock_pool[k];
3421  while (l != NULL) {
3422  kmp_indirect_lock_t *ll = l;
3423  l = (kmp_indirect_lock_t *)l->lock->pool.next;
3424  KA_TRACE(20, ("__kmp_cleanup_indirect_user_locks: freeing %p from pool\n",
3425  ll));
3426  __kmp_free(ll->lock);
3427  ll->lock = NULL;
3428  }
3429  __kmp_indirect_lock_pool[k] = NULL;
3430  }
3431  // Clean up the remaining undestroyed locks.
3432  for (i = 0; i < __kmp_i_lock_table.next; i++) {
3433  kmp_indirect_lock_t *l = KMP_GET_I_LOCK(i);
3434  if (l->lock != NULL) {
3435  // Locks not destroyed explicitly need to be destroyed here.
3436  KMP_I_LOCK_FUNC(l, destroy)(l->lock);
3437  KA_TRACE(
3438  20,
3439  ("__kmp_cleanup_indirect_user_locks: destroy/freeing %p from table\n",
3440  l));
3441  __kmp_free(l->lock);
3442  }
3443  }
3444  // Free the table
3445  for (i = 0; i < __kmp_i_lock_table.size / KMP_I_LOCK_CHUNK; i++)
3446  __kmp_free(__kmp_i_lock_table.table[i]);
3447  __kmp_free(__kmp_i_lock_table.table);
3448 
3449  __kmp_init_user_locks = FALSE;
3450 }
3451 
3452 enum kmp_lock_kind __kmp_user_lock_kind = lk_default;
3453 int __kmp_num_locks_in_block = 1; // FIXME - tune this value
3454 
3455 #else // KMP_USE_DYNAMIC_LOCK
3456 
3457 static void __kmp_init_tas_lock_with_checks(kmp_tas_lock_t *lck) {
3458  __kmp_init_tas_lock(lck);
3459 }
3460 
3461 static void __kmp_init_nested_tas_lock_with_checks(kmp_tas_lock_t *lck) {
3462  __kmp_init_nested_tas_lock(lck);
3463 }
3464 
3465 #if KMP_USE_FUTEX
3466 static void __kmp_init_futex_lock_with_checks(kmp_futex_lock_t *lck) {
3467  __kmp_init_futex_lock(lck);
3468 }
3469 
3470 static void __kmp_init_nested_futex_lock_with_checks(kmp_futex_lock_t *lck) {
3471  __kmp_init_nested_futex_lock(lck);
3472 }
3473 #endif
3474 
3475 static int __kmp_is_ticket_lock_initialized(kmp_ticket_lock_t *lck) {
3476  return lck == lck->lk.self;
3477 }
3478 
3479 static void __kmp_init_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
3480  __kmp_init_ticket_lock(lck);
3481 }
3482 
3483 static void __kmp_init_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
3484  __kmp_init_nested_ticket_lock(lck);
3485 }
3486 
3487 static int __kmp_is_queuing_lock_initialized(kmp_queuing_lock_t *lck) {
3488  return lck == lck->lk.initialized;
3489 }
3490 
3491 static void __kmp_init_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
3492  __kmp_init_queuing_lock(lck);
3493 }
3494 
3495 static void
3496 __kmp_init_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
3497  __kmp_init_nested_queuing_lock(lck);
3498 }
3499 
3500 #if KMP_USE_ADAPTIVE_LOCKS
3501 static void __kmp_init_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck) {
3502  __kmp_init_adaptive_lock(lck);
3503 }
3504 #endif
3505 
3506 static int __kmp_is_drdpa_lock_initialized(kmp_drdpa_lock_t *lck) {
3507  return lck == lck->lk.initialized;
3508 }
3509 
3510 static void __kmp_init_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) {
3511  __kmp_init_drdpa_lock(lck);
3512 }
3513 
3514 static void __kmp_init_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) {
3515  __kmp_init_nested_drdpa_lock(lck);
3516 }
3517 
3518 /* user locks
3519  * They are implemented as a table of function pointers which are set to the
3520  * lock functions of the appropriate kind, once that has been determined. */
3521 
3522 enum kmp_lock_kind __kmp_user_lock_kind = lk_default;
3523 
3524 size_t __kmp_base_user_lock_size = 0;
3525 size_t __kmp_user_lock_size = 0;
3526 
3527 kmp_int32 (*__kmp_get_user_lock_owner_)(kmp_user_lock_p lck) = NULL;
3528 int (*__kmp_acquire_user_lock_with_checks_)(kmp_user_lock_p lck,
3529  kmp_int32 gtid) = NULL;
3530 
3531 int (*__kmp_test_user_lock_with_checks_)(kmp_user_lock_p lck,
3532  kmp_int32 gtid) = NULL;
3533 int (*__kmp_release_user_lock_with_checks_)(kmp_user_lock_p lck,
3534  kmp_int32 gtid) = NULL;
3535 void (*__kmp_init_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL;
3536 void (*__kmp_destroy_user_lock_)(kmp_user_lock_p lck) = NULL;
3537 void (*__kmp_destroy_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL;
3538 int (*__kmp_acquire_nested_user_lock_with_checks_)(kmp_user_lock_p lck,
3539  kmp_int32 gtid) = NULL;
3540 
3541 int (*__kmp_test_nested_user_lock_with_checks_)(kmp_user_lock_p lck,
3542  kmp_int32 gtid) = NULL;
3543 int (*__kmp_release_nested_user_lock_with_checks_)(kmp_user_lock_p lck,
3544  kmp_int32 gtid) = NULL;
3545 void (*__kmp_init_nested_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL;
3546 void (*__kmp_destroy_nested_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL;
3547 
3548 int (*__kmp_is_user_lock_initialized_)(kmp_user_lock_p lck) = NULL;
3549 const ident_t *(*__kmp_get_user_lock_location_)(kmp_user_lock_p lck) = NULL;
3550 void (*__kmp_set_user_lock_location_)(kmp_user_lock_p lck,
3551  const ident_t *loc) = NULL;
3552 kmp_lock_flags_t (*__kmp_get_user_lock_flags_)(kmp_user_lock_p lck) = NULL;
3553 void (*__kmp_set_user_lock_flags_)(kmp_user_lock_p lck,
3554  kmp_lock_flags_t flags) = NULL;
3555 
3556 void __kmp_set_user_lock_vptrs(kmp_lock_kind_t user_lock_kind) {
3557  switch (user_lock_kind) {
3558  case lk_default:
3559  default:
3560  KMP_ASSERT(0);
3561 
3562  case lk_tas: {
3563  __kmp_base_user_lock_size = sizeof(kmp_base_tas_lock_t);
3564  __kmp_user_lock_size = sizeof(kmp_tas_lock_t);
3565 
3566  __kmp_get_user_lock_owner_ =
3567  (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_tas_lock_owner);
3568 
3569  if (__kmp_env_consistency_check) {
3570  KMP_BIND_USER_LOCK_WITH_CHECKS(tas);
3571  KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(tas);
3572  } else {
3573  KMP_BIND_USER_LOCK(tas);
3574  KMP_BIND_NESTED_USER_LOCK(tas);
3575  }
3576 
3577  __kmp_destroy_user_lock_ =
3578  (void (*)(kmp_user_lock_p))(&__kmp_destroy_tas_lock);
3579 
3580  __kmp_is_user_lock_initialized_ = (int (*)(kmp_user_lock_p))NULL;
3581 
3582  __kmp_get_user_lock_location_ = (const ident_t *(*)(kmp_user_lock_p))NULL;
3583 
3584  __kmp_set_user_lock_location_ =
3585  (void (*)(kmp_user_lock_p, const ident_t *))NULL;
3586 
3587  __kmp_get_user_lock_flags_ = (kmp_lock_flags_t(*)(kmp_user_lock_p))NULL;
3588 
3589  __kmp_set_user_lock_flags_ =
3590  (void (*)(kmp_user_lock_p, kmp_lock_flags_t))NULL;
3591  } break;
3592 
3593 #if KMP_USE_FUTEX
3594 
3595  case lk_futex: {
3596  __kmp_base_user_lock_size = sizeof(kmp_base_futex_lock_t);
3597  __kmp_user_lock_size = sizeof(kmp_futex_lock_t);
3598 
3599  __kmp_get_user_lock_owner_ =
3600  (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_futex_lock_owner);
3601 
3602  if (__kmp_env_consistency_check) {
3603  KMP_BIND_USER_LOCK_WITH_CHECKS(futex);
3604  KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(futex);
3605  } else {
3606  KMP_BIND_USER_LOCK(futex);
3607  KMP_BIND_NESTED_USER_LOCK(futex);
3608  }
3609 
3610  __kmp_destroy_user_lock_ =
3611  (void (*)(kmp_user_lock_p))(&__kmp_destroy_futex_lock);
3612 
3613  __kmp_is_user_lock_initialized_ = (int (*)(kmp_user_lock_p))NULL;
3614 
3615  __kmp_get_user_lock_location_ = (const ident_t *(*)(kmp_user_lock_p))NULL;
3616 
3617  __kmp_set_user_lock_location_ =
3618  (void (*)(kmp_user_lock_p, const ident_t *))NULL;
3619 
3620  __kmp_get_user_lock_flags_ = (kmp_lock_flags_t(*)(kmp_user_lock_p))NULL;
3621 
3622  __kmp_set_user_lock_flags_ =
3623  (void (*)(kmp_user_lock_p, kmp_lock_flags_t))NULL;
3624  } break;
3625 
3626 #endif // KMP_USE_FUTEX
3627 
3628  case lk_ticket: {
3629  __kmp_base_user_lock_size = sizeof(kmp_base_ticket_lock_t);
3630  __kmp_user_lock_size = sizeof(kmp_ticket_lock_t);
3631 
3632  __kmp_get_user_lock_owner_ =
3633  (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_owner);
3634 
3635  if (__kmp_env_consistency_check) {
3636  KMP_BIND_USER_LOCK_WITH_CHECKS(ticket);
3637  KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(ticket);
3638  } else {
3639  KMP_BIND_USER_LOCK(ticket);
3640  KMP_BIND_NESTED_USER_LOCK(ticket);
3641  }
3642 
3643  __kmp_destroy_user_lock_ =
3644  (void (*)(kmp_user_lock_p))(&__kmp_destroy_ticket_lock);
3645 
3646  __kmp_is_user_lock_initialized_ =
3647  (int (*)(kmp_user_lock_p))(&__kmp_is_ticket_lock_initialized);
3648 
3649  __kmp_get_user_lock_location_ =
3650  (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_location);
3651 
3652  __kmp_set_user_lock_location_ = (void (*)(
3653  kmp_user_lock_p, const ident_t *))(&__kmp_set_ticket_lock_location);
3654 
3655  __kmp_get_user_lock_flags_ =
3656  (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_flags);
3657 
3658  __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))(
3659  &__kmp_set_ticket_lock_flags);
3660  } break;
3661 
3662  case lk_queuing: {
3663  __kmp_base_user_lock_size = sizeof(kmp_base_queuing_lock_t);
3664  __kmp_user_lock_size = sizeof(kmp_queuing_lock_t);
3665 
3666  __kmp_get_user_lock_owner_ =
3667  (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_owner);
3668 
3669  if (__kmp_env_consistency_check) {
3670  KMP_BIND_USER_LOCK_WITH_CHECKS(queuing);
3671  KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(queuing);
3672  } else {
3673  KMP_BIND_USER_LOCK(queuing);
3674  KMP_BIND_NESTED_USER_LOCK(queuing);
3675  }
3676 
3677  __kmp_destroy_user_lock_ =
3678  (void (*)(kmp_user_lock_p))(&__kmp_destroy_queuing_lock);
3679 
3680  __kmp_is_user_lock_initialized_ =
3681  (int (*)(kmp_user_lock_p))(&__kmp_is_queuing_lock_initialized);
3682 
3683  __kmp_get_user_lock_location_ =
3684  (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_location);
3685 
3686  __kmp_set_user_lock_location_ = (void (*)(
3687  kmp_user_lock_p, const ident_t *))(&__kmp_set_queuing_lock_location);
3688 
3689  __kmp_get_user_lock_flags_ =
3690  (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_flags);
3691 
3692  __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))(
3693  &__kmp_set_queuing_lock_flags);
3694  } break;
3695 
3696 #if KMP_USE_ADAPTIVE_LOCKS
3697  case lk_adaptive: {
3698  __kmp_base_user_lock_size = sizeof(kmp_base_adaptive_lock_t);
3699  __kmp_user_lock_size = sizeof(kmp_adaptive_lock_t);
3700 
3701  __kmp_get_user_lock_owner_ =
3702  (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_owner);
3703 
3704  if (__kmp_env_consistency_check) {
3705  KMP_BIND_USER_LOCK_WITH_CHECKS(adaptive);
3706  } else {
3707  KMP_BIND_USER_LOCK(adaptive);
3708  }
3709 
3710  __kmp_destroy_user_lock_ =
3711  (void (*)(kmp_user_lock_p))(&__kmp_destroy_adaptive_lock);
3712 
3713  __kmp_is_user_lock_initialized_ =
3714  (int (*)(kmp_user_lock_p))(&__kmp_is_queuing_lock_initialized);
3715 
3716  __kmp_get_user_lock_location_ =
3717  (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_location);
3718 
3719  __kmp_set_user_lock_location_ = (void (*)(
3720  kmp_user_lock_p, const ident_t *))(&__kmp_set_queuing_lock_location);
3721 
3722  __kmp_get_user_lock_flags_ =
3723  (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_flags);
3724 
3725  __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))(
3726  &__kmp_set_queuing_lock_flags);
3727 
3728  } break;
3729 #endif // KMP_USE_ADAPTIVE_LOCKS
3730 
3731  case lk_drdpa: {
3732  __kmp_base_user_lock_size = sizeof(kmp_base_drdpa_lock_t);
3733  __kmp_user_lock_size = sizeof(kmp_drdpa_lock_t);
3734 
3735  __kmp_get_user_lock_owner_ =
3736  (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_owner);
3737 
3738  if (__kmp_env_consistency_check) {
3739  KMP_BIND_USER_LOCK_WITH_CHECKS(drdpa);
3740  KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(drdpa);
3741  } else {
3742  KMP_BIND_USER_LOCK(drdpa);
3743  KMP_BIND_NESTED_USER_LOCK(drdpa);
3744  }
3745 
3746  __kmp_destroy_user_lock_ =
3747  (void (*)(kmp_user_lock_p))(&__kmp_destroy_drdpa_lock);
3748 
3749  __kmp_is_user_lock_initialized_ =
3750  (int (*)(kmp_user_lock_p))(&__kmp_is_drdpa_lock_initialized);
3751 
3752  __kmp_get_user_lock_location_ =
3753  (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_location);
3754 
3755  __kmp_set_user_lock_location_ = (void (*)(
3756  kmp_user_lock_p, const ident_t *))(&__kmp_set_drdpa_lock_location);
3757 
3758  __kmp_get_user_lock_flags_ =
3759  (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_flags);
3760 
3761  __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))(
3762  &__kmp_set_drdpa_lock_flags);
3763  } break;
3764  }
3765 }
3766 
3767 // ----------------------------------------------------------------------------
3768 // User lock table & lock allocation
3769 
3770 kmp_lock_table_t __kmp_user_lock_table = {1, 0, NULL};
3771 kmp_user_lock_p __kmp_lock_pool = NULL;
3772 
3773 // Lock block-allocation support.
3774 kmp_block_of_locks *__kmp_lock_blocks = NULL;
3775 int __kmp_num_locks_in_block = 1; // FIXME - tune this value
3776 
3777 static kmp_lock_index_t __kmp_lock_table_insert(kmp_user_lock_p lck) {
3778  // Assume that kmp_global_lock is held upon entry/exit.
3779  kmp_lock_index_t index;
3780  if (__kmp_user_lock_table.used >= __kmp_user_lock_table.allocated) {
3781  kmp_lock_index_t size;
3782  kmp_user_lock_p *table;
3783  // Reallocate lock table.
3784  if (__kmp_user_lock_table.allocated == 0) {
3785  size = 1024;
3786  } else {
3787  size = __kmp_user_lock_table.allocated * 2;
3788  }
3789  table = (kmp_user_lock_p *)__kmp_allocate(sizeof(kmp_user_lock_p) * size);
3790  KMP_MEMCPY(table + 1, __kmp_user_lock_table.table + 1,
3791  sizeof(kmp_user_lock_p) * (__kmp_user_lock_table.used - 1));
3792  table[0] = (kmp_user_lock_p)__kmp_user_lock_table.table;
3793  // We cannot free the previous table now, since it may be in use by other
3794  // threads. So save the pointer to the previous table in in the first
3795  // element of the new table. All the tables will be organized into a list,
3796  // and could be freed when library shutting down.
3797  __kmp_user_lock_table.table = table;
3798  __kmp_user_lock_table.allocated = size;
3799  }
3800  KMP_DEBUG_ASSERT(__kmp_user_lock_table.used <
3801  __kmp_user_lock_table.allocated);
3802  index = __kmp_user_lock_table.used;
3803  __kmp_user_lock_table.table[index] = lck;
3804  ++__kmp_user_lock_table.used;
3805  return index;
3806 }
3807 
3808 static kmp_user_lock_p __kmp_lock_block_allocate() {
3809  // Assume that kmp_global_lock is held upon entry/exit.
3810  static int last_index = 0;
3811  if ((last_index >= __kmp_num_locks_in_block) || (__kmp_lock_blocks == NULL)) {
3812  // Restart the index.
3813  last_index = 0;
3814  // Need to allocate a new block.
3815  KMP_DEBUG_ASSERT(__kmp_user_lock_size > 0);
3816  size_t space_for_locks = __kmp_user_lock_size * __kmp_num_locks_in_block;
3817  char *buffer =
3818  (char *)__kmp_allocate(space_for_locks + sizeof(kmp_block_of_locks));
3819  // Set up the new block.
3820  kmp_block_of_locks *new_block =
3821  (kmp_block_of_locks *)(&buffer[space_for_locks]);
3822  new_block->next_block = __kmp_lock_blocks;
3823  new_block->locks = (void *)buffer;
3824  // Publish the new block.
3825  KMP_MB();
3826  __kmp_lock_blocks = new_block;
3827  }
3828  kmp_user_lock_p ret = (kmp_user_lock_p)(&(
3829  ((char *)(__kmp_lock_blocks->locks))[last_index * __kmp_user_lock_size]));
3830  last_index++;
3831  return ret;
3832 }
3833 
3834 // Get memory for a lock. It may be freshly allocated memory or reused memory
3835 // from lock pool.
3836 kmp_user_lock_p __kmp_user_lock_allocate(void **user_lock, kmp_int32 gtid,
3837  kmp_lock_flags_t flags) {
3838  kmp_user_lock_p lck;
3839  kmp_lock_index_t index;
3840  KMP_DEBUG_ASSERT(user_lock);
3841 
3842  __kmp_acquire_lock(&__kmp_global_lock, gtid);
3843 
3844  if (__kmp_lock_pool == NULL) {
3845  // Lock pool is empty. Allocate new memory.
3846 
3847  // ANNOTATION: Found no good way to express the syncronisation
3848  // between allocation and usage, so ignore the allocation
3849  ANNOTATE_IGNORE_WRITES_BEGIN();
3850  if (__kmp_num_locks_in_block <= 1) { // Tune this cutoff point.
3851  lck = (kmp_user_lock_p)__kmp_allocate(__kmp_user_lock_size);
3852  } else {
3853  lck = __kmp_lock_block_allocate();
3854  }
3855  ANNOTATE_IGNORE_WRITES_END();
3856 
3857  // Insert lock in the table so that it can be freed in __kmp_cleanup,
3858  // and debugger has info on all allocated locks.
3859  index = __kmp_lock_table_insert(lck);
3860  } else {
3861  // Pick up lock from pool.
3862  lck = __kmp_lock_pool;
3863  index = __kmp_lock_pool->pool.index;
3864  __kmp_lock_pool = __kmp_lock_pool->pool.next;
3865  }
3866 
3867  // We could potentially differentiate between nested and regular locks
3868  // here, and do the lock table lookup for regular locks only.
3869  if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3870  *((kmp_lock_index_t *)user_lock) = index;
3871  } else {
3872  *((kmp_user_lock_p *)user_lock) = lck;
3873  }
3874 
3875  // mark the lock if it is critical section lock.
3876  __kmp_set_user_lock_flags(lck, flags);
3877 
3878  __kmp_release_lock(&__kmp_global_lock, gtid); // AC: TODO move this line upper
3879 
3880  return lck;
3881 }
3882 
3883 // Put lock's memory to pool for reusing.
3884 void __kmp_user_lock_free(void **user_lock, kmp_int32 gtid,
3885  kmp_user_lock_p lck) {
3886  KMP_DEBUG_ASSERT(user_lock != NULL);
3887  KMP_DEBUG_ASSERT(lck != NULL);
3888 
3889  __kmp_acquire_lock(&__kmp_global_lock, gtid);
3890 
3891  lck->pool.next = __kmp_lock_pool;
3892  __kmp_lock_pool = lck;
3893  if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3894  kmp_lock_index_t index = *((kmp_lock_index_t *)user_lock);
3895  KMP_DEBUG_ASSERT(0 < index && index <= __kmp_user_lock_table.used);
3896  lck->pool.index = index;
3897  }
3898 
3899  __kmp_release_lock(&__kmp_global_lock, gtid);
3900 }
3901 
3902 kmp_user_lock_p __kmp_lookup_user_lock(void **user_lock, char const *func) {
3903  kmp_user_lock_p lck = NULL;
3904 
3905  if (__kmp_env_consistency_check) {
3906  if (user_lock == NULL) {
3907  KMP_FATAL(LockIsUninitialized, func);
3908  }
3909  }
3910 
3911  if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3912  kmp_lock_index_t index = *((kmp_lock_index_t *)user_lock);
3913  if (__kmp_env_consistency_check) {
3914  if (!(0 < index && index < __kmp_user_lock_table.used)) {
3915  KMP_FATAL(LockIsUninitialized, func);
3916  }
3917  }
3918  KMP_DEBUG_ASSERT(0 < index && index < __kmp_user_lock_table.used);
3919  KMP_DEBUG_ASSERT(__kmp_user_lock_size > 0);
3920  lck = __kmp_user_lock_table.table[index];
3921  } else {
3922  lck = *((kmp_user_lock_p *)user_lock);
3923  }
3924 
3925  if (__kmp_env_consistency_check) {
3926  if (lck == NULL) {
3927  KMP_FATAL(LockIsUninitialized, func);
3928  }
3929  }
3930 
3931  return lck;
3932 }
3933 
3934 void __kmp_cleanup_user_locks(void) {
3935  // Reset lock pool. Don't worry about lock in the pool--we will free them when
3936  // iterating through lock table (it includes all the locks, dead or alive).
3937  __kmp_lock_pool = NULL;
3938 
3939 #define IS_CRITICAL(lck) \
3940  ((__kmp_get_user_lock_flags_ != NULL) && \
3941  ((*__kmp_get_user_lock_flags_)(lck)&kmp_lf_critical_section))
3942 
3943  // Loop through lock table, free all locks.
3944  // Do not free item [0], it is reserved for lock tables list.
3945  //
3946  // FIXME - we are iterating through a list of (pointers to) objects of type
3947  // union kmp_user_lock, but we have no way of knowing whether the base type is
3948  // currently "pool" or whatever the global user lock type is.
3949  //
3950  // We are relying on the fact that for all of the user lock types
3951  // (except "tas"), the first field in the lock struct is the "initialized"
3952  // field, which is set to the address of the lock object itself when
3953  // the lock is initialized. When the union is of type "pool", the
3954  // first field is a pointer to the next object in the free list, which
3955  // will not be the same address as the object itself.
3956  //
3957  // This means that the check (*__kmp_is_user_lock_initialized_)(lck) will fail
3958  // for "pool" objects on the free list. This must happen as the "location"
3959  // field of real user locks overlaps the "index" field of "pool" objects.
3960  //
3961  // It would be better to run through the free list, and remove all "pool"
3962  // objects from the lock table before executing this loop. However,
3963  // "pool" objects do not always have their index field set (only on
3964  // lin_32e), and I don't want to search the lock table for the address
3965  // of every "pool" object on the free list.
3966  while (__kmp_user_lock_table.used > 1) {
3967  const ident *loc;
3968 
3969  // reduce __kmp_user_lock_table.used before freeing the lock,
3970  // so that state of locks is consistent
3971  kmp_user_lock_p lck =
3972  __kmp_user_lock_table.table[--__kmp_user_lock_table.used];
3973 
3974  if ((__kmp_is_user_lock_initialized_ != NULL) &&
3975  (*__kmp_is_user_lock_initialized_)(lck)) {
3976  // Issue a warning if: KMP_CONSISTENCY_CHECK AND lock is initialized AND
3977  // it is NOT a critical section (user is not responsible for destroying
3978  // criticals) AND we know source location to report.
3979  if (__kmp_env_consistency_check && (!IS_CRITICAL(lck)) &&
3980  ((loc = __kmp_get_user_lock_location(lck)) != NULL) &&
3981  (loc->psource != NULL)) {
3982  kmp_str_loc_t str_loc = __kmp_str_loc_init(loc->psource, false);
3983  KMP_WARNING(CnsLockNotDestroyed, str_loc.file, str_loc.line);
3984  __kmp_str_loc_free(&str_loc);
3985  }
3986 
3987 #ifdef KMP_DEBUG
3988  if (IS_CRITICAL(lck)) {
3989  KA_TRACE(
3990  20,
3991  ("__kmp_cleanup_user_locks: free critical section lock %p (%p)\n",
3992  lck, *(void **)lck));
3993  } else {
3994  KA_TRACE(20, ("__kmp_cleanup_user_locks: free lock %p (%p)\n", lck,
3995  *(void **)lck));
3996  }
3997 #endif // KMP_DEBUG
3998 
3999  // Cleanup internal lock dynamic resources (for drdpa locks particularly).
4000  __kmp_destroy_user_lock(lck);
4001  }
4002 
4003  // Free the lock if block allocation of locks is not used.
4004  if (__kmp_lock_blocks == NULL) {
4005  __kmp_free(lck);
4006  }
4007  }
4008 
4009 #undef IS_CRITICAL
4010 
4011  // delete lock table(s).
4012  kmp_user_lock_p *table_ptr = __kmp_user_lock_table.table;
4013  __kmp_user_lock_table.table = NULL;
4014  __kmp_user_lock_table.allocated = 0;
4015 
4016  while (table_ptr != NULL) {
4017  // In the first element we saved the pointer to the previous
4018  // (smaller) lock table.
4019  kmp_user_lock_p *next = (kmp_user_lock_p *)(table_ptr[0]);
4020  __kmp_free(table_ptr);
4021  table_ptr = next;
4022  }
4023 
4024  // Free buffers allocated for blocks of locks.
4025  kmp_block_of_locks_t *block_ptr = __kmp_lock_blocks;
4026  __kmp_lock_blocks = NULL;
4027 
4028  while (block_ptr != NULL) {
4029  kmp_block_of_locks_t *next = block_ptr->next_block;
4030  __kmp_free(block_ptr->locks);
4031  // *block_ptr itself was allocated at the end of the locks vector.
4032  block_ptr = next;
4033  }
4034 
4035  TCW_4(__kmp_init_user_locks, FALSE);
4036 }
4037 
4038 #endif // KMP_USE_DYNAMIC_LOCK
void set_stdout()
Definition: kmp.h:4262
void open(const char *filename, const char *mode, const char *env_var=nullptr)
Definition: kmp.h:4245
Definition: kmp.h:234
char const * psource
Definition: kmp.h:244