token_bucket_ctr: replace 32-bit wallclock time with monotime

This started as a response to ticket #40792 where Coverity is
complaining about a potential year 2038 bug where we cast time_t from
approx_time() to uint32_t for use in token_bucket_ctr.

There was a larger can of worms though, since token_bucket really
doesn't want to be using wallclock time here. I audited the call sites
for approx_time() and changed any that used a 32-bit cast or made
inappropriate use of wallclock time. Things like certificate lifetime,
consensus intervals, etc. need wallclock time. Measurements of rates
over time, however, are better served with a monotonic timer that does
not try and sync with wallclock ever.

Looking closer at token_bucket, its design is a bit odd because it was
initially intended for use with tick units but later forked into
token_bucket_rw which uses ticks to count bytes per second, and
token_bucket_ctr which uses seconds to count slower events. The rates
represented by either token bucket can't be lower than 1 per second, so
the slower timer in 'ctr' is necessary to represent the slower rates of
things like connections or introduction packets or rendezvous attempts.

I considered modifying token_bucket to use 64-bit timestamps overall
instead of 32-bit, but that seemed like an unnecessarily invasive change
that would grant some peace of mind but probably not help much. I was
more interested in removing the dependency on wallclock time. The
token_bucket_rw timer already uses monotonic time. This patch converts
token_bucket_ctr to use monotonic time as well. It introduces a new
monotime_coarse_absolute_sec(), which is currently the same as nsec
divided by a billion but could be optimized easily if we ever need to.

This patch also might fix a rollover bug.. I haven't tested this
extensively but I don't think the previous version of the rollover code
on either token bucket was correct, and I would expect it to get stuck
after the first rollover.

Signed-off-by: Micah Elizabeth Scott <beth@torproject.org>

4 files changed, 93 insertions, 63 deletions

diff --git a/src/lib/evloop/token_bucket.c b/src/lib/evloop/token_bucket.c
index 16452314e2..9bcfeb9367 100644
--- a/src/lib/evloop/token_bucket.c
+++ b/src/lib/evloop/token_bucket.c
@@ -111,7 +111,9 @@ token_bucket_raw_dec(token_bucket_raw_t *bucket,
   return becomes_empty;
 }
 
