Proposal for new ISO C 9x time API

[Markus Kuhn]

Paul Eggert wrote on 1998-10-07 22:37 UTC:
>    >     So the application
>    >     needs a way to find out whether a purported leap second is a known
>    >     leap second....
> 
>    My suggestion is to use xtime_cmp() in order to define a total
>    order on all know leap seconds and the parameter timestamp, so as
>    to locate the next higher/lower known leap second in a sorted list
>    of leap seconds
> 
> Sorry, I don't understand this suggestion.  Are you proposing that the
> program initially create a table of known leap seconds by iterating
> through tz_jump?

No.

> This sounds awkward, and anyway it won't work
> reliably in long-running programs, as new leap seconds may become
> known to the implementation during execution.

Agreed.

I was talking about the implementation of tz_jump() using xtime_cmp()
internally, because it was my understanding that you thought there might
be problems with specifying the precise semantics of tz_time() in the
context of bogus leap seconds. My point was that this is trivially
resolved by implementing tz_jump internally the following way:

Given are to tz_jump() a number of externally known leap seconds (and
these might indeed change in long-running implementations), plus an
input timestamp. Now you (conceptually) sort all known leap seconds
using xtime_cmp(). Then you lookup where the input timestamp would have
to be inserted into this sorted list, and you just return the next
higher or next lower (depending on the requested direction) known leap
second. This is a very clear and straight forward semantic of tz_jump,
that gives a well-defined answer even if the input timestamp is not only
a bogus leap second, but also out of the valid range.

Using tz_jump in order to test whether a given leap second is known or
not is also trivial: you set nsec=0 and sec-- in the suspected leap
second and give it with direction == +1 to tz_jump. If it returns the
same leap second, than the system know about it. If it did not, then
either the system has not been informed about the leap second, or what
you have is a bogus leap second. We never can distinguish for sure
between the two cases anyway, so the API's semantic should depend as
little as possible on this distinction.

>    Just use xtime_cmp() to compare timestamps, and build tz_jump completely
>    on top of xtime_cmp.
> 
> Sorry, I don't follow this suggestion.

I hope the above made clear what I meant. (Whether it is the answer to
what you asked originally is another question.)

>    How can the implementation be based fundamentally on TAI but not know
>    the TAI epoch?
> 
> Because it gets its timestamps from GPS?

GPS *does* output both TAI and UTC. You are probably more thinking about
time services like NTP and DCF77 that only warn about the next leap
second but provide no relationship to TAI.

>    Please make sure you have fully understood the difference
>    between TIME_MONOTONIC and TIME_TAI. Both are very similar in that they
>    do not have leap seconds, and the only difference is that TIME_TAI has a
>    known epoch, while TIME_MONOTONIC has not.
> 
> That's not the only difference!  There are two others:
> 
> (1) TIME_MONOTONIC is monotonically nondecreasing (hence its name),
> whereas TIME_TAI can go backwards when the clock is reset.

Well, that is just an immediate and direct unavoidable consequence of
having a known epoch. If you have a known epoch, then there is the
possibility that you learn that you have the wrong epoch and therefore
have to correct. If you by definition don't have a known epoch, then it
can't be wrong and you will never have to adjust the epoch (or
equivalently the pahse of the clock).

> (2) TIME_MONOTONIC's seconds may start right in the middle of a TAI
> second with no problem, whereas TIME_TAI's seconds are supposed to be
> synchronous with true TAI seconds (perhaps with some small error).

I do not see what advantages it has to have the fourth clock type that
you propose, which seems to be identical to TIME_MONOTONIC, except that
the difference to TIME_UTC and TIME_TAI is regulated to be an integral
number of seconds. What is so special about the second ticks here?

If prefer not to have such a rule in TIME_MONOTONIC, because this then
allows arbitrary precise and constant frequency of TIME_MONOTONIC, while
in your proposal you would have to introduce a phase control loop into
TIMe_MONOTONIC.

xtime_conv() is perfectly happy if TIME_MONOTONIC-TIME_UTC is 1234567.89
seconds before a leap second and 1234568.89 after a leap second. I see
no advantages of keeping the TIME_MONOTONIC-TIME_UTC difference a multiple
of integers, while I see big advantages in not requiring this in order
to allow highly stable TIME_MONOTONIC implementations.

> No, I'm assuming something stronger than that for TIME_TAI.  I'm
> assuming not only that it became frequency calibrated, but also that
> it became ``phase-calibrated'' (sorry, I don't know the lingo, but
> what I mean is that its second ticks should be very close to the true
> TAI second ticks), and also that for a certain window around the
> current time, the relationship between TIME_TAI and UTC is known.

