[PATCH] lib/div64: off by one in shift

[PATCH] lib/div64: off by one in shift

[Stanislaw Gruszka]

fls counts bits starting from 1 to 32 (returns 0 for zero argument).
If we add 1 we shift right one bit more and loose precision from
divisor, what cause function incorect results with some numbers.

Corrected code was tested in user-space, see bugzilla:
https://bugzilla.kernel.org/show_bug.cgi?id=202391

Fixes: 658716d19f8f ("div64_u64(): improve precision on 32bit platforms")
Reported-and-tested-by: Siarhei Volkau <lis8215@gmail.com>
Signed-off-by: Stanislaw Gruszka <sgruszka@redhat.com>
---
 lib/div64.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/div64.c b/lib/div64.c
index 01c8602bb6ff..ee146bb4c558 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)
-- 
1.9.3

Re: [PATCH] lib/div64: off by one in shift

[Oleg Nesterov]

On 01/28, Stanislaw Gruszka wrote:
>
> fls counts bits starting from 1 to 32 (returns 0 for zero argument).
> If we add 1 we shift right one bit more and loose precision

I forgot everything about this code, but I think this patch must be correct,

	divisor >> n;

should have MSB == 1 or we loose the precision... Heh, I managed to find the
initial version of this code, see

	https://lore.kernel.org/lkml/20101014121159.GA407@redhat.com/

and note that it uses __fls(), not fls()! I didn't notice the final version
replaced __fls() with fls() which is __fls() + 1 if arg != 0.

Acked-by: Oleg Nesterov <oleg@redhat.com>

Re: [PATCH] lib/div64: off by one in shift

[Andrew Morton]

On Mon, 28 Jan 2019 15:49:04 +0100 Stanislaw Gruszka <sgruszka@redhat.com> wrote:

> fls counts bits starting from 1 to 32 (returns 0 for zero argument).
> If we add 1 we shift right one bit more and loose precision from
> divisor, what cause function incorect results with some numbers.
> 
> Corrected code was tested in user-space, see bugzilla:
> https://bugzilla.kernel.org/show_bug.cgi?id=202391

What are the usersoace-visible runtime effects of this change?

Thanks.

Re: [PATCH] lib/div64: off by one in shift

[Stanislaw Gruszka]

On Mon, Jan 28, 2019 at 09:45:03AM -0800, Andrew Morton wrote:
> On Mon, 28 Jan 2019 15:49:04 +0100 Stanislaw Gruszka <sgruszka@redhat.com> wrote:
> 
> > fls counts bits starting from 1 to 32 (returns 0 for zero argument).
> > If we add 1 we shift right one bit more and loose precision from
> > divisor, what cause function incorect results with some numbers.
> > 
> > Corrected code was tested in user-space, see bugzilla:
> > https://bugzilla.kernel.org/show_bug.cgi?id=202391
> 
> What are the usersoace-visible runtime effects of this change?

The bug is rather theoretical and for most cases divisor is within
32 bits, so problem is not visible. Moreover the bug is only for
32-bit systems and various users of it like btrfs are unlikely
to be run on such systems. So I do not consider this as very
important fix.

Thanks
Stanislaw