[tor/master] Implement most of the prop271 data structure backends.

16 Dec 2016

commit 7bf946965bad88116582dfd3d20e5837eeddd758
Author: Nick Mathewson <nickm@torproject.org>
Date:   Wed Nov 16 08:21:39 2016 -0500

    Implement most of the prop271 data structure backends.
    
    This code handles:
      * Maintaining the sampled set, the filtered set, and the
        usable_filtered set.
      * Maintaining the confirmed and primary guard lists.
      * Picking guards for circuits, and updating guard state when
        circuit state changes.
    
    Additionally, I've done code structure movement: even more constants
    and structures from entrynodes.c have become ENTRYNODES_PRIVATE
    fields of entrynodes.h.
    
    I've also included a bunch of documentation and a bunch of unit
    tests.  Coverage on the new code is pretty high.
    
    I've noted important things to resolve before this branch is done
    with the /XXXX.*prop271/ regex.
---
 src/or/entrynodes.c        | 1256 +++++++++++++++++++++++++++++++++++++++-----
 src/or/entrynodes.h        |  272 +++++++++-
 src/test/test_entrynodes.c | 1093 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 2488 insertions(+), 133 deletions(-)

diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c
index c6ed59d..958aba4 100644
--- a/src/or/entrynodes.c
+++ b/src/or/entrynodes.c
@@ -10,7 +10,113 @@
  *
  * Entry nodes can be guards (for general use) or bridges (for censorship
  * circumvention).
+ *
+ * XXXX prop271 This module is in flux, since I'm currently in the middle of
+ * implementation proposal 271.  The module documentation here will describe
+ * the new algorithm and data structures; the old ones should get removed as
+ * proposal 271 is completed.
+ *
+ * In general, we use entry guards to prevent traffic-sampling attacks:
+ * if we chose every circuit independently, an adversary controlling
+ * some fraction of paths on the network would observe a sample of every
+ * user's traffic. Using guards gives users a chance of not being
+ * profiled.
+ *
+ * The current entry guard selection code is designed to try to avoid
+ * _ever_ trying every guard on the network, to try to stick to guards
+ * that we've used before, to handle hostile/broken networks, and
+ * to behave sanely when the network goes up and down.
+ *
+ * Our algorithm works as follows: First, we maintain a SAMPLE of guards
+ * we've seen in the networkstatus consensus.  We maintain this sample
+ * over time, and store it persistently; it is chosen without reference
+ * to our configuration or firewall rules.  Guards remain in the sample
+ * as they enter and leave the consensus.  We expand this sample as
+ * needed, up to a maximum size.
+ *
+ * As a subset of the sample, we maintain a FILTERED SET of the guards
+ * that we would be willing to use if we could connect to them.  The
+ * filter removes all the guards that we're excluding because they're
+ * bridges (or not bridges), because we have restrictive firewall rules,
+ * because of ExcludeNodes, because we of path bias restrictions,
+ * because they're absent from the network at present, and so on.
+ *
+ * As a subset of the filtered set, we keep a REACHABLE FILTERED SET
+ * (also called a "usable filtered set") of those guards that we call
+ * "reachable" or "maybe reachable".  A guard is reachable if we've
+ * connected to it more recently than we've failed.  A guard is "maybe
+ * reachable" if we have never tried to connect to it, or if we
+ * failed to connect to it so long ago that we no longer think our
+ * failure means it's down.
+ *
+ * As a persistent ordered list whose elements are taken from the
+ * sampled set, we track a CONFIRMED GUARDS LIST.  A guard becomes
+ * confirmed when we successfully build a circuit through it, and decide
+ * to use that circuit.  We order the guards on this list by the order
+ * in which they became confirmed.
+ *
+ * And as a final group, we have an ordered list of PRIMARY GUARDS,
+ * whose elements are taken from the filtered set. We prefer
+ * confirmed guards to non-confirmed guards for this list, and place
+ * other restrictions on it.  The primary guards are the ones that we
+ * connect to "when nothing is wrong" -- circuits through them can be used
+ * immediately.
+ *
+ * To build circuits, we take a primary guard if possible -- or a
+ * reachable filtered confirmed guard if no primary guard is possible --
+ * or a random reachable filtered guard otherwise.  If the guard is
+ * primary, we can use the circuit immediately on success.  Otherwise,
+ * the guard is now "pending" -- we won't use its circuit unless all
+ * of the circuits we're trying to build through better guards have
+ * definitely failed.
+ *
+ * While we're building circuits, we track a little "guard state" for
+ * each circuit. We use this to keep track of whether the circuit is
+ * one that we can use as soon as its done, or whether it's one that
+ * we should keep around to see if we can do better.  In the latter case,
+ * a periodic call to entry_guards_upgrade_waiting_circuits() will
+ * eventually upgrade it.
  **/
+/* DOCDOC -- expand this.
+ *
+ * XXXX prop271 -- make sure we check all of these properties everywhere we
+ * should.
+ *
+ * Information invariants:
+ *
+ * [x] whenever a guard becomes unreachable, clear its usable_filtered flag.
+ *
+ * [x] Whenever a guard becomes reachable or maybe-reachable, if its filtered
+ * flag is set, set its usable_filtered flag.
+ *
+ * [ ] Whenever we get a new consensus, call update_from_consensus(). (LATER.)
+ *
+ * [ ] Whenever the configuration changes in a relevant way, update the
+ * filtered/usable flags. (LATER.)
+ *
+ * [x] Whenever we add a guard to the sample, make sure its filtered/usable
+ * flags are set as possible.
+ *
+ * [x] Whenever we remove a guard from the sample, remove it from the primary
+ * and confirmed lists.
+ *
+ * [ ] When we make a guard confirmed, update the primary list.
+ *
+ * [ ] When we make a guard filtered or unfiltered, update the primary list.
+ *
+ * [ ] When we are about to pick a guard, make sure that the primary list is
+ * full.
+ *
+ * [x] Before calling sample_reachable_filtered_entry_guards(), make sure
+ * that the filtered, primary, and confirmed flags are up-to-date.
+ *
+ * [x] Call entry_guard_consider_retry every time we are about to check
+ * is_usable_filtered or is_reachable, and every time we set
+ * is_filtered to 1.
+ *
+ * [x] Call entry_guards_changed_for_guard_selection() whenever we update
+ * a persistent field.
+ */
 
 #define ENTRYNODES_PRIVATE
 
@@ -38,39 +144,6 @@
 #include "transports.h"
 #include "statefile.h"
 
-/** All the context for guard selection on a particular client */
-
-struct guard_selection_s {
-  /**
-   * A value of 1 means that guard_selection_t structures have changed
-   * and those changes need to be flushed to disk.
-   *
-   * XXX we don't know how to flush multiple guard contexts to disk yet;
-   * fix that as soon as any way to change the default exists, or at least
-   * make sure this gets set on change.
-   */
-  int dirty;
-
-  /**
-   * A list of the sampled entry guards, as entry_guard_t structures.
-   * Not in any particular order. */
-  smartlist_t *sampled_entry_guards;
-
-  /**
-   * A list of our chosen entry guards, as entry_guard_t structures; this
-   * preserves the pre-Prop271 behavior.
-   */
-  smartlist_t *chosen_entry_guards;
-
-  /**
-   * When we try to choose an entry guard, should we parse and add
-   * config's EntryNodes first?  This was formerly a global.
-   */
-  int should_add_entry_nodes;
-
-  int filtered_up_to_date;
-};
-
 static smartlist_t *guard_contexts = NULL;
 static guard_selection_t *curr_guard_context = NULL;
 
@@ -79,54 +152,9 @@ static const node_t *choose_random_entry_impl(guard_selection_t *gs,
                                               int for_directory,
                                               dirinfo_type_t dirtype,
                                               int *n_options_out);
-static guard_selection_t * guard_selection_new(void);
-
-/**
- * @name Constants for old (pre-prop271) guard selection algorithm.
- */
-
-/**@{*/
-
-/* Default number of entry guards in the case where the NumEntryGuards
- * consensus parameter is not set */
-#define DEFAULT_N_GUARDS 1
-/* Minimum and maximum number of entry guards (in case the NumEntryGuards
- * consensus parameter is set). */
-#define MIN_N_GUARDS 1
-#define MAX_N_GUARDS 10
-/** Largest amount that we'll backdate chosen_on_date */
-#define CHOSEN_ON_DATE_SLOP (30*86400)
-/** How long (in seconds) do we allow an entry guard to be nonfunctional,
- * unlisted, excluded, or otherwise nonusable before we give up on it? */
-#define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
-/**}@*/
-
-/**
- * @name Networkstatus parameters for old (pre-prop271) guard selection
- */
-/**@}*/
-/** Choose how many entry guards or directory guards we'll use. If
- * <b>for_directory</b> is true, we return how many directory guards to
- * use; else we return how many entry guards to use. */
-STATIC int
-decide_num_guards(const or_options_t *options, int for_directory)
-{
-  if (for_directory) {
-    int answer;
-    if (options->NumDirectoryGuards != 0)
-      return options->NumDirectoryGuards;
-    answer = networkstatus_get_param(NULL, "NumDirectoryGuards", 0, 0, 10);
-    if (answer) /* non-zero means use the consensus value */
-      return answer;
-  }
-
-  if (options->NumEntryGuards)
-    return options->NumEntryGuards;
-
-  /* Use the value from the consensus, or 3 if no guidance. */
-  return networkstatus_get_param(NULL, "NumEntryGuards", DEFAULT_N_GUARDS,
-                                 MIN_N_GUARDS, MAX_N_GUARDS);
-}
+static void entry_guard_set_filtered_flags(const or_options_t *options,
+                                           guard_selection_t *gs,
+                                           entry_guard_t *guard);
 
 /** Return 0 if we should apply guardfraction information found in the
  *  consensus. A specific consensus can be specified with the
@@ -149,31 +177,10 @@ should_apply_guardfraction(const networkstatus_t *ns)
 
   return options->UseGuardFraction;
 }
-/**@}*/
-
-/**
- * @name Parameters for new (prop271) entry guard algorithm.
- */
-/* XXXX prop271 some of these should be networkstatus parameters */
-#define MIN_SAMPLE_THRESHOLD 15
-#define MAX_SAMPLE_THRESHOLD 50
-#define GUARD_LIFETIME_DAYS 120
-#define REMOVE_UNLISTED_GUARDS_AFTER_DAYS 20
-#define MIN_FILTERED_SAMPLE_SIZE 20
-#define N_PRIMARY_GUARDS 3
-#define PRIMARY_GUARDS_RETRY_SCHEDULE /* XXX prop271 */
-#define OTHER_GUARDS_RETRY_SCHEDULE /* XXX prop271 */
-#define INTERNET_LIKELY_DOWN_INTERVAL (10*60)
-#define NONPRIMARY_GUARD_CONNECT_TIMEOUT 15
-#define NONPRIMARY_GUARD_IDLE_TIMEOUT (10*60)
-#define MEANINGFUL_RESTRICTION_FRAC 0.2
-#define EXTREME_RESTRICTION_FRAC 0.01
-#define GUARD_CONFIRMED_MIN_LIFETIME_DAYS 60
-/**}@*/
 
-/** Allocate a new guard_selection_t */
+/** Allocate and return a new guard_selection_t */
 
-static guard_selection_t *
+STATIC guard_selection_t *
 guard_selection_new(void)
 {
   guard_selection_t *gs;
@@ -181,6 +188,8 @@ guard_selection_new(void)
   gs = tor_malloc_zero(sizeof(*gs));
   gs->chosen_entry_guards = smartlist_new();
   gs->sampled_entry_guards = smartlist_new();
+  gs->confirmed_entry_guards = smartlist_new();
+  gs->primary_entry_guards = smartlist_new();
 
   return gs;
 }
@@ -255,9 +264,11 @@ entry_guard_get_pathbias_state(entry_guard_t *guard)
 }
 
 /** Return an interval betweeen 'now' and 'max_backdate' seconds in the past,
- * chosen uniformly at random. */
-STATIC time_t
-randomize_time(time_t now, time_t max_backdate)
+ * chosen uniformly at random.  We use this before recording persistent
+ * dates, so that we aren't leaking exactly when we recorded it.
+ */
+MOCK_IMPL(STATIC time_t,
+randomize_time,(time_t now, time_t max_backdate))
 {
   tor_assert(max_backdate > 0);
 
@@ -272,25 +283,71 @@ randomize_time(time_t now, time_t max_backdate)
 }
 
 /**
- * DOCDOC
+ * Return true iff <b>node</b> has all the flags needed for us to consider it
+ * a possible guard when sampling guards.
+ */
+static int
+node_is_possible_guard(guard_selection_t *gs, const node_t *node)
+{
+  /* The "GUARDS" set is all nodes in the nodelist for which this predicate
+   * holds. */
+
+  /* XXXX -- prop271 spec deviation. We require node_is_dir() here. */
+  (void)gs;
+  tor_assert(node);
+  return (node->is_possible_guard &&
+          node->is_stable &&
+          node->is_fast &&
+          node->is_valid &&
+          node_is_dir(node));
+}
+
+/**
+ * Return the sampled guard with the RSA identity digest <b>rsa_id</b>, or
+ * NULL if we don't have one. */
+STATIC entry_guard_t *
+get_sampled_guard_with_id(guard_selection_t *gs,
+                          const uint8_t *rsa_id)
+{
+  tor_assert(gs);
+  tor_assert(rsa_id);
+  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
+    if (tor_memeq(guard->identity, rsa_id, DIGEST_LEN))
+      return guard;
+  } SMARTLIST_FOREACH_END(guard);
+  return NULL;
+}
+
+/**
+ * Return true iff we have a sampled guard with the RSA identity digest
+ * <b>rsa_id</b>. */
+static inline int
+have_sampled_guard_with_id(guard_selection_t *gs, const uint8_t *rsa_id)
+{
+  return get_sampled_guard_with_id(gs, rsa_id) != NULL;
+}
+
+/**
+ * Allocate a new entry_guard_t object for <b>node</b>, add it to the
+ * sampled entry guards in <b>gs</b>, and return it. <b>node</b> must
+ * not currently be a sampled guard in <b>gs</b>.
  */