Better call this PPS-synchronization (PPS = pulse per second, the
standard TTL connector output of reference clocks, 500 ms high, 500 ms
low, positive edge at the start of the second, to which you can connect
a 2-channel 2 GHz digital oscilloscope to match the modulo 1 second
phase difference between two reference clocks).

> From what you've written, these are both reasonable assumptions for
> the devices that you're talking about.

The technical reason for why I do not want PPS synchronization in
TIME_MONOTONIC is that many types of reference clocks are not
immediately available at boot time. A DCF77 receiver needs up to two
minutes to lock onto the signal, a GPS receiver needs up to 12 minutes,
a NTP server also needs a couple of minutes to make its initial
measurements before the PLL stabilizes reasonably well to below
millisecond noise, etc. However there are requirements for reliable
clocks that are guaranteed to be available right from the first time a C
program is started.

Leap seconds are not the only uncertainty that we have to deal with,
initial or temporary unavailability of clocks, as well as spurious wrong
clock readings and fluctuations are another one, and these errors do not
come nicely in multiples of one billion nanoseconds. Once we get Caesium
clocks for 50 dollars inside a chip package, you will even notice
fluctuations in signals from external reference clocks (ionospheric
fluctuations for GPS, ground wave versus space wave interference for
DCF77, hop fluctuations for WWV) and it will be the task of the Kalman
filters in your kernel to compensate these appropriately without
affecting the stability of your own monotonic reference timescale.
PPS-synchronization seems to be a crude and bizarre requirement in this
context. But if you really need it:

You can easily construct the time you are talking about in your application
the following way:

1) As long as TIME_UTC is not yet available, you just use TIME_MONOTONIC.

2) Once UTC has become available, you determine x = TIME_MONOTONIC - TIME_UTC
   one single time (let's call this moment your post-epoch), and then remove
   the non-fractional part of x (x.sec = 0).

3) From then on, you use TIME_MONOTONIC - x instead of TIME_MONOTONIC,
   if there is really a need for a monotonic time with PPS synchronization.
   You can apply a lowpass filter to smooth the transition from
   0 to x if you want. You will have to live with that there is an x-wide
   gap between the time before and after your post-epoch, unless you
   go at the post-epoch over all your old time-stamps and convert them
   by subtracting x to the new PPS-synchronized TIME_MONOTONIC. (If
   you do this, you could also use x = TIME_MONOTONIC - TIME_TAI without
   truncation once TAI is available, and then replace all older timestamps
   by proper TAI timestamps. You could also use TIME_UTC at the time of the
   post-epoch instead. There are many things you can do here, depending on
   your needs and personal preferences)

As you see, it is easy to implement your clock API on top of mine (but
not vice versa). However, if you ever run into an application, where you
need this PPS-synchronized monotonic time, please let me know. I
certainly cannot think of any right now, therefore I don't want to add
another clock type to my proposal that can easily be derived by the
applications in numerous ways from the existing one. It is important
however to understand that and how even such more exotic clock types can
be easily emulated on top of it.

> All operations that take out-of-window struct xtime values would fail,
> because implementation X converts struct xtime to its internal format
> (TAI within a window) in order to do all operations.  This is a
> reasonable implementation.

No. My API is only reasonably implemented by operating *directly* on
struct xtime values. If you think that it is reasonable to implement
anything on some other internal format, then you have probably
misunderstood something. The actual clock registers that hold the
current time are the only places where you might have any of a large
number of implementation-dependent representations (often dictated by
the existing OS kernel or by the hardware clock format).

>    Remember that only tz_jump and xtime_conv depend on the leap second
>    history, all other functions do not care about the leap second history
> 
> This is true of the implementation that you're thinking of, but I
> don't think the C standard should require such an implementation; it
> should also allow implementations that are fundamentally TAI based as
> described above.

xtime_get() can use whatever it wants internally, but for all other
implementations, there is little need to introduce an extra internal
time representation beyond something very closely related to xtime
itself.

>    if you know only all leap seconds since you inserted the batteries and
>    TIME_MONOTONIC started, then xtime_conv will not allow you to convert a
>    TIME_UTC value from before you inserted the batteries to a negative
>    TIME_MONOTONIC value. But why would you want to do this, since you never
>    received a corresponding clock value from the clock anyway?
> 
> Because you imported a leap-second timestamp from some other source,
> e.g. from a correspondent over the network using the draft IETF calendar spec.

