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

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

Implement most of the prop271 data structure backends.

This code handles: * Maintaining the sampled set, the filtered set, and the usable_filtered set. * Maintaining the confirmed and primary guard lists. * Picking guards for circuits, and updating guard state when circuit state changes.

Additionally, I've done code structure movement: even more constants and structures from entrynodes.c have become ENTRYNODES_PRIVATE fields of entrynodes.h.

I've also included a bunch of documentation and a bunch of unit tests. Coverage on the new code is pretty high.

I've noted important things to resolve before this branch is done with the /XXXX.*prop271/ regex. --- src/or/entrynodes.c | 1256 +++++++++++++++++++++++++++++++++++++++----- src/or/entrynodes.h | 272 +++++++++- src/test/test_entrynodes.c | 1093 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 2488 insertions(+), 133 deletions(-)

diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c index c6ed59d..958aba4 100644 --- a/src/or/entrynodes.c +++ b/src/or/entrynodes.c @@ -10,7 +10,113 @@ * * Entry nodes can be guards (for general use) or bridges (for censorship * circumvention). + * + * XXXX prop271 This module is in flux, since I'm currently in the middle of + * implementation proposal 271. The module documentation here will describe + * the new algorithm and data structures; the old ones should get removed as + * proposal 271 is completed. + * + * In general, we use entry guards to prevent traffic-sampling attacks: + * if we chose every circuit independently, an adversary controlling + * some fraction of paths on the network would observe a sample of every + * user's traffic. Using guards gives users a chance of not being + * profiled. + * + * The current entry guard selection code is designed to try to avoid + * _ever_ trying every guard on the network, to try to stick to guards + * that we've used before, to handle hostile/broken networks, and + * to behave sanely when the network goes up and down. + * + * Our algorithm works as follows: First, we maintain a SAMPLE of guards + * we've seen in the networkstatus consensus. We maintain this sample + * over time, and store it persistently; it is chosen without reference + * to our configuration or firewall rules. Guards remain in the sample + * as they enter and leave the consensus. We expand this sample as + * needed, up to a maximum size. + * + * As a subset of the sample, we maintain a FILTERED SET of the guards + * that we would be willing to use if we could connect to them. The + * filter removes all the guards that we're excluding because they're + * bridges (or not bridges), because we have restrictive firewall rules, + * because of ExcludeNodes, because we of path bias restrictions, + * because they're absent from the network at present, and so on. + * + * As a subset of the filtered set, we keep a REACHABLE FILTERED SET + * (also called a "usable filtered set") of those guards that we call + * "reachable" or "maybe reachable". A guard is reachable if we've + * connected to it more recently than we've failed. A guard is "maybe + * reachable" if we have never tried to connect to it, or if we + * failed to connect to it so long ago that we no longer think our + * failure means it's down. + * + * As a persistent ordered list whose elements are taken from the + * sampled set, we track a CONFIRMED GUARDS LIST. A guard becomes + * confirmed when we successfully build a circuit through it, and decide + * to use that circuit. We order the guards on this list by the order + * in which they became confirmed. + * + * And as a final group, we have an ordered list of PRIMARY GUARDS, + * whose elements are taken from the filtered set. We prefer + * confirmed guards to non-confirmed guards for this list, and place + * other restrictions on it. The primary guards are the ones that we + * connect to "when nothing is wrong" -- circuits through them can be used + * immediately. + * + * To build circuits, we take a primary guard if possible -- or a + * reachable filtered confirmed guard if no primary guard is possible -- + * or a random reachable filtered guard otherwise. If the guard is + * primary, we can use the circuit immediately on success. Otherwise, + * the guard is now "pending" -- we won't use its circuit unless all + * of the circuits we're trying to build through better guards have + * definitely failed. + * + * While we're building circuits, we track a little "guard state" for + * each circuit. We use this to keep track of whether the circuit is + * one that we can use as soon as its done, or whether it's one that + * we should keep around to see if we can do better. In the latter case, + * a periodic call to entry_guards_upgrade_waiting_circuits() will + * eventually upgrade it. **/ +/* DOCDOC -- expand this. + * + * XXXX prop271 -- make sure we check all of these properties everywhere we + * should. + * + * Information invariants: + * + * [x] whenever a guard becomes unreachable, clear its usable_filtered flag. + * + * [x] Whenever a guard becomes reachable or maybe-reachable, if its filtered + * flag is set, set its usable_filtered flag. + * + * [ ] Whenever we get a new consensus, call update_from_consensus(). (LATER.) + * + * [ ] Whenever the configuration changes in a relevant way, update the + * filtered/usable flags. (LATER.) + * + * [x] Whenever we add a guard to the sample, make sure its filtered/usable + * flags are set as possible. + * + * [x] Whenever we remove a guard from the sample, remove it from the primary + * and confirmed lists. + * + * [ ] When we make a guard confirmed, update the primary list. + * + * [ ] When we make a guard filtered or unfiltered, update the primary list. + * + * [ ] When we are about to pick a guard, make sure that the primary list is + * full. + * + * [x] Before calling sample_reachable_filtered_entry_guards(), make sure + * that the filtered, primary, and confirmed flags are up-to-date. + * + * [x] Call entry_guard_consider_retry every time we are about to check + * is_usable_filtered or is_reachable, and every time we set + * is_filtered to 1. + * + * [x] Call entry_guards_changed_for_guard_selection() whenever we update + * a persistent field. + */

#define ENTRYNODES_PRIVATE

@@ -38,39 +144,6 @@ #include "transports.h" #include "statefile.h"

-/** All the context for guard selection on a particular client */ - -struct guard_selection_s { - /** - * A value of 1 means that guard_selection_t structures have changed - * and those changes need to be flushed to disk. - * - * XXX we don't know how to flush multiple guard contexts to disk yet; - * fix that as soon as any way to change the default exists, or at least - * make sure this gets set on change. - */ - int dirty; - - /** - * A list of the sampled entry guards, as entry_guard_t structures. - * Not in any particular order. */ - smartlist_t *sampled_entry_guards; - - /** - * A list of our chosen entry guards, as entry_guard_t structures; this - * preserves the pre-Prop271 behavior. - */ - smartlist_t *chosen_entry_guards; - - /** - * When we try to choose an entry guard, should we parse and add - * config's EntryNodes first? This was formerly a global. - */ - int should_add_entry_nodes; - - int filtered_up_to_date; -}; - static smartlist_t *guard_contexts = NULL; static guard_selection_t *curr_guard_context = NULL;

@@ -79,54 +152,9 @@ static const node_t *choose_random_entry_impl(guard_selection_t *gs, int for_directory, dirinfo_type_t dirtype, int *n_options_out); -static guard_selection_t * guard_selection_new(void); - -/** - * @name Constants for old (pre-prop271) guard selection algorithm. - */ - -/**@{*/ - -/* Default number of entry guards in the case where the NumEntryGuards - * consensus parameter is not set */ -#define DEFAULT_N_GUARDS 1 -/* Minimum and maximum number of entry guards (in case the NumEntryGuards - * consensus parameter is set). */ -#define MIN_N_GUARDS 1 -#define MAX_N_GUARDS 10 -/** Largest amount that we'll backdate chosen_on_date */ -#define CHOSEN_ON_DATE_SLOP (30*86400) -/** How long (in seconds) do we allow an entry guard to be nonfunctional, - * unlisted, excluded, or otherwise nonusable before we give up on it? */ -#define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60) -/**}@*/ - -/** - * @name Networkstatus parameters for old (pre-prop271) guard selection - */ -/**@}*/ -/** Choose how many entry guards or directory guards we'll use. If - * <b>for_directory</b> is true, we return how many directory guards to - * use; else we return how many entry guards to use. */ -STATIC int -decide_num_guards(const or_options_t *options, int for_directory) -{ - if (for_directory) { - int answer; - if (options->NumDirectoryGuards != 0) - return options->NumDirectoryGuards; - answer = networkstatus_get_param(NULL, "NumDirectoryGuards", 0, 0, 10); - if (answer) /* non-zero means use the consensus value */ - return answer; - } - - if (options->NumEntryGuards) - return options->NumEntryGuards; - - /* Use the value from the consensus, or 3 if no guidance. */ - return networkstatus_get_param(NULL, "NumEntryGuards", DEFAULT_N_GUARDS, - MIN_N_GUARDS, MAX_N_GUARDS); -} +static void entry_guard_set_filtered_flags(const or_options_t *options, + guard_selection_t *gs, + entry_guard_t *guard);

/** Return 0 if we should apply guardfraction information found in the * consensus. A specific consensus can be specified with the @@ -149,31 +177,10 @@ should_apply_guardfraction(const networkstatus_t *ns)

return options->UseGuardFraction; } -/**@}*/ - -/** - * @name Parameters for new (prop271) entry guard algorithm. - */ -/* XXXX prop271 some of these should be networkstatus parameters */ -#define MIN_SAMPLE_THRESHOLD 15 -#define MAX_SAMPLE_THRESHOLD 50 -#define GUARD_LIFETIME_DAYS 120 -#define REMOVE_UNLISTED_GUARDS_AFTER_DAYS 20 -#define MIN_FILTERED_SAMPLE_SIZE 20 -#define N_PRIMARY_GUARDS 3 -#define PRIMARY_GUARDS_RETRY_SCHEDULE /* XXX prop271 */ -#define OTHER_GUARDS_RETRY_SCHEDULE /* XXX prop271 */ -#define INTERNET_LIKELY_DOWN_INTERVAL (10*60) -#define NONPRIMARY_GUARD_CONNECT_TIMEOUT 15 -#define NONPRIMARY_GUARD_IDLE_TIMEOUT (10*60) -#define MEANINGFUL_RESTRICTION_FRAC 0.2 -#define EXTREME_RESTRICTION_FRAC 0.01 -#define GUARD_CONFIRMED_MIN_LIFETIME_DAYS 60 -/**}@*/

-/** Allocate a new guard_selection_t */ +/** Allocate and return a new guard_selection_t */

-static guard_selection_t * +STATIC guard_selection_t * guard_selection_new(void) { guard_selection_t *gs; @@ -181,6 +188,8 @@ guard_selection_new(void) gs = tor_malloc_zero(sizeof(*gs)); gs->chosen_entry_guards = smartlist_new(); gs->sampled_entry_guards = smartlist_new(); + gs->confirmed_entry_guards = smartlist_new(); + gs->primary_entry_guards = smartlist_new();

return gs; } @@ -255,9 +264,11 @@ entry_guard_get_pathbias_state(entry_guard_t *guard) }

/** Return an interval betweeen 'now' and 'max_backdate' seconds in the past, - * chosen uniformly at random. */ -STATIC time_t -randomize_time(time_t now, time_t max_backdate) + * chosen uniformly at random. We use this before recording persistent + * dates, so that we aren't leaking exactly when we recorded it. + */ +MOCK_IMPL(STATIC time_t, +randomize_time,(time_t now, time_t max_backdate)) { tor_assert(max_backdate > 0);

@@ -272,25 +283,71 @@ randomize_time(time_t now, time_t max_backdate) }

/** - * DOCDOC + * Return true iff <b>node</b> has all the flags needed for us to consider it + * a possible guard when sampling guards. + */ +static int +node_is_possible_guard(guard_selection_t *gs, const node_t *node) +{ + /* The "GUARDS" set is all nodes in the nodelist for which this predicate + * holds. */ + + /* XXXX -- prop271 spec deviation. We require node_is_dir() here. */ + (void)gs; + tor_assert(node); + return (node->is_possible_guard && + node->is_stable && + node->is_fast && + node->is_valid && + node_is_dir(node)); +} + +/** + * Return the sampled guard with the RSA identity digest <b>rsa_id</b>, or + * NULL if we don't have one. */ +STATIC entry_guard_t * +get_sampled_guard_with_id(guard_selection_t *gs, + const uint8_t *rsa_id) +{ + tor_assert(gs); + tor_assert(rsa_id); + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + if (tor_memeq(guard->identity, rsa_id, DIGEST_LEN)) + return guard; + } SMARTLIST_FOREACH_END(guard); + return NULL; +} + +/** + * Return true iff we have a sampled guard with the RSA identity digest + * <b>rsa_id</b>. */ +static inline int +have_sampled_guard_with_id(guard_selection_t *gs, const uint8_t *rsa_id) +{ + return get_sampled_guard_with_id(gs, rsa_id) != NULL; +} + +/** + * Allocate a new entry_guard_t object for <b>node</b>, add it to the + * sampled entry guards in <b>gs</b>, and return it. <b>node</b> must + * not currently be a sampled guard in <b>gs</b>. */ -ATTR_UNUSED STATIC void +STATIC entry_guard_t * entry_guard_add_to_sample(guard_selection_t *gs, - node_t *node) + const node_t *node) { const int GUARD_LIFETIME = GUARD_LIFETIME_DAYS * 86400; tor_assert(gs); tor_assert(node);

+ log_info(LD_GUARD, "Adding %s as to the entry guard sample set.", + node_describe(node)); + // XXXX prop271 take ed25519 identity here too.

/* make sure that the guard is not already sampled. */ - SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, - entry_guard_t *, sampled) { - if (BUG(tor_memeq(node->identity, sampled->identity, DIGEST_LEN))) { - return; - } - } SMARTLIST_FOREACH_END(sampled); + if (BUG(have_sampled_guard_with_id(gs, (uint8_t*)node->identity))) + return NULL; // LCOV_EXCL_LINE

