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, 48 insertions, 12 deletions

diff --git a/src/test/test_bwmgt.c b/src/test/test_bwmgt.c
index a034c369d1..51ad8be59f 100644
--- a/src/test/test_bwmgt.c
+++ b/src/test/test_bwmgt.c
@@ -243,10 +243,30 @@ test_bwmgt_token_buf_refill(void *arg)
   tt_int_op(b.read_bucket.bucket, OP_GT, 8*KB-400);
   tt_int_op(b.read_bucket.bucket, OP_LT, 8*KB+400);
 
-  // A ridiculous amount of time passes.
-  tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, INT32_MAX));
+  /* A large amount of time passes, but less than the threshold at which
+   * we start detecting an assumed rollover event. This might be about 20
+   * days on a system with stamp units equal to 1ms. */
+  uint32_t ts_stamp = START_TS + UINT32_MAX / 5;
+  tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, ts_stamp));
   tt_int_op(b.read_bucket.bucket, OP_EQ, b.cfg.burst);
 
+  /* Fully empty the bucket and make sure it's filling once again */
+  token_bucket_rw_dec_read(&b, b.cfg.burst);
+  tt_int_op(b.read_bucket.bucket, OP_EQ, 0);
+  tt_int_op(1, OP_EQ, token_bucket_rw_refill(&b, ts_stamp += BW_SEC));
+  tt_int_op(b.read_bucket.bucket, OP_GT, 16*KB - 300);
+  tt_int_op(b.read_bucket.bucket, OP_LT, 16*KB + 300);
+
+  /* An even larger amount of time passes, which we take to be a 32-bit
+   * rollover event. The individual update is ignored, but the timestamp
+   * is still updated and the very next update should be accounted properly. */
+  tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, ts_stamp += UINT32_MAX/2));
+  tt_int_op(b.read_bucket.bucket, OP_GT, 16*KB - 600);
+  tt_int_op(b.read_bucket.bucket, OP_LT, 16*KB + 600);
+  tt_int_op(0, OP_EQ, token_bucket_rw_refill(&b, ts_stamp += BW_SEC));
+  tt_int_op(b.read_bucket.bucket, OP_GT, 32*KB - 600);
+  tt_int_op(b.read_bucket.bucket, OP_LT, 32*KB + 600);
+
  done:
   ;
 }
diff --git a/src/test/test_dos.c b/src/test/test_dos.c
index a34420024f..8c9ddfcbe5 100644
--- a/src/test/test_dos.c
+++ b/src/test/test_dos.c
@@ -9,6 +9,7 @@
 #include "core/or/dos.h"
 #include "core/or/circuitlist.h"
 #include "lib/crypt_ops/crypto_rand.h"
+#include "lib/time/compat_time.h"
 #include "feature/stats/geoip_stats.h"
 #include "core/or/channel.h"
 #include "feature/nodelist/microdesc.h"
@@ -23,6 +24,8 @@
 #include "test/test.h"
 #include "test/log_test_helpers.h"
 
+static const uint64_t BILLION = 1000000000;
+
 static networkstatus_t *dummy_ns = NULL;
 static networkstatus_t *
 mock_networkstatus_get_latest_consensus(void)
@@ -58,14 +61,18 @@ mock_enable_dos_protection(const networkstatus_t *ns)
 static void
 test_dos_conn_creation(void *arg)
 {
+  uint64_t monotime_now = 0xfffffffe;
+
   (void) arg;
 
+  monotime_enable_test_mocking();
+  monotime_coarse_set_mock_time_nsec(monotime_now);
   MOCK(get_param_cc_enabled, mock_enable_dos_protection);
   MOCK(get_param_conn_enabled, mock_enable_dos_protection);
 
   /* Initialize test data */
   or_connection_t or_conn;
-  time_t now = 1281533250; /* 2010-08-11 13:27:30 UTC */
+  time_t wallclock_now = 1281533250; /* 2010-08-11 13:27:30 UTC */
   tt_int_op(AF_INET,OP_EQ, tor_addr_parse(&TO_CONN(&or_conn)->addr,
                                           "18.0.0.1"));
   tor_addr_t *addr = &TO_CONN(&or_conn)->addr;
@@ -75,13 +82,14 @@ test_dos_conn_creation(void *arg)
   uint32_t max_concurrent_conns = get_param_conn_max_concurrent_count(NULL);
 
   /* Introduce new client */
-  geoip_note_client_seen(GEOIP_CLIENT_CONNECT, addr, NULL, now);
+  geoip_note_client_seen(GEOIP_CLIENT_CONNECT, addr, NULL, wallclock_now);
   { /* Register many conns from this client but not enough to get it blocked */
     unsigned int i;
     for (i = 0; i < max_concurrent_conns; i++) {
       /* Don't trigger the connect() rate limitation so advance the clock 1
        * second for each connection. */
-      update_approx_time(++now);
+      monotime_coarse_set_mock_time_nsec(monotime_now += BILLION);
+      update_approx_time(++wallclock_now);
       dos_new_client_conn(&or_conn, NULL);
     }
   }
@@ -107,6 +115,7 @@ test_dos_conn_creation(void *arg)
 
  done:
   dos_free_all();
+  monotime_disable_test_mocking();
 }
 
 /** Helper mock: Place a fake IP addr for this channel in <b>addr_out</b> */
