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

Hi,

I spent some time finding an alternative implementation for
clk_round_rate_nearest, the result can be found below.
I hope this is closer to a working implementation.

	Thanks,
	Sören


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

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?

> +{
> +	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?

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

> +	if (upper == lower)
if (upper <= rate) is the better check here. (= would be a bug.)

> +		return upper;
> +
> +	lower = rate + 1;
ok, so your loop invariant is that the best freq is in [lower; upper].

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

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

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; 

	upper = clk_round_rate(clk, upper);

	lower = rate + 1;

	/*
	 * If there is a better approximation than clk_round_rate(clk,
	 * rate), it is in the interval [lower, upper]. Otherwise all
	 * values in this interval yield clk_round_rate(clk, rate).
	 */
	while (lower < upper) {
		unsigned long mid;

		mid = lower + (upper - lower) >> 1;
		rounded = clk_round_rate(clk, mid);

		if (rounded < rate) {
			/* implies rounded == clk_round_rate(clk, rate); */
			lower = mid + 1;
		} else {
			/*
			 * rounded is a better approximation than lower
			 * assuming that rounded <= mid
			 */
			upper = rounded;
		}
	}

	/*
	 * upper is always assigned a return value from clk_round_rate,
	 * so it's suitable for direct return.
	 */
	return upper;
}

? Note this is not even compile tested ...

	
> +
> +/**
>   * __clk_notify - call clk notifier chain
>   * @clk: struct clk * that is changing rate
>   * @msg: clk notifier type (see include/linux/clk.h)
> diff --git a/include/linux/clk.h b/include/linux/clk.h
> index fb5e097d8f72..2f83bf030ac6 100644
> --- a/include/linux/clk.h
> +++ b/include/linux/clk.h
> @@ -255,15 +255,25 @@ void devm_clk_put(struct device *dev, struct clk *clk);
>  
>  
>  /**
> - * clk_round_rate - adjust a rate to the exact rate a clock can provide
> + * clk_round_rate - round a rate to the exact rate a clock can provide not
> + *		    exceeding @rate
>   * @clk: clock source
>   * @rate: desired clock rate in Hz
>   *
> - * Returns rounded clock rate in Hz, or negative errno.
> + * Returns rounded clock rate in Hz, or parent rate
>   */
I'd put the changes in this hunk up to here into a separate patch.

Best regards
Uwe

>  long clk_round_rate(struct clk *clk, unsigned long rate);
>  
>  /**
> + * clk_round_rate_nearest - round a rate to the exact rate a clock can provide
> + * @clk: the clk for which we are rounding a rate
> + * @rate: the rate which is to be rounded
> + *
> + * Returns rounded clock rate in Hz, or parent rate
> + */
> +long clk_round_rate_nearest(struct clk *clk, unsigned long rate);
> +
> +/**
>   * clk_set_rate - set the clock rate for a clock source
>   * @clk: clock source
>   * @rate: desired clock rate in Hz
> -- 
> 1.9.3.1.ga73a6ad
> 
> 
>

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?

	Thanks,
	Sören

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

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@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.
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).


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

Best regards
Uwe

Hello,

On Mon, May 19, 2014 at 10:29:05AM -0700, Sören Brinkmann wrote:
> 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;
> }
This is nearly my version now. I just lacks the overflow check when
calculating upper and I skipped the early return if (upper == lower).
(Instead the while condition evaluates to false on the first hit and
returns with the same result.)

Other than that I added a few comments. :-)

Something we still should resolve is the return type. It should match
clk_round_rate, but should both be signed or unsigned? 

Uwe

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

On 05/20/14 09:01, Sören Brinkmann wrote:
>
>>>>> +{
>>>>> +	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
>
>

Please call this new API something like clk_find_nearest_rate() or
something. clk_round_rate() is supposed to return the rate that will be
set if you call clk_set_rate() with the same arguments. It's up to the
implementation to decide if that means rounding the rate up or down or
to the nearest value.

On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> On 05/20/14 09:01, Sören Brinkmann wrote:
> >
> >>>>> +{
> >>>>> +	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
> >
> >
> 
> Please call this new API something like clk_find_nearest_rate() or
> something. clk_round_rate() is supposed to return the rate that will be
> set if you call clk_set_rate() with the same arguments. It's up to the
> implementation to decide if that means rounding the rate up or down or
> to the nearest value.

Sounds good to me. Are there any cases of clocks that round up? I think
that case would not be handled correctly. But I also don't see a use
case for such an implementation.

	Sören

Hello,

On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > On 05/20/14 09:01, Sören Brinkmann wrote:
> > >
> > >>>>> +{
> > >>>>> +	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
> > >
> > >
> > 
> > Please call this new API something like clk_find_nearest_rate() or
> > something. clk_round_rate() is supposed to return the rate that will be
> > set if you call clk_set_rate() with the same arguments. It's up to the
> > implementation to decide if that means rounding the rate up or down or
> > to the nearest value.
> 
> Sounds good to me. Are there any cases of clocks that round up? I think
> that case would not be handled correctly. But I also don't see a use
> case for such an implementation.
I don't really care which semantic (i.e. round up, round down or round
closest) is picked, but I'd vote that all should pick up the same. I
think the least surprising definition is to choose rounding down and add
the function that is under discussion here to get a nearest match.

So I suggest:

	- if round_rate is given a rate that is smaller than the
	  smallest available rate, return 0
	- add WARN_ONCE to round_rate and set_rate if they return with a
	  rate bigger than requested
	- change the return values to unsigned long

Do we also need a round_up implementation?

Mike? Russell? Any thoughts from your side?

Best regards
Uwe

On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> Hello,
> 
> On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > >
> > > >>>>> +{
> > > >>>>> +	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
> > > >
> > > >
> > > 
> > > Please call this new API something like clk_find_nearest_rate() or
> > > something. clk_round_rate() is supposed to return the rate that will be
> > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > implementation to decide if that means rounding the rate up or down or
> > > to the nearest value.
> > 
> > Sounds good to me. Are there any cases of clocks that round up? I think
> > that case would not be handled correctly. But I also don't see a use
> > case for such an implementation.
> I don't really care which semantic (i.e. round up, round down or round
> closest) is picked, but I'd vote that all should pick up the same. I
> think the least surprising definition is to choose rounding down and add
> the function that is under discussion here to get a nearest match.
> 
> So I suggest:
> 
> 	- if round_rate is given a rate that is smaller than the
> 	  smallest available rate, return 0
> 	- add WARN_ONCE to round_rate and set_rate if they return with a
> 	  rate bigger than requested

Why do you think 0 is always valid? I think for a clock that can
generate 40, 70, 120, clk_round_rate(20) should return 40.

> 	- change the return values to unsigned long

Yep, I agree, this should happen.

	Sören

Hello Sören,

On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > >
> > > > >>>>> +{
> > > > >>>>> +	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
> > > > >
> > > > >
> > > > 
> > > > Please call this new API something like clk_find_nearest_rate() or
> > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > implementation to decide if that means rounding the rate up or down or
> > > > to the nearest value.
> > > 
> > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > that case would not be handled correctly. But I also don't see a use
> > > case for such an implementation.
> > I don't really care which semantic (i.e. round up, round down or round
> > closest) is picked, but I'd vote that all should pick up the same. I
> > think the least surprising definition is to choose rounding down and add
> > the function that is under discussion here to get a nearest match.
> > 
> > So I suggest:
> > 
> > 	- if round_rate is given a rate that is smaller than the
> > 	  smallest available rate, return 0
> > 	- add WARN_ONCE to round_rate and set_rate if they return with a
> > 	  rate bigger than requested
> 
> Why do you think 0 is always valid? I think for a clock that can
> generate 40, 70, 120, clk_round_rate(20) should return 40.
I didn't say it's a valid value. It just makes the it possible to check
for clk_round_rate(clk, rate) <= rate.

I grepped a bit around and found da850_round_armrate which implements a
round_rate callback returning the best match.
omap1_clk_round_rate_ckctl_arm can return a value < 0.
s3c2412_roundrate_usbsrc can return values that are bigger than
requested. (I wonder if that is a bug though.)

> > 	- change the return values to unsigned long
> 
> Yep, I agree, this should happen.
And we're using 0 as error value? e.g. for the case where
omap1_clk_round_rate_ckctl_arm returns -EIO now?

Best regards
Uwe

On Wed, 2014-05-21 at 08:23PM +0200, Uwe Kleine-König wrote:
> Hello Sören,
> 
> On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > >
> > > > > >>>>> +{
> > > > > >>>>> +	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
> > > > > >
> > > > > >
> > > > > 
> > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > implementation to decide if that means rounding the rate up or down or
> > > > > to the nearest value.
> > > > 
> > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > that case would not be handled correctly. But I also don't see a use
> > > > case for such an implementation.
> > > I don't really care which semantic (i.e. round up, round down or round
> > > closest) is picked, but I'd vote that all should pick up the same. I
> > > think the least surprising definition is to choose rounding down and add
> > > the function that is under discussion here to get a nearest match.
> > > 
> > > So I suggest:
> > > 
> > > 	- if round_rate is given a rate that is smaller than the
> > > 	  smallest available rate, return 0
> > > 	- add WARN_ONCE to round_rate and set_rate if they return with a
> > > 	  rate bigger than requested
> > 
> > Why do you think 0 is always valid? I think for a clock that can
> > generate 40, 70, 120, clk_round_rate(20) should return 40.
> I didn't say it's a valid value. It just makes the it possible to check
> for clk_round_rate(clk, rate) <= rate.

But if the set_rate() doesn't set the rate to 0 in that case, the
implementation was buggy.

> 
> I grepped a bit around and found da850_round_armrate which implements a
> round_rate callback returning the best match.
> omap1_clk_round_rate_ckctl_arm can return a value < 0.
> s3c2412_roundrate_usbsrc can return values that are bigger than
> requested. (I wonder if that is a bug though.)
> 
> > > 	- change the return values to unsigned long
> > 
> > Yep, I agree, this should happen.
> And we're using 0 as error value? e.g. for the case where
> omap1_clk_round_rate_ckctl_arm returns -EIO now?

IMHO, there should always be a valid frequency be returned from these
calls. The API says: return the frequency the clock provides when
set_rate() is called with the same argument. This should never result in
an error.

	Sören

Quoting Uwe Kleine-König (2014-05-21 11:23:08)
> Hello Sören,
> 
> On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > >
> > > > > >>>>> +{
> > > > > >>>>> + 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
> > > > > >
> > > > > >
> > > > > 
> > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > implementation to decide if that means rounding the rate up or down or
> > > > > to the nearest value.
> > > > 
> > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > that case would not be handled correctly. But I also don't see a use
> > > > case for such an implementation.
> > > I don't really care which semantic (i.e. round up, round down or round
> > > closest) is picked, but I'd vote that all should pick up the same. I
> > > think the least surprising definition is to choose rounding down and add
> > > the function that is under discussion here to get a nearest match.
> > > 
> > > So I suggest:
> > > 
> > >     - if round_rate is given a rate that is smaller than the
> > >       smallest available rate, return 0
> > >     - add WARN_ONCE to round_rate and set_rate if they return with a
> > >       rate bigger than requested
> > 
> > Why do you think 0 is always valid? I think for a clock that can
> > generate 40, 70, 120, clk_round_rate(20) should return 40.
> I didn't say it's a valid value. It just makes the it possible to check
> for clk_round_rate(clk, rate) <= rate.
> 
> I grepped a bit around and found da850_round_armrate which implements a
> round_rate callback returning the best match.
> omap1_clk_round_rate_ckctl_arm can return a value < 0.
> s3c2412_roundrate_usbsrc can return values that are bigger than
> requested. (I wonder if that is a bug though.)
> 
> > >     - change the return values to unsigned long
> > 
> > Yep, I agree, this should happen.
> And we're using 0 as error value? e.g. for the case where
> omap1_clk_round_rate_ckctl_arm returns -EIO now?

No. clk_round_rate returns long for a reason, which is that we can
provide an error code to the caller. From include/linux/clk.h:

/**
 * clk_round_rate - adjust a rate to the exact rate a clock can provide
 * @clk: clock source
 * @rate: desired clock rate in Hz
 *
 * Returns rounded clock rate in Hz, or negative errno.
 */

