Test code for implementation of faster circuit_unlink_all_from_channel

This contains the obvious implementation using the circuitmux data
structure.  It also runs the old (slow) algorithm and compares
the results of the two to make sure that they're the same.

Needs review and testing.

6 files changed, 79 insertions, 12 deletions

diff --git a/src/or/channel.c b/src/or/channel.c
index 9f6887588e..32e87c342c 100644
--- a/src/or/channel.c
+++ b/src/or/channel.c
@@ -800,7 +800,7 @@ channel_free(channel_t *chan)
 
   /* Get rid of cmux */
   if (chan->cmux) {
-    circuitmux_detach_all_circuits(chan->cmux);
+    circuitmux_detach_all_circuits(chan->cmux, NULL);
     circuitmux_mark_destroyed_circids_usable(chan->cmux, chan);
     circuitmux_free(chan->cmux);
     chan->cmux = NULL;
@@ -2860,7 +2860,7 @@ channel_free_list(smartlist_t *channels, int mark_for_close)
               channel_state_to_string(curr->state), curr->state);
     /* Detach circuits early so they can find the channel */
     if (curr->cmux) {
-      circuitmux_detach_all_circuits(curr->cmux);
+      circuitmux_detach_all_circuits(curr->cmux, NULL);
     }
     channel_unregister(curr);
     if (mark_for_close) {
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index b2eb730c8c..0015a680cf 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -1144,12 +1144,58 @@ void
 circuit_unlink_all_from_channel(channel_t *chan, int reason)
 {
   circuit_t *circ;
+  smartlist_t *detached = smartlist_new();
 
-  channel_unlink_all_circuits(chan);
+#define DEBUG_CIRCUIT_UNLINK_ALL
 
-  TOR_LIST_FOREACH(circ, &global_circuitlist, head) {
+  channel_unlink_all_circuits(chan, detached);
+
+#ifdef DEBUG_CIRCUIT_UNLINK_ALL
+  {
+    smartlist_t *detached_2 = smartlist_new();
+    int mismatch = 0, badlen = 0;
+
+    TOR_LIST_FOREACH(circ, &global_circuitlist, head) {
+      if (circ->n_chan == chan ||
+          (!CIRCUIT_IS_ORIGIN(circ) &&
+           TO_OR_CIRCUIT(circ)->p_chan == chan)) {
+        smartlist_add(detached_2, circ);
+      }
+    }
+
+    if (smartlist_len(detached) != smartlist_len(detached_2)) {
+       log_warn(LD_BUG, "List of detached circuits had the wrong length! "
+                "(got %d, should have gotten %d)",
+                (int)smartlist_len(detached),
+                (int)smartlist_len(detached_2));
+       badlen = 1;
+    }
+    smartlist_sort_pointers(detached);
+    smartlist_sort_pointers(detached_2);
+
+    SMARTLIST_FOREACH(detached, circuit_t *, c,
+        if (c != smartlist_get(detached_2, c_sl_idx))
+          mismatch = 1;
+    );
+
+    if (mismatch)
+      log_warn(LD_BUG, "Mismatch in list of detached circuits.");
+
+    if (badlen || mismatch) {
+      smartlist_free(detached);
+      detached = detached_2;
+    } else {
+      log_notice(LD_CIRC, "List of %d circuits was as expected.",
+                (int)smartlist_len(detached));
+      smartlist_free(detached_2);
+    }
+  }
+#endif
+
+  SMARTLIST_FOREACH_BEGIN(detached, circuit_t *, circ) {
     int mark = 0;
     if (circ->n_chan == chan) {
+
       circuit_set_n_circid_chan(circ, 0, NULL);
       mark = 1;
 
@@ -1165,9 +1211,16 @@ circuit_unlink_all_from_channel(channel_t *chan, int reason)
         mark = 1;
       }
     }
-    if (mark && !circ->marked_for_close)
+    if (!mark) {
+      log_warn(LD_BUG, "Circuit on detached list which I had no reason "
+          "to mark");
+      continue;
+    }
+    if (!circ->marked_for_close)
       circuit_mark_for_close(circ, reason);
-  }
+  } SMARTLIST_FOREACH_END(circ);
+
+  smartlist_free(detached);
 }
 
 /** Return a circ such that
diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c
index f2af943937..2d05c748ec 100644
--- a/src/or/circuitmux.c
+++ b/src/or/circuitmux.c
@@ -390,10 +390,13 @@ circuitmux_alloc(void)
 
 /**
  * Detach all circuits from a circuitmux (use before circuitmux_free())
+ *
+ * If <b>detached_out</b> is non-NULL, add every detached circuit_t to
+ * detached_out.
  */
 
 void
