commit b1d56fc5890fb6d594e70520c09d040e9b2e1544 Author: Nick Mathewson nickm@torproject.org Date: Fri Nov 13 13:38:01 2015 -0500

Decouple ..attach_circuit() from most of its callers.

Long ago we used to call connection_ap_handshake_attach_circuit() only in a few places, since connection_ap_attach_pending() attaches all the pending connections, and does so regularly. But this turned out to have a performance problem: it would introduce a delay to launching or connecting a stream.

We couldn't just call connection_ap_attach_pending() every time we make a new connection, since it walks the whole connection list. So we started calling connection_ap_attach_pending all over, instead! But that's kind of ugly and messes up our callgraph.

So instead, we now have connection_ap_attach_pending() use a list only of the pending connections, so we can call it much more frequently. We have a separate function to scan the whole connection array to see if we missed adding anything, and log a warning if so.

Closes ticket #17590 --- changes/decouple_conn_attach | 6 ++ src/or/circuituse.c | 2 +- src/or/connection_edge.c | 143 +++++++++++++++++++++++++++++++++++------- src/or/connection_edge.h | 2 + src/or/main.c | 5 ++ src/or/rendclient.c | 7 +-- 6 files changed, 137 insertions(+), 28 deletions(-)

diff --git a/changes/decouple_conn_attach b/changes/decouple_conn_attach new file mode 100644 index 0000000..6167b4e --- /dev/null +++ b/changes/decouple_conn_attach @@ -0,0 +1,6 @@ + o Code simplification and refactorings: + - Decouple the list of streams needing to be attached to circuits + from the overall connection list. This change makes it possible to + attach streams quickly while both simplifying Tor's callgraph and + avoiding O(N) scans of the entire connection list. Closes ticket + 17590. diff --git a/src/or/circuituse.c b/src/or/circuituse.c index 00340fd..3a1d154 100644 --- a/src/or/circuituse.c +++ b/src/or/circuituse.c @@ -1123,7 +1123,7 @@ circuit_build_needed_circs(time_t now) * don't require an exit circuit, review in #13814. * This allows HSs to function in a consensus without exits. */ if (router_have_consensus_path() != CONSENSUS_PATH_UNKNOWN) - connection_ap_attach_pending(); + connection_ap_rescan_and_attach_pending();

/* make sure any hidden services have enough intro points * HS intro point streams only require an internal circuit */ diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c index 729ef8a..ce6bace 100644 --- a/src/or/connection_edge.c +++ b/src/or/connection_edge.c @@ -503,6 +503,15 @@ connection_edge_finished_connecting(edge_connection_t *edge_conn) return connection_edge_process_inbuf(edge_conn, 1); }

+/** A list of all the entry_connection_t * objects that are not marked + * for close, and are in AP_CONN_STATE_CIRCUIT_WAIT. + * + * (Right now, we check in several places to make sure that this list is + * correct. When it's incorrect, we'll fix it, and log a BUG message.) + */ +/* XXXXX Free this list on exit. */ +static smartlist_t *pending_entry_connections = NULL; + /** Common code to connection_(ap|exit)_about_to_close. */ static void connection_edge_about_to_close(edge_connection_t *edge_conn) @@ -514,6 +523,27 @@ connection_edge_about_to_close(edge_connection_t *edge_conn) conn->marked_for_close_file, conn->marked_for_close); tor_fragile_assert(); } + + if (TO_CONN(edge_conn)->type != CONN_TYPE_AP || + PREDICT_UNLIKELY(NULL == pending_entry_connections)) + return; + + entry_connection_t *entry_conn = EDGE_TO_ENTRY_CONN(edge_conn); + + if (TO_CONN(edge_conn)->state == AP_CONN_STATE_CIRCUIT_WAIT) { + smartlist_remove(pending_entry_connections, entry_conn); + } + +#if 1 + /* Check to make sure that this isn't in pending_entry_connections if it + * didn't actually belong there. */ + if (TO_CONN(edge_conn)->type == CONN_TYPE_AP && + smartlist_contains(pending_entry_connections, entry_conn)) { + log_warn(LD_BUG, "What was %p doing in pending_entry_connections???", + entry_conn); + smartlist_remove(pending_entry_connections, entry_conn); + } +#endif }

