commit 86258df65d35b82ad4ee7480eec5d5434a28c9a8 Merge: 20912fb 907db00 Author: Nick Mathewson nickm@torproject.org Date: Mon Oct 22 11:35:32 2012 -0400

Merge branch 'split_circuitbuild'

Conflicts: src/or/circuitbuild.c

There was a huge-looking conflict in circuitbuild.c, but the only change that had been made to circuitbuild.c since I forked off the split_circuitbuild branch was 17442560c44e8093f9a. So I took the split_circuitbuild version of the conflicting part, and manually re-applied the change from 17442560c44e8093f9a..

changes/split_circuitbuild | 4 + src/or/channel.c | 2 + src/or/circuitbuild.c | 7304 ++++++++++++-------------------------------- src/or/circuitbuild.h | 90 - src/or/circuitlist.c | 1 + src/or/circuitstats.c | 1569 ++++++++++ src/or/circuitstats.h | 65 + src/or/circuituse.c | 2 + src/or/config.c | 1 + src/or/connection.c | 1 + src/or/connection_or.c | 2 + src/or/control.c | 2 + src/or/directory.c | 1 + src/or/entrynodes.c | 1945 ++++++++++++ src/or/entrynodes.h | 101 + src/or/include.am | 4 + src/or/main.c | 1 + src/or/microdesc.c | 1 + src/or/networkstatus.c | 3 +- src/or/routerlist.c | 3 +- src/or/routerparse.c | 2 +- src/or/statefile.c | 3 +- src/test/test.c | 4 +- 23 files changed, 5616 insertions(+), 5495 deletions(-)

diff --cc src/or/circuitbuild.c index b16dab2,75f0d5b..5e85b3e --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@@ -3671,248 -1340,182 +1340,182 @@@ entry_guard_inc_first_hop_count(entry_g return 0; }

- /** Return the number of routers in <b>routers</b> that are currently up - * and available for building circuits through. + /** A created or extended cell came back to us on the circuit, and it included + * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body + * contains (the second DH key, plus KH). If <b>reply_type</b> is + * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).) + * + * Calculate the appropriate keys and digests, make sure KH is + * correct, and initialize this hop of the cpath. + * + * Return - reason if we want to mark circ for close, else return 0. */ - static int - count_acceptable_nodes(smartlist_t *nodes) + int + circuit_finish_handshake(origin_circuit_t *circ, uint8_t reply_type, + const uint8_t *reply) { - int num=0; - - 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 (! node->is_running) - // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i); - continue; - if (! node->is_valid) - // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i); - 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; - } SMARTLIST_FOREACH_END(node); + char keys[CPATH_KEY_MATERIAL_LEN]; + crypt_path_t *hop; + int rv;

- // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num); + if ((rv = pathbias_count_first_hop(circ)) < 0) + return rv;

- return num; - } + if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) { + hop = circ->cpath; + } else { + hop = onion_next_hop_in_cpath(circ->cpath); + if (!hop) { /* got an extended when we're all done? */ + log_warn(LD_PROTOCOL,"got extended when circ already built? Closing."); + return - END_CIRC_REASON_TORPROTOCOL; + } + } + tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);

