random: use correct memory barriers for crng_node_pool

PATCH RESEND In review Eric Biggers 3 participants 11 messages Dec 19, 2021 – Dec 20, 2021

Subsystems (3)

Stable branch Crypto API Random number driver

lore

Share & tools

lore

Eric Biggers

author

2021-12-19 02:52 UTC #0 lore raw

PATCH RESEND 1/1 random: use correct memory barriers for crng_node_pool

From: Eric Biggers <[email protected]>

When a CPU selects which CRNG to use, it accesses crng_node_pool without a memory barrier. That's wrong, because crng_node_pool can be set by another CPU concurrently. Without a memory barrier, the crng_state that is used might not appear to be fully initialized.

There's an explicit mb() on the write side, but it's redundant with cmpxchg() (or cmpxchg_release()) and does nothing to fix the read side.

Implement this correctly by using a cmpxchg_release() + smp_load_acquire() pair.

Note: READ_ONCE() could be used instead of smp_load_acquire(), but it is harder to verify that it is correct, so I'd prefer not to use it here.

Fixes 1e7f583af67b ("random: make /dev/urandom scalable for silly userspace programs")

Cc <[email protected]> # v4.8+

Signed-off-by Eric Biggers <[email protected]>

---

I sent this fix about a year ago
(https://lore.kernel.org/lkml/[email protected]/T/#u),
and though it's a correct fix, it was derailed by a debate about whether it's safe to use READ_ONCE() instead of smp_load_acquire() or not. Therefore, the current code, which (AFAIK) everyone agrees is buggy, was never actually fixed. Since random.c has a new maintainer now, I think it's worth sending this fix for reconsideration.

 drivers/char/random.c | 42 ++++++++++++++++++++++--------------------
 1 file changed, 22 insertions(+), 20 deletions(-)

drivers/char/random.c +22 ~~-20~~

index 605969ed0f96..349a6f235c61 100644
@@ -843,8 +843,8 @@ static void do_numa_crng_init(struct work_struct *work)
 		crng_initialize_secondary(crng);
 		pool[i] = crng;
 	}
