Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Message-ID: <0dc78ec5-e934-fcb4-5153-1e8d3840f473@rasmusvillemoes.dk>
Date:   Tue, 11 Oct 2022 15:21:44 +0200
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101
 Thunderbird/91.11.0
Subject: Re: [crng-random:jd/get_random_u32_below 24/26]
 include/linux/random.h:64:77: sparse: sparse: cast truncates bits from
 constant value (e24d4d50 becomes 50)
Content-Language: en-US
To:     kernel test robot <lkp@intel.com>,
        "Jason A. Donenfeld" <zx2c4@kernel.org>
Cc:     kbuild-all@lists.01.org, linux-kernel@vger.kernel.org
References: <202210111756.pMpxXUwp-lkp@intel.com>
From:   Rasmus Villemoes <linux@rasmusvillemoes.dk>
In-Reply-To: <202210111756.pMpxXUwp-lkp@intel.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Precedence: bulk

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