Merge commit 'mikeperry/circuitbuildtimeout-final'

8 files changed, 1000 insertions, 17 deletions

diff --git a/src/or/Makefile.am b/src/or/Makefile.am
index 7d6c9eb0b9..e9916d5188 100644
--- a/src/or/Makefile.am
+++ b/src/or/Makefile.am
@@ -41,14 +41,14 @@ AM_CPPFLAGS = -DSHARE_DATADIR="\"$(datadir)\"" \
 tor_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ @TOR_LDFLAGS_libevent@
 tor_LDADD = ../common/libor.a ../common/libor-crypto.a \
 	../common/libor-event.a \
-	-lz -levent -lssl -lcrypto @TOR_LIB_WS32@ @TOR_LIB_GDI@
+	-lz -lm -levent -lssl -lcrypto @TOR_LIB_WS32@ @TOR_LIB_GDI@
 test_SOURCES = $(COMMON_SRC) test_data.c test.c
 
 test_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ \
         @TOR_LDFLAGS_libevent@
 test_LDADD = ../common/libor.a ../common/libor-crypto.a \
 	../common/libor-event.a \
-	-lz -levent -lssl -lcrypto @TOR_LIB_WS32@ @TOR_LIB_GDI@
+	-lz -lm -levent -lssl -lcrypto @TOR_LIB_WS32@ @TOR_LIB_GDI@
 
 noinst_HEADERS = or.h eventdns.h eventdns_tor.h micro-revision.i
 
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index ef9d24c853..177852f91a 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -9,9 +9,49 @@
  * \brief The actual details of building circuits.
  **/
 
+#define CIRCUIT_PRIVATE
+
 #include "or.h"
+#include "crypto.h"
+
+/*
+ * This madness is needed because if we simply #undef log
+ * before including or.h or log.h, we get linker collisions
+ * and random segfaults due to memory corruption (and
+ * not even at calls to log() either!)
+ */
+ /* XXX022 somebody should rename Tor's log() function, so we can
+  * remove this wart. -RD */
+#undef log
+
+/*
+ * Linux doesn't provide lround in math.h by default, but mac os does...
+ * It's best just to leave math.h out of the picture entirely.
+ */
+//#define log math_h_log
+//#include <math.h>
+//#undef log
+long int lround(double x);
+double ln(double x);
+double log(double x);
+double pow(double x, double y);
+
+double
+ln(double x)
+{
+  return log(x);
+}
+
+#define log _log
 
 /********* START VARIABLES **********/
+/** Global list of circuit build times */
+// FIXME: Add this as a member for entry_guard_t instead of global?
+// Then we could do per-guard statistics, as guards are likely to
+// vary in their own latency. The downside of this is that guards
+// can change frequently, so we'd be building a lot more circuits
+// most likely.
+circuit_build_times_t circ_times;
 
 /** A global list of all circuits at this hop. */
 extern circuit_t *global_circuitlist;
@@ -47,6 +87,10 @@ static smartlist_t *entry_guards = NULL;
  * and those changes need to be flushed to disk. */
 static int entry_guards_dirty = 0;
 
