Re: [RFC PATCH 2/5] clk: Introduce 'clk_round_rate_nearest()'

[SÃren Brinkmann]

Hi Uwe,

On Tue, 2014-05-20 at 09:33AM +0200, Uwe Kleine-KÃnig wrote:
> Hi SÃren,
> 
> On Mon, May 19, 2014 at 09:41:32AM -0700, SÃren Brinkmann wrote:
> > On Mon, 2014-05-19 at 06:19PM +0200, Uwe Kleine-KÃnig wrote:
> > > Hi SÃren,
> > > 
> > > On Sun, May 18, 2014 at 05:51:05PM -0700, SÃren Brinkmann wrote:
> > > > ------------------8<-----------------8<---------------------8<-------------8<---
> > > > From: Soren Brinkmann <soren.brinkmann@xxxxxxxxxx>
> > > > Date: Tue, 2 Apr 2013 10:08:13 -0700
> > > > Subject: [PATCH] clk: Introduce 'clk_round_rate_nearest()'
> > > > 
> > > > Introduce a new API function to round a rate to the closest possible
> > > > rate the HW clock can generate.
> > > > In contrast to 'clk_round_rate()' which works similar, but always returns
> > > > a frequency <= its input rate.
> > > > 
> > > > Cc: Uwe Kleine-KÃnig <u.kleine-koenig@xxxxxxxxxxxxxx>
> > > > Signed-off-by: Soren Brinkmann <soren.brinkmann@xxxxxxxxxx>
> > > > ---
> > > >  drivers/clk/clk.c   | 43 +++++++++++++++++++++++++++++++++++++++++--
> > > >  include/linux/clk.h | 14 ++++++++++++--
> > > >  2 files changed, 53 insertions(+), 4 deletions(-)
> > > > 
> > > > 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_rate operation
> > > > - * then the parent rate is returned.
> > > > + * use and does not exceed the requested frequency, which is then returned.
> > > > + * If clk doesn't support round_rate operation then the parent rate
> > > > + * is returned.
> > > >   */
> > > >  long clk_round_rate(struct clk *clk, unsigned long rate)
> > > >  {
> > > > @@ -1027,6 +1028,44 @@ long clk_round_rate(struct clk *clk, unsigned long rate)
> > > >  EXPORT_SYMBOL_GPL(clk_round_rate);
> > > >  
> > > >  /**
> > > > + * 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 that the clk
> > > > + * can actually use which is then returned. If clk doesn't support
> > > > + * 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 never
> > > returns a negative value? Ditto for clk_round_rate?
> > 
> > I matched the definition of clk_round_rate(). But you're probably right,
> > 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 = clk_round_rate(clk, rate);
> > > > +	if (lower >= rate)
> > > > +		return lower;
> > > Is the >-case worth a warning?
> > 
> > No, it's correct behavior. If you request a rate that is way lower than what the
> > clock can generate, returning something larger is perfectly valid, IMHO.
> > Which reveals one problem in this whole discussion. The API does not
> > require clk_round_rate() to round down. It is actually an implementation
> > 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).

A similar discussion - without final conclusion:
https://lkml.org/lkml/2010/7/14/260

> 
> 
> > > > +
> > > > +	upper = clk_round_rate(clk, rate + rate - lower);
> > > This was parenthesized in my original patch on purpose. If rate is big
> > > 
> > > 	rate + rate - lower
> > > 
> > > might overflow when
> > > 
> > > 	rate + (rate - lower)
> > > 
> > > doesn't. Thinking again, there is no real problem, because this is
> > > unsigned arithmetic. To be save we still need to check if rate + (rate -
> > > lower) overflows.
> > 
> > Good point. I'll add the parentheses.
> > 
> > > 
> > > > +	if (upper == lower)
> > > if (upper <= rate) is the better check here. (= would be a bug.)
> > 
> > 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 == lower we found our closest frequency and return it.
> > 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 <= rate is just a bit more robust for broken
> implementations.
> 
> > > > +		return upper;
> > > > +
> > > > +	lower = rate + 1;
> > > ok, so your loop invariant is that the best freq is in [lower; upper].
> > 
> > right.
> > 
> > > 
> > > > +	do {
> > > > +		upper_last = upper;
> > > > +		lower_last = lower;
> > > > +
> > > > +		cur = clk_round_rate(clk, lower + ((upper - lower) >> 1));
> > > > +		if (cur < lower)
> > > > +			lower += (upper - lower) >> 1;
> > > You already know that lower + ((upper - lower) >> 1) is too small, so
> > > you can better do
> > > 
> > > 	lower += ((upper - lower) >> 1) + 1;
> > 
> > right. I'll add the '+1'
> > 
> > > 
> > > > +		else
> > > > +			upper = cur;
> > > > +
> > > > +	} while (lower_last != lower && upper_last != upper);
> > > > +
> > > > +	return upper;
> > > > +}
> > > > +EXPORT_SYMBOL_GPL(clk_round_rate_nearest);
> > > I think the function still has potential for optimisation, what about:
> > 
> > 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;
> > > 
> > > 	rounded = clk_round_rate(clk, rate);
> > > 
> > > 	if (rounded >= rate)
> > > 		return rounded;
> > > 
> > > 	/*
> > > 	 * 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.
> > > 	 */
> > > 	 
> > > 	upper = rate + (rate - rounded) - 1;
> > > 	if (upper < rate)
> > > 		upper = ULONG_MAX; 
> > 
> > Aren't we done here? Your search for an upper boundary resulted in
> > 'lower'. Hence there is no valid frequency closer to 'rate' than 'lower'. Why do
> > you extend to ULONG_MAX?
> Consider a clock that can do (assuming ULONG_MAX = 4294967295):
> 
> 	12000, 4294967285
> 
> and you call
> 
> 	clk_round_rate_nearest(clk, 4294967283)
> 
> Then we have:
> 
> 	rounded = clk_round_rate(clk, 4294967283) = 12000.
> 	upper = 4294955269
> 
> because the addition overflowed upper is smaller than rate. Still we
> want to find rate=4294967285, right?

Ah, now I see the problem. Thanks. Due to the return type being long, I
kinda assumed that we operate far away from an overflow and should be
pretty much safe. Taking an overflow into account complicates things a
bit. I give this another look.

 	SÃren

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/