From mboxrd@z Thu Jan 1 00:00:00 1970 From: Uwe =?iso-8859-1?Q?Kleine-K=F6nig?= Subject: Re: [RFC PATCH 2/5] clk: Introduce 'clk_round_rate_nearest()' Date: Tue, 20 May 2014 09:33:58 +0200 Message-ID: <20140520073358.GJ16662@pengutronix.de> References: <1400106655-22465-1-git-send-email-soren.brinkmann@xilinx.com> <1400106655-22465-3-git-send-email-soren.brinkmann@xilinx.com> <20140515073816.GI16662@pengutronix.de> <91822600-39d0-4e71-b0f5-9eda35b76ec0@BN1AFFO11FD016.protection.gbl> <20140519161949.GG16662@pengutronix.de> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE Return-path: Received: from metis.ext.pengutronix.de ([92.198.50.35]:53372 "EHLO metis.ext.pengutronix.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751503AbaETHeL (ORCPT ); Tue, 20 May 2014 03:34:11 -0400 Content-Disposition: inline In-Reply-To: Sender: linux-pm-owner@vger.kernel.org List-Id: linux-pm@vger.kernel.org To: =?iso-8859-1?Q?S=F6ren?= Brinkmann Cc: Mike Turquette , "Rafael J. Wysocki" , Viresh Kumar , Russell King , Michal Simek , linux-pm@vger.kernel.org, linux-kernel@vger.kernel.org, cpufreq@vger.kernel.org, linux-arm-kernel@lists.infradead.org Hi S=F6ren, On Mon, May 19, 2014 at 09:41:32AM -0700, S=F6ren Brinkmann wrote: > On Mon, 2014-05-19 at 06:19PM +0200, Uwe Kleine-K=F6nig wrote: > > Hi S=F6ren, > >=20 > > On Sun, May 18, 2014 at 05:51:05PM -0700, S=F6ren Brinkmann wrote: > > > ------------------8<-----------------8<---------------------8<---= ----------8<--- > > > From: Soren Brinkmann > > > Date: Tue, 2 Apr 2013 10:08:13 -0700 > > > Subject: [PATCH] clk: Introduce 'clk_round_rate_nearest()' > > >=20 > > > Introduce a new API function to round a rate to the closest possi= ble > > > rate the HW clock can generate. > > > In contrast to 'clk_round_rate()' which works similar, but always= returns > > > a frequency <=3D its input rate. > > >=20 > > > Cc: Uwe Kleine-K=F6nig > > > Signed-off-by: Soren Brinkmann > > > --- > > > drivers/clk/clk.c | 43 +++++++++++++++++++++++++++++++++++++++= ++-- > > > include/linux/clk.h | 14 ++++++++++++-- > > > 2 files changed, 53 insertions(+), 4 deletions(-) > > >=20 > > > diff --git a/drivers/clk/clk.c b/drivers/clk/clk.c > > > index dff0373f53c1..faf24d0569df 100644 > > > --- a/drivers/clk/clk.c > > > +++ b/drivers/clk/clk.c > > > @@ -1011,8 +1011,9 @@ unsigned long __clk_round_rate(struct clk *= clk, unsigned long rate) > > > * @rate: the rate which is to be rounded > > > * > > > * Takes in a rate as input and rounds it to a rate that the clk= can actually > > > - * use which is then returned. If clk doesn't support round_rat= e operation > > > - * then the parent rate is returned. > > > + * use and does not exceed the requested frequency, which is the= n returned. > > > + * If clk doesn't support round_rate operation then the parent r= ate > > > + * is returned. > > > */ > > > long clk_round_rate(struct clk *clk, unsigned long rate) > > > { > > > @@ -1027,6 +1028,44 @@ long clk_round_rate(struct clk *clk, unsig= ned long rate) > > > EXPORT_SYMBOL_GPL(clk_round_rate); > > > =20 > > > /** > > > + * clk_round_rate_nearest - round the given rate for a clk > > > + * @clk: the clk for which we are rounding a rate > > > + * @rate: the rate which is to be rounded > > > + * > > > + * Takes in a rate as input and rounds it to the closest rate th= at the clk > > > + * can actually use which is then returned. If clk doesn't suppo= rt > > > + * round_rate operation then the parent rate is returned. > > > + */ > > > +long clk_round_rate_nearest(struct clk *clk, unsigned long rate) > > Why does this function doesn't return an unsigned long when it neve= r > > returns a negative value? Ditto for clk_round_rate? >=20 > I matched the definition of clk_round_rate(). But you're probably rig= ht, > it may be the right thing to change clk_round_rate to return an > unsigned, but with that being exposed API it would be a risky change. Russell, what do you think? > > > +{ > > > + unsigned long lower, upper, cur, lower_last, upper_last; > > > + > > > + lower =3D clk_round_rate(clk, rate); > > > + if (lower >=3D rate) > > > + return lower; > > Is the >-case worth a warning? >=20 > No, it's correct behavior. If you request a rate that is way lower th= an what the > clock can generate, returning something larger is perfectly valid, IM= HO. > Which reveals one problem in this whole discussion. The API does not > require clk_round_rate() to round down. It is actually an implementat= ion > choice that had been made for clk-divider. I'm sure it's more than an implementation choice for clk-divider. But I don't find any respective documentation (but I didn't try hard). > > > + > > > + upper =3D clk_round_rate(clk, rate + rate - lower); > > This was parenthesized in my original patch on purpose. If rate is = big > >=20 > > rate + rate - lower > >=20 > > might overflow when > >=20 > > rate + (rate - lower) > >=20 > > doesn't. Thinking again, there is no real problem, because this is > > unsigned arithmetic. To be save we still need to check if rate + (r= ate - > > lower) overflows. >=20 > Good point. I'll add the parentheses. >=20 > >=20 > > > + if (upper =3D=3D lower) > > if (upper <=3D rate) is the better check here. (=3D would be a bug.= ) >=20 > I don't understand. Passing rate + x to round rate can never return > something below 'lower'. Only something in the range [lower,lower+x]. > So, if upper =3D=3D lower we found our closest frequency and return i= t. > Otherwise we have to iterate over [lower+1,upper]. Or what did I miss= ? Assuming a correct implementation of clk_round_rate there is no difference. Checking for <=3D rate is just a bit more robust for broken implementations. > > > + return upper; > > > + > > > + lower =3D rate + 1; > > ok, so your loop invariant is that the best freq is in [lower; uppe= r]. >=20 > right. >=20 > >=20 > > > + do { > > > + upper_last =3D upper; > > > + lower_last =3D lower; > > > + > > > + cur =3D clk_round_rate(clk, lower + ((upper - lower) >> 1)); > > > + if (cur < lower) > > > + lower +=3D (upper - lower) >> 1; > > You already know that lower + ((upper - lower) >> 1) is too small, = so > > you can better do > >=20 > > lower +=3D ((upper - lower) >> 1) + 1; >=20 > right. I'll add the '+1' >=20 > >=20 > > > + else > > > + upper =3D cur; > > > + > > > + } while (lower_last !=3D lower && upper_last !=3D upper); > > > + > > > + return upper; > > > +} > > > +EXPORT_SYMBOL_GPL(clk_round_rate_nearest); > > I think the function still has potential for optimisation, what abo= ut: >=20 > At first glance, I don't see many differences except for the comments > you made above. I'll have a closer look though. I would expect my variant to result in more effective code as it has simpler expressions. > > unsigned long clk_round_rate_nearest(struct clk *clk, unsigned long= rate) > > { > > unsigned long lower, upper, rounded; > >=20 > > rounded =3D clk_round_rate(clk, rate); > >=20 > > if (rounded >=3D rate) > > return rounded; > >=20 > > /* > > * rounded is the best approximation for rate that is not > > * bigger than rate. If there is a better one, it must be in the > > * interval (rate; rate + (rate - rounded)). > > * Note that the upper limit isn't better than rate itself, so > > * that one doesn't need to be considered. > > */ > > =20 > > upper =3D rate + (rate - rounded) - 1; > > if (upper < rate) > > upper =3D ULONG_MAX;=20 >=20 > Aren't we done here? Your search for an upper boundary resulted in > 'lower'. Hence there is no valid frequency closer to 'rate' than 'low= er'. Why do > you extend to ULONG_MAX? Consider a clock that can do (assuming ULONG_MAX =3D 4294967295): 12000, 4294967285 and you call clk_round_rate_nearest(clk, 4294967283) Then we have: rounded =3D clk_round_rate(clk, 4294967283) =3D 12000. upper =3D 4294955269 because the addition overflowed upper is smaller than rate. Still we want to find rate=3D4294967285, right? Best regards Uwe --=20 Pengutronix e.K. | Uwe Kleine-K=F6nig = | Industrial Linux Solutions | http://www.pengutronix.de/= |