tor  0.4.0.0-alpha-dev
circuitmux.c
Go to the documentation of this file.
1 /* * Copyright (c) 2012-2018, 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  /* Clear n_mux */
298  circ->n_mux = NULL;
299 
300  if (detached_out)
301  smartlist_add(detached_out, circ);
302  } else if (circ->magic == OR_CIRCUIT_MAGIC) {
303  /*
304  * Update active_circuits et al.; this does policy notifies, so
305  * comes before freeing policy data
306  */
307 
308  if (to_remove->muxinfo.cell_count > 0) {
310  }
311 
312  /*
313  * It has a sensible p_chan and direction == CELL_DIRECTION_IN,
314  * so clear p_mux.
315  */
316  TO_OR_CIRCUIT(circ)->p_mux = NULL;
317 
318  if (detached_out)
319  smartlist_add(detached_out, circ);
320  } else {
321  /* Complain and move on */
322  log_warn(LD_CIRC,
323  "Circuit %u/channel %"PRIu64 " had direction == "
324  "CELL_DIRECTION_IN, but isn't an or_circuit_t",
325  (unsigned)to_remove->circ_id,
326  (to_remove->chan_id));
327  }
328 
329  /* Free policy-specific data if we have it */
330  if (to_remove->muxinfo.policy_data) {
331  /*
332  * If we have policy data, assert that we have the means to
333  * free it
334  */
335  tor_assert(cmux->policy);
336  tor_assert(cmux->policy->free_circ_data);
337  /* Call free_circ_data() */
338  cmux->policy->free_circ_data(cmux,
339  cmux->policy_data,
340  circ,
341  to_remove->muxinfo.policy_data);
342  to_remove->muxinfo.policy_data = NULL;
343  }
344  } else {
345  /* Complain and move on */
346  log_warn(LD_CIRC,
347  "Couldn't find circuit %u (for channel %"PRIu64 ")",
348  (unsigned)to_remove->circ_id,
349  (to_remove->chan_id));
350  }
351  } else {
352  /* Complain and move on */
353  log_warn(LD_CIRC,
354  "Couldn't find channel %"PRIu64 " (for circuit id %u)",
355  (to_remove->chan_id),
356  (unsigned)to_remove->circ_id);
357  }
358 
359  /* Assert that we don't have un-freed policy data for this circuit */
360  tor_assert(to_remove->muxinfo.policy_data == NULL);
361  }
362 
363  i = HT_NEXT_RMV(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
364 
365  /* Free it */
366  tor_free(to_remove);
367  }
368 
369  cmux->n_circuits = 0;
370  cmux->n_active_circuits = 0;
371  cmux->n_cells = 0;
372 }
373 
381 void
383 {
384  destroy_cell_t *cell;
385  TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
386  channel_mark_circid_usable(chan, cell->circid);
387  }
388 }
389 
395 void
397 {
398  if (!cmux) return;
399 
400  tor_assert(cmux->n_circuits == 0);
401  tor_assert(cmux->n_active_circuits == 0);
402 
403  /*
404  * Free policy-specific data if we have any; we don't
405  * need to do circuitmux_set_policy(cmux, NULL) to cover
406  * the circuits because they would have been handled in
407  * circuitmux_detach_all_circuits() before this was
408  * called.
409  */
410  if (cmux->policy && cmux->policy->free_cmux_data) {
411  if (cmux->policy_data) {
412  cmux->policy->free_cmux_data(cmux, cmux->policy_data);
413  cmux->policy_data = NULL;
414  }
415  } else tor_assert(cmux->policy_data == NULL);
416 
417  if (cmux->chanid_circid_map) {
418  HT_CLEAR(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
419  tor_free(cmux->chanid_circid_map);
420  }
421 
422  /*
423  * We're throwing away some destroys; log the counter and
424  * adjust the global counter by the queue size.
425  */
426  if (cmux->destroy_cell_queue.n > 0) {
427  cmux->destroy_ctr -= cmux->destroy_cell_queue.n;
429  log_debug(LD_CIRC,
430  "Freeing cmux at %p with %u queued destroys; the last cmux "
431  "destroy balance was %"PRId64", global is %"PRId64,
432  cmux, cmux->destroy_cell_queue.n,
433  (cmux->destroy_ctr),
435  } else {
436  log_debug(LD_CIRC,
437  "Freeing cmux at %p with no queued destroys, the cmux destroy "
438  "balance was %"PRId64", global is %"PRId64,
439  cmux,
440  (cmux->destroy_ctr),
442  }
443 
445 
446  tor_free(cmux);
447 }
448 
449 /*
450  * Circuitmux policy control functions
451  */
452 
459 void
461 {
462  tor_assert(cmux);
463 
464  /* Internally, this is just setting policy to NULL */
465  circuitmux_set_policy(cmux, NULL);
466 }
467 
473 circuitmux_get_policy, (circuitmux_t *cmux))
474 {
475  tor_assert(cmux);
476 
477  return cmux->policy;
478 }
479 
485 void
487  const circuitmux_policy_t *pol)
488 {
489  const circuitmux_policy_t *old_pol = NULL, *new_pol = NULL;
490  circuitmux_policy_data_t *old_pol_data = NULL, *new_pol_data = NULL;
491  chanid_circid_muxinfo_t **i = NULL;
492  channel_t *chan = NULL;
493  uint64_t last_chan_id_searched = 0;
494  circuit_t *circ = NULL;
495 
496  tor_assert(cmux);
497 
498  /* Set up variables */
499  old_pol = cmux->policy;
500  old_pol_data = cmux->policy_data;
501  new_pol = pol;
502 
503  /* Check if this is the trivial case */
504  if (old_pol == new_pol) return;
505 
506  /* Allocate data for new policy, if any */
507  if (new_pol && new_pol->alloc_cmux_data) {
508  /*
509  * If alloc_cmux_data is not null, then we expect to get some policy
510  * data. Assert that we also have free_cmux_data so we can free it
511  * when the time comes, and allocate it.
512  */
513  tor_assert(new_pol->free_cmux_data);
514  new_pol_data = new_pol->alloc_cmux_data(cmux);
515  tor_assert(new_pol_data);
516  }
517 
518  /* Install new policy and new policy data on cmux */
519  cmux->policy = new_pol;
520  cmux->policy_data = new_pol_data;
521 
522  /* Iterate over all circuits, attaching/detaching each one */
523  i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
524  while (i) {
525  /* Assert that this entry isn't NULL */
526  tor_assert(*i);
527 
528  /*
529  * Get the channel; since normal case is all circuits on the mux share a
530  * channel, we cache last_chan_id_searched
531  */
532  if (!chan || last_chan_id_searched != (*i)->chan_id) {
533  chan = channel_find_by_global_id((*i)->chan_id);
534  last_chan_id_searched = (*i)->chan_id;
535  }
536  tor_assert(chan);
537 
538  /* Get the circuit */
539  circ = circuit_get_by_circid_channel_even_if_marked((*i)->circ_id, chan);
540  tor_assert(circ);
541 
542  /* Need to tell old policy it becomes inactive (i.e., it is active) ? */
543  if (old_pol && old_pol->notify_circ_inactive &&
544  (*i)->muxinfo.cell_count > 0) {
545  old_pol->notify_circ_inactive(cmux, old_pol_data, circ,
546  (*i)->muxinfo.policy_data);
547  }
548 
549  /* Need to free old policy data? */
550  if ((*i)->muxinfo.policy_data) {
551  /* Assert that we have the means to free it if we have policy data */
552  tor_assert(old_pol);
553  tor_assert(old_pol->free_circ_data);
554  /* Free it */
555  old_pol->free_circ_data(cmux, old_pol_data, circ,
556  (*i)->muxinfo.policy_data);
557  (*i)->muxinfo.policy_data = NULL;
558  }
559 
560  /* Need to allocate new policy data? */
561  if (new_pol && new_pol->alloc_circ_data) {
562  /*
563  * If alloc_circ_data is not null, we expect to get some per-circuit
564  * policy data. Assert that we also have free_circ_data so we can
565  * free it when the time comes, and allocate it.
566  */
567  tor_assert(new_pol->free_circ_data);
568  (*i)->muxinfo.policy_data =
569  new_pol->alloc_circ_data(cmux, new_pol_data, circ,
570  (*i)->muxinfo.direction,
571  (*i)->muxinfo.cell_count);
572  }
573 
574  /* Need to make active on new policy? */
575  if (new_pol && new_pol->notify_circ_active &&
576  (*i)->muxinfo.cell_count > 0) {
577  new_pol->notify_circ_active(cmux, new_pol_data, circ,
578  (*i)->muxinfo.policy_data);
579  }
580 
581  /* Advance to next circuit map entry */
582  i = HT_NEXT(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
583  }
584 
585  /* Free data for old policy, if any */
586  if (old_pol_data) {
587  /*
588  * If we had old policy data, we should have an old policy and a free
589  * function for it.
590  */
591  tor_assert(old_pol);
592  tor_assert(old_pol->free_cmux_data);
593  old_pol->free_cmux_data(cmux, old_pol_data);
594  old_pol_data = NULL;
595  }
596 }
597 
598 /*
599  * Circuitmux/circuit attachment status inquiry functions
600  */
601 
608 {
609  chanid_circid_muxinfo_t *hashent = NULL;
610 
611  /* Try to find a map entry */
612  hashent = circuitmux_find_map_entry(cmux, circ);
613 
614  /*
615  * This function should only be called on attached circuits; assert that
616  * we had a map entry.
617  */
618  tor_assert(hashent);
619 
620  /* Return the direction from the map entry */
621  return hashent->muxinfo.direction;
622 }
623 
631 {
632  chanid_circid_muxinfo_t search, *hashent = NULL;
633 
634  /* Sanity-check parameters */
635  tor_assert(cmux);
636  tor_assert(cmux->chanid_circid_map);
637  tor_assert(circ);
638 
639  /* Check if we have n_chan */
640  if (circ->n_chan) {
641  /* Okay, let's see if it's attached for n_chan/n_circ_id */
642  search.chan_id = circ->n_chan->global_identifier;
643  search.circ_id = circ->n_circ_id;
644 
645  /* Query */
646  hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
647  &search);
648  }
649 
650  /* Found something? */
651  if (hashent) {
652  /*
653  * Assert that the direction makes sense for a hashent we found by
654  * n_chan/n_circ_id before we return it.
655  */
656  tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_OUT);
657  } else {
658  /* Not there, have we got a p_chan/p_circ_id to try? */
659  if (circ->magic == OR_CIRCUIT_MAGIC) {
660  search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
661  /* Check for p_chan */
662  if (TO_OR_CIRCUIT(circ)->p_chan) {
663  search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
664  /* Okay, search for that */
665  hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
666  &search);
667  /* Find anything? */
668  if (hashent) {
669  /* Assert that the direction makes sense before we return it */
670  tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_IN);
671  }
672  }
673  }
674  }
675 
676  /* Okay, hashent is it if it was there */
677  return hashent;
678 }
679 
684 int
686 {
687  chanid_circid_muxinfo_t *hashent = NULL;
688 
689  /* Look if it's in the circuit map */
690  hashent = circuitmux_find_map_entry(cmux, circ);
691 
692  return (hashent != NULL);
693 }
694 
699 int
701 {
702  chanid_circid_muxinfo_t *hashent = NULL;
703  int is_active = 0;
704 
705  tor_assert(cmux);
706  tor_assert(circ);
707 
708  /* Look if it's in the circuit map */
709  hashent = circuitmux_find_map_entry(cmux, circ);
710  if (hashent) {
711  /* Check the number of cells on this circuit */
712  is_active = (hashent->muxinfo.cell_count > 0);
713  }
714  /* else not attached, so not active */
715 
716  return is_active;
717 }
718 
723 unsigned int
725 {
726  chanid_circid_muxinfo_t *hashent = NULL;
727  unsigned int n_cells = 0;
728 
729  tor_assert(cmux);
730  tor_assert(circ);
731 
732  /* Look if it's in the circuit map */
733  hashent = circuitmux_find_map_entry(cmux, circ);
734  if (hashent) {
735  /* Just get the cell count for this circuit */
736  n_cells = hashent->muxinfo.cell_count;
737  }
738  /* else not attached, so 0 cells */
739 
740  return n_cells;
741 }
742 
747 MOCK_IMPL(unsigned int,
748 circuitmux_num_cells, (circuitmux_t *cmux))
749 {
750  tor_assert(cmux);
751 
752  return cmux->n_cells + cmux->destroy_cell_queue.n;
753 }
754 
759 unsigned int
761 {
762  tor_assert(cmux);
763 
764  return cmux->n_active_circuits;
765 }
766 
771 unsigned int
773 {
774  tor_assert(cmux);
775 
776  return cmux->n_circuits;
777 }
778 
779 /*
780  * Functions for circuit code to call to update circuit status
781  */
782 
788 circuitmux_attach_circuit,(circuitmux_t *cmux, circuit_t *circ,
789  cell_direction_t direction))
790 {
791  channel_t *chan = NULL;
792  uint64_t channel_id;
793  circid_t circ_id;
794  chanid_circid_muxinfo_t search, *hashent = NULL;
795  unsigned int cell_count;
796 
797  tor_assert(cmux);
798  tor_assert(circ);
799  tor_assert(direction == CELL_DIRECTION_IN ||
800  direction == CELL_DIRECTION_OUT);
801 
802  /*
803  * Figure out which channel we're using, and get the circuit's current
804  * cell count and circuit ID; assert that the circuit is not already
805  * attached to another mux.
806  */
807  if (direction == CELL_DIRECTION_OUT) {
808  /* It's n_chan */
809  chan = circ->n_chan;
810  cell_count = circ->n_chan_cells.n;
811  circ_id = circ->n_circ_id;
812  } else {
813  /* We want p_chan */
814  chan = TO_OR_CIRCUIT(circ)->p_chan;
815  cell_count = TO_OR_CIRCUIT(circ)->p_chan_cells.n;
816  circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
817  }
818  /* Assert that we did get a channel */
819  tor_assert(chan);
820  /* Assert that the circuit ID is sensible */
821  tor_assert(circ_id != 0);
822 
823  /* Get the channel ID */
824  channel_id = chan->global_identifier;
825 
826  /* See if we already have this one */
827  search.chan_id = channel_id;
828  search.circ_id = circ_id;
829  hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
830  &search);
831 
832  if (hashent) {
833  /*
834  * This circuit was already attached to this cmux; make sure the
835  * directions match and update the cell count and active circuit count.
836  */
837  log_info(LD_CIRC,
838  "Circuit %u on channel %"PRIu64 " was already attached to "
839  "cmux %p (trying to attach to %p)",
840  (unsigned)circ_id, (channel_id),
841  ((direction == CELL_DIRECTION_OUT) ?
842  circ->n_mux : TO_OR_CIRCUIT(circ)->p_mux),
843  cmux);
844 
845  /*
846  * The mux pointer on this circuit and the direction in result should
847  * match; otherwise assert.
848  */
849  if (direction == CELL_DIRECTION_OUT) tor_assert(circ->n_mux == cmux);
850  else tor_assert(TO_OR_CIRCUIT(circ)->p_mux == cmux);
851  tor_assert(hashent->muxinfo.direction == direction);
852 
853  /*
854  * Looks okay; just update the cell count and active circuits if we must
855  */
856  if (hashent->muxinfo.cell_count > 0 && cell_count == 0) {
857  --(cmux->n_active_circuits);
859  } else if (hashent->muxinfo.cell_count == 0 && cell_count > 0) {
860  ++(cmux->n_active_circuits);
861  circuitmux_make_circuit_active(cmux, circ);
862  }
863  cmux->n_cells -= hashent->muxinfo.cell_count;
864  cmux->n_cells += cell_count;
865  hashent->muxinfo.cell_count = cell_count;
866  } else {
867  /*
868  * New circuit; add an entry and update the circuit/active circuit
869  * counts.
870  */
871  log_debug(LD_CIRC,
872  "Attaching circuit %u on channel %"PRIu64 " to cmux %p",
873  (unsigned)circ_id, (channel_id), cmux);
874 
875  /*
876  * Assert that the circuit doesn't already have a mux for this
877  * direction.
878  */
879  if (direction == CELL_DIRECTION_OUT) tor_assert(circ->n_mux == NULL);
880  else tor_assert(TO_OR_CIRCUIT(circ)->p_mux == NULL);
881 
882  /* Insert it in the map */
883  hashent = tor_malloc_zero(sizeof(*hashent));
884  hashent->chan_id = channel_id;
885  hashent->circ_id = circ_id;
886  hashent->muxinfo.cell_count = cell_count;
887  hashent->muxinfo.direction = direction;
888  /* Allocate policy specific circuit data if we need it */
889  if (cmux->policy->alloc_circ_data) {
890  /* Assert that we have the means to free policy-specific data */
891  tor_assert(cmux->policy->free_circ_data);
892  /* Allocate it */
893  hashent->muxinfo.policy_data =
894  cmux->policy->alloc_circ_data(cmux,
895  cmux->policy_data,
896  circ,
897  direction,
898  cell_count);
899  /* If we wanted policy data, it's an error not to get any */
900  tor_assert(hashent->muxinfo.policy_data);
901  }
902  HT_INSERT(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
903  hashent);
904 
905  /* Set the circuit's mux for this direction */
906  if (direction == CELL_DIRECTION_OUT) circ->n_mux = cmux;
907  else TO_OR_CIRCUIT(circ)->p_mux = cmux;
908 
909  /* Update counters */
910  ++(cmux->n_circuits);
911  if (cell_count > 0) {
912  ++(cmux->n_active_circuits);
913  circuitmux_make_circuit_active(cmux, circ);
914  }
915  cmux->n_cells += cell_count;
916  }
917 }
918 
925 circuitmux_detach_circuit,(circuitmux_t *cmux, circuit_t *circ))
926 {
927  chanid_circid_muxinfo_t search, *hashent = NULL;
928  /*
929  * Use this to keep track of whether we found it for n_chan or
930  * p_chan for consistency checking.
931  *
932  * The 0 initializer is not a valid cell_direction_t value.
933  * We assert that it has been replaced with a valid value before it is used.
934  */
935  cell_direction_t last_searched_direction = 0;
936 
937  tor_assert(cmux);
938  tor_assert(cmux->chanid_circid_map);
939  tor_assert(circ);
940 
941  /* See if we have it for n_chan/n_circ_id */
942  if (circ->n_chan) {
943  search.chan_id = circ->n_chan->global_identifier;
944  search.circ_id = circ->n_circ_id;
945  hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
946  &search);
947  last_searched_direction = CELL_DIRECTION_OUT;
948  }
949 
950  /* Got one? If not, see if it's an or_circuit_t and try p_chan/p_circ_id */
951  if (!hashent) {
952  if (circ->magic == OR_CIRCUIT_MAGIC) {
953  search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
954  if (TO_OR_CIRCUIT(circ)->p_chan) {
955  search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
956  hashent = HT_FIND(chanid_circid_muxinfo_map,
957  cmux->chanid_circid_map,
958  &search);
959  last_searched_direction = CELL_DIRECTION_IN;
960  }
961  }
962  }
963 
964  tor_assert(last_searched_direction == CELL_DIRECTION_OUT
965  || last_searched_direction == CELL_DIRECTION_IN);
966 
967  /*
968  * If hashent isn't NULL, we have a circuit to detach; don't remove it from
969  * the map until later of circuitmux_make_circuit_inactive() breaks.
970  */
971  if (hashent) {
972  /* Update counters */
973  --(cmux->n_circuits);
974  if (hashent->muxinfo.cell_count > 0) {
975  --(cmux->n_active_circuits);
976  /* This does policy notifies, so comes before freeing policy data */
978  }
979  cmux->n_cells -= hashent->muxinfo.cell_count;
980 
981  /* Free policy-specific data if we have it */
982  if (hashent->muxinfo.policy_data) {
983  /* If we have policy data, assert that we have the means to free it */
984  tor_assert(cmux->policy);
985  tor_assert(cmux->policy->free_circ_data);
986  /* Call free_circ_data() */
987  cmux->policy->free_circ_data(cmux,
988  cmux->policy_data,
989  circ,
990  hashent->muxinfo.policy_data);
991  hashent->muxinfo.policy_data = NULL;
992  }
993 
994  /* Consistency check: the direction must match the direction searched */
995  tor_assert(last_searched_direction == hashent->muxinfo.direction);
996  /* Clear the circuit's mux for this direction */
997  if (last_searched_direction == CELL_DIRECTION_OUT) circ->n_mux = NULL;
998  else TO_OR_CIRCUIT(circ)->p_mux = NULL;
999 
1000  /* Now remove it from the map */
1001  HT_REMOVE(chanid_circid_muxinfo_map, cmux->chanid_circid_map, hashent);
1002 
1003  /* Free the hash entry */
1004  tor_free(hashent);
1005  }
1006 }
1007 
1013 static void
1015 {
1016  tor_assert(cmux);
1017  tor_assert(cmux->policy);
1018  tor_assert(circ);
1019 
1020  /* Policy-specific notification */
1021  if (cmux->policy->notify_circ_active) {
1022  /* Okay, we need to check the circuit for policy data now */
1023  chanid_circid_muxinfo_t *hashent = circuitmux_find_map_entry(cmux, circ);
1024  /* We should have found something */
1025  tor_assert(hashent);
1026  /* Notify */
1027  cmux->policy->notify_circ_active(cmux, cmux->policy_data,
1028  circ, hashent->muxinfo.policy_data);
1029  }
1030 }
1031 
1037 static void
1039 {
1040  tor_assert(cmux);
1041  tor_assert(cmux->policy);
1042  tor_assert(circ);
1043 
1044  /* Policy-specific notification */
1045  if (cmux->policy->notify_circ_inactive) {
1046  /* Okay, we need to check the circuit for policy data now */
1047  chanid_circid_muxinfo_t *hashent = circuitmux_find_map_entry(cmux, circ);
1048  /* We should have found something */
1049  tor_assert(hashent);
1050  /* Notify */
1051  cmux->policy->notify_circ_inactive(cmux, cmux->policy_data,
1052  circ, hashent->muxinfo.policy_data);
1053  }
1054 }
1055 
1060 void
1062 {
1063  /* This is the same as setting the cell count to zero */
1064  circuitmux_set_num_cells(cmux, circ, 0);
1065 }
1066 
1071 void
1073  unsigned int n_cells)
1074 {
1075  chanid_circid_muxinfo_t *hashent = NULL;
1076 
1077  tor_assert(cmux);
1078  tor_assert(circ);
1079 
1080  /* Search for this circuit's entry */
1081  hashent = circuitmux_find_map_entry(cmux, circ);
1082  /* Assert that we found one */
1083  tor_assert(hashent);
1084 
1085  /* Update cmux cell counter */
1086  cmux->n_cells -= hashent->muxinfo.cell_count;
1087  cmux->n_cells += n_cells;
1088 
1089  /* Do we need to notify a cmux policy? */
1090  if (cmux->policy->notify_set_n_cells) {
1091  /* Call notify_set_n_cells */
1092  cmux->policy->notify_set_n_cells(cmux,
1093  cmux->policy_data,
1094  circ,
1095  hashent->muxinfo.policy_data,
1096  n_cells);
1097  }
1098 
1099  /*
1100  * Update cmux active circuit counter: is the old cell count > 0 and the
1101  * new cell count == 0 ?
1102  */
1103  if (hashent->muxinfo.cell_count > 0 && n_cells == 0) {
1104  --(cmux->n_active_circuits);
1105  hashent->muxinfo.cell_count = n_cells;
1107  /* Is the old cell count == 0 and the new cell count > 0 ? */
1108  } else if (hashent->muxinfo.cell_count == 0 && n_cells > 0) {
1109  ++(cmux->n_active_circuits);
1110  hashent->muxinfo.cell_count = n_cells;
1111  circuitmux_make_circuit_active(cmux, circ);
1112  } else {
1113  hashent->muxinfo.cell_count = n_cells;
1114  }
1115 }
1116 
1117 /*
1118  * Functions for channel code to call to get a circuit to transmit from or
1119  * notify that cells have been transmitted.
1120  */
1121 
1133 circuit_t *
1135  destroy_cell_queue_t **destroy_queue_out)
1136 {
1137  circuit_t *circ = NULL;
1138 
1139  tor_assert(cmux);
1140  tor_assert(cmux->policy);
1141  /* This callback is mandatory. */
1142  tor_assert(cmux->policy->pick_active_circuit);
1143  tor_assert(destroy_queue_out);
1144 
1145  *destroy_queue_out = NULL;
1146 
1147  if (cmux->destroy_cell_queue.n &&
1148  (!cmux->last_cell_was_destroy || cmux->n_active_circuits == 0)) {
1149  /* We have destroy cells to send, and either we just sent a relay cell,
1150  * or we have no relay cells to send. */
1151 
1152  /* XXXX We should let the cmux policy have some say in this eventually. */
1153  /* XXXX Alternating is not a terribly brilliant approach here. */
1154  *destroy_queue_out = &cmux->destroy_cell_queue;
1155 
1156  cmux->last_cell_was_destroy = 1;
1157  } else if (cmux->n_active_circuits > 0) {
1158  /* We also must have a cell available for this to be the case */
1159  tor_assert(cmux->n_cells > 0);
1160  /* Do we have a policy-provided circuit selector? */
1161  circ = cmux->policy->pick_active_circuit(cmux, cmux->policy_data);
1162  cmux->last_cell_was_destroy = 0;
1163  } else {
1164  tor_assert(cmux->n_cells == 0);
1165  tor_assert(cmux->destroy_cell_queue.n == 0);
1166  }
1167 
1168  return circ;
1169 }
1170 
1176 void
1178  unsigned int n_cells)
1179 {
1180  chanid_circid_muxinfo_t *hashent = NULL;
1181  int becomes_inactive = 0;
1182 
1183  tor_assert(cmux);
1184  tor_assert(circ);
1185 
1186  if (n_cells == 0) return;
1187 
1188  /*
1189  * To handle this, we have to:
1190  *
1191  * 1.) Adjust the circuit's cell counter in the cmux hash table
1192  * 2.) Move the circuit to the tail of the active_circuits linked list
1193  * for this cmux, or make the circuit inactive if the cell count
1194  * went to zero.
1195  * 3.) Call cmux->policy->notify_xmit_cells(), if any
1196  */
1197 
1198  /* Find the hash entry */
1199  hashent = circuitmux_find_map_entry(cmux, circ);
1200  /* Assert that we found one */
1201  tor_assert(hashent);
1202 
1203  /* Adjust the cell counter and assert that we had that many cells to send */
1204  tor_assert(n_cells <= hashent->muxinfo.cell_count);
1205  hashent->muxinfo.cell_count -= n_cells;
1206  /* Do we need to make the circuit inactive? */
1207  if (hashent->muxinfo.cell_count == 0) becomes_inactive = 1;
1208  /* Adjust the mux cell counter */
1209  cmux->n_cells -= n_cells;
1210 
1211  /*
1212  * We call notify_xmit_cells() before making the circuit inactive if needed,
1213  * so the policy can always count on this coming in on an active circuit.
1214  */
1215  if (cmux->policy->notify_xmit_cells) {
1216  cmux->policy->notify_xmit_cells(cmux, cmux->policy_data, circ,
1217  hashent->muxinfo.policy_data,
1218  n_cells);
1219  }
1220 
1221  /*
1222  * Now make the circuit inactive if needed; this will call the policy's
1223  * notify_circ_inactive() if present.
1224  */
1225  if (becomes_inactive) {
1226  --(cmux->n_active_circuits);
1228  }
1229 }
1230 
1236 void
1238 {
1239  tor_assert(cmux);
1240 
1241  --(cmux->destroy_ctr);
1242  --(global_destroy_ctr);
1243  log_debug(LD_CIRC,
1244  "Cmux at %p sent a destroy, cmux counter is now %"PRId64", "
1245  "global counter is now %"PRId64,
1246  cmux,
1247  (cmux->destroy_ctr),
1248  (global_destroy_ctr));
1249 }
1250 
1251 /*DOCDOC */
1252 void
1253 circuitmux_append_destroy_cell(channel_t *chan,
1254  circuitmux_t *cmux,
1255  circid_t circ_id,
1256  uint8_t reason)
1257 {
1258  destroy_cell_queue_append(&cmux->destroy_cell_queue, circ_id, reason);
1259 
1260  /* Destroy entering the queue, update counters */
1261  ++(cmux->destroy_ctr);
1263  log_debug(LD_CIRC,
1264  "Cmux at %p queued a destroy for circ %u, cmux counter is now "
1265  "%"PRId64", global counter is now %"PRId64,
1266  cmux, circ_id,
1267  (cmux->destroy_ctr),
1268  (global_destroy_ctr));
1269 
1270  /* XXXX Duplicate code from append_cell_to_circuit_queue */
1271  if (!channel_has_queued_writes(chan)) {
1272  /* There is no data at all waiting to be sent on the outbuf. Add a
1273  * cell, so that we can notice when it gets flushed, flushed_some can
1274  * get called, and we can start putting more data onto the buffer then.
1275  */
1276  log_debug(LD_GENERAL, "Primed a buffer.");
1277  channel_flush_from_first_active_circuit(chan, 1);
1278  }
1279 }
1280 
1281 /*DOCDOC; for debugging 12184. This runs slowly. */
1282 int64_t
1283 circuitmux_count_queued_destroy_cells(const channel_t *chan,
1284  const circuitmux_t *cmux)
1285 {
1286  int64_t n_destroy_cells = cmux->destroy_ctr;
1287  int64_t destroy_queue_size = cmux->destroy_cell_queue.n;
1288 
1289  int64_t manual_total = 0;
1290  int64_t manual_total_in_map = 0;
1291  destroy_cell_t *cell;
1292 
1293  TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
1294  circid_t id;
1295  ++manual_total;
1296 
1297  id = cell->circid;
1298  if (circuit_id_in_use_on_channel(id, (channel_t*)chan))
1299  ++manual_total_in_map;
1300  }
1301 
1302  if (n_destroy_cells != destroy_queue_size ||
1303  n_destroy_cells != manual_total ||
1304  n_destroy_cells != manual_total_in_map) {
1305  log_warn(LD_BUG, " Discrepancy in counts for queued destroy cells on "
1306  "circuitmux. n=%"PRId64". queue_size=%"PRId64". "
1307  "manual_total=%"PRId64". manual_total_in_map=%"PRId64".",
1308  (n_destroy_cells),
1309  (destroy_queue_size),
1310  (manual_total),
1311  (manual_total_in_map));
1312  }
1313 
1314  return n_destroy_cells;
1315 }
1316 
1328 circuitmux_compare_muxes, (circuitmux_t *cmux_1, circuitmux_t *cmux_2))
1329 {
1330  const circuitmux_policy_t *policy;
1331 
1332  tor_assert(cmux_1);
1333  tor_assert(cmux_2);
1334 
1335  if (cmux_1 == cmux_2) {
1336  /* Equivalent because they're the same cmux */
1337  return 0;
1338  }
1339 
1340  if (cmux_1->policy && cmux_2->policy) {
1341  if (cmux_1->policy == cmux_2->policy) {
1342  policy = cmux_1->policy;
1343 
1344  if (policy->cmp_cmux) {
1345  /* Okay, we can compare! */
1346  return policy->cmp_cmux(cmux_1, cmux_1->policy_data,
1347  cmux_2, cmux_2->policy_data);
1348  } else {
1349  /*
1350  * Equivalent because the policy doesn't know how to compare between
1351  * muxes.
1352  */
1353  return 0;
1354  }
1355  } else {
1356  /* Equivalent because they have different policies */
1357  return 0;
1358  }
1359  } else {
1360  /* Equivalent because one or both are missing a policy */
1361  return 0;
1362  }
1363 }
1364 
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:1061
circuit_t * circuit_get_by_circid_channel_even_if_marked(circid_t circ_id, channel_t *chan)
Definition: circuitlist.c:1530
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:58
unsigned int circuitmux_num_cells_for_circuit(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:724
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:1544
cell_direction_t circuitmux_attached_circuit_direction(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:607
static chanid_circid_muxinfo_t * circuitmux_find_map_entry(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:630
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:396
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:76
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:1072
static void circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:1014
void destroy_cell_queue_append(destroy_cell_queue_t *queue, circid_t circid, uint8_t reason)
Definition: relay.c:2562
Header file for channel.c.
tor_assert(buffer)
#define LD_CIRC
Definition: log.h:78
circid_t n_circ_id
Definition: circuit_st.h:67
void circuitmux_notify_xmit_destroy(circuitmux_t *cmux)
Definition: circuitmux.c:1237
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:2536
void circuitmux_notify_xmit_cells(circuitmux_t *cmux, circuit_t *circ, unsigned int n_cells)
Definition: circuitmux.c:1177
void circuitmux_set_policy(circuitmux_t *cmux, const circuitmux_policy_t *pol)
Definition: circuitmux.c:486
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.
circuitmux_t * p_mux
Definition: or_circuit_st.h:40
int64_t destroy_ctr
Definition: circuitmux.c:135
void circuitmux_clear_policy(circuitmux_t *cmux)
Definition: circuitmux.c:460
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:700
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:382
uint32_t circid_t
Definition: or.h:608
unsigned int circuitmux_num_circuits(circuitmux_t *cmux)
Definition: circuitmux.c:772
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:2528
int circuitmux_is_circuit_attached(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:685
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:1134
MOCK_IMPL(const circuitmux_policy_t *, circuitmux_get_policy,(circuitmux_t *cmux))
Definition: circuitmux.c:472
unsigned int circuitmux_num_active_circuits(circuitmux_t *cmux)
Definition: circuitmux.c:760
circuitmux_t * n_mux
Definition: circuit_st.h:73
static void circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:1038
int channel_has_queued_writes(channel_t *chan)
Definition: channel.c:2869
static int64_t global_destroy_ctr
Definition: circuitmux.c:195
#define LD_BUG
Definition: log.h:82
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