Correct timing by timer + overflow count

[igendel]

Hi all,

This is more of an MCU programming question, that was mentioned in Jack Ganssle's latest newsletter. He presented the naive way of measuring time beyond a timer's bit-size limit: whenever the timer overflows, in the overflow interrupt, you increase a separate variable. Then, when you need to know the time, you take that variable and the current timer value, and do the math. 

Jack said this usually works but is guaranteed to fail eventually. I assume that's because between the time you access the variable and the time you access the timer value, an overflow may occur and the overall result will be false. 

This issue was actually presented as sort of an advertisement to one of Jack's seminars, so I hope I don't harm his business by asking this here  - how does one overcome the problem?

It seems to me that the only really safe way is to halt the timer itself right before the reading. However, this pause will interfere with the accuracy of the timing, unless I do exact cycle-counting on the process (or activate a separate timer just for that) and add the missing time to the timer afterwards. This doesn't feel very elegant.

So, is there a better way?

Thanks!

[Jeroen3]

You'll need a capture time (on that stops by hardware) otherwise your extra bit hack will have interrupt jitter.
But, an RTOS might make the jitter predictable. Which gives an known error you can put on your spec sheet.

https://en.wikipedia.org/wiki/Interrupt_latency

[Psi]

Use a stm32 and enable hardware master/slave over all of the timers

That's like 6x 16bit timers and one 32bit timer

A 128 bit counter at 48mhz overflows after 7,089,215,977,519,551,322,153,637,654,828 seconds

[Chris C]

1) Disable the timer interrupt (preferably all interrupts, so we can execute the following in a predictably timely fashion).
2) Get a copy of the timer value and the overflow count.
3) Check the interrupt flag.  If set, then we know we have to add one to our copy of the overflow count, since the interrupt hasn't yet been able to do it.  The timer value is where uncertainly creeps in, as we don't know if the value overflowed prior to, or after, previously copying its value - and if it was at 999 of 1,000, adding another 1,000 via the overflow count would give us an incorrect result.  But we know for certain it's overflowed NOW!  So copy the timer value again, problem solved.
4) Re-enable interrupts.
5) Use the copy of value and overflow count to calculate our final time.

I figured this out on my own, the first time I encountered this problem.  There may be other ways to do it.  Jack has no monopoly on the solution.

[igendel]

3) Check the interrupt flag.  If set, then we know we have to add one to our copy of the overflow count, since the interrupt hasn't yet been able to do it.  The timer value is where uncertainly creeps in, as we don't know if the value overflowed prior to, or after, previously copying its value - and if it was at 999 of 1,000, adding another 1,000 via the overflow count would give us an incorrect result.  But we know for certain it's overflowed NOW!  So copy the timer value again, problem solved.

Yes! That last step, of re-reading the timer value if the interrupt flag is set, is what I missed in my attempt to solve this earlier. Thanks!

[Chris C]

Here's an alternate solution.  It doesn't require disabling interrupts.  But does require a long enough timer interval, and short enough interrupts, that the following can ALWAYS run to completion in half the interval.  If you cannot guarantee that, it's fallible, which is why I usually use the prior approach.

1) Get a copy of the timer value (V1) and the overflow count (OC).
2) Get another, separate copy of the timer value (V2).  If V2 < V1, then resolve ambiguity by setting V1=V2, and getting OC again.
3) Compute time based on V1 and OC.

[hamster_nz]

Old-timer timer trick from 8-bit days for accessing long timers through small registers was to read the least most significant word(s) then least significant word, then read the most significant word again. If the most significant word changes you've sampled it during a roll-over, so repeat reading the least significant and most significant words again. The most significant word should be stable. Worst case is you'll stall for a few a handful of instructions.

If you do have to reread the registers you can roll take a few counts off the value to make allowance for the extra instruction cycles it took.

[igendel]

Use a stm32 and master/slave all of the timers to each other

That's like 6x 16bit timers and one 32bit timer

A 128 bit counter at 48mhz overflows after 7,089,215,977,519,551,322,153,637,654,828 seconds

Quite safe for everyday use, I guess, but if I want my system to outlast the universe, there may still be an issue 

