diff options
Diffstat (limited to 'final/runtime/src/kmp_lock.cpp')
-rw-r--r-- | final/runtime/src/kmp_lock.cpp | 3893 |
1 files changed, 3893 insertions, 0 deletions
diff --git a/final/runtime/src/kmp_lock.cpp b/final/runtime/src/kmp_lock.cpp new file mode 100644 index 0000000..8deb1fb --- /dev/null +++ b/final/runtime/src/kmp_lock.cpp @@ -0,0 +1,3893 @@ +/* + * kmp_lock.cpp -- lock-related functions + */ + +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.txt for details. +// +//===----------------------------------------------------------------------===// + +#include <stddef.h> +#include <atomic> + +#include "kmp.h" +#include "kmp_i18n.h" +#include "kmp_io.h" +#include "kmp_itt.h" +#include "kmp_lock.h" +#include "kmp_wait_release.h" +#include "kmp_wrapper_getpid.h" + +#include "tsan_annotations.h" + +#if KMP_USE_FUTEX +#include <sys/syscall.h> +#include <unistd.h> +// We should really include <futex.h>, but that causes compatibility problems on +// different Linux* OS distributions that either require that you include (or +// break when you try to include) <pci/types.h>. Since all we need is the two +// macros below (which are part of the kernel ABI, so can't change) we just +// define the constants here and don't include <futex.h> +#ifndef FUTEX_WAIT +#define FUTEX_WAIT 0 +#endif +#ifndef FUTEX_WAKE +#define FUTEX_WAKE 1 +#endif +#endif + +/* Implement spin locks for internal library use. */ +/* The algorithm implemented is Lamport's bakery lock [1974]. */ + +void __kmp_validate_locks(void) { + int i; + kmp_uint32 x, y; + + /* Check to make sure unsigned arithmetic does wraps properly */ + x = ~((kmp_uint32)0) - 2; + y = x - 2; + + for (i = 0; i < 8; ++i, ++x, ++y) { + kmp_uint32 z = (x - y); + KMP_ASSERT(z == 2); + } + + KMP_ASSERT(offsetof(kmp_base_queuing_lock, tail_id) % 8 == 0); +} + +/* ------------------------------------------------------------------------ */ +/* test and set locks */ + +// For the non-nested locks, we can only assume that the first 4 bytes were +// allocated, since gcc only allocates 4 bytes for omp_lock_t, and the Intel +// compiler only allocates a 4 byte pointer on IA-32 architecture. On +// Windows* OS on Intel(R) 64, we can assume that all 8 bytes were allocated. +// +// gcc reserves >= 8 bytes for nested locks, so we can assume that the +// entire 8 bytes were allocated for nested locks on all 64-bit platforms. + +static kmp_int32 __kmp_get_tas_lock_owner(kmp_tas_lock_t *lck) { + return KMP_LOCK_STRIP(KMP_ATOMIC_LD_RLX(&lck->lk.poll)) - 1; +} + +static inline bool __kmp_is_tas_lock_nestable(kmp_tas_lock_t *lck) { + return lck->lk.depth_locked != -1; +} + +__forceinline static int +__kmp_acquire_tas_lock_timed_template(kmp_tas_lock_t *lck, kmp_int32 gtid) { + KMP_MB(); + +#ifdef USE_LOCK_PROFILE + kmp_uint32 curr = KMP_LOCK_STRIP(lck->lk.poll); + if ((curr != 0) && (curr != gtid + 1)) + __kmp_printf("LOCK CONTENTION: %p\n", lck); +/* else __kmp_printf( "." );*/ +#endif /* USE_LOCK_PROFILE */ + + kmp_int32 tas_free = KMP_LOCK_FREE(tas); + kmp_int32 tas_busy = KMP_LOCK_BUSY(gtid + 1, tas); + + if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == tas_free && + __kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) { + KMP_FSYNC_ACQUIRED(lck); + return KMP_LOCK_ACQUIRED_FIRST; + } + + kmp_uint32 spins; + KMP_FSYNC_PREPARE(lck); + KMP_INIT_YIELD(spins); + if (TCR_4(__kmp_nth) > (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) { + KMP_YIELD(TRUE); + } else { + KMP_YIELD_SPIN(spins); + } + + kmp_backoff_t backoff = __kmp_spin_backoff_params; + while (KMP_ATOMIC_LD_RLX(&lck->lk.poll) != tas_free || + !__kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) { + __kmp_spin_backoff(&backoff); + if (TCR_4(__kmp_nth) > + (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) { + KMP_YIELD(TRUE); + } else { + KMP_YIELD_SPIN(spins); + } + } + KMP_FSYNC_ACQUIRED(lck); + return KMP_LOCK_ACQUIRED_FIRST; +} + +int __kmp_acquire_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { + int retval = __kmp_acquire_tas_lock_timed_template(lck, gtid); + ANNOTATE_TAS_ACQUIRED(lck); + return retval; +} + +static int __kmp_acquire_tas_lock_with_checks(kmp_tas_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_lock"; + if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) && + __kmp_is_tas_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) == gtid)) { + KMP_FATAL(LockIsAlreadyOwned, func); + } + return __kmp_acquire_tas_lock(lck, gtid); +} + +int __kmp_test_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { + kmp_int32 tas_free = KMP_LOCK_FREE(tas); + kmp_int32 tas_busy = KMP_LOCK_BUSY(gtid + 1, tas); + if (KMP_ATOMIC_LD_RLX(&lck->lk.poll) == tas_free && + __kmp_atomic_compare_store_acq(&lck->lk.poll, tas_free, tas_busy)) { + KMP_FSYNC_ACQUIRED(lck); + return TRUE; + } + return FALSE; +} + +static int __kmp_test_tas_lock_with_checks(kmp_tas_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_lock"; + if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) && + __kmp_is_tas_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + return __kmp_test_tas_lock(lck, gtid); +} + +int __kmp_release_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { + KMP_MB(); /* Flush all pending memory write invalidates. */ + + KMP_FSYNC_RELEASING(lck); + ANNOTATE_TAS_RELEASED(lck); + KMP_ATOMIC_ST_REL(&lck->lk.poll, KMP_LOCK_FREE(tas)); + KMP_MB(); /* Flush all pending memory write invalidates. */ + + KMP_YIELD(TCR_4(__kmp_nth) > + (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); + return KMP_LOCK_RELEASED; +} + +static int __kmp_release_tas_lock_with_checks(kmp_tas_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_lock"; + KMP_MB(); /* in case another processor initialized lock */ + if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) && + __kmp_is_tas_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_tas_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if ((gtid >= 0) && (__kmp_get_tas_lock_owner(lck) >= 0) && + (__kmp_get_tas_lock_owner(lck) != gtid)) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + return __kmp_release_tas_lock(lck, gtid); +} + +void __kmp_init_tas_lock(kmp_tas_lock_t *lck) { + lck->lk.poll = KMP_LOCK_FREE(tas); +} + +static void __kmp_init_tas_lock_with_checks(kmp_tas_lock_t *lck) { + __kmp_init_tas_lock(lck); +} + +void __kmp_destroy_tas_lock(kmp_tas_lock_t *lck) { lck->lk.poll = 0; } + +static void __kmp_destroy_tas_lock_with_checks(kmp_tas_lock_t *lck) { + char const *const func = "omp_destroy_lock"; + if ((sizeof(kmp_tas_lock_t) <= OMP_LOCK_T_SIZE) && + __kmp_is_tas_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_tas_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_tas_lock(lck); +} + +// nested test and set locks + +int __kmp_acquire_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_tas_lock_owner(lck) == gtid) { + lck->lk.depth_locked += 1; + return KMP_LOCK_ACQUIRED_NEXT; + } else { + __kmp_acquire_tas_lock_timed_template(lck, gtid); + ANNOTATE_TAS_ACQUIRED(lck); + lck->lk.depth_locked = 1; + return KMP_LOCK_ACQUIRED_FIRST; + } +} + +static int __kmp_acquire_nested_tas_lock_with_checks(kmp_tas_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_nest_lock"; + if (!__kmp_is_tas_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + return __kmp_acquire_nested_tas_lock(lck, gtid); +} + +int __kmp_test_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { + int retval; + + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_tas_lock_owner(lck) == gtid) { + retval = ++lck->lk.depth_locked; + } else if (!__kmp_test_tas_lock(lck, gtid)) { + retval = 0; + } else { + KMP_MB(); + retval = lck->lk.depth_locked = 1; + } + return retval; +} + +static int __kmp_test_nested_tas_lock_with_checks(kmp_tas_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_nest_lock"; + if (!__kmp_is_tas_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + return __kmp_test_nested_tas_lock(lck, gtid); +} + +int __kmp_release_nested_tas_lock(kmp_tas_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + KMP_MB(); + if (--(lck->lk.depth_locked) == 0) { + __kmp_release_tas_lock(lck, gtid); + return KMP_LOCK_RELEASED; + } + return KMP_LOCK_STILL_HELD; +} + +static int __kmp_release_nested_tas_lock_with_checks(kmp_tas_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_nest_lock"; + KMP_MB(); /* in case another processor initialized lock */ + if (!__kmp_is_tas_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_tas_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if (__kmp_get_tas_lock_owner(lck) != gtid) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + return __kmp_release_nested_tas_lock(lck, gtid); +} + +void __kmp_init_nested_tas_lock(kmp_tas_lock_t *lck) { + __kmp_init_tas_lock(lck); + lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks +} + +static void __kmp_init_nested_tas_lock_with_checks(kmp_tas_lock_t *lck) { + __kmp_init_nested_tas_lock(lck); +} + +void __kmp_destroy_nested_tas_lock(kmp_tas_lock_t *lck) { + __kmp_destroy_tas_lock(lck); + lck->lk.depth_locked = 0; +} + +static void __kmp_destroy_nested_tas_lock_with_checks(kmp_tas_lock_t *lck) { + char const *const func = "omp_destroy_nest_lock"; + if (!__kmp_is_tas_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_tas_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_nested_tas_lock(lck); +} + +#if KMP_USE_FUTEX + +/* ------------------------------------------------------------------------ */ +/* futex locks */ + +// futex locks are really just test and set locks, with a different method +// of handling contention. They take the same amount of space as test and +// set locks, and are allocated the same way (i.e. use the area allocated by +// the compiler for non-nested locks / allocate nested locks on the heap). + +static kmp_int32 __kmp_get_futex_lock_owner(kmp_futex_lock_t *lck) { + return KMP_LOCK_STRIP((TCR_4(lck->lk.poll) >> 1)) - 1; +} + +static inline bool __kmp_is_futex_lock_nestable(kmp_futex_lock_t *lck) { + return lck->lk.depth_locked != -1; +} + +__forceinline static int +__kmp_acquire_futex_lock_timed_template(kmp_futex_lock_t *lck, kmp_int32 gtid) { + kmp_int32 gtid_code = (gtid + 1) << 1; + + KMP_MB(); + +#ifdef USE_LOCK_PROFILE + kmp_uint32 curr = KMP_LOCK_STRIP(TCR_4(lck->lk.poll)); + if ((curr != 0) && (curr != gtid_code)) + __kmp_printf("LOCK CONTENTION: %p\n", lck); +/* else __kmp_printf( "." );*/ +#endif /* USE_LOCK_PROFILE */ + + KMP_FSYNC_PREPARE(lck); + KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d entering\n", + lck, lck->lk.poll, gtid)); + + kmp_int32 poll_val; + + while ((poll_val = KMP_COMPARE_AND_STORE_RET32( + &(lck->lk.poll), KMP_LOCK_FREE(futex), + KMP_LOCK_BUSY(gtid_code, futex))) != KMP_LOCK_FREE(futex)) { + + kmp_int32 cond = KMP_LOCK_STRIP(poll_val) & 1; + KA_TRACE( + 1000, + ("__kmp_acquire_futex_lock: lck:%p, T#%d poll_val = 0x%x cond = 0x%x\n", + lck, gtid, poll_val, cond)); + + // NOTE: if you try to use the following condition for this branch + // + // if ( poll_val & 1 == 0 ) + // + // Then the 12.0 compiler has a bug where the following block will + // always be skipped, regardless of the value of the LSB of poll_val. + if (!cond) { + // Try to set the lsb in the poll to indicate to the owner + // thread that they need to wake this thread up. + if (!KMP_COMPARE_AND_STORE_REL32(&(lck->lk.poll), poll_val, + poll_val | KMP_LOCK_BUSY(1, futex))) { + KA_TRACE( + 1000, + ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d can't set bit 0\n", + lck, lck->lk.poll, gtid)); + continue; + } + poll_val |= KMP_LOCK_BUSY(1, futex); + + KA_TRACE(1000, + ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d bit 0 set\n", lck, + lck->lk.poll, gtid)); + } + + KA_TRACE( + 1000, + ("__kmp_acquire_futex_lock: lck:%p, T#%d before futex_wait(0x%x)\n", + lck, gtid, poll_val)); + + kmp_int32 rc; + if ((rc = syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAIT, poll_val, NULL, + NULL, 0)) != 0) { + KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p, T#%d futex_wait(0x%x) " + "failed (rc=%d errno=%d)\n", + lck, gtid, poll_val, rc, errno)); + continue; + } + + KA_TRACE(1000, + ("__kmp_acquire_futex_lock: lck:%p, T#%d after futex_wait(0x%x)\n", + lck, gtid, poll_val)); + // This thread has now done a successful futex wait call and was entered on + // the OS futex queue. We must now perform a futex wake call when releasing + // the lock, as we have no idea how many other threads are in the queue. + gtid_code |= 1; + } + + KMP_FSYNC_ACQUIRED(lck); + KA_TRACE(1000, ("__kmp_acquire_futex_lock: lck:%p(0x%x), T#%d exiting\n", lck, + lck->lk.poll, gtid)); + return KMP_LOCK_ACQUIRED_FIRST; +} + +int __kmp_acquire_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { + int retval = __kmp_acquire_futex_lock_timed_template(lck, gtid); + ANNOTATE_FUTEX_ACQUIRED(lck); + return retval; +} + +static int __kmp_acquire_futex_lock_with_checks(kmp_futex_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_lock"; + if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) && + __kmp_is_futex_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) == gtid)) { + KMP_FATAL(LockIsAlreadyOwned, func); + } + return __kmp_acquire_futex_lock(lck, gtid); +} + +int __kmp_test_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { + if (KMP_COMPARE_AND_STORE_ACQ32(&(lck->lk.poll), KMP_LOCK_FREE(futex), + KMP_LOCK_BUSY((gtid + 1) << 1, futex))) { + KMP_FSYNC_ACQUIRED(lck); + return TRUE; + } + return FALSE; +} + +static int __kmp_test_futex_lock_with_checks(kmp_futex_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_lock"; + if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) && + __kmp_is_futex_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + return __kmp_test_futex_lock(lck, gtid); +} + +int __kmp_release_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { + KMP_MB(); /* Flush all pending memory write invalidates. */ + + KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d entering\n", + lck, lck->lk.poll, gtid)); + + KMP_FSYNC_RELEASING(lck); + ANNOTATE_FUTEX_RELEASED(lck); + + kmp_int32 poll_val = KMP_XCHG_FIXED32(&(lck->lk.poll), KMP_LOCK_FREE(futex)); + + KA_TRACE(1000, + ("__kmp_release_futex_lock: lck:%p, T#%d released poll_val = 0x%x\n", + lck, gtid, poll_val)); + + if (KMP_LOCK_STRIP(poll_val) & 1) { + KA_TRACE(1000, + ("__kmp_release_futex_lock: lck:%p, T#%d futex_wake 1 thread\n", + lck, gtid)); + syscall(__NR_futex, &(lck->lk.poll), FUTEX_WAKE, KMP_LOCK_BUSY(1, futex), + NULL, NULL, 0); + } + + KMP_MB(); /* Flush all pending memory write invalidates. */ + + KA_TRACE(1000, ("__kmp_release_futex_lock: lck:%p(0x%x), T#%d exiting\n", lck, + lck->lk.poll, gtid)); + + KMP_YIELD(TCR_4(__kmp_nth) > + (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); + return KMP_LOCK_RELEASED; +} + +static int __kmp_release_futex_lock_with_checks(kmp_futex_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_lock"; + KMP_MB(); /* in case another processor initialized lock */ + if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) && + __kmp_is_futex_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_futex_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if ((gtid >= 0) && (__kmp_get_futex_lock_owner(lck) >= 0) && + (__kmp_get_futex_lock_owner(lck) != gtid)) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + return __kmp_release_futex_lock(lck, gtid); +} + +void __kmp_init_futex_lock(kmp_futex_lock_t *lck) { + TCW_4(lck->lk.poll, KMP_LOCK_FREE(futex)); +} + +static void __kmp_init_futex_lock_with_checks(kmp_futex_lock_t *lck) { + __kmp_init_futex_lock(lck); +} + +void __kmp_destroy_futex_lock(kmp_futex_lock_t *lck) { lck->lk.poll = 0; } + +static void __kmp_destroy_futex_lock_with_checks(kmp_futex_lock_t *lck) { + char const *const func = "omp_destroy_lock"; + if ((sizeof(kmp_futex_lock_t) <= OMP_LOCK_T_SIZE) && + __kmp_is_futex_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_futex_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_futex_lock(lck); +} + +// nested futex locks + +int __kmp_acquire_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_futex_lock_owner(lck) == gtid) { + lck->lk.depth_locked += 1; + return KMP_LOCK_ACQUIRED_NEXT; + } else { + __kmp_acquire_futex_lock_timed_template(lck, gtid); + ANNOTATE_FUTEX_ACQUIRED(lck); + lck->lk.depth_locked = 1; + return KMP_LOCK_ACQUIRED_FIRST; + } +} + +static int __kmp_acquire_nested_futex_lock_with_checks(kmp_futex_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_nest_lock"; + if (!__kmp_is_futex_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + return __kmp_acquire_nested_futex_lock(lck, gtid); +} + +int __kmp_test_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { + int retval; + + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_futex_lock_owner(lck) == gtid) { + retval = ++lck->lk.depth_locked; + } else if (!__kmp_test_futex_lock(lck, gtid)) { + retval = 0; + } else { + KMP_MB(); + retval = lck->lk.depth_locked = 1; + } + return retval; +} + +static int __kmp_test_nested_futex_lock_with_checks(kmp_futex_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_nest_lock"; + if (!__kmp_is_futex_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + return __kmp_test_nested_futex_lock(lck, gtid); +} + +int __kmp_release_nested_futex_lock(kmp_futex_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + KMP_MB(); + if (--(lck->lk.depth_locked) == 0) { + __kmp_release_futex_lock(lck, gtid); + return KMP_LOCK_RELEASED; + } + return KMP_LOCK_STILL_HELD; +} + +static int __kmp_release_nested_futex_lock_with_checks(kmp_futex_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_nest_lock"; + KMP_MB(); /* in case another processor initialized lock */ + if (!__kmp_is_futex_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_futex_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if (__kmp_get_futex_lock_owner(lck) != gtid) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + return __kmp_release_nested_futex_lock(lck, gtid); +} + +void __kmp_init_nested_futex_lock(kmp_futex_lock_t *lck) { + __kmp_init_futex_lock(lck); + lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks +} + +static void __kmp_init_nested_futex_lock_with_checks(kmp_futex_lock_t *lck) { + __kmp_init_nested_futex_lock(lck); +} + +void __kmp_destroy_nested_futex_lock(kmp_futex_lock_t *lck) { + __kmp_destroy_futex_lock(lck); + lck->lk.depth_locked = 0; +} + +static void __kmp_destroy_nested_futex_lock_with_checks(kmp_futex_lock_t *lck) { + char const *const func = "omp_destroy_nest_lock"; + if (!__kmp_is_futex_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_futex_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_nested_futex_lock(lck); +} + +#endif // KMP_USE_FUTEX + +/* ------------------------------------------------------------------------ */ +/* ticket (bakery) locks */ + +static kmp_int32 __kmp_get_ticket_lock_owner(kmp_ticket_lock_t *lck) { + return std::atomic_load_explicit(&lck->lk.owner_id, + std::memory_order_relaxed) - + 1; +} + +static inline bool __kmp_is_ticket_lock_nestable(kmp_ticket_lock_t *lck) { + return std::atomic_load_explicit(&lck->lk.depth_locked, + std::memory_order_relaxed) != -1; +} + +static kmp_uint32 __kmp_bakery_check(void *now_serving, kmp_uint32 my_ticket) { + return std::atomic_load_explicit((std::atomic<unsigned> *)now_serving, + std::memory_order_acquire) == my_ticket; +} + +__forceinline static int +__kmp_acquire_ticket_lock_timed_template(kmp_ticket_lock_t *lck, + kmp_int32 gtid) { + kmp_uint32 my_ticket = std::atomic_fetch_add_explicit( + &lck->lk.next_ticket, 1U, std::memory_order_relaxed); + +#ifdef USE_LOCK_PROFILE + if (std::atomic_load_explicit(&lck->lk.now_serving, + std::memory_order_relaxed) != my_ticket) + __kmp_printf("LOCK CONTENTION: %p\n", lck); +/* else __kmp_printf( "." );*/ +#endif /* USE_LOCK_PROFILE */ + + if (std::atomic_load_explicit(&lck->lk.now_serving, + std::memory_order_acquire) == my_ticket) { + return KMP_LOCK_ACQUIRED_FIRST; + } + KMP_WAIT_YIELD_PTR(&lck->lk.now_serving, my_ticket, __kmp_bakery_check, lck); + return KMP_LOCK_ACQUIRED_FIRST; +} + +int __kmp_acquire_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { + int retval = __kmp_acquire_ticket_lock_timed_template(lck, gtid); + ANNOTATE_TICKET_ACQUIRED(lck); + return retval; +} + +static int __kmp_acquire_ticket_lock_with_checks(kmp_ticket_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_lock"; + + if (!std::atomic_load_explicit(&lck->lk.initialized, + std::memory_order_relaxed)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (lck->lk.self != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_ticket_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) == gtid)) { + KMP_FATAL(LockIsAlreadyOwned, func); + } + + __kmp_acquire_ticket_lock(lck, gtid); + + std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1, + std::memory_order_relaxed); + return KMP_LOCK_ACQUIRED_FIRST; +} + +int __kmp_test_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { + kmp_uint32 my_ticket = std::atomic_load_explicit(&lck->lk.next_ticket, + std::memory_order_relaxed); + + if (std::atomic_load_explicit(&lck->lk.now_serving, + std::memory_order_relaxed) == my_ticket) { + kmp_uint32 next_ticket = my_ticket + 1; + if (std::atomic_compare_exchange_strong_explicit( + &lck->lk.next_ticket, &my_ticket, next_ticket, + std::memory_order_acquire, std::memory_order_acquire)) { + return TRUE; + } + } + return FALSE; +} + +static int __kmp_test_ticket_lock_with_checks(kmp_ticket_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_lock"; + + if (!std::atomic_load_explicit(&lck->lk.initialized, + std::memory_order_relaxed)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (lck->lk.self != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_ticket_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + + int retval = __kmp_test_ticket_lock(lck, gtid); + + if (retval) { + std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1, + std::memory_order_relaxed); + } + return retval; +} + +int __kmp_release_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { + kmp_uint32 distance = std::atomic_load_explicit(&lck->lk.next_ticket, + std::memory_order_relaxed) - + std::atomic_load_explicit(&lck->lk.now_serving, + std::memory_order_relaxed); + + ANNOTATE_TICKET_RELEASED(lck); + std::atomic_fetch_add_explicit(&lck->lk.now_serving, 1U, + std::memory_order_release); + + KMP_YIELD(distance > + (kmp_uint32)(__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); + return KMP_LOCK_RELEASED; +} + +static int __kmp_release_ticket_lock_with_checks(kmp_ticket_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_lock"; + + if (!std::atomic_load_explicit(&lck->lk.initialized, + std::memory_order_relaxed)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (lck->lk.self != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_ticket_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_ticket_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if ((gtid >= 0) && (__kmp_get_ticket_lock_owner(lck) >= 0) && + (__kmp_get_ticket_lock_owner(lck) != gtid)) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed); + return __kmp_release_ticket_lock(lck, gtid); +} + +void __kmp_init_ticket_lock(kmp_ticket_lock_t *lck) { + lck->lk.location = NULL; + lck->lk.self = lck; + std::atomic_store_explicit(&lck->lk.next_ticket, 0U, + std::memory_order_relaxed); + std::atomic_store_explicit(&lck->lk.now_serving, 0U, + std::memory_order_relaxed); + std::atomic_store_explicit( + &lck->lk.owner_id, 0, + std::memory_order_relaxed); // no thread owns the lock. + std::atomic_store_explicit( + &lck->lk.depth_locked, -1, + std::memory_order_relaxed); // -1 => not a nested lock. + std::atomic_store_explicit(&lck->lk.initialized, true, + std::memory_order_release); +} + +static void __kmp_init_ticket_lock_with_checks(kmp_ticket_lock_t *lck) { + __kmp_init_ticket_lock(lck); +} + +void __kmp_destroy_ticket_lock(kmp_ticket_lock_t *lck) { + std::atomic_store_explicit(&lck->lk.initialized, false, + std::memory_order_release); + lck->lk.self = NULL; + lck->lk.location = NULL; + std::atomic_store_explicit(&lck->lk.next_ticket, 0U, + std::memory_order_relaxed); + std::atomic_store_explicit(&lck->lk.now_serving, 0U, + std::memory_order_relaxed); + std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed); + std::atomic_store_explicit(&lck->lk.depth_locked, -1, + std::memory_order_relaxed); +} + +static void __kmp_destroy_ticket_lock_with_checks(kmp_ticket_lock_t *lck) { + char const *const func = "omp_destroy_lock"; + + if (!std::atomic_load_explicit(&lck->lk.initialized, + std::memory_order_relaxed)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (lck->lk.self != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_ticket_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_ticket_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_ticket_lock(lck); +} + +// nested ticket locks + +int __kmp_acquire_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_ticket_lock_owner(lck) == gtid) { + std::atomic_fetch_add_explicit(&lck->lk.depth_locked, 1, + std::memory_order_relaxed); + return KMP_LOCK_ACQUIRED_NEXT; + } else { + __kmp_acquire_ticket_lock_timed_template(lck, gtid); + ANNOTATE_TICKET_ACQUIRED(lck); + std::atomic_store_explicit(&lck->lk.depth_locked, 1, + std::memory_order_relaxed); + std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1, + std::memory_order_relaxed); + return KMP_LOCK_ACQUIRED_FIRST; + } +} + +static int __kmp_acquire_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_nest_lock"; + + if (!std::atomic_load_explicit(&lck->lk.initialized, + std::memory_order_relaxed)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (lck->lk.self != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_ticket_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + return __kmp_acquire_nested_ticket_lock(lck, gtid); +} + +int __kmp_test_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { + int retval; + + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_ticket_lock_owner(lck) == gtid) { + retval = std::atomic_fetch_add_explicit(&lck->lk.depth_locked, 1, + std::memory_order_relaxed) + + 1; + } else if (!__kmp_test_ticket_lock(lck, gtid)) { + retval = 0; + } else { + std::atomic_store_explicit(&lck->lk.depth_locked, 1, + std::memory_order_relaxed); + std::atomic_store_explicit(&lck->lk.owner_id, gtid + 1, + std::memory_order_relaxed); + retval = 1; + } + return retval; +} + +static int __kmp_test_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_nest_lock"; + + if (!std::atomic_load_explicit(&lck->lk.initialized, + std::memory_order_relaxed)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (lck->lk.self != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_ticket_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + return __kmp_test_nested_ticket_lock(lck, gtid); +} + +int __kmp_release_nested_ticket_lock(kmp_ticket_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + if ((std::atomic_fetch_add_explicit(&lck->lk.depth_locked, -1, + std::memory_order_relaxed) - + 1) == 0) { + std::atomic_store_explicit(&lck->lk.owner_id, 0, std::memory_order_relaxed); + __kmp_release_ticket_lock(lck, gtid); + return KMP_LOCK_RELEASED; + } + return KMP_LOCK_STILL_HELD; +} + +static int __kmp_release_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_nest_lock"; + + if (!std::atomic_load_explicit(&lck->lk.initialized, + std::memory_order_relaxed)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (lck->lk.self != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_ticket_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_ticket_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if (__kmp_get_ticket_lock_owner(lck) != gtid) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + return __kmp_release_nested_ticket_lock(lck, gtid); +} + +void __kmp_init_nested_ticket_lock(kmp_ticket_lock_t *lck) { + __kmp_init_ticket_lock(lck); + std::atomic_store_explicit(&lck->lk.depth_locked, 0, + std::memory_order_relaxed); + // >= 0 for nestable locks, -1 for simple locks +} + +static void __kmp_init_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck) { + __kmp_init_nested_ticket_lock(lck); +} + +void __kmp_destroy_nested_ticket_lock(kmp_ticket_lock_t *lck) { + __kmp_destroy_ticket_lock(lck); + std::atomic_store_explicit(&lck->lk.depth_locked, 0, + std::memory_order_relaxed); +} + +static void +__kmp_destroy_nested_ticket_lock_with_checks(kmp_ticket_lock_t *lck) { + char const *const func = "omp_destroy_nest_lock"; + + if (!std::atomic_load_explicit(&lck->lk.initialized, + std::memory_order_relaxed)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (lck->lk.self != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_ticket_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_ticket_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_nested_ticket_lock(lck); +} + +// access functions to fields which don't exist for all lock kinds. + +static int __kmp_is_ticket_lock_initialized(kmp_ticket_lock_t *lck) { + return std::atomic_load_explicit(&lck->lk.initialized, + std::memory_order_relaxed) && + (lck->lk.self == lck); +} + +static const ident_t *__kmp_get_ticket_lock_location(kmp_ticket_lock_t *lck) { + return lck->lk.location; +} + +static void __kmp_set_ticket_lock_location(kmp_ticket_lock_t *lck, + const ident_t *loc) { + lck->lk.location = loc; +} + +static kmp_lock_flags_t __kmp_get_ticket_lock_flags(kmp_ticket_lock_t *lck) { + return lck->lk.flags; +} + +static void __kmp_set_ticket_lock_flags(kmp_ticket_lock_t *lck, + kmp_lock_flags_t flags) { + lck->lk.flags = flags; +} + +/* ------------------------------------------------------------------------ */ +/* queuing locks */ + +/* First the states + (head,tail) = 0, 0 means lock is unheld, nobody on queue + UINT_MAX or -1, 0 means lock is held, nobody on queue + h, h means lock held or about to transition, + 1 element on queue + h, t h <> t, means lock is held or about to + transition, >1 elements on queue + + Now the transitions + Acquire(0,0) = -1 ,0 + Release(0,0) = Error + Acquire(-1,0) = h ,h h > 0 + Release(-1,0) = 0 ,0 + Acquire(h,h) = h ,t h > 0, t > 0, h <> t + Release(h,h) = -1 ,0 h > 0 + Acquire(h,t) = h ,t' h > 0, t > 0, t' > 0, h <> t, h <> t', t <> t' + Release(h,t) = h',t h > 0, t > 0, h <> t, h <> h', h' maybe = t + + And pictorially + + +-----+ + | 0, 0|------- release -------> Error + +-----+ + | ^ + acquire| |release + | | + | | + v | + +-----+ + |-1, 0| + +-----+ + | ^ + acquire| |release + | | + | | + v | + +-----+ + | h, h| + +-----+ + | ^ + acquire| |release + | | + | | + v | + +-----+ + | h, t|----- acquire, release loopback ---+ + +-----+ | + ^ | + | | + +------------------------------------+ + */ + +#ifdef DEBUG_QUEUING_LOCKS + +/* Stuff for circular trace buffer */ +#define TRACE_BUF_ELE 1024 +static char traces[TRACE_BUF_ELE][128] = {0}; +static int tc = 0; +#define TRACE_LOCK(X, Y) \ + KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s\n", X, Y); +#define TRACE_LOCK_T(X, Y, Z) \ + KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s%d\n", X, Y, Z); +#define TRACE_LOCK_HT(X, Y, Z, Q) \ + KMP_SNPRINTF(traces[tc++ % TRACE_BUF_ELE], 128, "t%d at %s %d,%d\n", X, Y, \ + Z, Q); + +static void __kmp_dump_queuing_lock(kmp_info_t *this_thr, kmp_int32 gtid, + kmp_queuing_lock_t *lck, kmp_int32 head_id, + kmp_int32 tail_id) { + kmp_int32 t, i; + + __kmp_printf_no_lock("\n__kmp_dump_queuing_lock: TRACE BEGINS HERE! \n"); + + i = tc % TRACE_BUF_ELE; + __kmp_printf_no_lock("%s\n", traces[i]); + i = (i + 1) % TRACE_BUF_ELE; + while (i != (tc % TRACE_BUF_ELE)) { + __kmp_printf_no_lock("%s", traces[i]); + i = (i + 1) % TRACE_BUF_ELE; + } + __kmp_printf_no_lock("\n"); + + __kmp_printf_no_lock("\n__kmp_dump_queuing_lock: gtid+1:%d, spin_here:%d, " + "next_wait:%d, head_id:%d, tail_id:%d\n", + gtid + 1, this_thr->th.th_spin_here, + this_thr->th.th_next_waiting, head_id, tail_id); + + __kmp_printf_no_lock("\t\thead: %d ", lck->lk.head_id); + + if (lck->lk.head_id >= 1) { + t = __kmp_threads[lck->lk.head_id - 1]->th.th_next_waiting; + while (t > 0) { + __kmp_printf_no_lock("-> %d ", t); + t = __kmp_threads[t - 1]->th.th_next_waiting; + } + } + __kmp_printf_no_lock("; tail: %d ", lck->lk.tail_id); + __kmp_printf_no_lock("\n\n"); +} + +#endif /* DEBUG_QUEUING_LOCKS */ + +static kmp_int32 __kmp_get_queuing_lock_owner(kmp_queuing_lock_t *lck) { + return TCR_4(lck->lk.owner_id) - 1; +} + +static inline bool __kmp_is_queuing_lock_nestable(kmp_queuing_lock_t *lck) { + return lck->lk.depth_locked != -1; +} + +/* Acquire a lock using a the queuing lock implementation */ +template <bool takeTime> +/* [TLW] The unused template above is left behind because of what BEB believes + is a potential compiler problem with __forceinline. */ +__forceinline static int +__kmp_acquire_queuing_lock_timed_template(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + kmp_info_t *this_thr = __kmp_thread_from_gtid(gtid); + volatile kmp_int32 *head_id_p = &lck->lk.head_id; + volatile kmp_int32 *tail_id_p = &lck->lk.tail_id; + volatile kmp_uint32 *spin_here_p; + kmp_int32 need_mf = 1; + +#if OMPT_SUPPORT + omp_state_t prev_state = omp_state_undefined; +#endif + + KA_TRACE(1000, + ("__kmp_acquire_queuing_lock: lck:%p, T#%d entering\n", lck, gtid)); + + KMP_FSYNC_PREPARE(lck); + KMP_DEBUG_ASSERT(this_thr != NULL); + spin_here_p = &this_thr->th.th_spin_here; + +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK(gtid + 1, "acq ent"); + if (*spin_here_p) + __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); + if (this_thr->th.th_next_waiting != 0) + __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); +#endif + KMP_DEBUG_ASSERT(!*spin_here_p); + KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0); + + /* The following st.rel to spin_here_p needs to precede the cmpxchg.acq to + head_id_p that may follow, not just in execution order, but also in + visibility order. This way, when a releasing thread observes the changes to + the queue by this thread, it can rightly assume that spin_here_p has + already been set to TRUE, so that when it sets spin_here_p to FALSE, it is + not premature. If the releasing thread sets spin_here_p to FALSE before + this thread sets it to TRUE, this thread will hang. */ + *spin_here_p = TRUE; /* before enqueuing to prevent race */ + + while (1) { + kmp_int32 enqueued; + kmp_int32 head; + kmp_int32 tail; + + head = *head_id_p; + + switch (head) { + + case -1: { +#ifdef DEBUG_QUEUING_LOCKS + tail = *tail_id_p; + TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail); +#endif + tail = 0; /* to make sure next link asynchronously read is not set + accidentally; this assignment prevents us from entering the + if ( t > 0 ) condition in the enqueued case below, which is not + necessary for this state transition */ + + need_mf = 0; + /* try (-1,0)->(tid,tid) */ + enqueued = KMP_COMPARE_AND_STORE_ACQ64((volatile kmp_int64 *)tail_id_p, + KMP_PACK_64(-1, 0), + KMP_PACK_64(gtid + 1, gtid + 1)); +#ifdef DEBUG_QUEUING_LOCKS + if (enqueued) + TRACE_LOCK(gtid + 1, "acq enq: (-1,0)->(tid,tid)"); +#endif + } break; + + default: { + tail = *tail_id_p; + KMP_DEBUG_ASSERT(tail != gtid + 1); + +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail); +#endif + + if (tail == 0) { + enqueued = FALSE; + } else { + need_mf = 0; + /* try (h,t) or (h,h)->(h,tid) */ + enqueued = KMP_COMPARE_AND_STORE_ACQ32(tail_id_p, tail, gtid + 1); + +#ifdef DEBUG_QUEUING_LOCKS + if (enqueued) + TRACE_LOCK(gtid + 1, "acq enq: (h,t)->(h,tid)"); +#endif + } + } break; + + case 0: /* empty queue */ + { + kmp_int32 grabbed_lock; + +#ifdef DEBUG_QUEUING_LOCKS + tail = *tail_id_p; + TRACE_LOCK_HT(gtid + 1, "acq read: ", head, tail); +#endif + /* try (0,0)->(-1,0) */ + + /* only legal transition out of head = 0 is head = -1 with no change to + * tail */ + grabbed_lock = KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1); + + if (grabbed_lock) { + + *spin_here_p = FALSE; + + KA_TRACE( + 1000, + ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: no queuing\n", + lck, gtid)); +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK_HT(gtid + 1, "acq exit: ", head, 0); +#endif + +#if OMPT_SUPPORT + if (ompt_enabled.enabled && prev_state != omp_state_undefined) { + /* change the state before clearing wait_id */ + this_thr->th.ompt_thread_info.state = prev_state; + this_thr->th.ompt_thread_info.wait_id = 0; + } +#endif + + KMP_FSYNC_ACQUIRED(lck); + return KMP_LOCK_ACQUIRED_FIRST; /* lock holder cannot be on queue */ + } + enqueued = FALSE; + } break; + } + +#if OMPT_SUPPORT + if (ompt_enabled.enabled && prev_state == omp_state_undefined) { + /* this thread will spin; set wait_id before entering wait state */ + prev_state = this_thr->th.ompt_thread_info.state; + this_thr->th.ompt_thread_info.wait_id = (uint64_t)lck; + this_thr->th.ompt_thread_info.state = omp_state_wait_lock; + } +#endif + + if (enqueued) { + if (tail > 0) { + kmp_info_t *tail_thr = __kmp_thread_from_gtid(tail - 1); + KMP_ASSERT(tail_thr != NULL); + tail_thr->th.th_next_waiting = gtid + 1; + /* corresponding wait for this write in release code */ + } + KA_TRACE(1000, + ("__kmp_acquire_queuing_lock: lck:%p, T#%d waiting for lock\n", + lck, gtid)); + + /* ToDo: May want to consider using __kmp_wait_sleep or something that + sleeps for throughput only here. */ + KMP_MB(); + KMP_WAIT_YIELD(spin_here_p, FALSE, KMP_EQ, lck); + +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK(gtid + 1, "acq spin"); + + if (this_thr->th.th_next_waiting != 0) + __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); +#endif + KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0); + KA_TRACE(1000, ("__kmp_acquire_queuing_lock: lck:%p, T#%d exiting: after " + "waiting on queue\n", + lck, gtid)); + +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK(gtid + 1, "acq exit 2"); +#endif + +#if OMPT_SUPPORT + /* change the state before clearing wait_id */ + this_thr->th.ompt_thread_info.state = prev_state; + this_thr->th.ompt_thread_info.wait_id = 0; +#endif + + /* got lock, we were dequeued by the thread that released lock */ + return KMP_LOCK_ACQUIRED_FIRST; + } + + /* Yield if number of threads > number of logical processors */ + /* ToDo: Not sure why this should only be in oversubscription case, + maybe should be traditional YIELD_INIT/YIELD_WHEN loop */ + KMP_YIELD(TCR_4(__kmp_nth) > + (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK(gtid + 1, "acq retry"); +#endif + } + KMP_ASSERT2(0, "should not get here"); + return KMP_LOCK_ACQUIRED_FIRST; +} + +int __kmp_acquire_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + int retval = __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid); + ANNOTATE_QUEUING_ACQUIRED(lck); + return retval; +} + +static int __kmp_acquire_queuing_lock_with_checks(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_queuing_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_queuing_lock_owner(lck) == gtid) { + KMP_FATAL(LockIsAlreadyOwned, func); + } + + __kmp_acquire_queuing_lock(lck, gtid); + + lck->lk.owner_id = gtid + 1; + return KMP_LOCK_ACQUIRED_FIRST; +} + +int __kmp_test_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { + volatile kmp_int32 *head_id_p = &lck->lk.head_id; + kmp_int32 head; +#ifdef KMP_DEBUG + kmp_info_t *this_thr; +#endif + + KA_TRACE(1000, ("__kmp_test_queuing_lock: T#%d entering\n", gtid)); + KMP_DEBUG_ASSERT(gtid >= 0); +#ifdef KMP_DEBUG + this_thr = __kmp_thread_from_gtid(gtid); + KMP_DEBUG_ASSERT(this_thr != NULL); + KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here); +#endif + + head = *head_id_p; + + if (head == 0) { /* nobody on queue, nobody holding */ + /* try (0,0)->(-1,0) */ + if (KMP_COMPARE_AND_STORE_ACQ32(head_id_p, 0, -1)) { + KA_TRACE(1000, + ("__kmp_test_queuing_lock: T#%d exiting: holding lock\n", gtid)); + KMP_FSYNC_ACQUIRED(lck); + ANNOTATE_QUEUING_ACQUIRED(lck); + return TRUE; + } + } + + KA_TRACE(1000, + ("__kmp_test_queuing_lock: T#%d exiting: without lock\n", gtid)); + return FALSE; +} + +static int __kmp_test_queuing_lock_with_checks(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_queuing_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + + int retval = __kmp_test_queuing_lock(lck, gtid); + + if (retval) { + lck->lk.owner_id = gtid + 1; + } + return retval; +} + +int __kmp_release_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { + kmp_info_t *this_thr; + volatile kmp_int32 *head_id_p = &lck->lk.head_id; + volatile kmp_int32 *tail_id_p = &lck->lk.tail_id; + + KA_TRACE(1000, + ("__kmp_release_queuing_lock: lck:%p, T#%d entering\n", lck, gtid)); + KMP_DEBUG_ASSERT(gtid >= 0); + this_thr = __kmp_thread_from_gtid(gtid); + KMP_DEBUG_ASSERT(this_thr != NULL); +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK(gtid + 1, "rel ent"); + + if (this_thr->th.th_spin_here) + __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); + if (this_thr->th.th_next_waiting != 0) + __kmp_dump_queuing_lock(this_thr, gtid, lck, *head_id_p, *tail_id_p); +#endif + KMP_DEBUG_ASSERT(!this_thr->th.th_spin_here); + KMP_DEBUG_ASSERT(this_thr->th.th_next_waiting == 0); + + KMP_FSYNC_RELEASING(lck); + ANNOTATE_QUEUING_RELEASED(lck); + + while (1) { + kmp_int32 dequeued; + kmp_int32 head; + kmp_int32 tail; + + head = *head_id_p; + +#ifdef DEBUG_QUEUING_LOCKS + tail = *tail_id_p; + TRACE_LOCK_HT(gtid + 1, "rel read: ", head, tail); + if (head == 0) + __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail); +#endif + KMP_DEBUG_ASSERT(head != + 0); /* holding the lock, head must be -1 or queue head */ + + if (head == -1) { /* nobody on queue */ + /* try (-1,0)->(0,0) */ + if (KMP_COMPARE_AND_STORE_REL32(head_id_p, -1, 0)) { + KA_TRACE( + 1000, + ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: queue empty\n", + lck, gtid)); +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK_HT(gtid + 1, "rel exit: ", 0, 0); +#endif + +#if OMPT_SUPPORT +/* nothing to do - no other thread is trying to shift blame */ +#endif + return KMP_LOCK_RELEASED; + } + dequeued = FALSE; + } else { + KMP_MB(); + tail = *tail_id_p; + if (head == tail) { /* only one thread on the queue */ +#ifdef DEBUG_QUEUING_LOCKS + if (head <= 0) + __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail); +#endif + KMP_DEBUG_ASSERT(head > 0); + + /* try (h,h)->(-1,0) */ + dequeued = KMP_COMPARE_AND_STORE_REL64( + RCAST(volatile kmp_int64 *, tail_id_p), KMP_PACK_64(head, head), + KMP_PACK_64(-1, 0)); +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK(gtid + 1, "rel deq: (h,h)->(-1,0)"); +#endif + + } else { + volatile kmp_int32 *waiting_id_p; + kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1); + KMP_DEBUG_ASSERT(head_thr != NULL); + waiting_id_p = &head_thr->th.th_next_waiting; + +/* Does this require synchronous reads? */ +#ifdef DEBUG_QUEUING_LOCKS + if (head <= 0 || tail <= 0) + __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail); +#endif + KMP_DEBUG_ASSERT(head > 0 && tail > 0); + + /* try (h,t)->(h',t) or (t,t) */ + KMP_MB(); + /* make sure enqueuing thread has time to update next waiting thread + * field */ + *head_id_p = KMP_WAIT_YIELD((volatile kmp_uint32 *)waiting_id_p, 0, + KMP_NEQ, NULL); +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK(gtid + 1, "rel deq: (h,t)->(h',t)"); +#endif + dequeued = TRUE; + } + } + + if (dequeued) { + kmp_info_t *head_thr = __kmp_thread_from_gtid(head - 1); + KMP_DEBUG_ASSERT(head_thr != NULL); + +/* Does this require synchronous reads? */ +#ifdef DEBUG_QUEUING_LOCKS + if (head <= 0 || tail <= 0) + __kmp_dump_queuing_lock(this_thr, gtid, lck, head, tail); +#endif + KMP_DEBUG_ASSERT(head > 0 && tail > 0); + + /* For clean code only. Thread not released until next statement prevents + race with acquire code. */ + head_thr->th.th_next_waiting = 0; +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK_T(gtid + 1, "rel nw=0 for t=", head); +#endif + + KMP_MB(); + /* reset spin value */ + head_thr->th.th_spin_here = FALSE; + + KA_TRACE(1000, ("__kmp_release_queuing_lock: lck:%p, T#%d exiting: after " + "dequeuing\n", + lck, gtid)); +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK(gtid + 1, "rel exit 2"); +#endif + return KMP_LOCK_RELEASED; + } +/* KMP_CPU_PAUSE(); don't want to make releasing thread hold up acquiring + threads */ + +#ifdef DEBUG_QUEUING_LOCKS + TRACE_LOCK(gtid + 1, "rel retry"); +#endif + + } /* while */ + KMP_ASSERT2(0, "should not get here"); + return KMP_LOCK_RELEASED; +} + +static int __kmp_release_queuing_lock_with_checks(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_lock"; + KMP_MB(); /* in case another processor initialized lock */ + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_queuing_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_queuing_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if (__kmp_get_queuing_lock_owner(lck) != gtid) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + lck->lk.owner_id = 0; + return __kmp_release_queuing_lock(lck, gtid); +} + +void __kmp_init_queuing_lock(kmp_queuing_lock_t *lck) { + lck->lk.location = NULL; + lck->lk.head_id = 0; + lck->lk.tail_id = 0; + lck->lk.next_ticket = 0; + lck->lk.now_serving = 0; + lck->lk.owner_id = 0; // no thread owns the lock. + lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks. + lck->lk.initialized = lck; + + KA_TRACE(1000, ("__kmp_init_queuing_lock: lock %p initialized\n", lck)); +} + +static void __kmp_init_queuing_lock_with_checks(kmp_queuing_lock_t *lck) { + __kmp_init_queuing_lock(lck); +} + +void __kmp_destroy_queuing_lock(kmp_queuing_lock_t *lck) { + lck->lk.initialized = NULL; + lck->lk.location = NULL; + lck->lk.head_id = 0; + lck->lk.tail_id = 0; + lck->lk.next_ticket = 0; + lck->lk.now_serving = 0; + lck->lk.owner_id = 0; + lck->lk.depth_locked = -1; +} + +static void __kmp_destroy_queuing_lock_with_checks(kmp_queuing_lock_t *lck) { + char const *const func = "omp_destroy_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_queuing_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_queuing_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_queuing_lock(lck); +} + +// nested queuing locks + +int __kmp_acquire_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_queuing_lock_owner(lck) == gtid) { + lck->lk.depth_locked += 1; + return KMP_LOCK_ACQUIRED_NEXT; + } else { + __kmp_acquire_queuing_lock_timed_template<false>(lck, gtid); + ANNOTATE_QUEUING_ACQUIRED(lck); + KMP_MB(); + lck->lk.depth_locked = 1; + KMP_MB(); + lck->lk.owner_id = gtid + 1; + return KMP_LOCK_ACQUIRED_FIRST; + } +} + +static int +__kmp_acquire_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_nest_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_queuing_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + return __kmp_acquire_nested_queuing_lock(lck, gtid); +} + +int __kmp_test_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { + int retval; + + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_queuing_lock_owner(lck) == gtid) { + retval = ++lck->lk.depth_locked; + } else if (!__kmp_test_queuing_lock(lck, gtid)) { + retval = 0; + } else { + KMP_MB(); + retval = lck->lk.depth_locked = 1; + KMP_MB(); + lck->lk.owner_id = gtid + 1; + } + return retval; +} + +static int __kmp_test_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_nest_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_queuing_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + return __kmp_test_nested_queuing_lock(lck, gtid); +} + +int __kmp_release_nested_queuing_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + KMP_MB(); + if (--(lck->lk.depth_locked) == 0) { + KMP_MB(); + lck->lk.owner_id = 0; + __kmp_release_queuing_lock(lck, gtid); + return KMP_LOCK_RELEASED; + } + return KMP_LOCK_STILL_HELD; +} + +static int +__kmp_release_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_nest_lock"; + KMP_MB(); /* in case another processor initialized lock */ + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_queuing_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_queuing_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if (__kmp_get_queuing_lock_owner(lck) != gtid) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + return __kmp_release_nested_queuing_lock(lck, gtid); +} + +void __kmp_init_nested_queuing_lock(kmp_queuing_lock_t *lck) { + __kmp_init_queuing_lock(lck); + lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks +} + +static void +__kmp_init_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) { + __kmp_init_nested_queuing_lock(lck); +} + +void __kmp_destroy_nested_queuing_lock(kmp_queuing_lock_t *lck) { + __kmp_destroy_queuing_lock(lck); + lck->lk.depth_locked = 0; +} + +static void +__kmp_destroy_nested_queuing_lock_with_checks(kmp_queuing_lock_t *lck) { + char const *const func = "omp_destroy_nest_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_queuing_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_queuing_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_nested_queuing_lock(lck); +} + +// access functions to fields which don't exist for all lock kinds. + +static int __kmp_is_queuing_lock_initialized(kmp_queuing_lock_t *lck) { + return lck == lck->lk.initialized; +} + +static const ident_t *__kmp_get_queuing_lock_location(kmp_queuing_lock_t *lck) { + return lck->lk.location; +} + +static void __kmp_set_queuing_lock_location(kmp_queuing_lock_t *lck, + const ident_t *loc) { + lck->lk.location = loc; +} + +static kmp_lock_flags_t __kmp_get_queuing_lock_flags(kmp_queuing_lock_t *lck) { + return lck->lk.flags; +} + +static void __kmp_set_queuing_lock_flags(kmp_queuing_lock_t *lck, + kmp_lock_flags_t flags) { + lck->lk.flags = flags; +} + +#if KMP_USE_ADAPTIVE_LOCKS + +/* RTM Adaptive locks */ + +#if KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300 + +#include <immintrin.h> +#define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT) + +#else + +// Values from the status register after failed speculation. +#define _XBEGIN_STARTED (~0u) +#define _XABORT_EXPLICIT (1 << 0) +#define _XABORT_RETRY (1 << 1) +#define _XABORT_CONFLICT (1 << 2) +#define _XABORT_CAPACITY (1 << 3) +#define _XABORT_DEBUG (1 << 4) +#define _XABORT_NESTED (1 << 5) +#define _XABORT_CODE(x) ((unsigned char)(((x) >> 24) & 0xFF)) + +// Aborts for which it's worth trying again immediately +#define SOFT_ABORT_MASK (_XABORT_RETRY | _XABORT_CONFLICT | _XABORT_EXPLICIT) + +#define STRINGIZE_INTERNAL(arg) #arg +#define STRINGIZE(arg) STRINGIZE_INTERNAL(arg) + +// Access to RTM instructions +/*A version of XBegin which returns -1 on speculation, and the value of EAX on + an abort. This is the same definition as the compiler intrinsic that will be + supported at some point. */ +static __inline int _xbegin() { + int res = -1; + +#if KMP_OS_WINDOWS +#if KMP_ARCH_X86_64 + _asm { + _emit 0xC7 + _emit 0xF8 + _emit 2 + _emit 0 + _emit 0 + _emit 0 + jmp L2 + mov res, eax + L2: + } +#else /* IA32 */ + _asm { + _emit 0xC7 + _emit 0xF8 + _emit 2 + _emit 0 + _emit 0 + _emit 0 + jmp L2 + mov res, eax + L2: + } +#endif // KMP_ARCH_X86_64 +#else + /* Note that %eax must be noted as killed (clobbered), because the XSR is + returned in %eax(%rax) on abort. Other register values are restored, so + don't need to be killed. + + We must also mark 'res' as an input and an output, since otherwise + 'res=-1' may be dropped as being dead, whereas we do need the assignment on + the successful (i.e., non-abort) path. */ + __asm__ volatile("1: .byte 0xC7; .byte 0xF8;\n" + " .long 1f-1b-6\n" + " jmp 2f\n" + "1: movl %%eax,%0\n" + "2:" + : "+r"(res)::"memory", "%eax"); +#endif // KMP_OS_WINDOWS + return res; +} + +/* Transaction end */ +static __inline void _xend() { +#if KMP_OS_WINDOWS + __asm { + _emit 0x0f + _emit 0x01 + _emit 0xd5 + } +#else + __asm__ volatile(".byte 0x0f; .byte 0x01; .byte 0xd5" ::: "memory"); +#endif +} + +/* This is a macro, the argument must be a single byte constant which can be + evaluated by the inline assembler, since it is emitted as a byte into the + assembly code. */ +// clang-format off +#if KMP_OS_WINDOWS +#define _xabort(ARG) _asm _emit 0xc6 _asm _emit 0xf8 _asm _emit ARG +#else +#define _xabort(ARG) \ + __asm__ volatile(".byte 0xC6; .byte 0xF8; .byte " STRINGIZE(ARG):::"memory"); +#endif +// clang-format on +#endif // KMP_COMPILER_ICC && __INTEL_COMPILER >= 1300 + +// Statistics is collected for testing purpose +#if KMP_DEBUG_ADAPTIVE_LOCKS + +// We accumulate speculative lock statistics when the lock is destroyed. We +// keep locks that haven't been destroyed in the liveLocks list so that we can +// grab their statistics too. +static kmp_adaptive_lock_statistics_t destroyedStats; + +// To hold the list of live locks. +static kmp_adaptive_lock_info_t liveLocks; + +// A lock so we can safely update the list of locks. +static kmp_bootstrap_lock_t chain_lock = + KMP_BOOTSTRAP_LOCK_INITIALIZER(chain_lock); + +// Initialize the list of stats. +void __kmp_init_speculative_stats() { + kmp_adaptive_lock_info_t *lck = &liveLocks; + + memset(CCAST(kmp_adaptive_lock_statistics_t *, &(lck->stats)), 0, + sizeof(lck->stats)); + lck->stats.next = lck; + lck->stats.prev = lck; + + KMP_ASSERT(lck->stats.next->stats.prev == lck); + KMP_ASSERT(lck->stats.prev->stats.next == lck); + + __kmp_init_bootstrap_lock(&chain_lock); +} + +// Insert the lock into the circular list +static void __kmp_remember_lock(kmp_adaptive_lock_info_t *lck) { + __kmp_acquire_bootstrap_lock(&chain_lock); + + lck->stats.next = liveLocks.stats.next; + lck->stats.prev = &liveLocks; + + liveLocks.stats.next = lck; + lck->stats.next->stats.prev = lck; + + KMP_ASSERT(lck->stats.next->stats.prev == lck); + KMP_ASSERT(lck->stats.prev->stats.next == lck); + + __kmp_release_bootstrap_lock(&chain_lock); +} + +static void __kmp_forget_lock(kmp_adaptive_lock_info_t *lck) { + KMP_ASSERT(lck->stats.next->stats.prev == lck); + KMP_ASSERT(lck->stats.prev->stats.next == lck); + + kmp_adaptive_lock_info_t *n = lck->stats.next; + kmp_adaptive_lock_info_t *p = lck->stats.prev; + + n->stats.prev = p; + p->stats.next = n; +} + +static void __kmp_zero_speculative_stats(kmp_adaptive_lock_info_t *lck) { + memset(CCAST(kmp_adaptive_lock_statistics_t *, &lck->stats), 0, + sizeof(lck->stats)); + __kmp_remember_lock(lck); +} + +static void __kmp_add_stats(kmp_adaptive_lock_statistics_t *t, + kmp_adaptive_lock_info_t *lck) { + kmp_adaptive_lock_statistics_t volatile *s = &lck->stats; + + t->nonSpeculativeAcquireAttempts += lck->acquire_attempts; + t->successfulSpeculations += s->successfulSpeculations; + t->hardFailedSpeculations += s->hardFailedSpeculations; + t->softFailedSpeculations += s->softFailedSpeculations; + t->nonSpeculativeAcquires += s->nonSpeculativeAcquires; + t->lemmingYields += s->lemmingYields; +} + +static void __kmp_accumulate_speculative_stats(kmp_adaptive_lock_info_t *lck) { + __kmp_acquire_bootstrap_lock(&chain_lock); + + __kmp_add_stats(&destroyedStats, lck); + __kmp_forget_lock(lck); + + __kmp_release_bootstrap_lock(&chain_lock); +} + +static float percent(kmp_uint32 count, kmp_uint32 total) { + return (total == 0) ? 0.0 : (100.0 * count) / total; +} + +static FILE *__kmp_open_stats_file() { + if (strcmp(__kmp_speculative_statsfile, "-") == 0) + return stdout; + + size_t buffLen = KMP_STRLEN(__kmp_speculative_statsfile) + 20; + char buffer[buffLen]; + KMP_SNPRINTF(&buffer[0], buffLen, __kmp_speculative_statsfile, + (kmp_int32)getpid()); + FILE *result = fopen(&buffer[0], "w"); + + // Maybe we should issue a warning here... + return result ? result : stdout; +} + +void __kmp_print_speculative_stats() { + kmp_adaptive_lock_statistics_t total = destroyedStats; + kmp_adaptive_lock_info_t *lck; + + for (lck = liveLocks.stats.next; lck != &liveLocks; lck = lck->stats.next) { + __kmp_add_stats(&total, lck); + } + kmp_adaptive_lock_statistics_t *t = &total; + kmp_uint32 totalSections = + t->nonSpeculativeAcquires + t->successfulSpeculations; + kmp_uint32 totalSpeculations = t->successfulSpeculations + + t->hardFailedSpeculations + + t->softFailedSpeculations; + if (totalSections <= 0) + return; + + FILE *statsFile = __kmp_open_stats_file(); + + fprintf(statsFile, "Speculative lock statistics (all approximate!)\n"); + fprintf(statsFile, " Lock parameters: \n" + " max_soft_retries : %10d\n" + " max_badness : %10d\n", + __kmp_adaptive_backoff_params.max_soft_retries, + __kmp_adaptive_backoff_params.max_badness); + fprintf(statsFile, " Non-speculative acquire attempts : %10d\n", + t->nonSpeculativeAcquireAttempts); + fprintf(statsFile, " Total critical sections : %10d\n", + totalSections); + fprintf(statsFile, " Successful speculations : %10d (%5.1f%%)\n", + t->successfulSpeculations, + percent(t->successfulSpeculations, totalSections)); + fprintf(statsFile, " Non-speculative acquires : %10d (%5.1f%%)\n", + t->nonSpeculativeAcquires, + percent(t->nonSpeculativeAcquires, totalSections)); + fprintf(statsFile, " Lemming yields : %10d\n\n", + t->lemmingYields); + + fprintf(statsFile, " Speculative acquire attempts : %10d\n", + totalSpeculations); + fprintf(statsFile, " Successes : %10d (%5.1f%%)\n", + t->successfulSpeculations, + percent(t->successfulSpeculations, totalSpeculations)); + fprintf(statsFile, " Soft failures : %10d (%5.1f%%)\n", + t->softFailedSpeculations, + percent(t->softFailedSpeculations, totalSpeculations)); + fprintf(statsFile, " Hard failures : %10d (%5.1f%%)\n", + t->hardFailedSpeculations, + percent(t->hardFailedSpeculations, totalSpeculations)); + + if (statsFile != stdout) + fclose(statsFile); +} + +#define KMP_INC_STAT(lck, stat) (lck->lk.adaptive.stats.stat++) +#else +#define KMP_INC_STAT(lck, stat) + +#endif // KMP_DEBUG_ADAPTIVE_LOCKS + +static inline bool __kmp_is_unlocked_queuing_lock(kmp_queuing_lock_t *lck) { + // It is enough to check that the head_id is zero. + // We don't also need to check the tail. + bool res = lck->lk.head_id == 0; + +// We need a fence here, since we must ensure that no memory operations +// from later in this thread float above that read. +#if KMP_COMPILER_ICC + _mm_mfence(); +#else + __sync_synchronize(); +#endif + + return res; +} + +// Functions for manipulating the badness +static __inline void +__kmp_update_badness_after_success(kmp_adaptive_lock_t *lck) { + // Reset the badness to zero so we eagerly try to speculate again + lck->lk.adaptive.badness = 0; + KMP_INC_STAT(lck, successfulSpeculations); +} + +// Create a bit mask with one more set bit. +static __inline void __kmp_step_badness(kmp_adaptive_lock_t *lck) { + kmp_uint32 newBadness = (lck->lk.adaptive.badness << 1) | 1; + if (newBadness > lck->lk.adaptive.max_badness) { + return; + } else { + lck->lk.adaptive.badness = newBadness; + } +} + +// Check whether speculation should be attempted. +static __inline int __kmp_should_speculate(kmp_adaptive_lock_t *lck, + kmp_int32 gtid) { + kmp_uint32 badness = lck->lk.adaptive.badness; + kmp_uint32 attempts = lck->lk.adaptive.acquire_attempts; + int res = (attempts & badness) == 0; + return res; +} + +// Attempt to acquire only the speculative lock. +// Does not back off to the non-speculative lock. +static int __kmp_test_adaptive_lock_only(kmp_adaptive_lock_t *lck, + kmp_int32 gtid) { + int retries = lck->lk.adaptive.max_soft_retries; + + // We don't explicitly count the start of speculation, rather we record the + // results (success, hard fail, soft fail). The sum of all of those is the + // total number of times we started speculation since all speculations must + // end one of those ways. + do { + kmp_uint32 status = _xbegin(); + // Switch this in to disable actual speculation but exercise at least some + // of the rest of the code. Useful for debugging... + // kmp_uint32 status = _XABORT_NESTED; + + if (status == _XBEGIN_STARTED) { + /* We have successfully started speculation. Check that no-one acquired + the lock for real between when we last looked and now. This also gets + the lock cache line into our read-set, which we need so that we'll + abort if anyone later claims it for real. */ + if (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) { + // Lock is now visibly acquired, so someone beat us to it. Abort the + // transaction so we'll restart from _xbegin with the failure status. + _xabort(0x01); + KMP_ASSERT2(0, "should not get here"); + } + return 1; // Lock has been acquired (speculatively) + } else { + // We have aborted, update the statistics + if (status & SOFT_ABORT_MASK) { + KMP_INC_STAT(lck, softFailedSpeculations); + // and loop round to retry. + } else { + KMP_INC_STAT(lck, hardFailedSpeculations); + // Give up if we had a hard failure. + break; + } + } + } while (retries--); // Loop while we have retries, and didn't fail hard. + + // Either we had a hard failure or we didn't succeed softly after + // the full set of attempts, so back off the badness. + __kmp_step_badness(lck); + return 0; +} + +// Attempt to acquire the speculative lock, or back off to the non-speculative +// one if the speculative lock cannot be acquired. +// We can succeed speculatively, non-speculatively, or fail. +static int __kmp_test_adaptive_lock(kmp_adaptive_lock_t *lck, kmp_int32 gtid) { + // First try to acquire the lock speculatively + if (__kmp_should_speculate(lck, gtid) && + __kmp_test_adaptive_lock_only(lck, gtid)) + return 1; + + // Speculative acquisition failed, so try to acquire it non-speculatively. + // Count the non-speculative acquire attempt + lck->lk.adaptive.acquire_attempts++; + + // Use base, non-speculative lock. + if (__kmp_test_queuing_lock(GET_QLK_PTR(lck), gtid)) { + KMP_INC_STAT(lck, nonSpeculativeAcquires); + return 1; // Lock is acquired (non-speculatively) + } else { + return 0; // Failed to acquire the lock, it's already visibly locked. + } +} + +static int __kmp_test_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_lock"; + if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) { + KMP_FATAL(LockIsUninitialized, func); + } + + int retval = __kmp_test_adaptive_lock(lck, gtid); + + if (retval) { + lck->lk.qlk.owner_id = gtid + 1; + } + return retval; +} + +// Block until we can acquire a speculative, adaptive lock. We check whether we +// should be trying to speculate. If we should be, we check the real lock to see +// if it is free, and, if not, pause without attempting to acquire it until it +// is. Then we try the speculative acquire. This means that although we suffer +// from lemmings a little (because all we can't acquire the lock speculatively +// until the queue of threads waiting has cleared), we don't get into a state +// where we can never acquire the lock speculatively (because we force the queue +// to clear by preventing new arrivals from entering the queue). This does mean +// that when we're trying to break lemmings, the lock is no longer fair. However +// OpenMP makes no guarantee that its locks are fair, so this isn't a real +// problem. +static void __kmp_acquire_adaptive_lock(kmp_adaptive_lock_t *lck, + kmp_int32 gtid) { + if (__kmp_should_speculate(lck, gtid)) { + if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) { + if (__kmp_test_adaptive_lock_only(lck, gtid)) + return; + // We tried speculation and failed, so give up. + } else { + // We can't try speculation until the lock is free, so we pause here + // (without suspending on the queueing lock, to allow it to drain, then + // try again. All other threads will also see the same result for + // shouldSpeculate, so will be doing the same if they try to claim the + // lock from now on. + while (!__kmp_is_unlocked_queuing_lock(GET_QLK_PTR(lck))) { + KMP_INC_STAT(lck, lemmingYields); + __kmp_yield(TRUE); + } + + if (__kmp_test_adaptive_lock_only(lck, gtid)) + return; + } + } + + // Speculative acquisition failed, so acquire it non-speculatively. + // Count the non-speculative acquire attempt + lck->lk.adaptive.acquire_attempts++; + + __kmp_acquire_queuing_lock_timed_template<FALSE>(GET_QLK_PTR(lck), gtid); + // We have acquired the base lock, so count that. + KMP_INC_STAT(lck, nonSpeculativeAcquires); + ANNOTATE_QUEUING_ACQUIRED(lck); +} + +static void __kmp_acquire_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_lock"; + if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == gtid) { + KMP_FATAL(LockIsAlreadyOwned, func); + } + + __kmp_acquire_adaptive_lock(lck, gtid); + + lck->lk.qlk.owner_id = gtid + 1; +} + +static int __kmp_release_adaptive_lock(kmp_adaptive_lock_t *lck, + kmp_int32 gtid) { + if (__kmp_is_unlocked_queuing_lock(GET_QLK_PTR( + lck))) { // If the lock doesn't look claimed we must be speculating. + // (Or the user's code is buggy and they're releasing without locking; + // if we had XTEST we'd be able to check that case...) + _xend(); // Exit speculation + __kmp_update_badness_after_success(lck); + } else { // Since the lock *is* visibly locked we're not speculating, + // so should use the underlying lock's release scheme. + __kmp_release_queuing_lock(GET_QLK_PTR(lck), gtid); + } + return KMP_LOCK_RELEASED; +} + +static int __kmp_release_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_lock"; + KMP_MB(); /* in case another processor initialized lock */ + if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != gtid) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + lck->lk.qlk.owner_id = 0; + __kmp_release_adaptive_lock(lck, gtid); + return KMP_LOCK_RELEASED; +} + +static void __kmp_init_adaptive_lock(kmp_adaptive_lock_t *lck) { + __kmp_init_queuing_lock(GET_QLK_PTR(lck)); + lck->lk.adaptive.badness = 0; + lck->lk.adaptive.acquire_attempts = 0; // nonSpeculativeAcquireAttempts = 0; + lck->lk.adaptive.max_soft_retries = + __kmp_adaptive_backoff_params.max_soft_retries; + lck->lk.adaptive.max_badness = __kmp_adaptive_backoff_params.max_badness; +#if KMP_DEBUG_ADAPTIVE_LOCKS + __kmp_zero_speculative_stats(&lck->lk.adaptive); +#endif + KA_TRACE(1000, ("__kmp_init_adaptive_lock: lock %p initialized\n", lck)); +} + +static void __kmp_init_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck) { + __kmp_init_adaptive_lock(lck); +} + +static void __kmp_destroy_adaptive_lock(kmp_adaptive_lock_t *lck) { +#if KMP_DEBUG_ADAPTIVE_LOCKS + __kmp_accumulate_speculative_stats(&lck->lk.adaptive); +#endif + __kmp_destroy_queuing_lock(GET_QLK_PTR(lck)); + // Nothing needed for the speculative part. +} + +static void __kmp_destroy_adaptive_lock_with_checks(kmp_adaptive_lock_t *lck) { + char const *const func = "omp_destroy_lock"; + if (lck->lk.qlk.initialized != GET_QLK_PTR(lck)) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_get_queuing_lock_owner(GET_QLK_PTR(lck)) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_adaptive_lock(lck); +} + +#endif // KMP_USE_ADAPTIVE_LOCKS + +/* ------------------------------------------------------------------------ */ +/* DRDPA ticket locks */ +/* "DRDPA" means Dynamically Reconfigurable Distributed Polling Area */ + +static kmp_int32 __kmp_get_drdpa_lock_owner(kmp_drdpa_lock_t *lck) { + return lck->lk.owner_id - 1; +} + +static inline bool __kmp_is_drdpa_lock_nestable(kmp_drdpa_lock_t *lck) { + return lck->lk.depth_locked != -1; +} + +__forceinline static int +__kmp_acquire_drdpa_lock_timed_template(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { + kmp_uint64 ticket = KMP_ATOMIC_INC(&lck->lk.next_ticket); + kmp_uint64 mask = lck->lk.mask; // atomic load + std::atomic<kmp_uint64> *polls = lck->lk.polls; + +#ifdef USE_LOCK_PROFILE + if (polls[ticket & mask] != ticket) + __kmp_printf("LOCK CONTENTION: %p\n", lck); +/* else __kmp_printf( "." );*/ +#endif /* USE_LOCK_PROFILE */ + + // Now spin-wait, but reload the polls pointer and mask, in case the + // polling area has been reconfigured. Unless it is reconfigured, the + // reloads stay in L1 cache and are cheap. + // + // Keep this code in sync with KMP_WAIT_YIELD, in kmp_dispatch.cpp !!! + // + // The current implementation of KMP_WAIT_YIELD doesn't allow for mask + // and poll to be re-read every spin iteration. + kmp_uint32 spins; + + KMP_FSYNC_PREPARE(lck); + KMP_INIT_YIELD(spins); + while (polls[ticket & mask] < ticket) { // atomic load + // If we are oversubscribed, + // or have waited a bit (and KMP_LIBRARY=turnaround), then yield. + // CPU Pause is in the macros for yield. + // + KMP_YIELD(TCR_4(__kmp_nth) > + (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)); + KMP_YIELD_SPIN(spins); + + // Re-read the mask and the poll pointer from the lock structure. + // + // Make certain that "mask" is read before "polls" !!! + // + // If another thread picks reconfigures the polling area and updates their + // values, and we get the new value of mask and the old polls pointer, we + // could access memory beyond the end of the old polling area. + mask = lck->lk.mask; // atomic load + polls = lck->lk.polls; // atomic load + } + + // Critical section starts here + KMP_FSYNC_ACQUIRED(lck); + KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld acquired lock %p\n", + ticket, lck)); + lck->lk.now_serving = ticket; // non-volatile store + + // Deallocate a garbage polling area if we know that we are the last + // thread that could possibly access it. + // + // The >= check is in case __kmp_test_drdpa_lock() allocated the cleanup + // ticket. + if ((lck->lk.old_polls != NULL) && (ticket >= lck->lk.cleanup_ticket)) { + __kmp_free(lck->lk.old_polls); + lck->lk.old_polls = NULL; + lck->lk.cleanup_ticket = 0; + } + + // Check to see if we should reconfigure the polling area. + // If there is still a garbage polling area to be deallocated from a + // previous reconfiguration, let a later thread reconfigure it. + if (lck->lk.old_polls == NULL) { + bool reconfigure = false; + std::atomic<kmp_uint64> *old_polls = polls; + kmp_uint32 num_polls = TCR_4(lck->lk.num_polls); + + if (TCR_4(__kmp_nth) > + (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc)) { + // We are in oversubscription mode. Contract the polling area + // down to a single location, if that hasn't been done already. + if (num_polls > 1) { + reconfigure = true; + num_polls = TCR_4(lck->lk.num_polls); + mask = 0; + num_polls = 1; + polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls * + sizeof(*polls)); + polls[0] = ticket; + } + } else { + // We are in under/fully subscribed mode. Check the number of + // threads waiting on the lock. The size of the polling area + // should be at least the number of threads waiting. + kmp_uint64 num_waiting = TCR_8(lck->lk.next_ticket) - ticket - 1; + if (num_waiting > num_polls) { + kmp_uint32 old_num_polls = num_polls; + reconfigure = true; + do { + mask = (mask << 1) | 1; + num_polls *= 2; + } while (num_polls <= num_waiting); + + // Allocate the new polling area, and copy the relevant portion + // of the old polling area to the new area. __kmp_allocate() + // zeroes the memory it allocates, and most of the old area is + // just zero padding, so we only copy the release counters. + polls = (std::atomic<kmp_uint64> *)__kmp_allocate(num_polls * + sizeof(*polls)); + kmp_uint32 i; + for (i = 0; i < old_num_polls; i++) { + polls[i].store(old_polls[i]); + } + } + } + + if (reconfigure) { + // Now write the updated fields back to the lock structure. + // + // Make certain that "polls" is written before "mask" !!! + // + // If another thread picks up the new value of mask and the old polls + // pointer , it could access memory beyond the end of the old polling + // area. + // + // On x86, we need memory fences. + KA_TRACE(1000, ("__kmp_acquire_drdpa_lock: ticket #%lld reconfiguring " + "lock %p to %d polls\n", + ticket, lck, num_polls)); + + lck->lk.old_polls = old_polls; + lck->lk.polls = polls; // atomic store + + KMP_MB(); + + lck->lk.num_polls = num_polls; + lck->lk.mask = mask; // atomic store + + KMP_MB(); + + // Only after the new polling area and mask have been flushed + // to main memory can we update the cleanup ticket field. + // + // volatile load / non-volatile store + lck->lk.cleanup_ticket = lck->lk.next_ticket; + } + } + return KMP_LOCK_ACQUIRED_FIRST; +} + +int __kmp_acquire_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { + int retval = __kmp_acquire_drdpa_lock_timed_template(lck, gtid); + ANNOTATE_DRDPA_ACQUIRED(lck); + return retval; +} + +static int __kmp_acquire_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_drdpa_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) == gtid)) { + KMP_FATAL(LockIsAlreadyOwned, func); + } + + __kmp_acquire_drdpa_lock(lck, gtid); + + lck->lk.owner_id = gtid + 1; + return KMP_LOCK_ACQUIRED_FIRST; +} + +int __kmp_test_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { + // First get a ticket, then read the polls pointer and the mask. + // The polls pointer must be read before the mask!!! (See above) + kmp_uint64 ticket = lck->lk.next_ticket; // atomic load + std::atomic<kmp_uint64> *polls = lck->lk.polls; + kmp_uint64 mask = lck->lk.mask; // atomic load + if (polls[ticket & mask] == ticket) { + kmp_uint64 next_ticket = ticket + 1; + if (__kmp_atomic_compare_store_acq(&lck->lk.next_ticket, ticket, + next_ticket)) { + KMP_FSYNC_ACQUIRED(lck); + KA_TRACE(1000, ("__kmp_test_drdpa_lock: ticket #%lld acquired lock %p\n", + ticket, lck)); + lck->lk.now_serving = ticket; // non-volatile store + + // Since no threads are waiting, there is no possibility that we would + // want to reconfigure the polling area. We might have the cleanup ticket + // value (which says that it is now safe to deallocate old_polls), but + // we'll let a later thread which calls __kmp_acquire_lock do that - this + // routine isn't supposed to block, and we would risk blocks if we called + // __kmp_free() to do the deallocation. + return TRUE; + } + } + return FALSE; +} + +static int __kmp_test_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_drdpa_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + + int retval = __kmp_test_drdpa_lock(lck, gtid); + + if (retval) { + lck->lk.owner_id = gtid + 1; + } + return retval; +} + +int __kmp_release_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { + // Read the ticket value from the lock data struct, then the polls pointer and + // the mask. The polls pointer must be read before the mask!!! (See above) + kmp_uint64 ticket = lck->lk.now_serving + 1; // non-atomic load + std::atomic<kmp_uint64> *polls = lck->lk.polls; // atomic load + kmp_uint64 mask = lck->lk.mask; // atomic load + KA_TRACE(1000, ("__kmp_release_drdpa_lock: ticket #%lld released lock %p\n", + ticket - 1, lck)); + KMP_FSYNC_RELEASING(lck); + ANNOTATE_DRDPA_RELEASED(lck); + polls[ticket & mask] = ticket; // atomic store + return KMP_LOCK_RELEASED; +} + +static int __kmp_release_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_lock"; + KMP_MB(); /* in case another processor initialized lock */ + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_drdpa_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_drdpa_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if ((gtid >= 0) && (__kmp_get_drdpa_lock_owner(lck) >= 0) && + (__kmp_get_drdpa_lock_owner(lck) != gtid)) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + lck->lk.owner_id = 0; + return __kmp_release_drdpa_lock(lck, gtid); +} + +void __kmp_init_drdpa_lock(kmp_drdpa_lock_t *lck) { + lck->lk.location = NULL; + lck->lk.mask = 0; + lck->lk.num_polls = 1; + lck->lk.polls = (std::atomic<kmp_uint64> *)__kmp_allocate( + lck->lk.num_polls * sizeof(*(lck->lk.polls))); + lck->lk.cleanup_ticket = 0; + lck->lk.old_polls = NULL; + lck->lk.next_ticket = 0; + lck->lk.now_serving = 0; + lck->lk.owner_id = 0; // no thread owns the lock. + lck->lk.depth_locked = -1; // >= 0 for nestable locks, -1 for simple locks. + lck->lk.initialized = lck; + + KA_TRACE(1000, ("__kmp_init_drdpa_lock: lock %p initialized\n", lck)); +} + +static void __kmp_init_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) { + __kmp_init_drdpa_lock(lck); +} + +void __kmp_destroy_drdpa_lock(kmp_drdpa_lock_t *lck) { + lck->lk.initialized = NULL; + lck->lk.location = NULL; + if (lck->lk.polls.load() != NULL) { + __kmp_free(lck->lk.polls.load()); + lck->lk.polls = NULL; + } + if (lck->lk.old_polls != NULL) { + __kmp_free(lck->lk.old_polls); + lck->lk.old_polls = NULL; + } + lck->lk.mask = 0; + lck->lk.num_polls = 0; + lck->lk.cleanup_ticket = 0; + lck->lk.next_ticket = 0; + lck->lk.now_serving = 0; + lck->lk.owner_id = 0; + lck->lk.depth_locked = -1; +} + +static void __kmp_destroy_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) { + char const *const func = "omp_destroy_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (__kmp_is_drdpa_lock_nestable(lck)) { + KMP_FATAL(LockNestableUsedAsSimple, func); + } + if (__kmp_get_drdpa_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_drdpa_lock(lck); +} + +// nested drdpa ticket locks + +int __kmp_acquire_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_drdpa_lock_owner(lck) == gtid) { + lck->lk.depth_locked += 1; + return KMP_LOCK_ACQUIRED_NEXT; + } else { + __kmp_acquire_drdpa_lock_timed_template(lck, gtid); + ANNOTATE_DRDPA_ACQUIRED(lck); + KMP_MB(); + lck->lk.depth_locked = 1; + KMP_MB(); + lck->lk.owner_id = gtid + 1; + return KMP_LOCK_ACQUIRED_FIRST; + } +} + +static void __kmp_acquire_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_set_nest_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_drdpa_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + __kmp_acquire_nested_drdpa_lock(lck, gtid); +} + +int __kmp_test_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { + int retval; + + KMP_DEBUG_ASSERT(gtid >= 0); + + if (__kmp_get_drdpa_lock_owner(lck) == gtid) { + retval = ++lck->lk.depth_locked; + } else if (!__kmp_test_drdpa_lock(lck, gtid)) { + retval = 0; + } else { + KMP_MB(); + retval = lck->lk.depth_locked = 1; + KMP_MB(); + lck->lk.owner_id = gtid + 1; + } + return retval; +} + +static int __kmp_test_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_test_nest_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_drdpa_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + return __kmp_test_nested_drdpa_lock(lck, gtid); +} + +int __kmp_release_nested_drdpa_lock(kmp_drdpa_lock_t *lck, kmp_int32 gtid) { + KMP_DEBUG_ASSERT(gtid >= 0); + + KMP_MB(); + if (--(lck->lk.depth_locked) == 0) { + KMP_MB(); + lck->lk.owner_id = 0; + __kmp_release_drdpa_lock(lck, gtid); + return KMP_LOCK_RELEASED; + } + return KMP_LOCK_STILL_HELD; +} + +static int __kmp_release_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck, + kmp_int32 gtid) { + char const *const func = "omp_unset_nest_lock"; + KMP_MB(); /* in case another processor initialized lock */ + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_drdpa_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_drdpa_lock_owner(lck) == -1) { + KMP_FATAL(LockUnsettingFree, func); + } + if (__kmp_get_drdpa_lock_owner(lck) != gtid) { + KMP_FATAL(LockUnsettingSetByAnother, func); + } + return __kmp_release_nested_drdpa_lock(lck, gtid); +} + +void __kmp_init_nested_drdpa_lock(kmp_drdpa_lock_t *lck) { + __kmp_init_drdpa_lock(lck); + lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks +} + +static void __kmp_init_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) { + __kmp_init_nested_drdpa_lock(lck); +} + +void __kmp_destroy_nested_drdpa_lock(kmp_drdpa_lock_t *lck) { + __kmp_destroy_drdpa_lock(lck); + lck->lk.depth_locked = 0; +} + +static void __kmp_destroy_nested_drdpa_lock_with_checks(kmp_drdpa_lock_t *lck) { + char const *const func = "omp_destroy_nest_lock"; + if (lck->lk.initialized != lck) { + KMP_FATAL(LockIsUninitialized, func); + } + if (!__kmp_is_drdpa_lock_nestable(lck)) { + KMP_FATAL(LockSimpleUsedAsNestable, func); + } + if (__kmp_get_drdpa_lock_owner(lck) != -1) { + KMP_FATAL(LockStillOwned, func); + } + __kmp_destroy_nested_drdpa_lock(lck); +} + +// access functions to fields which don't exist for all lock kinds. + +static int __kmp_is_drdpa_lock_initialized(kmp_drdpa_lock_t *lck) { + return lck == lck->lk.initialized; +} + +static const ident_t *__kmp_get_drdpa_lock_location(kmp_drdpa_lock_t *lck) { + return lck->lk.location; +} + +static void __kmp_set_drdpa_lock_location(kmp_drdpa_lock_t *lck, + const ident_t *loc) { + lck->lk.location = loc; +} + +static kmp_lock_flags_t __kmp_get_drdpa_lock_flags(kmp_drdpa_lock_t *lck) { + return lck->lk.flags; +} + +static void __kmp_set_drdpa_lock_flags(kmp_drdpa_lock_t *lck, + kmp_lock_flags_t flags) { + lck->lk.flags = flags; +} + +// Time stamp counter +#if KMP_ARCH_X86 || KMP_ARCH_X86_64 +#define __kmp_tsc() __kmp_hardware_timestamp() +// Runtime's default backoff parameters +kmp_backoff_t __kmp_spin_backoff_params = {1, 4096, 100}; +#else +// Use nanoseconds for other platforms +extern kmp_uint64 __kmp_now_nsec(); +kmp_backoff_t __kmp_spin_backoff_params = {1, 256, 100}; +#define __kmp_tsc() __kmp_now_nsec() +#endif + +// A useful predicate for dealing with timestamps that may wrap. +// Is a before b? Since the timestamps may wrap, this is asking whether it's +// shorter to go clockwise from a to b around the clock-face, or anti-clockwise. +// Times where going clockwise is less distance than going anti-clockwise +// are in the future, others are in the past. e.g. a = MAX-1, b = MAX+1 (=0), +// then a > b (true) does not mean a reached b; whereas signed(a) = -2, +// signed(b) = 0 captures the actual difference +static inline bool before(kmp_uint64 a, kmp_uint64 b) { + return ((kmp_int64)b - (kmp_int64)a) > 0; +} + +// Truncated binary exponential backoff function +void __kmp_spin_backoff(kmp_backoff_t *boff) { + // We could flatten this loop, but making it a nested loop gives better result + kmp_uint32 i; + for (i = boff->step; i > 0; i--) { + kmp_uint64 goal = __kmp_tsc() + boff->min_tick; + do { + KMP_CPU_PAUSE(); + } while (before(__kmp_tsc(), goal)); + } + boff->step = (boff->step << 1 | 1) & (boff->max_backoff - 1); +} + +#if KMP_USE_DYNAMIC_LOCK + +// Direct lock initializers. It simply writes a tag to the low 8 bits of the +// lock word. +static void __kmp_init_direct_lock(kmp_dyna_lock_t *lck, + kmp_dyna_lockseq_t seq) { + TCW_4(*lck, KMP_GET_D_TAG(seq)); + KA_TRACE( + 20, + ("__kmp_init_direct_lock: initialized direct lock with type#%d\n", seq)); +} + +#if KMP_USE_TSX + +// HLE lock functions - imported from the testbed runtime. +#define HLE_ACQUIRE ".byte 0xf2;" +#define HLE_RELEASE ".byte 0xf3;" + +static inline kmp_uint32 swap4(kmp_uint32 volatile *p, kmp_uint32 v) { + __asm__ volatile(HLE_ACQUIRE "xchg %1,%0" : "+r"(v), "+m"(*p) : : "memory"); + return v; +} + +static void __kmp_destroy_hle_lock(kmp_dyna_lock_t *lck) { TCW_4(*lck, 0); } + +static void __kmp_acquire_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) { + // Use gtid for KMP_LOCK_BUSY if necessary + if (swap4(lck, KMP_LOCK_BUSY(1, hle)) != KMP_LOCK_FREE(hle)) { + int delay = 1; + do { + while (*(kmp_uint32 volatile *)lck != KMP_LOCK_FREE(hle)) { + for (int i = delay; i != 0; --i) + KMP_CPU_PAUSE(); + delay = ((delay << 1) | 1) & 7; + } + } while (swap4(lck, KMP_LOCK_BUSY(1, hle)) != KMP_LOCK_FREE(hle)); + } +} + +static void __kmp_acquire_hle_lock_with_checks(kmp_dyna_lock_t *lck, + kmp_int32 gtid) { + __kmp_acquire_hle_lock(lck, gtid); // TODO: add checks +} + +static int __kmp_release_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) { + __asm__ volatile(HLE_RELEASE "movl %1,%0" + : "=m"(*lck) + : "r"(KMP_LOCK_FREE(hle)) + : "memory"); + return KMP_LOCK_RELEASED; +} + +static int __kmp_release_hle_lock_with_checks(kmp_dyna_lock_t *lck, + kmp_int32 gtid) { + return __kmp_release_hle_lock(lck, gtid); // TODO: add checks +} + +static int __kmp_test_hle_lock(kmp_dyna_lock_t *lck, kmp_int32 gtid) { + return swap4(lck, KMP_LOCK_BUSY(1, hle)) == KMP_LOCK_FREE(hle); +} + +static int __kmp_test_hle_lock_with_checks(kmp_dyna_lock_t *lck, + kmp_int32 gtid) { + return __kmp_test_hle_lock(lck, gtid); // TODO: add checks +} + +static void __kmp_init_rtm_lock(kmp_queuing_lock_t *lck) { + __kmp_init_queuing_lock(lck); +} + +static void __kmp_destroy_rtm_lock(kmp_queuing_lock_t *lck) { + __kmp_destroy_queuing_lock(lck); +} + +static void __kmp_acquire_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { + unsigned retries = 3, status; + do { + status = _xbegin(); + if (status == _XBEGIN_STARTED) { + if (__kmp_is_unlocked_queuing_lock(lck)) + return; + _xabort(0xff); + } + if ((status & _XABORT_EXPLICIT) && _XABORT_CODE(status) == 0xff) { + // Wait until lock becomes free + while (!__kmp_is_unlocked_queuing_lock(lck)) + __kmp_yield(TRUE); + } else if (!(status & _XABORT_RETRY)) + break; + } while (retries--); + + // Fall-back non-speculative lock (xchg) + __kmp_acquire_queuing_lock(lck, gtid); +} + +static void __kmp_acquire_rtm_lock_with_checks(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + __kmp_acquire_rtm_lock(lck, gtid); +} + +static int __kmp_release_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { + if (__kmp_is_unlocked_queuing_lock(lck)) { + // Releasing from speculation + _xend(); + } else { + // Releasing from a real lock + __kmp_release_queuing_lock(lck, gtid); + } + return KMP_LOCK_RELEASED; +} + +static int __kmp_release_rtm_lock_with_checks(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + return __kmp_release_rtm_lock(lck, gtid); +} + +static int __kmp_test_rtm_lock(kmp_queuing_lock_t *lck, kmp_int32 gtid) { + unsigned retries = 3, status; + do { + status = _xbegin(); + if (status == _XBEGIN_STARTED && __kmp_is_unlocked_queuing_lock(lck)) { + return 1; + } + if (!(status & _XABORT_RETRY)) + break; + } while (retries--); + + return (__kmp_is_unlocked_queuing_lock(lck)) ? 1 : 0; +} + +static int __kmp_test_rtm_lock_with_checks(kmp_queuing_lock_t *lck, + kmp_int32 gtid) { + return __kmp_test_rtm_lock(lck, gtid); +} + +#endif // KMP_USE_TSX + +// Entry functions for indirect locks (first element of direct lock jump tables) +static void __kmp_init_indirect_lock(kmp_dyna_lock_t *l, + kmp_dyna_lockseq_t tag); +static void __kmp_destroy_indirect_lock(kmp_dyna_lock_t *lock); +static int __kmp_set_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32); +static int __kmp_unset_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32); +static int __kmp_test_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32); +static int __kmp_set_indirect_lock_with_checks(kmp_dyna_lock_t *lock, + kmp_int32); +static int __kmp_unset_indirect_lock_with_checks(kmp_dyna_lock_t *lock, + kmp_int32); +static int __kmp_test_indirect_lock_with_checks(kmp_dyna_lock_t *lock, + kmp_int32); + +// Jump tables for the indirect lock functions +// Only fill in the odd entries, that avoids the need to shift out the low bit + +// init functions +#define expand(l, op) 0, __kmp_init_direct_lock, +void (*__kmp_direct_init[])(kmp_dyna_lock_t *, kmp_dyna_lockseq_t) = { + __kmp_init_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, init)}; +#undef expand + +// destroy functions +#define expand(l, op) 0, (void (*)(kmp_dyna_lock_t *))__kmp_##op##_##l##_lock, +void (*__kmp_direct_destroy[])(kmp_dyna_lock_t *) = { + __kmp_destroy_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, destroy)}; +#undef expand + +// set/acquire functions +#define expand(l, op) \ + 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock, +static int (*direct_set[])(kmp_dyna_lock_t *, kmp_int32) = { + __kmp_set_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, acquire)}; +#undef expand +#define expand(l, op) \ + 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock_with_checks, +static int (*direct_set_check[])(kmp_dyna_lock_t *, kmp_int32) = { + __kmp_set_indirect_lock_with_checks, 0, + KMP_FOREACH_D_LOCK(expand, acquire)}; +#undef expand + +// unset/release and test functions +#define expand(l, op) \ + 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock, +static int (*direct_unset[])(kmp_dyna_lock_t *, kmp_int32) = { + __kmp_unset_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, release)}; +static int (*direct_test[])(kmp_dyna_lock_t *, kmp_int32) = { + __kmp_test_indirect_lock, 0, KMP_FOREACH_D_LOCK(expand, test)}; +#undef expand +#define expand(l, op) \ + 0, (int (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock_with_checks, +static int (*direct_unset_check[])(kmp_dyna_lock_t *, kmp_int32) = { + __kmp_unset_indirect_lock_with_checks, 0, + KMP_FOREACH_D_LOCK(expand, release)}; +static int (*direct_test_check[])(kmp_dyna_lock_t *, kmp_int32) = { + __kmp_test_indirect_lock_with_checks, 0, KMP_FOREACH_D_LOCK(expand, test)}; +#undef expand + +// Exposes only one set of jump tables (*lock or *lock_with_checks). +int (*(*__kmp_direct_set))(kmp_dyna_lock_t *, kmp_int32) = 0; +int (*(*__kmp_direct_unset))(kmp_dyna_lock_t *, kmp_int32) = 0; +int (*(*__kmp_direct_test))(kmp_dyna_lock_t *, kmp_int32) = 0; + +// Jump tables for the indirect lock functions +#define expand(l, op) (void (*)(kmp_user_lock_p)) __kmp_##op##_##l##_##lock, +void (*__kmp_indirect_init[])(kmp_user_lock_p) = { + KMP_FOREACH_I_LOCK(expand, init)}; +void (*__kmp_indirect_destroy[])(kmp_user_lock_p) = { + KMP_FOREACH_I_LOCK(expand, destroy)}; +#undef expand + +// set/acquire functions +#define expand(l, op) \ + (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock, +static int (*indirect_set[])(kmp_user_lock_p, + kmp_int32) = {KMP_FOREACH_I_LOCK(expand, acquire)}; +#undef expand +#define expand(l, op) \ + (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock_with_checks, +static int (*indirect_set_check[])(kmp_user_lock_p, kmp_int32) = { + KMP_FOREACH_I_LOCK(expand, acquire)}; +#undef expand + +// unset/release and test functions +#define expand(l, op) \ + (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock, +static int (*indirect_unset[])(kmp_user_lock_p, kmp_int32) = { + KMP_FOREACH_I_LOCK(expand, release)}; +static int (*indirect_test[])(kmp_user_lock_p, + kmp_int32) = {KMP_FOREACH_I_LOCK(expand, test)}; +#undef expand +#define expand(l, op) \ + (int (*)(kmp_user_lock_p, kmp_int32)) __kmp_##op##_##l##_##lock_with_checks, +static int (*indirect_unset_check[])(kmp_user_lock_p, kmp_int32) = { + KMP_FOREACH_I_LOCK(expand, release)}; +static int (*indirect_test_check[])(kmp_user_lock_p, kmp_int32) = { + KMP_FOREACH_I_LOCK(expand, test)}; +#undef expand + +// Exposes only one jump tables (*lock or *lock_with_checks). +int (*(*__kmp_indirect_set))(kmp_user_lock_p, kmp_int32) = 0; +int (*(*__kmp_indirect_unset))(kmp_user_lock_p, kmp_int32) = 0; +int (*(*__kmp_indirect_test))(kmp_user_lock_p, kmp_int32) = 0; + +// Lock index table. +kmp_indirect_lock_table_t __kmp_i_lock_table; + +// Size of indirect locks. +static kmp_uint32 __kmp_indirect_lock_size[KMP_NUM_I_LOCKS] = {0}; + +// Jump tables for lock accessor/modifier. +void (*__kmp_indirect_set_location[KMP_NUM_I_LOCKS])(kmp_user_lock_p, + const ident_t *) = {0}; +void (*__kmp_indirect_set_flags[KMP_NUM_I_LOCKS])(kmp_user_lock_p, + kmp_lock_flags_t) = {0}; +const ident_t *(*__kmp_indirect_get_location[KMP_NUM_I_LOCKS])( + kmp_user_lock_p) = {0}; +kmp_lock_flags_t (*__kmp_indirect_get_flags[KMP_NUM_I_LOCKS])( + kmp_user_lock_p) = {0}; + +// Use different lock pools for different lock types. +static kmp_indirect_lock_t *__kmp_indirect_lock_pool[KMP_NUM_I_LOCKS] = {0}; + +// User lock allocator for dynamically dispatched indirect locks. Every entry of +// the indirect lock table holds the address and type of the allocated indrect +// lock (kmp_indirect_lock_t), and the size of the table doubles when it is +// full. A destroyed indirect lock object is returned to the reusable pool of +// locks, unique to each lock type. +kmp_indirect_lock_t *__kmp_allocate_indirect_lock(void **user_lock, + kmp_int32 gtid, + kmp_indirect_locktag_t tag) { + kmp_indirect_lock_t *lck; + kmp_lock_index_t idx; + + __kmp_acquire_lock(&__kmp_global_lock, gtid); + + if (__kmp_indirect_lock_pool[tag] != NULL) { + // Reuse the allocated and destroyed lock object + lck = __kmp_indirect_lock_pool[tag]; + if (OMP_LOCK_T_SIZE < sizeof(void *)) + idx = lck->lock->pool.index; + __kmp_indirect_lock_pool[tag] = (kmp_indirect_lock_t *)lck->lock->pool.next; + KA_TRACE(20, ("__kmp_allocate_indirect_lock: reusing an existing lock %p\n", + lck)); + } else { + idx = __kmp_i_lock_table.next; + // Check capacity and double the size if it is full + if (idx == __kmp_i_lock_table.size) { + // Double up the space for block pointers + int row = __kmp_i_lock_table.size / KMP_I_LOCK_CHUNK; + kmp_indirect_lock_t **new_table = (kmp_indirect_lock_t **)__kmp_allocate( + 2 * row * sizeof(kmp_indirect_lock_t *)); + KMP_MEMCPY(new_table, __kmp_i_lock_table.table, + row * sizeof(kmp_indirect_lock_t *)); + kmp_indirect_lock_t **old_table = __kmp_i_lock_table.table; + __kmp_i_lock_table.table = new_table; + __kmp_free(old_table); + // Allocate new objects in the new blocks + for (int i = row; i < 2 * row; ++i) + *(__kmp_i_lock_table.table + i) = (kmp_indirect_lock_t *)__kmp_allocate( + KMP_I_LOCK_CHUNK * sizeof(kmp_indirect_lock_t)); + __kmp_i_lock_table.size = 2 * idx; + } + __kmp_i_lock_table.next++; + lck = KMP_GET_I_LOCK(idx); + // Allocate a new base lock object + lck->lock = (kmp_user_lock_p)__kmp_allocate(__kmp_indirect_lock_size[tag]); + KA_TRACE(20, + ("__kmp_allocate_indirect_lock: allocated a new lock %p\n", lck)); + } + + __kmp_release_lock(&__kmp_global_lock, gtid); + + lck->type = tag; + + if (OMP_LOCK_T_SIZE < sizeof(void *)) { + *((kmp_lock_index_t *)user_lock) = idx + << 1; // indirect lock word must be even + } else { + *((kmp_indirect_lock_t **)user_lock) = lck; + } + + return lck; +} + +// User lock lookup for dynamically dispatched locks. +static __forceinline kmp_indirect_lock_t * +__kmp_lookup_indirect_lock(void **user_lock, const char *func) { + if (__kmp_env_consistency_check) { + kmp_indirect_lock_t *lck = NULL; + if (user_lock == NULL) { + KMP_FATAL(LockIsUninitialized, func); + } + if (OMP_LOCK_T_SIZE < sizeof(void *)) { + kmp_lock_index_t idx = KMP_EXTRACT_I_INDEX(user_lock); + if (idx >= __kmp_i_lock_table.size) { + KMP_FATAL(LockIsUninitialized, func); + } + lck = KMP_GET_I_LOCK(idx); + } else { + lck = *((kmp_indirect_lock_t **)user_lock); + } + if (lck == NULL) { + KMP_FATAL(LockIsUninitialized, func); + } + return lck; + } else { + if (OMP_LOCK_T_SIZE < sizeof(void *)) { + return KMP_GET_I_LOCK(KMP_EXTRACT_I_INDEX(user_lock)); + } else { + return *((kmp_indirect_lock_t **)user_lock); + } + } +} + +static void __kmp_init_indirect_lock(kmp_dyna_lock_t *lock, + kmp_dyna_lockseq_t seq) { +#if KMP_USE_ADAPTIVE_LOCKS + if (seq == lockseq_adaptive && !__kmp_cpuinfo.rtm) { + KMP_WARNING(AdaptiveNotSupported, "kmp_lockseq_t", "adaptive"); + seq = lockseq_queuing; + } +#endif +#if KMP_USE_TSX + if (seq == lockseq_rtm && !__kmp_cpuinfo.rtm) { + seq = lockseq_queuing; + } +#endif + kmp_indirect_locktag_t tag = KMP_GET_I_TAG(seq); + kmp_indirect_lock_t *l = + __kmp_allocate_indirect_lock((void **)lock, __kmp_entry_gtid(), tag); + KMP_I_LOCK_FUNC(l, init)(l->lock); + KA_TRACE( + 20, ("__kmp_init_indirect_lock: initialized indirect lock with type#%d\n", + seq)); +} + +static void __kmp_destroy_indirect_lock(kmp_dyna_lock_t *lock) { + kmp_uint32 gtid = __kmp_entry_gtid(); + kmp_indirect_lock_t *l = + __kmp_lookup_indirect_lock((void **)lock, "omp_destroy_lock"); + KMP_I_LOCK_FUNC(l, destroy)(l->lock); + kmp_indirect_locktag_t tag = l->type; + + __kmp_acquire_lock(&__kmp_global_lock, gtid); + + // Use the base lock's space to keep the pool chain. + l->lock->pool.next = (kmp_user_lock_p)__kmp_indirect_lock_pool[tag]; + if (OMP_LOCK_T_SIZE < sizeof(void *)) { + l->lock->pool.index = KMP_EXTRACT_I_INDEX(lock); + } + __kmp_indirect_lock_pool[tag] = l; + + __kmp_release_lock(&__kmp_global_lock, gtid); +} + +static int __kmp_set_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) { + kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock); + return KMP_I_LOCK_FUNC(l, set)(l->lock, gtid); +} + +static int __kmp_unset_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) { + kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock); + return KMP_I_LOCK_FUNC(l, unset)(l->lock, gtid); +} + +static int __kmp_test_indirect_lock(kmp_dyna_lock_t *lock, kmp_int32 gtid) { + kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock); + return KMP_I_LOCK_FUNC(l, test)(l->lock, gtid); +} + +static int __kmp_set_indirect_lock_with_checks(kmp_dyna_lock_t *lock, + kmp_int32 gtid) { + kmp_indirect_lock_t *l = + __kmp_lookup_indirect_lock((void **)lock, "omp_set_lock"); + return KMP_I_LOCK_FUNC(l, set)(l->lock, gtid); +} + +static int __kmp_unset_indirect_lock_with_checks(kmp_dyna_lock_t *lock, + kmp_int32 gtid) { + kmp_indirect_lock_t *l = + __kmp_lookup_indirect_lock((void **)lock, "omp_unset_lock"); + return KMP_I_LOCK_FUNC(l, unset)(l->lock, gtid); +} + +static int __kmp_test_indirect_lock_with_checks(kmp_dyna_lock_t *lock, + kmp_int32 gtid) { + kmp_indirect_lock_t *l = + __kmp_lookup_indirect_lock((void **)lock, "omp_test_lock"); + return KMP_I_LOCK_FUNC(l, test)(l->lock, gtid); +} + +kmp_dyna_lockseq_t __kmp_user_lock_seq = lockseq_queuing; + +// This is used only in kmp_error.cpp when consistency checking is on. +kmp_int32 __kmp_get_user_lock_owner(kmp_user_lock_p lck, kmp_uint32 seq) { + switch (seq) { + case lockseq_tas: + case lockseq_nested_tas: + return __kmp_get_tas_lock_owner((kmp_tas_lock_t *)lck); +#if KMP_USE_FUTEX + case lockseq_futex: + case lockseq_nested_futex: + return __kmp_get_futex_lock_owner((kmp_futex_lock_t *)lck); +#endif + case lockseq_ticket: + case lockseq_nested_ticket: + return __kmp_get_ticket_lock_owner((kmp_ticket_lock_t *)lck); + case lockseq_queuing: + case lockseq_nested_queuing: +#if KMP_USE_ADAPTIVE_LOCKS + case lockseq_adaptive: +#endif + return __kmp_get_queuing_lock_owner((kmp_queuing_lock_t *)lck); + case lockseq_drdpa: + case lockseq_nested_drdpa: + return __kmp_get_drdpa_lock_owner((kmp_drdpa_lock_t *)lck); + default: + return 0; + } +} + +// Initializes data for dynamic user locks. +void __kmp_init_dynamic_user_locks() { + // Initialize jump table for the lock functions + if (__kmp_env_consistency_check) { + __kmp_direct_set = direct_set_check; + __kmp_direct_unset = direct_unset_check; + __kmp_direct_test = direct_test_check; + __kmp_indirect_set = indirect_set_check; + __kmp_indirect_unset = indirect_unset_check; + __kmp_indirect_test = indirect_test_check; + } else { + __kmp_direct_set = direct_set; + __kmp_direct_unset = direct_unset; + __kmp_direct_test = direct_test; + __kmp_indirect_set = indirect_set; + __kmp_indirect_unset = indirect_unset; + __kmp_indirect_test = indirect_test; + } + // If the user locks have already been initialized, then return. Allow the + // switch between different KMP_CONSISTENCY_CHECK values, but do not allocate + // new lock tables if they have already been allocated. + if (__kmp_init_user_locks) + return; + + // Initialize lock index table + __kmp_i_lock_table.size = KMP_I_LOCK_CHUNK; + __kmp_i_lock_table.table = + (kmp_indirect_lock_t **)__kmp_allocate(sizeof(kmp_indirect_lock_t *)); + *(__kmp_i_lock_table.table) = (kmp_indirect_lock_t *)__kmp_allocate( + KMP_I_LOCK_CHUNK * sizeof(kmp_indirect_lock_t)); + __kmp_i_lock_table.next = 0; + + // Indirect lock size + __kmp_indirect_lock_size[locktag_ticket] = sizeof(kmp_ticket_lock_t); + __kmp_indirect_lock_size[locktag_queuing] = sizeof(kmp_queuing_lock_t); +#if KMP_USE_ADAPTIVE_LOCKS + __kmp_indirect_lock_size[locktag_adaptive] = sizeof(kmp_adaptive_lock_t); +#endif + __kmp_indirect_lock_size[locktag_drdpa] = sizeof(kmp_drdpa_lock_t); +#if KMP_USE_TSX + __kmp_indirect_lock_size[locktag_rtm] = sizeof(kmp_queuing_lock_t); +#endif + __kmp_indirect_lock_size[locktag_nested_tas] = sizeof(kmp_tas_lock_t); +#if KMP_USE_FUTEX + __kmp_indirect_lock_size[locktag_nested_futex] = sizeof(kmp_futex_lock_t); +#endif + __kmp_indirect_lock_size[locktag_nested_ticket] = sizeof(kmp_ticket_lock_t); + __kmp_indirect_lock_size[locktag_nested_queuing] = sizeof(kmp_queuing_lock_t); + __kmp_indirect_lock_size[locktag_nested_drdpa] = sizeof(kmp_drdpa_lock_t); + +// Initialize lock accessor/modifier +#define fill_jumps(table, expand, sep) \ + { \ + table[locktag##sep##ticket] = expand(ticket); \ + table[locktag##sep##queuing] = expand(queuing); \ + table[locktag##sep##drdpa] = expand(drdpa); \ + } + +#if KMP_USE_ADAPTIVE_LOCKS +#define fill_table(table, expand) \ + { \ + fill_jumps(table, expand, _); \ + table[locktag_adaptive] = expand(queuing); \ + fill_jumps(table, expand, _nested_); \ + } +#else +#define fill_table(table, expand) \ + { \ + fill_jumps(table, expand, _); \ + fill_jumps(table, expand, _nested_); \ + } +#endif // KMP_USE_ADAPTIVE_LOCKS + +#define expand(l) \ + (void (*)(kmp_user_lock_p, const ident_t *)) __kmp_set_##l##_lock_location + fill_table(__kmp_indirect_set_location, expand); +#undef expand +#define expand(l) \ + (void (*)(kmp_user_lock_p, kmp_lock_flags_t)) __kmp_set_##l##_lock_flags + fill_table(__kmp_indirect_set_flags, expand); +#undef expand +#define expand(l) \ + (const ident_t *(*)(kmp_user_lock_p)) __kmp_get_##l##_lock_location + fill_table(__kmp_indirect_get_location, expand); +#undef expand +#define expand(l) \ + (kmp_lock_flags_t(*)(kmp_user_lock_p)) __kmp_get_##l##_lock_flags + fill_table(__kmp_indirect_get_flags, expand); +#undef expand + + __kmp_init_user_locks = TRUE; +} + +// Clean up the lock table. +void __kmp_cleanup_indirect_user_locks() { + kmp_lock_index_t i; + int k; + + // Clean up locks in the pools first (they were already destroyed before going + // into the pools). + for (k = 0; k < KMP_NUM_I_LOCKS; ++k) { + kmp_indirect_lock_t *l = __kmp_indirect_lock_pool[k]; + while (l != NULL) { + kmp_indirect_lock_t *ll = l; + l = (kmp_indirect_lock_t *)l->lock->pool.next; + KA_TRACE(20, ("__kmp_cleanup_indirect_user_locks: freeing %p from pool\n", + ll)); + __kmp_free(ll->lock); + ll->lock = NULL; + } + __kmp_indirect_lock_pool[k] = NULL; + } + // Clean up the remaining undestroyed locks. + for (i = 0; i < __kmp_i_lock_table.next; i++) { + kmp_indirect_lock_t *l = KMP_GET_I_LOCK(i); + if (l->lock != NULL) { + // Locks not destroyed explicitly need to be destroyed here. + KMP_I_LOCK_FUNC(l, destroy)(l->lock); + KA_TRACE( + 20, + ("__kmp_cleanup_indirect_user_locks: destroy/freeing %p from table\n", + l)); + __kmp_free(l->lock); + } + } + // Free the table + for (i = 0; i < __kmp_i_lock_table.size / KMP_I_LOCK_CHUNK; i++) + __kmp_free(__kmp_i_lock_table.table[i]); + __kmp_free(__kmp_i_lock_table.table); + + __kmp_init_user_locks = FALSE; +} + +enum kmp_lock_kind __kmp_user_lock_kind = lk_default; +int __kmp_num_locks_in_block = 1; // FIXME - tune this value + +#else // KMP_USE_DYNAMIC_LOCK + +/* user locks + * They are implemented as a table of function pointers which are set to the + * lock functions of the appropriate kind, once that has been determined. */ + +enum kmp_lock_kind __kmp_user_lock_kind = lk_default; + +size_t __kmp_base_user_lock_size = 0; +size_t __kmp_user_lock_size = 0; + +kmp_int32 (*__kmp_get_user_lock_owner_)(kmp_user_lock_p lck) = NULL; +int (*__kmp_acquire_user_lock_with_checks_)(kmp_user_lock_p lck, + kmp_int32 gtid) = NULL; + +int (*__kmp_test_user_lock_with_checks_)(kmp_user_lock_p lck, + kmp_int32 gtid) = NULL; +int (*__kmp_release_user_lock_with_checks_)(kmp_user_lock_p lck, + kmp_int32 gtid) = NULL; +void (*__kmp_init_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL; +void (*__kmp_destroy_user_lock_)(kmp_user_lock_p lck) = NULL; +void (*__kmp_destroy_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL; +int (*__kmp_acquire_nested_user_lock_with_checks_)(kmp_user_lock_p lck, + kmp_int32 gtid) = NULL; + +int (*__kmp_test_nested_user_lock_with_checks_)(kmp_user_lock_p lck, + kmp_int32 gtid) = NULL; +int (*__kmp_release_nested_user_lock_with_checks_)(kmp_user_lock_p lck, + kmp_int32 gtid) = NULL; +void (*__kmp_init_nested_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL; +void (*__kmp_destroy_nested_user_lock_with_checks_)(kmp_user_lock_p lck) = NULL; + +int (*__kmp_is_user_lock_initialized_)(kmp_user_lock_p lck) = NULL; +const ident_t *(*__kmp_get_user_lock_location_)(kmp_user_lock_p lck) = NULL; +void (*__kmp_set_user_lock_location_)(kmp_user_lock_p lck, + const ident_t *loc) = NULL; +kmp_lock_flags_t (*__kmp_get_user_lock_flags_)(kmp_user_lock_p lck) = NULL; +void (*__kmp_set_user_lock_flags_)(kmp_user_lock_p lck, + kmp_lock_flags_t flags) = NULL; + +void __kmp_set_user_lock_vptrs(kmp_lock_kind_t user_lock_kind) { + switch (user_lock_kind) { + case lk_default: + default: + KMP_ASSERT(0); + + case lk_tas: { + __kmp_base_user_lock_size = sizeof(kmp_base_tas_lock_t); + __kmp_user_lock_size = sizeof(kmp_tas_lock_t); + + __kmp_get_user_lock_owner_ = + (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_tas_lock_owner); + + if (__kmp_env_consistency_check) { + KMP_BIND_USER_LOCK_WITH_CHECKS(tas); + KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(tas); + } else { + KMP_BIND_USER_LOCK(tas); + KMP_BIND_NESTED_USER_LOCK(tas); + } + + __kmp_destroy_user_lock_ = + (void (*)(kmp_user_lock_p))(&__kmp_destroy_tas_lock); + + __kmp_is_user_lock_initialized_ = (int (*)(kmp_user_lock_p))NULL; + + __kmp_get_user_lock_location_ = (const ident_t *(*)(kmp_user_lock_p))NULL; + + __kmp_set_user_lock_location_ = + (void (*)(kmp_user_lock_p, const ident_t *))NULL; + + __kmp_get_user_lock_flags_ = (kmp_lock_flags_t(*)(kmp_user_lock_p))NULL; + + __kmp_set_user_lock_flags_ = + (void (*)(kmp_user_lock_p, kmp_lock_flags_t))NULL; + } break; + +#if KMP_USE_FUTEX + + case lk_futex: { + __kmp_base_user_lock_size = sizeof(kmp_base_futex_lock_t); + __kmp_user_lock_size = sizeof(kmp_futex_lock_t); + + __kmp_get_user_lock_owner_ = + (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_futex_lock_owner); + + if (__kmp_env_consistency_check) { + KMP_BIND_USER_LOCK_WITH_CHECKS(futex); + KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(futex); + } else { + KMP_BIND_USER_LOCK(futex); + KMP_BIND_NESTED_USER_LOCK(futex); + } + + __kmp_destroy_user_lock_ = + (void (*)(kmp_user_lock_p))(&__kmp_destroy_futex_lock); + + __kmp_is_user_lock_initialized_ = (int (*)(kmp_user_lock_p))NULL; + + __kmp_get_user_lock_location_ = (const ident_t *(*)(kmp_user_lock_p))NULL; + + __kmp_set_user_lock_location_ = + (void (*)(kmp_user_lock_p, const ident_t *))NULL; + + __kmp_get_user_lock_flags_ = (kmp_lock_flags_t(*)(kmp_user_lock_p))NULL; + + __kmp_set_user_lock_flags_ = + (void (*)(kmp_user_lock_p, kmp_lock_flags_t))NULL; + } break; + +#endif // KMP_USE_FUTEX + + case lk_ticket: { + __kmp_base_user_lock_size = sizeof(kmp_base_ticket_lock_t); + __kmp_user_lock_size = sizeof(kmp_ticket_lock_t); + + __kmp_get_user_lock_owner_ = + (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_owner); + + if (__kmp_env_consistency_check) { + KMP_BIND_USER_LOCK_WITH_CHECKS(ticket); + KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(ticket); + } else { + KMP_BIND_USER_LOCK(ticket); + KMP_BIND_NESTED_USER_LOCK(ticket); + } + + __kmp_destroy_user_lock_ = + (void (*)(kmp_user_lock_p))(&__kmp_destroy_ticket_lock); + + __kmp_is_user_lock_initialized_ = + (int (*)(kmp_user_lock_p))(&__kmp_is_ticket_lock_initialized); + + __kmp_get_user_lock_location_ = + (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_location); + + __kmp_set_user_lock_location_ = (void (*)( + kmp_user_lock_p, const ident_t *))(&__kmp_set_ticket_lock_location); + + __kmp_get_user_lock_flags_ = + (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_ticket_lock_flags); + + __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))( + &__kmp_set_ticket_lock_flags); + } break; + + case lk_queuing: { + __kmp_base_user_lock_size = sizeof(kmp_base_queuing_lock_t); + __kmp_user_lock_size = sizeof(kmp_queuing_lock_t); + + __kmp_get_user_lock_owner_ = + (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_owner); + + if (__kmp_env_consistency_check) { + KMP_BIND_USER_LOCK_WITH_CHECKS(queuing); + KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(queuing); + } else { + KMP_BIND_USER_LOCK(queuing); + KMP_BIND_NESTED_USER_LOCK(queuing); + } + + __kmp_destroy_user_lock_ = + (void (*)(kmp_user_lock_p))(&__kmp_destroy_queuing_lock); + + __kmp_is_user_lock_initialized_ = + (int (*)(kmp_user_lock_p))(&__kmp_is_queuing_lock_initialized); + + __kmp_get_user_lock_location_ = + (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_location); + + __kmp_set_user_lock_location_ = (void (*)( + kmp_user_lock_p, const ident_t *))(&__kmp_set_queuing_lock_location); + + __kmp_get_user_lock_flags_ = + (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_flags); + + __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))( + &__kmp_set_queuing_lock_flags); + } break; + +#if KMP_USE_ADAPTIVE_LOCKS + case lk_adaptive: { + __kmp_base_user_lock_size = sizeof(kmp_base_adaptive_lock_t); + __kmp_user_lock_size = sizeof(kmp_adaptive_lock_t); + + __kmp_get_user_lock_owner_ = + (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_owner); + + if (__kmp_env_consistency_check) { + KMP_BIND_USER_LOCK_WITH_CHECKS(adaptive); + } else { + KMP_BIND_USER_LOCK(adaptive); + } + + __kmp_destroy_user_lock_ = + (void (*)(kmp_user_lock_p))(&__kmp_destroy_adaptive_lock); + + __kmp_is_user_lock_initialized_ = + (int (*)(kmp_user_lock_p))(&__kmp_is_queuing_lock_initialized); + + __kmp_get_user_lock_location_ = + (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_location); + + __kmp_set_user_lock_location_ = (void (*)( + kmp_user_lock_p, const ident_t *))(&__kmp_set_queuing_lock_location); + + __kmp_get_user_lock_flags_ = + (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_queuing_lock_flags); + + __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))( + &__kmp_set_queuing_lock_flags); + + } break; +#endif // KMP_USE_ADAPTIVE_LOCKS + + case lk_drdpa: { + __kmp_base_user_lock_size = sizeof(kmp_base_drdpa_lock_t); + __kmp_user_lock_size = sizeof(kmp_drdpa_lock_t); + + __kmp_get_user_lock_owner_ = + (kmp_int32(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_owner); + + if (__kmp_env_consistency_check) { + KMP_BIND_USER_LOCK_WITH_CHECKS(drdpa); + KMP_BIND_NESTED_USER_LOCK_WITH_CHECKS(drdpa); + } else { + KMP_BIND_USER_LOCK(drdpa); + KMP_BIND_NESTED_USER_LOCK(drdpa); + } + + __kmp_destroy_user_lock_ = + (void (*)(kmp_user_lock_p))(&__kmp_destroy_drdpa_lock); + + __kmp_is_user_lock_initialized_ = + (int (*)(kmp_user_lock_p))(&__kmp_is_drdpa_lock_initialized); + + __kmp_get_user_lock_location_ = + (const ident_t *(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_location); + + __kmp_set_user_lock_location_ = (void (*)( + kmp_user_lock_p, const ident_t *))(&__kmp_set_drdpa_lock_location); + + __kmp_get_user_lock_flags_ = + (kmp_lock_flags_t(*)(kmp_user_lock_p))(&__kmp_get_drdpa_lock_flags); + + __kmp_set_user_lock_flags_ = (void (*)(kmp_user_lock_p, kmp_lock_flags_t))( + &__kmp_set_drdpa_lock_flags); + } break; + } +} + +// ---------------------------------------------------------------------------- +// User lock table & lock allocation + +kmp_lock_table_t __kmp_user_lock_table = {1, 0, NULL}; +kmp_user_lock_p __kmp_lock_pool = NULL; + +// Lock block-allocation support. +kmp_block_of_locks *__kmp_lock_blocks = NULL; +int __kmp_num_locks_in_block = 1; // FIXME - tune this value + +static kmp_lock_index_t __kmp_lock_table_insert(kmp_user_lock_p lck) { + // Assume that kmp_global_lock is held upon entry/exit. + kmp_lock_index_t index; + if (__kmp_user_lock_table.used >= __kmp_user_lock_table.allocated) { + kmp_lock_index_t size; + kmp_user_lock_p *table; + // Reallocate lock table. + if (__kmp_user_lock_table.allocated == 0) { + size = 1024; + } else { + size = __kmp_user_lock_table.allocated * 2; + } + table = (kmp_user_lock_p *)__kmp_allocate(sizeof(kmp_user_lock_p) * size); + KMP_MEMCPY(table + 1, __kmp_user_lock_table.table + 1, + sizeof(kmp_user_lock_p) * (__kmp_user_lock_table.used - 1)); + table[0] = (kmp_user_lock_p)__kmp_user_lock_table.table; + // We cannot free the previous table now, since it may be in use by other + // threads. So save the pointer to the previous table in in the first + // element of the new table. All the tables will be organized into a list, + // and could be freed when library shutting down. + __kmp_user_lock_table.table = table; + __kmp_user_lock_table.allocated = size; + } + KMP_DEBUG_ASSERT(__kmp_user_lock_table.used < + __kmp_user_lock_table.allocated); + index = __kmp_user_lock_table.used; + __kmp_user_lock_table.table[index] = lck; + ++__kmp_user_lock_table.used; + return index; +} + +static kmp_user_lock_p __kmp_lock_block_allocate() { + // Assume that kmp_global_lock is held upon entry/exit. + static int last_index = 0; + if ((last_index >= __kmp_num_locks_in_block) || (__kmp_lock_blocks == NULL)) { + // Restart the index. + last_index = 0; + // Need to allocate a new block. + KMP_DEBUG_ASSERT(__kmp_user_lock_size > 0); + size_t space_for_locks = __kmp_user_lock_size * __kmp_num_locks_in_block; + char *buffer = + (char *)__kmp_allocate(space_for_locks + sizeof(kmp_block_of_locks)); + // Set up the new block. + kmp_block_of_locks *new_block = + (kmp_block_of_locks *)(&buffer[space_for_locks]); + new_block->next_block = __kmp_lock_blocks; + new_block->locks = (void *)buffer; + // Publish the new block. + KMP_MB(); + __kmp_lock_blocks = new_block; + } + kmp_user_lock_p ret = (kmp_user_lock_p)(&( + ((char *)(__kmp_lock_blocks->locks))[last_index * __kmp_user_lock_size])); + last_index++; + return ret; +} + +// Get memory for a lock. It may be freshly allocated memory or reused memory +// from lock pool. +kmp_user_lock_p __kmp_user_lock_allocate(void **user_lock, kmp_int32 gtid, + kmp_lock_flags_t flags) { + kmp_user_lock_p lck; + kmp_lock_index_t index; + KMP_DEBUG_ASSERT(user_lock); + + __kmp_acquire_lock(&__kmp_global_lock, gtid); + + if (__kmp_lock_pool == NULL) { + // Lock pool is empty. Allocate new memory. + + // ANNOTATION: Found no good way to express the syncronisation + // between allocation and usage, so ignore the allocation + ANNOTATE_IGNORE_WRITES_BEGIN(); + if (__kmp_num_locks_in_block <= 1) { // Tune this cutoff point. + lck = (kmp_user_lock_p)__kmp_allocate(__kmp_user_lock_size); + } else { + lck = __kmp_lock_block_allocate(); + } + ANNOTATE_IGNORE_WRITES_END(); + + // Insert lock in the table so that it can be freed in __kmp_cleanup, + // and debugger has info on all allocated locks. + index = __kmp_lock_table_insert(lck); + } else { + // Pick up lock from pool. + lck = __kmp_lock_pool; + index = __kmp_lock_pool->pool.index; + __kmp_lock_pool = __kmp_lock_pool->pool.next; + } + + // We could potentially differentiate between nested and regular locks + // here, and do the lock table lookup for regular locks only. + if (OMP_LOCK_T_SIZE < sizeof(void *)) { + *((kmp_lock_index_t *)user_lock) = index; + } else { + *((kmp_user_lock_p *)user_lock) = lck; + } + + // mark the lock if it is critical section lock. + __kmp_set_user_lock_flags(lck, flags); + + __kmp_release_lock(&__kmp_global_lock, gtid); // AC: TODO move this line upper + + return lck; +} + +// Put lock's memory to pool for reusing. +void __kmp_user_lock_free(void **user_lock, kmp_int32 gtid, + kmp_user_lock_p lck) { + KMP_DEBUG_ASSERT(user_lock != NULL); + KMP_DEBUG_ASSERT(lck != NULL); + + __kmp_acquire_lock(&__kmp_global_lock, gtid); + + lck->pool.next = __kmp_lock_pool; + __kmp_lock_pool = lck; + if (OMP_LOCK_T_SIZE < sizeof(void *)) { + kmp_lock_index_t index = *((kmp_lock_index_t *)user_lock); + KMP_DEBUG_ASSERT(0 < index && index <= __kmp_user_lock_table.used); + lck->pool.index = index; + } + + __kmp_release_lock(&__kmp_global_lock, gtid); +} + +kmp_user_lock_p __kmp_lookup_user_lock(void **user_lock, char const *func) { + kmp_user_lock_p lck = NULL; + + if (__kmp_env_consistency_check) { + if (user_lock == NULL) { + KMP_FATAL(LockIsUninitialized, func); + } + } + + if (OMP_LOCK_T_SIZE < sizeof(void *)) { + kmp_lock_index_t index = *((kmp_lock_index_t *)user_lock); + if (__kmp_env_consistency_check) { + if (!(0 < index && index < __kmp_user_lock_table.used)) { + KMP_FATAL(LockIsUninitialized, func); + } + } + KMP_DEBUG_ASSERT(0 < index && index < __kmp_user_lock_table.used); + KMP_DEBUG_ASSERT(__kmp_user_lock_size > 0); + lck = __kmp_user_lock_table.table[index]; + } else { + lck = *((kmp_user_lock_p *)user_lock); + } + + if (__kmp_env_consistency_check) { + if (lck == NULL) { + KMP_FATAL(LockIsUninitialized, func); + } + } + + return lck; +} + +void __kmp_cleanup_user_locks(void) { + // Reset lock pool. Don't worry about lock in the pool--we will free them when + // iterating through lock table (it includes all the locks, dead or alive). + __kmp_lock_pool = NULL; + +#define IS_CRITICAL(lck) \ + ((__kmp_get_user_lock_flags_ != NULL) && \ + ((*__kmp_get_user_lock_flags_)(lck)&kmp_lf_critical_section)) + + // Loop through lock table, free all locks. + // Do not free item [0], it is reserved for lock tables list. + // + // FIXME - we are iterating through a list of (pointers to) objects of type + // union kmp_user_lock, but we have no way of knowing whether the base type is + // currently "pool" or whatever the global user lock type is. + // + // We are relying on the fact that for all of the user lock types + // (except "tas"), the first field in the lock struct is the "initialized" + // field, which is set to the address of the lock object itself when + // the lock is initialized. When the union is of type "pool", the + // first field is a pointer to the next object in the free list, which + // will not be the same address as the object itself. + // + // This means that the check (*__kmp_is_user_lock_initialized_)(lck) will fail + // for "pool" objects on the free list. This must happen as the "location" + // field of real user locks overlaps the "index" field of "pool" objects. + // + // It would be better to run through the free list, and remove all "pool" + // objects from the lock table before executing this loop. However, + // "pool" objects do not always have their index field set (only on + // lin_32e), and I don't want to search the lock table for the address + // of every "pool" object on the free list. + while (__kmp_user_lock_table.used > 1) { + const ident *loc; + + // reduce __kmp_user_lock_table.used before freeing the lock, + // so that state of locks is consistent + kmp_user_lock_p lck = + __kmp_user_lock_table.table[--__kmp_user_lock_table.used]; + + if ((__kmp_is_user_lock_initialized_ != NULL) && + (*__kmp_is_user_lock_initialized_)(lck)) { + // Issue a warning if: KMP_CONSISTENCY_CHECK AND lock is initialized AND + // it is NOT a critical section (user is not responsible for destroying + // criticals) AND we know source location to report. + if (__kmp_env_consistency_check && (!IS_CRITICAL(lck)) && + ((loc = __kmp_get_user_lock_location(lck)) != NULL) && + (loc->psource != NULL)) { + kmp_str_loc_t str_loc = __kmp_str_loc_init(loc->psource, 0); + KMP_WARNING(CnsLockNotDestroyed, str_loc.file, str_loc.line); + __kmp_str_loc_free(&str_loc); + } + +#ifdef KMP_DEBUG + if (IS_CRITICAL(lck)) { + KA_TRACE( + 20, + ("__kmp_cleanup_user_locks: free critical section lock %p (%p)\n", + lck, *(void **)lck)); + } else { + KA_TRACE(20, ("__kmp_cleanup_user_locks: free lock %p (%p)\n", lck, + *(void **)lck)); + } +#endif // KMP_DEBUG + + // Cleanup internal lock dynamic resources (for drdpa locks particularly). + __kmp_destroy_user_lock(lck); + } + + // Free the lock if block allocation of locks is not used. + if (__kmp_lock_blocks == NULL) { + __kmp_free(lck); + } + } + +#undef IS_CRITICAL + + // delete lock table(s). + kmp_user_lock_p *table_ptr = __kmp_user_lock_table.table; + __kmp_user_lock_table.table = NULL; + __kmp_user_lock_table.allocated = 0; + + while (table_ptr != NULL) { + // In the first element we saved the pointer to the previous + // (smaller) lock table. + kmp_user_lock_p *next = (kmp_user_lock_p *)(table_ptr[0]); + __kmp_free(table_ptr); + table_ptr = next; + } + + // Free buffers allocated for blocks of locks. + kmp_block_of_locks_t *block_ptr = __kmp_lock_blocks; + __kmp_lock_blocks = NULL; + + while (block_ptr != NULL) { + kmp_block_of_locks_t *next = block_ptr->next_block; + __kmp_free(block_ptr->locks); + // *block_ptr itself was allocated at the end of the locks vector. + block_ptr = next; + } + + TCW_4(__kmp_init_user_locks, FALSE); +} + +#endif // KMP_USE_DYNAMIC_LOCK |