[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

[or-cvs] [tor/master 20/28] Keep circuits open until the greater of 95th CDF percentile or 60s.



Author: Mike Perry <mikeperry-git@xxxxxxxxxx>
Date: Tue, 8 Jun 2010 01:01:47 -0700
Subject: Keep circuits open until the greater of 95th CDF percentile or 60s.
Commit: c96206090e5090433a7dbb4f5d52ad2efeb00c37

This is done to provide better data to our right-censored Pareto model.

We do this by simply marking them with a new purpose.
---
 src/or/circuitbuild.c |   43 +++++++++++++++++++++++++++++++++----------
 src/or/circuituse.c   |   23 ++++++++++++++++++++++-
 src/or/or.h           |   28 ++++++++++++++++++----------
 3 files changed, 73 insertions(+), 21 deletions(-)

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 7dc544d..90b4f52 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -139,6 +139,15 @@ circuit_build_times_quantile_cutoff(void)
   return num/100.0;
 }
 
+static double
+circuit_build_times_close_quantile(void)
+{
+  int32_t num = networkstatus_get_param(NULL, "cbtclosequantile",
+          CBT_DEFAULT_CLOSE_QUANTILE);
+
+  return num/100.0;
+}
+
 static int32_t
 circuit_build_times_test_frequency(void)
 {
@@ -539,7 +548,10 @@ circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
 
 /**
  * Filter old synthetic timeouts that were created before the
- * right censored new Pareto calculation was deployed.
+ * new right-censored Pareto calculation was deployed.
+ *
+ * Once all clients before 0.2.1.13-alpha are gone, this code
+ * will be unused.
  */
 static int
 circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
@@ -549,7 +561,7 @@ circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
   build_time_t max_timeout = 0;
 
   timeout_rate = circuit_build_times_timeout_rate(cbt);
-  max_timeout = (build_time_t)cbt->timeout_ms;
+  max_timeout = (build_time_t)cbt->close_ms;
 
   for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
     if (cbt->circuit_build_times[i] > max_timeout) {
@@ -1097,6 +1109,15 @@ circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
 
   cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
                                 circuit_build_times_quantile_cutoff());
+
+  cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
+                                circuit_build_times_close_quantile());
+
+  /* Sometimes really fast guard nodes give us such a steep curve
+   * that this ends up being not that much greater than timeout_ms.
+   * Make it be at least 1 min to handle this case. */
+  cbt->close_ms = MAX(cbt->close_ms, 60*1000);
+
   cbt->have_computed_timeout = 1;
   return 1;
 }
@@ -1132,8 +1153,9 @@ circuit_build_times_set_timeout(circuit_build_times_t *cbt)
                cbt->total_build_times,
                tor_lround(cbt->timeout_ms/1000));
     log_info(LD_CIRC,
-             "Circuit timeout data: %lfms, Xm: %d, a: %lf, r: %lf",
-             cbt->timeout_ms, cbt->Xm, cbt->alpha, timeout_rate);
+             "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf",
+             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
+             timeout_rate);
   } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
     log_notice(LD_CIRC,
                "Based on %d circuit times, it looks like we need to wait "
@@ -1142,14 +1164,15 @@ circuit_build_times_set_timeout(circuit_build_times_t *cbt)
                cbt->total_build_times,
                tor_lround(cbt->timeout_ms/1000));
     log_info(LD_CIRC,
-             "Circuit timeout data: %lfms, Xm: %d, a: %lf, r: %lf",
-             cbt->timeout_ms, cbt->Xm, cbt->alpha, timeout_rate);
+             "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf",
+             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
+             timeout_rate);
   } else {
     log_info(LD_CIRC,
-             "Set circuit build timeout to %lds (%lfms, Xm: %d, a: %lf, "
-             "r: %lf) based on %d circuit times",
+             "Set circuit build timeout to %lds (%lfms, %lfms, Xm: %d, a: %lf,"
+             " r: %lf) based on %d circuit times",
              tor_lround(cbt->timeout_ms/1000),
-             cbt->timeout_ms, cbt->Xm, cbt->alpha, timeout_rate,
+             cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
              cbt->total_build_times);
   }
 }
@@ -1747,7 +1770,7 @@ circuit_send_next_onion_skin(origin_circuit_t *circ)
          * it off at, we probably had a suspend event along this codepath,
          * and we should discard the value.
          */
