[tor/release-0.2.2] Merge remote branch 'origin/maint-0.2.1' into maint-0.2.2

8 Mar 2011

commit 9ad083d5731c983ea3e961822306c50ce32dfcc2
Merge: 95edd51 9a6df21
Author: Nick Mathewson <nickm@torproject.org>
Date:   Tue Mar 8 15:20:48 2011 -0500

    Merge remote branch 'origin/maint-0.2.1' into maint-0.2.2

 changes/bug2629       |    5 +++++
 src/or/circuitbuild.c |    3 ++-
 2 files changed, 7 insertions(+), 1 deletions(-)

diff --combined src/or/circuitbuild.c
index b3c9f0e,76713e6..6be27d2

--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@@ -9,1437 -9,55 +9,1437 @@@
   * \brief The actual details of building circuits.
   **/
  
 +#define CIRCUIT_PRIVATE
 +
  #include "or.h"
 +#include "circuitbuild.h"
 +#include "circuitlist.h"
 +#include "circuituse.h"
 +#include "config.h"
 +#include "connection.h"
 +#include "connection_edge.h"
 +#include "connection_or.h"
 +#include "control.h"
 +#include "directory.h"
 +#include "main.h"
 +#include "networkstatus.h"
 +#include "onion.h"
 +#include "policies.h"
 +#include "relay.h"
 +#include "rephist.h"
 +#include "router.h"
 +#include "routerlist.h"
 +#include "routerparse.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 */
 +// FIXME: Add this as a member for entry_guard_t instead of global?
 +// Then we could do per-guard statistics, as guards are likely to
 +// vary in their own latency. The downside of this is that guards
 +// can change frequently, so we'd be building a lot more circuits
 +// most likely.
 +circuit_build_times_t circ_times;
 +
 +/** A global list of all circuits at this hop. */
 +extern circuit_t *global_circuitlist;
 +
 +/** 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 routerinfo_t, since we want to remember these even when we
 + * don't have a directory. */
 +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?*/
 +  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. */
 +} entry_guard_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 int circuit_deliver_create_cell(circuit_t *circ,
 +                                       uint8_t cell_type, const char *payload);
 +static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
 +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_routers(smartlist_t *routers);
 +static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
 +
 +static void entry_guards_changed(void);
 +
 +/**
 + * 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 = (get_or_state()->LastWritten == -1);
 +
 +    if (consensus_disabled || config_disabled || dirauth_disabled ||
 +           state_disabled) {
 +      log_info(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 {
 +      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)
 +{
 +  return networkstatus_get_param(NULL, "cbtmaxtimeouts",
 +                                 CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT,
 +                                 CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
 +                                 CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);
 +}
 +
 +/**
 + * 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);
 +  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);
 +  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);
 +  return num/100.0;
 +}
 +
 +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 (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);
 +  return num;
 +}
 +
 +/**
 + * Retrieve and bounds-check the cbtmintimeout consensus paramter.
 + *
 + * 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);
 +  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 (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)
 +{
 +  return networkstatus_get_param(ns, "cbtrecentcount",
 +                                 CBT_DEFAULT_RECENT_CIRCUITS,
 +                                 CBT_MIN_RECENT_CIRCUITS,
 +                                 CBT_MAX_RECENT_CIRCUITS);
 +}
 +
 +/**
 + * 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 = circuit_build_times_recent_circuit_count(ns);
 +
 +  if (num > 0 && 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);
 +
 +    /*
 +     * 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);
 +    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;
 +  }
 +}
 +
 +/** 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;
 +  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();
 +  }
 +  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));
 +  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);
 +  cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
 +  control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
 +}
 +
 +#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</a> 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=3 most frequent build time bins.
 + */
 +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();
 +
 +  // 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));
 +
 +  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]]);
 +  }
 +
 +  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");
 +    line->value = tor_malloc(25);
 +    tor_snprintf(line->value, 25, "%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.
 + *
 + * Stolen from http://en.wikipedia.org/wiki/Fisher\u2013Yates_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 "
 +               "%d to %d.", num_times, CBT_NCIRCUITS_TO_OBSERVE);
 +  }
 +
 +  /* 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_create();
 +    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)
 +{
 +  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)
 +{
 +  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;
 +  }
 +}
  
 -/********* START VARIABLES **********/
 +/**
 + * 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);
 +    }
 +  }
 +}
  
 -/** A global list of all circuits at this hop. */
 -extern circuit_t *global_circuitlist;
 +/**
 + * 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;
 +  }
  
 -/** 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 routerinfo_t, since we want to remember these even when we
 - * don't have a directory. */
 -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?*/
 -  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. */
 -} entry_guard_t;
 +  return 1;
 +}
  
 -/** 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;
 +/**
 + * 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;
  
 -/********* END VARIABLES ************/
 +  /* 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];
 +  }
  
 -static int circuit_deliver_create_cell(circuit_t *circ,
 -                                       uint8_t cell_type, const char *payload);
 -static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
 -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_routers(smartlist_t *routers);
 -static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
 +  /* 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;
 +  }
  
 -static void entry_guards_changed(void);
 +  circuit_build_times_reset(cbt);
 +  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 = %lfmsec, close = %lfmsec)",
 +               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_notice(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;
 +
 +  if (!circuit_build_times_set_timeout_worker(cbt))
 +    return;
 +
 +  if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
 +    log_warn(LD_CIRC, "Set buildtimeout to low value %lfms. 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_notice(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: %lfms, %lfms, Xm: %d, a: %lf, r: %lf",
 +             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
 +             timeout_rate);
 +  } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
 +    log_notice(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: %lfms, %lfms, Xm: %d, a: %lf, r: %lf",
 +             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
 +             timeout_rate);
 +  } else {
 +    log_info(LD_CIRC,
 +             "Set circuit build timeout to %lds (%lfms, %lfms, Xm: %d, a: %lf,"
 +             " r: %lf) 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
@@@ -1494,21 -112,21 +1494,21 @@@ circuit_list_path_impl(origin_circuit_
    crypt_path_t *hop;
    smartlist_t *elements;
    const char *states[] = {"closed", "waiting for keys", "open"};
 -  char buf[128];
    char *s;
  
    elements = smartlist_create();
  
    if (verbose) {
      const char *nickname = build_state_get_exit_nickname(circ->build_state);
 -    tor_snprintf(buf, sizeof(buf), "%s%s circ (length %d%s%s):",
 +    char *cp;
 +    tor_asprintf(&cp, "%s%s circ (length %d%s%s):",
                   circ->build_state->is_internal ? "internal" : "exit",
                   circ->build_state->need_uptime ? " (high-uptime)" : "",
                   circ->build_state->desired_path_len,
                   circ->_base.state == CIRCUIT_STATE_OPEN ? "" : ", exit ",
                   circ->_base.state == CIRCUIT_STATE_OPEN ? "" :
                   (nickname?nickname:"*unnamed*"));
 -    smartlist_add(elements, tor_strdup(buf));
 +    smartlist_add(elements, cp);
    }
  
    hop = circ->cpath;
@@@ -1530,7 -148,8 +1530,7 @@@
          router_get_verbose_nickname(elt, ri);
        } else if ((rs = router_get_consensus_status_by_id(id))) {
          routerstatus_get_verbose_nickname(elt, rs);
 -      } else if (hop->extend_info->nickname &&
 -                 is_legal_nickname(hop->extend_info->nickname)) {
 +      } else if (is_legal_nickname(hop->extend_info->nickname)) {
          elt[0] = '$';
          base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
          elt[HEX_DIGEST_LEN+1]= '~';
@@@ -1598,7 -217,7 +1598,7 @@@ voi
  circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
  {
    char *s = circuit_list_path(circ,1);
 -  log(severity,domain,"%s",s);
 +  tor_log(severity,domain,"%s",s);
    tor_free(s);
  }
  
@@@ -1650,7 -269,7 +1650,7 @@@ static in
  onion_populate_cpath(origin_circuit_t *circ)
  {
    int r;
 -again:
 + again:
    r = onion_extend_cpath(circ);
    if (r < 0) {
      log_info(LD_CIRC,"Generating cpath hop failed.");
@@@ -1742,10 -361,9 +1742,10 @@@ circuit_handle_first_hop(origin_circuit
  
    if (!n_conn) {
      /* not currently connected in a useful way. */
 -    const char *name = firsthop->extend_info->nickname ?
 +    const char *name = strlen(firsthop->extend_info->nickname) ?
        firsthop->extend_info->nickname : fmt_addr(&firsthop->extend_info->addr);
 -    log_info(LD_CIRC, "Next router is %s: %s ", safe_str(name), msg?msg:"???");
 +    log_info(LD_CIRC, "Next router is %s: %s ",
 +             safe_str_client(name), msg?msg:"???");
      circ->_base.n_hop = extend_info_dup(firsthop->extend_info);
  
      if (should_launch) {
@@@ -1888,8 -506,7 +1888,8 @@@ circuit_deliver_create_cell(circuit_t *
    cell.circ_id = circ->n_circ_id;
  
    memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN);
 -  append_cell_to_circuit_queue(circ, circ->n_conn, &cell, CELL_DIRECTION_OUT);
 +  append_cell_to_circuit_queue(circ, circ->n_conn, &cell,
 +                               CELL_DIRECTION_OUT, 0);
  
    if (CIRCUIT_IS_ORIGIN(circ)) {
      /* mark it so it gets better rate limiting treatment. */
@@@ -1919,7 -536,7 +1919,7 @@@ inform_testing_reachability(void
                                  "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
                                  me->address, me->dir_port);
    }
 -  log(LOG_NOTICE, LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
 +  log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
                           "(this may take up to %d minutes -- look for log "
                           "messages indicating success)",
        me->address, me->or_port,
@@@ -1952,18 -569,6 +1952,18 @@@ should_use_create_fast_for_circuit(orig
    return 1;
  }
  
 +/** Return true if <b>circ</b> is the type of circuit we want to count
 + * timeouts from. In particular, we want it to have not completed yet
 + * (already completing indicates we cannibalized it), and we want it to
 + * have exactly three hops.
 + */
 +int
 +circuit_timeout_want_to_count_circ(origin_circuit_t *circ)
 +{
 +  return !circ->has_opened
 +          && circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN;
 +}
 +
  /** This is the backbone function for building circuits.
   *
   * If circ's first hop is closed, then we need to build a create
@@@ -2037,42 -642,15 +2037,42 @@@ circuit_send_next_onion_skin(origin_cir
      if (!hop) {
        /* done building the circuit. whew. */
        circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
 +      if (circuit_timeout_want_to_count_circ(circ)) {
 +        struct timeval end;
 +        long timediff;
 +        tor_gettimeofday(&end);
 +        timediff = tv_mdiff(&circ->_base.highres_created, &end);
 +
 +        /*
 +         * If the circuit build time is much greater than we would have cut
 +         * it off at, we probably had a suspend event along this codepath,
 +         * and we should discard the value.
 +         */
 +        if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) {
 +          log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. "
 +                              "Assuming clock jump. Purpose %d", timediff,
 +                              circ->_base.purpose);
 +        } else if (!circuit_build_times_disabled()) {
 +          /* Only count circuit times if the network is live */
 +          if (circuit_build_times_network_check_live(&circ_times)) {
 +            circuit_build_times_add_time(&circ_times, (build_time_t)timediff);
 +            circuit_build_times_set_timeout(&circ_times);
 +          }
 +
 +          if (circ->_base.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
 +            circuit_build_times_network_circ_success(&circ_times);
 +          }
 +        }
 +      }
        log_info(LD_CIRC,"circuit built!");
        circuit_reset_failure_count(0);
        if (circ->build_state->onehop_tunnel)
          control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
 -      if (!has_completed_circuit && !circ->build_state->onehop_tunnel) {
 +      if (!can_complete_circuit && !circ->build_state->onehop_tunnel) {
          or_options_t *options = get_options();
 -        has_completed_circuit=1;
 +        can_complete_circuit=1;
          /* FFFF Log a count of known routers here */
 -        log(LOG_NOTICE, LD_GENERAL,
 +        log_notice(LD_GENERAL,
              "Tor has successfully opened a circuit. "
              "Looks like client functionality is working.");
          control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0);
@@@ -2084,10 -662,6 +2084,10 @@@
        }
        circuit_rep_hist_note_result(circ);
        circuit_has_opened(circ); /* do other actions as necessary */
 +
 +      /* We're done with measurement circuits here. Just close them */
 +      if (circ->_base.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT)
 +        circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
        return 0;
      }
  
