From 9475e3f6f0216f22c5d04602e7194b8d86c73e51 Mon Sep 17 00:00:00 2001 From: John Denker Date: Wed, 9 Oct 2013 00:18:11 -0700 Subject: Clean up comments, figure out the logic; minor improvements in the logic. --- drivers/char/random.c | 108 +++++++++++++++++++++++++++++++++++--------------- 1 file changed, 76 insertions(+), 32 deletions(-) diff --git a/drivers/char/random.c b/drivers/char/random.c index a93ea7e..d1a0acd 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -235,6 +235,8 @@ * Eastlake, Steve Crocker, and Jeff Schiller. */ +// TODO: Scatter/gather, to reduce the number of files under /proc. + #include #include #include @@ -616,7 +618,11 @@ static void fast_mix(struct fast_pool *f, const void *in, int nbytes) } /* - * Credit (or debit) the entropy store with n bits of entropy + * Credit the entropy store with n bits of entropy. + * Normally n is positive. + * Sufficiently large n will wake up a blocked reader. + * Negative n values are allowed, but the resulting behavior + * might not be what you wanted. */ static void credit_entropy_bits(struct entropy_store *r, int nbits) { @@ -844,8 +850,8 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, * to an appropriate level, by pulling from the upstream * pool (r->pull), if any, if necessary. * - * We enforce (probably redundantly) the requirement that - * any pull be large enough to be "significant" to any attacker. + * We enforce the requirement that any contribution to the + * nonblocking PRNG be large enough to be "significant" to any attacker. * * In principle, this would cascade, pulling from other pools * even farther upstream, but as it stands there are only two @@ -855,22 +861,31 @@ static void fill_pool( struct entropy_store *r, size_t want_level /* measured in bytes */ ){ - __u32 tmp[OUTPUT_POOL_WORDS]; + __u32 tmp[OUTPUT_POOL_WORDS]; int rsvd = 0; /* measured in bits */ + int mybatch = 0; int actual; /* measured in BYTES */ int txbits = BYTE2BIT(want_level) - r->entropy_count; - if (txbits < 0) return; /* already have enough */ if (r->entropy_count >= r->poolinfo->POOLBITS) return; /* already full */ if (!r->pull) return; /* no upstream pool to pull from */ - if (!r->limit) { + if (r->limit) { + /* + * Use the values from the declarations, above. + */ + // FIXME: Think about increasing the request + // when entropy if pleniful. + } else { /* -* Here if we are non-limited i.e. non-blocking i.e. urandom. -* Reserve a suitable amount of entropy in the input pool, a -* sliding scale based on how desperately we need to be reseeded. -* -* The dilution factor ranges from 819 to 1 (at appetite=0) -* to 858,993,459 to 1 (at appetite=20) -*/ + * Here if we are non-limited i.e. non-blocking i.e. urandom i.e. PRNG. + * Reserve a suitable amount of entropy in the input pool, on a + * sliding scale based on how desperately we need to be reseeded. + * + * Ignore the caller's want_level. Entropy level doesn't mean much + * for a PRNG. The only thing the PRNG ever requests is RESEED_BATCH. + * + * The dilution factor ranges from 819 to 1 (at appetite=0) + * to 858,993,459 to 1 (at appetite=20) + */ int appetite = fls64(r->extracted_subttl) - 18; if (appetite < 0) return; /* 128k bits maps to appetite 0 */ /* The largest rsvd that makes any sense: */ @@ -878,42 +893,52 @@ static void fill_pool( /* When the appetite gets to 20, rsvd goes to zero: */ rsvd = rsvd - appetite*rsvd/20; if (rsvd < 0) rsvd = 0; +/* For the PRNG, make the request big enough to be "significant" to any attacker: */ + mybatch = RESEED_BATCH; } - /* Make the request big enough to be "significant" to any attacker: */ - txbits = max_t(int, txbits, RESEED_BATCH); + txbits = max_t(int, txbits, mybatch); /* but never more than our buffer size */ txbits = min_t(int, txbits, 8*sizeof(tmp)); - DEBUG_ENT("Going to reseed %s with %d bits; " + DEBUG_ENT("About to reseed %s adding %d bits; " "caller want_level: %zu prev level: %d\n", r->name, txbits, want_level * 8, r->entropy_count); + if (txbits < 0) return; /* already full enough */ actual = extract_entropy(r->pull, tmp, BIT2BYTE(txbits), - BIT2BYTE(RESEED_BATCH), BIT2BYTE(rsvd)); + BIT2BYTE(mybatch), BIT2BYTE(rsvd)); mix_pool_bytes(r, tmp, actual, NULL); credit_entropy_bits(r, actual*8); - if (BYTE2BIT(actual) > RESEED_BATCH) { +/* + * The subtotal starts over every time we transfer a + * sufficiently-large batch. Super-important for PRNG; + * probably not significant for TRNG. + */ + if (BYTE2BIT(actual) >= RESEED_BATCH) { r->extracted_subttl = 0; } -// FIXME: return actual; } /* - * These functions extracts randomness from the "entropy pool", and - * returns it in a buffer. + * General note, applying to several of the following routines: * * The /min/ parameter specifies the minimum amount we are allowed to pull; - * otherwise we pull nothing. This can be used to make sure the - * pull is "significant" to any attacker. + * otherwise we pull nothing. The PRNG uses this when reseeding, + * to make sure the pull is "significant" to any attacker. + * * The /reserved/ parameter indicates how much entropy we must leave * in the pool after each pull to avoid starving other readers. - * - * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words. */ -static size_t account(struct entropy_store *r, size_t nbytes, int min, + +/* + * Debit the entropy estimate for pool r. + * Usually done right before an extract_buf(). + * The return value is the amount to extract. + */ +static size_t debit(struct entropy_store *r, size_t nbytes, int min, int reserved) { unsigned long flags; @@ -923,10 +948,10 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min, spin_lock_irqsave(&r->lock, flags); BUG_ON(r->entropy_count > r->poolinfo->POOLBITS); - DEBUG_ENT("trying to extract %zu bits from %s\n", + DEBUG_ENT("trying to debit %zu bits from %s\n", nbytes * 8, r->name); - /* Can we pull enough? */ + /* If there's not enough available, don't extract anything. */ if (r->entropy_count / 8 < min + reserved) { nbytes = 0; } else { @@ -964,6 +989,10 @@ retry: return nbytes; } +/* + * Extract randomness from the specified pool (r) and return it in a buffer. + * Probably should always be preceded by debit(...). + */ static void extract_buf(struct entropy_store *r, __u8 *out) { int i; @@ -1025,7 +1054,11 @@ static void extract_buf(struct entropy_store *r, __u8 *out) memset(&hash, 0, sizeof(hash)); } -/* returns actual number of bytes extracted */ +/* + * Note: Here we assume that .poolwords is a multiple of 16 words. + * + * We return the actual number of bytes extracted. + */ static ssize_t extract_entropy(struct entropy_store *r, void *buf, size_t txbytes, int min, int reserved) { @@ -1050,13 +1083,16 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf, } trace_extract_entropy(r->name, txbytes, r->entropy_count, _RET_IP_); -/* We want our pool (r) to have enough, if possible. +/* + * We want our pool (r) to have enough entropy, if possible. * So pull it up to a level (txbits) that will cover the * extraction we are about to do. */ fill_pool(r, txbytes); - txbytes = account(r, txbytes, min, reserved); +/* This pool (r) has already been credited for the fill-in we just did. */ +/* Debit this pool for the extraction we are about to do. */ + txbytes = debit(r, txbytes, min, reserved); while (txbytes) { extract_buf(r, tmp); @@ -1095,7 +1131,9 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf, trace_extract_entropy_user(r->name, nbytes, r->entropy_count, _RET_IP_); fill_pool(r, nbytes); - nbytes = account(r, nbytes, 0, 0); + +/* Debit the estimate, according to the extraction we are about to do: */ + nbytes = debit(r, nbytes, 0, 0); while (nbytes) { if (need_resched()) { @@ -1237,6 +1275,12 @@ void rand_initialize_disk(struct gendisk *disk) } #endif +/* + * Interface used by the actual /dev/random. + * + * This is the only place where the process can block. + * It blocks if /dev/random wants to read more bits than are available. + */ static ssize_t random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos) { -- cgit v1.2.3