2 * kmp_lock.cpp -- lock-related functions
5 //===----------------------------------------------------------------------===//
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
11 //===----------------------------------------------------------------------===//
21 #include "kmp_wait_release.h"
22 #include "kmp_wrapper_getpid.h"
24 #include "tsan_annotations.h"
27 #include <sys/syscall.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>
42 /* Implement spin locks for internal library use. */
43 /* The algorithm implemented is Lamport's bakery lock [1974]. */
45 void __kmp_validate_locks(void) {
49 /* Check to make sure unsigned arithmetic does wraps properly */
50 x = ~((kmp_uint32)0) - 2;
53 for (i = 0; i < 8; ++i, ++x, ++y) {
54 kmp_uint32 z = (x - y);
58 KMP_ASSERT(offsetof(kmp_base_queuing_lock, tail_id) % 8 == 0);
61 /* ------------------------------------------------------------------------ */
62 /* test and set locks */
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.
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.
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;
76 static inline bool __kmp_is_tas_lock_nestable(kmp_tas_lock_t *lck) {
77 return lck->lk.depth_locked != -1;
80 __forceinline static int
81 __kmp_acquire_tas_lock_timed_template(kmp_tas_lock_t *lck, kmp_int32 gtid) {
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 */
91 kmp_int32 tas_free = KMP_LOCK_FREE(tas);
92 kmp_int32 tas_busy = KMP_LOCK_BUSY(gtid + 1, tas);
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;
101 KMP_FSYNC_PREPARE(lck);
102 KMP_INIT_YIELD(spins);
103 kmp_backoff_t backoff = __kmp_spin_backoff_params;
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;
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);
119 static int __kmp_acquire_tas_lock_with_checks(kmp_tas_lock_t *lck,
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);
126 if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) == gtid)) {
127 KMP_FATAL(LockIsAlreadyOwned, func);
129 return __kmp_acquire_tas_lock(lck, gtid);
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);
143 static int __kmp_test_tas_lock_with_checks(kmp_tas_lock_t *lck,
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);
150 return __kmp_test_tas_lock(lck, gtid);
153 int __kmp_release_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
154 KMP_MB(); /* Flush all pending memory write invalidates. */
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. */
162 return KMP_LOCK_RELEASED;
165 static int __kmp_release_tas_lock_with_checks(kmp_tas_lock_t *lck,
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);
173 if (__kmp_get_tas_lock_owner(lck) == -1) {
174 KMP_FATAL(LockUnsettingFree, func);
176 if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) >= 0) &&
177 (__kmp_get_tas_lock_owner(lck) != gtid)) {
178 KMP_FATAL(LockUnsettingSetByAnother, func);
180 return __kmp_release_tas_lock(lck, gtid);
183 void __kmp_init_tas_lock(kmp_tas_lock_t *lck) {
184 lck->lk.poll = KMP_LOCK_FREE(tas);
187 void __kmp_destroy_tas_lock(kmp_tas_lock_t *lck) { lck->lk.poll = 0; }
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);
195 if (__kmp_get_tas_lock_owner(lck) != -1) {
196 KMP_FATAL(LockStillOwned, func);
198 __kmp_destroy_tas_lock(lck);
201 // nested test and set locks
203 int __kmp_acquire_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
204 KMP_DEBUG_ASSERT(gtid >= 0);
206 if (__kmp_get_tas_lock_owner(lck) == gtid) {
207 lck->lk.depth_locked += 1;
208 return KMP_LOCK_ACQUIRED_NEXT;
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;
217 static int __kmp_acquire_nested_tas_lock_with_checks(kmp_tas_lock_t *lck,
219 char const *const func = "omp_set_nest_lock";
220 if (!__kmp_is_tas_lock_nestable(lck)) {
221 KMP_FATAL(LockSimpleUsedAsNestable, func);
223 return __kmp_acquire_nested_tas_lock(lck, gtid);
226 int __kmp_test_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
229 KMP_DEBUG_ASSERT(gtid >= 0);
231 if (__kmp_get_tas_lock_owner(lck) == gtid) {
232 retval = ++lck->lk.depth_locked;
233 } else if (!__kmp_test_tas_lock(lck, gtid)) {
237 retval = lck->lk.depth_locked = 1;
242 static int __kmp_test_nested_tas_lock_with_checks(kmp_tas_lock_t *lck,
244 char const *const func = "omp_test_nest_lock";
245 if (!__kmp_is_tas_lock_nestable(lck)) {
246 KMP_FATAL(LockSimpleUsedAsNestable, func);
248 return __kmp_test_nested_tas_lock(lck, gtid);
251 int __kmp_release_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) {
252 KMP_DEBUG_ASSERT(gtid >= 0);
255 if (--(lck->lk.depth_locked) == 0) {
256 __kmp_release_tas_lock(lck, gtid);
257 return KMP_LOCK_RELEASED;
259 return KMP_LOCK_STILL_HELD;
262 static int __kmp_release_nested_tas_lock_with_checks(kmp_tas_lock_t *lck,
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);
269 if (__kmp_get_tas_lock_owner(lck) == -1) {
270 KMP_FATAL(LockUnsettingFree, func);
272 if (__kmp_get_tas_lock_owner(lck) != gtid) {
273 KMP_FATAL(LockUnsettingSetByAnother, func);
275 return __kmp_release_nested_tas_lock(lck, gtid);
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
283 void __kmp_destroy_nested_tas_lock(kmp_tas_lock_t *lck) {
284 __kmp_destroy_tas_lock(lck);
285 lck->lk.depth_locked = 0;
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);
293 if (__kmp_get_tas_lock_owner(lck) != -1) {
294 KMP_FATAL(LockStillOwned, func);
296 __kmp_destroy_nested_tas_lock(lck);
301 /* ------------------------------------------------------------------------ */
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).
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;
313 static inline bool __kmp_is_futex_lock_nestable(kmp_futex_lock_t *lck) {
314 return lck->lk.depth_locked != -1;
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;
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 */
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));
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)) {
340 kmp_int32 cond = KMP_LOCK_STRIP(poll_val) & 1;
343 ("__kmp_acquire_futex_lock: lck:%p, T#%d poll_val = 0x%x cond = 0x%x\n",
344 lck, gtid, poll_val, cond));
346 // NOTE: if you try to use the following condition for this branch
348 // if ( poll_val & 1 == 0 )
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.
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))) {
359 ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d can't set bit 0\n",
360 lck, lck->lk.poll, gtid));
363 poll_val |= KMP_LOCK_BUSY(1, futex);
366 ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d bit 0 set\n", lck,
367 lck->lk.poll, gtid));
372 ("__kmp_acquire_futex_lock: lck:%p, T#%d before futex_wait(0x%x)\n",
373 lck, gtid, poll_val));
376 if ((rc = syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAIT, poll_val, NULL,
378 KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p, T#%d futex_wait(0x%x) "
379 "failed (rc=%d errno=%d)\n",
380 lck, gtid, poll_val, rc, errno));
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.
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;
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);
405 static int __kmp_acquire_futex_lock_with_checks(kmp_futex_lock_t *lck,
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);
412 if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) == gtid)) {
413 KMP_FATAL(LockIsAlreadyOwned, func);
415 return __kmp_acquire_futex_lock(lck, gtid);
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);
427 static int __kmp_test_futex_lock_with_checks(kmp_futex_lock_t *lck,
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);
434 return __kmp_test_futex_lock(lck, gtid);
437 int __kmp_release_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
438 KMP_MB(); /* Flush all pending memory write invalidates. */
440 KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d entering\n",
441 lck, lck->lk.poll, gtid));
443 KMP_FSYNC_RELEASING(lck);
444 ANNOTATE_FUTEX_RELEASED(lck);
446 kmp_int32 poll_val = KMP_XCHG_FIXED32(&(lck->lk.poll), KMP_LOCK_FREE(futex));
449 ("__kmp_release_futex_lock: lck:%p, T#%d released poll_val = 0x%x\n",
450 lck, gtid, poll_val));
452 if (KMP_LOCK_STRIP(poll_val) & 1) {
454 ("__kmp_release_futex_lock: lck:%p, T#%d futex_wake 1 thread\n",
456 syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAKE, KMP_LOCK_BUSY(1, futex),
460 KMP_MB(); /* Flush all pending memory write invalidates. */
462 KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d exiting\n", lck,
463 lck->lk.poll, gtid));
466 return KMP_LOCK_RELEASED;
469 static int __kmp_release_futex_lock_with_checks(kmp_futex_lock_t *lck,
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);
477 if (__kmp_get_futex_lock_owner(lck) == -1) {
478 KMP_FATAL(LockUnsettingFree, func);
480 if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) >= 0) &&
481 (__kmp_get_futex_lock_owner(lck) != gtid)) {
482 KMP_FATAL(LockUnsettingSetByAnother, func);
484 return __kmp_release_futex_lock(lck, gtid);
487 void __kmp_init_futex_lock(kmp_futex_lock_t *lck) {
488 TCW_4(lck->lk.poll, KMP_LOCK_FREE(futex));
491 void __kmp_destroy_futex_lock(kmp_futex_lock_t *lck) { lck->lk.poll = 0; }
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);
499 if (__kmp_get_futex_lock_owner(lck) != -1) {
500 KMP_FATAL(LockStillOwned, func);
502 __kmp_destroy_futex_lock(lck);
505 // nested futex locks
507 int __kmp_acquire_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
508 KMP_DEBUG_ASSERT(gtid >= 0);
510 if (__kmp_get_futex_lock_owner(lck) == gtid) {
511 lck->lk.depth_locked += 1;
512 return KMP_LOCK_ACQUIRED_NEXT;
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;
521 static int __kmp_acquire_nested_futex_lock_with_checks(kmp_futex_lock_t *lck,
523 char const *const func = "omp_set_nest_lock";
524 if (!__kmp_is_futex_lock_nestable(lck)) {
525 KMP_FATAL(LockSimpleUsedAsNestable, func);
527 return __kmp_acquire_nested_futex_lock(lck, gtid);
530 int __kmp_test_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
533 KMP_DEBUG_ASSERT(gtid >= 0);
535 if (__kmp_get_futex_lock_owner(lck) == gtid) {
536 retval = ++lck->lk.depth_locked;
537 } else if (!__kmp_test_futex_lock(lck, gtid)) {
541 retval = lck->lk.depth_locked = 1;
546 static int __kmp_test_nested_futex_lock_with_checks(kmp_futex_lock_t *lck,
548 char const *const func = "omp_test_nest_lock";
549 if (!__kmp_is_futex_lock_nestable(lck)) {
550 KMP_FATAL(LockSimpleUsedAsNestable, func);
552 return __kmp_test_nested_futex_lock(lck, gtid);
555 int __kmp_release_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) {
556 KMP_DEBUG_ASSERT(gtid >= 0);
559 if (--(lck->lk.depth_locked) == 0) {
560 __kmp_release_futex_lock(lck, gtid);
561 return KMP_LOCK_RELEASED;
563 return KMP_LOCK_STILL_HELD;
566 static int __kmp_release_nested_futex_lock_with_checks(kmp_futex_lock_t *lck,
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);
573 if (__kmp_get_futex_lock_owner(lck) == -1) {
574 KMP_FATAL(LockUnsettingFree, func);
576 if (__kmp_get_futex_lock_owner(lck) != gtid) {
577 KMP_FATAL(LockUnsettingSetByAnother, func);
579 return __kmp_release_nested_futex_lock(lck, gtid);
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
587 void __kmp_destroy_nested_futex_lock(kmp_futex_lock_t *lck) {
588 __kmp_destroy_futex_lock(lck);
589 lck->lk.depth_locked = 0;
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);
597 if (__kmp_get_futex_lock_owner(lck) != -1) {
598 KMP_FATAL(LockStillOwned, func);
600 __kmp_destroy_nested_futex_lock(lck);
603 #endif // KMP_USE_FUTEX
605 /* ------------------------------------------------------------------------ */
606 /* ticket (bakery) locks */
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) -
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;
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;
624 __forceinline static int
625 __kmp_acquire_ticket_lock_timed_template(kmp_ticket_lock_t *lck,
627 kmp_uint32 my_ticket = std::atomic_fetch_add_explicit(
628 &lck->lk.next_ticket, 1U, std::memory_order_relaxed);
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 */
637 if (std::atomic_load_explicit(&lck->lk.now_serving,
638 std::memory_order_acquire) == my_ticket) {
639 return KMP_LOCK_ACQUIRED_FIRST;
641 KMP_WAIT_PTR(&lck->lk.now_serving, my_ticket, __kmp_bakery_check, lck);
642 return KMP_LOCK_ACQUIRED_FIRST;
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);
651 static int __kmp_acquire_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
653 char const *const func = "omp_set_lock";
655 if (!std::atomic_load_explicit(&lck->lk.initialized,
656 std::memory_order_relaxed)) {
657 KMP_FATAL(LockIsUninitialized, func);
659 if (lck->lk.self != lck) {
660 KMP_FATAL(LockIsUninitialized, func);
662 if (__kmp_is_ticket_lock_nestable(lck)) {
663 KMP_FATAL(LockNestableUsedAsSimple, func);
665 if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) == gtid)) {
666 KMP_FATAL(LockIsAlreadyOwned, func);
669 __kmp_acquire_ticket_lock(lck, gtid);
671 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
672 std::memory_order_relaxed);
673 return KMP_LOCK_ACQUIRED_FIRST;
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);
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)) {
692 static int __kmp_test_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
694 char const *const func = "omp_test_lock";
696 if (!std::atomic_load_explicit(&lck->lk.initialized,
697 std::memory_order_relaxed)) {
698 KMP_FATAL(LockIsUninitialized, func);
700 if (lck->lk.self != lck) {
701 KMP_FATAL(LockIsUninitialized, func);
703 if (__kmp_is_ticket_lock_nestable(lck)) {
704 KMP_FATAL(LockNestableUsedAsSimple, func);
707 int retval = __kmp_test_ticket_lock(lck, gtid);
710 std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1,
711 std::memory_order_relaxed);
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);
722 ANNOTATE_TICKET_RELEASED(lck);
723 std::atomic_fetch_add_explicit(&lck->lk.now_serving, 1U,
724 std::memory_order_release);
727 (kmp_uint32)(__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc));
728 return KMP_LOCK_RELEASED;
731 static int __kmp_release_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
733 char const *const func = "omp_unset_lock";
735 if (!std::atomic_load_explicit(&lck->lk.initialized,
736 std::memory_order_relaxed)) {
737 KMP_FATAL(LockIsUninitialized, func);
739 if (lck->lk.self != lck) {
740 KMP_FATAL(LockIsUninitialized, func);
742 if (__kmp_is_ticket_lock_nestable(lck)) {
743 KMP_FATAL(LockNestableUsedAsSimple, func);
745 if (__kmp_get_ticket_lock_owner(lck) == -1) {
746 KMP_FATAL(LockUnsettingFree, func);
748 if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) >= 0) &&
749 (__kmp_get_ticket_lock_owner(lck) != gtid)) {
750 KMP_FATAL(LockUnsettingSetByAnother, func);
752 std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed);
753 return __kmp_release_ticket_lock(lck, gtid);
756 void __kmp_init_ticket_lock(kmp_ticket_lock_t *lck) {
757 lck->lk.location = NULL;
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);
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);
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);
787 static void __kmp_destroy_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
788 char const *const func = "omp_destroy_lock";
790 if (!std::atomic_load_explicit(&lck->lk.initialized,
791 std::memory_order_relaxed)) {
792 KMP_FATAL(LockIsUninitialized, func);
794 if (lck->lk.self != lck) {
795 KMP_FATAL(LockIsUninitialized, func);
797 if (__kmp_is_ticket_lock_nestable(lck)) {
798 KMP_FATAL(LockNestableUsedAsSimple, func);
800 if (__kmp_get_ticket_lock_owner(lck) != -1) {
801 KMP_FATAL(LockStillOwned, func);
803 __kmp_destroy_ticket_lock(lck);
806 // nested ticket locks
808 int __kmp_acquire_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
809 KMP_DEBUG_ASSERT(gtid >= 0);
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;
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;
826 static int __kmp_acquire_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
828 char const *const func = "omp_set_nest_lock";
830 if (!std::atomic_load_explicit(&lck->lk.initialized,
831 std::memory_order_relaxed)) {
832 KMP_FATAL(LockIsUninitialized, func);
834 if (lck->lk.self != lck) {
835 KMP_FATAL(LockIsUninitialized, func);
837 if (!__kmp_is_ticket_lock_nestable(lck)) {
838 KMP_FATAL(LockSimpleUsedAsNestable, func);
840 return __kmp_acquire_nested_ticket_lock(lck, gtid);
843 int __kmp_test_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
846 KMP_DEBUG_ASSERT(gtid >= 0);
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) +
852 } else if (!__kmp_test_ticket_lock(lck, gtid)) {
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);
864 static int __kmp_test_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
866 char const *const func = "omp_test_nest_lock";
868 if (!std::atomic_load_explicit(&lck->lk.initialized,
869 std::memory_order_relaxed)) {
870 KMP_FATAL(LockIsUninitialized, func);
872 if (lck->lk.self != lck) {
873 KMP_FATAL(LockIsUninitialized, func);
875 if (!__kmp_is_ticket_lock_nestable(lck)) {
876 KMP_FATAL(LockSimpleUsedAsNestable, func);
878 return __kmp_test_nested_ticket_lock(lck, gtid);
881 int __kmp_release_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) {
882 KMP_DEBUG_ASSERT(gtid >= 0);
884 if ((std::atomic_fetch_add_explicit(&lck->lk.depth_locked, -1,
885 std::memory_order_relaxed) -
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;
891 return KMP_LOCK_STILL_HELD;
894 static int __kmp_release_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck,
896 char const *const func = "omp_unset_nest_lock";
898 if (!std::atomic_load_explicit(&lck->lk.initialized,
899 std::memory_order_relaxed)) {
900 KMP_FATAL(LockIsUninitialized, func);
902 if (lck->lk.self != lck) {
903 KMP_FATAL(LockIsUninitialized, func);
905 if (!__kmp_is_ticket_lock_nestable(lck)) {
906 KMP_FATAL(LockSimpleUsedAsNestable, func);
908 if (__kmp_get_ticket_lock_owner(lck) == -1) {
909 KMP_FATAL(LockUnsettingFree, func);
911 if (__kmp_get_ticket_lock_owner(lck) != gtid) {
912 KMP_FATAL(LockUnsettingSetByAnother, func);
914 return __kmp_release_nested_ticket_lock(lck, gtid);
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
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);
931 __kmp_destroy_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
932 char const *const func = "omp_destroy_nest_lock";
934 if (!std::atomic_load_explicit(&lck->lk.initialized,
935 std::memory_order_relaxed)) {
936 KMP_FATAL(LockIsUninitialized, func);
938 if (lck->lk.self != lck) {
939 KMP_FATAL(LockIsUninitialized, func);
941 if (!__kmp_is_ticket_lock_nestable(lck)) {
942 KMP_FATAL(LockSimpleUsedAsNestable, func);
944 if (__kmp_get_ticket_lock_owner(lck) != -1) {
945 KMP_FATAL(LockStillOwned, func);
947 __kmp_destroy_nested_ticket_lock(lck);
950 // access functions to fields which don't exist for all lock kinds.
952 static const ident_t *__kmp_get_ticket_lock_location(kmp_ticket_lock_t *lck) {
953 return lck->lk.location;
956 static void __kmp_set_ticket_lock_location(kmp_ticket_lock_t *lck,
957 const ident_t *loc) {
958 lck->lk.location = loc;
961 static kmp_lock_flags_t __kmp_get_ticket_lock_flags(kmp_ticket_lock_t *lck) {
962 return lck->lk.flags;
965 static void __kmp_set_ticket_lock_flags(kmp_ticket_lock_t *lck,
966 kmp_lock_flags_t flags) {
967 lck->lk.flags = flags;
970 /* ------------------------------------------------------------------------ */
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,
978 h, t h <> t, means lock is held or about to
979 transition, >1 elements on queue
984 Acquire(-1,0) = h ,h h > 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
994 | 0, 0|------- release -------> Error
1018 | h, t|----- acquire, release loopback ---+
1022 +------------------------------------+
1025 #ifdef DEBUG_QUEUING_LOCKS
1027 /* Stuff for circular trace buffer */
1028 #define TRACE_BUF_ELE 1024
1029 static char traces[TRACE_BUF_ELE][128] = {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, \
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) {
1044 __kmp_printf_no_lock("\n__kmp_dump_queuing_lock: TRACE BEGINS HERE! \n");
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;
1053 __kmp_printf_no_lock("\n");
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);
1060 __kmp_printf_no_lock("\t\thead: %d ", lck->lk.head_id);
1062 if (lck->lk.head_id >= 1) {
1063 t = __kmp_threads[lck->lk.head_id - 1]->th.th_next_waiting;
1065 __kmp_printf_no_lock("-> %d ", t);
1066 t = __kmp_threads[t - 1]->th.th_next_waiting;
1069 __kmp_printf_no_lock("; tail: %d ", lck->lk.tail_id);
1070 __kmp_printf_no_lock("\n\n");
1073 #endif /* DEBUG_QUEUING_LOCKS */
1075 static kmp_int32 __kmp_get_queuing_lock_owner(kmp_queuing_lock_t *lck) {
1076 return TCR_4(lck->lk.owner_id) - 1;
1079 static inline bool __kmp_is_queuing_lock_nestable(kmp_queuing_lock_t *lck) {
1080 return lck->lk.depth_locked != -1;
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,
1090 kmp_info_t *this_thr = __kmp_thread_from_gtid(gtid);
1091 volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1092 volatile kmp_int32 *tail_id_p = &lck->lk.tail_id;
1093 volatile kmp_uint32 *spin_here_p;
1094 kmp_int32 need_mf = 1;
1097 ompt_state_t prev_state = ompt_state_undefined;
1101 ("__kmp_acquire_queuing_lock: lck:%p, T#%d entering\n", lck, gtid));
1103 KMP_FSYNC_PREPARE(lck);
1104 KMP_DEBUG_ASSERT(this_thr != NULL);
1105 spin_here_p = &this_thr->th.th_spin_here;
1107 #ifdef DEBUG_QUEUING_LOCKS
1108 TRACE_LOCK(gtid + 1, "acq ent");
1110 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1111 if (this_thr->th.th_next_waiting != 0)
1112 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1114 KMP_DEBUG_ASSERT(!*spin_here_p);
1115 KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1117 /* The following st.rel to spin_here_p needs to precede the cmpxchg.acq to
1118 head_id_p that may follow, not just in execution order, but also in
1119 visibility order. This way, when a releasing thread observes the changes to
1120 the queue by this thread, it can rightly assume that spin_here_p has
1121 already been set to TRUE, so that when it sets spin_here_p to FALSE, it is
1122 not premature. If the releasing thread sets spin_here_p to FALSE before
1123 this thread sets it to TRUE, this thread will hang. */
1124 *spin_here_p = TRUE; /* before enqueuing to prevent race */
1136 #ifdef DEBUG_QUEUING_LOCKS
1138 TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1140 tail = 0; /* to make sure next link asynchronously read is not set
1141 accidentally; this assignment prevents us from entering the
1142 if ( t > 0 ) condition in the enqueued case below, which is not
1143 necessary for this state transition */
1146 /* try (-1,0)->(tid,tid) */
1147 enqueued = KMP_COMPARE_AND_STORE_ACQ64((volatile kmp_int64 *)tail_id_p,
1149 KMP_PACK_64(gtid + 1, gtid + 1));
1150 #ifdef DEBUG_QUEUING_LOCKS
1152 TRACE_LOCK(gtid + 1, "acq enq: (-1,0)->(tid,tid)");
1158 KMP_DEBUG_ASSERT(tail != gtid + 1);
1160 #ifdef DEBUG_QUEUING_LOCKS
1161 TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1168 /* try (h,t) or (h,h)->(h,tid) */
1169 enqueued = KMP_COMPARE_AND_STORE_ACQ32(tail_id_p, tail, gtid + 1);
1171 #ifdef DEBUG_QUEUING_LOCKS
1173 TRACE_LOCK(gtid + 1, "acq enq: (h,t)->(h,tid)");
1178 case 0: /* empty queue */
1180 kmp_int32 grabbed_lock;
1182 #ifdef DEBUG_QUEUING_LOCKS
1184 TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail);
1186 /* try (0,0)->(-1,0) */
1188 /* only legal transition out of head = 0 is head = -1 with no change to
1190 grabbed_lock = KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1);
1194 *spin_here_p = FALSE;
1198 ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: no queuing\n",
1200 #ifdef DEBUG_QUEUING_LOCKS
1201 TRACE_LOCK_HT(gtid + 1, "acq exit: ", head, 0);
1205 if (ompt_enabled.enabled && prev_state != ompt_state_undefined) {
1206 /* change the state before clearing wait_id */
1207 this_thr->th.ompt_thread_info.state = prev_state;
1208 this_thr->th.ompt_thread_info.wait_id = 0;
1212 KMP_FSYNC_ACQUIRED(lck);
1213 return KMP_LOCK_ACQUIRED_FIRST; /* lock holder cannot be on queue */
1220 if (ompt_enabled.enabled && prev_state == ompt_state_undefined) {
1221 /* this thread will spin; set wait_id before entering wait state */
1222 prev_state = this_thr->th.ompt_thread_info.state;
1223 this_thr->th.ompt_thread_info.wait_id = (uint64_t)lck;
1224 this_thr->th.ompt_thread_info.state = ompt_state_wait_lock;
1230 kmp_info_t *tail_thr = __kmp_thread_from_gtid(tail - 1);
1231 KMP_ASSERT(tail_thr != NULL);
1232 tail_thr->th.th_next_waiting = gtid + 1;
1233 /* corresponding wait for this write in release code */
1236 ("__kmp_acquire_queuing_lock: lck:%p, T#%d waiting for lock\n",
1240 // ToDo: Use __kmp_wait_sleep or similar when blocktime != inf
1241 KMP_WAIT(spin_here_p, FALSE, KMP_EQ, lck);
1242 // Synchronize writes to both runtime thread structures
1243 // and writes in user code.
1246 #ifdef DEBUG_QUEUING_LOCKS
1247 TRACE_LOCK(gtid + 1, "acq spin");
1249 if (this_thr->th.th_next_waiting != 0)
1250 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1252 KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1253 KA_TRACE(1000, ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: after "
1254 "waiting on queue\n",
1257 #ifdef DEBUG_QUEUING_LOCKS
1258 TRACE_LOCK(gtid + 1, "acq exit 2");
1262 /* change the state before clearing wait_id */
1263 this_thr->th.ompt_thread_info.state = prev_state;
1264 this_thr->th.ompt_thread_info.wait_id = 0;
1267 /* got lock, we were dequeued by the thread that released lock */
1268 return KMP_LOCK_ACQUIRED_FIRST;
1271 /* Yield if number of threads > number of logical processors */
1272 /* ToDo: Not sure why this should only be in oversubscription case,
1273 maybe should be traditional YIELD_INIT/YIELD_WHEN loop */
1274 KMP_YIELD_OVERSUB();
1276 #ifdef DEBUG_QUEUING_LOCKS
1277 TRACE_LOCK(gtid + 1, "acq retry");
1280 KMP_ASSERT2(0, "should not get here");
1281 return KMP_LOCK_ACQUIRED_FIRST;
1284 int __kmp_acquire_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1285 KMP_DEBUG_ASSERT(gtid >= 0);
1287 int retval = __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid);
1288 ANNOTATE_QUEUING_ACQUIRED(lck);
1292 static int __kmp_acquire_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1294 char const *const func = "omp_set_lock";
1295 if (lck->lk.initialized != lck) {
1296 KMP_FATAL(LockIsUninitialized, func);
1298 if (__kmp_is_queuing_lock_nestable(lck)) {
1299 KMP_FATAL(LockNestableUsedAsSimple, func);
1301 if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1302 KMP_FATAL(LockIsAlreadyOwned, func);
1305 __kmp_acquire_queuing_lock(lck, gtid);
1307 lck->lk.owner_id = gtid + 1;
1308 return KMP_LOCK_ACQUIRED_FIRST;
1311 int __kmp_test_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1312 volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1315 kmp_info_t *this_thr;
1318 KA_TRACE(1000, ("__kmp_test_queuing_lock: T#%d entering\n", gtid));
1319 KMP_DEBUG_ASSERT(gtid >= 0);
1321 this_thr = __kmp_thread_from_gtid(gtid);
1322 KMP_DEBUG_ASSERT(this_thr != NULL);
1323 KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here);
1328 if (head == 0) { /* nobody on queue, nobody holding */
1329 /* try (0,0)->(-1,0) */
1330 if (KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1)) {
1332 ("__kmp_test_queuing_lock: T#%d exiting: holding lock\n", gtid));
1333 KMP_FSYNC_ACQUIRED(lck);
1334 ANNOTATE_QUEUING_ACQUIRED(lck);
1340 ("__kmp_test_queuing_lock: T#%d exiting: without lock\n", gtid));
1344 static int __kmp_test_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1346 char const *const func = "omp_test_lock";
1347 if (lck->lk.initialized != lck) {
1348 KMP_FATAL(LockIsUninitialized, func);
1350 if (__kmp_is_queuing_lock_nestable(lck)) {
1351 KMP_FATAL(LockNestableUsedAsSimple, func);
1354 int retval = __kmp_test_queuing_lock(lck, gtid);
1357 lck->lk.owner_id = gtid + 1;
1362 int __kmp_release_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1363 kmp_info_t *this_thr;
1364 volatile kmp_int32 *head_id_p = &lck->lk.head_id;
1365 volatile kmp_int32 *tail_id_p = &lck->lk.tail_id;
1368 ("__kmp_release_queuing_lock: lck:%p, T#%d entering\n", lck, gtid));
1369 KMP_DEBUG_ASSERT(gtid >= 0);
1370 this_thr = __kmp_thread_from_gtid(gtid);
1371 KMP_DEBUG_ASSERT(this_thr != NULL);
1372 #ifdef DEBUG_QUEUING_LOCKS
1373 TRACE_LOCK(gtid + 1, "rel ent");
1375 if (this_thr->th.th_spin_here)
1376 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1377 if (this_thr->th.th_next_waiting != 0)
1378 __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p);
1380 KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here);
1381 KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0);
1383 KMP_FSYNC_RELEASING(lck);
1384 ANNOTATE_QUEUING_RELEASED(lck);
1393 #ifdef DEBUG_QUEUING_LOCKS
1395 TRACE_LOCK_HT(gtid + 1, "rel read: ", head, tail);
1397 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1399 KMP_DEBUG_ASSERT(head !=
1400 0); /* holding the lock, head must be -1 or queue head */
1402 if (head == -1) { /* nobody on queue */
1403 /* try (-1,0)->(0,0) */
1404 if (KMP_COMPARE_AND_STORE_REL32(head_id_p, -1, 0)) {
1407 ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: queue empty\n",
1409 #ifdef DEBUG_QUEUING_LOCKS
1410 TRACE_LOCK_HT(gtid + 1, "rel exit: ", 0, 0);
1414 /* nothing to do - no other thread is trying to shift blame */
1416 return KMP_LOCK_RELEASED;
1422 if (head == tail) { /* only one thread on the queue */
1423 #ifdef DEBUG_QUEUING_LOCKS
1425 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1427 KMP_DEBUG_ASSERT(head > 0);
1429 /* try (h,h)->(-1,0) */
1430 dequeued = KMP_COMPARE_AND_STORE_REL64(
1431 RCAST(volatile kmp_int64 *, tail_id_p), KMP_PACK_64(head, head),
1432 KMP_PACK_64(-1, 0));
1433 #ifdef DEBUG_QUEUING_LOCKS
1434 TRACE_LOCK(gtid + 1, "rel deq: (h,h)->(-1,0)");
1438 volatile kmp_int32 *waiting_id_p;
1439 kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1);
1440 KMP_DEBUG_ASSERT(head_thr != NULL);
1441 waiting_id_p = &head_thr->th.th_next_waiting;
1443 /* Does this require synchronous reads? */
1444 #ifdef DEBUG_QUEUING_LOCKS
1445 if (head <= 0 || tail <= 0)
1446 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1448 KMP_DEBUG_ASSERT(head > 0 && tail > 0);
1450 /* try (h,t)->(h',t) or (t,t) */
1452 /* make sure enqueuing thread has time to update next waiting thread
1455 KMP_WAIT((volatile kmp_uint32 *)waiting_id_p, 0, KMP_NEQ, NULL);
1456 #ifdef DEBUG_QUEUING_LOCKS
1457 TRACE_LOCK(gtid + 1, "rel deq: (h,t)->(h',t)");
1464 kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1);
1465 KMP_DEBUG_ASSERT(head_thr != NULL);
1467 /* Does this require synchronous reads? */
1468 #ifdef DEBUG_QUEUING_LOCKS
1469 if (head <= 0 || tail <= 0)
1470 __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail);
1472 KMP_DEBUG_ASSERT(head > 0 && tail > 0);
1474 /* For clean code only. Thread not released until next statement prevents
1475 race with acquire code. */
1476 head_thr->th.th_next_waiting = 0;
1477 #ifdef DEBUG_QUEUING_LOCKS
1478 TRACE_LOCK_T(gtid + 1, "rel nw=0 for t=", head);
1482 /* reset spin value */
1483 head_thr->th.th_spin_here = FALSE;
1485 KA_TRACE(1000, ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: after "
1488 #ifdef DEBUG_QUEUING_LOCKS
1489 TRACE_LOCK(gtid + 1, "rel exit 2");
1491 return KMP_LOCK_RELEASED;
1493 /* KMP_CPU_PAUSE(); don't want to make releasing thread hold up acquiring
1496 #ifdef DEBUG_QUEUING_LOCKS
1497 TRACE_LOCK(gtid + 1, "rel retry");
1501 KMP_ASSERT2(0, "should not get here");
1502 return KMP_LOCK_RELEASED;
1505 static int __kmp_release_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1507 char const *const func = "omp_unset_lock";
1508 KMP_MB(); /* in case another processor initialized lock */
1509 if (lck->lk.initialized != lck) {
1510 KMP_FATAL(LockIsUninitialized, func);
1512 if (__kmp_is_queuing_lock_nestable(lck)) {
1513 KMP_FATAL(LockNestableUsedAsSimple, func);
1515 if (__kmp_get_queuing_lock_owner(lck) == -1) {
1516 KMP_FATAL(LockUnsettingFree, func);
1518 if (__kmp_get_queuing_lock_owner(lck) != gtid) {
1519 KMP_FATAL(LockUnsettingSetByAnother, func);
1521 lck->lk.owner_id = 0;
1522 return __kmp_release_queuing_lock(lck, gtid);
1525 void __kmp_init_queuing_lock(kmp_queuing_lock_t *lck) {
1526 lck->lk.location = NULL;
1527 lck->lk.head_id = 0;
1528 lck->lk.tail_id = 0;
1529 lck->lk.next_ticket = 0;
1530 lck->lk.now_serving = 0;
1531 lck->lk.owner_id = 0; // no thread owns the lock.
1532 lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks.
1533 lck->lk.initialized = lck;
1535 KA_TRACE(1000, ("__kmp_init_queuing_lock: lock %p initialized\n", lck));
1538 void __kmp_destroy_queuing_lock(kmp_queuing_lock_t *lck) {
1539 lck->lk.initialized = NULL;
1540 lck->lk.location = NULL;
1541 lck->lk.head_id = 0;
1542 lck->lk.tail_id = 0;
1543 lck->lk.next_ticket = 0;
1544 lck->lk.now_serving = 0;
1545 lck->lk.owner_id = 0;
1546 lck->lk.depth_locked = -1;
1549 static void __kmp_destroy_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
1550 char const *const func = "omp_destroy_lock";
1551 if (lck->lk.initialized != lck) {
1552 KMP_FATAL(LockIsUninitialized, func);
1554 if (__kmp_is_queuing_lock_nestable(lck)) {
1555 KMP_FATAL(LockNestableUsedAsSimple, func);
1557 if (__kmp_get_queuing_lock_owner(lck) != -1) {
1558 KMP_FATAL(LockStillOwned, func);
1560 __kmp_destroy_queuing_lock(lck);
1563 // nested queuing locks
1565 int __kmp_acquire_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1566 KMP_DEBUG_ASSERT(gtid >= 0);
1568 if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1569 lck->lk.depth_locked += 1;
1570 return KMP_LOCK_ACQUIRED_NEXT;
1572 __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid);
1573 ANNOTATE_QUEUING_ACQUIRED(lck);
1575 lck->lk.depth_locked = 1;
1577 lck->lk.owner_id = gtid + 1;
1578 return KMP_LOCK_ACQUIRED_FIRST;
1583 __kmp_acquire_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1585 char const *const func = "omp_set_nest_lock";
1586 if (lck->lk.initialized != lck) {
1587 KMP_FATAL(LockIsUninitialized, func);
1589 if (!__kmp_is_queuing_lock_nestable(lck)) {
1590 KMP_FATAL(LockSimpleUsedAsNestable, func);
1592 return __kmp_acquire_nested_queuing_lock(lck, gtid);
1595 int __kmp_test_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1598 KMP_DEBUG_ASSERT(gtid >= 0);
1600 if (__kmp_get_queuing_lock_owner(lck) == gtid) {
1601 retval = ++lck->lk.depth_locked;
1602 } else if (!__kmp_test_queuing_lock(lck, gtid)) {
1606 retval = lck->lk.depth_locked = 1;
1608 lck->lk.owner_id = gtid + 1;
1613 static int __kmp_test_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1615 char const *const func = "omp_test_nest_lock";
1616 if (lck->lk.initialized != lck) {
1617 KMP_FATAL(LockIsUninitialized, func);
1619 if (!__kmp_is_queuing_lock_nestable(lck)) {
1620 KMP_FATAL(LockSimpleUsedAsNestable, func);
1622 return __kmp_test_nested_queuing_lock(lck, gtid);
1625 int __kmp_release_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
1626 KMP_DEBUG_ASSERT(gtid >= 0);
1629 if (--(lck->lk.depth_locked) == 0) {
1631 lck->lk.owner_id = 0;
1632 __kmp_release_queuing_lock(lck, gtid);
1633 return KMP_LOCK_RELEASED;
1635 return KMP_LOCK_STILL_HELD;
1639 __kmp_release_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck,
1641 char const *const func = "omp_unset_nest_lock";
1642 KMP_MB(); /* in case another processor initialized lock */
1643 if (lck->lk.initialized != lck) {
1644 KMP_FATAL(LockIsUninitialized, func);
1646 if (!__kmp_is_queuing_lock_nestable(lck)) {
1647 KMP_FATAL(LockSimpleUsedAsNestable, func);
1649 if (__kmp_get_queuing_lock_owner(lck) == -1) {
1650 KMP_FATAL(LockUnsettingFree, func);
1652 if (__kmp_get_queuing_lock_owner(lck) != gtid) {
1653 KMP_FATAL(LockUnsettingSetByAnother, func);
1655 return __kmp_release_nested_queuing_lock(lck, gtid);
1658 void __kmp_init_nested_queuing_lock(kmp_queuing_lock_t *lck) {
1659 __kmp_init_queuing_lock(lck);
1660 lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
1663 void __kmp_destroy_nested_queuing_lock(kmp_queuing_lock_t *lck) {
1664 __kmp_destroy_queuing_lock(lck);
1665 lck->lk.depth_locked = 0;
1669 __kmp_destroy_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
1670 char const *const func = "omp_destroy_nest_lock";
1671 if (lck->lk.initialized != lck) {
1672 KMP_FATAL(LockIsUninitialized, func);
1674 if (!__kmp_is_queuing_lock_nestable(lck)) {
1675 KMP_FATAL(LockSimpleUsedAsNestable, func);
1677 if (__kmp_get_queuing_lock_owner(lck) != -1) {
1678 KMP_FATAL(LockStillOwned, func);
1680 __kmp_destroy_nested_queuing_lock(lck);
1683 // access functions to fields which don't exist for all lock kinds.
1685 static const ident_t *__kmp_get_queuing_lock_location(kmp_queuing_lock_t *lck) {
1686 return lck->lk.location;
1689 static void __kmp_set_queuing_lock_location(kmp_queuing_lock_t *lck,
1690 const ident_t *loc) {
1691 lck->lk.location = loc;
1694 static kmp_lock_flags_t __kmp_get_queuing_lock_flags(kmp_queuing_lock_t *lck) {
1695 return lck->lk.flags;
1698 static void __kmp_set_queuing_lock_flags(kmp_queuing_lock_t *lck,
1699 kmp_lock_flags_t flags) {
1700 lck->lk.flags = flags;
1703 #if KMP_USE_ADAPTIVE_LOCKS
1705 /* RTM Adaptive locks */
1707 #if (KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300) || \
1708 (KMP_COMPILER_MSVC && _MSC_VER >= 1700) || \
1709 (KMP_COMPILER_CLANG && (KMP_MSVC_COMPAT || __MINGW32__)) || \
1710 (KMP_COMPILER_GCC && __MINGW32__)
1712 #include <immintrin.h>
1713 #define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT)
1717 // Values from the status register after failed speculation.
1718 #define _XBEGIN_STARTED (~0u)
1719 #define _XABORT_EXPLICIT (1 << 0)
1720 #define _XABORT_RETRY (1 << 1)
1721 #define _XABORT_CONFLICT (1 << 2)
1722 #define _XABORT_CAPACITY (1 << 3)
1723 #define _XABORT_DEBUG (1 << 4)
1724 #define _XABORT_NESTED (1 << 5)
1725 #define _XABORT_CODE(x) ((unsigned char)(((x) >> 24) & 0xFF))
1727 // Aborts for which it's worth trying again immediately
1728 #define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT)
1730 #define STRINGIZE_INTERNAL(arg) #arg
1731 #define STRINGIZE(arg) STRINGIZE_INTERNAL(arg)
1733 // Access to RTM instructions
1734 /*A version of XBegin which returns -1 on speculation, and the value of EAX on
1735 an abort. This is the same definition as the compiler intrinsic that will be
1736 supported at some point. */
1737 static __inline int _xbegin() {
1765 #endif // KMP_ARCH_X86_64
1767 /* Note that %eax must be noted as killed (clobbered), because the XSR is
1768 returned in %eax(%rax) on abort. Other register values are restored, so
1769 don't need to be killed.
1771 We must also mark 'res' as an input and an output, since otherwise
1772 'res=-1' may be dropped as being dead, whereas we do need the assignment on
1773 the successful (i.e., non-abort) path. */
1774 __asm__ volatile("1: .byte 0xC7; .byte 0xF8;\n"
1777 "1: movl %%eax,%0\n"
1779 : "+r"(res)::"memory", "%eax");
1780 #endif // KMP_OS_WINDOWS
1784 /* Transaction end */
1785 static __inline void _xend() {
1793 __asm__ volatile(".byte 0x0f; .byte 0x01; .byte 0xd5" ::: "memory");
1797 /* This is a macro, the argument must be a single byte constant which can be
1798 evaluated by the inline assembler, since it is emitted as a byte into the
1802 #define _xabort(ARG) _asm _emit 0xc6 _asm _emit 0xf8 _asm _emit ARG
1804 #define _xabort(ARG) \
1805 __asm__ volatile(".byte 0xC6; .byte 0xF8; .byte " STRINGIZE(ARG):::"memory");
1808 #endif // KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300
1810 // Statistics is collected for testing purpose
1811 #if KMP_DEBUG_ADAPTIVE_LOCKS
1813 // We accumulate speculative lock statistics when the lock is destroyed. We
1814 // keep locks that haven't been destroyed in the liveLocks list so that we can
1815 // grab their statistics too.
1816 static kmp_adaptive_lock_statistics_t destroyedStats;
1818 // To hold the list of live locks.
1819 static kmp_adaptive_lock_info_t liveLocks;
1821 // A lock so we can safely update the list of locks.
1822 static kmp_bootstrap_lock_t chain_lock =
1823 KMP_BOOTSTRAP_LOCK_INITIALIZER(chain_lock);
1825 // Initialize the list of stats.
1826 void __kmp_init_speculative_stats() {
1827 kmp_adaptive_lock_info_t *lck = &liveLocks;
1829 memset(CCAST(kmp_adaptive_lock_statistics_t *, &(lck->stats)), 0,
1830 sizeof(lck->stats));
1831 lck->stats.next = lck;
1832 lck->stats.prev = lck;
1834 KMP_ASSERT(lck->stats.next->stats.prev == lck);
1835 KMP_ASSERT(lck->stats.prev->stats.next == lck);
1837 __kmp_init_bootstrap_lock(&chain_lock);
1840 // Insert the lock into the circular list
1841 static void __kmp_remember_lock(kmp_adaptive_lock_info_t *lck) {
1842 __kmp_acquire_bootstrap_lock(&chain_lock);
1844 lck->stats.next = liveLocks.stats.next;
1845 lck->stats.prev = &liveLocks;
1847 liveLocks.stats.next = lck;
1848 lck->stats.next->stats.prev = lck;
1850 KMP_ASSERT(lck->stats.next->stats.prev == lck);
1851 KMP_ASSERT(lck->stats.prev->stats.next == lck);
1853 __kmp_release_bootstrap_lock(&chain_lock);
1856 static void __kmp_forget_lock(kmp_adaptive_lock_info_t *lck) {
1857 KMP_ASSERT(lck->stats.next->stats.prev == lck);
1858 KMP_ASSERT(lck->stats.prev->stats.next == lck);
1860 kmp_adaptive_lock_info_t *n = lck->stats.next;
1861 kmp_adaptive_lock_info_t *p = lck->stats.prev;
1867 static void __kmp_zero_speculative_stats(kmp_adaptive_lock_info_t *lck) {
1868 memset(CCAST(kmp_adaptive_lock_statistics_t *, &lck->stats), 0,
1869 sizeof(lck->stats));
1870 __kmp_remember_lock(lck);
1873 static void __kmp_add_stats(kmp_adaptive_lock_statistics_t *t,
1874 kmp_adaptive_lock_info_t *lck) {
1875 kmp_adaptive_lock_statistics_t volatile *s = &lck->stats;
1877 t->nonSpeculativeAcquireAttempts += lck->acquire_attempts;
1878 t->successfulSpeculations += s->successfulSpeculations;
1879 t->hardFailedSpeculations += s->hardFailedSpeculations;
1880 t->softFailedSpeculations += s->softFailedSpeculations;
1881 t->nonSpeculativeAcquires += s->nonSpeculativeAcquires;
1882 t->lemmingYields += s->lemmingYields;
1885 static void __kmp_accumulate_speculative_stats(kmp_adaptive_lock_info_t *lck) {
1886 __kmp_acquire_bootstrap_lock(&chain_lock);
1888 __kmp_add_stats(&destroyedStats, lck);
1889 __kmp_forget_lock(lck);
1891 __kmp_release_bootstrap_lock(&chain_lock);
1894 static float percent(kmp_uint32 count, kmp_uint32 total) {
1895 return (total == 0) ? 0.0 : (100.0 * count) / total;
1898 static FILE *__kmp_open_stats_file() {
1899 if (strcmp(__kmp_speculative_statsfile, "-") == 0)
1902 size_t buffLen = KMP_STRLEN(__kmp_speculative_statsfile) + 20;
1903 char buffer[buffLen];
1904 KMP_SNPRINTF(&buffer[0], buffLen, __kmp_speculative_statsfile,
1905 (kmp_int32)getpid());
1906 FILE *result = fopen(&buffer[0], "w");
1908 // Maybe we should issue a warning here...
1909 return result ? result : stdout;
1912 void __kmp_print_speculative_stats() {
1913 kmp_adaptive_lock_statistics_t total = destroyedStats;
1914 kmp_adaptive_lock_info_t *lck;
1916 for (lck = liveLocks.stats.next; lck != &liveLocks; lck = lck->stats.next) {
1917 __kmp_add_stats(&total, lck);
1919 kmp_adaptive_lock_statistics_t *t = &total;
1920 kmp_uint32 totalSections =
1921 t->nonSpeculativeAcquires + t->successfulSpeculations;
1922 kmp_uint32 totalSpeculations = t->successfulSpeculations +
1923 t->hardFailedSpeculations +
1924 t->softFailedSpeculations;
1925 if (totalSections <= 0)
1928 FILE *statsFile = __kmp_open_stats_file();
1930 fprintf(statsFile, "Speculative lock statistics (all approximate!)\n");
1931 fprintf(statsFile, " Lock parameters: \n"
1932 " max_soft_retries : %10d\n"
1933 " max_badness : %10d\n",
1934 __kmp_adaptive_backoff_params.max_soft_retries,
1935 __kmp_adaptive_backoff_params.max_badness);
1936 fprintf(statsFile, " Non-speculative acquire attempts : %10d\n",
1937 t->nonSpeculativeAcquireAttempts);
1938 fprintf(statsFile, " Total critical sections : %10d\n",
1940 fprintf(statsFile, " Successful speculations : %10d (%5.1f%%)\n",
1941 t->successfulSpeculations,
1942 percent(t->successfulSpeculations, totalSections));
1943 fprintf(statsFile, " Non-speculative acquires : %10d (%5.1f%%)\n",
1944 t->nonSpeculativeAcquires,
1945 percent(t->nonSpeculativeAcquires, totalSections));
1946 fprintf(statsFile, " Lemming yields : %10d\n\n",
1949 fprintf(statsFile, " Speculative acquire attempts : %10d\n",
1951 fprintf(statsFile, " Successes : %10d (%5.1f%%)\n",
1952 t->successfulSpeculations,
1953 percent(t->successfulSpeculations, totalSpeculations));
1954 fprintf(statsFile, " Soft failures : %10d (%5.1f%%)\n",
1955 t->softFailedSpeculations,
1956 percent(t->softFailedSpeculations, totalSpeculations));
1957 fprintf(statsFile, " Hard failures : %10d (%5.1f%%)\n",
1958 t->hardFailedSpeculations,
1959 percent(t->hardFailedSpeculations, totalSpeculations));
1961 if (statsFile != stdout)
1965 #define KMP_INC_STAT(lck, stat) (lck->lk.adaptive.stats.stat++)
1967 #define KMP_INC_STAT(lck, stat)
1969 #endif // KMP_DEBUG_ADAPTIVE_LOCKS
1971 static inline bool __kmp_is_unlocked_queuing_lock(kmp_queuing_lock_t *lck) {
1972 // It is enough to check that the head_id is zero.
1973 // We don't also need to check the tail.
1974 bool res = lck->lk.head_id == 0;
1976 // We need a fence here, since we must ensure that no memory operations
1977 // from later in this thread float above that read.
1978 #if KMP_COMPILER_ICC
1981 __sync_synchronize();
1987 // Functions for manipulating the badness
1988 static __inline void
1989 __kmp_update_badness_after_success(kmp_adaptive_lock_t *lck) {
1990 // Reset the badness to zero so we eagerly try to speculate again
1991 lck->lk.adaptive.badness = 0;
1992 KMP_INC_STAT(lck, successfulSpeculations);
1995 // Create a bit mask with one more set bit.
1996 static __inline void __kmp_step_badness(kmp_adaptive_lock_t *lck) {
1997 kmp_uint32 newBadness = (lck->lk.adaptive.badness << 1) | 1;
1998 if (newBadness > lck->lk.adaptive.max_badness) {
2001 lck->lk.adaptive.badness = newBadness;
2005 // Check whether speculation should be attempted.
2006 static __inline int __kmp_should_speculate(kmp_adaptive_lock_t *lck,
2008 kmp_uint32 badness = lck->lk.adaptive.badness;
2009 kmp_uint32 attempts = lck->lk.adaptive.acquire_attempts;
2010 int res = (attempts & badness) == 0;
2014 // Attempt to acquire only the speculative lock.
2015 // Does not back off to the non-speculative lock.
2016 static int __kmp_test_adaptive_lock_only(kmp_adaptive_lock_t *lck,
2018 int retries = lck->lk.adaptive.max_soft_retries;
2020 // We don't explicitly count the start of speculation, rather we record the
2021 // results (success, hard fail, soft fail). The sum of all of those is the
2022 // total number of times we started speculation since all speculations must
2023 // end one of those ways.
2025 kmp_uint32 status = _xbegin();
2026 // Switch this in to disable actual speculation but exercise at least some
2027 // of the rest of the code. Useful for debugging...
2028 // kmp_uint32 status = _XABORT_NESTED;
2030 if (status == _XBEGIN_STARTED) {
2031 /* We have successfully started speculation. Check that no-one acquired
2032 the lock for real between when we last looked and now. This also gets
2033 the lock cache line into our read-set, which we need so that we'll
2034 abort if anyone later claims it for real. */
2035 if (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) {
2036 // Lock is now visibly acquired, so someone beat us to it. Abort the
2037 // transaction so we'll restart from _xbegin with the failure status.
2039 KMP_ASSERT2(0, "should not get here");
2041 return 1; // Lock has been acquired (speculatively)
2043 // We have aborted, update the statistics
2044 if (status & SOFT_ABORT_MASK) {
2045 KMP_INC_STAT(lck, softFailedSpeculations);
2046 // and loop round to retry.
2048 KMP_INC_STAT(lck, hardFailedSpeculations);
2049 // Give up if we had a hard failure.
2053 } while (retries--); // Loop while we have retries, and didn't fail hard.
2055 // Either we had a hard failure or we didn't succeed softly after
2056 // the full set of attempts, so back off the badness.
2057 __kmp_step_badness(lck);
2061 // Attempt to acquire the speculative lock, or back off to the non-speculative
2062 // one if the speculative lock cannot be acquired.
2063 // We can succeed speculatively, non-speculatively, or fail.
2064 static int __kmp_test_adaptive_lock(kmp_adaptive_lock_t *lck, kmp_int32 gtid) {
2065 // First try to acquire the lock speculatively
2066 if (__kmp_should_speculate(lck, gtid) &&
2067 __kmp_test_adaptive_lock_only(lck, gtid))
2070 // Speculative acquisition failed, so try to acquire it non-speculatively.
2071 // Count the non-speculative acquire attempt
2072 lck->lk.adaptive.acquire_attempts++;
2074 // Use base, non-speculative lock.
2075 if (__kmp_test_queuing_lock(GET_QLK_PTR(lck), gtid)) {
2076 KMP_INC_STAT(lck, nonSpeculativeAcquires);
2077 return 1; // Lock is acquired (non-speculatively)
2079 return 0; // Failed to acquire the lock, it's already visibly locked.
2083 static int __kmp_test_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck,
2085 char const *const func = "omp_test_lock";
2086 if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2087 KMP_FATAL(LockIsUninitialized, func);
2090 int retval = __kmp_test_adaptive_lock(lck, gtid);
2093 lck->lk.qlk.owner_id = gtid + 1;
2098 // Block until we can acquire a speculative, adaptive lock. We check whether we
2099 // should be trying to speculate. If we should be, we check the real lock to see
2100 // if it is free, and, if not, pause without attempting to acquire it until it
2101 // is. Then we try the speculative acquire. This means that although we suffer
2102 // from lemmings a little (because all we can't acquire the lock speculatively
2103 // until the queue of threads waiting has cleared), we don't get into a state
2104 // where we can never acquire the lock speculatively (because we force the queue
2105 // to clear by preventing new arrivals from entering the queue). This does mean
2106 // that when we're trying to break lemmings, the lock is no longer fair. However
2107 // OpenMP makes no guarantee that its locks are fair, so this isn't a real
2109 static void __kmp_acquire_adaptive_lock(kmp_adaptive_lock_t *lck,
2111 if (__kmp_should_speculate(lck, gtid)) {
2112 if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) {
2113 if (__kmp_test_adaptive_lock_only(lck, gtid))
2115 // We tried speculation and failed, so give up.
2117 // We can't try speculation until the lock is free, so we pause here
2118 // (without suspending on the queueing lock, to allow it to drain, then
2119 // try again. All other threads will also see the same result for
2120 // shouldSpeculate, so will be doing the same if they try to claim the
2121 // lock from now on.
2122 while (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) {
2123 KMP_INC_STAT(lck, lemmingYields);
2127 if (__kmp_test_adaptive_lock_only(lck, gtid))
2132 // Speculative acquisition failed, so acquire it non-speculatively.
2133 // Count the non-speculative acquire attempt
2134 lck->lk.adaptive.acquire_attempts++;
2136 __kmp_acquire_queuing_lock_timed_template<FALSE>(GET_QLK_PTR(lck), gtid);
2137 // We have acquired the base lock, so count that.
2138 KMP_INC_STAT(lck, nonSpeculativeAcquires);
2139 ANNOTATE_QUEUING_ACQUIRED(lck);
2142 static void __kmp_acquire_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck,
2144 char const *const func = "omp_set_lock";
2145 if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2146 KMP_FATAL(LockIsUninitialized, func);
2148 if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == gtid) {
2149 KMP_FATAL(LockIsAlreadyOwned, func);
2152 __kmp_acquire_adaptive_lock(lck, gtid);
2154 lck->lk.qlk.owner_id = gtid + 1;
2157 static int __kmp_release_adaptive_lock(kmp_adaptive_lock_t *lck,
2159 if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(
2160 lck))) { // If the lock doesn't look claimed we must be speculating.
2161 // (Or the user's code is buggy and they're releasing without locking;
2162 // if we had XTEST we'd be able to check that case...)
2163 _xend(); // Exit speculation
2164 __kmp_update_badness_after_success(lck);
2165 } else { // Since the lock *is* visibly locked we're not speculating,
2166 // so should use the underlying lock's release scheme.
2167 __kmp_release_queuing_lock(GET_QLK_PTR(lck), gtid);
2169 return KMP_LOCK_RELEASED;
2172 static int __kmp_release_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck,
2174 char const *const func = "omp_unset_lock";
2175 KMP_MB(); /* in case another processor initialized lock */
2176 if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2177 KMP_FATAL(LockIsUninitialized, func);
2179 if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == -1) {
2180 KMP_FATAL(LockUnsettingFree, func);
2182 if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != gtid) {
2183 KMP_FATAL(LockUnsettingSetByAnother, func);
2185 lck->lk.qlk.owner_id = 0;
2186 __kmp_release_adaptive_lock(lck, gtid);
2187 return KMP_LOCK_RELEASED;
2190 static void __kmp_init_adaptive_lock(kmp_adaptive_lock_t *lck) {
2191 __kmp_init_queuing_lock(GET_QLK_PTR(lck));
2192 lck->lk.adaptive.badness = 0;
2193 lck->lk.adaptive.acquire_attempts = 0; // nonSpeculativeAcquireAttempts = 0;
2194 lck->lk.adaptive.max_soft_retries =
2195 __kmp_adaptive_backoff_params.max_soft_retries;
2196 lck->lk.adaptive.max_badness = __kmp_adaptive_backoff_params.max_badness;
2197 #if KMP_DEBUG_ADAPTIVE_LOCKS
2198 __kmp_zero_speculative_stats(&lck->lk.adaptive);
2200 KA_TRACE(1000, ("__kmp_init_adaptive_lock: lock %p initialized\n", lck));
2203 static void __kmp_destroy_adaptive_lock(kmp_adaptive_lock_t *lck) {
2204 #if KMP_DEBUG_ADAPTIVE_LOCKS
2205 __kmp_accumulate_speculative_stats(&lck->lk.adaptive);
2207 __kmp_destroy_queuing_lock(GET_QLK_PTR(lck));
2208 // Nothing needed for the speculative part.
2211 static void __kmp_destroy_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck) {
2212 char const *const func = "omp_destroy_lock";
2213 if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) {
2214 KMP_FATAL(LockIsUninitialized, func);
2216 if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != -1) {
2217 KMP_FATAL(LockStillOwned, func);
2219 __kmp_destroy_adaptive_lock(lck);
2222 #endif // KMP_USE_ADAPTIVE_LOCKS
2224 /* ------------------------------------------------------------------------ */
2225 /* DRDPA ticket locks */
2226 /* "DRDPA" means Dynamically Reconfigurable Distributed Polling Area */
2228 static kmp_int32 __kmp_get_drdpa_lock_owner(kmp_drdpa_lock_t *lck) {
2229 return lck->lk.owner_id - 1;
2232 static inline bool __kmp_is_drdpa_lock_nestable(kmp_drdpa_lock_t *lck) {
2233 return lck->lk.depth_locked != -1;
2236 __forceinline static int
2237 __kmp_acquire_drdpa_lock_timed_template(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2238 kmp_uint64 ticket = KMP_ATOMIC_INC(&lck->lk.next_ticket);
2239 kmp_uint64 mask = lck->lk.mask; // atomic load
2240 std::atomic<kmp_uint64> *polls = lck->lk.polls;
2242 #ifdef USE_LOCK_PROFILE
2243 if (polls[ticket & mask] != ticket)
2244 __kmp_printf("LOCK CONTENTION: %p\n", lck);
2245 /* else __kmp_printf( "." );*/
2246 #endif /* USE_LOCK_PROFILE */
2248 // Now spin-wait, but reload the polls pointer and mask, in case the
2249 // polling area has been reconfigured. Unless it is reconfigured, the
2250 // reloads stay in L1 cache and are cheap.
2252 // Keep this code in sync with KMP_WAIT, in kmp_dispatch.cpp !!!
2253 // The current implementation of KMP_WAIT doesn't allow for mask
2254 // and poll to be re-read every spin iteration.
2256 KMP_FSYNC_PREPARE(lck);
2257 KMP_INIT_YIELD(spins);
2258 while (polls[ticket & mask] < ticket) { // atomic load
2259 KMP_YIELD_OVERSUB_ELSE_SPIN(spins);
2260 // Re-read the mask and the poll pointer from the lock structure.
2262 // Make certain that "mask" is read before "polls" !!!
2264 // If another thread picks reconfigures the polling area and updates their
2265 // values, and we get the new value of mask and the old polls pointer, we
2266 // could access memory beyond the end of the old polling area.
2267 mask = lck->lk.mask; // atomic load
2268 polls = lck->lk.polls; // atomic load
2271 // Critical section starts here
2272 KMP_FSYNC_ACQUIRED(lck);
2273 KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld acquired lock %p\n",
2275 lck->lk.now_serving = ticket; // non-volatile store
2277 // Deallocate a garbage polling area if we know that we are the last
2278 // thread that could possibly access it.
2280 // The >= check is in case __kmp_test_drdpa_lock() allocated the cleanup
2282 if ((lck->lk.old_polls != NULL) && (ticket >= lck->lk.cleanup_ticket)) {
2283 __kmp_free(lck->lk.old_polls);
2284 lck->lk.old_polls = NULL;
2285 lck->lk.cleanup_ticket = 0;
2288 // Check to see if we should reconfigure the polling area.
2289 // If there is still a garbage polling area to be deallocated from a
2290 // previous reconfiguration, let a later thread reconfigure it.
2291 if (lck->lk.old_polls == NULL) {
2292 bool reconfigure = false;
2293 std::atomic<kmp_uint64> *old_polls = polls;
2294 kmp_uint32 num_polls = TCR_4(lck->lk.num_polls);
2296 if (TCR_4(__kmp_nth) >
2297 (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) {
2298 // We are in oversubscription mode. Contract the polling area
2299 // down to a single location, if that hasn't been done already.
2300 if (num_polls > 1) {
2302 num_polls = TCR_4(lck->lk.num_polls);
2305 polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls *
2310 // We are in under/fully subscribed mode. Check the number of
2311 // threads waiting on the lock. The size of the polling area
2312 // should be at least the number of threads waiting.
2313 kmp_uint64 num_waiting = TCR_8(lck->lk.next_ticket) - ticket - 1;
2314 if (num_waiting > num_polls) {
2315 kmp_uint32 old_num_polls = num_polls;
2318 mask = (mask << 1) | 1;
2320 } while (num_polls <= num_waiting);
2322 // Allocate the new polling area, and copy the relevant portion
2323 // of the old polling area to the new area. __kmp_allocate()
2324 // zeroes the memory it allocates, and most of the old area is
2325 // just zero padding, so we only copy the release counters.
2326 polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls *
2329 for (i = 0; i < old_num_polls; i++) {
2330 polls[i].store(old_polls[i]);
2336 // Now write the updated fields back to the lock structure.
2338 // Make certain that "polls" is written before "mask" !!!
2340 // If another thread picks up the new value of mask and the old polls
2341 // pointer , it could access memory beyond the end of the old polling
2344 // On x86, we need memory fences.
2345 KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld reconfiguring "
2346 "lock %p to %d polls\n",
2347 ticket, lck, num_polls));
2349 lck->lk.old_polls = old_polls;
2350 lck->lk.polls = polls; // atomic store
2354 lck->lk.num_polls = num_polls;
2355 lck->lk.mask = mask; // atomic store
2359 // Only after the new polling area and mask have been flushed
2360 // to main memory can we update the cleanup ticket field.
2362 // volatile load / non-volatile store
2363 lck->lk.cleanup_ticket = lck->lk.next_ticket;
2366 return KMP_LOCK_ACQUIRED_FIRST;
2369 int __kmp_acquire_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2370 int retval = __kmp_acquire_drdpa_lock_timed_template(lck, gtid);
2371 ANNOTATE_DRDPA_ACQUIRED(lck);
2375 static int __kmp_acquire_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2377 char const *const func = "omp_set_lock";
2378 if (lck->lk.initialized != lck) {
2379 KMP_FATAL(LockIsUninitialized, func);
2381 if (__kmp_is_drdpa_lock_nestable(lck)) {
2382 KMP_FATAL(LockNestableUsedAsSimple, func);
2384 if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) == gtid)) {
2385 KMP_FATAL(LockIsAlreadyOwned, func);
2388 __kmp_acquire_drdpa_lock(lck, gtid);
2390 lck->lk.owner_id = gtid + 1;
2391 return KMP_LOCK_ACQUIRED_FIRST;
2394 int __kmp_test_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2395 // First get a ticket, then read the polls pointer and the mask.
2396 // The polls pointer must be read before the mask!!! (See above)
2397 kmp_uint64 ticket = lck->lk.next_ticket; // atomic load
2398 std::atomic<kmp_uint64> *polls = lck->lk.polls;
2399 kmp_uint64 mask = lck->lk.mask; // atomic load
2400 if (polls[ticket & mask] == ticket) {
2401 kmp_uint64 next_ticket = ticket + 1;
2402 if (__kmp_atomic_compare_store_acq(&lck->lk.next_ticket, ticket,
2404 KMP_FSYNC_ACQUIRED(lck);
2405 KA_TRACE(1000, ("__kmp_test_drdpa_lock: ticket #%lld acquired lock %p\n",
2407 lck->lk.now_serving = ticket; // non-volatile store
2409 // Since no threads are waiting, there is no possibility that we would
2410 // want to reconfigure the polling area. We might have the cleanup ticket
2411 // value (which says that it is now safe to deallocate old_polls), but
2412 // we'll let a later thread which calls __kmp_acquire_lock do that - this
2413 // routine isn't supposed to block, and we would risk blocks if we called
2414 // __kmp_free() to do the deallocation.
2421 static int __kmp_test_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2423 char const *const func = "omp_test_lock";
2424 if (lck->lk.initialized != lck) {
2425 KMP_FATAL(LockIsUninitialized, func);
2427 if (__kmp_is_drdpa_lock_nestable(lck)) {
2428 KMP_FATAL(LockNestableUsedAsSimple, func);
2431 int retval = __kmp_test_drdpa_lock(lck, gtid);
2434 lck->lk.owner_id = gtid + 1;
2439 int __kmp_release_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2440 // Read the ticket value from the lock data struct, then the polls pointer and
2441 // the mask. The polls pointer must be read before the mask!!! (See above)
2442 kmp_uint64 ticket = lck->lk.now_serving + 1; // non-atomic load
2443 std::atomic<kmp_uint64> *polls = lck->lk.polls; // atomic load
2444 kmp_uint64 mask = lck->lk.mask; // atomic load
2445 KA_TRACE(1000, ("__kmp_release_drdpa_lock: ticket #%lld released lock %p\n",
2447 KMP_FSYNC_RELEASING(lck);
2448 ANNOTATE_DRDPA_RELEASED(lck);
2449 polls[ticket & mask] = ticket; // atomic store
2450 return KMP_LOCK_RELEASED;
2453 static int __kmp_release_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2455 char const *const func = "omp_unset_lock";
2456 KMP_MB(); /* in case another processor initialized lock */
2457 if (lck->lk.initialized != lck) {
2458 KMP_FATAL(LockIsUninitialized, func);
2460 if (__kmp_is_drdpa_lock_nestable(lck)) {
2461 KMP_FATAL(LockNestableUsedAsSimple, func);
2463 if (__kmp_get_drdpa_lock_owner(lck) == -1) {
2464 KMP_FATAL(LockUnsettingFree, func);
2466 if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) >= 0) &&
2467 (__kmp_get_drdpa_lock_owner(lck) != gtid)) {
2468 KMP_FATAL(LockUnsettingSetByAnother, func);
2470 lck->lk.owner_id = 0;
2471 return __kmp_release_drdpa_lock(lck, gtid);
2474 void __kmp_init_drdpa_lock(kmp_drdpa_lock_t *lck) {
2475 lck->lk.location = NULL;
2477 lck->lk.num_polls = 1;
2478 lck->lk.polls = (std::atomic<kmp_uint64> *)__kmp_allocate(
2479 lck->lk.num_polls * sizeof(*(lck->lk.polls)));
2480 lck->lk.cleanup_ticket = 0;
2481 lck->lk.old_polls = NULL;
2482 lck->lk.next_ticket = 0;
2483 lck->lk.now_serving = 0;
2484 lck->lk.owner_id = 0; // no thread owns the lock.
2485 lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks.
2486 lck->lk.initialized = lck;
2488 KA_TRACE(1000, ("__kmp_init_drdpa_lock: lock %p initialized\n", lck));
2491 void __kmp_destroy_drdpa_lock(kmp_drdpa_lock_t *lck) {
2492 lck->lk.initialized = NULL;
2493 lck->lk.location = NULL;
2494 if (lck->lk.polls.load() != NULL) {
2495 __kmp_free(lck->lk.polls.load());
2496 lck->lk.polls = NULL;
2498 if (lck->lk.old_polls != NULL) {
2499 __kmp_free(lck->lk.old_polls);
2500 lck->lk.old_polls = NULL;
2503 lck->lk.num_polls = 0;
2504 lck->lk.cleanup_ticket = 0;
2505 lck->lk.next_ticket = 0;
2506 lck->lk.now_serving = 0;
2507 lck->lk.owner_id = 0;
2508 lck->lk.depth_locked = -1;
2511 static void __kmp_destroy_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) {
2512 char const *const func = "omp_destroy_lock";
2513 if (lck->lk.initialized != lck) {
2514 KMP_FATAL(LockIsUninitialized, func);
2516 if (__kmp_is_drdpa_lock_nestable(lck)) {
2517 KMP_FATAL(LockNestableUsedAsSimple, func);
2519 if (__kmp_get_drdpa_lock_owner(lck) != -1) {
2520 KMP_FATAL(LockStillOwned, func);
2522 __kmp_destroy_drdpa_lock(lck);
2525 // nested drdpa ticket locks
2527 int __kmp_acquire_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2528 KMP_DEBUG_ASSERT(gtid >= 0);
2530 if (__kmp_get_drdpa_lock_owner(lck) == gtid) {
2531 lck->lk.depth_locked += 1;
2532 return KMP_LOCK_ACQUIRED_NEXT;
2534 __kmp_acquire_drdpa_lock_timed_template(lck, gtid);
2535 ANNOTATE_DRDPA_ACQUIRED(lck);
2537 lck->lk.depth_locked = 1;
2539 lck->lk.owner_id = gtid + 1;
2540 return KMP_LOCK_ACQUIRED_FIRST;
2544 static void __kmp_acquire_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2546 char const *const func = "omp_set_nest_lock";
2547 if (lck->lk.initialized != lck) {
2548 KMP_FATAL(LockIsUninitialized, func);
2550 if (!__kmp_is_drdpa_lock_nestable(lck)) {
2551 KMP_FATAL(LockSimpleUsedAsNestable, func);
2553 __kmp_acquire_nested_drdpa_lock(lck, gtid);
2556 int __kmp_test_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2559 KMP_DEBUG_ASSERT(gtid >= 0);
2561 if (__kmp_get_drdpa_lock_owner(lck) == gtid) {
2562 retval = ++lck->lk.depth_locked;
2563 } else if (!__kmp_test_drdpa_lock(lck, gtid)) {
2567 retval = lck->lk.depth_locked = 1;
2569 lck->lk.owner_id = gtid + 1;
2574 static int __kmp_test_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2576 char const *const func = "omp_test_nest_lock";
2577 if (lck->lk.initialized != lck) {
2578 KMP_FATAL(LockIsUninitialized, func);
2580 if (!__kmp_is_drdpa_lock_nestable(lck)) {
2581 KMP_FATAL(LockSimpleUsedAsNestable, func);
2583 return __kmp_test_nested_drdpa_lock(lck, gtid);
2586 int __kmp_release_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) {
2587 KMP_DEBUG_ASSERT(gtid >= 0);
2590 if (--(lck->lk.depth_locked) == 0) {
2592 lck->lk.owner_id = 0;
2593 __kmp_release_drdpa_lock(lck, gtid);
2594 return KMP_LOCK_RELEASED;
2596 return KMP_LOCK_STILL_HELD;
2599 static int __kmp_release_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck,
2601 char const *const func = "omp_unset_nest_lock";
2602 KMP_MB(); /* in case another processor initialized lock */
2603 if (lck->lk.initialized != lck) {
2604 KMP_FATAL(LockIsUninitialized, func);
2606 if (!__kmp_is_drdpa_lock_nestable(lck)) {
2607 KMP_FATAL(LockSimpleUsedAsNestable, func);
2609 if (__kmp_get_drdpa_lock_owner(lck) == -1) {
2610 KMP_FATAL(LockUnsettingFree, func);
2612 if (__kmp_get_drdpa_lock_owner(lck) != gtid) {
2613 KMP_FATAL(LockUnsettingSetByAnother, func);
2615 return __kmp_release_nested_drdpa_lock(lck, gtid);
2618 void __kmp_init_nested_drdpa_lock(kmp_drdpa_lock_t *lck) {
2619 __kmp_init_drdpa_lock(lck);
2620 lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
2623 void __kmp_destroy_nested_drdpa_lock(kmp_drdpa_lock_t *lck) {
2624 __kmp_destroy_drdpa_lock(lck);
2625 lck->lk.depth_locked = 0;
2628 static void __kmp_destroy_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) {
2629 char const *const func = "omp_destroy_nest_lock";
2630 if (lck->lk.initialized != lck) {
2631 KMP_FATAL(LockIsUninitialized, func);
2633 if (!__kmp_is_drdpa_lock_nestable(lck)) {
2634 KMP_FATAL(LockSimpleUsedAsNestable, func);
2636 if (__kmp_get_drdpa_lock_owner(lck) != -1) {
2637 KMP_FATAL(LockStillOwned, func);
2639 __kmp_destroy_nested_drdpa_lock(lck);
2642 // access functions to fields which don't exist for all lock kinds.
2644 static const ident_t *__kmp_get_drdpa_lock_location(kmp_drdpa_lock_t *lck) {
2645 return lck->lk.location;
2648 static void __kmp_set_drdpa_lock_location(kmp_drdpa_lock_t *lck,
2649 const ident_t *loc) {
2650 lck->lk.location = loc;
2653 static kmp_lock_flags_t __kmp_get_drdpa_lock_flags(kmp_drdpa_lock_t *lck) {
2654 return lck->lk.flags;
2657 static void __kmp_set_drdpa_lock_flags(kmp_drdpa_lock_t *lck,
2658 kmp_lock_flags_t flags) {
2659 lck->lk.flags = flags;
2662 // Time stamp counter
2663 #if KMP_ARCH_X86 || KMP_ARCH_X86_64
2664 #define __kmp_tsc() __kmp_hardware_timestamp()
2665 // Runtime's default backoff parameters
2666 kmp_backoff_t __kmp_spin_backoff_params = {1, 4096, 100};
2668 // Use nanoseconds for other platforms
2669 extern kmp_uint64 __kmp_now_nsec();
2670 kmp_backoff_t __kmp_spin_backoff_params = {1, 256, 100};
2671 #define __kmp_tsc() __kmp_now_nsec()
2674 // A useful predicate for dealing with timestamps that may wrap.
2675 // Is a before b? Since the timestamps may wrap, this is asking whether it's
2676 // shorter to go clockwise from a to b around the clock-face, or anti-clockwise.
2677 // Times where going clockwise is less distance than going anti-clockwise
2678 // are in the future, others are in the past. e.g. a = MAX-1, b = MAX+1 (=0),
2679 // then a > b (true) does not mean a reached b; whereas signed(a) = -2,
2680 // signed(b) = 0 captures the actual difference
2681 static inline bool before(kmp_uint64 a, kmp_uint64 b) {
2682 return ((kmp_int64)b - (kmp_int64)a) > 0;
2685 // Truncated binary exponential backoff function
2686 void __kmp_spin_backoff(kmp_backoff_t *boff) {
2687 // We could flatten this loop, but making it a nested loop gives better result
2689 for (i = boff->step; i > 0; i--) {
2690 kmp_uint64 goal = __kmp_tsc() + boff->min_tick;
2693 } while (before(__kmp_tsc(), goal));
2695 boff->step = (boff->step << 1 | 1) & (boff->max_backoff - 1);
2698 #if KMP_USE_DYNAMIC_LOCK
2700 // Direct lock initializers. It simply writes a tag to the low 8 bits of the
2702 static void __kmp_init_direct_lock(kmp_dyna_lock_t *lck,
2703 kmp_dyna_lockseq_t seq) {
2704 TCW_4(*lck, KMP_GET_D_TAG(seq));
2707 ("__kmp_init_direct_lock: initialized direct lock with type#%d\n", seq));
2712 // HLE lock functions - imported from the testbed runtime.
2713 #define HLE_ACQUIRE ".byte 0xf2;"
2714 #define HLE_RELEASE ".byte 0xf3;"
2716 static inline kmp_uint32 swap4(kmp_uint32 volatile *p, kmp_uint32 v) {
2717 __asm__ volatile(HLE_ACQUIRE "xchg %1,%0" : "+r"(v), "+m"(*p) : : "memory");
2721 static void __kmp_destroy_hle_lock(kmp_dyna_lock_t *lck) { TCW_4(*lck, 0); }
2723 static void __kmp_destroy_hle_lock_with_checks(kmp_dyna_lock_t *lck) {
2727 static void __kmp_acquire_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) {
2728 // Use gtid for KMP_LOCK_BUSY if necessary
2729 if (swap4(lck, KMP_LOCK_BUSY(1, hle)) != KMP_LOCK_FREE(hle)) {
2732 while (*(kmp_uint32 volatile *)lck != KMP_LOCK_FREE(hle)) {
2733 for (int i = delay; i != 0; --i)
2735 delay = ((delay << 1) | 1) & 7;
2737 } while (swap4(lck, KMP_LOCK_BUSY(1, hle)) != KMP_LOCK_FREE(hle));
2741 static void __kmp_acquire_hle_lock_with_checks(kmp_dyna_lock_t *lck,
2743 __kmp_acquire_hle_lock(lck, gtid); // TODO: add checks
2746 static int __kmp_release_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) {
2747 __asm__ volatile(HLE_RELEASE "movl %1,%0"
2749 : "r"(KMP_LOCK_FREE(hle))
2751 return KMP_LOCK_RELEASED;
2754 static int __kmp_release_hle_lock_with_checks(kmp_dyna_lock_t *lck,
2756 return __kmp_release_hle_lock(lck, gtid); // TODO: add checks
2759 static int __kmp_test_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) {
2760 return swap4(lck, KMP_LOCK_BUSY(1, hle)) == KMP_LOCK_FREE(hle);
2763 static int __kmp_test_hle_lock_with_checks(kmp_dyna_lock_t *lck,
2765 return __kmp_test_hle_lock(lck, gtid); // TODO: add checks
2768 static void __kmp_init_rtm_lock(kmp_queuing_lock_t *lck) {
2769 __kmp_init_queuing_lock(lck);
2772 static void __kmp_destroy_rtm_lock(kmp_queuing_lock_t *lck) {
2773 __kmp_destroy_queuing_lock(lck);
2776 static void __kmp_destroy_rtm_lock_with_checks(kmp_queuing_lock_t *lck) {
2777 __kmp_destroy_queuing_lock_with_checks(lck);
2780 static void __kmp_acquire_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
2781 unsigned retries = 3, status;
2784 if (status == _XBEGIN_STARTED) {
2785 if (__kmp_is_unlocked_queuing_lock(lck))
2789 if ((status & _XABORT_EXPLICIT) && _XABORT_CODE(status) == 0xff) {
2790 // Wait until lock becomes free
2791 while (!__kmp_is_unlocked_queuing_lock(lck)) {
2794 } else if (!(status & _XABORT_RETRY))
2796 } while (retries--);
2798 // Fall-back non-speculative lock (xchg)
2799 __kmp_acquire_queuing_lock(lck, gtid);
2802 static void __kmp_acquire_rtm_lock_with_checks(kmp_queuing_lock_t *lck,
2804 __kmp_acquire_rtm_lock(lck, gtid);
2807 static int __kmp_release_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
2808 if (__kmp_is_unlocked_queuing_lock(lck)) {
2809 // Releasing from speculation
2812 // Releasing from a real lock
2813 __kmp_release_queuing_lock(lck, gtid);
2815 return KMP_LOCK_RELEASED;
2818 static int __kmp_release_rtm_lock_with_checks(kmp_queuing_lock_t *lck,
2820 return __kmp_release_rtm_lock(lck, gtid);
2823 static int __kmp_test_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) {
2824 unsigned retries = 3, status;
2827 if (status == _XBEGIN_STARTED && __kmp_is_unlocked_queuing_lock(lck)) {
2830 if (!(status & _XABORT_RETRY))
2832 } while (retries--);
2834 return (__kmp_is_unlocked_queuing_lock(lck)) ? 1 : 0;
2837 static int __kmp_test_rtm_lock_with_checks(kmp_queuing_lock_t *lck,
2839 return __kmp_test_rtm_lock(lck, gtid);
2842 #endif // KMP_USE_TSX
2844 // Entry functions for indirect locks (first element of direct lock jump tables)
2845 static void __kmp_init_indirect_lock(kmp_dyna_lock_t *l,
2846 kmp_dyna_lockseq_t tag);
2847 static void __kmp_destroy_indirect_lock(kmp_dyna_lock_t *lock);
2848 static int __kmp_set_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32);
2849 static int __kmp_unset_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32);
2850 static int __kmp_test_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32);
2851 static int __kmp_set_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
2853 static int __kmp_unset_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
2855 static int __kmp_test_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
2858 // Lock function definitions for the union parameter type
2859 #define KMP_FOREACH_LOCK_KIND(m, a) m(ticket, a) m(queuing, a) m(drdpa, a)
2861 #define expand1(lk, op) \
2862 static void __kmp_##op##_##lk##_##lock(kmp_user_lock_p lock) { \
2863 __kmp_##op##_##lk##_##lock(&lock->lk); \
2865 #define expand2(lk, op) \
2866 static int __kmp_##op##_##lk##_##lock(kmp_user_lock_p lock, \
2868 return __kmp_##op##_##lk##_##lock(&lock->lk, gtid); \
2870 #define expand3(lk, op) \
2871 static void __kmp_set_##lk##_##lock_flags(kmp_user_lock_p lock, \
2872 kmp_lock_flags_t flags) { \
2873 __kmp_set_##lk##_lock_flags(&lock->lk, flags); \
2875 #define expand4(lk, op) \
2876 static void __kmp_set_##lk##_##lock_location(kmp_user_lock_p lock, \
2877 const ident_t *loc) { \
2878 __kmp_set_##lk##_lock_location(&lock->lk, loc); \
2881 KMP_FOREACH_LOCK_KIND(expand1, init)
2882 KMP_FOREACH_LOCK_KIND(expand1, init_nested)
2883 KMP_FOREACH_LOCK_KIND(expand1, destroy)
2884 KMP_FOREACH_LOCK_KIND(expand1, destroy_nested)
2885 KMP_FOREACH_LOCK_KIND(expand2, acquire)
2886 KMP_FOREACH_LOCK_KIND(expand2, acquire_nested)
2887 KMP_FOREACH_LOCK_KIND(expand2, release)
2888 KMP_FOREACH_LOCK_KIND(expand2, release_nested)
2889 KMP_FOREACH_LOCK_KIND(expand2, test)
2890 KMP_FOREACH_LOCK_KIND(expand2, test_nested)
2891 KMP_FOREACH_LOCK_KIND(expand3, )
2892 KMP_FOREACH_LOCK_KIND(expand4, )
2899 // Jump tables for the indirect lock functions
2900 // Only fill in the odd entries, that avoids the need to shift out the low bit
2903 #define expand(l, op) 0, __kmp_init_direct_lock,
2904 void (*__kmp_direct_init[])(kmp_dyna_lock_t *, kmp_dyna_lockseq_t) = {
2905 __kmp_init_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, init)};
2908 // destroy functions
2909 #define expand(l, op) 0, (void (*)(kmp_dyna_lock_t *))__kmp_##op##_##l##_lock,
2910 static void (*direct_destroy[])(kmp_dyna_lock_t *) = {
2911 __kmp_destroy_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, destroy)};
2913 #define expand(l, op) \
2914 0, (void (*)(kmp_dyna_lock_t *))__kmp_destroy_##l##_lock_with_checks,
2915 static void (*direct_destroy_check[])(kmp_dyna_lock_t *) = {
2916 __kmp_destroy_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, destroy)};
2919 // set/acquire functions
2920 #define expand(l, op) \
2921 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock,
2922 static int (*direct_set[])(kmp_dyna_lock_t *, kmp_int32) = {
2923 __kmp_set_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, acquire)};
2925 #define expand(l, op) \
2926 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock_with_checks,
2927 static int (*direct_set_check[])(kmp_dyna_lock_t *, kmp_int32) = {
2928 __kmp_set_indirect_lock_with_checks, 0,
2929 KMP_FOREACH_D_LOCK(expand, acquire)};
2932 // unset/release and test functions
2933 #define expand(l, op) \
2934 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock,
2935 static int (*direct_unset[])(kmp_dyna_lock_t *, kmp_int32) = {
2936 __kmp_unset_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, release)};
2937 static int (*direct_test[])(kmp_dyna_lock_t *, kmp_int32) = {
2938 __kmp_test_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, test)};
2940 #define expand(l, op) \
2941 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock_with_checks,
2942 static int (*direct_unset_check[])(kmp_dyna_lock_t *, kmp_int32) = {
2943 __kmp_unset_indirect_lock_with_checks, 0,
2944 KMP_FOREACH_D_LOCK(expand, release)};
2945 static int (*direct_test_check[])(kmp_dyna_lock_t *, kmp_int32) = {
2946 __kmp_test_indirect_lock_with_checks, 0, KMP_FOREACH_D_LOCK(expand, test)};
2949 // Exposes only one set of jump tables (*lock or *lock_with_checks).
2950 void (**__kmp_direct_destroy)(kmp_dyna_lock_t *) = 0;
2951 int (**__kmp_direct_set)(kmp_dyna_lock_t *, kmp_int32) = 0;
2952 int (**__kmp_direct_unset)(kmp_dyna_lock_t *, kmp_int32) = 0;
2953 int (**__kmp_direct_test)(kmp_dyna_lock_t *, kmp_int32) = 0;
2955 // Jump tables for the indirect lock functions
2956 #define expand(l, op) (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock,
2957 void (*__kmp_indirect_init[])(kmp_user_lock_p) = {
2958 KMP_FOREACH_I_LOCK(expand, init)};
2961 #define expand(l, op) (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock,
2962 static void (*indirect_destroy[])(kmp_user_lock_p) = {
2963 KMP_FOREACH_I_LOCK(expand, destroy)};
2965 #define expand(l, op) \
2966 (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock_with_checks,
2967 static void (*indirect_destroy_check[])(kmp_user_lock_p) = {
2968 KMP_FOREACH_I_LOCK(expand, destroy)};
2971 // set/acquire functions
2972 #define expand(l, op) \
2973 (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock,
2974 static int (*indirect_set[])(kmp_user_lock_p,
2975 kmp_int32) = {KMP_FOREACH_I_LOCK(expand, acquire)};
2977 #define expand(l, op) \
2978 (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock_with_checks,
2979 static int (*indirect_set_check[])(kmp_user_lock_p, kmp_int32) = {
2980 KMP_FOREACH_I_LOCK(expand, acquire)};
2983 // unset/release and test functions
2984 #define expand(l, op) \
2985 (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock,
2986 static int (*indirect_unset[])(kmp_user_lock_p, kmp_int32) = {
2987 KMP_FOREACH_I_LOCK(expand, release)};
2988 static int (*indirect_test[])(kmp_user_lock_p,
2989 kmp_int32) = {KMP_FOREACH_I_LOCK(expand, test)};
2991 #define expand(l, op) \
2992 (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock_with_checks,
2993 static int (*indirect_unset_check[])(kmp_user_lock_p, kmp_int32) = {
2994 KMP_FOREACH_I_LOCK(expand, release)};
2995 static int (*indirect_test_check[])(kmp_user_lock_p, kmp_int32) = {
2996 KMP_FOREACH_I_LOCK(expand, test)};
2999 // Exposes only one jump tables (*lock or *lock_with_checks).
3000 void (**__kmp_indirect_destroy)(kmp_user_lock_p) = 0;
3001 int (**__kmp_indirect_set)(kmp_user_lock_p, kmp_int32) = 0;
3002 int (**__kmp_indirect_unset)(kmp_user_lock_p, kmp_int32) = 0;
3003 int (**__kmp_indirect_test)(kmp_user_lock_p, kmp_int32) = 0;
3005 // Lock index table.
3006 kmp_indirect_lock_table_t __kmp_i_lock_table;
3008 // Size of indirect locks.
3009 static kmp_uint32 __kmp_indirect_lock_size[KMP_NUM_I_LOCKS] = {0};
3011 // Jump tables for lock accessor/modifier.
3012 void (*__kmp_indirect_set_location[KMP_NUM_I_LOCKS])(kmp_user_lock_p,
3013 const ident_t *) = {0};
3014 void (*__kmp_indirect_set_flags[KMP_NUM_I_LOCKS])(kmp_user_lock_p,
3015 kmp_lock_flags_t) = {0};
3016 const ident_t *(*__kmp_indirect_get_location[KMP_NUM_I_LOCKS])(
3017 kmp_user_lock_p) = {0};
3018 kmp_lock_flags_t (*__kmp_indirect_get_flags[KMP_NUM_I_LOCKS])(
3019 kmp_user_lock_p) = {0};
3021 // Use different lock pools for different lock types.
3022 static kmp_indirect_lock_t *__kmp_indirect_lock_pool[KMP_NUM_I_LOCKS] = {0};
3024 // User lock allocator for dynamically dispatched indirect locks. Every entry of
3025 // the indirect lock table holds the address and type of the allocated indirect
3026 // lock (kmp_indirect_lock_t), and the size of the table doubles when it is
3027 // full. A destroyed indirect lock object is returned to the reusable pool of
3028 // locks, unique to each lock type.
3029 kmp_indirect_lock_t *__kmp_allocate_indirect_lock(void **user_lock,
3031 kmp_indirect_locktag_t tag) {
3032 kmp_indirect_lock_t *lck;
3033 kmp_lock_index_t idx;
3035 __kmp_acquire_lock(&__kmp_global_lock, gtid);
3037 if (__kmp_indirect_lock_pool[tag] != NULL) {
3038 // Reuse the allocated and destroyed lock object
3039 lck = __kmp_indirect_lock_pool[tag];
3040 if (OMP_LOCK_T_SIZE < sizeof(void *))
3041 idx = lck->lock->pool.index;
3042 __kmp_indirect_lock_pool[tag] = (kmp_indirect_lock_t *)lck->lock->pool.next;
3043 KA_TRACE(20, ("__kmp_allocate_indirect_lock: reusing an existing lock %p\n",
3046 idx = __kmp_i_lock_table.next;
3047 // Check capacity and double the size if it is full
3048 if (idx == __kmp_i_lock_table.size) {
3049 // Double up the space for block pointers
3050 int row = __kmp_i_lock_table.size / KMP_I_LOCK_CHUNK;
3051 kmp_indirect_lock_t **new_table = (kmp_indirect_lock_t **)__kmp_allocate(
3052 2 * row * sizeof(kmp_indirect_lock_t *));
3053 KMP_MEMCPY(new_table, __kmp_i_lock_table.table,
3054 row * sizeof(kmp_indirect_lock_t *));
3055 kmp_indirect_lock_t **old_table = __kmp_i_lock_table.table;
3056 __kmp_i_lock_table.table = new_table;
3057 __kmp_free(old_table);
3058 // Allocate new objects in the new blocks
3059 for (int i = row; i < 2 * row; ++i)
3060 *(__kmp_i_lock_table.table + i) = (kmp_indirect_lock_t *)__kmp_allocate(
3061 KMP_I_LOCK_CHUNK * sizeof(kmp_indirect_lock_t));
3062 __kmp_i_lock_table.size = 2 * idx;
3064 __kmp_i_lock_table.next++;
3065 lck = KMP_GET_I_LOCK(idx);
3066 // Allocate a new base lock object
3067 lck->lock = (kmp_user_lock_p)__kmp_allocate(__kmp_indirect_lock_size[tag]);
3069 ("__kmp_allocate_indirect_lock: allocated a new lock %p\n", lck));
3072 __kmp_release_lock(&__kmp_global_lock, gtid);
3076 if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3077 *((kmp_lock_index_t *)user_lock) = idx
3078 << 1; // indirect lock word must be even
3080 *((kmp_indirect_lock_t **)user_lock) = lck;
3086 // User lock lookup for dynamically dispatched locks.
3087 static __forceinline kmp_indirect_lock_t *
3088 __kmp_lookup_indirect_lock(void **user_lock, const char *func) {
3089 if (__kmp_env_consistency_check) {
3090 kmp_indirect_lock_t *lck = NULL;
3091 if (user_lock == NULL) {
3092 KMP_FATAL(LockIsUninitialized, func);
3094 if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3095 kmp_lock_index_t idx = KMP_EXTRACT_I_INDEX(user_lock);
3096 if (idx >= __kmp_i_lock_table.size) {
3097 KMP_FATAL(LockIsUninitialized, func);
3099 lck = KMP_GET_I_LOCK(idx);
3101 lck = *((kmp_indirect_lock_t **)user_lock);
3104 KMP_FATAL(LockIsUninitialized, func);
3108 if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3109 return KMP_GET_I_LOCK(KMP_EXTRACT_I_INDEX(user_lock));
3111 return *((kmp_indirect_lock_t **)user_lock);
3116 static void __kmp_init_indirect_lock(kmp_dyna_lock_t *lock,
3117 kmp_dyna_lockseq_t seq) {
3118 #if KMP_USE_ADAPTIVE_LOCKS
3119 if (seq == lockseq_adaptive && !__kmp_cpuinfo.rtm) {
3120 KMP_WARNING(AdaptiveNotSupported, "kmp_lockseq_t", "adaptive");
3121 seq = lockseq_queuing;
3125 if (seq == lockseq_rtm && !__kmp_cpuinfo.rtm) {
3126 seq = lockseq_queuing;
3129 kmp_indirect_locktag_t tag = KMP_GET_I_TAG(seq);
3130 kmp_indirect_lock_t *l =
3131 __kmp_allocate_indirect_lock((void **)lock, __kmp_entry_gtid(), tag);
3132 KMP_I_LOCK_FUNC(l, init)(l->lock);
3134 20, ("__kmp_init_indirect_lock: initialized indirect lock with type#%d\n",
3138 static void __kmp_destroy_indirect_lock(kmp_dyna_lock_t *lock) {
3139 kmp_uint32 gtid = __kmp_entry_gtid();
3140 kmp_indirect_lock_t *l =
3141 __kmp_lookup_indirect_lock((void **)lock, "omp_destroy_lock");
3142 KMP_I_LOCK_FUNC(l, destroy)(l->lock);
3143 kmp_indirect_locktag_t tag = l->type;
3145 __kmp_acquire_lock(&__kmp_global_lock, gtid);
3147 // Use the base lock's space to keep the pool chain.
3148 l->lock->pool.next = (kmp_user_lock_p)__kmp_indirect_lock_pool[tag];
3149 if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3150 l->lock->pool.index = KMP_EXTRACT_I_INDEX(lock);
3152 __kmp_indirect_lock_pool[tag] = l;
3154 __kmp_release_lock(&__kmp_global_lock, gtid);
3157 static int __kmp_set_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) {
3158 kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock);
3159 return KMP_I_LOCK_FUNC(l, set)(l->lock, gtid);
3162 static int __kmp_unset_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) {
3163 kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock);
3164 return KMP_I_LOCK_FUNC(l, unset)(l->lock, gtid);
3167 static int __kmp_test_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) {
3168 kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock);
3169 return KMP_I_LOCK_FUNC(l, test)(l->lock, gtid);
3172 static int __kmp_set_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
3174 kmp_indirect_lock_t *l =
3175 __kmp_lookup_indirect_lock((void **)lock, "omp_set_lock");
3176 return KMP_I_LOCK_FUNC(l, set)(l->lock, gtid);
3179 static int __kmp_unset_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
3181 kmp_indirect_lock_t *l =
3182 __kmp_lookup_indirect_lock((void **)lock, "omp_unset_lock");
3183 return KMP_I_LOCK_FUNC(l, unset)(l->lock, gtid);
3186 static int __kmp_test_indirect_lock_with_checks(kmp_dyna_lock_t *lock,
3188 kmp_indirect_lock_t *l =
3189 __kmp_lookup_indirect_lock((void **)lock, "omp_test_lock");
3190 return KMP_I_LOCK_FUNC(l, test)(l->lock, gtid);
3193 kmp_dyna_lockseq_t __kmp_user_lock_seq = lockseq_queuing;
3195 // This is used only in kmp_error.cpp when consistency checking is on.
3196 kmp_int32 __kmp_get_user_lock_owner(kmp_user_lock_p lck, kmp_uint32 seq) {
3199 case lockseq_nested_tas:
3200 return __kmp_get_tas_lock_owner((kmp_tas_lock_t *)lck);
3203 case lockseq_nested_futex:
3204 return __kmp_get_futex_lock_owner((kmp_futex_lock_t *)lck);
3206 case lockseq_ticket:
3207 case lockseq_nested_ticket:
3208 return __kmp_get_ticket_lock_owner((kmp_ticket_lock_t *)lck);
3209 case lockseq_queuing:
3210 case lockseq_nested_queuing:
3211 #if KMP_USE_ADAPTIVE_LOCKS
3212 case lockseq_adaptive:
3214 return __kmp_get_queuing_lock_owner((kmp_queuing_lock_t *)lck);
3216 case lockseq_nested_drdpa:
3217 return __kmp_get_drdpa_lock_owner((kmp_drdpa_lock_t *)lck);
3223 // Initializes data for dynamic user locks.
3224 void __kmp_init_dynamic_user_locks() {
3225 // Initialize jump table for the lock functions
3226 if (__kmp_env_consistency_check) {
3227 __kmp_direct_set = direct_set_check;
3228 __kmp_direct_unset = direct_unset_check;
3229 __kmp_direct_test = direct_test_check;
3230 __kmp_direct_destroy = direct_destroy_check;
3231 __kmp_indirect_set = indirect_set_check;
3232 __kmp_indirect_unset = indirect_unset_check;
3233 __kmp_indirect_test = indirect_test_check;
3234 __kmp_indirect_destroy = indirect_destroy_check;
3236 __kmp_direct_set = direct_set;
3237 __kmp_direct_unset = direct_unset;
3238 __kmp_direct_test = direct_test;
3239 __kmp_direct_destroy = direct_destroy;
3240 __kmp_indirect_set = indirect_set;
3241 __kmp_indirect_unset = indirect_unset;
3242 __kmp_indirect_test = indirect_test;
3243 __kmp_indirect_destroy = indirect_destroy;
3245 // If the user locks have already been initialized, then return. Allow the
3246 // switch between different KMP_CONSISTENCY_CHECK values, but do not allocate
3247 // new lock tables if they have already been allocated.
3248 if (__kmp_init_user_locks)
3251 // Initialize lock index table
3252 __kmp_i_lock_table.size = KMP_I_LOCK_CHUNK;
3253 __kmp_i_lock_table.table =
3254 (kmp_indirect_lock_t **)__kmp_allocate(sizeof(kmp_indirect_lock_t *));
3255 *(__kmp_i_lock_table.table) = (kmp_indirect_lock_t *)__kmp_allocate(
3256 KMP_I_LOCK_CHUNK * sizeof(kmp_indirect_lock_t));
3257 __kmp_i_lock_table.next = 0;
3259 // Indirect lock size
3260 __kmp_indirect_lock_size[locktag_ticket] = sizeof(kmp_ticket_lock_t);
3261 __kmp_indirect_lock_size[locktag_queuing] = sizeof(kmp_queuing_lock_t);
3262 #if KMP_USE_ADAPTIVE_LOCKS
3263 __kmp_indirect_lock_size[locktag_adaptive] = sizeof(kmp_adaptive_lock_t);
3265 __kmp_indirect_lock_size[locktag_drdpa] = sizeof(kmp_drdpa_lock_t);
3267 __kmp_indirect_lock_size[locktag_rtm] = sizeof(kmp_queuing_lock_t);
3269 __kmp_indirect_lock_size[locktag_nested_tas] = sizeof(kmp_tas_lock_t);
3271 __kmp_indirect_lock_size[locktag_nested_futex] = sizeof(kmp_futex_lock_t);
3273 __kmp_indirect_lock_size[locktag_nested_ticket] = sizeof(kmp_ticket_lock_t);
3274 __kmp_indirect_lock_size[locktag_nested_queuing] = sizeof(kmp_queuing_lock_t);
3275 __kmp_indirect_lock_size[locktag_nested_drdpa] = sizeof(kmp_drdpa_lock_t);
3277 // Initialize lock accessor/modifier
3278 #define fill_jumps(table, expand, sep) \
3280 table[locktag##sep##ticket] = expand(ticket); \
3281 table[locktag##sep##queuing] = expand(queuing); \
3282 table[locktag##sep##drdpa] = expand(drdpa); \
3285 #if KMP_USE_ADAPTIVE_LOCKS
3286 #define fill_table(table, expand) \
3288 fill_jumps(table, expand, _); \
3289 table[locktag_adaptive] = expand(queuing); \
3290 fill_jumps(table, expand, _nested_); \
3293 #define fill_table(table, expand) \
3295 fill_jumps(table, expand, _); \
3296 fill_jumps(table, expand, _nested_); \
3298 #endif // KMP_USE_ADAPTIVE_LOCKS
3301 (void (*)(kmp_user_lock_p, const ident_t *)) __kmp_set_##l##_lock_location
3302 fill_table(__kmp_indirect_set_location, expand);
3305 (void (*)(kmp_user_lock_p, kmp_lock_flags_t)) __kmp_set_##l##_lock_flags
3306 fill_table(__kmp_indirect_set_flags, expand);
3309 (const ident_t *(*)(kmp_user_lock_p)) __kmp_get_##l##_lock_location
3310 fill_table(__kmp_indirect_get_location, expand);
3313 (kmp_lock_flags_t(*)(kmp_user_lock_p)) __kmp_get_##l##_lock_flags
3314 fill_table(__kmp_indirect_get_flags, expand);
3317 __kmp_init_user_locks = TRUE;
3320 // Clean up the lock table.
3321 void __kmp_cleanup_indirect_user_locks() {
3325 // Clean up locks in the pools first (they were already destroyed before going
3327 for (k = 0; k < KMP_NUM_I_LOCKS; ++k) {
3328 kmp_indirect_lock_t *l = __kmp_indirect_lock_pool[k];
3330 kmp_indirect_lock_t *ll = l;
3331 l = (kmp_indirect_lock_t *)l->lock->pool.next;
3332 KA_TRACE(20, ("__kmp_cleanup_indirect_user_locks: freeing %p from pool\n",
3334 __kmp_free(ll->lock);
3337 __kmp_indirect_lock_pool[k] = NULL;
3339 // Clean up the remaining undestroyed locks.
3340 for (i = 0; i < __kmp_i_lock_table.next; i++) {
3341 kmp_indirect_lock_t *l = KMP_GET_I_LOCK(i);
3342 if (l->lock != NULL) {
3343 // Locks not destroyed explicitly need to be destroyed here.
3344 KMP_I_LOCK_FUNC(l, destroy)(l->lock);
3347 ("__kmp_cleanup_indirect_user_locks: destroy/freeing %p from table\n",
3349 __kmp_free(l->lock);
3353 for (i = 0; i < __kmp_i_lock_table.size / KMP_I_LOCK_CHUNK; i++)
3354 __kmp_free(__kmp_i_lock_table.table[i]);
3355 __kmp_free(__kmp_i_lock_table.table);
3357 __kmp_init_user_locks = FALSE;
3360 enum kmp_lock_kind __kmp_user_lock_kind = lk_default;
3361 int __kmp_num_locks_in_block = 1; // FIXME - tune this value
3363 #else // KMP_USE_DYNAMIC_LOCK
3365 static void __kmp_init_tas_lock_with_checks(kmp_tas_lock_t *lck) {
3366 __kmp_init_tas_lock(lck);
3369 static void __kmp_init_nested_tas_lock_with_checks(kmp_tas_lock_t *lck) {
3370 __kmp_init_nested_tas_lock(lck);
3374 static void __kmp_init_futex_lock_with_checks(kmp_futex_lock_t *lck) {
3375 __kmp_init_futex_lock(lck);
3378 static void __kmp_init_nested_futex_lock_with_checks(kmp_futex_lock_t *lck) {
3379 __kmp_init_nested_futex_lock(lck);
3383 static int __kmp_is_ticket_lock_initialized(kmp_ticket_lock_t *lck) {
3384 return lck == lck->lk.self;
3387 static void __kmp_init_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
3388 __kmp_init_ticket_lock(lck);
3391 static void __kmp_init_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck) {
3392 __kmp_init_nested_ticket_lock(lck);
3395 static int __kmp_is_queuing_lock_initialized(kmp_queuing_lock_t *lck) {
3396 return lck == lck->lk.initialized;
3399 static void __kmp_init_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
3400 __kmp_init_queuing_lock(lck);
3404 __kmp_init_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) {
3405 __kmp_init_nested_queuing_lock(lck);
3408 #if KMP_USE_ADAPTIVE_LOCKS
3409 static void __kmp_init_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck) {
3410 __kmp_init_adaptive_lock(lck);
3414 static int __kmp_is_drdpa_lock_initialized(kmp_drdpa_lock_t *lck) {
3415 return lck == lck->lk.initialized;
3418 static void __kmp_init_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) {
3419 __kmp_init_drdpa_lock(lck);
3422 static void __kmp_init_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) {
3423 __kmp_init_nested_drdpa_lock(lck);
3427 * They are implemented as a table of function pointers which are set to the
3428 * lock functions of the appropriate kind, once that has been determined. */
3430 enum kmp_lock_kind __kmp_user_lock_kind = lk_default;
3432 size_t __kmp_base_user_lock_size = 0;
3433 size_t __kmp_user_lock_size = 0;
3435 kmp_int32 (*__kmp_get_user_lock_owner_)(kmp_user_lock_p lck) = NULL;
3436 int (*__kmp_acquire_user_lock_with_checks_)(kmp_user_lock_p lck,
3437 kmp_int32 gtid) = NULL;
3439 int (*__kmp_test_user_lock_with_checks_)(kmp_user_lock_p lck,
3440 kmp_int32 gtid) = NULL;
3441 int (*__kmp_release_user_lock_with_checks_)(kmp_user_lock_p lck,
3442 kmp_int32 gtid) = NULL;
3443 void (*__kmp_init_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL;
3444 void (*__kmp_destroy_user_lock_)(kmp_user_lock_p lck) = NULL;
3445 void (*__kmp_destroy_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL;
3446 int (*__kmp_acquire_nested_user_lock_with_checks_)(kmp_user_lock_p lck,
3447 kmp_int32 gtid) = NULL;
3449 int (*__kmp_test_nested_user_lock_with_checks_)(kmp_user_lock_p lck,
3450 kmp_int32 gtid) = NULL;
3451 int (*__kmp_release_nested_user_lock_with_checks_)(kmp_user_lock_p lck,
3452 kmp_int32 gtid) = NULL;
3453 void (*__kmp_init_nested_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL;
3454 void (*__kmp_destroy_nested_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL;
3456 int (*__kmp_is_user_lock_initialized_)(kmp_user_lock_p lck) = NULL;
3457 const ident_t *(*__kmp_get_user_lock_location_)(kmp_user_lock_p lck) = NULL;
3458 void (*__kmp_set_user_lock_location_)(kmp_user_lock_p lck,
3459 const ident_t *loc) = NULL;
3460 kmp_lock_flags_t (*__kmp_get_user_lock_flags_)(kmp_user_lock_p lck) = NULL;
3461 void (*__kmp_set_user_lock_flags_)(kmp_user_lock_p lck,
3462 kmp_lock_flags_t flags) = NULL;
3464 void __kmp_set_user_lock_vptrs(kmp_lock_kind_t user_lock_kind) {
3465 switch (user_lock_kind) {
3471 __kmp_base_user_lock_size = sizeof(kmp_base_tas_lock_t);
3472 __kmp_user_lock_size = sizeof(kmp_tas_lock_t);
3474 __kmp_get_user_lock_owner_ =
3475 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_tas_lock_owner);
3477 if (__kmp_env_consistency_check) {
3478 KMP_BIND_USER_LOCK_WITH_CHECKS(tas);
3479 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(tas);
3481 KMP_BIND_USER_LOCK(tas);
3482 KMP_BIND_NESTED_USER_LOCK(tas);
3485 __kmp_destroy_user_lock_ =
3486 (void (*)(kmp_user_lock_p))(&__kmp_destroy_tas_lock);
3488 __kmp_is_user_lock_initialized_ = (int (*)(kmp_user_lock_p))NULL;
3490 __kmp_get_user_lock_location_ = (const ident_t *(*)(kmp_user_lock_p))NULL;
3492 __kmp_set_user_lock_location_ =
3493 (void (*)(kmp_user_lock_p, const ident_t *))NULL;
3495 __kmp_get_user_lock_flags_ = (kmp_lock_flags_t(*)(kmp_user_lock_p))NULL;
3497 __kmp_set_user_lock_flags_ =
3498 (void (*)(kmp_user_lock_p, kmp_lock_flags_t))NULL;
3504 __kmp_base_user_lock_size = sizeof(kmp_base_futex_lock_t);
3505 __kmp_user_lock_size = sizeof(kmp_futex_lock_t);
3507 __kmp_get_user_lock_owner_ =
3508 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_futex_lock_owner);
3510 if (__kmp_env_consistency_check) {
3511 KMP_BIND_USER_LOCK_WITH_CHECKS(futex);
3512 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(futex);
3514 KMP_BIND_USER_LOCK(futex);
3515 KMP_BIND_NESTED_USER_LOCK(futex);
3518 __kmp_destroy_user_lock_ =
3519 (void (*)(kmp_user_lock_p))(&__kmp_destroy_futex_lock);
3521 __kmp_is_user_lock_initialized_ = (int (*)(kmp_user_lock_p))NULL;
3523 __kmp_get_user_lock_location_ = (const ident_t *(*)(kmp_user_lock_p))NULL;
3525 __kmp_set_user_lock_location_ =
3526 (void (*)(kmp_user_lock_p, const ident_t *))NULL;
3528 __kmp_get_user_lock_flags_ = (kmp_lock_flags_t(*)(kmp_user_lock_p))NULL;
3530 __kmp_set_user_lock_flags_ =
3531 (void (*)(kmp_user_lock_p, kmp_lock_flags_t))NULL;
3534 #endif // KMP_USE_FUTEX
3537 __kmp_base_user_lock_size = sizeof(kmp_base_ticket_lock_t);
3538 __kmp_user_lock_size = sizeof(kmp_ticket_lock_t);
3540 __kmp_get_user_lock_owner_ =
3541 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_owner);
3543 if (__kmp_env_consistency_check) {
3544 KMP_BIND_USER_LOCK_WITH_CHECKS(ticket);
3545 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(ticket);
3547 KMP_BIND_USER_LOCK(ticket);
3548 KMP_BIND_NESTED_USER_LOCK(ticket);
3551 __kmp_destroy_user_lock_ =
3552 (void (*)(kmp_user_lock_p))(&__kmp_destroy_ticket_lock);
3554 __kmp_is_user_lock_initialized_ =
3555 (int (*)(kmp_user_lock_p))(&__kmp_is_ticket_lock_initialized);
3557 __kmp_get_user_lock_location_ =
3558 (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_location);
3560 __kmp_set_user_lock_location_ = (void (*)(
3561 kmp_user_lock_p, const ident_t *))(&__kmp_set_ticket_lock_location);
3563 __kmp_get_user_lock_flags_ =
3564 (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_flags);
3566 __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))(
3567 &__kmp_set_ticket_lock_flags);
3571 __kmp_base_user_lock_size = sizeof(kmp_base_queuing_lock_t);
3572 __kmp_user_lock_size = sizeof(kmp_queuing_lock_t);
3574 __kmp_get_user_lock_owner_ =
3575 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_owner);
3577 if (__kmp_env_consistency_check) {
3578 KMP_BIND_USER_LOCK_WITH_CHECKS(queuing);
3579 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(queuing);
3581 KMP_BIND_USER_LOCK(queuing);
3582 KMP_BIND_NESTED_USER_LOCK(queuing);
3585 __kmp_destroy_user_lock_ =
3586 (void (*)(kmp_user_lock_p))(&__kmp_destroy_queuing_lock);
3588 __kmp_is_user_lock_initialized_ =
3589 (int (*)(kmp_user_lock_p))(&__kmp_is_queuing_lock_initialized);
3591 __kmp_get_user_lock_location_ =
3592 (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_location);
3594 __kmp_set_user_lock_location_ = (void (*)(
3595 kmp_user_lock_p, const ident_t *))(&__kmp_set_queuing_lock_location);
3597 __kmp_get_user_lock_flags_ =
3598 (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_flags);
3600 __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))(
3601 &__kmp_set_queuing_lock_flags);
3604 #if KMP_USE_ADAPTIVE_LOCKS
3606 __kmp_base_user_lock_size = sizeof(kmp_base_adaptive_lock_t);
3607 __kmp_user_lock_size = sizeof(kmp_adaptive_lock_t);
3609 __kmp_get_user_lock_owner_ =
3610 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_owner);
3612 if (__kmp_env_consistency_check) {
3613 KMP_BIND_USER_LOCK_WITH_CHECKS(adaptive);
3615 KMP_BIND_USER_LOCK(adaptive);
3618 __kmp_destroy_user_lock_ =
3619 (void (*)(kmp_user_lock_p))(&__kmp_destroy_adaptive_lock);
3621 __kmp_is_user_lock_initialized_ =
3622 (int (*)(kmp_user_lock_p))(&__kmp_is_queuing_lock_initialized);
3624 __kmp_get_user_lock_location_ =
3625 (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_location);
3627 __kmp_set_user_lock_location_ = (void (*)(
3628 kmp_user_lock_p, const ident_t *))(&__kmp_set_queuing_lock_location);
3630 __kmp_get_user_lock_flags_ =
3631 (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_flags);
3633 __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))(
3634 &__kmp_set_queuing_lock_flags);
3637 #endif // KMP_USE_ADAPTIVE_LOCKS
3640 __kmp_base_user_lock_size = sizeof(kmp_base_drdpa_lock_t);
3641 __kmp_user_lock_size = sizeof(kmp_drdpa_lock_t);
3643 __kmp_get_user_lock_owner_ =
3644 (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_owner);
3646 if (__kmp_env_consistency_check) {
3647 KMP_BIND_USER_LOCK_WITH_CHECKS(drdpa);
3648 KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(drdpa);
3650 KMP_BIND_USER_LOCK(drdpa);
3651 KMP_BIND_NESTED_USER_LOCK(drdpa);
3654 __kmp_destroy_user_lock_ =
3655 (void (*)(kmp_user_lock_p))(&__kmp_destroy_drdpa_lock);
3657 __kmp_is_user_lock_initialized_ =
3658 (int (*)(kmp_user_lock_p))(&__kmp_is_drdpa_lock_initialized);
3660 __kmp_get_user_lock_location_ =
3661 (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_location);
3663 __kmp_set_user_lock_location_ = (void (*)(
3664 kmp_user_lock_p, const ident_t *))(&__kmp_set_drdpa_lock_location);
3666 __kmp_get_user_lock_flags_ =
3667 (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_flags);
3669 __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))(
3670 &__kmp_set_drdpa_lock_flags);
3675 // ----------------------------------------------------------------------------
3676 // User lock table & lock allocation
3678 kmp_lock_table_t __kmp_user_lock_table = {1, 0, NULL};
3679 kmp_user_lock_p __kmp_lock_pool = NULL;
3681 // Lock block-allocation support.
3682 kmp_block_of_locks *__kmp_lock_blocks = NULL;
3683 int __kmp_num_locks_in_block = 1; // FIXME - tune this value
3685 static kmp_lock_index_t __kmp_lock_table_insert(kmp_user_lock_p lck) {
3686 // Assume that kmp_global_lock is held upon entry/exit.
3687 kmp_lock_index_t index;
3688 if (__kmp_user_lock_table.used >= __kmp_user_lock_table.allocated) {
3689 kmp_lock_index_t size;
3690 kmp_user_lock_p *table;
3691 // Reallocate lock table.
3692 if (__kmp_user_lock_table.allocated == 0) {
3695 size = __kmp_user_lock_table.allocated * 2;
3697 table = (kmp_user_lock_p *)__kmp_allocate(sizeof(kmp_user_lock_p) * size);
3698 KMP_MEMCPY(table + 1, __kmp_user_lock_table.table + 1,
3699 sizeof(kmp_user_lock_p) * (__kmp_user_lock_table.used - 1));
3700 table[0] = (kmp_user_lock_p)__kmp_user_lock_table.table;
3701 // We cannot free the previous table now, since it may be in use by other
3702 // threads. So save the pointer to the previous table in in the first
3703 // element of the new table. All the tables will be organized into a list,
3704 // and could be freed when library shutting down.
3705 __kmp_user_lock_table.table = table;
3706 __kmp_user_lock_table.allocated = size;
3708 KMP_DEBUG_ASSERT(__kmp_user_lock_table.used <
3709 __kmp_user_lock_table.allocated);
3710 index = __kmp_user_lock_table.used;
3711 __kmp_user_lock_table.table[index] = lck;
3712 ++__kmp_user_lock_table.used;
3716 static kmp_user_lock_p __kmp_lock_block_allocate() {
3717 // Assume that kmp_global_lock is held upon entry/exit.
3718 static int last_index = 0;
3719 if ((last_index >= __kmp_num_locks_in_block) || (__kmp_lock_blocks == NULL)) {
3720 // Restart the index.
3722 // Need to allocate a new block.
3723 KMP_DEBUG_ASSERT(__kmp_user_lock_size > 0);
3724 size_t space_for_locks = __kmp_user_lock_size * __kmp_num_locks_in_block;
3726 (char *)__kmp_allocate(space_for_locks + sizeof(kmp_block_of_locks));
3727 // Set up the new block.
3728 kmp_block_of_locks *new_block =
3729 (kmp_block_of_locks *)(&buffer[space_for_locks]);
3730 new_block->next_block = __kmp_lock_blocks;
3731 new_block->locks = (void *)buffer;
3732 // Publish the new block.
3734 __kmp_lock_blocks = new_block;
3736 kmp_user_lock_p ret = (kmp_user_lock_p)(&(
3737 ((char *)(__kmp_lock_blocks->locks))[last_index * __kmp_user_lock_size]));
3742 // Get memory for a lock. It may be freshly allocated memory or reused memory
3744 kmp_user_lock_p __kmp_user_lock_allocate(void **user_lock, kmp_int32 gtid,
3745 kmp_lock_flags_t flags) {
3746 kmp_user_lock_p lck;
3747 kmp_lock_index_t index;
3748 KMP_DEBUG_ASSERT(user_lock);
3750 __kmp_acquire_lock(&__kmp_global_lock, gtid);
3752 if (__kmp_lock_pool == NULL) {
3753 // Lock pool is empty. Allocate new memory.
3755 // ANNOTATION: Found no good way to express the syncronisation
3756 // between allocation and usage, so ignore the allocation
3757 ANNOTATE_IGNORE_WRITES_BEGIN();
3758 if (__kmp_num_locks_in_block <= 1) { // Tune this cutoff point.
3759 lck = (kmp_user_lock_p)__kmp_allocate(__kmp_user_lock_size);
3761 lck = __kmp_lock_block_allocate();
3763 ANNOTATE_IGNORE_WRITES_END();
3765 // Insert lock in the table so that it can be freed in __kmp_cleanup,
3766 // and debugger has info on all allocated locks.
3767 index = __kmp_lock_table_insert(lck);
3769 // Pick up lock from pool.
3770 lck = __kmp_lock_pool;
3771 index = __kmp_lock_pool->pool.index;
3772 __kmp_lock_pool = __kmp_lock_pool->pool.next;
3775 // We could potentially differentiate between nested and regular locks
3776 // here, and do the lock table lookup for regular locks only.
3777 if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3778 *((kmp_lock_index_t *)user_lock) = index;
3780 *((kmp_user_lock_p *)user_lock) = lck;
3783 // mark the lock if it is critical section lock.
3784 __kmp_set_user_lock_flags(lck, flags);
3786 __kmp_release_lock(&__kmp_global_lock, gtid); // AC: TODO move this line upper
3791 // Put lock's memory to pool for reusing.
3792 void __kmp_user_lock_free(void **user_lock, kmp_int32 gtid,
3793 kmp_user_lock_p lck) {
3794 KMP_DEBUG_ASSERT(user_lock != NULL);
3795 KMP_DEBUG_ASSERT(lck != NULL);
3797 __kmp_acquire_lock(&__kmp_global_lock, gtid);
3799 lck->pool.next = __kmp_lock_pool;
3800 __kmp_lock_pool = lck;
3801 if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3802 kmp_lock_index_t index = *((kmp_lock_index_t *)user_lock);
3803 KMP_DEBUG_ASSERT(0 < index && index <= __kmp_user_lock_table.used);
3804 lck->pool.index = index;
3807 __kmp_release_lock(&__kmp_global_lock, gtid);
3810 kmp_user_lock_p __kmp_lookup_user_lock(void **user_lock, char const *func) {
3811 kmp_user_lock_p lck = NULL;
3813 if (__kmp_env_consistency_check) {
3814 if (user_lock == NULL) {
3815 KMP_FATAL(LockIsUninitialized, func);
3819 if (OMP_LOCK_T_SIZE < sizeof(void *)) {
3820 kmp_lock_index_t index = *((kmp_lock_index_t *)user_lock);
3821 if (__kmp_env_consistency_check) {
3822 if (!(0 < index && index < __kmp_user_lock_table.used)) {
3823 KMP_FATAL(LockIsUninitialized, func);
3826 KMP_DEBUG_ASSERT(0 < index && index < __kmp_user_lock_table.used);
3827 KMP_DEBUG_ASSERT(__kmp_user_lock_size > 0);
3828 lck = __kmp_user_lock_table.table[index];
3830 lck = *((kmp_user_lock_p *)user_lock);
3833 if (__kmp_env_consistency_check) {
3835 KMP_FATAL(LockIsUninitialized, func);
3842 void __kmp_cleanup_user_locks(void) {
3843 // Reset lock pool. Don't worry about lock in the pool--we will free them when
3844 // iterating through lock table (it includes all the locks, dead or alive).
3845 __kmp_lock_pool = NULL;
3847 #define IS_CRITICAL(lck) \
3848 ((__kmp_get_user_lock_flags_ != NULL) && \
3849 ((*__kmp_get_user_lock_flags_)(lck)&kmp_lf_critical_section))
3851 // Loop through lock table, free all locks.
3852 // Do not free item [0], it is reserved for lock tables list.
3854 // FIXME - we are iterating through a list of (pointers to) objects of type
3855 // union kmp_user_lock, but we have no way of knowing whether the base type is
3856 // currently "pool" or whatever the global user lock type is.
3858 // We are relying on the fact that for all of the user lock types
3859 // (except "tas"), the first field in the lock struct is the "initialized"
3860 // field, which is set to the address of the lock object itself when
3861 // the lock is initialized. When the union is of type "pool", the
3862 // first field is a pointer to the next object in the free list, which
3863 // will not be the same address as the object itself.
3865 // This means that the check (*__kmp_is_user_lock_initialized_)(lck) will fail
3866 // for "pool" objects on the free list. This must happen as the "location"
3867 // field of real user locks overlaps the "index" field of "pool" objects.
3869 // It would be better to run through the free list, and remove all "pool"
3870 // objects from the lock table before executing this loop. However,
3871 // "pool" objects do not always have their index field set (only on
3872 // lin_32e), and I don't want to search the lock table for the address
3873 // of every "pool" object on the free list.
3874 while (__kmp_user_lock_table.used > 1) {
3877 // reduce __kmp_user_lock_table.used before freeing the lock,
3878 // so that state of locks is consistent
3879 kmp_user_lock_p lck =
3880 __kmp_user_lock_table.table[--__kmp_user_lock_table.used];
3882 if ((__kmp_is_user_lock_initialized_ != NULL) &&
3883 (*__kmp_is_user_lock_initialized_)(lck)) {
3884 // Issue a warning if: KMP_CONSISTENCY_CHECK AND lock is initialized AND
3885 // it is NOT a critical section (user is not responsible for destroying
3886 // criticals) AND we know source location to report.
3887 if (__kmp_env_consistency_check && (!IS_CRITICAL(lck)) &&
3888 ((loc = __kmp_get_user_lock_location(lck)) != NULL) &&
3889 (loc->psource != NULL)) {
3890 kmp_str_loc_t str_loc = __kmp_str_loc_init(loc->psource, 0);
3891 KMP_WARNING(CnsLockNotDestroyed, str_loc.file, str_loc.line);
3892 __kmp_str_loc_free(&str_loc);
3896 if (IS_CRITICAL(lck)) {
3899 ("__kmp_cleanup_user_locks: free critical section lock %p (%p)\n",
3900 lck, *(void **)lck));
3902 KA_TRACE(20, ("__kmp_cleanup_user_locks: free lock %p (%p)\n", lck,
3907 // Cleanup internal lock dynamic resources (for drdpa locks particularly).
3908 __kmp_destroy_user_lock(lck);
3911 // Free the lock if block allocation of locks is not used.
3912 if (__kmp_lock_blocks == NULL) {
3919 // delete lock table(s).
3920 kmp_user_lock_p *table_ptr = __kmp_user_lock_table.table;
3921 __kmp_user_lock_table.table = NULL;
3922 __kmp_user_lock_table.allocated = 0;
3924 while (table_ptr != NULL) {
3925 // In the first element we saved the pointer to the previous
3926 // (smaller) lock table.
3927 kmp_user_lock_p *next = (kmp_user_lock_p *)(table_ptr[0]);
3928 __kmp_free(table_ptr);
3932 // Free buffers allocated for blocks of locks.
3933 kmp_block_of_locks_t *block_ptr = __kmp_lock_blocks;
3934 __kmp_lock_blocks = NULL;
3936 while (block_ptr != NULL) {
3937 kmp_block_of_locks_t *next = block_ptr->next_block;
3938 __kmp_free(block_ptr->locks);
3939 // *block_ptr itself was allocated at the end of the locks vector.
3943 TCW_4(__kmp_init_user_locks, FALSE);
3946 #endif // KMP_USE_DYNAMIC_LOCK