Internal time representations

[Sebastian Huber]

Hello,

I am not sure which problem you want to address. For the watchdogs we 
use currently a 64-bit integer key for relative and absolute timeouts. 
For the watchdog it is important that

* the key comparison operations are fast,
* the conversion from common time formats to the key are fast, and
* there is no integer overflow within a reasonable time frame.

This is all satisfied currently. It is NOT important to convert this key 
into a common time format, since there is no use case for this.

For timekeeping we use the FreeBSD time counters (provider for 
CLOCK_REALTIME and CLOCK_MONOTONIC). They use struct bintime (aka 
Timestamp_Control) for time representation. It allows fast conversion 
to/from common time formats. Addition is also fast. In addition there is 
a sbintime_t available which can be used for some problem domains as an 
optimization.

For NTP and PPS we just have to port the code from FreeBSD. It is very 
well integrated into the FreeBSD time counters.

On 27/07/16 23:29, Pavel Pisa wrote:
> Hello Gedare,
>
> thanks much for the great summary of the discussion.
>
> On Wednesday 27 of July 2016 18:30:02 Gedare Bloom wrote:
>> After an IRC chat this morning with Pavel, we've decided to query
>> everyone about thoughts on unifying the internal score representations
>> for time into a single format. This discussion comes from the work
>> I've done with nanosleep, which now uses both the relative and
>> absolute watchdogs that have two different representations of
>> time--relative uses the score "ticks", and absolute uses a 64-bit
>> compacted version of timespec with seconds in the upper 32-bits and ns
>> in the lower 32. The proposed format is a count of nanoseconds in
>> 64-bits, or ns64.
> minor correction, copact time works in 34+30 bit format so it
> has no 2038 problem (final year is about 2514 for unsigned
> and 2242 for signed representation)
>
> https://git.rtems.org/rtems/tree/cpukit/score/include/rtems/score/watchdogimpl.h#n295
>
> On the other hand, conversion of the timespec seconds to this format
> requires some shifts and masking. Conversion of 32-bit + 32-bit timespec
> to linear ns64 requires one 32*32->64 bit multiply and 64-bit addition.
> This has higher cost but on the modern CPUs it is not so big difference.
> It simplifies computation of differences, adding of relative time
> to actual time etc. It can be significant overhead for 16-architectures
> (bare h8, even h8s) and blocker for 8-bit ones (AVR). But they are
> not so common today.
>
> Conversion to timespec is significant problem.
>
> If the 34+30 bit compact timespec advantage of the faster conversion
> prevails for PER_CPU_WATCHDOG_ABSOLUTE then I would vote to change
> PER_CPU_WATCHDOG_RELATIVE to the same format.
>
> This simplifies clock_nanosleep logic and generally makes
> code more readable and lowers space for mistakes.
>
> If we consider 64-bit linear format then we should think about
> conversion to 64+32 bit timespec to overcome 2038 year problem.
> This makes multiplication 64*32->64 which is more complex.
> The most of the upper 32-bits would be discarded in ns64 format.
> But time wrap is around 2554, so no problem. For copacted
> timspec based format id 64-bit second field conversion easier,
> two LSB bits from upper 32-bit part are moved to MSB bits of
> compacted timespec.
>
> On the other hand, conversion of generic time source (which needs scaling)
> to the compacted timespec is disaster. So I think that linear
> 64-bit (ns64) format is better at the end.
>
> But discussion and counter examples are welcome.
>
> The cost of conversion from ns64 to timespec is high.
> May it be we can find some optimization but it is problem.
> So at this time I suggest ns64 only for timers which fire
> and user provided time, there is no requirement to read
> expire value back by user in common POSIX APIs (at least
> I hope).
>
>> Advantages of the ns64 is that conversion of user time formats
>> (timespec, timeval, etc)  to 64-bit nanoseconds is relatively
>> efficient, and the internal time representations can be compared with
>> easy logic. The ns64 allows for higher precision event triggers than
>> score ticks. Furthermore, converting multiple time sources into ns64
>> is simpler to maintain consistent notion of time than score "ticks".
>> Thus, we anticipate the ns64 would make it easier to introduce
>> variable length ticks (a.k.a. tickless/no_hz) and to synchronize time
>> across SMP chips where each core has its own time source.
>>
>> Some disadvantages are
>> 1) conversion back to user time is costly
>> 2) clock "tick" may add multiple nanoseconds to the ns64 counter
>> 3) no one has budget to implement it now :)
>>
>> I wanted to stimulate some discussion about the topic to see if there
>> was any great objection to this kind of change, and what other inputs
>> others may have.
> Best wishes,
>
>                Pavel
> _______________________________________________
> devel mailing list
> devel at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel

-- 
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone   : +49 89 189 47 41-16
Fax     : +49 89 189 47 41-09
E-Mail  : sebastian.huber at embedded-brains.de
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.