random: add helpers for random numbers with given floor or range
Jason A. Donenfeld
maintainerPATCH v2 1/1 random: add helpers for random numbers with given floor or range
Now that we have get_random_u32_below(), it's nearly trivial to make inline helpers to compute get_random_u32_above() and get_random_u32_inclusive(), which will help clean up open coded loops and manual computations throughout the tree.
One snag is that in order to make get_random_u32_inclusive() operate on closed intervals, we have to do some (unlikely) special case handling if get_random_u32_interval(0, U32_MAX) is called. The least expensive way of doing this is actually to adjust the slowpath of get_random_u32_below() to have its undefined 0 result just return the output of get_random_u32().
---
Changes v1->v2:
- Rename get_random_u32_between() to get_random_u32_inclusive(), and make it a closed interval.
drivers/char/random.c | 17 ++++++++++++++++- include/linux/random.h | 25 +++++++++++++++++++++++++ 2 files changed, 41 insertions(+), 1 deletion(-)
drivers/char/random.c +16 -1
@@ -161,6 +161,8 @@ EXPORT_SYMBOL(wait_for_random_bytes);* u16 get_random_u16() * u32 get_random_u32() * u32 get_random_u32_below(u32 ceil) +* u32 get_random_u32_above(u32 floor) +* u32 get_random_u32_inclusive(u32 ceil, u32 floor) * u64 get_random_u64() * unsigned long get_random_long() *
@@ -522,7 +524,20 @@ u32 __get_random_u32_below(u32 ceil)* of `-ceil % ceil` is analogous to `2^32 % ceil`, but is computable * in 32-bits. */ -u64 mult = (u64 )ceil *get_random_u32 (); +u64 mult; + +/* +* This function is technically undefined for ceil == 0, and in fact +* for the non-underscored constant version in the header, we build bug +* on that. But for the non-constant case, it's convenient to have that +* evaluate to being a straight call to get_random_u32(), so that +* get_random_u32_inclusive() can work over its whole range without +* undefined behavior. +*/ +if (unlikely (!ceil)) +return get_random_u32 (); + + mult = (u64 )ceil *get_random_u32 ();if (unlikely ((u32 )mult < ceil)) {u32 bound = -ceil % ceil;while (unlikely ((u32 )mult < bound))
include/linux/random.h +25 -0
@@ -91,6 +91,31 @@ static inline u32 get_random_u32_below(u32 ceil) } } +/* +* Returns a random integer in the interval (floor, U32_MAX], with uniform +* distribution, suitable for all uses. Fastest when floor is a constant, but +* still fast for variable floor as well. +*/ +static inline u32 get_random_u32_above (u32 floor) +{ +BUILD_BUG_ON_MSG (__builtin_constant_p (floor) && floor ==U32_MAX , +"get_random_u32_above() must take floor < U32_MAX" ); +return floor +1 +get_random_u32_below (U32_MAX - floor); +} + +/* +* Returns a random integer in the interval [floor, ceil], with uniform +* distribution, suitable for all uses. Fastest when floor and ceil are +* constant, but still fast for variable floor and ceil as well. +*/ +static inline u32 get_random_u32_inclusive (u32 floor,u32 ceil) +{ +BUILD_BUG_ON_MSG (__builtin_constant_p (floor) &&__builtin_constant_p (ceil) && + (floor > ceil || ceil - floor ==U32_MAX ), +"get_random_u32_inclusive() must take floor <= ceil" ); +return floor +get_random_u32_below (ceil - floor +1 ); +} +/* * On 64-bit architectures, protect against non-terminated C string overflows * by zeroing out the first byte of the canary; this leaves 56 bits of entropy.
Signature · 1 line
2.38.1
drivers/char/random.c EXPORT_SYMBOL(wait_for_random_bytes); · line 165
Quoted 10 lines · Jason A. Donenfeld
drivers/char/random.c +2
-0@@ -161,6 +161,8 @@ EXPORT_SYMBOL(wait_for_random_bytes);* u16 get_random_u16() * u32 get_random_u32() * u32 get_random_u32_below(u32 ceil) +* u32 get_random_u32_above(u32 floor) +* u32 get_random_u32_inclusive(u32 ceil, u32 floor)
floor, ceil)
Quoted 2 lines
drivers/char/random.c +0
-0* u64 get_random_u64() * unsigned long get_random_long()
Signature · 1 line
~Randy
Jason A. Donenfeld
maintainerPATCH v3 1/1 random: add helpers for random numbers with given floor or range
Now that we have get_random_u32_below(), it's nearly trivial to make inline helpers to compute get_random_u32_above() and get_random_u32_inclusive(), which will help clean up open coded loops and manual computations throughout the tree.
One snag is that in order to make get_random_u32_inclusive() operate on closed intervals, we have to do some (unlikely) special case handling if get_random_u32_interval(0, U32_MAX) is called. The least expensive way of doing this is actually to adjust the slowpath of get_random_u32_below() to have its undefined 0 result just return the output of get_random_u32(). We can make this basically free by calling get_random_u32() before the branch, so that the branch latency gets interleaved.
---v2->v3:
- Fix doc comment argument order.
- Interleave !ceil check with get_random_u32() call to make branch ~free.
drivers/char/random.c | 18 +++++++++++++++++- include/linux/random.h | 25 +++++++++++++++++++++++++ 2 files changed, 42 insertions(+), 1 deletion(-)
drivers/char/random.c +17 -1
@@ -161,6 +161,8 @@ EXPORT_SYMBOL(wait_for_random_bytes);* u16 get_random_u16() * u32 get_random_u32() * u32 get_random_u32_below(u32 ceil) +* u32 get_random_u32_above(u32 floor) +* u32 get_random_u32_inclusive(u32 floor, u32 ceil) * u64 get_random_u64() * unsigned long get_random_long() *
@@ -522,7 +524,21 @@ u32 __get_random_u32_below(u32 ceil)* of `-ceil % ceil` is analogous to `2^32 % ceil`, but is computable * in 32-bits. */ -u64 mult = (u64 )ceil *get_random_u32 (); +u32 rand =get_random_u32 (); +u64 mult; + +/* +* This function is technically undefined for ceil == 0, and in fact +* for the non-underscored constant version in the header, we build bug +* on that. But for the non-constant case, it's convenient to have that +* evaluate to being a straight call to get_random_u32(), so that +* get_random_u32_inclusive() can work over its whole range without +* undefined behavior. +*/ +if (unlikely (!ceil)) +return rand; + + mult = (u64 )ceil * rand;if (unlikely ((u32 )mult < ceil)) {u32 bound = -ceil % ceil;while (unlikely ((u32 )mult < bound))
include/linux/random.h +25 -0
@@ -91,6 +91,31 @@ static inline u32 get_random_u32_below(u32 ceil) } } +/* +* Returns a random integer in the interval (floor, U32_MAX], with uniform +* distribution, suitable for all uses. Fastest when floor is a constant, but +* still fast for variable floor as well. +*/ +static inline u32 get_random_u32_above (u32 floor) +{ +BUILD_BUG_ON_MSG (__builtin_constant_p (floor) && floor ==U32_MAX , +"get_random_u32_above() must take floor < U32_MAX" ); +return floor +1 +get_random_u32_below (U32_MAX - floor); +} + +/* +* Returns a random integer in the interval [floor, ceil], with uniform +* distribution, suitable for all uses. Fastest when floor and ceil are +* constant, but still fast for variable floor and ceil as well. +*/ +static inline u32 get_random_u32_inclusive (u32 floor,u32 ceil) +{ +BUILD_BUG_ON_MSG (__builtin_constant_p (floor) &&__builtin_constant_p (ceil) && + (floor > ceil || ceil - floor ==U32_MAX ), +"get_random_u32_inclusive() must take floor <= ceil" ); +return floor +get_random_u32_below (ceil - floor +1 ); +} +/* * On 64-bit architectures, protect against non-terminated C string overflows * by zeroing out the first byte of the canary; this leaves 56 bits of entropy.
Signature · 1 line
2.38.1
Quoted 14 lines · Jason A. Donenfeld
Now that we have
get_random_u32_below(), it's nearly trivial to make inline helpers to computeget_random_u32_above()andget_random_u32_inclusive(), which will help clean up open coded loops and manual computations throughout the tree.One snag is that in order to make
get_random_u32_inclusive()operate on closed intervals, we have to do some (unlikely) special case handling ifget_random_u32_interval(0, U32_MAX)is called. The least expensive way of doing this is actually to adjust the slowpath ofget_random_u32_below()to have its undefined 0 result just return the output ofget_random_u32(). We can make this basically free by callingget_random_u32()before the branch, so that the branch latency gets interleaved.
Quoted 1 line
Signed-off-by Jason A. Donenfeld <[email protected]>
I really like these -- unambiguous! :) Thanks for adjusting this API.
-Kees
Signature · 1 line
Kees Cook