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

[Stefan Liebler]

On 03/14/2017 04:55 PM, Stefan Liebler wrote:
> On 02/20/2017 02:51 PM, Torvald Riegel wrote:
>> On Mon, 2017-02-20 at 13:15 +0100, Stefan Liebler wrote:
>>>>>> 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 would guess that this would be the right place for a stub / generic
>> variant of such a header, but I'm not quite sure.
>>
>>>>
>>>> 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.
>>
>> Okay.  So let's do that.
>>
> Done. The wrapper-pthread_spin_lock.c files in sysdeps subfolders are
> removed and the option SPIN_LOCK_READS_BETWEEN_CMPXCHG is not available
> anymore.
> Instead there is only a loop of plain reads until we observe an not
> acquired lock.
> See comment in nptl/pthread_spin_lock.c.
>
>>>> 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.
>>
>> I guess this may then be yet another property atomic-machine.h could
>> expose: Whether an atomic fetch-and-and exists and is not implemented
>> throough a CAS loop.  Something like lll_unlock would then do an
>> exchange or fetch-and-and, and if that fails, a CAS loop.
>>
>>> 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.
>>
>> Thanks.
>>
>>>> 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.
>>
>> Yes, it may not be enough (e.g., you say that s390 may have fetch_and
>> but not an exchange, but other archs may just have an exchange but no
>> custom fetch_and).
>> So maybe we should add ATOMIC_EXCHANGE_USES_CAS and
>> ATOMIC_FETCH_AND_USES_CAS for now, and add further ones on demand?
>>
>>>> /* 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.
>>
>> That can be useful, but what I outlined would be about a more generic
>> case.  If you are going to solve this for your arch in gcc, you might
>> not need to address this in this patch.
>>
>>>>
>>>>
>>>> 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.
>>
>> I read this as stating that you agree that 1) doesn't need to be
>> considered.  But we still to choose between 2) and 3)  :)
>>
>> I'm not quite sure what to favor because some of the code out there that
>> uses trylock just uses it to prevent deadlock (e.g., when trying to
>> acquire multiple locks at once), whereas other code uses spin_trylock to
>> implement their own back-off and bounded spinning.
>> I lean towards assuming that lock acquisitons, including the former use
>> case for trylock, are supposed to succeed in the common case.  That is,
>> I would pick 2), but I have no data to back this up.
>>
>> Either way, whatever we choose, we should document polish the cases 1-3
>> above and the reasoning behind our choice for one of them, and add it as
>> a comment to the spinlock code.
>>
>
> Okay. I've attached an updated patch. It is now using case 2).
> This choice applies to pthread_spin_trylock.c and the first attempt to
> acquire the lock in pthread_spin_lock.c.
> Therefore I've introduced ATOMIC_EXCHANGE_USES_CAS for all architectures
> in atomic-machine.h files. There is a check in include/atomic.h which
> ensures that it is defined to either 0 or 1. Can you please review the
> setting of 0 or 1?
>
> Bye Stefan
Ping