October 2012 - tor-commits - lists.torproject.org

[tor/master] Implement circuitmux policy basic notifications mechanism
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit 851734d3245dfd56be02f6f4a78a3b776f4ebedc Author: Andrea Shepard <andrea(a)torproject.org> Date: Thu Sep 27 11:38:27 2012 -0700 Implement circuitmux policy basic notifications mechanism --- src/or/circuitmux.c | 59 +++++++++++++++++++++++++++++++++++++------------- src/or/circuitmux.h | 57 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 100 insertions(+), 16 deletions(-) diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c index 77bb568..860ba64 100644 --- a/src/or/circuitmux.c +++ b/src/or/circuitmux.c @@ -88,21 +88,14 @@ struct circuitmux_s { struct circuit_t *active_circuits_head, *active_circuits_tail; /* - * Priority queue of cell_ewma_t for circuits with queued cells waiting - * for room to free up on this connection's outbuf. Kept in heap order - * according to EWMA. - * - * This is redundant with active_circuits; if we ever decide only to use - * the cell_ewma algorithm for choosing circuits, we can remove - * active_circuits. + * Circuitmux policy; if this is non-NULL, it can override the built- + * in round-robin active circuits behavior. This is how EWMA works in + * the new circuitmux_t world. */ - smartlist_t *active_circuit_pqueue; + const circuitmux_policy_t *policy; - /* - * The tick on which the cell_ewma_ts in active_circuit_pqueue last had - * their ewma values rescaled. - */ - unsigned int active_circuit_pqueue_last_recalibrated; + /* Policy-specific data */ + circuitmux_policy_data_t *policy_data; }; /* @@ -115,6 +108,8 @@ struct circuit_muxinfo_s { unsigned int cell_count; /* Direction of flow */ cell_direction_t direction; + /* Policy-specific data */ + circuitmux_policy_circ_data_t *policy_data; }; /* @@ -321,7 +316,13 @@ circuitmux_free(circuitmux_t *cmux) tor_assert(cmux->n_circuits == 0); tor_assert(cmux->n_active_circuits == 0); - smartlist_free(cmux->active_circuit_pqueue); + /* Free policy-specific data if we have any */ + if (cmux->policy && cmux->policy->free_cmux_data) { + if (cmux->policy_data) { + cmux->policy->free_cmux_data(cmux, cmux->policy_data); + cmux->policy_data = NULL; + } + } else tor_assert(cmux->policy_data == NULL); if (cmux->chanid_circid_map) { HT_CLEAR(chanid_circid_muxinfo_map, cmux->chanid_circid_map); @@ -718,6 +719,7 @@ circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ, { circuit_t **next_active = NULL, **prev_active = NULL, **next_prev = NULL; circuitmux_t *circuit_cmux = NULL; + chanid_circid_muxinfo_t *hashent = NULL; channel_t *chan = NULL; circid_t circ_id; int already_active; @@ -782,7 +784,19 @@ circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ, /* This becomes the new head of the list */ cmux->active_circuits_head = circ; - /* TODO policy-specific notifications */ + /* Policy-specific notification */ + if (cmux->policy && + cmux->policy->notify_circ_active && + cmux->policy_data) { + /* Okay, we need to check the circuit for policy data now */ + hashent = circuitmux_find_map_entry(cmux, circ); + /* We should have found something */ + tor_assert(hashent); + /* Check for policy data for the circuit and notify */ + if (hashent->muxinfo.policy_data) + cmux->policy->notify_circ_active(cmux, cmux->policy_data, + circ, hashent->muxinfo.policy_data); + } } /** @@ -797,6 +811,7 @@ circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ, circuit_t **next_active = NULL, **prev_active = NULL; circuit_t **next_prev = NULL, **prev_next = NULL; circuitmux_t *circuit_cmux = NULL; + chanid_circid_muxinfo_t *hashent = NULL; channel_t *chan = NULL; circid_t circ_id; int already_inactive; @@ -878,7 +893,19 @@ circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ, *prev_active = NULL; *next_active = NULL; - /* TODO policy-specific notifications */ + /* Policy-specific notification */ + if (cmux->policy && + cmux->policy->notify_circ_inactive && + cmux->policy_data) { + /* Okay, we need to check the circuit for policy data now */ + hashent = circuitmux_find_map_entry(cmux, circ); + /* We should have found something */ + tor_assert(hashent); + /* Check for policy data for the circuit and notify */ + if (hashent->muxinfo.policy_data) + cmux->policy->notify_circ_inactive(cmux, cmux->policy_data, + circ, hashent->muxinfo.policy_data); + } } /** diff --git a/src/or/circuitmux.h b/src/or/circuitmux.h index ade544f..e344b6e 100644 --- a/src/or/circuitmux.h +++ b/src/or/circuitmux.h @@ -11,6 +11,57 @@ #include "or.h" +typedef struct circuitmux_policy_s circuitmux_policy_t; +typedef struct circuitmux_policy_data_s circuitmux_policy_data_t; +typedef struct circuitmux_policy_circ_data_s circuitmux_policy_circ_data_t; + +struct circuitmux_policy_s { + /* Allocate cmux-wide policy-specific data */ + circuitmux_policy_data_t * (*alloc_cmux_data)(circuitmux_t *cmux); + /* Free cmux-wide policy-specific data */ + void (*free_cmux_data)(circuitmux_t *cmux, + circuitmux_policy_data_t *pol_data); + /* Allocate circuit policy-specific data for a newly attached circuit */ + circuitmux_policy_circ_data_t * + (*alloc_circ_data)(circuitmux_t *cmux, + circuitmux_policy_data_t *pol_data, + circuit_t *circ, + cell_direction_t direction, + unsigned int cell_count); + /* Free circuit policy-specific data */ + void (*free_circ_data)(circuitmux_t *cmux, + circuitmux_policy_data_t *pol_data, + circuit_t *circ, + circuitmux_policy_circ_data_t *pol_circ_data); + /* Notify that a circuit has become active/inactive */ + void (*notify_circ_active)(circuitmux_t *cmux, + circuitmux_policy_data_t *pol_data, + circuit_t *circ, + circuitmux_policy_circ_data_t *pol_circ_data); + void (*notify_circ_inactive)(circuitmux_t *cmux, + circuitmux_policy_data_t *pol_data, + circuit_t *circ, + circuitmux_policy_circ_data_t *pol_circ_data); +}; + +/* + * Circuitmux policy implementations can subclass this to store circuitmux- + * wide data; it just has the magic number in the base struct. + */ + +struct circuitmux_policy_data_s { + uint32_t magic; +}; + +/* + * Circuitmux policy implementations can subclass this to store circuit- + * specific data; it just has the magic number in the base struct. + */ + +struct circuitmux_policy_circ_data_s { + uint32_t magic; +}; + /* Consistency check */ void circuitmux_assert_okay(circuitmux_t *cmux); @@ -19,6 +70,12 @@ circuitmux_t * circuitmux_alloc(void); void circuitmux_detach_all_circuits(circuitmux_t *cmux); void circuitmux_free(circuitmux_t *cmux); +/* Policy control */ +void circuitmux_clear_policy(circuitmux_t *cmux); +const circuitmux_policy_t * circuitmux_get_policy(circuitmux_t *cmux); +void circuitmux_set_policy(circuitmux_t *cmux, + const circuitmux_policy_t *pol); + /* Status inquiries */ cell_direction_t circuitmux_attached_circuit_direction( circuitmux_t *cmux,

1 0

[tor/master] Implement circuitmux_clear_policy(), circuitmux_get_policy() and circuitmux_set_policy() in circuitmux.c
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit 86d9d85dfc177b7a24051f64a5c35997de5c9ac9 Author: Andrea Shepard <andrea(a)torproject.org> Date: Thu Sep 27 13:42:47 2012 -0700 Implement circuitmux_clear_policy(), circuitmux_get_policy() and circuitmux_set_policy() in circuitmux.c --- src/or/circuitmux.c | 159 ++++++++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 158 insertions(+), 1 deletions(-) diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c index 53d3a1b..4e33569 100644 --- a/src/or/circuitmux.c +++ b/src/or/circuitmux.c @@ -343,7 +343,13 @@ circuitmux_free(circuitmux_t *cmux) tor_assert(cmux->n_circuits == 0); tor_assert(cmux->n_active_circuits == 0); - /* Free policy-specific data if we have any */ + /* + * Free policy-specific data if we have any; we don't + * need to do circuitmux_set_policy(cmux, NULL) to cover + * the circuits because they would have been handled in + * circuitmux_detach_all_circuits() before this was + * called. + */ if (cmux->policy && cmux->policy->free_cmux_data) { if (cmux->policy_data) { cmux->policy->free_cmux_data(cmux, cmux->policy_data); @@ -360,6 +366,157 @@ circuitmux_free(circuitmux_t *cmux) } /* + * Circuitmux policy control functions + */ + +/** + * Remove any policy installed on cmux; all policy data will be freed and + * cmux behavior will revert to the built-in round-robin active_circuits + * mechanism. + */ + +void +circuitmux_clear_policy(circuitmux_t *cmux) +{ + tor_assert(cmux); + + /* Internally, this is just setting policy to NULL */ + if (cmux->policy) { + circuitmux_set_policy(cmux, NULL); + } +} + +/** + * Return the policy currently installed on a circuitmux_t + */ + +const circuitmux_policy_t * +circuitmux_get_policy(circuitmux_t *cmux) +{ + tor_assert(cmux); + + return cmux->policy; +} + +/** + * Set policy; allocate for new policy, detach all circuits from old policy + * if any, attach them to new policy, and free old policy data. + */ + +void +circuitmux_set_policy(circuitmux_t *cmux, + const circuitmux_policy_t *pol) +{ + const circuitmux_policy_t *old_pol = NULL, *new_pol = NULL; + circuitmux_policy_data_t *old_pol_data = NULL, *new_pol_data = NULL; + chanid_circid_muxinfo_t **i = NULL; + channel_t *chan = NULL; + uint64_t last_chan_id_searched = 0; + circuit_t *circ = NULL; + + tor_assert(cmux); + + /* Set up variables */ + old_pol = cmux->policy; + old_pol_data = cmux->policy_data; + new_pol = pol; + + /* Check if this is the trivial case */ + if (old_pol == new_pol) return; + + /* Allocate data for new policy, if any */ + if (new_pol && new_pol->alloc_cmux_data) { + /* + * If alloc_cmux_data is not null, then we expect to get some policy + * data. Assert that we also have free_cmux_data so we can free it + * when the time comes, and allocate it. + */ + tor_assert(new_pol->free_cmux_data); + new_pol_data = new_pol->alloc_cmux_data(cmux); + tor_assert(new_pol_data); + } + + /* Install new policy and new policy data on cmux */ + cmux->policy = new_pol; + cmux->policy_data = new_pol_data; + + /* Iterate over all circuits, attaching/detaching each one */ + i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map); + while (i) { + /* Assert that this entry isn't NULL */ + tor_assert(*i); + + /* + * Get the channel; since normal case is all circuits on the mux share a + * channel, we cache last_chan_id_searched + */ + if (!chan || last_chan_id_searched != (*i)->chan_id) { + chan = channel_find_by_global_id((*i)->chan_id); + last_chan_id_searched = (*i)->chan_id; + } + tor_assert(chan); + + /* Get the circuit */ + circ = circuit_get_by_circid_channel((*i)->circ_id, chan); + tor_assert(circ); + + /* Need to tell old policy it becomes inactive (i.e., it is active) ? */ + if (old_pol && old_pol->notify_circ_inactive && + (*i)->muxinfo.cell_count > 0) { + old_pol->notify_circ_inactive(cmux, old_pol_data, circ, + (*i)->muxinfo.policy_data); + } + + /* Need to free old policy data? */ + if ((*i)->muxinfo.policy_data) { + /* Assert that we have the means to free it if we have policy data */ + tor_assert(old_pol); + tor_assert(old_pol->free_circ_data); + /* Free it */ + old_pol->free_circ_data(cmux, old_pol_data, circ, + (*i)->muxinfo.policy_data); + (*i)->muxinfo.policy_data = NULL; + } + + /* Need to allocate new policy data? */ + if (new_pol && new_pol->alloc_circ_data) { + /* + * If alloc_circ_data is not null, we expect to get some per-circuit + * policy data. Assert that we also have free_circ_data so we can + * free it when the time comes, and allocate it. + */ + tor_assert(new_pol->free_circ_data); + (*i)->muxinfo.policy_data = + new_pol->alloc_circ_data(cmux, new_pol_data, circ, + (*i)->muxinfo.direction, + (*i)->muxinfo.cell_count); + } + + /* Need to make active on new policy? */ + if (new_pol && new_pol->notify_circ_active && + (*i)->muxinfo.cell_count > 0) { + new_pol->notify_circ_active(cmux, new_pol_data, circ, + (*i)->muxinfo.policy_data); + } + + /* Advance to next circuit map entry */ + i = HT_NEXT(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i); + } + + /* Free data for old policy, if any */ + if (old_pol_data) { + /* + * If we had old policy data, we should have an old policy and a free + * function for it. + */ + tor_assert(old_pol); + tor_assert(old_pol->free_cmux_data); + old_pol->free_cmux_data(cmux, old_pol_data); + old_pol_data = NULL; + } +} + +/* * Circuitmux/circuit attachment status inquiry functions */

1 0

[tor/master] Implement circuitmux_notify_xmit_cells() and circuitmux_move_active_circ_to_tail() helper in circuitmux.c
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit aff77eb1a9dcbdf723d3f8e74e6502e5047bbe63 Author: Andrea Shepard <andrea(a)torproject.org> Date: Thu Sep 27 15:04:46 2012 -0700 Implement circuitmux_notify_xmit_cells() and circuitmux_move_active_circ_to_tail() helper in circuitmux.c --- src/or/circuitmux.c | 133 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 133 insertions(+), 0 deletions(-) diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c index b5dda9e..deb5bf1 100644 --- a/src/or/circuitmux.c +++ b/src/or/circuitmux.c @@ -141,6 +141,9 @@ circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ, static void circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ, cell_direction_t direction); +static INLINE void +circuitmux_move_active_circ_to_tail(circuitmux_t *cmux, circuit_t *circ, + cell_direction_t direction); static INLINE circuit_t ** circuitmux_next_active_circ_p(circuitmux_t *cmux, circuit_t *circ); static INLINE circuit_t ** @@ -152,6 +155,72 @@ circuitmux_prev_active_circ_p(circuitmux_t *cmux, circuit_t *circ); * Linked list helpers */ +static INLINE void +circuitmux_move_active_circ_to_tail(circuitmux_t *cmux, circuit_t *circ, + cell_direction_t direction) +{ + circuit_t **next_p = NULL, **prev_p = NULL; + circuit_t **next_prev = NULL, **prev_next = NULL; + or_circuit_t *or_circ = NULL; + + tor_assert(cmux); + tor_assert(circ); + + /* Figure out our next_p and prev_p for this cmux/direction */ + if (direction) { + if (direction == CELL_DIRECTION_OUT) { + tor_assert(circ->n_mux == cmux); + next_p = &(circ->next_active_on_n_chan); + prev_p = &(circ->prev_active_on_n_chan); + } else { + or_circ = TO_OR_CIRCUIT(circ); + tor_assert(or_circ->p_mux == cmux); + next_p = &(or_circ->next_active_on_p_chan); + prev_p = &(or_circ->prev_active_on_p_chan); + } + } else { + if (circ->n_mux == cmux) { + next_p = &(circ->next_active_on_n_chan); + prev_p = &(circ->prev_active_on_n_chan); + direction = CELL_DIRECTION_OUT; + } else { + or_circ = TO_OR_CIRCUIT(circ); + tor_assert(or_circ->p_mux == cmux); + next_p = &(or_circ->next_active_on_p_chan); + prev_p = &(or_circ->prev_active_on_p_chan); + direction = CELL_DIRECTION_IN; + } + } + tor_assert(next_p); + tor_assert(prev_p); + + /* Check if this really is an active circuit */ + if ((*next_p == NULL && *prev_p == NULL) && + !(circ == cmux->active_circuits_head || + circ == cmux->active_circuits_tail)) { + /* Not active, no-op */ + return; + } + + /* Check if this is already the tail */ + if (circ == cmux->active_circuits_tail) return; + + /* Okay, we have to move it; figure out next_prev and prev_next */ + if (*next_p) next_prev = circuitmux_prev_active_circ_p(cmux, *next_p); + if (*prev_p) prev_next = circuitmux_next_active_circ_p(cmux, *prev_p); + /* Adjust the previous node's next pointer, if any */ + if (prev_next) *prev_next = *next_p; + /* Otherwise, we were the head */ + else cmux->active_circuits_head = *next_p; + /* Adjust the next node's previous pointer, if any */ + if (next_prev) *next_prev = *prev_p; + /* Adjust our next and prev pointers */ + *next_p = NULL; + *prev_p = cmux->active_circuits_tail; + /* Set the tail to this circuit */ + cmux->active_circuits_tail = circ; +} + static INLINE circuit_t ** circuitmux_next_active_circ_p(circuitmux_t *cmux, circuit_t *circ) { @@ -1175,3 +1244,67 @@ circuitmux_set_num_cells(circuitmux_t *cmux, circuit_t *circ, hashent->muxinfo.cell_count = n_cells; } +/* + * Functions for channel code to call to get a circuit to transmit from or + * notify that cells have been transmitted. + */ + +void +circuitmux_notify_xmit_cells(circuitmux_t *cmux, circuit_t *circ, + unsigned int n_cells) +{ + chanid_circid_muxinfo_t *hashent = NULL; + int becomes_inactive = 0; + + tor_assert(cmux); + tor_assert(circ); + + if (n_cells == 0) return; + + /* + * To handle this, we have to: + * + * 1.) Adjust the circuit's cell counter in the cmux hash table + * 2.) Move the circuit to the tail of the active_circuits linked list + * for this cmux, or make the circuit inactive if the cell count + * went to zero. + * 3.) Call cmux->policy->notify_xmit_cells(), if any + */ + + /* Find the hash entry */ + hashent = circuitmux_find_map_entry(cmux, circ); + /* Assert that we found one */ + tor_assert(hashent); + + /* Adjust the cell counter and assert that we had that many cells to send */ + tor_assert(n_cells <= hashent->muxinfo.cell_count); + hashent->muxinfo.cell_count -= n_cells; + /* Do we need to make the circuit inactive? */ + if (hashent->muxinfo.cell_count == 0) becomes_inactive = 1; + + /* If we aren't making it inactive later, move it to the tail of the list */ + if (!becomes_inactive) { + circuitmux_move_active_circ_to_tail(cmux, circ, + hashent->muxinfo.direction); + } + + /* + * We call notify_xmit_cells() before making the circuit inactive if needed, + * so the policy can always count on this coming in on an active circuit. + */ + if (cmux->policy && cmux->policy->notify_xmit_cells) { + cmux->policy->notify_xmit_cells(cmux, cmux->policy_data, circ, + hashent->muxinfo.policy_data, + n_cells); + } + + /* + * Now make the circuit inactive if needed; this will call the policy's + * notify_circ_inactive() if present. + */ + if (becomes_inactive) { + --(cmux->n_active_circuits); + circuitmux_make_circuit_inactive(cmux, circ, hashent->muxinfo.direction); + } +} +

1 0

[tor/master] Implement circuitmux_get_first_active_circuit() in circuitmux.c; add pick_active_circuit() to circuitmux_policy_t in circuitmux.h
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit 4a14c6aa67df6ced083e2d6a6e66dbf443a40e75 Author: Andrea Shepard <andrea(a)torproject.org> Date: Fri Sep 28 16:56:46 2012 -0700 Implement circuitmux_get_first_active_circuit() in circuitmux.c; add pick_active_circuit() to circuitmux_policy_t in circuitmux.h --- src/or/circuitmux.c | 32 ++++++++++++++++++++++++++++++-- src/or/circuitmux.h | 3 +++ 2 files changed, 33 insertions(+), 2 deletions(-) diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c index 824bf0b..4500c6a 100644 --- a/src/or/circuitmux.c +++ b/src/or/circuitmux.c @@ -359,7 +359,6 @@ circuitmux_detach_all_circuits(circuitmux_t *cmux) U64_PRINTF_ARG(to_remove->chan_id)); } - /* Free policy-specific data if we have it */ if (to_remove->muxinfo.policy_data) { /* @@ -1255,6 +1254,35 @@ circuitmux_set_num_cells(circuitmux_t *cmux, circuit_t *circ, */ /** + * Pick a circuit to send from, using the active circuits list or a + * circuitmux policy if one is available. This is called from channel.c. + */ + +circuit_t * +circuitmux_get_first_active_circuit(circuitmux_t *cmux) +{ + circuit_t *circ = NULL; + + tor_assert(cmux); + + if (cmux->n_active_circuits > 0) { + /* We also must have a cell available for this to be the case */ + tor_assert(cmux->n_cells > 0); + /* Do we have a policy-provided circuit selector? */ + if (cmux->policy && cmux->policy->pick_active_circuit) { + circ = cmux->policy->pick_active_circuit(cmux, cmux->policy_data); + } + /* Fall back on the head of the active circuits list */ + if (!circ) { + tor_assert(cmux->active_circuits_head); + circ = cmux->active_circuits_head; + } + } else tor_assert(cmux->n_cells == 0); + + return circ; +} + +/** * Notify the circuitmux that cells have been sent on a circuit; this * is called from channel.c. */ @@ -1310,7 +1338,7 @@ circuitmux_notify_xmit_cells(circuitmux_t *cmux, circuit_t *circ, /* * Now make the circuit inactive if needed; this will call the policy's - * notify_circ_inactive() if present. + * notify_circ_inactive() if present. */ if (becomes_inactive) { --(cmux->n_active_circuits); diff --git a/src/or/circuitmux.h b/src/or/circuitmux.h index dcacb8e..f4eb73e 100644 --- a/src/or/circuitmux.h +++ b/src/or/circuitmux.h @@ -53,6 +53,9 @@ struct circuitmux_policy_s { circuit_t *circ, circuitmux_policy_circ_data_t *pol_circ_data, unsigned int n_cells); + /* Choose a circuit */ + circuit_t * (*pick_active_circuit)(circuitmux_t *cmux, + circuitmux_policy_data_t *pol_data); }; /*

1 0

[tor/master] Add comment for circuitmux_notify_xmit_cells() in circuitmux.c
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit c4e5e4727ddcf639a3a50856f74f24f373262baf Author: Andrea Shepard <andrea(a)torproject.org> Date: Thu Sep 27 15:17:48 2012 -0700 Add comment for circuitmux_notify_xmit_cells() in circuitmux.c --- src/or/circuitmux.c | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-) diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c index c01f38f..824bf0b 100644 --- a/src/or/circuitmux.c +++ b/src/or/circuitmux.c @@ -1254,6 +1254,11 @@ circuitmux_set_num_cells(circuitmux_t *cmux, circuit_t *circ, * notify that cells have been transmitted. */ +/** + * Notify the circuitmux that cells have been sent on a circuit; this + * is called from channel.c. + */ + void circuitmux_notify_xmit_cells(circuitmux_t *cmux, circuit_t *circ, unsigned int n_cells)

1 0

[tor/master] Add comment for circuitmux_move_active_circ_to_tail() in circuitmux.c
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit 741bc97b2414eb8ecfe0367bb75aea376e9ce73b Author: Andrea Shepard <andrea(a)torproject.org> Date: Thu Sep 27 15:09:37 2012 -0700 Add comment for circuitmux_move_active_circ_to_tail() in circuitmux.c --- src/or/circuitmux.c | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-) diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c index deb5bf1..c01f38f 100644 --- a/src/or/circuitmux.c +++ b/src/or/circuitmux.c @@ -155,6 +155,11 @@ circuitmux_prev_active_circ_p(circuitmux_t *cmux, circuit_t *circ); * Linked list helpers */ +/** + * Move an active circuit to the tail of the cmux's active circuits list; + * used by circuitmux_notify_xmit_cells(). + */ + static INLINE void circuitmux_move_active_circ_to_tail(circuitmux_t *cmux, circuit_t *circ, cell_direction_t direction)

1 0

[tor/master] Consistently allow policy alloc_cmux_data() and alloc_circ_data() functions to return NULL if the policy does not use this in circuitmux.c
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit debef8f0cd8fbe72fb40bd811c636bb66c7a9001 Author: Andrea Shepard <andrea(a)torproject.org> Date: Thu Sep 27 13:51:04 2012 -0700 Consistently allow policy alloc_cmux_data() and alloc_circ_data() functions to return NULL if the policy does not use this in circuitmux.c --- src/or/circuitmux.c | 35 ++++++++++++++--------------------- 1 files changed, 14 insertions(+), 21 deletions(-) diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c index 4e33569..b5dda9e 100644 --- a/src/or/circuitmux.c +++ b/src/or/circuitmux.c @@ -293,7 +293,6 @@ circuitmux_detach_all_circuits(circuitmux_t *cmux) * free it */ tor_assert(cmux->policy); - tor_assert(cmux->policy_data); tor_assert(cmux->policy->free_circ_data); /* Call free_circ_data() */ cmux->policy->free_circ_data(cmux, @@ -805,8 +804,10 @@ circuitmux_attach_circuit(circuitmux_t *cmux, circuit_t *circ, hashent->muxinfo.cell_count = cell_count; hashent->muxinfo.direction = direction; /* Allocate policy specific circuit data if we need it */ - if (cmux->policy && cmux->policy_data && - cmux->policy->alloc_circ_data) { + if (cmux->policy && cmux->policy->alloc_circ_data) { + /* Assert that we have the means to free policy-specific data */ + tor_assert(cmux->policy->free_circ_data); + /* Allocate it */ hashent->muxinfo.policy_data = cmux->policy->alloc_circ_data(cmux, cmux->policy_data, @@ -898,7 +899,6 @@ circuitmux_detach_circuit(circuitmux_t *cmux, circuit_t *circ) if (hashent->muxinfo.policy_data) { /* If we have policy data, assert that we have the means to free it */ tor_assert(cmux->policy); - tor_assert(cmux->policy_data); tor_assert(cmux->policy->free_circ_data); /* Call free_circ_data() */ cmux->policy->free_circ_data(cmux, @@ -997,16 +997,14 @@ circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ, /* Policy-specific notification */ if (cmux->policy && - cmux->policy->notify_circ_active && - cmux->policy_data) { + cmux->policy->notify_circ_active) { /* Okay, we need to check the circuit for policy data now */ hashent = circuitmux_find_map_entry(cmux, circ); /* We should have found something */ tor_assert(hashent); - /* Check for policy data for the circuit and notify */ - if (hashent->muxinfo.policy_data) - cmux->policy->notify_circ_active(cmux, cmux->policy_data, - circ, hashent->muxinfo.policy_data); + /* Notify */ + cmux->policy->notify_circ_active(cmux, cmux->policy_data, + circ, hashent->muxinfo.policy_data); } } @@ -1106,16 +1104,14 @@ circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ, /* Policy-specific notification */ if (cmux->policy && - cmux->policy->notify_circ_inactive && - cmux->policy_data) { + cmux->policy->notify_circ_inactive) { /* Okay, we need to check the circuit for policy data now */ hashent = circuitmux_find_map_entry(cmux, circ); /* We should have found something */ tor_assert(hashent); - /* Check for policy data for the circuit and notify */ - if (hashent->muxinfo.policy_data) - cmux->policy->notify_circ_inactive(cmux, cmux->policy_data, - circ, hashent->muxinfo.policy_data); + /* Notify */ + cmux->policy->notify_circ_inactive(cmux, cmux->policy_data, + circ, hashent->muxinfo.policy_data); } } @@ -1153,11 +1149,8 @@ circuitmux_set_num_cells(circuitmux_t *cmux, circuit_t *circ, cmux->n_cells += n_cells; /* Do we need to notify a cmux policy? */ - if (cmux->policy && cmux->policy_data && - cmux->policy->notify_set_n_cells) { - /* Yeah; assert that we have circuit policy data */ - tor_assert(hashent->muxinfo.policy_data); - /* ... and call notify_set_n_cells */ + if (cmux->policy && cmux->policy->notify_set_n_cells) { + /* Call notify_set_n_cells */ cmux->policy->notify_set_n_cells(cmux, cmux->policy_data, circ,

1 0

[tor/master] Implement circuitmux_assert_okay() and helper functions in circuitmux.c
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit 34591c61efcdd241e0c89006eeb9ae4cdf7565c0 Author: Andrea Shepard <andrea(a)torproject.org> Date: Sun Sep 30 21:24:04 2012 -0700 Implement circuitmux_assert_okay() and helper functions in circuitmux.c --- src/or/circuitmux.c | 286 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 286 insertions(+), 0 deletions(-) diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c index 4500c6a..b16eb63 100644 --- a/src/or/circuitmux.c +++ b/src/or/circuitmux.c @@ -110,6 +110,8 @@ struct circuit_muxinfo_s { cell_direction_t direction; /* Policy-specific data */ circuitmux_policy_circ_data_t *policy_data; + /* Mark bit for consistency checker */ + unsigned int mark:1; }; /* @@ -148,6 +150,9 @@ static INLINE circuit_t ** circuitmux_next_active_circ_p(circuitmux_t *cmux, circuit_t *circ); static INLINE circuit_t ** circuitmux_prev_active_circ_p(circuitmux_t *cmux, circuit_t *circ); +static void circuitmux_assert_okay_pass_one(circuitmux_t *cmux); +static void circuitmux_assert_okay_pass_two(circuitmux_t *cmux); +static void circuitmux_assert_okay_pass_three(circuitmux_t *cmux); /* Function definitions */ @@ -1346,3 +1351,284 @@ circuitmux_notify_xmit_cells(circuitmux_t *cmux, circuit_t *circ, } } +/* + * Circuitmux consistency checking assertions + */ + +/** + * Check that circuitmux data structures are consistent and fail with an + * assert if not. + */ + +void +circuitmux_assert_okay(circuitmux_t *cmux) +{ + tor_assert(cmux); + + /* + * Pass 1: iterate the hash table; for each entry: + * a) Check that the circuit has this cmux for n_mux or p_mux + * b) If the cell_count is > 0, set the mark bit; otherwise clear it + * c) Also check activeness (cell_count > 0 should be active) + * d) Count the number of circuits, active circuits and queued cells + * and at the end check that they match the counters in the cmux. + * + * Pass 2: iterate the active circuits list; for each entry, + * make sure the circuit is attached to this mux and appears + * in the hash table. Make sure the mark bit is 1, and clear + * it in the hash table entry. Consistency-check the linked + * list pointers. + * + * Pass 3: iterate the hash table again; assert if any active circuits + * (mark bit set to 1) are discovered that weren't cleared in pass 2 + * (don't appear in the linked list). + */ + + circuitmux_assert_okay_pass_one(cmux); + circuitmux_assert_okay_pass_two(cmux); + circuitmux_assert_okay_pass_three(cmux); +} + +/** + * Do the first pass of circuitmux_assert_okay(); see the comment in that + * function. + */ + +static void +circuitmux_assert_okay_pass_one(circuitmux_t *cmux) +{ + chanid_circid_muxinfo_t **i = NULL; + uint64_t chan_id; + channel_t *chan; + circid_t circ_id; + circuit_t *circ; + or_circuit_t *or_circ; + unsigned int circ_is_active; + circuit_t **next_p, **prev_p; + unsigned int n_circuits, n_active_circuits, n_cells; + + tor_assert(cmux); + tor_assert(cmux->chanid_circid_map); + + /* Reset the counters */ + n_circuits = n_active_circuits = n_cells = 0; + /* Start iterating the hash table */ + i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map); + while (i) { + /* Assert that the hash table entry isn't null */ + tor_assert(*i); + + /* Get the channel and circuit id */ + chan_id = (*i)->chan_id; + circ_id = (*i)->circ_id; + + /* Find the channel and circuit, assert that they exist */ + chan = channel_find_by_global_id(chan_id); + tor_assert(chan); + circ = circuit_get_by_circid_channel(circ_id, chan); + tor_assert(circ); + + /* Clear the circ_is_active bit to start */ + circ_is_active = 0; + + /* Assert that we know which direction this is going */ + tor_assert((*i)->muxinfo.direction == CELL_DIRECTION_OUT || + (*i)->muxinfo.direction == CELL_DIRECTION_IN); + + if ((*i)->muxinfo.direction == CELL_DIRECTION_OUT) { + /* We should be n_mux on this circuit */ + tor_assert(cmux == circ->n_mux); + tor_assert(chan == circ->n_chan); + /* Get next and prev for next test */ + next_p = &(circ->next_active_on_n_chan); + prev_p = &(circ->prev_active_on_n_chan); + } else { + /* This should be an or_circuit_t and we should be p_mux */ + or_circ = TO_OR_CIRCUIT(circ); + tor_assert(cmux == or_circ->p_mux); + tor_assert(chan == or_circ->p_chan); + /* Get next and prev for next test */ + next_p = &(or_circ->next_active_on_p_chan); + prev_p = &(or_circ->prev_active_on_p_chan); + } + + /* + * Should this circuit be active? I.e., does the mux know about > 0 + * cells on it? + */ + circ_is_active = ((*i)->muxinfo.cell_count > 0); + + /* It should be in the linked list iff it's active */ + if (circ_is_active) { + /* Either we have a next link or we are the tail */ + tor_assert(*next_p || (circ == cmux->active_circuits_tail)); + /* Either we have a prev link or we are the head */ + tor_assert(*prev_p || (circ == cmux->active_circuits_head)); + /* Increment the active circuits counter */ + ++n_active_circuits; + } else { + /* Shouldn't be in list, so no next or prev link */ + tor_assert(!(*next_p)); + tor_assert(!(*prev_p)); + /* And can't be head or tail */ + tor_assert(circ != cmux->active_circuits_head); + tor_assert(circ != cmux->active_circuits_tail); + } + + /* Increment the circuits counter */ + ++n_circuits; + /* Adjust the cell counter */ + n_cells += (*i)->muxinfo.cell_count; + + /* Set the mark bit to circ_is_active */ + (*i)->muxinfo.mark = circ_is_active; + + /* Advance to the next entry */ + i = HT_NEXT(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i); + } + + /* Now check the counters */ + tor_assert(n_cells == cmux->n_cells); + tor_assert(n_circuits == cmux->n_circuits); + tor_assert(n_active_circuits == cmux->n_active_circuits); +} + +/** + * Do the second pass of circuitmux_assert_okay(); see the comment in that + * function. + */ + +static void +circuitmux_assert_okay_pass_two(circuitmux_t *cmux) +{ + circuit_t *curr_circ, *prev_circ = NULL, *next_circ; + or_circuit_t *curr_or_circ; + uint64_t curr_chan_id; + circid_t curr_circ_id; + circuit_t **next_p, **prev_p; + channel_t *chan; + unsigned int n_active_circuits = 0; + cell_direction_t direction; + chanid_circid_muxinfo_t search, *hashent = NULL; + + tor_assert(cmux); + tor_assert(cmux->chanid_circid_map); + + /* + * Walk the linked list of active circuits in cmux; keep track of the + * previous circuit seen for consistency checking purposes. Count them + * to make sure the number in the linked list matches + * cmux->n_active_circuits. + */ + curr_circ = cmux->active_circuits_head; + while (curr_circ) { + /* Reset some things */ + chan = NULL; + curr_or_circ = NULL; + next_circ = NULL; + next_p = prev_p = NULL; + direction = 0; + + /* Figure out if this is n_mux or p_mux */ + if (cmux == curr_circ->n_mux) { + /* Get next_p and prev_p */ + next_p = &(curr_circ->next_active_on_n_chan); + prev_p = &(curr_circ->prev_active_on_n_chan); + /* Get the channel */ + chan = curr_circ->n_chan; + /* Get the circuit id */ + curr_circ_id = curr_circ->n_circ_id; + /* Remember the direction */ + direction = CELL_DIRECTION_OUT; + } else { + /* We must be p_mux and this must be an or_circuit_t */ + curr_or_circ = TO_OR_CIRCUIT(curr_circ); + tor_assert(cmux == curr_or_circ->p_mux); + /* Get next_p and prev_p */ + next_p = &(curr_or_circ->next_active_on_p_chan); + prev_p = &(curr_or_circ->prev_active_on_p_chan); + /* Get the channel */ + chan = curr_or_circ->p_chan; + /* Get the circuit id */ + curr_circ_id = curr_or_circ->p_circ_id; + /* Remember the direction */ + direction = CELL_DIRECTION_IN; + } + + /* Assert that we got a channel and get the channel ID */ + tor_assert(chan); + curr_chan_id = chan->global_identifier; + + /* Assert that prev_p points to last circuit we saw */ + tor_assert(*prev_p == prev_circ); + /* If that's NULL, assert that we are the head */ + if (!(*prev_p)) tor_assert(curr_circ == cmux->active_circuits_head); + + /* Get the next circuit */ + next_circ = *next_p; + /* If it's NULL, assert that we are the tail */ + if (!(*next_p)) tor_assert(curr_circ == cmux->active_circuits_tail); + + /* Now find the hash table entry for this circuit */ + search.chan_id = curr_chan_id; + search.circ_id = curr_circ_id; + hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map, + &search); + + /* Assert that we have one */ + tor_assert(hashent); + + /* Assert that the direction matches */ + tor_assert(direction == hashent->muxinfo.direction); + + /* Assert that the hash entry got marked in pass one */ + tor_assert(hashent->muxinfo.mark); + + /* Clear the mark */ + hashent->muxinfo.mark = 0; + + /* Increment the counter */ + ++n_active_circuits; + + /* Advance to the next active circuit and update prev_circ */ + prev_circ = curr_circ; + curr_circ = next_circ; + } + + /* Assert that the counter matches the cmux */ + tor_assert(n_active_circuits == cmux->n_active_circuits); +} + +/** + * Do the third pass of circuitmux_assert_okay(); see the comment in that + * function. + */ + +static void +circuitmux_assert_okay_pass_three(circuitmux_t *cmux) +{ + chanid_circid_muxinfo_t **i = NULL; + + tor_assert(cmux); + tor_assert(cmux->chanid_circid_map); + + /* Start iterating the hash table */ + i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map); + + /* Advance through each entry */ + while (i) { + /* Assert that it isn't null */ + tor_assert(*i); + + /* + * Assert that this entry is not marked - i.e., that either we didn't + * think it should be active in pass one or we saw it in the active + * circuits linked list. + */ + tor_assert(!((*i)->muxinfo.mark)); + + /* Advance to the next entry */ + i = HT_NEXT(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i); + } +} +

1 0

[tor/master] Add upcasts for circuitmux_policy_data_t and circuitmux_policy_circ_data_t to circuitmux.h
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit e1de2f1437ffe67ee0ae74ae6ac1d432f3981542 Author: Andrea Shepard <andrea(a)torproject.org> Date: Mon Oct 1 01:48:52 2012 -0700 Add upcasts for circuitmux_policy_data_t and circuitmux_policy_circ_data_t to circuitmux.h --- src/or/circuitmux.h | 17 +++++++++++++++++ 1 files changed, 17 insertions(+), 0 deletions(-) diff --git a/src/or/circuitmux.h b/src/or/circuitmux.h index f4eb73e..a3eacaf 100644 --- a/src/or/circuitmux.h +++ b/src/or/circuitmux.h @@ -76,6 +76,23 @@ struct circuitmux_policy_circ_data_s { uint32_t magic; }; +/* + * Upcast #defines for the above types + */ + +/** + * Convert a circuitmux_policy_data_t subtype to a circuitmux_policy_data_t. + */ + +#define TO_CMUX_POL_DATA(x) (&((x)->_base)) + +/** + * Convert a circuitmux_policy_circ_data_t subtype to a + * circuitmux_policy_circ_data_t. + */ + +#define TO_CMUX_POL_CIRC_DATA(x) (&((x)->_base)) + /* Consistency check */ void circuitmux_assert_okay(circuitmux_t *cmux);

1 0

[tor/master] Add circuitmux.h, circuitmux_ewma.h includes now necessary in config.c
by andrea＠torproject.org 11 Oct '12

11 Oct '12

commit 5f9d37e74ec269be8d496e8e0d4157875ff1fe59 Author: Andrea Shepard <andrea(a)torproject.org> Date: Mon Oct 1 01:52:39 2012 -0700 Add circuitmux.h, circuitmux_ewma.h includes now necessary in config.c --- src/or/config.c | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-) diff --git a/src/or/config.c b/src/or/config.c index bac2b2e..babbfb0 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -14,6 +14,8 @@ #include "or.h" #include "circuitbuild.h" #include "circuitlist.h" +#include "circuitmux.h" +#include "circuitmux_ewma.h" #include "config.h" #include "connection.h" #include "connection_edge.h"

1 0