summaryrefslogtreecommitdiff
path: root/drivers
diff options
context:
space:
mode:
authorJohn Denker <jsd@av8n.com>2013-10-09 00:18:11 -0700
committerJohn Denker <jsd@av8n.com>2013-10-18 05:33:22 -0700
commit9475e3f6f0216f22c5d04602e7194b8d86c73e51 (patch)
tree03f3b4bc3eaa571695d955a364399d56ecdd392c /drivers
parentcc743a3f097f6f634501b6229a25faa6086bd8af (diff)
Clean up comments, figure out the logic;
minor improvements in the logic.
Diffstat (limited to 'drivers')
-rw-r--r--drivers/char/random.c108
1 files 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 <linux/utsname.h>
#include <linux/module.h>
#include <linux/kernel.h>
@@ -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)
{