September 2013 - tor-commits - lists.torproject.org

[tor/master] Merge branch 'maint-0.2.4'
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit 6156887adfa724805f90b3b7cf2be6213f08a450 Merge: d5e9573 c6f1668 Author: Roger Dingledine <arma(a)torproject.org> Date: Wed Sep 4 23:44:39 2013 -0400 Merge branch 'maint-0.2.4' Conflicts: src/test/test.c changes/feature9574 | 7 ++ src/or/onion.c | 231 +++++++++++++++++++++++++++++++++++++++++---------- src/or/onion.h | 4 + src/test/test.c | 47 +++++++++++ 4 files changed, 244 insertions(+), 45 deletions(-) diff --cc src/test/test.c index f895563,4ec8792..21d0356 --- a/src/test/test.c +++ b/src/test/test.c @@@ -1539,8 -2047,10 +1585,9 @@@ const struct testcase_setup_t legacy_se { #name, legacy_test_helper, TT_FORK, &legacy_setup, test_ ## name } static struct testcase_t test_array[] = { - ENT(buffers), - { "buffer_copy", test_buffer_copy, 0, NULL, NULL }, ENT(onion_handshake), + { "bad_onion_handshake", test_bad_onion_handshake, 0, NULL, NULL }, + ENT(onion_queues), #ifdef CURVE25519_ENABLED { "ntor_handshake", test_ntor_handshake, 0, NULL, NULL }, #endif

1 0

[tor/master] Separate cpuworker queues by handshake type
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit 87a18514efc7af2ee70d3f180aede5a8da95457c Author: Roger Dingledine <arma(a)torproject.org> Date: Sat Aug 31 23:35:58 2013 -0400 Separate cpuworker queues by handshake type Now we prioritize ntor create cells over tap create cells. Starts to address ticket 9574. --- src/or/onion.c | 53 +++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 37 insertions(+), 16 deletions(-) diff --git a/src/or/onion.c b/src/or/onion.c index d4a6502..60dfdde 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -28,6 +28,7 @@ typedef struct onion_queue_t { TOR_TAILQ_ENTRY(onion_queue_t) next; or_circuit_t *circ; + uint16_t handshake_type; create_cell_t *onionskin; time_t when_added; } onion_queue_t; @@ -35,11 +36,16 @@ typedef struct onion_queue_t { /** 5 seconds on the onion queue til we just send back a destroy */ #define ONIONQUEUE_WAIT_CUTOFF 5 -/** Queue of circuits waiting for CPU workers, or NULL if the list is empty.*/ -TOR_TAILQ_HEAD(onion_queue_head_t, onion_queue_t) ol_list = - TOR_TAILQ_HEAD_INITIALIZER(ol_list); +/** Array of queues of circuits waiting for CPU workers. An element is NULL + * if that queue is empty.*/ +TOR_TAILQ_HEAD(onion_queue_head_t, onion_queue_t) + ol_list[MAX_ONION_HANDSHAKE_TYPE+1] = { + TOR_TAILQ_HEAD_INITIALIZER(ol_list[0]), /* tap */ + TOR_TAILQ_HEAD_INITIALIZER(ol_list[1]), /* fast */ + TOR_TAILQ_HEAD_INITIALIZER(ol_list[2]), /* ntor */ +}; -/** Number of entries of each type currently in ol_list. */ +/** Number of entries of each type currently in each element of ol_list[]. */ static int ol_entries[MAX_ONION_HANDSHAKE_TYPE+1]; static void onion_queue_entry_remove(onion_queue_t *victim); @@ -60,8 +66,7 @@ have_room_for_onionskin(uint16_t type) int num_cpus; uint64_t tap_usec, ntor_usec; /* If we've got fewer than 50 entries, we always have room for one more. */ - if (ol_entries[ONION_HANDSHAKE_TYPE_TAP] + - ol_entries[ONION_HANDSHAKE_TYPE_NTOR] < 50) + if (ol_entries[type] < 50) return 1; num_cpus = get_num_cpus(options); /* Compute how many microseconds we'd expect to need to clear all @@ -72,10 +77,17 @@ have_room_for_onionskin(uint16_t type) ntor_usec = estimated_usec_for_onionskins( ol_entries[ONION_HANDSHAKE_TYPE_NTOR], ONION_HANDSHAKE_TYPE_NTOR) / num_cpus; + /* See whether that exceeds MaxOnionQueueDelay. If so, we can't queue * this. */ - if ((tap_usec + ntor_usec) / 1000 > (uint64_t)options->MaxOnionQueueDelay) + if (type == ONION_HANDSHAKE_TYPE_NTOR && + ntor_usec / 1000 > (uint64_t)options->MaxOnionQueueDelay) return 0; + + if (type == ONION_HANDSHAKE_TYPE_TAP && + (tap_usec + ntor_usec) / 1000 > (uint64_t)options->MaxOnionQueueDelay) + return 0; + #ifdef CURVE25519_ENABLED /* If we support the ntor handshake, then don't let TAP handshakes use * more than 2/3 of the space on the queue. */ @@ -100,6 +112,7 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) tmp = tor_malloc_zero(sizeof(onion_queue_t)); tmp->circ = circ; + tmp->handshake_type = onionskin->handshake_type; tmp->onionskin = onionskin; tmp->when_added = now; @@ -108,7 +121,8 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) static ratelim_t last_warned = RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL); char *m; - if ((m = rate_limit_log(&last_warned, approx_time()))) { + if (onionskin->handshake_type == ONION_HANDSHAKE_TYPE_NTOR && + (m = rate_limit_log(&last_warned, approx_time()))) { log_warn(LD_GENERAL, "Your computer is too slow to handle this many circuit " "creation requests! Please consider using the " @@ -122,11 +136,11 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) ++ol_entries[onionskin->handshake_type]; circ->onionqueue_entry = tmp; - TOR_TAILQ_INSERT_TAIL(&ol_list, tmp, next); + TOR_TAILQ_INSERT_TAIL(&ol_list[onionskin->handshake_type], tmp, next); /* cull elderly requests. */ while (1) { - onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list); + onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[onionskin->handshake_type]); if (now - head->when_added < (time_t)ONIONQUEUE_WAIT_CUTOFF) break; @@ -140,14 +154,18 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) return 0; } -/** Remove the first item from ol_list and return it, or return - * NULL if the list is empty. +/** Remove the highest priority item from ol_list[] and return it, or + * return NULL if the lists are empty. */ or_circuit_t * onion_next_task(create_cell_t **onionskin_out) { or_circuit_t *circ; - onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list); + + /* skip ol_list[ONION_HANDSHAKE_TYPE_FAST] since we know it'll be empty */ + onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[ONION_HANDSHAKE_TYPE_NTOR]); + if (!head) + head = TOR_TAILQ_FIRST(&ol_list[ONION_HANDSHAKE_TYPE_TAP]); if (!head) return NULL; /* no onions pending, we're done */ @@ -186,7 +204,7 @@ onion_pending_remove(or_circuit_t *circ) static void onion_queue_entry_remove(onion_queue_t *victim) { - TOR_TAILQ_REMOVE(&ol_list, victim, next); + TOR_TAILQ_REMOVE(&ol_list[victim->handshake_type], victim, next); if (victim->circ) victim->circ->onionqueue_entry = NULL; @@ -204,8 +222,11 @@ void clear_pending_onions(void) { onion_queue_t *victim; - while ((victim = TOR_TAILQ_FIRST(&ol_list))) { - onion_queue_entry_remove(victim); + int i; + for (i=0; i<=MAX_ONION_HANDSHAKE_TYPE; i++) { + while ((victim = TOR_TAILQ_FIRST(&ol_list[i]))) { + onion_queue_entry_remove(victim); + } } memset(ol_entries, 0, sizeof(ol_entries)); }

1 0

[tor/master] refactor and give it unit tests
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit bb32bfa2f240d3f417e11b08d98069e0a4a8307e Author: Roger Dingledine <arma(a)torproject.org> Date: Sun Sep 1 04:40:05 2013 -0400 refactor and give it unit tests --- src/or/onion.c | 66 ++++++++++++++++++++++++++++++++++++------------------- src/or/onion.h | 4 ++++ src/test/test.c | 46 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 94 insertions(+), 22 deletions(-) diff --git a/src/or/onion.c b/src/or/onion.c index 60dfdde..a102f13 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -171,7 +171,9 @@ onion_next_task(create_cell_t **onionskin_out) return NULL; /* no onions pending, we're done */ tor_assert(head->circ); - tor_assert(head->circ->p_chan); /* make sure it's still valid */ +// tor_assert(head->circ->p_chan); /* make sure it's still valid */ +/* XXX I only commented out the above line to make the unit tests + * more manageable. That's probably not good long-term. -RD */ circ = head->circ; if (head->onionskin && head->onionskin->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) @@ -183,6 +185,14 @@ onion_next_task(create_cell_t **onionskin_out) return circ; } +/** Return the number of handshake_type-style create requests pending. + */ +int +onion_num_pending(uint16_t handshake_type) +{ + return ol_entries[handshake_type]; +} + /** Go through ol_list, find the onion_queue_t element which points to * circ, remove and free that element. Leave circ itself alone. */ @@ -535,6 +545,22 @@ check_create_cell(const create_cell_t *cell, int unknown_ok) return 0; } +/** Write the various parameters into the create cell. Separate from + * create_cell_parse() to make unit testing easier. + */ +void +create_cell_init(create_cell_t *cell_out, uint8_t cell_type, + uint16_t handshake_type, uint16_t handshake_len, + const uint8_t *onionskin) +{ + memset(cell_out, 0, sizeof(*cell_out)); + + cell_out->cell_type = cell_type; + cell_out->handshake_type = handshake_type; + cell_out->handshake_len = handshake_len; + memcpy(cell_out->onionskin, onionskin, handshake_len); +} + /** Helper: parse the CREATE2 payload at p, which could be up to * p_len bytes long, and use it to fill the fields of * cell_out. Return 0 on success and -1 on failure. @@ -545,17 +571,21 @@ check_create_cell(const create_cell_t *cell, int unknown_ok) static int parse_create2_payload(create_cell_t *cell_out, const uint8_t *p, size_t p_len) { + uint16_t handshake_type, handshake_len; + if (p_len < 4) return -1; - cell_out->cell_type = CELL_CREATE2; - cell_out->handshake_type = ntohs(get_uint16(p)); - cell_out->handshake_len = ntohs(get_uint16(p+2)); - if (cell_out->handshake_len > CELL_PAYLOAD_SIZE - 4 || - cell_out->handshake_len > p_len - 4) + + handshake_type = ntohs(get_uint16(p)); + handshake_len = ntohs(get_uint16(p+2)); + + if (handshake_len > CELL_PAYLOAD_SIZE - 4 || handshake_len > p_len - 4) return -1; - if (cell_out->handshake_type == ONION_HANDSHAKE_TYPE_FAST) + if (handshake_type == ONION_HANDSHAKE_TYPE_FAST) return -1; - memcpy(cell_out->onionskin, p+4, cell_out->handshake_len); + + create_cell_init(cell_out, CELL_CREATE2, handshake_type, handshake_len, + p+4); return 0; } @@ -573,27 +603,19 @@ parse_create2_payload(create_cell_t *cell_out, const uint8_t *p, size_t p_len) int create_cell_parse(create_cell_t *cell_out, const cell_t *cell_in) { - memset(cell_out, 0, sizeof(*cell_out)); - switch (cell_in->command) { case CELL_CREATE: - cell_out->cell_type = CELL_CREATE; if (tor_memeq(cell_in->payload, NTOR_CREATE_MAGIC, 16)) { - cell_out->handshake_type = ONION_HANDSHAKE_TYPE_NTOR; - cell_out->handshake_len = NTOR_ONIONSKIN_LEN; - memcpy(cell_out->onionskin, cell_in->payload+16, NTOR_ONIONSKIN_LEN); + create_cell_init(cell_out, CELL_CREATE, ONION_HANDSHAKE_TYPE_NTOR, + NTOR_ONIONSKIN_LEN, cell_in->payload+16); } else { - cell_out->handshake_type = ONION_HANDSHAKE_TYPE_TAP; - cell_out->handshake_len = TAP_ONIONSKIN_CHALLENGE_LEN; - memcpy(cell_out->onionskin, cell_in->payload, - TAP_ONIONSKIN_CHALLENGE_LEN); + create_cell_init(cell_out, CELL_CREATE, ONION_HANDSHAKE_TYPE_TAP, + TAP_ONIONSKIN_CHALLENGE_LEN, cell_in->payload); } break; case CELL_CREATE_FAST: - cell_out->cell_type = CELL_CREATE_FAST; - cell_out->handshake_type = ONION_HANDSHAKE_TYPE_FAST; - cell_out->handshake_len = CREATE_FAST_LEN; - memcpy(cell_out->onionskin, cell_in->payload, CREATE_FAST_LEN); + create_cell_init(cell_out, CELL_CREATE_FAST, ONION_HANDSHAKE_TYPE_FAST, + CREATE_FAST_LEN, cell_in->payload); break; case CELL_CREATE2: if (parse_create2_payload(cell_out, cell_in->payload, diff --git a/src/or/onion.h b/src/or/onion.h index db4c999..d62f032 100644 --- a/src/or/onion.h +++ b/src/or/onion.h @@ -15,6 +15,7 @@ struct create_cell_t; int onion_pending_add(or_circuit_t *circ, struct create_cell_t *onionskin); or_circuit_t *onion_next_task(struct create_cell_t **onionskin_out); +int onion_num_pending(uint16_t handshake_type); void onion_pending_remove(or_circuit_t *circ); void clear_pending_onions(void); @@ -99,6 +100,9 @@ typedef struct extended_cell_t { created_cell_t created_cell; } extended_cell_t; +void create_cell_init(create_cell_t *cell_out, uint8_t cell_type, + uint16_t handshake_type, uint16_t handshake_len, + const uint8_t *onionskin); int create_cell_parse(create_cell_t *cell_out, const cell_t *cell_in); int created_cell_parse(created_cell_t *cell_out, const cell_t *cell_in); int extend_cell_parse(extend_cell_t *cell_out, const uint8_t command, diff --git a/src/test/test.c b/src/test/test.c index 3ff39e6..4ec8792 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -44,6 +44,7 @@ double fabs(double x); #include "or.h" #include "buffers.h" +#include "circuitlist.h" #include "circuitstats.h" #include "config.h" #include "connection_edge.h" @@ -53,6 +54,7 @@ double fabs(double x); #include "torgzip.h" #include "mempool.h" #include "memarea.h" +#include "onion.h" #include "onion_tap.h" #include "policies.h" #include "rephist.h" @@ -933,6 +935,49 @@ test_ntor_handshake(void *arg) } #endif +/** Run unit tests for the onion queues. */ +static void +test_onion_queues(void) +{ + uint8_t buf1[TAP_ONIONSKIN_CHALLENGE_LEN] = {0}; + uint8_t buf2[NTOR_ONIONSKIN_LEN] = {0}; + + or_circuit_t *circ1 = or_circuit_new(0, NULL); + or_circuit_t *circ2 = or_circuit_new(0, NULL); + + create_cell_t *onionskin = NULL; + create_cell_t *create1 = tor_malloc_zero(sizeof(create_cell_t)); + create_cell_t *create2 = tor_malloc_zero(sizeof(create_cell_t)); + + create_cell_init(create1, CELL_CREATE, ONION_HANDSHAKE_TYPE_TAP, + TAP_ONIONSKIN_CHALLENGE_LEN, buf1); + create_cell_init(create2, CELL_CREATE, ONION_HANDSHAKE_TYPE_NTOR, + NTOR_ONIONSKIN_LEN, buf2); + + test_eq(0, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP)); + test_eq(0, onion_pending_add(circ1, create1)); + test_eq(1, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP)); + + test_eq(0, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR)); + test_eq(0, onion_pending_add(circ2, create2)); + test_eq(1, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR)); + + test_eq_ptr(circ2, onion_next_task(&onionskin)); + test_eq(1, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP)); + test_eq(0, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR)); + + clear_pending_onions(); + test_eq(0, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP)); + test_eq(0, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR)); + + done: + ; +// circuit_free(circ1); +// circuit_free(circ2); + /* and free create1 and create2 */ + /* XXX leaks everything here */ +} + static void test_circuit_timeout(void) { @@ -2005,6 +2050,7 @@ static struct testcase_t test_array[] = { ENT(buffers), { "buffer_copy", test_buffer_copy, 0, NULL, NULL }, ENT(onion_handshake), + ENT(onion_queues), #ifdef CURVE25519_ENABLED { "ntor_handshake", test_ntor_handshake, 0, NULL, NULL }, #endif

1 0

[tor/master] add info-level logs to help track onion queue sizes
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit 9d2030e5801acd955ab81d1329360b45af09d253 Author: Roger Dingledine <arma(a)torproject.org> Date: Sun Sep 1 16:51:27 2013 -0400 add info-level logs to help track onion queue sizes --- src/or/onion.c | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) diff --git a/src/or/onion.c b/src/or/onion.c index a102f13..c5f1566 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -135,6 +135,11 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) } ++ol_entries[onionskin->handshake_type]; + log_info(LD_OR, "New create (%s). Queues now ntor=%d and tap=%d.", + onionskin->handshake_type == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap", + ol_entries[ONION_HANDSHAKE_TYPE_NTOR], + ol_entries[ONION_HANDSHAKE_TYPE_TAP]); + circ->onionqueue_entry = tmp; TOR_TAILQ_INSERT_TAIL(&ol_list[onionskin->handshake_type], tmp, next); @@ -176,8 +181,13 @@ onion_next_task(create_cell_t **onionskin_out) * more manageable. That's probably not good long-term. -RD */ circ = head->circ; if (head->onionskin && - head->onionskin->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) - --ol_entries[head->onionskin->handshake_type]; + head->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) + --ol_entries[head->handshake_type]; + log_info(LD_OR, "Processing create (%s). Queues now ntor=%d and tap=%d.", + head->handshake_type == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap", + ol_entries[ONION_HANDSHAKE_TYPE_NTOR], + ol_entries[ONION_HANDSHAKE_TYPE_TAP]); + *onionskin_out = head->onionskin; head->onionskin = NULL; /* prevent free. */ circ->onionqueue_entry = NULL;

