[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[or-cvs] [tor/master] Recover from changing network connections.
Author: Mike Perry <mikeperry-git@xxxxxxxxxx>
Date: Mon, 31 Aug 2009 18:10:27 -0700
Subject: Recover from changing network connections.
Commit: 7ac9a66c8fb2ec369a7f99cc502200406f3760b2
Also add code to keep creating circuits every minute until we
hit our minimum threshhold.
---
src/or/circuitbuild.c | 125 ++++++++++++++++++++++++++++++++++++++++++++++--
src/or/circuituse.c | 21 ++++++++-
src/or/connection_or.c | 5 ++
src/or/or.h | 24 +++++++--
src/or/test.c | 25 ++++++++++
5 files changed, 188 insertions(+), 12 deletions(-)
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index b0bc840..a9ae139 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -97,6 +97,8 @@ circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
log_err(LD_CIRC, "Circuit build time is %u!", time);
return -1;
}
+
+ cbt->last_circ_at = approx_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)
@@ -322,7 +324,7 @@ circuit_build_times_generate_sample(circuit_build_times_t *cbt,
return ret;
}
-static void
+void
circuit_build_times_add_timeout_worker(circuit_build_times_t *cbt)
{
/* Generate 0.8-1.0... */
@@ -377,15 +379,128 @@ circuit_build_times_count_pretimeouts(circuit_build_times_t *cbt)
}
/**
+ * 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;
+}
+
+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;
+}
+
+void
+circuit_build_times_network_is_live(circuit_build_times_t *cbt)
+{
+ cbt->network_last_live = approx_time();
+}
+
+int
+circuit_build_times_is_network_live(circuit_build_times_t *cbt)
+{
+ time_t now = approx_time();
+ if (now - cbt->network_last_live > NETWORK_LIVE_INTERVAL)
+ return 0;
+ return 1;
+}
+
+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->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] < Xm) {
+ Xm = cbt->circuit_build_times[i];
+ }
+ if (cbt->circuit_build_times[i] >
+ (build_time_t)get_options()->CircuitBuildTimeout*1000) {
+ timeout_rate++;
+ }
+ }
+ timeout_rate /= RECENT_CIRCUITS;
+
+ /* If more then 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 type appears to have changed. "
+ "Resetting timeouts.");
+
+ if (Xm >= (build_time_t)get_options()->CircuitBuildTimeout*1000) {
+ Xm = circuit_build_times_min(cbt);
+ if (Xm >= (build_time_t)get_options()->CircuitBuildTimeout*1000) {
+ /* No circuits have completed */
+ get_options()->CircuitBuildTimeout *= 2;
+ log_warn(LD_CIRC,
+ "Adjusting CircuitBuildTimeout to %d in the hopes that "
+ "some connections will succeed",
+ get_options()->CircuitBuildTimeout);
+ goto reset;
+ }
+ }
+ cbt->Xm = Xm;
+
+ circuit_build_times_initial_alpha(cbt, 1.0-timeout_rate,
+ get_options()->CircuitBuildTimeout*1000.0);
+
+ timeout = circuit_build_times_calculate_timeout(cbt,
+ BUILDTIMEOUT_QUANTILE_CUTOFF);
+
+ get_options()->CircuitBuildTimeout = lround(timeout/1000.0);
+
+ log_notice(LD_CIRC,
+ "Set circuit build timeout to %d based on %d recent circuit times",
+ get_options()->CircuitBuildTimeout, 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;
+ return 1;
+}
+
+/**
* Store a timeout as a synthetic value
*/
void
circuit_build_times_add_timeout(circuit_build_times_t *cbt)
{
- /* XXX: If there are a ton of timeouts, we should reduce
- * the circuit build timeout by like 2X or something...
- * But then how do we differentiate between that and network
- * failure? */
+ /* 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->total_build_times < MIN_CIRCUITS_TO_OBSERVE) {
/* Store a timeout before we have enough data as special */
cbt->pre_timeouts++;
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index e93d28d..844ea72 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -519,6 +519,15 @@ circuit_predict_and_launch_new(void)
circuit_launch_by_router(CIRCUIT_PURPOSE_C_GENERAL, NULL, flags);
return;
}
+
+ /* Finally, check to see if we still need more circuits to learn
+ * a good build timeout */
+ if (circuit_build_times_needs_circuits_now(&circ_times)) {
+ flags = CIRCLAUNCH_NEED_CAPACITY;
+ log_info(LD_CIRC,
+ "Have %d clean circs need another buildtime test circ.", num);
+ circuit_launch_by_router(CIRCUIT_PURPOSE_C_GENERAL, NULL, flags);
+ }
}
/** Build a new test circuit every 5 minutes */
@@ -633,7 +642,15 @@ static void
circuit_expire_old_circuits(time_t now)
{
circuit_t *circ;
- time_t cutoff = now - get_options()->CircuitIdleTimeout;
+ time_t cutoff;
+
+ if (circuit_build_times_needs_circuits(&circ_times)) {
+ /* Circuits should be shorter lived if we need them
+ * for build time testing */
+ cutoff = now - get_options()->MaxCircuitDirtiness;
+ } else {
+ cutoff = now - get_options()->CircuitIdleTimeout;
+ }
for (circ = global_circuitlist; circ; circ = circ->next) {
if (circ->marked_for_close || ! CIRCUIT_IS_ORIGIN(circ))
@@ -840,6 +857,7 @@ circuit_build_failed(origin_circuit_t *circ)
break;
case CIRCUIT_PURPOSE_C_INTRODUCING:
/* at Alice, connecting to intro point */
+ circuit_increment_failure_count();
/* Don't increment failure count, since Bob may have picked
* the introduction point maliciously */
/* Alice will pick a new intro point when this one dies, if
@@ -853,6 +871,7 @@ circuit_build_failed(origin_circuit_t *circ)
break;
case CIRCUIT_PURPOSE_S_CONNECT_REND:
/* at Bob, connecting to rend point */
+ circuit_increment_failure_count();
/* Don't increment failure count, since Alice may have picked
* the rendezvous point maliciously */
log_info(LD_REND,
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 8c8b549..aa26bf8 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -1036,6 +1036,8 @@ connection_tls_finish_handshake(or_connection_t *conn)
digest_rcvd) < 0)
return -1;
+ circuit_build_times_network_is_live(&circ_times);
+
if (tor_tls_used_v1_handshake(conn->tls)) {
conn->link_proto = 1;
if (!started_here) {
@@ -1087,6 +1089,7 @@ connection_or_set_state_open(or_connection_t *conn)
control_event_or_conn_status(conn, OR_CONN_EVENT_CONNECTED, 0);
if (started_here) {
+ circuit_build_times_network_is_live(&circ_times);
rep_hist_note_connect_succeeded(conn->identity_digest, now);
if (entry_guard_register_connect_status(conn->identity_digest,
1, 0, now) < 0) {
@@ -1187,6 +1190,7 @@ connection_or_process_cells_from_inbuf(or_connection_t *conn)
if (connection_fetch_var_cell_from_buf(conn, &var_cell)) {
if (!var_cell)
return 0; /* not yet. */
+ circuit_build_times_network_is_live(&circ_times);
command_process_var_cell(var_cell, conn);
var_cell_free(var_cell);
} else {
@@ -1196,6 +1200,7 @@ connection_or_process_cells_from_inbuf(or_connection_t *conn)
available? */
return 0; /* not yet */
+ circuit_build_times_network_is_live(&circ_times);
connection_fetch_from_buf(buf, CELL_NETWORK_SIZE, TO_CONN(conn));
/* retrieve cell info from buf (create the host-order struct from the
diff --git a/src/or/or.h b/src/or/or.h
index 13626c4..809e385 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -2857,24 +2857,30 @@ void bridges_retry_all(void);
void entry_guards_free_all(void);
-/* Circuit Build Timeout "public" functions and structures.
- * (I love C... No wait.) */
-
-// XXX: Do we want to artifically tweak CircuitIdleTimeout and
-// the number of circuits we build at a time if < MIN here?
+/* Circuit Build Timeout "public" functions and structures. */
+#define RECENT_CIRCUITS 20
#define MIN_CIRCUITS_TO_OBSERVE 500
#define NCIRCUITS_TO_OBSERVE 5000 /* approx 1.5 weeks worth of circuits */
#define BUILDTIME_BIN_WIDTH 50
+#define MAX_RECENT_TIMEOUT_RATE 0.80
+
/* TODO: This should be moved to the consensus */
#define BUILDTIMEOUT_QUANTILE_CUTOFF 0.8
typedef uint32_t build_time_t;
#define BUILD_TIME_MAX ((build_time_t)(INT32_MAX))
+/* Have we recieved a cell in the last 90 seconds? */
+#define NETWORK_LIVE_INTERVAL 90
+
+/* How often in seconds should we build a test circuit */
+#define BUILD_TIMES_TEST_FREQUENCY 60
+
typedef struct {
- // XXX: Make this a smartlist..
build_time_t circuit_build_times[NCIRCUITS_TO_OBSERVE];
+ time_t network_last_live;
+ time_t last_circ_at;
int build_times_idx;
int total_build_times;
int pre_timeouts;
@@ -2891,6 +2897,10 @@ void circuit_build_times_add_timeout(circuit_build_times_t *cbt);
void circuit_build_times_set_timeout(circuit_build_times_t *cbt);
int circuit_build_times_add_time(circuit_build_times_t *cbt,
build_time_t time);
+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);
#ifdef CIRCUIT_PRIVATE
double circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
@@ -2901,6 +2911,8 @@ void circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
double quantile, build_time_t time);
void circuit_build_times_update_alpha(circuit_build_times_t *cbt);
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);
#endif
/********************************* circuitlist.c ***********************/
diff --git a/src/or/test.c b/src/or/test.c
index ea8ce86..c6cd6a8 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -3450,6 +3450,7 @@ test_circuit_timeout(void)
timeout1 = circuit_build_times_calculate_timeout(&estimate,
BUILDTIMEOUT_QUANTILE_CUTOFF);
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) -
circuit_build_times_cdf(&initial, timeout1)) > 0.05
/* 5% error */
@@ -3468,6 +3469,30 @@ test_circuit_timeout(void)
test_assert(fabs(circuit_build_times_cdf(&initial, timeout0) -
circuit_build_times_cdf(&initial, timeout2)) < 0.05);
+ /* Generate MAX_RECENT_TIMEOUT_RATE*RECENT_CIRCUITS timeouts
+ * and 1-that regular values. Then check for timeout error
+ * Do the same for one less timeout */
+ for (i = 0; i < RECENT_CIRCUITS; i++) {
+ circuit_build_times_add_time(&estimate,
+ circuit_build_times_generate_sample(&estimate, 0,
+ BUILDTIMEOUT_QUANTILE_CUTOFF));
+ circuit_build_times_add_time(&final,
+ 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));
+
+ for (i = 0; i < MAX_RECENT_TIMEOUT_RATE*RECENT_CIRCUITS; i++) {
+ circuit_build_times_add_timeout_worker(&estimate);
+ if (i < MAX_RECENT_TIMEOUT_RATE*RECENT_CIRCUITS-1) {
+ circuit_build_times_add_timeout_worker(&final);
+ }
+ }
+
+ test_assert(circuit_build_times_check_too_many_timeouts(&estimate));
+ test_assert(!circuit_build_times_check_too_many_timeouts(&final));
+
done:
return;
}
--
1.5.6.5