+/** If set, we're running the unit tests: we should avoid clobbering
+ * our state file or accessing get_options() or get_or_state() */
+static int unit_tests = 0;
+
 /********* END VARIABLES ************/
 
 static int circuit_deliver_create_cell(circuit_t *circ,
@@ -60,6 +104,698 @@ static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
 static void entry_guards_changed(void);
 static time_t start_of_month(time_t when);
 
+/** Make a note that we're running unit tests (rather than running Tor
+ * itself), so we avoid clobbering our state file. */
+void
+circuitbuild_running_unit_tests(void)
+{
+  unit_tests = 1;
+}
+
+/**
+ * Reset the build time state.
+ *
+ * Leave estimated paramters, timeout, and network liveness in tact
+ * for future use.
+ */
+void
+circuit_build_times_reset(circuit_build_times_t *cbt)
+{
+  memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times));
+  cbt->pre_timeouts = 0;
+  cbt->total_build_times = 0;
+  cbt->build_times_idx = 0;
+  cbt->have_computed_timeout = 0;
+}
+
+/**
+ * Initialize the buildtimes structure for first use.
+ *
+ * Sets the initial timeout value based to either the
+ * config setting or BUILD_TIMEOUT_INITIAL_VALUE.
+ */
+void
+circuit_build_times_init(circuit_build_times_t *cbt)
+{
+  memset(cbt, 0, sizeof(*cbt));
+
+  if (!unit_tests && get_options()->CircuitBuildTimeout) {
+    cbt->timeout = get_options()->CircuitBuildTimeout;
+    if (cbt->timeout < BUILD_TIMEOUT_MIN_VALUE) {
+      log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %d",
+               BUILD_TIMEOUT_MIN_VALUE);
+      cbt->timeout = BUILD_TIMEOUT_MIN_VALUE;
+    }
+  } else {
+    cbt->timeout = BUILD_TIMEOUT_INITIAL_VALUE;
+  }
+}
+
+/**
+ * Add a timeoutout value to the set of build times. Time units
+ * are milliseconds
+ *
+ * circuit_build_times is a circular array, so loop around when
+ * array is full.
+ */
+int
+circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
+{
+  if (time > BUILD_TIME_MAX) {
+    log_notice(LD_CIRC,
+       "Circuit build time of %ums exceeds max. Capping at 65536ms", time);
+    time = BUILD_TIME_MAX;
+  } else if (time <= 0) {
+    log_err(LD_CIRC, "Circuit build time is %u!", time);
+    return -1;
+  }
+
+  // XXX: Probably want to demote this to debug for the release.
+  log_info(LD_CIRC, "Adding circuit build time %u", time);
+
+  cbt->circuit_build_times[cbt->build_times_idx] = time;
+  cbt->build_times_idx = (cbt->build_times_idx + 1) % NCIRCUITS_TO_OBSERVE;
+  if (cbt->total_build_times < NCIRCUITS_TO_OBSERVE)
+    cbt->total_build_times++;
+
+  if ((cbt->total_build_times % BUILD_TIMES_SAVE_STATE_EVERY) == 0) {
+    /* Save state every 100 circuit builds */
+    if (!unit_tests && !get_options()->AvoidDiskWrites)
+      or_state_mark_dirty(get_or_state(), 0);
+  }
+
+  return 0;
+}
+
+/**
+ * Return maximum circuit build time
+ */
+static build_time_t
+circuit_build_times_max(circuit_build_times_t *cbt)
+{
+  int i = 0;
+  build_time_t max_build_time = 0;
+  for (i = 0; i < NCIRCUITS_TO_OBSERVE; i++) {
+    if (cbt->circuit_build_times[i] > max_build_time)
+      max_build_time = cbt->circuit_build_times[i];
+  }
+  return max_build_time;
+}
+
+/** Return minimum circuit build time */
+static build_time_t
+circuit_build_times_min(circuit_build_times_t *cbt)
+{
+  int i = 0;
+  build_time_t min_build_time = BUILD_TIME_MAX;
+  for (i = 0; i < NCIRCUITS_TO_OBSERVE; i++) {
+    if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
+        cbt->circuit_build_times[i] < min_build_time)
+      min_build_time = cbt->circuit_build_times[i];
+  }
+  if (min_build_time == BUILD_TIME_MAX) {
+    log_warn(LD_CIRC, "No build times less than BUILD_TIME_MAX!");
+  }
+  return min_build_time;
+}
+
+/**
+ * Calculate and return a histogram for the set of build times.
+ *
+ * Returns an allocated array of histrogram bins representing
+ * the frequency of index*BUILDTIME_BIN_WIDTH millisecond
+ * build times. Also outputs the number of bins in nbins.
+ *
+ * The return value must be freed by the caller.
+ */
+static uint32_t *
+circuit_build_times_create_histogram(circuit_build_times_t *cbt,
+                                     build_time_t *nbins)
+{
+  uint32_t *histogram;
+  build_time_t max_build_time = circuit_build_times_max(cbt);
+  int i, c;
+
+  *nbins = 1 + (max_build_time / BUILDTIME_BIN_WIDTH);
+  histogram = tor_malloc_zero(*nbins * sizeof(build_time_t));
+
+  // calculate histogram
+  for (i = 0; i < NCIRCUITS_TO_OBSERVE; i++) {
+    if (cbt->circuit_build_times[i] == 0) continue; /* 0 <-> uninitialized */
+
+    c = (cbt->circuit_build_times[i] / BUILDTIME_BIN_WIDTH);
+    histogram[c]++;
+  }
+
+  return histogram;
+}
+
+/**
+ * Return the most frequent build time (rounded to BUILDTIME_BIN_WIDTH ms).
+ *
+ * Ties go in favor of the slower time.
+ */
+static build_time_t
+circuit_build_times_mode(circuit_build_times_t *cbt)
+{
+  build_time_t i, nbins, max_bin=0;
+  uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
+
+  for (i = 0; i < nbins; i++) {
+    if (histogram[i] >= histogram[max_bin]) {
+      max_bin = i;
+    }
+  }
+
+  tor_free(histogram);
+
+  return max_bin*BUILDTIME_BIN_WIDTH+BUILDTIME_BIN_WIDTH/2;
+}
+
+/**
+ * Output a histogram of current circuit build times to
+ * the or_state_t state structure.
+ */
+void
+circuit_build_times_update_state(circuit_build_times_t *cbt,
+                                 or_state_t *state)
+{
+  uint32_t *histogram;
+  build_time_t i = 0;
+  build_time_t nbins = 0;
+  config_line_t **next, *line;
+
+  histogram = circuit_build_times_create_histogram(cbt, &nbins);
+  // write to state
+  config_free_lines(state->BuildtimeHistogram);
+  next = &state->BuildtimeHistogram;
+  *next = NULL;
+
+  state->TotalBuildTimes = cbt->total_build_times;
+
+  for (i = 0; i < nbins; i++) {
+    // compress the histogram by skipping the blanks
+    if (histogram[i] == 0) continue;
+    *next = line = tor_malloc_zero(sizeof(config_line_t));
+    line->key = tor_strdup("CircuitBuildTimeBin");
+    line->value = tor_malloc(25);
+    tor_snprintf(line->value, 25, "%d %d",
+            i*BUILDTIME_BIN_WIDTH+BUILDTIME_BIN_WIDTH/2, histogram[i]);
+    next = &(line->next);
+  }
+
+  if (!unit_tests) {
+    if (!get_options()->AvoidDiskWrites)
+      or_state_mark_dirty(get_or_state(), 0);
+  }
+
+  if (histogram) tor_free(histogram);
+}
+
+/**
+ * Shuffle the build times array.
+ *
+ * Stolen from http://en.wikipedia.org/wiki/Fisher\u2013Yates_shuffle
+ */
+static void
+circuit_build_times_shuffle_array(circuit_build_times_t *cbt)
+{
+   int n = cbt->total_build_times;
+
+   /* This code can only be run on a compact array */
+   tor_assert(cbt->total_build_times == cbt->build_times_idx);
+   while (n-- > 1) {
+     int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
+     build_time_t tmp = cbt->circuit_build_times[k];
+     cbt->circuit_build_times[k] = cbt->circuit_build_times[n];
+     cbt->circuit_build_times[n] = tmp;
+   }
+}
+
+/**
+ * Load histogram from <b>state</b>, shuffling the resulting array
+ * after we do so. Use this result to estimate parameters and
+ * calculate the timeout.
+ *
+ * Returns -1 and sets msg on error. Msg must be freed by the caller.
+ */
+int
+circuit_build_times_parse_state(circuit_build_times_t *cbt,
+                                or_state_t *state, char **msg)
+{
+  int tot_values = 0, N = 0;
+  config_line_t *line;
+  int i;
+  *msg = NULL;
+  circuit_build_times_init(cbt);
+
+  /* We don't support decreasing the table size yet */
+  tor_assert(state->TotalBuildTimes <= NCIRCUITS_TO_OBSERVE);
+
+  for (line = state->BuildtimeHistogram; line; line = line->next) {
+    smartlist_t *args = smartlist_create();
+    smartlist_split_string(args, line->value, " ",
+                           SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+    if (smartlist_len(args) < 2) {
+      *msg = tor_strdup("Unable to parse circuit build times: "
+                        "Too few arguments to CircuitBuildTime");
+      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
+      smartlist_free(args);
+      break;
+    } else {
+      const char *ms_str = smartlist_get(args,0);
+      const char *count_str = smartlist_get(args,1);
+      uint32_t count, k;
+      build_time_t ms;
+      int ok;
+      ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0,
+                                         BUILD_TIME_MAX, &ok, NULL);
+      if (!ok) {
+        *msg = tor_strdup("Unable to parse circuit build times: "
+                          "Unparsable bin number");
+        break;
+      }
+      count = (uint32_t)tor_parse_ulong(count_str, 0, 0,
+                                        UINT32_MAX, &ok, NULL);
+      if (!ok) {
+        *msg = tor_strdup("Unable to parse circuit build times: "
+                          "Unparsable bin count");
+        break;
+      }
+
+      for (k = 0; k < count; k++) {
+        circuit_build_times_add_time(cbt, ms);
+      }
+      N++;
+      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
+      smartlist_free(args);
+    }
+
+  }
+
+  circuit_build_times_shuffle_array(cbt);
+
+  /* Verify that we didn't overwrite any indexes */
+  for (i=0; i < NCIRCUITS_TO_OBSERVE; i++) {
+    if (!cbt->circuit_build_times[i])
+      break;
+    tot_values++;
+  }
+  log_info(LD_CIRC,
+           "Loaded %d/%d values from %d lines in circuit time histogram",
+           tot_values, cbt->total_build_times, N);
+  tor_assert(cbt->total_build_times == state->TotalBuildTimes);
+  tor_assert(tot_values == cbt->total_build_times);
+  circuit_build_times_set_timeout(cbt);
+  return *msg ? -1 : 0;
+}
+
+/**
+ * Estimates the Xm and Alpha parameters using
+ * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
+ *
+ * The notable difference is that we use mode instead of min to estimate Xm.
+ * This is because our distribution is frechet-like. We claim this is
+ * an acceptable approximation because we are only concerned with the
+ * accuracy of the CDF of the tail.
+ */
+void
+circuit_build_times_update_alpha(circuit_build_times_t *cbt)
+{
+  build_time_t *x=cbt->circuit_build_times;
+  double a = 0;
+  int n=0,i=0;
+
+  /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
+  /* We sort of cheat here and make our samples slightly more pareto-like
+   * and less frechet-like. */
+  cbt->Xm = circuit_build_times_mode(cbt);
+
+  for (i=0; i< NCIRCUITS_TO_OBSERVE; i++) {
+    if (!x[i]) {
+      continue;
+    }
+
+    if (x[i] < cbt->Xm) {
+      a += ln(cbt->Xm);
+    } else {
+      a += ln(x[i]);
+    }
+    n++;
+  }
+
+  if (n!=cbt->total_build_times) {
+    log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n,
+            cbt->total_build_times);
+  }
+  tor_assert(n==cbt->total_build_times);
+
+  a -= n*ln(cbt->Xm);
+  a = n/a;
+
+  cbt->alpha = a;
+}
+
+/**
+ * This is the Pareto Quantile Function. It calculates the point x
+ * in the distribution such that F(x) = quantile (ie quantile*100%
+ * of the mass of the density function is below x on the curve).
+ *
+ * We use it to calculate the timeout and also to generate synthetic
+ * values of time for circuits that timeout before completion.
+ *
+ * See http://en.wikipedia.org/wiki/Quantile_function,
+ * http://en.wikipedia.org/wiki/Inverse_transform_sampling and
+ * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
+ *     random_sample_from_Pareto_distribution
+ * That's right. I'll cite wikipedia all day long.
+ */
+double
+circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
+                                      double quantile)
+{
+  double ret;
+  tor_assert(quantile >= 0);
+  tor_assert(1.0-quantile > 0);
+  tor_assert(cbt->Xm > 0);
+
+  ret = cbt->Xm/pow(1.0-quantile,1.0/cbt->alpha);
+  if (ret > INT32_MAX) {
+    ret = INT32_MAX;
+  }
+  tor_assert(ret > 0);
+  return ret;
+}
+
+/** Pareto CDF */
+double
+circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
+{
+  double ret;
+  tor_assert(cbt->Xm > 0);
+  ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
+  tor_assert(0 <= ret && ret <= 1.0);
+  return ret;
+}
+
+/**
+ * Generate a synthetic time using our distribution parameters.
+ *
+ * The return value will be between q_lo and q_hi quantile points
+ * on the CDF.
+ */
+build_time_t
+circuit_build_times_generate_sample(circuit_build_times_t *cbt,
+                                    double q_lo, double q_hi)
+{
+  uint64_t r = crypto_rand_uint64(UINT64_MAX-1);
+  build_time_t ret;
+  double u;
+
+  tor_assert(q_lo >= 0);
+  tor_assert(q_hi < 1);
+
+  u = q_lo + ((q_hi-q_lo)*r)/(1.0*UINT64_MAX);
+
+  tor_assert(0 <= u && u < 1.0);
+  /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
+  ret = (uint32_t)lround(circuit_build_times_calculate_timeout(cbt, u));
+  tor_assert(ret > 0);
+  return ret;
+}
+
+/** Generate points in [cutoff, 1.0) on the CDF. */
+void
+circuit_build_times_add_timeout_worker(circuit_build_times_t *cbt,
+                                       double quantile_cutoff)
+{
+  build_time_t gentime = circuit_build_times_generate_sample(cbt,
+              quantile_cutoff, MAX_SYNTHETIC_QUANTILE);
+
+  if (gentime < (build_time_t)cbt->timeout*1000) {
+    log_warn(LD_CIRC,
+             "Generated a synthetic timeout LESS than the current timeout: "
+             "%u vs %d using Xm: %d a: %lf, q: %lf",
+             gentime, cbt->timeout*1000, cbt->Xm, cbt->alpha, quantile_cutoff);
+  } else if (gentime > BUILD_TIME_MAX) {
+    gentime = BUILD_TIME_MAX;
+    log_info(LD_CIRC,
+             "Generated a synthetic timeout larger than the max: %u",
+             gentime);
+  } else {
+    log_info(LD_CIRC, "Generated synthetic circuit build time %u for timeout",
+            gentime);
+  }
+
+  circuit_build_times_add_time(cbt, gentime);
+}
+
+/**
+ * Estimate an initial alpha parameter by solving the quantile
+ * function with a quantile point and a specific timeout value.
+ */
+void
+circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
+                                  double quantile, build_time_t timeout)
+{
+  // Q(u) = Xm/((1-u)^(1/a))
+  // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
+  // CircBuildTimeout = Xm/((1-0.8))^(1/a))
+  // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
+  // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
+  // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
+  tor_assert(quantile > 0);
+  tor_assert(cbt->Xm > 0);
+  cbt->alpha = ln(1.0-quantile)/(ln(cbt->Xm)-ln(timeout));
+  tor_assert(cbt->alpha > 0);
+}
+
+/**
+ * Generate synthetic timeout values for the timeouts
+ * that have happened before we estimated our parameters.
+ */
+static void
+circuit_build_times_count_pretimeouts(circuit_build_times_t *cbt)
+{
+  /* Store a timeout as a random position past the current
+   * cutoff on the pareto curve */
+  if (cbt->pre_timeouts) {
+    double timeout_quantile = 1.0-
+          ((double)cbt->pre_timeouts)/
+                    (cbt->pre_timeouts+cbt->total_build_times);
+    cbt->Xm = circuit_build_times_min(cbt);
+    tor_assert(cbt->Xm > 0);
+    // Use current timeout to get an estimate on alpha
+    circuit_build_times_initial_alpha(cbt, timeout_quantile,
+                                      cbt->timeout*1000);
+    while (cbt->pre_timeouts-- != 0) {
+      circuit_build_times_add_timeout_worker(cbt, timeout_quantile);
+    }
+    cbt->pre_timeouts = 0;
+  }
+}
+
+/**
+ * Returns true if we need circuits to be built
+ */
+int
+circuit_build_times_needs_circuits(circuit_build_times_t *cbt)
+{
+  /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
+  if (cbt->total_build_times < MIN_CIRCUITS_TO_OBSERVE)
+    return 1;
+  return 0;
+}
+
+/**
+ * Returns true if we should build a timeout test circuit
+ * right now.
+ */
+int
+circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt)
+{
+  return circuit_build_times_needs_circuits(cbt) &&
+    approx_time()-cbt->last_circ_at > BUILD_TIMES_TEST_FREQUENCY;
+}
+
+/**
+ * Called to indicate that the network showed some signs of liveness.
+ */
+void
+circuit_build_times_network_is_live(circuit_build_times_t *cbt)
+{
+  cbt->network_last_live = approx_time();
+}
+
+/**
+ * Returns true if the network showed some sign of liveness
+ * in the past NETWORK_LIVE_MULTIPLIER*cbt->timeout seconds.
+ */
+int
+circuit_build_times_is_network_live(circuit_build_times_t *cbt)
+{
+  time_t now = approx_time();
+  if (now - cbt->network_last_live >
+          (cbt->timeout*NETWORK_LIVE_MULTIPLIER)) {
+    log_info(LD_CIRC, "Network is no longer live. Dead for %ld seconds.",
+             now - cbt->network_last_live);
+    return 0;
+  }
+  return 1;
+}
+
+/**
+ * Returns true if we have seen more than MAX_RECENT_TIMEOUT_RATE of
+ * the past RECENT_CIRCUITS time out. Used to detect if the network
+ * connection has changed significantly.
+ *
+ * Also resets the entire timeout history in this case and causes us
+ * to restart the process of building test circuits and estimating a
+ * new timeout.
+ */
+int
+circuit_build_times_check_too_many_timeouts(circuit_build_times_t *cbt)
+{
+  double timeout_rate=0;
+  build_time_t Xm = BUILD_TIME_MAX;
+  double timeout;
+  int i;
+
+  if ((cbt->pre_timeouts + cbt->total_build_times) < RECENT_CIRCUITS) {
+    return 0;
+  }
+
+  /* Get timeout rate and Xm for recent circs */
+  for (i = (cbt->build_times_idx - RECENT_CIRCUITS) % NCIRCUITS_TO_OBSERVE;
+       i != cbt->build_times_idx;
+       i = (i + 1) % NCIRCUITS_TO_OBSERVE) {
+    if (cbt->circuit_build_times[i] && cbt->circuit_build_times[i] < Xm) {
+      Xm = cbt->circuit_build_times[i];
+    }
+    if (cbt->circuit_build_times[i] > (build_time_t)cbt->timeout*1000) {
+      timeout_rate++;
+    }
+  }
+  timeout_rate += cbt->pre_timeouts;
+  timeout_rate /= RECENT_CIRCUITS;
+
+  /* If more than 80% of our recent circuits are timing out,
+   * we need to re-estimate a new initial alpha and timeout */
+  if (timeout_rate < MAX_RECENT_TIMEOUT_RATE) {
+    return 0;
+  }
+
+  log_notice(LD_CIRC,
+            "Network connection speed appears to have changed. "
+            "Resetting timeouts after %d pretimouts and %d buildtimes",
+            cbt->pre_timeouts, cbt->total_build_times);
+
+  if (Xm >= (build_time_t)cbt->timeout*1000) {
+    Xm = circuit_build_times_min(cbt);
+    if (Xm >= (build_time_t)cbt->timeout*1000) {
+      /* No circuits have completed */
+      cbt->timeout *= 2;
+      log_warn(LD_CIRC,
+               "Adjusting CircuitBuildTimeout to %d in the hopes that "
+               "some connections will succeed", cbt->timeout);
+      goto reset;
+    }
+  }
+  tor_assert(Xm > 0);
+  cbt->Xm = Xm;
+
+  circuit_build_times_initial_alpha(cbt, 1.0-timeout_rate,
+          cbt->timeout*1000);
+
+  timeout = circuit_build_times_calculate_timeout(cbt,
+                                BUILDTIMEOUT_QUANTILE_CUTOFF);
+  /* timeout is INT32_MAX at most */
+  cbt->timeout = (uint32_t)lround(timeout/1000.0);
+
+  if (cbt->timeout < BUILD_TIMEOUT_MIN_VALUE) {
+    log_warn(LD_CIRC, "Reset buildtimeout to low value %lf. Setting to %d",
+             timeout, BUILD_TIMEOUT_MIN_VALUE);
+    cbt->timeout = BUILD_TIMEOUT_MIN_VALUE;
+  }
+
+  log_notice(LD_CIRC,
+             "Reset circuit build timeout to %d (%lf, Xm: %d, a: %lf) based "
+             "on %d recent circuit times", cbt->timeout, timeout, cbt->Xm,
+             cbt->alpha, RECENT_CIRCUITS);
+
+reset:
+
+  /* Reset all data */
+  circuit_build_times_reset(cbt);
+  return 1;
+}
+
+/**
+ * Store a timeout as a synthetic value
+ */
+void
+circuit_build_times_add_timeout(circuit_build_times_t *cbt)
+{
+  /* Only count timeouts if network is live.. */
+  if (!circuit_build_times_is_network_live(cbt)) {
+    return;
+  }
+
+  /* If there are a ton of timeouts, we should reduce
+   * the circuit build timeout */
+  if (circuit_build_times_check_too_many_timeouts(cbt)) {
+    return;
+  }
+
+  if (!cbt->have_computed_timeout) {
+    /* Store a timeout before we have enough data as special */
+    cbt->pre_timeouts++;
+    return;
+  }
+
+  circuit_build_times_count_pretimeouts(cbt);
+  circuit_build_times_add_timeout_worker(cbt, BUILDTIMEOUT_QUANTILE_CUTOFF);
+}
+
+/**
+ * Estimate a new timeout based on history and set our timeout
+ * variable accordingly.
+ */
+void
+circuit_build_times_set_timeout(circuit_build_times_t *cbt)
+{
+  double timeout;
+
+  if (cbt->total_build_times < MIN_CIRCUITS_TO_OBSERVE) {
+    log_info(LD_CIRC,
+             "Not enough circuits yet to calculate a new build timeout."
+             " Need %d more.",
+             MIN_CIRCUITS_TO_OBSERVE-cbt->total_build_times);
+    return;
+  }
+
+  circuit_build_times_count_pretimeouts(cbt);
+  circuit_build_times_update_alpha(cbt);
+  timeout = circuit_build_times_calculate_timeout(cbt,
+                                BUILDTIMEOUT_QUANTILE_CUTOFF);
+
+  cbt->have_computed_timeout = 1;
+  /* timeout is INT32_MAX at most */
+  cbt->timeout = (uint32_t)lround(timeout/1000.0);
+
+  if (cbt->timeout < BUILD_TIMEOUT_MIN_VALUE) {
+    log_warn(LD_CIRC, "Set buildtimeout to low value %lf. Setting to %d",
+             timeout, BUILD_TIMEOUT_MIN_VALUE);
+    cbt->timeout = BUILD_TIMEOUT_MIN_VALUE;
+  }
+
+  log_info(LD_CIRC,
+           "Set circuit build timeout to %d (%lf, Xm: %d, a: %lf) based on "
+           "%d circuit times", cbt->timeout, timeout, cbt->Xm, cbt->alpha,
+           cbt->total_build_times);
+
+}
+
 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
  * and with the high bit specified by conn-\>circ_id_type, until we get
  * a circ_id that is not in use by any other circuit on that conn.