-ATTR_UNUSED STATIC void
+STATIC entry_guard_t *
 entry_guard_add_to_sample(guard_selection_t *gs,
-                          node_t *node)
+                          const node_t *node)
 {
   const int GUARD_LIFETIME = GUARD_LIFETIME_DAYS * 86400;
   tor_assert(gs);
   tor_assert(node);
 
+  log_info(LD_GUARD, "Adding %s as to the entry guard sample set.",
+           node_describe(node));
+
   // XXXX prop271 take ed25519 identity here too.
 
   /* make sure that the guard is not already sampled. */
-   SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards,
-                           entry_guard_t *, sampled) {
-    if (BUG(tor_memeq(node->identity, sampled->identity, DIGEST_LEN))) {
-      return;
-    }
-  } SMARTLIST_FOREACH_END(sampled);
+  if (BUG(have_sampled_guard_with_id(gs, (uint8_t*)node->identity)))
+    return NULL; // LCOV_EXCL_LINE
 
   entry_guard_t *guard = tor_malloc_zero(sizeof(entry_guard_t));
 
@@ -300,22 +357,902 @@ entry_guard_add_to_sample(guard_selection_t *gs,
   guard->sampled_on_date = randomize_time(approx_time(), GUARD_LIFETIME/10);
   tor_free(guard->sampled_by_version);
   guard->sampled_by_version = tor_strdup(VERSION);
+  guard->currently_listed = 1;
   guard->confirmed_idx = -1;
 
   /* non-persistent fields */
   guard->is_reachable = GUARD_REACHABLE_MAYBE;
 
   smartlist_add(gs->sampled_entry_guards, guard);
-  gs->filtered_up_to_date = 0;
+  entry_guard_set_filtered_flags(get_options(), gs, guard);
+  entry_guards_changed_for_guard_selection(gs);
+  return guard;
+}
+
+/**
+ * Return the number of sampled guards in <b>gs</b> that are "filtered"
+ * (that is, we're willing to connect to them) and that are "usable"
+ * (that is, either "reachable" or "maybe reachable"). */
+STATIC int
+num_reachable_filtered_guards(guard_selection_t *gs)
+{
+  int n_reachable_filtered_guards = 0;
+  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
+    entry_guard_consider_retry(guard);
+    if (guard->is_usable_filtered_guard)
+      ++n_reachable_filtered_guards;
+  } SMARTLIST_FOREACH_END(guard);
+  return n_reachable_filtered_guards;
+}
+
+/**
+ * Add new guards to the sampled guards in <b>gs</b> until there are
+ * enough usable filtered guards, but never grow the sample beyond its
+ * maximum size.  Return the last guard added, or NULL if none were
+ * added.
+ */
+STATIC entry_guard_t *
+entry_guards_expand_sample(guard_selection_t *gs)
+{
+  tor_assert(gs);
+  int n_sampled = smartlist_len(gs->sampled_entry_guards);
+  entry_guard_t *added_guard = NULL;
+
+  smartlist_t *nodes = nodelist_get_list();
+  /* Construct eligible_guards as GUARDS - SAMPLED_GUARDS */
+  smartlist_t *eligible_guards = smartlist_new();
+  int n_guards = 0; // total size of "GUARDS"
+  int n_usable_filtered_guards = num_reachable_filtered_guards(gs);
+  {
+    /* Build a bloom filter of our current guards: let's keep this O(N). */
+    digestset_t *sampled_guard_ids = digestset_new(n_sampled);
+    SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, const entry_guard_t *,
+                            guard) {
+      digestset_add(sampled_guard_ids, guard->identity);
+    } SMARTLIST_FOREACH_END(guard);
+
+    SMARTLIST_FOREACH_BEGIN(nodes, node_t *, node) {
+      if (! node_is_possible_guard(gs, node))
+        continue;
+      ++n_guards;
+      if (digestset_contains(sampled_guard_ids, node->identity))
+        continue;
+      smartlist_add(eligible_guards, node);
+    } SMARTLIST_FOREACH_END(node);
+
+    /* Now we can free that bloom filter. */
+    digestset_free(sampled_guard_ids);
+  }
+
+  /* Is there at least one guard we haven't sampled? */
+  if (! smartlist_len(eligible_guards))
+    goto done;
+
+  const int max_sample = (int)(n_guards * MAX_SAMPLE_THRESHOLD);
+  const int min_filtered_sample = MIN_FILTERED_SAMPLE_SIZE;
+
+  log_info(LD_GUARD, "Expanding the sample guard set. We have %d guards "
+           "in the sample, and %d eligible guards to extend it with.",
+           n_sampled, smartlist_len(eligible_guards));
+
+  while (n_usable_filtered_guards < min_filtered_sample) {
+    /* Has our sample grown too large to expand? */
+    if (n_sampled >= max_sample) {
+      log_info(LD_GUARD, "Not expanding the guard sample any further; "
+               "just hit the maximum sample threshold of %d",
+               max_sample);
+      goto done;
+    }
+
+    /* Did we run out of guards? */
+    if (smartlist_len(eligible_guards) == 0) {
+      /* LCOV_EXCL_START
+         As long as MAX_SAMPLE_THRESHOLD makes can't be adjusted to
+         allow all guards to be sampled, this can't be reached.
+       */
+      log_info(LD_GUARD, "Not expanding the guard sample any further; "
+               "just ran out of eligible guards");
+      goto done;
+      /* LCOV_EXCL_STOP */
+    }
+
+    /* Otherwise we can add at least one new guard. */
+    const node_t *node =
+      node_sl_choose_by_bandwidth(eligible_guards, WEIGHT_FOR_GUARD);
+    if (BUG(! node))
+      goto done; // LCOV_EXCL_LINE -- should be impossible.
+
+    added_guard = entry_guard_add_to_sample(gs, node);
+    if (!added_guard)
+      goto done; // LCOV_EXCL_LINE -- only fails on BUG.
+
+    ++n_sampled;
+
+    if (added_guard->is_usable_filtered_guard)
+      ++n_usable_filtered_guards;
+
+    smartlist_remove(eligible_guards, node);
+  }
+
+ done:
+  smartlist_free(eligible_guards);
+  return added_guard;
+}
+
+/**
+ * Helper: <b>guard</b> has just been removed from the sampled guards:
+ * also remove it from primary and confirmed. */
+static void
+remove_guard_from_confirmed_and_primary_lists(guard_selection_t *gs,
+                                              entry_guard_t *guard)
+{
+  if (guard->is_primary) {
+    guard->is_primary = 0;
+    smartlist_remove_keeporder(gs->primary_entry_guards, guard);
+  } else {
+    if (BUG(smartlist_contains(gs->primary_entry_guards, guard))) {
+      smartlist_remove_keeporder(gs->primary_entry_guards, guard);
+    }
+  }
+
+  if (guard->confirmed_idx >= 0) {
+    entry_guard_t *found_guard = NULL;
+    if (guard->confirmed_idx < smartlist_len(gs->confirmed_entry_guards))
+      found_guard = smartlist_get(gs->confirmed_entry_guards,
+                                  guard->confirmed_idx);
+    if (BUG(guard != found_guard)) {
+      smartlist_remove_keeporder(gs->confirmed_entry_guards, guard);
+    } else {
+      smartlist_del_keeporder(gs->confirmed_entry_guards,
+                              guard->confirmed_idx);
+    }
+    guard->confirmed_idx = -1;
+    guard->confirmed_on_date = 0;
+  } else {
+    if (BUG(smartlist_contains(gs->confirmed_entry_guards, guard))) {
+      smartlist_remove_keeporder(gs->confirmed_entry_guards, guard);
+    }
+  }
+}
+
+/**
+ * Update the status of all sampled guards based on the arrival of a
+ * new consensus networkstatus document.  This will include marking
+ * some guards as listed or unlisted, and removing expired guards. */
+STATIC void
+sampled_guards_update_from_consensus(guard_selection_t *gs)
+{
+  tor_assert(gs);
+  const int REMOVE_UNLISTED_GUARDS_AFTER =
+    (REMOVE_UNLISTED_GUARDS_AFTER_DAYS * 86400);
+  const int unlisted_since_slop = REMOVE_UNLISTED_GUARDS_AFTER / 5;
+
+  // It's important to use only a live consensus here; we don't want to
+  // make changes based on anything expired or old.
+  networkstatus_t *ns = networkstatus_get_live_consensus(approx_time());
+
+  log_info(LD_GUARD, "Updating sampled guard status based on received "
+           "consensus.");
+
+  if (! ns || ns->valid_until < approx_time()) {
+    log_info(LD_GUARD, "Hey, that consensus isn't still valid. Ignoring.");
+    return;
+  }
+
+  int n_changes = 0;
+
+  /* First: Update listed/unlisted. */
+  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
+    /* XXXX prop271 handle bridges right?  */
+    /* XXXX prop271 check ed ID too */
+    const node_t *node = node_get_by_id(guard->identity);
+
+    const unsigned is_listed = node && node_is_possible_guard(gs, node);
+
+    if (is_listed && ! guard->currently_listed) {
+      ++n_changes;
+      guard->currently_listed = 1;
+      guard->unlisted_since_date = 0;
+      log_info(LD_GUARD, "Sampled guard %s is now listed again.",
+               entry_guard_describe(guard));
+    } else if (!is_listed && guard->currently_listed) {
+      ++n_changes;
+      guard->currently_listed = 0;
+      guard->unlisted_since_date = randomize_time(approx_time(),
+                                                  unlisted_since_slop);
+      log_info(LD_GUARD, "Sampled guard %s is now unlisted.",
+               entry_guard_describe(guard));
+    } else if (is_listed && guard->currently_listed) {
+      log_debug(LD_GUARD, "Sampled guard %s is still listed.",
+               entry_guard_describe(guard));
+    } else {
+      tor_assert(! is_listed && ! guard->currently_listed);
+      log_debug(LD_GUARD, "Sampled guard %s is still unlisted.",
+                entry_guard_describe(guard));
+    }
+
+    /* Clean up unlisted_since_date, just in case. */
+    if (guard->currently_listed && guard->unlisted_since_date) {
+      ++n_changes;
+      guard->unlisted_since_date = 0;
+      log_warn(LD_BUG, "Sampled guard %s was listed, but with "
+               "unlisted_since_date set. Fixing.",
+               entry_guard_describe(guard));
+    } else if (!guard->currently_listed && ! guard->unlisted_since_date) {
+      ++n_changes;
+      guard->unlisted_since_date = randomize_time(approx_time(),
+                                                  unlisted_since_slop);
+      log_warn(LD_BUG, "Sampled guard %s was unlisted, but with "
+               "unlisted_since_date unset. Fixing.",
+               entry_guard_describe(guard));
+    }
+  } SMARTLIST_FOREACH_END(guard);
+
+  const time_t remove_if_unlisted_since =
+    approx_time() - REMOVE_UNLISTED_GUARDS_AFTER;
+  const time_t maybe_remove_if_sampled_before =
+    approx_time() - (GUARD_LIFETIME_DAYS * 86400);
+  const time_t remove_if_confirmed_before =
+    approx_time() - (GUARD_CONFIRMED_MIN_LIFETIME_DAYS * 86400);
+
+  /* Then: remove the ones that have been junk for too long */
+  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
+    /* XXXX prop271 handle bridges right?  */
+
+    int remove = 0;
+
+    if (guard->currently_listed == 0 &&
+        guard->unlisted_since_date < remove_if_unlisted_since) {
+      /*
+        "We have a live consensus, and {IS_LISTED} is false, and
+         {FIRST_UNLISTED_AT} is over {REMOVE_UNLISTED_GUARDS_AFTER}
+         days in the past."
+      */
+      log_info(LD_GUARD, "Removing sampled guard %s: it has been unlisted "
+               "for over %d days", entry_guard_describe(guard),
+               REMOVE_UNLISTED_GUARDS_AFTER_DAYS);
+      remove = 1;
+    } else if (guard->sampled_on_date < maybe_remove_if_sampled_before) {
+      /* We have a live consensus, and {ADDED_ON_DATE} is over
+        {GUARD_LIFETIME} ago, *and* {CONFIRMED_ON_DATE} is either
+        "never", or over {GUARD_CONFIRMED_MIN_LIFETIME} ago.
+      */
+      if (guard->confirmed_on_date == 0) {
+        remove = 1;
+        log_info(LD_GUARD, "Removing sampled guard %s: it was sampled "
+                 "over %d days ago, but never confirmed.",
+                 entry_guard_describe(guard),
+                 GUARD_LIFETIME_DAYS);
+      } else if (guard->confirmed_on_date < remove_if_confirmed_before) {
+        remove = 1;
+        log_info(LD_GUARD, "Removing sampled guard %s: it was sampled "
+                 "over %d days ago, and confirmed over %d days ago.",
+                 entry_guard_describe(guard),
+                 GUARD_LIFETIME_DAYS, GUARD_CONFIRMED_MIN_LIFETIME_DAYS);
+      }
+    }
+
+    if (remove) {
+      ++n_changes;
+      SMARTLIST_DEL_CURRENT(gs->sampled_entry_guards, guard);
+      remove_guard_from_confirmed_and_primary_lists(gs, guard);
+      entry_guard_free(guard);
+    }
+  } SMARTLIST_FOREACH_END(guard);
+
+  if (n_changes) {
+    /* Regnerate other things. XXXXXX prop271 */
+    // XXXX prop271 rebuild confirmed list.
+    entry_guards_update_filtered_sets(gs);
+    entry_guards_changed_for_guard_selection(gs);
+  }
+}
+
+/**
+ * Return true iff <b>node</b> is a Tor relay that we are configured to
+ * be able to connect to. */
+static int
+node_passes_guard_filter(const or_options_t *options, guard_selection_t *gs,
+                         const node_t *node)
+{
+  (void)gs;
+  if (routerset_contains_node(options->ExcludeNodes, node))
+    return 0;
+
+  /* XXXX -- prop271 spec deviation -- add entrynodes to spec. */
+  if (options->EntryNodes &&
+      !options->UseBridges &&
+      !routerset_contains_node(options->EntryNodes, node))
+    return 0;
+
+  if (!fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION, 0))
+    return 0;
+
+  if (bool_neq(options->UseBridges, node_is_a_configured_bridge(node)))
+    return 0;
+
+  return 1;
+}
+
+/**
+ * Return true iff <b>guard</b> is a Tor relay that we are configured to
+ * be able to connect to, and we haven't disabled it for omission from
+ * the consensus or path bias issues. */
+static int
+entry_guard_passes_filter(const or_options_t *options, guard_selection_t *gs,
+                          entry_guard_t *guard)
+{
+  if (guard->currently_listed == 0)
+    return 0;
+  if (guard->pb.path_bias_disabled)
+    return 0;
+
+  const node_t *node = node_get_by_id(guard->identity);
+  if (BUG(node == NULL)) {
+    // should be impossible, since currently_listed was true.
+    return 0;
+  }
+
+  return node_passes_guard_filter(options, gs, node);
+}
+
+/**
+ * Update the <b>is_filtered_guard</b> and <b>is_usable_filtered_guard</b>
+ * flags on <b>guard</b>. */
+void
+entry_guard_set_filtered_flags(const or_options_t *options,
+                               guard_selection_t *gs,
+                               entry_guard_t *guard)
+{
+  guard->is_filtered_guard = 0;
+  guard->is_usable_filtered_guard = 0;
+
+  if (entry_guard_passes_filter(options, gs, guard)) {
+    guard->is_filtered_guard = 1;
+
+    if (guard->is_reachable != GUARD_REACHABLE_NO)
+      guard->is_usable_filtered_guard = 1;
+
+    entry_guard_consider_retry(guard);
+  }
+  log_debug(LD_GUARD, "Updated sampled guard %s: filtered=%d; "
+            "reachable_filtered=%d.", entry_guard_describe(guard),
+            guard->is_filtered_guard, guard->is_usable_filtered_guard);
+}
+
+/**
+ * Update the <b>is_filtered_guard</b> and <b>is_usable_filtered_guard</b>
+ * flag on every guard in <b>gs</b>. */
+STATIC void
+entry_guards_update_filtered_sets(guard_selection_t *gs)
+{
+  const or_options_t *options = get_options();
+
+  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
+    entry_guard_set_filtered_flags(options, gs, guard);
+  } SMARTLIST_FOREACH_END(guard);
+}
+
+/**
+ * Return a random guard from the reachable filtered sample guards
+ * in <b>gs</b>, subject to the exclusion rules listed in <b>flags</b>.
+ * Return NULL if no such guard can be found.
+ *
+ * Make sure that the sample is big enough, and that all the filter flags
+ * are set correctly, before calling this function.
+ **/
+STATIC entry_guard_t *
+sample_reachable_filtered_entry_guards(guard_selection_t *gs,
+                                       unsigned flags)
+{
+  tor_assert(gs);
+  entry_guard_t *result = NULL;
+  const unsigned exclude_confirmed = flags & SAMPLE_EXCLUDE_CONFIRMED;
+  const unsigned exclude_primary = flags & SAMPLE_EXCLUDE_PRIMARY;
+  const unsigned exclude_pending = flags & SAMPLE_EXCLUDE_PENDING;
+
+  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
+    entry_guard_consider_retry(guard);
+  } SMARTLIST_FOREACH_END(guard);
+
+  const int n_reachable_filtered = num_reachable_filtered_guards(gs);
+
+  log_info(LD_GUARD, "Trying to sample a reachable guard: We know of %d "
+           "in the USABLE_FILTERED set.", n_reachable_filtered);
+
+  if (n_reachable_filtered < MIN_FILTERED_SAMPLE_SIZE) {
+    log_info(LD_GUARD, "  (That isn't enough. Trying to expand the sample.)");
+    entry_guards_expand_sample(gs);
+  }
+
+  /* Build the set of reachable filtered guards. */
+  smartlist_t *reachable_filtered_sample = smartlist_new();
+  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
+    entry_guard_consider_retry(guard);// redundant, but cheap.
+    if (! guard->is_usable_filtered_guard)
+      continue;
+    if (exclude_confirmed && guard->confirmed_idx >= 0)
+      continue;
+    if (exclude_primary && guard->is_primary)
+      continue;
+    if (exclude_pending && guard->is_pending)
+      continue;
+    smartlist_add(reachable_filtered_sample, guard);
+  } SMARTLIST_FOREACH_END(guard);
+
+  log_info(LD_GUARD, "  (After filters [%x], we have %d guards to consider.)",
+           flags, smartlist_len(reachable_filtered_sample));
+
+  if (smartlist_len(reachable_filtered_sample)) {
+    result = smartlist_choose(reachable_filtered_sample);
+    log_info(LD_GUARD, "  (Selected %s.)",
+             result ? entry_guard_describe(result) : "<null>");
+  }
+  smartlist_free(reachable_filtered_sample);
+
+  return result;
+}
+
+/**
+ * Helper: compare two entry_guard_t by their confirmed_idx values.
+ * Used to sort the confirmed list.
+ */
+static int
+compare_guards_by_confirmed_idx(const void **a_, const void **b_)
+{
+  const entry_guard_t *a = *a_, *b = *b_;
+  if (a->confirmed_idx < b->confirmed_idx)
+    return -1;
+  else if (a->confirmed_idx > b->confirmed_idx)
+    return 1;
+  else
+    return 0;
+}
+
+/**
+ * Find the confirmed guards from among the sampled guards in <b>gs</b>,
+ * and put them in confirmed_entry_guards in the correct
+ * order. Recalculate their indices.
+ */
+STATIC void
+entry_guards_update_confirmed(guard_selection_t *gs)
+{
+  smartlist_clear(gs->confirmed_entry_guards);
+  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
+    if (guard->confirmed_idx >= 0)
+      smartlist_add(gs->confirmed_entry_guards, guard);
+  } SMARTLIST_FOREACH_END(guard);
+
+  smartlist_sort(gs->confirmed_entry_guards, compare_guards_by_confirmed_idx);
+
+  int any_changed = 0;
+  SMARTLIST_FOREACH_BEGIN(gs->confirmed_entry_guards, entry_guard_t *, guard) {
+    if (guard->confirmed_idx != guard_sl_idx) {
+      any_changed = 1;
+      guard->confirmed_idx = guard_sl_idx;
+    }
+  } SMARTLIST_FOREACH_END(guard);
+
+  gs->next_confirmed_idx = smartlist_len(gs->confirmed_entry_guards);
+
+  if (any_changed) {
+    entry_guards_changed_for_guard_selection(gs);
+  }
+}
+
+/**
+ * Mark <b>guard</b> as a confirmed guard -- that is, one that we have
+ * connected to, and intend to use again.
+ */
+STATIC void
+make_guard_confirmed(guard_selection_t *gs, entry_guard_t *guard)
+{
+  if (BUG(guard->confirmed_on_date && guard->confirmed_idx >= 0))
+    return;
+
+  if (BUG(smartlist_contains(gs->confirmed_entry_guards, guard)))
+    return;
+
+  const int GUARD_LIFETIME = GUARD_LIFETIME_DAYS * 86400;
+  guard->confirmed_on_date = randomize_time(approx_time(), GUARD_LIFETIME/10);
+
+  log_info(LD_GUARD, "Marking %s as a confirmed guard (index %d)",
+           entry_guard_describe(guard),
+           gs->next_confirmed_idx);
+
+  guard->confirmed_idx = gs->next_confirmed_idx++;
+  smartlist_add(gs->confirmed_entry_guards, guard);
 
   entry_guards_changed_for_guard_selection(gs);
 }
 
 /**
+ * Recalculate the list of primary guards (the ones we'd prefer to use) from
+ * the filtered sample and the confirmed list.
+ *
+ * XXXXX prop271 are calling this enough ???
+ */
+STATIC void
+entry_guards_update_primary(guard_selection_t *gs)
+{
+  tor_assert(gs);
+
+  smartlist_t *new_primary_guards = smartlist_new();
+  smartlist_t *old_primary_guards = smartlist_new();
+  smartlist_add_all(old_primary_guards, gs->primary_entry_guards);
+
+  /* First, can we fill it up with confirmed guards? */
+  SMARTLIST_FOREACH_BEGIN(gs->confirmed_entry_guards, entry_guard_t *, guard) {
+    if (smartlist_len(new_primary_guards) >= N_PRIMARY_GUARDS)
+      break;
+    if (! guard->is_filtered_guard)
+      continue;
+    guard->is_primary = 1;
+    smartlist_add(new_primary_guards, guard);
+  } SMARTLIST_FOREACH_END(guard);
+
+  /* Can we keep any older primary guards? First remove all the ones
+   * that we already kept. */
+  SMARTLIST_FOREACH_BEGIN(old_primary_guards, entry_guard_t *, guard) {
+    if (smartlist_contains(new_primary_guards, guard)) {
+      SMARTLIST_DEL_CURRENT_KEEPORDER(old_primary_guards, guard);
+    }
+  } SMARTLIST_FOREACH_END(guard);
+
+  /* Now add any that are still good. */
+  SMARTLIST_FOREACH_BEGIN(old_primary_guards, entry_guard_t *, guard) {
+    if (smartlist_len(new_primary_guards) >= N_PRIMARY_GUARDS)
+      break;
+    if (! guard->is_filtered_guard)
+      continue;
+    guard->is_primary = 1;
+    smartlist_add(new_primary_guards, guard);
+    SMARTLIST_DEL_CURRENT_KEEPORDER(old_primary_guards, guard);
+  } SMARTLIST_FOREACH_END(guard);
+
+  /* Mark the remaining previous primary guards as non-primary */
+  SMARTLIST_FOREACH_BEGIN(old_primary_guards, entry_guard_t *, guard) {
+    guard->is_primary = 0;
+  } SMARTLIST_FOREACH_END(guard);
+
+  /* Finally, fill out the list with sampled guards. */
+  while (smartlist_len(new_primary_guards) < N_PRIMARY_GUARDS) {
+    entry_guard_t *guard = sample_reachable_filtered_entry_guards(gs,
+                                            SAMPLE_EXCLUDE_CONFIRMED|
+                                            SAMPLE_EXCLUDE_PRIMARY);
+    if (!guard)
+      break;
+    guard->is_primary = 1;
+    smartlist_add(new_primary_guards, guard);
+  }
+
+#if 1
+  /* Debugging. */
+  SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, guard, {
+    tor_assert_nonfatal(
+                   bool_eq(guard->is_primary,
+                           smartlist_contains(new_primary_guards, guard)));
+  });
+#endif
+
+  int any_change = 0;
+  if (smartlist_len(gs->primary_entry_guards) !=
+      smartlist_len(new_primary_guards)) {
+    any_change = 1;
+  } else {
+    SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, g) {
+      if (g != smartlist_get(new_primary_guards, g_sl_idx)) {
+        any_change = 1;
+      }
+    } SMARTLIST_FOREACH_END(g);
+  }
+
+  if (any_change) {
+    log_info(LD_GUARD, "Primary entry guards have changed. "
+             "New primary guard list is: ");
+    int n = smartlist_len(new_primary_guards);
+    SMARTLIST_FOREACH_BEGIN(new_primary_guards, entry_guard_t *, g) {
+      log_info(LD_GUARD, "  %d/%d: %s%s%s",
+               g_sl_idx+1, n, entry_guard_describe(g),
+               g->confirmed_idx >= 0 ? " (confirmed)" : "",
+               g->is_filtered_guard ? "" : " (excluded by filter)");
+    } SMARTLIST_FOREACH_END(g);
+  }
+
+  smartlist_free(old_primary_guards);
+  smartlist_free(gs->primary_entry_guards);
+  gs->primary_entry_guards = new_primary_guards;
+}
+
+/**
+ * Return the number of seconds after the last attempt at which we should
+ * retry a guard that has been failing since <b>failing_since</b>.
+ */
+static unsigned
+get_retry_schedule(time_t failing_since, time_t now,
+                   int is_primary)
+{
+  const unsigned SIX_HOURS = 6 * 3600;
+  const unsigned FOUR_DAYS = 4 * 86400;
+  const unsigned SEVEN_DAYS = 7 * 86400;
+
+  time_t tdiff;
+  if (now > failing_since) {
+    tdiff = now - failing_since;
+  } else {
+    tdiff = 0;
+  }
+
+  const struct {
+    time_t maximum; int primary_delay; int nonprimary_delay;
+  } delays[] = {
+    { SIX_HOURS,    30*60,  1*60*60 },
+    { FOUR_DAYS,  2*60*60,  4*60*60 },
+    { SEVEN_DAYS, 4*60*60, 18*60*60 },
+    { TIME_MAX,   9*60*60, 36*60*60 }
+  };
+
+  unsigned i;
+  for (i = 0; i < ARRAY_LENGTH(delays); ++i) {
+    if (tdiff <= delays[i].maximum) {
+      return is_primary ? delays[i].primary_delay : delays[i].nonprimary_delay;
+    }
+  }
+  /* LCOV_EXCL_START -- can't reach, since delays ends with TIME_MAX. */
+  tor_assert_nonfatal_unreached();
+  return 36*60*60;
+  /* LCOV_EXCL_STOP */
+}
+
+/**
+ * If <b>guard</b> is unreachable, consider whether enough time has passed
+ * to consider it maybe-reachable again.
+ */
+STATIC void
+entry_guard_consider_retry(entry_guard_t *guard)
+{
+  if (guard->is_reachable != GUARD_REACHABLE_NO)
+    return; /* No retry needed. */
+
+  const time_t now = approx_time();
+  const unsigned delay =
+    get_retry_schedule(guard->failing_since, now, guard->is_primary);
+  const time_t last_attempt = guard->last_tried_to_connect;
+
+  if (BUG(last_attempt == 0) ||
+      now >= last_attempt + delay) {
+    /* We should mark this retriable. */
+    char tbuf[ISO_TIME_LEN+1];
+    format_local_iso_time(tbuf, last_attempt);
+    log_info(LD_GUARD, "Marked %s%sguard %s for possible retry, since we "
+             "haven't tried to use it since %s.",
+             guard->is_primary?"primary ":"",
+             guard->confirmed_idx>=0?"confirmed ":"",
+             entry_guard_describe(guard),
+             tbuf);
+
+    guard->is_reachable = GUARD_REACHABLE_MAYBE;
+    if (guard->is_filtered_guard)
+      guard->is_usable_filtered_guard = 1;
+  }
+}
+
+/**
+ * Get a guard for use with a circuit.  Prefer to pick a running primary
+ * guard; then a non-pending running filtered confirmed guard; then a
+ * non-pending runnable filtered guard.  Update the
+ * <b>last_tried_to_connect</b> time and the <b>is_pending</b> fields of the
+ * guard as appropriate.  Set <b>state_out</b> to the new guard-state
+ * of the circuit.
+ */
+STATIC entry_guard_t *
+select_entry_guard_for_circuit(guard_selection_t *gs, unsigned *state_out)
+{
+  tor_assert(gs);
+  tor_assert(state_out);
+
+  /* "If any entry in PRIMARY_GUARDS has {is_reachable} status of
+      <maybe> or <yes>, return the first such guard." */
+  SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) {
+    entry_guard_consider_retry(guard);
+    if (guard->is_reachable != GUARD_REACHABLE_NO) {
+      *state_out = GUARD_CIRC_STATE_USABLE_ON_COMPLETION;
+      guard->last_tried_to_connect = approx_time();
+      log_info(LD_GUARD, "Selected primary guard %s for circuit.",
+               entry_guard_describe(guard));
+      return guard;
+    }
+  } SMARTLIST_FOREACH_END(guard);
+
+  /* "Otherwise, if the ordered intersection of {CONFIRMED_GUARDS}
+      and {USABLE_FILTERED_GUARDS} is nonempty, return the first
+      entry in that intersection that has {is_pending} set to
+      false." */
+  SMARTLIST_FOREACH_BEGIN(gs->confirmed_entry_guards, entry_guard_t *, guard) {
+    if (guard->is_primary)
+      continue; /* we already considered this one. */
+    entry_guard_consider_retry(guard);
+    if (guard->is_usable_filtered_guard && ! guard->is_pending) {
+      guard->is_pending = 1;
+      guard->last_tried_to_connect = approx_time();
+      *state_out = GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD;
+      log_info(LD_GUARD, "No primary guards available. Selected confirmed "
+               "guard %s for circuit. Will try other guards before using "
+               "this circuit.",
+               entry_guard_describe(guard));
+      return guard;
+    }
+  } SMARTLIST_FOREACH_END(guard);
+
+  /* "Otherwise, if there is no such entry, select a member at
+      random from {USABLE_FILTERED_GUARDS}." */
+  {
+    entry_guard_t *guard;
+    guard = sample_reachable_filtered_entry_guards(gs,
+                                                   SAMPLE_EXCLUDE_CONFIRMED |
+                                                   SAMPLE_EXCLUDE_PRIMARY |
+                                                   SAMPLE_EXCLUDE_PENDING);
+    if (guard == NULL) {
+      log_info(LD_GUARD, "Absolutely no sampled guards were available.");
+      return NULL;
+    }
+    guard->is_pending = 1;
+    guard->last_tried_to_connect = approx_time();
+    *state_out = GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD;
+    log_info(LD_GUARD, "No primary or confirmed guards available. Selected "
+             "random guard %s for circuit. Will try other guards before "
+             "using this circuit.",
+             entry_guard_describe(guard));
+    return guard;
+  }
+}
+
+/**
+ * Note that we failed to connect to or build circuits through <b>guard</b>.
+ * Use with a guard returned by select_entry_guards_for_circuit().
+ */
+STATIC void
+entry_guards_note_guard_failure(guard_selection_t *gs,
+                                entry_guard_t *guard)
+{
+  tor_assert(gs);
+
+  guard->is_reachable = GUARD_REACHABLE_NO;
+  guard->is_usable_filtered_guard = 0;
+
+  guard->is_pending = 0;
+  if (guard->failing_since == 0)
+    guard->failing_since = approx_time();
+
+  log_info(LD_GUARD, "Recorded failure for %s%sguard %s",
+           guard->is_primary?"primary ":"",
+           guard->confirmed_idx>=0?"confirmed ":"",
+           entry_guard_describe(guard));
+}
+
+/**
+ * Called when the network comes up after having seemed to be down for
+ * a while: Mark the primary guards as maybe-reachable so that we'll
+ * try them again.
+ */
+STATIC void
+mark_primary_guards_maybe_reachable(guard_selection_t *gs)
+{
+  SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) {
+    if (guard->is_reachable != GUARD_REACHABLE_NO)
+      continue;
+
+    /* Note that we do not clear failing_since: this guard is now only
+     * _maybe-reachable_. */
+    guard->is_reachable = GUARD_REACHABLE_MAYBE;
+    if (guard->is_filtered_guard)
+      guard->is_usable_filtered_guard = 1;
+
+  } SMARTLIST_FOREACH_END(guard);
+}
+
+/**
+ * Note that we successfully connected to, and built a circuit through
+ * <b>guard</b>. Given the old guard-state of the circuit in <b>old_state</b>,
+ * return the new guard-state of the circuit.
+ *
+ * Be aware: the circuit is only usable when its guard-state becomes
+ * GUARD_CIRC_STATE_COMPLETE.
+ **/
+STATIC unsigned
+entry_guards_note_guard_success(guard_selection_t *gs,
+                                entry_guard_t *guard,
+                                unsigned old_state)
+{
+  tor_assert(gs);
+
+  /* Save this, since we're about to overwrite it. */
+  const time_t last_time_on_internet = gs->last_time_on_internet;
+  gs->last_time_on_internet = approx_time();
+
+  guard->is_reachable = GUARD_REACHABLE_YES;
+  guard->failing_since = 0;
+  guard->is_pending = 0;
+  if (guard->is_filtered_guard)
+    guard->is_usable_filtered_guard = 1;
+
+  if (guard->confirmed_idx < 0) {
+    // XXXX prop271 XXXX update primary guards, since we confirmed something?
+    make_guard_confirmed(gs, guard);
+  }
+
+  unsigned new_state;
+  if (old_state == GUARD_CIRC_STATE_USABLE_ON_COMPLETION) {
+    new_state = GUARD_CIRC_STATE_COMPLETE;
+  } else {
+    tor_assert_nonfatal(
+               old_state == GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD);
+    new_state = GUARD_CIRC_STATE_WAITING_FOR_BETTER_GUARD;
+
+    if (last_time_on_internet + INTERNET_LIKELY_DOWN_INTERVAL
+        < approx_time()) {
+      mark_primary_guards_maybe_reachable(gs);
+    } else {
+      // update_waiting_circuits(gs); // XXXX prop271 write this function.
+    }
+  }
+
+  // XXXX prop271 XXXX update primary guards, since we confirmed something?
+  // XXXX prop261 XXXX if so, here or above?
+
+  log_info(LD_GUARD, "Recorded success for %s%sguard %s",
+           guard->is_primary?"primary ":"",
+           guard->confirmed_idx>=0?"confirmed ":"",
+           entry_guard_describe(guard));
+
+  return new_state;
+}
+
+/**
+ * Helper: Return true iff <b>a</b> has higher priority than <b>b</b>.
+ */
+STATIC int
+entry_guard_has_higher_priority(entry_guard_t *a, entry_guard_t *b)
+{
+  tor_assert(a && b);
+  if (a == b)
+    return 0;
+
+  /* Confirmed is always better than unconfirmed; lower index better
+     than higher */
+  if (a->confirmed_idx < 0) {
+    if (b->confirmed_idx >= 0)
+      return 0;
+  } else {
+    if (b->confirmed_idx < 0)
+      return 1;
+
+    /* Lower confirmed_idx is better than higher. */
+    return (a->confirmed_idx < b->confirmed_idx);
+  }
+
+  /* If we reach this point, both are unconfirmed. If one is pending, it
+   * has higher priority. */
+  if (a->is_pending) {
+    if (! b->is_pending)
+      return 1;
+
+    /* Both are pending: earlier last_tried_connect wins. */
+    return a->last_tried_to_connect < b->last_tried_to_connect;
+  } else {
+    if (b->is_pending)
+      return 0;
+
+    /* Neither is pending: priorities are equal. */
+    return 0; // XXXX prop271 return a tristate instead?
+  }
+}
+
+/**
  * Return a newly allocated string for encoding the persistent parts of
  * <b>guard</b> to the state file.
  */
