Merge branch 'monotonic_v2_squashed'

9 files changed, 699 insertions, 155 deletions

diff --git a/src/common/compat.c b/src/common/compat.c
index bae76f45db..081490d381 100644
--- a/src/common/compat.c
+++ b/src/common/compat.c
@@ -33,6 +33,12 @@
 #ifdef HAVE_SYS_STAT_H
 #include <sys/stat.h>
 #endif
+#ifdef HAVE_UTIME_H
+#include <utime.h>
+#endif
+#ifdef HAVE_SYS_UTIME_H
+#include <sys/utime.h>
+#endif
 #ifdef HAVE_UNISTD_H
 #include <unistd.h>
 #endif
@@ -89,12 +95,6 @@ SecureZeroMemory(PVOID ptr, SIZE_T cnt)
 #include "tor_readpassphrase.h"
 #endif
 
-#ifndef HAVE_GETTIMEOFDAY
-#ifdef HAVE_FTIME
-#include <sys/timeb.h>
-#endif
-#endif
-
 /* Includes for the process attaching prevention */
 #if defined(HAVE_SYS_PRCTL_H) && defined(__linux__)
 /* Only use the linux prctl;  the IRIX prctl is totally different */
@@ -116,12 +116,6 @@ SecureZeroMemory(PVOID ptr, SIZE_T cnt)
 #ifdef HAVE_SIGNAL_H
 #include <signal.h>
 #endif
-#ifdef HAVE_UTIME_H
-#include <utime.h>
-#endif
-#ifdef HAVE_SYS_UTIME_H
-#include <sys/utime.h>
-#endif
 #ifdef HAVE_SYS_MMAN_H
 #include <sys/mman.h>
 #endif
@@ -131,12 +125,6 @@ SecureZeroMemory(PVOID ptr, SIZE_T cnt)
 #ifdef HAVE_SYS_FILE_H
 #include <sys/file.h>
 #endif
-#ifdef TOR_UNIT_TESTS
-#if !defined(HAVE_USLEEP) && defined(HAVE_SYS_SELECT_H)
-/* as fallback implementation for tor_sleep_msec */
-#include <sys/select.h>
-#endif
-#endif
 
 #include "torlog.h"
 #include "util.h"
@@ -2836,53 +2824,6 @@ compute_num_cpus(void)
   return num_cpus;
 }
 
-/** Set *timeval to the current time of day.  On error, log and terminate.
- * (Same as gettimeofday(timeval,NULL), but never returns -1.)
- */
-void
-tor_gettimeofday(struct timeval *timeval)
-{
-#ifdef _WIN32
-  /* Epoch bias copied from perl: number of units between windows epoch and
-   * Unix epoch. */
-#define EPOCH_BIAS U64_LITERAL(116444736000000000)
-#define UNITS_PER_SEC U64_LITERAL(10000000)
-#define USEC_PER_SEC U64_LITERAL(1000000)
-#define UNITS_PER_USEC U64_LITERAL(10)
-  union {
-    uint64_t ft_64;
-    FILETIME ft_ft;
-  } ft;
-  /* number of 100-nsec units since Jan 1, 1601 */
-  GetSystemTimeAsFileTime(&ft.ft_ft);
-  if (ft.ft_64 < EPOCH_BIAS) {
-    /* LCOV_EXCL_START */
-    log_err(LD_GENERAL,"System time is before 1970; failing.");
-    exit(1);
-    /* LCOV_EXCL_STOP */
-  }
-  ft.ft_64 -= EPOCH_BIAS;
-  timeval->tv_sec = (unsigned) (ft.ft_64 / UNITS_PER_SEC);
-  timeval->tv_usec = (unsigned) ((ft.ft_64 / UNITS_PER_USEC) % USEC_PER_SEC);
-#elif defined(HAVE_GETTIMEOFDAY)
-  if (gettimeofday(timeval, NULL)) {
-    /* LCOV_EXCL_START */
-    log_err(LD_GENERAL,"gettimeofday failed.");
-    /* If gettimeofday dies, we have either given a bad timezone (we didn't),
-       or segfaulted.*/
-    exit(1);
-    /* LCOV_EXCL_STOP */
-  }
-#elif defined(HAVE_FTIME)
-  struct timeb tb;
-  ftime(&tb);
-  timeval->tv_sec = tb.time;
-  timeval->tv_usec = tb.millitm * 1000;
-#else
-#error "No way to get time."
-#endif
-  return;
-}
 
 #if !defined(_WIN32)
 /** Defined iff we need to add locks when defining fake versions of reentrant
@@ -3441,26 +3382,6 @@ get_total_system_memory(size_t *mem_out)
   return 0;
 }
 
-#ifdef TOR_UNIT_TESTS
-/** Delay for <b>msec</b> milliseconds.  Only used in tests. */
-void
-tor_sleep_msec(int msec)
-{
-#ifdef _WIN32
-  Sleep(msec);
-#elif defined(HAVE_USLEEP)
-  sleep(msec / 1000);
-  /* Some usleep()s hate sleeping more than 1 sec */
-  usleep((msec % 1000) * 1000);
-#elif defined(HAVE_SYS_SELECT_H)
-  struct timeval tv = { msec / 1000, (msec % 1000) * 1000};
-  select(0, NULL, NULL, NULL, &tv);
-#else
-  sleep(CEIL_DIV(msec, 1000));
-#endif
-}
-#endif
-
 /** Emit the password prompt <b>prompt</b>, then read up to <b>buflen</b>
  * bytes of passphrase into <b>output</b>. Return the number of bytes in
  * the passphrase, excluding terminating NUL.
diff --git a/src/common/compat.h b/src/common/compat.h
index 6f102becc2..54ab8b08e8 100644
--- a/src/common/compat.h
+++ b/src/common/compat.h
@@ -42,6 +42,8 @@
 #include <netinet6/in6.h>
 #endif
 
+#include "compat_time.h"
+
 #if defined(__has_feature)
 #  if __has_feature(address_sanitizer)
 /* Some of the fancy glibc strcmp() macros include references to memory that
@@ -379,15 +381,6 @@ const char *tor_fix_source_file(const char *fname);
 #endif
 
 /* ===== Time compatibility */
