Google Git
Sign in
llvm / openmp / 57d548374213fbd3bbb85f973edb5469ea849899 / . / runtime / src / kmp_lock.cpp
blob: 0055116471c675adafc8115d64ddf347d7e9da60 [file] [log] [blame]
/*
* 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_itt.h"
#include "kmp_i18n.h"
#include "kmp_lock.h"
#include "kmp_io.h"
#include "tsan_annotations.h"
#if KMP_USE_FUTEX
# include <unistd.h>
# include <sys/syscall.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(TCR_4( 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( TCR_4( lck->lk.poll ) );
if ( ( curr != 0 ) && ( curr != gtid + 1 ) )
__kmp_printf( "LOCK CONTENTION: %p\n", lck );
/* else __kmp_printf( "." );*/
#endif /* USE_LOCK_PROFILE */
if ( ( lck->lk.poll == KMP_LOCK_FREE(tas) )
&& KMP_COMPARE_AND_STORE_ACQ32( & ( lck->lk.poll ), KMP_LOCK_FREE(tas), KMP_LOCK_BUSY(gtid+1, tas) ) ) {
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 ( ( lck->lk.poll != KMP_LOCK_FREE(tas) ) ||
( ! KMP_COMPARE_AND_STORE_ACQ32( & ( lck->lk.poll ), KMP_LOCK_FREE(tas), KMP_LOCK_BUSY(gtid+1, tas) ) ) ) {
__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 )
{
if ( ( lck->lk.poll == KMP_LOCK_FREE(tas) )
&& KMP_COMPARE_AND_STORE_ACQ32( & ( lck->lk.poll ), KMP_LOCK_FREE(tas), KMP_LOCK_BUSY(gtid+1, tas) ) ) {
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_ST_REL32( &(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 )
{
TCW_4( 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 is 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 )
{
register 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
ompt_state_t prev_state = ompt_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 && prev_state != ompt_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 && prev_state == ompt_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 = ompt_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 )
{
register 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 {
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( (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.
*/
#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
#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;
// Initialize the list of stats.
void
__kmp_init_speculative_stats()
{
kmp_adaptive_lock_info_t *lck = &liveLocks;
memset( ( void * ) & ( 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( ( void * )&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_adaptive_lock_statistics_t *t = &destroyedStats;
__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()
{
if (__kmp_user_lock_kind != lk_adaptive)
return;
FILE * statsFile = __kmp_open_stats_file();
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;
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 TCR_4( 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_TEST_THEN_INC64((kmp_int64 *)&lck->lk.next_ticket);
kmp_uint64 mask = TCR_8(lck->lk.mask); // volatile load
volatile struct kmp_base_drdpa_lock::kmp_lock_poll *polls
= (volatile struct kmp_base_drdpa_lock::kmp_lock_poll *)
TCR_PTR(lck->lk.polls); // volatile load
#ifdef USE_LOCK_PROFILE
if (TCR_8(polls[ticket & mask].poll) != 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 (TCR_8(polls[ticket & mask].poll) < ticket) { // volatile 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 = TCR_8(lck->lk.mask); // volatile load
polls = (volatile struct kmp_base_drdpa_lock::kmp_lock_poll *)
TCR_PTR(lck->lk.polls); // volatile 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((void *)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;
volatile struct kmp_base_drdpa_lock::kmp_lock_poll *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 = (volatile struct kmp_base_drdpa_lock::kmp_lock_poll *)
__kmp_allocate(num_polls * sizeof(*polls));
polls[0].poll = 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 = (volatile struct kmp_base_drdpa_lock::kmp_lock_poll *)
__kmp_allocate(num_polls * sizeof(*polls));
kmp_uint32 i;
for (i = 0; i < old_num_polls; i++) {
polls[i].poll = old_polls[i].poll;
}
}
}
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; // non-volatile store
lck->lk.polls = polls; // volatile store
KMP_MB();
lck->lk.num_polls = num_polls; // non-volatile store
lck->lk.mask = mask; // volatile 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 = TCR_8(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 = TCR_8(lck->lk.next_ticket); // volatile load
volatile struct kmp_base_drdpa_lock::kmp_lock_poll *polls
= (volatile struct kmp_base_drdpa_lock::kmp_lock_poll *)
TCR_PTR(lck->lk.polls); // volatile load
kmp_uint64 mask = TCR_8(lck->lk.mask); // volatile load
if (TCR_8(polls[ticket & mask].poll) == ticket) {
kmp_uint64 next_ticket = ticket + 1;
if (KMP_COMPARE_AND_STORE_ACQ64((kmp_int64 *)&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-volatile load
volatile struct kmp_base_drdpa_lock::kmp_lock_poll *polls
= (volatile struct kmp_base_drdpa_lock::kmp_lock_poll *)
TCR_PTR(lck->lk.polls); // volatile load
kmp_uint64 mask = TCR_8(lck->lk.mask); // volatile 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);
KMP_ST_REL64(&(polls[ticket & mask].poll), ticket); // volatile 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 = (volatile struct kmp_base_drdpa_lock::kmp_lock_poll *)
__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 != NULL) {
__kmp_free((void *)lck->lk.polls);
lck->lk.polls = NULL;
}
if (lck->lk.old_polls != NULL) {
__kmp_free((void *)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 void __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 void __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,(void (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock,
static void (*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,(void (*)(kmp_dyna_lock_t *, kmp_int32))__kmp_##op##_##l##_lock_with_checks,
static void (*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).
void (*(*__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) (void (*)(kmp_user_lock_p, kmp_int32))__kmp_##op##_##l##_##lock,
static void (*indirect_set[])(kmp_user_lock_p, kmp_int32) = { KMP_FOREACH_I_LOCK(expand, acquire) };
#undef expand
#define expand(l, op) (void (*)(kmp_user_lock_p, kmp_int32))__kmp_##op##_##l##_##lock_with_checks,
static void (*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).
void (*(*__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 **old_table = __kmp_i_lock_table.table;
__kmp_i_lock_table.table = (kmp_indirect_lock_t **)__kmp_allocate(2*row*sizeof(kmp_indirect_lock_t *));
KMP_MEMCPY(__kmp_i_lock_table.table, old_table, row*sizeof(kmp_indirect_lock_t *));
__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 void
__kmp_set_indirect_lock(kmp_dyna_lock_t * lock, kmp_int32 gtid)
{
kmp_indirect_lock_t *l = KMP_LOOKUP_I_LOCK(lock);
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 void
__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");
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;
}
// 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. Do not 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