-ATTR_UNUSED STATIC char *
+STATIC char *
 entry_guard_encode_for_state(entry_guard_t *guard)
 {
   /*
@@ -375,7 +1312,7 @@ entry_guard_encode_for_state(entry_guard_t *guard)
  * (if possible) and return an entry_guard_t object for it.  Return NULL
  * on complete failure.
  */
-ATTR_UNUSED STATIC entry_guard_t *
+STATIC entry_guard_t *
 entry_guard_parse_from_state(const char *s)
 {
   /* Unrecognized entries get put in here. */
@@ -492,6 +1429,7 @@ entry_guard_parse_from_state(const char *s)
   /* Take sampled_by_version verbatim. */
   guard->sampled_by_version = sampled_by;
   sampled_by = NULL; /* prevent free */
+  // XXXX -- prop271 spec deviation -- we do not require sampled_by_version
 
   /* Listed is a boolean */
   if (listed && strcmp(listed, "0"))
@@ -518,6 +1456,8 @@ entry_guard_parse_from_state(const char *s)
   /* initialize non-persistent fields */
   guard->is_reachable = GUARD_REACHABLE_MAYBE;
 
+  /* XXXX prop271 Update everything on this guard. */
+
   goto done;
 
  err:
@@ -540,6 +1480,79 @@ entry_guard_parse_from_state(const char *s)
   return guard;
 }
 
+/* XXXXprop271 This is a dummy function added for now so that all of the
+ *  new guard code will be counted as reachable. It should get removed.
+ */
+__attribute__((noreturn)) void
+entry_guards_DUMMY_ENTRY_POINT(void)
+{
+  // prop271 XXXXX kludge; remove this
+  sampled_guards_update_from_consensus(NULL);
+  sample_reachable_filtered_entry_guards(NULL, 0);
+  entry_guards_update_confirmed(NULL);
+  entry_guards_update_primary(NULL);
+  select_entry_guard_for_circuit(NULL, NULL);
+  entry_guards_note_guard_failure(NULL, NULL);
+  entry_guards_note_guard_success(NULL, NULL, 0);
+  entry_guard_has_higher_priority(NULL, NULL);
+  entry_guard_encode_for_state(NULL);
+  entry_guard_parse_from_state(NULL);
+  compare_guards_by_confirmed_idx(NULL, NULL);
+  entry_guards_update_filtered_sets(NULL);
+  tor_assert(0);
+}
+
+/* XXXXX ----------------------------------------------- */
+/* XXXXX prop271 ----- end of new-for-prop271 code ----- */
+/* XXXXX ----------------------------------------------- */
+
+/**
+ * @name Constants for old (pre-prop271) guard selection algorithm.
+ */
+
+/**@{*/
+
+/* Default number of entry guards in the case where the NumEntryGuards
+ * consensus parameter is not set */
+#define DEFAULT_N_GUARDS 1
+/* Minimum and maximum number of entry guards (in case the NumEntryGuards
+ * consensus parameter is set). */
+#define MIN_N_GUARDS 1
+#define MAX_N_GUARDS 10
+/** Largest amount that we'll backdate chosen_on_date */
+#define CHOSEN_ON_DATE_SLOP (30*86400)
+/** How long (in seconds) do we allow an entry guard to be nonfunctional,
+ * unlisted, excluded, or otherwise nonusable before we give up on it? */
+#define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
+/**}@*/
+
+/**
+ * @name Networkstatus parameters for old (pre-prop271) guard selection
+ */
+/**@}*/
+/** Choose how many entry guards or directory guards we'll use. If
+ * <b>for_directory</b> is true, we return how many directory guards to
+ * use; else we return how many entry guards to use. */
+STATIC int
+decide_num_guards(const or_options_t *options, int for_directory)
+{
+  if (for_directory) {
+    int answer;
+    if (options->NumDirectoryGuards != 0)
+      return options->NumDirectoryGuards;
+    answer = networkstatus_get_param(NULL, "NumDirectoryGuards", 0, 0, 10);
+    if (answer) /* non-zero means use the consensus value */
+      return answer;
+  }
+
+  if (options->NumEntryGuards)
+    return options->NumEntryGuards;
+
+  /* Use the value from the consensus, or 3 if no guidance. */
+  return networkstatus_get_param(NULL, "NumEntryGuards", DEFAULT_N_GUARDS,
+                                 MIN_N_GUARDS, MAX_N_GUARDS);
+}
+
 /** Check whether the entry guard <b>e</b> is usable, given the directory
  * authorities' opinion about the router (stored in <b>ri</b>) and the user's
  * configuration (in <b>options</b>). Set <b>e</b>->bad_since
@@ -2402,7 +3415,7 @@ entries_retry_all(const or_options_t *options)
 }
 
 /** Free one guard selection context */
-static void
+STATIC void
 guard_selection_free(guard_selection_t *gs)
 {
   if (!gs) return;
@@ -2421,6 +3434,9 @@ guard_selection_free(guard_selection_t *gs)
     gs->sampled_entry_guards = NULL;
   }
 
+  smartlist_free(gs->confirmed_entry_guards);
+  smartlist_free(gs->primary_entry_guards);
+
   tor_free(gs);
 }
 
