diff options
Diffstat (limited to 'src/or/circuitlist.c')
-rw-r--r-- | src/or/circuitlist.c | 831 |
1 files changed, 586 insertions, 245 deletions
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c index 977afca18d..7bdef0b878 100644 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@ -1,15 +1,58 @@ /* Copyright 2001 Matej Pfajfar. * Copyright (c) 2001-2004, Roger Dingledine. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. - * Copyright (c) 2007-2016, The Tor Project, Inc. */ + * Copyright (c) 2007-2017, The Tor Project, Inc. */ /* See LICENSE for licensing information */ /** * \file circuitlist.c * - * \brief Manage the global circuit list, and looking up circuits within it. + * \brief Manage global structures that list and index circuits, and + * look up circuits within them. + * + * One of the most frequent operations in Tor occurs every time that + * a relay cell arrives on a channel. When that happens, we need to + * find which circuit it is associated with, based on the channel and the + * circuit ID in the relay cell. + * + * To handle that, we maintain a global list of circuits, and a hashtable + * mapping [channel,circID] pairs to circuits. Circuits are added to and + * removed from this mapping using circuit_set_p_circid_chan() and + * circuit_set_n_circid_chan(). To look up a circuit from this map, most + * callers should use circuit_get_by_circid_channel(), though + * circuit_get_by_circid_channel_even_if_marked() is appropriate under some + * circumstances. + * + * We also need to allow for the possibility that we have blocked use of a + * circuit ID (because we are waiting to send a DESTROY cell), but the + * circuit is not there any more. For that case, we allow placeholder + * entries in the table, using channel_mark_circid_unusable(). + * + * To efficiently handle a channel that has just opened, we also maintain a + * list of the circuits waiting for channels, so we can attach them as + * needed without iterating through the whole list of circuits, using + * circuit_get_all_pending_on_channel(). + * + * In this module, we also handle the list of circuits that have been + * marked for close elsewhere, and close them as needed. (We use this + * "mark now, close later" pattern here and elsewhere to avoid + * unpredictable recursion if we closed every circuit immediately upon + * realizing it needed to close.) See circuit_mark_for_close() for the + * mark function, and circuit_close_all_marked() for the close function. + * + * For hidden services, we need to be able to look up introduction point + * circuits and rendezvous circuits by cookie, key, etc. These are + * currently handled with linear searches in + * circuit_get_ready_rend_circuit_by_rend_data(), + * circuit_get_next_by_pk_and_purpose(), and with hash lookups in + * circuit_get_rendezvous() and circuit_get_intro_point(). + * + * This module is also the entry point for our out-of-memory handler + * logic, which was originally circuit-focused. **/ #define CIRCUITLIST_PRIVATE +#include "torint.h" /* TOR_PRIuSZ */ + #include "or.h" #include "channel.h" #include "circpathbias.h" @@ -22,7 +65,11 @@ #include "connection_edge.h" #include "connection_or.h" #include "control.h" +#include "entrynodes.h" #include "main.h" +#include "hs_circuit.h" +#include "hs_circuitmap.h" +#include "hs_ident.h" #include "networkstatus.h" #include "nodelist.h" #include "onion.h" @@ -34,6 +81,10 @@ #include "rephist.h" #include "routerlist.h" #include "routerset.h" +#include "channelpadding.h" +#include "compress_lzma.h" +#include "compress_zlib.h" +#include "compress_zstd.h" #include "ht.h" @@ -42,21 +93,34 @@ /** A global list of all circuits at this hop. */ static smartlist_t *global_circuitlist = NULL; +/** A global list of all origin circuits. Every element of this is also + * an element of global_circuitlist. */ +static smartlist_t *global_origin_circuit_list = NULL; + /** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */ static smartlist_t *circuits_pending_chans = NULL; +/** List of all the (origin) circuits whose state is + * CIRCUIT_STATE_GUARD_WAIT. */ +static smartlist_t *circuits_pending_other_guards = NULL; + /** A list of all the circuits that have been marked with * circuit_mark_for_close and which are waiting for circuit_about_to_free. */ static smartlist_t *circuits_pending_close = NULL; static void circuit_free_cpath_node(crypt_path_t *victim); static void cpath_ref_decref(crypt_path_reference_t *cpath_ref); -//static void circuit_set_rend_token(or_circuit_t *circ, int is_rend_circ, -// const uint8_t *token); -static void circuit_clear_rend_token(or_circuit_t *circ); static void circuit_about_to_free_atexit(circuit_t *circ); static void circuit_about_to_free(circuit_t *circ); +/** + * A cached value of the current state of the origin circuit list. Has the + * value 1 if we saw any opened circuits recently (since the last call to + * circuit_any_opened_circuits(), which gets called around once a second by + * circuit_expire_building). 0 otherwise. + */ +static int any_opened_circs_cached_val = 0; + /********* END VARIABLES ************/ /** A map from channel and circuit ID to circuit. (Lookup performance is @@ -309,8 +373,8 @@ channel_note_destroy_pending(channel_t *chan, circid_t id) /** Called to indicate that a DESTROY is no longer pending on <b>chan</b> with * circuit ID <b>id</b> -- typically, because it has been sent. */ -MOCK_IMPL(void, channel_note_destroy_not_pending, - (channel_t *chan, circid_t id)) +MOCK_IMPL(void, +channel_note_destroy_not_pending,(channel_t *chan, circid_t id)) { circuit_t *circ = circuit_get_by_circid_channel_even_if_marked(id,chan); if (circ) { @@ -386,8 +450,10 @@ circuit_set_state(circuit_t *circ, uint8_t state) tor_assert(circ); if (state == circ->state) return; - if (!circuits_pending_chans) + if (PREDICT_UNLIKELY(!circuits_pending_chans)) circuits_pending_chans = smartlist_new(); + if (PREDICT_UNLIKELY(!circuits_pending_other_guards)) + circuits_pending_other_guards = smartlist_new(); if (circ->state == CIRCUIT_STATE_CHAN_WAIT) { /* remove from waiting-circuit list. */ smartlist_remove(circuits_pending_chans, circ); @@ -396,7 +462,13 @@ circuit_set_state(circuit_t *circ, uint8_t state) /* add to waiting-circuit list. */ smartlist_add(circuits_pending_chans, circ); } - if (state == CIRCUIT_STATE_OPEN) + if (circ->state == CIRCUIT_STATE_GUARD_WAIT) { + smartlist_remove(circuits_pending_other_guards, circ); + } + if (state == CIRCUIT_STATE_GUARD_WAIT) { + smartlist_add(circuits_pending_other_guards, circ); + } + if (state == CIRCUIT_STATE_GUARD_WAIT || state == CIRCUIT_STATE_OPEN) tor_assert(!circ->n_chan_create_cell); circ->state = state; } @@ -445,13 +517,45 @@ circuit_count_pending_on_channel(channel_t *chan) circuit_get_all_pending_on_channel(sl, chan); cnt = smartlist_len(sl); smartlist_free(sl); - log_debug(LD_CIRC,"or_conn to %s at %s, %d pending circs", - chan->nickname ? chan->nickname : "NULL", + log_debug(LD_CIRC,"or_conn to %s, %d pending circs", channel_get_canonical_remote_descr(chan), cnt); return cnt; } +/** Remove <b>origin_circ</b> from the global list of origin circuits. + * Called when we are freeing a circuit. + */ +static void +circuit_remove_from_origin_circuit_list(origin_circuit_t *origin_circ) +{ + int origin_idx = origin_circ->global_origin_circuit_list_idx; + if (origin_idx < 0) + return; + origin_circuit_t *c2; + tor_assert(origin_idx <= smartlist_len(global_origin_circuit_list)); + c2 = smartlist_get(global_origin_circuit_list, origin_idx); + tor_assert(origin_circ == c2); + smartlist_del(global_origin_circuit_list, origin_idx); + if (origin_idx < smartlist_len(global_origin_circuit_list)) { + origin_circuit_t *replacement = + smartlist_get(global_origin_circuit_list, origin_idx); + replacement->global_origin_circuit_list_idx = origin_idx; + } + origin_circ->global_origin_circuit_list_idx = -1; +} + +/** Add <b>origin_circ</b> to the global list of origin circuits. Called + * when creating the circuit. */ +static void +circuit_add_to_origin_circuit_list(origin_circuit_t *origin_circ) +{ + tor_assert(origin_circ->global_origin_circuit_list_idx == -1); + smartlist_t *lst = circuit_get_global_origin_circuit_list(); + smartlist_add(lst, origin_circ); + origin_circ->global_origin_circuit_list_idx = smartlist_len(lst) - 1; +} + /** Detach from the global circuit list, and deallocate, all * circuits that have been marked for close. */ @@ -474,6 +578,11 @@ circuit_close_all_marked(void) } circ->global_circuitlist_idx = -1; + /* Remove it from the origin circuit list, if appropriate. */ + if (CIRCUIT_IS_ORIGIN(circ)) { + circuit_remove_from_origin_circuit_list(TO_ORIGIN_CIRCUIT(circ)); + } + circuit_about_to_free(circ); circuit_free(circ); } SMARTLIST_FOREACH_END(circ); @@ -481,7 +590,7 @@ circuit_close_all_marked(void) smartlist_clear(circuits_pending_close); } -/** Return the head of the global linked list of circuits. */ +/** Return a pointer to the global list of circuits. */ MOCK_IMPL(smartlist_t *, circuit_get_global_list,(void)) { @@ -490,6 +599,65 @@ circuit_get_global_list,(void)) return global_circuitlist; } +/** Return a pointer to the global list of origin circuits. */ +smartlist_t * +circuit_get_global_origin_circuit_list(void) +{ + if (NULL == global_origin_circuit_list) + global_origin_circuit_list = smartlist_new(); + return global_origin_circuit_list; +} + +/** + * Return true if we have any opened general-purpose 3 hop + * origin circuits. + * + * The result from this function is cached for use by + * circuit_any_opened_circuits_cached(). + */ +int +circuit_any_opened_circuits(void) +{ + SMARTLIST_FOREACH_BEGIN(circuit_get_global_origin_circuit_list(), + const origin_circuit_t *, next_circ) { + if (!TO_CIRCUIT(next_circ)->marked_for_close && + next_circ->has_opened && + TO_CIRCUIT(next_circ)->state == CIRCUIT_STATE_OPEN && + TO_CIRCUIT(next_circ)->purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT && + next_circ->build_state && + next_circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN) { + circuit_cache_opened_circuit_state(1); + return 1; + } + } SMARTLIST_FOREACH_END(next_circ); + + circuit_cache_opened_circuit_state(0); + return 0; +} + +/** + * Cache the "any circuits opened" state, as specified in param + * circuits_are_opened. This is a helper function to update + * the circuit opened status whenever we happen to look at the + * circuit list. + */ +void +circuit_cache_opened_circuit_state(int circuits_are_opened) +{ + any_opened_circs_cached_val = circuits_are_opened; +} + +/** + * Return true if there were any opened circuits since the last call to + * circuit_any_opened_circuits(), or since circuit_expire_building() last + * ran (it runs roughly once per second). + */ +int +circuit_any_opened_circuits_cached(void) +{ + return any_opened_circs_cached_val; +} + /** Function to make circ-\>state human-readable */ const char * circuit_state_to_string(int state) @@ -499,6 +667,8 @@ circuit_state_to_string(int state) case CIRCUIT_STATE_BUILDING: return "doing handshakes"; case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion"; case CIRCUIT_STATE_CHAN_WAIT: return "connecting to server"; + case CIRCUIT_STATE_GUARD_WAIT: return "waiting to see how other " + "guards perform"; case CIRCUIT_STATE_OPEN: return "open"; default: log_warn(LD_BUG, "Unknown circuit state %d", state); @@ -522,6 +692,10 @@ circuit_purpose_to_controller_string(uint8_t purpose) case CIRCUIT_PURPOSE_C_GENERAL: return "GENERAL"; + + case CIRCUIT_PURPOSE_C_HSDIR_GET: + return "HS_CLIENT_HSDIR"; + case CIRCUIT_PURPOSE_C_INTRODUCING: case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT: case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED: @@ -533,6 +707,9 @@ circuit_purpose_to_controller_string(uint8_t purpose) case CIRCUIT_PURPOSE_C_REND_JOINED: return "HS_CLIENT_REND"; + case CIRCUIT_PURPOSE_S_HSDIR_POST: + return "HS_SERVICE_HSDIR"; + case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO: case CIRCUIT_PURPOSE_S_INTRO: return "HS_SERVICE_INTRO"; @@ -549,6 +726,8 @@ circuit_purpose_to_controller_string(uint8_t purpose) return "CONTROLLER"; case CIRCUIT_PURPOSE_PATH_BIAS_TESTING: return "PATH_BIAS_TESTING"; + case CIRCUIT_PURPOSE_HS_VANGUARDS: + return "HS_VANGUARDS"; default: tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose); @@ -577,6 +756,7 @@ circuit_purpose_to_controller_hs_state_string(uint8_t purpose) case CIRCUIT_PURPOSE_TESTING: case CIRCUIT_PURPOSE_CONTROLLER: case CIRCUIT_PURPOSE_PATH_BIAS_TESTING: + case CIRCUIT_PURPOSE_HS_VANGUARDS: return NULL; case CIRCUIT_PURPOSE_INTRO_POINT: @@ -586,6 +766,7 @@ circuit_purpose_to_controller_hs_state_string(uint8_t purpose) case CIRCUIT_PURPOSE_REND_ESTABLISHED: return "OR_HS_R_JOINED"; + case CIRCUIT_PURPOSE_C_HSDIR_GET: case CIRCUIT_PURPOSE_C_INTRODUCING: return "HSCI_CONNECTING"; case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT: @@ -602,6 +783,7 @@ circuit_purpose_to_controller_hs_state_string(uint8_t purpose) case CIRCUIT_PURPOSE_C_REND_JOINED: return "HSCR_JOINED"; + case CIRCUIT_PURPOSE_S_HSDIR_POST: case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO: return "HSSI_CONNECTING"; case CIRCUIT_PURPOSE_S_INTRO: @@ -627,9 +809,9 @@ circuit_purpose_to_string(uint8_t purpose) case CIRCUIT_PURPOSE_INTRO_POINT: return "Acting as intro point"; case CIRCUIT_PURPOSE_REND_POINT_WAITING: - return "Acting as rendevous (pending)"; + return "Acting as rendezvous (pending)"; case CIRCUIT_PURPOSE_REND_ESTABLISHED: - return "Acting as rendevous (established)"; + return "Acting as rendezvous (established)"; case CIRCUIT_PURPOSE_C_GENERAL: return "General-purpose client"; case CIRCUIT_PURPOSE_C_INTRODUCING: @@ -646,6 +828,9 @@ circuit_purpose_to_string(uint8_t purpose) return "Hidden service client: Pending rendezvous point (ack received)"; case CIRCUIT_PURPOSE_C_REND_JOINED: return "Hidden service client: Active rendezvous point"; + case CIRCUIT_PURPOSE_C_HSDIR_GET: + return "Hidden service client: Fetching HS descriptor"; + case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT: return "Measuring circuit timeout"; @@ -657,6 +842,8 @@ circuit_purpose_to_string(uint8_t purpose) return "Hidden service: Connecting to rendezvous point"; case CIRCUIT_PURPOSE_S_REND_JOINED: return "Hidden service: Active rendezvous point"; + case CIRCUIT_PURPOSE_S_HSDIR_POST: + return "Hidden service: Uploading HS descriptor"; case CIRCUIT_PURPOSE_TESTING: return "Testing circuit"; @@ -667,6 +854,9 @@ circuit_purpose_to_string(uint8_t purpose) case CIRCUIT_PURPOSE_PATH_BIAS_TESTING: return "Path-bias testing circuit"; + case CIRCUIT_PURPOSE_HS_VANGUARDS: + return "Hidden service: Pre-built vanguard circuit"; + default: tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose); return buf; @@ -708,6 +898,13 @@ init_circuit_base(circuit_t *circ) circ->global_circuitlist_idx = smartlist_len(circuit_get_global_list()) - 1; } +/** If we haven't yet decided on a good timeout value for circuit + * building, we close idle circuits aggressively so we can get more + * data points. These are the default, min, and max consensus values */ +#define DFLT_IDLE_TIMEOUT_WHILE_LEARNING (3*60) +#define MIN_IDLE_TIMEOUT_WHILE_LEARNING (10) +#define MAX_IDLE_TIMEOUT_WHILE_LEARNING (1000*60) + /** Allocate space for a new circuit, initializing with <b>p_circ_id</b> * and <b>p_conn</b>. Add it to the global circuit list. */ @@ -729,8 +926,55 @@ origin_circuit_new(void) init_circuit_base(TO_CIRCUIT(circ)); + /* Add to origin-list. */ + circ->global_origin_circuit_list_idx = -1; + circuit_add_to_origin_circuit_list(circ); + circuit_build_times_update_last_circ(get_circuit_build_times_mutable()); + if (! circuit_build_times_disabled(get_options()) && + circuit_build_times_needs_circuits(get_circuit_build_times())) { + /* Circuits should be shorter lived if we need more of them + * for learning a good build timeout */ + circ->circuit_idle_timeout = + networkstatus_get_param(NULL, "cbtlearntimeout", + DFLT_IDLE_TIMEOUT_WHILE_LEARNING, + MIN_IDLE_TIMEOUT_WHILE_LEARNING, + MAX_IDLE_TIMEOUT_WHILE_LEARNING); + } else { + // This should always be larger than the current port prediction time + // remaining, or else we'll end up with the case where a circuit times out + // and another one is built, effectively doubling the timeout window. + // + // We also randomize it by up to 5% more (ie 5% of 0 to 3600 seconds, + // depending on how much circuit prediction time is remaining) so that + // we don't close a bunch of unused circuits all at the same time. + int prediction_time_remaining = + predicted_ports_prediction_time_remaining(time(NULL)); + circ->circuit_idle_timeout = prediction_time_remaining+1+ + crypto_rand_int(1+prediction_time_remaining/20); + + if (circ->circuit_idle_timeout <= 0) { + log_warn(LD_BUG, + "Circuit chose a negative idle timeout of %d based on " + "%d seconds of predictive building remaining.", + circ->circuit_idle_timeout, + prediction_time_remaining); + circ->circuit_idle_timeout = + networkstatus_get_param(NULL, "cbtlearntimeout", + DFLT_IDLE_TIMEOUT_WHILE_LEARNING, + MIN_IDLE_TIMEOUT_WHILE_LEARNING, + MAX_IDLE_TIMEOUT_WHILE_LEARNING); + } + + log_info(LD_CIRC, + "Circuit " U64_FORMAT " chose an idle timeout of %d based on " + "%d seconds of predictive building remaining.", + U64_PRINTF_ARG(circ->global_identifier), + circ->circuit_idle_timeout, + prediction_time_remaining); + } + return circ; } @@ -771,21 +1015,34 @@ circuit_clear_testing_cell_stats(circuit_t *circ) /** Deallocate space associated with circ. */ STATIC void -circuit_free(circuit_t *circ) +circuit_free_(circuit_t *circ) { + circid_t n_circ_id = 0; void *mem; size_t memlen; int should_free = 1; if (!circ) return; + /* We keep a copy of this so we can log its value before it gets unset. */ + n_circ_id = circ->n_circ_id; + circuit_clear_testing_cell_stats(circ); + /* Cleanup circuit from anything HS v3 related. We also do this when the + * circuit is closed. This is to avoid any code path that free registered + * circuits without closing them before. This needs to be done before the + * hs identifier is freed. */ + hs_circ_cleanup(circ); + if (CIRCUIT_IS_ORIGIN(circ)) { origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ); mem = ocirc; memlen = sizeof(origin_circuit_t); tor_assert(circ->magic == ORIGIN_CIRCUIT_MAGIC); + + circuit_remove_from_origin_circuit_list(ocirc); + if (ocirc->build_state) { extend_info_free(ocirc->build_state->chosen_exit); circuit_free_cpath_node(ocirc->build_state->pending_final_cpath); @@ -793,11 +1050,22 @@ circuit_free(circuit_t *circ) } tor_free(ocirc->build_state); + /* Cancel before freeing, if we haven't already succeeded or failed. */ + if (ocirc->guard_state) { + entry_guard_cancel(ô->guard_state); + } + circuit_guard_state_free(ocirc->guard_state); + circuit_clear_cpath(ocirc); crypto_pk_free(ocirc->intro_key); rend_data_free(ocirc->rend_data); + /* Finally, free the identifier of the circuit and nullify it so multiple + * cleanup will work. */ + hs_ident_circuit_free(ocirc->hs_ident); + ocirc->hs_ident = NULL; + tor_free(ocirc->dest_address); if (ocirc->socks_username) { memwipe(ocirc->socks_username, 0x12, ocirc->socks_username_len); @@ -824,8 +1092,6 @@ circuit_free(circuit_t *circ) crypto_cipher_free(ocirc->n_crypto); crypto_digest_free(ocirc->n_digest); - circuit_clear_rend_token(ocirc); - if (ocirc->rend_splice) { or_circuit_t *other = ocirc->rend_splice; tor_assert(other->base_.magic == OR_CIRCUIT_MAGIC); @@ -861,6 +1127,11 @@ circuit_free(circuit_t *circ) * "active" checks will be violated. */ cell_queue_clear(&circ->n_chan_cells); + log_info(LD_CIRC, "Circuit %u (id: %" PRIu32 ") has been freed.", + n_circ_id, + CIRCUIT_IS_ORIGIN(circ) ? + TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0); + if (should_free) { memwipe(mem, 0xAA, memlen); /* poison memory */ tor_free(mem); @@ -912,7 +1183,7 @@ circuit_free_all(void) while (or_circ->resolving_streams) { edge_connection_t *next_conn; next_conn = or_circ->resolving_streams->next_stream; - connection_free(TO_CONN(or_circ->resolving_streams)); + connection_free_(TO_CONN(or_circ->resolving_streams)); or_circ->resolving_streams = next_conn; } } @@ -925,12 +1196,18 @@ circuit_free_all(void) smartlist_free(lst); global_circuitlist = NULL; + smartlist_free(global_origin_circuit_list); + global_origin_circuit_list = NULL; + smartlist_free(circuits_pending_chans); circuits_pending_chans = NULL; smartlist_free(circuits_pending_close); circuits_pending_close = NULL; + smartlist_free(circuits_pending_other_guards); + circuits_pending_other_guards = NULL; + { chan_circid_circuit_map_t **elt, **next, *c; for (elt = HT_START(chan_circid_map, &chan_circid_map); @@ -1262,7 +1539,7 @@ circuit_unlink_all_from_channel(channel_t *chan, int reason) smartlist_free(detached_2); } } -#endif +#endif /* defined(DEBUG_CIRCUIT_UNLINK_ALL) */ SMARTLIST_FOREACH_BEGIN(detached, circuit_t *, circ) { int mark = 0; @@ -1311,9 +1588,11 @@ circuit_get_ready_rend_circ_by_rend_data(const rend_data_t *rend_data) if (!circ->marked_for_close && circ->purpose == CIRCUIT_PURPOSE_C_REND_READY) { origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ); - if (ocirc->rend_data && - !rend_cmp_service_ids(rend_data->onion_address, - ocirc->rend_data->onion_address) && + if (ocirc->rend_data == NULL) { + continue; + } + if (!rend_cmp_service_ids(rend_data_get_address(rend_data), + rend_data_get_address(ocirc->rend_data)) && tor_memeq(ocirc->rend_data->rend_cookie, rend_data->rend_cookie, REND_COOKIE_LEN)) @@ -1324,209 +1603,155 @@ circuit_get_ready_rend_circ_by_rend_data(const rend_data_t *rend_data) return NULL; } -/** Return the first circuit originating here in global_circuitlist after - * <b>start</b> whose purpose is <b>purpose</b>, and where - * <b>digest</b> (if set) matches the rend_pk_digest field. Return NULL if no - * circuit is found. If <b>start</b> is NULL, begin at the start of the list. - */ +/** Return the first service introduction circuit originating from the global + * circuit list after <b>start</b> or at the start of the list if <b>start</b> + * is NULL. Return NULL if no circuit is found. + * + * A service introduction point circuit has a purpose of either + * CIRCUIT_PURPOSE_S_ESTABLISH_INTRO or CIRCUIT_PURPOSE_S_INTRO. This does not + * return a circuit marked for close and its state must be open. */ origin_circuit_t * -circuit_get_next_by_pk_and_purpose(origin_circuit_t *start, - const char *digest, uint8_t purpose) +circuit_get_next_service_intro_circ(origin_circuit_t *start) { - int idx; + int idx = 0; smartlist_t *lst = circuit_get_global_list(); - tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose)); - if (start == NULL) - idx = 0; - else + + if (start) { idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1; + } for ( ; idx < smartlist_len(lst); ++idx) { circuit_t *circ = smartlist_get(lst, idx); - if (circ->marked_for_close) + /* Ignore a marked for close circuit or purpose not matching a service + * intro point or if the state is not open. */ + if (circ->marked_for_close || circ->state != CIRCUIT_STATE_OPEN || + (circ->purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO && + circ->purpose != CIRCUIT_PURPOSE_S_INTRO)) { continue; - if (circ->purpose != purpose) - continue; - if (!digest) - return TO_ORIGIN_CIRCUIT(circ); - else if (TO_ORIGIN_CIRCUIT(circ)->rend_data && - tor_memeq(TO_ORIGIN_CIRCUIT(circ)->rend_data->rend_pk_digest, - digest, DIGEST_LEN)) - return TO_ORIGIN_CIRCUIT(circ); + } + /* The purposes we are looking for are only for origin circuits so the + * following is valid. */ + return TO_ORIGIN_CIRCUIT(circ); } + /* Not found. */ return NULL; } -/** Map from rendezvous cookie to or_circuit_t */ -static digestmap_t *rend_cookie_map = NULL; - -/** Map from introduction point digest to or_circuit_t */ -static digestmap_t *intro_digest_map = NULL; - -/** Return the OR circuit whose purpose is <b>purpose</b>, and whose - * rend_token is the REND_TOKEN_LEN-byte <b>token</b>. If <b>is_rend_circ</b>, - * look for rendezvous point circuits; otherwise look for introduction point - * circuits. */ -static or_circuit_t * -circuit_get_by_rend_token_and_purpose(uint8_t purpose, int is_rend_circ, - const char *token) +/** Return the first service rendezvous circuit originating from the global + * circuit list after <b>start</b> or at the start of the list if <b>start</b> + * is NULL. Return NULL if no circuit is found. + * + * A service rendezvous point circuit has a purpose of either + * CIRCUIT_PURPOSE_S_CONNECT_REND or CIRCUIT_PURPOSE_S_REND_JOINED. This does + * not return a circuit marked for close and its state must be open. */ +origin_circuit_t * +circuit_get_next_service_rp_circ(origin_circuit_t *start) { - or_circuit_t *circ; - digestmap_t *map = is_rend_circ ? rend_cookie_map : intro_digest_map; - - if (!map) - return NULL; - - circ = digestmap_get(map, token); - if (!circ || - circ->base_.purpose != purpose || - circ->base_.marked_for_close) - return NULL; + int idx = 0; + smartlist_t *lst = circuit_get_global_list(); - if (!circ->rendinfo) { - char *t = tor_strdup(hex_str(token, REND_TOKEN_LEN)); - log_warn(LD_BUG, "Wanted a circuit with %s:%d, but lookup returned a " - "circuit with no rendinfo set.", - safe_str(t), is_rend_circ); - tor_free(t); - return NULL; + if (start) { + idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1; } - if (! bool_eq(circ->rendinfo->is_rend_circ, is_rend_circ) || - tor_memneq(circ->rendinfo->rend_token, token, REND_TOKEN_LEN)) { - char *t = tor_strdup(hex_str(token, REND_TOKEN_LEN)); - log_warn(LD_BUG, "Wanted a circuit with %s:%d, but lookup returned %s:%d", - safe_str(t), is_rend_circ, - safe_str(hex_str(circ->rendinfo->rend_token, REND_TOKEN_LEN)), - (int)circ->rendinfo->is_rend_circ); - tor_free(t); - return NULL; - } + for ( ; idx < smartlist_len(lst); ++idx) { + circuit_t *circ = smartlist_get(lst, idx); - return circ; + /* Ignore a marked for close circuit or purpose not matching a service + * intro point or if the state is not open. */ + if (circ->marked_for_close || circ->state != CIRCUIT_STATE_OPEN || + (circ->purpose != CIRCUIT_PURPOSE_S_CONNECT_REND && + circ->purpose != CIRCUIT_PURPOSE_S_REND_JOINED)) { + continue; + } + /* The purposes we are looking for are only for origin circuits so the + * following is valid. */ + return TO_ORIGIN_CIRCUIT(circ); + } + /* Not found. */ + return NULL; } -/** Clear the rendezvous cookie or introduction point key digest that's - * configured on <b>circ</b>, if any, and remove it from any such maps. */ -static void -circuit_clear_rend_token(or_circuit_t *circ) +/** Return the first circuit originating here in global_circuitlist after + * <b>start</b> whose purpose is <b>purpose</b>, and where <b>digest</b> (if + * set) matches the private key digest of the rend data associated with the + * circuit. Return NULL if no circuit is found. If <b>start</b> is NULL, + * begin at the start of the list. + */ +origin_circuit_t * +circuit_get_next_by_pk_and_purpose(origin_circuit_t *start, + const uint8_t *digest, uint8_t purpose) { - or_circuit_t *found_circ; - digestmap_t *map; - - if (!circ || !circ->rendinfo) - return; - - map = circ->rendinfo->is_rend_circ ? rend_cookie_map : intro_digest_map; + int idx; + smartlist_t *lst = circuit_get_global_list(); + tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose)); + if (start == NULL) + idx = 0; + else + idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1; - if (!map) { - log_warn(LD_BUG, "Tried to clear rend token on circuit, but found no map"); - return; - } + for ( ; idx < smartlist_len(lst); ++idx) { + circuit_t *circ = smartlist_get(lst, idx); + origin_circuit_t *ocirc; - found_circ = digestmap_get(map, circ->rendinfo->rend_token); - if (found_circ == circ) { - /* Great, this is the right one. */ - digestmap_remove(map, circ->rendinfo->rend_token); - } else if (found_circ) { - log_warn(LD_BUG, "Tried to clear rend token on circuit, but " - "it was already replaced in the map."); - } else { - log_warn(LD_BUG, "Tried to clear rend token on circuit, but " - "it not in the map at all."); + if (circ->marked_for_close) + continue; + if (circ->purpose != purpose) + continue; + /* At this point we should be able to get a valid origin circuit because + * the origin purpose we are looking for matches this circuit. */ + if (BUG(!CIRCUIT_PURPOSE_IS_ORIGIN(circ->purpose))) { + break; + } + ocirc = TO_ORIGIN_CIRCUIT(circ); + if (!digest) + return ocirc; + if (rend_circuit_pk_digest_eq(ocirc, digest)) { + return ocirc; + } } - - tor_free(circ->rendinfo); /* Sets it to NULL too */ + return NULL; } -/** Set the rendezvous cookie (if is_rend_circ), or the introduction point - * digest (if ! is_rend_circ) of <b>circ</b> to the REND_TOKEN_LEN-byte value - * in <b>token</b>, and add it to the appropriate map. If it previously had a - * token, clear it. If another circuit previously had the same - * cookie/intro-digest, mark that circuit and remove it from the map. */ -static void -circuit_set_rend_token(or_circuit_t *circ, int is_rend_circ, - const uint8_t *token) +/** We might cannibalize this circuit: Return true if its last hop can be used + * as a v3 rendezvous point. */ +static int +circuit_can_be_cannibalized_for_v3_rp(const origin_circuit_t *circ) { - digestmap_t **map_p, *map; - or_circuit_t *found_circ; - - /* Find the right map, creating it as needed */ - map_p = is_rend_circ ? &rend_cookie_map : &intro_digest_map; - - if (!*map_p) - *map_p = digestmap_new(); - - map = *map_p; - - /* If this circuit already has a token, we need to remove that. */ - if (circ->rendinfo) - circuit_clear_rend_token(circ); + if (!circ->build_state) { + return 0; + } - if (token == NULL) { - /* We were only trying to remove this token, not set a new one. */ - return; + extend_info_t *chosen_exit = circ->build_state->chosen_exit; + if (BUG(!chosen_exit)) { + return 0; } - found_circ = digestmap_get(map, (const char *)token); - if (found_circ) { - tor_assert(found_circ != circ); - circuit_clear_rend_token(found_circ); - if (! found_circ->base_.marked_for_close) { - circuit_mark_for_close(TO_CIRCUIT(found_circ), END_CIRC_REASON_FINISHED); - if (is_rend_circ) { - log_fn(LOG_PROTOCOL_WARN, LD_REND, - "Duplicate rendezvous cookie (%s...) used on two circuits", - hex_str((const char*)token, 4)); /* only log first 4 chars */ - } + const node_t *rp_node = node_get_by_id(chosen_exit->identity_digest); + if (rp_node) { + if (node_supports_v3_rendezvous_point(rp_node)) { + return 1; } } - /* Now set up the rendinfo */ - circ->rendinfo = tor_malloc(sizeof(*circ->rendinfo)); - memcpy(circ->rendinfo->rend_token, token, REND_TOKEN_LEN); - circ->rendinfo->is_rend_circ = is_rend_circ ? 1 : 0; - - digestmap_set(map, (const char *)token, circ); -} - -/** Return the circuit waiting for a rendezvous with the provided cookie. - * Return NULL if no such circuit is found. - */ -or_circuit_t * -circuit_get_rendezvous(const uint8_t *cookie) -{ - return circuit_get_by_rend_token_and_purpose( - CIRCUIT_PURPOSE_REND_POINT_WAITING, - 1, (const char*)cookie); -} - -/** Return the circuit waiting for intro cells of the given digest. - * Return NULL if no such circuit is found. - */ -or_circuit_t * -circuit_get_intro_point(const uint8_t *digest) -{ - return circuit_get_by_rend_token_and_purpose( - CIRCUIT_PURPOSE_INTRO_POINT, 0, - (const char *)digest); -} - -/** Set the rendezvous cookie of <b>circ</b> to <b>cookie</b>. If another - * circuit previously had that cookie, mark it. */ -void -circuit_set_rendezvous_cookie(or_circuit_t *circ, const uint8_t *cookie) -{ - circuit_set_rend_token(circ, 1, cookie); + return 0; } -/** Set the intro point key digest of <b>circ</b> to <b>cookie</b>. If another - * circuit previously had that intro point digest, mark it. */ -void -circuit_set_intro_point_digest(or_circuit_t *circ, const uint8_t *digest) +/** We are trying to create a circuit of purpose <b>purpose</b> and we are + * looking for cannibalizable circuits. Return the circuit purpose we would be + * willing to cannibalize. */ +static uint8_t +get_circuit_purpose_needed_to_cannibalize(uint8_t purpose) { - circuit_set_rend_token(circ, 0, digest); + if (circuit_should_use_vanguards(purpose)) { + /* If we are using vanguards, then we should only cannibalize vanguard + * circuits so that we get the same path construction logic. */ + return CIRCUIT_PURPOSE_HS_VANGUARDS; + } else { + /* If no vanguards are used just get a general circuit! */ + return CIRCUIT_PURPOSE_C_GENERAL; + } } /** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL, @@ -1534,14 +1759,21 @@ circuit_set_intro_point_digest(or_circuit_t *circ, const uint8_t *digest) * flags in <b>flags</b>, and if info is defined, does not already use info * as any of its hops; or NULL if no circuit fits this description. * - * The <b>purpose</b> argument (currently ignored) refers to the purpose of - * the circuit we want to create, not the purpose of the circuit we want to - * cannibalize. + * The <b>purpose</b> argument refers to the purpose of the circuit we want to + * create, not the purpose of the circuit we want to cannibalize. * * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits. + * + * To "cannibalize" a circuit means to extend it an extra hop, and use it + * for some other purpose than we had originally intended. We do this when + * we want to perform some low-bandwidth task at a specific relay, and we + * would like the circuit to complete as soon as possible. (If we were going + * to use a lot of bandwidth, we wouldn't want a circuit with an extra hop. + * If we didn't care about circuit completion latency, we would just build + * a new circuit.) */ origin_circuit_t * -circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info, +circuit_find_to_cannibalize(uint8_t purpose_to_produce, extend_info_t *info, int flags) { origin_circuit_t *best=NULL; @@ -1549,29 +1781,53 @@ circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info, int need_capacity = (flags & CIRCLAUNCH_NEED_CAPACITY) != 0; int internal = (flags & CIRCLAUNCH_IS_INTERNAL) != 0; const or_options_t *options = get_options(); + /* We want the circuit we are trying to cannibalize to have this purpose */ + int purpose_to_search_for; /* Make sure we're not trying to create a onehop circ by * cannibalization. */ tor_assert(!(flags & CIRCLAUNCH_ONEHOP_TUNNEL)); + purpose_to_search_for = get_circuit_purpose_needed_to_cannibalize( + purpose_to_produce); + + tor_assert_nonfatal(purpose_to_search_for == CIRCUIT_PURPOSE_C_GENERAL || + purpose_to_search_for == CIRCUIT_PURPOSE_HS_VANGUARDS); + log_debug(LD_CIRC, "Hunting for a circ to cannibalize: purpose %d, uptime %d, " "capacity %d, internal %d", - purpose, need_uptime, need_capacity, internal); + purpose_to_produce, need_uptime, need_capacity, internal); SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ_) { if (CIRCUIT_IS_ORIGIN(circ_) && circ_->state == CIRCUIT_STATE_OPEN && !circ_->marked_for_close && - circ_->purpose == CIRCUIT_PURPOSE_C_GENERAL && + circ_->purpose == purpose_to_search_for && !circ_->timestamp_dirty) { origin_circuit_t *circ = TO_ORIGIN_CIRCUIT(circ_); + + /* Only cannibalize from reasonable length circuits. If we + * want C_GENERAL, then only choose 3 hop circs. If we want + * HS_VANGUARDS, only choose 4 hop circs. + */ + if (circ->build_state->desired_path_len != + route_len_for_purpose(purpose_to_search_for, NULL)) { + goto next; + } + + /* Ignore any circuits for which we can't use the Guard. It is possible + * that the Guard was removed from the samepled set after the circuit + * was created so avoid using it. */ + if (!entry_guard_could_succeed(circ->guard_state)) { + goto next; + } + if ((!need_uptime || circ->build_state->need_uptime) && (!need_capacity || circ->build_state->need_capacity) && (internal == circ->build_state->is_internal) && !circ->unusable_for_new_conns && circ->remaining_relay_early_cells && - circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN && !circ->build_state->onehop_tunnel && !circ->isolation_values_set) { if (info) { @@ -1603,6 +1859,14 @@ circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info, hop = hop->next; } while (hop != circ->cpath); } + + if ((flags & CIRCLAUNCH_IS_V3_RP) && + !circuit_can_be_cannibalized_for_v3_rp(circ)) { + log_debug(LD_GENERAL, "Skipping uncannibalizable circuit for v3 " + "rendezvous point."); + goto next; + } + if (!best || (best->build_state->need_uptime && !need_uptime)) best = circ; next: ; @@ -1613,6 +1877,37 @@ circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info, return best; } +/** + * Check whether any of the origin circuits that are waiting to see if + * their guard is good enough to use can be upgraded to "ready". If so, + * return a new smartlist containing them. Otherwise return NULL. + */ +smartlist_t * +circuit_find_circuits_to_upgrade_from_guard_wait(void) +{ + /* Only if some circuit is actually waiting on an upgrade should we + * run the algorithm. */ + if (! circuits_pending_other_guards || + smartlist_len(circuits_pending_other_guards)==0) + return NULL; + /* Only if we have some origin circuits should we run the algorithm. */ + if (!global_origin_circuit_list) + return NULL; + + /* Okay; we can pass our circuit list to entrynodes.c.*/ + smartlist_t *result = smartlist_new(); + int circuits_upgraded = entry_guards_upgrade_waiting_circuits( + get_guard_selection_info(), + global_origin_circuit_list, + result); + if (circuits_upgraded && smartlist_len(result)) { + return result; + } else { + smartlist_free(result); + return NULL; + } +} + /** Return the number of hops in circuit's path. If circ has no entries, * or is NULL, returns 0. */ int @@ -1629,6 +1924,25 @@ circuit_get_cpath_len(origin_circuit_t *circ) return n; } +/** Return the number of opened hops in circuit's path. + * If circ has no entries, or is NULL, returns 0. */ +int +circuit_get_cpath_opened_len(const origin_circuit_t *circ) +{ + int n = 0; + if (circ && circ->cpath) { + crypt_path_t *cpath, *cpath_next = NULL; + for (cpath = circ->cpath; + cpath->state == CPATH_STATE_OPEN + && cpath_next != circ->cpath; + cpath = cpath_next) { + cpath_next = cpath->next; + ++n; + } + } + return n; +} + /** Return the <b>hopnum</b>th hop in <b>circ</b>->cpath, or NULL if there * aren't that many hops in the list. <b>hopnum</b> starts at 1. * Returns NULL if <b>hopnum</b> is 0 or negative. */ @@ -1685,8 +1999,7 @@ circuit_mark_all_dirty_circs_as_unusable(void) * - If state is onionskin_pending, remove circ from the onion_pending * list. * - If circ isn't open yet: call circuit_build_failed() if we're - * the origin, and in either case call circuit_rep_hist_note_result() - * to note stats. + * the origin. * - If purpose is C_INTRODUCE_ACK_WAIT, report the intro point * failure we just had to the hidden service client module. * - If purpose is C_INTRODUCING and <b>reason</b> isn't TIMEOUT, @@ -1757,10 +2070,20 @@ circuit_mark_for_close_, (circuit_t *circ, int reason, int line, } } + /* Notify the HS subsystem that this circuit is closing. */ + hs_circ_cleanup(circ); + if (circuits_pending_close == NULL) circuits_pending_close = smartlist_new(); smartlist_add(circuits_pending_close, circ); + + log_info(LD_GENERAL, "Circuit %u (id: %" PRIu32 ") marked for close at " + "%s:%d (orig reason: %d, new reason: %d)", + circ->n_circ_id, + CIRCUIT_IS_ORIGIN(circ) ? + TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0, + file, line, orig_reason, reason); } /** Called immediately before freeing a marked circuit <b>circ</b> from @@ -1807,20 +2130,25 @@ circuit_about_to_free(circuit_t *circ) * module then. If it isn't OPEN, we send it there now to remember which * links worked and which didn't. */ - if (circ->state != CIRCUIT_STATE_OPEN) { + if (circ->state != CIRCUIT_STATE_OPEN && + circ->state != CIRCUIT_STATE_GUARD_WAIT) { if (CIRCUIT_IS_ORIGIN(circ)) { origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ); circuit_build_failed(ocirc); /* take actions if necessary */ - circuit_rep_hist_note_result(ocirc); } } if (circ->state == CIRCUIT_STATE_CHAN_WAIT) { if (circuits_pending_chans) smartlist_remove(circuits_pending_chans, circ); } + if (circuits_pending_other_guards) { + smartlist_remove(circuits_pending_other_guards, circ); + } if (CIRCUIT_IS_ORIGIN(circ)) { control_event_circuit_status(TO_ORIGIN_CIRCUIT(circ), - (circ->state == CIRCUIT_STATE_OPEN)?CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED, + (circ->state == CIRCUIT_STATE_OPEN || + circ->state == CIRCUIT_STATE_GUARD_WAIT) ? + CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED, orig_reason); } @@ -1829,11 +2157,11 @@ circuit_about_to_free(circuit_t *circ) int timed_out = (reason == END_CIRC_REASON_TIMEOUT); tor_assert(circ->state == CIRCUIT_STATE_OPEN); tor_assert(ocirc->build_state->chosen_exit); - tor_assert(ocirc->rend_data); - if (orig_reason != END_CIRC_REASON_IP_NOW_REDUNDANT) { + if (orig_reason != END_CIRC_REASON_IP_NOW_REDUNDANT && + ocirc->rend_data) { /* treat this like getting a nack from it */ log_info(LD_REND, "Failed intro circ %s to %s (awaiting ack). %s", - safe_str_client(ocirc->rend_data->onion_address), + safe_str_client(rend_data_get_address(ocirc->rend_data)), safe_str_client(build_state_get_exit_nickname(ocirc->build_state)), timed_out ? "Recording timeout." : "Removing from descriptor."); rend_client_report_intro_point_failure(ocirc->build_state->chosen_exit, @@ -1846,11 +2174,12 @@ circuit_about_to_free(circuit_t *circ) reason != END_CIRC_REASON_TIMEOUT) { origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ); if (ocirc->build_state->chosen_exit && ocirc->rend_data) { - if (orig_reason != END_CIRC_REASON_IP_NOW_REDUNDANT) { + if (orig_reason != END_CIRC_REASON_IP_NOW_REDUNDANT && + ocirc->rend_data) { log_info(LD_REND, "Failed intro circ %s to %s " "(building circuit to intro point). " "Marking intro point as possibly unreachable.", - safe_str_client(ocirc->rend_data->onion_address), + safe_str_client(rend_data_get_address(ocirc->rend_data)), safe_str_client(build_state_get_exit_nickname( ocirc->build_state))); rend_client_report_intro_point_failure(ocirc->build_state->chosen_exit, @@ -1945,10 +2274,10 @@ single_conn_free_bytes(connection_t *conn) } if (conn->type == CONN_TYPE_DIR) { dir_connection_t *dir_conn = TO_DIR_CONN(conn); - if (dir_conn->zlib_state) { - result += tor_zlib_state_size(dir_conn->zlib_state); - tor_zlib_free(dir_conn->zlib_state); - dir_conn->zlib_state = NULL; + if (dir_conn->compress_state) { + result += tor_compress_state_size(dir_conn->compress_state); + tor_compress_free(dir_conn->compress_state); + dir_conn->compress_state = NULL; } } return result; @@ -1995,12 +2324,12 @@ n_cells_in_circ_queues(const circuit_t *c) } /** - * Return the age of the oldest cell queued on <b>c</b>, in milliseconds. + * Return the age of the oldest cell queued on <b>c</b>, in timestamp units. * Return 0 if there are no cells queued on c. Requires that <b>now</b> be - * the current time in milliseconds since the epoch, truncated. + * the current coarse timestamp. * * This function will return incorrect results if the oldest cell queued on - * the circuit is older than 2**32 msec (about 49 days) old. + * the circuit is older than about 2**32 msec (about 49 days) old. */ STATIC uint32_t circuit_max_queued_cell_age(const circuit_t *c, uint32_t now) @@ -2009,12 +2338,12 @@ circuit_max_queued_cell_age(const circuit_t *c, uint32_t now) packed_cell_t *cell; if (NULL != (cell = TOR_SIMPLEQ_FIRST(&c->n_chan_cells.head))) - age = now - cell->inserted_time; + age = now - cell->inserted_timestamp; if (! CIRCUIT_IS_ORIGIN(c)) { const or_circuit_t *orcirc = CONST_TO_OR_CIRCUIT(c); if (NULL != (cell = TOR_SIMPLEQ_FIRST(&orcirc->p_chan_cells.head))) { - uint32_t age2 = now - cell->inserted_time; + uint32_t age2 = now - cell->inserted_timestamp; if (age2 > age) return age2; } @@ -2022,31 +2351,30 @@ circuit_max_queued_cell_age(const circuit_t *c, uint32_t now) return age; } -/** Return the age in milliseconds of the oldest buffer chunk on <b>conn</b>, - * where age is taken in milliseconds before the time <b>now</b> (in truncated - * absolute monotonic msec). If the connection has no data, treat - * it as having age zero. +/** Return the age of the oldest buffer chunk on <b>conn</b>, where age is + * taken in timestamp units before the time <b>now</b>. If the connection has + * no data, treat it as having age zero. **/ static uint32_t -conn_get_buffer_age(const connection_t *conn, uint32_t now) +conn_get_buffer_age(const connection_t *conn, uint32_t now_ts) { uint32_t age = 0, age2; if (conn->outbuf) { - age2 = buf_get_oldest_chunk_timestamp(conn->outbuf, now); + age2 = buf_get_oldest_chunk_timestamp(conn->outbuf, now_ts); if (age2 > age) age = age2; } if (conn->inbuf) { - age2 = buf_get_oldest_chunk_timestamp(conn->inbuf, now); + age2 = buf_get_oldest_chunk_timestamp(conn->inbuf, now_ts); if (age2 > age) age = age2; } return age; } -/** Return the age in milliseconds of the oldest buffer chunk on any stream in - * the linked list <b>stream</b>, where age is taken in milliseconds before - * the time <b>now</b> (in truncated milliseconds since the epoch). */ +/** Return the age in timestamp units of the oldest buffer chunk on any stream + * in the linked list <b>stream</b>, where age is taken in timestamp units + * before the timestamp <b>now</b>. */ static uint32_t circuit_get_streams_max_data_age(const edge_connection_t *stream, uint32_t now) { @@ -2065,9 +2393,9 @@ circuit_get_streams_max_data_age(const edge_connection_t *stream, uint32_t now) return age; } -/** Return the age in milliseconds of the oldest buffer chunk on any stream - * attached to the circuit <b>c</b>, where age is taken in milliseconds before - * the time <b>now</b> (in truncated milliseconds since the epoch). */ +/** Return the age in timestamp units of the oldest buffer chunk on any stream + * attached to the circuit <b>c</b>, where age is taken before the timestamp + * <b>now</b>. */ STATIC uint32_t circuit_max_queued_data_age(const circuit_t *c, uint32_t now) { @@ -2081,8 +2409,8 @@ circuit_max_queued_data_age(const circuit_t *c, uint32_t now) } /** Return the age of the oldest cell or stream buffer chunk on the circuit - * <b>c</b>, where age is taken in milliseconds before the time <b>now</b> (in - * truncated milliseconds since the epoch). */ + * <b>c</b>, where age is taken in timestamp units before the timestamp + * <b>now</b> */ STATIC uint32_t circuit_max_queued_item_age(const circuit_t *c, uint32_t now) { @@ -2112,7 +2440,7 @@ circuits_compare_by_oldest_queued_item_(const void **a_, const void **b_) return -1; } -static uint32_t now_ms_for_buf_cmp; +static uint32_t now_ts_for_buf_cmp; /** Helper to sort a list of circuit_t by age of oldest item, in descending * order. */ @@ -2121,8 +2449,8 @@ conns_compare_by_buffer_age_(const void **a_, const void **b_) { const connection_t *a = *a_; const connection_t *b = *b_; - time_t age_a = conn_get_buffer_age(a, now_ms_for_buf_cmp); - time_t age_b = conn_get_buffer_age(b, now_ms_for_buf_cmp); + time_t age_a = conn_get_buffer_age(a, now_ts_for_buf_cmp); + time_t age_b = conn_get_buffer_age(b, now_ts_for_buf_cmp); if (age_a < age_b) return 1; @@ -2147,10 +2475,22 @@ circuits_handle_oom(size_t current_allocation) size_t mem_recovered=0; int n_circuits_killed=0; int n_dirconns_killed=0; - uint32_t now_ms; - log_notice(LD_GENERAL, "We're low on memory. Killing circuits with " - "over-long queues. (This behavior is controlled by " - "MaxMemInQueues.)"); + uint32_t now_ts; + log_notice(LD_GENERAL, "We're low on memory (cell queues total alloc:" + " %"TOR_PRIuSZ" buffer total alloc: %" TOR_PRIuSZ "," + " tor compress total alloc: %" TOR_PRIuSZ + " (zlib: %" TOR_PRIuSZ ", zstd: %" TOR_PRIuSZ "," + " lzma: %" TOR_PRIuSZ ")," + " rendezvous cache total alloc: %" TOR_PRIuSZ "). Killing" + " circuits withover-long queues. (This behavior is controlled by" + " MaxMemInQueues.)", + cell_queues_get_total_allocation(), + buf_get_total_allocation(), + tor_compress_get_total_allocation(), + tor_zlib_get_total_allocation(), + tor_zstd_get_total_allocation(), + tor_lzma_get_total_allocation(), + rend_cache_get_total_allocation()); { size_t mem_target = (size_t)(get_options()->MaxMemInQueues * @@ -2160,11 +2500,11 @@ circuits_handle_oom(size_t current_allocation) mem_to_recover = current_allocation - mem_target; } - now_ms = (uint32_t)monotime_coarse_absolute_msec(); + now_ts = monotime_coarse_get_stamp(); circlist = circuit_get_global_list(); SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) { - circ->age_tmp = circuit_max_queued_item_age(circ, now_ms); + circ->age_tmp = circuit_max_queued_item_age(circ, now_ts); } SMARTLIST_FOREACH_END(circ); /* This is O(n log n); there are faster algorithms we could use instead. @@ -2177,9 +2517,9 @@ circuits_handle_oom(size_t current_allocation) } SMARTLIST_FOREACH_END(circ); /* Now sort the connection array ... */ - now_ms_for_buf_cmp = now_ms; + now_ts_for_buf_cmp = now_ts; smartlist_sort(connection_array, conns_compare_by_buffer_age_); - now_ms_for_buf_cmp = 0; + now_ts_for_buf_cmp = 0; /* Fix up the connection array to its new order. */ SMARTLIST_FOREACH_BEGIN(connection_array, connection_t *, conn) { @@ -2198,7 +2538,7 @@ circuits_handle_oom(size_t current_allocation) * data older than this circuit. */ while (conn_idx < smartlist_len(connection_array)) { connection_t *conn = smartlist_get(connection_array, conn_idx); - uint32_t conn_age = conn_get_buffer_age(conn, now_ms); + uint32_t conn_age = conn_get_buffer_age(conn, now_ts); if (conn_age < circ->age_tmp) { break; } @@ -2300,8 +2640,8 @@ assert_cpath_ok(const crypt_path_t *cp) /** Verify that circuit <b>c</b> has all of its invariants * correct. Trigger an assert if anything is invalid. */ -void -assert_circuit_ok(const circuit_t *c) +MOCK_IMPL(void, +assert_circuit_ok,(const circuit_t *c)) { edge_connection_t *conn; const or_circuit_t *or_circ = NULL; @@ -2343,7 +2683,8 @@ assert_circuit_ok(const circuit_t *c) tor_assert(c->deliver_window >= 0); tor_assert(c->package_window >= 0); - if (c->state == CIRCUIT_STATE_OPEN) { + if (c->state == CIRCUIT_STATE_OPEN || + c->state == CIRCUIT_STATE_GUARD_WAIT) { tor_assert(!c->n_chan_create_cell); if (or_circ) { tor_assert(or_circ->n_crypto); |