Merge branch 'simpleq_for_cells_3'

9 files changed, 181 insertions, 28 deletions

diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 5e51301ceb..85bacce485 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -682,6 +682,7 @@ init_circuit_base(circuit_t *circ)
 
   circ->package_window = circuit_initial_package_window();
   circ->deliver_window = CIRCWINDOW_START;
+  cell_queue_init(&circ->n_chan_cells);
 
   circuit_add(circ);
 }
@@ -727,6 +728,7 @@ or_circuit_new(circid_t p_circ_id, channel_t *p_chan)
     circuit_set_p_circid_chan(circ, p_circ_id, p_chan);
 
   circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
+  cell_queue_init(&circ->p_chan_cells);
 
   init_circuit_base(TO_CIRCUIT(circ));
 
@@ -1638,7 +1640,7 @@ marked_circuit_free_cells(circuit_t *circ)
 }
 
 /** Return the number of cells used by the circuit <b>c</b>'s cell queues. */
-static size_t
+STATIC size_t
 n_cells_in_circ_queues(const circuit_t *c)
 {
   size_t n = c->n_chan_cells.n;
diff --git a/src/or/circuitlist.h b/src/or/circuitlist.h
index a5a54859b2..4e56f5264f 100644
--- a/src/or/circuitlist.h
+++ b/src/or/circuitlist.h
@@ -72,6 +72,7 @@ void channel_note_destroy_not_pending(channel_t *chan, circid_t id);
 
 #ifdef CIRCUITLIST_PRIVATE
 STATIC void circuit_free(circuit_t *circ);
+STATIC size_t n_cells_in_circ_queues(const circuit_t *c);
 #endif
 
 #endif
diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c
index 081416368e..77cb2f98bc 100644
--- a/src/or/circuitmux.c
+++ b/src/or/circuitmux.c
@@ -510,7 +510,7 @@ circuitmux_mark_destroyed_circids_usable(circuitmux_t *cmux, channel_t *chan)
 {
   packed_cell_t *cell;
   int n_bad = 0;
-  for (cell = cmux->destroy_cell_queue.head; cell; cell = cell->next) {
+  TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
     circid_t circid = 0;
     if (packed_cell_is_destroy(chan, cell, &circid)) {
       channel_mark_circid_usable(chan, circid);
diff --git a/src/or/or.h b/src/or/or.h
index b8c4279896..06363fa360 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -99,6 +99,7 @@
 #include "ht.h"
 #include "replaycache.h"
 #include "crypto_curve25519.h"
+#include "tor_queue.h"
 
 /* These signals are defined to help handle_control_signal work.
  */
@@ -1083,7 +1084,8 @@ typedef struct var_cell_t {
 
 /** A cell as packed for writing to the network. */
 typedef struct packed_cell_t {
-  struct packed_cell_t *next; /**< Next cell queued on this circuit. */
+  /** Next cell queued on this circuit. */
+  TOR_SIMPLEQ_ENTRY(packed_cell_t) next;
   char body[CELL_MAX_NETWORK_SIZE]; /**< Cell as packed for network. */
 } packed_cell_t;
 
@@ -1105,8 +1107,8 @@ typedef struct insertion_time_queue_t {
 /** A queue of cells on a circuit, waiting to be added to the
  * or_connection_t's outbuf. */
 typedef struct cell_queue_t {
-  packed_cell_t *head; /**< The first cell, or NULL if the queue is empty. */
-  packed_cell_t *tail; /**< The last cell, or NULL if the queue is empty. */
+  /** Linked list of packed_cell_t*/
+  TOR_SIMPLEQ_HEAD(cell_simpleq, packed_cell_t) head;
   int n; /**< The number of cells in the queue. */
   insertion_time_queue_t *insertion_times; /**< Insertion times of cells. */
 } cell_queue_t;
diff --git a/src/or/relay.c b/src/or/relay.c
index 7ec7e03024..297f0f69e0 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -2089,7 +2089,7 @@ packed_cell_free_unchecked(packed_cell_t *cell)
 }
 
 /** Allocate and return a new packed_cell_t. */
-static INLINE packed_cell_t *
+STATIC packed_cell_t *
 packed_cell_new(void)
 {
   ++total_cells_allocated;
@@ -2100,6 +2100,8 @@ packed_cell_new(void)
 void
 packed_cell_free(packed_cell_t *cell)
 {
+  if (!cell)
+    return;
   packed_cell_free_unchecked(cell);
 }
 
@@ -2129,7 +2131,6 @@ packed_cell_copy(const cell_t *cell, int wide_circ_ids)
 {
   packed_cell_t *c = packed_cell_new();
   cell_pack(c, cell, wide_circ_ids);
-  c->next = NULL;
   return c;
 }
 
@@ -2137,14 +2138,7 @@ packed_cell_copy(const cell_t *cell, int wide_circ_ids)
 void
 cell_queue_append(cell_queue_t *queue, packed_cell_t *cell)
 {
-  if (queue->tail) {
-    tor_assert(!queue->tail->next);
-    queue->tail->next = cell;
-  } else {
-    queue->head = cell;
-  }
-  queue->tail = cell;
-  cell->next = NULL;
+  TOR_SIMPLEQ_INSERT_TAIL(&queue->head, cell, next);
   ++queue->n;
 }
 
@@ -2187,18 +2181,24 @@ cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell,
   cell_queue_append(queue, copy);
 }
 
+/** Initialize <b>queue</b> as an empty cell queue. */
+void
+cell_queue_init(cell_queue_t *queue)
+{
+  memset(queue, 0, sizeof(cell_queue_t));
+  TOR_SIMPLEQ_INIT(&queue->head);
+}
+
 /** Remove and free every cell in <b>queue</b>. */
 void
 cell_queue_clear(cell_queue_t *queue)
 {
-  packed_cell_t *cell, *next;
-  cell = queue->head;
-  while (cell) {
-    next = cell->next;
+  packed_cell_t *cell;
+  while ((cell = TOR_SIMPLEQ_FIRST(&queue->head))) {
+    TOR_SIMPLEQ_REMOVE_HEAD(&queue->head, next);
     packed_cell_free_unchecked(cell);
-    cell = next;
   }
-  queue->head = queue->tail = NULL;
+  TOR_SIMPLEQ_INIT(&queue->head);
   queue->n = 0;
   if (queue->insertion_times) {
     while (queue->insertion_times->first) {
@@ -2212,17 +2212,13 @@ cell_queue_clear(cell_queue_t *queue)
 
 /** Extract and return the cell at the head of <b>queue</b>; return NULL if
  * <b>queue</b> is empty. */
-static INLINE packed_cell_t *
+STATIC packed_cell_t *
 cell_queue_pop(cell_queue_t *queue)
 {
-  packed_cell_t *cell = queue->head;
+  packed_cell_t *cell = TOR_SIMPLEQ_FIRST(&queue->head);
   if (!cell)
     return NULL;
-  queue->head = cell->next;
-  if (cell == queue->tail) {
-    tor_assert(!queue->head);
-    queue->tail = NULL;
-  }
+  TOR_SIMPLEQ_REMOVE_HEAD(&queue->head, next);
   --queue->n;
   return cell;
 }
diff --git a/src/or/relay.h b/src/or/relay.h
index 4be3194e5b..e1b5e381ed 100644
--- a/src/or/relay.h
+++ b/src/or/relay.h
@@ -51,6 +51,7 @@ size_t packed_cell_mem_cost(void);
 /* For channeltls.c */
 void packed_cell_free(packed_cell_t *cell);
 
+void cell_queue_init(cell_queue_t *queue);
 void cell_queue_clear(cell_queue_t *queue);
 void cell_queue_append(cell_queue_t *queue, packed_cell_t *cell);
 void cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell,
@@ -81,6 +82,8 @@ int relay_crypt(circuit_t *circ, cell_t *cell, cell_direction_t cell_direction,
 #ifdef RELAY_PRIVATE
 STATIC int connected_cell_parse(const relay_header_t *rh, const cell_t *cell,
                          tor_addr_t *addr_out, int *ttl_out);
+STATIC packed_cell_t *packed_cell_new(void);
+STATIC packed_cell_t *cell_queue_pop(cell_queue_t *queue);
 #endif
 
 #endif
diff --git a/src/test/include.am b/src/test/include.am
index 279369e74f..d616067b85 100644
--- a/src/test/include.am
+++ b/src/test/include.am
@@ -22,6 +22,7 @@ src_test_test_SOURCES = \
 	src/test/test_circuitlist.c \
 	src/test/test_containers.c \
 	src/test/test_crypto.c \
+	src/test/test_cell_queue.c \
 	src/test/test_data.c \
 	src/test/test_dir.c \
 	src/test/test_introduce.c \
diff --git a/src/test/test.c b/src/test/test.c
index d7d4c6c062..d1c5b176b6 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -2133,6 +2133,7 @@ extern struct testcase_t introduce_tests[];
 extern struct testcase_t replaycache_tests[];
 extern struct testcase_t cell_format_tests[];
 extern struct testcase_t circuitlist_tests[];
+extern struct testcase_t cell_queue_tests[];
 
 static struct testgroup_t testgroups[] = {
   { "", test_array },
@@ -2142,6 +2143,7 @@ static struct testgroup_t testgroups[] = {
   { "container/", container_tests },
   { "util/", util_tests },
   { "cellfmt/", cell_format_tests },
+  { "cellqueue/", cell_queue_tests },
   { "dir/", dir_tests },
   { "dir/md/", microdesc_tests },
   { "pt/", pt_tests },
diff --git a/src/test/test_cell_queue.c b/src/test/test_cell_queue.c
new file mode 100644
index 0000000000..cf2d11ad5d
--- /dev/null
+++ b/src/test/test_cell_queue.c
@@ -0,0 +1,146 @@
+/* Copyright (c) 2013, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#define CIRCUITLIST_PRIVATE
+#define RELAY_PRIVATE
+#include "or.h"
+#include "circuitlist.h"
+#include "relay.h"
+#include "test.h"
+
+static void
+test_cq_manip(void *arg)
+{
+  packed_cell_t *pc1=NULL, *pc2=NULL, *pc3=NULL, *pc4=NULL, *pc_tmp=NULL;
+  cell_queue_t cq;
+  cell_t cell;
+  (void) arg;
+
+  init_cell_pool();
+  cell_queue_init(&cq);
+  tt_int_op(cq.n, ==, 0);
+
+  pc1 = packed_cell_new();
+  pc2 = packed_cell_new();
+  pc3 = packed_cell_new();
+  pc4 = packed_cell_new();
+  tt_assert(pc1 && pc2 && pc3 && pc4);
+
+  tt_ptr_op(NULL, ==, cell_queue_pop(&cq));
+
+  /* Add and remove a singleton. */
+  cell_queue_append(&cq, pc1);
+  tt_int_op(cq.n, ==, 1);
+  tt_ptr_op(pc1, ==, cell_queue_pop(&cq));
+  tt_int_op(cq.n, ==, 0);
+
+  /* Add and remove four items */
+  cell_queue_append(&cq, pc4);
+  cell_queue_append(&cq, pc3);
+  cell_queue_append(&cq, pc2);
+  cell_queue_append(&cq, pc1);
+  tt_int_op(cq.n, ==, 4);
+  tt_ptr_op(pc4, ==, cell_queue_pop(&cq));
+  tt_ptr_op(pc3, ==, cell_queue_pop(&cq));
+  tt_ptr_op(pc2, ==, cell_queue_pop(&cq));
+  tt_ptr_op(pc1, ==, cell_queue_pop(&cq));
+  tt_int_op(cq.n, ==, 0);
+  tt_ptr_op(NULL, ==, cell_queue_pop(&cq));
+
+  /* Try a packed copy (wide, then narrow, which is a bit of a cheat, since a
+   * real cell queue has only one type.) */
+  memset(&cell, 0, sizeof(cell));
+  cell.circ_id = 0x12345678;
+  cell.command = 10;
+  strlcpy((char*)cell.payload, "Lorax ipsum gruvvulus thneed amet, snergelly "
+          "once-ler lerkim, sed do barbaloot tempor gluppitus ut labore et "
+          "truffula magna aliqua.",
+          sizeof(cell.payload));
+  cell_queue_append_packed_copy(&cq, &cell, 1 /*wide*/, 0 /*stats*/);
+  cell.circ_id = 0x2013;
+  cell_queue_append_packed_copy(&cq, &cell, 0 /*wide*/, 0 /*stats*/);
+  tt_int_op(cq.n, ==, 2);
+
+  pc_tmp = cell_queue_pop(&cq);
+  tt_int_op(cq.n, ==, 1);
+  tt_ptr_op(pc_tmp, !=, NULL);
+  test_mem_op(pc_tmp->body, ==, "\x12\x34\x56\x78\x0a", 5);
+  test_mem_op(pc_tmp->body+5, ==, cell.payload, sizeof(cell.payload));
+  packed_cell_free(pc_tmp);
+
+  pc_tmp = cell_queue_pop(&cq);
+  tt_int_op(cq.n, ==, 0);
+  tt_ptr_op(pc_tmp, !=, NULL);
+  test_mem_op(pc_tmp->body, ==, "\x20\x13\x0a", 3);
+  test_mem_op(pc_tmp->body+3, ==, cell.payload, sizeof(cell.payload));
+  packed_cell_free(pc_tmp);
+  pc_tmp = NULL;
+
+  tt_ptr_op(NULL, ==, cell_queue_pop(&cq));
+
+  /* Now make sure cell_queue_clear works. */
+  cell_queue_append(&cq, pc2);
+  cell_queue_append(&cq, pc1);
+  tt_int_op(cq.n, ==, 2);
+  cell_queue_clear(&cq);
+  pc2 = pc1 = NULL; /* prevent double-free */
+  tt_int_op(cq.n, ==, 0);
+
+ done:
+  packed_cell_free(pc1);
+  packed_cell_free(pc2);
+  packed_cell_free(pc3);
+  packed_cell_free(pc4);
+  packed_cell_free(pc_tmp);
+
+  cell_queue_clear(&cq);
+  free_cell_pool();
+}
+
+static void
+test_circuit_n_cells(void *arg)
+{
+  packed_cell_t *pc1=NULL, *pc2=NULL, *pc3=NULL, *pc4=NULL, *pc5=NULL;
+  origin_circuit_t *origin_c=NULL;
+  or_circuit_t *or_c=NULL;
+
+  (void)arg;
+
+  init_cell_pool();
+
+  pc1 = packed_cell_new();
+  pc2 = packed_cell_new();
+  pc3 = packed_cell_new();
+  pc4 = packed_cell_new();
+  pc5 = packed_cell_new();
+  tt_assert(pc1 && pc2 && pc3 && pc4 && pc5);
+
+  or_c = or_circuit_new(0, NULL);
+  origin_c = origin_circuit_new();
+  origin_c->base_.purpose = CIRCUIT_PURPOSE_C_GENERAL;
+
+  tt_int_op(n_cells_in_circ_queues(TO_CIRCUIT(or_c)), ==, 0);
+  cell_queue_append(&or_c->p_chan_cells, pc1);
+  tt_int_op(n_cells_in_circ_queues(TO_CIRCUIT(or_c)), ==, 1);
+  cell_queue_append(&or_c->base_.n_chan_cells, pc2);
+  cell_queue_append(&or_c->base_.n_chan_cells, pc3);
+  tt_int_op(n_cells_in_circ_queues(TO_CIRCUIT(or_c)), ==, 3);
+
+  tt_int_op(n_cells_in_circ_queues(TO_CIRCUIT(origin_c)), ==, 0);
+  cell_queue_append(&origin_c->base_.n_chan_cells, pc4);
+  cell_queue_append(&origin_c->base_.n_chan_cells, pc5);
+  tt_int_op(n_cells_in_circ_queues(TO_CIRCUIT(origin_c)), ==, 2);
+
+ done:
+  circuit_free(TO_CIRCUIT(or_c));
+  circuit_free(TO_CIRCUIT(origin_c));
+
+  free_cell_pool();
+}
+
+struct testcase_t cell_queue_tests[] = {
+  { "basic", test_cq_manip, TT_FORK, NULL, NULL, },
+  { "circ_n_cells", test_circuit_n_cells, TT_FORK, NULL, NULL },
+  END_OF_TESTCASES
+};
+