[PATCH] lib/math/rational.c: Fix divide by zero

[PATCH] lib/math/rational.c: Fix divide by zero

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

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.

Reported-by: Yiyuan Guo <yguoaz@gmail.com>
Signed-off-by: Trent Piepho <tpiepho@gmail.com>
---
 lib/math/rational.c | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

diff --git a/lib/math/rational.c b/lib/math/rational.c
index 9781d521963d..c0ab51d8fbb9 100644
--- a/lib/math/rational.c
+++ b/lib/math/rational.c
@@ -12,6 +12,7 @@
 #include <linux/compiler.h>
 #include <linux/export.h>
 #include <linux/minmax.h>
+#include <linux/limits.h>
 
 /*
  * calculate best rational approximation for a given fraction
@@ -78,13 +79,18 @@ void rational_best_approximation(
 		 * found below as 't'.
 		 */
 		if ((n2 > max_numerator) || (d2 > max_denominator)) {
-			unsigned long t = min((max_numerator - n0) / n1,
-					      (max_denominator - d0) / d1);
+			unsigned long t = ULONG_MAX;
 
-			/* This tests if the semi-convergent is closer
-			 * than the previous convergent.
+			if (d1)
+				t = (max_denominator - d0) / d1;
+			if (n1)
+				t = min(t, (max_numerator - n0) / n1);
+
+			/* This tests if the semi-convergent is closer than the previous
+			 * convergent.  If d1 is zero there is no previous convergent as this
+			 * is the 1st iteration, so always choose the semi-convergent.
 			 */
-			if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
+			if (!d1 || 2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
 				n1 = n0 + t * n1;
 				d1 = d0 + t * d1;
 			}
-- 
2.26.2

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Andy Shevchenko]

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

Thanks for the fix! My comments below.

> If the input is out of the range of the allowed values, either larger
> than the largest value or closer to zero than the smallest non-zero
> allowed value, then a division by zero would occur.
> 
> In the case of input too large, the division by zero will occur on the
> first iteration.  The best result (largest allowed value) will be found
> by always choosing the semi-convergent and excluding the denominator
> based limit when finding it.
> 
> In the case of the input too small, the division by zero will occur on
> the second iteration.  The numerator based semi-convergent should not be
> calculated to avoid the division by zero.  But the semi-convergent vs
> previous convergent test is still needed, which effectively chooses
> between 0 (the previous convergent) vs the smallest allowed fraction
> (best semi-convergent) as the result.

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

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

Fixes tag?

> Reported-by: Yiyuan Guo <yguoaz@gmail.com>
> Signed-off-by: Trent Piepho <tpiepho@gmail.com>

...

> +			/* This tests if the semi-convergent is closer than the previous
> +			 * convergent.  If d1 is zero there is no previous convergent as this
> +			 * is the 1st iteration, so always choose the semi-convergent.
>  			 */
> -			if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
> +			if (!d1 || 2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
>  				n1 = n0 + t * n1;
>  				d1 = d0 + t * d1;
>  			}

I think that refactoring may lead us to check first iteration before even going
into the loop. But it's another story and we may do it later (the algo uses
heavy division anyway, so couple of additional branches probably won't affect
performance too much).

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Daniel Latypov]

On Mon, May 24, 2021 at 3:51 AM Andy Shevchenko
<andriy.shevchenko@intel.com> wrote:
>
> On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:
>
> Thanks for the fix! My comments below.
>
> > If the input is out of the range of the allowed values, either larger
> > than the largest value or closer to zero than the smallest non-zero
> > allowed value, then a division by zero would occur.
> >
> > In the case of input too large, the division by zero will occur on the
> > first iteration.  The best result (largest allowed value) will be found
> > by always choosing the semi-convergent and excluding the denominator
> > based limit when finding it.
> >
> > In the case of the input too small, the division by zero will occur on
> > the second iteration.  The numerator based semi-convergent should not be
> > calculated to avoid the division by zero.  But the semi-convergent vs
> > previous convergent test is still needed, which effectively chooses
> > between 0 (the previous convergent) vs the smallest allowed fraction
> > (best semi-convergent) as the result.
>
> This misses the test cases (*). Please, develop them with Daniel.

FYI, I was leaning towards not having this in the proposed
math_kunit.c, since this code is gated behind CONFIG_RATIONAL=y, while
the others are not.
I.e. I think we want to add a new rational_kunit.c to contain this test case.

I can help write it up if wanted, but I'll give some pointers on how
to do so below.

