Add a new notion of "stamps" to be a fast 32-bit monotonic timestamp

The goal here is to replace our use of msec-based timestamps with
something less precise, but easier to calculate.  We're doing this
because calculating lots of msec-based timestamps requires lots of
64/32 division operations, which can be inefficient on 32-bit
platforms.

We make sure that these stamps can be calculated using only the
coarse monotonic timer and 32-bit bitwise operations.

4 files changed, 97 insertions, 5 deletions

diff --git a/src/common/buffers.c b/src/common/buffers.c
index c45e13d551..e0ef0dc773 100644
--- a/src/common/buffers.c
+++ b/src/common/buffers.c
@@ -472,7 +472,7 @@ buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped)
     chunk = chunk_new_with_alloc_size(buf_preferred_chunk_size(capacity));
   }
 
-  chunk->inserted_time = (uint32_t)monotime_coarse_absolute_msec();
+  chunk->inserted_time = monotime_coarse_get_stamp();
 
   if (buf->tail) {
     tor_assert(buf->head);
@@ -487,8 +487,8 @@ buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped)
 }
 
 /** Return the age of the oldest chunk in the buffer <b>buf</b>, in
- * milliseconds.  Requires the current monotonic time, in truncated msec,
- * as its input <b>now</b>.
+ * timestamp units.  Requires the current monotonic timestamp as its
+ * input <b>now</b>.
  */
 uint32_t
 buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now)
diff --git a/src/common/buffers.h b/src/common/buffers.h
index 1eaa5f2d04..fe392d268f 100644
--- a/src/common/buffers.h
+++ b/src/common/buffers.h
@@ -79,8 +79,7 @@ typedef struct chunk_t {
   size_t DBG_alloc;
 #endif
   char *data; /**< A pointer to the first byte of data stored in <b>mem</b>. */
-  uint32_t inserted_time; /**< Timestamp in truncated ms since epoch
-                           * when this chunk was inserted. */
+  uint32_t inserted_time; /**< Timestamp when this chunk was inserted. */
   char mem[FLEXIBLE_ARRAY_MEMBER]; /**< The actual memory used for storage in
                 * this chunk. */
 } chunk_t;
diff --git a/src/common/compat_time.c b/src/common/compat_time.c
index 1ce6f5ce4e..fe0209c8f2 100644
--- a/src/common/compat_time.c
+++ b/src/common/compat_time.c
@@ -279,6 +279,7 @@ monotime_reset_ratchets_for_testing(void)
  * nanoseconds.
  */
 static struct mach_timebase_info mach_time_info;
+static int monotime_shift = 0;
 
 static void
 monotime_init_internal(void)
@@ -287,6 +288,14 @@ monotime_init_internal(void)
   int r = mach_timebase_info(&mach_time_info);
   tor_assert(r == 0);
   tor_assert(mach_time_info.denom != 0);
+
+  {
+    // approximate only.
+    uint64_t ns_per_tick = mach_time_info.numer / mach_time_info.denom;
+    uint64_t ms_per_tick = ns_per_tick * ONE_MILLION;
+    // requires that tor_log2(0) == 0.
+    monotime_shift = tor_log2(ms_per_tick);
+  }
 }
 
 /**
@@ -321,6 +330,12 @@ monotime_diff_nsec(const monotime_t *start,
   return diff_nsec;
 }
 
+uint32_t
+monotime_coarse_to_stamp(const monotime_coarse_t *t)
+{
+  return (uint32_t)(t->abstime_ >> monotime_shift);
+}
+
 /* end of "__APPLE__" */
 #elif defined(HAVE_CLOCK_GETTIME)
 
@@ -399,6 +414,18 @@ monotime_diff_nsec(const monotime_t *start,
   return diff_nsec;
 }
 
+/* This value is ONE_BILLION >> 20. */
+const uint32_t STAMP_TICKS_PER_SECOND = 953;
+
+uint32_t
+monotime_coarse_to_stamp(const monotime_coarse_t *t)
+{
+  uint32_t nsec = (uint32_t)t->ts_.tv_nsec;
+  uint32_t sec = (uint32_t)t->ts_.tv_sec;
+
+  return (sec * STAMP_TICKS_PER_SECOND) + (nsec >> 20);
+}
+
 /* end of "HAVE_CLOCK_GETTIME" */
 #elif defined (_WIN32)
 
