[PATCH v4 0/2] random: PREEMPT_RT fixes

[PATCH v4 0/2] random: PREEMPT_RT fixes

[Jason A. Donenfeld]

Here are the two patches we've been looking at thus far in separate
threads, now brought together as one patchset. This doesn't fix _all_ of
the PREEMPT_RT issues, but it does very much move in the right direction
of having less locking in places where that matters.

v4 improves on v3 by fixing documentation comments and copying the fast
pool to the stack before mixing.

Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Theodore Ts'o <tytso@mit.edu>
Cc: Sultan Alsawaf <sultan@kerneltoast.com>
Cc: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
Cc: Eric Biggers <ebiggers@kernel.org>

Jason A. Donenfeld (2):
  random: remove batched entropy locking
  random: defer fast pool mixing to worker

 drivers/char/random.c         | 109 +++++++++++++++++++---------------
 include/trace/events/random.h |   6 --
 2 files changed, 62 insertions(+), 53 deletions(-)

-- 
2.35.0

[PATCH v4 1/2] random: remove batched entropy locking

[Jason A. Donenfeld]

Rather than use spinlocks to protect batched entropy, we can instead
disable interrupts locally, since we're dealing with per-cpu data, and
manage resets with a basic generation counter. At the same time, we
can't quite do this on PREEMPT_RT, where we still want spinlocks-as-
mutexes semantics. So we use a local_lock_t, which provides the right
behavior for each. Because this is a per-cpu lock, that generation
counter is still doing the necessary CPU-to-CPU communication.

This should improve performance a bit. It will also fix the linked splat
that Jonathan received with a PROVE_RAW_LOCK_NESTING=y.

Suggested-by: Andy Lutomirski <luto@kernel.org>
Reported-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
Tested-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
Link: https://lore.kernel.org/lkml/YfMa0QgsjCVdRAvJ@latitude/
Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Cc: Sultan Alsawaf <sultan@kerneltoast.com>
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 drivers/char/random.c | 55 ++++++++++++++++++++++---------------------
 1 file changed, 28 insertions(+), 27 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 968c415d1f45..ceded1c4f73b 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1731,13 +1731,16 @@ static int __init random_sysctls_init(void)
 device_initcall(random_sysctls_init);
 #endif	/* CONFIG_SYSCTL */
 
+static atomic_t batch_generation = ATOMIC_INIT(0);
+
 struct batched_entropy {
 	union {
 		u64 entropy_u64[CHACHA_BLOCK_SIZE / sizeof(u64)];
 		u32 entropy_u32[CHACHA_BLOCK_SIZE / sizeof(u32)];
 	};
+	local_lock_t lock;
 	unsigned int position;
-	spinlock_t batch_lock;
+	int generation;
 };
 
 /*
@@ -1749,7 +1752,7 @@ struct batched_entropy {
  * point prior.
  */
 static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u64) = {
-	.batch_lock = __SPIN_LOCK_UNLOCKED(batched_entropy_u64.lock),
+	.lock = INIT_LOCAL_LOCK(batched_entropy_u64.lock)
 };
 
 u64 get_random_u64(void)
@@ -1758,67 +1761,65 @@ u64 get_random_u64(void)
 	unsigned long flags;
 	struct batched_entropy *batch;
 	static void *previous;
+	int next_gen;
 
 	warn_unseeded_randomness(&previous);
 
+	local_lock_irqsave(&batched_entropy_u64.lock, flags);
 	batch = raw_cpu_ptr(&batched_entropy_u64);
-	spin_lock_irqsave(&batch->batch_lock, flags);
-	if (batch->position % ARRAY_SIZE(batch->entropy_u64) == 0) {
+
+	next_gen = atomic_read(&batch_generation);
+	if (batch->position % ARRAY_SIZE(batch->entropy_u64) == 0 ||
+	    next_gen != batch->generation) {
 		extract_crng((u8 *)batch->entropy_u64);
 		batch->position = 0;
+		batch->generation = next_gen;
 	}
+
 	ret = batch->entropy_u64[batch->position++];
-	spin_unlock_irqrestore(&batch->batch_lock, flags);
+	local_unlock_irqrestore(&batched_entropy_u64.lock, flags);
 	return ret;
 }
 EXPORT_SYMBOL(get_random_u64);
 
 static DEFINE_PER_CPU(struct batched_entropy, batched_entropy_u32) = {
-	.batch_lock = __SPIN_LOCK_UNLOCKED(batched_entropy_u32.lock),
+	.lock = INIT_LOCAL_LOCK(batched_entropy_u32.lock)
 };
