commit b0b3c14c11afe55cd71f9c1b8a89d9e5a65c9799 Author: Nick Mathewson nickm@torproject.org Date: Wed Dec 26 18:08:01 2012 -0500
Eliminate MaxOnionsPending; replace it with MaxOnionQueueDelay
The right way to set "MaxOnionsPending" was to adjust it until the processing delay was appropriate. So instead, let's measure how long it takes to process onionskins (sampling them once we have a big number), and then limit the queue based on its expected time to finish.
This change is extra-necessary for ntor, since there is no longer a reasonable way to set MaxOnionsPending without knowing what mix of onionskins you'll get.
This patch also reserves 1/3 of the onionskin spots for ntor handshakes, on the theory that TAP handshakes shouldn't be allowed to starve their speedier cousins. We can change this later if need be.
Resolves 7291. --- changes/timed_onionqueue | 7 +++ doc/tor.1.txt | 6 +- src/or/config.c | 3 +- src/or/cpuworker.c | 122 +++++++++++++++++++++++++++++++++++++++++++++- src/or/cpuworker.h | 3 + src/or/onion.c | 68 +++++++++++++++++++++---- src/or/or.h | 5 +- 7 files changed, 195 insertions(+), 19 deletions(-)
diff --git a/changes/timed_onionqueue b/changes/timed_onionqueue new file mode 100644 index 0000000..d0900ba --- /dev/null +++ b/changes/timed_onionqueue @@ -0,0 +1,7 @@ + o Minor features (relay): + - Instead of limiting the number of queued onionskins to a configured, + hard-to-configure number, we limit the size of the queue based on how + many we expect to be able to process in a given amount of time. We + estimate the time it will take to process an onionskin based on average + processing time of previous onionskins. Closes ticket 7291. You'll + never have to configure MaxOnionsPending again. diff --git a/doc/tor.1.txt b/doc/tor.1.txt index 40cf66d..d107fa9 100644 --- a/doc/tor.1.txt +++ b/doc/tor.1.txt @@ -1376,9 +1376,9 @@ is non-zero): If set, and we are an exit node, allow clients to use us for IPv6 traffic. (Default: 0)
-**MaxOnionsPending** __NUM__:: - If you have more than this number of onionskins queued for decrypt, reject - new ones. (Default: 100) +**MaxOnionQueueDelay** __NUM__ [**msec**|**second**]:: + If we have more onionskins queued for processing than we can process in + this amount of time, reject new ones. (Default: 1750 msec)
**MyFamily** __node__,__node__,__...__:: Declare that this Tor server is controlled or administered by a group or diff --git a/src/or/config.c b/src/or/config.c index 9905a94..4b3937b 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -296,7 +296,8 @@ static config_var_t option_vars_[] = { V(MaxAdvertisedBandwidth, MEMUNIT, "1 GB"), V(MaxCircuitDirtiness, INTERVAL, "10 minutes"), V(MaxClientCircuitsPending, UINT, "32"), - V(MaxOnionsPending, UINT, "100"), + OBSOLETE("MaxOnionsPending"), + V(MaxOnionQueueDelay, MSEC_INTERVAL, "1750 msec"), OBSOLETE("MonthlyAccountingStart"), V(MyFamily, STRING, NULL), V(NewCircuitPeriod, INTERVAL, "30 seconds"), diff --git a/src/or/cpuworker.c b/src/or/cpuworker.c index 3f8fc94..a626224 100644 --- a/src/or/cpuworker.c +++ b/src/or/cpuworker.c @@ -98,6 +98,11 @@ typedef struct cpuworker_request_t { /** Task code. Must be one of CPUWORKER_TASK_* */ uint8_t task;
+ /** Flag: Are we timing this request? */ + unsigned timed : 1; + /** If we're timing this request, when was it sent to the cpuworker? */ + struct timeval started_at; + /** A create cell for the cpuworker to process. */ create_cell_t create_cell;
@@ -113,6 +118,17 @@ typedef struct cpuworker_reply_t { /** True iff we got a successful request. */ uint8_t success;
+ /** Are we timing this request? */ + unsigned int timed : 1; + /** What handshake type was the request? (Used for timing) */ + uint16_t handshake_type; + /** When did we send the request to the cpuworker? */ + struct timeval started_at; + /** Once the cpuworker received the request, how many microseconds did it + * take? (This shouldn't overflow; 4 billion micoseconds is over an hour, + * and we'll never have an onion handshake that takes so long.) */ + uint32_t n_usec; + /** Output of processing a create cell * * @{ @@ -163,6 +179,62 @@ connection_cpu_reached_eof(connection_t *conn) return 0; }
+/** Indexed by handshake type: how many onionskins have we processed and + * counted of that type? */ +static uint64_t onionskins_n_processed[MAX_ONION_HANDSHAKE_TYPE+1]; +/** Indexed by handshake type, corresponding to the onionskins counted in + * onionskins_n_processed: how many microseconds have we spent in cpuworkers + * processing that kind of onionskin? */ +static uint64_t onionskins_usec_internal[MAX_ONION_HANDSHAKE_TYPE+1]; +/** Indexed by handshake type, corresponding to onionskins counted in + * onionskins_n_processed: how many microseconds have we spent waiting for + * cpuworkers to give us answers for that kind of onionskin? + */ +static uint64_t onionskins_usec_roundtrip[MAX_ONION_HANDSHAKE_TYPE+1]; + +/** If any onionskin takes longer than this, we clip them to this + * time. (microseconds) */ +#define MAX_BELIEVABLE_ONIONSKIN_DELAY (2*1000*1000) + +/** Return true iff we'd like to measure a handshake of type + * <b>onionskin_type</b>. */ +static int +should_time_request(uint16_t onionskin_type) +{ + /* If we've never heard of this type, we shouldn't even be here. */ + if (onionskin_type > MAX_ONION_HANDSHAKE_TYPE) + return 0; + /* Measure the first N handshakes of each type, to ensure we have a + * sample */ + if (onionskins_n_processed[onionskin_type] < 4096) + return 1; + /** Otherwise, measure with P=1/128. We avoid doing this for every + * handshake, since the measurement itself can take a little time. */ + return tor_weak_random() < (TOR_RAND_MAX/128); +} + +/** Return an estimate of how many microseconds we will need for a single + * cpuworker to to process <b>n_requests</b> onionskins of type + * <b>onionskin_type</b>. */ +uint64_t +estimated_usec_for_onionskins(uint32_t n_requests, uint16_t onionskin_type) +{ + if (onionskin_type > MAX_ONION_HANDSHAKE_TYPE) /* should be impossible */ + return 1000 * n_requests; + if (PREDICT_UNLIKELY(onionskins_n_processed[onionskin_type] < 100)) { + /* Until we have 100 data points, just asssume everything takes 1 msec. */ + return 1000 * n_requests; + } else { + /* This can't overflow: we'll never have more than 500000 onionskins + * measured in onionskin_usec_internal, and they won't take anything near + * 1 sec each, and we won't have anything like 1 million queued + * onionskins. But that's 5e5 * 1e6 * 1e6, which is still less than + * UINT64_MAX. */ + return (onionskins_usec_internal[onionskin_type] * n_requests) / + onionskins_n_processed[onionskin_type]; + } +} + /** Called when we get data from a cpuworker. If the answer is not complete, * wait for a complete answer. If the answer is complete, * process it as appropriate. @@ -190,6 +262,31 @@ connection_cpu_process_inbuf(connection_t *conn) connection_fetch_from_buf((void*)&rpl,sizeof(cpuworker_reply_t),conn);
tor_assert(rpl.magic == CPUWORKER_REPLY_MAGIC); + + if (rpl.timed && rpl.success && + rpl.handshake_type <= MAX_ONION_HANDSHAKE_TYPE) { + /* Time how long this request took. The handshake_type check should be + needless, but let's leave it in to be safe. */ + struct timeval tv_end, tv_diff; + int64_t usec_roundtrip; + tor_gettimeofday(&tv_end); + timersub(&tv_end, &rpl.started_at, &tv_diff); + usec_roundtrip = ((int64_t)tv_diff.tv_sec)*1000000 + tv_diff.tv_usec; + if (usec_roundtrip < 0 || + usec_roundtrip > MAX_BELIEVABLE_ONIONSKIN_DELAY) { + usec_roundtrip = MAX_BELIEVABLE_ONIONSKIN_DELAY; + } + ++onionskins_n_processed[rpl.handshake_type]; + onionskins_usec_internal[rpl.handshake_type] += rpl.n_usec; + onionskins_usec_roundtrip[rpl.handshake_type] += usec_roundtrip; + if (onionskins_n_processed[rpl.handshake_type] >= 500000) { + /* Scale down every 500000 handshakes. On a busy server, that's + * less impressive than it sounds. */ + onionskins_n_processed[rpl.handshake_type] /= 2; + onionskins_usec_internal[rpl.handshake_type] /= 2; + onionskins_usec_roundtrip[rpl.handshake_type] /= 2; + } + } /* parse out the circ it was talking about */ tag_unpack(rpl.tag, &chan_id, &circ_id); circ = NULL; @@ -289,7 +386,13 @@ cpuworker_main(void *data) if (req.task == CPUWORKER_TASK_ONION) { const create_cell_t *cc = &req.create_cell; created_cell_t *cell_out = &rpl.created_cell; + struct timeval tv_start, tv_end; int n; + rpl.timed = req.timed; + rpl.started_at = req.started_at; + rpl.handshake_type = cc->handshake_type; + if (req.timed) + tor_gettimeofday(&tv_start); n = onion_skin_server_handshake(cc->handshake_type, cc->onionskin, cc->handshake_len, &onion_keys, @@ -321,6 +424,17 @@ cpuworker_main(void *data) rpl.success = 1; } rpl.magic = CPUWORKER_REPLY_MAGIC; + if (req.timed) { + struct timeval tv_diff; + int64_t usec; + tor_gettimeofday(&tv_end); + timersub(&tv_end, &tv_start, &tv_diff); + usec = ((int64_t)tv_diff.tv_sec)*1000000 + tv_diff.tv_usec; + if (usec < 0 || usec > MAX_BELIEVABLE_ONIONSKIN_DELAY) + rpl.n_usec = MAX_BELIEVABLE_ONIONSKIN_DELAY; + else + rpl.n_usec = (uint32_t) usec; + } if (write_all(fd, (void*)&rpl, sizeof(rpl), 1) != sizeof(rpl)) { log_err(LD_BUG,"writing response buf failed. Exiting."); goto end; @@ -478,6 +592,7 @@ assign_onionskin_to_cpuworker(connection_t *cpuworker, cpuworker_request_t req; time_t now = approx_time(); static time_t last_culled_cpuworkers = 0; + int should_time;
/* Checking for wedged cpuworkers requires a linear search over all * connections, so let's do it only once a minute. @@ -512,16 +627,18 @@ assign_onionskin_to_cpuworker(connection_t *cpuworker, return -1; }
+ should_time = should_time_request(onionskin->handshake_type); memset(&req, 0, sizeof(req)); req.magic = CPUWORKER_REQUEST_MAGIC; tag_pack(req.tag, circ->p_chan->global_identifier, circ->p_circ_id); + req.timed = should_time;
cpuworker->state = CPUWORKER_STATE_BUSY_ONION; /* touch the lastwritten timestamp, since that's how we check to * see how long it's been since we asked the question, and sometimes * we check before the first call to connection_handle_write(). */ - cpuworker->timestamp_lastwritten = time(NULL); + cpuworker->timestamp_lastwritten = now; num_cpuworkers_busy++;
req.task = CPUWORKER_TASK_ONION; @@ -529,6 +646,9 @@ assign_onionskin_to_cpuworker(connection_t *cpuworker,
tor_free(onionskin);
+ if (should_time) + tor_gettimeofday(&req.started_at); + connection_write_to_buf((void*)&req, sizeof(req), cpuworker); memwipe(&req, 0, sizeof(req)); } diff --git a/src/or/cpuworker.h b/src/or/cpuworker.h index f607e7d..df69172 100644 --- a/src/or/cpuworker.h +++ b/src/or/cpuworker.h @@ -22,5 +22,8 @@ int assign_onionskin_to_cpuworker(connection_t *cpuworker, or_circuit_t *circ, struct create_cell_t *onionskin);
+uint64_t estimated_usec_for_onionskins(uint32_t n_requests, + uint16_t onionskin_type); + #endif
diff --git a/src/or/onion.c b/src/or/onion.c index fc3e621..9e22208 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -13,6 +13,7 @@ #include "or.h" #include "circuitlist.h" #include "config.h" +#include "cpuworker.h" #include "onion.h" #include "onion_fast.h" #include "onion_ntor.h" @@ -39,10 +40,52 @@ typedef struct onion_queue_t { static onion_queue_t *ol_list=NULL; static onion_queue_t *ol_tail=NULL; /**@}*/ -/** Length of ol_list */ -static int ol_length=0;
-/* XXXX Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN */ +/** Number of entries of each type currently in ol_list. */ +static int ol_entries[MAX_ONION_HANDSHAKE_TYPE+1]; + +/* XXXX024 Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN. + * + * (By which I think I meant, "make sure that no + * X_ONIONSKIN_CHALLENGE/REPLY_LEN is greater than + * MAX_ONIONSKIN_CHALLENGE/REPLY_LEN." Also, make sure that we can pass + * over-large values via EXTEND2/EXTENDED2, for future-compatibility.*/ + +/** Return true iff we have room to queue another oninoskin of type + * <b>type</b>. */ +static int +have_room_for_onionskin(uint16_t type) +{ + const or_options_t *options = get_options(); + 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) + 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. */ + tap_usec = estimated_usec_for_onionskins( + ol_entries[ONION_HANDSHAKE_TYPE_TAP], + ONION_HANDSHAKE_TYPE_TAP) / num_cpus; + 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) + 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. */ + if (type == ONION_HANDSHAKE_TYPE_TAP && + tap_usec / 1000 > (uint64_t)options->MaxOnionQueueDelay * 2 / 3) + return 0; +#endif + + return 1; +}
/** Add <b>circ</b> to the end of ol_list and return 0, except * if ol_list is too long, in which case do nothing and return -1. @@ -60,17 +103,16 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin)
if (!ol_tail) { tor_assert(!ol_list); - tor_assert(!ol_length); ol_list = tmp; ol_tail = tmp; - ol_length++; + ++ol_entries[onionskin->handshake_type]; return 0; }
tor_assert(ol_list); tor_assert(!ol_tail->next);
- if (ol_length >= get_options()->MaxOnionsPending) { + if (!have_room_for_onionskin(onionskin->handshake_type)) { #define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60) static ratelim_t last_warned = RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL); @@ -87,7 +129,7 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) return -1; }
- ol_length++; + ++ol_entries[onionskin->handshake_type]; ol_tail->next = tmp; ol_tail = tmp; while ((int)(now - ol_list->when_added) >= ONIONQUEUE_WAIT_CUTOFF) { @@ -114,8 +156,10 @@ onion_next_task(create_cell_t **onionskin_out)
tor_assert(ol_list->circ); tor_assert(ol_list->circ->p_chan); /* make sure it's still valid */ - tor_assert(ol_length > 0); circ = ol_list->circ; + if (ol_list->onionskin && + ol_list->onionskin->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) + --ol_entries[ol_list->onionskin->handshake_type]; *onionskin_out = ol_list->onionskin; ol_list->onionskin = NULL; /* prevent free. */ onion_pending_remove(ol_list->circ); @@ -140,7 +184,6 @@ onion_pending_remove(or_circuit_t *circ) ol_list = tmpo->next; if (!ol_list) ol_tail = NULL; - ol_length--; victim = tmpo; } else { /* we need to hunt through the rest of the list */ for ( ;tmpo->next && tmpo->next->circ != circ; tmpo=tmpo->next) ; @@ -155,9 +198,12 @@ onion_pending_remove(or_circuit_t *circ) tmpo->next = victim->next; if (ol_tail == victim) ol_tail = tmpo; - ol_length--; }
+ if (victim->onionskin && + victim->onionskin->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) + --ol_entries[victim->onionskin->handshake_type]; + /* now victim points to the element that needs to be removed */
tor_free(victim->onionskin); @@ -175,7 +221,7 @@ clear_pending_onions(void) tor_free(victim); } ol_list = ol_tail = NULL; - ol_length = 0; + memset(ol_entries, 0, sizeof(ol_entries)); }
/* ============================================================ */ diff --git a/src/or/or.h b/src/or/or.h index 7b8ff70..7db5a52 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -2579,6 +2579,7 @@ struct ntor_handshake_state_t; #define ONION_HANDSHAKE_TYPE_TAP 0x0000 #define ONION_HANDSHAKE_TYPE_FAST 0x0001 #define ONION_HANDSHAKE_TYPE_NTOR 0x0002 +#define MAX_ONION_HANDSHAKE_TYPE 0x0002 typedef struct { uint16_t tag; union { @@ -3483,9 +3484,7 @@ typedef struct { * and try a new circuit if the stream has been * waiting for this many seconds. If zero, use * our default internal timeout schedule. */ - int MaxOnionsPending; /**< How many circuit CREATE requests do we allow - * to wait simultaneously before we start dropping - * them? */ + int MaxOnionQueueDelay; /**<DOCDOC*/ int NewCircuitPeriod; /**< How long do we use a circuit before building * a new one? */ int MaxCircuitDirtiness; /**< Never use circs that were first used more than