Use C++11 atomics for ticket locks implementation

[pawosm01]

Summary

This patch replaces use of compiler builtin atomics with
C++11 atomics for ticket locks implementation. Ticket locks
are used in critical places of the runtime, e.g. in the tasking
mechanism.

The main reason this change was introduced is the problem
with work stealing function on ARM architecture which suffered
from nasty race condition. It turned out that the root cause of
the problem lies in the way ticket locks are implemented. Changing
compiler builtins into C++11 atomics solves the problem.

Two assertions were added into kmp_tasking.c which are useful
for detecting early symptoms of something wrong going on with
work stealing, which were among the possible outcomes of the
race condition.

[jcownie]

I have only made a top-level scan, so this needs more review. However,
__kmp_baker_check should look like this

static kmp_uint32
__kmp_bakery_check(void *value, kmp_uint32 checker)
{
    return (std::atomic_load( (std::atomic<unsigned> *)value ) == checker);
}

Rather than having a test then returning TRUE or FALSE!

It would also be nice to reduce some of the code replication (e.g. kmp_wait_yield_4_ptr is identical to kmp_wait_yield_4 apart from the argument type [MIssing leading underscores since they cause underlining!] ). Either we should use a template (if we accept that this code is really C++ now), or even a macro for the whole function that is invoked with the function name and type is better than having the whole code duplicated.

[pawosm01]

In D19878#420844, @jcownie wrote:

I have only made a top-level scan, so this needs more review. However,
__kmp_baker_check should look like this

static kmp_uint32
__kmp_bakery_check(void *value, kmp_uint32 checker)
{
    return (std::atomic_load( (std::atomic<unsigned> *)value ) == checker);
}

Rather than having a test then returning TRUE or FALSE!

Yeah, I'd rather focused on removing this funny loop above return FALSE and didn't spot that loop removal caused whole 'if' became pointless. To be fixed.

It would also be nice to reduce some of the code replication (e.g. kmp_wait_yield_4_ptr is identical to kmp_wait_yield_4 apart from the argument type [MIssing leading underscores since they cause underlining!] ). Either we should use a template (if we accept that this code is really C++ now), or even a macro for the whole function that is invoked with the function name and type is better than having the whole code duplicated.

Note that all those functions are within 'extern "C" { .... }' block so templates aren't welcome there. The questioned slight code replication seems to be better solution for now than preparing ugly macro. This code yields for the further refactor but that is not the point of this patch which is to make tasking work on more architectures.

[pawosm01]

pointless 'if' removed

[hbae]

• I don't think it is necessary to introduce a new member "self" since std::atomic should be working fine with pointer types. Is there any specific reason for separating the original variable " initialized" into "initialized" and "self"?
• I don't know why KMP_FSYNC* calls were removed in the new code. It may not be meaningful in many cases, but it is not dead code as far as I know.

[pawosm01]

In D19878#429947, @hbae wrote:

• I don't think it is necessary to introduce a new member "self" since std::atomic should be working fine with pointer types. Is there any specific reason for separating the original variable " initialized" into "initialized" and "self"?

I don't remember, looks redundant for me now.

• I don't know why KMP_FSYNC* calls were removed in the new code. It may not be meaningful in many cases, but it is not dead code as far as I know.

Unfortunately, I don't see what you're pointing at. Can you quote some example?

[hbae]

In D19878#430007, @pawosm01 wrote:

In D19878#429947, @hbae wrote:

• I don't know why KMP_FSYNC* calls were removed in the new code. It may not be meaningful in many cases, but it is not dead code as far as I know.

Unfortunately, I don't see what you're pointing at. Can you quote some example?

I was just wondering if you are removing these calls on purpose:

KMP_FSYNC_ACQUIRED() - line 758, 762, 800
KMP_FSYNC_RELEASING() - line 833

[pawosm01]

Ok, now I see. If this code is not dead, is not live either. For example, KMP_FSYNC_RELEASING macro:

#if USE_ITT_BUILD
// Old stuff for reporting low-level internal synchronization.
#if USE_ITT_NOTIFY
#define KMP_FSYNC_RELEASING( obj )  __itt_fsync_releasing( (void *)( obj ) )
#else
# define KMP_FSYNC_RELEASING( obj )        ((void)0)
#endif
#else
# define KMP_FSYNC_RELEASING( obj )        ((void)0)
#endif

...where __itt_fsync_releasing() is declared:

