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: <CAM7=BFoktwgy=T0GK6Mpmp2gYToCUs=CrM29MRWw8O7TPypQ8w@mail.gmail.com>
 <CAHp75Vf8kQ73w0R9ieDNjDVkxM-V83QRN9mc6BjRZA8xHpPNAA@mail.gmail.com>
 <CAHp75Vft8pnA+m0C=Ok7nRyjERAd2uJJ4q6HcN460j0Hir6Kaw@mail.gmail.com> <CAM7=BFoH7Q+YHvPFnHM4j72ORHQp4gTjHFjnfeLsV2-30ZLNYw@mail.gmail.com>
In-Reply-To: <CAM7=BFoH7Q+YHvPFnHM4j72ORHQp4gTjHFjnfeLsV2-30ZLNYw@mail.gmail.com>
From:   Trent Piepho <tpiepho@gmail.com>
Date:   Fri, 21 May 2021 02:20:37 -0700
Message-ID: <CA+7tXigG7QVYOtkuFrqciHfuxE4+c0JM9z8r0e9rooTjjz5PYA@mail.gmail.com>
Subject: Re: A divide by zero bug in lib/math/rational.c (with triggering input)
To:     Yiyuan guo <yguoaz@gmail.com>
Cc:     Andy Shevchenko <andy.shevchenko@gmail.com>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        "andy@kernel.org" <andy@kernel.org>,
        "akpm@linux-foundation.org" <akpm@linux-foundation.org>,
        "oskar@scara.com" <oskar@scara.com>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Fri, May 21, 2021 at 12:55 AM Yiyuan guo <yguoaz@gmail.com> wrote:
>
> Thanks for your timely response.
>
> I am not familiar with the theorem. But any input satisfying the
> condition below will
> trigger a divide by zero at the first loop iteration:
>
> (given_numerator / given_denominator > max_numerator) || (1 +
> given_numerator / given_denominator > max_denominator)

I think the error can only occur when the loop exits on the 1st
iteration, when d1 is still zero.  In this case the prior convergent,
n1/d1 = 1/0, does not really exist as this is the 1st iteration.  The
actual series of convergents generated will never have zero terms,
because we stop at zero, so there will never be zero from the prior
iteration as we would have stopped there.

I think the prior version of the code, which did not consider
semi-convergents, would have determined the 1st convergent, 314/1,
exceeded the bounds and would return the prior one, 1/0, without
generating an exception but also not a correct answer, since 1/0 isn't
really part of the series, it's just an initial value to make the math
that generates the series work (d2 = a * d1 + d0).

With semi-convergents, this can actually get the correct answer.  The
best semi-convergent term is correctly found, (max_numerator - n0) /
n1 = 255.  Using this would return 255/1, which is in this case the
best answer.

But the "is semi-convergent better than prior convergent" test does
not consider what I think is a special case of there being no prior
convergent.  In this case it should always select the semi-convergent.

I think this handles it:

                if ((n2 > max_numerator) || (d2 > max_denominator)) {
                       unsigned long t = (max_numerator - n0) / n1;
                       if (!d1 || (t = min(t, max_denominator - d0) / d1)) ||
                           2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
                               n1 = n0 + t * n1;
                               d1 = d0 + t * d1;
                       }
                       break;
               }

Above !d1 is the special case.  I don't like that, but I'm not seeing
a way to think about the problect that doesn't involve one.


> I think such a condition is rather complex and may not be enforced by
> all callers of this function.
>
> On Fri, May 21, 2021 at 3:42 PM Andy Shevchenko
> <andy.shevchenko@gmail.com> wrote:
> >
> >
> >
> > On Friday, May 21, 2021, Andy Shevchenko <andy.shevchenko@gmail.com> wrote:
> >>
> >>
> >>
> >> On Friday, May 21, 2021, Yiyuan guo <yguoaz@gmail.com> wrote:
> >>>
> >>> In the file lib/math/rational.c, the function
> >>> rational_best_approximation has the following
> >>> code:
> >>>
> >>> void rational_best_approximation(
> >>>     unsigned long given_numerator, unsigned long given_denominator,
> >>>     unsigned long max_numerator, unsigned long max_denominator,
> >>>     unsigned long *best_numerator, unsigned long *best_denominator) {
> >>>    ...
> >>>    if ((n2 > max_numerator) || (d2 > max_denominator)) {
> >>>             unsigned long t = min((max_numerator - n0) / n1,
> >>>                           (max_denominator - d0) / d1);
> >>>    ...
> >>> }
> >>>
> >>> d1 may be equal to zero when performing the division, leading to a
> >>> divide by zero problem.
> >>>
> >>> One input  to trigger the divide by zero bug is:
> >>> rational_best_approximation(31415, 100, (1 << 8) - 1, (1 << 5) - 1, &n, &d)
> >>
> >>
> >>
> >> Have you read a theorem about this? TL;DR; as far as I can see the input data is not suitable for this function.
> >>
> >
> >
> > I think we may add the proper check and saturate the output which in your case should be (255,1).
> >
> >>
> >>
> >> --
> >> With Best Regards,
> >> Andy Shevchenko
> >>
> >>
> >
> >
> > --
> > With Best Regards,
> > Andy Shevchenko
> >
> >