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: Jason A. Donenfeld
> Sent: 10 October 2022 18:54
> 
> On Mon, Oct 10, 2022 at 05:18:40PM +0000, David Laight wrote:
> > 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.
> 
> It's part of a development tree I already linked you to. It's not done
> yet. This alert is just about needing a __force.

I keep thinking about this one.
sparse is being stupid because it is looking at code that cade be reached.
'ceil' must be 500 so the test at line 62 is false.
But what is the cast for?
Line 64 is only executed when ceil is <= 256 and the condition
only matters when ceil <= 255 - so the cast cannot be needed.

I think you might be trying to do 8-bit arithmetic - but you
should know it gets promoted to 'int' (and then to unsigned int).
What might do what you intended is (u8)~ceil % ceil.
But that is the same as (0xff - ceil) % ceil.
Which is the same as 0xff % ceil.

A quick check with ceil == 5 gives the wrong answer
as all values get accepted - and one need to be excluded.
So you either need (mult & 0xff) > 0xff % ceil
or (mult & 0xff) >= 0x100 % ceil.
The latter version is also right for powers of 2
except that the compiler won't like the xxx > 0u test
because it is always true.

	David

> 
> >
> > > 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))
> 
> I thought I opted out of the Laight drive-bys?
> 
> Either way, I don't understand your comments or how they pertain to the
> current code in that unfinished development branch. Please just send
> real patches.
> 
> Jason

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