Merge branch 'maint-0.4.7' into release-0.4.7

6 files changed, 99 insertions, 56 deletions

diff --git a/src/core/or/circuitlist.c b/src/core/or/circuitlist.c
index d1c734bdd2..eb13e3bccd 100644
--- a/src/core/or/circuitlist.c
+++ b/src/core/or/circuitlist.c
@@ -154,10 +154,6 @@ double cc_stats_circ_close_cwnd_ma = 0;
 /** Moving average of the cc->cwnd from each closed slow-start circuit. */
 double cc_stats_circ_close_ss_cwnd_ma = 0;
 
-/* Running count of the above moving averages. Needed so we can update it. */
-static double stats_circ_close_cwnd_ma_count = 0;
-static double stats_circ_close_ss_cwnd_ma_count = 0;
-
 /********* END VARIABLES ************/
 
 /* Implement circuit handle helpers. */
@@ -2244,18 +2240,14 @@ circuit_mark_for_close_, (circuit_t *circ, int reason, int line,
        * and a max RTT, and they are not the same. This prevents us from
        * averaging and reporting unused and low-use circuits here */
       if (circ->ccontrol->max_rtt_usec != circ->ccontrol->min_rtt_usec) {
-        stats_circ_close_ss_cwnd_ma_count++;
         cc_stats_circ_close_ss_cwnd_ma =
           stats_update_running_avg(cc_stats_circ_close_ss_cwnd_ma,
-                                   circ->ccontrol->cwnd,
-                                   stats_circ_close_ss_cwnd_ma_count);
+                                   circ->ccontrol->cwnd);
       }
     } else {
-      stats_circ_close_cwnd_ma_count++;
       cc_stats_circ_close_cwnd_ma =
         stats_update_running_avg(cc_stats_circ_close_cwnd_ma,
-                                 circ->ccontrol->cwnd,
-                                 stats_circ_close_cwnd_ma_count);
+                                 circ->ccontrol->cwnd);
     }
   }
 
diff --git a/src/core/or/congestion_control_flow.c b/src/core/or/congestion_control_flow.c
index 729e67b9a3..90b1927ef9 100644
--- a/src/core/or/congestion_control_flow.c
+++ b/src/core/or/congestion_control_flow.c
@@ -41,9 +41,7 @@ static uint32_t xon_rate_bytes;
 uint64_t cc_stats_flow_num_xoff_sent;
 uint64_t cc_stats_flow_num_xon_sent;
 double cc_stats_flow_xoff_outbuf_ma = 0;
-static double cc_stats_flow_xoff_outbuf_ma_count = 0;
 double cc_stats_flow_xon_outbuf_ma = 0;
-static double cc_stats_flow_xon_outbuf_ma_count = 0;
 
 /* In normal operation, we can get a burst of up to 32 cells before returning
  * to libevent to flush the outbuf. This is a heuristic from hardcoded values
@@ -485,11 +483,9 @@ flow_control_decide_xoff(edge_connection_t *stream)
                  total_buffered, buffer_limit_xoff);
       tor_trace(TR_SUBSYS(cc), TR_EV(flow_decide_xoff_sending), stream);
 
-      cc_stats_flow_xoff_outbuf_ma_count++;
       cc_stats_flow_xoff_outbuf_ma =
         stats_update_running_avg(cc_stats_flow_xoff_outbuf_ma,
-                                 total_buffered,
-                                 cc_stats_flow_xoff_outbuf_ma_count);
+                                 total_buffered);
 
       circuit_send_stream_xoff(stream);
 
@@ -646,11 +642,9 @@ flow_control_decide_xon(edge_connection_t *stream, size_t n_written)
                  total_buffered);
       tor_trace(TR_SUBSYS(cc), TR_EV(flow_decide_xon_rate_change), stream);
 
-      cc_stats_flow_xon_outbuf_ma_count++;
       cc_stats_flow_xon_outbuf_ma =
         stats_update_running_avg(cc_stats_flow_xon_outbuf_ma,
-                                 total_buffered,
-                                 cc_stats_flow_xon_outbuf_ma_count);
+                                 total_buffered);
 
       circuit_send_stream_xon(stream);
     }
diff --git a/src/core/or/congestion_control_vegas.c b/src/core/or/congestion_control_vegas.c
index 8351aa6e27..2b0ed3a507 100644
--- a/src/core/or/congestion_control_vegas.c
+++ b/src/core/or/congestion_control_vegas.c
@@ -54,10 +54,8 @@
 double cc_stats_vegas_exit_ss_cwnd_ma = 0;
 double cc_stats_vegas_gamma_drop_ma = 0;
 double cc_stats_vegas_delta_drop_ma = 0;
-/* Running count of this moving average. Needed so we can update it. */
-static double stats_cwnd_exit_ss_ma_count = 0;
-static double stats_cwnd_gamma_drop_ma_count = 0;
-static double stats_cwnd_delta_drop_ma_count = 0;
+double cc_stats_vegas_ss_csig_blocked_ma = 0;
+double cc_stats_vegas_csig_blocked_ma = 0;
 
 /** Stats on how many times we reached "delta" param. */
 uint64_t cc_stats_vegas_above_delta = 0;
