Skip to contentSkip to conversation

clocksource: tcb: fix min_delta calculation

PATCH New Marc Kleine-Budde 8 participants 33 messages Sep 13, 2013 – Oct 23, 2013

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 clocksource: tcb: fix min_delta calculation

The commit

77cc982 clocksource: use clockevents_config_and_register() where possible

switches from manually calculating min_delta_ns (and others) and clockevents_register_device() to automatic calculation via clockevents_config_and_register(). During this conversation the "+ 1" in

    min_delta_ns = clockevent_delta2ns(1, &clkevt.clkevt) + 1;

was lost. This leads to problems when programming clock events, resuling in e.g. a sleep(2) sleeping more than 3 seconds. The "+ 1" was added in the original code to fix a rounding problem in clockevent_delta2ns(), see
http://permalink.gmane.org/gmane.linux.kernel/549744 for background information.

This patch fixes the problem by increasing the min_delta to "2" ticks.

---
Changes since v1:
- Improved description. Thanks to Ronald Wahl.

 drivers/clocksource/tcb_clksrc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/clocksource/tcb_clksrc.c +1 -1
index 8a61872..7cf6dc7 100644
@@ -197,7 +197,7 @@ static void __init setup_clkevents(struct atmel_tc *tc, int clk32k_divisor_idx)
 
 	clkevt.clkevt.cpumask = cpumask_of(0);
 
-	clockevents_config_and_register(&clkevt.clkevt, 32768, 1, 0xffff);
+	clockevents_config_and_register(&clkevt.clkevt, 32768, 2, 0xffff);
 
 	setup_irq(irq, &tc_irqaction);
 }
Signature · 1 line
1.8.4.rc3
#1 lore raw

PATCH 1/1 clocksource: tcb: fix min_delta calculation

Hello Marc,

Quoted 10 lines · Marc Kleine-Budde

The commit

77cc982 clocksource: use clockevents_config_and_register() where possible

switches from manually calculating min_delta_ns (and others) and clockevents_register_device() to automatic calculation via clockevents_config_and_register(). During this conversation the "+ 1" in

    min_delta_ns = clockevent_delta2ns(1, &clkevt.clkevt) + 1;
Quoted 7 lines

was lost. This leads to problems when programming clock events, resuling in e.g. a sleep(2) sleeping more than 3 seconds. The "+ 1" was added in the original code to fix a rounding problem in clockevent_delta2ns(), see
http://permalink.gmane.org/gmane.linux.kernel/549744 for background information.

This patch fixes the problem by increasing the min_delta to "2" ticks.

Any reason to not do this:

drivers/clocksource/tcb_clksrc.c +0 -0
@@ -144,6 +144,9 @@ static void tc_mode(enum clock_event_mode m, struct

clock_event_device *d)

static int tc_next_event(unsigned long delta, struct clock_event_device
*d)
{
+ if (delta < d->min_delta_ticks)
+ delta = d->min_delta_ticks;
+

        __raw_writel(delta, tcaddr + ATMEL_TC_REG(2, RC));
 
        /* go go gadget! */

Then we can keep the same min_delta.

One more question why doing the correction here and not in the delta2ns conversion function?

Regards

Ludovic

Quoted 33 lines

---
Changes since v1:
- Improved description. Thanks to Ronald Wahl.

 drivers/clocksource/tcb_clksrc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/clocksource/tcb_clksrc.c +1 -1
index 8a61872..7cf6dc7 100644
@@ -197,7 +197,7 @@ static void __init setup_clkevents(struct atmel_tc *tc, int clk32k_divisor_idx)
 
 	clkevt.clkevt.cpumask = cpumask_of(0);
 
-	clockevents_config_and_register(&clkevt.clkevt, 32768, 1, 0xffff);
+	clockevents_config_and_register(&clkevt.clkevt, 32768, 2, 0xffff);
 
 	setup_irq(irq, &tc_irqaction);
 }
Signature · 7 lines
1.8.4.rc3


_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
#2 lore raw
Quoted 15 lines · Ludovic Desroches

Any reason to not do this:

