Bug 202391 - 32-bit kernel implementation of div64_u64_rem contains error
Summary: 32-bit kernel implementation of div64_u64_rem contains error
Alias: None
Product: Other
Classification: Unclassified
Component: Other (show other bugs)
Hardware: Other Linux
: P1 high
Assignee: other_other
Depends on:
Reported: 2019-01-23 07:21 UTC by Siarhei Volkau
Modified: 2019-01-28 16:23 UTC (History)
3 users (show)

See Also:
Kernel Version: 3.12.x and above
Tree: Mainline
Regression: Yes

Sample driver code to showcase the bug (1.27 KB, application/gzip)
2019-01-23 07:21 UTC, Siarhei Volkau
test_div64.c (2.74 KB, text/plain)
2019-01-26 16:00 UTC, Stanislaw Gruszka
test_div64.c (2.86 KB, text/plain)
2019-01-26 17:15 UTC, Stanislaw Gruszka
test_script.sh (755 bytes, text/plain)
2019-01-26 17:16 UTC, Stanislaw Gruszka
improved testcase from hackersdelight (3.91 KB, text/plain)
2019-01-27 05:55 UTC, Siarhei Volkau

Description Siarhei Volkau 2019-01-23 07:21:52 UTC
Created attachment 280687 [details]
Sample driver code to showcase the bug

Far time ago in the linux kernel was introduced helper
function named div64_u64_rem. Today i found that this
function gets wrong result for some input.

Example: try to divide 0x8000000000000000ULL by 4299651251ULL via this helper function.
I attach sample driver code to showcase this bug (see attachment).

There's an output of driver:
[  420.526425] div64_bug: loading out-of-tree module taints kernel.
[  420.526462] div64_bug: module verification failed: signature and/or required key missing - tainting kernel
[  420.528173] div64_u64_rem_bug showtime:
[  420.528178] div64_u64_rem_bug calculates 9223372036854775808 / 4299651251 via div64_u64_rem() helper
[  420.528180] div64_u64_rem_bug expect receive:
[  420.528182] quotient: 2145144221 and remainder: 3456705337
[  420.528184] but got
[  420.528185] quotient: 2145144223 and remainder: 18446744068566954451
[  420.528187] div64_u64_rem_bug ends.

Don't ask me how to fix this - i have no idea.
But reference implementation of this function
works as expected on provided numbers.

Comment 1 Stanislaw Gruszka 2019-01-26 16:00:25 UTC
Created attachment 280795 [details]

I copied your module to user space program for easier testing and playing with the code. Issue is reproducible even on 64 bit platform and looks like changing

int n = 1 +  fls(high);


int n = fls(high);

make the results correct. But this change require verification on other numbers.
Comment 2 Stanislaw Gruszka 2019-01-26 17:15:18 UTC
Created attachment 280799 [details]

Testcase version for script.
Comment 3 Stanislaw Gruszka 2019-01-26 17:16:01 UTC
Created attachment 280801 [details]

Test script for testing.
Comment 4 Stanislaw Gruszka 2019-01-26 17:17:42 UTC
For me verification on random numbers seems to work. Could you verify the change on your 32 bit platform ?
Comment 5 Siarhei Volkau 2019-01-27 05:52:58 UTC
(In reply to Stanislaw Gruszka from comment #4)

I not perform random test you mention, but
i perform tests presented in the reference implementation:
Buggy div64_u64_rem pass all of them :)
Then i add 0x100000003 to testcases and now it fail 11 tests.

Your fixed version pass all tests.

> For me verification on random numbers seems to work. Could you verify the
> change on your 32 bit platform ?

It works, thank you.
Assume, bug will be fixed soon in upstream.
Comment 6 Siarhei Volkau 2019-01-27 05:55:42 UTC
Created attachment 280805 [details]
improved testcase from hackersdelight

There are my testcase
Comment 8 Siarhei Volkau 2019-01-27 06:05:45 UTC
Link to another thread, where i post this bug earlier, may contain useful info.

Comment 9 Stanislaw Gruszka 2019-01-28 06:42:49 UTC
I'll to post the fix upstream. I think we also need to fix div64_u64 .
Comment 10 Stanislaw Gruszka 2019-01-28 16:23:07 UTC
Patch was posted.

Note You need to log in before you can comment on or make changes to this bug.