Time overflow and integer precision

[ThomasHornschuh]

The time value in HeliOS is defined as unsigned long, which most likely will be 32 Bit on typical embedded platforms.

With a time resolution of one microsecond it will "wrap around" (start over from zero...) after ~4295 seconds which is not much longer than one hour. To have a practical use of HeliOS the effects of timer overflow have to be mitigated. Not sure if this is handled in the code , I quick review shows this line in HeliOS.c:

 if (NOW() - waitingTask[i]->timerStartTime > waitingTask[i]->timerInterval) 

This will at least work also in overflow case, because all values are unsigned. But I'm not sure if all other cases handle wrap around well. At least users should be warned in the documentation that it will happen quite frequently. Another possibility would be to ensure that the time values are 64 Bits, but this may be very expensive on 8 Bit AVRs (not even sure if avr-gcc supports 64 Bit integers...). A general question is if relying on standard C "unsigned long" is an issue with portability, because "long" can be theoretically anything. Most portable software systems either define either their own integer types (like "u32", "u64") or include stdint.h At least you should define a type for such a very critical value like time (e.g. "t_helios_time") with the possibility to adapt it for different ports.
This would also allow e.g. to run HeliOS in x86_64 Linux userland (where long is 64 Bits) but still emulate the behavior of a 32 Bit MCU platform.

[MannyPeterson]

Thomas,

All excellent points. The HeliOS Programmer’s guide is still very much a work in progress but I will ensure overflow and precision are discussed in the guide. It may also be wise to (at least) discuss overflow in the example Arduino sketches. I will add your suggestion to my documentation backlog.

Defining time as a u32 is something I haven’t thought about yet. I used to have HeliOS defines setup so it could run in Windows and Linux userland. That is something I possibly could reintroduce if you and/or others find it useful. In that use case I could certainly use 64-bit precision. But going back to the Arduino platform, micros() only returns an unsigned long (per documentation, I admittedly have not verified the Arduino code). Using something other than unsigned long may not offer much value in that context. Thoughts?

Danke,

Manny

[JuPrgn]

Hi For portability I would recommend using stdint.h types as you suggested and use defined INTN_MAX values to check overflows.

[MannyPeterson]

I will post proposed code changes (using sized types for storing time) here. If it is agreed that the code changes address the issue, I will incorporate them in the next release.

One question for @JuPrgn , could you please elaborate on “check overflows”? I typically have applied the philosophy that you don’t try to handle overflows, instead you write overflow tolerant code. Please let me know what you are thinking. Thanks!

Manny

[JuPrgn]

I did not look to how you handle time yet but if your code is tolerant to overflow this is fine. I will look at this and answer you later if I can help. Your project is really interesting !

[MannyPeterson]

@ThomasHornschuh @JuPrgn thank you for your interest and input. I’ll post the proposed changes in one to two days.

Manny

[JuPrgn]

You handle it well on xHeliOSLoop() this is overflow tolerant. But there could be a problem if your datas size are different than the micros return type. If think this could be an issue for other microcontrollers but micros() return type should be the same for all arduino I guess (I am not using arduino micro). I will think about it and how we could handle this.

At first look I didn't get what corresponds the two cases notifyBytes and timerInterval but there seems to be some code duplication here that could be refactored into a single function updateRuntime(). I will propose some code this week too.

[ThomasHornschuh]

@MannyPeterson : Using sized types give better control how your code is compiled in general. On the other side, "generic" types give the opportunity to use the "natural" size of the machine which can lead to faster and smaller code. For example using e.g. "int" as variable in a for loop will use 16 bit on a 8 Bit AVR and 32 Bit on Cortex-M type MCUs. As long as you know the range of a 16 Bit int will be enough, using int is fine. In case you interact with platform specific data, explicitly controlling size is a better choice. I'm considering using HeliOS at my own custom RISC-V platform. RISC-V has a 64 Bit hardware timer, so using 64 Bit as time value seems natural on this platform, but on RV32 long is 32 Bit. In the simpest form you can write typedef unsignedlong t_helios_time; or something similar. Others can use more sophisticated schemes to define the type

[JuPrgn]

You can use a generic header, for example helios_target.h :

#include "target.h"

TIME_t currentTime();
TIME_t elapsed(TIME_t StartTime);

And a generic source helios_target.c :

#include "helios_target.h"

TIME_t elapsed(TIME_t StartTime)
{
    return currentTime() - StartTime;
}

Add specific target headers and sources for each platforms with their own function implementation : For example in arduino folder : target.h :

typedef uint32_t TIME_t;
#define TIME_MAX UINT32_MAX

target.c

#include "target.h"

TIME_t currentTime()
{
    return NOW();
}

And after some refactoring to the following code :

// Maybe these one go to task
void taskUpdateRuntime(Task *task, TIME_t taskStartTime)
{
    task->lastRuntime = elapsed(taskStartTime);
    task->totalRuntime += task->lastRuntime;
}

