Messages in this thread Patch in this message | | | From | Daniel Latypov <> | Date | Mon, 24 May 2021 09:55:01 -0700 | Subject | Re: [PATCH] lib/math/rational.c: Fix divide by zero |
| |
On Mon, May 24, 2021 at 3:51 AM Andy Shevchenko <andriy.shevchenko@intel.com> wrote: > > On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote: > > Thanks for the fix! My comments below. > > > If the input is out of the range of the allowed values, either larger > > than the largest value or closer to zero than the smallest non-zero > > allowed value, then a division by zero would occur. > > > > In the case of input too large, the division by zero will occur on the > > first iteration. The best result (largest allowed value) will be found > > by always choosing the semi-convergent and excluding the denominator > > based limit when finding it. > > > > In the case of the input too small, the division by zero will occur on > > the second iteration. The numerator based semi-convergent should not be > > calculated to avoid the division by zero. But the semi-convergent vs > > previous convergent test is still needed, which effectively chooses > > between 0 (the previous convergent) vs the smallest allowed fraction > > (best semi-convergent) as the result. > > This misses the test cases (*). Please, develop them with Daniel.
FYI, I was leaning towards not having this in the proposed math_kunit.c, since this code is gated behind CONFIG_RATIONAL=y, while the others are not. I.e. I think we want to add a new rational_kunit.c to contain this test case.
I can help write it up if wanted, but I'll give some pointers on how to do so below.
Trent, https://www.kernel.org/doc/html/latest/dev-tools/kunit/start.html would be the entry point for KUnit documentation. After you feel comfortable with the following, I'd recommend https://www.kernel.org/doc/html/latest/dev-tools/kunit/usage.html#testing-against-multiple-inputs
You can run the tests added via something like this
$ ./tools/testing/kunit/kunit.py run --kunitconfig /dev/stdin <<EOF CONFIG_KUNIT=y CONFIG_RATIONAL=y CONFIG_RATIONAL_KUNIT_TEST=y EOF
(feel free to put the heredoc into a file, just using it for a copy-paste friendly one-liner)
given a starting change like this (which I can see crash w/o the fix, and pass w/ it).
diff --git a/lib/math/Kconfig b/lib/math/Kconfig index f19bc9734fa7..20460b567493 100644 --- a/lib/math/Kconfig +++ b/lib/math/Kconfig @@ -15,3 +15,14 @@ config PRIME_NUMBERS
config RATIONAL bool + +config RATIONAL_KUNIT_TEST + tristate "KUnit test for rational number support" if !KUNIT_ALL_TESTS + # depends on KUNIT && RATIONAL # this is how it should work, but + depends on KUNIT + select RATIONAL # I don't grok kconfig enough to know why this is necessary + default KUNIT_ALL_TESTS + help + This builds unit tests for the rational number support. + + If unsure, say N. diff --git a/lib/math/Makefile b/lib/math/Makefile index 7456edb864fc..a11ffdb953ef 100644 --- a/lib/math/Makefile +++ b/lib/math/Makefile @@ -6,3 +6,4 @@ obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o obj-$(CONFIG_RATIONAL) += rational.o
obj-$(CONFIG_TEST_DIV64) += test_div64.o +obj-$(CONFIG_RATIONAL_KUNIT_TEST) += rational_kunit.o diff --git a/lib/math/rational_kunit.c b/lib/math/rational_kunit.c new file mode 100644 index 000000000000..88ad0e2baece --- /dev/null +++ b/lib/math/rational_kunit.c @@ -0,0 +1,28 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include <kunit/test.h> + +#include <linux/rational.h> + +static void rational_bug_test(struct kunit *test) +{ + unsigned long n = 0, d = 0; + + rational_best_approximation(31415, 100, (1 << 8) - 1, (1 << 5) - 1, &n, &d); + KUNIT_EXPECT_EQ(test, n, 255); + KUNIT_EXPECT_EQ(test, d, 1); +} + +static struct kunit_case rational_test_cases[] = { + KUNIT_CASE(rational_bug_test), + {} +}; + +static struct kunit_suite rational_test_suite = { + .name = "rational", + .test_cases = rational_test_cases, +}; + +kunit_test_suites(&rational_test_suite); + +MODULE_LICENSE("GPL v2");
> > *) We usually don't accept changes in the generic libraries without test cases. > > Fixes tag? > > > Reported-by: Yiyuan Guo <yguoaz@gmail.com> > > Signed-off-by: Trent Piepho <tpiepho@gmail.com> > > ... > > > + /* This tests if the semi-convergent is closer than the previous > > + * convergent. If d1 is zero there is no previous convergent as this > > + * is the 1st iteration, so always choose the semi-convergent. > > */ > > - if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) { > > + if (!d1 || 2u * t > a || (2u * t == a && d0 * dp > d1 * d)) { > > n1 = n0 + t * n1; > > d1 = d0 + t * d1; > > } > > I think that refactoring may lead us to check first iteration before even going > into the loop. But it's another story and we may do it later (the algo uses > heavy division anyway, so couple of additional branches probably won't affect > performance too much). > > -- > With Best Regards, > Andy Shevchenko > >
| |