Skip to contentSkip to conversation

random: do crng pre-init loading in worker rather than irq

PATCH Superseded Jason A. Donenfeld 3 participants 12 messages Feb 23, 2022 – Feb 28, 2022

Subsystems (2)
lore
Share & tools
lore

Jason A. Donenfeld

author maintainer
#0 lore raw

PATCH 1/1 random: do crng pre-init loading in worker rather than irq

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

But maybe there's another reason to change things up: by deferring the crng pre-init loading to the worker, we can use the cryptographic hash function rather than xor, which is perhaps a meaningful difference when considering this data has only been through the relatively weak fast_mix() function.

The biggest downside of this approach is that the pre-init loading is now deferred until later, which means things that need random numbers after interrupts are enabled, but before workqueues are running -- or before this particular worker manages to run -- are going to get into trouble. Hopefully in the real world, this window is rather small, especially since this code won't run until 64 interrupts had occurred.

Cc Dominik Brodowski <[email protected]>
Cc Sebastian Andrzej Siewior <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
---
 drivers/char/random.c | 62 ++++++++++++-------------------------------
 1 file changed, 17 insertions(+), 45 deletions(-)
drivers/char/random.c +17 -45
index 536237a0f073..9fb06fc298d3 100644
@@ -443,10 +443,6 @@ static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS],
  * boot time when it's better to have something there rather than
  * nothing.
  *
- * There are two paths, a slow one and a fast one. The slow one
- * hashes the input along with the current key. The fast one simply
- * xors it in, and should only be used from interrupt context.
- *
  * If account is set, then the crng_init_cnt counter is incremented.
  * This shouldn't be set by functions like add_device_randomness(),
  * where we can't trust the buffer passed to it is guaranteed to be
@@ -455,19 +451,15 @@ static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS],
  * Returns the number of bytes processed from input, which is bounded
  * by CRNG_INIT_CNT_THRESH if account is true.
  */
