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 */
10 * \brief Manage global structures that list and index circuits, and
11 * look up circuits within them.
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.
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
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().
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().
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.
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().
49 * This module is also the entry point for our out-of-memory handler
50 * logic, which was originally circuit-focused.
52 #define CIRCUITLIST_PRIVATE
53 #define OCIRC_EVENT_PRIVATE
54 #include "lib/cc/torint.h" /* TOR_PRIuSZ */
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"
68 #include "core/mainloop/connection.h"
69 #include "app/config/config.h"
70 #include "core/or/connection_edge.h"
71 #include "core/or/connection_or.h"
72 #include "feature/control/control_events.h"
73 #include "lib/crypt_ops/crypto_rand.h"
74 #include "lib/crypt_ops/crypto_util.h"
75 #include "lib/crypt_ops/crypto_dh.h"
76 #include "feature/dircommon/directory.h"
77 #include "feature/client/entrynodes.h"
78 #include "core/mainloop/mainloop.h"
79 #include "feature/hs/hs_cache.h"
80 #include "feature/hs/hs_circuit.h"
81 #include "feature/hs/hs_circuitmap.h"
82 #include "feature/hs/hs_ident.h"
83 #include "feature/nodelist/networkstatus.h"
84 #include "feature/nodelist/nodelist.h"
85 #include "feature/relay/onion_queue.h"
86 #include "core/crypto/onion_crypto.h"
87 #include "core/crypto/onion_fast.h"
88 #include "core/or/policies.h"
89 #include "core/or/relay.h"
90 #include "core/crypto/relay_crypto.h"
91 #include "feature/rend/rendcommon.h"
92 #include "feature/stats/predict_ports.h"
93 #include "feature/stats/bwhist.h"
94 #include "feature/stats/rephist.h"
95 #include "feature/nodelist/routerlist.h"
96 #include "feature/nodelist/routerset.h"
97 #include "core/or/channelpadding.h"
98 #include "lib/compress/compress.h"
99 #include "lib/compress/compress_lzma.h"
100 #include "lib/compress/compress_zlib.h"
101 #include "lib/compress/compress_zstd.h"
102 #include "lib/buf/buffers.h"
104 #include "core/or/ocirc_event.h"
108 #include "core/or/cpath_build_state_st.h"
109 #include "core/or/crypt_path_reference_st.h"
110 #include "feature/dircommon/dir_connection_st.h"
111 #include "core/or/edge_connection_st.h"
112 #include "core/or/half_edge_st.h"
113 #include "core/or/extend_info_st.h"
114 #include "core/or/or_circuit_st.h"
115 #include "core/or/origin_circuit_st.h"
117 /********* START VARIABLES **********/
119 /** A global list of all circuits at this hop. */
120 static smartlist_t
*global_circuitlist
= NULL
;
122 /** A global list of all origin circuits. Every element of this is also
123 * an element of global_circuitlist. */
124 static smartlist_t
*global_origin_circuit_list
= NULL
;
126 /** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
127 static smartlist_t
*circuits_pending_chans
= NULL
;
129 /** List of all the (origin) circuits whose state is
130 * CIRCUIT_STATE_GUARD_WAIT. */
131 static smartlist_t
*circuits_pending_other_guards
= NULL
;
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. */
135 static smartlist_t
*circuits_pending_close
= NULL
;
137 static void circuit_about_to_free_atexit(circuit_t
*circ
);
138 static void circuit_about_to_free(circuit_t
*circ
);
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.
146 static int any_opened_circs_cached_val
= 0;
148 /********* END VARIABLES ************/
150 /* Implement circuit handle helpers. */
151 HANDLE_IMPL(circuit
, circuit_t
,)
154 TO_OR_CIRCUIT(circuit_t
*x
)
156 tor_assert(x
->magic
== OR_CIRCUIT_MAGIC
);
157 return DOWNCAST(or_circuit_t
, x
);
160 CONST_TO_OR_CIRCUIT(const circuit_t
*x
)
162 tor_assert(x
->magic
== OR_CIRCUIT_MAGIC
);
163 return DOWNCAST(or_circuit_t
, x
);
166 TO_ORIGIN_CIRCUIT(circuit_t
*x
)
168 tor_assert(x
->magic
== ORIGIN_CIRCUIT_MAGIC
);
169 return DOWNCAST(origin_circuit_t
, x
);
171 const origin_circuit_t
*
172 CONST_TO_ORIGIN_CIRCUIT(const circuit_t
*x
)
174 tor_assert(x
->magic
== ORIGIN_CIRCUIT_MAGIC
);
175 return DOWNCAST(origin_circuit_t
, x
);
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.) */
180 typedef struct chan_circid_circuit_map_t
{
181 HT_ENTRY(chan_circid_circuit_map_t
) node
;
185 /* For debugging 12184: when was this placeholder item added? */
186 time_t made_placeholder_at
;
187 } chan_circid_circuit_map_t
;
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.
193 chan_circid_entries_eq_(chan_circid_circuit_map_t
*a
,
194 chan_circid_circuit_map_t
*b
)
196 return a
->chan
== b
->chan
&& a
->circ_id
== b
->circ_id
;
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
202 chan_circid_entry_hash_(chan_circid_circuit_map_t
*a
)
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
;
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
));
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
,
219 chan_circid_entry_hash_
, chan_circid_entries_eq_
);
220 HT_GENERATE2(chan_circid_map
, chan_circid_circuit_map_t
, node
,
221 chan_circid_entry_hash_
, chan_circid_entries_eq_
, 0.6,
222 tor_reallocarray_
, tor_free_
);
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
228 static chan_circid_circuit_map_t
*_last_circid_chan_ent
= NULL
;
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. */
235 circuit_set_circid_chan_helper(circuit_t
*circ
, int direction
,
239 chan_circid_circuit_map_t search
;
240 chan_circid_circuit_map_t
*found
;
241 channel_t
*old_chan
, **chan_ptr
;
242 circid_t old_id
, *circid_ptr
;
243 int make_active
, attached
= 0;
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;
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;
255 old_chan
= *chan_ptr
;
256 old_id
= *circid_ptr
;
258 if (id
== old_id
&& chan
== old_chan
)
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
;
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).
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
);
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
);
288 if (direction
== CELL_DIRECTION_OUT
) {
289 /* One fewer circuits use old_chan as n_chan */
290 --(old_chan
->num_n_circuits
);
292 /* One fewer circuits use old_chan as p_chan */
293 --(old_chan
->num_p_circuits
);
298 /* Change the values only after we have possibly made the circuit inactive
299 * on the previous chan. */
306 /* now add the new one to the conn-circid map */
309 found
= HT_FIND(chan_circid_map
, &chan_circid_map
, &search
);
311 found
->circuit
= circ
;
312 found
->made_placeholder_at
= 0;
314 found
= tor_malloc_zero(sizeof(chan_circid_circuit_map_t
));
317 found
->circuit
= circ
;
318 HT_INSERT(chan_circid_map
, &chan_circid_map
, found
);
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
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
);
334 * This is a no-op if we have no cells, but if we do it marks us active to
337 if (make_active
&& attached
)
338 update_circuit_on_cmux(circ
, direction
);
340 /* Adjust circuit counts on new channel */
341 if (direction
== CELL_DIRECTION_OUT
) {
342 ++chan
->num_n_circuits
;
344 ++chan
->num_p_circuits
;
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
353 channel_mark_circid_unusable(channel_t
*chan
, circid_t id
)
355 chan_circid_circuit_map_t search
;
356 chan_circid_circuit_map_t
*ent
;
358 /* See if there's an entry there. That wouldn't be good. */
359 memset(&search
, 0, sizeof(search
));
362 ent
= HT_FIND(chan_circid_map
, &chan_circid_map
, &search
);
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
);
369 /* It's already marked. */
370 if (!ent
->made_placeholder_at
)
371 ent
->made_placeholder_at
= approx_time();
373 ent
= tor_malloc_zero(sizeof(chan_circid_circuit_map_t
));
376 /* leave circuit at NULL. */
377 ent
->made_placeholder_at
= approx_time();
378 HT_INSERT(chan_circid_map
, &chan_circid_map
, ent
);
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.
386 channel_mark_circid_usable(channel_t
*chan
, circid_t id
)
388 chan_circid_circuit_map_t search
;
389 chan_circid_circuit_map_t
*ent
;
391 /* See if there's an entry there. That wouldn't be good. */
392 memset(&search
, 0, sizeof(search
));
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
);
401 if (_last_circid_chan_ent
== ent
)
402 _last_circid_chan_ent
= NULL
;
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. */
409 channel_note_destroy_pending(channel_t
*chan
, circid_t id
)
411 circuit_t
*circ
= circuit_get_by_circid_channel_even_if_marked(id
,chan
);
413 if (circ
->n_chan
== chan
&& circ
->n_circ_id
== id
) {
414 circ
->n_delete_pending
= 1;
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;
423 channel_mark_circid_unusable(chan
, id
);
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. */
429 channel_note_destroy_not_pending
,(channel_t
*chan
, circid_t id
))
431 circuit_t
*circ
= circuit_get_by_circid_channel_even_if_marked(id
,chan
);
433 if (circ
->n_chan
== chan
&& circ
->n_circ_id
== id
) {
434 circ
->n_delete_pending
= 0;
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;
441 /* XXXX this shouldn't happen; log a bug here. */
444 channel_mark_circid_usable(chan
, id
);
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. */
451 circuit_set_p_circid_chan(or_circuit_t
*or_circ
, circid_t id
,
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
;
458 circuit_set_circid_chan_helper(circ
, CELL_DIRECTION_IN
, id
, chan
);
461 chan
->timestamp_last_had_circuits
= approx_time();
464 if (circ
->p_delete_pending
&& old_chan
) {
465 channel_mark_circid_unusable(old_chan
, old_id
);
466 circ
->p_delete_pending
= 0;
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. */
474 circuit_set_n_circid_chan(circuit_t
*circ
, circid_t id
,
477 channel_t
*old_chan
= circ
->n_chan
;
478 circid_t old_id
= circ
->n_circ_id
;
480 circuit_set_circid_chan_helper(circ
, CELL_DIRECTION_OUT
, id
, chan
);
483 chan
->timestamp_last_had_circuits
= approx_time();
486 if (circ
->n_delete_pending
&& old_chan
) {
487 channel_mark_circid_unusable(old_chan
, old_id
);
488 circ
->n_delete_pending
= 0;
493 * Helper function to publish a message about events on an origin circuit
495 * Publishes a message to subscribers of origin circuit events, and
496 * sends the control event.
499 circuit_event_status(origin_circuit_t
*circ
, circuit_status_event_t tp
,
502 ocirc_cevent_msg_t
*msg
= tor_malloc(sizeof(*msg
));
506 msg
->gid
= circ
->global_identifier
;
508 msg
->reason
= reason_code
;
509 msg
->onehop
= circ
->build_state
->onehop_tunnel
;
511 ocirc_cevent_publish(msg
);
512 return control_event_circuit_status(circ
, tp
, reason_code
);
516 * Helper function to publish a state change message
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
523 circuit_state_publish(const circuit_t
*circ
)
525 ocirc_state_msg_t
*msg
= tor_malloc(sizeof(*msg
));
526 const origin_circuit_t
*ocirc
;
528 tor_assert(CIRCUIT_IS_ORIGIN(circ
));
529 ocirc
= CONST_TO_ORIGIN_CIRCUIT(circ
);
530 /* Only inbound OR circuits can be in this state, not origin circuits. */
531 tor_assert(circ
->state
!= CIRCUIT_STATE_ONIONSKIN_PENDING
);
533 msg
->gid
= ocirc
->global_identifier
;
534 msg
->state
= circ
->state
;
535 msg
->onehop
= ocirc
->build_state
->onehop_tunnel
;
537 ocirc_state_publish(msg
);
540 /** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
541 * it from lists as appropriate. */
543 circuit_set_state(circuit_t
*circ
, uint8_t state
)
546 if (state
== circ
->state
)
548 if (PREDICT_UNLIKELY(!circuits_pending_chans
))
549 circuits_pending_chans
= smartlist_new();
550 if (PREDICT_UNLIKELY(!circuits_pending_other_guards
))
551 circuits_pending_other_guards
= smartlist_new();
552 if (circ
->state
== CIRCUIT_STATE_CHAN_WAIT
) {
553 /* remove from waiting-circuit list. */
554 smartlist_remove(circuits_pending_chans
, circ
);
556 if (state
== CIRCUIT_STATE_CHAN_WAIT
) {
557 /* add to waiting-circuit list. */
558 smartlist_add(circuits_pending_chans
, circ
);
560 if (circ
->state
== CIRCUIT_STATE_GUARD_WAIT
) {
561 smartlist_remove(circuits_pending_other_guards
, circ
);
563 if (state
== CIRCUIT_STATE_GUARD_WAIT
) {
564 smartlist_add(circuits_pending_other_guards
, circ
);
566 if (state
== CIRCUIT_STATE_GUARD_WAIT
|| state
== CIRCUIT_STATE_OPEN
)
567 tor_assert(!circ
->n_chan_create_cell
);
569 tor_trace(TR_SUBSYS(circuit
), TR_EV(change_state
), circ
, circ
->state
, state
);
571 if (CIRCUIT_IS_ORIGIN(circ
))
572 circuit_state_publish(circ
);
575 /** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
576 * the given connection. */
578 circuit_get_all_pending_on_channel(smartlist_t
*out
, channel_t
*chan
)
583 if (!circuits_pending_chans
)
586 SMARTLIST_FOREACH_BEGIN(circuits_pending_chans
, circuit_t
*, circ
) {
587 if (circ
->marked_for_close
)
591 tor_assert(circ
->state
== CIRCUIT_STATE_CHAN_WAIT
);
592 if (tor_digest_is_zero(circ
->n_hop
->identity_digest
)) {
593 /* Look at addr/port. This is an unkeyed connection. */
594 if (!channel_matches_extend_info(chan
, circ
->n_hop
))
597 /* We expected a key. See if it's the right one. */
598 if (tor_memneq(chan
->identity_digest
,
599 circ
->n_hop
->identity_digest
, DIGEST_LEN
))
602 smartlist_add(out
, circ
);
603 } SMARTLIST_FOREACH_END(circ
);
606 /** Return the number of circuits in state CHAN_WAIT, waiting for the given
609 circuit_count_pending_on_channel(channel_t
*chan
)
612 smartlist_t
*sl
= smartlist_new();
616 circuit_get_all_pending_on_channel(sl
, chan
);
617 cnt
= smartlist_len(sl
);
619 log_debug(LD_CIRC
,"or_conn to %s, %d pending circs",
620 channel_describe_peer(chan
),
625 /** Remove <b>origin_circ</b> from the global list of origin circuits.
626 * Called when we are freeing a circuit.
629 circuit_remove_from_origin_circuit_list(origin_circuit_t
*origin_circ
)
631 int origin_idx
= origin_circ
->global_origin_circuit_list_idx
;
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
);
638 smartlist_del(global_origin_circuit_list
, origin_idx
);
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
;
644 origin_circ
->global_origin_circuit_list_idx
= -1;
647 /** Add <b>origin_circ</b> to the global list of origin circuits. Called
648 * when creating the circuit. */
650 circuit_add_to_origin_circuit_list(origin_circuit_t
*origin_circ
)
652 tor_assert(origin_circ
->global_origin_circuit_list_idx
== -1);
653 smartlist_t
*lst
= circuit_get_global_origin_circuit_list();
654 smartlist_add(lst
, origin_circ
);
655 origin_circ
->global_origin_circuit_list_idx
= smartlist_len(lst
) - 1;
658 /** Detach from the global circuit list, and deallocate, all
659 * circuits that have been marked for close.
662 circuit_close_all_marked(void)
664 if (circuits_pending_close
== NULL
)
667 smartlist_t
*lst
= circuit_get_global_list();
668 SMARTLIST_FOREACH_BEGIN(circuits_pending_close
, circuit_t
*, circ
) {
669 tor_assert(circ
->marked_for_close
);
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
;
678 circ
->global_circuitlist_idx
= -1;
680 /* Remove it from the origin circuit list, if appropriate. */
681 if (CIRCUIT_IS_ORIGIN(circ
)) {
682 circuit_remove_from_origin_circuit_list(TO_ORIGIN_CIRCUIT(circ
));
685 circuit_about_to_free(circ
);
687 } SMARTLIST_FOREACH_END(circ
);
689 smartlist_clear(circuits_pending_close
);
692 /** Return a pointer to the global list of circuits. */
693 MOCK_IMPL(smartlist_t
*,
694 circuit_get_global_list
,(void))
696 if (NULL
== global_circuitlist
)
697 global_circuitlist
= smartlist_new();
698 return global_circuitlist
;
701 /** Return a pointer to the global list of origin circuits. */
703 circuit_get_global_origin_circuit_list(void)
705 if (NULL
== global_origin_circuit_list
)
706 global_origin_circuit_list
= smartlist_new();
707 return global_origin_circuit_list
;
711 * Return true if we have any opened general-purpose 3 hop
714 * The result from this function is cached for use by
715 * circuit_any_opened_circuits_cached().
718 circuit_any_opened_circuits(void)
720 SMARTLIST_FOREACH_BEGIN(circuit_get_global_origin_circuit_list(),
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
) {
728 circuit_cache_opened_circuit_state(1);
731 } SMARTLIST_FOREACH_END(next_circ
);
733 circuit_cache_opened_circuit_state(0);
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
744 circuit_cache_opened_circuit_state(int circuits_are_opened
)
746 any_opened_circs_cached_val
= circuits_are_opened
;
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).
755 circuit_any_opened_circuits_cached(void)
757 return any_opened_circs_cached_val
;
760 /** Function to make circ-\>state human-readable */
762 circuit_state_to_string(int 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 "
771 case CIRCUIT_STATE_OPEN
: return "open";
773 log_warn(LD_BUG
, "Unknown circuit state %d", state
);
774 tor_snprintf(buf
, sizeof(buf
), "unknown state [%d]", state
);
779 /** Map a circuit purpose to a string suitable to be displayed to a
782 circuit_purpose_to_controller_string(uint8_t purpose
)
786 case CIRCUIT_PURPOSE_OR
:
787 case CIRCUIT_PURPOSE_INTRO_POINT
:
788 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
789 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
790 return "SERVER"; /* A controller should never see these, actually. */
792 case CIRCUIT_PURPOSE_C_GENERAL
:
795 case CIRCUIT_PURPOSE_C_HSDIR_GET
:
796 return "HS_CLIENT_HSDIR";
798 case CIRCUIT_PURPOSE_C_INTRODUCING
:
799 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
800 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
801 return "HS_CLIENT_INTRO";
803 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
804 case CIRCUIT_PURPOSE_C_REND_READY
:
805 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
806 case CIRCUIT_PURPOSE_C_REND_JOINED
:
807 return "HS_CLIENT_REND";
809 case CIRCUIT_PURPOSE_S_HSDIR_POST
:
810 return "HS_SERVICE_HSDIR";
812 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
813 case CIRCUIT_PURPOSE_S_INTRO
:
814 return "HS_SERVICE_INTRO";
816 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
817 case CIRCUIT_PURPOSE_S_REND_JOINED
:
818 return "HS_SERVICE_REND";
820 case CIRCUIT_PURPOSE_TESTING
:
822 case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
:
823 return "MEASURE_TIMEOUT";
824 case CIRCUIT_PURPOSE_CONTROLLER
:
826 case CIRCUIT_PURPOSE_PATH_BIAS_TESTING
:
827 return "PATH_BIAS_TESTING";
828 case CIRCUIT_PURPOSE_HS_VANGUARDS
:
829 return "HS_VANGUARDS";
830 case CIRCUIT_PURPOSE_C_CIRCUIT_PADDING
:
831 return "CIRCUIT_PADDING";
834 tor_snprintf(buf
, sizeof(buf
), "UNKNOWN_%d", (int)purpose
);
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. */
843 circuit_purpose_to_controller_hs_state_string(uint8_t purpose
)
848 log_fn(LOG_WARN
, LD_BUG
,
849 "Unrecognized circuit purpose: %d",
851 tor_fragile_assert();
852 FALLTHROUGH_UNLESS_ALL_BUGS_ARE_FATAL
;
854 case CIRCUIT_PURPOSE_OR
:
855 case CIRCUIT_PURPOSE_C_GENERAL
:
856 case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
:
857 case CIRCUIT_PURPOSE_TESTING
:
858 case CIRCUIT_PURPOSE_CONTROLLER
:
859 case CIRCUIT_PURPOSE_PATH_BIAS_TESTING
:
860 case CIRCUIT_PURPOSE_HS_VANGUARDS
:
861 case CIRCUIT_PURPOSE_C_CIRCUIT_PADDING
:
864 case CIRCUIT_PURPOSE_INTRO_POINT
:
865 return "OR_HSSI_ESTABLISHED";
866 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
867 return "OR_HSCR_ESTABLISHED";
868 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
869 return "OR_HS_R_JOINED";
871 case CIRCUIT_PURPOSE_C_HSDIR_GET
:
872 case CIRCUIT_PURPOSE_C_INTRODUCING
:
873 return "HSCI_CONNECTING";
874 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
875 return "HSCI_INTRO_SENT";
876 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
879 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
880 return "HSCR_CONNECTING";
881 case CIRCUIT_PURPOSE_C_REND_READY
:
882 return "HSCR_ESTABLISHED_IDLE";
883 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
884 return "HSCR_ESTABLISHED_WAITING";
885 case CIRCUIT_PURPOSE_C_REND_JOINED
:
886 return "HSCR_JOINED";
888 case CIRCUIT_PURPOSE_S_HSDIR_POST
:
889 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
890 return "HSSI_CONNECTING";
891 case CIRCUIT_PURPOSE_S_INTRO
:
892 return "HSSI_ESTABLISHED";
894 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
895 return "HSSR_CONNECTING";
896 case CIRCUIT_PURPOSE_S_REND_JOINED
:
897 return "HSSR_JOINED";
901 /** Return a human-readable string for the circuit purpose <b>purpose</b>. */
903 circuit_purpose_to_string(uint8_t purpose
)
909 case CIRCUIT_PURPOSE_OR
:
910 return "Circuit at relay";
911 case CIRCUIT_PURPOSE_INTRO_POINT
:
912 return "Acting as intro point";
913 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
914 return "Acting as rendezvous (pending)";
915 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
916 return "Acting as rendezvous (established)";
917 case CIRCUIT_PURPOSE_C_GENERAL
:
918 return "General-purpose client";
919 case CIRCUIT_PURPOSE_C_INTRODUCING
:
920 return "Hidden service client: Connecting to intro point";
921 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
922 return "Hidden service client: Waiting for ack from intro point";
923 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
924 return "Hidden service client: Received ack from intro point";
925 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
926 return "Hidden service client: Establishing rendezvous point";
927 case CIRCUIT_PURPOSE_C_REND_READY
:
928 return "Hidden service client: Pending rendezvous point";
929 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
930 return "Hidden service client: Pending rendezvous point (ack received)";
931 case CIRCUIT_PURPOSE_C_REND_JOINED
:
932 return "Hidden service client: Active rendezvous point";
933 case CIRCUIT_PURPOSE_C_HSDIR_GET
:
934 return "Hidden service client: Fetching HS descriptor";
936 case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
:
937 return "Measuring circuit timeout";
939 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
940 return "Hidden service: Establishing introduction point";
941 case CIRCUIT_PURPOSE_S_INTRO
:
942 return "Hidden service: Introduction point";
943 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
944 return "Hidden service: Connecting to rendezvous point";
945 case CIRCUIT_PURPOSE_S_REND_JOINED
:
946 return "Hidden service: Active rendezvous point";
947 case CIRCUIT_PURPOSE_S_HSDIR_POST
:
948 return "Hidden service: Uploading HS descriptor";
950 case CIRCUIT_PURPOSE_TESTING
:
951 return "Testing circuit";
953 case CIRCUIT_PURPOSE_CONTROLLER
:
954 return "Circuit made by controller";
956 case CIRCUIT_PURPOSE_PATH_BIAS_TESTING
:
957 return "Path-bias testing circuit";
959 case CIRCUIT_PURPOSE_HS_VANGUARDS
:
960 return "Hidden service: Pre-built vanguard circuit";
962 case CIRCUIT_PURPOSE_C_CIRCUIT_PADDING
:
963 return "Circuit kept open for padding";
966 tor_snprintf(buf
, sizeof(buf
), "UNKNOWN_%d", (int)purpose
);
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. */
975 circuit_initial_package_window(void)
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. */
982 num
= CIRCWINDOW_START
;
986 /** Initialize the common elements in a circuit_t, and add it to the global
989 init_circuit_base(circuit_t
*circ
)
991 tor_gettimeofday(&circ
->timestamp_created
);
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
;
998 circ
->package_window
= circuit_initial_package_window();
999 circ
->deliver_window
= CIRCWINDOW_START
;
1000 circuit_reset_sendme_randomness(circ
);
1001 cell_queue_init(&circ
->n_chan_cells
);
1003 smartlist_add(circuit_get_global_list(), circ
);
1004 circ
->global_circuitlist_idx
= smartlist_len(circuit_get_global_list()) - 1;
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)
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.
1018 origin_circuit_new(void)
1020 origin_circuit_t
*circ
;
1021 /* never zero, since a global ID of 0 is treated specially by the
1023 static uint32_t n_circuits_allocated
= 1;
1025 circ
= tor_malloc_zero(sizeof(origin_circuit_t
));
1026 circ
->base_
.magic
= ORIGIN_CIRCUIT_MAGIC
;
1028 circ
->next_stream_id
= crypto_rand_int(1<<16);
1029 circ
->global_identifier
= n_circuits_allocated
++;
1030 circ
->remaining_relay_early_cells
= MAX_RELAY_EARLY_CELLS_PER_CIRCUIT
;
1031 circ
->remaining_relay_early_cells
-= crypto_rand_int(2);
1033 init_circuit_base(TO_CIRCUIT(circ
));
1035 /* Add to origin-list. */
1036 circ
->global_origin_circuit_list_idx
= -1;
1037 circuit_add_to_origin_circuit_list(circ
);
1039 circuit_build_times_update_last_circ(get_circuit_build_times_mutable());
1041 if (! circuit_build_times_disabled(get_options()) &&
1042 circuit_build_times_needs_circuits(get_circuit_build_times())) {
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",
1047 DFLT_IDLE_TIMEOUT_WHILE_LEARNING
,
1048 MIN_IDLE_TIMEOUT_WHILE_LEARNING
,
1049 MAX_IDLE_TIMEOUT_WHILE_LEARNING
);
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.
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
=
1059 predicted_ports_prediction_time_remaining(time(NULL
));
1060 circ
->circuit_idle_timeout
= prediction_time_remaining
+1+
1061 crypto_rand_int(1+prediction_time_remaining
/20);
1063 if (circ
->circuit_idle_timeout
<= 0) {
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",
1071 DFLT_IDLE_TIMEOUT_WHILE_LEARNING
,
1072 MIN_IDLE_TIMEOUT_WHILE_LEARNING
,
1073 MAX_IDLE_TIMEOUT_WHILE_LEARNING
);
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
);
1084 tor_trace(TR_SUBSYS(circuit
), TR_EV(new_origin
), circ
);
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. */
1091 or_circuit_new(circid_t p_circ_id
, channel_t
*p_chan
)
1096 circ
= tor_malloc_zero(sizeof(or_circuit_t
));
1097 circ
->base_
.magic
= OR_CIRCUIT_MAGIC
;
1100 circuit_set_p_circid_chan(circ
, p_circ_id
, p_chan
);
1102 circ
->remaining_relay_early_cells
= MAX_RELAY_EARLY_CELLS_PER_CIRCUIT
;
1103 cell_queue_init(&circ
->p_chan_cells
);
1105 init_circuit_base(TO_CIRCUIT(circ
));
1107 tor_trace(TR_SUBSYS(circuit
), TR_EV(new_or
), circ
);
1111 /** Free all storage held in circ->testing_cell_stats */
1113 circuit_clear_testing_cell_stats(circuit_t
*circ
)
1115 if (!circ
|| !circ
->testing_cell_stats
)
1117 SMARTLIST_FOREACH(circ
->testing_cell_stats
, testing_cell_stats_entry_t
*,
1118 ent
, tor_free(ent
));
1119 smartlist_free(circ
->testing_cell_stats
);
1120 circ
->testing_cell_stats
= NULL
;
1123 /** Deallocate space associated with circ.
1126 circuit_free_(circuit_t
*circ
)
1128 circid_t n_circ_id
= 0;
1131 int should_free
= 1;
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
;
1138 circuit_clear_testing_cell_stats(circ
);
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. */
1144 hs_circ_cleanup_on_free(circ
);
1146 if (CIRCUIT_IS_ORIGIN(circ
)) {
1147 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
1149 memlen
= sizeof(origin_circuit_t
);
1150 tor_assert(circ
->magic
== ORIGIN_CIRCUIT_MAGIC
);
1152 circuit_remove_from_origin_circuit_list(ocirc
);
1154 if (ocirc
->half_streams
) {
1155 SMARTLIST_FOREACH_BEGIN(ocirc
->half_streams
, half_edge_t
*,
1157 half_edge_free(half_conn
);
1158 } SMARTLIST_FOREACH_END(half_conn
);
1159 smartlist_free(ocirc
->half_streams
);
1162 if (ocirc
->build_state
) {
1163 extend_info_free(ocirc
->build_state
->chosen_exit
);
1165 tor_free(ocirc
->build_state
);
1167 /* Cancel before freeing, if we haven't already succeeded or failed. */
1168 if (ocirc
->guard_state
) {
1169 entry_guard_cancel(ô
->guard_state
);
1171 circuit_guard_state_free(ocirc
->guard_state
);
1173 circuit_clear_cpath(ocirc
);
1175 crypto_pk_free(ocirc
->intro_key
);
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
;
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
);
1187 if (ocirc
->socks_password
) {
1188 memwipe(ocirc
->socks_password
, 0x06, ocirc
->socks_password_len
);
1189 tor_free(ocirc
->socks_password
);
1191 addr_policy_list_free(ocirc
->prepend_policy
);
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
));
1198 memlen
= sizeof(or_circuit_t
);
1199 tor_assert(circ
->magic
== OR_CIRCUIT_MAGIC
);
1201 should_free
= (ocirc
->workqueue_entry
== NULL
);
1203 relay_crypto_clear(ô
->crypto
);
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
;
1211 /* remove from map. */
1212 circuit_set_p_circid_chan(ocirc
, 0, NULL
);
1214 /* Clear cell queue _after_ removing it from the map. Otherwise our
1215 * "active" checks will be violated. */
1216 cell_queue_clear(ô
->p_chan_cells
);
1219 extend_info_free(circ
->n_hop
);
1220 tor_free(circ
->n_chan_create_cell
);
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
);
1226 smartlist_del(global_circuitlist
, idx
);
1227 if (idx
< smartlist_len(global_circuitlist
)) {
1228 c2
= smartlist_get(global_circuitlist
, idx
);
1229 c2
->global_circuitlist_idx
= idx
;
1233 /* Remove from map. */
1234 circuit_set_n_circid_chan(circ
, 0, NULL
);
1236 /* Clear cell queue _after_ removing it from the map. Otherwise our
1237 * "active" checks will be violated. */
1238 cell_queue_clear(&circ
->n_chan_cells
);
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
);
1246 log_info(LD_CIRC
, "Circuit %u (id: %" PRIu32
") has been freed.",
1248 CIRCUIT_IS_ORIGIN(circ
) ?
1249 TO_ORIGIN_CIRCUIT(circ
)->global_identifier
: 0);
1251 /* Free any circuit padding structures */
1252 circpad_circuit_free_all_machineinfos(circ
);
1254 /* Clear all dangling handle references. */
1255 circuit_handles_clear(circ
);
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
);
1262 memwipe(mem
, 0xAA, memlen
); /* poison memory */
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.
1270 memwipe(mem
, 0xAA, memlen
);
1271 circ
->magic
= DEAD_CIRCUIT_MAGIC
;
1275 /** Deallocate the linked list circ-><b>cpath</b>, and remove the cpath from
1278 circuit_clear_cpath(origin_circuit_t
*circ
)
1280 crypt_path_t
*victim
, *head
, *cpath
;
1282 head
= cpath
= circ
->cpath
;
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
) {
1291 cpath
= victim
->next
;
1300 /** Release all storage held by circuits. */
1302 circuit_free_all(void)
1304 smartlist_t
*lst
= circuit_get_global_list();
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
;
1312 connection_free_(TO_CONN(or_circ
->resolving_streams
));
1313 or_circ
->resolving_streams
= next_conn
;
1316 tmp
->global_circuitlist_idx
= -1;
1317 circuit_about_to_free_atexit(tmp
);
1319 SMARTLIST_DEL_CURRENT(lst
, tmp
);
1320 } SMARTLIST_FOREACH_END(tmp
);
1322 smartlist_free(lst
);
1323 global_circuitlist
= NULL
;
1325 smartlist_free(global_origin_circuit_list
);
1326 global_origin_circuit_list
= NULL
;
1328 smartlist_free(circuits_pending_chans
);
1329 circuits_pending_chans
= NULL
;
1331 smartlist_free(circuits_pending_close
);
1332 circuits_pending_close
= NULL
;
1334 smartlist_free(circuits_pending_other_guards
);
1335 circuits_pending_other_guards
= NULL
;
1338 chan_circid_circuit_map_t
**elt
, **next
, *c
;
1339 for (elt
= HT_START(chan_circid_map
, &chan_circid_map
);
1343 next
= HT_NEXT_RMV(chan_circid_map
, &chan_circid_map
, elt
);
1345 tor_assert(c
->circuit
== NULL
);
1349 HT_CLEAR(chan_circid_map
, &chan_circid_map
);
1352 /** A helper function for circuit_dump_by_conn() below. Log a bunch
1353 * of information about circuit <b>circ</b>.
1356 circuit_dump_conn_details(int severity
,
1358 int conn_array_index
,
1360 circid_t this_circid
,
1361 circid_t other_circid
)
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
));
1373 /** Log, at severity <b>severity</b>, information about each circuit
1374 * that is connected to <b>conn</b>.
1377 circuit_dump_by_conn(connection_t
*conn
, int severity
)
1379 edge_connection_t
*tmpconn
;
1381 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
1382 circid_t n_circ_id
= circ
->n_circ_id
, p_circ_id
= 0;
1384 if (circ
->marked_for_close
) {
1388 if (!CIRCUIT_IS_ORIGIN(circ
)) {
1389 p_circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
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
);
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
);
1412 SMARTLIST_FOREACH_END(circ
);
1415 /** Return the circuit whose global ID is <b>id</b>, or NULL if no
1416 * such circuit exists. */
1418 circuit_get_by_global_id(uint32_t id
)
1420 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
1421 if (CIRCUIT_IS_ORIGIN(circ
) &&
1422 TO_ORIGIN_CIRCUIT(circ
)->global_identifier
== id
) {
1423 if (circ
->marked_for_close
)
1426 return TO_ORIGIN_CIRCUIT(circ
);
1429 SMARTLIST_FOREACH_END(circ
);
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.
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.
1441 static inline circuit_t
*
1442 circuit_get_by_circid_channel_impl(circid_t circ_id
, channel_t
*chan
,
1443 int *found_entry_out
)
1445 chan_circid_circuit_map_t search
;
1446 chan_circid_circuit_map_t
*found
;
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
;
1453 search
.circ_id
= circ_id
;
1455 found
= HT_FIND(chan_circid_map
, &chan_circid_map
, &search
);
1456 _last_circid_chan_ent
= found
;
1458 if (found
&& found
->circuit
) {
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
;
1470 "circuit_get_by_circid_channel_impl() found %s for"
1471 " circ_id %u, channel ID %"PRIu64
" (%p)",
1472 found
? "placeholder" : "nothing",
1474 (chan
->global_identifier
), chan
);
1476 if (found_entry_out
)
1477 *found_entry_out
= found
? 1 : 0;
1480 /* The rest of this checks for bugs. Disabled by default. */
1481 /* We comment it out because coverity complains otherwise.
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) {
1489 "circuit matches p_chan, but not in hash table (Bug!)");
1493 if (circ->n_chan == chan && circ->n_circ_id == circ_id) {
1495 "circuit matches n_chan, but not in hash table (Bug!)");
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.
1510 circuit_get_by_circid_channel(circid_t circ_id
, channel_t
*chan
)
1512 circuit_t
*circ
= circuit_get_by_circid_channel_impl(circ_id
, chan
, NULL
);
1513 if (!circ
|| circ
->marked_for_close
)
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.
1525 circuit_get_by_circid_channel_even_if_marked(circid_t circ_id
,
1528 return circuit_get_by_circid_channel_impl(circ_id
, chan
, NULL
);
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.
1535 * (Return 1 if the circuit is present, marked or not; Return 2
1536 * if the circuit ID is pending a destroy.)
1539 circuit_id_in_use_on_channel(circid_t circ_id
, channel_t
*chan
)
1542 if (circuit_get_by_circid_channel_impl(circ_id
, chan
, &found
) != NULL
)
1549 /** Helper for debugging 12184. Returns the time since which 'circ_id' has
1550 * been marked unusable on 'chan'. */
1552 circuit_id_when_marked_unusable_on_channel(circid_t circ_id
, channel_t
*chan
)
1554 chan_circid_circuit_map_t search
;
1555 chan_circid_circuit_map_t
*found
;
1557 memset(&search
, 0, sizeof(search
));
1558 search
.circ_id
= circ_id
;
1561 found
= HT_FIND(chan_circid_map
, &chan_circid_map
, &search
);
1563 if (! found
|| found
->circuit
)
1566 return found
->made_placeholder_at
;
1569 /** Return the circuit that a given edge connection is using. */
1571 circuit_get_by_edge_conn(edge_connection_t
*conn
)
1575 circ
= conn
->on_circuit
;
1577 (CIRCUIT_IS_ORIGIN(circ
) ? circ
->magic
== ORIGIN_CIRCUIT_MAGIC
1578 : circ
->magic
== OR_CIRCUIT_MAGIC
));
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.
1588 circuit_unlink_all_from_channel(channel_t
*chan
, int reason
)
1590 smartlist_t
*detached
= smartlist_new();
1592 /* #define DEBUG_CIRCUIT_UNLINK_ALL */
1594 channel_unlink_all_circuits(chan
, detached
);
1596 #ifdef DEBUG_CIRCUIT_UNLINK_ALL
1598 smartlist_t
*detached_2
= smartlist_new();
1599 int mismatch
= 0, badlen
= 0;
1601 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
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
);
1608 SMARTLIST_FOREACH_END(circ
);
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
));
1617 smartlist_sort_pointers(detached
);
1618 smartlist_sort_pointers(detached_2
);
1620 SMARTLIST_FOREACH(detached
, circuit_t
*, c
,
1621 if (c
!= smartlist_get(detached_2
, c_sl_idx
))
1626 log_warn(LD_BUG
, "Mismatch in list of detached circuits.");
1628 if (badlen
|| mismatch
) {
1629 smartlist_free(detached
);
1630 detached
= detached_2
;
1632 log_notice(LD_CIRC
, "List of %d circuits was as expected.",
1633 (int)smartlist_len(detached
));
1634 smartlist_free(detached_2
);
1637 #endif /* defined(DEBUG_CIRCUIT_UNLINK_ALL) */
1639 SMARTLIST_FOREACH_BEGIN(detached
, circuit_t
*, circ
) {
1641 if (circ
->n_chan
== chan
) {
1643 circuit_set_n_circid_chan(circ
, 0, NULL
);
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
;
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
);
1659 log_warn(LD_BUG
, "Circuit on detached list which I had no reason "
1663 if (!circ
->marked_for_close
)
1664 circuit_mark_for_close(circ
, reason
);
1665 } SMARTLIST_FOREACH_END(circ
);
1667 smartlist_free(detached
);
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.
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.
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.
1686 circuit_get_next_intro_circ(const origin_circuit_t
*start
,
1687 bool want_client_circ
)
1690 smartlist_t
*lst
= circuit_get_global_list();
1693 idx
= TO_CIRCUIT(start
)->global_circuitlist_idx
+ 1;
1696 for ( ; idx
< smartlist_len(lst
); ++idx
) {
1697 circuit_t
*circ
= smartlist_get(lst
, idx
);
1699 /* Ignore a marked for close circuit or if the state is not open. */
1700 if (circ
->marked_for_close
) {
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
&&
1708 circ
->purpose
!= CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
&&
1709 circ
->purpose
!= CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
) {
1712 } else { /* we are looking for service-side circs */
1713 if (circ
->state
!= CIRCUIT_STATE_OPEN
) {
1716 if (circ
->purpose
!= CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
&&
1717 circ
->purpose
!= CIRCUIT_PURPOSE_S_INTRO
) {
1722 /* The purposes we are looking for are only for origin circuits so the
1723 * following is valid. */
1724 return TO_ORIGIN_CIRCUIT(circ
);
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.
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. */
1738 circuit_get_next_service_rp_circ(origin_circuit_t
*start
)
1741 smartlist_t
*lst
= circuit_get_global_list();
1744 idx
= TO_CIRCUIT(start
)->global_circuitlist_idx
+ 1;
1747 for ( ; idx
< smartlist_len(lst
); ++idx
) {
1748 circuit_t
*circ
= smartlist_get(lst
, idx
);
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
||
1753 (circ
->purpose
!= CIRCUIT_PURPOSE_S_CONNECT_REND
&&
1754 circ
->purpose
!= CIRCUIT_PURPOSE_S_REND_JOINED
)) {
1757 /* The purposes we are looking for are only for origin circuits so the
1758 * following is valid. */
1759 return TO_ORIGIN_CIRCUIT(circ
);
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. */
1769 circuit_get_next_by_purpose(origin_circuit_t
*start
, uint8_t purpose
)
1772 smartlist_t
*lst
= circuit_get_global_list();
1773 tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose
));
1777 idx
= TO_CIRCUIT(start
)->global_circuitlist_idx
+ 1;
1779 for ( ; idx
< smartlist_len(lst
); ++idx
) {
1780 circuit_t
*circ
= smartlist_get(lst
, idx
);
1782 if (circ
->marked_for_close
)
1784 if (circ
->purpose
!= purpose
)
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
))) {
1791 return TO_ORIGIN_CIRCUIT(circ
);
1796 /** We might cannibalize this circuit: Return true if its last hop can be used
1797 * as a v3 rendezvous point. */
1799 circuit_can_be_cannibalized_for_v3_rp(const origin_circuit_t
*circ
)
1801 if (!circ
->build_state
) {
1805 extend_info_t
*chosen_exit
= circ
->build_state
->chosen_exit
;
1806 if (BUG(!chosen_exit
)) {
1810 const node_t
*rp_node
= node_get_by_id(chosen_exit
->identity_digest
);
1812 if (node_supports_v3_rendezvous_point(rp_node
)) {
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. */
1824 get_circuit_purpose_needed_to_cannibalize(uint8_t purpose
)
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. */
1829 return CIRCUIT_PURPOSE_HS_VANGUARDS
;
1831 /* If no vanguards are used just get a general circuit! */
1832 return CIRCUIT_PURPOSE_C_GENERAL
;
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.
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.
1844 * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits.
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
1855 circuit_find_to_cannibalize(uint8_t purpose_to_produce
, extend_info_t
*info
,
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
;
1866 /* Make sure we're not trying to create a onehop circ by
1867 * cannibalization. */
1868 tor_assert(!(flags
& CIRCLAUNCH_ONEHOP_TUNNEL
));
1870 purpose_to_search_for
= get_circuit_purpose_needed_to_cannibalize(
1871 purpose_to_produce
);
1873 tor_assert_nonfatal(purpose_to_search_for
== CIRCUIT_PURPOSE_C_GENERAL
||
1874 purpose_to_search_for
== CIRCUIT_PURPOSE_HS_VANGUARDS
);
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
);
1881 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ_
) {
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_
);
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.
1893 if (circ
->build_state
->desired_path_len
!=
1894 route_len_for_purpose(purpose_to_search_for
, NULL
)) {
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
)) {
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
&&
1909 circ
->remaining_relay_early_cells
&&
1910 !circ
->build_state
->onehop_tunnel
&&
1911 !circ
->isolation_values_set
) {
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
);
1918 if (tor_memeq(hop
->extend_info
->identity_digest
,
1919 info
->identity_digest
, DIGEST_LEN
))
1922 (ri2
= node_get_by_id(hop
->extend_info
->identity_digest
))
1923 && nodes_in_same_family(ri1
, ri2
))
1926 } while (hop
!=circ
->cpath
);
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
;
1935 if (routerset_contains_extendinfo(options
->ExcludeNodes
,
1939 } while (hop
!= circ
->cpath
);
1942 if ((flags
& CIRCLAUNCH_IS_V3_RP
) &&
1943 !circuit_can_be_cannibalized_for_v3_rp(circ
)) {
1944 log_debug(LD_GENERAL
, "Skipping uncannibalizable circuit for v3 "
1945 "rendezvous point.");
1949 if (!best
|| (best
->build_state
->need_uptime
&& !need_uptime
))
1955 SMARTLIST_FOREACH_END(circ_
);
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.
1965 circuit_find_circuits_to_upgrade_from_guard_wait(void)
1967 /* Only if some circuit is actually waiting on an upgrade should we
1968 * run the algorithm. */
1969 if (! circuits_pending_other_guards
||
1970 smartlist_len(circuits_pending_other_guards
)==0)
1972 /* Only if we have some origin circuits should we run the algorithm. */
1973 if (!global_origin_circuit_list
)
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(
1979 get_guard_selection_info(),
1980 global_origin_circuit_list
,
1982 if (circuits_upgraded
&& smartlist_len(result
)) {
1985 smartlist_free(result
);
1990 /** Return the number of hops in circuit's path. If circ has no entries,
1991 * or is NULL, returns 0. */
1993 circuit_get_cpath_len(origin_circuit_t
*circ
)
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
;
2006 /** Return the number of opened hops in circuit's path.
2007 * If circ has no entries, or is NULL, returns 0. */
2009 circuit_get_cpath_opened_len(const origin_circuit_t
*circ
)
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
;
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. */
2029 circuit_get_cpath_hop(origin_circuit_t
*circ
, int hopnum
)
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
;
2042 /** Go through the circuitlist; mark-for-close each circuit that starts
2043 * at us but has not yet been used. */
2045 circuit_mark_all_unused_circs(void)
2047 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
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
);
2053 SMARTLIST_FOREACH_END(circ
);
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
2060 * This is useful for letting the user change pseudonyms, so new
2061 * streams will not be linkable to old streams.
2064 circuit_mark_all_dirty_circs_as_unusable(void)
2066 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
2067 if (CIRCUIT_IS_ORIGIN(circ
) &&
2068 !circ
->marked_for_close
&&
2069 circ
->timestamp_dirty
) {
2070 mark_circuit_unusable_for_new_conns(TO_ORIGIN_CIRCUIT(circ
));
2073 SMARTLIST_FOREACH_END(circ
);
2077 * Report any queued cells on or_circuits as written in our bandwidth
2078 * totals, for the specified channel direction.
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.
2086 * This function is in the critical path of circuit_mark_for_close().
2087 * It must be (and is) O(1)!
2089 * See https://bugs.torproject.org/tpo/core/tor/23512
2092 circuit_synchronize_written_or_bandwidth(const circuit_t
*c
,
2093 circuit_channel_direction_t dir
)
2097 uint64_t written_sync
;
2098 const channel_t
*chan
= NULL
;
2099 const or_circuit_t
*or_circ
;
2101 if (!CIRCUIT_IS_ORCIRC(c
))
2104 or_circ
= CONST_TO_OR_CIRCUIT(c
);
2106 if (dir
== CIRCUIT_N_CHAN
) {
2108 cells
= c
->n_chan_cells
.n
;
2110 chan
= or_circ
->p_chan
;
2111 cells
= or_circ
->p_chan_cells
.n
;
2114 /* If we still know the chan, determine real cell size. Otherwise,
2115 * assume it's a wide circid channel */
2117 cell_size
= get_cell_network_size(chan
->wide_circ_ids
);
2119 cell_size
= CELL_MAX_NETWORK_SIZE
;
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
;
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
);
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
);
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
2141 * - If circ isn't open yet: call circuit_build_failed() if we're
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.
2154 circuit_mark_for_close_
, (circuit_t
*circ
, int reason
, int line
,
2157 int orig_reason
= reason
; /* Passed to the controller */
2158 assert_circuit_ok(circ
);
2162 /* Check whether the circuitpadding subsystem wants to block this close */
2163 if (circpad_marked_circuit_for_padding(circ
, reason
)) {
2167 if (circ
->marked_for_close
) {
2169 "Duplicate call to circuit_mark_for_close at %s:%d"
2170 " (first at %s:%d)", file
, line
,
2171 circ
->marked_for_close_file
, circ
->marked_for_close
);
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
);
2180 reason
= END_CIRC_REASON_NONE
;
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 */
2189 /* We don't send reasons when closing circuits at the origin. */
2190 reason
= END_CIRC_REASON_NONE
;
2193 circuit_synchronize_written_or_bandwidth(circ
, CIRCUIT_N_CHAN
);
2194 circuit_synchronize_written_or_bandwidth(circ
, CIRCUIT_P_CHAN
);
2196 if (reason
& END_CIRC_REASON_FLAG_REMOTE
)
2197 reason
&= ~END_CIRC_REASON_FLAG_REMOTE
;
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
;
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
;
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
);
2217 or_circ
->rend_splice
= NULL
;
2221 /* Notify the HS subsystem that this circuit is closing. */
2222 hs_circ_cleanup_on_close(circ
);
2224 if (circuits_pending_close
== NULL
)
2225 circuits_pending_close
= smartlist_new();
2227 smartlist_add(circuits_pending_close
, circ
);
2228 mainloop_schedule_postloop_cleanup();
2230 log_info(LD_GENERAL
, "Circuit %u (id: %" PRIu32
") marked for close at "
2231 "%s:%d (orig reason: %d, new reason: %d)",
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
);
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.
2245 circuit_about_to_free_atexit(circuit_t
*circ
)
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
);
2254 if (! CIRCUIT_IS_ORIGIN(circ
)) {
2255 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
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
);
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.
2270 circuit_about_to_free(circuit_t
*circ
)
2273 int reason
= circ
->marked_for_close_reason
;
2274 int orig_reason
= circ
->marked_for_close_orig_reason
;
2276 if (circ
->state
== CIRCUIT_STATE_ONIONSKIN_PENDING
) {
2277 onion_pending_remove(TO_OR_CIRCUIT(circ
));
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.
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 */
2290 if (circ
->state
== CIRCUIT_STATE_CHAN_WAIT
) {
2291 if (circuits_pending_chans
)
2292 smartlist_remove(circuits_pending_chans
, circ
);
2294 if (circuits_pending_other_guards
) {
2295 smartlist_remove(circuits_pending_other_guards
, circ
);
2297 if (CIRCUIT_IS_ORIGIN(circ
)) {
2298 circuit_event_status(TO_ORIGIN_CIRCUIT(circ
),
2299 (circ
->state
== CIRCUIT_STATE_OPEN
||
2300 circ
->state
== CIRCUIT_STATE_GUARD_WAIT
) ?
2301 CIRC_EVENT_CLOSED
:CIRC_EVENT_FAILED
,
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
);
2311 circuitmux_detach_circuit(circ
->n_chan
->cmux
, circ
);
2312 circuit_set_n_circid_chan(circ
, 0, NULL
);
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
;
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
;
2331 conn
->end_reason
|= END_STREAM_REASON_FLAG_ALREADY_SENT_CLOSED
;
2332 connection_mark_for_close(TO_CONN(conn
));
2334 conn
->on_circuit
= NULL
;
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
);
2343 circuitmux_detach_circuit(or_circ
->p_chan
->cmux
, circ
);
2344 circuit_set_p_circid_chan(or_circ
, 0, NULL
);
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
;
2355 /** Given a marked circuit <b>circ</b>, aggressively free its cell queues to
2356 * recover memory. */
2358 marked_circuit_free_cells(circuit_t
*circ
)
2360 if (!circ
->marked_for_close
) {
2361 log_warn(LD_BUG
, "Called on non-marked circuit");
2364 cell_queue_clear(&circ
->n_chan_cells
);
2365 if (! CIRCUIT_IS_ORIGIN(circ
)) {
2366 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
2367 cell_queue_clear(&orcirc
->p_chan_cells
);
2372 single_conn_free_bytes(connection_t
*conn
)
2376 result
+= buf_allocation(conn
->inbuf
);
2377 buf_clear(conn
->inbuf
);
2380 result
+= buf_allocation(conn
->outbuf
);
2381 buf_clear(conn
->outbuf
);
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
;
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. */
2397 marked_circuit_streams_free_bytes(edge_connection_t
*stream
)
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
);
2410 /** Aggressively free buffer contents on all the buffers of all streams on
2411 * circuit <b>c</b>. Return the number of bytes recovered. */
2413 marked_circuit_free_stream_bytes(circuit_t
*c
)
2415 if (CIRCUIT_IS_ORIGIN(c
)) {
2416 return marked_circuit_streams_free_bytes(TO_ORIGIN_CIRCUIT(c
)->p_streams
);
2418 return marked_circuit_streams_free_bytes(TO_OR_CIRCUIT(c
)->n_streams
);
2422 /** Return the number of cells used by the circuit <b>c</b>'s cell queues. */
2424 n_cells_in_circ_queues(const circuit_t
*c
)
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
;
2434 /** Return the number of bytes allocated for <b>c</b>'s half-open streams. */
2436 circuit_alloc_in_half_streams(const circuit_t
*c
)
2438 if (! CIRCUIT_IS_ORIGIN(c
)) {
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
);
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.
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.
2457 circuit_max_queued_cell_age(const circuit_t
*c
, uint32_t now
)
2460 packed_cell_t
*cell
;
2462 if (NULL
!= (cell
= TOR_SIMPLEQ_FIRST(&c
->n_chan_cells
.head
)))
2463 age
= now
- cell
->inserted_timestamp
;
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
;
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.
2481 conn_get_buffer_age(const connection_t
*conn
, uint32_t now_ts
)
2483 uint32_t age
= 0, age2
;
2485 age2
= buf_get_oldest_chunk_timestamp(conn
->outbuf
, now_ts
);
2490 age2
= buf_get_oldest_chunk_timestamp(conn
->inbuf
, now_ts
);
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>. */
2501 circuit_get_streams_max_data_age(const edge_connection_t
*stream
, uint32_t now
)
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
);
2509 if (conn
->linked_conn
) {
2510 age2
= conn_get_buffer_age(conn
->linked_conn
, now
);
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
2522 circuit_max_queued_data_age(const circuit_t
*c
, uint32_t now
)
2524 if (CIRCUIT_IS_ORIGIN(c
)) {
2525 return circuit_get_streams_max_data_age(
2526 CONST_TO_ORIGIN_CIRCUIT(c
)->p_streams
, now
);
2528 return circuit_get_streams_max_data_age(
2529 CONST_TO_OR_CIRCUIT(c
)->n_streams
, now
);
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
2537 circuit_max_queued_item_age(const circuit_t
*c
, uint32_t now
)
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
)
2547 /** Helper to sort a list of circuit_t by age of oldest item, in descending
2550 circuits_compare_by_oldest_queued_item_(const void **a_
, const void **b_
)
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
;
2559 else if (age_a
== age_b
)
2565 static uint32_t now_ts_for_buf_cmp
;
2567 /** Helper to sort a list of circuit_t by age of oldest item, in descending
2570 conns_compare_by_buffer_age_(const void **a_
, const void **b_
)
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
);
2579 else if (age_a
== age_b
)
2585 #define FRACTION_OF_DATA_TO_RETAIN_ON_OOM 0.90
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. */
2591 circuits_handle_oom(size_t current_allocation
)
2593 smartlist_t
*circlist
;
2594 smartlist_t
*connection_array
= get_connection_array();
2596 size_t mem_to_recover
;
2597 size_t mem_recovered
=0;
2598 int n_circuits_killed
=0;
2599 int n_dirconns_killed
=0;
2601 log_notice(LD_GENERAL
, "We're low on memory (cell queues total alloc:"
2602 " %"TOR_PRIuSZ
" buffer total alloc: %" TOR_PRIuSZ
","
2603 " tor compress total alloc: %" TOR_PRIuSZ
2604 " (zlib: %" TOR_PRIuSZ
", zstd: %" TOR_PRIuSZ
","
2605 " lzma: %" TOR_PRIuSZ
"),"
2606 " rendezvous cache total alloc: %" TOR_PRIuSZ
"). Killing"
2607 " circuits withover-long queues. (This behavior is controlled by"
2608 " MaxMemInQueues.)",
2609 cell_queues_get_total_allocation(),
2610 buf_get_total_allocation(),
2611 tor_compress_get_total_allocation(),
2612 tor_zlib_get_total_allocation(),
2613 tor_zstd_get_total_allocation(),
2614 tor_lzma_get_total_allocation(),
2615 hs_cache_get_total_allocation());
2618 size_t mem_target
= (size_t)(get_options()->MaxMemInQueues
*
2619 FRACTION_OF_DATA_TO_RETAIN_ON_OOM
);
2620 if (current_allocation
<= mem_target
)
2622 mem_to_recover
= current_allocation
- mem_target
;
2625 now_ts
= monotime_coarse_get_stamp();
2627 circlist
= circuit_get_global_list();
2628 SMARTLIST_FOREACH_BEGIN(circlist
, circuit_t
*, circ
) {
2629 circ
->age_tmp
= circuit_max_queued_item_age(circ
, now_ts
);
2630 } SMARTLIST_FOREACH_END(circ
);
2632 /* This is O(n log n); there are faster algorithms we could use instead.
2633 * Let's hope this doesn't happen enough to be in the critical path. */
2634 smartlist_sort(circlist
, circuits_compare_by_oldest_queued_item_
);
2636 /* Fix up the indices before we run into trouble */
2637 SMARTLIST_FOREACH_BEGIN(circlist
, circuit_t
*, circ
) {
2638 circ
->global_circuitlist_idx
= circ_sl_idx
;
2639 } SMARTLIST_FOREACH_END(circ
);
2641 /* Now sort the connection array ... */
2642 now_ts_for_buf_cmp
= now_ts
;
2643 smartlist_sort(connection_array
, conns_compare_by_buffer_age_
);
2644 now_ts_for_buf_cmp
= 0;
2646 /* Fix up the connection array to its new order. */
2647 SMARTLIST_FOREACH_BEGIN(connection_array
, connection_t
*, conn
) {
2648 conn
->conn_array_index
= conn_sl_idx
;
2649 } SMARTLIST_FOREACH_END(conn
);
2651 /* Okay, now the worst circuits and connections are at the front of their
2652 * respective lists. Let's mark them, and reclaim their storage
2655 SMARTLIST_FOREACH_BEGIN(circlist
, circuit_t
*, circ
) {
2659 /* Free storage in any non-linked directory connections that have buffered
2660 * data older than this circuit. */
2661 while (conn_idx
< smartlist_len(connection_array
)) {
2662 connection_t
*conn
= smartlist_get(connection_array
, conn_idx
);
2663 uint32_t conn_age
= conn_get_buffer_age(conn
, now_ts
);
2664 if (conn_age
< circ
->age_tmp
) {
2667 if (conn
->type
== CONN_TYPE_DIR
&& conn
->linked_conn
== NULL
) {
2668 if (!conn
->marked_for_close
)
2669 connection_mark_for_close(conn
);
2670 mem_recovered
+= single_conn_free_bytes(conn
);
2672 ++n_dirconns_killed
;
2674 if (mem_recovered
>= mem_to_recover
)
2675 goto done_recovering_mem
;
2680 /* Now, kill the circuit. */
2681 n
= n_cells_in_circ_queues(circ
);
2682 const size_t half_stream_alloc
= circuit_alloc_in_half_streams(circ
);
2683 if (! circ
->marked_for_close
) {
2684 circuit_mark_for_close(circ
, END_CIRC_REASON_RESOURCELIMIT
);
2686 marked_circuit_free_cells(circ
);
2687 freed
= marked_circuit_free_stream_bytes(circ
);
2689 ++n_circuits_killed
;
2691 mem_recovered
+= n
* packed_cell_mem_cost();
2692 mem_recovered
+= half_stream_alloc
;
2693 mem_recovered
+= freed
;
2695 if (mem_recovered
>= mem_to_recover
)
2696 goto done_recovering_mem
;
2697 } SMARTLIST_FOREACH_END(circ
);
2699 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 "
2706 smartlist_len(circlist
) - n_circuits_killed
,
2710 /** Verify that circuit <b>c</b> has all of its invariants
2711 * correct. Trigger an assert if anything is invalid.
2714 assert_circuit_ok
,(const circuit_t
*c
))
2716 edge_connection_t
*conn
;
2717 const or_circuit_t
*or_circ
= NULL
;
2718 const origin_circuit_t
*origin_circ
= NULL
;
2721 tor_assert(c
->magic
== ORIGIN_CIRCUIT_MAGIC
|| c
->magic
== OR_CIRCUIT_MAGIC
);
2722 tor_assert(c
->purpose
>= CIRCUIT_PURPOSE_MIN_
&&
2723 c
->purpose
<= CIRCUIT_PURPOSE_MAX_
);
2725 if (CIRCUIT_IS_ORIGIN(c
))
2726 origin_circ
= CONST_TO_ORIGIN_CIRCUIT(c
);
2728 or_circ
= CONST_TO_OR_CIRCUIT(c
);
2731 tor_assert(!c
->n_hop
);
2734 /* We use the _impl variant here to make sure we don't fail on marked
2735 * circuits, which would not be returned by the regular function. */
2736 circuit_t
*c2
= circuit_get_by_circid_channel_impl(c
->n_circ_id
,
2738 tor_assert(c
== c2
);
2741 if (or_circ
&& or_circ
->p_chan
) {
2742 if (or_circ
->p_circ_id
) {
2745 circuit_get_by_circid_channel_impl(or_circ
->p_circ_id
,
2746 or_circ
->p_chan
, NULL
);
2747 tor_assert(c
== c2
);
2751 for (conn
= or_circ
->n_streams
; conn
; conn
= conn
->next_stream
)
2752 tor_assert(conn
->base_
.type
== CONN_TYPE_EXIT
);
2754 tor_assert(c
->deliver_window
>= 0);
2755 tor_assert(c
->package_window
>= 0);
2756 if (c
->state
== CIRCUIT_STATE_OPEN
||
2757 c
->state
== CIRCUIT_STATE_GUARD_WAIT
) {
2758 tor_assert(!c
->n_chan_create_cell
);
2760 relay_crypto_assert_ok(&or_circ
->crypto
);
2763 if (c
->state
== CIRCUIT_STATE_CHAN_WAIT
&& !c
->marked_for_close
) {
2764 tor_assert(circuits_pending_chans
&&
2765 smartlist_contains(circuits_pending_chans
, c
));
2767 tor_assert(!circuits_pending_chans
||
2768 !smartlist_contains(circuits_pending_chans
, c
));
2770 if (origin_circ
&& origin_circ
->cpath
) {
2771 cpath_assert_ok(origin_circ
->cpath
);
2773 if (c
->purpose
== CIRCUIT_PURPOSE_REND_ESTABLISHED
) {
2774 tor_assert(or_circ
);
2775 if (!c
->marked_for_close
) {
2776 tor_assert(or_circ
->rend_splice
);
2777 tor_assert(or_circ
->rend_splice
->rend_splice
== or_circ
);
2779 tor_assert(or_circ
->rend_splice
!= or_circ
);
2781 tor_assert(!or_circ
|| !or_circ
->rend_splice
);