More eyes requested (Re: Kernel entropy pool / cprng race fix)

[Thor Lancelot Simon <tls%panix.com@localhost>]

On Fri, Apr 06, 2012 at 10:59:16AM -0400, Thor Lancelot Simon wrote:
> The attached patch should fix a race that exists when an entropy sink
> (such as a CPRNG instance that is being reseeded) is destroyed while
> it is currently being reseeded.
> 
> I've minimally tested it but since the problem is hard to reproduce
> I'd appreciate additional testers or additional eyes.
> 
> The diff is also at http://www.panix.com/~tls/seed-destroy.diff .

This is checked in, and has one bugfix courtesy of Matthias Drochner.

The attached patch is -- mostly -- an optimization for the odd case
where someone runs a program very frequently that opens /dev/urandom
and does a short read every time it's run (some versions of the perl
interpreter, invoked, let's say, on a busy CGI host, act like this).

It adds a per-CPU persistent cprng_strong that is used to service short
requests.  I don't use percpu(9) as I don't really care if occasionally
we switch away from the "home" CPU of a cprng before generating; there
is locking to make that safe.  This way avoids a lot of kpreempt_disable()s.

It also changes the rekeying strategy on pool full.  In the course of
testing that, I discovered a bug in the reseed / destroy race fix:
the reseed_pending variable on the cprng could get set but not cleared
if a reseed was skipped because the cprng's mutex was held.

The patch attached here tries to fix that, but now there is a LOCKDEBUG
problem: sometimes we seem to get to the uiomove() in rnd_read with
the reseed spin mutex held.  I don't see how this is possible but it
can be reproduced like this:

% sysctl -w ddb.onpanic=1
% dd if=/dev/urandom of=/dev/null bs=4 &
% dd if=/dev/sd0d of=/dev/null &

When the entropy pool fills and the per-cpu rng is rekeyed, the
LOCKDEBUG panic occurs.

I'd really appreciate help with this; I've just spent my whole
commute on it and I don't see how we get to that uiomove() with a
spin lock held!  The rekeying fix and short-read optimizations are
important, since they address real problems with real-world use cases,
so I really want to get this debugged and in the tree.

Diff is also at http://www.panix.com/~tls/rngpercpu.diff .

Thor

? 1
? rh
? rngpercpu.diff
? seed-destroy.diff
? arch/amd64/conf/RNDVERBOSE
? arch/arm/xscale/.iopaau.c.swp
? dev/.rndpseudo.c.swp
? kern/1
? kern/lastbatch.txt
? sys/.cprng.h.swp
? sys/.cpu.h.swp
Index: dev/rndpseudo.c
===================================================================
RCS file: /cvsroot/src/sys/dev/rndpseudo.c,v
retrieving revision 1.6
diff -r1.6 rndpseudo.c
56a57
> #include <sys/cpu.h>
98a100,104
>  * The per-CPU RNGs used for short requests
>  */
> cprng_strong_t **rp_cpurngs;
> 
> /*
195a202,204
> 
>       rp_cpurngs = kmem_zalloc(maxcpus * sizeof(cprng_strong_t *),
>                                KM_SLEEP);
254a264
>       cprng_strong_t *cprng;
256a267
>       struct cpu_info *ci = curcpu();
265,268c276,278
<       if (ctx->cprng == NULL) {
<               rnd_alloc_cprng(ctx);
<               if (__predict_false(ctx->cprng == NULL)) {
<                       return EIO;
---
>       if (ctx->hard || uio->uio_resid > NIST_BLOCK_KEYLEN_BYTES) {
>               if (ctx->cprng == NULL) {
>                       rnd_alloc_cprng(ctx);
269a280,299
>               cprng = ctx->cprng;
>       } else {
>               int index = cpu_index(ci);
> 
>               if (__predict_false(rp_cpurngs[index] == NULL)) {
>                       char rngname[32];
> 
>                       snprintf(rngname, sizeof(rngname),
>                                "%s-short", cpu_name(ci));
>                       rp_cpurngs[index] =
>                           cprng_strong_create(rngname, IPL_NONE,
>                                               CPRNG_INIT_ANY |
>                                               CPRNG_REKEY_ANY);
>               }
>               cprng = rp_cpurngs[index];
>       }
> 
>       if (__predict_false(cprng == NULL)) {
>               printf("NULL rng!\n");
>               return EIO;
272c302
<       strength = cprng_strong_strength(ctx->cprng);
---
>       strength = cprng_strong_strength(cprng);
288c318
<               nread = cprng_strong(ctx->cprng, bf, n,
---
>               nread = cprng_strong(cprng, bf, n,
306c336
<               cprng_strong_deplete(ctx->cprng);
---
>               cprng_strong_deplete(cprng);
308a339
> 
Index: kern/kern_rndpool.c
===================================================================
RCS file: /cvsroot/src/sys/kern/kern_rndpool.c,v
retrieving revision 1.1
diff -r1.1 kern_rndpool.c
55c55,56
< int rnd_full;
---
> int rnd_full = 0;                     /* Flag: is the pool full? */
> int rnd_filled = 0;                   /* Count: how many times filled? */
218a220
>               rnd_filled++;
249c251,253
<       rnd_full = 0;
---
>       if (rp->stats.curentropy < RND_POOLBITS / 2) {
>               rnd_full = 0;
>       }
Index: kern/subr_cprng.c
===================================================================
RCS file: /cvsroot/src/sys/kern/subr_cprng.c,v
retrieving revision 1.7
diff -r1.7 subr_cprng.c
78,79c78,79
<       if (!(c->reseed_pending) && mutex_tryenter(&c->reseed.mtx)) {
<               c->reseed_pending = 1;
---
>       if (mutex_tryenter(&c->reseed.mtx) && !c->reseed.pending) {
>               c->reseed.pending = 1;
92a93,94
>       KASSERT(mutex_owned(&c->reseed.mtx));
> 
105c107,108
<       c->reseed_pending = 0;
---
>       c->entropy_serial = rnd_filled;
>       c->reseed.pending = 0;
127c130
<       c->reseed_pending = 0;
---
>       c->reseed.pending = 0;
129a133
>       c->entropy_serial = rnd_filled;
256,260c260,261
<       }
< 
<       if (rnd_full) {
<               if (!c->rekeyed_on_full) {
<                       c->rekeyed_on_full++;
---
>       } else if (rnd_full) {
>               if (c->entropy_serial != rnd_filled) {
263,264d263
<       } else {
<               c->rekeyed_on_full = 0;
283c282
<       if (c->reseed_pending) {
---
>       if (c->reseed.pending) {
Index: sys/cprng.h
===================================================================
RCS file: /cvsroot/src/sys/sys/cprng.h,v
retrieving revision 1.4
diff -r1.4 cprng.h
88c88
<       int             rekeyed_on_full;
---
>       int             entropy_serial;
Index: sys/rnd.h
===================================================================
RCS file: /cvsroot/src/sys/sys/rnd.h,v
retrieving revision 1.30
diff -r1.30 rnd.h
132a133
>       int             pending;        /* currently in use */
180a182
> extern int    rnd_filled;