Merge remote-tracking branch 'origin/maint-0.2.4'

Conflicts:
	src/or/relay.c

Conflict changes were easy; compilation fixes required were using
using TOR_SIMPLEQ_FIRST to get head of cell queue.

6 files changed, 79 insertions, 11 deletions

diff --git a/changes/bug9093 b/changes/bug9093
new file mode 100644
index 000000000..06b6cb926
--- /dev/null
+++ b/changes/bug9093
@@ -0,0 +1,7 @@
+  o Minor features:
+    - Improve the circuit queue out-of-memory handler. Previously, when
+      we ran low on memory, we'd close whichever circuits had the most
+      queued cells. Now, we close those that have the *oldest* queued
+      cells, on the theory that those are most responsible for us
+      running low on memory. Based on analysis from a forthcoming paper
+      by Jansen, Tschorsch, Johnson, and Scheuermann. Fixes bug 9093.
\ No newline at end of file
diff --git a/src/common/util.c b/src/common/util.c
index f3a6c1062..0771c9424 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -1303,6 +1303,18 @@ tv_mdiff(const struct timeval *start, const struct timeval *end)
   return mdiff;
 }
 
+/**
+ * Converts timeval to milliseconds.
+ */
+int64_t
+tv_to_msec(const struct timeval *tv)
+{
+  int64_t conv = ((int64_t)tv->tv_sec)*1000L;
+  /* Round ghetto-style */
+  conv += ((int64_t)tv->tv_usec+500)/1000L;
+  return conv;
+}
+
 /** Yield true iff <b>y</b> is a leap-year. */
 #define IS_LEAPYEAR(y) (!(y % 4) && ((y % 100) || !(y % 400)))
 /** Helper: Return the number of leap-days between Jan 1, y1 and Jan 1, y2. */
diff --git a/src/common/util.h b/src/common/util.h
index dcf45942f..3199ab112 100644
--- a/src/common/util.h
+++ b/src/common/util.h
@@ -253,6 +253,7 @@ int base16_decode(char *dest, size_t destlen, const char *src, size_t srclen);
 /* Time helpers */
 long tv_udiff(const struct timeval *start, const struct timeval *end);
 long tv_mdiff(const struct timeval *start, const struct timeval *end);
+int64_t tv_to_msec(const struct timeval *tv);
 int tor_timegm(const struct tm *tm, time_t *time_out);
 #define RFC1123_TIME_LEN 29
 void format_rfc1123_time(char *buf, time_t t);
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 19f46188b..c31bc49d0 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -1620,25 +1620,58 @@ n_cells_in_circ_queues(const circuit_t *c)
   return n;
 }
 
-/** helper to sort a list of circuit_q by total queue lengths, in descending
- * order. */
+/**
+ * Return the age of the oldest cell queued on <b>c</b>, in milliseconds.
+ * Return 0 if there are no cells queued on c.  Requires that <b>now</b> be
+ * the current time in milliseconds since the epoch, truncated.
+ *
+ * This function will return incorrect results if the oldest cell queued on
+ * the circuit is older than 2**32 msec (about 49 days) old.
+ */
+static uint32_t
+circuit_max_queued_cell_age(const circuit_t *c, uint32_t now)
+{
+  uint32_t age = 0;
+  packed_cell_t *cell;
+
+  if (NULL != (cell = TOR_SIMPLEQ_FIRST(&c->n_chan_cells.head)))
+    age = now - cell->inserted_time;
+
+  if (! CIRCUIT_IS_ORIGIN(c)) {
+    const or_circuit_t *orcirc = TO_OR_CIRCUIT((circuit_t*)c);
+    if (NULL != (cell = TOR_SIMPLEQ_FIRST(&orcirc->p_chan_cells.head))) {
+      uint32_t age2 = now - cell->inserted_time;
+      if (age2 > age)
+        return age2;
+    }
+  }
+  return age;
+}
+
+/** Temporary variable for circuits_compare_by_oldest_queued_cell_ This is a
+ * kludge to work around the fact that qsort doesn't provide a way for
+ * comparison functions to take an extra argument. */
+static uint32_t circcomp_now_tmp;
+
+/** Helper to sort a list of circuit_t by age of oldest cell, in descending
+ * order. Requires that circcomp_now_tmp is set correctly. */
 static int
