random: possible ways towards NIST SP800-90B compliance

index d20ba1b104ca..0580968fd28c 100644
@@ -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,11 +717,6 @@ 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);
-	}
-
 	trace_credit_entropy_bits(r->name, nbits,
 				  entropy_count >> ENTROPY_SHIFT, _RET_IP_);
 

index 0580968fd28c..c4b7bdbd460e 100644
@@ -654,7 +654,7 @@ static void process_random_ready_list(void)
 }
 
 /*
- * Credit (or debit) the entropy store with n bits of entropy.
+ * 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.
  */

@@ -663,50 +663,45 @@ 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;
+	int pnfrac;
 
 	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;
+	/*
+	 * 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.
+	 */
+	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 add =
+			((pool_size - entropy_count)*anfrac*3) >> s;
 
-		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));
-	}
+		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",

index c4b7bdbd460e..14c39608cc17 100644
@@ -716,13 +716,12 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 				  entropy_count >> ENTROPY_SHIFT, _RET_IP_);
 
 	if (r == &input_pool) {
-		int entropy_bits = entropy_count >> ENTROPY_SHIFT;
-
 		if (crng_init < 2) {
+			const int entropy_bits = entropy_count >> ENTROPY_SHIFT;
+
 			if (entropy_bits < 128)
 				return;
 			crng_reseed(&primary_crng, r);
-			entropy_bits = ENTROPY_BITS(r);
 		}
 	}
 }

index 14c39608cc17..35e381be20fe 100644
@@ -506,7 +506,7 @@ struct entropy_store {
 };
 
 static ssize_t extract_entropy(struct entropy_store *r, void *buf,
-			       size_t nbytes, int min, int rsvd);
+			       size_t nbytes, int min);
 static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
 				size_t nbytes, int fips);
 

@@ -944,7 +944,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	} buf;
 
 	if (r) {
-		num = extract_entropy(r, &buf, 32, 16, 0);
+		num = extract_entropy(r, &buf, 32, 16);
 		if (num == 0)
 			return;
 	} else {

@@ -1330,8 +1330,7 @@ EXPORT_SYMBOL_GPL(add_disk_randomness);
  * This function decides how many bytes to actually take from the
  * given pool, and also debits the entropy count accordingly.
  */
-static size_t account(struct entropy_store *r, size_t nbytes, int min,
-		      int reserved)
+static size_t account(struct entropy_store *r, size_t nbytes, int min)
 {
 	int entropy_count, orig, have_bytes;
 	size_t ibytes, nfrac;

@@ -1345,8 +1344,6 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 	/* never pull more than available */
 	have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
 
-	if ((have_bytes -= reserved) < 0)
-		have_bytes = 0;
 	ibytes = min_t(size_t, ibytes, have_bytes);
 	if (ibytes < min)
 		ibytes = 0;

@@ -1469,12 +1466,10 @@ static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
  * returns it in a buffer.
  *
  * The min parameter specifies the minimum amount we can pull before
- * failing to avoid races that defeat catastrophic reseeding while the
- * reserved parameter indicates how much entropy we must leave in the
- * pool after each pull to avoid starving other readers.
+ * failing to avoid races that defeat catastrophic reseeding.
  */
 static ssize_t extract_entropy(struct entropy_store *r, void *buf,
-				 size_t nbytes, int min, int reserved)
+				 size_t nbytes, int min)
 {
 	__u8 tmp[EXTRACT_SIZE];
 	unsigned long flags;

@@ -1495,7 +1490,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	}
 
 	trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
-	nbytes = account(r, nbytes, min, reserved);
+	nbytes = account(r, nbytes, min);
 
 	return _extract_entropy(r, buf, nbytes, fips_enabled);
 }

index 35e381be20fe..6adac462aa0d 100644
@@ -706,7 +706,7 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 	if (WARN_ON(entropy_count < 0)) {
 		pr_warn("negative entropy/overflow: pool %s count %d\n",
 			r->name, entropy_count);
-		entropy_count = 0;
+		entropy_count = orig;
 	} else if (entropy_count > pool_size)
 		entropy_count = pool_size;
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)

index 6adac462aa0d..15dd22d74029 100644
@@ -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;
 

index 15dd22d74029..08caa7a691a5 100644
@@ -655,21 +655,20 @@ static void process_random_ready_list(void)
 
 /*
  * 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.
+ * base_entropy_count, and the number of new entropy bits in units of
+ * 2^-ENTROPY_SHIFT 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 unsigned int pool_entropy_delta(struct entropy_store *r,
 				       int base_entropy_count,
-				       int nbits, bool fast)
+				       int nfrac, bool fast)
 {
 	const int pool_size = r->poolinfo->poolfracbits;
 	int entropy_count = base_entropy_count;
-	int nfrac = nbits << ENTROPY_SHIFT;
 
-	if (!nbits)
+	if (!nfrac)
 		return 0;
 
 	/*

@@ -729,7 +728,9 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 
 retry:
 	orig = READ_ONCE(r->entropy_count);
-	entropy_count = orig + pool_entropy_delta(r, orig, nbits, false);
+	entropy_count = orig + pool_entropy_delta(r, orig,
+						  nbits << ENTROPY_SHIFT,
+						  false);
 	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 		goto retry;
 

index 08caa7a691a5..d9e4dd27d45d 100644
@@ -714,6 +714,39 @@ static unsigned int pool_entropy_delta(struct entropy_store *r,
 	return entropy_count - base_entropy_count;
 }
 
+/*
+ * Credit the entropy store with n bits of entropy.
+ * To be used from hot paths when it is either known that nbits is
+ * smaller than one half of the pool size or losing anything beyond that
+ * doesn't matter.
+ */
+static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
+{
+	int entropy_count, orig;
+
+	if (!nbits)
+		return false;
+
+retry:
+	orig = READ_ONCE(r->entropy_count);
+	entropy_count = orig + pool_entropy_delta(r, orig,
+						  nbits << ENTROPY_SHIFT,
+						  true);
+	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
+		goto retry;
+
+	trace_credit_entropy_bits(r->name, nbits,
+				  entropy_count >> ENTROPY_SHIFT, _RET_IP_);
+
+	if (unlikely(r == &input_pool && crng_init < 2)) {
+		const int entropy_bits = entropy_count >> ENTROPY_SHIFT;
+
+		return (entropy_bits >= 128);
+	}
+
+	return false;
+}
+
 /*
  * Credit the entropy store with n bits of entropy.
  * Use credit_entropy_bits_safe() if the value comes from userspace

@@ -1169,6 +1202,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 		unsigned num;
 	} sample;
 	long delta, delta2, delta3;
+	bool reseed;
 
 	sample.jiffies = jiffies;
 	sample.cycles = random_get_entropy();

@@ -1206,7 +1240,9 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 	 * Round down by 1 bit on general principles,
 	 * and limit entropy estimate to 12 bits.
 	 */
-	credit_entropy_bits(r, min_t(int, fls(delta>>1), 11));
+	reseed = __credit_entropy_bits_fast(r, min_t(int, fls(delta>>1), 11));
+	if (reseed)
+		crng_reseed(&primary_crng, r);
 }
 
 void add_input_randomness(unsigned int type, unsigned int code,

@@ -1274,6 +1310,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	__u64			ip;
 	unsigned long		seed;
 	int			credit = 0;
+	bool			reseed;
 
 	if (cycles == 0)
 		cycles = get_reg(fast_pool, regs);

@@ -1326,7 +1363,9 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	fast_pool->count = 0;
 
 	/* award one bit for the contents of the fast pool */
-	credit_entropy_bits(r, credit + 1);
+	reseed = __credit_entropy_bits_fast(r, credit + 1);
+	if (reseed)
+		crng_reseed(&primary_crng, r);
 }
 EXPORT_SYMBOL_GPL(add_interrupt_randomness);
 

@@ -1599,7 +1638,11 @@ EXPORT_SYMBOL(get_random_bytes);
  */
 static void entropy_timer(struct timer_list *t)
 {
-	credit_entropy_bits(&input_pool, 1);
+	bool reseed;
+
+	reseed = __credit_entropy_bits_fast(&input_pool, 1);
+	if (reseed)
+		crng_reseed(&primary_crng, &input_pool);
 }
 
 /*

index d9e4dd27d45d..9f87332b158f 100644
@@ -718,7 +718,7 @@ static unsigned int pool_entropy_delta(struct entropy_store *r,
  * Credit the entropy store with n bits of entropy.
  * To be used from hot paths when it is either known that nbits is
  * smaller than one half of the pool size or losing anything beyond that
- * doesn't matter.
+ * doesn't matter. Must be called with r->lock being held.
  */
 static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
 {

@@ -727,13 +727,11 @@ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
 	if (!nbits)
 		return false;
 
-retry:
-	orig = READ_ONCE(r->entropy_count);
+	orig = r->entropy_count;
 	entropy_count = orig + pool_entropy_delta(r, orig,
 						  nbits << ENTROPY_SHIFT,
 						  true);
-	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
-		goto retry;
+	WRITE_ONCE(r->entropy_count, entropy_count);
 
 	trace_credit_entropy_bits(r->name, nbits,
 				  entropy_count >> ENTROPY_SHIFT, _RET_IP_);

@@ -755,17 +753,28 @@ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
 static void credit_entropy_bits(struct entropy_store *r, int nbits)
 {
 	int entropy_count, orig;
+	unsigned long flags;
 
 	if (!nbits)
 		return;
 
 retry:
+	/*
+	 * Don't run the potentially expensive pool_entropy_delta()
+	 * calculations under the spinlock. Instead retry until
+	 * ->entropy_count becomes stable.
+	 */
 	orig = READ_ONCE(r->entropy_count);
 	entropy_count = orig + pool_entropy_delta(r, orig,
 						  nbits << ENTROPY_SHIFT,
 						  false);
-	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
+	spin_lock_irqsave(&r->lock, flags);
+	if (r->entropy_count != orig) {
+		spin_unlock_irqrestore(&r->lock, flags);
 		goto retry;
+	}
+	WRITE_ONCE(r->entropy_count, entropy_count);
+	spin_unlock_irqrestore(&r->lock, flags);
 
 	trace_credit_entropy_bits(r->name, nbits,
 				  entropy_count >> ENTROPY_SHIFT, _RET_IP_);

@@ -1203,12 +1212,11 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 	} sample;
 	long delta, delta2, delta3;
 	bool reseed;
+	unsigned long flags;
 
 	sample.jiffies = jiffies;
 	sample.cycles = random_get_entropy();
 	sample.num = num;
-	r = &input_pool;
-	mix_pool_bytes(r, &sample, sizeof(sample));
 
 	/*
 	 * Calculate number of bits of randomness we probably added.

@@ -1235,12 +1243,16 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 	if (delta > delta3)
 		delta = delta3;
 
+	r = &input_pool;
+	spin_lock_irqsave(&r->lock, flags);
+	__mix_pool_bytes(r, &sample, sizeof(sample));
 	/*
 	 * delta is now minimum absolute delta.
 	 * Round down by 1 bit on general principles,
 	 * and limit entropy estimate to 12 bits.
 	 */
 	reseed = __credit_entropy_bits_fast(r, min_t(int, fls(delta>>1), 11));
+	spin_unlock_irqrestore(&r->lock, flags);
 	if (reseed)
 		crng_reseed(&primary_crng, r);
 }

