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>
 <CA+7tXiiogw+bWCj2=QiRBc+sp01dUh1j_mfLJC19CB6Wch0nuQ@mail.gmail.com>
In-Reply-To: <CA+7tXiiogw+bWCj2=QiRBc+sp01dUh1j_mfLJC19CB6Wch0nuQ@mail.gmail.com>
From:   Daniel Latypov <dlatypov@google.com>
Date:   Mon, 24 May 2021 13:35:16 -0700
Message-ID: <CAGS_qxpR3TPRV8YYqr0szk6LAuSrS+xQ45pH-iuBb6zdJy09vw@mail.gmail.com>
Subject: Re: [PATCH] lib/math/rational.c: Fix divide by zero
To:     Trent Piepho <tpiepho@gmail.com>
Cc:     Andy Shevchenko <andriy.shevchenko@intel.com>,
        Linux Kernel Mailing List <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 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.