-	mb();
-	if (cmpxchg(&crng_node_pool, NULL, pool)) {
+	/* pairs with smp_load_acquire() in select_crng() */
+	if (cmpxchg_release(&crng_node_pool, NULL, pool) != NULL) {
 		for_each_node(i)
 			kfree(pool[i]);
 		kfree(pool);

@@ -857,8 +857,26 @@ static void numa_crng_init(void)
 {
 	schedule_work(&numa_crng_init_work);
 }
+
+static inline struct crng_state *select_crng(void)
+{
+	struct crng_state **pool;
+	int nid = numa_node_id();
+
+	/* pairs with cmpxchg_release() in do_numa_crng_init() */
+	pool = smp_load_acquire(&crng_node_pool);
+	if (pool && pool[nid])
+		return pool[nid];
+
+	return &primary_crng;
+}
 #else
 static void numa_crng_init(void) {}
+
+static inline struct crng_state *select_crng(void)
+{
+	return &primary_crng;
+}
 #endif
 
 /*

@@ -1005,15 +1023,7 @@ static void _extract_crng(struct crng_state *crng,
 
 static void extract_crng(__u8 out[CHACHA_BLOCK_SIZE])
 {
-	struct crng_state *crng = NULL;
-
-#ifdef CONFIG_NUMA
-	if (crng_node_pool)
-		crng = crng_node_pool[numa_node_id()];
-	if (crng == NULL)
-#endif
-		crng = &primary_crng;
-	_extract_crng(crng, out);
+	_extract_crng(select_crng(), out);
 }
 
 /*

@@ -1042,15 +1052,7 @@ static void _crng_backtrack_protect(struct crng_state *crng,
 
 static void crng_backtrack_protect(__u8 tmp[CHACHA_BLOCK_SIZE], int used)
 {
-	struct crng_state *crng = NULL;
-
-#ifdef CONFIG_NUMA
-	if (crng_node_pool)
-		crng = crng_node_pool[numa_node_id()];
-	if (crng == NULL)
-#endif
-		crng = &primary_crng;
-	_crng_backtrack_protect(crng, tmp, used);
+	_crng_backtrack_protect(select_crng(), tmp, used);
 }
 
 static ssize_t extract_crng_user(void __user *buf, size_t nbytes)

Signature · 1 line

2.34.1

Jason A. Donenfeld

maintainer

2021-12-20 15:20 UTC #1 lore raw

drivers/char/random.c static void numa_crng_init(void) · line 877

Quoted 6 lines · Eric Biggers

drivers/char/random.c +6 -0

+
+static inline struct crng_state *select_crng(void)
+{
+
+static inline struct crng_state *select_crng(void)
+{

Usually static inline is avoided in .c files. Any special reason why we'd need this especially much here? Those functions are pretty small and I assume will be inlined anyway on most architectures.

I just did a test on x86_64 with GCC 11, and the same file was produced with 'static' as with 'static inline'. Was there an arch/config/compiler combo you were concerned about here?

Jason

Eric Biggers

author

2021-12-20 15:38 UTC #2 lore raw

Quoted 12 lines · Jason A. Donenfeld

drivers/char/random.c static void numa_crng_init(void) · line 877
Quoted 6 lines · Eric Biggers
drivers/char/random.c +6 -0
+
+static inline struct crng_state *select_crng(void)
+{
+
+static inline struct crng_state *select_crng(void)
+{
Usually static inline is avoided in .c files. Any special reason why we'd need this especially much here? Those functions are pretty small and I assume will be inlined anyway on most architectures.

Quoted 3 lines

I just did a test on x86_64 with GCC 11, and the same file was produced with 'static' as with 'static inline'. Was there an arch/config/compiler combo you were concerned about here?

No special reason, this is just a bad habit. I'm fine with omitting 'inline' here.

- Eric

Jason A. Donenfeld

maintainer

2021-12-20 15:26 UTC #3 lore raw

In reply to Eric Biggers

Hi Eric,

This patch seems fine to me, and I'll apply it in a few days after sitting on the list for comments, but:

Quoted 5 lines

Note: READ_ONCE() could be used instead of smp_load_acquire(), but it is harder to verify that it is correct, so I'd prefer not to use it here.
(https://lore.kernel.org/lkml/[email protected]/T/#u),
and though it's a correct fix, it was derailed by a debate about whether it's safe to use READ_ONCE() instead of smp_load_acquire() or not.

But holy smokes... I chuckled at your, "please explain in English." :)

Paul - if you'd like to look at this patch and confirm that this specific patch and usage is fine to be changed into READ_ONCE() instead of smp_load_acquire(), please pipe up here. And I really do mean this specific patch and usage, not to be confused with any other usage elsewhere in the kernel or question about general things, which doubtlessly involve larger discussions like the one Eric linked to above. If you're certain this patch here is READ_ONCE()able, I'd appreciate your saying so with a simple, "it is safe; go for it", since I'd definitely like the optimization if it's safe. If I don't hear from you, I'll apply this as-is from Eric, as I'd rather be safe than sorry.

Jason

Paul E. McKenney

2021-12-20 18:11 UTC #4 lore raw

Quoted 13 lines · Jason A. Donenfeld

Hi Eric,
This patch seems fine to me, and I'll apply it in a few days after sitting on the list for comments, but:
Quoted 5 lines
Note: READ_ONCE() could be used instead of smp_load_acquire(), but it is harder to verify that it is correct, so I'd prefer not to use it here.
(https://lore.kernel.org/lkml/[email protected]/T/#u),
and though it's a correct fix, it was derailed by a debate about whether it's safe to use READ_ONCE() instead of smp_load_acquire() or not.
But holy smokes... I chuckled at your, "please explain in English." :)

Quoted 11 lines

Paul - if you'd like to look at this patch and confirm that this specific patch and usage is fine to be changed into READ_ONCE() instead of smp_load_acquire(), please pipe up here. And I really do mean this specific patch and usage, not to be confused with any other usage elsewhere in the kernel or question about general things, which doubtlessly involve larger discussions like the one Eric linked to above. If you're certain this patch here is READ_ONCE()able, I'd appreciate your saying so with a simple, "it is safe; go for it", since I'd definitely like the optimization if it's safe. If I don't hear from you, I'll apply this as-is from Eric, as I'd rather be safe than sorry.

First I would want to see some evidence that READ_ONCE() was really providing measurable performance benefit. Such evidence would be easiest to obtain by running on a weakly ordered system such as ARM, ARMv8, or PowerPC.

If this does provide a measurable benefit, why not the following?

static inline struct crng_state *select_crng(void)

{
	struct crng_state **pool;
	struct crng_state *pooln;
	int nid = numa_node_id();

	/* pairs with cmpxchg_release() in do_numa_crng_init() */
	pool = rcu_dereference(&crng_node_pool);
	if (pool) {
		pooln = rcu_dereference(pool[nid]);
		if (pooln)
			return pooln;
	}

	return &primary_crng;
}

This is in ignorance of the kfree() side of this code. So another question is "Suppose that there was a long delay (vCPU preemption, for example) just before the 'return pooln'. What prevents a use-after-free bug?"

Of course, this question applies equally to the smp_load_acquire() version.

Thanx, Paul

Jason A. Donenfeld

maintainer

2021-12-20 18:17 UTC #5 lore raw

Quoted 1 line · Paul E. McKenney

First I would want

It looks like you've answered my question with four other questions, which seem certainly technically warranted, but also indicates we're probably not going to get to the nice easy resting place of, "it is safe; go for it" that I was hoping for. In light of that, it seems like merging Eric's patch is reasonable.

Jason

Paul E. McKenney

2021-12-20 18:31 UTC #6 lore raw

Quoted 8 lines · Jason A. Donenfeld

Quoted 1 line · Paul E. McKenney
First I would want
It looks like you've answered my question with four other questions, which seem certainly technically warranted, but also indicates we're probably not going to get to the nice easy resting place of, "it is safe; go for it" that I was hoping for. In light of that, it seems like merging Eric's patch is reasonable.

My hope would be that the questions can be quickly answered by the developers and maintainers. But yes, hope springs eternal.

Thanx, Paul

Eric Biggers

author

2021-12-20 18:35 UTC #7 lore raw

Quoted 10 lines · Paul E. McKenney

Quoted 8 lines · Jason A. Donenfeld
Quoted 1 line · Paul E. McKenney
First I would want
It looks like you've answered my question with four other questions, which seem certainly technically warranted, but also indicates we're probably not going to get to the nice easy resting place of, "it is safe; go for it" that I was hoping for. In light of that, it seems like merging Eric's patch is reasonable.

Quoted 4 lines

My hope would be that the questions can be quickly answered by the developers and maintainers. But yes, hope springs eternal.
Thanx, Paul

I wouldn't expect READ_ONCE() to provide a noticable performance improvement here, as it would be lost in the noise of the other work done, especially chacha20_block().

The data structures in question are never freed, so your other questions are irrelevant, if I understand correctly.

- Eric

Paul E. McKenney

2021-12-20 19:00 UTC #8 lore raw

Quoted 14 lines · Eric Biggers

Quoted 13 lines · Paul E. McKenney
Quoted 8 lines · Jason A. Donenfeld
Quoted 1 line · Paul E. McKenney
First I would want
It looks like you've answered my question with four other questions, which seem certainly technically warranted, but also indicates we're probably not going to get to the nice easy resting place of, "it is safe; go for it" that I was hoping for. In light of that, it seems like merging Eric's patch is reasonable.
My hope would be that the questions can be quickly answered by the developers and maintainers. But yes, hope springs eternal.

Quoted 8 lines

Quoted 1 line
Thanx, Paul
I wouldn't expect READ_ONCE() to provide a noticable performance improvement here, as it would be lost in the noise of the other work done, especially chacha20_block().
The data structures in question are never freed, so your other questions are irrelevant, if I understand correctly.

Very good, and thank you! You are correct, if the structures never are freed, there is no use-after-free issue. And that also explains why I was not able to find the free path. ;-)