/**
 * @ingroup legacy
 * @deprecated Legacy API
 * @brief Fast synchronization which does no require spinning.
 * - This special function is to be used by TBB and OpenMP libraries only when they know
 *   there is no spin but they need to suppress TC warnings about shared variable modifications.
 * - It only has corresponding pointers in static library and does not have corresponding function
 *   in dynamic library.
 * @see void __itt_sync_releasing(void* addr);
 */
void ITTAPI __itt_fsync_releasing(void* addr);

...but never defined!

IMHO the whole point of using C++11 atomics is to avoid necessity of using stuff like that. It is up to compiler (reinforced by memory order hints like std::memory_order_release) to generate proper binary code for targeted architecture, so no macros like KMP_FSYNC_RELEASING would be needed.

[AndreyChurbanov]

IMHO the whole point of using C++11 atomics is to avoid necessity of using stuff like that. It is up to compiler (reinforced by memory order hints like std::memory_order_release) to generate proper binary code for targeted architecture, so no macros like KMP_FSYNC_RELEASING would be needed.

Actually these macros were intended not to make proper code, but to send signals to tools. E.g. so that memory checker would not complain on accesses to shared memory inside critical sections. I consulted with the consumers of this code - Intel tools, - and the resolution is the *_fsync_* apis are not used by them nowadays. So the code looks more dead than live, and these stubs entries are never resolved to point to actual entries. As opposed to *_sync_* apis those can be dynamically changed from empty stubs to code with actual calls.

• Andrey

[pawosm01]

Hello?

[jmellorcrummey]

I have a few unsolicited comments to offer:

(1) The atomic load in kmp_bakery_check should use memory_order_acquire rather than the more restrictive default memory_order_seq_cst. Since this condition is tested with inlined code in quite a few places (checking for == or != my_ticket), I recommend that this detail be implemented in an inlined function or macro that is used ubiquitously.
(2) The atomic loads in kmp_get_ticket_lock_owner and kmp_is_ticket_lock_nestable should use memory_order_relaxed since they aren't used to enforce ordering for synchronization. The owner is written with atomic_store, which could also be memory_order_relaxed. In kmp_release_ticket_lock_with_checks, owner_id is written as 0 without an atomic store. Either you need atomic store and load to manipulate this field or not. I dislike mixing the two. If you are concerned about atomicity, you should use an atomic_store with memory_order_relaxed here too.
(3) I recommend renaming the parameters of kmp_bakery_check to more clearly indicate their intent: current_value and target_value, or now_serving and my_ticket.
(4) I dislike the way gtid+1 is written into a ticket lock's owner_id throughout the file and then kmp_get_ticket_lock_owner returns owner_id -1. I understand that the range of gtids and that unowned is indicated by 0. I recommend using macros like GTID_TO_LOCK_OWNER(gtid) and LOCK_OWNER_TO_GTID(owner_id) to replace the ugly -1 and +1 everywhere. Also, I think that kmp_get_ticket_lock_owner should return the owner_id and the subtraction should take place outside.
(5) The value for for non-nestable should be defined as something like LOCK_NOT_NESTABLE and not used with a raw -1.
(6) Why not correct the spelling of "checks" in the function prototype kmp_test_ticket_lock_with_cheks?
(7) I dislike checking the lock owner against 0 to determine if it is unowned. Why not use a macro set to 0: LOCK_NO_OWNER?

I'm sure that there is more worth saying, but I think that I've said enough.

[AndreyChurbanov]

LGTM.

I think we will address the John's comments separately. As they sounds perfectly sane to me, but should not further delay current change.

• Andrey

[pawosm01]

Hi Andrey,

Although most of Johns suggestions are good subject of bigger refactor (e.g. GTID_TO_LOCK_OWNER affects other lock mechanisms too), I think his remark regarding lack of atomic store in __kmp_release_ticket_lock_with_checks() is relevant here. And also seems like I didn't update my patch with 'self' field removal. Now we got two options 1) land it as it is and prepare the next patch which should address 'self' field issue and John's issues number 1, 2, 3 and 6 (while 4, 5 and 7 are outside of the scope of this change) or 2) wait 2-3 days until I finish checking updated patch where 'self' is removed and missing atomic store is added.

[AndreyChurbanov]

Once you are going to work on it soon I'd prefer to wait for couple of days. Let's get better patch in.

I was concerned by many days age of the request with most comments been addressed; couple more days - not o problem, I think.

