Basic portable monotonic timer implementation

This code uses QueryPerformanceCounter() [**] on Windows,
mach_absolute_time() on OSX, clock_gettime() where available, and
gettimeofday() [*] elsewhere.

Timer types are stored in an opaque OS-specific format; the only
supported operation is to compute the difference between two timers.

[*] As you know, gettimeofday() isn't monotonic, so we include
a simple ratchet function to ensure that it only moves forward.

[**] As you may not know, QueryPerformanceCounter() isn't actually
always as monotonic as you might like it to be, so we ratchet that
one too.

We also include a "coarse monotonic timer" for cases where we don't
actually need high-resolution time.  This is GetTickCount{,64}() on
Windows, clock_gettime(CLOCK_MONOTONIC_COARSE) on Linux, and falls
back to regular monotonic time elsewhere.

2 files changed, 501 insertions, 1 deletions

diff --git a/src/common/compat_time.c b/src/common/compat_time.c
index 866c288fe6..bbbca33ca5 100644
--- a/src/common/compat_time.c
+++ b/src/common/compat_time.c
@@ -9,7 +9,7 @@
  *   timers, etc.
  **/
 
-#define COMPAT_PRIVATE
+#define COMPAT_TIME_PRIVATE
 #include "compat.h"
 
 #ifdef _WIN32
@@ -30,6 +30,10 @@
 #endif
 #endif
 
+#ifdef __APPLE__
+#include <mach/mach_time.h>
+#endif
+
 #include "torlog.h"
 #include "util.h"
 #include "container.h"
@@ -108,3 +112,378 @@ tor_gettimeofday(struct timeval *timeval)
   return;
 }
 
