[PATCH 0/2] random: fix write locking for crng_init

[PATCH 0/2] random: fix write locking for crng_init

[Dominik Brodowski]

According to a comment in random.c, crng_init is protected by
primary_crng->lock. These two patches fix the locking for
writing tp (that is: increasing) crng_init in call sites where it
may matter. At rand_initialize() time (precisely: either in
crng_initialize_primary() or in crng_finalize_init()), crng_init
is set to 2 without the lock being held. However, then the
kernel is running with IRQs disabled and only the boot CPU
active (but not yet in PID 1).

Dominik Brodowski (2):
  random: fix locking in crng_fast_load()
  random: fix locking for crng_init in crng_reseed()

 drivers/char/random.c | 25 ++++++++++++++++++-------
 1 file changed, 18 insertions(+), 7 deletions(-)

-- 
2.35.1

[PATCH 1/2] random: fix locking in crng_fast_load()

[Dominik Brodowski]

crng_init is protected by primary_crng->lock, so keep holding that lock
when incrementing crng_init from 0 to 1 in crng_fast_load(). The call to
pr_notice() can wait until the lock is released; this code path cannot
be reached twice, as crng_fast_load() aborts early if crng_init > 0.

Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
---
 drivers/char/random.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 5d7d6e01bbc4..2df08d05e850 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -653,12 +653,13 @@ static size_t crng_fast_load(const u8 *cp, size_t len)
 		p[crng_init_cnt % CHACHA_KEY_SIZE] ^= *cp;
 		cp++; crng_init_cnt++; len--; ret++;
 	}
-	spin_unlock_irqrestore(&primary_crng.lock, flags);
 	if (crng_init_cnt >= CRNG_INIT_CNT_THRESH) {
 		invalidate_batched_entropy();
 		crng_init = 1;
-		pr_notice("fast init done\n");
 	}
+	spin_unlock_irqrestore(&primary_crng.lock, flags);
+	if (crng_init == 1)
+		pr_notice("fast init done\n");
 	return ret;
 }
 
-- 
2.35.1

[PATCH 2/2] random: fix locking for crng_init in crng_reseed()

[Dominik Brodowski]

crng_init is protected by primary_crng->lock. Therefore, we need
to hold this lock when increasing crng_init to 2. As we shouldn't
hold this lock for too long, only hold it for crng_finalize_init(),
and split out the parts which can be delayed to crng_late_init().

If crng_finalize_init() cannot proceed due to workqueues not yet
being available, it is called again in rand_initialize(). Then, we
do not need to call crng_late_init(): At this time, the boot
process is still so early that there are no other processes to wake
up.

Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
---
 drivers/char/random.c | 20 +++++++++++++++-----
 1 file changed, 15 insertions(+), 5 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 2df08d05e850..c70a9abbd8cb 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -557,19 +557,24 @@ static void __init crng_initialize_primary(void)
 	primary_crng.init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
 }
 
-static void crng_finalize_init(void)
+static bool crng_finalize_init(void)
 {
 	if (!system_wq) {
 		/* We can't call numa_crng_init until we have workqueues,
 		 * so mark this for processing later. */
 		crng_need_final_init = true;
-		return;
+		return false;
 	}
 
 	invalidate_batched_entropy();
 	numa_crng_init();
 	crng_init = 2;
 	crng_need_final_init = false;
+	return true;
+}
+
+static void crng_late_init(void)
+{
 	process_random_ready_list();
 	wake_up_interruptible(&crng_init_wait);
 	kill_fasync(&fasync, SIGIO, POLL_IN);
@@ -710,6 +715,7 @@ static int crng_slow_load(const u8 *cp, size_t len)
 
 static void crng_reseed(struct crng_state *crng)
 {
+	bool needs_late_init = false;
 	unsigned long flags;
 	int i;
 	union {
@@ -744,9 +750,11 @@ static void crng_reseed(struct crng_state *crng)
 	}
 	memzero_explicit(&buf, sizeof(buf));
 	WRITE_ONCE(crng->init_time, jiffies);
-	spin_unlock_irqrestore(&crng->lock, flags);
 	if (crng == &primary_crng && crng_init < 2)
-		crng_finalize_init();
+		needs_late_init = crng_finalize_init();
+	spin_unlock_irqrestore(&crng->lock, flags);
+	if (needs_late_init)
+		crng_late_init();
 }
 
 static void _extract_crng(struct crng_state *crng, u8 out[CHACHA_BLOCK_SIZE])
@@ -1383,8 +1391,10 @@ static void __init init_std_data(void)
 int __init rand_initialize(void)
 {
 	init_std_data();
-	if (crng_need_final_init)
+	if (crng_need_final_init) {
 		crng_finalize_init();
+		pr_notice("crng init done\n");
+	}
 	crng_initialize_primary();
 	crng_global_init_time = jiffies;
 	if (ratelimit_disable) {
-- 
2.35.1

Re: [PATCH 1/2] random: fix locking in crng_fast_load()

[Jason A. Donenfeld]

Hi Dominik,

Does this introduce a lock nesting inversion situation?

With your patch, crng_fast_load() now does:

    lock(primary_crng)
    invalidate_batched_entropy()
        lock(batch_lock)
        unlock(batch_lock)
    unlock(primary_crng)

While get_random_{u32,u64}() does:

    lock(batch_lock)
    extract_crng()
       lock(primary_crng)
       unlock(primary_crng)
    unlock(batch_lock)

Is this correct? If so, we might have to defer this patch until after
<https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?id=2dfab1b1>
or something like it lands, which attempts to get rid of the batched
entropy lock.

If that analysis seems right to you, I could pull this patch into that
development branch for poking and prodding.

Jason

Re: [PATCH 1/2] random: fix locking in crng_fast_load()

[Dominik Brodowski]

Hi Jason,

Am Sat, Feb 05, 2022 at 02:17:15PM +0100 schrieb Jason A. Donenfeld:
> Does this introduce a lock nesting inversion situation?
> 
> With your patch, crng_fast_load() now does:
> 
>     lock(primary_crng)
>     invalidate_batched_entropy()
>         lock(batch_lock)
>         unlock(batch_lock)
>     unlock(primary_crng)
> 
> While get_random_{u32,u64}() does:
> 
>     lock(batch_lock)
>     extract_crng()
>        lock(primary_crng)
>        unlock(primary_crng)
>     unlock(batch_lock)
> 
> Is this correct? If so, we might have to defer this patch until after
> <https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?id=2dfab1b1>
> or something like it lands, which attempts to get rid of the batched
> entropy lock.
> 
> If that analysis seems right to you, I could pull this patch into that
> development branch for poking and prodding.

Right, this makes sense -- I already "read" invalidate_batched_entropy() as
being just a call to atomic_inc().

Thanks,
	Dominik

Re: [PATCH 1/2] random: fix locking in crng_fast_load()

[Eric Biggers]

On Sat, Feb 05, 2022 at 11:34:57AM +0100, Dominik Brodowski wrote:
> crng_init is protected by primary_crng->lock, so keep holding that lock
> when incrementing crng_init from 0 to 1 in crng_fast_load(). The call to
> pr_notice() can wait until the lock is released; this code path cannot
> be reached twice, as crng_fast_load() aborts early if crng_init > 0.
> 
> Signed-off-by: Dominik Brodowski <linux@dominikbrodowski.net>
> ---
>  drivers/char/random.c | 5 +++--
>  1 file changed, 3 insertions(+), 2 deletions(-)

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

- Eric