Re: [PATCH] Make rcutorture RNG use temporal entropy

Paul E. McKenney
2007-09-03T20:09:20Z

On Mon, Sep 03, 2007 at 08:29:04AM -0500, Matt Mackall wrote:
> On Mon, Aug 27, 2007 at 06:15:54PM -0700, Paul E. McKenney wrote:
> > On Thu, Aug 23, 2007 at 02:40:37PM -0500, Matt Mackall wrote:
> > > Yes. Using a hash function rather than a trivial LFSR is preferable.
> > > But pulling the guts out and giving it an n-bytes interface like
> > > get_random_bytes().
> >
> > OK. But this cannot be the first discussion of getting a fast and loose
> > version of get_random_bytes() into the kernel. Anyplace I should look
> > for cautionary tales? A quick search located a spirited discussion of
> > proposed kernel infrastructure for user-mode random number generation
> > back in 2003, but...
> >
> > Also a 2006 proposal from Stephan Eranian: http://lkml.org/lkml/2006/8/23/41
> > This appears to have gotten zero replies. :-/ (Though not hash-based.)
>
> You probably did the same searches I would do, so no, don't have any
> pointers, just vague recollections.

I was afraid of that. ;-)

> > Other semi-related threads:
> >
> > http://lkml.org/lkml/2005/3/15/102
> > http://lkml.org/lkml/2004/9/23/337
> >
> > Some years back, my reflexive design would have been per-CPU state,
> > accessed with interrupts disabled. Not so good for realtime usage,
> > though. One could go with per-task state in order to avoid the
> > interrupt disabling, which might be OK if the state is quite small.
>
> We only need be concerned here with locking insofar as we'd produce
> duplicate output without it. So it's fairly easy to imagine a lockless
> design using percpu data and perhaps folding in the preemption state.

And if we have a hash on the output, conflicting updates to the state
should be tolerable as well. Still want per-CPU state in order to
avoid cache thrashing, of course, but should be able to avoid preemption
disabling. So the trick will be getting a performance/size/entropy
tradeoff that 75% of the current roll-your-own random-number-generator
uses can live with.

Thanx, Paul