@@ -641,8 +1377,16 @@ circuit_send_next_onion_skin(origin_circuit_t *circ)
     log_debug(LD_CIRC,"starting to send subsequent skin.");
     hop = onion_next_hop_in_cpath(circ->cpath);
     if (!hop) {
+      struct timeval end;
+      long timediff;
+      tor_gettimeofday(&end);
+      timediff = tv_mdiff(&circ->_base.highres_created, &end);
+      if (timediff > INT32_MAX)
+        timediff = INT32_MAX;
       /* done building the circuit. whew. */
       circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
+      circuit_build_times_add_time(&circ_times, (uint32_t)timediff);
+      circuit_build_times_set_timeout(&circ_times);
       log_info(LD_CIRC,"circuit built!");
       circuit_reset_failure_count(0);
       if (circ->build_state->onehop_tunnel)
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index e1da117168..259666732a 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -379,6 +379,7 @@ static void
 init_circuit_base(circuit_t *circ)
 {
   circ->timestamp_created = time(NULL);
+  tor_gettimeofday(&circ->highres_created);
 
   circ->package_window = circuit_initial_package_window();
   circ->deliver_window = CIRCWINDOW_START;
@@ -407,6 +408,8 @@ origin_circuit_new(void)
 
   init_circuit_base(TO_CIRCUIT(circ));
 
+  circ_times.last_circ_at = approx_time();
+
   return circ;
 }
 
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index ee2d0bbabf..7ca65bcc53 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -264,8 +264,8 @@ void
 circuit_expire_building(time_t now)
 {
   circuit_t *victim, *circ = global_circuitlist;
-  time_t general_cutoff = now - get_options()->CircuitBuildTimeout;
-  time_t begindir_cutoff = now - get_options()->CircuitBuildTimeout/2;
+  time_t general_cutoff = now - circ_times.timeout;
+  time_t begindir_cutoff = now - circ_times.timeout/2;
   time_t introcirc_cutoff = begindir_cutoff;
   cpath_build_state_t *build_state;
 
@@ -358,6 +358,8 @@ circuit_expire_building(time_t now)
 
     circuit_log_path(LOG_INFO,LD_CIRC,TO_ORIGIN_CIRCUIT(victim));
     circuit_mark_for_close(victim, END_CIRC_REASON_TIMEOUT);
+    circuit_build_times_add_timeout(&circ_times);
+    circuit_build_times_set_timeout(&circ_times);
   }
 }
 