1 0

[tor/master] check bounds on handshake_type more thoroughly
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit 16b5c609a4a4e9d6c25767cebb434746228de210 Author: Roger Dingledine <arma(a)torproject.org> Date: Tue Sep 3 18:48:16 2013 -0400 check bounds on handshake_type more thoroughly --- src/or/onion.c | 22 +++++++++++++++++----- 1 file changed, 17 insertions(+), 5 deletions(-) diff --git a/src/or/onion.c b/src/or/onion.c index c5f1566..0b04891 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -110,6 +110,12 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) onion_queue_t *tmp; time_t now = time(NULL); + if (onionskin->handshake_type > MAX_ONION_HANDSHAKE_TYPE) { + log_warn(LD_BUG, "Handshake %d out of range! Dropping.", + onionskin->handshake_type); + return -1; + } + tmp = tor_malloc_zero(sizeof(onion_queue_t)); tmp->circ = circ; tmp->handshake_type = onionskin->handshake_type; @@ -176,12 +182,12 @@ onion_next_task(create_cell_t **onionskin_out) return NULL; /* no onions pending, we're done */ tor_assert(head->circ); + tor_assert(head->handshake_type <= MAX_ONION_HANDSHAKE_TYPE); // tor_assert(head->circ->p_chan); /* make sure it's still valid */ /* XXX I only commented out the above line to make the unit tests * more manageable. That's probably not good long-term. -RD */ circ = head->circ; - if (head->onionskin && - head->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) + if (head->onionskin) --ol_entries[head->handshake_type]; log_info(LD_OR, "Processing create (%s). Queues now ntor=%d and tap=%d.", head->handshake_type == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap", @@ -224,14 +230,20 @@ onion_pending_remove(or_circuit_t *circ) static void onion_queue_entry_remove(onion_queue_t *victim) { + if (victim->handshake_type > MAX_ONION_HANDSHAKE_TYPE) { + log_warn(LD_BUG, "Handshake %d out of range! Dropping.", + victim->handshake_type); + /* XXX leaks */ + return; + } + TOR_TAILQ_REMOVE(&ol_list[victim->handshake_type], victim, next); if (victim->circ) victim->circ->onionqueue_entry = NULL; - if (victim->onionskin && - victim->onionskin->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) - --ol_entries[victim->onionskin->handshake_type]; + if (victim->onionskin) + --ol_entries[victim->handshake_type]; tor_free(victim->onionskin); tor_free(victim);

