Skip to contentSkip to conversation

random: defer fast pool mixing to worker

PATCH Superseded Jason A. Donenfeld 3 participants 20 messages Feb 11, 2022 – Feb 14, 2022

Subsystems (2)
lore
Share & tools
lore

Jason A. Donenfeld

author maintainer
#0 lore raw

PATCH v5 1/1 random: defer fast pool mixing to worker

On PREEMPT_RT, it's problematic to take spinlocks from hard irq handlers. We can fix this by deferring to a workqueue the dumping of the fast pool into the input pool.

We accomplish this with some careful rules on fast_pool->count:

- When it's incremented to >= 64, we schedule the work.
- If the top bit is set, we never schedule the work, even if >= 64.
- The worker is responsible for setting it back to 0 when it's done.

There are two small issues around using workqueues for this purpose that we work around.

The first issue is that mix_interrupt_randomness() might be migrated to another CPU during CPU hotplug. This issue is rectified by checking that it hasn't been migrated (after disabling migration). If it has been migrated, then we set the count to zero, so that when the CPU comes online again, it can requeue the work. As part of this, we switch to using an atomic_t, so that the increment in the irq handler doesn't wipe out the zeroing if the CPU comes back online while this worker is running.

The second issue is that, though relatively minor in effect, we probably want to make sure we get a consistent view of the pool onto the stack, in case it's interrupted by an irq while reading. To do this, we simply read count before and after the memcpy and make sure they're the same. If they're not, we try again. This isn't a seqlock or anything heavy like that because we're guaranteed to be on the same core as the irq handler interrupting, which means that interruption either happens in full or doesn't at all. The likelihood of actually hitting this is very low, as we're talking about a 2 or 4 word mov.

Cc Sebastian Andrzej Siewior <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Jonathan Neuschäfer <[email protected]>

---
Sebastian - I merged the fixes into the base commit and now I'm resending this. I also incorporated your nit about the acquire/release comments. Let me know if you think this needs further changes.

 drivers/char/random.c | 72 ++++++++++++++++++++++++++++++++++---------
 1 file changed, 58 insertions(+), 14 deletions(-)
drivers/char/random.c +58 -14
index c42c07a7eb56..43c7e6c0a1b7 100644
@@ -1162,10 +1162,12 @@ EXPORT_SYMBOL_GPL(add_bootloader_randomness);
 
 struct fast_pool {
 	unsigned long pool[16 / sizeof(long)];
+	struct work_struct mix;
 	unsigned long last;
+	atomic_t count;
 	u16 reg_idx;
-	u8 count;
 };
+#define FAST_POOL_MIX_INFLIGHT (1U << 31)
 
 /*
  * This is a fast mixing routine used by the interrupt randomness
@@ -1214,12 +1216,57 @@ static u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
 	return *ptr;
 }
 
+static void mix_interrupt_randomness(struct work_struct *work)
+{
+	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
+	unsigned long pool[ARRAY_SIZE(fast_pool->pool)];
+	unsigned int count_snapshot;
+	size_t i;
+
+	/* Check to see if we're running on the wrong CPU due to hotplug. */
+	migrate_disable();
+	if (fast_pool != this_cpu_ptr(&irq_randomness)) {
+		migrate_enable();
+		/*
+		 * If we are unlucky enough to have been moved to another CPU,
+		 * then we set our count to zero atomically so that when the
+		 * CPU comes back online, it can enqueue work again. The
+		 * _release here pairs with the atomic_inc_return_acquire in
+		 * add_interrupt_randomness().
+		 */
+		atomic_set_release(&fast_pool->count, 0);
+		return;
+	}
+
+	/*
+	 * Copy the pool to the stack so that the mixer always has a
+	 * consistent view. It's extremely unlikely but possible that
+	 * this 2 or 4 word read is interrupted by an irq, but in case
+	 * it is, we double check that count stays the same.
+	 */
+	do {
+		count_snapshot = (unsigned int)atomic_read(&fast_pool->count);
+		for (i = 0; i < ARRAY_SIZE(pool); ++i)
+			pool[i] = READ_ONCE(fast_pool->pool[i]);
+	} while (count_snapshot != (unsigned int)atomic_read(&fast_pool->count));
+
+	/* We take care to zero out the count only after we're done reading the pool. */
+	atomic_set(&fast_pool->count, 0);
+	fast_pool->last = jiffies;
+	migrate_enable();
+
+	mix_pool_bytes(pool, sizeof(pool));
+	credit_entropy_bits(1);
+	memzero_explicit(pool, sizeof(pool));
+}
+
 void add_interrupt_randomness(int irq)
 {
 	struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness);
 	struct pt_regs *regs = get_irq_regs();
 	unsigned long now = jiffies;
 	cycles_t cycles = random_get_entropy();
+	unsigned int new_count;
 
 	if (cycles == 0)
 		cycles = get_reg(fast_pool, regs);
@@ -1235,12 +1282,13 @@ void add_interrupt_randomness(int irq)
 	}
 
 	fast_mix((u32 *)fast_pool->pool);