entry_guard_t *guard = tor_malloc_zero(sizeof(entry_guard_t));

@@ -300,22 +357,902 @@ entry_guard_add_to_sample(guard_selection_t *gs, guard->sampled_on_date = randomize_time(approx_time(), GUARD_LIFETIME/10); tor_free(guard->sampled_by_version); guard->sampled_by_version = tor_strdup(VERSION); + guard->currently_listed = 1; guard->confirmed_idx = -1;

/* non-persistent fields */ guard->is_reachable = GUARD_REACHABLE_MAYBE;

smartlist_add(gs->sampled_entry_guards, guard); - gs->filtered_up_to_date = 0; + entry_guard_set_filtered_flags(get_options(), gs, guard); + entry_guards_changed_for_guard_selection(gs); + return guard; +} + +/** + * Return the number of sampled guards in <b>gs</b> that are "filtered" + * (that is, we're willing to connect to them) and that are "usable" + * (that is, either "reachable" or "maybe reachable"). */ +STATIC int +num_reachable_filtered_guards(guard_selection_t *gs) +{ + int n_reachable_filtered_guards = 0; + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + entry_guard_consider_retry(guard); + if (guard->is_usable_filtered_guard) + ++n_reachable_filtered_guards; + } SMARTLIST_FOREACH_END(guard); + return n_reachable_filtered_guards; +} + +/** + * Add new guards to the sampled guards in <b>gs</b> until there are + * enough usable filtered guards, but never grow the sample beyond its + * maximum size. Return the last guard added, or NULL if none were + * added. + */ +STATIC entry_guard_t * +entry_guards_expand_sample(guard_selection_t *gs) +{ + tor_assert(gs); + int n_sampled = smartlist_len(gs->sampled_entry_guards); + entry_guard_t *added_guard = NULL; + + smartlist_t *nodes = nodelist_get_list(); + /* Construct eligible_guards as GUARDS - SAMPLED_GUARDS */ + smartlist_t *eligible_guards = smartlist_new(); + int n_guards = 0; // total size of "GUARDS" + int n_usable_filtered_guards = num_reachable_filtered_guards(gs); + { + /* Build a bloom filter of our current guards: let's keep this O(N). */ + digestset_t *sampled_guard_ids = digestset_new(n_sampled); + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, const entry_guard_t *, + guard) { + digestset_add(sampled_guard_ids, guard->identity); + } SMARTLIST_FOREACH_END(guard); + + SMARTLIST_FOREACH_BEGIN(nodes, node_t *, node) { + if (! node_is_possible_guard(gs, node)) + continue; + ++n_guards; + if (digestset_contains(sampled_guard_ids, node->identity)) + continue; + smartlist_add(eligible_guards, node); + } SMARTLIST_FOREACH_END(node); + + /* Now we can free that bloom filter. */ + digestset_free(sampled_guard_ids); + } + + /* Is there at least one guard we haven't sampled? */ + if (! smartlist_len(eligible_guards)) + goto done; + + const int max_sample = (int)(n_guards * MAX_SAMPLE_THRESHOLD); + const int min_filtered_sample = MIN_FILTERED_SAMPLE_SIZE; + + log_info(LD_GUARD, "Expanding the sample guard set. We have %d guards " + "in the sample, and %d eligible guards to extend it with.", + n_sampled, smartlist_len(eligible_guards)); + + while (n_usable_filtered_guards < min_filtered_sample) { + /* Has our sample grown too large to expand? */ + if (n_sampled >= max_sample) { + log_info(LD_GUARD, "Not expanding the guard sample any further; " + "just hit the maximum sample threshold of %d", + max_sample); + goto done; + } + + /* Did we run out of guards? */ + if (smartlist_len(eligible_guards) == 0) { + /* LCOV_EXCL_START + As long as MAX_SAMPLE_THRESHOLD makes can't be adjusted to + allow all guards to be sampled, this can't be reached. + */ + log_info(LD_GUARD, "Not expanding the guard sample any further; " + "just ran out of eligible guards"); + goto done; + /* LCOV_EXCL_STOP */ + } + + /* Otherwise we can add at least one new guard. */ + const node_t *node = + node_sl_choose_by_bandwidth(eligible_guards, WEIGHT_FOR_GUARD); + if (BUG(! node)) + goto done; // LCOV_EXCL_LINE -- should be impossible. + + added_guard = entry_guard_add_to_sample(gs, node); + if (!added_guard) + goto done; // LCOV_EXCL_LINE -- only fails on BUG. + + ++n_sampled; + + if (added_guard->is_usable_filtered_guard) + ++n_usable_filtered_guards; + + smartlist_remove(eligible_guards, node); + } + + done: + smartlist_free(eligible_guards); + return added_guard; +} + +/** + * Helper: <b>guard</b> has just been removed from the sampled guards: + * also remove it from primary and confirmed. */ +static void +remove_guard_from_confirmed_and_primary_lists(guard_selection_t *gs, + entry_guard_t *guard) +{ + if (guard->is_primary) { + guard->is_primary = 0; + smartlist_remove_keeporder(gs->primary_entry_guards, guard); + } else { + if (BUG(smartlist_contains(gs->primary_entry_guards, guard))) { + smartlist_remove_keeporder(gs->primary_entry_guards, guard); + } + } + + if (guard->confirmed_idx >= 0) { + entry_guard_t *found_guard = NULL; + if (guard->confirmed_idx < smartlist_len(gs->confirmed_entry_guards)) + found_guard = smartlist_get(gs->confirmed_entry_guards, + guard->confirmed_idx); + if (BUG(guard != found_guard)) { + smartlist_remove_keeporder(gs->confirmed_entry_guards, guard); + } else { + smartlist_del_keeporder(gs->confirmed_entry_guards, + guard->confirmed_idx); + } + guard->confirmed_idx = -1; + guard->confirmed_on_date = 0; + } else { + if (BUG(smartlist_contains(gs->confirmed_entry_guards, guard))) { + smartlist_remove_keeporder(gs->confirmed_entry_guards, guard); + } + } +} + +/** + * Update the status of all sampled guards based on the arrival of a + * new consensus networkstatus document. This will include marking + * some guards as listed or unlisted, and removing expired guards. */ +STATIC void +sampled_guards_update_from_consensus(guard_selection_t *gs) +{ + tor_assert(gs); + const int REMOVE_UNLISTED_GUARDS_AFTER = + (REMOVE_UNLISTED_GUARDS_AFTER_DAYS * 86400); + const int unlisted_since_slop = REMOVE_UNLISTED_GUARDS_AFTER / 5; + + // It's important to use only a live consensus here; we don't want to + // make changes based on anything expired or old. + networkstatus_t *ns = networkstatus_get_live_consensus(approx_time()); + + log_info(LD_GUARD, "Updating sampled guard status based on received " + "consensus."); + + if (! ns || ns->valid_until < approx_time()) { + log_info(LD_GUARD, "Hey, that consensus isn't still valid. Ignoring."); + return; + } + + int n_changes = 0; + + /* First: Update listed/unlisted. */ + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + /* XXXX prop271 handle bridges right? */ + /* XXXX prop271 check ed ID too */ + const node_t *node = node_get_by_id(guard->identity); + + const unsigned is_listed = node && node_is_possible_guard(gs, node); + + if (is_listed && ! guard->currently_listed) { + ++n_changes; + guard->currently_listed = 1; + guard->unlisted_since_date = 0; + log_info(LD_GUARD, "Sampled guard %s is now listed again.", + entry_guard_describe(guard)); + } else if (!is_listed && guard->currently_listed) { + ++n_changes; + guard->currently_listed = 0; + guard->unlisted_since_date = randomize_time(approx_time(), + unlisted_since_slop); + log_info(LD_GUARD, "Sampled guard %s is now unlisted.", + entry_guard_describe(guard)); + } else if (is_listed && guard->currently_listed) { + log_debug(LD_GUARD, "Sampled guard %s is still listed.", + entry_guard_describe(guard)); + } else { + tor_assert(! is_listed && ! guard->currently_listed); + log_debug(LD_GUARD, "Sampled guard %s is still unlisted.", + entry_guard_describe(guard)); + } + + /* Clean up unlisted_since_date, just in case. */ + if (guard->currently_listed && guard->unlisted_since_date) { + ++n_changes; + guard->unlisted_since_date = 0; + log_warn(LD_BUG, "Sampled guard %s was listed, but with " + "unlisted_since_date set. Fixing.", + entry_guard_describe(guard)); + } else if (!guard->currently_listed && ! guard->unlisted_since_date) { + ++n_changes; + guard->unlisted_since_date = randomize_time(approx_time(), + unlisted_since_slop); + log_warn(LD_BUG, "Sampled guard %s was unlisted, but with " + "unlisted_since_date unset. Fixing.", + entry_guard_describe(guard)); + } + } SMARTLIST_FOREACH_END(guard); + + const time_t remove_if_unlisted_since = + approx_time() - REMOVE_UNLISTED_GUARDS_AFTER; + const time_t maybe_remove_if_sampled_before = + approx_time() - (GUARD_LIFETIME_DAYS * 86400); + const time_t remove_if_confirmed_before = + approx_time() - (GUARD_CONFIRMED_MIN_LIFETIME_DAYS * 86400); + + /* Then: remove the ones that have been junk for too long */ + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + /* XXXX prop271 handle bridges right? */ + + int remove = 0; + + if (guard->currently_listed == 0 && + guard->unlisted_since_date < remove_if_unlisted_since) { + /* + "We have a live consensus, and {IS_LISTED} is false, and + {FIRST_UNLISTED_AT} is over {REMOVE_UNLISTED_GUARDS_AFTER} + days in the past." + */ + log_info(LD_GUARD, "Removing sampled guard %s: it has been unlisted " + "for over %d days", entry_guard_describe(guard), + REMOVE_UNLISTED_GUARDS_AFTER_DAYS); + remove = 1; + } else if (guard->sampled_on_date < maybe_remove_if_sampled_before) { + /* We have a live consensus, and {ADDED_ON_DATE} is over + {GUARD_LIFETIME} ago, *and* {CONFIRMED_ON_DATE} is either + "never", or over {GUARD_CONFIRMED_MIN_LIFETIME} ago. + */ + if (guard->confirmed_on_date == 0) { + remove = 1; + log_info(LD_GUARD, "Removing sampled guard %s: it was sampled " + "over %d days ago, but never confirmed.", + entry_guard_describe(guard), + GUARD_LIFETIME_DAYS); + } else if (guard->confirmed_on_date < remove_if_confirmed_before) { + remove = 1; + log_info(LD_GUARD, "Removing sampled guard %s: it was sampled " + "over %d days ago, and confirmed over %d days ago.", + entry_guard_describe(guard), + GUARD_LIFETIME_DAYS, GUARD_CONFIRMED_MIN_LIFETIME_DAYS); + } + } + + if (remove) { + ++n_changes; + SMARTLIST_DEL_CURRENT(gs->sampled_entry_guards, guard); + remove_guard_from_confirmed_and_primary_lists(gs, guard); + entry_guard_free(guard); + } + } SMARTLIST_FOREACH_END(guard); + + if (n_changes) { + /* Regnerate other things. XXXXXX prop271 */ + // XXXX prop271 rebuild confirmed list. + entry_guards_update_filtered_sets(gs); + entry_guards_changed_for_guard_selection(gs); + } +} + +/** + * Return true iff <b>node</b> is a Tor relay that we are configured to + * be able to connect to. */ +static int +node_passes_guard_filter(const or_options_t *options, guard_selection_t *gs, + const node_t *node) +{ + (void)gs; + if (routerset_contains_node(options->ExcludeNodes, node)) + return 0; + + /* XXXX -- prop271 spec deviation -- add entrynodes to spec. */ + if (options->EntryNodes && + !options->UseBridges && + !routerset_contains_node(options->EntryNodes, node)) + return 0; + + if (!fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION, 0)) + return 0; + + if (bool_neq(options->UseBridges, node_is_a_configured_bridge(node))) + return 0; + + return 1; +} + +/** + * Return true iff <b>guard</b> is a Tor relay that we are configured to + * be able to connect to, and we haven't disabled it for omission from + * the consensus or path bias issues. */ +static int +entry_guard_passes_filter(const or_options_t *options, guard_selection_t *gs, + entry_guard_t *guard) +{ + if (guard->currently_listed == 0) + return 0; + if (guard->pb.path_bias_disabled) + return 0; + + const node_t *node = node_get_by_id(guard->identity); + if (BUG(node == NULL)) { + // should be impossible, since currently_listed was true. + return 0; + } + + return node_passes_guard_filter(options, gs, node); +} + +/** + * Update the <b>is_filtered_guard</b> and <b>is_usable_filtered_guard</b> + * flags on <b>guard</b>. */ +void +entry_guard_set_filtered_flags(const or_options_t *options, + guard_selection_t *gs, + entry_guard_t *guard) +{ + guard->is_filtered_guard = 0; + guard->is_usable_filtered_guard = 0; + + if (entry_guard_passes_filter(options, gs, guard)) { + guard->is_filtered_guard = 1; + + if (guard->is_reachable != GUARD_REACHABLE_NO) + guard->is_usable_filtered_guard = 1; + + entry_guard_consider_retry(guard); + } + log_debug(LD_GUARD, "Updated sampled guard %s: filtered=%d; " + "reachable_filtered=%d.", entry_guard_describe(guard), + guard->is_filtered_guard, guard->is_usable_filtered_guard); +} + +/** + * Update the <b>is_filtered_guard</b> and <b>is_usable_filtered_guard</b> + * flag on every guard in <b>gs</b>. */ +STATIC void +entry_guards_update_filtered_sets(guard_selection_t *gs) +{ + const or_options_t *options = get_options(); + + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + entry_guard_set_filtered_flags(options, gs, guard); + } SMARTLIST_FOREACH_END(guard); +} + +/** + * Return a random guard from the reachable filtered sample guards + * in <b>gs</b>, subject to the exclusion rules listed in <b>flags</b>. + * Return NULL if no such guard can be found. + * + * Make sure that the sample is big enough, and that all the filter flags + * are set correctly, before calling this function. + **/ +STATIC entry_guard_t * +sample_reachable_filtered_entry_guards(guard_selection_t *gs, + unsigned flags) +{ + tor_assert(gs); + entry_guard_t *result = NULL; + const unsigned exclude_confirmed = flags & SAMPLE_EXCLUDE_CONFIRMED; + const unsigned exclude_primary = flags & SAMPLE_EXCLUDE_PRIMARY; + const unsigned exclude_pending = flags & SAMPLE_EXCLUDE_PENDING; + + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + entry_guard_consider_retry(guard); + } SMARTLIST_FOREACH_END(guard); + + const int n_reachable_filtered = num_reachable_filtered_guards(gs); + + log_info(LD_GUARD, "Trying to sample a reachable guard: We know of %d " + "in the USABLE_FILTERED set.", n_reachable_filtered); + + if (n_reachable_filtered < MIN_FILTERED_SAMPLE_SIZE) { + log_info(LD_GUARD, " (That isn't enough. Trying to expand the sample.)"); + entry_guards_expand_sample(gs); + } + + /* Build the set of reachable filtered guards. */ + smartlist_t *reachable_filtered_sample = smartlist_new(); + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + entry_guard_consider_retry(guard);// redundant, but cheap. + if (! guard->is_usable_filtered_guard) + continue; + if (exclude_confirmed && guard->confirmed_idx >= 0) + continue; + if (exclude_primary && guard->is_primary) + continue; + if (exclude_pending && guard->is_pending) + continue; + smartlist_add(reachable_filtered_sample, guard); + } SMARTLIST_FOREACH_END(guard); + + log_info(LD_GUARD, " (After filters [%x], we have %d guards to consider.)", + flags, smartlist_len(reachable_filtered_sample)); + + if (smartlist_len(reachable_filtered_sample)) { + result = smartlist_choose(reachable_filtered_sample); + log_info(LD_GUARD, " (Selected %s.)", + result ? entry_guard_describe(result) : "<null>"); + } + smartlist_free(reachable_filtered_sample); + + return result; +} + +/** + * Helper: compare two entry_guard_t by their confirmed_idx values. + * Used to sort the confirmed list. + */ +static int +compare_guards_by_confirmed_idx(const void **a_, const void **b_) +{ + const entry_guard_t *a = *a_, *b = *b_; + if (a->confirmed_idx < b->confirmed_idx) + return -1; + else if (a->confirmed_idx > b->confirmed_idx) + return 1; + else + return 0; +} + +/** + * Find the confirmed guards from among the sampled guards in <b>gs</b>, + * and put them in confirmed_entry_guards in the correct + * order. Recalculate their indices. + */ +STATIC void +entry_guards_update_confirmed(guard_selection_t *gs) +{ + smartlist_clear(gs->confirmed_entry_guards); + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + if (guard->confirmed_idx >= 0) + smartlist_add(gs->confirmed_entry_guards, guard); + } SMARTLIST_FOREACH_END(guard); + + smartlist_sort(gs->confirmed_entry_guards, compare_guards_by_confirmed_idx); + + int any_changed = 0; + SMARTLIST_FOREACH_BEGIN(gs->confirmed_entry_guards, entry_guard_t *, guard) { + if (guard->confirmed_idx != guard_sl_idx) { + any_changed = 1; + guard->confirmed_idx = guard_sl_idx; + } + } SMARTLIST_FOREACH_END(guard); + + gs->next_confirmed_idx = smartlist_len(gs->confirmed_entry_guards); + + if (any_changed) { + entry_guards_changed_for_guard_selection(gs); + } +} + +/** + * Mark <b>guard</b> as a confirmed guard -- that is, one that we have + * connected to, and intend to use again. + */ +STATIC void +make_guard_confirmed(guard_selection_t *gs, entry_guard_t *guard) +{ + if (BUG(guard->confirmed_on_date && guard->confirmed_idx >= 0)) + return; + + if (BUG(smartlist_contains(gs->confirmed_entry_guards, guard))) + return; + + const int GUARD_LIFETIME = GUARD_LIFETIME_DAYS * 86400; + guard->confirmed_on_date = randomize_time(approx_time(), GUARD_LIFETIME/10); + + log_info(LD_GUARD, "Marking %s as a confirmed guard (index %d)", + entry_guard_describe(guard), + gs->next_confirmed_idx); + + guard->confirmed_idx = gs->next_confirmed_idx++; + smartlist_add(gs->confirmed_entry_guards, guard);

entry_guards_changed_for_guard_selection(gs); }

