[PATCH 1/2] random: Statically compute poolbitshift, poolbytes, poolbits

[PATCH 1/2] random: Statically compute poolbitshift, poolbytes, poolbits

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@linux.intel.com>

Use a macro to statically compute poolbitshift (will be used in a
subsequent patch), poolbytes, and poolbits.  On virtually all
architectures the cost of a memory load with an offset is the same as
the one of a memory load.

It is still possible for this to generate worse code since the C
compiler doesn't know the fixed relationship between these fields, but
that is somewhat unlikely.

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: <stable@vger.kernel.org>
---
 drivers/char/random.c | 39 +++++++++++++++++++--------------------
 1 file changed, 19 insertions(+), 20 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 57d4b15..106b9b2 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -309,46 +309,45 @@ static DEFINE_PER_CPU(int, trickle_count);
  * scaled squared error sum) except for the last tap, which is 1 to
  * get the twisting happening as fast as possible.
  */
+
 static struct poolinfo {
-	int poolwords;
+	int poolbitshift, poolwords, poolbytes, poolbits;
+#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32
 	int tap1, tap2, tap3, tap4, tap5;
 } poolinfo_table[] = {
 	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
-	{ 128,	103,	76,	51,	25,	1 },
+	{ S(128),	103,	76,	51,	25,	1 },
 	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
-	{ 32,	26,	20,	14,	7,	1 },
+	{ S(32),	26,	20,	14,	7,	1 },
 #if 0
 	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
-	{ 2048,	1638,	1231,	819,	411,	1 },
+	{ S(2048),	1638,	1231,	819,	411,	1 },
 
 	/* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
-	{ 1024,	817,	615,	412,	204,	1 },
+	{ S(1024),	817,	615,	412,	204,	1 },
 
 	/* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
-	{ 1024,	819,	616,	410,	207,	2 },
+	{ S(1024),	819,	616,	410,	207,	2 },
 
 	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
-	{ 512,	411,	308,	208,	104,	1 },
+	{ S(512),	411,	308,	208,	104,	1 },
 
 	/* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
-	{ 512,	409,	307,	206,	102,	2 },
+	{ S(512),	409,	307,	206,	102,	2 },
 	/* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */
-	{ 512,	409,	309,	205,	103,	2 },
+	{ S(512),	409,	309,	205,	103,	2 },
 
 	/* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
-	{ 256,	205,	155,	101,	52,	1 },
+	{ S(256),	205,	155,	101,	52,	1 },
 
 	/* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
-	{ 128,	103,	78,	51,	27,	2 },
+	{ S(128),	103,	78,	51,	27,	2 },
 
 	/* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */
-	{ 64,	52,	39,	26,	14,	1 },
+	{ S(64),	52,	39,	26,	14,	1 },
 #endif
 };
 
-#define POOLBITS	poolwords*32
-#define POOLBYTES	poolwords*4
-
 /*
  * For the purposes of better mixing, we use the CRC-32 polynomial as
  * well to make a twisted Generalized Feedback Shift Reigster
@@ -599,8 +598,8 @@ retry:
 	if (entropy_count < 0) {
 		DEBUG_ENT("negative entropy/overflow\n");
 		entropy_count = 0;
-	} else if (entropy_count > r->poolinfo->POOLBITS)
-		entropy_count = r->poolinfo->POOLBITS;
+	} else if (entropy_count > r->poolinfo->poolbits)
+		entropy_count = r->poolinfo->poolbits;
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 		goto retry;
 
@@ -815,7 +814,7 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
 	__u32	tmp[OUTPUT_POOL_WORDS];
 
 	if (r->pull && r->entropy_count < nbytes * 8 &&
-	    r->entropy_count < r->poolinfo->POOLBITS) {
+	    r->entropy_count < r->poolinfo->poolbits) {
 		/* If we're limited, always leave two wakeup worth's BITS */
 		int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
 		int bytes = nbytes;
@@ -857,7 +856,7 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 	/* Hold lock while accounting */
 	spin_lock_irqsave(&r->lock, flags);
 
-	BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);
+	BUG_ON(r->entropy_count > r->poolinfo->poolbits);
 	DEBUG_ENT("trying to extract %zu bits from %s\n",
 		  nbytes * 8, r->name);
 
