Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
MIME-Version: 1.0
References: <20210523001806.3927609-1-tpiepho@gmail.com> <YKuFPeH0sIFqrBt6@smile.fi.intel.com>
In-Reply-To: <YKuFPeH0sIFqrBt6@smile.fi.intel.com>
From:   Trent Piepho <tpiepho@gmail.com>
Date:   Mon, 24 May 2021 13:17:48 -0700
Message-ID: <CA+7tXiiogw+bWCj2=QiRBc+sp01dUh1j_mfLJC19CB6Wch0nuQ@mail.gmail.com>
Subject: Re: [PATCH] lib/math/rational.c: Fix divide by zero
To:     Andy Shevchenko <andriy.shevchenko@intel.com>
Cc:     Daniel Latypov <dlatypov@google.com>, linux-kernel@vger.kernel.org,
        andy@kernel.org, Andrew Morton <akpm@linux-foundation.org>,
        Oskar Schirmer <oskar@scara.com>, Yiyuan Guo <yguoaz@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

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.