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

[Stefan Liebler]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Optimize-generic-spinlock-code-and-use-C11-like-atom.patch
Type: text/x-patch
Size: 37166 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20170314/11dc129d/attachment.bin>