Tick count overflow

mdkendall wrote on Wednesday, February 08, 2012:

In the section describing the xTaskGetTickCount function, the FreeRTOS reference manual says:

The tick count will eventually overflow and return to zero. This will not effect the internal operation of the kernel for example, tasks will always block for the specified period even if the tick count overflows while the task is in the Blocked state. Overflows must however be considered by host applications if the application makes direct use of the tick count value.

It turns out that it is surprisingly easy to correctly do a comparison that will correctly handle wraparound, just by casting the unsigned tick counts to signed. In case it helps anyone else, below is the macro that I am using:

/*  Determine if time a is "after" time b.
 *  Times a and b are unsigned, but performing the comparison
 *  using signed arithmetic automatically handles wrapping.
 *  The disambiguation window is half the maximum value. */
#if (configUSE_16_BIT_TICKS == 1)
#define timeAfter(a,b)    (((int16_t)(a) - (int16_t)(b)) > 0)
#else
#define timeAfter(a,b)    (((int32_t)(a) - (int32_t)(b)) > 0)
#endif

richard_damon wrote on Wednesday, February 08, 2012:

This is sort of dangerous to do unless you KNOW that a and b occurred within 1 half of a wrapping period of each other. It would actually be a bit more correct to do it as (int16_t)(a-b) then ((int16_t)(a) - (int16_t(b))) as you invoke less opportunities for undefined behavior.

Basically your method is just saying the you are going to IGNORE the wrapping affect and assume that converting the difference in time stamps to signed is going to give the correct value.

rtel wrote on Wednesday, February 08, 2012:

I’m not following this.  What problem are you attempting to solve?

If a and b are unsigned numbers, and ( a + b ) < a, then you know it has overflowed.
Also, if a and b are unsigned times,  ( a - b ) will also be correct even when b has overflowed compared to a.

For example, using 8 bit numbers for ease, if you have two variables ucTimeBefore and ucTimeAfter, and ucTimeBefore is equal to 254 (two away from wrapping to zero), but ucTimeAfter occurs 5 ticks after ucTimeBefore, then ucTimeBefore will have wrapped around to equal 3.  Now, in 8 bit unsigned arithmetic, you have a time difference of ( ucTimeAfter - ucTimeBefore ) == ( 3 - 254 ) == 5 (because it underflows) == the right time difference.

I would have thought it easier to keep it unsigned.

Regards.

rtel wrote on Wednesday, February 08, 2012:

The above should say “then **ucTimeAfter **will have wrapped around to equal 3”.

Regards

mdkendall wrote on Wednesday, February 08, 2012:

The problem is to determine if one time is “after” another (not to find the difference between them).

The naive test is (a > b). That works until a overflows, but fails to give the desired answer if a has overflowed but b hasn’t.

If a is known to be after b then, using unsigned arithmetic, (a - b) does indeed give the correct time difference even if a has overflowed. But that’s not the question; the problem is to determine whether a is after b.

Essentially, (assuming 8-bit ticks for ease) we want a function that evaluates as true with the following arguments: (1,0), (2,1), (128,127), (255,254), (0,255); and false if the arguments are reversed.

The intended usage is situations such as:

alarm = timeNow() + SOME_SHORT_PERIOD;
...
// later, elsewhere
if (timeAfter(timeNow(), alarm)) do_something();

As noted, the disambiguation period is half the maximum tick value, i.e. the above example is safe if SOME_SHORT_PERIOD is less than 127 and the test happens soon/often enough. With a more realistic 32-bit tick these are straightforward conditions to meet.

A similar macro is used in the Linux Kernel (as time_after in jiffies.h)
http://kerneldox.net/d4/dce/jiffies_8h-source.html

Regards,
Matthew

rtel wrote on Wednesday, February 08, 2012:

If you don’t mind delving outside of the public API you might want to look at the vTaskSetTimeOutState() and xTaskCheckForTimeOut() functions.  These make use of the xNumOfOverflows variable that is maintained in the FreeRTOS kernel.  I think it might do what you want, or if nothing else, knowing about the xNumOfOverflows variable might help you.

Regards.

richard_damon wrote on Wednesday, February 08, 2012:

