RE: [crng-random:jd/get_random_u32_below 23/23] include/linux/random.h:64:69: sparse: sparse: cast truncates bits from constant value (1f4 becomes f4)

[David Laight]

From: kernel test robot <lkp@xxxxxxxxx>
> Sent: 10 October 2022 00:32
> To: Jason A. Donenfeld <zx2c4@xxxxxxxxxx>
...

I'm missing the main mailing list email for this change.
I'm guessing the non-inlined code for non-constant ceil
is similar.

> vim +64 include/linux/random.h
> 
>     53
>     54	u32 __get_random_u32_below(u32 ceil);
>     55	/* Returns a random integer in the interval [0, ceil), with uniform distribution. */
>     56	static inline u32 get_random_u32_below(u32 ceil)
>     57	{
>     58		if (!__builtin_constant_p(ceil))
>     59			return __get_random_u32_below(ceil);
>     60
>     61		for (;;) {
>     62			if (ceil <= 1U << 8) {
>     63				u32 mult = ceil * get_random_u8();
>   > 64				if (is_power_of_2(ceil) || (u8)mult >= -(u8)ceil % ceil)
>     65					return mult >> 8;

If you are going to check is_power_of_2() then you might as well do:
		u32 val = get_random_u8();
		if (is_power_of_2(ceil))
			return ceil == 0x100 ? val : val & (ceil - 1);
Except that you don't want to loop on zero - so !(ceil & (ceil - 1))
is arguably better since it is absolutely explicit.
Or (for the constant case) a BUILD_BUG_ON(ceil == 0)?

Notwithstanding the completely untested code the bot complained about
doing a division here is unnecessary and expensive.
(Except this is the constant path...)
I think:
		val *= ceil;
		if ((val + ceil - 1) >> 8 == val >> 8)
			return val >> 8;
has the desired property.

It is also definitely worth a comment like:
	/* In the worst case this loops 50% of the time.
	 * While the loop is unbounded the average number
	 * of iterations (for the worst ceil) is 2. */

There are also a lot of places where having the values
evenly spread is enough - even if some values are returned
one more time than others.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)