1 0

[tor/master] do a lopsided round-robin between the onion queues
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit 7acc7c3dc6299438f7d5e6ebc6cb64f2ea3b5fa6 Author: Roger Dingledine <arma(a)torproject.org> Date: Tue Sep 3 20:40:16 2013 -0400 do a lopsided round-robin between the onion queues that way tap won't starve entirely, but we'll still handle ntor requests quicker. --- src/or/onion.c | 43 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 38 insertions(+), 5 deletions(-) diff --git a/src/or/onion.c b/src/or/onion.c index 0b04891..639481b 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -165,6 +165,42 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) return 0; } +/** Return a fairness parameter, to prefer processing NTOR style + * handshakes but still slowly drain the TAP queue so we don't starve + * it entirely. */ +static int +num_ntors_per_tap(void) +{ +#define NUM_NTORS_PER_TAP 5 + return NUM_NTORS_PER_TAP; +} + +/** Choose which onion queue we'll pull from next. If one is empty choose + * the other; if they both have elements, load balance across them but + * favoring NTOR. */ +static uint16_t +decide_next_handshake_type(void) +{ + /* The number of times we've chosen ntor lately when both were available. */ + static int recently_chosen_ntors = 0; + + if (!ol_entries[ONION_HANDSHAKE_TYPE_NTOR]) + return ONION_HANDSHAKE_TYPE_TAP; /* no ntors? try tap */ + + if (!ol_entries[ONION_HANDSHAKE_TYPE_TAP]) + return ONION_HANDSHAKE_TYPE_NTOR; /* no taps? try ntor */ + + /* They both have something queued. Pick ntor if we haven't done that + * too much lately. */ + if (++recently_chosen_ntors <= num_ntors_per_tap()) { + return ONION_HANDSHAKE_TYPE_NTOR; + } + + /* Else, it's time to let tap have its turn. */ + recently_chosen_ntors = 0; + return ONION_HANDSHAKE_TYPE_TAP; +} + /** Remove the highest priority item from ol_list[] and return it, or * return NULL if the lists are empty. */ @@ -172,11 +208,8 @@ or_circuit_t * onion_next_task(create_cell_t **onionskin_out) { or_circuit_t *circ; - - /* skip ol_list[ONION_HANDSHAKE_TYPE_FAST] since we know it'll be empty */ - onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[ONION_HANDSHAKE_TYPE_NTOR]); - if (!head) - head = TOR_TAILQ_FIRST(&ol_list[ONION_HANDSHAKE_TYPE_TAP]); + uint16_t handshake_to_choose = decide_next_handshake_type(); + onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[handshake_to_choose]); if (!head) return NULL; /* no onions pending, we're done */

1 0

[tor/maint-0.2.4] check bounds on handshake_type more thoroughly
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit 16b5c609a4a4e9d6c25767cebb434746228de210 Author: Roger Dingledine <arma(a)torproject.org> Date: Tue Sep 3 18:48:16 2013 -0400 check bounds on handshake_type more thoroughly --- src/or/onion.c | 22 +++++++++++++++++----- 1 file changed, 17 insertions(+), 5 deletions(-) diff --git a/src/or/onion.c b/src/or/onion.c index c5f1566..0b04891 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -110,6 +110,12 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) onion_queue_t *tmp; time_t now = time(NULL); + if (onionskin->handshake_type > MAX_ONION_HANDSHAKE_TYPE) { + log_warn(LD_BUG, "Handshake %d out of range! Dropping.", + onionskin->handshake_type); + return -1; + } + tmp = tor_malloc_zero(sizeof(onion_queue_t)); tmp->circ = circ; tmp->handshake_type = onionskin->handshake_type; @@ -176,12 +182,12 @@ onion_next_task(create_cell_t **onionskin_out) return NULL; /* no onions pending, we're done */ tor_assert(head->circ); + tor_assert(head->handshake_type <= MAX_ONION_HANDSHAKE_TYPE); // tor_assert(head->circ->p_chan); /* make sure it's still valid */ /* XXX I only commented out the above line to make the unit tests * more manageable. That's probably not good long-term. -RD */ circ = head->circ; - if (head->onionskin && - head->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) + if (head->onionskin) --ol_entries[head->handshake_type]; log_info(LD_OR, "Processing create (%s). Queues now ntor=%d and tap=%d.", head->handshake_type == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap", @@ -224,14 +230,20 @@ onion_pending_remove(or_circuit_t *circ) static void onion_queue_entry_remove(onion_queue_t *victim) { + if (victim->handshake_type > MAX_ONION_HANDSHAKE_TYPE) { + log_warn(LD_BUG, "Handshake %d out of range! Dropping.", + victim->handshake_type); + /* XXX leaks */ + return; + } + TOR_TAILQ_REMOVE(&ol_list[victim->handshake_type], victim, next); if (victim->circ) victim->circ->onionqueue_entry = NULL; - if (victim->onionskin && - victim->onionskin->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) - --ol_entries[victim->onionskin->handshake_type]; + if (victim->onionskin) + --ol_entries[victim->handshake_type]; tor_free(victim->onionskin); tor_free(victim);

