Skip to contentSkip to conversation

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

PATCH Superseded Trent Piepho 6 participants 17 messages May 23, 2021 – May 25, 2021

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 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.

---
 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

On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:

Thanks for the fix! My comments below.

Quoted 9 lines

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.

This misses the test cases (*). Please, develop them with Daniel.

*) We usually don't accept changes in the generic libraries without test cases.

Fixes tag?

Quoted 2 lines

...

lib/math/rational.c void rational_best_approximation( · line 96

Quoted 9 lines
lib/math/rational.c +4 -1
+			/* 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).

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#2 lore raw
Quoted 14 lines · Andy Shevchenko

On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:

Thanks for the fix! My comments below.

Quoted 9 lines

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.

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).

lib/math/Kconfig +6 -0
index f19bc9734fa7..20460b567493 100644
@@ -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.

lib/math/Makefile +1 -0
index 7456edb864fc..a11ffdb953ef 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_kunit.o
lib/math/rational_kunit.c new file +11 -0
new file mode 100644
index 000000000000..88ad0e2baece
@@ -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");

Quoted 30 lines

*) We usually don't accept changes in the generic libraries without test cases.

Fixes tag?

Quoted 2 lines

...

Review

Quoted 9 lines
(quoted diff) +4 -1
+                     /* 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

#3 lore raw
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0 -0
index f19bc9734fa7..20460b567493 100644

lib/math/Kconfig config PRIME_NUMBERS · line 23

Quoted 9 lines
lib/math/Kconfig +6 -0
@@ -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

Only to set the symbol CONFIG_RATIONAL.
Then when 'make' descends into the lib/math/ subdir and looks at its Makefile, it will decide to build the binary rational.o.

obj-$(CONFIG_RATIONAL) += rational.o

Quoted 6 lines

is necessary

lib/math/Kconfig +5 -0
+       default KUNIT_ALL_TESTS
+       help
+               This builds unit tests for the rational number support.
+
+               If unsure, say N.
Signature · 1 line
~Randy
#4 lore raw
Quoted 21 lines · Randy Dunlap
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0 -0
index f19bc9734fa7..20460b567493 100644

lib/math/Kconfig config PRIME_NUMBERS · line 23

Quoted 9 lines
lib/math/Kconfig +6 -0
@@ -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

Only to set the symbol CONFIG_RATIONAL.
Then when 'make' descends into the lib/math/ subdir and looks at its Makefile, it will decide to build the binary rational.o.

Quoted 2 lines

obj-$(CONFIG_RATIONAL) += rational.o

Ack, I understand that much.

My confusion is why this doesn't work:

$ ./tools/testing/kunit/kunit.py run --kunitconfig /dev/stdin <<EOF
CONFIG_KUNIT=y
CONFIG_RATIONAL=y
EOF
...
ERROR:root:Provided Kconfig is not contained in validated .config.
Following fields found in kunitconfig, but not in .config:
CONFIG_RATIONAL=y

What it's complaining about is that make ARCH=um olddefconfig is leaving CONFIG_RATIONAL=y unset.

Stripping out kunit.py, it's this:

$ echo -e 'CONFIG_KUNIT=y\nCONFIG_RATIONAL=y' > .kunit/.config
$ make ARCH=um olddefconfig O=.kunit
$ grep RATIONAL .kunit/.config

I'm not versed in Kconfig enough to know why CONFIG_RATIONAL=y is getting removed.

Quoted 12 lines

lib/math/Kconfig

Quoted 7 lines

is necessary

lib/math/Kconfig +5 -0
+       default KUNIT_ALL_TESTS
+       help
+               This builds unit tests for the rational number support.
+
+               If unsure, say N.

--
~Randy

#5 lore raw
Quoted 22 lines · Daniel Latypov
Quoted 21 lines · Randy Dunlap
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0 -0
index f19bc9734fa7..20460b567493 100644

lib/math/Kconfig config PRIME_NUMBERS · line 23

Quoted 9 lines
lib/math/Kconfig +6 -0
@@ -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

Only to set the symbol CONFIG_RATIONAL.
Then when 'make' descends into the lib/math/ subdir and looks at its Makefile, it will decide to build the binary rational.o.

Quoted 4 lines
Quoted 2 lines

obj-$(CONFIG_RATIONAL) += rational.o

Ack, I understand that much.

Oh! Clearly I misunderstood the problem.

I had to look thru 60 config files before I found one where CONFIG_RATIONAL was not set.

And I'm still not sure, but I believe that it's because it has to be set by some other Kconfig entry doing a 'select' on it.

Here are the kconfigs that select it (on i386, where I found it not set):

- COMMON_CLK [=n] && !HAVE_LEGACY_CLK [=n]
- SERIAL_8250_LPSS [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_8250_MID [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_IMX [=n] && TTY [=n] && HAS_IOMEM [=y] && (ARCH_MXC || COMPILE_TEST [=y])
- VIDEO_V4L2 [=n] && MEDIA_SUPPORT [=n] && (I2C [=y] || I2C [=y]=n) && VIDEO_DEV [=n]
- SND_SOC_ROCKCHIP_PDM [=n] && SOUND [=n] && !UML && SND [=n] && SND_SOC [=n] && CLKDEV_LOOKUP [=n] && SND_SOC_ROCKCHIP [=n]
- COMMON_CLK_QCOM [=n] && COMMON_CLK [=n] && OF [=y] && (ARCH_QCOM || COMPILE_TEST [=y])

but my test config has none of those enabled, so I cannot set RATIONAL.

I guess the easiest solution is to have KUNIT or some sub-KUNIT test just select RATIONAL.

Quoted 30 lines

My confusion is why this doesn't work:

$ ./tools/testing/kunit/kunit.py run --kunitconfig /dev/stdin <<EOF
CONFIG_KUNIT=y
CONFIG_RATIONAL=y
EOF
...
ERROR:root:Provided Kconfig is not contained in validated .config.
Following fields found in kunitconfig, but not in .config:
CONFIG_RATIONAL=y

What it's complaining about is that make ARCH=um olddefconfig is leaving CONFIG_RATIONAL=y unset.

Stripping out kunit.py, it's this:

$ echo -e 'CONFIG_KUNIT=y\nCONFIG_RATIONAL=y' > .kunit/.config
$ make ARCH=um olddefconfig O=.kunit
$ grep RATIONAL .kunit/.config

I'm not versed in Kconfig enough to know why CONFIG_RATIONAL=y is getting removed.

Quoted 7 lines
Quoted 7 lines

is necessary

lib/math/Kconfig +5 -0
+       default KUNIT_ALL_TESTS
+       help
+               This builds unit tests for the rational number support.
+
+               If unsure, say N.
Signature · 1 line
~Randy
#6 lore raw
Quoted 47 lines · Randy Dunlap
Quoted 22 lines · Daniel Latypov
Quoted 21 lines · Randy Dunlap
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0 -0
index f19bc9734fa7..20460b567493 100644

lib/math/Kconfig config PRIME_NUMBERS · line 23

Quoted 9 lines
lib/math/Kconfig +6 -0
@@ -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

Only to set the symbol CONFIG_RATIONAL.
Then when 'make' descends into the lib/math/ subdir and looks at its Makefile, it will decide to build the binary rational.o.

Quoted 4 lines
Quoted 2 lines

obj-$(CONFIG_RATIONAL) += rational.o

Ack, I understand that much.

Oh! Clearly I misunderstood the problem.

I had to look thru 60 config files before I found one where CONFIG_RATIONAL was not set.

And I'm still not sure, but I believe that it's because it has to be set by some other Kconfig entry doing a 'select' on it.

Here are the kconfigs that select it (on i386, where I found it not set):

- COMMON_CLK [=n] && !HAVE_LEGACY_CLK [=n]
- SERIAL_8250_LPSS [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_8250_MID [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_IMX [=n] && TTY [=n] && HAS_IOMEM [=y] && (ARCH_MXC || COMPILE_TEST [=y])
- VIDEO_V4L2 [=n] && MEDIA_SUPPORT [=n] && (I2C [=y] || I2C [=y]=n) && VIDEO_DEV [=n]
- SND_SOC_ROCKCHIP_PDM [=n] && SOUND [=n] && !UML && SND [=n] && SND_SOC [=n] && CLKDEV_LOOKUP [=n] && SND_SOC_ROCKCHIP [=n]
- COMMON_CLK_QCOM [=n] && COMMON_CLK [=n] && OF [=y] && (ARCH_QCOM || COMPILE_TEST [=y])

Quoted 4 lines

but my test config has none of those enabled, so I cannot set RATIONAL.

I guess the easiest solution is to have KUNIT or some sub-KUNIT test just select RATIONAL.

Yeah, the easiest thing would be to keep the select RATIONAL that I showed in the example patch.

+David Gow +Brendan Higgins as they both particularly wanted to avoid having any tests select their dependencies, however.

Quoted 36 lines
Quoted 15 lines

My confusion is why this doesn't work:

$ ./tools/testing/kunit/kunit.py run --kunitconfig /dev/stdin <<EOF
CONFIG_KUNIT=y
CONFIG_RATIONAL=y
EOF
...
ERROR:root:Provided Kconfig is not contained in validated .config.
Following fields found in kunitconfig, but not in .config:
CONFIG_RATIONAL=y

What it's complaining about is that make ARCH=um olddefconfig is leaving CONFIG_RATIONAL=y unset.

Quoted 16 lines

Stripping out kunit.py, it's this:

$ echo -e 'CONFIG_KUNIT=y\nCONFIG_RATIONAL=y' > .kunit/.config
$ make ARCH=um olddefconfig O=.kunit
$ grep RATIONAL .kunit/.config

I'm not versed in Kconfig enough to know why CONFIG_RATIONAL=y is getting removed.

Quoted 7 lines
Quoted 7 lines

is necessary

lib/math/Kconfig +5 -0
+       default KUNIT_ALL_TESTS
+       help
+               This builds unit tests for the rational number support.
+
+               If unsure, say N.

--
~Randy

#7 lore raw
Quoted 51 lines · Daniel Latypov
Quoted 49 lines · Randy Dunlap
Quoted 22 lines · Daniel Latypov
Quoted 21 lines · Randy Dunlap
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0 -0
index f19bc9734fa7..20460b567493 100644

lib/math/Kconfig config PRIME_NUMBERS · line 23

Quoted 9 lines
lib/math/Kconfig +6 -0
@@ -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

Only to set the symbol CONFIG_RATIONAL.
Then when 'make' descends into the lib/math/ subdir and looks at its Makefile, it will decide to build the binary rational.o.

Quoted 4 lines
Quoted 2 lines

obj-$(CONFIG_RATIONAL) += rational.o

Ack, I understand that much.

Oh! Clearly I misunderstood the problem.

I had to look thru 60 config files before I found one where CONFIG_RATIONAL was not set.

And I'm still not sure, but I believe that it's because it has to be set by some other Kconfig entry doing a 'select' on it.

Here are the kconfigs that select it (on i386, where I found it not set):

- COMMON_CLK [=n] && !HAVE_LEGACY_CLK [=n]
- SERIAL_8250_LPSS [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_8250_MID [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_IMX [=n] && TTY [=n] && HAS_IOMEM [=y] && (ARCH_MXC || COMPILE_TEST [=y])
- VIDEO_V4L2 [=n] && MEDIA_SUPPORT [=n] && (I2C [=y] || I2C [=y]=n) && VIDEO_DEV [=n]
- SND_SOC_ROCKCHIP_PDM [=n] && SOUND [=n] && !UML && SND [=n] && SND_SOC [=n] && CLKDEV_LOOKUP [=n] && SND_SOC_ROCKCHIP [=n]
- COMMON_CLK_QCOM [=n] && COMMON_CLK [=n] && OF [=y] && (ARCH_QCOM || COMPILE_TEST [=y])

but my test config has none of those enabled, so I cannot set RATIONAL.

Quoted 9 lines
Quoted 2 lines

I guess the easiest solution is to have KUNIT or some sub-KUNIT test just select RATIONAL.

Yeah, the easiest thing would be to keep the select RATIONAL that I showed in the example patch.

+David Gow +Brendan Higgins as they both particularly wanted to avoid having any tests select their dependencies, however.

This came from a thread[1], and one of the causes behind it was not wanting to have KUNIT_ALL_TESTS enable things like filesystems and drivers which wouldn't otherwise be built.

Personally, I think that RATIONAL is probably an okay thing to select
here: it's not as heavyweight as drivers/filesystems/etc, and our general guidance here is "avoid select where sensible to do so", not "don't use it under any circumstances".

The other option would be to have a separate config entry which just selected RATIONAL, but even I think that's probably uglier, however nice it is for guaranteeing flexibility.

[1]: https://lore.kernel.org/linux-ext4/[email protected]/T/#t

Quoted 36 lines
Quoted 36 lines
Quoted 15 lines

My confusion is why this doesn't work:

$ ./tools/testing/kunit/kunit.py run --kunitconfig /dev/stdin <<EOF
CONFIG_KUNIT=y
CONFIG_RATIONAL=y
EOF
...
ERROR:root:Provided Kconfig is not contained in validated .config.
Following fields found in kunitconfig, but not in .config:
CONFIG_RATIONAL=y

What it's complaining about is that make ARCH=um olddefconfig is leaving CONFIG_RATIONAL=y unset.

Quoted 16 lines

Stripping out kunit.py, it's this:

$ echo -e 'CONFIG_KUNIT=y\nCONFIG_RATIONAL=y' > .kunit/.config
$ make ARCH=um olddefconfig O=.kunit
$ grep RATIONAL .kunit/.config

I'm not versed in Kconfig enough to know why CONFIG_RATIONAL=y is getting removed.

Quoted 7 lines
Quoted 7 lines

is necessary

lib/math/Kconfig +5 -0
+       default KUNIT_ALL_TESTS
+       help
+               This builds unit tests for the rational number support.
+
+               If unsure, say N.

--
~Randy

#8 lore raw
Quoted 58 lines · David Gow
Quoted 57 lines · Daniel Latypov
Quoted 47 lines · Randy Dunlap
Quoted 22 lines · Daniel Latypov
Quoted 21 lines · Randy Dunlap
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0 -0
index f19bc9734fa7..20460b567493 100644

lib/math/Kconfig config PRIME_NUMBERS · line 23

Quoted 9 lines
lib/math/Kconfig +6 -0
@@ -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

Only to set the symbol CONFIG_RATIONAL.
Then when 'make' descends into the lib/math/ subdir and looks at its Makefile, it will decide to build the binary rational.o.

Quoted 4 lines
Quoted 2 lines

obj-$(CONFIG_RATIONAL) += rational.o

Ack, I understand that much.

Oh! Clearly I misunderstood the problem.

I had to look thru 60 config files before I found one where CONFIG_RATIONAL was not set.

And I'm still not sure, but I believe that it's because it has to be set by some other Kconfig entry doing a 'select' on it.

Here are the kconfigs that select it (on i386, where I found it not set):

- COMMON_CLK [=n] && !HAVE_LEGACY_CLK [=n]
- SERIAL_8250_LPSS [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_8250_MID [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_IMX [=n] && TTY [=n] && HAS_IOMEM [=y] && (ARCH_MXC || COMPILE_TEST [=y])
- VIDEO_V4L2 [=n] && MEDIA_SUPPORT [=n] && (I2C [=y] || I2C [=y]=n) && VIDEO_DEV [=n]
- SND_SOC_ROCKCHIP_PDM [=n] && SOUND [=n] && !UML && SND [=n] && SND_SOC [=n] && CLKDEV_LOOKUP [=n] && SND_SOC_ROCKCHIP [=n]
- COMMON_CLK_QCOM [=n] && COMMON_CLK [=n] && OF [=y] && (ARCH_QCOM || COMPILE_TEST [=y])

Quoted 4 lines

but my test config has none of those enabled, so I cannot set RATIONAL.

I guess the easiest solution is to have KUNIT or some sub-KUNIT test just select RATIONAL.

Yeah, the easiest thing would be to keep the select RATIONAL that I showed in the example patch.

Quoted 7 lines
Quoted 3 lines

+David Gow +Brendan Higgins as they both particularly wanted to avoid having any tests select their dependencies, however.

This came from a thread[1], and one of the causes behind it was not wanting to have KUNIT_ALL_TESTS enable things like filesystems and drivers which wouldn't otherwise be built.

Ah yes, I recognize that thread.

Quoted 4 lines

Personally, I think that RATIONAL is probably an okay thing to select
here: it's not as heavyweight as drivers/filesystems/etc, and our general guidance here is "avoid select where sensible to do so", not "don't use it under any circumstances".

RATIONAL does not have a prompt string, so depending on it would not be reliable. I.e., it is meant to be selected.

Quoted 3 lines

The other option would be to have a separate config entry which just selected RATIONAL, but even I think that's probably uglier, however nice it is for guaranteeing flexibility.

Yes, that's even worse.

Quoted 33 lines

[1]: https://lore.kernel.org/linux-ext4/[email protected]/T/#t

Quoted 31 lines
Quoted 31 lines
Quoted 31 lines

My confusion is why this doesn't work:

$ ./tools/testing/kunit/kunit.py run --kunitconfig /dev/stdin <<EOF
CONFIG_KUNIT=y
CONFIG_RATIONAL=y
EOF
...
ERROR:root:Provided Kconfig is not contained in validated .config.
Following fields found in kunitconfig, but not in .config:
CONFIG_RATIONAL=y

What it's complaining about is that make ARCH=um olddefconfig is leaving CONFIG_RATIONAL=y unset.

Stripping out kunit.py, it's this:

$ echo -e 'CONFIG_KUNIT=y\nCONFIG_RATIONAL=y' > .kunit/.config
$ make ARCH=um olddefconfig O=.kunit
$ grep RATIONAL .kunit/.config

I'm not versed in Kconfig enough to know why CONFIG_RATIONAL=y is getting removed.

Quoted 7 lines
Quoted 7 lines

is necessary

lib/math/Kconfig +5 -0
+       default KUNIT_ALL_TESTS
+       help
+               This builds unit tests for the rational number support.
+
+               If unsure, say N.
Signature · 1 line
~Randy
#9 lore raw
Quoted 70 lines · Randy Dunlap
Quoted 58 lines · David Gow
Quoted 57 lines · Daniel Latypov
Quoted 47 lines · Randy Dunlap
Quoted 22 lines · Daniel Latypov
Quoted 21 lines · Randy Dunlap
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0 -0
index f19bc9734fa7..20460b567493 100644

lib/math/Kconfig config PRIME_NUMBERS · line 23

Quoted 9 lines
lib/math/Kconfig +6 -0
@@ -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

Only to set the symbol CONFIG_RATIONAL.
Then when 'make' descends into the lib/math/ subdir and looks at its Makefile, it will decide to build the binary rational.o.

Quoted 4 lines
Quoted 2 lines

obj-$(CONFIG_RATIONAL) += rational.o

Ack, I understand that much.

Oh! Clearly I misunderstood the problem.

I had to look thru 60 config files before I found one where CONFIG_RATIONAL was not set.

And I'm still not sure, but I believe that it's because it has to be set by some other Kconfig entry doing a 'select' on it.

Here are the kconfigs that select it (on i386, where I found it not set):

- COMMON_CLK [=n] && !HAVE_LEGACY_CLK [=n]
- SERIAL_8250_LPSS [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_8250_MID [=n] && TTY [=n] && HAS_IOMEM [=y] && SERIAL_8250 [=n] && PCI [=n] && (X86 [=y] || COMPILE_TEST [=y])
- SERIAL_IMX [=n] && TTY [=n] && HAS_IOMEM [=y] && (ARCH_MXC || COMPILE_TEST [=y])
- VIDEO_V4L2 [=n] && MEDIA_SUPPORT [=n] && (I2C [=y] || I2C [=y]=n) && VIDEO_DEV [=n]
- SND_SOC_ROCKCHIP_PDM [=n] && SOUND [=n] && !UML && SND [=n] && SND_SOC [=n] && CLKDEV_LOOKUP [=n] && SND_SOC_ROCKCHIP [=n]
- COMMON_CLK_QCOM [=n] && COMMON_CLK [=n] && OF [=y] && (ARCH_QCOM || COMPILE_TEST [=y])

Quoted 4 lines

but my test config has none of those enabled, so I cannot set RATIONAL.

I guess the easiest solution is to have KUNIT or some sub-KUNIT test just select RATIONAL.

Yeah, the easiest thing would be to keep the select RATIONAL that I showed in the example patch.

Quoted 7 lines
Quoted 3 lines

+David Gow +Brendan Higgins as they both particularly wanted to avoid having any tests select their dependencies, however.

This came from a thread[1], and one of the causes behind it was not wanting to have KUNIT_ALL_TESTS enable things like filesystems and drivers which wouldn't otherwise be built.

Ah yes, I recognize that thread.

Quoted 7 lines
Quoted 4 lines

Personally, I think that RATIONAL is probably an okay thing to select
here: it's not as heavyweight as drivers/filesystems/etc, and our general guidance here is "avoid select where sensible to do so", not "don't use it under any circumstances".

RATIONAL does not have a prompt string, so depending on it would not be reliable. I.e., it is meant to be selected.

Yeah: let's just select it then.

It's better to have KUNIT_ALL_TESTS pull in something extra than to have tests we've no reliable way of enabling, IMHO.

Quoted 44 lines
Quoted 3 lines

The other option would be to have a separate config entry which just selected RATIONAL, but even I think that's probably uglier, however nice it is for guaranteeing flexibility.

Yes, that's even worse.

Quoted 33 lines

[1]: https://lore.kernel.org/linux-ext4/[email protected]/T/#t

Quoted 31 lines
Quoted 31 lines
Quoted 31 lines

My confusion is why this doesn't work:

$ ./tools/testing/kunit/kunit.py run --kunitconfig /dev/stdin <<EOF
CONFIG_KUNIT=y
CONFIG_RATIONAL=y
EOF
...
ERROR:root:Provided Kconfig is not contained in validated .config.
Following fields found in kunitconfig, but not in .config:
CONFIG_RATIONAL=y

What it's complaining about is that make ARCH=um olddefconfig is leaving CONFIG_RATIONAL=y unset.

Stripping out kunit.py, it's this:

$ echo -e 'CONFIG_KUNIT=y\nCONFIG_RATIONAL=y' > .kunit/.config
$ make ARCH=um olddefconfig O=.kunit
$ grep RATIONAL .kunit/.config

I'm not versed in Kconfig enough to know why CONFIG_RATIONAL=y is getting removed.

Quoted 7 lines
Quoted 7 lines

is necessary

lib/math/Kconfig +5 -0
+       default KUNIT_ALL_TESTS
+       help
+               This builds unit tests for the rational number support.
+
+               If unsure, say N.

--
~Randy

#10 lore raw
In reply to Randy Dunlap
Quoted 8 lines · Randy Dunlap
Quoted 5 lines

Personally, I think that RATIONAL is probably an okay thing to select
here: it's not as heavyweight as drivers/filesystems/etc, and our general guidance here is "avoid select where sensible to do so", not "don't use it under any circumstances".

RATIONAL does not have a prompt string, so depending on it would not be reliable. I.e., it is meant to be selected.

Yes, there are no out of tree or userspace users of it. The only possible way to use it, is if some code in the kernel uses it. So that code can select it.

If it could be used by out of tree modules, then there should be an entry for it, like some of the compression and crc routines got so they could be turned on for out of tree modules when nothing in the kernel config used them.

#11 lore raw
In reply to Andy Shevchenko
Quoted 7 lines · Andy Shevchenko

On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:

This misses the test cases (*). Please, develop them with Daniel.

*) We usually don't accept changes in the generic libraries without test cases.

Fixes tag?

Is there a bug report on a tracker? I just got the email from Yigua.

Quoted 10 lines

lib/math/rational.c void rational_best_approximation( · line 96

Quoted 9 lines
lib/math/rational.c +4 -1
+                     /* 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;
                      }
Quoted 2 lines

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

I started that, but it had no advantages and some disadvantages.

Basically, there are three cases: too large, too small & closest to zero, too small & closest to non-zero. This code can handle those three cases by adding three branches, if(d1), if(n1), and if(!d1). The truth values we need already exist at this point the algorithm.

If it's at the start, then there still needs to be the three branches for each case. But the values to test must be calculated too.

What's more, it's possible that the value is exactly representable in the allowed range. That's actual appears to be the most common use case, reducing a fraction to lowest terms (*). By putting the tests in the "terminate because of limits" case, they don't need to happen when "terminate because exact value find" is the result. If the check was first, then it would always happen, even if it wouldn't have been necessary.

And the time it took to find this bug shows us that out of bounds inputs are not a common case, so putting that on the hot path by checking it first at the expense of the reducing to lowest terms path doesn't make sense.

(*) One could write a reduce to lowest terms function with an easier interface. It could be a trivial one expression wrapper around rational_best_approximation(). It could also be a simpler function, but I think it would still perform the exact same sequence of divisions and moduli, so it wouldn't really make any difference.

#12 lore raw
Quoted 5 lines · Trent Piepho
Quoted 2 lines · Andy Shevchenko

On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:

Quoted 7 lines
Quoted 5 lines

This misses the test cases (*). Please, develop them with Daniel.

*) We usually don't accept changes in the generic libraries without test cases.

Fixes tag?

Is there a bug report on a tracker? I just got the email from Yigua.

You'd want to add:

Fixes 323dd2c3ed06 ("lib/math/rational.c: fix possible incorrect

result from rational fractions helper")

Steps taken:

$ git log --oneline lib/math/rational.c
b296a6d53339 kernel.h: split out min()/max() et al. helpers  <- irrelevant
d89775fc929c lib/: replace HTTP links with HTTPS ones  <- just comments changes
323dd2c3ed06 lib/math/rational.c: fix possible incorrect result from
rational fractions helper
2c64e9cb0b6b lib: Move mathematic helpers to separate folder

At 2c64e9cb0b6b lib: Move mathematic helpers to separate folder [13:31:06] [FAILED] rational_bug_test
[13:31:06] # rational_bug_test: EXPECTATION FAILED at
lib/math/rational_kunit.c:12
[13:31:06] Expected n == 255, but
[13:31:06] n == 1
[13:31:06] # rational_bug_test: EXPECTATION FAILED at
lib/math/rational_kunit.c:13
[13:31:06] Expected d == 1, but
[13:31:06] d == 0
[13:31:06] not ok 1 - rational_bug_test

At 323dd2c3ed06 lib/math/rational.c: fix possible incorrect result from rational fractions helper
[13:32:50] ======== [CRASHED] rational ========
[13:32:50] [CRASHED]
[13:32:50] Kernel panic - not syncing: Kernel mode signal 8 [13:32:50] CPU: 0 PID: 15 Comm: kunit_try_catch Not tainted 5.13.0-rc1-15148-ge3e4bc7272a1-dirty #34
[13:32:50] Received SIGSEGV in SIGSEGV handler, aborting stack trace! [13:32:50]
[13:32:50] ============================================================

So this crash was introduced by 323dd2c3ed06. Anyone who has 323dd2c3ed06 will want to cherrypick this fix.

Quoted 42 lines
Quoted 11 lines

lib/math/rational.c void rational_best_approximation( · line 96

Quoted 10 lines
lib/math/rational.c +4 -1
+                     /* 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;
                      }
Quoted 2 lines

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

I started that, but it had no advantages and some disadvantages.

Basically, there are three cases: too large, too small & closest to zero, too small & closest to non-zero. This code can handle those three cases by adding three branches, if(d1), if(n1), and if(!d1). The truth values we need already exist at this point the algorithm.

If it's at the start, then there still needs to be the three branches for each case. But the values to test must be calculated too.

What's more, it's possible that the value is exactly representable in the allowed range. That's actual appears to be the most common use case, reducing a fraction to lowest terms (*). By putting the tests in the "terminate because of limits" case, they don't need to happen when "terminate because exact value find" is the result. If the check was first, then it would always happen, even if it wouldn't have been necessary.

And the time it took to find this bug shows us that out of bounds inputs are not a common case, so putting that on the hot path by checking it first at the expense of the reducing to lowest terms path doesn't make sense.

(*) One could write a reduce to lowest terms function with an easier interface. It could be a trivial one expression wrapper around rational_best_approximation(). It could also be a simpler function, but I think it would still perform the exact same sequence of divisions and moduli, so it wouldn't really make any difference.

#13 lore raw
In reply to Trent Piepho
Quoted 11 lines · Trent Piepho
Quoted 7 lines · Andy Shevchenko

On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:

This misses the test cases (*). Please, develop them with Daniel.

*) We usually don't accept changes in the generic libraries without test cases.

Fixes tag?

Is there a bug report on a tracker? I just got the email from Yigua.

Fixes tag refers to the existing commit that brought the bug. Also you may need to add Reported-by tag since Yigua reported it.

...

Quoted 21 lines
Quoted 2 lines

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

I started that, but it had no advantages and some disadvantages.

Basically, there are three cases: too large, too small & closest to zero, too small & closest to non-zero. This code can handle those three cases by adding three branches, if(d1), if(n1), and if(!d1). The truth values we need already exist at this point the algorithm.

If it's at the start, then there still needs to be the three branches for each case. But the values to test must be calculated too.

What's more, it's possible that the value is exactly representable in the allowed range. That's actual appears to be the most common use case, reducing a fraction to lowest terms (*). By putting the tests in the "terminate because of limits" case, they don't need to happen when "terminate because exact value find" is the result. If the check was first, then it would always happen, even if it wouldn't have been necessary.

Quoted 4 lines

And the time it took to find this bug shows us that out of bounds inputs are not a common case, so putting that on the hot path by checking it first at the expense of the reducing to lowest terms path doesn't make sense.

Thanks for detailed explanation of your view to the current state of the code. As you noticed I am not insisting on refactoring or so, I was rather wondering if it can be done in the future. Still we might need some performance tests.

Daniel, does KUnit have a capability to test performance? Like running test case 1M times or so and calc average (median?) time of execution.

Quoted 5 lines

(*) One could write a reduce to lowest terms function with an easier interface. It could be a trivial one expression wrapper around rational_best_approximation(). It could also be a simpler function, but I think it would still perform the exact same sequence of divisions and moduli, so it wouldn't really make any difference.

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#14 lore raw
Quoted 8 lines · Andy Shevchenko
Quoted 6 lines · Trent Piepho
Quoted 4 lines · Andy Shevchenko

On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:

This misses the test cases (*). Please, develop them with Daniel.

Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

*) We usually don't accept changes in the generic libraries without test cases.

Fixes tag?

Is there a bug report on a tracker? I just got the email from Yigua.

Fixes tag refers to the existing commit that brought the bug. Also you may need to add Reported-by tag since Yigua reported it.

I did add a Reported-by tag. Wasn't clear to me fixing a specific commit was entirely appropriate since not handling out of range values correctly has been there all along.

#15 lore raw
Quoted 12 lines · Trent Piepho
Quoted 10 lines · Andy Shevchenko
Quoted 8 lines · Trent Piepho
Quoted 6 lines · Andy Shevchenko

On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:

This misses the test cases (*). Please, develop them with Daniel.

*) We usually don't accept changes in the generic libraries without test cases.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines
Quoted 1 line

Fixes tag?

Is there a bug report on a tracker? I just got the email from Yigua.

Fixes tag refers to the existing commit that brought the bug. Also you may need to add Reported-by tag since Yigua reported it.

I did add a Reported-by tag.

Oh, I haven't seen it in the context left, but yes, I see it in the original mail, thanks!

Quoted 3 lines

Wasn't clear to me fixing a specific
commit was entirely appropriate since not handling out of range values correctly has been there all along.

Daniel proposed one, wouldn't it be good enough?

Signature · 2 lines
With Best Regards,
Andy Shevchenko
#16 lore raw
In reply to Andy Shevchenko
Quoted 45 lines · Andy Shevchenko
Quoted 11 lines · Trent Piepho
Quoted 7 lines · Andy Shevchenko

On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:

This misses the test cases (*). Please, develop them with Daniel.

*) We usually don't accept changes in the generic libraries without test cases.

Fixes tag?

Is there a bug report on a tracker? I just got the email from Yigua.

Fixes tag refers to the existing commit that brought the bug. Also you may need to add Reported-by tag since Yigua reported it.

...

Quoted 21 lines
Quoted 2 lines

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

I started that, but it had no advantages and some disadvantages.

Basically, there are three cases: too large, too small & closest to zero, too small & closest to non-zero. This code can handle those three cases by adding three branches, if(d1), if(n1), and if(!d1). The truth values we need already exist at this point the algorithm.

If it's at the start, then there still needs to be the three branches for each case. But the values to test must be calculated too.

What's more, it's possible that the value is exactly representable in the allowed range. That's actual appears to be the most common use case, reducing a fraction to lowest terms (*). By putting the tests in the "terminate because of limits" case, they don't need to happen when "terminate because exact value find" is the result. If the check was first, then it would always happen, even if it wouldn't have been necessary.

Quoted 4 lines

And the time it took to find this bug shows us that out of bounds inputs are not a common case, so putting that on the hot path by checking it first at the expense of the reducing to lowest terms path doesn't make sense.

Quoted 7 lines

Thanks for detailed explanation of your view to the current state of the code. As you noticed I am not insisting on refactoring or so, I was rather wondering if it can be done in the future. Still we might need some performance tests.

Daniel, does KUnit have a capability to test performance? Like running test case 1M times or so and calc average (median?) time of execution.

No, it does not.
It also currently lacks an option/flag for running a test multiple times. So one would have to manually modify the test code itself to handle that right now.

(One non-option is to call kunit.py execute in a loop, which will avoid build + config overhead, but it still adds more than we'd find acceptable here).

I don't think this was considered before bc it's unclear what the performance characteristics of UML would be like compared to a more "normal" arch. Brendan's current patchset to add QEMU support into kunit.py makes this a bit better, but still running on a physical machine is still probably safest.

Quoted 12 lines
Quoted 6 lines

(*) One could write a reduce to lowest terms function with an easier interface. It could be a trivial one expression wrapper around rational_best_approximation(). It could also be a simpler function, but I think it would still perform the exact same sequence of divisions and moduli, so it wouldn't really make any difference.

--
With Best Regards,
Andy Shevchenko