Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Message-ID: <2f07167152e807917acb8199939886ed8a3a00f9.camel@gmail.com>
Subject: Re: [PATCH] lib: Fix possible incorrect result from rational
 fractions helper
From:   tpiepho@gmail.com
To:     Andrew Morton <akpm@linux-foundation.org>
Cc:     linux-kernel@vger.kernel.org, Oskar Schirmer <oskar@scara.com>
Date:   Wed, 03 Apr 2019 20:41:30 -0700
References: <20190330205855.19396-1-tpiepho@gmail.com>
         <20190401222228.5692d7e8d5b979a8c574e76c@linux-foundation.org>
In-Reply-To: <20190401222228.5692d7e8d5b979a8c574e76c@linux-foundation.org>
Content-Type: text/plain; charset="UTF-8"
User-Agent: Evolution 3.30.5 (3.30.5-1.fc29) 
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On Mon, Apr 1, 2019 at 10:22 PM Andrew Morton <
akpm@linux-foundation.org> wrote:

> On Sat, 30 Mar 2019 13:58:55 -0700 Trent Piepho <tpiepho@gmail.com>
> wrote:
> > In some cases the previous algorithm would not return the closest
> > approximation.  This would happen when a semi-convergent was the
> > closest, as the previous algorithm would only consider convergents.
> > 
> > As an example, consider an initial value of 5/4, and trying to find
> > the
> > closest approximation with a maximum of 4 for numerator and
> > denominator.
> > The previous algorithm would return 1/1 as the closest
> > approximation,
> > while this version will return the correct answer of 4/3.
> 
> What are the userspace-visible runtime effects of this change?

Ok, I looked into this in some detail.

This routine is used in two places in the video4linux code, but in
those cases it is only used to reduce a fraction to lowest terms, which
the existing code will do correctly.  This could be done more
efficiently with a different library routine but it would still be the
Euclidean alogrithm at its heart.  So no change.

The remain users are places where a fractional PLL divider is
programmed.  What would happen is something asked for a clock of X MHz
but instead gets Y MHz, where Y is close to X but not exactly due to
the hardware limitations.  After this change they might, in some cases,
get Y' MHz, where Y' is a little closer to X then Y was.

Users like this are: Three UARTs, in 8250_mid, 8250_lpss, and
imx.  One GPU in vp4_hdmi.  And three clock drivers, clk-cdce706, clk-si5351, and clk-fractional-divider.  The last is a generic clock driver and so would have more users referenced via device tree entries.

I think there's a bug in that one, it's limiting an N bit field that is
offset-by-1 to the range 0 .. (1<<N)-2, when it should be (1<<N)-1 as
the upper limit.

I have an IMX system, one of the UARTs using this, so I can provide a
real example.  If I request a custom baud rate of 1499978, the driver
will program the PLL to produce a baud rate of 1500000.  After this
change, the fractional divider in the UART is programmed to a ratio of
65535/65536, which produces a baud rate of 1499977.0625.  Closer to the
requested value.