-#if !defined(HAVE_GETTIMEOFDAY) && !defined(HAVE_STRUCT_TIMEVAL_TV_SEC)
-/** Implementation of timeval for platforms that don't have it. */
-struct timeval {
-  time_t tv_sec;
-  unsigned int tv_usec;
-};
-#endif
-
-void tor_gettimeofday(struct timeval *timeval);
 
 struct tm *tor_localtime_r(const time_t *timep, struct tm *result);
 struct tm *tor_gmtime_r(const time_t *timep, struct tm *result);
@@ -737,10 +730,6 @@ char *format_win32_error(DWORD err);
 
 #endif
 
-#ifdef TOR_UNIT_TESTS
-void tor_sleep_msec(int msec);
-#endif
-
 #ifdef COMPAT_PRIVATE
 #if !defined(HAVE_SOCKETPAIR) || defined(_WIN32) || defined(TOR_UNIT_TESTS)
 #define NEED_ERSATZ_SOCKETPAIR
diff --git a/src/common/compat_libevent.c b/src/common/compat_libevent.c
index c5f73dc51a..4dab54493f 100644
--- a/src/common/compat_libevent.c
+++ b/src/common/compat_libevent.c
@@ -388,33 +388,3 @@ tor_gettimeofday_cache_set(const struct timeval *tv)
 #endif
 #endif
 
-/**
- * As tor_gettimeofday_cached, but can never move backwards in time.
- *
- * The returned value may diverge from wall-clock time, since wall-clock time
- * can trivially be adjusted backwards, and this can't.  Don't mix wall-clock
- * time with these values in the same calculation.
- *
- * Depending on implementation, this function may or may not "smooth out" huge
- * jumps forward in wall-clock time.  It may or may not keep its results
- * advancing forward (as opposed to stalling) if the wall-clock time goes
- * backwards.  The current implementation does neither of of these.
- *
- * This function is not thread-safe; do not call it outside the main thread.
- *
- * In future versions of Tor, this may return a time does not have its
- * origin at the Unix epoch.
- */
-void
-tor_gettimeofday_cached_monotonic(struct timeval *tv)
-{
-  struct timeval last_tv = { 0, 0 };
-
-  tor_gettimeofday_cached(tv);
-  if (timercmp(tv, &last_tv, OP_LT)) {
-    memcpy(tv, &last_tv, sizeof(struct timeval));
-  } else {
-    memcpy(&last_tv, tv, sizeof(struct timeval));
-  }
-}
-
diff --git a/src/common/compat_libevent.h b/src/common/compat_libevent.h
index 89b35c9faa..e64095bbfa 100644
--- a/src/common/compat_libevent.h
+++ b/src/common/compat_libevent.h
@@ -70,7 +70,6 @@ void tor_gettimeofday_cache_clear(void);
 #ifdef TOR_UNIT_TESTS
 void tor_gettimeofday_cache_set(const struct timeval *tv);
 #endif