drivers/clocksource/tcb_clksrc.c +3 -0
@@ -144,6 +144,9 @@ static void tc_mode(enum clock_event_mode m, struct
 clock_event_device *d)
 
 static int tc_next_event(unsigned long delta, struct clock_event_device
 *d)
 {
+       if (delta < d->min_delta_ticks)
+               delta = d->min_delta_ticks;
+
        __raw_writel(delta, tcaddr + ATMEL_TC_REG(2, RC));
Quoted 3 lines
        /* go go gadget! */

Then we can keep the same min_delta.

You really should not play such games in your set_next_event() code - if the interval is not supported, you should return -ETIME so that the core code knows about it and can adjust things to suit. If you're getting deltas which are too small for the hardware, that'll either be because the bounds are wrong, or there's a bug in the core code.

#3 lore raw
Quoted 18 lines · Russell King - ARM Linux
Quoted 17 lines · Ludovic Desroches

Any reason to not do this:

drivers/clocksource/tcb_clksrc.c +3 -0
@@ -144,6 +144,9 @@ static void tc_mode(enum clock_event_mode m, struct
 clock_event_device *d)
 
 static int tc_next_event(unsigned long delta, struct clock_event_device
 *d)
 {
+       if (delta < d->min_delta_ticks)
+               delta = d->min_delta_ticks;
+
        __raw_writel(delta, tcaddr + ATMEL_TC_REG(2, RC));
 
        /* go go gadget! */
Quoted 7 lines
Quoted 1 line

Then we can keep the same min_delta.

You really should not play such games in your set_next_event() code - if the interval is not supported, you should return -ETIME so that the core code knows about it and can adjust things to suit. If you're getting deltas which are too small for the hardware, that'll either be because the bounds are wrong, or there's a bug in the core code.

The core code does:

int clockevents_program_event(struct clock_event_device *dev, ktime_t expires,
bool force)
{
....

        delta = min(delta, (int64_t) dev->max_delta_ns);
        delta = max(delta, (int64_t) dev->min_delta_ns);

        clc = ((unsigned long long) delta * dev->mult) >> dev->shift;
        rc = dev->set_next_event((unsigned long) clc, dev);

}

So, the min_delta in timer ticks is set to 1 and converted by the core to nsecs for various reasons. This is where the rounding problem comes into play.

The patch below should fix that.

Thanks,

tglx
----

kernel/time/clockevents.c +9 -1
index 38959c8..41b7a30 100644
@@ -42,7 +42,7 @@ struct ce_unbind {
  */
 u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
 {
-	u64 clc = (u64) latch << evt->shift;
+	u64 tmp, clc = (u64) latch << evt->shift;
 
 	if (unlikely(!evt->mult)) {
 		evt->mult = 1;
@@ -52,6 +52,14 @@ u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
 	do_div(clc, evt->mult);
 	if (clc < 1000)
 		clc = 1000;
+
+	/* Avoid rounding artifacts */
+	tmp = (clc * dev->mult) >> dev->shift;
+	while (tmp < (u64) dev->min_delta_ticks) {
+		clc += 1000;
+		tmp = (clc * dev->mult) >> dev->shift;
+	}
+
 	if (clc > KTIME_MAX)
 		clc = KTIME_MAX;
 
#4 lore raw

PATCH 1/1 clocksource: tcb: fix min_delta calculation

Quoted 41 lines · Thomas Gleixner
Quoted 18 lines · Russell King - ARM Linux
Quoted 17 lines · Ludovic Desroches

Any reason to not do this:

drivers/clocksource/tcb_clksrc.c +3 -0
@@ -144,6 +144,9 @@ static void tc_mode(enum clock_event_mode m, struct
 clock_event_device *d)
 
 static int tc_next_event(unsigned long delta, struct clock_event_device
 *d)
 {
+       if (delta < d->min_delta_ticks)
+               delta = d->min_delta_ticks;
+
        __raw_writel(delta, tcaddr + ATMEL_TC_REG(2, RC));
 
        /* go go gadget! */
Quoted 7 lines
Quoted 1 line

Then we can keep the same min_delta.

You really should not play such games in your set_next_event() code - if the interval is not supported, you should return -ETIME so that the core code knows about it and can adjust things to suit. If you're getting deltas which are too small for the hardware, that'll either be because the bounds are wrong, or there's a bug in the core code.

The core code does:

int clockevents_program_event(struct clock_event_device *dev, ktime_t expires,
bool force)
{
....

        delta = min(delta, (int64_t) dev->max_delta_ns);
        delta = max(delta, (int64_t) dev->min_delta_ns);

        clc = ((unsigned long long) delta * dev->mult) >> dev->shift;
        rc = dev->set_next_event((unsigned long) clc, dev);
Quoted 7 lines

}

So, the min_delta in timer ticks is set to 1 and converted by the core to nsecs for various reasons. This is where the rounding problem comes into play.

The patch below should fix that.

Yes it works with s/dev/evt.

Thanks

Quoted 33 lines

Thanks,

tglx
----

kernel/time/clockevents.c +9 -1
index 38959c8..41b7a30 100644
@@ -42,7 +42,7 @@ struct ce_unbind {
  */
 u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
 {
-	u64 clc = (u64) latch << evt->shift;
+	u64 tmp, clc = (u64) latch << evt->shift;
 
 	if (unlikely(!evt->mult)) {
 		evt->mult = 1;
@@ -52,6 +52,14 @@ u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
 	do_div(clc, evt->mult);
 	if (clc < 1000)
 		clc = 1000;
+
+	/* Avoid rounding artifacts */
+	tmp = (clc * dev->mult) >> dev->shift;
+	while (tmp < (u64) dev->min_delta_ticks) {
+		clc += 1000;
+		tmp = (clc * dev->mult) >> dev->shift;
+	}
+
 	if (clc > KTIME_MAX)
 		clc = KTIME_MAX;
 
#5 lore raw

PATCH 1/1 clockevents: Sanitize ticks to nsec conversion

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

Now instead of fixing the underlying core code problem, Marcs patch tried to work around the core code issue by increasing the minimal tick delta at clockevents registration time so the resulting limit in the core code backwards conversion did not violate the hardware limits. More SIGH!

The solution for the issue at hand is simple: adding evt->mult - 1 to the shifted value before the integer divison in the core conversion function takes care of it.

Though looking closer at the details of that function reveals another
bogosity: The upper bounds check is broken as well. Checking for a resulting "clc" value greater than KTIME_MAX after the conversion is pointless. The conversion does:

      u64 clc = (latch << evt->shift) / evt->mult;

So there is no sanity check for (latch << evt->shift) exceeding the 64bit boundary. The latch argument is "unsigned long", so on a 64bit arch the handed in argument could easily lead to an unnoticed shift overflow. With the above rounding fix applied the calculation before the divison is:

       u64 clc = (latch << evt->shift) + evt->mult - 1;

Now we can easily verify whether the whole equation fits into the 64bit boundary. Shifting the "clc" result back by evt->shift MUST result in "latch". If that's not the case, we have a clear indicator for boundary violation and can limit "clc" to (1 << 63) - 1 before the divison by evt->mult. The resulting nsec * evt->mult in the programming path will therefor always be in the 64bit boundary.

---

kernel/time/clockevents.c +17 -5
index 38959c8..4fc4826 100644
@@ -49,13 +49,25 @@ u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
 		WARN_ON(1);
 	}
 
+	/*
+	 * Prevent integer rounding loss, otherwise the backward
+	 * conversion from nsec to ticks could result in a value less
+	 * than evt->min_delta_ticks.
+	 */
+	clc += evt->mult - 1;
+
+	/*
+	 * Upper bound sanity check. If the backwards conversion is
+	 * not equal latch, we know that the above (shift + rounding
+	 * correction) exceeded the 64 bit boundary.
+	 */
+	if ((clc >> evt->shift) != (u64)latch)
+		clc = ((u64)1 << 63) - 1;
+
 	do_div(clc, evt->mult);
-	if (clc < 1000)
-		clc = 1000;
-	if (clc > KTIME_MAX)
-		clc = KTIME_MAX;
 
-	return clc;
+	/* Deltas less than 1usec are pointless noise */
+	return clc > 1000 ? clc : 1000;
 }
 EXPORT_SYMBOL_GPL(clockevent_delta2ns);
#6 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Quoted 12 lines · Thomas Gleixner

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

Quoted 5 lines

Now instead of fixing the underlying core code problem, Marcs patch tried to work around the core code issue by increasing the minimal tick delta at clockevents registration time so the resulting limit in the core code backwards conversion did not violate the hardware limits. More SIGH!

It was not easy getting your attention with this problem :)

Marc

Signature · 12 lines
Pengutronix e.K.                  | Marc Kleine-Budde           |
Industrial Linux Solutions        | Phone: +49-231-2826-924     |
Vertretung West/Dortmund          | Fax:   +49-5121-206917-5555 |
Amtsgericht Hildesheim, HRA 2686  | http://www.pengutronix.de   |

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 259 bytes
Desc: OpenPGP digital signature
URL: <http://lists.infradead.org/pipermail/linux-arm-kernel/attachments/20130918/6569f9f6/attachment.sig>
#7 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Quoted 13 lines · Marc Kleine-Budde
Quoted 12 lines · Thomas Gleixner

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

Quoted 7 lines
Quoted 5 lines

Now instead of fixing the underlying core code problem, Marcs patch tried to work around the core code issue by increasing the minimal tick delta at clockevents registration time so the resulting limit in the core code backwards conversion did not violate the hardware limits. More SIGH!

It was not easy getting your attention with this problem :)

A really hard to understand and solve problem! Obviously you are a great fan of John Stultz famous "Math is hard, lets go shopping!" line.

Why on earth do you need my attention to fix at least the simple rounding issue in the core code?

You could have sent the "clk += evt->mult - 1:" patch directly to Linus without even cc'ing me.

It's not rocket science, really. When I responded with the while(1) loop patch today in the morning it was just because I did not have a second to think about the correct fix for this, but the reason WHY this happened was entirely clear in a split second after reading Russells reply.

The upper bounds issue tooks a few minutes more, but it's not rocket science either.

Sorry, I can understand the need for a second opinion on a weird race condition problem, but tracking down an obvious simple math issue to the point and fixing it... SIGH!

Thanks,

tglx

#8 lore raw

PATCH 1/1 clockevents: Sanitize ticks to nsec conversion

In reply to Thomas Gleixner
Quoted 37 lines · Thomas Gleixner

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

Now instead of fixing the underlying core code problem, Marcs patch tried to work around the core code issue by increasing the minimal tick delta at clockevents registration time so the resulting limit in the core code backwards conversion did not violate the hardware limits. More SIGH!

The solution for the issue at hand is simple: adding evt->mult - 1 to the shifted value before the integer divison in the core conversion function takes care of it.

Though looking closer at the details of that function reveals another
bogosity: The upper bounds check is broken as well. Checking for a resulting "clc" value greater than KTIME_MAX after the conversion is pointless. The conversion does:

      u64 clc = (latch << evt->shift) / evt->mult;

So there is no sanity check for (latch << evt->shift) exceeding the 64bit boundary. The latch argument is "unsigned long", so on a 64bit arch the handed in argument could easily lead to an unnoticed shift overflow. With the above rounding fix applied the calculation before the divison is:

       u64 clc = (latch << evt->shift) + evt->mult - 1;
Quoted 8 lines

Now we can easily verify whether the whole equation fits into the 64bit boundary. Shifting the "clc" result back by evt->shift MUST result in "latch". If that's not the case, we have a clear indicator for boundary violation and can limit "clc" to (1 << 63) - 1 before the divison by evt->mult. The resulting nsec * evt->mult in the programming path will therefor always be in the 64bit boundary.

Thanks

Quoted 35 lines

---

kernel/time/clockevents.c +17 -5
index 38959c8..4fc4826 100644
@@ -49,13 +49,25 @@ u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
 		WARN_ON(1);
 	}
 
+	/*
+	 * Prevent integer rounding loss, otherwise the backward
+	 * conversion from nsec to ticks could result in a value less
+	 * than evt->min_delta_ticks.
+	 */
+	clc += evt->mult - 1;
+
+	/*
+	 * Upper bound sanity check. If the backwards conversion is
+	 * not equal latch, we know that the above (shift + rounding
+	 * correction) exceeded the 64 bit boundary.
+	 */
+	if ((clc >> evt->shift) != (u64)latch)
+		clc = ((u64)1 << 63) - 1;
+
 	do_div(clc, evt->mult);
-	if (clc < 1000)
-		clc = 1000;
-	if (clc > KTIME_MAX)
-		clc = KTIME_MAX;
 
-	return clc;
+	/* Deltas less than 1usec are pointless noise */
+	return clc > 1000 ? clc : 1000;
 }
 EXPORT_SYMBOL_GPL(clockevent_delta2ns);
#9 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

In reply to Thomas Gleixner

Hello Thomas,

Quoted 12 lines · Thomas Gleixner

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

Quoted 1 line

Now instead of fixing the underlying core code problem, Marcs patch

s/Marcs/Marc's/

Quoted 22 lines

tried to work around the core code issue by increasing the minimal tick delta at clockevents registration time so the resulting limit in the core code backwards conversion did not violate the hardware limits. More SIGH!

The solution for the issue at hand is simple: adding evt->mult - 1 to the shifted value before the integer divison in the core conversion function takes care of it.

Though looking closer at the details of that function reveals another
bogosity: The upper bounds check is broken as well. Checking for a resulting "clc" value greater than KTIME_MAX after the conversion is pointless. The conversion does:

      u64 clc = (latch << evt->shift) / evt->mult;

So there is no sanity check for (latch << evt->shift) exceeding the 64bit boundary. The latch argument is "unsigned long", so on a 64bit arch the handed in argument could easily lead to an unnoticed shift overflow. With the above rounding fix applied the calculation before the divison is:

Quoted 5 lines
       u64 clc = (latch << evt->shift) + evt->mult - 1;

Now we can easily verify whether the whole equation fits into the 64bit boundary. Shifting the "clc" result back by evt->shift MUST result in "latch". If that's not the case, we have a clear indicator

But this is only the case if evt->mult is <= (1 << evt->shift). Is this always given?
Is it more sensible to adjust dev->max_delta_ns once at register time and so save the often recurrent overflow check in clockevents_program_event?

Another doubt I have is: You changed clockevent_delta2ns to round up now unconditionally. For the numbers on at91 that doesn't matter, but I wonder if there are situations that make the timer core violate the max_delta_ticks condition now.

Quoted 1 line

for boundary violation and can limit "clc" to (1 << 63) - 1 before the

Where does this magic constant come from?

Best regards
Uwe

Quoted 40 lines

divison by evt->mult. The resulting nsec * evt->mult in the programming path will therefor always be in the 64bit boundary.

---

kernel/time/clockevents.c +17 -5
index 38959c8..4fc4826 100644
@@ -49,13 +49,25 @@ u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
 		WARN_ON(1);
 	}
 
+	/*
+	 * Prevent integer rounding loss, otherwise the backward
+	 * conversion from nsec to ticks could result in a value less
+	 * than evt->min_delta_ticks.
+	 */
+	clc += evt->mult - 1;
+
+	/*
+	 * Upper bound sanity check. If the backwards conversion is
+	 * not equal latch, we know that the above (shift + rounding
+	 * correction) exceeded the 64 bit boundary.
+	 */
+	if ((clc >> evt->shift) != (u64)latch)
+		clc = ((u64)1 << 63) - 1;
+
 	do_div(clc, evt->mult);
-	if (clc < 1000)
-		clc = 1000;
-	if (clc > KTIME_MAX)
-		clc = KTIME_MAX;
 
-	return clc;
+	/* Deltas less than 1usec are pointless noise */
+	return clc > 1000 ? clc : 1000;
 }
 EXPORT_SYMBOL_GPL(clockevent_delta2ns);
 
Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#10 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Quoted 5 lines · Uwe Kleine-K?nig
Quoted 3 lines

Now we can easily verify whether the whole equation fits into the 64bit boundary. Shifting the "clc" result back by evt->shift MUST result in "latch". If that's not the case, we have a clear indicator

But this is only the case if evt->mult is <= (1 << evt->shift). Is this always given?

Crap, no. It's only true for device frequency <= 1GHz. Good catch!

Quoted 3 lines

Is it more sensible to adjust dev->max_delta_ns once at register time and so save the often recurrent overflow check in clockevents_program_event?

Which overflow check are you talking about?

There is only the boundary check:

        delta = min(delta, (int64_t) dev->max_delta_ns);
        delta = max(delta, (int64_t) dev->min_delta_ns);

Which sensible adjustment at register time is going to remove that?

Quoted 4 lines

Another doubt I have is: You changed clockevent_delta2ns to round up now unconditionally. For the numbers on at91 that doesn't matter, but I wonder if there are situations that make the timer core violate the max_delta_ticks condition now.

And how so? The + (mult - 1) ensures, that the conversion back to ticks results in the same value as latch. So how should it violate the max boundary?

Math is hard, right?

Quoted 2 lines
Quoted 1 line

for boundary violation and can limit "clc" to (1 << 63) - 1 before the

Where does this magic constant come from?

Rolling my magic hex dice gave me that.

Thanks,

tglx

#11 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Hello Thomas,

Quoted 13 lines · Thomas Gleixner
Quoted 5 lines · Uwe Kleine-K?nig
Quoted 3 lines

Now we can easily verify whether the whole equation fits into the 64bit boundary. Shifting the "clc" result back by evt->shift MUST result in "latch". If that's not the case, we have a clear indicator

But this is only the case if evt->mult is <= (1 << evt->shift). Is this always given?

Crap, no. It's only true for device frequency <= 1GHz. Good catch!

Quoted 3 lines

Is it more sensible to adjust dev->max_delta_ns once at register time and so save the often recurrent overflow check in clockevents_program_event?

Quoted 8 lines

Which overflow check are you talking about?

There is only the boundary check:

        delta = min(delta, (int64_t) dev->max_delta_ns);
        delta = max(delta, (int64_t) dev->min_delta_ns);

Which sensible adjustment at register time is going to remove that?

My idea was that wouldn't need to add

	if ((clc >> evt->shift) != (u64)latch)
		...

to clockevent_delta2ns (not clockevents_program_event as I wrote) if dev->max_delta_ns was small enough. So max_delta_ns would be the minimum of the hardware limit and the value to prevent an overflow. Not sure any more that this works though.

Quoted 8 lines
Quoted 4 lines

Another doubt I have is: You changed clockevent_delta2ns to round up now unconditionally. For the numbers on at91 that doesn't matter, but I wonder if there are situations that make the timer core violate the max_delta_ticks condition now.

And how so? The + (mult - 1) ensures, that the conversion back to ticks results in the same value as latch. So how should it violate the max boundary?

That is wrong:
With max_delta_ticks << shift = n * mult - k for k in [0 .. mult-1] and an integer n:

	  (max_delta_ns * mult) >> shift
	= ((((max_delta_ticks << shift) + mult - 1) / mult) * mult) >> shift
	= (((n * mult - k + mult - 1) / mult) * mult) >> shift
	= n * mult >> shift
	= ((max_delta_ticks << shift) + k) >> shift
	= max_delta_ticks + (k >> shift)

k >> shift is only known to be zero if mult <= 1 << shift (i.e. the same condition as above where your 64bit overflow detection is wrong). So this can result in values > max_delta_ticks.

Quoted 1 line

Math is hard, right?

Yes, if it involves integer division and overflow handling it's hard to come up with correct solutions during shopping. ;-)

Quoted 4 lines
Quoted 2 lines
Quoted 1 line

for boundary violation and can limit "clc" to (1 << 63) - 1 before the

Where does this magic constant come from?

Rolling my magic hex dice gave me that.

Wow, how many sides does your dice have? Couldn't it have choosen (u64)-1 for improved results?

Best regards
Uwe

Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#12 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Quoted 21 lines · Uwe Kleine-K?nig
Quoted 9 lines · Thomas Gleixner
Quoted 4 lines · Uwe Kleine-K?nig

Another doubt I have is: You changed clockevent_delta2ns to round up now unconditionally. For the numbers on at91 that doesn't matter, but I wonder if there are situations that make the timer core violate the max_delta_ticks condition now.

And how so? The + (mult - 1) ensures, that the conversion back to ticks results in the same value as latch. So how should it violate the max boundary?

That is wrong:
With max_delta_ticks << shift = n * mult - k for k in [0 .. mult-1] and an integer n:

	  (max_delta_ns * mult) >> shift
	= ((((max_delta_ticks << shift) + mult - 1) / mult) * mult) >> shift
	= (((n * mult - k + mult - 1) / mult) * mult) >> shift
	= n * mult >> shift
	= ((max_delta_ticks << shift) + k) >> shift
	= max_delta_ticks + (k >> shift)
Quoted 3 lines

k >> shift is only known to be zero if mult <= 1 << shift (i.e. the same condition as above where your 64bit overflow detection is wrong). So this can result in values > max_delta_ticks.

Right, should have waited for coffee actually activating the right brain cells.

So the rounding thing works nicely for mult <= (1 << sft). For the other cases the conversion is wrong by (mult / (1 << sft)) - 1. So for a 3 GHz clock it's off by 2. That's not an issue for the min value, but for the max value it might overflow the hardware limit. Not a real functional issue as we'd just get a pointless short interrupt, but for correctness reasons and for the sake of NOHZ we need to fix that.

There is no real correct solution for these cases, which will result in a correct backwards conversion. We could validate against the max delta ticks in program_event, but that adds another boundary check to the hotpath so I rather want to avoid it.

The simple solution is to check for the following in the conversion routine:

    if (latch == dev->min_delta_ticks || dev->mult <= (1 << dev->sft))
       clc += mult - 1

That ensures, that we never violate the lower boundary independent of the mult/sft relation. For the max_delta_ticks conversion in the "mult

Quoted 1 line

(1 << sft)" case we end up with a slightly smaller value, but well

inside the boundaries and close enough to the hardware limitations.

Versus the 64bit overflow check, we need to be even more careful. We need to check for overflowing (1 << 63) - 1 (i.e. the max positive value which fits into a s64). See clockevents_program_event().

So this check needs to be:

   u64 clc = (u64)latch << sft;

   if ((s64)clc < 0 || (clc >> sft ) != latch)
      clc = (1 << 63) - 1;

And the above rounding magic, which has to be applied after this needs to take the following condition into account as well:

(1 << 63) - 1 - clc >= mult - 1

If that's not true, we can't do the rounding add, but we know that we are well at the upper limit of the hardware, so no issue either.

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines
Quoted 1 line

for boundary violation and can limit "clc" to (1 << 63) - 1 before the

Where does this magic constant come from?

Rolling my magic hex dice gave me that.

Wow, how many sides does your dice have? Couldn't it have choosen (u64)-1 for improved results?

No it's restricted to s64 positiv values due to software limitations. See above.

Thanks,

tglx

#13 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Hello Thomas,

Quoted 29 lines · Thomas Gleixner
Quoted 21 lines · Uwe Kleine-K?nig
Quoted 9 lines · Thomas Gleixner
Quoted 4 lines · Uwe Kleine-K?nig

Another doubt I have is: You changed clockevent_delta2ns to round up now unconditionally. For the numbers on at91 that doesn't matter, but I wonder if there are situations that make the timer core violate the max_delta_ticks condition now.

And how so? The + (mult - 1) ensures, that the conversion back to ticks results in the same value as latch. So how should it violate the max boundary?

That is wrong:
With max_delta_ticks << shift = n * mult - k for k in [0 .. mult-1] and an integer n:

	  (max_delta_ns * mult) >> shift
	= ((((max_delta_ticks << shift) + mult - 1) / mult) * mult) >> shift
	= (((n * mult - k + mult - 1) / mult) * mult) >> shift
	= n * mult >> shift
	= ((max_delta_ticks << shift) + k) >> shift
	= max_delta_ticks + (k >> shift)
Quoted 3 lines

k >> shift is only known to be zero if mult <= 1 << shift (i.e. the same condition as above where your 64bit overflow detection is wrong). So this can result in values > max_delta_ticks.

Right, should have waited for coffee actually activating the right brain cells.

Quoted 6 lines

So the rounding thing works nicely for mult <= (1 << sft). For the other cases the conversion is wrong by (mult / (1 << sft)) - 1. So for a 3 GHz clock it's off by 2. That's not an issue for the min value, but for the max value it might overflow the hardware limit. Not a real functional issue as we'd just get a pointless short interrupt, but for correctness reasons and for the sake of NOHZ we need to fix that.

Well, you're assuming here that this is how the hardware reacts. Might be worse. But we're on the same side here, it should be fixed.

Quoted 10 lines

There is no real correct solution for these cases, which will result in a correct backwards conversion. We could validate against the max delta ticks in program_event, but that adds another boundary check to the hotpath so I rather want to avoid it.

The simple solution is to check for the following in the conversion routine:

    if (latch == dev->min_delta_ticks || dev->mult <= (1 << dev->sft))
       clc += mult - 1

I didn't do the necessary math, but I wouldn't be surprised if you'd need to check for

	latch <= dev->min_delta_ticks + n

for some non-negative n.

Another simple solution is to apply the uprounding only for min_delta_ticks -> min_delta_ns conversion, but not for the max_delta_ticks -> max_delta_ns conversion. For the first you have to guarantee not to yield lower values so round up, for the latter you must not pass on bigger values so round down.

Quoted 4 lines

That ensures, that we never violate the lower boundary independent of the mult/sft relation. For the max_delta_ticks conversion in the "mult

Quoted 1 line

(1 << sft)" case we end up with a slightly smaller value, but well

inside the boundaries and close enough to the hardware limitations.

Yeah, probably it's not worth to calculate the optimal value (actually for both limits). Anyhow, I will check that on my next shopping tour :-)

Quoted 3 lines

Versus the 64bit overflow check, we need to be even more careful. We need to check for overflowing (1 << 63) - 1 (i.e. the max positive value which fits into a s64). See clockevents_program_event().

That is because you interpret times < 0 as in the past, right? But note that the interim result we're talking about here is still to be divided by evt->mult. So assuming mult > 1, that check is too strict unless you move it below the do_div in clockevent_delta2ns. For sure it makes sense to use the same value for a and b in the handling:

if (calculatedval overflows a)
calculatedval = b

Best regards
Uwe

Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#14 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Quoted 10 lines · Uwe Kleine-K?nig
Quoted 3 lines · Thomas Gleixner

Versus the 64bit overflow check, we need to be even more careful. We need to check for overflowing (1 << 63) - 1 (i.e. the max positive value which fits into a s64). See clockevents_program_event().

That is because you interpret times < 0 as in the past, right? But note that the interim result we're talking about here is still to be divided by evt->mult. So assuming mult > 1, that check is too strict unless you move it below the do_div in clockevent_delta2ns. For sure it makes sense to use the same value for a and b in the handling:

No, it's not too strict.

    nsec = (latch << shift) / mult;

Now the backwards conversion does:

    latch = (nsec * mult) >> shift;

So we want nsec * mult to be in the positive range of s64. Which means, that latch << shift must be in that range as well.

Thanks,

tglx

#15 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Hello Thomas,

Quoted 14 lines · Thomas Gleixner
Quoted 10 lines · Uwe Kleine-K?nig
Quoted 3 lines · Thomas Gleixner

Versus the 64bit overflow check, we need to be even more careful. We need to check for overflowing (1 << 63) - 1 (i.e. the max positive value which fits into a s64). See clockevents_program_event().

That is because you interpret times < 0 as in the past, right? But note that the interim result we're talking about here is still to be divided by evt->mult. So assuming mult > 1, that check is too strict unless you move it below the do_div in clockevent_delta2ns. For sure it makes sense to use the same value for a and b in the handling:

No, it's not too strict.

Quoted 8 lines
    nsec = (latch << shift) / mult;

Now the backwards conversion does:

    latch = (nsec * mult) >> shift;

So we want nsec * mult to be in the positive range of s64. Which means, that latch << shift must be in that range as well.

The backwards conversion is in clockevents_program_event(), right? There is:

	clc = ((unsigned long long) delta * dev->mult) >> dev->shift;

So I don't see a problem if nsec * mult overflows (1 << 63) - 1 as long as it still fits into an unsigned long long (i.e. a 64 bit value).

What am I missing?

Best regards
Uwe

Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#16 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Quoted 23 lines · Uwe Kleine-K?nig
Quoted 14 lines · Thomas Gleixner
Quoted 10 lines · Uwe Kleine-K?nig
Quoted 3 lines · Thomas Gleixner

Versus the 64bit overflow check, we need to be even more careful. We need to check for overflowing (1 << 63) - 1 (i.e. the max positive value which fits into a s64). See clockevents_program_event().

That is because you interpret times < 0 as in the past, right? But note that the interim result we're talking about here is still to be divided by evt->mult. So assuming mult > 1, that check is too strict unless you move it below the do_div in clockevent_delta2ns. For sure it makes sense to use the same value for a and b in the handling:

No, it's not too strict.

Quoted 8 lines
    nsec = (latch << shift) / mult;

Now the backwards conversion does:

    latch = (nsec * mult) >> shift;

So we want nsec * mult to be in the positive range of s64. Which means, that latch << shift must be in that range as well.

Quoted 7 lines

The backwards conversion is in clockevents_program_event(), right? There is:

	clc = ((unsigned long long) delta * dev->mult) >> dev->shift;

So I don't see a problem if nsec * mult overflows (1 << 63) - 1 as long as it still fits into an unsigned long long (i.e. a 64 bit value).

Right. It doesn't matter.

#17 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

In reply to Uwe Kleine-König

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

The solution for the issue at hand is simple: adding evt->mult - 1 to the shifted value before the integer divison in the core conversion function takes care of it. But this only works for the case where for the scaled math mult/shift pair "mult <= 1 << shift" is true. For the case where "mult > 1 << shift" we can apply the rounding add only for the minimum delta value to make sure that the backward conversion is not less than the given hardware limit. For the upper bound we need to omit the rounding add, because the backwards conversion is always larger than the original latch value. That would violate the upper bound of the hardware device.

Though looking closer@the details of that function reveals another
bogosity: The upper bounds check is broken as well. Checking for a resulting "clc" value greater than KTIME_MAX after the conversion is pointless. The conversion does:

      u64 clc = (latch << evt->shift) / evt->mult;

So there is no sanity check for (latch << evt->shift) exceeding the 64bit boundary. The latch argument is "unsigned long", so on a 64bit arch the handed in argument could easily lead to an unnoticed shift overflow. With the above rounding fix applied the calculation before the divison is:

       u64 clc = (latch << evt->shift) + evt->mult - 1;

So we need to make sure, that neither the shift nor the rounding add is overflowing the u64 boundary.

Cc Russell King - ARM Linux <[email protected]>
Cc Marc Kleine-Budde <[email protected]>
Cc nicolas.ferre at atmel.com
Cc Marc Pignat <[email protected]>
Cc john.stultz at linaro.org
Cc kernel at pengutronix.de
Cc Ronald Wahl <[email protected]>
Cc u.kleine-koenig at pengutronix.de
Cc Ludovic Desroches <[email protected]>
---
 kernel/time/clockevents.c |   64 +++++++++++++++++++++++++++++++++++-----------
 1 file changed, 49 insertions(+), 15 deletions(-)
kernel/time/clockevents.c +49 -15
Index: linux-2.6/kernel/time/clockevents.c
===================================================================
@@ -33,29 +33,63 @@ struct ce_unbind {
 	int res;
 };
 
-/**
- * clockevents_delta2ns - Convert a latch value (device ticks) to nanoseconds
- * @latch:	value to convert
- * @evt:	pointer to clock event device descriptor
- *
- * Math helper, returns latch value converted to nanoseconds (bound checked)
- */
-u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
+static u64 cev_delta2ns(unsigned long latch, struct clock_event_device *evt,
+			bool ismax)
 {
 	u64 clc = (u64) latch << evt->shift;
+	u64 rnd = (u64) evt->mult - 1;
 
 	if (unlikely(!evt->mult)) {
 		evt->mult = 1;
 		WARN_ON(1);
 	}
 
+	/*
+	 * Upper bound sanity check. If the backwards conversion is
+	 * not equal latch, we know that the above shift overflowed.
+	 */
+	if (clc >> evt->shift) != (u64)latch)
+		clc = ~0ULL;
+
+	/*
+	 * Scaled math oddities:
+	 *
+	 * For mult <= (1 << shift) we can safely add mult - 1 to
+	 * prevent integer rounding loss. So the backwards conversion
+	 * from nsec to device ticks will be correct.
+	 *
+	 * For mult > (1 << shift), i.e. device frequency is > 1GHz we
+	 * need to be careful. Adding mult - 1 will result in a value
+	 * which when converted back to device ticks will be larger
+	 * than latch by (mult / (1 << shift)) - 1. For the min_delta
+	 * calculation we still want to apply this in order to stay
+	 * above the minimum device ticks limit. For the upper limit
+	 * we would end up with a latch value larger than the upper
+	 * limit of the device, so we omit the add to stay below the
+	 * device upper boundary.
+	 *
+	 * Also omit the add if it would overflow the u64 boundary.
+	 */
+	if ((~0ULL - clc > rnd) &&
+	    (!ismax || evt->mult <= (1U << evt->shift)))
+		clc += rnd;
+
 	do_div(clc, evt->mult);
-	if (clc < 1000)
-		clc = 1000;
-	if (clc > KTIME_MAX)
-		clc = KTIME_MAX;
 
-	return clc;
+	/* Deltas less than 1usec are pointless noise */
+	return clc > 1000 ? clc : 1000;
+}
+
+/**
+ * clockevents_delta2ns - Convert a latch value (device ticks) to nanoseconds
+ * @latch:	value to convert
+ * @evt:	pointer to clock event device descriptor
+ *
+ * Math helper, returns latch value converted to nanoseconds (bound checked)
+ */
+u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
+{
+	return cev_delta2ns(latch, evt, false);
 }
 EXPORT_SYMBOL_GPL(clockevent_delta2ns);
 
