Skip to contentSkip to conversation

kcsan: Rewrite kcsan_prandom_u32_max() without prandom_u32_state()

PATCH Applied Marco Elver 2 participants 4 messages Nov 24, 2020 – Dec 1, 2020

Subsystems (2)
lore
Share & tools
lore

Marco Elver

author maintainer
#0 lore raw

PATCH v3 1/2 kcsan: Rewrite kcsan_prandom_u32_max() without prandom_u32_state()

Rewrite kcsan_prandom_u32_max() to not depend on code that might be instrumented, removing any dependency on lib/random32.c. The rewrite implements a simple linear congruential generator, that is sufficient for our purposes (for udelay() and skip_watch counter randomness).

The initial motivation for this was to allow enabling KCSAN for kernel/sched (remove KCSAN_SANITIZE := n from kernel/sched/Makefile), with CONFIG_DEBUG_PREEMPT=y. Without this change, we could observe recursion:

check_access() [via instrumentation]
kcsan_setup_watchpoint()
reset_kcsan_skip()
kcsan_prandom_u32_max()
get_cpu_var()
preempt_disable()
preempt_count_add() [in kernel/sched/core.c]
check_access() [via instrumentation]

Note, while this currently does not affect an unmodified kernel, it'd be good to keep a KCSAN kernel working when KCSAN_SANITIZE := n is removed from kernel/sched/Makefile to permit testing scheduler code with KCSAN if desired.

Fixes cd290ec24633 ("kcsan: Use tracing-safe version of prandom")

---
v3:
* Rewrite kcsan_prandom_u32_max() without lib/random32.c!

v2: https://lkml.kernel.org/r/[email protected]
* Update comment to also point out preempt_enable().

v1: https://lkml.kernel.org/r/[email protected]

---
 kernel/kcsan/core.c | 26 +++++++++++++-------------
 1 file changed, 13 insertions(+), 13 deletions(-)
kernel/kcsan/core.c +13 -13
index 3994a217bde7..3bf98db9c702 100644
@@ -12,7 +12,6 @@
 #include <linux/moduleparam.h>
 #include <linux/percpu.h>
 #include <linux/preempt.h>
-#include <linux/random.h>
 #include <linux/sched.h>
 #include <linux/uaccess.h>
 
@@ -101,7 +100,7 @@ static atomic_long_t watchpoints[CONFIG_KCSAN_NUM_WATCHPOINTS + NUM_SLOTS-1];
 static DEFINE_PER_CPU(long, kcsan_skip);
 
 /* For kcsan_prandom_u32_max(). */
-static DEFINE_PER_CPU(struct rnd_state, kcsan_rand_state);
+static DEFINE_PER_CPU(u32, kcsan_rand_state);
 
 static __always_inline atomic_long_t *find_watchpoint(unsigned long addr,
 						      size_t size,
@@ -275,20 +274,17 @@ should_watch(const volatile void *ptr, size_t size, int type, struct kcsan_ctx *
 }
 
 /*
- * Returns a pseudo-random number in interval [0, ep_ro). See prandom_u32_max()
- * for more details.
- *
- * The open-coded version here is using only safe primitives for all contexts
- * where we can have KCSAN instrumentation. In particular, we cannot use
- * prandom_u32() directly, as its tracepoint could cause recursion.
+ * Returns a pseudo-random number in interval [0, ep_ro). Simple linear
+ * congruential generator, using constants from "Numerical Recipes".
  */
 static u32 kcsan_prandom_u32_max(u32 ep_ro)
 {
-	struct rnd_state *state = &get_cpu_var(kcsan_rand_state);
-	const u32 res = prandom_u32_state(state);
+	u32 state = this_cpu_read(kcsan_rand_state);
+
+	state = 1664525 * state + 1013904223;
+	this_cpu_write(kcsan_rand_state, state);
 
-	put_cpu_var(kcsan_rand_state);
-	return (u32)(((u64) res * ep_ro) >> 32);
+	return state % ep_ro;
 }
 
 static inline void reset_kcsan_skip(void)
@@ -639,10 +635,14 @@ static __always_inline void check_access(const volatile void *ptr, size_t size,
 
 void __init kcsan_init(void)
 {
+	int cpu;
+
 	BUG_ON(!in_task());
 
 	kcsan_debugfs_init();
-	prandom_seed_full_state(&kcsan_rand_state);
+
+	for_each_possible_cpu(cpu)
+		per_cpu(kcsan_rand_state, cpu) = (u32)get_cycles();
 
 	/*
 	 * We are in the init task, and no other tasks should be running;
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
author maintainer
#1 lore raw

PATCH v3 2/2 random32: Re-enable KCSAN instrumentation

Re-enable KCSAN instrumentation, now that KCSAN no longer relies on code in lib/random32.c.

---
v3:
* Add patch to series, since KCSAN no longer needs lib/random32.c.

---
 lib/Makefile | 3 ---
 1 file changed, 3 deletions(-)
lib/Makefile +0 -3
index ce45af50983a..301020c49533 100644
@@ -27,9 +27,6 @@ KASAN_SANITIZE_string.o := n
 CFLAGS_string.o += -fno-stack-protector
 endif
 
-# Used by KCSAN while enabled, avoid recursion.
-KCSAN_SANITIZE_random32.o := n
-
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o timerqueue.o xarray.o \
 	 idr.o extable.o sha1.o irq_regs.o argv_split.o \
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
#2 lore raw

Re: [PATCH v3 2/2] random32: Re-enable KCSAN instrumentation

Quoted 4 lines · Marco Elver

Re-enable KCSAN instrumentation, now that KCSAN no longer relies on code in lib/random32.c.

Queued and pushed both, thank you!

Thanx, Paul

Quoted 24 lines

---
v3:
* Add patch to series, since KCSAN no longer needs lib/random32.c.

---
 lib/Makefile | 3 ---
 1 file changed, 3 deletions(-)
lib/Makefile +0 -3
index ce45af50983a..301020c49533 100644
@@ -27,9 +27,6 @@ KASAN_SANITIZE_string.o := n
 CFLAGS_string.o += -fno-stack-protector
 endif
 
-# Used by KCSAN while enabled, avoid recursion.
-KCSAN_SANITIZE_random32.o := n
-
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o timerqueue.o xarray.o \
 	 idr.o extable.o sha1.o irq_regs.o argv_split.o \
Signature · 1 line
2.29.2.454.gaff20da3a2-goog
author maintainer
#3 lore raw
In reply to Marco Elver

Hi Paul,

Quoted 5 lines · Marco Elver

Rewrite kcsan_prandom_u32_max() to not depend on code that might be instrumented, removing any dependency on lib/random32.c. The rewrite implements a simple linear congruential generator, that is sufficient for our purposes (for udelay() and skip_watch counter randomness).

[...]

It's been about 7 days -- feel free to pick up this series (unless there are new comments).

Thanks,
-- Marco