lib/math/rational.c: Fix divide by zero
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
@@ -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
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
Reported-by Yiyuan Guo <[email protected]>Signed-off-by Trent Piepho <[email protected]>
...
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
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
@@ -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
@@ -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
@@ -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
Reported-by Yiyuan Guo <[email protected]>Signed-off-by Trent Piepho <[email protected]>...
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
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0
-0
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
Quoted 21 lines · Randy Dunlap
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0
-0lib/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 thisOnly to set the symbol
CONFIG_RATIONAL.
Then when 'make' descends into thelib/math/subdir and looks at itsMakefile, 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
Quoted 22 lines · Daniel Latypov
Quoted 21 lines · Randy Dunlap
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0
-0lib/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 thisOnly to set the symbol
CONFIG_RATIONAL.
Then when 'make' descends into thelib/math/subdir and looks at itsMakefile, 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=yWhat it's complaining about is that
make ARCH=um olddefconfigis leavingCONFIG_RATIONAL=yunset.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/.configI'm not versed in
Kconfigenough to know whyCONFIG_RATIONAL=yis 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
Quoted 47 lines · Randy Dunlap
Quoted 22 lines · Daniel Latypov
Quoted 21 lines · Randy Dunlap
Quoted 5 lines · Daniel Latypov
lib/math/Kconfig +0
-0lib/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 thisOnly to set the symbol
CONFIG_RATIONAL.
Then when 'make' descends into thelib/math/subdir and looks at itsMakefile, 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_RATIONALwas not set.And I'm still not sure, but I believe that it's because it has to be set by some other
Kconfigentry 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=yWhat it's complaining about is that
make ARCH=um olddefconfigis leavingCONFIG_RATIONAL=yunset.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/.configI'm not versed in
Kconfigenough to know whyCONFIG_RATIONAL=yis 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
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
-0lib/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 thisOnly to set the symbol
CONFIG_RATIONAL.
Then when 'make' descends into thelib/math/subdir and looks at itsMakefile, 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_RATIONALwas not set.And I'm still not sure, but I believe that it's because it has to be set by some other
Kconfigentry 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 RATIONALthat I showed in the example patch.+David Gow +Brendan Higgins as they both particularly wanted to avoid having any tests
selecttheir 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=yWhat it's complaining about is that
make ARCH=um olddefconfigis leavingCONFIG_RATIONAL=yunset.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/.configI'm not versed in
Kconfigenough to know whyCONFIG_RATIONAL=yis 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
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
-0lib/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 thisOnly to set the symbol
CONFIG_RATIONAL.
Then when 'make' descends into thelib/math/subdir and looks at itsMakefile, 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_RATIONALwas not set.And I'm still not sure, but I believe that it's because it has to be set by some other
Kconfigentry 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 RATIONALthat 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
selecttheir dependencies, however.This came from a thread[1], and one of the causes behind it was not wanting to have
KUNIT_ALL_TESTSenable 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 asdrivers/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=yWhat it's complaining about is that
make ARCH=um olddefconfigis leavingCONFIG_RATIONAL=yunset.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/.configI'm not versed in
Kconfigenough to know whyCONFIG_RATIONAL=yis 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
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
-0lib/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 thisOnly to set the symbol
CONFIG_RATIONAL.
Then when 'make' descends into thelib/math/subdir and looks at itsMakefile, 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_RATIONALwas not set.And I'm still not sure, but I believe that it's because it has to be set by some other
Kconfigentry 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 RATIONALthat 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
selecttheir dependencies, however.This came from a thread[1], and one of the causes behind it was not wanting to have
KUNIT_ALL_TESTSenable 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 asdrivers/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=yWhat it's complaining about is that
make ARCH=um olddefconfigis leavingCONFIG_RATIONAL=yunset.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/.configI'm not versed in
Kconfigenough to know whyCONFIG_RATIONAL=yis 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
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 asdrivers/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.
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.
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:
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 atlib/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 atlib/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.
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
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.
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
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