I actually got a cheap STM32 board lately and a programmer for it, but proper documentation for beginners seems hard to find. I guess I'll have to do some serious datasheet reading.


Thanks Chris C and hmaster_nz for the other suggestion. It sounds reasonable too 

Edit: Oh, and thanks Jeroen3, however I currently don't work with RTOSs.

[ralphd]

This is pretty basic. Just disable interrupts while accessing the counter in RAM.  The timer still keeps running without any skew getting added.
I posted some example code to do this on an AVR last year.
http://nerdralph.blogspot.ca/2014/07/writing-avr-interrupt-service-routines.html

[igendel]

This is pretty basic. Just disable interrupts while accessing the counter in RAM.  The timer still keeps running without any skew getting

No, if I understand you correctly, that doesn't solve the problem Ganssle was talking about.

Let's say the timer is 8-bit. To get the time, I read it, disable interrupts, read the counter in RAM etc.
Now suppose I caught the timer when it was 255, one nanosecond before it overflowed. There is a possibility, I think, that the overflow interrupt will trip before my "main" code gets the chance to disable it. So it runs, the counter is +1'ed, timer now 0, and only then I get to disable the interrupt and read the (updated) counter. So I get the new RAM value but the old timer value, and that's a bug.

Same if I read the RAM counter first and the timer later.

[Brutte]

I have asked a more generic question on avrfreaks some time ago.
By contrast, I was not interested in extending one timer register but rather whole timer.
I have found that implementations can be categorized in terms of "permissible delays" and range from "ridiculous" up to "timer period".
All (not buggy) extensions require runtime resolution of events which is PITA but doable. An example for resolution of only two events for AVR8 is available on the linked page.

This is pretty basic.

That is neither pretty nor basic.

[Chris C]

By contrast, I was not interested in extending one timer register but rather whole timer.

Virtual timers could accurately be called the heart of my custom PIC programming environment.

It takes a single real timer, and expands it to up to 16 virtual timers; with up to 32-bit resolution, regardless of what the real timer is.  It's bug-free, lean, can defer its own maintenance tasks in order to not delay an imminent event, and emulates interrupt chaining even if the MCU lacks that feature.  Glitchless PWM is built-in.  So is MIBAM, which can make every pin on an MCU capable of LED dimming, regardless of the number of pins, for about 5% CPU utilization.

Other functions can be hard coded in, or provided via a virtual interrupt (callback).  If any function will run too long, it can use what I call a "bridge" to pass data down to a lower priority interrupt; which does the real processing, and no longer interferes with other virtual timers.

It can be used to poll pins to implement virtual external interrupts, frequency counters, duty cycle measurement, quadrature decoding, and so on.  That obviously requires a trade-off between poll rate and CPU utilization, but it's still handy.  I can partially port my environment to a new MCU, and add native hardware support for these functions when it actually becomes necessary, or at my leisure.  And after that, I can still use it to extend what hardware peripherals are there, using hardware for the most demanding tasks, and software for the least.

And it can produce "0-tick error" when generating a single, larger timer.  Though I'm not sure how often that would actually be useful.  I feel that would usually be better addressed by starting with at least a 16-bit MCU in the first place.

It seems your search for prior art was limited to a single forum, and probably also too narrow in looking specifically for a timer extension.  You'll have better luck by Googling for finished and tested interrupt-driven software PWM implementations.  Which seem to be more common.  And if you think about it, they are nothing but virtual timers being used for a single purpose. 

Still, it seems relatively few people attempt anything of this nature.  Or get it right on the first try.  So by all means, publish your project!

[ralphd]

This is pretty basic. Just disable interrupts while accessing the counter in RAM.  The timer still keeps running without any skew getting

No, if I understand you correctly, that doesn't solve the problem Ganssle was talking about.

Let's say the timer is 8-bit. To get the time, I read it, disable interrupts, read the counter in RAM etc.
Now suppose I caught the timer when it was 255, one nanosecond before it overflowed. There is a possibility, I think, that the overflow interrupt will trip before my "main" code gets the chance to disable it. So it runs, the counter is +1'ed, timer now 0, and only then I get to disable the interrupt and read the (updated) counter. So I get the new RAM value but the old timer value, and that's a bug.

