diff options
Diffstat (limited to 'src/or/routerlist.c')
| -rw-r--r-- | src/or/routerlist.c | 1020 |
1 files changed, 695 insertions, 325 deletions
diff --git a/src/or/routerlist.c b/src/or/routerlist.c index be7ba0e96..f8df089a8 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -12,6 +12,25 @@ **/ #include "or.h" +#include "circuitbuild.h" +#include "config.h" +#include "connection.h" +#include "control.h" +#include "directory.h" +#include "dirserv.h" +#include "dirvote.h" +#include "geoip.h" +#include "hibernate.h" +#include "main.h" +#include "networkstatus.h" +#include "policies.h" +#include "reasons.h" +#include "rendcommon.h" +#include "rendservice.h" +#include "rephist.h" +#include "router.h" +#include "routerlist.h" +#include "routerparse.h" // #define DEBUG_ROUTERLIST @@ -26,8 +45,8 @@ static void mark_all_trusteddirservers_up(void); static int router_nickname_matches(routerinfo_t *router, const char *nickname); static void trusted_dir_server_free(trusted_dir_server_t *ds); static void launch_router_descriptor_downloads(smartlist_t *downloadable, + routerstatus_t *source, time_t now); -static void update_consensus_router_descriptor_downloads(time_t now); static int signed_desc_digest_is_recognized(signed_descriptor_t *desc); static void update_router_have_minimum_dir_info(void); static const char *signed_descriptor_get_body_impl(signed_descriptor_t *desc, @@ -156,21 +175,24 @@ already_have_cert(authority_cert_t *cert) /** Load a bunch of new key certificates from the string <b>contents</b>. If * <b>from_store</b> is true, the certificates are from the cache, and we - * don't need to flush them to disk. If <b>from_store</b> is false, we need - * to flush any changed certificates to disk. Return 0 on success, -1 on - * failure. */ + * don't need to flush them to disk. If <b>flush</b> is true, we need + * to flush any changed certificates to disk now. Return 0 on success, -1 + * if any certs fail to parse. */ int trusted_dirs_load_certs_from_string(const char *contents, int from_store, int flush) { trusted_dir_server_t *ds; const char *s, *eos; + int failure_code = 0; for (s = contents; *s; s = eos) { authority_cert_t *cert = authority_cert_parse_from_string(s, &eos); cert_list_t *cl; - if (!cert) + if (!cert) { + failure_code = -1; break; + } ds = trusteddirserver_get_by_v3_auth_digest( cert->cache_info.identity_digest); log_debug(LD_DIR, "Parsed certificate for %s", @@ -181,15 +203,15 @@ trusted_dirs_load_certs_from_string(const char *contents, int from_store, log_info(LD_DIR, "Skipping %s certificate for %s that we " "already have.", from_store ? "cached" : "downloaded", - ds ? ds->nickname : "??"); + ds ? ds->nickname : "an old or new authority"); /* a duplicate on a download should be treated as a failure, since it * probably means we wanted a different secret key or we are trying to * replace an expired cert that has not in fact been updated. */ if (!from_store) { - log_warn(LD_DIR, "Got a certificate for %s that we already have. " - "Maybe they haven't updated it. Waiting for a while.", - ds ? ds->nickname : "??"); + log_warn(LD_DIR, "Got a certificate for %s, but we already have it. " + "Maybe they haven't updated it. Waiting for a while.", + ds ? ds->nickname : "an old or new authority"); authority_cert_dl_failed(cert->cache_info.identity_digest, 404); } @@ -224,7 +246,7 @@ trusted_dirs_load_certs_from_string(const char *contents, int from_store, ds->dir_port != cert->dir_port)) { char *a = tor_dup_ip(cert->addr); log_notice(LD_DIR, "Updating address for directory authority %s " - "from %s:%d to %s:%d based on in certificate.", + "from %s:%d to %s:%d based on certificate.", ds->nickname, ds->address, (int)ds->dir_port, a, cert->dir_port); tor_free(a); @@ -241,8 +263,11 @@ trusted_dirs_load_certs_from_string(const char *contents, int from_store, if (flush) trusted_dirs_flush_certs_to_disk(); + /* call this even if failure_code is <0, since some certs might have + * succeeded. */ networkstatus_note_certs_arrived(); - return 0; + + return failure_code; } /** Save all v3 key certificates to the cached-certs file. */ @@ -303,7 +328,7 @@ trusted_dirs_remove_old_certs(void) time_t cert_published; if (newest == cert) continue; - expired = ftime_definitely_after(now, cert->expires); + expired = now > cert->expires; cert_published = cert->cache_info.published_on; /* Store expired certs for 48 hours after a newer arrives; */ @@ -415,6 +440,23 @@ authority_cert_dl_failed(const char *id_digest, int status) download_status_failed(&cl->dl_status, status); } +/** Return true iff when we've been getting enough failures when trying to + * download the certificate with ID digest <b>id_digest</b> that we're willing + * to start bugging the user about it. */ +int +authority_cert_dl_looks_uncertain(const char *id_digest) +{ +#define N_AUTH_CERT_DL_FAILURES_TO_BUG_USER 2 + cert_list_t *cl; + int n_failures; + if (!trusted_dir_certs || + !(cl = digestmap_get(trusted_dir_certs, id_digest))) + return 0; + + n_failures = download_status_get_n_failures(&cl->dl_status); + return n_failures >= N_AUTH_CERT_DL_FAILURES_TO_BUG_USER; +} + /** How many times will we try to fetch a certificate before giving up? */ #define MAX_CERT_DL_FAILURES 8 @@ -442,17 +484,18 @@ authority_certs_fetch_missing(networkstatus_t *status, time_t now) list_pending_downloads(pending, DIR_PURPOSE_FETCH_CERTIFICATE, "fp/"); if (status) { - SMARTLIST_FOREACH(status->voters, networkstatus_voter_info_t *, voter, - { - if (tor_digest_is_zero(voter->signing_key_digest)) - continue; /* This authority never signed this consensus, so don't - * go looking for a cert with key digest 0000000000. */ - if (!cache && - !trusteddirserver_get_by_v3_auth_digest(voter->identity_digest)) - continue; /* We are not a cache, and we don't know this authority.*/ - cl = get_cert_list(voter->identity_digest); + SMARTLIST_FOREACH_BEGIN(status->voters, networkstatus_voter_info_t *, + voter) { + if (!smartlist_len(voter->sigs)) + continue; /* This authority never signed this consensus, so don't + * go looking for a cert with key digest 0000000000. */ + if (!cache && + !trusteddirserver_get_by_v3_auth_digest(voter->identity_digest)) + continue; /* We are not a cache, and we don't know this authority.*/ + cl = get_cert_list(voter->identity_digest); + SMARTLIST_FOREACH_BEGIN(voter->sigs, document_signature_t *, sig) { cert = authority_cert_get_by_digests(voter->identity_digest, - voter->signing_key_digest); + sig->signing_key_digest); if (cert) { if (now < cert->expires) download_status_reset(&cl->dl_status); @@ -463,37 +506,36 @@ authority_certs_fetch_missing(networkstatus_t *status, time_t now) !digestmap_get(pending, voter->identity_digest)) { log_notice(LD_DIR, "We're missing a certificate from authority " "with signing key %s: launching request.", - hex_str(voter->signing_key_digest, DIGEST_LEN)); - smartlist_add(missing_digests, voter->identity_digest); + hex_str(sig->signing_key_digest, DIGEST_LEN)); + smartlist_add(missing_digests, sig->identity_digest); } - }); + } SMARTLIST_FOREACH_END(sig); + } SMARTLIST_FOREACH_END(voter); } - SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds, - { - int found = 0; - if (!(ds->type & V3_AUTHORITY)) - continue; - if (smartlist_digest_isin(missing_digests, ds->v3_identity_digest)) - continue; - cl = get_cert_list(ds->v3_identity_digest); - SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, - { - if (!ftime_definitely_after(now, cert->expires)) { - /* It's not expired, and we weren't looking for something to - * verify a consensus with. Call it done. */ - download_status_reset(&cl->dl_status); - found = 1; - break; - } - }); - if (!found && - download_status_is_ready(&cl->dl_status, now,MAX_CERT_DL_FAILURES) && - !digestmap_get(pending, ds->v3_identity_digest)) { - log_notice(LD_DIR, "No current certificate known for authority %s; " - "launching request.", ds->nickname); - smartlist_add(missing_digests, ds->v3_identity_digest); + SMARTLIST_FOREACH_BEGIN(trusted_dir_servers, trusted_dir_server_t *, ds) { + int found = 0; + if (!(ds->type & V3_AUTHORITY)) + continue; + if (smartlist_digest_isin(missing_digests, ds->v3_identity_digest)) + continue; + cl = get_cert_list(ds->v3_identity_digest); + SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, { + if (now < cert->expires) { + /* It's not expired, and we weren't looking for something to + * verify a consensus with. Call it done. */ + download_status_reset(&cl->dl_status); + found = 1; + break; } }); + if (!found && + download_status_is_ready(&cl->dl_status, now,MAX_CERT_DL_FAILURES) && + !digestmap_get(pending, ds->v3_identity_digest)) { + log_info(LD_DIR, "No current certificate known for authority %s; " + "launching request.", ds->nickname); + smartlist_add(missing_digests, ds->v3_identity_digest); + } + } SMARTLIST_FOREACH_END(ds); if (!smartlist_len(missing_digests)) { goto done; @@ -749,8 +791,7 @@ router_rebuild_store(int flags, desc_store_t *store) store->journal_len = 0; store->bytes_dropped = 0; done: - if (signed_descriptors) - smartlist_free(signed_descriptors); + smartlist_free(signed_descriptors); tor_free(fname); tor_free(fname_tmp); if (chunk_list) { @@ -968,8 +1009,9 @@ router_get_trusteddirserver_by_digest(const char *digest) return NULL; } -/** Return the trusted_dir_server_t for the directory authority whose identity - * key hashes to <b>digest</b>, or NULL if no such authority is known. +/** Return the trusted_dir_server_t for the directory authority whose + * v3 identity key hashes to <b>digest</b>, or NULL if no such authority + * is known. */ trusted_dir_server_t * trusteddirserver_get_by_v3_auth_digest(const char *digest) @@ -1028,6 +1070,7 @@ router_pick_trusteddirserver(authority_type_t type, int flags) static routerstatus_t * router_pick_directory_server_impl(authority_type_t type, int flags) { + or_options_t *options = get_options(); routerstatus_t *result; smartlist_t *direct, *tunnel; smartlist_t *trusted_direct, *trusted_tunnel; @@ -1037,10 +1080,13 @@ router_pick_directory_server_impl(authority_type_t type, int flags) int requireother = ! (flags & PDS_ALLOW_SELF); int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL); int prefer_tunnel = (flags & _PDS_PREFER_TUNNELED_DIR_CONNS); + int try_excluding = 1, n_excluded = 0; if (!consensus) return NULL; + retry_without_exclude: + direct = smartlist_create(); tunnel = smartlist_create(); trusted_direct = smartlist_create(); @@ -1072,6 +1118,11 @@ router_pick_directory_server_impl(authority_type_t type, int flags) if ((type & EXTRAINFO_CACHE) && !router_supports_extrainfo(status->identity_digest, 0)) continue; + if (try_excluding && options->ExcludeNodes && + routerset_contains_routerstatus(options->ExcludeNodes, status)) { + ++n_excluded; + continue; + } /* XXXX IP6 proposal 118 */ tor_addr_from_ipv4h(&addr, status->addr); @@ -1089,9 +1140,10 @@ router_pick_directory_server_impl(authority_type_t type, int flags) } SMARTLIST_FOREACH_END(status); if (smartlist_len(tunnel)) { - result = routerstatus_sl_choose_by_bandwidth(tunnel); + result = routerstatus_sl_choose_by_bandwidth(tunnel, WEIGHT_FOR_DIR); } else if (smartlist_len(overloaded_tunnel)) { - result = routerstatus_sl_choose_by_bandwidth(overloaded_tunnel); + result = routerstatus_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. */ @@ -1099,9 +1151,10 @@ router_pick_directory_server_impl(authority_type_t type, int flags) * is a feature, but it could easily be a bug. -RD */ result = smartlist_choose(trusted_tunnel); } else if (smartlist_len(direct)) { - result = routerstatus_sl_choose_by_bandwidth(direct); + result = routerstatus_sl_choose_by_bandwidth(direct, WEIGHT_FOR_DIR); } else if (smartlist_len(overloaded_direct)) { - result = routerstatus_sl_choose_by_bandwidth(overloaded_direct); + result = routerstatus_sl_choose_by_bandwidth(overloaded_direct, + WEIGHT_FOR_DIR); } else { result = smartlist_choose(trusted_direct); } @@ -1111,6 +1164,15 @@ router_pick_directory_server_impl(authority_type_t type, int flags) smartlist_free(trusted_tunnel); smartlist_free(overloaded_direct); smartlist_free(overloaded_tunnel); + + if (result == NULL && try_excluding && !options->StrictNodes && n_excluded) { + /* If we got no result, and we are excluding nodes, and StrictNodes is + * not set, try again without excluding nodes. */ + try_excluding = 0; + n_excluded = 0; + goto retry_without_exclude; + } + return result; } @@ -1121,6 +1183,7 @@ static routerstatus_t * router_pick_trusteddirserver_impl(authority_type_t type, int flags, int *n_busy_out) { + or_options_t *options = get_options(); smartlist_t *direct, *tunnel; smartlist_t *overloaded_direct, *overloaded_tunnel; routerinfo_t *me = router_get_my_routerinfo(); @@ -1131,10 +1194,13 @@ router_pick_trusteddirserver_impl(authority_type_t type, int flags, const int prefer_tunnel = (flags & _PDS_PREFER_TUNNELED_DIR_CONNS); const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH); int n_busy = 0; + int try_excluding = 1, n_excluded = 0; if (!trusted_dir_servers) return NULL; + retry_without_exclude: + direct = smartlist_create(); tunnel = smartlist_create(); overloaded_direct = smartlist_create(); @@ -1153,6 +1219,12 @@ router_pick_trusteddirserver_impl(authority_type_t type, int flags, continue; if (requireother && me && router_digest_is_me(d->digest)) continue; + if (try_excluding && options->ExcludeNodes && + routerset_contains_routerstatus(options->ExcludeNodes, + &d->fake_status)) { + ++n_excluded; + continue; + } /* XXXX IP6 proposal 118 */ tor_addr_from_ipv4h(&addr, d->addr); @@ -1199,6 +1271,15 @@ router_pick_trusteddirserver_impl(authority_type_t type, int flags, smartlist_free(tunnel); smartlist_free(overloaded_direct); smartlist_free(overloaded_tunnel); + + if (result == NULL && try_excluding && !options->StrictNodes && n_excluded) { + /* If we got no result, and we are excluding nodes, and StrictNodes is + * not set, try again without excluding nodes. */ + try_excluding = 0; + n_excluded = 0; + goto retry_without_exclude; + } + return result; } @@ -1230,6 +1311,13 @@ mark_all_trusteddirservers_up(void) router_dir_info_changed(); } +/** Return true iff r1 and r2 have the same address and OR port. */ +int +routers_have_same_or_addr(const routerinfo_t *r1, const routerinfo_t *r2) +{ + return r1->addr == r2->addr && r1->or_port == r2->or_port; +} + /** Reset all internal variables used to count failed downloads of network * status objects. */ void @@ -1450,6 +1538,8 @@ routerlist_find_my_routerinfo(void) /** Find a router that's up, that has this IP address, and * that allows exit to this address:port, or return NULL if there * isn't a good one. + * Don't exit enclave to excluded relays -- it wouldn't actually + * hurt anything, but this way there are fewer confused users. */ routerinfo_t * router_find_exact_exit_enclave(const char *address, uint16_t port) @@ -1457,6 +1547,7 @@ router_find_exact_exit_enclave(const char *address, uint16_t port) uint32_t addr; struct in_addr in; tor_addr_t a; + or_options_t *options = get_options(); if (!tor_inet_aton(address, &in)) return NULL; /* it's not an IP already */ @@ -1469,7 +1560,8 @@ router_find_exact_exit_enclave(const char *address, uint16_t port) if (router->addr == addr && router->is_running && compare_tor_addr_to_addr_policy(&a, port, router->exit_policy) == - ADDR_POLICY_ACCEPTED) + ADDR_POLICY_ACCEPTED && + !routerset_contains_router(options->_ExcludeExitNodesUnion, router)) return router; }); return NULL; @@ -1521,6 +1613,29 @@ router_get_advertised_bandwidth_capped(routerinfo_t *router) return result; } +/** 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; +} + /** Return bw*1000, unless bw*1000 would overflow, in which case return * INT32_MAX. */ static INLINE int32_t @@ -1531,6 +1646,218 @@ kb_to_bytes(uint32_t bw) /** Helper function: * choose a random element of smartlist <b>sl</b>, weighted by + * the advertised bandwidth of each element using the consensus + * bandwidth weights. + * + * If <b>statuses</b> is zero, then <b>sl</b> is a list of + * routerinfo_t's. Otherwise it's a list of routerstatus_t's. + * + * 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 void * +smartlist_choose_by_bandwidth_weights(smartlist_t *sl, + bandwidth_weight_rule_t rule, + int statuses) +{ + int64_t weight_scale; + int64_t rand_bw; + double Wg = -1, Wm = -1, We = -1, Wd = -1; + double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1; + double weighted_bw = 0; + double *bandwidths; + double tmp = 0; + unsigned int i; + int have_unknown = 0; /* true iff sl contains element not in consensus. */ + + /* 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); + + 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 NULL; + } + + weight_scale = circuit_build_times_get_bw_scale(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 old selection" + " algorithm."); + return NULL; // Use old algorithm. + } + + 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_malloc_zero(sizeof(double)*smartlist_len(sl)); + + // Cycle through smartlist and total the bandwidth. + for (i = 0; i < (unsigned)smartlist_len(sl); ++i) { + int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0, is_me = 0; + double weight = 1; + if (statuses) { + routerstatus_t *status = smartlist_get(sl, i); + is_exit = status->is_exit && !status->is_bad_exit; + is_guard = status->is_possible_guard; + is_dir = (status->dir_port != 0); + if (!status->has_bandwidth) { + tor_free(bandwidths); + /* This should never happen, unless all the authorites downgrade + * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */ + log_warn(LD_BUG, + "Consensus is not listing bandwidths. Defaulting back to " + "old router selection algorithm."); + return NULL; + } + this_bw = kb_to_bytes(status->bandwidth); + if (router_digest_is_me(status->identity_digest)) + is_me = 1; + } else { + routerstatus_t *rs; + routerinfo_t *router = smartlist_get(sl, i); + rs = router_get_consensus_status_by_id( + router->cache_info.identity_digest); + is_exit = router->is_exit && !router->is_bad_exit; + is_guard = router->is_possible_guard; + is_dir = (router->dir_port != 0); + if (rs && rs->has_bandwidth) { + this_bw = kb_to_bytes(rs->bandwidth); + } else { /* bridge or other descriptor not in our consensus */ + this_bw = bridge_get_advertised_bandwidth_bounded(router); + have_unknown = 1; + } + if (router_digest_is_me(router->cache_info.identity_digest)) + is_me = 1; + } + if (is_guard && is_exit) { + weight = (is_dir ? Wdb*Wd : Wd); + } else if (is_guard) { + weight = (is_dir ? Wgb*Wg : Wg); + } else if (is_exit) { + weight = (is_dir ? Web*We : We); + } else { // middle + weight = (is_dir ? Wmb*Wm : Wm); + } + + bandwidths[i] = weight*this_bw; + weighted_bw += weight*this_bw; + if (is_me) + sl_last_weighted_bw_of_me = weight*this_bw; + } + + /* XXXX023 this is a kludge to expose these values. */ + sl_last_total_weighted_bw = weighted_bw; + + log_debug(LD_CIRC, "Choosing node 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, weighted_bw); + + /* If there is no bandwidth, choose at random */ + if (DBL_TO_U64(weighted_bw) == 0) { + /* Don't warn when using bridges/relays not in the consensus */ + if (!have_unknown) + log_warn(LD_CIRC, + "Weighted bandwidth is %f in node selection for rule %s", + weighted_bw, bandwidth_weight_rule_to_string(rule)); + tor_free(bandwidths); + return smartlist_choose(sl); + } + + rand_bw = crypto_rand_uint64(DBL_TO_U64(weighted_bw)); + rand_bw++; /* crypto_rand_uint64() counts from 0, and we need to count + * from 1 below. See bug 1203 for details. */ + + /* Last, count through sl until we get to the element we picked */ + tmp = 0.0; + for (i=0; i < (unsigned)smartlist_len(sl); i++) { + tmp += bandwidths[i]; + if (tmp >= rand_bw) + break; + } + + if (i == (unsigned)smartlist_len(sl)) { + /* This was once possible due to round-off error, but shouldn't be able + * to occur any longer. */ + tor_fragile_assert(); + --i; + log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on " + " which router we chose. Please tell the developers. " + "%f " U64_FORMAT " %f", tmp, U64_PRINTF_ARG(rand_bw), + weighted_bw); + } + tor_free(bandwidths); + return smartlist_get(sl, i); +} + +/** Helper function: + * choose a random element of smartlist <b>sl</b>, weighted by * the advertised bandwidth of each element. * * If <b>statuses</b> is zero, then <b>sl</b> is a list of @@ -1565,11 +1892,24 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule, bitarray_t *guard_bits; int me_idx = -1; + // This function does not support WEIGHT_FOR_DIR + // or WEIGHT_FOR_MID + if (rule == WEIGHT_FOR_DIR || rule == WEIGHT_FOR_MID) { + rule = NO_WEIGHTING; + } + /* Can't choose exit and guard at same time */ tor_assert(rule == NO_WEIGHTING || rule == WEIGHT_FOR_EXIT || rule == WEIGHT_FOR_GUARD); + if (smartlist_len(sl) == 0) { + log_info(LD_CIRC, + "Empty routerlist passed in to old node selection for rule %s", + bandwidth_weight_rule_to_string(rule)); + return NULL; + } + /* First count the total bandwidth weight, and make a list * of each value. <0 means "unknown; no routerinfo." We use the * bits of negative values to remember whether the router was fast (-x)&1 @@ -1594,7 +1934,7 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule, if (status->has_bandwidth) { this_bw = kb_to_bytes(status->bandwidth); } else { /* guess */ - /* XXX022 once consensuses always list bandwidths, we can take + /* XXX023 once consensuses always list bandwidths, we can take * this guessing business out. -RD */ is_known = 0; flags = status->is_fast ? 1 : 0; @@ -1613,14 +1953,14 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule, if (rs && rs->has_bandwidth) { this_bw = kb_to_bytes(rs->bandwidth); } else if (rs) { /* guess; don't trust the descriptor */ - /* XXX022 once consensuses always list bandwidths, we can take + /* XXX023 once consensuses always list bandwidths, we can take * this guessing business out. -RD */ is_known = 0; flags = router->is_fast ? 1 : 0; flags |= is_exit ? 2 : 0; flags |= is_guard ? 4 : 0; } else /* bridge or other descriptor not in our consensus */ - this_bw = router_get_advertised_bandwidth_capped(router); + this_bw = bridge_get_advertised_bandwidth_bounded(router); } if (is_exit) bitarray_set(exit_bits, i); @@ -1628,6 +1968,8 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule, bitarray_set(guard_bits, i); if (is_known) { bandwidths[i] = (int32_t) this_bw; // safe since MAX_BELIEVABLE<INT32_MAX + // XXX this is no longer true! We don't always cap the bw anymore. Can + // a consensus make us overflow?-sh tor_assert(bandwidths[i] >= 0); if (is_guard) total_guard_bw += this_bw; @@ -1691,12 +2033,12 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule, * For detailed derivation of this formula, see * http://archives.seul.org/or/dev/Jul-2007/msg00056.html */ - if (rule == WEIGHT_FOR_EXIT) + if (rule == WEIGHT_FOR_EXIT || !total_exit_bw) exit_weight = 1.0; else exit_weight = 1.0 - all_bw/(3.0*exit_bw); - if (rule == WEIGHT_FOR_GUARD) + if (rule == WEIGHT_FOR_GUARD || !total_guard_bw) guard_weight = 1.0; else guard_weight = 1.0 - all_bw/(3.0*guard_bw); @@ -1727,15 +2069,15 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule, } } - /* XXXX022 this is a kludge to expose these values. */ + /* XXXX023 this is a kludge to expose these values. */ sl_last_total_weighted_bw = total_bw; log_debug(LD_CIRC, "Total weighted bw = "U64_FORMAT ", exit bw = "U64_FORMAT - ", nonexit bw = "U64_FORMAT", exit weight = %lf " + ", nonexit bw = "U64_FORMAT", exit weight = %f " "(for exit == %d)" ", guard bw = "U64_FORMAT - ", nonguard bw = "U64_FORMAT", guard weight = %lf " + ", nonguard bw = "U64_FORMAT", guard weight = %f " "(for guard == %d)", U64_PRINTF_ARG(total_bw), U64_PRINTF_ARG(total_exit_bw), U64_PRINTF_ARG(total_nonexit_bw), @@ -1745,6 +2087,8 @@ smartlist_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule, /* Almost done: choose a random value from the bandwidth weights. */ rand_bw = crypto_rand_uint64(total_bw); + rand_bw++; /* crypto_rand_uint64() counts from 0, and we need to count + * from 1 below. See bug 1203 for details. */ /* Last, count through sl until we get to the element we picked */ tmp = 0; @@ -1788,26 +2132,34 @@ routerinfo_t * routerlist_sl_choose_by_bandwidth(smartlist_t *sl, bandwidth_weight_rule_t rule) { - return smartlist_choose_by_bandwidth(sl, rule, 0); + routerinfo_t *ret; + if ((ret = smartlist_choose_by_bandwidth_weights(sl, rule, 0))) { + return ret; + } else { + return smartlist_choose_by_bandwidth(sl, rule, 0); + } } /** Choose a random element of status list <b>sl</b>, weighted by * the advertised bandwidth of each status. */ routerstatus_t * -routerstatus_sl_choose_by_bandwidth(smartlist_t *sl) +routerstatus_sl_choose_by_bandwidth(smartlist_t *sl, + bandwidth_weight_rule_t rule) { /* We are choosing neither exit nor guard here. Weight accordingly. */ - return smartlist_choose_by_bandwidth(sl, NO_WEIGHTING, 1); + routerstatus_t *ret; + if ((ret = smartlist_choose_by_bandwidth_weights(sl, rule, 1))) { + return ret; + } else { + return smartlist_choose_by_bandwidth(sl, rule, 1); + } } -/** Return a random running router from the routerlist. If any node - * named in <b>preferred</b> is available, pick one of those. Never +/** Return a random running router from the routerlist. Never * pick a node whose routerinfo is in * <b>excludedsmartlist</b>, or whose routerinfo matches <b>excludedset</b>, - * even if they are the only nodes - * available. If <b>CRN_STRICT_PREFERRED</b> is set in flags, never pick - * any node besides those in <b>preferred</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 @@ -1820,8 +2172,7 @@ routerstatus_sl_choose_by_bandwidth(smartlist_t *sl) * node (that is, possibly discounting exit nodes). */ routerinfo_t * -router_choose_random_node(const char *preferred, - smartlist_t *excludedsmartlist, +router_choose_random_node(smartlist_t *excludedsmartlist, routerset_t *excludedset, router_crn_flags_t flags) { @@ -1829,18 +2180,16 @@ router_choose_random_node(const char *preferred, const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0; const int need_guard = (flags & CRN_NEED_GUARD) != 0; const int allow_invalid = (flags & CRN_ALLOW_INVALID) != 0; - const int strict = (flags & CRN_STRICT_PREFERRED) != 0; const int weight_for_exit = (flags & CRN_WEIGHT_AS_EXIT) != 0; - smartlist_t *sl, *excludednodes; + smartlist_t *sl=smartlist_create(), + *excludednodes=smartlist_create(); routerinfo_t *choice = NULL, *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 : NO_WEIGHTING); - - excludednodes = smartlist_create(); + (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID); /* Exclude relays that allow single hop exit circuits, if the user * wants to (such relays might be risky) */ @@ -1857,60 +2206,35 @@ router_choose_random_node(const char *preferred, routerlist_add_family(excludednodes, r); } - /* Try the preferred nodes first. Ignore need_uptime and need_capacity - * and need_guard, since the user explicitly asked for these nodes. */ - if (preferred) { - sl = smartlist_create(); - add_nickname_list_to_smartlist(sl,preferred,1); - smartlist_subtract(sl,excludednodes); - if (excludedsmartlist) - smartlist_subtract(sl,excludedsmartlist); - if (excludedset) - routerset_subtract_routers(sl,excludedset); - choice = smartlist_choose(sl); - smartlist_free(sl); - } - if (!choice && !strict) { - /* Then give up on our preferred choices: any node - * will do that has the required attributes. */ - sl = smartlist_create(); - router_add_running_routers_to_smartlist(sl, allow_invalid, - need_uptime, need_capacity, - need_guard); - smartlist_subtract(sl,excludednodes); - if (excludedsmartlist) - smartlist_subtract(sl,excludedsmartlist); - if (excludedset) - routerset_subtract_routers(sl,excludedset); - - if (need_capacity || need_guard) - choice = routerlist_sl_choose_by_bandwidth(sl, rule); - else - choice = smartlist_choose(sl); - - smartlist_free(sl); - if (!choice && (need_uptime || need_capacity || need_guard)) { - /* 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); - choice = router_choose_random_node( - NULL, excludedsmartlist, excludedset, flags); - } + router_add_running_routers_to_smartlist(sl, allow_invalid, + need_uptime, need_capacity, + need_guard); + smartlist_subtract(sl,excludednodes); + if (excludedsmartlist) + smartlist_subtract(sl,excludedsmartlist); + if (excludedset) + routerset_subtract_routers(sl,excludedset); + + // Always weight by bandwidth + choice = routerlist_sl_choose_by_bandwidth(sl, rule); + + smartlist_free(sl); + if (!choice && (need_uptime || need_capacity || need_guard)) { + /* 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); + choice = router_choose_random_node( + excludedsmartlist, excludedset, flags); } smartlist_free(excludednodes); if (!choice) { - if (strict) { - log_warn(LD_CIRC, "All preferred nodes were down when trying to choose " - "node, and the Strict[...]Nodes option is set. Failing."); - } else { - log_warn(LD_CIRC, - "No available nodes when trying to choose node. Failing."); - } + log_warn(LD_CIRC, + "No available nodes when trying to choose node. Failing."); } return choice; } @@ -2367,6 +2691,9 @@ extrainfo_free(extrainfo_t *extrainfo) static void signed_descriptor_free(signed_descriptor_t *sd) { + if (!sd) + return; + tor_free(sd->signed_descriptor_body); /* XXXX remove this once more bugs go away. */ @@ -2374,12 +2701,15 @@ signed_descriptor_free(signed_descriptor_t *sd) tor_free(sd); } -/** Extract a signed_descriptor_t from a routerinfo, and free the routerinfo. +/** Extract a signed_descriptor_t from a general routerinfo, and free the + * routerinfo. */ static signed_descriptor_t * signed_descriptor_from_routerinfo(routerinfo_t *ri) { - signed_descriptor_t *sd = tor_malloc_zero(sizeof(signed_descriptor_t)); + signed_descriptor_t *sd; + tor_assert(ri->purpose == ROUTER_PURPOSE_GENERAL); + sd = tor_malloc_zero(sizeof(signed_descriptor_t)); memcpy(sd, &(ri->cache_info), sizeof(signed_descriptor_t)); sd->routerlist_index = -1; ri->cache_info.signed_descriptor_body = NULL; @@ -2398,7 +2728,8 @@ _extrainfo_free(void *e) void routerlist_free(routerlist_t *rl) { - tor_assert(rl); + if (!rl) + return; rimap_free(rl->identity_map, NULL); sdmap_free(rl->desc_digest_map, NULL); sdmap_free(rl->desc_by_eid_map, NULL); @@ -2437,46 +2768,6 @@ dump_routerlist_mem_usage(int severity) "In %d old descriptors: "U64_FORMAT" bytes.", smartlist_len(routerlist->routers), U64_PRINTF_ARG(livedescs), smartlist_len(routerlist->old_routers), U64_PRINTF_ARG(olddescs)); - -#if 0 - { - const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list(); - networkstatus_t *consensus = networkstatus_get_latest_consensus(); - log(severity, LD_DIR, "Now let's look through old_descriptors!"); - SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd, { - int in_v2 = 0; - int in_v3 = 0; - char published[ISO_TIME_LEN+1]; - char last_valid_until[ISO_TIME_LEN+1]; - char last_served_at[ISO_TIME_LEN+1]; - char id[HEX_DIGEST_LEN+1]; - routerstatus_t *rs; - format_iso_time(published, sd->published_on); - format_iso_time(last_valid_until, sd->last_listed_as_valid_until); - format_iso_time(last_served_at, sd->last_served_at); - base16_encode(id, sizeof(id), sd->identity_digest, DIGEST_LEN); - SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns, - { - rs = networkstatus_v2_find_entry(ns, sd->identity_digest); - if (rs && tor_memeq(rs->descriptor_digest, - sd->signed_descriptor_digest, DIGEST_LEN)) { - in_v2 = 1; break; - } - }); - if (consensus) { - rs = networkstatus_vote_find_entry(consensus, sd->identity_digest); - if (rs && tor_memeq(rs->descriptor_digest, - sd->signed_descriptor_digest, DIGEST_LEN)) - in_v3 = 1; - } - log(severity, LD_DIR, - "Old descriptor for %s (published %s) %sin v2 ns, %sin v3 " - "consensus. Last valid until %s; last served at %s.", - id, published, in_v2 ? "" : "not ", in_v3 ? "" : "not ", - last_valid_until, last_served_at); - }); - } -#endif } /** Debugging helper: If <b>idx</b> is nonnegative, assert that <b>ri</b> is @@ -2509,6 +2800,7 @@ static void routerlist_insert(routerlist_t *rl, routerinfo_t *ri) { routerinfo_t *ri_old; + signed_descriptor_t *sd_old; { /* XXXX Remove if this slows us down. */ routerinfo_t *ri_generated = router_get_my_routerinfo(); @@ -2518,8 +2810,16 @@ routerlist_insert(routerlist_t *rl, routerinfo_t *ri) ri_old = rimap_set(rl->identity_map, ri->cache_info.identity_digest, ri); tor_assert(!ri_old); - sdmap_set(rl->desc_digest_map, ri->cache_info.signed_descriptor_digest, - &(ri->cache_info)); + + sd_old = sdmap_set(rl->desc_digest_map, + ri->cache_info.signed_descriptor_digest, + &(ri->cache_info)); + if (sd_old) { + rl->desc_store.bytes_dropped += sd_old->signed_descriptor_len; + sdmap_remove(rl->desc_by_eid_map, sd_old->extra_info_digest); + signed_descriptor_free(sd_old); + } + if (!tor_digest_is_zero(ri->cache_info.extra_info_digest)) sdmap_set(rl->desc_by_eid_map, ri->cache_info.extra_info_digest, &ri->cache_info); @@ -2738,6 +3038,7 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, routerinfo_t *ri_new) { int idx; + int same_descriptors; routerinfo_t *ri_tmp; extrainfo_t *ei_tmp; @@ -2782,8 +3083,15 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, &ri_new->cache_info); } + same_descriptors = tor_memeq(ri_old->cache_info.signed_descriptor_digest, + ri_new->cache_info.signed_descriptor_digest, + DIGEST_LEN); + if (should_cache_old_descriptors() && - ri_old->purpose == ROUTER_PURPOSE_GENERAL) { + ri_old->purpose == ROUTER_PURPOSE_GENERAL && + !same_descriptors) { + /* ri_old is going to become a signed_descriptor_t and go into + * old_routers */ signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri_old); smartlist_add(rl->old_routers, sd); sd->routerlist_index = smartlist_len(rl->old_routers)-1; @@ -2791,24 +3099,27 @@ routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old, if (!tor_digest_is_zero(sd->extra_info_digest)) sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd); } else { - if (tor_memneq(ri_old->cache_info.signed_descriptor_digest, - ri_new->cache_info.signed_descriptor_digest, - DIGEST_LEN)) { - /* digests don't match; digestmap_set didn't replace */ + /* We're dropping ri_old. */ + if (!same_descriptors) { + /* digests don't match; The sdmap_set above didn't replace */ sdmap_remove(rl->desc_digest_map, ri_old->cache_info.signed_descriptor_digest); - } - ei_tmp = eimap_remove(rl->extra_info_map, - ri_old->cache_info.extra_info_digest); - if (ei_tmp) { - rl->extrainfo_store.bytes_dropped += - ei_tmp->cache_info.signed_descriptor_len; - extrainfo_free(ei_tmp); - } - if (!tor_digest_is_zero(ri_old->cache_info.extra_info_digest)) { - sdmap_remove(rl->desc_by_eid_map, - ri_old->cache_info.extra_info_digest); + if (tor_memneq(ri_old->cache_info.extra_info_digest, + ri_new->cache_info.extra_info_digest, DIGEST_LEN)) { + ei_tmp = eimap_remove(rl->extra_info_map, + ri_old->cache_info.extra_info_digest); + if (ei_tmp) { + rl->extrainfo_store.bytes_dropped += + ei_tmp->cache_info.signed_descriptor_len; + extrainfo_free(ei_tmp); + } + } + + if (!tor_digest_is_zero(ri_old->cache_info.extra_info_digest)) { + sdmap_remove(rl->desc_by_eid_map, + ri_old->cache_info.extra_info_digest); + } } rl->desc_store.bytes_dropped += ri_old->cache_info.signed_descriptor_len; routerinfo_free(ri_old); @@ -2846,8 +3157,7 @@ routerlist_reparse_old(routerlist_t *rl, signed_descriptor_t *sd) void routerlist_free_all(void) { - if (routerlist) - routerlist_free(routerlist); + routerlist_free(routerlist); routerlist = NULL; if (warned_nicknames) { SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp)); @@ -2900,8 +3210,8 @@ router_set_status(const char *digest, int up) router = router_get_by_digest(digest); if (router) { - log_debug(LD_DIR,"Marking router '%s/%s' as %s.", - router->nickname, router->address, up ? "up" : "down"); + log_debug(LD_DIR,"Marking router %s as %s.", + router_describe(router), up ? "up" : "down"); if (!up && router_is_me(router) && !we_are_hibernating()) log_warn(LD_NET, "We just marked ourself as down. Are your external " "addresses reachable?"); @@ -2940,7 +3250,8 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg, int from_cache, int from_fetch) { const char *id_digest; - int authdir = authdir_mode_handles_descs(get_options(), router->purpose); + or_options_t *options = get_options(); + int authdir = authdir_mode_handles_descs(options, router->purpose); int authdir_believes_valid = 0; routerinfo_t *old_router; networkstatus_t *consensus = networkstatus_get_latest_consensus(); @@ -2954,15 +3265,34 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg, id_digest = router->cache_info.identity_digest; + old_router = router_get_by_digest(id_digest); + /* Make sure that we haven't already got this exact descriptor. */ if (sdmap_get(routerlist->desc_digest_map, router->cache_info.signed_descriptor_digest)) { - log_info(LD_DIR, - "Dropping descriptor that we already have for router '%s'", - router->nickname); - *msg = "Router descriptor was not new."; - routerinfo_free(router); - return ROUTER_WAS_NOT_NEW; + /* If we have this descriptor already and the new descriptor is a bridge + * descriptor, replace it. If we had a bridge descriptor before and the + * new one is not a bridge descriptor, don't replace it. */ + + /* Only members of routerlist->identity_map can be bridges; we don't + * put bridges in old_routers. */ + const int was_bridge = old_router && + old_router->purpose == ROUTER_PURPOSE_BRIDGE; + + if (routerinfo_is_a_configured_bridge(router) && + router->purpose == ROUTER_PURPOSE_BRIDGE && + !was_bridge) { + log_info(LD_DIR, "Replacing non-bridge descriptor with bridge " + "descriptor for router %s", + router_describe(router)); + } else { + log_info(LD_DIR, + "Dropping descriptor that we already have for router %s", + router_describe(router)); + *msg = "Router descriptor was not new."; + routerinfo_free(router); + return ROUTER_WAS_NOT_NEW; + } } if (authdir) { @@ -2982,8 +3312,8 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg, /* We asked for it, so some networkstatus must have listed it when we * did. Save it if we're a cache in case somebody else asks for it. */ log_info(LD_DIR, - "Received a no-longer-recognized descriptor for router '%s'", - router->nickname); + "Received a no-longer-recognized descriptor for router %s", + router_describe(router)); *msg = "Router descriptor is not referenced by any network-status."; /* Only journal this desc if we'll be serving it. */ @@ -2999,15 +3329,14 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg, SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns, { routerstatus_t *rs = - networkstatus_v2_find_entry(ns, router->cache_info.identity_digest); + networkstatus_v2_find_entry(ns, id_digest); if (rs && tor_memeq(rs->descriptor_digest, router->cache_info.signed_descriptor_digest, DIGEST_LEN)) rs->need_to_mirror = 0; }); if (consensus) { - routerstatus_t *rs = networkstatus_vote_find_entry(consensus, - router->cache_info.identity_digest); + routerstatus_t *rs = networkstatus_vote_find_entry(consensus, id_digest); if (rs && tor_memeq(rs->descriptor_digest, router->cache_info.signed_descriptor_digest, DIGEST_LEN)) { @@ -3028,15 +3357,28 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg, return ROUTER_NOT_IN_CONSENSUS; } + /* If we're reading a bridge descriptor from our cache, and we don't + * recognize it as one of our currently configured bridges, drop the + * descriptor. Otherwise we could end up using it as one of our entry + * guards even if it isn't in our Bridge config lines. */ + if (router->purpose == ROUTER_PURPOSE_BRIDGE && from_cache && + !authdir_mode_bridge(options) && + !routerinfo_is_a_configured_bridge(router)) { + log_info(LD_DIR, "Dropping bridge descriptor for %s because we have " + "no bridge configured at that address.", + safe_str_client(router_describe(router))); + *msg = "Router descriptor was not a configured bridge."; + routerinfo_free(router); + return ROUTER_WAS_NOT_WANTED; + } + /* If we have a router with the same identity key, choose the newer one. */ - old_router = rimap_get(routerlist->identity_map, - router->cache_info.identity_digest); if (old_router) { if (!in_consensus && (router->cache_info.published_on <= old_router->cache_info.published_on)) { /* Same key, but old. This one is not listed in the consensus. */ - log_debug(LD_DIR, "Skipping not-new descriptor for router '%s'", - router->nickname); + log_debug(LD_DIR, "Not-new descriptor for router %s", + router_describe(router)); /* Only journal this desc if we'll be serving it. */ if (!from_cache && should_cache_old_descriptors()) signed_desc_append_to_journal(&router->cache_info, @@ -3046,11 +3388,9 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg, return ROUTER_WAS_NOT_NEW; } else { /* Same key, and either new, or listed in the consensus. */ - log_debug(LD_DIR, "Replacing entry for router '%s/%s' [%s]", - router->nickname, old_router->nickname, - hex_str(id_digest,DIGEST_LEN)); - if (router->addr == old_router->addr && - router->or_port == old_router->or_port) { + log_debug(LD_DIR, "Replacing entry for router %s", + router_describe(router)); + if (routers_have_same_or_addr(router, old_router)) { /* these carry over when the address and orport are unchanged. */ router->last_reachable = old_router->last_reachable; router->testing_since = old_router->testing_since; @@ -3078,9 +3418,10 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg, /* We haven't seen a router with this identity before. Add it to the end of * the list. */ routerlist_insert(routerlist, router); - if (!from_cache) + if (!from_cache) { signed_desc_append_to_journal(&router->cache_info, &routerlist->desc_store); + } directory_set_dirty(); return ROUTER_ADDED_SUCCESSFULLY; } @@ -3096,7 +3437,7 @@ router_add_extrainfo_to_routerlist(extrainfo_t *ei, const char **msg, int inserted; (void)from_fetch; if (msg) *msg = NULL; - /*XXXX022 Do something with msg */ + /*XXXX023 Do something with msg */ inserted = extrainfo_insert(router_get_routerlist(), ei); @@ -3324,8 +3665,8 @@ routerlist_remove_old_routers(void) /* Too old: remove it. (If we're a cache, just move it into * old_routers.) */ log_info(LD_DIR, - "Forgetting obsolete (too old) routerinfo for router '%s'", - router->nickname); + "Forgetting obsolete (too old) routerinfo for router %s", + router_describe(router)); routerlist_remove(routerlist, router, 1, now); i--; } @@ -3397,15 +3738,19 @@ routerlist_remove_old_routers(void) /** We just added a new set of descriptors. Take whatever extra steps * we need. */ -static void +void routerlist_descriptors_added(smartlist_t *sl, int from_cache) { tor_assert(sl); control_event_descriptors_changed(sl); - SMARTLIST_FOREACH(sl, routerinfo_t *, ri, + SMARTLIST_FOREACH_BEGIN(sl, routerinfo_t *, ri) { if (ri->purpose == ROUTER_PURPOSE_BRIDGE) learned_bridge_descriptor(ri, from_cache); - ); + if (ri->needs_retest_if_added) { + ri->needs_retest_if_added = 0; + dirserv_single_reachability_test(approx_time(), ri); + } + } SMARTLIST_FOREACH_END(ri); } /** @@ -3736,12 +4081,8 @@ add_trusted_dir_server(const char *nickname, const char *address, if (ent->or_port) ent->fake_status.version_supports_begindir = 1; -/* XX021 - wait until authorities are upgraded */ -#if 0 + ent->fake_status.version_supports_conditional_consensus = 1; -#else - ent->fake_status.version_supports_conditional_consensus = 0; -#endif smartlist_add(trusted_dir_servers, ent); router_dir_info_changed(); @@ -3756,10 +4097,8 @@ authority_cert_free(authority_cert_t *cert) return; tor_free(cert->cache_info.signed_descriptor_body); - if (cert->signing_key) - crypto_free_pk_env(cert->signing_key); - if (cert->identity_key) - crypto_free_pk_env(cert->identity_key); + crypto_free_pk_env(cert->signing_key); + crypto_free_pk_env(cert->identity_key); tor_free(cert); } @@ -3768,6 +4107,9 @@ authority_cert_free(authority_cert_t *cert) static void trusted_dir_server_free(trusted_dir_server_t *ds) { + if (!ds) + return; + tor_free(ds->nickname); tor_free(ds->description); tor_free(ds->address); @@ -3821,7 +4163,7 @@ list_pending_downloads(digestmap_t *result, const char *resource = TO_DIR_CONN(conn)->requested_resource; if (!strcmpstart(resource, prefix)) dir_split_resource_into_fingerprints(resource + p_len, - tmp, NULL, 1, 0); + tmp, NULL, DSR_HEX); } }); SMARTLIST_FOREACH(tmp, char *, d, @@ -3923,7 +4265,7 @@ client_would_use_router(routerstatus_t *rs, time_t now, or_options_t *options) * this number per server. */ #define MIN_DL_PER_REQUEST 4 /** To prevent a single screwy cache from confusing us by selective reply, - * try to split our requests into at least this this many requests. */ + * try to split our requests into at least this many requests. */ #define MIN_REQUESTS 3 /** If we want fewer than this many descriptors, wait until we * want more, or until MAX_CLIENT_INTERVAL_WITHOUT_REQUEST has @@ -3937,7 +4279,8 @@ client_would_use_router(routerstatus_t *rs, time_t now, or_options_t *options) * whether to delay fetching until we have more. If we don't want to delay, * launch one or more requests to the appropriate directory authorities. */ static void -launch_router_descriptor_downloads(smartlist_t *downloadable, time_t now) +launch_router_descriptor_downloads(smartlist_t *downloadable, + routerstatus_t *source, time_t now) { int should_delay = 0, n_downloadable; or_options_t *options = get_options(); @@ -3990,7 +4333,7 @@ launch_router_descriptor_downloads(smartlist_t *downloadable, time_t now) pds_flags |= PDS_NO_EXISTING_SERVERDESC_FETCH; } - n_per_request = (n_downloadable+MIN_REQUESTS-1) / MIN_REQUESTS; + n_per_request = CEIL_DIV(n_downloadable, MIN_REQUESTS); if (n_per_request > MAX_DL_PER_REQUEST) n_per_request = MAX_DL_PER_REQUEST; if (n_per_request < MIN_DL_PER_REQUEST) @@ -4003,11 +4346,11 @@ launch_router_descriptor_downloads(smartlist_t *downloadable, time_t now) log_info(LD_DIR, "Launching %d request%s for %d router%s, %d at a time", - (n_downloadable+n_per_request-1)/n_per_request, + CEIL_DIV(n_downloadable, n_per_request), req_plural, n_downloadable, rtr_plural, n_per_request); smartlist_sort_digests(downloadable); for (i=0; i < n_downloadable; i += n_per_request) { - initiate_descriptor_downloads(NULL, DIR_PURPOSE_FETCH_SERVERDESC, + initiate_descriptor_downloads(source, DIR_PURPOSE_FETCH_SERVERDESC, downloadable, i, i+n_per_request, pds_flags); } @@ -4163,18 +4506,18 @@ update_router_descriptor_cache_downloads_v2(time_t now) digestmap_free(map,NULL); } -/** For any descriptor that we want that's currently listed in the live - * consensus, download it as appropriate. */ -static void -update_consensus_router_descriptor_downloads(time_t now) +/** For any descriptor that we want that's currently listed in + * <b>consensus</b>, download it as appropriate. */ +void +update_consensus_router_descriptor_downloads(time_t now, int is_vote, + networkstatus_t *consensus) { or_options_t *options = get_options(); digestmap_t *map = NULL; smartlist_t *no_longer_old = smartlist_create(); smartlist_t *downloadable = smartlist_create(); + routerstatus_t *source = NULL; int authdir = authdir_mode(options); - networkstatus_t *consensus = - networkstatus_get_reasonably_live_consensus(now); int n_delayed=0, n_have=0, n_would_reject=0, n_wouldnt_use=0, n_inprogress=0, n_in_oldrouters=0; @@ -4183,10 +4526,24 @@ update_consensus_router_descriptor_downloads(time_t now) if (!consensus) goto done; + if (is_vote) { + /* where's it from, so we know whom to ask for descriptors */ + trusted_dir_server_t *ds; + networkstatus_voter_info_t *voter = smartlist_get(consensus->voters, 0); + tor_assert(voter); + ds = trusteddirserver_get_by_v3_auth_digest(voter->identity_digest); + if (ds) + source = &(ds->fake_status); + else + log_warn(LD_DIR, "couldn't lookup source from vote?"); + } + map = digestmap_new(); list_pending_descriptor_downloads(map, 0); - SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, rs, + SMARTLIST_FOREACH(consensus->routerstatus_list, void *, rsp, { + routerstatus_t *rs = + is_vote ? &(((vote_routerstatus_t *)rsp)->status) : rsp; signed_descriptor_t *sd; if ((sd = router_get_by_descriptor_digest(rs->descriptor_digest))) { routerinfo_t *ri; @@ -4221,6 +4578,19 @@ update_consensus_router_descriptor_downloads(time_t now) ++n_wouldnt_use; continue; /* We would never use it ourself. */ } + if (is_vote && source) { + char time_bufnew[ISO_TIME_LEN+1]; + char time_bufold[ISO_TIME_LEN+1]; + routerinfo_t *oldrouter = router_get_by_digest(rs->identity_digest); + format_iso_time(time_bufnew, rs->published_on); + if (oldrouter) + format_iso_time(time_bufold, oldrouter->cache_info.published_on); + log_info(LD_DIR, "Learned about %s (%s vs %s) from %s's vote (%s)", + routerstatus_describe(rs), + time_bufnew, + oldrouter ? time_bufold : "none", + source->nickname, oldrouter ? "known" : "unknown"); + } smartlist_add(downloadable, rs->descriptor_digest); }); @@ -4254,7 +4624,7 @@ update_consensus_router_descriptor_downloads(time_t now) smartlist_len(downloadable), n_delayed, n_have, n_in_oldrouters, n_would_reject, n_wouldnt_use, n_inprogress); - launch_router_descriptor_downloads(downloadable, now); + launch_router_descriptor_downloads(downloadable, source, now); digestmap_free(map, NULL); done: @@ -4264,7 +4634,7 @@ update_consensus_router_descriptor_downloads(time_t now) /** How often should we launch a server/authority request to be sure of getting * a guess for our IP? */ -/*XXXX021 this info should come from netinfo cells or something, or we should +/*XXXX023 this info should come from netinfo cells or something, or we should * do this only when we aren't seeing incoming data. see bug 652. */ #define DUMMY_DOWNLOAD_INTERVAL (20*60) @@ -4279,9 +4649,10 @@ update_router_descriptor_downloads(time_t now) if (directory_fetches_dir_info_early(options)) { update_router_descriptor_cache_downloads_v2(now); } - update_consensus_router_descriptor_downloads(now); + update_consensus_router_descriptor_downloads(now, 0, + networkstatus_get_reasonably_live_consensus(now)); - /* XXXX021 we could be smarter here; see notes on bug 652. */ + /* XXXX023 we could be smarter here; see notes on bug 652. */ /* If we're a server that doesn't have a configured address, we rely on * directory fetches to learn when our address changes. So if we haven't * tried to get any routerdescs in a long time, try a dummy fetch now. */ @@ -4416,16 +4787,21 @@ get_dir_info_status_string(void) /** Iterate over the servers listed in <b>consensus</b>, and count how many of * them seem like ones we'd use, and how many of <em>those</em> we have * descriptors for. Store the former in *<b>num_usable</b> and the latter in - * *<b>num_present</b>. */ + * *<b>num_present</b>. If <b>in_set</b> is non-NULL, only consider those + * routers in <b>in_set</b>. + */ static void count_usable_descriptors(int *num_present, int *num_usable, const networkstatus_t *consensus, - or_options_t *options, time_t now) + or_options_t *options, time_t now, + routerset_t *in_set) { *num_present = 0, *num_usable=0; SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, rs, { + if (in_set && ! routerset_contains_routerstatus(in_set, rs)) + continue; if (client_would_use_router(rs, now, options)) { ++*num_usable; /* the consensus says we want it. */ if (router_get_by_descriptor_digest(rs->descriptor_digest)) { @@ -4454,7 +4830,7 @@ count_loading_descriptors_progress(void) return 0; /* can't count descriptors if we have no list of them */ count_usable_descriptors(&num_present, &num_usable, - consensus, get_options(), now); + consensus, get_options(), now, NULL); if (num_usable == 0) return 0; /* don't div by 0 */ @@ -4498,22 +4874,39 @@ update_router_have_minimum_dir_info(void) goto done; } - count_usable_descriptors(&num_present, &num_usable, consensus, options, now); + count_usable_descriptors(&num_present, &num_usable, consensus, options, now, + NULL); if (num_present < num_usable/4) { tor_snprintf(dir_info_status, sizeof(dir_info_status), "We have only %d/%d usable descriptors.", num_present, num_usable); res = 0; control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0); + goto done; } else if (num_present < 2) { tor_snprintf(dir_info_status, sizeof(dir_info_status), "Only %d descriptor%s here and believed reachable!", num_present, num_present ? "" : "s"); res = 0; - } else { - res = 1; + goto done; + } + + /* Check for entry nodes. */ + if (options->EntryNodes) { + count_usable_descriptors(&num_present, &num_usable, consensus, options, + now, options->EntryNodes); + + if (!num_usable || !num_present) { + tor_snprintf(dir_info_status, sizeof(dir_info_status), + "We have only %d/%d usable entry node descriptors.", + num_present, num_usable); + res = 0; + goto done; + } } + res = 1; + done: if (res && !have_min_dir_info) { log(LOG_NOTICE, LD_DIR, @@ -4526,6 +4919,13 @@ update_router_have_minimum_dir_info(void) log(quiet ? LOG_INFO : LOG_NOTICE, LD_DIR, "Our directory information is no longer up-to-date " "enough to build circuits: %s", dir_info_status); + + /* a) make us log when we next complete a circuit, so we know when Tor + * is back up and usable, and b) disable some activities that Tor + * should only do while circuits are working, like reachability tests + * and fetching bridge descriptors only over circuits. */ + can_complete_circuit = 0; + control_event_client_status(LOG_NOTICE, "NOT_ENOUGH_DIR_INFO"); } have_min_dir_info = res; @@ -4813,8 +5213,8 @@ esc_router_info(routerinfo_t *router) static char *info=NULL; char *esc_contact, *esc_platform; size_t len; - if (info) - tor_free(info); + tor_free(info); + if (!router) return NULL; /* we're exiting; just free the memory we use */ @@ -4949,9 +5349,8 @@ void routerset_refresh_countries(routerset_t *target) { int cc; - if (target->countries) { - bitarray_free(target->countries); - } + bitarray_free(target->countries); + if (!geoip_is_loaded()) { target->countries = NULL; target->n_countries = 0; @@ -5025,7 +5424,9 @@ routerset_parse(routerset_t *target, const char *s, const char *description) return r; } -/** DOCDOC */ +/** Called when we change a node set, or when we reload the geoip list: + * recompute all country info in all configuration node sets and in the + * routerlist. */ void refresh_all_country_info(void) { @@ -5076,7 +5477,7 @@ routerset_needs_geoip(const routerset_t *set) } /** Return true iff there are no entries in <b>set</b>. */ -static int +int routerset_is_empty(const routerset_t *set) { return !set || smartlist_len(set->list) == 0; @@ -5159,10 +5560,11 @@ routerset_contains_routerstatus(const routerset_t *set, routerstatus_t *rs) } /** Add every known routerinfo_t that is a member of <b>routerset</b> to - * <b>out</b>. If <b>running_only</b>, only add the running ones. */ + * <b>out</b>, but never add any that are part of <b>excludeset</b>. + * If <b>running_only</b>, only add the running ones. */ void routerset_get_all_routers(smartlist_t *out, const routerset_t *routerset, - int running_only) + const routerset_t *excludeset, int running_only) { tor_assert(out); if (!routerset || !routerset->list) @@ -5172,12 +5574,13 @@ routerset_get_all_routers(smartlist_t *out, const routerset_t *routerset, if (routerset_is_list(routerset)) { /* No routers are specified by type; all are given by name or digest. - * we can do a lookup in O(len(list)). */ + * we can do a lookup in O(len(routerset)). */ SMARTLIST_FOREACH(routerset->list, const char *, name, { routerinfo_t *router = router_get_by_nickname(name, 1); if (router) { if (!running_only || router->is_running) - smartlist_add(out, router); + if (!routerset_contains_router(excludeset, router)) + smartlist_add(out, router); } }); } else { @@ -5187,15 +5590,21 @@ routerset_get_all_routers(smartlist_t *out, const routerset_t *routerset, SMARTLIST_FOREACH(rl->routers, routerinfo_t *, router, { if (running_only && !router->is_running) continue; - if (routerset_contains_router(routerset, router)) + if (routerset_contains_router(routerset, router) && + !routerset_contains_router(excludeset, router)) smartlist_add(out, router); }); } } -/** Add to <b>target</b> every routerinfo_t from <b>source</b> that is in - * <b>include</b>, but not excluded in a more specific fashion by - * <b>exclude</b>. If <b>running_only</b>, only include running routers. +#if 0 +/** Add to <b>target</b> every routerinfo_t from <b>source</b> except: + * + * 1) Don't add it if <b>include</b> is non-empty and the relay isn't in + * <b>include</b>; and + * 2) Don't add it if <b>exclude</b> is non-empty and the relay is + * excluded in a more specific fashion by <b>exclude</b>. + * 3) If <b>running_only</b>, don't add non-running routers. */ void routersets_get_disjunction(smartlist_t *target, @@ -5219,6 +5628,7 @@ routersets_get_disjunction(smartlist_t *target, } }); } +#endif /** Remove every routerinfo_t from <b>lst</b> that is in <b>routerset</b>. */ void @@ -5250,10 +5660,15 @@ routerset_to_string(const routerset_t *set) int routerset_equal(const routerset_t *old, const routerset_t *new) { - if (old == NULL && new == NULL) + if (routerset_is_empty(old) && routerset_is_empty(new)) { + /* Two empty sets are equal */ return 1; - else if (old == NULL || new == NULL) + } else if (routerset_is_empty(old) || routerset_is_empty(new)) { + /* An empty set is equal to nothing else. */ return 0; + } + tor_assert(old != NULL); + tor_assert(new != NULL); if (smartlist_len(old->list) != smartlist_len(new->list)) return 0; @@ -5265,35 +5680,15 @@ routerset_equal(const routerset_t *old, const routerset_t *new) }); return 1; - -#if 0 - /* XXXX: This won't work if the names/digests are identical but in a - different order. Checking for exact equality would be heavy going, - is it worth it? -RH*/ - /* This code is totally bogus; sizeof doesn't work even remotely like this - * code seems to think. Let's revert to a string-based comparison for - * now. -NM*/ - if (sizeof(old->names) != sizeof(new->names)) - return 0; - - if (tor_memcmp(old->names,new->names,sizeof(new->names))) - return 0; - if (sizeof(old->digests) != sizeof(new->digests)) - return 0; - if (tor_memcmp(old->digests,new->digests,sizeof(new->digests))) - return 0; - if (sizeof(old->countries) != sizeof(new->countries)) - return 0; - if (tor_memcmp(old->countries,new->countries,sizeof(new->countries))) - return 0; - return 1; -#endif } /** Free all storage held in <b>routerset</b>. */ void routerset_free(routerset_t *routerset) { + if (!routerset) + return; + SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp)); smartlist_free(routerset->list); SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p, @@ -5304,8 +5699,7 @@ routerset_free(routerset_t *routerset) strmap_free(routerset->names, NULL); digestmap_free(routerset->digests, NULL); - if (routerset->countries) - bitarray_free(routerset->countries); + bitarray_free(routerset->countries); tor_free(routerset); } @@ -5336,7 +5730,6 @@ hid_serv_get_responsible_directories(smartlist_t *responsible_dirs, { int start, found, n_added = 0, i; networkstatus_t *c = networkstatus_get_latest_consensus(); - int use_begindir = get_options()->TunnelDirConns; if (!c || !smartlist_len(c->routerstatus_list)) { log_warn(LD_REND, "We don't have a consensus, so we can't perform v2 " "rendezvous operations."); @@ -5349,14 +5742,9 @@ hid_serv_get_responsible_directories(smartlist_t *responsible_dirs, do { routerstatus_t *r = smartlist_get(c->routerstatus_list, i); if (r->is_hs_dir) { - if (r->dir_port || use_begindir) - smartlist_add(responsible_dirs, r); - else - log_info(LD_REND, "Not adding router '%s' to list of responsible " - "hidden service directories, because we have no way of " - "reaching it.", r->nickname); + smartlist_add(responsible_dirs, r); if (++n_added == REND_NUMBER_OF_CONSECUTIVE_REPLICAS) - break; + return 0; } if (++i == smartlist_len(c->routerstatus_list)) i = 0; @@ -5373,8 +5761,6 @@ int hid_serv_acting_as_directory(void) { routerinfo_t *me = router_get_my_routerinfo(); - networkstatus_t *c; - routerstatus_t *rs; if (!me) return 0; if (!get_options()->HidServDirectoryV2) { @@ -5382,22 +5768,6 @@ hid_serv_acting_as_directory(void) "because we have not been configured as such."); return 0; } - if (!(c = networkstatus_get_latest_consensus())) { - log_info(LD_REND, "There's no consensus, so I can't tell if I'm a hidden " - "service directory"); - return 0; - } - rs = networkstatus_vote_find_entry(c, me->cache_info.identity_digest); - if (!rs) { - log_info(LD_REND, "We're not listed in the consensus, so we're not " - "being a hidden service directory."); - return 0; - } - if (!rs->is_hs_dir) { - log_info(LD_REND, "We're not listed as a hidden service directory in " - "the consensus, so we won't be one."); - return 0; - } return 1; } |