[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [tor/master] Implement most of the prop271 data structure backends.
commit 7bf946965bad88116582dfd3d20e5837eeddd758
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
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
};
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits