Move the circuit build timeout code into its own file.

20 files changed, 1665 insertions, 3594 deletions

diff --git a/src/or/channel.c b/src/or/channel.c
index d0e36cd28..05ff9e246 100644
--- a/src/or/channel.c
+++ b/src/or/channel.c
@@ -18,8 +18,10 @@
 #include "channeltls.h"
 #include "circuitbuild.h"
 #include "circuitlist.h"
+#include "circuitstats.h"
 #include "connection_or.h" /* For var_cell_free() */
 #include "circuitmux.h"
+#include "entrynodes.h"
 #include "geoip.h"
 #include "nodelist.h"
 #include "relay.h"
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 9287084cb..75f0d5b80 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -9,12 +9,11 @@
  * \brief The actual details of building circuits.
  **/
 
-#define CIRCUIT_PRIVATE
-
 #include "or.h"
 #include "channel.h"
 #include "circuitbuild.h"
 #include "circuitlist.h"
+#include "circuitstats.h"
 #include "circuituse.h"
 #include "command.h"
 #include "config.h"
@@ -24,6 +23,7 @@
 #include "connection_or.h"
 #include "control.h"
 #include "directory.h"
+#include "entrynodes.h"
 #include "main.h"
 #include "networkstatus.h"
 #include "nodelist.h"
@@ -36,95 +36,17 @@
 #include "routerlist.h"
 #include "routerparse.h"
 #include "routerset.h"
-#include "statefile.h"
 #include "crypto.h"
-#undef log
-#include <math.h>
 
 #ifndef MIN
 #define MIN(a,b) ((a)<(b)?(a):(b))
 #endif
 
-#define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
-
 /********* START VARIABLES **********/
-/** Global list of circuit build times */
-// XXXX: 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.
-/* XXXX024 Make this static; add accessor functions. */
-circuit_build_times_t circ_times;
 
 /** A global list of all circuits at this hop. */
 extern circuit_t *global_circuitlist;
 
