Re: [PATCH 1/5] lib: div64: fix off-by-one shift in div64_u64() and div64_u64_rem()

On 2026-07-30T18:40:37, Alexey Charkov <[email protected]> wrote:
> lib: div64: fix off-by-one shift in div64_u64() and div64_u64_rem()
>
> fls() counts bits starting from 1, so shifting the operands right by
> 1 + fls(high) discards one more bit of the divisor than intended. Both
> functions estimate the quotient from the shifted operands and then fix
> it up with a single decrement/increment, so an estimate that is off by
> more than one cannot be repaired and the result comes out wrong.
>
> This only affects BITS_PER_LONG == 32, where these are the out-of-line
> implementations; on 64-bit the header provides plain C division.
>
> The error is only reachable when the quotient is large, which needs a
> divisor just above 2^32. For example:
>
>   dividend = 15559272575191414037
>   divisor  = 4333540799
>   expected = 3590429465
>   actual   = 3590429468            (off by 3)
>
> A sweep over 6.4M random operand pairs, stratified by the width of the
> divisor's high word, mismatches a __int128 reference 8260 times before
> this change and never after it. All failures have a divisor with one or
> two significant bits above bit 32; uniformly random 64-bit divisors are
> closer to 2^63 and yield quotients of ~1, which hides the problem.
>
> Port of Linux commit cdc94a374931 ("lib/div64.c: off by one in shift"),
> which fixed the same code and cites [1].
>
> In-tree users of div64_u64() that are built for 32-bit targets include
> the Aspeed, Meson and Cadence TTC PWM drivers, the Versaclock and
> wrpll-cln28hpc clock drivers, and the DWC3 USB core.
>
> Link: https://bugzilla.kernel.org/show_bug.cgi?id=202391 [1]
> Fixes: 0342e335ba88 ("lib: div64: sync with Linux")
> Signed-off-by: Alexey Charkov <[email protected]>
>
> lib/div64.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)

Reviewed-by: Simon Glass <[email protected]>