Guarantee udelay(N) spins at least N microseconds

Hello everyone,

This is take 2 of my tiny delay.c patch

Problem statement

When converting microseconds to timer cycles in __timer_udelay() and __timer_const_udelay(), the result is rounded down(*), which means the system will not spin as long as requested (specifically, between epsilon and 1 cycle shorter).

If I understand correctly, most drivers expect udelay(N) to spin for at least N ?s. Is that correct? In that use case, spinning less might introduce subtle heisenbugs.

Typical example

timer->freq = 90 kHz && HZ = 100
(thus UDELAY_MULT = 107374 && ticks_per_jiffy = 900)

udelay(10) => __timer_const_udelay(10*107374)

           => __timer_delay((1073740*900) >> 30)
           => __timer_delay(0)

So udelay(10) resolves to no delay at all.

(*) 2^41 / 10^6 = 2199023,255552
2199023 < 2^41 / 10^6
UDELAY_MULT = 2199023*HZ / 2^11 < 2^30*HZ / 10^6

cycles = N * UDELAY_MULT * freq/HZ / 2^30

       < N * 2^30*HZ / 10^6 * freq/HZ / 2^30
       < N / 10^6 * freq

Proposed fix

Since results are always rounded down, all we need is to increment the result by 1 to round it up.

Would someone ACK the patch below?

Regards.

Patch against 4.0-rc4

arch/arm/lib/delay.c +0 -0

index 312d43e..3cfbd07 100644

Hi,

Quoted 54 lines · Mason

Hello everyone,

This is take 2 of my tiny delay.c patch

Problem statement

When converting microseconds to timer cycles in __timer_udelay() and __timer_const_udelay(), the result is rounded down(*), which means the system will not spin as long as requested (specifically, between epsilon and 1 cycle shorter).

If I understand correctly, most drivers expect udelay(N) to spin for at least N ?s. Is that correct? In that use case, spinning less might introduce subtle heisenbugs.

Typical example

timer->freq = 90 kHz && HZ = 100
(thus UDELAY_MULT = 107374 && ticks_per_jiffy = 900)

udelay(10) => __timer_const_udelay(10*107374)

            => __timer_delay((1073740*900) >> 30)
            => __timer_delay(0)

So udelay(10) resolves to no delay at all.

(*) 2^41 / 10^6 = 2199023,255552
2199023 < 2^41 / 10^6
UDELAY_MULT = 2199023*HZ / 2^11 < 2^30*HZ / 10^6

cycles = N * UDELAY_MULT * freq/HZ / 2^30

        < N * 2^30*HZ / 10^6 * freq/HZ / 2^30
        < N / 10^6 * freq

Proposed fix

Since results are always rounded down, all we need is to increment the result by 1 to round it up.

Would someone ACK the patch below?

Regards.

Patch against 4.0-rc4

arch/arm/lib/delay.c +0 -0

index 312d43e..3cfbd07 100644

arch/arm/lib/delay.c static void __timer_const_udelay(unsigned long xloops) · line 70

Quoted 6 lines

arch/arm/lib/delay.c +1 -1

@@ -66,7 +66,7 @@ static void __timer_const_udelay(unsigned long xloops)
  {
         unsigned long long loops = xloops;
         loops *= arm_delay_ops.ticks_per_jiffy;
-       __timer_delay(loops >> UDELAY_SHIFT);
+       __timer_delay((loops >> UDELAY_SHIFT) + 1);
  }

If loops is a multiple of 2 ^ UDELAY_SHIFT, then your result is too high by one. The proper way to round by excess is the following :

     __timer_delay((loops + (1 << UDELAY_SHIFT) - 1) >> UDELAY_SHIFT);

That way it does +1 for every value of loop not an exact multiple of 2^UDELAY_SHIFT.

The important thing to realize is that xloops is already rounded down, because we use 2199023 as an approximation of 2^41 / 10^6.

Thus, even when 'loops' is a multiple of 2^30, we'll want to round up.

Illustration

timer->freq = 100*2^20 && HZ = 100
(thus UDELAY_MULT = 107374 && ticks_per_jiffy = 2^20)

Suppose udelay(512)
so we want to spin for 512 / 10^6 * 100*2^20 = 53687,0912 cycles i.e. 53688 cycles if we round up.

loops = 512 * 107374 * 2^20 = 53687 * 2^30

If we just add (2^30-1) before shifting by 30, the result comes out to 53687, but (loops >> 30) + 1 is closer to what we really want.

One might argue that the difference between 53687 and 53688 is lost in the noise and thus irrelevant. I can agree with that.

Which is why I chose the simpler

  __timer_delay((loops >> UDELAY_SHIFT) + 1);

over

  __timer_delay((loops + (1 << UDELAY_SHIFT) - 1) >> UDELAY_SHIFT);

Do you disagree with this logic?