/** + * Recalculate the list of primary guards (the ones we'd prefer to use) from + * the filtered sample and the confirmed list. + * + * XXXXX prop271 are calling this enough ??? + */ +STATIC void +entry_guards_update_primary(guard_selection_t *gs) +{ + tor_assert(gs); + + smartlist_t *new_primary_guards = smartlist_new(); + smartlist_t *old_primary_guards = smartlist_new(); + smartlist_add_all(old_primary_guards, gs->primary_entry_guards); + + /* First, can we fill it up with confirmed guards? */ + SMARTLIST_FOREACH_BEGIN(gs->confirmed_entry_guards, entry_guard_t *, guard) { + if (smartlist_len(new_primary_guards) >= N_PRIMARY_GUARDS) + break; + if (! guard->is_filtered_guard) + continue; + guard->is_primary = 1; + smartlist_add(new_primary_guards, guard); + } SMARTLIST_FOREACH_END(guard); + + /* Can we keep any older primary guards? First remove all the ones + * that we already kept. */ + SMARTLIST_FOREACH_BEGIN(old_primary_guards, entry_guard_t *, guard) { + if (smartlist_contains(new_primary_guards, guard)) { + SMARTLIST_DEL_CURRENT_KEEPORDER(old_primary_guards, guard); + } + } SMARTLIST_FOREACH_END(guard); + + /* Now add any that are still good. */ + SMARTLIST_FOREACH_BEGIN(old_primary_guards, entry_guard_t *, guard) { + if (smartlist_len(new_primary_guards) >= N_PRIMARY_GUARDS) + break; + if (! guard->is_filtered_guard) + continue; + guard->is_primary = 1; + smartlist_add(new_primary_guards, guard); + SMARTLIST_DEL_CURRENT_KEEPORDER(old_primary_guards, guard); + } SMARTLIST_FOREACH_END(guard); + + /* Mark the remaining previous primary guards as non-primary */ + SMARTLIST_FOREACH_BEGIN(old_primary_guards, entry_guard_t *, guard) { + guard->is_primary = 0; + } SMARTLIST_FOREACH_END(guard); + + /* Finally, fill out the list with sampled guards. */ + while (smartlist_len(new_primary_guards) < N_PRIMARY_GUARDS) { + entry_guard_t *guard = sample_reachable_filtered_entry_guards(gs, + SAMPLE_EXCLUDE_CONFIRMED| + SAMPLE_EXCLUDE_PRIMARY); + if (!guard) + break; + guard->is_primary = 1; + smartlist_add(new_primary_guards, guard); + } + +#if 1 + /* Debugging. */ + SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, guard, { + tor_assert_nonfatal( + bool_eq(guard->is_primary, + smartlist_contains(new_primary_guards, guard))); + }); +#endif + + int any_change = 0; + if (smartlist_len(gs->primary_entry_guards) != + smartlist_len(new_primary_guards)) { + any_change = 1; + } else { + SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, g) { + if (g != smartlist_get(new_primary_guards, g_sl_idx)) { + any_change = 1; + } + } SMARTLIST_FOREACH_END(g); + } + + if (any_change) { + log_info(LD_GUARD, "Primary entry guards have changed. " + "New primary guard list is: "); + int n = smartlist_len(new_primary_guards); + SMARTLIST_FOREACH_BEGIN(new_primary_guards, entry_guard_t *, g) { + log_info(LD_GUARD, " %d/%d: %s%s%s", + g_sl_idx+1, n, entry_guard_describe(g), + g->confirmed_idx >= 0 ? " (confirmed)" : "", + g->is_filtered_guard ? "" : " (excluded by filter)"); + } SMARTLIST_FOREACH_END(g); + } + + smartlist_free(old_primary_guards); + smartlist_free(gs->primary_entry_guards); + gs->primary_entry_guards = new_primary_guards; +} + +/** + * Return the number of seconds after the last attempt at which we should + * retry a guard that has been failing since <b>failing_since</b>. + */ +static unsigned +get_retry_schedule(time_t failing_since, time_t now, + int is_primary) +{ + const unsigned SIX_HOURS = 6 * 3600; + const unsigned FOUR_DAYS = 4 * 86400; + const unsigned SEVEN_DAYS = 7 * 86400; + + time_t tdiff; + if (now > failing_since) { + tdiff = now - failing_since; + } else { + tdiff = 0; + } + + const struct { + time_t maximum; int primary_delay; int nonprimary_delay; + } delays[] = { + { SIX_HOURS, 30*60, 1*60*60 }, + { FOUR_DAYS, 2*60*60, 4*60*60 }, + { SEVEN_DAYS, 4*60*60, 18*60*60 }, + { TIME_MAX, 9*60*60, 36*60*60 } + }; + + unsigned i; + for (i = 0; i < ARRAY_LENGTH(delays); ++i) { + if (tdiff <= delays[i].maximum) { + return is_primary ? delays[i].primary_delay : delays[i].nonprimary_delay; + } + } + /* LCOV_EXCL_START -- can't reach, since delays ends with TIME_MAX. */ + tor_assert_nonfatal_unreached(); + return 36*60*60; + /* LCOV_EXCL_STOP */ +} + +/** + * If <b>guard</b> is unreachable, consider whether enough time has passed + * to consider it maybe-reachable again. + */ +STATIC void +entry_guard_consider_retry(entry_guard_t *guard) +{ + if (guard->is_reachable != GUARD_REACHABLE_NO) + return; /* No retry needed. */ + + const time_t now = approx_time(); + const unsigned delay = + get_retry_schedule(guard->failing_since, now, guard->is_primary); + const time_t last_attempt = guard->last_tried_to_connect; + + if (BUG(last_attempt == 0) || + now >= last_attempt + delay) { + /* We should mark this retriable. */ + char tbuf[ISO_TIME_LEN+1]; + format_local_iso_time(tbuf, last_attempt); + log_info(LD_GUARD, "Marked %s%sguard %s for possible retry, since we " + "haven't tried to use it since %s.", + guard->is_primary?"primary ":"", + guard->confirmed_idx>=0?"confirmed ":"", + entry_guard_describe(guard), + tbuf); + + guard->is_reachable = GUARD_REACHABLE_MAYBE; + if (guard->is_filtered_guard) + guard->is_usable_filtered_guard = 1; + } +} + +/** + * Get a guard for use with a circuit. Prefer to pick a running primary + * guard; then a non-pending running filtered confirmed guard; then a + * non-pending runnable filtered guard. Update the + * <b>last_tried_to_connect</b> time and the <b>is_pending</b> fields of the + * guard as appropriate. Set <b>state_out</b> to the new guard-state + * of the circuit. + */ +STATIC entry_guard_t * +select_entry_guard_for_circuit(guard_selection_t *gs, unsigned *state_out) +{ + tor_assert(gs); + tor_assert(state_out); + + /* "If any entry in PRIMARY_GUARDS has {is_reachable} status of + <maybe> or <yes>, return the first such guard." */ + SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) { + entry_guard_consider_retry(guard); + if (guard->is_reachable != GUARD_REACHABLE_NO) { + *state_out = GUARD_CIRC_STATE_USABLE_ON_COMPLETION; + guard->last_tried_to_connect = approx_time(); + log_info(LD_GUARD, "Selected primary guard %s for circuit.", + entry_guard_describe(guard)); + return guard; + } + } SMARTLIST_FOREACH_END(guard); + + /* "Otherwise, if the ordered intersection of {CONFIRMED_GUARDS} + and {USABLE_FILTERED_GUARDS} is nonempty, return the first + entry in that intersection that has {is_pending} set to + false." */ + SMARTLIST_FOREACH_BEGIN(gs->confirmed_entry_guards, entry_guard_t *, guard) { + if (guard->is_primary) + continue; /* we already considered this one. */ + entry_guard_consider_retry(guard); + if (guard->is_usable_filtered_guard && ! guard->is_pending) { + guard->is_pending = 1; + guard->last_tried_to_connect = approx_time(); + *state_out = GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD; + log_info(LD_GUARD, "No primary guards available. Selected confirmed " + "guard %s for circuit. Will try other guards before using " + "this circuit.", + entry_guard_describe(guard)); + return guard; + } + } SMARTLIST_FOREACH_END(guard); + + /* "Otherwise, if there is no such entry, select a member at + random from {USABLE_FILTERED_GUARDS}." */ + { + entry_guard_t *guard; + guard = sample_reachable_filtered_entry_guards(gs, + SAMPLE_EXCLUDE_CONFIRMED | + SAMPLE_EXCLUDE_PRIMARY | + SAMPLE_EXCLUDE_PENDING); + if (guard == NULL) { + log_info(LD_GUARD, "Absolutely no sampled guards were available."); + return NULL; + } + guard->is_pending = 1; + guard->last_tried_to_connect = approx_time(); + *state_out = GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD; + log_info(LD_GUARD, "No primary or confirmed guards available. Selected " + "random guard %s for circuit. Will try other guards before " + "using this circuit.", + entry_guard_describe(guard)); + return guard; + } +} + +/** + * Note that we failed to connect to or build circuits through <b>guard</b>. + * Use with a guard returned by select_entry_guards_for_circuit(). + */ +STATIC void +entry_guards_note_guard_failure(guard_selection_t *gs, + entry_guard_t *guard) +{ + tor_assert(gs); + + guard->is_reachable = GUARD_REACHABLE_NO; + guard->is_usable_filtered_guard = 0; + + guard->is_pending = 0; + if (guard->failing_since == 0) + guard->failing_since = approx_time(); + + log_info(LD_GUARD, "Recorded failure for %s%sguard %s", + guard->is_primary?"primary ":"", + guard->confirmed_idx>=0?"confirmed ":"", + entry_guard_describe(guard)); +} + +/** + * Called when the network comes up after having seemed to be down for + * a while: Mark the primary guards as maybe-reachable so that we'll + * try them again. + */ +STATIC void +mark_primary_guards_maybe_reachable(guard_selection_t *gs) +{ + SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) { + if (guard->is_reachable != GUARD_REACHABLE_NO) + continue; + + /* Note that we do not clear failing_since: this guard is now only + * _maybe-reachable_. */ + guard->is_reachable = GUARD_REACHABLE_MAYBE; + if (guard->is_filtered_guard) + guard->is_usable_filtered_guard = 1; + + } SMARTLIST_FOREACH_END(guard); +} + +/** + * Note that we successfully connected to, and built a circuit through + * <b>guard</b>. Given the old guard-state of the circuit in <b>old_state</b>, + * return the new guard-state of the circuit. + * + * Be aware: the circuit is only usable when its guard-state becomes + * GUARD_CIRC_STATE_COMPLETE. + **/ +STATIC unsigned +entry_guards_note_guard_success(guard_selection_t *gs, + entry_guard_t *guard, + unsigned old_state) +{ + tor_assert(gs); + + /* Save this, since we're about to overwrite it. */ + const time_t last_time_on_internet = gs->last_time_on_internet; + gs->last_time_on_internet = approx_time(); + + guard->is_reachable = GUARD_REACHABLE_YES; + guard->failing_since = 0; + guard->is_pending = 0; + if (guard->is_filtered_guard) + guard->is_usable_filtered_guard = 1; + + if (guard->confirmed_idx < 0) { + // XXXX prop271 XXXX update primary guards, since we confirmed something? + make_guard_confirmed(gs, guard); + } + + unsigned new_state; + if (old_state == GUARD_CIRC_STATE_USABLE_ON_COMPLETION) { + new_state = GUARD_CIRC_STATE_COMPLETE; + } else { + tor_assert_nonfatal( + old_state == GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD); + new_state = GUARD_CIRC_STATE_WAITING_FOR_BETTER_GUARD; + + if (last_time_on_internet + INTERNET_LIKELY_DOWN_INTERVAL + < approx_time()) { + mark_primary_guards_maybe_reachable(gs); + } else { + // update_waiting_circuits(gs); // XXXX prop271 write this function. + } + } + + // XXXX prop271 XXXX update primary guards, since we confirmed something? + // XXXX prop261 XXXX if so, here or above? + + log_info(LD_GUARD, "Recorded success for %s%sguard %s", + guard->is_primary?"primary ":"", + guard->confirmed_idx>=0?"confirmed ":"", + entry_guard_describe(guard)); + + return new_state; +} + +/** + * Helper: Return true iff <b>a</b> has higher priority than <b>b</b>. + */ +STATIC int +entry_guard_has_higher_priority(entry_guard_t *a, entry_guard_t *b) +{ + tor_assert(a && b); + if (a == b) + return 0; + + /* Confirmed is always better than unconfirmed; lower index better + than higher */ + if (a->confirmed_idx < 0) { + if (b->confirmed_idx >= 0) + return 0; + } else { + if (b->confirmed_idx < 0) + return 1; + + /* Lower confirmed_idx is better than higher. */ + return (a->confirmed_idx < b->confirmed_idx); + } + + /* If we reach this point, both are unconfirmed. If one is pending, it + * has higher priority. */ + if (a->is_pending) { + if (! b->is_pending) + return 1; + + /* Both are pending: earlier last_tried_connect wins. */ + return a->last_tried_to_connect < b->last_tried_to_connect; + } else { + if (b->is_pending) + return 0; + + /* Neither is pending: priorities are equal. */ + return 0; // XXXX prop271 return a tristate instead? + } +} + +/** * Return a newly allocated string for encoding the persistent parts of * <b>guard</b> to the state file. */ -ATTR_UNUSED STATIC char * +STATIC char * entry_guard_encode_for_state(entry_guard_t *guard) { /* @@ -375,7 +1312,7 @@ entry_guard_encode_for_state(entry_guard_t *guard) * (if possible) and return an entry_guard_t object for it. Return NULL * on complete failure. */ -ATTR_UNUSED STATIC entry_guard_t * +STATIC entry_guard_t * entry_guard_parse_from_state(const char *s) { /* Unrecognized entries get put in here. */ @@ -492,6 +1429,7 @@ entry_guard_parse_from_state(const char *s) /* Take sampled_by_version verbatim. */ guard->sampled_by_version = sampled_by; sampled_by = NULL; /* prevent free */ + // XXXX -- prop271 spec deviation -- we do not require sampled_by_version

/* Listed is a boolean */ if (listed && strcmp(listed, "0")) @@ -518,6 +1456,8 @@ entry_guard_parse_from_state(const char *s) /* initialize non-persistent fields */ guard->is_reachable = GUARD_REACHABLE_MAYBE;

+ /* XXXX prop271 Update everything on this guard. */ + goto done;

err: @@ -540,6 +1480,79 @@ entry_guard_parse_from_state(const char *s) return guard; }