The Linux kernel can(sort of) get way with this as the tick is 32 (or 640 bits long. With a 16 bit tick, I find the loop around time short enough to make the 32768 tick limit dangerous.

For your use case, I find that the following is a much safer solution.

To set the alarm:

mark = timeNow();

to test the alarm:

if(timeNow() - mark > SOME_SHORT_PERIOD) do_something()

This almost doubles the time that needs to pass before you get a wrong result, and drastically shortens the period when you get the wrong result to SOME_SHORT_PERIOD rather than 1/2 the full tick cycle period.

mdkendall wrote on Wednesday, February 08, 2012:

I would rather stay within the public API, but it is interesting that xNumOfOverflows exists.

… This almost doubles the time that needs to pass before you get a wrong result, and drastically shortens the period when you get the wrong result to SOME_SHORT_PERIOD rather than 1/2 the full tick cycle period.

Thanks, that’s an interesting observation.

davidbrown wrote on Thursday, February 09, 2012:

One thing that is missing from this discussion is to understand that signed integer overflow and wrap is undefined in C.  Usually it works as you expect, but not always - and the compiler can take advantage of the undefined behaviour (according to C standards) to generate smaller and faster code, even though it does not work as you expect.  So if you are going to define macros like timeAfter, then do it right.

To make the types clearer, use “static inline” functions rather than function-like macros.  I know FreeRTOS has to work even on some horrible dinosaur compilers that can’t handle “static inline” functions, and therefore still uses outdated macro styles, but we’ll ignore that here.

The suggestion from the OP was:

static inline bool badTimeAfter(uint16_t a, uint16_t b) {
  return (((int16_t)(a) - (int16_t)(b)) > 0);
}

This code looks fine - as long as you call it with “a” and “b” less than half a period apart, it will give the right answer.

However, sometimes it can go wrong.  To take a simple example, supposing you call badTimeAfter(0, b)  But the compiler can see that “a” is fixed at zero.  It knows that “b” is unsigned, and therefore by definition >= 0.  So (int16_t)(b) is therefore also >= 0, since signed integer overflow is undefined - either “b” is in range and the value is correct, or it is out of range and the result is undefined, and the compiler can therefore assume anything it likes about the result.  Since (int16_t)(b) is >= 0, the compiler can optimise away the entire function with a fixed result “false”.  That is certainly not the result you would expect if “b” happened to have it’s MSB set (i.e., it represents a negative number).  But the compiler is correct here - the source code is wrong.

When you want to rely on overflows and wraparound, you must use unsigned arithmetic - this is defined explicitly as twos-complement arithmetic. 

At first glance, you might think we can do the arithmetic in unsigned, then cast the result to signed for the comparison with 0:

static inline bool bad2TimeAfter(uint16_t a, uint16_t b) {
  return ( (int16_t)(a - b) > 0 );
}

That too has a flaw.  Since (a -b) is unsigned, it is always >= 0 - if the compiler can figure out that it is non-zero, then it can optimise the function to being always true.

One way to handle unsigned to signed conversions that avoids the risk of undefined behaviour is to use type punning with unions (strictly speaking, this is also undefined behaviour according to the C standards - but there is an unwritten rule that all C compilers define type punning to work as expected):

static inline bool goodTimeAfter(uint16_t a, uint16_t b) {
  union { uint16_t u; int16_t s } us;
  us.u = (a - b);
  return (us.s > 0);
}

Of course, that might miss out on the optimiser’s conversion between “> 0” and “< 0” ("< 0" is usually faster to execute), so you might want to write:

static inline bool goodTimeAfter(uint16_t a, uint16_t b) {
  union { uint16_t u; int16_t s } us;
  us.u = (b - a);
  return (us.s < 0);
}

If you want to avoid type punning (maybe your compiler does something horrible here, like putting the union on the stack), you can stick to unsigned all the way:

static inline bool goodTimeAfter(uint16_t a, uint16_t b) {
  uint16_t u  = (b - a);
  return (u & 0x8000u);
}

rtel wrote on Thursday, February 09, 2012:

Wow - thanks for your valuable contribution.

The FreeRTOS coding standard doesn’t allow unions ;o)  - yes I know they are using in a couple of the heap implementations but the union is not actually used, it is just there to force alignment without adding any extra byte of RAM.

As an aside, the time difference an overflow behaviour in FreeRTOS has been tested to an extraordinary length by various people, including the SafeRTOS development.  davidbrown is adding another dimension here and showing that the tests should be executed at all compiler optimisation levels - normally only the highest and lowest is used.  This does not effect SafeRTOS as such because the testing there is done with the compiler set exactly as the final build will use it - and any deviation invalidates testing anyway (in other words, by definition the tests will fail before they are even run).

Regards.

mdkendall wrote on Thursday, February 09, 2012:

Excellent discussion, thank you.

richard_damon wrote on Friday, February 10, 2012:

Richard,
The FreeRTOS kernel doesn’t run into the roll around problem because I beleive  it uses an == test for the future time mark, and that code is guaranteed to be called for every tick passing. User task code has a bit more of an issue as it can’t be sure it will run every tick without other promises. If it knows that it will be run “frequently” than it can use the inequality and be fairly safe. It is the infrequently run task that has to be more worried about th issue.

David, the union hack is just as much (if not more) undefined behavior as the unsigned to signed cast, and there is just as much public pressure for compilers to “get it right” as for the union. A compiler that assumed an unsigned cast to the same sized signed type was alway positive would be considered broken, even if it could justify such behavior based on the standard.

rtel wrote on Friday, February 10, 2012:

The FreeRTOS kernel doesn’t run into the roll around problem because I beleive  it uses an == test for the future time mark

In most places that is true.  The only time the “off API” functions are used is in working out whether a task that was blocked on a queue waiting for an event (say something being posted to the queue) unblocks, but then finds the queue empty again when it actually gets processing time to read the queue (something else may have removed the item).  This is by far and away the most complex part of the kernel (and something that most kernels get wrong but then claim to be faster) because the tick count could have overflowed at any time between the task originally going to sleep, the many times it may unblock only to find it has to go back to sleep, and the eventual time that is should timeout if there is nothing in the queue.

Regards.

yuantuh wrote on Sunday, October 28, 2012:

static inline bool goodTimeAfter(uint16_t a, uint16_t b) {
  uint16_t u  = (b - a);
  return (u & 0x8000u);
}

May use “return (a<b) ? false: true”?

freertosguru wrote on Friday, May 10, 2013:

Coudlnt you just do this ;
???

		//save the old tick
		Tick_old = Tick_new;
		//get new tick
		Tick_new = xTaskGetTickCount();
		
		//Get number of tiks since last
		if(Tick_new > Tick_old)
		{
			Ticks = Tick_new - Tick_old;
		}
		else
		{
			//recover from roll over
			Ticks = MAXVAL - Tick_old;
			Ticks += Tick_new;
		}

richard_damon wrote on Friday, May 10, 2013:

If all math is done on portTickType, Tick_new - Tick_old will be the time difference modulus the roll over period (which is too big to be represented by portTickType), this is the nature of unsigned arithmetic in C.

In your code above you really need to use MAXVAL+1, as this is how much time was lost in the roll over, but it turns out that the value of MAXVAL+1 will be 0 (due to rollover) so the two branches of the if do the same calculation.