| Message ID | 20260311070416.972667-27-hch@lst.de (mailing list archive) |
|---|---|
| State | Handled Elsewhere |
| Headers | show |
| Series | [01/27] xor: assert that xor_blocks is not from preemptible user context | expand |
On Wed, Mar 11, 2026 at 08:03:58AM +0100, Christoph Hellwig wrote: > Factor out the guts of __get_random_u32_below into a new helper, > so that callers with their own prng state can reuse this code. > > Signed-off-by: Christoph Hellwig <hch@lst.de> I think I'd prefer that the test just uses the mod operation instead, like many of the existing tests do: prandom_u32_state(&rng) % ceil Yes, when ceil isn't a power of 2 the result isn't uniformly distributed. But that's perfectly fine for these tests, especially with the values of ceil being used being far smaller than U32_MAX. There's been an effort to keep the cryptographic random number generator (drivers/char/random.c and include/linux/random.h) separate from the non-cryptographic random number generator (lib/random32.c and include/linux/prandom.h). This patch feels like it's going in a slightly wrong direction, where random.c gains a function that's used with both cryptographic and non-cryptographic random numbers. And if someone actually needs a fully unform distribution, then they'd probably want cryptographic random numbers as well. So I'm not sure the proposed combination of "fully uniform non-cryptographic random numbers" makes much sense. Plus the '% ceil' implementation is much easier to understand. - Eric
On Wed, 11 Mar 2026 15:29:35 -0700 Eric Biggers <ebiggers@kernel.org> wrote: > On Wed, Mar 11, 2026 at 08:03:58AM +0100, Christoph Hellwig wrote: > > Factor out the guts of __get_random_u32_below into a new helper, > > so that callers with their own prng state can reuse this code. > > > > Signed-off-by: Christoph Hellwig <hch@lst.de> > > I think I'd prefer that the test just uses the mod operation instead, > like many of the existing tests do: > > prandom_u32_state(&rng) % ceil Or possibly what the old code used: (prandom_u32_state(&rnd) * (u64)ceil) >> 32 Which distributes the values evenly across the range although some values happen 1 more time than others. I suspect that is good enough for a lot of the users of the cryptographic random number generator as well. David > > Yes, when ceil isn't a power of 2 the result isn't uniformly > distributed. But that's perfectly fine for these tests, especially with > the values of ceil being used being far smaller than U32_MAX. > > There's been an effort to keep the cryptographic random number generator > (drivers/char/random.c and include/linux/random.h) separate from the > non-cryptographic random number generator (lib/random32.c and > include/linux/prandom.h). This patch feels like it's going in a > slightly wrong direction, where random.c gains a function that's used > with both cryptographic and non-cryptographic random numbers. > > And if someone actually needs a fully unform distribution, then they'd > probably want cryptographic random numbers as well. > > So I'm not sure the proposed combination of "fully uniform > non-cryptographic random numbers" makes much sense. > > Plus the '% ceil' implementation is much easier to understand. > > - Eric >
On Wed, Mar 11, 2026 at 08:03:58AM +0100, Christoph Hellwig wrote: > Factor out the guts of __get_random_u32_below into a new helper, > so that callers with their own prng state can reuse this code. What Eric said. random.c is not "some library code" meant to be pulled apart like this. If you think there are some good general purpose arithmetic functions, by all means develop shared infrastructure in the right place. But I think for this super simple/trivial _below function, you can probably just place it additionally where you're using it, without needing to touch random.c.
diff --git a/drivers/char/random.c b/drivers/char/random.c index 7ff4d29911fd..23b5addf02fb 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -544,18 +544,16 @@ DEFINE_BATCHED_ENTROPY(u16) DEFINE_BATCHED_ENTROPY(u32) DEFINE_BATCHED_ENTROPY(u64) -u32 __get_random_u32_below(u32 ceil) +/* + * This is the slow path for variable ceil. It is still fast, most of the time, + * by doing traditional reciprocal multiplication and opportunistically + * comparing the lower half to ceil itself, before falling back to computing a + * larger bound, and then rejecting samples whose lower half would indicate a + * range indivisible by ceil. The use of `-ceil % ceil` is analogous to `2^32 % + * ceil`, but is computable in 32-bits. + */ +u32 __limit_random_u32_below(u32 ceil, u32 rand) { - /* - * This is the slow path for variable ceil. It is still fast, most of - * the time, by doing traditional reciprocal multiplication and - * opportunistically comparing the lower half to ceil itself, before - * falling back to computing a larger bound, and then rejecting samples - * whose lower half would indicate a range indivisible by ceil. The use - * of `-ceil % ceil` is analogous to `2^32 % ceil`, but is computable - * in 32-bits. - */ - u32 rand = get_random_u32(); u64 mult; /* @@ -577,6 +575,12 @@ u32 __get_random_u32_below(u32 ceil) } return mult >> 32; } +EXPORT_SYMBOL_GPL(__limit_random_u32_below); + +u32 __get_random_u32_below(u32 ceil) +{ + return __limit_random_u32_below(ceil, get_random_u32()); +} EXPORT_SYMBOL(__get_random_u32_below); #ifdef CONFIG_SMP diff --git a/include/linux/random.h b/include/linux/random.h index 8a8064dc3970..54401dd53f68 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -50,6 +50,7 @@ static inline unsigned long get_random_long(void) #endif } +u32 __limit_random_u32_below(u32 ceil, u32 rand); u32 __get_random_u32_below(u32 ceil); /*
Factor out the guts of __get_random_u32_below into a new helper, so that callers with their own prng state can reuse this code. Signed-off-by: Christoph Hellwig <hch@lst.de> --- drivers/char/random.c | 26 +++++++++++++++----------- include/linux/random.h | 1 + 2 files changed, 16 insertions(+), 11 deletions(-)