-void tor_gettimeofday_cached_monotonic(struct timeval *tv);
 
 #ifdef COMPAT_LIBEVENT_PRIVATE
 
diff --git a/src/common/compat_time.c b/src/common/compat_time.c
new file mode 100644
index 0000000000..b7d69cf400
--- /dev/null
+++ b/src/common/compat_time.c
@@ -0,0 +1,513 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2016, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file compat_time.c
+ * \brief Portable wrappers for finding out the current time, running
+ *   timers, etc.
+ **/
+
+#define COMPAT_TIME_PRIVATE
+#include "compat.h"
+
+#ifdef _WIN32
+#include <winsock2.h>
+#include <windows.h>
+#endif
+
+#ifdef HAVE_SYS_TYPES_H
+#include <sys/types.h>
+#endif
+#ifdef HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+#ifdef TOR_UNIT_TESTS
+#if !defined(HAVE_USLEEP) && defined(HAVE_SYS_SELECT_H)
+/* as fallback implementation for tor_sleep_msec */
+#include <sys/select.h>
+#endif
+#endif
+
+#ifdef __APPLE__
+#include <mach/mach_time.h>
+#endif
+
+#include "torlog.h"
+#include "util.h"
+#include "container.h"
+
+#ifndef HAVE_GETTIMEOFDAY
+#ifdef HAVE_FTIME
+#include <sys/timeb.h>
+#endif
+#endif
+
+#ifdef TOR_UNIT_TESTS
+/** Delay for <b>msec</b> milliseconds.  Only used in tests. */
+void
+tor_sleep_msec(int msec)
+{
+#ifdef _WIN32
+  Sleep(msec);
+#elif defined(HAVE_USLEEP)
+  sleep(msec / 1000);
+  /* Some usleep()s hate sleeping more than 1 sec */
+  usleep((msec % 1000) * 1000);
+#elif defined(HAVE_SYS_SELECT_H)
+  struct timeval tv = { msec / 1000, (msec % 1000) * 1000};
+  select(0, NULL, NULL, NULL, &tv);
+#else
+  sleep(CEIL_DIV(msec, 1000));
+#endif
+}
+#endif
+
+/** Set *timeval to the current time of day.  On error, log and terminate.
+ * (Same as gettimeofday(timeval,NULL), but never returns -1.)
+ */
+void
+tor_gettimeofday(struct timeval *timeval)
+{
+#ifdef _WIN32
+  /* Epoch bias copied from perl: number of units between windows epoch and
+   * Unix epoch. */
+#define EPOCH_BIAS U64_LITERAL(116444736000000000)
+#define UNITS_PER_SEC U64_LITERAL(10000000)
+#define USEC_PER_SEC U64_LITERAL(1000000)
+#define UNITS_PER_USEC U64_LITERAL(10)
+  union {
+    uint64_t ft_64;
+    FILETIME ft_ft;
+  } ft;
+  /* number of 100-nsec units since Jan 1, 1601 */
+  GetSystemTimeAsFileTime(&ft.ft_ft);
+  if (ft.ft_64 < EPOCH_BIAS) {
+    /* LCOV_EXCL_START */
+    log_err(LD_GENERAL,"System time is before 1970; failing.");
+    exit(1);
+    /* LCOV_EXCL_STOP */
+  }
+  ft.ft_64 -= EPOCH_BIAS;
+  timeval->tv_sec = (unsigned) (ft.ft_64 / UNITS_PER_SEC);
+  timeval->tv_usec = (unsigned) ((ft.ft_64 / UNITS_PER_USEC) % USEC_PER_SEC);
+#elif defined(HAVE_GETTIMEOFDAY)
+  if (gettimeofday(timeval, NULL)) {
+    /* LCOV_EXCL_START */
+    log_err(LD_GENERAL,"gettimeofday failed.");
+    /* If gettimeofday dies, we have either given a bad timezone (we didn't),
+       or segfaulted.*/
+    exit(1);
+    /* LCOV_EXCL_STOP */
+  }
+#elif defined(HAVE_FTIME)
+  struct timeb tb;
+  ftime(&tb);
+  timeval->tv_sec = tb.time;
+  timeval->tv_usec = tb.millitm * 1000;
+#else
+#error "No way to get time."
+#endif
+  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;
+
+/* "ratchet" functions for monotonic time. */
+
+#if defined(_WIN32) || defined(TOR_UNIT_TESTS)
+
+/** 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;
+/* 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;
+
+/** 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;
+}
+#endif
+
+#if defined(MONOTIME_USING_GETTIMEOFDAY) || defined(TOR_UNIT_TESTS)
+static struct timeval last_timeofday = { 0, 0 };
+static struct timeval timeofday_offset = { 0, 0 };
+
+/** 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));
+  }
+}
+#endif
+
+#ifdef TOR_UNIT_TESTS
+/** For testing: reset all the ratchets */
+void
+monotime_reset_ratchets_for_testing(void)
+{
+  last_pctr = pctr_offset = last_tick_count = 0;
+  rollover_count = 0;
+  memset(&last_timeofday, 0, sizeof(struct timeval));
+  memset(&timeofday_offset, 0, sizeof(struct timeval));
+}
+#endif
+
+#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;
+
+/** Lock to protect last_pctr and pctr_offset */
+static CRITICAL_SECTION monotime_lock;
+/** Lock to protect rollover_count and last_tick_count */
+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) ?
+}
+
+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 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);
+}
+
+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;
+  if (BUG(monotime_initialized == 0)) {
+    monotime_init();
+  }
+
+  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)
+{
+  if (BUG(monotime_initialized == 0)) {
+    monotime_init();
+  }
+
+  monotime_coarse_t now;
+  monotime_coarse_get(&now);
+  return monotime_coarse_diff_nsec(&initialized_at_coarse, &now);
+}
+
+uint64_t
+monotime_coarse_absolute_usec(void)
+{
+  return monotime_coarse_absolute_nsec() / 1000;
+}
+
+uint64_t
+monotime_coarse_absolute_msec(void)
+{
+  return monotime_coarse_absolute_nsec() / ONE_MILLION;
+}
+#endif
diff --git a/src/common/compat_time.h b/src/common/compat_time.h
new file mode 100644
index 0000000000..8d61bc2580
--- /dev/null
+++ b/src/common/compat_time.h
@@ -0,0 +1,150 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * 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 {
+  time_t tv_sec;
+  unsigned int tv_usec;
+};
+#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
+#if defined(_WIN32) || defined(TOR_UNIT_TESTS)
+STATIC int64_t ratchet_performance_counter(int64_t count_raw);
+STATIC int64_t ratchet_coarse_performance_counter(int64_t count_raw);
+#endif
+#if defined(MONOTIME_USING_GETTIMEOFDAY) || defined(TOR_UNIT_TESTS)
+STATIC void ratchet_timeval(const struct timeval *timeval_raw,
+                            struct timeval *out);
+#endif
+#ifdef TOR_UNIT_TESTS
+void monotime_reset_ratchets_for_testing(void);
+#endif
+#endif
+
+#endif
+
diff --git a/src/common/include.am b/src/common/include.am
index 222afe0291..b0226802a8 100644
--- a/src/common/include.am
+++ b/src/common/include.am
@@ -83,6 +83,7 @@ LIBOR_A_SRC = \
   src/common/backtrace.c				\
   src/common/compat.c					\
   src/common/compat_threads.c				\
