diff options
author | Nick Mathewson <nickm@torproject.org> | 2018-09-19 14:10:15 -0400 |
---|---|---|
committer | Nick Mathewson <nickm@torproject.org> | 2018-09-19 17:08:57 -0400 |
commit | 08e3b88f0774fedb41a6b1c170a710dd12a7cb90 (patch) | |
tree | 856a7f9ce528021c1d0c9d09b631d09aeec2356c /src/feature/nodelist/node_select.c | |
parent | 119159677be14351ebcae647d3988f4f2fd9eb72 (diff) | |
download | tor-08e3b88f0774fedb41a6b1c170a710dd12a7cb90.tar.gz tor-08e3b88f0774fedb41a6b1c170a710dd12a7cb90.zip |
Split routerlist.c into 4 separate modules
There are now separate modules for:
* the list of router descriptors
* the list of authorities and fallbacks
* managing authority certificates
* selecting random nodes
Diffstat (limited to 'src/feature/nodelist/node_select.c')
-rw-r--r-- | src/feature/nodelist/node_select.c | 1108 |
1 files changed, 1108 insertions, 0 deletions
diff --git a/src/feature/nodelist/node_select.c b/src/feature/nodelist/node_select.c new file mode 100644 index 0000000000..a9f045d456 --- /dev/null +++ b/src/feature/nodelist/node_select.c @@ -0,0 +1,1108 @@ +/* Copyright (c) 2001 Matej Pfajfar. + * Copyright (c) 2001-2004, Roger Dingledine. + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file node_select.c + * \brief Code to choose nodes randomly based on restrictions and + * weighted probabilities. + **/ + +#define NODE_SELECT_PRIVATE +#include "core/or/or.h" + +#include "app/config/config.h" +#include "core/mainloop/connection.h" +#include "core/or/policies.h" +#include "core/or/reasons.h" +#include "feature/client/entrynodes.h" +#include "feature/dircache/directory.h" +#include "feature/nodelist/dirlist.h" +#include "feature/nodelist/microdesc.h" +#include "feature/nodelist/networkstatus.h" +#include "feature/nodelist/node_select.h" +#include "feature/nodelist/nodelist.h" +#include "feature/nodelist/routerlist.h" +#include "feature/nodelist/routerset.h" +#include "feature/relay/router.h" +#include "lib/crypt_ops/crypto_rand.h" +#include "lib/math/fp.h" + +#include "feature/dirclient/dir_server_st.h" +#include "feature/nodelist/networkstatus_st.h" +#include "feature/nodelist/node_st.h" +#include "feature/nodelist/routerinfo_st.h" +#include "feature/nodelist/routerstatus_st.h" + +static int compute_weighted_bandwidths(const smartlist_t *sl, + bandwidth_weight_rule_t rule, + double **bandwidths_out, + double *total_bandwidth_out); +static const routerstatus_t *router_pick_trusteddirserver_impl( + const smartlist_t *sourcelist, dirinfo_type_t auth, + int flags, int *n_busy_out); +static const routerstatus_t *router_pick_dirserver_generic( + smartlist_t *sourcelist, + dirinfo_type_t type, int flags); + +/** Try to find a running dirserver that supports operations of <b>type</b>. + * + * If there are no running dirservers in our routerlist and the + * <b>PDS_RETRY_IF_NO_SERVERS</b> flag is set, set all the fallback ones + * (including authorities) as running again, and pick one. + * + * If the <b>PDS_IGNORE_FASCISTFIREWALL</b> flag is set, then include + * dirservers that we can't reach. + * + * If the <b>PDS_ALLOW_SELF</b> flag is not set, then don't include ourself + * (if we're a dirserver). + * + * Don't pick a fallback directory mirror if any non-fallback is viable; + * (the fallback directory mirrors include the authorities) + * try to avoid using servers that have returned 503 recently. + */ +const routerstatus_t * +router_pick_directory_server(dirinfo_type_t type, int flags) +{ + int busy = 0; + const routerstatus_t *choice; + + choice = router_pick_directory_server_impl(type, flags, &busy); + if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS)) + return choice; + + if (busy) { + /* If the reason that we got no server is that servers are "busy", + * we must be excluding good servers because we already have serverdesc + * fetches with them. Do not mark down servers up because of this. */ + tor_assert((flags & (PDS_NO_EXISTING_SERVERDESC_FETCH| + PDS_NO_EXISTING_MICRODESC_FETCH))); + return NULL; + } + + log_info(LD_DIR, + "No reachable router entries for dirservers. " + "Trying them all again."); + /* mark all fallback directory mirrors as up again */ + router_reset_status_download_failures(); + /* try again */ + choice = router_pick_directory_server_impl(type, flags, NULL); + return choice; +} + +/** Try to find a running fallback directory. Flags are as for + * router_pick_directory_server. + */ +const routerstatus_t * +router_pick_dirserver_generic(smartlist_t *sourcelist, + dirinfo_type_t type, int flags) +{ + const routerstatus_t *choice; + int busy = 0; + + if (smartlist_len(sourcelist) == 1) { + /* If there's only one choice, then we should disable the logic that + * would otherwise prevent us from choosing ourself. */ + flags |= PDS_ALLOW_SELF; + } + + choice = router_pick_trusteddirserver_impl(sourcelist, type, flags, &busy); + if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS)) + return choice; + if (busy) { + /* If the reason that we got no server is that servers are "busy", + * we must be excluding good servers because we already have serverdesc + * fetches with them. Do not mark down servers up because of this. */ + tor_assert((flags & (PDS_NO_EXISTING_SERVERDESC_FETCH| + PDS_NO_EXISTING_MICRODESC_FETCH))); + return NULL; + } + + log_info(LD_DIR, + "No dirservers are reachable. Trying them all again."); + mark_all_dirservers_up(sourcelist); + return router_pick_trusteddirserver_impl(sourcelist, type, flags, NULL); +} + +/* Common retry code for router_pick_directory_server_impl and + * router_pick_trusteddirserver_impl. Retry with the non-preferred IP version. + * Must be called before RETRY_WITHOUT_EXCLUDE(). + * + * If we got no result, and we are applying IP preferences, and we are a + * client that could use an alternate IP version, try again with the + * opposite preferences. */ +#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) \ + && !n_busy) { \ + n_excluded = 0; \ + n_busy = 0; \ + try_ip_pref = 0; \ + goto retry_label; \ + } \ + STMT_END \ + +/* Common retry code for router_pick_directory_server_impl and + * router_pick_trusteddirserver_impl. Retry without excluding nodes, but with + * the preferred IP version. Must be called after RETRY_ALTERNATE_IP_VERSION(). + * + * If we got no result, and we are excluding nodes, and StrictNodes is + * not set, try again without excluding nodes. */ +#define RETRY_WITHOUT_EXCLUDE(retry_label) \ + STMT_BEGIN \ + if (result == NULL && try_excluding && !options->StrictNodes \ + && n_excluded && !n_busy) { \ + try_excluding = 0; \ + n_excluded = 0; \ + n_busy = 0; \ + try_ip_pref = 1; \ + goto retry_label; \ + } \ + STMT_END + +/* Common code used in the loop within router_pick_directory_server_impl and + * router_pick_trusteddirserver_impl. + * + * Check if the given <b>identity</b> supports extrainfo. If not, skip further + * checks. + */ +#define SKIP_MISSING_TRUSTED_EXTRAINFO(type, identity) \ + STMT_BEGIN \ + int is_trusted_extrainfo = router_digest_is_trusted_dir_type( \ + (identity), EXTRAINFO_DIRINFO); \ + if (((type) & EXTRAINFO_DIRINFO) && \ + !router_supports_extrainfo((identity), is_trusted_extrainfo)) \ + continue; \ + STMT_END + +#ifndef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP +#define LOG_FALSE_POSITIVES_DURING_BOOTSTRAP 0 +#endif + +/* Log a message if rs is not found or not a preferred address */ +static void +router_picked_poor_directory_log(const routerstatus_t *rs) +{ + const networkstatus_t *usable_consensus; + usable_consensus = networkstatus_get_reasonably_live_consensus(time(NULL), + usable_consensus_flavor()); + +#if !LOG_FALSE_POSITIVES_DURING_BOOTSTRAP + /* Don't log early in the bootstrap process, it's normal to pick from a + * small pool of nodes. Of course, this won't help if we're trying to + * diagnose bootstrap issues. */ + if (!smartlist_len(nodelist_get_list()) || !usable_consensus + || !router_have_minimum_dir_info()) { + return; + } +#endif /* !LOG_FALSE_POSITIVES_DURING_BOOTSTRAP */ + + /* We couldn't find a node, or the one we have doesn't fit our preferences. + * Sometimes this is normal, sometimes it can be a reachability issue. */ + if (!rs) { + /* This happens a lot, so it's at debug level */ + 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) + ) { + /* This is rare, and might be interesting to users trying to diagnose + * connection issues on dual-stack machines. */ + 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); + } +} + +#undef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP + +/* Check if we already have a directory fetch from ap, for serverdesc + * (including extrainfo) or microdesc documents. + * If so, return 1, if not, return 0. + * Also returns 0 if addr is NULL, tor_addr_is_null(addr), or dir_port is 0. + */ +STATIC int +router_is_already_dir_fetching(const tor_addr_port_t *ap, int serverdesc, + int microdesc) +{ + if (!ap || tor_addr_is_null(&ap->addr) || !ap->port) { + return 0; + } + + /* XX/teor - we're not checking tunnel connections here, see #17848 + */ + if (serverdesc && ( + connection_get_by_type_addr_port_purpose( + CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_SERVERDESC) + || connection_get_by_type_addr_port_purpose( + CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_EXTRAINFO))) { + return 1; + } + + if (microdesc && ( + connection_get_by_type_addr_port_purpose( + CONN_TYPE_DIR, &ap->addr, ap->port, DIR_PURPOSE_FETCH_MICRODESC))) { + return 1; + } + + return 0; +} + +/* Check if we already have a directory fetch from the ipv4 or ipv6 + * router, for serverdesc (including extrainfo) or microdesc documents. + * If so, return 1, if not, return 0. + */ +static int +router_is_already_dir_fetching_(uint32_t ipv4_addr, + const tor_addr_t *ipv6_addr, + uint16_t dir_port, + int serverdesc, + int microdesc) +{ + 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); + ipv4_dir_ap.port = dir_port; + tor_addr_copy(&ipv6_dir_ap.addr, ipv6_addr); + ipv6_dir_ap.port = dir_port; + + return (router_is_already_dir_fetching(&ipv4_dir_ap, serverdesc, microdesc) + || router_is_already_dir_fetching(&ipv6_dir_ap, serverdesc, microdesc)); +} + +/** Pick a random running valid directory server/mirror from our + * routerlist. Arguments are as for router_pick_directory_server(), except: + * + * If <b>n_busy_out</b> is provided, set *<b>n_busy_out</b> to the number of + * directories that we excluded for no other reason than + * PDS_NO_EXISTING_SERVERDESC_FETCH or PDS_NO_EXISTING_MICRODESC_FETCH. + */ +STATIC const routerstatus_t * +router_pick_directory_server_impl(dirinfo_type_t type, int flags, + int *n_busy_out) +{ + const or_options_t *options = get_options(); + const node_t *result; + smartlist_t *direct, *tunnel; + smartlist_t *trusted_direct, *trusted_tunnel; + smartlist_t *overloaded_direct, *overloaded_tunnel; + time_t now = time(NULL); + const networkstatus_t *consensus = networkstatus_get_latest_consensus(); + const int requireother = ! (flags & PDS_ALLOW_SELF); + const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL); + const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH); + const int no_microdesc_fetching = (flags & PDS_NO_EXISTING_MICRODESC_FETCH); + int try_excluding = 1, n_excluded = 0, n_busy = 0; + int try_ip_pref = 1; + + if (!consensus) + return NULL; + + retry_search: + + direct = smartlist_new(); + tunnel = smartlist_new(); + trusted_direct = smartlist_new(); + trusted_tunnel = smartlist_new(); + 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); + + /* Find all the running dirservers we know about. */ + SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) { + int is_trusted; + int is_overloaded; + const routerstatus_t *status = node->rs; + const country_t country = node->country; + if (!status) + continue; + + if (!node->is_running || !node_is_dir(node) || !node->is_valid) + continue; + if (requireother && router_digest_is_me(node->identity)) + continue; + + SKIP_MISSING_TRUSTED_EXTRAINFO(type, node->identity); + + if (try_excluding && + routerset_contains_routerstatus(options->ExcludeNodes, status, + country)) { + ++n_excluded; + continue; + } + + if (router_is_already_dir_fetching_(status->addr, + &status->ipv6_addr, + status->dir_port, + no_serverdesc_fetching, + no_microdesc_fetching)) { + ++n_busy; + continue; + } + + is_overloaded = status->last_dir_503_at + DIR_503_TIMEOUT > now; + is_trusted = router_digest_is_trusted_dir(node->identity); + + /* Clients use IPv6 addresses if the server has one and the client + * prefers IPv6. + * Add the router if its preferred address and port are reachable. + * If we don't get any routers, we'll try again with the non-preferred + * address for each router (if any). (To ensure correct load-balancing + * we try routers that only have one address both times.) + */ + if (!fascistfirewall || skip_or_fw || + fascist_firewall_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, + try_ip_pref))) + smartlist_add(is_trusted ? trusted_direct : + is_overloaded ? overloaded_direct : direct, (void*)node); + } SMARTLIST_FOREACH_END(node); + + if (smartlist_len(tunnel)) { + result = node_sl_choose_by_bandwidth(tunnel, WEIGHT_FOR_DIR); + } else if (smartlist_len(overloaded_tunnel)) { + result = node_sl_choose_by_bandwidth(overloaded_tunnel, + WEIGHT_FOR_DIR); + } else if (smartlist_len(trusted_tunnel)) { + /* FFFF We don't distinguish between trusteds and overloaded trusteds + * yet. Maybe one day we should. */ + /* FFFF We also don't load balance over authorities yet. I think this + * is a feature, but it could easily be a bug. -RD */ + result = smartlist_choose(trusted_tunnel); + } else if (smartlist_len(direct)) { + result = node_sl_choose_by_bandwidth(direct, WEIGHT_FOR_DIR); + } else if (smartlist_len(overloaded_direct)) { + result = node_sl_choose_by_bandwidth(overloaded_direct, + WEIGHT_FOR_DIR); + } else { + result = smartlist_choose(trusted_direct); + } + smartlist_free(direct); + smartlist_free(tunnel); + smartlist_free(trusted_direct); + smartlist_free(trusted_tunnel); + smartlist_free(overloaded_direct); + smartlist_free(overloaded_tunnel); + + RETRY_ALTERNATE_IP_VERSION(retry_search); + + RETRY_WITHOUT_EXCLUDE(retry_search); + + if (n_busy_out) + *n_busy_out = n_busy; + + router_picked_poor_directory_log(result ? result->rs : NULL); + + return result ? result->rs : NULL; +} + +/** Given an array of double/uint64_t unions that are currently being used as + * doubles, convert them to uint64_t, and try to scale them linearly so as to + * much of the range of uint64_t. If <b>total_out</b> is provided, set it to + * the sum of all elements in the array _before_ scaling. */ +STATIC void +scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in, + int n_entries, + uint64_t *total_out) +{ + double total = 0.0; + double scale_factor = 0.0; + int i; + + for (i = 0; i < n_entries; ++i) + total += entries_in[i]; + + if (total > 0.0) { + scale_factor = ((double)INT64_MAX) / total; + scale_factor /= 4.0; /* make sure we're very far away from overflowing */ + } + + for (i = 0; i < n_entries; ++i) + entries_out[i] = tor_llround(entries_in[i] * scale_factor); + + if (total_out) + *total_out = (uint64_t) total; +} + +/** Pick a random element of <b>n_entries</b>-element array <b>entries</b>, + * choosing each element with a probability proportional to its (uint64_t) + * value, and return the index of that element. If all elements are 0, choose + * an index at random. Return -1 on error. + */ +STATIC int +choose_array_element_by_weight(const uint64_t *entries, int n_entries) +{ + int i; + uint64_t rand_val; + uint64_t total = 0; + + for (i = 0; i < n_entries; ++i) + total += entries[i]; + + if (n_entries < 1) + return -1; + + if (total == 0) + return crypto_rand_int(n_entries); + + tor_assert(total < INT64_MAX); + + rand_val = crypto_rand_uint64(total); + + return select_array_member_cumulative_timei( + entries, n_entries, total, rand_val); +} + +/** Return bw*1000, unless bw*1000 would overflow, in which case return + * INT32_MAX. */ +static inline int32_t +kb_to_bytes(uint32_t bw) +{ + return (bw > (INT32_MAX/1000)) ? INT32_MAX : bw*1000; +} + +/** Helper function: + * choose a random element of smartlist <b>sl</b> of nodes, weighted by + * the advertised bandwidth of each element using the consensus + * bandwidth weights. + * + * If <b>rule</b>==WEIGHT_FOR_EXIT. we're picking an exit node: consider all + * nodes' bandwidth equally regardless of their Exit status, since there may + * be some in the list because they exit to obscure ports. If + * <b>rule</b>==NO_WEIGHTING, we're picking a non-exit node: weight + * exit-node's bandwidth less depending on the smallness of the fraction of + * Exit-to-total bandwidth. If <b>rule</b>==WEIGHT_FOR_GUARD, we're picking a + * guard node: consider all guard's bandwidth equally. Otherwise, weight + * guards proportionally less. + */ +static const node_t * +smartlist_choose_node_by_bandwidth_weights(const smartlist_t *sl, + bandwidth_weight_rule_t rule) +{ + double *bandwidths_dbl=NULL; + uint64_t *bandwidths_u64=NULL; + + if (compute_weighted_bandwidths(sl, rule, &bandwidths_dbl, NULL) < 0) + return NULL; + + bandwidths_u64 = tor_calloc(smartlist_len(sl), sizeof(uint64_t)); + scale_array_elements_to_u64(bandwidths_u64, bandwidths_dbl, + smartlist_len(sl), NULL); + + { + int idx = choose_array_element_by_weight(bandwidths_u64, + smartlist_len(sl)); + tor_free(bandwidths_dbl); + tor_free(bandwidths_u64); + return idx < 0 ? NULL : smartlist_get(sl, idx); + } +} + +/** When weighting bridges, enforce these values as lower and upper + * bound for believable bandwidth, because there is no way for us + * to verify a bridge's bandwidth currently. */ +#define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000 /* 20 kB/sec */ +#define BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000 /* 100 kB/sec */ + +/** Return the smaller of the router's configured BandwidthRate + * and its advertised capacity, making sure to stay within the + * interval between bridge-min-believe-bw and + * bridge-max-believe-bw. */ +static uint32_t +bridge_get_advertised_bandwidth_bounded(routerinfo_t *router) +{ + uint32_t result = router->bandwidthcapacity; + if (result > router->bandwidthrate) + result = router->bandwidthrate; + if (result > BRIDGE_MAX_BELIEVABLE_BANDWIDTH) + result = BRIDGE_MAX_BELIEVABLE_BANDWIDTH; + else if (result < BRIDGE_MIN_BELIEVABLE_BANDWIDTH) + result = BRIDGE_MIN_BELIEVABLE_BANDWIDTH; + return result; +} + +/** Given a list of routers and a weighting rule as in + * smartlist_choose_node_by_bandwidth_weights, compute weighted bandwidth + * values for each node and store them in a freshly allocated + * *<b>bandwidths_out</b> of the same length as <b>sl</b>, and holding results + * as doubles. If <b>total_bandwidth_out</b> is non-NULL, set it to the total + * of all the bandwidths. + * Return 0 on success, -1 on failure. */ +static int +compute_weighted_bandwidths(const smartlist_t *sl, + bandwidth_weight_rule_t rule, + double **bandwidths_out, + double *total_bandwidth_out) +{ + int64_t weight_scale; + double Wg = -1, Wm = -1, We = -1, Wd = -1; + double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1; + guardfraction_bandwidth_t guardfraction_bw; + double *bandwidths = NULL; + double total_bandwidth = 0.0; + + tor_assert(sl); + tor_assert(bandwidths_out); + + /* Can't choose exit and guard at same time */ + tor_assert(rule == NO_WEIGHTING || + rule == WEIGHT_FOR_EXIT || + rule == WEIGHT_FOR_GUARD || + rule == WEIGHT_FOR_MID || + rule == WEIGHT_FOR_DIR); + + *bandwidths_out = NULL; + + if (total_bandwidth_out) { + *total_bandwidth_out = 0.0; + } + + if (smartlist_len(sl) == 0) { + log_info(LD_CIRC, + "Empty routerlist passed in to consensus weight node " + "selection for rule %s", + bandwidth_weight_rule_to_string(rule)); + return -1; + } + + weight_scale = networkstatus_get_weight_scale_param(NULL); + + if (rule == WEIGHT_FOR_GUARD) { + Wg = networkstatus_get_bw_weight(NULL, "Wgg", -1); + Wm = networkstatus_get_bw_weight(NULL, "Wgm", -1); /* Bridges */ + We = 0; + Wd = networkstatus_get_bw_weight(NULL, "Wgd", -1); + + Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1); + Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1); + Web = networkstatus_get_bw_weight(NULL, "Web", -1); + Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1); + } else if (rule == WEIGHT_FOR_MID) { + Wg = networkstatus_get_bw_weight(NULL, "Wmg", -1); + Wm = networkstatus_get_bw_weight(NULL, "Wmm", -1); + We = networkstatus_get_bw_weight(NULL, "Wme", -1); + Wd = networkstatus_get_bw_weight(NULL, "Wmd", -1); + + Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1); + Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1); + Web = networkstatus_get_bw_weight(NULL, "Web", -1); + Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1); + } else if (rule == WEIGHT_FOR_EXIT) { + // Guards CAN be exits if they have weird exit policies + // They are d then I guess... + We = networkstatus_get_bw_weight(NULL, "Wee", -1); + Wm = networkstatus_get_bw_weight(NULL, "Wem", -1); /* Odd exit policies */ + Wd = networkstatus_get_bw_weight(NULL, "Wed", -1); + Wg = networkstatus_get_bw_weight(NULL, "Weg", -1); /* Odd exit policies */ + + Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1); + Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1); + Web = networkstatus_get_bw_weight(NULL, "Web", -1); + Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1); + } else if (rule == WEIGHT_FOR_DIR) { + We = networkstatus_get_bw_weight(NULL, "Wbe", -1); + Wm = networkstatus_get_bw_weight(NULL, "Wbm", -1); + Wd = networkstatus_get_bw_weight(NULL, "Wbd", -1); + Wg = networkstatus_get_bw_weight(NULL, "Wbg", -1); + + Wgb = Wmb = Web = Wdb = weight_scale; + } else if (rule == NO_WEIGHTING) { + Wg = Wm = We = Wd = weight_scale; + Wgb = Wmb = Web = Wdb = weight_scale; + } + + if (Wg < 0 || Wm < 0 || We < 0 || Wd < 0 || Wgb < 0 || Wmb < 0 || Wdb < 0 + || Web < 0) { + log_debug(LD_CIRC, + "Got negative bandwidth weights. Defaulting to naive selection" + " algorithm."); + Wg = Wm = We = Wd = weight_scale; + Wgb = Wmb = Web = Wdb = weight_scale; + } + + Wg /= weight_scale; + Wm /= weight_scale; + We /= weight_scale; + Wd /= weight_scale; + + Wgb /= weight_scale; + Wmb /= weight_scale; + Web /= weight_scale; + Wdb /= weight_scale; + + bandwidths = tor_calloc(smartlist_len(sl), sizeof(double)); + + // Cycle through smartlist and total the bandwidth. + static int warned_missing_bw = 0; + SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) { + int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0; + double weight = 1; + double weight_without_guard_flag = 0; /* Used for guardfraction */ + double final_weight = 0; + is_exit = node->is_exit && ! node->is_bad_exit; + is_guard = node->is_possible_guard; + is_dir = node_is_dir(node); + if (node->rs) { + if (!node->rs->has_bandwidth) { + /* This should never happen, unless all the authorities downgrade + * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */ + if (! warned_missing_bw) { + log_warn(LD_BUG, + "Consensus is missing some bandwidths. Using a naive " + "router selection algorithm"); + warned_missing_bw = 1; + } + this_bw = 30000; /* Chosen arbitrarily */ + } else { + this_bw = kb_to_bytes(node->rs->bandwidth_kb); + } + } else if (node->ri) { + /* bridge or other descriptor not in our consensus */ + this_bw = bridge_get_advertised_bandwidth_bounded(node->ri); + } else { + /* We can't use this one. */ + continue; + } + + if (is_guard && is_exit) { + weight = (is_dir ? Wdb*Wd : Wd); + weight_without_guard_flag = (is_dir ? Web*We : We); + } else if (is_guard) { + weight = (is_dir ? Wgb*Wg : Wg); + weight_without_guard_flag = (is_dir ? Wmb*Wm : Wm); + } else if (is_exit) { + weight = (is_dir ? Web*We : We); + } else { // middle + weight = (is_dir ? Wmb*Wm : Wm); + } + /* These should be impossible; but overflows here would be bad, so let's + * make sure. */ + if (this_bw < 0) + this_bw = 0; + if (weight < 0.0) + weight = 0.0; + if (weight_without_guard_flag < 0.0) + weight_without_guard_flag = 0.0; + + /* If guardfraction information is available in the consensus, we + * want to calculate this router's bandwidth according to its + * guardfraction. 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. + */ + if (node->rs && node->rs->has_guardfraction && rule != WEIGHT_FOR_GUARD) { + /* XXX The assert should actually check for is_guard. However, + * that crashes dirauths because of #13297. This should be + * equivalent: */ + tor_assert(node->rs->is_possible_guard); + + guard_get_guardfraction_bandwidth(&guardfraction_bw, + this_bw, + node->rs->guardfraction_percentage); + + /* Calculate final_weight = F*Wpf*B + (1-F)*Wpn*B */ + final_weight = + guardfraction_bw.guard_bw * weight + + guardfraction_bw.non_guard_bw * weight_without_guard_flag; + + log_debug(LD_GENERAL, "%s: Guardfraction weight %f instead of %f (%s)", + node->rs->nickname, final_weight, weight*this_bw, + bandwidth_weight_rule_to_string(rule)); + } else { /* no guardfraction information. calculate the weight normally. */ + final_weight = weight*this_bw; + } + + bandwidths[node_sl_idx] = final_weight; + total_bandwidth += final_weight; + } SMARTLIST_FOREACH_END(node); + + log_debug(LD_CIRC, "Generated weighted bandwidths for rule %s based " + "on weights " + "Wg=%f Wm=%f We=%f Wd=%f with total bw %f", + bandwidth_weight_rule_to_string(rule), + Wg, Wm, We, Wd, total_bandwidth); + + *bandwidths_out = bandwidths; + + if (total_bandwidth_out) { + *total_bandwidth_out = total_bandwidth; + } + + return 0; +} + +/** For all nodes in <b>sl</b>, return the fraction of those nodes, weighted + * by their weighted bandwidths with rule <b>rule</b>, for which we have + * descriptors. + * + * If <b>for_direct_connect</b> is true, we intend to connect to the node + * directly, as the first hop of a circuit; otherwise, we intend to connect + * to it indirectly, or use it as if we were connecting to it indirectly. */ +double +frac_nodes_with_descriptors(const smartlist_t *sl, + bandwidth_weight_rule_t rule, + int for_direct_conn) +{ + double *bandwidths = NULL; + double total, present; + + if (smartlist_len(sl) == 0) + return 0.0; + + if (compute_weighted_bandwidths(sl, rule, &bandwidths, &total) < 0 || + total <= 0.0) { + int n_with_descs = 0; + SMARTLIST_FOREACH(sl, const node_t *, node, { + if (node_has_preferred_descriptor(node, for_direct_conn)) + n_with_descs++; + }); + tor_free(bandwidths); + return ((double)n_with_descs) / smartlist_len(sl); + } + + present = 0.0; + SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) { + if (node_has_preferred_descriptor(node, for_direct_conn)) + present += bandwidths[node_sl_idx]; + } SMARTLIST_FOREACH_END(node); + + tor_free(bandwidths); + + return present / total; +} + +/** Choose a random element of status list <b>sl</b>, weighted by + * the advertised bandwidth of each node */ +const node_t * +node_sl_choose_by_bandwidth(const smartlist_t *sl, + bandwidth_weight_rule_t rule) +{ /*XXXX MOVE */ + return smartlist_choose_node_by_bandwidth_weights(sl, rule); +} + +/** Given a <b>router</b>, add every node_t in its family (including the + * node itself!) to <b>sl</b>. + * + * Note the type mismatch: This function takes a routerinfo, but adds nodes + * to the smartlist! + */ +static void +routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router) +{ + /* XXXX MOVE ? */ + node_t fake_node; + const node_t *node = node_get_by_id(router->cache_info.identity_digest); + if (node == NULL) { + memset(&fake_node, 0, sizeof(fake_node)); + fake_node.ri = (routerinfo_t *)router; + memcpy(fake_node.identity, router->cache_info.identity_digest, DIGEST_LEN); + node = &fake_node; + } + 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; + + 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); + } + } 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); + + router_add_running_nodes_to_smartlist(sl, need_uptime, need_capacity, + need_guard, need_desc, pref_addr, + direct_conn); + 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)); + + 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, + "We removed excludedset, leaving %d nodes.", + smartlist_len(sl)); + } + + // Always weight by bandwidth + choice = node_sl_choose_by_bandwidth(sl, rule); + + smartlist_free(sl); + if (!choice && (need_uptime || need_capacity || need_guard || pref_addr)) { + /* try once more -- recurse but with fewer restrictions. */ + log_info(LD_CIRC, + "We couldn't find any live%s%s%s routers; falling back " + "to list of all routers.", + need_capacity?", fast":"", + need_uptime?", stable":"", + need_guard?", guard":""); + flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD| + CRN_PREF_ADDR); + choice = router_choose_random_node( + excludedsmartlist, excludedset, flags); + } + smartlist_free(excludednodes); + if (!choice) { + log_warn(LD_CIRC, + "No available nodes when trying to choose node. Failing."); + } + return choice; +} + +/** Try to find a running directory authority. Flags are as for + * router_pick_directory_server. + */ +const routerstatus_t * +router_pick_trusteddirserver(dirinfo_type_t type, int flags) +{ + return router_pick_dirserver_generic( + router_get_trusted_dir_servers_mutable(), + type, flags); +} + +/** Try to find a running fallback directory. Flags are as for + * router_pick_directory_server. + */ +const routerstatus_t * +router_pick_fallback_dirserver(dirinfo_type_t type, int flags) +{ + return router_pick_dirserver_generic( + router_get_fallback_dir_servers_mutable(), + type, flags); +} + +/** Pick a random element from a list of dir_server_t, weighting by their + * <b>weight</b> field. */ +static const dir_server_t * +dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight) +{ + int n = smartlist_len(servers); + int i; + double *weights_dbl; + uint64_t *weights_u64; + const dir_server_t *ds; + + weights_dbl = tor_calloc(n, sizeof(double)); + weights_u64 = tor_calloc(n, sizeof(uint64_t)); + for (i = 0; i < n; ++i) { + ds = smartlist_get(servers, i); + weights_dbl[i] = ds->weight; + if (ds->is_authority) + weights_dbl[i] *= authority_weight; + } + + scale_array_elements_to_u64(weights_u64, weights_dbl, n, NULL); + i = choose_array_element_by_weight(weights_u64, n); + tor_free(weights_dbl); + tor_free(weights_u64); + return (i < 0) ? NULL : smartlist_get(servers, i); +} + +/** Choose randomly from among the dir_server_ts in sourcelist that + * are up. Flags are as for router_pick_directory_server_impl(). + */ +static const routerstatus_t * +router_pick_trusteddirserver_impl(const smartlist_t *sourcelist, + dirinfo_type_t type, int flags, + int *n_busy_out) +{ + const or_options_t *options = get_options(); + smartlist_t *direct, *tunnel; + smartlist_t *overloaded_direct, *overloaded_tunnel; + const routerinfo_t *me = router_get_my_routerinfo(); + const routerstatus_t *result = NULL; + time_t now = time(NULL); + const int requireother = ! (flags & PDS_ALLOW_SELF); + const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL); + const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH); + const int no_microdesc_fetching =(flags & PDS_NO_EXISTING_MICRODESC_FETCH); + const double auth_weight = + (sourcelist == router_get_fallback_dir_servers()) ? + options->DirAuthorityFallbackRate : 1.0; + smartlist_t *pick_from; + int n_busy = 0; + int try_excluding = 1, n_excluded = 0; + int try_ip_pref = 1; + + if (!sourcelist) + return NULL; + + retry_search: + + direct = smartlist_new(); + tunnel = smartlist_new(); + 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); + + SMARTLIST_FOREACH_BEGIN(sourcelist, const dir_server_t *, d) + { + int is_overloaded = + d->fake_status.last_dir_503_at + DIR_503_TIMEOUT > now; + if (!d->is_running) continue; + if ((type & d->type) == 0) + continue; + + SKIP_MISSING_TRUSTED_EXTRAINFO(type, d->digest); + + if (requireother && me && router_digest_is_me(d->digest)) + continue; + if (try_excluding && + routerset_contains_routerstatus(options->ExcludeNodes, + &d->fake_status, -1)) { + ++n_excluded; + continue; + } + + if (router_is_already_dir_fetching_(d->addr, + &d->ipv6_addr, + d->dir_port, + no_serverdesc_fetching, + no_microdesc_fetching)) { + ++n_busy; + continue; + } + + /* Clients use IPv6 addresses if the server has one and the client + * prefers IPv6. + * Add the router if its preferred address and port are reachable. + * If we don't get any routers, we'll try again with the non-preferred + * address for each router (if any). (To ensure correct load-balancing + * we try routers that only have one address both times.) + */ + if (!fascistfirewall || skip_or_fw || + fascist_firewall_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, + try_ip_pref))) + smartlist_add(is_overloaded ? overloaded_direct : direct, (void*)d); + } + SMARTLIST_FOREACH_END(d); + + if (smartlist_len(tunnel)) { + pick_from = tunnel; + } else if (smartlist_len(overloaded_tunnel)) { + pick_from = overloaded_tunnel; + } else if (smartlist_len(direct)) { + pick_from = direct; + } else { + pick_from = overloaded_direct; + } + + { + const dir_server_t *selection = + dirserver_choose_by_weight(pick_from, auth_weight); + + if (selection) + result = &selection->fake_status; + } + + smartlist_free(direct); + smartlist_free(tunnel); + smartlist_free(overloaded_direct); + smartlist_free(overloaded_tunnel); + + RETRY_ALTERNATE_IP_VERSION(retry_search); + + RETRY_WITHOUT_EXCLUDE(retry_search); + + router_picked_poor_directory_log(result); + + if (n_busy_out) + *n_busy_out = n_busy; + return result; +} |