diff options
Diffstat (limited to 'src/feature/nodelist/node_select.c')
| -rw-r--r-- | src/feature/nodelist/node_select.c | 256 |
1 files changed, 153 insertions, 103 deletions
diff --git a/src/feature/nodelist/node_select.c b/src/feature/nodelist/node_select.c index 7b9e241e5b..ecb70aef14 100644 --- a/src/feature/nodelist/node_select.c +++ b/src/feature/nodelist/node_select.c @@ -1,7 +1,7 @@ /* Copyright (c) 2001 Matej Pfajfar. * Copyright (c) 2001-2004, Roger Dingledine. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. - * Copyright (c) 2007-2019, The Tor Project, Inc. */ + * Copyright (c) 2007-2020, The Tor Project, Inc. */ /* See LICENSE for licensing information */ /** @@ -19,6 +19,7 @@ #include "core/or/reasons.h" #include "feature/client/entrynodes.h" #include "feature/dirclient/dirclient.h" +#include "feature/dirclient/dirclient_modes.h" #include "feature/dircommon/directory.h" #include "feature/nodelist/describe.h" #include "feature/nodelist/dirlist.h" @@ -30,6 +31,7 @@ #include "feature/nodelist/routerset.h" #include "feature/relay/router.h" #include "feature/relay/routermode.h" +#include "lib/container/bitarray.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/math/fp.h" @@ -139,14 +141,14 @@ router_pick_dirserver_generic(smartlist_t *sourcelist, #define RETRY_ALTERNATE_IP_VERSION(retry_label) \ STMT_BEGIN \ if (result == NULL && try_ip_pref && options->ClientUseIPv4 \ - && fascist_firewall_use_ipv6(options) && !server_mode(options) \ + && reachable_addr_use_ipv6(options) && !server_mode(options) \ && !n_busy) { \ n_excluded = 0; \ n_busy = 0; \ try_ip_pref = 0; \ goto retry_label; \ } \ - STMT_END \ + STMT_END /* Common retry code for router_pick_directory_server_impl and * router_pick_trusteddirserver_impl. Retry without excluding nodes, but with @@ -210,18 +212,20 @@ router_picked_poor_directory_log(const routerstatus_t *rs) log_debug(LD_DIR, "Wanted to make an outgoing directory connection, but " "we couldn't find a directory that fit our criteria. " "Perhaps we will succeed next time with less strict criteria."); - } else if (!fascist_firewall_allows_rs(rs, FIREWALL_OR_CONNECTION, 1) - && !fascist_firewall_allows_rs(rs, FIREWALL_DIR_CONNECTION, 1) + } else if (!reachable_addr_allows_rs(rs, FIREWALL_OR_CONNECTION, 1) + && !reachable_addr_allows_rs(rs, FIREWALL_DIR_CONNECTION, 1) ) { /* This is rare, and might be interesting to users trying to diagnose * connection issues on dual-stack machines. */ + char *ipv4_str = tor_addr_to_str_dup(&rs->ipv4_addr); log_info(LD_DIR, "Selected a directory %s with non-preferred OR and Dir " "addresses for launching an outgoing connection: " "IPv4 %s OR %d Dir %d IPv6 %s OR %d Dir %d", routerstatus_describe(rs), - fmt_addr32(rs->addr), rs->or_port, - rs->dir_port, fmt_addr(&rs->ipv6_addr), - rs->ipv6_orport, rs->dir_port); + ipv4_str, rs->ipv4_orport, + rs->ipv4_dirport, fmt_addr(&rs->ipv6_addr), + rs->ipv6_orport, rs->ipv4_dirport); + tor_free(ipv4_str); } } @@ -264,7 +268,7 @@ router_is_already_dir_fetching(const tor_addr_port_t *ap, int serverdesc, * If so, return 1, if not, return 0. */ static int -router_is_already_dir_fetching_(uint32_t ipv4_addr, +router_is_already_dir_fetching_(const tor_addr_t *ipv4_addr, const tor_addr_t *ipv6_addr, uint16_t dir_port, int serverdesc, @@ -273,7 +277,7 @@ router_is_already_dir_fetching_(uint32_t ipv4_addr, tor_addr_port_t ipv4_dir_ap, ipv6_dir_ap; /* Assume IPv6 DirPort is the same as IPv4 DirPort */ - tor_addr_from_ipv4h(&ipv4_dir_ap.addr, ipv4_addr); + tor_addr_copy(&ipv4_dir_ap.addr, ipv4_addr); ipv4_dir_ap.port = dir_port; tor_addr_copy(&ipv6_dir_ap.addr, ipv6_addr); ipv6_dir_ap.port = dir_port; @@ -319,9 +323,13 @@ router_pick_directory_server_impl(dirinfo_type_t type, int flags, overloaded_direct = smartlist_new(); overloaded_tunnel = smartlist_new(); - const int skip_or_fw = router_skip_or_reachability(options, try_ip_pref); - const int skip_dir_fw = router_skip_dir_reachability(options, try_ip_pref); - const int must_have_or = directory_must_use_begindir(options); + const int skip_or_fw = router_or_conn_should_skip_reachable_address_check( + options, + try_ip_pref); + const int skip_dir_fw = router_dir_conn_should_skip_reachable_address_check( + options, + try_ip_pref); + const int must_have_or = dirclient_must_use_begindir(options); /* Find all the running dirservers we know about. */ SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) { @@ -346,9 +354,9 @@ router_pick_directory_server_impl(dirinfo_type_t type, int flags, continue; } - if (router_is_already_dir_fetching_(status->addr, + if (router_is_already_dir_fetching_(&status->ipv4_addr, &status->ipv6_addr, - status->dir_port, + status->ipv4_dirport, no_serverdesc_fetching, no_microdesc_fetching)) { ++n_busy; @@ -366,12 +374,12 @@ router_pick_directory_server_impl(dirinfo_type_t type, int flags, * we try routers that only have one address both times.) */ if (!fascistfirewall || skip_or_fw || - fascist_firewall_allows_node(node, FIREWALL_OR_CONNECTION, + reachable_addr_allows_node(node, FIREWALL_OR_CONNECTION, try_ip_pref)) smartlist_add(is_trusted ? trusted_tunnel : is_overloaded ? overloaded_tunnel : tunnel, (void*)node); else if (!must_have_or && (skip_dir_fw || - fascist_firewall_allows_node(node, FIREWALL_DIR_CONNECTION, + reachable_addr_allows_node(node, FIREWALL_DIR_CONNECTION, try_ip_pref))) smartlist_add(is_trusted ? trusted_direct : is_overloaded ? overloaded_direct : direct, (void*)node); @@ -630,6 +638,7 @@ compute_weighted_bandwidths(const smartlist_t *sl, } weight_scale = networkstatus_get_weight_scale_param(NULL); + tor_assert(weight_scale >= 1); if (rule == WEIGHT_FOR_GUARD) { Wg = networkstatus_get_bw_weight(NULL, "Wgg", -1); @@ -871,90 +880,79 @@ routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router) nodelist_add_node_and_family(sl, node); } -/** Return a random running node from the nodelist. Never - * pick a node that is in - * <b>excludedsmartlist</b>, or which matches <b>excludedset</b>, - * even if they are the only nodes available. - * If <b>CRN_NEED_UPTIME</b> is set in flags and any router has more than - * a minimum uptime, return one of those. - * If <b>CRN_NEED_CAPACITY</b> is set in flags, weight your choice by the - * advertised capacity of each router. - * If <b>CRN_NEED_GUARD</b> is set in flags, consider only Guard routers. - * If <b>CRN_WEIGHT_AS_EXIT</b> is set in flags, we weight bandwidths as if - * picking an exit node, otherwise we weight bandwidths for picking a relay - * node (that is, possibly discounting exit nodes). - * If <b>CRN_NEED_DESC</b> is set in flags, we only consider nodes that - * have a routerinfo or microdescriptor -- that is, enough info to be - * used to build a circuit. - * If <b>CRN_PREF_ADDR</b> is set in flags, we only consider nodes that - * have an address that is preferred by the ClientPreferIPv6ORPort setting - * (regardless of this flag, we exclude nodes that aren't allowed by the - * firewall, including ClientUseIPv4 0 and fascist_firewall_use_ipv6() == 0). - */ -const node_t * -router_choose_random_node(smartlist_t *excludedsmartlist, - routerset_t *excludedset, - router_crn_flags_t flags) -{ /* XXXX MOVE */ - const int need_uptime = (flags & CRN_NEED_UPTIME) != 0; - const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0; - const int need_guard = (flags & CRN_NEED_GUARD) != 0; - const int weight_for_exit = (flags & CRN_WEIGHT_AS_EXIT) != 0; - const int need_desc = (flags & CRN_NEED_DESC) != 0; - const int pref_addr = (flags & CRN_PREF_ADDR) != 0; - const int direct_conn = (flags & CRN_DIRECT_CONN) != 0; - const int rendezvous_v3 = (flags & CRN_RENDEZVOUS_V3) != 0; - - smartlist_t *sl=smartlist_new(), - *excludednodes=smartlist_new(); - const node_t *choice = NULL; - const routerinfo_t *r; - bandwidth_weight_rule_t rule; +/** + * Remove every node_t that appears in <b>excluded</b> from <b>sl</b>. + * + * Behaves like smartlist_subtract, but uses nodelist_idx values to deliver + * linear performance when smartlist_subtract would be quadratic. + **/ +static void +nodelist_subtract(smartlist_t *sl, const smartlist_t *excluded) +{ + const smartlist_t *nodelist = nodelist_get_list(); + const int nodelist_len = smartlist_len(nodelist); + bitarray_t *excluded_idx = bitarray_init_zero(nodelist_len); - tor_assert(!(weight_for_exit && need_guard)); - rule = weight_for_exit ? WEIGHT_FOR_EXIT : - (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID); - - SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), node_t *, node) { - if (node_allows_single_hop_exits(node)) { - /* Exclude relays that allow single hop exit circuits. This is an - * obsolete option since 0.2.9.2-alpha and done by default in - * 0.3.1.0-alpha. */ - smartlist_add(excludednodes, node); - } else if (rendezvous_v3 && - !node_supports_v3_rendezvous_point(node)) { - /* Exclude relays that do not support to rendezvous for a hidden service - * version 3. */ - smartlist_add(excludednodes, node); + /* We haven't used nodelist_idx in this way previously, so I'm going to be + * paranoid in this code, and check that nodelist_idx is correct for every + * node before we use it. If we fail, we fall back to smartlist_subtract(). + */ + + /* Set the excluded_idx bit corresponding to every excluded node... + */ + SMARTLIST_FOREACH_BEGIN(excluded, const node_t *, node) { + const int idx = node->nodelist_idx; + if (BUG(idx < 0) || BUG(idx >= nodelist_len) || + BUG(node != smartlist_get(nodelist, idx))) { + goto internal_error; } + bitarray_set(excluded_idx, idx); } SMARTLIST_FOREACH_END(node); - /* If the node_t is not found we won't be to exclude ourself but we - * won't be able to pick ourself in router_choose_random_node() so - * this is fine to at least try with our routerinfo_t object. */ - if ((r = router_get_my_routerinfo())) - routerlist_add_node_and_family(excludednodes, r); + /* Then remove them from sl. + */ + SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) { + const int idx = node->nodelist_idx; + if (BUG(idx < 0) || BUG(idx >= nodelist_len) || + BUG(node != smartlist_get(nodelist, idx))) { + goto internal_error; + } + if (bitarray_is_set(excluded_idx, idx)) { + SMARTLIST_DEL_CURRENT(sl, node); + } + } SMARTLIST_FOREACH_END(node); + + bitarray_free(excluded_idx); + return; + + internal_error: + log_warn(LD_BUG, "Internal error prevented us from using the fast method " + "for subtracting nodelists. Falling back to the quadratic way."); + smartlist_subtract(sl, excluded); + bitarray_free(excluded_idx); +} + +/* Node selection helper for router_choose_random_node(). + * + * Populates a node list based on <b>flags</b>, ignoring nodes in + * <b>excludednodes</b> and <b>excludedset</b>. Chooses the node based on + * <b>rule</b>. */ +static const node_t * +router_choose_random_node_helper(smartlist_t *excludednodes, + routerset_t *excludedset, + router_crn_flags_t flags, + bandwidth_weight_rule_t rule) +{ + smartlist_t *sl=smartlist_new(); + const node_t *choice = NULL; - router_add_running_nodes_to_smartlist(sl, need_uptime, need_capacity, - need_guard, need_desc, pref_addr, - direct_conn); + router_add_running_nodes_to_smartlist(sl, flags); log_debug(LD_CIRC, "We found %d running nodes.", smartlist_len(sl)); - smartlist_subtract(sl,excludednodes); - log_debug(LD_CIRC, - "We removed %d excludednodes, leaving %d nodes.", - smartlist_len(excludednodes), - smartlist_len(sl)); + nodelist_subtract(sl, excludednodes); - if (excludedsmartlist) { - smartlist_subtract(sl,excludedsmartlist); - log_debug(LD_CIRC, - "We removed %d excludedsmartlist, leaving %d nodes.", - smartlist_len(excludedsmartlist), - smartlist_len(sl)); - } if (excludedset) { routerset_subtract_nodes(sl,excludedset); log_debug(LD_CIRC, @@ -966,18 +964,66 @@ router_choose_random_node(smartlist_t *excludedsmartlist, choice = node_sl_choose_by_bandwidth(sl, rule); smartlist_free(sl); + + return choice; +} + +/** Return a random running node from the nodelist. Never pick a node that is + * in <b>excludedsmartlist</b>, or which matches <b>excludedset</b>, even if + * they are the only nodes available. + * + * <b>flags</b> is a set of CRN_* flags, see + * router_add_running_nodes_to_smartlist() for details. + */ +const node_t * +router_choose_random_node(smartlist_t *excludedsmartlist, + routerset_t *excludedset, + router_crn_flags_t flags) +{ + /* A limited set of flags, used for fallback node selection. + */ + const bool need_uptime = (flags & CRN_NEED_UPTIME) != 0; + const bool need_capacity = (flags & CRN_NEED_CAPACITY) != 0; + const bool need_guard = (flags & CRN_NEED_GUARD) != 0; + const bool pref_addr = (flags & CRN_PREF_ADDR) != 0; + + smartlist_t *excludednodes=smartlist_new(); + const node_t *choice = NULL; + const routerinfo_t *r; + bandwidth_weight_rule_t rule; + + rule = (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID); + + /* If the node_t is not found we won't be to exclude ourself but we + * won't be able to pick ourself in router_choose_random_node() so + * this is fine to at least try with our routerinfo_t object. */ + if ((r = router_get_my_routerinfo())) + routerlist_add_node_and_family(excludednodes, r); + + if (excludedsmartlist) { + smartlist_add_all(excludednodes, excludedsmartlist); + } + + choice = router_choose_random_node_helper(excludednodes, + excludedset, + flags, + rule); + if (!choice && (need_uptime || need_capacity || need_guard || pref_addr)) { - /* try once more -- recurse but with fewer restrictions. */ + /* try once more, with fewer restrictions. */ log_info(LD_CIRC, - "We couldn't find any live%s%s%s routers; falling back " + "We couldn't find any live%s%s%s%s routers; falling back " "to list of all routers.", need_capacity?", fast":"", need_uptime?", stable":"", - need_guard?", guard":""); + need_guard?", guard":"", + pref_addr?", preferred address":""); flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD| CRN_PREF_ADDR); - choice = router_choose_random_node( - excludedsmartlist, excludedset, flags); + choice = router_choose_random_node_helper(excludednodes, + excludedset, + flags, + rule); } smartlist_free(excludednodes); if (!choice) { @@ -1072,9 +1118,13 @@ router_pick_trusteddirserver_impl(const smartlist_t *sourcelist, overloaded_direct = smartlist_new(); overloaded_tunnel = smartlist_new(); - const int skip_or_fw = router_skip_or_reachability(options, try_ip_pref); - const int skip_dir_fw = router_skip_dir_reachability(options, try_ip_pref); - const int must_have_or = directory_must_use_begindir(options); + const int skip_or_fw = router_or_conn_should_skip_reachable_address_check( + options, + try_ip_pref); + const int skip_dir_fw = router_dir_conn_should_skip_reachable_address_check( + options, + try_ip_pref); + const int must_have_or = dirclient_must_use_begindir(options); SMARTLIST_FOREACH_BEGIN(sourcelist, const dir_server_t *, d) { @@ -1095,9 +1145,9 @@ router_pick_trusteddirserver_impl(const smartlist_t *sourcelist, continue; } - if (router_is_already_dir_fetching_(d->addr, + if (router_is_already_dir_fetching_(&d->ipv4_addr, &d->ipv6_addr, - d->dir_port, + d->ipv4_dirport, no_serverdesc_fetching, no_microdesc_fetching)) { ++n_busy; @@ -1112,11 +1162,11 @@ router_pick_trusteddirserver_impl(const smartlist_t *sourcelist, * we try routers that only have one address both times.) */ if (!fascistfirewall || skip_or_fw || - fascist_firewall_allows_dir_server(d, FIREWALL_OR_CONNECTION, + reachable_addr_allows_dir_server(d, FIREWALL_OR_CONNECTION, try_ip_pref)) smartlist_add(is_overloaded ? overloaded_tunnel : tunnel, (void*)d); else if (!must_have_or && (skip_dir_fw || - fascist_firewall_allows_dir_server(d, FIREWALL_DIR_CONNECTION, + reachable_addr_allows_dir_server(d, FIREWALL_DIR_CONNECTION, try_ip_pref))) smartlist_add(is_overloaded ? overloaded_direct : direct, (void*)d); } |