-/** An entry_guard_t represents our information about a chosen long-term
- * first hop, known as a "helper" node in the literature. We can't just
- * use a node_t, since we want to remember these even when we
- * don't have any directory info. */
-typedef struct {
-  char nickname[MAX_NICKNAME_LEN+1];
-  char identity[DIGEST_LEN];
-  time_t chosen_on_date; /**< Approximately when was this guard added?
-                          * "0" if we don't know. */
-  char *chosen_by_version; /**< What tor version added this guard? NULL
-                            * if we don't know. */
-  unsigned int made_contact : 1; /**< 0 if we have never connected to this
-                                  * router, 1 if we have. */
-  unsigned int can_retry : 1; /**< Should we retry connecting to this entry,
-                               * in spite of having it marked as unreachable?*/
-  unsigned int path_bias_notice : 1; /**< Did we alert the user about path bias
-                                      * for this node already? */
-  unsigned int path_bias_disabled : 1; /**< Have we disabled this node because
-                                        * of path bias issues? */
-  time_t bad_since; /**< 0 if this guard is currently usable, or the time at
-                      * which it was observed to become (according to the
-                      * directory or the user configuration) unusable. */
-  time_t unreachable_since; /**< 0 if we can connect to this guard, or the
-                             * time at which we first noticed we couldn't
-                             * connect to it. */
-  time_t last_attempted; /**< 0 if we can connect to this guard, or the time
-                          * at which we last failed to connect to it. */
-
-  unsigned first_hops; /**< Number of first hops this guard has completed */
-  unsigned circuit_successes; /**< Number of successfully built circuits using
-                               * this guard as first hop. */
-} entry_guard_t;
-
-/** Information about a configured bridge. Currently this just matches the
- * ones in the torrc file, but one day we may be able to learn about new
- * bridges on our own, and remember them in the state file. */
-typedef struct {
-  /** Address of the bridge. */
-  tor_addr_t addr;
-  /** TLS port for the bridge. */
-  uint16_t port;
-  /** Boolean: We are re-parsing our bridge list, and we are going to remove
-   * this one if we don't find it in the list of configured bridges. */
-  unsigned marked_for_removal : 1;
-  /** Expected identity digest, or all zero bytes if we don't know what the
-   * digest should be. */
-  char identity[DIGEST_LEN];
-
-  /** Name of pluggable transport protocol taken from its config line. */
-  char *transport_name;
-
-  /** When should we next try to fetch a descriptor for this bridge? */
-  download_status_t fetch_status;
-} bridge_info_t;
-
-/** A list of our chosen entry guards. */
-static smartlist_t *entry_guards = NULL;
-/** A value of 1 means that the entry_guards list has changed
- * 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 channel_t * channel_connect_for_circuit(const tor_addr_t *addr,
@@ -137,12 +59,6 @@ static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
 static int onion_extend_cpath(origin_circuit_t *circ);
 static int count_acceptable_nodes(smartlist_t *routers);
 static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
-
-static void entry_guards_changed(void);
-static entry_guard_t *entry_guard_get_by_id_digest(const char *digest);
-
-static void bridge_free(bridge_info_t *bridge);
-
 static int entry_guard_inc_first_hop_count(entry_guard_t *guard);
 static void pathbias_count_success(origin_circuit_t *circ);
 
@@ -162,1541 +78,6 @@ channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
   return chan;
 }
 
-/**
- * This function decides if CBT learning should be disabled. It returns
- * true if one or more of the following four conditions are met:
- *
- *  1. If the cbtdisabled consensus parameter is set.
- *  2. If the torrc option LearnCircuitBuildTimeout is false.
- *  3. If we are a directory authority
- *  4. If we fail to write circuit build time history to our state file.
- */
-static int
-circuit_build_times_disabled(void)
-{
-  if (unit_tests) {
-    return 0;
-  } else {
-    int consensus_disabled = networkstatus_get_param(NULL, "cbtdisabled",
-                                                     0, 0, 1);
-    int config_disabled = !get_options()->LearnCircuitBuildTimeout;
-    int dirauth_disabled = get_options()->AuthoritativeDir;
-    int state_disabled = did_last_state_file_write_fail() ? 1 : 0;
-
-    if (consensus_disabled || config_disabled || dirauth_disabled ||
-           state_disabled) {
-      log_debug(LD_CIRC,
-               "CircuitBuildTime learning is disabled. "
-               "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
-               consensus_disabled, config_disabled, dirauth_disabled,
-               state_disabled);
-      return 1;
-    } else {
-      log_debug(LD_CIRC,
-                "CircuitBuildTime learning is not disabled. "
-                "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
-                consensus_disabled, config_disabled, dirauth_disabled,
-                state_disabled);
-      return 0;
-    }
-  }
-}
-
-/**
- * Retrieve and bounds-check the cbtmaxtimeouts consensus paramter.
- *
- * Effect: When this many timeouts happen in the last 'cbtrecentcount'
- * circuit attempts, the client should discard all of its history and
- * begin learning a fresh timeout value.
- */
-static int32_t
-circuit_build_times_max_timeouts(void)
-{
-  int32_t cbt_maxtimeouts;
-
-  cbt_maxtimeouts = networkstatus_get_param(NULL, "cbtmaxtimeouts",
-                                 CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT,
-                                 CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
-                                 CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);
-
-  if (!(get_options()->LearnCircuitBuildTimeout)) {
-    log_debug(LD_BUG,
-              "circuit_build_times_max_timeouts() called, cbtmaxtimeouts is"
-              " %d",
-              cbt_maxtimeouts);
-  }
-
-  return cbt_maxtimeouts;
-}
-
-/**
- * Retrieve and bounds-check the cbtnummodes consensus paramter.
- *
- * Effect: This value governs how many modes to use in the weighted
- * average calculation of Pareto parameter Xm. A value of 3 introduces
- * some bias (2-5% of CDF) under ideal conditions, but allows for better
- * performance in the event that a client chooses guard nodes of radically
- * different performance characteristics.
- */
-static int32_t
-circuit_build_times_default_num_xm_modes(void)
-{
-  int32_t num = networkstatus_get_param(NULL, "cbtnummodes",
-                                        CBT_DEFAULT_NUM_XM_MODES,
-                                        CBT_MIN_NUM_XM_MODES,
-                                        CBT_MAX_NUM_XM_MODES);
-
-  if (!(get_options()->LearnCircuitBuildTimeout)) {
-    log_debug(LD_BUG,
-              "circuit_build_times_default_num_xm_modes() called, cbtnummodes"
-              " is %d",
-              num);
-  }
-
-  return num;
-}
-
-/**
- * Retrieve and bounds-check the cbtmincircs consensus paramter.
- *
- * Effect: This is the minimum number of circuits to build before
- * computing a timeout.
- */
-static int32_t
-circuit_build_times_min_circs_to_observe(void)
-{
-  int32_t num = networkstatus_get_param(NULL, "cbtmincircs",
-                                        CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE,
-                                        CBT_MIN_MIN_CIRCUITS_TO_OBSERVE,
-                                        CBT_MAX_MIN_CIRCUITS_TO_OBSERVE);
-
-  if (!(get_options()->LearnCircuitBuildTimeout)) {
-    log_debug(LD_BUG,
-              "circuit_build_times_min_circs_to_observe() called, cbtmincircs"
-              " is %d",
-              num);
-  }
-
-  return num;
-}
-
-/** Return true iff <b>cbt</b> has recorded enough build times that we
- * want to start acting on the timeout it implies. */
-int
-circuit_build_times_enough_to_compute(circuit_build_times_t *cbt)
-{
-  return cbt->total_build_times >= circuit_build_times_min_circs_to_observe();
-}
-
-/**
- * Retrieve and bounds-check the cbtquantile consensus paramter.
- *
- * Effect: This is the position on the quantile curve to use to set the
- * timeout value. It is a percent (10-99).
- */
-double
-circuit_build_times_quantile_cutoff(void)
-{
-  int32_t num = networkstatus_get_param(NULL, "cbtquantile",
-                                        CBT_DEFAULT_QUANTILE_CUTOFF,
-                                        CBT_MIN_QUANTILE_CUTOFF,
-                                        CBT_MAX_QUANTILE_CUTOFF);
-
-  if (!(get_options()->LearnCircuitBuildTimeout)) {
-    log_debug(LD_BUG,
-              "circuit_build_times_quantile_cutoff() called, cbtquantile"
-              " is %d",
-              num);
-  }
-
-  return num/100.0;
-}
-
-/* DOCDOC circuit_build_times_get_bw_scale */
-int
-circuit_build_times_get_bw_scale(networkstatus_t *ns)
-{
-  return networkstatus_get_param(ns, "bwweightscale",
-                                 BW_WEIGHT_SCALE,
-                                 BW_MIN_WEIGHT_SCALE,
-                                 BW_MAX_WEIGHT_SCALE);
-}
-
-/**
- * Retrieve and bounds-check the cbtclosequantile consensus paramter.
- *
- * Effect: This is the position on the quantile curve to use to set the
- * timeout value to use to actually close circuits. It is a percent
- * (0-99).
- */
-static double
-circuit_build_times_close_quantile(void)
-{
-  int32_t param;
-  /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */
-  int32_t min = (int)tor_lround(100*circuit_build_times_quantile_cutoff());
-  param = networkstatus_get_param(NULL, "cbtclosequantile",
-             CBT_DEFAULT_CLOSE_QUANTILE,
-             CBT_MIN_CLOSE_QUANTILE,
-             CBT_MAX_CLOSE_QUANTILE);
-
-  if (!(get_options()->LearnCircuitBuildTimeout)) {
-    log_debug(LD_BUG,
-              "circuit_build_times_close_quantile() called, cbtclosequantile"
-              " is %d", param);
-  }
-
-  if (param < min) {
-    log_warn(LD_DIR, "Consensus parameter cbtclosequantile is "
-             "too small, raising to %d", min);
-    param = min;
-  }
-  return param / 100.0;
-}
-
-/**
- * Retrieve and bounds-check the cbttestfreq consensus paramter.
- *
- * Effect: Describes how often in seconds to build a test circuit to
- * gather timeout values. Only applies if less than 'cbtmincircs'
- * have been recorded.
- */
-static int32_t
-circuit_build_times_test_frequency(void)
-{
-  int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
-                                        CBT_DEFAULT_TEST_FREQUENCY,
-                                        CBT_MIN_TEST_FREQUENCY,
-                                        CBT_MAX_TEST_FREQUENCY);
-
-  if (!(get_options()->LearnCircuitBuildTimeout)) {
-    log_debug(LD_BUG,
-              "circuit_build_times_test_frequency() called, cbttestfreq is %d",
-              num);
-  }
-
-  return num;
-}
-
-/**
- * Retrieve and bounds-check the cbtmintimeout consensus parameter.
- *
- * Effect: This is the minimum allowed timeout value in milliseconds.
- * The minimum is to prevent rounding to 0 (we only check once
- * per second).
- */
-static int32_t
-circuit_build_times_min_timeout(void)
-{
-  int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
-                                        CBT_DEFAULT_TIMEOUT_MIN_VALUE,
-                                        CBT_MIN_TIMEOUT_MIN_VALUE,
-                                        CBT_MAX_TIMEOUT_MIN_VALUE);
-
-  if (!(get_options()->LearnCircuitBuildTimeout)) {
-    log_debug(LD_BUG,
-              "circuit_build_times_min_timeout() called, cbtmintimeout is %d",
-              num);
-  }
-
-  return num;
-}
-
-/**
- * Retrieve and bounds-check the cbtinitialtimeout consensus paramter.
- *
- * Effect: This is the timeout value to use before computing a timeout,
- * in milliseconds.
- */
-int32_t
-circuit_build_times_initial_timeout(void)
-{
-  int32_t min = circuit_build_times_min_timeout();
-  int32_t param = networkstatus_get_param(NULL, "cbtinitialtimeout",
-                                          CBT_DEFAULT_TIMEOUT_INITIAL_VALUE,
-                                          CBT_MIN_TIMEOUT_INITIAL_VALUE,
-                                          CBT_MAX_TIMEOUT_INITIAL_VALUE);
-
-  if (!(get_options()->LearnCircuitBuildTimeout)) {
-    log_debug(LD_BUG,
-              "circuit_build_times_initial_timeout() called, "
-              "cbtinitialtimeout is %d",
-              param);
-  }
-
-  if (param < min) {
-    log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, "
-             "raising to %d", min);
-    param = min;
-  }
-  return param;
-}
-
-/**
- * Retrieve and bounds-check the cbtrecentcount consensus paramter.
- *
- * Effect: This is the number of circuit build times to keep track of
- * for deciding if we hit cbtmaxtimeouts and need to reset our state
- * and learn a new timeout.
- */
-static int32_t
-circuit_build_times_recent_circuit_count(networkstatus_t *ns)
-{
-  int32_t num;
-  num = networkstatus_get_param(ns, "cbtrecentcount",
-                                CBT_DEFAULT_RECENT_CIRCUITS,
-                                CBT_MIN_RECENT_CIRCUITS,
-                                CBT_MAX_RECENT_CIRCUITS);
-
-  if (!(get_options()->LearnCircuitBuildTimeout)) {
-    log_debug(LD_BUG,
-              "circuit_build_times_recent_circuit_count() called, "
-              "cbtrecentcount is %d",
-              num);
-  }
-
-  return num;
-}
-
-/**
- * This function is called when we get a consensus update.
- *
- * It checks to see if we have changed any consensus parameters
- * that require reallocation or discard of previous stats.
- */
-void
-circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
-                                         networkstatus_t *ns)
-{
-  int32_t num;
-
-  /*
-   * First check if we're doing adaptive timeouts at all; nothing to
-   * update if we aren't.
-   */
-
-  if (!circuit_build_times_disabled()) {
-    num = circuit_build_times_recent_circuit_count(ns);
-
-    if (num > 0) {
-      if (num != cbt->liveness.num_recent_circs) {
-        int8_t *recent_circs;
-        log_notice(LD_CIRC, "The Tor Directory Consensus has changed how many "
-                   "circuits we must track to detect network failures from %d "
-                   "to %d.", cbt->liveness.num_recent_circs, num);
-
-        tor_assert(cbt->liveness.timeouts_after_firsthop ||
-                   cbt->liveness.num_recent_circs == 0);
-
-        /*
-         * Technically this is a circular array that we are reallocating
-         * and memcopying. However, since it only consists of either 1s
-         * or 0s, and is only used in a statistical test to determine when
-         * we should discard our history after a sufficient number of 1's
-         * have been reached, it is fine if order is not preserved or
-         * elements are lost.
-         *
-         * cbtrecentcount should only be changing in cases of severe network
-         * distress anyway, so memory correctness here is paramount over
-         * doing acrobatics to preserve the array.
-         */
-        recent_circs = tor_malloc_zero(sizeof(int8_t)*num);
-        if (cbt->liveness.timeouts_after_firsthop &&
-            cbt->liveness.num_recent_circs > 0) {
-          memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop,
-                 sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs));
-        }
-
-        // Adjust the index if it needs it.
-        if (num < cbt->liveness.num_recent_circs) {
-          cbt->liveness.after_firsthop_idx = MIN(num-1,
-                  cbt->liveness.after_firsthop_idx);
-        }
-
-        tor_free(cbt->liveness.timeouts_after_firsthop);
-        cbt->liveness.timeouts_after_firsthop = recent_circs;
-        cbt->liveness.num_recent_circs = num;
-      }
-      /* else no change, nothing to do */
-    } else { /* num == 0 */
-      /*
-       * Weird.  This probably shouldn't happen, so log a warning, but try
-       * to do something sensible anyway.
-       */
-
-      log_warn(LD_CIRC,
-               "The cbtrecentcircs consensus parameter came back zero!  "
-               "This disables adaptive timeouts since we can't keep track of "
-               "any recent circuits.");
-
-      circuit_build_times_free_timeouts(cbt);
-    }
-  } else {
-    /*
-     * Adaptive timeouts are disabled; this might be because of the
-     * LearnCircuitBuildTimes config parameter, and hence permanent, or
-     * the cbtdisabled consensus parameter, so it may be a new condition.
-     * Treat it like getting num == 0 above and free the circuit history
-     * if we have any.
-     */
-
-    circuit_build_times_free_timeouts(cbt);
-  }
-}
-
-/** 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;
-}
-
-/**
- * Return the initial default or configured timeout in milliseconds
- */
-static double
-circuit_build_times_get_initial_timeout(void)
-{
-  double timeout;
-
-  /*
-   * Check if we have LearnCircuitBuildTimeout, and if we don't,
-   * always use CircuitBuildTimeout, no questions asked.
-   */
-  if (get_options()->LearnCircuitBuildTimeout) {
-    if (!unit_tests && get_options()->CircuitBuildTimeout) {
-      timeout = get_options()->CircuitBuildTimeout*1000;
-      if (timeout < circuit_build_times_min_timeout()) {
-        log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
-                 circuit_build_times_min_timeout()/1000);
-        timeout = circuit_build_times_min_timeout();
-      }
-    } else {
-      timeout = circuit_build_times_initial_timeout();
-    }
-  } else {
-    timeout = get_options()->CircuitBuildTimeout*1000;
-  }
-
-  return timeout;
-}
-
-/**
- * Reset the build time state.
- *
- * Leave estimated parameters, timeout and network liveness intact
- * 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->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 values based on either the config setting,
- * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
- */
-void
-circuit_build_times_init(circuit_build_times_t *cbt)
-{
-  memset(cbt, 0, sizeof(*cbt));
-  /*
-   * Check if we really are using adaptive timeouts, and don't keep
-   * track of this stuff if not.
-   */
-  if (!circuit_build_times_disabled()) {
-    cbt->liveness.num_recent_circs =
-      circuit_build_times_recent_circuit_count(NULL);
-    cbt->liveness.timeouts_after_firsthop =
-      tor_malloc_zero(sizeof(int8_t)*cbt->liveness.num_recent_circs);
-  } else {
-    cbt->liveness.num_recent_circs = 0;
-    cbt->liveness.timeouts_after_firsthop = NULL;
-  }
-  cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
-  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
-}
-
-/**
- * Free the saved timeouts, if the cbtdisabled consensus parameter got turned
- * on or something.
- */
-
-void
-circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
-{
-  if (!cbt) return;
-
-  if (cbt->liveness.timeouts_after_firsthop) {
-    tor_free(cbt->liveness.timeouts_after_firsthop);
-  }
-
-  cbt->liveness.num_recent_circs = 0;
-}
-
-#if 0
-/**
- * Rewind our build time history by n positions.
- */
-static void
-circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
-{
-  int i = 0;
-
-  cbt->build_times_idx -= n;
-  cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;
-
-  for (i = 0; i < n; i++) {
-    cbt->circuit_build_times[(i+cbt->build_times_idx)
-                             %CBT_NCIRCUITS_TO_OBSERVE]=0;
-  }
-
-  if (cbt->total_build_times > n) {
-    cbt->total_build_times -= n;
-  } else {
-    cbt->total_build_times = 0;
-  }
-
-  log_info(LD_CIRC,
-          "Rewound history by %d places. Current index: %d. "
-          "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
-}
-#endif
-
-/**
- * Add a new build time value <b>time</b> to the set of build times. Time
- * units are milliseconds.
- *
- * circuit_build_times <b>cbt</b> 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 <= 0 || time > CBT_BUILD_TIME_MAX) {
-    log_warn(LD_BUG, "Circuit build time is too large (%u)."
-                      "This is probably a bug.", time);
-    tor_fragile_assert();
-    return -1;
-  }
-
-  log_debug(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) % CBT_NCIRCUITS_TO_OBSERVE;
-  if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
-    cbt->total_build_times++;
-
-  if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
-    /* Save state every n 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 < CBT_NCIRCUITS_TO_OBSERVE; i++) {
-    if (cbt->circuit_build_times[i] > max_build_time
-            && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED)
-      max_build_time = cbt->circuit_build_times[i];
-  }
-  return max_build_time;
-}
-
-#if 0
-/** Return minimum circuit build time */
-build_time_t
-circuit_build_times_min(circuit_build_times_t *cbt)
-{
-  int i = 0;
-  build_time_t min_build_time = CBT_BUILD_TIME_MAX;
-  for (i = 0; i < CBT_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 == CBT_BUILD_TIME_MAX) {
-    log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
-  }
-  return min_build_time;
-}
-#endif
-
-/**
- * Calculate and return a histogram for the set of build times.
- *
- * Returns an allocated array of histrogram bins representing
- * the frequency of index*CBT_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 / CBT_BIN_WIDTH);
-  histogram = tor_malloc_zero(*nbins * sizeof(build_time_t));
-
-  // calculate histogram
-  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
-    if (cbt->circuit_build_times[i] == 0
-            || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
-      continue; /* 0 <-> uninitialized */
-
-    c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH);
-    histogram[c]++;
-  }
-
-  return histogram;
-}
-
-/**
- * Return the Pareto start-of-curve parameter Xm.
- *
- * Because we are not a true Pareto curve, we compute this as the
- * weighted average of the N most frequent build time bins. N is either
- * 1 if we don't have enough circuit build time data collected, or
- * determined by the consensus parameter cbtnummodes (default 3).
- */
-static build_time_t
-circuit_build_times_get_xm(circuit_build_times_t *cbt)
-{
-  build_time_t i, nbins;
-  build_time_t *nth_max_bin;
-  int32_t bin_counts=0;
-  build_time_t ret = 0;
-  uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
-  int n=0;
-  int num_modes = circuit_build_times_default_num_xm_modes();
-
-  tor_assert(nbins > 0);
-  tor_assert(num_modes > 0);
-
-  // Only use one mode if < 1000 buildtimes. Not enough data
-  // for multiple.
-  if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
-    num_modes = 1;
-
-  nth_max_bin = (build_time_t*)tor_malloc_zero(num_modes*sizeof(build_time_t));
-
-  /* Determine the N most common build times */
-  for (i = 0; i < nbins; i++) {
-    if (histogram[i] >= histogram[nth_max_bin[0]]) {
-      nth_max_bin[0] = i;
-    }
-
-    for (n = 1; n < num_modes; n++) {
-      if (histogram[i] >= histogram[nth_max_bin[n]] &&
-           (!histogram[nth_max_bin[n-1]]
-               || histogram[i] < histogram[nth_max_bin[n-1]])) {
-        nth_max_bin[n] = i;
-      }
-    }
-  }
-
-  for (n = 0; n < num_modes; n++) {
-    bin_counts += histogram[nth_max_bin[n]];
-    ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]];
-    log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]),
-             histogram[nth_max_bin[n]]);
-  }
-
-  /* The following assert is safe, because we don't get called when we
-   * haven't observed at least CBT_MIN_MIN_CIRCUITS_TO_OBSERVE circuits. */
-  tor_assert(bin_counts > 0);
-
-  ret /= bin_counts;
-  tor_free(histogram);
-  tor_free(nth_max_bin);
-
-  return ret;
-}
-
-/**
- * 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;
-  state->CircuitBuildAbandonedCount = 0;
-
-  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
-    if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
-      state->CircuitBuildAbandonedCount++;
-  }
-
-  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");
-    tor_asprintf(&line->value, "%d %d",
-            CBT_BIN_TO_MS(i), histogram[i]);
-    next = &(line->next);
-  }
-
-  if (!unit_tests) {
-    if (!get_options()->AvoidDiskWrites)
-      or_state_mark_dirty(get_or_state(), 0);
-  }
-
-  tor_free(histogram);
-}
-
-/**
- * Shuffle the build times array.
- *
- * Adapted from http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
- */
-static void
-circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
-                                            build_time_t *raw_times,
-                                            uint32_t num_times)
-{
-  uint32_t n = num_times;
-  if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
-    log_notice(LD_CIRC, "The number of circuit times that this Tor version "
-               "uses to calculate build times is less than the number stored "
-               "in your state file. Decreasing the circuit time history from "
-               "%lu to %d.", (unsigned long)num_times,
-               CBT_NCIRCUITS_TO_OBSERVE);
-  }
-
-  if (n > INT_MAX-1) {
-    log_warn(LD_CIRC, "For some insane reasons, you had %lu circuit build "
-             "observations in your state file. That's far too many; probably "
-             "there's a bug here.", (unsigned long)n);
-    n = INT_MAX-1;
-  }
-
-  /* This code can only be run on a compact array */
-  while (n-- > 1) {
-    int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
-    build_time_t tmp = raw_times[k];
-    raw_times[k] = raw_times[n];
-    raw_times[n] = tmp;
-  }
-
-  /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
-   * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
-  for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) {
-    circuit_build_times_add_time(cbt, raw_times[n]);
-  }
-}
-
-/**
- * Filter old synthetic timeouts that were created before the
- * new right-censored Pareto calculation was deployed.
- *
- * Once all clients before 0.2.1.13-alpha are gone, this code
- * will be unused.
- */
-static int
-circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
-{
-  int num_filtered=0, i=0;
-  double timeout_rate = 0;
-  build_time_t max_timeout = 0;
-
-  timeout_rate = circuit_build_times_timeout_rate(cbt);
-  max_timeout = (build_time_t)cbt->close_ms;
-
-  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
-    if (cbt->circuit_build_times[i] > max_timeout) {
-      build_time_t replaced = cbt->circuit_build_times[i];
-      num_filtered++;
-      cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED;
-
-      log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced,
-               cbt->circuit_build_times[i]);
-    }
-  }
-
-  log_info(LD_CIRC,
-           "We had %d timeouts out of %d build times, "
-           "and filtered %d above the max of %u",
-          (int)(cbt->total_build_times*timeout_rate),
-          cbt->total_build_times, num_filtered, max_timeout);
-
-  return num_filtered;
-}
-
-/**
- * Load histogram from <b>state</b>, shuffling the resulting array
- * after we do so. Use this result to estimate parameters and
- * calculate the timeout.
- *
- * Return -1 on error.
- */
-int
-circuit_build_times_parse_state(circuit_build_times_t *cbt,
-                                or_state_t *state)
-{
-  int tot_values = 0;
-  uint32_t loaded_cnt = 0, N = 0;
-  config_line_t *line;
-  unsigned int i;
-  build_time_t *loaded_times;
-  int err = 0;
-  circuit_build_times_init(cbt);
-
-  if (circuit_build_times_disabled()) {
-    return 0;
-  }
-
-  /* build_time_t 0 means uninitialized */
-  loaded_times = tor_malloc_zero(sizeof(build_time_t)*state->TotalBuildTimes);
-
-  for (line = state->BuildtimeHistogram; line; line = line->next) {
-    smartlist_t *args = smartlist_new();
-    smartlist_split_string(args, line->value, " ",
-                           SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
-    if (smartlist_len(args) < 2) {
-      log_warn(LD_GENERAL, "Unable to parse circuit build times: "
-                           "Too few arguments to CircuitBuildTime");
-      err = 1;
-      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,
-                                         CBT_BUILD_TIME_MAX, &ok, NULL);
-      if (!ok) {
-        log_warn(LD_GENERAL, "Unable to parse circuit build times: "
-                             "Unparsable bin number");
-        err = 1;
-        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
-        smartlist_free(args);
-        break;
-      }
-      count = (uint32_t)tor_parse_ulong(count_str, 0, 0,
-                                        UINT32_MAX, &ok, NULL);
-      if (!ok) {
-        log_warn(LD_GENERAL, "Unable to parse circuit build times: "
-                             "Unparsable bin count");
-        err = 1;
-        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
-        smartlist_free(args);
-        break;
-      }
-
-      if (loaded_cnt+count+state->CircuitBuildAbandonedCount
-            > state->TotalBuildTimes) {
-        log_warn(LD_CIRC,
-                 "Too many build times in state file. "
-                 "Stopping short before %d",
-                 loaded_cnt+count);
-        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
-        smartlist_free(args);
-        break;
-      }
-
-      for (k = 0; k < count; k++) {
-        loaded_times[loaded_cnt++] = ms;
-      }
-      N++;
-      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
-      smartlist_free(args);
-    }
-  }
-
-  log_info(LD_CIRC,
-           "Adding %d timeouts.", state->CircuitBuildAbandonedCount);
-  for (i=0; i < state->CircuitBuildAbandonedCount; i++) {
-    loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED;
-  }
-
-  if (loaded_cnt != state->TotalBuildTimes) {
-    log_warn(LD_CIRC,
-            "Corrupt state file? Build times count mismatch. "
-            "Read %d times, but file says %d", loaded_cnt,
-            state->TotalBuildTimes);
-    err = 1;
-    circuit_build_times_reset(cbt);
-    goto done;
-  }
-
-  circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
-
-  /* Verify that we didn't overwrite any indexes */
-  for (i=0; i < CBT_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);
-
-  if (cbt->total_build_times != tot_values
-        || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) {
-    log_warn(LD_CIRC,
-            "Corrupt state file? Shuffled build times mismatch. "
-            "Read %d times, but file says %d", tot_values,
-            state->TotalBuildTimes);
-    err = 1;
-    circuit_build_times_reset(cbt);
-    goto done;
-  }
-
-  circuit_build_times_set_timeout(cbt);
-
-  if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) {
-    circuit_build_times_filter_timeouts(cbt);
-  }
-
- done:
-  tor_free(loaded_times);
-  return err ? -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.
- */
-int
-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,abandoned_count=0;
-  build_time_t max_time=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_get_xm(cbt);
-
-  tor_assert(cbt->Xm > 0);
-
-  for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) {
-    if (!x[i]) {
-      continue;
-    }
-
-    if (x[i] < cbt->Xm) {
-      a += tor_mathlog(cbt->Xm);
-    } else if (x[i] == CBT_BUILD_ABANDONED) {
-      abandoned_count++;
-    } else {
-      a += tor_mathlog(x[i]);
-      if (x[i] > max_time)
-        max_time = x[i];
-    }
-    n++;
-  }
-
-  /*
-   * We are erring and asserting here because this can only happen
-   * in codepaths other than startup. The startup state parsing code
-   * performs this same check, and resets state if it hits it. If we
-   * hit it at runtime, something serious has gone wrong.
-   */
-  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);
-
-  if (max_time <= 0) {
-    /* This can happen if Xm is actually the *maximum* value in the set.
-     * It can also happen if we've abandoned every single circuit somehow.
-     * In either case, tell the caller not to compute a new build timeout. */
-    log_warn(LD_BUG,
-             "Could not determine largest build time (%d). "
-             "Xm is %dms and we've abandoned %d out of %d circuits.", max_time,
-             cbt->Xm, abandoned_count, n);
-    return 0;
-  }
-
-  a += abandoned_count*tor_mathlog(max_time);
-
-  a -= n*tor_mathlog(cbt->Xm);
-  // Estimator comes from Eq #4 in:
-  // "Bayesian estimation based on trimmed samples from Pareto populations"
-  // by Arturo J. Fernández. We are right-censored only.
-  a = (n-abandoned_count)/a;
-
-  cbt->alpha = a;
-
-  return 1;
-}
-
-/**
- * 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.
- *
- * Return value is in milliseconds.
- */
-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 within the [q_lo, 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)
-{
-  double randval = crypto_rand_double();
-  build_time_t ret;
-  double u;
-
-  /* Generate between [q_lo, q_hi) */
-  /*XXXX This is what nextafter is supposed to be for; we should use it on the
-   * platforms that support it. */
-  q_hi -= 1.0/(INT32_MAX);
-
-  tor_assert(q_lo >= 0);
-  tor_assert(q_hi < 1);
-  tor_assert(q_lo < q_hi);
-
-  u = q_lo + (q_hi-q_lo)*randval;
-
-  tor_assert(0 <= u && u < 1.0);
-  /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
-  ret = (build_time_t)
-    tor_lround(circuit_build_times_calculate_timeout(cbt, u));
-  tor_assert(ret > 0);
-  return ret;
-}
-
-/**
- * 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, double timeout_ms)
-{
-  // 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 = tor_mathlog(1.0-quantile)/
-    (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
-  tor_assert(cbt->alpha > 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 */
-  return !circuit_build_times_enough_to_compute(cbt);
-}
-
-/**
- * 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 > circuit_build_times_test_frequency();
-}
-
-/**
- * Called to indicate that the network showed some signs of liveness,
- * i.e. we received a cell.
- *
- * This is used by circuit_build_times_network_check_live() to decide
- * if we should record the circuit build timeout or not.
- *
- * This function is called every time we receive a cell. Avoid
- * syscalls, events, and other high-intensity work.
- */
-void
-circuit_build_times_network_is_live(circuit_build_times_t *cbt)
-{
-  time_t now = approx_time();
-  if (cbt->liveness.nonlive_timeouts > 0) {
-    log_notice(LD_CIRC,
-               "Tor now sees network activity. Restoring circuit build "
-               "timeout recording. Network was down for %d seconds "
-               "during %d circuit attempts.",
-               (int)(now - cbt->liveness.network_last_live),
-               cbt->liveness.nonlive_timeouts);
-  }
-  cbt->liveness.network_last_live = now;
-  cbt->liveness.nonlive_timeouts = 0;
-}
-
-/**
- * Called to indicate that we completed a circuit. Because this circuit
- * succeeded, it doesn't count as a timeout-after-the-first-hop.
- *
- * This is used by circuit_build_times_network_check_changed() to determine
- * if we had too many recent timeouts and need to reset our learned timeout
- * to something higher.
- */
-void
-circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
-{
-  /* Check for NULLness because we might not be using adaptive timeouts */
-  if (cbt->liveness.timeouts_after_firsthop &&
-      cbt->liveness.num_recent_circs > 0) {
-    cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
-      = 0;
-    cbt->liveness.after_firsthop_idx++;
-    cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
-  }
-}
-
-/**
- * A circuit just timed out. If it failed after the first hop, record it
- * in our history for later deciding if the network speed has changed.
- *
- * This is used by circuit_build_times_network_check_changed() to determine
- * if we had too many recent timeouts and need to reset our learned timeout
- * to something higher.
- */
-static void
-circuit_build_times_network_timeout(circuit_build_times_t *cbt,
-                                    int did_onehop)
-{
-  /* Check for NULLness because we might not be using adaptive timeouts */
-  if (cbt->liveness.timeouts_after_firsthop &&
-      cbt->liveness.num_recent_circs > 0) {
-    if (did_onehop) {
-      cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
-        = 1;
-      cbt->liveness.after_firsthop_idx++;
-      cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
-    }
-  }
-}
-
-/**
- * A circuit was just forcibly closed. If there has been no recent network
- * activity at all, but this circuit was launched back when we thought the
- * network was live, increment the number of "nonlive" circuit timeouts.
- *
- * This is used by circuit_build_times_network_check_live() to decide
- * if we should record the circuit build timeout or not.
- */
-static void
-circuit_build_times_network_close(circuit_build_times_t *cbt,
-                                    int did_onehop, time_t start_time)
-{
-  time_t now = time(NULL);
-  /*
-   * Check if this is a timeout that was for a circuit that spent its
-   * entire existence during a time where we have had no network activity.
-   */
-  if (cbt->liveness.network_last_live < start_time) {
-    if (did_onehop) {
-      char last_live_buf[ISO_TIME_LEN+1];
-      char start_time_buf[ISO_TIME_LEN+1];
-      char now_buf[ISO_TIME_LEN+1];
-      format_local_iso_time(last_live_buf, cbt->liveness.network_last_live);
-      format_local_iso_time(start_time_buf, start_time);
-      format_local_iso_time(now_buf, now);
-      log_warn(LD_BUG,
-               "Circuit somehow completed a hop while the network was "
-               "not live. Network was last live at %s, but circuit launched "
-               "at %s. It's now %s.", last_live_buf, start_time_buf,
-               now_buf);
-    }
-    cbt->liveness.nonlive_timeouts++;
-    if (cbt->liveness.nonlive_timeouts == 1) {
-      log_notice(LD_CIRC,
-                 "Tor has not observed any network activity for the past %d "
-                 "seconds. Disabling circuit build timeout recording.",
-                 (int)(now - cbt->liveness.network_last_live));
-    } else {
-      log_info(LD_CIRC,
-             "Got non-live timeout. Current count is: %d",
-             cbt->liveness.nonlive_timeouts);
-    }
-  }
-}
-
-/**
- * When the network is not live, we do not record circuit build times.
- *
- * The network is considered not live if there has been at least one
- * circuit build that began and ended (had its close_ms measurement
- * period expire) since we last received a cell.
- *
- * Also has the side effect of rewinding the circuit time history
- * in the case of recent liveness changes.
- */
-int
-circuit_build_times_network_check_live(circuit_build_times_t *cbt)
-{
-  if (cbt->liveness.nonlive_timeouts > 0) {
-    return 0;
-  }
-
-  return 1;
-}
-
-/**
- * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
- * the past RECENT_CIRCUITS time out after the first hop. Used to detect
- * if the network connection has changed significantly, and if so,
- * resets our circuit build timeout to the default.
- *
- * 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_network_check_changed(circuit_build_times_t *cbt)
-{
-  int total_build_times = cbt->total_build_times;
-  int timeout_count=0;
-  int i;
-
-  if (cbt->liveness.timeouts_after_firsthop &&
-      cbt->liveness.num_recent_circs > 0) {
-    /* how many of our recent circuits made it to the first hop but then
-     * timed out? */
-    for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
-      timeout_count += cbt->liveness.timeouts_after_firsthop[i];
-    }
-  }
-
-  /* If 80% of our recent circuits are timing out after the first hop,
-   * we need to re-estimate a new initial alpha and timeout. */
-  if (timeout_count < circuit_build_times_max_timeouts()) {
-    return 0;
-  }
-
-  circuit_build_times_reset(cbt);
-  if (cbt->liveness.timeouts_after_firsthop &&
-      cbt->liveness.num_recent_circs > 0) {
-    memset(cbt->liveness.timeouts_after_firsthop, 0,
-            sizeof(*cbt->liveness.timeouts_after_firsthop)*
-            cbt->liveness.num_recent_circs);
-  }
-  cbt->liveness.after_firsthop_idx = 0;
-
-  /* Check to see if this has happened before. If so, double the timeout
-   * to give people on abysmally bad network connections a shot at access */
-  if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
-    if (cbt->timeout_ms > INT32_MAX/2 || cbt->close_ms > INT32_MAX/2) {
-      log_warn(LD_CIRC, "Insanely large circuit build timeout value. "
-              "(timeout = %fmsec, close = %fmsec)",
-               cbt->timeout_ms, cbt->close_ms);
-    } else {
-      cbt->timeout_ms *= 2;
-      cbt->close_ms *= 2;
-    }
-  } else {
-    cbt->close_ms = cbt->timeout_ms
-                  = circuit_build_times_get_initial_timeout();
-  }
-
-  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
-
-  log_notice(LD_CIRC,
-            "Your network connection speed appears to have changed. Resetting "
-            "timeout to %lds after %d timeouts and %d buildtimes.",
-            tor_lround(cbt->timeout_ms/1000), timeout_count,
-            total_build_times);
-
-  return 1;
-}
-
-/**
- * Count the number of timeouts in a set of cbt data.
- */
-double
-circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
-{
-  int i=0,timeouts=0;
-  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
-    if (cbt->circuit_build_times[i] >= cbt->timeout_ms) {
-       timeouts++;
-    }
-  }
-
-  if (!cbt->total_build_times)
-    return 0;
-
-  return ((double)timeouts)/cbt->total_build_times;
-}
-
-/**
- * Count the number of closed circuits in a set of cbt data.
- */
-double
-circuit_build_times_close_rate(const circuit_build_times_t *cbt)
-{
-  int i=0,closed=0;
-  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
-    if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) {
-       closed++;
-    }
-  }
-
-  if (!cbt->total_build_times)
-    return 0;
-
-  return ((double)closed)/cbt->total_build_times;
-}
-
-/**
- * Store a timeout as a synthetic value.
- *
- * Returns true if the store was successful and we should possibly
- * update our timeout estimate.
- */
-int
-circuit_build_times_count_close(circuit_build_times_t *cbt,
-                                int did_onehop,
-                                time_t start_time)
-{
-  if (circuit_build_times_disabled()) {
-    cbt->close_ms = cbt->timeout_ms
-                  = circuit_build_times_get_initial_timeout();
-    return 0;
-  }
-
-  /* Record this force-close to help determine if the network is dead */
-  circuit_build_times_network_close(cbt, did_onehop, start_time);
-
-  /* Only count timeouts if network is live.. */
-  if (!circuit_build_times_network_check_live(cbt)) {
-    return 0;
-  }
-
-  circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED);
-  return 1;
-}
-
-/**
- * Update timeout counts to determine if we need to expire
- * our build time history due to excessive timeouts.
- *
- * We do not record any actual time values at this stage;
- * we are only interested in recording the fact that a timeout
- * happened. We record the time values via
- * circuit_build_times_count_close() and circuit_build_times_add_time().
- */
-void
-circuit_build_times_count_timeout(circuit_build_times_t *cbt,
-                                  int did_onehop)
-{
-  if (circuit_build_times_disabled()) {
-    cbt->close_ms = cbt->timeout_ms
-                  = circuit_build_times_get_initial_timeout();
-    return;
-  }
-
-  /* Register the fact that a timeout just occurred. */
-  circuit_build_times_network_timeout(cbt, did_onehop);
-
-  /* If there are a ton of timeouts, we should reset
-   * the circuit build timeout. */
-  circuit_build_times_network_check_changed(cbt);
-}
-
-/**
- * Estimate a new timeout based on history and set our timeout
- * variable accordingly.
- */
-static int
-circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
-{
-  build_time_t max_time;
-  if (!circuit_build_times_enough_to_compute(cbt))
-    return 0;
-
-  if (!circuit_build_times_update_alpha(cbt))
-    return 0;
-
-  cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
-                                circuit_build_times_quantile_cutoff());
-
-  cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
-                                circuit_build_times_close_quantile());
-
-  max_time = circuit_build_times_max(cbt);
-
-  /* Sometimes really fast guard nodes give us such a steep curve
-   * that this ends up being not that much greater than timeout_ms.
-   * Make it be at least 1 min to handle this case. */
-  cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout());
-
-  if (cbt->timeout_ms > max_time) {
-    log_info(LD_CIRC,
-               "Circuit build timeout of %dms is beyond the maximum build "
-               "time we have ever observed. Capping it to %dms.",
-               (int)cbt->timeout_ms, max_time);
-    cbt->timeout_ms = max_time;
-  }
-
-  if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
-    log_info(LD_CIRC,
-               "Circuit build measurement period of %dms is more than twice "
-               "the maximum build time we have ever observed. Capping it to "
-               "%dms.", (int)cbt->close_ms, 2*max_time);
-    cbt->close_ms = 2*max_time;
-  }
-
-  cbt->have_computed_timeout = 1;
-  return 1;
-}
-
-/**
- * Exposed function to compute a new timeout. Dispatches events and
- * also filters out extremely high timeout values.
- */
-void
-circuit_build_times_set_timeout(circuit_build_times_t *cbt)
-{
-  long prev_timeout = tor_lround(cbt->timeout_ms/1000);
-  double timeout_rate;
-
-  /*
-   * Just return if we aren't using adaptive timeouts
-   */
-  if (circuit_build_times_disabled())
-    return;
-
-  if (!circuit_build_times_set_timeout_worker(cbt))
-    return;
-
-  if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
-    log_info(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms",
-             cbt->timeout_ms, circuit_build_times_min_timeout());
-    cbt->timeout_ms = circuit_build_times_min_timeout();
-    if (cbt->close_ms < cbt->timeout_ms) {
-      /* This shouldn't happen because of MAX() in timeout_worker above,
-       * but doing it just in case */
-      cbt->close_ms = circuit_build_times_initial_timeout();
-    }
-  }
-
-  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
-
-  timeout_rate = circuit_build_times_timeout_rate(cbt);
-
-  if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) {
-    log_info(LD_CIRC,
-               "Based on %d circuit times, it looks like we don't need to "
-               "wait so long for circuits to finish. We will now assume a "
-               "circuit is too slow to use after waiting %ld seconds.",
-               cbt->total_build_times,
-               tor_lround(cbt->timeout_ms/1000));
-    log_info(LD_CIRC,
-             "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
-             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
-             timeout_rate);
-  } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
-    log_info(LD_CIRC,
-               "Based on %d circuit times, it looks like we need to wait "
-               "longer for circuits to finish. We will now assume a "
-               "circuit is too slow to use after waiting %ld seconds.",
-               cbt->total_build_times,
-               tor_lround(cbt->timeout_ms/1000));
-    log_info(LD_CIRC,
-             "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
-             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
-             timeout_rate);
-  } else {
-    log_info(LD_CIRC,
-             "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f,"
-             " r: %f) based on %d circuit times",
-             tor_lround(cbt->timeout_ms/1000),
-             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
-             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.
@@ -3803,8 +2184,8 @@ choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
     });
   }
   /* and exclude current entry guards and their families, if applicable */
