64bit OS time

Discussions and support about ChibiOS/RT, the free embedded RTOS.
Thargon
Posts: 114
Joined: Wed Feb 04, 2015 5:03 pm
Location: CITEC, Bielefeld University, germany
Has thanked: 12 times
Been thanked: 21 times
Contact:

64bit OS time

Postby Thargon » Mon Oct 09, 2017 11:34 am

Hi,

as I mentioned earlier, I need high-resolution but unique timestamps for my application. More precisely, I want to allow µs precision but using 32 or even 16 bit timers results in overflows every 71.5 minutes or 65.5 milliseconds respectively. Since it is crucial for me that these timestamps are unique, I require 64 bit resolution instead. Please note that the actual frequency of underlying hardware timers does not need to be 1MHz! This is just about unique timestamps that can represent a high resolution if required and which are some kind of hardware independent, so that they can be used for communication with other systems (e.g. connected via CAN).

I have built my current solution on top of ChibiOS/RT, using an additional hardware timer (GPT) but this is not very efficient and suffers from several issues. Most importantly, I can not use the 64 bit timestamps for any timeout values of the ChibiOS functions, which still use systime_t, which is 16 or 32 bit. What I would like to do is to integrate my solution deeper into the ChibiOS/RT system tick structures, but I need some help on where to put all that code and how to do the stuff the clean way.

My plan is first to decouple the time structure used in the OS (i.e. ChibiOS/RT) from the one used by the hardware and LLDs (i.e. ChibiOS/HAL). Currently systime_t is used throughout the project and hence all high-level code depends on the underlying hardware resolution. By introducing a new structure (e.g. ostime_t) this issue could be resolved. While CH_CFG_ST_RESOLUTION would then define the width of ostime_t, the type of systime_t would depend on the port (which actually is the correct place, imo). The underlying hardware timer (STM32_ST_TIM) is still running with the frequency defined by CH_CONF_ST_FREQUENCY and suffers from the same overflows. However, this can be solved by using an interrupt that fires whenever the hardware timer is about to overflow (depends on CH_CFG_ST_TIMEDELTA). On this interrupt, a callback updates the ostime_t accordingly (mingles with the various combinations of resolutions). In order to handle timeouts and such, which would now be set as ostime_t values, the callback also has to set an alarm, if required. It basically has to check whether the next upcoming timeout will occur before the next overflow and if so configure an according alarm.

The major challenges to realize this will be to keep it configurable, implement it efficiently and to resolve all dependencies correctly. For the latter, the most difficult part is, that many timeout functions are handled within the LLDs, which are part of ChibiOS/HAL and thus either need to know ostime_t, or the mapping ostime_t -> systime_t must be handled before in another layer of ChibiOS/RT. Maybe you can give me some advice where to start and how to do all the stuff, as well as list of components that must be modified and checked. I hope I can keep the final solution quite simple so it can be integrated into the project without many troubles :)

Best regards,
Thomas

PS @ Giovanni: I know you have your doubts about my idea in general, but I would just like to try nevertheless and see what I can achieve ;)

User avatar
Giovanni
Site Admin
Posts: 13087
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 759 times
Been thanked: 638 times
Contact:

Re: 64bit OS time

Postby Giovanni » Mon Oct 09, 2017 1:30 pm

Hi,

In RT5 I am considering to implement a "large" mode for virtual timers and 64bits system time. Another change would be introducing a new type sysinterval_t that represents the difference between two systime_t. Intervals could be 32bits even if time would be 64bits in order to not have 64bits timeout parameters on all functions if not required.

Of course tick-less would decay in tick-saving if the physical counter is smaller than systime_t.

This is the general idea, I don't have yet all the details clear in my mind, it is a background think task ;) please don't expect it tomorrow, I need to consider the system as a whole, there would be impact on HAL, OSAL and probably other things. It could even slip in RT6.

What I could do "immediately" (read: probably not next year) is to allow 64bits for system time, just in case you have a large timer or do SW tricks.

Giovanni

Thargon
Posts: 114
Joined: Wed Feb 04, 2015 5:03 pm
Location: CITEC, Bielefeld University, germany
Has thanked: 12 times
Been thanked: 21 times
Contact:

Re: 64bit OS time

Postby Thargon » Mon Oct 09, 2017 5:39 pm

Hi and thanks for your reply!

Giovanni wrote:In RT5 I am considering to implement a "large" mode for virtual timers and 64bits system time.

64 bit virtual timers would be a nice start as all LLDs use OSAL for timeout checks and OSAL again uses chVT, if I am not mistaken. However, the interesting part will be to make the virtual timers capture time frames that are longer than the physical timer can represent. For this you will need a callback that is executed periodically and you end up with something similar as I proposed ;)

