Move pathbias functions into a new file.

Does not compile yet.  This is the "no code changed" diff.

5 files changed, 1527 insertions, 1503 deletions

diff --git a/src/or/circpathbias.c b/src/or/circpathbias.c
new file mode 100644
index 000000000..106337e01
--- /dev/null
+++ b/src/or/circpathbias.c
@@ -0,0 +1,1497 @@
+
+#include "circpathbias.h"
+#include "circuitbuild.h"
+
+static void pathbias_count_build_success(origin_circuit_t *circ);
+static void pathbias_count_successful_close(origin_circuit_t *circ);
+static void pathbias_count_collapse(origin_circuit_t *circ);
+static void pathbias_count_use_failed(origin_circuit_t *circ);
+static void pathbias_measure_use_rate(entry_guard_t *guard);
+static void pathbias_measure_close_rate(entry_guard_t *guard);
+static void pathbias_scale_use_rates(entry_guard_t *guard);
+
+/** The minimum number of circuit attempts before we start
+  * thinking about warning about path bias and dropping guards */
+static int
+pathbias_get_min_circs(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_MIN_CIRC 150
+  if (options->PathBiasCircThreshold >= 5)
+    return options->PathBiasCircThreshold;
+  else
+    return networkstatus_get_param(NULL, "pb_mincircs",
+                                   DFLT_PATH_BIAS_MIN_CIRC,
+                                   5, INT32_MAX);
+}
+
+/** The circuit success rate below which we issue a notice */
+static double
+pathbias_get_notice_rate(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_NOTICE_PCT 70
+  if (options->PathBiasNoticeRate >= 0.0)
+    return options->PathBiasNoticeRate;
+  else
+    return networkstatus_get_param(NULL, "pb_noticepct",
+                                   DFLT_PATH_BIAS_NOTICE_PCT, 0, 100)/100.0;
+}
+
+/* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
+/** The circuit success rate below which we issue a warn */
+static double
+pathbias_get_warn_rate(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_WARN_PCT 50
+  if (options->PathBiasWarnRate >= 0.0)
+    return options->PathBiasWarnRate;
+  else
+    return networkstatus_get_param(NULL, "pb_warnpct",
+                                   DFLT_PATH_BIAS_WARN_PCT, 0, 100)/100.0;
+}
+
+/* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
+/**
+ * The extreme rate is the rate at which we would drop the guard,
+ * if pb_dropguard is also set. Otherwise we just warn.
+ */
+double
+pathbias_get_extreme_rate(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_EXTREME_PCT 30
+  if (options->PathBiasExtremeRate >= 0.0)
+    return options->PathBiasExtremeRate;
+  else
+    return networkstatus_get_param(NULL, "pb_extremepct",
+                                   DFLT_PATH_BIAS_EXTREME_PCT, 0, 100)/100.0;
+}
+
+/* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
+/**
+ * If 1, we actually disable use of guards that fall below
+ * the extreme_pct.
+ */
+int
+pathbias_get_dropguards(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_DROP_GUARDS 0
+  if (options->PathBiasDropGuards >= 0)
+    return options->PathBiasDropGuards;
+  else
+    return networkstatus_get_param(NULL, "pb_dropguards",
+                                   DFLT_PATH_BIAS_DROP_GUARDS, 0, 1);
+}
+
+/**
+ * This is the number of circuits at which we scale our
+ * counts by mult_factor/scale_factor. Note, this count is
+ * not exact, as we only perform the scaling in the event
+ * of no integer truncation.
+ */
+static int
+pathbias_get_scale_threshold(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_SCALE_THRESHOLD 300
+  if (options->PathBiasScaleThreshold >= 10)
+    return options->PathBiasScaleThreshold;
+  else
+    return networkstatus_get_param(NULL, "pb_scalecircs",
+                                   DFLT_PATH_BIAS_SCALE_THRESHOLD, 10,
+                                   INT32_MAX);
+}
+
+/**
+ * Compute the path bias scaling ratio from the consensus
+ * parameters pb_multfactor/pb_scalefactor.
+ *
+ * Returns a value in (0, 1.0] which we multiply our pathbias
+ * counts with to scale them down.
+ */
+static double
+pathbias_get_scale_ratio(const or_options_t *options)
+{
+  /*
+   * The scale factor is the denominator for our scaling
+   * of circuit counts for our path bias window.
+   *
+   * Note that our use of doubles for the path bias state
+   * file means that powers of 2 work best here.
+   */
+  int denominator = networkstatus_get_param(NULL, "pb_scalefactor",
+                              2, 2, INT32_MAX);
+  (void) options;
+  /**
+   * The mult factor is the numerator for our scaling
+   * of circuit counts for our path bias window. It
+   * allows us to scale by fractions.
+   */
+  return networkstatus_get_param(NULL, "pb_multfactor",
+                              1, 1, denominator)/((double)denominator);
+}
+
+/** The minimum number of circuit usage attempts before we start
+  * thinking about warning about path use bias and dropping guards */
+static int
+pathbias_get_min_use(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_MIN_USE 20
+  if (options->PathBiasUseThreshold >= 3)
+    return options->PathBiasUseThreshold;
+  else
+    return networkstatus_get_param(NULL, "pb_minuse",
+                                   DFLT_PATH_BIAS_MIN_USE,
+                                   3, INT32_MAX);
+}
+
+/** The circuit use success rate below which we issue a notice */
+static double
+pathbias_get_notice_use_rate(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_NOTICE_USE_PCT 80
+  if (options->PathBiasNoticeUseRate >= 0.0)
+    return options->PathBiasNoticeUseRate;
+  else
+    return networkstatus_get_param(NULL, "pb_noticeusepct",
+                                   DFLT_PATH_BIAS_NOTICE_USE_PCT,
+                                   0, 100)/100.0;
+}
+
+/**
+ * The extreme use rate is the rate at which we would drop the guard,
+ * if pb_dropguard is also set. Otherwise we just warn.
+ */
+double
+pathbias_get_extreme_use_rate(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_EXTREME_USE_PCT 60
+  if (options->PathBiasExtremeUseRate >= 0.0)
+    return options->PathBiasExtremeUseRate;
+  else
+    return networkstatus_get_param(NULL, "pb_extremeusepct",
+                                   DFLT_PATH_BIAS_EXTREME_USE_PCT,
+                                   0, 100)/100.0;
+}
+
+/**
+ * This is the number of circuits at which we scale our
+ * use counts by mult_factor/scale_factor. Note, this count is
+ * not exact, as we only perform the scaling in the event
+ * of no integer truncation.
+ */
+static int
+pathbias_get_scale_use_threshold(const or_options_t *options)
+{
+#define DFLT_PATH_BIAS_SCALE_USE_THRESHOLD 100
+  if (options->PathBiasScaleUseThreshold >= 10)
+    return options->PathBiasScaleUseThreshold;
+  else
+    return networkstatus_get_param(NULL, "pb_scaleuse",
+                                   DFLT_PATH_BIAS_SCALE_USE_THRESHOLD,
+                                   10, INT32_MAX);
+}
+
+/**
+ * Convert a Guard's path state to string.
+ */
+const char *
+pathbias_state_to_string(path_state_t state)
+{
+  switch (state) {
+    case PATH_STATE_NEW_CIRC:
+      return "new";
+    case PATH_STATE_BUILD_ATTEMPTED:
+      return "build attempted";
+    case PATH_STATE_BUILD_SUCCEEDED:
+      return "build succeeded";
+    case PATH_STATE_USE_ATTEMPTED:
+      return "use attempted";
+    case PATH_STATE_USE_SUCCEEDED:
+      return "use succeeded";
+    case PATH_STATE_USE_FAILED:
+      return "use failed";
+    case PATH_STATE_ALREADY_COUNTED:
+      return "already counted";
+  }
+
+  return "unknown";
+}
+
+/**
+ * This function decides if a circuit has progressed far enough to count
+ * as a circuit "attempt". As long as end-to-end tagging is possible,
+ * we assume the adversary will use it over hop-to-hop failure. Therefore,
+ * we only need to account bias for the last hop. This should make us
+ * much more resilient to ambient circuit failure, and also make that
+ * failure easier to measure (we only need to measure Exit failure rates).
+ */
+static int
+pathbias_is_new_circ_attempt(origin_circuit_t *circ)
+{
+#define N2N_TAGGING_IS_POSSIBLE
+#ifdef N2N_TAGGING_IS_POSSIBLE
+  /* cpath is a circular list. We want circs with more than one hop,
+   * and the second hop must be waiting for keys still (it's just
+   * about to get them). */
+  return circ->cpath &&
+         circ->cpath->next != circ->cpath &&
+         circ->cpath->next->state == CPATH_STATE_AWAITING_KEYS;
+#else
+  /* If tagging attacks are no longer possible, we probably want to
+   * count bias from the first hop. However, one could argue that
+   * timing-based tagging is still more useful than per-hop failure.
+   * In which case, we'd never want to use this.
+   */
+  return circ->cpath &&
+         circ->cpath->state == CPATH_STATE_AWAITING_KEYS;
+#endif
+}
+
+/**
+ * Decide if the path bias code should count a circuit.
+ *
+ * @returns 1 if we should count it, 0 otherwise.
+ */
+static int
+pathbias_should_count(origin_circuit_t *circ)
+{
+#define PATHBIAS_COUNT_INTERVAL (600)
+  static ratelim_t count_limit =
+    RATELIM_INIT(PATHBIAS_COUNT_INTERVAL);
+  char *rate_msg = NULL;
+
+  /* We can't do path bias accounting without entry guards.
+   * Testing and controller circuits also have no guards.
+   *
+   * We also don't count server-side rends, because their
+   * endpoint could be chosen maliciously.
+   * Similarly, we can't count client-side intro attempts,
+   * because clients can be manipulated into connecting to
+   * malicious intro points. */
+  if (get_options()->UseEntryGuards == 0 ||
+          circ->base_.purpose == CIRCUIT_PURPOSE_TESTING ||
+          circ->base_.purpose == CIRCUIT_PURPOSE_CONTROLLER ||
+          circ->base_.purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
+          circ->base_.purpose == CIRCUIT_PURPOSE_S_REND_JOINED ||
+          (circ->base_.purpose >= CIRCUIT_PURPOSE_C_INTRODUCING &&
+           circ->base_.purpose <= CIRCUIT_PURPOSE_C_INTRODUCE_ACKED)) {
+
+    /* Check to see if the shouldcount result has changed due to a
+     * unexpected purpose change that would affect our results.
+     *
+     * The reason we check the path state too here is because for the
+     * cannibalized versions of these purposes, we count them as successful
+     * before their purpose change.
+     */
+    if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED
+            && circ->path_state != PATH_STATE_ALREADY_COUNTED) {
+      log_info(LD_BUG,
+               "Circuit %d is now being ignored despite being counted "
+               "in the past. Purpose is %s, path state is %s",
+               circ->global_identifier,
+               circuit_purpose_to_string(circ->base_.purpose),
+               pathbias_state_to_string(circ->path_state));
+    }
+    circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
+    return 0;
+  }
+
+  /* Completely ignore one hop circuits */
+  if (circ->build_state->onehop_tunnel ||
+      circ->build_state->desired_path_len == 1) {
+    /* Check for inconsistency */
+    if (circ->build_state->desired_path_len != 1 ||
+        !circ->build_state->onehop_tunnel) {
+      if ((rate_msg = rate_limit_log(&count_limit, approx_time()))) {
+        log_info(LD_BUG,
+               "One-hop circuit has length %d. Path state is %s. "
+               "Circuit is a %s currently %s.%s",
+               circ->build_state->desired_path_len,
+               pathbias_state_to_string(circ->path_state),
+               circuit_purpose_to_string(circ->base_.purpose),
+               circuit_state_to_string(circ->base_.state),
+               rate_msg);
+        tor_free(rate_msg);
+      }
+      tor_fragile_assert();
+    }
+
+    /* Check to see if the shouldcount result has changed due to a
+     * unexpected change that would affect our results */
+    if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED) {
+      log_info(LD_BUG,
+               "One-hop circuit %d is now being ignored despite being counted "
+               "in the past. Purpose is %s, path state is %s",
+               circ->global_identifier,
+               circuit_purpose_to_string(circ->base_.purpose),
+               pathbias_state_to_string(circ->path_state));
+    }
+    circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
+    return 0;
+  }
+
+  /* Check to see if the shouldcount result has changed due to a
+   * unexpected purpose change that would affect our results */
+  if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_IGNORED) {
+      log_info(LD_BUG,
+              "Circuit %d is now being counted despite being ignored "
+              "in the past. Purpose is %s, path state is %s",
+              circ->global_identifier,
+              circuit_purpose_to_string(circ->base_.purpose),
+              pathbias_state_to_string(circ->path_state));
+  }
+  circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_COUNTED;
+
+  return 1;
+}
+
+/**
+ * Check our circuit state to see if this is a successful circuit attempt.
+ * If so, record it in the current guard's path bias circ_attempt count.
+ *
+ * Also check for several potential error cases for bug #6475.
+ */
+static int
+pathbias_count_build_attempt(origin_circuit_t *circ)
+{
+#define CIRC_ATTEMPT_NOTICE_INTERVAL (600)
+  static ratelim_t circ_attempt_notice_limit =
+    RATELIM_INIT(CIRC_ATTEMPT_NOTICE_INTERVAL);
+  char *rate_msg = NULL;
+
+  if (!pathbias_should_count(circ)) {
+    return 0;
+  }
+
+  if (pathbias_is_new_circ_attempt(circ)) {
+    /* Help track down the real cause of bug #6475: */
+    if (circ->has_opened && circ->path_state != PATH_STATE_BUILD_ATTEMPTED) {
+      if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
+                                     approx_time()))) {
+        log_info(LD_BUG,
+                "Opened circuit is in strange path state %s. "
+                "Circuit is a %s currently %s.%s",
+                pathbias_state_to_string(circ->path_state),
+                circuit_purpose_to_string(circ->base_.purpose),
+                circuit_state_to_string(circ->base_.state),
+                rate_msg);
+        tor_free(rate_msg);
+      }
+    }
+
+    /* Don't re-count cannibalized circs.. */
+    if (!circ->has_opened) {
+      entry_guard_t *guard = NULL;
+
+      if (circ->cpath && circ->cpath->extend_info) {
+        guard = entry_guard_get_by_id_digest(
+                  circ->cpath->extend_info->identity_digest);
+      } else if (circ->base_.n_chan) {
+        guard =
+          entry_guard_get_by_id_digest(circ->base_.n_chan->identity_digest);
+      }
+
+      if (guard) {
+        if (circ->path_state == PATH_STATE_NEW_CIRC) {
+          circ->path_state = PATH_STATE_BUILD_ATTEMPTED;
+
+          if (entry_guard_inc_circ_attempt_count(guard) < 0) {
+            /* Bogus guard; we already warned. */
+            return -END_CIRC_REASON_TORPROTOCOL;
+          }
+        } else {
+          if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
+                  approx_time()))) {
+            log_info(LD_BUG,
+                   "Unopened circuit has strange path state %s. "
+                   "Circuit is a %s currently %s.%s",
+                   pathbias_state_to_string(circ->path_state),
+                   circuit_purpose_to_string(circ->base_.purpose),
+                   circuit_state_to_string(circ->base_.state),
+                   rate_msg);
+            tor_free(rate_msg);
+          }
+        }
+      } else {
+        if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
+                approx_time()))) {
+          log_info(LD_CIRC,
+              "Unopened circuit has no known guard. "
+              "Circuit is a %s currently %s.%s",
+              circuit_purpose_to_string(circ->base_.purpose),
+              circuit_state_to_string(circ->base_.state),
+              rate_msg);
+          tor_free(rate_msg);
+        }
+      }
+    }
+  }
+
+  return 0;
+}
+
+/**
+ * Check our circuit state to see if this is a successful circuit
+ * completion. If so, record it in the current guard's path bias
+ * success count.
+ *
+ * Also check for several potential error cases for bug #6475.
+ */
+static void
+pathbias_count_build_success(origin_circuit_t *circ)
+{
+#define SUCCESS_NOTICE_INTERVAL (600)
+  static ratelim_t success_notice_limit =
+    RATELIM_INIT(SUCCESS_NOTICE_INTERVAL);
+  char *rate_msg = NULL;
+  entry_guard_t *guard = NULL;
+
+  if (!pathbias_should_count(circ)) {
+    return;
+  }
+
+  /* Don't count cannibalized/reused circs for path bias
+   * "build" success, since they get counted under "use" success. */
+  if (!circ->has_opened) {
+    if (circ->cpath && circ->cpath->extend_info) {
+      guard = entry_guard_get_by_id_digest(
+                circ->cpath->extend_info->identity_digest);
+    }
+
+    if (guard) {
+      if (circ->path_state == PATH_STATE_BUILD_ATTEMPTED) {
+        circ->path_state = PATH_STATE_BUILD_SUCCEEDED;
+        guard->circ_successes++;
+        entry_guards_changed();
+
+        log_info(LD_CIRC, "Got success count %f/%f for guard %s ($%s)",
+                 guard->circ_successes, guard->circ_attempts,
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN));
+      } else {
+        if ((rate_msg = rate_limit_log(&success_notice_limit,
+                approx_time()))) {
+          log_info(LD_BUG,
+              "Succeeded circuit is in strange path state %s. "
+              "Circuit is a %s currently %s.%s",
+              pathbias_state_to_string(circ->path_state),
+              circuit_purpose_to_string(circ->base_.purpose),
+              circuit_state_to_string(circ->base_.state),
+              rate_msg);
+          tor_free(rate_msg);
+        }
+      }
+
+      if (guard->circ_attempts < guard->circ_successes) {
+        log_notice(LD_BUG, "Unexpectedly high successes counts (%f/%f) "
+                 "for guard %s ($%s)",
+                 guard->circ_successes, guard->circ_attempts,
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN));
+      }
+    /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
+     * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
+     * No need to log that case. */
+    } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
+      if ((rate_msg = rate_limit_log(&success_notice_limit,
+              approx_time()))) {
+        log_info(LD_CIRC,
+            "Completed circuit has no known guard. "
+            "Circuit is a %s currently %s.%s",
+            circuit_purpose_to_string(circ->base_.purpose),
+            circuit_state_to_string(circ->base_.state),
+            rate_msg);
+        tor_free(rate_msg);
+      }
+    }
+  } else {
+    if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) {
+      if ((rate_msg = rate_limit_log(&success_notice_limit,
+              approx_time()))) {
+        log_info(LD_BUG,
+            "Opened circuit is in strange path state %s. "
+            "Circuit is a %s currently %s.%s",
+            pathbias_state_to_string(circ->path_state),
+            circuit_purpose_to_string(circ->base_.purpose),
+            circuit_state_to_string(circ->base_.state),
+            rate_msg);
+        tor_free(rate_msg);
+      }
+    }
+  }
+}
+
+/**
+ * Record an attempt to use a circuit. Changes the circuit's
+ * path state and update its guard's usage counter.
+ *
+ * Used for path bias usage accounting.
+ */
+void
+pathbias_count_use_attempt(origin_circuit_t *circ)
+{
+  entry_guard_t *guard;
+
+  if (!pathbias_should_count(circ)) {
+    return;
+  }
+
+  if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) {
+    log_notice(LD_BUG,
+        "Used circuit is in strange path state %s. "
+        "Circuit is a %s currently %s.",
+        pathbias_state_to_string(circ->path_state),
+        circuit_purpose_to_string(circ->base_.purpose),
+        circuit_state_to_string(circ->base_.state));
+  } else if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
+    guard = entry_guard_get_by_id_digest(
+                circ->cpath->extend_info->identity_digest);
+    if (guard) {
+      pathbias_measure_use_rate(guard);
+      pathbias_scale_use_rates(guard);
+      guard->use_attempts++;
+      entry_guards_changed();
+
+      log_debug(LD_CIRC,
+               "Marked circuit %d (%f/%f) as used for guard %s ($%s).",
+               circ->global_identifier,
+               guard->use_successes, guard->use_attempts,
+               guard->nickname, hex_str(guard->identity, DIGEST_LEN));
+    }
+
+    circ->path_state = PATH_STATE_USE_ATTEMPTED;
+  } else {
+    /* Harmless but educational log message */
+    log_info(LD_CIRC,
+        "Used circuit %d is already in path state %s. "
+        "Circuit is a %s currently %s.",
+        circ->global_identifier,
+        pathbias_state_to_string(circ->path_state),
+        circuit_purpose_to_string(circ->base_.purpose),
+        circuit_state_to_string(circ->base_.state));
+  }
+
+  return;
+}
+
+/**
+ * Check the circuit's path state is appropriate and mark it as
+ * successfully used. Used for path bias usage accounting.
+ *
+ * We don't actually increment the guard's counters until
+ * pathbias_check_close(), because the circuit can still transition
+ * back to PATH_STATE_USE_ATTEMPTED if a stream fails later (this
+ * is done so we can probe the circuit for liveness at close).
+ */
+void
+pathbias_mark_use_success(origin_circuit_t *circ)
+{
+  if (!pathbias_should_count(circ)) {
+    return;
+  }
+
+  if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
+    log_notice(LD_BUG,
+        "Used circuit %d is in strange path state %s. "
+        "Circuit is a %s currently %s.",
+        circ->global_identifier,
+        pathbias_state_to_string(circ->path_state),
+        circuit_purpose_to_string(circ->base_.purpose),
+        circuit_state_to_string(circ->base_.state));
+
+    pathbias_count_use_attempt(circ);
+  }
+
+  /* We don't do any accounting at the guard until actual circuit close */
+  circ->path_state = PATH_STATE_USE_SUCCEEDED;
+
+  return;
+}
+
+/**
+ * If a stream ever detatches from a circuit in a retriable way,
+ * we need to mark this circuit as still needing either another
+ * successful stream, or in need of a probe.
+ *
+ * An adversary could let the first stream request succeed (ie the
+ * resolve), but then tag and timeout the remainder (via cell
+ * dropping), forcing them on new circuits.
+ *
+ * Rolling back the state will cause us to probe such circuits, which
+ * should lead to probe failures in the event of such tagging due to
+ * either unrecognized cells coming in while we wait for the probe,
+ * or the cipher state getting out of sync in the case of dropped cells.
+ */
+void
+pathbias_mark_use_rollback(origin_circuit_t *circ)
+{
+  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
+    log_info(LD_CIRC,
+             "Rolling back pathbias use state to 'attempted' for detached "
+             "circuit %d", circ->global_identifier);
+    circ->path_state = PATH_STATE_USE_ATTEMPTED;
+  }
+}
+
+/**
+ * Actually count a circuit success towards a guard's usage counters
+ * if the path state is appropriate.
+ */
+static void
+pathbias_count_use_success(origin_circuit_t *circ)
+{
+  entry_guard_t *guard;
+
+  if (!pathbias_should_count(circ)) {
+    return;
+  }
+
+  if (circ->path_state != PATH_STATE_USE_SUCCEEDED) {
+    log_notice(LD_BUG,
+        "Successfully used circuit %d is in strange path state %s. "
+        "Circuit is a %s currently %s.",
+        circ->global_identifier,
+        pathbias_state_to_string(circ->path_state),
+        circuit_purpose_to_string(circ->base_.purpose),
+        circuit_state_to_string(circ->base_.state));
+  } else {
+    guard = entry_guard_get_by_id_digest(
+                circ->cpath->extend_info->identity_digest);
+    if (guard) {
+      guard->use_successes++;
+      entry_guards_changed();
+
+      if (guard->use_attempts < guard->use_successes) {
+        log_notice(LD_BUG, "Unexpectedly high use successes counts (%f/%f) "
+                 "for guard %s=%s",
+                 guard->use_successes, guard->use_attempts,
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN));
+      }
+
+      log_debug(LD_CIRC,
+                "Marked circuit %d (%f/%f) as used successfully for guard "
+                "%s ($%s).",
+                circ->global_identifier, guard->use_successes,
+                guard->use_attempts, guard->nickname,
+                hex_str(guard->identity, DIGEST_LEN));
+    }
+  }
+
+  return;
+}
+
+/**
+ * Send a probe down a circuit that the client attempted to use,
+ * but for which the stream timed out/failed. The probe is a
+ * RELAY_BEGIN cell with a 0.a.b.c destination address, which
+ * the exit will reject and reply back, echoing that address.
+ *
+ * The reason for such probes is because it is possible to bias
+ * a user's paths simply by causing timeouts, and these timeouts
+ * are not possible to differentiate from unresponsive servers.
+ *
+ * The probe is sent at the end of the circuit lifetime for two
+ * reasons: to prevent cryptographic taggers from being able to
+ * drop cells to cause timeouts, and to prevent easy recognition
+ * of probes before any real client traffic happens.
+ *
+ * Returns -1 if we couldn't probe, 0 otherwise.
+ */
+static int
+pathbias_send_usable_probe(circuit_t *circ)
+{
+  /* Based on connection_ap_handshake_send_begin() */
+  char payload[CELL_PAYLOAD_SIZE];
+  int payload_len;
+  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
+  crypt_path_t *cpath_layer = NULL;
+  char *probe_nonce = NULL;
+
+  tor_assert(ocirc);
+
+  cpath_layer = ocirc->cpath->prev;
+
+  if (cpath_layer->state != CPATH_STATE_OPEN) {
+    /* This can happen for cannibalized circuits. Their
+     * last hop isn't yet open */
+    log_info(LD_CIRC,
+             "Got pathbias probe request for unopened circuit %d. "
+             "Opened %d, len %d", ocirc->global_identifier,
+             ocirc->has_opened, ocirc->build_state->desired_path_len);
+    return -1;
+  }
+
+  /* We already went down this road. */
+  if (circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING &&
+      ocirc->pathbias_probe_id) {
+    log_info(LD_CIRC,
+             "Got pathbias probe request for circuit %d with "
+             "outstanding probe", ocirc->global_identifier);
+    return -1;
+  }
+
+  /* Can't probe if the channel isn't open */
+  if (circ->n_chan == NULL ||
+      (circ->n_chan->state != CHANNEL_STATE_OPEN
+       && circ->n_chan->state != CHANNEL_STATE_MAINT)) {
+    log_info(LD_CIRC,
+             "Skipping pathbias probe for circuit %d: Channel is not open.",
+             ocirc->global_identifier);
+    return -1;
+  }
+
+  circuit_change_purpose(circ, CIRCUIT_PURPOSE_PATH_BIAS_TESTING);
+
+  /* Update timestamp for when circuit_expire_building() should kill us */
+  tor_gettimeofday(&circ->timestamp_began);
+
+  /* Generate a random address for the nonce */
+  crypto_rand((char*)&ocirc->pathbias_probe_nonce,
+              sizeof(ocirc->pathbias_probe_nonce));
+  ocirc->pathbias_probe_nonce &= 0x00ffffff;
+  probe_nonce = tor_dup_ip(ocirc->pathbias_probe_nonce);
+
+  tor_snprintf(payload,RELAY_PAYLOAD_SIZE, "%s:25", probe_nonce);
+  payload_len = (int)strlen(payload)+1;
+
+  // XXX: need this? Can we assume ipv4 will always be supported?
+  // If not, how do we tell?
+  //if (payload_len <= RELAY_PAYLOAD_SIZE - 4 && edge_conn->begincell_flags) {
+  //  set_uint32(payload + payload_len, htonl(edge_conn->begincell_flags));
+  //  payload_len += 4;
+  //}
+
+  /* Generate+Store stream id, make sure it's non-zero */
+  ocirc->pathbias_probe_id = get_unique_stream_id_by_circ(ocirc);
+
+  if (ocirc->pathbias_probe_id==0) {
+    log_warn(LD_CIRC,
+             "Ran out of stream IDs on circuit %u during "
+             "pathbias probe attempt.", ocirc->global_identifier);
+    tor_free(probe_nonce);
+    return -1;
+  }
+
+  log_info(LD_CIRC,
+           "Sending pathbias testing cell to %s:25 on stream %d for circ %d.",
+           probe_nonce, ocirc->pathbias_probe_id, ocirc->global_identifier);
+  tor_free(probe_nonce);
+
+  /* Send a test relay cell */
+  if (relay_send_command_from_edge(ocirc->pathbias_probe_id, circ,
+                               RELAY_COMMAND_BEGIN, payload,
+                               payload_len, cpath_layer) < 0) {
+    log_notice(LD_CIRC,
+               "Failed to send pathbias probe cell on circuit %d.",
+               ocirc->global_identifier);
+    return -1;
+  }
+
+  /* Mark it freshly dirty so it doesn't get expired in the meantime */
+  circ->timestamp_dirty = time(NULL);
+
+  return 0;
+}
+
+/**
+ * Check the response to a pathbias probe, to ensure the
+ * cell is recognized and the nonce and other probe
+ * characteristics are as expected.
+ *
+ * If the response is valid, return 0. Otherwise return < 0.
+ */
+int
+pathbias_check_probe_response(circuit_t *circ, const cell_t *cell)
+{
+  /* Based on connection_edge_process_relay_cell() */
+  relay_header_t rh;
+  int reason;
+  uint32_t ipv4_host;
+  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
+
+  tor_assert(cell);
+  tor_assert(ocirc);
+  tor_assert(circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING);
+
+  relay_header_unpack(&rh, cell->payload);
+
+  reason = rh.length > 0 ?
+        get_uint8(cell->payload+RELAY_HEADER_SIZE) : END_STREAM_REASON_MISC;
+
+  if (rh.command == RELAY_COMMAND_END &&
+      reason == END_STREAM_REASON_EXITPOLICY &&
+      ocirc->pathbias_probe_id == rh.stream_id) {
+
+    /* Check length+extract host: It is in network order after the reason code.
+     * See connection_edge_end(). */
+    if (rh.length < 9) { /* reason+ipv4+dns_ttl */
+      log_notice(LD_PROTOCOL,
+             "Short path bias probe response length field (%d).", rh.length);
+      return - END_CIRC_REASON_TORPROTOCOL;
+    }
+
+    ipv4_host = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+1));
+
+    /* Check nonce */
+    if (ipv4_host == ocirc->pathbias_probe_nonce) {
+      pathbias_mark_use_success(ocirc);
+      circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
+      log_info(LD_CIRC,
+               "Got valid path bias probe back for circ %d, stream %d.",
+               ocirc->global_identifier, ocirc->pathbias_probe_id);
+      return 0;
+    } else {
+      log_notice(LD_CIRC,
+               "Got strange probe value 0x%x vs 0x%x back for circ %d, "
+               "stream %d.", ipv4_host, ocirc->pathbias_probe_nonce,
+               ocirc->global_identifier, ocirc->pathbias_probe_id);
+      return -1;
+    }
+  }
+  log_info(LD_CIRC,
+             "Got another cell back back on pathbias probe circuit %d: "
+             "Command: %d, Reason: %d, Stream-id: %d",
+             ocirc->global_identifier, rh.command, reason, rh.stream_id);
+  return -1;
+}
+
+/**
+ * Check if a circuit was used and/or closed successfully.
+ *
+ * If we attempted to use the circuit to carry a stream but failed
+ * for whatever reason, or if the circuit mysteriously died before
+ * we could attach any streams, record these two cases.
+ *
+ * If we *have* successfully used the circuit, or it appears to
+ * have been closed by us locally, count it as a success.
+ *
+ * Returns 0 if we're done making decisions with the circ,
+ * or -1 if we want to probe it first.
+ */
+int
+pathbias_check_close(origin_circuit_t *ocirc, int reason)
+{
+  circuit_t *circ = &ocirc->base_;
+
+  if (!pathbias_should_count(ocirc)) {
+    return 0;
+  }
+
+  switch (ocirc->path_state) {
+    /* If the circuit was closed after building, but before use, we need
+     * to ensure we were the ones who tried to close it (and not a remote
+     * actor). */
+    case PATH_STATE_BUILD_SUCCEEDED:
+      if (reason & END_CIRC_REASON_FLAG_REMOTE) {
+        /* Remote circ close reasons on an unused circuit all could be bias */
+        log_info(LD_CIRC,
+            "Circuit %d remote-closed without successful use for reason %d. "
+            "Circuit purpose %d currently %d,%s. Len %d.",
+            ocirc->global_identifier,
+            reason, circ->purpose, ocirc->has_opened,
+            circuit_state_to_string(circ->state),
+            ocirc->build_state->desired_path_len);
+        pathbias_count_collapse(ocirc);
+      } else if ((reason & ~END_CIRC_REASON_FLAG_REMOTE)
+                  == END_CIRC_REASON_CHANNEL_CLOSED &&
+                 circ->n_chan &&
+                 circ->n_chan->reason_for_closing
+                  != CHANNEL_CLOSE_REQUESTED) {
+        /* If we didn't close the channel ourselves, it could be bias */
+        /* XXX: Only count bias if the network is live?
+         * What about clock jumps/suspends? */
+        log_info(LD_CIRC,
+            "Circuit %d's channel closed without successful use for reason "
+            "%d, channel reason %d. Circuit purpose %d currently %d,%s. Len "
+            "%d.", ocirc->global_identifier,
+            reason, circ->n_chan->reason_for_closing,
+            circ->purpose, ocirc->has_opened,
+            circuit_state_to_string(circ->state),
+            ocirc->build_state->desired_path_len);
+        pathbias_count_collapse(ocirc);
+      } else {
+        pathbias_count_successful_close(ocirc);
+      }
+      break;
+
+    /* If we tried to use a circuit but failed, we should probe it to ensure
+     * it has not been tampered with. */
+    case PATH_STATE_USE_ATTEMPTED:
+      /* XXX: Only probe and/or count failure if the network is live?
+       * What about clock jumps/suspends? */
+      if (pathbias_send_usable_probe(circ) == 0)
+        return -1;
+      else
+        pathbias_count_use_failed(ocirc);
+
+      /* Any circuit where there were attempted streams but no successful
+       * streams could be bias */
+      log_info(LD_CIRC,
+            "Circuit %d closed without successful use for reason %d. "
+            "Circuit purpose %d currently %d,%s. Len %d.",
+            ocirc->global_identifier,
+            reason, circ->purpose, ocirc->has_opened,
+            circuit_state_to_string(circ->state),
+            ocirc->build_state->desired_path_len);
+      break;
+
+    case PATH_STATE_USE_SUCCEEDED:
+      pathbias_count_successful_close(ocirc);
+      pathbias_count_use_success(ocirc);
+      break;
+
+    case PATH_STATE_USE_FAILED:
+      pathbias_count_use_failed(ocirc);
+      break;
+
+    case PATH_STATE_NEW_CIRC:
+    case PATH_STATE_BUILD_ATTEMPTED:
+    case PATH_STATE_ALREADY_COUNTED:
+    default:
+      // Other states are uninteresting. No stats to count.
+      break;
+  }
+
+  ocirc->path_state = PATH_STATE_ALREADY_COUNTED;
+
+  return 0;
+}
+
+/**
+ * Count a successfully closed circuit.
+ */
+static void
+pathbias_count_successful_close(origin_circuit_t *circ)
+{
+  entry_guard_t *guard = NULL;
+  if (!pathbias_should_count(circ)) {
+    return;
+  }
+
+  if (circ->cpath && circ->cpath->extend_info) {
+    guard = entry_guard_get_by_id_digest(
+              circ->cpath->extend_info->identity_digest);
+  }
+
+  if (guard) {
+    /* In the long run: circuit_success ~= successful_circuit_close +
+     *                                     circ_failure + stream_failure */
+    guard->successful_circuits_closed++;
+    entry_guards_changed();
+  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
+   /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
+    * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
+    * No need to log that case. */
+    log_info(LD_CIRC,
+        "Successfully closed circuit has no known guard. "
+        "Circuit is a %s currently %s",
+        circuit_purpose_to_string(circ->base_.purpose),
+        circuit_state_to_string(circ->base_.state));
+  }
+}
+
+/**
+ * Count a circuit that fails after it is built, but before it can
+ * carry any traffic.
+ *
+ * This is needed because there are ways to destroy a
+ * circuit after it has successfully completed. Right now, this is
+ * used for purely informational/debugging purposes.
+ */
+static void
+pathbias_count_collapse(origin_circuit_t *circ)
+{
+  entry_guard_t *guard = NULL;
+
+  if (!pathbias_should_count(circ)) {
+    return;
+  }
+
+  if (circ->cpath && circ->cpath->extend_info) {
+    guard = entry_guard_get_by_id_digest(
+              circ->cpath->extend_info->identity_digest);
+  }
+
+  if (guard) {
+    guard->collapsed_circuits++;
+    entry_guards_changed();
+  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
+   /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
+    * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
+    * No need to log that case. */
+    log_info(LD_CIRC,
+        "Destroyed circuit has no known guard. "
+        "Circuit is a %s currently %s",
+        circuit_purpose_to_string(circ->base_.purpose),
+        circuit_state_to_string(circ->base_.state));
+  }
+}
+
+/**
+ * Count a known failed circuit (because we could not probe it).
+ *
+ * This counter is informational.
+ */
+static void
+pathbias_count_use_failed(origin_circuit_t *circ)
+{
+  entry_guard_t *guard = NULL;
+  if (!pathbias_should_count(circ)) {
+    return;
+  }
+
+  if (circ->cpath && circ->cpath->extend_info) {
+    guard = entry_guard_get_by_id_digest(
+              circ->cpath->extend_info->identity_digest);
+  }
+
+  if (guard) {
+    guard->unusable_circuits++;
+    entry_guards_changed();
+  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
+   /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
+    * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
+    * No need to log that case. */
+    /* XXX note cut-and-paste code in this function compared to nearby
+     * functions. Would be nice to refactor. -RD */
+    log_info(LD_CIRC,
+        "Stream-failing circuit has no known guard. "
+        "Circuit is a %s currently %s",
+        circuit_purpose_to_string(circ->base_.purpose),
+        circuit_state_to_string(circ->base_.state));
+  }
+}
+
+/**
+ * Count timeouts for path bias log messages.
+ *
+ * These counts are purely informational.
+ */
+void
+pathbias_count_timeout(origin_circuit_t *circ)
+{
+  entry_guard_t *guard = NULL;
+
+  if (!pathbias_should_count(circ)) {
+    return;
+  }
+
+  /* For hidden service circs, they can actually be used
+   * successfully and then time out later (because
+   * the other side declines to use them). */
+  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
+    return;
+  }
+
+  if (circ->cpath && circ->cpath->extend_info) {
+    guard = entry_guard_get_by_id_digest(
+              circ->cpath->extend_info->identity_digest);
+  }
+
+  if (guard) {
+    guard->timeouts++;
+    entry_guards_changed();
+  }
+}
+
+/**
+ * Helper function to count all of the currently opened circuits
+ * for a guard that are in a given path state range. The state
+ * range is inclusive on both ends.
+ */
+static int
+pathbias_count_circs_in_states(entry_guard_t *guard,
+                              path_state_t from,
+                              path_state_t to)
+{
+  circuit_t *circ;
+  int open_circuits = 0;
+
+  /* Count currently open circuits. Give them the benefit of the doubt. */
+  TOR_LIST_FOREACH(circ, circuit_get_global_list(), head) {
+    origin_circuit_t *ocirc = NULL;
+    if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */
+        circ->marked_for_close) /* already counted */
+      continue;
+
+    ocirc = TO_ORIGIN_CIRCUIT(circ);
+
+    if (!ocirc->cpath || !ocirc->cpath->extend_info)
+      continue;
+
+    if (ocirc->path_state >= from &&
+        ocirc->path_state <= to &&
+        pathbias_should_count(ocirc) &&
+        fast_memeq(guard->identity,
+                   ocirc->cpath->extend_info->identity_digest,
+                   DIGEST_LEN)) {
+      log_debug(LD_CIRC, "Found opened circuit %d in path_state %s",
+                ocirc->global_identifier,
+                pathbias_state_to_string(ocirc->path_state));
+      open_circuits++;
+    }
+  }
+
+  return open_circuits;
+}
+
+/**
+ * Return the number of circuits counted as successfully closed for
+ * this guard.
+ *
+ * Also add in the currently open circuits to give them the benefit
+ * of the doubt.
+ */
+double
+pathbias_get_close_success_count(entry_guard_t *guard)
+{
+  return guard->successful_circuits_closed +
+         pathbias_count_circs_in_states(guard,
+                       PATH_STATE_BUILD_SUCCEEDED,
+                       PATH_STATE_USE_SUCCEEDED);
+}
+
+/**
+ * Return the number of circuits counted as successfully used
+ * this guard.
+ *
+ * Also add in the currently open circuits that we are attempting
+ * to use to give them the benefit of the doubt.
+ */
+double
+pathbias_get_use_success_count(entry_guard_t *guard)
+{
+  return guard->use_successes +
+         pathbias_count_circs_in_states(guard,
+                       PATH_STATE_USE_ATTEMPTED,
+                       PATH_STATE_USE_SUCCEEDED);
+}
+
+/**
+ * Check the path bias use rate against our consensus parameter limits.
+ *
+ * Emits a log message if the use success rates are too low.
+ *
+ * If pathbias_get_dropguards() is set, we also disable the use of
+ * very failure prone guards.
+ */
+static void
+pathbias_measure_use_rate(entry_guard_t *guard)
+{
+  const or_options_t *options = get_options();
+
+  if (guard->use_attempts > pathbias_get_min_use(options)) {
+    /* Note: We rely on the < comparison here to allow us to set a 0
+     * rate and disable the feature entirely. If refactoring, don't
+     * change to <= */
+    if (pathbias_get_use_success_count(guard)/guard->use_attempts
+        < pathbias_get_extreme_use_rate(options)) {
+      /* Dropping is currently disabled by default. */
+      if (pathbias_get_dropguards(options)) {
+        if (!guard->path_bias_disabled) {
+          log_warn(LD_CIRC,
+                 "Your Guard %s ($%s) is failing to carry an extremely large "
+                 "amount of stream on its circuits. "
+                 "To avoid potential route manipulation attacks, Tor has "
+                 "disabled use of this guard. "
+                 "Use counts are %ld/%ld. Success counts are %ld/%ld. "
+                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
+                 "and %ld timed out. "
+                 "For reference, your timeout cutoff is %ld seconds.",
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
+                 tor_lround(pathbias_get_use_success_count(guard)),
+                 tor_lround(guard->use_attempts),
+                 tor_lround(pathbias_get_close_success_count(guard)),
+                 tor_lround(guard->circ_attempts),
+                 tor_lround(guard->circ_successes),
+                 tor_lround(guard->unusable_circuits),
+                 tor_lround(guard->collapsed_circuits),
+                 tor_lround(guard->timeouts),
+                 tor_lround(get_circuit_build_close_time_ms()/1000));
+          guard->path_bias_disabled = 1;
+          guard->bad_since = approx_time();
+          entry_guards_changed();
+          return;
+        }
+      } else if (!guard->path_bias_use_extreme) {
+        guard->path_bias_use_extreme = 1;
+        log_warn(LD_CIRC,
+                 "Your Guard %s ($%s) is failing to carry an extremely large "
+                 "amount of streams on its circuits. "
+                 "This could indicate a route manipulation attack, network "
+                 "overload, bad local network connectivity, or a bug. "
+                 "Use counts are %ld/%ld. Success counts are %ld/%ld. "
+                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
+                 "and %ld timed out. "
+                 "For reference, your timeout cutoff is %ld seconds.",
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
+                 tor_lround(pathbias_get_use_success_count(guard)),
+                 tor_lround(guard->use_attempts),
+                 tor_lround(pathbias_get_close_success_count(guard)),
+                 tor_lround(guard->circ_attempts),
+                 tor_lround(guard->circ_successes),
+                 tor_lround(guard->unusable_circuits),
+                 tor_lround(guard->collapsed_circuits),
+                 tor_lround(guard->timeouts),
+                 tor_lround(get_circuit_build_close_time_ms()/1000));
+      }
+    } else if (pathbias_get_use_success_count(guard)/guard->use_attempts
+               < pathbias_get_notice_use_rate(options)) {
+      if (!guard->path_bias_use_noticed) {
+        guard->path_bias_use_noticed = 1;
+        log_notice(LD_CIRC,
+                 "Your Guard %s ($%s) is failing to carry more streams on its "
+                 "circuits than usual. "
+                 "Most likely this means the Tor network is overloaded "
+                 "or your network connection is poor. "
+                 "Use counts are %ld/%ld. Success counts are %ld/%ld. "
+                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
+                 "and %ld timed out. "
+                 "For reference, your timeout cutoff is %ld seconds.",
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
+                 tor_lround(pathbias_get_use_success_count(guard)),
+                 tor_lround(guard->use_attempts),
+                 tor_lround(pathbias_get_close_success_count(guard)),
+                 tor_lround(guard->circ_attempts),
+                 tor_lround(guard->circ_successes),
+                 tor_lround(guard->unusable_circuits),
+                 tor_lround(guard->collapsed_circuits),
+                 tor_lround(guard->timeouts),
+                 tor_lround(get_circuit_build_close_time_ms()/1000));
+      }
+    }
+  }
+}
+
+/**
+ * Check the path bias circuit close status rates against our consensus
+ * parameter limits.
+ *
+ * Emits a log message if the use success rates are too low.
+ *
+ * If pathbias_get_dropguards() is set, we also disable the use of
+ * very failure prone guards.
+ *
+ * XXX: This function shares similar log messages and checks to
+ * pathbias_measure_use_rate(). It may be possible to combine them
+ * eventually, especially if we can ever remove the need for 3
+ * levels of closure warns (if the overall circuit failure rate
+ * goes down with ntor). One way to do so would be to multiply
+ * the build rate with the use rate to get an idea of the total
+ * fraction of the total network paths the user is able to use.
+ * See ticket #8159.
+ */
+static void
+pathbias_measure_close_rate(entry_guard_t *guard)
+{
+  const or_options_t *options = get_options();
+
+  if (guard->circ_attempts > pathbias_get_min_circs(options)) {
+    /* Note: We rely on the < comparison here to allow us to set a 0
+     * rate and disable the feature entirely. If refactoring, don't
+     * change to <= */
+    if (pathbias_get_close_success_count(guard)/guard->circ_attempts
+        < pathbias_get_extreme_rate(options)) {
+      /* Dropping is currently disabled by default. */
+      if (pathbias_get_dropguards(options)) {
+        if (!guard->path_bias_disabled) {
+          log_warn(LD_CIRC,
+                 "Your Guard %s ($%s) is failing an extremely large "
+                 "amount of circuits. "
+                 "To avoid potential route manipulation attacks, Tor has "
+                 "disabled use of this guard. "
+                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
+                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
+                 "and %ld timed out. "
+                 "For reference, your timeout cutoff is %ld seconds.",
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
+                 tor_lround(pathbias_get_close_success_count(guard)),
+                 tor_lround(guard->circ_attempts),
+                 tor_lround(pathbias_get_use_success_count(guard)),
+                 tor_lround(guard->use_attempts),
+                 tor_lround(guard->circ_successes),
+                 tor_lround(guard->unusable_circuits),
+                 tor_lround(guard->collapsed_circuits),
+                 tor_lround(guard->timeouts),
+                 tor_lround(get_circuit_build_close_time_ms()/1000));
+          guard->path_bias_disabled = 1;
+          guard->bad_since = approx_time();
+          entry_guards_changed();
+          return;
+        }
+      } else if (!guard->path_bias_extreme) {
+        guard->path_bias_extreme = 1;
+        log_warn(LD_CIRC,
+                 "Your Guard %s ($%s) is failing an extremely large "
+                 "amount of circuits. "
+                 "This could indicate a route manipulation attack, "
+                 "extreme network overload, or a bug. "
+                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
+                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
+                 "and %ld timed out. "
+                 "For reference, your timeout cutoff is %ld seconds.",
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
+                 tor_lround(pathbias_get_close_success_count(guard)),
+                 tor_lround(guard->circ_attempts),
+                 tor_lround(pathbias_get_use_success_count(guard)),
+                 tor_lround(guard->use_attempts),
+                 tor_lround(guard->circ_successes),
+                 tor_lround(guard->unusable_circuits),
+                 tor_lround(guard->collapsed_circuits),
+                 tor_lround(guard->timeouts),
+                 tor_lround(get_circuit_build_close_time_ms()/1000));
+      }
+    } else if (pathbias_get_close_success_count(guard)/guard->circ_attempts
+                < pathbias_get_warn_rate(options)) {
+      if (!guard->path_bias_warned) {
+        guard->path_bias_warned = 1;
+        log_warn(LD_CIRC,
+                 "Your Guard %s ($%s) is failing a very large "
+                 "amount of circuits. "
+                 "Most likely this means the Tor network is "
+                 "overloaded, but it could also mean an attack against "
+                 "you or potentially the guard itself. "
+                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
+                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
+                 "and %ld timed out. "
+                 "For reference, your timeout cutoff is %ld seconds.",
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
+                 tor_lround(pathbias_get_close_success_count(guard)),
+                 tor_lround(guard->circ_attempts),
+                 tor_lround(pathbias_get_use_success_count(guard)),
+                 tor_lround(guard->use_attempts),
+                 tor_lround(guard->circ_successes),
+                 tor_lround(guard->unusable_circuits),
+                 tor_lround(guard->collapsed_circuits),
+                 tor_lround(guard->timeouts),
+                 tor_lround(get_circuit_build_close_time_ms()/1000));
+      }
+    } else if (pathbias_get_close_success_count(guard)/guard->circ_attempts
+               < pathbias_get_notice_rate(options)) {
+      if (!guard->path_bias_noticed) {
+        guard->path_bias_noticed = 1;
+        log_notice(LD_CIRC,
+                 "Your Guard %s ($%s) is failing more circuits than "
+                 "usual. "
+                 "Most likely this means the Tor network is overloaded. "
+                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
+                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
+                 "and %ld timed out. "
+                 "For reference, your timeout cutoff is %ld seconds.",
+                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
+                 tor_lround(pathbias_get_close_success_count(guard)),
+                 tor_lround(guard->circ_attempts),
+                 tor_lround(pathbias_get_use_success_count(guard)),
+                 tor_lround(guard->use_attempts),
+                 tor_lround(guard->circ_successes),
+                 tor_lround(guard->unusable_circuits),
+                 tor_lround(guard->collapsed_circuits),
+                 tor_lround(guard->timeouts),
+                 tor_lround(get_circuit_build_close_time_ms()/1000));
+      }
+    }
+  }
+}
+
+/**
+ * This function scales the path bias use rates if we have
+ * more data than the scaling threshold. This allows us to
+ * be more sensitive to recent measurements.
+ *
+ * XXX: The attempt count transfer stuff here might be done
+ * better by keeping separate pending counters that get
+ * transfered at circuit close. See ticket #8160.
+ */
+static void
+pathbias_scale_close_rates(entry_guard_t *guard)
+{
+  const or_options_t *options = get_options();
+
+  /* If we get a ton of circuits, just scale everything down */
+  if (guard->circ_attempts > pathbias_get_scale_threshold(options)) {
+    double scale_ratio = pathbias_get_scale_ratio(options);
+    int opened_attempts = pathbias_count_circs_in_states(guard,
+            PATH_STATE_BUILD_ATTEMPTED, PATH_STATE_BUILD_ATTEMPTED);
+    int opened_built = pathbias_count_circs_in_states(guard,
+                        PATH_STATE_BUILD_SUCCEEDED,
+                        PATH_STATE_USE_FAILED);
+    /* Verify that the counts are sane before and after scaling */
+    int counts_are_sane = (guard->circ_attempts >= guard->circ_successes);
+
+    guard->circ_attempts -= (opened_attempts+opened_built);
+    guard->circ_successes -= opened_built;
+
+    guard->circ_attempts *= scale_ratio;
+    guard->circ_successes *= scale_ratio;
+    guard->timeouts *= scale_ratio;
+    guard->successful_circuits_closed *= scale_ratio;
+    guard->collapsed_circuits *= scale_ratio;
+    guard->unusable_circuits *= scale_ratio;
+
+    guard->circ_attempts += (opened_attempts+opened_built);
+    guard->circ_successes += opened_built;
+
+    entry_guards_changed();
+
+    log_info(LD_CIRC,
+             "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard "
+             "%s ($%s)",
+             guard->circ_successes, guard->successful_circuits_closed,
+             guard->circ_attempts, opened_built, opened_attempts,
+             guard->nickname, hex_str(guard->identity, DIGEST_LEN));
+
+    /* Have the counts just become invalid by this scaling attempt? */
+    if (counts_are_sane && guard->circ_attempts < guard->circ_successes) {
+      log_notice(LD_BUG,
+               "Scaling has mangled pathbias counts to %f/%f (%d/%d open) "
+               "for guard %s ($%s)",
+               guard->circ_successes, guard->circ_attempts, opened_built,
+               opened_attempts, guard->nickname,
+               hex_str(guard->identity, DIGEST_LEN));
+    }
+  }
+}
+
+/**
+ * This function scales the path bias circuit close rates if we have
+ * more data than the scaling threshold. This allows us to be more
+ * sensitive to recent measurements.
+ *
+ * XXX: The attempt count transfer stuff here might be done
+ * better by keeping separate pending counters that get
+ * transfered at circuit close. See ticket #8160.
+ */
+void
+pathbias_scale_use_rates(entry_guard_t *guard)
+{
+  const or_options_t *options = get_options();
+
+  /* If we get a ton of circuits, just scale everything down */
+  if (guard->use_attempts > pathbias_get_scale_use_threshold(options)) {
+    double scale_ratio = pathbias_get_scale_ratio(options);
+    int opened_attempts = pathbias_count_circs_in_states(guard,
+            PATH_STATE_USE_ATTEMPTED, PATH_STATE_USE_SUCCEEDED);
+    /* Verify that the counts are sane before and after scaling */
+    int counts_are_sane = (guard->use_attempts >= guard->use_successes);
+
+    guard->use_attempts -= opened_attempts;
+
+    guard->use_attempts *= scale_ratio;
+    guard->use_successes *= scale_ratio;
+
+    guard->use_attempts += opened_attempts;
+
+    log_info(LD_CIRC,
+           "Scaled pathbias use counts to %f/%f (%d open) for guard %s ($%s)",
+           guard->use_successes, guard->use_attempts, opened_attempts,
+           guard->nickname, hex_str(guard->identity, DIGEST_LEN));
+
+    /* Have the counts just become invalid by this scaling attempt? */
+    if (counts_are_sane && guard->use_attempts < guard->use_successes) {
+      log_notice(LD_BUG,
+               "Scaling has mangled pathbias usage counts to %f/%f "
+               "(%d open) for guard %s ($%s)",
+               guard->circ_successes, guard->circ_attempts,
+               opened_attempts, guard->nickname,
+               hex_str(guard->identity, DIGEST_LEN));
+    }
+
+    entry_guards_changed();
+  }
+}
diff --git a/src/or/circpathbias.h b/src/or/circpathbias.h
new file mode 100644
index 000000000..bccc6f6fd
--- /dev/null
+++ b/src/or/circpathbias.h
@@ -0,0 +1,27 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2013, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file circuitbuild.h
+ * \brief Header file for circuitbuild.c.
+ **/
+
+#ifndef TOR_CIRCPATHBIAS_H
+#define TOR_CIRCPATHBIAS_H
+
+double pathbias_get_extreme_rate(const or_options_t *options);
+double pathbias_get_extreme_use_rate(const or_options_t *options);
+int pathbias_get_dropguards(const or_options_t *options);
+void pathbias_count_timeout(origin_circuit_t *circ);
+int pathbias_check_close(origin_circuit_t *circ, int reason);
+int pathbias_check_probe_response(circuit_t *circ, const cell_t *cell);
+void pathbias_count_use_attempt(origin_circuit_t *circ);
+void pathbias_mark_use_success(origin_circuit_t *circ);
+void pathbias_mark_use_rollback(origin_circuit_t *circ);
+const char *pathbias_state_to_string(path_state_t state);
+
+#endif
+
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index a685b0b27..96792b12c 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -11,6 +11,7 @@
 
 #include "or.h"
 #include "channel.h"
