linux-kernel - 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)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 10 Oct 2022 17:18:40 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     "Jason A. Donenfeld" <zx2c4@...nel.org>
CC:     "kbuild-all@...ts.01.org" <kbuild-all@...ts.01.org>,
        "zx2c4@...nel.org" <zx2c4@...nel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: 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)

From: kernel test robot <lkp@...el.com>
> Sent: 10 October 2022 00:32
> To: Jason A. Donenfeld <zx2c4@...nel.org>
...

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)