+#define ONE_MILLION ((int64_t) (1000 * 1000))
+#define ONE_BILLION ((int64_t) (1000 * 1000 * 1000))
+
+/** True iff monotime_init has been called. */
+static int monotime_initialized = 0;
+
+#ifdef __APPLE__
+
+/** Initialized on startup: tells is how to convert from ticks to
+ * nanoseconds.
+ */
+static struct mach_timebase_info mach_time_info;
+
+static void
+monotime_init_internal(void)
+{
+  tor_assert(!monotime_initialized);
+  int r = mach_timebase_info(&mach_time_info);
+  tor_assert(r == 0);
+  tor_assert(mach_time_info.denom != 0);
+}
+
+/**
+ * Set "out" to the most recent monotonic time value
+ */
+void
+monotime_get(monotime_t *out)
+{
+  out->abstime_ = mach_absolute_time();
+}
+
+/**
+ * Return the number of nanoseconds between <b>start</b> and <b>end</b>.
+ */
+int64_t
+monotime_diff_nsec(const monotime_t *start,
+                   const monotime_t *end)
+{
+  if (BUG(mach_time_info.denom == 0)) {
+    monotime_init();
+  }
+  const int64_t diff_ticks = end->abstime_ - start->abstime_;
+  const int64_t diff_nsec =
+    (diff_ticks * mach_time_info.numer) / mach_time_info.denom;
+  return diff_nsec;
+}
+
+/* end of "__APPLE__" */
+#elif defined(HAVE_CLOCK_GETTIME)
+
+static void
+monotime_init_internal(void)
+{
+  /* no action needed. */
+}
+
+void
+monotime_get(monotime_t *out)
+{
+  int r = clock_gettime(CLOCK_MONOTONIC, &out->ts_);
+  tor_assert(r == 0);
+}
+
+#ifdef CLOCK_MONOTONIC_COARSE
+void
+monotime_coarse_get(monotime_coarse_t *out)
+{
+  int r = clock_gettime(CLOCK_MONOTONIC_COARSE, &out->ts_);
+  tor_assert(r == 0);
+}
+#endif
+
+int64_t
+monotime_diff_nsec(const monotime_t *start,
+                   const monotime_t *end)
+{
+  const int64_t diff_sec = end->ts_.tv_sec - start->ts_.tv_sec;
+  const int64_t diff_nsec = diff_sec * ONE_BILLION +
+    (end->ts_.tv_nsec - start->ts_.tv_nsec);
+
+  return diff_nsec;
+}
+
+/* end of "HAVE_CLOCK_GETTIME" */
+#elif defined (_WIN32)
+
+/** Result of QueryPerformanceFrequency, as an int64_t. */
+static int64_t ticks_per_second = 0;
+
+/** Protected by lock: last value returned by monotime_get(). */
+static int64_t last_pctr = 0;
+/** Protected by lock: offset we must add to monotonic time values. */
+static int64_t pctr_offset = 0;
+/** Lock to protect last_pctr and pctr_offset */
+static CRITICAL_SECTION monotime_lock;
+/* If we are using GetTickCount(), how many times has it rolled over? */
+static uint32_t rollover_count = 0;
+/* If we are using GetTickCount(), what's the last value it returned? */
+static int64_t last_tick_count = 0;
+/** Lock to protect rollover_count and */
+static CRITICAL_SECTION monotime_coarse_lock;
+
+typedef ULONGLONG (WINAPI *GetTickCount64_fn_t)(void);
+static GetTickCount64_fn_t GetTickCount64_fn = NULL;
+
+static void
+monotime_init_internal(void)
+{
+  tor_assert(!monotime_initialized);
+  BOOL ok = InitializeCriticalSectionAndSpinCount(&monotime_lock, 200);
+  tor_assert(ok);
+  ok = InitializeCriticalSectionAndSpinCount(&monotime_coarse_lock, 200);
+  tor_assert(ok);
+  LARGE_INTEGER li;
+  ok = QueryPerformanceFrequency(&li);
+  tor_assert(ok);
+  tor_assert(li.QuadPart);
+  ticks_per_second = li.QuadPart;
+  last_pctr = 0;
+  pctr_offset = 0;
+
+  HANDLE h = load_windows_system_library(TEXT("kernel32.dll"));
+  if (h) {
+    GetTickCount64_fn = (GetTickCount64_fn_t)
+      GetProcAddress(h, "GetTickCount64");
+  }
+  // FreeLibrary(h) ?
+}
+
+/** Helper for windows: Called with a sequence of times that are supposed
+ * to be monotonic; increments them as appropriate so that they actually
+ * _are_ monotonic.
+ *
+ * Caller must hold lock. */
+STATIC int64_t
+ratchet_performance_counter(int64_t count_raw)
+{
+  /* must hold lock */
+  const int64_t count_adjusted = count_raw + pctr_offset;
+
+  if (PREDICT_UNLIKELY(count_adjusted < last_pctr)) {
+    /* Monotonicity failed! Pretend no time elapsed. */
+    pctr_offset = last_pctr - count_raw;
+    return last_pctr;
+  } else {
+    last_pctr = count_adjusted;
+    return count_adjusted;
+  }
+}
+
+STATIC int64_t
+ratchet_coarse_performance_counter(const int64_t count_raw)
+{
+  int64_t count = count_raw + (((int64_t)rollover_count) << 32);
+  while (PREDICT_UNLIKELY(count < last_tick_count)) {
+    ++rollover_count;
+    count = count_raw + (((int64_t)rollover_count) << 32);
+  }
+  last_tick_count = count;
+  return count;
+}
+
+void
+monotime_get(monotime_t *out)
+{
+  if (BUG(monotime_initialized == 0)) {
+    monotime_init();
+  }
+
+  /* Alas, QueryPerformanceCounter is not always monotonic: see bug list at
+
+    https://www.python.org/dev/peps/pep-0418/#windows-queryperformancecounter
+   */
+
+  EnterCriticalSection(&monotime_lock);
+  LARGE_INTEGER res;
+  BOOL ok = QueryPerformanceCounter(&res);
+  tor_assert(ok);
+  const int64_t count_raw = res.QuadPart;
+  out->pcount_ = ratchet_performance_counter(count_raw);
+  LeaveCriticalSection(&monotime_lock);
+}
+
+void
+monotime_coarse_get(monotime_coarse_t *out)
+{
+  if (GetTickCount64_fn) {
+    out->tick_count_ = (int64_t)GetTickCount64_fn();
+  } else {
+    EnterCriticalSection(&monotime_coarse_lock);
+    DWORD tick = GetTickCount();
+    out->tick_count_ = ratchet_coarse_performance_counter(tick);
+    LeaveCriticalSection(&monotime_coarse_lock);
+  }
+}
+
+int64_t
+monotime_diff_nsec(const monotime_t *start,
+                   const monotime_t *end)
+{
+  if (BUG(monotime_initialized == 0)) {
+    monotime_init();
+  }
+  const int64_t diff_ticks = end->pcount_ - start->pcount_;
+  return (diff_ticks * ONE_BILLION) / ticks_per_second;
+}
+
+int64_t
+monotime_coarse_diff_msec(const monotime_coarse_t *start,
+                          const monotime_coarse_t *end)
+{
+  const int64_t diff_ticks = end->tick_count_ - start->tick_count_;
+  return diff_ticks;
+}
+
+int64_t
+monotime_coarse_diff_usec(const monotime_coarse_t *start,
+                          const monotime_coarse_t *end)
+{
+  return monotime_coarse_diff_msec(start, end) * 1000;
+}
+
+int64_t
+monotime_coarse_diff_nsec(const monotime_coarse_t *start,
+                          const monotime_coarse_t *end)
+{
+  return monotime_coarse_diff_msec(start, end) * ONE_MILLION;
+}
+
+/* end of "_WIN32" */
+#elif defined(MONOTIME_USING_GETTIMEOFDAY)
+
+static int monotime_initialized = 0;
+static struct timeval last_timeofday = { 0, 0 };
+static struct timeval timeofday_offset = { 0, 0 };
+static tor_mutex_t monotime_lock;
+
+/** Initialize the monotonic timer subsystem. */
+static void
+monotime_init_internal(void)
+{
+  tor_assert(!monotime_initialized);
+  tor_mutex_init(&monotime_lock);
+}
+
+/** Helper for gettimeofday(): Called with a sequence of times that are
+ * supposed to be monotonic; increments them as appropriate so that they
+ * actually _are_ monotonic.
+ *
+ * Caller must hold lock. */
+STATIC void
+ratchet_timeval(const struct timeval *timeval_raw, struct timeval *out)
+{
+  /* must hold lock */
+  timeradd(timeval_raw, &timeofday_offset, out);
+  if (PREDICT_UNLIKELY(timercmp(out, &last_timeofday, <))) {
+    /* time ran backwards. Instead, declare that no time occurred. */
+    timersub(&last_timeofday, timeval_raw, &timeofday_offset);
+    memcpy(out, &last_timeofday, sizeof(struct timeval));
+  } else {
+    memcpy(&last_timeofday, out, sizeof(struct timeval));
+  }
+}
+
+void
+monotime_get(monotime_t *out)
+{
+  if (BUG(monotime_initialized == 0)) {
+    monotime_init();
+  }
+
+  tor_mutex_acquire(&monotime_lock);
+  struct timeval timeval_raw;
+  tor_gettimeofday(&timeval_raw);
+  ratchet_timeval(&timeval_raw, &out->tv_);
+  tor_mutex_release(&monotime_lock);
+}
+
+int64_t
+monotime_diff_nsec(const monotime_t *start,
+                   const monotime_t *end)
+{
+  struct timeval diff;
+  timersub(&end->tv_, &start->tv_, &diff);
+  return (diff.tv_sec * ONE_BILLION + diff.tv_usec * 1000);
+}
+
+/* end of "MONOTIME_USING_GETTIMEOFDAY" */
+#else
+#error "No way to implement monotonic timers."
+#endif
+
+static monotime_t initialized_at;
+#ifdef MONOTIME_COARSE_FN_IS_DIFFERENT
+static monotime_coarse_t initialized_at_coarse;
+#endif
+
+/**
+ * Initialize the monotonic timer subsystem. Must be called before any
+ * monotonic timer functions. This function is idempotent.
+ */
+void
+monotime_init(void)
+{
+  if (!monotime_initialized) {
+    monotime_init_internal();
+    monotime_get(&initialized_at);
+#ifdef MONOTIME_COARSE_FN_IS_DIFFERENT
+    monotime_coarse_get(&initialized_at_coarse);
+#endif
+    monotime_initialized = 1;
+  }
+}
+
+int64_t
+monotime_diff_usec(const monotime_t *start,
+                   const monotime_t *end)
+{
+  const int64_t nsec = monotime_diff_nsec(start, end);
+  return CEIL_DIV(nsec, 1000);
+}
+
+int64_t
+monotime_diff_msec(const monotime_t *start,
+                   const monotime_t *end)
+{
+  const int64_t nsec = monotime_diff_nsec(start, end);
+  return CEIL_DIV(nsec, ONE_MILLION);
+}
+
+uint64_t
+monotime_absolute_nsec(void)
+{
+  monotime_t now;
+  monotime_get(&now);
+  return monotime_diff_nsec(&initialized_at, &now);
+}
+
+uint64_t
+monotime_absolute_usec(void)
+{
+  return monotime_absolute_nsec() / 1000;
+}
+
+uint64_t
+monotime_absolute_msec(void)
+{
+  return monotime_absolute_nsec() / ONE_MILLION;
+}
+
+#ifdef MONOTIME_COARSE_FN_IS_DIFFERENT
+uint64_t
+monotime_coarse_absolute_nsec(void)
+{
+  monotime_coarse_t now;
+  monotime_coarse_get(&now);
+  return monotime_coarse_diff_nsec(&initialized_at_coarse, &now);
+}
+
+uint64_t
+monotime_coarse_absolute_usec(void)
+{
+  monotime_coarse_t now;
+  monotime_coarse_get(&now);
+  return monotime_coarse_diff_usec(&initialized_at_coarse, &now);
+}
+
+uint64_t
+monotime_coarse_absolute_msec(void)
+{
+  monotime_coarse_t now;
+  monotime_coarse_get(&now);
+  return monotime_coarse_diff_msec(&initialized_at_coarse, &now);
+}
+#endif
diff --git a/src/common/compat_time.h b/src/common/compat_time.h
index 56126ba84c..d69af8f98c 100644
--- a/src/common/compat_time.h
+++ b/src/common/compat_time.h
@@ -3,11 +3,28 @@
  * Copyright (c) 2007-2016, The Tor Project, Inc. */
 /* See LICENSE for licensing information */
 