-static size_t crng_pre_init_inject(const void *input, size_t len,
-				   bool fast, bool account)
+static size_t crng_pre_init_inject(const void *input, size_t len, bool account)
 {
 	static int crng_init_cnt = 0;
+	struct blake2s_state hash;
 	unsigned long flags;
 
-	if (fast) {
-		if (!spin_trylock_irqsave(&base_crng.lock, flags))
-			return 0;
-	} else {
-		spin_lock_irqsave(&base_crng.lock, flags);
-	}
+	blake2s_init(&hash, sizeof(base_crng.key));
 
+	spin_lock_irqsave(&base_crng.lock, flags);
 	if (crng_init != 0) {
 		spin_unlock_irqrestore(&base_crng.lock, flags);
 		return 0;
@@ -476,21 +468,9 @@ static size_t crng_pre_init_inject(const void *input, size_t len,
 	if (account)
 		len = min_t(size_t, len, CRNG_INIT_CNT_THRESH - crng_init_cnt);
 
-	if (fast) {
-		const u8 *src = input;
-		size_t i;
-
-		for (i = 0; i < len; ++i)
-			base_crng.key[(crng_init_cnt + i) %
-				      sizeof(base_crng.key)] ^= src[i];
-	} else {
-		struct blake2s_state hash;
-
-		blake2s_init(&hash, sizeof(base_crng.key));
-		blake2s_update(&hash, base_crng.key, sizeof(base_crng.key));
-		blake2s_update(&hash, input, len);
-		blake2s_final(&hash, base_crng.key);
-	}
+	blake2s_update(&hash, base_crng.key, sizeof(base_crng.key));
+	blake2s_update(&hash, input, len);
+	blake2s_final(&hash, base_crng.key);
 
 	if (account) {
 		crng_init_cnt += len;
@@ -1040,7 +1020,7 @@ void add_device_randomness(const void *buf, size_t size)
 	unsigned long flags;
 
 	if (crng_init == 0 && size)
-		crng_pre_init_inject(buf, size, false, false);
+		crng_pre_init_inject(buf, size, false);
 
 	spin_lock_irqsave(&input_pool.lock, flags);
 	_mix_pool_bytes(buf, size);
@@ -1157,7 +1137,7 @@ void add_hwgenerator_randomness(const void *buffer, size_t count,
 				size_t entropy)
 {
 	if (unlikely(crng_init == 0)) {
-		size_t ret = crng_pre_init_inject(buffer, count, false, true);
+		size_t ret = crng_pre_init_inject(buffer, count, true);
 		mix_pool_bytes(buffer, ret);
 		count -= ret;
 		buffer += ret;
@@ -1298,7 +1278,12 @@ static void mix_interrupt_randomness(struct work_struct *work)
 	local_irq_enable();
 
 	mix_pool_bytes(pool, sizeof(pool));
-	credit_entropy_bits(1);
+
+	if (unlikely(crng_init == 0))
+		crng_pre_init_inject(pool, sizeof(pool), true);
+	else
+		credit_entropy_bits(1);
+
 	memzero_explicit(pool, sizeof(pool));
 }
 
@@ -1331,24 +1316,11 @@ void add_interrupt_randomness(int irq)
 	fast_mix(fast_pool->pool32);
 	new_count = ++fast_pool->count;
 
-	if (unlikely(crng_init == 0)) {
-		if (new_count >= 64 &&
-		    crng_pre_init_inject(fast_pool->pool32, sizeof(fast_pool->pool32),
-					 true, true) > 0) {
-			fast_pool->count = 0;
-			fast_pool->last = now;
-			if (spin_trylock(&input_pool.lock)) {
-				_mix_pool_bytes(&fast_pool->pool32, sizeof(fast_pool->pool32));
-				spin_unlock(&input_pool.lock);
-			}
-		}
-		return;
-	}
-
 	if (new_count & MIX_INFLIGHT)
 		return;
 
-	if (new_count < 64 && !time_after(now, fast_pool->last + HZ))
+	if (new_count < 64 && (!time_after(now, fast_pool->last + HZ) ||
+			       unlikely(crng_init == 0)))
 		return;
 
 	if (unlikely(!fast_pool->mix.func))
Signature · 1 line
2.35.1
Reviewed-by on v1 1/1
#1 lore raw

Am Wed, Feb 23, 2022 at 07:55:11PM +0100 schrieb Jason A. Donenfeld:

Quoted 37 lines

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

But maybe there's another reason to change things up: by deferring the crng pre-init loading to the worker, we can use the cryptographic hash function rather than xor, which is perhaps a meaningful difference when considering this data has only been through the relatively weak fast_mix() function.

The biggest downside of this approach is that the pre-init loading is now deferred until later, which means things that need random numbers after interrupts are enabled, but before workqueues are running -- or before this particular worker manages to run -- are going to get into trouble. Hopefully in the real world, this window is rather small, especially since this code won't run until 64 interrupts had occurred.

Cc Dominik Brodowski <[email protected]>
Cc Sebastian Andrzej Siewior <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
---
 drivers/char/random.c | 62 ++++++++++++-------------------------------
 1 file changed, 17 insertions(+), 45 deletions(-)
drivers/char/random.c +0 -0
index 536237a0f073..9fb06fc298d3 100644
@@ -1298,7 +1278,12 @@ static void mix_interrupt_randomness(struct work_struct *work)
 	local_irq_enable();
 

drivers/char/random.c static void mix_interrupt_randomness(struct work_struct *work) · line 1288

Quoted 10 lines
drivers/char/random.c +6 -1
 	mix_pool_bytes(pool, sizeof(pool));
-	credit_entropy_bits(1);
+
+	if (unlikely(crng_init == 0))
+		crng_pre_init_inject(pool, sizeof(pool), true);
+	else
+		credit_entropy_bits(1);
+
 	memzero_explicit(pool, sizeof(pool));
 }

Might it make sense to call crng_pre_init_inject() before mix_pool_bytes? Otherwise, all looks fine:

Thanks
Dominik

author maintainer
#2 lore raw
Quoted 39 lines · Dominik Brodowski

Am Wed, Feb 23, 2022 at 07:55:11PM +0100 schrieb Jason A. Donenfeld:

Quoted 38 lines

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

But maybe there's another reason to change things up: by deferring the crng pre-init loading to the worker, we can use the cryptographic hash function rather than xor, which is perhaps a meaningful difference when considering this data has only been through the relatively weak fast_mix() function.

The biggest downside of this approach is that the pre-init loading is now deferred until later, which means things that need random numbers after interrupts are enabled, but before workqueues are running -- or before this particular worker manages to run -- are going to get into trouble. Hopefully in the real world, this window is rather small, especially since this code won't run until 64 interrupts had occurred.

Cc Dominik Brodowski <[email protected]>
Cc Sebastian Andrzej Siewior <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
---
 drivers/char/random.c | 62 ++++++++++++-------------------------------
 1 file changed, 17 insertions(+), 45 deletions(-)
drivers/char/random.c +0 -0
index 536237a0f073..9fb06fc298d3 100644
@@ -1298,7 +1278,12 @@ static void mix_interrupt_randomness(struct
 work_struct *work)
 	local_irq_enable();
 
Quoted 12 lines

drivers/char/random.c static void mix_interrupt_randomness(struct work_struct *work) · line 1288

Quoted 10 lines
drivers/char/random.c +6 -1
 	mix_pool_bytes(pool, sizeof(pool));
-	credit_entropy_bits(1);
+
+	if (unlikely(crng_init == 0))
+		crng_pre_init_inject(pool, sizeof(pool), true);
+	else
+		credit_entropy_bits(1);
+
 	memzero_explicit(pool, sizeof(pool));
 }

Might it make sense to call crng_pre_init_inject() before mix_pool_bytes?

What exactly is the difference you see mattering in the order? I keep chasing my tail trying to think about it.

Jason

#3 lore raw

Am Thu, Feb 24, 2022 at 10:49:12AM +0100 schrieb Jason A. Donenfeld:

Quoted 53 lines · Dominik Brodowski
Quoted 39 lines

Am Wed, Feb 23, 2022 at 07:55:11PM +0100 schrieb Jason A. Donenfeld:

Quoted 38 lines

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

But maybe there's another reason to change things up: by deferring the crng pre-init loading to the worker, we can use the cryptographic hash function rather than xor, which is perhaps a meaningful difference when considering this data has only been through the relatively weak fast_mix() function.

The biggest downside of this approach is that the pre-init loading is now deferred until later, which means things that need random numbers after interrupts are enabled, but before workqueues are running -- or before this particular worker manages to run -- are going to get into trouble. Hopefully in the real world, this window is rather small, especially since this code won't run until 64 interrupts had occurred.

Cc Dominik Brodowski <[email protected]>
Cc Sebastian Andrzej Siewior <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
---
 drivers/char/random.c | 62 ++++++++++++-------------------------------
 1 file changed, 17 insertions(+), 45 deletions(-)
drivers/char/random.c +0 -0
index 536237a0f073..9fb06fc298d3 100644
@@ -1298,7 +1278,12 @@ static void mix_interrupt_randomness(struct
 work_struct *work)
 	local_irq_enable();
 
Quoted 12 lines

drivers/char/random.c static void mix_interrupt_randomness(struct work_struct *work) · line 1288

Quoted 10 lines
drivers/char/random.c +6 -1
 	mix_pool_bytes(pool, sizeof(pool));
-	credit_entropy_bits(1);
+
+	if (unlikely(crng_init == 0))
+		crng_pre_init_inject(pool, sizeof(pool), true);
+	else
+		credit_entropy_bits(1);
+
 	memzero_explicit(pool, sizeof(pool));
 }

Might it make sense to call crng_pre_init_inject() before mix_pool_bytes?

Quoted 2 lines

What exactly is the difference you see mattering in the order? I keep chasing my tail trying to think about it.

We had that order beforehand -- and even if it probably doesn't matter, this means crng_pre_init_inject() gets called a tiny bit earlier. That means there's a chance to progres to crng_init=1 a tiny bit earlier as well.

Thanks,
Dominik

author maintainer
#4 lore raw
Quoted 55 lines · Dominik Brodowski

Am Thu, Feb 24, 2022 at 10:49:12AM +0100 schrieb Jason A. Donenfeld:

Quoted 53 lines · Dominik Brodowski
Quoted 51 lines

Am Wed, Feb 23, 2022 at 07:55:11PM +0100 schrieb Jason A. Donenfeld:

Quoted 38 lines

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

But maybe there's another reason to change things up: by deferring the crng pre-init loading to the worker, we can use the cryptographic hash function rather than xor, which is perhaps a meaningful difference when considering this data has only been through the relatively weak fast_mix() function.

The biggest downside of this approach is that the pre-init loading is now deferred until later, which means things that need random numbers after interrupts are enabled, but before workqueues are running -- or before this particular worker manages to run -- are going to get into trouble. Hopefully in the real world, this window is rather small, especially since this code won't run until 64 interrupts had occurred.

Cc Dominik Brodowski <[email protected]>
Cc Sebastian Andrzej Siewior <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
---
 drivers/char/random.c | 62 ++++++++++++-------------------------------
 1 file changed, 17 insertions(+), 45 deletions(-)
drivers/char/random.c +0 -0
index 536237a0f073..9fb06fc298d3 100644
@@ -1298,7 +1278,12 @@ static void mix_interrupt_randomness(struct
 work_struct *work)
   local_irq_enable();
 

drivers/char/random.c static void mix_interrupt_randomness(struct · line 1289

Quoted 10 lines
drivers/char/random.c +6 -1
   mix_pool_bytes(pool, sizeof(pool));
-  credit_entropy_bits(1);
+
+  if (unlikely(crng_init == 0))
+          crng_pre_init_inject(pool, sizeof(pool), true);
+  else
+          credit_entropy_bits(1);
+
   memzero_explicit(pool, sizeof(pool));
 }

Might it make sense to call crng_pre_init_inject() before mix_pool_bytes?

Quoted 6 lines
Quoted 2 lines

What exactly is the difference you see mattering in the order? I keep chasing my tail trying to think about it.

We had that order beforehand -- and even if it probably doesn't matter, this means crng_pre_init_inject() gets called a tiny bit earlier. That means there's a chance to progres to crng_init=1 a tiny bit earlier as well.

Alright, I'll send a v2.

author maintainer
#5 lore raw

PATCH v2 1/1 random: do crng pre-init loading in worker rather than irq

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

But maybe there's another reason to change things up: by deferring the crng pre-init loading to the worker, we can use the cryptographic hash function rather than xor, which is perhaps a meaningful difference when considering this data has only been through the relatively weak fast_mix() function.

The biggest downside of this approach is that the pre-init loading is now deferred until later, which means things that need random numbers after interrupts are enabled, but before workqueues are running -- or before this particular worker manages to run -- are going to get into trouble. Hopefully in the real world, this window is rather small, especially since this code won't run until 64 interrupts had occurred.

Cc Sebastian Andrzej Siewior <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Eric Biggers <[email protected]>
Cc Theodore Ts'o <[email protected]>

---
Changes v1->v2:
- [Dominik] Call crng_pre_init_inject() before calling mix_pool_bytes().

 drivers/char/random.c | 65 +++++++++++++------------------------------
 1 file changed, 19 insertions(+), 46 deletions(-)
drivers/char/random.c +19 -46
index 536237a0f073..19bf44b9ba0f 100644
@@ -443,10 +443,6 @@ static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS],
  * boot time when it's better to have something there rather than
  * nothing.
  *
- * There are two paths, a slow one and a fast one. The slow one
- * hashes the input along with the current key. The fast one simply
- * xors it in, and should only be used from interrupt context.
- *
  * If account is set, then the crng_init_cnt counter is incremented.
  * This shouldn't be set by functions like add_device_randomness(),
  * where we can't trust the buffer passed to it is guaranteed to be
@@ -455,19 +451,15 @@ static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS],
  * Returns the number of bytes processed from input, which is bounded
  * by CRNG_INIT_CNT_THRESH if account is true.
  */