Trent, https://www.kernel.org/doc/html/latest/dev-tools/kunit/start.html
would be the entry point for KUnit documentation.
After you feel comfortable with the following, I'd recommend
https://www.kernel.org/doc/html/latest/dev-tools/kunit/usage.html#testing-against-multiple-inputs

You can run the tests added via something like this

$ ./tools/testing/kunit/kunit.py run --kunitconfig /dev/stdin <<EOF
CONFIG_KUNIT=y
CONFIG_RATIONAL=y
CONFIG_RATIONAL_KUNIT_TEST=y
EOF

(feel free to put the heredoc into a file, just using it for a
copy-paste friendly one-liner)

given a starting change like this (which I can see crash w/o the fix,
and pass w/ it).

diff --git a/lib/math/Kconfig b/lib/math/Kconfig
index f19bc9734fa7..20460b567493 100644
--- a/lib/math/Kconfig
+++ b/lib/math/Kconfig
@@ -15,3 +15,14 @@ config PRIME_NUMBERS

 config RATIONAL
        bool
+
+config RATIONAL_KUNIT_TEST
+       tristate "KUnit test for rational number support" if !KUNIT_ALL_TESTS
+       # depends on KUNIT && RATIONAL  # this is how it should work, but
+       depends on KUNIT
+       select RATIONAL # I don't grok kconfig enough to know why this
is necessary
+       default KUNIT_ALL_TESTS
+       help
+               This builds unit tests for the rational number support.
+
+               If unsure, say N.
diff --git a/lib/math/Makefile b/lib/math/Makefile
index 7456edb864fc..a11ffdb953ef 100644
--- a/lib/math/Makefile
+++ b/lib/math/Makefile
@@ -6,3 +6,4 @@ obj-$(CONFIG_PRIME_NUMBERS)     += prime_numbers.o
 obj-$(CONFIG_RATIONAL)         += rational.o

 obj-$(CONFIG_TEST_DIV64)       += test_div64.o
+obj-$(CONFIG_RATIONAL_KUNIT_TEST)      += rational_kunit.o
diff --git a/lib/math/rational_kunit.c b/lib/math/rational_kunit.c
new file mode 100644
index 000000000000..88ad0e2baece
--- /dev/null
+++ b/lib/math/rational_kunit.c
@@ -0,0 +1,28 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <kunit/test.h>
+
+#include <linux/rational.h>
+
+static void rational_bug_test(struct kunit *test)
+{
+       unsigned long n = 0, d = 0;
+
+       rational_best_approximation(31415, 100, (1 << 8) - 1, (1 << 5)
- 1, &n, &d);
+       KUNIT_EXPECT_EQ(test, n, 255);
+       KUNIT_EXPECT_EQ(test, d, 1);
+}
+
+static struct kunit_case rational_test_cases[] = {
+       KUNIT_CASE(rational_bug_test),
+       {}
+};
+
+static struct kunit_suite rational_test_suite = {
+       .name = "rational",
+       .test_cases = rational_test_cases,
+};
+
+kunit_test_suites(&rational_test_suite);
+
+MODULE_LICENSE("GPL v2");



>
> *) We usually don't accept changes in the generic libraries without test cases.
>
> Fixes tag?
>
> > Reported-by: Yiyuan Guo <yguoaz@gmail.com>
> > Signed-off-by: Trent Piepho <tpiepho@gmail.com>
>
> ...
>
> > +                     /* This tests if the semi-convergent is closer than the previous
> > +                      * convergent.  If d1 is zero there is no previous convergent as this
> > +                      * is the 1st iteration, so always choose the semi-convergent.
> >                        */
> > -                     if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
> > +                     if (!d1 || 2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
> >                               n1 = n0 + t * n1;
> >                               d1 = d0 + t * d1;
> >                       }
>
> I think that refactoring may lead us to check first iteration before even going
> into the loop. But it's another story and we may do it later (the algo uses
> heavy division anyway, so couple of additional branches probably won't affect
> performance too much).
>
> --
> With Best Regards,
> Andy Shevchenko
>
>

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Randy Dunlap]

On 5/24/21 9:55 AM, Daniel Latypov wrote:
> diff --git a/lib/math/Kconfig b/lib/math/Kconfig
> index f19bc9734fa7..20460b567493 100644
> --- a/lib/math/Kconfig
> +++ b/lib/math/Kconfig
> @@ -15,3 +15,14 @@ config PRIME_NUMBERS
> 
>  config RATIONAL
>         bool
> +
> +config RATIONAL_KUNIT_TEST
> +       tristate "KUnit test for rational number support" if !KUNIT_ALL_TESTS
> +       # depends on KUNIT && RATIONAL  # this is how it should work, but
> +       depends on KUNIT
> +       select RATIONAL # I don't grok kconfig enough to know why this

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


