Bug 202391

Summary: 32-bit kernel implementation of div64_u64_rem contains error
Product: Other Reporter: Siarhei Volkau (lis8215)
Component: OtherAssignee: other_other
Status: CLOSED PATCH_ALREADY_AVAILABLE    
Severity: high CC: jwrdegoede, lis8215, stf_xl
Priority: P1    
Hardware: Other   
OS: Linux   
Kernel Version: 3.12.x and above Subsystem:
Regression: Yes Bisected commit-id:
Attachments: Sample driver code to showcase the bug
test_div64.c
test_div64.c
test_script.sh
improved testcase from hackersdelight

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
http://www.hackersdelight.org/hdcodetxt/divDouble.c.txt
works as expected on provided numbers.

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

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);

to

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]
test_div64.c

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

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.

https://bugzilla.redhat.com/show_bug.cgi?id=1668164
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.
https://lkml.org/lkml/2019/1/28/493