Kernel release status [LWN.net]

Monotonicity of gettimeofday()

Posted Feb 20, 2003 18:21 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246) [Link]

I was under the impression that (a) gettimeofday always returned UTC and thus was immune to daylight savings time, and that (b) it tended to be monotonic and protocols like NTP try to keep it that way unless there is a gigantic drift.

If you have ntpd always running, then you may see slight changes in the rate of time passage, but you shouldn't see major discontinuities or time going backwards (until 2038 at least...). The man page for adjtime (under Solaris at least) echos this view:

The adjustment is effected by speeding up (if that amount of time is positive) or slowing down (if that amount of time is negative) the system's clock by some small percentage, gen- erally a fraction of one percent. The time is always a mono- tonically increasing function. A time correction from an earlier call to adjtime() may not be finished when adjtime() is called again.

I looked in kernel/time.c for Linux 2.4.20, and it mentions that Linux's time-keeping paradigm is based on NTP-style updates described in David L. Mill's paper on said topic. I looked in that paper, and it indicated that monotonicity is a goal of that algorithm.

I think it's safe to say, under normal circumstances, gettimeofday() is atomic. Only large time-setting events (eg. during bootup, or on restart of a dead NTP daemon) should you see any large shift in time, forwards or backwards.

Monotonicity of gettimeofday()

Posted Feb 20, 2003 18:42 UTC (Thu) by zooko (subscriber, #2589) [Link]

No offense, but I think this is the Unix "worse is better" heritage.

Suppose that you were writing an app that depends on time being monotonically non-decreasing. If this assumption fails, your house catches on fire. Now are you satisfied with this "under normal circumstances" position?

No, you're not. You want a slightly stronger guarantee. As in "under all circumstances unless there is a very peculiar electrical malfunction in your CPU".

I don't think it is too difficult to offer a guaranteed (up to peculiarly malfunctioning hardware) non-decreasing timer. The cost is that you just have to give up on the idea that this same timer is also reflecting human time (UTC). I have in fact implemented such a thing in user space for my app, but it is quite expensive to do in user space, and I would have to go through the filesystem in order to get the guarantee past the app shutting down. Ugh! That is an extremely expensive and awkward, compared to doing it in kernel land and storing the value in some nice battery-backed NVRAM or something.

Monotonicity of gettimeofday()

Posted Feb 20, 2003 20:06 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246) [Link]

If you want gettimeofday() to be non-decreasing, simply set your time once at bootup and don't run NTP or any other time adjustment daemon. The only thing that can make it non-monotonic is settimeofday().

The alternative is not that expensive. Here's an implementation off the top of my head that is monotonic non-decreasing for up to LONG_MAX seconds, so long as there aren't any shifts of time on the order of LONG_MAX/2:

void nondecreasing_gettimeofday(struct timeval *tv)
{
    static int first = 1;
    static struct timeval tv_adj, tv_prev;

    /* set our initial adjustment factor to 'now' so time starts at 0 */
    if (first)
    {
         gettimeofday(&tv_adj, NULL);
         first = 0;
    }

    gettimeofday(tv, NULL);

    tv->tv_sec  -= tv_adj.tv_sec;
    tv->tv_usec -= tv_adj.tv_usec;
    while (tv->tv_usec < 0) 
    { 
        tv->tv_sec--; 
        tv->tv_usec += 10000000; 
    }

    /* did time go backwards?  If so, make time sit still this time,
       and change our adjustment factor so we still see forward deltas. */
    if (tv->tv_sec < tv_prev.tv_sec ||
        (tv->tv_sec == tv_prev.tv_sec && 
         tv->tv_usec < tv_prev.tv_usec))
    {
        tv_adj.tv_sec  += tv_prev.tv_sec  - tv->tv_sec;
        tv_adj.tv_usec += tv_prev.tv_usec - tv->tv_usec;
        *tv = tv_prev;
    } else /* time went forward or stayed put, so remember it. */
    {
        tv_prev = *tv;
    }
}

I agree, it's not perfect. And it certainly has a touch of "good enough is the worst enemy of best." But I feel it's perfectly serviceable.

Monotonicity of gettimeofday()

Posted Feb 20, 2003 20:09 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246) [Link]

Oh, and you're right that you need to use the filesystem to get monotonicity across apps if they share timebases. That kinda sucks.

Bear in mind, though, that that's only a problem on systems that are running a time daemon that allows large time deltas. I think xntpd can be configured to avoid those, and the kernel mechanisms for adjtimex do support non-decreasing monotonic clocks.

Kernel release status