-/** Convert a rate in bytes per second to a rate in bytes per step */
+/** Convert a rate in bytes per second to a rate in bytes per step.
+ * This is used for the 'rw' style (tick based) token buckets but not for
+ * the 'ctr' style buckets which count seconds. */
 STATIC uint32_t
 rate_per_sec_to_rate_per_step(uint32_t rate)
 {
@@ -130,18 +132,18 @@ rate_per_sec_to_rate_per_step(uint32_t rate)
 /**
  * Initialize a token bucket in *<b>bucket</b>, set up to allow <b>rate</b>
  * bytes per second, with a maximum burst of <b>burst</b> bytes. The bucket
- * is created such that <b>now_ts</b> is the current timestamp.  The bucket
- * starts out full.
+ * is created such that <b>now_ts_stamp</b> is the current time in coarse stamp
+ * units. The bucket starts out full.
  */
 void
 token_bucket_rw_init(token_bucket_rw_t *bucket,
                      uint32_t rate,
                      uint32_t burst,
-                     uint32_t now_ts)
+                     uint32_t now_ts_stamp)
 {
   memset(bucket, 0, sizeof(token_bucket_rw_t));
   token_bucket_rw_adjust(bucket, rate, burst);
-  token_bucket_rw_reset(bucket, now_ts);
+  token_bucket_rw_reset(bucket, now_ts_stamp);
 }
 
 /**
@@ -161,56 +163,54 @@ token_bucket_rw_adjust(token_bucket_rw_t *bucket,
 }
 
 /**
- * Reset <b>bucket</b> to be full, as of timestamp <b>now_ts</b>.
+ * Reset <b>bucket</b> to be full, as of timestamp <b>now_ts_stamp</b>.
  */
 void
 token_bucket_rw_reset(token_bucket_rw_t *bucket,
-                      uint32_t now_ts)
+                      uint32_t now_ts_stamp)
 {
   token_bucket_raw_reset(&bucket->read_bucket, &bucket->cfg);
   token_bucket_raw_reset(&bucket->write_bucket, &bucket->cfg);
-  bucket->last_refilled_at_timestamp = now_ts;
+  bucket->last_refilled_at_timestamp = now_ts_stamp;
 }
 
 /**
  * Refill <b>bucket</b> as appropriate, given that the current timestamp
- * is <b>now_ts</b>.
+ * is <b>now_ts_stamp</b> in coarse timestamp units.
  *
  * Return a bitmask containing TB_READ iff read bucket was empty and became
  * nonempty, and TB_WRITE iff the write bucket was empty and became nonempty.
  */
 int
 token_bucket_rw_refill(token_bucket_rw_t *bucket,
-                       uint32_t now_ts)
+                       uint32_t now_ts_stamp)
 {
   const uint32_t elapsed_ticks =
-    (now_ts - bucket->last_refilled_at_timestamp);
-  if (elapsed_ticks > UINT32_MAX-(300*1000)) {
-    /* Either about 48 days have passed since the last refill, or the
-     * monotonic clock has somehow moved backwards. (We're looking at you,
-     * Windows.).  We accept up to a 5 minute jump backwards as
-     * "unremarkable".
-     */
-    return 0;
-  }
-  const uint32_t elapsed_steps = elapsed_ticks / TICKS_PER_STEP;
+    (now_ts_stamp - bucket->last_refilled_at_timestamp);
+  int flags = 0;
 
-  if (!elapsed_steps) {
-    /* Note that if less than one whole step elapsed, we don't advance the
-     * time in last_refilled_at. That's intentional: we want to make sure
-     * that we add some bytes to it eventually. */
-    return 0;
-  }
+  /* Skip over updates that include an overflow or a very large jump.
+   * This can happen for platform specific reasons, such as the old ~48
+   * day windows timer. */
+  if (elapsed_ticks <= UINT32_MAX/4) {
+    const uint32_t elapsed_steps = elapsed_ticks / TICKS_PER_STEP;
 
-  int flags = 0;
-  if (token_bucket_raw_refill_steps(&bucket->read_bucket,
-                                    &bucket->cfg, elapsed_steps))
-    flags |= TB_READ;
-  if (token_bucket_raw_refill_steps(&bucket->write_bucket,
-                                    &bucket->cfg, elapsed_steps))
-    flags |= TB_WRITE;
+    if (!elapsed_steps) {
+      /* Note that if less than one whole step elapsed, we don't advance the
+       * time in last_refilled_at. That's intentional: we want to make sure
+       * that we add some bytes to it eventually. */
+      return 0;
+    }
+
+    if (token_bucket_raw_refill_steps(&bucket->read_bucket,
+                                      &bucket->cfg, elapsed_steps))
+      flags |= TB_READ;
+    if (token_bucket_raw_refill_steps(&bucket->write_bucket,
+                                      &bucket->cfg, elapsed_steps))
+      flags |= TB_WRITE;
+  }
 
-  bucket->last_refilled_at_timestamp = now_ts;
+  bucket->last_refilled_at_timestamp = now_ts_stamp;
   return flags;
 }
 
@@ -259,15 +259,17 @@ token_bucket_rw_dec(token_bucket_rw_t *bucket,
 
 /** Initialize a token bucket in <b>bucket</b>, set up to allow <b>rate</b>
  * per second, with a maximum burst of <b>burst</b>. The bucket is created
- * such that <b>now_ts</b> is the current timestamp. The bucket starts out
- * full. */
+ * such that <b>now_ts_sec</b> is the current timestamp. The bucket starts
+ * out full. Note that these counters use seconds instead of approximate
+ * milliseconds, in order to allow a lower minimum rate than the rw counters.
+ */
 void
 token_bucket_ctr_init(token_bucket_ctr_t *bucket, uint32_t rate,
-                      uint32_t burst, uint32_t now_ts)
+                      uint32_t burst, uint32_t now_ts_sec)
 {
   memset(bucket, 0, sizeof(token_bucket_ctr_t));
   token_bucket_ctr_adjust(bucket, rate, burst);
-  token_bucket_ctr_reset(bucket, now_ts);
+  token_bucket_ctr_reset(bucket, now_ts_sec);
 }
 
 /** Change the configured rate and burst of the given token bucket object in
@@ -280,31 +282,28 @@ token_bucket_ctr_adjust(token_bucket_ctr_t *bucket, uint32_t rate,
   token_bucket_raw_adjust(&bucket->counter, &bucket->cfg);
 }
 
-/** Reset <b>bucket</b> to be full, as of timestamp <b>now_ts</b>. */
+/** Reset <b>bucket</b> to be full, as of timestamp <b>now_ts_sec</b>. */
 void