-circuits_compare_by_queue_len_(const void **a_, const void **b_)
+circuits_compare_by_oldest_queued_cell_(const void **a_, const void **b_)
 {
   const circuit_t *a = *a_;
   const circuit_t *b = *b_;
-  size_t a_n = n_cells_in_circ_queues(a);
-  size_t b_n = n_cells_in_circ_queues(b);
+  uint32_t age_a = circuit_max_queued_cell_age(a, circcomp_now_tmp);
+  uint32_t age_b = circuit_max_queued_cell_age(b, circcomp_now_tmp);
 
-  if (a_n < b_n)
+  if (age_a < age_b)
     return 1;
-  else if (a_n == b_n)
+  else if (age_a == age_b)
     return 0;
   else
     return -1;
 }
 
-#define FRACTION_OF_CIRCS_TO_RETAIN_ON_OOM 0.90
+#define FRACTION_OF_CELLS_TO_RETAIN_ON_OOM 0.90
 
 /** We're out of memory for cells, having allocated <b>current_allocation</b>
  * bytes' worth.  Kill the 'worst' circuits until we're under
@@ -1651,13 +1684,14 @@ circuits_handle_oom(size_t current_allocation)
   circuit_t *circ;
   size_t n_cells_removed=0, n_cells_to_remove;
   int n_circuits_killed=0;
+  struct timeval now;
   log_notice(LD_GENERAL, "We're low on memory.  Killing circuits with "
              "over-long queues. (This behavior is controlled by "
              "MaxMemInCellQueues.)");
 
   {
     size_t mem_target = (size_t)(get_options()->MaxMemInCellQueues *
-                                 FRACTION_OF_CIRCS_TO_RETAIN_ON_OOM);
+                                 FRACTION_OF_CELLS_TO_RETAIN_ON_OOM);
     size_t mem_to_recover;
     if (current_allocation <= mem_target)
       return;
@@ -1670,9 +1704,13 @@ circuits_handle_oom(size_t current_allocation)
   TOR_LIST_FOREACH(circ, &global_circuitlist, head)
     smartlist_add(circlist, circ);
 
+  /* Set circcomp_now_tmp so that the sort can work. */
+  tor_gettimeofday_cached(&now);
+  circcomp_now_tmp = (uint32_t)tv_to_msec(&now);
+
   /* This is O(n log n); there are faster algorithms we could use instead.
    * Let's hope this doesn't happen enough to be in the critical path. */
-  smartlist_sort(circlist, circuits_compare_by_queue_len_);
+  smartlist_sort(circlist, circuits_compare_by_oldest_queued_cell_);
 
   /* Okay, now the worst circuits are at the front of the list. Let's mark
    * them, and reclaim their storage aggressively. */
diff --git a/src/or/or.h b/src/or/or.h
index a31324850..6b18f1328 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1120,8 +1120,13 @@ typedef struct packed_cell_t {
   /** Next cell queued on this circuit. */
   TOR_SIMPLEQ_ENTRY(packed_cell_t) next;
   char body[CELL_MAX_NETWORK_SIZE]; /**< Cell as packed for network. */
+  uint32_t inserted_time; /**< Time (in milliseconds since epoch, with high
+                           * bits truncated) when this cell was inserted. */
 } packed_cell_t;
 
+/* XXXX This next structure may be obsoleted by inserted_time in
+ * packed_cell_t */
+
 /** Number of cells added to a circuit queue including their insertion
  * time on 10 millisecond detail; used for buffer statistics. */
 typedef struct insertion_time_elem_t {
diff --git a/src/or/relay.c b/src/or/relay.c
index 3600707d1..0c9267a9a 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -2213,8 +2213,13 @@ cell_queue_append_packed_copy(circuit_t *circ, cell_queue_t *queue,
                               int exitward, const cell_t *cell,
                               int wide_circ_ids, int use_stats)
 {
+  struct timeval now;
   packed_cell_t *copy = packed_cell_copy(cell, wide_circ_ids);
+  tor_gettimeofday_cached(&now);
+  copy->inserted_time = (uint32_t)tv_to_msec(&now);
+
   /* Remember the time when this cell was put in the queue. */
+  /*XXXX This may be obsoleted by inserted_time */
   if ((get_options()->CellStatistics ||
       get_options()->TestingEnableCellStatsEvent) && use_stats) {
     struct timeval now;
@@ -2222,7 +2227,7 @@ cell_queue_append_packed_copy(circuit_t *circ, cell_queue_t *queue,
     insertion_time_queue_t *it_queue = queue->insertion_times;
     if (!it_pool)
       it_pool = mp_pool_new(sizeof(insertion_time_elem_t), 1024);
-    tor_gettimeofday_cached(&now);
+
 #define SECONDS_IN_A_DAY 86400L
     added = (uint32_t)(((now.tv_sec % SECONDS_IN_A_DAY) * 100L)
             + ((uint32_t)now.tv_usec / (uint32_t)10000L));