-	++fast_pool->count;
+	/* The _acquire here pairs with the atomic_set_release in mix_interrupt_randomness(). */
+	new_count = (unsigned int)atomic_inc_return_acquire(&fast_pool->count);
 
 	if (unlikely(crng_init == 0)) {
-		if (fast_pool->count >= 64 &&
+		if (new_count >= 64 &&
 		    crng_fast_load(fast_pool->pool, sizeof(fast_pool->pool)) > 0) {
-			fast_pool->count = 0;
+			atomic_set(&fast_pool->count, 0);
 			fast_pool->last = now;
 
 			/*
@@ -1254,20 +1302,16 @@ void add_interrupt_randomness(int irq)
 		return;
 	}
 
-	if ((fast_pool->count < 64) && !time_after(now, fast_pool->last + HZ))
+	if (new_count & FAST_POOL_MIX_INFLIGHT)
 		return;
 
-	if (!spin_trylock(&input_pool.lock))
+	if (new_count < 64 && !time_after(now, fast_pool->last + HZ))
 		return;
 
-	fast_pool->last = now;
-	_mix_pool_bytes(&fast_pool->pool, sizeof(fast_pool->pool));
-	spin_unlock(&input_pool.lock);
-
-	fast_pool->count = 0;
-
-	/* Award one bit for the contents of the fast pool. */
-	credit_entropy_bits(1);
+	if (unlikely(!fast_pool->mix.func))
+		INIT_WORK(&fast_pool->mix, mix_interrupt_randomness);
+	atomic_or(FAST_POOL_MIX_INFLIGHT, &fast_pool->count);
+	queue_work_on(raw_smp_processor_id(), system_highpri_wq, &fast_pool->mix);
 }
 EXPORT_SYMBOL_GPL(add_interrupt_randomness);
 
Signature · 1 line
2.35.0
#1 lore raw

On 2022-02-11 14:08:07 [+0100], Jason A. Donenfeld wrote:
…

Quoted 23 lines
drivers/char/random.c +23 -0
+static void mix_interrupt_randomness(struct work_struct *work)
+{
+	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
+	unsigned long pool[ARRAY_SIZE(fast_pool->pool)];
+	unsigned int count_snapshot;
+	size_t i;
+
+	/* Check to see if we're running on the wrong CPU due to hotplug. */
+	migrate_disable();
+	if (fast_pool != this_cpu_ptr(&irq_randomness)) {
+		migrate_enable();
+		/*
+		 * If we are unlucky enough to have been moved to another CPU,
+		 * then we set our count to zero atomically so that when the
+		 * CPU comes back online, it can enqueue work again. The
+		 * _release here pairs with the atomic_inc_return_acquire in
+		 * add_interrupt_randomness().
+		 */
+		atomic_set_release(&fast_pool->count, 0);
+		return;
+	}
+
+	/*

drivers/char/random.c static u32 get_reg(struct fast_pool *f, struct pt_regs *regs) · line 1251

Quoted 10 lines
drivers/char/random.c +10 -0
+	 * Copy the pool to the stack so that the mixer always has a
+	 * consistent view. It's extremely unlikely but possible that
+	 * this 2 or 4 word read is interrupted by an irq, but in case
+	 * it is, we double check that count stays the same.
+	 */
+	do {
+		count_snapshot = (unsigned int)atomic_read(&fast_pool->count);
+		for (i = 0; i < ARRAY_SIZE(pool); ++i)
+			pool[i] = READ_ONCE(fast_pool->pool[i]);
+	} while (count_snapshot != (unsigned int)atomic_read(&fast_pool->count));

Which what I wrote in the last mail, can't we just have a cmpxchg loop here?

Sebastian

author maintainer
#2 lore raw

PATCH v6 1/1 random: defer fast pool mixing to worker

On PREEMPT_RT, it's problematic to take spinlocks from hard irq handlers. We can fix this by deferring to a workqueue the dumping of the fast pool into the input pool.

We accomplish this with some careful rules on fast_pool->count:

- When it's incremented to >= 64, we schedule the work.
- If the top bit is set, we never schedule the work, even if >= 64.
- The worker is responsible for setting it back to 0 when it's done.

There are two small issues around using workqueues for this purpose that we work around.

The first issue is that mix_interrupt_randomness() might be migrated to another CPU during CPU hotplug. This issue is rectified by checking that it hasn't been migrated (after disabling migration). If it has been migrated, then we set the count to zero, so that when the CPU comes online again, it can requeue the work. As part of this, we switch to using an atomic_t, so that the increment in the irq handler doesn't wipe out the zeroing if the CPU comes back online while this worker is running.

The second issue is that, though relatively minor in effect, we probably want to make sure we get a consistent view of the pool onto the stack, in case it's interrupted by an irq while reading. To do this, we simply read count before and after the memcpy and make sure they're the same. If they're not, we try again. This isn't a seqlock or anything heavy like that because we're guaranteed to be on the same core as the irq handler interrupting, which means that interruption either happens in full or doesn't at all. The likelihood of actually hitting this is very low, as we're talking about a 2 or 4 word mov.

Cc Sebastian Andrzej Siewior <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Jonathan Neuschäfer <[email protected]>

---
Sebastian - this now uses cmpxchg as you suggested, and has comments on its various atomic uses. I think we should be finally good to go! PTAL. Thanks again for looking at this hairy patch.

 drivers/char/random.c | 73 ++++++++++++++++++++++++++++++++++---------
 1 file changed, 59 insertions(+), 14 deletions(-)
drivers/char/random.c +59 -14
index c42c07a7eb56..20b11a4b6559 100644
@@ -1162,9 +1162,10 @@ EXPORT_SYMBOL_GPL(add_bootloader_randomness);
 
 struct fast_pool {
 	unsigned long pool[16 / sizeof(long)];
+	struct work_struct mix;
 	unsigned long last;
+	atomic_t count;
 	u16 reg_idx;
-	u8 count;
 };
 
 /*
@@ -1214,12 +1215,59 @@ static u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
 	return *ptr;
 }
 
+static void mix_interrupt_randomness(struct work_struct *work)
+{
+	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
+	unsigned long pool[ARRAY_SIZE(fast_pool->pool)];
+	int count;
+
+	/* Check to see if we're running on the wrong CPU due to hotplug. */
+	migrate_disable();
+	if (fast_pool != this_cpu_ptr(&irq_randomness)) {
+		migrate_enable();
+		/*
+		 * If we are unlucky enough to have been moved to another CPU,
+		 * then we set our count to zero atomically so that when the
+		 * CPU comes back online, it can enqueue work again. The
+		 * _release here pairs with the atomic_inc_return_acquire in
+		 * add_interrupt_randomness().
+		 */
+		atomic_set_release(&fast_pool->count, 0);
+		return;
+	}
+
+	/*
+	 * Copy the pool to the stack so that the mixer always has a
+	 * consistent view. It's extremely unlikely but possible that
+	 * this 2 or 4 word read is interrupted by an irq, but in case
+	 * it is, we double check that count stays the same.
+	 *
+	 * We set the count to 0 so that irqs can immediately begin to
+	 * accumulate again after. Since any possible interruptions
+	 * at this stage are guaranteed to be on the same CPU, we can
+	 * use cmpxchg_relaxed.
+	 */
+	count = atomic_read(&fast_pool->count);
+	do {
+		memcpy(pool, fast_pool->pool, sizeof(pool));
+	} while (atomic_try_cmpxchg_relaxed(&fast_pool->count, &count, 0));
+
+	fast_pool->last = jiffies;
+	migrate_enable();
+
+	mix_pool_bytes(pool, sizeof(pool));
+	credit_entropy_bits(1);
+	memzero_explicit(pool, sizeof(pool));
+}
+
 void add_interrupt_randomness(int irq)
 {
+	enum { MIX_INFLIGHT = 1U << 31 };
 	struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness);
 	struct pt_regs *regs = get_irq_regs();
 	unsigned long now = jiffies;
 	cycles_t cycles = random_get_entropy();
+	unsigned int new_count;
 
 	if (cycles == 0)
 		cycles = get_reg(fast_pool, regs);
@@ -1235,12 +1283,13 @@ void add_interrupt_randomness(int irq)
 	}
 
 	fast_mix((u32 *)fast_pool->pool);
-	++fast_pool->count;
+	/* The _acquire here pairs with the atomic_set_release in mix_interrupt_randomness(). */
+	new_count = (unsigned int)atomic_inc_return_acquire(&fast_pool->count);
 
 	if (unlikely(crng_init == 0)) {
-		if (fast_pool->count >= 64 &&
+		if (new_count >= 64 &&
 		    crng_fast_load(fast_pool->pool, sizeof(fast_pool->pool)) > 0) {
-			fast_pool->count = 0;
+			atomic_set(&fast_pool->count, 0);
 			fast_pool->last = now;
 
 			/*
@@ -1254,20 +1303,16 @@ void add_interrupt_randomness(int irq)
 		return;
 	}
 
-	if ((fast_pool->count < 64) && !time_after(now, fast_pool->last + HZ))
+	if (new_count & MIX_INFLIGHT)
 		return;
 
-	if (!spin_trylock(&input_pool.lock))
+	if (new_count < 64 && !time_after(now, fast_pool->last + HZ))
 		return;
 
-	fast_pool->last = now;
-	_mix_pool_bytes(&fast_pool->pool, sizeof(fast_pool->pool));
-	spin_unlock(&input_pool.lock);
-
-	fast_pool->count = 0;
-
-	/* Award one bit for the contents of the fast pool. */
-	credit_entropy_bits(1);
+	if (unlikely(!fast_pool->mix.func))
+		INIT_WORK(&fast_pool->mix, mix_interrupt_randomness);
+	atomic_or(MIX_INFLIGHT, &fast_pool->count);
+	queue_work_on(raw_smp_processor_id(), system_highpri_wq, &fast_pool->mix);
 }
 EXPORT_SYMBOL_GPL(add_interrupt_randomness);
 
Signature · 1 line
2.35.0
#3 lore raw
Quoted 10 lines · Jason A. Donenfeld
drivers/char/random.c +2 -0
index c42c07a7eb56..20b11a4b6559 100644
@@ -1214,12 +1215,59 @@ static u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
 	return *ptr;
 }
 
+static void mix_interrupt_randomness(struct work_struct *work)
+{

drivers/char/random.c static u32 get_reg(struct fast_pool *f, struct pt_regs *regs) · line 1229

Quoted 10 lines
drivers/char/random.c +10 -0
+	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
+	unsigned long pool[ARRAY_SIZE(fast_pool->pool)];
+	int count;
+
+	/* Check to see if we're running on the wrong CPU due to hotplug. */
+	migrate_disable();
+	if (fast_pool != this_cpu_ptr(&irq_randomness)) {
+		migrate_enable();
+		/*
+		 * If we are unlucky enough to have been moved to another CPU,

+ "during CPU hotplug while the CPU was shutdown". It should not look like the worker can be migrated on system without CPU-hotplug involved.

Quoted 14 lines
drivers/char/random.c +14 -0
+		 * then we set our count to zero atomically so that when the
+		 * CPU comes back online, it can enqueue work again. The
+		 * _release here pairs with the atomic_inc_return_acquire in
+		 * add_interrupt_randomness().
+		 */
+		atomic_set_release(&fast_pool->count, 0);
+		return;
+	}
+
+	/*
+	 * Copy the pool to the stack so that the mixer always has a
+	 * consistent view. It's extremely unlikely but possible that
+	 * this 2 or 4 word read is interrupted by an irq, but in case
+	 * it is, we double check that count stays the same.

drivers/char/random.c static u32 get_reg(struct fast_pool *f, struct pt_regs *regs) · line 1253

Quoted 10 lines
drivers/char/random.c +10 -0
+	 *
+	 * We set the count to 0 so that irqs can immediately begin to
+	 * accumulate again after. Since any possible interruptions
+	 * at this stage are guaranteed to be on the same CPU, we can
+	 * use cmpxchg_relaxed.
+	 */
+	count = atomic_read(&fast_pool->count);
+	do {
+		memcpy(pool, fast_pool->pool, sizeof(pool));
+	} while (atomic_try_cmpxchg_relaxed(&fast_pool->count, &count, 0));

I *think* we could drop that "fast_pool != this_cpu_ptr(&irq_randomness)" check at the top since that cmpxchg will save us and redo the loop. But if I remember correctly you worried about fast_pool->pool being modified (which is only a corner case if we are on the other CPU while the orig CPU is back again). Either way, it would be random and we would not consume more entropy.

So if we have to keep this then please swap that migrate_disable() with local_irq_disable(). Otherwise PeterZ will yell at me.

Quoted 8 lines
drivers/char/random.c +8 -0
+	fast_pool->last = jiffies;
+	migrate_enable();
+
+	mix_pool_bytes(pool, sizeof(pool));
+	credit_entropy_bits(1);
+	memzero_explicit(pool, sizeof(pool));
+}
+

…

Quoted 5 lines
drivers/char/random.c +0 -1
@@ -1235,12 +1283,13 @@ void add_interrupt_randomness(int irq)
 	}
 
 	fast_mix((u32 *)fast_pool->pool);
-	++fast_pool->count;

drivers/char/random.c void add_interrupt_randomness(int irq) · line 1293

Quoted 10 lines
drivers/char/random.c +4 -2
+	/* The _acquire here pairs with the atomic_set_release in mix_interrupt_randomness(). */
+	new_count = (unsigned int)atomic_inc_return_acquire(&fast_pool->count);
 
 	if (unlikely(crng_init == 0)) {
-		if (fast_pool->count >= 64 &&
+		if (new_count >= 64 &&
 		    crng_fast_load(fast_pool->pool, sizeof(fast_pool->pool)) > 0) {
-			fast_pool->count = 0;
+			atomic_set(&fast_pool->count, 0);
 			fast_pool->last = now;

I'm fine if we keep this as is for now.
What do we do here vs RT? I suggested this
https://git.kernel.org/pub/scm/linux/kernel/git/rt/linux-rt-devel.git/commit/?id=a2d2d54409481aa23a3e11ab9559a843e36a79ec

Is this doable?

Sebastian

author maintainer
#4 lore raw

Hi Sebastian,

Quoted 10 lines · Sebastian Andrzej Siewior

drivers/char/random.c static u32 get_reg(struct fast_pool *f, struct pt_regs *regs) · line 1229

Quoted 7 lines
drivers/char/random.c +7 -0
+
+     /* Check to see if we're running on the wrong CPU due to hotplug. */
+     migrate_disable();
+     if (fast_pool != this_cpu_ptr(&irq_randomness)) {
+             migrate_enable();
+             /*
+              * If we are unlucky enough to have been moved to another CPU,

+ "during CPU hotplug while the CPU was shutdown". It should not look like the worker can be migrated on system without CPU-hotplug involved.

Will adjust comment.

Quoted 6 lines

I *think* we could drop that "fast_pool != this_cpu_ptr(&irq_randomness)" check at the top since that cmpxchg will save us and redo the loop. But if I remember correctly you worried about fast_pool->pool being modified (which is only a corner case if we are on the other CPU while the orig CPU is back again). Either way, it would be random and we would not consume more entropy.

No, we cannot, and "it's all random anyway so who cares if we corrupt things!" is not rigorous, as entropy may actually be thrown away as it's moved between words on each mix. If we're not running on the same CPU, one CPU can corrupt the other's view of fast pool before updating count. We must keep this.

Quoted 2 lines

So if we have to keep this then please swap that migrate_disable() with local_irq_disable(). Otherwise PeterZ will yell at me.

Okay, I'll do that then, and then in the process get rid of the cmpxchg loop since it's no longer required.

Quoted 8 lines

drivers/char/random.c void add_interrupt_randomness(int irq) · line 1293

Quoted 7 lines
      if (unlikely(crng_init == 0)) {
drivers/char/random.c +2 -2
-             if (fast_pool->count >= 64 &&
+             if (new_count >= 64 &&
                  crng_fast_load(fast_pool->pool, sizeof(fast_pool->pool)) > 0) {
-                     fast_pool->count = 0;
+                     atomic_set(&fast_pool->count, 0);
                      fast_pool->last = now;
Quoted 5 lines

I'm fine if we keep this as is for now.
What do we do here vs RT? I suggested this
https://git.kernel.org/pub/scm/linux/kernel/git/rt/linux-rt-devel.git/commit/?id=a2d2d54409481aa23a3e11ab9559a843e36a79ec

Is this doable?

It might be, but last time I checked it seemed problematic. As I mentioned in an earlier thread, I'll take a look again at that next week after this patch here settles. Haven't forgotten.

v+1 coming up with irqs disabled.

Jason

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

Hi Sebastian,

Hi Jason,

Quoted 7 lines
Quoted 6 lines

I *think* we could drop that "fast_pool != this_cpu_ptr(&irq_randomness)" check at the top since that cmpxchg will save us and redo the loop. But if I remember correctly you worried about fast_pool->pool being modified (which is only a corner case if we are on the other CPU while the orig CPU is back again). Either way, it would be random and we would not consume more entropy.

Quoted 5 lines

No, we cannot, and "it's all random anyway so who cares if we corrupt things!" is not rigorous, as entropy may actually be thrown away as it's moved between words on each mix. If we're not running on the same CPU, one CPU can corrupt the other's view of fast pool before updating count. We must keep this.

Okay, I assumed something like that.

Quoted 5 lines
Quoted 2 lines

So if we have to keep this then please swap that migrate_disable() with local_irq_disable(). Otherwise PeterZ will yell at me.

Okay, I'll do that then, and then in the process get rid of the cmpxchg loop since it's no longer required.

So the only reason why we have that atomic_t is for rare case where run on the remote CPU and need to remove the upper bit in the counter?

Quoted 12 lines
Quoted 12 lines

drivers/char/random.c void add_interrupt_randomness(int irq) · line 1293

Quoted 7 lines
      if (unlikely(crng_init == 0)) {
drivers/char/random.c +2 -2
-             if (fast_pool->count >= 64 &&
+             if (new_count >= 64 &&
                  crng_fast_load(fast_pool->pool, sizeof(fast_pool->pool)) > 0) {
-                     fast_pool->count = 0;
+                     atomic_set(&fast_pool->count, 0);
                      fast_pool->last = now;

I'm fine if we keep this as is for now.
What do we do here vs RT? I suggested this
https://git.kernel.org/pub/scm/linux/kernel/git/rt/linux-rt-devel.git/commit/?id=a2d2d54409481aa23a3e11ab9559a843e36a79ec

Quoted 5 lines
Quoted 1 line

Is this doable?

It might be, but last time I checked it seemed problematic. As I mentioned in an earlier thread, I'll take a look again at that next week after this patch here settles. Haven't forgotten.

Ah, cheers.

Quoted 3 lines

v+1 coming up with irqs disabled.

Jason

Sebastian

author maintainer
#6 lore raw

Hi Sebastian,

Quoted 5 lines · Sebastian Andrzej Siewior
Quoted 2 lines

Okay, I'll do that then, and then in the process get rid of the cmpxchg loop since it's no longer required.

So the only reason why we have that atomic_t is for rare case where run on the remote CPU and need to remove the upper bit in the counter?

Yes. That's the only remaining reason. Annoying, but whatareyagonnado?

Jason

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

Hi Sebastian,

Hi Jason,

Quoted 9 lines
Quoted 5 lines · Sebastian Andrzej Siewior
Quoted 2 lines

Okay, I'll do that then, and then in the process get rid of the cmpxchg loop since it's no longer required.

So the only reason why we have that atomic_t is for rare case where run on the remote CPU and need to remove the upper bit in the counter?

Yes. That's the only remaining reason. Annoying, but whatareyagonnado?

A CPU hotplug notifier which removes unconditionally that bit when the CPU goes down or sets it to 0.
We can keep it as it. Just an idea for later maybe ;)

Quoted 1 line

Jason

Sebastian

author maintainer
#8 lore raw
Quoted 3 lines · Sebastian Andrzej Siewior

A CPU hotplug notifier which removes unconditionally that bit when the CPU goes down or sets it to 0.
We can keep it as it. Just an idea for later maybe ;)

I looked into it and it seemed like the plumbing was kind of miserable for that. If you want to take a stab, though, that might be an okay followup patch, and then we can assess atomics vs notifier. I think notifier will wind up being a lot clunkier, though.

Sounds like we should be all set for the v7 I sent out?

Jason

#9 lore raw
Quoted 6 lines · Jason A. Donenfeld
Quoted 3 lines · Sebastian Andrzej Siewior

A CPU hotplug notifier which removes unconditionally that bit when the CPU goes down or sets it to 0.
We can keep it as it. Just an idea for later maybe ;)

Quoted 6 lines

I looked into it and it seemed like the plumbing was kind of miserable for that. If you want to take a stab, though, that might be an okay followup patch, and then we can assess atomics vs notifier. I think notifier will wind up being a lot clunkier, though.

Sounds like we should be all set for the v7 I sent out?

Sure. I can do the CPU-HP notifier later one once we are done with everything. I acked the v7, don't see a road block.

Quoted 1 line

Jason

Sebastian

author maintainer
#10 lore raw

Hey Sebastian,

Quoted 2 lines · Sebastian Andrzej Siewior

Sure. I can do the CPU-HP notifier later one once we are done with everything. I acked the v7, don't see a road block.

I've been running this over the weekend and performance is generally okay.

# perf top --symbols $(objdump -t
/usr/src/linux/drivers/char/random.o|fgrep 'F .text'|awk '{print
$6}'|tr '\n' ,) -F max -g

One thing I noticed though was that add_interrupt_randomness spends most of its time on:

    lock   xadd   %eax,0x38(%rbp)

So, as expected, those atomics really need to go. Indeed we might be best off with the CPU hotplug notifier for setting the count back to zero.

Do you want to prepare a patch for this? Or should I take a stab at it?

Jason

author maintainer
#11 lore raw
Quoted 16 lines · Jason A. Donenfeld

Hey Sebastian,

Quoted 2 lines · Sebastian Andrzej Siewior

Sure. I can do the CPU-HP notifier later one once we are done with everything. I acked the v7, don't see a road block.

I've been running this over the weekend and performance is generally okay.

# perf top --symbols $(objdump -t
/usr/src/linux/drivers/char/random.o|fgrep 'F .text'|awk '{print
$6}'|tr '\n' ,) -F max -g

One thing I noticed though was that add_interrupt_randomness spends most of its time on:

Quoted 7 lines
    lock   xadd   %eax,0x38(%rbp)

So, as expected, those atomics really need to go. Indeed we might be best off with the CPU hotplug notifier for setting the count back to zero.

Do you want to prepare a patch for this? Or should I take a stab at it?

FYI, I was overwhelmed with a compulsion to try doing it myself and posted that here
https://lore.kernel.org/lkml/[email protected]/
which is now pending your review.

author maintainer
#12 lore raw
In reply to Sebastian Andrzej Siewior
Quoted 10 lines · Sebastian Andrzej Siewior
Quoted 8 lines
Quoted 4 lines

What do we do here vs RT? I suggested this
https://git.kernel.org/pub/scm/linux/kernel/git/rt/linux-rt-devel.git/commit/?id=a2d2d54409481aa23a3e11ab9559a843e36a79ec

Is this doable?

It might be, but last time I checked it seemed problematic. As I mentioned in an earlier thread, I'll take a look again at that next week after this patch here settles. Haven't forgotten.

Ah, cheers.

I started looking at this and came up with this draft with questions:
https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?h=jd/no-irq-trylocks

Some research remains...

Jason

#13 lore raw
Quoted 2 lines · Jason A. Donenfeld

I started looking at this and came up with this draft with questions:
https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?h=jd/no-irq-trylocks

to
| - Does anything anywhere call get_random_xx() before the worker has a
| chance to run?

Once you queue a work item I don't think that the scheduler needs to put it on the CPU right away. It may have already have other tasks waiting including some with a RT priority.
Also, the lock is irqsave() so they can be users in an interrupt handler. I remember the original reason why I made it irqsave is because something did kmalloc() and SLUB somehow asked for random bits.

Quoted 3 lines

Some research remains...

Jason

Sebastian

author maintainer
#14 lore raw
Quoted 10 lines · Sebastian Andrzej Siewior

to
| - Does anything anywhere call get_random_xx() before the worker has a
| chance to run?

Once you queue a work item I don't think that the scheduler needs to put it on the CPU right away. It may have already have other tasks waiting including some with a RT priority.
Also, the lock is irqsave() so they can be users in an interrupt handler. I remember the original reason why I made it irqsave is because something did kmalloc() and SLUB somehow asked for random bits.

Right. So there are two sides of the questions: 1) how bad is this actual race, and are there any drivers that do regularly get bit by this? 2) There's a largeish window between workqueue_init_early() setting up the system highprio workqueue, and workqueue_init() enabling queued workers to actually run. Interrupts also get enabled in the interim. Does anything get bit by that window?

Jason

#15 lore raw
Quoted 12 lines · Jason A. Donenfeld
Quoted 10 lines · Sebastian Andrzej Siewior

to
| - Does anything anywhere call get_random_xx() before the worker has a
| chance to run?

Once you queue a work item I don't think that the scheduler needs to put it on the CPU right away. It may have already have other tasks waiting including some with a RT priority.
Also, the lock is irqsave() so they can be users in an interrupt handler. I remember the original reason why I made it irqsave is because something did kmalloc() and SLUB somehow asked for random bits.

Quoted 6 lines

Right. So there are two sides of the questions: 1) how bad is this actual race, and are there any drivers that do regularly get bit by this? 2) There's a largeish window between workqueue_init_early() setting up the system highprio workqueue, and workqueue_init() enabling queued workers to actually run. Interrupts also get enabled in the interim. Does anything get bit by that window?

This is only important during boot-up, right? Otherwise it just extracts entropy from the pool.
I posted numbers earlier on where the work go scheduled and the three or four interrupts came in before the work-item was scheduled. I could send you the diff if you want to up it on some machines.

Quoted 1 line

Jason

Sebastian

author maintainer
#16 lore raw
Quoted 14 lines · Sebastian Andrzej Siewior
Quoted 12 lines · Jason A. Donenfeld
Quoted 10 lines · Sebastian Andrzej Siewior

to
| - Does anything anywhere call get_random_xx() before the worker has a
| chance to run?

Once you queue a work item I don't think that the scheduler needs to put it on the CPU right away. It may have already have other tasks waiting including some with a RT priority.
Also, the lock is irqsave() so they can be users in an interrupt handler. I remember the original reason why I made it irqsave is because something did kmalloc() and SLUB somehow asked for random bits.

Quoted 8 lines
Quoted 6 lines

Right. So there are two sides of the questions: 1) how bad is this actual race, and are there any drivers that do regularly get bit by this? 2) There's a largeish window between workqueue_init_early() setting up the system highprio workqueue, and workqueue_init() enabling queued workers to actually run. Interrupts also get enabled in the interim. Does anything get bit by that window?

This is only important during boot-up, right?

Right. This is a pre-init window only. But a bunch of things are done pre-init -- siphash secret keys, aslr seeds, and so forth.

author maintainer
#17 lore raw

PATCH v7 1/1 random: defer fast pool mixing to worker

In reply to Jason A. Donenfeld

On PREEMPT_RT, it's problematic to take spinlocks from hard irq handlers. We can fix this by deferring to a workqueue the dumping of the fast pool into the input pool.

We accomplish this with some careful rules on fast_pool->count:

- When it's incremented to >= 64, we schedule the work.
- If the top bit is set, we never schedule the work, even if >= 64.
- The worker is responsible for setting it back to 0 when it's done.

There are two small issues around using workqueues for this purpose that we work around.

The first issue is that mix_interrupt_randomness() might be migrated to another CPU during CPU hotplug. This issue is rectified by checking that it hasn't been migrated (after disabling irqs). If it has been migrated, then we set the count to zero, so that when the CPU comes online again, it can requeue the work. As part of this, we switch to using an atomic_t, so that the increment in the irq handler doesn't wipe out the zeroing if the CPU comes back online while this worker is running.

The second issue is that, though relatively minor in effect, we probably want to make sure we get a consistent view of the pool onto the stack, in case it's interrupted by an irq while reading. To do this, we don't reenable irqs until after the copy. There are only 18 instructions between the cli and sti, so this is a pretty tiny window.

Cc Sebastian Andrzej Siewior <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Jonathan Neuschäfer <[email protected]>

---
Sebastian - as requested, we now disable irqs for a very short 18 instructions rather than fishing into migrate_disable() and upsetting PeterZ. Might this be the lucky patch? -Jason

 drivers/char/random.c | 63 +++++++++++++++++++++++++++++++++----------
 1 file changed, 49 insertions(+), 14 deletions(-)
drivers/char/random.c +49 -14
index 1dbf21c02b40..b921127ea693 100644
@@ -1162,9 +1162,10 @@ EXPORT_SYMBOL_GPL(add_bootloader_randomness);
 
 struct fast_pool {
 	unsigned long pool[16 / sizeof(long)];
+	struct work_struct mix;
 	unsigned long last;
+	atomic_t count;
 	u16 reg_idx;
-	u8 count;
 };
 
 /*
@@ -1214,12 +1215,49 @@ static u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
 	return *ptr;
 }
 
+static void mix_interrupt_randomness(struct work_struct *work)
+{
+	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
+	unsigned long pool[ARRAY_SIZE(fast_pool->pool)];
+
+	/* Check to see if we're running on the wrong CPU due to hotplug. */
+	local_irq_disable();
+	if (fast_pool != this_cpu_ptr(&irq_randomness)) {
+		local_irq_enable();
+		/*
+		 * If we are unlucky enough to have been moved to another CPU,
+		 * during CPU hotplug while the CPU was shutdown then we set
+		 * our count to zero atomically so that when the CPU comes
+		 * back online, it can enqueue work again. The _release here
+		 * pairs with the atomic_inc_return_acquire in
+		 * add_interrupt_randomness().
+		 */
+		atomic_set_release(&fast_pool->count, 0);
+		return;
+	}
+
+	/*
+	 * Copy the pool to the stack so that the mixer always has a
+	 * consistent view, before we reenable irqs again.
+	 */
+	memcpy(pool, fast_pool->pool, sizeof(pool));
+	atomic_set(&fast_pool->count, 0);
+	fast_pool->last = jiffies;
+	local_irq_enable();
+
+	mix_pool_bytes(pool, sizeof(pool));
+	credit_entropy_bits(1);
+	memzero_explicit(pool, sizeof(pool));
+}
+
 void add_interrupt_randomness(int irq)
 {
+	enum { MIX_INFLIGHT = 1U << 31 };
 	struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness);
 	struct pt_regs *regs = get_irq_regs();
 	unsigned long now = jiffies;
 	cycles_t cycles = random_get_entropy();
+	unsigned int new_count;
 
 	if (cycles == 0)
 		cycles = get_reg(fast_pool, regs);
@@ -1235,12 +1273,13 @@ void add_interrupt_randomness(int irq)
 	}
 
 	fast_mix((u32 *)fast_pool->pool);
-	++fast_pool->count;
+	/* The _acquire here pairs with the atomic_set_release in mix_interrupt_randomness(). */
+	new_count = (unsigned int)atomic_inc_return_acquire(&fast_pool->count);
 
 	if (unlikely(crng_init == 0)) {
-		if (fast_pool->count >= 64 &&
+		if (new_count >= 64 &&
 		    crng_fast_load(fast_pool->pool, sizeof(fast_pool->pool)) > 0) {
-			fast_pool->count = 0;
+			atomic_set(&fast_pool->count, 0);
 			fast_pool->last = now;
 
 			/*
@@ -1254,20 +1293,16 @@ void add_interrupt_randomness(int irq)
 		return;
 	}
 
-	if ((fast_pool->count < 64) && !time_after(now, fast_pool->last + HZ))
+	if (new_count & MIX_INFLIGHT)
 		return;
 
-	if (!spin_trylock(&input_pool.lock))
+	if (new_count < 64 && !time_after(now, fast_pool->last + HZ))
 		return;
 
-	fast_pool->last = now;
-	_mix_pool_bytes(&fast_pool->pool, sizeof(fast_pool->pool));
-	spin_unlock(&input_pool.lock);
-
-	fast_pool->count = 0;
-
-	/* Award one bit for the contents of the fast pool. */
-	credit_entropy_bits(1);
+	if (unlikely(!fast_pool->mix.func))
+		INIT_WORK(&fast_pool->mix, mix_interrupt_randomness);
+	atomic_or(MIX_INFLIGHT, &fast_pool->count);
+	queue_work_on(raw_smp_processor_id(), system_highpri_wq, &fast_pool->mix);
 }
 EXPORT_SYMBOL_GPL(add_interrupt_randomness);
 
Signature · 1 line
2.35.0
Reviewed-by on v7 1/1
#18 lore raw
Quoted 35 lines · Jason A. Donenfeld

On PREEMPT_RT, it's problematic to take spinlocks from hard irq handlers. We can fix this by deferring to a workqueue the dumping of the fast pool into the input pool.

We accomplish this with some careful rules on fast_pool->count:

- When it's incremented to >= 64, we schedule the work.
- If the top bit is set, we never schedule the work, even if >= 64.
- The worker is responsible for setting it back to 0 when it's done.

There are two small issues around using workqueues for this purpose that we work around.

The first issue is that mix_interrupt_randomness() might be migrated to another CPU during CPU hotplug. This issue is rectified by checking that it hasn't been migrated (after disabling irqs). If it has been migrated, then we set the count to zero, so that when the CPU comes online again, it can requeue the work. As part of this, we switch to using an atomic_t, so that the increment in the irq handler doesn't wipe out the zeroing if the CPU comes back online while this worker is running.

The second issue is that, though relatively minor in effect, we probably want to make sure we get a consistent view of the pool onto the stack, in case it's interrupted by an irq while reading. To do this, we don't reenable irqs until after the copy. There are only 18 instructions between the cli and sti, so this is a pretty tiny window.

Cc Sebastian Andrzej Siewior <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Jonathan Neuschäfer <[email protected]>
Quoted 4 lines

---
Sebastian - as requested, we now disable irqs for a very short 18 instructions rather than fishing into migrate_disable() and upsetting PeterZ. Might this be the lucky patch? -Jason

I think this might be the lucky patch.

Sultan

Acked-by on v7 1/1
#19 lore raw
In reply to Jason A. Donenfeld
Quoted 27 lines · Jason A. Donenfeld

On PREEMPT_RT, it's problematic to take spinlocks from hard irq handlers. We can fix this by deferring to a workqueue the dumping of the fast pool into the input pool.

We accomplish this with some careful rules on fast_pool->count:

- When it's incremented to >= 64, we schedule the work.
- If the top bit is set, we never schedule the work, even if >= 64.
- The worker is responsible for setting it back to 0 when it's done.

There are two small issues around using workqueues for this purpose that we work around.

The first issue is that mix_interrupt_randomness() might be migrated to another CPU during CPU hotplug. This issue is rectified by checking that it hasn't been migrated (after disabling irqs). If it has been migrated, then we set the count to zero, so that when the CPU comes online again, it can requeue the work. As part of this, we switch to using an atomic_t, so that the increment in the irq handler doesn't wipe out the zeroing if the CPU comes back online while this worker is running.

The second issue is that, though relatively minor in effect, we probably want to make sure we get a consistent view of the pool onto the stack, in case it's interrupted by an irq while reading. To do this, we don't reenable irqs until after the copy. There are only 18 instructions between the cli and sti, so this is a pretty tiny window.

Quoted 8 lines
Cc Sebastian Andrzej Siewior <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Theodore Ts'o <[email protected]>
Cc Sultan Alsawaf <[email protected]>
Cc Jonathan Neuschäfer <[email protected]>
Quoted 4 lines

---
Sebastian - as requested, we now disable irqs for a very short 18 instructions rather than fishing into migrate_disable() and upsetting PeterZ. Might this be the lucky patch? -Jason

I think we good. I'm not going to comment on the 90 char wide comment :)

Sebastian