If I understand correctly, most drivers expect udelay(N) to spin for at least N ?s. Is that correct? In that use case, spinning less might introduce subtle heisenbugs.

Typical example

timer->freq = 90 kHz && HZ = 100
(thus UDELAY_MULT = 107374 && ticks_per_jiffy = 900)

udelay(10) => __timer_const_udelay(10*107374)

           => __timer_delay((1073740*900) >> 30)
           => __timer_delay(0)

Quoted 3 lines · Mason

If I understand correctly, most drivers expect udelay(N) to spin for at least N ?s. Is that correct? In that use case, spinning less might introduce subtle heisenbugs.

We've never guaranteed this.

The fact is that udelay() can delay for _approximately_ the time you ask for - it might be slightly shorter, or it could be much longer than you expect.

On most UP implementations using the software loop it will typically be around 1% slower than requested.

Adding 1us to every delay is going to be very bad. Rather than doing that, why not arrange for the rounding error to be accommodated?

Quoted 5 lines · Russell King - ARM Linux

Quoted 3 lines · Mason

If I understand correctly, most drivers expect udelay(N) to spin for at least N ?s. Is that correct? In that use case, spinning less might introduce subtle heisenbugs.

Quoted 5 lines

We've never guaranteed this.

The fact is that udelay() can delay for _approximately_ the time you ask for - it might be slightly shorter, or it could be much longer than you expect.

OK, but asking for 10 ?s and spinning 0 is a problem, right?

Quoted 2 lines

On most UP implementations using the software loop it will typically be around 1% slower than requested.

Please correct any misconception, it seems to me that typical driver writers, reading "operation X takes 10 ?s to complete" will write udelay(10); (if they want to spin-wait)

Do you think they should take the inherent imprecision of loop-based delays into account, and add a small cushion to be safe?

Quoted 6 lines · Mason

Quoted 5 lines · Russell King - ARM Linux

Quoted 3 lines · Mason

If I understand correctly, most drivers expect udelay(N) to spin for at least N ?s. Is that correct? In that use case, spinning less might introduce subtle heisenbugs.

Quoted 7 lines

Quoted 5 lines

We've never guaranteed this.

The fact is that udelay() can delay for _approximately_ the time you ask for - it might be slightly shorter, or it could be much longer than you expect.

OK, but asking for 10 ?s and spinning 0 is a problem, right?

Potentially.

Quoted 6 lines

Quoted 2 lines

On most UP implementations using the software loop it will typically be around 1% slower than requested.

Please correct any misconception, it seems to me that typical driver writers, reading "operation X takes 10 ?s to complete" will write udelay(10); (if they want to spin-wait)

Arguments do not matter here, sorry. What I said above is the way it behaves, period. It's not for discussion.

It may interest you that I discussed this issue with Linus, and Linus also said that it _isn't_ a problem and it _isn't_ something we care to fix.

So, like it or not, we're stuck with udelay(10) being possible to delay by 9.99us instead of 10us.

Where the inaccuracy comes from is entirely down to the way we calculate loops_per_jiffy - this is the number of loop cycles between two timer interrupts - but this does _not_ take account of the time to execute a timer interrupt.

So, loops_per_jiffy is the number of loop cycles between two timer interrupts minus the time taken to service the timer interrupt.

And what this means is that udelay(n) where 'n' is less than the period between two timer interrupts /will/ be, and is /expected to be/ potentially shorter than the requested period.

There's no getting away from that, we can't estimate how long the timer interrupt takes to handle without the use of an external timer, and if we've got an external timer, we might as well use it for all delays.

Quoted 2 lines

Do you think they should take the inherent imprecision of loop-based delays into account, and add a small cushion to be safe?

No. See above. Not doing that. Live with it.

Fix the rounding errors if you wish, but do _not_ try to fix the "udelay() may return slightly earlier than requested" problem. I will not apply a patch to fix _that_ problem.

