Skip to contentSkip to conversation

lib/math/rational.c: Fix divide by zero

PATCH Applied Trent Piepho 5 participants 10 messages May 25, 2021 – May 26, 2021 Library code

v2 of 3 Applied 2/2 Latest is v3 →

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/2 lib/math/rational.c: Fix divide by zero

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")
---
 lib/math/rational.c | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)
lib/math/rational.c +11 -5
index 9781d521963d..c0ab51d8fbb9 100644
@@ -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;
 			}
Signature · 1 line
2.26.2
#1 lore raw

PATCH v2 2/2 lib/math/rational: Add Kunit test cases

Adds a number of test cases that cover a range of possible code paths.

---
 lib/Kconfig.debug        | 12 +++++++++
 lib/math/Makefile        |  1 +
 lib/math/rational-test.c | 56 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 69 insertions(+)
 create mode 100644 lib/math/rational-test.c
lib/Kconfig.debug +12 -0
index 678c13967580..6c0e66a7d416 100644
@@ -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
lib/math/Makefile +1 -0
index 7456edb864fc..bfac26ddfc22 100644
@@ -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-test.o
lib/math/rational-test.c new file +56 -0

56 lines not on this page · raw message

Signature · 1 line
2.26.2
Reviewed-by on v2 2/2
#2 lore raw

Re: [PATCH v2 2/2] lib/math/rational: Add Kunit test cases

Quoted 1 line · Trent Piepho

Adds a number of test cases that cover a range of possible code paths.

Good for the starter!

Quoted 105 lines
---
 lib/Kconfig.debug        | 12 +++++++++
 lib/math/Makefile        |  1 +
 lib/math/rational-test.c | 56 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 69 insertions(+)
 create mode 100644 lib/math/rational-test.c