Giovanni wrote:Another change would be introducing a new type sysinterval_t that represents the difference between two systime_t. Intervals could be 32bits even if time would be 64bits in order to not have 64bits timeout parameters on all functions if not required.

I thought about something like that as well. I don't know if it is actually a good idea, but maybe each current timeout function should be split in two versions: One like the current implementation taking an efficient interval type as argument, and another one that takes an absolute time (64 bits).

Giovanni wrote:Of course tick-less would decay in tick-saving if the physical counter is smaller than systime_t.

Yes, but there is only one additional function call each time the physical counter fires an overflow interrupt. For 16 bit hardware that might be quite bad but for 32bit this should be of no concern. As mentioned before, the system can still be configurable so that a hardware timer tick (a system tick) can still represent an arbitrary time frame (e.g. 100us for CH_CONF_ST_FREQUENCY = 10000) and the 64bit timeouts etc. will just ceil to the next 100us value. It will work the same way as the ST system does now when you use the XX2ST() macros.
For this reason I think 64 bit time values should be of a defined scale that is NOT configurable. Even at 0.1us precision about 600 years can be represented which should be more than enough. Furthermore it might be preferable to use signed integers here (300 years will still suffice) as it is less efficient to check whether a>b before subtracting b from a (two 64 bit operations), than just execute the subtraction and then check for <0 (one 64 bit operation + 1 or 2 comparisons).

Giovanni wrote:This is the general idea, I don't have yet all the details clear in my mind, it is a background think task ;) please don't expect it tomorrow, I need to consider the system as a whole, there would be impact on HAL, OSAL and probably other things. It could even slip in RT6.

What I could do "immediately" (read: probably not next year) is to allow 64bits for system time, just in case you have a large timer or do SW tricks.

I really would like to have such a system asap and I am more than willing to help ;) If it is ok for you, I will take a look at the 64bit implementation of the virtual timer and see how far I get. Maybe I can provide you a patch soon enough to merge it into RT5 =)

Thargon
Posts: 114
Joined: Wed Feb 04, 2015 5:03 pm
Location: CITEC, Bielefeld University, germany
Has thanked: 12 times
Been thanked: 21 times
Contact:

Re: 64bit OS time

Postby Thargon » Tue Oct 10, 2017 9:44 am

Well, I didn't come far :D

I already encountered two issues, I need some advice for.
First, I can not find the code that handles the "wakeup" or "alarm" for virtual timers in tickless mode. For the normal mode the function chVTDoSetI() activates an according alarm using port_timer_start_alarm(). For tickless mode there is nothing like that in the chVT code. Where is the code that fires an interrupt event as soon as the next VT expires?
Second, the ch_virtual_timers_list struct holds the current system time as volatile systime_t. For 64 bit timers this value needs to be modified to a 64 bit value, which again makes atomicity problematic. What do you think is the best solution here? Should I use chSysLock() whenever I use the variable, introduce a mutex or semaphore, or do something completely different?

Thomas

User avatar
Giovanni
Site Admin
Posts: 13087
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 759 times
Been thanked: 638 times
Contact:

Re: 64bit OS time

Postby Giovanni » Tue Oct 10, 2017 1:11 pm

Hi,

The code is the same in tick and tickless modes, there are #ifs into the same functions and is everything in chvt.c/h.

It looks premature to me anyway.

Giovanni

User avatar
Giovanni
Site Admin
Posts: 13087
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 759 times
Been thanked: 638 times
Contact:

Re: 64bit OS time

Postby Giovanni » Wed Oct 11, 2017 9:24 am

The problem with 64 bits time is that without a 64 bits time you would have to handle half of it in SW and the other half using the timer counter.

It means that within critical zones the lower 32 bits would continue to run, potentially overflowing, the upper 32 bits could be not immediately updated. The result would be a counter that is not monotonic.

I don't see problems with long delays but 64 bits system time looks problematic without dedicated HW.

Giovanni

Thargon
Posts: 114
Joined: Wed Feb 04, 2015 5:03 pm
Location: CITEC, Bielefeld University, germany
Has thanked: 12 times
Been thanked: 21 times
Contact:

Re: 64bit OS time

Postby Thargon » Wed Oct 11, 2017 9:58 am

Of course, if the hardware features a 64 bit timer the solution would be trivial, but It should be realizable with 32 or even 16 bit timers as well. Originally I had two ideas how to solve this: Either accumulate "small" hardware timer by software, or use a combination of RTC and TIM.