@@@ -2131,13 -705,13 +2131,13 @@@ voi
  circuit_note_clock_jumped(int seconds_elapsed)
  {
    int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
 -  log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; "
 +  tor_log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; "
        "assuming established circuits no longer work.",
        seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed,
        seconds_elapsed >=0 ? "forward" : "backward");
    control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d",
                                 seconds_elapsed);
 -  has_completed_circuit=0; /* so it'll log when it works again */
 +  can_complete_circuit=0; /* so it'll log when it works again */
    control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
                                "CLOCK_JUMPED");
    circuit_mark_all_unused_circs();
@@@ -2370,9 -944,10 +2370,9 @@@ circuit_finish_handshake(origin_circuit
      return -END_CIRC_REASON_TORPROTOCOL;
    }
  
 -  if (hop->dh_handshake_state) {
 -    crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */
 -    hop->dh_handshake_state = NULL;
 -  }
 +  crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */
 +  hop->dh_handshake_state = NULL;
 +
    memset(hop->fast_handshake_state, 0, sizeof(hop->fast_handshake_state));
  
    if (circuit_init_cpath_crypto(hop, keys, 0)<0) {
@@@ -2460,8 -1035,8 +2460,8 @@@ onionskin_answer(or_circuit_t *circ, ui
           cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2);
  
    log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.",
 -            (unsigned int)*(uint32_t*)(keys),
 -            (unsigned int)*(uint32_t*)(keys+20));
 +            (unsigned int)get_uint32(keys),
 +            (unsigned int)get_uint32(keys+20));
    if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) {
      log_warn(LD_BUG,"Circuit initialization failed");
      tor_free(tmp_cpath);
@@@ -2482,7 -1057,7 +2482,7 @@@
    circ->is_first_hop = (cell_type == CELL_CREATED_FAST);
  
    append_cell_to_circuit_queue(TO_CIRCUIT(circ),
 -                               circ->p_conn, &cell, CELL_DIRECTION_IN);
 +                               circ->p_conn, &cell, CELL_DIRECTION_IN, 0);
    log_debug(LD_CIRC,"Finished sending 'created' cell.");
  
    if (!is_local_addr(&circ->p_conn->_base.addr) &&
@@@ -2511,7 -1086,7 +2511,7 @@@ new_route_len(uint8_t purpose, extend_i
  
    tor_assert(routers);
  
 -  routelen = 3;
 +  routelen = DEFAULT_ROUTE_LEN;
    if (exit &&
        purpose != CIRCUIT_PURPOSE_TESTING &&
        purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
@@@ -2576,8 -1151,6 +2576,8 @@@ circuit_all_predicted_ports_handled(tim
    smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
    tor_assert(need_uptime);
    tor_assert(need_capacity);
 +  // Always predict need_capacity
 +  *need_capacity = 1;
    enough = (smartlist_len(sl) == 0);
    for (i = 0; i < smartlist_len(sl); ++i) {
      port = smartlist_get(sl, i);
@@@ -2600,8 -1173,6 +2600,8 @@@ router_handles_some_port(routerinfo_t *
  
    for (i = 0; i < smartlist_len(needed_ports); ++i) {
      addr_policy_result_t r;
 +    /* alignment issues aren't a worry for this dereference, since
 +       needed_ports is explicitly a smartlist of uint16_t's */
      port = *(uint16_t *)smartlist_get(needed_ports, i);
      tor_assert(port);
      r = compare_addr_to_addr_policy(0, port, router->exit_policy);
@@@ -2684,16 -1255,9 +2684,16 @@@ choose_good_exit_server_general(routerl
        n_supported[i] = -1;
        continue; /* skip routers that are known to be down or bad exits */
      }
 -    if (router_is_unreliable(router, need_uptime, need_capacity, 0)) {
 +    if (router_is_unreliable(router, need_uptime, need_capacity, 0) &&
 +        (!options->ExitNodes ||
 +         !routerset_contains_router(options->ExitNodes, router))) {
 +      /* FFFF Someday, differentiate between a routerset that names
 +       * routers, and a routerset that names countries, and only do this
 +       * check if they've asked for specific exit relays. Or if the country
 +       * they ask for is rare. Or something. */
        n_supported[i] = -1;
 -      continue; /* skip routers that are not suitable */
 +      continue; /* skip routers that are not suitable, unless we have
 +                 * ExitNodes set, in which case we asked for it */
      }
      if (!(router->is_valid || options->_AllowInvalid & ALLOW_INVALID_EXIT)) {
        /* if it's invalid and we don't want it */
@@@ -2718,7 -1282,7 +2718,7 @@@
      {
        if (!ap_stream_wants_exit_attention(conn))
          continue; /* Skip everything but APs in CIRCUIT_WAIT */
 -      if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), router)) {
 +      if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), router, 1)) {
          ++n_supported[i];
  //        log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
  //               router->nickname, i, n_supported[i]);
@@@ -2760,8 -1324,7 +2760,8 @@@
  
      routersets_get_disjunction(use, supporting, options->ExitNodes,
                                 options->_ExcludeExitNodesUnion, 1);
 -    if (smartlist_len(use) == 0 && !options->StrictExitNodes) {
 +    if (smartlist_len(use) == 0 && options->ExitNodes &&
 +        !options->StrictNodes) { /* give up on exitnodes and try again */
        routersets_get_disjunction(use, supporting, NULL,
                                   options->_ExcludeExitNodesUnion, 1);
      }
@@@ -2773,7 -1336,7 +2773,7 @@@
       * possibly support any of them.  Choose a router at random that satisfies
       * at least one predicted exit port. */
  
 -    int try;
 +    int attempt;
      smartlist_t *needed_ports, *supporting, *use;
  
      if (best_support == -1) {
@@@ -2786,20 -1349,19 +2786,20 @@@
          tor_free(n_supported);
          return choose_good_exit_server_general(dir, 0, 0);
        }
 -      log_notice(LD_CIRC, "All routers are down or won't exit -- choosing a "
 -                 "doomed exit at random.");
 +      log_notice(LD_CIRC, "All routers are down or won't exit%s -- "
 +                 "choosing a doomed exit at random.",
 +                 options->_ExcludeExitNodesUnion ? " or are Excluded" : "");
      }
      supporting = smartlist_create();
      use = smartlist_create();
      needed_ports = circuit_get_unhandled_ports(time(NULL));
 -    for (try = 0; try < 2; try++) {
 +    for (attempt = 0; attempt < 2; attempt++) {
        /* try once to pick only from routers that satisfy a needed port,
         * then if there are none, pick from any that support exiting. */
        for (i = 0; i < smartlist_len(dir->routers); i++) {
          router = smartlist_get(dir->routers, i);
          if (n_supported[i] != -1 &&
 -            (try || router_handles_some_port(router, needed_ports))) {
 +            (attempt || router_handles_some_port(router, needed_ports))) {
  //          log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
  //                 try, router->nickname);
            smartlist_add(supporting, router);
@@@ -2808,14 -1370,12 +2808,14 @@@
  
        routersets_get_disjunction(use, supporting, options->ExitNodes,
                                   options->_ExcludeExitNodesUnion, 1);
 -      if (smartlist_len(use) == 0 && !options->StrictExitNodes) {
 +      if (smartlist_len(use) == 0 && options->ExitNodes &&
 +          !options->StrictNodes) { /* give up on exitnodes and try again */
          routersets_get_disjunction(use, supporting, NULL,
                                     options->_ExcludeExitNodesUnion, 1);
        }
 -      /* XXX sometimes the above results in null, when the requested
 -       * exit node is down. we should pick it anyway. */
 +      /* FFF sometimes the above results in null, when the requested
 +       * exit node is considered down by the consensus. we should pick
 +       * it anyway, since the user asked for it. */
        router = routerlist_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT);
        if (router)
          break;
@@@ -2833,10 -1393,10 +2833,10 @@@
      log_info(LD_CIRC, "Chose exit server '%s'", router->nickname);
      return router;
    }
 -  if (options->StrictExitNodes) {
 +  if (options->ExitNodes && options->StrictNodes) {
      log_warn(LD_CIRC,
               "No specified exit routers seem to be running, and "
 -             "StrictExitNodes is set: can't choose an exit.");
 +             "StrictNodes is set: can't choose an exit.");
    }
    return NULL;
  }
@@@ -2867,13 -1427,15 +2867,13 @@@ choose_good_exit_server(uint8_t purpose
        if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
          flags |= CRN_ALLOW_INVALID;
        if (is_internal) /* pick it like a middle hop */
 -        return router_choose_random_node(NULL, NULL,
 -                                         options->ExcludeNodes, flags);
 +        return router_choose_random_node(NULL, options->ExcludeNodes, flags);
        else
          return choose_good_exit_server_general(dir,need_uptime,need_capacity);
      case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
        if (options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS)
          flags |= CRN_ALLOW_INVALID;
 -      return router_choose_random_node(NULL, NULL,
 -                                       options->ExcludeNodes, flags);
 +      return router_choose_random_node(NULL, options->ExcludeNodes, flags);
    }
    log_warn(LD_BUG,"Unhandled purpose %d", purpose);
    tor_fragile_assert();
@@@ -2993,7 -1555,8 +2993,7 @@@ circuit_append_new_exit(origin_circuit_
  
    state = circ->build_state;
    tor_assert(state);
 -  if (state->chosen_exit)
 -    extend_info_free(state->chosen_exit);
 +  extend_info_free(state->chosen_exit);
    state->chosen_exit = extend_info_dup(exit);
  
    ++circ->build_state->desired_path_len;
@@@ -3115,7 -1678,8 +3115,7 @@@ choose_good_middle_server(uint8_t purpo
      flags |= CRN_NEED_CAPACITY;
    if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE)
      flags |= CRN_ALLOW_INVALID;
 -  choice = router_choose_random_node(NULL,
 -                                     excluded, options->ExcludeNodes, flags);
 +  choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
    smartlist_free(excluded);
    return choice;
  }
@@@ -3179,7 -1743,11 +3179,7 @@@ choose_good_entry_server(uint8_t purpos
    if (options->_AllowInvalid & ALLOW_INVALID_ENTRY)
      flags |= CRN_ALLOW_INVALID;
  
 -  choice = router_choose_random_node(
 -           NULL,
 -           excluded,
 -           options->ExcludeNodes,
 -           flags);
 +  choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
    smartlist_free(excluded);
    return choice;
  }
@@@ -3300,9 -1868,9 +3300,9 @@@ extend_info_from_router(routerinfo_t *r
  void
  extend_info_free(extend_info_t *info)
  {
 -  tor_assert(info);
 -  if (info->onion_key)
 -    crypto_free_pk_env(info->onion_key);
 +  if (!info)
 +    return;
 +  crypto_free_pk_env(info->onion_key);
    tor_free(info);
  }
  
@@@ -3361,6 -1929,8 +3361,6 @@@ entry_guard_set_status(entry_guard_t *e
    char buf[HEX_DIGEST_LEN+1];
    int changed = 0;
  
 -  tor_assert(options);
 -
    *reason = NULL;
  
    /* Do we want to mark this guard as bad? */
@@@ -3423,58 -1993,35 +3423,58 @@@ entry_is_time_to_retry(entry_guard_t *e
   * - 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>;
 - *   (This check is currently redundant with the Guard flag, but in
 - *   the future that might change. Best to leave it in for now.)
 + *   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 assume_reachable
 + * - 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 routerinfo_t *
  entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity,
 -              int assume_reachable)
 +              int assume_reachable, const char **msg)
  {
    routerinfo_t *r;
 -  if (e->bad_since)
 +  or_options_t *options = get_options();
 +  tor_assert(msg);
 +
 +  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)))
 +      e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) {
 +    *msg = "unreachable";
      return NULL;
 +  }
    r = router_get_by_digest(e->identity);
 -  if (!r)
 +  if (!r) {
 +    *msg = "no descriptor";
      return NULL;
 -  if (get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_BRIDGE)
 +  }
 +  if (get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_BRIDGE) {
 +    *msg = "not a bridge";
      return NULL;
 -  if (!get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_GENERAL)
 +  }
 +  if (!get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_GENERAL) {
 +    *msg = "not general-purpose";
      return NULL;
 -  if (router_is_unreliable(r, need_uptime, need_capacity, 0))
 +  }
 +  if (options->EntryNodes &&
 +      routerset_contains_router(options->EntryNodes, r)) {
 +    /* they asked for it, they get it */
 +    need_uptime = need_capacity = 0;
 +  }
 +  if (router_is_unreliable(r, need_uptime, need_capacity, 0)) {
 +    *msg = "not fast/stable";
      return NULL;
 -  if (!fascist_firewall_allows_or(r))
 +  }
 +  if (!fascist_firewall_allows_or(r)) {
 +    *msg = "unreachable by config";
      return NULL;
 +  }
    return r;
  }
  
@@@ -3483,12 -2030,11 +3483,12 @@@ static in
  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))
 +      if (entry_is_live(entry, 0, 1, 0, &msg))
          ++n;
      });
    return n;
@@@ -3512,21 -2058,16 +3512,21 @@@ static voi
  log_entry_guards(int severity)
  {
    smartlist_t *elements = smartlist_create();
 -  char buf[1024];
    char *s;
  
    SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
      {
 -      tor_snprintf(buf, sizeof(buf), "%s (%s%s)",
 -                   e->nickname,
 -                   entry_is_live(e, 0, 1, 0) ? "up " : "down ",
 -                   e->made_contact ? "made-contact" : "never-contacted");
 -      smartlist_add(elements, tor_strdup(buf));
 +      const char *msg = NULL;
 +      char *cp;
 +      if (entry_is_live(e, 0, 1, 0, &msg))
 +        tor_asprintf(&cp, "%s (up %s)",
 +                     e->nickname,
 +                     e->made_contact ? "made-contact" : "never-contacted");
 +      else
 +        tor_asprintf(&cp, "%s (%s, %s)",
 +                     e->nickname, msg,
 +                     e->made_contact ? "made-contact" : "never-contacted");
 +      smartlist_add(elements, cp);
      });
  
    s = smartlist_join_strings(elements, ",", 0, NULL);
@@@ -3550,13 -2091,12 +3550,13 @@@ control_event_guard_deferred(void
     **/
  #if 0
    int n = 0;
 +  const char *msg;
    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)) {
 +      if (entry_is_live(entry, 0, 1, 0, &msg)) {
          if (n++ == options->NumEntryGuards) {
            control_event_guard(entry->nickname, entry->identity, "DEFERRED");
            return;
@@@ -3618,8 -2158,9 +3618,8 @@@ add_an_entry_guard(routerinfo_t *chosen
  /** If the use of entry guards is configured, choose more entry guards
   * until we have enough in the list. */
  static void
 -pick_entry_guards(void)
 +pick_entry_guards(or_options_t *options)
  {
 -  or_options_t *options = get_options();
    int changed = 0;
  
    tor_assert(entry_guards);
@@@ -3641,8 -2182,7 +3641,8 @@@
  static void
  entry_guard_free(entry_guard_t *e)
  {
 -  tor_assert(e);
 +  if (!e)
 +    return;
    tor_free(e->chosen_by_version);
    tor_free(e);
  }
@@@ -3651,9 -2191,10 +3651,9 @@@
   * or which was selected by a version of Tor that's known to select
   * entry guards badly. */
  static int
 -remove_obsolete_entry_guards(void)
 +remove_obsolete_entry_guards(time_t now)
  {
    int changed = 0, i;
 -  time_t now = time(NULL);
  
    for (i = 0; i < smartlist_len(entry_guards); ++i) {
      entry_guard_t *entry = smartlist_get(entry_guards, i);
@@@ -3713,10 -2254,11 +3713,10 @@@
   * 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(void)
 +remove_dead_entry_guards(time_t now)
  {
    char dbuf[HEX_DIGEST_LEN+1];
    char tbuf[ISO_TIME_LEN+1];
 -  time_t now = time(NULL);
    int i;
    int changed = 0;
  
@@@ -3751,17 -2293,19 +3751,17 @@@
   * think that things are unlisted.
   */
  void
 -entry_guards_compute_status(void)
 +entry_guards_compute_status(or_options_t *options, time_t now)
  {
 -  time_t now;
    int changed = 0;
    int severity = LOG_DEBUG;
 -  or_options_t *options;
    digestmap_t *reasons;
 +
    if (! entry_guards)
      return;
  
 -  options = get_options();
 -
 -  now = time(NULL);
 +  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)
@@@ -3778,7 -2322,7 +3778,7 @@@
      }
    SMARTLIST_FOREACH_END(entry);
  
 -  if (remove_dead_entry_guards())
 +  if (remove_dead_entry_guards(now))
      changed = 1;
  
    severity = changed ? LOG_DEBUG : LOG_INFO;
@@@ -3786,16 -2330,13 +3786,16 @@@
    if (changed) {
      SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) {
        const char *reason = digestmap_get(reasons, entry->identity);
 -      log_info(LD_CIRC, "Summary: Entry '%s' is %s, %s%s%s, and %s.",
 +      const char *live_msg = "";
 +      routerinfo_t *r = entry_is_live(entry, 0, 1, 0, &live_msg);
 +      log_info(LD_CIRC, "Summary: Entry '%s' is %s, %s%s%s, and %s%s.",
                 entry->nickname,
                 entry->unreachable_since ? "unreachable" : "reachable",
                 entry->bad_since ? "unusable" : "usable",
                 reason ? ", ": "",
                 reason ? reason : "",
 -               entry_is_live(entry, 0, 1, 0) ? "live" : "not live");
 +               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));
@@@ -3866,7 -2407,6 +3866,7 @@@ entry_guard_register_connect_status(con
                 "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);
@@@ -3903,8 -2443,7 +3903,8 @@@
          if (e == entry)
            break;
          if (e->made_contact) {
 -          routerinfo_t *r = entry_is_live(e, 0, 1, 1);
 +          const char *msg;
 +          routerinfo_t *r = entry_is_live(e, 0, 1, 1, &msg);
            if (r && e->unreachable_since) {
              refuse_conn = 1;
              e->can_retry = 1;
@@@ -3935,16 -2474,16 +3935,16 @@@ static int should_add_entry_nodes = 0
  void
  entry_nodes_should_be_added(void)
  {
 -  log_info(LD_CIRC, "New EntryNodes config option detected. Will use.");
 +  log_info(LD_CIRC, "EntryNodes config option set. Putting configured "
 +           "relays at the front of the entry guard list.");
    should_add_entry_nodes = 1;
  }
  
  /** Add all nodes in EntryNodes that aren't currently guard nodes to the list
   * of guard nodes, at the front. */
  static void
 -entry_guards_prepend_from_config(void)
 +entry_guards_prepend_from_config(or_options_t *options)
  {
 -  or_options_t *options = get_options();
    smartlist_t *entry_routers, *entry_fps;
    smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list;
    tor_assert(entry_guards);
@@@ -3959,7 -2498,7 +3959,7 @@@
      return;
    }
  
 -  if (options->EntryNodes) {
 +  {
      char *string = routerset_to_string(options->EntryNodes);
      log_info(LD_CIRC,"Adding configured EntryNodes '%s'.", string);
      tor_free(string);
@@@ -4003,9 -2542,8 +4003,9 @@@
    SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, {
      add_an_entry_guard(ri, 0);
    });
 -  /* Finally, the remaining EntryNodes, unless we're strict */
 -  if (options->StrictEntryNodes) {
 +  /* Finally, the remaining previously configured guards that are not in
 +   * EntryNodes, unless we're strict in which case we drop them */
 +  if (options->StrictNodes) {
      SMARTLIST_FOREACH(old_entry_guards_not_on_list, entry_guard_t *, e,
                        entry_guard_free(e));
    } else {
@@@ -4019,30 -2557,16 +4019,30 @@@
    entry_guards_changed();
  }
  
 -/** Return 1 if we're fine adding arbitrary routers out of the
 - * directory to our entry guard list. Else return 0. */
 +/** 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'd prefer to stick to it.
 + */
  int
 -entry_list_can_grow(or_options_t *options)
 +entry_list_is_constrained(or_options_t *options)
  {
 -  if (options->StrictEntryNodes)
 -    return 0;
 +  if (options->EntryNodes)
 +    return 1;
    if (options->UseBridges)
 -    return 0;
 -  return 1;
 +    return 1;
 +  return 0;
 +}
 +
 +/* Are we dead set against changing our entry guard list, or would we
 + * change it if it means keeping Tor usable? */
 +static int
 +entry_list_is_totally_static(or_options_t *options)
 +{
 +  if (options->EntryNodes && options->StrictNodes)
 +    return 1;
 +  if (options->UseBridges)
 +    return 1;
 +  return 0;
  }
  
  /** Pick a live (up and listed) entry guard from entry_guards. If
@@@ -4060,9 -2584,10 +4060,9 @@@ choose_random_entry(cpath_build_state_
    routerinfo_t *r = NULL;
    int need_uptime = state ? state->need_uptime : 0;
    int need_capacity = state ? state->need_capacity : 0;
 -  int consider_exit_family = 0;
 +  int preferred_min, consider_exit_family = 0;
  
    if (chosen_exit) {
 -    smartlist_add(exit_family, chosen_exit);
      routerlist_add_family(exit_family, chosen_exit);
      consider_exit_family = 1;
    }
@@@ -4071,64 -2596,38 +4071,64 @@@
      entry_guards = smartlist_create();
  
    if (should_add_entry_nodes)
 -    entry_guards_prepend_from_config();
 +    entry_guards_prepend_from_config(options);
  
 -  if (entry_list_can_grow(options) &&
 -      (! entry_guards ||
 -       smartlist_len(entry_guards) < options->NumEntryGuards))
 -    pick_entry_guards();
 +  if (!entry_list_is_constrained(options) &&
 +      smartlist_len(entry_guards) < options->NumEntryGuards)
 +    pick_entry_guards(options);
  
   retry:
    smartlist_clear(live_entry_guards);
    SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry,
      {
 -      r = entry_is_live(entry, need_uptime, need_capacity, 0);
 -      if (r && (!consider_exit_family || !smartlist_isin(exit_family, r))) {
 -        smartlist_add(live_entry_guards, r);
 -        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;
 +      const char *msg;
 +      r = entry_is_live(entry, need_uptime, need_capacity, 0, &msg);
 +      if (!r)
 +        continue; /* down, no point */
 +      if (r == chosen_exit)
 +        continue; /* don't pick the same node for entry and exit */
 +      if (consider_exit_family && smartlist_isin(exit_family, r))
 +        continue; /* avoid relays that are family members of our exit */
 +      if (options->EntryNodes &&
 +          !routerset_contains_router(options->EntryNodes, r)) {
 +        /* 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_prepend_from_config() drops unwanted relays */
 +          tor_fragile_assert();
 +        } else {
 +          log_info(LD_CIRC,
 +                   "No relays from EntryNodes available. Using others.");
          }
 -        if (smartlist_len(live_entry_guards) >= options->NumEntryGuards)
 -          break; /* we have enough */
        }
 +      smartlist_add(live_entry_guards, r);
 +      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)
 +        break; /* we have enough */
      });
  
 -  /* 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.) */
 -  if (smartlist_len(live_entry_guards) < 2) {
 -    if (entry_list_can_grow(options)) {
 +  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_totally_static(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
@@@ -4153,7 -2652,7 +4153,7 @@@
        need_capacity = 0;
        goto retry;
      }
 -    if (!r && !entry_list_can_grow(options) && consider_exit_family) {
 +    if (!r && 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. */
@@@ -4164,15 -2663,15 +4164,15 @@@
    }
  
   choose_and_finish:
 -  if (entry_list_can_grow(options)) {
 +  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. */
 +    r = routerlist_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. */
      r = smartlist_choose(live_entry_guards);
 -  } else {
 -    /* We need to weight by bandwidth, because our bridges or entryguards
 -     * were not already selected proportional to their bandwidth. */
 -    r = routerlist_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD);
    }
    smartlist_free(live_entry_guards);
    smartlist_free(exit_family);
@@@ -4306,7 -2805,7 +4306,7 @@@ entry_guards_parse_state(or_state_t *st
      entry_guards_dirty = 0;
      /* XXX022 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())
 +    if (remove_obsolete_entry_guards(now))
        entry_guards_dirty = 1;
    }
    digestmap_free(added_by, _tor_free);
@@@ -4405,11 -2904,9 +4405,11 @@@ entry_guards_update_state(or_state_t *s
   * */
  int
  getinfo_helper_entry_guards(control_connection_t *conn,
 -                            const char *question, char **answer)
 +                            const char *question, char **answer,
 +                            const char **errmsg)
  {
 -  int use_long_names = conn->use_long_names;
 +  (void) conn;
 +  (void) errmsg;
  
    if (!strcmp(question,"entry-guards") ||
        !strcmp(question,"helper-nodes")) {
@@@ -4418,13 -2915,12 +4418,13 @@@
      char nbuf[MAX_VERBOSE_NICKNAME_LEN+1];
      if (!entry_guards)
        entry_guards = smartlist_create();
 -    SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
 -      {
 +    SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) {
          size_t len = MAX_VERBOSE_NICKNAME_LEN+ISO_TIME_LEN+32;
          char *c = tor_malloc(len);
          const char *status = NULL;
          time_t when = 0;
 +        routerinfo_t *ri;
 +
          if (!e->made_contact) {
            status = "never-connected";
          } else if (e->bad_since) {
@@@ -4433,17 -2929,19 +4433,17 @@@
          } else {
            status = "up";
          }
 -        if (use_long_names) {
 -          routerinfo_t *ri = router_get_by_digest(e->identity);
 -          if (ri) {
 -            router_get_verbose_nickname(nbuf, ri);
 -          } 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. */
 -          }
 +
 +        ri = router_get_by_digest(e->identity);
 +        if (ri) {
 +          router_get_verbose_nickname(nbuf, ri);
          } else {
 -          base16_encode(nbuf, sizeof(nbuf), e->identity, DIGEST_LEN);
 +          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);
            tor_snprintf(c, len, "%s %s %s\n", nbuf, status, tbuf);
@@@ -4451,7 -2949,7 +4451,7 @@@
            tor_snprintf(c, len, "%s %s\n", nbuf, status);
          }
          smartlist_add(sl, c);
 -      });
 +    } SMARTLIST_FOREACH_END(e);
      *answer = smartlist_join_strings(sl, "", 0, NULL);
      SMARTLIST_FOREACH(sl, char *, c, tor_free(c));
      smartlist_free(sl);
@@@ -4492,56 -2990,29 +4492,56 @@@ clear_bridge_list(void
   * (either by comparing keys if possible, else by comparing addr/port).
   * Else return NULL. */
  static bridge_info_t *
 -routerinfo_get_configured_bridge(routerinfo_t *ri)
 +get_configured_bridge_by_addr_port_digest(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_eq_ipv4h(&bridge->addr, ri->addr) &&
 -          bridge->port == ri->or_port)
 +          !tor_addr_compare(&bridge->addr, addr, CMP_EXACT) &&
 +          bridge->port == port)
          return bridge;
 -      if (!memcmp(bridge->identity, ri->cache_info.identity_digest,
 -                  DIGEST_LEN))
 +      if (!memcmp(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(routerinfo_t *ri)
 +{
 +  tor_addr_t addr;
 +  tor_addr_from_ipv4h(&addr, ri->addr);
 +  return get_configured_bridge_by_addr_port_digest(&addr,
 +                              ri->or_port, ri->cache_info.identity_digest);
 +}
 +
  /** Return 1 if <b>ri</b> is one of our known bridges, else 0. */
  int
  routerinfo_is_a_configured_bridge(routerinfo_t *ri)
  {
 -  return routerinfo_get_configured_bridge(ri) ? 1 : 0;
 +  return get_configured_bridge_by_routerinfo(ri) ? 1 : 0;
 +}
 +
 +/** 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(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:%d",
 +               hex_str(digest, DIGEST_LEN), fmt_addr(addr), port);
 +  }
  }
  
  /** Remember a new bridge at <b>addr</b>:<b>port</b>. If <b>digest</b>
@@@ -4611,8 -3082,9 +4611,8 @@@ retry_bridge_descriptor_fetch_directly(
   * descriptor, fetch a new copy of its descriptor -- either directly
   * from the bridge or via a bridge authority. */
  void
 -fetch_bridge_descriptors(time_t now)
 +fetch_bridge_descriptors(or_options_t *options, time_t now)
  {
 -  or_options_t *options = get_options();
    int num_bridge_auths = get_n_authorities(BRIDGE_AUTHORITY);
    int ask_bridge_directly;
    int can_use_bridge_authority;
@@@ -4680,7 -3152,7 +4680,7 @@@ learned_bridge_descriptor(routerinfo_t 
    tor_assert(ri->purpose == ROUTER_PURPOSE_BRIDGE);
    if (get_options()->UseBridges) {
      int first = !any_bridge_descriptors_known();
 -    bridge_info_t *bridge = routerinfo_get_configured_bridge(ri);
 +    bridge_info_t *bridge = get_configured_bridge_by_routerinfo(ri);
      time_t now = time(NULL);
      ri->is_running = 1;
  
@@@ -4728,7 -3200,8 +4728,8 @@@ any_pending_bridge_descriptor_fetches(v
          conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC &&
          TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE &&
          !conn->marked_for_close &&
-         conn->linked && !conn->linked_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;
      }
@@@ -4736,38 -3209,26 +4737,38 @@@
    return 0;
  }
  
 -/** Return 1 if we have at least one descriptor for a bridge and
 - * all descriptors we know are down. Else return 0. If <b>act</b> is
 - * 1, then mark the down bridges up; else just observe and report. */
 +/** 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
 -bridges_retry_helper(int act)
 +entries_retry_helper(or_options_t *options, int act)
  {
    routerinfo_t *ri;
    int any_known = 0;
    int any_running = 0;
 +  int purpose = options->UseBridges ?
 +                  ROUTER_PURPOSE_BRIDGE : ROUTER_PURPOSE_GENERAL;
    if (!entry_guards)
      entry_guards = smartlist_create();
    SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e,
      {
        ri = router_get_by_digest(e->identity);
 -      if (ri && ri->purpose == ROUTER_PURPOSE_BRIDGE) {
 +      if (ri && ri->purpose == purpose) {
          any_known = 1;
          if (ri->is_running)
 -          any_running = 1; /* some bridge is both known and running */
 -        else if (act) { /* mark it for retry */
 -          ri->is_running = 1;
 +          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(ri->cache_info.identity_digest, 1);
 +
 +          /* mark this entry node for retry */
 +          router_set_status(ri->cache_info.identity_digest, 1);
            e->can_retry = 1;
            e->bad_since = 0;
          }
@@@ -4778,21 -3239,19 +4779,21 @@@
    return any_known && !any_running;
  }
  
 -/** Do we know any descriptors for our bridges, and are they all
 - * down? */
 +/** Do we know any descriptors for our bridges / entrynodes, and are
 + * all the ones we have descriptors for down? */
  int
 -bridges_known_but_down(void)
 +entries_known_but_down(or_options_t *options)
  {
 -  return bridges_retry_helper(0);
 +  tor_assert(entry_list_is_constrained(options));
 +  return entries_retry_helper(options, 0);
  }
  
 -/** Mark all down known bridges up. */
 +/** Mark all down known bridges / entrynodes up. */
  void
 -bridges_retry_all(void)
 +entries_retry_all(or_options_t *options)
  {
 -  bridges_retry_helper(1);
 +  tor_assert(entry_list_is_constrained(options));
 +  entries_retry_helper(options, 1);
  }
  
  /** Release all storage held by the list of entry guards and related

    

arma＠torproject.org

tags

participants (1)