diff --git a/src/or/entrynodes.h b/src/or/entrynodes.h
index f07f843..5501e62 100644
--- a/src/or/entrynodes.h
+++ b/src/or/entrynodes.h
@@ -18,10 +18,6 @@ typedef struct guard_selection_s guard_selection_t;
 /* Forward declare for entry_guard_t; the real declaration is private. */
 typedef struct entry_guard_t entry_guard_t;
 
-#define GUARD_REACHABLE_NO    0
-#define GUARD_REACHABLE_YES   1
-#define GUARD_REACHABLE_MAYBE 2
-
 /* Information about a guard's pathbias status.
  * These fields are used in circpathbias.c to try to detect entry
  * nodes that are failing circuits at a suspicious frequency.
@@ -58,6 +54,17 @@ typedef struct guard_pathbias_t {
 } guard_pathbias_t;
 
 #if defined(ENTRYNODES_PRIVATE)
+/**
+ * @name values for entry_guard_t.is_reachable.
+ *
+ * See entry_guard_t.is_reachable for more information.
+ */
+/**@{*/
+#define GUARD_REACHABLE_NO    0
+#define GUARD_REACHABLE_YES   1
+#define GUARD_REACHABLE_MAYBE 2
+/**@}*/
+
 /** An entry_guard_t represents our information about a chosen long-term
  * first hop, known as a "helper" node in the literature. We can't just
  * use a node_t, since we want to remember these even when we
@@ -67,35 +74,80 @@ struct entry_guard_t {
   char identity[DIGEST_LEN];
   ed25519_public_key_t ed_id;
 
-  /* XXXX prop271 DOCDOC document all these fields better */
+  /**
+   * @name new guard selection algorithm fields.
+   *
+   * Only the new (prop271) algorithm uses these.  For a more full
+   * description of the algorithm, see the module documentation for
+   * entrynodes.c
+   */
+  /**@{*/
 