This has the unfortunate side effect that the max value we can return
safely is 2147483647 (~2GHz). So another issue here is converting clock
rates to 64-bit values.

Regards,
Mike

> 
> Best regards
> Uwe
> 
> -- 
> Pengutronix e.K.                           | Uwe Kleine-König            |
> Industrial Linux Solutions                 | http://www.pengutronix.de/  |

On Wed, 2014-05-21 at 01:33PM -0700, Mike Turquette wrote:
> Quoting Uwe Kleine-König (2014-05-21 11:23:08)
> > Hello Sören,
> > 
> > On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > > >
> > > > > > >>>>> +{
> > > > > > >>>>> + 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
> > > > > > >
> > > > > > >
> > > > > > 
> > > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > > implementation to decide if that means rounding the rate up or down or
> > > > > > to the nearest value.
> > > > > 
> > > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > > that case would not be handled correctly. But I also don't see a use
> > > > > case for such an implementation.
> > > > I don't really care which semantic (i.e. round up, round down or round
> > > > closest) is picked, but I'd vote that all should pick up the same. I
> > > > think the least surprising definition is to choose rounding down and add
> > > > the function that is under discussion here to get a nearest match.
> > > > 
> > > > So I suggest:
> > > > 
> > > >     - if round_rate is given a rate that is smaller than the
> > > >       smallest available rate, return 0
> > > >     - add WARN_ONCE to round_rate and set_rate if they return with a
> > > >       rate bigger than requested
> > > 
> > > Why do you think 0 is always valid? I think for a clock that can
> > > generate 40, 70, 120, clk_round_rate(20) should return 40.
> > I didn't say it's a valid value. It just makes the it possible to check
> > for clk_round_rate(clk, rate) <= rate.
> > 
> > I grepped a bit around and found da850_round_armrate which implements a
> > round_rate callback returning the best match.
> > omap1_clk_round_rate_ckctl_arm can return a value < 0.
> > s3c2412_roundrate_usbsrc can return values that are bigger than
> > requested. (I wonder if that is a bug though.)
> > 
> > > >     - change the return values to unsigned long
> > > 
> > > Yep, I agree, this should happen.
> > And we're using 0 as error value? e.g. for the case where
> > omap1_clk_round_rate_ckctl_arm returns -EIO now?
> 
> No. clk_round_rate returns long for a reason, which is that we can
> provide an error code to the caller. From include/linux/clk.h:
> 
> /**
>  * clk_round_rate - adjust a rate to the exact rate a clock can provide
>  * @clk: clock source
>  * @rate: desired clock rate in Hz
>  *
>  * Returns rounded clock rate in Hz, or negative errno.
>  */
> 
> This has the unfortunate side effect that the max value we can return
> safely is 2147483647 (~2GHz). So another issue here is converting clock
> rates to 64-bit values.

