Re: [PATCH] Make rcutorture RNG use temporal entropy

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

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