1 /* * Copyright (c) 2012-2017, 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.
74 #include "circuitlist.h"
75 #include "circuitmux.h"
79 * Private typedefs for circuitmux.c
83 * Map of muxinfos for circuitmux_t to use; struct is defined below (name
84 * of struct must match HT_HEAD line).
86 typedef struct chanid_circid_muxinfo_map chanid_circid_muxinfo_map_t
;
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_s circuit_muxinfo_t
;
102 * Structures for circuitmux.c
105 struct circuitmux_s
{
106 /* Keep count of attached, active circuits */
107 unsigned int n_circuits
, n_active_circuits
;
109 /* Total number of queued cells on all circuits */
110 unsigned int n_cells
;
113 * Map from (channel ID, circuit ID) pairs to circuit_muxinfo_t
115 chanid_circid_muxinfo_map_t
*chanid_circid_map
;
118 * Double-linked ring of circuits with queued cells waiting for room to
119 * free up on this connection's outbuf. Every time we pull cells from
120 * a circuit, we advance this pointer to the next circuit in the ring.
122 struct circuit_t
*active_circuits_head
, *active_circuits_tail
;
124 /** List of queued destroy cells */
125 cell_queue_t destroy_cell_queue
;
126 /** Boolean: True iff the last cell to circuitmux_get_first_active_circuit
127 * returned the destroy queue. Used to force alternation between
128 * destroy/non-destroy cells.
130 * XXXX There is no reason to think that alternating is a particularly good
131 * approach -- it's just designed to prevent destroys from starving other
134 unsigned int last_cell_was_destroy
: 1;
135 /** Destroy counter: increment this when a destroy gets queued, decrement
136 * when we unqueue it, so we can test to make sure they don't starve.
141 * Circuitmux policy; if this is non-NULL, it can override the built-
142 * in round-robin active circuits behavior. This is how EWMA works in
143 * the new circuitmux_t world.
145 const circuitmux_policy_t
*policy
;
147 /* Policy-specific data */
148 circuitmux_policy_data_t
*policy_data
;
152 * This struct holds whatever we want to store per attached circuit on a
153 * circuitmux_t; right now, just the count of queued cells and the direction.
156 struct circuit_muxinfo_s
{
157 /* Count of cells on this circuit at last update */
158 unsigned int cell_count
;
159 /* Direction of flow */
160 cell_direction_t direction
;
161 /* Policy-specific data */
162 circuitmux_policy_circ_data_t
*policy_data
;
163 /* Mark bit for consistency checker */
168 * A map from channel ID and circuit ID to a circuit_muxinfo_t for that
172 struct chanid_circid_muxinfo_t
{
173 HT_ENTRY(chanid_circid_muxinfo_t
) node
;
176 circuit_muxinfo_t muxinfo
;
180 * Internal-use #defines
184 #define circuitmux_assert_okay_paranoid(cmux) \
185 circuitmux_assert_okay(cmux)
187 #define circuitmux_assert_okay_paranoid(cmux)
188 #endif /* defined(CMUX_PARANOIA) */
191 * Static function declarations
195 chanid_circid_entries_eq(chanid_circid_muxinfo_t
*a
,
196 chanid_circid_muxinfo_t
*b
);
197 static inline unsigned int
198 chanid_circid_entry_hash(chanid_circid_muxinfo_t
*a
);
199 static chanid_circid_muxinfo_t
*
200 circuitmux_find_map_entry(circuitmux_t
*cmux
, circuit_t
*circ
);
202 circuitmux_make_circuit_active(circuitmux_t
*cmux
, circuit_t
*circ
,
203 cell_direction_t direction
);
205 circuitmux_make_circuit_inactive(circuitmux_t
*cmux
, circuit_t
*circ
,
206 cell_direction_t direction
);
208 circuitmux_move_active_circ_to_tail(circuitmux_t
*cmux
, circuit_t
*circ
,
209 cell_direction_t direction
);
210 static inline circuit_t
**
211 circuitmux_next_active_circ_p(circuitmux_t
*cmux
, circuit_t
*circ
);
212 static inline circuit_t
**
213 circuitmux_prev_active_circ_p(circuitmux_t
*cmux
, circuit_t
*circ
);
214 static void circuitmux_assert_okay_pass_one(circuitmux_t
*cmux
);
215 static void circuitmux_assert_okay_pass_two(circuitmux_t
*cmux
);
216 static void circuitmux_assert_okay_pass_three(circuitmux_t
*cmux
);
218 /* Static global variables */
220 /** Count the destroy balance to debug destroy queue logic */
221 static int64_t global_destroy_ctr
= 0;
223 /* Function definitions */
226 * Linked list helpers
230 * Move an active circuit to the tail of the cmux's active circuits list;
231 * used by circuitmux_notify_xmit_cells().
235 circuitmux_move_active_circ_to_tail(circuitmux_t
*cmux
, circuit_t
*circ
,
236 cell_direction_t direction
)
238 circuit_t
**next_p
= NULL
, **prev_p
= NULL
;
239 circuit_t
**next_prev
= NULL
, **prev_next
= NULL
;
240 circuit_t
**tail_next
= NULL
;
241 or_circuit_t
*or_circ
= NULL
;
246 circuitmux_assert_okay_paranoid(cmux
);
248 /* Figure out our next_p and prev_p for this cmux/direction */
250 if (direction
== CELL_DIRECTION_OUT
) {
251 tor_assert(circ
->n_mux
== cmux
);
252 next_p
= &(circ
->next_active_on_n_chan
);
253 prev_p
= &(circ
->prev_active_on_n_chan
);
255 or_circ
= TO_OR_CIRCUIT(circ
);
256 tor_assert(or_circ
->p_mux
== cmux
);
257 next_p
= &(or_circ
->next_active_on_p_chan
);
258 prev_p
= &(or_circ
->prev_active_on_p_chan
);
261 if (circ
->n_mux
== cmux
) {
262 next_p
= &(circ
->next_active_on_n_chan
);
263 prev_p
= &(circ
->prev_active_on_n_chan
);
265 or_circ
= TO_OR_CIRCUIT(circ
);
266 tor_assert(or_circ
->p_mux
== cmux
);
267 next_p
= &(or_circ
->next_active_on_p_chan
);
268 prev_p
= &(or_circ
->prev_active_on_p_chan
);
274 /* Check if this really is an active circuit */
275 if ((*next_p
== NULL
&& *prev_p
== NULL
) &&
276 !(circ
== cmux
->active_circuits_head
||
277 circ
== cmux
->active_circuits_tail
)) {
278 /* Not active, no-op */
282 /* Check if this is already the tail */
283 if (circ
== cmux
->active_circuits_tail
) return;
285 /* Okay, we have to move it; figure out next_prev and prev_next */
286 if (*next_p
) next_prev
= circuitmux_prev_active_circ_p(cmux
, *next_p
);
287 if (*prev_p
) prev_next
= circuitmux_next_active_circ_p(cmux
, *prev_p
);
288 /* Adjust the previous node's next pointer, if any */
289 if (prev_next
) *prev_next
= *next_p
;
290 /* Otherwise, we were the head */
291 else cmux
->active_circuits_head
= *next_p
;
292 /* Adjust the next node's previous pointer, if any */
293 if (next_prev
) *next_prev
= *prev_p
;
294 /* We're out of the list; now re-attach at the tail */
295 /* Adjust our next and prev pointers */
297 *prev_p
= cmux
->active_circuits_tail
;
298 /* Set the next pointer of the tail, or the head if none */
299 if (cmux
->active_circuits_tail
) {
300 tail_next
= circuitmux_next_active_circ_p(cmux
,
301 cmux
->active_circuits_tail
);
304 cmux
->active_circuits_head
= circ
;
306 /* Set the tail to this circuit */
307 cmux
->active_circuits_tail
= circ
;
309 circuitmux_assert_okay_paranoid(cmux
);
312 static inline circuit_t
**
313 circuitmux_next_active_circ_p(circuitmux_t
*cmux
, circuit_t
*circ
)
318 if (circ
->n_mux
== cmux
) return &(circ
->next_active_on_n_chan
);
320 tor_assert(TO_OR_CIRCUIT(circ
)->p_mux
== cmux
);
321 return &(TO_OR_CIRCUIT(circ
)->next_active_on_p_chan
);
325 static inline circuit_t
**
326 circuitmux_prev_active_circ_p(circuitmux_t
*cmux
, circuit_t
*circ
)
331 if (circ
->n_mux
== cmux
) return &(circ
->prev_active_on_n_chan
);
333 tor_assert(TO_OR_CIRCUIT(circ
)->p_mux
== cmux
);
334 return &(TO_OR_CIRCUIT(circ
)->prev_active_on_p_chan
);
339 * Helper for chanid_circid_cell_count_map_t hash table: compare the channel
340 * ID and circuit ID for a and b, and return less than, equal to, or greater
341 * than zero appropriately.
345 chanid_circid_entries_eq(chanid_circid_muxinfo_t
*a
,
346 chanid_circid_muxinfo_t
*b
)
348 return a
->chan_id
== b
->chan_id
&& a
->circ_id
== b
->circ_id
;
352 * Helper: return a hash based on circuit ID and channel ID in a.
355 static inline unsigned int
356 chanid_circid_entry_hash(chanid_circid_muxinfo_t
*a
)
358 return (((unsigned int)(a
->circ_id
) << 8) ^
359 ((unsigned int)((a
->chan_id
>> 32) & 0xffffffff)) ^
360 ((unsigned int)(a
->chan_id
& 0xffffffff)));
363 /* Declare the struct chanid_circid_muxinfo_map type */
364 HT_HEAD(chanid_circid_muxinfo_map
, chanid_circid_muxinfo_t
);
366 /* Emit a bunch of hash table stuff */
367 HT_PROTOTYPE(chanid_circid_muxinfo_map
, chanid_circid_muxinfo_t
, node
,
368 chanid_circid_entry_hash
, chanid_circid_entries_eq
)
369 HT_GENERATE2(chanid_circid_muxinfo_map
, chanid_circid_muxinfo_t
, node
,
370 chanid_circid_entry_hash
, chanid_circid_entries_eq
, 0.6,
371 tor_reallocarray_
, tor_free_
)
374 * Circuitmux alloc/free functions
378 * Allocate a new circuitmux_t
382 circuitmux_alloc(void)
384 circuitmux_t
*rv
= NULL
;
386 rv
= tor_malloc_zero(sizeof(*rv
));
387 rv
->chanid_circid_map
= tor_malloc_zero(sizeof(*( rv
->chanid_circid_map
)));
388 HT_INIT(chanid_circid_muxinfo_map
, rv
->chanid_circid_map
);
389 cell_queue_init(&rv
->destroy_cell_queue
);
395 * Detach all circuits from a circuitmux (use before circuitmux_free())
397 * If <b>detached_out</b> is non-NULL, add every detached circuit_t to
402 circuitmux_detach_all_circuits(circuitmux_t
*cmux
, smartlist_t
*detached_out
)
404 chanid_circid_muxinfo_t
**i
= NULL
, *to_remove
;
405 channel_t
*chan
= NULL
;
406 circuit_t
*circ
= NULL
;
410 * Don't circuitmux_assert_okay_paranoid() here; this gets called when
411 * channels are being freed and have already been unregistered, so
412 * the channel ID lookups it does will fail.
415 i
= HT_START(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
);
420 log_warn(LD_BUG
, "Somehow, an HT iterator gave us a NULL pointer.");
423 /* Find a channel and circuit */
424 chan
= channel_find_by_global_id(to_remove
->chan_id
);
427 circuit_get_by_circid_channel_even_if_marked(to_remove
->circ_id
,
430 /* Clear the circuit's mux for this direction */
431 if (to_remove
->muxinfo
.direction
== CELL_DIRECTION_OUT
) {
433 * Update active_circuits et al.; this does policy notifies, so
434 * comes before freeing policy data
437 if (to_remove
->muxinfo
.cell_count
> 0) {
438 circuitmux_make_circuit_inactive(cmux
, circ
, CELL_DIRECTION_OUT
);
445 smartlist_add(detached_out
, circ
);
446 } else if (circ
->magic
== OR_CIRCUIT_MAGIC
) {
448 * Update active_circuits et al.; this does policy notifies, so
449 * comes before freeing policy data
452 if (to_remove
->muxinfo
.cell_count
> 0) {
453 circuitmux_make_circuit_inactive(cmux
, circ
, CELL_DIRECTION_IN
);
457 * It has a sensible p_chan and direction == CELL_DIRECTION_IN,
460 TO_OR_CIRCUIT(circ
)->p_mux
= NULL
;
463 smartlist_add(detached_out
, circ
);
465 /* Complain and move on */
467 "Circuit %u/channel " U64_FORMAT
" had direction == "
468 "CELL_DIRECTION_IN, but isn't an or_circuit_t",
469 (unsigned)to_remove
->circ_id
,
470 U64_PRINTF_ARG(to_remove
->chan_id
));
473 /* Free policy-specific data if we have it */
474 if (to_remove
->muxinfo
.policy_data
) {
476 * If we have policy data, assert that we have the means to
479 tor_assert(cmux
->policy
);
480 tor_assert(cmux
->policy
->free_circ_data
);
481 /* Call free_circ_data() */
482 cmux
->policy
->free_circ_data(cmux
,
485 to_remove
->muxinfo
.policy_data
);
486 to_remove
->muxinfo
.policy_data
= NULL
;
489 /* Complain and move on */
491 "Couldn't find circuit %u (for channel " U64_FORMAT
")",
492 (unsigned)to_remove
->circ_id
,
493 U64_PRINTF_ARG(to_remove
->chan_id
));
496 /* Complain and move on */
498 "Couldn't find channel " U64_FORMAT
" (for circuit id %u)",
499 U64_PRINTF_ARG(to_remove
->chan_id
),
500 (unsigned)to_remove
->circ_id
);
503 /* Assert that we don't have un-freed policy data for this circuit */
504 tor_assert(to_remove
->muxinfo
.policy_data
== NULL
);
507 i
= HT_NEXT_RMV(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
, i
);
513 cmux
->n_circuits
= 0;
514 cmux
->n_active_circuits
= 0;
518 /** Reclaim all circuit IDs currently marked as unusable on <b>chan</b> because
519 * of pending destroy cells in <b>cmux</b>.
521 * This function must be called AFTER circuits are unlinked from the (channel,
522 * circuid-id) map with circuit_unlink_all_from_channel(), but before calling
526 circuitmux_mark_destroyed_circids_usable(circuitmux_t
*cmux
, channel_t
*chan
)
530 TOR_SIMPLEQ_FOREACH(cell
, &cmux
->destroy_cell_queue
.head
, next
) {
532 if (packed_cell_is_destroy(chan
, cell
, &circid
)) {
533 channel_mark_circid_usable(chan
, circid
);
539 log_warn(LD_BUG
, "%d cell(s) on destroy queue did not look like a "
540 "DESTROY cell.", n_bad
);
544 * Free a circuitmux_t; the circuits must be detached first with
545 * circuitmux_detach_all_circuits().
549 circuitmux_free(circuitmux_t
*cmux
)
553 tor_assert(cmux
->n_circuits
== 0);
554 tor_assert(cmux
->n_active_circuits
== 0);
557 * Free policy-specific data if we have any; we don't
558 * need to do circuitmux_set_policy(cmux, NULL) to cover
559 * the circuits because they would have been handled in
560 * circuitmux_detach_all_circuits() before this was
563 if (cmux
->policy
&& cmux
->policy
->free_cmux_data
) {
564 if (cmux
->policy_data
) {
565 cmux
->policy
->free_cmux_data(cmux
, cmux
->policy_data
);
566 cmux
->policy_data
= NULL
;
568 } else tor_assert(cmux
->policy_data
== NULL
);
570 if (cmux
->chanid_circid_map
) {
571 HT_CLEAR(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
);
572 tor_free(cmux
->chanid_circid_map
);
576 * We're throwing away some destroys; log the counter and
577 * adjust the global counter by the queue size.
579 if (cmux
->destroy_cell_queue
.n
> 0) {
580 cmux
->destroy_ctr
-= cmux
->destroy_cell_queue
.n
;
581 global_destroy_ctr
-= cmux
->destroy_cell_queue
.n
;
583 "Freeing cmux at %p with %u queued destroys; the last cmux "
584 "destroy balance was "I64_FORMAT
", global is "I64_FORMAT
,
585 cmux
, cmux
->destroy_cell_queue
.n
,
586 I64_PRINTF_ARG(cmux
->destroy_ctr
),
587 I64_PRINTF_ARG(global_destroy_ctr
));
590 "Freeing cmux at %p with no queued destroys, the cmux destroy "
591 "balance was "I64_FORMAT
", global is "I64_FORMAT
,
593 I64_PRINTF_ARG(cmux
->destroy_ctr
),
594 I64_PRINTF_ARG(global_destroy_ctr
));
597 cell_queue_clear(&cmux
->destroy_cell_queue
);
603 * Circuitmux policy control functions
607 * Remove any policy installed on cmux; all policy data will be freed and
608 * cmux behavior will revert to the built-in round-robin active_circuits
613 circuitmux_clear_policy(circuitmux_t
*cmux
)
617 /* Internally, this is just setting policy to NULL */
619 circuitmux_set_policy(cmux
, NULL
);
624 * Return the policy currently installed on a circuitmux_t
627 MOCK_IMPL(const circuitmux_policy_t
*,
628 circuitmux_get_policy
, (circuitmux_t
*cmux
))
636 * Set policy; allocate for new policy, detach all circuits from old policy
637 * if any, attach them to new policy, and free old policy data.
641 circuitmux_set_policy(circuitmux_t
*cmux
,
642 const circuitmux_policy_t
*pol
)
644 const circuitmux_policy_t
*old_pol
= NULL
, *new_pol
= NULL
;
645 circuitmux_policy_data_t
*old_pol_data
= NULL
, *new_pol_data
= NULL
;
646 chanid_circid_muxinfo_t
**i
= NULL
;
647 channel_t
*chan
= NULL
;
648 uint64_t last_chan_id_searched
= 0;
649 circuit_t
*circ
= NULL
;
653 /* Set up variables */
654 old_pol
= cmux
->policy
;
655 old_pol_data
= cmux
->policy_data
;
658 /* Check if this is the trivial case */
659 if (old_pol
== new_pol
) return;
661 /* Allocate data for new policy, if any */
662 if (new_pol
&& new_pol
->alloc_cmux_data
) {
664 * If alloc_cmux_data is not null, then we expect to get some policy
665 * data. Assert that we also have free_cmux_data so we can free it
666 * when the time comes, and allocate it.
668 tor_assert(new_pol
->free_cmux_data
);
669 new_pol_data
= new_pol
->alloc_cmux_data(cmux
);
670 tor_assert(new_pol_data
);
673 /* Install new policy and new policy data on cmux */
674 cmux
->policy
= new_pol
;
675 cmux
->policy_data
= new_pol_data
;
677 /* Iterate over all circuits, attaching/detaching each one */
678 i
= HT_START(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
);
680 /* Assert that this entry isn't NULL */
684 * Get the channel; since normal case is all circuits on the mux share a
685 * channel, we cache last_chan_id_searched
687 if (!chan
|| last_chan_id_searched
!= (*i
)->chan_id
) {
688 chan
= channel_find_by_global_id((*i
)->chan_id
);
689 last_chan_id_searched
= (*i
)->chan_id
;
693 /* Get the circuit */
694 circ
= circuit_get_by_circid_channel_even_if_marked((*i
)->circ_id
, chan
);
697 /* Need to tell old policy it becomes inactive (i.e., it is active) ? */
698 if (old_pol
&& old_pol
->notify_circ_inactive
&&
699 (*i
)->muxinfo
.cell_count
> 0) {
700 old_pol
->notify_circ_inactive(cmux
, old_pol_data
, circ
,
701 (*i
)->muxinfo
.policy_data
);
704 /* Need to free old policy data? */
705 if ((*i
)->muxinfo
.policy_data
) {
706 /* Assert that we have the means to free it if we have policy data */
708 tor_assert(old_pol
->free_circ_data
);
710 old_pol
->free_circ_data(cmux
, old_pol_data
, circ
,
711 (*i
)->muxinfo
.policy_data
);
712 (*i
)->muxinfo
.policy_data
= NULL
;
715 /* Need to allocate new policy data? */
716 if (new_pol
&& new_pol
->alloc_circ_data
) {
718 * If alloc_circ_data is not null, we expect to get some per-circuit
719 * policy data. Assert that we also have free_circ_data so we can
720 * free it when the time comes, and allocate it.
722 tor_assert(new_pol
->free_circ_data
);
723 (*i
)->muxinfo
.policy_data
=
724 new_pol
->alloc_circ_data(cmux
, new_pol_data
, circ
,
725 (*i
)->muxinfo
.direction
,
726 (*i
)->muxinfo
.cell_count
);
729 /* Need to make active on new policy? */
730 if (new_pol
&& new_pol
->notify_circ_active
&&
731 (*i
)->muxinfo
.cell_count
> 0) {
732 new_pol
->notify_circ_active(cmux
, new_pol_data
, circ
,
733 (*i
)->muxinfo
.policy_data
);
736 /* Advance to next circuit map entry */
737 i
= HT_NEXT(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
, i
);
740 /* Free data for old policy, if any */
743 * If we had old policy data, we should have an old policy and a free
747 tor_assert(old_pol
->free_cmux_data
);
748 old_pol
->free_cmux_data(cmux
, old_pol_data
);
754 * Circuitmux/circuit attachment status inquiry functions
758 * Query the direction of an attached circuit
762 circuitmux_attached_circuit_direction(circuitmux_t
*cmux
, circuit_t
*circ
)
764 chanid_circid_muxinfo_t
*hashent
= NULL
;
766 /* Try to find a map entry */
767 hashent
= circuitmux_find_map_entry(cmux
, circ
);
770 * This function should only be called on attached circuits; assert that
771 * we had a map entry.
775 /* Return the direction from the map entry */
776 return hashent
->muxinfo
.direction
;
780 * Find an entry in the cmux's map for this circuit or return NULL if there
784 static chanid_circid_muxinfo_t
*
785 circuitmux_find_map_entry(circuitmux_t
*cmux
, circuit_t
*circ
)
787 chanid_circid_muxinfo_t search
, *hashent
= NULL
;
789 /* Sanity-check parameters */
791 tor_assert(cmux
->chanid_circid_map
);
794 /* Check if we have n_chan */
796 /* Okay, let's see if it's attached for n_chan/n_circ_id */
797 search
.chan_id
= circ
->n_chan
->global_identifier
;
798 search
.circ_id
= circ
->n_circ_id
;
801 hashent
= HT_FIND(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
805 /* Found something? */
808 * Assert that the direction makes sense for a hashent we found by
809 * n_chan/n_circ_id before we return it.
811 tor_assert(hashent
->muxinfo
.direction
== CELL_DIRECTION_OUT
);
813 /* Not there, have we got a p_chan/p_circ_id to try? */
814 if (circ
->magic
== OR_CIRCUIT_MAGIC
) {
815 search
.circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
816 /* Check for p_chan */
817 if (TO_OR_CIRCUIT(circ
)->p_chan
) {
818 search
.chan_id
= TO_OR_CIRCUIT(circ
)->p_chan
->global_identifier
;
819 /* Okay, search for that */
820 hashent
= HT_FIND(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
824 /* Assert that the direction makes sense before we return it */
825 tor_assert(hashent
->muxinfo
.direction
== CELL_DIRECTION_IN
);
831 /* Okay, hashent is it if it was there */
836 * Query whether a circuit is attached to a circuitmux
840 circuitmux_is_circuit_attached(circuitmux_t
*cmux
, circuit_t
*circ
)
842 chanid_circid_muxinfo_t
*hashent
= NULL
;
844 /* Look if it's in the circuit map */
845 hashent
= circuitmux_find_map_entry(cmux
, circ
);
847 return (hashent
!= NULL
);
851 * Query whether a circuit is active on a circuitmux
855 circuitmux_is_circuit_active(circuitmux_t
*cmux
, circuit_t
*circ
)
857 chanid_circid_muxinfo_t
*hashent
= NULL
;
863 /* Look if it's in the circuit map */
864 hashent
= circuitmux_find_map_entry(cmux
, circ
);
866 /* Check the number of cells on this circuit */
867 is_active
= (hashent
->muxinfo
.cell_count
> 0);
869 /* else not attached, so not active */
875 * Query number of available cells for a circuit on a circuitmux
879 circuitmux_num_cells_for_circuit(circuitmux_t
*cmux
, circuit_t
*circ
)
881 chanid_circid_muxinfo_t
*hashent
= NULL
;
882 unsigned int n_cells
= 0;
887 /* Look if it's in the circuit map */
888 hashent
= circuitmux_find_map_entry(cmux
, circ
);
890 /* Just get the cell count for this circuit */
891 n_cells
= hashent
->muxinfo
.cell_count
;
893 /* else not attached, so 0 cells */
899 * Query total number of available cells on a circuitmux
902 MOCK_IMPL(unsigned int,
903 circuitmux_num_cells
, (circuitmux_t
*cmux
))
907 return cmux
->n_cells
+ cmux
->destroy_cell_queue
.n
;
911 * Query total number of circuits active on a circuitmux
915 circuitmux_num_active_circuits(circuitmux_t
*cmux
)
919 return cmux
->n_active_circuits
;
923 * Query total number of circuits attached to a circuitmux
927 circuitmux_num_circuits(circuitmux_t
*cmux
)
931 return cmux
->n_circuits
;
935 * Functions for circuit code to call to update circuit status
939 * Attach a circuit to a circuitmux, for the specified direction.
943 circuitmux_attach_circuit
,(circuitmux_t
*cmux
, circuit_t
*circ
,
944 cell_direction_t direction
))
946 channel_t
*chan
= NULL
;
949 chanid_circid_muxinfo_t search
, *hashent
= NULL
;
950 unsigned int cell_count
;
954 tor_assert(direction
== CELL_DIRECTION_IN
||
955 direction
== CELL_DIRECTION_OUT
);
956 circuitmux_assert_okay_paranoid(cmux
);
959 * Figure out which channel we're using, and get the circuit's current
960 * cell count and circuit ID; assert that the circuit is not already
961 * attached to another mux.
963 if (direction
== CELL_DIRECTION_OUT
) {
966 cell_count
= circ
->n_chan_cells
.n
;
967 circ_id
= circ
->n_circ_id
;
970 chan
= TO_OR_CIRCUIT(circ
)->p_chan
;
971 cell_count
= TO_OR_CIRCUIT(circ
)->p_chan_cells
.n
;
972 circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
974 /* Assert that we did get a channel */
976 /* Assert that the circuit ID is sensible */
977 tor_assert(circ_id
!= 0);
979 /* Get the channel ID */
980 channel_id
= chan
->global_identifier
;
982 /* See if we already have this one */
983 search
.chan_id
= channel_id
;
984 search
.circ_id
= circ_id
;
985 hashent
= HT_FIND(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
990 * This circuit was already attached to this cmux; make sure the
991 * directions match and update the cell count and active circuit count.
994 "Circuit %u on channel " U64_FORMAT
" was already attached to "
995 "cmux %p (trying to attach to %p)",
996 (unsigned)circ_id
, U64_PRINTF_ARG(channel_id
),
997 ((direction
== CELL_DIRECTION_OUT
) ?
998 circ
->n_mux
: TO_OR_CIRCUIT(circ
)->p_mux
),
1002 * The mux pointer on this circuit and the direction in result should
1003 * match; otherwise assert.
1005 if (direction
== CELL_DIRECTION_OUT
) tor_assert(circ
->n_mux
== cmux
);
1006 else tor_assert(TO_OR_CIRCUIT(circ
)->p_mux
== cmux
);
1007 tor_assert(hashent
->muxinfo
.direction
== direction
);
1010 * Looks okay; just update the cell count and active circuits if we must
1012 if (hashent
->muxinfo
.cell_count
> 0 && cell_count
== 0) {
1013 --(cmux
->n_active_circuits
);
1014 circuitmux_make_circuit_inactive(cmux
, circ
, direction
);
1015 } else if (hashent
->muxinfo
.cell_count
== 0 && cell_count
> 0) {
1016 ++(cmux
->n_active_circuits
);
1017 circuitmux_make_circuit_active(cmux
, circ
, direction
);
1019 cmux
->n_cells
-= hashent
->muxinfo
.cell_count
;
1020 cmux
->n_cells
+= cell_count
;
1021 hashent
->muxinfo
.cell_count
= cell_count
;
1024 * New circuit; add an entry and update the circuit/active circuit
1028 "Attaching circuit %u on channel " U64_FORMAT
" to cmux %p",
1029 (unsigned)circ_id
, U64_PRINTF_ARG(channel_id
), cmux
);
1032 * Assert that the circuit doesn't already have a mux for this
1035 if (direction
== CELL_DIRECTION_OUT
) tor_assert(circ
->n_mux
== NULL
);
1036 else tor_assert(TO_OR_CIRCUIT(circ
)->p_mux
== NULL
);
1038 /* Insert it in the map */
1039 hashent
= tor_malloc_zero(sizeof(*hashent
));
1040 hashent
->chan_id
= channel_id
;
1041 hashent
->circ_id
= circ_id
;
1042 hashent
->muxinfo
.cell_count
= cell_count
;
1043 hashent
->muxinfo
.direction
= direction
;
1044 /* Allocate policy specific circuit data if we need it */
1045 if (cmux
->policy
&& cmux
->policy
->alloc_circ_data
) {
1046 /* Assert that we have the means to free policy-specific data */
1047 tor_assert(cmux
->policy
->free_circ_data
);
1049 hashent
->muxinfo
.policy_data
=
1050 cmux
->policy
->alloc_circ_data(cmux
,
1055 /* If we wanted policy data, it's an error not to get any */
1056 tor_assert(hashent
->muxinfo
.policy_data
);
1058 HT_INSERT(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
1061 /* Set the circuit's mux for this direction */
1062 if (direction
== CELL_DIRECTION_OUT
) circ
->n_mux
= cmux
;
1063 else TO_OR_CIRCUIT(circ
)->p_mux
= cmux
;
1065 /* Make sure the next/prev pointers are NULL */
1066 if (direction
== CELL_DIRECTION_OUT
) {
1067 circ
->next_active_on_n_chan
= NULL
;
1068 circ
->prev_active_on_n_chan
= NULL
;
1070 TO_OR_CIRCUIT(circ
)->next_active_on_p_chan
= NULL
;
1071 TO_OR_CIRCUIT(circ
)->prev_active_on_p_chan
= NULL
;
1074 /* Update counters */
1075 ++(cmux
->n_circuits
);
1076 if (cell_count
> 0) {
1077 ++(cmux
->n_active_circuits
);
1078 circuitmux_make_circuit_active(cmux
, circ
, direction
);
1080 cmux
->n_cells
+= cell_count
;
1083 circuitmux_assert_okay_paranoid(cmux
);
1087 * Detach a circuit from a circuitmux and update all counters as needed;
1088 * no-op if not attached.
1092 circuitmux_detach_circuit
,(circuitmux_t
*cmux
, circuit_t
*circ
))
1094 chanid_circid_muxinfo_t search
, *hashent
= NULL
;
1096 * Use this to keep track of whether we found it for n_chan or
1097 * p_chan for consistency checking.
1099 * The 0 initializer is not a valid cell_direction_t value.
1100 * We assert that it has been replaced with a valid value before it is used.
1102 cell_direction_t last_searched_direction
= 0;
1105 tor_assert(cmux
->chanid_circid_map
);
1107 circuitmux_assert_okay_paranoid(cmux
);
1109 /* See if we have it for n_chan/n_circ_id */
1111 search
.chan_id
= circ
->n_chan
->global_identifier
;
1112 search
.circ_id
= circ
->n_circ_id
;
1113 hashent
= HT_FIND(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
1115 last_searched_direction
= CELL_DIRECTION_OUT
;
1118 /* Got one? If not, see if it's an or_circuit_t and try p_chan/p_circ_id */
1120 if (circ
->magic
== OR_CIRCUIT_MAGIC
) {
1121 search
.circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
1122 if (TO_OR_CIRCUIT(circ
)->p_chan
) {
1123 search
.chan_id
= TO_OR_CIRCUIT(circ
)->p_chan
->global_identifier
;
1124 hashent
= HT_FIND(chanid_circid_muxinfo_map
,
1125 cmux
->chanid_circid_map
,
1127 last_searched_direction
= CELL_DIRECTION_IN
;
1132 tor_assert(last_searched_direction
== CELL_DIRECTION_OUT
1133 || last_searched_direction
== CELL_DIRECTION_IN
);
1136 * If hashent isn't NULL, we have a circuit to detach; don't remove it from
1137 * the map until later of circuitmux_make_circuit_inactive() breaks.
1140 /* Update counters */
1141 --(cmux
->n_circuits
);
1142 if (hashent
->muxinfo
.cell_count
> 0) {
1143 --(cmux
->n_active_circuits
);
1144 /* This does policy notifies, so comes before freeing policy data */
1145 circuitmux_make_circuit_inactive(cmux
, circ
, last_searched_direction
);
1147 cmux
->n_cells
-= hashent
->muxinfo
.cell_count
;
1149 /* Free policy-specific data if we have it */
1150 if (hashent
->muxinfo
.policy_data
) {
1151 /* If we have policy data, assert that we have the means to free it */
1152 tor_assert(cmux
->policy
);
1153 tor_assert(cmux
->policy
->free_circ_data
);
1154 /* Call free_circ_data() */
1155 cmux
->policy
->free_circ_data(cmux
,
1158 hashent
->muxinfo
.policy_data
);
1159 hashent
->muxinfo
.policy_data
= NULL
;
1162 /* Consistency check: the direction must match the direction searched */
1163 tor_assert(last_searched_direction
== hashent
->muxinfo
.direction
);
1164 /* Clear the circuit's mux for this direction */
1165 if (last_searched_direction
== CELL_DIRECTION_OUT
) circ
->n_mux
= NULL
;
1166 else TO_OR_CIRCUIT(circ
)->p_mux
= NULL
;
1168 /* Now remove it from the map */
1169 HT_REMOVE(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
, hashent
);
1171 /* Free the hash entry */
1175 circuitmux_assert_okay_paranoid(cmux
);
1179 * Make a circuit active; update active list and policy-specific info, but
1180 * we don't mess with the counters or hash table here.
1184 circuitmux_make_circuit_active(circuitmux_t
*cmux
, circuit_t
*circ
,
1185 cell_direction_t direction
)
1187 circuit_t
**next_active
= NULL
, **prev_active
= NULL
, **next_prev
= NULL
;
1188 circuitmux_t
*circuit_cmux
= NULL
;
1189 chanid_circid_muxinfo_t
*hashent
= NULL
;
1190 channel_t
*chan
= NULL
;
1196 tor_assert(direction
== CELL_DIRECTION_OUT
||
1197 direction
== CELL_DIRECTION_IN
);
1199 * Don't circuitmux_assert_okay_paranoid(cmux) here because the cell count
1200 * already got changed and we have to update the list for it to be consistent
1204 /* Get the right set of active list links for this direction */
1205 if (direction
== CELL_DIRECTION_OUT
) {
1206 next_active
= &(circ
->next_active_on_n_chan
);
1207 prev_active
= &(circ
->prev_active_on_n_chan
);
1208 circuit_cmux
= circ
->n_mux
;
1209 chan
= circ
->n_chan
;
1210 circ_id
= circ
->n_circ_id
;
1212 next_active
= &(TO_OR_CIRCUIT(circ
)->next_active_on_p_chan
);
1213 prev_active
= &(TO_OR_CIRCUIT(circ
)->prev_active_on_p_chan
);
1214 circuit_cmux
= TO_OR_CIRCUIT(circ
)->p_mux
;
1215 chan
= TO_OR_CIRCUIT(circ
)->p_chan
;
1216 circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
1219 /* Assert that it is attached to this mux and a channel */
1220 tor_assert(cmux
== circuit_cmux
);
1221 tor_assert(chan
!= NULL
);
1224 * Check if the circuit really was inactive; if it's active, at least one
1225 * of the next_active and prev_active pointers will not be NULL, or this
1226 * circuit will be either the head or tail of the list for this cmux.
1228 already_active
= (*prev_active
!= NULL
|| *next_active
!= NULL
||
1229 cmux
->active_circuits_head
== circ
||
1230 cmux
->active_circuits_tail
== circ
);
1232 /* If we're already active, log a warning and finish */
1233 if (already_active
) {
1235 "Circuit %u on channel " U64_FORMAT
" was already active",
1236 (unsigned)circ_id
, U64_PRINTF_ARG(chan
->global_identifier
));
1241 * This is going at the head of the list; if the old head is not NULL,
1242 * then its prev pointer should point to this.
1244 *next_active
= cmux
->active_circuits_head
; /* Next is old head */
1245 *prev_active
= NULL
; /* Prev is NULL (this will be the head) */
1246 if (cmux
->active_circuits_head
) {
1247 /* The list had an old head; update its prev pointer */
1249 circuitmux_prev_active_circ_p(cmux
, cmux
->active_circuits_head
);
1250 tor_assert(next_prev
);
1253 /* The list was empty; this becomes the tail as well */
1254 cmux
->active_circuits_tail
= circ
;
1256 /* This becomes the new head of the list */
1257 cmux
->active_circuits_head
= circ
;
1259 /* Policy-specific notification */
1261 cmux
->policy
->notify_circ_active
) {
1262 /* Okay, we need to check the circuit for policy data now */
1263 hashent
= circuitmux_find_map_entry(cmux
, circ
);
1264 /* We should have found something */
1265 tor_assert(hashent
);
1267 cmux
->policy
->notify_circ_active(cmux
, cmux
->policy_data
,
1268 circ
, hashent
->muxinfo
.policy_data
);
1271 circuitmux_assert_okay_paranoid(cmux
);
1275 * Make a circuit inactive; update active list and policy-specific info, but
1276 * we don't mess with the counters or hash table here.
1280 circuitmux_make_circuit_inactive(circuitmux_t
*cmux
, circuit_t
*circ
,
1281 cell_direction_t direction
)
1283 circuit_t
**next_active
= NULL
, **prev_active
= NULL
;
1284 circuit_t
**next_prev
= NULL
, **prev_next
= NULL
;
1285 circuitmux_t
*circuit_cmux
= NULL
;
1286 chanid_circid_muxinfo_t
*hashent
= NULL
;
1287 channel_t
*chan
= NULL
;
1289 int already_inactive
;
1293 tor_assert(direction
== CELL_DIRECTION_OUT
||
1294 direction
== CELL_DIRECTION_IN
);
1296 * Don't circuitmux_assert_okay_paranoid(cmux) here because the cell count
1297 * already got changed and we have to update the list for it to be consistent
1301 /* Get the right set of active list links for this direction */
1302 if (direction
== CELL_DIRECTION_OUT
) {
1303 next_active
= &(circ
->next_active_on_n_chan
);
1304 prev_active
= &(circ
->prev_active_on_n_chan
);
1305 circuit_cmux
= circ
->n_mux
;
1306 chan
= circ
->n_chan
;
1307 circ_id
= circ
->n_circ_id
;
1309 next_active
= &(TO_OR_CIRCUIT(circ
)->next_active_on_p_chan
);
1310 prev_active
= &(TO_OR_CIRCUIT(circ
)->prev_active_on_p_chan
);
1311 circuit_cmux
= TO_OR_CIRCUIT(circ
)->p_mux
;
1312 chan
= TO_OR_CIRCUIT(circ
)->p_chan
;
1313 circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
1316 /* Assert that it is attached to this mux and a channel */
1317 tor_assert(cmux
== circuit_cmux
);
1318 tor_assert(chan
!= NULL
);
1321 * Check if the circuit really was active; if it's inactive, the
1322 * next_active and prev_active pointers will be NULL and this circuit
1323 * will not be the head or tail of the list for this cmux.
1325 already_inactive
= (*prev_active
== NULL
&& *next_active
== NULL
&&
1326 cmux
->active_circuits_head
!= circ
&&
1327 cmux
->active_circuits_tail
!= circ
);
1329 /* If we're already inactive, log a warning and finish */
1330 if (already_inactive
) {
1332 "Circuit %d on channel " U64_FORMAT
" was already inactive",
1333 (unsigned)circ_id
, U64_PRINTF_ARG(chan
->global_identifier
));
1337 /* Remove from the list; first get next_prev and prev_next */
1340 * If there's a next circuit, its previous circuit becomes this
1341 * circuit's previous circuit.
1343 next_prev
= circuitmux_prev_active_circ_p(cmux
, *next_active
);
1345 /* Else, the tail becomes this circuit's previous circuit */
1346 next_prev
= &(cmux
->active_circuits_tail
);
1349 /* Got next_prev, now prev_next */
1352 * If there's a previous circuit, its next circuit becomes this circuit's
1355 prev_next
= circuitmux_next_active_circ_p(cmux
, *prev_active
);
1357 /* Else, the head becomes this circuit's next circuit */
1358 prev_next
= &(cmux
->active_circuits_head
);
1361 /* Assert that we got sensible values for the next/prev pointers */
1362 tor_assert(next_prev
!= NULL
);
1363 tor_assert(prev_next
!= NULL
);
1365 /* Update the next/prev pointers - this removes circ from the list */
1366 *next_prev
= *prev_active
;
1367 *prev_next
= *next_active
;
1369 /* Now null out prev_active/next_active */
1370 *prev_active
= NULL
;
1371 *next_active
= NULL
;
1373 /* Policy-specific notification */
1375 cmux
->policy
->notify_circ_inactive
) {
1376 /* Okay, we need to check the circuit for policy data now */
1377 hashent
= circuitmux_find_map_entry(cmux
, circ
);
1378 /* We should have found something */
1379 tor_assert(hashent
);
1381 cmux
->policy
->notify_circ_inactive(cmux
, cmux
->policy_data
,
1382 circ
, hashent
->muxinfo
.policy_data
);
1385 circuitmux_assert_okay_paranoid(cmux
);
1389 * Clear the cell counter for a circuit on a circuitmux
1393 circuitmux_clear_num_cells(circuitmux_t
*cmux
, circuit_t
*circ
)
1395 /* This is the same as setting the cell count to zero */
1396 circuitmux_set_num_cells(cmux
, circ
, 0);
1400 * Set the cell counter for a circuit on a circuitmux
1404 circuitmux_set_num_cells(circuitmux_t
*cmux
, circuit_t
*circ
,
1405 unsigned int n_cells
)
1407 chanid_circid_muxinfo_t
*hashent
= NULL
;
1412 circuitmux_assert_okay_paranoid(cmux
);
1414 /* Search for this circuit's entry */
1415 hashent
= circuitmux_find_map_entry(cmux
, circ
);
1416 /* Assert that we found one */
1417 tor_assert(hashent
);
1419 /* Update cmux cell counter */
1420 cmux
->n_cells
-= hashent
->muxinfo
.cell_count
;
1421 cmux
->n_cells
+= n_cells
;
1423 /* Do we need to notify a cmux policy? */
1424 if (cmux
->policy
&& cmux
->policy
->notify_set_n_cells
) {
1425 /* Call notify_set_n_cells */
1426 cmux
->policy
->notify_set_n_cells(cmux
,
1429 hashent
->muxinfo
.policy_data
,
1434 * Update cmux active circuit counter: is the old cell count > 0 and the
1435 * new cell count == 0 ?
1437 if (hashent
->muxinfo
.cell_count
> 0 && n_cells
== 0) {
1438 --(cmux
->n_active_circuits
);
1439 hashent
->muxinfo
.cell_count
= n_cells
;
1440 circuitmux_make_circuit_inactive(cmux
, circ
, hashent
->muxinfo
.direction
);
1441 /* Is the old cell count == 0 and the new cell count > 0 ? */
1442 } else if (hashent
->muxinfo
.cell_count
== 0 && n_cells
> 0) {
1443 ++(cmux
->n_active_circuits
);
1444 hashent
->muxinfo
.cell_count
= n_cells
;
1445 circuitmux_make_circuit_active(cmux
, circ
, hashent
->muxinfo
.direction
);
1448 * Update the entry cell count like this so we can put a
1449 * circuitmux_assert_okay_paranoid inside make_circuit_(in)active() too.
1451 hashent
->muxinfo
.cell_count
= n_cells
;
1454 circuitmux_assert_okay_paranoid(cmux
);
1458 * Functions for channel code to call to get a circuit to transmit from or
1459 * notify that cells have been transmitted.
1463 * Pick a circuit to send from, using the active circuits list or a
1464 * circuitmux policy if one is available. This is called from channel.c.
1466 * If we would rather send a destroy cell, return NULL and set
1467 * *<b>destroy_queue_out</b> to the destroy queue.
1469 * If we have nothing to send, set *<b>destroy_queue_out</b> to NULL and
1474 circuitmux_get_first_active_circuit(circuitmux_t
*cmux
,
1475 cell_queue_t
**destroy_queue_out
)
1477 circuit_t
*circ
= NULL
;
1480 tor_assert(destroy_queue_out
);
1482 *destroy_queue_out
= NULL
;
1484 if (cmux
->destroy_cell_queue
.n
&&
1485 (!cmux
->last_cell_was_destroy
|| cmux
->n_active_circuits
== 0)) {
1486 /* We have destroy cells to send, and either we just sent a relay cell,
1487 * or we have no relay cells to send. */
1489 /* XXXX We should let the cmux policy have some say in this eventually. */
1490 /* XXXX Alternating is not a terribly brilliant approach here. */
1491 *destroy_queue_out
= &cmux
->destroy_cell_queue
;
1493 cmux
->last_cell_was_destroy
= 1;
1494 } else if (cmux
->n_active_circuits
> 0) {
1495 /* We also must have a cell available for this to be the case */
1496 tor_assert(cmux
->n_cells
> 0);
1497 /* Do we have a policy-provided circuit selector? */
1498 if (cmux
->policy
&& cmux
->policy
->pick_active_circuit
) {
1499 circ
= cmux
->policy
->pick_active_circuit(cmux
, cmux
->policy_data
);
1501 /* Fall back on the head of the active circuits list */
1503 tor_assert(cmux
->active_circuits_head
);
1504 circ
= cmux
->active_circuits_head
;
1506 cmux
->last_cell_was_destroy
= 0;
1508 tor_assert(cmux
->n_cells
== 0);
1509 tor_assert(cmux
->destroy_cell_queue
.n
== 0);
1516 * Notify the circuitmux that cells have been sent on a circuit; this
1517 * is called from channel.c.
1521 circuitmux_notify_xmit_cells(circuitmux_t
*cmux
, circuit_t
*circ
,
1522 unsigned int n_cells
)
1524 chanid_circid_muxinfo_t
*hashent
= NULL
;
1525 int becomes_inactive
= 0;
1529 circuitmux_assert_okay_paranoid(cmux
);
1531 if (n_cells
== 0) return;
1534 * To handle this, we have to:
1536 * 1.) Adjust the circuit's cell counter in the cmux hash table
1537 * 2.) Move the circuit to the tail of the active_circuits linked list
1538 * for this cmux, or make the circuit inactive if the cell count
1540 * 3.) Call cmux->policy->notify_xmit_cells(), if any
1543 /* Find the hash entry */
1544 hashent
= circuitmux_find_map_entry(cmux
, circ
);
1545 /* Assert that we found one */
1546 tor_assert(hashent
);
1548 /* Adjust the cell counter and assert that we had that many cells to send */
1549 tor_assert(n_cells
<= hashent
->muxinfo
.cell_count
);
1550 hashent
->muxinfo
.cell_count
-= n_cells
;
1551 /* Do we need to make the circuit inactive? */
1552 if (hashent
->muxinfo
.cell_count
== 0) becomes_inactive
= 1;
1553 /* Adjust the mux cell counter */
1554 cmux
->n_cells
-= n_cells
;
1556 /* If we aren't making it inactive later, move it to the tail of the list */
1557 if (!becomes_inactive
) {
1558 circuitmux_move_active_circ_to_tail(cmux
, circ
,
1559 hashent
->muxinfo
.direction
);
1563 * We call notify_xmit_cells() before making the circuit inactive if needed,
1564 * so the policy can always count on this coming in on an active circuit.
1566 if (cmux
->policy
&& cmux
->policy
->notify_xmit_cells
) {
1567 cmux
->policy
->notify_xmit_cells(cmux
, cmux
->policy_data
, circ
,
1568 hashent
->muxinfo
.policy_data
,
1573 * Now make the circuit inactive if needed; this will call the policy's
1574 * notify_circ_inactive() if present.
1576 if (becomes_inactive
) {
1577 --(cmux
->n_active_circuits
);
1578 circuitmux_make_circuit_inactive(cmux
, circ
, hashent
->muxinfo
.direction
);
1581 circuitmux_assert_okay_paranoid(cmux
);
1585 * Notify the circuitmux that a destroy was sent, so we can update
1590 circuitmux_notify_xmit_destroy(circuitmux_t
*cmux
)
1594 --(cmux
->destroy_ctr
);
1595 --(global_destroy_ctr
);
1597 "Cmux at %p sent a destroy, cmux counter is now "I64_FORMAT
", "
1598 "global counter is now "I64_FORMAT
,
1600 I64_PRINTF_ARG(cmux
->destroy_ctr
),
1601 I64_PRINTF_ARG(global_destroy_ctr
));
1605 * Circuitmux consistency checking assertions
1609 * Check that circuitmux data structures are consistent and fail with an
1614 circuitmux_assert_okay(circuitmux_t
*cmux
)
1619 * Pass 1: iterate the hash table; for each entry:
1620 * a) Check that the circuit has this cmux for n_mux or p_mux
1621 * b) If the cell_count is > 0, set the mark bit; otherwise clear it
1622 * c) Also check activeness (cell_count > 0 should be active)
1623 * d) Count the number of circuits, active circuits and queued cells
1624 * and at the end check that they match the counters in the cmux.
1626 * Pass 2: iterate the active circuits list; for each entry,
1627 * make sure the circuit is attached to this mux and appears
1628 * in the hash table. Make sure the mark bit is 1, and clear
1629 * it in the hash table entry. Consistency-check the linked
1632 * Pass 3: iterate the hash table again; assert if any active circuits
1633 * (mark bit set to 1) are discovered that weren't cleared in pass 2
1634 * (don't appear in the linked list).
1637 circuitmux_assert_okay_pass_one(cmux
);
1638 circuitmux_assert_okay_pass_two(cmux
);
1639 circuitmux_assert_okay_pass_three(cmux
);
1643 * Do the first pass of circuitmux_assert_okay(); see the comment in that
1648 circuitmux_assert_okay_pass_one(circuitmux_t
*cmux
)
1650 chanid_circid_muxinfo_t
**i
= NULL
;
1655 or_circuit_t
*or_circ
;
1656 circuit_t
**next_p
, **prev_p
;
1657 unsigned int n_circuits
, n_active_circuits
, n_cells
;
1660 tor_assert(cmux
->chanid_circid_map
);
1662 /* Reset the counters */
1663 n_circuits
= n_active_circuits
= n_cells
= 0;
1664 /* Start iterating the hash table */
1665 i
= HT_START(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
);
1667 /* Assert that the hash table entry isn't null */
1670 /* Get the channel and circuit id */
1671 chan_id
= (*i
)->chan_id
;
1672 circ_id
= (*i
)->circ_id
;
1674 /* Find the channel and circuit, assert that they exist */
1675 chan
= channel_find_by_global_id(chan_id
);
1677 circ
= circuit_get_by_circid_channel_even_if_marked(circ_id
, chan
);
1680 /* Assert that we know which direction this is going */
1681 tor_assert((*i
)->muxinfo
.direction
== CELL_DIRECTION_OUT
||
1682 (*i
)->muxinfo
.direction
== CELL_DIRECTION_IN
);
1684 if ((*i
)->muxinfo
.direction
== CELL_DIRECTION_OUT
) {
1685 /* We should be n_mux on this circuit */
1686 tor_assert(cmux
== circ
->n_mux
);
1687 tor_assert(chan
== circ
->n_chan
);
1688 /* Get next and prev for next test */
1689 next_p
= &(circ
->next_active_on_n_chan
);
1690 prev_p
= &(circ
->prev_active_on_n_chan
);
1692 /* This should be an or_circuit_t and we should be p_mux */
1693 or_circ
= TO_OR_CIRCUIT(circ
);
1694 tor_assert(cmux
== or_circ
->p_mux
);
1695 tor_assert(chan
== or_circ
->p_chan
);
1696 /* Get next and prev for next test */
1697 next_p
= &(or_circ
->next_active_on_p_chan
);
1698 prev_p
= &(or_circ
->prev_active_on_p_chan
);
1702 * Should this circuit be active? I.e., does the mux know about > 0
1705 const int circ_is_active
= ((*i
)->muxinfo
.cell_count
> 0);
1707 /* It should be in the linked list iff it's active */
1708 if (circ_is_active
) {
1709 /* Either we have a next link or we are the tail */
1710 tor_assert(*next_p
|| (circ
== cmux
->active_circuits_tail
));
1711 /* Either we have a prev link or we are the head */
1712 tor_assert(*prev_p
|| (circ
== cmux
->active_circuits_head
));
1713 /* Increment the active circuits counter */
1714 ++n_active_circuits
;
1716 /* Shouldn't be in list, so no next or prev link */
1717 tor_assert(!(*next_p
));
1718 tor_assert(!(*prev_p
));
1719 /* And can't be head or tail */
1720 tor_assert(circ
!= cmux
->active_circuits_head
);
1721 tor_assert(circ
!= cmux
->active_circuits_tail
);
1724 /* Increment the circuits counter */
1726 /* Adjust the cell counter */
1727 n_cells
+= (*i
)->muxinfo
.cell_count
;
1729 /* Set the mark bit to circ_is_active */
1730 (*i
)->muxinfo
.mark
= circ_is_active
;
1732 /* Advance to the next entry */
1733 i
= HT_NEXT(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
, i
);
1736 /* Now check the counters */
1737 tor_assert(n_cells
== cmux
->n_cells
);
1738 tor_assert(n_circuits
== cmux
->n_circuits
);
1739 tor_assert(n_active_circuits
== cmux
->n_active_circuits
);
1743 * Do the second pass of circuitmux_assert_okay(); see the comment in that
1748 circuitmux_assert_okay_pass_two(circuitmux_t
*cmux
)
1750 circuit_t
*curr_circ
, *prev_circ
= NULL
, *next_circ
;
1751 or_circuit_t
*curr_or_circ
;
1752 uint64_t curr_chan_id
;
1753 circid_t curr_circ_id
;
1754 circuit_t
**next_p
, **prev_p
;
1756 unsigned int n_active_circuits
= 0;
1757 chanid_circid_muxinfo_t search
, *hashent
= NULL
;
1760 tor_assert(cmux
->chanid_circid_map
);
1763 * Walk the linked list of active circuits in cmux; keep track of the
1764 * previous circuit seen for consistency checking purposes. Count them
1765 * to make sure the number in the linked list matches
1766 * cmux->n_active_circuits.
1768 curr_circ
= cmux
->active_circuits_head
;
1770 /* Reset some things */
1772 curr_or_circ
= NULL
;
1774 next_p
= prev_p
= NULL
;
1775 cell_direction_t direction
;
1777 /* Figure out if this is n_mux or p_mux */
1778 if (cmux
== curr_circ
->n_mux
) {
1779 /* Get next_p and prev_p */
1780 next_p
= &(curr_circ
->next_active_on_n_chan
);
1781 prev_p
= &(curr_circ
->prev_active_on_n_chan
);
1782 /* Get the channel */
1783 chan
= curr_circ
->n_chan
;
1784 /* Get the circuit id */
1785 curr_circ_id
= curr_circ
->n_circ_id
;
1786 /* Remember the direction */
1787 direction
= CELL_DIRECTION_OUT
;
1789 /* We must be p_mux and this must be an or_circuit_t */
1790 curr_or_circ
= TO_OR_CIRCUIT(curr_circ
);
1791 tor_assert(cmux
== curr_or_circ
->p_mux
);
1792 /* Get next_p and prev_p */
1793 next_p
= &(curr_or_circ
->next_active_on_p_chan
);
1794 prev_p
= &(curr_or_circ
->prev_active_on_p_chan
);
1795 /* Get the channel */
1796 chan
= curr_or_circ
->p_chan
;
1797 /* Get the circuit id */
1798 curr_circ_id
= curr_or_circ
->p_circ_id
;
1799 /* Remember the direction */
1800 direction
= CELL_DIRECTION_IN
;
1803 /* Assert that we got a channel and get the channel ID */
1805 curr_chan_id
= chan
->global_identifier
;
1807 /* Assert that prev_p points to last circuit we saw */
1808 tor_assert(*prev_p
== prev_circ
);
1809 /* If that's NULL, assert that we are the head */
1810 if (!(*prev_p
)) tor_assert(curr_circ
== cmux
->active_circuits_head
);
1812 /* Get the next circuit */
1813 next_circ
= *next_p
;
1814 /* If it's NULL, assert that we are the tail */
1815 if (!(*next_p
)) tor_assert(curr_circ
== cmux
->active_circuits_tail
);
1817 /* Now find the hash table entry for this circuit */
1818 search
.chan_id
= curr_chan_id
;
1819 search
.circ_id
= curr_circ_id
;
1820 hashent
= HT_FIND(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
,
1823 /* Assert that we have one */
1824 tor_assert(hashent
);
1826 /* Assert that the direction matches */
1827 tor_assert(direction
== hashent
->muxinfo
.direction
);
1829 /* Assert that the hash entry got marked in pass one */
1830 tor_assert(hashent
->muxinfo
.mark
);
1832 /* Clear the mark */
1833 hashent
->muxinfo
.mark
= 0;
1835 /* Increment the counter */
1836 ++n_active_circuits
;
1838 /* Advance to the next active circuit and update prev_circ */
1839 prev_circ
= curr_circ
;
1840 curr_circ
= next_circ
;
1843 /* Assert that the counter matches the cmux */
1844 tor_assert(n_active_circuits
== cmux
->n_active_circuits
);
1848 * Do the third pass of circuitmux_assert_okay(); see the comment in that
1853 circuitmux_assert_okay_pass_three(circuitmux_t
*cmux
)
1855 chanid_circid_muxinfo_t
**i
= NULL
;
1858 tor_assert(cmux
->chanid_circid_map
);
1860 /* Start iterating the hash table */
1861 i
= HT_START(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
);
1863 /* Advance through each entry */
1865 /* Assert that it isn't null */
1869 * Assert that this entry is not marked - i.e., that either we didn't
1870 * think it should be active in pass one or we saw it in the active
1871 * circuits linked list.
1873 tor_assert(!((*i
)->muxinfo
.mark
));
1875 /* Advance to the next entry */
1876 i
= HT_NEXT(chanid_circid_muxinfo_map
, cmux
->chanid_circid_map
, i
);
1882 circuitmux_append_destroy_cell(channel_t
*chan
,
1888 memset(&cell
, 0, sizeof(cell_t
));
1889 cell
.circ_id
= circ_id
;
1890 cell
.command
= CELL_DESTROY
;
1891 cell
.payload
[0] = (uint8_t) reason
;
1893 cell_queue_append_packed_copy(NULL
, &cmux
->destroy_cell_queue
, 0, &cell
,
1894 chan
->wide_circ_ids
, 0);
1896 /* Destroy entering the queue, update counters */
1897 ++(cmux
->destroy_ctr
);
1898 ++global_destroy_ctr
;
1900 "Cmux at %p queued a destroy for circ %u, cmux counter is now "
1901 I64_FORMAT
", global counter is now "I64_FORMAT
,
1903 I64_PRINTF_ARG(cmux
->destroy_ctr
),
1904 I64_PRINTF_ARG(global_destroy_ctr
));
1906 /* XXXX Duplicate code from append_cell_to_circuit_queue */
1907 if (!channel_has_queued_writes(chan
)) {
1908 /* There is no data at all waiting to be sent on the outbuf. Add a
1909 * cell, so that we can notice when it gets flushed, flushed_some can
1910 * get called, and we can start putting more data onto the buffer then.
1912 log_debug(LD_GENERAL
, "Primed a buffer.");
1913 channel_flush_from_first_active_circuit(chan
, 1);
1917 /*DOCDOC; for debugging 12184. This runs slowly. */
1919 circuitmux_count_queued_destroy_cells(const channel_t
*chan
,
1920 const circuitmux_t
*cmux
)
1922 int64_t n_destroy_cells
= cmux
->destroy_ctr
;
1923 int64_t destroy_queue_size
= cmux
->destroy_cell_queue
.n
;
1925 int64_t manual_total
= 0;
1926 int64_t manual_total_in_map
= 0;
1927 packed_cell_t
*cell
;
1929 TOR_SIMPLEQ_FOREACH(cell
, &cmux
->destroy_cell_queue
.head
, next
) {
1933 id
= packed_cell_get_circid(cell
, chan
->wide_circ_ids
);
1934 if (circuit_id_in_use_on_channel(id
, (channel_t
*)chan
))
1935 ++manual_total_in_map
;
1938 if (n_destroy_cells
!= destroy_queue_size
||
1939 n_destroy_cells
!= manual_total
||
1940 n_destroy_cells
!= manual_total_in_map
) {
1941 log_warn(LD_BUG
, " Discrepancy in counts for queued destroy cells on "
1942 "circuitmux. n="I64_FORMAT
". queue_size="I64_FORMAT
". "
1943 "manual_total="I64_FORMAT
". manual_total_in_map="I64_FORMAT
".",
1944 I64_PRINTF_ARG(n_destroy_cells
),
1945 I64_PRINTF_ARG(destroy_queue_size
),
1946 I64_PRINTF_ARG(manual_total
),
1947 I64_PRINTF_ARG(manual_total_in_map
));
1950 return n_destroy_cells
;
1954 * Compare cmuxes to see which is more preferred; return < 0 if
1955 * cmux_1 has higher priority (i.e., cmux_1 < cmux_2 in the scheduler's
1956 * sort order), > 0 if cmux_2 has higher priority, or 0 if they are
1957 * equally preferred.
1959 * If the cmuxes have different cmux policies or the policy does not
1960 * support the cmp_cmux method, return 0.
1964 circuitmux_compare_muxes
, (circuitmux_t
*cmux_1
, circuitmux_t
*cmux_2
))
1966 const circuitmux_policy_t
*policy
;
1971 if (cmux_1
== cmux_2
) {
1972 /* Equivalent because they're the same cmux */
1976 if (cmux_1
->policy
&& cmux_2
->policy
) {
1977 if (cmux_1
->policy
== cmux_2
->policy
) {
1978 policy
= cmux_1
->policy
;
1980 if (policy
->cmp_cmux
) {
1981 /* Okay, we can compare! */
1982 return policy
->cmp_cmux(cmux_1
, cmux_1
->policy_data
,
1983 cmux_2
, cmux_2
->policy_data
);
1986 * Equivalent because the policy doesn't know how to compare between
1992 /* Equivalent because they have different policies */
1996 /* Equivalent because one or both are missing a policy */