13#define NODE_SELECT_PRIVATE
46 double **bandwidths_out,
47 double *total_bandwidth_out);
50 int flags,
int *n_busy_out);
91 "No reachable router entries for dirservers. "
92 "Trying them all again.");
110 if (smartlist_len(sourcelist) == 1) {
129 "No dirservers are reachable. Trying them all again.");
141#define RETRY_ALTERNATE_IP_VERSION(retry_label) \
143 if (result == NULL && try_ip_pref && options->ClientUseIPv4 \
144 && reachable_addr_use_ipv6(options) && !server_mode(options) \
159#define RETRY_WITHOUT_EXCLUDE(retry_label) \
161 if (result == NULL && try_excluding && !options->StrictNodes \
162 && n_excluded && !n_busy) { \
177#define SKIP_MISSING_TRUSTED_EXTRAINFO(type, identity) \
179 int is_trusted_extrainfo = router_digest_is_trusted_dir_type( \
180 (identity), EXTRAINFO_DIRINFO); \
181 if (((type) & EXTRAINFO_DIRINFO) && \
182 !router_supports_extrainfo((identity), is_trusted_extrainfo)) \
186#ifndef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
187#define LOG_FALSE_POSITIVES_DURING_BOOTSTRAP 0
198#if !LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
212 log_debug(
LD_DIR,
"Wanted to make an outgoing directory connection, but "
213 "we couldn't find a directory that fit our criteria. "
214 "Perhaps we will succeed next time with less strict criteria.");
221 log_info(
LD_DIR,
"Selected a directory %s with non-preferred OR and Dir "
222 "addresses for launching an outgoing connection: "
223 "IPv4 %s OR %d Dir %d IPv6 %s OR %d Dir %d",
232#undef LOG_FALSE_POSITIVES_DURING_BOOTSTRAP
240router_is_already_dir_fetching(
const tor_addr_port_t *ap,
int serverdesc,
271router_is_already_dir_fetching_(
const tor_addr_t *ipv4_addr,
281 ipv4_dir_ap.port = dir_port;
283 ipv6_dir_ap.port = dir_port;
285 return (router_is_already_dir_fetching(&ipv4_dir_ap, serverdesc, microdesc)
286 || router_is_already_dir_fetching(&ipv6_dir_ap, serverdesc, microdesc));
304 smartlist_t *overloaded_direct, *overloaded_tunnel;
305 time_t now = time(NULL);
311 int try_excluding = 1, n_excluded = 0, n_busy = 0;
326 const int skip_or_fw = router_or_conn_should_skip_reachable_address_check(
329 const int skip_dir_fw = router_dir_conn_should_skip_reachable_address_check(
332 const int must_have_or = dirclient_must_use_begindir(options);
343 if (!node->is_running || !
node_is_dir(node) || !node->is_valid)
348 SKIP_MISSING_TRUSTED_EXTRAINFO(type, node->identity);
357 if (router_is_already_dir_fetching_(&status->ipv4_addr,
359 status->ipv4_dirport,
360 no_serverdesc_fetching,
361 no_microdesc_fetching)) {
367 is_trusted = router_digest_is_trusted_dir(node->identity);
376 if (!fascistfirewall || skip_or_fw ||
380 is_overloaded ? overloaded_tunnel : tunnel, (
void*)node);
381 else if (!must_have_or && (skip_dir_fw ||
385 is_overloaded ? overloaded_direct : direct, (
void*)node);
386 } SMARTLIST_FOREACH_END(node);
388 if (smartlist_len(tunnel)) {
390 }
else if (smartlist_len(overloaded_tunnel)) {
393 }
else if (smartlist_len(trusted_tunnel)) {
399 }
else if (smartlist_len(direct)) {
401 }
else if (smartlist_len(overloaded_direct)) {
407 smartlist_free(direct);
408 smartlist_free(tunnel);
409 smartlist_free(trusted_direct);
410 smartlist_free(trusted_tunnel);
411 smartlist_free(overloaded_direct);
412 smartlist_free(overloaded_tunnel);
414 RETRY_ALTERNATE_IP_VERSION(retry_search);
416 RETRY_WITHOUT_EXCLUDE(retry_search);
419 *n_busy_out = n_busy;
421 router_picked_poor_directory_log(result ? result->rs : NULL);
423 return result ? result->rs : NULL;
436 double scale_factor = 0.0;
439 for (i = 0; i < n_entries; ++i)
440 total += entries_in[i];
443 scale_factor = ((double)INT64_MAX) / total;
447 for (i = 0; i < n_entries; ++i)
448 entries_out[i] =
tor_llround(entries_in[i] * scale_factor);
451 *total_out = (uint64_t) total;
466 for (i = 0; i < n_entries; ++i)
480 entries, n_entries, total, rand_val);
488 return (bw > (INT32_MAX/1000)) ? INT32_MAX : bw*1000;
509 double *bandwidths_dbl=NULL;
510 uint64_t *bandwidths_u64=NULL;
515 bandwidths_u64 = tor_calloc(smartlist_len(sl),
sizeof(uint64_t));
517 smartlist_len(sl), NULL);
524 return idx < 0 ? NULL : smartlist_get(sl, idx);
531#define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000
532#define BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000
544 if (result > BRIDGE_MAX_BELIEVABLE_BANDWIDTH)
545 result = BRIDGE_MAX_BELIEVABLE_BANDWIDTH;
558 static ratelim_t buggy_rs_ratelim = RATELIM_INIT(1200);
562 "Found a routerstatus %p with has_guardfraction=%u "
563 " and guardfraction_percentage=%u, but is_possible_guard=%u.%s",
576 log_warn(
LD_BUG,
"Found the routerstatus at position %d of the "
577 "NS consensus.", pos);
584 log_warn(
LD_BUG,
"Found the routerstatus at position %d of the "
585 "MD consensus.", pos);
588 if (in_ns_count == 0) {
589 log_warn(
LD_BUG,
"Could not find the routerstatus in any "
590 "latest consensus.");
606 double **bandwidths_out,
607 double *total_bandwidth_out)
609 int64_t weight_scale;
610 double Wg = -1, Wm = -1, We = -1, Wd = -1;
611 double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1;
613 double *bandwidths = NULL;
614 double total_bandwidth = 0.0;
621 rule == WEIGHT_FOR_EXIT ||
622 rule == WEIGHT_FOR_GUARD ||
623 rule == WEIGHT_FOR_MID ||
624 rule == WEIGHT_FOR_DIR);
626 *bandwidths_out = NULL;
628 if (total_bandwidth_out) {
629 *total_bandwidth_out = 0.0;
632 if (smartlist_len(sl) == 0) {
634 "Empty routerlist passed in to consensus weight node "
635 "selection for rule %s",
643 if (rule == WEIGHT_FOR_GUARD) {
653 }
else if (rule == WEIGHT_FOR_MID) {
663 }
else if (rule == WEIGHT_FOR_EXIT) {
675 }
else if (rule == WEIGHT_FOR_DIR) {
681 Wgb = Wmb = Web = Wdb = weight_scale;
682 }
else if (rule == NO_WEIGHTING) {
683 Wg = Wm = We = Wd = weight_scale;
684 Wgb = Wmb = Web = Wdb = weight_scale;
687 if (Wg < 0 || Wm < 0 || We < 0 || Wd < 0 || Wgb < 0 || Wmb < 0 || Wdb < 0
690 "Got negative bandwidth weights. Defaulting to naive selection"
692 Wg = Wm = We = Wd = weight_scale;
693 Wgb = Wmb = Web = Wdb = weight_scale;
706 bandwidths = tor_calloc(smartlist_len(sl),
sizeof(
double));
709 static int warned_missing_bw = 0;
711 int is_exit = 0, is_guard = 0,
is_dir = 0, this_bw = 0;
713 double weight_without_guard_flag = 0;
714 double final_weight = 0;
715 is_exit = node->is_exit && ! node->is_bad_exit;
716 is_guard = node->is_possible_guard;
719 if (!node->rs->has_bandwidth) {
722 if (! warned_missing_bw) {
724 "Consensus is missing some bandwidths. Using a naive "
725 "router selection algorithm");
726 warned_missing_bw = 1;
732 }
else if (node->ri) {
740 if (is_guard && is_exit) {
741 weight = (
is_dir ? Wdb*Wd : Wd);
742 weight_without_guard_flag = (
is_dir ? Web*We : We);
743 }
else if (is_guard) {
744 weight = (
is_dir ? Wgb*Wg : Wg);
745 weight_without_guard_flag = (
is_dir ? Wmb*Wm : Wm);
746 }
else if (is_exit) {
747 weight = (
is_dir ? Web*We : We);
749 weight = (
is_dir ? Wmb*Wm : Wm);
757 if (weight_without_guard_flag < 0.0)
758 weight_without_guard_flag = 0.0;
771 if (node->rs && node->rs->has_guardfraction && rule != WEIGHT_FOR_GUARD) {
774 if (! node->rs->is_possible_guard) {
778 guard_get_guardfraction_bandwidth(&guardfraction_bw,
780 node->rs->guardfraction_percentage);
784 guardfraction_bw.
guard_bw * weight +
785 guardfraction_bw.
non_guard_bw * weight_without_guard_flag;
787 log_debug(
LD_GENERAL,
"%s: Guardfraction weight %f instead of %f (%s)",
788 node->rs->nickname, final_weight, weight*this_bw,
791 final_weight = weight*this_bw;
794 bandwidths[node_sl_idx] = final_weight;
795 total_bandwidth += final_weight;
796 } SMARTLIST_FOREACH_END(node);
798 log_debug(
LD_CIRC,
"Generated weighted bandwidths for rule %s based "
800 "Wg=%f Wm=%f We=%f Wd=%f with total bw %f",
802 Wg, Wm, We, Wd, total_bandwidth);
804 *bandwidths_out = bandwidths;
806 if (total_bandwidth_out) {
807 *total_bandwidth_out = total_bandwidth;
825 double *bandwidths = NULL;
826 double total, present;
828 if (smartlist_len(sl) == 0)
833 int n_with_descs = 0;
839 return ((
double)n_with_descs) / smartlist_len(sl);
845 present += bandwidths[node_sl_idx];
846 } SMARTLIST_FOREACH_END(node);
850 return present / total;
875 memset(&fake_node, 0,
sizeof(fake_node));
893 const int nodelist_len = smartlist_len(nodelist);
904 const int idx = node->nodelist_idx;
905 if (BUG(idx < 0) || BUG(idx >= nodelist_len) ||
906 BUG(node != smartlist_get(nodelist, idx))) {
910 } SMARTLIST_FOREACH_END(node);
915 const int idx = node->nodelist_idx;
916 if (BUG(idx < 0) || BUG(idx >= nodelist_len) ||
917 BUG(node != smartlist_get(nodelist, idx))) {
923 } SMARTLIST_FOREACH_END(node);
925 bitarray_free(excluded_idx);
929 log_warn(
LD_BUG,
"Internal error prevented us from using the fast method "
930 "for subtracting nodelists. Falling back to the quadratic way.");
932 bitarray_free(excluded_idx);
941router_choose_random_node_helper(
smartlist_t *excludednodes,
942 routerset_t *excludedset,
947 const node_t *choice = NULL;
951 "We found %d running nodes.",
959 "We removed excludedset, leaving %d nodes.",
980 routerset_t *excludedset,
985 const bool need_uptime = (flags & CRN_NEED_UPTIME) != 0;
986 const bool need_capacity = (flags & CRN_NEED_CAPACITY) != 0;
987 const bool need_guard = (flags & CRN_NEED_GUARD) != 0;
988 const bool pref_addr = (flags & CRN_PREF_ADDR) != 0;
991 const node_t *choice = NULL;
995 rule = (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID);
1003 if (excludedsmartlist) {
1007 choice = router_choose_random_node_helper(excludednodes,
1012 if (!choice && (need_uptime || need_capacity || need_guard || pref_addr)) {
1015 "We couldn't find any live%s%s%s%s routers; falling back "
1016 "to list of all routers.",
1017 need_capacity?
", fast":
"",
1018 need_uptime?
", stable":
"",
1019 need_guard?
", guard":
"",
1020 pref_addr?
", preferred address":
"");
1021 flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD|
1023 choice = router_choose_random_node_helper(excludednodes,
1028 smartlist_free(excludednodes);
1031 "No available nodes when trying to choose node. Failing.");
1054 router_get_fallback_dir_servers_mutable(),
1063 int n = smartlist_len(servers);
1065 double *weights_dbl;
1066 uint64_t *weights_u64;
1069 weights_dbl = tor_calloc(n,
sizeof(
double));
1070 weights_u64 = tor_calloc(n,
sizeof(uint64_t));
1071 for (i = 0; i < n; ++i) {
1072 ds = smartlist_get(servers, i);
1073 weights_dbl[i] = ds->weight;
1075 weights_dbl[i] *= authority_weight;
1082 return (i < 0) ? NULL : smartlist_get(servers, i);
1095 smartlist_t *overloaded_direct, *overloaded_tunnel;
1098 time_t now = time(NULL);
1103 const double auth_weight =
1104 (sourcelist == router_get_fallback_dir_servers()) ?
1108 int try_excluding = 1, n_excluded = 0;
1109 int try_ip_pref = 1;
1121 const int skip_or_fw = router_or_conn_should_skip_reachable_address_check(
1124 const int skip_dir_fw = router_dir_conn_should_skip_reachable_address_check(
1127 const int must_have_or = dirclient_must_use_begindir(options);
1133 if (!d->is_running)
continue;
1134 if ((type & d->type) == 0)
1137 SKIP_MISSING_TRUSTED_EXTRAINFO(type, d->digest);
1141 if (try_excluding &&
1143 &d->fake_status, -1)) {
1148 if (router_is_already_dir_fetching_(&d->ipv4_addr,
1151 no_serverdesc_fetching,
1152 no_microdesc_fetching)) {
1164 if (!fascistfirewall || skip_or_fw ||
1167 smartlist_add(is_overloaded ? overloaded_tunnel : tunnel, (
void*)d);
1168 else if (!must_have_or && (skip_dir_fw ||
1171 smartlist_add(is_overloaded ? overloaded_direct : direct, (
void*)d);
1173 SMARTLIST_FOREACH_END(d);
1175 if (smartlist_len(tunnel)) {
1177 }
else if (smartlist_len(overloaded_tunnel)) {
1178 pick_from = overloaded_tunnel;
1179 }
else if (smartlist_len(direct)) {
1182 pick_from = overloaded_direct;
1193 smartlist_free(direct);
1194 smartlist_free(tunnel);
1195 smartlist_free(overloaded_direct);
1196 smartlist_free(overloaded_tunnel);
1198 RETRY_ALTERNATE_IP_VERSION(retry_search);
1200 RETRY_WITHOUT_EXCLUDE(retry_search);
1202 router_picked_poor_directory_log(result);
1205 *n_busy_out = n_busy;
void tor_addr_copy(tor_addr_t *dest, const tor_addr_t *src)
int tor_addr_is_null(const tor_addr_t *addr)
char * tor_addr_to_str_dup(const tor_addr_t *addr)
Implements a variable-sized (but non-resizeable) bit-array.
static bitarray_t * bitarray_init_zero(unsigned int n_bits)
static void bitarray_set(bitarray_t *b, int bit)
static unsigned int bitarray_is_set(bitarray_t *b, int bit)
const or_options_t * get_options(void)
Header file for config.c.
connection_t * connection_get_by_type_addr_port_purpose(int type, const tor_addr_t *addr, uint16_t port, int purpose)
Header file for connection.c.
void * smartlist_choose(const smartlist_t *sl)
Common functions for using (pseudo-)random number generators.
uint64_t crypto_rand_uint64(uint64_t max)
int crypto_rand_int(unsigned int max)
const char * routerstatus_describe(const routerstatus_t *rs)
Header file for describe.c.
int select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, uint64_t total, uint64_t rand_val)
Trusted/fallback directory server structure.
Header file for dirclient.c.
Header for feature/dirclient/dirclient_modes.c.
Header file for directory.c.
#define DIR_PURPOSE_FETCH_EXTRAINFO
#define DIR_PURPOSE_FETCH_MICRODESC
#define DIR_PURPOSE_FETCH_SERVERDESC
void mark_all_dirservers_up(smartlist_t *server_list)
void router_reset_status_download_failures(void)
smartlist_t * router_get_trusted_dir_servers_mutable(void)
Header file for dirlist.c.
Header file for circuitbuild.c.
bool is_dir(file_status_t file_type)
int64_t tor_llround(double d)
int usable_consensus_flavor(void)
Header file for microdesc.c.
networkstatus_t * networkstatus_get_latest_consensus_by_flavor(consensus_flavor_t f)
networkstatus_t * networkstatus_get_reasonably_live_consensus(time_t now, int flavor)
networkstatus_t * networkstatus_get_latest_consensus(void)
int32_t networkstatus_get_bw_weight(networkstatus_t *ns, const char *weight_name, int32_t default_val)
int networkstatus_get_weight_scale_param(networkstatus_t *ns)
Header file for networkstatus.c.
Networkstatus consensus/vote structure.
STATIC const routerstatus_t * router_pick_directory_server_impl(dirinfo_type_t type, int flags, int *n_busy_out)
static void nodelist_subtract(smartlist_t *sl, const smartlist_t *excluded)
static uint32_t bridge_get_advertised_bandwidth_bounded(routerinfo_t *router)
const routerstatus_t * router_pick_directory_server(dirinfo_type_t type, int flags)
static const dir_server_t * dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight)
const routerstatus_t * router_pick_fallback_dirserver(dirinfo_type_t type, int flags)
static int compute_weighted_bandwidths(const smartlist_t *sl, bandwidth_weight_rule_t rule, double **bandwidths_out, double *total_bandwidth_out)
const routerstatus_t * router_pick_trusteddirserver(dirinfo_type_t type, int flags)
static int32_t kb_to_bytes(uint32_t bw)
const node_t * router_choose_random_node(smartlist_t *excludedsmartlist, routerset_t *excludedset, router_crn_flags_t flags)
double frac_nodes_with_descriptors(const smartlist_t *sl, bandwidth_weight_rule_t rule, int for_direct_conn)
static const routerstatus_t * router_pick_dirserver_generic(smartlist_t *sourcelist, dirinfo_type_t type, int flags)
static const node_t * smartlist_choose_node_by_bandwidth_weights(const smartlist_t *sl, bandwidth_weight_rule_t rule)
STATIC int choose_array_element_by_weight(const uint64_t *entries, int n_entries)
static const routerstatus_t * router_pick_trusteddirserver_impl(const smartlist_t *sourcelist, dirinfo_type_t auth, int flags, int *n_busy_out)
STATIC void scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in, int n_entries, uint64_t *total_out)
#define BRIDGE_MIN_BELIEVABLE_BANDWIDTH
const node_t * node_sl_choose_by_bandwidth(const smartlist_t *sl, bandwidth_weight_rule_t rule)
static void log_buggy_rs_source(const routerstatus_t *rs)
static void routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router)
Header file for node_select.c.
#define PDS_NO_EXISTING_SERVERDESC_FETCH
#define PDS_NO_EXISTING_MICRODESC_FETCH
#define PDS_IGNORE_FASCISTFIREWALL
#define PDS_RETRY_IF_NO_SERVERS
Node information structure.
const node_t * node_get_by_id(const char *identity_digest)
void nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
const smartlist_t * nodelist_get_list(void)
int node_has_preferred_descriptor(const node_t *node, int for_direct_connect)
int node_is_dir(const node_t *node)
int router_have_minimum_dir_info(void)
Header file for nodelist.c.
Master header file for Tor-specific functionality.
int reachable_addr_allows_rs(const routerstatus_t *rs, firewall_connection_t fw_connection, int pref_only)
int reachable_addr_allows_node(const node_t *node, firewall_connection_t fw_connection, int pref_only)
int reachable_addr_allows_dir_server(const dir_server_t *ds, firewall_connection_t fw_connection, int pref_only)
Header file for policies.c.
char * rate_limit_log(ratelim_t *lim, time_t now)
const char * bandwidth_weight_rule_to_string(bandwidth_weight_rule_t rule)
Header file for reasons.c.
int router_digest_is_me(const char *digest)
const routerinfo_t * router_get_my_routerinfo(void)
Header file for router.c.
Router descriptor structure.
void router_add_running_nodes_to_smartlist(smartlist_t *sl, int flags)
Header file for routerlist.c.
Header file for routermode.c.
int routerset_contains_routerstatus(const routerset_t *set, const routerstatus_t *rs, country_t country)
void routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
Header file for routerset.c.
Routerstatus (consensus entry) structure.
int smartlist_pos(const smartlist_t *sl, const void *element)
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
void smartlist_add_all(smartlist_t *s1, const smartlist_t *s2)
smartlist_t * smartlist_new(void)
void smartlist_add(smartlist_t *sl, void *element)
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
#define SMARTLIST_FOREACH(sl, type, var, cmd)
#define SMARTLIST_DEL_CURRENT(sl, var)
routerstatus_t fake_status
unsigned int is_authority
smartlist_t * routerstatus_list
char identity[DIGEST_LEN]
struct routerset_t * ExcludeNodes
double DirAuthorityFallbackRate
uint32_t bandwidthcapacity
unsigned int has_guardfraction
unsigned int is_possible_guard
uint32_t guardfraction_percentage
char identity_digest[DIGEST_LEN]
#define tor_assert_nonfatal_unreached()