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: <0ae047e216298e6239e39ec40a2d545ac07a7406.camel@nxp.com>
Date:   Thu, 15 Jul 2021 13:26:48 +0800
From:   Liu Ying <victor.liu@....com>
To:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
Cc:     linux-clk@...r.kernel.org, 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 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?

Is that snippet really needed?

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()?

Does rational_best_approximation() always offer best_numerator by the
range of [1, max_numerator] and best_denominator [1, max_denominator]?

Regards,
Liu Ying

> > 
> > > > 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
> > 
> >