linux-kernel - Re: [RFC PATCH] clk: fractional-divider: Correct max_{m,n} handed over to rational_best

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] [thread-next>] [day] [month] [year] [list]
Message-ID: <CAHp75VfFx4eDF484QKXgB=rhu3AptnDvX+2C+qd+U_3atfjnjQ@mail.gmail.com>
Date:   Thu, 15 Jul 2021 11:14:49 +0300
From:   Andy Shevchenko <andy.shevchenko@...il.com>
To:     Liu Ying <victor.liu@....com>
Cc:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        linux-clk <linux-clk@...r.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        Heikki Krogerus <heikki.krogerus@...ux.intel.com>,
        Michael Turquette <mturquette@...libre.com>,
        Stephen Boyd <sboyd@...nel.org>,
        Dong Aisheng <aisheng.dong@....com>,
        NXP Linux Team <linux-imx@....com>,
        Jacky Bai <ping.bai@....com>
Subject: Re: [RFC PATCH] clk: fractional-divider: Correct max_{m,n} handed
 over to rational_best_approximation()

On Thu, Jul 15, 2021 at 11:02 AM Andy Shevchenko
<andy.shevchenko@...il.com> wrote:
> On Thu, Jul 15, 2021 at 8:51 AM Liu Ying <victor.liu@....com> wrote:
> > On Wed, 2021-07-14 at 13:46 +0300, Andy Shevchenko wrote:
> > > On Wed, Jul 14, 2021 at 01:38:22PM +0300, Andy Shevchenko wrote:
> > > > On Wed, Jul 14, 2021 at 06:10:46PM +0800, Liu Ying wrote:
> > > > > On Wed, 2021-07-14 at 12:12 +0300, Andy Shevchenko wrote:
> > > > > > On Wed, Jul 14, 2021 at 02:41:29PM +0800, Liu Ying wrote:
> > > >
> > > > ...
> > > >
> > > > > > > /*
> > > > > > >  * Get rate closer to *parent_rate to guarantee there is no overflow
> > > > > > >  * for m and n. In the result it will be the nearest rate left shifted
> > > > > > >  * by (scale - fd->nwidth) bits.
> > > > > > >  */
> > > > > >
> > > > > > I don't know how to rephrase above comment better.
> > > > > >
> > > > > > > scale = fls_long(*parent_rate / rate - 1);
> > > > > > > if (scale > fd->nwidth)
> > > > > > >       rate <<= scale - fd->nwidth;
> > > > > >
> > > > > > This takes an advantage of the numbers be in a form of
> > > > > >
> > > > > >         n = k * 2^m, (1)
> > > > > >
> > > > > > where m will be scale in the snippet above. Thus, if n can be represented by
> > > > > > (1), we opportunistically reduce amount of bits needed for it by shifting right
> > > > > > by m bits.
> > > > > > Does it make sense?
> > > > >
> > > > > Thanks for your explaination.
> > > > > But, sorry, Jacky and I still don't understand this.
> > >
> > > It seems I poorly chose the letters for (1). Let's rewrite above as
> > >
> > > This takes an advantage of the numbers be in a form of
> > >
> > >       a = k * 2^b, (1)
> > >
> > > where b will be scale in the snippet above. Thus, if a can be represented by
> > > (1), we opportunistically reduce amount of bits needed for it by shifting right
> > > by b bits.
> > >
> > > Also note, "shifting right" here is about the result of n (see below).
> > >
> > > > Okay, We have two values in question:
> > > >  r_o (original rate of the parent clock)
> > > >  r_u (the rate user asked for)
> > > >
> > > > We have a pre-scaler block which asks for
> > > >  m (denominator)
> > > >  n (nominator)
> > > > values to be provided to satisfy the (2)
> > > >
> > > >     r_u ~= r_o * m / n, (2)
> > > >
> > > > where we try our best to make it "=" instead of "~=".
> > > >
> > > > Now, m and n have the limitation by a range, e.g.
> > > >
> > > >     n >= 1, n < N_lim, where N_lim = 2^nlim. (3)
> > > >
> > > > Hence, from (2) and (3), assuming the worst case m = 1,
> > > >
> > > >     ln2(r_o / r_u) <= nlim. (4)
> > > >
> > > > The above code tries to satisfy (4).
> > > >
> > > > Have you got it now?
> >
> > I'm afraid I haven't, sorry. Jacky, what about you?
>
> You may take a pen and paper and model different cases. After all it's
> not rocket science, just arithmetics :-)
>
> > Is that snippet really needed?
>
> Yes. The (4)  shows why.

Now I realize one more item which is missed in the big picture.
When we have overflowed the denominator (n) and shifted the values, we
are expecting that the caller will check the rate and use another
2^scale (see (6) below) prescaler if needed to drop frequency to the
needed values. The first few users of this were the drivers of the IPs
which have an additional prescaler themselves. I dunno if there is any
flag in CCF to show that the set frequency is 2^scale higher than
asked.

It means if

        r_o / r_u >> N_lim (5)

we will get m and n *saturated* without this snipped, while with it
they will be much much better with a nuance that resulting frequency
is shifted left by

        scale = ln2(r_o/r_u) - nlim (6)

scale bits.

> > Without that snippet, it seems that rational_best_approximation() is
> > able to offer best_numerator and best_denominator without the risk of
> > overflow for m and n, since max_numerator and max_denominator are
> > already handed over to rational_best_approximation()?
>
> No.
>
> > Does rational_best_approximation() always offer best_numerator by the
> > range of [1, max_numerator] and best_denominator [1, max_denominator]?
>
> Of course not, when it goes out of the range.

> > > > > > The code looks good to me, btw, although I dunno if you need to call the newly
> > > > > > introduced function before or after the above mentioned snippet.
> > > > >
> > > > > Assuming that snippet is fully orthogonal to this patch, then it
> > > > > doesn't matter if it's before or after.
> > > >
> > > > Please, double check this. Because you play with limits, while we expect them
> > > > to satisfy (3).

-- 
With Best Regards,
Andy Shevchenko