@@ -380,8 +414,8 @@ void clockevents_config(struct clock_eve
 		sec = 600;
 
 	clockevents_calc_mult_shift(dev, freq, sec);
-	dev->min_delta_ns = clockevent_delta2ns(dev->min_delta_ticks, dev);
-	dev->max_delta_ns = clockevent_delta2ns(dev->max_delta_ticks, dev);
+	dev->min_delta_ns = cev_delta2ns(dev->min_delta_ticks, dev, false);
+	dev->max_delta_ns = cev_delta2ns(dev->max_delta_ticks, dev, true);
 }
 
 /**
#18 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Hi Thomas,

Quoted 73 lines · Thomas Gleixner

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

The solution for the issue at hand is simple: adding evt->mult - 1 to the shifted value before the integer divison in the core conversion function takes care of it. But this only works for the case where for the scaled math mult/shift pair "mult <= 1 << shift" is true. For the case where "mult > 1 << shift" we can apply the rounding add only for the minimum delta value to make sure that the backward conversion is not less than the given hardware limit. For the upper bound we need to omit the rounding add, because the backwards conversion is always larger than the original latch value. That would violate the upper bound of the hardware device.

Though looking closer at the details of that function reveals another
bogosity: The upper bounds check is broken as well. Checking for a resulting "clc" value greater than KTIME_MAX after the conversion is pointless. The conversion does:

      u64 clc = (latch << evt->shift) / evt->mult;

So there is no sanity check for (latch << evt->shift) exceeding the 64bit boundary. The latch argument is "unsigned long", so on a 64bit arch the handed in argument could easily lead to an unnoticed shift overflow. With the above rounding fix applied the calculation before the divison is:

       u64 clc = (latch << evt->shift) + evt->mult - 1;

So we need to make sure, that neither the shift nor the rounding add is overflowing the u64 boundary.

Cc Russell King - ARM Linux <[email protected]>
Cc Marc Kleine-Budde <[email protected]>
Cc nicolas.ferre at atmel.com
Cc Marc Pignat <[email protected]>
Cc john.stultz at linaro.org
Cc kernel at pengutronix.de
Cc Ronald Wahl <[email protected]>
Cc u.kleine-koenig at pengutronix.de
Cc Ludovic Desroches <[email protected]>
---
 kernel/time/clockevents.c |   64 +++++++++++++++++++++++++++++++++++-----------
 1 file changed, 49 insertions(+), 15 deletions(-)

Index: linux-2.6/kernel/time/clockevents.c
===================================================================

kernel/time/clockevents.c +0 -8
@@ -33,29 +33,63 @@ struct ce_unbind {
 	int res;
 };
 
-/**
- * clockevents_delta2ns - Convert a latch value (device ticks) to nanoseconds
- * @latch:	value to convert
- * @evt:	pointer to clock event device descriptor
- *
- * Math helper, returns latch value converted to nanoseconds (bound checked)
- */
-u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)

