path: root/contrib/libs/cxxsupp/openmp/kmp_lock.cpp

/* 
 * 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 "kmp.h" 
#include "kmp_itt.h" 
#include "kmp_i18n.h" 
#include "kmp_lock.h" 
#include "kmp_io.h" 
 
#if KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64) 
# 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 = 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 ); 
    } 
 
    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) ) ) ) { 
        // 
        // FIXME - use exponential backoff here 
        // 
        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 ) 
{ 
    return __kmp_acquire_tas_lock_timed_template( lck, gtid ); 
} 
 
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); 
    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 ); 
        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_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64) 
 
/* ------------------------------------------------------------------------ */ 
/* 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 = 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 ) 
{ 
   return __kmp_acquire_futex_lock_timed_template( lck, gtid ); 
} 
 
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, futex) << 1 ) ) { 
        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); 
 
    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 ); 
        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_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM) 
 
 
/* ------------------------------------------------------------------------ */ 
/* ticket (bakery) locks */ 
 
static kmp_int32 
__kmp_get_ticket_lock_owner( kmp_ticket_lock_t *lck ) 
{ 
    return TCR_4( lck->lk.owner_id ) - 1; 
} 
 
static inline bool 
__kmp_is_ticket_lock_nestable( kmp_ticket_lock_t *lck ) 
{ 
    return lck->lk.depth_locked != -1; 
} 
 
static kmp_uint32 
__kmp_bakery_check(kmp_uint value, kmp_uint checker) 
{ 
    kmp_uint32 pause;
 
    if (value == checker) { 
        return TRUE; 
    } 
    for (pause = checker - value; pause != 0; --pause); 
    return FALSE; 
} 
 
__forceinline static int 
__kmp_acquire_ticket_lock_timed_template( kmp_ticket_lock_t *lck, kmp_int32 gtid ) 
{ 
    kmp_uint32 my_ticket; 
    KMP_MB(); 
 
    my_ticket = KMP_TEST_THEN_INC32( (kmp_int32 *) &lck->lk.next_ticket ); 
 
#ifdef USE_LOCK_PROFILE 
    if ( TCR_4( lck->lk.now_serving ) != my_ticket ) 
        __kmp_printf( "LOCK CONTENTION: %p\n", lck ); 
    /* else __kmp_printf( "." );*/ 
#endif /* USE_LOCK_PROFILE */ 
 
    if ( TCR_4( lck->lk.now_serving ) == my_ticket ) { 
        KMP_FSYNC_ACQUIRED(lck); 
        return KMP_LOCK_ACQUIRED_FIRST; 
    } 
    KMP_WAIT_YIELD( &lck->lk.now_serving, my_ticket, __kmp_bakery_check, lck ); 
    KMP_FSYNC_ACQUIRED(lck); 
    return KMP_LOCK_ACQUIRED_FIRST; 
} 
 
int 
__kmp_acquire_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid ) 
{ 
    return __kmp_acquire_ticket_lock_timed_template( lck, gtid ); 
} 
 
static int 
__kmp_acquire_ticket_lock_with_checks( kmp_ticket_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_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 ); 
 
    lck->lk.owner_id = gtid + 1; 
    return KMP_LOCK_ACQUIRED_FIRST; 
} 
 
int 
__kmp_test_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid ) 
{ 
    kmp_uint32 my_ticket = TCR_4( lck->lk.next_ticket ); 
    if ( TCR_4( lck->lk.now_serving ) == my_ticket ) { 
        kmp_uint32 next_ticket = my_ticket + 1; 
        if ( KMP_COMPARE_AND_STORE_ACQ32( (kmp_int32 *) &lck->lk.next_ticket, 
          my_ticket, next_ticket ) ) { 
            KMP_FSYNC_ACQUIRED( lck ); 
            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 ( lck->lk.initialized != 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 ) { 
        lck->lk.owner_id = gtid + 1; 
    } 
    return retval; 
} 
 
int 
__kmp_release_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid ) 
{ 
    kmp_uint32  distance; 
 
    KMP_MB();       /* Flush all pending memory write invalidates.  */ 
 
    KMP_FSYNC_RELEASING(lck); 
    distance = ( TCR_4( lck->lk.next_ticket ) - TCR_4( lck->lk.now_serving ) ); 
 
    KMP_ST_REL32( &(lck->lk.now_serving), lck->lk.now_serving + 1 ); 
 
    KMP_MB();       /* Flush all pending memory write invalidates.  */ 
 
    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"; 
    KMP_MB();  /* in case another processor initialized lock */ 
    if ( lck->lk.initialized != 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 ); 
    } 
    lck->lk.owner_id = 0; 
    return __kmp_release_ticket_lock( lck, gtid ); 
} 
 