So, let's assume
 - a clock does either of these
   - round down
   - round nearest
   - round up (is there any such case? I don't see a use-case for this)
 - or return an error

I think my latest try handles such cases, with the limitation of
for a clock that rounds up, the up-rounded value is found instead of the
nearest.


static long clk_find_nearest_rate(struct clk *clk, unsigned long rate)
{
	long ret;
	unsigned long lower, upper;

	clk_prepare_lock();

	lower = __clk_round_rate(clk, rate);
	if (lower >= rate || (long)lower < 0) {
		ret = lower;
		goto unlock;
	}

	upper = rate + (rate - lower) - 1;
	if (upper > LONG_MAX)
		upper = LONG_MAX;

	upper = __clk_round_rate(clk, upper);
	if (upper <= lower || (long)upper < 0) {
		ret = lower;
		goto unlock;
	}

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

	ret = upper;

unlock:
	clk_prepare_unlock();

	return ret;
}

	Sören

Hello Sören,

On Thu, May 22, 2014 at 11:03:00AM -0700, Sören Brinkmann wrote:
> On Wed, 2014-05-21 at 01:33PM -0700, Mike Turquette wrote:
> > Quoting Uwe Kleine-König (2014-05-21 11:23:08)
> > > Hello Sören,
> > > 
> > > On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > > > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > > > >
> > > > > > > >>>>> +{
> > > > > > > >>>>> + 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
> > > > > > > >
> > > > > > > >
> > > > > > > 
> > > > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > > > implementation to decide if that means rounding the rate up or down or
> > > > > > > to the nearest value.
> > > > > > 
> > > > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > > > that case would not be handled correctly. But I also don't see a use
> > > > > > case for such an implementation.
> > > > > I don't really care which semantic (i.e. round up, round down or round
> > > > > closest) is picked, but I'd vote that all should pick up the same. I
> > > > > think the least surprising definition is to choose rounding down and add
> > > > > the function that is under discussion here to get a nearest match.
> > > > > 
> > > > > So I suggest:
> > > > > 
> > > > >     - if round_rate is given a rate that is smaller than the
> > > > >       smallest available rate, return 0
> > > > >     - add WARN_ONCE to round_rate and set_rate if they return with a
> > > > >       rate bigger than requested
> > > > 
> > > > Why do you think 0 is always valid? I think for a clock that can
> > > > generate 40, 70, 120, clk_round_rate(20) should return 40.
> > > I didn't say it's a valid value. It just makes the it possible to check
> > > for clk_round_rate(clk, rate) <= rate.
> > > 
> > > I grepped a bit around and found da850_round_armrate which implements a
> > > round_rate callback returning the best match.
> > > omap1_clk_round_rate_ckctl_arm can return a value < 0.
> > > s3c2412_roundrate_usbsrc can return values that are bigger than
> > > requested. (I wonder if that is a bug though.)
> > > 
> > > > >     - change the return values to unsigned long
> > > > 
> > > > Yep, I agree, this should happen.
> > > And we're using 0 as error value? e.g. for the case where
> > > omap1_clk_round_rate_ckctl_arm returns -EIO now?
> > 
> > No. clk_round_rate returns long for a reason, which is that we can
> > provide an error code to the caller. From include/linux/clk.h:
> > 
> > /**
> >  * clk_round_rate - adjust a rate to the exact rate a clock can provide
> >  * @clk: clock source
> >  * @rate: desired clock rate in Hz
> >  *
> >  * Returns rounded clock rate in Hz, or negative errno.
> >  */
> > 
> > This has the unfortunate side effect that the max value we can return
> > safely is 2147483647 (~2GHz). So another issue here is converting clock
> > rates to 64-bit values.
> 
> So, let's assume
>  - a clock does either of these
>    - round down
>    - round nearest
>    - round up (is there any such case? I don't see a use-case for this)
>  - or return an error
> 
> I think my latest try handles such cases, with the limitation of
> for a clock that rounds up, the up-rounded value is found instead of the
> nearest.
> 
> 
> static long clk_find_nearest_rate(struct clk *clk, unsigned long rate)
> {
> 	long ret;
> 	unsigned long lower, upper;
> 
> 	clk_prepare_lock();
> 
> 	lower = __clk_round_rate(clk, rate);
this is CCF specific while I don't see a need for it. (But yes, a
lock-less clk_find_nearest_rate is of course racy.)

> 	if (lower >= rate || (long)lower < 0) {
If you made lower and upper a signed long, you could drop the casting
here. BTW, why does __clk_round_rate return an unsigned long??
There seem to be several more type mismatches in that area.
Maybe we should add a waring if rate is > LONG_MAX?

(And ISTR that the C standard doesn't specify what the result of
(long)lower is given that lower is of type unsigned long and holding a
value > LONG_MAX.)

> 		ret = lower;
> 		goto unlock;
> 	}
> 
> 	upper = rate + (rate - lower) - 1;
> 	if (upper > LONG_MAX)
> 		upper = LONG_MAX;
> 
> 	upper = __clk_round_rate(clk, upper);
> 	if (upper <= lower || (long)upper < 0) {
> 		ret = lower;
> 		goto unlock;
> 	}
> 
> 	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;
> 	}
> 
> 	ret = upper;
> 
> unlock:
> 	clk_prepare_unlock();
> 
> 	return ret;
> }