+  src/common/compat_time.c				\
   src/common/container.c				\
   src/common/log.c					\
   src/common/memarea.c					\
diff --git a/src/common/timers.c b/src/common/timers.c
index 2eb75a148b..41b2008ac4 100644
--- a/src/common/timers.c
+++ b/src/common/timers.c
@@ -19,9 +19,6 @@
 
 /* Notes:
  *
- * The use of tor_gettimeofday_cached_monotonic() is kind of ugly.  It would
- * be neat to fix it.
- *
  * Having a way to free all timers on shutdown would free people from the
  * need to track them.  Not sure if that's clever though.
  *
@@ -72,6 +69,8 @@ struct timeout_cb {
 static struct timeouts *global_timeouts = NULL;
 static struct event *global_timer_event = NULL;
 
+static monotime_t start_of_time;
+
 /** We need to choose this value carefully.  Because we're using timer wheels,
  * it actually costs us to have extra resolution we don't use.  So for now,
  * I'm going to define our resolution as .1 msec, and hope that's good enough.
@@ -95,9 +94,8 @@ static struct event *global_timer_event = NULL;
 /**
  * Convert the timeval in <b>tv</b> to a timeout_t, and return it.
  *
- * The output resolution is set by USEC_PER_TICK, and the time corresponding
- * to 0 is the same as the time corresponding to 0 from
- * tor_gettimeofday_cached_monotonic().
+ * The output resolution is set by USEC_PER_TICK. Only use this to convert
+ * delays to number of ticks; the time represented by 0 is undefined.
  */
 static timeout_t
 tv_to_timeout(const struct timeval *tv)