-  if (options->UseEntryGuards && entry_guards) {
-    SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
+  if (options->UseEntryGuards) {
+    SMARTLIST_FOREACH(get_entry_guards(), const entry_guard_t *, entry,
       {
         if ((node = node_get_by_id(entry->identity))) {
           nodelist_add_node_and_family(excluded, node);
@@ -4025,1878 +2406,3 @@ build_state_get_exit_nickname(cpath_build_state_t *state)
   return state->chosen_exit->nickname;
 }
 
-/** Check whether the entry guard <b>e</b> is usable, given the directory
- * authorities' opinion about the router (stored in <b>ri</b>) and the user's
- * configuration (in <b>options</b>). Set <b>e</b>-&gt;bad_since
- * accordingly. Return true iff the entry guard's status changes.
- *
- * If it's not usable, set *<b>reason</b> to a static string explaining why.
- */
-static int
-entry_guard_set_status(entry_guard_t *e, const node_t *node,
-                       time_t now, const or_options_t *options,
-                       const char **reason)
-{
-  char buf[HEX_DIGEST_LEN+1];
-  int changed = 0;
-
-  *reason = NULL;
-
-  /* Do we want to mark this guard as bad? */
-  if (!node)
-    *reason = "unlisted";
-  else if (!node->is_running)
-    *reason = "down";
-  else if (options->UseBridges && (!node->ri ||
-                                   node->ri->purpose != ROUTER_PURPOSE_BRIDGE))
-    *reason = "not a bridge";
-  else if (options->UseBridges && !node_is_a_configured_bridge(node))
-    *reason = "not a configured bridge";
-  else if (!options->UseBridges && !node->is_possible_guard &&
-           !routerset_contains_node(options->EntryNodes,node))
-    *reason = "not recommended as a guard";
-  else if (routerset_contains_node(options->ExcludeNodes, node))
-    *reason = "excluded";
-  else if (e->path_bias_disabled)
-    *reason = "path-biased";
-
-  if (*reason && ! e->bad_since) {
-    /* Router is newly bad. */
-    base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
-    log_info(LD_CIRC, "Entry guard %s (%s) is %s: marking as unusable.",
-             e->nickname, buf, *reason);
-
-    e->bad_since = now;
-    control_event_guard(e->nickname, e->identity, "BAD");
-    changed = 1;
-  } else if (!*reason && e->bad_since) {
-    /* There's nothing wrong with the router any more. */
-    base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN);
-    log_info(LD_CIRC, "Entry guard %s (%s) is no longer unusable: "
-             "marking as ok.", e->nickname, buf);
-
-    e->bad_since = 0;
-    control_event_guard(e->nickname, e->identity, "GOOD");
-    changed = 1;
-  }
-  return changed;
-}
-
-/** Return true iff enough time has passed since we last tried to connect
- * to the unreachable guard <b>e</b> that we're willing to try again. */
-static int
-entry_is_time_to_retry(entry_guard_t *e, time_t now)
-{
-  long diff;
-  if (e->last_attempted < e->unreachable_since)
-    return 1;
-  diff = now - e->unreachable_since;
-  if (diff < 6*60*60)
-    return now > (e->last_attempted + 60*60);
-  else if (diff < 3*24*60*60)
-    return now > (e->last_attempted + 4*60*60);
-  else if (diff < 7*24*60*60)
-    return now > (e->last_attempted + 18*60*60);
-  else
-    return now > (e->last_attempted + 36*60*60);
-}
-
-/** Return the node corresponding to <b>e</b>, if <b>e</b> is
- * working well enough that we are willing to use it as an entry
- * right now. (Else return NULL.) In particular, it must be
- * - Listed as either up or never yet contacted;
- * - Present in the routerlist;
- * - Listed as 'stable' or 'fast' by the current dirserver consensus,
- *   if demanded by <b>need_uptime</b> or <b>need_capacity</b>
- *   (unless it's a configured EntryNode);
- * - Allowed by our current ReachableORAddresses config option; and
- * - Currently thought to be reachable by us (unless <b>assume_reachable</b>
- *   is true).
- *
- * If the answer is no, set *<b>msg</b> to an explanation of why.
- */
-static INLINE const node_t *
-entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity,
-              int assume_reachable, const char **msg)
-{
-  const node_t *node;
-  const or_options_t *options = get_options();
-  tor_assert(msg);
-
-  if (e->path_bias_disabled) {
-    *msg = "path-biased";
-    return NULL;
-  }
-  if (e->bad_since) {
-    *msg = "bad";
-    return NULL;
-  }
-  /* no good if it's unreachable, unless assume_unreachable or can_retry. */
-  if (!assume_reachable && !e->can_retry &&
-      e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) {
-    *msg = "unreachable";
-    return NULL;
-  }
-  node = node_get_by_id(e->identity);
-  if (!node || !node_has_descriptor(node)) {
-    *msg = "no descriptor";
-    return NULL;
-  }
-  if (get_options()->UseBridges) {
-    if (node_get_purpose(node) != ROUTER_PURPOSE_BRIDGE) {
-      *msg = "not a bridge";
-      return NULL;
-    }
-    if (!node_is_a_configured_bridge(node)) {
-      *msg = "not a configured bridge";
-      return NULL;
-    }
-  } else { /* !get_options()->UseBridges */
-    if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) {
-      *msg = "not general-purpose";
-      return NULL;
-    }
-  }
-  if (routerset_contains_node(options->EntryNodes, node)) {
-    /* they asked for it, they get it */
-    need_uptime = need_capacity = 0;
-  }
-  if (node_is_unreliable(node, need_uptime, need_capacity, 0)) {
-    *msg = "not fast/stable";
-    return NULL;
-  }
-  if (!fascist_firewall_allows_node(node)) {
-    *msg = "unreachable by config";
-    return NULL;
-  }
-  return node;
-}
-
-/** Return the number of entry guards that we think are usable. */
-static int
-num_live_entry_guards(void)
-{
-  int n = 0;
-  const char *msg;
-  if (! entry_guards)
-    return 0;
-  SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
-    {
-      if (entry_is_live(entry, 0, 1, 0, &msg))
-        ++n;
-    });
-  return n;
-}
-
-/** If <b>digest</b> matches the identity of any node in the
- * entry_guards list, return that node. Else return NULL. */
-static entry_guard_t *
-entry_guard_get_by_id_digest(const char *digest)
-{
-  SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
-                    if (tor_memeq(digest, entry->identity, DIGEST_LEN))
-                      return entry;
-                   );
-  return NULL;
-}
-
-/** Dump a description of our list of entry guards to the log at level
- * <b>severity</b>. */
-static void
-log_entry_guards(int severity)
-{
-  smartlist_t *elements = smartlist_new();
-  char *s;
-
-  SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e)
-    {
-      const char *msg = NULL;
-      if (entry_is_live(e, 0, 1, 0, &msg))
-        smartlist_add_asprintf(elements, "%s [%s] (up %s)",
-                     e->nickname,
-                     hex_str(e->identity, DIGEST_LEN),
-                     e->made_contact ? "made-contact" : "never-contacted");
-      else
-        smartlist_add_asprintf(elements, "%s [%s] (%s, %s)",
-                     e->nickname,
-                     hex_str(e->identity, DIGEST_LEN),
-                     msg,
-                     e->made_contact ? "made-contact" : "never-contacted");
-    }
-  SMARTLIST_FOREACH_END(e);
-
-  s = smartlist_join_strings(elements, ",", 0, NULL);
-  SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
-  smartlist_free(elements);
-  log_fn(severity,LD_CIRC,"%s",s);
-  tor_free(s);
-}
-
-/** Called when one or more guards that we would previously have used for some
- * purpose are no longer in use because a higher-priority guard has become
- * usable again. */
-static void
-control_event_guard_deferred(void)
-{
-  /* XXXX We don't actually have a good way to figure out _how many_ entries
-   * are live for some purpose.  We need an entry_is_even_slightly_live()
-   * function for this to work right.  NumEntryGuards isn't reliable: if we
-   * need guards with weird properties, we can have more than that number
-   * live.
-   **/
-#if 0
-  int n = 0;
-  const char *msg;
-  const or_options_t *options = get_options();
-  if (!entry_guards)
-    return;
-  SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
-    {
-      if (entry_is_live(entry, 0, 1, 0, &msg)) {
-        if (n++ == options->NumEntryGuards) {
-          control_event_guard(entry->nickname, entry->identity, "DEFERRED");
-          return;
-        }
-      }
-    });
-#endif
-}
-
-/** Add a new (preferably stable and fast) router to our
- * entry_guards list. Return a pointer to the router if we succeed,
- * or NULL if we can't find any more suitable entries.
- *
- * If <b>chosen</b> is defined, use that one, and if it's not
- * already in our entry_guards list, put it at the *beginning*.
- * Else, put the one we pick at the end of the list. */
-static const node_t *
-add_an_entry_guard(const node_t *chosen, int reset_status, int prepend)
-{
-  const node_t *node;
-  entry_guard_t *entry;
-
-  if (chosen) {
-    node = chosen;
-    entry = entry_guard_get_by_id_digest(node->identity);
-    if (entry) {
-      if (reset_status) {
-        entry->bad_since = 0;
-        entry->can_retry = 1;
-      }
-      return NULL;
-    }
-  } else {
-    node = choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL, NULL);
-    if (!node)
-      return NULL;
-  }
-  entry = tor_malloc_zero(sizeof(entry_guard_t));
-  log_info(LD_CIRC, "Chose %s as new entry guard.",
-           node_describe(node));
-  strlcpy(entry->nickname, node_get_nickname(node), sizeof(entry->nickname));
-  memcpy(entry->identity, node->identity, DIGEST_LEN);
-  /* Choose expiry time smudged over the past month. The goal here
-   * is to a) spread out when Tor clients rotate their guards, so they
-   * don't all select them on the same day, and b) avoid leaving a
-   * precise timestamp in the state file about when we first picked
-   * this guard. For details, see the Jan 2010 or-dev thread. */
-  entry->chosen_on_date = time(NULL) - crypto_rand_int(3600*24*30);
-  entry->chosen_by_version = tor_strdup(VERSION);
-  if (prepend)
-    smartlist_insert(entry_guards, 0, entry);
-  else
-    smartlist_add(entry_guards, entry);
-  control_event_guard(entry->nickname, entry->identity, "NEW");
-  control_event_guard_deferred();
-  log_entry_guards(LOG_INFO);
-  return node;
-}
-
-/** If the use of entry guards is configured, choose more entry guards
- * until we have enough in the list. */
-static void
-pick_entry_guards(const or_options_t *options)
-{
-  int changed = 0;
-
-  tor_assert(entry_guards);
-
-  while (num_live_entry_guards() < options->NumEntryGuards) {
-    if (!add_an_entry_guard(NULL, 0, 0))
-      break;
-    changed = 1;
-  }
-  if (changed)
-    entry_guards_changed();
-}
-
-/** How long (in seconds) do we allow an entry guard to be nonfunctional,
- * unlisted, excluded, or otherwise nonusable before we give up on it? */
-#define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
-
-/** Release all storage held by <b>e</b>. */
-static void
-entry_guard_free(entry_guard_t *e)
-{
-  if (!e)
-    return;
-  tor_free(e->chosen_by_version);
-  tor_free(e);
-}
-
-/** Remove any entry guard which was selected by an unknown version of Tor,
- * or which was selected by a version of Tor that's known to select
- * entry guards badly, or which was selected more 2 months ago. */
-/* XXXX The "obsolete guards" and "chosen long ago guards" things should
- * probably be different functions. */
-static int
-remove_obsolete_entry_guards(time_t now)
-{
-  int changed = 0, i;
-
-  for (i = 0; i < smartlist_len(entry_guards); ++i) {
-    entry_guard_t *entry = smartlist_get(entry_guards, i);
-    const char *ver = entry->chosen_by_version;
-    const char *msg = NULL;
-    tor_version_t v;
-    int version_is_bad = 0, date_is_bad = 0;
-    if (!ver) {
-      msg = "does not say what version of Tor it was selected by";
-      version_is_bad = 1;
-    } else if (tor_version_parse(ver, &v)) {
-      msg = "does not seem to be from any recognized version of Tor";
-      version_is_bad = 1;
-    } else {
-      char *tor_ver = NULL;
-      tor_asprintf(&tor_ver, "Tor %s", ver);
-      if ((tor_version_as_new_as(tor_ver, "0.1.0.10-alpha") &&
-           !tor_version_as_new_as(tor_ver, "0.1.2.16-dev")) ||
-          (tor_version_as_new_as(tor_ver, "0.2.0.0-alpha") &&
-           !tor_version_as_new_as(tor_ver, "0.2.0.6-alpha")) ||
-          /* above are bug 440; below are bug 1217 */
-          (tor_version_as_new_as(tor_ver, "0.2.1.3-alpha") &&
-           !tor_version_as_new_as(tor_ver, "0.2.1.23")) ||
-          (tor_version_as_new_as(tor_ver, "0.2.2.0-alpha") &&
-           !tor_version_as_new_as(tor_ver, "0.2.2.7-alpha"))) {
-        msg = "was selected without regard for guard bandwidth";
-        version_is_bad = 1;
-      }
-      tor_free(tor_ver);
-    }
-    if (!version_is_bad && entry->chosen_on_date + 3600*24*60 < now) {
-      /* It's been 2 months since the date listed in our state file. */
-      msg = "was selected several months ago";
-      date_is_bad = 1;
-    }
-
-    if (version_is_bad || date_is_bad) { /* we need to drop it */
-      char dbuf[HEX_DIGEST_LEN+1];
-      tor_assert(msg);
-      base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
-      log_fn(version_is_bad ? LOG_NOTICE : LOG_INFO, LD_CIRC,
-             "Entry guard '%s' (%s) %s. (Version=%s.) Replacing it.",
-             entry->nickname, dbuf, msg, ver?escaped(ver):"none");
-      control_event_guard(entry->nickname, entry->identity, "DROPPED");
-      entry_guard_free(entry);
-      smartlist_del_keeporder(entry_guards, i--);
-      log_entry_guards(LOG_INFO);
-      changed = 1;
-    }
-  }
-
-  return changed ? 1 : 0;
-}
-
-/** Remove all entry guards that have been down or unlisted for so
- * long that we don't think they'll come up again. Return 1 if we
- * removed any, or 0 if we did nothing. */
-static int
-remove_dead_entry_guards(time_t now)
-{
-  char dbuf[HEX_DIGEST_LEN+1];
-  char tbuf[ISO_TIME_LEN+1];
-  int i;
-  int changed = 0;
-
-  for (i = 0; i < smartlist_len(entry_guards); ) {
-    entry_guard_t *entry = smartlist_get(entry_guards, i);
-    if (entry->bad_since &&
-        ! entry->path_bias_disabled &&
-        entry->bad_since + ENTRY_GUARD_REMOVE_AFTER < now) {
-
-      base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN);
-      format_local_iso_time(tbuf, entry->bad_since);
-      log_info(LD_CIRC, "Entry guard '%s' (%s) has been down or unlisted "
-               "since %s local time; removing.",
-               entry->nickname, dbuf, tbuf);
-      control_event_guard(entry->nickname, entry->identity, "DROPPED");
-      entry_guard_free(entry);
-      smartlist_del_keeporder(entry_guards, i);
-      log_entry_guards(LOG_INFO);
-      changed = 1;
-    } else
-      ++i;
-  }
-  return changed ? 1 : 0;
-}
-
-/** A new directory or router-status has arrived; update the down/listed
- * status of the entry guards.
- *
- * An entry is 'down' if the directory lists it as nonrunning.
- * An entry is 'unlisted' if the directory doesn't include it.
- *
- * Don't call this on startup; only on a fresh download. Otherwise we'll
- * think that things are unlisted.
- */
-void
-entry_guards_compute_status(const or_options_t *options, time_t now)
-{
-  int changed = 0;
-  digestmap_t *reasons;
-
-  if (! entry_guards)
-    return;
-
-  if (options->EntryNodes) /* reshuffle the entry guard list if needed */
-    entry_nodes_should_be_added();
-
-  reasons = digestmap_new();
-  SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry)
-    {
-      const node_t *r = node_get_by_id(entry->identity);
-      const char *reason = NULL;
-      if (entry_guard_set_status(entry, r, now, options, &reason))
-        changed = 1;
-
-      if (entry->bad_since)
-        tor_assert(reason);
-      if (reason)
-        digestmap_set(reasons, entry->identity, (char*)reason);
-    }
-  SMARTLIST_FOREACH_END(entry);
-
-  if (remove_dead_entry_guards(now))
-    changed = 1;
-  if (remove_obsolete_entry_guards(now))
-    changed = 1;
-
-  if (changed) {
-    SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) {
-      const char *reason = digestmap_get(reasons, entry->identity);
-      const char *live_msg = "";
-      const node_t *r = entry_is_live(entry, 0, 1, 0, &live_msg);
-      log_info(LD_CIRC, "Summary: Entry %s [%s] is %s, %s%s%s, and %s%s.",
-               entry->nickname,
-               hex_str(entry->identity, DIGEST_LEN),
-               entry->unreachable_since ? "unreachable" : "reachable",
-               entry->bad_since ? "unusable" : "usable",
-               reason ? ", ": "",
-               reason ? reason : "",
-               r ? "live" : "not live / ",
-               r ? "" : live_msg);
-    } SMARTLIST_FOREACH_END(entry);
-    log_info(LD_CIRC, "    (%d/%d entry guards are usable/new)",
-             num_live_entry_guards(), smartlist_len(entry_guards));
-    log_entry_guards(LOG_INFO);
-    entry_guards_changed();
-  }
-
-  digestmap_free(reasons, NULL);
-}
-
-/** Called when a connection to an OR with the identity digest <b>digest</b>
- * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0).
- * If the OR is an entry, change that entry's up/down status.
- * Return 0 normally, or -1 if we want to tear down the new connection.
- *
- * If <b>mark_relay_status</b>, also call router_set_status() on this
- * relay.
- *
- * XXX024 change succeeded and mark_relay_status into 'int flags'.
- */
-int
-entry_guard_register_connect_status(const char *digest, int succeeded,
-                                    int mark_relay_status, time_t now)
-{
-  int changed = 0;
-  int refuse_conn = 0;
-  int first_contact = 0;
-  entry_guard_t *entry = NULL;
-  int idx = -1;
-  char buf[HEX_DIGEST_LEN+1];
-
-  if (! entry_guards)
-    return 0;
-
-  SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
-    tor_assert(e);
-    if (tor_memeq(e->identity, digest, DIGEST_LEN)) {
-      entry = e;
-      idx = e_sl_idx;
-      break;
-    }
-  } SMARTLIST_FOREACH_END(e);
-
-  if (!entry)
-    return 0;
-
-  base16_encode(buf, sizeof(buf), entry->identity, DIGEST_LEN);
-
-  if (succeeded) {
-    if (entry->unreachable_since) {
-      log_info(LD_CIRC, "Entry guard '%s' (%s) is now reachable again. Good.",
-               entry->nickname, buf);
-      entry->can_retry = 0;
-      entry->unreachable_since = 0;
-      entry->last_attempted = now;
-      control_event_guard(entry->nickname, entry->identity, "UP");
-      changed = 1;
-    }
-    if (!entry->made_contact) {
-      entry->made_contact = 1;
-      first_contact = changed = 1;
-    }
-  } else { /* ! succeeded */
-    if (!entry->made_contact) {
-      /* We've never connected to this one. */
-      log_info(LD_CIRC,
-               "Connection to never-contacted entry guard '%s' (%s) failed. "
-               "Removing from the list. %d/%d entry guards usable/new.",
-               entry->nickname, buf,
-               num_live_entry_guards()-1, smartlist_len(entry_guards)-1);
-      control_event_guard(entry->nickname, entry->identity, "DROPPED");
-      entry_guard_free(entry);
-      smartlist_del_keeporder(entry_guards, idx);
-      log_entry_guards(LOG_INFO);
-      changed = 1;
-    } else if (!entry->unreachable_since) {
-      log_info(LD_CIRC, "Unable to connect to entry guard '%s' (%s). "
-               "Marking as unreachable.", entry->nickname, buf);
-      entry->unreachable_since = entry->last_attempted = now;
-      control_event_guard(entry->nickname, entry->identity, "DOWN");
-      changed = 1;
-      entry->can_retry = 0; /* We gave it an early chance; no good. */
-    } else {
-      char tbuf[ISO_TIME_LEN+1];
-      format_iso_time(tbuf, entry->unreachable_since);
-      log_debug(LD_CIRC, "Failed to connect to unreachable entry guard "
-                "'%s' (%s).  It has been unreachable since %s.",
-                entry->nickname, buf, tbuf);
-      entry->last_attempted = now;
-      entry->can_retry = 0; /* We gave it an early chance; no good. */
-    }
-  }
-
-  /* if the caller asked us to, also update the is_running flags for this
-   * relay */
-  if (mark_relay_status)
-    router_set_status(digest, succeeded);
-
-  if (first_contact) {
-    /* We've just added a new long-term entry guard. Perhaps the network just
-     * came back? We should give our earlier entries another try too,
-     * and close this connection so we don't use it before we've given
-     * the others a shot. */
-    SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
-        if (e == entry)
-          break;
-        if (e->made_contact) {
-          const char *msg;
-          const node_t *r = entry_is_live(e, 0, 1, 1, &msg);
-          if (r && e->unreachable_since) {
-            refuse_conn = 1;
-            e->can_retry = 1;
-          }
-        }
-    } SMARTLIST_FOREACH_END(e);
-    if (refuse_conn) {
-      log_info(LD_CIRC,
-               "Connected to new entry guard '%s' (%s). Marking earlier "
-               "entry guards up. %d/%d entry guards usable/new.",
-               entry->nickname, buf,
-               num_live_entry_guards(), smartlist_len(entry_guards));
-      log_entry_guards(LOG_INFO);
-      changed = 1;
-    }
-  }
-
-  if (changed)
-    entry_guards_changed();
-  return refuse_conn ? -1 : 0;
-}
-
-/** When we try to choose an entry guard, should we parse and add
- * config's EntryNodes first? */
-static int should_add_entry_nodes = 0;
-
-/** Called when the value of EntryNodes changes in our configuration. */
-void
-entry_nodes_should_be_added(void)
-{
-  log_info(LD_CIRC, "EntryNodes config option set. Putting configured "
-           "relays at the front of the entry guard list.");
-  should_add_entry_nodes = 1;
-}
-
-/** Adjust the entry guards list so that it only contains entries from
- * EntryNodes, adding new entries from EntryNodes to the list as needed. */
-static void
-entry_guards_set_from_config(const or_options_t *options)
-{
-  smartlist_t *entry_nodes, *worse_entry_nodes, *entry_fps;
-  smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list;
-  tor_assert(entry_guards);
-
-  should_add_entry_nodes = 0;
-
-  if (!options->EntryNodes) {
-    /* It's possible that a controller set EntryNodes, thus making
-     * should_add_entry_nodes set, then cleared it again, all before the
-     * call to choose_random_entry() that triggered us. If so, just return.
-     */
-    return;
-  }
-
-  {
-    char *string = routerset_to_string(options->EntryNodes);
-    log_info(LD_CIRC,"Adding configured EntryNodes '%s'.", string);
-    tor_free(string);
-  }
-
-  entry_nodes = smartlist_new();
-  worse_entry_nodes = smartlist_new();
-  entry_fps = smartlist_new();
-  old_entry_guards_on_list = smartlist_new();
-  old_entry_guards_not_on_list = smartlist_new();
-
-  /* Split entry guards into those on the list and those not. */
-
-  routerset_get_all_nodes(entry_nodes, options->EntryNodes,
-                          options->ExcludeNodes, 0);
-  SMARTLIST_FOREACH(entry_nodes, const node_t *,node,
-                    smartlist_add(entry_fps, (void*)node->identity));
-
-  SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, {
-    if (smartlist_digest_isin(entry_fps, e->identity))
-      smartlist_add(old_entry_guards_on_list, e);
-    else
-      smartlist_add(old_entry_guards_not_on_list, e);
-  });
-
-  /* Remove all currently configured guard nodes, excluded nodes, unreachable
-   * nodes, or non-Guard nodes from entry_nodes. */
-  SMARTLIST_FOREACH_BEGIN(entry_nodes, const node_t *, node) {
-    if (entry_guard_get_by_id_digest(node->identity)) {
-      SMARTLIST_DEL_CURRENT(entry_nodes, node);
-      continue;
-    } else if (routerset_contains_node(options->ExcludeNodes, node)) {
-      SMARTLIST_DEL_CURRENT(entry_nodes, node);
-      continue;
-    } else if (!fascist_firewall_allows_node(node)) {
-      SMARTLIST_DEL_CURRENT(entry_nodes, node);
-      continue;
-    } else if (! node->is_possible_guard) {
-      smartlist_add(worse_entry_nodes, (node_t*)node);
-      SMARTLIST_DEL_CURRENT(entry_nodes, node);
-    }
-  } SMARTLIST_FOREACH_END(node);
-
-  /* Now build the new entry_guards list. */
-  smartlist_clear(entry_guards);
-  /* First, the previously configured guards that are in EntryNodes. */
-  smartlist_add_all(entry_guards, old_entry_guards_on_list);
-  /* Next, scramble the rest of EntryNodes, putting the guards first. */
-  smartlist_shuffle(entry_nodes);
-  smartlist_shuffle(worse_entry_nodes);
-  smartlist_add_all(entry_nodes, worse_entry_nodes);
-
-  /* Next, the rest of EntryNodes */
-  SMARTLIST_FOREACH_BEGIN(entry_nodes, const node_t *, node) {
-    add_an_entry_guard(node, 0, 0);
-    if (smartlist_len(entry_guards) > options->NumEntryGuards * 10)
-      break;
-  } SMARTLIST_FOREACH_END(node);
-  log_notice(LD_GENERAL, "%d entries in guards", smartlist_len(entry_guards));
-  /* Finally, free the remaining previously configured guards that are not in
-   * EntryNodes. */
-  SMARTLIST_FOREACH(old_entry_guards_not_on_list, entry_guard_t *, e,
-                    entry_guard_free(e));
-
-  smartlist_free(entry_nodes);
-  smartlist_free(worse_entry_nodes);
-  smartlist_free(entry_fps);
-  smartlist_free(old_entry_guards_on_list);
-  smartlist_free(old_entry_guards_not_on_list);
-  entry_guards_changed();
-}
-
-/** Return 0 if we're fine adding arbitrary routers out of the
- * directory to our entry guard list, or return 1 if we have a
- * list already and we must stick to it.
- */
-int
-entry_list_is_constrained(const or_options_t *options)
-{
-  if (options->EntryNodes)
-    return 1;
-  if (options->UseBridges)
-    return 1;
-  return 0;
-}
-
-/** Pick a live (up and listed) entry guard from entry_guards. If
- * <b>state</b> is non-NULL, this is for a specific circuit --
- * make sure not to pick this circuit's exit or any node in the
- * exit's family. If <b>state</b> is NULL, we're looking for a random
- * guard (likely a bridge). */
-const node_t *
-choose_random_entry(cpath_build_state_t *state)
-{
-  const or_options_t *options = get_options();
-  smartlist_t *live_entry_guards = smartlist_new();
-  smartlist_t *exit_family = smartlist_new();
-  const node_t *chosen_exit =
-    state?build_state_get_exit_node(state) : NULL;
-  const node_t *node = NULL;
-  int need_uptime = state ? state->need_uptime : 0;
-  int need_capacity = state ? state->need_capacity : 0;
-  int preferred_min, consider_exit_family = 0;
-
-  if (chosen_exit) {
-    nodelist_add_node_and_family(exit_family, chosen_exit);
-    consider_exit_family = 1;
-  }
-
-  if (!entry_guards)
-    entry_guards = smartlist_new();
-
-  if (should_add_entry_nodes)
-    entry_guards_set_from_config(options);
-
-  if (!entry_list_is_constrained(options) &&
-      smartlist_len(entry_guards) < options->NumEntryGuards)
-    pick_entry_guards(options);
-
- retry:
-  smartlist_clear(live_entry_guards);
-  SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) {
-      const char *msg;
-      node = entry_is_live(entry, need_uptime, need_capacity, 0, &msg);
-      if (!node)
-        continue; /* down, no point */
-      if (node == chosen_exit)
-        continue; /* don't pick the same node for entry and exit */
-      if (consider_exit_family && smartlist_isin(exit_family, node))
-        continue; /* avoid relays that are family members of our exit */
-#if 0 /* since EntryNodes is always strict now, this clause is moot */
-      if (options->EntryNodes &&
-          !routerset_contains_node(options->EntryNodes, node)) {
-        /* We've come to the end of our preferred entry nodes. */
-        if (smartlist_len(live_entry_guards))
-          goto choose_and_finish; /* only choose from the ones we like */
-        if (options->StrictNodes) {
-          /* in theory this case should never happen, since
-           * entry_guards_set_from_config() drops unwanted relays */
-          tor_fragile_assert();
-        } else {
-          log_info(LD_CIRC,
-                   "No relays from EntryNodes available. Using others.");
-        }
-      }
-#endif
-      smartlist_add(live_entry_guards, (void*)node);
-      if (!entry->made_contact) {
-        /* Always start with the first not-yet-contacted entry
-         * guard. Otherwise we might add several new ones, pick
-         * the second new one, and now we've expanded our entry
-         * guard list without needing to. */
-        goto choose_and_finish;
-      }
-      if (smartlist_len(live_entry_guards) >= options->NumEntryGuards)
-        goto choose_and_finish; /* we have enough */
-  } SMARTLIST_FOREACH_END(entry);
-
-  if (entry_list_is_constrained(options)) {
-    /* If we prefer the entry nodes we've got, and we have at least
-     * one choice, that's great. Use it. */
-    preferred_min = 1;
-  } else {
-    /* Try to have at least 2 choices available. This way we don't
-     * get stuck with a single live-but-crummy entry and just keep
-     * using him.
-     * (We might get 2 live-but-crummy entry guards, but so be it.) */
-    preferred_min = 2;
-  }
-
-  if (smartlist_len(live_entry_guards) < preferred_min) {
-    if (!entry_list_is_constrained(options)) {
-      /* still no? try adding a new entry then */
-      /* XXX if guard doesn't imply fast and stable, then we need
-       * to tell add_an_entry_guard below what we want, or it might
-       * be a long time til we get it. -RD */
-      node = add_an_entry_guard(NULL, 0, 0);
-      if (node) {
-        entry_guards_changed();
-        /* XXX we start over here in case the new node we added shares
-         * a family with our exit node. There's a chance that we'll just
-         * load up on entry guards here, if the network we're using is
-         * one big family. Perhaps we should teach add_an_entry_guard()
-         * to understand nodes-to-avoid-if-possible? -RD */
-        goto retry;
-      }
-    }
-    if (!node && need_uptime) {
-      need_uptime = 0; /* try without that requirement */
-      goto retry;
-    }
-    if (!node && need_capacity) {
-      /* still no? last attempt, try without requiring capacity */
-      need_capacity = 0;
-      goto retry;
-    }
-#if 0
-    /* Removing this retry logic: if we only allow one exit, and it is in the
-       same family as all our entries, then we are just plain not going to win
-       here. */
-    if (!node && entry_list_is_constrained(options) && consider_exit_family) {
-      /* still no? if we're using bridges or have strictentrynodes
-       * set, and our chosen exit is in the same family as all our
-       * bridges/entry guards, then be flexible about families. */
-      consider_exit_family = 0;
-      goto retry;
-    }
-#endif
-    /* live_entry_guards may be empty below. Oh well, we tried. */
-  }
-
- choose_and_finish:
-  if (entry_list_is_constrained(options)) {
-    /* We need to weight by bandwidth, because our bridges or entryguards
-     * were not already selected proportional to their bandwidth. */
-    node = node_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD);
-  } else {
-    /* We choose uniformly at random here, because choose_good_entry_server()
-     * already weights its choices by bandwidth, so we don't want to
-     * *double*-weight our guard selection. */
-    node = smartlist_choose(live_entry_guards);
-  }
-  smartlist_free(live_entry_guards);
-  smartlist_free(exit_family);
-  return node;
-}
-
-/** Parse <b>state</b> and learn about the entry guards it describes.
- * If <b>set</b> is true, and there are no errors, replace the global
- * entry_list with what we find.
- * On success, return 0. On failure, alloc into *<b>msg</b> a string
- * describing the error, and return -1.
- */
-int
-entry_guards_parse_state(or_state_t *state, int set, char **msg)
-{
-  entry_guard_t *node = NULL;
-  smartlist_t *new_entry_guards = smartlist_new();
-  config_line_t *line;
-  time_t now = time(NULL);
-  const char *state_version = state->TorVersion;
-  digestmap_t *added_by = digestmap_new();
-
-  *msg = NULL;
-  for (line = state->EntryGuards; line; line = line->next) {
-    if (!strcasecmp(line->key, "EntryGuard")) {
-      smartlist_t *args = smartlist_new();
-      node = tor_malloc_zero(sizeof(entry_guard_t));
-      /* all entry guards on disk have been contacted */
-      node->made_contact = 1;
-      smartlist_add(new_entry_guards, node);
-      smartlist_split_string(args, line->value, " ",
-                             SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
-      if (smartlist_len(args)<2) {
-        *msg = tor_strdup("Unable to parse entry nodes: "
-                          "Too few arguments to EntryGuard");
-      } else if (!is_legal_nickname(smartlist_get(args,0))) {
-        *msg = tor_strdup("Unable to parse entry nodes: "
-                          "Bad nickname for EntryGuard");
-      } else {
-        strlcpy(node->nickname, smartlist_get(args,0), MAX_NICKNAME_LEN+1);
-        if (base16_decode(node->identity, DIGEST_LEN, smartlist_get(args,1),
-                          strlen(smartlist_get(args,1)))<0) {
-          *msg = tor_strdup("Unable to parse entry nodes: "
-                            "Bad hex digest for EntryGuard");
-        }
-      }
-      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
-      smartlist_free(args);
-      if (*msg)
-        break;
-    } else if (!strcasecmp(line->key, "EntryGuardDownSince") ||
-               !strcasecmp(line->key, "EntryGuardUnlistedSince")) {
-      time_t when;
-      time_t last_try = 0;
-      if (!node) {
-        *msg = tor_strdup("Unable to parse entry nodes: "
-               "EntryGuardDownSince/UnlistedSince without EntryGuard");
-        break;
-      }
-      if (parse_iso_time(line->value, &when)<0) {
-        *msg = tor_strdup("Unable to parse entry nodes: "
-                          "Bad time in EntryGuardDownSince/UnlistedSince");
-        break;
-      }
-      if (when > now) {
-        /* It's a bad idea to believe info in the future: you can wind
-         * up with timeouts that aren't allowed to happen for years. */
-        continue;
-      }
-      if (strlen(line->value) >= ISO_TIME_LEN+ISO_TIME_LEN+1) {
-        /* ignore failure */
-        (void) parse_iso_time(line->value+ISO_TIME_LEN+1, &last_try);
-      }
-      if (!strcasecmp(line->key, "EntryGuardDownSince")) {
-        node->unreachable_since = when;
-        node->last_attempted = last_try;
-      } else {
-        node->bad_since = when;
-      }
-    } else if (!strcasecmp(line->key, "EntryGuardAddedBy")) {
-      char d[DIGEST_LEN];
-      /* format is digest version date */
-      if (strlen(line->value) < HEX_DIGEST_LEN+1+1+1+ISO_TIME_LEN) {
-        log_warn(LD_BUG, "EntryGuardAddedBy line is not long enough.");
-        continue;
-      }
-      if (base16_decode(d, sizeof(d), line->value, HEX_DIGEST_LEN)<0 ||
-          line->value[HEX_DIGEST_LEN] != ' ') {
-        log_warn(LD_BUG, "EntryGuardAddedBy line %s does not begin with "
-                 "hex digest", escaped(line->value));
-        continue;
-      }
-      digestmap_set(added_by, d, tor_strdup(line->value+HEX_DIGEST_LEN+1));
-    } else if (!strcasecmp(line->key, "EntryGuardPathBias")) {
-      const or_options_t *options = get_options();
-      unsigned hop_cnt, success_cnt;
-
-      if (!node) {
-        *msg = tor_strdup("Unable to parse entry nodes: "
-               "EntryGuardPathBias without EntryGuard");
-        break;
-      }
-
-      if (tor_sscanf(line->value, "%u %u", &success_cnt, &hop_cnt) != 2) {
-        log_warn(LD_GENERAL, "Unable to parse guard path bias info: "
-                 "Misformated EntryGuardPathBias %s", escaped(line->value));
-        continue;
-      }
-
-      node->first_hops = hop_cnt;
-      node->circuit_successes = success_cnt;
-      log_info(LD_GENERAL, "Read %u/%u path bias for node %s",
-               node->circuit_successes, node->first_hops, node->nickname);
-      /* Note: We rely on the < comparison here to allow us to set a 0
-       * rate and disable the feature entirely. If refactoring, don't
-       * change to <= */
-      if (node->circuit_successes/((double)node->first_hops)
-          < pathbias_get_disable_rate(options)) {
-        node->path_bias_disabled = 1;
-        log_info(LD_GENERAL,
-                 "Path bias is too high (%u/%u); disabling node %s",
-                 node->circuit_successes, node->first_hops, node->nickname);
-      }
-
-    } else {
-      log_warn(LD_BUG, "Unexpected key %s", line->key);
-    }
-  }
-
-  SMARTLIST_FOREACH_BEGIN(new_entry_guards, entry_guard_t *, e) {
-     char *sp;
-     char *val = digestmap_get(added_by, e->identity);
-     if (val && (sp = strchr(val, ' '))) {
-       time_t when;
-       *sp++ = '\0';
-       if (parse_iso_time(sp, &when)<0) {
-         log_warn(LD_BUG, "Can't read time %s in EntryGuardAddedBy", sp);
-       } else {
-         e->chosen_by_version = tor_strdup(val);
-         e->chosen_on_date = when;
-       }
-     } else {
-       if (state_version) {
-         e->chosen_by_version = tor_strdup(state_version);
-         e->chosen_on_date = time(NULL) - crypto_rand_int(3600*24*30);
-       }
-     }
-     if (e->path_bias_disabled && !e->bad_since)
-       e->bad_since = time(NULL);
-    }
-  SMARTLIST_FOREACH_END(e);
-
-  if (*msg || !set) {
-    SMARTLIST_FOREACH(new_entry_guards, entry_guard_t *, e,
-                      entry_guard_free(e));
-    smartlist_free(new_entry_guards);
-  } else { /* !err && set */
-    if (entry_guards) {
-      SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
-                        entry_guard_free(e));
-      smartlist_free(entry_guards);
-    }
-    entry_guards = new_entry_guards;
-    entry_guards_dirty = 0;
-    /* XXX024 hand new_entry_guards to this func, and move it up a
-     * few lines, so we don't have to re-dirty it */
-    if (remove_obsolete_entry_guards(now))
-      entry_guards_dirty = 1;
-  }
-  digestmap_free(added_by, tor_free_);
-  return *msg ? -1 : 0;
-}
-
-/** Our list of entry guards has changed, or some element of one
- * of our entry guards has changed. Write the changes to disk within
- * the next few minutes.
- */
-static void
-entry_guards_changed(void)
-{
-  time_t when;
-  entry_guards_dirty = 1;
-
-  /* or_state_save() will call entry_guards_update_state(). */
-  when = get_options()->AvoidDiskWrites ? time(NULL) + 3600 : time(NULL)+600;
-  or_state_mark_dirty(get_or_state(), when);
-}
-
-/** If the entry guard info has not changed, do nothing and return.
- * Otherwise, free the EntryGuards piece of <b>state</b> and create
- * a new one out of the global entry_guards list, and then mark
- * <b>state</b> dirty so it will get saved to disk.
- */
-void
-entry_guards_update_state(or_state_t *state)
-{
-  config_line_t **next, *line;
-  if (! entry_guards_dirty)
-    return;
-
-  config_free_lines(state->EntryGuards);
-  next = &state->EntryGuards;
-  *next = NULL;
-  if (!entry_guards)
-    entry_guards = smartlist_new();
-  SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
-      char dbuf[HEX_DIGEST_LEN+1];
-      if (!e->made_contact)
-        continue; /* don't write this one to disk */
-      *next = line = tor_malloc_zero(sizeof(config_line_t));
-      line->key = tor_strdup("EntryGuard");
-      base16_encode(dbuf, sizeof(dbuf), e->identity, DIGEST_LEN);
-      tor_asprintf(&line->value, "%s %s", e->nickname, dbuf);
-      next = &(line->next);
-      if (e->unreachable_since) {
-        *next = line = tor_malloc_zero(sizeof(config_line_t));
-        line->key = tor_strdup("EntryGuardDownSince");
-        line->value = tor_malloc(ISO_TIME_LEN+1+ISO_TIME_LEN+1);
-        format_iso_time(line->value, e->unreachable_since);
-        if (e->last_attempted) {
-          line->value[ISO_TIME_LEN] = ' ';
-          format_iso_time(line->value+ISO_TIME_LEN+1, e->last_attempted);
-        }
-        next = &(line->next);
-      }
-      if (e->bad_since) {
-        *next = line = tor_malloc_zero(sizeof(config_line_t));
-        line->key = tor_strdup("EntryGuardUnlistedSince");
-        line->value = tor_malloc(ISO_TIME_LEN+1);
-        format_iso_time(line->value, e->bad_since);
-        next = &(line->next);
-      }
-      if (e->chosen_on_date && e->chosen_by_version &&
-          !strchr(e->chosen_by_version, ' ')) {
-        char d[HEX_DIGEST_LEN+1];
-        char t[ISO_TIME_LEN+1];
-        *next = line = tor_malloc_zero(sizeof(config_line_t));
-        line->key = tor_strdup("EntryGuardAddedBy");
-        base16_encode(d, sizeof(d), e->identity, DIGEST_LEN);
-        format_iso_time(t, e->chosen_on_date);
-        tor_asprintf(&line->value, "%s %s %s",
-                     d, e->chosen_by_version, t);
-        next = &(line->next);
-      }
-      if (e->first_hops) {
-        *next = line = tor_malloc_zero(sizeof(config_line_t));
-        line->key = tor_strdup("EntryGuardPathBias");
-        tor_asprintf(&line->value, "%u %u",
-                     e->circuit_successes, e->first_hops);
-        next = &(line->next);
-      }
-
-  } SMARTLIST_FOREACH_END(e);
-  if (!get_options()->AvoidDiskWrites)
-    or_state_mark_dirty(get_or_state(), 0);
-  entry_guards_dirty = 0;
-}
-
-/** If <b>question</b> is the string "entry-guards", then dump
- * to *<b>answer</b> a newly allocated string describing all of
- * the nodes in the global entry_guards list. See control-spec.txt
- * for details.
- * For backward compatibility, we also handle the string "helper-nodes".
- * */
-int
-getinfo_helper_entry_guards(control_connection_t *conn,
-                            const char *question, char **answer,
-                            const char **errmsg)
-{
-  (void) conn;
-  (void) errmsg;
-
-  if (!strcmp(question,"entry-guards") ||
-      !strcmp(question,"helper-nodes")) {
-    smartlist_t *sl = smartlist_new();
-    char tbuf[ISO_TIME_LEN+1];
-    char nbuf[MAX_VERBOSE_NICKNAME_LEN+1];
-    if (!entry_guards)
-      entry_guards = smartlist_new();
-    SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
-        const char *status = NULL;
-        time_t when = 0;
-        const node_t *node;
-
-        if (!e->made_contact) {
-          status = "never-connected";
-        } else if (e->bad_since) {
-          when = e->bad_since;
-          status = "unusable";
-        } else {
-          status = "up";
-        }
-
-        node = node_get_by_id(e->identity);
-        if (node) {
-          node_get_verbose_nickname(node, nbuf);
-        } else {
-          nbuf[0] = '$';
-          base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN);
-          /* e->nickname field is not very reliable if we don't know about
-           * this router any longer; don't include it. */
-        }
-
-        if (when) {
-          format_iso_time(tbuf, when);
-          smartlist_add_asprintf(sl, "%s %s %s\n", nbuf, status, tbuf);
-        } else {
-          smartlist_add_asprintf(sl, "%s %s\n", nbuf, status);
-        }
-    } SMARTLIST_FOREACH_END(e);
-    *answer = smartlist_join_strings(sl, "", 0, NULL);
-    SMARTLIST_FOREACH(sl, char *, c, tor_free(c));
-    smartlist_free(sl);
-  }
-  return 0;
-}
-
-/** A list of configured bridges. Whenever we actually get a descriptor
- * for one, we add it as an entry guard.  Note that the order of bridges
- * in this list does not necessarily correspond to the order of bridges
- * in the torrc. */
-static smartlist_t *bridge_list = NULL;
-
-/** Mark every entry of the bridge list to be removed on our next call to
- * sweep_bridge_list unless it has first been un-marked. */
-void
-mark_bridge_list(void)
-{
-  if (!bridge_list)
-    bridge_list = smartlist_new();
-  SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b,
-                    b->marked_for_removal = 1);
-}
-
-/** Remove every entry of the bridge list that was marked with
- * mark_bridge_list if it has not subsequently been un-marked. */
-void
-sweep_bridge_list(void)
-{
-  if (!bridge_list)
-    bridge_list = smartlist_new();
-  SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, b) {
-    if (b->marked_for_removal) {
-      SMARTLIST_DEL_CURRENT(bridge_list, b);
-      bridge_free(b);
-    }
-  } SMARTLIST_FOREACH_END(b);
-}
-
-/** Initialize the bridge list to empty, creating it if needed. */
-static void
-clear_bridge_list(void)
-{
-  if (!bridge_list)
-    bridge_list = smartlist_new();
-  SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b, bridge_free(b));
-  smartlist_clear(bridge_list);
-}
-
-/** Free the bridge <b>bridge</b>. */
-static void
-bridge_free(bridge_info_t *bridge)
-{
-  if (!bridge)
-    return;
-
-  tor_free(bridge->transport_name);
-  tor_free(bridge);
-}
-
-/** If we have a bridge configured whose digest matches <b>digest</b>, or a
- * bridge with no known digest whose address matches any of the
- * tor_addr_port_t's in <b>orports</b>, return that bridge.  Else return
- * NULL. */
-static bridge_info_t *
-get_configured_bridge_by_orports_digest(const char *digest,
-                                        const smartlist_t *orports)
-{
-  if (!bridge_list)
-    return NULL;
-  SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
-    {
-      if (tor_digest_is_zero(bridge->identity)) {
-        SMARTLIST_FOREACH_BEGIN(orports, tor_addr_port_t *, ap)
-          {
-            if (tor_addr_compare(&bridge->addr, &ap->addr, CMP_EXACT) == 0 &&
-                bridge->port == ap->port)
-              return bridge;
-          }
-        SMARTLIST_FOREACH_END(ap);
-      }
-      if (digest && tor_memeq(bridge->identity, digest, DIGEST_LEN))
-        return bridge;
-    }
-  SMARTLIST_FOREACH_END(bridge);
-  return NULL;
-}
-
-/** If we have a bridge configured whose digest matches <b>digest</b>, or a
- * bridge with no known digest whose address matches <b>addr</b>:<b>/port</b>,
- * return that bridge.  Else return NULL. */
-static bridge_info_t *
-get_configured_bridge_by_addr_port_digest(const tor_addr_t *addr,
-                                          uint16_t port,
-                                          const char *digest)
-{
-  if (!bridge_list)
-    return NULL;
-  SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
-    {
-      if (tor_digest_is_zero(bridge->identity) &&
-          !tor_addr_compare(&bridge->addr, addr, CMP_EXACT) &&
-          bridge->port == port)
-        return bridge;
-      if (digest && tor_memeq(bridge->identity, digest, DIGEST_LEN))
-        return bridge;
-    }
-  SMARTLIST_FOREACH_END(bridge);
-  return NULL;
-}
-
-/** Wrapper around get_configured_bridge_by_addr_port_digest() to look
- * it up via router descriptor <b>ri</b>. */
-static bridge_info_t *
-get_configured_bridge_by_routerinfo(const routerinfo_t *ri)
-{
-  bridge_info_t *bi = NULL;
-  smartlist_t *orports = router_get_all_orports(ri);
-  bi = get_configured_bridge_by_orports_digest(ri->cache_info.identity_digest,
-                                               orports);
-  SMARTLIST_FOREACH(orports, tor_addr_port_t *, p, tor_free(p));
-  smartlist_free(orports);
-  return bi;
-}
-
-/** Return 1 if <b>ri</b> is one of our known bridges, else 0. */
-int
-routerinfo_is_a_configured_bridge(const routerinfo_t *ri)
-{
-  return get_configured_bridge_by_routerinfo(ri) ? 1 : 0;
-}
-
-/** Return 1 if <b>node</b> is one of our configured bridges, else 0. */
-int
-node_is_a_configured_bridge(const node_t *node)
-{
-  int retval = 0;
-  smartlist_t *orports = node_get_all_orports(node);
-  retval = get_configured_bridge_by_orports_digest(node->identity,
-                                                   orports) != NULL;
-  SMARTLIST_FOREACH(orports, tor_addr_port_t *, p, tor_free(p));
-  smartlist_free(orports);
-  return retval;
-}
-
-/** We made a connection to a router at <b>addr</b>:<b>port</b>
- * without knowing its digest. Its digest turned out to be <b>digest</b>.
- * If it was a bridge, and we still don't know its digest, record it.
- */
-void
-learned_router_identity(const tor_addr_t *addr, uint16_t port,
-                        const char *digest)
-{
-  bridge_info_t *bridge =
-    get_configured_bridge_by_addr_port_digest(addr, port, digest);
-  if (bridge && tor_digest_is_zero(bridge->identity)) {
-    memcpy(bridge->identity, digest, DIGEST_LEN);
-    log_notice(LD_DIR, "Learned fingerprint %s for bridge %s",
-               hex_str(digest, DIGEST_LEN), fmt_addrport(addr, port));
-  }
-}
-
-/** Return true if <b>bridge</b> has the same identity digest as
- *  <b>digest</b>. If <b>digest</b> is NULL, it matches
- *  bridges with unspecified identity digests. */
-static int
-bridge_has_digest(const bridge_info_t *bridge, const char *digest)
-{
-  if (digest)
-    return tor_memeq(digest, bridge->identity, DIGEST_LEN);
-  else
-    return tor_digest_is_zero(bridge->identity);
-}
-
-/** We are about to add a new bridge at <b>addr</b>:<b>port</b>, with optional
- * <b>digest</b> and <b>transport_name</b>. Mark for removal any previously
- * existing bridge with the same address and port, and warn the user as
- * appropriate.
- */
-static void
-bridge_resolve_conflicts(const tor_addr_t *addr, uint16_t port,
-                         const char *digest, const char *transport_name)
-{
-  /* Iterate the already-registered bridge list:
-
-     If you find a bridge with the same adress and port, mark it for
-     removal. It doesn't make sense to have two active bridges with
-     the same IP:PORT. If the bridge in question has a different
-     digest or transport than <b>digest</b>/<b>transport_name</b>,
-     it's probably a misconfiguration and we should warn the user.
-  */
-  SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge) {
-    if (bridge->marked_for_removal)
-      continue;
-
-    if (tor_addr_eq(&bridge->addr, addr) && (bridge->port == port)) {
-
-      bridge->marked_for_removal = 1;
-
-      if (!bridge_has_digest(bridge, digest) ||
-          strcmp_opt(bridge->transport_name, transport_name)) {
-        /* warn the user */
-        char *bridge_description_new, *bridge_description_old;
-        tor_asprintf(&bridge_description_new, "%s:%s:%s",
-                     fmt_addrport(addr, port),
-                     digest ? hex_str(digest, DIGEST_LEN) : "",
-                     transport_name ? transport_name : "");
-        tor_asprintf(&bridge_description_old, "%s:%s:%s",
-                     fmt_addrport(&bridge->addr, bridge->port),
-                     tor_digest_is_zero(bridge->identity) ?
-                     "" : hex_str(bridge->identity,DIGEST_LEN),
-                     bridge->transport_name ? bridge->transport_name : "");
-
-        log_warn(LD_GENERAL,"Tried to add bridge '%s', but we found a conflict"
-                 " with the already registered bridge '%s'. We will discard"
-                 " the old bridge and keep '%s'. If this is not what you"
-                 " wanted, please change your configuration file accordingly.",
-                 bridge_description_new, bridge_description_old,
-                 bridge_description_new);
-
-        tor_free(bridge_description_new);
-        tor_free(bridge_description_old);
-      }
-    }
-  } SMARTLIST_FOREACH_END(bridge);
-}
-
-/** Remember a new bridge at <b>addr</b>:<b>port</b>. If <b>digest</b>
- * is set, it tells us the identity key too.  If we already had the
- * bridge in our list, unmark it, and don't actually add anything new.
- * If <b>transport_name</b> is non-NULL - the bridge is associated with a
- * pluggable transport - we assign the transport to the bridge. */
-void
-bridge_add_from_config(const tor_addr_t *addr, uint16_t port,
-                       const char *digest, const char *transport_name)
-{
-  bridge_info_t *b;
-
-  bridge_resolve_conflicts(addr, port, digest, transport_name);
-
-  b = tor_malloc_zero(sizeof(bridge_info_t));
-  tor_addr_copy(&b->addr, addr);
-  b->port = port;
-  if (digest)
-    memcpy(b->identity, digest, DIGEST_LEN);
-  if (transport_name)
-    b->transport_name = tor_strdup(transport_name);
-  b->fetch_status.schedule = DL_SCHED_BRIDGE;
-  if (!bridge_list)
-    bridge_list = smartlist_new();
-
-  smartlist_add(bridge_list, b);
-}
-
-/** Return true iff <b>routerset</b> contains the bridge <b>bridge</b>. */
-static int
-routerset_contains_bridge(const routerset_t *routerset,
-                          const bridge_info_t *bridge)
-{
-  int result;
-  extend_info_t *extinfo;
-  tor_assert(bridge);
-  if (!routerset)
-    return 0;
-
-  extinfo = extend_info_new(
-         NULL, bridge->identity, NULL, &bridge->addr, bridge->port);
-  result = routerset_contains_extendinfo(routerset, extinfo);
-  extend_info_free(extinfo);
-  return result;
-}
-
-/** If <b>digest</b> is one of our known bridges, return it. */
-static bridge_info_t *
-find_bridge_by_digest(const char *digest)
-{
-  SMARTLIST_FOREACH(bridge_list, bridge_info_t *, bridge,
-    {
-      if (tor_memeq(bridge->identity, digest, DIGEST_LEN))
-        return bridge;
-    });
-  return NULL;
-}
-
-/* DOCDOC find_transport_name_by_bridge_addrport */
-const char *
-find_transport_name_by_bridge_addrport(const tor_addr_t *addr, uint16_t port)
-{
-  if (!bridge_list)
-    return NULL;
-
-  SMARTLIST_FOREACH_BEGIN(bridge_list, const bridge_info_t *, bridge) {
-    if (tor_addr_eq(&bridge->addr, addr) &&
-        (bridge->port == port))
-      return bridge->transport_name;
-  } SMARTLIST_FOREACH_END(bridge);
-
-  return NULL;
-}
-
-/** If <b>addr</b> and <b>port</b> match the address and port of a
- * bridge of ours that uses pluggable transports, place its transport
- * in <b>transport</b>.
- *
- * Return 0 on success (found a transport, or found a bridge with no
- * transport, or found no bridge); return -1 if we should be using a
- * transport, but the transport could not be found.
- */
-int
-find_transport_by_bridge_addrport(const tor_addr_t *addr, uint16_t port,
-                                  const transport_t **transport)
-{
-  *transport = NULL;
-  if (!bridge_list)
-    return 0;
-
-  SMARTLIST_FOREACH_BEGIN(bridge_list, const bridge_info_t *, bridge) {
-    if (tor_addr_eq(&bridge->addr, addr) &&
-        (bridge->port == port)) { /* bridge matched */
-      if (bridge->transport_name) { /* it also uses pluggable transports */
-        *transport = transport_get_by_name(bridge->transport_name);
-        if (*transport == NULL) { /* it uses pluggable transports, but
-                                     the transport could not be found! */
-          return -1;
-        }
-        return 0;
-      } else { /* bridge matched, but it doesn't use transports. */
-        break;
-      }
-    }
-  } SMARTLIST_FOREACH_END(bridge);
-
-  *transport = NULL;
-  return 0;
-}
-
-/** We need to ask <b>bridge</b> for its server descriptor. */
-static void
-launch_direct_bridge_descriptor_fetch(bridge_info_t *bridge)
-{
-  char *address;
-  const or_options_t *options = get_options();
-
-  if (connection_get_by_type_addr_port_purpose(
-      CONN_TYPE_DIR, &bridge->addr, bridge->port,
-      DIR_PURPOSE_FETCH_SERVERDESC))
-    return; /* it's already on the way */
-
-  if (routerset_contains_bridge(options->ExcludeNodes, bridge)) {
-    download_status_mark_impossible(&bridge->fetch_status);
-    log_warn(LD_APP, "Not using bridge at %s: it is in ExcludeNodes.",
-             safe_str_client(fmt_and_decorate_addr(&bridge->addr)));
-    return;
-  }
-
-  address = tor_dup_addr(&bridge->addr);
-
-  directory_initiate_command(address, &bridge->addr,
-                             bridge->port, 0/*no dirport*/,
-                             bridge->identity,
-                             DIR_PURPOSE_FETCH_SERVERDESC,
-                             ROUTER_PURPOSE_BRIDGE,
-                             DIRIND_ONEHOP, "authority.z", NULL, 0, 0);
-  tor_free(address);
-}
-
-/** Fetching the bridge descriptor from the bridge authority returned a
- * "not found". Fall back to trying a direct fetch. */
-void
-retry_bridge_descriptor_fetch_directly(const char *digest)
-{
-  bridge_info_t *bridge = find_bridge_by_digest(digest);
-  if (!bridge)
-    return; /* not found? oh well. */
-
-  launch_direct_bridge_descriptor_fetch(bridge);
-}
-
-/** For each bridge in our list for which we don't currently have a
- * descriptor, fetch a new copy of its descriptor -- either directly
- * from the bridge or via a bridge authority. */
-void
-fetch_bridge_descriptors(const or_options_t *options, time_t now)
-{
-  int num_bridge_auths = get_n_authorities(BRIDGE_DIRINFO);
-  int ask_bridge_directly;
-  int can_use_bridge_authority;
-
-  if (!bridge_list)
-    return;
-
-  /* If we still have unconfigured managed proxies, don't go and
-     connect to a bridge. */
-  if (pt_proxies_configuration_pending())
-    return;
-
-  SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge)
-    {
-      if (!download_status_is_ready(&bridge->fetch_status, now,
-                                    IMPOSSIBLE_TO_DOWNLOAD))
-        continue; /* don't bother, no need to retry yet */
-      if (routerset_contains_bridge(options->ExcludeNodes, bridge)) {
-        download_status_mark_impossible(&bridge->fetch_status);
-        log_warn(LD_APP, "Not using bridge at %s: it is in ExcludeNodes.",
-                 safe_str_client(fmt_and_decorate_addr(&bridge->addr)));
-        continue;
-      }
-
-      /* schedule another fetch as if this one will fail, in case it does */
-      download_status_failed(&bridge->fetch_status, 0);
-
-      can_use_bridge_authority = !tor_digest_is_zero(bridge->identity) &&
-                                 num_bridge_auths;
-      ask_bridge_directly = !can_use_bridge_authority ||
-                            !options->UpdateBridgesFromAuthority;
-      log_debug(LD_DIR, "ask_bridge_directly=%d (%d, %d, %d)",
-                ask_bridge_directly, tor_digest_is_zero(bridge->identity),
-                !options->UpdateBridgesFromAuthority, !num_bridge_auths);
-
-      if (ask_bridge_directly &&
-          !fascist_firewall_allows_address_or(&bridge->addr, bridge->port)) {
-        log_notice(LD_DIR, "Bridge at '%s' isn't reachable by our "
-                   "firewall policy. %s.",
-                   fmt_addrport(&bridge->addr, bridge->port),
-                   can_use_bridge_authority ?
-                     "Asking bridge authority instead" : "Skipping");
-        if (can_use_bridge_authority)
-          ask_bridge_directly = 0;
-        else
-          continue;
-      }
-
-      if (ask_bridge_directly) {
-        /* we need to ask the bridge itself for its descriptor. */
-        launch_direct_bridge_descriptor_fetch(bridge);
-      } else {
-        /* We have a digest and we want to ask an authority. We could
-         * combine all the requests into one, but that may give more
-         * hints to the bridge authority than we want to give. */
-        char resource[10 + HEX_DIGEST_LEN];
-        memcpy(resource, "fp/", 3);
-        base16_encode(resource+3, HEX_DIGEST_LEN+1,
-                      bridge->identity, DIGEST_LEN);
-        memcpy(resource+3+HEX_DIGEST_LEN, ".z", 3);
-        log_info(LD_DIR, "Fetching bridge info '%s' from bridge authority.",
-                 resource);
-        directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC,
-                ROUTER_PURPOSE_BRIDGE, resource, 0);
-      }
-    }
-  SMARTLIST_FOREACH_END(bridge);
-}
-
-/** If our <b>bridge</b> is configured to be a different address than
- * the bridge gives in <b>node</b>, rewrite the routerinfo
- * we received to use the address we meant to use. Now we handle
- * multihomed bridges better.
- */
-static void
-rewrite_node_address_for_bridge(const bridge_info_t *bridge, node_t *node)
-{
-  /* XXXX move this function. */
-  /* XXXX overridden addresses should really live in the node_t, so that the
-   *   routerinfo_t and the microdesc_t can be immutable.  But we can only
-   *   do that safely if we know that no function that connects to an OR
-   *   does so through an address from any source other than node_get_addr().
-   */
-  tor_addr_t addr;
-
-  if (node->ri) {
-    routerinfo_t *ri = node->ri;
-    tor_addr_from_ipv4h(&addr, ri->addr);
-
-    if ((!tor_addr_compare(&bridge->addr, &addr, CMP_EXACT) &&
-         bridge->port == ri->or_port) ||
-        (!tor_addr_compare(&bridge->addr, &ri->ipv6_addr, CMP_EXACT) &&
-         bridge->port == ri->ipv6_orport)) {
-      /* they match, so no need to do anything */
-    } else {
-      if (tor_addr_family(&bridge->addr) == AF_INET) {
-        ri->addr = tor_addr_to_ipv4h(&bridge->addr);
-        tor_free(ri->address);
-        ri->address = tor_dup_ip(ri->addr);
-        ri->or_port = bridge->port;
-        log_info(LD_DIR,
-                 "Adjusted bridge routerinfo for '%s' to match configured "
-                 "address %s:%d.",
-                 ri->nickname, ri->address, ri->or_port);
-      } else if (tor_addr_family(&bridge->addr) == AF_INET6) {
-        tor_addr_copy(&ri->ipv6_addr, &bridge->addr);
-        ri->ipv6_orport = bridge->port;
-        log_info(LD_DIR,
-                 "Adjusted bridge routerinfo for '%s' to match configured "
-                 "address %s.",
-                 ri->nickname, fmt_addrport(&ri->ipv6_addr, ri->ipv6_orport));
-      } else {
-        log_err(LD_BUG, "Address family not supported: %d.",
-                tor_addr_family(&bridge->addr));
-        return;
-      }
-    }
-
-    /* Mark which address to use based on which bridge_t we got. */
-    node->ipv6_preferred = (tor_addr_family(&bridge->addr) == AF_INET6 &&
-                            !tor_addr_is_null(&node->ri->ipv6_addr));
-
-    /* XXXipv6 we lack support for falling back to another address for
-       the same relay, warn the user */
-    if (!tor_addr_is_null(&ri->ipv6_addr)) {
-      tor_addr_port_t ap;
-      node_get_pref_orport(node, &ap);
-      log_notice(LD_CONFIG,
-                 "Bridge '%s' has both an IPv4 and an IPv6 address.  "
-                 "Will prefer using its %s address (%s).",
-                 ri->nickname,
-                 tor_addr_family(&ap.addr) == AF_INET6 ? "IPv6" : "IPv4",
-                 fmt_addrport(&ap.addr, ap.port));
-    }
-  }
-  if (node->rs) {
-    routerstatus_t *rs = node->rs;
-    tor_addr_from_ipv4h(&addr, rs->addr);
-
-    if (!tor_addr_compare(&bridge->addr, &addr, CMP_EXACT) &&
-        bridge->port == rs->or_port) {
-      /* they match, so no need to do anything */
-    } else {
-      rs->addr = tor_addr_to_ipv4h(&bridge->addr);
-      rs->or_port = bridge->port;
-      log_info(LD_DIR,
-               "Adjusted bridge routerstatus for '%s' to match "
-               "configured address %s.",
-               rs->nickname, fmt_addrport(&bridge->addr, rs->or_port));
-    }
-  }
-}
-
-/** We just learned a descriptor for a bridge. See if that
- * digest is in our entry guard list, and add it if not. */
-void
-learned_bridge_descriptor(routerinfo_t *ri, int from_cache)
-{
-  tor_assert(ri);
-  tor_assert(ri->purpose == ROUTER_PURPOSE_BRIDGE);
-  if (get_options()->UseBridges) {
-    int first = !any_bridge_descriptors_known();
-    bridge_info_t *bridge = get_configured_bridge_by_routerinfo(ri);
-    time_t now = time(NULL);
-    router_set_status(ri->cache_info.identity_digest, 1);
-
-    if (bridge) { /* if we actually want to use this one */
-      node_t *node;
-      /* it's here; schedule its re-fetch for a long time from now. */
-      if (!from_cache)
-        download_status_reset(&bridge->fetch_status);
-
-      node = node_get_mutable_by_id(ri->cache_info.identity_digest);
-      tor_assert(node);
-      rewrite_node_address_for_bridge(bridge, node);
-      add_an_entry_guard(node, 1, 1);
-
-      log_notice(LD_DIR, "new bridge descriptor '%s' (%s): %s", ri->nickname,
-                 from_cache ? "cached" : "fresh", router_describe(ri));
-      /* set entry->made_contact so if it goes down we don't drop it from
-       * our entry node list */
-      entry_guard_register_connect_status(ri->cache_info.identity_digest,
-                                          1, 0, now);
-      if (first)
-        routerlist_retry_directory_downloads(now);
-    }
-  }
-}
-
-/** Return 1 if any of our entry guards have descriptors that
- * are marked with purpose 'bridge' and are running. Else return 0.
- *
- * We use this function to decide if we're ready to start building
- * circuits through our bridges, or if we need to wait until the
- * directory "server/authority" requests finish. */
-int
-any_bridge_descriptors_known(void)
-{
-  tor_assert(get_options()->UseBridges);
-  return choose_random_entry(NULL)!=NULL ? 1 : 0;
-}
-
-/** Return 1 if there are any directory conns fetching bridge descriptors
- * that aren't marked for close. We use this to guess if we should tell
- * the controller that we have a problem. */
-int
-any_pending_bridge_descriptor_fetches(void)
-{
-  smartlist_t *conns = get_connection_array();
-  SMARTLIST_FOREACH_BEGIN(conns, connection_t *, conn) {
-    if (conn->type == CONN_TYPE_DIR &&
-        conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC &&
-        TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE &&
-        !conn->marked_for_close &&
-        conn->linked &&
-        conn->linked_conn && !conn->linked_conn->marked_for_close) {
-      log_debug(LD_DIR, "found one: %s", conn->address);
-      return 1;
-    }
-  } SMARTLIST_FOREACH_END(conn);
-  return 0;
-}
-
-/** Return 1 if we have at least one descriptor for an entry guard
- * (bridge or member of EntryNodes) and all descriptors we know are
- * down. Else return 0. If <b>act</b> is 1, then mark the down guards
- * up; else just observe and report. */
-static int
-entries_retry_helper(const or_options_t *options, int act)
-{
-  const node_t *node;
-  int any_known = 0;
-  int any_running = 0;
-  int need_bridges = options->UseBridges != 0;
-  if (!entry_guards)
-    entry_guards = smartlist_new();
-  SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
-      node = node_get_by_id(e->identity);
-      if (node && node_has_descriptor(node) &&
-          node_is_bridge(node) == need_bridges) {
-        any_known = 1;
-        if (node->is_running)
-          any_running = 1; /* some entry is both known and running */
-        else if (act) {
-          /* Mark all current connections to this OR as unhealthy, since
-           * otherwise there could be one that started 30 seconds
-           * ago, and in 30 seconds it will time out, causing us to mark
-           * the node down and undermine the retry attempt. We mark even
-           * the established conns, since if the network just came back
-           * we'll want to attach circuits to fresh conns. */
-          connection_or_set_bad_connections(node->identity, 1);
-
-          /* mark this entry node for retry */
-          router_set_status(node->identity, 1);
-          e->can_retry = 1;
-          e->bad_since = 0;
-        }
-      }
-  } SMARTLIST_FOREACH_END(e);
-  log_debug(LD_DIR, "%d: any_known %d, any_running %d",
-            act, any_known, any_running);
-  return any_known && !any_running;
-}
-
-/** Do we know any descriptors for our bridges / entrynodes, and are
- * all the ones we have descriptors for down? */
-int
-entries_known_but_down(const or_options_t *options)
-{
-  tor_assert(entry_list_is_constrained(options));
-  return entries_retry_helper(options, 0);
-}
-
-/** Mark all down known bridges / entrynodes up. */
-void
-entries_retry_all(const or_options_t *options)
-{
-  tor_assert(entry_list_is_constrained(options));
-  entries_retry_helper(options, 1);
-}
-
-/** Return true if we've ever had a bridge running a Tor version that can't
- * provide microdescriptors to us. In that case fall back to asking for
- * full descriptors. Eventually all bridges will support microdescriptors
- * and we can take this check out; see bug 4013. */
-int
-any_bridges_dont_support_microdescriptors(void)
-{
-  const node_t *node;
-  static int ever_answered_yes = 0;
-  if (!get_options()->UseBridges || !entry_guards)
-    return 0;
-  if (ever_answered_yes)
-    return 1; /* if we ever answer 'yes', always answer 'yes' */
-  SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
-    node = node_get_by_id(e->identity);
-    if (node && node->ri &&
-        node_is_bridge(node) && node_is_a_configured_bridge(node) &&
-        !tor_version_supports_microdescriptors(node->ri->platform)) {
-      /* This is one of our current bridges, and we know enough about
-       * it to know that it won't be able to answer our microdescriptor
-       * questions. */
-      ever_answered_yes = 1;
-      return 1;
-    }
-  } SMARTLIST_FOREACH_END(e);
-  return 0;
-}
-
-/** Release all storage held by the list of entry guards and related
- * memory structs. */
-void
-entry_guards_free_all(void)
-{
-  if (entry_guards) {
-    SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
-                      entry_guard_free(e));
-    smartlist_free(entry_guards);
-    entry_guards = NULL;
-  }
-  clear_bridge_list();
-  smartlist_free(bridge_list);
-  bridge_list = NULL;
-  circuit_build_times_free_timeouts(&circ_times);
-}
-
diff --git a/src/or/circuitbuild.h b/src/or/circuitbuild.h
index 3ab8fd5ca..a1d407268 100644
--- a/src/or/circuitbuild.h
+++ b/src/or/circuitbuild.h
@@ -51,95 +51,5 @@ void extend_info_free(extend_info_t *info);
 const node_t *build_state_get_exit_node(cpath_build_state_t *state);
 const char *build_state_get_exit_nickname(cpath_build_state_t *state);
 
