* [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero @ 2021-05-25 23:35 Trent Piepho 2021-05-25 23:35 ` [PATCH v3 2/2] lib/math/rational: Add Kunit test cases Trent Piepho 2021-05-26 8:04 ` [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero Andy Shevchenko 0 siblings, 2 replies; 6+ messages in thread From: Trent Piepho @ 2021-05-25 23:35 UTC (permalink / raw) To: linux-kernel; +Cc: andy, akpm, oskar, Daniel Latypov, Trent Piepho, Yiyuan Guo 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. Fixes: 323dd2c3ed0 ("lib/math/rational.c: fix possible incorrect result from rational fractions helper") Reported-by: Yiyuan Guo <yguoaz@gmail.com> Signed-off-by: Trent Piepho <tpiepho@gmail.com> --- lib/math/rational.c | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) diff --git a/lib/math/rational.c b/lib/math/rational.c index 9781d521963d..c0ab51d8fbb9 100644 --- a/lib/math/rational.c +++ b/lib/math/rational.c @@ -12,6 +12,7 @@ #include <linux/compiler.h> #include <linux/export.h> #include <linux/minmax.h> +#include <linux/limits.h> /* * calculate best rational approximation for a given fraction @@ -78,13 +79,18 @@ void rational_best_approximation( * found below as 't'. */ if ((n2 > max_numerator) || (d2 > max_denominator)) { - unsigned long t = min((max_numerator - n0) / n1, - (max_denominator - d0) / d1); + unsigned long t = ULONG_MAX; - /* This tests if the semi-convergent is closer - * than the previous convergent. + if (d1) + t = (max_denominator - d0) / d1; + if (n1) + t = min(t, (max_numerator - n0) / n1); + + /* 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; } -- 2.26.2 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH v3 2/2] lib/math/rational: Add Kunit test cases 2021-05-25 23:35 [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero Trent Piepho @ 2021-05-25 23:35 ` Trent Piepho 2021-05-25 23:53 ` Daniel Latypov 2021-05-26 8:04 ` [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero Andy Shevchenko 1 sibling, 1 reply; 6+ messages in thread From: Trent Piepho @ 2021-05-25 23:35 UTC (permalink / raw) To: linux-kernel; +Cc: andy, akpm, oskar, Daniel Latypov, Trent Piepho Adds a number of test cases that cover a range of possible code paths. Signed-off-by: Trent Piepho <tpiepho@gmail.com> --- Changes from v2: Rename file to follow new kunit naming convention Fix whitespace issues Remove unicode characters Add more testcases lib/Kconfig.debug | 12 ++++++++ lib/math/Makefile | 1 + lib/math/rational_kunit.c | 60 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 73 insertions(+) create mode 100644 lib/math/rational_kunit.c diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 678c13967580..6c0e66a7d416 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2429,6 +2429,18 @@ config BITS_TEST If unsure, say N. +config RATIONAL_KUNIT_TEST + tristate "KUnit test for rational.c" if !KUNIT_ALL_TESTS + depends on KUNIT + select RATIONAL + default KUNIT_ALL_TESTS + help + This builds the rational math unit test. + For more information on KUnit and unit tests in general please refer + to the KUnit documentation in Documentation/dev-tools/kunit/. + + If unsure, say N. + config TEST_UDELAY tristate "udelay test driver" help diff --git a/lib/math/Makefile b/lib/math/Makefile index 7456edb864fc..de7d16ca3cf5 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..439b06fdfe66 --- /dev/null +++ b/lib/math/rational_kunit.c @@ -0,0 +1,60 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include <kunit/test.h> + +#include <linux/rational.h> + +struct rational_test_param { + unsigned long num, den; + unsigned long max_num, max_den; + unsigned long exp_num, exp_den; + + const char *name; +}; + +static const struct rational_test_param test_parameters[] = { + { 1230, 10, 100, 20, 100, 1, "Exceeds bounds, semi-convergent term > half last term" }, + { 34567, 100, 120, 20, 120, 1, "Exceeds bounds, semi-convergent term < half last term" }, + { 1, 30, 100, 10, 0, 1, "Closest to zero" }, + { 1, 19, 100, 10, 1, 10, "Closest to smallest non-zero" }, + { 1155, 7735, 255, 255, 33, 221, "Exact answer" }, + { 27, 32, 16, 16, 11, 13, "Convergent" }, + { 67, 54, 17, 18, 5, 4, "Convergent, semiconvergent term half convergent term" }, + { 453, 182, 60, 60, 57, 23, "Semiconvergent, semiconvergent term half convergent term" }, + { 87, 32, 70, 32, 68, 25, "Semiconvergent, numerator limit" }, + { 14533, 4626, 15000, 2400, 7433, 2366, "Semiconvergent, demominator limit" }, +}; + +static void get_desc(const struct rational_test_param *param, char *desc) +{ + strscpy(desc, param->name, KUNIT_PARAM_DESC_SIZE); +} + +/* Creates function rational_gen_params */ +KUNIT_ARRAY_PARAM(rational, test_parameters, get_desc); + +static void rational_test(struct kunit *test) +{ + const struct rational_test_param *param = + (const struct rational_test_param *)test->param_value; + unsigned long n = 0, d = 0; + + rational_best_approximation(param->num, param->den, param->max_num, param->max_den, &n, &d); + KUNIT_EXPECT_EQ(test, n, param->exp_num); + KUNIT_EXPECT_EQ(test, d, param->exp_den); +} + +static struct kunit_case rational_test_cases[] = { + KUNIT_CASE_PARAM(rational_test, rational_gen_params), + {} +}; + +static struct kunit_suite rational_test_suite = { + .name = "rational", + .test_cases = rational_test_cases, +}; + +kunit_test_suites(&rational_test_suite); + +MODULE_LICENSE("GPL v2"); -- 2.26.2 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH v3 2/2] lib/math/rational: Add Kunit test cases 2021-05-25 23:35 ` [PATCH v3 2/2] lib/math/rational: Add Kunit test cases Trent Piepho @ 2021-05-25 23:53 ` Daniel Latypov 0 siblings, 0 replies; 6+ messages in thread From: Daniel Latypov @ 2021-05-25 23:53 UTC (permalink / raw) To: Trent Piepho Cc: Linux Kernel Mailing List, andy, Andrew Morton, Oskar Schirmer On Tue, May 25, 2021 at 4:36 PM Trent Piepho <tpiepho@gmail.com> wrote: > > Adds a number of test cases that cover a range of possible code paths. > > Signed-off-by: Trent Piepho <tpiepho@gmail.com> Reviewed-by: Daniel Latypov <dlatypov@google.com> LGTM, thanks! > --- > Changes from v2: > Rename file to follow new kunit naming convention > Fix whitespace issues > Remove unicode characters > Add more testcases > > lib/Kconfig.debug | 12 ++++++++ > lib/math/Makefile | 1 + > lib/math/rational_kunit.c | 60 +++++++++++++++++++++++++++++++++++++++ > 3 files changed, 73 insertions(+) > create mode 100644 lib/math/rational_kunit.c > > diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug > index 678c13967580..6c0e66a7d416 100644 > --- a/lib/Kconfig.debug > +++ b/lib/Kconfig.debug > @@ -2429,6 +2429,18 @@ config BITS_TEST > > If unsure, say N. > > +config RATIONAL_KUNIT_TEST > + tristate "KUnit test for rational.c" if !KUNIT_ALL_TESTS > + depends on KUNIT > + select RATIONAL > + default KUNIT_ALL_TESTS > + help > + This builds the rational math unit test. > + For more information on KUnit and unit tests in general please refer > + to the KUnit documentation in Documentation/dev-tools/kunit/. > + > + If unsure, say N. > + > config TEST_UDELAY > tristate "udelay test driver" > help > diff --git a/lib/math/Makefile b/lib/math/Makefile > index 7456edb864fc..de7d16ca3cf5 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..439b06fdfe66 > --- /dev/null > +++ b/lib/math/rational_kunit.c > @@ -0,0 +1,60 @@ > +// SPDX-License-Identifier: GPL-2.0 > + > +#include <kunit/test.h> > + > +#include <linux/rational.h> > + > +struct rational_test_param { > + unsigned long num, den; > + unsigned long max_num, max_den; > + unsigned long exp_num, exp_den; > + > + const char *name; > +}; > + > +static const struct rational_test_param test_parameters[] = { > + { 1230, 10, 100, 20, 100, 1, "Exceeds bounds, semi-convergent term > half last term" }, > + { 34567, 100, 120, 20, 120, 1, "Exceeds bounds, semi-convergent term < half last term" }, > + { 1, 30, 100, 10, 0, 1, "Closest to zero" }, > + { 1, 19, 100, 10, 1, 10, "Closest to smallest non-zero" }, > + { 1155, 7735, 255, 255, 33, 221, "Exact answer" }, > + { 27, 32, 16, 16, 11, 13, "Convergent" }, > + { 67, 54, 17, 18, 5, 4, "Convergent, semiconvergent term half convergent term" }, > + { 453, 182, 60, 60, 57, 23, "Semiconvergent, semiconvergent term half convergent term" }, > + { 87, 32, 70, 32, 68, 25, "Semiconvergent, numerator limit" }, > + { 14533, 4626, 15000, 2400, 7433, 2366, "Semiconvergent, demominator limit" }, > +}; > + > +static void get_desc(const struct rational_test_param *param, char *desc) > +{ > + strscpy(desc, param->name, KUNIT_PARAM_DESC_SIZE); > +} > + > +/* Creates function rational_gen_params */ > +KUNIT_ARRAY_PARAM(rational, test_parameters, get_desc); > + > +static void rational_test(struct kunit *test) > +{ > + const struct rational_test_param *param = > + (const struct rational_test_param *)test->param_value; > + unsigned long n = 0, d = 0; > + > + rational_best_approximation(param->num, param->den, param->max_num, param->max_den, &n, &d); > + KUNIT_EXPECT_EQ(test, n, param->exp_num); > + KUNIT_EXPECT_EQ(test, d, param->exp_den); > +} > + > +static struct kunit_case rational_test_cases[] = { > + KUNIT_CASE_PARAM(rational_test, rational_gen_params), > + {} > +}; > + > +static struct kunit_suite rational_test_suite = { > + .name = "rational", > + .test_cases = rational_test_cases, > +}; > + > +kunit_test_suites(&rational_test_suite); > + > +MODULE_LICENSE("GPL v2"); > -- > 2.26.2 > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero 2021-05-25 23:35 [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero Trent Piepho 2021-05-25 23:35 ` [PATCH v3 2/2] lib/math/rational: Add Kunit test cases Trent Piepho @ 2021-05-26 8:04 ` Andy Shevchenko 2021-05-26 8:06 ` Andy Shevchenko 2021-05-26 19:09 ` Trent Piepho 1 sibling, 2 replies; 6+ messages in thread From: Andy Shevchenko @ 2021-05-26 8:04 UTC (permalink / raw) To: Trent Piepho; +Cc: linux-kernel, andy, akpm, oskar, Daniel Latypov, Yiyuan Guo On Tue, May 25, 2021 at 04:35:18PM -0700, Trent Piepho wrote: > 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. What has been changed that you haven't applied my Rb tag? -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero 2021-05-26 8:04 ` [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero Andy Shevchenko @ 2021-05-26 8:06 ` Andy Shevchenko 2021-05-26 19:09 ` Trent Piepho 1 sibling, 0 replies; 6+ messages in thread From: Andy Shevchenko @ 2021-05-26 8:06 UTC (permalink / raw) To: Trent Piepho; +Cc: linux-kernel, andy, akpm, oskar, Daniel Latypov, Yiyuan Guo On Wed, May 26, 2021 at 11:04:30AM +0300, Andy Shevchenko wrote: > On Tue, May 25, 2021 at 04:35:18PM -0700, Trent Piepho wrote: > > 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. > > What has been changed that you haven't applied my Rb tag? Note, the `b4` tool can easily collect them for you from previous thread. -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero 2021-05-26 8:04 ` [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero Andy Shevchenko 2021-05-26 8:06 ` Andy Shevchenko @ 2021-05-26 19:09 ` Trent Piepho 1 sibling, 0 replies; 6+ messages in thread From: Trent Piepho @ 2021-05-26 19:09 UTC (permalink / raw) To: Andy Shevchenko Cc: Linux Kernel Mailing List, andy, Andrew Morton, Oskar Schirmer, Daniel Latypov, Yiyuan Guo On Wed, May 26, 2021 at 1:04 AM Andy Shevchenko <andriy.shevchenko@intel.com> wrote: > > What has been changed that you haven't applied my Rb tag? I think I thought that was for patch 2, which changed (slightly). Patch 1 is unchanged and should have collected Rb. ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2021-05-26 19:09 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2021-05-25 23:35 [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero Trent Piepho 2021-05-25 23:35 ` [PATCH v3 2/2] lib/math/rational: Add Kunit test cases Trent Piepho 2021-05-25 23:53 ` Daniel Latypov 2021-05-26 8:04 ` [PATCH v3 1/2] lib/math/rational.c: Fix divide by zero Andy Shevchenko 2021-05-26 8:06 ` Andy Shevchenko 2021-05-26 19:09 ` Trent Piepho
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.