I appreciate (very much so) that you spend time replying to me, but I also sense a lot of animosity, and I don't know what I've done wrong to deserve it :-(

Quoted 3 lines

And what this means is that udelay(n) where 'n' is less than the period between two timer interrupts /will/ be, and is /expected to be/ potentially shorter than the requested period.

You've made it clear how loop-based delays are implemented; and also that loop-based delays are typically 1% shorter than requested. (Thanks for the overview, by the way.) Please note that I haven't touched to the loop-based code, I'm only discussing the timer-based code.

Quoted 3 lines

There's no getting away from that, we can't estimate how long the timer interrupt takes to handle without the use of an external timer, and if we've got an external timer, we might as well use it for all delays.

Exactly! And my patch only changes __timer_const_udelay() so again I'm not touching loop-based code.

Quoted 1 line

No. See above. Not doing that. Live with it.

Specifically, should a driver writer use

  udelay(101);

when his spec says to spin 100 ?s?

(Anyway, this is just a tangential question, as I digest the ins and outs of kernel and driver development.)

Quoted 3 lines · Mason

I appreciate (very much so) that you spend time replying to me, but I also sense a lot of animosity, and I don't know what I've done wrong to deserve it :-(

I'm putting the point across strongly because I really don't think there is an issue to be solved here.

Quoted 10 lines · Russell King - ARM Linux

Quoted 3 lines

And what this means is that udelay(n) where 'n' is less than the period between two timer interrupts /will/ be, and is /expected to be/ potentially shorter than the requested period.

You've made it clear how loop-based delays are implemented; and also that loop-based delays are typically 1% shorter than requested. (Thanks for the overview, by the way.) Please note that I haven't touched to the loop-based code, I'm only discussing the timer-based code.

1% is a figure I pulled out of the air. It really depends on the CPU instructions per cycle, and how much work is being done in the timer interrupt handler.

Quoted 4 lines

Quoted 3 lines

There's no getting away from that, we can't estimate how long the timer interrupt takes to handle without the use of an external timer, and if we've got an external timer, we might as well use it for all delays.

Quoted 2 lines

Exactly! And my patch only changes __timer_const_udelay() so again I'm not touching loop-based code.

What I'm trying to get through to you is that udelay() as a _whole_ does not provide a guarantee that it will wait for _at least_ the time you asked for. All that it does is provide an _approximate_ delay.

There is, however, an important difference between loop-based delays and timer-based delays; CPU frequencies typically fall in the 50-5000 MHz range, while timer frequencies typically span tens of kHz up to hundreds of MHz. For example, 90 kHz is sometimes provided in multimedia systems (MPEG TS).

Quoted 5 lines · Mason

There is, however, an important difference between loop-based delays and timer-based delays; CPU frequencies typically fall in the 50-5000 MHz range, while timer frequencies typically span tens of kHz up to hundreds of MHz. For example, 90 kHz is sometimes provided in multimedia systems (MPEG TS).

Why would you want to use such a slowly clocked counter for something which is supposed to be able to produce delays in the micro-second and potentially the nanosecond range?

get_cycles(), which is what the timer based delay is based upon, is supposed to be a _high resolution counter_, preferably running at the same kind of speeds as the CPU, though with a fixed clock rate. It most definitely is not supposed to be in the kHz range.

Quoted 7 lines · Russell King - ARM Linux

Quoted 5 lines · Mason

There is, however, an important difference between loop-based delays and timer-based delays; CPU frequencies typically fall in the 50-5000 MHz range, while timer frequencies typically span tens of kHz up to hundreds of MHz. For example, 90 kHz is sometimes provided in multimedia systems (MPEG TS).

Quoted 8 lines

Why would you want to use such a slowly clocked counter for something which is supposed to be able to produce delays in the micro-second and potentially the nanosecond range?

get_cycles(), which is what the timer based delay is based upon, is supposed to be a _high resolution counter_, preferably running at the same kind of speeds as the CPU, though with a fixed clock rate. It most definitely is not supposed to be in the kHz range.

If there's only a single fixed clock in the system, I'd use it for sched_clock, clocksource, and timer delay. Are there other options?

It was you who wrote some time ago: "Timers are preferred because of the problems with the software delay loop." (My system implements DVFS.)

It seems to me that a 90 kHz timer is still better than the jiffy counter, or am I mistaken again?

Quoted 4 lines · Mason

It was you who wrote some time ago: "Timers are preferred because of the problems with the software delay loop." (My system implements DVFS.)

Quoted 2 lines

It seems to me that a 90 kHz timer is still better than the jiffy counter, or am I mistaken again?

Given the choice of a 90kHz timer vs using a calibrated software delay loop, the software delay loop wins. I never envisioned that someone would be silly enough to think

that a 90kHz timer would somehow be suitable to replace a software delay loop calibrated against a timer.

Quoted 6 lines · Russell King - ARM Linux

Quoted 4 lines · Mason

It was you who wrote some time ago: "Timers are preferred because of the problems with the software delay loop." (My system implements DVFS.)

Quoted 6 lines

Quoted 2 lines

It seems to me that a 90 kHz timer is still better than the jiffy counter, or am I mistaken again?

Given the choice of a 90kHz timer vs using a calibrated software delay loop, the software delay loop wins. I never envisioned that someone would be silly enough to think

I'm full of surprises.

Quoted 2 lines

that a 90kHz timer would somehow be suitable to replace a software delay loop calibrated against a timer.

Only one message ago, you were arguing that loop-based delays could be up to 50% inaccurate. Thus, if one wanted to spin for 500 ?s, they'd have to request 1 ms just to be sure. An 11 ?s accuracy looks like a better deal to me, overall.

Add DVFS to the mix, and that 500 ?s loop-based delay turns into a 50 ?s delay when the other core decides to boost the cluster from 100 MHz to 1 GHz. And then drivers break randomly.

What this also means is that if you only have a 90kHz counter available, doing DVFS is also a stupid idea.