-static size_t crng_pre_init_inject(const void *input, size_t len,
-				   bool fast, bool account)
+static size_t crng_pre_init_inject(const void *input, size_t len, bool account)
 {
 	static int crng_init_cnt = 0;
+	struct blake2s_state hash;
 	unsigned long flags;
 
-	if (fast) {
-		if (!spin_trylock_irqsave(&base_crng.lock, flags))
-			return 0;
-	} else {
-		spin_lock_irqsave(&base_crng.lock, flags);
-	}
+	blake2s_init(&hash, sizeof(base_crng.key));
 
+	spin_lock_irqsave(&base_crng.lock, flags);
 	if (crng_init != 0) {
 		spin_unlock_irqrestore(&base_crng.lock, flags);
 		return 0;
@@ -476,21 +468,9 @@ static size_t crng_pre_init_inject(const void *input, size_t len,
 	if (account)
 		len = min_t(size_t, len, CRNG_INIT_CNT_THRESH - crng_init_cnt);
 
-	if (fast) {
-		const u8 *src = input;
-		size_t i;
-
-		for (i = 0; i < len; ++i)
-			base_crng.key[(crng_init_cnt + i) %
-				      sizeof(base_crng.key)] ^= src[i];
-	} else {
-		struct blake2s_state hash;
-
-		blake2s_init(&hash, sizeof(base_crng.key));
-		blake2s_update(&hash, base_crng.key, sizeof(base_crng.key));
-		blake2s_update(&hash, input, len);
-		blake2s_final(&hash, base_crng.key);
-	}
+	blake2s_update(&hash, base_crng.key, sizeof(base_crng.key));
+	blake2s_update(&hash, input, len);
+	blake2s_final(&hash, base_crng.key);
 
 	if (account) {
 		crng_init_cnt += len;
@@ -1040,7 +1020,7 @@ void add_device_randomness(const void *buf, size_t size)
 	unsigned long flags;
 
 	if (crng_init == 0 && size)
-		crng_pre_init_inject(buf, size, false, false);
+		crng_pre_init_inject(buf, size, false);
 
 	spin_lock_irqsave(&input_pool.lock, flags);
 	_mix_pool_bytes(buf, size);
@@ -1157,7 +1137,7 @@ void add_hwgenerator_randomness(const void *buffer, size_t count,
 				size_t entropy)
 {
 	if (unlikely(crng_init == 0)) {
-		size_t ret = crng_pre_init_inject(buffer, count, false, true);
+		size_t ret = crng_pre_init_inject(buffer, count, true);
 		mix_pool_bytes(buffer, ret);
 		count -= ret;
 		buffer += ret;
@@ -1297,8 +1277,14 @@ static void mix_interrupt_randomness(struct work_struct *work)
 	fast_pool->last = jiffies;
 	local_irq_enable();
 
-	mix_pool_bytes(pool, sizeof(pool));
-	credit_entropy_bits(1);
+	if (unlikely(crng_init == 0)) {
+		crng_pre_init_inject(pool, sizeof(pool), true);
+		mix_pool_bytes(pool, sizeof(pool));
+	} else {
+		mix_pool_bytes(pool, sizeof(pool));
+		credit_entropy_bits(1);
+	}
+
 	memzero_explicit(pool, sizeof(pool));
 }
 
@@ -1331,24 +1317,11 @@ void add_interrupt_randomness(int irq)
 	fast_mix(fast_pool->pool32);
 	new_count = ++fast_pool->count;
 
-	if (unlikely(crng_init == 0)) {
-		if (new_count >= 64 &&
-		    crng_pre_init_inject(fast_pool->pool32, sizeof(fast_pool->pool32),
-					 true, true) > 0) {
-			fast_pool->count = 0;
-			fast_pool->last = now;
-			if (spin_trylock(&input_pool.lock)) {
-				_mix_pool_bytes(&fast_pool->pool32, sizeof(fast_pool->pool32));
-				spin_unlock(&input_pool.lock);
-			}
-		}
-		return;
-	}
-
 	if (new_count & MIX_INFLIGHT)
 		return;
 
-	if (new_count < 64 && !time_after(now, fast_pool->last + HZ))
+	if (new_count < 64 && (!time_after(now, fast_pool->last + HZ) ||
+			       unlikely(crng_init == 0)))
 		return;
 
 	if (unlikely(!fast_pool->mix.func))
Signature · 1 line
2.35.1
Acked-by on v2 1/1
#6 lore raw
Quoted 5 lines · Jason A. Donenfeld

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

Could you please post a lockdep report so I can take a look?

Quoted 13 lines

But maybe there's another reason to change things up: by deferring the crng pre-init loading to the worker, we can use the cryptographic hash function rather than xor, which is perhaps a meaningful difference when considering this data has only been through the relatively weak fast_mix() function.

The biggest downside of this approach is that the pre-init loading is now deferred until later, which means things that need random numbers after interrupts are enabled, but before workqueues are running -- or before this particular worker manages to run -- are going to get into trouble. Hopefully in the real world, this window is rather small, especially since this code won't run until 64 interrupts had occurred.

Quoted 7 lines
Cc Sebastian Andrzej Siewior <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Eric Biggers <[email protected]>
Cc Theodore Ts'o <[email protected]>

Other than that:

Sebastian

author maintainer
#7 lore raw

Hey Sebastian,

Quoted 8 lines · Sebastian Andrzej Siewior
Quoted 5 lines · Jason A. Donenfeld

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

Could you please post a lockdep report so I can take a look?

I thought the problem with lockdep was stated by you somewhere in this thread?
https://lore.kernel.org/lkml/[email protected]/
"But even then we need to find a way to move the crng init part (crng_fast_load()) out of the hard-IRQ."
And Jonathan posted two related (?) splats he ran into.

I may have gotten that all wrong, in which case, I'll just excise that part from the commit message. I'm pretty sure you want this patch either way, right?

Jason

#8 lore raw
Quoted 1 line · Jason A. Donenfeld

Hey Sebastian,

Hi Jason,

Quoted 16 lines · Sebastian Andrzej Siewior
Quoted 8 lines · Jason A. Donenfeld
Quoted 5 lines

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

Could you please post a lockdep report so I can take a look?

I thought the problem with lockdep was stated by you somewhere in this thread?
https://lore.kernel.org/lkml/[email protected]/
"But even then we need to find a way to move the crng init part (crng_fast_load()) out of the hard-IRQ."
And Jonathan posted two related (?) splats he ran into.

Quoted 3 lines

I may have gotten that all wrong, in which case, I'll just excise that part from the commit message. I'm pretty sure you want this patch either way, right?

Oh, that report. So yes, I want that patch ;)

In this case the lockdep is right. The thing that it affects only PREEMPT_RT.
That trylock is not the thing that lockdep complains about but the spin_lock_irqsave() within invalidate_batched_entropy().

Taking a spinlock_t from IRQ context is problematic for PREEMPT_RT, correct. A spin_try_lock() is also problematic since another spin_lock() invocation would PI-boost the wrong task (the spin_try_lock() is invoked from an IRQ-context so the task on CPU (random task or idle) is not the actual owner). I'm pointing this out because there was also _another_ problem with try_lock from hard-IRQ context which was fixed in the meantime.

Would it work for you to update the commit message? Basically I'm fine with the firs sentence but the remaining part is misleading.

Quoted 1 line

Jason

Sebastian

author maintainer
#9 lore raw

Hi Sebastian,

Quoted 27 lines · Sebastian Andrzej Siewior
Quoted 11 lines
Quoted 1 line

Could you please post a lockdep report so I can take a look?

I thought the problem with lockdep was stated by you somewhere in this thread?
https://lore.kernel.org/lkml/[email protected]/
"But even then we need to find a way to move the crng init part (crng_fast_load()) out of the hard-IRQ."
And Jonathan posted two related (?) splats he ran into.

I may have gotten that all wrong, in which case, I'll just excise that part from the commit message. I'm pretty sure you want this patch either way, right?

Oh, that report. So yes, I want that patch ;)

In this case the lockdep is right. The thing that it affects only PREEMPT_RT.
That trylock is not the thing that lockdep complains about but the spin_lock_irqsave() within invalidate_batched_entropy().

Taking a spinlock_t from IRQ context is problematic for PREEMPT_RT, correct. A spin_try_lock() is also problematic since another spin_lock() invocation would PI-boost the wrong task (the spin_try_lock() is invoked from an IRQ-context so the task on CPU (random task or idle) is not the actual owner). I'm pointing this out because there was also _another_ problem with try_lock from hard-IRQ context which was fixed in the meantime.

Quoted 2 lines

Would it work for you to update the commit message? Basically I'm fine with the firs sentence but the remaining part is misleading.

Ahh, I understand, okay. Yes, I'll change that first paragraph to incorporate your wording, as:

"""
Taking spinlocks from IRQ context is generally problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. However, a spin_try_lock() is also problematic since another spin_lock() invocation can potentially PI-boost the wrong task, as the spin_try_lock() is invoked from an IRQ-context, so the task on CPU (random task or idle) is not the actual owner.
"""

Jason

#10 lore raw
Quoted 1 line · Jason A. Donenfeld

Hi Sebastian,

Hi Jason,

Quoted 11 lines

Ahh, I understand, okay. Yes, I'll change that first paragraph to incorporate your wording, as:

"""
Taking spinlocks from IRQ context is generally problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. However, a spin_try_lock() is also problematic since another spin_lock() invocation can potentially PI-boost the wrong task, as the spin_try_lock() is invoked from an IRQ-context, so the task on CPU (random task or idle) is not the actual owner.
"""

I didn't expect it that verbose but yes, full ACK from side. Thank you.

Quoted 1 line

Jason

Sebastian

author maintainer
#11 lore raw
In reply to Jason A. Donenfeld

CC +Eric

Quoted 155 lines · Jason A. Donenfeld

Taking spinlocks from IRQ context is problematic for PREEMPT_RT. That is, in part, why we take trylocks instead. But apparently this still trips up various lock dependency analyzers. That seems like a bug in the analyzers that should be fixed, rather than having to change things here.

But maybe there's another reason to change things up: by deferring the crng pre-init loading to the worker, we can use the cryptographic hash function rather than xor, which is perhaps a meaningful difference when considering this data has only been through the relatively weak fast_mix() function.

The biggest downside of this approach is that the pre-init loading is now deferred until later, which means things that need random numbers after interrupts are enabled, but before workqueues are running -- or before this particular worker manages to run -- are going to get into trouble. Hopefully in the real world, this window is rather small, especially since this code won't run until 64 interrupts had occurred.

Cc Dominik Brodowski <[email protected]>
Cc Sebastian Andrzej Siewior <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
---
 drivers/char/random.c | 62 ++++++++++++-------------------------------
 1 file changed, 17 insertions(+), 45 deletions(-)
drivers/char/random.c +17 -46
index 536237a0f073..9fb06fc298d3 100644
@@ -443,10 +443,6 @@ static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS],
  * boot time when it's better to have something there rather than
  * nothing.
  *
- * There are two paths, a slow one and a fast one. The slow one
- * hashes the input along with the current key. The fast one simply
- * xors it in, and should only be used from interrupt context.
- *
  * If account is set, then the crng_init_cnt counter is incremented.
  * This shouldn't be set by functions like add_device_randomness(),
  * where we can't trust the buffer passed to it is guaranteed to be
@@ -455,19 +451,15 @@ static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS],
  * Returns the number of bytes processed from input, which is bounded
  * by CRNG_INIT_CNT_THRESH if account is true.
  */
-static size_t crng_pre_init_inject(const void *input, size_t len,
-                                  bool fast, bool account)
+static size_t crng_pre_init_inject(const void *input, size_t len, bool account)
 {
        static int crng_init_cnt = 0;
+       struct blake2s_state hash;
        unsigned long flags;
 
-       if (fast) {
-               if (!spin_trylock_irqsave(&base_crng.lock, flags))
-                       return 0;
-       } else {
-               spin_lock_irqsave(&base_crng.lock, flags);
-       }
+       blake2s_init(&hash, sizeof(base_crng.key));
 
+       spin_lock_irqsave(&base_crng.lock, flags);
        if (crng_init != 0) {
                spin_unlock_irqrestore(&base_crng.lock, flags);
                return 0;
@@ -476,21 +468,9 @@ static size_t crng_pre_init_inject(const void *input, size_t len,
        if (account)
                len = min_t(size_t, len, CRNG_INIT_CNT_THRESH - crng_init_cnt);
 
-       if (fast) {
-               const u8 *src = input;
-               size_t i;
-
-               for (i = 0; i < len; ++i)
-                       base_crng.key[(crng_init_cnt + i) %
-                                     sizeof(base_crng.key)] ^= src[i];
-       } else {
-               struct blake2s_state hash;
-
-               blake2s_init(&hash, sizeof(base_crng.key));
-               blake2s_update(&hash, base_crng.key, sizeof(base_crng.key));
-               blake2s_update(&hash, input, len);
-               blake2s_final(&hash, base_crng.key);
-       }
+       blake2s_update(&hash, base_crng.key, sizeof(base_crng.key));
+       blake2s_update(&hash, input, len);
+       blake2s_final(&hash, base_crng.key);
 
        if (account) {
                crng_init_cnt += len;
@@ -1040,7 +1020,7 @@ void add_device_randomness(const void *buf, size_t size)
        unsigned long flags;
 
        if (crng_init == 0 && size)
-               crng_pre_init_inject(buf, size, false, false);
+               crng_pre_init_inject(buf, size, false);
 
        spin_lock_irqsave(&input_pool.lock, flags);
        _mix_pool_bytes(buf, size);
@@ -1157,7 +1137,7 @@ void add_hwgenerator_randomness(const void *buffer, size_t count,
                                size_t entropy)
 {
        if (unlikely(crng_init == 0)) {
-               size_t ret = crng_pre_init_inject(buffer, count, false, true);
+               size_t ret = crng_pre_init_inject(buffer, count, true);
                mix_pool_bytes(buffer, ret);
                count -= ret;
                buffer += ret;
@@ -1298,7 +1278,12 @@ static void mix_interrupt_randomness(struct work_struct *work)
        local_irq_enable();
 
        mix_pool_bytes(pool, sizeof(pool));
-       credit_entropy_bits(1);
+
+       if (unlikely(crng_init == 0))
+               crng_pre_init_inject(pool, sizeof(pool), true);
+       else
+               credit_entropy_bits(1);
+
        memzero_explicit(pool, sizeof(pool));
 }
 
@@ -1331,24 +1316,11 @@ void add_interrupt_randomness(int irq)
        fast_mix(fast_pool->pool32);
        new_count = ++fast_pool->count;
 
-       if (unlikely(crng_init == 0)) {
-               if (new_count >= 64 &&
-                   crng_pre_init_inject(fast_pool->pool32, sizeof(fast_pool->pool32),
-                                        true, true) > 0) {
-                       fast_pool->count = 0;
-                       fast_pool->last = now;
-                       if (spin_trylock(&input_pool.lock)) {
-                               _mix_pool_bytes(&fast_pool->pool32, sizeof(fast_pool->pool32));
-                               spin_unlock(&input_pool.lock);
-                       }
-               }
-               return;
-       }
-
        if (new_count & MIX_INFLIGHT)
                return;
 
-       if (new_count < 64 && !time_after(now, fast_pool->last + HZ))
+       if (new_count < 64 && (!time_after(now, fast_pool->last + HZ) ||
+                              unlikely(crng_init == 0)))
                return;
 
        if (unlikely(!fast_pool->mix.func))
--
Quoted 2 lines

2.35.1

FYI, I think you were concerned about those trylocks too. This should make that go away.

Jason