Re: [PATCH] random: get_random_u64_below()
From: David Laight
Date: Sat Mar 15 2025 - 09:58:38 EST
On Sat, 15 Mar 2025 13:52:34 +0000
David Laight <david.laight.linux@xxxxxxxxx> wrote:
> On Thu, 13 Mar 2025 12:38:10 -0400
> Kent Overstreet <kent.overstreet@xxxxxxxxx> wrote:
>
> > bcachefs needs this, for sampling devices to read from based on squared
> > device latencies.
> >
> > this uses the same algorithm as get_random_u32_below: since the multiply
> > uses the top and bottom halves separately, it works out fairly well.
>
> Adding two separate copies of much the same code is silly.
> Given what the code is doing, does it ever make any sense to inline it.
>
> Inlining the original get_random_u32_below(ceil) that did
> (random_u32() * ((1ull << 32) / ceil) >> 32
Brain fade, it is just (random_u32() * (u64)ceil) >> 32
> (for constant ceil) made sense.
> While good enough for most purposes it was replaced by the much more
> expensive function that guarantees that all the output values are
> equally likely - rather than just evenly distributed.
>
> David
>
> >
> > Cc: "Theodore Ts'o" <tytso@xxxxxxx> (maintainer:RANDOM NUMBER DRIVER)
> > Cc: "Jason A. Donenfeld" <Jason@xxxxxxxxx> (maintainer:RANDOM NUMBER DRIVER)
> > Signed-off-by: Kent Overstreet <kent.overstreet@xxxxxxxxx>
> > ---
> > drivers/char/random.c | 22 ++++++++++++++++++++++
> > include/linux/random.h | 22 ++++++++++++++++++++++
> > 2 files changed, 44 insertions(+)
> >
> > diff --git a/drivers/char/random.c b/drivers/char/random.c
> > index 2581186fa61b..84808300044c 100644
> > --- a/drivers/char/random.c
> > +++ b/drivers/char/random.c
> > @@ -588,6 +588,28 @@ u32 __get_random_u32_below(u32 ceil)
> > }
> > EXPORT_SYMBOL(__get_random_u32_below);
> >
> > +u64 __get_random_u64_below(u64 ceil)
> > +{
> > + if (unlikely(!ceil))
> > + return get_random_u64();
> > + if (ceil <= U32_MAX)
> > + return __get_random_u32_below(ceil);
> > +
> > + u64 rand = get_random_u64();
> > + u64 mult = ceil * rand;
> > +
> > + if (unlikely(mult < ceil)) {
> > + u64 bound = -ceil % ceil;
> > + while (unlikely(mult < bound)) {
> > + rand = get_random_u64();
> > + mult = ceil * rand;
> > + }
> > + }
> > +
> > + return mul_u64_u64_shr(ceil, rand, 64);
> > +}
> > +EXPORT_SYMBOL(__get_random_u64_below);
> > +
> > #ifdef CONFIG_SMP
> > /*
> > * This function is called when the CPU is coming up, with entry
> > diff --git a/include/linux/random.h b/include/linux/random.h
> > index 333cecfca93f..b025bf3d8f27 100644
> > --- a/include/linux/random.h
> > +++ b/include/linux/random.h
> > @@ -6,6 +6,7 @@
> > #include <linux/bug.h>
> > #include <linux/kernel.h>
> > #include <linux/list.h>
> > +#include <linux/math64.h>
> >
> > #include <uapi/linux/random.h>
> >
> > @@ -90,6 +91,27 @@ static inline u32 get_random_u32_below(u32 ceil)
> > }
> > }
> >
> > +u64 __get_random_u64_below(u64 ceil);
> > +
> > +static inline u64 get_random_u64_below(u32 ceil)
> > +{
> > + if (!__builtin_constant_p(ceil))
> > + return __get_random_u64_below(ceil);
> > +
> > + BUILD_BUG_ON_MSG(!ceil, "get_random_u64_below() must take ceil > 0");
> > + if (ceil <= 1)
> > + return 0;
> > + if (ceil <= U32_MAX)
> > + return get_random_u32_below(ceil);
> > +
> > + for (;;) {
> > + u64 rand = get_random_u64();
> > + u64 mult = ceil * rand;
> > + if (likely(mult >= -ceil % ceil))
> > + return mul_u64_u64_shr(ceil, rand, 64);
> > + }
> > +}
> > +
> > /*
> > * Returns a random integer in the interval (floor, U32_MAX], with uniform
> > * distribution, suitable for all uses. Fastest when floor is a constant, but
>