-        if (timediff < 0 || timediff > 2*circ_times.timeout_ms+1000) {
+        if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) {
           log_notice(LD_CIRC, "Strange value for circuit build time: %ld. "
                               "Assuming clock jump.", timediff);
         } else if (!circuit_build_times_disabled()) {
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index e7d10a2..5696d9c 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -270,6 +270,7 @@ circuit_expire_building(time_t now)
    * decided on a customized one yet */
   time_t general_cutoff = now - lround(circ_times.timeout_ms/1000);
   time_t begindir_cutoff = now - lround(circ_times.timeout_ms/2000);
+  time_t close_cutoff = now - lround(circ_times.close_ms/1000);
   time_t introcirc_cutoff = begindir_cutoff;
   cpath_build_state_t *build_state;
 
@@ -286,8 +287,11 @@ circuit_expire_building(time_t now)
       cutoff = begindir_cutoff;
     else if (victim->purpose == CIRCUIT_PURPOSE_C_INTRODUCING)
       cutoff = introcirc_cutoff;
+    else if (victim->purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT)
+      cutoff = close_cutoff;
     else
       cutoff = general_cutoff;
+
     if (victim->timestamp_created > cutoff)
       continue; /* it's still young, leave it alone */
 
@@ -350,12 +354,29 @@ circuit_expire_building(time_t now)
     } else { /* circuit not open, consider recording failure as timeout */
       int first_hop_succeeded = TO_ORIGIN_CIRCUIT(victim)->cpath &&
             TO_ORIGIN_CIRCUIT(victim)->cpath->state == CPATH_STATE_OPEN;
+
+      if (TO_ORIGIN_CIRCUIT(victim)->p_streams != NULL) {
+        log_warn(LD_BUG, "Circuit %d (purpose %d) has timed out, "
+                 "yet has attached streams!",
+                 TO_ORIGIN_CIRCUIT(victim)->global_identifier,
+                 victim->purpose);
+        tor_fragile_assert();
+        continue;
+      }
+
+      /* circuits are allowed to last longer for measurement.
+       * Switch their purpose and wait. */
+      if (victim->purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
+        victim->purpose = CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT;
+        continue;
+      }
+
       /*
        * If the circuit build time is much greater than we would have cut
        * it off at, we probably had a suspend event along this codepath,
        * and we should discard the value.
        */
-      if (now - victim->timestamp_created > (2*circ_times.timeout_ms)/1000+1) {
+      if (now - victim->timestamp_created > 2*circ_times.close_ms/1000+1) {
         log_notice(LD_CIRC,
                    "Extremely large value for circuit build timeout: %ld. "
                    "Assuming clock jump.", now - victim->timestamp_created);
diff --git a/src/or/or.h b/src/or/or.h
index e99b2e9..8e8ea18 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -467,23 +467,23 @@ typedef enum {
 #define CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED 11
 /** Client-side circuit purpose: at Alice, rendezvous established. */
 #define CIRCUIT_PURPOSE_C_REND_JOINED 12
-
-#define _CIRCUIT_PURPOSE_C_MAX 12
-
+/** This circuit is used for build time measurement only */
+#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT 13
+#define _CIRCUIT_PURPOSE_C_MAX 13
 /** Hidden-service-side circuit purpose: at Bob, waiting for introductions. */
-#define CIRCUIT_PURPOSE_S_ESTABLISH_INTRO 13
+#define CIRCUIT_PURPOSE_S_ESTABLISH_INTRO 14
 /** Hidden-service-side circuit purpose: at Bob, successfully established
  * intro. */
-#define CIRCUIT_PURPOSE_S_INTRO 14
+#define CIRCUIT_PURPOSE_S_INTRO 15
 /** Hidden-service-side circuit purpose: at Bob, connecting to rend point. */
-#define CIRCUIT_PURPOSE_S_CONNECT_REND 15
+#define CIRCUIT_PURPOSE_S_CONNECT_REND 16
 /** Hidden-service-side circuit purpose: at Bob, rendezvous established. */
-#define CIRCUIT_PURPOSE_S_REND_JOINED 16
+#define CIRCUIT_PURPOSE_S_REND_JOINED 17
 /** A testing circuit; not meant to be used for actual traffic. */
-#define CIRCUIT_PURPOSE_TESTING 17
+#define CIRCUIT_PURPOSE_TESTING 18
 /** A controller made this circuit and Tor should not use it. */
-#define CIRCUIT_PURPOSE_CONTROLLER 18
-#define _CIRCUIT_PURPOSE_MAX 18
+#define CIRCUIT_PURPOSE_CONTROLLER 19
+#define _CIRCUIT_PURPOSE_MAX 19
 /** A catch-all for unrecognized purposes. Currently we don't expect
  * to make or see any circuits with this purpose. */
 #define CIRCUIT_PURPOSE_UNKNOWN 255
@@ -3056,6 +3056,12 @@ typedef uint32_t build_time_t;
 /* Circuit build times consensus parameters */
 
 /**
+ * How long to wait before actually closing circuits that take too long to
+ * build in terms of CDF quantile.
+ */
+#define CBT_DEFAULT_CLOSE_QUANTILE 95
+
+/**
  * How many circuits count as recent when considering if the
  * connection has gone gimpy or changed.
  */
@@ -3134,6 +3140,8 @@ typedef struct {
   /** The exact value for that timeout in milliseconds. Stored as a double
    * to maintain precision from calculations to and from quantile value. */
   double timeout_ms;
+  /** How long we wait before actually closing the circuit. */
+  double close_ms;
 } circuit_build_times_t;
 
 extern circuit_build_times_t circ_times;
-- 
1.7.1