> is necessary
> +       default KUNIT_ALL_TESTS
> +       help
> +               This builds unit tests for the rational number support.
> +
> +               If unsure, say N.


-- 
~Randy

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Daniel Latypov]

On Mon, May 24, 2021 at 3:04 PM Randy Dunlap <rdunlap@infradead.org> wrote:
>
> On 5/24/21 9:55 AM, Daniel Latypov wrote:
> > diff --git a/lib/math/Kconfig b/lib/math/Kconfig
> > index f19bc9734fa7..20460b567493 100644
> > --- a/lib/math/Kconfig
> > +++ b/lib/math/Kconfig
> > @@ -15,3 +15,14 @@ config PRIME_NUMBERS
> >
> >  config RATIONAL
> >         bool
> > +
> > +config RATIONAL_KUNIT_TEST
> > +       tristate "KUnit test for rational number support" if !KUNIT_ALL_TESTS
> > +       # depends on KUNIT && RATIONAL  # this is how it should work, but
> > +       depends on KUNIT
> > +       select RATIONAL # I don't grok kconfig enough to know why this
>
> 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
>

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.

>
> > is necessary
> > +       default KUNIT_ALL_TESTS
> > +       help
> > +               This builds unit tests for the rational number support.
> > +
> > +               If unsure, say N.
>
>
> --
> ~Randy
>

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Randy Dunlap]

On 5/24/21 3:56 PM, Daniel Latypov wrote:
> On Mon, May 24, 2021 at 3:04 PM Randy Dunlap <rdunlap@infradead.org> wrote:
>>
>> On 5/24/21 9:55 AM, Daniel Latypov wrote:
>>> diff --git a/lib/math/Kconfig b/lib/math/Kconfig
>>> index f19bc9734fa7..20460b567493 100644
>>> --- a/lib/math/Kconfig
>>> +++ b/lib/math/Kconfig
>>> @@ -15,3 +15,14 @@ config PRIME_NUMBERS
>>>
>>>  config RATIONAL
>>>         bool
>>> +
>>> +config RATIONAL_KUNIT_TEST
>>> +       tristate "KUnit test for rational number support" if !KUNIT_ALL_TESTS
>>> +       # depends on KUNIT && RATIONAL  # this is how it should work, but
>>> +       depends on KUNIT
>>> +       select RATIONAL # I don't grok kconfig enough to know why this
>>
>> 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
>>
> 
> 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.

> 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.
> 
>>
>>> is necessary
>>> +       default KUNIT_ALL_TESTS
>>> +       help
>>> +               This builds unit tests for the rational number support.
>>> +
>>> +               If unsure, say N.


-- 
~Randy

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Daniel Latypov]

On Mon, May 24, 2021 at 4:30 PM Randy Dunlap <rdunlap@infradead.org> wrote:
>
> On 5/24/21 3:56 PM, Daniel Latypov wrote:
> > On Mon, May 24, 2021 at 3:04 PM Randy Dunlap <rdunlap@infradead.org> wrote:
> >>
> >> On 5/24/21 9:55 AM, Daniel Latypov wrote:
> >>> diff --git a/lib/math/Kconfig b/lib/math/Kconfig
> >>> index f19bc9734fa7..20460b567493 100644
> >>> --- a/lib/math/Kconfig
> >>> +++ b/lib/math/Kconfig
> >>> @@ -15,3 +15,14 @@ config PRIME_NUMBERS
> >>>
> >>>  config RATIONAL
> >>>         bool
> >>> +
> >>> +config RATIONAL_KUNIT_TEST
> >>> +       tristate "KUnit test for rational number support" if !KUNIT_ALL_TESTS
> >>> +       # depends on KUNIT && RATIONAL  # this is how it should work, but
> >>> +       depends on KUNIT
> >>> +       select RATIONAL # I don't grok kconfig enough to know why this
> >>
> >> 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
> >>
> >
> > 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.

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.

>
> > 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.
> >
> >>
> >>> is necessary
> >>> +       default KUNIT_ALL_TESTS
> >>> +       help
> >>> +               This builds unit tests for the rational number support.
> >>> +
> >>> +               If unsure, say N.
>
>
> --
> ~Randy
>

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[David Gow]