Thanks,
Andrey

[AndreyChurbanov]

Cancel my LGTM basing on Pawel's comment.

[pawosm01]

Nah, I don't like this idea of making pointer to 'self' in 'initialized' field atomic - it leads to nasty casting of pointers (e.g. you can't do atomic store of NULL or nullptr to atomic pointer of certain type without ugly casting). I don't like the idea of removing self-pointer and leaving only boolean 'initialized' field either - checking whether self equals lck is a whole point of those sanity check functions. I think it should be left as it is and only missing atomic store in the __kmp_release_ticket_lock_with_checks() requires immediate attention.

[pawosm01]

I'll put updated patch in a few days.

[pawosm01]

I'm placing updated patch here. Overnight executions of OpenUH taskbench tests didn't fail, so I assume relaxed memory ordering (as suggested by Jim) is ok. Missing atomic store also added, __kmp_bakery_check() params renamed.

[jcownie]

(as suggested by Jim)

I believe the suggestion was from John, and I wouldn’t want to steal his thunder!

• Jim

James Cownie <[e-mail]>
SSG/DPD/TCAR (Technical Computing, Analyzers and Runtimes)
Tel: [phone]

[jmellorcrummey]

I have a few more comments about the memory orderings. Not having too much order is important for performance. Fences that are inserted unless they are explicitly omitted hurt performance.

After you see my list below, you'll be wondering whether you should have ventured down this path :-)

Line 741 the fetch and add can be relaxed order. the acquire order is important on the load that tests vs. myticket
Line 744 this load isn't for synchronization, it can be relaxed order
Line 749 this atomic load should have acquire order, but does not need to be sequentially consistent
Line 767 this load isn't for synchronization, it can be relaxed order
Line 782 this store isn't for synchronization, the store can be relaxed order
Line 789 this load isn't for synchronization, it can be relaxed order
Line 791 this load can be relaxed because the CAS on line 793 enfoceces the acquire order
Line 806 this load isn't for synchronization, it can be relaxed order
Line 782 this store isn't for synchronization, the store can be relaxed order
Line 827 neither of these loads are for synchronization, so they can be relaxed
Line 840 this load isn't for synchronization, it can be relaxed order
Lines 865-869 all of these stores can be relaxed
Line 870 if this store is release order, all of the prior stores in this routine will complete before the initialized flag is set
Line 882 could be release order to ensure all prior operations on the lock are complete.
Line 883-888 these stores can be relaxed. I could argue that once you clear initialized, you could not bother writing the rest of the values.
Line 986 this load can be relaxed because it isn't for synchronization
Line 922 can be relaxed. all ordering will be enforced by synchronizing accesses for the outer lock
Line 927-928 can be relaxed. these aren't synchronizing.
Line 938 can be relaxed. it isn't synchronizing.
Line 958 can be relaxed. all ordering will be enforced by synchronizing accesses for the outer lock
Lines 964-965 can be relaxed.
Line 977 can be relaxed. it isn't synchronizing.
Lines 994-995 aren't synchronizing and can be relaxed.
Line 1007 isn't synchronizing and can be relaxed.
Line 1029 can be relaxed (or even omitted)
Line 1042 can be relaxed (or even omitted)
Line 1050 can be relaxed
Line 1073 can be relaxed

[pawosm01]

Hi John,

Thanks for all of your recommendations, I applied all of them and started taskbench in infinite loop on it for the night run. If it still works tomorrow, I'll place updated patch here.

[jmellorcrummey]

I hope that you are testing it on a system with weak ordering rather than an Intel chip ;-)

John Mellor-Crummey

(sent from my phone)

[pawosm01]

Here it is, updated version. Overnight tests on two different AArch64 machines using two different compilers (clang, gcc 5.3) passed.

[AndreyChurbanov]

LGTM

runtime/src/kmp.h

 
 
 extern kmp_uint32 __kmp_eq_4(  kmp_uint32 value, kmp_uint32 checker );
 extern kmp_uint32 __kmp_neq_4( kmp_uint32 value, kmp_uint32 checker );
 extern kmp_uint32 __kmp_lt_4(  kmp_uint32 value, kmp_uint32 checker );
 extern kmp_uint32 __kmp_ge_4(  kmp_uint32 value, kmp_uint32 checker );
 extern kmp_uint32 __kmp_le_4(  kmp_uint32 value, kmp_uint32 checker );
 extern kmp_uint32 __kmp_wait_yield_4( kmp_uint32 volatile * spinner, kmp_uint32 checker, kmp_uint32 (*pred) (kmp_uint32, kmp_uint32), void * obj );