- /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>. - * This function is used to extend cpath by another hop. - */ - void - onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop) - { - if (*head_ptr) { - new_hop->next = (*head_ptr); - new_hop->prev = (*head_ptr)->prev; - (*head_ptr)->prev->next = new_hop; - (*head_ptr)->prev = new_hop; + if (reply_type == CELL_CREATED && hop->dh_handshake_state) { + if (onion_skin_client_handshake(hop->dh_handshake_state, (char*)reply,keys, + DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) { + log_warn(LD_CIRC,"onion_skin_client_handshake failed."); + return -END_CIRC_REASON_TORPROTOCOL; + } + /* Remember hash of g^xy */ + memcpy(hop->handshake_digest, reply+DH_KEY_LEN, DIGEST_LEN); + } else if (reply_type == CELL_CREATED_FAST && !hop->dh_handshake_state) { + if (fast_client_handshake(hop->fast_handshake_state, reply, + (uint8_t*)keys, + DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) { + log_warn(LD_CIRC,"fast_client_handshake failed."); + return -END_CIRC_REASON_TORPROTOCOL; + } + memcpy(hop->handshake_digest, reply+DIGEST_LEN, DIGEST_LEN); } else { - *head_ptr = new_hop; - new_hop->prev = new_hop->next = new_hop; + log_warn(LD_PROTOCOL,"CREATED cell type did not match CREATE cell type."); + return -END_CIRC_REASON_TORPROTOCOL; } - }

- /** A helper function used by onion_extend_cpath(). Use <b>purpose</b> - * and <b>state</b> and the cpath <b>head</b> (currently populated only - * to length <b>cur_len</b> to decide a suitable middle hop for a - * 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 const node_t * - choose_good_middle_server(uint8_t purpose, - cpath_build_state_t *state, - crypt_path_t *head, - int cur_len) - { - int i; - const node_t *r, *choice; - crypt_path_t *cpath; - smartlist_t *excluded; - const or_options_t *options = get_options(); - router_crn_flags_t flags = CRN_NEED_DESC; - tor_assert(CIRCUIT_PURPOSE_MIN_ <= purpose && - purpose <= CIRCUIT_PURPOSE_MAX_); + crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */ + hop->dh_handshake_state = NULL;

- log_debug(LD_CIRC, "Contemplating intermediate hop: random choice."); - excluded = smartlist_new(); - if ((r = build_state_get_exit_node(state))) { - nodelist_add_node_and_family(excluded, r); - } - for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) { - if ((r = node_get_by_id(cpath->extend_info->identity_digest))) { - nodelist_add_node_and_family(excluded, r); - } + memset(hop->fast_handshake_state, 0, sizeof(hop->fast_handshake_state)); + + if (circuit_init_cpath_crypto(hop, keys, 0)<0) { + return -END_CIRC_REASON_TORPROTOCOL; }

- if (state->need_uptime) - flags |= CRN_NEED_UPTIME; - if (state->need_capacity) - flags |= CRN_NEED_CAPACITY; - if (options->AllowInvalid_ & ALLOW_INVALID_MIDDLE) - flags |= CRN_ALLOW_INVALID; - choice = router_choose_random_node(excluded, options->ExcludeNodes, flags); - smartlist_free(excluded); - return choice; + hop->state = CPATH_STATE_OPEN; + log_info(LD_CIRC,"Finished building %scircuit hop:", + (reply_type == CELL_CREATED_FAST) ? "fast " : ""); + circuit_log_path(LOG_INFO,LD_CIRC,circ); + control_event_circuit_status(circ, CIRC_EVENT_EXTENDED, 0); + + return 0; }

- /** Pick a good entry server for the circuit to be built according to - * <b>state</b>. Don't reuse a chosen exit (if any), don't use this - * router (if we're an OR), and respect firewall settings; if we're - * configured to use entry guards, return one. + /** We received a relay truncated cell on circ. * - * If <b>state</b> is NULL, we're choosing a router to serve as an entry - * guard, not for any particular circuit. + * Since we don't ask for truncates currently, getting a truncated + * means that a connection broke or an extend failed. For now, + * just give up: for circ to close, and return 0. */ - static const node_t * - choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state) + int + circuit_truncated(origin_circuit_t *circ, crypt_path_t *layer, int reason) { - const node_t *choice; - smartlist_t *excluded; - const or_options_t *options = get_options(); - router_crn_flags_t flags = CRN_NEED_GUARD|CRN_NEED_DESC; - const node_t *node; + // crypt_path_t *victim; + // connection_t *stream;

- if (state && options->UseEntryGuards && - (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) { - /* This request is 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); - } + tor_assert(circ); + tor_assert(layer);

- excluded = smartlist_new(); + /* XXX Since we don't ask for truncates currently, getting a truncated + * means that a connection broke or an extend failed. For now, + * just give up. + */ + circuit_mark_for_close(TO_CIRCUIT(circ), - END_CIRC_REASON_FLAG_REMOTE|END_CIRC_REASON_CHANNEL_CLOSED|reason); ++ END_CIRC_REASON_FLAG_REMOTE|reason); + return 0;

- if (state && (node = build_state_get_exit_node(state))) { - /* Exclude the exit node from the state, if we have one. Also exclude its - * family. */ - nodelist_add_node_and_family(excluded, node); - } - if (firewall_is_fascist_or()) { - /* 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 and their families, if applicable */ - if (options->UseEntryGuards && entry_guards) { - SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, - { - if ((node = node_get_by_id(entry->identity))) { - nodelist_add_node_and_family(excluded, node); - } - }); - } + #if 0 + while (layer->next != circ->cpath) { + /* we need to clear out layer->next */ + victim = layer->next; + log_debug(LD_CIRC, "Killing a layer of the cpath.");

- if (state) { - if (state->need_uptime) - flags |= CRN_NEED_UPTIME; - if (state->need_capacity) - flags |= CRN_NEED_CAPACITY; - } - if (options->AllowInvalid_ & ALLOW_INVALID_ENTRY) - flags |= CRN_ALLOW_INVALID; + for (stream = circ->p_streams; stream; stream=stream->next_stream) { + if (stream->cpath_layer == victim) { + log_info(LD_APP, "Marking stream %d for close because of truncate.", + stream->stream_id); + /* no need to send 'end' relay cells, + * because the other side's already dead + */ + connection_mark_unattached_ap(stream, END_STREAM_REASON_DESTROY); + } + }

- choice = router_choose_random_node(excluded, options->ExcludeNodes, flags); - smartlist_free(excluded); - return choice; - } + layer->next = victim->next; + circuit_free_cpath_node(victim); + }

- /** Return the first non-open hop in cpath, or return NULL if all - * hops are open. */ - static crypt_path_t * - onion_next_hop_in_cpath(crypt_path_t *cpath) - { - crypt_path_t *hop = cpath; - do { - if (hop->state != CPATH_STATE_OPEN) - return hop; - hop = hop->next; - } while (hop != cpath); - return NULL; + log_info(LD_CIRC, "finished"); + return 0; + #endif }

- /** Choose a suitable next hop in the cpath <b>head_ptr</b>, - * based on <b>state</b>. Append the hop info to head_ptr. + /** Given a response payload and keys, initialize, then send a created + * cell back. */ - static int - onion_extend_cpath(origin_circuit_t *circ) + int + onionskin_answer(or_circuit_t *circ, uint8_t cell_type, const char *payload, + const char *keys) { - uint8_t purpose = circ->base_.purpose; - cpath_build_state_t *state = circ->build_state; - int cur_len = circuit_get_cpath_len(circ); - extend_info_t *info = NULL; + cell_t cell; + crypt_path_t *tmp_cpath;

- if (cur_len >= state->desired_path_len) { - log_debug(LD_CIRC, "Path is complete: %d steps long", - state->desired_path_len); - return 1; - } + tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t)); + tmp_cpath->magic = CRYPT_PATH_MAGIC;

- log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len, - state->desired_path_len); + memset(&cell, 0, sizeof(cell_t)); + cell.command = cell_type; + cell.circ_id = circ->p_circ_id;

