diff options
| -rw-r--r-- | changes/ticket32088 | 13 | ||||
| -rw-r--r-- | scripts/maint/practracker/exceptions.txt | 4 | ||||
| -rw-r--r-- | src/feature/client/entrynodes.c | 275 | ||||
| -rw-r--r-- | src/feature/client/entrynodes.h | 25 | ||||
| -rw-r--r-- | src/test/test_entrynodes.c | 147 |
5 files changed, 326 insertions, 138 deletions
diff --git a/changes/ticket32088 b/changes/ticket32088 new file mode 100644 index 0000000000..0d4fc74754 --- /dev/null +++ b/changes/ticket32088 @@ -0,0 +1,13 @@ + o Major features (Proposal 310, performance + security): + - Implements Proposal 310 - Bandaid on guard selection. + Proposal 310 solves a load-balancing issue within Prop271 which strongly + impact experimental research with Shadow. + Security improvement: Proposal 310 prevents any newly Guard relay to + have a chance to get into the primary list of older Tor clients, + except if the N first sampled guards of these clients are unreachable. + Implements recommendation from 32088. + + Proposal 310 is linked to the CLAPS project researching optimal + client location-aware path selections. This project is a collaboration + between the UCLouvain Crypto Group, the U.S. Naval Research Laboratory and + Princeton University. diff --git a/scripts/maint/practracker/exceptions.txt b/scripts/maint/practracker/exceptions.txt index 9444dbdb66..154f43ee1f 100644 --- a/scripts/maint/practracker/exceptions.txt +++ b/scripts/maint/practracker/exceptions.txt @@ -182,10 +182,10 @@ problem function-size /src/feature/client/addressmap.c:addressmap_rewrite() 109 problem function-size /src/feature/client/bridges.c:rewrite_node_address_for_bridge() 125 problem function-size /src/feature/client/circpathbias.c:pathbias_measure_close_rate() 108 problem function-size /src/feature/client/dnsserv.c:evdns_server_callback() 153 -problem file-size /src/feature/client/entrynodes.c 3827 +problem file-size /src/feature/client/entrynodes.c 4000 problem function-size /src/feature/client/entrynodes.c:entry_guards_upgrade_waiting_circuits() 155 problem function-size /src/feature/client/entrynodes.c:entry_guard_parse_from_state() 246 -problem file-size /src/feature/client/entrynodes.h 639 +problem file-size /src/feature/client/entrynodes.h 700 problem function-size /src/feature/client/transports.c:handle_proxy_line() 108 problem function-size /src/feature/client/transports.c:parse_method_line_helper() 110 problem function-size /src/feature/client/transports.c:create_managed_proxy_environment() 111 diff --git a/src/feature/client/entrynodes.c b/src/feature/client/entrynodes.c index ded7db969a..2a000a47b6 100644 --- a/src/feature/client/entrynodes.c +++ b/src/feature/client/entrynodes.c @@ -47,8 +47,7 @@ * 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. + * to use that circuit. * * And as a final group, we have an ordered list of PRIMARY GUARDS, * whose elements are taken from the filtered set. We prefer @@ -59,7 +58,7 @@ * * 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 + * or the first (by sampled order) 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 @@ -92,14 +91,18 @@ * [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 confirmed, update the primary list, and sort them + * by sampled order. * * [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 + * [x] When we update the confirmed list, or when we re-build the primary list + * and detect a change, we sort those lists by sampled_idx + * + * [x] Before calling first_reachable_filtered_entry_guard(), 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 @@ -172,6 +175,7 @@ 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); +static int compare_guards_by_sampled_idx(const void **a_, const void **b_); /** Return 0 if we should apply guardfraction information found in the * consensus. A specific consensus can be specified with the @@ -890,6 +894,7 @@ entry_guard_add_to_sample_impl(guard_selection_t *gs, tor_free(guard->sampled_by_version); guard->sampled_by_version = tor_strdup(VERSION); guard->currently_listed = 1; + guard->sampled_idx = gs->next_sampled_idx++; guard->confirmed_idx = -1; /* non-persistent fields */ @@ -1383,7 +1388,7 @@ sampled_guards_prune_obsolete_entries(guard_selection_t *gs, if (rmv) { ++n_changes; - SMARTLIST_DEL_CURRENT(gs->sampled_entry_guards, guard); + SMARTLIST_DEL_CURRENT_KEEPORDER(gs->sampled_entry_guards, guard); remove_guard_from_confirmed_and_primary_lists(gs, guard); entry_guard_free(guard); } @@ -1707,7 +1712,7 @@ entry_guards_update_filtered_sets(guard_selection_t *gs) } /** - * Return a random guard from the reachable filtered sample guards + * Return the first sampled 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. * @@ -1718,7 +1723,7 @@ entry_guards_update_filtered_sets(guard_selection_t *gs) * violate it. **/ STATIC entry_guard_t * -sample_reachable_filtered_entry_guards(guard_selection_t *gs, +first_reachable_filtered_entry_guard(guard_selection_t *gs, const entry_guard_restriction_t *rst, unsigned flags) { @@ -1771,7 +1776,17 @@ sample_reachable_filtered_entry_guards(guard_selection_t *gs, flags, smartlist_len(reachable_filtered_sample)); if (smartlist_len(reachable_filtered_sample)) { - result = smartlist_choose(reachable_filtered_sample); + /** + * Get the first guard of the filtered set builds from + * sampled_entry_guards. Proposal 310 suggests this design to overcome + * performance and security issues linked to the previous selection + * method. The guard selected here should be filtered out if this function + * is called again in the same context. I.e., if we filter guards to add + * them into some list X, then the guards from list X will be filtered out + * when this function is called again. Hence it requires setting exclude + * flags in a appropriate way (depending of the context of the caller). + */ + result = smartlist_get(reachable_filtered_sample, 0); log_info(LD_GUARD, " (Selected %s.)", result ? entry_guard_describe(result) : "<null>"); } @@ -1780,10 +1795,6 @@ sample_reachable_filtered_entry_guards(guard_selection_t *gs, return result; } -/** - * Helper: compare two entry_guard_t by their confirmed_idx values. - * Used to sort the confirmed list. - */ static int compare_guards_by_confirmed_idx(const void **a_, const void **b_) { @@ -1795,6 +1806,21 @@ compare_guards_by_confirmed_idx(const void **a_, const void **b_) else return 0; } +/** + * Helper: compare two entry_guard_t by their sampled_idx values. + * Used to sort the sampled list + */ +static int +compare_guards_by_sampled_idx(const void **a_, const void **b_) +{ + const entry_guard_t *a = *a_, *b = *b_; + if (a->sampled_idx < b->sampled_idx) + return -1; + else if (a->sampled_idx > b->sampled_idx) + return 1; + else + return 0; +} /** * Find the confirmed guards from among the sampled guards in <b>gs</b>, @@ -1811,7 +1837,7 @@ entry_guards_update_confirmed(guard_selection_t *gs) } SMARTLIST_FOREACH_END(guard); smartlist_sort(gs->confirmed_entry_guards, compare_guards_by_confirmed_idx); - + /** Needed to keep a dense array of confirmed_idx */ int any_changed = 0; SMARTLIST_FOREACH_BEGIN(gs->confirmed_entry_guards, entry_guard_t *, guard) { if (guard->confirmed_idx != guard_sl_idx) { @@ -1821,6 +1847,8 @@ entry_guards_update_confirmed(guard_selection_t *gs) } SMARTLIST_FOREACH_END(guard); gs->next_confirmed_idx = smartlist_len(gs->confirmed_entry_guards); + // We need the confirmed list to always be give guards in sampled order + smartlist_sort(gs->confirmed_entry_guards, compare_guards_by_sampled_idx); if (any_changed) { entry_guards_changed_for_guard_selection(gs); @@ -1849,6 +1877,9 @@ make_guard_confirmed(guard_selection_t *gs, entry_guard_t *guard) guard->confirmed_idx = gs->next_confirmed_idx++; smartlist_add(gs->confirmed_entry_guards, guard); + /** The confirmation ordering might not be the sample ording. We need to + * reorder */ + smartlist_sort(gs->confirmed_entry_guards, compare_guards_by_sampled_idx); // This confirmed guard might kick something else out of the primary // guards. @@ -1912,7 +1943,7 @@ entry_guards_update_primary(guard_selection_t *gs) /* 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, + entry_guard_t *guard = first_reachable_filtered_entry_guard(gs, NULL, SAMPLE_EXCLUDE_CONFIRMED| SAMPLE_EXCLUDE_PRIMARY| SAMPLE_NO_UPDATE_PRIMARY); @@ -1943,6 +1974,7 @@ entry_guards_update_primary(guard_selection_t *gs) g->confirmed_idx >= 0 ? " (confirmed)" : "", g->is_filtered_guard ? "" : " (excluded by filter)"); } SMARTLIST_FOREACH_END(g); + smartlist_sort(new_primary_guards, compare_guards_by_sampled_idx); } smartlist_free(old_primary_guards); @@ -2055,10 +2087,15 @@ select_primary_guard_for_circuit(guard_selection_t *gs, SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) { entry_guard_consider_retry(guard); - if (! entry_guard_obeys_restriction(guard, rst)) + if (!entry_guard_obeys_restriction(guard, rst)) { + log_info(LD_GUARD, "Entry guard %s doesn't obey restriction, we test the" + " next one", entry_guard_describe(guard)); continue; + } if (guard->is_reachable != GUARD_REACHABLE_NO) { if (need_descriptor && !guard_has_descriptor(guard)) { + log_info(LD_GUARD, "Guard %s does not have a descriptor", + entry_guard_describe(guard)); continue; } *state_out = GUARD_CIRC_STATE_USABLE_ON_COMPLETION; @@ -2071,9 +2108,11 @@ select_primary_guard_for_circuit(guard_selection_t *gs, if (smartlist_len(usable_primary_guards)) { chosen_guard = smartlist_choose(usable_primary_guards); + log_info(LD_GUARD, + "Selected primary guard %s for circuit from a list size of %d.", + entry_guard_describe(chosen_guard), + smartlist_len(usable_primary_guards)); smartlist_free(usable_primary_guards); - log_info(LD_GUARD, "Selected primary guard %s for circuit.", - entry_guard_describe(chosen_guard)); } smartlist_free(usable_primary_guards); @@ -2118,10 +2157,10 @@ select_confirmed_guard_for_circuit(guard_selection_t *gs, } /** - * For use with a circuit, pick a confirmed usable filtered guard - * at random. 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. + * For use with a circuit, pick a usable 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_filtered_guard_for_circuit(guard_selection_t *gs, @@ -2134,7 +2173,7 @@ select_filtered_guard_for_circuit(guard_selection_t *gs, unsigned flags = 0; if (need_descriptor) flags |= SAMPLE_EXCLUDE_NO_DESCRIPTOR; - chosen_guard = sample_reachable_filtered_entry_guards(gs, + chosen_guard = first_reachable_filtered_entry_guard(gs, rst, SAMPLE_EXCLUDE_CONFIRMED | SAMPLE_EXCLUDE_PRIMARY | @@ -2148,7 +2187,7 @@ select_filtered_guard_for_circuit(guard_selection_t *gs, chosen_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 " + "guard %s for circuit. Will try other guards before " "using this circuit.", entry_guard_describe(chosen_guard)); return chosen_guard; @@ -2189,8 +2228,8 @@ select_entry_guard_for_circuit(guard_selection_t *gs, if (chosen_guard) return chosen_guard; - /* "Otherwise, if there is no such entry, select a member at - random from {USABLE_FILTERED_GUARDS}." */ + /* "Otherwise, if there is no such entry, select a member + * {USABLE_FILTERED_GUARDS} following the sample ordering" */ chosen_guard = select_filtered_guard_for_circuit(gs, usage, rst, state_out); if (chosen_guard == NULL) { @@ -2773,10 +2812,12 @@ entry_guards_update_all(guard_selection_t *gs) /** * Return a newly allocated string for encoding the persistent parts of - * <b>guard</b> to the state file. + * <b>guard</b> to the state file. <b>dense_sampled_idx</b> refers to the + * sampled_idx made dense for this <b>guard</b>. Encoding all guards should + * lead to a dense array of sampled_idx in the state file. */ STATIC char * -entry_guard_encode_for_state(entry_guard_t *guard) +entry_guard_encode_for_state(entry_guard_t *guard, int dense_sampled_idx) { /* * The meta-format we use is K=V K=V K=V... where K can be any @@ -2805,7 +2846,8 @@ entry_guard_encode_for_state(entry_guard_t *guard) format_iso_time_nospace(tbuf, guard->sampled_on_date); smartlist_add_asprintf(result, "sampled_on=%s", tbuf); - + // Replacing the sampled_idx by dense array + smartlist_add_asprintf(result, "sampled_idx=%d", dense_sampled_idx); if (guard->sampled_by_version) { smartlist_add_asprintf(result, "sampled_by=%s", guard->sampled_by_version); @@ -2861,6 +2903,78 @@ entry_guard_encode_for_state(entry_guard_t *guard) } /** + * Extract key=val from the state string <b>s</b> and duplicate the value to + * some string target declared in entry_guard_parse_from_state + */ +static void +parse_from_state_set_vals(const char *s, smartlist_t *entries, smartlist_t + *extra, strmap_t *vals) +{ + 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; + } + + *target = tor_strdup(eq+1); + tor_free(key); + tor_free(entry); + } SMARTLIST_FOREACH_END(entry); +} + +/** + * Handle part of the parsing state file logic, focused on time related things + */ +static void +parse_from_state_handle_time(entry_guard_t *guard, char *sampled_on, char + *unlisted_since, char *confirmed_on) +{ +#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; +} + +/** * 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. @@ -2876,6 +2990,7 @@ entry_guard_parse_from_state(const char *s) char *rsa_id = NULL; char *nickname = NULL; char *sampled_on = NULL; + char *sampled_idx = NULL; char *sampled_by = NULL; char *unlisted_since = NULL; char *listed = NULL; @@ -2892,6 +3007,7 @@ entry_guard_parse_from_state(const char *s) char *pb_collapsed_circuits = NULL; char *pb_unusable_circuits = NULL; char *pb_timeouts = NULL; + int invalid_sampled_idx = get_max_sample_size_absolute(); /* Split up the entries. Put the ones we know about in strings and the * rest in "extra". */ @@ -2905,6 +3021,7 @@ entry_guard_parse_from_state(const char *s) FIELD(rsa_id); FIELD(nickname); FIELD(sampled_on); + FIELD(sampled_idx); FIELD(sampled_by); FIELD(unlisted_since); FIELD(listed); @@ -2920,29 +3037,8 @@ entry_guard_parse_from_state(const char *s) 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; - } - - *target = tor_strdup(eq+1); - tor_free(key); - tor_free(entry); - } SMARTLIST_FOREACH_END(entry); + /* Extract from s the key=val that we recognize, put the others in extra*/ + parse_from_state_set_vals(s, entries, extra, vals); smartlist_free(entries); strmap_free(vals, NULL); @@ -2990,43 +3086,12 @@ entry_guard_parse_from_state(const char *s) } /* 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; + parse_from_state_handle_time(guard, sampled_on, unlisted_since, + confirmed_on); /* 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; @@ -3044,6 +3109,29 @@ entry_guard_parse_from_state(const char *s) } } + if (sampled_idx) { + int ok = 1; + long idx = tor_parse_long(sampled_idx, 10, 0, INT_MAX, &ok, NULL); + if (!ok) { + log_warn(LD_GUARD, "Guard has invalid sampled_idx %s", + escaped(sampled_idx)); + /* set it to a idx higher than the max sample size */ + guard->sampled_idx = invalid_sampled_idx++; + } else { + guard->sampled_idx = (int)idx; + } + } else if (confirmed_idx) { + /* This state has been written by an older Tor version which did not have + * sample ordering */ + + guard->sampled_idx = guard->confirmed_idx; + } else { + log_warn(LD_GUARD, "The state file seems to be into a status that could" + " yield to weird entry node selection: we're missing both a" + " sampled_idx and a confirmed_idx."); + guard->sampled_idx = invalid_sampled_idx++; + } + /* Anything we didn't recognize gets crammed together */ if (smartlist_len(extra) > 0) { guard->extra_state_fields = smartlist_join_strings(extra, " ", 0, NULL); @@ -3098,6 +3186,7 @@ entry_guard_parse_from_state(const char *s) tor_free(listed); tor_free(confirmed_on); tor_free(confirmed_idx); + tor_free(sampled_idx); tor_free(bridge_addr); tor_free(pb_use_attempts); tor_free(pb_use_successes); @@ -3127,13 +3216,15 @@ entry_guards_update_guards_in_state(or_state_t *state) config_line_t **nextline = &lines; SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) { + int i = 0; 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)->value = entry_guard_encode_for_state(guard, i); nextline = &(*nextline)->next; + i++; } SMARTLIST_FOREACH_END(guard); } SMARTLIST_FOREACH_END(gs); @@ -3186,6 +3277,14 @@ entry_guards_load_guards_from_state(or_state_t *state, int set) tor_assert(gs); smartlist_add(gs->sampled_entry_guards, guard); guard->in_selection = gs; + /* Recompute the next_sampled_id from the state. We do not assume that + * sampled guards appear in the correct order within the file, and we + * need to know what would be the next sampled idx to give to any + * new sampled guard (i.e., max of guard->sampled_idx + 1)*/ + if (gs->next_sampled_idx <= guard->sampled_idx) { + gs->next_sampled_idx = guard->sampled_idx + 1; + } + } else { entry_guard_free(guard); } @@ -3193,6 +3292,10 @@ entry_guards_load_guards_from_state(or_state_t *state, int set) if (set) { SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) { + /** Guards should be in sample order within the file, but it is maybe + * better NOT to assume that. Let's order them before updating lists + */ + smartlist_sort(gs->sampled_entry_guards, compare_guards_by_sampled_idx); entry_guards_update_all(gs); } SMARTLIST_FOREACH_END(gs); } diff --git a/src/feature/client/entrynodes.h b/src/feature/client/entrynodes.h index 6eede2c8d4..4b236dc80c 100644 --- a/src/feature/client/entrynodes.h +++ b/src/feature/client/entrynodes.h @@ -117,6 +117,13 @@ struct entry_guard_t { * confirmed guard. */ time_t confirmed_on_date; /* 0 if not confirmed */ /** + * In what order was this guard sampled? Guards with + * lower indices appear earlier on the sampled list, the confirmed list and + * the primary list as a result of Prop 310 + */ + int sampled_idx; + + /** * In what order was this guard confirmed? Guards with lower indices * appear earlier on the confirmed list. If the confirmed list is compacted, * this field corresponds to the index of this guard on the confirmed list. @@ -242,8 +249,9 @@ struct guard_selection_t { * Ordered list (from highest to lowest priority) of guards that we * have successfully contacted and decided to use. Every member of * this list is a member of sampled_entry_guards. Every member should - * have confirmed_on_date set, and have confirmed_idx greater than - * any earlier member of the list. + * have confirmed_on_date set. + * The ordering of the list should be by sampled idx. The reasoning behind + * it is linked to Proposal 310. * * This list is persistent. It is a subset of the elements in * sampled_entry_guards, and its pointers point to elements of @@ -271,6 +279,12 @@ struct guard_selection_t { * confirmed_entry_guards receive? */ int next_confirmed_idx; + /** What sampled_idx value should the next-added member of + * sampled_entry_guards receive? This should follow the size of the sampled + * list until sampled relays get pruned for some reason + */ + int next_sampled_idx; + }; struct entry_guard_handle_t; @@ -515,7 +529,8 @@ MOCK_DECL(STATIC circuit_guard_state_t *, STATIC entry_guard_t *entry_guard_add_to_sample(guard_selection_t *gs, const node_t *node); STATIC entry_guard_t *entry_guards_expand_sample(guard_selection_t *gs); -STATIC char *entry_guard_encode_for_state(entry_guard_t *guard); +STATIC char *entry_guard_encode_for_state(entry_guard_t *guard, int + dense_sampled_index); STATIC entry_guard_t *entry_guard_parse_from_state(const char *s); #define entry_guard_free(e) \ FREE_AND_NULL(entry_guard_t, entry_guard_free_, (e)) @@ -523,7 +538,7 @@ STATIC void entry_guard_free_(entry_guard_t *e); STATIC void entry_guards_update_filtered_sets(guard_selection_t *gs); STATIC int entry_guards_all_primary_guards_are_down(guard_selection_t *gs); /** - * @name Flags for sample_reachable_filtered_entry_guards() + * @name Flags for first_reachable_filtered_entry_guard() */ /**@{*/ #define SAMPLE_EXCLUDE_CONFIRMED (1u<<0) @@ -532,7 +547,7 @@ STATIC int entry_guards_all_primary_guards_are_down(guard_selection_t *gs); #define SAMPLE_NO_UPDATE_PRIMARY (1u<<3) #define SAMPLE_EXCLUDE_NO_DESCRIPTOR (1u<<4) /**@}*/ -STATIC entry_guard_t *sample_reachable_filtered_entry_guards( +STATIC entry_guard_t *first_reachable_filtered_entry_guard( guard_selection_t *gs, const entry_guard_restriction_t *rst, unsigned flags); diff --git a/src/test/test_entrynodes.c b/src/test/test_entrynodes.c index 12b4fcde3c..5ddd1a3db0 100644 --- a/src/test/test_entrynodes.c +++ b/src/test/test_entrynodes.c @@ -390,12 +390,13 @@ test_entry_guard_encode_for_state_minimal(void *arg) eg->confirmed_idx = -1; char *s = NULL; - s = entry_guard_encode_for_state(eg); + s = entry_guard_encode_for_state(eg, 0); tt_str_op(s, OP_EQ, "in=wubwub " "rsa_id=706C75727079666C75727079736C75727079646F " "sampled_on=2016-11-14T00:00:00 " + "sampled_idx=0 " "listed=0"); done: @@ -421,10 +422,11 @@ test_entry_guard_encode_for_state_maximal(void *arg) eg->currently_listed = 1; eg->confirmed_on_date = 1479081690; eg->confirmed_idx = 333; + eg->sampled_idx = 42; eg->extra_state_fields = tor_strdup("and the green grass grew all around"); char *s = NULL; - s = entry_guard_encode_for_state(eg); + s = entry_guard_encode_for_state(eg, 0); tt_str_op(s, OP_EQ, "in=default " @@ -432,6 +434,7 @@ test_entry_guard_encode_for_state_maximal(void *arg) "bridge_addr=8.8.4.4:9999 " "nickname=Fred " "sampled_on=2016-11-14T00:00:00 " + "sampled_idx=0 " "sampled_by=1.2.3 " "unlisted_since=2016-11-14T00:00:45 " "listed=1 " @@ -621,39 +624,47 @@ test_entry_guard_parse_from_state_full(void *arg) const char STATE[] = "Guard in=default rsa_id=214F44BD5B638E8C817D47FF7C97397790BF0345 " "nickname=TotallyNinja sampled_on=2016-11-12T19:32:49 " + "sampled_idx=0 " "sampled_by=0.3.0.0-alpha-dev " "listed=1\n" "Guard in=default rsa_id=052900AB0EA3ED54BAB84AE8A99E74E8693CE2B2 " "nickname=5OfNovember sampled_on=2016-11-20T04:32:05 " + "sampled_idx=1 " "sampled_by=0.3.0.0-alpha-dev " "listed=1 confirmed_on=2016-11-22T08:13:28 confirmed_idx=0 " "pb_circ_attempts=4.000000 pb_circ_successes=2.000000 " "pb_successful_circuits_closed=2.000000\n" "Guard in=default rsa_id=7B700C0C207EBD0002E00F499BE265519AC3C25A " "nickname=dc6jgk11 sampled_on=2016-11-28T11:50:13 " + "sampled_idx=2 " "sampled_by=0.3.0.0-alpha-dev " "listed=1 confirmed_on=2016-11-24T08:45:30 confirmed_idx=4 " "pb_circ_attempts=5.000000 pb_circ_successes=5.000000 " "pb_successful_circuits_closed=5.000000\n" "Guard in=wobblesome rsa_id=7B700C0C207EBD0002E00F499BE265519AC3C25A " "nickname=dc6jgk11 sampled_on=2016-11-28T11:50:13 " + "sampled_idx=0 " "sampled_by=0.3.0.0-alpha-dev " "listed=1\n" "Guard in=default rsa_id=E9025AD60D86875D5F11548D536CC6AF60F0EF5E " "nickname=maibrunn sampled_on=2016-11-25T22:36:38 " + "sampled_idx=3 " "sampled_by=0.3.0.0-alpha-dev listed=1\n" "Guard in=default rsa_id=DCD30B90BA3A792DA75DC54A327EF353FB84C38E " "nickname=Unnamed sampled_on=2016-11-25T14:34:00 " + "sampled_idx=10 " "sampled_by=0.3.0.0-alpha-dev listed=1\n" "Guard in=bridges rsa_id=8FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2E " "bridge_addr=24.1.1.1:443 sampled_on=2016-11-25T06:44:14 " + "sampled_idx=0 " "sampled_by=0.3.0.0-alpha-dev listed=1 " "confirmed_on=2016-11-29T10:36:06 confirmed_idx=0 " "pb_circ_attempts=8.000000 pb_circ_successes=8.000000 " "pb_successful_circuits_closed=13.000000\n" "Guard in=bridges rsa_id=5800000000000000000000000000000000000000 " "bridge_addr=37.218.246.143:28366 " - "sampled_on=2016-11-18T15:07:34 sampled_by=0.3.0.0-alpha-dev listed=1\n"; + "sampled_on=2016-11-18T15:07:34 sampled_idx=1 " + "sampled_by=0.3.0.0-alpha-dev listed=1\n"; config_line_t *lines = NULL; or_state_t *state = tor_malloc_zero(sizeof(or_state_t)); @@ -729,35 +740,42 @@ test_entry_guard_parse_from_state_full(void *arg) tt_str_op(joined, OP_EQ, "Guard in=default rsa_id=052900AB0EA3ED54BAB84AE8A99E74E8693CE2B2 " "nickname=5OfNovember sampled_on=2016-11-20T04:32:05 " + "sampled_idx=0 " "sampled_by=0.3.0.0-alpha-dev " "listed=1 confirmed_on=2016-11-22T08:13:28 confirmed_idx=0 " "pb_circ_attempts=4.000000 pb_circ_successes=2.000000 " "pb_successful_circuits_closed=2.000000\n" "Guard in=default rsa_id=7B700C0C207EBD0002E00F499BE265519AC3C25A " "nickname=dc6jgk11 sampled_on=2016-11-28T11:50:13 " + "sampled_idx=1 " "sampled_by=0.3.0.0-alpha-dev " "listed=1 confirmed_on=2016-11-24T08:45:30 confirmed_idx=1 " "pb_circ_attempts=5.000000 pb_circ_successes=5.000000 " "pb_successful_circuits_closed=5.000000\n" "Guard in=default rsa_id=E9025AD60D86875D5F11548D536CC6AF60F0EF5E " "nickname=maibrunn sampled_on=2016-11-25T22:36:38 " + "sampled_idx=2 " "sampled_by=0.3.0.0-alpha-dev listed=1\n" "Guard in=default rsa_id=DCD30B90BA3A792DA75DC54A327EF353FB84C38E " "nickname=Unnamed sampled_on=2016-11-25T14:34:00 " + "sampled_idx=3 " "sampled_by=0.3.0.0-alpha-dev listed=1\n" "Guard in=wobblesome rsa_id=7B700C0C207EBD0002E00F499BE265519AC3C25A " "nickname=dc6jgk11 sampled_on=2016-11-28T11:50:13 " + "sampled_idx=0 " "sampled_by=0.3.0.0-alpha-dev " "listed=1\n" "Guard in=bridges rsa_id=8FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF2E " "bridge_addr=24.1.1.1:443 sampled_on=2016-11-25T06:44:14 " + "sampled_idx=0 " "sampled_by=0.3.0.0-alpha-dev listed=1 " "confirmed_on=2016-11-29T10:36:06 confirmed_idx=0 " "pb_circ_attempts=8.000000 pb_circ_successes=8.000000 " "pb_successful_circuits_closed=13.000000\n" "Guard in=bridges rsa_id=5800000000000000000000000000000000000000 " "bridge_addr=37.218.246.143:28366 " - "sampled_on=2016-11-18T15:07:34 sampled_by=0.3.0.0-alpha-dev listed=1\n"); + "sampled_on=2016-11-18T15:07:34 sampled_idx=1 " + "sampled_by=0.3.0.0-alpha-dev listed=1\n"); done: config_free_lines(lines); @@ -1461,8 +1479,8 @@ test_entry_guard_confirming_guards(void *arg) tt_i64_op(g1->confirmed_on_date, OP_EQ, start+10); tt_i64_op(g2->confirmed_on_date, OP_EQ, start); tt_i64_op(g3->confirmed_on_date, OP_EQ, start+10); - tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g2); - tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g1); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g1); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g2); tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 2), OP_EQ, g3); /* Now make sure we can regenerate the confirmed_entry_guards list. */ @@ -1474,8 +1492,8 @@ test_entry_guard_confirming_guards(void *arg) tt_int_op(g1->confirmed_idx, OP_EQ, 1); tt_int_op(g2->confirmed_idx, OP_EQ, 0); tt_int_op(g3->confirmed_idx, OP_EQ, 2); - tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g2); - tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g1); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 0), OP_EQ, g1); + tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 1), OP_EQ, g2); tt_ptr_op(smartlist_get(gs->confirmed_entry_guards, 2), OP_EQ, g3); /* Now make sure we can regenerate the confirmed_entry_guards list if @@ -1492,9 +1510,9 @@ test_entry_guard_confirming_guards(void *arg) g1 = smartlist_get(gs->confirmed_entry_guards, 0); g2 = smartlist_get(gs->confirmed_entry_guards, 1); g3 = smartlist_get(gs->confirmed_entry_guards, 2); - tt_int_op(g1->confirmed_idx, OP_EQ, 0); - tt_int_op(g2->confirmed_idx, OP_EQ, 1); - tt_int_op(g3->confirmed_idx, OP_EQ, 2); + tt_int_op(g1->sampled_idx, OP_EQ, 0); + tt_int_op(g2->sampled_idx, OP_EQ, 1); + tt_int_op(g3->sampled_idx, OP_EQ, 8); tt_assert(g1 != g2); tt_assert(g1 != g3); tt_assert(g2 != g3); @@ -1510,9 +1528,6 @@ test_entry_guard_sample_reachable_filtered(void *arg) (void)arg; guard_selection_t *gs = guard_selection_new("default", GS_TYPE_NORMAL); entry_guards_expand_sample(gs); - const int N = 10000; - bitarray_t *selected = NULL; - int i, j; /* We've got a sampled list now; let's make one non-usable-filtered; some * confirmed, some primary, some pending. @@ -1547,32 +1562,21 @@ test_entry_guard_sample_reachable_filtered(void *arg) { SAMPLE_EXCLUDE_PENDING, 0 }, { -1, -1}, }; - + int j; for (j = 0; tests[j].flag >= 0; ++j) { - selected = bitarray_init_zero(n_guards); const int excluded_flags = tests[j].flag; const int excluded_idx = tests[j].idx; - for (i = 0; i < N; ++i) { - g = sample_reachable_filtered_entry_guards(gs, NULL, excluded_flags); - tor_assert(g); - int pos = smartlist_pos(gs->sampled_entry_guards, g); - tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_guards); - tt_int_op(pos, OP_GE, 0); - tt_int_op(pos, OP_LT, n_guards); - bitarray_set(selected, pos); - } - for (i = 0; i < n_guards; ++i) { - const int should_be_set = (i != excluded_idx && - i != 3); // filtered out. - tt_int_op(!!bitarray_is_set(selected, i), OP_EQ, should_be_set); - } - bitarray_free(selected); - selected = NULL; + g = first_reachable_filtered_entry_guard(gs, NULL, excluded_flags); + tor_assert(g); + int pos = smartlist_pos(gs->sampled_entry_guards, g); + tt_int_op(smartlist_len(gs->sampled_entry_guards), OP_EQ, n_guards); + const int should_be_set = (pos != excluded_idx && + pos != 3); // filtered out. + tt_int_op(1, OP_EQ, should_be_set); } done: guard_selection_free(gs); - bitarray_free(selected); } static void @@ -1584,7 +1588,7 @@ test_entry_guard_sample_reachable_filtered_empty(void *arg) SMARTLIST_FOREACH(big_fake_net_nodes, node_t *, n, n->is_possible_guard = 0); - entry_guard_t *g = sample_reachable_filtered_entry_guards(gs, NULL, 0); + entry_guard_t *g = first_reachable_filtered_entry_guard(gs, NULL, 0); tt_ptr_op(g, OP_EQ, NULL); done: @@ -1675,10 +1679,13 @@ test_entry_guard_manage_primary(void *arg) tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx)); }); - /* If we have one confirmed guard, that guards becomes the first primary - * guard, and the other primary guards get kept. */ + /** + * If we have one confirmed guard, that guards becomes the first primary + * only if its sampled_idx is smaller + * */ - /* find a non-primary guard... */ + /* find a non-primary guard... it should have a sampled_idx higher than + * existing primary guards */ entry_guard_t *confirmed = NULL; SMARTLIST_FOREACH(gs->sampled_entry_guards, entry_guard_t *, g, { if (! g->is_primary) { @@ -1694,15 +1701,13 @@ test_entry_guard_manage_primary(void *arg) smartlist_add_all(prev_guards, gs->primary_entry_guards); entry_guards_update_primary(gs); - /* and see what's primary now! */ + /* the confirmed guard should be at the end of the primary list! Hopefully, + * one of the primary guards with a lower sampled_idx will confirm soon :) + * Doing this won't make the client switches between primaries depending on + * the order of confirming events */ tt_int_op(smartlist_len(gs->primary_entry_guards), OP_EQ, n_primary); - tt_ptr_op(smartlist_get(gs->primary_entry_guards, 0), OP_EQ, confirmed); - SMARTLIST_FOREACH(gs->primary_entry_guards, entry_guard_t *, g, { - tt_assert(g->is_primary); - if (g_sl_idx == 0) - continue; - tt_ptr_op(g, OP_EQ, smartlist_get(prev_guards, g_sl_idx - 1)); - }); + tt_ptr_op(smartlist_get(gs->primary_entry_guards, + smartlist_len(gs->primary_entry_guards)-1), OP_EQ, confirmed); { entry_guard_t *prev_last_guard = smartlist_get(prev_guards, n_primary-1); tt_assert(! prev_last_guard->is_primary); @@ -1793,6 +1798,57 @@ test_entry_guard_guard_preferred(void *arg) } static void +test_entry_guard_correct_cascading_order(void *arg) +{ + (void)arg; + smartlist_t *old_primary_guards = smartlist_new(); + guard_selection_t *gs = guard_selection_new("default", GS_TYPE_NORMAL); + entry_guards_expand_sample(gs); + /** First, a test in which the primary guards need be pulled from different + * lists to fill up the primary list -- this may happen, if for example, not + * enough guards have confirmed yet */ + entry_guard_t *g; + /** just one confirmed */ + g = smartlist_get(gs->sampled_entry_guards, 2); + make_guard_confirmed(gs, g); + entry_guards_update_primary(gs); + g = smartlist_get(gs->primary_entry_guards, 0); + tt_int_op(g->sampled_idx, OP_EQ, 0); + g = smartlist_get(gs->primary_entry_guards, 1); + tt_int_op(g->sampled_idx, OP_EQ, 1); + g = smartlist_get(gs->primary_entry_guards, 2); + tt_int_op(g->sampled_idx, OP_EQ, 2); + + /** Now the primaries get all confirmed, and the primary list should not + * change */ + make_guard_confirmed(gs, smartlist_get(gs->primary_entry_guards, 0)); + make_guard_confirmed(gs, smartlist_get(gs->primary_entry_guards, 1)); + smartlist_add_all(old_primary_guards, gs->primary_entry_guards); + entry_guards_update_primary(gs); + smartlist_ptrs_eq(gs->primary_entry_guards, old_primary_guards); + /** the confirmed guards should also have the same set of guards, in the same + * order :-) */ + smartlist_ptrs_eq(gs->confirmed_entry_guards, gs->primary_entry_guards); + /** Now select a guard for a circuit, and make sure it is the first primary + * guard */ + unsigned state = 9999; + g = select_entry_guard_for_circuit(gs, GUARD_USAGE_TRAFFIC, NULL, &state); + tt_ptr_op(g, OP_EQ, smartlist_get(gs->primary_entry_guards, 0)); + /** Now, let's mark this guard as unreachable and let's update the lists */ + g->is_reachable = GUARD_REACHABLE_NO; + g->failing_since = approx_time() - 10; + g->last_tried_to_connect = approx_time() - 10; + state = 9999; + entry_guards_update_primary(gs); + g = select_entry_guard_for_circuit(gs, GUARD_USAGE_TRAFFIC, NULL, &state); + /** we should have switched to the next one is sampled order */ + tt_int_op(g->sampled_idx, OP_EQ, 1); + done: + smartlist_free(old_primary_guards); + guard_selection_free(gs); +} + +static void test_entry_guard_select_for_circuit_no_confirmed(void *arg) { /* Simpler cases: no gaurds are confirmed yet. */ @@ -3094,6 +3150,7 @@ struct testcase_t entrynodes_tests[] = { BFN_TEST(sample_reachable_filtered_empty), BFN_TEST(retry_unreachable), BFN_TEST(manage_primary), + BFN_TEST(correct_cascading_order), EN_TEST_FORK(guard_preferred), |