void taskRun(Task *task)
{
    TIME_t taskStartTime = currentTime();
    (*task->callback)(task->id);
    taskUpdateRuntime(task, taskStartTime);
}

// In HeliOS.c we can replace with this :

TIME_t taskStartTime = 0;
TIME_t  leastRuntime = TIME_MAX ;

for (int i = 0; i < waiting; i++) {
    if (waitingTask[i]->notifyBytes > 0) {
            taskRun(waitingTask[i]);
            waitingTask[i]->notifyBytes = 0;
        } else if (waitingTask[i]->timerInterval > 0) {
        if (elapsed(waitingTask[i]->timerStartTime) > waitingTask[i]->timerInterval) {
            taskRun(waitingTask[i]);
            waitingTask[i]->timerStartTime = currentTime();
        }
    }
}

There are probably other places where you are using NOW(), and every variable where you store time should be of type TIME_t. Then to add a new platform the user will only have to change or add his own target.c and target.h.

Hope this help

[MannyPeterson]

@JuPrgn very helpful and I appreciate the contribution! I am going to branch this issue and add your suggestions - hopefully today. Thanks!

[MannyPeterson]

@JuPrgn one question about your proposed code. You have structured the code to reduce duplication which is exactly what I would do in most circumstances. But one of the reasons you are seeing duplicate blocks of code in HeliOS is to avoid the PUSH->JUMP->POP cost, both in terms of stack and clock cycles, on small microcontrollers. So I have chosen to error on larger compilation size. What are your thoughts about the trade offs? Again, you proposed clean code - just thinking about the cost inside of xHeliOSLoop() which we want optimized for runtime. Please let me know your thoughts. Thank you!

(Just to be clear, there is no question about the need to address the sized types/precision - that I will definitely address)

[JuPrgn]

@MannyPeterson I think this is the job of the compiler to optimize code and user can choose to optimize size or speed or a tradeoff between those two. I understand your thoughts on this but I prefer a clean code that is easily readable. A good practice is to avoid to mix 2 levels of abstraction in a same function. You should probably avoid to use a lot of levels but I don't think you need that kind of abstraction. Many slow 8 bits micro are no more used for new designs and are replaced by powerfull microcontrollers. I think that would be nice to compare your code before and after refactoring to compare these performances I don't know if you have such tools in arduino ?

[MannyPeterson]

@JuPrgn I am not aware of any performance testing / profiling tools for the Arduino environment. But! What about using the "inline" attribution for functions combined with the finline-functions optimization option with GCC/G++? My understanding is that the compiler will effectively inline those functions at compile time thus eliminating the cost of the call. This could allow us to use more concise code while maintaining the performance advantage. Thoughts?

for example

inline TIME_t currentTime() { return NOW(); }

[JuPrgn]

I am not an expert using inline but yes this seems to be a good way doing this for simple functions like this one !

[MannyPeterson]

Changes are in progress.

@JuPrgn @ThomasHornschuh I would appreciate any input you are willing to provide on my solution to issue #11

Thanks!

[MannyPeterson]

Added 64-bit precision support for building on Linux. It will be available in the 0.2.5 release.

If anyone has experience getting time from Windows I would be happy to add it.

inline Time_t CurrentTime() {
#if defined(OTHER_ARCH_WINDOWS)
    /*
     * Get time from Windows. Need to implement and test.
     */
    return 0;
#elif defined(OTHER_ARCH_LINUX)
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC_RAW, &t);
    return t.tv_sec * 1000000 + t.tv_nsec / 1000;
#else
    return 0;
#endif
}

[JuPrgn]

To implement Time fromWindows this should be helpfull as I think this is the best suited method but it is not simple as a function call : https://stackoverflow.com/questions/1739259/how-to-use-queryperformancecounter I could try to propose some code later but if you have some free time to work on this don't wait for me =)

[MannyPeterson]

@JuPrgn what a mess. This reminds me why I develop on Linux/UNIX. :) I will add the code but I don’t currently have a way to test on Windows. Hopefully someone will be able to compile and test on the Windows platform. Thanks!

[JuPrgn]

Ok great I could test on Windows !

[MannyPeterson]

@JuPrgn the Windows code is now in the develop branch. Feel free to compile/test when you have time. I hacked together the following C file to test on Linux. I plan on building a Makefile and better main() file example for Linux and Windows in the next release so this will have to do for now. :)

#include <stdio.h>
#include "HeliOS.h"
#include "list.h"
#include "mem.h"
#include "task.h"

void task(int id_) {
  printf("task() ran.\n");
}

int main(int argc, char *argv[]) {

  xHeliOSSetup();

  int id = 0;

  id = xTaskAdd("TASK", &task);
  xTaskWait(id);

  xTaskSetTimer(id, 1000000);

  while(1) {
    xHeliOSLoop();
  }

  return 0;
}

[MannyPeterson]

@ThomasHornschuh @JuPrgn thank you both for your ideas and contributions. I think everything in this issue is now taken care of. You should see the changes in 0.2.5 which I will release Saturday or Sunday. I am going to close this issue for now. :)