-  /* Persistent fields, present for all sampled guards. */
+  /* == Persistent fields, present for all sampled guards. */
+  /** When was this guard added to the sample? */
   time_t sampled_on_date;
+  /** Since what date has this guard been "unlisted"?  A guard counts as
+   * unlisted if we have a live consensus that does not include it, or
+   * if we have a live consensus that does not include it as a usable
+   * guard.  This field is zero when the guard is listed. */
   time_t unlisted_since_date; // can be zero
+  /** What version of Tor added this guard to the sample? */
   char *sampled_by_version;
+  /** Is this guard listed right now? If this is set, then
+   * unlisted_since_date should be set too. */
   unsigned currently_listed : 1;
 
-  /* Persistent fields, for confirmed guards. */
+  /* == Persistent fields, for confirmed guards only */
+  /** When was this guard confirmed? (That is, when did we first use it
+   * successfully and decide to keep it?) This field is zero if this is not a
+   * confirmed guard. */
   time_t confirmed_on_date; /* 0 if not confirmed */
+  /**
+   * In what order was this guard confirmed? Guards with lower indices
+   * appear earlier on the confirmed list.  If the confirmed list is compacted,
+   * this field corresponds to the index of this guard on the confirmed list.
+   *
+   * This field is set to -1 if this guard is not confirmed.
+   */
   int confirmed_idx; /* -1 if not confirmed; otherwise the order that this
                       * item should occur in the CONFIRMED_GUARDS ordered
                       * list */
 
   /* ==== Non-persistent fields. */
   /* == These are used by sampled guards */
+  /** When did we last decide to try using this guard for a circuit? 0 for
+   * "not since we started up." */
   time_t last_tried_to_connect;
-  unsigned is_reachable : 2; /* One of GUARD_REACHABLE_{NO,YES,MAYBE} */
+  /** How reachable do we consider this guard to be? One of
+   * GUARD_REACHABLE_NO, GUARD_REACHABLE_YES, or GUARD_REACHABLE_MAYBE. */
+  unsigned is_reachable : 2;
+  /** Boolean: true iff this guard is pending. A pending guard is one
+   * that we have an in-progress circuit through, and which we do not plan
+   * to try again until it either succeeds or fails. Primary guards can
+   * never be pending. */
   unsigned is_pending : 1;
+  /** When did we get the earliest connection failure for this guard?
+   * We clear this field on a successful connect.  We do _not_ clear it
+   * when we mark the guard as "MAYBE" reachable.
+   */
   time_t failing_since;
 
-  /* These determine presence in filtered guards and usable-filtered-guards
-   * respectively. */
+  /* == Set inclusion flags. */
+  /** If true, this guard is in the filtered set.  The filtered set includes
+   * all sampled guards that our configuration allows us to use. */
   unsigned is_filtered_guard : 1;
+  /** If true, this guard is in the usable filtered set. The usable filtered
+   * set includes all filtered guards that are not believed to be
+   * unreachable. (That is, those for which is_reachable is not
+   * GUARD_REACHABLE_NO) */
   unsigned is_usable_filtered_guard : 1;
+  unsigned is_primary:1;
 
   /** This string holds any fields that we are maintaining because
    * we saw them in the state, even if we don't understand them. */
   char *extra_state_fields;
+  /**@}*/
+
   /**
    * @name legacy guard selection algorithm fields
    *
@@ -128,6 +180,85 @@ struct entry_guard_t {
   /** Path bias information for this guard. */
   guard_pathbias_t pb;
 };
+
+/**
+ * All of the the context for guard selection on a particular client.
+ *
+ * (XXXX prop271 this paragraph below is not actually implemented yet.)
+ * We maintain multiple guard selection contexts for a client, depending
+ * aspects on its current configuration -- whether an extremely
+ * restrictive EntryNodes is used, whether UseBridges is enabled, and so
+ * on.)
+ *
+ * See the module documentation for entrynodes.c for more information
+ * about guard selection algorithms.
+ */
+struct guard_selection_s {
+  /**
+   * A value of 1 means that guard_selection_t structures have changed
+   * and those changes need to be flushed to disk.
+   *
+   * XXX prop271 we don't know how to flush multiple guard contexts to
+   * disk yet; fix that as soon as any way to change the default exists,
+   * or at least make sure this gets set on change.
+   */
+  int dirty;
+
+  /**
+   * A list of the sampled entry guards, as entry_guard_t structures.
+   * Not in any particular order.  When we 'sample' a guard, we are
+   * noting it as a possible guard to pick in the future. The use of
+   * sampling here prevents us from being forced by an attacker to try
+   * every guard on the network. This list is persistent.
+   */
+  smartlist_t *sampled_entry_guards;
+
+  /**
+   * Ordered list (from highest to lowest priority) of guards that we
+   * have successfully contacted and decided to use. Every member of
+   * this list is a member of sampled_entry_guards. Every member should
+   * have confirmed_on_date set, and have confirmed_idx greater than
+   * any earlier member of the list.
+   *
+   * This list is persistent. It is a subset of the elements in
+   * sampled_entry_guards, and its pointers point to elements of
+   * sampled_entry_guards.
+   */
+  smartlist_t *confirmed_entry_guards;
+
+  /**
+   * Ordered list (from highest to lowest priority) of guards that we
+   * are willing to use the most happily.  These guards may or may not
+   * yet be confirmed yet.  If we can use one of these guards, we are
+   * probably not on a network that is trying to restrict our guard
+   * choices.
+   *
+   * This list is a subset of the elements in
+   * sampled_entry_guards, and its pointers point to elements of
+   * sampled_entry_guards.
+   */
+  smartlist_t *primary_entry_guards;
+
+  /** When did we last successfully build a circuit or use a circuit? */
+  time_t last_time_on_internet;
+
+  /** What confirmed_idx value should the next-added member of
+   * confirmed_entry_guards receive? */
+  int next_confirmed_idx;
+
+  /**
+   * A list of our chosen entry guards, as entry_guard_t structures; this
+   * preserves the pre-Prop271 behavior.
+   */
+  smartlist_t *chosen_entry_guards;
+
+  /**
+   * When we try to choose an entry guard, should we parse and add
+   * config's EntryNodes first?  This was formerly a global.  This
+   * preserves the pre-Prop271 behavior.
+   */
+  int should_add_entry_nodes;
+};
 #endif
 
 #if 1
@@ -160,12 +291,127 @@ void add_bridge_as_entry_guard(guard_selection_t *gs,
 int num_bridges_usable(void);
 
 #ifdef ENTRYNODES_PRIVATE
-STATIC time_t randomize_time(time_t now, time_t max_backdate);
-STATIC void entry_guard_add_to_sample(guard_selection_t *gs,
-                                      node_t *node);
+/**
+ * @name Parameters for the new (prop271) entry guard algorithm.
+ */
+/* XXXX prop271 some of these should be networkstatus parameters */
+/**@{*/
+/**
+ * We never let our sampled guard set grow larger than this fraction
+ * of the guards on the network.
+ */
+#define MAX_SAMPLE_THRESHOLD 0.30
+/**
+ * We always try to make our sample contain at least this many guards.
+ *
+ * XXXX prop271 There was a MIN_SAMPLE_THRESHOLD in the proposal, but I
+ * removed it in favor of MIN_FILTERED_SAMPLE_SIZE. -NM
+ */
+#define MIN_FILTERED_SAMPLE_SIZE 20
+/**
+ * If a guard is unlisted for this many days in a row, we remove it.
+ */
+#define REMOVE_UNLISTED_GUARDS_AFTER_DAYS 20
+/**
+ * We remove unconfirmed guards from the sample after this many days,
+ * regardless of whether they are listed or unlisted.
+ */
+#define GUARD_LIFETIME_DAYS 120
+/**
+ * We remove confirmed guards from the sample if they were sampled
+ * GUARD_LIFETIME_DAYS ago and confirmed this many days ago.
+ */
+#define GUARD_CONFIRMED_MIN_LIFETIME_DAYS 60
+/**
+ * How many guards do we try to keep on our primary guard list?
+ */
+#define N_PRIMARY_GUARDS 3
+/**
+ * If we haven't successfully built or used a circuit in this long, then
+ * consider that the internet is probably down.
+ */
+#define INTERNET_LIKELY_DOWN_INTERVAL (10*60)
+/**
+ * DOCDOC. not yet used; see prop271.
+ */
+#define NONPRIMARY_GUARD_CONNECT_TIMEOUT 15
+/**
+ * DOCDOC. not yet used; see prop271.
+ */
+#define NONPRIMARY_GUARD_IDLE_TIMEOUT (10*60)
+/**
+ * DOCDOC. not yet used; see prop271.
+ */
+#define MEANINGFUL_RESTRICTION_FRAC 0.2
+/**
+ * DOCDOC. not yet used. see prop271.
+ */
+#define EXTREME_RESTRICTION_FRAC 0.01
+/**@}*/
+
+// ---------- XXXX these functions and definitions are post-prop271.
+STATIC guard_selection_t *guard_selection_new(void);
+STATIC void guard_selection_free(guard_selection_t *gs);
+STATIC entry_guard_t *get_sampled_guard_with_id(guard_selection_t *gs,
+                                                const uint8_t *rsa_id);
+
+MOCK_DECL(STATIC time_t, randomize_time, (time_t now, time_t max_backdate));
+STATIC entry_guard_t *entry_guard_add_to_sample(guard_selection_t *gs,
+                                                const node_t *node);
+STATIC entry_guard_t *entry_guards_expand_sample(guard_selection_t *gs);
 STATIC char *entry_guard_encode_for_state(entry_guard_t *guard);
 STATIC entry_guard_t *entry_guard_parse_from_state(const char *s);
 STATIC void entry_guard_free(entry_guard_t *e);
+STATIC void entry_guards_update_filtered_sets(guard_selection_t *gs);
+/**
+ * @name Flags for sample_reachable_filtered_entry_guards()
+ */
+/**@{*/
+#define SAMPLE_EXCLUDE_CONFIRMED   (1u<<0)
+#define SAMPLE_EXCLUDE_PRIMARY     (1u<<1)
+#define SAMPLE_EXCLUDE_PENDING     (1u<<2)
+/**@}*/
+STATIC entry_guard_t *sample_reachable_filtered_entry_guards(
+                                    guard_selection_t *gs,
+                                    unsigned flags);
+STATIC void entry_guard_consider_retry(entry_guard_t *guard);
+STATIC void make_guard_confirmed(guard_selection_t *gs, entry_guard_t *guard);
+STATIC void entry_guards_update_confirmed(guard_selection_t *gs);
+STATIC void entry_guards_update_primary(guard_selection_t *gs);
+STATIC int num_reachable_filtered_guards(guard_selection_t *gs);
+STATIC void sampled_guards_update_from_consensus(guard_selection_t *gs);
+/**
+ * @name Possible guard-states for a circuit.
+ */
+/**@{*/
+/** State for a circuit that can (so far as the guard subsystem is
+ * concerned) be used for actual traffic as soon as it is successfully
+ * opened. */
+#define GUARD_CIRC_STATE_USABLE_ON_COMPLETION 1
+/** State for an non-open circuit that we shouldn't use for actual
+ * traffic, when it completes, unless other circuits to preferable
+ * guards fail. */
+#define GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD 2
+/** State for an open circuit that we shouldn't use for actual traffic
+ * unless other circuits to preferable guards fail. */
+#define GUARD_CIRC_STATE_WAITING_FOR_BETTER_GUARD 3
+/** State for a circuit that can (so far as the guard subsystem is
+ * concerned) be used for actual traffic. */
+#define GUARD_CIRC_STATE_COMPLETE 4
+/**@}*/
+STATIC void entry_guards_note_guard_failure(guard_selection_t *gs,
+                                            entry_guard_t *guard);
+STATIC entry_guard_t *select_entry_guard_for_circuit(guard_selection_t *gs,
+                                                     unsigned *state_out);
+STATIC void mark_primary_guards_maybe_reachable(guard_selection_t *gs);
+STATIC unsigned entry_guards_note_guard_success(guard_selection_t *gs,
+                                                entry_guard_t *guard,
+                                                unsigned old_state);
+STATIC int entry_guard_has_higher_priority(entry_guard_t *a, entry_guard_t *b);
+
+void entry_guards_DUMMY_ENTRY_POINT(void);
+
+// ---------- XXXX this stuff is pre-prop271.
 
 STATIC const node_t *add_an_entry_guard(guard_selection_t *gs,
                                         const node_t *chosen,
diff --git a/src/test/test_entrynodes.c b/src/test/test_entrynodes.c
index 45b730c..8e90b00 100644
--- a/src/test/test_entrynodes.c
+++ b/src/test/test_entrynodes.c
@@ -10,9 +10,11 @@
 #include "or.h"
 #include "test.h"
 
+#include "bridges.h"
 #include "config.h"
 #include "entrynodes.h"
 #include "nodelist.h"
+#include "networkstatus.h"
 #include "policies.h"
 #include "routerlist.h"
 #include "routerparse.h"
@@ -21,6 +23,7 @@
 #include "util.h"
 
 #include "test_helpers.h"
+#include "log_test_helpers.h"
 
 /* TODO:
  * choose_random_entry() test with state set.
@@ -72,6 +75,120 @@ fake_network_setup(const struct testcase_t *testcase)
   return dummy_state;
 }
 
+static networkstatus_t *dummy_consensus = NULL;
+
+static smartlist_t *big_fake_net_nodes = NULL;
+
+static smartlist_t *
+bfn_mock_nodelist_get_list(void)
+{
+  return big_fake_net_nodes;
+}
+
+static networkstatus_t *
+bfn_mock_networkstatus_get_live_consensus(time_t now)
+{
+  (void)now;
+  return dummy_consensus;
+}
+
+static const node_t *
+bfn_mock_node_get_by_id(const char *id)
+{
+  SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n,
+                    if (fast_memeq(n->identity, id, 20))
+                      return n);
+
+  return NULL;
+}
+
+/* Unittest cleanup function: Cleanup the fake network. */
+static int
+big_fake_network_cleanup(const struct testcase_t *testcase, void *ptr)
+{
+  (void) testcase;
+  (void) ptr;
+
+  if (big_fake_net_nodes) {
+    SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n, {
+      tor_free(n->rs);
+      tor_free(n->md);
+      tor_free(n);
+    });
+    smartlist_free(big_fake_net_nodes);
+  }
+
+  UNMOCK(nodelist_get_list);
+  UNMOCK(node_get_by_id);
+  UNMOCK(get_or_state);
+  UNMOCK(networkstatus_get_live_consensus);
+  or_state_free(dummy_state);
+  dummy_state = NULL;
+  tor_free(dummy_consensus);
+
+  return 1; /* NOP */
+}
+
+/* Unittest setup function: Setup a fake network. */
+static void *
+big_fake_network_setup(const struct testcase_t *testcase)
+{
+  int i;
+
+  /* These are minimal node_t objects that only contain the aspects of node_t
+   * that we need for entrynodes.c. */
+  const int N_NODES = 271;
+
+  big_fake_net_nodes = smartlist_new();
+  for (i = 0; i < N_NODES; ++i) {
+    node_t *n = tor_malloc_zero(sizeof(node_t));
+    n->md = tor_malloc_zero(sizeof(microdesc_t));
+
+    crypto_rand(n->identity, sizeof(n->identity));
+    n->rs = tor_malloc_zero(sizeof(routerstatus_t));
+
+    memcpy(n->rs->identity_digest, n->identity, DIGEST_LEN);
+
+    n->is_running = n->is_valid = n->is_fast = n->is_stable = 1;
+
+    n->rs->addr = 0x04020202;
+    n->rs->or_port = 1234;
+    n->rs->is_v2_dir = 1;
+    n->rs->has_bandwidth = 1;
+    n->rs->bandwidth_kb = 30;
+
+    /* Call half of the nodes a possible guard. */
+    if (i % 2 == 0) {
+      n->is_possible_guard = 1;
+      n->rs->guardfraction_percentage = 100;
+      n->rs->has_guardfraction = 1;
+    }
+
+    smartlist_add(big_fake_net_nodes, n);
+  }
+
+  dummy_state = tor_malloc_zero(sizeof(or_state_t));
+  dummy_consensus = tor_malloc_zero(sizeof(networkstatus_t));
+  dummy_consensus->valid_after = approx_time() - 3600;
+  dummy_consensus->valid_until = approx_time() + 3600;
+
+  MOCK(nodelist_get_list, bfn_mock_nodelist_get_list);
+  MOCK(node_get_by_id, bfn_mock_node_get_by_id);
+  MOCK(get_or_state,
+       get_or_state_replacement);
+  MOCK(networkstatus_get_live_consensus,
+       bfn_mock_networkstatus_get_live_consensus);
+  /* Return anything but NULL (it's interpreted as test fail) */
+  return (void*)testcase;
+}
+
+static time_t
+mock_randomize_time_no_randomization(time_t a, time_t b)
+{
+  (void) b;
+  return a;
+}
+
 static or_options_t mocked_options;
 
 static const or_options_t *
@@ -1089,10 +1206,972 @@ test_entry_guard_parse_from_state_partial_failure(void *arg)
   tor_free(mem_op_hex_tmp);
 }
 
