Re: [9front] [PATCH] libc: replace lrand's algorithm

[Ori Bernstein <ori@eigenstate.org>]

On Wed, 03 Apr 2024 11:07:22 +0200
qwx@sciops.net wrote:

> On Tue Apr  2 16:38:36 +0200 2024, eolien55@disroot.org wrote:
> > qwx@sciops.net wrote:
> > > I like the idea of simplifying the tree and deleting some code,
> > > but keep in mind that the xoroshiro128+ variant is what is
> > > exposed by /dev/random via truerand(2).
> > 
> > That's not quite it. What is exposed by /dev/random is actually
> > a Chacha-based CSPRNG. truerand(2) is a cryptographic PRNG.
> 
> Ah, my bad, sorry.
> 
> 
> > However, the kernel itself (via tcp, ip, sdp, esp...) uses
> > a non-cryptographic PRNG (in nrand and rand calls, in the
> > kernel). The kernel's PRNG was changed to xoroshiro128+
> > in 10275ad6dd2. I believe it would make sense to either
> > change libc's lrand to xoroshiro128+ too, or to change
> > them both at the same time.
> [...]
> > > Most people are
> > > uninsterested in a change here because of the dichotomy between
> > > rand and truerand, the negligeable performance impact, etc.,
> > > and beyond this, it gets into "this is like, my opinion man"
> > > territory.  I wouldn't mind replacing libc's lrand with a PCG
> > > variant also exposing a 64bit version, which we don't have, if
> > > it indeed also improves the statistical properties of the prng.
> > > But that's like, my opinion man.
> > 
> > Well, this is feasible. Both PCG and xoroshiro require 128 bits
> > of state for a 64-bit output. kernel's implementation simulates
> > 128-bits operations using 2 64-bit integers. It should be feasible
> > to implement a PC64 with the same approach, or to implement
> > xoroshiro128+ (or another variant, for statistical quality of the
> > lower bits).
> > 
> > I understand the change here is highly subjective, and has
> > negligible performance impact (except for seeding/re-seeding).
> > I still believe we could, and should, implement a better PRNG
> > for libc. Kernel's PRNG has changed; why not libc's?
> > 
> > I found (rand()<<16) + rand() in kernel's devsdp, which is
> > strange considering lrand already has 32 bits of output. I
> > think this should be considered a bug.
> 
> I think at this point it would be better to look at a patch, with the
> changes mentioned after the first post, and a sweep through the other
> implementations.  There are some odd occurrences as you found; libc's
> frand() is also somewhat suspect but will likely need to change if
> lrand() does.  We need a 16bit, 32bit, floating point, and possibly
> 64bit variant; this will clean up some code and remove some
> redundancies which is always nice.  Perhaps take the extreme route and
> do *all* of the changes you'd like to see, so we could more easily
> discuss each case.  We then need to check if there's a performance
> impact on non-amd64 arches.  For xoroshiro128+ vs.  pcg I'd be
> interested to know if there's any significant difference between the
> two in statistical properties and performance; if we make a change,
> it'd be nice to pick the best alternative and make it once and for
> all.  Code size and simplicity also counts.  Is there any other
> variant that should be assessed?
> 
> 
> > > I agree, though again, I don't know what the impact of such
> > > a change would be.
> > 
> > Arguably, very negligible. Both use random tests, and quality is
> > somewhat important in these context. A little more than in, say,
> > fortune(1), but way less than in tls(3). However, venti's randtest
> > uses a hard-coded PRNG instead of libc's.
> > 
> > Cheers,
> > Elie Le Vaillant
> 
> In that case, I wouldn't touch venti either.  There are at least two
> projects for replacing venti with a new implementation; imo any such
> changes should be made there.
> 
> Cheers,
> qwx


-- 
Ori Bernstein <ori@eigenstate.org>