commit 1a74360c2dd5c197e2dfc28b37961c77bb7792f1 Author: Nick Mathewson nickm@torproject.org Date: Mon Sep 9 13:48:44 2013 -0400

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. --- src/common/container.c | 20 ++++++++++++++++ src/common/container.h | 1 + src/or/channel.c | 4 ++-- src/or/circuitlist.c | 61 ++++++++++++++++++++++++++++++++++++++++++++---- src/or/circuitmux.c | 11 ++++++++- src/or/circuitmux.h | 3 ++- src/or/relay.c | 10 +++++--- src/or/relay.h | 2 +- 8 files changed, 100 insertions(+), 12 deletions(-)

diff --git a/src/common/container.c b/src/common/container.c index f489430..b937d54 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -727,6 +727,26 @@ smartlist_uniq_strings(smartlist_t *sl) smartlist_uniq(sl, compare_string_ptrs_, tor_free_); }

+/** Helper: compare two pointers. */ +static int +compare_ptrs_(const void **_a, const void **_b) +{ + const void *a = *_a, *b = *_b; + if (a<b) + return -1; + else if (a==b) + return 0; + else + return 1; +} + +/** Sort <b>sl</b> in ascending order of the pointers it contains. */ +void +smartlist_sort_pointers(smartlist_t *sl) +{ + smartlist_sort(sl, compare_ptrs_); +} + /* Heap-based priority queue implementation for O(lg N) insert and remove. * Recall that the heap property is that, for every index I, h[I] < * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]]. diff --git a/src/common/container.h b/src/common/container.h index 93f0b71..0d31f20 100644 --- a/src/common/container.h +++ b/src/common/container.h @@ -103,6 +103,7 @@ void smartlist_uniq(smartlist_t *sl, void smartlist_sort_strings(smartlist_t *sl); void smartlist_sort_digests(smartlist_t *sl); void smartlist_sort_digests256(smartlist_t *sl); +void smartlist_sort_pointers(smartlist_t *sl);

char *smartlist_get_most_frequent_string(smartlist_t *sl); char *smartlist_get_most_frequent_digest256(smartlist_t *sl); diff --git a/src/or/channel.c b/src/or/channel.c index 9f68875..32e87c3 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 b2eb730..0015a68 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 f2af943..2d05c74 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 ee2f5d1..c4c0649 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 d6742d2..8c009b5 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 2c7d0d8..4e1c7f5 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,