diff options
Diffstat (limited to 'src/or/circuitbuild.c')
| -rw-r--r-- | src/or/circuitbuild.c | 744 |
1 files changed, 744 insertions, 0 deletions
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index ef9d24c853..177852f91a 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -9,9 +9,49 @@ * \brief The actual details of building circuits. **/ +#define CIRCUIT_PRIVATE + #include "or.h" +#include "crypto.h" + +/* + * This madness is needed because if we simply #undef log + * before including or.h or log.h, we get linker collisions + * and random segfaults due to memory corruption (and + * not even at calls to log() either!) + */ + /* XXX022 somebody should rename Tor's log() function, so we can + * remove this wart. -RD */ +#undef log + +/* + * Linux doesn't provide lround in math.h by default, but mac os does... + * It's best just to leave math.h out of the picture entirely. + */ +//#define log math_h_log +//#include <math.h> +//#undef log +long int lround(double x); +double ln(double x); +double log(double x); +double pow(double x, double y); + +double +ln(double x) +{ + return log(x); +} + +#define log _log /********* START VARIABLES **********/ +/** Global list of circuit build times */ +// FIXME: Add this as a member for entry_guard_t instead of global? +// Then we could do per-guard statistics, as guards are likely to +// vary in their own latency. The downside of this is that guards +// can change frequently, so we'd be building a lot more circuits +// most likely. +circuit_build_times_t circ_times; /** A global list of all circuits at this hop. */ extern circuit_t *global_circuitlist; @@ -47,6 +87,10 @@ static smartlist_t *entry_guards = NULL; * and those changes need to be flushed to disk. */ static int entry_guards_dirty = 0; +/** If set, we're running the unit tests: we should avoid clobbering + * our state file or accessing get_options() or get_or_state() */ +static int unit_tests = 0; + /********* END VARIABLES ************/ static int circuit_deliver_create_cell(circuit_t *circ, @@ -60,6 +104,698 @@ static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice); static void entry_guards_changed(void); static time_t start_of_month(time_t when); +/** Make a note that we're running unit tests (rather than running Tor + * itself), so we avoid clobbering our state file. */ +void +circuitbuild_running_unit_tests(void) +{ + unit_tests = 1; +} + +/** + * Reset the build time state. + * + * Leave estimated paramters, timeout, and network liveness in tact + * for future use. + */ +void +circuit_build_times_reset(circuit_build_times_t *cbt) +{ + memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times)); + cbt->pre_timeouts = 0; + cbt->total_build_times = 0; + cbt->build_times_idx = 0; + cbt->have_computed_timeout = 0; +} + +/** + * Initialize the buildtimes structure for first use. + * + * Sets the initial timeout value based to either the + * config setting or BUILD_TIMEOUT_INITIAL_VALUE. + */ +void +circuit_build_times_init(circuit_build_times_t *cbt) +{ + memset(cbt, 0, sizeof(*cbt)); + + if (!unit_tests && get_options()->CircuitBuildTimeout) { + cbt->timeout = get_options()->CircuitBuildTimeout; + if (cbt->timeout < BUILD_TIMEOUT_MIN_VALUE) { + log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %d", + BUILD_TIMEOUT_MIN_VALUE); + cbt->timeout = BUILD_TIMEOUT_MIN_VALUE; + } + } else { + cbt->timeout = BUILD_TIMEOUT_INITIAL_VALUE; + } +} + +/** + * Add a timeoutout value to the set of build times. Time units + * are milliseconds + * + * circuit_build_times is a circular array, so loop around when + * array is full. + */ +int +circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time) +{ + if (time > BUILD_TIME_MAX) { + log_notice(LD_CIRC, + "Circuit build time of %ums exceeds max. Capping at 65536ms", time); + time = BUILD_TIME_MAX; + } else if (time <= 0) { + log_err(LD_CIRC, "Circuit build time is %u!", time); + return -1; + } + + // XXX: Probably want to demote this to debug for the release. + log_info(LD_CIRC, "Adding circuit build time %u", time); + + cbt->circuit_build_times[cbt->build_times_idx] = time; + cbt->build_times_idx = (cbt->build_times_idx + 1) % NCIRCUITS_TO_OBSERVE; + if (cbt->total_build_times < NCIRCUITS_TO_OBSERVE) + cbt->total_build_times++; + + if ((cbt->total_build_times % BUILD_TIMES_SAVE_STATE_EVERY) == 0) { + /* Save state every 100 circuit builds */ + if (!unit_tests && !get_options()->AvoidDiskWrites) + or_state_mark_dirty(get_or_state(), 0); + } + + return 0; +} + +/** + * Return maximum circuit build time + */ +static build_time_t +circuit_build_times_max(circuit_build_times_t *cbt) +{ + int i = 0; + build_time_t max_build_time = 0; + for (i = 0; i < NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] > max_build_time) + max_build_time = cbt->circuit_build_times[i]; + } + return max_build_time; +} + +/** Return minimum circuit build time */ +static build_time_t +circuit_build_times_min(circuit_build_times_t *cbt) +{ + int i = 0; + build_time_t min_build_time = BUILD_TIME_MAX; + for (i = 0; i < NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */ + cbt->circuit_build_times[i] < min_build_time) + min_build_time = cbt->circuit_build_times[i]; + } + if (min_build_time == BUILD_TIME_MAX) { + log_warn(LD_CIRC, "No build times less than BUILD_TIME_MAX!"); + } + return min_build_time; +} + +/** + * Calculate and return a histogram for the set of build times. + * + * Returns an allocated array of histrogram bins representing + * the frequency of index*BUILDTIME_BIN_WIDTH millisecond + * build times. Also outputs the number of bins in nbins. + * + * The return value must be freed by the caller. + */ +static uint32_t * +circuit_build_times_create_histogram(circuit_build_times_t *cbt, + build_time_t *nbins) +{ + uint32_t *histogram; + build_time_t max_build_time = circuit_build_times_max(cbt); + int i, c; + + *nbins = 1 + (max_build_time / BUILDTIME_BIN_WIDTH); + histogram = tor_malloc_zero(*nbins * sizeof(build_time_t)); + + // calculate histogram + for (i = 0; i < NCIRCUITS_TO_OBSERVE; i++) { + if (cbt->circuit_build_times[i] == 0) continue; /* 0 <-> uninitialized */ + + c = (cbt->circuit_build_times[i] / BUILDTIME_BIN_WIDTH); + histogram[c]++; + } + + return histogram; +} + +/** + * Return the most frequent build time (rounded to BUILDTIME_BIN_WIDTH ms). + * + * Ties go in favor of the slower time. + */ +static build_time_t +circuit_build_times_mode(circuit_build_times_t *cbt) +{ + build_time_t i, nbins, max_bin=0; + uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins); + + for (i = 0; i < nbins; i++) { + if (histogram[i] >= histogram[max_bin]) { + max_bin = i; + } + } + + tor_free(histogram); + + return max_bin*BUILDTIME_BIN_WIDTH+BUILDTIME_BIN_WIDTH/2; +} + +/** + * Output a histogram of current circuit build times to + * the or_state_t state structure. + */ +void +circuit_build_times_update_state(circuit_build_times_t *cbt, + or_state_t *state) +{ + uint32_t *histogram; + build_time_t i = 0; + build_time_t nbins = 0; + config_line_t **next, *line; + + histogram = circuit_build_times_create_histogram(cbt, &nbins); + // write to state + config_free_lines(state->BuildtimeHistogram); + next = &state->BuildtimeHistogram; + *next = NULL; + + state->TotalBuildTimes = cbt->total_build_times; + + for (i = 0; i < nbins; i++) { + // compress the histogram by skipping the blanks + if (histogram[i] == 0) continue; + *next = line = tor_malloc_zero(sizeof(config_line_t)); + line->key = tor_strdup("CircuitBuildTimeBin"); + line->value = tor_malloc(25); + tor_snprintf(line->value, 25, "%d %d", + i*BUILDTIME_BIN_WIDTH+BUILDTIME_BIN_WIDTH/2, histogram[i]); + next = &(line->next); + } + + if (!unit_tests) { + if (!get_options()->AvoidDiskWrites) + or_state_mark_dirty(get_or_state(), 0); + } + + if (histogram) tor_free(histogram); +} + +/** + * Shuffle the build times array. + * + * Stolen from http://en.wikipedia.org/wiki/Fisher\u2013Yates_shuffle + */ +static void +circuit_build_times_shuffle_array(circuit_build_times_t *cbt) +{ + int n = cbt->total_build_times; + + /* This code can only be run on a compact array */ + tor_assert(cbt->total_build_times == cbt->build_times_idx); + while (n-- > 1) { + int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */ + build_time_t tmp = cbt->circuit_build_times[k]; + cbt->circuit_build_times[k] = cbt->circuit_build_times[n]; + cbt->circuit_build_times[n] = tmp; + } +} + +/** + * Load histogram from <b>state</b>, shuffling the resulting array + * after we do so. Use this result to estimate parameters and + * calculate the timeout. + * + * Returns -1 and sets msg on error. Msg must be freed by the caller. + */ +int +circuit_build_times_parse_state(circuit_build_times_t *cbt, + or_state_t *state, char **msg) +{ + int tot_values = 0, N = 0; + config_line_t *line; + int i; + *msg = NULL; + circuit_build_times_init(cbt); + + /* We don't support decreasing the table size yet */ + tor_assert(state->TotalBuildTimes <= NCIRCUITS_TO_OBSERVE); + + for (line = state->BuildtimeHistogram; line; line = line->next) { + smartlist_t *args = smartlist_create(); + smartlist_split_string(args, line->value, " ", + SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0); + if (smartlist_len(args) < 2) { + *msg = tor_strdup("Unable to parse circuit build times: " + "Too few arguments to CircuitBuildTime"); + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + break; + } else { + const char *ms_str = smartlist_get(args,0); + const char *count_str = smartlist_get(args,1); + uint32_t count, k; + build_time_t ms; + int ok; + ms = (build_time_t)tor_parse_ulong(ms_str, 0, 0, + BUILD_TIME_MAX, &ok, NULL); + if (!ok) { + *msg = tor_strdup("Unable to parse circuit build times: " + "Unparsable bin number"); + break; + } + count = (uint32_t)tor_parse_ulong(count_str, 0, 0, + UINT32_MAX, &ok, NULL); + if (!ok) { + *msg = tor_strdup("Unable to parse circuit build times: " + "Unparsable bin count"); + break; + } + + for (k = 0; k < count; k++) { + circuit_build_times_add_time(cbt, ms); + } + N++; + SMARTLIST_FOREACH(args, char*, cp, tor_free(cp)); + smartlist_free(args); + } + + } + + circuit_build_times_shuffle_array(cbt); + + /* Verify that we didn't overwrite any indexes */ + for (i=0; i < NCIRCUITS_TO_OBSERVE; i++) { + if (!cbt->circuit_build_times[i]) + break; + tot_values++; + } + log_info(LD_CIRC, + "Loaded %d/%d values from %d lines in circuit time histogram", + tot_values, cbt->total_build_times, N); + tor_assert(cbt->total_build_times == state->TotalBuildTimes); + tor_assert(tot_values == cbt->total_build_times); + circuit_build_times_set_timeout(cbt); + return *msg ? -1 : 0; +} + +/** + * Estimates the Xm and Alpha parameters using + * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation + * + * The notable difference is that we use mode instead of min to estimate Xm. + * This is because our distribution is frechet-like. We claim this is + * an acceptable approximation because we are only concerned with the + * accuracy of the CDF of the tail. + */ +void +circuit_build_times_update_alpha(circuit_build_times_t *cbt) +{ + build_time_t *x=cbt->circuit_build_times; + double a = 0; + int n=0,i=0; + + /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */ + /* We sort of cheat here and make our samples slightly more pareto-like + * and less frechet-like. */ + cbt->Xm = circuit_build_times_mode(cbt); + + for (i=0; i< NCIRCUITS_TO_OBSERVE; i++) { + if (!x[i]) { + continue; + } + + if (x[i] < cbt->Xm) { + a += ln(cbt->Xm); + } else { + a += ln(x[i]); + } + n++; + } + + if (n!=cbt->total_build_times) { + log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n, + cbt->total_build_times); + } + tor_assert(n==cbt->total_build_times); + + a -= n*ln(cbt->Xm); + a = n/a; + + cbt->alpha = a; +} + +/** + * This is the Pareto Quantile Function. It calculates the point x + * in the distribution such that F(x) = quantile (ie quantile*100% + * of the mass of the density function is below x on the curve). + * + * We use it to calculate the timeout and also to generate synthetic + * values of time for circuits that timeout before completion. + * + * See http://en.wikipedia.org/wiki/Quantile_function, + * http://en.wikipedia.org/wiki/Inverse_transform_sampling and + * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_ + * random_sample_from_Pareto_distribution + * That's right. I'll cite wikipedia all day long. + */ +double +circuit_build_times_calculate_timeout(circuit_build_times_t *cbt, + double quantile) +{ + double ret; + tor_assert(quantile >= 0); + tor_assert(1.0-quantile > 0); + tor_assert(cbt->Xm > 0); + + ret = cbt->Xm/pow(1.0-quantile,1.0/cbt->alpha); + if (ret > INT32_MAX) { + ret = INT32_MAX; + } + tor_assert(ret > 0); + return ret; +} + +/** Pareto CDF */ +double +circuit_build_times_cdf(circuit_build_times_t *cbt, double x) +{ + double ret; + tor_assert(cbt->Xm > 0); + ret = 1.0-pow(cbt->Xm/x,cbt->alpha); + tor_assert(0 <= ret && ret <= 1.0); + return ret; +} + +/** + * Generate a synthetic time using our distribution parameters. + * + * The return value will be between q_lo and q_hi quantile points + * on the CDF. + */ +build_time_t +circuit_build_times_generate_sample(circuit_build_times_t *cbt, + double q_lo, double q_hi) +{ + uint64_t r = crypto_rand_uint64(UINT64_MAX-1); + build_time_t ret; + double u; + + tor_assert(q_lo >= 0); + tor_assert(q_hi < 1); + + u = q_lo + ((q_hi-q_lo)*r)/(1.0*UINT64_MAX); + + tor_assert(0 <= u && u < 1.0); + /* circuit_build_times_calculate_timeout returns <= INT32_MAX */ + ret = (uint32_t)lround(circuit_build_times_calculate_timeout(cbt, u)); + tor_assert(ret > 0); + return ret; +} + +/** Generate points in [cutoff, 1.0) on the CDF. */ +void +circuit_build_times_add_timeout_worker(circuit_build_times_t *cbt, + double quantile_cutoff) +{ + build_time_t gentime = circuit_build_times_generate_sample(cbt, + quantile_cutoff, MAX_SYNTHETIC_QUANTILE); + + if (gentime < (build_time_t)cbt->timeout*1000) { + log_warn(LD_CIRC, + "Generated a synthetic timeout LESS than the current timeout: " + "%u vs %d using Xm: %d a: %lf, q: %lf", + gentime, cbt->timeout*1000, cbt->Xm, cbt->alpha, quantile_cutoff); + } else if (gentime > BUILD_TIME_MAX) { + gentime = BUILD_TIME_MAX; + log_info(LD_CIRC, + "Generated a synthetic timeout larger than the max: %u", + gentime); + } else { + log_info(LD_CIRC, "Generated synthetic circuit build time %u for timeout", + gentime); + } + + circuit_build_times_add_time(cbt, gentime); +} + +/** + * Estimate an initial alpha parameter by solving the quantile + * function with a quantile point and a specific timeout value. + */ +void +circuit_build_times_initial_alpha(circuit_build_times_t *cbt, + double quantile, build_time_t timeout) +{ + // Q(u) = Xm/((1-u)^(1/a)) + // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout + // CircBuildTimeout = Xm/((1-0.8))^(1/a)) + // CircBuildTimeout = Xm*((1-0.8))^(-1/a)) + // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a) + // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a + tor_assert(quantile > 0); + tor_assert(cbt->Xm > 0); + cbt->alpha = ln(1.0-quantile)/(ln(cbt->Xm)-ln(timeout)); + tor_assert(cbt->alpha > 0); +} + +/** + * Generate synthetic timeout values for the timeouts + * that have happened before we estimated our parameters. + */ +static void +circuit_build_times_count_pretimeouts(circuit_build_times_t *cbt) +{ + /* Store a timeout as a random position past the current + * cutoff on the pareto curve */ + if (cbt->pre_timeouts) { + double timeout_quantile = 1.0- + ((double)cbt->pre_timeouts)/ + (cbt->pre_timeouts+cbt->total_build_times); + cbt->Xm = circuit_build_times_min(cbt); + tor_assert(cbt->Xm > 0); + // Use current timeout to get an estimate on alpha + circuit_build_times_initial_alpha(cbt, timeout_quantile, + cbt->timeout*1000); + while (cbt->pre_timeouts-- != 0) { + circuit_build_times_add_timeout_worker(cbt, timeout_quantile); + } + cbt->pre_timeouts = 0; + } +} + +/** + * Returns true if we need circuits to be built + */ +int +circuit_build_times_needs_circuits(circuit_build_times_t *cbt) +{ + /* Return true if < MIN_CIRCUITS_TO_OBSERVE */ + if (cbt->total_build_times < MIN_CIRCUITS_TO_OBSERVE) + return 1; + return 0; +} + +/** + * Returns true if we should build a timeout test circuit + * right now. + */ +int +circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt) +{ + return circuit_build_times_needs_circuits(cbt) && + approx_time()-cbt->last_circ_at > BUILD_TIMES_TEST_FREQUENCY; +} + +/** + * Called to indicate that the network showed some signs of liveness. + */ +void +circuit_build_times_network_is_live(circuit_build_times_t *cbt) +{ + cbt->network_last_live = approx_time(); +} + +/** + * Returns true if the network showed some sign of liveness + * in the past NETWORK_LIVE_MULTIPLIER*cbt->timeout seconds. + */ +int +circuit_build_times_is_network_live(circuit_build_times_t *cbt) +{ + time_t now = approx_time(); + if (now - cbt->network_last_live > + (cbt->timeout*NETWORK_LIVE_MULTIPLIER)) { + log_info(LD_CIRC, "Network is no longer live. Dead for %ld seconds.", + now - cbt->network_last_live); + return 0; + } + return 1; +} + +/** + * Returns true if we have seen more than MAX_RECENT_TIMEOUT_RATE of + * the past RECENT_CIRCUITS time out. Used to detect if the network + * connection has changed significantly. + * + * Also resets the entire timeout history in this case and causes us + * to restart the process of building test circuits and estimating a + * new timeout. + */ +int +circuit_build_times_check_too_many_timeouts(circuit_build_times_t *cbt) +{ + double timeout_rate=0; + build_time_t Xm = BUILD_TIME_MAX; + double timeout; + int i; + + if ((cbt->pre_timeouts + cbt->total_build_times) < RECENT_CIRCUITS) { + return 0; + } + + /* Get timeout rate and Xm for recent circs */ + for (i = (cbt->build_times_idx - RECENT_CIRCUITS) % NCIRCUITS_TO_OBSERVE; + i != cbt->build_times_idx; + i = (i + 1) % NCIRCUITS_TO_OBSERVE) { + if (cbt->circuit_build_times[i] && cbt->circuit_build_times[i] < Xm) { + Xm = cbt->circuit_build_times[i]; + } + if (cbt->circuit_build_times[i] > (build_time_t)cbt->timeout*1000) { + timeout_rate++; + } + } + timeout_rate += cbt->pre_timeouts; + timeout_rate /= RECENT_CIRCUITS; + + /* If more than 80% of our recent circuits are timing out, + * we need to re-estimate a new initial alpha and timeout */ + if (timeout_rate < MAX_RECENT_TIMEOUT_RATE) { + return 0; + } + + log_notice(LD_CIRC, + "Network connection speed appears to have changed. " + "Resetting timeouts after %d pretimouts and %d buildtimes", + cbt->pre_timeouts, cbt->total_build_times); + + if (Xm >= (build_time_t)cbt->timeout*1000) { + Xm = circuit_build_times_min(cbt); + if (Xm >= (build_time_t)cbt->timeout*1000) { + /* No circuits have completed */ + cbt->timeout *= 2; + log_warn(LD_CIRC, + "Adjusting CircuitBuildTimeout to %d in the hopes that " + "some connections will succeed", cbt->timeout); + goto reset; + } + } + tor_assert(Xm > 0); + cbt->Xm = Xm; + + circuit_build_times_initial_alpha(cbt, 1.0-timeout_rate, + cbt->timeout*1000); + + timeout = circuit_build_times_calculate_timeout(cbt, + BUILDTIMEOUT_QUANTILE_CUTOFF); + /* timeout is INT32_MAX at most */ + cbt->timeout = (uint32_t)lround(timeout/1000.0); + + if (cbt->timeout < BUILD_TIMEOUT_MIN_VALUE) { + log_warn(LD_CIRC, "Reset buildtimeout to low value %lf. Setting to %d", + timeout, BUILD_TIMEOUT_MIN_VALUE); + cbt->timeout = BUILD_TIMEOUT_MIN_VALUE; + } + + log_notice(LD_CIRC, + "Reset circuit build timeout to %d (%lf, Xm: %d, a: %lf) based " + "on %d recent circuit times", cbt->timeout, timeout, cbt->Xm, + cbt->alpha, RECENT_CIRCUITS); + +reset: + + /* Reset all data */ + circuit_build_times_reset(cbt); + return 1; +} + +/** + * Store a timeout as a synthetic value + */ +void +circuit_build_times_add_timeout(circuit_build_times_t *cbt) +{ + /* Only count timeouts if network is live.. */ + if (!circuit_build_times_is_network_live(cbt)) { + return; + } + + /* If there are a ton of timeouts, we should reduce + * the circuit build timeout */ + if (circuit_build_times_check_too_many_timeouts(cbt)) { + return; + } + + if (!cbt->have_computed_timeout) { + /* Store a timeout before we have enough data as special */ + cbt->pre_timeouts++; + return; + } + + circuit_build_times_count_pretimeouts(cbt); + circuit_build_times_add_timeout_worker(cbt, BUILDTIMEOUT_QUANTILE_CUTOFF); +} + +/** + * Estimate a new timeout based on history and set our timeout + * variable accordingly. + */ +void +circuit_build_times_set_timeout(circuit_build_times_t *cbt) +{ + double timeout; + + if (cbt->total_build_times < MIN_CIRCUITS_TO_OBSERVE) { + log_info(LD_CIRC, + "Not enough circuits yet to calculate a new build timeout." + " Need %d more.", + MIN_CIRCUITS_TO_OBSERVE-cbt->total_build_times); + return; + } + + circuit_build_times_count_pretimeouts(cbt); + circuit_build_times_update_alpha(cbt); + timeout = circuit_build_times_calculate_timeout(cbt, + BUILDTIMEOUT_QUANTILE_CUTOFF); + + cbt->have_computed_timeout = 1; + /* timeout is INT32_MAX at most */ + cbt->timeout = (uint32_t)lround(timeout/1000.0); + + if (cbt->timeout < BUILD_TIMEOUT_MIN_VALUE) { + log_warn(LD_CIRC, "Set buildtimeout to low value %lf. Setting to %d", + timeout, BUILD_TIMEOUT_MIN_VALUE); + cbt->timeout = BUILD_TIMEOUT_MIN_VALUE; + } + + log_info(LD_CIRC, + "Set circuit build timeout to %d (%lf, Xm: %d, a: %lf) based on " + "%d circuit times", cbt->timeout, timeout, cbt->Xm, cbt->alpha, + cbt->total_build_times); + +} + /** 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. @@ -641,8 +1377,16 @@ circuit_send_next_onion_skin(origin_circuit_t *circ) log_debug(LD_CIRC,"starting to send subsequent skin."); hop = onion_next_hop_in_cpath(circ->cpath); if (!hop) { + struct timeval end; + long timediff; + tor_gettimeofday(&end); + timediff = tv_mdiff(&circ->_base.highres_created, &end); + if (timediff > INT32_MAX) + timediff = INT32_MAX; /* done building the circuit. whew. */ circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN); + circuit_build_times_add_time(&circ_times, (uint32_t)timediff); + circuit_build_times_set_timeout(&circ_times); log_info(LD_CIRC,"circuit built!"); circuit_reset_failure_count(0); if (circ->build_state->onehop_tunnel) |