-void entry_guards_compute_status(const or_options_t *options, time_t now);
-int entry_guard_register_connect_status(const char *digest, int succeeded,
-                                        int mark_relay_status, time_t now);
-void entry_nodes_should_be_added(void);
-int entry_list_is_constrained(const or_options_t *options);
-const node_t *choose_random_entry(cpath_build_state_t *state);
-int entry_guards_parse_state(or_state_t *state, int set, char **msg);
-void entry_guards_update_state(or_state_t *state);
-int getinfo_helper_entry_guards(control_connection_t *conn,
-                                const char *question, char **answer,
-                                const char **errmsg);
-
-void mark_bridge_list(void);
-void sweep_bridge_list(void);
-
-int routerinfo_is_a_configured_bridge(const routerinfo_t *ri);
-int node_is_a_configured_bridge(const node_t *node);
-void learned_router_identity(const tor_addr_t *addr, uint16_t port,
-                             const char *digest);
-void bridge_add_from_config(const tor_addr_t *addr, uint16_t port,
-                            const char *digest,
-                            const char *transport_name);
-void retry_bridge_descriptor_fetch_directly(const char *digest);
-void fetch_bridge_descriptors(const or_options_t *options, time_t now);
-void learned_bridge_descriptor(routerinfo_t *ri, int from_cache);
-int any_bridge_descriptors_known(void);
-int any_pending_bridge_descriptor_fetches(void);
-int entries_known_but_down(const or_options_t *options);
-void entries_retry_all(const or_options_t *options);
-
-int any_bridges_dont_support_microdescriptors(void);
-
-void entry_guards_free_all(void);
-
-extern circuit_build_times_t circ_times;
-int circuit_build_times_enough_to_compute(circuit_build_times_t *cbt);
-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);
-void circuit_build_times_count_timeout(circuit_build_times_t *cbt,
-                                       int did_onehop);
-int circuit_build_times_count_close(circuit_build_times_t *cbt,
-                                    int did_onehop, time_t start_time);
-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);
-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);
-void circuit_build_times_free_timeouts(circuit_build_times_t *cbt);
-void circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
-                                              networkstatus_t *ns);
-double circuit_build_times_timeout_rate(const circuit_build_times_t *cbt);
-double circuit_build_times_close_rate(const 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, double time_ms);
-int circuit_build_times_update_alpha(circuit_build_times_t *cbt);
-double circuit_build_times_cdf(circuit_build_times_t *cbt, double x);
-void circuitbuild_running_unit_tests(void);
-void circuit_build_times_reset(circuit_build_times_t *cbt);
-
-/* Network liveness functions */
-int circuit_build_times_network_check_changed(circuit_build_times_t *cbt);
-#endif
-
-/* Network liveness functions */
-void circuit_build_times_network_is_live(circuit_build_times_t *cbt);
-int circuit_build_times_network_check_live(circuit_build_times_t *cbt);
-void circuit_build_times_network_circ_success(circuit_build_times_t *cbt);
-
-/* DOCDOC circuit_build_times_get_bw_scale */
-int circuit_build_times_get_bw_scale(networkstatus_t *ns);
-
-/* DOCDOC find_transport_name_by_bridge_addrport */
-const char *find_transport_name_by_bridge_addrport(const tor_addr_t *addr,
-                                                   uint16_t port);
-struct transport_t;
-int find_transport_by_bridge_addrport(const tor_addr_t *addr, uint16_t port,
-                                      const struct transport_t **transport);
-
-int validate_pluggable_transports_config(void);
-
 #endif
 
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index b994ce9f7..3ec2bf15b 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -14,6 +14,7 @@
 #include "circuitbuild.h"
 #include "circuitlist.h"
 #include "circuituse.h"
