Improved lib/qt_craft_monotonic() handling of overflow.

Improved the arithmetic and changed code to deal with wrap around
only if clock_t is 32-bits (and not to compile if it is less !).

Updated documentation.

2 files changed, 106 insertions, 40 deletions

diff --git a/lib/qtime.c b/lib/qtime.c
index 3e1e8269..413abefd 100644
--- a/lib/qtime.c
+++ b/lib/qtime.c
@@ -1,4 +1,4 @@
-/* Quagga Realtime Clock handling -- functions
+/* Quagga realtime and monotonic clock handling -- functions
  * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
  *
  * This file is part of GNU Zebra.
@@ -28,6 +28,11 @@
 /*==============================================================================
  * This is a collection of functions and (in qtime.h) macros and inline
  * functions which support system time and a monotonic clock.
+ *
+ * TODO: introduce mutex for crafted monotonic time, and initialisation
+ *       routine for that: which can preset the various variables... but
+ *       unless is guaranteed to be called, must leave the on-the-fly
+ *       initialisation...  could also start a watchdog at that point.
  */
 
 /*==============================================================================
@@ -41,29 +46,54 @@
  * is measured in units of sysconf(_SC_CLK_TCK) ticks per second.
  *
  * The only tricky bit is that the value returned (of type clock_t) is a
- * signed integer, which may wrap round.  It is not defined exactly how it
- * does this... but it is generally assumed that this_sample - last_sample will
- * give the time between the samples.
+ * signed integer, which can overflow.  It is not defined exactly how it
+ * does this... This code assumes that the system will wrap around in some
+ * obvious way.  The base of the time for this clock may be when the *system*
+ * started... so when it overflows may depend on how long the system has been
+ * up... which suggests that some sensible wrap around is likely (?).
  *
  * The qtime_t value is in nano-seconds.
  *
  * The result from times() is in units of sysconf(_SC_CLK_TCK) ticks per second.
  *
- * NB: it is assumed that qt_craft_monotonic will be called often enough to
- *     ensure that it is not fooled by the clock wrapping round.
+ * If clock_t is a signed 32-bit integer, which is kept +ve, then the clock
+ * overflows/wraps round in 2^31 ticks which is:
+ *
+ *   at     100 ticks/sec: > 248 days
+ *   at   1,000 ticks/sec: >  24 days
+ *   at  10,000 ticks/sec: >  59 hours
+ *
+ * For safety, this asserts that sysconf(_SC_CLK_TCK) <= 1,000,000 for
+ * sizeof(clock_t) > 4, but <= 1,000 for sizeof(clock_t) == 4.
+ *
+ * (It appears that 60, 100, 250 and 1,000 ticks/sec. are popular options.)
+ *
+ * If sizeof(clock_t) > 4, it is assumed large enough never to wrap around.
+ *
+ * When clock_t is a 32-bit integer must be at least ready for wrap around.
+ * There are two cases:
+ *
+ *   * +ve wrap around.  new < old value, and new >= 0
+ *
+ *       step = (INT32_MAX - old + 1) + new
  *
- *     Assuming that clock_t is a signed 32-bit integer, which is kept +ve,
- *     then the clock wraps round in 2^31 ticks which is:
+ *   * -ve wrap around.  new < old value, and new <  0 (and old > 0)
  *
- *       at     1,000 ticks/sec: > 24 days !
- *       at 1,000,000 ticks/sec: > 35 minutes
+ *       step = (INT32_MAX - old + 1) - (INT32_MIN - new)
  *
- *     So this should be a safe assumption -- particularly as 60, 100, 250 and
- *     1000 ticks per second appear to be the popular options.
+ * In any event, a step > 24 hours is taken to means that something has gone
+ * very, very badly wrong.
  *
- *     For safety, this asserts that sysconf(_SC_CLK_TCK) <= 1,000,000.
+ * NB: it is assumed that qt_craft_monotonic will be called often enough to
+ *     ensure that the check on the step size will not be triggered !
+ *
+ * NB: it is assumed that times() does not simply stick if it overflows.
+ *
+ * TODO: Add a watchdog to monitor the behaviour of this clock ?
  */
 