Posted Feb 20, 2003 22:50 UTC (Thu) by Ross (subscriber, #4065) [Link]

I think you are confused.

gettimeofday() should be strictly monotonic.

There have been bugs in the past with the kernel TSC implementation,
with SMP syncronization, etc.

The fact the system time is in UTC is one of the better design decisions in Unix. See Windows for a painful lesson in reimplemnting something incorrectly.

Some examples:
I am on the east coast and mount a filesystem from the west coast. The timestamps on files I create will be wrong on the west coast and all the current files will be wrong for me.

A user logs into my system from another timezone. They have no option see the time or file timestamps with their localtime. Actually they do, but now I also see them in their timezone.

Daylight saving comes and goes, but your computer wasn't on. Now it boots up. To tell if it should change the time it has to look at a registry entry.

I have a laptop and travel. I use a floppy disk in a system locally then put it in the laptop. The creation timestamp says 1:00 (PM). When was it created?

Kernel release status

Posted Feb 21, 2003 1:15 UTC (Fri) by zooko (subscriber, #2589) [Link]

I need a timer for internal scheduling purposes in my app. It need not be, and indeed should not be the same as the timer used for human-meaningful things like file timestamps. If it were the same, then the human sysadmin may need to change it, for example because his clock is out of sync with UTC, which breaks my app.

The whole "gettimeofday() is more or less much monotonically non-decreasing" argument is classic "worse is better" (and I mean "w-i-b" in the bad way here). gettimeofday() cannot guarantee both non-decreasing and synchronization with UTC. In practice, it fails in both of these sometimes. Failure to be synced to UTC is generally just a hassle for the human to deal with. Failure to be non-decreasing can cause unpredictable behavior in your applications that depend on non-decreasingness.

The worse-is-better approach is just to say "Yep, gettimeofday() tries to be non-decreasing. That's pretty much good.".

For what it's worth, I became intimately aware of this problem last year when my gettimeofday was experiencing jitter due to my laptop CPU slowing down to save energy. This manifested as events in my application code going off in a different order than I had specified them. Boy was that tricky to debug.

The worse-is-better approach is to change the behavior in this particular instance so that gettimeofday is non-decreasing even in the presence of CPU throttling. The Right Way To Do It is specify a service that actually guarantees non-decreasingness in all cases up to very unusual hardware failure or a bug in the implementation. Therefore, this service cannot also guarantee synchronization with UTC, so the Right Way To Do It is to specify clearly that this service is not synchronized in any way with UTC.

The fact that a lot of people don't understand the difference between these two approaches is the worse-is-better legacy.

Regards,

Zooko

Kernel release status

Posted Feb 21, 2003 6:07 UTC (Fri) by Ross (subscriber, #4065) [Link]

Yes, you are right that gettimeofday() can jump back if settimeofday() is used by the root user to change the time. Hmm... the root user, who is trusted with the ability to do anything, can break the monotonic guarantee. That's not surprising. The root user can break just about everything.

And I'm not saying you can't do time synchronization. You can. Getting the time right at boot is a start. Using NTP or something similar which doesn't change the time but changes the rate of time adjustment is another.

Of course if you absolutely don't trust it you can do it yourself. Just set up a timer and increment a variable yourself. Or use a separate process or thread doing usleep() or select(). It can't go backwards unless the system can somehow take back signals or scheduling time.

But don't forget, root can attach to your process with ptrace() and modify your variable. ;)

monotic time

Posted Feb 23, 2003 22:45 UTC (Sun) by giraffedata (subscriber, #1954) [Link]

Like most things in a computer, gettimeofday() is monotonic or not depending on what level you look at. If you look at it above the system administration policy level, it can be monotonic. Just establish a policy of not turning back the clock.

But any level below that, it is not monotonic. Ordinary system calls are provided to set the clock back. It is thus normal. And customary. And necessary.

We need to be able write programs that work in spite of system administration policy.

Within the kernel, nobody every uses the real time clock to measure passage of time. They use the 'jiffies' clock, which cannot be turned back at any level higher than "modifying the operating system." We need that at user level.

BTW, Daylight Savings Time is _not_ an issue here. It has always been possible to get absolute time (absolute time, whether it follows the UTC standard or not, doesn't vary according to where the sun appears or local custom).

monotic time

Posted Feb 27, 2003 6:56 UTC (Thu) by hpreg (guest, #9842) [Link]

"Within the kernel, nobody every uses the real time clock to measure passage of time. They use the 'jiffies' clock, which cannot be turned back at any level higher than 'modifying the operating system.' We need that at user level."

You already have it. And it is Posix.

man 2 times

monotonic time

Posted Feb 27, 2003 18:54 UTC (Thu) by zooko (subscriber, #2589) [Link]

Thanks! That's useful.

I still have two challenges to deal with, but the fundamental one of the clock running backward can be fixed by using this. Thanks again.

(Those two challenges are (a) communicating between processes e.g. IPC or storing persistent state between invocations, and (b) mapping to programmer-meaningful elapsed time by dividing by "clocks per second".)

Regards,

Zooko