1 0

[tor/maint-0.2.4] do a lopsided round-robin between the onion queues
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit 7acc7c3dc6299438f7d5e6ebc6cb64f2ea3b5fa6 Author: Roger Dingledine <arma(a)torproject.org> Date: Tue Sep 3 20:40:16 2013 -0400 do a lopsided round-robin between the onion queues that way tap won't starve entirely, but we'll still handle ntor requests quicker. --- src/or/onion.c | 43 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 38 insertions(+), 5 deletions(-) diff --git a/src/or/onion.c b/src/or/onion.c index 0b04891..639481b 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -165,6 +165,42 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) return 0; } +/** Return a fairness parameter, to prefer processing NTOR style + * handshakes but still slowly drain the TAP queue so we don't starve + * it entirely. */ +static int +num_ntors_per_tap(void) +{ +#define NUM_NTORS_PER_TAP 5 + return NUM_NTORS_PER_TAP; +} + +/** Choose which onion queue we'll pull from next. If one is empty choose + * the other; if they both have elements, load balance across them but + * favoring NTOR. */ +static uint16_t +decide_next_handshake_type(void) +{ + /* The number of times we've chosen ntor lately when both were available. */ + static int recently_chosen_ntors = 0; + + if (!ol_entries[ONION_HANDSHAKE_TYPE_NTOR]) + return ONION_HANDSHAKE_TYPE_TAP; /* no ntors? try tap */ + + if (!ol_entries[ONION_HANDSHAKE_TYPE_TAP]) + return ONION_HANDSHAKE_TYPE_NTOR; /* no taps? try ntor */ + + /* They both have something queued. Pick ntor if we haven't done that + * too much lately. */ + if (++recently_chosen_ntors <= num_ntors_per_tap()) { + return ONION_HANDSHAKE_TYPE_NTOR; + } + + /* Else, it's time to let tap have its turn. */ + recently_chosen_ntors = 0; + return ONION_HANDSHAKE_TYPE_TAP; +} + /** Remove the highest priority item from ol_list[] and return it, or * return NULL if the lists are empty. */ @@ -172,11 +208,8 @@ or_circuit_t * onion_next_task(create_cell_t **onionskin_out) { or_circuit_t *circ; - - /* skip ol_list[ONION_HANDSHAKE_TYPE_FAST] since we know it'll be empty */ - onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[ONION_HANDSHAKE_TYPE_NTOR]); - if (!head) - head = TOR_TAILQ_FIRST(&ol_list[ONION_HANDSHAKE_TYPE_TAP]); + uint16_t handshake_to_choose = decide_next_handshake_type(); + onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[handshake_to_choose]); if (!head) return NULL; /* no onions pending, we're done */

1 0

[tor/maint-0.2.4] Be more general in calculating expected onion queue processing time
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit a4400952ee477ac6fb5a2743f14df0dcd1cb8424 Author: Roger Dingledine <arma(a)torproject.org> Date: Tue Sep 3 22:15:33 2013 -0400 Be more general in calculating expected onion queue processing time Now we consider the TAP cells we'll process while draining the NTor queue, and vice versa. --- src/or/onion.c | 31 +++++++++++++++++++++++++++---- 1 file changed, 27 insertions(+), 4 deletions(-) diff --git a/src/or/onion.c b/src/or/onion.c index 4ea2061..cabd055 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -49,6 +49,7 @@ TOR_TAILQ_HEAD(onion_queue_head_t, onion_queue_t) /** Number of entries of each type currently in each element of ol_list[]. */ static int ol_entries[MAX_ONION_HANDSHAKE_TYPE+1]; +static int num_ntors_per_tap(void); static void onion_queue_entry_remove(onion_queue_t *victim); /* XXXX024 Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN. @@ -66,27 +67,49 @@ have_room_for_onionskin(uint16_t type) const or_options_t *options = get_options(); int num_cpus; uint64_t tap_usec, ntor_usec; + uint64_t ntor_during_tap_usec, tap_during_ntor_usec; + /* If we've got fewer than 50 entries, we always have room for one more. */ if (ol_entries[type] < 50) return 1; num_cpus = get_num_cpus(options); /* Compute how many microseconds we'd expect to need to clear all - * onionskins in the current queue. */ + * onionskins in various combinations of the queues. */ + + /* How long would it take to process all the TAP cells in the queue? */ tap_usec = estimated_usec_for_onionskins( ol_entries[ONION_HANDSHAKE_TYPE_TAP], ONION_HANDSHAKE_TYPE_TAP) / num_cpus; + + /* How long would it take to process all the NTor cells in the queue? */ ntor_usec = estimated_usec_for_onionskins( ol_entries[ONION_HANDSHAKE_TYPE_NTOR], ONION_HANDSHAKE_TYPE_NTOR) / num_cpus; + /* How long would it take to process the tap cells that we expect to + * process while draining the ntor queue? */ + tap_during_ntor_usec = estimated_usec_for_onionskins( + MIN(ol_entries[ONION_HANDSHAKE_TYPE_TAP], + ol_entries[ONION_HANDSHAKE_TYPE_NTOR] / num_ntors_per_tap()), + ONION_HANDSHAKE_TYPE_TAP) / num_cpus; + + /* How long would it take to process the ntor cells that we expect to + * process while draining the tap queue? */ + ntor_during_tap_usec = estimated_usec_for_onionskins( + MIN(ol_entries[ONION_HANDSHAKE_TYPE_NTOR], + ol_entries[ONION_HANDSHAKE_TYPE_TAP] * num_ntors_per_tap()), + ONION_HANDSHAKE_TYPE_NTOR) / num_cpus; + /* See whether that exceeds MaxOnionQueueDelay. If so, we can't queue * this. */ if (type == ONION_HANDSHAKE_TYPE_NTOR && - ntor_usec / 1000 > (uint64_t)options->MaxOnionQueueDelay) + (ntor_usec + tap_during_ntor_usec) / 1000 > + (uint64_t)options->MaxOnionQueueDelay) return 0; if (type == ONION_HANDSHAKE_TYPE_TAP && - (tap_usec + ntor_usec) / 1000 > (uint64_t)options->MaxOnionQueueDelay) + (tap_usec + ntor_during_tap_usec) / 1000 > + (uint64_t)options->MaxOnionQueueDelay) return 0; #ifdef CURVE25519_ENABLED @@ -173,7 +196,7 @@ static int num_ntors_per_tap(void) { #define DEFAULT_NUM_NTORS_PER_TAP 10 -#define MIN_NUM_NTORS_PER_TAP 0 +#define MIN_NUM_NTORS_PER_TAP 1 #define MAX_NUM_NTORS_PER_TAP 100000 return networkstatus_get_param(NULL, "NumNTorsPerTAP",