+#include "circpathbias.h"
 #include "circuitbuild.h"
 #include "circuitlist.h"
 #include "circuitstats.h"
@@ -58,13 +59,6 @@ static int onion_extend_cpath(origin_circuit_t *circ);
 static int count_acceptable_nodes(smartlist_t *routers);
 static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
 static int entry_guard_inc_circ_attempt_count(entry_guard_t *guard);
-static void pathbias_count_build_success(origin_circuit_t *circ);
-static void pathbias_count_successful_close(origin_circuit_t *circ);
-static void pathbias_count_collapse(origin_circuit_t *circ);
-static void pathbias_count_use_failed(origin_circuit_t *circ);
-static void pathbias_measure_use_rate(entry_guard_t *guard);
-static void pathbias_measure_close_rate(entry_guard_t *guard);
-static void pathbias_scale_use_rates(entry_guard_t *guard);
 
 /** This function tries to get a channel to the specified endpoint,
  * and then calls command_setup_channel() to give it the right
@@ -1084,1492 +1078,6 @@ circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data,
   return 0;
 }
 
-/** The minimum number of circuit attempts before we start
-  * thinking about warning about path bias and dropping guards */
-static int
-pathbias_get_min_circs(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_MIN_CIRC 150
-  if (options->PathBiasCircThreshold >= 5)
-    return options->PathBiasCircThreshold;
-  else
-    return networkstatus_get_param(NULL, "pb_mincircs",
-                                   DFLT_PATH_BIAS_MIN_CIRC,
-                                   5, INT32_MAX);
-}
-
-/** The circuit success rate below which we issue a notice */
-static double
-pathbias_get_notice_rate(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_NOTICE_PCT 70
-  if (options->PathBiasNoticeRate >= 0.0)
-    return options->PathBiasNoticeRate;
-  else
-    return networkstatus_get_param(NULL, "pb_noticepct",
-                                   DFLT_PATH_BIAS_NOTICE_PCT, 0, 100)/100.0;
-}
-
-/* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
-/** The circuit success rate below which we issue a warn */
-static double
-pathbias_get_warn_rate(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_WARN_PCT 50
-  if (options->PathBiasWarnRate >= 0.0)
-    return options->PathBiasWarnRate;
-  else
-    return networkstatus_get_param(NULL, "pb_warnpct",
-                                   DFLT_PATH_BIAS_WARN_PCT, 0, 100)/100.0;
-}
-
-/* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
-/**
- * The extreme rate is the rate at which we would drop the guard,
- * if pb_dropguard is also set. Otherwise we just warn.
- */
-double
-pathbias_get_extreme_rate(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_EXTREME_PCT 30
-  if (options->PathBiasExtremeRate >= 0.0)
-    return options->PathBiasExtremeRate;
-  else
-    return networkstatus_get_param(NULL, "pb_extremepct",
-                                   DFLT_PATH_BIAS_EXTREME_PCT, 0, 100)/100.0;
-}
-
-/* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
-/**
- * If 1, we actually disable use of guards that fall below
- * the extreme_pct.
- */
-int
-pathbias_get_dropguards(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_DROP_GUARDS 0
-  if (options->PathBiasDropGuards >= 0)
-    return options->PathBiasDropGuards;
-  else
-    return networkstatus_get_param(NULL, "pb_dropguards",
-                                   DFLT_PATH_BIAS_DROP_GUARDS, 0, 1);
-}
-
-/**
- * This is the number of circuits at which we scale our
- * counts by mult_factor/scale_factor. Note, this count is
- * not exact, as we only perform the scaling in the event
- * of no integer truncation.
- */
-static int
-pathbias_get_scale_threshold(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_SCALE_THRESHOLD 300
-  if (options->PathBiasScaleThreshold >= 10)
-    return options->PathBiasScaleThreshold;
-  else
-    return networkstatus_get_param(NULL, "pb_scalecircs",
-                                   DFLT_PATH_BIAS_SCALE_THRESHOLD, 10,
-                                   INT32_MAX);
-}
-
-/**
- * Compute the path bias scaling ratio from the consensus
- * parameters pb_multfactor/pb_scalefactor.
- *
- * Returns a value in (0, 1.0] which we multiply our pathbias
- * counts with to scale them down.
- */
-static double
-pathbias_get_scale_ratio(const or_options_t *options)
-{
-  /*
-   * The scale factor is the denominator for our scaling
-   * of circuit counts for our path bias window.
-   *
-   * Note that our use of doubles for the path bias state
-   * file means that powers of 2 work best here.
-   */
-  int denominator = networkstatus_get_param(NULL, "pb_scalefactor",
-                              2, 2, INT32_MAX);
-  (void) options;
-  /**
-   * The mult factor is the numerator for our scaling
-   * of circuit counts for our path bias window. It
-   * allows us to scale by fractions.
-   */
-  return networkstatus_get_param(NULL, "pb_multfactor",
-                              1, 1, denominator)/((double)denominator);
-}
-
-/** The minimum number of circuit usage attempts before we start
-  * thinking about warning about path use bias and dropping guards */
-static int
-pathbias_get_min_use(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_MIN_USE 20
-  if (options->PathBiasUseThreshold >= 3)
-    return options->PathBiasUseThreshold;
-  else
-    return networkstatus_get_param(NULL, "pb_minuse",
-                                   DFLT_PATH_BIAS_MIN_USE,
-                                   3, INT32_MAX);
-}
-
-/** The circuit use success rate below which we issue a notice */
-static double
-pathbias_get_notice_use_rate(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_NOTICE_USE_PCT 80
-  if (options->PathBiasNoticeUseRate >= 0.0)
-    return options->PathBiasNoticeUseRate;
-  else
-    return networkstatus_get_param(NULL, "pb_noticeusepct",
-                                   DFLT_PATH_BIAS_NOTICE_USE_PCT,
-                                   0, 100)/100.0;
-}
-
-/**
- * The extreme use rate is the rate at which we would drop the guard,
- * if pb_dropguard is also set. Otherwise we just warn.
- */
-double
-pathbias_get_extreme_use_rate(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_EXTREME_USE_PCT 60
-  if (options->PathBiasExtremeUseRate >= 0.0)
-    return options->PathBiasExtremeUseRate;
-  else
-    return networkstatus_get_param(NULL, "pb_extremeusepct",
-                                   DFLT_PATH_BIAS_EXTREME_USE_PCT,
-                                   0, 100)/100.0;
-}
-
-/**
- * This is the number of circuits at which we scale our
- * use counts by mult_factor/scale_factor. Note, this count is
- * not exact, as we only perform the scaling in the event
- * of no integer truncation.
- */
-static int
-pathbias_get_scale_use_threshold(const or_options_t *options)
-{
-#define DFLT_PATH_BIAS_SCALE_USE_THRESHOLD 100
-  if (options->PathBiasScaleUseThreshold >= 10)
-    return options->PathBiasScaleUseThreshold;
-  else
-    return networkstatus_get_param(NULL, "pb_scaleuse",
-                                   DFLT_PATH_BIAS_SCALE_USE_THRESHOLD,
-                                   10, INT32_MAX);
-}
-
-/**
- * Convert a Guard's path state to string.
- */
-const char *
-pathbias_state_to_string(path_state_t state)
-{
-  switch (state) {
-    case PATH_STATE_NEW_CIRC:
-      return "new";
-    case PATH_STATE_BUILD_ATTEMPTED:
-      return "build attempted";
-    case PATH_STATE_BUILD_SUCCEEDED:
-      return "build succeeded";
-    case PATH_STATE_USE_ATTEMPTED:
-      return "use attempted";
-    case PATH_STATE_USE_SUCCEEDED:
-      return "use succeeded";
-    case PATH_STATE_USE_FAILED:
-      return "use failed";
-    case PATH_STATE_ALREADY_COUNTED:
-      return "already counted";
-  }
-
-  return "unknown";
-}
-
-/**
- * This function decides if a circuit has progressed far enough to count
- * as a circuit "attempt". As long as end-to-end tagging is possible,
- * we assume the adversary will use it over hop-to-hop failure. Therefore,
- * we only need to account bias for the last hop. This should make us
- * much more resilient to ambient circuit failure, and also make that
- * failure easier to measure (we only need to measure Exit failure rates).
- */
-static int
-pathbias_is_new_circ_attempt(origin_circuit_t *circ)
-{
-#define N2N_TAGGING_IS_POSSIBLE
-#ifdef N2N_TAGGING_IS_POSSIBLE
-  /* cpath is a circular list. We want circs with more than one hop,
-   * and the second hop must be waiting for keys still (it's just
-   * about to get them). */
-  return circ->cpath &&
-         circ->cpath->next != circ->cpath &&
-         circ->cpath->next->state == CPATH_STATE_AWAITING_KEYS;
-#else
-  /* If tagging attacks are no longer possible, we probably want to
-   * count bias from the first hop. However, one could argue that
-   * timing-based tagging is still more useful than per-hop failure.
-   * In which case, we'd never want to use this.
-   */
-  return circ->cpath &&
-         circ->cpath->state == CPATH_STATE_AWAITING_KEYS;
-#endif
-}
-
-/**
- * Decide if the path bias code should count a circuit.
- *
- * @returns 1 if we should count it, 0 otherwise.
- */
-static int
-pathbias_should_count(origin_circuit_t *circ)
-{
-#define PATHBIAS_COUNT_INTERVAL (600)
-  static ratelim_t count_limit =
-    RATELIM_INIT(PATHBIAS_COUNT_INTERVAL);
-  char *rate_msg = NULL;
-
-  /* We can't do path bias accounting without entry guards.
-   * Testing and controller circuits also have no guards.
-   *
-   * We also don't count server-side rends, because their
-   * endpoint could be chosen maliciously.
-   * Similarly, we can't count client-side intro attempts,
-   * because clients can be manipulated into connecting to
-   * malicious intro points. */
-  if (get_options()->UseEntryGuards == 0 ||
-          circ->base_.purpose == CIRCUIT_PURPOSE_TESTING ||
-          circ->base_.purpose == CIRCUIT_PURPOSE_CONTROLLER ||
-          circ->base_.purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
-          circ->base_.purpose == CIRCUIT_PURPOSE_S_REND_JOINED ||
-          (circ->base_.purpose >= CIRCUIT_PURPOSE_C_INTRODUCING &&
-           circ->base_.purpose <= CIRCUIT_PURPOSE_C_INTRODUCE_ACKED)) {
-
-    /* Check to see if the shouldcount result has changed due to a
-     * unexpected purpose change that would affect our results.
-     *
-     * The reason we check the path state too here is because for the
-     * cannibalized versions of these purposes, we count them as successful
-     * before their purpose change.
-     */
-    if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED
-            && circ->path_state != PATH_STATE_ALREADY_COUNTED) {
-      log_info(LD_BUG,
-               "Circuit %d is now being ignored despite being counted "
-               "in the past. Purpose is %s, path state is %s",
-               circ->global_identifier,
-               circuit_purpose_to_string(circ->base_.purpose),
-               pathbias_state_to_string(circ->path_state));
-    }
-    circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
-    return 0;
-  }
-
-  /* Completely ignore one hop circuits */
-  if (circ->build_state->onehop_tunnel ||
-      circ->build_state->desired_path_len == 1) {
-    /* Check for inconsistency */
-    if (circ->build_state->desired_path_len != 1 ||
-        !circ->build_state->onehop_tunnel) {
-      if ((rate_msg = rate_limit_log(&count_limit, approx_time()))) {
-        log_info(LD_BUG,
-               "One-hop circuit has length %d. Path state is %s. "
-               "Circuit is a %s currently %s.%s",
-               circ->build_state->desired_path_len,
-               pathbias_state_to_string(circ->path_state),
-               circuit_purpose_to_string(circ->base_.purpose),
-               circuit_state_to_string(circ->base_.state),
-               rate_msg);
-        tor_free(rate_msg);
-      }
-      tor_fragile_assert();
-    }
-
-    /* Check to see if the shouldcount result has changed due to a
-     * unexpected change that would affect our results */
-    if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_COUNTED) {
-      log_info(LD_BUG,
-               "One-hop circuit %d is now being ignored despite being counted "
-               "in the past. Purpose is %s, path state is %s",
-               circ->global_identifier,
-               circuit_purpose_to_string(circ->base_.purpose),
-               pathbias_state_to_string(circ->path_state));
-    }
-    circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_IGNORED;
-    return 0;
-  }
-
-  /* Check to see if the shouldcount result has changed due to a
-   * unexpected purpose change that would affect our results */
-  if (circ->pathbias_shouldcount == PATHBIAS_SHOULDCOUNT_IGNORED) {
-      log_info(LD_BUG,
-              "Circuit %d is now being counted despite being ignored "
-              "in the past. Purpose is %s, path state is %s",
-              circ->global_identifier,
-              circuit_purpose_to_string(circ->base_.purpose),
-              pathbias_state_to_string(circ->path_state));
-  }
-  circ->pathbias_shouldcount = PATHBIAS_SHOULDCOUNT_COUNTED;
-
-  return 1;
-}
-
-/**
- * Check our circuit state to see if this is a successful circuit attempt.
- * If so, record it in the current guard's path bias circ_attempt count.
- *
- * Also check for several potential error cases for bug #6475.
- */
-static int
-pathbias_count_build_attempt(origin_circuit_t *circ)
-{
-#define CIRC_ATTEMPT_NOTICE_INTERVAL (600)
-  static ratelim_t circ_attempt_notice_limit =
-    RATELIM_INIT(CIRC_ATTEMPT_NOTICE_INTERVAL);
-  char *rate_msg = NULL;
-
-  if (!pathbias_should_count(circ)) {
-    return 0;
-  }
-
-  if (pathbias_is_new_circ_attempt(circ)) {
-    /* Help track down the real cause of bug #6475: */
-    if (circ->has_opened && circ->path_state != PATH_STATE_BUILD_ATTEMPTED) {
-      if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
-                                     approx_time()))) {
-        log_info(LD_BUG,
-                "Opened circuit is in strange path state %s. "
-                "Circuit is a %s currently %s.%s",
-                pathbias_state_to_string(circ->path_state),
-                circuit_purpose_to_string(circ->base_.purpose),
-                circuit_state_to_string(circ->base_.state),
-                rate_msg);
-        tor_free(rate_msg);
-      }
-    }
-
-    /* Don't re-count cannibalized circs.. */
-    if (!circ->has_opened) {
-      entry_guard_t *guard = NULL;
-
-      if (circ->cpath && circ->cpath->extend_info) {
-        guard = entry_guard_get_by_id_digest(
-                  circ->cpath->extend_info->identity_digest);
-      } else if (circ->base_.n_chan) {
-        guard =
-          entry_guard_get_by_id_digest(circ->base_.n_chan->identity_digest);
-      }
-
-      if (guard) {
-        if (circ->path_state == PATH_STATE_NEW_CIRC) {
-          circ->path_state = PATH_STATE_BUILD_ATTEMPTED;
-
-          if (entry_guard_inc_circ_attempt_count(guard) < 0) {
-            /* Bogus guard; we already warned. */
-            return -END_CIRC_REASON_TORPROTOCOL;
-          }
-        } else {
-          if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
-                  approx_time()))) {
-            log_info(LD_BUG,
-                   "Unopened circuit has strange path state %s. "
-                   "Circuit is a %s currently %s.%s",
-                   pathbias_state_to_string(circ->path_state),
-                   circuit_purpose_to_string(circ->base_.purpose),
-                   circuit_state_to_string(circ->base_.state),
-                   rate_msg);
-            tor_free(rate_msg);
-          }
-        }
-      } else {
-        if ((rate_msg = rate_limit_log(&circ_attempt_notice_limit,
-                approx_time()))) {
-          log_info(LD_CIRC,
-              "Unopened circuit has no known guard. "
-              "Circuit is a %s currently %s.%s",
-              circuit_purpose_to_string(circ->base_.purpose),
-              circuit_state_to_string(circ->base_.state),
-              rate_msg);
-          tor_free(rate_msg);
-        }
-      }
-    }
-  }
-
-  return 0;
-}
-
-/**
- * Check our circuit state to see if this is a successful circuit
- * completion. If so, record it in the current guard's path bias
- * success count.
- *
- * Also check for several potential error cases for bug #6475.
- */
-static void
-pathbias_count_build_success(origin_circuit_t *circ)
-{
-#define SUCCESS_NOTICE_INTERVAL (600)
-  static ratelim_t success_notice_limit =
-    RATELIM_INIT(SUCCESS_NOTICE_INTERVAL);
-  char *rate_msg = NULL;
-  entry_guard_t *guard = NULL;
-
-  if (!pathbias_should_count(circ)) {
-    return;
-  }
-
-  /* Don't count cannibalized/reused circs for path bias
-   * "build" success, since they get counted under "use" success. */
-  if (!circ->has_opened) {
-    if (circ->cpath && circ->cpath->extend_info) {
-      guard = entry_guard_get_by_id_digest(
-                circ->cpath->extend_info->identity_digest);
-    }
-
-    if (guard) {
-      if (circ->path_state == PATH_STATE_BUILD_ATTEMPTED) {
-        circ->path_state = PATH_STATE_BUILD_SUCCEEDED;
-        guard->circ_successes++;
-        entry_guards_changed();
-
-        log_info(LD_CIRC, "Got success count %f/%f for guard %s ($%s)",
-                 guard->circ_successes, guard->circ_attempts,
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN));
-      } else {
-        if ((rate_msg = rate_limit_log(&success_notice_limit,
-                approx_time()))) {
-          log_info(LD_BUG,
-              "Succeeded circuit is in strange path state %s. "
-              "Circuit is a %s currently %s.%s",
-              pathbias_state_to_string(circ->path_state),
-              circuit_purpose_to_string(circ->base_.purpose),
-              circuit_state_to_string(circ->base_.state),
-              rate_msg);
-          tor_free(rate_msg);
-        }
-      }
-
-      if (guard->circ_attempts < guard->circ_successes) {
-        log_notice(LD_BUG, "Unexpectedly high successes counts (%f/%f) "
-                 "for guard %s ($%s)",
-                 guard->circ_successes, guard->circ_attempts,
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN));
-      }
-    /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
-     * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
-     * No need to log that case. */
-    } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
-      if ((rate_msg = rate_limit_log(&success_notice_limit,
-              approx_time()))) {
-        log_info(LD_CIRC,
-            "Completed circuit has no known guard. "
-            "Circuit is a %s currently %s.%s",
-            circuit_purpose_to_string(circ->base_.purpose),
-            circuit_state_to_string(circ->base_.state),
-            rate_msg);
-        tor_free(rate_msg);
-      }
-    }
-  } else {
-    if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) {
-      if ((rate_msg = rate_limit_log(&success_notice_limit,
-              approx_time()))) {
-        log_info(LD_BUG,
-            "Opened circuit is in strange path state %s. "
-            "Circuit is a %s currently %s.%s",
-            pathbias_state_to_string(circ->path_state),
-            circuit_purpose_to_string(circ->base_.purpose),
-            circuit_state_to_string(circ->base_.state),
-            rate_msg);
-        tor_free(rate_msg);
-      }
-    }
-  }
-}
-
-/**
- * Record an attempt to use a circuit. Changes the circuit's
- * path state and update its guard's usage counter.
- *
- * Used for path bias usage accounting.
- */
-void
-pathbias_count_use_attempt(origin_circuit_t *circ)
-{
-  entry_guard_t *guard;
-
-  if (!pathbias_should_count(circ)) {
-    return;
-  }
-
-  if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) {
-    log_notice(LD_BUG,
-        "Used circuit is in strange path state %s. "
-        "Circuit is a %s currently %s.",
-        pathbias_state_to_string(circ->path_state),
-        circuit_purpose_to_string(circ->base_.purpose),
-        circuit_state_to_string(circ->base_.state));
-  } else if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
-    guard = entry_guard_get_by_id_digest(
-                circ->cpath->extend_info->identity_digest);
-    if (guard) {
-      pathbias_measure_use_rate(guard);
-      pathbias_scale_use_rates(guard);
-      guard->use_attempts++;
-      entry_guards_changed();
-
-      log_debug(LD_CIRC,
-               "Marked circuit %d (%f/%f) as used for guard %s ($%s).",
-               circ->global_identifier,
-               guard->use_successes, guard->use_attempts,
-               guard->nickname, hex_str(guard->identity, DIGEST_LEN));
-    }
-
-    circ->path_state = PATH_STATE_USE_ATTEMPTED;
-  } else {
-    /* Harmless but educational log message */
-    log_info(LD_CIRC,
-        "Used circuit %d is already in path state %s. "
-        "Circuit is a %s currently %s.",
-        circ->global_identifier,
-        pathbias_state_to_string(circ->path_state),
-        circuit_purpose_to_string(circ->base_.purpose),
-        circuit_state_to_string(circ->base_.state));
-  }
-
-  return;
-}
-
-/**
- * Check the circuit's path state is appropriate and mark it as
- * successfully used. Used for path bias usage accounting.
- *
- * We don't actually increment the guard's counters until
- * pathbias_check_close(), because the circuit can still transition
- * back to PATH_STATE_USE_ATTEMPTED if a stream fails later (this
- * is done so we can probe the circuit for liveness at close).
- */
-void
-pathbias_mark_use_success(origin_circuit_t *circ)
-{
-  if (!pathbias_should_count(circ)) {
-    return;
-  }
-
-  if (circ->path_state < PATH_STATE_USE_ATTEMPTED) {
-    log_notice(LD_BUG,
-        "Used circuit %d is in strange path state %s. "
-        "Circuit is a %s currently %s.",
-        circ->global_identifier,
-        pathbias_state_to_string(circ->path_state),
-        circuit_purpose_to_string(circ->base_.purpose),
-        circuit_state_to_string(circ->base_.state));
-
-    pathbias_count_use_attempt(circ);
-  }
-
-  /* We don't do any accounting at the guard until actual circuit close */
-  circ->path_state = PATH_STATE_USE_SUCCEEDED;
-
-  return;
-}
-
-/**
- * If a stream ever detatches from a circuit in a retriable way,
- * we need to mark this circuit as still needing either another
- * successful stream, or in need of a probe.
- *
- * An adversary could let the first stream request succeed (ie the
- * resolve), but then tag and timeout the remainder (via cell
- * dropping), forcing them on new circuits.
- *
- * Rolling back the state will cause us to probe such circuits, which
- * should lead to probe failures in the event of such tagging due to
- * either unrecognized cells coming in while we wait for the probe,
- * or the cipher state getting out of sync in the case of dropped cells.
- */
-void
-pathbias_mark_use_rollback(origin_circuit_t *circ)
-{
-  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
-    log_info(LD_CIRC,
-             "Rolling back pathbias use state to 'attempted' for detached "
-             "circuit %d", circ->global_identifier);
-    circ->path_state = PATH_STATE_USE_ATTEMPTED;
-  }
-}
-
-/**
- * Actually count a circuit success towards a guard's usage counters
- * if the path state is appropriate.
- */
-static void
-pathbias_count_use_success(origin_circuit_t *circ)
-{
-  entry_guard_t *guard;
-
-  if (!pathbias_should_count(circ)) {
-    return;
-  }
-
-  if (circ->path_state != PATH_STATE_USE_SUCCEEDED) {
-    log_notice(LD_BUG,
-        "Successfully used circuit %d is in strange path state %s. "
-        "Circuit is a %s currently %s.",
-        circ->global_identifier,
-        pathbias_state_to_string(circ->path_state),
-        circuit_purpose_to_string(circ->base_.purpose),
-        circuit_state_to_string(circ->base_.state));
-  } else {
-    guard = entry_guard_get_by_id_digest(
-                circ->cpath->extend_info->identity_digest);
-    if (guard) {
-      guard->use_successes++;
-      entry_guards_changed();
-
-      if (guard->use_attempts < guard->use_successes) {
-        log_notice(LD_BUG, "Unexpectedly high use successes counts (%f/%f) "
-                 "for guard %s=%s",
-                 guard->use_successes, guard->use_attempts,
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN));
-      }
-
-      log_debug(LD_CIRC,
-                "Marked circuit %d (%f/%f) as used successfully for guard "
-                "%s ($%s).",
-                circ->global_identifier, guard->use_successes,
-                guard->use_attempts, guard->nickname,
-                hex_str(guard->identity, DIGEST_LEN));
-    }
-  }
-
-  return;
-}
-
-/**
- * Send a probe down a circuit that the client attempted to use,
- * but for which the stream timed out/failed. The probe is a
- * RELAY_BEGIN cell with a 0.a.b.c destination address, which
- * the exit will reject and reply back, echoing that address.
- *
- * The reason for such probes is because it is possible to bias
- * a user's paths simply by causing timeouts, and these timeouts
- * are not possible to differentiate from unresponsive servers.
- *
- * The probe is sent at the end of the circuit lifetime for two
- * reasons: to prevent cryptographic taggers from being able to
- * drop cells to cause timeouts, and to prevent easy recognition
- * of probes before any real client traffic happens.
- *
- * Returns -1 if we couldn't probe, 0 otherwise.
- */
-static int
-pathbias_send_usable_probe(circuit_t *circ)
-{
-  /* Based on connection_ap_handshake_send_begin() */
-  char payload[CELL_PAYLOAD_SIZE];
-  int payload_len;
-  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
-  crypt_path_t *cpath_layer = NULL;
-  char *probe_nonce = NULL;
-
-  tor_assert(ocirc);
-
-  cpath_layer = ocirc->cpath->prev;
-
-  if (cpath_layer->state != CPATH_STATE_OPEN) {
-    /* This can happen for cannibalized circuits. Their
-     * last hop isn't yet open */
-    log_info(LD_CIRC,
-             "Got pathbias probe request for unopened circuit %d. "
-             "Opened %d, len %d", ocirc->global_identifier,
-             ocirc->has_opened, ocirc->build_state->desired_path_len);
-    return -1;
-  }
-
-  /* We already went down this road. */
-  if (circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING &&
-      ocirc->pathbias_probe_id) {
-    log_info(LD_CIRC,
-             "Got pathbias probe request for circuit %d with "
-             "outstanding probe", ocirc->global_identifier);
-    return -1;
-  }
-
-  /* Can't probe if the channel isn't open */
-  if (circ->n_chan == NULL ||
-      (circ->n_chan->state != CHANNEL_STATE_OPEN
-       && circ->n_chan->state != CHANNEL_STATE_MAINT)) {
-    log_info(LD_CIRC,
-             "Skipping pathbias probe for circuit %d: Channel is not open.",
-             ocirc->global_identifier);
-    return -1;
-  }
-
-  circuit_change_purpose(circ, CIRCUIT_PURPOSE_PATH_BIAS_TESTING);
-
-  /* Update timestamp for when circuit_expire_building() should kill us */
-  tor_gettimeofday(&circ->timestamp_began);
-
-  /* Generate a random address for the nonce */
-  crypto_rand((char*)&ocirc->pathbias_probe_nonce,
-              sizeof(ocirc->pathbias_probe_nonce));
-  ocirc->pathbias_probe_nonce &= 0x00ffffff;
-  probe_nonce = tor_dup_ip(ocirc->pathbias_probe_nonce);
-
-  tor_snprintf(payload,RELAY_PAYLOAD_SIZE, "%s:25", probe_nonce);
-  payload_len = (int)strlen(payload)+1;
-
-  // XXX: need this? Can we assume ipv4 will always be supported?
-  // If not, how do we tell?
-  //if (payload_len <= RELAY_PAYLOAD_SIZE - 4 && edge_conn->begincell_flags) {
-  //  set_uint32(payload + payload_len, htonl(edge_conn->begincell_flags));
-  //  payload_len += 4;
-  //}
-
-  /* Generate+Store stream id, make sure it's non-zero */
-  ocirc->pathbias_probe_id = get_unique_stream_id_by_circ(ocirc);
-
-  if (ocirc->pathbias_probe_id==0) {
-    log_warn(LD_CIRC,
-             "Ran out of stream IDs on circuit %u during "
-             "pathbias probe attempt.", ocirc->global_identifier);
-    tor_free(probe_nonce);
-    return -1;
-  }
-
-  log_info(LD_CIRC,
-           "Sending pathbias testing cell to %s:25 on stream %d for circ %d.",
-           probe_nonce, ocirc->pathbias_probe_id, ocirc->global_identifier);
-  tor_free(probe_nonce);
-
-  /* Send a test relay cell */
-  if (relay_send_command_from_edge(ocirc->pathbias_probe_id, circ,
-                               RELAY_COMMAND_BEGIN, payload,
-                               payload_len, cpath_layer) < 0) {
-    log_notice(LD_CIRC,
-               "Failed to send pathbias probe cell on circuit %d.",
-               ocirc->global_identifier);
-    return -1;
-  }
-
-  /* Mark it freshly dirty so it doesn't get expired in the meantime */
-  circ->timestamp_dirty = time(NULL);
-
-  return 0;
-}
-
-/**
- * Check the response to a pathbias probe, to ensure the
- * cell is recognized and the nonce and other probe
- * characteristics are as expected.
- *
- * If the response is valid, return 0. Otherwise return < 0.
- */
-int
-pathbias_check_probe_response(circuit_t *circ, const cell_t *cell)
-{
-  /* Based on connection_edge_process_relay_cell() */
-  relay_header_t rh;
-  int reason;
-  uint32_t ipv4_host;
-  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
-
-  tor_assert(cell);
-  tor_assert(ocirc);
-  tor_assert(circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING);
-
-  relay_header_unpack(&rh, cell->payload);
-
-  reason = rh.length > 0 ?
-        get_uint8(cell->payload+RELAY_HEADER_SIZE) : END_STREAM_REASON_MISC;
-
-  if (rh.command == RELAY_COMMAND_END &&
-      reason == END_STREAM_REASON_EXITPOLICY &&
-      ocirc->pathbias_probe_id == rh.stream_id) {
-
-    /* Check length+extract host: It is in network order after the reason code.
-     * See connection_edge_end(). */
-    if (rh.length < 9) { /* reason+ipv4+dns_ttl */
-      log_notice(LD_PROTOCOL,
-             "Short path bias probe response length field (%d).", rh.length);
-      return - END_CIRC_REASON_TORPROTOCOL;
-    }
-
-    ipv4_host = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+1));
-
-    /* Check nonce */
-    if (ipv4_host == ocirc->pathbias_probe_nonce) {
-      pathbias_mark_use_success(ocirc);
-      circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
-      log_info(LD_CIRC,
-               "Got valid path bias probe back for circ %d, stream %d.",
-               ocirc->global_identifier, ocirc->pathbias_probe_id);
-      return 0;
-    } else {
-      log_notice(LD_CIRC,
-               "Got strange probe value 0x%x vs 0x%x back for circ %d, "
-               "stream %d.", ipv4_host, ocirc->pathbias_probe_nonce,
-               ocirc->global_identifier, ocirc->pathbias_probe_id);
-      return -1;
-    }
-  }
-  log_info(LD_CIRC,
-             "Got another cell back back on pathbias probe circuit %d: "
-             "Command: %d, Reason: %d, Stream-id: %d",
-             ocirc->global_identifier, rh.command, reason, rh.stream_id);
-  return -1;
-}
-
-/**
- * Check if a circuit was used and/or closed successfully.
- *
- * If we attempted to use the circuit to carry a stream but failed
- * for whatever reason, or if the circuit mysteriously died before
- * we could attach any streams, record these two cases.
- *
- * If we *have* successfully used the circuit, or it appears to
- * have been closed by us locally, count it as a success.
- *
- * Returns 0 if we're done making decisions with the circ,
- * or -1 if we want to probe it first.
- */
-int
-pathbias_check_close(origin_circuit_t *ocirc, int reason)
-{
-  circuit_t *circ = &ocirc->base_;
-
-  if (!pathbias_should_count(ocirc)) {
-    return 0;
-  }
-
-  switch (ocirc->path_state) {
-    /* If the circuit was closed after building, but before use, we need
-     * to ensure we were the ones who tried to close it (and not a remote
-     * actor). */
-    case PATH_STATE_BUILD_SUCCEEDED:
-      if (reason & END_CIRC_REASON_FLAG_REMOTE) {
-        /* Remote circ close reasons on an unused circuit all could be bias */
-        log_info(LD_CIRC,
-            "Circuit %d remote-closed without successful use for reason %d. "
-            "Circuit purpose %d currently %d,%s. Len %d.",
-            ocirc->global_identifier,
-            reason, circ->purpose, ocirc->has_opened,
-            circuit_state_to_string(circ->state),
-            ocirc->build_state->desired_path_len);
-        pathbias_count_collapse(ocirc);
-      } else if ((reason & ~END_CIRC_REASON_FLAG_REMOTE)
-                  == END_CIRC_REASON_CHANNEL_CLOSED &&
-                 circ->n_chan &&
-                 circ->n_chan->reason_for_closing
-                  != CHANNEL_CLOSE_REQUESTED) {
-        /* If we didn't close the channel ourselves, it could be bias */
-        /* XXX: Only count bias if the network is live?
-         * What about clock jumps/suspends? */
-        log_info(LD_CIRC,
-            "Circuit %d's channel closed without successful use for reason "
-            "%d, channel reason %d. Circuit purpose %d currently %d,%s. Len "
-            "%d.", ocirc->global_identifier,
-            reason, circ->n_chan->reason_for_closing,
-            circ->purpose, ocirc->has_opened,
-            circuit_state_to_string(circ->state),
-            ocirc->build_state->desired_path_len);
-        pathbias_count_collapse(ocirc);
-      } else {
-        pathbias_count_successful_close(ocirc);
-      }
-      break;
-
-    /* If we tried to use a circuit but failed, we should probe it to ensure
-     * it has not been tampered with. */
-    case PATH_STATE_USE_ATTEMPTED:
-      /* XXX: Only probe and/or count failure if the network is live?
-       * What about clock jumps/suspends? */
-      if (pathbias_send_usable_probe(circ) == 0)
-        return -1;
-      else
-        pathbias_count_use_failed(ocirc);
-
-      /* Any circuit where there were attempted streams but no successful
-       * streams could be bias */
-      log_info(LD_CIRC,
-            "Circuit %d closed without successful use for reason %d. "
-            "Circuit purpose %d currently %d,%s. Len %d.",
-            ocirc->global_identifier,
-            reason, circ->purpose, ocirc->has_opened,
-            circuit_state_to_string(circ->state),
-            ocirc->build_state->desired_path_len);
-      break;
-
-    case PATH_STATE_USE_SUCCEEDED:
-      pathbias_count_successful_close(ocirc);
-      pathbias_count_use_success(ocirc);
-      break;
-
-    case PATH_STATE_USE_FAILED:
-      pathbias_count_use_failed(ocirc);
-      break;
-
-    case PATH_STATE_NEW_CIRC:
-    case PATH_STATE_BUILD_ATTEMPTED:
-    case PATH_STATE_ALREADY_COUNTED:
-    default:
-      // Other states are uninteresting. No stats to count.
-      break;
-  }
-
-  ocirc->path_state = PATH_STATE_ALREADY_COUNTED;
-
-  return 0;
-}
-
-/**
- * Count a successfully closed circuit.
- */
-static void
-pathbias_count_successful_close(origin_circuit_t *circ)
-{
-  entry_guard_t *guard = NULL;
-  if (!pathbias_should_count(circ)) {
-    return;
-  }
-
-  if (circ->cpath && circ->cpath->extend_info) {
-    guard = entry_guard_get_by_id_digest(
-              circ->cpath->extend_info->identity_digest);
-  }
-
-  if (guard) {
-    /* In the long run: circuit_success ~= successful_circuit_close +
-     *                                     circ_failure + stream_failure */
-    guard->successful_circuits_closed++;
-    entry_guards_changed();
-  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
-   /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
-    * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
-    * No need to log that case. */
-    log_info(LD_CIRC,
-        "Successfully closed circuit has no known guard. "
-        "Circuit is a %s currently %s",
-        circuit_purpose_to_string(circ->base_.purpose),
-        circuit_state_to_string(circ->base_.state));
-  }
-}
-
-/**
- * Count a circuit that fails after it is built, but before it can
- * carry any traffic.
- *
- * This is needed because there are ways to destroy a
- * circuit after it has successfully completed. Right now, this is
- * used for purely informational/debugging purposes.
- */
-static void
-pathbias_count_collapse(origin_circuit_t *circ)
-{
-  entry_guard_t *guard = NULL;
-
-  if (!pathbias_should_count(circ)) {
-    return;
-  }
-
-  if (circ->cpath && circ->cpath->extend_info) {
-    guard = entry_guard_get_by_id_digest(
-              circ->cpath->extend_info->identity_digest);
-  }
-
-  if (guard) {
-    guard->collapsed_circuits++;
-    entry_guards_changed();
-  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
-   /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
-    * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
-    * No need to log that case. */
-    log_info(LD_CIRC,
-        "Destroyed circuit has no known guard. "
-        "Circuit is a %s currently %s",
-        circuit_purpose_to_string(circ->base_.purpose),
-        circuit_state_to_string(circ->base_.state));
-  }
-}
-
-/**
- * Count a known failed circuit (because we could not probe it).
- *
- * This counter is informational.
- */
-static void
-pathbias_count_use_failed(origin_circuit_t *circ)
-{
-  entry_guard_t *guard = NULL;
-  if (!pathbias_should_count(circ)) {
-    return;
-  }
-
-  if (circ->cpath && circ->cpath->extend_info) {
-    guard = entry_guard_get_by_id_digest(
-              circ->cpath->extend_info->identity_digest);
-  }
-
-  if (guard) {
-    guard->unusable_circuits++;
-    entry_guards_changed();
-  } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
-   /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
-    * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
-    * No need to log that case. */
-    /* XXX note cut-and-paste code in this function compared to nearby
-     * functions. Would be nice to refactor. -RD */
-    log_info(LD_CIRC,
-        "Stream-failing circuit has no known guard. "
-        "Circuit is a %s currently %s",
-        circuit_purpose_to_string(circ->base_.purpose),
-        circuit_state_to_string(circ->base_.state));
-  }
-}
-
-/**
- * Count timeouts for path bias log messages.
- *
- * These counts are purely informational.
- */
-void
-pathbias_count_timeout(origin_circuit_t *circ)
-{
-  entry_guard_t *guard = NULL;
-
-  if (!pathbias_should_count(circ)) {
-    return;
-  }
-
-  /* For hidden service circs, they can actually be used
-   * successfully and then time out later (because
-   * the other side declines to use them). */
-  if (circ->path_state == PATH_STATE_USE_SUCCEEDED) {
-    return;
-  }
-
-  if (circ->cpath && circ->cpath->extend_info) {
-    guard = entry_guard_get_by_id_digest(
-              circ->cpath->extend_info->identity_digest);
-  }
-
-  if (guard) {
-    guard->timeouts++;
-    entry_guards_changed();
-  }
-}
-
-/**
- * Helper function to count all of the currently opened circuits
- * for a guard that are in a given path state range. The state
- * range is inclusive on both ends.
- */
-static int
-pathbias_count_circs_in_states(entry_guard_t *guard,
-                              path_state_t from,
-                              path_state_t to)
-{
-  circuit_t *circ;
-  int open_circuits = 0;
-
-  /* Count currently open circuits. Give them the benefit of the doubt. */
-  TOR_LIST_FOREACH(circ, circuit_get_global_list(), head) {
-    origin_circuit_t *ocirc = NULL;
-    if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */
-        circ->marked_for_close) /* already counted */
-      continue;
-
-    ocirc = TO_ORIGIN_CIRCUIT(circ);
-
-    if (!ocirc->cpath || !ocirc->cpath->extend_info)
-      continue;
-
-    if (ocirc->path_state >= from &&
-        ocirc->path_state <= to &&
-        pathbias_should_count(ocirc) &&
-        fast_memeq(guard->identity,
-                   ocirc->cpath->extend_info->identity_digest,
-                   DIGEST_LEN)) {
-      log_debug(LD_CIRC, "Found opened circuit %d in path_state %s",
-                ocirc->global_identifier,
-                pathbias_state_to_string(ocirc->path_state));
-      open_circuits++;
-    }
-  }
-
-  return open_circuits;
-}
-
-/**
- * Return the number of circuits counted as successfully closed for
- * this guard.
- *
- * Also add in the currently open circuits to give them the benefit
- * of the doubt.
- */
-double
-pathbias_get_close_success_count(entry_guard_t *guard)
-{
-  return guard->successful_circuits_closed +
-         pathbias_count_circs_in_states(guard,
-                       PATH_STATE_BUILD_SUCCEEDED,
-                       PATH_STATE_USE_SUCCEEDED);
-}
-
-/**
- * Return the number of circuits counted as successfully used
- * this guard.
- *
- * Also add in the currently open circuits that we are attempting
- * to use to give them the benefit of the doubt.
- */
-double
-pathbias_get_use_success_count(entry_guard_t *guard)
-{
-  return guard->use_successes +
-         pathbias_count_circs_in_states(guard,
-                       PATH_STATE_USE_ATTEMPTED,
-                       PATH_STATE_USE_SUCCEEDED);
-}
-
-/**
- * Check the path bias use rate against our consensus parameter limits.
- *
- * Emits a log message if the use success rates are too low.
- *
- * If pathbias_get_dropguards() is set, we also disable the use of
- * very failure prone guards.
- */
-static void
-pathbias_measure_use_rate(entry_guard_t *guard)
-{
-  const or_options_t *options = get_options();
-
-  if (guard->use_attempts > pathbias_get_min_use(options)) {
-    /* Note: We rely on the < comparison here to allow us to set a 0
-     * rate and disable the feature entirely. If refactoring, don't
-     * change to <= */
-    if (pathbias_get_use_success_count(guard)/guard->use_attempts
-        < pathbias_get_extreme_use_rate(options)) {
-      /* Dropping is currently disabled by default. */
-      if (pathbias_get_dropguards(options)) {
-        if (!guard->path_bias_disabled) {
-          log_warn(LD_CIRC,
-                 "Your Guard %s ($%s) is failing to carry an extremely large "
-                 "amount of stream on its circuits. "
-                 "To avoid potential route manipulation attacks, Tor has "
-                 "disabled use of this guard. "
-                 "Use counts are %ld/%ld. Success counts are %ld/%ld. "
-                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
-                 "and %ld timed out. "
-                 "For reference, your timeout cutoff is %ld seconds.",
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
-                 tor_lround(pathbias_get_use_success_count(guard)),
-                 tor_lround(guard->use_attempts),
-                 tor_lround(pathbias_get_close_success_count(guard)),
-                 tor_lround(guard->circ_attempts),
-                 tor_lround(guard->circ_successes),
-                 tor_lround(guard->unusable_circuits),
-                 tor_lround(guard->collapsed_circuits),
-                 tor_lround(guard->timeouts),
-                 tor_lround(get_circuit_build_close_time_ms()/1000));
-          guard->path_bias_disabled = 1;
-          guard->bad_since = approx_time();
-          entry_guards_changed();
-          return;
-        }
-      } else if (!guard->path_bias_use_extreme) {
-        guard->path_bias_use_extreme = 1;
-        log_warn(LD_CIRC,
-                 "Your Guard %s ($%s) is failing to carry an extremely large "
-                 "amount of streams on its circuits. "
-                 "This could indicate a route manipulation attack, network "
-                 "overload, bad local network connectivity, or a bug. "
-                 "Use counts are %ld/%ld. Success counts are %ld/%ld. "
-                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
-                 "and %ld timed out. "
-                 "For reference, your timeout cutoff is %ld seconds.",
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
-                 tor_lround(pathbias_get_use_success_count(guard)),
-                 tor_lround(guard->use_attempts),
-                 tor_lround(pathbias_get_close_success_count(guard)),
-                 tor_lround(guard->circ_attempts),
-                 tor_lround(guard->circ_successes),
-                 tor_lround(guard->unusable_circuits),
-                 tor_lround(guard->collapsed_circuits),
-                 tor_lround(guard->timeouts),
-                 tor_lround(get_circuit_build_close_time_ms()/1000));
-      }
-    } else if (pathbias_get_use_success_count(guard)/guard->use_attempts
-               < pathbias_get_notice_use_rate(options)) {
-      if (!guard->path_bias_use_noticed) {
-        guard->path_bias_use_noticed = 1;
-        log_notice(LD_CIRC,
-                 "Your Guard %s ($%s) is failing to carry more streams on its "
-                 "circuits than usual. "
-                 "Most likely this means the Tor network is overloaded "
-                 "or your network connection is poor. "
-                 "Use counts are %ld/%ld. Success counts are %ld/%ld. "
-                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
-                 "and %ld timed out. "
-                 "For reference, your timeout cutoff is %ld seconds.",
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
-                 tor_lround(pathbias_get_use_success_count(guard)),
-                 tor_lround(guard->use_attempts),
-                 tor_lround(pathbias_get_close_success_count(guard)),
-                 tor_lround(guard->circ_attempts),
-                 tor_lround(guard->circ_successes),
-                 tor_lround(guard->unusable_circuits),
-                 tor_lround(guard->collapsed_circuits),
-                 tor_lround(guard->timeouts),
-                 tor_lround(get_circuit_build_close_time_ms()/1000));
-      }
-    }
-  }
-}
-
-/**
- * Check the path bias circuit close status rates against our consensus
- * parameter limits.
- *
- * Emits a log message if the use success rates are too low.
- *
- * If pathbias_get_dropguards() is set, we also disable the use of
- * very failure prone guards.
- *
- * XXX: This function shares similar log messages and checks to
- * pathbias_measure_use_rate(). It may be possible to combine them
- * eventually, especially if we can ever remove the need for 3
- * levels of closure warns (if the overall circuit failure rate
- * goes down with ntor). One way to do so would be to multiply
- * the build rate with the use rate to get an idea of the total
- * fraction of the total network paths the user is able to use.
- * See ticket #8159.
- */
-static void
-pathbias_measure_close_rate(entry_guard_t *guard)
-{
-  const or_options_t *options = get_options();
-
-  if (guard->circ_attempts > pathbias_get_min_circs(options)) {
-    /* Note: We rely on the < comparison here to allow us to set a 0
-     * rate and disable the feature entirely. If refactoring, don't
-     * change to <= */
-    if (pathbias_get_close_success_count(guard)/guard->circ_attempts
-        < pathbias_get_extreme_rate(options)) {
-      /* Dropping is currently disabled by default. */
-      if (pathbias_get_dropguards(options)) {
-        if (!guard->path_bias_disabled) {
-          log_warn(LD_CIRC,
-                 "Your Guard %s ($%s) is failing an extremely large "
-                 "amount of circuits. "
-                 "To avoid potential route manipulation attacks, Tor has "
-                 "disabled use of this guard. "
-                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
-                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
-                 "and %ld timed out. "
-                 "For reference, your timeout cutoff is %ld seconds.",
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
-                 tor_lround(pathbias_get_close_success_count(guard)),
-                 tor_lround(guard->circ_attempts),
-                 tor_lround(pathbias_get_use_success_count(guard)),
-                 tor_lround(guard->use_attempts),
-                 tor_lround(guard->circ_successes),
-                 tor_lround(guard->unusable_circuits),
-                 tor_lround(guard->collapsed_circuits),
-                 tor_lround(guard->timeouts),
-                 tor_lround(get_circuit_build_close_time_ms()/1000));
-          guard->path_bias_disabled = 1;
-          guard->bad_since = approx_time();
-          entry_guards_changed();
-          return;
-        }
-      } else if (!guard->path_bias_extreme) {
-        guard->path_bias_extreme = 1;
-        log_warn(LD_CIRC,
-                 "Your Guard %s ($%s) is failing an extremely large "
-                 "amount of circuits. "
-                 "This could indicate a route manipulation attack, "
-                 "extreme network overload, or a bug. "
-                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
-                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
-                 "and %ld timed out. "
-                 "For reference, your timeout cutoff is %ld seconds.",
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
-                 tor_lround(pathbias_get_close_success_count(guard)),
-                 tor_lround(guard->circ_attempts),
-                 tor_lround(pathbias_get_use_success_count(guard)),
-                 tor_lround(guard->use_attempts),
-                 tor_lround(guard->circ_successes),
-                 tor_lround(guard->unusable_circuits),
-                 tor_lround(guard->collapsed_circuits),
-                 tor_lround(guard->timeouts),
-                 tor_lround(get_circuit_build_close_time_ms()/1000));
-      }
-    } else if (pathbias_get_close_success_count(guard)/guard->circ_attempts
-                < pathbias_get_warn_rate(options)) {
-      if (!guard->path_bias_warned) {
-        guard->path_bias_warned = 1;
-        log_warn(LD_CIRC,
-                 "Your Guard %s ($%s) is failing a very large "
-                 "amount of circuits. "
-                 "Most likely this means the Tor network is "
-                 "overloaded, but it could also mean an attack against "
-                 "you or potentially the guard itself. "
-                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
-                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
-                 "and %ld timed out. "
-                 "For reference, your timeout cutoff is %ld seconds.",
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
-                 tor_lround(pathbias_get_close_success_count(guard)),
-                 tor_lround(guard->circ_attempts),
-                 tor_lround(pathbias_get_use_success_count(guard)),
-                 tor_lround(guard->use_attempts),
-                 tor_lround(guard->circ_successes),
-                 tor_lround(guard->unusable_circuits),
-                 tor_lround(guard->collapsed_circuits),
-                 tor_lround(guard->timeouts),
-                 tor_lround(get_circuit_build_close_time_ms()/1000));
-      }
-    } else if (pathbias_get_close_success_count(guard)/guard->circ_attempts
-               < pathbias_get_notice_rate(options)) {
-      if (!guard->path_bias_noticed) {
-        guard->path_bias_noticed = 1;
-        log_notice(LD_CIRC,
-                 "Your Guard %s ($%s) is failing more circuits than "
-                 "usual. "
-                 "Most likely this means the Tor network is overloaded. "
-                 "Success counts are %ld/%ld. Use counts are %ld/%ld. "
-                 "%ld circuits completed, %ld were unusable, %ld collapsed, "
-                 "and %ld timed out. "
-                 "For reference, your timeout cutoff is %ld seconds.",
-                 guard->nickname, hex_str(guard->identity, DIGEST_LEN),
-                 tor_lround(pathbias_get_close_success_count(guard)),
-                 tor_lround(guard->circ_attempts),
-                 tor_lround(pathbias_get_use_success_count(guard)),
-                 tor_lround(guard->use_attempts),
-                 tor_lround(guard->circ_successes),
-                 tor_lround(guard->unusable_circuits),
-                 tor_lround(guard->collapsed_circuits),
-                 tor_lround(guard->timeouts),
-                 tor_lround(get_circuit_build_close_time_ms()/1000));
-      }
-    }
-  }
-}
-
-/**
- * This function scales the path bias use rates if we have
- * more data than the scaling threshold. This allows us to
- * be more sensitive to recent measurements.
- *
- * XXX: The attempt count transfer stuff here might be done
- * better by keeping separate pending counters that get
- * transfered at circuit close. See ticket #8160.
- */
-static void
-pathbias_scale_close_rates(entry_guard_t *guard)
-{
-  const or_options_t *options = get_options();
-
-  /* If we get a ton of circuits, just scale everything down */
-  if (guard->circ_attempts > pathbias_get_scale_threshold(options)) {
-    double scale_ratio = pathbias_get_scale_ratio(options);
-    int opened_attempts = pathbias_count_circs_in_states(guard,
-            PATH_STATE_BUILD_ATTEMPTED, PATH_STATE_BUILD_ATTEMPTED);
-    int opened_built = pathbias_count_circs_in_states(guard,
-                        PATH_STATE_BUILD_SUCCEEDED,
-                        PATH_STATE_USE_FAILED);
-    /* Verify that the counts are sane before and after scaling */
-    int counts_are_sane = (guard->circ_attempts >= guard->circ_successes);
-
-    guard->circ_attempts -= (opened_attempts+opened_built);
-    guard->circ_successes -= opened_built;
-
-    guard->circ_attempts *= scale_ratio;
-    guard->circ_successes *= scale_ratio;
-    guard->timeouts *= scale_ratio;
-    guard->successful_circuits_closed *= scale_ratio;
-    guard->collapsed_circuits *= scale_ratio;
-    guard->unusable_circuits *= scale_ratio;
-
-    guard->circ_attempts += (opened_attempts+opened_built);
-    guard->circ_successes += opened_built;
-
-    entry_guards_changed();
-
-    log_info(LD_CIRC,
-             "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard "
-             "%s ($%s)",
-             guard->circ_successes, guard->successful_circuits_closed,
-             guard->circ_attempts, opened_built, opened_attempts,
-             guard->nickname, hex_str(guard->identity, DIGEST_LEN));
-
-    /* Have the counts just become invalid by this scaling attempt? */
-    if (counts_are_sane && guard->circ_attempts < guard->circ_successes) {
-      log_notice(LD_BUG,
-               "Scaling has mangled pathbias counts to %f/%f (%d/%d open) "
-               "for guard %s ($%s)",
-               guard->circ_successes, guard->circ_attempts, opened_built,
-               opened_attempts, guard->nickname,
-               hex_str(guard->identity, DIGEST_LEN));
-    }
-  }
-}
-
-/**
- * This function scales the path bias circuit close rates if we have
- * more data than the scaling threshold. This allows us to be more
- * sensitive to recent measurements.
- *
- * XXX: The attempt count transfer stuff here might be done
- * better by keeping separate pending counters that get
- * transfered at circuit close. See ticket #8160.
- */
-void
-pathbias_scale_use_rates(entry_guard_t *guard)
-{
-  const or_options_t *options = get_options();
-
-  /* If we get a ton of circuits, just scale everything down */
-  if (guard->use_attempts > pathbias_get_scale_use_threshold(options)) {
-    double scale_ratio = pathbias_get_scale_ratio(options);
-    int opened_attempts = pathbias_count_circs_in_states(guard,
-            PATH_STATE_USE_ATTEMPTED, PATH_STATE_USE_SUCCEEDED);
-    /* Verify that the counts are sane before and after scaling */
-    int counts_are_sane = (guard->use_attempts >= guard->use_successes);
-
-    guard->use_attempts -= opened_attempts;
-
-    guard->use_attempts *= scale_ratio;
-    guard->use_successes *= scale_ratio;
-
-    guard->use_attempts += opened_attempts;
-
-    log_info(LD_CIRC,
-           "Scaled pathbias use counts to %f/%f (%d open) for guard %s ($%s)",
-           guard->use_successes, guard->use_attempts, opened_attempts,
-           guard->nickname, hex_str(guard->identity, DIGEST_LEN));
-
-    /* Have the counts just become invalid by this scaling attempt? */
-    if (counts_are_sane && guard->use_attempts < guard->use_successes) {
-      log_notice(LD_BUG,
-               "Scaling has mangled pathbias usage counts to %f/%f "
-               "(%d open) for guard %s ($%s)",
-               guard->circ_successes, guard->circ_attempts,
-               opened_attempts, guard->nickname,
-               hex_str(guard->identity, DIGEST_LEN));
-    }
-
-    entry_guards_changed();
-  }
-}
-
 /** Increment the number of times we successfully extended a circuit to
  * <b>guard</b>, first checking if the failure rate is high enough that
  * we should eliminate the guard. Return -1 if the guard looks no good;
diff --git a/src/or/circuitbuild.h b/src/or/circuitbuild.h
index a3091707e..ebcb22c45 100644
--- a/src/or/circuitbuild.h
+++ b/src/or/circuitbuild.h
@@ -57,16 +57,6 @@ const char *build_state_get_exit_nickname(cpath_build_state_t *state);
 
 const node_t *choose_good_entry_server(uint8_t purpose,
                                        cpath_build_state_t *state);
-double pathbias_get_extreme_rate(const or_options_t *options);
-double pathbias_get_extreme_use_rate(const or_options_t *options);
-int pathbias_get_dropguards(const or_options_t *options);
-void pathbias_count_timeout(origin_circuit_t *circ);
-int pathbias_check_close(origin_circuit_t *circ, int reason);
-int pathbias_check_probe_response(circuit_t *circ, const cell_t *cell);
-void pathbias_count_use_attempt(origin_circuit_t *circ);
-void pathbias_mark_use_success(origin_circuit_t *circ);
-void pathbias_mark_use_rollback(origin_circuit_t *circ);
-const char *pathbias_state_to_string(path_state_t state);
 
 #endif
 
diff --git a/src/or/include.am b/src/or/include.am
index 8922e0397..47bdd0990 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -34,6 +34,7 @@ LIBTOR_A_SOURCES = \
 	src/or/buffers.c				\
 	src/or/channel.c				\
 	src/or/channeltls.c				\
+	src/or/circpathbias.c				\
 	src/or/circuitbuild.c				\
 	src/or/circuitlist.c				\
 	src/or/circuitmux.c				\
@@ -134,6 +135,7 @@ ORHEADERS = \
 	src/or/buffers.h				\
 	src/or/channel.h				\
 	src/or/channeltls.h				\
+	src/or/circpathbias.h				\
 	src/or/circuitbuild.h				\
 	src/or/circuitlist.h				\
 	src/or/circuitmux.h				\