kernel/time/clockevents.c struct ce_unbind { · line 45

Quoted 10 lines
kernel/time/clockevents.c +3 -0
+static u64 cev_delta2ns(unsigned long latch, struct clock_event_device *evt,
+			bool ismax)
 {
 	u64 clc = (u64) latch << evt->shift;
+	u64 rnd = (u64) evt->mult - 1;
 
 	if (unlikely(!evt->mult)) {
 		evt->mult = 1;
 		WARN_ON(1);
 	}

I suggest to move the assignment to rnd below this if block as it changes mult.

kernel/time/clockevents.c struct ce_unbind { · line 51

Quoted 6 lines
kernel/time/clockevents.c +5 -0
+	/*
+	 * Upper bound sanity check. If the backwards conversion is
+	 * not equal latch, we know that the above shift overflowed.
+	 */
+	if (clc >> evt->shift) != (u64)latch)

You didn't compile test, did you? Also the cast on the rhs isn't needed.

kernel/time/clockevents.c struct ce_unbind { · line 58

Quoted 7 lines
kernel/time/clockevents.c +7 -0
+		clc = ~0ULL;
+
+	/*
+	 * Scaled math oddities:
+	 *
+	 * For mult <= (1 << shift) we can safely add mult - 1 to
+	 * prevent integer rounding loss. So the backwards conversion

It doesn't prevent inexactness to add mult - 1. It (only) asserts that the ns2delta(delta2ns(latch)) >= latch instead of ... <= latch when not doing it.

kernel/time/clockevents.c struct ce_unbind { · line 63

Quoted 5 lines
kernel/time/clockevents.c +5 -0
+	 * from nsec to device ticks will be correct.
+	 *
+	 * For mult > (1 << shift), i.e. device frequency is > 1GHz we
+	 * need to be careful. Adding mult - 1 will result in a value
+	 * which when converted back to device ticks will be larger

s/will/can/

kernel/time/clockevents.c struct ce_unbind { · line 64

Quoted 1 line
kernel/time/clockevents.c +1 -0
+	 * than latch by (mult / (1 << shift)) - 1. For the min_delta

s/by/by up to/

kernel/time/clockevents.c struct ce_unbind { · line 75

Quoted 11 lines
kernel/time/clockevents.c +11 -0
+	 * calculation we still want to apply this in order to stay
+	 * above the minimum device ticks limit. For the upper limit
+	 * we would end up with a latch value larger than the upper
+	 * limit of the device, so we omit the add to stay below the
+	 * device upper boundary.
+	 *
+	 * Also omit the add if it would overflow the u64 boundary.
+	 */
+	if ((~0ULL - clc > rnd) &&
+	    (!ismax || evt->mult <= (1U << evt->shift)))
+		clc += rnd;

I would expect that

	if (!ismax)
		if (~0ULL - clc > rnd)
			clc += rnd;
		else
			clc = ~0ULL;

is enough (and a tad more exact in the presence of an overflow). I have to think about that though.

Quoted 12 lines
kernel/time/clockevents.c +5 -5
+
 	do_div(clc, evt->mult);
-	if (clc < 1000)
-		clc = 1000;
-	if (clc > KTIME_MAX)
-		clc = KTIME_MAX;
 
-	return clc;
+	/* Deltas less than 1usec are pointless noise */
+	return clc > 1000 ? clc : 1000;
+}
+

kernel/time/clockevents.c struct ce_unbind { · line 92

Quoted 10 lines
kernel/time/clockevents.c +10 -0
+/**
+ * clockevents_delta2ns - Convert a latch value (device ticks) to nanoseconds
+ * @latch:	value to convert
+ * @evt:	pointer to clock event device descriptor
+ *
+ * Math helper, returns latch value converted to nanoseconds (bound checked)
+ */
+u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
+{
+	return cev_delta2ns(latch, evt, false);

Hmm, I wonder if you need to be more clever in the general case. So you still may return a value > max_delta_ticks here if latch is big enough. But see below ...

kernel/time/clockevents.c void clockevents_config(struct clock_eve · line 418

Quoted 11 lines
kernel/time/clockevents.c +2 -2
 }
 EXPORT_SYMBOL_GPL(clockevent_delta2ns);
 
@@ -380,8 +414,8 @@ void clockevents_config(struct clock_eve
 		sec = 600;
 
 	clockevents_calc_mult_shift(dev, freq, sec);
-	dev->min_delta_ns = clockevent_delta2ns(dev->min_delta_ticks, dev);
-	dev->max_delta_ns = clockevent_delta2ns(dev->max_delta_ticks, dev);
+	dev->min_delta_ns = cev_delta2ns(dev->min_delta_ticks, dev, false);
+	dev->max_delta_ns = cev_delta2ns(dev->max_delta_ticks, dev, true);

Another improvement that came to my mind just now. For min_delta_ns you want to assert that it results in a value >= min_delta_ticks when converted back. For max_delta_ns you want ... value <= max_delta_ticks. What about the values in between? They for sure should land in [min_delta_ticks ... max_delta_ticks] when converted back and ideally should be most exact. The latter part would mean to add (rnd / 2) instead of rnd. I don't know yet how that would behave@the borders of the [min_delta_ns ... max_delta_ns] interval, but I think you still need to special-case that.

Best regards
Uwe

Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#19 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Quoted 8 lines · Uwe Kleine-K?nig
Quoted 6 lines

+ u64 rnd = (u64) evt->mult - 1;

      if (unlikely(!evt->mult)) {
              evt->mult = 1;
              WARN_ON(1);
      }

I suggest to move the assignment to rnd below this if block as it changes mult.

True.

kernel/time/clockevents.c struct ce_unbind { · line 51

Quoted 6 lines
kernel/time/clockevents.c +5 -0
+     /*
+      * Upper bound sanity check. If the backwards conversion is
+      * not equal latch, we know that the above shift overflowed.
+      */
+     if (clc >> evt->shift) != (u64)latch)

You didn't compile test, did you? Also the cast on the rhs isn't needed.

I did. I just missed to refresh the patch before sending it :)

Quoted 5 lines

kernel/time/clockevents.c struct ce_unbind { · line 58

Quoted 2 lines
kernel/time/clockevents.c +2 -0
+	 * For mult <= (1 << shift) we can safely add mult - 1 to
+	 * prevent integer rounding loss. So the backwards conversion

It doesn't prevent inexactness to add mult - 1. It (only) asserts that the ns2delta(delta2ns(latch)) >= latch instead of ... <= latch when not doing it.

For mult <= 1 << shift the conversion is always ending up with the same latch value.

Quoted 6 lines

kernel/time/clockevents.c struct ce_unbind { · line 63

Quoted 5 lines
kernel/time/clockevents.c +5 -0
+	 * from nsec to device ticks will be correct.
+	 *
+	 * For mult > (1 << shift), i.e. device frequency is > 1GHz we
+	 * need to be careful. Adding mult - 1 will result in a value
+	 * which when converted back to device ticks will be larger

s/will/can/

No, it will always be larger.

Quoted 16 lines

kernel/time/clockevents.c struct ce_unbind { · line 64

Quoted 1 line
kernel/time/clockevents.c +1 -0
+	 * than latch by (mult / (1 << shift)) - 1. For the min_delta

s/by/by up to/

kernel/time/clockevents.c struct ce_unbind { · line 75

Quoted 11 lines
kernel/time/clockevents.c +11 -0
+	 * calculation we still want to apply this in order to stay
+	 * above the minimum device ticks limit. For the upper limit
+	 * we would end up with a latch value larger than the upper
+	 * limit of the device, so we omit the add to stay below the
+	 * device upper boundary.
+	 *
+	 * Also omit the add if it would overflow the u64 boundary.
+	 */
+	if ((~0ULL - clc > rnd) &&
+	    (!ismax || evt->mult <= (1U << evt->shift)))
+		clc += rnd;

I would expect that

Quoted 8 lines
	if (!ismax)
		if (~0ULL - clc > rnd)
			clc += rnd;
		else
			clc = ~0ULL;

is enough (and a tad more exact in the presence of an overflow). I have to think about that though.

Errm.

1) We cannot add if we'd overflow

2) For mult <= 1 << shift it's always correct

3) for mult > 1 << shift we only apply it to the min value not the max

Quoted 6 lines

kernel/time/clockevents.c void clockevents_config(struct clock_eve · line 418

Quoted 5 lines
kernel/time/clockevents.c +2 -2
 	clockevents_calc_mult_shift(dev, freq, sec);
-	dev->min_delta_ns = clockevent_delta2ns(dev->min_delta_ticks, dev);
-	dev->max_delta_ns = clockevent_delta2ns(dev->max_delta_ticks, dev);
+	dev->min_delta_ns = cev_delta2ns(dev->min_delta_ticks, dev, false);
+	dev->max_delta_ns = cev_delta2ns(dev->max_delta_ticks, dev, true);

Another improvement that came to my mind just now. For min_delta_ns you

Quoted 8 lines

want to assert that it results in a value >= min_delta_ticks when converted back. For max_delta_ns you want ... value <= max_delta_ticks. What about the values in between? They for sure should land in [min_delta_ticks ... max_delta_ticks] when converted back and ideally should be most exact. The latter part would mean to add (rnd / 2) instead of rnd. I don't know yet how that would behave at the borders of the [min_delta_ns ... max_delta_ns] interval, but I think you still need to special-case that.

Again:

1) For mult <= 1 << shift the backwards conversion is always the same as the input value.

2) For mult > 1 << shift the backwards conversion of the min value is always > than the input value. And the backwards conversion of the max value is always < than the input value.

The values between that are completely uninteresting as the program_events code always converts from nsec to device ticks.

We clamp the delta between min_ns and max_ns. So due to the above any

min_ns <= delta <= max_ns

will after conversion fulfil

min_tick <= delta_tick <= max_tick

So what are you going to improve? Either the math works or it does not.

Thanks,

tglx

#20 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Hi Thomas,

Quoted 9 lines · Thomas Gleixner
Quoted 5 lines · Uwe Kleine-K?nig

kernel/time/clockevents.c struct ce_unbind { · line 58

Quoted 2 lines
kernel/time/clockevents.c +2 -0
+	 * For mult <= (1 << shift) we can safely add mult - 1 to
+	 * prevent integer rounding loss. So the backwards conversion

It doesn't prevent inexactness to add mult - 1. It (only) asserts that the ns2delta(delta2ns(latch)) >= latch instead of ... <= latch when not doing it.

For mult <= 1 << shift the conversion is always ending up with the same latch value.

Ah right, I missed that we're in the slow-clock-case.

Quoted 8 lines
Quoted 6 lines

kernel/time/clockevents.c struct ce_unbind { · line 63

Quoted 5 lines
kernel/time/clockevents.c +5 -0
+	 * from nsec to device ticks will be correct.
+	 *
+	 * For mult > (1 << shift), i.e. device frequency is > 1GHz we
+	 * need to be careful. Adding mult - 1 will result in a value
+	 * which when converted back to device ticks will be larger

s/will/can/

No, it will always be larger.

Hmm, consider a 1.25 GHz clock with shift = 2 and mult = 5. Then ns2clc(clc2ns(1000)) = 1000. So it's not always larger!
In the fast-clock-case we have:
With x << shift = n * mult - k for k in [0 .. mult-1] and an integer n:

	  ns2clc(clc2ns(x))
	= ns2clc(((x << shift) + mult - 1) / mult)
	= ((((x << shift) + mult - 1) / mult) * mult) >> shift
	= n * mult >> shift
	= ((x << shift) + k) >> shift
	= x + (k >> shift)

So ns2clc(clc2ns(x)) = x for all x > 0 that have

	k = mult - ((x << shift) - 1) % mult - 1 < 1 << shift

So my correction still stands.

Quoted 3 lines
Quoted 2 lines

kernel/time/clockevents.c struct ce_unbind { · line 64

Quoted 1 line
kernel/time/clockevents.c +1 -0
+	 * than latch by (mult / (1 << shift)) - 1. For the min_delta

s/by/by up to/

From the calculation above you can also see that this term is wrong. k

is smaller than mult (and there are values that realize k = mult - 1). So the converted back value can be larger than latch by up to (mult - 1) >> shift. This is zero for the slow-clock-case.

In the 1.25 GHz example above that means that the difference is up to 1, not 0 as your term would imply. 1004 is an example where the conversion to nano seconds and back to ticks results in a difference of 1.

Quoted 22 lines
Quoted 13 lines

kernel/time/clockevents.c struct ce_unbind { · line 75

Quoted 11 lines
kernel/time/clockevents.c +11 -0
+	 * calculation we still want to apply this in order to stay
+	 * above the minimum device ticks limit. For the upper limit
+	 * we would end up with a latch value larger than the upper
+	 * limit of the device, so we omit the add to stay below the
+	 * device upper boundary.
+	 *
+	 * Also omit the add if it would overflow the u64 boundary.
+	 */
+	if ((~0ULL - clc > rnd) &&
+	    (!ismax || evt->mult <= (1U << evt->shift)))
+		clc += rnd;

I would expect that

Quoted 8 lines
	if (!ismax)
		if (~0ULL - clc > rnd)
			clc += rnd;
		else
			clc = ~0ULL;

is enough (and a tad more exact in the presence of an overflow). I have to think about that though.

Quoted 7 lines

Errm.

1) We cannot add if we'd overflow

2) For mult <= 1 << shift it's always correct

3) for mult > 1 << shift we only apply it to the min value not the max

Yeah, I didn't say your code is wrong *here*. I just think that my easier (and so probably faster) code is good enough.

Quoted 29 lines
Quoted 6 lines

kernel/time/clockevents.c void clockevents_config(struct clock_eve · line 418

Quoted 5 lines
kernel/time/clockevents.c +2 -2
 	clockevents_calc_mult_shift(dev, freq, sec);
-	dev->min_delta_ns = clockevent_delta2ns(dev->min_delta_ticks, dev);
-	dev->max_delta_ns = clockevent_delta2ns(dev->max_delta_ticks, dev);
+	dev->min_delta_ns = cev_delta2ns(dev->min_delta_ticks, dev, false);
+	dev->max_delta_ns = cev_delta2ns(dev->max_delta_ticks, dev, true);

Another improvement that came to my mind just now. For min_delta_ns you

Quoted 8 lines

want to assert that it results in a value >= min_delta_ticks when converted back. For max_delta_ns you want ... value <= max_delta_ticks. What about the values in between? They for sure should land in [min_delta_ticks ... max_delta_ticks] when converted back and ideally should be most exact. The latter part would mean to add (rnd / 2) instead of rnd. I don't know yet how that would behave at the borders of the [min_delta_ns ... max_delta_ns] interval, but I think you still need to special-case that.

Again:

1) For mult <= 1 << shift the backwards conversion is always the same as the input value.

2) For mult > 1 << shift the backwards conversion of the min value is always > than the input value. And the backwards conversion of the max value is always < than the input value.

The values between that are completely uninteresting as the program_events code always converts from nsec to device ticks.

We clamp the delta between min_ns and max_ns. So due to the above any

Quoted 7 lines

min_ns <= delta <= max_ns

will after conversion fulfil

min_tick <= delta_tick <= max_tick

So what are you going to improve? Either the math works or it does not.

Right, my idea is nice, but useless.

So I suggest you resend your patch with the compile fix and the corrected comment and I will think about my suggestion to simplify the if condition independently as it's only a small runtime improvent and so not important enough to stop the correctness issue your patch is fixing.

Best regards and thanks for the nice discussion,
Uwe

Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#21 lore raw

Re: [PATCH] clockevents: Sanitize ticks to nsec conversion

Quoted 22 lines · Uwe Kleine-K?nig
Quoted 9 lines · Thomas Gleixner
Quoted 6 lines · Uwe Kleine-K?nig

kernel/time/clockevents.c struct ce_unbind { · line 63

Quoted 5 lines
kernel/time/clockevents.c +5 -0
+	 * from nsec to device ticks will be correct.
+	 *
+	 * For mult > (1 << shift), i.e. device frequency is > 1GHz we
+	 * need to be careful. Adding mult - 1 will result in a value
+	 * which when converted back to device ticks will be larger

s/will/can/

No, it will always be larger.

Hmm, consider a 1.25 GHz clock with shift = 2 and mult = 5. Then ns2clc(clc2ns(1000)) = 1000. So it's not always larger!
In the fast-clock-case we have:
With x << shift = n * mult - k for k in [0 .. mult-1] and an integer n:

	  ns2clc(clc2ns(x))
	= ns2clc(((x << shift) + mult - 1) / mult)
	= ((((x << shift) + mult - 1) / mult) * mult) >> shift
	= n * mult >> shift
	= ((x << shift) + k) >> shift
	= x + (k >> shift)
Quoted 5 lines

So ns2clc(clc2ns(x)) = x for all x > 0 that have

	k = mult - ((x << shift) - 1) % mult - 1 < 1 << shift

So my correction still stands.

Fair enough.

Quoted 8 lines
Quoted 5 lines

1) We cannot add if we'd overflow

2) For mult <= 1 << shift it's always correct

3) for mult > 1 << shift we only apply it to the min value not the max

Yeah, I didn't say your code is wrong *here*. I just think that my easier (and so probably faster) code is good enough.

Granted. I was stuck in the correctness discussion. So yeah, it does not matter if we steal 30 usec of maximum idle sleep time from a 32kHz clock. OTOH it does not matter much in the setup slow path to take another conditional. :)

Quoted 1 line

Best regards and thanks for the nice discussion,

Ditto! You saved me from actually sitting down and using the pencil to do the proper math.

Thanks,

tglx

#22 lore raw

PATCH v2 1/1 clockevents: Sanitize ticks to nsec conversion

In reply to Thomas Gleixner

From: Thomas Gleixner <[email protected]>

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

The solution for the issue at hand is simple: adding evt->mult - 1 to the shifted value before the integer divison in the core conversion function takes care of it. But this only works for the case where for the scaled math mult/shift pair "mult <= 1 << shift" is true. For the case where "mult > 1 << shift" we can apply the rounding add only for the minimum delta value to make sure that the backward conversion is not less than the given hardware limit. For the upper bound we need to omit the rounding add, because the backwards conversion is always larger than the original latch value. That would violate the upper bound of the hardware device.

Though looking closer@the details of that function reveals another
bogosity: The upper bounds check is broken as well. Checking for a resulting "clc" value greater than KTIME_MAX after the conversion is pointless. The conversion does:

      u64 clc = (latch << evt->shift) / evt->mult;

So there is no sanity check for (latch << evt->shift) exceeding the 64bit boundary. The latch argument is "unsigned long", so on a 64bit arch the handed in argument could easily lead to an unnoticed shift overflow. With the above rounding fix applied the calculation before the divison is:

       u64 clc = (latch << evt->shift) + evt->mult - 1;

So we need to make sure, that neither the shift nor the rounding add is overflowing the u64 boundary.

Cc Russell King - ARM Linux <[email protected]>
Cc Marc Kleine-Budde <[email protected]>
Cc nicolas.ferre at atmel.com
Cc Marc Pignat <[email protected]>
Cc john.stultz at linaro.org
Cc kernel at pengutronix.de
Cc Ronald Wahl <[email protected]>
Cc Ludovic Desroches <[email protected]>

[ukl: move assignment to rnd after eventually changing mult, fix build
issue and correct comment with the right math]

---
 kernel/time/clockevents.c | 65 ++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 50 insertions(+), 15 deletions(-)
kernel/time/clockevents.c +50 -15
index 38959c8..662c579 100644
@@ -33,29 +33,64 @@ struct ce_unbind {
 	int res;
 };
 
-/**
- * clockevents_delta2ns - Convert a latch value (device ticks) to nanoseconds
- * @latch:	value to convert
- * @evt:	pointer to clock event device descriptor
- *
- * Math helper, returns latch value converted to nanoseconds (bound checked)
- */
-u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
+static u64 cev_delta2ns(unsigned long latch, struct clock_event_device *evt,
+			bool ismax)
 {
 	u64 clc = (u64) latch << evt->shift;
+	u64 rnd;
 
 	if (unlikely(!evt->mult)) {
 		evt->mult = 1;
 		WARN_ON(1);
 	}
+	rnd = (u64) evt->mult - 1;
+
+	/*
+	 * Upper bound sanity check. If the backwards conversion is
+	 * not equal latch, we know that the above shift overflowed.
+	 */
+	if ((clc >> evt->shift) != (u64)latch)
+		clc = ~0ULL;
+
+	/*
+	 * Scaled math oddities:
+	 *
+	 * For mult <= (1 << shift) we can safely add mult - 1 to
+	 * prevent integer rounding loss. So the backwards conversion
+	 * from nsec to device ticks will be correct.
+	 *
+	 * For mult > (1 << shift), i.e. device frequency is > 1GHz we
+	 * need to be careful. Adding mult - 1 will result in a value
+	 * which when converted back to device ticks can be larger
+	 * than latch by up to (mult - 1) >> shift. For the min_delta
+	 * calculation we still want to apply this in order to stay
+	 * above the minimum device ticks limit. For the upper limit
+	 * we would end up with a latch value larger than the upper
+	 * limit of the device, so we omit the add to stay below the
+	 * device upper boundary.
+	 *
+	 * Also omit the add if it would overflow the u64 boundary.
+	 */
+	if ((~0ULL - clc > rnd) &&
+	    (!ismax || evt->mult <= (1U << evt->shift)))
+		clc += rnd;
 
 	do_div(clc, evt->mult);
-	if (clc < 1000)
-		clc = 1000;
-	if (clc > KTIME_MAX)
-		clc = KTIME_MAX;
 
-	return clc;
+	/* Deltas less than 1usec are pointless noise */
+	return clc > 1000 ? clc : 1000;
+}
+
+/**
+ * clockevents_delta2ns - Convert a latch value (device ticks) to nanoseconds
+ * @latch:	value to convert
+ * @evt:	pointer to clock event device descriptor
+ *
+ * Math helper, returns latch value converted to nanoseconds (bound checked)
+ */
+u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
+{
+	return cev_delta2ns(latch, evt, false);
 }
 EXPORT_SYMBOL_GPL(clockevent_delta2ns);
 
@@ -380,8 +415,8 @@ void clockevents_config(struct clock_event_device *dev, u32 freq)
 		sec = 600;
 
 	clockevents_calc_mult_shift(dev, freq, sec);
-	dev->min_delta_ns = clockevent_delta2ns(dev->min_delta_ticks, dev);
-	dev->max_delta_ns = clockevent_delta2ns(dev->max_delta_ticks, dev);
+	dev->min_delta_ns = cev_delta2ns(dev->min_delta_ticks, dev, false);
+	dev->max_delta_ns = cev_delta2ns(dev->max_delta_ticks, dev, true);
 }
 
 /**
Signature · 1 line
1.8.4.rc3
#23 lore raw

Timekeeping on at91rm9200 [Was: [PATCH v2] clockevents: Sanitize ticks to nsec conversion]

Hello Nicolas, hello Jean-Christophe,

I expect you should be able to revert

	b7a8ca5 (ARM: at91: rm9200 fix time support)

which reverted

838a2ae (ARM: use clockevents_config_and_register() where possible)

for at91rm9200 on top of the patch this mail is a reply to.

Can you please test that?

Best regards
Uwe

Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
Tested-by
#24 lore raw

Re: Timekeeping on at91rm9200 [Was: [PATCH v2] clockevents: Sanitize ticks to nsec conversion]

On 24/09/2013 23:11, Uwe Kleine-K?nig :

Quoted 6 lines

Hello Nicolas, hello Jean-Christophe,

I expect you should be able to revert

	b7a8ca5 (ARM: at91: rm9200 fix time support)
Quoted 7 lines

which reverted

838a2ae (ARM: use clockevents_config_and_register() where possible)

for at91rm9200 on top of the patch this mail is a reply to.

Can you please test that?

I have just tested that on at91rm9200-ek:
- revert the revert (!)
- experience the crash
- then apply the v2 patch
- and finally see it working nicely!

Thanks a lot for having corrected this. Now, do you want that I stack this revert-of-revert on the AT91 git tree or you are able to apply it through the clock git tree together with the patch that is fixing the issue (it may prevent synchronization difficulties)? (BTW, I do not see it yet in "next").

Anyway, if it is required, you can add my:

Thanks, bye,

Signature · 1 line
Nicolas Ferre
#25 lore raw

Re: [PATCH v2] clockevents: Sanitize ticks to nsec conversion

In reply to Uwe Kleine-König

Hello Thomas,

just found another little issue ...

kernel/time/clockevents.c struct ce_unbind { · line 91

Quoted 8 lines · Uwe Kleine-K?nig
kernel/time/clockevents.c +8 -0
+/**
+ * clockevents_delta2ns - Convert a latch value (device ticks) to nanoseconds
+ * @latch:	value to convert
+ * @evt:	pointer to clock event device descriptor
+ *
+ * Math helper, returns latch value converted to nanoseconds (bound checked)
+ */
+u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)

