Re: Updated scalable urandom patchkit

["Theodore Ts'o" <tytso@mit.edu>]

On Sun, Oct 11, 2015 at 12:35:46AM -0400, George Spelvin wrote:
> 
> One is the final write back of add_ptr on the last line of
> _mix_pool_bytes.  It actually writes i, which includes the per-cpu nonce,
> and will have it jumping all over without the steady progression that
> the mixing polynomial assumes.

Yep, good catch; I need to subtract that off.

> (There's a similar, lesser problem with input_rotate.)

I didn't bother messing with input_rotate at all, and I don't think
that will be a problem.

> The second, less obvious, problem is that by calling _mix_pool_bytes
> completely lockless, there's the risk that it will race with and overwrite
> the addition of new seed material to the pool.
> 
> The add-back is not critical, and races between two writers don't really
> do any harm.  But seed entropy is valuable.

That's true, but I've been going back and forth about how much it's
worth to fix this.  After all, the the non-blocking pool is guaranteed
to have cryptographic randomness, and so it's a question of how much
effort we want to avoid the possibility of losing some seed entropy.

One approach might be to use take a reader lock when mixing back
entropy, but take an exclusive lock in the case when seeding the
non-random pool.

Another approach is to have an alternate mechanism for the
non-blocking pool which uses the LOCK prefix when XOR'ing into the
pool.  This would mean that we would have to drop the twisted LFSR and
replace it with something simpler but so long as the mixing algothm
eventually involves all of the bits in the pool, that will probably be
OK.

Of course, using the LOCK prefix is CPU architecture specific, and in
particular, there is no equivalent on the ARM architecture.

The final thing we could do is to just throw in a smp_mb() before the
write into the pool, and just call it day, and accept that while we
might lose a small amount of entropy due to a race, it will only a
byte's worth each time we lose a race (instead of the whole 32 byte
cache line).

None of the alternatives are all that satisfying, and they will all be
a bit more expensive than the first patch.  The question is how to
weigh these problems against just simply using a separate pool for
each NUMA node, and how much scalability are we really need for
"realistic" workloads?

						- Ted