@@ -517,6 +519,16 @@ circuit_predict_and_launch_new(void)
     circuit_launch_by_router(CIRCUIT_PURPOSE_C_GENERAL, NULL, flags);
     return;
   }
+
+  /* Finally, check to see if we still need more circuits to learn
+   * a good build timeout */
+  if (circuit_build_times_needs_circuits_now(&circ_times)) {
+    flags = CIRCLAUNCH_NEED_CAPACITY;
+    log_info(LD_CIRC,
+             "Have %d clean circs need another buildtime test circ.", num);
+    circuit_launch_by_router(CIRCUIT_PURPOSE_C_GENERAL, NULL, flags);
+    return;
+  }
 }
 
 /** Build a new test circuit every 5 minutes */
@@ -631,7 +643,15 @@ static void
 circuit_expire_old_circuits(time_t now)
 {
   circuit_t *circ;
-  time_t cutoff = now - get_options()->CircuitIdleTimeout;
+  time_t cutoff;
+
+  if (circuit_build_times_needs_circuits(&circ_times)) {
+    /* Circuits should be shorter lived if we need them
+     * for build time testing */
+    cutoff = now - get_options()->MaxCircuitDirtiness;
+  } else {
+    cutoff = now - get_options()->CircuitIdleTimeout;
+  }
 
   for (circ = global_circuitlist; circ; circ = circ->next) {
     if (circ->marked_for_close || ! CIRCUIT_IS_ORIGIN(circ))
diff --git a/src/or/config.c b/src/or/config.c
index d830229d3b..0712fbee7d 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -164,7 +164,7 @@ static config_var_t _option_vars[] = {
   V(BridgeRecordUsageByCountry,  BOOL,     "1"),
   V(BridgeRelay,                 BOOL,     "0"),
   V(CellStatistics,              BOOL,     "0"),
-  V(CircuitBuildTimeout,         INTERVAL, "1 minute"),
+  V(CircuitBuildTimeout,         INTERVAL, "0"),
   V(CircuitIdleTimeout,          INTERVAL, "1 hour"),
   V(ClientDNSRejectInternalAddresses, BOOL,"1"),
   V(ClientOnly,                  BOOL,     "0"),
@@ -409,6 +409,10 @@ static config_var_t _state_vars[] = {
   V(LastRotatedOnionKey,              ISOTIME,  NULL),
   V(LastWritten,                      ISOTIME,  NULL),
 
+  V(TotalBuildTimes,                  UINT,     NULL),
+  VAR("CircuitBuildTimeBin",          LINELIST_S, BuildtimeHistogram, NULL),
+  VAR("BuildtimeHistogram",           LINELIST_V, BuildtimeHistogram, NULL),
+
   { NULL, CONFIG_TYPE_OBSOLETE, 0, NULL }
 };
 
@@ -597,6 +601,10 @@ static config_var_description_t options_description[] = {
   /* Hidden service options: HiddenService: dir,excludenodes, nodes,
    * options, port.  PublishHidServDescriptor */
 
+  /* Circuit build time histogram options */
+  { "CircuitBuildTimeBin", "Histogram of recent circuit build times"},
+  { "TotalBuildTimes", "Total number of buildtimes in histogram"},
+
   /* Nonpersistent options: __LeaveStreamsUnattached, __AllDirActionsPrivate */
   { NULL, NULL },
 };
@@ -2911,11 +2919,6 @@ compute_publishserverdescriptor(or_options_t *options)
 /** Highest allowable value for RendPostPeriod. */
 #define MAX_DIR_PERIOD (MIN_ONION_KEY_LIFETIME/2)
 
-/** Lowest allowable value for CircuitBuildTimeout; values too low will
- * increase network load because of failing connections being retried, and
- * might prevent users from connecting to the network at all. */
-#define MIN_CIRCUIT_BUILD_TIMEOUT 30
-
 /** Lowest allowable value for MaxCircuitDirtiness; if this is too low, Tor
  * will generate too many circuits and potentially overload the network. */
 #define MIN_MAX_CIRCUIT_DIRTINESS 10
@@ -3362,12 +3365,6 @@ options_validate(or_options_t *old_options, or_options_t *options,
     options->RendPostPeriod = MAX_DIR_PERIOD;
   }
 
-  if (options->CircuitBuildTimeout < MIN_CIRCUIT_BUILD_TIMEOUT) {
-    log(LOG_WARN, LD_CONFIG, "CircuitBuildTimeout option is too short; "
-      "raising to %d seconds.", MIN_CIRCUIT_BUILD_TIMEOUT);
-    options->CircuitBuildTimeout = MIN_CIRCUIT_BUILD_TIMEOUT;
-  }
-
   if (options->MaxCircuitDirtiness < MIN_MAX_CIRCUIT_DIRTINESS) {
     log(LOG_WARN, LD_CONFIG, "MaxCircuitDirtiness option is too short; "
       "raising to %d seconds.", MIN_MAX_CIRCUIT_DIRTINESS);
@@ -5060,6 +5057,10 @@ or_state_set(or_state_t *new_state)
     log_warn(LD_GENERAL,"Unparseable bandwidth history state: %s",err);
     tor_free(err);
   }
+  if (circuit_build_times_parse_state(&circ_times, global_state, &err) < 0) {
+    log_warn(LD_GENERAL,"%s",err);
+    tor_free(err);
+  }
 }
 
 /** Reload the persistent state from disk, generating a new state as needed.
@@ -5192,6 +5193,7 @@ or_state_save(time_t now)
    * to avoid redundant writes. */
   entry_guards_update_state(global_state);
   rep_hist_update_state(global_state);
+  circuit_build_times_update_state(&circ_times, global_state);
   if (accounting_is_enabled(get_options()))
     accounting_run_housekeeping(now);
 
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 8c8b5496a7..aa26bf8f4b 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -1036,6 +1036,8 @@ connection_tls_finish_handshake(or_connection_t *conn)
                                               digest_rcvd) < 0)
     return -1;
 