... the kernel-doc comment has an 's' too much in the function name.

I'm not sending a v3 for just that. Can you fix that up when/if applying?

Best regards
Uwe

Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#26 lore raw

Re: [PATCH v2] clockevents: Sanitize ticks to nsec conversion

In reply to Uwe Kleine-König
Quoted 53 lines · Uwe Kleine-K?nig

From: Thomas Gleixner <[email protected]>

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

The solution for the issue at hand is simple: adding evt->mult - 1 to the shifted value before the integer divison in the core conversion function takes care of it. But this only works for the case where for the scaled math mult/shift pair "mult <= 1 << shift" is true. For the case where "mult > 1 << shift" we can apply the rounding add only for the minimum delta value to make sure that the backward conversion is not less than the given hardware limit. For the upper bound we need to omit the rounding add, because the backwards conversion is always larger than the original latch value. That would violate the upper bound of the hardware device.

Though looking closer at the details of that function reveals another
bogosity: The upper bounds check is broken as well. Checking for a resulting "clc" value greater than KTIME_MAX after the conversion is pointless. The conversion does:

      u64 clc = (latch << evt->shift) / evt->mult;

So there is no sanity check for (latch << evt->shift) exceeding the 64bit boundary. The latch argument is "unsigned long", so on a 64bit arch the handed in argument could easily lead to an unnoticed shift overflow. With the above rounding fix applied the calculation before the divison is:

       u64 clc = (latch << evt->shift) + evt->mult - 1;