+/* XXXXprop271 This is a dummy function added for now so that all of the + * new guard code will be counted as reachable. It should get removed. + */ +__attribute__((noreturn)) void +entry_guards_DUMMY_ENTRY_POINT(void) +{ + // prop271 XXXXX kludge; remove this + sampled_guards_update_from_consensus(NULL); + sample_reachable_filtered_entry_guards(NULL, 0); + entry_guards_update_confirmed(NULL); + entry_guards_update_primary(NULL); + select_entry_guard_for_circuit(NULL, NULL); + entry_guards_note_guard_failure(NULL, NULL); + entry_guards_note_guard_success(NULL, NULL, 0); + entry_guard_has_higher_priority(NULL, NULL); + entry_guard_encode_for_state(NULL); + entry_guard_parse_from_state(NULL); + compare_guards_by_confirmed_idx(NULL, NULL); + entry_guards_update_filtered_sets(NULL); + tor_assert(0); +} + +/* XXXXX ----------------------------------------------- */ +/* XXXXX prop271 ----- end of new-for-prop271 code ----- */ +/* XXXXX ----------------------------------------------- */ + +/** + * @name Constants for old (pre-prop271) guard selection algorithm. + */ + +/**@{*/ + +/* Default number of entry guards in the case where the NumEntryGuards + * consensus parameter is not set */ +#define DEFAULT_N_GUARDS 1 +/* Minimum and maximum number of entry guards (in case the NumEntryGuards + * consensus parameter is set). */ +#define MIN_N_GUARDS 1 +#define MAX_N_GUARDS 10 +/** Largest amount that we'll backdate chosen_on_date */ +#define CHOSEN_ON_DATE_SLOP (30*86400) +/** How long (in seconds) do we allow an entry guard to be nonfunctional, + * unlisted, excluded, or otherwise nonusable before we give up on it? */ +#define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60) +/**}@*/ + +/** + * @name Networkstatus parameters for old (pre-prop271) guard selection + */ +/**@}*/ +/** Choose how many entry guards or directory guards we'll use. If + * <b>for_directory</b> is true, we return how many directory guards to + * use; else we return how many entry guards to use. */ +STATIC int +decide_num_guards(const or_options_t *options, int for_directory) +{ + if (for_directory) { + int answer; + if (options->NumDirectoryGuards != 0) + return options->NumDirectoryGuards; + answer = networkstatus_get_param(NULL, "NumDirectoryGuards", 0, 0, 10); + if (answer) /* non-zero means use the consensus value */ + return answer; + } + + if (options->NumEntryGuards) + return options->NumEntryGuards; + + /* Use the value from the consensus, or 3 if no guidance. */ + return networkstatus_get_param(NULL, "NumEntryGuards", DEFAULT_N_GUARDS, + MIN_N_GUARDS, MAX_N_GUARDS); +} + /** Check whether the entry guard <b>e</b> is usable, given the directory * authorities' opinion about the router (stored in <b>ri</b>) and the user's * configuration (in <b>options</b>). Set <b>e</b>->bad_since @@ -2402,7 +3415,7 @@ entries_retry_all(const or_options_t *options) }

/** Free one guard selection context */ -static void +STATIC void guard_selection_free(guard_selection_t *gs) { if (!gs) return; @@ -2421,6 +3434,9 @@ guard_selection_free(guard_selection_t *gs) gs->sampled_entry_guards = NULL; }

+ smartlist_free(gs->confirmed_entry_guards); + smartlist_free(gs->primary_entry_guards); + tor_free(gs); }

diff --git a/src/or/entrynodes.h b/src/or/entrynodes.h index f07f843..5501e62 100644 --- a/src/or/entrynodes.h +++ b/src/or/entrynodes.h @@ -18,10 +18,6 @@ typedef struct guard_selection_s guard_selection_t; /* Forward declare for entry_guard_t; the real declaration is private. */ typedef struct entry_guard_t entry_guard_t;

-#define GUARD_REACHABLE_NO 0 -#define GUARD_REACHABLE_YES 1 -#define GUARD_REACHABLE_MAYBE 2 - /* Information about a guard's pathbias status. * These fields are used in circpathbias.c to try to detect entry * nodes that are failing circuits at a suspicious frequency. @@ -58,6 +54,17 @@ typedef struct guard_pathbias_t { } guard_pathbias_t;

#if defined(ENTRYNODES_PRIVATE) +/** + * @name values for entry_guard_t.is_reachable. + * + * See entry_guard_t.is_reachable for more information. + */ +/**@{*/ +#define GUARD_REACHABLE_NO 0 +#define GUARD_REACHABLE_YES 1 +#define GUARD_REACHABLE_MAYBE 2 +/**@}*/ + /** An entry_guard_t represents our information about a chosen long-term * first hop, known as a "helper" node in the literature. We can't just * use a node_t, since we want to remember these even when we @@ -67,35 +74,80 @@ struct entry_guard_t { char identity[DIGEST_LEN]; ed25519_public_key_t ed_id;

- /* XXXX prop271 DOCDOC document all these fields better */ + /** + * @name new guard selection algorithm fields. + * + * Only the new (prop271) algorithm uses these. For a more full + * description of the algorithm, see the module documentation for + * entrynodes.c + */ + /**@{*/

