commit 0d75344b0e0eafc89db89a974e87b16564cd8f0a Author: Nick Mathewson nickm@torproject.org Date: Fri Apr 18 12:50:04 2014 -0400
Switch to random allocation on circuitIDs.
Fixes a possible root cause of 11553 by only making 64 attempts at most to pick a circuitID. Previously, we would test every possible circuit ID until we found one or ran out.
This algorithm succeeds probabilistically. As the comment says:
This potentially causes us to give up early if our circuit ID space is nearly full. If we have N circuit IDs in use, then we will reject a new circuit with probability (N / max_range) ^ MAX_CIRCID_ATTEMPTS. This means that in practice, a few percent of our circuit ID capacity will go unused.
The alternative here, though, is to do a linear search over the whole circuit ID space every time we extend a circuit, which is not so great either.
This makes new vs old clients distinguishable, so we should try to batch it with other patches that do that, like 11438. --- changes/bug11553 | 10 ++++++++++ src/or/channel.c | 3 --- src/or/channel.h | 5 ----- src/or/circuitbuild.c | 43 ++++++++++++++++++++++++++++--------------- src/or/connection.c | 2 -- 5 files changed, 38 insertions(+), 25 deletions(-)
diff --git a/changes/bug11553 b/changes/bug11553 index 1540f46..ed30ce9 100644 --- a/changes/bug11553 +++ b/changes/bug11553 @@ -3,3 +3,13 @@ warning for the whole channel, and include a description of how many circuits there were on the channel. Fix for part of ticket #11553. + + + o Major features (performance): + - Avoid wasting cycles looking for usable circuit IDs. Previously, + when allocating a new circuit ID, we would in the worst case do a + linear scan over the entire possible range of circuit IDs before + deciding that we had exhausted our possibilities. Now, we + try 64 circuit IDs at random before deciding that we probably + won't succeed. Fix for a possible root cause of ticket + #11553. diff --git a/src/or/channel.c b/src/or/channel.c index 1270eac..dfef703 100644 --- a/src/or/channel.c +++ b/src/or/channel.c @@ -731,9 +731,6 @@ channel_init(channel_t *chan) /* Init timestamp */ chan->timestamp_last_added_nonpadding = time(NULL);
- /* Init next_circ_id */ - chan->next_circ_id = crypto_rand_int(1 << 15); - /* Initialize queues. */ TOR_SIMPLEQ_INIT(&chan->incoming_queue); TOR_SIMPLEQ_INIT(&chan->outgoing_queue); diff --git a/src/or/channel.h b/src/or/channel.h index 29ba40e..e63c949 100644 --- a/src/or/channel.h +++ b/src/or/channel.h @@ -150,11 +150,6 @@ struct channel_s { unsigned wide_circ_ids:1; /** Have we logged a warning about circID exhaustion on this channel? */ unsigned warned_circ_ids_exhausted:1; - /* - * Which circ_id do we try to use next on this connection? This is - * always in the range 0..1<<15-1. - */ - circid_t next_circ_id;
/* For how many circuits are we n_chan? What about p_chan? */ unsigned int num_n_circuits, num_p_circuits; diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 2b4d3c3..1b3c599 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -92,18 +92,21 @@ channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port, return chan; }
-/** Iterate over values of circ_id, starting from conn->next_circ_id, - * and with the high bit specified by conn->circ_id_type, until we get - * a circ_id that is not in use by any other circuit on that conn. + +/** Search for a value for circ_id that we can use on <b>chan</b> for an + * outbound circuit, until we get a circ_id that is not in use by any other + * circuit on that conn. * * Return it, or 0 if can't get a unique circ_id. */ static circid_t get_unique_circ_id_by_chan(channel_t *chan) { +#define MAX_CIRCID_ATTEMPTS 64 + circid_t test_circ_id; circid_t attempts=0; - circid_t high_bit, max_range; + circid_t high_bit, max_range, mask;
tor_assert(chan);
@@ -113,19 +116,26 @@ get_unique_circ_id_by_chan(channel_t *chan) "a client with no identity."); return 0; } - max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15); + max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15); + mask = max_range - 1; high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0; do { - /* Sequentially iterate over test_circ_id=1...max_range until we find a - * circID such that (high_bit|test_circ_id) is not already used. */ - test_circ_id = chan->next_circ_id++; - if (test_circ_id == 0 || test_circ_id >= max_range) { - test_circ_id = 1; - chan->next_circ_id = 2; - } - if (++attempts > max_range) { - /* Make sure we don't loop forever if all circ_id's are used. This - * matters because it's an external DoS opportunity. + if (++attempts > MAX_CIRCID_ATTEMPTS) { + /* Make sure we don't loop forever because all circuit IDs are used. + * + * Once, we would try until we had tried every possible circuit ID. But + * that's quite expensive. Instead, we try MAX_CIRCID_ATTEMPTS random + * circuit IDs, and then give up. + * + * This potentially causes us to give up early if our circuit ID space + * is nearly full. If we have N circuit IDs in use, then we will reject + * a new circuit with probability (N / max_range) ^ MAX_CIRCID_ATTEMPTS. + * This means that in practice, a few percent of our circuit ID capacity + * will go unused. + * + * The alternative here, though, is to do a linear search over the + * whole circuit ID space every time we extend a circuit, which is + * not so great either. */ if (! chan->warned_circ_ids_exhausted) { chan->warned_circ_ids_exhausted = 1; @@ -137,6 +147,9 @@ get_unique_circ_id_by_chan(channel_t *chan) } return 0; } + + crypto_rand((char*) &test_circ_id, sizeof(test_circ_id)); + test_circ_id &= mask; test_circ_id |= high_bit; } while (circuit_id_in_use_on_channel(test_circ_id, chan)); return test_circ_id; diff --git a/src/or/connection.c b/src/or/connection.c index 4f74a1d..96e6a47 100644 --- a/src/or/connection.c +++ b/src/or/connection.c @@ -251,8 +251,6 @@ dir_connection_new(int socket_family) * * Set timestamp_last_added_nonpadding to now. * - * Assign a pseudorandom next_circ_id between 0 and 2**15. - * * Initialize active_circuit_pqueue. * * Set active_circuit_pqueue_last_recalibrated to current cell_ewma tick.