12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364 |
- /* * Copyright (c) 2012-2018, The Tor Project, Inc. */
- /* See LICENSE for licensing information */
- /**
- * \file circuitmux.c
- * \brief Circuit mux/cell selection abstraction
- *
- * A circuitmux is responsible for <b>MU</b>ltiple<b>X</b>ing 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/or.h"
- #include "or/channel.h"
- #include "or/circuitlist.h"
- #include "or/circuitmux.h"
- #include "or/relay.h"
- #include "or/cell_queue_st.h"
- #include "or/destroy_cell_queue_st.h"
- #include "or/or_circuit_st.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;
- /** List of queued destroy cells */
- destroy_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;
- };
- /*
- * 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);
- static void
- circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ);
- /* Static global variables */
- /** Count the destroy balance to debug destroy queue logic */
- static int64_t global_destroy_ctr = 0;
- /* Function definitions */
- /**
- * 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);
- destroy_cell_queue_init(&rv->destroy_cell_queue);
- return rv;
- }
- /**
- * Detach all circuits from a circuitmux (use before circuitmux_free())
- *
- * If <b>detached_out</b> is non-NULL, add every detached circuit_t to
- * detached_out.
- */
- void
- circuitmux_detach_all_circuits(circuitmux_t *cmux, smartlist_t *detached_out)
- {
- chanid_circid_muxinfo_t **i = NULL, *to_remove;
- channel_t *chan = NULL;
- circuit_t *circ = NULL;
- tor_assert(cmux);
- 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);
- }
- /* 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);
- }
- /*
- * 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 %"PRIu64 " had direction == "
- "CELL_DIRECTION_IN, but isn't an or_circuit_t",
- (unsigned)to_remove->circ_id,
- (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 %"PRIu64 ")",
- (unsigned)to_remove->circ_id,
- (to_remove->chan_id));
- }
- } else {
- /* Complain and move on */
- log_warn(LD_CIRC,
- "Couldn't find channel %"PRIu64 " (for circuit id %u)",
- (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 <b>chan</b> because
- * of pending destroy cells in <b>cmux</b>.
- *
- * 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)
- {
- destroy_cell_t *cell;
- TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
- channel_mark_circid_usable(chan, cell->circid);
- }
- }
- /**
- * 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 %"PRId64", global is %"PRId64,
- cmux, cmux->destroy_cell_queue.n,
- (cmux->destroy_ctr),
- (global_destroy_ctr));
- } else {
- log_debug(LD_CIRC,
- "Freeing cmux at %p with no queued destroys, the cmux destroy "
- "balance was %"PRId64", global is %"PRId64,
- cmux,
- (cmux->destroy_ctr),
- (global_destroy_ctr));
- }
- destroy_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 */
- 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);
- /*
- * 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 %"PRIu64 " was already attached to "
- "cmux %p (trying to attach to %p)",
- (unsigned)circ_id, (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);
- } else if (hashent->muxinfo.cell_count == 0 && cell_count > 0) {
- ++(cmux->n_active_circuits);
- circuitmux_make_circuit_active(cmux, circ);
- }
- 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 %"PRIu64 " to cmux %p",
- (unsigned)circ_id, (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->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;
- /* Update counters */
- ++(cmux->n_circuits);
- if (cell_count > 0) {
- ++(cmux->n_active_circuits);
- circuitmux_make_circuit_active(cmux, circ);
- }
- cmux->n_cells += cell_count;
- }
- }
- /**
- * 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);
- /* 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);
- }
- 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);
- }
- }
- /**
- * 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)
- {
- tor_assert(cmux);
- tor_assert(cmux->policy);
- tor_assert(circ);
- /* Policy-specific notification */
- if (cmux->policy->notify_circ_active) {
- /* Okay, we need to check the circuit for policy data now */
- chanid_circid_muxinfo_t *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);
- }
- }
- /**
- * 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)
- {
- tor_assert(cmux);
- tor_assert(cmux->policy);
- tor_assert(circ);
- /* Policy-specific notification */
- if (cmux->policy->notify_circ_inactive) {
- /* Okay, we need to check the circuit for policy data now */
- chanid_circid_muxinfo_t *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);
- }
- }
- /**
- * 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);
- /* 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->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);
- /* 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);
- } else {
- 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.
- */
- /**
- * 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
- * *<b>destroy_queue_out</b> to the destroy queue.
- *
- * If we have nothing to send, set *<b>destroy_queue_out</b> to NULL and
- * return NULL.
- */
- circuit_t *
- circuitmux_get_first_active_circuit(circuitmux_t *cmux,
- destroy_cell_queue_t **destroy_queue_out)
- {
- circuit_t *circ = NULL;
- tor_assert(cmux);
- tor_assert(cmux->policy);
- /* This callback is mandatory. */
- tor_assert(cmux->policy->pick_active_circuit);
- 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? */
- circ = cmux->policy->pick_active_circuit(cmux, cmux->policy_data);
- 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);
- 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;
- /*
- * 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->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);
- }
- }
- /**
- * 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 %"PRId64", "
- "global counter is now %"PRId64,
- cmux,
- (cmux->destroy_ctr),
- (global_destroy_ctr));
- }
- /*DOCDOC */
- void
- circuitmux_append_destroy_cell(channel_t *chan,
- circuitmux_t *cmux,
- circid_t circ_id,
- uint8_t reason)
- {
- destroy_cell_queue_append(&cmux->destroy_cell_queue, circ_id, reason);
- /* 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 "
- "%"PRId64", global counter is now %"PRId64,
- cmux, circ_id,
- (cmux->destroy_ctr),
- (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;
- destroy_cell_t *cell;
- TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
- circid_t id;
- ++manual_total;
- id = cell->circid;
- 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=%"PRId64". queue_size=%"PRId64". "
- "manual_total=%"PRId64". manual_total_in_map=%"PRId64".",
- (n_destroy_cells),
- (destroy_queue_size),
- (manual_total),
- (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;
- }
- }
|