Re: [PATCH] random: get_random_u64_below()

[David Laight]

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  
>