@@ -259,10 +257,9 @@ congestion_control_vegas_exit_slow_start(const circuit_t *circ,
   congestion_control_vegas_log(circ, cc);
 
   /* Update running cc->cwnd average for metrics. */
-  stats_cwnd_exit_ss_ma_count++;
   cc_stats_vegas_exit_ss_cwnd_ma =
     stats_update_running_avg(cc_stats_vegas_exit_ss_cwnd_ma,
-                             cc->cwnd, stats_cwnd_exit_ss_ma_count);
+                             cc->cwnd);
 
   /* We need to report that slow start has exited ASAP,
    * for sbws bandwidth measurement. */
@@ -343,10 +340,20 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc,
 
       /* Account the amount we reduced the cwnd by for the gamma cutoff */
       cwnd_diff = (old_cwnd > cc->cwnd ? old_cwnd - cc->cwnd : 0);
-      stats_cwnd_gamma_drop_ma_count++;
       cc_stats_vegas_gamma_drop_ma =
         stats_update_running_avg(cc_stats_vegas_gamma_drop_ma,
-                             cwnd_diff, stats_cwnd_gamma_drop_ma_count);
+                             cwnd_diff);
+
+      /* Compute the percentage we experience a blocked csig vs RTT sig */
+      if (cc->blocked_chan) {
+        cc_stats_vegas_ss_csig_blocked_ma =
+          stats_update_running_avg(cc_stats_vegas_ss_csig_blocked_ma,
+                                   100);
+      } else {
+        cc_stats_vegas_ss_csig_blocked_ma =
+          stats_update_running_avg(cc_stats_vegas_ss_csig_blocked_ma,
+                                   0);
+      }
 
       congestion_control_vegas_exit_slow_start(circ, cc);
     }