+extern void __kmp_wait_yield_4_ptr( void * spinner, kmp_uint32 checker, kmp_uint32 (* pred)( void *, kmp_uint32 ), void * obj );
 
 class kmp_flag_32;
 class kmp_flag_64;
 class kmp_flag_oncore;
 extern void __kmp_wait_32(kmp_info_t *this_thr, kmp_flag_32 *flag, int final_spin
 #if USE_ITT_BUILD
                    , void * itt_sync_obj
 #endif

runtime/src/kmp_dispatch.cpp

while(!f(r = TCR_4(*spin), check)) {
         /* pause is in the following code */
         KMP_YIELD( TCR_4(__kmp_nth) > __kmp_avail_proc );
         KMP_YIELD_SPIN( spins );
     }
     KMP_FSYNC_SPIN_ACQUIRED( obj );
     return r;
 }
 
+void
+__kmp_wait_yield_4_ptr(void *spinner,
+                   kmp_uint32 checker,
+                   kmp_uint32 (*pred)( void *, kmp_uint32 ),
+                   void        *obj    // Higher-level synchronization object, or NULL.
+                   )
+{
+    // note: we may not belong to a team at this point
+    register void                *spin          = spinner;
+    register kmp_uint32           check         = checker;
+    register kmp_uint32           spins;
+    register kmp_uint32 (*f) ( void *, kmp_uint32 ) = pred;
+
+    KMP_FSYNC_SPIN_INIT( obj, spin );
+    KMP_INIT_YIELD( spins );
+    // main wait spin loop
+    while ( !f( spin, check ) ) {
+        KMP_FSYNC_SPIN_PREPARE( obj );
+        /* if we have waited a bit, or are oversubscribed, yield */
+        /* pause is in the following code */
+        KMP_YIELD( TCR_4( __kmp_nth ) > __kmp_avail_proc );
+        KMP_YIELD_SPIN( spins );
+    }
+    KMP_FSYNC_SPIN_ACQUIRED( obj );
+}
+
 } // extern "C"
 
 #ifdef KMP_GOMP_COMPAT
 
 void
 __kmp_aux_dispatch_init_4( ident_t *loc, kmp_int32 gtid, enum sched_type schedule,
                            kmp_int32 lb, kmp_int32 ub, kmp_int32 st,
                            kmp_int32 chunk, int push_ws )

runtime/src/kmp_lock.h

 
 #include <limits.h>    // CHAR_BIT
 #include <stddef.h>    // offsetof
 
 #include "kmp_os.h"
 #include "kmp_debug.h"
 
 #ifdef __cplusplus