void 
__kmp_init_ticket_lock( kmp_ticket_lock_t * lck ) 
{ 
    lck->lk.location = NULL; 
    TCW_4( lck->lk.next_ticket, 0 ); 
    TCW_4( lck->lk.now_serving, 0 ); 
    lck->lk.owner_id = 0;      // no thread owns the lock. 
    lck->lk.depth_locked = -1; // -1 => not a nested lock. 
    lck->lk.initialized = (kmp_ticket_lock *)lck; 
} 
 
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 ) 
{ 
    lck->lk.initialized = NULL; 
    lck->lk.location    = NULL; 
    lck->lk.next_ticket = 0; 
    lck->lk.now_serving = 0; 
    lck->lk.owner_id = 0; 
    lck->lk.depth_locked = -1; 
} 
 
static void 
__kmp_destroy_ticket_lock_with_checks( kmp_ticket_lock_t *lck ) 
{ 
    char const * const func = "omp_destroy_lock"; 
    if ( lck->lk.initialized != 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 ) { 
        lck->lk.depth_locked += 1; 
        return KMP_LOCK_ACQUIRED_NEXT; 
    } 
    else { 
        __kmp_acquire_ticket_lock_timed_template( lck, gtid ); 
        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_ticket_lock_with_checks( kmp_ticket_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_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 = ++lck->lk.depth_locked; 
    } 
    else if ( !__kmp_test_ticket_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_ticket_lock_with_checks( kmp_ticket_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_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 ); 
 
    KMP_MB(); 
    if ( --(lck->lk.depth_locked) == 0 ) { 
        KMP_MB(); 
        lck->lk.owner_id = 0; 
        __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"; 
    KMP_MB();  /* in case another processor initialized lock */ 
    if ( lck->lk.initialized != 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 ); 
    lck->lk.depth_locked = 0; // >= 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 ); 
    lck->lk.depth_locked = 0; 
} 
 
static void 
__kmp_destroy_nested_ticket_lock_with_checks( kmp_ticket_lock_t *lck ) 
{ 
    char const * const func = "omp_destroy_nest_lock"; 
    if ( lck->lk.initialized != 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 lck == lck->lk.initialized; 
} 
 
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 ) 
{ 
    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 ); 
 
    return __kmp_acquire_queuing_lock_timed_template<false>( lck, gtid ); 
} 
 
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); 
            return TRUE; 
        } 
    } 
 
    KA_TRACE( 1000, ("__kmp_test_queuing_lock: T#%d exiting: without lock\n", gtid )); 
    return FALSE; 
} 
 
static int 
__kmp_test_queuing_lock_with_checks( kmp_queuing_lock_t *lck, kmp_int32 gtid ) 
{ 
    char const * const func = "omp_test_lock"; 
    if ( lck->lk.initialized != lck ) { 
        KMP_FATAL( LockIsUninitialized, func ); 
    } 
    if ( __kmp_is_queuing_lock_nestable( lck ) ) { 
        KMP_FATAL( LockNestableUsedAsSimple, func ); 
    } 
 
    int retval = __kmp_test_queuing_lock( lck, gtid ); 
 
    if ( retval ) { 
        lck->lk.owner_id = gtid + 1; 
    } 
    return retval; 
} 
 
int 
__kmp_release_queuing_lock( kmp_queuing_lock_t *lck, kmp_int32 gtid ) 
{ 
    kmp_info_t *this_thr;
    volatile kmp_int32 *head_id_p = & lck->lk.head_id; 
    volatile kmp_int32 *tail_id_p = & lck->lk.tail_id; 
 
    KA_TRACE( 1000, ("__kmp_release_queuing_lock: lck:%p, T#%d entering\n", lck, gtid )); 
    KMP_DEBUG_ASSERT( gtid >= 0 ); 
    this_thr    = __kmp_thread_from_gtid( gtid ); 
    KMP_DEBUG_ASSERT( this_thr != NULL ); 
#ifdef DEBUG_QUEUING_LOCKS 
    TRACE_LOCK( gtid+1, "rel ent" ); 
 
    if ( this_thr->th.th_spin_here ) 
        __kmp_dump_queuing_lock( this_thr, gtid, lck, *head_id_p, *tail_id_p ); 
    if ( this_thr->th.th_next_waiting != 0 ) 
        __kmp_dump_queuing_lock( this_thr, gtid, lck, *head_id_p, *tail_id_p ); 
#endif 
    KMP_DEBUG_ASSERT( !this_thr->th.th_spin_here ); 
    KMP_DEBUG_ASSERT( this_thr->th.th_next_waiting == 0 ); 
 
    KMP_FSYNC_RELEASING(lck); 
 
    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_int32) KMP_WAIT_YIELD((volatile kmp_uint*) 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 ); 
        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 ); 
} 
 
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.c !!! 
    // 
    // 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 ) 
{ 
    return __kmp_acquire_drdpa_lock_timed_template( lck, gtid ); 
} 
 
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); 
    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 ); 
        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; 
} 
 
#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.c 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_HAS_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: 
            return __kmp_get_queuing_lock_owner((kmp_queuing_lock_t *)lck); 
#endif 
        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; 
        } 
    } 
    // 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_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM) 
 
        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_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM) 
 
        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. 
        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(); 
        } 
 
        // 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