diff options
Diffstat (limited to 'src/or/entrynodes.c')
| -rw-r--r-- | src/or/entrynodes.c | 5248 |
1 files changed, 3100 insertions, 2148 deletions
diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c index 265b6dcda1..0109da8e01 100644 --- a/src/or/entrynodes.c +++ b/src/or/entrynodes.c @@ -10,18 +10,118 @@ * * Entry nodes can be guards (for general use) or bridges (for censorship * circumvention). + * + * 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. + * + * 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. + * + * [x] Whenever we get a new consensus, call update_from_consensus(). (LATER.) + * + * [x] 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. + * + * [x] When we make a guard confirmed, update the primary list. + * + * [x] When we make a guard filtered or unfiltered, update the primary list. + * + * [x] 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 #include "or.h" +#include "channel.h" +#include "bridges.h" #include "circpathbias.h" #include "circuitbuild.h" +#include "circuitlist.h" #include "circuitstats.h" #include "config.h" #include "confparse.h" #include "connection.h" -#include "connection_or.h" #include "control.h" #include "directory.h" #include "entrynodes.h" @@ -37,2509 +137,3360 @@ #include "transports.h" #include "statefile.h" -/** Information about a configured bridge. Currently this just matches the - * ones in the torrc file, but one day we may be able to learn about new - * bridges on our own, and remember them in the state file. */ -typedef struct { - /** Address of the bridge. */ - tor_addr_t addr; - /** TLS port for the bridge. */ - uint16_t port; - /** Boolean: We are re-parsing our bridge list, and we are going to remove - * this one if we don't find it in the list of configured bridges. */ - unsigned marked_for_removal : 1; - /** Expected identity digest, or all zero bytes if we don't know what the - * digest should be. */ - char identity[DIGEST_LEN]; - - /** Name of pluggable transport protocol taken from its config line. */ - char *transport_name; - - /** When should we next try to fetch a descriptor for this bridge? */ - download_status_t fetch_status; - - /** A smartlist of k=v values to be passed to the SOCKS proxy, if - transports are used for this bridge. */ - smartlist_t *socks_args; -} bridge_info_t; - -/** A list of our chosen entry guards. */ -static smartlist_t *entry_guards = NULL; -/** A value of 1 means that the entry_guards list has changed +/** A list of existing guard selection contexts. */ +static smartlist_t *guard_contexts = NULL; +/** The currently enabled guard selection context. */ +static guard_selection_t *curr_guard_context = NULL; + +/** A value of 1 means that at least one context has changed, * and those changes need to be flushed to disk. */ static int entry_guards_dirty = 0; -static void bridge_free(bridge_info_t *bridge); -static const node_t *choose_random_entry_impl(cpath_build_state_t *state, - int for_directory, - dirinfo_type_t dirtype, - int *n_options_out); -static int num_bridges_usable(void); - -/* 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 - -/** Return the list of entry guards, creating it if necessary. */ -const smartlist_t * -get_entry_guards(void) -{ - if (! entry_guards) - entry_guards = smartlist_new(); - return entry_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 - * accordingly. Return true iff the entry guard's status changes. - * - * If it's not usable, set *<b>reason</b> to a static string explaining why. - */ -static int -entry_guard_set_status(entry_guard_t *e, const node_t *node, - time_t now, const or_options_t *options, - const char **reason) +static void entry_guard_set_filtered_flags(const or_options_t *options, + guard_selection_t *gs, + entry_guard_t *guard); +static void pathbias_check_use_success_count(entry_guard_t *guard); +static void pathbias_check_close_success_count(entry_guard_t *guard); +static int node_is_possible_guard(const node_t *node); +static int node_passes_guard_filter(const or_options_t *options, + const node_t *node); +static entry_guard_t *entry_guard_add_to_sample_impl(guard_selection_t *gs, + const uint8_t *rsa_id_digest, + const char *nickname, + const tor_addr_port_t *bridge_addrport); +static entry_guard_t *get_sampled_guard_by_bridge_addr(guard_selection_t *gs, + const tor_addr_port_t *addrport); +static int entry_guard_obeys_restriction(const entry_guard_t *guard, + const entry_guard_restriction_t *rst); + +/** Return 0 if we should apply guardfraction information found in the + * consensus. A specific consensus can be specified with the + * <b>ns</b> argument, if NULL the most recent one will be picked.*/ +int +should_apply_guardfraction(const networkstatus_t *ns) { - char buf[HEX_DIGEST_LEN+1]; - int changed = 0; + /* We need to check the corresponding torrc option and the consensus + * parameter if we need to. */ + const or_options_t *options = get_options(); + + /* If UseGuardFraction is 'auto' then check the same-named consensus + * parameter. If the consensus parameter is not present, default to + * "off". */ + if (options->UseGuardFraction == -1) { + return networkstatus_get_param(ns, "UseGuardFraction", + 0, /* default to "off" */ + 0, 1); + } - *reason = NULL; + return options->UseGuardFraction; +} - /* Do we want to mark this guard as bad? */ +/** Return true iff we know a descriptor for <b>guard</b> */ +static int +guard_has_descriptor(const entry_guard_t *guard) +{ + const node_t *node = node_get_by_id(guard->identity); if (!node) - *reason = "unlisted"; - else if (!node->is_running) - *reason = "down"; - else if (options->UseBridges && (!node->ri || - node->ri->purpose != ROUTER_PURPOSE_BRIDGE)) - *reason = "not a bridge"; - else if (options->UseBridges && !node_is_a_configured_bridge(node)) - *reason = "not a configured bridge"; - else if (!options->UseBridges && !node->is_possible_guard && - !routerset_contains_node(options->EntryNodes,node)) - *reason = "not recommended as a guard"; - else if (routerset_contains_node(options->ExcludeNodes, node)) - *reason = "excluded"; - /* We only care about OR connection connectivity for entry guards. */ - else if (!fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION, 0)) - *reason = "unreachable by config"; - else if (e->path_bias_disabled) - *reason = "path-biased"; - - if (*reason && ! e->bad_since) { - /* Router is newly bad. */ - base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN); - log_info(LD_CIRC, "Entry guard %s (%s) is %s: marking as unusable.", - e->nickname, buf, *reason); - - e->bad_since = now; - control_event_guard(e->nickname, e->identity, "BAD"); - changed = 1; - } else if (!*reason && e->bad_since) { - /* There's nothing wrong with the router any more. */ - base16_encode(buf, sizeof(buf), e->identity, DIGEST_LEN); - log_info(LD_CIRC, "Entry guard %s (%s) is no longer unusable: " - "marking as ok.", e->nickname, buf); - - e->bad_since = 0; - control_event_guard(e->nickname, e->identity, "GOOD"); - changed = 1; + return 0; + return node_has_descriptor(node); +} + +/** + * Try to determine the correct type for a selection named "name", + * if <b>type</b> is GS_TYPE_INFER. + */ +STATIC guard_selection_type_t +guard_selection_infer_type(guard_selection_type_t type, + const char *name) +{ + if (type == GS_TYPE_INFER) { + if (!strcmp(name, "bridges")) + type = GS_TYPE_BRIDGE; + else if (!strcmp(name, "restricted")) + type = GS_TYPE_RESTRICTED; + else + type = GS_TYPE_NORMAL; } + return type; +} - if (node) { - int is_dir = node_is_dir(node); - if (options->UseBridges && node_is_a_configured_bridge(node)) - is_dir = 1; - if (e->is_dir_cache != is_dir) { - e->is_dir_cache = is_dir; - changed = 1; - } +/** + * Allocate and return a new guard_selection_t, with the name <b>name</b>. + */ +STATIC guard_selection_t * +guard_selection_new(const char *name, + guard_selection_type_t type) +{ + guard_selection_t *gs; + + type = guard_selection_infer_type(type, name); + + gs = tor_malloc_zero(sizeof(*gs)); + gs->name = tor_strdup(name); + gs->type = type; + gs->sampled_entry_guards = smartlist_new(); + gs->confirmed_entry_guards = smartlist_new(); + gs->primary_entry_guards = smartlist_new(); + + return gs; +} + +/** + * Return the guard selection called <b>name</b>. If there is none, and + * <b>create_if_absent</b> is true, then create and return it. If there + * is none, and <b>create_if_absent</b> is false, then return NULL. + */ +STATIC guard_selection_t * +get_guard_selection_by_name(const char *name, + guard_selection_type_t type, + int create_if_absent) +{ + if (!guard_contexts) { + guard_contexts = smartlist_new(); } + SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) { + if (!strcmp(gs->name, name)) + return gs; + } SMARTLIST_FOREACH_END(gs); - return changed; + if (! create_if_absent) + return NULL; + + log_debug(LD_GUARD, "Creating a guard selection called %s", name); + guard_selection_t *new_selection = guard_selection_new(name, type); + smartlist_add(guard_contexts, new_selection); + + return new_selection; } -/** Return true iff enough time has passed since we last tried to connect - * to the unreachable guard <b>e</b> that we're willing to try again. */ -STATIC int -entry_is_time_to_retry(const entry_guard_t *e, time_t now) +/** + * Allocate the first guard context that we're planning to use, + * and make it the current context. + */ +static void +create_initial_guard_context(void) { - struct guard_retry_period_s { - time_t period_duration; - time_t interval_during_period; - }; + tor_assert(! curr_guard_context); + if (!guard_contexts) { + guard_contexts = smartlist_new(); + } + guard_selection_type_t type = GS_TYPE_INFER; + const char *name = choose_guard_selection( + get_options(), + networkstatus_get_live_consensus(approx_time()), + NULL, + &type); + tor_assert(name); // "name" can only be NULL if we had an old name. + tor_assert(type != GS_TYPE_INFER); + log_notice(LD_GUARD, "Starting with guard context \"%s\"", name); + curr_guard_context = get_guard_selection_by_name(name, type, 1); +} + +/** Get current default guard_selection_t, creating it if necessary */ +guard_selection_t * +get_guard_selection_info(void) +{ + if (!curr_guard_context) { + create_initial_guard_context(); + } - struct guard_retry_period_s periods[] = { - { 6*60*60, 60*60 }, /* For first 6 hrs., retry hourly; */ - { 3*24*60*60, 4*60*60 }, /* Then retry every 4 hrs. until the - 3-day mark; */ - { 7*24*60*60, 18*60*60 }, /* After 3 days, retry every 18 hours until - 1 week mark. */ - { TIME_MAX, 36*60*60 } /* After 1 week, retry every 36 hours. */ - }; + return curr_guard_context; +} - time_t ith_deadline_for_retry; - time_t unreachable_for; - unsigned i; +/** Return a statically allocated human-readable description of <b>guard</b> + */ +const char * +entry_guard_describe(const entry_guard_t *guard) +{ + static char buf[256]; + tor_snprintf(buf, sizeof(buf), + "%s ($%s)", + strlen(guard->nickname) ? guard->nickname : "[bridge]", + hex_str(guard->identity, DIGEST_LEN)); + return buf; +} - if (e->last_attempted < e->unreachable_since) - return 1; +/** Return <b>guard</b>'s 20-byte RSA identity digest */ +const char * +entry_guard_get_rsa_id_digest(const entry_guard_t *guard) +{ + return guard->identity; +} - unreachable_for = now - e->unreachable_since; +/** Return the pathbias state associated with <b>guard</b>. */ +guard_pathbias_t * +entry_guard_get_pathbias_state(entry_guard_t *guard) +{ + return &guard->pb; +} - for (i = 0; i < ARRAY_LENGTH(periods); i++) { - if (unreachable_for <= periods[i].period_duration) { - ith_deadline_for_retry = e->last_attempted + - periods[i].interval_during_period; +HANDLE_IMPL(entry_guard, entry_guard_t, ATTR_UNUSED STATIC) - return (now > ith_deadline_for_retry); - } - } - return 0; +/** Return an interval betweeen 'now' and 'max_backdate' seconds in the past, + * 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); + + time_t earliest = now - max_backdate; + time_t latest = now; + if (earliest <= 0) + earliest = 1; + if (latest <= earliest) + latest = earliest + 1; + + return crypto_rand_time_range(earliest, latest); } -/** Return the node corresponding to <b>e</b>, if <b>e</b> is - * working well enough that we are willing to use it as an entry - * right now. (Else return NULL.) In particular, it must be - * - Listed as either up or never yet contacted; - * - Present in the routerlist; - * - Listed as 'stable' or 'fast' by the current dirserver consensus, - * if demanded by <b>need_uptime</b> or <b>need_capacity</b> - * (unless it's a configured EntryNode); - * - Allowed by our current ReachableORAddresses config option; and - * - Currently thought to be reachable by us (unless <b>assume_reachable</b> - * is true). - * - * If the answer is no, set *<b>msg</b> to an explanation of why. +/** + * @name parameters for networkstatus algorithm * - * If need_descriptor is true, only return the node if we currently have - * a descriptor (routerinfo or microdesc) for it. + * These parameters are taken from the consensus; some are overrideable in + * the torrc. + */ +/**@{*/ +/** + * We never let our sampled guard set grow larger than this fraction + * of the guards on the network. */ -STATIC const node_t * -entry_is_live(const entry_guard_t *e, entry_is_live_flags_t flags, - const char **msg) +STATIC double +get_max_sample_threshold(void) { - const node_t *node; - const or_options_t *options = get_options(); - int need_uptime = (flags & ENTRY_NEED_UPTIME) != 0; - int need_capacity = (flags & ENTRY_NEED_CAPACITY) != 0; - const int assume_reachable = (flags & ENTRY_ASSUME_REACHABLE) != 0; - const int need_descriptor = (flags & ENTRY_NEED_DESCRIPTOR) != 0; - - tor_assert(msg); + int32_t pct = + networkstatus_get_param(NULL, "guard-max-sample-threshold-percent", + DFLT_MAX_SAMPLE_THRESHOLD_PERCENT, + 1, 100); + return pct / 100.0; +} +/** + * We never let our sampled guard set grow larger than this number. + */ +STATIC int +get_max_sample_size_absolute(void) +{ + return (int) networkstatus_get_param(NULL, "guard-max-sample-size", + DFLT_MAX_SAMPLE_SIZE, + 1, INT32_MAX); +} +/** + * We always try to make our sample contain at least this many guards. + */ +STATIC int +get_min_filtered_sample_size(void) +{ + return networkstatus_get_param(NULL, "guard-min-filtered-sample-size", + DFLT_MIN_FILTERED_SAMPLE_SIZE, + 1, INT32_MAX); +} +/** + * If a guard is unlisted for this many days in a row, we remove it. + */ +STATIC int +get_remove_unlisted_guards_after_days(void) +{ + return networkstatus_get_param(NULL, + "guard-remove-unlisted-guards-after-days", + DFLT_REMOVE_UNLISTED_GUARDS_AFTER_DAYS, + 1, 365*10); +} +/** + * We remove unconfirmed guards from the sample after this many days, + * regardless of whether they are listed or unlisted. + */ +STATIC int +get_guard_lifetime(void) +{ + if (get_options()->GuardLifetime >= 86400) + return get_options()->GuardLifetime; + int32_t days; + days = networkstatus_get_param(NULL, + "guard-lifetime-days", + DFLT_GUARD_LIFETIME_DAYS, 1, 365*10); + return days * 86400; +} +/** + * We remove confirmed guards from the sample if they were sampled + * GUARD_LIFETIME_DAYS ago and confirmed this many days ago. + */ +STATIC int +get_guard_confirmed_min_lifetime(void) +{ + if (get_options()->GuardLifetime >= 86400) + return get_options()->GuardLifetime; + int32_t days; + days = networkstatus_get_param(NULL, "guard-confirmed-min-lifetime-days", + DFLT_GUARD_CONFIRMED_MIN_LIFETIME_DAYS, + 1, 365*10); + return days * 86400; +} +/** + * How many guards do we try to keep on our primary guard list? + */ +STATIC int +get_n_primary_guards(void) +{ + const int n = get_options()->NumEntryGuards; + const int n_dir = get_options()->NumDirectoryGuards; + if (n > 5) { + return MAX(n_dir, n + n / 2); + } else if (n >= 1) { + return MAX(n_dir, n * 2); + } - if (e->path_bias_disabled) { - *msg = "path-biased"; - return NULL; + return networkstatus_get_param(NULL, + "guard-n-primary-guards", + DFLT_N_PRIMARY_GUARDS, 1, INT32_MAX); +} +/** + * Return the number of the live primary guards we should look at when + * making a circuit. + */ +STATIC int +get_n_primary_guards_to_use(guard_usage_t usage) +{ + int configured; + const char *param_name; + int param_default; + if (usage == GUARD_USAGE_DIRGUARD) { + configured = get_options()->NumDirectoryGuards; + param_name = "guard-n-primary-dir-guards-to-use"; + param_default = DFLT_N_PRIMARY_DIR_GUARDS_TO_USE; + } else { + configured = get_options()->NumEntryGuards; + param_name = "guard-n-primary-guards-to-use"; + param_default = DFLT_N_PRIMARY_GUARDS_TO_USE; } - if (e->bad_since) { - *msg = "bad"; - return NULL; + if (configured >= 1) { + return configured; } - /* no good if it's unreachable, unless assume_unreachable or can_retry. */ - if (!assume_reachable && !e->can_retry && - e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) { - *msg = "unreachable"; - return NULL; + return networkstatus_get_param(NULL, + param_name, param_default, 1, INT32_MAX); +} +/** + * If we haven't successfully built or used a circuit in this long, then + * consider that the internet is probably down. + */ +STATIC int +get_internet_likely_down_interval(void) +{ + return networkstatus_get_param(NULL, "guard-internet-likely-down-interval", + DFLT_INTERNET_LIKELY_DOWN_INTERVAL, + 1, INT32_MAX); +} +/** + * If we're trying to connect to a nonprimary guard for at least this + * many seconds, and we haven't gotten the connection to work, we will treat + * lower-priority guards as usable. + */ +STATIC int +get_nonprimary_guard_connect_timeout(void) +{ + return networkstatus_get_param(NULL, + "guard-nonprimary-guard-connect-timeout", + DFLT_NONPRIMARY_GUARD_CONNECT_TIMEOUT, + 1, INT32_MAX); +} +/** + * If a circuit has been sitting around in 'waiting for better guard' state + * for at least this long, we'll expire it. + */ +STATIC int +get_nonprimary_guard_idle_timeout(void) +{ + return networkstatus_get_param(NULL, + "guard-nonprimary-guard-idle-timeout", + DFLT_NONPRIMARY_GUARD_IDLE_TIMEOUT, + 1, INT32_MAX); +} +/** + * If our configuration retains fewer than this fraction of guards from the + * torrc, we are in a restricted setting. + */ +STATIC double +get_meaningful_restriction_threshold(void) +{ + int32_t pct = networkstatus_get_param(NULL, + "guard-meaningful-restriction-percent", + DFLT_MEANINGFUL_RESTRICTION_PERCENT, + 1, INT32_MAX); + return pct / 100.0; +} +/** + * If our configuration retains fewer than this fraction of guards from the + * torrc, we are in an extremely restricted setting, and should warn. + */ +STATIC double +get_extreme_restriction_threshold(void) +{ + int32_t pct = networkstatus_get_param(NULL, + "guard-extreme-restriction-percent", + DFLT_EXTREME_RESTRICTION_PERCENT, + 1, INT32_MAX); + return pct / 100.0; +} + +/* Mark <b>guard</b> as maybe reachable again. */ +static void +mark_guard_maybe_reachable(entry_guard_t *guard) +{ + if (guard->is_reachable != GUARD_REACHABLE_NO) { + return; } - node = node_get_by_id(e->identity); - if (!node) { - *msg = "no node info"; - return NULL; + + /* 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; +} + +/** + * 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) +{ + tor_assert(gs); + + if (!gs->primary_guards_up_to_date) + entry_guards_update_primary(gs); + + SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) { + mark_guard_maybe_reachable(guard); + } SMARTLIST_FOREACH_END(guard); +} + +/* Called when we exhaust all guards in our sampled set: Marks all guards as + maybe-reachable so that we 'll try them again. */ +static void +mark_all_guards_maybe_reachable(guard_selection_t *gs) +{ + tor_assert(gs); + + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + mark_guard_maybe_reachable(guard); + } SMARTLIST_FOREACH_END(guard); +} + +/**@}*/ + +/** + * Given our options and our list of nodes, return the name of the + * guard selection that we should use. Return NULL for "use the + * same selection you were using before. + */ +STATIC const char * +choose_guard_selection(const or_options_t *options, + const networkstatus_t *live_ns, + const guard_selection_t *old_selection, + guard_selection_type_t *type_out) +{ + tor_assert(options); + tor_assert(type_out); + + if (options->UseBridges) { + *type_out = GS_TYPE_BRIDGE; + return "bridges"; } - if (need_descriptor && !node_has_descriptor(node)) { - *msg = "no descriptor"; - return NULL; + + if (! live_ns) { + /* without a networkstatus, we can't tell any more than that. */ + *type_out = GS_TYPE_NORMAL; + return "default"; } - if (get_options()->UseBridges) { - if (node_get_purpose(node) != ROUTER_PURPOSE_BRIDGE) { - *msg = "not a bridge"; - return NULL; - } - if (!node_is_a_configured_bridge(node)) { - *msg = "not a configured bridge"; - return NULL; - } - } else { /* !get_options()->UseBridges */ - if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) { - *msg = "not general-purpose"; - return NULL; + + const smartlist_t *nodes = nodelist_get_list(); + int n_guards = 0, n_passing_filter = 0; + SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) { + if (node_is_possible_guard(node)) { + ++n_guards; + if (node_passes_guard_filter(options, node)) { + ++n_passing_filter; + } } + } SMARTLIST_FOREACH_END(node); + + /* We use separate 'high' and 'low' thresholds here to prevent flapping + * back and forth */ + const int meaningful_threshold_high = + (int)(n_guards * get_meaningful_restriction_threshold() * 1.05); + const int meaningful_threshold_mid = + (int)(n_guards * get_meaningful_restriction_threshold()); + const int meaningful_threshold_low = + (int)(n_guards * get_meaningful_restriction_threshold() * .95); + const int extreme_threshold = + (int)(n_guards * get_extreme_restriction_threshold()); + + /* + If we have no previous selection, then we're "restricted" iff we are + below the meaningful restriction threshold. That's easy enough. + + But if we _do_ have a previous selection, we make it a little + "sticky": we only move from "restricted" to "default" when we find + that we're above the threshold plus 5%, and we only move from + "default" to "restricted" when we're below the threshold minus 5%. + That should prevent us from flapping back and forth if we happen to + be hovering very close to the default. + + The extreme threshold is for warning only. + */ + + static int have_warned_extreme_threshold = 0; + if (n_guards && + n_passing_filter < extreme_threshold && + ! have_warned_extreme_threshold) { + have_warned_extreme_threshold = 1; + const double exclude_frac = + (n_guards - n_passing_filter) / (double)n_guards; + log_warn(LD_GUARD, "Your configuration excludes %d%% of all possible " + "guards. That's likely to make you stand out from the " + "rest of the world.", (int)(exclude_frac * 100)); } - if (routerset_contains_node(options->EntryNodes, node)) { - /* they asked for it, they get it */ - need_uptime = need_capacity = 0; - } - if (node_is_unreliable(node, need_uptime, need_capacity, 0)) { - *msg = "not fast/stable"; - return NULL; + + /* Easy case: no previous selection. Just check if we are in restricted or + normal guard selection. */ + if (old_selection == NULL) { + if (n_passing_filter >= meaningful_threshold_mid) { + *type_out = GS_TYPE_NORMAL; + return "default"; + } else { + *type_out = GS_TYPE_RESTRICTED; + return "restricted"; + } } - if (!fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION, 0)) { - *msg = "unreachable by config"; - return NULL; + + /* Trickier case: we do have a previous guard selection context. */ + tor_assert(old_selection); + + /* Use high and low thresholds to decide guard selection, and if we fall in + the middle then keep the current guard selection context. */ + if (n_passing_filter >= meaningful_threshold_high) { + *type_out = GS_TYPE_NORMAL; + return "default"; + } else if (n_passing_filter < meaningful_threshold_low) { + *type_out = GS_TYPE_RESTRICTED; + return "restricted"; + } else { + /* we are in the middle: maintain previous guard selection */ + *type_out = old_selection->type; + return old_selection->name; } - return node; } -/** Return the number of entry guards that we think are usable. */ +/** + * Check whether we should switch from our current guard selection to a + * different one. If so, switch and return 1. Return 0 otherwise. + * + * On a 1 return, the caller should mark all currently live circuits unusable + * for new streams, by calling circuit_mark_all_unused_circs() and + * circuit_mark_all_dirty_circs_as_unusable(). + */ int -num_live_entry_guards(int for_directory) +update_guard_selection_choice(const or_options_t *options) { - int n = 0; - const char *msg; - /* Set the entry node attributes we are interested in. */ - entry_is_live_flags_t entry_flags = ENTRY_NEED_CAPACITY; - if (!for_directory) { - entry_flags |= ENTRY_NEED_DESCRIPTOR; + if (!curr_guard_context) { + create_initial_guard_context(); + return 1; } - if (! entry_guards) - return 0; - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) { - if (for_directory && !entry->is_dir_cache) - continue; - if (entry_is_live(entry, entry_flags, &msg)) - ++n; - } SMARTLIST_FOREACH_END(entry); - return n; + guard_selection_type_t type = GS_TYPE_INFER; + const char *new_name = choose_guard_selection( + options, + networkstatus_get_live_consensus(approx_time()), + curr_guard_context, + &type); + tor_assert(new_name); + tor_assert(type != GS_TYPE_INFER); + + const char *cur_name = curr_guard_context->name; + if (! strcmp(cur_name, new_name)) { + log_debug(LD_GUARD, + "Staying with guard context \"%s\" (no change)", new_name); + return 0; // No change + } + + log_notice(LD_GUARD, "Switching to guard context \"%s\" (was using \"%s\")", + new_name, cur_name); + guard_selection_t *new_guard_context; + new_guard_context = get_guard_selection_by_name(new_name, type, 1); + tor_assert(new_guard_context); + tor_assert(new_guard_context != curr_guard_context); + curr_guard_context = new_guard_context; + + return 1; } -/** If <b>digest</b> matches the identity of any node in the - * entry_guards list, return that node. Else return NULL. */ -entry_guard_t * -entry_guard_get_by_id_digest(const char *digest) +/** + * 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(const node_t *node) { - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, - if (tor_memeq(digest, entry->identity, DIGEST_LEN)) - return entry; - ); + /* The "GUARDS" set is all nodes in the nodelist for which this predicate + * holds. */ + + tor_assert(node); + return (node->is_possible_guard && + node->is_stable && + node->is_fast && + node->is_valid && + node_is_dir(node) && + !router_digest_is_me(node->identity)); +} + +/** + * 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; } -/** Dump a description of our list of entry guards to the log at level - * <b>severity</b>. */ -static void -log_entry_guards(int severity) -{ - smartlist_t *elements = smartlist_new(); - char *s; - - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) - { - const char *msg = NULL; - if (entry_is_live(e, ENTRY_NEED_CAPACITY, &msg)) - smartlist_add_asprintf(elements, "%s [%s] (up %s)", - e->nickname, - hex_str(e->identity, DIGEST_LEN), - e->made_contact ? "made-contact" : "never-contacted"); - else - smartlist_add_asprintf(elements, "%s [%s] (%s, %s)", - e->nickname, - hex_str(e->identity, DIGEST_LEN), - msg, - e->made_contact ? "made-contact" : "never-contacted"); - } - SMARTLIST_FOREACH_END(e); +/** If <b>gs</b> contains a sampled entry guard matching <b>bridge</b>, + * return that guard. Otherwise return NULL. */ +static entry_guard_t * +get_sampled_guard_for_bridge(guard_selection_t *gs, + const bridge_info_t *bridge) +{ + const uint8_t *id = bridge_get_rsa_id_digest(bridge); + const tor_addr_port_t *addrport = bridge_get_addr_port(bridge); + entry_guard_t *guard; + if (BUG(!addrport)) + return NULL; // LCOV_EXCL_LINE + guard = get_sampled_guard_by_bridge_addr(gs, addrport); + if (! guard || (id && tor_memneq(id, guard->identity, DIGEST_LEN))) + return NULL; + else + return guard; +} - s = smartlist_join_strings(elements, ",", 0, NULL); - SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp)); - smartlist_free(elements); - log_fn(severity,LD_CIRC,"%s",s); - tor_free(s); +/** If we know a bridge_info_t matching <b>guard</b>, return that + * bridge. Otherwise return NULL. */ +static bridge_info_t * +get_bridge_info_for_guard(const entry_guard_t *guard) +{ + const uint8_t *identity = NULL; + if (! tor_digest_is_zero(guard->identity)) { + identity = (const uint8_t *)guard->identity; + } + if (BUG(guard->bridge_addr == NULL)) + return NULL; + + return get_configured_bridge_by_exact_addr_port_digest( + &guard->bridge_addr->addr, + guard->bridge_addr->port, + (const char*)identity); } -/** Called when one or more guards that we would previously have used for some - * purpose are no longer in use because a higher-priority guard has become - * usable again. */ -static void -control_event_guard_deferred(void) -{ - /* XXXX We don't actually have a good way to figure out _how many_ entries - * are live for some purpose. We need an entry_is_even_slightly_live() - * function for this to work right. NumEntryGuards isn't reliable: if we - * need guards with weird properties, we can have more than that number - * live. - **/ -#if 0 - int n = 0; - const char *msg; - const or_options_t *options = get_options(); - if (!entry_guards) - return; - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, - { - if (entry_is_live(entry, 0, 1, 0, &msg)) { - if (n++ == options->NumEntryGuards) { - control_event_guard(entry->nickname, entry->identity, "DEFERRED"); - return; - } - } - }); -#endif +/** + * 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; } -/** Largest amount that we'll backdate chosen_on_date */ -#define CHOSEN_ON_DATE_SLOP (30*86400) +/** + * 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>. + */ +STATIC entry_guard_t * +entry_guard_add_to_sample(guard_selection_t *gs, + const node_t *node) +{ + log_info(LD_GUARD, "Adding %s as to the entry guard sample set.", + node_describe(node)); -/** Add a new (preferably stable and fast) router to our - * entry_guards list. Return a pointer to the router if we succeed, - * or NULL if we can't find any more suitable entries. - * - * If <b>chosen</b> is defined, use that one, and if it's not - * already in our entry_guards list, put it at the *beginning*. - * Else, put the one we pick at the end of the list. */ -STATIC const node_t * -add_an_entry_guard(const node_t *chosen, int reset_status, int prepend, - int for_discovery, int for_directory) + /* make sure that the guard is not already sampled. */ + if (BUG(have_sampled_guard_with_id(gs, (const uint8_t*)node->identity))) + return NULL; // LCOV_EXCL_LINE + + return entry_guard_add_to_sample_impl(gs, + (const uint8_t*)node->identity, + node_get_nickname(node), + NULL); +} + +/** + * Backend: adds a new sampled guard to <b>gs</b>, with given identity, + * nickname, and ORPort. rsa_id_digest and bridge_addrport are optional, but + * we need one of them. nickname is optional. The caller is responsible for + * maintaining the size limit of the SAMPLED_GUARDS set. + */ +static entry_guard_t * +entry_guard_add_to_sample_impl(guard_selection_t *gs, + const uint8_t *rsa_id_digest, + const char *nickname, + const tor_addr_port_t *bridge_addrport) +{ + const int GUARD_LIFETIME = get_guard_lifetime(); + tor_assert(gs); + + // XXXX #20827 take ed25519 identity here too. + + /* Make sure we can actually identify the guard. */ + if (BUG(!rsa_id_digest && !bridge_addrport)) + return NULL; // LCOV_EXCL_LINE + + entry_guard_t *guard = tor_malloc_zero(sizeof(entry_guard_t)); + + /* persistent fields */ + guard->is_persistent = (rsa_id_digest != NULL); + guard->selection_name = tor_strdup(gs->name); + if (rsa_id_digest) + memcpy(guard->identity, rsa_id_digest, DIGEST_LEN); + if (nickname) + strlcpy(guard->nickname, nickname, sizeof(guard->nickname)); + 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; + if (bridge_addrport) + guard->bridge_addr = tor_memdup(bridge_addrport, sizeof(*bridge_addrport)); + + smartlist_add(gs->sampled_entry_guards, guard); + guard->in_selection = gs; + entry_guard_set_filtered_flags(get_options(), gs, guard); + entry_guards_changed_for_guard_selection(gs); + return guard; +} + +/** + * Add an entry guard to the "bridges" guard selection sample, with + * information taken from <b>bridge</b>. Return that entry guard. + */ +static entry_guard_t * +entry_guard_add_bridge_to_sample(guard_selection_t *gs, + const bridge_info_t *bridge) { - const node_t *node; - entry_guard_t *entry; - - if (chosen) { - node = chosen; - entry = entry_guard_get_by_id_digest(node->identity); - if (entry) { - if (reset_status) { - entry->bad_since = 0; - entry->can_retry = 1; - } - entry->is_dir_cache = node_is_dir(node); - if (get_options()->UseBridges && node_is_a_configured_bridge(node)) - entry->is_dir_cache = 1; + const uint8_t *id_digest = bridge_get_rsa_id_digest(bridge); + const tor_addr_port_t *addrport = bridge_get_addr_port(bridge); - return NULL; - } - } else if (!for_directory) { - node = choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL, NULL); - if (!node) - return NULL; - } else { - const routerstatus_t *rs; - rs = router_pick_directory_server(MICRODESC_DIRINFO|V3_DIRINFO, - PDS_FOR_GUARD); - if (!rs) - return NULL; - node = node_get_by_id(rs->identity_digest); - if (!node) - return NULL; - } - if (node->using_as_guard) + tor_assert(addrport); + + /* make sure that the guard is not already sampled. */ + if (BUG(get_sampled_guard_for_bridge(gs, bridge))) + return NULL; // LCOV_EXCL_LINE + + return entry_guard_add_to_sample_impl(gs, id_digest, NULL, addrport); +} + +/** + * Return the entry_guard_t in <b>gs</b> whose address is <b>addrport</b>, + * or NULL if none exists. +*/ +static entry_guard_t * +get_sampled_guard_by_bridge_addr(guard_selection_t *gs, + const tor_addr_port_t *addrport) +{ + if (! gs) return NULL; - if (entry_guard_get_by_id_digest(node->identity) != NULL) { - log_info(LD_CIRC, "I was about to add a duplicate entry guard."); - /* This can happen if we choose a guard, then the node goes away, then - * comes back. */ - ((node_t*) node)->using_as_guard = 1; + if (BUG(!addrport)) return NULL; + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, g) { + if (g->bridge_addr && tor_addr_port_eq(addrport, g->bridge_addr)) + return g; + } SMARTLIST_FOREACH_END(g); + return NULL; +} + +/** Update the guard subsystem's knowledge of the identity of the bridge + * at <b>addrport</b>. Idempotent. + */ +void +entry_guard_learned_bridge_identity(const tor_addr_port_t *addrport, + const uint8_t *rsa_id_digest) +{ + guard_selection_t *gs = get_guard_selection_by_name("bridges", + GS_TYPE_BRIDGE, + 0); + if (!gs) + return; + + entry_guard_t *g = get_sampled_guard_by_bridge_addr(gs, addrport); + if (!g) + return; + + int make_persistent = 0; + + if (tor_digest_is_zero(g->identity)) { + memcpy(g->identity, rsa_id_digest, DIGEST_LEN); + make_persistent = 1; + } else if (tor_memeq(g->identity, rsa_id_digest, DIGEST_LEN)) { + /* Nothing to see here; we learned something we already knew. */ + if (BUG(! g->is_persistent)) + make_persistent = 1; + } else { + char old_id[HEX_DIGEST_LEN+1]; + base16_encode(old_id, sizeof(old_id), g->identity, sizeof(g->identity)); + log_warn(LD_BUG, "We 'learned' an identity %s for a bridge at %s:%d, but " + "we already knew a different one (%s). Ignoring the new info as " + "possibly bogus.", + hex_str((const char *)rsa_id_digest, DIGEST_LEN), + fmt_and_decorate_addr(&addrport->addr), addrport->port, + old_id); + return; // redundant, but let's be clear: we're not making this persistent. } - entry = tor_malloc_zero(sizeof(entry_guard_t)); - log_info(LD_CIRC, "Chose %s as new entry guard.", - node_describe(node)); - strlcpy(entry->nickname, node_get_nickname(node), sizeof(entry->nickname)); - memcpy(entry->identity, node->identity, DIGEST_LEN); - entry->is_dir_cache = node_is_dir(node); - if (get_options()->UseBridges && node_is_a_configured_bridge(node)) - entry->is_dir_cache = 1; - - /* Choose expiry time smudged over the past month. The goal here - * is to a) spread out when Tor clients rotate their guards, so they - * don't all select them on the same day, and b) avoid leaving a - * precise timestamp in the state file about when we first picked - * this guard. For details, see the Jan 2010 or-dev thread. */ - time_t now = time(NULL); - entry->chosen_on_date = crypto_rand_time_range(now - 3600*24*30, now); - entry->chosen_by_version = tor_strdup(VERSION); - - /* Are we picking this guard because all of our current guards are - * down so we need another one (for_discovery is 1), or because we - * decided we need more variety in our guard list (for_discovery is 0)? - * - * Currently we hack this behavior into place by setting "made_contact" - * for guards of the latter variety, so we'll be willing to use any of - * them right off the bat. - */ - if (!for_discovery) - entry->made_contact = 1; - ((node_t*)node)->using_as_guard = 1; - if (prepend) - smartlist_insert(entry_guards, 0, entry); - else - smartlist_add(entry_guards, entry); - control_event_guard(entry->nickname, entry->identity, "NEW"); - control_event_guard_deferred(); - log_entry_guards(LOG_INFO); - return node; + if (make_persistent) { + g->is_persistent = 1; + entry_guards_changed_for_guard_selection(gs); + } } -/** 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. */ +/** + * 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"). + * + * If a restriction is provided in <b>rst</b>, do not count any guards that + * violate it. + */ STATIC int -decide_num_guards(const or_options_t *options, int for_directory) +num_reachable_filtered_guards(guard_selection_t *gs, + const entry_guard_restriction_t *rst) { - 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; + int n_reachable_filtered_guards = 0; + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + entry_guard_consider_retry(guard); + if (! entry_guard_obeys_restriction(guard, rst)) + continue; + if (guard->is_usable_filtered_guard) + ++n_reachable_filtered_guards; + } SMARTLIST_FOREACH_END(guard); + return n_reachable_filtered_guards; +} - /* 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); +/** Return the actual maximum size for the sample in <b>gs</b>, + * given that we know about <b>n_guards</b> total. */ +static int +get_max_sample_size(guard_selection_t *gs, + int n_guards) +{ + const int using_bridges = (gs->type == GS_TYPE_BRIDGE); + const int min_sample = get_min_filtered_sample_size(); + + /* If we are in bridge mode, expand our sample set as needed without worrying + * about max size. We should respect the user's wishes to use many bridges if + * that's what they have specified in their configuration file. */ + if (using_bridges) + return INT_MAX; + + const int max_sample_by_pct = (int)(n_guards * get_max_sample_threshold()); + const int max_sample_absolute = get_max_sample_size_absolute(); + const int max_sample = MIN(max_sample_by_pct, max_sample_absolute); + if (max_sample < min_sample) + return min_sample; + else + return max_sample; } -/** If the use of entry guards is configured, choose more entry guards - * until we have enough in the list. */ -static void -pick_entry_guards(const or_options_t *options, int for_directory) -{ - int changed = 0; - const int num_needed = decide_num_guards(options, for_directory); +/** + * Return a smartlist of the all the guards that are not currently + * members of the sample (GUARDS - SAMPLED_GUARDS). The elements of + * this list are node_t pointers in the non-bridge case, and + * bridge_info_t pointers in the bridge case. Set *<b>n_guards_out/b> + * to the number of guards that we found in GUARDS, including those + * that were already sampled. + */ +static smartlist_t * +get_eligible_guards(const or_options_t *options, + guard_selection_t *gs, + int *n_guards_out) +{ + /* Construct eligible_guards as GUARDS - SAMPLED_GUARDS */ + smartlist_t *eligible_guards = smartlist_new(); + int n_guards = 0; // total size of "GUARDS" + + if (gs->type == GS_TYPE_BRIDGE) { + const smartlist_t *bridges = bridge_list_get(); + SMARTLIST_FOREACH_BEGIN(bridges, bridge_info_t *, bridge) { + ++n_guards; + if (NULL != get_sampled_guard_for_bridge(gs, bridge)) { + continue; + } + smartlist_add(eligible_guards, bridge); + } SMARTLIST_FOREACH_END(bridge); + } else { + const smartlist_t *nodes = nodelist_get_list(); + const int n_sampled = smartlist_len(gs->sampled_entry_guards); + + /* 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, const node_t *, node) { + if (! node_is_possible_guard(node)) + continue; + if (gs->type == GS_TYPE_RESTRICTED) { + /* In restricted mode, we apply the filter BEFORE sampling, so + * that we are sampling from the nodes that we might actually + * select. If we sampled first, we might wind up with a sample + * that didn't include any EntryNodes at all. */ + if (! node_passes_guard_filter(options, node)) + continue; + } + ++n_guards; + if (digestset_contains(sampled_guard_ids, node->identity)) + continue; + smartlist_add(eligible_guards, (node_t*)node); + } SMARTLIST_FOREACH_END(node); - tor_assert(entry_guards); + /* Now we can free that bloom filter. */ + digestset_free(sampled_guard_ids); + } - while (num_live_entry_guards(for_directory) < num_needed) { - if (!add_an_entry_guard(NULL, 0, 0, 0, for_directory)) - break; - changed = 1; + *n_guards_out = n_guards; + return eligible_guards; +} + +/** Helper: given a smartlist of either bridge_info_t (if gs->type is + * GS_TYPE_BRIDGE) or node_t (otherwise), pick one that can be a guard, + * add it as a guard, remove it from the list, and return a new + * entry_guard_t. Return NULL on failure. */ +static entry_guard_t * +select_and_add_guard_item_for_sample(guard_selection_t *gs, + smartlist_t *eligible_guards) +{ + entry_guard_t *added_guard; + if (gs->type == GS_TYPE_BRIDGE) { + const bridge_info_t *bridge = smartlist_choose(eligible_guards); + if (BUG(!bridge)) + return NULL; // LCOV_EXCL_LINE + smartlist_remove(eligible_guards, bridge); + added_guard = entry_guard_add_bridge_to_sample(gs, bridge); + } else { + const node_t *node = + node_sl_choose_by_bandwidth(eligible_guards, WEIGHT_FOR_GUARD); + if (BUG(!node)) + return NULL; // LCOV_EXCL_LINE + smartlist_remove(eligible_guards, node); + added_guard = entry_guard_add_to_sample(gs, node); } - if (changed) - entry_guards_changed(); -} -/** 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) + return added_guard; +} -/** Release all storage held by <b>e</b>. */ -static void -entry_guard_free(entry_guard_t *e) +/** Return true iff we need a consensus to maintain our */ +static int +live_consensus_is_missing(const guard_selection_t *gs) { - if (!e) - return; - tor_free(e->chosen_by_version); - tor_free(e); + tor_assert(gs); + if (gs->type == GS_TYPE_BRIDGE) { + /* We don't update bridges from the consensus; they aren't there. */ + return 0; + } + return networkstatus_get_live_consensus(approx_time()) == NULL; } /** - * Return the minimum lifetime of working entry guard, in seconds, - * as given in the consensus networkstatus. (Plus CHOSEN_ON_DATE_SLOP, - * so that we can do the chosen_on_date randomization while achieving the - * desired minimum lifetime.) + * 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 int32_t -guards_get_lifetime(void) +STATIC entry_guard_t * +entry_guards_expand_sample(guard_selection_t *gs) { + tor_assert(gs); const or_options_t *options = get_options(); -#define DFLT_GUARD_LIFETIME (86400 * 60) /* Two months. */ -#define MIN_GUARD_LIFETIME (86400 * 30) /* One months. */ -#define MAX_GUARD_LIFETIME (86400 * 1826) /* Five years. */ - if (options->GuardLifetime >= 1) { - return CLAMP(MIN_GUARD_LIFETIME, - options->GuardLifetime, - MAX_GUARD_LIFETIME) + CHOSEN_ON_DATE_SLOP; + if (live_consensus_is_missing(gs)) { + log_info(LD_GUARD, "Not expanding the sample guard set; we have " + "no live consensus."); + return NULL; } - return networkstatus_get_param(NULL, "GuardLifetime", - DFLT_GUARD_LIFETIME, - MIN_GUARD_LIFETIME, - MAX_GUARD_LIFETIME) + CHOSEN_ON_DATE_SLOP; -} - -/** Remove any entry guard which was selected by an unknown version of Tor, - * or which was selected by a version of Tor that's known to select - * entry guards badly, or which was selected more 2 months ago. */ -/* XXXX The "obsolete guards" and "chosen long ago guards" things should - * probably be different functions. */ -static int -remove_obsolete_entry_guards(time_t now) -{ - int changed = 0, i; - int32_t guard_lifetime = guards_get_lifetime(); - - for (i = 0; i < smartlist_len(entry_guards); ++i) { - entry_guard_t *entry = smartlist_get(entry_guards, i); - const char *ver = entry->chosen_by_version; - const char *msg = NULL; - tor_version_t v; - int version_is_bad = 0, date_is_bad = 0; - if (!ver) { - msg = "does not say what version of Tor it was selected by"; - version_is_bad = 1; - } else if (tor_version_parse(ver, &v)) { - msg = "does not seem to be from any recognized version of Tor"; - version_is_bad = 1; - } - if (!version_is_bad && entry->chosen_on_date + guard_lifetime < now) { - /* It's been too long since the date listed in our state file. */ - msg = "was selected several months ago"; - date_is_bad = 1; + int n_sampled = smartlist_len(gs->sampled_entry_guards); + entry_guard_t *added_guard = NULL; + int n_usable_filtered_guards = num_reachable_filtered_guards(gs, NULL); + int n_guards = 0; + smartlist_t *eligible_guards = get_eligible_guards(options, gs, &n_guards); + + const int max_sample = get_max_sample_size(gs, n_guards); + const int min_filtered_sample = get_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; } - if (version_is_bad || date_is_bad) { /* we need to drop it */ - char dbuf[HEX_DIGEST_LEN+1]; - tor_assert(msg); - base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN); - log_fn(version_is_bad ? LOG_NOTICE : LOG_INFO, LD_CIRC, - "Entry guard '%s' (%s) %s. (Version=%s.) Replacing it.", - entry->nickname, dbuf, msg, ver?escaped(ver):"none"); - control_event_guard(entry->nickname, entry->identity, "DROPPED"); - entry_guard_free(entry); - smartlist_del_keeporder(entry_guards, i--); - log_entry_guards(LOG_INFO); - changed = 1; + /* 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. */ + added_guard = select_and_add_guard_item_for_sample(gs, eligible_guards); + 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; } - return changed ? 1 : 0; + done: + smartlist_free(eligible_guards); + return added_guard; } -/** Remove all entry guards that have been down or unlisted for so - * long that we don't think they'll come up again. Return 1 if we - * removed any, or 0 if we did nothing. */ -static int -remove_dead_entry_guards(time_t now) -{ - char dbuf[HEX_DIGEST_LEN+1]; - char tbuf[ISO_TIME_LEN+1]; - int i; - int changed = 0; - - for (i = 0; i < smartlist_len(entry_guards); ) { - entry_guard_t *entry = smartlist_get(entry_guards, i); - if (entry->bad_since && - ! entry->path_bias_disabled && - entry->bad_since + ENTRY_GUARD_REMOVE_AFTER < now) { - - base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN); - format_local_iso_time(tbuf, entry->bad_since); - log_info(LD_CIRC, "Entry guard '%s' (%s) has been down or unlisted " - "since %s local time; removing.", - entry->nickname, dbuf, tbuf); - control_event_guard(entry->nickname, entry->identity, "DROPPED"); - entry_guard_free(entry); - smartlist_del_keeporder(entry_guards, i); - log_entry_guards(LOG_INFO); - changed = 1; - } else - ++i; - } - return changed ? 1 : 0; -} - -/** Remove all currently listed entry guards. So new ones will be chosen. */ -void -remove_all_entry_guards(void) +/** + * 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) { - char dbuf[HEX_DIGEST_LEN+1]; + 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); + } + } - while (smartlist_len(entry_guards)) { - entry_guard_t *entry = smartlist_get(entry_guards, 0); - base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN); - log_info(LD_CIRC, "Entry guard '%s' (%s) has been dropped.", - entry->nickname, dbuf); - control_event_guard(entry->nickname, entry->identity, "DROPPED"); - entry_guard_free(entry); - smartlist_del(entry_guards, 0); + if (guard->confirmed_idx >= 0) { + smartlist_remove_keeporder(gs->confirmed_entry_guards, guard); + guard->confirmed_idx = -1; + guard->confirmed_on_date = 0; + } else { + if (BUG(smartlist_contains(gs->confirmed_entry_guards, guard))) { + // LCOV_EXCL_START + smartlist_remove_keeporder(gs->confirmed_entry_guards, guard); + // LCOV_EXCL_STOP + } } - log_entry_guards(LOG_INFO); - entry_guards_changed(); } -/** A new directory or router-status has arrived; update the down/listed - * status of the entry guards. - * - * An entry is 'down' if the directory lists it as nonrunning. - * An entry is 'unlisted' if the directory doesn't include it. - * - * Don't call this on startup; only on a fresh download. Otherwise we'll - * think that things are unlisted. - */ -void -entry_guards_compute_status(const or_options_t *options, time_t now) +/** Return true iff <b>guard</b> is currently "listed" -- that is, it + * appears in the consensus, or as a configured bridge (as + * appropriate) */ +MOCK_IMPL(STATIC int, +entry_guard_is_listed,(guard_selection_t *gs, const entry_guard_t *guard)) { - int changed = 0; - digestmap_t *reasons; + if (gs->type == GS_TYPE_BRIDGE) { + return NULL != get_bridge_info_for_guard(guard); + } else { + const node_t *node = node_get_by_id(guard->identity); + + return node && node_is_possible_guard(node); + } +} - if (! entry_guards) +/** + * 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 = + (get_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. + if (live_consensus_is_missing(gs)) { + log_info(LD_GUARD, "Not updating the sample guard set; we have " + "no live consensus."); return; + } + log_info(LD_GUARD, "Updating sampled guard status based on received " + "consensus."); + + int n_changes = 0; + + /* First: Update listed/unlisted. */ + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + /* XXXX #20827 check ed ID too */ + const int is_listed = entry_guard_is_listed(gs, guard); + + 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)); + } - if (options->EntryNodes) /* reshuffle the entry guard list if needed */ - entry_nodes_should_be_added(); - - reasons = digestmap_new(); - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) - { - const node_t *r = node_get_by_id(entry->identity); - const char *reason = NULL; - if (entry_guard_set_status(entry, r, now, options, &reason)) - changed = 1; - - if (entry->bad_since) - tor_assert(reason); - if (reason) - digestmap_set(reasons, entry->identity, (char*)reason); + /* 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(entry); - - if (remove_dead_entry_guards(now)) - changed = 1; - if (remove_obsolete_entry_guards(now)) - changed = 1; - - if (changed) { - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) { - const char *reason = digestmap_get(reasons, entry->identity); - const char *live_msg = ""; - const node_t *r = entry_is_live(entry, ENTRY_NEED_CAPACITY, &live_msg); - log_info(LD_CIRC, "Summary: Entry %s [%s] is %s, %s%s%s, and %s%s.", - entry->nickname, - hex_str(entry->identity, DIGEST_LEN), - entry->unreachable_since ? "unreachable" : "reachable", - entry->bad_since ? "unusable" : "usable", - reason ? ", ": "", - reason ? reason : "", - r ? "live" : "not live / ", - r ? "" : live_msg); - } SMARTLIST_FOREACH_END(entry); - log_info(LD_CIRC, " (%d/%d entry guards are usable/new)", - num_live_entry_guards(0), smartlist_len(entry_guards)); - log_entry_guards(LOG_INFO); - entry_guards_changed(); + } 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() - get_guard_lifetime(); + const time_t remove_if_confirmed_before = + approx_time() - get_guard_confirmed_min_lifetime(); + + /* Then: remove the ones that have been junk for too long */ + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + int rmv = 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), + get_remove_unlisted_guards_after_days()); + rmv = 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) { + rmv = 1; + log_info(LD_GUARD, "Removing sampled guard %s: it was sampled " + "over %d days ago, but never confirmed.", + entry_guard_describe(guard), + get_guard_lifetime() / 86400); + } else if (guard->confirmed_on_date < remove_if_confirmed_before) { + rmv = 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), + get_guard_lifetime() / 86400, + get_guard_confirmed_min_lifetime() / 86400); + } + } + + if (rmv) { + ++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) { + gs->primary_guards_up_to_date = 0; + entry_guards_update_filtered_sets(gs); + /* We don't need to rebuild the confirmed list right here -- we may have + * removed confirmed guards above, but we can't have added any new + * confirmed guards. + */ + 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, + const node_t *node) +{ + /* NOTE: Make sure that this function stays in sync with + * options_transition_affects_entry_guards */ + if (routerset_contains_node(options->ExcludeNodes, node)) + return 0; - digestmap_free(reasons, NULL); + if (options->EntryNodes && + !routerset_contains_node(options->EntryNodes, node)) + return 0; + + if (!fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION, 0)) + return 0; + + if (node_is_a_configured_bridge(node)) + return 0; + + return 1; } -/** Called when a connection to an OR with the identity digest <b>digest</b> - * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0). - * If the OR is an entry, change that entry's up/down status. - * Return 0 normally, or -1 if we want to tear down the new connection. - * - * If <b>mark_relay_status</b>, also call router_set_status() on this - * relay. - */ -/* XXX We could change succeeded and mark_relay_status into 'int flags'. - * Too many boolean arguments is a recipe for confusion. - */ -int -entry_guard_register_connect_status(const char *digest, int succeeded, - int mark_relay_status, time_t now) +/** Helper: Return true iff <b>bridge</b> passes our configuration + * filter-- if it is a relay that we are configured to be able to + * connect to. */ +static int +bridge_passes_guard_filter(const or_options_t *options, + const bridge_info_t *bridge) { - int changed = 0; - int refuse_conn = 0; - int first_contact = 0; - entry_guard_t *entry = NULL; - int idx = -1; - char buf[HEX_DIGEST_LEN+1]; + tor_assert(bridge); + if (!bridge) + return 0; - if (! entry_guards) + if (routerset_contains_bridge(options->ExcludeNodes, bridge)) return 0; - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) { - tor_assert(e); - if (tor_memeq(e->identity, digest, DIGEST_LEN)) { - entry = e; - idx = e_sl_idx; - break; - } - } SMARTLIST_FOREACH_END(e); + /* Ignore entrynodes */ + const tor_addr_port_t *addrport = bridge_get_addr_port(bridge); - if (!entry) + if (!fascist_firewall_allows_address_addr(&addrport->addr, + addrport->port, + FIREWALL_OR_CONNECTION, + 0, 0)) return 0; - base16_encode(buf, sizeof(buf), entry->identity, DIGEST_LEN); - - if (succeeded) { - if (entry->unreachable_since) { - log_info(LD_CIRC, "Entry guard '%s' (%s) is now reachable again. Good.", - entry->nickname, buf); - entry->can_retry = 0; - entry->unreachable_since = 0; - entry->last_attempted = now; - control_event_guard(entry->nickname, entry->identity, "UP"); - changed = 1; - } - if (!entry->made_contact) { - entry->made_contact = 1; - first_contact = changed = 1; - } - } else { /* ! succeeded */ - if (!entry->made_contact) { - /* We've never connected to this one. */ - log_info(LD_CIRC, - "Connection to never-contacted entry guard '%s' (%s) failed. " - "Removing from the list. %d/%d entry guards usable/new.", - entry->nickname, buf, - num_live_entry_guards(0)-1, smartlist_len(entry_guards)-1); - control_event_guard(entry->nickname, entry->identity, "DROPPED"); - entry_guard_free(entry); - smartlist_del_keeporder(entry_guards, idx); - log_entry_guards(LOG_INFO); - changed = 1; - } else if (!entry->unreachable_since) { - log_info(LD_CIRC, "Unable to connect to entry guard '%s' (%s). " - "Marking as unreachable.", entry->nickname, buf); - entry->unreachable_since = entry->last_attempted = now; - control_event_guard(entry->nickname, entry->identity, "DOWN"); - changed = 1; - entry->can_retry = 0; /* We gave it an early chance; no good. */ - } else { - char tbuf[ISO_TIME_LEN+1]; - format_iso_time(tbuf, entry->unreachable_since); - log_debug(LD_CIRC, "Failed to connect to unreachable entry guard " - "'%s' (%s). It has been unreachable since %s.", - entry->nickname, buf, tbuf); - entry->last_attempted = now; - entry->can_retry = 0; /* We gave it an early chance; no good. */ - } - } + return 1; +} - /* if the caller asked us to, also update the is_running flags for this - * relay */ - if (mark_relay_status) - router_set_status(digest, succeeded); - - if (first_contact) { - /* We've just added a new long-term entry guard. Perhaps the network just - * came back? We should give our earlier entries another try too, - * and close this connection so we don't use it before we've given - * the others a shot. */ - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) { - if (e == entry) - break; - if (e->made_contact) { - const char *msg; - const node_t *r = entry_is_live(e, - ENTRY_NEED_CAPACITY | ENTRY_ASSUME_REACHABLE, - &msg); - if (r && e->unreachable_since) { - refuse_conn = 1; - e->can_retry = 1; - } - } - } SMARTLIST_FOREACH_END(e); - if (refuse_conn) { - log_info(LD_CIRC, - "Connected to new entry guard '%s' (%s). Marking earlier " - "entry guards up. %d/%d entry guards usable/new.", - entry->nickname, buf, - num_live_entry_guards(0), smartlist_len(entry_guards)); - log_entry_guards(LOG_INFO); - changed = 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; + + if (gs->type == GS_TYPE_BRIDGE) { + const bridge_info_t *bridge = get_bridge_info_for_guard(guard); + if (bridge == NULL) + return 0; + return bridge_passes_guard_filter(options, bridge); + } else { + const node_t *node = node_get_by_id(guard->identity); + if (node == NULL) { + // This can happen when currently_listed is true, and we're not updating + // it because we don't have a live consensus. + return 0; } - } - if (changed) - entry_guards_changed(); - return refuse_conn ? -1 : 0; + return node_passes_guard_filter(options, node); + } } -/** When we try to choose an entry guard, should we parse and add - * config's EntryNodes first? */ -static int should_add_entry_nodes = 0; - -/** Called when the value of EntryNodes changes in our configuration. */ -void -entry_nodes_should_be_added(void) +/** Return true iff <b>guard</b> is in the same family as <b>node</b>. + */ +static int +guard_in_node_family(const entry_guard_t *guard, const node_t *node) { - log_info(LD_CIRC, "EntryNodes config option set. Putting configured " - "relays at the front of the entry guard list."); - should_add_entry_nodes = 1; + const node_t *guard_node = node_get_by_id(guard->identity); + if (guard_node) { + return nodes_in_same_family(guard_node, node); + } else { + /* If we don't have a node_t for the guard node, we might have + * a bridge_info_t for it. So let's check to see whether the bridge + * address matches has any family issues. + * + * (Strictly speaking, I believe this check is unnecessary, since we only + * use it to avoid the exit's family when building circuits, and we don't + * build multihop circuits until we have a routerinfo_t for the + * bridge... at which point, we'll also have a node_t for the + * bridge. Nonetheless, it seems wise to include it, in case our + * assumptions change down the road. -nickm.) + */ + if (get_options()->EnforceDistinctSubnets && guard->bridge_addr) { + tor_addr_t node_addr; + node_get_addr(node, &node_addr); + if (addrs_in_same_network_family(&node_addr, + &guard->bridge_addr->addr)) { + return 1; + } + } + return 0; + } } -/** Update the using_as_guard fields of all the nodes. We do this after we - * remove entry guards from the list: This is the only function that clears - * the using_as_guard field. */ -static void -update_node_guard_status(void) +/** + * Return true iff <b>guard</b> obeys the restrictions defined in <b>rst</b>. + * (If <b>rst</b> is NULL, there are no restrictions.) + */ +static int +entry_guard_obeys_restriction(const entry_guard_t *guard, + const entry_guard_restriction_t *rst) { - smartlist_t *nodes = nodelist_get_list(); - SMARTLIST_FOREACH(nodes, node_t *, node, node->using_as_guard = 0); - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) { - node_t *node = node_get_mutable_by_id(entry->identity); - if (node) - node->using_as_guard = 1; - } SMARTLIST_FOREACH_END(entry); + tor_assert(guard); + if (! rst) + return 1; // No restriction? No problem. + + // Only one kind of restriction exists right now: excluding an exit + // ID and all of its family. + const node_t *node = node_get_by_id((const char*)rst->exclude_id); + if (node && guard_in_node_family(guard, node)) + return 0; + + return tor_memneq(guard->identity, rst->exclude_id, DIGEST_LEN); } -/** Adjust the entry guards list so that it only contains entries from - * EntryNodes, adding new entries from EntryNodes to the list as needed. */ -STATIC void -entry_guards_set_from_config(const or_options_t *options) +/** + * 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) { - smartlist_t *entry_nodes, *worse_entry_nodes, *entry_fps; - smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list; - const int numentryguards = decide_num_guards(options, 0); - tor_assert(entry_guards); + unsigned was_filtered = guard->is_filtered_guard; + guard->is_filtered_guard = 0; + guard->is_usable_filtered_guard = 0; - should_add_entry_nodes = 0; + if (entry_guard_passes_filter(options, gs, guard)) { + guard->is_filtered_guard = 1; - if (!options->EntryNodes) { - /* It's possible that a controller set EntryNodes, thus making - * should_add_entry_nodes set, then cleared it again, all before the - * call to choose_random_entry() that triggered us. If so, just return. - */ - return; + 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); - { - char *string = routerset_to_string(options->EntryNodes); - log_info(LD_CIRC,"Adding configured EntryNodes '%s'.", string); - tor_free(string); + if (!bool_eq(was_filtered, guard->is_filtered_guard)) { + /* This guard might now be primary or nonprimary. */ + gs->primary_guards_up_to_date = 0; } +} - entry_nodes = smartlist_new(); - worse_entry_nodes = smartlist_new(); - entry_fps = smartlist_new(); - old_entry_guards_on_list = smartlist_new(); - old_entry_guards_not_on_list = smartlist_new(); +/** + * 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(); - /* Split entry guards into those on the list and those not. */ + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + entry_guard_set_filtered_flags(options, gs, guard); + } SMARTLIST_FOREACH_END(guard); +} - routerset_get_all_nodes(entry_nodes, options->EntryNodes, - options->ExcludeNodes, 0); - SMARTLIST_FOREACH(entry_nodes, const node_t *,node, - smartlist_add(entry_fps, (void*)node->identity)); +/** + * 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. + * + * If a restriction is provided in <b>rst</b>, do not return any guards that + * violate it. + **/ +STATIC entry_guard_t * +sample_reachable_filtered_entry_guards(guard_selection_t *gs, + const entry_guard_restriction_t *rst, + 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; + const unsigned no_update_primary = flags & SAMPLE_NO_UPDATE_PRIMARY; + const unsigned need_descriptor = flags & SAMPLE_EXCLUDE_NO_DESCRIPTOR; + + 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, rst); + + log_info(LD_GUARD, "Trying to sample a reachable guard: We know of %d " + "in the USABLE_FILTERED set.", n_reachable_filtered); + + const int min_filtered_sample = get_min_filtered_sample_size(); + if (n_reachable_filtered < min_filtered_sample) { + log_info(LD_GUARD, " (That isn't enough. Trying to expand the sample.)"); + entry_guards_expand_sample(gs); + } - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, { - if (smartlist_contains_digest(entry_fps, e->identity)) - smartlist_add(old_entry_guards_on_list, e); - else - smartlist_add(old_entry_guards_not_on_list, e); - }); + if (exclude_primary && !gs->primary_guards_up_to_date && !no_update_primary) + entry_guards_update_primary(gs); - /* Remove all currently configured guard nodes, excluded nodes, unreachable - * nodes, or non-Guard nodes from entry_nodes. */ - SMARTLIST_FOREACH_BEGIN(entry_nodes, const node_t *, node) { - if (entry_guard_get_by_id_digest(node->identity)) { - SMARTLIST_DEL_CURRENT(entry_nodes, node); + /* 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 (! entry_guard_obeys_restriction(guard, rst)) continue; - } else if (routerset_contains_node(options->ExcludeNodes, node)) { - SMARTLIST_DEL_CURRENT(entry_nodes, node); + if (! guard->is_usable_filtered_guard) continue; - } else if (!fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION, - 0)) { - SMARTLIST_DEL_CURRENT(entry_nodes, node); + if (exclude_confirmed && guard->confirmed_idx >= 0) continue; - } else if (! node->is_possible_guard) { - smartlist_add(worse_entry_nodes, (node_t*)node); - SMARTLIST_DEL_CURRENT(entry_nodes, node); - } - } SMARTLIST_FOREACH_END(node); + if (exclude_primary && guard->is_primary) + continue; + if (exclude_pending && guard->is_pending) + continue; + if (need_descriptor && !guard_has_descriptor(guard)) + continue; + smartlist_add(reachable_filtered_sample, guard); + } SMARTLIST_FOREACH_END(guard); - /* Now build the new entry_guards list. */ - smartlist_clear(entry_guards); - /* First, the previously configured guards that are in EntryNodes. */ - smartlist_add_all(entry_guards, old_entry_guards_on_list); - /* Next, scramble the rest of EntryNodes, putting the guards first. */ - smartlist_shuffle(entry_nodes); - smartlist_shuffle(worse_entry_nodes); - smartlist_add_all(entry_nodes, worse_entry_nodes); - - /* Next, the rest of EntryNodes */ - SMARTLIST_FOREACH_BEGIN(entry_nodes, const node_t *, node) { - add_an_entry_guard(node, 0, 0, 1, 0); - if (smartlist_len(entry_guards) > numentryguards * 10) - break; - } SMARTLIST_FOREACH_END(node); - log_notice(LD_GENERAL, "%d entries in guards", smartlist_len(entry_guards)); - /* Finally, free the remaining previously configured guards that are not in - * EntryNodes. */ - SMARTLIST_FOREACH(old_entry_guards_not_on_list, entry_guard_t *, e, - entry_guard_free(e)); + log_info(LD_GUARD, " (After filters [%x], we have %d guards to consider.)", + flags, smartlist_len(reachable_filtered_sample)); - update_node_guard_status(); + 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); - smartlist_free(entry_nodes); - smartlist_free(worse_entry_nodes); - smartlist_free(entry_fps); - smartlist_free(old_entry_guards_on_list); - smartlist_free(old_entry_guards_not_on_list); - entry_guards_changed(); + return result; } -/** Return 0 if we're fine adding arbitrary routers out of the - * directory to our entry guard list, or return 1 if we have a - * list already and we must stick to it. +/** + * Helper: compare two entry_guard_t by their confirmed_idx values. + * Used to sort the confirmed list. */ -int -entry_list_is_constrained(const or_options_t *options) +static int +compare_guards_by_confirmed_idx(const void **a_, const void **b_) { - if (options->EntryNodes) + 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; - if (options->UseBridges) - return 1; - return 0; + else + return 0; } -/** Pick a live (up and listed) entry guard from entry_guards. If - * <b>state</b> is non-NULL, this is for a specific circuit -- - * make sure not to pick this circuit's exit or any node in the - * exit's family. If <b>state</b> is NULL, we're looking for a random - * guard (likely a bridge). If <b>dirinfo</b> is not NO_DIRINFO (zero), - * then only select from nodes that know how to answer directory questions - * of that type. */ -const node_t * -choose_random_entry(cpath_build_state_t *state) +/** + * 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) { - return choose_random_entry_impl(state, 0, NO_DIRINFO, NULL); + 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); + } } -/** Pick a live (up and listed) directory guard from entry_guards for - * downloading information of type <b>type</b>. */ -const node_t * -choose_random_dirguard(dirinfo_type_t type) +/** + * 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) { - return choose_random_entry_impl(NULL, 1, type, NULL); + if (BUG(guard->confirmed_on_date && guard->confirmed_idx >= 0)) + return; // LCOV_EXCL_LINE + + if (BUG(smartlist_contains(gs->confirmed_entry_guards, guard))) + return; // LCOV_EXCL_LINE + + const int GUARD_LIFETIME = get_guard_lifetime(); + 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); + + // This confirmed guard might kick something else out of the primary + // guards. + gs->primary_guards_up_to_date = 0; + + entry_guards_changed_for_guard_selection(gs); } -/** Filter <b>all_entry_guards</b> for usable entry guards and put them - * in <b>live_entry_guards</b>. We filter based on whether the node is - * currently alive, and on whether it satisfies the restrictions - * imposed by the other arguments of this function. - * - * We don't place more guards than NumEntryGuards in <b>live_entry_guards</b>. - * - * If <b>chosen_exit</b> is set, it contains the exit node of this - * circuit. Make sure to not use it or its family as an entry guard. - * - * If <b>need_uptime</b> is set, we are looking for a stable entry guard. - * if <b>need_capacity</b> is set, we are looking for a fast entry guard. - * - * The rest of the arguments are the same as in choose_random_entry_impl(). - * - * Return 1 if we should choose a guard right away. Return 0 if we - * should try to add more nodes to our list before deciding on a - * guard. +/** + * Recalculate the list of primary guards (the ones we'd prefer to use) from + * the filtered sample and the confirmed list. */ -STATIC int -populate_live_entry_guards(smartlist_t *live_entry_guards, - const smartlist_t *all_entry_guards, - const node_t *chosen_exit, - dirinfo_type_t dirinfo_type, - int for_directory, - int need_uptime, int need_capacity) +STATIC void +entry_guards_update_primary(guard_selection_t *gs) { - const or_options_t *options = get_options(); - const node_t *node = NULL; - const int num_needed = decide_num_guards(options, for_directory); - smartlist_t *exit_family = smartlist_new(); - int retval = 0; - entry_is_live_flags_t entry_flags = 0; + tor_assert(gs); - (void) dirinfo_type; + // prevent recursion. Recursion is potentially very bad here. + static int running = 0; + tor_assert(!running); + running = 1; - { /* Set the flags we want our entry node to have */ - if (need_uptime) { - entry_flags |= ENTRY_NEED_UPTIME; - } - if (need_capacity) { - entry_flags |= ENTRY_NEED_CAPACITY; - } - if (!for_directory) { - entry_flags |= ENTRY_NEED_DESCRIPTOR; - } - } + const int N_PRIMARY_GUARDS = get_n_primary_guards(); - tor_assert(all_entry_guards); + smartlist_t *new_primary_guards = smartlist_new(); + smartlist_t *old_primary_guards = smartlist_new(); + smartlist_add_all(old_primary_guards, gs->primary_entry_guards); - if (chosen_exit) { - nodelist_add_node_and_family(exit_family, chosen_exit); + /* Set this flag now, to prevent the calls below from recursing. */ + gs->primary_guards_up_to_date = 1; + + /* 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, NULL, + SAMPLE_EXCLUDE_CONFIRMED| + SAMPLE_EXCLUDE_PRIMARY| + SAMPLE_NO_UPDATE_PRIMARY); + if (!guard) + break; + guard->is_primary = 1; + smartlist_add(new_primary_guards, guard); } - SMARTLIST_FOREACH_BEGIN(all_entry_guards, const entry_guard_t *, entry) { - const char *msg; - node = entry_is_live(entry, entry_flags, &msg); - if (!node) - continue; /* down, no point */ - if (for_directory) { - if (!entry->is_dir_cache) - continue; /* We need a directory and didn't get one. */ - } - if (node == chosen_exit) - continue; /* don't pick the same node for entry and exit */ - if (smartlist_contains(exit_family, node)) - continue; /* avoid relays that are family members of our exit */ - smartlist_add(live_entry_guards, (void*)node); - if (!entry->made_contact) { - /* Always start with the first not-yet-contacted entry - * guard. Otherwise we might add several new ones, pick - * the second new one, and now we've expanded our entry - * guard list without needing to. */ - retval = 1; - goto done; - } - if (smartlist_len(live_entry_guards) >= num_needed) { - retval = 1; - goto done; /* We picked enough entry guards. Done! */ +#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(entry); + } SMARTLIST_FOREACH_END(g); + } - done: - smartlist_free(exit_family); + 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); + } - return retval; + smartlist_free(old_primary_guards); + smartlist_free(gs->primary_entry_guards); + gs->primary_entry_guards = new_primary_guards; + gs->primary_guards_up_to_date = 1; + running = 0; } -/** Pick a node to be used as the entry guard of a circuit. - * - * If <b>state</b> is set, it contains the information we know about - * the upcoming circuit. - * - * If <b>for_directory</b> is set, we are looking for a directory guard. - * - * <b>dirinfo_type</b> contains the kind of directory information we - * are looking for in our node, or NO_DIRINFO (zero) if we are not - * looking for any particular directory information (when set to - * NO_DIRINFO, the <b>dirinfo_type</b> filter is ignored). - * - * If <b>n_options_out</b> is set, we set it to the number of - * candidate guard nodes we had before picking a specific guard node. - * - * On success, return the node that should be used as the entry guard - * of the circuit. Return NULL if no such node could be found. - * - * Helper for choose_random{entry,dirguard}. -*/ -static const node_t * -choose_random_entry_impl(cpath_build_state_t *state, int for_directory, - dirinfo_type_t dirinfo_type, int *n_options_out) +/** + * 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 int +get_retry_schedule(time_t failing_since, time_t now, + int is_primary) { - const or_options_t *options = get_options(); - smartlist_t *live_entry_guards = smartlist_new(); - const node_t *chosen_exit = - state?build_state_get_exit_node(state) : NULL; - const node_t *node = NULL; - int need_uptime = state ? state->need_uptime : 0; - int need_capacity = state ? state->need_capacity : 0; - int preferred_min = 0; - const int num_needed = decide_num_guards(options, for_directory); - int retval = 0; - - if (n_options_out) - *n_options_out = 0; - - if (!entry_guards) - entry_guards = smartlist_new(); - - if (should_add_entry_nodes) - entry_guards_set_from_config(options); - - if (!entry_list_is_constrained(options) && - smartlist_len(entry_guards) < num_needed) - pick_entry_guards(options, for_directory); - - retry: - smartlist_clear(live_entry_guards); - - /* Populate the list of live entry guards so that we pick one of - them. */ - retval = populate_live_entry_guards(live_entry_guards, - entry_guards, - chosen_exit, - dirinfo_type, - for_directory, - need_uptime, need_capacity); - - if (retval == 1) { /* We should choose a guard right now. */ - goto choose_and_finish; - } - - if (entry_list_is_constrained(options)) { - /* If we prefer the entry nodes we've got, and we have at least - * one choice, that's great. Use it. */ - preferred_min = 1; - } else { - /* Try to have at least 2 choices available. This way we don't - * get stuck with a single live-but-crummy entry and just keep - * using it. - * (We might get 2 live-but-crummy entry guards, but so be it.) */ - preferred_min = 2; - } - - if (smartlist_len(live_entry_guards) < preferred_min) { - if (!entry_list_is_constrained(options)) { - /* still no? try adding a new entry then */ - /* XXX if guard doesn't imply fast and stable, then we need - * to tell add_an_entry_guard below what we want, or it might - * be a long time til we get it. -RD */ - node = add_an_entry_guard(NULL, 0, 0, 1, for_directory); - if (node) { - entry_guards_changed(); - /* XXX we start over here in case the new node we added shares - * a family with our exit node. There's a chance that we'll just - * load up on entry guards here, if the network we're using is - * one big family. Perhaps we should teach add_an_entry_guard() - * to understand nodes-to-avoid-if-possible? -RD */ - goto retry; - } - } - if (!node && need_uptime) { - need_uptime = 0; /* try without that requirement */ - goto retry; - } - if (!node && need_capacity) { - /* still no? last attempt, try without requiring capacity */ - need_capacity = 0; - goto retry; - } + const unsigned SIX_HOURS = 6 * 3600; + const unsigned FOUR_DAYS = 4 * 86400; + const unsigned SEVEN_DAYS = 7 * 86400; - /* live_entry_guards may be empty below. Oh well, we tried. */ + time_t tdiff; + if (now > failing_since) { + tdiff = now - failing_since; + } else { + tdiff = 0; } - choose_and_finish: - if (entry_list_is_constrained(options)) { - /* We need to weight by bandwidth, because our bridges or entryguards - * were not already selected proportional to their bandwidth. */ - node = node_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD); - } else { - /* We choose uniformly at random here, because choose_good_entry_server() - * already weights its choices by bandwidth, so we don't want to - * *double*-weight our guard selection. */ - node = smartlist_choose(live_entry_guards); + const struct { + time_t maximum; int primary_delay; int nonprimary_delay; + } delays[] = { + { SIX_HOURS, 10*60, 1*60*60 }, + { FOUR_DAYS, 90*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; + } } - if (n_options_out) - *n_options_out = smartlist_len(live_entry_guards); - smartlist_free(live_entry_guards); - return node; + /* LCOV_EXCL_START -- can't reach, since delays ends with TIME_MAX. */ + tor_assert_nonfatal_unreached(); + return 36*60*60; + /* LCOV_EXCL_STOP */ } -/** Parse <b>state</b> and learn about the entry guards it describes. - * If <b>set</b> is true, and there are no errors, replace the global - * entry_list with what we find. - * On success, return 0. On failure, alloc into *<b>msg</b> a string - * describing the error, and return -1. +/** + * If <b>guard</b> is unreachable, consider whether enough time has passed + * to consider it maybe-reachable again. */ -int -entry_guards_parse_state(or_state_t *state, int set, char **msg) +STATIC void +entry_guard_consider_retry(entry_guard_t *guard) { - entry_guard_t *node = NULL; - smartlist_t *new_entry_guards = smartlist_new(); - config_line_t *line; - time_t now = time(NULL); - const char *state_version = state->TorVersion; - digestmap_t *added_by = digestmap_new(); - - *msg = NULL; - for (line = state->EntryGuards; line; line = line->next) { - if (!strcasecmp(line->key, "EntryGuard")) { - smartlist_t *args = smartlist_new(); - node = tor_malloc_zero(sizeof(entry_guard_t)); - /* all entry guards on disk have been contacted */ - node->made_contact = 1; - smartlist_add(new_entry_guards, node); - smartlist_split_string(args, line->value, " ", - SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); - if (smartlist_len(args)<2) { - *msg = tor_strdup("Unable to parse entry nodes: " - "Too few arguments to EntryGuard"); - } else if (!is_legal_nickname(smartlist_get(args,0))) { - *msg = tor_strdup("Unable to parse entry nodes: " - "Bad nickname for EntryGuard"); - } else { - strlcpy(node->nickname, smartlist_get(args,0), MAX_NICKNAME_LEN+1); - if (base16_decode(node->identity, DIGEST_LEN, smartlist_get(args,1), - strlen(smartlist_get(args,1))) != DIGEST_LEN) { - *msg = tor_strdup("Unable to parse entry nodes: " - "Bad hex digest for EntryGuard"); - } - } - if (smartlist_len(args) >= 3) { - const char *is_cache = smartlist_get(args, 2); - if (!strcasecmp(is_cache, "DirCache")) { - node->is_dir_cache = 1; - } else if (!strcasecmp(is_cache, "NoDirCache")) { - node->is_dir_cache = 0; - } else { - log_warn(LD_CONFIG, "Bogus third argument to EntryGuard line: %s", - escaped(is_cache)); - } - } - SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); - smartlist_free(args); - if (*msg) - break; - } else if (!strcasecmp(line->key, "EntryGuardDownSince") || - !strcasecmp(line->key, "EntryGuardUnlistedSince")) { - time_t when; - time_t last_try = 0; - if (!node) { - *msg = tor_strdup("Unable to parse entry nodes: " - "EntryGuardDownSince/UnlistedSince without EntryGuard"); - break; - } - if (parse_iso_time_(line->value, &when, 0)<0) { - *msg = tor_strdup("Unable to parse entry nodes: " - "Bad time in EntryGuardDownSince/UnlistedSince"); - break; - } - if (when > now) { - /* It's a bad idea to believe info in the future: you can wind - * up with timeouts that aren't allowed to happen for years. */ - continue; - } - if (strlen(line->value) >= ISO_TIME_LEN+ISO_TIME_LEN+1) { - /* ignore failure */ - (void) parse_iso_time(line->value+ISO_TIME_LEN+1, &last_try); - } - if (!strcasecmp(line->key, "EntryGuardDownSince")) { - node->unreachable_since = when; - node->last_attempted = last_try; - } else { - node->bad_since = when; - } - } else if (!strcasecmp(line->key, "EntryGuardAddedBy")) { - char d[DIGEST_LEN]; - /* format is digest version date */ - if (strlen(line->value) < HEX_DIGEST_LEN+1+1+1+ISO_TIME_LEN) { - log_warn(LD_BUG, "EntryGuardAddedBy line is not long enough."); - continue; - } - if (base16_decode(d, sizeof(d), - line->value, HEX_DIGEST_LEN) != sizeof(d) || - line->value[HEX_DIGEST_LEN] != ' ') { - log_warn(LD_BUG, "EntryGuardAddedBy line %s does not begin with " - "hex digest", escaped(line->value)); + if (guard->is_reachable != GUARD_REACHABLE_NO) + return; /* No retry needed. */ + + const time_t now = approx_time(); + const int 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; + } +} + +/** Tell the entry guards subsystem that we have confirmed that as of + * just now, we're on the internet. */ +void +entry_guards_note_internet_connectivity(guard_selection_t *gs) +{ + gs->last_time_on_internet = approx_time(); +} + +/** + * 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, + guard_usage_t usage, + const entry_guard_restriction_t *rst, + unsigned *state_out) +{ + const int need_descriptor = (usage == GUARD_USAGE_TRAFFIC); + tor_assert(gs); + tor_assert(state_out); + + if (!gs->primary_guards_up_to_date) + entry_guards_update_primary(gs); + + int num_entry_guards = get_n_primary_guards_to_use(usage); + smartlist_t *usable_primary_guards = smartlist_new(); + + /* "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 (! entry_guard_obeys_restriction(guard, rst)) + continue; + if (guard->is_reachable != GUARD_REACHABLE_NO) { + if (need_descriptor && !guard_has_descriptor(guard)) { continue; } - digestmap_set(added_by, d, tor_strdup(line->value+HEX_DIGEST_LEN+1)); - } else if (!strcasecmp(line->key, "EntryGuardPathUseBias")) { - const or_options_t *options = get_options(); - double use_cnt, success_cnt; - - if (!node) { - *msg = tor_strdup("Unable to parse entry nodes: " - "EntryGuardPathUseBias without EntryGuard"); + *state_out = GUARD_CIRC_STATE_USABLE_ON_COMPLETION; + guard->last_tried_to_connect = approx_time(); + smartlist_add(usable_primary_guards, guard); + if (smartlist_len(usable_primary_guards) >= num_entry_guards) break; - } + } + } SMARTLIST_FOREACH_END(guard); + + if (smartlist_len(usable_primary_guards)) { + entry_guard_t *guard = smartlist_choose(usable_primary_guards); + smartlist_free(usable_primary_guards); + log_info(LD_GUARD, "Selected primary guard %s for circuit.", + entry_guard_describe(guard)); + return guard; + } + smartlist_free(usable_primary_guards); + + /* "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. */ + if (! entry_guard_obeys_restriction(guard, rst)) + continue; + entry_guard_consider_retry(guard); + if (guard->is_usable_filtered_guard && ! guard->is_pending) { + if (need_descriptor && !guard_has_descriptor(guard)) + continue; /* not a bug */ + 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); - if (tor_sscanf(line->value, "%lf %lf", - &use_cnt, &success_cnt) != 2) { - log_info(LD_GENERAL, "Malformed path use bias line for node %s", - node->nickname); - continue; - } + /* "Otherwise, if there is no such entry, select a member at + random from {USABLE_FILTERED_GUARDS}." */ + { + entry_guard_t *guard; + unsigned flags = 0; + if (need_descriptor) + flags |= SAMPLE_EXCLUDE_NO_DESCRIPTOR; + guard = sample_reachable_filtered_entry_guards(gs, + rst, + SAMPLE_EXCLUDE_CONFIRMED | + SAMPLE_EXCLUDE_PRIMARY | + SAMPLE_EXCLUDE_PENDING | + flags); + if (guard == NULL) { + log_info(LD_GUARD, "Absolutely no sampled guards were available. " + "Marking all guards for retry and starting from top again."); + mark_all_guards_maybe_reachable(gs); + 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; + } +} - if (use_cnt < success_cnt) { - int severity = LOG_INFO; - /* If this state file was written by a Tor that would have - * already fixed it, then the overcounting bug is still there.. */ - if (tor_version_as_new_as(state_version, "0.2.4.13-alpha")) { - severity = LOG_NOTICE; - } - log_fn(severity, LD_BUG, - "State file contains unexpectedly high usage success " - "counts %lf/%lf for Guard %s ($%s)", - success_cnt, use_cnt, - node->nickname, hex_str(node->identity, DIGEST_LEN)); - success_cnt = use_cnt; - } +/** + * Note that we failed to connect to or build circuits through <b>guard</b>. + * Use with a guard returned by select_entry_guard_for_circuit(). + */ +STATIC void +entry_guards_note_guard_failure(guard_selection_t *gs, + entry_guard_t *guard) +{ + tor_assert(gs); - node->use_attempts = use_cnt; - node->use_successes = success_cnt; - - log_info(LD_GENERAL, "Read %f/%f path use bias for node %s", - node->use_successes, node->use_attempts, node->nickname); - - /* Note: We rely on the < comparison here to allow us to set a 0 - * rate and disable the feature entirely. If refactoring, don't - * change to <= */ - if (pathbias_get_use_success_count(node)/node->use_attempts - < pathbias_get_extreme_use_rate(options) && - pathbias_get_dropguards(options)) { - node->path_bias_disabled = 1; - log_info(LD_GENERAL, - "Path use bias is too high (%f/%f); disabling node %s", - node->circ_successes, node->circ_attempts, node->nickname); - } - } else if (!strcasecmp(line->key, "EntryGuardPathBias")) { - const or_options_t *options = get_options(); - double hop_cnt, success_cnt, timeouts, collapsed, successful_closed, - unusable; - - if (!node) { - *msg = tor_strdup("Unable to parse entry nodes: " - "EntryGuardPathBias without EntryGuard"); - break; - } + guard->is_reachable = GUARD_REACHABLE_NO; + guard->is_usable_filtered_guard = 0; - /* First try 3 params, then 2. */ - /* In the long run: circuit_success ~= successful_circuit_close + - * collapsed_circuits + - * unusable_circuits */ - if (tor_sscanf(line->value, "%lf %lf %lf %lf %lf %lf", - &hop_cnt, &success_cnt, &successful_closed, - &collapsed, &unusable, &timeouts) != 6) { - int old_success, old_hops; - if (tor_sscanf(line->value, "%u %u", &old_success, &old_hops) != 2) { - continue; - } - log_info(LD_GENERAL, "Reading old-style EntryGuardPathBias %s", - escaped(line->value)); - - success_cnt = old_success; - successful_closed = old_success; - hop_cnt = old_hops; - timeouts = 0; - collapsed = 0; - unusable = 0; - } + guard->is_pending = 0; + if (guard->failing_since == 0) + guard->failing_since = approx_time(); - if (hop_cnt < success_cnt) { - int severity = LOG_INFO; - /* If this state file was written by a Tor that would have - * already fixed it, then the overcounting bug is still there.. */ - if (tor_version_as_new_as(state_version, "0.2.4.13-alpha")) { - severity = LOG_NOTICE; - } - log_fn(severity, LD_BUG, - "State file contains unexpectedly high success counts " - "%lf/%lf for Guard %s ($%s)", - success_cnt, hop_cnt, - node->nickname, hex_str(node->identity, DIGEST_LEN)); - success_cnt = hop_cnt; - } + log_info(LD_GUARD, "Recorded failure for %s%sguard %s", + guard->is_primary?"primary ":"", + guard->confirmed_idx>=0?"confirmed ":"", + entry_guard_describe(guard)); +} - node->circ_attempts = hop_cnt; - node->circ_successes = success_cnt; - - node->successful_circuits_closed = successful_closed; - node->timeouts = timeouts; - node->collapsed_circuits = collapsed; - node->unusable_circuits = unusable; - - log_info(LD_GENERAL, "Read %f/%f path bias for node %s", - node->circ_successes, node->circ_attempts, node->nickname); - /* Note: We rely on the < comparison here to allow us to set a 0 - * rate and disable the feature entirely. If refactoring, don't - * change to <= */ - if (pathbias_get_close_success_count(node)/node->circ_attempts - < pathbias_get_extreme_rate(options) && - pathbias_get_dropguards(options)) { - node->path_bias_disabled = 1; - log_info(LD_GENERAL, - "Path bias is too high (%f/%f); disabling node %s", - node->circ_successes, node->circ_attempts, node->nickname); - } +/** + * 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) { + make_guard_confirmed(gs, guard); + if (!gs->primary_guards_up_to_date) + entry_guards_update_primary(gs); + } - } else { - log_warn(LD_BUG, "Unexpected key %s", line->key); - } + unsigned new_state; + switch (old_state) { + case GUARD_CIRC_STATE_COMPLETE: + case GUARD_CIRC_STATE_USABLE_ON_COMPLETION: + new_state = GUARD_CIRC_STATE_COMPLETE; + break; + default: + tor_assert_nonfatal_unreached(); + /* Fall through. */ + case GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD: + if (guard->is_primary) { + /* XXXX #20832 -- I don't actually like this logic. It seems to make + * us a little more susceptible to evil-ISP attacks. The mitigations + * I'm thinking of, however, aren't local to this point, so I'll leave + * it alone. */ + /* This guard may have become primary by virtue of being confirmed. + * If so, the circuit for it is now complete. + */ + new_state = GUARD_CIRC_STATE_COMPLETE; + } else { + new_state = GUARD_CIRC_STATE_WAITING_FOR_BETTER_GUARD; + } + break; } - SMARTLIST_FOREACH_BEGIN(new_entry_guards, entry_guard_t *, e) { - char *sp; - char *val = digestmap_get(added_by, e->identity); - if (val && (sp = strchr(val, ' '))) { - time_t when; - *sp++ = '\0'; - if (parse_iso_time(sp, &when)<0) { - log_warn(LD_BUG, "Can't read time %s in EntryGuardAddedBy", sp); - } else { - e->chosen_by_version = tor_strdup(val); - e->chosen_on_date = when; - } - } else { - if (state_version) { - e->chosen_on_date = crypto_rand_time_range(now - 3600*24*30, now); - e->chosen_by_version = tor_strdup(state_version); - } - } - if (e->path_bias_disabled && !e->bad_since) - e->bad_since = time(NULL); + if (! guard->is_primary) { + if (last_time_on_internet + get_internet_likely_down_interval() + < approx_time()) { + mark_primary_guards_maybe_reachable(gs); } - SMARTLIST_FOREACH_END(e); + } - if (*msg || !set) { - SMARTLIST_FOREACH(new_entry_guards, entry_guard_t *, e, - entry_guard_free(e)); - smartlist_free(new_entry_guards); - } else { /* !err && set */ - if (entry_guards) { - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, - entry_guard_free(e)); - smartlist_free(entry_guards); - } - entry_guards = new_entry_guards; - entry_guards_dirty = 0; - /* XXX hand new_entry_guards to this func, and move it up a - * few lines, so we don't have to re-dirty it */ - if (remove_obsolete_entry_guards(now)) - entry_guards_dirty = 1; + log_info(LD_GUARD, "Recorded success for %s%sguard %s", + guard->is_primary?"primary ":"", + guard->confirmed_idx>=0?"confirmed ":"", + entry_guard_describe(guard)); - update_node_guard_status(); - } - digestmap_free(added_by, tor_free_); - return *msg ? -1 : 0; + return new_state; } -/** How long will we let a change in our guard nodes stay un-saved - * when we are trying to avoid disk writes? */ -#define SLOW_GUARD_STATE_FLUSH_TIME 600 -/** How long will we let a change in our guard nodes stay un-saved - * when we are not trying to avoid disk writes? */ -#define FAST_GUARD_STATE_FLUSH_TIME 30 - -/** Our list of entry guards has changed, or some element of one - * of our entry guards has changed. Write the changes to disk within - * the next few minutes. +/** + * Helper: Return true iff <b>a</b> has higher priority than <b>b</b>. */ -void -entry_guards_changed(void) +STATIC int +entry_guard_has_higher_priority(entry_guard_t *a, entry_guard_t *b) { - time_t when; - entry_guards_dirty = 1; + tor_assert(a && b); + if (a == b) + return 0; - if (get_options()->AvoidDiskWrites) - when = time(NULL) + SLOW_GUARD_STATE_FLUSH_TIME; - else - when = time(NULL) + FAST_GUARD_STATE_FLUSH_TIME; + /* 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; - /* or_state_save() will call entry_guards_update_state(). */ - or_state_mark_dirty(get_or_state(), when); + /* 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; + } } -/** If the entry guard info has not changed, do nothing and return. - * Otherwise, free the EntryGuards piece of <b>state</b> and create - * a new one out of the global entry_guards list, and then mark - * <b>state</b> dirty so it will get saved to disk. +/** Release all storage held in <b>restriction</b> */ +static void +entry_guard_restriction_free(entry_guard_restriction_t *rst) +{ + tor_free(rst); +} + +/** + * Release all storage held in <b>state</b>. */ void -entry_guards_update_state(or_state_t *state) +circuit_guard_state_free(circuit_guard_state_t *state) { - config_line_t **next, *line; - if (! entry_guards_dirty) + if (!state) return; - - config_free_lines(state->EntryGuards); - next = &state->EntryGuards; - *next = NULL; - if (!entry_guards) - entry_guards = smartlist_new(); - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) { - char dbuf[HEX_DIGEST_LEN+1]; - if (!e->made_contact) - continue; /* don't write this one to disk */ - *next = line = tor_malloc_zero(sizeof(config_line_t)); - line->key = tor_strdup("EntryGuard"); - base16_encode(dbuf, sizeof(dbuf), e->identity, DIGEST_LEN); - tor_asprintf(&line->value, "%s %s %sDirCache", e->nickname, dbuf, - e->is_dir_cache ? "" : "No"); - next = &(line->next); - if (e->unreachable_since) { - *next = line = tor_malloc_zero(sizeof(config_line_t)); - line->key = tor_strdup("EntryGuardDownSince"); - line->value = tor_malloc(ISO_TIME_LEN+1+ISO_TIME_LEN+1); - format_iso_time(line->value, e->unreachable_since); - if (e->last_attempted) { - line->value[ISO_TIME_LEN] = ' '; - format_iso_time(line->value+ISO_TIME_LEN+1, e->last_attempted); - } - next = &(line->next); - } - if (e->bad_since) { - *next = line = tor_malloc_zero(sizeof(config_line_t)); - line->key = tor_strdup("EntryGuardUnlistedSince"); - line->value = tor_malloc(ISO_TIME_LEN+1); - format_iso_time(line->value, e->bad_since); - next = &(line->next); - } - if (e->chosen_on_date && e->chosen_by_version && - !strchr(e->chosen_by_version, ' ')) { - char d[HEX_DIGEST_LEN+1]; - char t[ISO_TIME_LEN+1]; - *next = line = tor_malloc_zero(sizeof(config_line_t)); - line->key = tor_strdup("EntryGuardAddedBy"); - base16_encode(d, sizeof(d), e->identity, DIGEST_LEN); - format_iso_time(t, e->chosen_on_date); - tor_asprintf(&line->value, "%s %s %s", - d, e->chosen_by_version, t); - next = &(line->next); - } - if (e->circ_attempts > 0) { - *next = line = tor_malloc_zero(sizeof(config_line_t)); - line->key = tor_strdup("EntryGuardPathBias"); - /* In the long run: circuit_success ~= successful_circuit_close + - * collapsed_circuits + - * unusable_circuits */ - tor_asprintf(&line->value, "%f %f %f %f %f %f", - e->circ_attempts, e->circ_successes, - pathbias_get_close_success_count(e), - e->collapsed_circuits, - e->unusable_circuits, e->timeouts); - next = &(line->next); - } - if (e->use_attempts > 0) { - *next = line = tor_malloc_zero(sizeof(config_line_t)); - line->key = tor_strdup("EntryGuardPathUseBias"); - - tor_asprintf(&line->value, "%f %f", - e->use_attempts, - pathbias_get_use_success_count(e)); - next = &(line->next); - } - - } SMARTLIST_FOREACH_END(e); - if (!get_options()->AvoidDiskWrites) - or_state_mark_dirty(get_or_state(), 0); - entry_guards_dirty = 0; + entry_guard_restriction_free(state->restrictions); + entry_guard_handle_free(state->guard); + tor_free(state); } -/** If <b>question</b> is the string "entry-guards", then dump - * to *<b>answer</b> a newly allocated string describing all of - * the nodes in the global entry_guards list. See control-spec.txt - * for details. - * For backward compatibility, we also handle the string "helper-nodes". - * */ +/** + * Pick a suitable entry guard for a circuit in, and place that guard + * in *<b>chosen_node_out</b>. Set *<b>guard_state_out</b> to an opaque + * state object that will record whether the circuit is ready to be used + * or not. Return 0 on success; on failure, return -1. + * + * If a restriction is provided in <b>rst</b>, do not return any guards that + * violate it, and remember that restriction in <b>guard_state_out</b> for + * later use. (Takes ownership of the <b>rst</b> object.) + */ int -getinfo_helper_entry_guards(control_connection_t *conn, - const char *question, char **answer, - const char **errmsg) -{ - (void) conn; - (void) errmsg; +entry_guard_pick_for_circuit(guard_selection_t *gs, + guard_usage_t usage, + entry_guard_restriction_t *rst, + const node_t **chosen_node_out, + circuit_guard_state_t **guard_state_out) +{ + tor_assert(gs); + tor_assert(chosen_node_out); + tor_assert(guard_state_out); + *chosen_node_out = NULL; + *guard_state_out = NULL; + + unsigned state = 0; + entry_guard_t *guard = + select_entry_guard_for_circuit(gs, usage, rst, &state); + if (! guard) + goto fail; + if (BUG(state == 0)) + goto fail; + const node_t *node = node_get_by_id(guard->identity); + // XXXX #20827 check Ed ID. + if (! node) + goto fail; + if (BUG(usage != GUARD_USAGE_DIRGUARD && !node_has_descriptor(node))) + goto fail; + + *chosen_node_out = node; + *guard_state_out = tor_malloc_zero(sizeof(circuit_guard_state_t)); + (*guard_state_out)->guard = entry_guard_handle_new(guard); + (*guard_state_out)->state = state; + (*guard_state_out)->state_set_at = approx_time(); + (*guard_state_out)->restrictions = rst; - if (!strcmp(question,"entry-guards") || - !strcmp(question,"helper-nodes")) { - smartlist_t *sl = smartlist_new(); - char tbuf[ISO_TIME_LEN+1]; - char nbuf[MAX_VERBOSE_NICKNAME_LEN+1]; - if (!entry_guards) - entry_guards = smartlist_new(); - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) { - const char *status = NULL; - time_t when = 0; - const node_t *node; - - if (!e->made_contact) { - status = "never-connected"; - } else if (e->bad_since) { - when = e->bad_since; - status = "unusable"; - } else if (e->unreachable_since) { - when = e->unreachable_since; - status = "down"; - } else { - status = "up"; - } - - node = node_get_by_id(e->identity); - if (node) { - node_get_verbose_nickname(node, nbuf); - } else { - nbuf[0] = '$'; - base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN); - /* e->nickname field is not very reliable if we don't know about - * this router any longer; don't include it. */ - } - - if (when) { - format_iso_time(tbuf, when); - smartlist_add_asprintf(sl, "%s %s %s\n", nbuf, status, tbuf); - } else { - smartlist_add_asprintf(sl, "%s %s\n", nbuf, status); - } - } SMARTLIST_FOREACH_END(e); - *answer = smartlist_join_strings(sl, "", 0, NULL); - SMARTLIST_FOREACH(sl, char *, c, tor_free(c)); - smartlist_free(sl); - } return 0; + fail: + entry_guard_restriction_free(rst); + return -1; } -/** Return 0 if we should apply guardfraction information found in the - * consensus. A specific consensus can be specified with the - * <b>ns</b> argument, if NULL the most recent one will be picked.*/ -int -should_apply_guardfraction(const networkstatus_t *ns) +/** + * Called by the circuit building module when a circuit has succeeded: informs + * the guards code that the guard in *<b>guard_state_p</b> is working, and + * advances the state of the guard module. On a GUARD_USABLE_NEVER return + * value, the circuit is broken and should not be used. On a GUARD_USABLE_NOW + * return value, the circuit is ready to use. On a GUARD_MAYBE_USABLE_LATER + * return value, the circuit should not be used until we find out whether + * preferred guards will work for us. + */ +guard_usable_t +entry_guard_succeeded(circuit_guard_state_t **guard_state_p) { - /* We need to check the corresponding torrc option and the consensus - * parameter if we need to. */ - const or_options_t *options = get_options(); + if (BUG(*guard_state_p == NULL)) + return GUARD_USABLE_NEVER; - /* If UseGuardFraction is 'auto' then check the same-named consensus - * parameter. If the consensus parameter is not present, default to - * "off". */ - if (options->UseGuardFraction == -1) { - return networkstatus_get_param(ns, "UseGuardFraction", - 0, /* default to "off" */ - 0, 1); + entry_guard_t *guard = entry_guard_handle_get((*guard_state_p)->guard); + if (! guard || BUG(guard->in_selection == NULL)) + return GUARD_USABLE_NEVER; + + unsigned newstate = + entry_guards_note_guard_success(guard->in_selection, guard, + (*guard_state_p)->state); + + (*guard_state_p)->state = newstate; + (*guard_state_p)->state_set_at = approx_time(); + + if (newstate == GUARD_CIRC_STATE_COMPLETE) { + return GUARD_USABLE_NOW; + } else { + return GUARD_MAYBE_USABLE_LATER; } +} - return options->UseGuardFraction; +/** Cancel the selection of *<b>guard_state_p</b> without declaring + * success or failure. It is safe to call this function if success or + * failure _has_ already been declared. */ +void +entry_guard_cancel(circuit_guard_state_t **guard_state_p) +{ + if (BUG(*guard_state_p == NULL)) + return; + entry_guard_t *guard = entry_guard_handle_get((*guard_state_p)->guard); + if (! guard) + return; + + /* XXXX prop271 -- last_tried_to_connect_at will be erroneous here, but this + * function will only get called in "bug" cases anyway. */ + guard->is_pending = 0; + circuit_guard_state_free(*guard_state_p); + *guard_state_p = NULL; } -/* Given the original bandwidth of a guard and its guardfraction, - * calculate how much bandwidth the guard should have as a guard and - * as a non-guard. - * - * Quoting from proposal236: - * - * Let Wpf denote the weight from the 'bandwidth-weights' line a - * client would apply to N for position p if it had the guard - * flag, Wpn the weight if it did not have the guard flag, and B the - * measured bandwidth of N in the consensus. Then instead of choosing - * N for position p proportionally to Wpf*B or Wpn*B, clients should - * choose N proportionally to F*Wpf*B + (1-F)*Wpn*B. - * - * This function fills the <b>guardfraction_bw</b> structure. It sets - * <b>guard_bw</b> to F*B and <b>non_guard_bw</b> to (1-F)*B. +/** + * Called by the circuit building module when a circuit has succeeded: + * informs the guards code that the guard in *<b>guard_state_p</b> is + * not working, and advances the state of the guard module. */ void -guard_get_guardfraction_bandwidth(guardfraction_bandwidth_t *guardfraction_bw, - int orig_bandwidth, - uint32_t guardfraction_percentage) +entry_guard_failed(circuit_guard_state_t **guard_state_p) { - double guardfraction_fraction; - - /* Turn the percentage into a fraction. */ - tor_assert(guardfraction_percentage <= 100); - guardfraction_fraction = guardfraction_percentage / 100.0; + if (BUG(*guard_state_p == NULL)) + return; - long guard_bw = tor_lround(guardfraction_fraction * orig_bandwidth); - tor_assert(guard_bw <= INT_MAX); + entry_guard_t *guard = entry_guard_handle_get((*guard_state_p)->guard); + if (! guard || BUG(guard->in_selection == NULL)) + return; - guardfraction_bw->guard_bw = (int) guard_bw; + entry_guards_note_guard_failure(guard->in_selection, guard); - guardfraction_bw->non_guard_bw = orig_bandwidth - (int) guard_bw; + (*guard_state_p)->state = GUARD_CIRC_STATE_DEAD; + (*guard_state_p)->state_set_at = approx_time(); } -/** A list of configured bridges. Whenever we actually get a descriptor - * for one, we add it as an entry guard. Note that the order of bridges - * in this list does not necessarily correspond to the order of bridges - * in the torrc. */ -static smartlist_t *bridge_list = NULL; - -/** Mark every entry of the bridge list to be removed on our next call to - * sweep_bridge_list unless it has first been un-marked. */ +/** + * Run the entry_guard_failed() function on every circuit that is + * pending on <b>chan</b>. + */ void -mark_bridge_list(void) +entry_guard_chan_failed(channel_t *chan) { - if (!bridge_list) - bridge_list = smartlist_new(); - SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b, - b->marked_for_removal = 1); -} + if (!chan) + return; -/** Remove every entry of the bridge list that was marked with - * mark_bridge_list if it has not subsequently been un-marked. */ -void -sweep_bridge_list(void) -{ - if (!bridge_list) - bridge_list = smartlist_new(); - SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, b) { - if (b->marked_for_removal) { - SMARTLIST_DEL_CURRENT(bridge_list, b); - bridge_free(b); + smartlist_t *pending = smartlist_new(); + circuit_get_all_pending_on_channel(pending, chan); + SMARTLIST_FOREACH_BEGIN(pending, circuit_t *, circ) { + if (!CIRCUIT_IS_ORIGIN(circ)) + continue; + + origin_circuit_t *origin_circ = TO_ORIGIN_CIRCUIT(circ); + if (origin_circ->guard_state) { + /* We might have no guard state if we didn't use a guard on this + * circuit (eg it's for a fallback directory). */ + entry_guard_failed(&origin_circ->guard_state); } - } SMARTLIST_FOREACH_END(b); + } SMARTLIST_FOREACH_END(circ); + smartlist_free(pending); } -/** Initialize the bridge list to empty, creating it if needed. */ -static void -clear_bridge_list(void) +/** + * Return true iff every primary guard in <b>gs</b> is believed to + * be unreachable. + */ +STATIC int +entry_guards_all_primary_guards_are_down(guard_selection_t *gs) +{ + tor_assert(gs); + if (!gs->primary_guards_up_to_date) + entry_guards_update_primary(gs); + SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) { + entry_guard_consider_retry(guard); + if (guard->is_reachable != GUARD_REACHABLE_NO) + return 0; + } SMARTLIST_FOREACH_END(guard); + return 1; +} + +/** Wrapper for entry_guard_has_higher_priority that compares the + * guard-priorities of a pair of circuits. Return 1 if <b>a</b> has higher + * priority than <b>b</b>. + * + * If a restriction is provided in <b>rst</b>, then do not consider + * <b>a</b> to have higher priority if it violates the restriction. + */ +static int +circ_state_has_higher_priority(origin_circuit_t *a, + const entry_guard_restriction_t *rst, + origin_circuit_t *b) { - if (!bridge_list) - bridge_list = smartlist_new(); - SMARTLIST_FOREACH(bridge_list, bridge_info_t *, b, bridge_free(b)); - smartlist_clear(bridge_list); -} + circuit_guard_state_t *state_a = origin_circuit_get_guard_state(a); + circuit_guard_state_t *state_b = origin_circuit_get_guard_state(b); -/** Free the bridge <b>bridge</b>. */ -static void -bridge_free(bridge_info_t *bridge) -{ - if (!bridge) - return; + tor_assert(state_a); + tor_assert(state_b); - tor_free(bridge->transport_name); - if (bridge->socks_args) { - SMARTLIST_FOREACH(bridge->socks_args, char*, s, tor_free(s)); - smartlist_free(bridge->socks_args); - } + entry_guard_t *guard_a = entry_guard_handle_get(state_a->guard); + entry_guard_t *guard_b = entry_guard_handle_get(state_b->guard); - tor_free(bridge); + if (! guard_a) { + /* Unknown guard -- never higher priority. */ + return 0; + } else if (! guard_b) { + /* Known guard -- higher priority than any unknown guard. */ + return 1; + } else if (! entry_guard_obeys_restriction(guard_a, rst)) { + /* Restriction violated; guard_a cannot have higher priority. */ + return 0; + } else { + /* Both known -- compare.*/ + return entry_guard_has_higher_priority(guard_a, guard_b); + } } -/** If we have a bridge configured whose digest matches <b>digest</b>, or a - * bridge with no known digest whose address matches any of the - * tor_addr_port_t's in <b>orports</b>, return that bridge. Else return - * NULL. */ -static bridge_info_t * -get_configured_bridge_by_orports_digest(const char *digest, - const smartlist_t *orports) -{ - if (!bridge_list) - return NULL; - SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge) - { - if (tor_digest_is_zero(bridge->identity)) { - SMARTLIST_FOREACH_BEGIN(orports, tor_addr_port_t *, ap) - { - if (tor_addr_compare(&bridge->addr, &ap->addr, CMP_EXACT) == 0 && - bridge->port == ap->port) - return bridge; - } - SMARTLIST_FOREACH_END(ap); +/** + * Look at all of the origin_circuit_t * objects in <b>all_circuits_in</b>, + * and see if any of them that were previously not ready to use for + * guard-related reasons are now ready to use. Place those circuits + * in <b>newly_complete_out</b>, and mark them COMPLETE. + * + * Return 1 if we upgraded any circuits, and 0 otherwise. + */ +int +entry_guards_upgrade_waiting_circuits(guard_selection_t *gs, + const smartlist_t *all_circuits_in, + smartlist_t *newly_complete_out) +{ + tor_assert(gs); + tor_assert(all_circuits_in); + tor_assert(newly_complete_out); + + if (! entry_guards_all_primary_guards_are_down(gs)) { + /* We only upgrade a waiting circuit if the primary guards are all + * down. */ + log_debug(LD_GUARD, "Considered upgrading guard-stalled circuits, " + "but not all primary guards were definitely down."); + return 0; + } + + int n_waiting = 0; + int n_complete = 0; + int n_complete_blocking = 0; + origin_circuit_t *best_waiting_circuit = NULL; + smartlist_t *all_circuits = smartlist_new(); + SMARTLIST_FOREACH_BEGIN(all_circuits_in, origin_circuit_t *, circ) { + // We filter out circuits that aren't ours, or which we can't + // reason about. + circuit_guard_state_t *state = origin_circuit_get_guard_state(circ); + if (state == NULL) + continue; + entry_guard_t *guard = entry_guard_handle_get(state->guard); + if (!guard || guard->in_selection != gs) + continue; + + smartlist_add(all_circuits, circ); + } SMARTLIST_FOREACH_END(circ); + + SMARTLIST_FOREACH_BEGIN(all_circuits, origin_circuit_t *, circ) { + circuit_guard_state_t *state = origin_circuit_get_guard_state(circ); + if (BUG(state == NULL)) + continue; + + if (state->state == GUARD_CIRC_STATE_WAITING_FOR_BETTER_GUARD) { + ++n_waiting; + if (! best_waiting_circuit || + circ_state_has_higher_priority(circ, NULL, best_waiting_circuit)) { + best_waiting_circuit = circ; } - if (digest && tor_memeq(bridge->identity, digest, DIGEST_LEN)) - return bridge; } - SMARTLIST_FOREACH_END(bridge); - return NULL; -} + } SMARTLIST_FOREACH_END(circ); -/** If we have a bridge configured whose digest matches <b>digest</b>, or a - * bridge with no known digest whose address matches <b>addr</b>:<b>port</b>, - * return that bridge. Else return NULL. If <b>digest</b> is NULL, check for - * address/port matches only. */ -static bridge_info_t * -get_configured_bridge_by_addr_port_digest(const tor_addr_t *addr, - uint16_t port, - const char *digest) -{ - if (!bridge_list) - return NULL; - SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge) - { - if ((tor_digest_is_zero(bridge->identity) || digest == NULL) && - !tor_addr_compare(&bridge->addr, addr, CMP_EXACT) && - bridge->port == port) - return bridge; - if (digest && tor_memeq(bridge->identity, digest, DIGEST_LEN)) - return bridge; + if (! best_waiting_circuit) { + log_debug(LD_GUARD, "Considered upgrading guard-stalled circuits, " + "but didn't find any."); + goto no_change; + } + + /* We'll need to keep track of what restrictions were used when picking this + * circuit, so that we don't allow any circuit without those restrictions to + * block it. */ + const entry_guard_restriction_t *rst_on_best_waiting = + origin_circuit_get_guard_state(best_waiting_circuit)->restrictions; + + /* First look at the complete circuits: Do any block this circuit? */ + SMARTLIST_FOREACH_BEGIN(all_circuits, origin_circuit_t *, circ) { + /* "C2 "blocks" C1 if: + * C2 obeys all the restrictions that C1 had to obey, AND + * C2 has higher priority than C1, AND + * Either C2 is <complete>, or C2 is <waiting_for_better_guard>, + or C2 has been <usable_if_no_better_guard> for no more than + {NONPRIMARY_GUARD_CONNECT_TIMEOUT} seconds." + */ + circuit_guard_state_t *state = origin_circuit_get_guard_state(circ); + if BUG((state == NULL)) + continue; + if (state->state != GUARD_CIRC_STATE_COMPLETE) + continue; + ++n_complete; + if (circ_state_has_higher_priority(circ, rst_on_best_waiting, + best_waiting_circuit)) + ++n_complete_blocking; + } SMARTLIST_FOREACH_END(circ); + + if (n_complete_blocking) { + log_debug(LD_GUARD, "Considered upgrading guard-stalled circuits: found " + "%d complete and %d guard-stalled. At least one complete " + "circuit had higher priority, so not upgrading.", + n_complete, n_waiting); + goto no_change; + } + + /* " * If any circuit C1 is <waiting_for_better_guard>, AND: + * All primary guards have reachable status of <no>. + * There is no circuit C2 that "blocks" C1. + Then, upgrade C1 to <complete>."" + */ + int n_blockers_found = 0; + const time_t state_set_at_cutoff = + approx_time() - get_nonprimary_guard_connect_timeout(); + SMARTLIST_FOREACH_BEGIN(all_circuits, origin_circuit_t *, circ) { + circuit_guard_state_t *state = origin_circuit_get_guard_state(circ); + if (BUG(state == NULL)) + continue; + if (state->state != GUARD_CIRC_STATE_USABLE_IF_NO_BETTER_GUARD) + continue; + if (state->state_set_at <= state_set_at_cutoff) + continue; + if (circ_state_has_higher_priority(circ, rst_on_best_waiting, + best_waiting_circuit)) + ++n_blockers_found; + } SMARTLIST_FOREACH_END(circ); + + if (n_blockers_found) { + log_debug(LD_GUARD, "Considered upgrading guard-stalled circuits: found " + "%d guard-stalled, but %d pending circuit(s) had higher " + "guard priority, so not upgrading.", + n_waiting, n_blockers_found); + goto no_change; + } + + /* Okay. We have a best waiting circuit, and we aren't waiting for + anything better. Add all circuits with that priority to the + list, and call them COMPLETE. */ + int n_succeeded = 0; + SMARTLIST_FOREACH_BEGIN(all_circuits, origin_circuit_t *, circ) { + circuit_guard_state_t *state = origin_circuit_get_guard_state(circ); + if (BUG(state == NULL)) + continue; + if (circ != best_waiting_circuit && rst_on_best_waiting) { + /* Can't upgrade other circ with same priority as best; might + be blocked. */ + continue; } - SMARTLIST_FOREACH_END(bridge); - return NULL; -} + if (state->state != GUARD_CIRC_STATE_WAITING_FOR_BETTER_GUARD) + continue; + if (circ_state_has_higher_priority(best_waiting_circuit, NULL, circ)) + continue; -/** If we have a bridge configured whose digest matches <b>digest</b>, or a - * bridge with no known digest whose address matches <b>addr</b>:<b>port</b>, - * return 1. Else return 0. If <b>digest</b> is NULL, check for - * address/port matches only. */ -int -addr_is_a_configured_bridge(const tor_addr_t *addr, - uint16_t port, - const char *digest) -{ - tor_assert(addr); - return get_configured_bridge_by_addr_port_digest(addr, port, digest) ? 1 : 0; -} + state->state = GUARD_CIRC_STATE_COMPLETE; + state->state_set_at = approx_time(); + smartlist_add(newly_complete_out, circ); + ++n_succeeded; + } SMARTLIST_FOREACH_END(circ); -/** If we have a bridge configured whose digest matches - * <b>ei->identity_digest</b>, or a bridge with no known digest whose address - * matches <b>ei->addr</b>:<b>ei->port</b>, return 1. Else return 0. - * If <b>ei->onion_key</b> is NULL, check for address/port matches only. */ -int -extend_info_is_a_configured_bridge(const extend_info_t *ei) -{ - const char *digest = ei->onion_key ? ei->identity_digest : NULL; - return addr_is_a_configured_bridge(&ei->addr, ei->port, digest); -} + log_info(LD_GUARD, "Considered upgrading guard-stalled circuits: found " + "%d guard-stalled, %d complete. %d of the guard-stalled " + "circuit(s) had high enough priority to upgrade.", + n_waiting, n_complete, n_succeeded); -/** Wrapper around get_configured_bridge_by_addr_port_digest() to look - * it up via router descriptor <b>ri</b>. */ -static bridge_info_t * -get_configured_bridge_by_routerinfo(const routerinfo_t *ri) -{ - bridge_info_t *bi = NULL; - smartlist_t *orports = router_get_all_orports(ri); - bi = get_configured_bridge_by_orports_digest(ri->cache_info.identity_digest, - orports); - SMARTLIST_FOREACH(orports, tor_addr_port_t *, p, tor_free(p)); - smartlist_free(orports); - return bi; + tor_assert_nonfatal(n_succeeded >= 1); + smartlist_free(all_circuits); + return 1; + + no_change: + smartlist_free(all_circuits); + return 0; } -/** Return 1 if <b>ri</b> is one of our known bridges, else 0. */ +/** + * Return true iff the circuit whose state is <b>guard_state</b> should + * expire. + */ int -routerinfo_is_a_configured_bridge(const routerinfo_t *ri) +entry_guard_state_should_expire(circuit_guard_state_t *guard_state) { - return get_configured_bridge_by_routerinfo(ri) ? 1 : 0; + if (guard_state == NULL) + return 0; + const time_t expire_if_waiting_since = + approx_time() - get_nonprimary_guard_idle_timeout(); + return (guard_state->state == GUARD_CIRC_STATE_WAITING_FOR_BETTER_GUARD + && guard_state->state_set_at < expire_if_waiting_since); } -/** Return 1 if <b>node</b> is one of our configured bridges, else 0. */ +/** + * Update all derived pieces of the guard selection state in <b>gs</b>. + * Return true iff we should stop using all previously generated circuits. + */ int -node_is_a_configured_bridge(const node_t *node) +entry_guards_update_all(guard_selection_t *gs) { - int retval = 0; - smartlist_t *orports = node_get_all_orports(node); - retval = get_configured_bridge_by_orports_digest(node->identity, - orports) != NULL; - SMARTLIST_FOREACH(orports, tor_addr_port_t *, p, tor_free(p)); - smartlist_free(orports); - return retval; + sampled_guards_update_from_consensus(gs); + entry_guards_update_filtered_sets(gs); + entry_guards_update_confirmed(gs); + entry_guards_update_primary(gs); + return 0; } -/** We made a connection to a router at <b>addr</b>:<b>port</b> - * without knowing its digest. Its digest turned out to be <b>digest</b>. - * If it was a bridge, and we still don't know its digest, record it. +/** + * Return a newly allocated string for encoding the persistent parts of + * <b>guard</b> to the state file. */ -void -learned_router_identity(const tor_addr_t *addr, uint16_t port, - const char *digest) -{ - bridge_info_t *bridge = - get_configured_bridge_by_addr_port_digest(addr, port, digest); - if (bridge && tor_digest_is_zero(bridge->identity)) { - char *transport_info = NULL; - const char *transport_name = - find_transport_name_by_bridge_addrport(addr, port); - if (transport_name) - tor_asprintf(&transport_info, " (with transport '%s')", transport_name); +STATIC char * +entry_guard_encode_for_state(entry_guard_t *guard) +{ + /* + * The meta-format we use is K=V K=V K=V... where K can be any + * characters excepts space and =, and V can be any characters except + * space. The order of entries is not allowed to matter. + * Unrecognized K=V entries are persisted; recognized but erroneous + * entries are corrected. + */ - memcpy(bridge->identity, digest, DIGEST_LEN); - log_notice(LD_DIR, "Learned fingerprint %s for bridge %s%s.", - hex_str(digest, DIGEST_LEN), fmt_addrport(addr, port), - transport_info ? transport_info : ""); - tor_free(transport_info); + smartlist_t *result = smartlist_new(); + char tbuf[ISO_TIME_LEN+1]; + + tor_assert(guard); + + smartlist_add_asprintf(result, "in=%s", guard->selection_name); + smartlist_add_asprintf(result, "rsa_id=%s", + hex_str(guard->identity, DIGEST_LEN)); + if (guard->bridge_addr) { + smartlist_add_asprintf(result, "bridge_addr=%s:%d", + fmt_and_decorate_addr(&guard->bridge_addr->addr), + guard->bridge_addr->port); + } + if (strlen(guard->nickname) && is_legal_nickname(guard->nickname)) { + smartlist_add_asprintf(result, "nickname=%s", guard->nickname); } -} -/** Return true if <b>bridge</b> has the same identity digest as - * <b>digest</b>. If <b>digest</b> is NULL, it matches - * bridges with unspecified identity digests. */ -static int -bridge_has_digest(const bridge_info_t *bridge, const char *digest) -{ - if (digest) - return tor_memeq(digest, bridge->identity, DIGEST_LEN); - else - return tor_digest_is_zero(bridge->identity); + format_iso_time_nospace(tbuf, guard->sampled_on_date); + smartlist_add_asprintf(result, "sampled_on=%s", tbuf); + + if (guard->sampled_by_version) { + smartlist_add_asprintf(result, "sampled_by=%s", + guard->sampled_by_version); + } + + if (guard->unlisted_since_date > 0) { + format_iso_time_nospace(tbuf, guard->unlisted_since_date); + smartlist_add_asprintf(result, "unlisted_since=%s", tbuf); + } + + smartlist_add_asprintf(result, "listed=%d", + (int)guard->currently_listed); + + if (guard->confirmed_idx >= 0) { + format_iso_time_nospace(tbuf, guard->confirmed_on_date); + smartlist_add_asprintf(result, "confirmed_on=%s", tbuf); + + smartlist_add_asprintf(result, "confirmed_idx=%d", guard->confirmed_idx); + } + + const double EPSILON = 1.0e-6; + + /* Make a copy of the pathbias object, since we will want to update + some of them */ + guard_pathbias_t *pb = tor_memdup(&guard->pb, sizeof(*pb)); + pb->use_successes = pathbias_get_use_success_count(guard); + pb->successful_circuits_closed = pathbias_get_close_success_count(guard); + + #define PB_FIELD(field) do { \ + if (pb->field >= EPSILON) { \ + smartlist_add_asprintf(result, "pb_" #field "=%f", pb->field); \ + } \ + } while (0) + PB_FIELD(use_attempts); + PB_FIELD(use_successes); + PB_FIELD(circ_attempts); + PB_FIELD(circ_successes); + PB_FIELD(successful_circuits_closed); + PB_FIELD(collapsed_circuits); + PB_FIELD(unusable_circuits); + PB_FIELD(timeouts); + tor_free(pb); +#undef PB_FIELD + + if (guard->extra_state_fields) + smartlist_add_strdup(result, guard->extra_state_fields); + + char *joined = smartlist_join_strings(result, " ", 0, NULL); + SMARTLIST_FOREACH(result, char *, cp, tor_free(cp)); + smartlist_free(result); + + return joined; } -/** We are about to add a new bridge at <b>addr</b>:<b>port</b>, with optional - * <b>digest</b> and <b>transport_name</b>. Mark for removal any previously - * existing bridge with the same address and port, and warn the user as - * appropriate. +/** + * Given a string generated by entry_guard_encode_for_state(), parse it + * (if possible) and return an entry_guard_t object for it. Return NULL + * on complete failure. */ -static void -bridge_resolve_conflicts(const tor_addr_t *addr, uint16_t port, - const char *digest, const char *transport_name) -{ - /* Iterate the already-registered bridge list: +STATIC entry_guard_t * +entry_guard_parse_from_state(const char *s) +{ + /* Unrecognized entries get put in here. */ + smartlist_t *extra = smartlist_new(); + + /* These fields get parsed from the string. */ + char *in = NULL; + char *rsa_id = NULL; + char *nickname = NULL; + char *sampled_on = NULL; + char *sampled_by = NULL; + char *unlisted_since = NULL; + char *listed = NULL; + char *confirmed_on = NULL; + char *confirmed_idx = NULL; + char *bridge_addr = NULL; + + // pathbias + char *pb_use_attempts = NULL; + char *pb_use_successes = NULL; + char *pb_circ_attempts = NULL; + char *pb_circ_successes = NULL; + char *pb_successful_circuits_closed = NULL; + char *pb_collapsed_circuits = NULL; + char *pb_unusable_circuits = NULL; + char *pb_timeouts = NULL; + + /* Split up the entries. Put the ones we know about in strings and the + * rest in "extra". */ + { + smartlist_t *entries = smartlist_new(); + + strmap_t *vals = strmap_new(); // Maps keyword to location +#define FIELD(f) \ + strmap_set(vals, #f, &f); + FIELD(in); + FIELD(rsa_id); + FIELD(nickname); + FIELD(sampled_on); + FIELD(sampled_by); + FIELD(unlisted_since); + FIELD(listed); + FIELD(confirmed_on); + FIELD(confirmed_idx); + FIELD(bridge_addr); + FIELD(pb_use_attempts); + FIELD(pb_use_successes); + FIELD(pb_circ_attempts); + FIELD(pb_circ_successes); + FIELD(pb_successful_circuits_closed); + FIELD(pb_collapsed_circuits); + FIELD(pb_unusable_circuits); + FIELD(pb_timeouts); +#undef FIELD + + smartlist_split_string(entries, s, " ", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + + SMARTLIST_FOREACH_BEGIN(entries, char *, entry) { + const char *eq = strchr(entry, '='); + if (!eq) { + smartlist_add(extra, entry); + continue; + } + char *key = tor_strndup(entry, eq-entry); + char **target = strmap_get(vals, key); + if (target == NULL || *target != NULL) { + /* unrecognized or already set */ + smartlist_add(extra, entry); + tor_free(key); + continue; + } - If you find a bridge with the same adress and port, mark it for - removal. It doesn't make sense to have two active bridges with - the same IP:PORT. If the bridge in question has a different - digest or transport than <b>digest</b>/<b>transport_name</b>, - it's probably a misconfiguration and we should warn the user. - */ - SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge) { - if (bridge->marked_for_removal) - continue; + *target = tor_strdup(eq+1); + tor_free(key); + tor_free(entry); + } SMARTLIST_FOREACH_END(entry); - if (tor_addr_eq(&bridge->addr, addr) && (bridge->port == port)) { - - bridge->marked_for_removal = 1; - - if (!bridge_has_digest(bridge, digest) || - strcmp_opt(bridge->transport_name, transport_name)) { - /* warn the user */ - char *bridge_description_new, *bridge_description_old; - tor_asprintf(&bridge_description_new, "%s:%s:%s", - fmt_addrport(addr, port), - digest ? hex_str(digest, DIGEST_LEN) : "", - transport_name ? transport_name : ""); - tor_asprintf(&bridge_description_old, "%s:%s:%s", - fmt_addrport(&bridge->addr, bridge->port), - tor_digest_is_zero(bridge->identity) ? - "" : hex_str(bridge->identity,DIGEST_LEN), - bridge->transport_name ? bridge->transport_name : ""); - - log_warn(LD_GENERAL,"Tried to add bridge '%s', but we found a conflict" - " with the already registered bridge '%s'. We will discard" - " the old bridge and keep '%s'. If this is not what you" - " wanted, please change your configuration file accordingly.", - bridge_description_new, bridge_description_old, - bridge_description_new); - - tor_free(bridge_description_new); - tor_free(bridge_description_old); - } - } - } SMARTLIST_FOREACH_END(bridge); -} + smartlist_free(entries); + strmap_free(vals, NULL); + } -/** Return True if we have a bridge that uses a transport with name - * <b>transport_name</b>. */ -MOCK_IMPL(int, -transport_is_needed, (const char *transport_name)) -{ - if (!bridge_list) - return 0; + entry_guard_t *guard = tor_malloc_zero(sizeof(entry_guard_t)); + guard->is_persistent = 1; - SMARTLIST_FOREACH_BEGIN(bridge_list, const bridge_info_t *, bridge) { - if (bridge->transport_name && - !strcmp(bridge->transport_name, transport_name)) - return 1; - } SMARTLIST_FOREACH_END(bridge); + if (in == NULL) { + log_warn(LD_CIRC, "Guard missing 'in' field"); + goto err; + } - return 0; -} + guard->selection_name = in; + in = NULL; -/** Register the bridge information in <b>bridge_line</b> to the - * bridge subsystem. Steals reference of <b>bridge_line</b>. */ -void -bridge_add_from_config(bridge_line_t *bridge_line) -{ - bridge_info_t *b; + if (rsa_id == NULL) { + log_warn(LD_CIRC, "Guard missing RSA ID field"); + goto err; + } - { /* Log the bridge we are about to register: */ - log_debug(LD_GENERAL, "Registering bridge at %s (transport: %s) (%s)", - fmt_addrport(&bridge_line->addr, bridge_line->port), - bridge_line->transport_name ? - bridge_line->transport_name : "no transport", - tor_digest_is_zero(bridge_line->digest) ? - "no key listed" : hex_str(bridge_line->digest, DIGEST_LEN)); + /* Process the identity and nickname. */ + if (base16_decode(guard->identity, sizeof(guard->identity), + rsa_id, strlen(rsa_id)) != DIGEST_LEN) { + log_warn(LD_CIRC, "Unable to decode guard identity %s", escaped(rsa_id)); + goto err; + } - if (bridge_line->socks_args) { /* print socks arguments */ - int i = 0; + if (nickname) { + strlcpy(guard->nickname, nickname, sizeof(guard->nickname)); + } else { + guard->nickname[0]='$'; + base16_encode(guard->nickname+1, sizeof(guard->nickname)-1, + guard->identity, DIGEST_LEN); + } - tor_assert(smartlist_len(bridge_line->socks_args) > 0); + if (bridge_addr) { + tor_addr_port_t res; + memset(&res, 0, sizeof(res)); + int r = tor_addr_port_parse(LOG_WARN, bridge_addr, + &res.addr, &res.port, -1); + if (r == 0) + guard->bridge_addr = tor_memdup(&res, sizeof(res)); + /* On error, we already warned. */ + } - log_debug(LD_GENERAL, "Bridge uses %d SOCKS arguments:", - smartlist_len(bridge_line->socks_args)); - SMARTLIST_FOREACH(bridge_line->socks_args, const char *, arg, - log_debug(LD_CONFIG, "%d: %s", ++i, arg)); + /* Process the various time fields. */ + +#define HANDLE_TIME(field) do { \ + if (field) { \ + int r = parse_iso_time_nospace(field, &field ## _time); \ + if (r < 0) { \ + log_warn(LD_CIRC, "Unable to parse %s %s from guard", \ + #field, escaped(field)); \ + field##_time = -1; \ + } \ + } \ + } while (0) + + time_t sampled_on_time = 0; + time_t unlisted_since_time = 0; + time_t confirmed_on_time = 0; + + HANDLE_TIME(sampled_on); + HANDLE_TIME(unlisted_since); + HANDLE_TIME(confirmed_on); + + if (sampled_on_time <= 0) + sampled_on_time = approx_time(); + if (unlisted_since_time < 0) + unlisted_since_time = 0; + if (confirmed_on_time < 0) + confirmed_on_time = 0; + + #undef HANDLE_TIME + + guard->sampled_on_date = sampled_on_time; + guard->unlisted_since_date = unlisted_since_time; + guard->confirmed_on_date = confirmed_on_time; + + /* Take sampled_by_version verbatim. */ + guard->sampled_by_version = sampled_by; + sampled_by = NULL; /* prevent free */ + + /* Listed is a boolean */ + if (listed && strcmp(listed, "0")) + guard->currently_listed = 1; + + /* The index is a nonnegative integer. */ + guard->confirmed_idx = -1; + if (confirmed_idx) { + int ok=1; + long idx = tor_parse_long(confirmed_idx, 10, 0, INT_MAX, &ok, NULL); + if (! ok) { + log_warn(LD_GUARD, "Guard has invalid confirmed_idx %s", + escaped(confirmed_idx)); + } else { + guard->confirmed_idx = (int)idx; } } - bridge_resolve_conflicts(&bridge_line->addr, - bridge_line->port, - bridge_line->digest, - bridge_line->transport_name); + /* Anything we didn't recognize gets crammed together */ + if (smartlist_len(extra) > 0) { + guard->extra_state_fields = smartlist_join_strings(extra, " ", 0, NULL); + } - b = tor_malloc_zero(sizeof(bridge_info_t)); - tor_addr_copy(&b->addr, &bridge_line->addr); - b->port = bridge_line->port; - memcpy(b->identity, bridge_line->digest, DIGEST_LEN); - if (bridge_line->transport_name) - b->transport_name = bridge_line->transport_name; - b->fetch_status.schedule = DL_SCHED_BRIDGE; - b->fetch_status.backoff = DL_SCHED_RANDOM_EXPONENTIAL; - b->socks_args = bridge_line->socks_args; - if (!bridge_list) - bridge_list = smartlist_new(); + /* initialize non-persistent fields */ + guard->is_reachable = GUARD_REACHABLE_MAYBE; + +#define PB_FIELD(field) \ + do { \ + if (pb_ ## field) { \ + int ok = 1; \ + double r = tor_parse_double(pb_ ## field, 0.0, 1e9, &ok, NULL); \ + if (! ok) { \ + log_warn(LD_CIRC, "Guard has invalid pb_%s %s", \ + #field, pb_ ## field); \ + } else { \ + guard->pb.field = r; \ + } \ + } \ + } while (0) + PB_FIELD(use_attempts); + PB_FIELD(use_successes); + PB_FIELD(circ_attempts); + PB_FIELD(circ_successes); + PB_FIELD(successful_circuits_closed); + PB_FIELD(collapsed_circuits); + PB_FIELD(unusable_circuits); + PB_FIELD(timeouts); +#undef PB_FIELD + + pathbias_check_use_success_count(guard); + pathbias_check_close_success_count(guard); + + /* We update everything on this guard later, after we've parsed + * everything. */ + + goto done; + + err: + // only consider it an error if the guard state was totally unparseable. + entry_guard_free(guard); + guard = NULL; - tor_free(bridge_line); /* Deallocate bridge_line now. */ + done: + tor_free(in); + tor_free(rsa_id); + tor_free(nickname); + tor_free(sampled_on); + tor_free(sampled_by); + tor_free(unlisted_since); + tor_free(listed); + tor_free(confirmed_on); + tor_free(confirmed_idx); + tor_free(bridge_addr); + tor_free(pb_use_attempts); + tor_free(pb_use_successes); + tor_free(pb_circ_attempts); + tor_free(pb_circ_successes); + tor_free(pb_successful_circuits_closed); + tor_free(pb_collapsed_circuits); + tor_free(pb_unusable_circuits); + tor_free(pb_timeouts); + + SMARTLIST_FOREACH(extra, char *, cp, tor_free(cp)); + smartlist_free(extra); + + return guard; +} - smartlist_add(bridge_list, b); +/** + * Replace the Guards entries in <b>state</b> with a list of all our sampled + * guards. + */ +static void +entry_guards_update_guards_in_state(or_state_t *state) +{ + if (!guard_contexts) + return; + config_line_t *lines = NULL; + config_line_t **nextline = &lines; + + SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) { + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + if (guard->is_persistent == 0) + continue; + *nextline = tor_malloc_zero(sizeof(config_line_t)); + (*nextline)->key = tor_strdup("Guard"); + (*nextline)->value = entry_guard_encode_for_state(guard); + nextline = &(*nextline)->next; + } SMARTLIST_FOREACH_END(guard); + } SMARTLIST_FOREACH_END(gs); + + config_free_lines(state->Guard); + state->Guard = lines; } -/** Return true iff <b>routerset</b> contains the bridge <b>bridge</b>. */ +/** + * Replace our sampled guards from the Guards entries in <b>state</b>. Return 0 + * on success, -1 on failure. (If <b>set</b> is true, replace nothing -- only + * check whether replacing would work.) + */ static int -routerset_contains_bridge(const routerset_t *routerset, - const bridge_info_t *bridge) +entry_guards_load_guards_from_state(or_state_t *state, int set) +{ + const config_line_t *line = state->Guard; + int n_errors = 0; + + if (!guard_contexts) + guard_contexts = smartlist_new(); + + /* Wipe all our existing guard info. (we shouldn't have any, but + * let's be safe.) */ + if (set) { + SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) { + guard_selection_free(gs); + if (curr_guard_context == gs) + curr_guard_context = NULL; + SMARTLIST_DEL_CURRENT(guard_contexts, gs); + } SMARTLIST_FOREACH_END(gs); + } + + for ( ; line != NULL; line = line->next) { + entry_guard_t *guard = entry_guard_parse_from_state(line->value); + if (guard == NULL) { + ++n_errors; + continue; + } + tor_assert(guard->selection_name); + if (!strcmp(guard->selection_name, "legacy")) { + ++n_errors; + entry_guard_free(guard); + continue; + } + + if (set) { + guard_selection_t *gs; + gs = get_guard_selection_by_name(guard->selection_name, + GS_TYPE_INFER, 1); + tor_assert(gs); + smartlist_add(gs->sampled_entry_guards, guard); + guard->in_selection = gs; + } else { + entry_guard_free(guard); + } + } + + if (set) { + SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) { + entry_guards_update_all(gs); + } SMARTLIST_FOREACH_END(gs); + } + return n_errors ? -1 : 0; +} + +/** If <b>digest</b> matches the identity of any node in the + * entry_guards list for the provided guard selection state, + return that node. Else return NULL. */ +entry_guard_t * +entry_guard_get_by_id_digest_for_guard_selection(guard_selection_t *gs, + const char *digest) { - int result; - extend_info_t *extinfo; - tor_assert(bridge); - if (!routerset) - return 0; + return get_sampled_guard_with_id(gs, (const uint8_t*)digest); +} - extinfo = extend_info_new( - NULL, bridge->identity, NULL, NULL, &bridge->addr, bridge->port); - result = routerset_contains_extendinfo(routerset, extinfo); - extend_info_free(extinfo); - return result; +/** Return the node_t associated with a single entry_guard_t. May + * return NULL if the guard is not currently in the consensus. */ +const node_t * +entry_guard_find_node(const entry_guard_t *guard) +{ + tor_assert(guard); + return node_get_by_id(guard->identity); } -/** If <b>digest</b> is one of our known bridges, return it. */ -static bridge_info_t * -find_bridge_by_digest(const char *digest) +/** If <b>digest</b> matches the identity of any node in the + * entry_guards list for the default guard selection state, + return that node. Else return NULL. */ +entry_guard_t * +entry_guard_get_by_id_digest(const char *digest) { - SMARTLIST_FOREACH(bridge_list, bridge_info_t *, bridge, - { - if (tor_memeq(bridge->identity, digest, DIGEST_LEN)) - return bridge; - }); - return NULL; + return entry_guard_get_by_id_digest_for_guard_selection( + get_guard_selection_info(), digest); } -/** Given the <b>addr</b> and <b>port</b> of a bridge, if that bridge - * supports a pluggable transport, return its name. Otherwise, return - * NULL. */ -const char * -find_transport_name_by_bridge_addrport(const tor_addr_t *addr, uint16_t port) +/** We are about to connect to bridge with identity <b>digest</b> to fetch its + * descriptor. Create a new guard state for this connection and return it. */ +circuit_guard_state_t * +get_guard_state_for_bridge_desc_fetch(const char *digest) { - if (!bridge_list) + circuit_guard_state_t *guard_state = NULL; + entry_guard_t *guard = NULL; + + guard = entry_guard_get_by_id_digest_for_guard_selection( + get_guard_selection_info(), digest); + if (!guard) { return NULL; + } - SMARTLIST_FOREACH_BEGIN(bridge_list, const bridge_info_t *, bridge) { - if (tor_addr_eq(&bridge->addr, addr) && - (bridge->port == port)) - return bridge->transport_name; - } SMARTLIST_FOREACH_END(bridge); + /* Update the guard last_tried_to_connect time since it's checked by the + * guard susbsystem. */ + guard->last_tried_to_connect = approx_time(); - return NULL; + /* Create the guard state */ + guard_state = tor_malloc_zero(sizeof(circuit_guard_state_t)); + guard_state->guard = entry_guard_handle_new(guard); + guard_state->state = GUARD_CIRC_STATE_USABLE_ON_COMPLETION; + guard_state->state_set_at = approx_time(); + guard_state->restrictions = NULL; + + return guard_state; } -/** If <b>addr</b> and <b>port</b> match the address and port of a - * bridge of ours that uses pluggable transports, place its transport - * in <b>transport</b>. - * - * Return 0 on success (found a transport, or found a bridge with no - * transport, or found no bridge); return -1 if we should be using a - * transport, but the transport could not be found. +/** Release all storage held by <b>e</b>. */ +STATIC void +entry_guard_free(entry_guard_t *e) +{ + if (!e) + return; + entry_guard_handles_clear(e); + tor_free(e->sampled_by_version); + tor_free(e->extra_state_fields); + tor_free(e->selection_name); + tor_free(e->bridge_addr); + tor_free(e); +} + +/** Return 0 if we're fine adding arbitrary routers out of the + * directory to our entry guard list, or return 1 if we have a + * list already and we must stick to it. */ int -get_transport_by_bridge_addrport(const tor_addr_t *addr, uint16_t port, - const transport_t **transport) +entry_list_is_constrained(const or_options_t *options) { - *transport = NULL; - if (!bridge_list) - return 0; - - SMARTLIST_FOREACH_BEGIN(bridge_list, const bridge_info_t *, bridge) { - if (tor_addr_eq(&bridge->addr, addr) && - (bridge->port == port)) { /* bridge matched */ - if (bridge->transport_name) { /* it also uses pluggable transports */ - *transport = transport_get_by_name(bridge->transport_name); - if (*transport == NULL) { /* it uses pluggable transports, but - the transport could not be found! */ - return -1; - } - return 0; - } else { /* bridge matched, but it doesn't use transports. */ - break; - } - } - } SMARTLIST_FOREACH_END(bridge); - - *transport = NULL; + // XXXX #21425 look at the current selection. + if (options->EntryNodes) + return 1; + if (options->UseBridges) + return 1; return 0; } -/** Return a smartlist containing all the SOCKS arguments that we - * should pass to the SOCKS proxy. */ -const smartlist_t * -get_socks_args_by_bridge_addrport(const tor_addr_t *addr, uint16_t port) +/** Return the number of bridges that have descriptors that are marked with + * purpose 'bridge' and are running. + */ +int +num_bridges_usable(void) { - bridge_info_t *bridge = get_configured_bridge_by_addr_port_digest(addr, - port, - NULL); - return bridge ? bridge->socks_args : NULL; + int n_options = 0; + + tor_assert(get_options()->UseBridges); + guard_selection_t *gs = get_guard_selection_info(); + tor_assert(gs->type == GS_TYPE_BRIDGE); + + SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) { + if (guard->is_reachable == GUARD_REACHABLE_NO) + continue; + if (tor_digest_is_zero(guard->identity)) + continue; + const node_t *node = node_get_by_id(guard->identity); + if (node && node->ri) + ++n_options; + } SMARTLIST_FOREACH_END(guard); + + return n_options; } -/** We need to ask <b>bridge</b> for its server descriptor. */ +/** Check the pathbias use success count of <b>node</b> and disable it if it + * goes over our thresholds. */ static void -launch_direct_bridge_descriptor_fetch(bridge_info_t *bridge) +pathbias_check_use_success_count(entry_guard_t *node) { const or_options_t *options = get_options(); - - if (connection_get_by_type_addr_port_purpose( - CONN_TYPE_DIR, &bridge->addr, bridge->port, - DIR_PURPOSE_FETCH_SERVERDESC)) - return; /* it's already on the way */ - - if (routerset_contains_bridge(options->ExcludeNodes, bridge)) { - download_status_mark_impossible(&bridge->fetch_status); - log_warn(LD_APP, "Not using bridge at %s: it is in ExcludeNodes.", - safe_str_client(fmt_and_decorate_addr(&bridge->addr))); - return; + const double EPSILON = 1.0e-9; + + /* Note: We rely on the < comparison here to allow us to set a 0 + * rate and disable the feature entirely. If refactoring, don't + * change to <= */ + if (node->pb.use_attempts > EPSILON && + pathbias_get_use_success_count(node)/node->pb.use_attempts + < pathbias_get_extreme_use_rate(options) && + pathbias_get_dropguards(options)) { + node->pb.path_bias_disabled = 1; + log_info(LD_GENERAL, + "Path use bias is too high (%f/%f); disabling node %s", + node->pb.circ_successes, node->pb.circ_attempts, + node->nickname); } +} - /* Until we get a descriptor for the bridge, we only know one address for - * it. */ - if (!fascist_firewall_allows_address_addr(&bridge->addr, bridge->port, - FIREWALL_OR_CONNECTION, 0, 0)) { - log_notice(LD_CONFIG, "Tried to fetch a descriptor directly from a " - "bridge, but that bridge is not reachable through our " - "firewall."); - return; +/** Check the pathbias close count of <b>node</b> and disable it if it goes + * over our thresholds. */ +static void +pathbias_check_close_success_count(entry_guard_t *node) +{ + const or_options_t *options = get_options(); + const double EPSILON = 1.0e-9; + + /* Note: We rely on the < comparison here to allow us to set a 0 + * rate and disable the feature entirely. If refactoring, don't + * change to <= */ + if (node->pb.circ_attempts > EPSILON && + pathbias_get_close_success_count(node)/node->pb.circ_attempts + < pathbias_get_extreme_rate(options) && + pathbias_get_dropguards(options)) { + node->pb.path_bias_disabled = 1; + log_info(LD_GENERAL, + "Path bias is too high (%f/%f); disabling node %s", + node->pb.circ_successes, node->pb.circ_attempts, + node->nickname); } - - directory_initiate_command(&bridge->addr, bridge->port, - NULL, 0, /*no dirport*/ - bridge->identity, - DIR_PURPOSE_FETCH_SERVERDESC, - ROUTER_PURPOSE_BRIDGE, - DIRIND_ONEHOP, "authority.z", NULL, 0, 0); } -/** Fetching the bridge descriptor from the bridge authority returned a - * "not found". Fall back to trying a direct fetch. */ -void -retry_bridge_descriptor_fetch_directly(const char *digest) +/** Parse <b>state</b> and learn about the entry guards it describes. + * If <b>set</b> is true, and there are no errors, replace the guard + * list in the default guard selection context with what we find. + * On success, return 0. On failure, alloc into *<b>msg</b> a string + * describing the error, and return -1. + */ +int +entry_guards_parse_state(or_state_t *state, int set, char **msg) { - bridge_info_t *bridge = find_bridge_by_digest(digest); - if (!bridge) - return; /* not found? oh well. */ + entry_guards_dirty = 0; + int r1 = entry_guards_load_guards_from_state(state, set); + entry_guards_dirty = 0; - launch_direct_bridge_descriptor_fetch(bridge); + if (r1 < 0) { + if (msg && *msg == NULL) { + *msg = tor_strdup("parsing error"); + } + return -1; + } + return 0; } -/** For each bridge in our list for which we don't currently have a - * descriptor, fetch a new copy of its descriptor -- either directly - * from the bridge or via a bridge authority. */ +/** How long will we let a change in our guard nodes stay un-saved + * when we are trying to avoid disk writes? */ +#define SLOW_GUARD_STATE_FLUSH_TIME 600 +/** How long will we let a change in our guard nodes stay un-saved + * when we are not trying to avoid disk writes? */ +#define FAST_GUARD_STATE_FLUSH_TIME 30 + +/** Our list of entry guards has changed for a particular guard selection + * context, or some element of one of our entry guards has changed for one. + * Write the changes to disk within the next few minutes. + */ void -fetch_bridge_descriptors(const or_options_t *options, time_t now) +entry_guards_changed_for_guard_selection(guard_selection_t *gs) { - int num_bridge_auths = get_n_authorities(BRIDGE_DIRINFO); - int ask_bridge_directly; - int can_use_bridge_authority; + time_t when; - if (!bridge_list) - return; + tor_assert(gs != NULL); - /* If we still have unconfigured managed proxies, don't go and - connect to a bridge. */ - if (pt_proxies_configuration_pending()) - return; + entry_guards_dirty = 1; - SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge) - { - if (!download_status_is_ready(&bridge->fetch_status, now, - IMPOSSIBLE_TO_DOWNLOAD)) - continue; /* don't bother, no need to retry yet */ - if (routerset_contains_bridge(options->ExcludeNodes, bridge)) { - download_status_mark_impossible(&bridge->fetch_status); - log_warn(LD_APP, "Not using bridge at %s: it is in ExcludeNodes.", - safe_str_client(fmt_and_decorate_addr(&bridge->addr))); - continue; - } + if (get_options()->AvoidDiskWrites) + when = time(NULL) + SLOW_GUARD_STATE_FLUSH_TIME; + else + when = time(NULL) + FAST_GUARD_STATE_FLUSH_TIME; - /* schedule another fetch as if this one will fail, in case it does */ - download_status_failed(&bridge->fetch_status, 0); - - can_use_bridge_authority = !tor_digest_is_zero(bridge->identity) && - num_bridge_auths; - ask_bridge_directly = !can_use_bridge_authority || - !options->UpdateBridgesFromAuthority; - log_debug(LD_DIR, "ask_bridge_directly=%d (%d, %d, %d)", - ask_bridge_directly, tor_digest_is_zero(bridge->identity), - !options->UpdateBridgesFromAuthority, !num_bridge_auths); - - if (ask_bridge_directly && - !fascist_firewall_allows_address_addr(&bridge->addr, bridge->port, - FIREWALL_OR_CONNECTION, 0, - 0)) { - log_notice(LD_DIR, "Bridge at '%s' isn't reachable by our " - "firewall policy. %s.", - fmt_addrport(&bridge->addr, bridge->port), - can_use_bridge_authority ? - "Asking bridge authority instead" : "Skipping"); - if (can_use_bridge_authority) - ask_bridge_directly = 0; - else - continue; - } + /* or_state_save() will call entry_guards_update_state() and + entry_guards_update_guards_in_state() + */ + or_state_mark_dirty(get_or_state(), when); +} - if (ask_bridge_directly) { - /* we need to ask the bridge itself for its descriptor. */ - launch_direct_bridge_descriptor_fetch(bridge); - } else { - /* We have a digest and we want to ask an authority. We could - * combine all the requests into one, but that may give more - * hints to the bridge authority than we want to give. */ - char resource[10 + HEX_DIGEST_LEN]; - memcpy(resource, "fp/", 3); - base16_encode(resource+3, HEX_DIGEST_LEN+1, - bridge->identity, DIGEST_LEN); - memcpy(resource+3+HEX_DIGEST_LEN, ".z", 3); - log_info(LD_DIR, "Fetching bridge info '%s' from bridge authority.", - resource); - directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC, - ROUTER_PURPOSE_BRIDGE, resource, 0, DL_WANT_AUTHORITY); - } - } - SMARTLIST_FOREACH_END(bridge); +/** Our list of entry guards has changed for the default guard selection + * context, or some element of one of our entry guards has changed. Write + * the changes to disk within the next few minutes. + */ +void +entry_guards_changed(void) +{ + entry_guards_changed_for_guard_selection(get_guard_selection_info()); } -/** If our <b>bridge</b> is configured to be a different address than - * the bridge gives in <b>node</b>, rewrite the routerinfo - * we received to use the address we meant to use. Now we handle - * multihomed bridges better. +/** If the entry guard info has not changed, do nothing and return. + * Otherwise, free the EntryGuards piece of <b>state</b> and create + * a new one out of the global entry_guards list, and then mark + * <b>state</b> dirty so it will get saved to disk. */ -static void -rewrite_node_address_for_bridge(const bridge_info_t *bridge, node_t *node) +void +entry_guards_update_state(or_state_t *state) { - /* XXXX move this function. */ - /* XXXX overridden addresses should really live in the node_t, so that the - * routerinfo_t and the microdesc_t can be immutable. But we can only - * do that safely if we know that no function that connects to an OR - * does so through an address from any source other than node_get_addr(). - */ - tor_addr_t addr; - const or_options_t *options = get_options(); + entry_guards_dirty = 0; - if (node->ri) { - routerinfo_t *ri = node->ri; - tor_addr_from_ipv4h(&addr, ri->addr); + // Handles all guard info. + entry_guards_update_guards_in_state(state); - if ((!tor_addr_compare(&bridge->addr, &addr, CMP_EXACT) && - bridge->port == ri->or_port) || - (!tor_addr_compare(&bridge->addr, &ri->ipv6_addr, CMP_EXACT) && - bridge->port == ri->ipv6_orport)) { - /* they match, so no need to do anything */ - } else { - if (tor_addr_family(&bridge->addr) == AF_INET) { - ri->addr = tor_addr_to_ipv4h(&bridge->addr); - ri->or_port = bridge->port; - log_info(LD_DIR, - "Adjusted bridge routerinfo for '%s' to match configured " - "address %s:%d.", - ri->nickname, fmt_addr32(ri->addr), ri->or_port); - } else if (tor_addr_family(&bridge->addr) == AF_INET6) { - tor_addr_copy(&ri->ipv6_addr, &bridge->addr); - ri->ipv6_orport = bridge->port; - log_info(LD_DIR, - "Adjusted bridge routerinfo for '%s' to match configured " - "address %s.", - ri->nickname, fmt_addrport(&ri->ipv6_addr, ri->ipv6_orport)); - } else { - log_err(LD_BUG, "Address family not supported: %d.", - tor_addr_family(&bridge->addr)); - return; - } - } + entry_guards_dirty = 0; - if (options->ClientPreferIPv6ORPort == -1) { - /* Mark which address to use based on which bridge_t we got. */ - node->ipv6_preferred = (tor_addr_family(&bridge->addr) == AF_INET6 && - !tor_addr_is_null(&node->ri->ipv6_addr)); - } else { - /* Mark which address to use based on user preference */ - node->ipv6_preferred = (fascist_firewall_prefer_ipv6_orport(options) && - !tor_addr_is_null(&node->ri->ipv6_addr)); - } + if (!get_options()->AvoidDiskWrites) + or_state_mark_dirty(get_or_state(), 0); + entry_guards_dirty = 0; +} - /* XXXipv6 we lack support for falling back to another address for - the same relay, warn the user */ - if (!tor_addr_is_null(&ri->ipv6_addr)) { - tor_addr_port_t ap; - node_get_pref_orport(node, &ap); - log_notice(LD_CONFIG, - "Bridge '%s' has both an IPv4 and an IPv6 address. " - "Will prefer using its %s address (%s) based on %s.", - ri->nickname, - node->ipv6_preferred ? "IPv6" : "IPv4", - fmt_addrport(&ap.addr, ap.port), - options->ClientPreferIPv6ORPort == -1 ? - "the configured Bridge address" : - "ClientPreferIPv6ORPort"); - } +/** + * Format a single entry guard in the format expected by the controller. + * Return a newly allocated string. + */ +STATIC char * +getinfo_helper_format_single_entry_guard(const entry_guard_t *e) +{ + const char *status = NULL; + time_t when = 0; + const node_t *node; + char tbuf[ISO_TIME_LEN+1]; + char nbuf[MAX_VERBOSE_NICKNAME_LEN+1]; + + /* This is going to be a bit tricky, since the status + * codes weren't really intended for prop271 guards. + * + * XXXX use a more appropriate format for exporting this information + */ + if (e->confirmed_idx < 0) { + status = "never-connected"; + } else if (! e->currently_listed) { + when = e->unlisted_since_date; + status = "unusable"; + } else if (! e->is_filtered_guard) { + status = "unusable"; + } else if (e->is_reachable == GUARD_REACHABLE_NO) { + when = e->failing_since; + status = "down"; + } else { + status = "up"; } - if (node->rs) { - routerstatus_t *rs = node->rs; - tor_addr_from_ipv4h(&addr, rs->addr); - if (!tor_addr_compare(&bridge->addr, &addr, CMP_EXACT) && - bridge->port == rs->or_port) { - /* they match, so no need to do anything */ - } else { - rs->addr = tor_addr_to_ipv4h(&bridge->addr); - rs->or_port = bridge->port; - log_info(LD_DIR, - "Adjusted bridge routerstatus for '%s' to match " - "configured address %s.", - rs->nickname, fmt_addrport(&bridge->addr, rs->or_port)); - } + node = entry_guard_find_node(e); + if (node) { + node_get_verbose_nickname(node, nbuf); + } else { + nbuf[0] = '$'; + base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN); + /* e->nickname field is not very reliable if we don't know about + * this router any longer; don't include it. */ } -} -/** We just learned a descriptor for a bridge. See if that - * digest is in our entry guard list, and add it if not. */ -void -learned_bridge_descriptor(routerinfo_t *ri, int from_cache) -{ - tor_assert(ri); - tor_assert(ri->purpose == ROUTER_PURPOSE_BRIDGE); - if (get_options()->UseBridges) { - int first = num_bridges_usable() <= 1; - bridge_info_t *bridge = get_configured_bridge_by_routerinfo(ri); - time_t now = time(NULL); - router_set_status(ri->cache_info.identity_digest, 1); - - if (bridge) { /* if we actually want to use this one */ - node_t *node; - /* it's here; schedule its re-fetch for a long time from now. */ - if (!from_cache) - download_status_reset(&bridge->fetch_status); - - node = node_get_mutable_by_id(ri->cache_info.identity_digest); - tor_assert(node); - rewrite_node_address_for_bridge(bridge, node); - if (tor_digest_is_zero(bridge->identity)) { - memcpy(bridge->identity,ri->cache_info.identity_digest, DIGEST_LEN); - log_notice(LD_DIR, "Learned identity %s for bridge at %s:%d", - hex_str(bridge->identity, DIGEST_LEN), - fmt_and_decorate_addr(&bridge->addr), - (int) bridge->port); - } - add_an_entry_guard(node, 1, 1, 0, 0); - - log_notice(LD_DIR, "new bridge descriptor '%s' (%s): %s", ri->nickname, - from_cache ? "cached" : "fresh", router_describe(ri)); - /* set entry->made_contact so if it goes down we don't drop it from - * our entry node list */ - entry_guard_register_connect_status(ri->cache_info.identity_digest, - 1, 0, now); - if (first) { - routerlist_retry_directory_downloads(now); - } - } + char *result = NULL; + if (when) { + format_iso_time(tbuf, when); + tor_asprintf(&result, "%s %s %s\n", nbuf, status, tbuf); + } else { + tor_asprintf(&result, "%s %s\n", nbuf, status); } + return result; } -/** Return the number of bridges that have descriptors that - * are marked with purpose 'bridge' and are running. +/** If <b>question</b> is the string "entry-guards", then dump + * to *<b>answer</b> a newly allocated string describing all of + * the nodes in the global entry_guards list. See control-spec.txt + * for details. + * For backward compatibility, we also handle the string "helper-nodes". * - * We use this function to decide if we're ready to start building - * circuits through our bridges, or if we need to wait until the - * directory "server/authority" requests finish. */ + * XXX this should be totally redesigned after prop 271 too, and that's + * going to take some control spec work. + * */ int -any_bridge_descriptors_known(void) +getinfo_helper_entry_guards(control_connection_t *conn, + const char *question, char **answer, + const char **errmsg) { - tor_assert(get_options()->UseBridges); - return choose_random_entry(NULL) != NULL; + guard_selection_t *gs = get_guard_selection_info(); + + tor_assert(gs != NULL); + + (void) conn; + (void) errmsg; + + if (!strcmp(question,"entry-guards") || + !strcmp(question,"helper-nodes")) { + const smartlist_t *guards; + guards = gs->sampled_entry_guards; + + smartlist_t *sl = smartlist_new(); + + SMARTLIST_FOREACH_BEGIN(guards, const entry_guard_t *, e) { + char *cp = getinfo_helper_format_single_entry_guard(e); + smartlist_add(sl, cp); + } SMARTLIST_FOREACH_END(e); + *answer = smartlist_join_strings(sl, "", 0, NULL); + SMARTLIST_FOREACH(sl, char *, c, tor_free(c)); + smartlist_free(sl); + } + return 0; } -/** Return the number of bridges that have descriptors that are marked with - * purpose 'bridge' and are running. +/* Given the original bandwidth of a guard and its guardfraction, + * calculate how much bandwidth the guard should have as a guard and + * as a non-guard. + * + * Quoting from proposal236: + * + * Let Wpf denote the weight from the 'bandwidth-weights' line a + * client would apply to N for position p if it had the guard + * flag, Wpn the weight if it did not have the guard flag, and B the + * measured bandwidth of N in the consensus. Then instead of choosing + * N for position p proportionally to Wpf*B or Wpn*B, clients should + * choose N proportionally to F*Wpf*B + (1-F)*Wpn*B. + * + * This function fills the <b>guardfraction_bw</b> structure. It sets + * <b>guard_bw</b> to F*B and <b>non_guard_bw</b> to (1-F)*B. */ -static int -num_bridges_usable(void) +void +guard_get_guardfraction_bandwidth(guardfraction_bandwidth_t *guardfraction_bw, + int orig_bandwidth, + uint32_t guardfraction_percentage) { - int n_options = 0; - tor_assert(get_options()->UseBridges); - (void) choose_random_entry_impl(NULL, 0, 0, &n_options); - return n_options; + double guardfraction_fraction; + + /* Turn the percentage into a fraction. */ + tor_assert(guardfraction_percentage <= 100); + guardfraction_fraction = guardfraction_percentage / 100.0; + + long guard_bw = tor_lround(guardfraction_fraction * orig_bandwidth); + tor_assert(guard_bw <= INT_MAX); + + guardfraction_bw->guard_bw = (int) guard_bw; + + guardfraction_bw->non_guard_bw = orig_bandwidth - (int) guard_bw; } -/** Return a smartlist containing all bridge identity digests */ -MOCK_IMPL(smartlist_t *, -list_bridge_identities, (void)) +/** Helper: Update the status of all entry guards, in whatever algorithm + * is used. Return true if we should stop using all previously generated + * circuits, by calling circuit_mark_all_unused_circs() and + * circuit_mark_all_dirty_circs_as_unusable(). + */ +int +guards_update_all(void) { - smartlist_t *result = NULL; - char *digest_tmp; + int mark_circuits = 0; + if (update_guard_selection_choice(get_options())) + mark_circuits = 1; - if (get_options()->UseBridges && bridge_list) { - result = smartlist_new(); + tor_assert(curr_guard_context); - SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, b) { - digest_tmp = tor_malloc(DIGEST_LEN); - memcpy(digest_tmp, b->identity, DIGEST_LEN); - smartlist_add(result, digest_tmp); - } SMARTLIST_FOREACH_END(b); - } + if (entry_guards_update_all(curr_guard_context)) + mark_circuits = 1; - return result; + return mark_circuits; } -/** Get the download status for a bridge descriptor given its identity */ -MOCK_IMPL(download_status_t *, -get_bridge_dl_status_by_id, (const char *digest)) +/** Helper: pick a guard for a circuit, with whatever algorithm is + used. */ +const node_t * +guards_choose_guard(cpath_build_state_t *state, + circuit_guard_state_t **guard_state_out) +{ + const node_t *r = NULL; + const uint8_t *exit_id = NULL; + entry_guard_restriction_t *rst = NULL; + if (state && (exit_id = build_state_get_exit_rsa_id(state))) { + /* We're building to a targeted exit node, so that node can't be + * chosen as our guard for this circuit. Remember that fact in a + * restriction. */ + rst = tor_malloc_zero(sizeof(entry_guard_restriction_t)); + memcpy(rst->exclude_id, exit_id, DIGEST_LEN); + } + if (entry_guard_pick_for_circuit(get_guard_selection_info(), + GUARD_USAGE_TRAFFIC, + rst, + &r, + guard_state_out) < 0) { + tor_assert(r == NULL); + } + return r; +} + +/** Remove all currently listed entry guards for a given guard selection + * context. This frees and replaces <b>gs</b>, so don't use <b>gs</b> + * after calling this function. */ +void +remove_all_entry_guards_for_guard_selection(guard_selection_t *gs) { - download_status_t *dl = NULL; + // This function shouldn't exist. XXXX + tor_assert(gs != NULL); + char *old_name = tor_strdup(gs->name); + guard_selection_type_t old_type = gs->type; - if (digest && get_options()->UseBridges && bridge_list) { - SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, b) { - if (tor_memeq(digest, b->identity, DIGEST_LEN)) { - dl = &(b->fetch_status); - break; - } - } SMARTLIST_FOREACH_END(b); + SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, entry, { + control_event_guard(entry->nickname, entry->identity, "DROPPED"); + }); + + if (gs == curr_guard_context) { + curr_guard_context = NULL; } - return dl; + smartlist_remove(guard_contexts, gs); + guard_selection_free(gs); + + gs = get_guard_selection_by_name(old_name, old_type, 1); + entry_guards_changed_for_guard_selection(gs); + tor_free(old_name); } -/** Return 1 if we have at least one descriptor for an entry guard - * (bridge or member of EntryNodes) and all descriptors we know are - * down. Else return 0. If <b>act</b> is 1, then mark the down guards - * up; else just observe and report. */ -static int -entries_retry_helper(const or_options_t *options, int act) +/** Remove all currently listed entry guards, so new ones will be chosen. + * + * XXXX This function shouldn't exist -- it's meant to support the DROPGUARDS + * command, which is deprecated. + */ +void +remove_all_entry_guards(void) { - const node_t *node; - int any_known = 0; - int any_running = 0; - int need_bridges = options->UseBridges != 0; - if (!entry_guards) - entry_guards = smartlist_new(); - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) { - node = node_get_by_id(e->identity); - if (node && node_has_descriptor(node) && - node_is_bridge(node) == need_bridges && - (!need_bridges || (!e->bad_since && - node_is_a_configured_bridge(node)))) { - any_known = 1; - if (node->is_running) - any_running = 1; /* some entry is both known and running */ - else if (act) { - /* Mark all current connections to this OR as unhealthy, since - * otherwise there could be one that started 30 seconds - * ago, and in 30 seconds it will time out, causing us to mark - * the node down and undermine the retry attempt. We mark even - * the established conns, since if the network just came back - * we'll want to attach circuits to fresh conns. */ - connection_or_set_bad_connections(node->identity, 1); - - /* mark this entry node for retry */ - router_set_status(node->identity, 1); - e->can_retry = 1; - e->bad_since = 0; - } - } - } SMARTLIST_FOREACH_END(e); - log_debug(LD_DIR, "%d: any_known %d, any_running %d", - act, any_known, any_running); - return any_known && !any_running; + remove_all_entry_guards_for_guard_selection(get_guard_selection_info()); } -/** Do we know any descriptors for our bridges / entrynodes, and are - * all the ones we have descriptors for down? */ +/** Helper: pick a directory guard, with whatever algorithm is used. */ +const node_t * +guards_choose_dirguard(circuit_guard_state_t **guard_state_out) +{ + const node_t *r = NULL; + if (entry_guard_pick_for_circuit(get_guard_selection_info(), + GUARD_USAGE_DIRGUARD, + NULL, + &r, + guard_state_out) < 0) { + tor_assert(r == NULL); + } + return r; +} + +/** + * If we're running with a constrained guard set, then maybe mark our guards + * usable. Return 1 if we do; 0 if we don't. + */ int -entries_known_but_down(const or_options_t *options) +guards_retry_optimistic(const or_options_t *options) { - tor_assert(entry_list_is_constrained(options)); - return entries_retry_helper(options, 0); + if (! entry_list_is_constrained(options)) + return 0; + + mark_primary_guards_maybe_reachable(get_guard_selection_info()); + + return 1; } -/** Mark all down known bridges / entrynodes up. */ -void -entries_retry_all(const or_options_t *options) +/** + * Return true iff we know enough directory information to construct + * circuits through all of the primary guards we'd currently use. + */ +int +guard_selection_have_enough_dir_info_to_build_circuits(guard_selection_t *gs) { - tor_assert(entry_list_is_constrained(options)); - entries_retry_helper(options, 1); + if (!gs->primary_guards_up_to_date) + entry_guards_update_primary(gs); + + int n_missing_descriptors = 0; + int n_considered = 0; + int num_primary_to_check; + + /* We want to check for the descriptor of at least the first two primary + * guards in our list, since these are the guards that we typically use for + * circuits. */ + num_primary_to_check = get_n_primary_guards_to_use(GUARD_USAGE_TRAFFIC); + num_primary_to_check++; + + SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) { + entry_guard_consider_retry(guard); + if (guard->is_reachable == GUARD_REACHABLE_NO) + continue; + n_considered++; + if (!guard_has_descriptor(guard)) + n_missing_descriptors++; + if (n_considered >= num_primary_to_check) + break; + } SMARTLIST_FOREACH_END(guard); + + return n_missing_descriptors == 0; } -/** Return true if at least one of our bridges runs a Tor version that can - * provide microdescriptors to us. If not, we'll fall back to asking for - * full descriptors. */ +/** As guard_selection_have_enough_dir_info_to_build_circuits, but uses + * the default guard selection. */ int -any_bridge_supports_microdescriptors(void) +entry_guards_have_enough_dir_info_to_build_circuits(void) { - const node_t *node; - if (!get_options()->UseBridges || !entry_guards) - return 0; - SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) { - node = node_get_by_id(e->identity); - if (node && node->is_running && - node_is_bridge(node) && node_is_a_configured_bridge(node)) { - /* This is one of our current bridges, and we know enough about - * it to know that it will be able to answer our questions. */ - return 1; - } - } SMARTLIST_FOREACH_END(e); - return 0; + return guard_selection_have_enough_dir_info_to_build_circuits( + get_guard_selection_info()); +} + +/** Free one guard selection context */ +STATIC void +guard_selection_free(guard_selection_t *gs) +{ + if (!gs) return; + + tor_free(gs->name); + + if (gs->sampled_entry_guards) { + SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, e, + entry_guard_free(e)); + smartlist_free(gs->sampled_entry_guards); + gs->sampled_entry_guards = NULL; + } + + smartlist_free(gs->confirmed_entry_guards); + smartlist_free(gs->primary_entry_guards); + + tor_free(gs); } /** Release all storage held by the list of entry guards and related @@ -2547,15 +3498,16 @@ any_bridge_supports_microdescriptors(void) void entry_guards_free_all(void) { - if (entry_guards) { - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, - entry_guard_free(e)); - smartlist_free(entry_guards); - entry_guards = NULL; + /* Null out the default */ + curr_guard_context = NULL; + /* Free all the guard contexts */ + if (guard_contexts != NULL) { + SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) { + guard_selection_free(gs); + } SMARTLIST_FOREACH_END(gs); + smartlist_free(guard_contexts); + guard_contexts = NULL; } - clear_bridge_list(); - smartlist_free(bridge_list); - bridge_list = NULL; circuit_build_times_free_timeouts(get_circuit_build_times_mutable()); } |