Same if I read the RAM counter first and the timer later.

You obviously didn't look at my code and I'm guessing you didn't even read the whole blog post that explains the code.
The getseconds() function is only a few lines of C.
Now if you need a microsecond-resolution timer things get a bit more complicated, but you never said that is a requirement.

[Jeroen3]

Still, it seems relatively few people attempt anything of this nature.  Or get it right on the first try.  So by all means, publish your project!

Virtual timers are often included in operating systems, few people have time to roll their own.

[igendel]

You obviously didn't look at my code and I'm guessing you didn't even read the whole blog post that explains the code.
The getseconds() function is only a few lines of C.
Now if you need a microsecond-resolution timer things get a bit more complicated, but you never said that is a requirement.

It might be my own daftness, but even now after re-reading the post you linked to, I don't see how it relates to the very specific issue I raised in the original post.

[Brutte]

Virtual timers could accurately be called the heart of my custom PIC programming environment.

That was not the subject of the Muse.

You'll have better luck by Googling for finished and tested interrupt-driven software PWM implementations. 

Nor software PWM.
As stated before:

all implementations can be categorized in terms of "permissible delays" and range from "ridiculous" up to "timer period".

the software PWM falls into "ridiculous" category because to obtain a "0-tick error" you would have to pinpoint toggling code in exact instruction clock.

Still, it seems relatively few people attempt anything of this nature.  Or get it right on the first try.  So by all means, publish your project!

I have already abandoned that sinking ship.

[ralphd]

You obviously didn't look at my code and I'm guessing you didn't even read the whole blog post that explains the code.
The getseconds() function is only a few lines of C.
Now if you need a microsecond-resolution timer things get a bit more complicated, but you never said that is a requirement.

It might be my own daftness, but even now after re-reading the post you linked to, I don't see how it relates to the very specific issue I raised in the original post.

My solution provides a glitch-free timer.  Isn't that what you want?
If you want to do it the more complicated way, reading the timer register and combining it with the overflow count, it's a bit more code, but still not rocket science.  After cli(), if the overflow interrupt flag is set and the timer register value is < 128 then add 1 to the overflow value.

[igendel]

My solution provides a glitch-free timer.  Isn't that what you want?

As a by-product, perhaps. My original question was about the technique of counting time specifically using overflow counting + timer value.

If you want to do it the more complicated way, reading the timer register and combining it with the overflow count, it's a bit more code, but still not rocket science.  After cli(), if the overflow interrupt flag is set and the timer register value is < 128 then add 1 to the overflow value.

Yes, in the vein of some answers given above. It all boils down to checking, in retrospect, whether an overflow occurred while I was "taking time";  the exact details of the implementation seem to be a matter of taste and resource constraints. Thanks!

[hamster_nz]

My solution provides a glitch-free timer.  Isn't that what you want?
If you want to do it the more complicated way, reading the timer register and combining it with the overflow count, it's a bit more code, but still not rocket science.  After cli(), if the overflow interrupt flag is set and the timer register value is < 128 then add 1 to the overflow value.

I didn't read your code, but based on the description "This is pretty basic. Just disable interrupts while accessing the counter in RAM.  The timer still keeps running without any skew getting added" are you sure that it is glitch free?

Right column is RAM_Counter:Timer Counter for a 16 bit counter, left column is the instructions being run....

0000:FFFF disable interrupts
0000:FFFF read timer.   Gives xxxx:FFFFF for timer value (the upper half comes from RAM)
 --- timer rolls over here ---
0000:0000 read RAM  - GIves 0000:FFFF for timer value
0000:0000 check timer's IRQ flag = true
0000:0000 enable interrupts
-- IRQ happens --
0001:0000 IRQ flag is set, so inc reading from RAM (0000:FFFF => 00001:FFFF)

Or how about:

0000:FFFF disable interrupts
0000:0000 read timer.   Gives xxxx:FFFF for timer value (the upper half comes from RAM)
0000:0000 read RAM  - GIves 0000:FFFF for timer value
 --- timer rolls over here ---
