[PATCH 1/3] random: Further dead code elimination

[PATCH 1/3] random: Further dead code elimination

[George Spelvin]

Earlier commits left some dead code behind in credit_entropy_bits().

In particular, has_initialized was always zero.

Fixes: 90ea1c6436d2 ("random: remove the blocking pool")
Signed-off-by: George Spelvin <lkml@sdf.org>
Cc: Andy Lutomirski <luto@kernel.org>
---
Just some odds & ends I noticed.

 drivers/char/random.c | 23 +++++------------------
 1 file changed, 5 insertions(+), 18 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index c7f9584de2c8..273dcbb4a790 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -660,7 +660,7 @@ static void process_random_ready_list(void)
  */
 static void credit_entropy_bits(struct entropy_store *r, int nbits)
 {
-	int entropy_count, orig, has_initialized = 0;
+	int entropy_count, orig;
 	const int pool_size = r->poolinfo->poolfracbits;
 	int nfrac = nbits << ENTROPY_SHIFT;
 
@@ -717,24 +717,11 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 		goto retry;
 
-	if (has_initialized) {
-		r->initialized = 1;
-		kill_fasync(&fasync, SIGIO, POLL_IN);
-	}
+	entropy_count >>= ENTROPY_SHIFT;	/* Convert to bits */
+	trace_credit_entropy_bits(r->name, nbits, entropy_count, _RET_IP_);
 
-	trace_credit_entropy_bits(r->name, nbits,
-				  entropy_count >> ENTROPY_SHIFT, _RET_IP_);
-
-	if (r == &input_pool) {
-		int entropy_bits = entropy_count >> ENTROPY_SHIFT;
-
-		if (crng_init < 2) {
-			if (entropy_bits < 128)
-				return;
-			crng_reseed(&primary_crng, r);
-			entropy_bits = ENTROPY_BITS(r);
-		}
-	}
+	if (r == &input_pool && crng_init < 2 && entropy_count >= 128)
+		crng_reseed(&primary_crng, r);
 }
 
 static int credit_entropy_bits_safe(struct entropy_store *r, int nbits)
-- 
2.26.0

[PATCH 2/3] random: Factor helper calc_entropy_frac() out of credit_entropy_bits()

[George Spelvin]

The helper is mathematically complex, with a large comment
explaining it.  credit_entropy_bits() has atomicity complexity.
Breaking them apart makes both easier to read and understand.

No functional change.

Signed-off-by: George Spelvin <lkml@sdf.org>
---
And it makes the approximation easier to change in the next patch.

 drivers/char/random.c | 114 +++++++++++++++++++++++-------------------
 1 file changed, 63 insertions(+), 51 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 273dcbb4a790..de90bab5af36 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -653,6 +653,64 @@ static void process_random_ready_list(void)
 	spin_unlock_irqrestore(&random_ready_list_lock, flags);
 }
 