I dropped the latter, though, as it is very difficult (maybe even impossible) to synchronize RTC and TIM readings. There will always be an unpredictable delay, making synchronization imprecise (probably reducing precision to RTC frequency).

Hence I decided for the former, a software based accumulation. The issue that the accumulated time would not be updated before the hardware overflows can be solved by slightly reducing the frequency at which the register value is accumulated to a period of TIME_MAXIMUM - CH_CFG_ST_TIMEDELTA. If you then still encounter overflows, your system violates CH_CFG_ST_TIMEDELTA and you have to increase that value. I already implemented that method atop of ChibiOS/RT and it is working quite well. The only issue is that I can not use my 64 bit values for timeouts (since it is not integrated INTO ChibiOS) and that I need an additional GPT that fires the periodic interrupts to call the accumulation function. Actually I "only" need to make the selected ST_TIM fire that periodic interrupt and integrate 64bit timeout functions etc. into the deep layers of the OS. Regarding the monotonic behavior of the time variable, my implementation updates it within an ISR, which should be fine. Of course, every reading access to the 64 bit value must be surrounded by some kind of lock as well.

Thomas

User avatar
Giovanni
Site Admin
Posts: 13087
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 759 times
Been thanked: 638 times
Contact:

Re: 64bit OS time

Postby Giovanni » Wed Oct 11, 2017 3:05 pm

I wrote some notes regarding this, it looks a complex task all things considered.

*** Adding an time interval type ***

. It represents the differences between two system times.
. Sleep and timeout functions would take a sysinterval_t.
. SleepUntil functions would take a systime_t.
+ Stronger type checking.
+ API clarity.
- Requires changes to many APIs in PORT, RT, NIL, HAL and OSAL.

*** Time intervals larger than system time ***

. Can be implemented using "large virtual timers".
. Must have the same resolution of system time for simplicity.
+ Useful feature.
+ Allows for large intervals using small timers.
- Cannot be added to a systime_t without checks, it could wrap the time
more than once.

*** 64 bits system time ***

+ Useful feature coupled with high resolution.
- No 64 bits HW timers.
- SW simulation complex and/or not safe and/or not monotonic.
- Linking HW timers is complex (reading multiple counters, race conditions).
- Safe time conversion functions would require 128bits arithmetic.

*** 64 bits intervals ***

- Safe time conversion functions would require 128bits arithmetic unless
limiting to 32bits types for seconds, milliseconds and microseconds.


I will open an experimental branch about this, it would break too many things to be handled in trunk. It could not go in RT5.

Giovanni

Thargon
Posts: 114
Joined: Wed Feb 04, 2015 5:03 pm
Location: CITEC, Bielefeld University, germany
Has thanked: 12 times
Been thanked: 21 times
Contact:

Re: 64bit OS time

Postby Thargon » Thu Oct 12, 2017 8:35 am

