aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorNick Mathewson <nickm@torproject.org>2012-10-15 14:48:34 -0400
committerNick Mathewson <nickm@torproject.org>2012-10-15 14:50:55 -0400
commit907db008ab0007f0a02da62b68130344fc2e9353 (patch)
tree3b6c5afb45b34a855894d50dde2f43737435a95f /src
parent9e9edf71f7d3093b4ac1fe61ccc6dad2976e0a1e (diff)
downloadtor-907db008ab0007f0a02da62b68130344fc2e9353.tar
tor-907db008ab0007f0a02da62b68130344fc2e9353.tar.gz
Move the circuit build timeout code into its own file.
Diffstat (limited to 'src')
-rw-r--r--src/or/channel.c2
-rw-r--r--src/or/circuitbuild.c3502
-rw-r--r--src/or/circuitbuild.h90
-rw-r--r--src/or/circuitlist.c1
-rw-r--r--src/or/circuitstats.c1569
-rw-r--r--src/or/circuitstats.h65
-rw-r--r--src/or/circuituse.c2
-rw-r--r--src/or/config.c1
-rw-r--r--src/or/connection.c1
-rw-r--r--src/or/connection_or.c2
-rw-r--r--src/or/control.c2
-rw-r--r--src/or/directory.c1
-rw-r--r--src/or/include.am4
-rw-r--r--src/or/main.c1
-rw-r--r--src/or/microdesc.c1
-rw-r--r--src/or/networkstatus.c3
-rw-r--r--src/or/routerlist.c3
-rw-r--r--src/or/routerparse.c2
-rw-r--r--src/or/statefile.c3
-rw-r--r--src/test/test.c4
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"