+/*
+ * Add some new entropy to an existing pool with finite capacity.  We have
+ * to account for the possibility of overwriting already present entropy.
+ * Even in the ideal case of pure Shannon entropy, new contributions
+ * approach the pool capacity asymptotically:
+ *
+ * entropy += (capacity - entropy) * (1 - exp(-add/capacity))
+ *
+ * To avoid evaluating an exponential in interrupt context, we use a
+ * simple fixed-point underestimate.
+ *
+ * For add <= capacity/2 then
+ * (1 - exp(-add/capacity)) >= (add/capacity)*0.7869...
+ * so we can approximate the exponential with 3/4*add/capacity and still
+ * be on the safe side by adding at most capacity/2 at a time.
+ */
+static int calc_entropy_frac(int add, int entropy,
+			     struct entropy_store const *r)
+{
+	struct poolinfo const *info = r->poolinfo;
+	const int capacity = info->poolfracbits;
+
+	if (add < 0) {
+		/* Debit */
+		entropy += add;
+	} else {
+		const int s = info->poolbitshift + ENTROPY_SHIFT + 2;
+		/* The +2 corresponds to the denominator of the 3/4 */
+
+		do {
+			unsigned int frac = min(add, capacity/2);
+			unsigned int delta = ((capacity - entropy)*frac*3) >> s;
+
+			entropy += delta;
+			add -= frac;
+		} while (unlikely(add) && entropy < capacity-2);
+		/*
+		 * Because we're careful to always round down, the pool
+		 * will never be completely full.  In fact, the maximum
+		 * delta is 3/8 of the space remaining, which means that 3
+		 * fractional bits remaining will round to +1, but 2 will
+		 * round to +0, so there's no sense continuing.
+		 *
+		 * Stopping at capacity-2 also limits the loop to
+		 * log2(pool_size)/log2(5/8) = 1.475*log2(pool_size)
+		 * iterations no matter how large add is.
+		 */
+	}
+
+	if (WARN_ON(entropy < 0)) {
+		pr_warn("negative entropy/overflow: pool %s count %d\n",
+			r->name, entropy);
+		entropy = 0;
+	} else if (unlikely(entropy > capacity))
+		entropy = capacity;
+	return entropy;
+}
+
 /*
  * Credit (or debit) the entropy store with n bits of entropy.
  * Use credit_entropy_bits_safe() if the value comes from userspace
@@ -661,61 +719,15 @@ static void process_random_ready_list(void)
 static void credit_entropy_bits(struct entropy_store *r, int nbits)
 {
 	int entropy_count, orig;
-	const int pool_size = r->poolinfo->poolfracbits;
-	int nfrac = nbits << ENTROPY_SHIFT;
 
 	if (!nbits)
 		return;
 
-retry:
-	entropy_count = orig = READ_ONCE(r->entropy_count);
-	if (nfrac < 0) {
-		/* Debit */
-		entropy_count += nfrac;
-	} else {
-		/*
-		 * Credit: we have to account for the possibility of
-		 * overwriting already present entropy.	 Even in the
-		 * ideal case of pure Shannon entropy, new contributions
-		 * approach the full value asymptotically:
-		 *
-		 * entropy <- entropy + (pool_size - entropy) *
-		 *	(1 - exp(-add_entropy/pool_size))
-		 *
-		 * For add_entropy <= pool_size/2 then
-		 * (1 - exp(-add_entropy/pool_size)) >=
-		 *    (add_entropy/pool_size)*0.7869...
-		 * so we can approximate the exponential with
-		 * 3/4*add_entropy/pool_size and still be on the
-		 * safe side by adding at most pool_size/2 at a time.
-		 *
-		 * The use of pool_size-2 in the while statement is to
-		 * prevent rounding artifacts from making the loop
-		 * arbitrarily long; this limits the loop to log2(pool_size)*2
-		 * turns no matter how large nbits is.
-		 */
-		int pnfrac = nfrac;
-		const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
-		/* The +2 corresponds to the /4 in the denominator */
-
-		do {
-			unsigned int anfrac = min(pnfrac, pool_size/2);
-			unsigned int add =
-				((pool_size - entropy_count)*anfrac*3) >> s;
-
-			entropy_count += add;
-			pnfrac -= anfrac;
-		} while (unlikely(entropy_count < pool_size-2 && pnfrac));
-	}
-
-	if (WARN_ON(entropy_count < 0)) {
-		pr_warn("negative entropy/overflow: pool %s count %d\n",
-			r->name, entropy_count);
-		entropy_count = 0;
-	} else if (entropy_count > pool_size)
-		entropy_count = pool_size;
-	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
-		goto retry;
+	do {
+		orig = READ_ONCE(r->entropy_count);
+		entropy_count = calc_entropy_frac(nbits << ENTROPY_SHIFT,
+						  orig, r);
+	} while (cmpxchg(&r->entropy_count, orig, entropy_count) != orig);
 
 	entropy_count >>= ENTROPY_SHIFT;	/* Convert to bits */
 	trace_credit_entropy_bits(r->name, nbits, entropy_count, _RET_IP_);
-- 
2.26.0

[PATCH 3/3] random: use better approximation in calc_entropy_frac()

[George Spelvin]

Rather than a linear approximation to 1-exp(-x) which has 25% error for
small x (the common case), this uses a quadratic approximation which is
best for small x.

Both compute the same approximation 0.375 (-4.7% error) at x=0.5, the
high end of the input range.

If the processor supports it, a 32x32->64-bit multiply is used for greater
accuracy. If not, an intermediate normalizing shift is added to ensure
the product fits into 32 bits.

This also allows ENTROPY_SHIFT to be increased to 4, tracking entropy
in 1/16 bit increments.

Signed-off-by: George Spelvin <lkml@sdf.org>
---
There's a lot of estimated entropy wasted by inaccurate accounting whwn
we add it in small increments.  This improves that.

 drivers/char/random.c | 69 +++++++++++++++++++++++++++++++++----------
 1 file changed, 53 insertions(+), 16 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index de90bab5af36..b10962861c5e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -336,6 +336,7 @@
 #include <linux/syscalls.h>
 #include <linux/completion.h>
 #include <linux/uuid.h>
+#include <linux/math64.h>
 #include <crypto/chacha.h>
 
 #include <asm/processor.h>