-circuitmux_detach_all_circuits(circuitmux_t *cmux)
+circuitmux_detach_all_circuits(circuitmux_t *cmux, smartlist_t *detached_out)
 {
   chanid_circid_muxinfo_t **i = NULL, *to_remove;
   channel_t *chan = NULL;
@@ -430,6 +433,9 @@ circuitmux_detach_all_circuits(circuitmux_t *cmux)
 
             /* Clear n_mux */
             circ->n_mux = NULL;
+
+            if (detached_out)
+              smartlist_add(detached_out, circ);
           } else if (circ->magic == OR_CIRCUIT_MAGIC) {
             /*
              * Update active_circuits et al.; this does policy notifies, so
@@ -445,6 +451,9 @@ circuitmux_detach_all_circuits(circuitmux_t *cmux)
              * so clear p_mux.
              */
             TO_OR_CIRCUIT(circ)->p_mux = NULL;
+
+            if (detached_out)
+              smartlist_add(detached_out, circ);
           } else {
             /* Complain and move on */
             log_warn(LD_CIRC,
diff --git a/src/or/circuitmux.h b/src/or/circuitmux.h
index ee2f5d1535..c4c0649c6c 100644
--- a/src/or/circuitmux.h
+++ b/src/or/circuitmux.h
@@ -99,7 +99,8 @@ void circuitmux_assert_okay(circuitmux_t *cmux);
 
 /* Create/destroy */
 circuitmux_t * circuitmux_alloc(void);
-void circuitmux_detach_all_circuits(circuitmux_t *cmux);
+void circuitmux_detach_all_circuits(circuitmux_t *cmux,
+                                    smartlist_t *detached_out);
 void circuitmux_free(circuitmux_t *cmux);
 
 /* Policy control */
diff --git a/src/or/relay.c b/src/or/relay.c
index d6742d25e1..8c009b5564 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -2271,14 +2271,18 @@ update_circuit_on_cmux_(circuit_t *circ, cell_direction_t direction,
   assert_cmux_ok_paranoid(chan);
 }
 
-/** Remove all circuits from the cmux on <b>chan</b>. */
+/** Remove all circuits from the cmux on <b>chan</b>.
+ *
+ * If <b>circuits_out</b> is non-NULL, add all detached circuits to
+ * <b>circuits_out</b>.
+ **/
 void
-channel_unlink_all_circuits(channel_t *chan)
+channel_unlink_all_circuits(channel_t *chan, smartlist_t *circuits_out)
 {
   tor_assert(chan);
   tor_assert(chan->cmux);
 
-  circuitmux_detach_all_circuits(chan->cmux);
+  circuitmux_detach_all_circuits(chan->cmux, circuits_out);
   chan->num_n_circuits = 0;
   chan->num_p_circuits = 0;
 }
diff --git a/src/or/relay.h b/src/or/relay.h
index 2c7d0d8ae4..4e1c7f5091 100644
--- a/src/or/relay.h
+++ b/src/or/relay.h
@@ -61,7 +61,7 @@ void cell_queue_append_packed_copy(circuit_t *circ, cell_queue_t *queue,
 void append_cell_to_circuit_queue(circuit_t *circ, channel_t *chan,
                                   cell_t *cell, cell_direction_t direction,
                                   streamid_t fromstream);
-void channel_unlink_all_circuits(channel_t *chan);
+void channel_unlink_all_circuits(channel_t *chan, smartlist_t *detached_out);
 int channel_flush_from_first_active_circuit(channel_t *chan, int max);
 void assert_circuit_mux_okay(channel_t *chan);
 void update_circuit_on_cmux_(circuit_t *circ, cell_direction_t direction,