[PATCH v2] nptl: Add backoff mechanism to spinlock loop

[Adhemerval Zanella]

On 30/03/2022 14:07, Noah Goldstein wrote:
> On Wed, Mar 30, 2022 at 6:54 AM Adhemerval Zanella via Libc-alpha
> <libc-alpha@sourceware.org> wrote:
>>
>>
>>
>> On 28/03/2022 05:47, Wangyang Guo via Libc-alpha wrote:
>>> When mutiple threads waiting for lock at the same time, once lock owner
>>> releases the lock, waiters will see lock available and all try to lock,
>>> which may cause an expensive CAS storm.
>>>
>>> Binary exponential backoff with random jitter is introduced. As try-lock
>>> attempt increases, there is more likely that a larger number threads
>>> compete for adaptive mutex lock, so increase wait time in exponential.
>>> A random jitter is also added to avoid synchronous try-lock from other
>>> threads.
>>>
>>> v2: Remove read-check before try-lock for performance.
>>>
>>> Signed-off-by: Wangyang Guo <wangyang.guo@intel.com>
>>> ---
>>>  nptl/pthread_mutex_lock.c | 25 ++++++++++++++++---------
>>>  1 file changed, 16 insertions(+), 9 deletions(-)
>>>
>>> diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c
>>> index d2e652d151..7e75ec1cba 100644
>>> --- a/nptl/pthread_mutex_lock.c
>>> +++ b/nptl/pthread_mutex_lock.c
>>> @@ -26,6 +26,7 @@
>>>  #include <futex-internal.h>
>>>  #include <stap-probe.h>
>>>  #include <shlib-compat.h>
>>> +#include <random-bits.h>
>>>
>>>  /* Some of the following definitions differ when pthread_mutex_cond_lock.c
>>>     includes this file.  */
>>> @@ -64,11 +65,6 @@ lll_mutex_lock_optimized (pthread_mutex_t *mutex)
>>>  # define PTHREAD_MUTEX_VERSIONS 1
>>>  #endif
>>>
>>> -#ifndef LLL_MUTEX_READ_LOCK
>>> -# define LLL_MUTEX_READ_LOCK(mutex) \
>>> -  atomic_load_relaxed (&(mutex)->__data.__lock)
>>> -#endif
>>> -
>>>  static int __pthread_mutex_lock_full (pthread_mutex_t *mutex)
>>>       __attribute_noinline__;
>>>
>>> @@ -138,17 +134,28 @@ PTHREAD_MUTEX_LOCK (pthread_mutex_t *mutex)
>>>         int cnt = 0;
>>>         int max_cnt = MIN (max_adaptive_count (),
>>>                            mutex->__data.__spins * 2 + 10);
>>> +       int spin_count, exp_backoff = 1;
>>> +       unsigned int jitter = random_bits ();
>>
>> This will issue a syscall for architectures that do not have clock_gettime
>> on vDSO, which is a performance regression.  You will need to move the
>> jitter setup to be arch-specific, where the generic interface setting
>> no random jitter.
> 
> What would be the best init jitter for arch w/ only syscall timers? TID? Or
> something else?

We don't cached the TID anymore, so it would still generate syscalls. I think
it safer that since we don't have a internal source of entropy (Florian send
some time ago a arc4random implementation that we could use in this case)
the generic interface would do any jitter at all (so it would be basically
the algorithm we already have).