linux-kernel - Re: [PATCH] lib: Fix possible incorrect result from rational fractions helper

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <2f07167152e807917acb8199939886ed8a3a00f9.camel@gmail.com>
Date:   Wed, 03 Apr 2019 20:41:30 -0700
From:   tpiepho@...il.com
To:     Andrew Morton <akpm@...ux-foundation.org>
Cc:     linux-kernel@...r.kernel.org, Oskar Schirmer <oskar@...ra.com>
Subject: Re: [PATCH] lib: Fix possible incorrect result from rational
 fractions helper

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

> On Sat, 30 Mar 2019 13:58:55 -0700 Trent Piepho <tpiepho@...il.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.