@@ -368,13 +375,23 @@ congestion_control_vegas_process_sendme(congestion_control_t *cc,
 
       /* Account the amount we reduced the cwnd by for the gamma cutoff */
       cwnd_diff = (old_cwnd > cc->cwnd ? old_cwnd - cc->cwnd : 0);
-      stats_cwnd_delta_drop_ma_count++;
       cc_stats_vegas_delta_drop_ma =
         stats_update_running_avg(cc_stats_vegas_delta_drop_ma,
-                             cwnd_diff, stats_cwnd_delta_drop_ma_count);
+                             cwnd_diff);
 
       cc_stats_vegas_above_delta++;
     } else if (queue_use > cc->vegas_params.beta || cc->blocked_chan) {
+      /* Compute the percentage we experience a blocked csig vs RTT sig */
+      if (cc->blocked_chan) {
+        cc_stats_vegas_csig_blocked_ma =
+          stats_update_running_avg(cc_stats_vegas_csig_blocked_ma,
+                                   100);
+      } else {
+        cc_stats_vegas_csig_blocked_ma =
+          stats_update_running_avg(cc_stats_vegas_csig_blocked_ma,
+                                   0);
+      }
+
       cc->cwnd -= CWND_INC(cc);
     } else if (queue_use < cc->vegas_params.alpha) {
       cc->cwnd += CWND_INC(cc);
diff --git a/src/core/or/congestion_control_vegas.h b/src/core/or/congestion_control_vegas.h
index 6048b1e26d..722ffde01a 100644
--- a/src/core/or/congestion_control_vegas.h
+++ b/src/core/or/congestion_control_vegas.h
@@ -15,6 +15,8 @@
 extern double cc_stats_vegas_exit_ss_cwnd_ma;
 extern double cc_stats_vegas_gamma_drop_ma;
 extern double cc_stats_vegas_delta_drop_ma;
+extern double cc_stats_vegas_ss_csig_blocked_ma;
+extern double cc_stats_vegas_csig_blocked_ma;
 extern uint64_t cc_stats_vegas_above_delta;
 extern uint64_t cc_stats_vegas_above_ss_cwnd_max;
 
diff --git a/src/feature/relay/relay_metrics.c b/src/feature/relay/relay_metrics.c
index 02e38d7699..c9a3c7944d 100644
--- a/src/feature/relay/relay_metrics.c
+++ b/src/feature/relay/relay_metrics.c
@@ -411,15 +411,6 @@ fill_cc_values(void)
   sentry = metrics_store_add(the_store, rentry->type, rentry->name,
                              rentry->help);
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("state", "slow_start_exit"));
-  metrics_store_entry_add_label(sentry,
-          metrics_format_label("action", "gamma_drop"));
-  metrics_store_entry_update(sentry,
-                             tor_llround(cc_stats_vegas_gamma_drop_ma));
-
-  sentry = metrics_store_add(the_store, rentry->type, rentry->name,
-                             rentry->help);
-  metrics_store_entry_add_label(sentry,
           metrics_format_label("state", "on_circ_close"));
   metrics_store_entry_add_label(sentry,
           metrics_format_label("action", "cwnd"));
@@ -438,43 +429,43 @@ fill_cc_values(void)
   sentry = metrics_store_add(the_store, rentry->type, rentry->name,
                              rentry->help);
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("state", "xoff"));
+          metrics_format_label("state", "flow_control"));
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("action", "outbuf"));
+          metrics_format_label("action", "xoff_num_sent"));
   metrics_store_entry_update(sentry,
-                             tor_llround(cc_stats_flow_xoff_outbuf_ma));
+                             cc_stats_flow_num_xoff_sent);
 
   sentry = metrics_store_add(the_store, rentry->type, rentry->name,
                              rentry->help);
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("state", "xoff"));
+          metrics_format_label("state", "flow_control"));
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("action", "num_sent"));
+          metrics_format_label("action", "xon_num_sent"));
   metrics_store_entry_update(sentry,
-                             cc_stats_flow_num_xoff_sent);
+                             cc_stats_flow_num_xon_sent);
 
   sentry = metrics_store_add(the_store, rentry->type, rentry->name,
                              rentry->help);
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("state", "xon"));
+          metrics_format_label("state", "buffers"));
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("action", "outbuf"));
+          metrics_format_label("action", "xon_outbuf"));
   metrics_store_entry_update(sentry,
                              tor_llround(cc_stats_flow_xon_outbuf_ma));
 
   sentry = metrics_store_add(the_store, rentry->type, rentry->name,
                              rentry->help);
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("state", "xon"));
+          metrics_format_label("state", "buffers"));
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("action", "num_sent"));
+          metrics_format_label("action", "xoff_outbuf"));
   metrics_store_entry_update(sentry,
-                             cc_stats_flow_num_xon_sent);
+                             tor_llround(cc_stats_flow_xoff_outbuf_ma));
 
   sentry = metrics_store_add(the_store, rentry->type, rentry->name,
                              rentry->help);
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("state", "process_sendme"));
+          metrics_format_label("state", "cc_limits"));
   metrics_store_entry_add_label(sentry,
           metrics_format_label("action", "above_delta"));
   metrics_store_entry_update(sentry, cc_stats_vegas_above_delta);