/** Called when we're about to finally unlink and free an AP (client) @@ -711,26 +741,104 @@ connection_ap_expire_beginning(void) } SMARTLIST_FOREACH_END(base_conn); }

-/** Tell any AP streams that are waiting for a new circuit to try again, - * either attaching to an available circ or launching a new one. +/** + * As connection_ap_attach_pending, but first scans the entire connection + * array to see if any elements are missing. */ void -connection_ap_attach_pending(void) +connection_ap_rescan_and_attach_pending(void) { entry_connection_t *entry_conn; smartlist_t *conns = get_connection_array(); + + if (PREDICT_UNLIKELY(NULL == pending_entry_connections)) + pending_entry_connections = smartlist_new(); + SMARTLIST_FOREACH_BEGIN(conns, connection_t *, conn) { if (conn->marked_for_close || conn->type != CONN_TYPE_AP || conn->state != AP_CONN_STATE_CIRCUIT_WAIT) continue; + entry_conn = TO_ENTRY_CONN(conn); + if (! smartlist_contains(pending_entry_connections, entry_conn)) { + log_warn(LD_BUG, "Found a connection %p that was supposed to be " + "in pending_entry_connections, but wasn't. No worries; " + "adding it.", + pending_entry_connections); + smartlist_add(pending_entry_connections, entry_conn); + } + + } SMARTLIST_FOREACH_END(conn); + + connection_ap_attach_pending(); +} + +/** Tell any AP streams that are listed as waiting for a new circuit to try + * again, either attaching to an available circ or launching a new one. + */ +void +connection_ap_attach_pending(void) +{ + if (PREDICT_UNLIKELY(!pending_entry_connections)) { + return; + } + + SMARTLIST_FOREACH_BEGIN(pending_entry_connections, + entry_connection_t *, entry_conn) { + connection_t *conn = ENTRY_TO_CONN(entry_conn); + if (conn->marked_for_close) { + SMARTLIST_DEL_CURRENT(pending_entry_connections, entry_conn); + continue; + } + if (conn->state != AP_CONN_STATE_CIRCUIT_WAIT) { + log_warn(LD_BUG, "%p is no longer in circuit_wait. Why is it on " + "pending_entry_connections?", entry_conn); + SMARTLIST_DEL_CURRENT(pending_entry_connections, entry_conn); + continue; + } + if (connection_ap_handshake_attach_circuit(entry_conn) < 0) { if (!conn->marked_for_close) connection_mark_unattached_ap(entry_conn, END_STREAM_REASON_CANT_ATTACH); } - } SMARTLIST_FOREACH_END(conn); + + if (conn->marked_for_close || + conn->type != CONN_TYPE_AP || + conn->state != AP_CONN_STATE_CIRCUIT_WAIT) { + SMARTLIST_DEL_CURRENT(pending_entry_connections, entry_conn); + } + + } SMARTLIST_FOREACH_END(entry_conn); +} + +/** Mark <b>entry_conn</b> as needing to get attached to a circuit. + * + * And <b>entry_conn</b> must be in AP_CONN_STATE_CIRCUIT_WAIT, + * should not already be pending a circuit. The circuit will get + * launched or the connection will get attached the next time we + * call connection_ap_attach_pending(). + */ +void +connection_ap_mark_as_pending_circuit(entry_connection_t *entry_conn) +{ + connection_t *conn = ENTRY_TO_CONN(entry_conn); + tor_assert(conn->state == AP_CONN_STATE_CIRCUIT_WAIT); + if (conn->marked_for_close) + return; + + if (PREDICT_UNLIKELY(NULL == pending_entry_connections)) + pending_entry_connections = smartlist_new(); + + if (PREDICT_UNLIKELY(smartlist_contains(pending_entry_connections, + entry_conn))) { + log_warn(LD_BUG, "What?? pending_entry_connections already contains %p!", + entry_conn); + return; + } + + smartlist_add(pending_entry_connections, entry_conn); }

/** Tell any AP streams that are waiting for a one-hop tunnel to @@ -851,12 +959,12 @@ connection_ap_detach_retriable(entry_connection_t *conn, * a tunneled directory connection, then just attach it. */ ENTRY_TO_CONN(conn)->state = AP_CONN_STATE_CIRCUIT_WAIT; circuit_detach_stream(TO_CIRCUIT(circ),ENTRY_TO_EDGE_CONN(conn)); - return connection_ap_handshake_attach_circuit(conn); + connection_ap_mark_as_pending_circuit(conn); } else { ENTRY_TO_CONN(conn)->state = AP_CONN_STATE_CONTROLLER_WAIT; circuit_detach_stream(TO_CIRCUIT(circ),ENTRY_TO_EDGE_CONN(conn)); - return 0; } + return 0; }

