|Summary:||32-bit kernel implementation of div64_u64_rem contains error|
|Product:||Other||Reporter:||Siarhei Volkau (lis8215)|
|Severity:||high||CC:||jwrdegoede, lis8215, stf_xl|
|Kernel Version:||3.12.x and above||Tree:||Mainline|
Sample driver code to showcase the bug
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 7 Siarhei Volkau 2019-01-27 06:03:30 UTC
Assume its a regression, see this commit: https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/commit/lib/div64.c?id=658716d19f8f155c67d4677ba68034b8e492dfbe
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 .