Re: [PATCH 2/2] Add single-threaded fast path to rand()

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

On 2024-03-21 09:33, Cristian Rodríguez wrote:
> On Thu, Mar 21, 2024 at 4:39 AM Florian Weimer <fweimer@redhat.com> wrote:
>>
>> * Adhemerval Zanella Netto:
>>
>>> On 20/03/24 11:18, Cristian Rodríguez wrote:
>>>> On Wed, Mar 20, 2024 at 9:31 AM Adhemerval Zanella Netto
>>>> <adhemerval.zanella@linaro.org> wrote:
>>>>
>>>>
>>>>> I don't have a strong opinion on this rand patch, if this idea is to
>>>>> have it as an workbench for a possible single-thread lock optimization
>>>>> it should be fine.  It is just that I don't see much gain in optimizing
>>>>> such a bad interface (although we still lack a proper userland PRNG).
>>>>
>>>> Yeah, it should be no surprise this interfaces are bad,
>>>> I thought this was common knowledge.
>>>>
>>>> we need something like https://github.com/C2SP/C2SP/blob/main/chacha8rand.md
>>>> which prety much outperforms even non-CS algorithms in at least 64 bit x86.
>>>> but the question of the state remains.global? TLS? how to discard it
>>>> in all the appropriate occasions?
>>>
>>> And this is the arc4random in userspace discussion all over again.
>>
>> Agreed.  But what has changed that we know now that Linux won't provide
>> us with vDSO acceleration for arc4random.  So I think it wouldn't be
>> unreasonable to roll our own.  Right now, the switch to arc4random
>> provided by glibc is a massive performance regression compared to other
>> implementations.
> 
> 
> Afaik the other path that hasn't been tried is rseq no ? could the
> kernel provide a random state this way that it is cleared on the right
> conditions..

Letting rseq know about userspace random state would add a lot of coupling
between kernel and userspace. I wonder if we can achieve the speed up you
are looking for using existing rseq/membarrier features.

At the last GNU Cauldron, I created a biased locking prototype for Florian
based on rseq:

https://github.com/compudj/librseq/tree/biased-lock
https://github.com/compudj/librseq/blob/biased-lock/tests/rseq_biased_lock.h
https://github.com/compudj/librseq/blob/biased-lock/tests/rseq_biased_lock.c
https://github.com/compudj/librseq/blob/biased-lock/tests/test_rseq_biased_lock.c

The original purpose of this prototype was to replace the FILE lock
by a biased lock, which acts as a very fast lock (a small rseq assembly
sequence of loads, comparisons, stores) as long as the thread accessing the
FILE is the thread owner thread whom created it.

If another thread attempts to access the FILE, then the internal state machine
of the biased lock transitions from RSEQ_BIASED_LOCK_STATE_ST to
RSEQ_BIASED_LOCK_STATE_MT_STARTED, issues a membarrier RSEQ_PRIVATE_EXPEDITED
(also referred to as "rseq fence") to abort all pre-existing rseq critical
sections, and then transition to RSEQ_BIASED_LOCK_STATE_MT_READY before taking
the lock.

After the biased lock has transitioned to RSEQ_BIASED_LOCK_STATE_MT_READY
it is meant to stay in that state forever. So as long as only the owner
thread uses the lock, it stays fast. This means that even a multi-threaded
process with short-lived FILE that are only used by a single thread in their
lifetime will benefit from the biased lock fast-path.

I suspect we could adapt this scheme to the srand()/rand() lock. Here is how
I see this unfold for both srand() and rand():

   - On first use (if rseq biased lock owner is NULL):
     - use rseq_biased_lock_try_set_fast_thread to set lock owner with a
       compare-and-swap (expecting NULL).
   - Take the rseq biased lock:
     - This rseq biased lock will take care of transitioning to a scheme
       which is MT-aware if it detects that the thread trying to access
       the biased lock is not the owner.

So this scheme applied to both srand() and rand() should take care of making
things really fast as long as only the biased lock owner thread uses
srand()/rand().

Its overhead would be a single system call (membarrier) issued the first
time the biased lock is accessed from a thread which differs from the
first thread which used the lock.

Thoughts ?

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com