@@ -1104,7 +1103,7 @@ static void init_std_data(struct entropy_store *r)
 	r->entropy_total = 0;
 	r->last_data_init = false;
 	mix_pool_bytes(r, &now, sizeof(now), NULL);
-	for (i = r->poolinfo->POOLBYTES; i > 0; i -= sizeof(rv)) {
+	for (i = r->poolinfo->poolbytes; i > 0; i -= sizeof(rv)) {
 		if (!arch_get_random_long(&rv))
 			break;
 		mix_pool_bytes(r, &rv, sizeof(rv), NULL);
-- 
1.7.11.7

[PATCH 2/2] random: Account for entropy loss due to overwrites

[H. Peter Anvin]

From: "H. Peter Anvin" <hpa@linux.intel.com>

When we write entropy into a non-empty pool, we currently don't
account at all for the fact that we will probabilistically overwrite
some of the entropy in that pool.  This means that unless the pool is
fully empty, we are currently *guaranteed* to overestimate the amount
of entropy in the pool!

Assuming Shannon entropy with zero correlations we end up with an
exponentally decaying value of new entropy added:

	entropy <- entropy + (pool_size - entropy) *
		(1 - exp(-add_entropy/pool_size))

However, calculations involving fractional exponentials are not
practical in the kernel, so apply a piecewise linearization:

	  For add_entropy <= pool_size then

	  (1 - exp(-add_entropy/pool_size)) >= (add_entropy/pool_size)*0.632...

	  ... so we can approximate the exponential with
	  add_entropy/(pool_size*2) and still be on the
	  safe side by adding at most one pool_size at a time.

In order for the loop not to take arbitrary amounts of time if a bad
ioctl is received, terminate if we are within one bit of full.  This
way the loop is guaranteed to terminate after no more than
log2(poolsize) iterations, no matter what the input value is.  The
vast majority of the time the loop will be executed exactly once.

The piecewise linearization is very conservative, approaching 1/2 of
the usable input value for small inputs, however, our entropy
estimation is pretty weak at best, especially for small values; we
have no handle on correlation; and the Shannon entropy measure (Rényi
entropy of order 1) is not the correct one to use in the first place,
but rather the correct entropy measure is the min-entropy, the Rényi
entropy of infinite order.

As such, this conservatism seems more than justified.  Note, however,
that attempting to add one bit of entropy will never succeed; nor will
two bits unless the pool is completely empty.  These roundoff
artifacts could be improved by using fixed-point arithmetic and adding
some number of fractional entropy bits.

[ v2: rely on the previous patch for poolbitshift ]

Signed-off-by: H. Peter Anvin <hpa@linux.intel.com>
Cc: DJ Johnston <dj.johnston@intel.com>
Cc: <stable@vger.kernel.org>
---
 drivers/char/random.c | 56 +++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 48 insertions(+), 8 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 106b9b2..b0a502c 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -272,10 +272,12 @@
 /*
  * Configuration information
  */
-#define INPUT_POOL_WORDS 128
-#define OUTPUT_POOL_WORDS 32
-#define SEC_XFER_SIZE 512
-#define EXTRACT_SIZE 10
+#define INPUT_POOL_SHIFT	12
+#define INPUT_POOL_WORDS	(1 << (INPUT_POOL_SHIFT-5))
+#define OUTPUT_POOL_SHIFT	10
+#define OUTPUT_POOL_WORDS	(1 << (OUTPUT_POOL_SHIFT-5))
+#define SEC_XFER_SIZE		512
+#define EXTRACT_SIZE		10
 
 #define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
 
@@ -419,7 +421,7 @@ module_param(debug, bool, 0644);
 struct entropy_store;
 struct entropy_store {
 	/* read-only data: */
-	struct poolinfo *poolinfo;
+	const struct poolinfo *poolinfo;
 	__u32 *pool;
 	const char *name;
 	struct entropy_store *pull;
@@ -581,11 +583,13 @@ 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 (or debit) the entropy store with n bits of entropy.
+ * The nbits value is given in units of 2^-16 bits, i.e. 0x10000 == 1 bit.
  */
 static void credit_entropy_bits(struct entropy_store *r, int nbits)
 {
 	int entropy_count, orig;
+	const int pool_size = r->poolinfo->poolbits;
 
 	if (!nbits)
 		return;
@@ -594,12 +598,48 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 retry:
 	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
 	entropy_count += nbits;
+	if (nbits < 0) {
+		/* Debit. */
+		entropy_count += nbits;
+	} 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 then
+		 * (1 - exp(-add_entropy/pool_size)) >=
+		 *    (add_entropy/pool_size)*0.632...
+		 * so we can approximate the exponential with
+		 * add_entropy/(pool_size*2) and still be on the
+		 * safe side by adding at most one pool_size at a time.
+		 *
+		 * The use of pool_size-1 in the while statement is to
+		 * prevent rounding artifacts from making the loop
+		 * arbitrarily long; this limits the loop to poolshift
+		 * turns no matter how large nbits is.
+		 */
+		int pnbits  = nbits;
+		const int s = r->poolinfo->poolbitshift + 1;
+
+		do {
+			int anbits = min(pnbits, pool_size);
+
+			entropy_count +=
+				((pool_size - entropy_count)*anbits) >> s;
+			pnbits -= anbits;
+		} while (unlikely(entropy_count < pool_size-1 && pnbits));
+	}
 
 	if (entropy_count < 0) {
 		DEBUG_ENT("negative entropy/overflow\n");
 		entropy_count = 0;
-	} else if (entropy_count > r->poolinfo->poolbits)
-		entropy_count = r->poolinfo->poolbits;
+	} else if (entropy_count > pool_size)
+		entropy_count = pool_size;
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 		goto retry;
 
-- 
1.7.11.7

Re: [PATCH 2/2] random: Account for entropy loss due to overwrites

[Linus Torvalds]

This doesn't work AT ALL. You even hint at the reason why in your message.

On Tue, Apr 23, 2013 at 9:26 PM, H. Peter Anvin <hpa@zytor.com> wrote:
>
> As such, this conservatism seems more than justified.  Note, however,
> that attempting to add one bit of entropy will never succeed; nor will
> two bits unless the pool is completely empty.  These roundoff
> artifacts could be improved by using fixed-point arithmetic and adding
> some number of fractional entropy bits.

Take a look at "add_interrupt_randomness()". Hmm..

                Linus

Re: [PATCH 2/2] random: Account for entropy loss due to overwrites

[H. Peter Anvin]

On 04/25/2013 07:38 AM, Linus Torvalds wrote:
> This doesn't work AT ALL. You even hint at the reason why in your message.
> 
> On Tue, Apr 23, 2013 at 9:26 PM, H. Peter Anvin <hpa@zytor.com> wrote:
>>
>> As such, this conservatism seems more than justified.  Note, however,
>> that attempting to add one bit of entropy will never succeed; nor will
>> two bits unless the pool is completely empty.  These roundoff
>> artifacts could be improved by using fixed-point arithmetic and adding
>> some number of fractional entropy bits.
> 
> Take a look at "add_interrupt_randomness()". Hmm..
> 

<facepalm>

Right.  Before July of last year add_interrupt_randomness() called
add_timer_randomness() which credits up to 11 bits, but not anymore.

-ESTALEBRAIN.

OK, so we need to track fractional bits.

	-hpa

Re: [PATCH 2/2] random: Account for entropy loss due to overwrites

[H. Peter Anvin]

On 04/25/2013 07:44 AM, H. Peter Anvin wrote:
> 
> OK, so we need to track fractional bits.
> 

Ted, Linus: there are two ways we can do this: we can either change the
credit_entropy_bits() interface to take some kind of fractional bits as
interface, or we can change the accounting internally.

The latter has the advantage of being a less invasive change, but the
former has the advantage of making it possible to credit sub-bit entropy.

Do you have a preference?  Otherwise I will probably write up the
internal change for now.

	-hpa

Re: [PATCH 2/2] random: Account for entropy loss due to overwrites

[H. Peter Anvin]

On this subject, I assume this is a bug?

   871
   872                  if (r->entropy_count / 8 >= nbytes + reserved)
   873                          r->entropy_count -= nbytes*8;
   874                  else
   875                          r->entropy_count = reserved;
   876

[specifically the use of "reserved" as opposed to "reserved*8" on line 875?]

	-hpa