-token_bucket_ctr_reset(token_bucket_ctr_t *bucket, uint32_t now_ts)
+token_bucket_ctr_reset(token_bucket_ctr_t *bucket, uint32_t now_ts_sec)
 {
   token_bucket_raw_reset(&bucket->counter, &bucket->cfg);
-  bucket->last_refilled_at_timestamp = now_ts;
+  bucket->last_refilled_at_timestamp = now_ts_sec;
 }
 
 /** Refill <b>bucket</b> as appropriate, given that the current timestamp is
- * <b>now_ts</b>. */
+ * <b>now_ts_sec</b> in seconds. */
 void
-token_bucket_ctr_refill(token_bucket_ctr_t *bucket, uint32_t now_ts)
+token_bucket_ctr_refill(token_bucket_ctr_t *bucket, uint32_t now_ts_sec)
 {
-  const uint32_t elapsed_ticks =
-    (now_ts - bucket->last_refilled_at_timestamp);
-  if (elapsed_ticks > UINT32_MAX-(300*1000)) {
-    /* Either about 48 days have passed since the last refill, or the
-     * monotonic clock has somehow moved backwards. (We're looking at you,
-     * Windows.).  We accept up to a 5 minute jump backwards as
-     * "unremarkable".
-     */
-    return;
-  }
+  const uint32_t elapsed_sec =
+    (now_ts_sec - bucket->last_refilled_at_timestamp);
 
-  token_bucket_raw_refill_steps(&bucket->counter, &bucket->cfg,
-                                elapsed_ticks);
-  bucket->last_refilled_at_timestamp = now_ts;
+  /* Are we detecting a rollover or a similar extremely large jump? This
+   * shouldn't generally happen, but if it does for whatever (possibly
+   * platform-specific) reason, ignore it. */
+  if (elapsed_sec <= UINT32_MAX/4) {
+    token_bucket_raw_refill_steps(&bucket->counter, &bucket->cfg,
+                                  elapsed_sec);
+  }
+  bucket->last_refilled_at_timestamp = now_ts_sec;
 }
diff --git a/src/lib/evloop/token_bucket.h b/src/lib/evloop/token_bucket.h
index b57d704298..d042041e02 100644
--- a/src/lib/evloop/token_bucket.h
+++ b/src/lib/evloop/token_bucket.h
@@ -66,19 +66,19 @@ typedef struct token_bucket_rw_t {
 void token_bucket_rw_init(token_bucket_rw_t *bucket,
                           uint32_t rate,
                           uint32_t burst,
-                          uint32_t now_ts);
+                          uint32_t now_ts_stamp);
 
 void token_bucket_rw_adjust(token_bucket_rw_t *bucket,
                             uint32_t rate, uint32_t burst);
 
 void token_bucket_rw_reset(token_bucket_rw_t *bucket,
-                           uint32_t now_ts);
+                           uint32_t now_ts_stamp);
 
 #define TB_READ 1
 #define TB_WRITE 2
 
 int token_bucket_rw_refill(token_bucket_rw_t *bucket,
-                           uint32_t now_ts);
+                           uint32_t now_ts_stamp);
 
 int token_bucket_rw_dec_read(token_bucket_rw_t *bucket,
                              ssize_t n);
@@ -114,11 +114,11 @@ typedef struct token_bucket_ctr_t {
 } token_bucket_ctr_t;
 
 void token_bucket_ctr_init(token_bucket_ctr_t *bucket, uint32_t rate,
-                           uint32_t burst, uint32_t now_ts);
+                           uint32_t burst, uint32_t now_ts_sec);
 void token_bucket_ctr_adjust(token_bucket_ctr_t *bucket, uint32_t rate,
                              uint32_t burst);