+#include "circuitstats.h"
 #include "connection.h"
 #include "config.h"
 #include "connection_edge.h"
diff --git a/src/or/circuitstats.c b/src/or/circuitstats.c
new file mode 100644
index 000000000..6d529d1e4
--- /dev/null
+++ b/src/or/circuitstats.c
@@ -0,0 +1,1569 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#define CIRCUITSTATS_PRIVATE
+
+#include "or.h"
+#include "circuitbuild.h"
+#include "circuitstats.h"
+#include "config.h"
+#include "confparse.h"
+#include "control.h"
+#include "networkstatus.h"
+#include "statefile.h"
+
+#undef log
+#include <math.h>
+
+#define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
+
+/** Global list of circuit build times */
+// XXXX: 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.
+/* XXXX024 Make this static; add accessor functions. */
+circuit_build_times_t circ_times;
+
+/** 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;
+
+/**
+ * This function decides if CBT learning should be disabled. It returns
+ * true if one or more of the following four conditions are met:
+ *
+ *  1. If the cbtdisabled consensus parameter is set.
+ *  2. If the torrc option LearnCircuitBuildTimeout is false.
+ *  3. If we are a directory authority
+ *  4. If we fail to write circuit build time history to our state file.
+ */
+int
+circuit_build_times_disabled(void)
+{
+  if (unit_tests) {
+    return 0;
+  } else {
+    int consensus_disabled = networkstatus_get_param(NULL, "cbtdisabled",
+                                                     0, 0, 1);
+    int config_disabled = !get_options()->LearnCircuitBuildTimeout;
+    int dirauth_disabled = get_options()->AuthoritativeDir;
+    int state_disabled = did_last_state_file_write_fail() ? 1 : 0;
+
+    if (consensus_disabled || config_disabled || dirauth_disabled ||
+           state_disabled) {
+      log_debug(LD_CIRC,
+               "CircuitBuildTime learning is disabled. "
+               "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
+               consensus_disabled, config_disabled, dirauth_disabled,
+               state_disabled);
+      return 1;
+    } else {
+      log_debug(LD_CIRC,
+                "CircuitBuildTime learning is not disabled. "
+                "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
+                consensus_disabled, config_disabled, dirauth_disabled,
+                state_disabled);
+      return 0;
+    }
+  }
+}
+
+/**
+ * Retrieve and bounds-check the cbtmaxtimeouts consensus paramter.
+ *
+ * Effect: When this many timeouts happen in the last 'cbtrecentcount'
+ * circuit attempts, the client should discard all of its history and
+ * begin learning a fresh timeout value.
+ */
+static int32_t
+circuit_build_times_max_timeouts(void)
+{
+  int32_t cbt_maxtimeouts;
+
+  cbt_maxtimeouts = networkstatus_get_param(NULL, "cbtmaxtimeouts",
+                                 CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT,
+                                 CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
+                                 CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);
+
+  if (!(get_options()->LearnCircuitBuildTimeout)) {
+    log_debug(LD_BUG,
+              "circuit_build_times_max_timeouts() called, cbtmaxtimeouts is"
+              " %d",
+              cbt_maxtimeouts);
+  }
+
+  return cbt_maxtimeouts;
+}
+
+/**
+ * Retrieve and bounds-check the cbtnummodes consensus paramter.
+ *
+ * Effect: This value governs how many modes to use in the weighted
+ * average calculation of Pareto parameter Xm. A value of 3 introduces
+ * some bias (2-5% of CDF) under ideal conditions, but allows for better
+ * performance in the event that a client chooses guard nodes of radically
+ * different performance characteristics.
+ */
+static int32_t
+circuit_build_times_default_num_xm_modes(void)
+{
+  int32_t num = networkstatus_get_param(NULL, "cbtnummodes",
+                                        CBT_DEFAULT_NUM_XM_MODES,
+                                        CBT_MIN_NUM_XM_MODES,
+                                        CBT_MAX_NUM_XM_MODES);
+
+  if (!(get_options()->LearnCircuitBuildTimeout)) {
+    log_debug(LD_BUG,
+              "circuit_build_times_default_num_xm_modes() called, cbtnummodes"
+              " is %d",
+              num);
+  }
+
+  return num;
+}
+
+/**
+ * Retrieve and bounds-check the cbtmincircs consensus paramter.
+ *
+ * Effect: This is the minimum number of circuits to build before
+ * computing a timeout.
+ */
+static int32_t
+circuit_build_times_min_circs_to_observe(void)
+{
+  int32_t num = networkstatus_get_param(NULL, "cbtmincircs",
+                                        CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE,
+                                        CBT_MIN_MIN_CIRCUITS_TO_OBSERVE,
+                                        CBT_MAX_MIN_CIRCUITS_TO_OBSERVE);
+
+  if (!(get_options()->LearnCircuitBuildTimeout)) {
+    log_debug(LD_BUG,
+              "circuit_build_times_min_circs_to_observe() called, cbtmincircs"
+              " is %d",
+              num);
+  }
+
+  return num;
+}
+
+/** Return true iff <b>cbt</b> has recorded enough build times that we
+ * want to start acting on the timeout it implies. */
+int
+circuit_build_times_enough_to_compute(circuit_build_times_t *cbt)
+{
+  return cbt->total_build_times >= circuit_build_times_min_circs_to_observe();
+}
+
+/**
+ * Retrieve and bounds-check the cbtquantile consensus paramter.
+ *
+ * Effect: This is the position on the quantile curve to use to set the
+ * timeout value. It is a percent (10-99).
+ */
+double
+circuit_build_times_quantile_cutoff(void)
+{
+  int32_t num = networkstatus_get_param(NULL, "cbtquantile",
+                                        CBT_DEFAULT_QUANTILE_CUTOFF,
+                                        CBT_MIN_QUANTILE_CUTOFF,
+                                        CBT_MAX_QUANTILE_CUTOFF);
+
+  if (!(get_options()->LearnCircuitBuildTimeout)) {
+    log_debug(LD_BUG,
+              "circuit_build_times_quantile_cutoff() called, cbtquantile"
+              " is %d",
+              num);
+  }
+
+  return num/100.0;
+}
+
+/* DOCDOC circuit_build_times_get_bw_scale */
+int
+circuit_build_times_get_bw_scale(networkstatus_t *ns)
+{
+  return networkstatus_get_param(ns, "bwweightscale",
+                                 BW_WEIGHT_SCALE,
+                                 BW_MIN_WEIGHT_SCALE,
+                                 BW_MAX_WEIGHT_SCALE);
+}
+
+/**
+ * Retrieve and bounds-check the cbtclosequantile consensus paramter.
+ *
+ * Effect: This is the position on the quantile curve to use to set the
+ * timeout value to use to actually close circuits. It is a percent
+ * (0-99).
+ */
+static double
+circuit_build_times_close_quantile(void)
+{
+  int32_t param;
+  /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */
+  int32_t min = (int)tor_lround(100*circuit_build_times_quantile_cutoff());
+  param = networkstatus_get_param(NULL, "cbtclosequantile",
+             CBT_DEFAULT_CLOSE_QUANTILE,
+             CBT_MIN_CLOSE_QUANTILE,
+             CBT_MAX_CLOSE_QUANTILE);
+
+  if (!(get_options()->LearnCircuitBuildTimeout)) {
+    log_debug(LD_BUG,
+              "circuit_build_times_close_quantile() called, cbtclosequantile"
+              " is %d", param);
+  }
+
+  if (param < min) {
+    log_warn(LD_DIR, "Consensus parameter cbtclosequantile is "
+             "too small, raising to %d", min);
+    param = min;
+  }
+  return param / 100.0;
+}
+
+/**
+ * Retrieve and bounds-check the cbttestfreq consensus paramter.
+ *
+ * Effect: Describes how often in seconds to build a test circuit to
+ * gather timeout values. Only applies if less than 'cbtmincircs'
+ * have been recorded.
+ */
+static int32_t
+circuit_build_times_test_frequency(void)
+{
+  int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
+                                        CBT_DEFAULT_TEST_FREQUENCY,
+                                        CBT_MIN_TEST_FREQUENCY,
+                                        CBT_MAX_TEST_FREQUENCY);
+
+  if (!(get_options()->LearnCircuitBuildTimeout)) {
+    log_debug(LD_BUG,
+              "circuit_build_times_test_frequency() called, cbttestfreq is %d",
+              num);
+  }
+
+  return num;
+}
+
+/**
+ * Retrieve and bounds-check the cbtmintimeout consensus parameter.
+ *
+ * Effect: This is the minimum allowed timeout value in milliseconds.
+ * The minimum is to prevent rounding to 0 (we only check once
+ * per second).
+ */
+static int32_t
+circuit_build_times_min_timeout(void)
+{
+  int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
+                                        CBT_DEFAULT_TIMEOUT_MIN_VALUE,
+                                        CBT_MIN_TIMEOUT_MIN_VALUE,
+                                        CBT_MAX_TIMEOUT_MIN_VALUE);
+
+  if (!(get_options()->LearnCircuitBuildTimeout)) {
+    log_debug(LD_BUG,
+              "circuit_build_times_min_timeout() called, cbtmintimeout is %d",
+              num);
+  }
+
+  return num;
+}
+
+/**
+ * Retrieve and bounds-check the cbtinitialtimeout consensus paramter.
+ *
+ * Effect: This is the timeout value to use before computing a timeout,
+ * in milliseconds.
+ */
+int32_t
+circuit_build_times_initial_timeout(void)
+{
+  int32_t min = circuit_build_times_min_timeout();
+  int32_t param = networkstatus_get_param(NULL, "cbtinitialtimeout",
+                                          CBT_DEFAULT_TIMEOUT_INITIAL_VALUE,
+                                          CBT_MIN_TIMEOUT_INITIAL_VALUE,
+                                          CBT_MAX_TIMEOUT_INITIAL_VALUE);
+
+  if (!(get_options()->LearnCircuitBuildTimeout)) {
+    log_debug(LD_BUG,
+              "circuit_build_times_initial_timeout() called, "
+              "cbtinitialtimeout is %d",
+              param);
+  }
+
+  if (param < min) {
+    log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, "
+             "raising to %d", min);
+    param = min;
+  }
+  return param;
+}
+
+/**
+ * Retrieve and bounds-check the cbtrecentcount consensus paramter.
+ *
+ * Effect: This is the number of circuit build times to keep track of
+ * for deciding if we hit cbtmaxtimeouts and need to reset our state
+ * and learn a new timeout.
+ */
+static int32_t
+circuit_build_times_recent_circuit_count(networkstatus_t *ns)
+{
+  int32_t num;
+  num = networkstatus_get_param(ns, "cbtrecentcount",
+                                CBT_DEFAULT_RECENT_CIRCUITS,
+                                CBT_MIN_RECENT_CIRCUITS,
+                                CBT_MAX_RECENT_CIRCUITS);
+
+  if (!(get_options()->LearnCircuitBuildTimeout)) {
+    log_debug(LD_BUG,
+              "circuit_build_times_recent_circuit_count() called, "
+              "cbtrecentcount is %d",
+              num);
+  }
+
+  return num;
+}
+
+/**
+ * This function is called when we get a consensus update.
+ *
+ * It checks to see if we have changed any consensus parameters
+ * that require reallocation or discard of previous stats.
+ */
+void
+circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
+                                         networkstatus_t *ns)
+{
+  int32_t num;
+
+  /*
+   * First check if we're doing adaptive timeouts at all; nothing to
+   * update if we aren't.
+   */
+
+  if (!circuit_build_times_disabled()) {
+    num = circuit_build_times_recent_circuit_count(ns);
+
+    if (num > 0) {
+      if (num != cbt->liveness.num_recent_circs) {
+        int8_t *recent_circs;
+        log_notice(LD_CIRC, "The Tor Directory Consensus has changed how many "
+                   "circuits we must track to detect network failures from %d "
+                   "to %d.", cbt->liveness.num_recent_circs, num);
+
+        tor_assert(cbt->liveness.timeouts_after_firsthop ||
+                   cbt->liveness.num_recent_circs == 0);
+
+        /*
+         * Technically this is a circular array that we are reallocating
+         * and memcopying. However, since it only consists of either 1s
+         * or 0s, and is only used in a statistical test to determine when
+         * we should discard our history after a sufficient number of 1's
+         * have been reached, it is fine if order is not preserved or
+         * elements are lost.
+         *
+         * cbtrecentcount should only be changing in cases of severe network
+         * distress anyway, so memory correctness here is paramount over
+         * doing acrobatics to preserve the array.
+         */
+        recent_circs = tor_malloc_zero(sizeof(int8_t)*num);
+        if (cbt->liveness.timeouts_after_firsthop &&
+            cbt->liveness.num_recent_circs > 0) {
+          memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop,
+                 sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs));
+        }
+
+        // Adjust the index if it needs it.
+        if (num < cbt->liveness.num_recent_circs) {
+          cbt->liveness.after_firsthop_idx = MIN(num-1,
+                  cbt->liveness.after_firsthop_idx);
+        }
+
+        tor_free(cbt->liveness.timeouts_after_firsthop);
+        cbt->liveness.timeouts_after_firsthop = recent_circs;
+        cbt->liveness.num_recent_circs = num;
+      }
+      /* else no change, nothing to do */
+    } else { /* num == 0 */
+      /*
+       * Weird.  This probably shouldn't happen, so log a warning, but try
+       * to do something sensible anyway.
+       */
+
+      log_warn(LD_CIRC,
+               "The cbtrecentcircs consensus parameter came back zero!  "
+               "This disables adaptive timeouts since we can't keep track of "
+               "any recent circuits.");
+
+      circuit_build_times_free_timeouts(cbt);
+    }
+  } else {
+    /*
+     * Adaptive timeouts are disabled; this might be because of the
+     * LearnCircuitBuildTimes config parameter, and hence permanent, or
+     * the cbtdisabled consensus parameter, so it may be a new condition.
+     * Treat it like getting num == 0 above and free the circuit history
+     * if we have any.
+     */
+
+    circuit_build_times_free_timeouts(cbt);
+  }
+}
+
+/**
+ * Return the initial default or configured timeout in milliseconds
+ */
+static double
+circuit_build_times_get_initial_timeout(void)
+{
+  double timeout;
+
+  /*
+   * Check if we have LearnCircuitBuildTimeout, and if we don't,
+   * always use CircuitBuildTimeout, no questions asked.
+   */
+  if (get_options()->LearnCircuitBuildTimeout) {
+    if (!unit_tests && get_options()->CircuitBuildTimeout) {
+      timeout = get_options()->CircuitBuildTimeout*1000;
+      if (timeout < circuit_build_times_min_timeout()) {
+        log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
+                 circuit_build_times_min_timeout()/1000);
+        timeout = circuit_build_times_min_timeout();
+      }
+    } else {
+      timeout = circuit_build_times_initial_timeout();
+    }
+  } else {
+    timeout = get_options()->CircuitBuildTimeout*1000;
+  }
+
+  return timeout;
+}
+
+/**
+ * Reset the build time state.
+ *
+ * Leave estimated parameters, timeout and network liveness intact
+ * 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->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 values based on either the config setting,
+ * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
+ */
+void
+circuit_build_times_init(circuit_build_times_t *cbt)
+{
+  memset(cbt, 0, sizeof(*cbt));
+  /*
+   * Check if we really are using adaptive timeouts, and don't keep
+   * track of this stuff if not.
+   */
+  if (!circuit_build_times_disabled()) {
+    cbt->liveness.num_recent_circs =
+      circuit_build_times_recent_circuit_count(NULL);
+    cbt->liveness.timeouts_after_firsthop =
+      tor_malloc_zero(sizeof(int8_t)*cbt->liveness.num_recent_circs);
+  } else {
+    cbt->liveness.num_recent_circs = 0;
+    cbt->liveness.timeouts_after_firsthop = NULL;
+  }
+  cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
+  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
+}
+
+/**
+ * Free the saved timeouts, if the cbtdisabled consensus parameter got turned
+ * on or something.
+ */
+
+void
+circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
+{
+  if (!cbt) return;
+
+  if (cbt->liveness.timeouts_after_firsthop) {
+    tor_free(cbt->liveness.timeouts_after_firsthop);
+  }
+
+  cbt->liveness.num_recent_circs = 0;
+}
+
+#if 0
+/**
+ * Rewind our build time history by n positions.
+ */
+static void
+circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
+{
+  int i = 0;
+
+  cbt->build_times_idx -= n;
+  cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;
+
+  for (i = 0; i < n; i++) {
+    cbt->circuit_build_times[(i+cbt->build_times_idx)
+                             %CBT_NCIRCUITS_TO_OBSERVE]=0;
+  }
+
+  if (cbt->total_build_times > n) {
+    cbt->total_build_times -= n;
+  } else {
+    cbt->total_build_times = 0;
+  }
+
+  log_info(LD_CIRC,
+          "Rewound history by %d places. Current index: %d. "
+          "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
+}
+#endif
+
+/**
+ * Add a new build time value <b>time</b> to the set of build times. Time
+ * units are milliseconds.
+ *
+ * circuit_build_times <b>cbt</b> 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 <= 0 || time > CBT_BUILD_TIME_MAX) {
+    log_warn(LD_BUG, "Circuit build time is too large (%u)."
+                      "This is probably a bug.", time);
+    tor_fragile_assert();
+    return -1;
+  }
+
+  log_debug(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) % CBT_NCIRCUITS_TO_OBSERVE;
+  if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
+    cbt->total_build_times++;
+
+  if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
+    /* Save state every n 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 < CBT_NCIRCUITS_TO_OBSERVE; i++) {
+    if (cbt->circuit_build_times[i] > max_build_time
+            && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED)
+      max_build_time = cbt->circuit_build_times[i];
+  }
+  return max_build_time;
+}
+
+#if 0
+/** Return minimum circuit build time */
+build_time_t
+circuit_build_times_min(circuit_build_times_t *cbt)
+{
+  int i = 0;
+  build_time_t min_build_time = CBT_BUILD_TIME_MAX;
+  for (i = 0; i < CBT_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 == CBT_BUILD_TIME_MAX) {
+    log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
+  }
+  return min_build_time;
+}
+#endif
+
+/**
+ * Calculate and return a histogram for the set of build times.
+ *
+ * Returns an allocated array of histrogram bins representing
+ * the frequency of index*CBT_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 / CBT_BIN_WIDTH);
+  histogram = tor_malloc_zero(*nbins * sizeof(build_time_t));
+
+  // calculate histogram
+  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
+    if (cbt->circuit_build_times[i] == 0
+            || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
+      continue; /* 0 <-> uninitialized */
+
+    c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH);
+    histogram[c]++;
+  }
+
+  return histogram;
+}
+
+/**
+ * Return the Pareto start-of-curve parameter Xm.
+ *
+ * Because we are not a true Pareto curve, we compute this as the
+ * weighted average of the N most frequent build time bins. N is either
+ * 1 if we don't have enough circuit build time data collected, or
+ * determined by the consensus parameter cbtnummodes (default 3).
+ */
+static build_time_t
+circuit_build_times_get_xm(circuit_build_times_t *cbt)
+{
+  build_time_t i, nbins;
+  build_time_t *nth_max_bin;
+  int32_t bin_counts=0;
+  build_time_t ret = 0;
+  uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
+  int n=0;
+  int num_modes = circuit_build_times_default_num_xm_modes();
+
+  tor_assert(nbins > 0);
+  tor_assert(num_modes > 0);
+
+  // Only use one mode if < 1000 buildtimes. Not enough data
+  // for multiple.
+  if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
+    num_modes = 1;
+
+  nth_max_bin = (build_time_t*)tor_malloc_zero(num_modes*sizeof(build_time_t));
+
+  /* Determine the N most common build times */
+  for (i = 0; i < nbins; i++) {
+    if (histogram[i] >= histogram[nth_max_bin[0]]) {
+      nth_max_bin[0] = i;
+    }
+
+    for (n = 1; n < num_modes; n++) {
+      if (histogram[i] >= histogram[nth_max_bin[n]] &&
+           (!histogram[nth_max_bin[n-1]]
+               || histogram[i] < histogram[nth_max_bin[n-1]])) {
+        nth_max_bin[n] = i;
+      }
+    }
+  }
+
+  for (n = 0; n < num_modes; n++) {
+    bin_counts += histogram[nth_max_bin[n]];
+    ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]];
+    log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]),
+             histogram[nth_max_bin[n]]);
+  }
+
+  /* The following assert is safe, because we don't get called when we
+   * haven't observed at least CBT_MIN_MIN_CIRCUITS_TO_OBSERVE circuits. */
+  tor_assert(bin_counts > 0);
+
+  ret /= bin_counts;
+  tor_free(histogram);
+  tor_free(nth_max_bin);
+
+  return ret;
+}
+
+/**
+ * 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;
+  state->CircuitBuildAbandonedCount = 0;
+
+  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
+    if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
+      state->CircuitBuildAbandonedCount++;
+  }
+
+  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");
+    tor_asprintf(&line->value, "%d %d",
+            CBT_BIN_TO_MS(i), histogram[i]);
+    next = &(line->next);
+  }
+
+  if (!unit_tests) {
+    if (!get_options()->AvoidDiskWrites)
+      or_state_mark_dirty(get_or_state(), 0);
+  }
+
+  tor_free(histogram);
+}
+
+/**
+ * Shuffle the build times array.
+ *
+ * Adapted from http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
+ */
+static void
+circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
+                                            build_time_t *raw_times,
+                                            uint32_t num_times)
+{
+  uint32_t n = num_times;
+  if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
+    log_notice(LD_CIRC, "The number of circuit times that this Tor version "
+               "uses to calculate build times is less than the number stored "
+               "in your state file. Decreasing the circuit time history from "
+               "%lu to %d.", (unsigned long)num_times,
+               CBT_NCIRCUITS_TO_OBSERVE);
+  }
+
+  if (n > INT_MAX-1) {
+    log_warn(LD_CIRC, "For some insane reasons, you had %lu circuit build "
+             "observations in your state file. That's far too many; probably "
+             "there's a bug here.", (unsigned long)n);
+    n = INT_MAX-1;
+  }
+
+  /* This code can only be run on a compact array */
+  while (n-- > 1) {
+    int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
+    build_time_t tmp = raw_times[k];
+    raw_times[k] = raw_times[n];
+    raw_times[n] = tmp;
+  }
+
+  /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
+   * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
+  for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) {
+    circuit_build_times_add_time(cbt, raw_times[n]);
+  }
+}
+
+/**
+ * Filter old synthetic timeouts that were created before the
+ * new right-censored Pareto calculation was deployed.
+ *
+ * Once all clients before 0.2.1.13-alpha are gone, this code
+ * will be unused.
+ */
+static int
+circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
+{
+  int num_filtered=0, i=0;
+  double timeout_rate = 0;
+  build_time_t max_timeout = 0;
+
+  timeout_rate = circuit_build_times_timeout_rate(cbt);
+  max_timeout = (build_time_t)cbt->close_ms;
+
+  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
+    if (cbt->circuit_build_times[i] > max_timeout) {
+      build_time_t replaced = cbt->circuit_build_times[i];
+      num_filtered++;
+      cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED;
+
+      log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced,
+               cbt->circuit_build_times[i]);
+    }
+  }
+
+  log_info(LD_CIRC,
+           "We had %d timeouts out of %d build times, "
+           "and filtered %d above the max of %u",
+          (int)(cbt->total_build_times*timeout_rate),
+          cbt->total_build_times, num_filtered, max_timeout);
+
+  return num_filtered;
+}
+
+/**
+ * Load histogram from <b>state</b>, shuffling the resulting array
+ * after we do so. Use this result to estimate parameters and
+ * calculate the timeout.
+ *
+ * Return -1 on error.
+ */
+int
+circuit_build_times_parse_state(circuit_build_times_t *cbt,
+                                or_state_t *state)
+{
+  int tot_values = 0;
+  uint32_t loaded_cnt = 0, N = 0;
+  config_line_t *line;
+  unsigned int i;
+  build_time_t *loaded_times;
+  int err = 0;
+  circuit_build_times_init(cbt);
+
+  if (circuit_build_times_disabled()) {
+    return 0;
+  }
+
+  /* build_time_t 0 means uninitialized */
+  loaded_times = tor_malloc_zero(sizeof(build_time_t)*state->TotalBuildTimes);
+
+  for (line = state->BuildtimeHistogram; line; line = line->next) {
+    smartlist_t *args = smartlist_new();
+    smartlist_split_string(args, line->value, " ",
+                           SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+    if (smartlist_len(args) < 2) {
+      log_warn(LD_GENERAL, "Unable to parse circuit build times: "
+                           "Too few arguments to CircuitBuildTime");
+      err = 1;
+      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,
+                                         CBT_BUILD_TIME_MAX, &ok, NULL);
+      if (!ok) {
+        log_warn(LD_GENERAL, "Unable to parse circuit build times: "
+                             "Unparsable bin number");
+        err = 1;
+        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
+        smartlist_free(args);
+        break;
+      }
+      count = (uint32_t)tor_parse_ulong(count_str, 0, 0,
+                                        UINT32_MAX, &ok, NULL);
+      if (!ok) {
+        log_warn(LD_GENERAL, "Unable to parse circuit build times: "
+                             "Unparsable bin count");
+        err = 1;
+        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
+        smartlist_free(args);
+        break;
+      }
+
+      if (loaded_cnt+count+state->CircuitBuildAbandonedCount
+            > state->TotalBuildTimes) {
+        log_warn(LD_CIRC,
+                 "Too many build times in state file. "
+                 "Stopping short before %d",
+                 loaded_cnt+count);
+        SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
+        smartlist_free(args);
+        break;
+      }
+
+      for (k = 0; k < count; k++) {
+        loaded_times[loaded_cnt++] = ms;
+      }
+      N++;
+      SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
+      smartlist_free(args);
+    }
+  }
+
+  log_info(LD_CIRC,
+           "Adding %d timeouts.", state->CircuitBuildAbandonedCount);
+  for (i=0; i < state->CircuitBuildAbandonedCount; i++) {
+    loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED;
+  }
+
+  if (loaded_cnt != state->TotalBuildTimes) {
+    log_warn(LD_CIRC,
+            "Corrupt state file? Build times count mismatch. "
+            "Read %d times, but file says %d", loaded_cnt,
+            state->TotalBuildTimes);
+    err = 1;
+    circuit_build_times_reset(cbt);
+    goto done;
+  }
+
+  circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
+
+  /* Verify that we didn't overwrite any indexes */
+  for (i=0; i < CBT_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);
+
+  if (cbt->total_build_times != tot_values
+        || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) {
+    log_warn(LD_CIRC,
+            "Corrupt state file? Shuffled build times mismatch. "
+            "Read %d times, but file says %d", tot_values,
+            state->TotalBuildTimes);
+    err = 1;
+    circuit_build_times_reset(cbt);
+    goto done;
+  }
+
+  circuit_build_times_set_timeout(cbt);
+
+  if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) {
+    circuit_build_times_filter_timeouts(cbt);
+  }
+
+ done:
+  tor_free(loaded_times);
+  return err ? -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.
+ */
+int
+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,abandoned_count=0;
+  build_time_t max_time=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_get_xm(cbt);
+
+  tor_assert(cbt->Xm > 0);
+
+  for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) {
+    if (!x[i]) {
+      continue;
+    }
+
+    if (x[i] < cbt->Xm) {
+      a += tor_mathlog(cbt->Xm);
+    } else if (x[i] == CBT_BUILD_ABANDONED) {
+      abandoned_count++;
+    } else {
+      a += tor_mathlog(x[i]);
+      if (x[i] > max_time)
+        max_time = x[i];
+    }
+    n++;
+  }
+
+  /*
+   * We are erring and asserting here because this can only happen
+   * in codepaths other than startup. The startup state parsing code
+   * performs this same check, and resets state if it hits it. If we
+   * hit it at runtime, something serious has gone wrong.
+   */
+  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);
+
+  if (max_time <= 0) {
+    /* This can happen if Xm is actually the *maximum* value in the set.
+     * It can also happen if we've abandoned every single circuit somehow.
+     * In either case, tell the caller not to compute a new build timeout. */
+    log_warn(LD_BUG,
+             "Could not determine largest build time (%d). "
+             "Xm is %dms and we've abandoned %d out of %d circuits.", max_time,
+             cbt->Xm, abandoned_count, n);
+    return 0;
+  }
+
+  a += abandoned_count*tor_mathlog(max_time);
+
+  a -= n*tor_mathlog(cbt->Xm);
+  // Estimator comes from Eq #4 in:
+  // "Bayesian estimation based on trimmed samples from Pareto populations"
+  // by Arturo J. Fernández. We are right-censored only.
+  a = (n-abandoned_count)/a;
+
+  cbt->alpha = a;
+
+  return 1;
+}
+
+/**
+ * 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.
+ *
+ * Return value is in milliseconds.
+ */
+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 within the [q_lo, 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)
+{
+  double randval = crypto_rand_double();
+  build_time_t ret;
+  double u;
+
+  /* Generate between [q_lo, q_hi) */
+  /*XXXX This is what nextafter is supposed to be for; we should use it on the
+   * platforms that support it. */
+  q_hi -= 1.0/(INT32_MAX);
+
+  tor_assert(q_lo >= 0);
+  tor_assert(q_hi < 1);
+  tor_assert(q_lo < q_hi);
+
+  u = q_lo + (q_hi-q_lo)*randval;
+
+  tor_assert(0 <= u && u < 1.0);
+  /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
+  ret = (build_time_t)
+    tor_lround(circuit_build_times_calculate_timeout(cbt, u));
+  tor_assert(ret > 0);
+  return ret;
+}
+
+/**
+ * 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, double timeout_ms)
+{
+  // 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 = tor_mathlog(1.0-quantile)/
+    (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
+  tor_assert(cbt->alpha > 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 */
+  return !circuit_build_times_enough_to_compute(cbt);
+}
+
+/**
+ * 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 > circuit_build_times_test_frequency();
+}
+
+/**
+ * Called to indicate that the network showed some signs of liveness,
+ * i.e. we received a cell.
+ *
+ * This is used by circuit_build_times_network_check_live() to decide
+ * if we should record the circuit build timeout or not.
+ *
+ * This function is called every time we receive a cell. Avoid
+ * syscalls, events, and other high-intensity work.
+ */
+void
+circuit_build_times_network_is_live(circuit_build_times_t *cbt)
+{
+  time_t now = approx_time();
+  if (cbt->liveness.nonlive_timeouts > 0) {
+    log_notice(LD_CIRC,
+               "Tor now sees network activity. Restoring circuit build "
+               "timeout recording. Network was down for %d seconds "
+               "during %d circuit attempts.",
+               (int)(now - cbt->liveness.network_last_live),
+               cbt->liveness.nonlive_timeouts);
+  }
+  cbt->liveness.network_last_live = now;
+  cbt->liveness.nonlive_timeouts = 0;
+}
+
+/**
+ * Called to indicate that we completed a circuit. Because this circuit
+ * succeeded, it doesn't count as a timeout-after-the-first-hop.
+ *
+ * This is used by circuit_build_times_network_check_changed() to determine
+ * if we had too many recent timeouts and need to reset our learned timeout
+ * to something higher.
+ */
+void
+circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
+{
+  /* Check for NULLness because we might not be using adaptive timeouts */
+  if (cbt->liveness.timeouts_after_firsthop &&
+      cbt->liveness.num_recent_circs > 0) {
+    cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
+      = 0;
+    cbt->liveness.after_firsthop_idx++;
+    cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
+  }
+}
+
+/**
+ * A circuit just timed out. If it failed after the first hop, record it
+ * in our history for later deciding if the network speed has changed.
+ *
+ * This is used by circuit_build_times_network_check_changed() to determine
+ * if we had too many recent timeouts and need to reset our learned timeout
+ * to something higher.
+ */
+static void
+circuit_build_times_network_timeout(circuit_build_times_t *cbt,
+                                    int did_onehop)
+{
+  /* Check for NULLness because we might not be using adaptive timeouts */
+  if (cbt->liveness.timeouts_after_firsthop &&
+      cbt->liveness.num_recent_circs > 0) {
+    if (did_onehop) {
+      cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
+        = 1;
+      cbt->liveness.after_firsthop_idx++;
+      cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
+    }
+  }
+}
+
+/**
+ * A circuit was just forcibly closed. If there has been no recent network
+ * activity at all, but this circuit was launched back when we thought the
+ * network was live, increment the number of "nonlive" circuit timeouts.
+ *
+ * This is used by circuit_build_times_network_check_live() to decide
+ * if we should record the circuit build timeout or not.
+ */
+static void
+circuit_build_times_network_close(circuit_build_times_t *cbt,
+                                    int did_onehop, time_t start_time)
+{
+  time_t now = time(NULL);
+  /*
+   * Check if this is a timeout that was for a circuit that spent its
+   * entire existence during a time where we have had no network activity.
+   */
+  if (cbt->liveness.network_last_live < start_time) {
+    if (did_onehop) {
+      char last_live_buf[ISO_TIME_LEN+1];
+      char start_time_buf[ISO_TIME_LEN+1];
+      char now_buf[ISO_TIME_LEN+1];
+      format_local_iso_time(last_live_buf, cbt->liveness.network_last_live);
+      format_local_iso_time(start_time_buf, start_time);
+      format_local_iso_time(now_buf, now);
+      log_warn(LD_BUG,
+               "Circuit somehow completed a hop while the network was "
+               "not live. Network was last live at %s, but circuit launched "
+               "at %s. It's now %s.", last_live_buf, start_time_buf,
+               now_buf);
+    }
+    cbt->liveness.nonlive_timeouts++;
+    if (cbt->liveness.nonlive_timeouts == 1) {
+      log_notice(LD_CIRC,
+                 "Tor has not observed any network activity for the past %d "
+                 "seconds. Disabling circuit build timeout recording.",
+                 (int)(now - cbt->liveness.network_last_live));
+    } else {
+      log_info(LD_CIRC,
+             "Got non-live timeout. Current count is: %d",
+             cbt->liveness.nonlive_timeouts);
+    }
+  }
+}
+
+/**
+ * When the network is not live, we do not record circuit build times.
+ *
+ * The network is considered not live if there has been at least one
+ * circuit build that began and ended (had its close_ms measurement
+ * period expire) since we last received a cell.
+ *
+ * Also has the side effect of rewinding the circuit time history
+ * in the case of recent liveness changes.
+ */
+int
+circuit_build_times_network_check_live(circuit_build_times_t *cbt)
+{
+  if (cbt->liveness.nonlive_timeouts > 0) {
+    return 0;
+  }
+
+  return 1;
+}
+
+/**
+ * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
+ * the past RECENT_CIRCUITS time out after the first hop. Used to detect
+ * if the network connection has changed significantly, and if so,
+ * resets our circuit build timeout to the default.
+ *
+ * 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_network_check_changed(circuit_build_times_t *cbt)
+{
+  int total_build_times = cbt->total_build_times;
+  int timeout_count=0;
+  int i;
+
+  if (cbt->liveness.timeouts_after_firsthop &&
+      cbt->liveness.num_recent_circs > 0) {
+    /* how many of our recent circuits made it to the first hop but then
+     * timed out? */
+    for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
+      timeout_count += cbt->liveness.timeouts_after_firsthop[i];
+    }
+  }
+
+  /* If 80% of our recent circuits are timing out after the first hop,
+   * we need to re-estimate a new initial alpha and timeout. */
+  if (timeout_count < circuit_build_times_max_timeouts()) {
+    return 0;
+  }
+
+  circuit_build_times_reset(cbt);
+  if (cbt->liveness.timeouts_after_firsthop &&
+      cbt->liveness.num_recent_circs > 0) {
+    memset(cbt->liveness.timeouts_after_firsthop, 0,
+            sizeof(*cbt->liveness.timeouts_after_firsthop)*
+            cbt->liveness.num_recent_circs);
+  }
+  cbt->liveness.after_firsthop_idx = 0;
+
+  /* Check to see if this has happened before. If so, double the timeout
+   * to give people on abysmally bad network connections a shot at access */
+  if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
+    if (cbt->timeout_ms > INT32_MAX/2 || cbt->close_ms > INT32_MAX/2) {
+      log_warn(LD_CIRC, "Insanely large circuit build timeout value. "
+              "(timeout = %fmsec, close = %fmsec)",
+               cbt->timeout_ms, cbt->close_ms);
+    } else {
+      cbt->timeout_ms *= 2;
+      cbt->close_ms *= 2;
+    }
+  } else {
+    cbt->close_ms = cbt->timeout_ms
+                  = circuit_build_times_get_initial_timeout();
+  }
+
+  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
+
+  log_notice(LD_CIRC,
+            "Your network connection speed appears to have changed. Resetting "
+            "timeout to %lds after %d timeouts and %d buildtimes.",
+            tor_lround(cbt->timeout_ms/1000), timeout_count,
+            total_build_times);
+
+  return 1;
+}
+
+/**
+ * Count the number of timeouts in a set of cbt data.
+ */
+double
+circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
+{
+  int i=0,timeouts=0;
+  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
+    if (cbt->circuit_build_times[i] >= cbt->timeout_ms) {
+       timeouts++;
+    }
+  }
+
+  if (!cbt->total_build_times)
+    return 0;
+
+  return ((double)timeouts)/cbt->total_build_times;
+}
+
+/**
+ * Count the number of closed circuits in a set of cbt data.
+ */
+double
+circuit_build_times_close_rate(const circuit_build_times_t *cbt)
+{
+  int i=0,closed=0;
+  for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
+    if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) {
+       closed++;
+    }
+  }
+
+  if (!cbt->total_build_times)
+    return 0;
+
+  return ((double)closed)/cbt->total_build_times;
+}
+
+/**
+ * Store a timeout as a synthetic value.
+ *
+ * Returns true if the store was successful and we should possibly
+ * update our timeout estimate.
+ */
+int
+circuit_build_times_count_close(circuit_build_times_t *cbt,
+                                int did_onehop,
+                                time_t start_time)
+{
+  if (circuit_build_times_disabled()) {
+    cbt->close_ms = cbt->timeout_ms
+                  = circuit_build_times_get_initial_timeout();
+    return 0;
+  }
+
+  /* Record this force-close to help determine if the network is dead */
+  circuit_build_times_network_close(cbt, did_onehop, start_time);
+
+  /* Only count timeouts if network is live.. */
+  if (!circuit_build_times_network_check_live(cbt)) {
+    return 0;
+  }
+
+  circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED);
+  return 1;
+}
+
+/**
+ * Update timeout counts to determine if we need to expire
+ * our build time history due to excessive timeouts.
+ *
+ * We do not record any actual time values at this stage;
+ * we are only interested in recording the fact that a timeout
+ * happened. We record the time values via
+ * circuit_build_times_count_close() and circuit_build_times_add_time().
+ */
+void
+circuit_build_times_count_timeout(circuit_build_times_t *cbt,
+                                  int did_onehop)
+{
+  if (circuit_build_times_disabled()) {
+    cbt->close_ms = cbt->timeout_ms
+                  = circuit_build_times_get_initial_timeout();
+    return;
+  }
+
+  /* Register the fact that a timeout just occurred. */
+  circuit_build_times_network_timeout(cbt, did_onehop);
+
+  /* If there are a ton of timeouts, we should reset
+   * the circuit build timeout. */
+  circuit_build_times_network_check_changed(cbt);
+}
+
+/**
+ * Estimate a new timeout based on history and set our timeout
+ * variable accordingly.
+ */
+static int
+circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
+{
+  build_time_t max_time;
+  if (!circuit_build_times_enough_to_compute(cbt))
+    return 0;
+
+  if (!circuit_build_times_update_alpha(cbt))
+    return 0;
+
+  cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
+                                circuit_build_times_quantile_cutoff());
+
+  cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
+                                circuit_build_times_close_quantile());
+
+  max_time = circuit_build_times_max(cbt);
+
+  /* Sometimes really fast guard nodes give us such a steep curve
+   * that this ends up being not that much greater than timeout_ms.
+   * Make it be at least 1 min to handle this case. */
+  cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout());
+
+  if (cbt->timeout_ms > max_time) {
+    log_info(LD_CIRC,
+               "Circuit build timeout of %dms is beyond the maximum build "
+               "time we have ever observed. Capping it to %dms.",
+               (int)cbt->timeout_ms, max_time);
+    cbt->timeout_ms = max_time;
+  }
+
+  if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
+    log_info(LD_CIRC,
+               "Circuit build measurement period of %dms is more than twice "
+               "the maximum build time we have ever observed. Capping it to "
+               "%dms.", (int)cbt->close_ms, 2*max_time);
+    cbt->close_ms = 2*max_time;
+  }
+
+  cbt->have_computed_timeout = 1;
+  return 1;
+}
+
+/**
+ * Exposed function to compute a new timeout. Dispatches events and
+ * also filters out extremely high timeout values.
+ */
+void
+circuit_build_times_set_timeout(circuit_build_times_t *cbt)
+{
+  long prev_timeout = tor_lround(cbt->timeout_ms/1000);
+  double timeout_rate;
+
+  /*
+   * Just return if we aren't using adaptive timeouts
+   */
+  if (circuit_build_times_disabled())
+    return;
+
+  if (!circuit_build_times_set_timeout_worker(cbt))
+    return;
+
+  if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
+    log_info(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms",
+             cbt->timeout_ms, circuit_build_times_min_timeout());
+    cbt->timeout_ms = circuit_build_times_min_timeout();
+    if (cbt->close_ms < cbt->timeout_ms) {
+      /* This shouldn't happen because of MAX() in timeout_worker above,
+       * but doing it just in case */
+      cbt->close_ms = circuit_build_times_initial_timeout();
+    }
+  }
+
+  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
+
+  timeout_rate = circuit_build_times_timeout_rate(cbt);
+
+  if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) {
+    log_info(LD_CIRC,
+               "Based on %d circuit times, it looks like we don't need to "
+               "wait so long for circuits to finish. We will now assume a "
+               "circuit is too slow to use after waiting %ld seconds.",
+               cbt->total_build_times,
+               tor_lround(cbt->timeout_ms/1000));
+    log_info(LD_CIRC,
+             "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
+             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
+             timeout_rate);
+  } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
+    log_info(LD_CIRC,
+               "Based on %d circuit times, it looks like we need to wait "
+               "longer for circuits to finish. We will now assume a "
+               "circuit is too slow to use after waiting %ld seconds.",
+               cbt->total_build_times,
+               tor_lround(cbt->timeout_ms/1000));
+    log_info(LD_CIRC,
+             "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
+             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
+             timeout_rate);
+  } else {
+    log_info(LD_CIRC,
+             "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f,"
+             " r: %f) based on %d circuit times",
+             tor_lround(cbt->timeout_ms/1000),
+             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
+             cbt->total_build_times);
+  }
+}
+/** 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;
+}
+
diff --git a/src/or/circuitstats.h b/src/or/circuitstats.h
new file mode 100644
index 000000000..efe2799b0
--- /dev/null
+++ b/src/or/circuitstats.h
@@ -0,0 +1,65 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file circuitstats.h
+ * \brief Header file for circuitstats.c
+ **/
+
+#ifndef TOR_CIRCUITSTATS_H
+#define TOR_CIRCUITSTATS_H
+
+extern circuit_build_times_t circ_times;
+
+int circuit_build_times_disabled(void);
+int circuit_build_times_enough_to_compute(circuit_build_times_t *cbt);
+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);
+void circuit_build_times_count_timeout(circuit_build_times_t *cbt,
+                                       int did_onehop);
+int circuit_build_times_count_close(circuit_build_times_t *cbt,
+                                    int did_onehop, time_t start_time);
+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);
+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);
+void circuit_build_times_free_timeouts(circuit_build_times_t *cbt);
+void circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
+                                              networkstatus_t *ns);
+double circuit_build_times_timeout_rate(const circuit_build_times_t *cbt);
+double circuit_build_times_close_rate(const circuit_build_times_t *cbt);
+
+#ifdef CIRCUITSTATS_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, double time_ms);
+int circuit_build_times_update_alpha(circuit_build_times_t *cbt);
+double circuit_build_times_cdf(circuit_build_times_t *cbt, double x);
+void circuitbuild_running_unit_tests(void);
+void circuit_build_times_reset(circuit_build_times_t *cbt);
+
+/* Network liveness functions */
+int circuit_build_times_network_check_changed(circuit_build_times_t *cbt);
+#endif
+
+/* Network liveness functions */
+void circuit_build_times_network_is_live(circuit_build_times_t *cbt);
+int circuit_build_times_network_check_live(circuit_build_times_t *cbt);
+void circuit_build_times_network_circ_success(circuit_build_times_t *cbt);
+
+/* DOCDOC circuit_build_times_get_bw_scale */
+int circuit_build_times_get_bw_scale(networkstatus_t *ns);
+
+#endif
+
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index 4d8906f4f..ded78550f 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -13,11 +13,13 @@
 #include "channel.h"
 #include "circuitbuild.h"
 #include "circuitlist.h"