And, what harm can it do to you? I have shown you functions that you can
use to savely use this other timestamp in calculations with well-defined
semantics, even if they are bogus, and if you try to convert it using
xtime_conv() to TIME_TAI or TIME_MONOTONIC, then the implementation will
certainly tell you whether this is possible. Doing this is however not
advisable. It is in most cases preferable if you go the other way round
and convert you own time_stamps to TIME_UTC before doing any
comparisons, etc.

I think I have now completely understood what your API model is and what
you are thinking about it in relation to xtime. I also think that you
are on the wrong path: You are analysing in some sense xtime by trying
to implement it on top of something similar to libtai and you discover
that this is not possible conveniently. Instead of recognizing that the
real problem is that a libtai-style lower layer has a much more
restricted functionality and that therefore this type of implementation
is not a good idea for a universal standard clock API (although it might
be highly useful for certain types of special application, such as
accounting which Dan Bernstein mentioned), you try to redesign and
restrict my API to make it implementable on top of a restricted
pseudo-TAI like clock model. Why do you think this is a good thing?

>    You can always call xtime_delay yourself if you are inside a leap
>    second and call xtime_get again afterwards.
> 
> This is the sort of hack that most users are unlikely to think of on
> their own -- and also it will impose unacceptable delays on some apps.
> We need a simple way to get the desired values, without delays.

Yes, but we do not know WHAT the desired values are!

>    If you want to get a special filter (e.g., the US 59 Hz power grid
>    leap rule or the BSD 10000 ppm adjtimex() rule), then you can
>    implement easily this specific rule using tz_jump (just do: if the
>    last leap second is less than 60 s away, add a linear compensation
>    ramp (delta_t / 60.0) to the time).
> 
> I thought that tz_jump was supposed to report only discontinuities.
> Aren't these filters continuous?

Tz_jump() reports only discontinuities. Think of the leap second
discontinuity as a dirac pulse, which you convolute with your filter
function, and the resulting sequences of soft falling steps is what you
add to your leap-filtered time. without system-theory lingo: You use
tz_jump only to measure how far away the last leap second is when you
read a clock, and then you add the height of the compensation ramp that
is adequate for the reported distance to the leap second. You will
normally use finite-impulse response filters, i.e. the frequency of the
filtered clock is correct again after say 1 or 20 minutes.

> Now that you mention it, though, it'd be nice if tz_jump (or some new
> primitive) also reported continuous changes to the TIME_TAI and
> TIME_UTC clocks as well, if that information is available.

Instead of reporting drifts between TIME_UTC | TIME_SYNC and
TIME_MONOTONIC, you should steer the frequency of TIME_MONOTONIC to be
identical to that of TIME_UTC | TIME_SYNC. Then the API does not provide
you with any continuous changes that are worth reporting.

> This is a
> good idea, and will better support apps that don't want to know about
> leap seconds.  It is a reasonable extension, though offhand I don't
> think it needs to be in the standard.

If you want, you can easily add your own xtime_get_smooth_UTC() function
that takes as argument a maximum frequency deviation (the steepness of
the ramp), and gives you pack a leap-second free UTC that is free of all
discontinuities reported by tz_jump. You can filter using linear ramps,
Gaussian bells, Bezier splines, and whatever you want.

If there is a very wide need, then I can provide a sample implementation
for a linear ramp filter with selectable frequency deviation. The
important thing is that xtime_get and tz_jump are all that is needed to
implement these, i.e. the right infrastructure is in place.

> My basic argument is that it's much more convenient to base the clock
> on an integer than to base it on a structure containing a
> somewhat-broken-down time, with all its foibles.

My basic argument is that if you use just an integer, most algorithms
will get more complicated if you provide for leap seconds, while the
algorithms continue to look pretty much the same as what we have for
POSIX systems if you use xtime.

> The (partial) leap second table and implementation-defined epoch is
> inherent to this sort of implementation.  You can't properly support
> UTC leap seconds without it.  In this respect, the ``calculation
> overhead'' and ``reliability concerns'' of integer-based clocks apply
> with equal force to struct xtime.

In your implementation, you need a (partial) leap second table each time
you want to convert to a broken down time, while in my implementation
you need it only to do conversion between clock types (including
filtered ones). If you always use real UTC (and I think that is what
most applications will want to use, because that is what legal local
time is based on), you never use a leap second table (except for the
internal kernel warning flag that one is coming at the end of the next
minute).

Markus

-- 
Markus G. Kuhn, Security Group, Computer Lab, Cambridge University, UK
email: mkuhn at acm.org,  home page: <http://www.cl.cam.ac.uk/~mgk25/>