[PATCH v3 3/5] treewide: use get_random_u32() when possible

[Jason A. Donenfeld]

On Sat, Oct 08, 2022 at 09:53:33PM +0000, David Laight wrote:
> From: Jason A. Donenfeld
> > Sent: 07 October 2022 18:56
> ...
> > > Given these kinds of less mechanical changes, it may make sense to split
> > > these from the "trivial" conversions in a treewide patch. The chance of
> > > needing a revert from the simple 1:1 conversions is much lower than the
> > > need to revert by-hand changes.
> > >
> > > The Cocci script I suggested in my v1 review gets 80% of the first
> > > patch, for example.
> > 
> > I'll split things up into a mechanical step and a non-mechanical step.
> > Good idea.
> 
> I'd also do something about the 'get_random_int() & 3' cases.
> (ie remainder by 2^n-1)
> These can be converted to 'get_random_u8() & 3' (etc).
> So they only need one random byte (not 4) and no multiply.
> 
> Possibly something based on (the quickly typed, and not C):
> #define get_random_below(val) [
> 	if (builtin_constant(val))
> 		BUILD_BUG_ON(!val || val > 0x100000000ull)
> 		if (!(val & (val - 1)) {
> 			if (val <= 0x100)
> 				return get_random_u8() & (val - 1);
> 			if (val <= 0x10000)
> 				return get_random_u16() & (val - 1);
> 			return get_random_u32() & (val - 1);
> 		}
> 	}
> 	BUILD_BUG_ON(sizeof (val) > 4);
> 	return ((u64)get_random_u32() * val) >> 32;

This is already how the prandom_u32_max() implementation works, as
suggested in the cover letter. The multiplication by constants in it
reduces to bit shifts and you already get all the manual masking
possible.

> get_random_below() is a much better name than prandom_u32_max().

Yes, but that name is reserved for when I succeed at making a function
that bounds with a uniform distribution. prandom_u32_max()'s
distribution is non-uniform since it doesn't do rejection sampling. Work
in progress is on https://git.zx2c4.com/linux-rng/commit/?h=jd/get_random_u32_below .
But out of common respect for this already huge thread with a massive
CC list, if you want to bikeshed my WIP stuff, please start a new thread
for that and not bog this one down. IOW, no need to reply here directly.
That'd annoy me.

Jason