+#include "circuitstats.h"
 #include "circuituse.h"
 #include "config.h"
 #include "connection.h"
 #include "connection_edge.h"
 #include "control.h"
+#include "entrynodes.h"
 #include "nodelist.h"
 #include "networkstatus.h"
 #include "policies.h"
diff --git a/src/or/config.c b/src/or/config.c
index 30376b86f..da73f783f 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -27,6 +27,7 @@
 #include "dirserv.h"
 #include "dirvote.h"
 #include "dns.h"
+#include "entrynodes.h"x
 #include "geoip.h"
 #include "hibernate.h"
 #include "main.h"
diff --git a/src/or/connection.c b/src/or/connection.c
index b4589bfb0..1fbce418a 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -32,6 +32,7 @@
 #include "dirserv.h"
 #include "dns.h"
 #include "dnsserv.h"
+#include "entrynodes.h"
 #include "geoip.h"
 #include "main.h"
 #include "policies.h"
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 877ddf131..970f55a74 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -21,12 +21,14 @@
 #include "channeltls.h"
 #include "circuitbuild.h"
 #include "circuitlist.h"
+#include "circuitstats.h"
 #include "command.h"
 #include "config.h"
 #include "connection.h"
 #include "connection_or.h"
 #include "control.h"
 #include "dirserv.h"