- /* Persistent fields, present for all sampled guards. */ + /* == Persistent fields, present for all sampled guards. */ + /** When was this guard added to the sample? */ time_t sampled_on_date; + /** Since what date has this guard been "unlisted"? A guard counts as + * unlisted if we have a live consensus that does not include it, or + * if we have a live consensus that does not include it as a usable + * guard. This field is zero when the guard is listed. */ time_t unlisted_since_date; // can be zero + /** What version of Tor added this guard to the sample? */ char *sampled_by_version; + /** Is this guard listed right now? If this is set, then + * unlisted_since_date should be set too. */ unsigned currently_listed : 1;

- /* Persistent fields, for confirmed guards. */ + /* == Persistent fields, for confirmed guards only */ + /** When was this guard confirmed? (That is, when did we first use it + * successfully and decide to keep it?) This field is zero if this is not a + * confirmed guard. */ time_t confirmed_on_date; /* 0 if not confirmed */ + /** + * In what order was this guard confirmed? Guards with lower indices + * appear earlier on the confirmed list. If the confirmed list is compacted, + * this field corresponds to the index of this guard on the confirmed list. + * + * This field is set to -1 if this guard is not confirmed. + */ int confirmed_idx; /* -1 if not confirmed; otherwise the order that this * item should occur in the CONFIRMED_GUARDS ordered * list */

/* ==== Non-persistent fields. */ /* == These are used by sampled guards */ + /** When did we last decide to try using this guard for a circuit? 0 for + * "not since we started up." */ time_t last_tried_to_connect; - unsigned is_reachable : 2; /* One of GUARD_REACHABLE_{NO,YES,MAYBE} */ + /** How reachable do we consider this guard to be? One of + * GUARD_REACHABLE_NO, GUARD_REACHABLE_YES, or GUARD_REACHABLE_MAYBE. */ + unsigned is_reachable : 2; + /** Boolean: true iff this guard is pending. A pending guard is one + * that we have an in-progress circuit through, and which we do not plan + * to try again until it either succeeds or fails. Primary guards can + * never be pending. */ unsigned is_pending : 1; + /** When did we get the earliest connection failure for this guard? + * We clear this field on a successful connect. We do _not_ clear it + * when we mark the guard as "MAYBE" reachable. + */ time_t failing_since;

- /* These determine presence in filtered guards and usable-filtered-guards - * respectively. */ + /* == Set inclusion flags. */ + /** If true, this guard is in the filtered set. The filtered set includes + * all sampled guards that our configuration allows us to use. */ unsigned is_filtered_guard : 1; + /** If true, this guard is in the usable filtered set. The usable filtered + * set includes all filtered guards that are not believed to be + * unreachable. (That is, those for which is_reachable is not + * GUARD_REACHABLE_NO) */ unsigned is_usable_filtered_guard : 1; + unsigned is_primary:1;

/** This string holds any fields that we are maintaining because * we saw them in the state, even if we don't understand them. */ char *extra_state_fields; + /**@}*/ + /** * @name legacy guard selection algorithm fields * @@ -128,6 +180,85 @@ struct entry_guard_t { /** Path bias information for this guard. */ guard_pathbias_t pb; }; + +/** + * All of the the context for guard selection on a particular client. + * + * (XXXX prop271 this paragraph below is not actually implemented yet.) + * We maintain multiple guard selection contexts for a client, depending + * aspects on its current configuration -- whether an extremely + * restrictive EntryNodes is used, whether UseBridges is enabled, and so + * on.) + * + * See the module documentation for entrynodes.c for more information + * about guard selection algorithms. + */ +struct guard_selection_s { + /** + * A value of 1 means that guard_selection_t structures have changed + * and those changes need to be flushed to disk. + * + * XXX prop271 we don't know how to flush multiple guard contexts to + * disk yet; fix that as soon as any way to change the default exists, + * or at least make sure this gets set on change. + */ + int dirty; + + /** + * A list of the sampled entry guards, as entry_guard_t structures. + * Not in any particular order. When we 'sample' a guard, we are + * noting it as a possible guard to pick in the future. The use of + * sampling here prevents us from being forced by an attacker to try + * every guard on the network. This list is persistent. + */ + smartlist_t *sampled_entry_guards; + + /** + * Ordered list (from highest to lowest priority) of guards that we + * have successfully contacted and decided to use. Every member of + * this list is a member of sampled_entry_guards. Every member should + * have confirmed_on_date set, and have confirmed_idx greater than + * any earlier member of the list. + * + * This list is persistent. It is a subset of the elements in + * sampled_entry_guards, and its pointers point to elements of + * sampled_entry_guards. + */ + smartlist_t *confirmed_entry_guards; + + /** + * Ordered list (from highest to lowest priority) of guards that we + * are willing to use the most happily. These guards may or may not + * yet be confirmed yet. If we can use one of these guards, we are + * probably not on a network that is trying to restrict our guard + * choices. + * + * This list is a subset of the elements in + * sampled_entry_guards, and its pointers point to elements of + * sampled_entry_guards. + */ + smartlist_t *primary_entry_guards; + + /** When did we last successfully build a circuit or use a circuit? */ + time_t last_time_on_internet; + + /** What confirmed_idx value should the next-added member of + * confirmed_entry_guards receive? */ + int next_confirmed_idx; + + /** + * A list of our chosen entry guards, as entry_guard_t structures; this + * preserves the pre-Prop271 behavior. + */ + smartlist_t *chosen_entry_guards; + + /** + * When we try to choose an entry guard, should we parse and add + * config's EntryNodes first? This was formerly a global. This + * preserves the pre-Prop271 behavior. + */ + int should_add_entry_nodes; +}; #endif

#if 1 @@ -160,12 +291,127 @@ void add_bridge_as_entry_guard(guard_selection_t *gs, int num_bridges_usable(void);

#ifdef ENTRYNODES_PRIVATE -STATIC time_t randomize_time(time_t now, time_t max_backdate); -STATIC void entry_guard_add_to_sample(guard_selection_t *gs, - node_t *node); +/** + * @name Parameters for the new (prop271) entry guard algorithm. + */ +/* XXXX prop271 some of these should be networkstatus parameters */ +/**@{*/ +/** + * We never let our sampled guard set grow larger than this fraction + * of the guards on the network. + */ +#define MAX_SAMPLE_THRESHOLD 0.30 +/** + * We always try to make our sample contain at least this many guards. + * + * XXXX prop271 There was a MIN_SAMPLE_THRESHOLD in the proposal, but I + * removed it in favor of MIN_FILTERED_SAMPLE_SIZE. -NM + */ +#define MIN_FILTERED_SAMPLE_SIZE 20 +/** + * If a guard is unlisted for this many days in a row, we remove it. + */ +#define REMOVE_UNLISTED_GUARDS_AFTER_DAYS 20 +/** + * We remove unconfirmed guards from the sample after this many days, + * regardless of whether they are listed or unlisted. + */ +#define GUARD_LIFETIME_DAYS 120 +/** + * We remove confirmed guards from the sample if they were sampled + * GUARD_LIFETIME_DAYS ago and confirmed this many days ago. + */ +#define GUARD_CONFIRMED_MIN_LIFETIME_DAYS 60 +/** + * How many guards do we try to keep on our primary guard list? + */ +#define N_PRIMARY_GUARDS 3 +/** + * If we haven't successfully built or used a circuit in this long, then + * consider that the internet is probably down. + */ +#define INTERNET_LIKELY_DOWN_INTERVAL (10*60) +/** + * DOCDOC. not yet used; see prop271. + */ +#define NONPRIMARY_GUARD_CONNECT_TIMEOUT 15 +/** + * DOCDOC. not yet used; see prop271. + */ +#define NONPRIMARY_GUARD_IDLE_TIMEOUT (10*60) +/** + * DOCDOC. not yet used; see prop271. + */ +#define MEANINGFUL_RESTRICTION_FRAC 0.2 +/** + * DOCDOC. not yet used. see prop271. + */ +#define EXTREME_RESTRICTION_FRAC 0.01 +/**@}*/ + +// ---------- XXXX these functions and definitions are post-prop271. +STATIC guard_selection_t *guard_selection_new(void); +STATIC void guard_selection_free(guard_selection_t *gs); +STATIC entry_guard_t *get_sampled_guard_with_id(guard_selection_t *gs, + const uint8_t *rsa_id); + +MOCK_DECL(STATIC time_t, randomize_time, (time_t now, time_t max_backdate)); +STATIC entry_guard_t *entry_guard_add_to_sample(guard_selection_t *gs, + const node_t *node); +STATIC entry_guard_t *entry_guards_expand_sample(guard_selection_t *gs); STATIC char *entry_guard_encode_for_state(entry_guard_t *guard); STATIC entry_guard_t *entry_guard_parse_from_state(const char *s); STATIC void entry_guard_free(entry_guard_t *e); +STATIC void entry_guards_update_filtered_sets(guard_selection_t *gs); +/** + * @name Flags for sample_reachable_filtered_entry_guards() + */ +/**@{*/ +#define SAMPLE_EXCLUDE_CONFIRMED (1u<<0) +#define SAMPLE_EXCLUDE_PRIMARY (1u<<1) +#define SAMPLE_EXCLUDE_PENDING (1u<<2) +/**@}*/ +STATIC entry_guard_t *sample_reachable_filtered_entry_guards( + guard_selection_t *gs, + unsigned flags); +STATIC void entry_guard_consider_retry(entry_guard_t *guard); +STATIC void make_guard_confirmed(guard_selection_t *gs, entry_guard_t *guard); +STATIC void entry_guards_update_confirmed(guard_selection_t *gs); +STATIC void entry_guards_update_primary(guard_selection_t *gs); +STATIC int num_reachable_filtered_guards(guard_selection_t *gs); +STATIC void sampled_guards_update_from_consensus(guard_selection_t *gs); +/** + * @name Possible guard-states for a circuit. + */ +/**@{*/ +/** State for a circuit that can (so far as the guard subsystem is + * concerned) be used for actual traffic as soon as it is successfully + * opened. */ +#define GUARD_CIRC_STATE_USABLE_ON_COMPLETION 1 +/** State for an non-open circuit that we shouldn't use for actual + * traffic, when it completes, unless other circuits to preferable + * guards fail. */ +#define GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD 2 +/** State for an open circuit that we shouldn't use for actual traffic + * unless other circuits to preferable guards fail. */ +#define GUARD_CIRC_STATE_WAITING_FOR_BETTER_GUARD 3 +/** State for a circuit that can (so far as the guard subsystem is + * concerned) be used for actual traffic. */ +#define GUARD_CIRC_STATE_COMPLETE 4 +/**@}*/ +STATIC void entry_guards_note_guard_failure(guard_selection_t *gs, + entry_guard_t *guard); +STATIC entry_guard_t *select_entry_guard_for_circuit(guard_selection_t *gs, + unsigned *state_out); +STATIC void mark_primary_guards_maybe_reachable(guard_selection_t *gs); +STATIC unsigned entry_guards_note_guard_success(guard_selection_t *gs, + entry_guard_t *guard, + unsigned old_state); +STATIC int entry_guard_has_higher_priority(entry_guard_t *a, entry_guard_t *b); + +void entry_guards_DUMMY_ENTRY_POINT(void); + +// ---------- XXXX this stuff is pre-prop271.