1 0

[tor/maint-0.2.4] nickm wants us to prioritize tap in a currently-rare edge case
by arma＠torproject.org 05 Sep '13

05 Sep '13

commit c6f1668db3010de6aed22bd87850aa846911d43b Author: Roger Dingledine <arma(a)torproject.org> Date: Wed Sep 4 19:43:46 2013 -0400 nickm wants us to prioritize tap in a currently-rare edge case --- src/or/onion.c | 15 ++++++++++++++- 1 file changed, 14 insertions(+), 1 deletion(-) diff --git a/src/or/onion.c b/src/or/onion.c index cabd055..41fe7b6 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -217,8 +217,21 @@ decide_next_handshake_type(void) if (!ol_entries[ONION_HANDSHAKE_TYPE_NTOR]) return ONION_HANDSHAKE_TYPE_TAP; /* no ntors? try tap */ - if (!ol_entries[ONION_HANDSHAKE_TYPE_TAP]) + if (!ol_entries[ONION_HANDSHAKE_TYPE_TAP]) { + + /* Nick wants us to prioritize new tap requests when there aren't + * any in the queue and we've processed k ntor cells since the last + * tap cell. This strategy is maybe a good idea, since it starves tap + * less in the case where tap is rare, or maybe a poor idea, since it + * makes the new tap cell unfairly jump in front of ntor cells that + * got here first. In any case this edge case will only become relevant + * once tap is rare. We should reevaluate whether we like this decision + * once tap gets more rare. */ + if (ol_entries[ONION_HANDSHAKE_TYPE_NTOR]) + ++recently_chosen_ntors; + return ONION_HANDSHAKE_TYPE_NTOR; /* no taps? try ntor */ + } /* They both have something queued. Pick ntor if we haven't done that * too much lately. */

1 0