March 2011 - tor-commits - lists.torproject.org

[tor/maint-0.2.2] Remove an incorrect comment in connection_or_check_valid_tls_handshake
by nickm＠torproject.org 08 Mar '11

08 Mar '11

commit 80357abb11023ff285c251ee75b864e0a27d5809 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Nov 22 11:36:22 2010 -0500 Remove an incorrect comment in connection_or_check_valid_tls_handshake --- src/or/connection_or.c | 3 --- 1 files changed, 0 insertions(+), 3 deletions(-) diff --git a/src/or/connection_or.c b/src/or/connection_or.c index 415a48d..6279c93 100644 --- a/src/or/connection_or.c +++ b/src/or/connection_or.c @@ -1098,9 +1098,6 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn, as_advertised = 0; } if (authdir_mode_tests_reachability(options)) { - /* We initiated this connection to address:port. Drop all routers - * with the same address:port and a different key. - */ dirserv_orconn_tls_done(conn->_base.address, conn->_base.port, digest_rcvd_out, as_advertised); }

1 0

[tor/maint-0.2.2] Handle negative run lengths in wfu/mtbf calculations
by nickm＠torproject.org 08 Mar '11

08 Mar '11

commit 5a9903b9e09697ac131c841310dd82eebcca02e0 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Nov 22 12:39:22 2010 -0500 Handle negative run lengths in wfu/mtbf calculations --- changes/bug1035 | 5 +++++ src/or/rephist.c | 22 +++++++++++++++------- 2 files changed, 20 insertions(+), 7 deletions(-) diff --git a/changes/bug1035 b/changes/bug1035 index 4b62b46..041e3b3 100644 --- a/changes/bug1035 +++ b/changes/bug1035 @@ -4,4 +4,9 @@ treat it as having any downtime for the purposes of stability calculation, whereas clients would experience downtime since the IP could take a while to propagate to them. Resolves issue 1035. + o Minor bugfixes (authorities) + - Try to be more robust to hops back in time when calculating + router stability. Previously, if a run of uptime or downtime + appeared to be negative, the calculation could give incorrect + results. Bugfix on 0.2.0.6-alpha. diff --git a/src/or/rephist.c b/src/or/rephist.c index a0c9c9f..e59fcb5 100644 --- a/src/or/rephist.c +++ b/src/or/rephist.c @@ -380,12 +380,20 @@ rep_hist_note_router_unreachable(const char *id, time_t when) long run_length = when - hist->start_of_run; format_local_iso_time(tbuf, hist->start_of_run); - hist->weighted_run_length += run_length; hist->total_run_weights += 1.0; hist->start_of_run = 0; - hist->weighted_uptime += run_length; - hist->total_weighted_time += run_length; + if (run_length < 0) { + unsigned long penalty = -run_length; +#define SUBTRACT_CLAMPED(var, penalty) \ + do { (var) = (var) < (penalty) ? 0 : (var) - (penalty); } while (0) + SUBTRACT_CLAMPED(hist->weighted_run_length, penalty); + SUBTRACT_CLAMPED(hist->weighted_uptime, penalty); + } else { + hist->weighted_run_length += run_length; + hist->weighted_uptime += run_length; + hist->total_weighted_time += run_length; + } was_running = 1; log_info(LD_HIST, "Router %s is now non-Running: it had previously been " "Running since %s. Its total weighted uptime is %lu/%lu.", @@ -458,7 +466,7 @@ rep_hist_downrate_old_runs(time_t now) static double get_stability(or_history_t *hist, time_t when) { - unsigned long total = hist->weighted_run_length; + long total = hist->weighted_run_length; double total_weights = hist->total_run_weights; if (hist->start_of_run) { @@ -494,8 +502,8 @@ get_total_weighted_time(or_history_t *hist, time_t when) static double get_weighted_fractional_uptime(or_history_t *hist, time_t when) { - unsigned long total = hist->total_weighted_time; - unsigned long up = hist->weighted_uptime; + long total = hist->total_weighted_time; + long up = hist->weighted_uptime; if (hist->start_of_run) { long run_length = (when - hist->start_of_run);

1 0

[tor/maint-0.2.2] Treat routers whose IPs have changed as having been down for MTBF/routerinfo
by nickm＠torproject.org 08 Mar '11

08 Mar '11

commit bea0a31c1c859a563f065d8b868570560abc5135 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Nov 22 12:30:33 2010 -0500 Treat routers whose IPs have changed as having been down for MTBF/routerinfo calculation purposes. --- changes/bug1035 | 7 +++++++ src/or/dirserv.c | 16 +++++++++++----- src/or/rephist.c | 38 +++++++++++++++++++++++++++++++++++++- src/or/rephist.h | 3 ++- 4 files changed, 57 insertions(+), 7 deletions(-) diff --git a/changes/bug1035 b/changes/bug1035 new file mode 100644 index 0000000..4b62b46 --- /dev/null +++ b/changes/bug1035 @@ -0,0 +1,7 @@ + o Minor features (authorities) + - Take altered router IPs into account when determining router stability. + Previously, if a router changed its IP, the authorities would not + treat it as having any downtime for the purposes of stability + calculation, whereas clients would experience downtime since the + IP could take a while to propagate to them. Resolves issue 1035. + diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 42d7d56..52e59cd 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -3108,19 +3108,25 @@ dirserv_orconn_tls_done(const char *address, tor_assert(address); tor_assert(digest_rcvd); - SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ri, { + /* XXX023 Doing a loop like this is stupid. We should just look up the + * router by digest_rcvd, and see if address, orport, and as_advertised + * match up. -NM */ + SMARTLIST_FOREACH_BEGIN(rl->routers, routerinfo_t *, ri) { if (!strcasecmp(address, ri->address) && or_port == ri->or_port && as_advertised && !memcmp(ri->cache_info.identity_digest, digest_rcvd, DIGEST_LEN)) { /* correct digest. mark this router reachable! */ if (!bridge_auth || ri->purpose == ROUTER_PURPOSE_BRIDGE) { - log_info(LD_DIRSERV, "Found router %s to be reachable. Yay.", - ri->nickname); - rep_hist_note_router_reachable(digest_rcvd, now); + tor_addr_t addr, *addrp=NULL; + log_info(LD_DIRSERV, "Found router %s to be reachable at %s. Yay.", + ri->nickname, address); + if (tor_addr_from_str(&addr, ri->address) != -1) + addrp = &addr; + rep_hist_note_router_reachable(digest_rcvd, addrp, now); ri->last_reachable = now; } } - }); + } SMARTLIST_FOREACH_END(ri); /* FFFF Maybe we should reinstate the code that dumps routers with the same * addr/port but with nonmatching keys, but instead of dumping, we should * skip testing. */ diff --git a/src/or/rephist.c b/src/or/rephist.c index 22b3ec5..a0c9c9f 100644 --- a/src/or/rephist.c +++ b/src/or/rephist.c @@ -14,6 +14,7 @@ #include "circuitlist.h" #include "circuituse.h" #include "config.h" +#include "networkstatus.h" #include "rephist.h" #include "router.h" #include "routerlist.h" @@ -73,6 +74,10 @@ typedef struct or_history_t { /** If nonzero, we have been unable to connect since this time. */ time_t down_since; + /** The address at which we most recently connected to this OR + * sucessfully. */ + tor_addr_t last_reached_addr; + /* === For MTBF tracking: */ /** Weighted sum total of all times that this router has been online. */ @@ -119,6 +124,7 @@ get_or_history(const char* id) rephist_total_num++; hist->link_history_map = digestmap_new(); hist->since = hist->changed = time(NULL); + tor_addr_make_unspec(&hist->last_reached_addr); digestmap_set(history_map, id, hist); } return hist; @@ -289,14 +295,19 @@ rep_hist_note_connection_died(const char* id, time_t when) /** We have just decided that this router with identity digest id is * reachable, meaning we will give it a "Running" flag for the next while. */ void -rep_hist_note_router_reachable(const char *id, time_t when) +rep_hist_note_router_reachable(const char *id, const tor_addr_t *at_addr, + time_t when) { or_history_t *hist = get_or_history(id); int was_in_run = 1; char tbuf[ISO_TIME_LEN+1]; + int addr_changed; tor_assert(hist); + addr_changed = at_addr && + tor_addr_compare(at_addr, &hist->last_reached_addr, CMP_EXACT) != 0; + if (!started_tracking_stability) started_tracking_stability = time(NULL); if (!hist->start_of_run) { @@ -315,6 +326,29 @@ rep_hist_note_router_reachable(const char *id, time_t when) down_length = when - hist->start_of_downtime; hist->total_weighted_time += down_length; hist->start_of_downtime = 0; + } else if (addr_changed) { + /* If we're reachable, but the address changed, treat this as some + * downtime. */ +#define MIN_DOWNTIME_FOR_ADDR_CHANGE 600 + int penalty = get_options()->TestingTorNetwork ? 240 : 3600; + networkstatus_t *ns; + tor_assert(at_addr); + + if ((ns = networkstatus_get_latest_consensus())) { + int fresh_interval = ns->fresh_until - ns->valid_after; + int live_interval = ns->valid_until - ns->valid_after; + /* on average, a descriptor addr change takes .5 intervals to make it + * into a consensus, and half a liveness period to make it to + * clients. */ + penalty = (fresh_interval + live_interval) / 2; + } + format_local_iso_time(tbuf, hist->start_of_run); + log_info(LD_HIST,"Router %s still seems Running, but its address appears " + "to have changed since the last time it was reachable. I'm " + "going to treat it as having been down for %d seconds", + hex_str(id, DIGEST_LEN), penalty); + rep_hist_note_router_unreachable(id, when-penalty); + rep_hist_note_router_reachable(id, NULL, when); } else { format_local_iso_time(tbuf, hist->start_of_run); if (was_in_run) @@ -324,6 +358,8 @@ rep_hist_note_router_reachable(const char *id, time_t when) log_info(LD_HIST,"Router %s is now Running; it was previously untracked", hex_str(id, DIGEST_LEN)); } + if (at_addr) + tor_addr_copy(&hist->last_reached_addr, at_addr); } /** We have just decided that this router is unreachable, meaning diff --git a/src/or/rephist.h b/src/or/rephist.h index 8f5a34d..1ddbac4 100644 --- a/src/or/rephist.h +++ b/src/or/rephist.h @@ -33,7 +33,8 @@ void rep_hist_update_state(or_state_t *state); int rep_hist_load_state(or_state_t *state, char **err); void rep_history_clean(time_t before); -void rep_hist_note_router_reachable(const char *id, time_t when); +void rep_hist_note_router_reachable(const char *id, const tor_addr_t *at_addr, + time_t when); void rep_hist_note_router_unreachable(const char *id, time_t when); int rep_hist_record_mtbf_data(time_t now, int missing_means_down); int rep_hist_load_mtbf_data(time_t now);

1 0

[tor/maint-0.2.2] update spec locations
by arma＠torproject.org 08 Mar '11

08 Mar '11

commit 9c72324ae85c3f2cc23fee7d383128fa239b36d0 Author: Roger Dingledine <arma(a)torproject.org> Date: Tue Mar 8 15:31:04 2011 -0500 update spec locations --- doc/HACKING | 13 ++++++------- 1 files changed, 6 insertions(+), 7 deletions(-) diff --git a/doc/HACKING b/doc/HACKING index bdb86c0..f42628b 100644 --- a/doc/HACKING +++ b/doc/HACKING @@ -5,17 +5,17 @@ Getting started --------------- For full information on how Tor is supposed to work, look at the files in -doc/spec/ . +https://gitweb.torproject.org/torspec.git/tree For an explanation of how to change Tor's design to work differently, look at -doc/spec/proposals/001-process.txt . +https://gitweb.torproject.org/torspec.git/blob_plain/HEAD:/proposals/001-process.txt For the latest version of the code, get a copy of git, and git clone git://git.torproject.org/git/tor . -We talk about Tor on the or-talk mailing list. Design proposals and -discussion belong on the or-dev mailing list. We hang around on +We talk about Tor on the tor-talk mailing list. Design proposals and +discussion belong on the tor-dev mailing list. We hang around on irc.oftc.net, with general discussion happening on #tor and development happening on #tor-dev. @@ -65,8 +65,8 @@ If at all possible, try to create this file in the same commit where you are making the change. Please give it a distinctive name that no other branch will use for the lifetime of your change. -When Roger goes to make a release, he will concatenate all the entries -in changes to make a draft changelog, and clear the directory. He'll +When we go to make a release, we will concatenate all the entries +in changes to make a draft changelog, and clear the directory. We'll then edit the draft changelog into a nice readable format. What needs a changes file?:: @@ -405,4 +405,3 @@ function should mention that it does that something in the documentation. If you rely on a function doing something beyond what is in its documentation, then you should watch out, or it might do something else later. -

1 0

[tor/master] Avoid crash in any_pending_bridge_descriptor_fetches
by nickm＠torproject.org 08 Mar '11

08 Mar '11

commit 9a6df215395750286383eed77f3c49d2b3ef34df Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 8 15:17:41 2011 -0500 Avoid crash in any_pending_bridge_descriptor_fetches This is based on shitlei's fix for bug2629, with extra parens removed. Fixes bug 2629, bugfix on 0.2.1.2-alpha. --- changes/bug2629 | 5 +++++ src/or/circuitbuild.c | 3 ++- 2 files changed, 7 insertions(+), 1 deletions(-) diff --git a/changes/bug2629 b/changes/bug2629 new file mode 100644 index 0000000..87817cf --- /dev/null +++ b/changes/bug2629 @@ -0,0 +1,5 @@ + o Minor bugfixes + - Fix a crash bug that could occur occasionally when a client was + configured with a large number of bridges. Fixes bug 2629; bugfix + on 0.2.1.2-alpha. Bugfix by trac user "shitlei". + diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 065eb05..76713e6 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -3200,7 +3200,8 @@ any_pending_bridge_descriptor_fetches(void) conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC && TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE && !conn->marked_for_close && - conn->linked && !conn->linked_conn->marked_for_close) { + conn->linked && + conn->linked_conn && !conn->linked_conn->marked_for_close) { log_debug(LD_DIR, "found one: %s", conn->address); return 1; }

1 0

[tor/master] Merge remote branch 'origin/maint-0.2.2'
by nickm＠torproject.org 08 Mar '11

08 Mar '11

commit d5907e7d9d79297cc7359aeae810972a1b834e23 Merge: 26009a3 9ad083d Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 8 15:23:30 2011 -0500 Merge remote branch 'origin/maint-0.2.2' changes/bug2629 | 5 +++++ doc/HACKING | 10 +++++----- src/or/circuitbuild.c | 3 ++- 3 files changed, 12 insertions(+), 6 deletions(-) diff --combined src/or/circuitbuild.c index cfc6b0d,6be27d2..7ad3b07 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@@ -23,7 -23,6 +23,7 @@@ #include "directory.h" #include "main.h" #include "networkstatus.h" +#include "nodelist.h" #include "onion.h" #include "policies.h" #include "relay.h" @@@ -55,8 -54,8 +55,8 @@@ extern circuit_t *global_circuitlist /** An entry_guard_t represents our information about a chosen long-term * first hop, known as a "helper" node in the literature. We can't just - * use a routerinfo_t, since we want to remember these even when we - * don't have a directory. */ + * use a node_t, since we want to remember these even when we + * don't have any directory info. */ typedef struct { char nickname[MAX_NICKNAME_LEN+1]; char identity[DIGEST_LEN]; @@@ -95,7 -94,7 +95,7 @@@ static int circuit_deliver_create_cell( static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit); static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath); static int onion_extend_cpath(origin_circuit_t *circ); -static int count_acceptable_routers(smartlist_t *routers); +static int count_acceptable_nodes(smartlist_t *routers); static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice); static void entry_guards_changed(void); @@@ -1514,9 -1513,10 +1514,9 @@@ circuit_list_path_impl(origin_circuit_ hop = circ->cpath; do { - routerinfo_t *ri; - routerstatus_t *rs; char *elt; const char *id; + const node_t *node; if (!hop) break; if (!verbose && hop->state != CPATH_STATE_OPEN) @@@ -1526,8 -1526,10 +1526,8 @@@ id = hop->extend_info->identity_digest; if (verbose_names) { elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1); - if ((ri = router_get_by_digest(id))) { - router_get_verbose_nickname(elt, ri); - } else if ((rs = router_get_consensus_status_by_id(id))) { - routerstatus_get_verbose_nickname(elt, rs); + if ((node = node_get_by_id(id))) { + node_get_verbose_nickname(node, elt); } else if (is_legal_nickname(hop->extend_info->nickname)) { elt[0] = '$'; base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN); @@@ -1539,9 -1541,9 +1539,9 @@@ base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN); } } else { /* ! verbose_names */ - if ((ri = router_get_by_digest(id)) && - ri->is_named) { - elt = tor_strdup(hop->extend_info->nickname); + node = node_get_by_id(id); + if (node && node_is_named(node)) { + elt = tor_strdup(node_get_nickname(node)); } else { elt = tor_malloc(HEX_DIGEST_LEN+2); elt[0] = '$'; @@@ -1610,28 -1612,31 +1610,28 @@@ voi circuit_rep_hist_note_result(origin_circuit_t *circ) { crypt_path_t *hop; - char *prev_digest = NULL; - routerinfo_t *router; + const char *prev_digest = NULL; hop = circ->cpath; if (!hop) /* circuit hasn't started building yet. */ return; if (server_mode(get_options())) { - routerinfo_t *me = router_get_my_routerinfo(); + const routerinfo_t *me = router_get_my_routerinfo(); if (!me) return; prev_digest = me->cache_info.identity_digest; } do { - router = router_get_by_digest(hop->extend_info->identity_digest); - if (router) { + const node_t *node = node_get_by_id(hop->extend_info->identity_digest); + if (node) { /* Why do we check this? We know the identity. -NM XXXX */ if (prev_digest) { if (hop->state == CPATH_STATE_OPEN) - rep_hist_note_extend_succeeded(prev_digest, - router->cache_info.identity_digest); + rep_hist_note_extend_succeeded(prev_digest, node->identity); else { - rep_hist_note_extend_failed(prev_digest, - router->cache_info.identity_digest); + rep_hist_note_extend_failed(prev_digest, node->identity); break; } } - prev_digest = router->cache_info.identity_digest; + prev_digest = node->identity; } else { prev_digest = NULL; } @@@ -1901,7 -1906,7 +1901,7 @@@ in inform_testing_reachability(void) { char dirbuf[128]; - routerinfo_t *me = router_get_my_routerinfo(); + const routerinfo_t *me = router_get_my_routerinfo(); if (!me) return 0; control_event_server_status(LOG_NOTICE, @@@ -1973,7 -1978,7 +1973,7 @@@ in circuit_send_next_onion_skin(origin_circuit_t *circ) { crypt_path_t *hop; - routerinfo_t *router; + const node_t *node; char payload[2+4+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN]; char *onionskin; size_t payload_len; @@@ -1989,7 -1994,7 +1989,7 @@@ else control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0); - router = router_get_by_digest(circ->_base.n_conn->identity_digest); + node = node_get_by_id(circ->_base.n_conn->identity_digest); fast = should_use_create_fast_for_circuit(circ); if (!fast) { /* We are an OR and we know the right onion key: we should @@@ -2023,7 -2028,7 +2023,7 @@@ circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING); log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'", fast ? "CREATE_FAST" : "CREATE", - router ? router->nickname : "<unnamed>"); + node ? node_get_nickname(node) : "<unnamed>"); } else { tor_assert(circ->cpath->state == CPATH_STATE_OPEN); tor_assert(circ->_base.state == CIRCUIT_STATE_BUILDING); @@@ -2036,7 -2041,7 +2036,7 @@@ struct timeval end; long timediff; tor_gettimeofday(&end); - timediff = tv_mdiff(&circ->_base.highres_created, &end); + timediff = tv_mdiff(&circ->_base.timestamp_created, &end); /* * If the circuit build time is much greater than we would have cut @@@ -2499,12 -2504,12 +2499,12 @@@ onionskin_answer(or_circuit_t *circ, ui */ static int new_route_len(uint8_t purpose, extend_info_t *exit, - smartlist_t *routers) + smartlist_t *nodes) { int num_acceptable_routers; int routelen; - tor_assert(routers); + tor_assert(nodes); routelen = DEFAULT_ROUTE_LEN; if (exit && @@@ -2512,10 -2517,10 +2512,10 @@@ purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO) routelen++; - num_acceptable_routers = count_acceptable_routers(routers); + num_acceptable_routers = count_acceptable_nodes(nodes); log_debug(LD_CIRC,"Chosen route length %d (%d/%d routers suitable).", - routelen, num_acceptable_routers, smartlist_len(routers)); + routelen, num_acceptable_routers, smartlist_len(nodes)); if (num_acceptable_routers < 2) { log_info(LD_CIRC, @@@ -2533,12 -2538,24 +2533,12 @@@ return routelen; } -/** Fetch the list of predicted ports, dup it into a smartlist of - * uint16_t's, remove the ones that are already handled by an - * existing circuit, and return it. - */ +/** Return a newly allocated list of uint16_t * for each predicted port not + * handled by a current circuit. */ static smartlist_t * circuit_get_unhandled_ports(time_t now) { - smartlist_t *source = rep_hist_get_predicted_ports(now); - smartlist_t *dest = smartlist_create(); - uint16_t *tmp; - int i; - - for (i = 0; i < smartlist_len(source); ++i) { - tmp = tor_malloc(sizeof(uint16_t)); - memcpy(tmp, smartlist_get(source, i), sizeof(uint16_t)); - smartlist_add(dest, tmp); - } - + smartlist_t *dest = rep_hist_get_predicted_ports(now); circuit_remove_handled_ports(dest); return dest; } @@@ -2572,12 -2589,12 +2572,12 @@@ circuit_all_predicted_ports_handled(tim return enough; } -/** Return 1 if router can handle one or more of the ports in +/** Return 1 if node can handle one or more of the ports in * needed_ports, else return 0. */ static int -router_handles_some_port(routerinfo_t *router, smartlist_t *needed_ports) -{ +node_handles_some_port(const node_t *node, smartlist_t *needed_ports) +{ /* XXXX MOVE */ int i; uint16_t port; @@@ -2587,10 -2604,7 +2587,10 @@@ needed_ports is explicitly a smartlist of uint16_t's */ port = *(uint16_t *)smartlist_get(needed_ports, i); tor_assert(port); - r = compare_addr_to_addr_policy(0, port, router->exit_policy); + if (node) + r = compare_addr_to_node_policy(0, port, node); + else + continue; if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED) return 1; } @@@ -2623,17 -2637,18 +2623,17 @@@ ap_stream_wants_exit_attention(connecti * * Return NULL if we can't find any suitable routers. */ -static routerinfo_t * -choose_good_exit_server_general(routerlist_t *dir, int need_uptime, - int need_capacity) +static const node_t * +choose_good_exit_server_general(int need_uptime, int need_capacity) { int *n_supported; - int i; int n_pending_connections = 0; smartlist_t *connections; int best_support = -1; int n_best_support=0; - routerinfo_t *router; or_options_t *options = get_options(); + const smartlist_t *the_nodes; + const node_t *node=NULL; connections = get_connection_array(); @@@ -2654,11 -2669,10 +2654,11 @@@ * * -1 means "Don't use this router at all." */ - n_supported = tor_malloc(sizeof(int)*smartlist_len(dir->routers)); - for (i = 0; i < smartlist_len(dir->routers); ++i) {/* iterate over routers */ - router = smartlist_get(dir->routers, i); - if (router_is_me(router)) { + the_nodes = nodelist_get_list(); + n_supported = tor_malloc(sizeof(int)*smartlist_len(the_nodes)); + SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) { + const int i = node_sl_idx; + if (router_digest_is_me(node->identity)) { n_supported[i] = -1; // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname); /* XXX there's probably a reverse predecessor attack here, but @@@ -2666,15 -2680,13 +2666,15 @@@ */ continue; } - if (!router->is_running || router->is_bad_exit) { + if (!node_has_descriptor(node)) + continue; + if (!node->is_running || node->is_bad_exit) { n_supported[i] = -1; continue; /* skip routers that are known to be down or bad exits */ } - if (router_is_unreliable(router, need_uptime, need_capacity, 0) && + if (node_is_unreliable(node, need_uptime, need_capacity, 0) && (!options->ExitNodes || - !routerset_contains_router(options->ExitNodes, router))) { + !routerset_contains_node(options->ExitNodes, node))) { /* FFFF Someday, differentiate between a routerset that names * routers, and a routerset that names countries, and only do this * check if they've asked for specific exit relays. Or if the country @@@ -2683,19 -2695,18 +2683,19 @@@ continue; /* skip routers that are not suitable, unless we have * ExitNodes set, in which case we asked for it */ } - if (!(router->is_valid || options->_AllowInvalid & ALLOW_INVALID_EXIT)) { + if (!(node->is_valid || options->_AllowInvalid & ALLOW_INVALID_EXIT)) { /* if it's invalid and we don't want it */ n_supported[i] = -1; // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.", // router->nickname, i); continue; /* skip invalid routers */ } - if (options->ExcludeSingleHopRelays && router->allow_single_hop_exits) { + if (options->ExcludeSingleHopRelays && + node_allows_single_hop_exits(node)) { n_supported[i] = -1; continue; } - if (router_exit_policy_rejects_all(router)) { + if (node_exit_policy_rejects_all(node)) { n_supported[i] = -1; // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.", // router->nickname, i); @@@ -2703,10 -2714,11 +2703,10 @@@ } n_supported[i] = 0; /* iterate over connections */ - SMARTLIST_FOREACH(connections, connection_t *, conn, - { + SMARTLIST_FOREACH_BEGIN(connections, connection_t *, conn) { if (!ap_stream_wants_exit_attention(conn)) continue; /* Skip everything but APs in CIRCUIT_WAIT */ - if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), router, 1)) { + if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), node, 1)) { ++n_supported[i]; // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.", // router->nickname, i, n_supported[i]); @@@ -2714,7 -2726,7 +2714,7 @@@ // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.", // router->nickname, i); } - }); /* End looping over connections. */ + } SMARTLIST_FOREACH_END(conn); if (n_pending_connections > 0 && n_supported[i] == 0) { /* Leave best_support at -1 if that's where it is, so we can * distinguish it later. */ @@@ -2731,7 -2743,7 +2731,7 @@@ * count of equally good routers.*/ ++n_best_support; } - } + } SMARTLIST_FOREACH_END(node); log_info(LD_CIRC, "Found %d servers that might support %d/%d pending connections.", n_best_support, best_support >= 0 ? best_support : 0, @@@ -2742,19 -2754,18 +2742,19 @@@ if (best_support > 0) { smartlist_t *supporting = smartlist_create(), *use = smartlist_create(); - for (i = 0; i < smartlist_len(dir->routers); i++) - if (n_supported[i] == best_support) - smartlist_add(supporting, smartlist_get(dir->routers, i)); + SMARTLIST_FOREACH(the_nodes, const node_t *, node, { + if (n_supported[node_sl_idx] == best_support) + smartlist_add(supporting, (void*)node); + }); - routersets_get_disjunction(use, supporting, options->ExitNodes, + routersets_get_node_disjunction(use, supporting, options->ExitNodes, options->_ExcludeExitNodesUnion, 1); if (smartlist_len(use) == 0 && options->ExitNodes && !options->StrictNodes) { /* give up on exitnodes and try again */ - routersets_get_disjunction(use, supporting, NULL, + routersets_get_node_disjunction(use, supporting, NULL, options->_ExcludeExitNodesUnion, 1); } - router = routerlist_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT); + node = node_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT); smartlist_free(use); smartlist_free(supporting); } else { @@@ -2773,7 -2784,7 +2773,7 @@@ need_capacity?", fast":"", need_uptime?", stable":""); tor_free(n_supported); - return choose_good_exit_server_general(dir, 0, 0); + return choose_good_exit_server_general(0, 0); } log_notice(LD_CIRC, "All routers are down or won't exit%s -- " "choosing a doomed exit at random.", @@@ -2785,29 -2796,28 +2785,29 @@@ for (attempt = 0; attempt < 2; attempt++) { /* try once to pick only from routers that satisfy a needed port, * then if there are none, pick from any that support exiting. */ - for (i = 0; i < smartlist_len(dir->routers); i++) { - router = smartlist_get(dir->routers, i); - if (n_supported[i] != -1 && - (attempt || router_handles_some_port(router, needed_ports))) { + SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) { + if (!node_has_descriptor(node)) + continue; + if (n_supported[node_sl_idx] != -1 && + (attempt || node_handles_some_port(node, needed_ports))) { // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.", // try, router->nickname); - smartlist_add(supporting, router); + smartlist_add(supporting, (void*)node); } - } + } SMARTLIST_FOREACH_END(node); - routersets_get_disjunction(use, supporting, options->ExitNodes, + routersets_get_node_disjunction(use, supporting, options->ExitNodes, options->_ExcludeExitNodesUnion, 1); if (smartlist_len(use) == 0 && options->ExitNodes && !options->StrictNodes) { /* give up on exitnodes and try again */ - routersets_get_disjunction(use, supporting, NULL, + routersets_get_node_disjunction(use, supporting, NULL, options->_ExcludeExitNodesUnion, 1); } /* FFF sometimes the above results in null, when the requested * exit node is considered down by the consensus. we should pick * it anyway, since the user asked for it. */ - router = routerlist_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT); - if (router) + node = node_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT); + if (node) break; smartlist_clear(supporting); smartlist_clear(use); @@@ -2819,9 -2829,9 +2819,9 @@@ } tor_free(n_supported); - if (router) { - log_info(LD_CIRC, "Chose exit server '%s'", router->nickname); - return router; + if (node) { + log_info(LD_CIRC, "Chose exit server '%s'", node_get_nickname(node)); + return node; } if (options->ExitNodes && options->StrictNodes) { log_warn(LD_CIRC, @@@ -2841,12 -2851,12 +2841,12 @@@ * For client-side rendezvous circuits, choose a random node, weighted * toward the preferences in 'options'. */ -static routerinfo_t * -choose_good_exit_server(uint8_t purpose, routerlist_t *dir, +static const node_t * +choose_good_exit_server(uint8_t purpose, int need_uptime, int need_capacity, int is_internal) { or_options_t *options = get_options(); - router_crn_flags_t flags = 0; + router_crn_flags_t flags = CRN_NEED_DESC; if (need_uptime) flags |= CRN_NEED_UPTIME; if (need_capacity) @@@ -2859,7 -2869,7 +2859,7 @@@ if (is_internal) /* pick it like a middle hop */ return router_choose_random_node(NULL, options->ExcludeNodes, flags); else - return choose_good_exit_server_general(dir,need_uptime,need_capacity); + return choose_good_exit_server_general(need_uptime,need_capacity); case CIRCUIT_PURPOSE_C_ESTABLISH_REND: if (options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS) flags |= CRN_ALLOW_INVALID; @@@ -2940,12 -2950,13 +2940,12 @@@ static in onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit) { cpath_build_state_t *state = circ->build_state; - routerlist_t *rl = router_get_routerlist(); if (state->onehop_tunnel) { log_debug(LD_CIRC, "Launching a one-hop circuit for dir tunnel."); state->desired_path_len = 1; } else { - int r = new_route_len(circ->_base.purpose, exit, rl->routers); + int r = new_route_len(circ->_base.purpose, exit, nodelist_get_list()); if (r < 1) /* must be at least 1 */ return -1; state->desired_path_len = r; @@@ -2956,15 -2967,14 +2956,15 @@@ log_info(LD_CIRC,"Using requested exit node '%s'", exit->nickname); exit = extend_info_dup(exit); } else { /* we have to decide one */ - routerinfo_t *router = - choose_good_exit_server(circ->_base.purpose, rl, state->need_uptime, + const node_t *node = + choose_good_exit_server(circ->_base.purpose, state->need_uptime, state->need_capacity, state->is_internal); - if (!router) { + if (!node) { log_warn(LD_CIRC,"failed to choose an exit server"); return -1; } - exit = extend_info_from_router(router); + exit = extend_info_from_node(node); + tor_assert(exit); } state->chosen_exit = exit; return 0; @@@ -3015,30 -3025,35 +3015,30 @@@ circuit_extend_to_new_exit(origin_circu * and available for building circuits through. */ static int -count_acceptable_routers(smartlist_t *routers) +count_acceptable_nodes(smartlist_t *nodes) { - int i, n; int num=0; - routerinfo_t *r; - n = smartlist_len(routers); - for (i=0;i<n;i++) { - r = smartlist_get(routers, i); -// log_debug(LD_CIRC, + SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) { + // log_debug(LD_CIRC, // "Contemplating whether router %d (%s) is a new option.", // i, r->nickname); - if (r->is_running == 0) { + if (! node->is_running) // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i); - goto next_i_loop; - } - if (r->is_valid == 0) { + continue; + if (! node->is_valid) // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i); - goto next_i_loop; + continue; + if (! node_has_descriptor(node)) + continue; /* XXX This clause makes us count incorrectly: if AllowInvalidRouters * allows this node in some places, then we're getting an inaccurate * count. For now, be conservative and don't count it. But later we * should try to be smarter. */ - } - num++; + ++num; + } SMARTLIST_FOREACH_END(node); + // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num); - next_i_loop: - ; /* C requires an explicit statement after the label */ - } return num; } @@@ -3066,31 -3081,31 +3066,31 @@@ onion_append_to_cpath(crypt_path_t **he * circuit. In particular, make sure we don't pick the exit node or its * family, and make sure we don't duplicate any previous nodes or their * families. */ -static routerinfo_t * +static const node_t * choose_good_middle_server(uint8_t purpose, cpath_build_state_t *state, crypt_path_t *head, int cur_len) { int i; - routerinfo_t *r, *choice; + const node_t *r, *choice; crypt_path_t *cpath; smartlist_t *excluded; or_options_t *options = get_options(); - router_crn_flags_t flags = 0; + router_crn_flags_t flags = CRN_NEED_DESC; tor_assert(_CIRCUIT_PURPOSE_MIN <= purpose && purpose <= _CIRCUIT_PURPOSE_MAX); log_debug(LD_CIRC, "Contemplating intermediate hop: random choice."); excluded = smartlist_create(); - if ((r = build_state_get_exit_router(state))) { - smartlist_add(excluded, r); - routerlist_add_family(excluded, r); + if ((r = build_state_get_exit_node(state))) { + smartlist_add(excluded, (void*) r); + nodelist_add_node_family(excluded, r); } for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) { - if ((r = router_get_by_digest(cpath->extend_info->identity_digest))) { - smartlist_add(excluded, r); - routerlist_add_family(excluded, r); + if ((r = node_get_by_id(cpath->extend_info->identity_digest))) { + smartlist_add(excluded, (void*)r); + nodelist_add_node_family(excluded, r); } } @@@ -3113,45 -3128,44 +3113,45 @@@ * If state is NULL, we're choosing a router to serve as an entry * guard, not for any particular circuit. */ -static routerinfo_t * +static const node_t * choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state) { - routerinfo_t *r, *choice; + const node_t *choice; smartlist_t *excluded; or_options_t *options = get_options(); - router_crn_flags_t flags = CRN_NEED_GUARD; + router_crn_flags_t flags = CRN_NEED_GUARD|CRN_NEED_DESC; + const node_t *node; if (state && options->UseEntryGuards && (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) { + /* This is request for an entry server to use for a regular circuit, + * and we use entry guard nodes. Just return one of the guard nodes. */ return choose_random_entry(state); } excluded = smartlist_create(); - if (state && (r = build_state_get_exit_router(state))) { - smartlist_add(excluded, r); - routerlist_add_family(excluded, r); + if (state && (node = build_state_get_exit_node(state))) { + /* Exclude the exit node from the state, if we have one. Also exclude its + * family. */ + smartlist_add(excluded, (void*)node); + nodelist_add_node_family(excluded, node); } if (firewall_is_fascist_or()) { - /*XXXX This could slow things down a lot; use a smarter implementation */ - /* exclude all ORs that listen on the wrong port, if anybody notices. */ - routerlist_t *rl = router_get_routerlist(); - int i; - - for (i=0; i < smartlist_len(rl->routers); i++) { - r = smartlist_get(rl->routers, i); - if (!fascist_firewall_allows_or(r)) - smartlist_add(excluded, r); - } + /* Exclude all ORs that we can't reach through our firewall */ + smartlist_t *nodes = nodelist_get_list(); + SMARTLIST_FOREACH(nodes, const node_t *, node, { + if (!fascist_firewall_allows_node(node)) + smartlist_add(excluded, (void*)node); + }); } - /* and exclude current entry guards, if applicable */ + /* and exclude current entry guards and their families, if applicable */ if (options->UseEntryGuards && entry_guards) { SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, { - if ((r = router_get_by_digest(entry->identity))) { - smartlist_add(excluded, r); - routerlist_add_family(excluded, r); + if ((node = node_get_by_id(entry->identity))) { + smartlist_add(excluded, (void*)node); + nodelist_add_node_family(excluded, node); } }); } @@@ -3207,18 -3221,14 +3207,18 @@@ onion_extend_cpath(origin_circuit_t *ci if (cur_len == state->desired_path_len - 1) { /* Picking last node */ info = extend_info_dup(state->chosen_exit); } else if (cur_len == 0) { /* picking first node */ - routerinfo_t *r = choose_good_entry_server(purpose, state); - if (r) - info = extend_info_from_router(r); + const node_t *r = choose_good_entry_server(purpose, state); + if (r) { + info = extend_info_from_node(r); + tor_assert(info); + } } else { - routerinfo_t *r = + const node_t *r = choose_good_middle_server(purpose, state, circ->cpath, cur_len); - if (r) - info = extend_info_from_router(r); + if (r) { + info = extend_info_from_node(r); + tor_assert(info); + } } if (!info) { @@@ -3277,7 -3287,7 +3277,7 @@@ extend_info_alloc(const char *nickname /** Allocate and return a new extend_info_t that can be used to build a * circuit to or through the router r. */ extend_info_t * -extend_info_from_router(routerinfo_t *r) +extend_info_from_router(const routerinfo_t *r) { tor_addr_t addr; tor_assert(r); @@@ -3286,29 -3296,6 +3286,29 @@@ r->onion_pkey, &addr, r->or_port); } +/** Allocate and return a new extend_info that can be used to build a ircuit + * to or through the node node. May return NULL if there is not + * enough info about node to extend to it--for example, if there + * is no routerinfo_t or microdesc_t. + **/ +extend_info_t * +extend_info_from_node(const node_t *node) +{ + if (node->ri) { + return extend_info_from_router(node->ri); + } else if (node->rs && node->md) { + tor_addr_t addr; + tor_addr_from_ipv4h(&addr, node->rs->addr); + return extend_info_alloc(node->rs->nickname, + node->identity, + node->md->onion_pkey, + &addr, + node->rs->or_port); + } else { + return NULL; + } +} + /** Release storage held by an extend_info_t struct. */ void extend_info_free(extend_info_t *info) @@@ -3339,12 -3326,12 +3339,12 @@@ extend_info_dup(extend_info_t *info * If there is no chosen exit, or if we don't know the routerinfo_t for * the chosen exit, return NULL. */ -routerinfo_t * -build_state_get_exit_router(cpath_build_state_t *state) +const node_t * +build_state_get_exit_node(cpath_build_state_t *state) { if (!state || !state->chosen_exit) return NULL; - return router_get_by_digest(state->chosen_exit->identity_digest); + return node_get_by_id(state->chosen_exit->identity_digest); } /** Return the nickname for the chosen exit router in state. If @@@ -3366,8 -3353,9 +3366,8 @@@ build_state_get_exit_nickname(cpath_bui * * If it's not usable, set *reason to a static string explaining why. */ -/*XXXX take a routerstatus, not a routerinfo. */ static int -entry_guard_set_status(entry_guard_t *e, routerinfo_t *ri, +entry_guard_set_status(entry_guard_t *e, const node_t *node, time_t now, or_options_t *options, const char **reason) { char buf[HEX_DIGEST_LEN+1]; @@@ -3376,17 -3364,16 +3376,17 @@@ *reason = NULL; /* Do we want to mark this guard as bad? */ - if (!ri) + if (!node) *reason = "unlisted"; - else if (!ri->is_running) + else if (!node->is_running) *reason = "down"; - else if (options->UseBridges && ri->purpose != ROUTER_PURPOSE_BRIDGE) + else if (options->UseBridges && (!node->ri || + node->ri->purpose != ROUTER_PURPOSE_BRIDGE)) *reason = "not a bridge"; - else if (!options->UseBridges && !ri->is_possible_guard && - !routerset_contains_router(options->EntryNodes,ri)) + else if (!options->UseBridges && !node->is_possible_guard && + !routerset_contains_node(options->EntryNodes,node)) *reason = "not recommended as a guard"; - else if (routerset_contains_router(options->ExcludeNodes, ri)) + else if (routerset_contains_node(options->ExcludeNodes, node)) *reason = "excluded"; if (*reason && ! e->bad_since) { @@@ -3430,7 -3417,7 +3430,7 @@@ entry_is_time_to_retry(entry_guard_t *e return now > (e->last_attempted + 36*60*60); } -/** Return the router corresponding to e, if e is +/** Return the node corresponding to e, if e is * working well enough that we are willing to use it as an entry * right now. (Else return NULL.) In particular, it must be * - Listed as either up or never yet contacted; @@@ -3444,11 -3431,11 +3444,11 @@@ * * If the answer is no, set *msg to an explanation of why. */ -static INLINE routerinfo_t * +static INLINE const node_t * entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity, int assume_reachable, const char **msg) { - routerinfo_t *r; + const node_t *node; or_options_t *options = get_options(); tor_assert(msg); @@@ -3462,36 -3449,33 +3462,36 @@@ *msg = "unreachable"; return NULL; } - r = router_get_by_digest(e->identity); - if (!r) { + node = node_get_by_id(e->identity); + if (!node || !node_has_descriptor(node)) { *msg = "no descriptor"; return NULL; } - if (get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_BRIDGE) { - *msg = "not a bridge"; - return NULL; - } - if (!get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_GENERAL) { - *msg = "not general-purpose"; - return NULL; + if (get_options()->UseBridges) { + if (node_get_purpose(node) != ROUTER_PURPOSE_BRIDGE) { + *msg = "not a bridge"; + return NULL; + } + } else { /* !get_options()->UseBridges */ + if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) { + *msg = "not general-purpose"; + return NULL; + } } if (options->EntryNodes && - routerset_contains_router(options->EntryNodes, r)) { + routerset_contains_node(options->EntryNodes, node)) { /* they asked for it, they get it */ need_uptime = need_capacity = 0; } - if (router_is_unreliable(r, need_uptime, need_capacity, 0)) { + if (node_is_unreliable(node, need_uptime, need_capacity, 0)) { *msg = "not fast/stable"; return NULL; } - if (!fascist_firewall_allows_or(r)) { + if (!fascist_firewall_allows_node(node)) { *msg = "unreachable by config"; return NULL; } - return r; + return node; } /** Return the number of entry guards that we think are usable. */ @@@ -3589,15 -3573,15 +3589,15 @@@ control_event_guard_deferred(void * If chosen is defined, use that one, and if it's not * already in our entry_guards list, put it at the *beginning*. * Else, put the one we pick at the end of the list. */ -static routerinfo_t * -add_an_entry_guard(routerinfo_t *chosen, int reset_status) +static const node_t * +add_an_entry_guard(const node_t *chosen, int reset_status) { - routerinfo_t *router; + const node_t *node; entry_guard_t *entry; if (chosen) { - router = chosen; - entry = is_an_entry_guard(router->cache_info.identity_digest); + node = chosen; + entry = is_an_entry_guard(node->identity); if (entry) { if (reset_status) { entry->bad_since = 0; @@@ -3606,15 -3590,14 +3606,15 @@@ return NULL; } } else { - router = choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL, NULL); - if (!router) + node = choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL, NULL); + if (!node) return NULL; } entry = tor_malloc_zero(sizeof(entry_guard_t)); - log_info(LD_CIRC, "Chose '%s' as new entry guard.", router->nickname); - strlcpy(entry->nickname, router->nickname, sizeof(entry->nickname)); - memcpy(entry->identity, router->cache_info.identity_digest, DIGEST_LEN); + log_info(LD_CIRC, "Chose '%s' as new entry guard.", + node_get_nickname(node)); + strlcpy(entry->nickname, node_get_nickname(node), sizeof(entry->nickname)); + memcpy(entry->identity, node->identity, DIGEST_LEN); /* Choose expiry time smudged over the past month. The goal here * is to a) spread out when Tor clients rotate their guards, so they * don't all select them on the same day, and b) avoid leaving a @@@ -3629,7 -3612,7 +3629,7 @@@ control_event_guard(entry->nickname, entry->identity, "NEW"); control_event_guard_deferred(); log_entry_guards(LOG_INFO); - return router; + return node; } /** If the use of entry guards is configured, choose more entry guards @@@ -3783,7 -3766,7 +3783,7 @@@ entry_guards_compute_status(or_options_ reasons = digestmap_new(); SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) { - routerinfo_t *r = router_get_by_digest(entry->identity); + const node_t *r = node_get_by_id(entry->identity); const char *reason = NULL; if (entry_guard_set_status(entry, r, now, options, &reason)) changed = 1; @@@ -3804,7 -3787,7 +3804,7 @@@ SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) { const char *reason = digestmap_get(reasons, entry->identity); const char *live_msg = ""; - routerinfo_t *r = entry_is_live(entry, 0, 1, 0, &live_msg); + const node_t *r = entry_is_live(entry, 0, 1, 0, &live_msg); log_info(LD_CIRC, "Summary: Entry '%s' is %s, %s%s%s, and %s%s.", entry->nickname, entry->unreachable_since ? "unreachable" : "reachable", @@@ -3921,7 -3904,7 +3921,7 @@@ entry_guard_register_connect_status(con break; if (e->made_contact) { const char *msg; - routerinfo_t *r = entry_is_live(e, 0, 1, 1, &msg); + const node_t *r = entry_is_live(e, 0, 1, 1, &msg); if (r && e->unreachable_since) { refuse_conn = 1; e->can_retry = 1; @@@ -3962,7 -3945,7 +3962,7 @@@ entry_nodes_should_be_added(void static void entry_guards_prepend_from_config(or_options_t *options) { - smartlist_t *entry_routers, *entry_fps; + smartlist_t *entry_nodes, *entry_fps; smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list; tor_assert(entry_guards); @@@ -3982,22 -3965,22 +3982,22 @@@ tor_free(string); } - entry_routers = smartlist_create(); + entry_nodes = smartlist_create(); entry_fps = smartlist_create(); old_entry_guards_on_list = smartlist_create(); old_entry_guards_not_on_list = smartlist_create(); /* Split entry guards into those on the list and those not. */ - /* XXXX022 Now that we allow countries and IP ranges in EntryNodes, this is - * potentially an enormous list. For now, we disable such values for - * EntryNodes in options_validate(); really, this wants a better solution. - * Perhaps we should do this calculation once whenever the list of routers - * changes or the entrynodes setting changes. - */ - routerset_get_all_routers(entry_routers, options->EntryNodes, 0); - SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, - smartlist_add(entry_fps,ri->cache_info.identity_digest)); + /* Now that we allow countries and IP ranges in EntryNodes, this is + * potentially an enormous list. It's not so bad though because we + * only call this function when a) we're making a new circuit, and b) + * we've called directory_info_has_arrived() or changed our EntryNodes + * since the last time we made a circuit. */ + routerset_get_all_nodes(entry_nodes, options->EntryNodes, 0); + SMARTLIST_FOREACH(entry_nodes, const node_t *,node, + smartlist_add(entry_fps, (void*)node->identity)); + SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, { if (smartlist_digest_isin(entry_fps, e->identity)) smartlist_add(old_entry_guards_on_list, e); @@@ -4006,9 -3989,9 +4006,9 @@@ }); /* Remove all currently configured entry guards from entry_routers. */ - SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, { - if (is_an_entry_guard(ri->cache_info.identity_digest)) { - SMARTLIST_DEL_CURRENT(entry_routers, ri); + SMARTLIST_FOREACH(entry_nodes, const node_t *, node, { + if (is_an_entry_guard(node->identity)) { + SMARTLIST_DEL_CURRENT(entry_nodes, node); } }); @@@ -4017,8 -4000,8 +4017,8 @@@ /* First, the previously configured guards that are in EntryNodes. */ smartlist_add_all(entry_guards, old_entry_guards_on_list); /* Next, the rest of EntryNodes */ - SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, { - add_an_entry_guard(ri, 0); + SMARTLIST_FOREACH(entry_nodes, const node_t *, node, { + add_an_entry_guard(node, 0); }); /* Finally, the remaining previously configured guards that are not in * EntryNodes, unless we're strict in which case we drop them */ @@@ -4029,7 -4012,7 +4029,7 @@@ smartlist_add_all(entry_guards, old_entry_guards_not_on_list); } - smartlist_free(entry_routers); + smartlist_free(entry_nodes); smartlist_free(entry_fps); smartlist_free(old_entry_guards_on_list); smartlist_free(old_entry_guards_not_on_list); @@@ -4067,21 -4050,20 +4067,21 @@@ entry_list_is_totally_static(or_options * make sure not to pick this circuit's exit or any node in the * exit's family. If state is NULL, we're looking for a random * guard (likely a bridge). */ -routerinfo_t * +const node_t * choose_random_entry(cpath_build_state_t *state) { or_options_t *options = get_options(); smartlist_t *live_entry_guards = smartlist_create(); smartlist_t *exit_family = smartlist_create(); - routerinfo_t *chosen_exit = state?build_state_get_exit_router(state) : NULL; - routerinfo_t *r = NULL; + const node_t *chosen_exit = + state?build_state_get_exit_node(state) : NULL; + const node_t *node = NULL; int need_uptime = state ? state->need_uptime : 0; int need_capacity = state ? state->need_capacity : 0; int preferred_min, consider_exit_family = 0; if (chosen_exit) { - routerlist_add_family(exit_family, chosen_exit); + nodelist_add_node_family(exit_family, chosen_exit); consider_exit_family = 1; } @@@ -4097,17 -4079,18 +4097,17 @@@ retry: smartlist_clear(live_entry_guards); - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, - { + SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) { const char *msg; - r = entry_is_live(entry, need_uptime, need_capacity, 0, &msg); - if (!r) + node = entry_is_live(entry, need_uptime, need_capacity, 0, &msg); + if (!node) continue; /* down, no point */ - if (r == chosen_exit) + if (node == chosen_exit) continue; /* don't pick the same node for entry and exit */ - if (consider_exit_family && smartlist_isin(exit_family, r)) + if (consider_exit_family && smartlist_isin(exit_family, node)) continue; /* avoid relays that are family members of our exit */ if (options->EntryNodes && - !routerset_contains_router(options->EntryNodes, r)) { + !routerset_contains_node(options->EntryNodes, node)) { /* We've come to the end of our preferred entry nodes. */ if (smartlist_len(live_entry_guards)) goto choose_and_finish; /* only choose from the ones we like */ @@@ -4120,7 -4103,7 +4120,7 @@@ "No relays from EntryNodes available. Using others."); } } - smartlist_add(live_entry_guards, r); + smartlist_add(live_entry_guards, (void*)node); if (!entry->made_contact) { /* Always start with the first not-yet-contacted entry * guard. Otherwise we might add several new ones, pick @@@ -4130,7 -4113,7 +4130,7 @@@ } if (smartlist_len(live_entry_guards) >= options->NumEntryGuards) break; /* we have enough */ - }); + } SMARTLIST_FOREACH_END(entry); if (entry_list_is_constrained(options)) { /* If we prefer the entry nodes we've got, and we have at least @@@ -4150,8 -4133,8 +4150,8 @@@ /* XXX if guard doesn't imply fast and stable, then we need * to tell add_an_entry_guard below what we want, or it might * be a long time til we get it. -RD */ - r = add_an_entry_guard(NULL, 0); - if (r) { + node = add_an_entry_guard(NULL, 0); + if (node) { entry_guards_changed(); /* XXX we start over here in case the new node we added shares * a family with our exit node. There's a chance that we'll just @@@ -4161,16 -4144,16 +4161,16 @@@ goto retry; } } - if (!r && need_uptime) { + if (!node && need_uptime) { need_uptime = 0; /* try without that requirement */ goto retry; } - if (!r && need_capacity) { + if (!node && need_capacity) { /* still no? last attempt, try without requiring capacity */ need_capacity = 0; goto retry; } - if (!r && entry_list_is_constrained(options) && consider_exit_family) { + if (!node && entry_list_is_constrained(options) && consider_exit_family) { /* still no? if we're using bridges or have strictentrynodes * set, and our chosen exit is in the same family as all our * bridges/entry guards, then be flexible about families. */ @@@ -4184,16 -4167,16 +4184,16 @@@ if (entry_list_is_constrained(options)) { /* We need to weight by bandwidth, because our bridges or entryguards * were not already selected proportional to their bandwidth. */ - r = routerlist_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD); + node = node_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD); } else { /* We choose uniformly at random here, because choose_good_entry_server() * already weights its choices by bandwidth, so we don't want to * *double*-weight our guard selection. */ - r = smartlist_choose(live_entry_guards); + node = smartlist_choose(live_entry_guards); } smartlist_free(live_entry_guards); smartlist_free(exit_family); - return r; + return node; } /** Parse state and learn about the entry guards it describes. @@@ -4440,7 -4423,7 +4440,7 @@@ getinfo_helper_entry_guards(control_con char *c = tor_malloc(len); const char *status = NULL; time_t when = 0; - routerinfo_t *ri; + const node_t *node; if (!e->made_contact) { status = "never-connected"; @@@ -4451,9 -4434,9 +4451,9 @@@ status = "up"; } - ri = router_get_by_digest(e->identity); - if (ri) { - router_get_verbose_nickname(nbuf, ri); + node = node_get_by_id(e->identity); + if (node) { + node_get_verbose_nickname(node, nbuf); } else { nbuf[0] = '$'; base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN); @@@ -4530,7 -4513,7 +4530,7 @@@ get_configured_bridge_by_addr_port_dige /** Wrapper around get_configured_bridge_by_addr_port_digest() to look * it up via router descriptor ri. */ static bridge_info_t * -get_configured_bridge_by_routerinfo(routerinfo_t *ri) +get_configured_bridge_by_routerinfo(const routerinfo_t *ri) { tor_addr_t addr; tor_addr_from_ipv4h(&addr, ri->addr); @@@ -4540,7 -4523,7 +4540,7 @@@ /** Return 1 if ri is one of our known bridges, else 0. */ int -routerinfo_is_a_configured_bridge(routerinfo_t *ri) +routerinfo_is_a_configured_bridge(const routerinfo_t *ri) { return get_configured_bridge_by_routerinfo(ri) ? 1 : 0; } @@@ -4699,17 -4682,14 +4699,17 @@@ learned_bridge_descriptor(routerinfo_t int first = !any_bridge_descriptors_known(); bridge_info_t *bridge = get_configured_bridge_by_routerinfo(ri); time_t now = time(NULL); - ri->is_running = 1; + router_set_status(ri->cache_info.identity_digest, 1); if (bridge) { /* if we actually want to use this one */ + const node_t *node; /* it's here; schedule its re-fetch for a long time from now. */ if (!from_cache) download_status_reset(&bridge->fetch_status); - add_an_entry_guard(ri, 1); + node = node_get_by_id(ri->cache_info.identity_digest); + tor_assert(node); + add_an_entry_guard(node, 1); log_notice(LD_DIR, "new bridge descriptor '%s' (%s)", ri->nickname, from_cache ? "cached" : "fresh"); /* set entry->made_contact so if it goes down we don't drop it from @@@ -4748,7 -4728,8 +4748,8 @@@ any_pending_bridge_descriptor_fetches(v conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC && TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE && !conn->marked_for_close && - conn->linked && !conn->linked_conn->marked_for_close) { + conn->linked && + conn->linked_conn && !conn->linked_conn->marked_for_close) { log_debug(LD_DIR, "found one: %s", conn->address); return 1; } @@@ -4763,18 -4744,19 +4764,18 @@@ static int entries_retry_helper(or_options_t *options, int act) { - routerinfo_t *ri; + const node_t *node; int any_known = 0; int any_running = 0; - int purpose = options->UseBridges ? - ROUTER_PURPOSE_BRIDGE : ROUTER_PURPOSE_GENERAL; + int need_bridges = options->UseBridges != 0; if (!entry_guards) entry_guards = smartlist_create(); - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, - { - ri = router_get_by_digest(e->identity); - if (ri && ri->purpose == purpose) { + SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) { + node = node_get_by_id(e->identity); + if (node && node_has_descriptor(node) && + node_is_bridge(node) == need_bridges) { any_known = 1; - if (ri->is_running) + if (node->is_running) any_running = 1; /* some entry is both known and running */ else if (act) { /* Mark all current connections to this OR as unhealthy, since @@@ -4783,15 -4765,15 +4784,15 @@@ * the node down and undermine the retry attempt. We mark even * the established conns, since if the network just came back * we'll want to attach circuits to fresh conns. */ - connection_or_set_bad_connections(ri->cache_info.identity_digest, 1); + connection_or_set_bad_connections(node->identity, 1); /* mark this entry node for retry */ - router_set_status(ri->cache_info.identity_digest, 1); + router_set_status(node->identity, 1); e->can_retry = 1; e->bad_since = 0; } } - }); + } SMARTLIST_FOREACH_END(e); log_debug(LD_DIR, "%d: any_known %d, any_running %d", act, any_known, any_running); return any_known && !any_running;

1 0

[tor/master] Merge remote branch 'origin/maint-0.2.1' into maint-0.2.2
by nickm＠torproject.org 08 Mar '11

08 Mar '11

commit 9ad083d5731c983ea3e961822306c50ce32dfcc2 Merge: 95edd51 9a6df21 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 8 15:20:48 2011 -0500 Merge remote branch 'origin/maint-0.2.1' into maint-0.2.2 changes/bug2629 | 5 +++++ src/or/circuitbuild.c | 3 ++- 2 files changed, 7 insertions(+), 1 deletions(-) diff --combined src/or/circuitbuild.c index b3c9f0e,76713e6..6be27d2 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@@ -9,1437 -9,55 +9,1437 @@@ * \brief The actual details of building circuits. **/ +#define CIRCUIT_PRIVATE + #include "or.h" +#include "circuitbuild.h" +#include "circuitlist.h" +#include "circuituse.h" +#include "config.h" +#include "connection.h" +#include "connection_edge.h" +#include "connection_or.h" +#include "control.h" +#include "directory.h" +#include "main.h" +#include "networkstatus.h" +#include "onion.h" +#include "policies.h" +#include "relay.h" +#include "rephist.h" +#include "router.h" +#include "routerlist.h" +#include "routerparse.h" +#include "crypto.h" +#undef log +#include <math.h> + +#ifndef MIN +#define MIN(a,b) ((a)<(b)?(a):(b)) +#endif + +#define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2)) + +/********* START VARIABLES **********/ +/** Global list of circuit build times */ +// FIXME: Add this as a member for entry_guard_t instead of global? +// Then we could do per-guard statistics, as guards are likely to +// vary in their own latency. The downside of this is that guards +// can change frequently, so we'd be building a lot more circuits +// most likely. +circuit_build_times_t circ_times; + +/** A global list of all circuits at this hop. */ +extern circuit_t *global_circuitlist; + +/** An entry_guard_t represents our information about a chosen long-term + * first hop, known as a "helper" node in the literature. We can't just + * use a routerinfo_t, since we want to remember these even when we + * don't have a directory. */ +typedef struct { + char nickname[MAX_NICKNAME_LEN+1]; + char identity[DIGEST_LEN]; + time_t chosen_on_date; /**< Approximately when was this guard added? + * "0" if we don't know. */ + char *chosen_by_version; /**< What tor version added this guard? NULL + * if we don't know. */ + unsigned int made_contact : 1; /**< 0 if we have never connected to this + * router, 1 if we have. */ + unsigned int can_retry : 1; /**< Should we retry connecting to this entry, + * in spite of having it marked as unreachable?*/ + time_t bad_since; /**< 0 if this guard is currently usable, or the time at + * which it was observed to become (according to the + * directory or the user configuration) unusable. */ + time_t unreachable_since; /**< 0 if we can connect to this guard, or the + * time at which we first noticed we couldn't + * connect to it. */ + time_t last_attempted; /**< 0 if we can connect to this guard, or the time + * at which we last failed to connect to it. */ +} entry_guard_t; + +/** A list of our chosen entry guards. */ +static smartlist_t *entry_guards = NULL; +/** A value of 1 means that the entry_guards list has changed + * and those changes need to be flushed to disk. */ +static int entry_guards_dirty = 0; + +/** If set, we're running the unit tests: we should avoid clobbering + * our state file or accessing get_options() or get_or_state() */ +static int unit_tests = 0; + +/********* END VARIABLES ************/ + +static int circuit_deliver_create_cell(circuit_t *circ, + uint8_t cell_type, const char *payload); +static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit); +static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath); +static int onion_extend_cpath(origin_circuit_t *circ); +static int count_acceptable_routers(smartlist_t *routers); +static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice); + +static void entry_guards_changed(void); + +/** + * This function decides if CBT learning should be disabled. It returns + * true if one or more of the following four conditions are met: + * + * 1. If the cbtdisabled consensus parameter is set. + * 2. If the torrc option LearnCircuitBuildTimeout is false. + * 3. If we are a directory authority + * 4. If we fail to write circuit build time history to our state file. + */ +static int +circuit_build_times_disabled(void) +{ + if (unit_tests) { + return 0; + } else { + int consensus_disabled = networkstatus_get_param(NULL, "cbtdisabled", + 0, 0, 1); + int config_disabled = !get_options()->LearnCircuitBuildTimeout; + int dirauth_disabled = get_options()->AuthoritativeDir; + int state_disabled = (get_or_state()->LastWritten == -1); + + if (consensus_disabled || config_disabled || dirauth_disabled || + state_disabled) { + log_info(LD_CIRC, + "CircuitBuildTime learning is disabled. " + "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d", + consensus_disabled, config_disabled, dirauth_disabled, + state_disabled); + return 1; + } else { + return 0; + } + } +} + +/** + * Retrieve and bounds-check the cbtmaxtimeouts consensus paramter. + * + * Effect: When this many timeouts happen in the last 'cbtrecentcount' + * circuit attempts, the client should discard all of its history and + * begin learning a fresh timeout value. + */ +static int32_t +circuit_build_times_max_timeouts(void) +{ + return networkstatus_get_param(NULL, "cbtmaxtimeouts", + CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT, + CBT_MIN_MAX_RECENT_TIMEOUT_COUNT, + CBT_MAX_MAX_RECENT_TIMEOUT_COUNT); +} + +/** + * Retrieve and bounds-check the cbtnummodes consensus paramter. + * + * Effect: This value governs how many modes to use in the weighted + * average calculation of Pareto parameter Xm. A value of 3 introduces + * some bias (2-5% of CDF) under ideal conditions, but allows for better + * performance in the event that a client chooses guard nodes of radically + * different performance characteristics. + */ +static int32_t +circuit_build_times_default_num_xm_modes(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbtnummodes", + CBT_DEFAULT_NUM_XM_MODES, + CBT_MIN_NUM_XM_MODES, + CBT_MAX_NUM_XM_MODES); + return num; +} + +/** + * Retrieve and bounds-check the cbtmincircs consensus paramter. + * + * Effect: This is the minimum number of circuits to build before + * computing a timeout. + */ +static int32_t +circuit_build_times_min_circs_to_observe(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbtmincircs", + CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE, + CBT_MIN_MIN_CIRCUITS_TO_OBSERVE, + CBT_MAX_MIN_CIRCUITS_TO_OBSERVE); + return num; +} + +/** Return true iff cbt has recorded enough build times that we + * want to start acting on the timeout it implies. */ +int +circuit_build_times_enough_to_compute(circuit_build_times_t *cbt) +{ + return cbt->total_build_times >= circuit_build_times_min_circs_to_observe(); +} + +/** + * Retrieve and bounds-check the cbtquantile consensus paramter. + * + * Effect: This is the position on the quantile curve to use to set the + * timeout value. It is a percent (10-99). + */ +double +circuit_build_times_quantile_cutoff(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbtquantile", + CBT_DEFAULT_QUANTILE_CUTOFF, + CBT_MIN_QUANTILE_CUTOFF, + CBT_MAX_QUANTILE_CUTOFF); + return num/100.0; +} + +int +circuit_build_times_get_bw_scale(networkstatus_t *ns) +{ + return networkstatus_get_param(ns, "bwweightscale", + BW_WEIGHT_SCALE, + BW_MIN_WEIGHT_SCALE, + BW_MAX_WEIGHT_SCALE); +} + +/** + * Retrieve and bounds-check the cbtclosequantile consensus paramter. + * + * Effect: This is the position on the quantile curve to use to set the + * timeout value to use to actually close circuits. It is a percent + * (0-99). + */ +static double +circuit_build_times_close_quantile(void) +{ + int32_t param; + /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */ + int32_t min = (int)tor_lround(100*circuit_build_times_quantile_cutoff()); + param = networkstatus_get_param(NULL, "cbtclosequantile", + CBT_DEFAULT_CLOSE_QUANTILE, + CBT_MIN_CLOSE_QUANTILE, + CBT_MAX_CLOSE_QUANTILE); + if (param < min) { + log_warn(LD_DIR, "Consensus parameter cbtclosequantile is " + "too small, raising to %d", min); + param = min; + } + return param / 100.0; +} + +/** + * Retrieve and bounds-check the cbttestfreq consensus paramter. + * + * Effect: Describes how often in seconds to build a test circuit to + * gather timeout values. Only applies if less than 'cbtmincircs' + * have been recorded. + */ +static int32_t +circuit_build_times_test_frequency(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbttestfreq", + CBT_DEFAULT_TEST_FREQUENCY, + CBT_MIN_TEST_FREQUENCY, + CBT_MAX_TEST_FREQUENCY); + return num; +} + +/** + * Retrieve and bounds-check the cbtmintimeout consensus paramter. + * + * Effect: This is the minimum allowed timeout value in milliseconds. + * The minimum is to prevent rounding to 0 (we only check once + * per second). + */ +static int32_t +circuit_build_times_min_timeout(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbtmintimeout", + CBT_DEFAULT_TIMEOUT_MIN_VALUE, + CBT_MIN_TIMEOUT_MIN_VALUE, + CBT_MAX_TIMEOUT_MIN_VALUE); + return num; +} + +/** + * Retrieve and bounds-check the cbtinitialtimeout consensus paramter. + * + * Effect: This is the timeout value to use before computing a timeout, + * in milliseconds. + */ +int32_t +circuit_build_times_initial_timeout(void) +{ + int32_t min = circuit_build_times_min_timeout(); + int32_t param = networkstatus_get_param(NULL, "cbtinitialtimeout", + CBT_DEFAULT_TIMEOUT_INITIAL_VALUE, + CBT_MIN_TIMEOUT_INITIAL_VALUE, + CBT_MAX_TIMEOUT_INITIAL_VALUE); + if (param < min) { + log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, " + "raising to %d", min); + param = min; + } + return param; +} + +/** + * Retrieve and bounds-check the cbtrecentcount consensus paramter. + * + * Effect: This is the number of circuit build times to keep track of + * for deciding if we hit cbtmaxtimeouts and need to reset our state + * and learn a new timeout. + */ +static int32_t +circuit_build_times_recent_circuit_count(networkstatus_t *ns) +{ + return networkstatus_get_param(ns, "cbtrecentcount", + CBT_DEFAULT_RECENT_CIRCUITS, + CBT_MIN_RECENT_CIRCUITS, + CBT_MAX_RECENT_CIRCUITS); +} + +/** + * This function is called when we get a consensus update. + * + * It checks to see if we have changed any consensus parameters + * that require reallocation or discard of previous stats. + */ +void +circuit_build_times_new_consensus_params(circuit_build_times_t *cbt, + networkstatus_t *ns) +{ + int32_t num = circuit_build_times_recent_circuit_count(ns); + + if (num > 0 && num != cbt->liveness.num_recent_circs) { + int8_t *recent_circs; + log_notice(LD_CIRC, "The Tor Directory Consensus has changed how many " + "circuits we must track to detect network failures from %d " + "to %d.", cbt->liveness.num_recent_circs, num); + + tor_assert(cbt->liveness.timeouts_after_firsthop); + + /* + * Technically this is a circular array that we are reallocating + * and memcopying. However, since it only consists of either 1s + * or 0s, and is only used in a statistical test to determine when + * we should discard our history after a sufficient number of 1's + * have been reached, it is fine if order is not preserved or + * elements are lost. + * + * cbtrecentcount should only be changing in cases of severe network + * distress anyway, so memory correctness here is paramount over + * doing acrobatics to preserve the array. + */ + recent_circs = tor_malloc_zero(sizeof(int8_t)*num); + memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop, + sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs)); + + // Adjust the index if it needs it. + if (num < cbt->liveness.num_recent_circs) { + cbt->liveness.after_firsthop_idx = MIN(num-1, + cbt->liveness.after_firsthop_idx); + } + + tor_free(cbt->liveness.timeouts_after_firsthop); + cbt->liveness.timeouts_after_firsthop = recent_circs; + cbt->liveness.num_recent_circs = num; + } +} + +/** Make a note that we're running unit tests (rather than running Tor + * itself), so we avoid clobbering our state file. */ +void +circuitbuild_running_unit_tests(void) +{ + unit_tests = 1; +} + +/** + * Return the initial default or configured timeout in milliseconds + */ +static double +circuit_build_times_get_initial_timeout(void) +{ + double timeout; + if (!unit_tests && get_options()->CircuitBuildTimeout) { + timeout = get_options()->CircuitBuildTimeout*1000; + if (timeout < circuit_build_times_min_timeout()) { + log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds", + circuit_build_times_min_timeout()/1000); + timeout = circuit_build_times_min_timeout(); + } + } else { + timeout = circuit_build_times_initial_timeout(); + } + return timeout; +} + +/** + * Reset the build time state. + * + * Leave estimated parameters, timeout and network liveness intact + * for future use. + */ +void +circuit_build_times_reset(circuit_build_times_t *cbt) +{ + memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times)); + cbt->total_build_times = 0; + cbt->build_times_idx = 0; + cbt->have_computed_timeout = 0; +} + +/** + * Initialize the buildtimes structure for first use. + * + * Sets the initial timeout values based on either the config setting, + * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE). + */ +void +circuit_build_times_init(circuit_build_times_t *cbt) +{ + memset(cbt, 0, sizeof(*cbt)); + cbt->liveness.num_recent_circs = + circuit_build_times_recent_circuit_count(NULL); + cbt->liveness.timeouts_after_firsthop = tor_malloc_zero(sizeof(int8_t)* + cbt->liveness.num_recent_circs); + cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout(); + control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET); +} + +#if 0 +/** + * Rewind our build time history by n positions. + */ +static void +circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n) +{ + int i = 0; + + cbt->build_times_idx -= n; + cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE; + + for (i = 0; i < n; i++) { + cbt->circuit_build_times[(i+cbt->build_times_idx) + %CBT_NCIRCUITS_TO_OBSERVE]=0; + } + + if (cbt->total_build_times > n) { + cbt->total_build_times -= n; + } else { + cbt->total_build_times = 0; + } + + log_info(LD_CIRC, + "Rewound history by %d places. Current index: %d. " + "Total: %d", n, cbt->build_times_idx, cbt->total_build_times); +} +#endif + +/** + * Add a new build time value time to the set of build times. Time + * units are milliseconds. + * + * circuit_build_times cbt</a> is a circular array, so loop around when + * array is full. + */ +int +circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time) +{ + if (time <= 0 || time > CBT_BUILD_TIME_MAX) { + log_warn(LD_BUG, "Circuit build time is too large (%u)." + "This is probably a bug.", time); + tor_fragile_assert(); + return -1; + } + + log_debug(LD_CIRC, "Adding circuit build time %u", time); + + cbt->circuit_build_times[cbt->build_times_idx] = time; + cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE; + if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE) + cbt->total_build_times++; + + if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) { + /* Save state every n circuit builds */ + if (!unit_tests && !get_options()->AvoidDiskWrites) + or_state_mark_dirty(get_or_state(), 0); + } + + return 0; +} + +/** + * Return maximum circuit build time + */ +static build_time_t +circuit_build_times_max(circuit_build_times_t *cbt) +{ + int i = 0; + build_time_t max_build_time = 0; + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] > max_build_time + && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED) + max_build_time = cbt->circuit_build_times[i]; + } + return max_build_time; +} + +#if 0 +/** Return minimum circuit build time */ +build_time_t +circuit_build_times_min(circuit_build_times_t *cbt) +{ + int i = 0; + build_time_t min_build_time = CBT_BUILD_TIME_MAX; + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */ + cbt->circuit_build_times[i] < min_build_time) + min_build_time = cbt->circuit_build_times[i]; + } + if (min_build_time == CBT_BUILD_TIME_MAX) { + log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!"); + } + return min_build_time; +} +#endif + +/** + * Calculate and return a histogram for the set of build times. + * + * Returns an allocated array of histrogram bins representing + * the frequency of index*CBT_BIN_WIDTH millisecond + * build times. Also outputs the number of bins in nbins. + * + * The return value must be freed by the caller. + */ +static uint32_t * +circuit_build_times_create_histogram(circuit_build_times_t *cbt, + build_time_t *nbins) +{ + uint32_t *histogram; + build_time_t max_build_time = circuit_build_times_max(cbt); + int i, c; + + *nbins = 1 + (max_build_time / CBT_BIN_WIDTH); + histogram = tor_malloc_zero(*nbins * sizeof(build_time_t)); + + // calculate histogram + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] == 0 + || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) + continue; /* 0 <-> uninitialized */ + + c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH); + histogram[c]++; + } + + return histogram; +} + +/** + * Return the Pareto start-of-curve parameter Xm. + * + * Because we are not a true Pareto curve, we compute this as the + * weighted average of the N=3 most frequent build time bins. + */ +static build_time_t +circuit_build_times_get_xm(circuit_build_times_t *cbt) +{ + build_time_t i, nbins; + build_time_t *nth_max_bin; + int32_t bin_counts=0; + build_time_t ret = 0; + uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins); + int n=0; + int num_modes = circuit_build_times_default_num_xm_modes(); + + // Only use one mode if < 1000 buildtimes. Not enough data + // for multiple. + if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE) + num_modes = 1; + + nth_max_bin = (build_time_t*)tor_malloc_zero(num_modes*sizeof(build_time_t)); + + for (i = 0; i < nbins; i++) { + if (histogram[i] >= histogram[nth_max_bin[0]]) { + nth_max_bin[0] = i; + } + + for (n = 1; n < num_modes; n++) { + if (histogram[i] >= histogram[nth_max_bin[n]] && + (!histogram[nth_max_bin[n-1]] + || histogram[i] < histogram[nth_max_bin[n-1]])) { + nth_max_bin[n] = i; + } + } + } + + for (n = 0; n < num_modes; n++) { + bin_counts += histogram[nth_max_bin[n]]; + ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]]; + log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]), + histogram[nth_max_bin[n]]); + } + + ret /= bin_counts; + tor_free(histogram); + tor_free(nth_max_bin); + + return ret; +} + +/** + * Output a histogram of current circuit build times to + * the or_state_t state structure. + */ +void +circuit_build_times_update_state(circuit_build_times_t *cbt, + or_state_t *state) +{ + uint32_t *histogram; + build_time_t i = 0; + build_time_t nbins = 0; + config_line_t **next, *line; + + histogram = circuit_build_times_create_histogram(cbt, &nbins); + // write to state + config_free_lines(state->BuildtimeHistogram); + next = &state->BuildtimeHistogram; + *next = NULL; + + state->TotalBuildTimes = cbt->total_build_times; + state->CircuitBuildAbandonedCount = 0; + + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) + state->CircuitBuildAbandonedCount++; + } + + for (i = 0; i < nbins; i++) { + // compress the histogram by skipping the blanks + if (histogram[i] == 0) continue; + *next = line = tor_malloc_zero(sizeof(config_line_t)); + line->key = tor_strdup("CircuitBuildTimeBin"); + line->value = tor_malloc(25); + tor_snprintf(line->value, 25, "%d %d", + CBT_BIN_TO_MS(i), histogram[i]); + next = &(line->next); + } + + if (!unit_tests) { + if (!get_options()->AvoidDiskWrites) + or_state_mark_dirty(get_or_state(), 0); + } + + tor_free(histogram); +} + +/** + * Shuffle the build times array. + * + * Stolen from http://en.wikipedia.org/wiki/Fisher\u2013Yates_shuffle + */ +static void +circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt, + build_time_t *raw_times, + uint32_t num_times) +{ + uint32_t n = num_times; + if (num_times > CBT_NCIRCUITS_TO_OBSERVE) { + log_notice(LD_CIRC, "The number of circuit times that this Tor version " + "uses to calculate build times is less than the number stored " + "in your state file. Decreasing the circuit time history from " + "%d to %d.", num_times, CBT_NCIRCUITS_TO_OBSERVE); + } + + /* This code can only be run on a compact array */ + while (n-- > 1) { + int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */ + build_time_t tmp = raw_times[k]; + raw_times[k] = raw_times[n]; + raw_times[n] = tmp; + } + + /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE + * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */ + for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) { + circuit_build_times_add_time(cbt, raw_times[n]); + } +} + +/** + * Filter old synthetic timeouts that were created before the + * new right-censored Pareto calculation was deployed. + * + * Once all clients before 0.2.1.13-alpha are gone, this code + * will be unused. + */ +static int +circuit_build_times_filter_timeouts(circuit_build_times_t *cbt) +{ + int num_filtered=0, i=0; + double timeout_rate = 0; + build_time_t max_timeout = 0; + + timeout_rate = circuit_build_times_timeout_rate(cbt); + max_timeout = (build_time_t)cbt->close_ms; + + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] > max_timeout) { + build_time_t replaced = cbt->circuit_build_times[i]; + num_filtered++; + cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED; + + log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced, + cbt->circuit_build_times[i]); + } + } + + log_info(LD_CIRC, + "We had %d timeouts out of %d build times, " + "and filtered %d above the max of %u", + (int)(cbt->total_build_times*timeout_rate), + cbt->total_build_times, num_filtered, max_timeout); + + return num_filtered; +} + +/** + * Load histogram from state, shuffling the resulting array + * after we do so. Use this result to estimate parameters and + * calculate the timeout. + * + * Return -1 on error. + */ +int +circuit_build_times_parse_state(circuit_build_times_t *cbt, + or_state_t *state) +{ + int tot_values = 0; + uint32_t loaded_cnt = 0, N = 0; + config_line_t *line; + unsigned int i; + build_time_t *loaded_times; + int err = 0; + circuit_build_times_init(cbt); + + if (circuit_build_times_disabled()) { + return 0; + } + + /* build_time_t 0 means uninitialized */ + loaded_times = tor_malloc_zero(sizeof(build_time_t)*state->TotalBuildTimes); + + for (line = state->BuildtimeHistogram; line; line = line->next) { + smartlist_t *args = smartlist_create(); + smartlist_split_string(args, line->value, " ", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + if (smartlist_len(args) < 2) { + log_warn(LD_GENERAL, "Unable to parse circuit build times: " + "Too few arguments to CircuitBuildTime"); + err = 1; + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + break; + } else { + const char *ms_str = smartlist_get(args,0); + const char *count_str = smartlist_get(args,1); + uint32_t count, k; + build_time_t ms; + int ok; + ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0, + CBT_BUILD_TIME_MAX, &ok, NULL); + if (!ok) { + log_warn(LD_GENERAL, "Unable to parse circuit build times: " + "Unparsable bin number"); + err = 1; + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + break; + } + count = (uint32_t)tor_parse_ulong(count_str, 0, 0, + UINT32_MAX, &ok, NULL); + if (!ok) { + log_warn(LD_GENERAL, "Unable to parse circuit build times: " + "Unparsable bin count"); + err = 1; + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + break; + } + + if (loaded_cnt+count+state->CircuitBuildAbandonedCount + > state->TotalBuildTimes) { + log_warn(LD_CIRC, + "Too many build times in state file. " + "Stopping short before %d", + loaded_cnt+count); + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + break; + } + + for (k = 0; k < count; k++) { + loaded_times[loaded_cnt++] = ms; + } + N++; + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + } + } + + log_info(LD_CIRC, + "Adding %d timeouts.", state->CircuitBuildAbandonedCount); + for (i=0; i < state->CircuitBuildAbandonedCount; i++) { + loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED; + } + + if (loaded_cnt != state->TotalBuildTimes) { + log_warn(LD_CIRC, + "Corrupt state file? Build times count mismatch. " + "Read %d times, but file says %d", loaded_cnt, + state->TotalBuildTimes); + err = 1; + circuit_build_times_reset(cbt); + goto done; + } + + circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt); + + /* Verify that we didn't overwrite any indexes */ + for (i=0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (!cbt->circuit_build_times[i]) + break; + tot_values++; + } + log_info(LD_CIRC, + "Loaded %d/%d values from %d lines in circuit time histogram", + tot_values, cbt->total_build_times, N); + + if (cbt->total_build_times != tot_values + || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) { + log_warn(LD_CIRC, + "Corrupt state file? Shuffled build times mismatch. " + "Read %d times, but file says %d", tot_values, + state->TotalBuildTimes); + err = 1; + circuit_build_times_reset(cbt); + goto done; + } + + circuit_build_times_set_timeout(cbt); + + if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) { + circuit_build_times_filter_timeouts(cbt); + } + + done: + tor_free(loaded_times); + return err ? -1 : 0; +} + +/** + * Estimates the Xm and Alpha parameters using + * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation + * + * The notable difference is that we use mode instead of min to estimate Xm. + * This is because our distribution is frechet-like. We claim this is + * an acceptable approximation because we are only concerned with the + * accuracy of the CDF of the tail. + */ +int +circuit_build_times_update_alpha(circuit_build_times_t *cbt) +{ + build_time_t *x=cbt->circuit_build_times; + double a = 0; + int n=0,i=0,abandoned_count=0; + build_time_t max_time=0; + + /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */ + /* We sort of cheat here and make our samples slightly more pareto-like + * and less frechet-like. */ + cbt->Xm = circuit_build_times_get_xm(cbt); + + tor_assert(cbt->Xm > 0); + + for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (!x[i]) { + continue; + } + + if (x[i] < cbt->Xm) { + a += tor_mathlog(cbt->Xm); + } else if (x[i] == CBT_BUILD_ABANDONED) { + abandoned_count++; + } else { + a += tor_mathlog(x[i]); + if (x[i] > max_time) + max_time = x[i]; + } + n++; + } + + /* + * We are erring and asserting here because this can only happen + * in codepaths other than startup. The startup state parsing code + * performs this same check, and resets state if it hits it. If we + * hit it at runtime, something serious has gone wrong. + */ + if (n!=cbt->total_build_times) { + log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n, + cbt->total_build_times); + } + tor_assert(n==cbt->total_build_times); + + if (max_time <= 0) { + /* This can happen if Xm is actually the *maximum* value in the set. + * It can also happen if we've abandoned every single circuit somehow. + * In either case, tell the caller not to compute a new build timeout. */ + log_warn(LD_BUG, + "Could not determine largest build time (%d). " + "Xm is %dms and we've abandoned %d out of %d circuits.", max_time, + cbt->Xm, abandoned_count, n); + return 0; + } + + a += abandoned_count*tor_mathlog(max_time); + + a -= n*tor_mathlog(cbt->Xm); + // Estimator comes from Eq #4 in: + // "Bayesian estimation based on trimmed samples from Pareto populations" + // by Arturo J. Fernández. We are right-censored only. + a = (n-abandoned_count)/a; + + cbt->alpha = a; + + return 1; +} + +/** + * This is the Pareto Quantile Function. It calculates the point x + * in the distribution such that F(x) = quantile (ie quantile*100% + * of the mass of the density function is below x on the curve). + * + * We use it to calculate the timeout and also to generate synthetic + * values of time for circuits that timeout before completion. + * + * See http://en.wikipedia.org/wiki/Quantile_function, + * http://en.wikipedia.org/wiki/Inverse_transform_sampling and + * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_ + * random_sample_from_Pareto_distribution + * That's right. I'll cite wikipedia all day long. + * + * Return value is in milliseconds. + */ +double +circuit_build_times_calculate_timeout(circuit_build_times_t *cbt, + double quantile) +{ + double ret; + tor_assert(quantile >= 0); + tor_assert(1.0-quantile > 0); + tor_assert(cbt->Xm > 0); + + ret = cbt->Xm/pow(1.0-quantile,1.0/cbt->alpha); + if (ret > INT32_MAX) { + ret = INT32_MAX; + } + tor_assert(ret > 0); + return ret; +} + +/** Pareto CDF */ +double +circuit_build_times_cdf(circuit_build_times_t *cbt, double x) +{ + double ret; + tor_assert(cbt->Xm > 0); + ret = 1.0-pow(cbt->Xm/x,cbt->alpha); + tor_assert(0 <= ret && ret <= 1.0); + return ret; +} + +/** + * Generate a synthetic time using our distribution parameters. + * + * The return value will be within the [q_lo, q_hi) quantile points + * on the CDF. + */ +build_time_t +circuit_build_times_generate_sample(circuit_build_times_t *cbt, + double q_lo, double q_hi) +{ + double randval = crypto_rand_double(); + build_time_t ret; + double u; + + /* Generate between [q_lo, q_hi) */ + /*XXXX This is what nextafter is supposed to be for; we should use it on the + * platforms that support it. */ + q_hi -= 1.0/(INT32_MAX); + + tor_assert(q_lo >= 0); + tor_assert(q_hi < 1); + tor_assert(q_lo < q_hi); + + u = q_lo + (q_hi-q_lo)*randval; + + tor_assert(0 <= u && u < 1.0); + /* circuit_build_times_calculate_timeout returns <= INT32_MAX */ + ret = (build_time_t) + tor_lround(circuit_build_times_calculate_timeout(cbt, u)); + tor_assert(ret > 0); + return ret; +} + +/** + * Estimate an initial alpha parameter by solving the quantile + * function with a quantile point and a specific timeout value. + */ +void +circuit_build_times_initial_alpha(circuit_build_times_t *cbt, + double quantile, double timeout_ms) +{ + // Q(u) = Xm/((1-u)^(1/a)) + // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout + // CircBuildTimeout = Xm/((1-0.8))^(1/a)) + // CircBuildTimeout = Xm*((1-0.8))^(-1/a)) + // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a) + // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a + tor_assert(quantile >= 0); + tor_assert(cbt->Xm > 0); + cbt->alpha = tor_mathlog(1.0-quantile)/ + (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms)); + tor_assert(cbt->alpha > 0); +} + +/** + * Returns true if we need circuits to be built + */ +int +circuit_build_times_needs_circuits(circuit_build_times_t *cbt) +{ + /* Return true if < MIN_CIRCUITS_TO_OBSERVE */ + return !circuit_build_times_enough_to_compute(cbt); +} + +/** + * Returns true if we should build a timeout test circuit + * right now. + */ +int +circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt) +{ + return circuit_build_times_needs_circuits(cbt) && + approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency(); +} + +/** + * Called to indicate that the network showed some signs of liveness, + * i.e. we received a cell. + * + * This is used by circuit_build_times_network_check_live() to decide + * if we should record the circuit build timeout or not. + * + * This function is called every time we receive a cell. Avoid + * syscalls, events, and other high-intensity work. + */ +void +circuit_build_times_network_is_live(circuit_build_times_t *cbt) +{ + time_t now = approx_time(); + if (cbt->liveness.nonlive_timeouts > 0) { + log_notice(LD_CIRC, + "Tor now sees network activity. Restoring circuit build " + "timeout recording. Network was down for %d seconds " + "during %d circuit attempts.", + (int)(now - cbt->liveness.network_last_live), + cbt->liveness.nonlive_timeouts); + } + cbt->liveness.network_last_live = now; + cbt->liveness.nonlive_timeouts = 0; +} + +/** + * Called to indicate that we completed a circuit. Because this circuit + * succeeded, it doesn't count as a timeout-after-the-first-hop. + * + * This is used by circuit_build_times_network_check_changed() to determine + * if we had too many recent timeouts and need to reset our learned timeout + * to something higher. + */ +void +circuit_build_times_network_circ_success(circuit_build_times_t *cbt) +{ + cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx] = 0; + cbt->liveness.after_firsthop_idx++; + cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs; +} + +/** + * A circuit just timed out. If it failed after the first hop, record it + * in our history for later deciding if the network speed has changed. + * + * This is used by circuit_build_times_network_check_changed() to determine + * if we had too many recent timeouts and need to reset our learned timeout + * to something higher. + */ +static void +circuit_build_times_network_timeout(circuit_build_times_t *cbt, + int did_onehop) +{ + if (did_onehop) { + cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]=1; + cbt->liveness.after_firsthop_idx++; + cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs; + } +} -/********* START VARIABLES **********/ +/** + * A circuit was just forcibly closed. If there has been no recent network + * activity at all, but this circuit was launched back when we thought the + * network was live, increment the number of "nonlive" circuit timeouts. + * + * This is used by circuit_build_times_network_check_live() to decide + * if we should record the circuit build timeout or not. + */ +static void +circuit_build_times_network_close(circuit_build_times_t *cbt, + int did_onehop, time_t start_time) +{ + time_t now = time(NULL); + /* + * Check if this is a timeout that was for a circuit that spent its + * entire existence during a time where we have had no network activity. + */ + if (cbt->liveness.network_last_live < start_time) { + if (did_onehop) { + char last_live_buf[ISO_TIME_LEN+1]; + char start_time_buf[ISO_TIME_LEN+1]; + char now_buf[ISO_TIME_LEN+1]; + format_local_iso_time(last_live_buf, cbt->liveness.network_last_live); + format_local_iso_time(start_time_buf, start_time); + format_local_iso_time(now_buf, now); + log_warn(LD_BUG, + "Circuit somehow completed a hop while the network was " + "not live. Network was last live at %s, but circuit launched " + "at %s. It's now %s.", last_live_buf, start_time_buf, + now_buf); + } + cbt->liveness.nonlive_timeouts++; + if (cbt->liveness.nonlive_timeouts == 1) { + log_notice(LD_CIRC, + "Tor has not observed any network activity for the past %d " + "seconds. Disabling circuit build timeout recording.", + (int)(now - cbt->liveness.network_last_live)); + } else { + log_info(LD_CIRC, + "Got non-live timeout. Current count is: %d", + cbt->liveness.nonlive_timeouts); + } + } +} -/** A global list of all circuits at this hop. */ -extern circuit_t *global_circuitlist; +/** + * When the network is not live, we do not record circuit build times. + * + * The network is considered not live if there has been at least one + * circuit build that began and ended (had its close_ms measurement + * period expire) since we last received a cell. + * + * Also has the side effect of rewinding the circuit time history + * in the case of recent liveness changes. + */ +int +circuit_build_times_network_check_live(circuit_build_times_t *cbt) +{ + if (cbt->liveness.nonlive_timeouts > 0) { + return 0; + } -/** An entry_guard_t represents our information about a chosen long-term - * first hop, known as a "helper" node in the literature. We can't just - * use a routerinfo_t, since we want to remember these even when we - * don't have a directory. */ -typedef struct { - char nickname[MAX_NICKNAME_LEN+1]; - char identity[DIGEST_LEN]; - time_t chosen_on_date; /**< Approximately when was this guard added? - * "0" if we don't know. */ - char *chosen_by_version; /**< What tor version added this guard? NULL - * if we don't know. */ - unsigned int made_contact : 1; /**< 0 if we have never connected to this - * router, 1 if we have. */ - unsigned int can_retry : 1; /**< Should we retry connecting to this entry, - * in spite of having it marked as unreachable?*/ - time_t bad_since; /**< 0 if this guard is currently usable, or the time at - * which it was observed to become (according to the - * directory or the user configuration) unusable. */ - time_t unreachable_since; /**< 0 if we can connect to this guard, or the - * time at which we first noticed we couldn't - * connect to it. */ - time_t last_attempted; /**< 0 if we can connect to this guard, or the time - * at which we last failed to connect to it. */ -} entry_guard_t; + return 1; +} -/** A list of our chosen entry guards. */ -static smartlist_t *entry_guards = NULL; -/** A value of 1 means that the entry_guards list has changed - * and those changes need to be flushed to disk. */ -static int entry_guards_dirty = 0; +/** + * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of + * the past RECENT_CIRCUITS time out after the first hop. Used to detect + * if the network connection has changed significantly, and if so, + * resets our circuit build timeout to the default. + * + * Also resets the entire timeout history in this case and causes us + * to restart the process of building test circuits and estimating a + * new timeout. + */ +int +circuit_build_times_network_check_changed(circuit_build_times_t *cbt) +{ + int total_build_times = cbt->total_build_times; + int timeout_count=0; + int i; -/********* END VARIABLES ************/ + /* how many of our recent circuits made it to the first hop but then + * timed out? */ + for (i = 0; i < cbt->liveness.num_recent_circs; i++) { + timeout_count += cbt->liveness.timeouts_after_firsthop[i]; + } -static int circuit_deliver_create_cell(circuit_t *circ, - uint8_t cell_type, const char *payload); -static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit); -static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath); -static int onion_extend_cpath(origin_circuit_t *circ); -static int count_acceptable_routers(smartlist_t *routers); -static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice); + /* If 80% of our recent circuits are timing out after the first hop, + * we need to re-estimate a new initial alpha and timeout. */ + if (timeout_count < circuit_build_times_max_timeouts()) { + return 0; + } -static void entry_guards_changed(void); + circuit_build_times_reset(cbt); + memset(cbt->liveness.timeouts_after_firsthop, 0, + sizeof(*cbt->liveness.timeouts_after_firsthop)* + cbt->liveness.num_recent_circs); + cbt->liveness.after_firsthop_idx = 0; + + /* Check to see if this has happened before. If so, double the timeout + * to give people on abysmally bad network connections a shot at access */ + if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) { + if (cbt->timeout_ms > INT32_MAX/2 || cbt->close_ms > INT32_MAX/2) { + log_warn(LD_CIRC, "Insanely large circuit build timeout value. " + "(timeout = %lfmsec, close = %lfmsec)", + cbt->timeout_ms, cbt->close_ms); + } else { + cbt->timeout_ms *= 2; + cbt->close_ms *= 2; + } + } else { + cbt->close_ms = cbt->timeout_ms + = circuit_build_times_get_initial_timeout(); + } + + control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET); + + log_notice(LD_CIRC, + "Your network connection speed appears to have changed. Resetting " + "timeout to %lds after %d timeouts and %d buildtimes.", + tor_lround(cbt->timeout_ms/1000), timeout_count, + total_build_times); + + return 1; +} + +/** + * Count the number of timeouts in a set of cbt data. + */ +double +circuit_build_times_timeout_rate(const circuit_build_times_t *cbt) +{ + int i=0,timeouts=0; + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] >= cbt->timeout_ms) { + timeouts++; + } + } + + if (!cbt->total_build_times) + return 0; + + return ((double)timeouts)/cbt->total_build_times; +} + +/** + * Count the number of closed circuits in a set of cbt data. + */ +double +circuit_build_times_close_rate(const circuit_build_times_t *cbt) +{ + int i=0,closed=0; + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) { + closed++; + } + } + + if (!cbt->total_build_times) + return 0; + + return ((double)closed)/cbt->total_build_times; +} + +/** + * Store a timeout as a synthetic value. + * + * Returns true if the store was successful and we should possibly + * update our timeout estimate. + */ +int +circuit_build_times_count_close(circuit_build_times_t *cbt, + int did_onehop, + time_t start_time) +{ + if (circuit_build_times_disabled()) { + cbt->close_ms = cbt->timeout_ms + = circuit_build_times_get_initial_timeout(); + return 0; + } + + /* Record this force-close to help determine if the network is dead */ + circuit_build_times_network_close(cbt, did_onehop, start_time); + + /* Only count timeouts if network is live.. */ + if (!circuit_build_times_network_check_live(cbt)) { + return 0; + } + + circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED); + return 1; +} + +/** + * Update timeout counts to determine if we need to expire + * our build time history due to excessive timeouts. + * + * We do not record any actual time values at this stage; + * we are only interested in recording the fact that a timeout + * happened. We record the time values via + * circuit_build_times_count_close() and circuit_build_times_add_time(). + */ +void +circuit_build_times_count_timeout(circuit_build_times_t *cbt, + int did_onehop) +{ + if (circuit_build_times_disabled()) { + cbt->close_ms = cbt->timeout_ms + = circuit_build_times_get_initial_timeout(); + return; + } + + /* Register the fact that a timeout just occurred. */ + circuit_build_times_network_timeout(cbt, did_onehop); + + /* If there are a ton of timeouts, we should reset + * the circuit build timeout. */ + circuit_build_times_network_check_changed(cbt); +} + +/** + * Estimate a new timeout based on history and set our timeout + * variable accordingly. + */ +static int +circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt) +{ + build_time_t max_time; + if (!circuit_build_times_enough_to_compute(cbt)) + return 0; + + if (!circuit_build_times_update_alpha(cbt)) + return 0; + + cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt, + circuit_build_times_quantile_cutoff()); + + cbt->close_ms = circuit_build_times_calculate_timeout(cbt, + circuit_build_times_close_quantile()); + + max_time = circuit_build_times_max(cbt); + + /* Sometimes really fast guard nodes give us such a steep curve + * that this ends up being not that much greater than timeout_ms. + * Make it be at least 1 min to handle this case. */ + cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout()); + + if (cbt->timeout_ms > max_time) { + log_notice(LD_CIRC, + "Circuit build timeout of %dms is beyond the maximum build " + "time we have ever observed. Capping it to %dms.", + (int)cbt->timeout_ms, max_time); + cbt->timeout_ms = max_time; + } + + if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) { + log_info(LD_CIRC, + "Circuit build measurement period of %dms is more than twice " + "the maximum build time we have ever observed. Capping it to " + "%dms.", (int)cbt->close_ms, 2*max_time); + cbt->close_ms = 2*max_time; + } + + cbt->have_computed_timeout = 1; + return 1; +} + +/** + * Exposed function to compute a new timeout. Dispatches events and + * also filters out extremely high timeout values. + */ +void +circuit_build_times_set_timeout(circuit_build_times_t *cbt) +{ + long prev_timeout = tor_lround(cbt->timeout_ms/1000); + double timeout_rate; + + if (!circuit_build_times_set_timeout_worker(cbt)) + return; + + if (cbt->timeout_ms < circuit_build_times_min_timeout()) { + log_warn(LD_CIRC, "Set buildtimeout to low value %lfms. Setting to %dms", + cbt->timeout_ms, circuit_build_times_min_timeout()); + cbt->timeout_ms = circuit_build_times_min_timeout(); + if (cbt->close_ms < cbt->timeout_ms) { + /* This shouldn't happen because of MAX() in timeout_worker above, + * but doing it just in case */ + cbt->close_ms = circuit_build_times_initial_timeout(); + } + } + + control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED); + + timeout_rate = circuit_build_times_timeout_rate(cbt); + + if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) { + log_notice(LD_CIRC, + "Based on %d circuit times, it looks like we don't need to " + "wait so long for circuits to finish. We will now assume a " + "circuit is too slow to use after waiting %ld seconds.", + cbt->total_build_times, + tor_lround(cbt->timeout_ms/1000)); + log_info(LD_CIRC, + "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf", + cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, + timeout_rate); + } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) { + log_notice(LD_CIRC, + "Based on %d circuit times, it looks like we need to wait " + "longer for circuits to finish. We will now assume a " + "circuit is too slow to use after waiting %ld seconds.", + cbt->total_build_times, + tor_lround(cbt->timeout_ms/1000)); + log_info(LD_CIRC, + "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf", + cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, + timeout_rate); + } else { + log_info(LD_CIRC, + "Set circuit build timeout to %lds (%lfms, %lfms, Xm: %d, a: %lf," + " r: %lf) based on %d circuit times", + tor_lround(cbt->timeout_ms/1000), + cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate, + cbt->total_build_times); + } +} /** Iterate over values of circ_id, starting from conn-\>next_circ_id, * and with the high bit specified by conn-\>circ_id_type, until we get @@@ -1494,21 -112,21 +1494,21 @@@ circuit_list_path_impl(origin_circuit_ crypt_path_t *hop; smartlist_t *elements; const char *states[] = {"closed", "waiting for keys", "open"}; - char buf[128]; char *s; elements = smartlist_create(); if (verbose) { const char *nickname = build_state_get_exit_nickname(circ->build_state); - tor_snprintf(buf, sizeof(buf), "%s%s circ (length %d%s%s):", + char *cp; + tor_asprintf(&cp, "%s%s circ (length %d%s%s):", circ->build_state->is_internal ? "internal" : "exit", circ->build_state->need_uptime ? " (high-uptime)" : "", circ->build_state->desired_path_len, circ->_base.state == CIRCUIT_STATE_OPEN ? "" : ", exit ", circ->_base.state == CIRCUIT_STATE_OPEN ? "" : (nickname?nickname:"*unnamed*")); - smartlist_add(elements, tor_strdup(buf)); + smartlist_add(elements, cp); } hop = circ->cpath; @@@ -1530,7 -148,8 +1530,7 @@@ router_get_verbose_nickname(elt, ri); } else if ((rs = router_get_consensus_status_by_id(id))) { routerstatus_get_verbose_nickname(elt, rs); - } else if (hop->extend_info->nickname && - is_legal_nickname(hop->extend_info->nickname)) { + } else if (is_legal_nickname(hop->extend_info->nickname)) { elt[0] = '$'; base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN); elt[HEX_DIGEST_LEN+1]= '~'; @@@ -1598,7 -217,7 +1598,7 @@@ voi circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ) { char *s = circuit_list_path(circ,1); - log(severity,domain,"%s",s); + tor_log(severity,domain,"%s",s); tor_free(s); } @@@ -1650,7 -269,7 +1650,7 @@@ static in onion_populate_cpath(origin_circuit_t *circ) { int r; -again: + again: r = onion_extend_cpath(circ); if (r < 0) { log_info(LD_CIRC,"Generating cpath hop failed."); @@@ -1742,10 -361,9 +1742,10 @@@ circuit_handle_first_hop(origin_circuit if (!n_conn) { /* not currently connected in a useful way. */ - const char *name = firsthop->extend_info->nickname ? + const char *name = strlen(firsthop->extend_info->nickname) ? firsthop->extend_info->nickname : fmt_addr(&firsthop->extend_info->addr); - log_info(LD_CIRC, "Next router is %s: %s ", safe_str(name), msg?msg:"???"); + log_info(LD_CIRC, "Next router is %s: %s ", + safe_str_client(name), msg?msg:"???"); circ->_base.n_hop = extend_info_dup(firsthop->extend_info); if (should_launch) { @@@ -1888,8 -506,7 +1888,8 @@@ circuit_deliver_create_cell(circuit_t * cell.circ_id = circ->n_circ_id; memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN); - append_cell_to_circuit_queue(circ, circ->n_conn, &cell, CELL_DIRECTION_OUT); + append_cell_to_circuit_queue(circ, circ->n_conn, &cell, + CELL_DIRECTION_OUT, 0); if (CIRCUIT_IS_ORIGIN(circ)) { /* mark it so it gets better rate limiting treatment. */ @@@ -1919,7 -536,7 +1919,7 @@@ inform_testing_reachability(void "CHECKING_REACHABILITY DIRADDRESS=%s:%d", me->address, me->dir_port); } - log(LOG_NOTICE, LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... " + log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... " "(this may take up to %d minutes -- look for log " "messages indicating success)", me->address, me->or_port, @@@ -1952,18 -569,6 +1952,18 @@@ should_use_create_fast_for_circuit(orig return 1; } +/** Return true if circ is the type of circuit we want to count + * timeouts from. In particular, we want it to have not completed yet + * (already completing indicates we cannibalized it), and we want it to + * have exactly three hops. + */ +int +circuit_timeout_want_to_count_circ(origin_circuit_t *circ) +{ + return !circ->has_opened + && circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN; +} + /** This is the backbone function for building circuits. * * If circ's first hop is closed, then we need to build a create @@@ -2037,42 -642,15 +2037,42 @@@ circuit_send_next_onion_skin(origin_cir if (!hop) { /* done building the circuit. whew. */ circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN); + if (circuit_timeout_want_to_count_circ(circ)) { + struct timeval end; + long timediff; + tor_gettimeofday(&end); + timediff = tv_mdiff(&circ->_base.highres_created, &end); + + /* + * If the circuit build time is much greater than we would have cut + * it off at, we probably had a suspend event along this codepath, + * and we should discard the value. + */ + if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) { + log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. " + "Assuming clock jump. Purpose %d", timediff, + circ->_base.purpose); + } else if (!circuit_build_times_disabled()) { + /* Only count circuit times if the network is live */ + if (circuit_build_times_network_check_live(&circ_times)) { + circuit_build_times_add_time(&circ_times, (build_time_t)timediff); + circuit_build_times_set_timeout(&circ_times); + } + + if (circ->_base.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { + circuit_build_times_network_circ_success(&circ_times); + } + } + } log_info(LD_CIRC,"circuit built!"); circuit_reset_failure_count(0); if (circ->build_state->onehop_tunnel) control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0); - if (!has_completed_circuit && !circ->build_state->onehop_tunnel) { + if (!can_complete_circuit && !circ->build_state->onehop_tunnel) { or_options_t *options = get_options(); - has_completed_circuit=1; + can_complete_circuit=1; /* FFFF Log a count of known routers here */ - log(LOG_NOTICE, LD_GENERAL, + log_notice(LD_GENERAL, "Tor has successfully opened a circuit. " "Looks like client functionality is working."); control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0); @@@ -2084,10 -662,6 +2084,10 @@@ } circuit_rep_hist_note_result(circ); circuit_has_opened(circ); /* do other actions as necessary */ + + /* We're done with measurement circuits here. Just close them */ + if (circ->_base.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) + circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED); return 0; } @@@ -2131,13 -705,13 +2131,13 @@@ voi circuit_note_clock_jumped(int seconds_elapsed) { int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE; - log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; " + tor_log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; " "assuming established circuits no longer work.", seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed, seconds_elapsed >=0 ? "forward" : "backward"); control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d", seconds_elapsed); - has_completed_circuit=0; /* so it'll log when it works again */ + can_complete_circuit=0; /* so it'll log when it works again */ control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s", "CLOCK_JUMPED"); circuit_mark_all_unused_circs(); @@@ -2370,9 -944,10 +2370,9 @@@ circuit_finish_handshake(origin_circuit return -END_CIRC_REASON_TORPROTOCOL; } - if (hop->dh_handshake_state) { - crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */ - hop->dh_handshake_state = NULL; - } + crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */ + hop->dh_handshake_state = NULL; + memset(hop->fast_handshake_state, 0, sizeof(hop->fast_handshake_state)); if (circuit_init_cpath_crypto(hop, keys, 0)<0) { @@@ -2460,8 -1035,8 +2460,8 @@@ onionskin_answer(or_circuit_t *circ, ui cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2); log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.", - (unsigned int)*(uint32_t*)(keys), - (unsigned int)*(uint32_t*)(keys+20)); + (unsigned int)get_uint32(keys), + (unsigned int)get_uint32(keys+20)); if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) { log_warn(LD_BUG,"Circuit initialization failed"); tor_free(tmp_cpath); @@@ -2482,7 -1057,7 +2482,7 @@@ circ->is_first_hop = (cell_type == CELL_CREATED_FAST); append_cell_to_circuit_queue(TO_CIRCUIT(circ), - circ->p_conn, &cell, CELL_DIRECTION_IN); + circ->p_conn, &cell, CELL_DIRECTION_IN, 0); log_debug(LD_CIRC,"Finished sending 'created' cell."); if (!is_local_addr(&circ->p_conn->_base.addr) && @@@ -2511,7 -1086,7 +2511,7 @@@ new_route_len(uint8_t purpose, extend_i tor_assert(routers); - routelen = 3; + routelen = DEFAULT_ROUTE_LEN; if (exit && purpose != CIRCUIT_PURPOSE_TESTING && purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO) @@@ -2576,8 -1151,6 +2576,8 @@@ circuit_all_predicted_ports_handled(tim smartlist_t *LongLivedServices = get_options()->LongLivedPorts; tor_assert(need_uptime); tor_assert(need_capacity); + // Always predict need_capacity + *need_capacity = 1; enough = (smartlist_len(sl) == 0); for (i = 0; i < smartlist_len(sl); ++i) { port = smartlist_get(sl, i); @@@ -2600,8 -1173,6 +2600,8 @@@ router_handles_some_port(routerinfo_t * for (i = 0; i < smartlist_len(needed_ports); ++i) { addr_policy_result_t r; + /* alignment issues aren't a worry for this dereference, since + needed_ports is explicitly a smartlist of uint16_t's */ port = *(uint16_t *)smartlist_get(needed_ports, i); tor_assert(port); r = compare_addr_to_addr_policy(0, port, router->exit_policy); @@@ -2684,16 -1255,9 +2684,16 @@@ choose_good_exit_server_general(routerl n_supported[i] = -1; continue; /* skip routers that are known to be down or bad exits */ } - if (router_is_unreliable(router, need_uptime, need_capacity, 0)) { + if (router_is_unreliable(router, need_uptime, need_capacity, 0) && + (!options->ExitNodes || + !routerset_contains_router(options->ExitNodes, router))) { + /* FFFF Someday, differentiate between a routerset that names + * routers, and a routerset that names countries, and only do this + * check if they've asked for specific exit relays. Or if the country + * they ask for is rare. Or something. */ n_supported[i] = -1; - continue; /* skip routers that are not suitable */ + continue; /* skip routers that are not suitable, unless we have + * ExitNodes set, in which case we asked for it */ } if (!(router->is_valid || options->_AllowInvalid & ALLOW_INVALID_EXIT)) { /* if it's invalid and we don't want it */ @@@ -2718,7 -1282,7 +2718,7 @@@ { if (!ap_stream_wants_exit_attention(conn)) continue; /* Skip everything but APs in CIRCUIT_WAIT */ - if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), router)) { + if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), router, 1)) { ++n_supported[i]; // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.", // router->nickname, i, n_supported[i]); @@@ -2760,8 -1324,7 +2760,8 @@@ routersets_get_disjunction(use, supporting, options->ExitNodes, options->_ExcludeExitNodesUnion, 1); - if (smartlist_len(use) == 0 && !options->StrictExitNodes) { + if (smartlist_len(use) == 0 && options->ExitNodes && + !options->StrictNodes) { /* give up on exitnodes and try again */ routersets_get_disjunction(use, supporting, NULL, options->_ExcludeExitNodesUnion, 1); } @@@ -2773,7 -1336,7 +2773,7 @@@ * possibly support any of them. Choose a router at random that satisfies * at least one predicted exit port. */ - int try; + int attempt; smartlist_t *needed_ports, *supporting, *use; if (best_support == -1) { @@@ -2786,20 -1349,19 +2786,20 @@@ tor_free(n_supported); return choose_good_exit_server_general(dir, 0, 0); } - log_notice(LD_CIRC, "All routers are down or won't exit -- choosing a " - "doomed exit at random."); + log_notice(LD_CIRC, "All routers are down or won't exit%s -- " + "choosing a doomed exit at random.", + options->_ExcludeExitNodesUnion ? " or are Excluded" : ""); } supporting = smartlist_create(); use = smartlist_create(); needed_ports = circuit_get_unhandled_ports(time(NULL)); - for (try = 0; try < 2; try++) { + for (attempt = 0; attempt < 2; attempt++) { /* try once to pick only from routers that satisfy a needed port, * then if there are none, pick from any that support exiting. */ for (i = 0; i < smartlist_len(dir->routers); i++) { router = smartlist_get(dir->routers, i); if (n_supported[i] != -1 && - (try || router_handles_some_port(router, needed_ports))) { + (attempt || router_handles_some_port(router, needed_ports))) { // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.", // try, router->nickname); smartlist_add(supporting, router); @@@ -2808,14 -1370,12 +2808,14 @@@ routersets_get_disjunction(use, supporting, options->ExitNodes, options->_ExcludeExitNodesUnion, 1); - if (smartlist_len(use) == 0 && !options->StrictExitNodes) { + if (smartlist_len(use) == 0 && options->ExitNodes && + !options->StrictNodes) { /* give up on exitnodes and try again */ routersets_get_disjunction(use, supporting, NULL, options->_ExcludeExitNodesUnion, 1); } - /* XXX sometimes the above results in null, when the requested - * exit node is down. we should pick it anyway. */ + /* FFF sometimes the above results in null, when the requested + * exit node is considered down by the consensus. we should pick + * it anyway, since the user asked for it. */ router = routerlist_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT); if (router) break; @@@ -2833,10 -1393,10 +2833,10 @@@ log_info(LD_CIRC, "Chose exit server '%s'", router->nickname); return router; } - if (options->StrictExitNodes) { + if (options->ExitNodes && options->StrictNodes) { log_warn(LD_CIRC, "No specified exit routers seem to be running, and " - "StrictExitNodes is set: can't choose an exit."); + "StrictNodes is set: can't choose an exit."); } return NULL; } @@@ -2867,13 -1427,15 +2867,13 @@@ choose_good_exit_server(uint8_t purpose if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE) flags |= CRN_ALLOW_INVALID; if (is_internal) /* pick it like a middle hop */ - return router_choose_random_node(NULL, NULL, - options->ExcludeNodes, flags); + return router_choose_random_node(NULL, options->ExcludeNodes, flags); else return choose_good_exit_server_general(dir,need_uptime,need_capacity); case CIRCUIT_PURPOSE_C_ESTABLISH_REND: if (options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS) flags |= CRN_ALLOW_INVALID; - return router_choose_random_node(NULL, NULL, - options->ExcludeNodes, flags); + return router_choose_random_node(NULL, options->ExcludeNodes, flags); } log_warn(LD_BUG,"Unhandled purpose %d", purpose); tor_fragile_assert(); @@@ -2993,7 -1555,8 +2993,7 @@@ circuit_append_new_exit(origin_circuit_ state = circ->build_state; tor_assert(state); - if (state->chosen_exit) - extend_info_free(state->chosen_exit); + extend_info_free(state->chosen_exit); state->chosen_exit = extend_info_dup(exit); ++circ->build_state->desired_path_len; @@@ -3115,7 -1678,8 +3115,7 @@@ choose_good_middle_server(uint8_t purpo flags |= CRN_NEED_CAPACITY; if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE) flags |= CRN_ALLOW_INVALID; - choice = router_choose_random_node(NULL, - excluded, options->ExcludeNodes, flags); + choice = router_choose_random_node(excluded, options->ExcludeNodes, flags); smartlist_free(excluded); return choice; } @@@ -3179,7 -1743,11 +3179,7 @@@ choose_good_entry_server(uint8_t purpos if (options->_AllowInvalid & ALLOW_INVALID_ENTRY) flags |= CRN_ALLOW_INVALID; - choice = router_choose_random_node( - NULL, - excluded, - options->ExcludeNodes, - flags); + choice = router_choose_random_node(excluded, options->ExcludeNodes, flags); smartlist_free(excluded); return choice; } @@@ -3300,9 -1868,9 +3300,9 @@@ extend_info_from_router(routerinfo_t *r void extend_info_free(extend_info_t *info) { - tor_assert(info); - if (info->onion_key) - crypto_free_pk_env(info->onion_key); + if (!info) + return; + crypto_free_pk_env(info->onion_key); tor_free(info); } @@@ -3361,6 -1929,8 +3361,6 @@@ entry_guard_set_status(entry_guard_t *e char buf[HEX_DIGEST_LEN+1]; int changed = 0; - tor_assert(options); - *reason = NULL; /* Do we want to mark this guard as bad? */ @@@ -3423,58 -1993,35 +3423,58 @@@ entry_is_time_to_retry(entry_guard_t *e * - Listed as either up or never yet contacted; * - Present in the routerlist; * - Listed as 'stable' or 'fast' by the current dirserver consensus, - * if demanded by need_uptime or need_capacity; - * (This check is currently redundant with the Guard flag, but in - * the future that might change. Best to leave it in for now.) + * if demanded by need_uptime or need_capacity + * (unless it's a configured EntryNode); * - Allowed by our current ReachableORAddresses config option; and - * - Currently thought to be reachable by us (unless assume_reachable + * - Currently thought to be reachable by us (unless assume_reachable * is true). + * + * If the answer is no, set *msg to an explanation of why. */ static INLINE routerinfo_t * entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity, - int assume_reachable) + int assume_reachable, const char **msg) { routerinfo_t *r; - if (e->bad_since) + or_options_t *options = get_options(); + tor_assert(msg); + + if (e->bad_since) { + *msg = "bad"; return NULL; + } /* no good if it's unreachable, unless assume_unreachable or can_retry. */ if (!assume_reachable && !e->can_retry && - e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) + e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) { + *msg = "unreachable"; return NULL; + } r = router_get_by_digest(e->identity); - if (!r) + if (!r) { + *msg = "no descriptor"; return NULL; - if (get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_BRIDGE) + } + if (get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_BRIDGE) { + *msg = "not a bridge"; return NULL; - if (!get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_GENERAL) + } + if (!get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_GENERAL) { + *msg = "not general-purpose"; return NULL; - if (router_is_unreliable(r, need_uptime, need_capacity, 0)) + } + if (options->EntryNodes && + routerset_contains_router(options->EntryNodes, r)) { + /* they asked for it, they get it */ + need_uptime = need_capacity = 0; + } + if (router_is_unreliable(r, need_uptime, need_capacity, 0)) { + *msg = "not fast/stable"; return NULL; - if (!fascist_firewall_allows_or(r)) + } + if (!fascist_firewall_allows_or(r)) { + *msg = "unreachable by config"; return NULL; + } return r; } @@@ -3483,12 -2030,11 +3483,12 @@@ static in num_live_entry_guards(void) { int n = 0; + const char *msg; if (! entry_guards) return 0; SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, { - if (entry_is_live(entry, 0, 1, 0)) + if (entry_is_live(entry, 0, 1, 0, &msg)) ++n; }); return n; @@@ -3512,21 -2058,16 +3512,21 @@@ static voi log_entry_guards(int severity) { smartlist_t *elements = smartlist_create(); - char buf[1024]; char *s; SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, { - tor_snprintf(buf, sizeof(buf), "%s (%s%s)", - e->nickname, - entry_is_live(e, 0, 1, 0) ? "up " : "down ", - e->made_contact ? "made-contact" : "never-contacted"); - smartlist_add(elements, tor_strdup(buf)); + const char *msg = NULL; + char *cp; + if (entry_is_live(e, 0, 1, 0, &msg)) + tor_asprintf(&cp, "%s (up %s)", + e->nickname, + e->made_contact ? "made-contact" : "never-contacted"); + else + tor_asprintf(&cp, "%s (%s, %s)", + e->nickname, msg, + e->made_contact ? "made-contact" : "never-contacted"); + smartlist_add(elements, cp); }); s = smartlist_join_strings(elements, ",", 0, NULL); @@@ -3550,13 -2091,12 +3550,13 @@@ control_event_guard_deferred(void **/ #if 0 int n = 0; + const char *msg; or_options_t *options = get_options(); if (!entry_guards) return; SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, { - if (entry_is_live(entry, 0, 1, 0)) { + if (entry_is_live(entry, 0, 1, 0, &msg)) { if (n++ == options->NumEntryGuards) { control_event_guard(entry->nickname, entry->identity, "DEFERRED"); return; @@@ -3618,8 -2158,9 +3618,8 @@@ add_an_entry_guard(routerinfo_t *chosen /** If the use of entry guards is configured, choose more entry guards * until we have enough in the list. */ static void -pick_entry_guards(void) +pick_entry_guards(or_options_t *options) { - or_options_t *options = get_options(); int changed = 0; tor_assert(entry_guards); @@@ -3641,8 -2182,7 +3641,8 @@@ static void entry_guard_free(entry_guard_t *e) { - tor_assert(e); + if (!e) + return; tor_free(e->chosen_by_version); tor_free(e); } @@@ -3651,9 -2191,10 +3651,9 @@@ * or which was selected by a version of Tor that's known to select * entry guards badly. */ static int -remove_obsolete_entry_guards(void) +remove_obsolete_entry_guards(time_t now) { int changed = 0, i; - time_t now = time(NULL); for (i = 0; i < smartlist_len(entry_guards); ++i) { entry_guard_t *entry = smartlist_get(entry_guards, i); @@@ -3713,10 -2254,11 +3713,10 @@@ * long that we don't think they'll come up again. Return 1 if we * removed any, or 0 if we did nothing. */ static int -remove_dead_entry_guards(void) +remove_dead_entry_guards(time_t now) { char dbuf[HEX_DIGEST_LEN+1]; char tbuf[ISO_TIME_LEN+1]; - time_t now = time(NULL); int i; int changed = 0; @@@ -3751,17 -2293,19 +3751,17 @@@ * think that things are unlisted. */ void -entry_guards_compute_status(void) +entry_guards_compute_status(or_options_t *options, time_t now) { - time_t now; int changed = 0; int severity = LOG_DEBUG; - or_options_t *options; digestmap_t *reasons; + if (! entry_guards) return; - options = get_options(); - - now = time(NULL); + if (options->EntryNodes) /* reshuffle the entry guard list if needed */ + entry_nodes_should_be_added(); reasons = digestmap_new(); SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) @@@ -3778,7 -2322,7 +3778,7 @@@ } SMARTLIST_FOREACH_END(entry); - if (remove_dead_entry_guards()) + if (remove_dead_entry_guards(now)) changed = 1; severity = changed ? LOG_DEBUG : LOG_INFO; @@@ -3786,16 -2330,13 +3786,16 @@@ if (changed) { SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) { const char *reason = digestmap_get(reasons, entry->identity); - log_info(LD_CIRC, "Summary: Entry '%s' is %s, %s%s%s, and %s.", + const char *live_msg = ""; + routerinfo_t *r = entry_is_live(entry, 0, 1, 0, &live_msg); + log_info(LD_CIRC, "Summary: Entry '%s' is %s, %s%s%s, and %s%s.", entry->nickname, entry->unreachable_since ? "unreachable" : "reachable", entry->bad_since ? "unusable" : "usable", reason ? ", ": "", reason ? reason : "", - entry_is_live(entry, 0, 1, 0) ? "live" : "not live"); + r ? "live" : "not live / ", + r ? "" : live_msg); } SMARTLIST_FOREACH_END(entry); log_info(LD_CIRC, " (%d/%d entry guards are usable/new)", num_live_entry_guards(), smartlist_len(entry_guards)); @@@ -3866,7 -2407,6 +3866,7 @@@ entry_guard_register_connect_status(con "Removing from the list. %d/%d entry guards usable/new.", entry->nickname, buf, num_live_entry_guards()-1, smartlist_len(entry_guards)-1); + control_event_guard(entry->nickname, entry->identity, "DROPPED"); entry_guard_free(entry); smartlist_del_keeporder(entry_guards, idx); log_entry_guards(LOG_INFO); @@@ -3903,8 -2443,7 +3903,8 @@@ if (e == entry) break; if (e->made_contact) { - routerinfo_t *r = entry_is_live(e, 0, 1, 1); + const char *msg; + routerinfo_t *r = entry_is_live(e, 0, 1, 1, &msg); if (r && e->unreachable_since) { refuse_conn = 1; e->can_retry = 1; @@@ -3935,16 -2474,16 +3935,16 @@@ static int should_add_entry_nodes = 0 void entry_nodes_should_be_added(void) { - log_info(LD_CIRC, "New EntryNodes config option detected. Will use."); + log_info(LD_CIRC, "EntryNodes config option set. Putting configured " + "relays at the front of the entry guard list."); should_add_entry_nodes = 1; } /** Add all nodes in EntryNodes that aren't currently guard nodes to the list * of guard nodes, at the front. */ static void -entry_guards_prepend_from_config(void) +entry_guards_prepend_from_config(or_options_t *options) { - or_options_t *options = get_options(); smartlist_t *entry_routers, *entry_fps; smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list; tor_assert(entry_guards); @@@ -3959,7 -2498,7 +3959,7 @@@ return; } - if (options->EntryNodes) { + { char *string = routerset_to_string(options->EntryNodes); log_info(LD_CIRC,"Adding configured EntryNodes '%s'.", string); tor_free(string); @@@ -4003,9 -2542,8 +4003,9 @@@ SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, { add_an_entry_guard(ri, 0); }); - /* Finally, the remaining EntryNodes, unless we're strict */ - if (options->StrictEntryNodes) { + /* Finally, the remaining previously configured guards that are not in + * EntryNodes, unless we're strict in which case we drop them */ + if (options->StrictNodes) { SMARTLIST_FOREACH(old_entry_guards_not_on_list, entry_guard_t *, e, entry_guard_free(e)); } else { @@@ -4019,30 -2557,16 +4019,30 @@@ entry_guards_changed(); } -/** Return 1 if we're fine adding arbitrary routers out of the - * directory to our entry guard list. Else return 0. */ +/** Return 0 if we're fine adding arbitrary routers out of the + * directory to our entry guard list, or return 1 if we have a + * list already and we'd prefer to stick to it. + */ int -entry_list_can_grow(or_options_t *options) +entry_list_is_constrained(or_options_t *options) { - if (options->StrictEntryNodes) - return 0; + if (options->EntryNodes) + return 1; if (options->UseBridges) - return 0; - return 1; + return 1; + return 0; +} + +/* Are we dead set against changing our entry guard list, or would we + * change it if it means keeping Tor usable? */ +static int +entry_list_is_totally_static(or_options_t *options) +{ + if (options->EntryNodes && options->StrictNodes) + return 1; + if (options->UseBridges) + return 1; + return 0; } /** Pick a live (up and listed) entry guard from entry_guards. If @@@ -4060,9 -2584,10 +4060,9 @@@ choose_random_entry(cpath_build_state_ routerinfo_t *r = NULL; int need_uptime = state ? state->need_uptime : 0; int need_capacity = state ? state->need_capacity : 0; - int consider_exit_family = 0; + int preferred_min, consider_exit_family = 0; if (chosen_exit) { - smartlist_add(exit_family, chosen_exit); routerlist_add_family(exit_family, chosen_exit); consider_exit_family = 1; } @@@ -4071,64 -2596,38 +4071,64 @@@ entry_guards = smartlist_create(); if (should_add_entry_nodes) - entry_guards_prepend_from_config(); + entry_guards_prepend_from_config(options); - if (entry_list_can_grow(options) && - (! entry_guards || - smartlist_len(entry_guards) < options->NumEntryGuards)) - pick_entry_guards(); + if (!entry_list_is_constrained(options) && + smartlist_len(entry_guards) < options->NumEntryGuards) + pick_entry_guards(options); retry: smartlist_clear(live_entry_guards); SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, { - r = entry_is_live(entry, need_uptime, need_capacity, 0); - if (r && (!consider_exit_family || !smartlist_isin(exit_family, r))) { - smartlist_add(live_entry_guards, r); - if (!entry->made_contact) { - /* Always start with the first not-yet-contacted entry - * guard. Otherwise we might add several new ones, pick - * the second new one, and now we've expanded our entry - * guard list without needing to. */ - goto choose_and_finish; + const char *msg; + r = entry_is_live(entry, need_uptime, need_capacity, 0, &msg); + if (!r) + continue; /* down, no point */ + if (r == chosen_exit) + continue; /* don't pick the same node for entry and exit */ + if (consider_exit_family && smartlist_isin(exit_family, r)) + continue; /* avoid relays that are family members of our exit */ + if (options->EntryNodes && + !routerset_contains_router(options->EntryNodes, r)) { + /* We've come to the end of our preferred entry nodes. */ + if (smartlist_len(live_entry_guards)) + goto choose_and_finish; /* only choose from the ones we like */ + if (options->StrictNodes) { + /* in theory this case should never happen, since + * entry_guards_prepend_from_config() drops unwanted relays */ + tor_fragile_assert(); + } else { + log_info(LD_CIRC, + "No relays from EntryNodes available. Using others."); } - if (smartlist_len(live_entry_guards) >= options->NumEntryGuards) - break; /* we have enough */ } + smartlist_add(live_entry_guards, r); + if (!entry->made_contact) { + /* Always start with the first not-yet-contacted entry + * guard. Otherwise we might add several new ones, pick + * the second new one, and now we've expanded our entry + * guard list without needing to. */ + goto choose_and_finish; + } + if (smartlist_len(live_entry_guards) >= options->NumEntryGuards) + break; /* we have enough */ }); - /* Try to have at least 2 choices available. This way we don't - * get stuck with a single live-but-crummy entry and just keep - * using him. - * (We might get 2 live-but-crummy entry guards, but so be it.) */ - if (smartlist_len(live_entry_guards) < 2) { - if (entry_list_can_grow(options)) { + if (entry_list_is_constrained(options)) { + /* If we prefer the entry nodes we've got, and we have at least + * one choice, that's great. Use it. */ + preferred_min = 1; + } else { + /* Try to have at least 2 choices available. This way we don't + * get stuck with a single live-but-crummy entry and just keep + * using him. + * (We might get 2 live-but-crummy entry guards, but so be it.) */ + preferred_min = 2; + } + + if (smartlist_len(live_entry_guards) < preferred_min) { + if (!entry_list_is_totally_static(options)) { /* still no? try adding a new entry then */ /* XXX if guard doesn't imply fast and stable, then we need * to tell add_an_entry_guard below what we want, or it might @@@ -4153,7 -2652,7 +4153,7 @@@ need_capacity = 0; goto retry; } - if (!r && !entry_list_can_grow(options) && consider_exit_family) { + if (!r && entry_list_is_constrained(options) && consider_exit_family) { /* still no? if we're using bridges or have strictentrynodes * set, and our chosen exit is in the same family as all our * bridges/entry guards, then be flexible about families. */ @@@ -4164,15 -2663,15 +4164,15 @@@ } choose_and_finish: - if (entry_list_can_grow(options)) { + if (entry_list_is_constrained(options)) { + /* We need to weight by bandwidth, because our bridges or entryguards + * were not already selected proportional to their bandwidth. */ + r = routerlist_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD); + } else { /* We choose uniformly at random here, because choose_good_entry_server() * already weights its choices by bandwidth, so we don't want to * *double*-weight our guard selection. */ r = smartlist_choose(live_entry_guards); - } else { - /* We need to weight by bandwidth, because our bridges or entryguards - * were not already selected proportional to their bandwidth. */ - r = routerlist_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD); } smartlist_free(live_entry_guards); smartlist_free(exit_family); @@@ -4306,7 -2805,7 +4306,7 @@@ entry_guards_parse_state(or_state_t *st entry_guards_dirty = 0; /* XXX022 hand new_entry_guards to this func, and move it up a * few lines, so we don't have to re-dirty it */ - if (remove_obsolete_entry_guards()) + if (remove_obsolete_entry_guards(now)) entry_guards_dirty = 1; } digestmap_free(added_by, _tor_free); @@@ -4405,11 -2904,9 +4405,11 @@@ entry_guards_update_state(or_state_t *s * */ int getinfo_helper_entry_guards(control_connection_t *conn, - const char *question, char **answer) + const char *question, char **answer, + const char **errmsg) { - int use_long_names = conn->use_long_names; + (void) conn; + (void) errmsg; if (!strcmp(question,"entry-guards") || !strcmp(question,"helper-nodes")) { @@@ -4418,13 -2915,12 +4418,13 @@@ char nbuf[MAX_VERBOSE_NICKNAME_LEN+1]; if (!entry_guards) entry_guards = smartlist_create(); - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, - { + SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) { size_t len = MAX_VERBOSE_NICKNAME_LEN+ISO_TIME_LEN+32; char *c = tor_malloc(len); const char *status = NULL; time_t when = 0; + routerinfo_t *ri; + if (!e->made_contact) { status = "never-connected"; } else if (e->bad_since) { @@@ -4433,17 -2929,19 +4433,17 @@@ } else { status = "up"; } - if (use_long_names) { - routerinfo_t *ri = router_get_by_digest(e->identity); - if (ri) { - router_get_verbose_nickname(nbuf, ri); - } else { - nbuf[0] = '$'; - base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN); - /* e->nickname field is not very reliable if we don't know about - * this router any longer; don't include it. */ - } + + ri = router_get_by_digest(e->identity); + if (ri) { + router_get_verbose_nickname(nbuf, ri); } else { - base16_encode(nbuf, sizeof(nbuf), e->identity, DIGEST_LEN); + nbuf[0] = '$'; + base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN); + /* e->nickname field is not very reliable if we don't know about + * this router any longer; don't include it. */ } + if (when) { format_iso_time(tbuf, when); tor_snprintf(c, len, "%s %s %s\n", nbuf, status, tbuf); @@@ -4451,7 -2949,7 +4451,7 @@@ tor_snprintf(c, len, "%s %s\n", nbuf, status); } smartlist_add(sl, c); - }); + } SMARTLIST_FOREACH_END(e); *answer = smartlist_join_strings(sl, "", 0, NULL); SMARTLIST_FOREACH(sl, char *, c, tor_free(c)); smartlist_free(sl); @@@ -4492,56 -2990,29 +4492,56 @@@ clear_bridge_list(void * (either by comparing keys if possible, else by comparing addr/port). * Else return NULL. */ static bridge_info_t * -routerinfo_get_configured_bridge(routerinfo_t *ri) +get_configured_bridge_by_addr_port_digest(tor_addr_t *addr, uint16_t port, + const char *digest) { if (!bridge_list) return NULL; SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge) { if (tor_digest_is_zero(bridge->identity) && - tor_addr_eq_ipv4h(&bridge->addr, ri->addr) && - bridge->port == ri->or_port) + !tor_addr_compare(&bridge->addr, addr, CMP_EXACT) && + bridge->port == port) return bridge; - if (!memcmp(bridge->identity, ri->cache_info.identity_digest, - DIGEST_LEN)) + if (!memcmp(bridge->identity, digest, DIGEST_LEN)) return bridge; } SMARTLIST_FOREACH_END(bridge); return NULL; } +/** Wrapper around get_configured_bridge_by_addr_port_digest() to look + * it up via router descriptor ri. */ +static bridge_info_t * +get_configured_bridge_by_routerinfo(routerinfo_t *ri) +{ + tor_addr_t addr; + tor_addr_from_ipv4h(&addr, ri->addr); + return get_configured_bridge_by_addr_port_digest(&addr, + ri->or_port, ri->cache_info.identity_digest); +} + /** Return 1 if ri is one of our known bridges, else 0. */ int routerinfo_is_a_configured_bridge(routerinfo_t *ri) { - return routerinfo_get_configured_bridge(ri) ? 1 : 0; + return get_configured_bridge_by_routerinfo(ri) ? 1 : 0; +} + +/** We made a connection to a router at addr:port + * without knowing its digest. Its digest turned out to be digest. + * If it was a bridge, and we still don't know its digest, record it. + */ +void +learned_router_identity(tor_addr_t *addr, uint16_t port, const char *digest) +{ + bridge_info_t *bridge = + get_configured_bridge_by_addr_port_digest(addr, port, digest); + if (bridge && tor_digest_is_zero(bridge->identity)) { + memcpy(bridge->identity, digest, DIGEST_LEN); + log_notice(LD_DIR, "Learned fingerprint %s for bridge %s:%d", + hex_str(digest, DIGEST_LEN), fmt_addr(addr), port); + } } /** Remember a new bridge at addr:port. If digest @@@ -4611,8 -3082,9 +4611,8 @@@ retry_bridge_descriptor_fetch_directly( * descriptor, fetch a new copy of its descriptor -- either directly * from the bridge or via a bridge authority. */ void -fetch_bridge_descriptors(time_t now) +fetch_bridge_descriptors(or_options_t *options, time_t now) { - or_options_t *options = get_options(); int num_bridge_auths = get_n_authorities(BRIDGE_AUTHORITY); int ask_bridge_directly; int can_use_bridge_authority; @@@ -4680,7 -3152,7 +4680,7 @@@ learned_bridge_descriptor(routerinfo_t tor_assert(ri->purpose == ROUTER_PURPOSE_BRIDGE); if (get_options()->UseBridges) { int first = !any_bridge_descriptors_known(); - bridge_info_t *bridge = routerinfo_get_configured_bridge(ri); + bridge_info_t *bridge = get_configured_bridge_by_routerinfo(ri); time_t now = time(NULL); ri->is_running = 1; @@@ -4728,7 -3200,8 +4728,8 @@@ any_pending_bridge_descriptor_fetches(v conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC && TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE && !conn->marked_for_close && - conn->linked && !conn->linked_conn->marked_for_close) { + conn->linked && + conn->linked_conn && !conn->linked_conn->marked_for_close) { log_debug(LD_DIR, "found one: %s", conn->address); return 1; } @@@ -4736,38 -3209,26 +4737,38 @@@ return 0; } -/** Return 1 if we have at least one descriptor for a bridge and - * all descriptors we know are down. Else return 0. If act is - * 1, then mark the down bridges up; else just observe and report. */ +/** Return 1 if we have at least one descriptor for an entry guard + * (bridge or member of EntryNodes) and all descriptors we know are + * down. Else return 0. If act is 1, then mark the down guards + * up; else just observe and report. */ static int -bridges_retry_helper(int act) +entries_retry_helper(or_options_t *options, int act) { routerinfo_t *ri; int any_known = 0; int any_running = 0; + int purpose = options->UseBridges ? + ROUTER_PURPOSE_BRIDGE : ROUTER_PURPOSE_GENERAL; if (!entry_guards) entry_guards = smartlist_create(); SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, { ri = router_get_by_digest(e->identity); - if (ri && ri->purpose == ROUTER_PURPOSE_BRIDGE) { + if (ri && ri->purpose == purpose) { any_known = 1; if (ri->is_running) - any_running = 1; /* some bridge is both known and running */ - else if (act) { /* mark it for retry */ - ri->is_running = 1; + any_running = 1; /* some entry is both known and running */ + else if (act) { + /* Mark all current connections to this OR as unhealthy, since + * otherwise there could be one that started 30 seconds + * ago, and in 30 seconds it will time out, causing us to mark + * the node down and undermine the retry attempt. We mark even + * the established conns, since if the network just came back + * we'll want to attach circuits to fresh conns. */ + connection_or_set_bad_connections(ri->cache_info.identity_digest, 1); + + /* mark this entry node for retry */ + router_set_status(ri->cache_info.identity_digest, 1); e->can_retry = 1; e->bad_since = 0; } @@@ -4778,21 -3239,19 +4779,21 @@@ return any_known && !any_running; } -/** Do we know any descriptors for our bridges, and are they all - * down? */ +/** Do we know any descriptors for our bridges / entrynodes, and are + * all the ones we have descriptors for down? */ int -bridges_known_but_down(void) +entries_known_but_down(or_options_t *options) { - return bridges_retry_helper(0); + tor_assert(entry_list_is_constrained(options)); + return entries_retry_helper(options, 0); } -/** Mark all down known bridges up. */ +/** Mark all down known bridges / entrynodes up. */ void -bridges_retry_all(void) +entries_retry_all(or_options_t *options) { - bridges_retry_helper(1); + tor_assert(entry_list_is_constrained(options)); + entries_retry_helper(options, 1); } /** Release all storage held by the list of entry guards and related

1 0

[tor/master] make nickm's proposed convention from 2003 be gospel
by nickm＠torproject.org 08 Mar '11

08 Mar '11

commit 95edd51116c17327f314bc132a0a5f86499e410a Author: Roger Dingledine <arma(a)torproject.org> Date: Tue Mar 8 14:59:30 2011 -0500 make nickm's proposed convention from 2003 be gospel --- doc/HACKING | 10 +++++----- 1 files changed, 5 insertions(+), 5 deletions(-) diff --git a/doc/HACKING b/doc/HACKING index 486fe6d..bdb86c0 100644 --- a/doc/HACKING +++ b/doc/HACKING @@ -312,11 +312,11 @@ operation. If a library function is currently called such that failure always means ERR, then the library function should log WARN and let the caller log ERR. -[XXX Proposed convention: every message of severity INFO or higher should -either (A) be intelligible to end-users who don't know the Tor source; or (B) -somehow inform the end-users that they aren't expected to understand the -message (perhaps with a string like "internal error"). Option (A) is to be -preferred to option (B). -NM] +Every message of severity INFO or higher should either (A) be intelligible +to end-users who don't know the Tor source; or (B) somehow inform the +end-users that they aren't expected to understand the message (perhaps +with a string like "internal error"). Option (A) is to be preferred to +option (B). Doxygen ~~~~~~~~

1 0

[tor/maint-0.2.2] Avoid crash in any_pending_bridge_descriptor_fetches
by nickm＠torproject.org 08 Mar '11

08 Mar '11

commit 9a6df215395750286383eed77f3c49d2b3ef34df Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 8 15:17:41 2011 -0500 Avoid crash in any_pending_bridge_descriptor_fetches This is based on shitlei's fix for bug2629, with extra parens removed. Fixes bug 2629, bugfix on 0.2.1.2-alpha. --- changes/bug2629 | 5 +++++ src/or/circuitbuild.c | 3 ++- 2 files changed, 7 insertions(+), 1 deletions(-) diff --git a/changes/bug2629 b/changes/bug2629 new file mode 100644 index 0000000..87817cf --- /dev/null +++ b/changes/bug2629 @@ -0,0 +1,5 @@ + o Minor bugfixes + - Fix a crash bug that could occur occasionally when a client was + configured with a large number of bridges. Fixes bug 2629; bugfix + on 0.2.1.2-alpha. Bugfix by trac user "shitlei". + diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 065eb05..76713e6 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -3200,7 +3200,8 @@ any_pending_bridge_descriptor_fetches(void) conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC && TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE && !conn->marked_for_close && - conn->linked && !conn->linked_conn->marked_for_close) { + conn->linked && + conn->linked_conn && !conn->linked_conn->marked_for_close) { log_debug(LD_DIR, "found one: %s", conn->address); return 1; }

1 0

[tor/maint-0.2.2] Merge remote branch 'origin/maint-0.2.1' into maint-0.2.2
by nickm＠torproject.org 08 Mar '11

08 Mar '11

commit 9ad083d5731c983ea3e961822306c50ce32dfcc2 Merge: 95edd51 9a6df21 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 8 15:20:48 2011 -0500 Merge remote branch 'origin/maint-0.2.1' into maint-0.2.2 changes/bug2629 | 5 +++++ src/or/circuitbuild.c | 3 ++- 2 files changed, 7 insertions(+), 1 deletions(-) diff --combined src/or/circuitbuild.c index b3c9f0e,76713e6..6be27d2 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@@ -9,1437 -9,55 +9,1437 @@@ * \brief The actual details of building circuits. **/ +#define CIRCUIT_PRIVATE + #include "or.h" +#include "circuitbuild.h" +#include "circuitlist.h" +#include "circuituse.h" +#include "config.h" +#include "connection.h" +#include "connection_edge.h" +#include "connection_or.h" +#include "control.h" +#include "directory.h" +#include "main.h" +#include "networkstatus.h" +#include "onion.h" +#include "policies.h" +#include "relay.h" +#include "rephist.h" +#include "router.h" +#include "routerlist.h" +#include "routerparse.h" +#include "crypto.h" +#undef log +#include <math.h> + +#ifndef MIN +#define MIN(a,b) ((a)<(b)?(a):(b)) +#endif + +#define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2)) + +/********* START VARIABLES **********/ +/** Global list of circuit build times */ +// FIXME: Add this as a member for entry_guard_t instead of global? +// Then we could do per-guard statistics, as guards are likely to +// vary in their own latency. The downside of this is that guards +// can change frequently, so we'd be building a lot more circuits +// most likely. +circuit_build_times_t circ_times; + +/** A global list of all circuits at this hop. */ +extern circuit_t *global_circuitlist; + +/** An entry_guard_t represents our information about a chosen long-term + * first hop, known as a "helper" node in the literature. We can't just + * use a routerinfo_t, since we want to remember these even when we + * don't have a directory. */ +typedef struct { + char nickname[MAX_NICKNAME_LEN+1]; + char identity[DIGEST_LEN]; + time_t chosen_on_date; /**< Approximately when was this guard added? + * "0" if we don't know. */ + char *chosen_by_version; /**< What tor version added this guard? NULL + * if we don't know. */ + unsigned int made_contact : 1; /**< 0 if we have never connected to this + * router, 1 if we have. */ + unsigned int can_retry : 1; /**< Should we retry connecting to this entry, + * in spite of having it marked as unreachable?*/ + time_t bad_since; /**< 0 if this guard is currently usable, or the time at + * which it was observed to become (according to the + * directory or the user configuration) unusable. */ + time_t unreachable_since; /**< 0 if we can connect to this guard, or the + * time at which we first noticed we couldn't + * connect to it. */ + time_t last_attempted; /**< 0 if we can connect to this guard, or the time + * at which we last failed to connect to it. */ +} entry_guard_t; + +/** A list of our chosen entry guards. */ +static smartlist_t *entry_guards = NULL; +/** A value of 1 means that the entry_guards list has changed + * and those changes need to be flushed to disk. */ +static int entry_guards_dirty = 0; + +/** If set, we're running the unit tests: we should avoid clobbering + * our state file or accessing get_options() or get_or_state() */ +static int unit_tests = 0; + +/********* END VARIABLES ************/ + +static int circuit_deliver_create_cell(circuit_t *circ, + uint8_t cell_type, const char *payload); +static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit); +static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath); +static int onion_extend_cpath(origin_circuit_t *circ); +static int count_acceptable_routers(smartlist_t *routers); +static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice); + +static void entry_guards_changed(void); + +/** + * This function decides if CBT learning should be disabled. It returns + * true if one or more of the following four conditions are met: + * + * 1. If the cbtdisabled consensus parameter is set. + * 2. If the torrc option LearnCircuitBuildTimeout is false. + * 3. If we are a directory authority + * 4. If we fail to write circuit build time history to our state file. + */ +static int +circuit_build_times_disabled(void) +{ + if (unit_tests) { + return 0; + } else { + int consensus_disabled = networkstatus_get_param(NULL, "cbtdisabled", + 0, 0, 1); + int config_disabled = !get_options()->LearnCircuitBuildTimeout; + int dirauth_disabled = get_options()->AuthoritativeDir; + int state_disabled = (get_or_state()->LastWritten == -1); + + if (consensus_disabled || config_disabled || dirauth_disabled || + state_disabled) { + log_info(LD_CIRC, + "CircuitBuildTime learning is disabled. " + "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d", + consensus_disabled, config_disabled, dirauth_disabled, + state_disabled); + return 1; + } else { + return 0; + } + } +} + +/** + * Retrieve and bounds-check the cbtmaxtimeouts consensus paramter. + * + * Effect: When this many timeouts happen in the last 'cbtrecentcount' + * circuit attempts, the client should discard all of its history and + * begin learning a fresh timeout value. + */ +static int32_t +circuit_build_times_max_timeouts(void) +{ + return networkstatus_get_param(NULL, "cbtmaxtimeouts", + CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT, + CBT_MIN_MAX_RECENT_TIMEOUT_COUNT, + CBT_MAX_MAX_RECENT_TIMEOUT_COUNT); +} + +/** + * Retrieve and bounds-check the cbtnummodes consensus paramter. + * + * Effect: This value governs how many modes to use in the weighted + * average calculation of Pareto parameter Xm. A value of 3 introduces + * some bias (2-5% of CDF) under ideal conditions, but allows for better + * performance in the event that a client chooses guard nodes of radically + * different performance characteristics. + */ +static int32_t +circuit_build_times_default_num_xm_modes(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbtnummodes", + CBT_DEFAULT_NUM_XM_MODES, + CBT_MIN_NUM_XM_MODES, + CBT_MAX_NUM_XM_MODES); + return num; +} + +/** + * Retrieve and bounds-check the cbtmincircs consensus paramter. + * + * Effect: This is the minimum number of circuits to build before + * computing a timeout. + */ +static int32_t +circuit_build_times_min_circs_to_observe(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbtmincircs", + CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE, + CBT_MIN_MIN_CIRCUITS_TO_OBSERVE, + CBT_MAX_MIN_CIRCUITS_TO_OBSERVE); + return num; +} + +/** Return true iff cbt has recorded enough build times that we + * want to start acting on the timeout it implies. */ +int +circuit_build_times_enough_to_compute(circuit_build_times_t *cbt) +{ + return cbt->total_build_times >= circuit_build_times_min_circs_to_observe(); +} + +/** + * Retrieve and bounds-check the cbtquantile consensus paramter. + * + * Effect: This is the position on the quantile curve to use to set the + * timeout value. It is a percent (10-99). + */ +double +circuit_build_times_quantile_cutoff(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbtquantile", + CBT_DEFAULT_QUANTILE_CUTOFF, + CBT_MIN_QUANTILE_CUTOFF, + CBT_MAX_QUANTILE_CUTOFF); + return num/100.0; +} + +int +circuit_build_times_get_bw_scale(networkstatus_t *ns) +{ + return networkstatus_get_param(ns, "bwweightscale", + BW_WEIGHT_SCALE, + BW_MIN_WEIGHT_SCALE, + BW_MAX_WEIGHT_SCALE); +} + +/** + * Retrieve and bounds-check the cbtclosequantile consensus paramter. + * + * Effect: This is the position on the quantile curve to use to set the + * timeout value to use to actually close circuits. It is a percent + * (0-99). + */ +static double +circuit_build_times_close_quantile(void) +{ + int32_t param; + /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */ + int32_t min = (int)tor_lround(100*circuit_build_times_quantile_cutoff()); + param = networkstatus_get_param(NULL, "cbtclosequantile", + CBT_DEFAULT_CLOSE_QUANTILE, + CBT_MIN_CLOSE_QUANTILE, + CBT_MAX_CLOSE_QUANTILE); + if (param < min) { + log_warn(LD_DIR, "Consensus parameter cbtclosequantile is " + "too small, raising to %d", min); + param = min; + } + return param / 100.0; +} + +/** + * Retrieve and bounds-check the cbttestfreq consensus paramter. + * + * Effect: Describes how often in seconds to build a test circuit to + * gather timeout values. Only applies if less than 'cbtmincircs' + * have been recorded. + */ +static int32_t +circuit_build_times_test_frequency(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbttestfreq", + CBT_DEFAULT_TEST_FREQUENCY, + CBT_MIN_TEST_FREQUENCY, + CBT_MAX_TEST_FREQUENCY); + return num; +} + +/** + * Retrieve and bounds-check the cbtmintimeout consensus paramter. + * + * Effect: This is the minimum allowed timeout value in milliseconds. + * The minimum is to prevent rounding to 0 (we only check once + * per second). + */ +static int32_t +circuit_build_times_min_timeout(void) +{ + int32_t num = networkstatus_get_param(NULL, "cbtmintimeout", + CBT_DEFAULT_TIMEOUT_MIN_VALUE, + CBT_MIN_TIMEOUT_MIN_VALUE, + CBT_MAX_TIMEOUT_MIN_VALUE); + return num; +} + +/** + * Retrieve and bounds-check the cbtinitialtimeout consensus paramter. + * + * Effect: This is the timeout value to use before computing a timeout, + * in milliseconds. + */ +int32_t +circuit_build_times_initial_timeout(void) +{ + int32_t min = circuit_build_times_min_timeout(); + int32_t param = networkstatus_get_param(NULL, "cbtinitialtimeout", + CBT_DEFAULT_TIMEOUT_INITIAL_VALUE, + CBT_MIN_TIMEOUT_INITIAL_VALUE, + CBT_MAX_TIMEOUT_INITIAL_VALUE); + if (param < min) { + log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, " + "raising to %d", min); + param = min; + } + return param; +} + +/** + * Retrieve and bounds-check the cbtrecentcount consensus paramter. + * + * Effect: This is the number of circuit build times to keep track of + * for deciding if we hit cbtmaxtimeouts and need to reset our state + * and learn a new timeout. + */ +static int32_t +circuit_build_times_recent_circuit_count(networkstatus_t *ns) +{ + return networkstatus_get_param(ns, "cbtrecentcount", + CBT_DEFAULT_RECENT_CIRCUITS, + CBT_MIN_RECENT_CIRCUITS, + CBT_MAX_RECENT_CIRCUITS); +} + +/** + * This function is called when we get a consensus update. + * + * It checks to see if we have changed any consensus parameters + * that require reallocation or discard of previous stats. + */ +void +circuit_build_times_new_consensus_params(circuit_build_times_t *cbt, + networkstatus_t *ns) +{ + int32_t num = circuit_build_times_recent_circuit_count(ns); + + if (num > 0 && num != cbt->liveness.num_recent_circs) { + int8_t *recent_circs; + log_notice(LD_CIRC, "The Tor Directory Consensus has changed how many " + "circuits we must track to detect network failures from %d " + "to %d.", cbt->liveness.num_recent_circs, num); + + tor_assert(cbt->liveness.timeouts_after_firsthop); + + /* + * Technically this is a circular array that we are reallocating + * and memcopying. However, since it only consists of either 1s + * or 0s, and is only used in a statistical test to determine when + * we should discard our history after a sufficient number of 1's + * have been reached, it is fine if order is not preserved or + * elements are lost. + * + * cbtrecentcount should only be changing in cases of severe network + * distress anyway, so memory correctness here is paramount over + * doing acrobatics to preserve the array. + */ + recent_circs = tor_malloc_zero(sizeof(int8_t)*num); + memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop, + sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs)); + + // Adjust the index if it needs it. + if (num < cbt->liveness.num_recent_circs) { + cbt->liveness.after_firsthop_idx = MIN(num-1, + cbt->liveness.after_firsthop_idx); + } + + tor_free(cbt->liveness.timeouts_after_firsthop); + cbt->liveness.timeouts_after_firsthop = recent_circs; + cbt->liveness.num_recent_circs = num; + } +} + +/** Make a note that we're running unit tests (rather than running Tor + * itself), so we avoid clobbering our state file. */ +void +circuitbuild_running_unit_tests(void) +{ + unit_tests = 1; +} + +/** + * Return the initial default or configured timeout in milliseconds + */ +static double +circuit_build_times_get_initial_timeout(void) +{ + double timeout; + if (!unit_tests && get_options()->CircuitBuildTimeout) { + timeout = get_options()->CircuitBuildTimeout*1000; + if (timeout < circuit_build_times_min_timeout()) { + log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds", + circuit_build_times_min_timeout()/1000); + timeout = circuit_build_times_min_timeout(); + } + } else { + timeout = circuit_build_times_initial_timeout(); + } + return timeout; +} + +/** + * Reset the build time state. + * + * Leave estimated parameters, timeout and network liveness intact + * for future use. + */ +void +circuit_build_times_reset(circuit_build_times_t *cbt) +{ + memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times)); + cbt->total_build_times = 0; + cbt->build_times_idx = 0; + cbt->have_computed_timeout = 0; +} + +/** + * Initialize the buildtimes structure for first use. + * + * Sets the initial timeout values based on either the config setting, + * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE). + */ +void +circuit_build_times_init(circuit_build_times_t *cbt) +{ + memset(cbt, 0, sizeof(*cbt)); + cbt->liveness.num_recent_circs = + circuit_build_times_recent_circuit_count(NULL); + cbt->liveness.timeouts_after_firsthop = tor_malloc_zero(sizeof(int8_t)* + cbt->liveness.num_recent_circs); + cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout(); + control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET); +} + +#if 0 +/** + * Rewind our build time history by n positions. + */ +static void +circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n) +{ + int i = 0; + + cbt->build_times_idx -= n; + cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE; + + for (i = 0; i < n; i++) { + cbt->circuit_build_times[(i+cbt->build_times_idx) + %CBT_NCIRCUITS_TO_OBSERVE]=0; + } + + if (cbt->total_build_times > n) { + cbt->total_build_times -= n; + } else { + cbt->total_build_times = 0; + } + + log_info(LD_CIRC, + "Rewound history by %d places. Current index: %d. " + "Total: %d", n, cbt->build_times_idx, cbt->total_build_times); +} +#endif + +/** + * Add a new build time value time to the set of build times. Time + * units are milliseconds. + * + * circuit_build_times cbt</a> is a circular array, so loop around when + * array is full. + */ +int +circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time) +{ + if (time <= 0 || time > CBT_BUILD_TIME_MAX) { + log_warn(LD_BUG, "Circuit build time is too large (%u)." + "This is probably a bug.", time); + tor_fragile_assert(); + return -1; + } + + log_debug(LD_CIRC, "Adding circuit build time %u", time); + + cbt->circuit_build_times[cbt->build_times_idx] = time; + cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE; + if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE) + cbt->total_build_times++; + + if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) { + /* Save state every n circuit builds */ + if (!unit_tests && !get_options()->AvoidDiskWrites) + or_state_mark_dirty(get_or_state(), 0); + } + + return 0; +} + +/** + * Return maximum circuit build time + */ +static build_time_t +circuit_build_times_max(circuit_build_times_t *cbt) +{ + int i = 0; + build_time_t max_build_time = 0; + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] > max_build_time + && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED) + max_build_time = cbt->circuit_build_times[i]; + } + return max_build_time; +} + +#if 0 +/** Return minimum circuit build time */ +build_time_t +circuit_build_times_min(circuit_build_times_t *cbt) +{ + int i = 0; + build_time_t min_build_time = CBT_BUILD_TIME_MAX; + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */ + cbt->circuit_build_times[i] < min_build_time) + min_build_time = cbt->circuit_build_times[i]; + } + if (min_build_time == CBT_BUILD_TIME_MAX) { + log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!"); + } + return min_build_time; +} +#endif + +/** + * Calculate and return a histogram for the set of build times. + * + * Returns an allocated array of histrogram bins representing + * the frequency of index*CBT_BIN_WIDTH millisecond + * build times. Also outputs the number of bins in nbins. + * + * The return value must be freed by the caller. + */ +static uint32_t * +circuit_build_times_create_histogram(circuit_build_times_t *cbt, + build_time_t *nbins) +{ + uint32_t *histogram; + build_time_t max_build_time = circuit_build_times_max(cbt); + int i, c; + + *nbins = 1 + (max_build_time / CBT_BIN_WIDTH); + histogram = tor_malloc_zero(*nbins * sizeof(build_time_t)); + + // calculate histogram + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] == 0 + || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) + continue; /* 0 <-> uninitialized */ + + c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH); + histogram[c]++; + } + + return histogram; +} + +/** + * Return the Pareto start-of-curve parameter Xm. + * + * Because we are not a true Pareto curve, we compute this as the + * weighted average of the N=3 most frequent build time bins. + */ +static build_time_t +circuit_build_times_get_xm(circuit_build_times_t *cbt) +{ + build_time_t i, nbins; + build_time_t *nth_max_bin; + int32_t bin_counts=0; + build_time_t ret = 0; + uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins); + int n=0; + int num_modes = circuit_build_times_default_num_xm_modes(); + + // Only use one mode if < 1000 buildtimes. Not enough data + // for multiple. + if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE) + num_modes = 1; + + nth_max_bin = (build_time_t*)tor_malloc_zero(num_modes*sizeof(build_time_t)); + + for (i = 0; i < nbins; i++) { + if (histogram[i] >= histogram[nth_max_bin[0]]) { + nth_max_bin[0] = i; + } + + for (n = 1; n < num_modes; n++) { + if (histogram[i] >= histogram[nth_max_bin[n]] && + (!histogram[nth_max_bin[n-1]] + || histogram[i] < histogram[nth_max_bin[n-1]])) { + nth_max_bin[n] = i; + } + } + } + + for (n = 0; n < num_modes; n++) { + bin_counts += histogram[nth_max_bin[n]]; + ret += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]]; + log_info(LD_CIRC, "Xm mode #%d: %u %u", n, CBT_BIN_TO_MS(nth_max_bin[n]), + histogram[nth_max_bin[n]]); + } + + ret /= bin_counts; + tor_free(histogram); + tor_free(nth_max_bin); + + return ret; +} + +/** + * Output a histogram of current circuit build times to + * the or_state_t state structure. + */ +void +circuit_build_times_update_state(circuit_build_times_t *cbt, + or_state_t *state) +{ + uint32_t *histogram; + build_time_t i = 0; + build_time_t nbins = 0; + config_line_t **next, *line; + + histogram = circuit_build_times_create_histogram(cbt, &nbins); + // write to state + config_free_lines(state->BuildtimeHistogram); + next = &state->BuildtimeHistogram; + *next = NULL; + + state->TotalBuildTimes = cbt->total_build_times; + state->CircuitBuildAbandonedCount = 0; + + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) + state->CircuitBuildAbandonedCount++; + } + + for (i = 0; i < nbins; i++) { + // compress the histogram by skipping the blanks + if (histogram[i] == 0) continue; + *next = line = tor_malloc_zero(sizeof(config_line_t)); + line->key = tor_strdup("CircuitBuildTimeBin"); + line->value = tor_malloc(25); + tor_snprintf(line->value, 25, "%d %d", + CBT_BIN_TO_MS(i), histogram[i]); + next = &(line->next); + } + + if (!unit_tests) { + if (!get_options()->AvoidDiskWrites) + or_state_mark_dirty(get_or_state(), 0); + } + + tor_free(histogram); +} + +/** + * Shuffle the build times array. + * + * Stolen from http://en.wikipedia.org/wiki/Fisher\u2013Yates_shuffle + */ +static void +circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt, + build_time_t *raw_times, + uint32_t num_times) +{ + uint32_t n = num_times; + if (num_times > CBT_NCIRCUITS_TO_OBSERVE) { + log_notice(LD_CIRC, "The number of circuit times that this Tor version " + "uses to calculate build times is less than the number stored " + "in your state file. Decreasing the circuit time history from " + "%d to %d.", num_times, CBT_NCIRCUITS_TO_OBSERVE); + } + + /* This code can only be run on a compact array */ + while (n-- > 1) { + int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */ + build_time_t tmp = raw_times[k]; + raw_times[k] = raw_times[n]; + raw_times[n] = tmp; + } + + /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE + * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */ + for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) { + circuit_build_times_add_time(cbt, raw_times[n]); + } +} + +/** + * Filter old synthetic timeouts that were created before the + * new right-censored Pareto calculation was deployed. + * + * Once all clients before 0.2.1.13-alpha are gone, this code + * will be unused. + */ +static int +circuit_build_times_filter_timeouts(circuit_build_times_t *cbt) +{ + int num_filtered=0, i=0; + double timeout_rate = 0; + build_time_t max_timeout = 0; + + timeout_rate = circuit_build_times_timeout_rate(cbt); + max_timeout = (build_time_t)cbt->close_ms; + + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] > max_timeout) { + build_time_t replaced = cbt->circuit_build_times[i]; + num_filtered++; + cbt->circuit_build_times[i] = CBT_BUILD_ABANDONED; + + log_debug(LD_CIRC, "Replaced timeout %d with %d", replaced, + cbt->circuit_build_times[i]); + } + } + + log_info(LD_CIRC, + "We had %d timeouts out of %d build times, " + "and filtered %d above the max of %u", + (int)(cbt->total_build_times*timeout_rate), + cbt->total_build_times, num_filtered, max_timeout); + + return num_filtered; +} + +/** + * Load histogram from state, shuffling the resulting array + * after we do so. Use this result to estimate parameters and + * calculate the timeout. + * + * Return -1 on error. + */ +int +circuit_build_times_parse_state(circuit_build_times_t *cbt, + or_state_t *state) +{ + int tot_values = 0; + uint32_t loaded_cnt = 0, N = 0; + config_line_t *line; + unsigned int i; + build_time_t *loaded_times; + int err = 0; + circuit_build_times_init(cbt); + + if (circuit_build_times_disabled()) { + return 0; + } + + /* build_time_t 0 means uninitialized */ + loaded_times = tor_malloc_zero(sizeof(build_time_t)*state->TotalBuildTimes); + + for (line = state->BuildtimeHistogram; line; line = line->next) { + smartlist_t *args = smartlist_create(); + smartlist_split_string(args, line->value, " ", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + if (smartlist_len(args) < 2) { + log_warn(LD_GENERAL, "Unable to parse circuit build times: " + "Too few arguments to CircuitBuildTime"); + err = 1; + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + break; + } else { + const char *ms_str = smartlist_get(args,0); + const char *count_str = smartlist_get(args,1); + uint32_t count, k; + build_time_t ms; + int ok; + ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0, + CBT_BUILD_TIME_MAX, &ok, NULL); + if (!ok) { + log_warn(LD_GENERAL, "Unable to parse circuit build times: " + "Unparsable bin number"); + err = 1; + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + break; + } + count = (uint32_t)tor_parse_ulong(count_str, 0, 0, + UINT32_MAX, &ok, NULL); + if (!ok) { + log_warn(LD_GENERAL, "Unable to parse circuit build times: " + "Unparsable bin count"); + err = 1; + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + break; + } + + if (loaded_cnt+count+state->CircuitBuildAbandonedCount + > state->TotalBuildTimes) { + log_warn(LD_CIRC, + "Too many build times in state file. " + "Stopping short before %d", + loaded_cnt+count); + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + break; + } + + for (k = 0; k < count; k++) { + loaded_times[loaded_cnt++] = ms; + } + N++; + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + } + } + + log_info(LD_CIRC, + "Adding %d timeouts.", state->CircuitBuildAbandonedCount); + for (i=0; i < state->CircuitBuildAbandonedCount; i++) { + loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED; + } + + if (loaded_cnt != state->TotalBuildTimes) { + log_warn(LD_CIRC, + "Corrupt state file? Build times count mismatch. " + "Read %d times, but file says %d", loaded_cnt, + state->TotalBuildTimes); + err = 1; + circuit_build_times_reset(cbt); + goto done; + } + + circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt); + + /* Verify that we didn't overwrite any indexes */ + for (i=0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (!cbt->circuit_build_times[i]) + break; + tot_values++; + } + log_info(LD_CIRC, + "Loaded %d/%d values from %d lines in circuit time histogram", + tot_values, cbt->total_build_times, N); + + if (cbt->total_build_times != tot_values + || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) { + log_warn(LD_CIRC, + "Corrupt state file? Shuffled build times mismatch. " + "Read %d times, but file says %d", tot_values, + state->TotalBuildTimes); + err = 1; + circuit_build_times_reset(cbt); + goto done; + } + + circuit_build_times_set_timeout(cbt); + + if (!state->CircuitBuildAbandonedCount && cbt->total_build_times) { + circuit_build_times_filter_timeouts(cbt); + } + + done: + tor_free(loaded_times); + return err ? -1 : 0; +} + +/** + * Estimates the Xm and Alpha parameters using + * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation + * + * The notable difference is that we use mode instead of min to estimate Xm. + * This is because our distribution is frechet-like. We claim this is + * an acceptable approximation because we are only concerned with the + * accuracy of the CDF of the tail. + */ +int +circuit_build_times_update_alpha(circuit_build_times_t *cbt) +{ + build_time_t *x=cbt->circuit_build_times; + double a = 0; + int n=0,i=0,abandoned_count=0; + build_time_t max_time=0; + + /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */ + /* We sort of cheat here and make our samples slightly more pareto-like + * and less frechet-like. */ + cbt->Xm = circuit_build_times_get_xm(cbt); + + tor_assert(cbt->Xm > 0); + + for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (!x[i]) { + continue; + } + + if (x[i] < cbt->Xm) { + a += tor_mathlog(cbt->Xm); + } else if (x[i] == CBT_BUILD_ABANDONED) { + abandoned_count++; + } else { + a += tor_mathlog(x[i]); + if (x[i] > max_time) + max_time = x[i]; + } + n++; + } + + /* + * We are erring and asserting here because this can only happen + * in codepaths other than startup. The startup state parsing code + * performs this same check, and resets state if it hits it. If we + * hit it at runtime, something serious has gone wrong. + */ + if (n!=cbt->total_build_times) { + log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n, + cbt->total_build_times); + } + tor_assert(n==cbt->total_build_times); + + if (max_time <= 0) { + /* This can happen if Xm is actually the *maximum* value in the set. + * It can also happen if we've abandoned every single circuit somehow. + * In either case, tell the caller not to compute a new build timeout. */ + log_warn(LD_BUG, + "Could not determine largest build time (%d). " + "Xm is %dms and we've abandoned %d out of %d circuits.", max_time, + cbt->Xm, abandoned_count, n); + return 0; + } + + a += abandoned_count*tor_mathlog(max_time); + + a -= n*tor_mathlog(cbt->Xm); + // Estimator comes from Eq #4 in: + // "Bayesian estimation based on trimmed samples from Pareto populations" + // by Arturo J. Fernández. We are right-censored only. + a = (n-abandoned_count)/a; + + cbt->alpha = a; + + return 1; +} + +/** + * This is the Pareto Quantile Function. It calculates the point x + * in the distribution such that F(x) = quantile (ie quantile*100% + * of the mass of the density function is below x on the curve). + * + * We use it to calculate the timeout and also to generate synthetic + * values of time for circuits that timeout before completion. + * + * See http://en.wikipedia.org/wiki/Quantile_function, + * http://en.wikipedia.org/wiki/Inverse_transform_sampling and + * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_ + * random_sample_from_Pareto_distribution + * That's right. I'll cite wikipedia all day long. + * + * Return value is in milliseconds. + */ +double +circuit_build_times_calculate_timeout(circuit_build_times_t *cbt, + double quantile) +{ + double ret; + tor_assert(quantile >= 0); + tor_assert(1.0-quantile > 0); + tor_assert(cbt->Xm > 0); + + ret = cbt->Xm/pow(1.0-quantile,1.0/cbt->alpha); + if (ret > INT32_MAX) { + ret = INT32_MAX; + } + tor_assert(ret > 0); + return ret; +} + +/** Pareto CDF */ +double +circuit_build_times_cdf(circuit_build_times_t *cbt, double x) +{ + double ret; + tor_assert(cbt->Xm > 0); + ret = 1.0-pow(cbt->Xm/x,cbt->alpha); + tor_assert(0 <= ret && ret <= 1.0); + return ret; +} + +/** + * Generate a synthetic time using our distribution parameters. + * + * The return value will be within the [q_lo, q_hi) quantile points + * on the CDF. + */ +build_time_t +circuit_build_times_generate_sample(circuit_build_times_t *cbt, + double q_lo, double q_hi) +{ + double randval = crypto_rand_double(); + build_time_t ret; + double u; + + /* Generate between [q_lo, q_hi) */ + /*XXXX This is what nextafter is supposed to be for; we should use it on the + * platforms that support it. */ + q_hi -= 1.0/(INT32_MAX); + + tor_assert(q_lo >= 0); + tor_assert(q_hi < 1); + tor_assert(q_lo < q_hi); + + u = q_lo + (q_hi-q_lo)*randval; + + tor_assert(0 <= u && u < 1.0); + /* circuit_build_times_calculate_timeout returns <= INT32_MAX */ + ret = (build_time_t) + tor_lround(circuit_build_times_calculate_timeout(cbt, u)); + tor_assert(ret > 0); + return ret; +} + +/** + * Estimate an initial alpha parameter by solving the quantile + * function with a quantile point and a specific timeout value. + */ +void +circuit_build_times_initial_alpha(circuit_build_times_t *cbt, + double quantile, double timeout_ms) +{ + // Q(u) = Xm/((1-u)^(1/a)) + // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout + // CircBuildTimeout = Xm/((1-0.8))^(1/a)) + // CircBuildTimeout = Xm*((1-0.8))^(-1/a)) + // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a) + // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a + tor_assert(quantile >= 0); + tor_assert(cbt->Xm > 0); + cbt->alpha = tor_mathlog(1.0-quantile)/ + (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms)); + tor_assert(cbt->alpha > 0); +} + +/** + * Returns true if we need circuits to be built + */ +int +circuit_build_times_needs_circuits(circuit_build_times_t *cbt) +{ + /* Return true if < MIN_CIRCUITS_TO_OBSERVE */ + return !circuit_build_times_enough_to_compute(cbt); +} + +/** + * Returns true if we should build a timeout test circuit + * right now. + */ +int +circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt) +{ + return circuit_build_times_needs_circuits(cbt) && + approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency(); +} + +/** + * Called to indicate that the network showed some signs of liveness, + * i.e. we received a cell. + * + * This is used by circuit_build_times_network_check_live() to decide + * if we should record the circuit build timeout or not. + * + * This function is called every time we receive a cell. Avoid + * syscalls, events, and other high-intensity work. + */ +void +circuit_build_times_network_is_live(circuit_build_times_t *cbt) +{ + time_t now = approx_time(); + if (cbt->liveness.nonlive_timeouts > 0) { + log_notice(LD_CIRC, + "Tor now sees network activity. Restoring circuit build " + "timeout recording. Network was down for %d seconds " + "during %d circuit attempts.", + (int)(now - cbt->liveness.network_last_live), + cbt->liveness.nonlive_timeouts); + } + cbt->liveness.network_last_live = now; + cbt->liveness.nonlive_timeouts = 0; +} + +/** + * Called to indicate that we completed a circuit. Because this circuit + * succeeded, it doesn't count as a timeout-after-the-first-hop. + * + * This is used by circuit_build_times_network_check_changed() to determine + * if we had too many recent timeouts and need to reset our learned timeout + * to something higher. + */ +void +circuit_build_times_network_circ_success(circuit_build_times_t *cbt) +{ + cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx] = 0; + cbt->liveness.after_firsthop_idx++; + cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs; +} + +/** + * A circuit just timed out. If it failed after the first hop, record it + * in our history for later deciding if the network speed has changed. + * + * This is used by circuit_build_times_network_check_changed() to determine + * if we had too many recent timeouts and need to reset our learned timeout + * to something higher. + */ +static void +circuit_build_times_network_timeout(circuit_build_times_t *cbt, + int did_onehop) +{ + if (did_onehop) { + cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]=1; + cbt->liveness.after_firsthop_idx++; + cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs; + } +} -/********* START VARIABLES **********/ +/** + * A circuit was just forcibly closed. If there has been no recent network + * activity at all, but this circuit was launched back when we thought the + * network was live, increment the number of "nonlive" circuit timeouts. + * + * This is used by circuit_build_times_network_check_live() to decide + * if we should record the circuit build timeout or not. + */ +static void +circuit_build_times_network_close(circuit_build_times_t *cbt, + int did_onehop, time_t start_time) +{ + time_t now = time(NULL); + /* + * Check if this is a timeout that was for a circuit that spent its + * entire existence during a time where we have had no network activity. + */ + if (cbt->liveness.network_last_live < start_time) { + if (did_onehop) { + char last_live_buf[ISO_TIME_LEN+1]; + char start_time_buf[ISO_TIME_LEN+1]; + char now_buf[ISO_TIME_LEN+1]; + format_local_iso_time(last_live_buf, cbt->liveness.network_last_live); + format_local_iso_time(start_time_buf, start_time); + format_local_iso_time(now_buf, now); + log_warn(LD_BUG, + "Circuit somehow completed a hop while the network was " + "not live. Network was last live at %s, but circuit launched " + "at %s. It's now %s.", last_live_buf, start_time_buf, + now_buf); + } + cbt->liveness.nonlive_timeouts++; + if (cbt->liveness.nonlive_timeouts == 1) { + log_notice(LD_CIRC, + "Tor has not observed any network activity for the past %d " + "seconds. Disabling circuit build timeout recording.", + (int)(now - cbt->liveness.network_last_live)); + } else { + log_info(LD_CIRC, + "Got non-live timeout. Current count is: %d", + cbt->liveness.nonlive_timeouts); + } + } +} -/** A global list of all circuits at this hop. */ -extern circuit_t *global_circuitlist; +/** + * When the network is not live, we do not record circuit build times. + * + * The network is considered not live if there has been at least one + * circuit build that began and ended (had its close_ms measurement + * period expire) since we last received a cell. + * + * Also has the side effect of rewinding the circuit time history + * in the case of recent liveness changes. + */ +int +circuit_build_times_network_check_live(circuit_build_times_t *cbt) +{ + if (cbt->liveness.nonlive_timeouts > 0) { + return 0; + } -/** An entry_guard_t represents our information about a chosen long-term - * first hop, known as a "helper" node in the literature. We can't just - * use a routerinfo_t, since we want to remember these even when we - * don't have a directory. */ -typedef struct { - char nickname[MAX_NICKNAME_LEN+1]; - char identity[DIGEST_LEN]; - time_t chosen_on_date; /**< Approximately when was this guard added? - * "0" if we don't know. */ - char *chosen_by_version; /**< What tor version added this guard? NULL - * if we don't know. */ - unsigned int made_contact : 1; /**< 0 if we have never connected to this - * router, 1 if we have. */ - unsigned int can_retry : 1; /**< Should we retry connecting to this entry, - * in spite of having it marked as unreachable?*/ - time_t bad_since; /**< 0 if this guard is currently usable, or the time at - * which it was observed to become (according to the - * directory or the user configuration) unusable. */ - time_t unreachable_since; /**< 0 if we can connect to this guard, or the - * time at which we first noticed we couldn't - * connect to it. */ - time_t last_attempted; /**< 0 if we can connect to this guard, or the time - * at which we last failed to connect to it. */ -} entry_guard_t; + return 1; +} -/** A list of our chosen entry guards. */ -static smartlist_t *entry_guards = NULL; -/** A value of 1 means that the entry_guards list has changed - * and those changes need to be flushed to disk. */ -static int entry_guards_dirty = 0; +/** + * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of + * the past RECENT_CIRCUITS time out after the first hop. Used to detect + * if the network connection has changed significantly, and if so, + * resets our circuit build timeout to the default. + * + * Also resets the entire timeout history in this case and causes us + * to restart the process of building test circuits and estimating a + * new timeout. + */ +int +circuit_build_times_network_check_changed(circuit_build_times_t *cbt) +{ + int total_build_times = cbt->total_build_times; + int timeout_count=0; + int i; -/********* END VARIABLES ************/ + /* how many of our recent circuits made it to the first hop but then + * timed out? */ + for (i = 0; i < cbt->liveness.num_recent_circs; i++) { + timeout_count += cbt->liveness.timeouts_after_firsthop[i]; + } -static int circuit_deliver_create_cell(circuit_t *circ, - uint8_t cell_type, const char *payload); -static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit); -static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath); -static int onion_extend_cpath(origin_circuit_t *circ); -static int count_acceptable_routers(smartlist_t *routers); -static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice); + /* If 80% of our recent circuits are timing out after the first hop, + * we need to re-estimate a new initial alpha and timeout. */ + if (timeout_count < circuit_build_times_max_timeouts()) { + return 0; + } -static void entry_guards_changed(void); + circuit_build_times_reset(cbt); + memset(cbt->liveness.timeouts_after_firsthop, 0, + sizeof(*cbt->liveness.timeouts_after_firsthop)* + cbt->liveness.num_recent_circs); + cbt->liveness.after_firsthop_idx = 0; + + /* Check to see if this has happened before. If so, double the timeout + * to give people on abysmally bad network connections a shot at access */ + if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) { + if (cbt->timeout_ms > INT32_MAX/2 || cbt->close_ms > INT32_MAX/2) { + log_warn(LD_CIRC, "Insanely large circuit build timeout value. " + "(timeout = %lfmsec, close = %lfmsec)", + cbt->timeout_ms, cbt->close_ms); + } else { + cbt->timeout_ms *= 2; + cbt->close_ms *= 2; + } + } else { + cbt->close_ms = cbt->timeout_ms + = circuit_build_times_get_initial_timeout(); + } + + control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET); + + log_notice(LD_CIRC, + "Your network connection speed appears to have changed. Resetting " + "timeout to %lds after %d timeouts and %d buildtimes.", + tor_lround(cbt->timeout_ms/1000), timeout_count, + total_build_times); + + return 1; +} + +/** + * Count the number of timeouts in a set of cbt data. + */ +double +circuit_build_times_timeout_rate(const circuit_build_times_t *cbt) +{ + int i=0,timeouts=0; + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] >= cbt->timeout_ms) { + timeouts++; + } + } + + if (!cbt->total_build_times) + return 0; + + return ((double)timeouts)/cbt->total_build_times; +} + +/** + * Count the number of closed circuits in a set of cbt data. + */ +double +circuit_build_times_close_rate(const circuit_build_times_t *cbt) +{ + int i=0,closed=0; + for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) { + closed++; + } + } + + if (!cbt->total_build_times) + return 0; + + return ((double)closed)/cbt->total_build_times; +} + +/** + * Store a timeout as a synthetic value. + * + * Returns true if the store was successful and we should possibly + * update our timeout estimate. + */ +int +circuit_build_times_count_close(circuit_build_times_t *cbt, + int did_onehop, + time_t start_time) +{ + if (circuit_build_times_disabled()) { + cbt->close_ms = cbt->timeout_ms + = circuit_build_times_get_initial_timeout(); + return 0; + } + + /* Record this force-close to help determine if the network is dead */ + circuit_build_times_network_close(cbt, did_onehop, start_time); + + /* Only count timeouts if network is live.. */ + if (!circuit_build_times_network_check_live(cbt)) { + return 0; + } + + circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED); + return 1; +} + +/** + * Update timeout counts to determine if we need to expire + * our build time history due to excessive timeouts. + * + * We do not record any actual time values at this stage; + * we are only interested in recording the fact that a timeout + * happened. We record the time values via + * circuit_build_times_count_close() and circuit_build_times_add_time(). + */ +void +circuit_build_times_count_timeout(circuit_build_times_t *cbt, + int did_onehop) +{ + if (circuit_build_times_disabled()) { + cbt->close_ms = cbt->timeout_ms + = circuit_build_times_get_initial_timeout(); + return; + } + + /* Register the fact that a timeout just occurred. */ + circuit_build_times_network_timeout(cbt, did_onehop); + + /* If there are a ton of timeouts, we should reset + * the circuit build timeout. */ + circuit_build_times_network_check_changed(cbt); +} + +/** + * Estimate a new timeout based on history and set our timeout + * variable accordingly. + */ +static int +circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt) +{ + build_time_t max_time; + if (!circuit_build_times_enough_to_compute(cbt)) + return 0; + + if (!circuit_build_times_update_alpha(cbt)) + return 0; + + cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt, + circuit_build_times_quantile_cutoff()); + + cbt->close_ms = circuit_build_times_calculate_timeout(cbt, + circuit_build_times_close_quantile()); + + max_time = circuit_build_times_max(cbt); + + /* Sometimes really fast guard nodes give us such a steep curve + * that this ends up being not that much greater than timeout_ms. + * Make it be at least 1 min to handle this case. */ + cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout()); + + if (cbt->timeout_ms > max_time) { + log_notice(LD_CIRC, + "Circuit build timeout of %dms is beyond the maximum build " + "time we have ever observed. Capping it to %dms.", + (int)cbt->timeout_ms, max_time); + cbt->timeout_ms = max_time; + } + + if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) { + log_info(LD_CIRC, + "Circuit build measurement period of %dms is more than twice " + "the maximum build time we have ever observed. Capping it to " + "%dms.", (int)cbt->close_ms, 2*max_time); + cbt->close_ms = 2*max_time; + } + + cbt->have_computed_timeout = 1; + return 1; +} + +/** + * Exposed function to compute a new timeout. Dispatches events and + * also filters out extremely high timeout values. + */ +void +circuit_build_times_set_timeout(circuit_build_times_t *cbt) +{ + long prev_timeout = tor_lround(cbt->timeout_ms/1000); + double timeout_rate; + + if (!circuit_build_times_set_timeout_worker(cbt)) + return; + + if (cbt->timeout_ms < circuit_build_times_min_timeout()) { + log_warn(LD_CIRC, "Set buildtimeout to low value %lfms. Setting to %dms", + cbt->timeout_ms, circuit_build_times_min_timeout()); + cbt->timeout_ms = circuit_build_times_min_timeout(); + if (cbt->close_ms < cbt->timeout_ms) { + /* This shouldn't happen because of MAX() in timeout_worker above, + * but doing it just in case */ + cbt->close_ms = circuit_build_times_initial_timeout(); + } + } + + control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED); + + timeout_rate = circuit_build_times_timeout_rate(cbt); + + if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) { + log_notice(LD_CIRC, + "Based on %d circuit times, it looks like we don't need to " + "wait so long for circuits to finish. We will now assume a " + "circuit is too slow to use after waiting %ld seconds.", + cbt->total_build_times, + tor_lround(cbt->timeout_ms/1000)); + log_info(LD_CIRC, + "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf", + cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, + timeout_rate); + } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) { + log_notice(LD_CIRC, + "Based on %d circuit times, it looks like we need to wait " + "longer for circuits to finish. We will now assume a " + "circuit is too slow to use after waiting %ld seconds.", + cbt->total_build_times, + tor_lround(cbt->timeout_ms/1000)); + log_info(LD_CIRC, + "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf", + cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, + timeout_rate); + } else { + log_info(LD_CIRC, + "Set circuit build timeout to %lds (%lfms, %lfms, Xm: %d, a: %lf," + " r: %lf) based on %d circuit times", + tor_lround(cbt->timeout_ms/1000), + cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate, + cbt->total_build_times); + } +} /** Iterate over values of circ_id, starting from conn-\>next_circ_id, * and with the high bit specified by conn-\>circ_id_type, until we get @@@ -1494,21 -112,21 +1494,21 @@@ circuit_list_path_impl(origin_circuit_ crypt_path_t *hop; smartlist_t *elements; const char *states[] = {"closed", "waiting for keys", "open"}; - char buf[128]; char *s; elements = smartlist_create(); if (verbose) { const char *nickname = build_state_get_exit_nickname(circ->build_state); - tor_snprintf(buf, sizeof(buf), "%s%s circ (length %d%s%s):", + char *cp; + tor_asprintf(&cp, "%s%s circ (length %d%s%s):", circ->build_state->is_internal ? "internal" : "exit", circ->build_state->need_uptime ? " (high-uptime)" : "", circ->build_state->desired_path_len, circ->_base.state == CIRCUIT_STATE_OPEN ? "" : ", exit ", circ->_base.state == CIRCUIT_STATE_OPEN ? "" : (nickname?nickname:"*unnamed*")); - smartlist_add(elements, tor_strdup(buf)); + smartlist_add(elements, cp); } hop = circ->cpath; @@@ -1530,7 -148,8 +1530,7 @@@ router_get_verbose_nickname(elt, ri); } else if ((rs = router_get_consensus_status_by_id(id))) { routerstatus_get_verbose_nickname(elt, rs); - } else if (hop->extend_info->nickname && - is_legal_nickname(hop->extend_info->nickname)) { + } else if (is_legal_nickname(hop->extend_info->nickname)) { elt[0] = '$'; base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN); elt[HEX_DIGEST_LEN+1]= '~'; @@@ -1598,7 -217,7 +1598,7 @@@ voi circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ) { char *s = circuit_list_path(circ,1); - log(severity,domain,"%s",s); + tor_log(severity,domain,"%s",s); tor_free(s); } @@@ -1650,7 -269,7 +1650,7 @@@ static in onion_populate_cpath(origin_circuit_t *circ) { int r; -again: + again: r = onion_extend_cpath(circ); if (r < 0) { log_info(LD_CIRC,"Generating cpath hop failed."); @@@ -1742,10 -361,9 +1742,10 @@@ circuit_handle_first_hop(origin_circuit if (!n_conn) { /* not currently connected in a useful way. */ - const char *name = firsthop->extend_info->nickname ? + const char *name = strlen(firsthop->extend_info->nickname) ? firsthop->extend_info->nickname : fmt_addr(&firsthop->extend_info->addr); - log_info(LD_CIRC, "Next router is %s: %s ", safe_str(name), msg?msg:"???"); + log_info(LD_CIRC, "Next router is %s: %s ", + safe_str_client(name), msg?msg:"???"); circ->_base.n_hop = extend_info_dup(firsthop->extend_info); if (should_launch) { @@@ -1888,8 -506,7 +1888,8 @@@ circuit_deliver_create_cell(circuit_t * cell.circ_id = circ->n_circ_id; memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN); - append_cell_to_circuit_queue(circ, circ->n_conn, &cell, CELL_DIRECTION_OUT); + append_cell_to_circuit_queue(circ, circ->n_conn, &cell, + CELL_DIRECTION_OUT, 0); if (CIRCUIT_IS_ORIGIN(circ)) { /* mark it so it gets better rate limiting treatment. */ @@@ -1919,7 -536,7 +1919,7 @@@ inform_testing_reachability(void "CHECKING_REACHABILITY DIRADDRESS=%s:%d", me->address, me->dir_port); } - log(LOG_NOTICE, LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... " + log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... " "(this may take up to %d minutes -- look for log " "messages indicating success)", me->address, me->or_port, @@@ -1952,18 -569,6 +1952,18 @@@ should_use_create_fast_for_circuit(orig return 1; } +/** Return true if circ is the type of circuit we want to count + * timeouts from. In particular, we want it to have not completed yet + * (already completing indicates we cannibalized it), and we want it to + * have exactly three hops. + */ +int +circuit_timeout_want_to_count_circ(origin_circuit_t *circ) +{ + return !circ->has_opened + && circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN; +} + /** This is the backbone function for building circuits. * * If circ's first hop is closed, then we need to build a create @@@ -2037,42 -642,15 +2037,42 @@@ circuit_send_next_onion_skin(origin_cir if (!hop) { /* done building the circuit. whew. */ circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN); + if (circuit_timeout_want_to_count_circ(circ)) { + struct timeval end; + long timediff; + tor_gettimeofday(&end); + timediff = tv_mdiff(&circ->_base.highres_created, &end); + + /* + * If the circuit build time is much greater than we would have cut + * it off at, we probably had a suspend event along this codepath, + * and we should discard the value. + */ + if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) { + log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. " + "Assuming clock jump. Purpose %d", timediff, + circ->_base.purpose); + } else if (!circuit_build_times_disabled()) { + /* Only count circuit times if the network is live */ + if (circuit_build_times_network_check_live(&circ_times)) { + circuit_build_times_add_time(&circ_times, (build_time_t)timediff); + circuit_build_times_set_timeout(&circ_times); + } + + if (circ->_base.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { + circuit_build_times_network_circ_success(&circ_times); + } + } + } log_info(LD_CIRC,"circuit built!"); circuit_reset_failure_count(0); if (circ->build_state->onehop_tunnel) control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0); - if (!has_completed_circuit && !circ->build_state->onehop_tunnel) { + if (!can_complete_circuit && !circ->build_state->onehop_tunnel) { or_options_t *options = get_options(); - has_completed_circuit=1; + can_complete_circuit=1; /* FFFF Log a count of known routers here */ - log(LOG_NOTICE, LD_GENERAL, + log_notice(LD_GENERAL, "Tor has successfully opened a circuit. " "Looks like client functionality is working."); control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0); @@@ -2084,10 -662,6 +2084,10 @@@ } circuit_rep_hist_note_result(circ); circuit_has_opened(circ); /* do other actions as necessary */ + + /* We're done with measurement circuits here. Just close them */ + if (circ->_base.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) + circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED); return 0; } @@@ -2131,13 -705,13 +2131,13 @@@ voi circuit_note_clock_jumped(int seconds_elapsed) { int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE; - log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; " + tor_log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; " "assuming established circuits no longer work.", seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed, seconds_elapsed >=0 ? "forward" : "backward"); control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d", seconds_elapsed); - has_completed_circuit=0; /* so it'll log when it works again */ + can_complete_circuit=0; /* so it'll log when it works again */ control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s", "CLOCK_JUMPED"); circuit_mark_all_unused_circs(); @@@ -2370,9 -944,10 +2370,9 @@@ circuit_finish_handshake(origin_circuit return -END_CIRC_REASON_TORPROTOCOL; } - if (hop->dh_handshake_state) { - crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */ - hop->dh_handshake_state = NULL; - } + crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */ + hop->dh_handshake_state = NULL; + memset(hop->fast_handshake_state, 0, sizeof(hop->fast_handshake_state)); if (circuit_init_cpath_crypto(hop, keys, 0)<0) { @@@ -2460,8 -1035,8 +2460,8 @@@ onionskin_answer(or_circuit_t *circ, ui cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2); log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.", - (unsigned int)*(uint32_t*)(keys), - (unsigned int)*(uint32_t*)(keys+20)); + (unsigned int)get_uint32(keys), + (unsigned int)get_uint32(keys+20)); if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) { log_warn(LD_BUG,"Circuit initialization failed"); tor_free(tmp_cpath); @@@ -2482,7 -1057,7 +2482,7 @@@ circ->is_first_hop = (cell_type == CELL_CREATED_FAST); append_cell_to_circuit_queue(TO_CIRCUIT(circ), - circ->p_conn, &cell, CELL_DIRECTION_IN); + circ->p_conn, &cell, CELL_DIRECTION_IN, 0); log_debug(LD_CIRC,"Finished sending 'created' cell."); if (!is_local_addr(&circ->p_conn->_base.addr) && @@@ -2511,7 -1086,7 +2511,7 @@@ new_route_len(uint8_t purpose, extend_i tor_assert(routers); - routelen = 3; + routelen = DEFAULT_ROUTE_LEN; if (exit && purpose != CIRCUIT_PURPOSE_TESTING && purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO) @@@ -2576,8 -1151,6 +2576,8 @@@ circuit_all_predicted_ports_handled(tim smartlist_t *LongLivedServices = get_options()->LongLivedPorts; tor_assert(need_uptime); tor_assert(need_capacity); + // Always predict need_capacity + *need_capacity = 1; enough = (smartlist_len(sl) == 0); for (i = 0; i < smartlist_len(sl); ++i) { port = smartlist_get(sl, i); @@@ -2600,8 -1173,6 +2600,8 @@@ router_handles_some_port(routerinfo_t * for (i = 0; i < smartlist_len(needed_ports); ++i) { addr_policy_result_t r; + /* alignment issues aren't a worry for this dereference, since + needed_ports is explicitly a smartlist of uint16_t's */ port = *(uint16_t *)smartlist_get(needed_ports, i); tor_assert(port); r = compare_addr_to_addr_policy(0, port, router->exit_policy); @@@ -2684,16 -1255,9 +2684,16 @@@ choose_good_exit_server_general(routerl n_supported[i] = -1; continue; /* skip routers that are known to be down or bad exits */ } - if (router_is_unreliable(router, need_uptime, need_capacity, 0)) { + if (router_is_unreliable(router, need_uptime, need_capacity, 0) && + (!options->ExitNodes || + !routerset_contains_router(options->ExitNodes, router))) { + /* FFFF Someday, differentiate between a routerset that names + * routers, and a routerset that names countries, and only do this + * check if they've asked for specific exit relays. Or if the country + * they ask for is rare. Or something. */ n_supported[i] = -1; - continue; /* skip routers that are not suitable */ + continue; /* skip routers that are not suitable, unless we have + * ExitNodes set, in which case we asked for it */ } if (!(router->is_valid || options->_AllowInvalid & ALLOW_INVALID_EXIT)) { /* if it's invalid and we don't want it */ @@@ -2718,7 -1282,7 +2718,7 @@@ { if (!ap_stream_wants_exit_attention(conn)) continue; /* Skip everything but APs in CIRCUIT_WAIT */ - if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), router)) { + if (connection_ap_can_use_exit(TO_EDGE_CONN(conn), router, 1)) { ++n_supported[i]; // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.", // router->nickname, i, n_supported[i]); @@@ -2760,8 -1324,7 +2760,8 @@@ routersets_get_disjunction(use, supporting, options->ExitNodes, options->_ExcludeExitNodesUnion, 1); - if (smartlist_len(use) == 0 && !options->StrictExitNodes) { + if (smartlist_len(use) == 0 && options->ExitNodes && + !options->StrictNodes) { /* give up on exitnodes and try again */ routersets_get_disjunction(use, supporting, NULL, options->_ExcludeExitNodesUnion, 1); } @@@ -2773,7 -1336,7 +2773,7 @@@ * possibly support any of them. Choose a router at random that satisfies * at least one predicted exit port. */ - int try; + int attempt; smartlist_t *needed_ports, *supporting, *use; if (best_support == -1) { @@@ -2786,20 -1349,19 +2786,20 @@@ tor_free(n_supported); return choose_good_exit_server_general(dir, 0, 0); } - log_notice(LD_CIRC, "All routers are down or won't exit -- choosing a " - "doomed exit at random."); + log_notice(LD_CIRC, "All routers are down or won't exit%s -- " + "choosing a doomed exit at random.", + options->_ExcludeExitNodesUnion ? " or are Excluded" : ""); } supporting = smartlist_create(); use = smartlist_create(); needed_ports = circuit_get_unhandled_ports(time(NULL)); - for (try = 0; try < 2; try++) { + for (attempt = 0; attempt < 2; attempt++) { /* try once to pick only from routers that satisfy a needed port, * then if there are none, pick from any that support exiting. */ for (i = 0; i < smartlist_len(dir->routers); i++) { router = smartlist_get(dir->routers, i); if (n_supported[i] != -1 && - (try || router_handles_some_port(router, needed_ports))) { + (attempt || router_handles_some_port(router, needed_ports))) { // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.", // try, router->nickname); smartlist_add(supporting, router); @@@ -2808,14 -1370,12 +2808,14 @@@ routersets_get_disjunction(use, supporting, options->ExitNodes, options->_ExcludeExitNodesUnion, 1); - if (smartlist_len(use) == 0 && !options->StrictExitNodes) { + if (smartlist_len(use) == 0 && options->ExitNodes && + !options->StrictNodes) { /* give up on exitnodes and try again */ routersets_get_disjunction(use, supporting, NULL, options->_ExcludeExitNodesUnion, 1); } - /* XXX sometimes the above results in null, when the requested - * exit node is down. we should pick it anyway. */ + /* FFF sometimes the above results in null, when the requested + * exit node is considered down by the consensus. we should pick + * it anyway, since the user asked for it. */ router = routerlist_sl_choose_by_bandwidth(use, WEIGHT_FOR_EXIT); if (router) break; @@@ -2833,10 -1393,10 +2833,10 @@@ log_info(LD_CIRC, "Chose exit server '%s'", router->nickname); return router; } - if (options->StrictExitNodes) { + if (options->ExitNodes && options->StrictNodes) { log_warn(LD_CIRC, "No specified exit routers seem to be running, and " - "StrictExitNodes is set: can't choose an exit."); + "StrictNodes is set: can't choose an exit."); } return NULL; } @@@ -2867,13 -1427,15 +2867,13 @@@ choose_good_exit_server(uint8_t purpose if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE) flags |= CRN_ALLOW_INVALID; if (is_internal) /* pick it like a middle hop */ - return router_choose_random_node(NULL, NULL, - options->ExcludeNodes, flags); + return router_choose_random_node(NULL, options->ExcludeNodes, flags); else return choose_good_exit_server_general(dir,need_uptime,need_capacity); case CIRCUIT_PURPOSE_C_ESTABLISH_REND: if (options->_AllowInvalid & ALLOW_INVALID_RENDEZVOUS) flags |= CRN_ALLOW_INVALID; - return router_choose_random_node(NULL, NULL, - options->ExcludeNodes, flags); + return router_choose_random_node(NULL, options->ExcludeNodes, flags); } log_warn(LD_BUG,"Unhandled purpose %d", purpose); tor_fragile_assert(); @@@ -2993,7 -1555,8 +2993,7 @@@ circuit_append_new_exit(origin_circuit_ state = circ->build_state; tor_assert(state); - if (state->chosen_exit) - extend_info_free(state->chosen_exit); + extend_info_free(state->chosen_exit); state->chosen_exit = extend_info_dup(exit); ++circ->build_state->desired_path_len; @@@ -3115,7 -1678,8 +3115,7 @@@ choose_good_middle_server(uint8_t purpo flags |= CRN_NEED_CAPACITY; if (options->_AllowInvalid & ALLOW_INVALID_MIDDLE) flags |= CRN_ALLOW_INVALID; - choice = router_choose_random_node(NULL, - excluded, options->ExcludeNodes, flags); + choice = router_choose_random_node(excluded, options->ExcludeNodes, flags); smartlist_free(excluded); return choice; } @@@ -3179,7 -1743,11 +3179,7 @@@ choose_good_entry_server(uint8_t purpos if (options->_AllowInvalid & ALLOW_INVALID_ENTRY) flags |= CRN_ALLOW_INVALID; - choice = router_choose_random_node( - NULL, - excluded, - options->ExcludeNodes, - flags); + choice = router_choose_random_node(excluded, options->ExcludeNodes, flags); smartlist_free(excluded); return choice; } @@@ -3300,9 -1868,9 +3300,9 @@@ extend_info_from_router(routerinfo_t *r void extend_info_free(extend_info_t *info) { - tor_assert(info); - if (info->onion_key) - crypto_free_pk_env(info->onion_key); + if (!info) + return; + crypto_free_pk_env(info->onion_key); tor_free(info); } @@@ -3361,6 -1929,8 +3361,6 @@@ entry_guard_set_status(entry_guard_t *e char buf[HEX_DIGEST_LEN+1]; int changed = 0; - tor_assert(options); - *reason = NULL; /* Do we want to mark this guard as bad? */ @@@ -3423,58 -1993,35 +3423,58 @@@ entry_is_time_to_retry(entry_guard_t *e * - Listed as either up or never yet contacted; * - Present in the routerlist; * - Listed as 'stable' or 'fast' by the current dirserver consensus, - * if demanded by need_uptime or need_capacity; - * (This check is currently redundant with the Guard flag, but in - * the future that might change. Best to leave it in for now.) + * if demanded by need_uptime or need_capacity + * (unless it's a configured EntryNode); * - Allowed by our current ReachableORAddresses config option; and - * - Currently thought to be reachable by us (unless assume_reachable + * - Currently thought to be reachable by us (unless assume_reachable * is true). + * + * If the answer is no, set *msg to an explanation of why. */ static INLINE routerinfo_t * entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity, - int assume_reachable) + int assume_reachable, const char **msg) { routerinfo_t *r; - if (e->bad_since) + or_options_t *options = get_options(); + tor_assert(msg); + + if (e->bad_since) { + *msg = "bad"; return NULL; + } /* no good if it's unreachable, unless assume_unreachable or can_retry. */ if (!assume_reachable && !e->can_retry && - e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) + e->unreachable_since && !entry_is_time_to_retry(e, time(NULL))) { + *msg = "unreachable"; return NULL; + } r = router_get_by_digest(e->identity); - if (!r) + if (!r) { + *msg = "no descriptor"; return NULL; - if (get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_BRIDGE) + } + if (get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_BRIDGE) { + *msg = "not a bridge"; return NULL; - if (!get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_GENERAL) + } + if (!get_options()->UseBridges && r->purpose != ROUTER_PURPOSE_GENERAL) { + *msg = "not general-purpose"; return NULL; - if (router_is_unreliable(r, need_uptime, need_capacity, 0)) + } + if (options->EntryNodes && + routerset_contains_router(options->EntryNodes, r)) { + /* they asked for it, they get it */ + need_uptime = need_capacity = 0; + } + if (router_is_unreliable(r, need_uptime, need_capacity, 0)) { + *msg = "not fast/stable"; return NULL; - if (!fascist_firewall_allows_or(r)) + } + if (!fascist_firewall_allows_or(r)) { + *msg = "unreachable by config"; return NULL; + } return r; } @@@ -3483,12 -2030,11 +3483,12 @@@ static in num_live_entry_guards(void) { int n = 0; + const char *msg; if (! entry_guards) return 0; SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, { - if (entry_is_live(entry, 0, 1, 0)) + if (entry_is_live(entry, 0, 1, 0, &msg)) ++n; }); return n; @@@ -3512,21 -2058,16 +3512,21 @@@ static voi log_entry_guards(int severity) { smartlist_t *elements = smartlist_create(); - char buf[1024]; char *s; SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, { - tor_snprintf(buf, sizeof(buf), "%s (%s%s)", - e->nickname, - entry_is_live(e, 0, 1, 0) ? "up " : "down ", - e->made_contact ? "made-contact" : "never-contacted"); - smartlist_add(elements, tor_strdup(buf)); + const char *msg = NULL; + char *cp; + if (entry_is_live(e, 0, 1, 0, &msg)) + tor_asprintf(&cp, "%s (up %s)", + e->nickname, + e->made_contact ? "made-contact" : "never-contacted"); + else + tor_asprintf(&cp, "%s (%s, %s)", + e->nickname, msg, + e->made_contact ? "made-contact" : "never-contacted"); + smartlist_add(elements, cp); }); s = smartlist_join_strings(elements, ",", 0, NULL); @@@ -3550,13 -2091,12 +3550,13 @@@ control_event_guard_deferred(void **/ #if 0 int n = 0; + const char *msg; or_options_t *options = get_options(); if (!entry_guards) return; SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, { - if (entry_is_live(entry, 0, 1, 0)) { + if (entry_is_live(entry, 0, 1, 0, &msg)) { if (n++ == options->NumEntryGuards) { control_event_guard(entry->nickname, entry->identity, "DEFERRED"); return; @@@ -3618,8 -2158,9 +3618,8 @@@ add_an_entry_guard(routerinfo_t *chosen /** If the use of entry guards is configured, choose more entry guards * until we have enough in the list. */ static void -pick_entry_guards(void) +pick_entry_guards(or_options_t *options) { - or_options_t *options = get_options(); int changed = 0; tor_assert(entry_guards); @@@ -3641,8 -2182,7 +3641,8 @@@ static void entry_guard_free(entry_guard_t *e) { - tor_assert(e); + if (!e) + return; tor_free(e->chosen_by_version); tor_free(e); } @@@ -3651,9 -2191,10 +3651,9 @@@ * or which was selected by a version of Tor that's known to select * entry guards badly. */ static int -remove_obsolete_entry_guards(void) +remove_obsolete_entry_guards(time_t now) { int changed = 0, i; - time_t now = time(NULL); for (i = 0; i < smartlist_len(entry_guards); ++i) { entry_guard_t *entry = smartlist_get(entry_guards, i); @@@ -3713,10 -2254,11 +3713,10 @@@ * long that we don't think they'll come up again. Return 1 if we * removed any, or 0 if we did nothing. */ static int -remove_dead_entry_guards(void) +remove_dead_entry_guards(time_t now) { char dbuf[HEX_DIGEST_LEN+1]; char tbuf[ISO_TIME_LEN+1]; - time_t now = time(NULL); int i; int changed = 0; @@@ -3751,17 -2293,19 +3751,17 @@@ * think that things are unlisted. */ void -entry_guards_compute_status(void) +entry_guards_compute_status(or_options_t *options, time_t now) { - time_t now; int changed = 0; int severity = LOG_DEBUG; - or_options_t *options; digestmap_t *reasons; + if (! entry_guards) return; - options = get_options(); - - now = time(NULL); + if (options->EntryNodes) /* reshuffle the entry guard list if needed */ + entry_nodes_should_be_added(); reasons = digestmap_new(); SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) @@@ -3778,7 -2322,7 +3778,7 @@@ } SMARTLIST_FOREACH_END(entry); - if (remove_dead_entry_guards()) + if (remove_dead_entry_guards(now)) changed = 1; severity = changed ? LOG_DEBUG : LOG_INFO; @@@ -3786,16 -2330,13 +3786,16 @@@ if (changed) { SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, entry) { const char *reason = digestmap_get(reasons, entry->identity); - log_info(LD_CIRC, "Summary: Entry '%s' is %s, %s%s%s, and %s.", + const char *live_msg = ""; + routerinfo_t *r = entry_is_live(entry, 0, 1, 0, &live_msg); + log_info(LD_CIRC, "Summary: Entry '%s' is %s, %s%s%s, and %s%s.", entry->nickname, entry->unreachable_since ? "unreachable" : "reachable", entry->bad_since ? "unusable" : "usable", reason ? ", ": "", reason ? reason : "", - entry_is_live(entry, 0, 1, 0) ? "live" : "not live"); + r ? "live" : "not live / ", + r ? "" : live_msg); } SMARTLIST_FOREACH_END(entry); log_info(LD_CIRC, " (%d/%d entry guards are usable/new)", num_live_entry_guards(), smartlist_len(entry_guards)); @@@ -3866,7 -2407,6 +3866,7 @@@ entry_guard_register_connect_status(con "Removing from the list. %d/%d entry guards usable/new.", entry->nickname, buf, num_live_entry_guards()-1, smartlist_len(entry_guards)-1); + control_event_guard(entry->nickname, entry->identity, "DROPPED"); entry_guard_free(entry); smartlist_del_keeporder(entry_guards, idx); log_entry_guards(LOG_INFO); @@@ -3903,8 -2443,7 +3903,8 @@@ if (e == entry) break; if (e->made_contact) { - routerinfo_t *r = entry_is_live(e, 0, 1, 1); + const char *msg; + routerinfo_t *r = entry_is_live(e, 0, 1, 1, &msg); if (r && e->unreachable_since) { refuse_conn = 1; e->can_retry = 1; @@@ -3935,16 -2474,16 +3935,16 @@@ static int should_add_entry_nodes = 0 void entry_nodes_should_be_added(void) { - log_info(LD_CIRC, "New EntryNodes config option detected. Will use."); + log_info(LD_CIRC, "EntryNodes config option set. Putting configured " + "relays at the front of the entry guard list."); should_add_entry_nodes = 1; } /** Add all nodes in EntryNodes that aren't currently guard nodes to the list * of guard nodes, at the front. */ static void -entry_guards_prepend_from_config(void) +entry_guards_prepend_from_config(or_options_t *options) { - or_options_t *options = get_options(); smartlist_t *entry_routers, *entry_fps; smartlist_t *old_entry_guards_on_list, *old_entry_guards_not_on_list; tor_assert(entry_guards); @@@ -3959,7 -2498,7 +3959,7 @@@ return; } - if (options->EntryNodes) { + { char *string = routerset_to_string(options->EntryNodes); log_info(LD_CIRC,"Adding configured EntryNodes '%s'.", string); tor_free(string); @@@ -4003,9 -2542,8 +4003,9 @@@ SMARTLIST_FOREACH(entry_routers, routerinfo_t *, ri, { add_an_entry_guard(ri, 0); }); - /* Finally, the remaining EntryNodes, unless we're strict */ - if (options->StrictEntryNodes) { + /* Finally, the remaining previously configured guards that are not in + * EntryNodes, unless we're strict in which case we drop them */ + if (options->StrictNodes) { SMARTLIST_FOREACH(old_entry_guards_not_on_list, entry_guard_t *, e, entry_guard_free(e)); } else { @@@ -4019,30 -2557,16 +4019,30 @@@ entry_guards_changed(); } -/** Return 1 if we're fine adding arbitrary routers out of the - * directory to our entry guard list. Else return 0. */ +/** Return 0 if we're fine adding arbitrary routers out of the + * directory to our entry guard list, or return 1 if we have a + * list already and we'd prefer to stick to it. + */ int -entry_list_can_grow(or_options_t *options) +entry_list_is_constrained(or_options_t *options) { - if (options->StrictEntryNodes) - return 0; + if (options->EntryNodes) + return 1; if (options->UseBridges) - return 0; - return 1; + return 1; + return 0; +} + +/* Are we dead set against changing our entry guard list, or would we + * change it if it means keeping Tor usable? */ +static int +entry_list_is_totally_static(or_options_t *options) +{ + if (options->EntryNodes && options->StrictNodes) + return 1; + if (options->UseBridges) + return 1; + return 0; } /** Pick a live (up and listed) entry guard from entry_guards. If @@@ -4060,9 -2584,10 +4060,9 @@@ choose_random_entry(cpath_build_state_ routerinfo_t *r = NULL; int need_uptime = state ? state->need_uptime : 0; int need_capacity = state ? state->need_capacity : 0; - int consider_exit_family = 0; + int preferred_min, consider_exit_family = 0; if (chosen_exit) { - smartlist_add(exit_family, chosen_exit); routerlist_add_family(exit_family, chosen_exit); consider_exit_family = 1; } @@@ -4071,64 -2596,38 +4071,64 @@@ entry_guards = smartlist_create(); if (should_add_entry_nodes) - entry_guards_prepend_from_config(); + entry_guards_prepend_from_config(options); - if (entry_list_can_grow(options) && - (! entry_guards || - smartlist_len(entry_guards) < options->NumEntryGuards)) - pick_entry_guards(); + if (!entry_list_is_constrained(options) && + smartlist_len(entry_guards) < options->NumEntryGuards) + pick_entry_guards(options); retry: smartlist_clear(live_entry_guards); SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, { - r = entry_is_live(entry, need_uptime, need_capacity, 0); - if (r && (!consider_exit_family || !smartlist_isin(exit_family, r))) { - smartlist_add(live_entry_guards, r); - if (!entry->made_contact) { - /* Always start with the first not-yet-contacted entry - * guard. Otherwise we might add several new ones, pick - * the second new one, and now we've expanded our entry - * guard list without needing to. */ - goto choose_and_finish; + const char *msg; + r = entry_is_live(entry, need_uptime, need_capacity, 0, &msg); + if (!r) + continue; /* down, no point */ + if (r == chosen_exit) + continue; /* don't pick the same node for entry and exit */ + if (consider_exit_family && smartlist_isin(exit_family, r)) + continue; /* avoid relays that are family members of our exit */ + if (options->EntryNodes && + !routerset_contains_router(options->EntryNodes, r)) { + /* We've come to the end of our preferred entry nodes. */ + if (smartlist_len(live_entry_guards)) + goto choose_and_finish; /* only choose from the ones we like */ + if (options->StrictNodes) { + /* in theory this case should never happen, since + * entry_guards_prepend_from_config() drops unwanted relays */ + tor_fragile_assert(); + } else { + log_info(LD_CIRC, + "No relays from EntryNodes available. Using others."); } - if (smartlist_len(live_entry_guards) >= options->NumEntryGuards) - break; /* we have enough */ } + smartlist_add(live_entry_guards, r); + if (!entry->made_contact) { + /* Always start with the first not-yet-contacted entry + * guard. Otherwise we might add several new ones, pick + * the second new one, and now we've expanded our entry + * guard list without needing to. */ + goto choose_and_finish; + } + if (smartlist_len(live_entry_guards) >= options->NumEntryGuards) + break; /* we have enough */ }); - /* Try to have at least 2 choices available. This way we don't - * get stuck with a single live-but-crummy entry and just keep - * using him. - * (We might get 2 live-but-crummy entry guards, but so be it.) */ - if (smartlist_len(live_entry_guards) < 2) { - if (entry_list_can_grow(options)) { + if (entry_list_is_constrained(options)) { + /* If we prefer the entry nodes we've got, and we have at least + * one choice, that's great. Use it. */ + preferred_min = 1; + } else { + /* Try to have at least 2 choices available. This way we don't + * get stuck with a single live-but-crummy entry and just keep + * using him. + * (We might get 2 live-but-crummy entry guards, but so be it.) */ + preferred_min = 2; + } + + if (smartlist_len(live_entry_guards) < preferred_min) { + if (!entry_list_is_totally_static(options)) { /* still no? try adding a new entry then */ /* XXX if guard doesn't imply fast and stable, then we need * to tell add_an_entry_guard below what we want, or it might @@@ -4153,7 -2652,7 +4153,7 @@@ need_capacity = 0; goto retry; } - if (!r && !entry_list_can_grow(options) && consider_exit_family) { + if (!r && entry_list_is_constrained(options) && consider_exit_family) { /* still no? if we're using bridges or have strictentrynodes * set, and our chosen exit is in the same family as all our * bridges/entry guards, then be flexible about families. */ @@@ -4164,15 -2663,15 +4164,15 @@@ } choose_and_finish: - if (entry_list_can_grow(options)) { + if (entry_list_is_constrained(options)) { + /* We need to weight by bandwidth, because our bridges or entryguards + * were not already selected proportional to their bandwidth. */ + r = routerlist_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD); + } else { /* We choose uniformly at random here, because choose_good_entry_server() * already weights its choices by bandwidth, so we don't want to * *double*-weight our guard selection. */ r = smartlist_choose(live_entry_guards); - } else { - /* We need to weight by bandwidth, because our bridges or entryguards - * were not already selected proportional to their bandwidth. */ - r = routerlist_sl_choose_by_bandwidth(live_entry_guards, WEIGHT_FOR_GUARD); } smartlist_free(live_entry_guards); smartlist_free(exit_family); @@@ -4306,7 -2805,7 +4306,7 @@@ entry_guards_parse_state(or_state_t *st entry_guards_dirty = 0; /* XXX022 hand new_entry_guards to this func, and move it up a * few lines, so we don't have to re-dirty it */ - if (remove_obsolete_entry_guards()) + if (remove_obsolete_entry_guards(now)) entry_guards_dirty = 1; } digestmap_free(added_by, _tor_free); @@@ -4405,11 -2904,9 +4405,11 @@@ entry_guards_update_state(or_state_t *s * */ int getinfo_helper_entry_guards(control_connection_t *conn, - const char *question, char **answer) + const char *question, char **answer, + const char **errmsg) { - int use_long_names = conn->use_long_names; + (void) conn; + (void) errmsg; if (!strcmp(question,"entry-guards") || !strcmp(question,"helper-nodes")) { @@@ -4418,13 -2915,12 +4418,13 @@@ char nbuf[MAX_VERBOSE_NICKNAME_LEN+1]; if (!entry_guards) entry_guards = smartlist_create(); - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, - { + SMARTLIST_FOREACH_BEGIN(entry_guards, entry_guard_t *, e) { size_t len = MAX_VERBOSE_NICKNAME_LEN+ISO_TIME_LEN+32; char *c = tor_malloc(len); const char *status = NULL; time_t when = 0; + routerinfo_t *ri; + if (!e->made_contact) { status = "never-connected"; } else if (e->bad_since) { @@@ -4433,17 -2929,19 +4433,17 @@@ } else { status = "up"; } - if (use_long_names) { - routerinfo_t *ri = router_get_by_digest(e->identity); - if (ri) { - router_get_verbose_nickname(nbuf, ri); - } else { - nbuf[0] = '$'; - base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN); - /* e->nickname field is not very reliable if we don't know about - * this router any longer; don't include it. */ - } + + ri = router_get_by_digest(e->identity); + if (ri) { + router_get_verbose_nickname(nbuf, ri); } else { - base16_encode(nbuf, sizeof(nbuf), e->identity, DIGEST_LEN); + nbuf[0] = '$'; + base16_encode(nbuf+1, sizeof(nbuf)-1, e->identity, DIGEST_LEN); + /* e->nickname field is not very reliable if we don't know about + * this router any longer; don't include it. */ } + if (when) { format_iso_time(tbuf, when); tor_snprintf(c, len, "%s %s %s\n", nbuf, status, tbuf); @@@ -4451,7 -2949,7 +4451,7 @@@ tor_snprintf(c, len, "%s %s\n", nbuf, status); } smartlist_add(sl, c); - }); + } SMARTLIST_FOREACH_END(e); *answer = smartlist_join_strings(sl, "", 0, NULL); SMARTLIST_FOREACH(sl, char *, c, tor_free(c)); smartlist_free(sl); @@@ -4492,56 -2990,29 +4492,56 @@@ clear_bridge_list(void * (either by comparing keys if possible, else by comparing addr/port). * Else return NULL. */ static bridge_info_t * -routerinfo_get_configured_bridge(routerinfo_t *ri) +get_configured_bridge_by_addr_port_digest(tor_addr_t *addr, uint16_t port, + const char *digest) { if (!bridge_list) return NULL; SMARTLIST_FOREACH_BEGIN(bridge_list, bridge_info_t *, bridge) { if (tor_digest_is_zero(bridge->identity) && - tor_addr_eq_ipv4h(&bridge->addr, ri->addr) && - bridge->port == ri->or_port) + !tor_addr_compare(&bridge->addr, addr, CMP_EXACT) && + bridge->port == port) return bridge; - if (!memcmp(bridge->identity, ri->cache_info.identity_digest, - DIGEST_LEN)) + if (!memcmp(bridge->identity, digest, DIGEST_LEN)) return bridge; } SMARTLIST_FOREACH_END(bridge); return NULL; } +/** Wrapper around get_configured_bridge_by_addr_port_digest() to look + * it up via router descriptor ri. */ +static bridge_info_t * +get_configured_bridge_by_routerinfo(routerinfo_t *ri) +{ + tor_addr_t addr; + tor_addr_from_ipv4h(&addr, ri->addr); + return get_configured_bridge_by_addr_port_digest(&addr, + ri->or_port, ri->cache_info.identity_digest); +} + /** Return 1 if ri is one of our known bridges, else 0. */ int routerinfo_is_a_configured_bridge(routerinfo_t *ri) { - return routerinfo_get_configured_bridge(ri) ? 1 : 0; + return get_configured_bridge_by_routerinfo(ri) ? 1 : 0; +} + +/** We made a connection to a router at addr:port + * without knowing its digest. Its digest turned out to be digest. + * If it was a bridge, and we still don't know its digest, record it. + */ +void +learned_router_identity(tor_addr_t *addr, uint16_t port, const char *digest) +{ + bridge_info_t *bridge = + get_configured_bridge_by_addr_port_digest(addr, port, digest); + if (bridge && tor_digest_is_zero(bridge->identity)) { + memcpy(bridge->identity, digest, DIGEST_LEN); + log_notice(LD_DIR, "Learned fingerprint %s for bridge %s:%d", + hex_str(digest, DIGEST_LEN), fmt_addr(addr), port); + } } /** Remember a new bridge at addr:port. If digest @@@ -4611,8 -3082,9 +4611,8 @@@ retry_bridge_descriptor_fetch_directly( * descriptor, fetch a new copy of its descriptor -- either directly * from the bridge or via a bridge authority. */ void -fetch_bridge_descriptors(time_t now) +fetch_bridge_descriptors(or_options_t *options, time_t now) { - or_options_t *options = get_options(); int num_bridge_auths = get_n_authorities(BRIDGE_AUTHORITY); int ask_bridge_directly; int can_use_bridge_authority; @@@ -4680,7 -3152,7 +4680,7 @@@ learned_bridge_descriptor(routerinfo_t tor_assert(ri->purpose == ROUTER_PURPOSE_BRIDGE); if (get_options()->UseBridges) { int first = !any_bridge_descriptors_known(); - bridge_info_t *bridge = routerinfo_get_configured_bridge(ri); + bridge_info_t *bridge = get_configured_bridge_by_routerinfo(ri); time_t now = time(NULL); ri->is_running = 1; @@@ -4728,7 -3200,8 +4728,8 @@@ any_pending_bridge_descriptor_fetches(v conn->purpose == DIR_PURPOSE_FETCH_SERVERDESC && TO_DIR_CONN(conn)->router_purpose == ROUTER_PURPOSE_BRIDGE && !conn->marked_for_close && - conn->linked && !conn->linked_conn->marked_for_close) { + conn->linked && + conn->linked_conn && !conn->linked_conn->marked_for_close) { log_debug(LD_DIR, "found one: %s", conn->address); return 1; } @@@ -4736,38 -3209,26 +4737,38 @@@ return 0; } -/** Return 1 if we have at least one descriptor for a bridge and - * all descriptors we know are down. Else return 0. If act is - * 1, then mark the down bridges up; else just observe and report. */ +/** Return 1 if we have at least one descriptor for an entry guard + * (bridge or member of EntryNodes) and all descriptors we know are + * down. Else return 0. If act is 1, then mark the down guards + * up; else just observe and report. */ static int -bridges_retry_helper(int act) +entries_retry_helper(or_options_t *options, int act) { routerinfo_t *ri; int any_known = 0; int any_running = 0; + int purpose = options->UseBridges ? + ROUTER_PURPOSE_BRIDGE : ROUTER_PURPOSE_GENERAL; if (!entry_guards) entry_guards = smartlist_create(); SMARTLIST_FOREACH(entry_guards, entry_guard_t *, e, { ri = router_get_by_digest(e->identity); - if (ri && ri->purpose == ROUTER_PURPOSE_BRIDGE) { + if (ri && ri->purpose == purpose) { any_known = 1; if (ri->is_running) - any_running = 1; /* some bridge is both known and running */ - else if (act) { /* mark it for retry */ - ri->is_running = 1; + any_running = 1; /* some entry is both known and running */ + else if (act) { + /* Mark all current connections to this OR as unhealthy, since + * otherwise there could be one that started 30 seconds + * ago, and in 30 seconds it will time out, causing us to mark + * the node down and undermine the retry attempt. We mark even + * the established conns, since if the network just came back + * we'll want to attach circuits to fresh conns. */ + connection_or_set_bad_connections(ri->cache_info.identity_digest, 1); + + /* mark this entry node for retry */ + router_set_status(ri->cache_info.identity_digest, 1); e->can_retry = 1; e->bad_since = 0; } @@@ -4778,21 -3239,19 +4779,21 @@@ return any_known && !any_running; } -/** Do we know any descriptors for our bridges, and are they all - * down? */ +/** Do we know any descriptors for our bridges / entrynodes, and are + * all the ones we have descriptors for down? */ int -bridges_known_but_down(void) +entries_known_but_down(or_options_t *options) { - return bridges_retry_helper(0); + tor_assert(entry_list_is_constrained(options)); + return entries_retry_helper(options, 0); } -/** Mark all down known bridges up. */ +/** Mark all down known bridges / entrynodes up. */ void -bridges_retry_all(void) +entries_retry_all(or_options_t *options) { - bridges_retry_helper(1); + tor_assert(entry_list_is_constrained(options)); + entries_retry_helper(options, 1); } /** Release all storage held by the list of entry guards and related

1 0