Fix unittest failure in bug 1660.

We now record large times as abandoned, to prevent a filter step from
happening and skewing our results.

Also, issue a warn for a rare case that can happen for funky values of Xm or
too many abandoned circuits. Can happen (very rarely) during unit tests, but
should not be possble during live operation, due to network liveness filters
and discard logic.

3 files changed, 31 insertions, 14 deletions

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 6ee2921885..07a66cf55f 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -710,7 +710,7 @@ circuit_build_times_parse_state(circuit_build_times_t *cbt,
  * an acceptable approximation because we are only concerned with the
  * accuracy of the CDF of the tail.
  */
-void
+int
 circuit_build_times_update_alpha(circuit_build_times_t *cbt)
 {
   build_time_t *x=cbt->circuit_build_times;
@@ -748,7 +748,16 @@ circuit_build_times_update_alpha(circuit_build_times_t *cbt)
   }
   tor_assert(n==cbt->total_build_times);
 
-  tor_assert(max_time > 0);
+  if (max_time <= 0) {
+    /* This can happen if Xm is actually the *maximum* value in the set.
+     * It can also happen if we've abandoned every single circuit somehow.
+     * In either case, tell the caller not to compute a new build timeout. */
+    log_warn(LD_BUG,
+             "Could not determine largest build time (%d). "
+             "Xm is %dms and we've abandoned %d out of %d circuits.", max_time,
+             cbt->Xm, abandoned_count, n);
+    return 0;
+  }
 
   a += abandoned_count*tor_mathlog(max_time);
 
@@ -759,6 +768,8 @@ circuit_build_times_update_alpha(circuit_build_times_t *cbt)
   a = (n-abandoned_count)/a;
 
   cbt->alpha = a;
+
+  return 1;
 }
 
 /**
@@ -1177,7 +1188,8 @@ circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
     return 0;
   }
 
-  circuit_build_times_update_alpha(cbt);
+  if (!circuit_build_times_update_alpha(cbt))
+    return 0;
 
   cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
                                 circuit_build_times_quantile_cutoff());
diff --git a/src/or/or.h b/src/or/or.h
index 5393b27d4d..60987698b4 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -3188,7 +3188,7 @@ build_time_t circuit_build_times_generate_sample(circuit_build_times_t *cbt,
                                                  double q_lo, double q_hi);
 void circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
                                        double quantile, double time_ms);
-void circuit_build_times_update_alpha(circuit_build_times_t *cbt);
+int circuit_build_times_update_alpha(circuit_build_times_t *cbt);
 double circuit_build_times_cdf(circuit_build_times_t *cbt, double x);
 void circuit_build_times_add_timeout_worker(circuit_build_times_t *cbt,
                                        double quantile_cutoff);
diff --git a/src/test/test.c b/src/test/test.c
index fbcfedbc9a..a753db27f6 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -470,6 +470,7 @@ test_circuit_timeout(void)
   or_state_t state;
   char *msg;
   int i, runs;
+  double close_ms;
   circuit_build_times_init(&initial);
   circuit_build_times_init(&estimate);
   circuit_build_times_init(&final);
@@ -478,27 +479,31 @@ test_circuit_timeout(void)
 
   circuitbuild_running_unit_tests();
 #define timeout0 (build_time_t)(30*1000.0)
-  initial.Xm = 750;
+  initial.Xm = 3000;
   circuit_build_times_initial_alpha(&initial,
                                     CBT_DEFAULT_QUANTILE_CUTOFF/100.0,
                                     timeout0);
+  close_ms = MAX(circuit_build_times_calculate_timeout(&initial,
+                             CBT_DEFAULT_CLOSE_QUANTILE/100.0),
+                 CBT_DEFAULT_TIMEOUT_INITIAL_VALUE);
   do {
-    int n = 0;
     for (i=0; i < CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE; i++) {
-      if (circuit_build_times_add_time(&estimate,
-              circuit_build_times_generate_sample(&initial, 0, 1)) == 0) {
-        n++;
+      build_time_t sample = circuit_build_times_generate_sample(&initial,0,1);
+
+      if (sample > close_ms) {
+        circuit_build_times_add_time(&estimate, CBT_BUILD_ABANDONED);
+      } else {
+        circuit_build_times_add_time(&estimate, sample);
       }
     }
     circuit_build_times_update_alpha(&estimate);
     timeout1 = circuit_build_times_calculate_timeout(&estimate,
                                   CBT_DEFAULT_QUANTILE_CUTOFF/100.0);
     circuit_build_times_set_timeout(&estimate);
-    log_warn(LD_CIRC, "Timeout1 is %lf, Xm is %d", timeout1, estimate.Xm);
+    log_notice(LD_CIRC, "Timeout1 is %lf, Xm is %d", timeout1, estimate.Xm);
+           /* 2% error */
   } while (fabs(circuit_build_times_cdf(&initial, timeout0) -
-                circuit_build_times_cdf(&initial, timeout1)) > 0.02
-                /* 2% error */
-           && estimate.total_build_times < CBT_NCIRCUITS_TO_OBSERVE);
+                circuit_build_times_cdf(&initial, timeout1)) > 0.02);
 
   test_assert(estimate.total_build_times <= CBT_NCIRCUITS_TO_OBSERVE);
 
@@ -510,7 +515,7 @@ test_circuit_timeout(void)
                                  CBT_DEFAULT_QUANTILE_CUTOFF/100.0);
 
   circuit_build_times_set_timeout(&final);
-  log_warn(LD_CIRC, "Timeout2 is %lf, Xm is %d", timeout2, final.Xm);
+  log_notice(LD_CIRC, "Timeout2 is %lf, Xm is %d", timeout2, final.Xm);
 
   /* 5% here because some accuracy is lost due to histogram conversion */
   test_assert(fabs(circuit_build_times_cdf(&initial, timeout0) -