tor  0.4.2.0-alpha-dev
circuitmux.c
Go to the documentation of this file.
1 /* * Copyright (c) 2012-2019, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 
72 #include "core/or/or.h"
73 #include "core/or/channel.h"
74 #include "core/or/circuitlist.h"
75 #include "core/or/circuitmux.h"
76 #include "core/or/relay.h"
77 
78 #include "core/or/cell_queue_st.h"
79 #include "core/or/destroy_cell_queue_st.h"
80 #include "core/or/or_circuit_st.h"
81 
82 /*
83  * Private typedefs for circuitmux.c
84  */
85 
86 /*
87  * Map of muxinfos for circuitmux_t to use; struct is defined below (name
88  * of struct must match HT_HEAD line).
89  */
90 typedef struct chanid_circid_muxinfo_map chanid_circid_muxinfo_map_t;
91 
92 /*
93  * Hash table entry (yeah, calling it chanid_circid_muxinfo_s seems to
94  * break the hash table code).
95  */
97 
98 /*
99  * Anything the mux wants to store per-circuit in the map; right now just
100  * a count of queued cells.
101  */
102 
103 typedef struct circuit_muxinfo_s circuit_muxinfo_t;
104 
105 /*
106  * Structures for circuitmux.c
107  */
108 
109 struct circuitmux_s {
110  /* Keep count of attached, active circuits */
111  unsigned int n_circuits, n_active_circuits;
112 
113  /* Total number of queued cells on all circuits */
114  unsigned int n_cells;
115 
116  /*
117  * Map from (channel ID, circuit ID) pairs to circuit_muxinfo_t
118  */
119  chanid_circid_muxinfo_map_t *chanid_circid_map;
120 
131  unsigned int last_cell_was_destroy : 1;
135  int64_t destroy_ctr;
136 
137  /*
138  * Circuitmux policy; if this is non-NULL, it can override the built-
139  * in round-robin active circuits behavior. This is how EWMA works in
140  * the new circuitmux_t world.
141  */
142  const circuitmux_policy_t *policy;
143 
144  /* Policy-specific data */
145  circuitmux_policy_data_t *policy_data;
146 };
147 
148 /*
149  * This struct holds whatever we want to store per attached circuit on a
150  * circuitmux_t; right now, just the count of queued cells and the direction.
151  */
152 
154  /* Count of cells on this circuit at last update */
155  unsigned int cell_count;
156  /* Direction of flow */
157  cell_direction_t direction;
158  /* Policy-specific data */
159  circuitmux_policy_circ_data_t *policy_data;
160  /* Mark bit for consistency checker */
161  unsigned int mark:1;
162 };
163 
164 /*
165  * A map from channel ID and circuit ID to a circuit_muxinfo_t for that
166  * circuit.
167  */
168 
170  HT_ENTRY(chanid_circid_muxinfo_t) node;
171  uint64_t chan_id;
172  circid_t circ_id;
173  circuit_muxinfo_t muxinfo;
174 };
175 
176 /*
177  * Static function declarations
178  */
179 
180 static inline int
183 static inline unsigned int
187 static void
189 static void
191 
192 /* Static global variables */
193 
195 static int64_t global_destroy_ctr = 0;
196 
197 /* Function definitions */
198 
205 static inline int
208 {
209  return a->chan_id == b->chan_id && a->circ_id == b->circ_id;
210 }
211 
216 static inline unsigned int
218 {
219  return (((unsigned int)(a->circ_id) << 8) ^
220  ((unsigned int)((a->chan_id >> 32) & 0xffffffff)) ^
221  ((unsigned int)(a->chan_id & 0xffffffff)));
222 }
223 
224 /* Declare the struct chanid_circid_muxinfo_map type */
225 HT_HEAD(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t);
226 
227 /* Emit a bunch of hash table stuff */
228 HT_PROTOTYPE(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t, node,
230 HT_GENERATE2(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t, node,
233 
234 /*
235  * Circuitmux alloc/free functions
236  */
237 
238 
242 circuitmux_t *
243 circuitmux_alloc(void)
244 {
245  circuitmux_t *rv = NULL;
246 
247  rv = tor_malloc_zero(sizeof(*rv));
248  rv->chanid_circid_map = tor_malloc_zero(sizeof(*( rv->chanid_circid_map)));
249  HT_INIT(chanid_circid_muxinfo_map, rv->chanid_circid_map);
251 
252  return rv;
253 }
254 
262 void
264 {
265  chanid_circid_muxinfo_t **i = NULL, *to_remove;
266  channel_t *chan = NULL;
267  circuit_t *circ = NULL;
268 
269  tor_assert(cmux);
270 
271  i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
272  while (i) {
273  to_remove = *i;
274 
275  if (! to_remove) {
276  log_warn(LD_BUG, "Somehow, an HT iterator gave us a NULL pointer.");
277  break;
278  } else {
279  /* Find a channel and circuit */
280  chan = channel_find_by_global_id(to_remove->chan_id);
281  if (chan) {
282  circ =
284  chan);
285  if (circ) {
286  /* Clear the circuit's mux for this direction */
287  if (to_remove->muxinfo.direction == CELL_DIRECTION_OUT) {
288  /*
289  * Update active_circuits et al.; this does policy notifies, so
290  * comes before freeing policy data
291  */
292 
293  if (to_remove->muxinfo.cell_count > 0) {
295  }
296 
297  if (detached_out)
298  smartlist_add(detached_out, circ);
299  } else if (circ->magic == OR_CIRCUIT_MAGIC) {
300  /*
301  * Update active_circuits et al.; this does policy notifies, so
302  * comes before freeing policy data
303  */
304 
305  if (to_remove->muxinfo.cell_count > 0) {
307  }
308 
309  if (detached_out)
310  smartlist_add(detached_out, circ);
311  } else {
312  /* Complain and move on */
313  log_warn(LD_CIRC,
314  "Circuit %u/channel %"PRIu64 " had direction == "
315  "CELL_DIRECTION_IN, but isn't an or_circuit_t",
316  (unsigned)to_remove->circ_id,
317  (to_remove->chan_id));
318  }
319 
320  /* Free policy-specific data if we have it */
321  if (to_remove->muxinfo.policy_data) {
322  /*
323  * If we have policy data, assert that we have the means to
324  * free it
325  */
326  tor_assert(cmux->policy);
327  tor_assert(cmux->policy->free_circ_data);
328  /* Call free_circ_data() */
329  cmux->policy->free_circ_data(cmux,
330  cmux->policy_data,
331  circ,
332  to_remove->muxinfo.policy_data);
333  to_remove->muxinfo.policy_data = NULL;
334  }
335  } else {
336  /* Complain and move on */
337  log_warn(LD_CIRC,
338  "Couldn't find circuit %u (for channel %"PRIu64 ")",
339  (unsigned)to_remove->circ_id,
340  (to_remove->chan_id));
341  }
342  } else {
343  /* Complain and move on */
344  log_warn(LD_CIRC,
345  "Couldn't find channel %"PRIu64 " (for circuit id %u)",
346  (to_remove->chan_id),
347  (unsigned)to_remove->circ_id);
348  }
349 
350  /* Assert that we don't have un-freed policy data for this circuit */
351  tor_assert(to_remove->muxinfo.policy_data == NULL);
352  }
353 
354  i = HT_NEXT_RMV(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
355 
356  /* Free it */
357  tor_free(to_remove);
358  }
359 
360  cmux->n_circuits = 0;
361  cmux->n_active_circuits = 0;
362  cmux->n_cells = 0;
363 }
364 
372 void
374 {
375  destroy_cell_t *cell;
376  TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
377  channel_mark_circid_usable(chan, cell->circid);
378  }
379 }
380 
386 void
388 {
389  if (!cmux) return;
390 
391  tor_assert(cmux->n_circuits == 0);
392  tor_assert(cmux->n_active_circuits == 0);
393 
394  /*
395  * Free policy-specific data if we have any; we don't
396  * need to do circuitmux_set_policy(cmux, NULL) to cover
397  * the circuits because they would have been handled in
398  * circuitmux_detach_all_circuits() before this was
399  * called.
400  */
401  if (cmux->policy && cmux->policy->free_cmux_data) {
402  if (cmux->policy_data) {
403  cmux->policy->free_cmux_data(cmux, cmux->policy_data);
404  cmux->policy_data = NULL;
405  }
406  } else tor_assert(cmux->policy_data == NULL);
407 
408  if (cmux->chanid_circid_map) {
409  HT_CLEAR(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
410  tor_free(cmux->chanid_circid_map);
411  }
412 
413  /*
414  * We're throwing away some destroys; log the counter and
415  * adjust the global counter by the queue size.
416  */
417  if (cmux->destroy_cell_queue.n > 0) {
418  cmux->destroy_ctr -= cmux->destroy_cell_queue.n;
420  log_debug(LD_CIRC,
421  "Freeing cmux at %p with %u queued destroys; the last cmux "
422  "destroy balance was %"PRId64", global is %"PRId64,
423  cmux, cmux->destroy_cell_queue.n,
424  (cmux->destroy_ctr),
426  } else {
427  log_debug(LD_CIRC,
428  "Freeing cmux at %p with no queued destroys, the cmux destroy "
429  "balance was %"PRId64", global is %"PRId64,
430  cmux,
431  (cmux->destroy_ctr),
433  }
434 
436 
437  tor_free(cmux);
438 }
439 
440 /*
441  * Circuitmux policy control functions
442  */
443 
450 void
452 {
453  tor_assert(cmux);
454 
455  /* Internally, this is just setting policy to NULL */
456  circuitmux_set_policy(cmux, NULL);
457 }
458 
464 circuitmux_get_policy, (circuitmux_t *cmux))
465 {
466  tor_assert(cmux);
467 
468  return cmux->policy;
469 }
470 
476 void
478  const circuitmux_policy_t *pol)
479 {
480  const circuitmux_policy_t *old_pol = NULL, *new_pol = NULL;
481  circuitmux_policy_data_t *old_pol_data = NULL, *new_pol_data = NULL;
482  chanid_circid_muxinfo_t **i = NULL;
483  channel_t *chan = NULL;
484  uint64_t last_chan_id_searched = 0;
485  circuit_t *circ = NULL;
486 
487  tor_assert(cmux);
488 
489  /* Set up variables */
490  old_pol = cmux->policy;
491  old_pol_data = cmux->policy_data;
492  new_pol = pol;
493 
494  /* Check if this is the trivial case */
495  if (old_pol == new_pol) return;
496 
497  /* Allocate data for new policy, if any */
498  if (new_pol && new_pol->alloc_cmux_data) {
499  /*
500  * If alloc_cmux_data is not null, then we expect to get some policy
501  * data. Assert that we also have free_cmux_data so we can free it
502  * when the time comes, and allocate it.
503  */
504  tor_assert(new_pol->free_cmux_data);
505  new_pol_data = new_pol->alloc_cmux_data(cmux);
506  tor_assert(new_pol_data);
507  }
508 
509  /* Install new policy and new policy data on cmux */
510  cmux->policy = new_pol;
511  cmux->policy_data = new_pol_data;
512 
513  /* Iterate over all circuits, attaching/detaching each one */
514  i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
515  while (i) {
516  /* Assert that this entry isn't NULL */
517  tor_assert(*i);
518 
519  /*
520  * Get the channel; since normal case is all circuits on the mux share a
521  * channel, we cache last_chan_id_searched
522  */
523  if (!chan || last_chan_id_searched != (*i)->chan_id) {
524  chan = channel_find_by_global_id((*i)->chan_id);
525  last_chan_id_searched = (*i)->chan_id;
526  }
527  tor_assert(chan);
528 
529  /* Get the circuit */
530  circ = circuit_get_by_circid_channel_even_if_marked((*i)->circ_id, chan);
531  tor_assert(circ);
532 
533  /* Need to tell old policy it becomes inactive (i.e., it is active) ? */
534  if (old_pol && old_pol->notify_circ_inactive &&
535  (*i)->muxinfo.cell_count > 0) {
536  old_pol->notify_circ_inactive(cmux, old_pol_data, circ,
537  (*i)->muxinfo.policy_data);
538  }
539 
540  /* Need to free old policy data? */
541  if ((*i)->muxinfo.policy_data) {
542  /* Assert that we have the means to free it if we have policy data */
543  tor_assert(old_pol);
544  tor_assert(old_pol->free_circ_data);
545  /* Free it */
546  old_pol->free_circ_data(cmux, old_pol_data, circ,
547  (*i)->muxinfo.policy_data);
548  (*i)->muxinfo.policy_data = NULL;
549  }
550 
551  /* Need to allocate new policy data? */
552  if (new_pol && new_pol->alloc_circ_data) {
553  /*
554  * If alloc_circ_data is not null, we expect to get some per-circuit
555  * policy data. Assert that we also have free_circ_data so we can
556  * free it when the time comes, and allocate it.
557  */
558  tor_assert(new_pol->free_circ_data);
559  (*i)->muxinfo.policy_data =
560  new_pol->alloc_circ_data(cmux, new_pol_data, circ,
561  (*i)->muxinfo.direction,
562  (*i)->muxinfo.cell_count);
563  }
564 
565  /* Need to make active on new policy? */
566  if (new_pol && new_pol->notify_circ_active &&
567  (*i)->muxinfo.cell_count > 0) {
568  new_pol->notify_circ_active(cmux, new_pol_data, circ,
569  (*i)->muxinfo.policy_data);
570  }
571 
572  /* Advance to next circuit map entry */
573  i = HT_NEXT(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
574  }
575 
576  /* Free data for old policy, if any */
577  if (old_pol_data) {
578  /*
579  * If we had old policy data, we should have an old policy and a free
580  * function for it.
581  */
582  tor_assert(old_pol);
583  tor_assert(old_pol->free_cmux_data);
584  old_pol->free_cmux_data(cmux, old_pol_data);
585  old_pol_data = NULL;
586  }
587 }
588 
589 /*
590  * Circuitmux/circuit attachment status inquiry functions
591  */
592 
599 {
600  chanid_circid_muxinfo_t *hashent = NULL;
601 
602  /* Try to find a map entry */
603  hashent = circuitmux_find_map_entry(cmux, circ);
604 
605  /*
606  * This function should only be called on attached circuits; assert that
607  * we had a map entry.
608  */
609  tor_assert(hashent);
610 
611  /* Return the direction from the map entry */
612  return hashent->muxinfo.direction;
613 }
614 
622 {
623  chanid_circid_muxinfo_t search, *hashent = NULL;
624 
625  /* Sanity-check parameters */
626  tor_assert(cmux);
627  tor_assert(cmux->chanid_circid_map);
628  tor_assert(circ);
629 
630  /* Check if we have n_chan */
631  if (circ->n_chan) {
632  /* Okay, let's see if it's attached for n_chan/n_circ_id */
633  search.chan_id = circ->n_chan->global_identifier;
634  search.circ_id = circ->n_circ_id;
635 
636  /* Query */
637  hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
638  &search);
639  }
640 
641  /* Found something? */
642  if (hashent) {
643  /*
644  * Assert that the direction makes sense for a hashent we found by
645  * n_chan/n_circ_id before we return it.
646  */
647  tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_OUT);
648  } else {
649  /* Not there, have we got a p_chan/p_circ_id to try? */
650  if (circ->magic == OR_CIRCUIT_MAGIC) {
651  search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
652  /* Check for p_chan */
653  if (TO_OR_CIRCUIT(circ)->p_chan) {
654  search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
655  /* Okay, search for that */
656  hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
657  &search);
658  /* Find anything? */
659  if (hashent) {
660  /* Assert that the direction makes sense before we return it */
661  tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_IN);
662  }
663  }
664  }
665  }
666 
667  /* Okay, hashent is it if it was there */
668  return hashent;
669 }
670 
675 int
677 {
678  chanid_circid_muxinfo_t *hashent = NULL;
679 
680  /* Look if it's in the circuit map */
681  hashent = circuitmux_find_map_entry(cmux, circ);
682 
683  return (hashent != NULL);
684 }
685 
690 int
692 {
693  chanid_circid_muxinfo_t *hashent = NULL;
694  int is_active = 0;
695 
696  tor_assert(cmux);
697  tor_assert(circ);
698 
699  /* Look if it's in the circuit map */
700  hashent = circuitmux_find_map_entry(cmux, circ);
701  if (hashent) {
702  /* Check the number of cells on this circuit */
703  is_active = (hashent->muxinfo.cell_count > 0);
704  }
705  /* else not attached, so not active */
706 
707  return is_active;
708 }
709 
714 unsigned int
716 {
717  chanid_circid_muxinfo_t *hashent = NULL;
718  unsigned int n_cells = 0;
719 
720  tor_assert(cmux);
721  tor_assert(circ);
722 
723  /* Look if it's in the circuit map */
724  hashent = circuitmux_find_map_entry(cmux, circ);
725  if (hashent) {
726  /* Just get the cell count for this circuit */
727  n_cells = hashent->muxinfo.cell_count;
728  }
729  /* else not attached, so 0 cells */
730 
731  return n_cells;
732 }
733 
738 MOCK_IMPL(unsigned int,
739 circuitmux_num_cells, (circuitmux_t *cmux))
740 {
741  tor_assert(cmux);
742 
743  return cmux->n_cells + cmux->destroy_cell_queue.n;
744 }
745 
750 unsigned int
752 {
753  tor_assert(cmux);
754 
755  return cmux->n_active_circuits;
756 }
757 
762 unsigned int
764 {
765  tor_assert(cmux);
766 
767  return cmux->n_circuits;
768 }
769 
770 /*
771  * Functions for circuit code to call to update circuit status
772  */
773 
779 circuitmux_attach_circuit,(circuitmux_t *cmux, circuit_t *circ,
780  cell_direction_t direction))
781 {
782  channel_t *chan = NULL;
783  uint64_t channel_id;
784  circid_t circ_id;
785  chanid_circid_muxinfo_t search, *hashent = NULL;
786  unsigned int cell_count;
787 
788  tor_assert(cmux);
789  tor_assert(circ);
790  tor_assert(direction == CELL_DIRECTION_IN ||
791  direction == CELL_DIRECTION_OUT);
792 
793  /*
794  * Figure out which channel we're using, and get the circuit's current
795  * cell count and circuit ID; assert that the circuit is not already
796  * attached to another mux.
797  */
798  if (direction == CELL_DIRECTION_OUT) {
799  /* It's n_chan */
800  chan = circ->n_chan;
801  cell_count = circ->n_chan_cells.n;
802  circ_id = circ->n_circ_id;
803  } else {
804  /* We want p_chan */
805  chan = TO_OR_CIRCUIT(circ)->p_chan;
806  cell_count = TO_OR_CIRCUIT(circ)->p_chan_cells.n;
807  circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
808  }
809  /* Assert that we did get a channel */
810  tor_assert(chan);
811  /* Assert that the circuit ID is sensible */
812  tor_assert(circ_id != 0);
813 
814  /* Get the channel ID */
815  channel_id = chan->global_identifier;
816 
817  /* See if we already have this one */
818  search.chan_id = channel_id;
819  search.circ_id = circ_id;
820  hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
821  &search);
822 
823  if (hashent) {
824  /*
825  * This circuit was already attached to this cmux; make sure the
826  * directions match and update the cell count and active circuit count.
827  */
828  log_info(LD_CIRC,
829  "Circuit %u on channel %"PRIu64 " was already attached to "
830  "(trying to attach to %p)",
831  (unsigned)circ_id, (channel_id),
832  cmux);
833 
834  /*
835  * The mux pointer on this circuit and the direction in result should
836  * match; otherwise assert.
837  */
838  tor_assert(hashent->muxinfo.direction == direction);
839 
840  /*
841  * Looks okay; just update the cell count and active circuits if we must
842  */
843  if (hashent->muxinfo.cell_count > 0 && cell_count == 0) {
844  --(cmux->n_active_circuits);
846  } else if (hashent->muxinfo.cell_count == 0 && cell_count > 0) {
847  ++(cmux->n_active_circuits);
848  circuitmux_make_circuit_active(cmux, circ);
849  }
850  cmux->n_cells -= hashent->muxinfo.cell_count;
851  cmux->n_cells += cell_count;
852  hashent->muxinfo.cell_count = cell_count;
853  } else {
854  /*
855  * New circuit; add an entry and update the circuit/active circuit
856  * counts.
857  */
858  log_debug(LD_CIRC,
859  "Attaching circuit %u on channel %"PRIu64 " to cmux %p",
860  (unsigned)circ_id, (channel_id), cmux);
861 
862  /* Insert it in the map */
863  hashent = tor_malloc_zero(sizeof(*hashent));
864  hashent->chan_id = channel_id;
865  hashent->circ_id = circ_id;
866  hashent->muxinfo.cell_count = cell_count;
867  hashent->muxinfo.direction = direction;
868  /* Allocate policy specific circuit data if we need it */
869  if (cmux->policy->alloc_circ_data) {
870  /* Assert that we have the means to free policy-specific data */
871  tor_assert(cmux->policy->free_circ_data);
872  /* Allocate it */
873  hashent->muxinfo.policy_data =
874  cmux->policy->alloc_circ_data(cmux,
875  cmux->policy_data,
876  circ,
877  direction,
878  cell_count);
879  /* If we wanted policy data, it's an error not to get any */
880  tor_assert(hashent->muxinfo.policy_data);
881  }
882  HT_INSERT(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
883  hashent);
884 
885  /* Update counters */
886  ++(cmux->n_circuits);
887  if (cell_count > 0) {
888  ++(cmux->n_active_circuits);
889  circuitmux_make_circuit_active(cmux, circ);
890  }
891  cmux->n_cells += cell_count;
892  }
893 }
894 
901 circuitmux_detach_circuit,(circuitmux_t *cmux, circuit_t *circ))
902 {
903  chanid_circid_muxinfo_t search, *hashent = NULL;
904  /*
905  * Use this to keep track of whether we found it for n_chan or
906  * p_chan for consistency checking.
907  *
908  * The 0 initializer is not a valid cell_direction_t value.
909  * We assert that it has been replaced with a valid value before it is used.
910  */
911  cell_direction_t last_searched_direction = 0;
912 
913  tor_assert(cmux);
914  tor_assert(cmux->chanid_circid_map);
915  tor_assert(circ);
916 
917  /* See if we have it for n_chan/n_circ_id */
918  if (circ->n_chan) {
919  search.chan_id = circ->n_chan->global_identifier;
920  search.circ_id = circ->n_circ_id;
921  hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
922  &search);
923  last_searched_direction = CELL_DIRECTION_OUT;
924  }
925 
926  /* Got one? If not, see if it's an or_circuit_t and try p_chan/p_circ_id */
927  if (!hashent) {
928  if (circ->magic == OR_CIRCUIT_MAGIC) {
929  search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
930  if (TO_OR_CIRCUIT(circ)->p_chan) {
931  search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
932  hashent = HT_FIND(chanid_circid_muxinfo_map,
933  cmux->chanid_circid_map,
934  &search);
935  last_searched_direction = CELL_DIRECTION_IN;
936  }
937  }
938  }
939 
940  tor_assert(last_searched_direction == CELL_DIRECTION_OUT
941  || last_searched_direction == CELL_DIRECTION_IN);
942 
943  /*
944  * If hashent isn't NULL, we have a circuit to detach; don't remove it from
945  * the map until later of circuitmux_make_circuit_inactive() breaks.
946  */
947  if (hashent) {
948  /* Update counters */
949  --(cmux->n_circuits);
950  if (hashent->muxinfo.cell_count > 0) {
951  --(cmux->n_active_circuits);
952  /* This does policy notifies, so comes before freeing policy data */
954  }
955  cmux->n_cells -= hashent->muxinfo.cell_count;
956 
957  /* Free policy-specific data if we have it */
958  if (hashent->muxinfo.policy_data) {
959  /* If we have policy data, assert that we have the means to free it */
960  tor_assert(cmux->policy);
961  tor_assert(cmux->policy->free_circ_data);
962  /* Call free_circ_data() */
963  cmux->policy->free_circ_data(cmux,
964  cmux->policy_data,
965  circ,
966  hashent->muxinfo.policy_data);
967  hashent->muxinfo.policy_data = NULL;
968  }
969 
970  /* Consistency check: the direction must match the direction searched */
971  tor_assert(last_searched_direction == hashent->muxinfo.direction);
972 
973  /* Now remove it from the map */
974  HT_REMOVE(chanid_circid_muxinfo_map, cmux->chanid_circid_map, hashent);
975 
976  /* Free the hash entry */
977  tor_free(hashent);
978  }
979 }
980 
986 static void
988 {
989  tor_assert(cmux);
990  tor_assert(cmux->policy);
991  tor_assert(circ);
992 
993  /* Policy-specific notification */
994  if (cmux->policy->notify_circ_active) {
995  /* Okay, we need to check the circuit for policy data now */
996  chanid_circid_muxinfo_t *hashent = circuitmux_find_map_entry(cmux, circ);
997  /* We should have found something */
998  tor_assert(hashent);
999  /* Notify */
1000  cmux->policy->notify_circ_active(cmux, cmux->policy_data,
1001  circ, hashent->muxinfo.policy_data);
1002  }
1003 }
1004 
1010 static void
1012 {
1013  tor_assert(cmux);
1014  tor_assert(cmux->policy);
1015  tor_assert(circ);
1016 
1017  /* Policy-specific notification */
1018  if (cmux->policy->notify_circ_inactive) {
1019  /* Okay, we need to check the circuit for policy data now */
1020  chanid_circid_muxinfo_t *hashent = circuitmux_find_map_entry(cmux, circ);
1021  /* We should have found something */
1022  tor_assert(hashent);
1023  /* Notify */
1024  cmux->policy->notify_circ_inactive(cmux, cmux->policy_data,
1025  circ, hashent->muxinfo.policy_data);
1026  }
1027 }
1028 
1033 void
1035 {
1036  /* This is the same as setting the cell count to zero */
1037  circuitmux_set_num_cells(cmux, circ, 0);
1038 }
1039 
1044 void
1046  unsigned int n_cells)
1047 {
1048  chanid_circid_muxinfo_t *hashent = NULL;
1049 
1050  tor_assert(cmux);
1051  tor_assert(circ);
1052 
1053  /* Search for this circuit's entry */
1054  hashent = circuitmux_find_map_entry(cmux, circ);
1055  /* Assert that we found one */
1056  tor_assert(hashent);
1057 
1058  /* Update cmux cell counter */
1059  cmux->n_cells -= hashent->muxinfo.cell_count;
1060  cmux->n_cells += n_cells;
1061 
1062  /* Do we need to notify a cmux policy? */
1063  if (cmux->policy->notify_set_n_cells) {
1064  /* Call notify_set_n_cells */
1065  cmux->policy->notify_set_n_cells(cmux,
1066  cmux->policy_data,
1067  circ,
1068  hashent->muxinfo.policy_data,
1069  n_cells);
1070  }
1071 
1072  /*
1073  * Update cmux active circuit counter: is the old cell count > 0 and the
1074  * new cell count == 0 ?
1075  */
1076  if (hashent->muxinfo.cell_count > 0 && n_cells == 0) {
1077  --(cmux->n_active_circuits);
1078  hashent->muxinfo.cell_count = n_cells;
1080  /* Is the old cell count == 0 and the new cell count > 0 ? */
1081  } else if (hashent->muxinfo.cell_count == 0 && n_cells > 0) {
1082  ++(cmux->n_active_circuits);
1083  hashent->muxinfo.cell_count = n_cells;
1084  circuitmux_make_circuit_active(cmux, circ);
1085  } else {
1086  hashent->muxinfo.cell_count = n_cells;
1087  }
1088 }
1089 
1090 /*
1091  * Functions for channel code to call to get a circuit to transmit from or
1092  * notify that cells have been transmitted.
1093  */
1094 
1106 circuit_t *
1108  destroy_cell_queue_t **destroy_queue_out)
1109 {
1110  circuit_t *circ = NULL;
1111 
1112  tor_assert(cmux);
1113  tor_assert(cmux->policy);
1114  /* This callback is mandatory. */
1115  tor_assert(cmux->policy->pick_active_circuit);
1116  tor_assert(destroy_queue_out);
1117 
1118  *destroy_queue_out = NULL;
1119 
1120  if (cmux->destroy_cell_queue.n &&
1121  (!cmux->last_cell_was_destroy || cmux->n_active_circuits == 0)) {
1122  /* We have destroy cells to send, and either we just sent a relay cell,
1123  * or we have no relay cells to send. */
1124 
1125  /* XXXX We should let the cmux policy have some say in this eventually. */
1126  /* XXXX Alternating is not a terribly brilliant approach here. */
1127  *destroy_queue_out = &cmux->destroy_cell_queue;
1128 
1129  cmux->last_cell_was_destroy = 1;
1130  } else if (cmux->n_active_circuits > 0) {
1131  /* We also must have a cell available for this to be the case */
1132  tor_assert(cmux->n_cells > 0);
1133  /* Do we have a policy-provided circuit selector? */
1134  circ = cmux->policy->pick_active_circuit(cmux, cmux->policy_data);
1135  cmux->last_cell_was_destroy = 0;
1136  } else {
1137  tor_assert(cmux->n_cells == 0);
1138  tor_assert(cmux->destroy_cell_queue.n == 0);
1139  }
1140 
1141  return circ;
1142 }
1143 
1149 void
1151  unsigned int n_cells)
1152 {
1153  chanid_circid_muxinfo_t *hashent = NULL;
1154  int becomes_inactive = 0;
1155 
1156  tor_assert(cmux);
1157  tor_assert(circ);
1158 
1159  if (n_cells == 0) return;
1160 
1161  /*
1162  * To handle this, we have to:
1163  *
1164  * 1.) Adjust the circuit's cell counter in the cmux hash table
1165  * 2.) Move the circuit to the tail of the active_circuits linked list
1166  * for this cmux, or make the circuit inactive if the cell count
1167  * went to zero.
1168  * 3.) Call cmux->policy->notify_xmit_cells(), if any
1169  */
1170 
1171  /* Find the hash entry */
1172  hashent = circuitmux_find_map_entry(cmux, circ);
1173  /* Assert that we found one */
1174  tor_assert(hashent);
1175 
1176  /* Adjust the cell counter and assert that we had that many cells to send */
1177  tor_assert(n_cells <= hashent->muxinfo.cell_count);
1178  hashent->muxinfo.cell_count -= n_cells;
1179  /* Do we need to make the circuit inactive? */
1180  if (hashent->muxinfo.cell_count == 0) becomes_inactive = 1;
1181  /* Adjust the mux cell counter */
1182  cmux->n_cells -= n_cells;
1183 
1184  /*
1185  * We call notify_xmit_cells() before making the circuit inactive if needed,
1186  * so the policy can always count on this coming in on an active circuit.
1187  */
1188  if (cmux->policy->notify_xmit_cells) {
1189  cmux->policy->notify_xmit_cells(cmux, cmux->policy_data, circ,
1190  hashent->muxinfo.policy_data,
1191  n_cells);
1192  }
1193 
1194  /*
1195  * Now make the circuit inactive if needed; this will call the policy's
1196  * notify_circ_inactive() if present.
1197  */
1198  if (becomes_inactive) {
1199  --(cmux->n_active_circuits);
1201  }
1202 }
1203 
1209 void
1211 {
1212  tor_assert(cmux);
1213 
1214  --(cmux->destroy_ctr);
1215  --(global_destroy_ctr);
1216  log_debug(LD_CIRC,
1217  "Cmux at %p sent a destroy, cmux counter is now %"PRId64", "
1218  "global counter is now %"PRId64,
1219  cmux,
1220  (cmux->destroy_ctr),
1221  (global_destroy_ctr));
1222 }
1223 
1224 /*DOCDOC */
1225 void
1226 circuitmux_append_destroy_cell(channel_t *chan,
1227  circuitmux_t *cmux,
1228  circid_t circ_id,
1229  uint8_t reason)
1230 {
1231  destroy_cell_queue_append(&cmux->destroy_cell_queue, circ_id, reason);
1232 
1233  /* Destroy entering the queue, update counters */
1234  ++(cmux->destroy_ctr);
1236  log_debug(LD_CIRC,
1237  "Cmux at %p queued a destroy for circ %u, cmux counter is now "
1238  "%"PRId64", global counter is now %"PRId64,
1239  cmux, circ_id,
1240  (cmux->destroy_ctr),
1241  (global_destroy_ctr));
1242 
1243  /* XXXX Duplicate code from append_cell_to_circuit_queue */
1244  if (!channel_has_queued_writes(chan)) {
1245  /* There is no data at all waiting to be sent on the outbuf. Add a
1246  * cell, so that we can notice when it gets flushed, flushed_some can
1247  * get called, and we can start putting more data onto the buffer then.
1248  */
1249  log_debug(LD_GENERAL, "Primed a buffer.");
1250  channel_flush_from_first_active_circuit(chan, 1);
1251  }
1252 }
1253 
1254 /*DOCDOC; for debugging 12184. This runs slowly. */
1255 int64_t
1256 circuitmux_count_queued_destroy_cells(const channel_t *chan,
1257  const circuitmux_t *cmux)
1258 {
1259  int64_t n_destroy_cells = cmux->destroy_ctr;
1260  int64_t destroy_queue_size = cmux->destroy_cell_queue.n;
1261 
1262  int64_t manual_total = 0;
1263  int64_t manual_total_in_map = 0;
1264  destroy_cell_t *cell;
1265 
1266  TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
1267  circid_t id;
1268  ++manual_total;
1269 
1270  id = cell->circid;
1271  if (circuit_id_in_use_on_channel(id, (channel_t*)chan))
1272  ++manual_total_in_map;
1273  }
1274 
1275  if (n_destroy_cells != destroy_queue_size ||
1276  n_destroy_cells != manual_total ||
1277  n_destroy_cells != manual_total_in_map) {
1278  log_warn(LD_BUG, " Discrepancy in counts for queued destroy cells on "
1279  "circuitmux. n=%"PRId64". queue_size=%"PRId64". "
1280  "manual_total=%"PRId64". manual_total_in_map=%"PRId64".",
1281  (n_destroy_cells),
1282  (destroy_queue_size),
1283  (manual_total),
1284  (manual_total_in_map));
1285  }
1286 
1287  return n_destroy_cells;
1288 }
1289 
1301 circuitmux_compare_muxes, (circuitmux_t *cmux_1, circuitmux_t *cmux_2))
1302 {
1303  const circuitmux_policy_t *policy;
1304 
1305  tor_assert(cmux_1);
1306  tor_assert(cmux_2);
1307 
1308  if (cmux_1 == cmux_2) {
1309  /* Equivalent because they're the same cmux */
1310  return 0;
1311  }
1312 
1313  if (cmux_1->policy && cmux_2->policy) {
1314  if (cmux_1->policy == cmux_2->policy) {
1315  policy = cmux_1->policy;
1316 
1317  if (policy->cmp_cmux) {
1318  /* Okay, we can compare! */
1319  return policy->cmp_cmux(cmux_1, cmux_1->policy_data,
1320  cmux_2, cmux_2->policy_data);
1321  } else {
1322  /*
1323  * Equivalent because the policy doesn't know how to compare between
1324  * muxes.
1325  */
1326  return 0;
1327  }
1328  } else {
1329  /* Equivalent because they have different policies */
1330  return 0;
1331  }
1332  } else {
1333  /* Equivalent because one or both are missing a policy */
1334  return 0;
1335  }
1336 }
1337 
HT_PROTOTYPE(HT_GENERATE2(chanid_circid_muxinfo_map, HT_GENERATE2(chanid_circid_muxinfo_t, HT_GENERATE2(node, HT_GENERATE2(chanid_circid_entry_hash, HT_GENERATE2(chanid_circid_entries_eq)
Definition: circuitmux.c:228
void circuitmux_clear_num_cells(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:1034
circuit_t * circuit_get_by_circid_channel_even_if_marked(circid_t circ_id, channel_t *chan)
Definition: circuitlist.c:1526
static int chanid_circid_entries_eq(chanid_circid_muxinfo_t *a, chanid_circid_muxinfo_t *b)
Definition: circuitmux.c:206
#define LD_GENERAL
Definition: log.h:59
unsigned int circuitmux_num_cells_for_circuit(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:715
unsigned int last_cell_was_destroy
Definition: circuitmux.c:131
void smartlist_add(smartlist_t *sl, void *element)
int circuit_id_in_use_on_channel(circid_t circ_id, channel_t *chan)
Definition: circuitlist.c:1540
cell_direction_t circuitmux_attached_circuit_direction(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:598
static chanid_circid_muxinfo_t * circuitmux_find_map_entry(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:621
channel_t * channel_find_by_global_id(uint64_t global_identifier)
Definition: channel.c:650
void circuitmux_detach_all_circuits(circuitmux_t *cmux, smartlist_t *detached_out)
Definition: circuitmux.c:263
#define tor_free(p)
Definition: malloc.h:52
void circuitmux_free_(circuitmux_t *cmux)
Definition: circuitmux.c:387
void * tor_reallocarray_(void *ptr, size_t sz1, size_t sz2)
Definition: malloc.c:146
cell_queue_t n_chan_cells
Definition: circuit_st.h:70
cell_direction_t
Definition: or.h:482
channel_t * p_chan
Definition: or_circuit_st.h:35
void circuitmux_set_num_cells(circuitmux_t *cmux, circuit_t *circ, unsigned int n_cells)
Definition: circuitmux.c:1045
static void circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:987
void destroy_cell_queue_append(destroy_cell_queue_t *queue, circid_t circid, uint8_t reason)
Definition: relay.c:2623
Header file for channel.c.
tor_assert(buffer)
#define LD_CIRC
Definition: log.h:79
circid_t n_circ_id
Definition: circuit_st.h:67
void circuitmux_notify_xmit_destroy(circuitmux_t *cmux)
Definition: circuitmux.c:1210
static unsigned int chanid_circid_entry_hash(chanid_circid_muxinfo_t *a)
Definition: circuitmux.c:217
Master header file for Tor-specific functionality.
void destroy_cell_queue_clear(destroy_cell_queue_t *queue)
Definition: relay.c:2597
void circuitmux_notify_xmit_cells(circuitmux_t *cmux, circuit_t *circ, unsigned int n_cells)
Definition: circuitmux.c:1150
void circuitmux_set_policy(circuitmux_t *cmux, const circuitmux_policy_t *pol)
Definition: circuitmux.c:477
void channel_mark_circid_usable(channel_t *chan, circid_t id)
Definition: circuitlist.c:383
void tor_free_(void *mem)
Definition: malloc.c:227
circid_t p_circ_id
Definition: or_circuit_st.h:31
Header file for circuitlist.c.
int64_t destroy_ctr
Definition: circuitmux.c:135
void circuitmux_clear_policy(circuitmux_t *cmux)
Definition: circuitmux.c:451
cell_queue_t p_chan_cells
Definition: or_circuit_st.h:33
int circuitmux_is_circuit_active(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:691
Header file for relay.c.
Header file for circuitmux.c.
void circuitmux_mark_destroyed_circids_usable(circuitmux_t *cmux, channel_t *chan)
Definition: circuitmux.c:373
uint32_t circid_t
Definition: or.h:608
unsigned int circuitmux_num_circuits(circuitmux_t *cmux)
Definition: circuitmux.c:763
or_circuit_t * TO_OR_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:151
void destroy_cell_queue_init(destroy_cell_queue_t *queue)
Definition: relay.c:2589
int circuitmux_is_circuit_attached(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:676
uint32_t magic
Definition: circuit_st.h:54
circuit_t * circuitmux_get_first_active_circuit(circuitmux_t *cmux, destroy_cell_queue_t **destroy_queue_out)
Definition: circuitmux.c:1107
MOCK_IMPL(const circuitmux_policy_t *, circuitmux_get_policy,(circuitmux_t *cmux))
Definition: circuitmux.c:463
unsigned int circuitmux_num_active_circuits(circuitmux_t *cmux)
Definition: circuitmux.c:751
static void circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:1011
int channel_has_queued_writes(channel_t *chan)
Definition: channel.c:2880
static int64_t global_destroy_ctr
Definition: circuitmux.c:195
#define LD_BUG
Definition: log.h:83
destroy_cell_queue_t destroy_cell_queue
Definition: circuitmux.c:122
channel_t * n_chan
Definition: circuit_st.h:58
uint64_t global_identifier
Definition: channel.h:197