+static void
+test_entry_guard_add_single_guard(void *arg)
+{
+  (void)arg;
+  guard_selection_t *gs = guard_selection_new();
+
+  /* 1: Add a single guard to the sample. */
+  node_t *n1 = smartlist_get(big_fake_net_nodes, 0);
+  time_t now = approx_time();
+  tt_assert(n1->is_possible_guard == 1);
+  entry_guard_t *g1 = entry_guard_add_to_sample(gs, n1);
+  tt_assert(g1);
+
+  /* Make sure its fields look right. */
+  tt_mem_op(n1->identity, OP_EQ, g1->identity, DIGEST_LEN);
+  tt_i64_op(g1->sampled_on_date, OP_GE, now - 12*86400);
+  tt_i64_op(g1->sampled_on_date, OP_LE, now);
+  tt_str_op(g1->sampled_by_version, OP_EQ, VERSION);
+  tt_assert(g1->currently_listed == 1);
+  tt_i64_op(g1->confirmed_on_date, OP_EQ, 0);
+  tt_int_op(g1->confirmed_idx, OP_EQ, -1);
+  tt_int_op(g1->last_tried_to_connect, OP_EQ, 0);
+  tt_uint_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE);
+  tt_i64_op(g1->failing_since, OP_EQ, 0);
+  tt_assert(g1->is_filtered_guard == 1);
+  tt_assert(g1->is_usable_filtered_guard == 1);
+  tt_assert(g1->is_primary == 0);
+  tt_assert(g1->extra_state_fields == NULL);
+
+  /* Make sure it got added. */
+  tt_int_op(1, OP_EQ, smartlist_len(gs->sampled_entry_guards));
+  tt_ptr_op(g1, OP_EQ, smartlist_get(gs->sampled_entry_guards, 0));
+  tt_ptr_op(g1, OP_EQ, get_sampled_guard_with_id(gs, (uint8_t*)n1->identity));
+  const uint8_t bad_id[20] = {0};
+  tt_ptr_op(NULL, OP_EQ, get_sampled_guard_with_id(gs, bad_id));
+
+ done:
+  guard_selection_free(gs);
+}
+
+static void
+test_entry_guard_node_filter(void *arg)
+{
+  (void)arg;
+  guard_selection_t *gs = guard_selection_new();
+  bridge_line_t *bl = NULL;
+
+  /* Initialize a bunch of node objects that are all guards. */
+  const int NUM = 7;
+  node_t *n[NUM];
+  entry_guard_t *g[NUM];
+  int i;
+  for (i=0; i < NUM; ++i) {
+    n[i] = smartlist_get(big_fake_net_nodes, i*2); // even ones are guards.
+    g[i] = entry_guard_add_to_sample(gs, n[i]);
+
+    // everything starts out filtered-in
+    tt_assert(g[i]->is_filtered_guard == 1);
+    tt_assert(g[i]->is_usable_filtered_guard == 1);
+  }
+  tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, NUM);
+
+  /* Make sure refiltering doesn't hurt */
+  entry_guards_update_filtered_sets(gs);
+  for (i = 0; i < NUM; ++i) {
+    tt_assert(g[i]->is_filtered_guard == 1);
+    tt_assert(g[i]->is_usable_filtered_guard == 1);
+  }
+  tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, NUM);
+
+  /* Now start doing things to make the guards get filtered out, 1 by 1. */
+
+  /* 0: Not listed. */
+  g[0]->currently_listed = 0;
+
+  /* 1: path bias says this guard is maybe eeeevil. */
+  g[1]->pb.path_bias_disabled = 1;
+
+  /* 2: Unreachable address. */
+  n[2]->rs->addr = 0;
+
+  /* 3: ExcludeNodes */
+  n[3]->rs->addr = 0x90902020;
+  routerset_free(get_options_mutable()->ExcludeNodes);
+  get_options_mutable()->ExcludeNodes = routerset_new();
+  routerset_parse(get_options_mutable()->ExcludeNodes, "144.144.0.0/16", "");
+
+  /* 4: Bridge. */
+  sweep_bridge_list();
+  bl = tor_malloc_zero(sizeof(bridge_line_t));
+  tor_addr_from_ipv4h(&bl->addr, n[4]->rs->addr);
+  bl->port = n[4]->rs->or_port;
+  memcpy(bl->digest, n[4]->identity, 20);
+  bridge_add_from_config(bl);
+  bl = NULL; // prevent free.
+
+  /* 5: Unreachable. This stays in the filter, but isn't in usable-filtered */
+  g[5]->last_tried_to_connect = approx_time(); // prevent retry.
+  g[5]->is_reachable = GUARD_REACHABLE_NO;
+
+  /* 6: no change. */
+
+  /* Now refilter and inspect. */
+  entry_guards_update_filtered_sets(gs);
+  for (i = 0; i < NUM; ++i) {
+    tt_assert(g[i]->is_filtered_guard == (i == 5 || i == 6));
+    tt_assert(g[i]->is_usable_filtered_guard == (i == 6));
+  }
+  tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, 1);
+
+ done:
+  guard_selection_free(gs);
+  tor_free(bl);
+}
+
+static void
+test_entry_guard_expand_sample(void *arg)
+{
+  (void)arg;
+  guard_selection_t *gs = guard_selection_new();
+  digestmap_t *node_by_id = digestmap_new();
+
+  entry_guard_t *guard = entry_guards_expand_sample(gs);
+  tt_assert(guard); // the last guard returned.
+
+  // Every sampled guard here should be filtered and reachable for now.
+  tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ,
+            num_reachable_filtered_guards(gs));
+
+  /* Make sure we got the right number. */
+  tt_int_op(MIN_FILTERED_SAMPLE_SIZE, OP_EQ,
+            num_reachable_filtered_guards(gs));
+
+  // Make sure everything we got was from our fake node list, and everything
+  // was unique.
+  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, g) {
+    const node_t *n = bfn_mock_node_get_by_id(g->identity);
+    tt_assert(n);
+    tt_ptr_op(NULL, OP_EQ, digestmap_get(node_by_id, g->identity));
+    digestmap_set(node_by_id, g->identity, (void*) n);
+    int idx = smartlist_pos(big_fake_net_nodes, n);
+    // The even ones are the guards; make sure we got guards.
+    tt_int_op(idx & 1, OP_EQ, 0);
+  } SMARTLIST_FOREACH_END(g);
+
+  // Nothing became unusable/unfiltered, so a subsequent expand should
+  // make no changes.
+  guard = entry_guards_expand_sample(gs);
+  tt_assert(! guard); // no guard was added.
+  tt_int_op(MIN_FILTERED_SAMPLE_SIZE, OP_EQ,
+            num_reachable_filtered_guards(gs));
+
+  // Make a few guards unreachable.
+  guard = smartlist_get(gs->sampled_entry_guards, 0);
+  guard->is_usable_filtered_guard = 0;
+  guard = smartlist_get(gs->sampled_entry_guards, 1);
+  guard->is_usable_filtered_guard = 0;
+  guard = smartlist_get(gs->sampled_entry_guards, 2);
+  guard->is_usable_filtered_guard = 0;
+  tt_int_op(MIN_FILTERED_SAMPLE_SIZE - 3, OP_EQ,
+            num_reachable_filtered_guards(gs));
+
+  // This time, expanding the sample will add some more guards.
+  guard = entry_guards_expand_sample(gs);
+  tt_assert(guard); // no guard was added.
+  tt_int_op(MIN_FILTERED_SAMPLE_SIZE, OP_EQ,
+            num_reachable_filtered_guards(gs));
+  tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ,
+            num_reachable_filtered_guards(gs)+3);
+
+  // Still idempotent.
+  guard = entry_guards_expand_sample(gs);
+  tt_assert(! guard); // no guard was added.
+  tt_int_op(MIN_FILTERED_SAMPLE_SIZE, OP_EQ,
+            num_reachable_filtered_guards(gs));
+
+  // Now, do a nasty trick: tell the filter to exclude 31/32 of the guards.
+  // This will cause the sample size to get reeeeally huge, while the
+  // filtered sample size grows only slowly.
+  routerset_free(get_options_mutable()->ExcludeNodes);
+  get_options_mutable()->ExcludeNodes = routerset_new();
+  routerset_parse(get_options_mutable()->ExcludeNodes, "144.144.0.0/16", "");
+  SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n, {
+    if (n_sl_idx % 64 != 0) {
+      n->rs->addr = 0x90903030;
+    }
+  });
+  entry_guards_update_filtered_sets(gs);
+
+  // Surely (p ~ 1-2**-60), one of our guards has been excluded.
+  tt_int_op(num_reachable_filtered_guards(gs), OP_LT,
+            MIN_FILTERED_SAMPLE_SIZE);
+
+  // Try to regenerate the guards.
+  guard = entry_guards_expand_sample(gs);
+  tt_assert(guard); // no guard was added.
+
+  /* this time, it's possible that we didn't add enough sampled guards. */
+  tt_int_op(num_reachable_filtered_guards(gs), OP_LE,
+            MIN_FILTERED_SAMPLE_SIZE);
+  /* but we definitely didn't exceed the sample maximum. */
+  tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_LE,
+            (int)((271 / 2) * .3));
+
+ done:
+  guard_selection_free(gs);
+  digestmap_free(node_by_id, NULL);
+}
+
+static void
+test_entry_guard_expand_sample_small_net(void *arg)
+{
+  (void)arg;
+  guard_selection_t *gs = guard_selection_new();
+
+  /* Fun corner case: not enough guards to make up our whole sample size. */
+  SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n, {
+    if (n_sl_idx >= 40) {
+      tor_free(n->rs);
+      tor_free(n->md);
+      tor_free(n);
+      SMARTLIST_DEL_CURRENT(big_fake_net_nodes, n);
+    } else {
+      n->rs->addr = 0; // make the filter reject this.
+    }
+  });
+
+  entry_guard_t *guard = entry_guards_expand_sample(gs);
+  tt_assert(guard); // the last guard returned -- some guard was added.
+  tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_GT, 0);
+  tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_LT, 10);
+  tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, 0);
+ done:
+  guard_selection_free(gs);
+}
+
+static void
+test_entry_guard_update_from_consensus_status(void *arg)
+{
+  /* Here we're going to have some nodes become un-guardy, and say we got a
+   * new consensus. This should cause those nodes to get detected as
+   * unreachable. */
+
+  (void)arg;
+  int i;
+  time_t start = approx_time();
+  guard_selection_t *gs = guard_selection_new();
+  networkstatus_t *ns_tmp = NULL;
+
+  /* Don't randomly backdate stuff; it will make correctness harder to check.*/
+  MOCK(randomize_time, mock_randomize_time_no_randomization);
+
+  /* First, sample some guards. */
+  entry_guards_expand_sample(gs);
+  int n_sampled_pre = smartlist_len(gs->sampled_entry_guards);
+  int n_filtered_pre = num_reachable_filtered_guards(gs);
+  tt_i64_op(n_sampled_pre, OP_EQ, n_filtered_pre);
+  tt_i64_op(n_sampled_pre, OP_GT, 10);
+
+  /* At this point, it should be a no-op to do this: */
+  sampled_guards_update_from_consensus(gs);
+
+  /* Now let's make some of our guards become unlisted.  The easiest way to
+   * do that would be to take away their guard flag. */
+  for (i = 0; i < 5; ++i) {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i);
+    node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity);
+    n->is_possible_guard = 0;
+  }
+
+  update_approx_time(start + 30);
+  {
+    /* try this with no live networkstatus. Nothing should happen! */
+    ns_tmp = dummy_consensus;
+    dummy_consensus = NULL;
+    sampled_guards_update_from_consensus(gs);
+    tt_i64_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre);
+    tt_i64_op(num_reachable_filtered_guards(gs), OP_EQ, n_filtered_pre);
+    /* put the networkstatus back. */
+    dummy_consensus = ns_tmp;
+    ns_tmp = NULL;
+  }
+
+  /* Now those guards should become unlisted, and drop off the filter, but
+   * stay in the sample. */
+  update_approx_time(start + 60);
+  sampled_guards_update_from_consensus(gs);
+
+  tt_i64_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre);
+  tt_i64_op(num_reachable_filtered_guards(gs), OP_EQ, n_filtered_pre - 5);
+  for (i = 0; i < 5; ++i) {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i);
+    tt_assert(! g->currently_listed);
+    tt_i64_op(g->unlisted_since_date, OP_EQ, start+60);
+  }
+  for (i = 5; i < n_sampled_pre; ++i) {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i);
+    tt_assert(g->currently_listed);
+    tt_i64_op(g->unlisted_since_date, OP_EQ, 0);
+  }
+
+  /* Now re-list one, and remove one completely. */
+  {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 0);
+    node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity);
+    n->is_possible_guard = 1;
+  }
+  {
+    /* try removing the node, to make sure we don't crash on an absent node
+     */
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 5);
+    node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity);
+    smartlist_remove(big_fake_net_nodes, n);
+    tor_free(n->rs);
+    tor_free(n->md);
+    tor_free(n);
+  }
+  update_approx_time(start + 300);
+  sampled_guards_update_from_consensus(gs);
+
+  /* guards 1..5 are now unlisted; 0,6,7.. are listed. */
+  tt_i64_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre);
+  for (i = 1; i < 6; ++i) {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i);
+    tt_assert(! g->currently_listed);
+    if (i == 5)
+      tt_i64_op(g->unlisted_since_date, OP_EQ, start+300);
+    else
+      tt_i64_op(g->unlisted_since_date, OP_EQ, start+60);
+  }
+  for (i = 0; i < n_sampled_pre; i = (!i) ? 6 : i+1) { /* 0,6,7,8, ... */
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i);
+    tt_assert(g->currently_listed);
+    tt_i64_op(g->unlisted_since_date, OP_EQ, 0);
+  }
+
+ done:
+  tor_free(ns_tmp); /* in case we couldn't put it back */
+  guard_selection_free(gs);
+  UNMOCK(randomize_time);
+}
+
+static void
+test_entry_guard_update_from_consensus_repair(void *arg)
+{
+  /* Here we'll make sure that our code to repair the unlisted-since
+   * times is correct. */
+
+  (void)arg;
+  int i;
+  time_t start = approx_time();
+  guard_selection_t *gs = guard_selection_new();
+
+  /* Don't randomly backdate stuff; it will make correctness harder to check.*/
+  MOCK(randomize_time, mock_randomize_time_no_randomization);
+
+  /* First, sample some guards. */
+  entry_guards_expand_sample(gs);
+  int n_sampled_pre = smartlist_len(gs->sampled_entry_guards);
+  int n_filtered_pre = num_reachable_filtered_guards(gs);
+  tt_i64_op(n_sampled_pre, OP_EQ, n_filtered_pre);
+  tt_i64_op(n_sampled_pre, OP_GT, 10);
+
+  /* Now corrupt the list a bit.  Call some unlisted-since-never, and some
+   * listed-and-unlisted-since-a-time. */
+  update_approx_time(start + 300);
+  for (i = 0; i < 3; ++i) {
+    /* these will get a date. */
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i);
+    node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity);
+    n->is_possible_guard = 0;
+    g->currently_listed = 0;
+  }
+  for (i = 3; i < 6; ++i) {
+    /* these will become listed. */
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i);
+    g->unlisted_since_date = start+100;
+  }
+  setup_full_capture_of_logs(LOG_WARN);
+  sampled_guards_update_from_consensus(gs);
+  expect_log_msg_containing(
+             "was listed, but with unlisted_since_date set");
+  expect_log_msg_containing(
+             "was unlisted, but with unlisted_since_date unset");
+  teardown_capture_of_logs();
+
+  tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre);
+  tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, n_filtered_pre - 3);
+  for (i = 3; i < n_sampled_pre; ++i) {
+    /* these will become listed. */
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i);
+    if (i < 3) {
+      tt_assert(! g->currently_listed);
+      tt_i64_op(g->unlisted_since_date, OP_EQ, start+300);
+    } else {
+      tt_assert(g->currently_listed);
+      tt_i64_op(g->unlisted_since_date, OP_EQ, 0);
+    }
+  }
+
+ done:
+  teardown_capture_of_logs();
+  guard_selection_free(gs);
+  UNMOCK(randomize_time);
+}
+
+static void
+test_entry_guard_update_from_consensus_remove(void *arg)
+{
+  /* Now let's check the logic responsible for removing guards from the
+   * sample entirely. */
+
+  (void)arg;
+  //int i;
+  guard_selection_t *gs = guard_selection_new();
+  smartlist_t *keep_ids = smartlist_new();
+  smartlist_t *remove_ids = smartlist_new();
+
+  /* Don't randomly backdate stuff; it will make correctness harder to check.*/
+  MOCK(randomize_time, mock_randomize_time_no_randomization);
+
+  /* First, sample some guards. */
+  entry_guards_expand_sample(gs);
+  int n_sampled_pre = smartlist_len(gs->sampled_entry_guards);
+  int n_filtered_pre = num_reachable_filtered_guards(gs);
+  tt_i64_op(n_sampled_pre, OP_EQ, n_filtered_pre);
+  tt_i64_op(n_sampled_pre, OP_GT, 10);
+
+  const time_t one_day_ago = approx_time() - 1*24*60*60;
+  const time_t one_year_ago = approx_time() - 365*24*60*60;
+  const time_t two_years_ago = approx_time() - 2*365*24*60*60;
+  /* 0: unlisted for a day. (keep this) */
+  {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 0);
+    node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity);
+    n->is_possible_guard = 0;
+    g->currently_listed = 0;
+    g->unlisted_since_date = one_day_ago;
+    smartlist_add(keep_ids, tor_memdup(g->identity, 20));
+  }
+  /* 1: unlisted for a year. (remove this) */
+  {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 1);
+    node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity);
+    n->is_possible_guard = 0;
+    g->currently_listed = 0;
+    g->unlisted_since_date = one_year_ago;
+    smartlist_add(remove_ids, tor_memdup(g->identity, 20));
+  }
+  /* 2: added a day ago, never confirmed. (keep this) */
+  {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 2);
+    g->sampled_on_date = one_day_ago;
+    smartlist_add(keep_ids, tor_memdup(g->identity, 20));
+  }
+  /* 3: added a year ago, never confirmed. (remove this) */
+  {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 3);
+    g->sampled_on_date = one_year_ago;
+    smartlist_add(remove_ids, tor_memdup(g->identity, 20));
+  }
+  /* 4: added two year ago, confirmed yesterday, primary. (keep this.) */
+  {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 4);
+    g->sampled_on_date = one_year_ago;
+    g->confirmed_on_date = one_day_ago;
+    g->confirmed_idx = 0;
+    g->is_primary = 1;
+    smartlist_add(gs->confirmed_entry_guards, g);
+    smartlist_add(gs->primary_entry_guards, g);
+    smartlist_add(keep_ids, tor_memdup(g->identity, 20));
+  }
+  /* 5: added two years ago, confirmed a year ago, primary. (remove this) */
+  {
+    entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 5);
+    g->sampled_on_date = two_years_ago;
+    g->confirmed_on_date = one_year_ago;
+    g->confirmed_idx = 1;
+    g->is_primary = 1;
+    smartlist_add(gs->confirmed_entry_guards, g);
+    smartlist_add(gs->primary_entry_guards, g);
+    smartlist_add(remove_ids, tor_memdup(g->identity, 20));
+  }
+
+  sampled_guards_update_from_consensus(gs);
+
+  /* Did we remove the right ones? */
+  SMARTLIST_FOREACH(keep_ids, uint8_t *, id, {
+      tt_assert(get_sampled_guard_with_id(gs, id) != NULL);
+  });
+  SMARTLIST_FOREACH(remove_ids, uint8_t *, id, {
+    tt_want(get_sampled_guard_with_id(gs, id) == NULL);
+  });
+
+  /* Did we remove the right number? */
+  tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre - 3);
+
+ done:
+  guard_selection_free(gs);
+  UNMOCK(randomize_time);
+  SMARTLIST_FOREACH(keep_ids, char *, cp, tor_free(cp));
+  SMARTLIST_FOREACH(remove_ids, char *, cp, tor_free(cp));
+  smartlist_free(keep_ids);
+  smartlist_free(remove_ids);
+}
+
+static void
+test_entry_guard_confirming_guards(void *arg)
+{
+  (void)arg;
+  /* Now let's check the logic responsible for manipulating the list
+   * of confirmed guards */
+  guard_selection_t *gs = guard_selection_new();
+  MOCK(randomize_time, mock_randomize_time_no_randomization);
+
+  /* Create the sample. */
+  entry_guards_expand_sample(gs);
+
+  /* Confirm a few  guards. */
+  time_t start = approx_time();
+  entry_guard_t *g1 = smartlist_get(gs->sampled_entry_guards, 0);
+  entry_guard_t *g2 = smartlist_get(gs->sampled_entry_guards, 1);
+  entry_guard_t *g3 = smartlist_get(gs->sampled_entry_guards, 8);
+  make_guard_confirmed(gs, g2);
+  update_approx_time(start + 10);
+  make_guard_confirmed(gs, g1);
+  make_guard_confirmed(gs, g3);
+
+  /* Were the correct dates and indices fed in? */
+  tt_int_op(g1->confirmed_idx, OP_EQ, 1);
+  tt_int_op(g2->confirmed_idx, OP_EQ, 0);
+  tt_int_op(g3->confirmed_idx, OP_EQ, 2);
+  tt_i64_op(g1->confirmed_on_date, OP_EQ, start+10);
+  tt_i64_op(g2->confirmed_on_date, OP_EQ, start);
+  tt_i64_op(g3->confirmed_on_date, OP_EQ, start+10);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g2);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g1);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 2), OP_EQ, g3);
+
+  /* Now make sure we can regenerate the confirmed_entry_guards list. */
+  smartlist_clear(gs->confirmed_entry_guards);
+  g2->confirmed_idx = 0;
+  g1->confirmed_idx = 10;
+  g3->confirmed_idx = 100;
+  entry_guards_update_confirmed(gs);
+  tt_int_op(g1->confirmed_idx, OP_EQ, 1);
+  tt_int_op(g2->confirmed_idx, OP_EQ, 0);
+  tt_int_op(g3->confirmed_idx, OP_EQ, 2);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g2);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g1);
+  tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 2), OP_EQ, g3);
+
+  /* Now make sure we can regenerate the confirmed_entry_guards list if
+   * the indices are messed up. */
+  g1->confirmed_idx = g2->confirmed_idx = g3->confirmed_idx = 999;
+  smartlist_clear(gs->confirmed_entry_guards);
+  entry_guards_update_confirmed(gs);
+  tt_int_op(g1->confirmed_idx, OP_GE, 0);
+  tt_int_op(g2->confirmed_idx, OP_GE, 0);
+  tt_int_op(g3->confirmed_idx, OP_GE, 0);
+  tt_int_op(g1->confirmed_idx, OP_LE, 2);
+  tt_int_op(g2->confirmed_idx, OP_LE, 2);
+  tt_int_op(g3->confirmed_idx, OP_LE, 2);
+  g1 = smartlist_get(gs->confirmed_entry_guards, 0);
+  g2 = smartlist_get(gs->confirmed_entry_guards, 1);
+  g3 = smartlist_get(gs->confirmed_entry_guards, 2);
+  tt_int_op(g1->confirmed_idx, OP_EQ, 0);
+  tt_int_op(g2->confirmed_idx, OP_EQ, 1);
+  tt_int_op(g3->confirmed_idx, OP_EQ, 2);
+  tt_assert(g1 != g2);
+  tt_assert(g1 != g3);
+  tt_assert(g2 != g3);
+
+ done:
+  UNMOCK(randomize_time);
+  guard_selection_free(gs);
+}
+
+static void
+test_entry_guard_sample_reachable_filtered(void *arg)
+{
+  (void)arg;
+  guard_selection_t *gs = guard_selection_new();
+  entry_guards_expand_sample(gs);
+  const int N = 10000;
+  bitarray_t *selected = NULL;
+  int i, j;
+
+  /* We've got a sampled list now; let's make one non-usable-filtered; some
+   * confirmed, some primary, some pending.
+   */
+  int n_guards = smartlist_len(gs->sampled_entry_guards);
+  tt_int_op(n_guards, OP_GT, 10);
+  entry_guard_t *g;
+  g = smartlist_get(gs->sampled_entry_guards, 0);
+  g->is_pending = 1;
+  g = smartlist_get(gs->sampled_entry_guards, 1);
+  make_guard_confirmed(gs, g);
+  g = smartlist_get(gs->sampled_entry_guards, 2);
+  g->is_primary = 1;
+  g = smartlist_get(gs->sampled_entry_guards, 3);
+  g->pb.path_bias_disabled = 1;
+
+  entry_guards_update_filtered_sets(gs);
+  tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, n_guards - 1);
+  tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_guards);
+
+  // +1 since the one we made disabled will make  another one get added.
+  ++n_guards;
+
+  /* Try a bunch of selections. */
+  const struct {
+    int flag; int idx;
+  } tests[] = {
+    { 0, -1 },
+    { SAMPLE_EXCLUDE_CONFIRMED, 1 },
+    { SAMPLE_EXCLUDE_PRIMARY, 2 },
+    { SAMPLE_EXCLUDE_PENDING, 0 },
+    { -1, -1},
+  };
+
+  for (j = 0; tests[j].flag >= 0; ++j) {
+    selected = bitarray_init_zero(n_guards);
+    const int excluded_flags = tests[j].flag;
+    const int excluded_idx = tests[j].idx;
+    for (i = 0; i < N; ++i) {
+      g = sample_reachable_filtered_entry_guards(gs, excluded_flags);
+      tor_assert(g);
+      int pos = smartlist_pos(gs->sampled_entry_guards, g);
+      tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_guards);
+      tt_int_op(pos, OP_GE, 0);
+      tt_int_op(pos, OP_LT, n_guards);
+      bitarray_set(selected, pos);
+    }
+    for (i = 0; i < n_guards; ++i) {
+      const int should_be_set = (i != excluded_idx &&
+                                 i != 3); // filtered out.
+      tt_int_op(!!bitarray_is_set(selected, i), OP_EQ, should_be_set);
+    }
+    bitarray_free(selected);
+    selected = NULL;
+  }
+
+ done:
+  guard_selection_free(gs);
+  bitarray_free(selected);
+}
+
+static void
+test_entry_guard_sample_reachable_filtered_empty(void *arg)
+{
+  (void)arg;
+  guard_selection_t *gs = guard_selection_new();
+  /* What if we try to sample from a set of 0? */
+  SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n,
+                    n->is_possible_guard = 0);
+
+  entry_guard_t *g = sample_reachable_filtered_entry_guards(gs, 0);
+  tt_ptr_op(g, OP_EQ, NULL);
+
+ done:
+  guard_selection_free(gs);
+}
+
+static void
+test_entry_guard_retry_unreachable(void *arg)
+{
+  (void)arg;
+  guard_selection_t *gs = guard_selection_new();
+
+  entry_guards_expand_sample(gs);
+  /* Let's say that we have two guards, and they're down.
+   */
+  time_t start = approx_time();;
+  entry_guard_t *g1 = smartlist_get(gs->sampled_entry_guards, 0);
+  entry_guard_t *g2 = smartlist_get(gs->sampled_entry_guards, 1);
+  entry_guard_t *g3 = smartlist_get(gs->sampled_entry_guards, 2);
+  g1->is_reachable = GUARD_REACHABLE_NO;
+  g2->is_reachable = GUARD_REACHABLE_NO;
+  g1->is_primary = 1;
+  g1->failing_since = g2->failing_since = start;
+  g1->last_tried_to_connect = g2->last_tried_to_connect = start;
+
+  /* Wait 5 minutes.  Nothing will get retried. */
+  update_approx_time(start + 5 * 60);
+  entry_guard_consider_retry(g1);
+  entry_guard_consider_retry(g2);
+  entry_guard_consider_retry(g3); // just to make sure this doesn't crash.
+  tt_int_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_NO);
+  tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_NO);
+  tt_int_op(g3->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE);
+
+  /* After 30 min, the primary one gets retried */
+  update_approx_time(start + 35 * 60);
+  entry_guard_consider_retry(g1);
+  entry_guard_consider_retry(g2);
+  tt_int_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE);
+  tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_NO);
+
+  g1->is_reachable = GUARD_REACHABLE_NO;
+  g1->last_tried_to_connect = start + 35*60;
+
+  /* After 1 hour, we'll retry the nonprimary one. */
+  update_approx_time(start + 61 * 60);
+  entry_guard_consider_retry(g1);
+  entry_guard_consider_retry(g2);
+  tt_int_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_NO);
+  tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE);
+
+  g2->is_reachable = GUARD_REACHABLE_NO;
+  g2->last_tried_to_connect = start + 61*60;
+
+  /* And then the primary one again. */
+  update_approx_time(start + 66 * 60);
+  entry_guard_consider_retry(g1);
+  entry_guard_consider_retry(g2);
+  tt_int_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE);
+  tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_NO);
+
+ done:
+  guard_selection_free(gs);
+}
+
+static void
+test_entry_guard_manage_primary(void *arg)
+{
+  (void)arg;
+  guard_selection_t *gs = guard_selection_new();
+  smartlist_t *prev_guards = smartlist_new();
+
+  /* If no guards are confirmed, we should pick a few reachable guards and
+   * call them all primary. But not confirmed.*/
+  entry_guards_update_primary(gs);
+  int n_primary = smartlist_len(gs->primary_entry_guards);
+  tt_int_op(n_primary, OP_GE, 1);
+  SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, {
+    tt_assert(g->is_primary);
+    tt_assert(g->confirmed_idx == -1);
+  });
+
+  /* Calling it a second time should leave the guards unchanged. */
+  smartlist_add_all(prev_guards, gs->primary_entry_guards);
+  entry_guards_update_primary(gs);
+  tt_int_op(smartlist_len(gs->primary_entry_guards), OP_EQ, n_primary);
+  SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, {
+    tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx));
+  });
+
+  /* If we have one confirmed guard, that guards becomes the first primary
+   * guard, and the other primary guards get kept. */
+
+  /* find a non-primary guard... */
+  entry_guard_t *confirmed = NULL;
+  SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, g, {
+    if (! g->is_primary) {
+      confirmed = g;
+      break;
+    }
+  });
+  tt_assert(confirmed);
+  /* make it confirmed. */
+  make_guard_confirmed(gs, confirmed);
+  /* update the list... */
+  smartlist_clear(prev_guards);
+  smartlist_add_all(prev_guards, gs->primary_entry_guards);
+  entry_guards_update_primary(gs);
+
+  /*  and see what's primary now! */
+  tt_int_op(smartlist_len(gs->primary_entry_guards), OP_EQ, n_primary);
+  tt_ptr_op(smartlist_get(gs->primary_entry_guards, 0), OP_EQ, confirmed);
+  SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, {
+    tt_assert(g->is_primary);
+    if (g_sl_idx == 0)
+      continue;
+    tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx - 1));
+  });
+  {
+    entry_guard_t *prev_last_guard = smartlist_get(prev_guards, n_primary-1);
+    tt_assert(! prev_last_guard->is_primary);
+  }
+
+  /* Calling it a fourth time should leave the guards unchanged. */
+  smartlist_clear(prev_guards);
+  smartlist_add_all(prev_guards, gs->primary_entry_guards);
+  entry_guards_update_primary(gs);
+  tt_int_op(smartlist_len(gs->primary_entry_guards), OP_EQ, n_primary);
+  SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, {
+    tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx));
+  });
+
+ done:
+  guard_selection_free(gs);
+  smartlist_free(prev_guards);
+}
+
+static void
+test_entry_guard_select_for_circuit_no_confirmed(void *arg)
+{
+  /* Simpler cases: no gaurds are confirmed yet. */
+  (void)arg;
+  guard_selection_t *gs = guard_selection_new();
+
+  /* simple starting configuration */
+  entry_guards_update_primary(gs);
+  unsigned state = 9999;
+
+  entry_guard_t *g = select_entry_guard_for_circuit(gs, &state);
+
+  tt_assert(g);
+  tt_assert(g->is_primary);
+  tt_int_op(g->confirmed_idx, OP_EQ, -1);
+  tt_assert(g->is_pending == 0); // primary implies non-pending.
+  tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_ON_COMPLETION);
+  tt_i64_op(g->last_tried_to_connect, OP_EQ, approx_time());
+
+  // If we do that again, we should get the same guard.
+  entry_guard_t *g2 = select_entry_guard_for_circuit(gs, &state);
+  tt_ptr_op(g2, OP_EQ, g);
+
+  // if we mark that guard down, we should get a different primary guard.
+  // auto-retry it.
+  g->is_reachable = GUARD_REACHABLE_NO;
+  g->unreachable_since = approx_time() - 10;
+  g->last_tried_to_connect = approx_time() - 10;
+  state = 9999;
+  g2 = select_entry_guard_for_circuit(gs, &state);
+  tt_ptr_op(g2, OP_NE, g);
+  tt_assert(g2);
+  tt_assert(g2->is_primary);
+  tt_int_op(g2->confirmed_idx, OP_EQ, -1);
+  tt_assert(g2->is_pending == 0); // primary implies non-pending.
+  tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_ON_COMPLETION);
+  tt_i64_op(g2->last_tried_to_connect, OP_EQ, approx_time());
+
+  // If we say that the first primary guard was last tried a long time ago, we
+  // should get an automatic retry on it.
+  g->unreachable_since = approx_time() - 72*60*60;
+  g->last_tried_to_connect = approx_time() - 72*60*60;
+  state = 9999;
+  g2 = select_entry_guard_for_circuit(gs, &state);
+  tt_ptr_op(g2, OP_EQ, g);
+  tt_assert(g2);
+  tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_ON_COMPLETION);
+  tt_i64_op(g2->last_tried_to_connect, OP_EQ, approx_time());
+  tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE);
+
+  // And if we mark ALL the primary guards down, we should get another guard
+  // at random.
+  SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, guard, {
+    guard->is_reachable = GUARD_REACHABLE_NO;
+    guard->last_tried_to_connect = approx_time() - 5;
+    guard->unreachable_since = approx_time() - 30;
+  });
+  state = 9999;
+  g2 = select_entry_guard_for_circuit(gs, &state);
+  tt_assert(g2);
+  tt_assert(!g2->is_primary);
+  tt_int_op(g2->confirmed_idx, OP_EQ, -1);
+  tt_assert(g2->is_pending == 1);
+  tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD);
+  tt_i64_op(g2->last_tried_to_connect, OP_EQ, approx_time());
+  tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE);
+
+  // As a bonus, maybe we should be retrying the primary guards. Let's say so.
+  mark_primary_guards_maybe_reachable(gs);
+  SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, guard, {
+    tt_int_op(guard->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE);
+    tt_assert(guard->is_usable_filtered_guard == 1);
+    // no change to these fields.
+    tt_i64_op(guard->last_tried_to_connect, OP_EQ, approx_time() - 5);
+    tt_i64_op(guard->unreachable_since, OP_EQ, approx_time() - 30);
+  });
+
+ done:
+  guard_selection_free(gs);
+}
+
+static void
+test_entry_guard_select_for_circuit_confirmed(void *arg)
+{
+  /* Case 2: if all the primary guards are down, and there are more confirmed
+     guards, we use a confirmed guard. */
+  (void)arg;
+  int i;
+  guard_selection_t *gs = guard_selection_new();
+  const int N_CONFIRMED = 10;
+
+  /* slightly more complicated simple starting configuration */
+  entry_guards_update_primary(gs);
+  for (i = 0; i < N_CONFIRMED; ++i) {
+    entry_guard_t *guard = smartlist_get(gs->sampled_entry_guards, i);
+    make_guard_confirmed(gs, guard);
+  }
+  entry_guards_update_primary(gs); // rebuild the primary list.
+
+  unsigned state = 9999;
+
+  // As above, this gives us a primary guard.
+  entry_guard_t *g = select_entry_guard_for_circuit(gs, &state);
+  tt_assert(g);
+  tt_assert(g->is_primary);
+  tt_int_op(g->confirmed_idx, OP_EQ, 0);
+  tt_assert(g->is_pending == 0); // primary implies non-pending.
+  tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_ON_COMPLETION);
+  tt_i64_op(g->last_tried_to_connect, OP_EQ, approx_time());
+  tt_ptr_op(g, OP_EQ, smartlist_get(gs->primary_entry_guards, 0));
+
+  // But if we mark all the primary guards down...
+  SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, guard, {
+    guard->last_tried_to_connect = approx_time();
+    entry_guards_note_guard_failure(gs, guard);
+  });
+
+  // ... we should get a confirmed guard.
+  state = 9999;
+  g = select_entry_guard_for_circuit(gs, &state);
+  tt_assert(g);
+  tt_assert(! g->is_primary);
+  tt_int_op(g->confirmed_idx, OP_EQ, smartlist_len(gs->primary_entry_guards));
+  tt_assert(g->is_pending);
+  tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD);
+  tt_i64_op(g->last_tried_to_connect, OP_EQ, approx_time());
+
+  // And if we try again, we should get a different confirmed guard, since
+  // that one is pending.
+  state = 9999;
+  entry_guard_t *g2 = select_entry_guard_for_circuit(gs, &state);
+  tt_assert(g2);
+  tt_assert(! g2->is_primary);
+  tt_ptr_op(g2, OP_NE, g);
+  tt_int_op(g2->confirmed_idx, OP_EQ,
+            smartlist_len(gs->primary_entry_guards)+1);
+  tt_assert(g2->is_pending);
+  tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD);
+  tt_i64_op(g2->last_tried_to_connect, OP_EQ, approx_time());
+
+  // If we make every confirmed guard become pending then we start poking
+  // other guards.
+  const int n_remaining_confirmed =
+    N_CONFIRMED - 2 - smartlist_len(gs->primary_entry_guards);
+  for (i = 0; i < n_remaining_confirmed; ++i) {
+    g = select_entry_guard_for_circuit(gs, &state);
+    tt_int_op(g->confirmed_idx, OP_GE, 0);
+    tt_assert(g);
+  }
+  state = 9999;
+  g = select_entry_guard_for_circuit(gs, &state);
+  tt_assert(g);
+  tt_assert(g->is_pending);
+  tt_int_op(g->confirmed_idx, OP_EQ, -1);
+
+ done:
+  guard_selection_free(gs);
+}
+
 static const struct testcase_setup_t fake_network = {
   fake_network_setup, fake_network_cleanup
 };
 