So the main issue is the race between insertion and lookup. So yes, READ_ONCE() suffices.

This assumes that the various crng_node_pool[i] pointers never change while accessible to readers (and that some sort of synchronization applies to the values in the pointed-to structure). If these pointers do change, then there also needs to be a READ_ONCE(pool[nid]) in select_crng(), where the value returned from this READ_ONCE() is both tested and returned. (As in assign this value to a temporary.)

But if the various crng_node_pool[i] pointers really are constant while readers can access them, then the cmpxchg_release() suffices. The loads from pool[nid] are then data-race free, and because they are unmarked, the compiler is prohibited from hoisting them out from within the "if" statement. The address dependency prohibits the CPU from reordering them.

So READ_ONCE() should be just fine. Which answers Jason's question. ;-)

Looking at _extract_crng(), if this was my code, I would use READ_ONCE() in the checks, but that might be my misunderstanding boot-time constraints or some such. Without some sort of constraint, I don't see how the code avoids confusion from reloads of crng->init_time if two CPUs concurrently see the expiration of CRNG_RESEED_INTERVAL, but I could easily be missing something that makes this safe. (And this is irrelevant to this patch.)

You do appear to have ->lock guarding the pointed-to data, so that is good.

Thanx, Paul

Jason A. Donenfeld

