Skip to contentSkip to conversation

archs/random: fallback to best raw ktime when no cycle counter

PATCH Superseded Jason A. Donenfeld 3 participants 14 messages Apr 12, 2022

Subsystems (11)
Arm (32-bit) x86 MIPS RISC-V +7 more subsystems

v3 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

v3 cover archs/random: fallback to best raw ktime when no cycle counter

Hi folks,

The RNG uses a function called random_get_entropy() basically anytime that it needs to timestamp an event. For example, an interrupt comes in, and we mix a random_get_entropy() into the entropy pool somehow. Somebody mashes their keyboard or moves their mouse around? We mix a random_get_entropy() into the entropy pool. It's one of the main varieties of input.

Unfortunately, it's always 0 on a few platforms. The RNG has accumulated various hacks to deal with this, but in general it's not great. Surely we can do better than 0. In fact, *anything* that's not the same exact value all the time would be better than 0. Even a counter that increments once per hour would be better than 0! I think you get the idea.

On most platforms, random_get_entropy() is aliased to get_cycles(), which makes sense for platforms where get_cycles() is defined. RDTSC, for example, has all the characteristics we care about for this
function: it's fast to acquire (i.e. acceptable in an irq handler), pretty high precision, available, forms a 2-monotone distribution, etc. But for platforms without that, what is the next best thing?

Sometimes the next best thing is architecture-defined. For example, really old MIPS has the CP0 random register, which isn't a cycle counter, but is at least something. However, some platforms don't even have an architecture-defined fallback.

Fortunately, the timekeeping subsystem has already solved this problem of trying to determine what the least bad clock is on constrained systems, falling back to jiffies in the worst case. By exporting the raw clock, we can get a decent fallback function for when there's no cycle counter or architecture-specific function.

This series makes the RNG more useful on: m68k, RISC-V, MIPS, ARM32, NIOS II, SPARC32, Xtensa, and Usermode Linux. Previously these platforms would, in certain circumstances, but out of luck with regards to having any type of event timestamping source in the RNG.

Finally, note that this series isn't about "jitter entropy" or other ways of initializing the RNG. That's a different topic for a different thread. Please don't let this discussion veer off into that. Here, I'm just trying to find a good fallback counter/timer for platforms without get_cycles(), a question with limited scope.

If this (or a future revision) looks good to you all and receives the requisite acks, my plan was to take these through the random.git tree for 5.19, so that I can then build on top of it. Alternatively, maybe Thomas wants to take it through his timekeeping tree? Or something else. If anybody has strong preferences, please pipe up.

Thanks,
Jason

Changes v2->v3:
- Name the fallback function random_get_entropy_fallback(), so that it can be changed out as needed.
- Include header with prototype in timekeeping.c to avoid compiler warning.
- Export fallback function symbol.

Changes v1->v2:
- Use ktime_read_raw_clock() instead of sched_clock(), per Thomas' suggestion.
- Drop arm64 change.
- Cleanup header inclusion ordering problem.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Theodore Ts'o <[email protected]>
Cc Dominik Brodowski <[email protected]>
Cc Russell King <[email protected]>
Cc Catalin Marinas <[email protected]>
Cc Will Deacon <[email protected]>
Cc Geert Uytterhoeven <[email protected]>
Cc Thomas Bogendoerfer <[email protected]>
Cc Paul Walmsley <[email protected]>
Cc Palmer Dabbelt <[email protected]>
Cc Albert Ou <[email protected]>
Cc David S. Miller <[email protected]>
Cc Richard Weinberger <[email protected]>
Cc Anton Ivanov <[email protected]>
Cc Johannes Berg <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Dave Hansen <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Chris Zankel <[email protected]>
Cc Max Filippov <[email protected]>
Cc John Stultz <[email protected]>
Cc Stephen Boyd <[email protected]>
Cc Dinh Nguyen <[email protected]>