@@ -1358,12 +1370,12 @@ void add_interrupt_randomness(int irq, int irq_flags)
 		__mix_pool_bytes(r, &seed, sizeof(seed));
 		credit = 1;
 	}
-	spin_unlock(&r->lock);
 
 	fast_pool->count = 0;
 
 	/* award one bit for the contents of the fast pool */
 	reseed = __credit_entropy_bits_fast(r, credit + 1);
+	spin_unlock(&r->lock);
 	if (reseed)
 		crng_reseed(&primary_crng, r);
 }

@@ -1393,14 +1405,15 @@ EXPORT_SYMBOL_GPL(add_disk_randomness);
  */
 static size_t account(struct entropy_store *r, size_t nbytes, int min)
 {
-	int entropy_count, orig, have_bytes;
+	int entropy_count, have_bytes;
 	size_t ibytes, nfrac;
+	unsigned long flags;
 
 	BUG_ON(r->entropy_count > r->poolinfo->poolfracbits);
 
+	spin_lock_irqsave(&r->lock, flags);
 	/* Can we pull enough? */
-retry:
-	entropy_count = orig = READ_ONCE(r->entropy_count);
+	entropy_count = r->entropy_count;
 	ibytes = nbytes;
 	/* never pull more than available */
 	have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);

@@ -1420,8 +1433,8 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min)
 	else
 		entropy_count = 0;
 