lib/Kconfig.debug +12 -0
index 678c13967580..6c0e66a7d416 100644
@@ -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
lib/math/Makefile +1 -0
index 7456edb864fc..bfac26ddfc22 100644
@@ -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-test.o
lib/math/rational-test.c new file +56 -0
new file mode 100644
index 000000000000..f64166dbe9ea
@@ -0,0 +1,56 @@
+// 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 > ½ last term" },
+	{ 34567,100, 	120, 20,	120, 1,    "Exceeds bounds, semi-convergent term < ½ last term" },
+	{ 1, 30,	100, 10,	0, 1,	   "Closest to zero" },
+	{ 1, 19,	100, 10,	1, 10,     "Closest to smallest non-zero" },
+	{ 27,32,	16, 16,		11, 13,    "Use convergent" },
+	{ 1155, 7735,	255, 255,	33, 221,   "Exact answer" },
+	{ 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");
Signature · 1 line
2.26.2
Signature · 2 lines
With Best Regards,
Andy Shevchenko
Reviewed-by on v2 2/2
#3 lore raw

Re: [PATCH v2 2/2] lib/math/rational: Add Kunit test cases

In reply to Trent Piepho
Quoted 4 lines · Trent Piepho

Adds a number of test cases that cover a range of possible code paths.

Looks really good to me, just two nits.

Tangent:
I didn't check to see that this covers all the interesting cases, but it seems like it does.
If you want, you can try generating a code coverage report to double check. Instructions for doing so can be found in
https://lore.kernel.org/linux-kselftest/[email protected]/
I would have done that and included the #s in this email, but my workplace decided to subtly break my workstation in some way and I haven't gotten around to root causing...

Quoted 4 lines
---
 lib/Kconfig.debug        | 12 +++++++++
 lib/math/Makefile        |  1 +
 lib/math/rational-test.c | 56 ++++++++++++++++++++++++++++++++++++++++

Ah, sorry, I forgot to mention this in the previous email. If you look at kunit/style.rst docs, you'll see the documentation now states a preference for the name of this file to be one of {rational_test.c, rational_kunit.c}

Unfortunately, we have a number of tests throughout the tree that don't reflect this, including lib/kunit/kunit-example-test.c :(

Quoted 48 lines
 3 files changed, 69 insertions(+)
 create mode 100644 lib/math/rational-test.c
lib/Kconfig.debug +12 -0
index 678c13967580..6c0e66a7d416 100644
@@ -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
lib/math/Makefile +1 -0
index 7456edb864fc..bfac26ddfc22 100644
@@ -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-test.o
lib/math/rational-test.c new file +7 -0
new file mode 100644
index 000000000000..f64166dbe9ea
@@ -0,0 +1,56 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <kunit/test.h>
+
+#include <linux/rational.h>
+
+struct rational_test_param {

lib/math/rational-test.c line 17

Quoted 10 lines
lib/math/rational-test.c new file +10 -0
+       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 > ½ last term" },
+       { 34567,100,    120, 20,        120, 1,    "Exceeds bounds, semi-convergent term < ½ last term" },

very minor nit: there's an extraneous space character after the "100,"

Quoted 42 lines
lib/math/rational-test.c new file +39 -1
+       { 1, 30,        100, 10,        0, 1,      "Closest to zero" },
+       { 1, 19,        100, 10,        1, 10,     "Closest to smallest non-zero" },
+       { 27,32,        16, 16,         11, 13,    "Use convergent" },
+       { 1155, 7735,   255, 255,       33, 221,   "Exact answer" },
+       { 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

#4 lore raw

Re: [PATCH v2 2/2] lib/math/rational: Add Kunit test cases

Quoted 9 lines · Daniel Latypov
Quoted 3 lines · Trent Piepho

Adds a number of test cases that cover a range of possible code paths.

Looks really good to me, just two nits.

Quoted 9 lines

Tangent:
I didn't check to see that this covers all the interesting cases, but it seems like it does.
If you want, you can try generating a code coverage report to double check. Instructions for doing so can be found in
https://lore.kernel.org/linux-kselftest/[email protected]/
I would have done that and included the #s in this email, but my workplace decided to subtly break my workstation in some way and I haven't gotten around to root causing...

I installed a gcc 6.4 toolchain and changed the uml_abort() call to exit(), coverage was generated, but still truncated and incorrectly near 0%. So what I did was crash after running all the test cases I cared about by dividing by zero and then coverage data was produced correctly. It's 100% by lines. But I think both possibilities when the largest semiconvergent is exactly half the previous convergent aren't tested.

Quoted 6 lines
Quoted 1 line
 lib/math/rational-test.c | 56 ++++++++++++++++++++++++++++++++++++++++

Ah, sorry, I forgot to mention this in the previous email. If you look at kunit/style.rst docs, you'll see the documentation now states a preference for the name of this file to be one of {rational_test.c, rational_kunit.c}

Before I chose a name, I checked every file with kunit tests cases, and *-test was the most common naming pattern, including the sample case. I would be nice if changing the docs to say something is a standard also updated the code to make that reality.

#5 lore raw

Re: [PATCH v2 2/2] lib/math/rational: Add Kunit test cases

Quoted 21 lines · Trent Piepho
Quoted 9 lines · Daniel Latypov
Quoted 3 lines · Trent Piepho

Adds a number of test cases that cover a range of possible code paths.

Looks really good to me, just two nits.

Quoted 9 lines

Tangent:
I didn't check to see that this covers all the interesting cases, but it seems like it does.
If you want, you can try generating a code coverage report to double check. Instructions for doing so can be found in
https://lore.kernel.org/linux-kselftest/[email protected]/
I would have done that and included the #s in this email, but my workplace decided to subtly break my workstation in some way and I haven't gotten around to root causing...

Quoted 7 lines

I installed a gcc 6.4 toolchain and changed the uml_abort() call to exit(), coverage was generated, but still truncated and incorrectly near 0%. So what I did was crash after running all the test cases I cared about by dividing by zero and then coverage data was produced correctly. It's 100% by lines. But I think both possibilities when the largest semiconvergent is exactly half the previous convergent aren't tested.

Yeah, it's finicky.
Hopefully Brendan's change to cleanly shutdown the kernel at the end of the tests might make it a bit more robust (still probably requires gcc-6).

Thanks for running it!
It's nice to know we have 100% (line) coverage.

Quoted 8 lines
Quoted 7 lines
Quoted 2 lines
 lib/math/rational-test.c | 56 ++++++++++++++++++++++++++++++++++++++++

Ah, sorry, I forgot to mention this in the previous email. If you look at kunit/style.rst docs, you'll see the documentation now states a preference for the name of this file to be one of {rational_test.c, rational_kunit.c}

Quoted 4 lines

Before I chose a name, I checked every file with kunit tests cases, and *-test was the most common naming pattern, including the sample case. I would be nice if changing the docs to say something is a standard also updated the code to make that reality.

Yeah, it's frustrating...
Andy sent out some changes renaming a lot of the files, but we've not managed to get everything up to date.

maintainer
#6 lore raw

Re: [PATCH v2 2/2] lib/math/rational: Add Kunit test cases

In reply to Trent Piepho
Quoted 12 lines · On Tue, 25 May 2021 07:42:50 -0700 Trent Piepho <[email protected]> wrote:

Adds a number of test cases that cover a range of possible code paths.

lib/math/rational-test.c new file +7 -0
@@ -0,0 +1,56 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <kunit/test.h>
+
+#include <linux/rational.h>
+
+struct rational_test_param {

lib/math/rational-test.c line 17

Quoted 10 lines
lib/math/rational-test.c new file +10 -0
+	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 > ½ last term" },
+	{ 34567,100, 	120, 20,	120, 1,    "Exceeds bounds, semi-convergent term < ½ last term" },

It seems to be asking for trouble to use these characters in kernel output - heaven knows what sort of weird output devices people are using. So I think I'll switch to "1/2", OK?

Quoted 7 lines
lib/math/rational-test.c new file +7 -0
+	{ 1, 30,	100, 10,	0, 1,	   "Closest to zero" },
+	{ 1, 19,	100, 10,	1, 10,     "Closest to smallest non-zero" },
+	{ 27,32,	16, 16,		11, 13,    "Use convergent" },
+	{ 1155, 7735,	255, 255,	33, 221,   "Exact answer" },
+	{ 87, 32,	70, 32,		68, 25,    "Semiconvergent, numerator limit" },
+	{ 14533, 4626,	15000, 2400,	7433, 2366, "Semiconvergent, demominator limit" },
+};

lib/math/rational-test.c line 52

Quoted 10 lines
lib/math/rational-test.c new file +9 -0
...
+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,
+};

And let's use tabs to indent here. checkpatch detects this.

Reviewed-by on v2 1/2
#7 lore raw
In reply to Trent Piepho
Quoted 9 lines · Trent Piepho

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.

Quoted 6 lines

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.

LGTM, thanks!

Quoted 46 lines
Fixes 323dd2c3ed0 ("lib/math/rational.c: fix possible incorrect result from rational fractions helper")
---
 lib/math/rational.c | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)
lib/math/rational.c +11 -5
index 9781d521963d..c0ab51d8fbb9 100644
@@ -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;
 			}
Signature · 1 line
2.26.2
Signature · 2 lines
With Best Regards,
Andy Shevchenko
maintainer
#8 lore raw
In reply to Trent Piepho
Quoted 9 lines · On Tue, 25 May 2021 07:42:49 -0700 Trent Piepho <[email protected]> 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.

Quoted 6 lines

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.

Is there any known userspace workload which can trigger this?

IOW, should it be backported into -stable and fast-tracked into 5.13 or will a 5.14 merge suffice?

#9 lore raw
Quoted 11 lines · Andrew Morton
Quoted 9 lines · On Tue, 25 May 2021 07:42:49 -0700 Trent Piepho <[email protected]> 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.

Quoted 8 lines
Quoted 6 lines

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.

Is there any known userspace workload which can trigger this?

Doubtfully.

What I can imagine (which also can be impossible) is to try on some UART drivers that use this algorithm to ask crazy baud rates (much higher than the clock). Sounds like a theoretical possibility is present, but practically no one except bad hackers would do that (requires a special code to be written in user space to select BOTHER with an arbitrary input in termios).

Quoted 2 lines

IOW, should it be backported into -stable and fast-tracked into 5.13 or will a 5.14 merge suffice?

Signature · 2 lines
With Best Regards,
Andy Shevchenko