Jason A. Donenfeld (10):
timekeeping: add raw clock fallback for random_get_entropy()
m68k: use fallback for random_get_entropy() instead of zero
riscv: use fallback for random_get_entropy() instead of zero
mips: use fallback for random_get_entropy() instead of zero
arm: use fallback for random_get_entropy() instead of zero
nios2: use fallback for random_get_entropy() instead of zero
x86: use fallback for random_get_entropy() instead of zero
um: use fallback for random_get_entropy() instead of zero
sparc: use fallback for random_get_entropy() instead of zero
xtensa: use fallback for random_get_entropy() instead of zero

 arch/arm/include/asm/timex.h      |  1 +
 arch/m68k/include/asm/timex.h     |  2 +-
 arch/mips/include/asm/timex.h     |  2 +-
 arch/nios2/include/asm/timex.h    |  2 ++
 arch/riscv/include/asm/timex.h    |  2 +-
 arch/sparc/include/asm/timex_32.h |  4 +---
 arch/um/include/asm/timex.h       |  9 ++-------
 arch/x86/include/asm/tsc.h        | 10 ++++++++++
 arch/xtensa/include/asm/timex.h   |  6 ++----
 include/linux/timex.h             |  8 ++++++++
 kernel/time/timekeeping.c         | 10 ++++++++++
 11 files changed, 39 insertions(+), 17 deletions(-)
Signature · 1 line
2.35.1
#1 lore raw

PATCH v3 1/10 timekeeping: add raw clock fallback for random_get_entropy()

The addition of random_get_entropy_fallback() provides access to whichever time source has the highest frequency, which is useful for gathering entropy on platforms without available cycle counters. It's not necessarily as good as being able to quickly access a cycle counter that the CPU has, but it's still something, even when it falls back to being jiffies-based.

In the event that a given arch does not define get_cycles(), falling back to the get_cycles() default implementation that returns 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Theodore Ts'o <[email protected]>
---
 include/linux/timex.h     |  8 ++++++++
 kernel/time/timekeeping.c | 10 ++++++++++
 2 files changed, 18 insertions(+)
include/linux/timex.h +8 -0
index 5745c90c8800..fbbe34226044 100644
@@ -62,6 +62,8 @@
 #include <linux/types.h>
 #include <linux/param.h>
 
+extern unsigned long random_get_entropy_fallback(void);
+
 #include <asm/timex.h>
 
 #ifndef random_get_entropy
@@ -74,8 +76,14 @@
  *
  * By default we use get_cycles() for this purpose, but individual
  * architectures may override this in their asm/timex.h header file.
+ * If a given arch does not have get_cycles(), then we fallback to
+ * using random_get_entropy_fallback().
  */
+#ifdef get_cycles
 #define random_get_entropy()	((unsigned long)get_cycles())
+#else
+#define random_get_entropy()	random_get_entropy_fallback()
+#endif
 #endif
 
 /*
kernel/time/timekeeping.c +10 -0
index dcdcb85121e4..7372d60c7c65 100644
@@ -17,6 +17,7 @@
 #include <linux/clocksource.h>
 #include <linux/jiffies.h>
 #include <linux/time.h>
+#include <linux/timex.h>
 #include <linux/tick.h>
 #include <linux/stop_machine.h>
 #include <linux/pvclock_gtod.h>
@@ -2380,6 +2381,15 @@ static int timekeeping_validate_timex(const struct __kernel_timex *txc)
 	return 0;
 }
 
+/**
+ * random_get_entropy_fallback - Returns the raw clock source value,
+ * used by random.c for platforms with no valid random_get_entropy().
+ */
+unsigned long random_get_entropy_fallback(void)
+{
+	return tk_clock_read(&tk_core.timekeeper.tkr_mono);
+}
+EXPORT_SYMBOL(random_get_entropy_fallback);
 
 /**
  * do_adjtimex() - Accessor function to NTP __do_adjtimex function
Signature · 1 line
2.35.1
#2 lore raw

Re: [PATCH v3 01/10] timekeeping: add raw clock fallback for random_get_entropy()

kernel/time/timekeeping.c static int timekeeping_validate_timex(const struct __kernel_timex *txc) · line 2392

Quoted 9 lines · Jason A. Donenfeld
kernel/time/timekeeping.c +9 -0
+/**
+ * random_get_entropy_fallback - Returns the raw clock source value,
+ * used by random.c for platforms with no valid random_get_entropy().
+ */
+unsigned long random_get_entropy_fallback(void)
+{
+	return tk_clock_read(&tk_core.timekeeper.tkr_mono);
+}
+EXPORT_SYMBOL(random_get_entropy_fallback);

EXPORT_SYMBOL_GPL() please.

Thanks,

tglx

#3 lore raw

Re: [PATCH v3 01/10] timekeeping: add raw clock fallback for random_get_entropy()

Hi Thomas,

Quoted 13 lines · Thomas Gleixner