So we need to make sure, that neither the shift nor the rounding add is overflowing the u64 boundary.

Cc Russell King - ARM Linux <[email protected]>
Cc Marc Kleine-Budde <[email protected]>
Cc nicolas.ferre at atmel.com
Cc Marc Pignat <[email protected]>
Cc john.stultz at linaro.org
Cc kernel at pengutronix.de
Cc Ronald Wahl <[email protected]>
Cc Ludovic Desroches <[email protected]>
Quoted 3 lines

[ukl: move assignment to rnd after eventually changing mult, fix build
issue and correct comment with the right math]

What's the status of this patch?

Marc

Signature · 12 lines
Pengutronix e.K.                  | Marc Kleine-Budde           |
Industrial Linux Solutions        | Phone: +49-231-2826-924     |
Vertretung West/Dortmund          | Fax:   +49-5121-206917-5555 |
Amtsgericht Hildesheim, HRA 2686  | http://www.pengutronix.de   |

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 259 bytes
Desc: OpenPGP digital signature
URL: <http://lists.infradead.org/pipermail/linux-arm-kernel/attachments/20131008/e2dd9038/attachment.sig>
#27 lore raw

[GIT PULL] fixes for integer rounding in timer core (Was: [PATCH v2] clockevents: Sanitize ticks to nsec conversion)

