Tor  0.4.7.0-alpha-dev
circuitlist.c
Go to the documentation of this file.
1 /* Copyright 2001 Matej Pfajfar.
2  * Copyright (c) 2001-2004, Roger Dingledine.
3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4  * Copyright (c) 2007-2021, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
7 /**
8  * \file circuitlist.c
9  *
10  * \brief Manage global structures that list and index circuits, and
11  * look up circuits within them.
12  *
13  * One of the most frequent operations in Tor occurs every time that
14  * a relay cell arrives on a channel. When that happens, we need to
15  * find which circuit it is associated with, based on the channel and the
16  * circuit ID in the relay cell.
17  *
18  * To handle that, we maintain a global list of circuits, and a hashtable
19  * mapping [channel,circID] pairs to circuits. Circuits are added to and
20  * removed from this mapping using circuit_set_p_circid_chan() and
21  * circuit_set_n_circid_chan(). To look up a circuit from this map, most
22  * callers should use circuit_get_by_circid_channel(), though
23  * circuit_get_by_circid_channel_even_if_marked() is appropriate under some
24  * circumstances.
25  *
26  * We also need to allow for the possibility that we have blocked use of a
27  * circuit ID (because we are waiting to send a DESTROY cell), but the
28  * circuit is not there any more. For that case, we allow placeholder
29  * entries in the table, using channel_mark_circid_unusable().
30  *
31  * To efficiently handle a channel that has just opened, we also maintain a
32  * list of the circuits waiting for channels, so we can attach them as
33  * needed without iterating through the whole list of circuits, using
34  * circuit_get_all_pending_on_channel().
35  *
36  * In this module, we also handle the list of circuits that have been
37  * marked for close elsewhere, and close them as needed. (We use this
38  * "mark now, close later" pattern here and elsewhere to avoid
39  * unpredictable recursion if we closed every circuit immediately upon
40  * realizing it needed to close.) See circuit_mark_for_close() for the
41  * mark function, and circuit_close_all_marked() for the close function.
42  *
43  * For hidden services, we need to be able to look up introduction point
44  * circuits and rendezvous circuits by cookie, key, etc. These are
45  * currently handled with linear searches in
46  * circuit_get_next_by_pk_and_purpose(), and with hash lookups in
47  * circuit_get_rendezvous() and circuit_get_intro_point().
48  *
49  * This module is also the entry point for our out-of-memory handler
50  * logic, which was originally circuit-focused.
51  **/
52 #define CIRCUITLIST_PRIVATE
53 #define OCIRC_EVENT_PRIVATE
54 #include "lib/cc/torint.h" /* TOR_PRIuSZ */
55 
56 #include "core/or/or.h"
57 #include "core/or/channel.h"
58 #include "core/or/channeltls.h"
59 #include "feature/client/circpathbias.h"
60 #include "core/or/circuitbuild.h"
61 #include "core/or/circuitlist.h"
62 #include "core/or/circuituse.h"
63 #include "core/or/circuitstats.h"
64 #include "core/or/circuitpadding.h"
65 #include "core/or/crypt_path.h"
66 #include "core/or/extendinfo.h"
67 #include "core/or/trace_probes_circuit.h"
69 #include "app/config/config.h"
71 #include "core/or/connection_or.h"
78 #include "core/mainloop/mainloop.h"
79 #include "feature/hs/hs_cache.h"
80 #include "feature/hs/hs_circuit.h"
82 #include "feature/hs/hs_ident.h"
87 #include "core/crypto/onion_fast.h"
88 #include "core/or/policies.h"
89 #include "core/or/relay.h"
93 #include "feature/stats/bwhist.h"
94 #include "feature/stats/rephist.h"
97 #include "core/or/channelpadding.h"
98 #include "lib/compress/compress.h"
102 #include "lib/buf/buffers.h"
103 
104 #include "core/or/ocirc_event.h"
105 
106 #include "ht.h"
107 
112 #include "core/or/half_edge_st.h"
113 #include "core/or/extend_info_st.h"
114 #include "core/or/or_circuit_st.h"
116 
117 /********* START VARIABLES **********/
118 
119 /** A global list of all circuits at this hop. */
121 
122 /** A global list of all origin circuits. Every element of this is also
123  * an element of global_circuitlist. */
125 
126 /** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
128 
129 /** List of all the (origin) circuits whose state is
130  * CIRCUIT_STATE_GUARD_WAIT. */
132 
133 /** A list of all the circuits that have been marked with
134  * circuit_mark_for_close and which are waiting for circuit_about_to_free. */
136 
137 static void circuit_about_to_free_atexit(circuit_t *circ);
138 static void circuit_about_to_free(circuit_t *circ);
139 
140 /**
141  * A cached value of the current state of the origin circuit list. Has the
142  * value 1 if we saw any opened circuits recently (since the last call to
143  * circuit_any_opened_circuits(), which gets called around once a second by
144  * circuit_expire_building). 0 otherwise.
145  */
147 
148 /********* END VARIABLES ************/
149 
150 /* Implement circuit handle helpers. */
151 HANDLE_IMPL(circuit, circuit_t,)
152 
153 or_circuit_t *
155 {
156  tor_assert(x->magic == OR_CIRCUIT_MAGIC);
157  return DOWNCAST(or_circuit_t, x);
158 }
159 const or_circuit_t *
160 CONST_TO_OR_CIRCUIT(const circuit_t *x)
161 {
163  return DOWNCAST(or_circuit_t, x);
164 }
167 {
169  return DOWNCAST(origin_circuit_t, x);
170 }
171 const origin_circuit_t *
172 CONST_TO_ORIGIN_CIRCUIT(const circuit_t *x)
173 {
175  return DOWNCAST(origin_circuit_t, x);
176 }
177 
178 /** A map from channel and circuit ID to circuit. (Lookup performance is
179  * very important here, since we need to do it every time a cell arrives.) */
181  HT_ENTRY(chan_circid_circuit_map_t) node;
182  channel_t *chan;
183  circid_t circ_id;
184  circuit_t *circuit;
185  /* For debugging 12184: when was this placeholder item added? */
186  time_t made_placeholder_at;
188 
189 /** Helper for hash tables: compare the channel and circuit ID for a and
190  * b, and return less than, equal to, or greater than zero appropriately.
191  */
192 static inline int
195 {
196  return a->chan == b->chan && a->circ_id == b->circ_id;
197 }
198 
199 /** Helper: return a hash based on circuit ID and the pointer value of
200  * chan in <b>a</b>. */
201 static inline unsigned int
203 {
204  /* Try to squeze the siphash input into 8 bytes to save any extra siphash
205  * rounds. This hash function is in the critical path. */
206  uintptr_t chan = (uintptr_t) (void*) a->chan;
207  uint32_t array[2];
208  array[0] = a->circ_id;
209  /* The low bits of the channel pointer are uninteresting, since the channel
210  * is a pretty big structure. */
211  array[1] = (uint32_t) (chan >> 6);
212  return (unsigned) siphash24g(array, sizeof(array));
213 }
214 
215 /** Map from [chan,circid] to circuit. */
216 static HT_HEAD(chan_circid_map, chan_circid_circuit_map_t)
217  chan_circid_map = HT_INITIALIZER();
218 HT_PROTOTYPE(chan_circid_map, chan_circid_circuit_map_t, node,
220 HT_GENERATE2(chan_circid_map, chan_circid_circuit_map_t, node,
223 
224 /** The most recently returned entry from circuit_get_by_circid_chan;
225  * used to improve performance when many cells arrive in a row from the
226  * same circuit.
227  */
228 static chan_circid_circuit_map_t *_last_circid_chan_ent = NULL;
229 
230 /** Implementation helper for circuit_set_{p,n}_circid_channel: A circuit ID
231  * and/or channel for circ has just changed from <b>old_chan, old_id</b>
232  * to <b>chan, id</b>. Adjust the chan,circid map as appropriate, removing
233  * the old entry (if any) and adding a new one. */
234 static void
235 circuit_set_circid_chan_helper(circuit_t *circ, int direction,
236  circid_t id,
237  channel_t *chan)
238 {
241  channel_t *old_chan, **chan_ptr;
242  circid_t old_id, *circid_ptr;
243  int make_active, attached = 0;
244 
245  if (direction == CELL_DIRECTION_OUT) {
246  chan_ptr = &circ->n_chan;
247  circid_ptr = &circ->n_circ_id;
248  make_active = circ->n_chan_cells.n > 0;
249  } else {
250  or_circuit_t *c = TO_OR_CIRCUIT(circ);
251  chan_ptr = &c->p_chan;
252  circid_ptr = &c->p_circ_id;
253  make_active = c->p_chan_cells.n > 0;
254  }
255  old_chan = *chan_ptr;
256  old_id = *circid_ptr;
257 
258  if (id == old_id && chan == old_chan)
259  return;
260 
261  if (_last_circid_chan_ent &&
262  ((old_id == _last_circid_chan_ent->circ_id &&
263  old_chan == _last_circid_chan_ent->chan) ||
264  (id == _last_circid_chan_ent->circ_id &&
265  chan == _last_circid_chan_ent->chan))) {
266  _last_circid_chan_ent = NULL;
267  }
268 
269  if (old_chan) {
270  /*
271  * If we're changing channels or ID and had an old channel and a non
272  * zero old ID and weren't marked for close (i.e., we should have been
273  * attached), detach the circuit. ID changes require this because
274  * circuitmux hashes on (channel_id, circuit_id).
275  */
276  if (old_id != 0 && (old_chan != chan || old_id != id) &&
277  !(circ->marked_for_close)) {
278  tor_assert(old_chan->cmux);
279  circuitmux_detach_circuit(old_chan->cmux, circ);
280  }
281 
282  /* we may need to remove it from the conn-circid map */
283  search.circ_id = old_id;
284  search.chan = old_chan;
285  found = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
286  if (found) {
287  tor_free(found);
288  if (direction == CELL_DIRECTION_OUT) {
289  /* One fewer circuits use old_chan as n_chan */
290  --(old_chan->num_n_circuits);
291  } else {
292  /* One fewer circuits use old_chan as p_chan */
293  --(old_chan->num_p_circuits);
294  }
295  }
296  }
297 
298  /* Change the values only after we have possibly made the circuit inactive
299  * on the previous chan. */
300  *chan_ptr = chan;
301  *circid_ptr = id;
302 
303  if (chan == NULL)
304  return;
305 
306  /* now add the new one to the conn-circid map */
307  search.circ_id = id;
308  search.chan = chan;
309  found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
310  if (found) {
311  found->circuit = circ;
312  found->made_placeholder_at = 0;
313  } else {
314  found = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
315  found->circ_id = id;
316  found->chan = chan;
317  found->circuit = circ;
318  HT_INSERT(chan_circid_map, &chan_circid_map, found);
319  }
320 
321  /*
322  * Attach to the circuitmux if we're changing channels or IDs and
323  * have a new channel and ID to use and the circuit is not marked for
324  * close.
325  */
326  if (chan && id != 0 && (old_chan != chan || old_id != id) &&
327  !(circ->marked_for_close)) {
328  tor_assert(chan->cmux);
329  circuitmux_attach_circuit(chan->cmux, circ, direction);
330  attached = 1;
331  }
332 
333  /*
334  * This is a no-op if we have no cells, but if we do it marks us active to
335  * the circuitmux
336  */
337  if (make_active && attached)
338  update_circuit_on_cmux(circ, direction);
339 
340  /* Adjust circuit counts on new channel */
341  if (direction == CELL_DIRECTION_OUT) {
342  ++chan->num_n_circuits;
343  } else {
344  ++chan->num_p_circuits;
345  }
346 }
347 
348 /** Mark that circuit id <b>id</b> shouldn't be used on channel <b>chan</b>,
349  * even if there is no circuit on the channel. We use this to keep the
350  * circuit id from getting re-used while we have queued but not yet sent
351  * a destroy cell. */
352 void
354 {
357 
358  /* See if there's an entry there. That wouldn't be good. */
359  memset(&search, 0, sizeof(search));
360  search.chan = chan;
361  search.circ_id = id;
362  ent = HT_FIND(chan_circid_map, &chan_circid_map, &search);
363 
364  if (ent && ent->circuit) {
365  /* we have a problem. */
366  log_warn(LD_BUG, "Tried to mark %u unusable on %p, but there was already "
367  "a circuit there.", (unsigned)id, chan);
368  } else if (ent) {
369  /* It's already marked. */
370  if (!ent->made_placeholder_at)
371  ent->made_placeholder_at = approx_time();
372  } else {
373  ent = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
374  ent->chan = chan;
375  ent->circ_id = id;
376  /* leave circuit at NULL. */
377  ent->made_placeholder_at = approx_time();
378  HT_INSERT(chan_circid_map, &chan_circid_map, ent);
379  }
380 }
381 
382 /** Mark that a circuit id <b>id</b> can be used again on <b>chan</b>.
383  * We use this to re-enable the circuit ID after we've sent a destroy cell.
384  */
385 void
387 {
390 
391  /* See if there's an entry there. That wouldn't be good. */
392  memset(&search, 0, sizeof(search));
393  search.chan = chan;
394  search.circ_id = id;
395  ent = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
396  if (ent && ent->circuit) {
397  log_warn(LD_BUG, "Tried to mark %u usable on %p, but there was already "
398  "a circuit there.", (unsigned)id, chan);
399  return;
400  }
401  if (_last_circid_chan_ent == ent)
402  _last_circid_chan_ent = NULL;
403  tor_free(ent);
404 }
405 
406 /** Called to indicate that a DESTROY is pending on <b>chan</b> with
407  * circuit ID <b>id</b>, but hasn't been sent yet. */
408 void
410 {
412  if (circ) {
413  if (circ->n_chan == chan && circ->n_circ_id == id) {
414  circ->n_delete_pending = 1;
415  } else {
416  or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
417  if (orcirc->p_chan == chan && orcirc->p_circ_id == id) {
418  circ->p_delete_pending = 1;
419  }
420  }
421  return;
422  }
424 }
425 
426 /** Called to indicate that a DESTROY is no longer pending on <b>chan</b> with
427  * circuit ID <b>id</b> -- typically, because it has been sent. */
428 MOCK_IMPL(void,
430 {
432  if (circ) {
433  if (circ->n_chan == chan && circ->n_circ_id == id) {
434  circ->n_delete_pending = 0;
435  } else {
436  or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
437  if (orcirc->p_chan == chan && orcirc->p_circ_id == id) {
438  circ->p_delete_pending = 0;
439  }
440  }
441  /* XXXX this shouldn't happen; log a bug here. */
442  return;
443  }
444  channel_mark_circid_usable(chan, id);
445 }
446 
447 /** Set the p_conn field of a circuit <b>circ</b>, along
448  * with the corresponding circuit ID, and add the circuit as appropriate
449  * to the (chan,id)->circuit map. */
450 void
452  channel_t *chan)
453 {
454  circuit_t *circ = TO_CIRCUIT(or_circ);
455  channel_t *old_chan = or_circ->p_chan;
456  circid_t old_id = or_circ->p_circ_id;
457 
458  circuit_set_circid_chan_helper(circ, CELL_DIRECTION_IN, id, chan);
459 
460  if (chan) {
462  }
463 
464  if (circ->p_delete_pending && old_chan) {
465  channel_mark_circid_unusable(old_chan, old_id);
466  circ->p_delete_pending = 0;
467  }
468 }
469 
470 /** Set the n_conn field of a circuit <b>circ</b>, along
471  * with the corresponding circuit ID, and add the circuit as appropriate
472  * to the (chan,id)->circuit map. */
473 void
475  channel_t *chan)
476 {
477  channel_t *old_chan = circ->n_chan;
478  circid_t old_id = circ->n_circ_id;
479 
480  circuit_set_circid_chan_helper(circ, CELL_DIRECTION_OUT, id, chan);
481 
482  if (chan) {
484  }
485 
486  if (circ->n_delete_pending && old_chan) {
487  channel_mark_circid_unusable(old_chan, old_id);
488  circ->n_delete_pending = 0;
489  }
490 }
491 
492 /**
493  * Helper function to publish a message about events on an origin circuit
494  *
495  * Publishes a message to subscribers of origin circuit events, and
496  * sends the control event.
497  **/
498 int
500  int reason_code)
501 {
502  ocirc_cevent_msg_t *msg = tor_malloc(sizeof(*msg));
503 
504  tor_assert(circ);
505 
506  msg->gid = circ->global_identifier;
507  msg->evtype = tp;
508  msg->reason = reason_code;
509  msg->onehop = circ->build_state->onehop_tunnel;
510 
511  ocirc_cevent_publish(msg);
512  return control_event_circuit_status(circ, tp, reason_code);
513 }
514 
515 /**
516  * Helper function to publish a state change message
517  *
518  * circuit_set_state() calls this to notify subscribers about a change
519  * of the state of an origin circuit. @a circ must be an origin
520  * circuit.
521  **/
522 static void
524 {
525  ocirc_state_msg_t *msg = tor_malloc(sizeof(*msg));
526  const origin_circuit_t *ocirc;
527 
529  ocirc = CONST_TO_ORIGIN_CIRCUIT(circ);
530  /* Only inbound OR circuits can be in this state, not origin circuits. */
532 
533  msg->gid = ocirc->global_identifier;
534  msg->state = circ->state;
535  msg->onehop = ocirc->build_state->onehop_tunnel;
536 
537  ocirc_state_publish(msg);
538 }
539 
540 /** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
541  * it from lists as appropriate. */
542 void
543 circuit_set_state(circuit_t *circ, uint8_t state)
544 {
545  tor_assert(circ);
546  if (state == circ->state)
547  return;
548  if (PREDICT_UNLIKELY(!circuits_pending_chans))
550  if (PREDICT_UNLIKELY(!circuits_pending_other_guards))
552  if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
553  /* remove from waiting-circuit list. */
555  }
556  if (state == CIRCUIT_STATE_CHAN_WAIT) {
557  /* add to waiting-circuit list. */
559  }
560  if (circ->state == CIRCUIT_STATE_GUARD_WAIT) {
562  }
563  if (state == CIRCUIT_STATE_GUARD_WAIT) {
565  }
566  if (state == CIRCUIT_STATE_GUARD_WAIT || state == CIRCUIT_STATE_OPEN)
568 
569  tor_trace(TR_SUBSYS(circuit), TR_EV(change_state), circ, circ->state, state);
570  circ->state = state;
571  if (CIRCUIT_IS_ORIGIN(circ))
572  circuit_state_publish(circ);
573 }
574 
575 /** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
576  * the given connection. */
577 void
579 {
580  tor_assert(out);
581  tor_assert(chan);
582 
584  return;
585 
587  if (circ->marked_for_close)
588  continue;
589  if (!circ->n_hop)
590  continue;
593  /* Look at addr/port. This is an unkeyed connection. */
594  if (!channel_matches_extend_info(chan, circ->n_hop))
595  continue;
596  } else {
597  /* We expected a key. See if it's the right one. */
598  if (tor_memneq(chan->identity_digest,
600  continue;
601  }
602  smartlist_add(out, circ);
603  } SMARTLIST_FOREACH_END(circ);
604 }
605 
606 /** Return the number of circuits in state CHAN_WAIT, waiting for the given
607  * channel. */
608 int
610 {
611  int cnt;
612  smartlist_t *sl = smartlist_new();
613 
614  tor_assert(chan);
615 
617  cnt = smartlist_len(sl);
618  smartlist_free(sl);
619  log_debug(LD_CIRC,"or_conn to %s, %d pending circs",
620  channel_describe_peer(chan),
621  cnt);
622  return cnt;
623 }
624 
625 /** Remove <b>origin_circ</b> from the global list of origin circuits.
626  * Called when we are freeing a circuit.
627  */
628 static void
630 {
631  int origin_idx = origin_circ->global_origin_circuit_list_idx;
632  if (origin_idx < 0)
633  return;
634  origin_circuit_t *c2;
635  tor_assert(origin_idx <= smartlist_len(global_origin_circuit_list));
636  c2 = smartlist_get(global_origin_circuit_list, origin_idx);
637  tor_assert(origin_circ == c2);
639  if (origin_idx < smartlist_len(global_origin_circuit_list)) {
640  origin_circuit_t *replacement =
641  smartlist_get(global_origin_circuit_list, origin_idx);
642  replacement->global_origin_circuit_list_idx = origin_idx;
643  }
644  origin_circ->global_origin_circuit_list_idx = -1;
645 }
646 
647 /** Add <b>origin_circ</b> to the global list of origin circuits. Called
648  * when creating the circuit. */
649 static void
651 {
652  tor_assert(origin_circ->global_origin_circuit_list_idx == -1);
654  smartlist_add(lst, origin_circ);
655  origin_circ->global_origin_circuit_list_idx = smartlist_len(lst) - 1;
656 }
657 
658 /** Detach from the global circuit list, and deallocate, all
659  * circuits that have been marked for close.
660  */
661 void
663 {
664  if (circuits_pending_close == NULL)
665  return;
666 
670 
671  /* Remove it from the circuit list. */
672  int idx = circ->global_circuitlist_idx;
673  smartlist_del(lst, idx);
674  if (idx < smartlist_len(lst)) {
675  circuit_t *replacement = smartlist_get(lst, idx);
676  replacement->global_circuitlist_idx = idx;
677  }
678  circ->global_circuitlist_idx = -1;
679 
680  /* Remove it from the origin circuit list, if appropriate. */
681  if (CIRCUIT_IS_ORIGIN(circ)) {
683  }
684 
685  circuit_about_to_free(circ);
686  circuit_free(circ);
687  } SMARTLIST_FOREACH_END(circ);
688 
690 }
691 
692 /** Return a pointer to the global list of circuits. */
695 {
696  if (NULL == global_circuitlist)
698  return global_circuitlist;
699 }
700 
701 /** Return a pointer to the global list of origin circuits. */
702 smartlist_t *
704 {
705  if (NULL == global_origin_circuit_list)
708 }
709 
710 /**
711  * Return true if we have any opened general-purpose 3 hop
712  * origin circuits.
713  *
714  * The result from this function is cached for use by
715  * circuit_any_opened_circuits_cached().
716  */
717 int
719 {
721  const origin_circuit_t *, next_circ) {
722  if (!TO_CIRCUIT(next_circ)->marked_for_close &&
723  next_circ->has_opened &&
724  TO_CIRCUIT(next_circ)->state == CIRCUIT_STATE_OPEN &&
725  TO_CIRCUIT(next_circ)->purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT &&
726  next_circ->build_state &&
727  next_circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN) {
729  return 1;
730  }
731  } SMARTLIST_FOREACH_END(next_circ);
732 
734  return 0;
735 }
736 
737 /**
738  * Cache the "any circuits opened" state, as specified in param
739  * circuits_are_opened. This is a helper function to update
740  * the circuit opened status whenever we happen to look at the
741  * circuit list.
742  */
743 void
744 circuit_cache_opened_circuit_state(int circuits_are_opened)
745 {
746  any_opened_circs_cached_val = circuits_are_opened;
747 }
748 
749 /**
750  * Return true if there were any opened circuits since the last call to
751  * circuit_any_opened_circuits(), or since circuit_expire_building() last
752  * ran (it runs roughly once per second).
753  */
754 int
756 {
758 }
759 
760 /** Function to make circ->state human-readable */
761 const char *
763 {
764  static char buf[64];
765  switch (state) {
766  case CIRCUIT_STATE_BUILDING: return "doing handshakes";
767  case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
768  case CIRCUIT_STATE_CHAN_WAIT: return "connecting to server";
769  case CIRCUIT_STATE_GUARD_WAIT: return "waiting to see how other "
770  "guards perform";
771  case CIRCUIT_STATE_OPEN: return "open";
772  default:
773  log_warn(LD_BUG, "Unknown circuit state %d", state);
774  tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
775  return buf;
776  }
777 }
778 
779 /** Map a circuit purpose to a string suitable to be displayed to a
780  * controller. */
781 const char *
783 {
784  static char buf[32];
785  switch (purpose) {
786  case CIRCUIT_PURPOSE_OR:
790  return "SERVER"; /* A controller should never see these, actually. */
791 
793  return "GENERAL";
794 
796  return "HS_CLIENT_HSDIR";
797 
801  return "HS_CLIENT_INTRO";
802 
807  return "HS_CLIENT_REND";
808 
810  return "HS_SERVICE_HSDIR";
811 
814  return "HS_SERVICE_INTRO";
815 
818  return "HS_SERVICE_REND";
819 
821  return "TESTING";
823  return "MEASURE_TIMEOUT";
825  return "CONTROLLER";
827  return "PATH_BIAS_TESTING";
829  return "HS_VANGUARDS";
831  return "CIRCUIT_PADDING";
832 
833  default:
834  tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
835  return buf;
836  }
837 }
838 
839 /** Return a string specifying the state of the hidden-service circuit
840  * purpose <b>purpose</b>, or NULL if <b>purpose</b> is not a
841  * hidden-service-related circuit purpose. */
842 const char *
844 {
845  switch (purpose)
846  {
847  default:
849  "Unrecognized circuit purpose: %d",
850  (int)purpose);
853 
854  case CIRCUIT_PURPOSE_OR:
862  return NULL;
863 
865  return "OR_HSSI_ESTABLISHED";
867  return "OR_HSCR_ESTABLISHED";
869  return "OR_HS_R_JOINED";
870 
873  return "HSCI_CONNECTING";
875  return "HSCI_INTRO_SENT";
877  return "HSCI_DONE";
878 
880  return "HSCR_CONNECTING";
882  return "HSCR_ESTABLISHED_IDLE";
884  return "HSCR_ESTABLISHED_WAITING";
886  return "HSCR_JOINED";
887 
890  return "HSSI_CONNECTING";
892  return "HSSI_ESTABLISHED";
893 
895  return "HSSR_CONNECTING";
897  return "HSSR_JOINED";
898  }
899 }
900 
901 /** Return a human-readable string for the circuit purpose <b>purpose</b>. */
902 const char *
904 {
905  static char buf[32];
906 
907  switch (purpose)
908  {
909  case CIRCUIT_PURPOSE_OR:
910  return "Circuit at relay";
912  return "Acting as intro point";
914  return "Acting as rendezvous (pending)";
916  return "Acting as rendezvous (established)";
918  return "General-purpose client";
920  return "Hidden service client: Connecting to intro point";
922  return "Hidden service client: Waiting for ack from intro point";
924  return "Hidden service client: Received ack from intro point";
926  return "Hidden service client: Establishing rendezvous point";
928  return "Hidden service client: Pending rendezvous point";
930  return "Hidden service client: Pending rendezvous point (ack received)";
932  return "Hidden service client: Active rendezvous point";
934  return "Hidden service client: Fetching HS descriptor";
935 
937  return "Measuring circuit timeout";
938 
940  return "Hidden service: Establishing introduction point";
942  return "Hidden service: Introduction point";
944  return "Hidden service: Connecting to rendezvous point";
946  return "Hidden service: Active rendezvous point";
948  return "Hidden service: Uploading HS descriptor";
949 
951  return "Testing circuit";
952 
954  return "Circuit made by controller";
955 
957  return "Path-bias testing circuit";
958 
960  return "Hidden service: Pre-built vanguard circuit";
961 
963  return "Circuit kept open for padding";
964 
965  default:
966  tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
967  return buf;
968  }
969 }
970 
971 /** Pick a reasonable package_window to start out for our circuits.
972  * Originally this was hard-coded at 1000, but now the consensus votes
973  * on the answer. See proposal 168. */
974 int32_t
976 {
977  int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
978  CIRCWINDOW_START_MIN,
979  CIRCWINDOW_START_MAX);
980  /* If the consensus tells us a negative number, we'd assert. */
981  if (num < 0)
982  num = CIRCWINDOW_START;
983  return num;
984 }
985 
986 /** Initialize the common elements in a circuit_t, and add it to the global
987  * list. */
988 static void
990 {
992 
993  // Gets reset when we send CREATE_FAST.
994  // circuit_expire_building() expects these to be equal
995  // until the orconn is built.
996  circ->timestamp_began = circ->timestamp_created;
997 
1001  cell_queue_init(&circ->n_chan_cells);
1002 
1004  circ->global_circuitlist_idx = smartlist_len(circuit_get_global_list()) - 1;
1005 }
1006 
1007 /** If we haven't yet decided on a good timeout value for circuit
1008  * building, we close idle circuits aggressively so we can get more
1009  * data points. These are the default, min, and max consensus values */
1010 #define DFLT_IDLE_TIMEOUT_WHILE_LEARNING (3*60)
1011 #define MIN_IDLE_TIMEOUT_WHILE_LEARNING (10)
1012 #define MAX_IDLE_TIMEOUT_WHILE_LEARNING (1000*60)
1013 
1014 /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
1015  * and <b>p_conn</b>. Add it to the global circuit list.
1016  */
1019 {
1020  origin_circuit_t *circ;
1021  /* never zero, since a global ID of 0 is treated specially by the
1022  * controller */
1023  static uint32_t n_circuits_allocated = 1;
1024 
1025  circ = tor_malloc_zero(sizeof(origin_circuit_t));
1026  circ->base_.magic = ORIGIN_CIRCUIT_MAGIC;
1027 
1028  circ->next_stream_id = crypto_rand_int(1<<16);
1029  circ->global_identifier = n_circuits_allocated++;
1032 
1034 
1035  /* Add to origin-list. */
1036  circ->global_origin_circuit_list_idx = -1;
1038 
1039  circuit_build_times_update_last_circ(get_circuit_build_times_mutable());
1040 
1043  /* Circuits should be shorter lived if we need more of them
1044  * for learning a good build timeout */
1045  circ->circuit_idle_timeout =
1046  networkstatus_get_param(NULL, "cbtlearntimeout",
1048  MIN_IDLE_TIMEOUT_WHILE_LEARNING,
1049  MAX_IDLE_TIMEOUT_WHILE_LEARNING);
1050  } else {
1051  // This should always be larger than the current port prediction time
1052  // remaining, or else we'll end up with the case where a circuit times out
1053  // and another one is built, effectively doubling the timeout window.
1054  //
1055  // We also randomize it by up to 5% more (ie 5% of 0 to 3600 seconds,
1056  // depending on how much circuit prediction time is remaining) so that
1057  // we don't close a bunch of unused circuits all at the same time.
1058  int prediction_time_remaining =
1060  circ->circuit_idle_timeout = prediction_time_remaining+1+
1061  crypto_rand_int(1+prediction_time_remaining/20);
1062 
1063  if (circ->circuit_idle_timeout <= 0) {
1064  log_warn(LD_BUG,
1065  "Circuit chose a negative idle timeout of %d based on "
1066  "%d seconds of predictive building remaining.",
1067  circ->circuit_idle_timeout,
1068  prediction_time_remaining);
1069  circ->circuit_idle_timeout =
1070  networkstatus_get_param(NULL, "cbtlearntimeout",
1072  MIN_IDLE_TIMEOUT_WHILE_LEARNING,
1073  MAX_IDLE_TIMEOUT_WHILE_LEARNING);
1074  }
1075 
1076  log_info(LD_CIRC,
1077  "Circuit %"PRIu32" chose an idle timeout of %d based on "
1078  "%d seconds of predictive building remaining.",
1079  (circ->global_identifier),
1080  circ->circuit_idle_timeout,
1081  prediction_time_remaining);
1082  }
1083 
1084  tor_trace(TR_SUBSYS(circuit), TR_EV(new_origin), circ);
1085  return circ;
1086 }
1087 
1088 /** Allocate a new or_circuit_t, connected to <b>p_chan</b> as
1089  * <b>p_circ_id</b>. If <b>p_chan</b> is NULL, the circuit is unattached. */
1090 or_circuit_t *
1091 or_circuit_new(circid_t p_circ_id, channel_t *p_chan)
1092 {
1093  /* CircIDs */
1094  or_circuit_t *circ;
1095 
1096  circ = tor_malloc_zero(sizeof(or_circuit_t));
1097  circ->base_.magic = OR_CIRCUIT_MAGIC;
1098 
1099  if (p_chan)
1100  circuit_set_p_circid_chan(circ, p_circ_id, p_chan);
1101 
1103  cell_queue_init(&circ->p_chan_cells);
1104 
1106 
1107  tor_trace(TR_SUBSYS(circuit), TR_EV(new_or), circ);
1108  return circ;
1109 }
1110 
1111 /** Free all storage held in circ->testing_cell_stats */
1112 void
1114 {
1115  if (!circ || !circ->testing_cell_stats)
1116  return;
1118  ent, tor_free(ent));
1119  smartlist_free(circ->testing_cell_stats);
1120  circ->testing_cell_stats = NULL;
1121 }
1122 
1123 /** Deallocate space associated with circ.
1124  */
1125 STATIC void
1127 {
1128  circid_t n_circ_id = 0;
1129  void *mem;
1130  size_t memlen;
1131  int should_free = 1;
1132  if (!circ)
1133  return;
1134 
1135  /* We keep a copy of this so we can log its value before it gets unset. */
1136  n_circ_id = circ->n_circ_id;
1137 
1139 
1140  /* Cleanup circuit from anything HS v3 related. We also do this when the
1141  * circuit is closed. This is to avoid any code path that free registered
1142  * circuits without closing them before. This needs to be done before the
1143  * hs identifier is freed. */
1145 
1146  if (CIRCUIT_IS_ORIGIN(circ)) {
1147  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
1148  mem = ocirc;
1149  memlen = sizeof(origin_circuit_t);
1151 
1153 
1154  if (ocirc->half_streams) {
1156  half_conn) {
1157  half_edge_free(half_conn);
1158  } SMARTLIST_FOREACH_END(half_conn);
1159  smartlist_free(ocirc->half_streams);
1160  }
1161 
1162  if (ocirc->build_state) {
1163  extend_info_free(ocirc->build_state->chosen_exit);
1164  }
1165  tor_free(ocirc->build_state);
1166 
1167  /* Cancel before freeing, if we haven't already succeeded or failed. */
1168  if (ocirc->guard_state) {
1170  }
1171  circuit_guard_state_free(ocirc->guard_state);
1172 
1173  circuit_clear_cpath(ocirc);
1174 
1175  crypto_pk_free(ocirc->intro_key);
1176 
1177  /* Finally, free the identifier of the circuit and nullify it so multiple
1178  * cleanup will work. */
1179  hs_ident_circuit_free(ocirc->hs_ident);
1180  ocirc->hs_ident = NULL;
1181 
1182  tor_free(ocirc->dest_address);
1183  if (ocirc->socks_username) {
1184  memwipe(ocirc->socks_username, 0x12, ocirc->socks_username_len);
1185  tor_free(ocirc->socks_username);
1186  }
1187  if (ocirc->socks_password) {
1188  memwipe(ocirc->socks_password, 0x06, ocirc->socks_password_len);
1189  tor_free(ocirc->socks_password);
1190  }
1191  addr_policy_list_free(ocirc->prepend_policy);
1192  } else {
1193  or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
1194  /* Remember cell statistics for this circuit before deallocating. */
1195  if (get_options()->CellStatistics)
1196  rep_hist_buffer_stats_add_circ(circ, time(NULL));
1197  mem = ocirc;
1198  memlen = sizeof(or_circuit_t);
1199  tor_assert(circ->magic == OR_CIRCUIT_MAGIC);
1200 
1201  should_free = (ocirc->workqueue_entry == NULL);
1202 
1203  relay_crypto_clear(&ocirc->crypto);
1204 
1205  if (ocirc->rend_splice) {
1206  or_circuit_t *other = ocirc->rend_splice;
1207  tor_assert(other->base_.magic == OR_CIRCUIT_MAGIC);
1208  other->rend_splice = NULL;
1209  }
1210 
1211  /* remove from map. */
1212  circuit_set_p_circid_chan(ocirc, 0, NULL);
1213 
1214  /* Clear cell queue _after_ removing it from the map. Otherwise our
1215  * "active" checks will be violated. */
1216  cell_queue_clear(&ocirc->p_chan_cells);
1217  }
1218 
1219  extend_info_free(circ->n_hop);
1221 
1222  if (circ->global_circuitlist_idx != -1) {
1223  int idx = circ->global_circuitlist_idx;
1224  circuit_t *c2 = smartlist_get(global_circuitlist, idx);
1225  tor_assert(c2 == circ);
1227  if (idx < smartlist_len(global_circuitlist)) {
1228  c2 = smartlist_get(global_circuitlist, idx);
1229  c2->global_circuitlist_idx = idx;
1230  }
1231  }
1232 
1233  /* Remove from map. */
1234  circuit_set_n_circid_chan(circ, 0, NULL);
1235 
1236  /* Clear cell queue _after_ removing it from the map. Otherwise our
1237  * "active" checks will be violated. */
1239 
1240  /* Cleanup possible SENDME state. */
1241  if (circ->sendme_last_digests) {
1242  SMARTLIST_FOREACH(circ->sendme_last_digests, uint8_t *, d, tor_free(d));
1243  smartlist_free(circ->sendme_last_digests);
1244  }
1245 
1246  log_info(LD_CIRC, "Circuit %u (id: %" PRIu32 ") has been freed.",
1247  n_circ_id,
1248  CIRCUIT_IS_ORIGIN(circ) ?
1249  TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0);
1250 
1251  /* Free any circuit padding structures */
1253 
1254  /* Clear all dangling handle references. */
1255  circuit_handles_clear(circ);
1256 
1257  /* Tracepoint. Data within the circuit object is recorded so do this before
1258  * the actual memory free. */
1259  tor_trace(TR_SUBSYS(circuit), TR_EV(free), circ);
1260 
1261  if (should_free) {
1262  memwipe(mem, 0xAA, memlen); /* poison memory */
1263  tor_free(mem);
1264  } else {
1265  /* If we made it here, this is an or_circuit_t that still has a pending
1266  * cpuworker request which we weren't able to cancel. Instead, set up
1267  * the magic value so that when the reply comes back, we'll know to discard
1268  * the reply and free this structure.
1269  */
1270  memwipe(mem, 0xAA, memlen);
1271  circ->magic = DEAD_CIRCUIT_MAGIC;
1272  }
1273 }
1274 
1275 /** Deallocate the linked list circ-><b>cpath</b>, and remove the cpath from
1276  * <b>circ</b>. */
1277 void
1279 {
1280  crypt_path_t *victim, *head, *cpath;
1281 
1282  head = cpath = circ->cpath;
1283 
1284  if (!cpath)
1285  return;
1286 
1287  /* it's a circular list, so we have to notice when we've
1288  * gone through it once. */
1289  while (cpath->next && cpath->next != head) {
1290  victim = cpath;
1291  cpath = victim->next;
1292  cpath_free(victim);
1293  }
1294 
1295  cpath_free(cpath);
1296 
1297  circ->cpath = NULL;
1298 }
1299 
1300 /** Release all storage held by circuits. */
1301 void
1303 {
1305 
1306  SMARTLIST_FOREACH_BEGIN(lst, circuit_t *, tmp) {
1307  if (! CIRCUIT_IS_ORIGIN(tmp)) {
1308  or_circuit_t *or_circ = TO_OR_CIRCUIT(tmp);
1309  while (or_circ->resolving_streams) {
1310  edge_connection_t *next_conn;
1311  next_conn = or_circ->resolving_streams->next_stream;
1313  or_circ->resolving_streams = next_conn;
1314  }
1315  }
1316  tmp->global_circuitlist_idx = -1;
1318  circuit_free(tmp);
1319  SMARTLIST_DEL_CURRENT(lst, tmp);
1320  } SMARTLIST_FOREACH_END(tmp);
1321 
1322  smartlist_free(lst);
1323  global_circuitlist = NULL;
1324 
1325  smartlist_free(global_origin_circuit_list);
1327 
1328  smartlist_free(circuits_pending_chans);
1329  circuits_pending_chans = NULL;
1330 
1331  smartlist_free(circuits_pending_close);
1332  circuits_pending_close = NULL;
1333 
1334  smartlist_free(circuits_pending_other_guards);
1336 
1337  {
1338  chan_circid_circuit_map_t **elt, **next, *c;
1339  for (elt = HT_START(chan_circid_map, &chan_circid_map);
1340  elt;
1341  elt = next) {
1342  c = *elt;
1343  next = HT_NEXT_RMV(chan_circid_map, &chan_circid_map, elt);
1344 
1345  tor_assert(c->circuit == NULL);
1346  tor_free(c);
1347  }
1348  }
1349  HT_CLEAR(chan_circid_map, &chan_circid_map);
1350 }
1351 
1352 /** A helper function for circuit_dump_by_conn() below. Log a bunch
1353  * of information about circuit <b>circ</b>.
1354  */
1355 static void
1357  circuit_t *circ,
1358  int conn_array_index,
1359  const char *type,
1360  circid_t this_circid,
1361  circid_t other_circid)
1362 {
1363  tor_log(severity, LD_CIRC, "Conn %d has %s circuit: circID %u "
1364  "(other side %u), state %d (%s), born %ld:",
1365  conn_array_index, type, (unsigned)this_circid, (unsigned)other_circid,
1366  circ->state, circuit_state_to_string(circ->state),
1367  (long)circ->timestamp_began.tv_sec);
1368  if (CIRCUIT_IS_ORIGIN(circ)) { /* circ starts at this node */
1369  circuit_log_path(severity, LD_CIRC, TO_ORIGIN_CIRCUIT(circ));
1370  }
1371 }
1372 
1373 /** Log, at severity <b>severity</b>, information about each circuit
1374  * that is connected to <b>conn</b>.
1375  */
1376 void
1378 {
1379  edge_connection_t *tmpconn;
1380 
1382  circid_t n_circ_id = circ->n_circ_id, p_circ_id = 0;
1383 
1384  if (circ->marked_for_close) {
1385  continue;
1386  }
1387 
1388  if (!CIRCUIT_IS_ORIGIN(circ)) {
1389  p_circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
1390  }
1391 
1392  if (CIRCUIT_IS_ORIGIN(circ)) {
1393  for (tmpconn=TO_ORIGIN_CIRCUIT(circ)->p_streams; tmpconn;
1394  tmpconn=tmpconn->next_stream) {
1395  if (TO_CONN(tmpconn) == conn) {
1396  circuit_dump_conn_details(severity, circ, conn->conn_array_index,
1397  "App-ward", p_circ_id, n_circ_id);
1398  }
1399  }
1400  }
1401 
1402  if (! CIRCUIT_IS_ORIGIN(circ)) {
1403  for (tmpconn=TO_OR_CIRCUIT(circ)->n_streams; tmpconn;
1404  tmpconn=tmpconn->next_stream) {
1405  if (TO_CONN(tmpconn) == conn) {
1406  circuit_dump_conn_details(severity, circ, conn->conn_array_index,
1407  "Exit-ward", n_circ_id, p_circ_id);
1408  }
1409  }
1410  }
1411  }
1412  SMARTLIST_FOREACH_END(circ);
1413 }
1414 
1415 /** Return the circuit whose global ID is <b>id</b>, or NULL if no
1416  * such circuit exists. */
1419 {
1421  if (CIRCUIT_IS_ORIGIN(circ) &&
1422  TO_ORIGIN_CIRCUIT(circ)->global_identifier == id) {
1423  if (circ->marked_for_close)
1424  return NULL;
1425  else
1426  return TO_ORIGIN_CIRCUIT(circ);
1427  }
1428  }
1429  SMARTLIST_FOREACH_END(circ);
1430  return NULL;
1431 }
1432 
1433 /** Return a circ such that:
1434  * - circ->n_circ_id or circ->p_circ_id is equal to <b>circ_id</b>, and
1435  * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
1436  * Return NULL if no such circuit exists.
1437  *
1438  * If <b>found_entry_out</b> is provided, set it to true if we have a
1439  * placeholder entry for circid/chan, and leave it unset otherwise.
1440  */
1441 static inline circuit_t *
1443  int *found_entry_out)
1444 {
1447 
1448  if (_last_circid_chan_ent &&
1449  circ_id == _last_circid_chan_ent->circ_id &&
1450  chan == _last_circid_chan_ent->chan) {
1451  found = _last_circid_chan_ent;
1452  } else {
1453  search.circ_id = circ_id;
1454  search.chan = chan;
1455  found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
1456  _last_circid_chan_ent = found;
1457  }
1458  if (found && found->circuit) {
1459  log_debug(LD_CIRC,
1460  "circuit_get_by_circid_channel_impl() returning circuit %p for"
1461  " circ_id %u, channel ID %"PRIu64 " (%p)",
1462  found->circuit, (unsigned)circ_id,
1463  (chan->global_identifier), chan);
1464  if (found_entry_out)
1465  *found_entry_out = 1;
1466  return found->circuit;
1467  }
1468 
1469  log_debug(LD_CIRC,
1470  "circuit_get_by_circid_channel_impl() found %s for"
1471  " circ_id %u, channel ID %"PRIu64 " (%p)",
1472  found ? "placeholder" : "nothing",
1473  (unsigned)circ_id,
1474  (chan->global_identifier), chan);
1475 
1476  if (found_entry_out)
1477  *found_entry_out = found ? 1 : 0;
1478 
1479  return NULL;
1480  /* The rest of this checks for bugs. Disabled by default. */
1481  /* We comment it out because coverity complains otherwise.
1482  {
1483  circuit_t *circ;
1484  TOR_LIST_FOREACH(circ, &global_circuitlist, head) {
1485  if (! CIRCUIT_IS_ORIGIN(circ)) {
1486  or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
1487  if (or_circ->p_chan == chan && or_circ->p_circ_id == circ_id) {
1488  log_warn(LD_BUG,
1489  "circuit matches p_chan, but not in hash table (Bug!)");
1490  return circ;
1491  }
1492  }
1493  if (circ->n_chan == chan && circ->n_circ_id == circ_id) {
1494  log_warn(LD_BUG,
1495  "circuit matches n_chan, but not in hash table (Bug!)");
1496  return circ;
1497  }
1498  }
1499  return NULL;
1500  } */
1501 }
1502 
1503 /** Return a circ such that:
1504  * - circ->n_circ_id or circ->p_circ_id is equal to <b>circ_id</b>, and
1505  * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
1506  * - circ is not marked for close.
1507  * Return NULL if no such circuit exists.
1508  */
1509 circuit_t *
1511 {
1512  circuit_t *circ = circuit_get_by_circid_channel_impl(circ_id, chan, NULL);
1513  if (!circ || circ->marked_for_close)
1514  return NULL;
1515  else
1516  return circ;
1517 }
1518 
1519 /** Return a circ such that:
1520  * - circ->n_circ_id or circ->p_circ_id is equal to <b>circ_id</b>, and
1521  * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
1522  * Return NULL if no such circuit exists.
1523  */
1524 circuit_t *
1526  channel_t *chan)
1527 {
1528  return circuit_get_by_circid_channel_impl(circ_id, chan, NULL);
1529 }
1530 
1531 /** Return true iff the circuit ID <b>circ_id</b> is currently used by a
1532  * circuit, marked or not, on <b>chan</b>, or if the circ ID is reserved until
1533  * a queued destroy cell can be sent.
1534  *
1535  * (Return 1 if the circuit is present, marked or not; Return 2
1536  * if the circuit ID is pending a destroy.)
1537  **/
1538 int
1540 {
1541  int found = 0;
1542  if (circuit_get_by_circid_channel_impl(circ_id, chan, &found) != NULL)
1543  return 1;
1544  if (found)
1545  return 2;
1546  return 0;
1547 }
1548 
1549 /** Helper for debugging 12184. Returns the time since which 'circ_id' has
1550  * been marked unusable on 'chan'. */
1551 time_t
1553 {
1556 
1557  memset(&search, 0, sizeof(search));
1558  search.circ_id = circ_id;
1559  search.chan = chan;
1560 
1561  found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
1562 
1563  if (! found || found->circuit)
1564  return 0;
1565 
1566  return found->made_placeholder_at;
1567 }
1568 
1569 /** Return the circuit that a given edge connection is using. */
1570 circuit_t *
1572 {
1573  circuit_t *circ;
1574 
1575  circ = conn->on_circuit;
1576  tor_assert(!circ ||
1577  (CIRCUIT_IS_ORIGIN(circ) ? circ->magic == ORIGIN_CIRCUIT_MAGIC
1578  : circ->magic == OR_CIRCUIT_MAGIC));
1579 
1580  return circ;
1581 }
1582 
1583 /** For each circuit that has <b>chan</b> as n_chan or p_chan, unlink the
1584  * circuit from the chan,circid map, and mark it for close if it hasn't
1585  * been marked already.
1586  */
1587 void
1589 {
1590  smartlist_t *detached = smartlist_new();
1591 
1592 /* #define DEBUG_CIRCUIT_UNLINK_ALL */
1593 
1594  channel_unlink_all_circuits(chan, detached);
1595 
1596 #ifdef DEBUG_CIRCUIT_UNLINK_ALL
1597  {
1598  smartlist_t *detached_2 = smartlist_new();
1599  int mismatch = 0, badlen = 0;
1600 
1602  if (circ->n_chan == chan ||
1603  (!CIRCUIT_IS_ORIGIN(circ) &&
1604  TO_OR_CIRCUIT(circ)->p_chan == chan)) {
1605  smartlist_add(detached_2, circ);
1606  }
1607  }
1608  SMARTLIST_FOREACH_END(circ);
1609 
1610  if (smartlist_len(detached) != smartlist_len(detached_2)) {
1611  log_warn(LD_BUG, "List of detached circuits had the wrong length! "
1612  "(got %d, should have gotten %d)",
1613  (int)smartlist_len(detached),
1614  (int)smartlist_len(detached_2));
1615  badlen = 1;
1616  }
1617  smartlist_sort_pointers(detached);
1618  smartlist_sort_pointers(detached_2);
1619 
1620  SMARTLIST_FOREACH(detached, circuit_t *, c,
1621  if (c != smartlist_get(detached_2, c_sl_idx))
1622  mismatch = 1;
1623  );
1624 
1625  if (mismatch)
1626  log_warn(LD_BUG, "Mismatch in list of detached circuits.");
1627 
1628  if (badlen || mismatch) {
1629  smartlist_free(detached);
1630  detached = detached_2;
1631  } else {
1632  log_notice(LD_CIRC, "List of %d circuits was as expected.",
1633  (int)smartlist_len(detached));
1634  smartlist_free(detached_2);
1635  }
1636  }
1637 #endif /* defined(DEBUG_CIRCUIT_UNLINK_ALL) */
1638 
1639  SMARTLIST_FOREACH_BEGIN(detached, circuit_t *, circ) {
1640  int mark = 0;
1641  if (circ->n_chan == chan) {
1642 
1643  circuit_set_n_circid_chan(circ, 0, NULL);
1644  mark = 1;
1645 
1646  /* If we didn't request this closure, pass the remote
1647  * bit to mark_for_close. */
1648  if (chan->reason_for_closing != CHANNEL_CLOSE_REQUESTED)
1649  reason |= END_CIRC_REASON_FLAG_REMOTE;
1650  }
1651  if (! CIRCUIT_IS_ORIGIN(circ)) {
1652  or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
1653  if (or_circ->p_chan == chan) {
1654  circuit_set_p_circid_chan(or_circ, 0, NULL);
1655  mark = 1;
1656  }
1657  }
1658  if (!mark) {
1659  log_warn(LD_BUG, "Circuit on detached list which I had no reason "
1660  "to mark");
1661  continue;
1662  }
1663  if (!circ->marked_for_close)
1664  circuit_mark_for_close(circ, reason);
1665  } SMARTLIST_FOREACH_END(circ);
1666 
1667  smartlist_free(detached);
1668 }
1669 
1670 /** Return the first introduction circuit originating from the global circuit
1671  * list after <b>start</b> or at the start of the list if <b>start</b> is
1672  * NULL. Return NULL if no circuit is found.
1673  *
1674  * If <b>want_client_circ</b> is true, then we are looking for client-side
1675  * introduction circuits: A client introduction point circuit has a purpose of
1676  * either CIRCUIT_PURPOSE_C_INTRODUCING, CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
1677  * or CIRCUIT_PURPOSE_C_INTRODUCE_ACKED. This does not return a circuit marked
1678  * for close, but it returns circuits regardless of their circuit state.
1679  *
1680  * If <b>want_client_circ</b> is false, then we are looking for service-side
1681  * introduction circuits: A service introduction point circuit has a purpose of
1682  * either CIRCUIT_PURPOSE_S_ESTABLISH_INTRO or CIRCUIT_PURPOSE_S_INTRO. This
1683  * does not return circuits marked for close, or in any state other than open.
1684  */
1687  bool want_client_circ)
1688 {
1689  int idx = 0;
1691 
1692  if (start) {
1693  idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1;
1694  }
1695 
1696  for ( ; idx < smartlist_len(lst); ++idx) {
1697  circuit_t *circ = smartlist_get(lst, idx);
1698 
1699  /* Ignore a marked for close circuit or if the state is not open. */
1700  if (circ->marked_for_close) {
1701  continue;
1702  }
1703 
1704  /* Depending on whether we are looking for client or service circs, skip
1705  * circuits with other purposes. */
1706  if (want_client_circ) {
1707  if (circ->purpose != CIRCUIT_PURPOSE_C_INTRODUCING &&
1710  continue;
1711  }
1712  } else { /* we are looking for service-side circs */
1713  if (circ->state != CIRCUIT_STATE_OPEN) {
1714  continue;
1715  }
1717  circ->purpose != CIRCUIT_PURPOSE_S_INTRO) {
1718  continue;
1719  }
1720  }
1721 
1722  /* The purposes we are looking for are only for origin circuits so the
1723  * following is valid. */
1724  return TO_ORIGIN_CIRCUIT(circ);
1725  }
1726  /* Not found. */
1727  return NULL;
1728 }
1729 
1730 /** Return the first service rendezvous circuit originating from the global
1731  * circuit list after <b>start</b> or at the start of the list if <b>start</b>
1732  * is NULL. Return NULL if no circuit is found.
1733  *
1734  * A service rendezvous point circuit has a purpose of either
1735  * CIRCUIT_PURPOSE_S_CONNECT_REND or CIRCUIT_PURPOSE_S_REND_JOINED. This does
1736  * not return a circuit marked for close and its state must be open. */
1739 {
1740  int idx = 0;
1742 
1743  if (start) {
1744  idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1;
1745  }
1746 
1747  for ( ; idx < smartlist_len(lst); ++idx) {
1748  circuit_t *circ = smartlist_get(lst, idx);
1749 
1750  /* Ignore a marked for close circuit or purpose not matching a service
1751  * intro point or if the state is not open. */
1752  if (circ->marked_for_close || circ->state != CIRCUIT_STATE_OPEN ||
1755  continue;
1756  }
1757  /* The purposes we are looking for are only for origin circuits so the
1758  * following is valid. */
1759  return TO_ORIGIN_CIRCUIT(circ);
1760  }
1761  /* Not found. */
1762  return NULL;
1763 }
1764 
1765 /** Return the first circuit originating here in global_circuitlist after
1766  * <b>start</b> whose purpose is <b>purpose</b>. Return NULL if no circuit is
1767  * found. If <b>start</b> is NULL, begin at the start of the list. */
1770 {
1771  int idx;
1774  if (start == NULL)
1775  idx = 0;
1776  else
1777  idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1;
1778 
1779  for ( ; idx < smartlist_len(lst); ++idx) {
1780  circuit_t *circ = smartlist_get(lst, idx);
1781 
1782  if (circ->marked_for_close)
1783  continue;
1784  if (circ->purpose != purpose)
1785  continue;
1786  /* At this point we should be able to get a valid origin circuit because
1787  * the origin purpose we are looking for matches this circuit. */
1788  if (BUG(!CIRCUIT_PURPOSE_IS_ORIGIN(circ->purpose))) {
1789  break;
1790  }
1791  return TO_ORIGIN_CIRCUIT(circ);
1792  }
1793  return NULL;
1794 }
1795 
1796 /** We might cannibalize this circuit: Return true if its last hop can be used
1797  * as a v3 rendezvous point. */
1798 static int
1800 {
1801  if (!circ->build_state) {
1802  return 0;
1803  }
1804 
1805  extend_info_t *chosen_exit = circ->build_state->chosen_exit;
1806  if (BUG(!chosen_exit)) {
1807  return 0;
1808  }
1809 
1810  const node_t *rp_node = node_get_by_id(chosen_exit->identity_digest);
1811  if (rp_node) {
1812  if (node_supports_v3_rendezvous_point(rp_node)) {
1813  return 1;
1814  }
1815  }
1816 
1817  return 0;
1818 }
1819 
1820 /** We are trying to create a circuit of purpose <b>purpose</b> and we are
1821  * looking for cannibalizable circuits. Return the circuit purpose we would be
1822  * willing to cannibalize. */
1823 static uint8_t
1825 {
1826  if (circuit_should_use_vanguards(purpose)) {
1827  /* If we are using vanguards, then we should only cannibalize vanguard
1828  * circuits so that we get the same path construction logic. */
1830  } else {
1831  /* If no vanguards are used just get a general circuit! */
1833  }
1834 }
1835 
1836 /** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL,
1837  * has a timestamp_dirty value of 0, has flags matching the CIRCLAUNCH_*
1838  * flags in <b>flags</b>, and if info is defined, does not already use info
1839  * as any of its hops; or NULL if no circuit fits this description.
1840  *
1841  * The <b>purpose</b> argument refers to the purpose of the circuit we want to
1842  * create, not the purpose of the circuit we want to cannibalize.
1843  *
1844  * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits.
1845  *
1846  * To "cannibalize" a circuit means to extend it an extra hop, and use it
1847  * for some other purpose than we had originally intended. We do this when
1848  * we want to perform some low-bandwidth task at a specific relay, and we
1849  * would like the circuit to complete as soon as possible. (If we were going
1850  * to use a lot of bandwidth, we wouldn't want a circuit with an extra hop.
1851  * If we didn't care about circuit completion latency, we would just build
1852  * a new circuit.)
1853  */
1855 circuit_find_to_cannibalize(uint8_t purpose_to_produce, extend_info_t *info,
1856  int flags)
1857 {
1858  origin_circuit_t *best=NULL;
1859  int need_uptime = (flags & CIRCLAUNCH_NEED_UPTIME) != 0;
1860  int need_capacity = (flags & CIRCLAUNCH_NEED_CAPACITY) != 0;
1861  int internal = (flags & CIRCLAUNCH_IS_INTERNAL) != 0;
1862  const or_options_t *options = get_options();
1863  /* We want the circuit we are trying to cannibalize to have this purpose */
1864  int purpose_to_search_for;
1865 
1866  /* Make sure we're not trying to create a onehop circ by
1867  * cannibalization. */
1869 
1870  purpose_to_search_for = get_circuit_purpose_needed_to_cannibalize(
1871  purpose_to_produce);
1872 
1873  tor_assert_nonfatal(purpose_to_search_for == CIRCUIT_PURPOSE_C_GENERAL ||
1874  purpose_to_search_for == CIRCUIT_PURPOSE_HS_VANGUARDS);
1875 
1876  log_debug(LD_CIRC,
1877  "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
1878  "capacity %d, internal %d",
1879  purpose_to_produce, need_uptime, need_capacity, internal);
1880 
1882  if (CIRCUIT_IS_ORIGIN(circ_) &&
1883  circ_->state == CIRCUIT_STATE_OPEN &&
1884  !circ_->marked_for_close &&
1885  circ_->purpose == purpose_to_search_for &&
1886  !circ_->timestamp_dirty) {
1887  origin_circuit_t *circ = TO_ORIGIN_CIRCUIT(circ_);
1888 
1889  /* Only cannibalize from reasonable length circuits. If we
1890  * want C_GENERAL, then only choose 3 hop circs. If we want
1891  * HS_VANGUARDS, only choose 4 hop circs.
1892  */
1893  if (circ->build_state->desired_path_len !=
1894  route_len_for_purpose(purpose_to_search_for, NULL)) {
1895  goto next;
1896  }
1897 
1898  /* Ignore any circuits for which we can't use the Guard. It is possible
1899  * that the Guard was removed from the sampled set after the circuit
1900  * was created, so avoid using it. */
1901  if (!entry_guard_could_succeed(circ->guard_state)) {
1902  goto next;
1903  }
1904 
1905  if ((!need_uptime || circ->build_state->need_uptime) &&
1906  (!need_capacity || circ->build_state->need_capacity) &&
1907  (internal == circ->build_state->is_internal) &&
1908  !circ->unusable_for_new_conns &&
1910  !circ->build_state->onehop_tunnel &&
1911  !circ->isolation_values_set) {
1912  if (info) {
1913  /* need to make sure we don't duplicate hops */
1914  crypt_path_t *hop = circ->cpath;
1915  const node_t *ri1 = node_get_by_id(info->identity_digest);
1916  do {
1917  const node_t *ri2;
1919  info->identity_digest, DIGEST_LEN))
1920  goto next;
1921  if (ri1 &&
1923  && nodes_in_same_family(ri1, ri2))
1924  goto next;
1925  hop=hop->next;
1926  } while (hop!=circ->cpath);
1927  }
1928  if (options->ExcludeNodes) {
1929  /* Make sure no existing nodes in the circuit are excluded for
1930  * general use. (This may be possible if StrictNodes is 0, and we
1931  * thought we needed to use an otherwise excluded node for, say, a
1932  * directory operation.) */
1933  crypt_path_t *hop = circ->cpath;
1934  do {
1936  hop->extend_info))
1937  goto next;
1938  hop = hop->next;
1939  } while (hop != circ->cpath);
1940  }
1941 
1942  if ((flags & CIRCLAUNCH_IS_V3_RP) &&
1944  log_debug(LD_GENERAL, "Skipping uncannibalizable circuit for v3 "
1945  "rendezvous point.");
1946  goto next;
1947  }
1948 
1949  if (!best || (best->build_state->need_uptime && !need_uptime))
1950  best = circ;
1951  next: ;
1952  }
1953  }
1954  }
1955  SMARTLIST_FOREACH_END(circ_);
1956  return best;
1957 }
1958 
1959 /**
1960  * Check whether any of the origin circuits that are waiting to see if
1961  * their guard is good enough to use can be upgraded to "ready". If so,
1962  * return a new smartlist containing them. Otherwise return NULL.
1963  */
1964 smartlist_t *
1966 {
1967  /* Only if some circuit is actually waiting on an upgrade should we
1968  * run the algorithm. */
1970  smartlist_len(circuits_pending_other_guards)==0)
1971  return NULL;
1972  /* Only if we have some origin circuits should we run the algorithm. */
1974  return NULL;
1975 
1976  /* Okay; we can pass our circuit list to entrynodes.c.*/
1977  smartlist_t *result = smartlist_new();
1978  int circuits_upgraded = entry_guards_upgrade_waiting_circuits(
1981  result);
1982  if (circuits_upgraded && smartlist_len(result)) {
1983  return result;
1984  } else {
1985  smartlist_free(result);
1986  return NULL;
1987  }
1988 }
1989 
1990 /** Return the number of hops in circuit's path. If circ has no entries,
1991  * or is NULL, returns 0. */
1992 int
1994 {
1995  int n = 0;
1996  if (circ && circ->cpath) {
1997  crypt_path_t *cpath, *cpath_next = NULL;
1998  for (cpath = circ->cpath; cpath_next != circ->cpath; cpath = cpath_next) {
1999  cpath_next = cpath->next;
2000  ++n;
2001  }
2002  }
2003  return n;
2004 }
2005 
2006 /** Return the number of opened hops in circuit's path.
2007  * If circ has no entries, or is NULL, returns 0. */
2008 int
2010 {
2011  int n = 0;
2012  if (circ && circ->cpath) {
2013  crypt_path_t *cpath, *cpath_next = NULL;
2014  for (cpath = circ->cpath;
2015  cpath->state == CPATH_STATE_OPEN
2016  && cpath_next != circ->cpath;
2017  cpath = cpath_next) {
2018  cpath_next = cpath->next;
2019  ++n;
2020  }
2021  }
2022  return n;
2023 }
2024 
2025 /** Return the <b>hopnum</b>th hop in <b>circ</b>->cpath, or NULL if there
2026  * aren't that many hops in the list. <b>hopnum</b> starts at 1.
2027  * Returns NULL if <b>hopnum</b> is 0 or negative. */
2028 crypt_path_t *
2030 {
2031  if (circ && circ->cpath && hopnum > 0) {
2032  crypt_path_t *cpath, *cpath_next = NULL;
2033  for (cpath = circ->cpath; cpath_next != circ->cpath; cpath = cpath_next) {
2034  cpath_next = cpath->next;
2035  if (--hopnum <= 0)
2036  return cpath;
2037  }
2038  }
2039  return NULL;
2040 }
2041 
2042 /** Go through the circuitlist; mark-for-close each circuit that starts
2043  * at us but has not yet been used. */
2044 void
2046 {
2048  if (CIRCUIT_IS_ORIGIN(circ) &&
2049  !circ->marked_for_close &&
2050  !circ->timestamp_dirty)
2051  circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
2052  }
2053  SMARTLIST_FOREACH_END(circ);
2054 }
2055 
2056 /** Go through the circuitlist; for each circuit that starts at us
2057  * and is dirty, frob its timestamp_dirty so we won't use it for any
2058  * new streams.
2059  *
2060  * This is useful for letting the user change pseudonyms, so new
2061  * streams will not be linkable to old streams.
2062  */
2063 void
2065 {
2067  if (CIRCUIT_IS_ORIGIN(circ) &&
2068  !circ->marked_for_close &&
2069  circ->timestamp_dirty) {
2071  }
2072  }
2073  SMARTLIST_FOREACH_END(circ);
2074 }
2075 
2076 /**
2077  * Report any queued cells on or_circuits as written in our bandwidth
2078  * totals, for the specified channel direction.
2079  *
2080  * When we close a circuit or clear its cell queues, we've read
2081  * data and recorded those bytes in our read statistics, but we're
2082  * not going to write it. This discrepancy can be used by an adversary
2083  * to infer information from our public relay statistics and perform
2084  * attacks such as guard discovery.
2085  *
2086  * This function is in the critical path of circuit_mark_for_close().
2087  * It must be (and is) O(1)!
2088  *
2089  * See https://bugs.torproject.org/tpo/core/tor/23512
2090  */
2091 void
2094 {
2095  uint64_t cells;
2096  uint64_t cell_size;
2097  uint64_t written_sync;
2098  const channel_t *chan = NULL;
2099  const or_circuit_t *or_circ;
2100 
2101  if (!CIRCUIT_IS_ORCIRC(c))
2102  return;
2103 
2104  or_circ = CONST_TO_OR_CIRCUIT(c);
2105 
2106  if (dir == CIRCUIT_N_CHAN) {
2107  chan = c->n_chan;
2108  cells = c->n_chan_cells.n;
2109  } else {
2110  chan = or_circ->p_chan;
2111  cells = or_circ->p_chan_cells.n;
2112  }
2113 
2114  /* If we still know the chan, determine real cell size. Otherwise,
2115  * assume it's a wide circid channel */
2116  if (chan)
2117  cell_size = get_cell_network_size(chan->wide_circ_ids);
2118  else
2119  cell_size = CELL_MAX_NETWORK_SIZE;
2120 
2121  /* If we know the channel, find out if it's IPv6. */
2122  tor_addr_t remote_addr;
2123  bool is_ipv6 = chan &&
2124  channel_get_addr_if_possible(chan, &remote_addr) &&
2125  tor_addr_family(&remote_addr) == AF_INET6;
2126 
2127  /* The missing written bytes are the cell counts times their cell
2128  * size plus TLS per cell overhead */
2129  written_sync = cells*(cell_size+TLS_PER_CELL_OVERHEAD);
2130 
2131  /* Report the missing bytes as written, to avoid asymmetry.
2132  * We must use time() for consistency with rephist, even though on
2133  * some very old rare platforms, approx_time() may be faster. */
2134  bwhist_note_bytes_written(written_sync, time(NULL), is_ipv6);
2135 }
2136 
2137 /** Mark <b>circ</b> to be closed next time we call
2138  * circuit_close_all_marked(). Do any cleanup needed:
2139  * - If state is onionskin_pending, remove circ from the onion_pending
2140  * list.
2141  * - If circ isn't open yet: call circuit_build_failed() if we're
2142  * the origin.
2143  * - If purpose is C_INTRODUCE_ACK_WAIT, report the intro point
2144  * failure we just had to the hidden service client module.
2145  * - If purpose is C_INTRODUCING and <b>reason</b> isn't TIMEOUT,
2146  * report to the hidden service client module that the intro point
2147  * we just tried may be unreachable.
2148  * - Send appropriate destroys and edge_destroys for conns and
2149  * streams attached to circ.
2150  * - If circ->rend_splice is set (we are the midpoint of a joined
2151  * rendezvous stream), then mark the other circuit to close as well.
2152  */
2153 MOCK_IMPL(void,
2154 circuit_mark_for_close_, (circuit_t *circ, int reason, int line,
2155  const char *file))
2156 {
2157  int orig_reason = reason; /* Passed to the controller */
2158  assert_circuit_ok(circ);
2159  tor_assert(line);
2160  tor_assert(file);
2161 
2162  /* Check whether the circuitpadding subsystem wants to block this close */
2163  if (circpad_marked_circuit_for_padding(circ, reason)) {
2164  return;
2165  }
2166 
2167  if (circ->marked_for_close) {
2168  log_warn(LD_BUG,
2169  "Duplicate call to circuit_mark_for_close at %s:%d"
2170  " (first at %s:%d)", file, line,
2172  return;
2173  }
2174  if (reason == END_CIRC_AT_ORIGIN) {
2175  if (!CIRCUIT_IS_ORIGIN(circ)) {
2176  log_warn(LD_BUG, "Specified 'at-origin' non-reason for ending circuit, "
2177  "but circuit was not at origin. (called %s:%d, purpose=%d)",
2178  file, line, circ->purpose);
2179  }
2180  reason = END_CIRC_REASON_NONE;
2181  }
2182 
2183  if (CIRCUIT_IS_ORIGIN(circ)) {
2184  if (pathbias_check_close(TO_ORIGIN_CIRCUIT(circ), reason) == -1) {
2185  /* Don't close it yet, we need to test it first */
2186  return;
2187  }
2188 
2189  /* We don't send reasons when closing circuits at the origin. */
2190  reason = END_CIRC_REASON_NONE;
2191  }
2192 
2193  circuit_synchronize_written_or_bandwidth(circ, CIRCUIT_N_CHAN);
2194  circuit_synchronize_written_or_bandwidth(circ, CIRCUIT_P_CHAN);
2195 
2196  if (reason & END_CIRC_REASON_FLAG_REMOTE)
2197  reason &= ~END_CIRC_REASON_FLAG_REMOTE;
2198 
2199  if (reason < END_CIRC_REASON_MIN_ || reason > END_CIRC_REASON_MAX_) {
2200  if (!(orig_reason & END_CIRC_REASON_FLAG_REMOTE))
2201  log_warn(LD_BUG, "Reason %d out of range at %s:%d", reason, file, line);
2202  reason = END_CIRC_REASON_NONE;
2203  }
2204 
2205  circ->marked_for_close = line;
2206  circ->marked_for_close_file = file;
2207  circ->marked_for_close_reason = reason;
2208  circ->marked_for_close_orig_reason = orig_reason;
2209 
2210  if (!CIRCUIT_IS_ORIGIN(circ)) {
2211  or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
2212  if (or_circ->rend_splice) {
2213  if (!or_circ->rend_splice->base_.marked_for_close) {
2214  /* do this after marking this circuit, to avoid infinite recursion. */
2215  circuit_mark_for_close(TO_CIRCUIT(or_circ->rend_splice), reason);
2216  }
2217  or_circ->rend_splice = NULL;
2218  }
2219  }
2220 
2221  /* Notify the HS subsystem that this circuit is closing. */
2223 
2224  if (circuits_pending_close == NULL)
2226 
2229 
2230  log_info(LD_GENERAL, "Circuit %u (id: %" PRIu32 ") marked for close at "
2231  "%s:%d (orig reason: %d, new reason: %d)",
2232  circ->n_circ_id,
2233  CIRCUIT_IS_ORIGIN(circ) ?
2234  TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0,
2235  file, line, orig_reason, reason);
2236  tor_trace(TR_SUBSYS(circuit), TR_EV(mark_for_close), circ);
2237 }
2238 
2239 /** Called immediately before freeing a marked circuit <b>circ</b> from
2240  * circuit_free_all() while shutting down Tor; this is a safe-at-shutdown
2241  * version of circuit_about_to_free(). It's important that it at least
2242  * do circuitmux_detach_circuit() when appropriate.
2243  */
2244 static void
2246 {
2247 
2248  if (circ->n_chan) {
2249  circuit_clear_cell_queue(circ, circ->n_chan);
2250  circuitmux_detach_circuit(circ->n_chan->cmux, circ);
2251  circuit_set_n_circid_chan(circ, 0, NULL);
2252  }
2253 
2254  if (! CIRCUIT_IS_ORIGIN(circ)) {
2255  or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
2256 
2257  if (or_circ->p_chan) {
2258  circuit_clear_cell_queue(circ, or_circ->p_chan);
2259  circuitmux_detach_circuit(or_circ->p_chan->cmux, circ);
2260  circuit_set_p_circid_chan(or_circ, 0, NULL);
2261  }
2262  }
2263 }
2264 
2265 /** Called immediately before freeing a marked circuit <b>circ</b>.
2266  * Disconnects the circuit from other data structures, launches events
2267  * as appropriate, and performs other housekeeping.
2268  */
2269 static void
2271 {
2272 
2273  int reason = circ->marked_for_close_reason;
2274  int orig_reason = circ->marked_for_close_orig_reason;
2275 
2276  if (circ->state == CIRCUIT_STATE_ONIONSKIN_PENDING) {
2278  }
2279  /* If the circuit ever became OPEN, we sent it to the reputation history
2280  * module then. If it isn't OPEN, we send it there now to remember which
2281  * links worked and which didn't.
2282  */
2283  if (circ->state != CIRCUIT_STATE_OPEN &&
2284  circ->state != CIRCUIT_STATE_GUARD_WAIT) {
2285  if (CIRCUIT_IS_ORIGIN(circ)) {
2286  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
2287  circuit_build_failed(ocirc); /* take actions if necessary */
2288  }
2289  }
2290  if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
2293  }
2296  }
2297  if (CIRCUIT_IS_ORIGIN(circ)) {
2299  (circ->state == CIRCUIT_STATE_OPEN ||
2300  circ->state == CIRCUIT_STATE_GUARD_WAIT) ?
2301  CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED,
2302  orig_reason);
2303  }
2304 
2305  if (circ->n_chan) {
2306  circuit_clear_cell_queue(circ, circ->n_chan);
2307  /* Only send destroy if the channel isn't closing anyway */
2308  if (!CHANNEL_CONDEMNED(circ->n_chan)) {
2309  channel_send_destroy(circ->n_circ_id, circ->n_chan, reason);
2310  }
2311  circuitmux_detach_circuit(circ->n_chan->cmux, circ);
2312  circuit_set_n_circid_chan(circ, 0, NULL);
2313  }
2314 
2315  if (! CIRCUIT_IS_ORIGIN(circ)) {
2316  or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
2317  edge_connection_t *conn;
2318  for (conn=or_circ->n_streams; conn; conn=conn->next_stream)
2319  connection_edge_destroy(or_circ->p_circ_id, conn);
2320  or_circ->n_streams = NULL;
2321 
2322  while (or_circ->resolving_streams) {
2323  conn = or_circ->resolving_streams;
2324  or_circ->resolving_streams = conn->next_stream;
2325  if (!conn->base_.marked_for_close) {
2326  /* The client will see a DESTROY, and infer that the connections
2327  * are closing because the circuit is getting torn down. No need
2328  * to send an end cell. */
2329  conn->edge_has_sent_end = 1;
2330  conn->end_reason = END_STREAM_REASON_DESTROY;
2332  connection_mark_for_close(TO_CONN(conn));
2333  }
2334  conn->on_circuit = NULL;
2335  }
2336 
2337  if (or_circ->p_chan) {
2338  circuit_clear_cell_queue(circ, or_circ->p_chan);
2339  /* Only send destroy if the channel isn't closing anyway */
2340  if (!CHANNEL_CONDEMNED(or_circ->p_chan)) {
2341  channel_send_destroy(or_circ->p_circ_id, or_circ->p_chan, reason);
2342  }
2343  circuitmux_detach_circuit(or_circ->p_chan->cmux, circ);
2344  circuit_set_p_circid_chan(or_circ, 0, NULL);
2345  }
2346  } else {
2347  origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
2348  edge_connection_t *conn;
2349  for (conn=ocirc->p_streams; conn; conn=conn->next_stream)
2350  connection_edge_destroy(circ->n_circ_id, conn);
2351  ocirc->p_streams = NULL;
2352  }
2353 }
2354 
2355 /** Given a marked circuit <b>circ</b>, aggressively free its cell queues to
2356  * recover memory. */
2357 static void
2359 {
2360  if (!circ->marked_for_close) {
2361  log_warn(LD_BUG, "Called on non-marked circuit");
2362  return;
2363  }
2365  if (! CIRCUIT_IS_ORIGIN(circ)) {
2366  or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
2367  cell_queue_clear(&orcirc->p_chan_cells);
2368  }
2369 }
2370 
2371 static size_t
2372 single_conn_free_bytes(connection_t *conn)
2373 {
2374  size_t result = 0;
2375  if (conn->inbuf) {
2376  result += buf_allocation(conn->inbuf);
2377  buf_clear(conn->inbuf);
2378  }
2379  if (conn->outbuf) {
2380  result += buf_allocation(conn->outbuf);
2381  buf_clear(conn->outbuf);
2382  }
2383  if (conn->type == CONN_TYPE_DIR) {
2384  dir_connection_t *dir_conn = TO_DIR_CONN(conn);
2385  if (dir_conn->compress_state) {
2386  result += tor_compress_state_size(dir_conn->compress_state);
2387  tor_compress_free(dir_conn->compress_state);
2388  dir_conn->compress_state = NULL;
2389  }
2390  }
2391  return result;
2392 }
2393 
2394 /** Aggressively free buffer contents on all the buffers of all streams in the
2395  * list starting at <b>stream</b>. Return the number of bytes recovered. */
2396 static size_t
2398 {
2399  size_t result = 0;
2400  for ( ; stream; stream = stream->next_stream) {
2401  connection_t *conn = TO_CONN(stream);
2402  result += single_conn_free_bytes(conn);
2403  if (conn->linked_conn) {
2404  result += single_conn_free_bytes(conn->linked_conn);
2405  }
2406  }
2407  return result;
2408 }
2409 
2410 /** Aggressively free buffer contents on all the buffers of all streams on
2411  * circuit <b>c</b>. Return the number of bytes recovered. */
2412 static size_t
2414 {
2415  if (CIRCUIT_IS_ORIGIN(c)) {
2417  } else {
2418  return marked_circuit_streams_free_bytes(TO_OR_CIRCUIT(c)->n_streams);
2419  }
2420 }
2421 
2422 /** Return the number of cells used by the circuit <b>c</b>'s cell queues. */
2423 STATIC size_t
2425 {
2426  size_t n = c->n_chan_cells.n;
2427  if (! CIRCUIT_IS_ORIGIN(c)) {
2428  circuit_t *cc = (circuit_t *) c;
2429  n += TO_OR_CIRCUIT(cc)->p_chan_cells.n;
2430  }
2431  return n;
2432 }
2433 
2434 /** Return the number of bytes allocated for <b>c</b>'s half-open streams. */
2435 static size_t
2437 {
2438  if (! CIRCUIT_IS_ORIGIN(c)) {
2439  return 0;
2440  }
2441  const origin_circuit_t *ocirc = CONST_TO_ORIGIN_CIRCUIT(c);
2442  if (ocirc->half_streams)
2443  return smartlist_len(ocirc->half_streams) * sizeof(half_edge_t);
2444  else
2445  return 0;
2446 }
2447 
2448 /**
2449  * Return the age of the oldest cell queued on <b>c</b>, in timestamp units.
2450  * Return 0 if there are no cells queued on c. Requires that <b>now</b> be
2451  * the current coarse timestamp.
2452  *
2453  * This function will return incorrect results if the oldest cell queued on
2454  * the circuit is older than about 2**32 msec (about 49 days) old.
2455  */
2456 STATIC uint32_t
2458 {
2459  uint32_t age = 0;
2460  packed_cell_t *cell;
2461 
2462  if (NULL != (cell = TOR_SIMPLEQ_FIRST(&c->n_chan_cells.head)))
2463  age = now - cell->inserted_timestamp;
2464 
2465  if (! CIRCUIT_IS_ORIGIN(c)) {
2466  const or_circuit_t *orcirc = CONST_TO_OR_CIRCUIT(c);
2467  if (NULL != (cell = TOR_SIMPLEQ_FIRST(&orcirc->p_chan_cells.head))) {
2468  uint32_t age2 = now - cell->inserted_timestamp;
2469  if (age2 > age)
2470  return age2;
2471  }
2472  }
2473  return age;
2474 }
2475 
2476 /** Return the age of the oldest buffer chunk on <b>conn</b>, where age is
2477  * taken in timestamp units before the time <b>now</b>. If the connection has
2478  * no data, treat it as having age zero.
2479  **/
2480 static uint32_t
2481 conn_get_buffer_age(const connection_t *conn, uint32_t now_ts)
2482 {
2483  uint32_t age = 0, age2;
2484  if (conn->outbuf) {
2485  age2 = buf_get_oldest_chunk_timestamp(conn->outbuf, now_ts);
2486  if (age2 > age)
2487  age = age2;
2488  }
2489  if (conn->inbuf) {
2490  age2 = buf_get_oldest_chunk_timestamp(conn->inbuf, now_ts);
2491  if (age2 > age)
2492  age = age2;
2493  }
2494  return age;
2495 }
2496 
2497 /** Return the age in timestamp units of the oldest buffer chunk on any stream
2498  * in the linked list <b>stream</b>, where age is taken in timestamp units
2499  * before the timestamp <b>now</b>. */
2500 static uint32_t
2502 {
2503  uint32_t age = 0, age2;
2504  for (; stream; stream = stream->next_stream) {
2505  const connection_t *conn = TO_CONN(stream);
2506  age2 = conn_get_buffer_age(conn, now);
2507  if (age2 > age)
2508  age = age2;
2509  if (conn->linked_conn) {
2510  age2 = conn_get_buffer_age(conn->linked_conn, now);
2511  if (age2 > age)
2512  age = age2;
2513  }
2514  }
2515  return age;
2516 }
2517 
2518 /** Return the age in timestamp units of the oldest buffer chunk on any stream
2519  * attached to the circuit <b>c</b>, where age is taken before the timestamp
2520  * <b>now</b>. */
2521 STATIC uint32_t
2523 {
2524  if (CIRCUIT_IS_ORIGIN(c)) {
2526  CONST_TO_ORIGIN_CIRCUIT(c)->p_streams, now);
2527  } else {
2529  CONST_TO_OR_CIRCUIT(c)->n_streams, now);
2530  }
2531 }
2532 
2533 /** Return the age of the oldest cell or stream buffer chunk on the circuit
2534  * <b>c</b>, where age is taken in timestamp units before the timestamp
2535  * <b>now</b> */
2536 STATIC uint32_t
2538 {
2539  uint32_t cell_age = circuit_max_queued_cell_age(c, now);
2540  uint32_t data_age = circuit_max_queued_data_age(c, now);
2541  if (cell_age > data_age)
2542  return cell_age;
2543  else
2544  return data_age;
2545 }
2546 
2547 /** Helper to sort a list of circuit_t by age of oldest item, in descending
2548  * order. */
2549 static int
2550 circuits_compare_by_oldest_queued_item_(const void **a_, const void **b_)
2551 {
2552  const circuit_t *a = *a_;
2553  const circuit_t *b = *b_;
2554  uint32_t age_a = a->age_tmp;
2555  uint32_t age_b = b->age_tmp;
2556 
2557  if (age_a < age_b)
2558  return 1;
2559  else if (age_a == age_b)
2560  return 0;
2561  else
2562  return -1;
2563 }
2564 
2565 static uint32_t now_ts_for_buf_cmp;
2566 
2567 /** Helper to sort a list of circuit_t by age of oldest item, in descending
2568  * order. */
2569 static int
2570 conns_compare_by_buffer_age_(const void **a_, const void **b_)
2571 {
2572  const connection_t *a = *a_;
2573  const connection_t *b = *b_;
2574  time_t age_a = conn_get_buffer_age(a, now_ts_for_buf_cmp);
2575  time_t age_b = conn_get_buffer_age(b, now_ts_for_buf_cmp);
2576 
2577  if (age_a < age_b)
2578  return 1;
2579  else if (age_a == age_b)
2580  return 0;
2581  else
2582  return -1;
2583 }
2584 
2585 #define FRACTION_OF_DATA_TO_RETAIN_ON_OOM 0.90
2586 
2587 /** We're out of memory for cells, having allocated <b>current_allocation</b>
2588  * bytes' worth. Kill the 'worst' circuits until we're under
2589  * FRACTION_OF_DATA_TO_RETAIN_ON_OOM of our maximum usage.
2590  *
2591  * Return the number of bytes removed. */
2592 size_t
2593 circuits_handle_oom(size_t current_allocation)
2594 {
2595  smartlist_t *circlist;
2597  int conn_idx;
2598  size_t mem_to_recover;
2599  size_t mem_recovered=0;
2600  int n_circuits_killed=0;
2601  int n_dirconns_killed=0;
2602  uint32_t now_ts;
2603  log_notice(LD_GENERAL, "We're low on memory (cell queues total alloc:"
2604  " %"TOR_PRIuSZ" buffer total alloc: %" TOR_PRIuSZ ","
2605  " tor compress total alloc: %" TOR_PRIuSZ
2606  " (zlib: %" TOR_PRIuSZ ", zstd: %" TOR_PRIuSZ ","
2607  " lzma: %" TOR_PRIuSZ "),"
2608  " rendezvous cache total alloc: %" TOR_PRIuSZ "). Killing"
2609  " circuits withover-long queues. (This behavior is controlled by"
2610  " MaxMemInQueues.)",
2611  cell_queues_get_total_allocation(),
2612  buf_get_total_allocation(),
2617  hs_cache_get_total_allocation());
2618  {
2619  size_t mem_target = (size_t)(get_options()->MaxMemInQueues *
2620  FRACTION_OF_DATA_TO_RETAIN_ON_OOM);
2621  if (current_allocation <= mem_target)
2622  return 0;
2623  mem_to_recover = current_allocation - mem_target;
2624  }
2625 
2626  now_ts = monotime_coarse_get_stamp();
2627 
2628  circlist = circuit_get_global_list();
2629  SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) {
2630  circ->age_tmp = circuit_max_queued_item_age(circ, now_ts);
2631  } SMARTLIST_FOREACH_END(circ);
2632 
2633  /* This is O(n log n); there are faster algorithms we could use instead.
2634  * Let's hope this doesn't happen enough to be in the critical path. */
2636 
2637  /* Fix up the indices before we run into trouble */
2638  SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) {
2639  circ->global_circuitlist_idx = circ_sl_idx;
2640  } SMARTLIST_FOREACH_END(circ);
2641 
2642  /* Now sort the connection array ... */
2643  now_ts_for_buf_cmp = now_ts;
2645  now_ts_for_buf_cmp = 0;
2646 
2647  /* Fix up the connection array to its new order. */
2649  conn->conn_array_index = conn_sl_idx;
2650  } SMARTLIST_FOREACH_END(conn);
2651 
2652  /* Okay, now the worst circuits and connections are at the front of their
2653  * respective lists. Let's mark them, and reclaim their storage
2654  * aggressively. */
2655  conn_idx = 0;
2656  SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) {
2657  size_t n;
2658  size_t freed;
2659 
2660  /* Free storage in any non-linked directory connections that have buffered
2661  * data older than this circuit. */
2662  while (conn_idx < smartlist_len(connection_array)) {
2663  connection_t *conn = smartlist_get(connection_array, conn_idx);
2664  uint32_t conn_age = conn_get_buffer_age(conn, now_ts);
2665  if (conn_age < circ->age_tmp) {
2666  break;
2667  }
2668  if (conn->type == CONN_TYPE_DIR && conn->linked_conn == NULL) {
2669  if (!conn->marked_for_close)
2670  connection_mark_for_close(conn);
2671  mem_recovered += single_conn_free_bytes(conn);
2672 
2673  ++n_dirconns_killed;
2674 
2675  if (mem_recovered >= mem_to_recover)
2676  goto done_recovering_mem;
2677  }
2678  ++conn_idx;
2679  }
2680 
2681  /* Now, kill the circuit. */
2682  n = n_cells_in_circ_queues(circ);
2683  const size_t half_stream_alloc = circuit_alloc_in_half_streams(circ);
2684  if (! circ->marked_for_close) {
2685  circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
2686  }
2688  freed = marked_circuit_free_stream_bytes(circ);
2689 
2690  ++n_circuits_killed;
2691 
2692  mem_recovered += n * packed_cell_mem_cost();
2693  mem_recovered += half_stream_alloc;
2694  mem_recovered += freed;
2695 
2696  if (mem_recovered >= mem_to_recover)
2697  goto done_recovering_mem;
2698  } SMARTLIST_FOREACH_END(circ);
2699 
2700  done_recovering_mem:
2701  log_notice(LD_GENERAL, "Removed %"TOR_PRIuSZ" bytes by killing %d circuits; "
2702  "%d circuits remain alive. Also killed %d non-linked directory "
2703  "connections.",
2704  mem_recovered,
2705  n_circuits_killed,
2706  smartlist_len(circlist) - n_circuits_killed,
2707  n_dirconns_killed);
2708 
2709  return mem_recovered;
2710 }
2711 
2712 /** Verify that circuit <b>c</b> has all of its invariants
2713  * correct. Trigger an assert if anything is invalid.
2714  */
2715 MOCK_IMPL(void,
2717 {
2718  edge_connection_t *conn;
2719  const or_circuit_t *or_circ = NULL;
2720  const origin_circuit_t *origin_circ = NULL;
2721 
2722  tor_assert(c);
2724  tor_assert(c->purpose >= CIRCUIT_PURPOSE_MIN_ &&
2725  c->purpose <= CIRCUIT_PURPOSE_MAX_);
2726 
2727  if (CIRCUIT_IS_ORIGIN(c))
2728  origin_circ = CONST_TO_ORIGIN_CIRCUIT(c);
2729  else
2730  or_circ = CONST_TO_OR_CIRCUIT(c);
2731 
2732  if (c->n_chan) {
2733  tor_assert(!c->n_hop);
2734 
2735  if (c->n_circ_id) {
2736  /* We use the _impl variant here to make sure we don't fail on marked
2737  * circuits, which would not be returned by the regular function. */
2739  c->n_chan, NULL);
2740  tor_assert(c == c2);
2741  }
2742  }
2743  if (or_circ && or_circ->p_chan) {
2744  if (or_circ->p_circ_id) {
2745  /* ibid */
2746  circuit_t *c2 =
2748  or_circ->p_chan, NULL);
2749  tor_assert(c == c2);
2750  }
2751  }
2752  if (or_circ)
2753  for (conn = or_circ->n_streams; conn; conn = conn->next_stream)
2754  tor_assert(conn->base_.type == CONN_TYPE_EXIT);
2755 
2756  tor_assert(c->deliver_window >= 0);
2757  tor_assert(c->package_window >= 0);
2758  if (c->state == CIRCUIT_STATE_OPEN ||
2761  if (or_circ) {
2762  relay_crypto_assert_ok(&or_circ->crypto);
2763  }
2764  }
2765  if (c->state == CIRCUIT_STATE_CHAN_WAIT && !c->marked_for_close) {
2768  } else {
2771  }
2772  if (origin_circ && origin_circ->cpath) {
2773  cpath_assert_ok(origin_circ->cpath);
2774  }
2776  tor_assert(or_circ);
2777  if (!c->marked_for_close) {
2778  tor_assert(or_circ->rend_splice);
2779  tor_assert(or_circ->rend_splice->rend_splice == or_circ);
2780  }
2781  tor_assert(or_circ->rend_splice != or_circ);
2782  } else {
2783  tor_assert(!or_circ || !or_circ->rend_splice);
2784  }
2785 }
static sa_family_t tor_addr_family(const tor_addr_t *a)
Definition: address.h:187
time_t approx_time(void)
Definition: approx_time.c:32
void buf_clear(buf_t *buf)
Definition: buffers.c:381
size_t buf_allocation(const buf_t *buf)
Definition: buffers.c:401
uint32_t buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now)
Definition: buffers.c:506
Header file for buffers.c.
void bwhist_note_bytes_written(uint64_t num_bytes, time_t when, bool ipv6)
Definition: bwhist.c:164
Header for feature/stats/bwhist.c.
int channel_matches_extend_info(channel_t *chan, extend_info_t *extend_info)
Definition: channel.c:3270
int channel_send_destroy(circid_t circ_id, channel_t *chan, int reason)
Definition: channel.c:2031
int channel_get_addr_if_possible(const channel_t *chan, tor_addr_t *addr_out)
Definition: channel.c:2835
const char * channel_describe_peer(channel_t *chan)
Definition: channel.c:2815
Header file for channel.c.
Header file for channeltls.c.
int pathbias_check_close(origin_circuit_t *ocirc, int reason)
#define DEAD_CIRCUIT_MAGIC
Definition: circuit_st.h:36
#define ORIGIN_CIRCUIT_MAGIC
Definition: circuit_st.h:30
#define OR_CIRCUIT_MAGIC
Definition: circuit_st.h:32
void circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
Definition: circuitbuild.c:351
int route_len_for_purpose(uint8_t purpose, extend_info_t *exit_ei)
Header file for circuitbuild.c.
STATIC uint32_t circuit_max_queued_item_age(const circuit_t *c, uint32_t now)
Definition: circuitlist.c:2537
const char * circuit_purpose_to_controller_hs_state_string(uint8_t purpose)
Definition: circuitlist.c:843
static int chan_circid_entries_eq_(chan_circid_circuit_map_t *a, chan_circid_circuit_map_t *b)
Definition: circuitlist.c:193
circuit_t * circuit_get_by_circid_channel_even_if_marked(circid_t circ_id, channel_t *chan)
Definition: circuitlist.c:1525
static uint32_t circuit_get_streams_max_data_age(const edge_connection_t *stream, uint32_t now)
Definition: circuitlist.c:2501
STATIC void circuit_free_(circuit_t *circ)
Definition: circuitlist.c:1126
void circuit_close_all_marked(void)
Definition: circuitlist.c:662
void circuit_mark_for_close_(circuit_t *circ, int reason, int line, const char *file)
Definition: circuitlist.c:2155
static smartlist_t * global_circuitlist
Definition: circuitlist.c:120
int circuit_any_opened_circuits_cached(void)
Definition: circuitlist.c:755
void channel_note_destroy_pending(channel_t *chan, circid_t id)
Definition: circuitlist.c:409
static int any_opened_circs_cached_val
Definition: circuitlist.c:146
origin_circuit_t * circuit_get_next_intro_circ(const origin_circuit_t *start, bool want_client_circ)
Definition: circuitlist.c:1686
void circuit_set_p_circid_chan(or_circuit_t *or_circ, circid_t id, channel_t *chan)
Definition: circuitlist.c:451
origin_circuit_t * circuit_find_to_cannibalize(uint8_t purpose_to_produce, extend_info_t *info, int flags)
Definition: circuitlist.c:1855
int circuit_id_in_use_on_channel(circid_t circ_id, channel_t *chan)
Definition: circuitlist.c:1539
STATIC size_t n_cells_in_circ_queues(const circuit_t *c)
Definition: circuitlist.c:2424
static void circuit_dump_conn_details(int severity, circuit_t *circ, int conn_array_index, const char *type, circid_t this_circid, circid_t other_circid)
Definition: circuitlist.c:1356
void circuit_synchronize_written_or_bandwidth(const circuit_t *c, circuit_channel_direction_t dir)
Definition: circuitlist.c:2092
void circuit_set_n_circid_chan(circuit_t *circ, circid_t id, channel_t *chan)
Definition: circuitlist.c:474
static void init_circuit_base(circuit_t *circ)
Definition: circuitlist.c:989
circuit_t * circuit_get_by_circid_channel(circid_t circ_id, channel_t *chan)
Definition: circuitlist.c:1510
static uint32_t conn_get_buffer_age(const connection_t *conn, uint32_t now_ts)
Definition: circuitlist.c:2481
void circuit_mark_all_dirty_circs_as_unusable(void)
Definition: circuitlist.c:2064
origin_circuit_t * origin_circuit_new(void)
Definition: circuitlist.c:1018
static int circuits_compare_by_oldest_queued_item_(const void **a_, const void **b_)
Definition: circuitlist.c:2550
void circuit_clear_cpath(origin_circuit_t *circ)
Definition: circuitlist.c:1278
void circuit_set_state(circuit_t *circ, uint8_t state)
Definition: circuitlist.c:543
void circuit_free_all(void)
Definition: circuitlist.c:1302
origin_circuit_t * circuit_get_next_by_purpose(origin_circuit_t *start, uint8_t purpose)
Definition: circuitlist.c:1769
circuit_t * circuit_get_by_edge_conn(edge_connection_t *conn)
Definition: circuitlist.c:1571
const char * circuit_purpose_to_string(uint8_t purpose)
Definition: circuitlist.c:903
static unsigned int chan_circid_entry_hash_(chan_circid_circuit_map_t *a)
Definition: circuitlist.c:202
void channel_mark_circid_unusable(channel_t *chan, circid_t id)
Definition: circuitlist.c:353
void circuit_dump_by_conn(connection_t *conn, int severity)
Definition: circuitlist.c:1377
int circuit_any_opened_circuits(void)
Definition: circuitlist.c:718
const char * circuit_purpose_to_controller_string(uint8_t purpose)
Definition: circuitlist.c:782
STATIC uint32_t circuit_max_queued_data_age(const circuit_t *c, uint32_t now)
Definition: circuitlist.c:2522
int circuit_get_cpath_len(origin_circuit_t *circ)
Definition: circuitlist.c:1993
smartlist_t * circuit_find_circuits_to_upgrade_from_guard_wait(void)
Definition: circuitlist.c:1965
void channel_mark_circid_usable(channel_t *chan, circid_t id)
Definition: circuitlist.c:386
static smartlist_t * circuits_pending_close
Definition: circuitlist.c:135
int circuit_get_cpath_opened_len(const origin_circuit_t *circ)
Definition: circuitlist.c:2009
void assert_circuit_ok(const circuit_t *c)
Definition: circuitlist.c:2716
smartlist_t * circuit_get_global_list(void)
Definition: circuitlist.c:694
static void circuit_remove_from_origin_circuit_list(origin_circuit_t *origin_circ)
Definition: circuitlist.c:629
static smartlist_t * circuits_pending_other_guards
Definition: circuitlist.c:131
static size_t marked_circuit_free_stream_bytes(circuit_t *c)
Definition: circuitlist.c:2413
int circuit_count_pending_on_channel(channel_t *chan)
Definition: circuitlist.c:609
static HT_HEAD(HT_PROTOTYPE(chan_circid_map, HT_PROTOTYPE(chan_circid_circuit_map_t)
Definition: circuitlist.c:216
STATIC uint32_t circuit_max_queued_cell_age(const circuit_t *c, uint32_t now)
Definition: circuitlist.c:2457
origin_circuit_t * TO_ORIGIN_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:166
static int conns_compare_by_buffer_age_(const void **a_, const void **b_)
Definition: circuitlist.c:2570
size_t circuits_handle_oom(size_t current_allocation)
Definition: circuitlist.c:2593
void circuit_get_all_pending_on_channel(smartlist_t *out, channel_t *chan)
Definition: circuitlist.c:578
smartlist_t * circuit_get_global_origin_circuit_list(void)
Definition: circuitlist.c:703
static void circuit_about_to_free(circuit_t *circ)
Definition: circuitlist.c:2270
int circuit_event_status(origin_circuit_t *circ, circuit_status_event_t tp, int reason_code)
Definition: circuitlist.c:499
crypt_path_t * circuit_get_cpath_hop(origin_circuit_t *circ, int hopnum)
Definition: circuitlist.c:2029
static void circuit_about_to_free_atexit(circuit_t *circ)
Definition: circuitlist.c:2245
static size_t marked_circuit_streams_free_bytes(edge_connection_t *stream)
Definition: circuitlist.c:2397
time_t circuit_id_when_marked_unusable_on_channel(circid_t circ_id, channel_t *chan)
Definition: circuitlist.c:1552
or_circuit_t * TO_OR_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:154
void circuit_cache_opened_circuit_state(int circuits_are_opened)
Definition: circuitlist.c:744
origin_circuit_t * circuit_get_next_service_rp_circ(origin_circuit_t *start)
Definition: circuitlist.c:1738
#define DFLT_IDLE_TIMEOUT_WHILE_LEARNING
Definition: circuitlist.c:1010
static void circuit_add_to_origin_circuit_list(origin_circuit_t *origin_circ)
Definition: circuitlist.c:650
static smartlist_t * circuits_pending_chans
Definition: circuitlist.c:127
static uint8_t get_circuit_purpose_needed_to_cannibalize(uint8_t purpose)
Definition: circuitlist.c:1824
void channel_note_destroy_not_pending(channel_t *chan, circid_t id)
Definition: circuitlist.c:429
static void circuit_state_publish(const circuit_t *circ)
Definition: circuitlist.c:523
const char * circuit_state_to_string(int state)
Definition: circuitlist.c:762
void circuit_clear_testing_cell_stats(circuit_t *circ)
Definition: circuitlist.c:1113
static size_t circuit_alloc_in_half_streams(const circuit_t *c)
Definition: circuitlist.c:2436
static circuit_t * circuit_get_by_circid_channel_impl(circid_t circ_id, channel_t *chan, int *found_entry_out)
Definition: circuitlist.c:1442
void circuit_unlink_all_from_channel(channel_t *chan, int reason)
Definition: circuitlist.c:1588
static void marked_circuit_free_cells(circuit_t *circ)
Definition: circuitlist.c:2358
static int circuit_can_be_cannibalized_for_v3_rp(const origin_circuit_t *circ)
Definition: circuitlist.c:1799
or_circuit_t * or_circuit_new(circid_t p_circ_id, channel_t *p_chan)
Definition: circuitlist.c:1091
static smartlist_t * global_origin_circuit_list
Definition: circuitlist.c:124
origin_circuit_t * circuit_get_by_global_id(uint32_t id)
Definition: circuitlist.c:1418
void circuit_mark_all_unused_circs(void)
Definition: circuitlist.c:2045
int32_t circuit_initial_package_window(void)
Definition: circuitlist.c:975
Header file for circuitlist.c.
#define CIRCUIT_PURPOSE_S_CONNECT_REND
Definition: circuitlist.h:107
#define CIRCUIT_STATE_ONIONSKIN_PENDING
Definition: circuitlist.h:23
#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
Definition: circuitlist.h:93
#define CIRCUIT_PURPOSE_REND_POINT_WAITING
Definition: circuitlist.h:45
#define CIRCUIT_PURPOSE_PATH_BIAS_TESTING
Definition: circuitlist.h:123
#define CIRCUIT_STATE_OPEN
Definition: circuitlist.h:32
#define CIRCUIT_IS_ORCIRC(c)
Definition: circuitlist.h:154
#define CIRCUIT_PURPOSE_IS_ORIGIN(p)
Definition: circuitlist.h:140
#define CIRCUIT_STATE_BUILDING
Definition: circuitlist.h:21
#define CIRCUIT_PURPOSE_C_REND_JOINED
Definition: circuitlist.h:88
#define CIRCUIT_PURPOSE_S_INTRO
Definition: circuitlist.h:104
#define CIRCUIT_PURPOSE_INTRO_POINT
Definition: circuitlist.h:42
#define CIRCUIT_PURPOSE_CONTROLLER
Definition: circuitlist.h:121
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:147
#define CIRCUIT_PURPOSE_C_CIRCUIT_PADDING
Definition: circuitlist.h:95
#define CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
Definition: circuitlist.h:86
#define CIRCUIT_STATE_GUARD_WAIT
Definition: circuitlist.h:30
#define CIRCUIT_PURPOSE_TESTING
Definition: circuitlist.h:118
#define CIRCUIT_PURPOSE_OR
Definition: circuitlist.h:39
#define CIRCUIT_STATE_CHAN_WAIT
Definition: circuitlist.h:26
#define CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
Definition: circuitlist.h:76
#define CIRCUIT_PURPOSE_S_REND_JOINED
Definition: circuitlist.h:110
#define CIRCUIT_PURPOSE_C_REND_READY
Definition: circuitlist.h:83
#define CIRCUIT_PURPOSE_S_HSDIR_POST
Definition: circuitlist.h:112
#define CIRCUIT_PURPOSE_C_HSDIR_GET
Definition: circuitlist.h:90
#define CIRCUIT_PURPOSE_REND_ESTABLISHED
Definition: circuitlist.h:47
#define CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
Definition: circuitlist.h:79
#define CIRCUIT_PURPOSE_C_INTRODUCING
Definition: circuitlist.h:73
#define CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
Definition: circuitlist.h:101
#define CIRCUIT_PURPOSE_C_ESTABLISH_REND
Definition: circuitlist.h:81
#define CIRCUIT_PURPOSE_C_GENERAL
Definition: circuitlist.h:70
#define CIRCUIT_PURPOSE_HS_VANGUARDS
Definition: circuitlist.h:131
void circuitmux_attach_circuit(circuitmux_t *cmux, circuit_t *circ, cell_direction_t direction)
Definition: circuitmux.c:730
void circuitmux_detach_circuit(circuitmux_t *cmux, circuit_t *circ)
Definition: circuitmux.c:851
void circpad_circuit_free_all_machineinfos(circuit_t *circ)
int circpad_marked_circuit_for_padding(circuit_t *circ, int reason)
Header file for circuitpadding.c.
const circuit_build_times_t * get_circuit_build_times(void)
Definition: circuitstats.c:78
int circuit_build_times_disabled(const or_options_t *options)
Definition: circuitstats.c:117
circuit_build_times_t * get_circuit_build_times_mutable(void)
Definition: circuitstats.c:85
int circuit_build_times_needs_circuits(const circuit_build_times_t *cbt)
Header file for circuitstats.c.
void circuit_build_failed(origin_circuit_t *circ)
Definition: circuituse.c:1772
int circuit_should_use_vanguards(uint8_t purpose)
Definition: circuituse.c:2023
void mark_circuit_unusable_for_new_conns(origin_circuit_t *circ)
Definition: circuituse.c:3120
Header file for circuituse.c.
#define CIRCLAUNCH_NEED_CAPACITY
Definition: circuituse.h:43
#define CIRCLAUNCH_ONEHOP_TUNNEL
Definition: circuituse.h:39
#define CIRCLAUNCH_IS_V3_RP
Definition: circuituse.h:49
#define CIRCLAUNCH_IS_INTERNAL
Definition: circuituse.h:46
#define CIRCLAUNCH_NEED_UPTIME
Definition: circuituse.h:41
uint32_t monotime_coarse_get_stamp(void)
Definition: compat_time.c:844
size_t tor_compress_state_size(const tor_compress_state_t *state)
Definition: compress.c:639
size_t tor_compress_get_total_allocation(void)
Definition: compress.c:458
Headers for compress.c.
size_t tor_lzma_get_total_allocation(void)
Header for compress_lzma.c.
size_t tor_zlib_get_total_allocation(void)
Header for compress_zlib.c.
size_t tor_zstd_get_total_allocation(void)
Header for compress_zstd.c.
const or_options_t * get_options(void)
Definition: config.c:919
Header file for config.c.
void connection_free_(connection_t *conn)
Definition: connection.c:960
Header file for connection.c.
#define CONN_TYPE_DIR
Definition: connection.h:55
#define CONN_TYPE_EXIT
Definition: connection.h:46
int connection_edge_destroy(circid_t circ_id, edge_connection_t *conn)
Header file for connection_edge.c.
Header file for connection_or.c.
int control_event_circuit_status(origin_circuit_t *circ, circuit_status_event_t tp, int reason_code)
Header file for control_events.c.
Circuit-build-stse structure.
void cpath_assert_ok(const crypt_path_t *cp)
Definition: crypt_path.c:80
void cpath_free(crypt_path_t *victim)
Definition: crypt_path.c:159
Header file for crypt_path.c.
reference-counting structure for crypt_path_t
Headers for crypto_dh.c.
Common functions for using (pseudo-)random number generators.
int crypto_rand_int(unsigned int max)
void memwipe(void *mem, uint8_t byte, size_t sz)
Definition: crypto_util.c:55
Common functions for cryptographic routines.
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
#define tor_memneq(a, b, sz)
Definition: di_ops.h:21
#define DIGEST_LEN
Definition: digest_sizes.h:20
Client/server directory connection structure.
dir_connection_t * TO_DIR_CONN(connection_t *c)
Definition: directory.c:88
Header file for directory.c.
Edge-connection structure.
void entry_guard_cancel(circuit_guard_state_t **guard_state_p)
Definition: entrynodes.c:2513
int entry_guards_upgrade_waiting_circuits(guard_selection_t *gs, const smartlist_t *all_circuits_in, smartlist_t *newly_complete_out)
Definition: entrynodes.c:2638
int entry_guard_could_succeed(const circuit_guard_state_t *guard_state)
Definition: entrynodes.c:3575
guard_selection_t * get_guard_selection_info(void)
Definition: entrynodes.c:307
Header file for circuitbuild.c.
#define TR_SUBSYS(name)
Definition: events.h:45
Extend-info structure.
Header for core/or/extendinfo.c.
Half-open connection structure.
Header file for hs_cache.c.
void hs_circ_cleanup_on_close(circuit_t *circ)
Definition: hs_circuit.c:1198
void hs_circ_cleanup_on_free(circuit_t *circ)
Definition: hs_circuit.c:1224
Header file containing circuit data for the whole HS subsystem.
HT_PROTOTYPE(hs_circuitmap_ht, circuit_t, hs_circuitmap_node, hs_circuit_hash_token, hs_circuits_have_same_token)
Header file for hs_circuitmap.c.
Header file containing circuit and connection identifier data for the whole HS subsystem.
void tor_log(int severity, log_domain_mask_t domain, const char *format,...)
Definition: log.c:590
#define log_fn(severity, domain, args,...)
Definition: log.h:283
#define LD_BUG
Definition: log.h:86
#define LD_GENERAL
Definition: log.h:62
#define LD_CIRC
Definition: log.h:82
#define LOG_WARN
Definition: log.h:53
smartlist_t * get_connection_array(void)
Definition: mainloop.c:451
STATIC smartlist_t * connection_array
Definition: mainloop.c:164
void mainloop_schedule_postloop_cleanup(void)
Definition: mainloop.c:1631
Header file for mainloop.c.
void tor_free_(void *mem)
Definition: malloc.c:227
void * tor_reallocarray_(void *ptr, size_t sz1, size_t sz2)
Definition: malloc.c:146
#define tor_free(p)
Definition: malloc.h:52
int32_t networkstatus_get_param(const networkstatus_t *ns, const char *param_name, int32_t default_val, int32_t min_val, int32_t max_val)
Header file for networkstatus.c.
bool node_supports_v3_rendezvous_point(const node_t *node)
Definition: nodelist.c:1271
const node_t * node_get_by_id(const char *identity_digest)
Definition: nodelist.c:226
int nodes_in_same_family(const node_t *node1, const node_t *node2)
Definition: nodelist.c:2195
Header file for nodelist.c.
Header file for ocirc_event.c.
circuit_status_event_t
Definition: ocirc_event.h:19
Header file for onion_crypto.c.
Header file for onion_fast.c.
void onion_pending_remove(or_circuit_t *circ)
Definition: onion_queue.c:316
Header file for onion_queue.c.
Master header file for Tor-specific functionality.
#define DEFAULT_ROUTE_LEN
Definition: or.h:899
#define MAX_RELAY_EARLY_CELLS_PER_CIRCUIT
Definition: or.h:834
#define CELL_MAX_NETWORK_SIZE
Definition: or.h:460
uint32_t circid_t
Definition: or.h:489
#define TO_CIRCUIT(x)
Definition: or.h:845
#define CIRCWINDOW_START
Definition: or.h:382
#define END_STREAM_REASON_FLAG_ALREADY_SENT_CLOSED
Definition: or.h:280
#define TO_CONN(c)
Definition: or.h:616
#define END_CIRC_REASON_FLAG_REMOTE
Definition: or.h:329
@ CELL_DIRECTION_OUT
Definition: or.h:365
@ CELL_DIRECTION_IN
Definition: or.h:364
#define DOWNCAST(to, ptr)
Definition: or.h:109
#define END_CIRC_AT_ORIGIN
Definition: or.h:306
circuit_channel_direction_t
Definition: or.h:375
Origin circuit structure.
Header file for policies.c.
int predicted_ports_prediction_time_remaining(time_t now)
Definition: predict_ports.c:54
Header file for predict_ports.c.
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
void channel_unlink_all_circuits(channel_t *chan, smartlist_t *circuits_out)
Definition: relay.c:2826
void circuit_reset_sendme_randomness(circuit_t *circ)
Definition: relay.c:2070
void cell_queue_clear(cell_queue_t *queue)
Definition: relay.c:2593
void circuit_clear_cell_queue(circuit_t *circ, channel_t *chan)
Definition: relay.c:3257
void cell_queue_init(cell_queue_t *queue)
Definition: relay.c:2585
size_t packed_cell_mem_cost(void)
Definition: relay.c:2686
Header file for relay.c.
Header for relay_crypto.c.
void relay_crypto_assert_ok(const relay_crypto_t *crypto)
Definition: relay_crypto.c:367
void relay_crypto_clear(relay_crypto_t *crypto)
Definition: relay_crypto.c:265
Header file for rendcommon.c.
void rep_hist_buffer_stats_add_circ(circuit_t *circ, time_t end_of_interval)
Definition: rephist.c:1639
Header file for rephist.c.
Header file for routerlist.c.
int routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
Definition: routerset.c:308
Header file for routerset.c.
void smartlist_sort(smartlist_t *sl, int(*compare)(const void **a, const void **b))
Definition: smartlist.c:334
void smartlist_sort_pointers(smartlist_t *sl)
Definition: smartlist.c:594
smartlist_t * smartlist_new(void)
int smartlist_contains(const smartlist_t *sl, const void *element)
void smartlist_add(smartlist_t *sl, void *element)
void smartlist_clear(smartlist_t *sl)
void smartlist_remove(smartlist_t *sl, const void *element)
void smartlist_del(smartlist_t *sl, int idx)
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
#define SMARTLIST_FOREACH(sl, type, var, cmd)
#define SMARTLIST_DEL_CURRENT(sl, var)
time_t timestamp_last_had_circuits
Definition: channel.h:448
unsigned int num_n_circuits
Definition: channel.h:410
char identity_digest[DIGEST_LEN]
Definition: channel.h:378
uint64_t global_identifier
Definition: channel.h:197
circuitmux_t * cmux
Definition: channel.h:397
enum channel_t::@8 reason_for_closing
uint32_t age_tmp
Definition: circuit_st.h:150
unsigned int p_delete_pending
Definition: circuit_st.h:98
int marked_for_close_reason
Definition: circuit_st.h:197
uint8_t state
Definition: circuit_st.h:110
int global_circuitlist_idx
Definition: circuit_st.h:207
int marked_for_close_orig_reason
Definition: circuit_st.h:201
struct create_cell_t * n_chan_create_cell
Definition: circuit_st.h:153
time_t timestamp_dirty
Definition: circuit_st.h:187
cell_queue_t n_chan_cells
Definition: circuit_st.h:81
uint32_t magic
Definition: circuit_st.h:62
smartlist_t * sendme_last_digests
Definition: circuit_st.h:147
uint16_t marked_for_close
Definition: circuit_st.h:189
uint8_t purpose
Definition: circuit_st.h:111
const char * marked_for_close_file
Definition: circuit_st.h:192
unsigned int n_delete_pending
Definition: circuit_st.h:101
struct timeval timestamp_began
Definition: circuit_st.h:165
int deliver_window
Definition: circuit_st.h:121
int package_window
Definition: circuit_st.h:116
smartlist_t * testing_cell_stats
Definition: circuit_st.h:212
struct timeval timestamp_created
Definition: circuit_st.h:168
channel_t * n_chan
Definition: circuit_st.h:69
extend_info_t * n_hop
Definition: circuit_st.h:87
circid_t n_circ_id
Definition: circuit_st.h:78
struct buf_t * inbuf
struct connection_t * linked_conn
int conn_array_index
Definition: connection_st.h:97
unsigned int type
Definition: connection_st.h:50
struct buf_t * outbuf
uint16_t marked_for_close
extend_info_t * chosen_exit
uint8_t state
Definition: crypt_path_st.h:68
struct crypt_path_t * next
Definition: crypt_path_st.h:72
extend_info_t * extend_info
Definition: crypt_path_st.h:61
struct tor_compress_state_t * compress_state
struct edge_connection_t * next_stream
unsigned int edge_has_sent_end
struct circuit_t * on_circuit
char identity_digest[DIGEST_LEN]
Definition: node_st.h:34
edge_connection_t * resolving_streams
Definition: or_circuit_st.h:42
channel_t * p_chan
Definition: or_circuit_st.h:37
unsigned int remaining_relay_early_cells
Definition: or_circuit_st.h:57
struct workqueue_entry_t * workqueue_entry
Definition: or_circuit_st.h:30
circid_t p_circ_id
Definition: or_circuit_st.h:33
cell_queue_t p_chan_cells
Definition: or_circuit_st.h:35
struct or_circuit_t * rend_splice
Definition: or_circuit_st.h:50
edge_connection_t * n_streams
Definition: or_circuit_st.h:39
relay_crypto_t crypto
Definition: or_circuit_st.h:46
uint64_t MaxMemInQueues
struct routerset_t * ExcludeNodes
struct hs_ident_circuit_t * hs_ident
edge_connection_t * p_streams
unsigned int isolation_values_set
unsigned int remaining_relay_early_cells
smartlist_t * prepend_policy
crypt_path_t * cpath
cpath_build_state_t * build_state
struct circuit_guard_state_t * guard_state
streamid_t next_stream_id
smartlist_t * half_streams
uint32_t inserted_timestamp
Definition: cell_queue_st.h:22
Definition: or.h:817
#define STATIC
Definition: testsupport.h:32
#define MOCK_IMPL(rv, funcname, arglist)
Definition: testsupport.h:133
void tor_gettimeofday(struct timeval *timeval)
Integer definitions used throughout Tor.
#define FALLTHROUGH_UNLESS_ALL_BUGS_ARE_FATAL
Definition: util_bug.h:260
#define tor_assert(expr)
Definition: util_bug.h:102
#define tor_fragile_assert()
Definition: util_bug.h:270
int tor_digest_is_zero(const char *digest)
Definition: util_string.c:96