kernel/time/timekeeping.c static int timekeeping_validate_timex(const struct __kernel_timex *txc) · line 2392

Quoted 9 lines · Jason A. Donenfeld
kernel/time/timekeeping.c +9 -0
+/**
+ * random_get_entropy_fallback - Returns the raw clock source value,
+ * used by random.c for platforms with no valid random_get_entropy().
+ */
+unsigned long random_get_entropy_fallback(void)
+{
+     return tk_clock_read(&tk_core.timekeeper.tkr_mono);
+}
+EXPORT_SYMBOL(random_get_entropy_fallback);

EXPORT_SYMBOL_GPL() please.

Okay, will do.

Jason

#4 lore raw

PATCH v3 2/10 m68k: use fallback for random_get_entropy() instead of zero

In reply to Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Geert Uytterhoeven <[email protected]>
---
 arch/m68k/include/asm/timex.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
arch/m68k/include/asm/timex.h +1 -1
index 6a21d9358280..f4a7a340f4ca 100644
@@ -35,7 +35,7 @@ static inline unsigned long random_get_entropy(void)
 {
 	if (mach_random_get_entropy)
 		return mach_random_get_entropy();
-	return 0;
+	return random_get_entropy_fallback();
 }
 #define random_get_entropy	random_get_entropy
 
Signature · 1 line
2.35.1
maintainer Acked-by on v3 2/10
#5 lore raw

Re: [PATCH v3 02/10] m68k: use fallback for random_get_entropy() instead of zero

Quoted 9 lines · Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

Quoted 4 lines
Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Geert Uytterhoeven <[email protected]>

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

#6 lore raw

PATCH v3 3/10 riscv: use fallback for random_get_entropy() instead of zero

In reply to Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Paul Walmsley <[email protected]>
Cc Palmer Dabbelt <[email protected]>
---
 arch/riscv/include/asm/timex.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
arch/riscv/include/asm/timex.h +1 -1
index 507cae273bc6..d6a7428f6248 100644
@@ -41,7 +41,7 @@ static inline u32 get_cycles_hi(void)
 static inline unsigned long random_get_entropy(void)
 {
 	if (unlikely(clint_time_val == NULL))
-		return 0;
+		return random_get_entropy_fallback();
 	return get_cycles();
 }
 #define random_get_entropy()	random_get_entropy()
Signature · 1 line
2.35.1
#7 lore raw

PATCH v3 4/10 mips: use fallback for random_get_entropy() instead of zero

In reply to Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Thomas Bogendoerfer <[email protected]>
---
 arch/mips/include/asm/timex.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
arch/mips/include/asm/timex.h +1 -1
index b05bb70a2e46..abc60a6395e3 100644
@@ -94,7 +94,7 @@ static inline unsigned long random_get_entropy(void)
 	else if (likely(imp != PRID_IMP_R6000 && imp != PRID_IMP_R6000A))
 		return read_c0_random();
 	else
-		return 0;	/* no usable register */
+		return random_get_entropy_fallback();	/* no usable register */
 }
 #define random_get_entropy random_get_entropy
 
Signature · 1 line
2.35.1
#8 lore raw

PATCH v3 5/10 arm: use fallback for random_get_entropy() instead of zero

In reply to Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Russell King <[email protected]>
---
 arch/arm/include/asm/timex.h | 1 +
 1 file changed, 1 insertion(+)
arch/arm/include/asm/timex.h +1 -0
index 7c3b3671d6c2..6d1337c169cd 100644
@@ -11,5 +11,6 @@
 
 typedef unsigned long cycles_t;
 #define get_cycles()	({ cycles_t c; read_current_timer(&c) ? 0 : c; })
+#define random_get_entropy() (((unsigned long)get_cycles()) ?: random_get_entropy_fallback())
 
 #endif
Signature · 1 line
2.35.1
#9 lore raw

PATCH v3 6/10 nios2: use fallback for random_get_entropy() instead of zero

In reply to Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Dinh Nguyen <[email protected]>
---
 arch/nios2/include/asm/timex.h | 2 ++
 1 file changed, 2 insertions(+)
arch/nios2/include/asm/timex.h +2 -0
index a769f871b28d..d9a3f426cdda 100644
@@ -9,4 +9,6 @@ typedef unsigned long cycles_t;
 
 extern cycles_t get_cycles(void);
 
+#define random_get_entropy() (((unsigned long)get_cycles()) ?: random_get_entropy_fallback())
+
 #endif
