summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/or/circuitbuild.c144
-rw-r--r--src/or/circuituse.c4
-rw-r--r--src/or/config.c6
-rw-r--r--src/or/or.h12
-rw-r--r--src/or/test.c16
5 files changed, 121 insertions, 61 deletions
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index d3f95254c6..b1c377a82e 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -86,6 +86,8 @@ static smartlist_t *entry_guards = NULL;
* and those changes need to be flushed to disk. */
static int entry_guards_dirty = 0;
+static int unit_tests = 0;
+
/********* END VARIABLES ************/
static int circuit_deliver_create_cell(circuit_t *circ,
@@ -99,6 +101,34 @@ 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);
+void
+circuitbuild_running_unit_tests(void)
+{
+ unit_tests = 1;
+}
+
+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->computed = 0;
+}
+
+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;
+ } else {
+ cbt->timeout = BUILD_TIMEOUT_INITIAL_VALUE;
+ }
+}
+
/**
* circuit_build_times is a circular array, so loop around when
* array is full
@@ -124,7 +154,7 @@ circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
if ((cbt->total_build_times % BUILD_TIMES_SAVE_STATE_EVERY) == 0) {
/* Save state every 100 circuit builds */
- if (!get_options()->AvoidDiskWrites)
+ if (!unit_tests && !get_options()->AvoidDiskWrites)
or_state_mark_dirty(get_or_state(), 0);
}
@@ -205,15 +235,13 @@ circuit_build_times_mode(circuit_build_times_t *cbt)
/**
* output a histogram of current circuit build times.
*
- * XXX: Is do_unit the right way to do this unit test
- * noise?
*/
void
circuit_build_times_update_state(circuit_build_times_t *cbt,
- or_state_t *state, int do_unit)
+ or_state_t *state)
{
uint32_t *histogram;
- int i = 0;
+ build_time_t i = 0;
build_time_t nbins = 0;
config_line_t **next, *line;
@@ -225,11 +253,7 @@ circuit_build_times_update_state(circuit_build_times_t *cbt,
state->TotalBuildTimes = cbt->total_build_times;
- /* Write the bins in reverse so that on startup, the faster
- times are at the end. This is needed because of
- the checks in circuit_build_times_check_too_many_timeouts()
- which check the end of the array for recent values */
- for (i = nbins-1; i >= 0; i--) {
+ 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));
@@ -240,7 +264,7 @@ circuit_build_times_update_state(circuit_build_times_t *cbt,
next = &(line->next);
}
- if (!do_unit) {
+ if (!unit_tests) {
if (!get_options()->AvoidDiskWrites)
or_state_mark_dirty(get_or_state(), 0);
}
@@ -248,15 +272,35 @@ circuit_build_times_update_state(circuit_build_times_t *cbt,
if (histogram) tor_free(histogram);
}
+/* 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 state */
int
circuit_build_times_parse_state(circuit_build_times_t *cbt,
or_state_t *state, char **msg)
{
- int tot_values = 0, lines = 0;
+ int tot_values = 0, N = 0;
config_line_t *line;
+ int i;
msg = NULL;
- memset(cbt, 0, sizeof(*cbt));
+ 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();
@@ -269,7 +313,7 @@ circuit_build_times_parse_state(circuit_build_times_t *cbt,
} else {
const char *ms_str = smartlist_get(args,0);
const char *count_str = smartlist_get(args,1);
- uint32_t count, i;
+ uint32_t count, k;
build_time_t ms;
int ok;
ms = tor_parse_ulong(ms_str, 0, 0, BUILD_TIME_MAX, &ok, NULL);
@@ -284,15 +328,27 @@ circuit_build_times_parse_state(circuit_build_times_t *cbt,
"Unparsable bin count");
break;
}
- lines++;
- for (i = 0; i < count; i++) {
+
+ for (k = 0; k < count; k++) {
circuit_build_times_add_time(cbt, ms);
- tot_values++;
}
+ N++;
}
}
- log_info(LD_CIRC, "Loaded %d values from %d lines in circuit time histogram",
- tot_values, lines);
+
+ 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);
}
@@ -368,8 +424,8 @@ build_time_t
circuit_build_times_generate_sample(circuit_build_times_t *cbt,
double q_lo, double q_hi)
{
- uint32_t r = crypto_rand_int(UINT32_MAX-1);
- double u = q_lo + ((q_hi-q_lo)*r)/(1.0*UINT32_MAX);
+ uint64_t r = crypto_rand_uint64(UINT64_MAX-1);
+ double u = q_lo + ((q_hi-q_lo)*r)/(1.0*UINT64_MAX);
build_time_t ret;
tor_assert(0 <= u && u < 1.0);
@@ -386,12 +442,11 @@ circuit_build_times_add_timeout_worker(circuit_build_times_t *cbt,
build_time_t gentime = circuit_build_times_generate_sample(cbt,
quantile_cutoff, 1.0);
- if (gentime < (build_time_t)get_options()->CircuitBuildTimeout*1000) {
+ if (gentime < (build_time_t)cbt->timeout*1000) {
log_warn(LD_CIRC,
"Generated a synthetic timeout LESS than the current timeout: %u vs %d",
- gentime, get_options()->CircuitBuildTimeout*1000);
- tor_assert(gentime >=
- (build_time_t)get_options()->CircuitBuildTimeout*1000);
+ gentime, cbt->timeout*1000);
+ tor_assert(gentime >= (build_time_t)cbt->timeout*1000);
} else if (gentime > BUILD_TIME_MAX) {
gentime = BUILD_TIME_MAX;
log_info(LD_CIRC,
@@ -426,7 +481,7 @@ circuit_build_times_count_pretimeouts(circuit_build_times_t *cbt)
cbt->Xm = circuit_build_times_min(cbt);
// Use current timeout to get an estimate on alpha
circuit_build_times_initial_alpha(cbt, timeout_quantile,
- get_options()->CircuitBuildTimeout*1000);
+ cbt->timeout*1000);
while (cbt->pre_timeouts-- != 0) {
circuit_build_times_add_timeout_worker(cbt, timeout_quantile);
}
@@ -487,11 +542,10 @@ circuit_build_times_check_too_many_timeouts(circuit_build_times_t *cbt)
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] < Xm) {
+ 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)get_options()->CircuitBuildTimeout*1000) {
+ if (cbt->circuit_build_times[i] > (build_time_t)cbt->timeout*1000) {
timeout_rate++;
}
}
@@ -507,42 +561,36 @@ circuit_build_times_check_too_many_timeouts(circuit_build_times_t *cbt)
"Network connection type appears to have changed. "
"Resetting timeouts.");
- if (Xm >= (build_time_t)get_options()->CircuitBuildTimeout*1000) {
+ if (Xm >= (build_time_t)cbt->timeout*1000) {
Xm = circuit_build_times_min(cbt);
- if (Xm >= (build_time_t)get_options()->CircuitBuildTimeout*1000) {
+ if (Xm >= (build_time_t)cbt->timeout*1000) {
/* No circuits have completed */
- get_options()->CircuitBuildTimeout *= 2;
+ cbt->timeout *= 2;
log_warn(LD_CIRC,
"Adjusting CircuitBuildTimeout to %d in the hopes that "
- "some connections will succeed",
- get_options()->CircuitBuildTimeout);
+ "some connections will succeed", cbt->timeout);
goto reset;
}
}
cbt->Xm = Xm;
circuit_build_times_initial_alpha(cbt, 1.0-timeout_rate,
- get_options()->CircuitBuildTimeout*1000.0);
+ cbt->timeout*1000.0);
timeout = circuit_build_times_calculate_timeout(cbt,
BUILDTIMEOUT_QUANTILE_CUTOFF);
- get_options()->CircuitBuildTimeout = lround(timeout/1000.0);
+ cbt->timeout = lround(timeout/1000.0);
log_notice(LD_CIRC,
"Reset circuit build timeout to %d (Xm: %d a: %lf) based on "
- "%d recent circuit times",
- get_options()->CircuitBuildTimeout, cbt->Xm, cbt->alpha,
+ "%d recent circuit times", cbt->timeout, cbt->Xm, cbt->alpha,
RECENT_CIRCUITS);
reset:
- /* Reset all data. Do we need a constructor? */
- 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->estimated = 0;
+ /* Reset all data */
+ circuit_build_times_reset(cbt);
return 1;
}
@@ -563,7 +611,7 @@ circuit_build_times_add_timeout(circuit_build_times_t *cbt)
return;
}
- if (!cbt->estimated) {
+ if (!cbt->computed) {
/* Store a timeout before we have enough data as special */
cbt->pre_timeouts++;
return;
@@ -591,13 +639,13 @@ circuit_build_times_set_timeout(circuit_build_times_t *cbt)
timeout = circuit_build_times_calculate_timeout(cbt,
BUILDTIMEOUT_QUANTILE_CUTOFF);
- cbt->estimated = 1;
- get_options()->CircuitBuildTimeout = lround(timeout/1000.0);
+ cbt->computed = 1;
+ cbt->timeout = lround(timeout/1000.0);
log_info(LD_CIRC,
"Set circuit build timeout to %d (Xm: %d a: %lf) based on "
"%d circuit times",
- get_options()->CircuitBuildTimeout, cbt->Xm, cbt->alpha,
+ cbt->timeout, cbt->Xm, cbt->alpha,
cbt->total_build_times);
}
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index d53cb198a2..4162790ec3 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -264,8 +264,8 @@ void
circuit_expire_building(time_t now)
{
circuit_t *victim, *circ = global_circuitlist;
- time_t general_cutoff = now - get_options()->CircuitBuildTimeout;
- time_t begindir_cutoff = now - get_options()->CircuitBuildTimeout/2;
+ time_t general_cutoff = now - circ_times.timeout;
+ time_t begindir_cutoff = now - circ_times.timeout/2;
time_t introcirc_cutoff = begindir_cutoff;
cpath_build_state_t *build_state;
diff --git a/src/or/config.c b/src/or/config.c
index 45ce5cf13b..1505dc3e4e 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -164,7 +164,7 @@ static config_var_t _option_vars[] = {
V(BridgeRecordUsageByCountry, BOOL, "1"),
V(BridgeRelay, BOOL, "0"),
V(CellStatistics, BOOL, "0"),
- V(CircuitBuildTimeout, INTERVAL, "1 minute"),
+ V(CircuitBuildTimeout, INTERVAL, "0"),
V(CircuitIdleTimeout, INTERVAL, "1 hour"),
V(ClientDNSRejectInternalAddresses, BOOL,"1"),
V(ClientOnly, BOOL, "0"),
@@ -2922,7 +2922,7 @@ compute_publishserverdescriptor(or_options_t *options)
/** Lowest allowable value for CircuitBuildTimeout; values too low will
* increase network load because of failing connections being retried, and
* might prevent users from connecting to the network at all. */
-#define MIN_CIRCUIT_BUILD_TIMEOUT 5
+#define MIN_CIRCUIT_BUILD_TIMEOUT 3
/** Lowest allowable value for MaxCircuitDirtiness; if this is too low, Tor
* will generate too many circuits and potentially overload the network. */
@@ -5207,7 +5207,7 @@ or_state_save(time_t now)
* to avoid redundant writes. */
entry_guards_update_state(global_state);
rep_hist_update_state(global_state);
- circuit_build_times_update_state(&circ_times, global_state, 0);
+ circuit_build_times_update_state(&circ_times, global_state);
if (accounting_is_enabled(get_options()))
accounting_run_housekeeping(now);
diff --git a/src/or/or.h b/src/or/or.h
index 66db091e5e..6f4ad4516d 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -2863,7 +2863,7 @@ void entry_guards_free_all(void);
#define NCIRCUITS_TO_OBSERVE 5000 /* approx 1.5 weeks worth of circuits */
#define BUILDTIME_BIN_WIDTH 50
-#define MAX_RECENT_TIMEOUT_RATE 0.80
+#define MAX_RECENT_TIMEOUT_RATE 0.7999999
/* TODO: This should be moved to the consensus */
#define BUILDTIMEOUT_QUANTILE_CUTOFF 0.8
@@ -2874,6 +2874,8 @@ typedef uint32_t build_time_t;
/* Have we recieved a cell in the last 90 seconds? */
#define NETWORK_LIVE_INTERVAL 90
+#define BUILD_TIMEOUT_INITIAL_VALUE 60
+
/* How often in seconds should we build a test circuit */
#define BUILD_TIMES_TEST_FREQUENCY 60
@@ -2889,12 +2891,13 @@ typedef struct {
int pre_timeouts;
build_time_t Xm;
double alpha;
- int estimated;
+ int computed;
+ int timeout;
} circuit_build_times_t;
extern circuit_build_times_t circ_times;
void circuit_build_times_update_state(circuit_build_times_t *cbt,
- or_state_t *state, int do_unit);
+ or_state_t *state);
int circuit_build_times_parse_state(circuit_build_times_t *cbt,
or_state_t *state, char **msg);
void circuit_build_times_add_timeout(circuit_build_times_t *cbt);
@@ -2905,6 +2908,7 @@ void circuit_build_times_network_is_live(circuit_build_times_t *cbt);
int circuit_build_times_is_network_live(circuit_build_times_t *cbt);
int circuit_build_times_needs_circuits(circuit_build_times_t *cbt);
int circuit_build_times_needs_circuits_now(circuit_build_times_t *cbt);
+void circuit_build_times_init(circuit_build_times_t *cbt);
#ifdef CIRCUIT_PRIVATE
double circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
@@ -2918,6 +2922,8 @@ double circuit_build_times_cdf(circuit_build_times_t *cbt, double x);
int circuit_build_times_check_too_many_timeouts(circuit_build_times_t *cbt);
void circuit_build_times_add_timeout_worker(circuit_build_times_t *cbt,
double quantile_cutoff);
+void circuitbuild_running_unit_tests(void);
+void circuit_build_times_reset(circuit_build_times_t *cbt);
#endif
/********************************* circuitlist.c ***********************/
diff --git a/src/or/test.c b/src/or/test.c
index a7f56fe4d1..7228425241 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -3429,11 +3429,13 @@ test_circuit_timeout(void)
int i;
char *msg;
double timeout1, timeout2;
- memset(&initial, 0, sizeof(circuit_build_times_t));
- memset(&estimate, 0, sizeof(circuit_build_times_t));
- memset(&final, 0, sizeof(circuit_build_times_t));
+ circuit_build_times_init(&initial);
+ circuit_build_times_init(&estimate);
+ circuit_build_times_init(&final);
+
memset(&state, 0, sizeof(or_state_t));
+ circuitbuild_running_unit_tests();
#define timeout0 (30*1000.0)
initial.Xm = 750;
circuit_build_times_initial_alpha(&initial, BUILDTIMEOUT_QUANTILE_CUTOFF,
@@ -3449,6 +3451,7 @@ test_circuit_timeout(void)
circuit_build_times_update_alpha(&estimate);
timeout1 = circuit_build_times_calculate_timeout(&estimate,
BUILDTIMEOUT_QUANTILE_CUTOFF);
+ circuit_build_times_set_timeout(&estimate);
log_warn(LD_CIRC, "Timeout is %lf, Xm is %d", timeout1, estimate.Xm);
/* XXX: 5% distribution error may not be the right metric */
} while (fabs(circuit_build_times_cdf(&initial, timeout0) -
@@ -3458,12 +3461,14 @@ test_circuit_timeout(void)
test_assert(estimate.total_build_times < NCIRCUITS_TO_OBSERVE);
- circuit_build_times_update_state(&estimate, &state, 1);
+ circuit_build_times_update_state(&estimate, &state);
test_assert(circuit_build_times_parse_state(&final, &state, &msg) == 0);
circuit_build_times_update_alpha(&final);
timeout2 = circuit_build_times_calculate_timeout(&final,
BUILDTIMEOUT_QUANTILE_CUTOFF);
+
+ circuit_build_times_set_timeout(&final);
log_warn(LD_CIRC, "Timeout is %lf, Xm is %d", timeout2, final.Xm);
test_assert(fabs(circuit_build_times_cdf(&initial, timeout0) -
@@ -3480,6 +3485,7 @@ test_circuit_timeout(void)
circuit_build_times_generate_sample(&final, 0,
BUILDTIMEOUT_QUANTILE_CUTOFF));
}
+
test_assert(!circuit_build_times_check_too_many_timeouts(&estimate));
test_assert(!circuit_build_times_check_too_many_timeouts(&final));
@@ -3492,7 +3498,7 @@ test_circuit_timeout(void)
}
}
- test_assert(circuit_build_times_check_too_many_timeouts(&estimate));
+ test_assert(circuit_build_times_check_too_many_timeouts(&estimate) == 1);
test_assert(!circuit_build_times_check_too_many_timeouts(&final));
done:
7apu2bq3rhoylwmucxizk54afw5jyda7pho4j5zdcqpwkufke7zdzwad.onion