Skip to contentSkip to conversation

archs/random: fallback to using ktime_read_raw_clock() if no cycle counter

PATCH Superseded Jason A. Donenfeld 2 participants 14 messages Apr 10, 2022 – Apr 11, 2022

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

v2 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

v2 cover archs/random: fallback to using ktime_read_raw_clock() if 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.

Thanks,
Jason

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 (11):
timekeeping: add accessor for raw clock
timekeeping: use ktime_read_raw_clock() for random_get_entropy() if no
get_cycles()
m68k: use ktime_read_raw_clock() for random_get_entropy() instead of
zero
riscv: use ktime_read_raw_clock() for random_get_entropy() instead of
zero
mips: use ktime_read_raw_clock() for random_get_entropy() instead of
zero
arm: use ktime_read_raw_clock() for random_get_entropy() instead of
zero
nios2: use ktime_read_raw_clock() for random_get_entropy() instead of
zero
x86: use ktime_read_raw_clock() for random_get_entropy() instead of
zero
um: use ktime_read_raw_clock() for random_get_entropy() instead of
zero
sparc: use ktime_read_raw_clock() for random_get_entropy() instead of
zero
xtensa: use ktime_read_raw_clock() 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         |  8 ++++++++
 11 files changed, 37 insertions(+), 17 deletions(-)
Signature · 1 line
2.35.1
#1 lore raw

PATCH v2 1/11 timekeeping: add accessor for raw clock

This 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.

It's defined in linux/timex.h rather than linux/timekeeping.h, because the latter cannot be included easily from asm/ headers, and generally shouldn't be used outside of this rather narrow purpose. It's a ktime function, but it's not the usual ktime API.

---
 include/linux/timex.h     | 2 ++
 kernel/time/timekeeping.c | 8 ++++++++
 2 files changed, 10 insertions(+)
include/linux/timex.h +2 -0
index 5745c90c8800..56502b338287 100644
@@ -62,6 +62,8 @@
 #include <linux/types.h>
 #include <linux/param.h>
 
+extern u64 ktime_read_raw_clock(void);
+
 #include <asm/timex.h>
 
 #ifndef random_get_entropy
kernel/time/timekeeping.c +8 -0
index dcdcb85121e4..0d04d2e8b94b 100644
@@ -939,6 +939,14 @@ ktime_t ktime_get_raw(void)
 }
 EXPORT_SYMBOL_GPL(ktime_get_raw);
 
+/**
+ * ktime_read_raw_clock - Returns the raw clock source value
+ */
+u64 ktime_read_raw_clock(void)
+{
+	return tk_clock_read(&tk_core.timekeeper.tkr_mono);
+}
+
 /**
  * ktime_get_ts64 - get the monotonic clock in timespec64 format
  * @ts:		pointer to timespec variable
Signature · 1 line
2.35.1
#2 lore raw

PATCH v2 2/11 timekeeping: use ktime_read_raw_clock() for random_get_entropy() if no get_cycles()

In reply to Jason A. Donenfeld

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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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 | 6 ++++++
 1 file changed, 6 insertions(+)
include/linux/timex.h +6 -0
index 56502b338287..4050f68c34cb 100644
@@ -76,8 +76,14 @@ extern u64 ktime_read_raw_clock(void);
  *
  * 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 sched_clock().
  */
+#ifdef get_cycles
 #define random_get_entropy()	((unsigned long)get_cycles())
+#else
+#define random_get_entropy()	((unsigned long)ktime_read_raw_clock())
+#endif
 #endif
 
 /*
Signature · 1 line
2.35.1
#3 lore raw

PATCH v2 3/11 m68k: use ktime_read_raw_clock() 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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..5351b10e1b18 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 ktime_read_raw_clock();
 }
 #define random_get_entropy	random_get_entropy
 
Signature · 1 line
2.35.1
#4 lore raw

Re: [PATCH v2 03/11] m68k: use ktime_read_raw_clock() for random_get_entropy() instead of zero

Quoted 21 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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 +0 -0
index 6a21d9358280..5351b10e1b18 100644

arch/m68k/include/asm/timex.h static inline unsigned long random_get_entropy(void) · line 38

Quoted 5 lines
arch/m68k/include/asm/timex.h +1 -1
@@ -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 ktime_read_raw_clock();

I'd rather do something like this in a common header:

unsigned long random_get_entropy_fallback(void);

and use random_get_entropy_fallback() in the architecture specific files.

That way you can encapsulate the fallback implementation in the random code and if it turns out that ktime_read_raw_clock() is a stupid idea or someone has a better idea then you have to change exactly one place and not patch the whole tree again.

Thanks,

tglx

#5 lore raw

Re: [PATCH v2 03/11] m68k: use ktime_read_raw_clock() for random_get_entropy() instead of zero

Hi Thomas,

Quoted 15 lines · Thomas Gleixner

arch/m68k/include/asm/timex.h static inline unsigned long random_get_entropy(void) · line 38

Quoted 10 lines
arch/m68k/include/asm/timex.h +1 -1
index 6a21d9358280..5351b10e1b18 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 ktime_read_raw_clock();

I'd rather do something like this in a common header:

unsigned long random_get_entropy_fallback(void);

Quoted 7 lines

and use random_get_entropy_fallback() in the architecture specific files.

That way you can encapsulate the fallback implementation in the random code and if it turns out that ktime_read_raw_clock() is a stupid idea or someone has a better idea then you have to change exactly one place and not patch the whole tree again.

Absolutely. That's a good idea. I'll do that for v3.

Jason

#6 lore raw

PATCH v2 4/11 riscv: use ktime_read_raw_clock() 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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..b320afede88a 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 ktime_read_raw_clock();
 	return get_cycles();
 }
 #define random_get_entropy()	random_get_entropy()
Signature · 1 line
2.35.1
#7 lore raw

PATCH v2 5/11 mips: use ktime_read_raw_clock() 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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..fa6a5ca20b46 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 ktime_read_raw_clock();	/* no usable register */
 }
 #define random_get_entropy random_get_entropy
 
Signature · 1 line
2.35.1
#8 lore raw

PATCH v2 6/11 arm: use ktime_read_raw_clock() 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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..d0b32ce87254 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() ?: ktime_read_raw_clock()))
 
 #endif
Signature · 1 line
2.35.1
#9 lore raw

PATCH v2 7/11 nios2: use ktime_read_raw_clock() 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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..3c74d3e337a0 100644
@@ -9,4 +9,6 @@ typedef unsigned long cycles_t;
 
 extern cycles_t get_cycles(void);
 
+#define random_get_entropy() ((unsigned long)(get_cycles() ?: ktime_read_raw_clock()))
+
 #endif
Signature · 1 line
2.35.1
#10 lore raw

PATCH v2 8/11 x86: use ktime_read_raw_clock() 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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..dad3027bf6a2 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 ktime_read_raw_clock();
+#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 v2 9/11 um: use ktime_read_raw_clock() 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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 v2 10/11 sparc: use ktime_read_raw_clock() 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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 v2 11/11 xtensa: use ktime_read_raw_clock() 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 ktime_read_raw_clock() would be preferable, because that always needs to return _something_, even falling back to jiffies eventually. It's not as though ktime_read_raw_clock() 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