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>
 <CA+7tXigG7QVYOtkuFrqciHfuxE4+c0JM9z8r0e9rooTjjz5PYA@mail.gmail.com>
 <CAHp75VdeSkQSHjwTFObj84TyOOW2dh9LW3Ci9L7=iDFTbEvRoA@mail.gmail.com> <20210522190759.GA9755@basil.scara.com>
In-Reply-To: <20210522190759.GA9755@basil.scara.com>
From:   Trent Piepho <tpiepho@gmail.com>
Date:   Sun, 23 May 2021 20:20:00 -0700
Message-ID: <CA+7tXigHEwwnVqjD=Hi1HBCxrBfeuvieK8v=W4nvgsm+ipaLmQ@mail.gmail.com>
Subject: Re: A divide by zero bug in lib/math/rational.c (with triggering input)
To:     Oskar Schirmer <oskar@scara.com>
Cc:     Andy Shevchenko <andy.shevchenko@gmail.com>,
        Daniel Latypov <dlatypov@google.com>,
        Yiyuan guo <yguoaz@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>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Sat, May 22, 2021 at 12:08 PM Oskar Schirmer <oskar@scara.com> wrote:
> On Fri, May 21, 2021 at 12:53:27 +0300, Andy Shevchenko wrote:
> > On Fri, May 21, 2021 at 12:20 PM Trent Piepho <tpiepho@gmail.com> wrote:
> > > On Fri, May 21, 2021 at 12:55 AM Yiyuan guo <yguoaz@gmail.com> wrote:
>
> Sorry, it does not. E.g. with the given fraction of 31/1000
> and the registers restricted to 8 and 5 bits respectively, the
> proposed fixed function would still divide by zero, because
> n1 == 0. If it was for the division by d1, the test for !d1

Yes, values less than 1 less than the smallest allowed non-zero value
will divide by zero will finish on the 2nd iteration, with n1 == 0,
and divide by zero.

The finished patch I've since sent fixes this.

> Moreover, for a fraction of 33/1000, both the original and
> the latest version would produce 1/30, which is off by some
> 1.01%, but the proposed fixed version would result in 1/31,
> which is worse: 2.24% off.

Finished patch correctly produces 1/30 in this case.

> I think the original function was not so bad. And the code it
> produced was much shorter than the latest version, although
> this might not be an argument in times, where a simple OS
> kernel is beyond the 40MB.

I measured this.  I've compared the original, which did not consider
semi-convergents nor out of range values, the current version, which
does semi-convergents but fails on out of range, and the patched
version, which handles that too.

Size in bytes:
X64 149 205 278
ARM 164 220 300

So 129 bytes on x64 and 136 bytes on ARM.  Not all that much.  I
didn't try writing a special check for large/small inputs in the older
code to see how large that was, for a more like-to-like comparison to
my latest patch.