Messages in this thread Patch in this message |  | | Date | Tue, 31 Mar 2020 08:56:59 GMT | From | George Spelvin <> | Subject | [PATCH 2/3] random: Factor helper calc_entropy_frac() out of credit_entropy_bits() |
| |
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
|  |