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(-)
diff --git a/lib/div64.c b/lib/div64.c
index 779d7521f69f..14d402ce4c7e 100644
--- a/lib/div64.c
+++ b/lib/div64.c
@@ -109,7 +109,7 @@ u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)
quot = div_u64_rem(dividend, divisor, &rem32);
*remainder = rem32;
} else {
- int n = 1 + fls(high);
+ int n = fls(high);
quot = div_u64(dividend >> n, divisor >> n);
if (quot != 0)
@@ -147,7 +147,7 @@ u64 div64_u64(u64 dividend, u64 divisor)
if (high == 0) {
quot = div_u64(dividend, divisor);
} else {
- int n = 1 + fls(high);
+ int n = fls(high);
quot = div_u64(dividend >> n, divisor >> n);
if (quot != 0)
--
2.54.0