diff --git a/src/test/test_hs_dos.c b/src/test/test_hs_dos.c
index 70f2ef412f..81410f7b9b 100644
--- a/src/test/test_hs_dos.c
+++ b/src/test/test_hs_dos.c
@@ -16,6 +16,7 @@
 #include "test/log_test_helpers.h"
 
 #include "app/config/config.h"
+#include "lib/time/compat_time.h"
 
 #include "core/or/circuitlist.h"
 #include "core/or/circuituse.h"
@@ -45,7 +46,8 @@ free_mock_consensus(void)
 static void
 test_can_send_intro2(void *arg)
 {
-  uint32_t now = (uint32_t) approx_time();
+  static const uint64_t BILLION = 1000000000;
+  uint64_t now = 12345;
   or_circuit_t *or_circ = NULL;
 
   (void) arg;
@@ -55,6 +57,8 @@ test_can_send_intro2(void *arg)
 
   get_options_mutable()->ORPort_set = 1;
   setup_mock_consensus();
+  monotime_enable_test_mocking();
+  monotime_coarse_set_mock_time_nsec(now);
 
   or_circ =  or_circuit_new(1, NULL);
 
@@ -68,7 +72,7 @@ test_can_send_intro2(void *arg)
 
   /* Simulate that 10 cells have arrived in 1 second. There should be no
    * refill since the bucket is already at maximum on the first cell. */
-  update_approx_time(++now);
+  monotime_coarse_set_mock_time_nsec(now += BILLION);
   for (int i = 0; i < 10; i++) {
     tt_int_op(true, OP_EQ, hs_dos_can_send_intro2(or_circ));
   }
@@ -76,7 +80,7 @@ test_can_send_intro2(void *arg)
              get_intro2_burst_consensus_param(NULL) - 10);
 
   /* Fully refill the bucket minus 1 cell. */
-  update_approx_time(++now);
+  monotime_coarse_set_mock_time_nsec(now += BILLION);
   tt_int_op(true, OP_EQ, hs_dos_can_send_intro2(or_circ));
   tt_uint_op(token_bucket_ctr_get(&or_circ->introduce2_bucket), OP_EQ,
              get_intro2_burst_consensus_param(NULL) - 1);
@@ -84,7 +88,7 @@ test_can_send_intro2(void *arg)
   /* Receive an INTRODUCE2 at each second. We should have the bucket full
    * since at every second it gets refilled. */
   for (int i = 0; i < 10; i++) {
-    update_approx_time(++now);
+    monotime_coarse_set_mock_time_nsec(now += BILLION);
     tt_int_op(true, OP_EQ, hs_dos_can_send_intro2(or_circ));
   }
   /* Last check if we can send the cell decrements the bucket so minus 1. */
@@ -92,7 +96,8 @@ test_can_send_intro2(void *arg)
              get_intro2_burst_consensus_param(NULL) - 1);
 
   /* Manually reset bucket for next test. */
-  token_bucket_ctr_reset(&or_circ->introduce2_bucket, now);
+  token_bucket_ctr_reset(&or_circ->introduce2_bucket,
+                         (uint32_t) monotime_coarse_absolute_sec());
   tt_uint_op(token_bucket_ctr_get(&or_circ->introduce2_bucket), OP_EQ,
              get_intro2_burst_consensus_param(NULL));
 
@@ -115,7 +120,7 @@ test_can_send_intro2(void *arg)
   }
 
   /* One second has passed, we should have the rate minus 1 cell added. */
-  update_approx_time(++now);
+  monotime_coarse_set_mock_time_nsec(now += BILLION);
   tt_int_op(true, OP_EQ, hs_dos_can_send_intro2(or_circ));
   tt_uint_op(token_bucket_ctr_get(&or_circ->introduce2_bucket), OP_EQ,
              get_intro2_rate_consensus_param(NULL) - 1);
@@ -125,6 +130,7 @@ test_can_send_intro2(void *arg)
 
   hs_free_all();
   free_mock_consensus();
+  monotime_disable_test_mocking();
 }
 
 static void
diff --git a/src/test/test_hs_intropoint.c b/src/test/test_hs_intropoint.c
index cbcdeade92..82b7ec029d 100644
--- a/src/test/test_hs_intropoint.c
+++ b/src/test/test_hs_intropoint.c
@@ -14,6 +14,7 @@
 #include "test/test.h"
 #include "test/log_test_helpers.h"
 #include "lib/crypt_ops/crypto_rand.h"
+#include "lib/time/compat_time.h"
 
 #include "core/or/or.h"
 #include "core/or/channel.h"
@@ -127,7 +128,7 @@ helper_create_intro_circuit(void)
   tt_assert(circ);
   circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_OR);
   token_bucket_ctr_init(&circ->introduce2_bucket, 100, 100,
-                        (uint32_t) approx_time());
+                       (uint32_t) monotime_coarse_absolute_sec());
  done:
   return circ;
 }