- 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 */ - const node_t *r = choose_good_entry_server(purpose, state); - if (r) { - /* If we're a client, use the preferred address rather than the - primary address, for potentially connecting to an IPv6 OR - port. */ - info = extend_info_from_node(r, server_mode(get_options()) == 0); - tor_assert(info); - } - } else { - const node_t *r = - choose_good_middle_server(purpose, state, circ->cpath, cur_len); - if (r) { - info = extend_info_from_node(r, 0); - tor_assert(info); - } - } + circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);

- if (!info) { - log_warn(LD_CIRC,"Failed to find node for hop %d of our path. Discarding " - "this circuit.", cur_len); + memcpy(cell.payload, payload, + cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2); + + log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.", + (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); return -1; } + circ->n_digest = tmp_cpath->f_digest; + circ->n_crypto = tmp_cpath->f_crypto; + circ->p_digest = tmp_cpath->b_digest; + circ->p_crypto = tmp_cpath->b_crypto; + tmp_cpath->magic = 0; + tor_free(tmp_cpath);

- log_debug(LD_CIRC,"Chose router %s for hop %d (exit is %s)", - extend_info_describe(info), - cur_len+1, build_state_get_exit_nickname(state)); - - onion_append_hop(&circ->cpath, info); - extend_info_free(info); - return 0; - } - - /** Create a new hop, annotate it with information about its - * corresponding router <b>choice</b>, and append it to the - * end of the cpath <b>head_ptr</b>. */ - static int - onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice) - { - crypt_path_t *hop = tor_malloc_zero(sizeof(crypt_path_t)); - - /* link hop into the cpath, at the end. */ - onion_append_to_cpath(head_ptr, hop); + if (cell_type == CELL_CREATED) + memcpy(circ->handshake_digest, cell.payload+DH_KEY_LEN, DIGEST_LEN); + else + memcpy(circ->handshake_digest, cell.payload+DIGEST_LEN, DIGEST_LEN);

- hop->magic = CRYPT_PATH_MAGIC; - hop->state = CPATH_STATE_CLOSED; + circ->is_first_hop = (cell_type == CELL_CREATED_FAST);

- hop->extend_info = extend_info_dup(choice); + append_cell_to_circuit_queue(TO_CIRCUIT(circ), + circ->p_chan, &cell, CELL_DIRECTION_IN, 0); + log_debug(LD_CIRC,"Finished sending '%s' cell.", + circ->is_first_hop ? "created_fast" : "created");

- hop->package_window = circuit_initial_package_window(); - hop->deliver_window = CIRCWINDOW_START; + if (!channel_is_local(circ->p_chan) && + !channel_is_outgoing(circ->p_chan)) { + /* record that we could process create cells from a non-local conn + * that we didn't initiate; presumably this means that create cells + * can reach us too. */ + router_orport_found_reachable(); + }

return 0; }