Hello,

Quoted 1 line

What's the status of this patch?

I pinged Thomas about it already via irc, but I didn't get a response up to now. It would be great to get that into 3.12. To make it easy for Thomas, here is a pull request that includes the fix and converts at91rm9200 back to clockevents_config_and_register dropping one of the workarounds for the fixed bug.

The following changes since commit 4a10c2ac2f368583138b774ca41fac4207911983:

Linux 3.12-rc2 (2013-09-23 15:41:09 -0700)

are available in the git repository at:

git://git.pengutronix.de/git/ukl/linux.git tags/timer-for-tip

for you to fetch changes up to b58c4b70121070f45eefa739ecbb58d57da1c4d9:

ARM: at91: rm9200: switch back to clockevents_config_and_register (2013-10-08 16:58:22 +0200)

----------------------------------------------------------------
The first patch in this pull request fixes an old integer rounding bug in the timer core that was (and still is) worked around in a few arch's timer code. The second patch drops such a work around now that the core is fixed.

----------------------------------------------------------------
Thomas Gleixner (1):
clockevents: Sanitize ticks to nsec conversion

Uwe Kleine-K?nig (1):
ARM: at91: rm9200: switch back to clockevents_config_and_register

 arch/arm/mach-at91/at91rm9200_time.c |  7 ++--
 kernel/time/clockevents.c            | 65 +++++++++++++++++++++++++++---------
 2 files changed, 52 insertions(+), 20 deletions(-)
Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#28 lore raw

Re: [GIT PULL] fixes for integer rounding in timer core

Hello Linus, hello Ingo,

Quoted 15 lines · Uwe Kleine-K?nig
Quoted 1 line

What's the status of this patch?

I pinged Thomas about it already via irc, but I didn't get a response up to now. It would be great to get that into 3.12. To make it easy for Thomas, here is a pull request that includes the fix and converts at91rm9200 back to clockevents_config_and_register dropping one of the workarounds for the fixed bug.

The following changes since commit 4a10c2ac2f368583138b774ca41fac4207911983:

Linux 3.12-rc2 (2013-09-23 15:41:09 -0700)

are available in the git repository at:

git://git.pengutronix.de/git/ukl/linux.git tags/timer-for-tip

Quoted 8 lines

for you to fetch changes up to b58c4b70121070f45eefa739ecbb58d57da1c4d9:

ARM: at91: rm9200: switch back to clockevents_config_and_register (2013-10-08 16:58:22 +0200)

----------------------------------------------------------------
The first patch in this pull request fixes an old integer rounding bug in the timer core that was (and still is) worked around in a few arch's timer code. The second patch drops such a work around now that the core is fixed.

It would be nice to get that fix into 3.12, but Thomas stopped responding nearly a month ago---his last mail in this thread[1] dates back to September 20.

Can one of you please take it directly?

Thanks
Uwe

[1] http://thread.gmane.org/gmane.linux.kernel/1563370/

Quoted 20 lines

----------------------------------------------------------------
Thomas Gleixner (1):
clockevents: Sanitize ticks to nsec conversion

Uwe Kleine-K?nig (1):
ARM: at91: rm9200: switch back to clockevents_config_and_register

 arch/arm/mach-at91/at91rm9200_time.c |  7 ++--
 kernel/time/clockevents.c            | 65 +++++++++++++++++++++++++++---------
 2 files changed, 52 insertions(+), 20 deletions(-)
Signature · 7 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel
Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#29 lore raw

Re: [GIT PULL] fixes for integer rounding in timer core

On 14/10/2013 09:34, Uwe Kleine-K?nig :

Quoted 26 lines

Hello Linus, hello Ingo,

Quoted 15 lines · Uwe Kleine-K?nig
Quoted 1 line

What's the status of this patch?

I pinged Thomas about it already via irc, but I didn't get a response up to now. It would be great to get that into 3.12. To make it easy for Thomas, here is a pull request that includes the fix and converts at91rm9200 back to clockevents_config_and_register dropping one of the workarounds for the fixed bug.

The following changes since commit 4a10c2ac2f368583138b774ca41fac4207911983:

   Linux 3.12-rc2 (2013-09-23 15:41:09 -0700)

