/* * Copyright (c) 2012-2017, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/**
* \file circuitmux.c
* \brief Circuit mux/cell selection abstraction
*
* A circuitmux is responsible for MUltipleXing all of the
* circuits that are writing on a single channel. It keeps track of which of
* these circuits has something to write (aka, "active" circuits), and which
* one should write next. A circuitmux corresponds 1:1 with a channel.
*
* There can be different implementations of the circuitmux's rules (which
* decide which circuit is next to write).
*
* A circuitmux exposes three distinct
* interfaces to other components:
*
* To channels, which each have a circuitmux_t, the supported operations
* (invoked from relay.c) are:
*
* circuitmux_get_first_active_circuit():
*
* Pick one of the circuitmux's active circuits to send cells from.
*
* circuitmux_notify_xmit_cells():
*
* Notify the circuitmux that cells have been sent on a circuit.
*
* To circuits, the exposed operations are:
*
* circuitmux_attach_circuit():
*
* Attach a circuit to the circuitmux; this will allocate any policy-
* specific data wanted for this circuit and add it to the active
* circuits list if it has queued cells.
*
* circuitmux_detach_circuit():
*
* Detach a circuit from the circuitmux, freeing associated structures.
*
* circuitmux_clear_num_cells():
*
* Clear the circuitmux's cell counter for this circuit.
*
* circuitmux_set_num_cells():
*
* Set the circuitmux's cell counter for this circuit. One of
* circuitmuc_clear_num_cells() or circuitmux_set_num_cells() MUST be
* called when the number of cells queued on a circuit changes.
*
* See circuitmux.h for the circuitmux_policy_t data structure, which contains
* a table of function pointers implementing a circuit selection policy, and
* circuitmux_ewma.c for an example of a circuitmux policy. Circuitmux
* policies can be manipulated with:
*
* circuitmux_get_policy():
*
* Return the current policy for a circuitmux_t, if any.
*
* circuitmux_clear_policy():
*
* Remove a policy installed on a circuitmux_t, freeing all associated
* data. The circuitmux will revert to the built-in round-robin behavior.
*
* circuitmux_set_policy():
*
* Install a policy on a circuitmux_t; the appropriate callbacks will be
* made to attach all existing circuits to the new policy.
**/
#include "or.h"
#include "channel.h"
#include "circuitlist.h"
#include "circuitmux.h"
#include "relay.h"
/*
* Private typedefs for circuitmux.c
*/
/*
* Map of muxinfos for circuitmux_t to use; struct is defined below (name
* of struct must match HT_HEAD line).
*/
typedef struct chanid_circid_muxinfo_map chanid_circid_muxinfo_map_t;
/*
* Hash table entry (yeah, calling it chanid_circid_muxinfo_s seems to
* break the hash table code).
*/
typedef struct chanid_circid_muxinfo_t chanid_circid_muxinfo_t;
/*
* Anything the mux wants to store per-circuit in the map; right now just
* a count of queued cells.
*/
typedef struct circuit_muxinfo_s circuit_muxinfo_t;
/*
* Structures for circuitmux.c
*/
struct circuitmux_s {
/* Keep count of attached, active circuits */
unsigned int n_circuits, n_active_circuits;
/* Total number of queued cells on all circuits */
unsigned int n_cells;
/*
* Map from (channel ID, circuit ID) pairs to circuit_muxinfo_t
*/
chanid_circid_muxinfo_map_t *chanid_circid_map;
/*
* Double-linked ring of circuits with queued cells waiting for room to
* free up on this connection's outbuf. Every time we pull cells from
* a circuit, we advance this pointer to the next circuit in the ring.
*/
struct circuit_t *active_circuits_head, *active_circuits_tail;
/** List of queued destroy cells */
cell_queue_t destroy_cell_queue;
/** Boolean: True iff the last cell to circuitmux_get_first_active_circuit
* returned the destroy queue. Used to force alternation between
* destroy/non-destroy cells.
*
* XXXX There is no reason to think that alternating is a particularly good
* approach -- it's just designed to prevent destroys from starving other
* cells completely.
*/
unsigned int last_cell_was_destroy : 1;
/** Destroy counter: increment this when a destroy gets queued, decrement
* when we unqueue it, so we can test to make sure they don't starve.
*/
int64_t destroy_ctr;
/*
* 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.
*/
const circuitmux_policy_t *policy;
/* Policy-specific data */
circuitmux_policy_data_t *policy_data;
};
/*
* This struct holds whatever we want to store per attached circuit on a
* circuitmux_t; right now, just the count of queued cells and the direction.
*/
struct circuit_muxinfo_s {
/* Count of cells on this circuit at last update */
unsigned int cell_count;
/* Direction of flow */
cell_direction_t direction;
/* Policy-specific data */
circuitmux_policy_circ_data_t *policy_data;
/* Mark bit for consistency checker */
unsigned int mark:1;
};
/*
* A map from channel ID and circuit ID to a circuit_muxinfo_t for that
* circuit.
*/
struct chanid_circid_muxinfo_t {
HT_ENTRY(chanid_circid_muxinfo_t) node;
uint64_t chan_id;
circid_t circ_id;
circuit_muxinfo_t muxinfo;
};
/*
* Internal-use #defines
*/
#ifdef CMUX_PARANOIA
#define circuitmux_assert_okay_paranoid(cmux) \
circuitmux_assert_okay(cmux)
#else
#define circuitmux_assert_okay_paranoid(cmux)
#endif
/*
* Static function declarations
*/
static inline int
chanid_circid_entries_eq(chanid_circid_muxinfo_t *a,
chanid_circid_muxinfo_t *b);
static inline unsigned int
chanid_circid_entry_hash(chanid_circid_muxinfo_t *a);
static chanid_circid_muxinfo_t *
circuitmux_find_map_entry(circuitmux_t *cmux, circuit_t *circ);
static void
circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ,
cell_direction_t direction);
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 **
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);
/* Static global variables */
/** Count the destroy balance to debug destroy queue logic */
static int64_t global_destroy_ctr = 0;
/* Function definitions */
/**
* 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)
{
circuit_t **next_p = NULL, **prev_p = NULL;
circuit_t **next_prev = NULL, **prev_next = NULL;
circuit_t **tail_next = NULL;
or_circuit_t *or_circ = NULL;
tor_assert(cmux);
tor_assert(circ);
circuitmux_assert_okay_paranoid(cmux);
/* 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;
/* We're out of the list; now re-attach at the tail */
/* Adjust our next and prev pointers */
*next_p = NULL;
*prev_p = cmux->active_circuits_tail;
/* Set the next pointer of the tail, or the head if none */
if (cmux->active_circuits_tail) {
tail_next = circuitmux_next_active_circ_p(cmux,
cmux->active_circuits_tail);
*tail_next = circ;
} else {
cmux->active_circuits_head = circ;
}
/* Set the tail to this circuit */
cmux->active_circuits_tail = circ;
circuitmux_assert_okay_paranoid(cmux);
}
static inline circuit_t **
circuitmux_next_active_circ_p(circuitmux_t *cmux, circuit_t *circ)
{
tor_assert(cmux);
tor_assert(circ);
if (circ->n_mux == cmux) return &(circ->next_active_on_n_chan);
else {
tor_assert(TO_OR_CIRCUIT(circ)->p_mux == cmux);
return &(TO_OR_CIRCUIT(circ)->next_active_on_p_chan);
}
}
static inline circuit_t **
circuitmux_prev_active_circ_p(circuitmux_t *cmux, circuit_t *circ)
{
tor_assert(cmux);
tor_assert(circ);
if (circ->n_mux == cmux) return &(circ->prev_active_on_n_chan);
else {
tor_assert(TO_OR_CIRCUIT(circ)->p_mux == cmux);
return &(TO_OR_CIRCUIT(circ)->prev_active_on_p_chan);
}
}
/**
* Helper for chanid_circid_cell_count_map_t hash table: compare the channel
* ID and circuit ID for a and b, and return less than, equal to, or greater
* than zero appropriately.
*/
static inline int
chanid_circid_entries_eq(chanid_circid_muxinfo_t *a,
chanid_circid_muxinfo_t *b)
{
return a->chan_id == b->chan_id && a->circ_id == b->circ_id;
}
/**
* Helper: return a hash based on circuit ID and channel ID in a.
*/
static inline unsigned int
chanid_circid_entry_hash(chanid_circid_muxinfo_t *a)
{
return (((unsigned int)(a->circ_id) << 8) ^
((unsigned int)((a->chan_id >> 32) & 0xffffffff)) ^
((unsigned int)(a->chan_id & 0xffffffff)));
}
/* Declare the struct chanid_circid_muxinfo_map type */
HT_HEAD(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t);
/* Emit a bunch of hash table stuff */
HT_PROTOTYPE(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t, node,
chanid_circid_entry_hash, chanid_circid_entries_eq)
HT_GENERATE2(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t, node,
chanid_circid_entry_hash, chanid_circid_entries_eq, 0.6,
tor_reallocarray_, tor_free_)
/*
* Circuitmux alloc/free functions
*/
/**
* Allocate a new circuitmux_t
*/
circuitmux_t *
circuitmux_alloc(void)
{
circuitmux_t *rv = NULL;
rv = tor_malloc_zero(sizeof(*rv));
rv->chanid_circid_map = tor_malloc_zero(sizeof(*( rv->chanid_circid_map)));
HT_INIT(chanid_circid_muxinfo_map, rv->chanid_circid_map);
cell_queue_init(&rv->destroy_cell_queue);
return rv;
}
/**
* Detach all circuits from a circuitmux (use before circuitmux_free())
*
* If detached_out is non-NULL, add every detached circuit_t to
* detached_out.
*/
void
circuitmux_detach_all_circuits(circuitmux_t *cmux, smartlist_t *detached_out)
{
chanid_circid_muxinfo_t **i = NULL, *to_remove;
channel_t *chan = NULL;
circuit_t *circ = NULL;
tor_assert(cmux);
/*
* Don't circuitmux_assert_okay_paranoid() here; this gets called when
* channels are being freed and have already been unregistered, so
* the channel ID lookups it does will fail.
*/
i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
while (i) {
to_remove = *i;
if (! to_remove) {
log_warn(LD_BUG, "Somehow, an HT iterator gave us a NULL pointer.");
break;
} else {
/* Find a channel and circuit */
chan = channel_find_by_global_id(to_remove->chan_id);
if (chan) {
circ =
circuit_get_by_circid_channel_even_if_marked(to_remove->circ_id,
chan);
if (circ) {
/* Clear the circuit's mux for this direction */
if (to_remove->muxinfo.direction == CELL_DIRECTION_OUT) {
/*
* Update active_circuits et al.; this does policy notifies, so
* comes before freeing policy data
*/
if (to_remove->muxinfo.cell_count > 0) {
circuitmux_make_circuit_inactive(cmux, circ, CELL_DIRECTION_OUT);
}
/* 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
* comes before freeing policy data
*/
if (to_remove->muxinfo.cell_count > 0) {
circuitmux_make_circuit_inactive(cmux, circ, CELL_DIRECTION_IN);
}
/*
* It has a sensible p_chan and direction == CELL_DIRECTION_IN,
* 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,
"Circuit %u/channel " U64_FORMAT " had direction == "
"CELL_DIRECTION_IN, but isn't an or_circuit_t",
(unsigned)to_remove->circ_id,
U64_PRINTF_ARG(to_remove->chan_id));
}
/* Free policy-specific data if we have it */
if (to_remove->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->free_circ_data);
/* Call free_circ_data() */
cmux->policy->free_circ_data(cmux,
cmux->policy_data,
circ,
to_remove->muxinfo.policy_data);
to_remove->muxinfo.policy_data = NULL;
}
} else {
/* Complain and move on */
log_warn(LD_CIRC,
"Couldn't find circuit %u (for channel " U64_FORMAT ")",
(unsigned)to_remove->circ_id,
U64_PRINTF_ARG(to_remove->chan_id));
}
} else {
/* Complain and move on */
log_warn(LD_CIRC,
"Couldn't find channel " U64_FORMAT " (for circuit id %u)",
U64_PRINTF_ARG(to_remove->chan_id),
(unsigned)to_remove->circ_id);
}
/* Assert that we don't have un-freed policy data for this circuit */
tor_assert(to_remove->muxinfo.policy_data == NULL);
}
i = HT_NEXT_RMV(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
/* Free it */
tor_free(to_remove);
}
cmux->n_circuits = 0;
cmux->n_active_circuits = 0;
cmux->n_cells = 0;
}
/** Reclaim all circuit IDs currently marked as unusable on chan because
* of pending destroy cells in cmux.
*
* This function must be called AFTER circuits are unlinked from the (channel,
* circuid-id) map with circuit_unlink_all_from_channel(), but before calling
* circuitmux_free().
*/
void
circuitmux_mark_destroyed_circids_usable(circuitmux_t *cmux, channel_t *chan)
{
packed_cell_t *cell;
int n_bad = 0;
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);
} else {
++n_bad;
}
}
if (n_bad)
log_warn(LD_BUG, "%d cell(s) on destroy queue did not look like a "
"DESTROY cell.", n_bad);
}
/**
* Free a circuitmux_t; the circuits must be detached first with
* circuitmux_detach_all_circuits().
*/
void
circuitmux_free(circuitmux_t *cmux)
{
if (!cmux) return;
tor_assert(cmux->n_circuits == 0);
tor_assert(cmux->n_active_circuits == 0);
/*
* 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);
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);
tor_free(cmux->chanid_circid_map);
}
/*
* We're throwing away some destroys; log the counter and
* adjust the global counter by the queue size.
*/
if (cmux->destroy_cell_queue.n > 0) {
cmux->destroy_ctr -= cmux->destroy_cell_queue.n;
global_destroy_ctr -= cmux->destroy_cell_queue.n;
log_debug(LD_CIRC,
"Freeing cmux at %p with %u queued destroys; the last cmux "
"destroy balance was "I64_FORMAT", global is "I64_FORMAT,
cmux, cmux->destroy_cell_queue.n,
I64_PRINTF_ARG(cmux->destroy_ctr),
I64_PRINTF_ARG(global_destroy_ctr));
} else {
log_debug(LD_CIRC,
"Freeing cmux at %p with no queued destroys, the cmux destroy "
"balance was "I64_FORMAT", global is "I64_FORMAT,
cmux,
I64_PRINTF_ARG(cmux->destroy_ctr),
I64_PRINTF_ARG(global_destroy_ctr));
}
cell_queue_clear(&cmux->destroy_cell_queue);
tor_free(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
*/
MOCK_IMPL(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_even_if_marked((*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
*/
/**
* Query the direction of an attached circuit
*/
cell_direction_t
circuitmux_attached_circuit_direction(circuitmux_t *cmux, circuit_t *circ)
{
chanid_circid_muxinfo_t *hashent = NULL;
/* Try to find a map entry */
hashent = circuitmux_find_map_entry(cmux, circ);
/*
* This function should only be called on attached circuits; assert that
* we had a map entry.
*/
tor_assert(hashent);
/* Return the direction from the map entry */
return hashent->muxinfo.direction;
}
/**
* Find an entry in the cmux's map for this circuit or return NULL if there
* is none.
*/
static chanid_circid_muxinfo_t *
circuitmux_find_map_entry(circuitmux_t *cmux, circuit_t *circ)
{
chanid_circid_muxinfo_t search, *hashent = NULL;
/* Sanity-check parameters */
tor_assert(cmux);
tor_assert(cmux->chanid_circid_map);
tor_assert(circ);
/* Check if we have n_chan */
if (circ->n_chan) {
/* Okay, let's see if it's attached for n_chan/n_circ_id */
search.chan_id = circ->n_chan->global_identifier;
search.circ_id = circ->n_circ_id;
/* Query */
hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
&search);
}
/* Found something? */
if (hashent) {
/*
* Assert that the direction makes sense for a hashent we found by
* n_chan/n_circ_id before we return it.
*/
tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_OUT);
} else {
/* Not there, have we got a p_chan/p_circ_id to try? */
if (circ->magic == OR_CIRCUIT_MAGIC) {
search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
/* Check for p_chan */
if (TO_OR_CIRCUIT(circ)->p_chan) {
search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
/* Okay, search for that */
hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
&search);
/* Find anything? */
if (hashent) {
/* Assert that the direction makes sense before we return it */
tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_IN);
}
}
}
}
/* Okay, hashent is it if it was there */
return hashent;
}
/**
* Query whether a circuit is attached to a circuitmux
*/
int
circuitmux_is_circuit_attached(circuitmux_t *cmux, circuit_t *circ)
{
chanid_circid_muxinfo_t *hashent = NULL;
/* Look if it's in the circuit map */
hashent = circuitmux_find_map_entry(cmux, circ);
return (hashent != NULL);
}
/**
* Query whether a circuit is active on a circuitmux
*/
int
circuitmux_is_circuit_active(circuitmux_t *cmux, circuit_t *circ)
{
chanid_circid_muxinfo_t *hashent = NULL;
int is_active = 0;
tor_assert(cmux);
tor_assert(circ);
/* Look if it's in the circuit map */
hashent = circuitmux_find_map_entry(cmux, circ);
if (hashent) {
/* Check the number of cells on this circuit */
is_active = (hashent->muxinfo.cell_count > 0);
}
/* else not attached, so not active */
return is_active;
}
/**
* Query number of available cells for a circuit on a circuitmux
*/
unsigned int
circuitmux_num_cells_for_circuit(circuitmux_t *cmux, circuit_t *circ)
{
chanid_circid_muxinfo_t *hashent = NULL;
unsigned int n_cells = 0;
tor_assert(cmux);
tor_assert(circ);
/* Look if it's in the circuit map */
hashent = circuitmux_find_map_entry(cmux, circ);
if (hashent) {
/* Just get the cell count for this circuit */
n_cells = hashent->muxinfo.cell_count;
}
/* else not attached, so 0 cells */
return n_cells;
}
/**
* Query total number of available cells on a circuitmux
*/
MOCK_IMPL(unsigned int,
circuitmux_num_cells, (circuitmux_t *cmux))
{
tor_assert(cmux);
return cmux->n_cells + cmux->destroy_cell_queue.n;
}
/**
* Query total number of circuits active on a circuitmux
*/
unsigned int
circuitmux_num_active_circuits(circuitmux_t *cmux)
{
tor_assert(cmux);
return cmux->n_active_circuits;
}
/**
* Query total number of circuits attached to a circuitmux
*/
unsigned int
circuitmux_num_circuits(circuitmux_t *cmux)
{
tor_assert(cmux);
return cmux->n_circuits;
}
/*
* Functions for circuit code to call to update circuit status
*/
/**
* Attach a circuit to a circuitmux, for the specified direction.
*/
MOCK_IMPL(void,
circuitmux_attach_circuit,(circuitmux_t *cmux, circuit_t *circ,
cell_direction_t direction))
{
channel_t *chan = NULL;
uint64_t channel_id;
circid_t circ_id;
chanid_circid_muxinfo_t search, *hashent = NULL;
unsigned int cell_count;
tor_assert(cmux);
tor_assert(circ);
tor_assert(direction == CELL_DIRECTION_IN ||
direction == CELL_DIRECTION_OUT);
circuitmux_assert_okay_paranoid(cmux);
/*
* Figure out which channel we're using, and get the circuit's current
* cell count and circuit ID; assert that the circuit is not already
* attached to another mux.
*/
if (direction == CELL_DIRECTION_OUT) {
/* It's n_chan */
chan = circ->n_chan;
cell_count = circ->n_chan_cells.n;
circ_id = circ->n_circ_id;
} else {
/* We want p_chan */
chan = TO_OR_CIRCUIT(circ)->p_chan;
cell_count = TO_OR_CIRCUIT(circ)->p_chan_cells.n;
circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
}
/* Assert that we did get a channel */
tor_assert(chan);
/* Assert that the circuit ID is sensible */
tor_assert(circ_id != 0);
/* Get the channel ID */
channel_id = chan->global_identifier;
/* See if we already have this one */
search.chan_id = channel_id;
search.circ_id = circ_id;
hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
&search);
if (hashent) {
/*
* This circuit was already attached to this cmux; make sure the
* directions match and update the cell count and active circuit count.
*/
log_info(LD_CIRC,
"Circuit %u on channel " U64_FORMAT " was already attached to "
"cmux %p (trying to attach to %p)",
(unsigned)circ_id, U64_PRINTF_ARG(channel_id),
((direction == CELL_DIRECTION_OUT) ?
circ->n_mux : TO_OR_CIRCUIT(circ)->p_mux),
cmux);
/*
* The mux pointer on this circuit and the direction in result should
* match; otherwise assert.
*/
if (direction == CELL_DIRECTION_OUT) tor_assert(circ->n_mux == cmux);
else tor_assert(TO_OR_CIRCUIT(circ)->p_mux == cmux);
tor_assert(hashent->muxinfo.direction == direction);
/*
* Looks okay; just update the cell count and active circuits if we must
*/
if (hashent->muxinfo.cell_count > 0 && cell_count == 0) {
--(cmux->n_active_circuits);
circuitmux_make_circuit_inactive(cmux, circ, direction);
} else if (hashent->muxinfo.cell_count == 0 && cell_count > 0) {
++(cmux->n_active_circuits);
circuitmux_make_circuit_active(cmux, circ, direction);
}
cmux->n_cells -= hashent->muxinfo.cell_count;
cmux->n_cells += cell_count;
hashent->muxinfo.cell_count = cell_count;
} else {
/*
* New circuit; add an entry and update the circuit/active circuit
* counts.
*/
log_debug(LD_CIRC,
"Attaching circuit %u on channel " U64_FORMAT " to cmux %p",
(unsigned)circ_id, U64_PRINTF_ARG(channel_id), cmux);
/*
* Assert that the circuit doesn't already have a mux for this
* direction.
*/
if (direction == CELL_DIRECTION_OUT) tor_assert(circ->n_mux == NULL);
else tor_assert(TO_OR_CIRCUIT(circ)->p_mux == NULL);
/* Insert it in the map */
hashent = tor_malloc_zero(sizeof(*hashent));
hashent->chan_id = channel_id;
hashent->circ_id = circ_id;
hashent->muxinfo.cell_count = cell_count;
hashent->muxinfo.direction = direction;
/* Allocate policy specific circuit data if we need it */
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,
circ,
direction,
cell_count);
/* If we wanted policy data, it's an error not to get any */
tor_assert(hashent->muxinfo.policy_data);
}
HT_INSERT(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
hashent);
/* Set the circuit's mux for this direction */
if (direction == CELL_DIRECTION_OUT) circ->n_mux = cmux;
else TO_OR_CIRCUIT(circ)->p_mux = cmux;
/* Make sure the next/prev pointers are NULL */
if (direction == CELL_DIRECTION_OUT) {
circ->next_active_on_n_chan = NULL;
circ->prev_active_on_n_chan = NULL;
} else {
TO_OR_CIRCUIT(circ)->next_active_on_p_chan = NULL;
TO_OR_CIRCUIT(circ)->prev_active_on_p_chan = NULL;
}
/* Update counters */
++(cmux->n_circuits);
if (cell_count > 0) {
++(cmux->n_active_circuits);
circuitmux_make_circuit_active(cmux, circ, direction);
}
cmux->n_cells += cell_count;
}
circuitmux_assert_okay_paranoid(cmux);
}
/**
* Detach a circuit from a circuitmux and update all counters as needed;
* no-op if not attached.
*/
MOCK_IMPL(void,
circuitmux_detach_circuit,(circuitmux_t *cmux, circuit_t *circ))
{
chanid_circid_muxinfo_t search, *hashent = NULL;
/*
* Use this to keep track of whether we found it for n_chan or
* p_chan for consistency checking.
*
* The 0 initializer is not a valid cell_direction_t value.
* We assert that it has been replaced with a valid value before it is used.
*/
cell_direction_t last_searched_direction = 0;
tor_assert(cmux);
tor_assert(cmux->chanid_circid_map);
tor_assert(circ);
circuitmux_assert_okay_paranoid(cmux);
/* See if we have it for n_chan/n_circ_id */
if (circ->n_chan) {
search.chan_id = circ->n_chan->global_identifier;
search.circ_id = circ->n_circ_id;
hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
&search);
last_searched_direction = CELL_DIRECTION_OUT;
}
/* Got one? If not, see if it's an or_circuit_t and try p_chan/p_circ_id */
if (!hashent) {
if (circ->magic == OR_CIRCUIT_MAGIC) {
search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
if (TO_OR_CIRCUIT(circ)->p_chan) {
search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
hashent = HT_FIND(chanid_circid_muxinfo_map,
cmux->chanid_circid_map,
&search);
last_searched_direction = CELL_DIRECTION_IN;
}
}
}
tor_assert(last_searched_direction == CELL_DIRECTION_OUT
|| last_searched_direction == CELL_DIRECTION_IN);
/*
* If hashent isn't NULL, we have a circuit to detach; don't remove it from
* the map until later of circuitmux_make_circuit_inactive() breaks.
*/
if (hashent) {
/* Update counters */
--(cmux->n_circuits);
if (hashent->muxinfo.cell_count > 0) {
--(cmux->n_active_circuits);
/* This does policy notifies, so comes before freeing policy data */
circuitmux_make_circuit_inactive(cmux, circ, last_searched_direction);
}
cmux->n_cells -= hashent->muxinfo.cell_count;
/* Free policy-specific data if we have it */
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->free_circ_data);
/* Call free_circ_data() */
cmux->policy->free_circ_data(cmux,
cmux->policy_data,
circ,
hashent->muxinfo.policy_data);
hashent->muxinfo.policy_data = NULL;
}
/* Consistency check: the direction must match the direction searched */
tor_assert(last_searched_direction == hashent->muxinfo.direction);
/* Clear the circuit's mux for this direction */
if (last_searched_direction == CELL_DIRECTION_OUT) circ->n_mux = NULL;
else TO_OR_CIRCUIT(circ)->p_mux = NULL;
/* Now remove it from the map */
HT_REMOVE(chanid_circid_muxinfo_map, cmux->chanid_circid_map, hashent);
/* Free the hash entry */
tor_free(hashent);
}
circuitmux_assert_okay_paranoid(cmux);
}
/**
* Make a circuit active; update active list and policy-specific info, but
* we don't mess with the counters or hash table here.
*/
static void
circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ,
cell_direction_t direction)
{
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;
tor_assert(cmux);
tor_assert(circ);
tor_assert(direction == CELL_DIRECTION_OUT ||
direction == CELL_DIRECTION_IN);
/*
* Don't circuitmux_assert_okay_paranoid(cmux) here because the cell count
* already got changed and we have to update the list for it to be consistent
* again.
*/
/* Get the right set of active list links for this direction */
if (direction == CELL_DIRECTION_OUT) {
next_active = &(circ->next_active_on_n_chan);
prev_active = &(circ->prev_active_on_n_chan);
circuit_cmux = circ->n_mux;
chan = circ->n_chan;
circ_id = circ->n_circ_id;
} else {
next_active = &(TO_OR_CIRCUIT(circ)->next_active_on_p_chan);
prev_active = &(TO_OR_CIRCUIT(circ)->prev_active_on_p_chan);
circuit_cmux = TO_OR_CIRCUIT(circ)->p_mux;
chan = TO_OR_CIRCUIT(circ)->p_chan;
circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
}
/* Assert that it is attached to this mux and a channel */
tor_assert(cmux == circuit_cmux);
tor_assert(chan != NULL);
/*
* Check if the circuit really was inactive; if it's active, at least one
* of the next_active and prev_active pointers will not be NULL, or this
* circuit will be either the head or tail of the list for this cmux.
*/
already_active = (*prev_active != NULL || *next_active != NULL ||
cmux->active_circuits_head == circ ||
cmux->active_circuits_tail == circ);
/* If we're already active, log a warning and finish */
if (already_active) {
log_warn(LD_CIRC,
"Circuit %u on channel " U64_FORMAT " was already active",
(unsigned)circ_id, U64_PRINTF_ARG(chan->global_identifier));
return;
}
/*
* This is going at the head of the list; if the old head is not NULL,
* then its prev pointer should point to this.
*/
*next_active = cmux->active_circuits_head; /* Next is old head */
*prev_active = NULL; /* Prev is NULL (this will be the head) */
if (cmux->active_circuits_head) {
/* The list had an old head; update its prev pointer */
next_prev =
circuitmux_prev_active_circ_p(cmux, cmux->active_circuits_head);
tor_assert(next_prev);
*next_prev = circ;
} else {
/* The list was empty; this becomes the tail as well */
cmux->active_circuits_tail = circ;
}
/* This becomes the new head of the list */
cmux->active_circuits_head = circ;
/* Policy-specific notification */
if (cmux->policy &&
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);
/* Notify */
cmux->policy->notify_circ_active(cmux, cmux->policy_data,
circ, hashent->muxinfo.policy_data);
}
circuitmux_assert_okay_paranoid(cmux);
}
/**
* Make a circuit inactive; update active list and policy-specific info, but
* we don't mess with the counters or hash table here.
*/
static void
circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ,
cell_direction_t direction)
{
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;
tor_assert(cmux);
tor_assert(circ);
tor_assert(direction == CELL_DIRECTION_OUT ||
direction == CELL_DIRECTION_IN);
/*
* Don't circuitmux_assert_okay_paranoid(cmux) here because the cell count
* already got changed and we have to update the list for it to be consistent
* again.
*/
/* Get the right set of active list links for this direction */
if (direction == CELL_DIRECTION_OUT) {
next_active = &(circ->next_active_on_n_chan);
prev_active = &(circ->prev_active_on_n_chan);
circuit_cmux = circ->n_mux;
chan = circ->n_chan;
circ_id = circ->n_circ_id;
} else {
next_active = &(TO_OR_CIRCUIT(circ)->next_active_on_p_chan);
prev_active = &(TO_OR_CIRCUIT(circ)->prev_active_on_p_chan);
circuit_cmux = TO_OR_CIRCUIT(circ)->p_mux;
chan = TO_OR_CIRCUIT(circ)->p_chan;
circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
}
/* Assert that it is attached to this mux and a channel */
tor_assert(cmux == circuit_cmux);
tor_assert(chan != NULL);
/*
* Check if the circuit really was active; if it's inactive, the
* next_active and prev_active pointers will be NULL and this circuit
* will not be the head or tail of the list for this cmux.
*/
already_inactive = (*prev_active == NULL && *next_active == NULL &&
cmux->active_circuits_head != circ &&
cmux->active_circuits_tail != circ);
/* If we're already inactive, log a warning and finish */
if (already_inactive) {
log_warn(LD_CIRC,
"Circuit %d on channel " U64_FORMAT " was already inactive",
(unsigned)circ_id, U64_PRINTF_ARG(chan->global_identifier));
return;
}
/* Remove from the list; first get next_prev and prev_next */
if (*next_active) {
/*
* If there's a next circuit, its previous circuit becomes this
* circuit's previous circuit.
*/
next_prev = circuitmux_prev_active_circ_p(cmux, *next_active);
} else {
/* Else, the tail becomes this circuit's previous circuit */
next_prev = &(cmux->active_circuits_tail);
}
/* Got next_prev, now prev_next */
if (*prev_active) {
/*
* If there's a previous circuit, its next circuit becomes this circuit's
* next circuit.
*/
prev_next = circuitmux_next_active_circ_p(cmux, *prev_active);
} else {
/* Else, the head becomes this circuit's next circuit */
prev_next = &(cmux->active_circuits_head);
}
/* Assert that we got sensible values for the next/prev pointers */
tor_assert(next_prev != NULL);
tor_assert(prev_next != NULL);
/* Update the next/prev pointers - this removes circ from the list */
*next_prev = *prev_active;
*prev_next = *next_active;
/* Now null out prev_active/next_active */
*prev_active = NULL;
*next_active = NULL;
/* Policy-specific notification */
if (cmux->policy &&
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);
/* Notify */
cmux->policy->notify_circ_inactive(cmux, cmux->policy_data,
circ, hashent->muxinfo.policy_data);
}
circuitmux_assert_okay_paranoid(cmux);
}
/**
* Clear the cell counter for a circuit on a circuitmux
*/
void
circuitmux_clear_num_cells(circuitmux_t *cmux, circuit_t *circ)
{
/* This is the same as setting the cell count to zero */
circuitmux_set_num_cells(cmux, circ, 0);
}
/**
* Set the cell counter for a circuit on a circuitmux
*/
void
circuitmux_set_num_cells(circuitmux_t *cmux, circuit_t *circ,
unsigned int n_cells)
{
chanid_circid_muxinfo_t *hashent = NULL;
tor_assert(cmux);
tor_assert(circ);
circuitmux_assert_okay_paranoid(cmux);
/* Search for this circuit's entry */
hashent = circuitmux_find_map_entry(cmux, circ);
/* Assert that we found one */
tor_assert(hashent);
/* Update cmux cell counter */
cmux->n_cells -= hashent->muxinfo.cell_count;
cmux->n_cells += n_cells;
/* Do we need to notify a cmux policy? */
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,
hashent->muxinfo.policy_data,
n_cells);
}
/*
* Update cmux active circuit counter: is the old cell count > 0 and the
* new cell count == 0 ?
*/
if (hashent->muxinfo.cell_count > 0 && n_cells == 0) {
--(cmux->n_active_circuits);
hashent->muxinfo.cell_count = n_cells;
circuitmux_make_circuit_inactive(cmux, circ, hashent->muxinfo.direction);
/* Is the old cell count == 0 and the new cell count > 0 ? */
} else if (hashent->muxinfo.cell_count == 0 && n_cells > 0) {
++(cmux->n_active_circuits);
hashent->muxinfo.cell_count = n_cells;
circuitmux_make_circuit_active(cmux, circ, hashent->muxinfo.direction);
} else {
/*
* Update the entry cell count like this so we can put a
* circuitmux_assert_okay_paranoid inside make_circuit_(in)active() too.
*/
hashent->muxinfo.cell_count = n_cells;
}
circuitmux_assert_okay_paranoid(cmux);
}
/*
* Functions for channel code to call to get a circuit to transmit from or
* notify that cells have been transmitted.
*/
/**
* 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.
*
* If we would rather send a destroy cell, return NULL and set
* *destroy_queue_out to the destroy queue.
*
* If we have nothing to send, set *destroy_queue_out to NULL and
* return NULL.
*/
circuit_t *
circuitmux_get_first_active_circuit(circuitmux_t *cmux,
cell_queue_t **destroy_queue_out)
{
circuit_t *circ = NULL;
tor_assert(cmux);
tor_assert(destroy_queue_out);
*destroy_queue_out = NULL;
if (cmux->destroy_cell_queue.n &&
(!cmux->last_cell_was_destroy || cmux->n_active_circuits == 0)) {
/* We have destroy cells to send, and either we just sent a relay cell,
* or we have no relay cells to send. */
/* XXXX We should let the cmux policy have some say in this eventually. */
/* XXXX Alternating is not a terribly brilliant approach here. */
*destroy_queue_out = &cmux->destroy_cell_queue;
cmux->last_cell_was_destroy = 1;
} else 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;
}
cmux->last_cell_was_destroy = 0;
} else {
tor_assert(cmux->n_cells == 0);
tor_assert(cmux->destroy_cell_queue.n == 0);
}
return circ;
}
/**
* 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)
{
chanid_circid_muxinfo_t *hashent = NULL;
int becomes_inactive = 0;
tor_assert(cmux);
tor_assert(circ);
circuitmux_assert_okay_paranoid(cmux);
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;
/* Adjust the mux cell counter */
cmux->n_cells -= n_cells;
/* 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);
}
circuitmux_assert_okay_paranoid(cmux);
}
/**
* Notify the circuitmux that a destroy was sent, so we can update
* the counter.
*/
void
circuitmux_notify_xmit_destroy(circuitmux_t *cmux)
{
tor_assert(cmux);
--(cmux->destroy_ctr);
--(global_destroy_ctr);
log_debug(LD_CIRC,
"Cmux at %p sent a destroy, cmux counter is now "I64_FORMAT", "
"global counter is now "I64_FORMAT,
cmux,
I64_PRINTF_ARG(cmux->destroy_ctr),
I64_PRINTF_ARG(global_destroy_ctr));
}
/*
* 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_even_if_marked(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);
}
}
/*DOCDOC */
void
circuitmux_append_destroy_cell(channel_t *chan,
circuitmux_t *cmux,
circid_t circ_id,
uint8_t reason)
{
cell_t cell;
memset(&cell, 0, sizeof(cell_t));
cell.circ_id = circ_id;
cell.command = CELL_DESTROY;
cell.payload[0] = (uint8_t) reason;
cell_queue_append_packed_copy(NULL, &cmux->destroy_cell_queue, 0, &cell,
chan->wide_circ_ids, 0);
/* Destroy entering the queue, update counters */
++(cmux->destroy_ctr);
++global_destroy_ctr;
log_debug(LD_CIRC,
"Cmux at %p queued a destroy for circ %u, cmux counter is now "
I64_FORMAT", global counter is now "I64_FORMAT,
cmux, circ_id,
I64_PRINTF_ARG(cmux->destroy_ctr),
I64_PRINTF_ARG(global_destroy_ctr));
/* XXXX Duplicate code from append_cell_to_circuit_queue */
if (!channel_has_queued_writes(chan)) {
/* There is no data at all waiting to be sent on the outbuf. Add a
* cell, so that we can notice when it gets flushed, flushed_some can
* get called, and we can start putting more data onto the buffer then.
*/
log_debug(LD_GENERAL, "Primed a buffer.");
channel_flush_from_first_active_circuit(chan, 1);
}
}
/*DOCDOC; for debugging 12184. This runs slowly. */
int64_t
circuitmux_count_queued_destroy_cells(const channel_t *chan,
const circuitmux_t *cmux)
{
int64_t n_destroy_cells = cmux->destroy_ctr;
int64_t destroy_queue_size = cmux->destroy_cell_queue.n;
int64_t manual_total = 0;
int64_t manual_total_in_map = 0;
packed_cell_t *cell;
TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
circid_t id;
++manual_total;
id = packed_cell_get_circid(cell, chan->wide_circ_ids);
if (circuit_id_in_use_on_channel(id, (channel_t*)chan))
++manual_total_in_map;
}
if (n_destroy_cells != destroy_queue_size ||
n_destroy_cells != manual_total ||
n_destroy_cells != manual_total_in_map) {
log_warn(LD_BUG, " Discrepancy in counts for queued destroy cells on "
"circuitmux. n="I64_FORMAT". queue_size="I64_FORMAT". "
"manual_total="I64_FORMAT". manual_total_in_map="I64_FORMAT".",
I64_PRINTF_ARG(n_destroy_cells),
I64_PRINTF_ARG(destroy_queue_size),
I64_PRINTF_ARG(manual_total),
I64_PRINTF_ARG(manual_total_in_map));
}
return n_destroy_cells;
}
/**
* Compare cmuxes to see which is more preferred; return < 0 if
* cmux_1 has higher priority (i.e., cmux_1 < cmux_2 in the scheduler's
* sort order), > 0 if cmux_2 has higher priority, or 0 if they are
* equally preferred.
*
* If the cmuxes have different cmux policies or the policy does not
* support the cmp_cmux method, return 0.
*/
MOCK_IMPL(int,
circuitmux_compare_muxes, (circuitmux_t *cmux_1, circuitmux_t *cmux_2))
{
const circuitmux_policy_t *policy;
tor_assert(cmux_1);
tor_assert(cmux_2);
if (cmux_1 == cmux_2) {
/* Equivalent because they're the same cmux */
return 0;
}
if (cmux_1->policy && cmux_2->policy) {
if (cmux_1->policy == cmux_2->policy) {
policy = cmux_1->policy;
if (policy->cmp_cmux) {
/* Okay, we can compare! */
return policy->cmp_cmux(cmux_1, cmux_1->policy_data,
cmux_2, cmux_2->policy_data);
} else {
/*
* Equivalent because the policy doesn't know how to compare between
* muxes.
*/
return 0;
}
} else {
/* Equivalent because they have different policies */
return 0;
}
} else {
/* Equivalent because one or both are missing a policy */
return 0;
}
}