diff options
Diffstat (limited to 'src/core')
29 files changed, 1322 insertions, 182 deletions
diff --git a/src/core/crypto/onion_crypto.c b/src/core/crypto/onion_crypto.c index f85ee2c82b..81e4e1b078 100644 --- a/src/core/crypto/onion_crypto.c +++ b/src/core/crypto/onion_crypto.c @@ -35,14 +35,28 @@ #include "core/crypto/onion_crypto.h" #include "core/crypto/onion_fast.h" #include "core/crypto/onion_ntor.h" +#include "core/crypto/onion_ntor_v3.h" #include "core/crypto/onion_tap.h" #include "feature/relay/router.h" #include "lib/crypt_ops/crypto_dh.h" #include "lib/crypt_ops/crypto_util.h" +#include "feature/relay/routerkeys.h" +#include "core/or/congestion_control_common.h" + +#include "core/or/circuitbuild.h" #include "core/or/crypt_path_st.h" #include "core/or/extend_info_st.h" +#include "trunnel/congestion_control.h" +#include "trunnel/extension.h" + +static const uint8_t NTOR3_CIRC_VERIFICATION[] = "circuit extend"; +static const size_t NTOR3_CIRC_VERIFICATION_LEN = 14; + +#define NTOR3_VERIFICATION_ARGS \ + NTOR3_CIRC_VERIFICATION, NTOR3_CIRC_VERIFICATION_LEN + /** Return a new server_onion_keys_t object with all of the keys * and other info we might need to do onion handshakes. (We make a copy of * our keys for each cpuworker to avoid race conditions with the main thread, @@ -52,6 +66,7 @@ server_onion_keys_new(void) { server_onion_keys_t *keys = tor_malloc_zero(sizeof(server_onion_keys_t)); memcpy(keys->my_identity, router_get_my_id_digest(), DIGEST_LEN); + ed25519_pubkey_copy(&keys->my_ed_identity, get_master_identity_key()); dup_onion_keys(&keys->onion_key, &keys->last_onion_key); keys->curve25519_key_map = construct_ntor_key_map(); keys->junk_keypair = tor_malloc_zero(sizeof(curve25519_keypair_t)); @@ -91,6 +106,9 @@ onion_handshake_state_release(onion_handshake_state_t *state) ntor_handshake_state_free(state->u.ntor); state->u.ntor = NULL; break; + case ONION_HANDSHAKE_TYPE_NTOR_V3: + ntor3_handshake_state_free(state->u.ntor3); + break; default: /* LCOV_EXCL_START * This state should not even exist. */ @@ -103,19 +121,23 @@ onion_handshake_state_release(onion_handshake_state_t *state) /** Perform the first step of a circuit-creation handshake of type <b>type</b> * (one of ONION_HANDSHAKE_TYPE_*): generate the initial "onion skin" in - * <b>onion_skin_out</b>, and store any state information in <b>state_out</b>. + * <b>onion_skin_out</b> with length of up to <b>onion_skin_out_maxlen</b>, + * and store any state information in <b>state_out</b>. * Return -1 on failure, and the length of the onionskin on acceptance. */ int onion_skin_create(int type, const extend_info_t *node, onion_handshake_state_t *state_out, - uint8_t *onion_skin_out) + uint8_t *onion_skin_out, + size_t onion_skin_out_maxlen) { int r = -1; switch (type) { case ONION_HANDSHAKE_TYPE_TAP: + if (onion_skin_out_maxlen < TAP_ONIONSKIN_CHALLENGE_LEN) + return -1; if (!node->onion_key) return -1; @@ -133,7 +155,9 @@ onion_skin_create(int type, r = CREATE_FAST_LEN; break; case ONION_HANDSHAKE_TYPE_NTOR: - if (!extend_info_supports_ntor(node)) + if (onion_skin_out_maxlen < NTOR_ONIONSKIN_LEN) + return -1; + if (!extend_info_supports_ntor(node)) return -1; if (onion_skin_ntor_create((const uint8_t*)node->identity_digest, &node->curve25519_onion_key, @@ -143,6 +167,37 @@ onion_skin_create(int type, r = NTOR_ONIONSKIN_LEN; break; + case ONION_HANDSHAKE_TYPE_NTOR_V3: + if (!extend_info_supports_ntor_v3(node)) + return -1; + if (ed25519_public_key_is_zero(&node->ed_identity)) + return -1; + size_t msg_len = 0; + uint8_t *msg = NULL; + if (client_circ_negotiation_message(node, &msg, &msg_len) < 0) + return -1; + uint8_t *onion_skin = NULL; + size_t onion_skin_len = 0; + int status = onion_skin_ntor3_create( + &node->ed_identity, + &node->curve25519_onion_key, + NTOR3_VERIFICATION_ARGS, + msg, msg_len, /* client message */ + &state_out->u.ntor3, + &onion_skin, &onion_skin_len); + tor_free(msg); + if (status < 0) { + return -1; + } + if (onion_skin_len > onion_skin_out_maxlen) { + tor_free(onion_skin); + return -1; + } + memcpy(onion_skin_out, onion_skin, onion_skin_len); + tor_free(onion_skin); + r = (int) onion_skin_len; + break; + default: /* LCOV_EXCL_START * We should never try to create an impossible handshake type. */ @@ -158,6 +213,50 @@ onion_skin_create(int type, return r; } +/** + * Takes a param request message from the client, compares it to our + * consensus parameters, and creates a reply message and output + * parameters. + * + * This function runs in a worker thread, so it can only inspect + * arguments and local variables. + * + * Returns 0 if successful. + * Returns -1 on parsing, parameter failure, or reply creation failure. + */ +static int +negotiate_v3_ntor_server_circ_params(const uint8_t *param_request_msg, + size_t param_request_len, + const circuit_params_t *our_ns_params, + circuit_params_t *params_out, + uint8_t **resp_msg_out, + size_t *resp_msg_len_out) +{ + int ret; + + /* Parse request. */ + ret = congestion_control_parse_ext_request(param_request_msg, + param_request_len); + if (ret < 0) { + goto err; + } + params_out->cc_enabled = ret && our_ns_params->cc_enabled; + + /* Build the response. */ + ret = congestion_control_build_ext_response(our_ns_params, params_out, + resp_msg_out, resp_msg_len_out); + if (ret < 0) { + goto err; + } + params_out->sendme_inc_cells = our_ns_params->sendme_inc_cells; + + /* Success. */ + ret = 0; + + err: + return ret; +} + /* This is the maximum value for keys_out_len passed to * onion_skin_server_handshake, plus 16. We can make it bigger if needed: * It just defines how many bytes to stack-allocate. */ @@ -174,14 +273,20 @@ int onion_skin_server_handshake(int type, const uint8_t *onion_skin, size_t onionskin_len, const server_onion_keys_t *keys, + const circuit_params_t *our_ns_params, uint8_t *reply_out, + size_t reply_out_maxlen, uint8_t *keys_out, size_t keys_out_len, - uint8_t *rend_nonce_out) + uint8_t *rend_nonce_out, + circuit_params_t *params_out) { int r = -1; + memset(params_out, 0, sizeof(*params_out)); switch (type) { case ONION_HANDSHAKE_TYPE_TAP: + if (reply_out_maxlen < TAP_ONIONSKIN_REPLY_LEN) + return -1; if (onionskin_len != TAP_ONIONSKIN_CHALLENGE_LEN) return -1; if (onion_skin_TAP_server_handshake((const char*)onion_skin, @@ -193,6 +298,8 @@ onion_skin_server_handshake(int type, memcpy(rend_nonce_out, reply_out+DH1024_KEY_LEN, DIGEST_LEN); break; case ONION_HANDSHAKE_TYPE_FAST: + if (reply_out_maxlen < CREATED_FAST_LEN) + return -1; if (onionskin_len != CREATE_FAST_LEN) return -1; if (fast_server_handshake(onion_skin, reply_out, keys_out, keys_out_len)<0) @@ -201,6 +308,8 @@ onion_skin_server_handshake(int type, memcpy(rend_nonce_out, reply_out+DIGEST_LEN, DIGEST_LEN); break; case ONION_HANDSHAKE_TYPE_NTOR: + if (reply_out_maxlen < NTOR_REPLY_LEN) + return -1; if (onionskin_len < NTOR_ONIONSKIN_LEN) return -1; { @@ -223,6 +332,71 @@ onion_skin_server_handshake(int type, r = NTOR_REPLY_LEN; } break; + case ONION_HANDSHAKE_TYPE_NTOR_V3: { + size_t keys_tmp_len = keys_out_len + DIGEST_LEN; + tor_assert(keys_tmp_len <= MAX_KEYS_TMP_LEN); + uint8_t keys_tmp[MAX_KEYS_TMP_LEN]; + uint8_t *client_msg = NULL; + size_t client_msg_len = 0; + uint8_t *reply_msg = NULL; + size_t reply_msg_len = 0; + + ntor3_server_handshake_state_t *state = NULL; + + if (onion_skin_ntor3_server_handshake_part1( + keys->curve25519_key_map, + keys->junk_keypair, + &keys->my_ed_identity, + onion_skin, onionskin_len, + NTOR3_VERIFICATION_ARGS, + &client_msg, &client_msg_len, + &state) < 0) { + return -1; + } + + if (negotiate_v3_ntor_server_circ_params(client_msg, + client_msg_len, + our_ns_params, + params_out, + &reply_msg, + &reply_msg_len) < 0) { + ntor3_server_handshake_state_free(state); + tor_free(client_msg); + return -1; + } + tor_free(client_msg); + + uint8_t *server_handshake = NULL; + size_t server_handshake_len = 0; + if (onion_skin_ntor3_server_handshake_part2( + state, + NTOR3_VERIFICATION_ARGS, + reply_msg, reply_msg_len, + &server_handshake, &server_handshake_len, + keys_tmp, keys_tmp_len) < 0) { + tor_free(reply_msg); + ntor3_server_handshake_state_free(state); + return -1; + } + tor_free(reply_msg); + + if (server_handshake_len > reply_out_maxlen) { + tor_free(server_handshake); + ntor3_server_handshake_state_free(state); + return -1; + } + + memcpy(keys_out, keys_tmp, keys_out_len); + memcpy(rend_nonce_out, keys_tmp+keys_out_len, DIGEST_LEN); + memcpy(reply_out, server_handshake, server_handshake_len); + memwipe(keys_tmp, 0, keys_tmp_len); + memwipe(server_handshake, 0, server_handshake_len); + tor_free(server_handshake); + ntor3_server_handshake_state_free(state); + + r = (int) server_handshake_len; + } + break; default: /* LCOV_EXCL_START * We should have rejected this far before this point */ @@ -235,6 +409,44 @@ onion_skin_server_handshake(int type, return r; } +/** + * Takes a param response message from the exit, compares it to our + * consensus parameters for sanity, and creates output parameters + * if sane. + * + * Returns -1 on parsing or insane params, 0 if success. + */ +static int +negotiate_v3_ntor_client_circ_params(const uint8_t *param_response_msg, + size_t param_response_len, + circuit_params_t *params_out) +{ + int ret = congestion_control_parse_ext_response(param_response_msg, + param_response_len, + params_out); + if (ret < 0) { + return -1; + } + + /* If congestion control came back enabled, but we didn't ask for it + * because the consensus said no, close the circuit. + * + * This is a fatal error condition for the circuit, because it either + * means that congestion control was disabled by the consensus + * during the handshake, or the exit decided to send us an unsolicited + * congestion control response. + * + * In either case, we cannot proceed on this circuit, and must try a + * new one. + */ + if (ret && !congestion_control_enabled()) { + return -1; + } + params_out->cc_enabled = ret; + + return 0; +} + /** Perform the final (client-side) step of a circuit-creation handshake of * type <b>type</b>, using our state in <b>handshake_state</b> and the * server's response in <b>reply</b>. On success, generate <b>keys_out_len</b> @@ -249,11 +461,14 @@ onion_skin_client_handshake(int type, const uint8_t *reply, size_t reply_len, uint8_t *keys_out, size_t keys_out_len, uint8_t *rend_authenticator_out, + circuit_params_t *params_out, const char **msg_out) { if (handshake_state->tag != type) return -1; + memset(params_out, 0, sizeof(*params_out)); + switch (type) { case ONION_HANDSHAKE_TYPE_TAP: if (reply_len != TAP_ONIONSKIN_REPLY_LEN) { @@ -303,6 +518,39 @@ onion_skin_client_handshake(int type, tor_free(keys_tmp); } return 0; + case ONION_HANDSHAKE_TYPE_NTOR_V3: { + size_t keys_tmp_len = keys_out_len + DIGEST_LEN; + uint8_t *keys_tmp = tor_malloc(keys_tmp_len); + uint8_t *server_msg = NULL; + size_t server_msg_len = 0; + int r = onion_ntor3_client_handshake( + handshake_state->u.ntor3, + reply, reply_len, + NTOR3_VERIFICATION_ARGS, + keys_tmp, keys_tmp_len, + &server_msg, &server_msg_len); + if (r < 0) { + tor_free(keys_tmp); + tor_free(server_msg); + return -1; + } + + if (negotiate_v3_ntor_client_circ_params(server_msg, + server_msg_len, + params_out) < 0) { + tor_free(keys_tmp); + tor_free(server_msg); + return -1; + } + tor_free(server_msg); + + memcpy(keys_out, keys_tmp, keys_out_len); + memcpy(rend_authenticator_out, keys_tmp + keys_out_len, DIGEST_LEN); + memwipe(keys_tmp, 0, keys_tmp_len); + tor_free(keys_tmp); + + return 0; + } default: log_warn(LD_BUG, "called with unknown handshake state type %d", type); tor_fragile_assert(); diff --git a/src/core/crypto/onion_crypto.h b/src/core/crypto/onion_crypto.h index 68cd465cf7..cb0188ff54 100644 --- a/src/core/crypto/onion_crypto.h +++ b/src/core/crypto/onion_crypto.h @@ -12,8 +12,11 @@ #ifndef TOR_ONION_CRYPTO_H #define TOR_ONION_CRYPTO_H +#include "lib/crypt_ops/crypto_ed25519.h" + typedef struct server_onion_keys_t { uint8_t my_identity[DIGEST_LEN]; + ed25519_public_key_t my_ed_identity; crypto_pk_t *onion_key; crypto_pk_t *last_onion_key; struct di_digest256_map_t *curve25519_key_map; @@ -22,21 +25,37 @@ typedef struct server_onion_keys_t { void onion_handshake_state_release(onion_handshake_state_t *state); +/** + * Parameters negotiated as part of a circuit handshake. + */ +typedef struct circuit_params_t { + /** Is true if congestion control is enabled in consensus or param, + * as per congestion_control_enabled() result. */ + bool cc_enabled; + /** The number of cells in a sendme increment. Only used if cc_enabled=1. */ + uint8_t sendme_inc_cells; +} circuit_params_t; + int onion_skin_create(int type, const extend_info_t *node, onion_handshake_state_t *state_out, - uint8_t *onion_skin_out); + uint8_t *onion_skin_out, + size_t onion_skin_out_maxlen); int onion_skin_server_handshake(int type, const uint8_t *onion_skin, size_t onionskin_len, const server_onion_keys_t *keys, + const circuit_params_t *ns_params, uint8_t *reply_out, + size_t reply_out_maxlen, uint8_t *keys_out, size_t key_out_len, - uint8_t *rend_nonce_out); + uint8_t *rend_nonce_out, + circuit_params_t *negotiated_params_out); int onion_skin_client_handshake(int type, const onion_handshake_state_t *handshake_state, const uint8_t *reply, size_t reply_len, uint8_t *keys_out, size_t key_out_len, uint8_t *rend_authenticator_out, + circuit_params_t *negotiated_params_out, const char **msg_out); server_onion_keys_t *server_onion_keys_new(void); diff --git a/src/core/mainloop/cpuworker.c b/src/core/mainloop/cpuworker.c index 17855b8567..ab970259b5 100644 --- a/src/core/mainloop/cpuworker.c +++ b/src/core/mainloop/cpuworker.c @@ -21,6 +21,8 @@ #include "core/or/channel.h" #include "core/or/circuitlist.h" #include "core/or/connection_or.h" +#include "core/or/congestion_control_common.h" +#include "core/or/congestion_control_flow.h" #include "app/config/config.h" #include "core/mainloop/cpuworker.h" #include "lib/crypt_ops/crypto_rand.h" @@ -126,6 +128,11 @@ typedef struct cpuworker_request_t { /** A create cell for the cpuworker to process. */ create_cell_t create_cell; + /** + * A copy of this relay's consensus params that are relevant to + * the circuit, for use in negotiation. */ + circuit_params_t circ_ns_params; + /* Turn the above into a tagged union if needed. */ } cpuworker_request_t; @@ -158,6 +165,8 @@ typedef struct cpuworker_reply_t { uint8_t keys[CPATH_KEY_MATERIAL_LEN]; /** Input to use for authenticating introduce1 cells. */ uint8_t rend_auth_material[DIGEST_LEN]; + /** Negotiated circuit parameters. */ + circuit_params_t circ_params; } cpuworker_reply_t; typedef struct cpuworker_job_u_t { @@ -379,6 +388,18 @@ cpuworker_onion_handshake_replyfn(void *work_) goto done_processing; } + /* If the client asked for congestion control, if our consensus parameter + * allowed it to negotiate as enabled, allocate a congestion control obj. */ + if (rpl.circ_params.cc_enabled) { + if (get_options()->SbwsExit) { + TO_CIRCUIT(circ)->ccontrol = congestion_control_new(&rpl.circ_params, + CC_PATH_SBWS); + } else { + TO_CIRCUIT(circ)->ccontrol = congestion_control_new(&rpl.circ_params, + CC_PATH_EXIT); + } + } + if (onionskin_answer(circ, &rpl.created_cell, (const char*)rpl.keys, sizeof(rpl.keys), @@ -387,6 +408,7 @@ cpuworker_onion_handshake_replyfn(void *work_) circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL); goto done_processing; } + log_debug(LD_OR,"onionskin_answer succeeded. Yay."); done_processing: @@ -425,9 +447,12 @@ cpuworker_onion_handshake_threadfn(void *state_, void *work_) n = onion_skin_server_handshake(cc->handshake_type, cc->onionskin, cc->handshake_len, onion_keys, + &req.circ_ns_params, cell_out->reply, + sizeof(cell_out->reply), rpl.keys, CPATH_KEY_MATERIAL_LEN, - rpl.rend_auth_material); + rpl.rend_auth_material, + &rpl.circ_params); if (n < 0) { /* failure */ log_debug(LD_OR,"onion_skin_server_handshake failed."); @@ -450,6 +475,7 @@ cpuworker_onion_handshake_threadfn(void *state_, void *work_) } rpl.success = 1; } + rpl.magic = CPUWORKER_REPLY_MAGIC; if (req.timed) { struct timeval tv_diff; @@ -550,6 +576,11 @@ assign_onionskin_to_cpuworker(or_circuit_t *circ, if (should_time) tor_gettimeofday(&req.started_at); + /* Copy the current cached consensus params relevant to + * circuit negotiation into the CPU worker context */ + req.circ_ns_params.cc_enabled = congestion_control_enabled(); + req.circ_ns_params.sendme_inc_cells = congestion_control_sendme_inc(); + job = tor_malloc_zero(sizeof(cpuworker_job_t)); job->circ = circ; memcpy(&job->u.request, &req, sizeof(req)); diff --git a/src/core/or/circuitbuild.c b/src/core/or/circuitbuild.c index 31e3868b65..f62a1d93f5 100644 --- a/src/core/or/circuitbuild.c +++ b/src/core/or/circuitbuild.c @@ -72,6 +72,7 @@ #include "feature/stats/predict_ports.h" #include "lib/crypt_ops/crypto_rand.h" #include "lib/trace/events.h" +#include "core/or/congestion_control_common.h" #include "core/or/cell_st.h" #include "core/or/cpath_build_state_st.h" @@ -81,6 +82,9 @@ #include "core/or/or_circuit_st.h" #include "core/or/origin_circuit_st.h" +#include "trunnel/extension.h" +#include "trunnel/congestion_control.h" + static int circuit_send_first_onion_skin(origin_circuit_t *circ); static int circuit_build_no_more_hops(origin_circuit_t *circ); static int circuit_send_intermediate_onion_skin(origin_circuit_t *circ, @@ -841,7 +845,13 @@ circuit_pick_create_handshake(uint8_t *cell_type_out, * using the TAP handshake, and CREATE2 otherwise. */ if (extend_info_supports_ntor(ei)) { *cell_type_out = CELL_CREATE2; - *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR; + /* Only use ntor v3 with exits that support congestion control, + * and only when it is enabled. */ + if (ei->exit_supports_congestion_control && + congestion_control_enabled()) + *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR_V3; + else + *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR; } else { /* XXXX030 Remove support for deciding to use TAP and EXTEND. */ *cell_type_out = CELL_CREATE; @@ -995,7 +1005,8 @@ circuit_send_first_onion_skin(origin_circuit_t *circ) len = onion_skin_create(cc.handshake_type, circ->cpath->extend_info, &circ->cpath->handshake_state, - cc.onionskin); + cc.onionskin, + sizeof(cc.onionskin)); if (len < 0) { log_warn(LD_CIRC,"onion_skin_create (first hop) failed."); return - END_CIRC_REASON_INTERNAL; @@ -1142,7 +1153,8 @@ circuit_send_intermediate_onion_skin(origin_circuit_t *circ, len = onion_skin_create(ec.create_cell.handshake_type, hop->extend_info, &hop->handshake_state, - ec.create_cell.onionskin); + ec.create_cell.onionskin, + sizeof(ec.create_cell.onionskin)); if (len < 0) { log_warn(LD_CIRC,"onion_skin_create failed."); return - END_CIRC_REASON_INTERNAL; @@ -1240,6 +1252,7 @@ circuit_finish_handshake(origin_circuit_t *circ, } tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS); + circuit_params_t params; { const char *msg = NULL; if (onion_skin_client_handshake(hop->handshake_state.tag, @@ -1247,6 +1260,7 @@ circuit_finish_handshake(origin_circuit_t *circ, reply->reply, reply->handshake_len, (uint8_t*)keys, sizeof(keys), (uint8_t*)hop->rend_circ_nonce, + ¶ms, &msg) < 0) { if (msg) log_warn(LD_CIRC,"onion_skin_client_handshake failed: %s", msg); @@ -1260,6 +1274,24 @@ circuit_finish_handshake(origin_circuit_t *circ, return -END_CIRC_REASON_TORPROTOCOL; } + if (params.cc_enabled) { + int circ_len = circuit_get_cpath_len(circ); + + if (circ_len == DEFAULT_ROUTE_LEN && + circuit_get_cpath_hop(circ, DEFAULT_ROUTE_LEN) == hop) { + hop->ccontrol = congestion_control_new(¶ms, CC_PATH_EXIT); + } else if (circ_len == SBWS_ROUTE_LEN && + circuit_get_cpath_hop(circ, SBWS_ROUTE_LEN) == hop) { + hop->ccontrol = congestion_control_new(¶ms, CC_PATH_SBWS); + } else { + static ratelim_t cc_path_limit = RATELIM_INIT(600); + log_fn_ratelim(&cc_path_limit, LOG_WARN, LD_CIRC, + "Unexpected path length %d for circuit", + circ_len); + hop->ccontrol = congestion_control_new(¶ms, CC_PATH_EXIT); + } + } + hop->state = CPATH_STATE_OPEN; log_info(LD_CIRC,"Finished building circuit hop:"); circuit_log_path(LOG_INFO,LD_CIRC,circ); @@ -2059,7 +2091,10 @@ onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit_ei, log_warn(LD_CIRC,"Failed to choose an exit server"); return -1; } - exit_ei = extend_info_from_node(node, state->onehop_tunnel); + exit_ei = extend_info_from_node(node, state->onehop_tunnel, + /* for_exit_use */ + !state->is_internal && TO_CIRCUIT(circ)->purpose == + CIRCUIT_PURPOSE_C_GENERAL); if (BUG(exit_ei == NULL)) return -1; } @@ -2455,7 +2490,7 @@ onion_extend_cpath(origin_circuit_t *circ) primary address, for potentially connecting to an IPv6 OR port. Servers always want the primary (IPv4) address. */ int client = (server_mode(get_options()) == 0); - info = extend_info_from_node(r, client); + info = extend_info_from_node(r, client, false); /* Clients can fail to find an allowed address */ tor_assert_nonfatal(info || client); } @@ -2463,7 +2498,7 @@ onion_extend_cpath(origin_circuit_t *circ) const node_t *r = choose_good_middle_server(purpose, state, circ->cpath, cur_len); if (r) { - info = extend_info_from_node(r, 0); + info = extend_info_from_node(r, 0, false); } } @@ -2573,3 +2608,25 @@ circuit_upgrade_circuits_from_guard_wait(void) smartlist_free(to_upgrade); } + +/** + * Try to generate a circuit-negotiation message for communication with a + * given relay. Assumes we are using ntor v3, or some later version that + * supports parameter negotiatoin. + * + * On success, return 0 and pass back a message in the `out` parameters. + * Otherwise, return -1. + **/ +int +client_circ_negotiation_message(const extend_info_t *ei, + uint8_t **msg_out, + size_t *msg_len_out) +{ + tor_assert(ei && msg_out && msg_len_out); + + if (!ei->exit_supports_congestion_control) { + return -1; + } + + return congestion_control_build_ext_request(msg_out, msg_len_out); +} diff --git a/src/core/or/circuitbuild.h b/src/core/or/circuitbuild.h index 278cdfae1c..a66c611132 100644 --- a/src/core/or/circuitbuild.h +++ b/src/core/or/circuitbuild.h @@ -64,6 +64,10 @@ circuit_deliver_create_cell,(circuit_t *circ, const struct create_cell_t *create_cell, int relayed)); +int client_circ_negotiation_message(const extend_info_t *ei, + uint8_t **msg_out, + size_t *msg_len_out); + #ifdef CIRCUITBUILD_PRIVATE STATIC circid_t get_unique_circ_id_by_chan(channel_t *chan); STATIC int new_route_len(uint8_t purpose, extend_info_t *exit_ei, diff --git a/src/core/or/circuituse.c b/src/core/or/circuituse.c index 2ec391eca0..a259957d37 100644 --- a/src/core/or/circuituse.c +++ b/src/core/or/circuituse.c @@ -2427,7 +2427,8 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn, /* We might want to connect to an IPv6 bridge for loading descriptors so we use the preferred address rather than the primary. */ - extend_info = extend_info_from_node(r, conn->want_onehop ? 1 : 0); + extend_info = extend_info_from_node(r, conn->want_onehop ? 1 : 0, + desired_circuit_purpose == CIRCUIT_PURPOSE_C_GENERAL); if (!extend_info) { log_warn(LD_CIRC,"Could not make a one-hop connection to %s. " "Discarding this circuit.", conn->chosen_exit_name); @@ -2462,7 +2463,9 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn, digest, NULL, /* Ed25519 ID */ NULL, NULL, /* onion keys */ - &addr, conn->socks_request->port); + &addr, conn->socks_request->port, + NULL, + false); } else { /* ! (want_onehop && conn->chosen_exit_name[0] == '$') */ /* We will need an onion key for the router, and we * don't have one. Refuse or relax requirements. */ diff --git a/src/core/or/command.c b/src/core/or/command.c index 40eb1554c0..ffdd1f19d9 100644 --- a/src/core/or/command.c +++ b/src/core/or/command.c @@ -360,15 +360,19 @@ command_process_create_cell(cell_t *cell, channel_t *chan) uint8_t rend_circ_nonce[DIGEST_LEN]; int len; created_cell_t created_cell; + circuit_params_t params; memset(&created_cell, 0, sizeof(created_cell)); len = onion_skin_server_handshake(ONION_HANDSHAKE_TYPE_FAST, create_cell->onionskin, create_cell->handshake_len, NULL, + NULL, created_cell.reply, + sizeof(created_cell.reply), keys, CPATH_KEY_MATERIAL_LEN, - rend_circ_nonce); + rend_circ_nonce, + ¶ms); tor_free(create_cell); if (len < 0) { log_warn(LD_OR,"Failed to generate key material. Closing."); diff --git a/src/core/or/congestion_control_common.c b/src/core/or/congestion_control_common.c index 0919f037db..93d3a9f2c5 100644 --- a/src/core/or/congestion_control_common.c +++ b/src/core/or/congestion_control_common.c @@ -10,6 +10,7 @@ #include "core/or/or.h" +#include "core/crypto/onion_crypto.h" #include "core/or/circuitlist.h" #include "core/or/crypt_path.h" #include "core/or/or_circuit_st.h" @@ -25,22 +26,32 @@ #include "core/or/trace_probes_cc.h" #include "lib/time/compat_time.h" #include "feature/nodelist/networkstatus.h" +#include "app/config/config.h" + +#include "trunnel/congestion_control.h" +#include "trunnel/extension.h" /* Consensus parameter defaults. * * More details for each of the parameters can be found in proposal 324, * section 6.5 including tuning notes. */ -#define CIRCWINDOW_INIT (500) -#define SENDME_INC_DFLT (50) +#define SENDME_INC_DFLT (TLS_RECORD_MAX_CELLS) +#define CIRCWINDOW_INIT (4*SENDME_INC_DFLT) + +#define CC_ALG_DFLT (CC_ALG_SENDME) +#define CC_ALG_DFLT_ALWAYS (CC_ALG_VEGAS) -#define CWND_INC_DFLT (50) -#define CWND_INC_PCT_SS_DFLT (100) +#define CWND_INC_DFLT (TLS_RECORD_MAX_CELLS) +#define CWND_INC_PCT_SS_DFLT (50) #define CWND_INC_RATE_DFLT (1) + +#define CWND_MIN_DFLT (SENDME_INC_DFLT) #define CWND_MAX_DFLT (INT32_MAX) -#define CWND_MIN_DFLT (MAX(100, SENDME_INC_DFLT)) #define BWE_SENDME_MIN_DFLT (5) -#define EWMA_CWND_COUNT_DFLT (2) + +#define N_EWMA_CWND_PCT_DFLT (50) +#define N_EWMA_MAX_DFLT (10) /* BDP algorithms for each congestion control algorithms use the piecewise * estimattor. See section 3.1.4 of proposal 324. */ @@ -74,6 +85,8 @@ static bool congestion_control_update_circuit_bdp(congestion_control_t *, const circuit_t *, const crypt_path_t *, uint64_t, uint64_t); +/* For unit tests */ +void congestion_control_set_cc_enabled(void); /* Consensus parameters cached. The non static ones are extern. */ static uint32_t cwnd_max = CWND_MAX_DFLT; @@ -81,6 +94,23 @@ int32_t cell_queue_high = CELL_QUEUE_HIGH_DFLT; int32_t cell_queue_low = CELL_QUEUE_LOW_DFLT; uint32_t or_conn_highwater = OR_CONN_HIGHWATER_DFLT; uint32_t or_conn_lowwater = OR_CONN_LOWWATER_DFLT; +uint8_t cc_sendme_inc = SENDME_INC_DFLT; +static cc_alg_t cc_alg = CC_ALG_DFLT; + +/** + * Number of cwnd worth of sendme acks to smooth RTT and BDP with, + * using N_EWMA */ +static uint8_t n_ewma_cwnd_pct; + +/** + * Maximum number N for the N-count EWMA averaging of RTT and BDP. + */ +static uint8_t n_ewma_max; + +/** + * Minimum number of sendmes before we begin BDP estimates + */ +static uint8_t bwe_sendme_min; /** * Update global congestion control related consensus parameter values, @@ -126,6 +156,46 @@ congestion_control_new_consensus_params(const networkstatus_t *ns) CWND_MAX_DFLT, CWND_MAX_MIN, CWND_MAX_MAX); + +#define SENDME_INC_MIN 1 +#define SENDME_INC_MAX (255) + cc_sendme_inc = + networkstatus_get_param(NULL, "cc_sendme_inc", + SENDME_INC_DFLT, + SENDME_INC_MIN, + SENDME_INC_MAX); + +#define CC_ALG_MIN 0 +#define CC_ALG_MAX (NUM_CC_ALGS-1) + cc_alg = + networkstatus_get_param(NULL, "cc_alg", + CC_ALG_DFLT, + CC_ALG_MIN, + CC_ALG_MAX); + +#define BWE_SENDME_MIN_MIN 2 +#define BWE_SENDME_MIN_MAX (20) + bwe_sendme_min = + networkstatus_get_param(NULL, "cc_bwe_min", + BWE_SENDME_MIN_DFLT, + BWE_SENDME_MIN_MIN, + BWE_SENDME_MIN_MAX); + +#define N_EWMA_CWND_PCT_MIN 1 +#define N_EWMA_CWND_PCT_MAX (255) + n_ewma_cwnd_pct = + networkstatus_get_param(NULL, "cc_ewma_cwnd_pct", + N_EWMA_CWND_PCT_DFLT, + N_EWMA_CWND_PCT_MIN, + N_EWMA_CWND_PCT_MAX); + +#define N_EWMA_MAX_MIN 2 +#define N_EWMA_MAX_MAX (INT32_MAX) + n_ewma_max = + networkstatus_get_param(NULL, "cc_ewma_max", + N_EWMA_MAX_DFLT, + N_EWMA_MAX_MIN, + N_EWMA_MAX_MAX); } /** @@ -139,10 +209,13 @@ congestion_control_new_consensus_params(const networkstatus_t *ns) */ static void congestion_control_init_params(congestion_control_t *cc, - cc_alg_t cc_alg, - int sendme_inc) + const circuit_params_t *params, + cc_path_t path) { -#define CWND_INIT_MIN 100 + const or_options_t *opts = get_options(); + cc->sendme_inc = params->sendme_inc_cells; + +#define CWND_INIT_MIN SENDME_INC_DFLT #define CWND_INIT_MAX (10000) cc->cwnd = networkstatus_get_param(NULL, "cc_cwnd_init", @@ -174,16 +247,7 @@ congestion_control_init_params(congestion_control_t *cc, CWND_INC_RATE_MIN, CWND_INC_RATE_MAX); -#define SENDME_INC_MIN 10 -#define SENDME_INC_MAX (1000) - cc->sendme_inc = - networkstatus_get_param(NULL, "cc_sendme_inc", - sendme_inc, - SENDME_INC_MIN, - SENDME_INC_MAX); - - // XXX: this min needs to abide by sendme_inc range rules somehow -#define CWND_MIN_MIN sendme_inc +#define CWND_MIN_MIN SENDME_INC_DFLT #define CWND_MIN_MAX (1000) cc->cwnd_min = networkstatus_get_param(NULL, "cc_cwnd_min", @@ -191,29 +255,14 @@ congestion_control_init_params(congestion_control_t *cc, CWND_MIN_MIN, CWND_MIN_MAX); -#define EWMA_CWND_COUNT_MIN 1 -#define EWMA_CWND_COUNT_MAX (100) - cc->ewma_cwnd_cnt = - networkstatus_get_param(NULL, "cc_ewma_cwnd_cnt", - EWMA_CWND_COUNT_DFLT, - EWMA_CWND_COUNT_MIN, - EWMA_CWND_COUNT_MAX); - -#define BWE_SENDME_MIN_MIN 2 -#define BWE_SENDME_MIN_MAX (20) - cc->bwe_sendme_min = - networkstatus_get_param(NULL, "cc_bwe_min", - BWE_SENDME_MIN_DFLT, - BWE_SENDME_MIN_MIN, - BWE_SENDME_MIN_MAX); - -#define CC_ALG_MIN 0 -#define CC_ALG_MAX (NUM_CC_ALGS-1) - cc->cc_alg = - networkstatus_get_param(NULL, "cc_alg", - cc_alg, - CC_ALG_MIN, - CC_ALG_MAX); + /* If the consensus says to use OG sendme, but torrc has + * always-enabled, use the default "always" alg (vegas), + * else use cached conensus alg. */ + if (cc_alg == CC_ALG_SENDME && opts->AlwaysCongestionControl) { + cc->cc_alg = CC_ALG_DFLT_ALWAYS; + } else { + cc->cc_alg = cc_alg; + } bdp_alg_t default_bdp_alg = 0; @@ -243,12 +292,56 @@ congestion_control_init_params(congestion_control_t *cc, if (cc->cc_alg == CC_ALG_WESTWOOD) { congestion_control_westwood_set_params(cc); } else if (cc->cc_alg == CC_ALG_VEGAS) { - congestion_control_vegas_set_params(cc); + congestion_control_vegas_set_params(cc, path); } else if (cc->cc_alg == CC_ALG_NOLA) { congestion_control_nola_set_params(cc); } } +/** Returns true if congestion control is enabled in the most recent + * consensus, or if __AlwaysCongestionControl is set to true. + * + * Note that this function (and many many other functions) should not + * be called from the CPU worker threads when handling congestion + * control negotiation. Relevant values are marshaled into the + * `circuit_params_t` struct, in order to be used in worker threads + * without touching global state. Use those values in CPU worker + * threads, instead of calling this function. + * + * The danger is still present, in your time, as it was in ours. + */ +bool +congestion_control_enabled(void) +{ + const or_options_t *opts = NULL; + + tor_assert_nonfatal_once(in_main_thread()); + + opts = get_options(); + + /* If the user has set "__AlwaysCongesttionControl", + * then always try to negotiate congestion control, regardless + * of consensus param. This is to be used for testing and sbws. + * + * Note that we do *not* allow disabling congestion control + * if the consensus says to use it, as this is bad for queueing + * and fairness. */ + if (opts->AlwaysCongestionControl) + return 1; + + return cc_alg != CC_ALG_SENDME; +} + +/** + * For unit tests only: set the cached consensus cc alg to + * specified value. + */ +void +congestion_control_set_cc_enabled(void) +{ + cc_alg = CC_ALG_VEGAS; +} + /** * Allocate and initialize fields in congestion control object. * @@ -258,27 +351,26 @@ congestion_control_init_params(congestion_control_t *cc, * acks. This parameter will come from circuit negotiation. */ static void -congestion_control_init(congestion_control_t *cc, cc_alg_t cc_alg, - int sendme_inc) +congestion_control_init(congestion_control_t *cc, + const circuit_params_t *params, + cc_path_t path) { cc->sendme_pending_timestamps = smartlist_new(); cc->sendme_arrival_timestamps = smartlist_new(); cc->in_slow_start = 1; - congestion_control_init_params(cc, cc_alg, sendme_inc); + congestion_control_init_params(cc, params, path); cc->next_cc_event = CWND_UPDATE_RATE(cc); } /** Allocate and initialize a new congestion control object */ congestion_control_t * -congestion_control_new(void) +congestion_control_new(const circuit_params_t *params, cc_path_t path) { congestion_control_t *cc = tor_malloc_zero(sizeof(congestion_control_t)); - // XXX: the alg and the sendme_inc need to be negotiated during - // circuit handshake - congestion_control_init(cc, CC_ALG_VEGAS, SENDME_INC_DFLT); + congestion_control_init(cc, params, path); return cc; } @@ -351,14 +443,19 @@ dequeue_timestamp(smartlist_t *timestamps_u64_usecs) } /** - * Returns the number of sendme acks that will be recieved in the - * current congestion window size, rounded to nearest int. + * Returns the number N of N-count EWMA, for averaging RTT and BDP over + * N SENDME acks. + * + * This N is bracketed between a divisor of the number of acks in a CWND + * and a max value. It is always at least 2. */ static inline uint64_t -sendme_acks_per_cwnd(const congestion_control_t *cc) +n_ewma_count(const congestion_control_t *cc) { - /* We add half a sendme_inc to cwnd to round to the nearest int */ - return ((cc->cwnd + cc->sendme_inc/2)/cc->sendme_inc); + uint64_t ewma_cnt = MIN(CWND_UPDATE_RATE(cc)*n_ewma_cwnd_pct/100, + n_ewma_max); + ewma_cnt = MAX(ewma_cnt, 2); + return ewma_cnt; } /** @@ -631,7 +728,7 @@ static bool time_delta_stalled_or_jumped(const congestion_control_t *cc, uint64_t old_delta, uint64_t new_delta) { -#define DELTA_DISCREPENCY_RATIO_MAX 100 +#define DELTA_DISCREPENCY_RATIO_MAX 5000 /* If we have a 0 new_delta, that is definitely a monotime stall */ if (new_delta == 0) { static ratelim_t stall_info_limit = RATELIM_INIT(60); @@ -737,8 +834,7 @@ congestion_control_update_circuit_rtt(congestion_control_t *cc, return 0; } - ewma_cnt = cc->ewma_cwnd_cnt*sendme_acks_per_cwnd(cc); - ewma_cnt = MAX(ewma_cnt, 2); // Use at least 2 + ewma_cnt = n_ewma_count(cc); cc->ewma_rtt_usec = n_count_ewma(rtt, cc->ewma_rtt_usec, ewma_cnt); @@ -854,14 +950,14 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, */ enqueue_timestamp(cc->sendme_arrival_timestamps, now_usec); - if (smartlist_len(cc->sendme_arrival_timestamps) >= cc->bwe_sendme_min) { + if (smartlist_len(cc->sendme_arrival_timestamps) >= bwe_sendme_min) { /* If we have more sendmes than fit in a cwnd, trim the list. * Those are not acurrately measuring throughput, if cwnd is * currently smaller than BDP */ while (smartlist_len(cc->sendme_arrival_timestamps) > - cc->bwe_sendme_min && + bwe_sendme_min && (uint64_t)smartlist_len(cc->sendme_arrival_timestamps) > - sendme_acks_per_cwnd(cc)) { + n_ewma_count(cc)) { (void)dequeue_timestamp(cc->sendme_arrival_timestamps); } int sendme_cnt = smartlist_len(cc->sendme_arrival_timestamps); @@ -870,21 +966,26 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, timestamp_usec = peek_timestamp(cc->sendme_arrival_timestamps); uint64_t delta = now_usec - timestamp_usec; - /* The acked data is in sendme_cnt-1 chunks, because we are counting the - * data that is processed by the other endpoint *between* all of these - * sendmes. There's one less gap between the sendmes than the number - * of sendmes. */ - uint64_t cells = (sendme_cnt-1)*cc->sendme_inc; - - /* The bandwidth estimate is cells/delta, which when multiplied - * by min RTT obtains the BDP. However, we multiply first to - * avoid precision issues with the RTT being close to delta in size. */ - sendme_rate_bdp = cells*cc->min_rtt_usec/delta; - - /* Calculate BDP_EWMA_COUNT N-EWMA */ - cc->bdp[BDP_ALG_SENDME_RATE] = - n_count_ewma(sendme_rate_bdp, cc->bdp[BDP_ALG_SENDME_RATE], - cc->ewma_cwnd_cnt*sendme_acks_per_cwnd(cc)); + /* In Shadow, the time delta between acks can be 0 if there is no + * network activity between them. Only update BDP if the delta is + * non-zero. */ + if (delta > 0) { + /* The acked data is in sendme_cnt-1 chunks, because we are counting + * the data that is processed by the other endpoint *between* all of + * these sendmes. There's one less gap between the sendmes than the + * number of sendmes. */ + uint64_t cells = (sendme_cnt-1)*cc->sendme_inc; + + /* The bandwidth estimate is cells/delta, which when multiplied + * by min RTT obtains the BDP. However, we multiply first to + * avoid precision issues with the RTT being close to delta in size. */ + sendme_rate_bdp = cells*cc->min_rtt_usec/delta; + + /* Calculate BDP_EWMA_COUNT N-EWMA */ + cc->bdp[BDP_ALG_SENDME_RATE] = + n_count_ewma(sendme_rate_bdp, cc->bdp[BDP_ALG_SENDME_RATE], + n_ewma_count(cc)); + } } /* In-flight BDP will cause the cwnd to drift down when underutilized. @@ -973,9 +1074,8 @@ congestion_control_update_circuit_bdp(congestion_control_t *cc, "%"PRIu64", " "%"PRIu64", " "%"PRIu64". ", - // XXX: actually, is this p_chan here? This is - // an or_circuit (exit or onion) - circ->n_chan->global_identifier, circ->n_circ_id, + CONST_TO_OR_CIRCUIT(circ)->p_chan->global_identifier, + CONST_TO_OR_CIRCUIT(circ)->p_circ_id, cc->min_rtt_usec/1000, curr_rtt_usec/1000, cc->ewma_rtt_usec/1000, @@ -1036,3 +1136,309 @@ congestion_control_dispatch_cc_alg(congestion_control_t *cc, return ret; } + +/** + * Build an extension field request to negotiate congestion control. + * + * If congestion control is enabled, field TRUNNEL_EXT_TYPE_CC_FIELD_REQUEST + * is created in msg_out. It is a single 0-length field that signifies that we + * want to use congestion control. The length of msg_out is provided via + * msg_len_out. + * + * If congestion control is not enabled, a payload with 0 extensions is created + * and returned. + * + * If there is a failure building the request, -1 is returned, else 0. + * + * *msg_out must be freed if the return value is 0. + */ +int +congestion_control_build_ext_request(uint8_t **msg_out, size_t *msg_len_out) +{ + uint8_t *request = NULL; + trn_extension_t *ext = NULL; + trn_extension_field_t *field = NULL; + + ext = trn_extension_new(); + + /* With congestion control enabled, add the request, else it is an empty + * request in the payload. */ + + if (congestion_control_enabled()) { + /* Build the extension field that will hold the CC field. */ + field = trn_extension_field_new(); + trn_extension_field_set_field_type(field, + TRUNNEL_EXT_TYPE_CC_FIELD_REQUEST); + + /* No payload indicating a request to use congestion control. */ + trn_extension_field_set_field_len(field, 0); + + /* Build final extension. */ + trn_extension_add_fields(ext, field); + trn_extension_set_num(ext, 1); + } + + /* Encode extension. */ + ssize_t ret = trn_extension_encoded_len(ext); + if (BUG(ret < 0)) { + goto err; + } + size_t request_len = ret; + request = tor_malloc_zero(request_len); + ret = trn_extension_encode(request, request_len, ext); + if (BUG(ret < 0)) { + tor_free(request); + goto err; + } + *msg_out = request; + *msg_len_out = request_len; + + /* Free everything, we've encoded the request now. */ + ret = 0; + + err: + trn_extension_free(ext); + return (int)ret; +} + +/** + * Parse a congestion control ntorv3 request payload for extensions. + * + * On parsing failure, -1 is returned. + * + * If congestion control request is present, return 1. If it is not present, + * return 0. + * + * WARNING: Called from CPU worker! Must not access any global state. + */ +int +congestion_control_parse_ext_request(const uint8_t *msg, const size_t msg_len) +{ + ssize_t ret = 0; + trn_extension_t *ext = NULL; + size_t num_fields = 0; + + /* Parse extension from payload. */ + ret = trn_extension_parse(&ext, msg, msg_len); + if (ret < 0) { + goto end; + } + + /* No extension implies no support for congestion control. In this case, we + * simply return 0 to indicate CC is disabled. */ + if ((num_fields = trn_extension_get_num(ext)) == 0) { + ret = 0; + goto end; + } + + /* Go over all fields. If any field is TRUNNEL_EXT_TYPE_CC_FIELD_REQUEST, + * then congestion control is enabled. Ignore unknown fields. */ + for (size_t f = 0; f < num_fields; f++) { + const trn_extension_field_t *field = trn_extension_get_fields(ext, f); + if (field == NULL) { + ret = -1; + goto end; + } + + /* For congestion control to be enabled, we only need the field type. */ + if (trn_extension_field_get_field_type(field) == + TRUNNEL_EXT_TYPE_CC_FIELD_REQUEST) { + ret = 1; + break; + } + } + + end: + trn_extension_free(ext); + return (int)ret; +} + +/** + * Given our observed parameters for circuits and congestion control, + * as well as the parameters for the resulting circuit, build a response + * payload using extension fields into *msg_out, with length specified in + * *msg_out_len. + * + * If congestion control will be enabled, the extension field for + * TRUNNEL_EXT_TYPE_CC_FIELD_RESPONSE will contain the sendme_inc value. + * + * If congestion control won't be enabled, an extension payload with 0 + * fields will be created. + * + * Return 0 if an extension payload was created in *msg_out, and -1 on + * error. + * + * *msg_out must be freed if the return value is 0. + * + * WARNING: Called from CPU worker! Must not access any global state. + */ +int +congestion_control_build_ext_response(const circuit_params_t *our_params, + const circuit_params_t *circ_params, + uint8_t **msg_out, size_t *msg_len_out) +{ + ssize_t ret; + uint8_t *request = NULL; + trn_extension_t *ext = NULL; + trn_extension_field_t *field = NULL; + trn_extension_field_cc_t *cc_field = NULL; + + tor_assert(our_params); + tor_assert(circ_params); + tor_assert(msg_out); + tor_assert(msg_len_out); + + ext = trn_extension_new(); + + if (circ_params->cc_enabled) { + /* Build the extension field that will hold the CC field. */ + field = trn_extension_field_new(); + trn_extension_field_set_field_type(field, + TRUNNEL_EXT_TYPE_CC_FIELD_RESPONSE); + + /* Build the congestion control field response. */ + cc_field = trn_extension_field_cc_new(); + trn_extension_field_cc_set_sendme_inc(cc_field, + our_params->sendme_inc_cells); + + ret = trn_extension_field_cc_encoded_len(cc_field); + if (BUG(ret <= 0)) { + trn_extension_field_free(field); + goto err; + } + size_t field_len = ret; + trn_extension_field_set_field_len(field, field_len); + trn_extension_field_setlen_field(field, field_len); + + uint8_t *field_array = trn_extension_field_getarray_field(field); + ret = trn_extension_field_cc_encode(field_array, + trn_extension_field_getlen_field(field), cc_field); + if (BUG(ret <= 0)) { + trn_extension_field_free(field); + goto err; + } + + /* Build final extension. */ + trn_extension_add_fields(ext, field); + trn_extension_set_num(ext, 1); + } + + /* Encode extension. */ + ret = trn_extension_encoded_len(ext); + if (BUG(ret < 0)) { + goto err; + } + size_t request_len = ret; + request = tor_malloc_zero(request_len); + ret = trn_extension_encode(request, request_len, ext); + if (BUG(ret < 0)) { + tor_free(request); + goto err; + } + *msg_out = request; + *msg_len_out = request_len; + + /* We've just encoded the extension, clean everything. */ + ret = 0; + + err: + trn_extension_free(ext); + trn_extension_field_cc_free(cc_field); + return (int)ret; +} + +/** Return true iff the given sendme increment is within the acceptable + * margins. */ +bool +congestion_control_validate_sendme_increment(uint8_t sendme_inc) +{ + /* We will only accept this response (and this circuit) if sendme_inc + * is within a factor of 2 of our consensus value. We should not need + * to change cc_sendme_inc much, and if we do, we can spread out those + * changes over smaller increments once every 4 hours. Exits that + * violate this range should just not be used. */ +#define MAX_SENDME_INC_NEGOTIATE_FACTOR 2 + + if (sendme_inc == 0) + return false; + + if (sendme_inc > + MAX_SENDME_INC_NEGOTIATE_FACTOR * congestion_control_sendme_inc() || + sendme_inc < + congestion_control_sendme_inc() / MAX_SENDME_INC_NEGOTIATE_FACTOR) { + return false; + } + return true; +} + +/** Return 1 if CC is enabled which also will set the SENDME increment into our + * params_out. Return 0 if CC is disabled. Else, return -1 on error. */ +int +congestion_control_parse_ext_response(const uint8_t *msg, + const size_t msg_len, + circuit_params_t *params_out) +{ + ssize_t ret = 0; + size_t num_fields = 0; + trn_extension_t *ext = NULL; + trn_extension_field_cc_t *cc_field = NULL; + + /* We will only accept this response (and this circuit) if sendme_inc + * is within a factor of 2 of our consensus value. We should not need + * to change cc_sendme_inc much, and if we do, we can spread out those + * changes over smaller increments once every 4 hours. Exits that + * violate this range should just not be used. */ +#define MAX_SENDME_INC_NEGOTIATE_FACTOR 2 + + /* Parse extension from payload. */ + ret = trn_extension_parse(&ext, msg, msg_len); + if (ret < 0) { + goto end; + } + + if ((num_fields = trn_extension_get_num(ext)) == 0) { + ret = 0; + goto end; + } + + /* Go over all fields. If any field is TRUNNEL_EXT_TYPE_CC_FIELD_RESPONSE, + * then congestion control is enabled. Ignore unknown fields. */ + for (size_t f = 0; f < num_fields; f++) { + const trn_extension_field_t *field = trn_extension_get_fields(ext, f); + if (field == NULL) { + ret = -1; + goto end; + } + + /* Only examine TRUNNEL_EXT_TYPE_CC_FIELD_RESPONSE; ignore other fields */ + if (trn_extension_field_get_field_type(field) == + TRUNNEL_EXT_TYPE_CC_FIELD_RESPONSE) { + + /* Parse the field into the congestion control field. */ + ret = trn_extension_field_cc_parse(&cc_field, + trn_extension_field_getconstarray_field(field), + trn_extension_field_getlen_field(field)); + if (ret < 0) { + goto end; + } + + uint8_t sendme_inc_cells = + trn_extension_field_cc_get_sendme_inc(cc_field); + if (!congestion_control_validate_sendme_increment(sendme_inc_cells)) { + ret = -1; + goto end; + } + + /* All good. Get value and break */ + params_out->sendme_inc_cells = sendme_inc_cells; + ret = 1; + break; + } + } + + end: + trn_extension_free(ext); + trn_extension_field_cc_free(cc_field); + + return (int)ret; +} diff --git a/src/core/or/congestion_control_common.h b/src/core/or/congestion_control_common.h index 01dbc1ceb4..1a57d71331 100644 --- a/src/core/or/congestion_control_common.h +++ b/src/core/or/congestion_control_common.h @@ -9,18 +9,41 @@ #ifndef TOR_CONGESTION_CONTROL_COMMON_H #define TOR_CONGESTION_CONTROL_COMMON_H +#include "core/crypto/onion_crypto.h" #include "core/or/crypt_path_st.h" #include "core/or/circuit_st.h" +/* The maximum whole number of cells that can fit in a + * full TLS record. This is 31. */ +#define TLS_RECORD_MAX_CELLS ((16 * 1024) / CELL_MAX_NETWORK_SIZE) + typedef struct congestion_control_t congestion_control_t; +/** + * Specifies the path type to help choose congestion control + * parameters. Since these paths are different lengths, they + * will need different queue parameters. */ +typedef enum { + CC_PATH_EXIT = 0, + CC_PATH_ONION = 1, + CC_PATH_ONION_SOS = 2, + CC_PATH_ONION_VG = 3, + CC_PATH_SBWS = 4, +} cc_path_t; + +/** The length of a path for sbws measurement */ +#define SBWS_ROUTE_LEN 2 + /** Wrapper for the free function, set the CC pointer to NULL after free */ #define congestion_control_free(cc) \ FREE_AND_NULL(congestion_control_t, congestion_control_free_, cc) void congestion_control_free_(congestion_control_t *cc); -congestion_control_t *congestion_control_new(void); +struct circuit_params_t; +congestion_control_t *congestion_control_new( + const struct circuit_params_t *params, + cc_path_t path); int congestion_control_dispatch_cc_alg(congestion_control_t *cc, const circuit_t *circ, @@ -43,12 +66,28 @@ bool is_monotime_clock_reliable(void); void congestion_control_new_consensus_params(const networkstatus_t *ns); -/* Ugh, C.. these four are private. Use the getter instead, when +bool congestion_control_enabled(void); + +int congestion_control_build_ext_request(uint8_t **msg_out, + size_t *msg_len_out); +int congestion_control_parse_ext_request(const uint8_t *msg, + const size_t msg_len); +int congestion_control_build_ext_response(const circuit_params_t *our_params, + const circuit_params_t *circ_params, + uint8_t **msg_out, + size_t *msg_len_out); +int congestion_control_parse_ext_response(const uint8_t *msg, + const size_t msg_len, + circuit_params_t *params_out); +bool congestion_control_validate_sendme_increment(uint8_t sendme_inc); + +/* Ugh, C.. these are private. Use the getter instead, when * external to the congestion control code. */ extern uint32_t or_conn_highwater; extern uint32_t or_conn_lowwater; extern int32_t cell_queue_high; extern int32_t cell_queue_low; +extern uint8_t cc_sendme_inc; /** Stop writing on an orconn when its outbuf is this large */ static inline uint32_t @@ -80,6 +119,13 @@ cell_queue_lowwatermark(void) return cell_queue_low; } +/** Returns the sendme inc rate cached from the most recent consensus */ +static inline uint8_t +congestion_control_sendme_inc(void) +{ + return cc_sendme_inc; +} + /** * Compute an N-count EWMA, aka N-EWMA. N-EWMA is defined as: * EWMA = alpha*value + (1-alpha)*EWMA_prev @@ -106,6 +152,8 @@ n_count_ewma(uint64_t curr, uint64_t prev, uint64_t N) */ #ifdef TOR_UNIT_TESTS +void congestion_control_set_cc_enabled(void); + #endif /* defined(TOR_UNIT_TESTS) */ #endif /* defined(TOR_CONGESTION_CONTROL_PRIVATE) */ diff --git a/src/core/or/congestion_control_flow.c b/src/core/or/congestion_control_flow.c index 805654664c..3a3a9522fd 100644 --- a/src/core/or/congestion_control_flow.c +++ b/src/core/or/congestion_control_flow.c @@ -62,12 +62,15 @@ static uint32_t xon_rate_bytes; static inline const congestion_control_t * edge_get_ccontrol(const edge_connection_t *edge) { - if (edge->cpath_layer) - return edge->cpath_layer->ccontrol; - else if (edge->on_circuit) - return edge->on_circuit->ccontrol; - else - return NULL; + congestion_control_t *ccontrol = NULL; + + if (edge->on_circuit && edge->on_circuit->ccontrol) { + ccontrol = edge->on_circuit->ccontrol; + } else if (edge->cpath_layer && edge->cpath_layer->ccontrol) { + ccontrol = edge->cpath_layer->ccontrol; + } + + return ccontrol; } /** @@ -113,7 +116,7 @@ flow_control_new_consensus_params(const networkstatus_t *ns) CC_XON_RATE_BYTES_MAX)*RELAY_PAYLOAD_SIZE; #define CC_XON_EWMA_CNT_DFLT (2) -#define CC_XON_EWMA_CNT_MIN (1) +#define CC_XON_EWMA_CNT_MIN (2) #define CC_XON_EWMA_CNT_MAX (100) xon_ewma_cnt = networkstatus_get_param(ns, "cc_xon_ewma_cnt", CC_XON_EWMA_CNT_DFLT, @@ -275,10 +278,6 @@ circuit_process_stream_xoff(edge_connection_t *conn, */ if (TO_CONN(conn)->type == CONN_TYPE_AP || conn->hs_ident != NULL) { uint32_t limit = 0; - - /* TODO: This limit technically needs to come from negotiation, - * and be bounds checked for sanity, because the other endpoint - * may have a different consensus */ if (conn->hs_ident) limit = xoff_client; else @@ -296,9 +295,6 @@ circuit_process_stream_xoff(edge_connection_t *conn, } } - // TODO: Count how many xoffs we have; log if "too many", for shadow - // analysis of chatter. Possibly add to extra-info? - log_info(LD_EDGE, "Got XOFF!"); connection_stop_reading(TO_CONN(conn)); conn->xoff_received = true; @@ -371,9 +367,6 @@ circuit_process_stream_xon(edge_connection_t *conn, if (TO_CONN(conn)->type == CONN_TYPE_AP || conn->hs_ident != NULL) { uint32_t limit = 0; - /* TODO: This limit technically needs to come from negotiation, - * and be bounds checked for sanity, because the other endpoint - * may have a different consensus */ if (conn->hs_ident) limit = MIN(xoff_client, xon_rate_bytes); else diff --git a/src/core/or/congestion_control_nola.c b/src/core/or/congestion_control_nola.c index 09f88d4699..52d41157a2 100644 --- a/src/core/or/congestion_control_nola.c +++ b/src/core/or/congestion_control_nola.c @@ -111,7 +111,8 @@ congestion_control_nola_process_sendme(congestion_control_t *cc, "INFL: %"PRIu64", " "NCCE: %"PRIu64", " "SS: %d", - circ->n_chan->global_identifier, circ->n_circ_id, + CONST_TO_OR_CIRCUIT(circ)->p_chan->global_identifier, + CONST_TO_OR_CIRCUIT(circ)->p_circ_id, cc->cwnd, cc->inflight, cc->next_cc_event, diff --git a/src/core/or/congestion_control_st.h b/src/core/or/congestion_control_st.h index 251ebd82e3..2c905772c1 100644 --- a/src/core/or/congestion_control_st.h +++ b/src/core/or/congestion_control_st.h @@ -103,6 +103,8 @@ struct vegas_params_t { uint16_t alpha; /** The queue use above which we decrement cwnd */ uint16_t beta; + /** The queue use at which we cap cwnd in steady state */ + uint16_t delta; /** Weighted average (percent) between cwnd estimator and * piecewise estimator. */ uint8_t bdp_mix_pct; @@ -115,7 +117,7 @@ struct nola_params_t { }; /** Fields common to all congestion control algorithms */ -typedef struct congestion_control_t { +struct congestion_control_t { /** * Smartlist of uint64_t monotime usec timestamps of when we sent a data * cell that is pending a sendme. FIFO queue that is managed similar to @@ -178,16 +180,6 @@ typedef struct congestion_control_t { uint8_t cwnd_inc_rate; /** - * Number of cwnd worth of sendme acks to smooth RTT and BDP with, - * using N_EWMA */ - uint8_t ewma_cwnd_cnt; - - /** - * Minimum number of sendmes before we begin BDP estimates - */ - uint8_t bwe_sendme_min; - - /** * Number of cells to ack with every sendme. Taken from consensus parameter * and negotiation during circuit setup. */ uint8_t sendme_inc; @@ -209,24 +201,30 @@ typedef struct congestion_control_t { struct vegas_params_t vegas_params; struct nola_params_t nola_params; }; -} congestion_control_t; +}; /** * Returns the number of sendme acks we will recieve before we update cwnd. * * Congestion control literature recommends only one update of cwnd per * cwnd worth of acks. However, we can also tune this to be more frequent - * by increasing the 'cc_cwnd_inc_rate' consensus parameter. + * by increasing the 'cc_cwnd_inc_rate' consensus parameter. This tuning + * only applies after slow start. * * If this returns 0 due to high cwnd_inc_rate, the calling code will * update every sendme ack. */ -static inline uint64_t CWND_UPDATE_RATE(const congestion_control_t *cc) +static inline uint64_t CWND_UPDATE_RATE(const struct congestion_control_t *cc) { /* We add cwnd_inc_rate*sendme_inc/2 to round to nearest integer number * of acks */ - return ((cc->cwnd + cc->cwnd_inc_rate*cc->sendme_inc/2) + + if (cc->in_slow_start) { + return ((cc->cwnd + cc->sendme_inc/2)/cc->sendme_inc); + } else { + return ((cc->cwnd + cc->cwnd_inc_rate*cc->sendme_inc/2) / (cc->cwnd_inc_rate*cc->sendme_inc)); + } } /** @@ -241,7 +239,7 @@ static inline uint64_t CWND_UPDATE_RATE(const congestion_control_t *cc) * allows us to specify the percent of the current consensus window * to update by. */ -static inline uint64_t CWND_INC_SS(const congestion_control_t *cc) +static inline uint64_t CWND_INC_SS(const struct congestion_control_t *cc) { return (cc->cwnd_inc_pct_ss*cc->cwnd/100); } diff --git a/src/core/or/congestion_control_vegas.c b/src/core/or/congestion_control_vegas.c index 3206821f4c..5c62787375 100644 --- a/src/core/or/congestion_control_vegas.c +++ b/src/core/or/congestion_control_vegas.c @@ -23,11 +23,40 @@ #include "core/or/channel.h" #include "feature/nodelist/networkstatus.h" -#define VEGAS_GAMMA(cc) (6*(cc)->sendme_inc) -#define VEGAS_ALPHA(cc) (3*(cc)->sendme_inc) -#define VEGAS_BETA(cc) (6*(cc)->sendme_inc) +#define OUTBUF_CELLS (2*TLS_RECORD_MAX_CELLS) -#define VEGAS_BDP_MIX_PCT 0 +/* sbws circs are two hops, so params are based on 2 outbufs of cells */ +#define VEGAS_ALPHA_SBWS_DFLT (2*OUTBUF_CELLS-TLS_RECORD_MAX_CELLS) +#define VEGAS_BETA_SBWS_DFLT (2*OUTBUF_CELLS) +#define VEGAS_GAMMA_SBWS_DFLT (2*OUTBUF_CELLS) +#define VEGAS_DELTA_SBWS_DFLT (4*OUTBUF_CELLS) + +/* Exits are three hops, so params are based on 3 outbufs of cells */ +#define VEGAS_ALPHA_EXIT_DFLT (3*OUTBUF_CELLS-TLS_RECORD_MAX_CELLS) +#define VEGAS_BETA_EXIT_DFLT (3*OUTBUF_CELLS) +#define VEGAS_GAMMA_EXIT_DFLT (3*OUTBUF_CELLS) +#define VEGAS_DELTA_EXIT_DFLT (5*OUTBUF_CELLS) + +/* Onion rends are six hops, so params are based on 6 outbufs of cells */ +#define VEGAS_ALPHA_ONION_DFLT (6*OUTBUF_CELLS-TLS_RECORD_MAX_CELLS) +#define VEGAS_BETA_ONION_DFLT (6*OUTBUF_CELLS) +#define VEGAS_GAMMA_ONION_DFLT (6*OUTBUF_CELLS) +#define VEGAS_DELTA_ONION_DFLT (8*OUTBUF_CELLS) + +/* Single Onions are three hops, so params are based on 3 outbufs of cells */ +#define VEGAS_ALPHA_SOS_DFLT (3*OUTBUF_CELLS-TLS_RECORD_MAX_CELLS) +#define VEGAS_BETA_SOS_DFLT (3*OUTBUF_CELLS) +#define VEGAS_GAMMA_SOS_DFLT (3*OUTBUF_CELLS) +#define VEGAS_DELTA_SOS_DFLT (5*OUTBUF_CELLS) + +/* Vanguard Onions are 7 hops (or 8 if both sides use vanguards, but that + * should be rare), so params are based on 7 outbufs of cells */ +#define VEGAS_ALPHA_VG_DFLT (7*OUTBUF_CELLS-TLS_RECORD_MAX_CELLS) +#define VEGAS_BETA_VG_DFLT (7*OUTBUF_CELLS) +#define VEGAS_GAMMA_VG_DFLT (7*OUTBUF_CELLS) +#define VEGAS_DELTA_VG_DFLT (9*OUTBUF_CELLS) + +#define VEGAS_BDP_MIX_PCT 100 /** * The original TCP Vegas used only a congestion window BDP estimator. We @@ -52,28 +81,94 @@ vegas_bdp_mix(const congestion_control_t *cc) * Cache Vegas consensus parameters. */ void -congestion_control_vegas_set_params(congestion_control_t *cc) +congestion_control_vegas_set_params(congestion_control_t *cc, + cc_path_t path) { tor_assert(cc->cc_alg == CC_ALG_VEGAS); + const char *alpha_str = NULL, *beta_str = NULL, *gamma_str = NULL; + const char *delta_str = NULL; + int alpha, beta, gamma, delta; - cc->vegas_params.gamma = - networkstatus_get_param(NULL, "cc_vegas_gamma", - VEGAS_GAMMA(cc), - 0, - 1000); + switch (path) { + case CC_PATH_SBWS: + alpha_str = "cc_vegas_alpha_sbws"; + beta_str = "cc_vegas_beta_sbws"; + gamma_str = "cc_vegas_gamma_sbws"; + delta_str = "cc_vegas_delta_sbws"; + alpha = VEGAS_ALPHA_SBWS_DFLT; + beta = VEGAS_BETA_SBWS_DFLT; + gamma = VEGAS_GAMMA_SBWS_DFLT; + delta = VEGAS_DELTA_SBWS_DFLT; + break; + case CC_PATH_EXIT: + alpha_str = "cc_vegas_alpha_exit"; + beta_str = "cc_vegas_beta_exit"; + gamma_str = "cc_vegas_gamma_exit"; + delta_str = "cc_vegas_delta_exit"; + alpha = VEGAS_ALPHA_EXIT_DFLT; + beta = VEGAS_BETA_EXIT_DFLT; + gamma = VEGAS_GAMMA_EXIT_DFLT; + delta = VEGAS_DELTA_EXIT_DFLT; + break; + case CC_PATH_ONION: + alpha_str = "cc_vegas_alpha_onion"; + beta_str = "cc_vegas_beta_onion"; + gamma_str = "cc_vegas_gamma_onion"; + delta_str = "cc_vegas_delta_onion"; + alpha = VEGAS_ALPHA_ONION_DFLT; + beta = VEGAS_BETA_ONION_DFLT; + gamma = VEGAS_GAMMA_ONION_DFLT; + delta = VEGAS_DELTA_ONION_DFLT; + break; + case CC_PATH_ONION_SOS: + alpha_str = "cc_vegas_alpha_sos"; + beta_str = "cc_vegas_beta_sos"; + gamma_str = "cc_vegas_gamma_sos"; + delta_str = "cc_vegas_delta_sos"; + alpha = VEGAS_ALPHA_SOS_DFLT; + beta = VEGAS_BETA_SOS_DFLT; + gamma = VEGAS_GAMMA_SOS_DFLT; + delta = VEGAS_DELTA_SOS_DFLT; + break; + case CC_PATH_ONION_VG: + alpha_str = "cc_vegas_alpha_vg"; + beta_str = "cc_vegas_beta_vg"; + gamma_str = "cc_vegas_gamma_vg"; + delta_str = "cc_vegas_delta_vg"; + alpha = VEGAS_ALPHA_VG_DFLT; + beta = VEGAS_BETA_VG_DFLT; + gamma = VEGAS_GAMMA_VG_DFLT; + delta = VEGAS_DELTA_VG_DFLT; + break; + default: + tor_assert(0); + break; + } cc->vegas_params.alpha = - networkstatus_get_param(NULL, "cc_vegas_alpha", - VEGAS_ALPHA(cc), + networkstatus_get_param(NULL, alpha_str, + alpha, 0, 1000); cc->vegas_params.beta = - networkstatus_get_param(NULL, "cc_vegas_beta", - VEGAS_BETA(cc), + networkstatus_get_param(NULL, beta_str, + beta, 0, 1000); + cc->vegas_params.gamma = + networkstatus_get_param(NULL, gamma_str, + gamma, + 0, + 1000); + + cc->vegas_params.delta = + networkstatus_get_param(NULL, delta_str, + delta, + 0, + INT32_MAX); + cc->vegas_params.bdp_mix_pct = networkstatus_get_param(NULL, "cc_vegas_bdp_mix", VEGAS_BDP_MIX_PCT, @@ -133,17 +228,19 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, if (cc->in_slow_start) { if (queue_use < cc->vegas_params.gamma && !cc->blocked_chan) { /* Grow to BDP immediately, then exponential growth until - * congestion signal */ - cc->cwnd = MAX(cc->cwnd + CWND_INC_SS(cc), + * congestion signal. Increment by at least 2 sendme's worth. */ + cc->cwnd = MAX(cc->cwnd + MAX(CWND_INC_SS(cc), 2*cc->sendme_inc), vegas_bdp_mix(cc)); } else { - /* Congestion signal: Fall back to Vegas equilibrium (BDP) */ - cc->cwnd = vegas_bdp_mix(cc); + /* Congestion signal: Set cwnd to gamma threshhold */ + cc->cwnd = vegas_bdp_mix(cc) + cc->vegas_params.gamma; cc->in_slow_start = 0; log_info(LD_CIRC, "CC: TOR_VEGAS exiting slow start"); } } else { - if (queue_use > cc->vegas_params.beta || cc->blocked_chan) { + if (queue_use > cc->vegas_params.delta) { + cc->cwnd = vegas_bdp_mix(cc) + cc->vegas_params.delta - CWND_INC(cc); + } else if (queue_use > cc->vegas_params.beta || cc->blocked_chan) { cc->cwnd -= CWND_INC(cc); } else if (queue_use < cc->vegas_params.alpha) { cc->cwnd += CWND_INC(cc); @@ -182,7 +279,8 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc, "QUSE: %"PRIu64", " "NCCE: %"PRIu64", " "SS: %d", - circ->n_chan->global_identifier, circ->n_circ_id, + CONST_TO_OR_CIRCUIT(circ)->p_chan->global_identifier, + CONST_TO_OR_CIRCUIT(circ)->p_circ_id, cc->cwnd, cc->inflight, vegas_bdp_mix(cc), diff --git a/src/core/or/congestion_control_vegas.h b/src/core/or/congestion_control_vegas.h index 111345081c..95fcea5722 100644 --- a/src/core/or/congestion_control_vegas.h +++ b/src/core/or/congestion_control_vegas.h @@ -16,7 +16,8 @@ int congestion_control_vegas_process_sendme(struct congestion_control_t *cc, const circuit_t *circ, const crypt_path_t *layer_hint); -void congestion_control_vegas_set_params(struct congestion_control_t *cc); +void congestion_control_vegas_set_params(struct congestion_control_t *cc, + cc_path_t path); /* Private section starts. */ #ifdef TOR_CONGESTION_CONTROL_VEGAS_PRIVATE diff --git a/src/core/or/congestion_control_westwood.c b/src/core/or/congestion_control_westwood.c index 4b24234212..357cdeb3b9 100644 --- a/src/core/or/congestion_control_westwood.c +++ b/src/core/or/congestion_control_westwood.c @@ -213,7 +213,8 @@ congestion_control_westwood_process_sendme(congestion_control_t *cc, "WRTT: %"PRIu64", " "WSIG: %"PRIu64", " "SS: %d", - circ->n_chan->global_identifier, circ->n_circ_id, + CONST_TO_OR_CIRCUIT(circ)->p_chan->global_identifier, + CONST_TO_OR_CIRCUIT(circ)->p_circ_id, cc->cwnd, cc->inflight, cc->next_cc_event, diff --git a/src/core/or/crypt_path_st.h b/src/core/or/crypt_path_st.h index ddc85eec14..fdc6b6fbb2 100644 --- a/src/core/or/crypt_path_st.h +++ b/src/core/or/crypt_path_st.h @@ -21,11 +21,14 @@ struct fast_handshake_state_t; struct ntor_handshake_state_t; struct crypto_dh_t; struct onion_handshake_state_t { + /** One of `ONION_HANDSHAKE_TYPE_*`. Determines which member of the union + * is accessible. */ uint16_t tag; union { struct fast_handshake_state_t *fast; struct crypto_dh_t *tap; struct ntor_handshake_state_t *ntor; + struct ntor3_handshake_state_t *ntor3; } u; }; diff --git a/src/core/or/extend_info_st.h b/src/core/or/extend_info_st.h index 868417f392..2ab0beb7e6 100644 --- a/src/core/or/extend_info_st.h +++ b/src/core/or/extend_info_st.h @@ -38,6 +38,10 @@ struct extend_info_t { crypto_pk_t *onion_key; /** Ntor onion key for this hop. */ curve25519_public_key_t curve25519_onion_key; + /** True if this hop is to be used as an _exit_, + * and it also supports supports NtorV3 _and_ negotiation + * of congestion control parameters */ + bool exit_supports_congestion_control; }; #endif /* !defined(EXTEND_INFO_ST_H) */ diff --git a/src/core/or/extendinfo.c b/src/core/or/extendinfo.c index 6bcef181be..ca623f09ce 100644 --- a/src/core/or/extendinfo.c +++ b/src/core/or/extendinfo.c @@ -35,7 +35,9 @@ extend_info_new(const char *nickname, const ed25519_public_key_t *ed_id, crypto_pk_t *onion_key, const curve25519_public_key_t *ntor_key, - const tor_addr_t *addr, uint16_t port) + const tor_addr_t *addr, uint16_t port, + const protover_summary_flags_t *pv, + bool for_exit_use) { extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t)); if (rsa_id_digest) @@ -56,6 +58,12 @@ extend_info_new(const char *nickname, if (addr) { extend_info_add_orport(info, addr, port); } + + if (pv && for_exit_use) { + info->exit_supports_congestion_control = + pv->supports_congestion_control; + } + return info; } @@ -89,7 +97,8 @@ extend_info_add_orport(extend_info_t *ei, * and IP version config. **/ extend_info_t * -extend_info_from_node(const node_t *node, int for_direct_connect) +extend_info_from_node(const node_t *node, int for_direct_connect, + bool for_exit) { crypto_pk_t *rsa_pubkey = NULL; extend_info_t *info = NULL; @@ -149,7 +158,9 @@ extend_info_from_node(const node_t *node, int for_direct_connect) rsa_pubkey, curve_pubkey, &ap.addr, - ap.port); + ap.port, + &node->ri->pv, + for_exit); } else if (valid_addr && node->rs && node->md) { info = extend_info_new(node->rs->nickname, node->identity, @@ -157,7 +168,9 @@ extend_info_from_node(const node_t *node, int for_direct_connect) rsa_pubkey, curve_pubkey, &ap.addr, - ap.port); + ap.port, + &node->rs->pv, + for_exit); } crypto_pk_free(rsa_pubkey); @@ -210,6 +223,15 @@ extend_info_supports_ntor(const extend_info_t* ei) CURVE25519_PUBKEY_LEN); } +/** Return true if we can use the Ntor v3 handshake with `ei` */ +int +extend_info_supports_ntor_v3(const extend_info_t *ei) +{ + tor_assert(ei); + return extend_info_supports_ntor(ei) && + ei->exit_supports_congestion_control; +} + /* Does ei have an onion key which it would prefer to use? * Currently, we prefer ntor keys*/ int diff --git a/src/core/or/extendinfo.h b/src/core/or/extendinfo.h index 9c07205709..6d1f20597b 100644 --- a/src/core/or/extendinfo.h +++ b/src/core/or/extendinfo.h @@ -17,8 +17,11 @@ extend_info_t *extend_info_new(const char *nickname, const struct ed25519_public_key_t *ed_id, crypto_pk_t *onion_key, const struct curve25519_public_key_t *ntor_key, - const tor_addr_t *addr, uint16_t port); -extend_info_t *extend_info_from_node(const node_t *r, int for_direct_connect); + const tor_addr_t *addr, uint16_t port, + const struct protover_summary_flags_t *pv, + bool for_exit_use); +extend_info_t *extend_info_from_node(const node_t *r, int for_direct_connect, + bool for_exit); extend_info_t *extend_info_dup(extend_info_t *info); void extend_info_free_(extend_info_t *info); #define extend_info_free(info) \ @@ -26,6 +29,7 @@ void extend_info_free_(extend_info_t *info); int extend_info_addr_is_allowed(const tor_addr_t *addr); int extend_info_supports_tap(const extend_info_t* ei); int extend_info_supports_ntor(const extend_info_t* ei); +int extend_info_supports_ntor_v3(const extend_info_t *ei); int extend_info_has_preferred_onion_key(const extend_info_t* ei); bool extend_info_has_orport(const extend_info_t *ei, const tor_addr_t *addr, uint16_t port); diff --git a/src/core/or/onion.c b/src/core/or/onion.c index 62ad7af3fe..0bdd2a6d35 100644 --- a/src/core/or/onion.c +++ b/src/core/or/onion.c @@ -88,6 +88,10 @@ check_create_cell(const create_cell_t *cell, int unknown_ok) if (cell->handshake_len != NTOR_ONIONSKIN_LEN) return -1; break; + case ONION_HANDSHAKE_TYPE_NTOR_V3: + /* ntor v3 has variable length fields that are checked + * elsewhere. Fall through to always valid here. */ + break; default: if (! unknown_ok) return -1; @@ -521,6 +525,11 @@ create_cell_format_impl(cell_t *cell_out, const create_cell_t *cell_in, switch (cell_in->cell_type) { case CELL_CREATE: + if (BUG(cell_in->handshake_type == ONION_HANDSHAKE_TYPE_NTOR_V3)) { + log_warn(LD_BUG, "Create cells cannot contain ntorv3."); + return -1; + } + if (cell_in->handshake_type == ONION_HANDSHAKE_TYPE_NTOR) { memcpy(p, NTOR_CREATE_MAGIC, 16); p += 16; @@ -619,6 +628,11 @@ extend_cell_format(uint8_t *command_out, uint16_t *len_out, switch (cell_in->cell_type) { case RELAY_COMMAND_EXTEND: { + if (BUG(cell_in->create_cell.handshake_type == + ONION_HANDSHAKE_TYPE_NTOR_V3)) { + log_warn(LD_BUG, "Extend cells cannot contain ntorv3!"); + return -1; + } *command_out = RELAY_COMMAND_EXTEND; *len_out = 6 + TAP_ONIONSKIN_CHALLENGE_LEN + DIGEST_LEN; set_uint32(p, tor_addr_to_ipv4n(&cell_in->orport_ipv4.addr)); diff --git a/src/core/or/or.h b/src/core/or/or.h index 392a848ee7..dc8f516f0a 100644 --- a/src/core/or/or.h +++ b/src/core/or/or.h @@ -732,6 +732,9 @@ typedef struct protover_summary_flags_t { * negotiate hs circuit setup padding. Requires Padding=2. */ unsigned int supports_hs_setup_padding : 1; + /** True iff this router supports congestion control. + * Requires both FlowCtrl=2 *and* Relay=4 */ + unsigned int supports_congestion_control : 1; } protover_summary_flags_t; typedef struct routerinfo_t routerinfo_t; @@ -790,7 +793,8 @@ typedef enum { #define ONION_HANDSHAKE_TYPE_TAP 0x0000 #define ONION_HANDSHAKE_TYPE_FAST 0x0001 #define ONION_HANDSHAKE_TYPE_NTOR 0x0002 -#define MAX_ONION_HANDSHAKE_TYPE 0x0002 +#define ONION_HANDSHAKE_TYPE_NTOR_V3 0x0003 +#define MAX_ONION_HANDSHAKE_TYPE 0x0003 typedef struct onion_handshake_state_t onion_handshake_state_t; typedef struct relay_crypto_t relay_crypto_t; diff --git a/src/core/or/origin_circuit_st.h b/src/core/or/origin_circuit_st.h index 9264077c50..6c86a56000 100644 --- a/src/core/or/origin_circuit_st.h +++ b/src/core/or/origin_circuit_st.h @@ -180,6 +180,12 @@ struct origin_circuit_t { unsigned first_hop_from_controller : 1; /** + * If true, this circuit's path has been chosen, in full or in part, + * by the controller API, and it's okay to ignore checks that we'd + * usually do on the path as whole. */ + unsigned int any_hop_from_controller : 1; + + /** * Tristate variable to guard against pathbias miscounting * due to circuit purpose transitions changing the decision * of pathbias_should_count(). This variable is informational diff --git a/src/core/or/protover.c b/src/core/or/protover.c index 28680f70d3..4cd6510da7 100644 --- a/src/core/or/protover.c +++ b/src/core/or/protover.c @@ -382,8 +382,53 @@ protocol_list_supports_protocol_or_later(const char *list, return contains; } +/* + * XXX START OF HAZARDOUS ZONE XXX + */ +/* All protocol version that this relay version supports. */ +#define PR_CONS_V "1-2" +#define PR_DESC_V "1-2" +#define PR_DIRCACHE_V "2" +#define PR_FLOWCTRL_V "1-2" +#define PR_HSDIR_V "2" +#define PR_HSINTRO_V "4-5" +#define PR_HSREND_V "1-2" +#define PR_LINK_V "1-5" +#ifdef HAVE_WORKING_TOR_TLS_GET_TLSSECRETS +#define PR_LINKAUTH_V "1,3" +#else +#define PR_LINKAUTH_V "3" +#endif +#define PR_MICRODESC_V "1-2" +#define PR_PADDING_V "2" +#define PR_RELAY_V "1-4" + +/** Return the string containing the supported version for the given protocol + * type. */ +const char * +protover_get_supported(const protocol_type_t type) +{ + switch (type) { + case PRT_CONS: return PR_CONS_V; + case PRT_DESC: return PR_DESC_V; + case PRT_DIRCACHE: return PR_DIRCACHE_V; + case PRT_FLOWCTRL: return PR_FLOWCTRL_V; + case PRT_HSDIR: return PR_HSDIR_V; + case PRT_HSINTRO: return PR_HSINTRO_V; + case PRT_HSREND: return PR_HSREND_V; + case PRT_LINK: return PR_LINK_V; + case PRT_LINKAUTH: return PR_LINKAUTH_V; + case PRT_MICRODESC: return PR_MICRODESC_V; + case PRT_PADDING: return PR_PADDING_V; + case PRT_RELAY: return PR_RELAY_V; + default: + tor_assert_unreached(); + } +} + /** Return the canonical string containing the list of protocols - * that we support. */ + * that we support. + **/ /// C_RUST_COUPLED: src/rust/protover/protover.rs `SUPPORTED_PROTOCOLS` const char * protover_get_supported_protocols(void) @@ -393,25 +438,119 @@ protover_get_supported_protocols(void) * Remember to edit the SUPPORTED_PROTOCOLS list in protover.rs if you * are editing this list. */ + + /* + * XXX: WARNING! + * + * Be EXTREMELY CAREFUL when *removing* versions from this list. If you + * remove an entry while it still appears as "recommended" in the consensus, + * you'll cause all the instances without it to warn. + * + * If you remove an entry while it still appears as "required" in the + * consensus, you'll cause all the instances without it to refuse to connect + * to the network, and shut down. + * + * If you need to remove a version from this list, you need to make sure that + * it is not listed in the _current consensuses_: just removing it from the + * required list below is NOT ENOUGH. You need to remove it from the + * required list, and THEN let the authorities upgrade and vote on new + * consensuses without it. Only once those consensuses are out is it safe to + * remove from this list. + * + * One concrete example of a very dangerous race that could occur: + * + * Suppose that the client supports protocols "HsDir=1-2" and the consensus + * requires protocols "HsDir=1-2. If the client supported protocol list is + * then changed to "HSDir=2", while the consensus stills lists "HSDir=1-2", + * then these clients, even very recent ones, will shut down because they + * don't support "HSDir=1". + * + * And so, changes need to be done in strict sequence as described above. + * + * XXX: WARNING! + */ + return - "Cons=1-2 " - "Desc=1-2 " - "DirCache=2 " - "FlowCtrl=1 " - "HSDir=1-2 " - "HSIntro=3-5 " - "HSRend=1-2 " - "Link=1-5 " -#ifdef HAVE_WORKING_TOR_TLS_GET_TLSSECRETS - "LinkAuth=1,3 " -#else - "LinkAuth=3 " -#endif - "Microdesc=1-2 " - "Padding=2 " - "Relay=1-3"; + "Cons=" PR_CONS_V " " + "Desc=" PR_DESC_V " " + "DirCache=" PR_DIRCACHE_V " " + "FlowCtrl=" PR_FLOWCTRL_V " " + "HSDir=" PR_HSDIR_V " " + "HSIntro=" PR_HSINTRO_V " " + "HSRend=" PR_HSREND_V " " + "Link=" PR_LINK_V " " + "LinkAuth=" PR_LINKAUTH_V " " + "Microdesc=" PR_MICRODESC_V " " + "Padding=" PR_PADDING_V " " + "Relay=" PR_RELAY_V; } +/* + * XXX: WARNING! + * + * The recommended and required values are hardwired, to avoid disaster. Voting + * on the wrong subprotocols here has the potential to take down the network. + * + * In particular, you need to be EXTREMELY CAREFUL before adding new versions + * to the required protocol list. Doing so will cause every relay or client + * that doesn't support those versions to refuse to connect to the network and + * shut down. + * + * Note that this applies to versions, not just protocols! If you say that + * Foobar=8-9 is required, and the client only has Foobar=9, it will shut down. + * + * It is okay to do this only for SUPER OLD relays that are not supported on + * the network anyway. For clients, we really shouldn't kick them off the + * network unless their presence is causing serious active harm. + * + * The following required and recommended lists MUST be changed BEFORE the + * supported list above is changed, so that these lists appear in the + * consensus BEFORE clients need them. + * + * Please, see the warning in protocol_get_supported_versions(). + * + * XXX: WARNING! + */ + +/** Return the recommended client protocols list that directory authorities + * put in the consensus. */ +const char * +protover_get_recommended_client_protocols(void) +{ + return "Cons=2 Desc=2 DirCache=2 HSDir=2 HSIntro=4 HSRend=2 " + "Link=4-5 Microdesc=2 Relay=2"; +} + +/** Return the recommended relay protocols list that directory authorities + * put in the consensus. */ +const char * +protover_get_recommended_relay_protocols(void) +{ + return "Cons=2 Desc=2 DirCache=2 HSDir=2 HSIntro=4 HSRend=2 " + "Link=4-5 LinkAuth=3 Microdesc=2 Relay=2"; +} + +/** Return the required client protocols list that directory authorities + * put in the consensus. */ +const char * +protover_get_required_client_protocols(void) +{ + return "Cons=2 Desc=2 Link=4 Microdesc=2 Relay=2"; +} + +/** Return the required relay protocols list that directory authorities + * put in the consensus. */ +const char * +protover_get_required_relay_protocols(void) +{ + return "Cons=2 Desc=2 DirCache=2 HSDir=2 HSIntro=4 HSRend=2 " + "Link=4-5 LinkAuth=3 Microdesc=2 Relay=2"; +} + +/* + * XXX END OF HAZARDOUS ZONE XXX + */ + /** The protocols from protover_get_supported_protocols(), as parsed into a * list of proto_entry_t values. Access this via * get_supported_protocol_list. */ diff --git a/src/core/or/protover.h b/src/core/or/protover.h index 3a7545e45d..8f15c02fb2 100644 --- a/src/core/or/protover.h +++ b/src/core/or/protover.h @@ -35,6 +35,8 @@ struct smartlist_t; /** The protover version number where relays can consider IPv6 connections * canonical */ #define PROTOVER_RELAY_CANONICAL_IPV6 3 +/** The protover version number where relays can accept ntorv3 */ +#define PROTOVER_RELAY_NTOR_V3 4 /** The protover version number that signifies HSv3 intro point support */ #define PROTOVER_HS_INTRO_V3 4 @@ -51,6 +53,9 @@ struct smartlist_t; /** The protover that signals support for HS circuit setup padding machines */ #define PROTOVER_HS_SETUP_PADDING 2 +/** The protover that signals support for congestion control */ +#define PROTOVER_FLOWCTRL_CC 2 + /** List of recognized subprotocols. */ /// C_RUST_COUPLED: src/rust/protover/ffi.rs `translate_to_rust` /// C_RUST_COUPLED: src/rust/protover/protover.rs `Proto` @@ -70,9 +75,14 @@ typedef enum protocol_type_t { } protocol_type_t; bool protover_list_is_invalid(const char *s); +const char *protover_get_supported(const protocol_type_t type); int protover_all_supported(const char *s, char **missing); int protover_is_supported_here(protocol_type_t pr, uint32_t ver); const char *protover_get_supported_protocols(void); +const char *protover_get_recommended_client_protocols(void); +const char *protover_get_recommended_relay_protocols(void); +const char *protover_get_required_client_protocols(void); +const char *protover_get_required_relay_protocols(void); char *protover_compute_vote(const struct smartlist_t *list_of_proto_strings, int threshold); diff --git a/src/core/or/scheduler_kist.c b/src/core/or/scheduler_kist.c index eba55f6497..52bc62f1b4 100644 --- a/src/core/or/scheduler_kist.c +++ b/src/core/or/scheduler_kist.c @@ -465,9 +465,17 @@ MOCK_IMPL(int, channel_should_write_to_kernel, MOCK_IMPL(void, channel_write_to_kernel, (channel_t *chan)) { tor_assert(chan); + + /* This is possible because a channel might have an outbuf table entry even + * though it has no more cells in its outbuf. Just move on. */ + size_t outbuf_len = channel_outbuf_length(chan); + if (outbuf_len == 0) { + return; + } + log_debug(LD_SCHED, "Writing %lu bytes to kernel for chan %" PRIu64, - (unsigned long)channel_outbuf_length(chan), - chan->global_identifier); + (unsigned long) outbuf_len, chan->global_identifier); + /* Note that 'connection_handle_write()' may change the scheduler state of * the channel during the scheduling loop with * 'connection_or_flushed_some()' -> 'scheduler_channel_wants_writes()'. diff --git a/src/core/or/sendme.c b/src/core/or/sendme.c index ee670f9d51..494910049e 100644 --- a/src/core/or/sendme.c +++ b/src/core/or/sendme.c @@ -338,8 +338,8 @@ record_cell_digest_on_circ(circuit_t *circ, const uint8_t *sendme_digest) * low in the stack when decrypting or encrypting a cell. The window is only * updated once the cell is actually put in the outbuf. */ -static bool -circuit_sendme_cell_is_next(int window, int sendme_inc) +STATIC bool +circuit_sendme_cell_is_next(int deliver_window, int sendme_inc) { /* Are we at the limit of the increment and if not, we don't expect next * cell is a SENDME. @@ -348,8 +348,13 @@ circuit_sendme_cell_is_next(int window, int sendme_inc) * next cell is a SENDME, the window (either package or deliver) hasn't been * decremented just yet so when this is called, we are currently processing * the "window - 1" cell. + * + * Because deliver_window starts at CIRCWINDOW_START and counts down, + * to get the actual number of received cells for this check, we must + * first convert to receieved cells, or the modulus operator will fail. */ - if (((window - 1) % sendme_inc) != 0) { + tor_assert(deliver_window <= CIRCWINDOW_START); + if (((CIRCWINDOW_START - (deliver_window - 1)) % sendme_inc) != 0) { return false; } diff --git a/src/core/or/sendme.h b/src/core/or/sendme.h index 2abec91a91..bc1daef23d 100644 --- a/src/core/or/sendme.h +++ b/src/core/or/sendme.h @@ -73,6 +73,8 @@ STATIC ssize_t build_cell_payload_v1(const uint8_t *cell_digest, STATIC bool sendme_is_valid(const circuit_t *circ, const uint8_t *cell_payload, size_t cell_payload_len); +STATIC bool circuit_sendme_cell_is_next(int deliver_window, + int sendme_inc); #endif /* defined(TOR_UNIT_TESTS) */ diff --git a/src/core/or/trace_probes_cc.c b/src/core/or/trace_probes_cc.c index d52646da4f..b0ca23e208 100644 --- a/src/core/or/trace_probes_cc.c +++ b/src/core/or/trace_probes_cc.c @@ -19,6 +19,7 @@ #include "core/or/channel.h" #include "core/or/circuit_st.h" #include "core/or/circuitlist.h" +#include "core/or/congestion_control_common.h" #include "core/or/congestion_control_st.h" #include "core/or/connection_st.h" #include "core/or/edge_connection_st.h" diff --git a/src/core/or/versions.c b/src/core/or/versions.c index b9fad22c04..9913b3ee31 100644 --- a/src/core/or/versions.c +++ b/src/core/or/versions.c @@ -482,6 +482,12 @@ memoize_protover_summary(protover_summary_flags_t *out, protocol_list_supports_protocol(protocols, PRT_PADDING, PROTOVER_HS_SETUP_PADDING); + out->supports_congestion_control = + protocol_list_supports_protocol(protocols, PRT_FLOWCTRL, + PROTOVER_FLOWCTRL_CC) && + protocol_list_supports_protocol(protocols, PRT_RELAY, + PROTOVER_RELAY_NTOR_V3); + protover_summary_flags_t *new_cached = tor_memdup(out, sizeof(*out)); cached = strmap_set(protover_summary_map, protocols, new_cached); tor_assert(!cached); |