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

["Sören Brinkmann" <soren.brinkmann@xilinx.com>]

Hi Uwe,

On Mon, 2014-05-19 at 09:41AM -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@xilinx.com>
> > > 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@pengutronix.de>
> > > Signed-off-by: Soren Brinkmann <soren.brinkmann@xilinx.com>
> > > ---
> > >  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.
> 
> > 
> > > +{
> > > +	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.
> 
> > 
> > > +
> > > +	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?
> 
> > 
> > > +		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.
> 
> > 
> > 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?

With the improvements suggested by you I have this now:

long clk_round_rate_nearest(struct clk *clk, unsigned long rate)
{
	unsigned long lower, upper;

	lower = clk_round_rate(clk, rate);
	if (lower >= rate)
		return lower;

	upper = clk_round_rate(clk, rate + (rate - lower) - 1);
	if (upper == lower)
		return upper;

	lower = rate + 1;
	while (lower < upper) {
		unsigned long rounded, mid;

		mid = lower + ((upper - lower) >> 1);
		rounded = clk_round_rate(clk, mid);
		if (rounded < lower)
			lower = mid + 1;
		else
			upper = rounded;
	}

	return upper;
}

	Sören