On Tue, May 25, 2021 at 7:38 AM Daniel Latypov <dlatypov@google.com> wrote:
>
> On Mon, May 24, 2021 at 4:30 PM Randy Dunlap <rdunlap@infradead.org> wrote:
> >
> > On 5/24/21 3:56 PM, Daniel Latypov wrote:
> > > On Mon, May 24, 2021 at 3:04 PM Randy Dunlap <rdunlap@infradead.org> wrote:
> > >>
> > >> On 5/24/21 9:55 AM, Daniel Latypov wrote:
> > >>> diff --git a/lib/math/Kconfig b/lib/math/Kconfig
> > >>> index f19bc9734fa7..20460b567493 100644
> > >>> --- a/lib/math/Kconfig
> > >>> +++ b/lib/math/Kconfig
> > >>> @@ -15,3 +15,14 @@ config PRIME_NUMBERS
> > >>>
> > >>>  config RATIONAL
> > >>>         bool
> > >>> +
> > >>> +config RATIONAL_KUNIT_TEST
> > >>> +       tristate "KUnit test for rational number support" if !KUNIT_ALL_TESTS
> > >>> +       # depends on KUNIT && RATIONAL  # this is how it should work, but
> > >>> +       depends on KUNIT
> > >>> +       select RATIONAL # I don't grok kconfig enough to know why this
> > >>
> > >> 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
> > >>
> > >
> > > 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.
>
> 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/52959e99-4105-3de9-730c-c46894b82bdd@infradead.org/T/#t

> >
> > > 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.
> > >
> > >>
> > >>> is necessary
> > >>> +       default KUNIT_ALL_TESTS
> > >>> +       help
> > >>> +               This builds unit tests for the rational number support.
> > >>> +
> > >>> +               If unsure, say N.
> >
> >
> > --
> > ~Randy
> >

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Randy Dunlap]

On 5/24/21 5:42 PM, David Gow wrote:
> On Tue, May 25, 2021 at 7:38 AM Daniel Latypov <dlatypov@google.com> wrote:
>>
>> On Mon, May 24, 2021 at 4:30 PM Randy Dunlap <rdunlap@infradead.org> wrote:
>>>
>>> On 5/24/21 3:56 PM, Daniel Latypov wrote:
>>>> On Mon, May 24, 2021 at 3:04 PM Randy Dunlap <rdunlap@infradead.org> wrote:
>>>>>
>>>>> On 5/24/21 9:55 AM, Daniel Latypov wrote:
>>>>>> diff --git a/lib/math/Kconfig b/lib/math/Kconfig
>>>>>> index f19bc9734fa7..20460b567493 100644
>>>>>> --- a/lib/math/Kconfig
>>>>>> +++ b/lib/math/Kconfig
>>>>>> @@ -15,3 +15,14 @@ config PRIME_NUMBERS
>>>>>>
>>>>>>  config RATIONAL
>>>>>>         bool
>>>>>> +
>>>>>> +config RATIONAL_KUNIT_TEST
>>>>>> +       tristate "KUnit test for rational number support" if !KUNIT_ALL_TESTS
>>>>>> +       # depends on KUNIT && RATIONAL  # this is how it should work, but
>>>>>> +       depends on KUNIT
>>>>>> +       select RATIONAL # I don't grok kconfig enough to know why this
>>>>>
>>>>> 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
>>>>>
>>>>
>>>> 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.
>>
>> 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.

Ah yes, I recognize that thread.

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

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

> [1]: https://lore.kernel.org/linux-ext4/52959e99-4105-3de9-730c-c46894b82bdd@infradead.org/T/#t
> 
>>>
>>>> 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.
>>>>
>>>>>
>>>>>> is necessary
>>>>>> +       default KUNIT_ALL_TESTS
>>>>>> +       help
>>>>>> +               This builds unit tests for the rational number support.
>>>>>> +
>>>>>> +               If unsure, say N.


-- 
~Randy

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[David Gow]

