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.
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.
Created attachment 280799 [details] test_div64.c Testcase version for script.
Created attachment 280801 [details] test_script.sh Test script for testing.
For me verification on random numbers seems to work. Could you verify the change on your 32 bit platform ?
(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.
Created attachment 280805 [details] improved testcase from hackersdelight There are my testcase
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
Link to another thread, where i post this bug earlier, may contain useful info. https://bugzilla.redhat.com/show_bug.cgi?id=1668164
I'll to post the fix upstream. I think we also need to fix div64_u64 .
Patch was posted. https://lkml.org/lkml/2019/1/28/493