STATIC const node_t *add_an_entry_guard(guard_selection_t *gs, const node_t *chosen, diff --git a/src/test/test_entrynodes.c b/src/test/test_entrynodes.c index 45b730c..8e90b00 100644 --- a/src/test/test_entrynodes.c +++ b/src/test/test_entrynodes.c @@ -10,9 +10,11 @@ #include "or.h" #include "test.h"

+#include "bridges.h" #include "config.h" #include "entrynodes.h" #include "nodelist.h" +#include "networkstatus.h" #include "policies.h" #include "routerlist.h" #include "routerparse.h" @@ -21,6 +23,7 @@ #include "util.h"

#include "test_helpers.h" +#include "log_test_helpers.h"

/* TODO: * choose_random_entry() test with state set. @@ -72,6 +75,120 @@ fake_network_setup(const struct testcase_t *testcase) return dummy_state; }

+static networkstatus_t *dummy_consensus = NULL; + +static smartlist_t *big_fake_net_nodes = NULL; + +static smartlist_t * +bfn_mock_nodelist_get_list(void) +{ + return big_fake_net_nodes; +} + +static networkstatus_t * +bfn_mock_networkstatus_get_live_consensus(time_t now) +{ + (void)now; + return dummy_consensus; +} + +static const node_t * +bfn_mock_node_get_by_id(const char *id) +{ + SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n, + if (fast_memeq(n->identity, id, 20)) + return n); + + return NULL; +} + +/* Unittest cleanup function: Cleanup the fake network. */ +static int +big_fake_network_cleanup(const struct testcase_t *testcase, void *ptr) +{ + (void) testcase; + (void) ptr; + + if (big_fake_net_nodes) { + SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n, { + tor_free(n->rs); + tor_free(n->md); + tor_free(n); + }); + smartlist_free(big_fake_net_nodes); + } + + UNMOCK(nodelist_get_list); + UNMOCK(node_get_by_id); + UNMOCK(get_or_state); + UNMOCK(networkstatus_get_live_consensus); + or_state_free(dummy_state); + dummy_state = NULL; + tor_free(dummy_consensus); + + return 1; /* NOP */ +} + +/* Unittest setup function: Setup a fake network. */ +static void * +big_fake_network_setup(const struct testcase_t *testcase) +{ + int i; + + /* These are minimal node_t objects that only contain the aspects of node_t + * that we need for entrynodes.c. */ + const int N_NODES = 271; + + big_fake_net_nodes = smartlist_new(); + for (i = 0; i < N_NODES; ++i) { + node_t *n = tor_malloc_zero(sizeof(node_t)); + n->md = tor_malloc_zero(sizeof(microdesc_t)); + + crypto_rand(n->identity, sizeof(n->identity)); + n->rs = tor_malloc_zero(sizeof(routerstatus_t)); + + memcpy(n->rs->identity_digest, n->identity, DIGEST_LEN); + + n->is_running = n->is_valid = n->is_fast = n->is_stable = 1; + + n->rs->addr = 0x04020202; + n->rs->or_port = 1234; + n->rs->is_v2_dir = 1; + n->rs->has_bandwidth = 1; + n->rs->bandwidth_kb = 30; + + /* Call half of the nodes a possible guard. */ + if (i % 2 == 0) { + n->is_possible_guard = 1; + n->rs->guardfraction_percentage = 100; + n->rs->has_guardfraction = 1; + } + + smartlist_add(big_fake_net_nodes, n); + } + + dummy_state = tor_malloc_zero(sizeof(or_state_t)); + dummy_consensus = tor_malloc_zero(sizeof(networkstatus_t)); + dummy_consensus->valid_after = approx_time() - 3600; + dummy_consensus->valid_until = approx_time() + 3600; + + MOCK(nodelist_get_list, bfn_mock_nodelist_get_list); + MOCK(node_get_by_id, bfn_mock_node_get_by_id); + MOCK(get_or_state, + get_or_state_replacement); + MOCK(networkstatus_get_live_consensus, + bfn_mock_networkstatus_get_live_consensus); + /* Return anything but NULL (it's interpreted as test fail) */ + return (void*)testcase; +} + +static time_t +mock_randomize_time_no_randomization(time_t a, time_t b) +{ + (void) b; + return a; +} + static or_options_t mocked_options;

static const or_options_t * @@ -1089,10 +1206,972 @@ test_entry_guard_parse_from_state_partial_failure(void *arg) tor_free(mem_op_hex_tmp); }