+/**
+ * \file compat_time.h
+ *
+ * \brief Functions and types for monotonic times.
+ *
+ * monotime_* functions try to provide a high-resolution monotonic timer with
+ * something the best resolution the system provides.  monotime_coarse_*
+ * functions run faster (if the operating system gives us a way to do that)
+ * but produce a less accurate timer: accuracy will probably be on the order
+ * of tens of milliseconds.
+ */
+
 #ifndef TOR_COMPAT_TIME_H
 #define TOR_COMPAT_TIME_H
 
 #include "orconfig.h"
 
+#if defined(HAVE_CLOCK_GETTIME)
+/* to ensure definition of CLOCK_MONOTONIC_COARSE if it's there */
+#include <time.h>
+#endif
+
 #if !defined(HAVE_GETTIMEOFDAY) && !defined(HAVE_STRUCT_TIMEVAL_TV_SEC)
 /** Implementation of timeval for platforms that don't have it. */
 struct timeval {
@@ -16,11 +33,115 @@ struct timeval {
 };
 #endif
 
+/** Represents a monotonic timer in a platform-dependent way. */
+typedef struct monotime_t {
+#ifdef __APPLE__
+  /* On apple, there is a 64-bit counter whose precision we must look up. */
+  uint64_t abstime_;
+#elif defined(HAVE_CLOCK_GETTIME)
+  /* It sure would be nice to use clock_gettime(). Posix is a nice thing. */
+  struct timespec ts_;
+#elif defined (_WIN32)
+  /* On Windows, there is a 64-bit counter whose precision we must look up. */
+  int64_t pcount_;
+#else
+#define MONOTIME_USING_GETTIMEOFDAY
+  /* Otherwise, we will be stuck using gettimeofday. */
+  struct timeval tv_;
+#endif
+} monotime_t;
+
+#if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_MONOTONIC_COARSE)
+#define MONOTIME_COARSE_FN_IS_DIFFERENT
+#define monotime_coarse_t monotime_t
+#elif defined(_WIN32)
+#define MONOTIME_COARSE_FN_IS_DIFFERENT
+#define MONOTIME_COARSE_TYPE_IS_DIFFERENT
+/** Represents a coarse monotonic time in a platform-independent way. */
+typedef struct monotime_coarse_t {
+  uint64_t tick_count_;
+} monotime_coarse_t;
+#else
+#define monotime_coarse_t monotime_t
+#endif
+
+/**
+ * Initialize the timing subsystem. This function is idempotent.
+ */
+void monotime_init(void);
+/**
+ * Set <b>out</b> to the current time.
+ */
+void monotime_get(monotime_t *out);
+/**
+ * Return the number of nanoseconds between <b>start</b> and <b>end</b>.
+ */
+int64_t monotime_diff_nsec(const monotime_t *start, const monotime_t *end);
+/**
+ * Return the number of microseconds between <b>start</b> and <b>end</b>.
+ */
+int64_t monotime_diff_usec(const monotime_t *start, const monotime_t *end);
+/**
+ * Return the number of milliseconds between <b>start</b> and <b>end</b>.
+ */
+int64_t monotime_diff_msec(const monotime_t *start, const monotime_t *end);
+/**
+ * Return the number of nanoseconds since the timer system was initialized.
+ */
+uint64_t monotime_absolute_nsec(void);
+/**
+ * Return the number of microseconds since the timer system was initialized.
+ */
+uint64_t monotime_absolute_usec(void);
+/**
+ * Return the number of milliseconds since the timer system was initialized.
+ */
+uint64_t monotime_absolute_msec(void);
+
+#if defined(MONOTIME_COARSE_FN_IS_DIFFERENT)
+/**
+ * Set <b>out</b> to the current coarse time.
+ */
+void monotime_coarse_get(monotime_coarse_t *out);
+uint64_t monotime_coarse_absolute_nsec(void);
+uint64_t monotime_coarse_absolute_usec(void);
+uint64_t monotime_coarse_absolute_msec(void);
+#else
+#define monotime_coarse_get monotime_get
+#define monotime_coarse_absolute_nsec monotime_absolute_nsec
+#define monotime_coarse_absolute_usec monotime_absolute_usec
+#define monotime_coarse_absolute_msec monotime_absolute_msec
+#endif
+
+#if defined(MONOTIME_COARSE_TYPE_IS_DIFFERENT)
+int64_t monotime_coarse_diff_nsec(const monotime_coarse_t *start,
+    const monotime_coarse_t *end);
+int64_t monotime_coarse_diff_usec(const monotime_coarse_t *start,
+    const monotime_coarse_t *end);
+int64_t monotime_coarse_diff_msec(const monotime_coarse_t *start,
+    const monotime_coarse_t *end);
+#else
+#define monotime_coarse_diff_nsec monotime_diff_nsec
+#define monotime_coarse_diff_usec monotime_diff_usec
+#define monotime_coarse_diff_msec monotime_diff_msec
+#endif
+
 void tor_gettimeofday(struct timeval *timeval);
 
 #ifdef TOR_UNIT_TESTS
 void tor_sleep_msec(int msec);
 #endif
 
+#ifdef COMPAT_TIME_PRIVATE
+#ifdef _WIN32
+STATIC int64_t ratchet_performance_counter(int64_t count_raw);
+STATIC int64_t ratchet_coarse_performance_counter(int64_t count_raw);
+#endif
+#ifdef MONOTIME_USING_GETTIMEOFDAY
+STATIC void ratchet_timeval(const struct timeval *timeval_raw,
+                            struct timeval *out);
+#endif
+#endif
+
 #endif