@@ -363,13 +364,16 @@
 
 /*
  * To allow fractional bits to be tracked, the entropy_count field is
- * denominated in units of 1/8th bits.
+ * denominated in units of 1/16 bits.
  *
- * 2*(ENTROPY_SHIFT + poolbitshift) must <= 31, or the multiply in
- * credit_entropy_bits() needs to be 64 bits wide.
+ * 2*(ENTROPY_SHIFT + poolbitshift) must <= 32, or the code in
+ * entropy_frac_add() must be adjusted to use a larger first multiply.
  */
-#define ENTROPY_SHIFT 3
+#define ENTROPY_SHIFT 4
 #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
+#if INPUT_POOL_SHIFT + ENTROPY_SHIFT > 16
+#error Those parameters are not going to work.
+#endif
 
 /*
  * If the entropy count falls under this number of bits, then we
@@ -662,12 +666,34 @@ static void process_random_ready_list(void)
  * entropy += (capacity - entropy) * (1 - exp(-add/capacity))
  *
  * To avoid evaluating an exponential in interrupt context, we use a
- * simple fixed-point underestimate.
+ * simple fixed-point underestimate for 1 - exp(-x).  A second-order
+ * Taylor approximation works well:  x * (1 - x/2) <= 1 - exp(-x)
  *
- * For add <= capacity/2 then
- * (1 - exp(-add/capacity)) >= (add/capacity)*0.7869...
- * so we can approximate the exponential with 3/4*add/capacity and still
- * be on the safe side by adding at most capacity/2 at a time.
+ * This approximation is excellent for small x:
+ * x = 0.1 ->  0.17% low
+ * x = 0.2 ->  0.70% low
+ * x = 0.3 ->  1.61% low
+ * x = 0.4 ->  2.94% low
+ * x = 0.5 ->  4.69% low
+ * x = 1.0 -> 58.19% low
+ *
+ * It breaks (100% low) for x = 2.0, so in the rare case that add is
+ * large relative to capacity, we add the entropy a piece at a time.
+ * (We actually let the threshold equal half the pool size, but the
+ * exact value is not critical.)
+ *
+ * We are trying to compute
+ * (capacity - entropy) * (add/capacity) * (1 - add/capacity/2)
+ * using fixed-point, in fractional bits scaled by ENTROPY_SHIFT.
+ *
+ * For maximum accuracy, we'd do all the divisions last:
+ * (capacity - entropy) * add * (2*capacity - add) / (2*capacity^2)
+ * but at the maximum value of add = capacity/2, the intermediate
+ * product is almost capacity^3, which overflows 32 bits.
+ *
+ * If we are on a 64-bit processor OR have an arch-specific mul_u32_u32(),
+ * then use a 64-bit intermediate product.  Otherwise, use a normalizing
+ * shift (the smallest possible) between the two multiplies.
  */
 static int calc_entropy_frac(int add, int entropy,
 			     struct entropy_store const *r)
@@ -679,13 +705,24 @@ static int calc_entropy_frac(int add, int entropy,
 		/* Debit */
 		entropy += add;
 	} else {
-		const int s = info->poolbitshift + ENTROPY_SHIFT + 2;
-		/* The +2 corresponds to the denominator of the 3/4 */
+		const int s = info->poolbitshift + ENTROPY_SHIFT;
 
 		do {
 			unsigned int frac = min(add, capacity/2);
-			unsigned int delta = ((capacity - entropy)*frac*3) >> s;
+			u32 delta = frac * (2*capacity - frac);
 
+#if defined(mul_u32_u32) || BITS_PER_LONG == 64
+			/* Use a 64-bit product */
+			delta = mul_u32_u32(delta, capacity - entropy) >>
+				(2*s + 1);
+#else
+			/* Use only 32-bit products */
+			const int s1 = max(3*s - 32, 0);
+
+			delta >>= s1;
+			delta *= capacity - entropy;
+			delta >>= 2*s + 1 - s1;
+#endif
 			entropy += delta;
 			add -= frac;
 		} while (unlikely(add) && entropy < capacity-2);
@@ -702,12 +739,12 @@ static int calc_entropy_frac(int add, int entropy,
 		 */
 	}
 
-	if (WARN_ON(entropy < 0)) {
+	/* If out of range (should never happen), warn and clamp. */
+	if (WARN_ON(entropy < 0 || entropy > capacity)) {
 		pr_warn("negative entropy/overflow: pool %s count %d\n",
 			r->name, entropy);
-		entropy = 0;
-	} else if (unlikely(entropy > capacity))
-		entropy = capacity;
+		entropy = entropy < 0 ? 0 : capacity;
+	}
 	return entropy;
 }
 
-- 
2.26.0