are available in the git repository at:

git://git.pengutronix.de/git/ukl/linux.git tags/timer-for-tip

Quoted 8 lines

for you to fetch changes up to b58c4b70121070f45eefa739ecbb58d57da1c4d9:

   ARM: at91: rm9200: switch back to clockevents_config_and_register (2013-10-08 16:58:22 +0200)

----------------------------------------------------------------
The first patch in this pull request fixes an old integer rounding bug in the timer core that was (and still is) worked around in a few arch's timer code. The second patch drops such a work around now that the core is fixed.

Quoted 5 lines

It would be nice to get that fix into 3.12, but Thomas stopped responding nearly a month ago---his last mail in this thread[1] dates back to September 20.

Can one of you please take it directly?

I second Uwe in his request (aka +1).

Thanks, bye,

Quoted 22 lines

[1] http://thread.gmane.org/gmane.linux.kernel/1563370/

Quoted 20 lines

----------------------------------------------------------------
Thomas Gleixner (1):
clockevents: Sanitize ticks to nsec conversion

Uwe Kleine-K?nig (1):
ARM: at91: rm9200: switch back to clockevents_config_and_register

  arch/arm/mach-at91/at91rm9200_time.c |  7 ++--
  kernel/time/clockevents.c            | 65 +++++++++++++++++++++++++++---------
  2 files changed, 52 insertions(+), 20 deletions(-)

--

Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |

_______________________________________________
linux-arm-kernel mailing list
linux-arm-kernel at lists.infradead.org
http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

Signature · 1 line
Nicolas Ferre
#30 lore raw

Re: [GIT PULL] fixes for integer rounding in timer core

In reply to Uwe Kleine-König

Hello,

[added Daniel Lezcano to To:]

Quoted 20 lines · Uwe Kleine-K?nig
Quoted 19 lines · Uwe Kleine-K?nig
Quoted 1 line

What's the status of this patch?

I pinged Thomas about it already via irc, but I didn't get a response up to now. It would be great to get that into 3.12. To make it easy for Thomas, here is a pull request that includes the fix and converts at91rm9200 back to clockevents_config_and_register dropping one of the workarounds for the fixed bug.

The following changes since commit 4a10c2ac2f368583138b774ca41fac4207911983:

Linux 3.12-rc2 (2013-09-23 15:41:09 -0700)

are available in the git repository at:

git://git.pengutronix.de/git/ukl/linux.git tags/timer-for-tip

for you to fetch changes up to b58c4b70121070f45eefa739ecbb58d57da1c4d9:

ARM: at91: rm9200: switch back to clockevents_config_and_register (2013-10-08 16:58:22 +0200)

Quoted 7 lines
Quoted 4 lines

----------------------------------------------------------------
The first patch in this pull request fixes an old integer rounding bug in the timer core that was (and still is) worked around in a few arch's timer code. The second patch drops such a work around now that the core is fixed.

It would be nice to get that fix into 3.12, but Thomas stopped responding nearly a month ago---his last mail in this thread[1] dates back to September 20.

Still no sign of life from Thomas.

Quoted 1 line

Can one of you please take it directly?

Daniel, would you care to take it?

Best regards
Uwe

Signature · 2 lines
Pengutronix e.K.                           | Uwe Kleine-K?nig            |
Industrial Linux Solutions                 | http://www.pengutronix.de/  |
#31 lore raw

Re: [GIT PULL] fixes for integer rounding in timer core

Quoted 12 lines · Uwe Kleine-K?nig

Hello,

[added Daniel Lezcano to To:]

Quoted 7 lines · Uwe Kleine-K?nig
Quoted 6 lines · Uwe Kleine-K?nig
Quoted 1 line

What's the status of this patch?

I pinged Thomas about it already via irc, but I didn't get a response up to now. It would be great to get that into 3.12. To make it easy for Thomas, here is a pull request that includes the fix and converts at91rm9200 back to clockevents_config_and_register dropping one of the workarounds for the fixed bug.

[ ... ]

Quoted 11 lines
Quoted 7 lines
Quoted 4 lines

----------------------------------------------------------------
The first patch in this pull request fixes an old integer rounding bug in the timer core that was (and still is) worked around in a few arch's timer code. The second patch drops such a work around now that the core is fixed.

It would be nice to get that fix into 3.12, but Thomas stopped responding nearly a month ago---his last mail in this thread[1] dates back to September 20.

Still no sign of life from Thomas.

Quoted 1 line

Can one of you please take it directly?

Daniel, would you care to take it?

Yes, sure.

-- Daniel

Signature · 5 lines
  <http://www.linaro.org/> Linaro.org ? Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog
#32 lore raw

[tip:timers/urgent] clockevents: Sanitize ticks to nsec conversion

In reply to Uwe Kleine-König
clockevents: Sanitize ticks to nsec conversion
Commit-ID:  97b9410643475d6557d2517c2aff9fd2221141a9
Gitweb:     http://git.kernel.org/tip/97b9410643475d6557d2517c2aff9fd2221141a9
Author:     Thomas Gleixner <[email protected]>
AuthorDate: Tue, 24 Sep 2013 21:50:23 +0200
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Wed, 23 Oct 2013 12:51:21 +0200

clockevents: Sanitize ticks to nsec conversion

Marc Kleine-Budde pointed out, that commit 77cc982 "clocksource: use clockevents_config_and_register() where possible" caused a regression for some of the converted subarchs.

The reason is, that the clockevents core code converts the minimal hardware tick delta to a nanosecond value for core internal usage. This conversion is affected by integer math rounding loss, so the backwards conversion to hardware ticks will likely result in a value which is less than the configured hardware limitation. The affected subarchs used their own workaround (SIGH!) which got lost in the conversion.

The solution for the issue at hand is simple: adding evt->mult - 1 to the shifted value before the integer divison in the core conversion function takes care of it. But this only works for the case where for the scaled math mult/shift pair "mult <= 1 << shift" is true. For the case where "mult > 1 << shift" we can apply the rounding add only for the minimum delta value to make sure that the backward conversion is not less than the given hardware limit. For the upper bound we need to omit the rounding add, because the backwards conversion is always larger than the original latch value. That would violate the upper bound of the hardware device.

Though looking closer at the details of that function reveals another
bogosity: The upper bounds check is broken as well. Checking for a resulting "clc" value greater than KTIME_MAX after the conversion is pointless. The conversion does:

      u64 clc = (latch << evt->shift) / evt->mult;

So there is no sanity check for (latch << evt->shift) exceeding the 64bit boundary. The latch argument is "unsigned long", so on a 64bit arch the handed in argument could easily lead to an unnoticed shift overflow. With the above rounding fix applied the calculation before the divison is:

       u64 clc = (latch << evt->shift) + evt->mult - 1;

So we need to make sure, that neither the shift nor the rounding add is overflowing the u64 boundary.

[ukl: move assignment to rnd after eventually changing mult, fix build
issue and correct comment with the right math]

---
 kernel/time/clockevents.c | 65 ++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 50 insertions(+), 15 deletions(-)
kernel/time/clockevents.c +50 -15
index 38959c8..662c579 100644
@@ -33,29 +33,64 @@ struct ce_unbind {
 	int res;
 };
 
-/**
- * clockevents_delta2ns - Convert a latch value (device ticks) to nanoseconds
- * @latch:	value to convert
- * @evt:	pointer to clock event device descriptor
- *
- * Math helper, returns latch value converted to nanoseconds (bound checked)
- */
-u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
+static u64 cev_delta2ns(unsigned long latch, struct clock_event_device *evt,
+			bool ismax)
 {
 	u64 clc = (u64) latch << evt->shift;
+	u64 rnd;
 
 	if (unlikely(!evt->mult)) {
 		evt->mult = 1;
 		WARN_ON(1);
 	}
+	rnd = (u64) evt->mult - 1;
+
+	/*
+	 * Upper bound sanity check. If the backwards conversion is
+	 * not equal latch, we know that the above shift overflowed.
+	 */
+	if ((clc >> evt->shift) != (u64)latch)
+		clc = ~0ULL;
+
+	/*
+	 * Scaled math oddities:
+	 *
+	 * For mult <= (1 << shift) we can safely add mult - 1 to
+	 * prevent integer rounding loss. So the backwards conversion
+	 * from nsec to device ticks will be correct.
+	 *
+	 * For mult > (1 << shift), i.e. device frequency is > 1GHz we
+	 * need to be careful. Adding mult - 1 will result in a value
+	 * which when converted back to device ticks can be larger
+	 * than latch by up to (mult - 1) >> shift. For the min_delta
+	 * calculation we still want to apply this in order to stay
+	 * above the minimum device ticks limit. For the upper limit
+	 * we would end up with a latch value larger than the upper
+	 * limit of the device, so we omit the add to stay below the
+	 * device upper boundary.
+	 *
+	 * Also omit the add if it would overflow the u64 boundary.
+	 */
+	if ((~0ULL - clc > rnd) &&
+	    (!ismax || evt->mult <= (1U << evt->shift)))
+		clc += rnd;
 
 	do_div(clc, evt->mult);
-	if (clc < 1000)
-		clc = 1000;
-	if (clc > KTIME_MAX)
-		clc = KTIME_MAX;
 
-	return clc;
+	/* Deltas less than 1usec are pointless noise */
+	return clc > 1000 ? clc : 1000;
+}
+
+/**
+ * clockevents_delta2ns - Convert a latch value (device ticks) to nanoseconds
+ * @latch:	value to convert
+ * @evt:	pointer to clock event device descriptor
+ *
+ * Math helper, returns latch value converted to nanoseconds (bound checked)
+ */
+u64 clockevent_delta2ns(unsigned long latch, struct clock_event_device *evt)
+{
+	return cev_delta2ns(latch, evt, false);
 }
 EXPORT_SYMBOL_GPL(clockevent_delta2ns);
 
@@ -380,8 +415,8 @@ void clockevents_config(struct clock_event_device *dev, u32 freq)
 		sec = 600;
 
 	clockevents_calc_mult_shift(dev, freq, sec);
-	dev->min_delta_ns = clockevent_delta2ns(dev->min_delta_ticks, dev);
-	dev->max_delta_ns = clockevent_delta2ns(dev->max_delta_ticks, dev);
+	dev->min_delta_ns = cev_delta2ns(dev->min_delta_ticks, dev, false);
+	dev->max_delta_ns = cev_delta2ns(dev->max_delta_ticks, dev, true);
 }
 
 /**