[RFC] powerpc: optimizing random() and POSIX question

[RFC] powerpc: optimizing random() and POSIX question

[Raphael M Zinsly]

Hi,

I’m investigating ways to optimize random() for powerpc and got some 
questions regarding POSIX.
The current code on stdlib/random.c does:

long int
__random (void)
{
   int32_t retval;

   __libc_lock_lock (lock);

   (void) __random_r (&unsafe_state, &retval);

   __libc_lock_unlock (lock);

   return retval;
}

If I remove the lock in order to use lqarx/stqcx to access fptr and rptr 
(that are adjacents), then compute the result as is done in random_r, 
will this still be compliant with POSIX?
As the data is accessed atomically, only one thread access the critical 
section at a time. Am I missing something?


Thanks,
-- 
Raphael Moreira Zinsly
IBM
Linux on Power Toolchain

Re: [RFC] powerpc: optimizing random() and POSIX question

[Florian Weimer]

* Raphael M. Zinsly:

> If I remove the lock in order to use lqarx/stqcx to access fptr and
> rptr (that are adjacents), then compute the result as is done in
> random_r, will this still be compliant with POSIX?

I think POSIX requires random to the thread-safe in the presence of
concurrent initstate calls.  Would your change preserve this property?

This means that random in other threads would either produce values from
the new sequence, or from the old sequence.  But not values that are
part of neither sequence.

Thanks,
Florian

Re: [RFC] powerpc: optimizing random() and POSIX question

[Raphael M Zinsly]

On 11/02/2020 11:42, Florian Weimer wrote:
> I think POSIX requires random to the thread-safe in the presence of
> concurrent initstate calls.  Would your change preserve this property?
> 

Yes, concurrent calls to initstate, setstate or srandom will still be 
mutual exclusive.

Thanks,
-- 
Raphael Moreira Zinsly
IBM
Linux on Power Toolchain

Re: [RFC] powerpc: optimizing random() and POSIX question

[Florian Weimer]

* Raphael M. Zinsly:

> On 11/02/2020 11:42, Florian Weimer wrote:
>> I think POSIX requires random to the thread-safe in the presence of
>> concurrent initstate calls.  Would your change preserve this property?
>>
>
> Yes, concurrent calls to initstate, setstate or srandom will still be
> mutual exclusive.

Then I don't see any immediate problems with this change.

Thanks,
Florian

Re: [RFC] powerpc: optimizing random() and POSIX question

[Adhemerval Zanella]

On 12/02/2020 10:23, Florian Weimer wrote:
> * Raphael M. Zinsly:
> 
>> On 11/02/2020 11:42, Florian Weimer wrote:
>>> I think POSIX requires random to the thread-safe in the presence of
>>> concurrent initstate calls.  Would your change preserve this property?
>>>
>>
>> Yes, concurrent calls to initstate, setstate or srandom will still be
>> mutual exclusive.
> 
> Then I don't see any immediate problems with this change.

So if I understood correctly, you want to make a lock-free implementation
of 'random' by doing something like:

--
__int128_t unsafe_state;

long int
__random_r (void)
{
  union {
    __int128_t u128;
    struct {
      uint32_t *fptr, *rptr, *end_ptr;
    } p;
  } u_e, u_d;

  while (1)
    {
       u_e.u128 = atomic_load_explicit ((__int128*) &unsafe_state,
                                         memory_order_relaxed);
       u_d = u_e;

       // update u.d.*

       if (atomic_compare_exchange_weak ((__int128*) &unsafe_state,
                                         &u_e.u128, u_d.u128))
          break;
    }

  return 0;
}
--

Besides the issue that at line stdlib/random_r.c:375 __random_r not
only updates the pointer value, but also the pointer value (which
would make failed CAS to update the random state), I failing to see
the either the value of adding a powerpc specific implementation
to such bad interface or to maybe implement a generic lock-free
implementation since we have __random_r.

I would rather focus on provide a better interface with a better
implementation, such as the lock-free arc4random one Florian has
suggested sometime ago. 

Re: [RFC] powerpc: optimizing random() and POSIX question

[Wilco Dijkstra]

Hi,

Wouldn't the easiest and safest option to be just add the single-threaded check
so 99% of applications just bypass the locks?

Also I would strongly suggest to optimize the generic code first - target-specific
optimizations are almost always counter productive in the long term.

Cheers,
Wilco