Re: Revising prandom_32 generator

[Stephen Hemminger <stephen@networkplumber.org>]

On Tue, 26 Mar 2019 11:10:15 GMT
George Spelvin <lkml@sdf.org> wrote:

> I started on a project to correct all of the instances of
> "prandom_u32() % FOO" in the kernel (there are lots)
> to "prandom_u32_max(FOO)".
> 
> This has snowballed into an ongoing audit of random number use in the
> kernel, including uses of get_random_bytes() when get_random_u32 or
> prandom_u32() would suffice.
> 
> But one of the more potentially-controversial changes in the series,
> which might benefit from more discussion time, is a change of the
> actual prandom_u32() generator itself.
> 
> The current lfsr113 generator isn't bad, but like all LFSRs, it fails
> linear complexity tests in suites like testU01 and PractRand.
> 
> And there are generators with the same 128-bit state which produce
> better output in about half the time.  So I figured as long as I was
> neck-deep in the code, I might as well tweak that, too.
> 
> Thw ones that seem interesting to me are:
> - Chris Doty-Humphrey's sfc32.  This is a 96-bit chaotic generator
>   (meaning period *probably* long but not well defined) fed with
>   a 32-bit counter to ensure a minimum period.  It's extremely
>   fast, and the author is also the author of PractRand, so it's
>   well-tested.
> - Vigna and Bacman's xoshiro128**.  This is a 128-bit LFSR with some
>   output postprocessing.
> - (on 64-bit machines) xoroshiro128**, by the same authors.
>   This is only efficient on 64-bit machines, so it would need
>   a have a 32-bit backup.
> - Bob Jenkins' jsf (originally "flea").  128 bits, good mixing,
>   fully chaotic.  I prefer the safety of a guaranteed minimum
>   period, but this is well thought of.
> - A lag-3 mutiply-with-carry generator.  2^32 - 1736 is the largest
>   "safe prime" mutiplier.
> 
> I'm currently planning on using the first.  It also has the advantage
> for lockless reseeding that there are no bad states to avoid.
> 
> Some discussion of most of these at
> http://www.pcg-random.org/posts/some-prng-implementations.html
> 
> Here are some timing numbers.  Clock cycles per 1e7 iterations,
> sp 8-19 cycles per iteration.
> 
> Core 2:
>          lcg32: cycles 89018580
>          lcg64: cycles 130782048
>            mwc: cycles 90385992
>    prandom_u32: cycles 168780348
>   xoshiro128ss: cycles 90331056
> xoroshiro128ss: cycles 106012008
>          sfc32: cycles 90318276
>          jsf32: cycles 90364464
>         jsf32a: cycles 100382724
>         gjrand: cycles 131713680
> 
> Opteron:
>          lcg32: cycles 103434699
>          lcg64: cycles 80064205
>            mwc: cycles 110313786
>    prandom_u32: cycles 190311062
>   xoshiro128ss: cycles 110115475
> xoroshiro128ss: cycles 100114345
>          sfc32: cycles 100163397
>          jsf32: cycles 100104957
>         jsf32a: cycles 110133030
>         gjrand: cycles 110122007
> 
> (The LCGs are not 128-bit state; they're just there as a speed baseine.)
> 
> As you can see, the current lfsr113-based prandom_u32 takes almost
> twice the time of the aternatives.
> 
> My quick & dirty test code is appended for anyone who wants to play.
> 

A little backstory.  I started the prandom_32 stuff long ago when I wanted
a better (longer period) PRNG for use in netem. Took the existing code from
older version of GNU scientific library (pre GPLv3).  If there is something
faster with better properties go for it. But the whole point of prandom_32
is that it doesn't have to be crypto quality.