Optimize cell-ewma circuit priority algorithm.

There are two big changes here:
  - We store active circuits in a priority queue for each or_conn,
    rather than doing a linear search over all the active circuits
    before we send each cell.
  - Rather than multiplying every circuit's cell-ewma by a decay
    factor every time we send a cell (thus normalizing the value of a
    current cell to 1.0 and a past cell to alpha^t), we instead
    only scale down the cell-ewma every tick (ten seconds atm),
    normalizing so that a cell sent at the start of the tick has
    value 1.0).

1 files changed, 4 insertions, 0 deletions

diff --git a/src/or/connection.c b/src/or/connection.c
index 409884b920..a95850b9e5 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -180,6 +180,9 @@ or_connection_new(int socket_family)
   or_conn->timestamp_last_added_nonpadding = time(NULL);
   or_conn->next_circ_id = crypto_rand_int(1<<15);
 
+  or_conn->active_circuit_pqueue = smartlist_create();
+  or_conn->active_circuit_pqueue_last_recalibrated = cell_ewma_get_tick();
+
   return or_conn;
 }
 
@@ -375,6 +378,7 @@ _connection_free(connection_t *conn)
     or_conn->tls = NULL;
     or_handshake_state_free(or_conn->handshake_state);
     or_conn->handshake_state = NULL;
+    smartlist_free(or_conn->active_circuit_pqueue);
     tor_free(or_conn->nickname);
   }
   if (CONN_IS_EDGE(conn)) {