I've got some remarks on that, but first one step back: so there will be three time types:
  • systime_t
    width depends on hardware (timer); represents time in system ticks (configurable); each tick is "real", no virtual quantization
  • abstime_t
    64 bits wide; represents time since system startup in us; there may be quantization effects if ST resolution is lower than 1us
  • interval_t
    width either native to architecture (i.e. 32 bits) or identical to systime_t (the latter doesn't make sense, does it?); represents relative time offset at same resolution as abstime_t; there may be quantization effects for the same resons
Btw, we should agree on some names for those three or this discussion will become very confusing (I'll leave that to you). ;)

So now to your notes. I've taken the freedom to add my type names in brackets.
Giovanni wrote:*** Adding an time interval type ***

. It represents the differences between two system times.
. Sleep and timeout functions would take a sysinterval_t [interval_t].
. SleepUntil functions would take a systime_t [abstime_t].
+ Stronger type checking.
+ API clarity.
- Requires changes to many APIs in PORT, RT, NIL, HAL and OSAL.

Agreed, but I think this type will just help for the API. The implementation will probably just convert the interval to an absolute time first and then call an according xxxUntil() function. You can not save any computational overhead since the system must be aware of 64 bit time anyway (VTimers must be ordered according to their 64 bit values). Maybe it would make sense to keep all xxxTimeout() functions as they are (taking systime_t) for compatibility and just modifiy/introduce xxxUntil() functions and provide a macro/function INTERVAL2ABSTIME(interval_t). Example:

Code: Select all

whatever_t chDoSomethingTimeout(systime_t);                    // API unchanged and compatible
whatever_t chDoSomethingUntil(abstime_t);                      // new or modified API
whatever_t chDoSomethingUntil( INTERVAL2ABSTIME(interval_t) ); // no need for further functions
whatever_t chDoSomethingTimeout( INTERVAL2ST(interval_t) );    // no need for further functions but with same drawbacks as using US2ST()


Giovanni wrote:*** Time intervals larger than system time ***

. Can be implemented using "large virtual timers".
. Must have the same resolution of system time for simplicity.
+ Useful feature.
+ Allows for large intervals using small timers.
- Cannot be added to a systime_t without checks, it could wrap the time
more than once.

What do you mean with "system time" for the second point? Imo, interval_t should have the same temporal resolution as abstime_t, but the width of the type should be native to the architecture, so it can be calculated more efficiently.
As for the last point (the drawback), yes it can not be easily added to systime_t, but as said before, the core of the system must be aware of 64 bit times anyway. So in the end, the implementation will convert any interval_t arguments to abstime_t for the VTimer and each time the hardware timer starts anew (after an overflow of systime_t) the OS must check if there is a timeout within the next iteration (until systime_t overflows again). So imo this drawback can be neglected because there should be no reason to convert interval_t to systime_t.

Giovanni wrote:*** 64 bits system time ***

+ Useful feature coupled with high resolution.
- No 64 bits HW timers.
- SW simulation complex and/or not safe and/or not monotonic.
- Linking HW timers is complex (reading multiple counters, race conditions).
- Safe time conversion functions would require 128bits arithmetic.

SW simulation is not that complex, actually, and as with everything that can not be calculated atomicly by the hardware, safety must be ensured by an according lock mechanism. This makes 64 bit time more complex than the current implementation, but I don't think it is that bad.
Why would you link HW timers? All you need is one timer running at CH_CFG_ST_FREQUENCY (like it is right now) and make it fire an interrupt before the register overflows. The according ISR then accumulates time to the 64 bit value and sets any alarm if a VTimer expires within the next period (before the ISR is executed again). One HW counter, no race conditions.
With 64bit variables and assuming a temporal resolution of 1nanosecond (yes, nano), you only need 128 bit arithmetic if you want to represent a timeframe of several hundred years. I don't know about NASA use cases, but for most people that should be more than enough ;) I would only add such functions if someone really requests it

Giovanni wrote:*** 64 bits intervals ***

- Safe time conversion functions would require 128bits arithmetic unless
limiting to 32bits types for seconds, milliseconds and microseconds.
.
Same again ;)

Giovanni wrote:I will open an experimental branch about this, it would break too many things to be handled in trunk. It could not go in RT5.

That is absolutely fine for me as long as I can get an "experimental" patch for RT5.

Best regards,
Thomas

User avatar
Giovanni
Site Admin
Posts: 13087
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 759 times
Been thanked: 638 times
Contact:

Re: 64bit OS time

Postby Giovanni » Thu Oct 12, 2017 9:49 am

Hi,

When you posted I already committed a set of changes to /branches/rt5-dev-point1.

The current state is the following:

systime_t: is the system time we know, it is absolute, it is expressed in system ticks, it can wrap, 16-32-64 bits.
sysinterval_t: it is the difference between two systime_t but can be larger than a systime_t, it is expressed in system ticks, 16-32-64 bits.
time_secs_t, time_msecs_t, time_usecs_t: new types for expressing time intervals using standard units, 16-32 bits.

Various new functions and macros:

Code: Select all

#define TIME_S2I(secs)
#define TIME_MS2I(msecs)
#define TIME_US2I(usecs)
#define TIME_I2S(interval)
#define TIME_I2MS(interval)
#define TIME_I2US(interval)
static inline sysinterval_t chTimeS2I(time_secs_t secs)
static inline sysinterval_t chTimeMS2I(time_msecs_t msec)
static inline sysinterval_t chTimeUS2I(time_usecs_t usec)
static inline time_secs_t chTimeI2S(sysinterval_t interval)
static inline time_msecs_t chTimeI2MS(sysinterval_t interval)
static inline time_usecs_t chTimeI2US(sysinterval_t interval)
static inline systime_t chTimeAddX(systime_t systime,
                                   sysinterval_t interval)
static inline sysinterval_t chTimeSubtractX(systime_t start,
                                            systime_t end)
static inline bool chTimeIsInRangeX(systime_t time,
                                    systime_t start,
                                    systime_t end)


Previous conversion macros and function disappeared, there is no converting between systime_t and other units, only intervals can be converted.

I am evaluating the changes to virtual timers for sizeof(sysinterval_t)>sizeof(systime_t), looks complex.

Giovanni


Return to “ChibiOS/RT”

Who is online

Users browsing this forum: No registered users and 4 guests