+static const struct testcase_setup_t big_fake_network = {
+  big_fake_network_setup, big_fake_network_cleanup
+};
+
+#define BFN_TEST(name) \
+  { #name, test_entry_guard_ ## name, TT_FORK, &big_fake_network, NULL }
+
 struct testcase_t entrynodes_tests[] = {
   { "entry_is_time_to_retry", test_entry_is_time_to_retry,
     TT_FORK, NULL, NULL },
@@ -1136,6 +2215,20 @@ struct testcase_t entrynodes_tests[] = {
     test_entry_guard_parse_from_state_failure, 0, NULL, NULL },
   { "parse_from_state_partial_failure",
     test_entry_guard_parse_from_state_partial_failure, 0, NULL, NULL },
+  BFN_TEST(add_single_guard),
+  BFN_TEST(node_filter),
+  BFN_TEST(expand_sample),
+  BFN_TEST(expand_sample_small_net),
+  BFN_TEST(update_from_consensus_status),
+  BFN_TEST(update_from_consensus_repair),
+  BFN_TEST(update_from_consensus_remove),
+  BFN_TEST(confirming_guards),
+  BFN_TEST(sample_reachable_filtered),
+  BFN_TEST(sample_reachable_filtered_empty),
+  BFN_TEST(retry_unreachable),
+  BFN_TEST(manage_primary),
+  BFN_TEST(select_for_circuit_no_confirmed),
+  BFN_TEST(select_for_circuit_confirmed),
   END_OF_TESTCASES
 };

    

nickm＠torproject.org

tags

participants (1)