@@ -531,6 +558,14 @@ monotime_coarse_diff_nsec(const monotime_coarse_t *start,
   return monotime_coarse_diff_msec(start, end) * ONE_MILLION;
 }
 
+const uint32_t STAMP_TICKS_PER_SECOND = 1000;
+
+uint32_t
+monotime_coarse_to_stamp(const monotime_coarse_t *t)
+{
+  return (uint32_t) t->tick_count;
+}
+
 /* end of "_WIN32" */
 #elif defined(MONOTIME_USING_GETTIMEOFDAY)
 
@@ -567,6 +602,17 @@ monotime_diff_nsec(const monotime_t *start,
   return (diff.tv_sec * ONE_BILLION + diff.tv_usec * 1000);
 }
 
+/* This value is ONE_MILLION >> 10. */
+const uint32_t STAMP_TICKS_PER_SECOND = 976;
+
+uint32_t
+monotime_coarse_to_stamp(const monotime_coarse_t *t)
+{
+  const uint32_t usec = (uint32_t)t->tv_.tv_usec;
+  const uint32_t sec = (uint32_t)t->tv_.tv_sec;
+  return (sec * STAMP_TICKS_PER_SECOND) | (nsec >> 10);
+}
+
 /* end of "MONOTIME_USING_GETTIMEOFDAY" */
 #else
 #error "No way to implement monotonic timers."
@@ -653,5 +699,35 @@ monotime_coarse_absolute_msec(void)
 {
   return monotime_coarse_absolute_nsec() / ONE_MILLION;
 }
+#else
+#define initalized_at_coarse initialized_at
 #endif /* defined(MONOTIME_COARSE_FN_IS_DIFFERENT) */
 
+/**
+ * Return the current time "stamp" as described by monotime_coarse_to_stamp.
+ */
+uint32_t
+monotime_coarse_get_stamp(void)
+{
+  monotime_coarse_t now;
+  monotime_coarse_get(&now);
+  return monotime_coarse_to_stamp(&now);
+}
+
+#ifdef __APPLE__
+uint64_t
+monotime_coarse_stamp_units_to_approx_msec(uint64_t units)
+{
+  /* Recover as much precision as we can. */
+  uint64_t abstime_diff = (units << monotime_shift);
+  return (abstime_diff * mach_time_info.numer) /
+    (mach_time_info.denom * ONE_MILLION);
+}
+#else
+uint64_t
+monotime_coarse_stamp_units_to_approx_msec(uint64_t units)
+{
+  return (units * 1000) / STAMP_TICKS_PER_SECOND;
+}
+#endif
+
diff --git a/src/common/compat_time.h b/src/common/compat_time.h
index 5ea4aae42b..462dceccea 100644
--- a/src/common/compat_time.h
+++ b/src/common/compat_time.h
@@ -117,6 +117,23 @@ uint64_t monotime_coarse_absolute_msec(void);
 #define monotime_coarse_absolute_msec monotime_absolute_msec
 #endif /* defined(MONOTIME_COARSE_FN_IS_DIFFERENT) */
 
+/**
+ * Return a "timestamp" approximation for a coarse monotonic timer.
+ * This timestamp is meant to be fast to calculate and easy to
+ * compare, and have a unit of something roughly around 1 msec.
+ *
+ * It will wrap over from time to time.
+ *
+ * It has no defined zero point.
+ */
+uint32_t monotime_coarse_to_stamp(const monotime_coarse_t *t);
+/**
+ * Convert a difference, expressed in the units of monotime_coarse_to_stamp,
+ * into an approximate number of milliseconds.
+ */
+uint64_t monotime_coarse_stamp_units_to_approx_msec(uint64_t units);
+uint32_t monotime_coarse_get_stamp(void);
+
 #if defined(MONOTIME_COARSE_TYPE_IS_DIFFERENT)
 int64_t monotime_coarse_diff_nsec(const monotime_coarse_t *start,
     const monotime_coarse_t *end);