1 /* * Copyright (c) 2012-2021, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
6 * \brief Circuit mux/cell selection abstraction
8 * A circuitmux is responsible for <b>MU</b>ltiple<b>X</b>ing all of the
9 * circuits that are writing on a single channel. It keeps track of which of
10 * these circuits has something to write (aka, "active" circuits), and which
11 * one should write next. A circuitmux corresponds 1:1 with a channel.
13 * There can be different implementations of the circuitmux's rules (which
14 * decide which circuit is next to write).
16 * A circuitmux exposes three distinct
17 * interfaces to other components:
19 * To channels, which each have a circuitmux_t, the supported operations
20 * (invoked from relay.c) are:
22 * circuitmux_get_first_active_circuit():
24 * Pick one of the circuitmux's active circuits to send cells from.
26 * circuitmux_notify_xmit_cells():
28 * Notify the circuitmux that cells have been sent on a circuit.
30 * To circuits, the exposed operations are:
32 * circuitmux_attach_circuit():
34 * Attach a circuit to the circuitmux; this will allocate any policy-
35 * specific data wanted for this circuit and add it to the active
36 * circuits list if it has queued cells.
38 * circuitmux_detach_circuit():
40 * Detach a circuit from the circuitmux, freeing associated structures.
42 * circuitmux_clear_num_cells():
44 * Clear the circuitmux's cell counter for this circuit.
46 * circuitmux_set_num_cells():
48 * Set the circuitmux's cell counter for this circuit. One of
49 * circuitmuc_clear_num_cells() or circuitmux_set_num_cells() MUST be
50 * called when the number of cells queued on a circuit changes.
52 * See circuitmux.h for the circuitmux_policy_t data structure, which contains
53 * a table of function pointers implementing a circuit selection policy, and
54 * circuitmux_ewma.c for an example of a circuitmux policy. Circuitmux
55 * policies can be manipulated with:
57 * circuitmux_get_policy():
59 * Return the current policy for a circuitmux_t, if any.
61 * circuitmux_clear_policy():
63 * Remove a policy installed on a circuitmux_t, freeing all associated
64 * data. The circuitmux will revert to the built-in round-robin behavior.
66 * circuitmux_set_policy():
68 * Install a policy on a circuitmux_t; the appropriate callbacks will be
69 * made to attach all existing circuits to the new policy.
72 #define CIRCUITMUX_PRIVATE
74 #include "core/or/or.h"
75 #include "core/or/channel.h"
76 #include "core/or/circuitlist.h"
77 #include "core/or/circuitmux.h"
78 #include "core/or/relay.h"
80 #include "core/or/or_circuit_st.h"
82 #include "lib/crypt_ops/crypto_util.h"
85 * Private typedefs for circuitmux.c
89 * Hash table entry (yeah, calling it chanid_circid_muxinfo_s seems to
90 * break the hash table code).
92 typedef struct chanid_circid_muxinfo_t chanid_circid_muxinfo_t
;
95 * Anything the mux wants to store per-circuit in the map; right now just
96 * a count of queued cells.
99 typedef struct circuit_muxinfo_t circuit_muxinfo_t
;
102 * This struct holds whatever we want to store per attached circuit on a
103 * circuitmux_t; right now, just the count of queued cells and the direction.
106 struct circuit_muxinfo_t
{
107 /* Count of cells on this circuit at last update */
108 unsigned int cell_count
;
109 /* Direction of flow */
110 cell_direction_t direction
;
111 /* Policy-specific data */
112 circuitmux_policy_circ_data_t
*policy_data
;
113 /* Mark bit for consistency checker */
118 * A map from channel ID and circuit ID to a circuit_muxinfo_t for that
122 struct chanid_circid_muxinfo_t
{
123 HT_ENTRY(chanid_circid_muxinfo_t
) node
;
126 circuit_muxinfo_t muxinfo
;
130 * Static function declarations
134 chanid_circid_entries_eq(chanid_circid_muxinfo_t
*a
,
135 chanid_circid_muxinfo_t
*b
);
136 static inline unsigned int
137 chanid_circid_entry_hash(chanid_circid_muxinfo_t
*a
);
138 static chanid_circid_muxinfo_t
*
139 circuitmux_find_map_entry(circuitmux_t
*cmux
, circuit_t
*circ
);
141 circuitmux_make_circuit_active(circuitmux_t
*cmux
, circuit_t
*circ
);
143 circuitmux_make_circuit_inactive(circuitmux_t
*cmux
, circuit_t
*circ
);
145 /* Static global variables */
147 /** Count the destroy balance to debug destroy queue logic */
148 static int64_t global_destroy_ctr
= 0;
150 /* Function definitions */
153 * Helper for chanid_circid_cell_count_map_t hash table: compare the channel
154 * ID and circuit ID for a and b, and return less than, equal to, or greater
155 * than zero appropriately.
159 chanid_circid_entries_eq(chanid_circid_muxinfo_t
*a
,
160 chanid_circid_muxinfo_t
*b
)
162 return a
->chan_id
== b
->chan_id
&& a
->circ_id
== b
->circ_id
;
166 * Helper: return a hash based on circuit ID and channel ID in a.
169 static inline unsigned int
170 chanid_circid_entry_hash(chanid_circid_muxinfo_t
*a
)
172 return (((unsigned int)(a
->circ_id
) << 8) ^
173 ((unsigned int)((a
->chan_id
>> 32) & 0xffffffff)) ^
174 ((unsigned int)(a
->chan_id
& 0xffffffff)));
177 /* Emit a bunch of hash table stuff */
178 HT_PROTOTYPE(chanid_circid_muxinfo_map
, chanid_circid_muxinfo_t
, node
,
179 chanid_circid_entry_hash
, chanid_circid_entries_eq
);
180 HT_GENERATE2(chanid_circid_muxinfo_map
, chanid_circid_muxinfo_t
, node
,
181 chanid_circid_entry_hash
, chanid_circid_entries_eq
, 0.6,
182 tor_reallocarray_
, tor_free_
);
185 * Circuitmux alloc/free functions
189 * Allocate a new circuitmux_t
193 circuitmux_alloc(void)
195 circuitmux_t
*rv
= NULL
;
197 rv
= tor_malloc_zero(sizeof(*rv
));
198 rv
->chanid_circid_map
= tor_malloc_zero(sizeof(*( rv
->chanid_circid_map
)));
199 HT_INIT(chanid_circid_muxinfo_map
, rv
->chanid_circid_map
);
200 destroy_cell_queue_init(&rv
->destroy_cell_queue
);
206 * Detach all circuits from a circuitmux (use before circuitmux_free())
208 * If <b>detached_out</b> is non-NULL, add every detached circuit_t to
213 circuitmux_detach_all_circuits(circuitmux_t
*cmux
, smartlist_t
*detached_out
)
215 chanid_circid_muxinfo_t
**i
= NULL
, *to_remove
;
216 channel_t
*chan
= NULL
;
217 circuit_t
*circ
= NULL
;
221 i
= HT_START(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
);
226 log_warn(LD_BUG
, "Somehow, an HT iterator gave us a NULL pointer.");
229 /* Find a channel and circuit */
230 chan
= channel_find_by_global_id(to_remove
->chan_id
);
233 circuit_get_by_circid_channel_even_if_marked(to_remove
->circ_id
,
236 /* Clear the circuit's mux for this direction */
237 if (to_remove
->muxinfo
.direction
== CELL_DIRECTION_OUT
) {
239 * Update active_circuits et al.; this does policy notifies, so
240 * comes before freeing policy data
243 if (to_remove
->muxinfo
.cell_count
> 0) {
244 circuitmux_make_circuit_inactive(cmux
, circ
);
248 smartlist_add(detached_out
, circ
);
249 } else if (circ
->magic
== OR_CIRCUIT_MAGIC
) {
251 * Update active_circuits et al.; this does policy notifies, so
252 * comes before freeing policy data
255 if (to_remove
->muxinfo
.cell_count
> 0) {
256 circuitmux_make_circuit_inactive(cmux
, circ
);
260 smartlist_add(detached_out
, circ
);
262 /* Complain and move on */
264 "Circuit %u/channel %"PRIu64
" had direction == "
265 "CELL_DIRECTION_IN, but isn't an or_circuit_t",
266 (unsigned)to_remove
->circ_id
,
267 (to_remove
->chan_id
));
270 /* Free policy-specific data if we have it */
271 if (to_remove
->muxinfo
.policy_data
) {
273 * If we have policy data, assert that we have the means to
276 tor_assert(cmux
->policy
);
277 tor_assert(cmux
->policy
->free_circ_data
);
278 /* Call free_circ_data() */
279 cmux
->policy
->free_circ_data(cmux
,
282 to_remove
->muxinfo
.policy_data
);
283 to_remove
->muxinfo
.policy_data
= NULL
;
286 /* Complain and move on */
288 "Couldn't find circuit %u (for channel %"PRIu64
")",
289 (unsigned)to_remove
->circ_id
,
290 (to_remove
->chan_id
));
293 /* Complain and move on */
295 "Couldn't find channel %"PRIu64
" (for circuit id %u)",
296 (to_remove
->chan_id
),
297 (unsigned)to_remove
->circ_id
);
300 /* Assert that we don't have un-freed policy data for this circuit */
301 tor_assert(to_remove
->muxinfo
.policy_data
== NULL
);
304 i
= HT_NEXT_RMV(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
, i
);
310 cmux
->n_circuits
= 0;
311 cmux
->n_active_circuits
= 0;
315 /** Reclaim all circuit IDs currently marked as unusable on <b>chan</b> because
316 * of pending destroy cells in <b>cmux</b>.
318 * This function must be called AFTER circuits are unlinked from the (channel,
319 * circuid-id) map with circuit_unlink_all_from_channel(), but before calling
323 circuitmux_mark_destroyed_circids_usable(circuitmux_t
*cmux
, channel_t
*chan
)
325 destroy_cell_t
*cell
;
326 TOR_SIMPLEQ_FOREACH(cell
, &cmux
->destroy_cell_queue
.head
, next
) {
327 channel_mark_circid_usable(chan
, cell
->circid
);
332 * Free a circuitmux_t; the circuits must be detached first with
333 * circuitmux_detach_all_circuits().
337 circuitmux_free_(circuitmux_t
*cmux
)
341 tor_assert(cmux
->n_circuits
== 0);
342 tor_assert(cmux
->n_active_circuits
== 0);
345 * Free policy-specific data if we have any; we don't
346 * need to do circuitmux_set_policy(cmux, NULL) to cover
347 * the circuits because they would have been handled in
348 * circuitmux_detach_all_circuits() before this was
351 if (cmux
->policy
&& cmux
->policy
->free_cmux_data
) {
352 if (cmux
->policy_data
) {
353 cmux
->policy
->free_cmux_data(cmux
, cmux
->policy_data
);
354 cmux
->policy_data
= NULL
;
356 } else tor_assert(cmux
->policy_data
== NULL
);
358 if (cmux
->chanid_circid_map
) {
359 HT_CLEAR(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
);
360 tor_free(cmux
->chanid_circid_map
);
364 * We're throwing away some destroys; log the counter and
365 * adjust the global counter by the queue size.
367 if (cmux
->destroy_cell_queue
.n
> 0) {
368 cmux
->destroy_ctr
-= cmux
->destroy_cell_queue
.n
;
369 global_destroy_ctr
-= cmux
->destroy_cell_queue
.n
;
371 "Freeing cmux at %p with %u queued destroys; the last cmux "
372 "destroy balance was %"PRId64
", global is %"PRId64
,
373 cmux
, cmux
->destroy_cell_queue
.n
,
375 (global_destroy_ctr
));
378 "Freeing cmux at %p with no queued destroys, the cmux destroy "
379 "balance was %"PRId64
", global is %"PRId64
,
382 (global_destroy_ctr
));
385 destroy_cell_queue_clear(&cmux
->destroy_cell_queue
);
391 * Circuitmux policy control functions
395 * Remove any policy installed on cmux; all policy data will be freed and
396 * cmux behavior will revert to the built-in round-robin active_circuits
401 circuitmux_clear_policy(circuitmux_t
*cmux
)
405 /* Internally, this is just setting policy to NULL */
406 circuitmux_set_policy(cmux
, NULL
);
410 * Return the policy currently installed on a circuitmux_t
413 MOCK_IMPL(const circuitmux_policy_t
*,
414 circuitmux_get_policy
, (circuitmux_t
*cmux
))
422 * Set policy; allocate for new policy, detach all circuits from old policy
423 * if any, attach them to new policy, and free old policy data.
427 circuitmux_set_policy(circuitmux_t
*cmux
,
428 const circuitmux_policy_t
*pol
)
430 const circuitmux_policy_t
*old_pol
= NULL
, *new_pol
= NULL
;
431 circuitmux_policy_data_t
*old_pol_data
= NULL
, *new_pol_data
= NULL
;
432 chanid_circid_muxinfo_t
**i
= NULL
;
433 channel_t
*chan
= NULL
;
434 uint64_t last_chan_id_searched
= 0;
435 circuit_t
*circ
= NULL
;
439 /* Set up variables */
440 old_pol
= cmux
->policy
;
441 old_pol_data
= cmux
->policy_data
;
444 /* Check if this is the trivial case */
445 if (old_pol
== new_pol
) return;
447 /* Allocate data for new policy, if any */
448 if (new_pol
&& new_pol
->alloc_cmux_data
) {
450 * If alloc_cmux_data is not null, then we expect to get some policy
451 * data. Assert that we also have free_cmux_data so we can free it
452 * when the time comes, and allocate it.
454 tor_assert(new_pol
->free_cmux_data
);
455 new_pol_data
= new_pol
->alloc_cmux_data(cmux
);
456 tor_assert(new_pol_data
);
459 /* Install new policy and new policy data on cmux */
460 cmux
->policy
= new_pol
;
461 cmux
->policy_data
= new_pol_data
;
463 /* Iterate over all circuits, attaching/detaching each one */
464 i
= HT_START(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
);
466 /* Assert that this entry isn't NULL */
470 * Get the channel; since normal case is all circuits on the mux share a
471 * channel, we cache last_chan_id_searched
473 if (!chan
|| last_chan_id_searched
!= (*i
)->chan_id
) {
474 chan
= channel_find_by_global_id((*i
)->chan_id
);
475 last_chan_id_searched
= (*i
)->chan_id
;
479 /* Get the circuit */
480 circ
= circuit_get_by_circid_channel_even_if_marked((*i
)->circ_id
, chan
);
483 /* Need to tell old policy it becomes inactive (i.e., it is active) ? */
484 if (old_pol
&& old_pol
->notify_circ_inactive
&&
485 (*i
)->muxinfo
.cell_count
> 0) {
486 old_pol
->notify_circ_inactive(cmux
, old_pol_data
, circ
,
487 (*i
)->muxinfo
.policy_data
);
490 /* Need to free old policy data? */
491 if ((*i
)->muxinfo
.policy_data
) {
492 /* Assert that we have the means to free it if we have policy data */
494 tor_assert(old_pol
->free_circ_data
);
496 old_pol
->free_circ_data(cmux
, old_pol_data
, circ
,
497 (*i
)->muxinfo
.policy_data
);
498 (*i
)->muxinfo
.policy_data
= NULL
;
501 /* Need to allocate new policy data? */
502 if (new_pol
&& new_pol
->alloc_circ_data
) {
504 * If alloc_circ_data is not null, we expect to get some per-circuit
505 * policy data. Assert that we also have free_circ_data so we can
506 * free it when the time comes, and allocate it.
508 tor_assert(new_pol
->free_circ_data
);
509 (*i
)->muxinfo
.policy_data
=
510 new_pol
->alloc_circ_data(cmux
, new_pol_data
, circ
,
511 (*i
)->muxinfo
.direction
,
512 (*i
)->muxinfo
.cell_count
);
515 /* Need to make active on new policy? */
516 if (new_pol
&& new_pol
->notify_circ_active
&&
517 (*i
)->muxinfo
.cell_count
> 0) {
518 new_pol
->notify_circ_active(cmux
, new_pol_data
, circ
,
519 (*i
)->muxinfo
.policy_data
);
522 /* Advance to next circuit map entry */
523 i
= HT_NEXT(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
, i
);
526 /* Free data for old policy, if any */
529 * If we had old policy data, we should have an old policy and a free
533 tor_assert(old_pol
->free_cmux_data
);
534 old_pol
->free_cmux_data(cmux
, old_pol_data
);
540 * Circuitmux/circuit attachment status inquiry functions
544 * Query the direction of an attached circuit
548 circuitmux_attached_circuit_direction(circuitmux_t
*cmux
, circuit_t
*circ
)
550 chanid_circid_muxinfo_t
*hashent
= NULL
;
552 /* Try to find a map entry */
553 hashent
= circuitmux_find_map_entry(cmux
, circ
);
556 * This function should only be called on attached circuits; assert that
557 * we had a map entry.
561 /* Return the direction from the map entry */
562 return hashent
->muxinfo
.direction
;
566 * Find an entry in the cmux's map for this circuit or return NULL if there
570 static chanid_circid_muxinfo_t
*
571 circuitmux_find_map_entry(circuitmux_t
*cmux
, circuit_t
*circ
)
573 chanid_circid_muxinfo_t search
, *hashent
= NULL
;
575 /* Sanity-check parameters */
577 tor_assert(cmux
->chanid_circid_map
);
580 /* Check if we have n_chan */
582 /* Okay, let's see if it's attached for n_chan/n_circ_id */
583 search
.chan_id
= circ
->n_chan
->global_identifier
;
584 search
.circ_id
= circ
->n_circ_id
;
587 hashent
= HT_FIND(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
591 /* Found something? */
594 * Assert that the direction makes sense for a hashent we found by
595 * n_chan/n_circ_id before we return it.
597 tor_assert(hashent
->muxinfo
.direction
== CELL_DIRECTION_OUT
);
599 /* Not there, have we got a p_chan/p_circ_id to try? */
600 if (circ
->magic
== OR_CIRCUIT_MAGIC
) {
601 search
.circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
602 /* Check for p_chan */
603 if (TO_OR_CIRCUIT(circ
)->p_chan
) {
604 search
.chan_id
= TO_OR_CIRCUIT(circ
)->p_chan
->global_identifier
;
605 /* Okay, search for that */
606 hashent
= HT_FIND(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
610 /* Assert that the direction makes sense before we return it */
611 tor_assert(hashent
->muxinfo
.direction
== CELL_DIRECTION_IN
);
617 /* Okay, hashent is it if it was there */
622 * Query whether a circuit is attached to a circuitmux
626 circuitmux_is_circuit_attached(circuitmux_t
*cmux
, circuit_t
*circ
)
628 chanid_circid_muxinfo_t
*hashent
= NULL
;
630 /* Look if it's in the circuit map */
631 hashent
= circuitmux_find_map_entry(cmux
, circ
);
633 return (hashent
!= NULL
);
637 * Query whether a circuit is active on a circuitmux
641 circuitmux_is_circuit_active(circuitmux_t
*cmux
, circuit_t
*circ
)
643 chanid_circid_muxinfo_t
*hashent
= NULL
;
649 /* Look if it's in the circuit map */
650 hashent
= circuitmux_find_map_entry(cmux
, circ
);
652 /* Check the number of cells on this circuit */
653 is_active
= (hashent
->muxinfo
.cell_count
> 0);
655 /* else not attached, so not active */
661 * Query number of available cells for a circuit on a circuitmux
665 circuitmux_num_cells_for_circuit(circuitmux_t
*cmux
, circuit_t
*circ
)
667 chanid_circid_muxinfo_t
*hashent
= NULL
;
668 unsigned int n_cells
= 0;
673 /* Look if it's in the circuit map */
674 hashent
= circuitmux_find_map_entry(cmux
, circ
);
676 /* Just get the cell count for this circuit */
677 n_cells
= hashent
->muxinfo
.cell_count
;
679 /* else not attached, so 0 cells */
685 * Query total number of available cells on a circuitmux
688 MOCK_IMPL(unsigned int,
689 circuitmux_num_cells
, (circuitmux_t
*cmux
))
693 return cmux
->n_cells
+ cmux
->destroy_cell_queue
.n
;
697 * Query total number of circuits active on a circuitmux
701 circuitmux_num_active_circuits(circuitmux_t
*cmux
)
705 return cmux
->n_active_circuits
;
709 * Query total number of circuits attached to a circuitmux
713 circuitmux_num_circuits(circuitmux_t
*cmux
)
717 return cmux
->n_circuits
;
721 * Functions for circuit code to call to update circuit status
725 * Attach a circuit to a circuitmux, for the specified direction.
729 circuitmux_attach_circuit
,(circuitmux_t
*cmux
, circuit_t
*circ
,
730 cell_direction_t direction
))
732 channel_t
*chan
= NULL
;
735 chanid_circid_muxinfo_t search
, *hashent
= NULL
;
736 unsigned int cell_count
;
740 tor_assert(direction
== CELL_DIRECTION_IN
||
741 direction
== CELL_DIRECTION_OUT
);
744 * Figure out which channel we're using, and get the circuit's current
745 * cell count and circuit ID; assert that the circuit is not already
746 * attached to another mux.
748 if (direction
== CELL_DIRECTION_OUT
) {
751 cell_count
= circ
->n_chan_cells
.n
;
752 circ_id
= circ
->n_circ_id
;
755 chan
= TO_OR_CIRCUIT(circ
)->p_chan
;
756 cell_count
= TO_OR_CIRCUIT(circ
)->p_chan_cells
.n
;
757 circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
759 /* Assert that we did get a channel */
761 /* Assert that the circuit ID is sensible */
762 tor_assert(circ_id
!= 0);
764 /* Get the channel ID */
765 channel_id
= chan
->global_identifier
;
767 /* See if we already have this one */
768 search
.chan_id
= channel_id
;
769 search
.circ_id
= circ_id
;
770 hashent
= HT_FIND(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
775 * This circuit was already attached to this cmux; make sure the
776 * directions match and update the cell count and active circuit count.
779 "Circuit %u on channel %"PRIu64
" was already attached to "
780 "(trying to attach to %p)",
781 (unsigned)circ_id
, (channel_id
),
785 * The mux pointer on this circuit and the direction in result should
786 * match; otherwise assert.
788 tor_assert(hashent
->muxinfo
.direction
== direction
);
791 * Looks okay; just update the cell count and active circuits if we must
793 if (hashent
->muxinfo
.cell_count
> 0 && cell_count
== 0) {
794 --(cmux
->n_active_circuits
);
795 circuitmux_make_circuit_inactive(cmux
, circ
);
796 } else if (hashent
->muxinfo
.cell_count
== 0 && cell_count
> 0) {
797 ++(cmux
->n_active_circuits
);
798 circuitmux_make_circuit_active(cmux
, circ
);
800 cmux
->n_cells
-= hashent
->muxinfo
.cell_count
;
801 cmux
->n_cells
+= cell_count
;
802 hashent
->muxinfo
.cell_count
= cell_count
;
805 * New circuit; add an entry and update the circuit/active circuit
809 "Attaching circuit %u on channel %"PRIu64
" to cmux %p",
810 (unsigned)circ_id
, (channel_id
), cmux
);
812 /* Insert it in the map */
813 hashent
= tor_malloc_zero(sizeof(*hashent
));
814 hashent
->chan_id
= channel_id
;
815 hashent
->circ_id
= circ_id
;
816 hashent
->muxinfo
.cell_count
= cell_count
;
817 hashent
->muxinfo
.direction
= direction
;
818 /* Allocate policy specific circuit data if we need it */
819 if (cmux
->policy
->alloc_circ_data
) {
820 /* Assert that we have the means to free policy-specific data */
821 tor_assert(cmux
->policy
->free_circ_data
);
823 hashent
->muxinfo
.policy_data
=
824 cmux
->policy
->alloc_circ_data(cmux
,
829 /* If we wanted policy data, it's an error not to get any */
830 tor_assert(hashent
->muxinfo
.policy_data
);
832 HT_INSERT(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
835 /* Update counters */
836 ++(cmux
->n_circuits
);
837 if (cell_count
> 0) {
838 ++(cmux
->n_active_circuits
);
839 circuitmux_make_circuit_active(cmux
, circ
);
841 cmux
->n_cells
+= cell_count
;
846 * Detach a circuit from a circuitmux and update all counters as needed;
847 * no-op if not attached.
851 circuitmux_detach_circuit
,(circuitmux_t
*cmux
, circuit_t
*circ
))
853 chanid_circid_muxinfo_t search
, *hashent
= NULL
;
855 * Use this to keep track of whether we found it for n_chan or
856 * p_chan for consistency checking.
858 * The 0 initializer is not a valid cell_direction_t value.
859 * We assert that it has been replaced with a valid value before it is used.
861 cell_direction_t last_searched_direction
= 0;
864 tor_assert(cmux
->chanid_circid_map
);
867 /* See if we have it for n_chan/n_circ_id */
869 search
.chan_id
= circ
->n_chan
->global_identifier
;
870 search
.circ_id
= circ
->n_circ_id
;
871 hashent
= HT_FIND(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
873 last_searched_direction
= CELL_DIRECTION_OUT
;
876 /* Got one? If not, see if it's an or_circuit_t and try p_chan/p_circ_id */
878 if (circ
->magic
== OR_CIRCUIT_MAGIC
) {
879 search
.circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
880 if (TO_OR_CIRCUIT(circ
)->p_chan
) {
881 search
.chan_id
= TO_OR_CIRCUIT(circ
)->p_chan
->global_identifier
;
882 hashent
= HT_FIND(chanid_circid_muxinfo_map
,
883 cmux
->chanid_circid_map
,
885 last_searched_direction
= CELL_DIRECTION_IN
;
890 tor_assert(last_searched_direction
== CELL_DIRECTION_OUT
891 || last_searched_direction
== CELL_DIRECTION_IN
);
894 * If hashent isn't NULL, we have a circuit to detach; don't remove it from
895 * the map until later of circuitmux_make_circuit_inactive() breaks.
898 /* Update counters */
899 --(cmux
->n_circuits
);
900 if (hashent
->muxinfo
.cell_count
> 0) {
901 --(cmux
->n_active_circuits
);
902 /* This does policy notifies, so comes before freeing policy data */
903 circuitmux_make_circuit_inactive(cmux
, circ
);
905 cmux
->n_cells
-= hashent
->muxinfo
.cell_count
;
907 /* Free policy-specific data if we have it */
908 if (hashent
->muxinfo
.policy_data
) {
909 /* If we have policy data, assert that we have the means to free it */
910 tor_assert(cmux
->policy
);
911 tor_assert(cmux
->policy
->free_circ_data
);
912 /* Call free_circ_data() */
913 cmux
->policy
->free_circ_data(cmux
,
916 hashent
->muxinfo
.policy_data
);
917 hashent
->muxinfo
.policy_data
= NULL
;
920 /* Consistency check: the direction must match the direction searched */
921 tor_assert(last_searched_direction
== hashent
->muxinfo
.direction
);
923 /* Now remove it from the map */
924 HT_REMOVE(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
, hashent
);
926 /* Wipe and free the hash entry */
927 // This isn't sensitive, but we want to be sure to know if we're accessing
928 // this accidentally.
929 memwipe(hashent
, 0xef, sizeof(*hashent
));
935 * Make a circuit active; update active list and policy-specific info, but
936 * we don't mess with the counters or hash table here.
940 circuitmux_make_circuit_active(circuitmux_t
*cmux
, circuit_t
*circ
)
943 tor_assert(cmux
->policy
);
946 /* Policy-specific notification */
947 if (cmux
->policy
->notify_circ_active
) {
948 /* Okay, we need to check the circuit for policy data now */
949 chanid_circid_muxinfo_t
*hashent
= circuitmux_find_map_entry(cmux
, circ
);
950 /* We should have found something */
953 cmux
->policy
->notify_circ_active(cmux
, cmux
->policy_data
,
954 circ
, hashent
->muxinfo
.policy_data
);
959 * Make a circuit inactive; update active list and policy-specific info, but
960 * we don't mess with the counters or hash table here.
964 circuitmux_make_circuit_inactive(circuitmux_t
*cmux
, circuit_t
*circ
)
967 tor_assert(cmux
->policy
);
970 /* Policy-specific notification */
971 if (cmux
->policy
->notify_circ_inactive
) {
972 /* Okay, we need to check the circuit for policy data now */
973 chanid_circid_muxinfo_t
*hashent
= circuitmux_find_map_entry(cmux
, circ
);
974 /* We should have found something */
977 cmux
->policy
->notify_circ_inactive(cmux
, cmux
->policy_data
,
978 circ
, hashent
->muxinfo
.policy_data
);
983 * Clear the cell counter for a circuit on a circuitmux
987 circuitmux_clear_num_cells(circuitmux_t
*cmux
, circuit_t
*circ
)
989 /* This is the same as setting the cell count to zero */
990 circuitmux_set_num_cells(cmux
, circ
, 0);
994 * Set the cell counter for a circuit on a circuitmux
998 circuitmux_set_num_cells(circuitmux_t
*cmux
, circuit_t
*circ
,
999 unsigned int n_cells
)
1001 chanid_circid_muxinfo_t
*hashent
= NULL
;
1006 /* Search for this circuit's entry */
1007 hashent
= circuitmux_find_map_entry(cmux
, circ
);
1008 /* Assert that we found one */
1009 tor_assert(hashent
);
1011 /* Update cmux cell counter */
1012 cmux
->n_cells
-= hashent
->muxinfo
.cell_count
;
1013 cmux
->n_cells
+= n_cells
;
1015 /* Do we need to notify a cmux policy? */
1016 if (cmux
->policy
->notify_set_n_cells
) {
1017 /* Call notify_set_n_cells */
1018 cmux
->policy
->notify_set_n_cells(cmux
,
1021 hashent
->muxinfo
.policy_data
,
1026 * Update cmux active circuit counter: is the old cell count > 0 and the
1027 * new cell count == 0 ?
1029 if (hashent
->muxinfo
.cell_count
> 0 && n_cells
== 0) {
1030 --(cmux
->n_active_circuits
);
1031 hashent
->muxinfo
.cell_count
= n_cells
;
1032 circuitmux_make_circuit_inactive(cmux
, circ
);
1033 /* Is the old cell count == 0 and the new cell count > 0 ? */
1034 } else if (hashent
->muxinfo
.cell_count
== 0 && n_cells
> 0) {
1035 ++(cmux
->n_active_circuits
);
1036 hashent
->muxinfo
.cell_count
= n_cells
;
1037 circuitmux_make_circuit_active(cmux
, circ
);
1039 hashent
->muxinfo
.cell_count
= n_cells
;
1044 * Functions for channel code to call to get a circuit to transmit from or
1045 * notify that cells have been transmitted.
1049 * Pick a circuit to send from, using the active circuits list or a
1050 * circuitmux policy if one is available. This is called from channel.c.
1052 * If we would rather send a destroy cell, return NULL and set
1053 * *<b>destroy_queue_out</b> to the destroy queue.
1055 * If we have nothing to send, set *<b>destroy_queue_out</b> to NULL and
1060 circuitmux_get_first_active_circuit(circuitmux_t
*cmux
,
1061 destroy_cell_queue_t
**destroy_queue_out
)
1063 circuit_t
*circ
= NULL
;
1066 tor_assert(cmux
->policy
);
1067 /* This callback is mandatory. */
1068 tor_assert(cmux
->policy
->pick_active_circuit
);
1069 tor_assert(destroy_queue_out
);
1071 *destroy_queue_out
= NULL
;
1073 if (cmux
->destroy_cell_queue
.n
&&
1074 (!cmux
->last_cell_was_destroy
|| cmux
->n_active_circuits
== 0)) {
1075 /* We have destroy cells to send, and either we just sent a relay cell,
1076 * or we have no relay cells to send. */
1078 /* XXXX We should let the cmux policy have some say in this eventually. */
1079 /* XXXX Alternating is not a terribly brilliant approach here. */
1080 *destroy_queue_out
= &cmux
->destroy_cell_queue
;
1082 cmux
->last_cell_was_destroy
= 1;
1083 } else if (cmux
->n_active_circuits
> 0) {
1084 /* We also must have a cell available for this to be the case */
1085 tor_assert(cmux
->n_cells
> 0);
1086 /* Do we have a policy-provided circuit selector? */
1087 circ
= cmux
->policy
->pick_active_circuit(cmux
, cmux
->policy_data
);
1088 cmux
->last_cell_was_destroy
= 0;
1090 tor_assert(cmux
->n_cells
== 0);
1091 tor_assert(cmux
->destroy_cell_queue
.n
== 0);
1098 * Notify the circuitmux that cells have been sent on a circuit; this
1099 * is called from channel.c.
1103 circuitmux_notify_xmit_cells(circuitmux_t
*cmux
, circuit_t
*circ
,
1104 unsigned int n_cells
)
1106 chanid_circid_muxinfo_t
*hashent
= NULL
;
1107 int becomes_inactive
= 0;
1112 if (n_cells
== 0) return;
1115 * To handle this, we have to:
1117 * 1.) Adjust the circuit's cell counter in the cmux hash table
1118 * 2.) Move the circuit to the tail of the active_circuits linked list
1119 * for this cmux, or make the circuit inactive if the cell count
1121 * 3.) Call cmux->policy->notify_xmit_cells(), if any
1124 /* Find the hash entry */
1125 hashent
= circuitmux_find_map_entry(cmux
, circ
);
1126 /* Assert that we found one */
1127 tor_assert(hashent
);
1129 /* Adjust the cell counter and assert that we had that many cells to send */
1130 tor_assert(n_cells
<= hashent
->muxinfo
.cell_count
);
1131 hashent
->muxinfo
.cell_count
-= n_cells
;
1132 /* Do we need to make the circuit inactive? */
1133 if (hashent
->muxinfo
.cell_count
== 0) becomes_inactive
= 1;
1134 /* Adjust the mux cell counter */
1135 cmux
->n_cells
-= n_cells
;
1138 * We call notify_xmit_cells() before making the circuit inactive if needed,
1139 * so the policy can always count on this coming in on an active circuit.
1141 if (cmux
->policy
->notify_xmit_cells
) {
1142 cmux
->policy
->notify_xmit_cells(cmux
, cmux
->policy_data
, circ
,
1143 hashent
->muxinfo
.policy_data
,
1148 * Now make the circuit inactive if needed; this will call the policy's
1149 * notify_circ_inactive() if present.
1151 if (becomes_inactive
) {
1152 --(cmux
->n_active_circuits
);
1153 circuitmux_make_circuit_inactive(cmux
, circ
);
1158 * Notify the circuitmux that a destroy was sent, so we can update
1163 circuitmux_notify_xmit_destroy(circuitmux_t
*cmux
)
1167 --(cmux
->destroy_ctr
);
1168 --(global_destroy_ctr
);
1170 "Cmux at %p sent a destroy, cmux counter is now %"PRId64
", "
1171 "global counter is now %"PRId64
,
1173 (cmux
->destroy_ctr
),
1174 (global_destroy_ctr
));
1179 circuitmux_append_destroy_cell(channel_t
*chan
,
1184 destroy_cell_queue_append(&cmux
->destroy_cell_queue
, circ_id
, reason
);
1186 /* Destroy entering the queue, update counters */
1187 ++(cmux
->destroy_ctr
);
1188 ++global_destroy_ctr
;
1190 "Cmux at %p queued a destroy for circ %u, cmux counter is now "
1191 "%"PRId64
", global counter is now %"PRId64
,
1193 (cmux
->destroy_ctr
),
1194 (global_destroy_ctr
));
1196 /* XXXX Duplicate code from append_cell_to_circuit_queue */
1197 if (!channel_has_queued_writes(chan
)) {
1198 /* There is no data at all waiting to be sent on the outbuf. Add a
1199 * cell, so that we can notice when it gets flushed, flushed_some can
1200 * get called, and we can start putting more data onto the buffer then.
1202 log_debug(LD_GENERAL
, "Primed a buffer.");
1203 channel_flush_from_first_active_circuit(chan
, 1);
1207 /*DOCDOC; for debugging 12184. This runs slowly. */
1209 circuitmux_count_queued_destroy_cells(const channel_t
*chan
,
1210 const circuitmux_t
*cmux
)
1212 int64_t n_destroy_cells
= cmux
->destroy_ctr
;
1213 int64_t destroy_queue_size
= cmux
->destroy_cell_queue
.n
;
1215 int64_t manual_total
= 0;
1216 int64_t manual_total_in_map
= 0;
1217 destroy_cell_t
*cell
;
1219 TOR_SIMPLEQ_FOREACH(cell
, &cmux
->destroy_cell_queue
.head
, next
) {
1224 if (circuit_id_in_use_on_channel(id
, (channel_t
*)chan
))
1225 ++manual_total_in_map
;
1228 if (n_destroy_cells
!= destroy_queue_size
||
1229 n_destroy_cells
!= manual_total
||
1230 n_destroy_cells
!= manual_total_in_map
) {
1231 log_warn(LD_BUG
, " Discrepancy in counts for queued destroy cells on "
1232 "circuitmux. n=%"PRId64
". queue_size=%"PRId64
". "
1233 "manual_total=%"PRId64
". manual_total_in_map=%"PRId64
".",
1235 (destroy_queue_size
),
1237 (manual_total_in_map
));
1240 return n_destroy_cells
;
1244 * Compare cmuxes to see which is more preferred; return < 0 if
1245 * cmux_1 has higher priority (i.e., cmux_1 < cmux_2 in the scheduler's
1246 * sort order), > 0 if cmux_2 has higher priority, or 0 if they are
1247 * equally preferred.
1249 * If the cmuxes have different cmux policies or the policy does not
1250 * support the cmp_cmux method, return 0.
1254 circuitmux_compare_muxes
, (circuitmux_t
*cmux_1
, circuitmux_t
*cmux_2
))
1256 const circuitmux_policy_t
*policy
;
1261 if (cmux_1
== cmux_2
) {
1262 /* Equivalent because they're the same cmux */
1266 if (cmux_1
->policy
&& cmux_2
->policy
) {
1267 if (cmux_1
->policy
== cmux_2
->policy
) {
1268 policy
= cmux_1
->policy
;
1270 if (policy
->cmp_cmux
) {
1271 /* Okay, we can compare! */
1272 return policy
->cmp_cmux(cmux_1
, cmux_1
->policy_data
,
1273 cmux_2
, cmux_2
->policy_data
);
1276 * Equivalent because the policy doesn't know how to compare between
1282 /* Equivalent because they have different policies */
1286 /* Equivalent because one or both are missing a policy */