On Tue, May 25, 2021 at 9:49 AM Randy Dunlap <rdunlap@infradead.org> wrote:
>
> On 5/24/21 5:42 PM, David Gow wrote:
> > On Tue, May 25, 2021 at 7:38 AM Daniel Latypov <dlatypov@google.com> wrote:
> >>
> >> On Mon, May 24, 2021 at 4:30 PM Randy Dunlap <rdunlap@infradead.org> wrote:
> >>>
> >>> On 5/24/21 3:56 PM, Daniel Latypov wrote:
> >>>> On Mon, May 24, 2021 at 3:04 PM Randy Dunlap <rdunlap@infradead.org> wrote:
> >>>>>
> >>>>> On 5/24/21 9:55 AM, Daniel Latypov wrote:
> >>>>>> diff --git a/lib/math/Kconfig b/lib/math/Kconfig
> >>>>>> index f19bc9734fa7..20460b567493 100644
> >>>>>> --- a/lib/math/Kconfig
> >>>>>> +++ b/lib/math/Kconfig
> >>>>>> @@ -15,3 +15,14 @@ config PRIME_NUMBERS
> >>>>>>
> >>>>>>  config RATIONAL
> >>>>>>         bool
> >>>>>> +
> >>>>>> +config RATIONAL_KUNIT_TEST
> >>>>>> +       tristate "KUnit test for rational number support" if !KUNIT_ALL_TESTS
> >>>>>> +       # depends on KUNIT && RATIONAL  # this is how it should work, but
> >>>>>> +       depends on KUNIT
> >>>>>> +       select RATIONAL # I don't grok kconfig enough to know why this
> >>>>>
> >>>>> 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
> >>>>>
> >>>>
> >>>> 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.
> >>
> >> 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.
>
> Ah yes, I recognize that thread.
>
> > 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.

> > 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.
>
> > [1]: https://lore.kernel.org/linux-ext4/52959e99-4105-3de9-730c-c46894b82bdd@infradead.org/T/#t
> >
> >>>
> >>>> 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.
> >>>>
> >>>>>
> >>>>>> is necessary
> >>>>>> +       default KUNIT_ALL_TESTS
> >>>>>> +       help
> >>>>>> +               This builds unit tests for the rational number support.
> >>>>>> +
> >>>>>> +               If unsure, say N.
>
>
> --
> ~Randy
>

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Trent Piepho]

On Mon, May 24, 2021 at 6:49 PM Randy Dunlap <rdunlap@infradead.org> wrote:
>
> > 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.

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Trent Piepho]

On Mon, May 24, 2021 at 3:51 AM Andy Shevchenko
<andriy.shevchenko@intel.com> wrote:
> On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:
>
> 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.

> > +                     /* 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

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.

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Daniel Latypov]

On Mon, May 24, 2021 at 1:18 PM Trent Piepho <tpiepho@gmail.com> wrote:
>
> On Mon, May 24, 2021 at 3:51 AM Andy Shevchenko
> <andriy.shevchenko@intel.com> wrote:
> > On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:
> >
> > 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.

>
> > > +                     /* 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
>
> 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.

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Andy Shevchenko]

On Mon, May 24, 2021 at 01:17:48PM -0700, Trent Piepho wrote:
> On Mon, May 24, 2021 at 3:51 AM Andy Shevchenko
> <andriy.shevchenko@intel.com> wrote:
> > On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:
> >
> > 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.

...

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

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.

> (*)  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

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Trent Piepho]

On Tue, May 25, 2021 at 2:02 AM Andy Shevchenko
<andriy.shevchenko@intel.com> wrote:
>
> On Mon, May 24, 2021 at 01:17:48PM -0700, Trent Piepho wrote:
> > On Mon, May 24, 2021 at 3:51 AM Andy Shevchenko
> > <andriy.shevchenko@intel.com> wrote:
> > > On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:
> > >
> > > 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.

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.

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Andy Shevchenko]

On Tue, May 25, 2021 at 12:21 PM Trent Piepho <tpiepho@gmail.com> wrote:
> On Tue, May 25, 2021 at 2:02 AM Andy Shevchenko
> <andriy.shevchenko@intel.com> wrote:
> >
> > On Mon, May 24, 2021 at 01:17:48PM -0700, Trent Piepho wrote:
> > > On Mon, May 24, 2021 at 3:51 AM Andy Shevchenko
> > > <andriy.shevchenko@intel.com> wrote:
> > > > On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:
> > > >
> > > > 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.
>
> 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!

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

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH] lib/math/rational.c: Fix divide by zero

[Daniel Latypov]

On Tue, May 25, 2021 at 2:02 AM Andy Shevchenko
<andriy.shevchenko@intel.com> wrote:
>
> On Mon, May 24, 2021 at 01:17:48PM -0700, Trent Piepho wrote:
> > On Mon, May 24, 2021 at 3:51 AM Andy Shevchenko
> > <andriy.shevchenko@intel.com> wrote:
> > > On Sat, May 22, 2021 at 05:18:06PM -0700, Trent Piepho wrote:
> > >
> > > 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.
>
> ...
>
> > > 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.
>
> 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.

>
> > (*)  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
>
>