+#include "entrynodes.h"
 #include "geoip.h"
 #include "main.h"
 #include "networkstatus.h"
diff --git a/src/or/control.c b/src/or/control.c
index 8206699b1..ad2f2788f 100644
--- a/src/or/control.c
+++ b/src/or/control.c
@@ -16,6 +16,7 @@
 #include "channeltls.h"
 #include "circuitbuild.h"
 #include "circuitlist.h"
+#include "circuitstats.h"
 #include "circuituse.h"
 #include "config.h"
 #include "confparse.h"
@@ -26,6 +27,7 @@
 #include "directory.h"
 #include "dirserv.h"
 #include "dnsserv.h"
+#include "entrynodes.h"
 #include "geoip.h"
 #include "hibernate.h"
 #include "main.h"
diff --git a/src/or/directory.c b/src/or/directory.c
index 2f70d1100..2ceeb0bd0 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -13,6 +13,7 @@
 #include "directory.h"
 #include "dirserv.h"
 #include "dirvote.h"
+#include "entrynodes.h"
 #include "geoip.h"
 #include "main.h"
 #include "microdesc.h"
diff --git a/src/or/include.am b/src/or/include.am
index 749206151..01f4784d0 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -23,6 +23,7 @@ src_or_libtor_a_SOURCES = \
 	src/or/circuitlist.c				\
 	src/or/circuitmux.c				\
 	src/or/circuitmux_ewma.c			\
