tree: git://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git jd/get_random_u32_below
head: 64e577cf130af4c0a0cb0dcc9cd64de6525ab80f
commit: 5c94e468bcbf3081935eb45d6ce9137b2dc78b77 [24/26] ext4: use get_random_u32_below() for more efficient selection
config: i386-randconfig-s001-20221010
compiler: gcc-11 (Debian 11.3.0-5) 11.3.0
reproduce:
# apt-get install sparse
# sparse version: v0.6.4-39-gce1a6720-dirty
# https://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git/commit/?id=5c94e468bcbf3081935eb45d6ce9137b2dc78b77
git remote add crng-random git://git.kernel.org/pub/scm/linux/kernel/git/crng/random.git
git fetch --no-tags crng-random jd/get_random_u32_below
git checkout 5c94e468bcbf3081935eb45d6ce9137b2dc78b77
# save the config file
mkdir build_dir && cp config build_dir/.config
make W=1 C=1 CF='-fdiagnostic-prefix -D__CHECK_ENDIAN__' O=build_dir ARCH=i386 SHELL=/bin/bash
If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <[email protected]>
sparse warnings: (new ones prefixed by >>)
fs/ext4/mmp.c: note: in included file (through include/linux/nodemask.h, include/linux/list_lru.h, include/linux/fs.h):
>> include/linux/random.h:64:77: sparse: sparse: cast truncates bits from constant value (e24d4d50 becomes 50)
>> include/linux/random.h:68:79: sparse: sparse: cast truncates bits from constant value (e24d4d50 becomes 4d50)
vim +64 include/linux/random.h
c440408cf6901e Jason A. Donenfeld 2017-01-22 53
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 54 u32 __get_random_u32_below(u32 ceil);
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 55 /* Returns a random integer in the interval [0, ceil), with uniform distribution. */
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 56 static inline u32 get_random_u32_below(u32 ceil)
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 57 {
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 58 if (!__builtin_constant_p(ceil))
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 59 return __get_random_u32_below(ceil);
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 60
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 61 for (;;) {
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 62 if (ceil <= 1U << 8) {
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 63 u32 mult = ceil * get_random_u8();
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 @64 if (is_power_of_2(ceil) || (u8)mult >= -(__force u8)ceil % ceil)
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 65 return mult >> 8;
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 66 } else if (ceil <= 1U << 16) {
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 67 u32 mult = ceil * get_random_u16();
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 @68 if (is_power_of_2(ceil) || (u16)mult >= -(__force u16)ceil % ceil)
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 69 return mult >> 16;
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 70 } else {
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 71 u64 mult = (u64)ceil * get_random_u32();
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 72 if (is_power_of_2(ceil) || (u32)mult >= -ceil % ceil)
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 73 return mult >> 32;
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 74 }
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 75 }
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 76 }
dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 77
:::::: The code at line 64 was first introduced by commit
:::::: dbc0933c6b1d8c21eb938d44038ae0ffaf930c0c random: use rejection sampling for uniform bounded random integers
:::::: TO: Jason A. Donenfeld <[email protected]>
:::::: CC: Jason A. Donenfeld <[email protected]>
--
0-DAY CI Kernel Test Service
https://01.org/lkp
On 11/10/2022 11.59, kernel test robot wrote:
> c440408cf6901e Jason A. Donenfeld 2017-01-22 53
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 54 u32 __get_random_u32_below(u32 ceil);
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 55 /* Returns a random integer in the interval [0, ceil), with uniform distribution. */
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 56 static inline u32 get_random_u32_below(u32 ceil)
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 57 {
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 58 if (!__builtin_constant_p(ceil))
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 59 return __get_random_u32_below(ceil);
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 60
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 61 for (;;) {
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 62 if (ceil <= 1U << 8) {
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 63 u32 mult = ceil * get_random_u8();
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 @64 if (is_power_of_2(ceil) || (u8)mult >= -(__force u8)ceil % ceil)
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 65 return mult >> 8;
I don't have a good suggestion for how to silence sparse, but I think
the cast and unary minus here needs to be interchanged. I.e., the
condition should be
if (is_power_of_2(ceil) || (u8)mult >= ((__force u8)-ceil) % ceil)
Otherwise it fails to provide uniform distribution for ceil=11, 19, 22,
23, ... [these are the numbers that are not divisors of 2^32-2^8].
Rasmus
On Tue, Oct 11, 2022 at 03:21:44PM +0200, Rasmus Villemoes wrote:
> On 11/10/2022 11.59, kernel test robot wrote:
>
> > c440408cf6901e Jason A. Donenfeld 2017-01-22 53
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 54 u32 __get_random_u32_below(u32 ceil);
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 55 /* Returns a random integer in the interval [0, ceil), with uniform distribution. */
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 56 static inline u32 get_random_u32_below(u32 ceil)
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 57 {
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 58 if (!__builtin_constant_p(ceil))
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 59 return __get_random_u32_below(ceil);
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 60
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 61 for (;;) {
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 62 if (ceil <= 1U << 8) {
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 63 u32 mult = ceil * get_random_u8();
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 @64 if (is_power_of_2(ceil) || (u8)mult >= -(__force u8)ceil % ceil)
> > dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 65 return mult >> 8;
>
> I don't have a good suggestion for how to silence sparse, but I think
> the cast and unary minus here needs to be interchanged. I.e., the
> condition should be
>
> if (is_power_of_2(ceil) || (u8)mult >= ((__force u8)-ceil) % ceil)
>
> Otherwise it fails to provide uniform distribution for ceil=11, 19, 22,
> 23, ... [these are the numbers that are not divisors of 2^32-2^8].
Thanks! Note that this is an incomplete dev branch I haven't posted to
the ML yet. As for the sparse error, I think I'll fix both issues at
once by just doing (256 - ceil) % ceil.
Jason