-	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
-		goto retry;
+	WRITE_ONCE(r->entropy_count, entropy_count);
+	spin_unlock_irqrestore(&r->lock, flags);
 
 	trace_debit_entropy(r->name, 8 * ibytes);
 	if (ibytes && ENTROPY_BITS(r) < random_write_wakeup_bits) {

@@ -1639,8 +1652,11 @@ EXPORT_SYMBOL(get_random_bytes);
 static void entropy_timer(struct timer_list *t)
 {
 	bool reseed;
+	unsigned long flags;
 
+	spin_lock_irqsave(&input_pool.lock, flags);
 	reseed = __credit_entropy_bits_fast(&input_pool, 1);
+	spin_unlock_irqrestore(&input_pool.lock, flags);
 	if (reseed)
 		crng_reseed(&primary_crng, &input_pool);
 }

index 9f87332b158f..b91d1fc08ac5 100644
@@ -499,7 +499,13 @@ struct entropy_store {
 	spinlock_t lock;
 	unsigned short add_ptr;
 	unsigned short input_rotate;
+
 	int entropy_count;
+	unsigned int entropy_watermark_delta;
+	unsigned int entropy_watermark_seq;
+	unsigned int queued_entropy_batches;
+	unsigned int pending_extractions;
+	unsigned long entropy_watermark_leak_time;
 	unsigned int initialized:1;
 	unsigned int last_data_init:1;
 	__u8 last_data[EXTRACT_SIZE];

@@ -671,6 +677,9 @@ static unsigned int pool_entropy_delta(struct entropy_store *r,
 	if (!nfrac)
 		return 0;
 
+	if (pool_size <= base_entropy_count)
+		return 0;
+
 	/*
 	 * Credit: we have to account for the possibility of
 	 * overwriting already present entropy.	 Even in the

@@ -714,26 +723,172 @@ static unsigned int pool_entropy_delta(struct entropy_store *r,
 	return entropy_count - base_entropy_count;
 }
 
+struct queued_entropy {
+	unsigned int pool_watermark_seq;
+	unsigned int queued_entropy_fracbits;
+};
+
 /*
- * Credit the entropy store with n bits of entropy.
- * To be used from hot paths when it is either known that nbits is
- * smaller than one half of the pool size or losing anything beyond that
- * doesn't matter. Must be called with r->lock being held.
+ * Queue a given amount of new entropy which is about to mixed into
+ * the entropy pool for later dispatch.
+ *
+ * __queue_entropy() may be called one or more time on the same struct
+ * queued_entropy instance in order to accumulate entropy for later
+ * dispatch. However, any such sequence of invocations must eventually
+ * be followed by exactly one call to either of __dequeue_entropy(),
+ * __dispatch_queued_entropy_fast() or dispatch_queued_entropy()
+ * when the actual pool mixing has completed.
+ * __queue_entropy() must be called with r->lock held.
+ *
+ * Entropy extraction is a two-step process:
+ * 1.) The allocated amount of entropy gets subtracted from ->entropy_count.
+ * 2.) The entropy is actually extracted from the pool by means of one or more
+ *     extract_buf() invocations.
+ * Likewise for the mixing side:
+ * 1.) The new entropy data gets mixed into the pool via __mix_pool_bytes() and
+ * 2.) the pool's ->entropy_count incremented by a certain amount afterwards.
+ * However, that amount of new entropy credited in the last step depends
+ * on the current pool fill level: the higher the current ->entropy_count,
+ * the less the amount of new entropy credited, c.f. pool_entropy_delta().
+ *
+ * This must be accounted for in a scenario involving concurrent producers
+ * and consumers like the following:
+ *   Producer                                     Consumer
+ *   --------                                     --------
+ *                                                ->entropy_count -= n
+ *   __mix_pool_bytes()
+ *   ->entropy_count += pool_entropy_delta()
+ *                                                extract_buf()
+ * Note how the pool_entropy_delta() would observe a too small pool
+ * fill level and thus, credits too much entropy to the new batch.
+ *
+ * The solution to work around this is to maintain a watermark, which
+ * is guaranteed to be >= than the pool's ->entropy_count value
+ * at any point in time from before __mix_pool_bytes() to after it.
+ *
+ * A call to __queue_entropy() enables watermark tracking from the
+ * producers side, the final __dequeue_entropy() disables it and
+ * returns the watermark. See also account_begin() and
+ * account_complete().
+ *
+ * Note there's no problem wuth multiple concurrent producers, because
+ *   e1 = e0 + pool_entropy_delta(e0, n1);
+ *   e2 = e1 + pool_entropy_delta(e1, n2);
+ * is equivalent (modulo approximation artifacts) to
+ *   e2 = e0 + pool_entropy_delta(e0, n1 + n2);
  */
-static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
+static void __queue_entropy(struct entropy_store *r, struct queued_entropy *q,
+			    unsigned int nfrac)
+{
+	if (!nfrac)
+		return;
+
+	if (!q->queued_entropy_fracbits) {
+		/*
+		 * First call with non-zero nbits, enable watermark
+		 * tracking.
+		 */
+		q->pool_watermark_seq = r->entropy_watermark_seq;
+		r->queued_entropy_batches++;
+	} else if (q->pool_watermark_seq != r->entropy_watermark_seq) {
+		/*
+		 * Previously queued entropy is doomed because
+		 * the ->pool_watermark_delta had been reset.
+		 * Don't add any more entropy on top of that.
+		 */
+		q->pool_watermark_seq = r->entropy_watermark_seq;
+		q->queued_entropy_fracbits = 0;
+	}
+
+	q->queued_entropy_fracbits += nfrac;
+}
+
+static void queue_entropy(struct entropy_store *r, struct queued_entropy *q,
+			  unsigned int nfrac)
 {
-	int entropy_count, orig;
+	unsigned long flags;
 
-	if (!nbits)
+	spin_lock_irqsave(&r->lock, flags);
+	__queue_entropy(r, q, nfrac);
+	spin_unlock_irqrestore(&r->lock, flags);
+}
+
+/*
+ * Dequeue previously queued entropy and return the pool entropy
+ * watermark to be used in pool_entropy_delta().
+ *
+ * Must only be called after a sequence of one or more matching
+ * __queue_entropy() invocations. Must be called with r->lock
+ * held.
+ *
+ * __dequeue_entropy() returns the number of queued bits and resets
+ * q. *pool_watermark receives the pool entropy watermark as tracked
+ * from the beginning of the first preceding __queue_entropy() call
+ * up to the __dequeue_entropy() invocation.
+ *
+ * The number of returned fractional bits is intended to get
+ * subsequently passed together with the larger of *pool_watermark and
+ * r->entropy_count to pool_entropy_delta().
+ * If r->lock is not dropped inbetween *pool_watermark and the load
+ * of r->entropy_count, the former is guaranteed to equal the maximum.
+ */
+static unsigned int __dequeue_entropy(struct entropy_store *r,
+				      struct queued_entropy *q,
+				      int *pool_watermark)
+{
+	unsigned int nfrac;
+
+	nfrac = q->queued_entropy_fracbits;
+	if (!nfrac)
+		return 0;
+
+	/* Disable watermark tracking. */
+	q->queued_entropy_fracbits = 0;
+	r->queued_entropy_batches--;
+
+	/*
+	 * The watermark has been invalidated in the meanwhile and
+	 * the queued entropy is lost.
+	 */
+	if (q->pool_watermark_seq != r->entropy_watermark_seq)
+		return 0;
+
+	*pool_watermark = r->entropy_count + r->entropy_watermark_delta;
+	if (*pool_watermark < 0)
+		return 0;
+
+	return nfrac;
+}
+
+/*
+ * Credit the pool with previously queued entropy.
+ *
+ * Must only be called after a sequence of one or more matching
+ * __queue_entropy() invocations. Must be called with r->lock
+ * held.
+ *
+ * To be used from hot paths when it is either known that the amount
+ * of queued entropy is smaller than one half of the pool size or
+ * losing anything beyond that doesn't matter.
+ *
+ * Returns true if the caller is supposed to seed the primary_crng.
+ */
+static bool __dispatch_queued_entropy_fast(struct entropy_store *r,
+					   struct queued_entropy *q)
+{
+	unsigned int nfrac;
+	int entropy_count, orig, pool_watermark;
+
+	nfrac = __dequeue_entropy(r, q, &pool_watermark);
+	if (!nfrac)
 		return false;
 
 	orig = r->entropy_count;
-	entropy_count = orig + pool_entropy_delta(r, orig,
-						  nbits << ENTROPY_SHIFT,
+	entropy_count = orig + pool_entropy_delta(r, pool_watermark, nfrac,
 						  true);
 	WRITE_ONCE(r->entropy_count, entropy_count);
 
-	trace_credit_entropy_bits(r->name, nbits,
+	trace_credit_entropy_bits(r->name, nfrac >> ENTROPY_SHIFT,
 				  entropy_count >> ENTROPY_SHIFT, _RET_IP_);
 
 	if (unlikely(r == &input_pool && crng_init < 2)) {

@@ -747,15 +902,35 @@ static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
 
 /*
  * 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.
+ * To be used from hot paths when it is either known that nbits is
+ * smaller than one half of the pool size or losing anything beyond that
+ * doesn't matter. Must be called with r->lock being held.
  */
-static void credit_entropy_bits(struct entropy_store *r, int nbits)
+static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
+{
+	struct queued_entropy q = { 0 };
+
+	__queue_entropy(r, &q, nbits << ENTROPY_SHIFT);
+	return __dispatch_queued_entropy_fast(r, &q);
+}
+
+/*
+ * Credit the pool with previously queued entropy.
+ *
+ * Must only be called after a sequence of one or more matching
+ * __queue_entropy() invocations.
+ */
+static void dispatch_queued_entropy(struct entropy_store *r,
+				    struct queued_entropy *q)
 {
-	int entropy_count, orig;
+	unsigned int nfrac;
+	int entropy_count, orig, pool_watermark, base;
 	unsigned long flags;
 
-	if (!nbits)
+	spin_lock_irqsave(&r->lock, flags);
+	nfrac = __dequeue_entropy(r, q, &pool_watermark);
+	spin_unlock_irqrestore(&r->lock, flags);
+	if (!nfrac)
 		return;
 
 retry:

@@ -765,9 +940,8 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 	 * ->entropy_count becomes stable.
 	 */
 	orig = READ_ONCE(r->entropy_count);
-	entropy_count = orig + pool_entropy_delta(r, orig,
-						  nbits << ENTROPY_SHIFT,
-						  false);
+	base = max_t(int, pool_watermark, orig);
+	entropy_count = orig + pool_entropy_delta(r, base, nfrac, false);
 	spin_lock_irqsave(&r->lock, flags);
 	if (r->entropy_count != orig) {
 		spin_unlock_irqrestore(&r->lock, flags);

@@ -776,7 +950,7 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 	WRITE_ONCE(r->entropy_count, entropy_count);
 	spin_unlock_irqrestore(&r->lock, flags);
 
-	trace_credit_entropy_bits(r->name, nbits,
+	trace_credit_entropy_bits(r->name, nfrac >> ENTROPY_SHIFT,
 				  entropy_count >> ENTROPY_SHIFT, _RET_IP_);
 
 	if (r == &input_pool) {

@@ -790,6 +964,19 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
 	}
 }
 
+/*
+ * 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)
+{
+	struct queued_entropy q = { 0 };
+
+	queue_entropy(r, &q, nbits << ENTROPY_SHIFT);
+	dispatch_queued_entropy(r, &q);
+}
+
 static int credit_entropy_bits_safe(struct entropy_store *r, int nbits)
 {
 	const int nbits_max = r->poolinfo->poolwords * 32;

@@ -1402,8 +1589,12 @@ EXPORT_SYMBOL_GPL(add_disk_randomness);
 /*
  * This function decides how many bytes to actually take from the
  * given pool, and also debits the entropy count accordingly.
+ *
+ * Increases the pool entropy watermark (c.f. __queue_entropy() and
+ * __dequeue_entropy()) and must be followed with a matching
+ * account_complete() in order to decrease it again, if possible.
  */
-static size_t account(struct entropy_store *r, size_t nbytes, int min)
+static size_t account_begin(struct entropy_store *r, size_t nbytes, int min)
 {
 	int entropy_count, have_bytes;
 	size_t ibytes, nfrac;

@@ -1419,6 +1610,7 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min)
 	have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
 
 	ibytes = min_t(size_t, ibytes, have_bytes);
+
 	if (ibytes < min)
 		ibytes = 0;
 

@@ -1434,6 +1626,18 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min)
 		entropy_count = 0;
 
 	WRITE_ONCE(r->entropy_count, entropy_count);
+
+	if (!r->entropy_watermark_delta) {
+		/*
+		 * This is not exact. In fact it is not known yet if
+		 * the watermark entropy added below will be actually
+		 * be leaked in account_complete(). But there can be
+		 * concurrent consumers and someone has to set this.
+		 */
+		r->entropy_watermark_leak_time = jiffies;
+	}
+	r->entropy_watermark_delta += nfrac;
+	r->pending_extractions++;
 	spin_unlock_irqrestore(&r->lock, flags);
 
 	trace_debit_entropy(r->name, 8 * ibytes);

@@ -1445,6 +1649,69 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min)
 	return ibytes;
 }
 
+/*
+ * Undo the pool watermark increment from a preceding
+ * account_begin(), if possible.
+ */
+static void account_complete(struct entropy_store *r, size_t ibytes)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&r->lock, flags);
+	r->pending_extractions--;
+	if (!r->queued_entropy_batches) {
+		/*
+		 * There's currently no entropy queued at the producer
+		 * side and at the very least it is safe to undo the
+		 * watermark increment from the matching
+		 * account_begin().
+		 */
+		if (!r->pending_extractions) {
+			/*
+			 * No other extractions pending. It is even
+			 * safe to dismiss all watermark increments
+			 * which had to be leaked from previous,
+			 * unrelated account_complete() invocations
+			 * because there had been some entropy queued
+			 * at their time.
+			 */
+			r->entropy_watermark_delta = 0;
+		} else {
+			unsigned int nfrac;
+
+			nfrac = ibytes << (ENTROPY_SHIFT + 3);
+			r->entropy_watermark_delta -= nfrac;
+		}
+	} else if (!r->pending_extractions) {
+		/*
+		 * There is currently some entropy queued at the
+		 * producer side and there's no choice but to leave
+		 * the pool watermark untouched and thus, to "leak"
+		 * the increment from the matching account_begin().
+		 *
+		 * However, if it gets too wild, the watermark is
+		 * reset and all currently queued entropy invalidated.
+		 * We don't want to keep leaked watermark increments
+		 * forever and also keep them bounded by 1/8 of the
+		 * pool size in total in order to limit its damping
+		 * effect on new entropy in pool_entropy_delta().
+		 */
+		int leak_limit;
+		unsigned long leak_cleanup_time;
+
+		leak_limit = r->poolinfo->poolfracbits >> 3;
+		leak_cleanup_time = (r->entropy_watermark_leak_time +
+				     2 * CRNG_RESEED_INTERVAL);
+		if (r->entropy_watermark_delta > leak_limit ||
+		    time_after(jiffies, leak_cleanup_time)) {
+			r->entropy_watermark_delta = 0;
+			/* Invalidate all queued entropy. */
+			r->entropy_watermark_seq++;
+		}
+	}
+	spin_unlock_irqrestore(&r->lock, flags);
+}
+
 /*
  * This function does the actual extraction for extract_entropy and
  * extract_entropy_user.

@@ -1547,6 +1814,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 {
 	__u8 tmp[EXTRACT_SIZE];
 	unsigned long flags;
+	ssize_t ret;
 
 	/* if last_data isn't primed, we need EXTRACT_SIZE extra bytes */
 	if (fips_enabled) {

@@ -1564,9 +1832,10 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	}
 
 	trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
-	nbytes = account(r, nbytes, min);
-
-	return _extract_entropy(r, buf, nbytes, fips_enabled);
+	nbytes = account_begin(r, nbytes, min);
+	ret = _extract_entropy(r, buf, nbytes, fips_enabled);
+	account_complete(r, nbytes);
+	return ret;
 }
 
 #define warn_unseeded_randomness(previous) \

index b91d1fc08ac5..e8c86abde901 100644
@@ -1400,6 +1400,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 	long delta, delta2, delta3;
 	bool reseed;
 	unsigned long flags;
+	struct queued_entropy q = { 0 };
 
 	sample.jiffies = jiffies;
 	sample.cycles = random_get_entropy();

@@ -1432,13 +1433,14 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 
 	r = &input_pool;
 	spin_lock_irqsave(&r->lock, flags);
-	__mix_pool_bytes(r, &sample, sizeof(sample));
 	/*
 	 * delta is now minimum absolute delta.
 	 * Round down by 1 bit on general principles,
 	 * and limit entropy estimate to 12 bits.
 	 */
-	reseed = __credit_entropy_bits_fast(r, min_t(int, fls(delta>>1), 11));
+	__queue_entropy(r, &q, min_t(int, fls(delta>>1), 11) << ENTROPY_SHIFT);
+	__mix_pool_bytes(r, &sample, sizeof(sample));
+	reseed = __dispatch_queued_entropy_fast(r, &q);
 	spin_unlock_irqrestore(&r->lock, flags);
 	if (reseed)
 		crng_reseed(&primary_crng, r);

index e8c86abde901..bd3774c6be4b 100644
@@ -1512,6 +1512,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	unsigned long		seed;
 	int			credit = 0;
 	bool			reseed;
+	struct queued_entropy	q = { 0 };
 
 	if (cycles == 0)
 		cycles = get_reg(fast_pool, regs);

@@ -1546,24 +1547,27 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	if (!spin_trylock(&r->lock))
 		return;
 
-	fast_pool->last = now;
-	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
-
 	/*
 	 * If we have architectural seed generator, produce a seed and
-	 * add it to the pool.  For the sake of paranoia don't let the
-	 * architectural seed generator dominate the input from the
-	 * interrupt noise.
+	 * add it to the pool further below. For the sake of paranoia
+	 * don't let the architectural seed generator dominate the
+	 * input from the interrupt noise.
 	 */
-	if (arch_get_random_seed_long(&seed)) {
-		__mix_pool_bytes(r, &seed, sizeof(seed));
-		credit = 1;
-	}
+	credit = !!arch_get_random_long(&seed);
 
+	fast_pool->last = now;
 	fast_pool->count = 0;
-
 	/* award one bit for the contents of the fast pool */
-	reseed = __credit_entropy_bits_fast(r, credit + 1);
+	__queue_entropy(r, &q, (credit + 1) << ENTROPY_SHIFT);
+	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
+	if (credit) {
+		/*
+		 * A seed has been obtained from
+		 * arch_get_random_seed_long() above, mix it in.
+		 */
+		__mix_pool_bytes(r, &seed, sizeof(seed));
+	}
+	reseed = __dispatch_queued_entropy_fast(r, &q);
 	spin_unlock(&r->lock);
 	if (reseed)
 		crng_reseed(&primary_crng, r);

index bd3774c6be4b..dfbe49fdbcf1 100644
@@ -1911,6 +1911,12 @@ void get_random_bytes(void *buf, int nbytes)
 EXPORT_SYMBOL(get_random_bytes);
 
 
+struct try_to_generate_entropy_stack {
+	unsigned long now;
+	struct timer_list timer;
+	struct queued_entropy q;
+} stack;
+
 /*
  * Each time the timer fires, we expect that we got an unpredictable
  * jump in the cycle counter. Even if the timer is running on another

@@ -1926,14 +1932,10 @@ EXPORT_SYMBOL(get_random_bytes);
  */
 static void entropy_timer(struct timer_list *t)
 {
-	bool reseed;
-	unsigned long flags;
+	struct try_to_generate_entropy_stack *stack;
 
-	spin_lock_irqsave(&input_pool.lock, flags);
-	reseed = __credit_entropy_bits_fast(&input_pool, 1);
-	spin_unlock_irqrestore(&input_pool.lock, flags);
-	if (reseed)
-		crng_reseed(&primary_crng, &input_pool);
+	stack = container_of(t, struct try_to_generate_entropy_stack, timer);
+	queue_entropy(&input_pool, &stack->q, 1 << ENTROPY_SHIFT);
 }
 
 /*

@@ -1942,10 +1944,9 @@ static void entropy_timer(struct timer_list *t)
  */
 static void try_to_generate_entropy(void)
 {
-	struct {
-		unsigned long now;
-		struct timer_list timer;
-	} stack;
+	struct try_to_generate_entropy_stack stack = { 0 };
+	unsigned long flags;
+	bool reseed;
 
 	stack.now = random_get_entropy();
 

@@ -1957,14 +1958,29 @@ static void try_to_generate_entropy(void)
 	while (!crng_ready()) {
 		if (!timer_pending(&stack.timer))
 			mod_timer(&stack.timer, jiffies+1);
-		mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
+		spin_lock_irqsave(&input_pool.lock, flags);
+		__mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
+		reseed = __dispatch_queued_entropy_fast(&input_pool, &stack.q);
+		spin_unlock_irqrestore(&input_pool.lock, flags);
+
+		if (reseed)
+			crng_reseed(&primary_crng, &input_pool);
+
 		schedule();
 		stack.now = random_get_entropy();
 	}
 
 	del_timer_sync(&stack.timer);
 	destroy_timer_on_stack(&stack.timer);
-	mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
+	spin_lock_irqsave(&input_pool.lock, flags);
+	__mix_pool_bytes(&input_pool, &stack.now, sizeof(stack.now));
+	/*
+	 * Must be called here once more in order to complete a
+	 * previously unmatched queue_entropy() from entropy_timer(),
+	 * if any.
+	 */
+	__dispatch_queued_entropy_fast(&input_pool, &stack.q);
+	spin_unlock_irqrestore(&input_pool.lock, flags);
 }
 
 /*

index dfbe49fdbcf1..60ce185d7b2d 100644
@@ -900,20 +900,6 @@ static bool __dispatch_queued_entropy_fast(struct entropy_store *r,
 	return false;
 }
 
-/*
- * Credit the entropy store with n bits of entropy.
- * To be used from hot paths when it is either known that nbits is
- * smaller than one half of the pool size or losing anything beyond that
- * doesn't matter. Must be called with r->lock being held.
- */
-static bool __credit_entropy_bits_fast(struct entropy_store *r, int nbits)
-{
-	struct queued_entropy q = { 0 };
-
-	__queue_entropy(r, &q, nbits << ENTROPY_SHIFT);
-	return __dispatch_queued_entropy_fast(r, &q);
-}
-
 /*
  * Credit the pool with previously queued entropy.
  *

index 60ce185d7b2d..78e65367ea86 100644
@@ -2640,6 +2640,7 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 				size_t entropy)
 {
 	struct entropy_store *poolp = &input_pool;
+	struct queued_entropy q = { 0 };
 
 	if (unlikely(crng_init == 0)) {
 		crng_fast_load(buffer, count);

@@ -2652,8 +2653,9 @@ void add_hwgenerator_randomness(const char *buffer, size_t count,
 	 */
 	wait_event_interruptible(random_write_wait, kthread_should_stop() ||
 			ENTROPY_BITS(&input_pool) <= random_write_wakeup_bits);
+	queue_entropy(poolp, &q, entropy << ENTROPY_SHIFT);
 	mix_pool_bytes(poolp, buffer, count);
-	credit_entropy_bits(poolp, entropy);
+	dispatch_queued_entropy(poolp, &q);
 }
 EXPORT_SYMBOL_GPL(add_hwgenerator_randomness);
 

index 78e65367ea86..03eadefabbca 100644
@@ -737,7 +737,9 @@ struct queued_entropy {
  * dispatch. However, any such sequence of invocations must eventually
  * be followed by exactly one call to either of __dequeue_entropy(),
  * __dispatch_queued_entropy_fast() or dispatch_queued_entropy()
- * when the actual pool mixing has completed.
+ * when the actual pool mixing has completed. Alternatively,
+ * discard_queued_entropy() may be called in case the mixing has
+ * failed.
  * __queue_entropy() must be called with r->lock held.
  *
  * Entropy extraction is a two-step process:

@@ -813,6 +815,26 @@ static void queue_entropy(struct entropy_store *r, struct queued_entropy *q,
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
+/*
+ * Queue entropy which comes from userspace and might take extreme
+ * values.
+ */
+static int queue_entropy_bits_safe(struct entropy_store *r,
+				   struct queued_entropy *q,
+				   int nbits)
+{
+	const int nbits_max = r->poolinfo->poolwords * 32;
+
+	if (nbits < 0)
+		return -EINVAL;
+
+	/* Cap the value to avoid overflows */
+	nbits = min(nbits,  nbits_max);
+
+	queue_entropy(r, q, nbits << ENTROPY_SHIFT);
+	return 0;
+}
+
 /*
  * Dequeue previously queued entropy and return the pool entropy
  * watermark to be used in pool_entropy_delta().

@@ -950,6 +972,22 @@ static void dispatch_queued_entropy(struct entropy_store *r,
 	}
 }
 
+/*
+ * Discard queued entropy. May be called when e.g. a write_pool()
+ * operation failed and the corresponding previously queued entropy
+ * should not get dispatched to the pool.
+ */
+static void discard_queued_entropy(struct entropy_store *r,
+				   struct queued_entropy *q)
+{
+	unsigned long flags;
+	int pool_watermark;
+
+	spin_lock_irqsave(&r->lock, flags);
+	__dequeue_entropy(r, q, &pool_watermark);
+	spin_unlock_irqrestore(&r->lock, flags);
+}
+
 /*
  * Credit the entropy store with n bits of entropy.
  * Use credit_entropy_bits_safe() if the value comes from userspace

@@ -2272,6 +2310,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 	int size, ent_count;
 	int __user *p = (int __user *)arg;
 	int retval;
+	struct queued_entropy q = { 0 };
 
 	switch (cmd) {
 	case RNDGETENTCNT:

@@ -2285,7 +2324,11 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 			return -EPERM;
 		if (get_user(ent_count, p))
 			return -EFAULT;
-		return credit_entropy_bits_safe(&input_pool, ent_count);
+		retval = queue_entropy_bits_safe(&input_pool, &q, ent_count);
+		if (retval < 0)
+			return retval;
+		dispatch_queued_entropy(&input_pool, &q);
+		return 0;
 	case RNDADDENTROPY:
 		if (!capable(CAP_SYS_ADMIN))
 			return -EPERM;

@@ -2295,11 +2338,17 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
 			return -EINVAL;
 		if (get_user(size, p++))
 			return -EFAULT;
+		retval = queue_entropy_bits_safe(&input_pool, &q, ent_count);
+		if (retval < 0)
+			return retval;
 		retval = write_pool(&input_pool, (const char __user *)p,
 				    size);
-		if (retval < 0)
+		if (retval < 0) {
+			discard_queued_entropy(&input_pool, &q);
 			return retval;
-		return credit_entropy_bits_safe(&input_pool, ent_count);
+		}
+		discard_queued_entropy(&input_pool, &q);
+		return 0;
 	case RNDZAPENTCNT:
 	case RNDCLEARPOOL:
 		/*

index 03eadefabbca..a49805d0d23c 100644
@@ -533,7 +533,7 @@ static __u32 const twist_table[8] = {
 /*
  * This function adds bytes into the entropy "pool".  It does not
  * update the entropy estimate.  The caller should call
- * credit_entropy_bits if this is appropriate.
+ * queue_entropy()+dispatch_queued_entropy() if this is appropriate.
  *
  * The pool is stirred with a primitive polynomial of the appropriate
  * degree, and then twisted.  We twist by three bits at a time because

@@ -988,33 +988,6 @@ static void discard_queued_entropy(struct entropy_store *r,
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
-/*
- * 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)
-{
-	struct queued_entropy q = { 0 };
-
-	queue_entropy(r, &q, nbits << ENTROPY_SHIFT);
-	dispatch_queued_entropy(r, &q);
-}
-
-static int credit_entropy_bits_safe(struct entropy_store *r, int nbits)
-{
-	const int nbits_max = r->poolinfo->poolwords * 32;
-
-	if (nbits < 0)
-		return -EINVAL;
-
-	/* Cap the value to avoid overflows */
-	nbits = min(nbits,  nbits_max);
-
-	credit_entropy_bits(r, nbits);
-	return 0;
-}
-
 /*********************************************************************
  *
  * CRNG using CHACHA20

index a49805d0d23c..1945249597e0 100644
@@ -1200,14 +1200,18 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 		_crng_backtrack_protect(&primary_crng, buf.block,
 					CHACHA_KEY_SIZE);
 	}
-	spin_lock_irqsave(&crng->lock, flags);
+
 	for (i = 0; i < 8; i++) {
 		unsigned long	rv;
 		if (!arch_get_random_seed_long(&rv) &&
 		    !arch_get_random_long(&rv))
 			rv = random_get_entropy();
-		crng->state[i+4] ^= buf.key[i] ^ rv;
+		buf.key[i] ^= rv;
 	}
+
+	spin_lock_irqsave(&crng->lock, flags);
+	for (i = 0; i < 8; i++)
+		crng->state[i+4] ^= buf.key[i];
 	memzero_explicit(&buf, sizeof(buf));
 	crng->init_time = jiffies;
 	spin_unlock_irqrestore(&crng->lock, flags);

index 44209f6146aa..055d18713db7 100644
@@ -26,17 +26,13 @@ static inline bool __arm64_rndr(unsigned long *v)
 	return ok;
 }
 
-static inline bool __must_check arch_get_random_long(unsigned long *v)
-{
-	return false;
-}
 
-static inline bool __must_check arch_get_random_int(unsigned int *v)
+static inline bool arch_has_random(void)
 {
 	return false;
 }
 
-static inline bool __must_check arch_get_random_seed_long(unsigned long *v)
+static inline bool arch_has_random_seed(void)
 {
 	/*
 	 * Only support the generic interface after we have detected

@@ -44,7 +40,22 @@ static inline bool __must_check arch_get_random_seed_long(unsigned long *v)
 	 * cpufeature code and with potential scheduling between CPUs
 	 * with and without the feature.
 	 */
-	if (!cpus_have_const_cap(ARM64_HAS_RNG))
+	return cpus_have_const_cap(ARM64_HAS_RNG);
+}
+
+static inline bool __must_check arch_get_random_long(unsigned long *v)
+{
+	return false;
+}
+
+static inline bool __must_check arch_get_random_int(unsigned int *v)
+{
+	return false;
+}
+
+static inline bool __must_check arch_get_random_seed_long(unsigned long *v)
+{
+	if (!arch_has_random_seed())
 		return false;
 
 	return __arm64_rndr(v);

index 9a53e29680f4..47c2d74e7244 100644
@@ -6,6 +6,16 @@
 
 #include <asm/machdep.h>
 
+static inline bool arch_has_random(void)
+{
+	return false;
+}
+
+static inline bool arch_has_random_seed(void)
+{
+	return ppc_md.get_random_seed;
+}
+
 static inline bool __must_check arch_get_random_long(unsigned long *v)
 {
 	return false;

@@ -18,7 +28,7 @@ static inline bool __must_check arch_get_random_int(unsigned int *v)
 
 static inline bool __must_check arch_get_random_seed_long(unsigned long *v)
 {
-	if (ppc_md.get_random_seed)
+	if (arch_has_random_seed())
 		return ppc_md.get_random_seed(v);
 
 	return false;

index de61ce562052..18973845634c 100644
@@ -21,6 +21,16 @@ extern atomic64_t s390_arch_random_counter;
 
 bool s390_arch_random_generate(u8 *buf, unsigned int nbytes);
 
+static inline bool arch_has_random(void)
+{
+	return false;
+}
+
+static inline bool arch_has_random_seed(void)
+{
+	return static_branch_likely(&s390_arch_random_available);
+}
+
 static inline bool __must_check arch_get_random_long(unsigned long *v)
 {
 	return false;

@@ -33,7 +43,7 @@ static inline bool __must_check arch_get_random_int(unsigned int *v)
 
 static inline bool __must_check arch_get_random_seed_long(unsigned long *v)
 {
-	if (static_branch_likely(&s390_arch_random_available)) {
+	if (arch_has_random_seed()) {
 		return s390_arch_random_generate((u8 *)v, sizeof(*v));
 	}
 	return false;

@@ -41,7 +51,7 @@ static inline bool __must_check arch_get_random_seed_long(unsigned long *v)
 
 static inline bool __must_check arch_get_random_seed_int(unsigned int *v)
 {
-	if (static_branch_likely(&s390_arch_random_available)) {
+	if (arch_has_random_seed()) {
 		return s390_arch_random_generate((u8 *)v, sizeof(*v));
 	}
 	return false;

index ebc248e49549..030f46c9e310 100644
@@ -70,24 +70,34 @@ static inline bool __must_check rdseed_int(unsigned int *v)
  */
 #ifdef CONFIG_ARCH_RANDOM
 
+static inline bool arch_has_random(void)
+{
+	return static_cpu_has(X86_FEATURE_RDRAND);
+}
+
+static inline bool arch_has_random_seed(void)
+{
+	return static_cpu_has(X86_FEATURE_RDSEED);
+}
+
 static inline bool __must_check arch_get_random_long(unsigned long *v)
 {
-	return static_cpu_has(X86_FEATURE_RDRAND) ? rdrand_long(v) : false;
+	return arch_has_random() ? rdrand_long(v) : false;
 }
 
 static inline bool __must_check arch_get_random_int(unsigned int *v)
 {
-	return static_cpu_has(X86_FEATURE_RDRAND) ? rdrand_int(v) : false;
+	return arch_has_random() ? rdrand_int(v) : false;
 }
 
 static inline bool __must_check arch_get_random_seed_long(unsigned long *v)
 {
-	return static_cpu_has(X86_FEATURE_RDSEED) ? rdseed_long(v) : false;
+	return arch_has_random_seed() ? rdseed_long(v) : false;
 }
 
 static inline bool __must_check arch_get_random_seed_int(unsigned int *v)
 {
-	return static_cpu_has(X86_FEATURE_RDSEED) ? rdseed_int(v) : false;
+	return arch_has_random_seed() ? rdseed_int(v) : false;
 }
 
 extern void x86_init_rdrand(struct cpuinfo_x86 *c);

index f45b8be3e3c4..d4653422a0c7 100644
@@ -120,6 +120,14 @@ unsigned long randomize_page(unsigned long start, unsigned long range);
 #ifdef CONFIG_ARCH_RANDOM
 # include <asm/archrandom.h>
 #else
+static inline bool arch_has_random(void)
+{
+	return false;
+}
+static inline bool arch_has_random_seed(void)
+{
+	return false;
+}
 static inline bool __must_check arch_get_random_long(unsigned long *v)
 {
 	return false;

index 1945249597e0..424de1565927 100644
@@ -516,6 +516,8 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
 				size_t nbytes, int fips);
 
+static int min_crng_reseed_pool_entropy(void);
+
 static void crng_reseed(struct crng_state *crng, struct entropy_store *r);
 static __u32 input_pool_data[INPUT_POOL_WORDS] __latent_entropy;
 

@@ -916,7 +918,7 @@ static bool __dispatch_queued_entropy_fast(struct entropy_store *r,
 	if (unlikely(r == &input_pool && crng_init < 2)) {
 		const int entropy_bits = entropy_count >> ENTROPY_SHIFT;
 
-		return (entropy_bits >= 128);
+		return (entropy_bits >= min_crng_reseed_pool_entropy() * 8);
 	}
 
 	return false;

@@ -965,7 +967,7 @@ static void dispatch_queued_entropy(struct entropy_store *r,
 		if (crng_init < 2) {
 			const int entropy_bits = entropy_count >> ENTROPY_SHIFT;
 
-			if (entropy_bits < 128)
+			if (entropy_bits < min_crng_reseed_pool_entropy() * 8)
 				return;
 			crng_reseed(&primary_crng, r);
 		}

@@ -1182,6 +1184,15 @@ static int crng_slow_load(const char *cp, size_t len)
 	return 1;
 }
 
+/*
+ * Minimum amount of entropy in bytes required from the input_pool for
+ * a successful reseed of the primary_crng.
+ */
+static int min_crng_reseed_pool_entropy(void)
+{
+	return 16;
+}
+
 static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 {
 	unsigned long	flags;

@@ -1192,7 +1203,8 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	} buf;
 
 	if (r) {
-		num = extract_entropy(r, &buf, 32, 16);
+		num = extract_entropy(r, &buf, 32,
+				      min_crng_reseed_pool_entropy());
 		if (num == 0)
 			return;
 	} else {

index 424de1565927..7712b4464ef5 100644
@@ -1190,6 +1190,14 @@ static int crng_slow_load(const char *cp, size_t len)
  */
 static int min_crng_reseed_pool_entropy(void)
 {
+	/*
+	 * If there's an architecture provided RNG, use it for
+	 * up to one half of the minimum entropy needed for
+	 * reseeding. That way it won't dominate the entropy
+	 * collected by other means at input_pool.
+	 */
+	if (arch_has_random() || arch_has_random_seed())
+		return 8;
 	return 16;
 }
 

@@ -1197,6 +1205,7 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 {
 	unsigned long	flags;
 	int		i, num;
+	bool		arch_randomness_required = false;
 	union {
 		__u8	block[CHACHA_BLOCK_SIZE];
 		__u32	key[8];

@@ -1205,8 +1214,16 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	if (r) {
 		num = extract_entropy(r, &buf, 32,
 				      min_crng_reseed_pool_entropy());
-		if (num == 0)
+		if (num == 0) {
 			return;
+		} else if (num < 16) {
+			/*
+			 * The input_pool did not provide sufficient
+			 * entropy for reseeding and the architecture
+			 * provided RNG will have to make up for it.
+			 */
+			arch_randomness_required = true;
+		}
 	} else {
 		_extract_crng(&primary_crng, buf.block);
 		_crng_backtrack_protect(&primary_crng, buf.block,

@@ -1216,8 +1233,17 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	for (i = 0; i < 8; i++) {
 		unsigned long	rv;
 		if (!arch_get_random_seed_long(&rv) &&
-		    !arch_get_random_long(&rv))
+		    !arch_get_random_long(&rv)) {
+			if (arch_randomness_required) {
+				/*
+				 * The input_pool failed to provide
+				 * sufficient entropy and the arch RNG
+				 * could not make up for that either.
+				 */
+				return;
+			}
 			rv = random_get_entropy();
+		}
 		buf.key[i] ^= rv;
 	}
 

@@ -1522,8 +1548,6 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	cycles_t		cycles = random_get_entropy();
 	__u32			c_high, j_high;
 	__u64			ip;
-	unsigned long		seed;
-	int			credit = 0;
 	bool			reseed;
 	struct queued_entropy	q = { 0 };
 

@@ -1560,26 +1584,11 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	if (!spin_trylock(&r->lock))
 		return;
 
-	/*
-	 * If we have architectural seed generator, produce a seed and
-	 * add it to the pool further below. For the sake of paranoia
-	 * don't let the architectural seed generator dominate the
-	 * input from the interrupt noise.
-	 */
-	credit = !!arch_get_random_long(&seed);
-
 	fast_pool->last = now;
 	fast_pool->count = 0;
 	/* award one bit for the contents of the fast pool */
-	__queue_entropy(r, &q, (credit + 1) << ENTROPY_SHIFT);
+	__queue_entropy(r, &q, 1 << ENTROPY_SHIFT);
 	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
-	if (credit) {
-		/*
-		 * A seed has been obtained from
-		 * arch_get_random_seed_long() above, mix it in.
-		 */
-		__mix_pool_bytes(r, &seed, sizeof(seed));
-	}
 	reseed = __dispatch_queued_entropy_fast(r, &q);
 	spin_unlock(&r->lock);
 	if (reseed)

index 055d18713db7..db7813c79b3e 100644
@@ -42,7 +42,15 @@ static inline bool arch_has_random_seed(void)
 	 */
 	return cpus_have_const_cap(ARM64_HAS_RNG);
 }
-
+static inine bool arch_has_sp800_90b_random_seed(void)
+{
+	/*
+	 * Section K.12.1 from the Arm Architecture Reference Manual
+	 * Armv8" (DDI0487F) sounds like RNDRRS could qualify as a
+	 * NIST SP800-90C NRBG, but we're currently using RNDR only.
+	 */
+	return false;
+}
 static inline bool __must_check arch_get_random_long(unsigned long *v)
 {
 	return false;

index 47c2d74e7244..ba0f816d9750 100644
@@ -16,6 +16,11 @@ static inline bool arch_has_random_seed(void)
 	return ppc_md.get_random_seed;
 }
 
+static inline bool arch_has_sp800_90b_random_seed(void)
+{
+	return false;
+}
+
 static inline bool __must_check arch_get_random_long(unsigned long *v)
 {
 	return false;

index 18973845634c..1ee7f9e4b255 100644
@@ -31,6 +31,11 @@ static inline bool arch_has_random_seed(void)
 	return static_branch_likely(&s390_arch_random_available);
 }
 
+static inline bool arch_has_sp800_90b_random_seed(void)
+{
+	return false;
+}
+
 static inline bool __must_check arch_get_random_long(unsigned long *v)
 {
 	return false;

index 030f46c9e310..94d4ee8c9e45 100644
@@ -80,6 +80,14 @@ static inline bool arch_has_random_seed(void)
 	return static_cpu_has(X86_FEATURE_RDSEED);
 }
 
+static inline bool arch_has_sp800_90b_random_seed(void)
+{
+	/*
+	 * According to the Intel SDM, rdseed is NIST SP800-90B
+	 * compliant.
+	 */
+	return arch_has_random_seed();
+}
 static inline bool __must_check arch_get_random_long(unsigned long *v)
 {
 	return arch_has_random() ? rdrand_long(v) : false;

index d4653422a0c7..933f5daa4a1c 100644
@@ -128,6 +128,15 @@ static inline bool arch_has_random_seed(void)
 {
 	return false;
 }
+/*
+ * Whether or not arch_get_random_seed_long() qualifies as a NIST
+ * SP800-90B compliant entropy source providing full entropy output.
+ * NIST SP800-90C NRBG's are probably fine, too.
+ */
+static inline bool arch_has_sp800_90b_random_seed(void)
+{
+	return false;
+}
 static inline bool __must_check arch_get_random_long(unsigned long *v)
 {
 	return false;

index 7712b4464ef5..aaddee4e4ab1 100644
@@ -1195,9 +1195,13 @@ static int min_crng_reseed_pool_entropy(void)
 	 * up to one half of the minimum entropy needed for
 	 * reseeding. That way it won't dominate the entropy
 	 * collected by other means at input_pool.
+	 * If in FIPS mode, restrict this to SP900-90B compliant
+	 * architectural RNGs.
 	 */
-	if (arch_has_random() || arch_has_random_seed())
+	if (arch_has_sp800_90b_random_seed() ||
+	    (!fips_enabled && (arch_has_random() || arch_has_random_seed()))) {
 		return 8;
+	}
 	return 16;
 }
 

@@ -1233,7 +1237,8 @@ static void crng_reseed(struct crng_state *crng, struct entropy_store *r)
 	for (i = 0; i < 8; i++) {
 		unsigned long	rv;
 		if (!arch_get_random_seed_long(&rv) &&
-		    !arch_get_random_long(&rv)) {
+		    ((arch_randomness_required && fips_enabled) ||
+		     !arch_get_random_long(&rv))) {
 			if (arch_randomness_required) {
 				/*
 				 * The input_pool failed to provide

index ae78fb68d231..30892675f48e 100644
@@ -942,6 +942,7 @@ asmlinkage __visible void __init __no_sanitize_address start_kernel(void)
 	hrtimers_init();
 	softirq_init();
 	timekeeping_init();
+	time_init();
 
 	/*
 	 * For best initial stack canary entropy, prepare it after:

@@ -956,7 +957,6 @@ asmlinkage __visible void __init __no_sanitize_address start_kernel(void)
 	add_device_randomness(command_line, strlen(command_line));
 	boot_init_stack_canary();
 
-	time_init();
 	perf_event_init();
 	profile_init();
 	call_function_init();

index aaddee4e4ab1..a985ceb22c7c 100644
@@ -335,6 +335,7 @@
 #include <linux/syscalls.h>
 #include <linux/completion.h>
 #include <linux/uuid.h>
+#include <linux/jump_label.h>
 #include <crypto/chacha.h>
 #include <crypto/sha.h>
 

@@ -478,6 +479,8 @@ static struct ratelimit_state urandom_warning =
 
 static int ratelimit_disable __read_mostly;
 
+static DEFINE_STATIC_KEY_TRUE(have_highres_cycle_ctr);
+
 module_param_named(ratelimit_disable, ratelimit_disable, int, 0644);
 MODULE_PARM_DESC(ratelimit_disable, "Disable random ratelimit suppression");
 

@@ -2170,6 +2173,31 @@ static void __init init_std_data(struct entropy_store *r)
 	mix_pool_bytes(r, utsname(), sizeof(*(utsname())));
 }
 
+static void probe_cycle_ctr_resolution(void)
+{
+	cycles_t prev;
+	int i;
+
+	if (!fips_enabled)
+		return;
+
+	/*
+	 * Check if the cycle counter has insn granularity (or at
+	 * least close to).
+	 */
+	prev = random_get_entropy();
+	for (i = 0; i < 16; ++i) {
+		cycles_t next;
+
+		next = random_get_entropy();
+		if (next == prev) {
+			static_branch_disable(&have_highres_cycle_ctr);
+			return;
+		}
+		prev = next;
+	}
+}
+
 /*
  * Note that setup_arch() may call add_device_randomness()
  * long before we get here. This allows seeding of the pools

@@ -2182,6 +2210,7 @@ static void __init init_std_data(struct entropy_store *r)
  */
 int __init rand_initialize(void)
 {
+	probe_cycle_ctr_resolution();
 	init_std_data(&input_pool);
 	crng_initialize_primary(&primary_crng);
 	crng_global_init_time = jiffies;

index a985ceb22c7c..ac36c56dd135 100644
@@ -1547,6 +1547,58 @@ static __u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
 	return *ptr;
 }
 
+/*
+ * Calculate the entropy of a fast_pool after num_events IRQ events of
+ * assessed entropy 2^-event_entropy_shift each have been mixed in.
+ */
+static unsigned int fast_pool_entropy(unsigned int num_events,
+				      int event_entropy_shift)
+{
+	unsigned int result, cur, interval_len;
+
+	/*
+	 * Assume that each event fed into the fast_pool
+	 * carries h = 2^-event_entropy_shift bits of entropy.
+	 * In analogy to how entropy deltas are calculated
+	 * in pool_entropy_delta() for the struct entropy_store
+	 * input_pool, a fast_pool which received num_events
+	 * of total entropy num_events * h will contain
+	 * p * (1 - exp(-num_events * h / p)
+	 * bits of entropy, where p equals the poolsize of 128 bits.
+	 *
+	 * Note that most of the time num_events will be ~64, c.f.
+	 * add_interrupt_randomness.  Approximate the resulting
+	 * fast_pool entropy in a piecewise linear manner from below:
+	 * from 0 to 32, from 32 to 96 and from 96 to 224.
+	 * Event entropy above 224 gets simply discarded. For p = 128,
+	 * the calculated fast_pool entropy is ~226 at
+	 * num_events * h == 32, ~540 at 96 and ~846 at 224, all given
+	 * in units of 2^-ENTROPY_SHIFT.
+	 */
+	BUILD_BUG_ON(sizeof(((struct fast_pool *)NULL)->pool) != 16);
+	BUILD_BUG_ON(ENTROPY_SHIFT != 3);
+
+	/* Interval from 0 to 32. */
+	interval_len = 32 << event_entropy_shift;
+	cur = min_t(unsigned int, num_events, interval_len);
+	result = (226 * cur) >> 5; /* shift is for /32 */
+	num_events -= cur;
+
+	/* Interval of length 64 from 32 to 96. */
+	interval_len <<= 1;
+	cur = min_t(unsigned int, num_events, interval_len);
+	result += ((540 - 226) * cur) >> 6; /* shift is for /64 */
+	num_events -= cur;
+
+	/* Interval of length 128 from 96 to 224. */
+	interval_len <<= 1;
+	cur = min_t(unsigned int, num_events, interval_len);
+	result += ((846 - 540) * cur) >> 7; /* shift is for /128 */
+
+	/* Return value is in units of 2^-ENTROPY_SHIFT. */
+	return result >> event_entropy_shift;
+}
+
 void add_interrupt_randomness(int irq, int irq_flags)
 {
 	struct entropy_store	*r;

index ac36c56dd135..8f79e90f2429 100644
@@ -615,6 +615,7 @@ struct fast_pool {
 	unsigned long	last;
 	unsigned short	reg_idx;
 	unsigned char	count;
+	int		event_entropy_shift;
 };
 
 /*

@@ -1509,7 +1510,9 @@ void add_input_randomness(unsigned int type, unsigned int code,
 }
 EXPORT_SYMBOL_GPL(add_input_randomness);
 
-static DEFINE_PER_CPU(struct fast_pool, irq_randomness);
+static DEFINE_PER_CPU(struct fast_pool, irq_randomness) = {
+	.event_entropy_shift = -1,
+};
 
 #ifdef ADD_INTERRUPT_BENCH
 static unsigned long avg_cycles, avg_deviation;

@@ -1599,6 +1602,32 @@ static unsigned int fast_pool_entropy(unsigned int num_events,
 	return result >> event_entropy_shift;
 }
 
+static inline int min_irq_event_entropy_shift(void)
+{
+	if (static_branch_likely(&have_highres_cycle_ctr)) {
+		/*
+		 * If a cycle counter with a good enough resolution is
+		 * available, estimate the entropy per IRQ event to
+		 * be no more than 2^-0 == 1 bit.
+		 */
+		return 0;
+	}
+
+	/*
+	 * Otherwise return an estimate upper bound of
+	 * 2^-3 == 1/8 bit per event.
+	 */
+	return 3;
+}
+
+static inline void fast_pool_init_accounting(struct fast_pool *f)
+{
+	if (likely(f->event_entropy_shift >= 0))
+		return;
+
+	f->event_entropy_shift = min_irq_event_entropy_shift();
+}
+
 void add_interrupt_randomness(int irq, int irq_flags)
 {
 	struct entropy_store	*r;

@@ -1610,6 +1639,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	__u64			ip;
 	bool			reseed;
 	struct queued_entropy	q = { 0 };
+	unsigned int		nfrac;
 
 	if (cycles == 0)
 		cycles = get_reg(fast_pool, regs);

@@ -1644,13 +1674,23 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	if (!spin_trylock(&r->lock))
 		return;
 
-	fast_pool->last = now;
-	fast_pool->count = 0;
-	/* award one bit for the contents of the fast pool */
-	__queue_entropy(r, &q, 1 << ENTROPY_SHIFT);
+	fast_pool_init_accounting(fast_pool);
+
+	if (!fips_enabled) {
+		/* award one bit for the contents of the fast pool */
+		nfrac = 1 << ENTROPY_SHIFT;
+	} else {
+		nfrac = fast_pool_entropy(fast_pool->count,
+					  fast_pool->event_entropy_shift);
+	}
+	__queue_entropy(r, &q, nfrac);
 	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
 	reseed = __dispatch_queued_entropy_fast(r, &q);
 	spin_unlock(&r->lock);
+
+	fast_pool->last = now;
+	fast_pool->count = 0;
+
 	if (reseed)
 		crng_reseed(&primary_crng, r);
 }

index 8f79e90f2429..680ccc82a436 100644
@@ -1481,12 +1481,24 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 
 	r = &input_pool;
 	spin_lock_irqsave(&r->lock, flags);
-	/*
-	 * delta is now minimum absolute delta.
-	 * Round down by 1 bit on general principles,
-	 * and limit entropy estimate to 12 bits.
-	 */
-	__queue_entropy(r, &q, min_t(int, fls(delta>>1), 11) << ENTROPY_SHIFT);
+	if (!fips_enabled) {
+		unsigned int nfrac;
+
+		/*
+		 * delta is now minimum absolute delta.
+		 * Round down by 1 bit on general principles,
+		 * and limit entropy estimate to 12 bits.
+		 */
+		nfrac = min_t(int, fls(delta>>1), 11) << ENTROPY_SHIFT;
+		__queue_entropy(r, &q, nfrac);
+	} else {
+		/*
+		 * Multiple correlated entropy sources are prohibited
+		 * by NIST SP800-90C. Leave it up to
+		 * add_interrupt_randomness() to contribute any
+		 * entropy.
+		 */
+	}
 	__mix_pool_bytes(r, &sample, sizeof(sample));
 	reseed = __dispatch_queued_entropy_fast(r, &q);
 	spin_unlock_irqrestore(&r->lock, flags);

index 680ccc82a436..55e784a5a2ec 100644
@@ -519,6 +519,10 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 static ssize_t _extract_entropy(struct entropy_store *r, void *buf,
 				size_t nbytes, int fips);
 
+static unsigned int pool_entropy_delta(struct entropy_store *r,
+				       int base_entropy_count,
+				       int nfrac, bool fast);
+
 static int min_crng_reseed_pool_entropy(void);
 
 static void crng_reseed(struct crng_state *crng, struct entropy_store *r);

@@ -610,125 +614,6 @@ static void mix_pool_bytes(struct entropy_store *r, const void *in,
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
-struct fast_pool {
-	__u32		pool[4];
-	unsigned long	last;
-	unsigned short	reg_idx;
-	unsigned char	count;
-	int		event_entropy_shift;
-};
-
-/*
- * This is a fast mixing routine used by the interrupt randomness
- * collector.  It's hardcoded for an 128 bit pool and assumes that any
- * locks that might be needed are taken by the caller.
- */
-static void fast_mix(struct fast_pool *f)
-{
-	__u32 a = f->pool[0],	b = f->pool[1];
-	__u32 c = f->pool[2],	d = f->pool[3];
-
-	a += b;			c += d;
-	b = rol32(b, 6);	d = rol32(d, 27);
-	d ^= a;			b ^= c;
-
-	a += b;			c += d;
-	b = rol32(b, 16);	d = rol32(d, 14);
-	d ^= a;			b ^= c;
-
-	a += b;			c += d;
-	b = rol32(b, 6);	d = rol32(d, 27);
-	d ^= a;			b ^= c;
-
-	a += b;			c += d;
-	b = rol32(b, 16);	d = rol32(d, 14);
-	d ^= a;			b ^= c;
-
-	f->pool[0] = a;  f->pool[1] = b;
-	f->pool[2] = c;  f->pool[3] = d;
-	f->count++;
-}
-
-static void process_random_ready_list(void)
-{
-	unsigned long flags;
-	struct random_ready_callback *rdy, *tmp;
-
-	spin_lock_irqsave(&random_ready_list_lock, flags);
-	list_for_each_entry_safe(rdy, tmp, &random_ready_list, list) {
-		struct module *owner = rdy->owner;
-
-		list_del_init(&rdy->list);
-		rdy->func(rdy);
-		module_put(owner);
-	}
-	spin_unlock_irqrestore(&random_ready_list_lock, flags);
-}
-
-/*
- * Based on the pool's current entropy fill level, specified as
- * base_entropy_count, and the number of new entropy bits in units of
- * 2^-ENTROPY_SHIFT 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 unsigned int pool_entropy_delta(struct entropy_store *r,
-				       int base_entropy_count,
-				       int nfrac, bool fast)
-{
-	const int pool_size = r->poolinfo->poolfracbits;
-	int entropy_count = base_entropy_count;
-
-	if (!nfrac)
-		return 0;
-
-	if (pool_size <= base_entropy_count)
-		return 0;
-
-	/*
-	 * 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.
-	 */
-	do {
-		/* The +2 corresponds to the /4 in the denominator */
-		const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
-		unsigned int anfrac = min(nfrac, pool_size/2);
-		unsigned int add =
-			((pool_size - entropy_count)*anfrac*3) >> s;
-
-		entropy_count += add;
-		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 = base_entropy_count;
-	} else if (entropy_count > pool_size) {
-		entropy_count = pool_size;
-	}
-
-	return entropy_count - base_entropy_count;
-}
-
 struct queued_entropy {
 	unsigned int pool_watermark_seq;
 	unsigned int queued_entropy_fracbits;

@@ -994,6 +879,126 @@ static void discard_queued_entropy(struct entropy_store *r,
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
+struct fast_pool {
+	__u32		pool[4];
+	unsigned long	last;
+	unsigned short	reg_idx;
+	unsigned char	count;
+	int		event_entropy_shift;
+};
+
+/*
+ * This is a fast mixing routine used by the interrupt randomness
+ * collector.  It's hardcoded for an 128 bit pool and assumes that any
+ * locks that might be needed are taken by the caller.
+ */
+static void fast_mix(struct fast_pool *f)
+{
+	__u32 a = f->pool[0],	b = f->pool[1];
+	__u32 c = f->pool[2],	d = f->pool[3];
+
+	a += b;			c += d;
+	b = rol32(b, 6);	d = rol32(d, 27);
+	d ^= a;			b ^= c;
+
+	a += b;			c += d;
+	b = rol32(b, 16);	d = rol32(d, 14);
+	d ^= a;			b ^= c;
+
+	a += b;			c += d;
+	b = rol32(b, 6);	d = rol32(d, 27);
+	d ^= a;			b ^= c;
+
+	a += b;			c += d;
+	b = rol32(b, 16);	d = rol32(d, 14);
+	d ^= a;			b ^= c;
+
+	f->pool[0] = a;  f->pool[1] = b;
+	f->pool[2] = c;  f->pool[3] = d;
+	f->count++;
+}
+
+static void process_random_ready_list(void)
+{
+	unsigned long flags;
+	struct random_ready_callback *rdy, *tmp;
+
+	spin_lock_irqsave(&random_ready_list_lock, flags);
+	list_for_each_entry_safe(rdy, tmp, &random_ready_list, list) {
+		struct module *owner = rdy->owner;
+
+		list_del_init(&rdy->list);
+		rdy->func(rdy);
+		module_put(owner);
+	}
+	spin_unlock_irqrestore(&random_ready_list_lock, flags);
+}
+
+/*
+ * Based on the pool's current entropy fill level, specified as
+ * base_entropy_count, and the number of new entropy bits in units of
+ * 2^-ENTROPY_SHIFT 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 unsigned int pool_entropy_delta(struct entropy_store *r,
+				       int base_entropy_count,
+				       int nfrac, bool fast)
+{
+	const int pool_size = r->poolinfo->poolfracbits;
+	int entropy_count = base_entropy_count;
+
+	if (!nfrac)
+		return 0;
+
+	if (pool_size <= base_entropy_count)
+		return 0;
+
+	/*
+	 * 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.
+	 */
+	do {
+		/* The +2 corresponds to the /4 in the denominator */
+		const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
+		unsigned int anfrac = min(nfrac, pool_size/2);
+		unsigned int add =
+			((pool_size - entropy_count)*anfrac*3) >> s;
+
+		entropy_count += add;
+		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 = base_entropy_count;
+	} else if (entropy_count > pool_size) {
+		entropy_count = pool_size;
+	}
+
+	return entropy_count - base_entropy_count;
+}
+
+
 /*********************************************************************
  *
  * CRNG using CHACHA20

index 55e784a5a2ec..37746df53acf 100644
@@ -885,6 +885,7 @@ struct fast_pool {
 	unsigned short	reg_idx;
 	unsigned char	count;
 	int		event_entropy_shift;
+	struct queued_entropy	q;
 };
 
 /*

@@ -1655,7 +1656,7 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	__u32			c_high, j_high;
 	__u64			ip;
 	bool			reseed;
-	struct queued_entropy	q = { 0 };
+	struct queued_entropy	*q = &fast_pool->q;
 	unsigned int		nfrac;
 
 	if (cycles == 0)

@@ -1700,9 +1701,9 @@ void add_interrupt_randomness(int irq, int irq_flags)
 		nfrac = fast_pool_entropy(fast_pool->count,
 					  fast_pool->event_entropy_shift);
 	}
-	__queue_entropy(r, &q, nfrac);
+	__queue_entropy(r, q, nfrac);
 	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
-	reseed = __dispatch_queued_entropy_fast(r, &q);
+	reseed = __dispatch_queued_entropy_fast(r, q);
 	spin_unlock(&r->lock);
 
 	fast_pool->last = now;

index 37746df53acf..0f56c873a501 100644
@@ -879,6 +879,11 @@ static void discard_queued_entropy(struct entropy_store *r,
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
+struct health_test {};
+
+static void health_test_reset(struct health_test *h)
+{}
+
 struct fast_pool {
 	__u32		pool[4];
 	unsigned long	last;

@@ -886,6 +891,7 @@ struct fast_pool {
 	unsigned char	count;
 	int		event_entropy_shift;
 	struct queued_entropy	q;
+	struct health_test	health;
 };
 
 /*

@@ -1644,6 +1650,7 @@ static inline void fast_pool_init_accounting(struct fast_pool *f)
 		return;
 
 	f->event_entropy_shift = min_irq_event_entropy_shift();
+	health_test_reset(&f->health);
 }
 
 void add_interrupt_randomness(int irq, int irq_flags)

@@ -1674,6 +1681,8 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	add_interrupt_bench(cycles);
 	this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]);
 
+	fast_pool_init_accounting(fast_pool);
+
 	if (unlikely(crng_init == 0)) {
 		if ((fast_pool->count >= 64) &&
 		    crng_fast_load((char *) fast_pool->pool,

@@ -1692,8 +1701,6 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	if (!spin_trylock(&r->lock))
 		return;
 
-	fast_pool_init_accounting(fast_pool);
-
 	if (!fips_enabled) {
 		/* award one bit for the contents of the fast pool */
 		nfrac = 1 << ENTROPY_SHIFT;

index 0f56c873a501..cb6441b96b8e 100644
@@ -881,14 +881,30 @@ static void discard_queued_entropy(struct entropy_store *r,
 
 struct health_test {};
 
+enum health_result {
+	health_none,
+	health_queue,
+	health_dispatch,
+	health_discard,
+};
+
 static void health_test_reset(struct health_test *h)
 {}
 
+static enum health_result
+health_test_process(struct health_test *h, unsigned int event_entropy_shift,
+		    u8 sample)
+{
+	return health_none;
+}
+
 struct fast_pool {
 	__u32		pool[4];
 	unsigned long	last;
 	unsigned short	reg_idx;
 	unsigned char	count;
+	bool		dispatch_needed : 1;
+	bool		discard_needed : 1;
 	int		event_entropy_shift;
 	struct queued_entropy	q;
 	struct health_test	health;

@@ -1662,9 +1678,10 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	cycles_t		cycles = random_get_entropy();
 	__u32			c_high, j_high;
 	__u64			ip;
-	bool			reseed;
+	bool			reseed = false;
 	struct queued_entropy	*q = &fast_pool->q;
 	unsigned int		nfrac;
+	enum health_result	health_result = health_none;
 
 	if (cycles == 0)
 		cycles = get_reg(fast_pool, regs);

@@ -1682,6 +1699,12 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	this_cpu_add(net_rand_state.s1, fast_pool->pool[cycles & 3]);
 
 	fast_pool_init_accounting(fast_pool);
+	if (fips_enabled) {
+		health_result =
+			health_test_process(&fast_pool->health,
+					    fast_pool->event_entropy_shift,
+					    cycles);
+	}
 
 	if (unlikely(crng_init == 0)) {
 		if ((fast_pool->count >= 64) &&

@@ -1693,8 +1716,48 @@ void add_interrupt_randomness(int irq, int irq_flags)
 		return;
 	}
 
+	switch (health_result) {
+	case health_dispatch:
+		/*
+		 * Still haven't made it around processing a previous
+		 * entropy discard request?
+		 */
+		fast_pool->dispatch_needed = !fast_pool->discard_needed;
+		break;
+
+	case health_discard:
+		/*
+		 * Still haven't made it around processing a previous
+		 * entropy dispatch request?
+		 */
+		fast_pool->discard_needed = !fast_pool->dispatch_needed;
+		break;
+
+	case health_queue:
+		/*
+		 * If a previous sample triggered a dispatch which is
+		 * still pending, it's impossible to add new events on
+		 * top as far as entropy accounting is
+		 * concerned. Don't count any events until we get a
+		 * hold of the input_pool ->lock and complete the
+		 * dispatch below. Undo the increment from fast_mix()
+		 * above.
+		 */
+		if (fast_pool->dispatch_needed)
+			fast_pool->count--;
+		break;
+
+	case health_none:
+		/*
+		 * fips_enabled is unset, suppress compiler warnings.
+		 */
+		break;
+	};
+
 	if ((fast_pool->count < 64) &&
-	    !time_after(now, fast_pool->last + HZ))
+	    !(health_result == health_none &&
+	      time_after(now, fast_pool->last + HZ)) &&
+	    !fast_pool->dispatch_needed && !fast_pool->discard_needed)
 		return;
 
 	r = &input_pool;

@@ -1710,7 +1773,16 @@ void add_interrupt_randomness(int irq, int irq_flags)
 	}
 	__queue_entropy(r, q, nfrac);
 	__mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
-	reseed = __dispatch_queued_entropy_fast(r, q);
+
+	if (fast_pool->dispatch_needed || health_result == health_none) {
+		reseed = __dispatch_queued_entropy_fast(r, q);
+		fast_pool->dispatch_needed = false;
+	} else if (fast_pool->discard_needed) {
+		int dummy;
+
+		__dequeue_entropy(r, q, &dummy);
+		fast_pool->discard_needed = false;
+	}
 	spin_unlock(&r->lock);
 
 	fast_pool->last = now;

index cb6441b96b8e..33f9b7b59f92 100644
@@ -879,7 +879,9 @@ static void discard_queued_entropy(struct entropy_store *r,
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
-struct health_test {};
+struct health_test {
+	u8 previous_sample;
+};
 
 enum health_result {
 	health_none,

@@ -895,6 +897,16 @@ static enum health_result
 health_test_process(struct health_test *h, unsigned int event_entropy_shift,
 		    u8 sample)
 {
+	u8 sample_delta;
+
+	/*
+	 * The min-entropy estimate has been made for the lower eight
+	 * bits of the deltas between cycle counter values from
+	 * successive IRQ events.
+	 */
+	sample_delta = sample - h->previous_sample;
+	h->previous_sample = sample;
+
 	return health_none;
 }
 

index 33f9b7b59f92..131302cbc495 100644
@@ -880,6 +880,10 @@ static void discard_queued_entropy(struct entropy_store *r,
 }
 
 struct health_test {
+	unsigned short apt_event_count;
+	unsigned short apt_candidate_count;
+	u8 apt_candidate;
+
 	u8 previous_sample;
 };
 

@@ -890,8 +894,56 @@ enum health_result {
 	health_discard,
 };
 
+/* Adaptive Proportion Test */
+static void health_apt_reset(struct health_test *h)
+{
+	h->apt_event_count = 0;
+}
+
+static enum health_result
+health_test_apt(struct health_test *h, unsigned int event_entropy_shift,
+		u8 sample_delta)
+{
+	unsigned int n = 128 << event_entropy_shift;
+	/*
+	 * Observing some particular sample value more often than
+	 * these thresholds, specified for the different possible
+	 * values of event_entropy_shift each, should have probability
+	 * <= 2^-16.
+	 */
+	static const unsigned int c[] = {87, 210, 463, 973, 1997, 4044, 8140};
+
+	if (!h->apt_event_count) {
+		h->apt_event_count = 1;
+		h->apt_candidate = sample_delta;
+		h->apt_candidate_count = 0;
+		return health_queue;
+	}
+
+	++h->apt_event_count;
+	if (unlikely(h->apt_candidate == sample_delta &&
+		     ++h->apt_candidate_count == c[event_entropy_shift])) {
+		health_apt_reset(h);
+		return health_discard;
+	} else if (c[event_entropy_shift] - h->apt_candidate_count >
+		   n - h->apt_event_count) {
+		/*
+		 * The currently pending APT might not have seen all n
+		 * events yet, but it's already known by now that it
+		 * can't fail anymore. Note that the above condition
+		 * also coverts the case h->apt_event_count == n.
+		 */
+		health_apt_reset(h);
+		return health_dispatch;
+	}
+
+	return health_queue;
+}
+
 static void health_test_reset(struct health_test *h)
-{}
+{
+	health_apt_reset(h);
+}
 
 static enum health_result
 health_test_process(struct health_test *h, unsigned int event_entropy_shift,

@@ -907,7 +959,7 @@ health_test_process(struct health_test *h, unsigned int event_entropy_shift,
 	sample_delta = sample - h->previous_sample;
 	h->previous_sample = sample;
 
-	return health_none;
+	return health_test_apt(h, event_entropy_shift, sample_delta);
 }
 
 struct fast_pool {

index 131302cbc495..75a103f24fea 100644
@@ -881,8 +881,13 @@ static void discard_queued_entropy(struct entropy_store *r,
 
 struct health_test {
 	unsigned short apt_event_count;
-	unsigned short apt_candidate_count;
-	u8 apt_candidate;
+	union {
+		u8 apt_presearch_bit_counters[8];
+		struct {
+			unsigned short apt_candidate_count;
+			u8 apt_candidate;
+		};
+	};
 
 	u8 previous_sample;
 };

@@ -895,9 +900,44 @@ enum health_result {
 };
 
 /* Adaptive Proportion Test */
+#define HEALTH_APT_PRESEARCH_EVENT_COUNT 7
+
+static void health_apt_presearch_update(struct health_test *h, u8 sample_delta)
+{
+	int i;
+
+	for (i = 0; i < 8; ++i) {
+		h->apt_presearch_bit_counters[i] = sample_delta & 0x1;
+		sample_delta >>= 1;
+	}
+}
+
+static void health_apt_presearch_finalize(struct health_test *h)
+{
+	int i;
+
+	/*
+	 * If some event octet occurred more than half of the time,
+	 * i.e. more than HEALTH_APT_PRESEARCH_EVENT_COUNT / 2 times,
+	 * then its value can be restored unambigiously from the eight
+	 * ->apt_presearch_bit_counters each holding the count of 1s
+	 * encountered at the corresponding bit positions.
+	 */
+	h->apt_candidate = 0;
+	for (i = 0; i < 8; ++i) {
+		if (h->apt_presearch_bit_counters[i] >=
+		    (HEALTH_APT_PRESEARCH_EVENT_COUNT + 1) / 2) {
+			h->apt_candidate |= 1 << i;
+		}
+	}
+	h->apt_candidate_count = 0;
+};
+
 static void health_apt_reset(struct health_test *h)
 {
 	h->apt_event_count = 0;
+	memset(h->apt_presearch_bit_counters, 0,
+		sizeof(h->apt_presearch_bit_counters));
 }
 
 static enum health_result

@@ -911,16 +951,18 @@ health_test_apt(struct health_test *h, unsigned int event_entropy_shift,
 	 * values of event_entropy_shift each, should have probability
 	 * <= 2^-16.
 	 */
-	static const unsigned int c[] = {87, 210, 463, 973, 1997, 4044, 8140};
+	static const unsigned int c[] = {83, 205, 458, 968, 1991, 4038, 8134};
+
+	BUILD_BUG_ON(HEALTH_APT_PRESEARCH_EVENT_COUNT != 7);
 
-	if (!h->apt_event_count) {
-		h->apt_event_count = 1;
-		h->apt_candidate = sample_delta;
-		h->apt_candidate_count = 0;
+	++h->apt_event_count;
+	if (unlikely(h->apt_event_count <= HEALTH_APT_PRESEARCH_EVENT_COUNT)) {
+		health_apt_presearch_update(h, sample_delta);
+		if (h->apt_event_count == HEALTH_APT_PRESEARCH_EVENT_COUNT)
+			health_apt_presearch_finalize(h);
 		return health_queue;
 	}
 
-	++h->apt_event_count;
 	if (unlikely(h->apt_candidate == sample_delta &&
 		     ++h->apt_candidate_count == c[event_entropy_shift])) {
 		health_apt_reset(h);