0000:0000 check timer's IRQ flag = true
0000:0000 enable interrupts
-- IRQ happens --
0001:0000 IRQ flag is set, so inc reading from RAM (0000:FFFF => 00001:FFFF)

I guess you are now about to suggest that if an IRQ was flagged you look at the value from the h/w timer, and decide if the IRQ was raised before of after the timer was read (based on the high bit).

Why not just keep it simple...

   read RAM value into reg1
   read H/W timer into reg2
   read RAM value into reg3
   if reg3 != reg1
      clear reg2 to zero
   use reg3:reg2 as timer value

You don't even need to disable interrupts...

[ralphd]

If you want to do it the more complicated way, reading the timer register and combining it with the overflow count, it's a bit more code, but still not rocket science.  After cli(), if the overflow interrupt flag is set and the timer register value is < 128 then add 1 to the overflow value.

Yes, in the vein of some answers given above. It all boils down to checking, in retrospect, whether an overflow occurred while I was "taking time";  the exact details of the implementation seem to be a matter of taste and resource constraints. Thanks!

I can only think of one way to do it, and it is straightforward enough that I doubt there's a better way: (code tested only in my head)

Code: [Select]

__uint24 get_ticks()
{
  uint16_t ovfl;
  uint8_t timerval;
  cli();
  ovfl = _overflows;
  timerval = TCNT0;
  if ( (TIFR0 & (1<<TOV0)) && (timerval < 128) ) ovfl++;
  sei();
  return ( (ovfl << 8) | timerval );
}


[nctnico]

This is pretty basic. Just disable interrupts while accessing the counter in RAM.  The timer still keeps running without any skew getting

No, if I understand you correctly, that doesn't solve the problem Ganssle was talking about.

Let's say the timer is 8-bit. To get the time, I read it, disable interrupts, read the counter in RAM etc.
Now suppose I caught the timer when it was 255, one nanosecond before it overflowed. There is a possibility, I think, that the overflow interrupt will trip before my "main" code gets the chance to disable it. So it runs, the counter is +1'ed, timer now 0, and only then I get to disable the interrupt and read the (updated) counter. So I get the new RAM value but the old timer value, and that's a bug.

Same if I read the RAM counter first and the timer later.

Interesting problem... The timer interrupt adds extra difficulties due to parallel process synchronisation. It is not a particular timer problem but a process synchronisation problem. If you don't use a timer interrupt but just poll the counter from a main loop you can create a global time counter in a very simple way. Every time you read a value from the counter which is less than the previous value an overflow has occured. If you need the instant time just call the routine which determines the time. The only requirement is that the counter is polled often enough so that an overflow do not happen unnoticed.

[igendel]

I can only think of one way to do it, and it is straightforward enough that I doubt there's a better way: (code tested only in my head)

Code: [Select]

__uint24 get_ticks()
{
  uint16_t ovfl;
  uint8_t timerval;
  cli();
  ovfl = _overflows;
  timerval = TCNT0;
  if ( (TIFR0 & (1<<TOV0)) && (timerval < 128) ) ovfl++;
  sei();
  return ( (ovfl << 8) | timerval );
}


Why do you check whether timerval < 128?

[mikerj]

Why do you check whether timerval < 128?

Think about what would happen if the overflow occurred after TCNT0 had been read.

[igendel]

Why do you check whether timerval < 128?

Think about what would happen if the overflow occurred after TCNT0 had been read.

Actually that's another bug in the code above. If the OF flag is raised, it should re-read TCNT0 to get its updated value, not just increase the overflow count. This has nothing to do with the number 128. [edit: perhaps no need to re-read TCNT0, but the 128 check is still redundant]

[ralphd]

Why do you check whether timerval < 128?

Think about what would happen if the overflow occurred after TCNT0 had been read.

Actually that's another bug in the code above. If the OF flag is raised, it should re-read TCNT0 to get its updated value, not just increase the overflow count. This has nothing to do with the number 128. [edit: perhaps no need to re-read TCNT0, but the 128 check is still redundant]

Sounds like it is rocket science to you.