[PATCH 1/2] Optimize generic spinlock code and use C11 like atomic macros.

[Stefan Liebler]

On 02/18/2017 05:57 PM, Torvald Riegel wrote:
> On Wed, 2017-02-15 at 10:35 +0100, Stefan Liebler wrote:
>> On 02/13/2017 09:29 PM, Torvald Riegel wrote:
>>> Thanks for working on this.  Detailed comments below.
>>>
>>> Generally, I think we need to keep working on optimizing this (this can
>>> happen in follow-up patches).  For example, we should have
>>> microbenchmarks for the exchange vs. CAS choice.
>>>
>>> Also, some of the tuning knobs such as
>>> SPIN_TRYLOCK_USE_CMPXCHG_INSTEAD_OF_XCHG apply to atomics in general and
>>> not just the spinlock.  I'd prefer if these where in a state in which we
>>> could add them as property that's part of the atomics interface.
>>>
>>> On Wed, 2017-02-08 at 15:49 +0100, Stefan Liebler wrote:
>>>> diff --git a/include/atomic.h b/include/atomic.h
>>>> index 7f32640..770db4a 100644
>>>> --- a/include/atomic.h
>>>>
>>>> +++ b/include/atomic.h
>>>>
>>>> @@ -54,7 +54,7 @@
>>>>     and following args.  */
>>>>  #define __atomic_val_bysize(pre, post, mem, ...)			      \
>>>>    ({									      \
>>>> -    __typeof (*mem) __atg1_result;					      \
>>>>
>>>> +    __typeof ((__typeof (*(mem))) *(mem)) __atg1_result;		      \
>>>>
>>>>      if (sizeof (*mem) == 1)						      \
>>>>        __atg1_result = pre##_8_##post (mem, __VA_ARGS__);		      \
>>>>      else if (sizeof (*mem) == 2)					      \
>>>> @@ -162,9 +162,9 @@
>>>>  /* Store NEWVALUE in *MEM and return the old value.  */
>>>>  #ifndef atomic_exchange_acq
>>>>  # define atomic_exchange_acq(mem, newvalue) \
>>>> -  ({ __typeof (*(mem)) __atg5_oldval;					      \
>>>>
>>>> +  ({ __typeof ((__typeof (*(mem))) *(mem)) __atg5_oldval;		      \
>>>>
>>>>       __typeof (mem) __atg5_memp = (mem);				      \
>>>> -     __typeof (*(mem)) __atg5_value = (newvalue);			      \
>>>>
>>>> +     __typeof ((__typeof (*(mem))) *(mem)) __atg5_value = (newvalue);	      \
>>>>
>>>>  									      \
>>>>       do									      \
>>>>         __atg5_oldval = *__atg5_memp;					      \
>>>> @@ -668,7 +668,7 @@ void __atomic_link_error (void);
>>>>
>>>>  # ifndef atomic_load_relaxed
>>>>  #  define atomic_load_relaxed(mem) \
>>>> -   ({ __typeof (*(mem)) __atg100_val;					      \
>>>>
>>>> +   ({ __typeof ((__typeof (*(mem))) *(mem)) __atg100_val;		      \
>>>>
>>>>     __asm ("" : "=r" (__atg100_val) : "0" (*(mem)));			      \
>>>>     __atg100_val; })
>>>>  # endif
>>>
>>> You could keep these changes, but it's a bit odd because you only apply
>>> them for the functions you needed them for.  I think it would be better
>>> to just remove the volatile qualification in the caller (ie, cast lock
>>> to nonvolatile in pthread_spin_lock etc.
>>>
>> Yes, I've only applied them for the functions needed in spinlock-code.
>> Removing volatile from type pthread_spinlock_t is no option and
>> casting the volatile pointer to a non-volatile pointer is undefined.
>> See comment from Florian:
>> On 12/16/2016 09:12 PM, Florian Weimer wrote:
>>> That's undefined:
>>>
>>> “If an attempt is made to refer to an object defined with a
>>> volatile-qualified type through use of an lvalue with
>>> non-volatile-qualified type, the behavior is undefined.”
>>>
>>> But we cannot drop the volatile qualifier from the definition of
>>> pthread_spinlock_t because it would change the C++ mangling of
>>> pthread_spinlock_t * and similar types.
>
> Generally, I wouldn't agree with Florian's comment.  However, all we are
> interested in is the storage behind the volatile-qualified type.  Users
> aren't allowed the object through other means than the pthread_spin*
> functions, so if we cast everywhere, we'll never have any
> volatile-qualified accesses.  I believe none of the architectures we
> support makes weaker requirements on alignment for volatile-qualified
> than for non-volatile-qualified types, so I can't see any problem in
> practice with the cast.
>
>
>>>>
>>>> +  if (__glibc_likely (atomic_exchange_acquire (lock, 1) == 0))
>>>>
>>>>      return 0;
>>>>
>>>> +  int val;
>>>>
>>>>    do
>>>>      {
>>>>        /* The lock is contended and we need to wait.  Going straight back
>>>> @@ -50,20 +53,39 @@ pthread_spin_lock (pthread_spinlock_t *lock)
>>>>  	 On the other hand, we do want to update memory state on the local core
>>>>  	 once in a while to avoid spinning indefinitely until some event that
>>>>  	 will happen to update local memory as a side-effect.  */
>>>> -      if (SPIN_LOCK_READS_BETWEEN_CMPXCHG >= 0)
>>>>
>>>> +
>>>>
>>>> +#if SPIN_LOCK_READS_BETWEEN_CMPXCHG >= 0
>>>>
>>>> +      /* Use at most SPIN_LOCK_READS_BETWEEN_CMPXCHG plain reads between the
>>>>
>>>> +	 atomic compare and exchanges.  */
>>>>
>> Also changed this comment to:
>> /* Use at most SPIN_LOCK_READS_BETWEEN_CMPXCHG relaxed MO reads between
>>     the atomic compare and exchanges.  */
>
> Thanks.
>
>>> A while ago we tried hard to remove all code that would fail silently
>>> when a macro had a typo in the name, for example.  We still have a few
>>> of them left (e.g., in the atomics), but I think this here doesn't
>>> warrant an exception.
>>>
>> Okay. You're right.
>>
>> In comment of patch 2/2, you've mentioned a header where an architecture
>> shall define those parameters.
>> Thus I've added the file nptl/pthread_spin_parameters.h.
>
> I think the stub version should be in sysdeps/ but the wiki is missing
> this information (default ENOTSUP location):
> https://sourceware.org/glibc/wiki/Style_and_Conventions#Proper_sysdeps_Location
In case we need a new header, shall we move it to sysdeps/nptl/ ?

>
> I think we should just get rid of SPIN_LOCK_READS_BETWEEN_CMPXCHG, and
> make some choice for SPIN_TRYLOCK_LOAD_AND_TEST_BEFORE_XCHG.  There is
> no technical reason for throwing in a CAS every now and then, and so far
> we have no evidence that it can improve performance (if that would be
> the case, we'd need to think harder about that, because we have
> spin-waiting loops elsewhere that don't want to modify the value after
> waiting for a change of the value).
Okay. For s390 we don't need a CAS every now and then.

>
> With that applied you don't have to solve the header problem in this
> patch.
>
> I'll write a separate email with suggestions about how to refactor the
> spinlock code project-wide.  Also, some more comments on the tuning
> parameters below.
>
> I'm still a bit undecided about how to deal with other arch's
> pthread_spin_lock.c files that just set SPIN_LOCK_READS_BETWEEN_CMPXCHG
> and then include the generic pthread_spin_lock.c.  Maybe it's best if we
> just remove them in this patch of yours.
>
I think the archs currently using the generic implementation have just 
copied the default value to get rid of the warning "machine-dependent 
file should define SPIN_LOCK_READS_BETWEEN_CMPXCHG". But this is only an 
assumption.
In general removing those "wrapper"-pthread_spin_lock.c files and using 
information from a header like the proposed pthread_spin_parameters.h or 
atomic-machine.h is a good approach.

>>>>
>>>> +#if SPIN_TRYLOCK_USE_CMPXCHG_INSTEAD_OF_XCHG == 1
>>>>
>>>> +  /* Load and test the spinlock and only try to lock the spinlock if it is
>>>>
>>>> +     free.  */
>>>>
>>>> +  int val = atomic_load_relaxed (lock);
>>>>
>>>> +  if (__glibc_likely (val == 0 && atomic_exchange_acquire (lock, 1) == 0))
>>>
>>> I think that's not quite the same as a choice between CAS and exchange.
>> Yes. You are right.
>>> Doing a load first could be helpful for *both* CAS and exchange.  OTOH,
>>> if we assume that trylock will succeed most of the time, then the load
>>> is unnecessary and might be more costly (eg, if it causes the state of
>>> the cache line to change twice).
>>>
>> E.g. on s390, there exists no instruction which atomically exchanges the
>> value. Instead a CAS loop is used. The CAS instruction locks the
>> cache-line exclusively whether the value in memory equals the expected
>> old-value or not. Therefore the value is loaded and compared before
>> using the CAS instruction.
>> If no other CPU has accessed the lock-value, the load will cause
>> the state of the cache line to exclusive.
>> If the lock is not acquired, the subsequent CAS instruction does not
>> need to change the state of the cache line.
>> If another CPU has accessed the lock-value e.g. by acquiring the lock,
>> the load will cause the state of the cache line either to read-only
>> or exclusive. This depends on the other CPU - whether it has already
>> stored a new value or not.
>>
>> As this behaviour depends on the architecture, the architecture has to
>> decide whether it should load and test the lock-value before the
>> atomic-macro.
>
> I agree that the there are architecture-specific properties of atomic
> operations that have a significant effect on performance.  For s390, you
> list the following points:
> * atomic exchange (I suppose all atomic read-modify-write ops?) are
> implemented through CAS.
atomic exchange is implemented by a CAS loop due to lack of an exchange 
instruction. For exchanging to a "0", s390 can use the load-and-and 
instruction instead of a CAS loop (See my atomic-machine.h patch; For 
gcc, we plan to emit such a load-and-and instruction for builtin 
__atomic_exchange_n in future;). This also saves one register usage 
compared to the CAS loop.
Exchanging to "0" is e.g. used for lll_unlock macro or in 
malloc_consolidate.

Starting with z196 zarch CPUs, the following instructions which are used 
by the appropriate __atomic_fetch_xyz builtins instead of a CAS loop:
load-and-add, load-and-and, load-and-exclusive-or, load-and-or.
As information:
I will update my atomic-machine.h patch to use at least some of the C11 
atomic builtins or all depending on gcc version.
As additional information:
E.g. RHEL 7 / SLES 12 are using z196 as architecture baseline level.
A 64bit s390x glibc build always use zarch instructions.
A 31bit s390 glibc build does not use zarch instructions by default, but 
somebody can build glibc with gcc -mzarch option.
The latter means, that a CAS loop is used for a default 31bit s390 build.

> * CAS always brings the cache line into an exclusive state.
Yes that's true.

>
> (Is the second point correct? I'm not quite sure I understood you
> correctly: for example, you write that a load move a cache line to an
> exclusive state, which seems odd).
Not in all cases, but in the case if no other CPU accesses this cache 
line. Otherwise it is read-only.

>
> These properties are specific to the architecture, but they are not
> specific to the synchronization code (eg, to spinlocks).  Thus, I think
> such settings should be in the atomics headers (i.e., in
> atomic-machine.h).
> This should probably be a separate patch.  I would propose the following
> macros (both are bool):
> /* Nonzero iff all atomic read-modify-write operations (e.g., atomic
> exchange) are implemented using a CAS loop.  */
> #define ATOMIC_RMW_USES_CAS 1
Is one macro enough to describe all read-modify-write operations in 
include/atomic.h?
Please also see my comment above.

> /* Nonzero iff CAS always assumes it will store, and thus has cache
> performance effects similar to a store (e.g., it always puts the
> respective cacheline into an exclusive state, even if the comparison
> against the expected value fails).  */
> ATOMIC_CAS_ALWAYS_PREPARES_FOR_STORE 1
>
> I'm not sure whether there are architectures for which the second macro
> would not be true.  It would be good to investigate this, maybe we don't
> need to add this at all.
>
We plan that in future gcc will emit e.g. a load-and-test instruction in 
front of the CAS instruction if the old-value is a constant zero.
>
>
> For the spin lock specifically, we have the following possibilities:
>
> 1) If we assume that trylock will most likely succeed in practice:
> * We just do an exchange.  The properties above don't matter.
>
> 2) If we want to bias towards cases where trylock succeeds, but don't
> rule out contention:
> * If exchange not a CAS loop, and exchange is faster than CAS, do an
> exchange.
> * If exchange is a CAS loop, use a weak CAS and not an exchange so we
> bail out after the first failed attempt to change the state.
>
> 3) If we expect contention to be likely:
> * If CAS always brings the cache line into an exclusive state, then load
> first.  Then do 2).
>
> Do we have consensus yet on whether we assume 2 or 3 (I don't think 1
> buys us anything over 2)?
>
Yes. Sounds good.

>
>>>> diff --git a/nptl/pthread_spin_unlock.c b/nptl/pthread_spin_unlock.c
>>>> index 5fd73e5..f83b696 100644
>>>> --- a/nptl/pthread_spin_unlock.c
>>>>
>>>> +++ b/nptl/pthread_spin_unlock.c
>>>>
>>>> @@ -23,7 +23,9 @@
>>>>  int
>>>>  pthread_spin_unlock (pthread_spinlock_t *lock)
>>>>  {
>>>> -  atomic_full_barrier ();
>>>>
>>>> -  *lock = 0;
>>>>
>>>> +  /* The atomic_store_release synchronizes-with the atomic_exchange_acquire
>>>>
>>>> +     or atomic_compare_exchange_weak_acquire in pthread_spin_lock /
>>>>
>>>> +     pthread_spin_trylock.  */
>>>>
>>>> +  atomic_store_release (lock, 0);
>>>>
>>>>    return 0;
>>>>  }
>>>
>>> I agree with this change.  However, depending on how one interprets
>>> POSIX' memory model, one may expect lock releases to be sequentially
>>> consistent.  Nonetheless, IMO, glibc should use only release MO.
>>>
>>> But we need to announce this change.  Some of us have been considering
>>> an additional section in the manual were we specify where we deviate
>>> from POSIX; this change might be the first we're listing there (though
>>> to be fair, this is a deviation only on some architectures because on
>>> others such as powerpc I think, we've been using release MO forever).
>>>
>>>
>> As not all architectures use the generic spinlock implementation, what
>> about a NEWS entry like:
>>
>> * The new generic spinlock implementation uses C11 like atomics.
>>    The pthread_spin_unlock implementation is now using release
>>    memory order instead of sequentially consistent memory order.
>
> That's a good start, but I think we need to be more specific.  We also
> don't need to say that we use C11-like atomics because that's an
> implementation detail.
>
> I'd add something like this instead:
>
> The synchronization that pthread_spin_unlock performs has been changed
> to now be equivalent to a C11 atomic store with release memory order to
> the spin lock's memory location.  This ensures correct synchronization
> for the spin lock's operations and critical sections protected by a spin
> lock.  Previously, several (but not all) architectures used stronger
> synchronization (e.g., containing what is often called a full barrier).
> This change can improve performance, but may affect odd fringe uses of
> spin locks that depend on the previous behavior (e.g., using spin locks
> as atomic variables to try to implement Dekker's mutual exclusion
> algorithm).
>
> This should highlight the potential change for the weird (ab)uses of
> spin locks but also makes it clear that this won't affect correctness of
> all the common code.
>
Okay. The next patch-iteration will use the text above.