Signature · 1 line
2.35.1
#10 lore raw

PATCH v3 7/10 x86: use fallback for random_get_entropy() instead of zero

In reply to Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

If CONFIG_X86_TSC=n, then it's possible that we're running on a 486 with no RDTSC, so we only need the fallback code for that case.

---
 arch/x86/include/asm/tsc.h | 10 ++++++++++
 1 file changed, 10 insertions(+)
arch/x86/include/asm/tsc.h +10 -0
index 01a300a9700b..194dc1e3f77c 100644
@@ -28,6 +28,16 @@ static inline cycles_t get_cycles(void)
 	return rdtsc();
 }
 
+static inline unsigned long random_get_entropy(void)
+{
+#ifndef CONFIG_X86_TSC
+	if (!boot_cpu_has(X86_FEATURE_TSC))
+		return random_get_entropy_fallback();
+#endif
+	return rdtsc();
+}
+#define random_get_entropy random_get_entropy
+
 extern struct system_counterval_t convert_art_to_tsc(u64 art);
 extern struct system_counterval_t convert_art_ns_to_tsc(u64 art_ns);
 
Signature · 1 line
2.35.1
#11 lore raw

PATCH v3 8/10 um: use fallback for random_get_entropy() instead of zero

In reply to Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

This is accomplished by just including the asm-generic code like on other architectures, which means we can get rid of the empty stub function here.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Richard Weinberger <[email protected]>
Cc Anton Ivanov <[email protected]>
Cc Johannes Berg <[email protected]>
---
 arch/um/include/asm/timex.h | 9 ++-------
 1 file changed, 2 insertions(+), 7 deletions(-)
arch/um/include/asm/timex.h +2 -7
index e392a9a5bc9b..9f27176adb26 100644
@@ -2,13 +2,8 @@
 #ifndef __UM_TIMEX_H
 #define __UM_TIMEX_H
 
-typedef unsigned long cycles_t;
-
-static inline cycles_t get_cycles (void)
-{
-	return 0;
-}
-
 #define CLOCK_TICK_RATE (HZ)
 
+#include <asm-generic/timex.h>
+
 #endif
Signature · 1 line
2.35.1
#12 lore raw

PATCH v3 9/10 sparc: use fallback for random_get_entropy() instead of zero

In reply to Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

This is accomplished by just including the asm-generic code like on other architectures, which means we can get rid of the empty stub function here.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc David S. Miller <[email protected]>
---
 arch/sparc/include/asm/timex_32.h | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)
arch/sparc/include/asm/timex_32.h +1 -3
index 542915b46209..f86326a6f89e 100644
@@ -9,8 +9,6 @@
 
 #define CLOCK_TICK_RATE	1193180 /* Underlying HZ */
 
-/* XXX Maybe do something better at some point... -DaveM */
-typedef unsigned long cycles_t;
-#define get_cycles()	(0)
+#include <asm-generic/timex.h>
 
 #endif
Signature · 1 line
2.35.1
#13 lore raw

PATCH v3 10/10 xtensa: use fallback for random_get_entropy() instead of zero

In reply to Jason A. Donenfeld

In the event that random_get_entropy() can't access a cycle counter or similar, falling back to returning 0 is really not the best we can do. Instead, at least calling random_get_entropy_fallback() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though random_get_entropy_fallback() is super high precision or guaranteed to be entropic, but basically anything that's not zero all the time is better than returning zero all the time.

This is accomplished by just including the asm-generic code like on other architectures, which means we can get rid of the empty stub function here.

Cc Thomas Gleixner <[email protected]>
Cc Arnd Bergmann <[email protected]>
Cc Max Filippov <[email protected]>
---
 arch/xtensa/include/asm/timex.h | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
arch/xtensa/include/asm/timex.h +2 -4
index 233ec75e60c6..3f2462f2d027 100644
@@ -29,10 +29,6 @@
 
 extern unsigned long ccount_freq;
 
-typedef unsigned long long cycles_t;
-
-#define get_cycles()	(0)
-
 void local_timer_setup(unsigned cpu);
 
 /*
@@ -59,4 +55,6 @@ static inline void set_linux_timer (unsigned long ccompare)
 	xtensa_set_sr(ccompare, SREG_CCOMPARE + LINUX_TIMER);
 }
 
+#include <asm-generic/timex.h>
+
 #endif	/* _XTENSA_TIMEX_H */
Signature · 1 line
2.35.1