@@ -108,7 +106,8 @@ tv_to_timeout(const struct timeval *tv)
 }
 
 /**
- * Convert the timeout in <b>t</b> to a timeval in <b>tv_out</b>
+ * Convert the timeout in <b>t</b> to a timeval in <b>tv_out</b>. Only
+ * use this for delays, not absolute times.
  */
 static void
 timeout_to_tv(timeout_t t, struct timeval *tv_out)
@@ -122,12 +121,10 @@ timeout_to_tv(timeout_t t, struct timeval *tv_out)
  * Update the timer <b>tv</b> to the current time in <b>tv</b>.
  */
 static void
-timer_advance_to_cur_time(const struct timeval *tv)
+timer_advance_to_cur_time(const monotime_t *now)
 {
-  timeout_t cur_tick = tv_to_timeout(tv);
-  if (BUG(cur_tick < timeouts_get_curtime(global_timeouts))) {
-    cur_tick = timeouts_get_curtime(global_timeouts); // LCOV_EXCL_LINE
-  }
+  timeout_t cur_tick = CEIL_DIV(monotime_diff_usec(&start_of_time, now),
+                                USEC_PER_TICK);
   timeouts_update(global_timeouts, cur_tick);
 }
 
@@ -138,11 +135,12 @@ timer_advance_to_cur_time(const struct timeval *tv)
 static void
 libevent_timer_reschedule(void)
 {
-  struct timeval now;
-  tor_gettimeofday_cached_monotonic(&now);
+  monotime_t now;
+  monotime_get(&now);
   timer_advance_to_cur_time(&now);
 
   timeout_t delay = timeouts_timeout(global_timeouts);
+
   struct timeval d;
   if (delay > MIN_CHECK_TICKS)
     delay = MIN_CHECK_TICKS;
@@ -161,9 +159,8 @@ libevent_timer_callback(evutil_socket_t fd, short what, void *arg)
   (void)what;
   (void)arg;
 
-  struct timeval now;
-  tor_gettimeofday_cache_clear();
-  tor_gettimeofday_cached_monotonic(&now);
+  monotime_t now;
+  monotime_get(&now);
   timer_advance_to_cur_time(&now);
 
   tor_timer_t *t;
@@ -171,7 +168,6 @@ libevent_timer_callback(evutil_socket_t fd, short what, void *arg)
     t->callback.cb(t, t->callback.arg, &now);
   }
 
-  tor_gettimeofday_cache_clear();
   libevent_timer_reschedule();
 }
 
@@ -194,6 +190,9 @@ timers_initialize(void)
     // LCOV_EXCL_STOP
   }
 
+  monotime_init();
+  monotime_get(&start_of_time);
+
   struct event *timer_event;
   timer_event = tor_event_new(tor_libevent_get_base(),
                               -1, 0, libevent_timer_callback, NULL);
@@ -256,24 +255,25 @@ timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg)
 }
 
 /**
- * Schedule the timer t to fire at the current time plus a delay of <b>tv</b>.
- * All times are relative to tor_gettimeofday_cached_monotonic.
+ * Schedule the timer t to fire at the current time plus a delay of
+ * <b>delay</b> microseconds.  All times are relative to monotime_get().
  */
 void
 timer_schedule(tor_timer_t *t, const struct timeval *tv)
 {
-  const timeout_t when = tv_to_timeout(tv);
-  struct timeval now;
-  tor_gettimeofday_cached_monotonic(&now);
+  const timeout_t delay = tv_to_timeout(tv);
+
+  monotime_t now;
+  monotime_get(&now);
   timer_advance_to_cur_time(&now);
 
   /* Take the old timeout value. */
   timeout_t to = timeouts_timeout(global_timeouts);
 
-  timeouts_add(global_timeouts, t, when);
+  timeouts_add(global_timeouts, t, delay);
 
   /* Should we update the libevent timer? */
-  if (to <= when) {
+  if (to <= delay) {
     return; /* we're already going to fire before this timer would trigger. */
   }
   libevent_timer_reschedule();
diff --git a/src/common/timers.h b/src/common/timers.h
index 594cf38a64..2c36af172d 100644
--- a/src/common/timers.h
+++ b/src/common/timers.h
@@ -7,8 +7,9 @@
 #include "orconfig.h"
 #include "testsupport.h"
 
+struct monotime_t;
 typedef struct timeout tor_timer_t;
-typedef void (*timer_cb_fn_t)(tor_timer_t *, void *, const struct timeval *);
+typedef void (*timer_cb_fn_t)(tor_timer_t *, void *, const struct monotime_t *);
 tor_timer_t *timer_new(timer_cb_fn_t cb, void *arg);
 void timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg);
 void timer_schedule(tor_timer_t *t, const struct timeval *delay);