Monotonicity of gettimeofday()

Posted Feb 20, 2003 18:21 UTC (Thu) by jzbiciak (guest, #5246)
In reply to: Kernel release status by zooko
Parent article: Kernel release status

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.

to post comments

Monotonicity of gettimeofday()

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

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 (guest, #5246) [Link] (1 responses)

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 (guest, #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.