On Thu, 2014-05-22 at 08:20PM +0200, Uwe Kleine-König wrote:
> Hello Sören,
> 
> On Thu, May 22, 2014 at 11:03:00AM -0700, Sören Brinkmann wrote:
> > On Wed, 2014-05-21 at 01:33PM -0700, Mike Turquette wrote:
> > > Quoting Uwe Kleine-König (2014-05-21 11:23:08)
> > > > Hello Sören,
> > > > 
> > > > On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > > > > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > > > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > > > > >
> > > > > > > > >>>>> +{
> > > > > > > > >>>>> + 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
> > > > > > > > >
> > > > > > > > >
> > > > > > > > 
> > > > > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > > > > implementation to decide if that means rounding the rate up or down or
> > > > > > > > to the nearest value.
> > > > > > > 
> > > > > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > > > > that case would not be handled correctly. But I also don't see a use
> > > > > > > case for such an implementation.
> > > > > > I don't really care which semantic (i.e. round up, round down or round
> > > > > > closest) is picked, but I'd vote that all should pick up the same. I
> > > > > > think the least surprising definition is to choose rounding down and add
> > > > > > the function that is under discussion here to get a nearest match.
> > > > > > 
> > > > > > So I suggest:
> > > > > > 
> > > > > >     - if round_rate is given a rate that is smaller than the
> > > > > >       smallest available rate, return 0
> > > > > >     - add WARN_ONCE to round_rate and set_rate if they return with a
> > > > > >       rate bigger than requested
> > > > > 
> > > > > Why do you think 0 is always valid? I think for a clock that can
> > > > > generate 40, 70, 120, clk_round_rate(20) should return 40.
> > > > I didn't say it's a valid value. It just makes the it possible to check
> > > > for clk_round_rate(clk, rate) <= rate.
> > > > 
> > > > I grepped a bit around and found da850_round_armrate which implements a
> > > > round_rate callback returning the best match.
> > > > omap1_clk_round_rate_ckctl_arm can return a value < 0.
> > > > s3c2412_roundrate_usbsrc can return values that are bigger than
> > > > requested. (I wonder if that is a bug though.)
> > > > 
> > > > > >     - change the return values to unsigned long
> > > > > 
> > > > > Yep, I agree, this should happen.
> > > > And we're using 0 as error value? e.g. for the case where
> > > > omap1_clk_round_rate_ckctl_arm returns -EIO now?
> > > 
> > > No. clk_round_rate returns long for a reason, which is that we can
> > > provide an error code to the caller. From include/linux/clk.h:
> > > 
> > > /**
> > >  * clk_round_rate - adjust a rate to the exact rate a clock can provide
> > >  * @clk: clock source
> > >  * @rate: desired clock rate in Hz
> > >  *
> > >  * Returns rounded clock rate in Hz, or negative errno.
> > >  */
> > > 
> > > This has the unfortunate side effect that the max value we can return
> > > safely is 2147483647 (~2GHz). So another issue here is converting clock
> > > rates to 64-bit values.
> > 
> > So, let's assume
> >  - a clock does either of these
> >    - round down
> >    - round nearest
> >    - round up (is there any such case? I don't see a use-case for this)
> >  - or return an error
> > 
> > I think my latest try handles such cases, with the limitation of
> > for a clock that rounds up, the up-rounded value is found instead of the
> > nearest.
> > 
> > 
> > static long clk_find_nearest_rate(struct clk *clk, unsigned long rate)
> > {
> > 	long ret;
> > 	unsigned long lower, upper;
> > 
> > 	clk_prepare_lock();
> > 
> > 	lower = __clk_round_rate(clk, rate);
> this is CCF specific while I don't see a need for it. (But yes, a
> lock-less clk_find_nearest_rate is of course racy.)
Do we have to support non-CCF implementations? Isn't switching to the
CCF encouraged?

> 
> > 	if (lower >= rate || (long)lower < 0) {
> If you made lower and upper a signed long, you could drop the casting
> here. BTW, why does __clk_round_rate return an unsigned long??
> There seem to be several more type mismatches in that area.
> Maybe we should add a waring if rate is > LONG_MAX?
> 
> (And ISTR that the C standard doesn't specify what the result of
> (long)lower is given that lower is of type unsigned long and holding a
> value > LONG_MAX.)
Looks like you're right. This probably needs some polishing to get types
sorted out.
Mike/Russel: As Uwe pointed out, shouldn't __clk_round_rate return a
long as well?

	Sören

Quoting Sören Brinkmann (2014-05-22 13:32:09)
> On Thu, 2014-05-22 at 08:20PM +0200, Uwe Kleine-König wrote:
> > Hello Sören,
> > 
> > On Thu, May 22, 2014 at 11:03:00AM -0700, Sören Brinkmann wrote:
> > > On Wed, 2014-05-21 at 01:33PM -0700, Mike Turquette wrote:
> > > > Quoting Uwe Kleine-König (2014-05-21 11:23:08)
> > > > > Hello Sören,
> > > > > 
> > > > > On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > > > > > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > > > > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > > > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > > > > > >
> > > > > > > > > >>>>> +{
> > > > > > > > > >>>>> + 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
> > > > > > > > > >
> > > > > > > > > >
> > > > > > > > > 
> > > > > > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > > > > > implementation to decide if that means rounding the rate up or down or
> > > > > > > > > to the nearest value.
> > > > > > > > 
> > > > > > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > > > > > that case would not be handled correctly. But I also don't see a use
> > > > > > > > case for such an implementation.
> > > > > > > I don't really care which semantic (i.e. round up, round down or round
> > > > > > > closest) is picked, but I'd vote that all should pick up the same. I
> > > > > > > think the least surprising definition is to choose rounding down and add
> > > > > > > the function that is under discussion here to get a nearest match.
> > > > > > > 
> > > > > > > So I suggest:
> > > > > > > 
> > > > > > >     - if round_rate is given a rate that is smaller than the
> > > > > > >       smallest available rate, return 0
> > > > > > >     - add WARN_ONCE to round_rate and set_rate if they return with a
> > > > > > >       rate bigger than requested
> > > > > > 
> > > > > > Why do you think 0 is always valid? I think for a clock that can
> > > > > > generate 40, 70, 120, clk_round_rate(20) should return 40.
> > > > > I didn't say it's a valid value. It just makes the it possible to check
> > > > > for clk_round_rate(clk, rate) <= rate.
> > > > > 
> > > > > I grepped a bit around and found da850_round_armrate which implements a
> > > > > round_rate callback returning the best match.
> > > > > omap1_clk_round_rate_ckctl_arm can return a value < 0.
> > > > > s3c2412_roundrate_usbsrc can return values that are bigger than
> > > > > requested. (I wonder if that is a bug though.)
> > > > > 
> > > > > > >     - change the return values to unsigned long
> > > > > > 
> > > > > > Yep, I agree, this should happen.
> > > > > And we're using 0 as error value? e.g. for the case where
> > > > > omap1_clk_round_rate_ckctl_arm returns -EIO now?
> > > > 
> > > > No. clk_round_rate returns long for a reason, which is that we can
> > > > provide an error code to the caller. From include/linux/clk.h:
> > > > 
> > > > /**
> > > >  * clk_round_rate - adjust a rate to the exact rate a clock can provide
> > > >  * @clk: clock source
> > > >  * @rate: desired clock rate in Hz
> > > >  *
> > > >  * Returns rounded clock rate in Hz, or negative errno.
> > > >  */
> > > > 
> > > > This has the unfortunate side effect that the max value we can return
> > > > safely is 2147483647 (~2GHz). So another issue here is converting clock
> > > > rates to 64-bit values.
> > > 
> > > So, let's assume
> > >  - a clock does either of these
> > >    - round down
> > >    - round nearest
> > >    - round up (is there any such case? I don't see a use-case for this)
> > >  - or return an error
> > > 
> > > I think my latest try handles such cases, with the limitation of
> > > for a clock that rounds up, the up-rounded value is found instead of the
> > > nearest.
> > > 
> > > 
> > > static long clk_find_nearest_rate(struct clk *clk, unsigned long rate)
> > > {
> > >     long ret;
> > >     unsigned long lower, upper;
> > > 
> > >     clk_prepare_lock();
> > > 
> > >     lower = __clk_round_rate(clk, rate);
> > this is CCF specific while I don't see a need for it. (But yes, a
> > lock-less clk_find_nearest_rate is of course racy.)
> Do we have to support non-CCF implementations? Isn't switching to the
> CCF encouraged?

No we don't. If you check out the ifdeffery in include/linux/clk.h
you'll see more function declarations for CONFIG_COMMON_CLK then for
!CONFIG_COMMON_CLK, so we're not breaking any ground here.

> 
> > 
> > >     if (lower >= rate || (long)lower < 0) {
> > If you made lower and upper a signed long, you could drop the casting
> > here. BTW, why does __clk_round_rate return an unsigned long??
> > There seem to be several more type mismatches in that area.
> > Maybe we should add a waring if rate is > LONG_MAX?
> > 
> > (And ISTR that the C standard doesn't specify what the result of
> > (long)lower is given that lower is of type unsigned long and holding a
> > value > LONG_MAX.)
> Looks like you're right. This probably needs some polishing to get types
> sorted out.
> Mike/Russel: As Uwe pointed out, shouldn't __clk_round_rate return a
> long as well?

Yeah. The strange thing is that .round_rate and .determine_rate both
return long. I think I was asleep at the wheel on this one.

I count about a dozen call sites that need to be fixed up for this
change to happen. As we approach 3.15-rc6 I'm a bit nervous about
introducing this change. How do you feel about dropping this change in
first thing after 3.16-rc1 and layering in your new clk_find_*_rate
stuff on top of it?

I'll take a stab at fixing up __clk_round_rate early next week.

Regards,
Mike

> 
>         Sören
>

On Thu, 2014-05-22 at 02:03PM -0700, Mike Turquette wrote:
> Quoting Sören Brinkmann (2014-05-22 13:32:09)
> > On Thu, 2014-05-22 at 08:20PM +0200, Uwe Kleine-König wrote:
> > > Hello Sören,
> > > 
> > > On Thu, May 22, 2014 at 11:03:00AM -0700, Sören Brinkmann wrote:
> > > > On Wed, 2014-05-21 at 01:33PM -0700, Mike Turquette wrote:
> > > > > Quoting Uwe Kleine-König (2014-05-21 11:23:08)
> > > > > > Hello Sören,
> > > > > > 
> > > > > > On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > > > > > > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > > > > > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > > > > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > > > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > > > > > > >
> > > > > > > > > > >>>>> +{
> > > > > > > > > > >>>>> + 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
> > > > > > > > > > >
> > > > > > > > > > >
> > > > > > > > > > 
> > > > > > > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > > > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > > > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > > > > > > implementation to decide if that means rounding the rate up or down or
> > > > > > > > > > to the nearest value.
> > > > > > > > > 
> > > > > > > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > > > > > > that case would not be handled correctly. But I also don't see a use
> > > > > > > > > case for such an implementation.
> > > > > > > > I don't really care which semantic (i.e. round up, round down or round
> > > > > > > > closest) is picked, but I'd vote that all should pick up the same. I
> > > > > > > > think the least surprising definition is to choose rounding down and add
> > > > > > > > the function that is under discussion here to get a nearest match.
> > > > > > > > 
> > > > > > > > So I suggest:
> > > > > > > > 
> > > > > > > >     - if round_rate is given a rate that is smaller than the
> > > > > > > >       smallest available rate, return 0
> > > > > > > >     - add WARN_ONCE to round_rate and set_rate if they return with a
> > > > > > > >       rate bigger than requested
> > > > > > > 
> > > > > > > Why do you think 0 is always valid? I think for a clock that can
> > > > > > > generate 40, 70, 120, clk_round_rate(20) should return 40.
> > > > > > I didn't say it's a valid value. It just makes the it possible to check
> > > > > > for clk_round_rate(clk, rate) <= rate.
> > > > > > 
> > > > > > I grepped a bit around and found da850_round_armrate which implements a
> > > > > > round_rate callback returning the best match.
> > > > > > omap1_clk_round_rate_ckctl_arm can return a value < 0.
> > > > > > s3c2412_roundrate_usbsrc can return values that are bigger than
> > > > > > requested. (I wonder if that is a bug though.)
> > > > > > 
> > > > > > > >     - change the return values to unsigned long
> > > > > > > 
> > > > > > > Yep, I agree, this should happen.
> > > > > > And we're using 0 as error value? e.g. for the case where
> > > > > > omap1_clk_round_rate_ckctl_arm returns -EIO now?
> > > > > 
> > > > > No. clk_round_rate returns long for a reason, which is that we can
> > > > > provide an error code to the caller. From include/linux/clk.h:
> > > > > 
> > > > > /**
> > > > >  * clk_round_rate - adjust a rate to the exact rate a clock can provide
> > > > >  * @clk: clock source
> > > > >  * @rate: desired clock rate in Hz
> > > > >  *
> > > > >  * Returns rounded clock rate in Hz, or negative errno.
> > > > >  */
> > > > > 
> > > > > This has the unfortunate side effect that the max value we can return
> > > > > safely is 2147483647 (~2GHz). So another issue here is converting clock
> > > > > rates to 64-bit values.
> > > > 
> > > > So, let's assume
> > > >  - a clock does either of these
> > > >    - round down
> > > >    - round nearest
> > > >    - round up (is there any such case? I don't see a use-case for this)
> > > >  - or return an error
> > > > 
> > > > I think my latest try handles such cases, with the limitation of
> > > > for a clock that rounds up, the up-rounded value is found instead of the
> > > > nearest.
> > > > 
> > > > 
> > > > static long clk_find_nearest_rate(struct clk *clk, unsigned long rate)
> > > > {
> > > >     long ret;
> > > >     unsigned long lower, upper;
> > > > 
> > > >     clk_prepare_lock();
> > > > 
> > > >     lower = __clk_round_rate(clk, rate);
> > > this is CCF specific while I don't see a need for it. (But yes, a
> > > lock-less clk_find_nearest_rate is of course racy.)
> > Do we have to support non-CCF implementations? Isn't switching to the
> > CCF encouraged?
> 
> No we don't. If you check out the ifdeffery in include/linux/clk.h
> you'll see more function declarations for CONFIG_COMMON_CLK then for
> !CONFIG_COMMON_CLK, so we're not breaking any ground here.
> 
> > 
> > > 
> > > >     if (lower >= rate || (long)lower < 0) {
> > > If you made lower and upper a signed long, you could drop the casting
> > > here. BTW, why does __clk_round_rate return an unsigned long??
> > > There seem to be several more type mismatches in that area.
> > > Maybe we should add a waring if rate is > LONG_MAX?
> > > 
> > > (And ISTR that the C standard doesn't specify what the result of
> > > (long)lower is given that lower is of type unsigned long and holding a
> > > value > LONG_MAX.)
> > Looks like you're right. This probably needs some polishing to get types
> > sorted out.
> > Mike/Russel: As Uwe pointed out, shouldn't __clk_round_rate return a
> > long as well?

Sorry, Russell, of course.

> 
> Yeah. The strange thing is that .round_rate and .determine_rate both
> return long. I think I was asleep at the wheel on this one.
> 
> I count about a dozen call sites that need to be fixed up for this
> change to happen. As we approach 3.15-rc6 I'm a bit nervous about
> introducing this change. How do you feel about dropping this change in
> first thing after 3.16-rc1 and layering in your new clk_find_*_rate
> stuff on top of it?
> 
> I'll take a stab at fixing up __clk_round_rate early next week.

Yeah, at some point this 'fix cpufreq stats'-series grew a little out of
control. Targeting the 3.16 cycle sounds reasonable. Then we could probably
also look at moving from (unsigned) long to some 64-bit type as well ;)

	Thanks,
	Sören

Quoting Sören Brinkmann (2014-05-22 16:44:53)
> On Thu, 2014-05-22 at 02:03PM -0700, Mike Turquette wrote:
> > Quoting Sören Brinkmann (2014-05-22 13:32:09)
> > > On Thu, 2014-05-22 at 08:20PM +0200, Uwe Kleine-König wrote:
> > > > Hello Sören,
> > > > 
> > > > On Thu, May 22, 2014 at 11:03:00AM -0700, Sören Brinkmann wrote:
> > > > > On Wed, 2014-05-21 at 01:33PM -0700, Mike Turquette wrote:
> > > > > > Quoting Uwe Kleine-König (2014-05-21 11:23:08)
> > > > > > > Hello Sören,
> > > > > > > 
> > > > > > > On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > > > > > > > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > > > > > > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > > > > > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > > > > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > > > > > > > >
> > > > > > > > > > > >>>>> +{
> > > > > > > > > > > >>>>> + 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
> > > > > > > > > > > >
> > > > > > > > > > > >
> > > > > > > > > > > 
> > > > > > > > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > > > > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > > > > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > > > > > > > implementation to decide if that means rounding the rate up or down or
> > > > > > > > > > > to the nearest value.
> > > > > > > > > > 
> > > > > > > > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > > > > > > > that case would not be handled correctly. But I also don't see a use
> > > > > > > > > > case for such an implementation.
> > > > > > > > > I don't really care which semantic (i.e. round up, round down or round
> > > > > > > > > closest) is picked, but I'd vote that all should pick up the same. I
> > > > > > > > > think the least surprising definition is to choose rounding down and add
> > > > > > > > > the function that is under discussion here to get a nearest match.
> > > > > > > > > 
> > > > > > > > > So I suggest:
> > > > > > > > > 
> > > > > > > > >     - if round_rate is given a rate that is smaller than the
> > > > > > > > >       smallest available rate, return 0
> > > > > > > > >     - add WARN_ONCE to round_rate and set_rate if they return with a
> > > > > > > > >       rate bigger than requested
> > > > > > > > 
> > > > > > > > Why do you think 0 is always valid? I think for a clock that can
> > > > > > > > generate 40, 70, 120, clk_round_rate(20) should return 40.
> > > > > > > I didn't say it's a valid value. It just makes the it possible to check
> > > > > > > for clk_round_rate(clk, rate) <= rate.
> > > > > > > 
> > > > > > > I grepped a bit around and found da850_round_armrate which implements a
> > > > > > > round_rate callback returning the best match.
> > > > > > > omap1_clk_round_rate_ckctl_arm can return a value < 0.
> > > > > > > s3c2412_roundrate_usbsrc can return values that are bigger than
> > > > > > > requested. (I wonder if that is a bug though.)
> > > > > > > 
> > > > > > > > >     - change the return values to unsigned long
> > > > > > > > 
> > > > > > > > Yep, I agree, this should happen.
> > > > > > > And we're using 0 as error value? e.g. for the case where
> > > > > > > omap1_clk_round_rate_ckctl_arm returns -EIO now?
> > > > > > 
> > > > > > No. clk_round_rate returns long for a reason, which is that we can
> > > > > > provide an error code to the caller. From include/linux/clk.h:
> > > > > > 
> > > > > > /**
> > > > > >  * clk_round_rate - adjust a rate to the exact rate a clock can provide
> > > > > >  * @clk: clock source
> > > > > >  * @rate: desired clock rate in Hz
> > > > > >  *
> > > > > >  * Returns rounded clock rate in Hz, or negative errno.
> > > > > >  */
> > > > > > 
> > > > > > This has the unfortunate side effect that the max value we can return
> > > > > > safely is 2147483647 (~2GHz). So another issue here is converting clock
> > > > > > rates to 64-bit values.
> > > > > 
> > > > > So, let's assume
> > > > >  - a clock does either of these
> > > > >    - round down
> > > > >    - round nearest
> > > > >    - round up (is there any such case? I don't see a use-case for this)
> > > > >  - or return an error
> > > > > 
> > > > > I think my latest try handles such cases, with the limitation of
> > > > > for a clock that rounds up, the up-rounded value is found instead of the
> > > > > nearest.
> > > > > 
> > > > > 
> > > > > static long clk_find_nearest_rate(struct clk *clk, unsigned long rate)
> > > > > {
> > > > >     long ret;
> > > > >     unsigned long lower, upper;
> > > > > 
> > > > >     clk_prepare_lock();
> > > > > 
> > > > >     lower = __clk_round_rate(clk, rate);
> > > > this is CCF specific while I don't see a need for it. (But yes, a
> > > > lock-less clk_find_nearest_rate is of course racy.)
> > > Do we have to support non-CCF implementations? Isn't switching to the
> > > CCF encouraged?
> > 
> > No we don't. If you check out the ifdeffery in include/linux/clk.h
> > you'll see more function declarations for CONFIG_COMMON_CLK then for
> > !CONFIG_COMMON_CLK, so we're not breaking any ground here.
> > 
> > > 
> > > > 
> > > > >     if (lower >= rate || (long)lower < 0) {
> > > > If you made lower and upper a signed long, you could drop the casting
> > > > here. BTW, why does __clk_round_rate return an unsigned long??
> > > > There seem to be several more type mismatches in that area.
> > > > Maybe we should add a waring if rate is > LONG_MAX?
> > > > 
> > > > (And ISTR that the C standard doesn't specify what the result of
> > > > (long)lower is given that lower is of type unsigned long and holding a
> > > > value > LONG_MAX.)
> > > Looks like you're right. This probably needs some polishing to get types
> > > sorted out.
> > > Mike/Russel: As Uwe pointed out, shouldn't __clk_round_rate return a
> > > long as well?
> 
> Sorry, Russell, of course.
> 
> > 
> > Yeah. The strange thing is that .round_rate and .determine_rate both
> > return long. I think I was asleep at the wheel on this one.
> > 
> > I count about a dozen call sites that need to be fixed up for this
> > change to happen. As we approach 3.15-rc6 I'm a bit nervous about
> > introducing this change. How do you feel about dropping this change in
> > first thing after 3.16-rc1 and layering in your new clk_find_*_rate
> > stuff on top of it?
> > 
> > I'll take a stab at fixing up __clk_round_rate early next week.
> 
> Yeah, at some point this 'fix cpufreq stats'-series grew a little out of
> control. Targeting the 3.16 cycle sounds reasonable. Then we could probably
> also look at moving from (unsigned) long to some 64-bit type as well ;)

Agreed on the 64-bit thing.

Thanks,
Mike

> 
>         Thanks,
>         Sören
>

On Thu, 2014-05-22 at 06:37PM -0700, Mike Turquette wrote:
> Quoting Sören Brinkmann (2014-05-22 16:44:53)
> > On Thu, 2014-05-22 at 02:03PM -0700, Mike Turquette wrote:
> > > Quoting Sören Brinkmann (2014-05-22 13:32:09)
> > > > On Thu, 2014-05-22 at 08:20PM +0200, Uwe Kleine-König wrote:
> > > > > Hello Sören,
> > > > > 
> > > > > On Thu, May 22, 2014 at 11:03:00AM -0700, Sören Brinkmann wrote:
> > > > > > On Wed, 2014-05-21 at 01:33PM -0700, Mike Turquette wrote:
> > > > > > > Quoting Uwe Kleine-König (2014-05-21 11:23:08)
> > > > > > > > Hello Sören,
> > > > > > > > 
> > > > > > > > On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > > > > > > > > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > > > > > > > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > > > > > > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > > > > > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > > > > > > > > >
> > > > > > > > > > > > >>>>> +{
> > > > > > > > > > > > >>>>> + 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
> > > > > > > > > > > > >
> > > > > > > > > > > > >
> > > > > > > > > > > > 
> > > > > > > > > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > > > > > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > > > > > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > > > > > > > > implementation to decide if that means rounding the rate up or down or
> > > > > > > > > > > > to the nearest value.
> > > > > > > > > > > 
> > > > > > > > > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > > > > > > > > that case would not be handled correctly. But I also don't see a use
> > > > > > > > > > > case for such an implementation.
> > > > > > > > > > I don't really care which semantic (i.e. round up, round down or round
> > > > > > > > > > closest) is picked, but I'd vote that all should pick up the same. I
> > > > > > > > > > think the least surprising definition is to choose rounding down and add
> > > > > > > > > > the function that is under discussion here to get a nearest match.
> > > > > > > > > > 
> > > > > > > > > > So I suggest:
> > > > > > > > > > 
> > > > > > > > > >     - if round_rate is given a rate that is smaller than the
> > > > > > > > > >       smallest available rate, return 0
> > > > > > > > > >     - add WARN_ONCE to round_rate and set_rate if they return with a
> > > > > > > > > >       rate bigger than requested
> > > > > > > > > 
> > > > > > > > > Why do you think 0 is always valid? I think for a clock that can
> > > > > > > > > generate 40, 70, 120, clk_round_rate(20) should return 40.
> > > > > > > > I didn't say it's a valid value. It just makes the it possible to check
> > > > > > > > for clk_round_rate(clk, rate) <= rate.
> > > > > > > > 
> > > > > > > > I grepped a bit around and found da850_round_armrate which implements a
> > > > > > > > round_rate callback returning the best match.
> > > > > > > > omap1_clk_round_rate_ckctl_arm can return a value < 0.
> > > > > > > > s3c2412_roundrate_usbsrc can return values that are bigger than
> > > > > > > > requested. (I wonder if that is a bug though.)
> > > > > > > > 
> > > > > > > > > >     - change the return values to unsigned long
> > > > > > > > > 
> > > > > > > > > Yep, I agree, this should happen.
> > > > > > > > And we're using 0 as error value? e.g. for the case where
> > > > > > > > omap1_clk_round_rate_ckctl_arm returns -EIO now?
> > > > > > > 
> > > > > > > No. clk_round_rate returns long for a reason, which is that we can
> > > > > > > provide an error code to the caller. From include/linux/clk.h:
> > > > > > > 
> > > > > > > /**
> > > > > > >  * clk_round_rate - adjust a rate to the exact rate a clock can provide
> > > > > > >  * @clk: clock source
> > > > > > >  * @rate: desired clock rate in Hz
> > > > > > >  *
> > > > > > >  * Returns rounded clock rate in Hz, or negative errno.
> > > > > > >  */
> > > > > > > 
> > > > > > > This has the unfortunate side effect that the max value we can return
> > > > > > > safely is 2147483647 (~2GHz). So another issue here is converting clock
> > > > > > > rates to 64-bit values.
> > > > > > 
> > > > > > So, let's assume
> > > > > >  - a clock does either of these
> > > > > >    - round down
> > > > > >    - round nearest
> > > > > >    - round up (is there any such case? I don't see a use-case for this)
> > > > > >  - or return an error
> > > > > > 
> > > > > > I think my latest try handles such cases, with the limitation of
> > > > > > for a clock that rounds up, the up-rounded value is found instead of the
> > > > > > nearest.
> > > > > > 
> > > > > > 
> > > > > > static long clk_find_nearest_rate(struct clk *clk, unsigned long rate)
> > > > > > {
> > > > > >     long ret;
> > > > > >     unsigned long lower, upper;
> > > > > > 
> > > > > >     clk_prepare_lock();
> > > > > > 
> > > > > >     lower = __clk_round_rate(clk, rate);
> > > > > this is CCF specific while I don't see a need for it. (But yes, a
> > > > > lock-less clk_find_nearest_rate is of course racy.)
> > > > Do we have to support non-CCF implementations? Isn't switching to the
> > > > CCF encouraged?
> > > 
> > > No we don't. If you check out the ifdeffery in include/linux/clk.h
> > > you'll see more function declarations for CONFIG_COMMON_CLK then for
> > > !CONFIG_COMMON_CLK, so we're not breaking any ground here.
> > > 
> > > > 
> > > > > 
> > > > > >     if (lower >= rate || (long)lower < 0) {
> > > > > If you made lower and upper a signed long, you could drop the casting
> > > > > here. BTW, why does __clk_round_rate return an unsigned long??
> > > > > There seem to be several more type mismatches in that area.
> > > > > Maybe we should add a waring if rate is > LONG_MAX?
> > > > > 
> > > > > (And ISTR that the C standard doesn't specify what the result of
> > > > > (long)lower is given that lower is of type unsigned long and holding a
> > > > > value > LONG_MAX.)
> > > > Looks like you're right. This probably needs some polishing to get types
> > > > sorted out.
> > > > Mike/Russel: As Uwe pointed out, shouldn't __clk_round_rate return a
> > > > long as well?
> > 
> > Sorry, Russell, of course.
> > 
> > > 
> > > Yeah. The strange thing is that .round_rate and .determine_rate both
> > > return long. I think I was asleep at the wheel on this one.
> > > 
> > > I count about a dozen call sites that need to be fixed up for this
> > > change to happen. As we approach 3.15-rc6 I'm a bit nervous about
> > > introducing this change. How do you feel about dropping this change in
> > > first thing after 3.16-rc1 and layering in your new clk_find_*_rate
> > > stuff on top of it?
> > > 
> > > I'll take a stab at fixing up __clk_round_rate early next week.
> > 
> > Yeah, at some point this 'fix cpufreq stats'-series grew a little out of
> > control. Targeting the 3.16 cycle sounds reasonable. Then we could probably
> > also look at moving from (unsigned) long to some 64-bit type as well ;)
> 
> Agreed on the 64-bit thing.

Viresh: Could you imagine something similar for cpufreq? You suggested
migrating to Hz resolution. I guess that would ideally mean to follow
the CCF to a 64-bit type for frequencies and increasing the resolution.
I have a messy patch migrating cpufreq and OPP to Hz and unsigned long
that works on Zynq. But cpufreq has so many users that it would become
quite an undertaking.
And we'd need some new/amended OPP DT binding.

	Thanks,
	Sören

On 23 May 2014 21:44, Sören Brinkmann <soren.brinkmann@xilinx.com> wrote:
> Viresh: Could you imagine something similar for cpufreq? You suggested
> migrating to Hz resolution. I guess that would ideally mean to follow
> the CCF to a 64-bit type for frequencies and increasing the resolution.
> I have a messy patch migrating cpufreq and OPP to Hz and unsigned long
> that works on Zynq. But cpufreq has so many users that it would become
> quite an undertaking.
> And we'd need some new/amended OPP DT binding.

If we are going to migrate to Hz from KHz, I think we must consider the
64 bit stuff right now, otherwise it will bite us later.

@Rafael: What do you think?

On 26 May 2014 16:52, Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> I agree as far as the 64-bit thing goes, but is switching to Hz really
> necessary?

Don't really know that.. It seems that there will always be problems with
close enough frequencies whenever rounding is done.

More can be elaborated by Soren.

On Monday, May 26, 2014 11:59:09 AM Viresh Kumar wrote:
> On 23 May 2014 21:44, Sören Brinkmann <soren.brinkmann@xilinx.com> wrote:
> > Viresh: Could you imagine something similar for cpufreq? You suggested
> > migrating to Hz resolution. I guess that would ideally mean to follow
> > the CCF to a 64-bit type for frequencies and increasing the resolution.
> > I have a messy patch migrating cpufreq and OPP to Hz and unsigned long
> > that works on Zynq. But cpufreq has so many users that it would become
> > quite an undertaking.
> > And we'd need some new/amended OPP DT binding.
> 
> If we are going to migrate to Hz from KHz, I think we must consider the
> 64 bit stuff right now, otherwise it will bite us later.
> 
> @Rafael: What do you think?

I agree as far as the 64-bit thing goes, but is switching to Hz really
necessary?

Rafael

On Monday, May 26, 2014 04:37:13 PM Viresh Kumar wrote:
> On 26 May 2014 16:52, Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> > I agree as far as the 64-bit thing goes, but is switching to Hz really
> > necessary?
> 
> Don't really know that.. It seems that there will always be problems with
> close enough frequencies whenever rounding is done.

Well, rounding errors are a problem, but question is if that is enough of
a problem to justify expanding the storage size twice.  Also, that'd be
a performance hit on 32-bit systems.

> More can be elaborated by Soren.

OK

Rafael

On Mon, 2014-05-26 at 01:47PM +0200, Rafael J. Wysocki wrote:
> On Monday, May 26, 2014 04:37:13 PM Viresh Kumar wrote:
> > On 26 May 2014 16:52, Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> > > I agree as far as the 64-bit thing goes, but is switching to Hz really
> > > necessary?
> > 
> > Don't really know that.. It seems that there will always be problems with
> > close enough frequencies whenever rounding is done.
> 
> Well, rounding errors are a problem, but question is if that is enough of
> a problem to justify expanding the storage size twice.  Also, that'd be
> a performance hit on 32-bit systems.
> 
> > More can be elaborated by Soren.
> 
> OK

I'd say it's probably not worth switching. As you and I said, rounding
issues are likely to happen no matter what. In this particular case,
switching would not remove the need for the patch I proposed to allow
for rounding errors. The error margin could be reduced, but that's it.
I think it would be nice if CCF, OPP and cpufreq would use the same
resolution and types, since it would remove the need for all these
conversions that are going on in cpufreq drivers, but looking at the
wide usage of cpufreq and the potential drawbacks Rafael pointed at:
nice-to-have is probably not enough of a justification.

	Sören

Quoting Rafael J. Wysocki (2014-05-26 04:22:32)
> On Monday, May 26, 2014 11:59:09 AM Viresh Kumar wrote:
> > On 23 May 2014 21:44, Sören Brinkmann <soren.brinkmann@xilinx.com> wrote:
> > > Viresh: Could you imagine something similar for cpufreq? You suggested
> > > migrating to Hz resolution. I guess that would ideally mean to follow
> > > the CCF to a 64-bit type for frequencies and increasing the resolution.
> > > I have a messy patch migrating cpufreq and OPP to Hz and unsigned long
> > > that works on Zynq. But cpufreq has so many users that it would become
> > > quite an undertaking.
> > > And we'd need some new/amended OPP DT binding.
> > 
> > If we are going to migrate to Hz from KHz, I think we must consider the
> > 64 bit stuff right now, otherwise it will bite us later.
> > 
> > @Rafael: What do you think?
> 
> I agree as far as the 64-bit thing goes, but is switching to Hz really
> necessary?

Rafael,

Why should CPUfreq migrate to 64-bit if not switching to Hz? CPU clock
rates are specified as KHz in CPUfreq via an unsigned int. On 32-bit
systems that comes out to a max of 4.29THz (terahertz!)!

Or maybe you meant, "I agree that the clock framework should switch to
the 64-bit thing"?

Personally I'd like to see the clock framework and cpufreq get on the
same page (data type) for specifying clock rates, and the clock
framework really should not use a granularity like KHz. In fact we have
some fractional rates like 13.25Hz ...

Thanks,
Mike

> 
> Rafael
>

On Tuesday, May 27, 2014 07:05:31 PM Mike Turquette wrote:
> Quoting Rafael J. Wysocki (2014-05-26 04:22:32)
> > On Monday, May 26, 2014 11:59:09 AM Viresh Kumar wrote:
> > > On 23 May 2014 21:44, Sören Brinkmann <soren.brinkmann@xilinx.com> wrote:
> > > > Viresh: Could you imagine something similar for cpufreq? You suggested
> > > > migrating to Hz resolution. I guess that would ideally mean to follow
> > > > the CCF to a 64-bit type for frequencies and increasing the resolution.
> > > > I have a messy patch migrating cpufreq and OPP to Hz and unsigned long
> > > > that works on Zynq. But cpufreq has so many users that it would become
> > > > quite an undertaking.
> > > > And we'd need some new/amended OPP DT binding.
> > > 
> > > If we are going to migrate to Hz from KHz, I think we must consider the
> > > 64 bit stuff right now, otherwise it will bite us later.
> > > 
> > > @Rafael: What do you think?
> > 
> > I agree as far as the 64-bit thing goes, but is switching to Hz really
> > necessary?
> 
> Rafael,
> 
> Why should CPUfreq migrate to 64-bit if not switching to Hz? CPU clock
> rates are specified as KHz in CPUfreq via an unsigned int. On 32-bit
> systems that comes out to a max of 4.29THz (terahertz!)!
> 
> Or maybe you meant, "I agree that the clock framework should switch to
> the 64-bit thing"?

That should have been something like "If we were to switch to Hz
resolution, it would be necessary to switch over to 64-bit too".

> Personally I'd like to see the clock framework and cpufreq get on the
> same page (data type) for specifying clock rates, and the clock
> framework really should not use a granularity like KHz. In fact we have
> some fractional rates like 13.25Hz ...

Well, as I said.  There's a cost to that and it is not particularly
clear to me whether or not that cost is justifiable.  And some architectures
don't even use the clock framework for cpufreq, mind you.  How many of them
do, actually?

Rafael

On Thu, 2014-05-22 at 08:20PM +0200, Uwe Kleine-König wrote:
> Hello Sören,
> 
> On Thu, May 22, 2014 at 11:03:00AM -0700, Sören Brinkmann wrote:
> > On Wed, 2014-05-21 at 01:33PM -0700, Mike Turquette wrote:
> > > Quoting Uwe Kleine-König (2014-05-21 11:23:08)
> > > > Hello Sören,
> > > > 
> > > > On Wed, May 21, 2014 at 08:58:10AM -0700, Sören Brinkmann wrote:
> > > > > On Wed, 2014-05-21 at 09:34AM +0200, Uwe Kleine-König wrote:
> > > > > > On Tue, May 20, 2014 at 02:48:20PM -0700, Sören Brinkmann wrote:
> > > > > > > On Tue, 2014-05-20 at 10:48AM -0700, Stephen Boyd wrote:
> > > > > > > > On 05/20/14 09:01, Sören Brinkmann wrote:
> > > > > > > > >
> > > > > > > > >>>>> +{
> > > > > > > > >>>>> + 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
> > > > > > > > >
> > > > > > > > >
> > > > > > > > 
> > > > > > > > Please call this new API something like clk_find_nearest_rate() or
> > > > > > > > something. clk_round_rate() is supposed to return the rate that will be
> > > > > > > > set if you call clk_set_rate() with the same arguments. It's up to the
> > > > > > > > implementation to decide if that means rounding the rate up or down or
> > > > > > > > to the nearest value.
> > > > > > > 
> > > > > > > Sounds good to me. Are there any cases of clocks that round up? I think
> > > > > > > that case would not be handled correctly. But I also don't see a use
> > > > > > > case for such an implementation.
> > > > > > I don't really care which semantic (i.e. round up, round down or round
> > > > > > closest) is picked, but I'd vote that all should pick up the same. I
> > > > > > think the least surprising definition is to choose rounding down and add
> > > > > > the function that is under discussion here to get a nearest match.
> > > > > > 
> > > > > > So I suggest:
> > > > > > 
> > > > > >     - if round_rate is given a rate that is smaller than the
> > > > > >       smallest available rate, return 0
> > > > > >     - add WARN_ONCE to round_rate and set_rate if they return with a
> > > > > >       rate bigger than requested
> > > > > 
> > > > > Why do you think 0 is always valid? I think for a clock that can
> > > > > generate 40, 70, 120, clk_round_rate(20) should return 40.
> > > > I didn't say it's a valid value. It just makes the it possible to check
> > > > for clk_round_rate(clk, rate) <= rate.
> > > > 
> > > > I grepped a bit around and found da850_round_armrate which implements a
> > > > round_rate callback returning the best match.
> > > > omap1_clk_round_rate_ckctl_arm can return a value < 0.
> > > > s3c2412_roundrate_usbsrc can return values that are bigger than
> > > > requested. (I wonder if that is a bug though.)
> > > > 
> > > > > >     - change the return values to unsigned long
> > > > > 
> > > > > Yep, I agree, this should happen.
> > > > And we're using 0 as error value? e.g. for the case where
> > > > omap1_clk_round_rate_ckctl_arm returns -EIO now?
> > > 
> > > No. clk_round_rate returns long for a reason, which is that we can
> > > provide an error code to the caller. From include/linux/clk.h:
> > > 
> > > /**
> > >  * clk_round_rate - adjust a rate to the exact rate a clock can provide
> > >  * @clk: clock source
> > >  * @rate: desired clock rate in Hz
> > >  *
> > >  * Returns rounded clock rate in Hz, or negative errno.
> > >  */
> > > 
> > > This has the unfortunate side effect that the max value we can return
> > > safely is 2147483647 (~2GHz). So another issue here is converting clock
> > > rates to 64-bit values.
> > 
> > So, let's assume
> >  - a clock does either of these
> >    - round down
> >    - round nearest
> >    - round up (is there any such case? I don't see a use-case for this)
> >  - or return an error
> > 
> > I think my latest try handles such cases, with the limitation of
> > for a clock that rounds up, the up-rounded value is found instead of the
> > nearest.
> > 
> > 
> > static long clk_find_nearest_rate(struct clk *clk, unsigned long rate)
> > {
> > 	long ret;
> > 	unsigned long lower, upper;
> > 
> > 	clk_prepare_lock();
> > 
> > 	lower = __clk_round_rate(clk, rate);
> this is CCF specific while I don't see a need for it. (But yes, a
> lock-less clk_find_nearest_rate is of course racy.)
> 
> > 	if (lower >= rate || (long)lower < 0) {
> If you made lower and upper a signed long, you could drop the casting
> here. BTW, why does __clk_round_rate return an unsigned long??
> There seem to be several more type mismatches in that area.
> Maybe we should add a waring if rate is > LONG_MAX?
> 
> (And ISTR that the C standard doesn't specify what the result of
> (long)lower is given that lower is of type unsigned long and holding a
> value > LONG_MAX.)

I have another iteration. I kept the locking part, switched to assuming
'long' being used for frequencies and hopefully got rid of constructs
that are not defined by the C standard:

long clk_find_nearest_rate(struct clk *clk, unsigned long rate)
{
	long ret, lower, upper;
	unsigned long tmp;

	clk_prepare_lock();

	lower = __clk_round_rate(clk, rate);
	if (lower >= rate || lower < 0) {
		ret = lower;
		goto unlock;
	}

	tmp = rate + (rate - lower) - 1;
	if (tmp > LONG_MAX)
		upper = LONG_MAX;
	else
		upper = tmp;

	upper = __clk_round_rate(clk, upper);
	if (upper <= lower || upper < 0) {
		ret = lower;
		goto unlock;
	}

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

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

	ret = upper;

unlock:
	clk_prepare_unlock();

	return ret;
}

Is there a more elegant way to check for the arithmetic overflow?

	Thanks,
	Sören