+#include <atomic>
+
 extern "C" {
 #endif // __cplusplus
 
 // ----------------------------------------------------------------------------
 // Have to copy these definitions from kmp.h because kmp.h cannot be included
 // due to circular dependencies.  Will undef these at end of file.
 
 #define KMP_PAD(type, sz)     (sizeof(type) + (sz - ((sizeof(type) - 1) % (sz)) - 1))

 
 #endif // KMP_OS_LINUX && (KMP_ARCH_X86 || KMP_ARCH_X86_64 || KMP_ARCH_ARM || KMP_ARCH_AARCH64)
 
 
 // ----------------------------------------------------------------------------
 // Ticket locks.
 // ----------------------------------------------------------------------------
 
+#ifdef __cplusplus
+
 struct kmp_base_ticket_lock {
     // `initialized' must be the first entry in the lock data structure!
-    volatile union kmp_ticket_lock * initialized;  // points to the lock union if in initialized state
-    ident_t const *     location;     // Source code location of omp_init_lock().
-    volatile kmp_uint32 next_ticket;  // ticket number to give to next thread which acquires
-    volatile kmp_uint32 now_serving;  // ticket number for thread which holds the lock
-    volatile kmp_int32  owner_id;     // (gtid+1) of owning thread, 0 if unlocked
-    kmp_int32           depth_locked; // depth locked, for nested locks only
-    kmp_lock_flags_t    flags;        // lock specifics, e.g. critical section lock
+    std::atomic<bool>     initialized;
+    volatile union kmp_ticket_lock *self; // points to the lock union
+    ident_t const *       location;       // Source code location of omp_init_lock().
+    std::atomic<unsigned> next_ticket;    // ticket number to give to next thread which acquires
+    std::atomic<unsigned> now_serving;    // ticket number for thread which holds the lock
+    std::atomic<int>      owner_id;       // (gtid+1) of owning thread, 0 if unlocked
+    std::atomic<int>      depth_locked;   // depth locked, for nested locks only
+    kmp_lock_flags_t      flags;          // lock specifics, e.g. critical section lock
 };
 
+#else // __cplusplus
+
+struct kmp_base_ticket_lock;
+
+#endif // !__cplusplus
+
 typedef struct kmp_base_ticket_lock kmp_base_ticket_lock_t;
 
 union KMP_ALIGN_CACHE kmp_ticket_lock {
     kmp_base_ticket_lock_t lk;       // This field must be first to allow static initializing.
     kmp_lock_pool_t pool;
     double                 lk_align; // use worst case alignment
     char                   lk_pad[ KMP_PAD( kmp_base_ticket_lock_t, CACHE_LINE ) ];
 };
 
 typedef union kmp_ticket_lock kmp_ticket_lock_t;
 
 //
 // Static initializer for simple ticket lock variables. Usage:
 //    kmp_ticket_lock_t xlock = KMP_TICKET_LOCK_INITIALIZER( xlock );
 // Note the macro argument. It is important to make var properly initialized.
 //
-#define KMP_TICKET_LOCK_INITIALIZER( lock ) { { (kmp_ticket_lock_t *) & (lock), NULL, 0, 0, 0, -1 } }
+#define KMP_TICKET_LOCK_INITIALIZER( lock ) { { ATOMIC_VAR_INIT(true), \
+                                                              &(lock), \
+                                                                 NULL, \
+                                                  ATOMIC_VAR_INIT(0U), \
+                                                  ATOMIC_VAR_INIT(0U), \
+                                                   ATOMIC_VAR_INIT(0), \
+                                                  ATOMIC_VAR_INIT(-1)    } }
 
 extern int __kmp_acquire_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid );
 extern int __kmp_test_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid );
 extern int __kmp_test_ticket_lock_with_cheks( kmp_ticket_lock_t *lck, kmp_int32 gtid );
 extern int __kmp_release_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid );
 extern void __kmp_init_ticket_lock( kmp_ticket_lock_t *lck );
 extern void __kmp_destroy_ticket_lock( kmp_ticket_lock_t *lck );
 

runtime/src/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 <atomic>
 
 #include "kmp.h"
 #include "kmp_itt.h"
 #include "kmp_i18n.h"
 #include "kmp_lock.h"
 #include "kmp_io.h"
 
 #if KMP_USE_FUTEX

 
 
 /* ------------------------------------------------------------------------ */
 /* ticket (bakery) locks */
 
 static kmp_int32
 __kmp_get_ticket_lock_owner( kmp_ticket_lock_t *lck )
 {
-    return TCR_4( lck->lk.owner_id ) - 1;
+    return std::atomic_load( &lck->lk.owner_id ) - 1;
 }
 
 static inline bool
 __kmp_is_ticket_lock_nestable( kmp_ticket_lock_t *lck )
 {
-    return lck->lk.depth_locked != -1;
+    return std::atomic_load( &lck->lk.depth_locked ) != -1;
 }
 
 static kmp_uint32
-__kmp_bakery_check(kmp_uint32 value, kmp_uint32 checker)
+__kmp_bakery_check(void *value, kmp_uint32 checker)
 {
-    register kmp_uint32 pause;
-
-    if (value == checker) {
-        return TRUE;
-    }
-    for (pause = checker - value; pause != 0; --pause);
-    return FALSE;
+    return std::atomic_load( (std::atomic<unsigned> *)value ) == checker;
 }
 
 __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 );
+    kmp_uint32 my_ticket = std::atomic_fetch_add_explicit( &lck->lk.next_ticket, 1U, std::memory_order_acquire );
 
 #ifdef USE_LOCK_PROFILE
