
Paul Eggert <eggert@twinsun.com> writes:
I agree that my proposed API is still too complicated. When I get the time I'll try to simplify it. Your code is a valuable resource in this area: implementation experience counts for a lot in my book.
Well, then I hope you suggest an implementation for a monotonic time implementation. Constraints are: The underlying OS will not notify each running program about a sudden clock change and itself does not provide a monotonic clock. In this situation the only thing you can count on are some hardware "clocks" the kernel does not (or cannot) influence. I think about things like the time stamp counters found on many modern processors. But: - they are only found on modern processors, and therefore a generic implementation isn't possible - even if they are available, they might be useless if, as in the case of the Alpha, the counter range is too small (just do the math: a 32 bit counter increment in each clock cycle on machines with, as seen two weeks ago, 1GHz clock speed). What I meant to say is think about the implementation before you propose something. It is certainly nice to have such a timer but it is very often not possible to implement it and for exactly this reason we have adjtime(). -- ---------------. drepper at gnu.org ,-. 1325 Chesapeake Terrace Ulrich Drepper \ ,-------------------' \ Sunnyvale, CA 94089 USA Cygnus Solutions `--' drepper at cygnus.com `------------------------

From: Ulrich Drepper <drepper@cygnus.com> Date: 29 Aug 1999 09:56:37 -0700 I hope you suggest an implementation for a monotonic time implementation. Constraints are: The underlying OS will not notify each running program about a sudden clock change and itself does not provide a monotonic clock. TIME_MONOTONIC is optional; if the OS does not support TIME_MONOTONIC, then xtime_get (TIME_MONOTONIC | ...) returns an error indication. Kuhn's hope is that OS and C library suppliers can find their way to support TIME_MONOTONIC. I'm not an expert on GNU/Linux, but I believe that there's currently an awful way to get a TIME_MONOTONIC clock -- namely, read /proc/uptime. Clearly this could be improved by providing a more efficient way to get at the freerunning clock that's running inside the kernel. I expect that a small, well-thought-out patch to do this would be acceptable to the Linux kernel hackers. I expect other Unix kernels would be similar. I think about things like the time stamp counters found on many modern processors. But: - they are only found on modern processors, and therefore a generic implementation isn't possible Absolutely. - even if they are available, they might be useless if, as in the case of the Alpha, the counter range is too small That's a problem. (I wonder why the Alpha doesn't have a 64-bit clock?) Presumably on the Alpha one would have to fall back on a lower-resolution monotonic clock, e.g. the number of clock interrupts serviced by the kernel. As Kuhn mentions, there is certainly a need for a TIME_MONOTONIC in some applications. The question is whether this need is enough to justify inclusion in a standard API.

I agree that there are programs that use a low-level tick counter. One obvious example is the operating system: there's no reasonable way to implement gettimeofday(), for example, without a low-level tick counter. I also agree that toasters and other memoryless real-time embedded systems, being constitutionally incapable of figuring out the current time, need to use low-level tick counters instead. However, treating low-level tick counters the same way as timestamps is a blatant error. Old timestamps have a defined relationship to civil time; old tick counters do not. Most time functions simply don't make sense for tick counters. The fact that something is changing over time doesn't mean that it belongs in a time library! Furthermore, it is clearly incorrect to claim that tick counters eliminate the problems of setting clocks backwards. I already gave the example of the ``make'' program; if you use tick counters here instead of timestamps, you get disastrous results after a reboot. ---Dan

Date: 29 Aug 1999 23:18:53 -0000 From: "D. J. Bernstein" <djb@cr.yp.to> Old timestamps have a defined relationship to civil time; old tick counters do not. Most time functions simply don't make sense for tick counters. These are good arguments that the current draft API is too complex. However, I'm not yet convinced that we should throw out TIME_MONOTONIC entirely, given its utility for important classes of applications. I already gave the example of the ``make'' program; if you use tick counters here instead of timestamps, you get disastrous results after a reboot. `make' is stuck between a rock and a hard place. There is no perfect solution based solely on time stamps of real-world hosts where clocks are supposed to be accurate, but sometimes aren't. Obviously TIME_MONOTONIC wouldn't solve make's problem. But it would solve the (different) problem of real-time measurements in the presence of real-world clock adjustments better than a pure UTC or TAI based approach would.

Ulrich Drepper wrote on 1999-08-29 16:56 UTC:
Well, then I hope you suggest an implementation for a monotonic time implementation. Constraints are:
The underlying OS will not notify each running program about a sudden clock change and itself does not provide a monotonic clock.
Which should definitely be changed soon for the GNU kernels. An API that provides useful functionality does not become bad, just because it would require some kernels to be upgraded. It just shows up a deficiency in the current repertoire of OS functionality. And you are surely well aware that the Kuhn/Eggert API drafts are certainly not the only ones that require monotonic time: The Real-Time Annex (especially section D.8) of the Ada95 standard for instance requires a lot of useful OS functionality for safety-critical applications (monotonic clock, priority ceiling locks, etc.), and Linux for instance is still far away unfortunately from providing the required functionality to implement this. (Embedded operating systems like QNX or VxWorks are much more advanced here; please don't ask me about Windows CE ;-) See: http://wuarchive.wustl.edu/languages/ada/userdocs/docadalt/rm95/d.htm And this is not just theoretical stuff, this is an API you use each time you fly with a Boing 777. An Ada95 run-time system wouldn't get the mandatory FAA certification if the time monotonicity weren't guaranteed during the uptime of an aviation system. I hope that my API proposal is good enough to allow a portable conforming implementation of Ada95's section D.8 on top of it. I hope you don't mind if I propose APIs with implementation options that strech a bit the capabilities of underlying systems if practically useful functionality is involved, because this will hopefully lead to such problems being fixed eventually in the underlying systems. Dan is certainly right in that TIME_MONOTONIC is not of use for "make", because it does not guarantee monotonicity over certain types of system events (e.g., hard reset, power-down, etc.) in systems without any non-volatile state. I had thought of course early on about adding a requirement for long-term monotonicity, but I didn't add it for two reasons: a) Defining a term such as "shutdown", "reboot", "cold start", "hard reset", "EMS sequence", "recovery", etc. in a sufficiently general way is difficult to get right for the broad range of systems that we want ISO C to be applicable to, and we talk also about systems that do not smell like Unix with an init process whose termination marks what a system reboot is. b) The definition would have been impossible to implement on systems without non-volatile memory, but there are a huge number of applications (practically most industrial controlling systems), that need monotonic time only between two hard resets. c) Finite integer arithmetic makes long-time monotonicity a somewhat hazardous project anyway, because once your clock gets by accident too close too 2**n (n = clock wordlength), you can never back off again and will be forced over the overflow. If we require the clock only to be monotonic for a certain maximum uptime (e.g., the 50 years mentioned in section D.8 of the Ada95 standard), we can always restart the entire system if we ever get too close to 2**n. A really guaranteed long-time monotonic clock on the other hand would have no way of recovering from a glitch that set it to 2**n-epsilon. So this would have been an example for a theoretically unimplementable specification. Safety system requirements also often specify, that systems have to be reset in a completely well-defined state on reset, which can mean that a monotonic clock has to be guaranteed to be 2**n-1 steps away from the next overflow. So I decided to remove the requirement of long-term monotonicity from TIME_MONOTONIC. This provides not what Dan's idealized "make" would need, but it provides what many systems need, and there is no feasible implementation I can think of that would really guarantee a long-term monotonicity requirement as Dan seems to want. Except perhaps with bignum arithmetic, but that seems like real overkill here, and it can still accidentally overflow the memory during a glitch. (I said "idealized make", because an alternative implementation that would satisfy make's specific requirements is a clock with long-term monotonicity and an overflow warning flag, and at each overflow of the clock, this make semantics could automatically do a "make clean" or equivalent action.) I hope that this makes a bit clearer why I am so convinced that the idea behind my TIME_MONOTONIC definition is already the most practical one that you can get. It was strongly influenced, why what is commonly required in the safety-critical systems literature and the Ada95 real-time annex is just one reference that I have handy. If there is any interest, I would certainly be willing to discuss the option of an overflow warning bit to TIME_MONOTONIC. I considered it when I drafted the API, but dismissed it, because I wanted to have the minimum complexity level that I though to be highgly practically relevant. I also do not see monotonic clock overflow warning flags as a common feature in embedded OS implementations, and "make" is one of the very few applications that comes to mind, where this could be made good use of. Markus -- Markus G. Kuhn, Computer Laboratory, University of Cambridge, UK Email: mkuhn at acm.org, WWW: <http://www.cl.cam.ac.uk/~mgk25/>

Markus Kuhn writes:
no feasible implementation I can think of that would really guarantee a long-term monotonicity requirement as Dan seems to want.
Long-term monotonicity is the natural state of affairs. Clocks increase over time, see? It would be trivial for an OS kernel to guarantee this, even through reboots, given the battery-powered clocks already available in almost all computers.
I hope that my API proposal is good enough to allow a portable conforming implementation of Ada95's section D.8 on top of it.
But your API obviously flunks this test. You keep talking about safety-critical real-time applications. I have news for you: safety-critical real-time applications need tick counters that _=08w_=08o_=08r_=08k. Your TIME_MONOTONIC is allowed to fail at any mo= ment. ---Dan

"D. J. Bernstein" wrote on 1999-08-30 23:02 UTC:
Markus Kuhn writes:
no feasible implementation I can think of that would really guarantee a long-term monotonicity requirement as Dan seems to want.
Long-term monotonicity is the natural state of affairs. Clocks increase over time, see? It would be trivial for an OS kernel to guarantee this, even through reboots, given the battery-powered clocks already available in almost all computers.
I hope that my API proposal is good enough to allow a portable conforming implementation of Ada95's section D.8 on top of it.
But your API obviously flunks this test.
You keep talking about safety-critical real-time applications. I have news for you: safety-critical real-time applications need tick counters that _=08w_=08o_=08r_=08k. Your TIME_MONOTONIC is allowed to fail at any moment.
The reason for why I haven't required TIME_MONOTONIC to be always available is that there are currently operating systems that are not able to provide anything like TIME_MONOTONIC. See Ulrich's posting. I want to enable Ulrich to let glibc say on Linux 2.2 that TIME_MONOTONIC is not available. The reason why I allowed TIME_MONOTONIC to fail even when it has worked before in the same process is in order to allow an environment to signal to an application that there has been an unavoidable TIME_MONOTONIC discontinuity. The simplest example is a laptop with power management function enabled, where the Pentium can stop its clock and thereby also the TSC. Another more interesting example is an ATM security module using the DS5002FP processor with a battery stop enabled, or a DS1954 iButton that has been pulled off the socket prematurely by the user, which must not interrupt a transaction, but where it is security critical that the application is informed about the fact that the system can't provide any data on how long the full transaction has lasted, such that a secure path can be followed (in a crypto application this means usually to abort a transaction and invite a restart with new nonces). As I said, just a real world example. My API proposal does not guarantee that anything is available. I don't want to make such restrictions, because I want the API to be very widely implementable, and at the same time, I want it to make possible for implementors to use the API such that it never has to lie to the application. I just don't like APIs that lie to the application. Offering additional guarantees is the task of the documentation that comes with the API. It is perfectly possible to make this documentation also available as a compile-time or run-time parameter to the software, like we have in the form of the POSIX sysconf() mechanism. If you want additional useful requirements such as "TIME_MONOTONIC is always available", then please send me a list of these and I'd be happy to define for you a TIME_MONOTONIC_IS_ALWAYS_AVAILABLE flag for sysconf() and whatever else you need as guarantee flags from the implementation. An implementation would not be allowed to set this flag on e.g. a laptop where APM functions are active or could be easily activated, or on crypto modules, where power-downs are required to only pause but never abort protocol transactions. The Ada95 D.8 spec is actually much more generous, because it has only requirements for the documentations that come with the API: "The implementation shall document the properties of the underlying time base used for the clock and for type Time, such as the range of values supported and any relevant aspects of the underlying hardware or operating system facilities used. [...] The implementation shall document any aspects of the the external environment that could interfere with the clock behavior as defined in this clause." So the authors of the Ada95 real-time annex followed here as well the principle: We provide the implementor of the environment all the tools necessary to get it really right, but whether it was really done right, the user has to verify by reading the documentation. We require that the documentation talks about these things honestly and in sufficient detail. Markus -- Markus G. Kuhn, Computer Laboratory, University of Cambridge, UK Email: mkuhn at acm.org, WWW: <http://www.cl.cam.ac.uk/~mgk25/>
participants (4)
-
D. J. Bernstein
-
Markus Kuhn
-
Paul Eggert
-
Ulrich Drepper