/** Check if <b>conn</b> is using a dangerous port. Then warn and/or @@ -1454,10 +1562,12 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn, /* If we were given a circuit to attach to, try to attach. Otherwise, * try to find a good one and attach to that. */ int rv; - if (circ) - rv = connection_ap_handshake_attach_chosen_circuit(conn, circ, cpath); - else - rv = connection_ap_handshake_attach_circuit(conn); + if (circ) { + rv = connection_ap_handshake_attach_chosen_circuit(conn, circ, cpath); + } else { + connection_ap_mark_as_pending_circuit(conn); + rv = 0; + }

/* If the above function returned 0 then we're waiting for a circuit. * if it returned 1, we're attached. Both are okay. But if it returned @@ -1564,11 +1674,7 @@ connection_ap_handshake_rewrite_and_attach(entry_connection_t *conn, /* We have the descriptor so launch a connection to the HS. */ base_conn->state = AP_CONN_STATE_CIRCUIT_WAIT; log_info(LD_REND, "Descriptor is here. Great."); - if (connection_ap_handshake_attach_circuit(conn) < 0) { - if (!base_conn->marked_for_close) - connection_mark_unattached_ap(conn, END_STREAM_REASON_CANT_ATTACH); - return -1; - } + connection_ap_mark_as_pending_circuit(conn); return 0; }

@@ -2324,12 +2430,7 @@ connection_ap_make_link(connection_t *partner, control_event_stream_status(conn, STREAM_EVENT_NEW, 0);

/* attaching to a dirty circuit is fine */ - if (connection_ap_handshake_attach_circuit(conn) < 0) { - if (!base_conn->marked_for_close) - connection_mark_unattached_ap(conn, END_STREAM_REASON_CANT_ATTACH); - return NULL; - } - + connection_ap_mark_as_pending_circuit(conn); log_info(LD_APP,"... application connection created and linked."); return conn; } diff --git a/src/or/connection_edge.h b/src/or/connection_edge.h index 7c0b9c0..2030999 100644 --- a/src/or/connection_edge.h +++ b/src/or/connection_edge.h @@ -64,7 +64,9 @@ int connection_edge_is_rendezvous_stream(edge_connection_t *conn); int connection_ap_can_use_exit(const entry_connection_t *conn, const node_t *exit); void connection_ap_expire_beginning(void); +void connection_ap_rescan_and_attach_pending(void); void connection_ap_attach_pending(void); +void connection_ap_mark_as_pending_circuit(entry_connection_t *entry_conn); void connection_ap_fail_onehop(const char *failed_digest, cpath_build_state_t *build_state); void circuit_discard_optional_exit_enclaves(extend_info_t *info); diff --git a/src/or/main.c b/src/or/main.c index afcb313..bfa41b9 100644 --- a/src/or/main.c +++ b/src/or/main.c @@ -2505,6 +2505,11 @@ run_main_loop_once(void) } }

+ /* This should be pretty fast if nothing is pending. BUT... watch out; + * we need to make sure it doesn't show up in the profiles. five times a + * second would be enough, for instance. */ + connection_ap_attach_pending(); + return 1; }

diff --git a/src/or/rendclient.c b/src/or/rendclient.c index a39e518..3846ef0 100644 --- a/src/or/rendclient.c +++ b/src/or/rendclient.c @@ -1226,12 +1226,7 @@ rend_client_desc_trynow(const char *query) base_conn->timestamp_lastread = now; base_conn->timestamp_lastwritten = now;

- if (connection_ap_handshake_attach_circuit(conn) < 0) { - /* it will never work */ - log_warn(LD_REND,"Rendezvous attempt failed. Closing."); - if (!base_conn->marked_for_close) - connection_mark_unattached_ap(conn, END_STREAM_REASON_CANT_ATTACH); - } + connection_ap_mark_as_pending_circuit(conn); } else { /* 404, or fetch didn't get that far */ log_notice(LD_REND,"Closing stream for '%s.onion': hidden service is " "unavailable (try again later).",