@@ -482,7 +473,7 @@ fill_cc_values(void)
   sentry = metrics_store_add(the_store, rentry->type, rentry->name,
                              rentry->help);
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("state", "process_sendme"));
+          metrics_format_label("state", "cc_limits"));
   metrics_store_entry_add_label(sentry,
           metrics_format_label("action", "above_ss_cwnd_max"));
   metrics_store_entry_update(sentry, cc_stats_vegas_above_ss_cwnd_max);
@@ -490,11 +481,38 @@ fill_cc_values(void)
   sentry = metrics_store_add(the_store, rentry->type, rentry->name,
                              rentry->help);
   metrics_store_entry_add_label(sentry,
-          metrics_format_label("state", "process_sendme"));
+          metrics_format_label("state", "cc_backoff"));
+  metrics_store_entry_add_label(sentry,
+          metrics_format_label("action", "chan_blocked_pct"));
+  metrics_store_entry_update(sentry,
+                             tor_llround(cc_stats_vegas_csig_blocked_ma));
+
+  sentry = metrics_store_add(the_store, rentry->type, rentry->name,
+                             rentry->help);
+  metrics_store_entry_add_label(sentry,
+          metrics_format_label("state", "cc_backoff"));
+  metrics_store_entry_add_label(sentry,
+          metrics_format_label("action", "gamma_drop"));
+  metrics_store_entry_update(sentry,
+                             tor_llround(cc_stats_vegas_gamma_drop_ma));
+
+  sentry = metrics_store_add(the_store, rentry->type, rentry->name,
+                             rentry->help);
+  metrics_store_entry_add_label(sentry,
+          metrics_format_label("state", "cc_backoff"));
   metrics_store_entry_add_label(sentry,
           metrics_format_label("action", "delta_drop"));
   metrics_store_entry_update(sentry,
                              tor_llround(cc_stats_vegas_delta_drop_ma));
+
+  sentry = metrics_store_add(the_store, rentry->type, rentry->name,
+                             rentry->help);
+  metrics_store_entry_add_label(sentry,
+          metrics_format_label("state", "cc_backoff"));
+  metrics_store_entry_add_label(sentry,
+          metrics_format_label("action", "ss_chan_blocked_pct"));
+  metrics_store_entry_update(sentry,
+                             tor_llround(cc_stats_vegas_ss_csig_blocked_ma));
 }
 
 /** Helper: Fill in single stream metrics output. */
diff --git a/src/lib/math/stats.h b/src/lib/math/stats.h
index 328d61a9d6..14315a2506 100644
--- a/src/lib/math/stats.h
+++ b/src/lib/math/stats.h
@@ -10,13 +10,33 @@
 #ifndef TOR_STATS_H
 #define TOR_STATS_H
 
-/** Update an average making it a "running average". The "avg" is the current
- * value that will be updated to the new one. The "value" is the new value to
- * add to the average and "n" is the new count as in including the "value". */
+/**
+ * Compute an N-count EWMA, aka N-EWMA. N-EWMA is defined as:
+ *  EWMA = alpha*value + (1-alpha)*EWMA_prev
+ * with alpha = 2/(N+1).
+ *
+ * This works out to:
+ *  EWMA = value*2/(N+1) + EMA_prev*(N-1)/(N+1)
+ *       = (value*2 + EWMA_prev*(N-1))/(N+1)
+ */
 static inline double
-stats_update_running_avg(double avg, double value, double n)
+n_count_ewma_double(double avg, double value, uint64_t N)
 {
-  return ((avg * (n - 1)) + value) / n;
+  /* If the average was not previously computed, return value.
+   * The less than is because we have stupid C warning flags that
+   * prevent exact comparison to 0.0, so we can't do an exact
+   * check for unitialized double values. Yay pedantry!
+   * Love it when it introduces surprising edge case bugs like
+   * this will. */
+  if (avg < 0.0000002)
+    return value;
+  else
+    return (2*value + (N-1)*avg)/(N+1);
 }
 
+/* For most stats, an N_EWMA of 100 is sufficient */
+#define DEFAULT_STATS_N_EWMA_COUNT 100
+#define stats_update_running_avg(avg, value) \
+    n_count_ewma_double(avg, value, DEFAULT_STATS_N_EWMA_COUNT)
+
 #endif /* !defined(TOR_STATS_H) */