+CONFIRM((sizeof(clock_t) >= 4) && (sizeof(clock_t) <= 8)) ;
+
 #ifdef GNU_LINUX
 #define TIMES_TAKES_NULL 1
 #else
@@ -71,7 +101,9 @@
 #endif
 
 static uint64_t monotonic          = 0 ;  /* monotonic clock in _SC_CLK_TCK's */
-static uint64_t last_times_sample  = 0 ;  /* last value returned by times()   */
+static int64_t  last_times_sample  = 0 ;  /* last value returned by times()   */
+
+static uint64_t step_limit         = 0 ;  /* for sanity check                 */
 
 static int64_t  times_clk_tcks     = 0 ;  /* sysconf(_SC_CLK_TCK)             */
 static qtime_t  times_scale_q      = 0 ;  /* 10**9 / times_clk_tcks           */
@@ -80,7 +112,26 @@ static qtime_t  times_scale_r      = 0 ;  /* 10**9 % times_clk_tcks           */
 qtime_t
 qt_craft_monotonic(void) {
   struct tms dummy ;
-  uint64_t   this_times_sample ;
+  int64_t    this_times_sample ;
+  uint64_t   step ;
+
+  /* Set up times_scale_q & times_scale_q if not yet done.              */
+  if (times_clk_tcks == 0)      /* Is zero until it's initialized       */
+    {
+      ldiv_t qr ;
+      confirm(sizeof(qtime_t) <= sizeof(long int)) ;
+
+      times_clk_tcks = sysconf(_SC_CLK_TCK) ;
+      passert((times_clk_tcks > 0) &&
+              (times_clk_tcks <= (sizeof(clock_t) > 4) ? 1000000
+                                                       :    1000)) ;
+
+      qr = ldiv(QTIME_SECOND, times_clk_tcks) ;
+      times_scale_q = qr.quot ;
+      times_scale_r = qr.rem ;
+
+      step_limit = (uint64_t)24 * 60 * 60 * times_clk_tcks ;
+    } ;
 
   /* No errors are defined for times(), but a return of -1 is defined   */
   /* to indicate an error condition, with errno saying what it is !     */
@@ -94,7 +145,7 @@ qt_craft_monotonic(void) {
   this_times_sample = times(&dummy) ;
 #endif
 
-  if (this_times_sample == (uint64_t)-1)  /* deal with theoretical error  */
+  if (this_times_sample == -1)            /* deal with theoretical error  */
     {
        errno = 0 ;
        this_times_sample = times(&dummy) ;
@@ -102,24 +153,37 @@ qt_craft_monotonic(void) {
          zabort_errno("times() failed") ;
     } ;
 
-  /* Advance the monotonic clock in sysconf(_SC_CLK_TCK) units.         */
-  monotonic += (this_times_sample - last_times_sample) ;
+  /* Calculate the step and verify sensible.                            */
+  /*                                                                    */
+  /* Watch out for huge jumps and/or time going backwards.              */
+  /* For 32-bit clock_t, look out for wrap-around.                      */
 
-  /* Set up times_scale_q & times_scale_q if not yet done               */
-  if (times_clk_tcks == 0)      /* Is zero until it's initialized       */
+  if ((sizeof(clock_t) > 4) || (this_times_sample > last_times_sample))
+    /* time going backwards will appear as HUGE step forwards.          */
+    step = (uint64_t)(this_times_sample - last_times_sample) ;
+  else
     {
-      lldiv_t qr ;
-      confirm(sizeof(qtime_t) <= sizeof(long long int)) ;
+      if (this_times_sample > 0)
+        /* both samples +ve => +ve wrap around.                         */
+        step = (uint64_t)( ((int64_t)INT32_MAX - last_times_sample + 1)
+                                                        + this_times_sample  ) ;
+      else
+        /* this sample -ve and last sample +ve => -ve wrap round        */
+        /* this sample -ve and last sample -ve => time gone backwards   */
+        /*                     (which appears as a HUGE step forwards). */
+        step = (uint64_t)( ((int64_t)INT32_MAX - last_times_sample + 1)
+                                  - ((int64_t)INT32_MIN - this_times_sample) ) ;
+    } ;
 
-      times_clk_tcks = sysconf(_SC_CLK_TCK) ;
-      passert((times_clk_tcks > 0) && (times_clk_tcks <= 1000000)) ;
+  /*  TODO: better error messaging for large clock jumps.               */
+  if (step > step_limit)
+    zabort("Sudden large monotonic clock jump") ;
 
-      qr = lldiv(QTIME_SECOND, times_clk_tcks) ;
-      times_scale_q = qr.quot ;
-      times_scale_r = qr.rem ;
+  /* Advance the monotonic clock in sysconf(_SC_CLK_TCK) units.         */
+  monotonic += step ;
 
-      last_times_sample = this_times_sample ;
-    } ;
+  /* Remember what we got, for next time.                               */
+  last_times_sample = this_times_sample ;
 
   /* Scale to qtime_t units.                                            */
   if (times_scale_r == 0)
diff --git a/lib/qtime.h b/lib/qtime.h
index 4cfdd1fb..3f089f53 100644
--- a/lib/qtime.h
+++ b/lib/qtime.h
@@ -1,4 +1,4 @@
-/* Quagga Realtime Clock handling -- header
+/* Quagga realtime and monotonic clock handling -- header
  * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
  *
  * This file is part of GNU Zebra.
@@ -47,8 +47,8 @@
  *                 tv_usecs   micro-seconds
  *
  * Given a 64-bit integer it is much easier to do operations on a 64 bit
- * (signed) nano-second value.  That gives 34 bits for the seconds count, which
- * is > 290 years.
+ * (signed) nano-second value.  That gives > 34 bits for the seconds count,
+ * and counts from zero to > 290 years.
  */
 
 typedef int64_t qtime_t ;
@@ -92,10 +92,10 @@ qtime2timeval(struct timeval* p_tv, qtime_t qt) ;
  */
 
 Inline qtime_t
-qt_get_realtime(void) ;         /* clock_gettime(CLOCK_REALTIME, &ts)   */
+qt_get_realtime(void) ;         /* clock_gettime(CLOCK_REALTIME, ...)   */
 
 Inline qtime_t
-qt_get_monotonic(void) ;        /* clock_gettime(CLOCK_MONOTONIC, &ts   */
+qt_get_monotonic(void) ;        /* clock_gettime(CLOCK_MONOTONIC, ...)  */
                                 /* OR equivalent using times()          */
 
 Inline qtime_t                  /* monotonic time from CLOCK_REALTIME   */
@@ -181,7 +181,8 @@ qtime2timeval(struct timeval* p_tv, qtime_t qt)
 
 /* Read given clock & return a qtime_t value.
  *
- * Crunch, zabbort_errno, if fails: cannot continue with broken time value !
+ * While possibility of error is essentially theoretical, must treat it as a
+ * FATAL error -- cannot continue with broken time value !
  */
 
 Inline qtime_t
@@ -205,9 +206,10 @@ qt_get_timeofday(void)
   return timeval2qtime(&tv) ;
 }
 
-/* clock_gettime(CLOCK_REALTIME, &ts) -- returning qtime_t value
+/* clock_gettime(CLOCK_REALTIME, ...) -- returning qtime_t value
  *
- * Crunch, zabbort_errno, if fails: cannot continue with broken time value !
+ * While possibility of error is essentially theoretical, must treat it as a
+ * FATAL error -- cannot continue with broken time value !
  */
 Inline qtime_t
 qt_get_realtime(void)
@@ -215,10 +217,11 @@ qt_get_realtime(void)
   return qt_clock_gettime(CLOCK_REALTIME) ;
 } ;
 
-/* clock_gettime(CLOCK_MONOTONIC, &ts) OR qt_craft_monotonic()
+/* clock_gettime(CLOCK_MONOTONIC, ...) OR qt_craft_monotonic()
  *                                                   -- returning qtime_t value
  *
- * Crunch, zabbort_errno, if fails: cannot continue with broken time value !
+ * While possibility of error is essentially theoretical, must treat it as a
+ * FATAL error -- cannot continue with broken time value !
  */
 Inline qtime_t
 qt_get_monotonic(void)
@@ -232,7 +235,6 @@ qt_get_monotonic(void)
 
 /*==============================================================================
  * Conversion between realtime/timeofday and monotonic
- *
  */
 
 /* Convert a CLOCK_REALTIME time to our local monotonic time.           */