maintainer

2021-12-20 21:45 UTC #9 lore raw

Hi Paul,

Quoted 7 lines · Paul E. McKenney

This assumes that the various crng_node_pool[i] pointers never change while accessible to readers (and that some sort of synchronization applies to the values in the pointed-to structure). If these pointers do change, then there also needs to be a READ_ONCE(pool[nid]) in select_crng(), where the value returned from this READ_ONCE() is both tested and returned. (As in assign this value to a temporary.)

Quoted 6 lines

But if the various crng_node_pool[i] pointers really are constant while readers can access them, then the cmpxchg_release() suffices. The loads from pool[nid] are then data-race free, and because they are unmarked, the compiler is prohibited from hoisting them out from within the "if" statement. The address dependency prohibits the CPU from reordering them.

Right, this is just an initialization-time allocation and assignment, never updated or freed again after.

Quoted 1 line

So READ_ONCE() should be just fine. Which answers Jason's question. ;-)

Great. So v2 of this patch can use READ_ONCE then. Thanks!

Quoted 6 lines

Looking at _extract_crng(), if this was my code, I would use READ_ONCE() in the checks, but that might be my misunderstanding boot-time constraints or some such. Without some sort of constraint, I don't see how the code avoids confusion from reloads of crng->init_time if two CPUs concurrently see the expiration of CRNG_RESEED_INTERVAL, but I could easily be missing something that makes this safe. (And this is irrelevant to this patch.)

Indeed init_time seems to race via the crng_reseed path, and READ_ONCE()ing that seems reasonable. The other setters of it -- initialize_{primary,secondary} -- are in the boot path.

Jason

Eric Biggers

author

2021-12-20 22:10 UTC #10 lore raw

Quoted 17 lines · Jason A. Donenfeld

Hi Paul,
Quoted 7 lines · Paul E. McKenney
This assumes that the various crng_node_pool[i] pointers never change while accessible to readers (and that some sort of synchronization applies to the values in the pointed-to structure). If these pointers do change, then there also needs to be a READ_ONCE(pool[nid]) in select_crng(), where the value returned from this READ_ONCE() is both tested and returned. (As in assign this value to a temporary.)
Quoted 6 lines
But if the various crng_node_pool[i] pointers really are constant while readers can access them, then the cmpxchg_release() suffices. The loads from pool[nid] are then data-race free, and because they are unmarked, the compiler is prohibited from hoisting them out from within the "if" statement. The address dependency prohibits the CPU from reordering them.

Quoted 6 lines

Right, this is just an initialization-time allocation and assignment, never updated or freed again after.
Quoted 1 line
So READ_ONCE() should be just fine. Which answers Jason's question. ;-)
Great. So v2 of this patch can use READ_ONCE then. Thanks!

Sure, I really don't care anymore. If people want READ_ONCE() here, I'll use it. It seems that the people who really prefer smp_load_acquire() aren't on this thread (unlike on
https://lore.kernel.org/linux-fsdevel/[email protected]/T/#u
for example, where READ_ONCE() was rejected), so I guess that is what people are going to agree on in this particular case.

- Eric