+  circuit_build_times_network_is_live(&circ_times);
+
   if (tor_tls_used_v1_handshake(conn->tls)) {
     conn->link_proto = 1;
     if (!started_here) {
@@ -1087,6 +1089,7 @@ connection_or_set_state_open(or_connection_t *conn)
   control_event_or_conn_status(conn, OR_CONN_EVENT_CONNECTED, 0);
 
   if (started_here) {
+    circuit_build_times_network_is_live(&circ_times);
     rep_hist_note_connect_succeeded(conn->identity_digest, now);
     if (entry_guard_register_connect_status(conn->identity_digest,
                                             1, 0, now) < 0) {
@@ -1187,6 +1190,7 @@ connection_or_process_cells_from_inbuf(or_connection_t *conn)
     if (connection_fetch_var_cell_from_buf(conn, &var_cell)) {
       if (!var_cell)
         return 0; /* not yet. */
+      circuit_build_times_network_is_live(&circ_times);
       command_process_var_cell(var_cell, conn);
       var_cell_free(var_cell);
     } else {
@@ -1196,6 +1200,7 @@ connection_or_process_cells_from_inbuf(or_connection_t *conn)
                                                                  available? */
         return 0; /* not yet */
 
+      circuit_build_times_network_is_live(&circ_times);
       connection_fetch_from_buf(buf, CELL_NETWORK_SIZE, TO_CONN(conn));
 
       /* retrieve cell info from buf (create the host-order struct from the
diff --git a/src/or/or.h b/src/or/or.h
index 8587ea61fc..bdb4d97924 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1977,6 +1977,7 @@ typedef struct circuit_t {
   time_t timestamp_created; /**< When was this circuit created? */
   time_t timestamp_dirty; /**< When the circuit was first used, or 0 if the
                            * circuit is clean. */
+  struct timeval highres_created; /**< When exactly was the circuit created? */
 
   uint16_t marked_for_close; /**< Should we close this circuit at the end of
                               * the main loop? (If true, holds the line number
@@ -2683,6 +2684,10 @@ typedef struct {
   int         BWHistoryWriteInterval;
   smartlist_t *BWHistoryWriteValues;
 
+  /** Build time histogram */
+  config_line_t * BuildtimeHistogram;
+  uint16_t TotalBuildTimes;
+
   /** What version of Tor wrote this state file? */
   char *TorVersion;
 
@@ -2852,6 +2857,109 @@ void bridges_retry_all(void);
 
 void entry_guards_free_all(void);
 
+/* Circuit Build Timeout "public" functions and structures. */
+
+/** How many circuits count as recent when deciding if the
+ * connection has changed. */
+#define RECENT_CIRCUITS 20
+
+/** Maximum fraction of timeouts to tolerate in the past
+ * RECENT_CIRCUITS before calculating a new timeout */
+#define MAX_RECENT_TIMEOUT_RATE 0.7999999
+
+/** Maximum quantile to use to generate synthetic timeouts.
+ *  We want to stay a bit short of 1.0, because longtail is
+ *  loooooooooooooooooooooooooooooooooooooooooooooooooooong. */
+#define MAX_SYNTHETIC_QUANTILE 0.98
+
+/** Minimum circuits before estimating a timeout */
+#define MIN_CIRCUITS_TO_OBSERVE 500
+
+/** Total size of the circuit timeout history to accumulate.
+ * 5000 is approx 1.5 weeks worth of continual-use circuits. */
+#define NCIRCUITS_TO_OBSERVE 5000
+
+/** Width of the histogram bins in milliseconds */
+#define BUILDTIME_BIN_WIDTH ((build_time_t)50)
+
+/** Cuttof point on the CDF for our timeout estimation.
+ * TODO: This should be moved to the consensus */
+#define BUILDTIMEOUT_QUANTILE_CUTOFF 0.8
+
+/** A build_time_t is milliseconds */
+typedef uint32_t build_time_t;
+#define BUILD_TIME_MAX  ((build_time_t)(INT32_MAX))
+
+/** Have we received a cell in the last N seconds? */
+#define NETWORK_LIVE_MULTIPLIER (RECENT_CIRCUITS/2.5)
+
+/** Lowest allowable value for CircuitBuildTimeout */
+#define BUILD_TIMEOUT_MIN_VALUE 3
+
+/** Initial circuit build timeout */
+#define BUILD_TIMEOUT_INITIAL_VALUE 60
+
+/** How often in seconds should we build a test circuit */
+#define BUILD_TIMES_TEST_FREQUENCY 60
+
+/** Save state every 10 circuits */
+#define BUILD_TIMES_SAVE_STATE_EVERY  10
+
+typedef struct {
+  /** The circular array of recorded build times in milliseconds */
+  build_time_t circuit_build_times[NCIRCUITS_TO_OBSERVE];
+  /** The timestamp we last completed a TLS handshake or received a cell */
+  time_t network_last_live;
+  /** Last time we built a circuit. Used to decide to build new test circs */
+  time_t last_circ_at;
+  /** Current index in the circuit_build_times circular array */
+  int build_times_idx;
+  /** Total number of build times accumulated. Maxes at NCIRCUITS_TO_OBSERVE */
+  int total_build_times;
+  /** Number of timeouts that have happened before estimating pareto
+   *  parameters */
+  int pre_timeouts;
+  /** "Minimum" value of our pareto distribution (actually mode) */
+  build_time_t Xm;
+  /** alpha exponent for pareto dist. */
+  double alpha;
+  /** Have we computed a timeout? */
+  int have_computed_timeout;
+  /** The value for that timeout in seconds, not milliseconds */
+  int timeout;
+} circuit_build_times_t;
+
+extern circuit_build_times_t circ_times;
+void circuit_build_times_update_state(circuit_build_times_t *cbt,
+                                      or_state_t *state);
+int circuit_build_times_parse_state(circuit_build_times_t *cbt,
+                                    or_state_t *state, char **msg);
+void circuit_build_times_add_timeout(circuit_build_times_t *cbt);
+void circuit_build_times_set_timeout(circuit_build_times_t *cbt);
+int circuit_build_times_add_time(circuit_build_times_t *cbt,
+                                 build_time_t time);
+void circuit_build_times_network_is_live(circuit_build_times_t *cbt);
+int circuit_build_times_is_network_live(circuit_build_times_t *cbt);
+int circuit_build_times_needs_circuits(circuit_build_times_t *cbt);
+int circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt);
+void circuit_build_times_init(circuit_build_times_t *cbt);
+
+#ifdef CIRCUIT_PRIVATE
+double circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
+                                             double quantile);
+build_time_t circuit_build_times_generate_sample(circuit_build_times_t *cbt,
+                                                 double q_lo, double q_hi);
+void circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
+                                       double quantile, build_time_t time);
+void circuit_build_times_update_alpha(circuit_build_times_t *cbt);
+double circuit_build_times_cdf(circuit_build_times_t *cbt, double x);
+int circuit_build_times_check_too_many_timeouts(circuit_build_times_t *cbt);
+void circuit_build_times_add_timeout_worker(circuit_build_times_t *cbt,
+                                       double quantile_cutoff);
+void circuitbuild_running_unit_tests(void);
+void circuit_build_times_reset(circuit_build_times_t *cbt);
+#endif
+
 /********************************* circuitlist.c ***********************/
 
 circuit_t * _circuit_get_global_list(void);
diff --git a/src/or/test.c b/src/or/test.c
index f2cc7cc1f3..cf00c080d4 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -37,6 +37,9 @@ const char tor_git_revision[] = "";
 #define GEOIP_PRIVATE
 #define MEMPOOL_PRIVATE
 #define ROUTER_PRIVATE
+#define CIRCUIT_PRIVATE
+
+#include <math.h>
 
 #include "or.h"
 #include "test.h"
@@ -3404,6 +3407,103 @@ test_dirutil_param_voting(void)
   smartlist_free(vote3.net_params);
   smartlist_free(vote4.net_params);
 
+  return;
+}
+
+static void
+test_circuit_timeout(void)
+{
+  /* Plan:
+   *  1. Generate 1000 samples
+   *  2. Estimate parameters
+   *  3. If difference, repeat
+   *  4. Save state
+   *  5. load state
+   *  6. Estimate parameters
+   *  7. compare differences
+   */
+  circuit_build_times_t initial;
+  circuit_build_times_t estimate;
+  circuit_build_times_t final;
+  or_state_t state;
+  int i;
+  char *msg;
+  double timeout1, timeout2;
+  circuit_build_times_init(&initial);
+  circuit_build_times_init(&estimate);
+  circuit_build_times_init(&final);
+
+  memset(&state, 0, sizeof(or_state_t));
+
+  circuitbuild_running_unit_tests();
+#define timeout0 (build_time_t)(30*1000.0)
+  initial.Xm = 750;
+  circuit_build_times_initial_alpha(&initial, BUILDTIMEOUT_QUANTILE_CUTOFF,
+                                    timeout0);
+  do {
+    int n = 0;
+    for (i=0; i < MIN_CIRCUITS_TO_OBSERVE; i++) {
+      if (circuit_build_times_add_time(&estimate,
+              circuit_build_times_generate_sample(&initial, 0,
+                  MAX_SYNTHETIC_QUANTILE)) == 0) {
+        n++;
+      }
+    }
+    circuit_build_times_update_alpha(&estimate);
+    timeout1 = circuit_build_times_calculate_timeout(&estimate,
+                                  BUILDTIMEOUT_QUANTILE_CUTOFF);
+    circuit_build_times_set_timeout(&estimate);
+    log_warn(LD_CIRC, "Timeout is %lf, Xm is %d", timeout1, estimate.Xm);
+    /* XXX: 5% distribution error may not be the right metric */
+  } while (fabs(circuit_build_times_cdf(&initial, timeout0) -
+                circuit_build_times_cdf(&initial, timeout1)) > 0.05
+                /* 5% error */
+           && estimate.total_build_times < NCIRCUITS_TO_OBSERVE);
+
+  test_assert(estimate.total_build_times < NCIRCUITS_TO_OBSERVE);
+
+  circuit_build_times_update_state(&estimate, &state);
+  test_assert(circuit_build_times_parse_state(&final, &state, &msg) == 0);
+
+  circuit_build_times_update_alpha(&final);
+  timeout2 = circuit_build_times_calculate_timeout(&final,
+                                 BUILDTIMEOUT_QUANTILE_CUTOFF);
+
+  circuit_build_times_set_timeout(&final);
+  log_warn(LD_CIRC, "Timeout is %lf, Xm is %d", timeout2, final.Xm);
+
+  test_assert(fabs(circuit_build_times_cdf(&initial, timeout0) -
+                   circuit_build_times_cdf(&initial, timeout2)) < 0.05);
+
+  /* Generate MAX_RECENT_TIMEOUT_RATE*RECENT_CIRCUITS timeouts
+   * and 1-that regular values. Then check for timeout error
+   * Do the same for one less timeout */
+  for (i = 0; i < RECENT_CIRCUITS; i++) {
+    circuit_build_times_add_time(&estimate,
+          circuit_build_times_generate_sample(&estimate, 0,
+              BUILDTIMEOUT_QUANTILE_CUTOFF));
+    circuit_build_times_add_time(&final,
+          circuit_build_times_generate_sample(&final, 0,
+              BUILDTIMEOUT_QUANTILE_CUTOFF));
+  }
+
+  test_assert(!circuit_build_times_check_too_many_timeouts(&estimate));
+  test_assert(!circuit_build_times_check_too_many_timeouts(&final));
+
+  for (i = 0; i < MAX_RECENT_TIMEOUT_RATE*RECENT_CIRCUITS; i++) {
+    circuit_build_times_add_timeout_worker(&estimate,
+                                           BUILDTIMEOUT_QUANTILE_CUTOFF);
+    if (i < MAX_RECENT_TIMEOUT_RATE*RECENT_CIRCUITS-1) {
+      circuit_build_times_add_timeout_worker(&final,
+                                             BUILDTIMEOUT_QUANTILE_CUTOFF);
+    }
+  }
+
+  test_assert(circuit_build_times_check_too_many_timeouts(&estimate) == 1);
+  test_assert(!circuit_build_times_check_too_many_timeouts(&final));
+
+done:
+  return;
 }
 
 extern const char AUTHORITY_CERT_1[];
@@ -4931,6 +5031,7 @@ static struct {
   ENT(dirutil),
   SUBENT(dirutil, measured_bw),
   SUBENT(dirutil, param_voting),
+  ENT(circuit_timeout),
   ENT(v3_networkstatus),
   ENT(policies),
   ENT(rend_fns),