aboutsummaryrefslogtreecommitdiff
path: root/src/or
diff options
context:
space:
mode:
authorNick Mathewson <nickm@torproject.org>2014-04-18 13:00:45 -0400
committerNick Mathewson <nickm@torproject.org>2014-04-18 13:00:45 -0400
commitbd169aa9a512857fe95fa0cbe44e4e6dbc2c800f (patch)
tree3b864e4cd291c2bd240dd7fbbf0d7e200f40dd92 /src/or
parenteb896d5e6f09902a760af010326b79ce82492da1 (diff)
parent0d75344b0e0eafc89db89a974e87b16564cd8f0a (diff)
downloadtor-bd169aa9a512857fe95fa0cbe44e4e6dbc2c800f.tar
tor-bd169aa9a512857fe95fa0cbe44e4e6dbc2c800f.tar.gz
Merge remote-tracking branch 'public/bug11553_024' into bug11553_025
Conflicts: src/or/channel.h
Diffstat (limited to 'src/or')
-rw-r--r--src/or/channel.c3
-rw-r--r--src/or/channel.h7
-rw-r--r--src/or/circuitbuild.c52
-rw-r--r--src/or/connection.c2
4 files changed, 38 insertions, 26 deletions
diff --git a/src/or/channel.c b/src/or/channel.c
index 32e87c342..286154cb2 100644
--- a/src/or/channel.c
+++ b/src/or/channel.c
@@ -728,9 +728,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 7ec222df0..de19fad9a 100644
--- a/src/or/channel.h
+++ b/src/or/channel.h
@@ -149,11 +149,8 @@ struct channel_s {
circ_id_type_bitfield_t circ_id_type:2;
/** DOCDOC*/
unsigned wide_circ_ids: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;
+ /** Have we logged a warning about circID exhaustion on this channel? */
+ unsigned warned_circ_ids_exhausted:1;
/** 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 98fef4c14..e1d57ad6e 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -77,18 +77,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);
@@ -98,23 +101,40 @@ 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.
*/
- log_warn(LD_CIRC,"No unused circ IDs. Failing.");
+ if (! chan->warned_circ_ids_exhausted) {
+ chan->warned_circ_ids_exhausted = 1;
+ log_warn(LD_CIRC,"No unused circIDs found on channel %s wide "
+ "circID support, with %u inbound and %u outbound circuits. "
+ "Failing a circuit.",
+ chan->wide_circ_ids ? "with" : "without",
+ chan->num_p_circuits, chan->num_n_circuits);
+ }
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 2e72e6b39..9614fa52d 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -271,8 +271,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.