+
 u32 get_random_u32(void)
 {
 	u32 ret;
 	unsigned long flags;
 	struct batched_entropy *batch;
 	static void *previous;
+	int next_gen;
 
 	warn_unseeded_randomness(&previous);
 
+	local_lock_irqsave(&batched_entropy_u32.lock, flags);
 	batch = raw_cpu_ptr(&batched_entropy_u32);
-	spin_lock_irqsave(&batch->batch_lock, flags);
-	if (batch->position % ARRAY_SIZE(batch->entropy_u32) == 0) {
+
+	next_gen = atomic_read(&batch_generation);
+	if (batch->position % ARRAY_SIZE(batch->entropy_u32) == 0 ||
+	    next_gen != batch->generation) {
 		extract_crng((u8 *)batch->entropy_u32);
 		batch->position = 0;
+		batch->generation = next_gen;
 	}
+
 	ret = batch->entropy_u32[batch->position++];
-	spin_unlock_irqrestore(&batch->batch_lock, flags);
+	local_unlock_irqrestore(&batched_entropy_u32.lock, flags);
 	return ret;
 }
 EXPORT_SYMBOL(get_random_u32);
 
 /* It's important to invalidate all potential batched entropy that might
  * be stored before the crng is initialized, which we can do lazily by
- * simply resetting the counter to zero so that it's re-extracted on the
- * next usage. */
+ * bumping the generation counter.
+ */
 static void invalidate_batched_entropy(void)
 {
-	int cpu;
-	unsigned long flags;
-
-	for_each_possible_cpu(cpu) {
-		struct batched_entropy *batched_entropy;
-
-		batched_entropy = per_cpu_ptr(&batched_entropy_u32, cpu);
-		spin_lock_irqsave(&batched_entropy->batch_lock, flags);
-		batched_entropy->position = 0;
-		spin_unlock(&batched_entropy->batch_lock);
-
-		batched_entropy = per_cpu_ptr(&batched_entropy_u64, cpu);
-		spin_lock(&batched_entropy->batch_lock);
-		batched_entropy->position = 0;
-		spin_unlock_irqrestore(&batched_entropy->batch_lock, flags);
-	}
+	atomic_inc(&batch_generation);
 }
 
 /**
-- 
2.35.0

[PATCH v4 2/2] random: defer fast pool mixing to worker

[Jason A. Donenfeld]

On PREEMPT_RT, it's problematic to take spinlocks from hard irq
handlers. We can fix this by deferring to a work queue 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.

In the worst case, an irq handler is mixing a new irq into the pool at
the same time as the worker is dumping it into the input pool. In this
case, we only ever set the count back to 0 _after_ we're done, so that
subsequent cycles will require a full 64 to dump it in again. In other
words, the result of this race is only ever adding a little bit more
information than normal, but never less, and never crediting any more
for this partial additional information.

Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Theodore Ts'o <tytso@mit.edu>
Cc: Sultan Alsawaf <sultan@kerneltoast.com>
Cc: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 drivers/char/random.c         | 54 ++++++++++++++++++++++-------------
 include/trace/events/random.h |  6 ----
 2 files changed, 34 insertions(+), 26 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index ceded1c4f73b..f985d84872de 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -377,12 +377,6 @@ static void _mix_pool_bytes(const void *in, int nbytes)
 	blake2s_update(&input_pool.hash, in, nbytes);
 }
 
-static void __mix_pool_bytes(const void *in, int nbytes)
-{
-	trace_mix_pool_bytes_nolock(nbytes, _RET_IP_);
-	_mix_pool_bytes(in, nbytes);
-}
-
 static void mix_pool_bytes(const void *in, int nbytes)
 {
 	unsigned long flags;
@@ -394,11 +388,13 @@ static void mix_pool_bytes(const void *in, int nbytes)
 }
 
 struct fast_pool {
-	u32 pool[4];
+	struct work_struct mix;
 	unsigned long last;
+	u32 pool[4];
+	unsigned int count;
 	u16 reg_idx;
-	u8 count;
 };
+#define FAST_POOL_MIX_INFLIGHT (1U << 31)
 
 /*
  * This is a fast mixing routine used by the interrupt randomness
@@ -428,7 +424,6 @@ static void fast_mix(struct fast_pool *f)
 
 	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)
@@ -977,12 +972,34 @@ 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);
+	u8 pool[sizeof(fast_pool->pool)];
+
+	/*
+	 * Since this is the result of a trip through the scheduler, xor in
+	 * a cycle counter. It can't hurt, and might help.
+	 */
+	fast_pool->pool[3] ^= random_get_entropy();
+	/* Copy the pool to the stack so that the mixer always has a consistent view. */
+	memcpy(pool, fast_pool->pool, sizeof(pool));
+	/* We take care to zero out the count only after we're done reading the pool. */
+	WRITE_ONCE(fast_pool->count, 0);
+	fast_pool->last = jiffies;
+
+	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;
 	u32 c_high, j_high;
 	u64 ip;
 
@@ -999,9 +1016,10 @@ void add_interrupt_randomness(int irq)
 
 	fast_mix(fast_pool);
 	add_interrupt_bench(cycles);
+	new_count = ++fast_pool->count;
 
 	if (unlikely(crng_init == 0)) {
-		if ((fast_pool->count >= 64) &&
+		if (new_count >= 64 &&
 		    crng_fast_load((u8 *)fast_pool->pool, sizeof(fast_pool->pool)) > 0) {
 			fast_pool->count = 0;
 			fast_pool->last = now;
@@ -1009,20 +1027,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);
+	fast_pool->count |= FAST_POOL_MIX_INFLIGHT;
+	queue_work_on(raw_smp_processor_id(), system_highpri_wq, &fast_pool->mix);
 }
 EXPORT_SYMBOL_GPL(add_interrupt_randomness);
 
diff --git a/include/trace/events/random.h b/include/trace/events/random.h
index ad149aeaf42c..833f42afc70f 100644
--- a/include/trace/events/random.h
+++ b/include/trace/events/random.h
@@ -52,12 +52,6 @@ DEFINE_EVENT(random__mix_pool_bytes, mix_pool_bytes,
 	TP_ARGS(bytes, IP)
 );
 
-DEFINE_EVENT(random__mix_pool_bytes, mix_pool_bytes_nolock,
-	TP_PROTO(int bytes, unsigned long IP),
-
-	TP_ARGS(bytes, IP)
-);
-
 TRACE_EVENT(credit_entropy_bits,
 	TP_PROTO(int bits, int entropy_count, unsigned long IP),
 
-- 
2.35.0

Re: [PATCH v4 1/2] random: remove batched entropy locking

[Sebastian Andrzej Siewior]

On 2022-02-09 13:56:43 [+0100], Jason A. Donenfeld wrote:
> Rather than use spinlocks to protect batched entropy, we can instead
> disable interrupts locally, since we're dealing with per-cpu data, and
> manage resets with a basic generation counter. At the same time, we
> can't quite do this on PREEMPT_RT, where we still want spinlocks-as-
> mutexes semantics. So we use a local_lock_t, which provides the right
> behavior for each. Because this is a per-cpu lock, that generation
> counter is still doing the necessary CPU-to-CPU communication.
> 
> This should improve performance a bit. It will also fix the linked splat
> that Jonathan received with a PROVE_RAW_LOCK_NESTING=y.
> 
> Suggested-by: Andy Lutomirski <luto@kernel.org>
> Reported-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
> Tested-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
> Link: https://lore.kernel.org/lkml/YfMa0QgsjCVdRAvJ@latitude/
> Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
> Cc: Sultan Alsawaf <sultan@kerneltoast.com>
> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>

Reviewed-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>

Sebastian

Re: [PATCH v4 2/2] random: defer fast pool mixing to worker

[Sebastian Andrzej Siewior]

On 2022-02-09 13:56:44 [+0100], Jason A. Donenfeld wrote:
> +static void mix_interrupt_randomness(struct work_struct *work)
> +{
> +	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
> +	u8 pool[sizeof(fast_pool->pool)];

So.
- CPU1 schedules a worker
- CPU1 goes offline before the gets on the CPU.
- The worker runs CPU2
- CPU2 is back online
- and now
   CPU1						CPU2
   new_count = ++fast_pool->count;
    reg = fast_pool->count (FAST_POOL_MIX_INFLIGHT | 64)
    incl reg (FAST_POOL_MIX_INFLIGHT | 65)
    						WRITE_ONCE(fast_pool->count, 0);
    fast_pool->count = reg ((FAST_POOL_MIX_INFLIGHT | 65)

So we lost the WRITE_ONCE(, 0), FAST_POOL_MIX_INFLIGHT is still set and
worker is not scheduled. Not easy to trigger, not by an ordinary user.
Just wanted to mention…

…
> @@ -999,9 +1016,10 @@ void add_interrupt_randomness(int irq)
>  
>  	fast_mix(fast_pool);
>  	add_interrupt_bench(cycles);
> +	new_count = ++fast_pool->count;
>  
>  	if (unlikely(crng_init == 0)) {
> -		if ((fast_pool->count >= 64) &&
> +		if (new_count >= 64 &&
>  		    crng_fast_load((u8 *)fast_pool->pool, sizeof(fast_pool->pool)) > 0) {

crng_fast_load() does spin_trylock_irqsave() in hardirq context. It does
not produce any warning on RT but is still wrong IMHO:
- lockdep will see a random task and I remember in the past it produced
  strange lock chains based on this.

- Should another task attempt to acquire this lock then it will PI-boost the
  wrong task.

If we just could move this, too.

I don't know how timing critical this is but the first backtrace from
crng_fast_load() came (to my surprise) from hwrng_fillfn() (a kthread)
and added 64bytes in one go.

I did move that crng_fast_load() into the worker and did made some
numbers:
           <idle>-0       [000] d..h1..     2.069924: add_interrupt_randomness: Tick

first interrupt
…
        swapper/0-1       [000] d..h.11     2.341938: add_interrupt_randomness: Tick
        swapper/0-1       [000] d..h.11     2.341938: add_interrupt_randomness: work

the 64th interrupt, scheduling the worker.

        swapper/0-1       [000] d..h.11     2.345937: add_interrupt_randomness: Tick
        swapper/0-1       [000] d..h111     2.349938: add_interrupt_randomness: Tick
        swapper/0-1       [000] d..h.11     2.353939: add_interrupt_randomness: Tick
        swapper/0-1       [000] d..h.11     2.357940: add_interrupt_randomness: Tick
        swapper/0-1       [000] d..h111     2.361939: add_interrupt_randomness: Tick
        swapper/0-1       [000] d..h111     2.365939: add_interrupt_randomness: Tick
        swapper/0-1       [000] d..h.11     2.369941: add_interrupt_randomness: Tick
     kworker/0:0H-6       [000] .......     2.384714: mix_interrupt_randomness: load
     kworker/0:0H-6       [000] .......     2.384715: crng_fast_load: 16
           <idle>-0       [001] dn.h1..     3.205766: add_interrupt_randomness: Tick
           <idle>-0       [019] dn.h1..     6.771047: add_interrupt_randomness: Tick

7 interrupts got lost before the worker could run & load first 16 bytes.
The workqueue core gets initialized at that point and spawns first
worker. After that the interrupts took a break.
And then the work-to-load delay was quite low:

           <idle>-0       [019] dn.h1..     7.586234: add_interrupt_randomness: Tick
           <idle>-0       [019] dn.h1..     7.586234: add_interrupt_randomness: work
    kworker/19:0H-175     [019] .......     7.586504: mix_interrupt_randomness: load
    kworker/19:0H-175     [019] .......     7.586507: crng_fast_load: 16
           <idle>-0       [020] dn.h1..     7.614649: add_interrupt_randomness: Tick
           <idle>-0       [020] dn.h1..     7.614651: add_interrupt_randomness: work
           <idle>-0       [020] dn.h1..     7.614736: add_interrupt_randomness: Tick
    kworker/20:0H-183     [020] dn.h...     7.614859: add_interrupt_randomness: Tick
    kworker/20:0H-183     [020] .......     7.614871: mix_interrupt_randomness: load
    kworker/20:0H-183     [020] .......     7.614872: crng_fast_load: 16
           <idle>-0       [018] dn.h1..     8.352423: add_interrupt_randomness: Tick
           <idle>-0       [018] dn.h1..     8.352423: add_interrupt_randomness: work
    kworker/18:0H-167     [018] dn.h1..     8.352438: add_interrupt_randomness: Tick
    kworker/18:0H-167     [018] dn.h1..     8.352448: add_interrupt_randomness: Tick
    kworker/18:0H-167     [018] dn.h1..     8.352459: add_interrupt_randomness: Tick
    kworker/18:0H-167     [018] dn.h1..     8.352491: add_interrupt_randomness: Tick
    kworker/18:0H-167     [018] .......     8.352505: mix_interrupt_randomness: load
    kworker/18:0H-167     [018] .......     8.352506: crng_fast_load: 16

In total we lost 13 ticks.
I did the same test on PREEMPT_VOLUNTARY and lost 2 ticks only.

Sebastian

Re: [PATCH v4 2/2] random: defer fast pool mixing to worker

[Jason A. Donenfeld]

Hi Sebastian,

On Thu, Feb 10, 2022 at 7:04 PM Sebastian Andrzej Siewior
<bigeasy@linutronix.de> wrote:
> So.
> - CPU1 schedules a worker
> - CPU1 goes offline before the gets on the CPU.
> - The worker runs CPU2
> - CPU2 is back online
> - and now
>    CPU1                                         CPU2
>    new_count = ++fast_pool->count;
>     reg = fast_pool->count (FAST_POOL_MIX_INFLIGHT | 64)
>     incl reg (FAST_POOL_MIX_INFLIGHT | 65)
>                                                 WRITE_ONCE(fast_pool->count, 0);
>     fast_pool->count = reg ((FAST_POOL_MIX_INFLIGHT | 65)
>
> So we lost the WRITE_ONCE(, 0), FAST_POOL_MIX_INFLIGHT is still set and
> worker is not scheduled. Not easy to trigger, not by an ordinary user.
> Just wanted to mention…

Thanks for pointing this out. I'll actually fix this using atomics,
and fix another minor issue at the same time the same way, and move to
making sure the worker is running on the right CPU like we originally
discussed. I'm going to send that as an additional patch so that we
can narrow in on the issue there. It's a little bit involved but not
too bad. I'll have that for you shortly.

> crng_fast_load() does spin_trylock_irqsave() in hardirq context. It does
> not produce any warning on RT but is still wrong IMHO:
> If we just could move this, too.
> I don't know how timing critical this is but the first backtrace from
> crng_fast_load() came (to my surprise) from hwrng_fillfn() (a kthread)
> and added 64bytes in one go.

I'll look into seeing if I can do it. On my first pass a few days ago,
it seemed a bit too tricky, but I'll revisit after this part here
settles. Thanks for your benchmarks, by the way. That's useful.

Jason

[PATCH] random: ensure mix_interrupt_randomness() is consistent

[Jason A. Donenfeld]

This addresses two issues alluded to in an earlier commit.

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
do after all 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. The likelihood of actually
hitting this is very low, as we're talking about a 2 or 4 word mov, and
we're executing on the same CPU as the potential interruption.
Nonetheless, it's easy enough to fix, so we do here.

If we only were concerned with the first issue rather than the second,
we could fix this entirely with just using an atomic_t. But in order to
fix them both, it requires a bit of coordination, which this patch
tackles.

Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Theodore Ts'o <tytso@mit.edu>
Cc: Dominik Brodowski <linux@dominikbrodowski.net>
Cc: Sultan Alsawaf <sultan@kerneltoast.com>
Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
---
 drivers/char/random.c | 42 ++++++++++++++++++++++++++++++++++--------
 1 file changed, 34 insertions(+), 8 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 9c779f1bda34..caaf3c33bb38 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1152,10 +1152,11 @@ struct fast_pool {
 	union {
 		u64 pool64[2];
 		u32 pool32[4];
+		unsigned long pool_long[16 / sizeof(long)];
 	};
 	struct work_struct mix;
 	unsigned long last;
-	unsigned int count;
+	atomic_t count;
 	u16 reg_idx;
 };
 #define FAST_POOL_MIX_INFLIGHT (1U << 31)
@@ -1210,14 +1211,39 @@ static u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
 static void mix_interrupt_randomness(struct work_struct *work)
 {
 	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
-	u32 pool[ARRAY_SIZE(fast_pool->pool32)];
+	unsigned long pool[ARRAY_SIZE(fast_pool->pool_long)];
+	unsigned int count_snapshot;
+	size_t i;
 
-	/* Copy the pool to the stack so that the mixer always has a consistent view. */
-	memcpy(pool, fast_pool->pool32, sizeof(pool));
+	/* 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.
+		 */
+		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_long[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. */
-	WRITE_ONCE(fast_pool->count, 0);
+	atomic_set(&fast_pool->count, 0);
 	fast_pool->last = jiffies;
+	migrate_enable();
 
 	mix_pool_bytes(pool, sizeof(pool));
 	credit_entropy_bits(1);
@@ -1246,12 +1272,12 @@ void add_interrupt_randomness(int irq)
 	}
 
 	fast_mix(fast_pool->pool32);
-	new_count = ++fast_pool->count;
+	new_count = (unsigned int)atomic_inc_return_acquire(&fast_pool->count);
 
 	if (unlikely(crng_init == 0)) {
 		if (new_count >= 64 &&
 		    crng_fast_load(fast_pool->pool32, sizeof(fast_pool->pool32)) > 0) {
-			fast_pool->count = 0;
+			atomic_set(&fast_pool->count, 0);
 			fast_pool->last = now;
 
 			/*
@@ -1273,7 +1299,7 @@ void add_interrupt_randomness(int irq)
 
 	if (unlikely(!fast_pool->mix.func))
 		INIT_WORK(&fast_pool->mix, mix_interrupt_randomness);
-	fast_pool->count |= FAST_POOL_MIX_INFLIGHT;
+	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);
-- 
2.35.0

Re: [PATCH v4 2/2] random: defer fast pool mixing to worker

[Sebastian Andrzej Siewior]

On 2022-02-11 01:42:56 [+0100], Jason A. Donenfeld wrote:
> Hi Sebastian,
Hi Jason,

> Thanks for pointing this out. I'll actually fix this using atomics,
> and fix another minor issue at the same time the same way, and move to
> making sure the worker is running on the right CPU like we originally
> discussed. I'm going to send that as an additional patch so that we
> can narrow in on the issue there. It's a little bit involved but not
> too bad. I'll have that for you shortly.

oki.

> > crng_fast_load() does spin_trylock_irqsave() in hardirq context. It does
> > not produce any warning on RT but is still wrong IMHO:
> > If we just could move this, too.
> > I don't know how timing critical this is but the first backtrace from
> > crng_fast_load() came (to my surprise) from hwrng_fillfn() (a kthread)
> > and added 64bytes in one go.
> 
> I'll look into seeing if I can do it. On my first pass a few days ago,
> it seemed a bit too tricky, but I'll revisit after this part here
> settles. Thanks for your benchmarks, by the way. That's useful.

If you want me to do it again or another machines, just let me know.
That was from a bigger x86 machine. I added that series and the patch at
the bottom to my RT queue.

-------->8--------

From: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Date: Thu, 10 Feb 2022 18:22:05 +0100
Subject: [PATCH] random: Move crng_fast_load() to the worker.

crng_fast_load() is invoked from hard IRQ context and acquires a
spinlock_t via a trylock. If the lock is locked in hard IRQ context then
the following locking attempt (on another CPU) will PI-boost the wrong
task.

Move the crng_fast_load() invocation into the worker.

Signed-off-by: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
---
 drivers/char/random.c |   27 ++++++++++++++++++++++-----
 1 file changed, 22 insertions(+), 5 deletions(-)

--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1047,6 +1047,17 @@ static void mix_interrupt_randomness(str
 	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
 	u8 pool[sizeof(fast_pool->pool)];
 
+	if (unlikely(crng_init == 0)) {
+		size_t ret;
+
+		ret = crng_fast_load((u8 *)fast_pool->pool, sizeof(fast_pool->pool));
+		if (ret) {
+			WRITE_ONCE(fast_pool->count, 0);
+			fast_pool->last = jiffies;
+			return;
+		}
+	}
+
 	/*
 	 * Since this is the result of a trip through the scheduler, xor in
 	 * a cycle counter. It can't hurt, and might help.
@@ -1089,11 +1100,17 @@ void add_interrupt_randomness(int irq)
 	new_count = ++fast_pool->count;
 
 	if (unlikely(crng_init == 0)) {
-		if (new_count >= 64 &&
-		    crng_fast_load((u8 *)fast_pool->pool, sizeof(fast_pool->pool)) > 0) {
-			fast_pool->count = 0;
-			fast_pool->last = now;
-		}
+		if (new_count & FAST_POOL_MIX_INFLIGHT)
+			return;
+
+		if (new_count < 64)
+			return;
+
+		fast_pool->count |= FAST_POOL_MIX_INFLIGHT;
+		if (unlikely(!fast_pool->mix.func))
+			INIT_WORK(&fast_pool->mix, mix_interrupt_randomness);
+		queue_work_on(raw_smp_processor_id(), system_highpri_wq,
+			      &fast_pool->mix);
 		return;
 	}
 

> Jason

Sebastian

Re: [PATCH] random: ensure mix_interrupt_randomness() is consistent

[Sebastian Andrzej Siewior]

On 2022-02-11 02:14:46 [+0100], Jason A. Donenfeld wrote:
> Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Theodore Ts'o <tytso@mit.edu>
> Cc: Dominik Brodowski <linux@dominikbrodowski.net>
> Cc: Sultan Alsawaf <sultan@kerneltoast.com>
> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
> ---
>  drivers/char/random.c | 42 ++++++++++++++++++++++++++++++++++--------
>  1 file changed, 34 insertions(+), 8 deletions(-)
> 
> diff --git a/drivers/char/random.c b/drivers/char/random.c
> index 9c779f1bda34..caaf3c33bb38 100644
> --- a/drivers/char/random.c
> +++ b/drivers/char/random.c
> @@ -1210,14 +1211,39 @@ static u32 get_reg(struct fast_pool *f, struct pt_regs *regs)
>  static void mix_interrupt_randomness(struct work_struct *work)
>  {
>  	struct fast_pool *fast_pool = container_of(work, struct fast_pool, mix);
> -	u32 pool[ARRAY_SIZE(fast_pool->pool32)];
> +	unsigned long pool[ARRAY_SIZE(fast_pool->pool_long)];
> +	unsigned int count_snapshot;
> +	size_t i;
>  
> -	/* Copy the pool to the stack so that the mixer always has a consistent view. */
> -	memcpy(pool, fast_pool->pool32, sizeof(pool));
> +	/* Check to see if we're running on the wrong CPU due to hotplug. */
> +	migrate_disable();
> +	if (fast_pool != this_cpu_ptr(&irq_randomness)) {

I am not sure that acquire and release semantic is needed and if so a
comment would probably be helpful to explain why.
But I'm trying to avoid the migrate_disable(), so:
To close the racy with losing the workqueue bit, wouldn't it be
sufficient to set it to zero via atomic_cmpxchg()? Also if the counter
before the memcpy() and after (at cmpxchg time) didn't change then the
pool wasn't modified. So basically 

 do {
 	counter = atomic_read(&fast_pool->count); // no need to cast
	memcpy(pool, fast_pool->pool_long, ARRAY_SIZE(pool));
    } while (atomic_cmpxchg(&fast_pool->count, counter, 0) != counter);


then it also shouldn't matter if we are _accidentally_ on the wrong CPU.

> +		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.
> +		 */
> +		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_long[i]);

Why do you avoid memcpy()? Since it is a small memcpy, I'm sure the
compile will inline the register moves.

Sebastian

Re: [PATCH v4 2/2] random: defer fast pool mixing to worker

[Dominik Brodowski]

Am Thu, Feb 10, 2022 at 07:04:20PM +0100 schrieb Sebastian Andrzej Siewior:
> > @@ -999,9 +1016,10 @@ void add_interrupt_randomness(int irq)
> >  
> >  	fast_mix(fast_pool);
> >  	add_interrupt_bench(cycles);
> > +	new_count = ++fast_pool->count;
> >  
> >  	if (unlikely(crng_init == 0)) {
> > -		if ((fast_pool->count >= 64) &&
> > +		if (new_count >= 64 &&
> >  		    crng_fast_load((u8 *)fast_pool->pool, sizeof(fast_pool->pool)) > 0) {
> 
> crng_fast_load() does spin_trylock_irqsave() in hardirq context. It does
> not produce any warning on RT but is still wrong IMHO:
> - lockdep will see a random task and I remember in the past it produced
>   strange lock chains based on this.
> 
> - Should another task attempt to acquire this lock then it will PI-boost the
>   wrong task.
> 
> If we just could move this, too.
> 
> I don't know how timing critical this is but the first backtrace from
> crng_fast_load() came (to my surprise) from hwrng_fillfn() (a kthread)
> and added 64bytes in one go.

That's a hw rng (such as a tpm chip or the virtio-rng driver) providing some
entropy; if it's 64 bytes of input, crng_init progresses to 1, and
crng_fast_load() should never be called again.[*] I'm a bit suprised that the
hw_rng input occurred so early (it's only at device_initcall() level), and
earlier than 64 interrupts. But that may differ from system to system.

Note that crng_fast_load() will also never be called from
add_interrupt_randomness() if

	EFI, DT or kexec provides bootloader entropy of at least 64 bytes,
	and CONFIG_RANDOM_TRUST_BOOTLOADER is set

and/or	CONFIG_RANDOM_TRUST_CPU is set and the RDRAND/RDSEED instructions do
	not fail.

If neither of these three conditions (hw_rng is run early, bootloader or CPU
randomness) are met, the initial and early seeding of the base_crng depends
on add_interrupt_randomness(), and should happen rather quickly.

> I did move that crng_fast_load() into the worker and did made some
> numbers:
>            <idle>-0       [000] d..h1..     2.069924: add_interrupt_randomness: Tick
> 
> first interrupt
> …
>         swapper/0-1       [000] d..h.11     2.341938: add_interrupt_randomness: Tick
>         swapper/0-1       [000] d..h.11     2.341938: add_interrupt_randomness: work
> 
> the 64th interrupt, scheduling the worker.
> 
>         swapper/0-1       [000] d..h.11     2.345937: add_interrupt_randomness: Tick
>         swapper/0-1       [000] d..h111     2.349938: add_interrupt_randomness: Tick
>         swapper/0-1       [000] d..h.11     2.353939: add_interrupt_randomness: Tick
>         swapper/0-1       [000] d..h.11     2.357940: add_interrupt_randomness: Tick
>         swapper/0-1       [000] d..h111     2.361939: add_interrupt_randomness: Tick
>         swapper/0-1       [000] d..h111     2.365939: add_interrupt_randomness: Tick
>         swapper/0-1       [000] d..h.11     2.369941: add_interrupt_randomness: Tick
>      kworker/0:0H-6       [000] .......     2.384714: mix_interrupt_randomness: load
>      kworker/0:0H-6       [000] .......     2.384715: crng_fast_load: 16
>            <idle>-0       [001] dn.h1..     3.205766: add_interrupt_randomness: Tick
>            <idle>-0       [019] dn.h1..     6.771047: add_interrupt_randomness: Tick
> 
> 7 interrupts got lost before the worker could run & load first 16 bytes.
> The workqueue core gets initialized at that point and spawns first
> worker.

So the reason for the longer delay here is that the workqueue core had not
been initialized beforehand?

> After that the interrupts took a break.
> And then the work-to-load delay was quite low:
> 
>            <idle>-0       [019] dn.h1..     7.586234: add_interrupt_randomness: Tick
>            <idle>-0       [019] dn.h1..     7.586234: add_interrupt_randomness: work
>     kworker/19:0H-175     [019] .......     7.586504: mix_interrupt_randomness: load
>     kworker/19:0H-175     [019] .......     7.586507: crng_fast_load: 16
>            <idle>-0       [020] dn.h1..     7.614649: add_interrupt_randomness: Tick
>            <idle>-0       [020] dn.h1..     7.614651: add_interrupt_randomness: work
>            <idle>-0       [020] dn.h1..     7.614736: add_interrupt_randomness: Tick
>     kworker/20:0H-183     [020] dn.h...     7.614859: add_interrupt_randomness: Tick
>     kworker/20:0H-183     [020] .......     7.614871: mix_interrupt_randomness: load
>     kworker/20:0H-183     [020] .......     7.614872: crng_fast_load: 16
>            <idle>-0       [018] dn.h1..     8.352423: add_interrupt_randomness: Tick
>            <idle>-0       [018] dn.h1..     8.352423: add_interrupt_randomness: work
>     kworker/18:0H-167     [018] dn.h1..     8.352438: add_interrupt_randomness: Tick
>     kworker/18:0H-167     [018] dn.h1..     8.352448: add_interrupt_randomness: Tick
>     kworker/18:0H-167     [018] dn.h1..     8.352459: add_interrupt_randomness: Tick
>     kworker/18:0H-167     [018] dn.h1..     8.352491: add_interrupt_randomness: Tick
>     kworker/18:0H-167     [018] .......     8.352505: mix_interrupt_randomness: load
>     kworker/18:0H-167     [018] .......     8.352506: crng_fast_load: 16
> 
> In total we lost 13 ticks.

Was this still way before the initramfs was up and running?

> I did the same test on PREEMPT_VOLUNTARY and lost 2 ticks only.

Thanks,
	Dominik

[*] Actually, there's some contradiciton going on: If we do not trust the
hw_rng device (that is, its quality setting is 0), crng_fast_load() will be
called nonetheless, and the hw_rng-provided input will be used to increment
crng_init to 1. If !CONFIG_RANDOM_TRUST_BOOTLOADER, only crng_slow_load() is
called, and crng_init will remain at 0. Similar for
!CONFIG_RANDOM_TRUST_CPU.

Re: [PATCH] random: ensure mix_interrupt_randomness() is consistent

[Jason A. Donenfeld]

Hi Sebastian,

On Fri, Feb 11, 2022 at 9:16 AM Sebastian Andrzej Siewior
<bigeasy@linutronix.de> wrote:
> But I'm trying to avoid the migrate_disable(), so:
> To close the racy with losing the workqueue bit, wouldn't it be
> sufficient to set it to zero via atomic_cmpxchg()? Also if the counter
> before the memcpy() and after (at cmpxchg time) didn't change then the
> pool wasn't modified. So basically
>
>  do {
>         counter = atomic_read(&fast_pool->count); // no need to cast
>         memcpy(pool, fast_pool->pool_long, ARRAY_SIZE(pool));
>     } while (atomic_cmpxchg(&fast_pool->count, counter, 0) != counter);
>
>
> then it also shouldn't matter if we are _accidentally_ on the wrong CPU.

This won't work. If we're executing on a different CPU, the CPU
mutating the pool won't necessarily update the count at the right
time. This isn't actually a seqlock or something like that. Rather, it
depends on running on the same CPU, where the interrupting irq handler
runs in full before giving control back, so that count and pool are
either both updated or not at all. Making this work across CPUs makes
things a lot more complicated and I'd rather not do that.

Actually, though, a nicer fix would be to just disable local
interrupts for that *2 word copy*. That's a tiny period of time. If
you permit me, that seems nicer. But if you don't like that, I'll keep
that loop.

Unfortunately, though, I think disabling migration is required. Sultan
(CC'd) found that these workqueues can migrate even midway through
running. And generally the whole idea is to keep this on the *same*
CPU so that we don't have to introduce locks and synchronization.

I'll add comments around the acquire/release. The remaining question
I believe is: would you prefer disabing irqs during the 2 word memcpy,
or this counter double read loop?


Jason

Re: [PATCH] random: ensure mix_interrupt_randomness() is consistent

[Jason A. Donenfeld]

Sorry, missed this in your last email:

On Fri, Feb 11, 2022 at 9:16 AM Sebastian Andrzej Siewior
<bigeasy@linutronix.de> wrote:
> > +     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_long[i]);
>
> Why do you avoid memcpy()? Since it is a small memcpy, I'm sure the
> compile will inline the register moves.

Because the compiler will otherwise reorder it to be after the two
counter reads. I checked. And a barrier() is too heavy as it flushes
the writes to the stack instead of keeping them read into registers.
READ_ONCE() is the exact semantics we care about here.

Jason

Re: [PATCH v4 2/2] random: defer fast pool mixing to worker

[Sebastian Andrzej Siewior]

On 2022-02-11 09:25:00 [+0100], Dominik Brodowski wrote:
> That's a hw rng (such as a tpm chip or the virtio-rng driver) providing some
> entropy; if it's 64 bytes of input, crng_init progresses to 1, and
> crng_fast_load() should never be called again.[*] I'm a bit suprised that the
> hw_rng input occurred so early (it's only at device_initcall() level), and
> earlier than 64 interrupts. But that may differ from system to system.
> 
> Note that crng_fast_load() will also never be called from
> add_interrupt_randomness() if
> 
> 	EFI, DT or kexec provides bootloader entropy of at least 64 bytes,
> 	and CONFIG_RANDOM_TRUST_BOOTLOADER is set
> 
> and/or	CONFIG_RANDOM_TRUST_CPU is set and the RDRAND/RDSEED instructions do
> 	not fail.
> 
> If neither of these three conditions (hw_rng is run early, bootloader or CPU
> randomness) are met, the initial and early seeding of the base_crng depends
> on add_interrupt_randomness(), and should happen rather quickly.

Right.

> > I did move that crng_fast_load() into the worker and did made some
> > numbers:
> >            <idle>-0       [000] d..h1..     2.069924: add_interrupt_randomness: Tick
> > 
> > first interrupt
> > …
> >         swapper/0-1       [000] d..h.11     2.341938: add_interrupt_randomness: Tick
> >         swapper/0-1       [000] d..h.11     2.341938: add_interrupt_randomness: work
> > 
> > the 64th interrupt, scheduling the worker.
> > 
> >         swapper/0-1       [000] d..h.11     2.345937: add_interrupt_randomness: Tick
> >         swapper/0-1       [000] d..h111     2.349938: add_interrupt_randomness: Tick
> >         swapper/0-1       [000] d..h.11     2.353939: add_interrupt_randomness: Tick
> >         swapper/0-1       [000] d..h.11     2.357940: add_interrupt_randomness: Tick
> >         swapper/0-1       [000] d..h111     2.361939: add_interrupt_randomness: Tick
> >         swapper/0-1       [000] d..h111     2.365939: add_interrupt_randomness: Tick
> >         swapper/0-1       [000] d..h.11     2.369941: add_interrupt_randomness: Tick
> >      kworker/0:0H-6       [000] .......     2.384714: mix_interrupt_randomness: load
> >      kworker/0:0H-6       [000] .......     2.384715: crng_fast_load: 16
> >            <idle>-0       [001] dn.h1..     3.205766: add_interrupt_randomness: Tick
> >            <idle>-0       [019] dn.h1..     6.771047: add_interrupt_randomness: Tick
> > 
> > 7 interrupts got lost before the worker could run & load first 16 bytes.
> > The workqueue core gets initialized at that point and spawns first
> > worker.
> 
> So the reason for the longer delay here is that the workqueue core had not
> been initialized beforehand?

Kind of, yes. workqueue_init_early() happens quite early so we don't
have to worry about NULL pointer for system_highpri_wq. The worker
started after workqueue_init() populated the worker pools.

> > After that the interrupts took a break.
> > And then the work-to-load delay was quite low:
> > 
> >            <idle>-0       [019] dn.h1..     7.586234: add_interrupt_randomness: Tick
> >            <idle>-0       [019] dn.h1..     7.586234: add_interrupt_randomness: work
> >     kworker/19:0H-175     [019] .......     7.586504: mix_interrupt_randomness: load
> >     kworker/19:0H-175     [019] .......     7.586507: crng_fast_load: 16
> >            <idle>-0       [020] dn.h1..     7.614649: add_interrupt_randomness: Tick
> >            <idle>-0       [020] dn.h1..     7.614651: add_interrupt_randomness: work
> >            <idle>-0       [020] dn.h1..     7.614736: add_interrupt_randomness: Tick
> >     kworker/20:0H-183     [020] dn.h...     7.614859: add_interrupt_randomness: Tick
> >     kworker/20:0H-183     [020] .......     7.614871: mix_interrupt_randomness: load
> >     kworker/20:0H-183     [020] .......     7.614872: crng_fast_load: 16
> >            <idle>-0       [018] dn.h1..     8.352423: add_interrupt_randomness: Tick
> >            <idle>-0       [018] dn.h1..     8.352423: add_interrupt_randomness: work
> >     kworker/18:0H-167     [018] dn.h1..     8.352438: add_interrupt_randomness: Tick
> >     kworker/18:0H-167     [018] dn.h1..     8.352448: add_interrupt_randomness: Tick
> >     kworker/18:0H-167     [018] dn.h1..     8.352459: add_interrupt_randomness: Tick
> >     kworker/18:0H-167     [018] dn.h1..     8.352491: add_interrupt_randomness: Tick
> >     kworker/18:0H-167     [018] .......     8.352505: mix_interrupt_randomness: load
> >     kworker/18:0H-167     [018] .......     8.352506: crng_fast_load: 16
> > 
> > In total we lost 13 ticks.
> 
> Was this still way before the initramfs was up and running?

After unpacked initramfs. From current boot:

| [    5.901462] Unpacking initramfs...
| [    6.758747] sd 1:0:0:0: [sda] Attached SCSI disk
| [    7.886651] Freeing initrd memory: 9532K
| [    7.893753] Freeing unused kernel image (initmem) memory: 2184K
| [    7.963519] Write protecting the kernel read-only data: 20480k
| [    7.971465] Freeing unused kernel image (text/rodata gap) memory: 2032K
| [    7.979711] Freeing unused kernel image (rodata/data gap) memory: 1980K
| [    7.987132] Run /init as init process
| Loading, please wait...
| 
| Starting version 250.3-2
| [    8.157529] igb 0000:07:00.0 eno0: renamed from eth0
| [    8.203836] igb 0000:07:00.1 enp7s0f1: renamed from eth1
| [    8.219489] random: fast init done
| Begin: Loading essential drivers ... done.
| Begin: Running /scripts/init-premount ... done.
| Begin: Mounting root file system ... Begin: Running /scripts/local-top ... done.
| Begin: Running /scripts/local-premount ... done.
| Warning: fsck not present, so skipping root file[    8.337554] XFS (sda2): Mounting V5 Filesystem
| [    8.392151] XFS (sda2): Ending clean mount
| done.
| Begin: Running /scripts/local-bottom ... done.
| Begin: Running /scripts/init-bottom ... done.
| [    8.540708] systemd[1]: systemd 250.3-2 running in system mode …
| [   12.207227] random: crng init done

I have to note that on this system there is a initramfs but all drivers
are built-in (you see sd, net _after_ "Unpacking initramfs" but there
are not drivers to load).

> Thanks,
> 	Dominik

Sebastian

Re: [PATCH] random: ensure mix_interrupt_randomness() is consistent

[Sebastian Andrzej Siewior]

On 2022-02-11 11:48:15 [+0100], Jason A. Donenfeld wrote:
> Hi Sebastian,
Hi,

> On Fri, Feb 11, 2022 at 9:16 AM Sebastian Andrzej Siewior
> <bigeasy@linutronix.de> wrote:
> > But I'm trying to avoid the migrate_disable(), so:
> > To close the racy with losing the workqueue bit, wouldn't it be
> > sufficient to set it to zero via atomic_cmpxchg()? Also if the counter
> > before the memcpy() and after (at cmpxchg time) didn't change then the
> > pool wasn't modified. So basically
> >
> >  do {
> >         counter = atomic_read(&fast_pool->count); // no need to cast
> >         memcpy(pool, fast_pool->pool_long, ARRAY_SIZE(pool));
> >     } while (atomic_cmpxchg(&fast_pool->count, counter, 0) != counter);
> >
> >
> > then it also shouldn't matter if we are _accidentally_ on the wrong CPU.
> 
> This won't work. If we're executing on a different CPU, the CPU
> mutating the pool won't necessarily update the count at the right
> time. This isn't actually a seqlock or something like that. Rather, it

But it is atomic, isn't it?

> depends on running on the same CPU, where the interrupting irq handler
> runs in full before giving control back, so that count and pool are
> either both updated or not at all. Making this work across CPUs makes
> things a lot more complicated and I'd rather not do that.

but this isn't the rule, is it? It runs on the same CPU so we should
observe the update in IRQ context and the worker should observe the
counter _and_ pool update.

And cross CPU isn't the rule. We only re-do the loop if
- an interrupt came in on the local-CPU between atomic_read() and
  atomic_cmpxchg().

- the worker was migrated due CPU hotplug and we managed properly reset
  counter back to 0.

> Actually, though, a nicer fix would be to just disable local
> interrupts for that *2 word copy*. That's a tiny period of time. If
> you permit me, that seems nicer. But if you don't like that, I'll keep
> that loop.

Here, I don't mind but I don't think it is needed.

> Unfortunately, though, I think disabling migration is required. Sultan
> (CC'd) found that these workqueues can migrate even midway through
> running. And generally the whole idea is to keep this on the *same*
> CPU so that we don't have to introduce locks and synchronization.

They can't. Your workqueue is not unbound _and_ you specify a specific
CPU instead of WORK_CPU_UNBOUND (or an offlined CPU).
The only way it can migrate is if the CPU goes down while the worker is
running (or before it had a chance I think) which forces the scheduler
to break its (worker's) CPU affinity and move it to another CPU.

> I'll add comments around the acquire/release. The remaining question
> I believe is: would you prefer disabing irqs during the 2 word memcpy,
> or this counter double read loop?

I would prefer the cmpxchg in case it highly unlikely gets moved to
another CPU and we may lose that SCHED bit. That is why we switched to
atomics I think. Otherwise if the updates are only local can disable
interrupts during the update.
But I don't mind disabling interrupts for that copy.

> Jason

Sebastian

Re: [PATCH] random: ensure mix_interrupt_randomness() is consistent

[Jason A. Donenfeld]

Hi Sebastian,

On Fri, Feb 11, 2022 at 3:51 PM Sebastian Andrzej Siewior
<bigeasy@linutronix.de> wrote:
> > Unfortunately, though, I think disabling migration is required. Sultan
> > (CC'd) found that these workqueues can migrate even midway through
> > running. And generally the whole idea is to keep this on the *same*
> > CPU so that we don't have to introduce locks and synchronization.
>
> They can't. Your workqueue is not unbound _and_ you specify a specific
> CPU instead of WORK_CPU_UNBOUND (or an offlined CPU).
> The only way it can migrate is if the CPU goes down while the worker is
> running (or before it had a chance I think) which forces the scheduler
> to break its (worker's) CPU affinity and move it to another CPU.

Right, but the CPU could come back up while the worker is running on
the wrong CPU, and then kaboom. Anyway, the migration_disable() window
is very, very small - a few instructions at most with no loops. I
think it'll be fine.

> > I'll add comments around the acquire/release. The remaining question
> > I believe is: would you prefer disabing irqs during the 2 word memcpy,
> > or this counter double read loop?
>
> I would prefer the cmpxchg

I'll do the cmpxchg and send you a v+1. Sorry it wasn't in the last
one. It only now clicked with me what that code would look like, after
I stepped away from the screen for a bit to defrobulate my brains.

Jason

Re: [PATCH] random: ensure mix_interrupt_randomness() is consistent

[Sebastian Andrzej Siewior]

On 2022-02-11 17:19:21 [+0100], Jason A. Donenfeld wrote:
> Hi Sebastian,
Hi,

> I'll do the cmpxchg and send you a v+1. Sorry it wasn't in the last
> one. It only now clicked with me what that code would look like, after
> I stepped away from the screen for a bit to defrobulate my brains.

No worries. As much as I liked my first series, I like even more where
this is heading to ;)

> Jason

Sebastian

Re: [PATCH v4 1/2] random: remove batched entropy locking

[Eric Biggers]

On Wed, Feb 09, 2022 at 01:56:43PM +0100, Jason A. Donenfeld wrote:
> Rather than use spinlocks to protect batched entropy, we can instead
> disable interrupts locally, since we're dealing with per-cpu data, and
> manage resets with a basic generation counter. At the same time, we
> can't quite do this on PREEMPT_RT, where we still want spinlocks-as-
> mutexes semantics. So we use a local_lock_t, which provides the right
> behavior for each. Because this is a per-cpu lock, that generation
> counter is still doing the necessary CPU-to-CPU communication.
> 
> This should improve performance a bit. It will also fix the linked splat
> that Jonathan received with a PROVE_RAW_LOCK_NESTING=y.
> 
> Suggested-by: Andy Lutomirski <luto@kernel.org>
> Reported-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
> Tested-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>
> Link: https://lore.kernel.org/lkml/YfMa0QgsjCVdRAvJ@latitude/
> Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
> Cc: Sultan Alsawaf <sultan@kerneltoast.com>
> Signed-off-by: Jason A. Donenfeld <Jason@zx2c4.com>
> ---
>  drivers/char/random.c | 55 ++++++++++++++++++++++---------------------
>  1 file changed, 28 insertions(+), 27 deletions(-)

Reviewed-by: Eric Biggers <ebiggers@google.com>

- Eric