Message-Id: <20200921075857.4424-7-nstange@suse.de>
Date:   Mon, 21 Sep 2020 09:58:22 +0200
From:   Nicolai Stange <nstange@...e.de>
To:     "Theodore Y. Ts'o" <tytso@....edu>
Cc:     linux-crypto@...r.kernel.org, LKML <linux-kernel@...r.kernel.org>,
        Arnd Bergmann <arnd@...db.de>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        "Eric W. Biederman" <ebiederm@...ssion.com>,
        "Alexander E. Patrakov" <patrakov@...il.com>,
        "Ahmed S. Darwish" <darwish.07@...il.com>,
        Willy Tarreau <w@....eu>,
        Matthew Garrett <mjg59@...f.ucam.org>,
        Vito Caputo <vcaputo@...garu.com>,
        Andreas Dilger <adilger.kernel@...ger.ca>,
        Jan Kara <jack@...e.cz>, Ray Strode <rstrode@...hat.com>,
        William Jon McCann <mccann@....edu>,
        zhangjs <zachary@...shancloud.com>,
        Andy Lutomirski <luto@...nel.org>,
        Florian Weimer <fweimer@...hat.com>,
        Lennart Poettering <mzxreary@...inter.de>,
        Peter Matthias <matthias.peter@....bund.de>,
        Marcelo Henrique Cerri <marcelo.cerri@...onical.com>,
        Roman Drahtmueller <draht@...altsekun.de>,
        Neil Horman <nhorman@...hat.com>,
        Randy Dunlap <rdunlap@...radead.org>,
        Julia Lawall <julia.lawall@...ia.fr>,
        Dan Carpenter <dan.carpenter@...cle.com>,
        Andy Lavr <andy.lavr@...il.com>,
        Eric Biggers <ebiggers@...nel.org>,
        "Jason A. Donenfeld" <Jason@...c4.com>,
        Stephan Müller <smueller@...onox.de>,
        Torsten Duwe <duwe@...e.de>, Petr Tesarik <ptesarik@...e.cz>,
        Nicolai Stange <nstange@...e.de>
Subject: [RFC PATCH 06/41] random: factor the exponential approximation in credit_entropy_bits() out

In the course of calculating the actual amount of new entropy to credit,
credit_entropy_bits() applies a linear approximation to
exp(-nbits/pool_size)) (neglecting scaling factors in the exponent for
the sake of simplicity).

In order to limit approximation errors for large nbits, nbits is divided
into chunks of maximum value pool_size/2 each and said approximation is
applied to these individually in a loop. That loop has a theoretic upper
bound of 2*log2(pool_size), which, with the given pool_size of 128 * 32
bits, equals 24.

However, in practice nbits hardly ever exceeds values as a large as
pool_size/2 == 2048, especially not when called from interrupt context,
i.e. from add_interrupt_randomness() and alike. Thus, imposing a limit of
one single iteration in these contexts would yield a good guarantee with
respect to runtime while not losing any entropy.

In preparation to enabling that, move the approximation code in
credit_entropy_bits() into a separate function, pool_entropy_delta().
Based on the initial pool entropy count and the number of new entropy bits
to credit, it calculates and returns a (positive) delta to add to the
former. In case the 'fast' parameter is set to true, the calculation
will be terminated after the first iteration, effectively capping the input
nbits to one half of the pool size.

There is no functional change; callers with 'fast' set to true will be
introduced in a future patch.

Signed-off-by: Nicolai Stange <nstange@...e.de>
---
 drivers/char/random.c | 53 ++++++++++++++++++++++++++++++-------------
 1 file changed, 37 insertions(+), 16 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 6adac462aa0d..15dd22d74029 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -366,7 +366,7 @@
  * denominated in units of 1/8th bits.
  *
  * 2*(ENTROPY_SHIFT + poolbitshift) must <= 31, or the multiply in
- * credit_entropy_bits() needs to be 64 bits wide.
+ * pool_entropy_delta() needs to be 64 bits wide.
  */
 #define ENTROPY_SHIFT 3
 #define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
@@ -654,22 +654,24 @@ static void process_random_ready_list(void)
 }
 
 /*
- * Credit the entropy store with n bits of entropy.
- * Use credit_entropy_bits_safe() if the value comes from userspace
- * or otherwise should be checked for extreme values.
+ * Based on the pool's current entropy fill level, specified as
+ * base_entropy_count, and the number of new entropy bits to add,
+ * return the amount of new entropy to credit. If the 'fast'
+ * parameter is set to true, the calculation will be guaranteed to
+ * terminate quickly, but this comes at the expense of capping
+ * nbits to one half of the pool size.
  */
-static void credit_entropy_bits(struct entropy_store *r, int nbits)
+static unsigned int pool_entropy_delta(struct entropy_store *r,
+				       int base_entropy_count,
+				       int nbits, bool fast)
 {
-	int entropy_count, orig;
 	const int pool_size = r->poolinfo->poolfracbits;
+	int entropy_count = base_entropy_count;
 	int nfrac = nbits << ENTROPY_SHIFT;
-	int pnfrac;
 
 	if (!nbits)
-		return;
+		return 0;
 
-retry:
-	entropy_count = orig = READ_ONCE(r->entropy_count);
 	/*
 	 * Credit: we have to account for the possibility of
 	 * overwriting already present entropy.	 Even in the
@@ -691,24 +693,43 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 	 * arbitrarily long; this limits the loop to log2(pool_size)*2
 	 * turns no matter how large nbits is.
 	 */
-	pnfrac = nfrac;
 	do {
 		/* The +2 corresponds to the /4 in the denominator */
 		const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
-		unsigned int anfrac = min(pnfrac, pool_size/2);
+		unsigned int anfrac = min(nfrac, 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));
+		nfrac -= anfrac;
+	} while (unlikely(!fast && entropy_count < pool_size-2 && nfrac));
 
 	if (WARN_ON(entropy_count < 0)) {
 		pr_warn("negative entropy/overflow: pool %s count %d\n",
 			r->name, entropy_count);
-		entropy_count = orig;
-	} else if (entropy_count > pool_size)
+		entropy_count = base_entropy_count;
+	} else if (entropy_count > pool_size) {
 		entropy_count = pool_size;
+	}
+
+	return entropy_count - base_entropy_count;
+}
+
+/*
+ * Credit the entropy store with n bits of entropy.
+ * Use credit_entropy_bits_safe() if the value comes from userspace
+ * or otherwise should be checked for extreme values.
+ */
+static void credit_entropy_bits(struct entropy_store *r, int nbits)
+{
+	int entropy_count, orig;
+
+	if (!nbits)
+		return;
+
+retry:
+	orig = READ_ONCE(r->entropy_count);
+	entropy_count = orig + pool_entropy_delta(r, orig, nbits, false);
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 		goto retry;
 
-- 
2.26.2

Powered by blists - more mailing lists