From 9475e3f6f0216f22c5d04602e7194b8d86c73e51 Mon Sep 17 00:00:00 2001
From: John Denker <jsd@av8n.com>
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 <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)
 {
-- 
cgit v1.2.3