-void token_bucket_ctr_reset(token_bucket_ctr_t *bucket, uint32_t now_ts);
-void token_bucket_ctr_refill(token_bucket_ctr_t *bucket, uint32_t now_ts);
+void token_bucket_ctr_reset(token_bucket_ctr_t *bucket, uint32_t now_ts_sec);
+void token_bucket_ctr_refill(token_bucket_ctr_t *bucket, uint32_t now_ts_sec);
 
 static inline bool
 token_bucket_ctr_dec(token_bucket_ctr_t *bucket, ssize_t n)
diff --git a/src/lib/time/compat_time.c b/src/lib/time/compat_time.c
index eb716259c4..57a1e45b84 100644
--- a/src/lib/time/compat_time.c
+++ b/src/lib/time/compat_time.c
@@ -812,6 +812,12 @@ monotime_absolute_msec(void)
   return monotime_absolute_nsec() / ONE_MILLION;
 }
 
+uint64_t
+monotime_absolute_sec(void)
+{
+  return monotime_absolute_nsec() / ONE_BILLION;
+}
+
 #ifdef MONOTIME_COARSE_FN_IS_DIFFERENT
 uint64_t
 monotime_coarse_absolute_nsec(void)
@@ -836,6 +842,17 @@ monotime_coarse_absolute_msec(void)
 {
   return monotime_coarse_absolute_nsec() / ONE_MILLION;
 }
+
+uint64_t
+monotime_coarse_absolute_sec(void)
+{
+  /* Note: Right now I'm not too concerned about 64-bit division, but if this
+   * ever becomes a hotspot we need to optimize, we can modify this to grab
+   * tv_sec directly from CLOCK_MONOTONIC_COARSE on linux at least. Right now
+   * I'm choosing to make this simpler and easier to test, but this
+   * optimization is available easily if we need it. */
+  return monotime_coarse_absolute_nsec() / ONE_BILLION;
+}
 #else /* !defined(MONOTIME_COARSE_FN_IS_DIFFERENT) */
 #define initialized_at_coarse initialized_at
 #endif /* defined(MONOTIME_COARSE_FN_IS_DIFFERENT) */
diff --git a/src/lib/time/compat_time.h b/src/lib/time/compat_time.h
index da96023894..eaf676ae84 100644
--- a/src/lib/time/compat_time.h
+++ b/src/lib/time/compat_time.h
@@ -89,6 +89,13 @@
  * A: In general, regular monotime uses something that requires a system call.
  * On platforms where system calls are cheap, you win!  Otherwise, you lose.
  *
+ *   XXX: This hasn't been true for a long time. Expect both coarse and fine
+ *        monotime won't require a syscall, but they will have different
+ *        costs in terms of low-level synchronization inside the vDSO and
+ *        the hardware. The basic guidelines here still apply, but we aren't
+ *        really worrying about system calls any more, and the integer div
+ *        concerns are becoming nearly unimportant as well.
+ *
  * On Windows, monotonic time uses QuereyPerformanceCounter.  Storing
  * monotime_t costs 8 bytes.
  *
@@ -232,7 +239,12 @@ MOCK_DECL(uint64_t, monotime_absolute_usec,(void));
  * Fractional units are truncated, not rounded.
  */
 uint64_t monotime_absolute_msec(void);
-
+/**
+ * Return the number of seconds since the timer system was initialized.
+ * The returned value may be equal to zero.
+ * Fractional units are truncated, not rounded.
+ */
+uint64_t monotime_absolute_sec(void);
 /**
  * Set <b>out</b> to zero.
  */
@@ -259,11 +271,13 @@ 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);
+uint64_t monotime_coarse_absolute_sec(void);
 #else /* !defined(MONOTIME_COARSE_FN_IS_DIFFERENT) */
 #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
+#define monotime_coarse_absolute_sec monotime_absolute_sec
 #endif /* defined(MONOTIME_COARSE_FN_IS_DIFFERENT) */
 
 /**