+static void +test_entry_guard_add_single_guard(void *arg) +{ + (void)arg; + guard_selection_t *gs = guard_selection_new(); + + /* 1: Add a single guard to the sample. */ + node_t *n1 = smartlist_get(big_fake_net_nodes, 0); + time_t now = approx_time(); + tt_assert(n1->is_possible_guard == 1); + entry_guard_t *g1 = entry_guard_add_to_sample(gs, n1); + tt_assert(g1); + + /* Make sure its fields look right. */ + tt_mem_op(n1->identity, OP_EQ, g1->identity, DIGEST_LEN); + tt_i64_op(g1->sampled_on_date, OP_GE, now - 12*86400); + tt_i64_op(g1->sampled_on_date, OP_LE, now); + tt_str_op(g1->sampled_by_version, OP_EQ, VERSION); + tt_assert(g1->currently_listed == 1); + tt_i64_op(g1->confirmed_on_date, OP_EQ, 0); + tt_int_op(g1->confirmed_idx, OP_EQ, -1); + tt_int_op(g1->last_tried_to_connect, OP_EQ, 0); + tt_uint_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + tt_i64_op(g1->failing_since, OP_EQ, 0); + tt_assert(g1->is_filtered_guard == 1); + tt_assert(g1->is_usable_filtered_guard == 1); + tt_assert(g1->is_primary == 0); + tt_assert(g1->extra_state_fields == NULL); + + /* Make sure it got added. */ + tt_int_op(1, OP_EQ, smartlist_len(gs->sampled_entry_guards)); + tt_ptr_op(g1, OP_EQ, smartlist_get(gs->sampled_entry_guards, 0)); + tt_ptr_op(g1, OP_EQ, get_sampled_guard_with_id(gs, (uint8_t*)n1->identity)); + const uint8_t bad_id[20] = {0}; + tt_ptr_op(NULL, OP_EQ, get_sampled_guard_with_id(gs, bad_id)); + + done: + guard_selection_free(gs); +} + +static void +test_entry_guard_node_filter(void *arg) +{ + (void)arg; + guard_selection_t *gs = guard_selection_new(); + bridge_line_t *bl = NULL; + + /* Initialize a bunch of node objects that are all guards. */ + const int NUM = 7; + node_t *n[NUM]; + entry_guard_t *g[NUM]; + int i; + for (i=0; i < NUM; ++i) { + n[i] = smartlist_get(big_fake_net_nodes, i*2); // even ones are guards. + g[i] = entry_guard_add_to_sample(gs, n[i]); + + // everything starts out filtered-in + tt_assert(g[i]->is_filtered_guard == 1); + tt_assert(g[i]->is_usable_filtered_guard == 1); + } + tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, NUM); + + /* Make sure refiltering doesn't hurt */ + entry_guards_update_filtered_sets(gs); + for (i = 0; i < NUM; ++i) { + tt_assert(g[i]->is_filtered_guard == 1); + tt_assert(g[i]->is_usable_filtered_guard == 1); + } + tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, NUM); + + /* Now start doing things to make the guards get filtered out, 1 by 1. */ + + /* 0: Not listed. */ + g[0]->currently_listed = 0; + + /* 1: path bias says this guard is maybe eeeevil. */ + g[1]->pb.path_bias_disabled = 1; + + /* 2: Unreachable address. */ + n[2]->rs->addr = 0; + + /* 3: ExcludeNodes */ + n[3]->rs->addr = 0x90902020; + routerset_free(get_options_mutable()->ExcludeNodes); + get_options_mutable()->ExcludeNodes = routerset_new(); + routerset_parse(get_options_mutable()->ExcludeNodes, "144.144.0.0/16", ""); + + /* 4: Bridge. */ + sweep_bridge_list(); + bl = tor_malloc_zero(sizeof(bridge_line_t)); + tor_addr_from_ipv4h(&bl->addr, n[4]->rs->addr); + bl->port = n[4]->rs->or_port; + memcpy(bl->digest, n[4]->identity, 20); + bridge_add_from_config(bl); + bl = NULL; // prevent free. + + /* 5: Unreachable. This stays in the filter, but isn't in usable-filtered */ + g[5]->last_tried_to_connect = approx_time(); // prevent retry. + g[5]->is_reachable = GUARD_REACHABLE_NO; + + /* 6: no change. */ + + /* Now refilter and inspect. */ + entry_guards_update_filtered_sets(gs); + for (i = 0; i < NUM; ++i) { + tt_assert(g[i]->is_filtered_guard == (i == 5 || i == 6)); + tt_assert(g[i]->is_usable_filtered_guard == (i == 6)); + } + tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, 1); + + done: + guard_selection_free(gs); + tor_free(bl); +} + +static void +test_entry_guard_expand_sample(void *arg) +{ + (void)arg; + guard_selection_t *gs = guard_selection_new(); + digestmap_t *node_by_id = digestmap_new(); + + entry_guard_t *guard = entry_guards_expand_sample(gs); + tt_assert(guard); // the last guard returned. + + // Every sampled guard here should be filtered and reachable for now. + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, + num_reachable_filtered_guards(gs)); + + /* Make sure we got the right number. */ + tt_int_op(MIN_FILTERED_SAMPLE_SIZE, OP_EQ, + num_reachable_filtered_guards(gs)); + + // Make sure everything we got was from our fake node list, and everything + // was unique. + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, g) { + const node_t *n = bfn_mock_node_get_by_id(g->identity); + tt_assert(n); + tt_ptr_op(NULL, OP_EQ, digestmap_get(node_by_id, g->identity)); + digestmap_set(node_by_id, g->identity, (void*) n); + int idx = smartlist_pos(big_fake_net_nodes, n); + // The even ones are the guards; make sure we got guards. + tt_int_op(idx & 1, OP_EQ, 0); + } SMARTLIST_FOREACH_END(g); + + // Nothing became unusable/unfiltered, so a subsequent expand should + // make no changes. + guard = entry_guards_expand_sample(gs); + tt_assert(! guard); // no guard was added. + tt_int_op(MIN_FILTERED_SAMPLE_SIZE, OP_EQ, + num_reachable_filtered_guards(gs)); + + // Make a few guards unreachable. + guard = smartlist_get(gs->sampled_entry_guards, 0); + guard->is_usable_filtered_guard = 0; + guard = smartlist_get(gs->sampled_entry_guards, 1); + guard->is_usable_filtered_guard = 0; + guard = smartlist_get(gs->sampled_entry_guards, 2); + guard->is_usable_filtered_guard = 0; + tt_int_op(MIN_FILTERED_SAMPLE_SIZE - 3, OP_EQ, + num_reachable_filtered_guards(gs)); + + // This time, expanding the sample will add some more guards. + guard = entry_guards_expand_sample(gs); + tt_assert(guard); // no guard was added. + tt_int_op(MIN_FILTERED_SAMPLE_SIZE, OP_EQ, + num_reachable_filtered_guards(gs)); + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, + num_reachable_filtered_guards(gs)+3); + + // Still idempotent. + guard = entry_guards_expand_sample(gs); + tt_assert(! guard); // no guard was added. + tt_int_op(MIN_FILTERED_SAMPLE_SIZE, OP_EQ, + num_reachable_filtered_guards(gs)); + + // Now, do a nasty trick: tell the filter to exclude 31/32 of the guards. + // This will cause the sample size to get reeeeally huge, while the + // filtered sample size grows only slowly. + routerset_free(get_options_mutable()->ExcludeNodes); + get_options_mutable()->ExcludeNodes = routerset_new(); + routerset_parse(get_options_mutable()->ExcludeNodes, "144.144.0.0/16", ""); + SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n, { + if (n_sl_idx % 64 != 0) { + n->rs->addr = 0x90903030; + } + }); + entry_guards_update_filtered_sets(gs); + + // Surely (p ~ 1-2**-60), one of our guards has been excluded. + tt_int_op(num_reachable_filtered_guards(gs), OP_LT, + MIN_FILTERED_SAMPLE_SIZE); + + // Try to regenerate the guards. + guard = entry_guards_expand_sample(gs); + tt_assert(guard); // no guard was added. + + /* this time, it's possible that we didn't add enough sampled guards. */ + tt_int_op(num_reachable_filtered_guards(gs), OP_LE, + MIN_FILTERED_SAMPLE_SIZE); + /* but we definitely didn't exceed the sample maximum. */ + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_LE, + (int)((271 / 2) * .3)); + + done: + guard_selection_free(gs); + digestmap_free(node_by_id, NULL); +} + +static void +test_entry_guard_expand_sample_small_net(void *arg) +{ + (void)arg; + guard_selection_t *gs = guard_selection_new(); + + /* Fun corner case: not enough guards to make up our whole sample size. */ + SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n, { + if (n_sl_idx >= 40) { + tor_free(n->rs); + tor_free(n->md); + tor_free(n); + SMARTLIST_DEL_CURRENT(big_fake_net_nodes, n); + } else { + n->rs->addr = 0; // make the filter reject this. + } + }); + + entry_guard_t *guard = entry_guards_expand_sample(gs); + tt_assert(guard); // the last guard returned -- some guard was added. + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_GT, 0); + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_LT, 10); + tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, 0); + done: + guard_selection_free(gs); +} + +static void +test_entry_guard_update_from_consensus_status(void *arg) +{ + /* Here we're going to have some nodes become un-guardy, and say we got a + * new consensus. This should cause those nodes to get detected as + * unreachable. */ + + (void)arg; + int i; + time_t start = approx_time(); + guard_selection_t *gs = guard_selection_new(); + networkstatus_t *ns_tmp = NULL; + + /* Don't randomly backdate stuff; it will make correctness harder to check.*/ + MOCK(randomize_time, mock_randomize_time_no_randomization); + + /* First, sample some guards. */ + entry_guards_expand_sample(gs); + int n_sampled_pre = smartlist_len(gs->sampled_entry_guards); + int n_filtered_pre = num_reachable_filtered_guards(gs); + tt_i64_op(n_sampled_pre, OP_EQ, n_filtered_pre); + tt_i64_op(n_sampled_pre, OP_GT, 10); + + /* At this point, it should be a no-op to do this: */ + sampled_guards_update_from_consensus(gs); + + /* Now let's make some of our guards become unlisted. The easiest way to + * do that would be to take away their guard flag. */ + for (i = 0; i < 5; ++i) { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i); + node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity); + n->is_possible_guard = 0; + } + + update_approx_time(start + 30); + { + /* try this with no live networkstatus. Nothing should happen! */ + ns_tmp = dummy_consensus; + dummy_consensus = NULL; + sampled_guards_update_from_consensus(gs); + tt_i64_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre); + tt_i64_op(num_reachable_filtered_guards(gs), OP_EQ, n_filtered_pre); + /* put the networkstatus back. */ + dummy_consensus = ns_tmp; + ns_tmp = NULL; + } + + /* Now those guards should become unlisted, and drop off the filter, but + * stay in the sample. */ + update_approx_time(start + 60); + sampled_guards_update_from_consensus(gs); + + tt_i64_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre); + tt_i64_op(num_reachable_filtered_guards(gs), OP_EQ, n_filtered_pre - 5); + for (i = 0; i < 5; ++i) { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i); + tt_assert(! g->currently_listed); + tt_i64_op(g->unlisted_since_date, OP_EQ, start+60); + } + for (i = 5; i < n_sampled_pre; ++i) { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i); + tt_assert(g->currently_listed); + tt_i64_op(g->unlisted_since_date, OP_EQ, 0); + } + + /* Now re-list one, and remove one completely. */ + { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 0); + node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity); + n->is_possible_guard = 1; + } + { + /* try removing the node, to make sure we don't crash on an absent node + */ + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 5); + node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity); + smartlist_remove(big_fake_net_nodes, n); + tor_free(n->rs); + tor_free(n->md); + tor_free(n); + } + update_approx_time(start + 300); + sampled_guards_update_from_consensus(gs); + + /* guards 1..5 are now unlisted; 0,6,7.. are listed. */ + tt_i64_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre); + for (i = 1; i < 6; ++i) { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i); + tt_assert(! g->currently_listed); + if (i == 5) + tt_i64_op(g->unlisted_since_date, OP_EQ, start+300); + else + tt_i64_op(g->unlisted_since_date, OP_EQ, start+60); + } + for (i = 0; i < n_sampled_pre; i = (!i) ? 6 : i+1) { /* 0,6,7,8, ... */ + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i); + tt_assert(g->currently_listed); + tt_i64_op(g->unlisted_since_date, OP_EQ, 0); + } + + done: + tor_free(ns_tmp); /* in case we couldn't put it back */ + guard_selection_free(gs); + UNMOCK(randomize_time); +} + +static void +test_entry_guard_update_from_consensus_repair(void *arg) +{ + /* Here we'll make sure that our code to repair the unlisted-since + * times is correct. */ + + (void)arg; + int i; + time_t start = approx_time(); + guard_selection_t *gs = guard_selection_new(); + + /* Don't randomly backdate stuff; it will make correctness harder to check.*/ + MOCK(randomize_time, mock_randomize_time_no_randomization); + + /* First, sample some guards. */ + entry_guards_expand_sample(gs); + int n_sampled_pre = smartlist_len(gs->sampled_entry_guards); + int n_filtered_pre = num_reachable_filtered_guards(gs); + tt_i64_op(n_sampled_pre, OP_EQ, n_filtered_pre); + tt_i64_op(n_sampled_pre, OP_GT, 10); + + /* Now corrupt the list a bit. Call some unlisted-since-never, and some + * listed-and-unlisted-since-a-time. */ + update_approx_time(start + 300); + for (i = 0; i < 3; ++i) { + /* these will get a date. */ + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i); + node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity); + n->is_possible_guard = 0; + g->currently_listed = 0; + } + for (i = 3; i < 6; ++i) { + /* these will become listed. */ + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i); + g->unlisted_since_date = start+100; + } + setup_full_capture_of_logs(LOG_WARN); + sampled_guards_update_from_consensus(gs); + expect_log_msg_containing( + "was listed, but with unlisted_since_date set"); + expect_log_msg_containing( + "was unlisted, but with unlisted_since_date unset"); + teardown_capture_of_logs(); + + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre); + tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, n_filtered_pre - 3); + for (i = 3; i < n_sampled_pre; ++i) { + /* these will become listed. */ + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, i); + if (i < 3) { + tt_assert(! g->currently_listed); + tt_i64_op(g->unlisted_since_date, OP_EQ, start+300); + } else { + tt_assert(g->currently_listed); + tt_i64_op(g->unlisted_since_date, OP_EQ, 0); + } + } + + done: + teardown_capture_of_logs(); + guard_selection_free(gs); + UNMOCK(randomize_time); +} + +static void +test_entry_guard_update_from_consensus_remove(void *arg) +{ + /* Now let's check the logic responsible for removing guards from the + * sample entirely. */ + + (void)arg; + //int i; + guard_selection_t *gs = guard_selection_new(); + smartlist_t *keep_ids = smartlist_new(); + smartlist_t *remove_ids = smartlist_new(); + + /* Don't randomly backdate stuff; it will make correctness harder to check.*/ + MOCK(randomize_time, mock_randomize_time_no_randomization); + + /* First, sample some guards. */ + entry_guards_expand_sample(gs); + int n_sampled_pre = smartlist_len(gs->sampled_entry_guards); + int n_filtered_pre = num_reachable_filtered_guards(gs); + tt_i64_op(n_sampled_pre, OP_EQ, n_filtered_pre); + tt_i64_op(n_sampled_pre, OP_GT, 10); + + const time_t one_day_ago = approx_time() - 1*24*60*60; + const time_t one_year_ago = approx_time() - 365*24*60*60; + const time_t two_years_ago = approx_time() - 2*365*24*60*60; + /* 0: unlisted for a day. (keep this) */ + { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 0); + node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity); + n->is_possible_guard = 0; + g->currently_listed = 0; + g->unlisted_since_date = one_day_ago; + smartlist_add(keep_ids, tor_memdup(g->identity, 20)); + } + /* 1: unlisted for a year. (remove this) */ + { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 1); + node_t *n = (node_t*) bfn_mock_node_get_by_id(g->identity); + n->is_possible_guard = 0; + g->currently_listed = 0; + g->unlisted_since_date = one_year_ago; + smartlist_add(remove_ids, tor_memdup(g->identity, 20)); + } + /* 2: added a day ago, never confirmed. (keep this) */ + { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 2); + g->sampled_on_date = one_day_ago; + smartlist_add(keep_ids, tor_memdup(g->identity, 20)); + } + /* 3: added a year ago, never confirmed. (remove this) */ + { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 3); + g->sampled_on_date = one_year_ago; + smartlist_add(remove_ids, tor_memdup(g->identity, 20)); + } + /* 4: added two year ago, confirmed yesterday, primary. (keep this.) */ + { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 4); + g->sampled_on_date = one_year_ago; + g->confirmed_on_date = one_day_ago; + g->confirmed_idx = 0; + g->is_primary = 1; + smartlist_add(gs->confirmed_entry_guards, g); + smartlist_add(gs->primary_entry_guards, g); + smartlist_add(keep_ids, tor_memdup(g->identity, 20)); + } + /* 5: added two years ago, confirmed a year ago, primary. (remove this) */ + { + entry_guard_t *g = smartlist_get(gs->sampled_entry_guards, 5); + g->sampled_on_date = two_years_ago; + g->confirmed_on_date = one_year_ago; + g->confirmed_idx = 1; + g->is_primary = 1; + smartlist_add(gs->confirmed_entry_guards, g); + smartlist_add(gs->primary_entry_guards, g); + smartlist_add(remove_ids, tor_memdup(g->identity, 20)); + } + + sampled_guards_update_from_consensus(gs); + + /* Did we remove the right ones? */ + SMARTLIST_FOREACH(keep_ids, uint8_t *, id, { + tt_assert(get_sampled_guard_with_id(gs, id) != NULL); + }); + SMARTLIST_FOREACH(remove_ids, uint8_t *, id, { + tt_want(get_sampled_guard_with_id(gs, id) == NULL); + }); + + /* Did we remove the right number? */ + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_sampled_pre - 3); + + done: + guard_selection_free(gs); + UNMOCK(randomize_time); + SMARTLIST_FOREACH(keep_ids, char *, cp, tor_free(cp)); + SMARTLIST_FOREACH(remove_ids, char *, cp, tor_free(cp)); + smartlist_free(keep_ids); + smartlist_free(remove_ids); +} + +static void +test_entry_guard_confirming_guards(void *arg) +{ + (void)arg; + /* Now let's check the logic responsible for manipulating the list + * of confirmed guards */ + guard_selection_t *gs = guard_selection_new(); + MOCK(randomize_time, mock_randomize_time_no_randomization); + + /* Create the sample. */ + entry_guards_expand_sample(gs); + + /* Confirm a few guards. */ + time_t start = approx_time(); + entry_guard_t *g1 = smartlist_get(gs->sampled_entry_guards, 0); + entry_guard_t *g2 = smartlist_get(gs->sampled_entry_guards, 1); + entry_guard_t *g3 = smartlist_get(gs->sampled_entry_guards, 8); + make_guard_confirmed(gs, g2); + update_approx_time(start + 10); + make_guard_confirmed(gs, g1); + make_guard_confirmed(gs, g3); + + /* Were the correct dates and indices fed in? */ + tt_int_op(g1->confirmed_idx, OP_EQ, 1); + tt_int_op(g2->confirmed_idx, OP_EQ, 0); + tt_int_op(g3->confirmed_idx, OP_EQ, 2); + tt_i64_op(g1->confirmed_on_date, OP_EQ, start+10); + tt_i64_op(g2->confirmed_on_date, OP_EQ, start); + tt_i64_op(g3->confirmed_on_date, OP_EQ, start+10); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g2); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g1); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 2), OP_EQ, g3); + + /* Now make sure we can regenerate the confirmed_entry_guards list. */ + smartlist_clear(gs->confirmed_entry_guards); + g2->confirmed_idx = 0; + g1->confirmed_idx = 10; + g3->confirmed_idx = 100; + entry_guards_update_confirmed(gs); + tt_int_op(g1->confirmed_idx, OP_EQ, 1); + tt_int_op(g2->confirmed_idx, OP_EQ, 0); + tt_int_op(g3->confirmed_idx, OP_EQ, 2); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g2); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g1); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 2), OP_EQ, g3); + + /* Now make sure we can regenerate the confirmed_entry_guards list if + * the indices are messed up. */ + g1->confirmed_idx = g2->confirmed_idx = g3->confirmed_idx = 999; + smartlist_clear(gs->confirmed_entry_guards); + entry_guards_update_confirmed(gs); + tt_int_op(g1->confirmed_idx, OP_GE, 0); + tt_int_op(g2->confirmed_idx, OP_GE, 0); + tt_int_op(g3->confirmed_idx, OP_GE, 0); + tt_int_op(g1->confirmed_idx, OP_LE, 2); + tt_int_op(g2->confirmed_idx, OP_LE, 2); + tt_int_op(g3->confirmed_idx, OP_LE, 2); + g1 = smartlist_get(gs->confirmed_entry_guards, 0); + g2 = smartlist_get(gs->confirmed_entry_guards, 1); + g3 = smartlist_get(gs->confirmed_entry_guards, 2); + tt_int_op(g1->confirmed_idx, OP_EQ, 0); + tt_int_op(g2->confirmed_idx, OP_EQ, 1); + tt_int_op(g3->confirmed_idx, OP_EQ, 2); + tt_assert(g1 != g2); + tt_assert(g1 != g3); + tt_assert(g2 != g3); + + done: + UNMOCK(randomize_time); + guard_selection_free(gs); +} + +static void +test_entry_guard_sample_reachable_filtered(void *arg) +{ + (void)arg; + guard_selection_t *gs = guard_selection_new(); + entry_guards_expand_sample(gs); + const int N = 10000; + bitarray_t *selected = NULL; + int i, j; + + /* We've got a sampled list now; let's make one non-usable-filtered; some + * confirmed, some primary, some pending. + */ + int n_guards = smartlist_len(gs->sampled_entry_guards); + tt_int_op(n_guards, OP_GT, 10); + entry_guard_t *g; + g = smartlist_get(gs->sampled_entry_guards, 0); + g->is_pending = 1; + g = smartlist_get(gs->sampled_entry_guards, 1); + make_guard_confirmed(gs, g); + g = smartlist_get(gs->sampled_entry_guards, 2); + g->is_primary = 1; + g = smartlist_get(gs->sampled_entry_guards, 3); + g->pb.path_bias_disabled = 1; + + entry_guards_update_filtered_sets(gs); + tt_int_op(num_reachable_filtered_guards(gs), OP_EQ, n_guards - 1); + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_guards); + + // +1 since the one we made disabled will make another one get added. + ++n_guards; + + /* Try a bunch of selections. */ + const struct { + int flag; int idx; + } tests[] = { + { 0, -1 }, + { SAMPLE_EXCLUDE_CONFIRMED, 1 }, + { SAMPLE_EXCLUDE_PRIMARY, 2 }, + { SAMPLE_EXCLUDE_PENDING, 0 }, + { -1, -1}, + }; + + for (j = 0; tests[j].flag >= 0; ++j) { + selected = bitarray_init_zero(n_guards); + const int excluded_flags = tests[j].flag; + const int excluded_idx = tests[j].idx; + for (i = 0; i < N; ++i) { + g = sample_reachable_filtered_entry_guards(gs, excluded_flags); + tor_assert(g); + int pos = smartlist_pos(gs->sampled_entry_guards, g); + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_guards); + tt_int_op(pos, OP_GE, 0); + tt_int_op(pos, OP_LT, n_guards); + bitarray_set(selected, pos); + } + for (i = 0; i < n_guards; ++i) { + const int should_be_set = (i != excluded_idx && + i != 3); // filtered out. + tt_int_op(!!bitarray_is_set(selected, i), OP_EQ, should_be_set); + } + bitarray_free(selected); + selected = NULL; + } + + done: + guard_selection_free(gs); + bitarray_free(selected); +} + +static void +test_entry_guard_sample_reachable_filtered_empty(void *arg) +{ + (void)arg; + guard_selection_t *gs = guard_selection_new(); + /* What if we try to sample from a set of 0? */ + SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n, + n->is_possible_guard = 0); + + entry_guard_t *g = sample_reachable_filtered_entry_guards(gs, 0); + tt_ptr_op(g, OP_EQ, NULL); + + done: + guard_selection_free(gs); +} + +static void +test_entry_guard_retry_unreachable(void *arg) +{ + (void)arg; + guard_selection_t *gs = guard_selection_new(); + + entry_guards_expand_sample(gs); + /* Let's say that we have two guards, and they're down. + */ + time_t start = approx_time();; + entry_guard_t *g1 = smartlist_get(gs->sampled_entry_guards, 0); + entry_guard_t *g2 = smartlist_get(gs->sampled_entry_guards, 1); + entry_guard_t *g3 = smartlist_get(gs->sampled_entry_guards, 2); + g1->is_reachable = GUARD_REACHABLE_NO; + g2->is_reachable = GUARD_REACHABLE_NO; + g1->is_primary = 1; + g1->failing_since = g2->failing_since = start; + g1->last_tried_to_connect = g2->last_tried_to_connect = start; + + /* Wait 5 minutes. Nothing will get retried. */ + update_approx_time(start + 5 * 60); + entry_guard_consider_retry(g1); + entry_guard_consider_retry(g2); + entry_guard_consider_retry(g3); // just to make sure this doesn't crash. + tt_int_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_NO); + tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_NO); + tt_int_op(g3->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + + /* After 30 min, the primary one gets retried */ + update_approx_time(start + 35 * 60); + entry_guard_consider_retry(g1); + entry_guard_consider_retry(g2); + tt_int_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_NO); + + g1->is_reachable = GUARD_REACHABLE_NO; + g1->last_tried_to_connect = start + 35*60; + + /* After 1 hour, we'll retry the nonprimary one. */ + update_approx_time(start + 61 * 60); + entry_guard_consider_retry(g1); + entry_guard_consider_retry(g2); + tt_int_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_NO); + tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + + g2->is_reachable = GUARD_REACHABLE_NO; + g2->last_tried_to_connect = start + 61*60; + + /* And then the primary one again. */ + update_approx_time(start + 66 * 60); + entry_guard_consider_retry(g1); + entry_guard_consider_retry(g2); + tt_int_op(g1->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_NO); + + done: + guard_selection_free(gs); +} + +static void +test_entry_guard_manage_primary(void *arg) +{ + (void)arg; + guard_selection_t *gs = guard_selection_new(); + smartlist_t *prev_guards = smartlist_new(); + + /* If no guards are confirmed, we should pick a few reachable guards and + * call them all primary. But not confirmed.*/ + entry_guards_update_primary(gs); + int n_primary = smartlist_len(gs->primary_entry_guards); + tt_int_op(n_primary, OP_GE, 1); + SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, { + tt_assert(g->is_primary); + tt_assert(g->confirmed_idx == -1); + }); + + /* Calling it a second time should leave the guards unchanged. */ + smartlist_add_all(prev_guards, gs->primary_entry_guards); + entry_guards_update_primary(gs); + tt_int_op(smartlist_len(gs->primary_entry_guards), OP_EQ, n_primary); + SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, { + tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx)); + }); + + /* If we have one confirmed guard, that guards becomes the first primary + * guard, and the other primary guards get kept. */ + + /* find a non-primary guard... */ + entry_guard_t *confirmed = NULL; + SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, g, { + if (! g->is_primary) { + confirmed = g; + break; + } + }); + tt_assert(confirmed); + /* make it confirmed. */ + make_guard_confirmed(gs, confirmed); + /* update the list... */ + smartlist_clear(prev_guards); + smartlist_add_all(prev_guards, gs->primary_entry_guards); + entry_guards_update_primary(gs); + + /* and see what's primary now! */ + tt_int_op(smartlist_len(gs->primary_entry_guards), OP_EQ, n_primary); + tt_ptr_op(smartlist_get(gs->primary_entry_guards, 0), OP_EQ, confirmed); + SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, { + tt_assert(g->is_primary); + if (g_sl_idx == 0) + continue; + tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx - 1)); + }); + { + entry_guard_t *prev_last_guard = smartlist_get(prev_guards, n_primary-1); + tt_assert(! prev_last_guard->is_primary); + } + + /* Calling it a fourth time should leave the guards unchanged. */ + smartlist_clear(prev_guards); + smartlist_add_all(prev_guards, gs->primary_entry_guards); + entry_guards_update_primary(gs); + tt_int_op(smartlist_len(gs->primary_entry_guards), OP_EQ, n_primary); + SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, { + tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx)); + }); + + done: + guard_selection_free(gs); + smartlist_free(prev_guards); +} + +static void +test_entry_guard_select_for_circuit_no_confirmed(void *arg) +{ + /* Simpler cases: no gaurds are confirmed yet. */ + (void)arg; + guard_selection_t *gs = guard_selection_new(); + + /* simple starting configuration */ + entry_guards_update_primary(gs); + unsigned state = 9999; + + entry_guard_t *g = select_entry_guard_for_circuit(gs, &state); + + tt_assert(g); + tt_assert(g->is_primary); + tt_int_op(g->confirmed_idx, OP_EQ, -1); + tt_assert(g->is_pending == 0); // primary implies non-pending. + tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_ON_COMPLETION); + tt_i64_op(g->last_tried_to_connect, OP_EQ, approx_time()); + + // If we do that again, we should get the same guard. + entry_guard_t *g2 = select_entry_guard_for_circuit(gs, &state); + tt_ptr_op(g2, OP_EQ, g); + + // if we mark that guard down, we should get a different primary guard. + // auto-retry it. + g->is_reachable = GUARD_REACHABLE_NO; + g->unreachable_since = approx_time() - 10; + g->last_tried_to_connect = approx_time() - 10; + state = 9999; + g2 = select_entry_guard_for_circuit(gs, &state); + tt_ptr_op(g2, OP_NE, g); + tt_assert(g2); + tt_assert(g2->is_primary); + tt_int_op(g2->confirmed_idx, OP_EQ, -1); + tt_assert(g2->is_pending == 0); // primary implies non-pending. + tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_ON_COMPLETION); + tt_i64_op(g2->last_tried_to_connect, OP_EQ, approx_time()); + + // If we say that the first primary guard was last tried a long time ago, we + // should get an automatic retry on it. + g->unreachable_since = approx_time() - 72*60*60; + g->last_tried_to_connect = approx_time() - 72*60*60; + state = 9999; + g2 = select_entry_guard_for_circuit(gs, &state); + tt_ptr_op(g2, OP_EQ, g); + tt_assert(g2); + tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_ON_COMPLETION); + tt_i64_op(g2->last_tried_to_connect, OP_EQ, approx_time()); + tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + + // And if we mark ALL the primary guards down, we should get another guard + // at random. + SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, guard, { + guard->is_reachable = GUARD_REACHABLE_NO; + guard->last_tried_to_connect = approx_time() - 5; + guard->unreachable_since = approx_time() - 30; + }); + state = 9999; + g2 = select_entry_guard_for_circuit(gs, &state); + tt_assert(g2); + tt_assert(!g2->is_primary); + tt_int_op(g2->confirmed_idx, OP_EQ, -1); + tt_assert(g2->is_pending == 1); + tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD); + tt_i64_op(g2->last_tried_to_connect, OP_EQ, approx_time()); + tt_int_op(g2->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + + // As a bonus, maybe we should be retrying the primary guards. Let's say so. + mark_primary_guards_maybe_reachable(gs); + SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, guard, { + tt_int_op(guard->is_reachable, OP_EQ, GUARD_REACHABLE_MAYBE); + tt_assert(guard->is_usable_filtered_guard == 1); + // no change to these fields. + tt_i64_op(guard->last_tried_to_connect, OP_EQ, approx_time() - 5); + tt_i64_op(guard->unreachable_since, OP_EQ, approx_time() - 30); + }); + + done: + guard_selection_free(gs); +} + +static void +test_entry_guard_select_for_circuit_confirmed(void *arg) +{ + /* Case 2: if all the primary guards are down, and there are more confirmed + guards, we use a confirmed guard. */ + (void)arg; + int i; + guard_selection_t *gs = guard_selection_new(); + const int N_CONFIRMED = 10; + + /* slightly more complicated simple starting configuration */ + entry_guards_update_primary(gs); + for (i = 0; i < N_CONFIRMED; ++i) { + entry_guard_t *guard = smartlist_get(gs->sampled_entry_guards, i); + make_guard_confirmed(gs, guard); + } + entry_guards_update_primary(gs); // rebuild the primary list. + + unsigned state = 9999; + + // As above, this gives us a primary guard. + entry_guard_t *g = select_entry_guard_for_circuit(gs, &state); + tt_assert(g); + tt_assert(g->is_primary); + tt_int_op(g->confirmed_idx, OP_EQ, 0); + tt_assert(g->is_pending == 0); // primary implies non-pending. + tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_ON_COMPLETION); + tt_i64_op(g->last_tried_to_connect, OP_EQ, approx_time()); + tt_ptr_op(g, OP_EQ, smartlist_get(gs->primary_entry_guards, 0)); + + // But if we mark all the primary guards down... + SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, guard, { + guard->last_tried_to_connect = approx_time(); + entry_guards_note_guard_failure(gs, guard); + }); + + // ... we should get a confirmed guard. + state = 9999; + g = select_entry_guard_for_circuit(gs, &state); + tt_assert(g); + tt_assert(! g->is_primary); + tt_int_op(g->confirmed_idx, OP_EQ, smartlist_len(gs->primary_entry_guards)); + tt_assert(g->is_pending); + tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD); + tt_i64_op(g->last_tried_to_connect, OP_EQ, approx_time()); + + // And if we try again, we should get a different confirmed guard, since + // that one is pending. + state = 9999; + entry_guard_t *g2 = select_entry_guard_for_circuit(gs, &state); + tt_assert(g2); + tt_assert(! g2->is_primary); + tt_ptr_op(g2, OP_NE, g); + tt_int_op(g2->confirmed_idx, OP_EQ, + smartlist_len(gs->primary_entry_guards)+1); + tt_assert(g2->is_pending); + tt_uint_op(state, OP_EQ, GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD); + tt_i64_op(g2->last_tried_to_connect, OP_EQ, approx_time()); + + // If we make every confirmed guard become pending then we start poking + // other guards. + const int n_remaining_confirmed = + N_CONFIRMED - 2 - smartlist_len(gs->primary_entry_guards); + for (i = 0; i < n_remaining_confirmed; ++i) { + g = select_entry_guard_for_circuit(gs, &state); + tt_int_op(g->confirmed_idx, OP_GE, 0); + tt_assert(g); + } + state = 9999; + g = select_entry_guard_for_circuit(gs, &state); + tt_assert(g); + tt_assert(g->is_pending); + tt_int_op(g->confirmed_idx, OP_EQ, -1); + + done: + guard_selection_free(gs); +} + static const struct testcase_setup_t fake_network = { fake_network_setup, fake_network_cleanup };

+static const struct testcase_setup_t big_fake_network = { + big_fake_network_setup, big_fake_network_cleanup +}; + +#define BFN_TEST(name) \ + { #name, test_entry_guard_ ## name, TT_FORK, &big_fake_network, NULL } + struct testcase_t entrynodes_tests[] = { { "entry_is_time_to_retry", test_entry_is_time_to_retry, TT_FORK, NULL, NULL }, @@ -1136,6 +2215,20 @@ struct testcase_t entrynodes_tests[] = { test_entry_guard_parse_from_state_failure, 0, NULL, NULL }, { "parse_from_state_partial_failure", test_entry_guard_parse_from_state_partial_failure, 0, NULL, NULL }, + BFN_TEST(add_single_guard), + BFN_TEST(node_filter), + BFN_TEST(expand_sample), + BFN_TEST(expand_sample_small_net), + BFN_TEST(update_from_consensus_status), + BFN_TEST(update_from_consensus_repair), + BFN_TEST(update_from_consensus_remove), + BFN_TEST(confirming_guards), + BFN_TEST(sample_reachable_filtered), + BFN_TEST(sample_reachable_filtered_empty), + BFN_TEST(retry_unreachable), + BFN_TEST(manage_primary), + BFN_TEST(select_for_circuit_no_confirmed), + BFN_TEST(select_for_circuit_confirmed), END_OF_TESTCASES };