From patchwork Mon Sep 21 07:58:22 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nicolai Stange X-Patchwork-Id: 11788661 X-Patchwork-Delegate: herbert@gondor.apana.org.au Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7E1461731 for ; Mon, 21 Sep 2020 07:59:23 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 6D8402085B for ; Mon, 21 Sep 2020 07:59:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726507AbgIUH7W (ORCPT ); Mon, 21 Sep 2020 03:59:22 -0400 Received: from mx2.suse.de ([195.135.220.15]:56798 "EHLO mx2.suse.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726455AbgIUH7T (ORCPT ); Mon, 21 Sep 2020 03:59:19 -0400 X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 8BDECB502; Mon, 21 Sep 2020 07:59:52 +0000 (UTC) From: Nicolai Stange To: "Theodore Y. Ts'o" Cc: linux-crypto@vger.kernel.org, LKML , Arnd Bergmann , Greg Kroah-Hartman , "Eric W. Biederman" , "Alexander E. Patrakov" , "Ahmed S. Darwish" , Willy Tarreau , Matthew Garrett , Vito Caputo , Andreas Dilger , Jan Kara , Ray Strode , William Jon McCann , zhangjs , Andy Lutomirski , Florian Weimer , Lennart Poettering , Peter Matthias , Marcelo Henrique Cerri , Roman Drahtmueller , Neil Horman , Randy Dunlap , Julia Lawall , Dan Carpenter , Andy Lavr , Eric Biggers , "Jason A. Donenfeld" , =?utf-8?q?Stephan_M=C3=BCller?= , Torsten Duwe , Petr Tesarik , Nicolai Stange Subject: [RFC PATCH 06/41] random: factor the exponential approximation in credit_entropy_bits() out Date: Mon, 21 Sep 2020 09:58:22 +0200 Message-Id: <20200921075857.4424-7-nstange@suse.de> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20200921075857.4424-1-nstange@suse.de> References: <20200921075857.4424-1-nstange@suse.de> MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org 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 --- 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;