-    if ( TCR_4( lck->lk.now_serving ) != my_ticket )
+    if ( std::atomic_load( &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);
+    if ( std::atomic_load( &lck->lk.now_serving ) == my_ticket ) {
         return KMP_LOCK_ACQUIRED_FIRST;
     }
-    KMP_WAIT_YIELD( &lck->lk.now_serving, my_ticket, __kmp_bakery_check, lck );
-    KMP_FSYNC_ACQUIRED(lck);
+    KMP_WAIT_YIELD_PTR( &lck->lk.now_serving, my_ticket, __kmp_bakery_check, lck );
     return KMP_LOCK_ACQUIRED_FIRST;
 }
 
 int
 __kmp_acquire_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid )
 {
     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 ) {
+
+    if ( ! std::atomic_load( &lck->lk.initialized ) ) {
+        KMP_FATAL( LockIsUninitialized, func );
+    }
+    if ( lck->lk.self != lck ) {
         KMP_FATAL( LockIsUninitialized, func );
     }
     if ( __kmp_is_ticket_lock_nestable( lck ) ) {
         KMP_FATAL( LockNestableUsedAsSimple, func );
     }
     if ( ( gtid >= 0 ) && ( __kmp_get_ticket_lock_owner( lck ) == gtid ) ) {
         KMP_FATAL( LockIsAlreadyOwned, func );
     }
 
     __kmp_acquire_ticket_lock( lck, gtid );
 
-    lck->lk.owner_id = gtid + 1;
+    std::atomic_store( &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 my_ticket = std::atomic_load( &lck->lk.next_ticket );
+
+    if ( std::atomic_load( &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 );
+        if ( std::atomic_compare_exchange_strong_explicit( &lck->lk.next_ticket,
+             &my_ticket, next_ticket, std::memory_order_acquire, std::memory_order_acquire )) {
             return TRUE;
         }
     }
     return FALSE;
 }
 
 static int
 __kmp_test_ticket_lock_with_checks( kmp_ticket_lock_t *lck, kmp_int32 gtid )
 {
     char const * const func = "omp_test_lock";
-    if ( lck->lk.initialized != lck ) {
+
+    if ( ! std::atomic_load( &lck->lk.initialized ) ) {
+        KMP_FATAL( LockIsUninitialized, func );
+    }
+    if ( lck->lk.self != lck ) {
         KMP_FATAL( LockIsUninitialized, func );
     }
     if ( __kmp_is_ticket_lock_nestable( lck ) ) {
         KMP_FATAL( LockNestableUsedAsSimple, func );
     }
 
     int retval = __kmp_test_ticket_lock( lck, gtid );
 
     if ( retval ) {
-        lck->lk.owner_id = gtid + 1;
+        std::atomic_store( &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_uint32 distance = std::atomic_load( &lck->lk.next_ticket ) - std::atomic_load( &lck->lk.now_serving );
 
-    KMP_MB();       /* Flush all pending memory write invalidates.  */
+    std::atomic_fetch_add_explicit( &lck->lk.now_serving, 1U, std::memory_order_release );
 
     KMP_YIELD( distance
       > (kmp_uint32) (__kmp_avail_proc ? __kmp_avail_proc : __kmp_xproc) );
     return KMP_LOCK_RELEASED;
 }
 
 static int
 __kmp_release_ticket_lock_with_checks( kmp_ticket_lock_t *lck, kmp_int32 gtid )
 {
     char const * const func = "omp_unset_lock";
-    KMP_MB();  /* in case another processor initialized lock */
-    if ( lck->lk.initialized != lck ) {
+
+    if ( ! std::atomic_load( &lck->lk.initialized ) ) {
+        KMP_FATAL( LockIsUninitialized, func );
+    }
+    if ( lck->lk.self != lck ) {
         KMP_FATAL( LockIsUninitialized, func );
     }
     if ( __kmp_is_ticket_lock_nestable( lck ) ) {
         KMP_FATAL( LockNestableUsedAsSimple, func );
     }
     if ( __kmp_get_ticket_lock_owner( lck ) == -1 ) {
         KMP_FATAL( LockUnsettingFree, func );
     }
     if ( ( gtid >= 0 ) && ( __kmp_get_ticket_lock_owner( lck ) >= 0 )
       && ( __kmp_get_ticket_lock_owner( lck ) != gtid ) ) {
         KMP_FATAL( LockUnsettingSetByAnother, func );
     }
     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;
+    lck->lk.self = lck;
+    std::atomic_store( &lck->lk.next_ticket, 0U );
+    std::atomic_store( &lck->lk.now_serving, 0U );
+    std::atomic_store( &lck->lk.owner_id, 0 ); // no thread owns the lock.
+    std::atomic_store( &lck->lk.depth_locked, -1 ); // -1 => not a nested lock.
+    std::atomic_store( &lck->lk.initialized, true );
 }
 
 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;
+    std::atomic_store( &lck->lk.initialized, false );
+    lck->lk.self = NULL;
+    lck->lk.location = NULL;
+    std::atomic_store( &lck->lk.next_ticket, 0U );
+    std::atomic_store( &lck->lk.now_serving, 0U );
+    std::atomic_store( &lck->lk.owner_id, 0 );
+    std::atomic_store( &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 ) {
+
+    if ( ! std::atomic_load( &lck->lk.initialized ) ) {
+        KMP_FATAL( LockIsUninitialized, func );
+    }
+    if ( lck->lk.self != lck ) {
         KMP_FATAL( LockIsUninitialized, func );
     }
     if ( __kmp_is_ticket_lock_nestable( lck ) ) {
         KMP_FATAL( LockNestableUsedAsSimple, func );
     }
     if ( __kmp_get_ticket_lock_owner( lck ) != -1 ) {
         KMP_FATAL( LockStillOwned, func );
     }
     __kmp_destroy_ticket_lock( lck );
 }
 
 
 //
 // nested ticket locks
 //
 
 int
 __kmp_acquire_nested_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid )
 {
     KMP_DEBUG_ASSERT( gtid >= 0 );
 
     if ( __kmp_get_ticket_lock_owner( lck ) == gtid ) {
-        lck->lk.depth_locked += 1;
+        std::atomic_fetch_add_explicit( &lck->lk.depth_locked, 1, std::memory_order_acquire );
         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;
+        std::atomic_store( &lck->lk.depth_locked, 1 );
+        std::atomic_store( &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 ) {
+
+    if ( ! std::atomic_load( &lck->lk.initialized ) ) {
+        KMP_FATAL( LockIsUninitialized, func );
+    }
+    if ( lck->lk.self != lck ) {
         KMP_FATAL( LockIsUninitialized, func );
     }
     if ( ! __kmp_is_ticket_lock_nestable( lck ) ) {
         KMP_FATAL( LockSimpleUsedAsNestable, func );
     }
     return __kmp_acquire_nested_ticket_lock( lck, gtid );
 }
 
 int
 __kmp_test_nested_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid )
 {
     int retval;
 
     KMP_DEBUG_ASSERT( gtid >= 0 );
 
     if ( __kmp_get_ticket_lock_owner( lck ) == gtid ) {
-        retval = ++lck->lk.depth_locked;
+        retval = std::atomic_fetch_add_explicit( &lck->lk.depth_locked, 1, std::memory_order_acquire ) + 1;
     }
     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;
+        std::atomic_store( &lck->lk.depth_locked, 1 );
+        std::atomic_store( &lck->lk.owner_id, gtid + 1 );
+        retval = 1;
     }
     return retval;
 }
 
 static int
 __kmp_test_nested_ticket_lock_with_checks( kmp_ticket_lock_t *lck,
   kmp_int32 gtid )
 {
     char const * const func = "omp_test_nest_lock";
-    if ( lck->lk.initialized != lck ) {
+
+    if ( ! std::atomic_load( &lck->lk.initialized ) ) {
+        KMP_FATAL( LockIsUninitialized, func );
+    }
+    if ( lck->lk.self != lck ) {
         KMP_FATAL( LockIsUninitialized, func );
     }
     if ( ! __kmp_is_ticket_lock_nestable( lck ) ) {
         KMP_FATAL( LockSimpleUsedAsNestable, func );
     }
     return __kmp_test_nested_ticket_lock( lck, gtid );
 }
 
 int
 __kmp_release_nested_ticket_lock( kmp_ticket_lock_t *lck, kmp_int32 gtid )
 {
     KMP_DEBUG_ASSERT( gtid >= 0 );
 
-    KMP_MB();
-    if ( --(lck->lk.depth_locked) == 0 ) {
-        KMP_MB();
-        lck->lk.owner_id = 0;
+    if ( ( std::atomic_fetch_add_explicit( &lck->lk.depth_locked, -1, std::memory_order_release ) - 1 ) == 0 ) {
+        std::atomic_store( &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 ) {
+
+    if ( ! std::atomic_load( &lck->lk.initialized ) ) {
+        KMP_FATAL( LockIsUninitialized, func );
+    }
+    if ( lck->lk.self != lck ) {
         KMP_FATAL( LockIsUninitialized, func );
     }
     if ( ! __kmp_is_ticket_lock_nestable( lck ) ) {
         KMP_FATAL( LockSimpleUsedAsNestable, func );
     }
     if ( __kmp_get_ticket_lock_owner( lck ) == -1 ) {
         KMP_FATAL( LockUnsettingFree, func );
     }
     if ( __kmp_get_ticket_lock_owner( lck ) != gtid ) {
         KMP_FATAL( LockUnsettingSetByAnother, func );
     }
     return __kmp_release_nested_ticket_lock( lck, gtid );
 }
 
 void
 __kmp_init_nested_ticket_lock( kmp_ticket_lock_t * lck )
 {
     __kmp_init_ticket_lock( lck );
-    lck->lk.depth_locked = 0; // >= 0 for nestable locks, -1 for simple locks
+    std::atomic_store( &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;
+    std::atomic_store( &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 ) {
+
+    if ( ! std::atomic_load( &lck->lk.initialized ) ) {
+        KMP_FATAL( LockIsUninitialized, func );
+    }
+    if ( lck->lk.self != lck ) {
         KMP_FATAL( LockIsUninitialized, func );
     }
     if ( ! __kmp_is_ticket_lock_nestable( lck ) ) {
         KMP_FATAL( LockSimpleUsedAsNestable, func );
     }
     if ( __kmp_get_ticket_lock_owner( lck ) != -1 ) {
         KMP_FATAL( LockStillOwned, func );
     }
     __kmp_destroy_nested_ticket_lock( lck );
 }
 
 
 //
 // access functions to fields which don't exist for all lock kinds.
 //
 
 static int
 __kmp_is_ticket_lock_initialized( kmp_ticket_lock_t *lck )
 {
-    return lck == lck->lk.initialized;
+    return std::atomic_load( &lck->lk.initialized ) && ( lck->lk.self == lck );
 }
 
 static const ident_t *
 __kmp_get_ticket_lock_location( kmp_ticket_lock_t *lck )
 {
     return lck->lk.location;
 }
 

runtime/src/kmp_os.h

 
 #ifdef USE_VOLATILE_CAST
 # define VOLATILE_CAST(x)        (volatile x)
 #else
 # define VOLATILE_CAST(x)        (x)
 #endif
 
 #define KMP_WAIT_YIELD           __kmp_wait_yield_4
+#define KMP_WAIT_YIELD_PTR       __kmp_wait_yield_4_ptr
 #define KMP_EQ                   __kmp_eq_4
 #define KMP_NEQ                  __kmp_neq_4
 #define KMP_LT                   __kmp_lt_4
 #define KMP_GE                   __kmp_ge_4
 #define KMP_LE                   __kmp_le_4
 
 /* Workaround for Intel(R) 64 code gen bug when taking address of static array (Intel(R) 64 Tracker #138) */
 #if (KMP_ARCH_X86_64 || KMP_ARCH_PPC64) && KMP_OS_LINUX

runtime/src/kmp_tasking.c

if ( (TCR_4(victim_td -> td.td_deque_ntasks) == 0) ||
                       victim_td->td.td_deque_head, victim_td->td.td_deque_tail) );
         return NULL;
     }
 
     KMP_DEBUG_ASSERT( victim_td -> td.td_deque != NULL );
 
     if ( !is_constrained ) {
         taskdata = victim_td -> td.td_deque[ victim_td -> td.td_deque_head ];
+        KMP_ASSERT(taskdata);
         // Bump head pointer and Wrap.
         victim_td -> td.td_deque_head = ( victim_td -> td.td_deque_head + 1 ) & TASK_DEQUE_MASK;
     } else {
         // While we have postponed tasks let's steal from tail of the deque (smaller tasks)
         kmp_int32 tail = ( victim_td -> td.td_deque_tail - 1 ) & TASK_DEQUE_MASK;  // Wrap index.
         taskdata = victim_td -> td.td_deque[ tail ];
+        KMP_ASSERT(taskdata);
         // we need to check if the candidate obeys task scheduling constraint:
         // only child of current task can be scheduled
         kmp_taskdata_t * current = __kmp_threads[ gtid ]->th.th_current_task;
         kmp_int32        level = current->td_level;
         kmp_taskdata_t * parent = taskdata->td_parent;
         while ( parent != current && parent->td_level > level ) {
             parent = parent->td_parent;  // check generation up to the level of the current task
             KMP_DEBUG_ASSERT(parent != NULL);