+	src/or/circuitstats.c				\
 	src/or/circuituse.c				\
 	src/or/command.c				\
 	src/or/config.c					\
@@ -38,6 +39,7 @@ src_or_libtor_a_SOURCES = \
 	src/or/dns.c					\
 	src/or/dnsserv.c				\
 	src/or/geoip.c					\
+	src/or/entrynodes.c				\
 	src/or/hibernate.c				\
 	src/or/main.c					\
 	src/or/microdesc.c				\
@@ -96,6 +98,7 @@ ORHEADERS = \
 	src/or/circuitlist.h				\
 	src/or/circuitmux.h				\
 	src/or/circuitmux_ewma.h			\
+	src/or/circuitstats.h				\
 	src/or/circuituse.h				\
 	src/or/command.h				\
 	src/or/config.h					\
@@ -112,6 +115,7 @@ ORHEADERS = \
 	src/or/dnsserv.h				\
 	src/or/eventdns_tor.h				\
 	src/or/geoip.h					\
+	src/or/entrynodes.h				\
 	src/or/hibernate.h				\
 	src/or/main.h					\
 	src/or/microdesc.h				\
diff --git a/src/or/main.c b/src/or/main.c
index adc1f5d98..0ba28db05 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -30,6 +30,7 @@
 #include "dirvote.h"
 #include "dns.h"
 #include "dnsserv.h"
+#include "entrynodes.h"
 #include "geoip.h"
 #include "hibernate.h"
 #include "main.h"
diff --git a/src/or/microdesc.c b/src/or/microdesc.c
index 4abfe9c9b..42a35f067 100644
--- a/src/or/microdesc.c
+++ b/src/or/microdesc.c
@@ -6,6 +6,7 @@
 #include "config.h"
 #include "directory.h"
 #include "dirserv.h"
+#include "entrynodes.h"
 #include "microdesc.h"
 #include "networkstatus.h"
 #include "nodelist.h"
diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c
index b27d5354d..89afb5a5c 100644
--- a/src/or/networkstatus.c
+++ b/src/or/networkstatus.c
@@ -12,9 +12,9 @@
 
 #include "or.h"
 #include "channel.h"
-#include "circuitbuild.h"
 #include "circuitmux.h"
 #include "circuitmux_ewma.h"
+#include "circuitstats.h"
 #include "config.h"
 #include "connection.h"
 #include "connection_or.h"
@@ -22,6 +22,7 @@
 #include "directory.h"
 #include "dirserv.h"
 #include "dirvote.h"
+#include "entrynodes.h"
 #include "main.h"
 #include "microdesc.h"
 #include "networkstatus.h"
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 07f69c243..8c831496c 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -13,13 +13,14 @@
 
 #define ROUTERLIST_PRIVATE
 #include "or.h"
-#include "circuitbuild.h"
+#include "circuitstats.h"
 #include "config.h"
 #include "connection.h"
 #include "control.h"
 #include "directory.h"
 #include "dirserv.h"
 #include "dirvote.h"
+#include "entrynodes.h"
 #include "geoip.h"
 #include "hibernate.h"
 #include "main.h"
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 25c7b15b4..8d6cd1c7f 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -11,7 +11,7 @@
 
 #include "or.h"
 #include "config.h"
-#include "circuitbuild.h"
+#include "circuitstats.h"
 #include "dirserv.h"
 #include "dirvote.h"
 #include "policies.h"
diff --git a/src/or/statefile.c b/src/or/statefile.c
index 97200f17b..beb9cf81b 100644
--- a/src/or/statefile.c
+++ b/src/or/statefile.c
@@ -5,9 +5,10 @@
 /* See LICENSE for licensing information */
 
 #include "or.h"
-#include "circuitbuild.h"
+#include "circuitstats.h"
 #include "config.h"
 #include "confparse.h"
+#include "entrynodes.h"
 #include "hibernate.h"
 #include "rephist.h"
 #include "router.h"
diff --git a/src/test/test.c b/src/test/test.c
index bbe63d904..c84aafc75 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -32,7 +32,7 @@ const char tor_git_revision[] = "";
 #define CONFIG_PRIVATE
 #define GEOIP_PRIVATE
 #define ROUTER_PRIVATE
-#define CIRCUIT_PRIVATE
+#define CIRCUITSTATS_PRIVATE
 
 /*
  * Linux doesn't provide lround in math.h by default, but mac os does...
@@ -44,7 +44,7 @@ double fabs(double x);
 
 #include "or.h"
 #include "buffers.h"
-#include "circuitbuild.h"
+#include "circuitstats.h"
 #include "config.h"
 #include "connection_edge.h"
 #include "geoip.h"