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/status.h"
68 #include "core/or/trace_probes_circuit.h"
69 #include "core/mainloop/connection.h"
70 #include "app/config/config.h"
71 #include "core/or/connection_edge.h"
72 #include "core/or/connection_or.h"
73 #include "feature/control/control_events.h"
74 #include "lib/crypt_ops/crypto_rand.h"
75 #include "lib/crypt_ops/crypto_util.h"
76 #include "lib/crypt_ops/crypto_dh.h"
77 #include "feature/dircommon/directory.h"
78 #include "feature/client/entrynodes.h"
79 #include "core/mainloop/mainloop.h"
80 #include "feature/hs/hs_cache.h"
81 #include "feature/hs/hs_circuit.h"
82 #include "feature/hs/hs_circuitmap.h"
83 #include "feature/hs/hs_ident.h"
84 #include "feature/nodelist/networkstatus.h"
85 #include "feature/nodelist/nodelist.h"
86 #include "feature/relay/onion_queue.h"
87 #include "core/crypto/onion_crypto.h"
88 #include "core/crypto/onion_fast.h"
89 #include "core/or/policies.h"
90 #include "core/or/relay.h"
91 #include "core/crypto/relay_crypto.h"
92 #include "feature/rend/rendcommon.h"
93 #include "feature/stats/predict_ports.h"
94 #include "feature/stats/bwhist.h"
95 #include "feature/stats/rephist.h"
96 #include "feature/nodelist/routerlist.h"
97 #include "feature/nodelist/routerset.h"
98 #include "core/or/channelpadding.h"
99 #include "lib/compress/compress.h"
100 #include "lib/compress/compress_lzma.h"
101 #include "lib/compress/compress_zlib.h"
102 #include "lib/compress/compress_zstd.h"
103 #include "lib/buf/buffers.h"
104 #include "core/or/congestion_control_common.h"
105 #include "core/or/congestion_control_st.h"
106 #include "lib/math/stats.h"
108 #include "core/or/ocirc_event.h"
112 #include "core/or/cpath_build_state_st.h"
113 #include "core/or/crypt_path_reference_st.h"
114 #include "feature/dircommon/dir_connection_st.h"
115 #include "core/or/edge_connection_st.h"
116 #include "core/or/half_edge_st.h"
117 #include "core/or/extend_info_st.h"
118 #include "core/or/or_circuit_st.h"
119 #include "core/or/origin_circuit_st.h"
121 /********* START VARIABLES **********/
123 /** A global list of all circuits at this hop. */
124 static smartlist_t
*global_circuitlist
= NULL
;
126 /** A global list of all origin circuits. Every element of this is also
127 * an element of global_circuitlist. */
128 static smartlist_t
*global_origin_circuit_list
= NULL
;
130 /** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
131 static smartlist_t
*circuits_pending_chans
= NULL
;
133 /** List of all the (origin) circuits whose state is
134 * CIRCUIT_STATE_GUARD_WAIT. */
135 static smartlist_t
*circuits_pending_other_guards
= NULL
;
137 /** A list of all the circuits that have been marked with
138 * circuit_mark_for_close and which are waiting for circuit_about_to_free. */
139 static smartlist_t
*circuits_pending_close
= NULL
;
141 static void circuit_about_to_free_atexit(circuit_t
*circ
);
142 static void circuit_about_to_free(circuit_t
*circ
);
145 * A cached value of the current state of the origin circuit list. Has the
146 * value 1 if we saw any opened circuits recently (since the last call to
147 * circuit_any_opened_circuits(), which gets called around once a second by
148 * circuit_expire_building). 0 otherwise.
150 static int any_opened_circs_cached_val
= 0;
152 /** Moving average of the cc->cwnd from each closed circuit. */
153 double cc_stats_circ_close_cwnd_ma
= 0;
154 /** Moving average of the cc->cwnd from each closed slow-start circuit. */
155 double cc_stats_circ_close_ss_cwnd_ma
= 0;
157 /********* END VARIABLES ************/
159 /* Implement circuit handle helpers. */
160 HANDLE_IMPL(circuit
, circuit_t
,)
163 TO_OR_CIRCUIT(circuit_t
*x
)
165 tor_assert(x
->magic
== OR_CIRCUIT_MAGIC
);
166 return DOWNCAST(or_circuit_t
, x
);
169 CONST_TO_OR_CIRCUIT(const circuit_t
*x
)
171 tor_assert(x
->magic
== OR_CIRCUIT_MAGIC
);
172 return DOWNCAST(or_circuit_t
, x
);
175 TO_ORIGIN_CIRCUIT(circuit_t
*x
)
177 tor_assert(x
->magic
== ORIGIN_CIRCUIT_MAGIC
);
178 return DOWNCAST(origin_circuit_t
, x
);
180 const origin_circuit_t
*
181 CONST_TO_ORIGIN_CIRCUIT(const circuit_t
*x
)
183 tor_assert(x
->magic
== ORIGIN_CIRCUIT_MAGIC
);
184 return DOWNCAST(origin_circuit_t
, x
);
187 /** A map from channel and circuit ID to circuit. (Lookup performance is
188 * very important here, since we need to do it every time a cell arrives.) */
189 typedef struct chan_circid_circuit_map_t
{
190 HT_ENTRY(chan_circid_circuit_map_t
) node
;
194 /* For debugging 12184: when was this placeholder item added? */
195 time_t made_placeholder_at
;
196 } chan_circid_circuit_map_t
;
198 /** Helper for hash tables: compare the channel and circuit ID for a and
199 * b, and return less than, equal to, or greater than zero appropriately.
202 chan_circid_entries_eq_(chan_circid_circuit_map_t
*a
,
203 chan_circid_circuit_map_t
*b
)
205 return a
->chan
== b
->chan
&& a
->circ_id
== b
->circ_id
;
208 /** Helper: return a hash based on circuit ID and the pointer value of
209 * chan in <b>a</b>. */
210 static inline unsigned int
211 chan_circid_entry_hash_(chan_circid_circuit_map_t
*a
)
213 /* Try to squeze the siphash input into 8 bytes to save any extra siphash
214 * rounds. This hash function is in the critical path. */
215 uintptr_t chan
= (uintptr_t) (void*) a
->chan
;
217 array
[0] = a
->circ_id
;
218 /* The low bits of the channel pointer are uninteresting, since the channel
219 * is a pretty big structure. */
220 array
[1] = (uint32_t) (chan
>> 6);
221 return (unsigned) siphash24g(array
, sizeof(array
));
224 /** Map from [chan,circid] to circuit. */
225 static HT_HEAD(chan_circid_map
, chan_circid_circuit_map_t
)
226 chan_circid_map
= HT_INITIALIZER();
227 HT_PROTOTYPE(chan_circid_map
, chan_circid_circuit_map_t
, node
,
228 chan_circid_entry_hash_
, chan_circid_entries_eq_
);
229 HT_GENERATE2(chan_circid_map
, chan_circid_circuit_map_t
, node
,
230 chan_circid_entry_hash_
, chan_circid_entries_eq_
, 0.6,
231 tor_reallocarray_
, tor_free_
);
233 /** The most recently returned entry from circuit_get_by_circid_chan;
234 * used to improve performance when many cells arrive in a row from the
237 static chan_circid_circuit_map_t
*_last_circid_chan_ent
= NULL
;
239 /** Implementation helper for circuit_set_{p,n}_circid_channel: A circuit ID
240 * and/or channel for circ has just changed from <b>old_chan, old_id</b>
241 * to <b>chan, id</b>. Adjust the chan,circid map as appropriate, removing
242 * the old entry (if any) and adding a new one. */
244 circuit_set_circid_chan_helper(circuit_t
*circ
, int direction
,
248 chan_circid_circuit_map_t search
;
249 chan_circid_circuit_map_t
*found
;
250 channel_t
*old_chan
, **chan_ptr
;
251 circid_t old_id
, *circid_ptr
;
252 int make_active
, attached
= 0;
254 if (direction
== CELL_DIRECTION_OUT
) {
255 chan_ptr
= &circ
->n_chan
;
256 circid_ptr
= &circ
->n_circ_id
;
257 make_active
= circ
->n_chan_cells
.n
> 0;
259 or_circuit_t
*c
= TO_OR_CIRCUIT(circ
);
260 chan_ptr
= &c
->p_chan
;
261 circid_ptr
= &c
->p_circ_id
;
262 make_active
= c
->p_chan_cells
.n
> 0;
264 old_chan
= *chan_ptr
;
265 old_id
= *circid_ptr
;
267 if (id
== old_id
&& chan
== old_chan
)
270 if (_last_circid_chan_ent
&&
271 ((old_id
== _last_circid_chan_ent
->circ_id
&&
272 old_chan
== _last_circid_chan_ent
->chan
) ||
273 (id
== _last_circid_chan_ent
->circ_id
&&
274 chan
== _last_circid_chan_ent
->chan
))) {
275 _last_circid_chan_ent
= NULL
;
280 * If we're changing channels or ID and had an old channel and a non
281 * zero old ID and weren't marked for close (i.e., we should have been
282 * attached), detach the circuit. ID changes require this because
283 * circuitmux hashes on (channel_id, circuit_id).
285 if (old_id
!= 0 && (old_chan
!= chan
|| old_id
!= id
) &&
286 !(circ
->marked_for_close
)) {
287 tor_assert(old_chan
->cmux
);
288 circuitmux_detach_circuit(old_chan
->cmux
, circ
);
291 /* we may need to remove it from the conn-circid map */
292 search
.circ_id
= old_id
;
293 search
.chan
= old_chan
;
294 found
= HT_REMOVE(chan_circid_map
, &chan_circid_map
, &search
);
297 if (direction
== CELL_DIRECTION_OUT
) {
298 /* One fewer circuits use old_chan as n_chan */
299 --(old_chan
->num_n_circuits
);
301 /* One fewer circuits use old_chan as p_chan */
302 --(old_chan
->num_p_circuits
);
307 /* Change the values only after we have possibly made the circuit inactive
308 * on the previous chan. */
315 /* now add the new one to the conn-circid map */
318 found
= HT_FIND(chan_circid_map
, &chan_circid_map
, &search
);
320 found
->circuit
= circ
;
321 found
->made_placeholder_at
= 0;
323 found
= tor_malloc_zero(sizeof(chan_circid_circuit_map_t
));
326 found
->circuit
= circ
;
327 HT_INSERT(chan_circid_map
, &chan_circid_map
, found
);
331 * Attach to the circuitmux if we're changing channels or IDs and
332 * have a new channel and ID to use and the circuit is not marked for
335 if (chan
&& id
!= 0 && (old_chan
!= chan
|| old_id
!= id
) &&
336 !(circ
->marked_for_close
)) {
337 tor_assert(chan
->cmux
);
338 circuitmux_attach_circuit(chan
->cmux
, circ
, direction
);
343 * This is a no-op if we have no cells, but if we do it marks us active to
346 if (make_active
&& attached
)
347 update_circuit_on_cmux(circ
, direction
);
349 /* Adjust circuit counts on new channel */
350 if (direction
== CELL_DIRECTION_OUT
) {
351 ++chan
->num_n_circuits
;
353 ++chan
->num_p_circuits
;
357 /** Mark that circuit id <b>id</b> shouldn't be used on channel <b>chan</b>,
358 * even if there is no circuit on the channel. We use this to keep the
359 * circuit id from getting re-used while we have queued but not yet sent
362 channel_mark_circid_unusable(channel_t
*chan
, circid_t id
)
364 chan_circid_circuit_map_t search
;
365 chan_circid_circuit_map_t
*ent
;
367 /* See if there's an entry there. That wouldn't be good. */
368 memset(&search
, 0, sizeof(search
));
371 ent
= HT_FIND(chan_circid_map
, &chan_circid_map
, &search
);
373 if (ent
&& ent
->circuit
) {
374 /* we have a problem. */
375 log_warn(LD_BUG
, "Tried to mark %u unusable on %p, but there was already "
376 "a circuit there.", (unsigned)id
, chan
);
378 /* It's already marked. */
379 if (!ent
->made_placeholder_at
)
380 ent
->made_placeholder_at
= approx_time();
382 ent
= tor_malloc_zero(sizeof(chan_circid_circuit_map_t
));
385 /* leave circuit at NULL. */
386 ent
->made_placeholder_at
= approx_time();
387 HT_INSERT(chan_circid_map
, &chan_circid_map
, ent
);
391 /** Mark that a circuit id <b>id</b> can be used again on <b>chan</b>.
392 * We use this to re-enable the circuit ID after we've sent a destroy cell.
395 channel_mark_circid_usable(channel_t
*chan
, circid_t id
)
397 chan_circid_circuit_map_t search
;
398 chan_circid_circuit_map_t
*ent
;
400 /* See if there's an entry there. That wouldn't be good. */
401 memset(&search
, 0, sizeof(search
));
404 ent
= HT_REMOVE(chan_circid_map
, &chan_circid_map
, &search
);
405 if (ent
&& ent
->circuit
) {
406 log_warn(LD_BUG
, "Tried to mark %u usable on %p, but there was already "
407 "a circuit there.", (unsigned)id
, chan
);
410 if (_last_circid_chan_ent
== ent
)
411 _last_circid_chan_ent
= NULL
;
415 /** Called to indicate that a DESTROY is pending on <b>chan</b> with
416 * circuit ID <b>id</b>, but hasn't been sent yet. */
418 channel_note_destroy_pending(channel_t
*chan
, circid_t id
)
420 circuit_t
*circ
= circuit_get_by_circid_channel_even_if_marked(id
,chan
);
422 if (circ
->n_chan
== chan
&& circ
->n_circ_id
== id
) {
423 circ
->n_delete_pending
= 1;
425 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
426 if (orcirc
->p_chan
== chan
&& orcirc
->p_circ_id
== id
) {
427 circ
->p_delete_pending
= 1;
432 channel_mark_circid_unusable(chan
, id
);
435 /** Called to indicate that a DESTROY is no longer pending on <b>chan</b> with
436 * circuit ID <b>id</b> -- typically, because it has been sent. */
438 channel_note_destroy_not_pending
,(channel_t
*chan
, circid_t id
))
440 circuit_t
*circ
= circuit_get_by_circid_channel_even_if_marked(id
,chan
);
442 if (circ
->n_chan
== chan
&& circ
->n_circ_id
== id
) {
443 circ
->n_delete_pending
= 0;
445 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
446 if (orcirc
->p_chan
== chan
&& orcirc
->p_circ_id
== id
) {
447 circ
->p_delete_pending
= 0;
450 /* XXXX this shouldn't happen; log a bug here. */
453 channel_mark_circid_usable(chan
, id
);
456 /** Set the p_conn field of a circuit <b>circ</b>, along
457 * with the corresponding circuit ID, and add the circuit as appropriate
458 * to the (chan,id)-\>circuit map. */
460 circuit_set_p_circid_chan(or_circuit_t
*or_circ
, circid_t id
,
463 circuit_t
*circ
= TO_CIRCUIT(or_circ
);
464 channel_t
*old_chan
= or_circ
->p_chan
;
465 circid_t old_id
= or_circ
->p_circ_id
;
467 circuit_set_circid_chan_helper(circ
, CELL_DIRECTION_IN
, id
, chan
);
470 chan
->timestamp_last_had_circuits
= approx_time();
473 if (circ
->p_delete_pending
&& old_chan
) {
474 channel_mark_circid_unusable(old_chan
, old_id
);
475 circ
->p_delete_pending
= 0;
479 /** Set the n_conn field of a circuit <b>circ</b>, along
480 * with the corresponding circuit ID, and add the circuit as appropriate
481 * to the (chan,id)-\>circuit map. */
483 circuit_set_n_circid_chan(circuit_t
*circ
, circid_t id
,
486 channel_t
*old_chan
= circ
->n_chan
;
487 circid_t old_id
= circ
->n_circ_id
;
489 circuit_set_circid_chan_helper(circ
, CELL_DIRECTION_OUT
, id
, chan
);
492 chan
->timestamp_last_had_circuits
= approx_time();
495 if (circ
->n_delete_pending
&& old_chan
) {
496 channel_mark_circid_unusable(old_chan
, old_id
);
497 circ
->n_delete_pending
= 0;
502 * Helper function to publish a message about events on an origin circuit
504 * Publishes a message to subscribers of origin circuit events, and
505 * sends the control event.
508 circuit_event_status(origin_circuit_t
*circ
, circuit_status_event_t tp
,
511 ocirc_cevent_msg_t
*msg
= tor_malloc(sizeof(*msg
));
515 msg
->gid
= circ
->global_identifier
;
517 msg
->reason
= reason_code
;
518 msg
->onehop
= circ
->build_state
->onehop_tunnel
;
520 ocirc_cevent_publish(msg
);
521 return control_event_circuit_status(circ
, tp
, reason_code
);
525 * Helper function to publish a state change message
527 * circuit_set_state() calls this to notify subscribers about a change
528 * of the state of an origin circuit. @a circ must be an origin
532 circuit_state_publish(const circuit_t
*circ
)
534 ocirc_state_msg_t
*msg
= tor_malloc(sizeof(*msg
));
535 const origin_circuit_t
*ocirc
;
537 tor_assert(CIRCUIT_IS_ORIGIN(circ
));
538 ocirc
= CONST_TO_ORIGIN_CIRCUIT(circ
);
539 /* Only inbound OR circuits can be in this state, not origin circuits. */
540 tor_assert(circ
->state
!= CIRCUIT_STATE_ONIONSKIN_PENDING
);
542 msg
->gid
= ocirc
->global_identifier
;
543 msg
->state
= circ
->state
;
544 msg
->onehop
= ocirc
->build_state
->onehop_tunnel
;
546 ocirc_state_publish(msg
);
549 /** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
550 * it from lists as appropriate. */
552 circuit_set_state(circuit_t
*circ
, uint8_t state
)
555 if (state
== circ
->state
)
557 if (PREDICT_UNLIKELY(!circuits_pending_chans
))
558 circuits_pending_chans
= smartlist_new();
559 if (PREDICT_UNLIKELY(!circuits_pending_other_guards
))
560 circuits_pending_other_guards
= smartlist_new();
561 if (circ
->state
== CIRCUIT_STATE_CHAN_WAIT
) {
562 /* remove from waiting-circuit list. */
563 smartlist_remove(circuits_pending_chans
, circ
);
565 if (state
== CIRCUIT_STATE_CHAN_WAIT
) {
566 /* add to waiting-circuit list. */
567 smartlist_add(circuits_pending_chans
, circ
);
569 if (circ
->state
== CIRCUIT_STATE_GUARD_WAIT
) {
570 smartlist_remove(circuits_pending_other_guards
, circ
);
572 if (state
== CIRCUIT_STATE_GUARD_WAIT
) {
573 smartlist_add(circuits_pending_other_guards
, circ
);
575 if (state
== CIRCUIT_STATE_GUARD_WAIT
|| state
== CIRCUIT_STATE_OPEN
)
576 tor_assert(!circ
->n_chan_create_cell
);
578 tor_trace(TR_SUBSYS(circuit
), TR_EV(change_state
), circ
, circ
->state
, state
);
580 if (CIRCUIT_IS_ORIGIN(circ
))
581 circuit_state_publish(circ
);
584 /** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
585 * the given connection. */
587 circuit_get_all_pending_on_channel(smartlist_t
*out
, channel_t
*chan
)
592 if (!circuits_pending_chans
)
595 SMARTLIST_FOREACH_BEGIN(circuits_pending_chans
, circuit_t
*, circ
) {
596 if (circ
->marked_for_close
)
600 tor_assert(circ
->state
== CIRCUIT_STATE_CHAN_WAIT
);
601 if (tor_digest_is_zero(circ
->n_hop
->identity_digest
)) {
602 /* Look at addr/port. This is an unkeyed connection. */
603 if (!channel_matches_extend_info(chan
, circ
->n_hop
))
606 /* We expected a key. See if it's the right one. */
607 if (tor_memneq(chan
->identity_digest
,
608 circ
->n_hop
->identity_digest
, DIGEST_LEN
))
611 smartlist_add(out
, circ
);
612 } SMARTLIST_FOREACH_END(circ
);
615 /** Return the number of circuits in state CHAN_WAIT, waiting for the given
618 circuit_count_pending_on_channel(channel_t
*chan
)
621 smartlist_t
*sl
= smartlist_new();
625 circuit_get_all_pending_on_channel(sl
, chan
);
626 cnt
= smartlist_len(sl
);
628 log_debug(LD_CIRC
,"or_conn to %s, %d pending circs",
629 channel_describe_peer(chan
),
634 /** Remove <b>origin_circ</b> from the global list of origin circuits.
635 * Called when we are freeing a circuit.
638 circuit_remove_from_origin_circuit_list(origin_circuit_t
*origin_circ
)
640 int origin_idx
= origin_circ
->global_origin_circuit_list_idx
;
643 origin_circuit_t
*c2
;
644 tor_assert(origin_idx
<= smartlist_len(global_origin_circuit_list
));
645 c2
= smartlist_get(global_origin_circuit_list
, origin_idx
);
646 tor_assert(origin_circ
== c2
);
647 smartlist_del(global_origin_circuit_list
, origin_idx
);
648 if (origin_idx
< smartlist_len(global_origin_circuit_list
)) {
649 origin_circuit_t
*replacement
=
650 smartlist_get(global_origin_circuit_list
, origin_idx
);
651 replacement
->global_origin_circuit_list_idx
= origin_idx
;
653 origin_circ
->global_origin_circuit_list_idx
= -1;
656 /** Add <b>origin_circ</b> to the global list of origin circuits. Called
657 * when creating the circuit. */
659 circuit_add_to_origin_circuit_list(origin_circuit_t
*origin_circ
)
661 tor_assert(origin_circ
->global_origin_circuit_list_idx
== -1);
662 smartlist_t
*lst
= circuit_get_global_origin_circuit_list();
663 smartlist_add(lst
, origin_circ
);
664 origin_circ
->global_origin_circuit_list_idx
= smartlist_len(lst
) - 1;
667 /** Detach from the global circuit list, and deallocate, all
668 * circuits that have been marked for close.
671 circuit_close_all_marked(void)
673 if (circuits_pending_close
== NULL
)
676 smartlist_t
*lst
= circuit_get_global_list();
677 SMARTLIST_FOREACH_BEGIN(circuits_pending_close
, circuit_t
*, circ
) {
678 tor_assert(circ
->marked_for_close
);
680 /* Remove it from the circuit list. */
681 int idx
= circ
->global_circuitlist_idx
;
682 smartlist_del(lst
, idx
);
683 if (idx
< smartlist_len(lst
)) {
684 circuit_t
*replacement
= smartlist_get(lst
, idx
);
685 replacement
->global_circuitlist_idx
= idx
;
687 circ
->global_circuitlist_idx
= -1;
689 /* Remove it from the origin circuit list, if appropriate. */
690 if (CIRCUIT_IS_ORIGIN(circ
)) {
691 circuit_remove_from_origin_circuit_list(TO_ORIGIN_CIRCUIT(circ
));
694 circuit_about_to_free(circ
);
696 } SMARTLIST_FOREACH_END(circ
);
698 smartlist_clear(circuits_pending_close
);
701 /** Return a pointer to the global list of circuits. */
702 MOCK_IMPL(smartlist_t
*,
703 circuit_get_global_list
,(void))
705 if (NULL
== global_circuitlist
)
706 global_circuitlist
= smartlist_new();
707 return global_circuitlist
;
710 /** Return a pointer to the global list of origin circuits. */
712 circuit_get_global_origin_circuit_list(void)
714 if (NULL
== global_origin_circuit_list
)
715 global_origin_circuit_list
= smartlist_new();
716 return global_origin_circuit_list
;
720 * Return true if we have any opened general-purpose 3 hop
723 * The result from this function is cached for use by
724 * circuit_any_opened_circuits_cached().
727 circuit_any_opened_circuits(void)
729 SMARTLIST_FOREACH_BEGIN(circuit_get_global_origin_circuit_list(),
730 const origin_circuit_t
*, next_circ
) {
731 if (!TO_CIRCUIT(next_circ
)->marked_for_close
&&
732 next_circ
->has_opened
&&
733 TO_CIRCUIT(next_circ
)->state
== CIRCUIT_STATE_OPEN
&&
734 TO_CIRCUIT(next_circ
)->purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
&&
735 next_circ
->build_state
&&
736 next_circ
->build_state
->desired_path_len
== DEFAULT_ROUTE_LEN
) {
737 circuit_cache_opened_circuit_state(1);
740 } SMARTLIST_FOREACH_END(next_circ
);
742 circuit_cache_opened_circuit_state(0);
747 * Cache the "any circuits opened" state, as specified in param
748 * circuits_are_opened. This is a helper function to update
749 * the circuit opened status whenever we happen to look at the
753 circuit_cache_opened_circuit_state(int circuits_are_opened
)
755 any_opened_circs_cached_val
= circuits_are_opened
;
759 * Return true if there were any opened circuits since the last call to
760 * circuit_any_opened_circuits(), or since circuit_expire_building() last
761 * ran (it runs roughly once per second).
764 circuit_any_opened_circuits_cached(void)
766 return any_opened_circs_cached_val
;
769 /** Function to make circ-\>state human-readable */
771 circuit_state_to_string(int state
)
775 case CIRCUIT_STATE_BUILDING
: return "doing handshakes";
776 case CIRCUIT_STATE_ONIONSKIN_PENDING
: return "processing the onion";
777 case CIRCUIT_STATE_CHAN_WAIT
: return "connecting to server";
778 case CIRCUIT_STATE_GUARD_WAIT
: return "waiting to see how other "
780 case CIRCUIT_STATE_OPEN
: return "open";
782 log_warn(LD_BUG
, "Unknown circuit state %d", state
);
783 tor_snprintf(buf
, sizeof(buf
), "unknown state [%d]", state
);
788 /** Map a circuit purpose to a string suitable to be displayed to a
791 circuit_purpose_to_controller_string(uint8_t purpose
)
795 case CIRCUIT_PURPOSE_OR
:
796 case CIRCUIT_PURPOSE_INTRO_POINT
:
797 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
798 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
799 return "SERVER"; /* A controller should never see these, actually. */
801 case CIRCUIT_PURPOSE_C_GENERAL
:
804 case CIRCUIT_PURPOSE_C_HSDIR_GET
:
805 return "HS_CLIENT_HSDIR";
807 case CIRCUIT_PURPOSE_C_INTRODUCING
:
808 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
809 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
810 return "HS_CLIENT_INTRO";
812 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
813 case CIRCUIT_PURPOSE_C_REND_READY
:
814 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
815 case CIRCUIT_PURPOSE_C_REND_JOINED
:
816 return "HS_CLIENT_REND";
818 case CIRCUIT_PURPOSE_S_HSDIR_POST
:
819 return "HS_SERVICE_HSDIR";
821 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
822 case CIRCUIT_PURPOSE_S_INTRO
:
823 return "HS_SERVICE_INTRO";
825 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
826 case CIRCUIT_PURPOSE_S_REND_JOINED
:
827 return "HS_SERVICE_REND";
829 case CIRCUIT_PURPOSE_TESTING
:
831 case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
:
832 return "MEASURE_TIMEOUT";
833 case CIRCUIT_PURPOSE_CONTROLLER
:
835 case CIRCUIT_PURPOSE_PATH_BIAS_TESTING
:
836 return "PATH_BIAS_TESTING";
837 case CIRCUIT_PURPOSE_HS_VANGUARDS
:
838 return "HS_VANGUARDS";
839 case CIRCUIT_PURPOSE_C_CIRCUIT_PADDING
:
840 return "CIRCUIT_PADDING";
843 tor_snprintf(buf
, sizeof(buf
), "UNKNOWN_%d", (int)purpose
);
848 /** Return a string specifying the state of the hidden-service circuit
849 * purpose <b>purpose</b>, or NULL if <b>purpose</b> is not a
850 * hidden-service-related circuit purpose. */
852 circuit_purpose_to_controller_hs_state_string(uint8_t purpose
)
857 log_fn(LOG_WARN
, LD_BUG
,
858 "Unrecognized circuit purpose: %d",
860 tor_fragile_assert();
861 FALLTHROUGH_UNLESS_ALL_BUGS_ARE_FATAL
;
863 case CIRCUIT_PURPOSE_OR
:
864 case CIRCUIT_PURPOSE_C_GENERAL
:
865 case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
:
866 case CIRCUIT_PURPOSE_TESTING
:
867 case CIRCUIT_PURPOSE_CONTROLLER
:
868 case CIRCUIT_PURPOSE_PATH_BIAS_TESTING
:
869 case CIRCUIT_PURPOSE_HS_VANGUARDS
:
870 case CIRCUIT_PURPOSE_C_CIRCUIT_PADDING
:
873 case CIRCUIT_PURPOSE_INTRO_POINT
:
874 return "OR_HSSI_ESTABLISHED";
875 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
876 return "OR_HSCR_ESTABLISHED";
877 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
878 return "OR_HS_R_JOINED";
880 case CIRCUIT_PURPOSE_C_HSDIR_GET
:
881 case CIRCUIT_PURPOSE_C_INTRODUCING
:
882 return "HSCI_CONNECTING";
883 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
884 return "HSCI_INTRO_SENT";
885 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
888 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
889 return "HSCR_CONNECTING";
890 case CIRCUIT_PURPOSE_C_REND_READY
:
891 return "HSCR_ESTABLISHED_IDLE";
892 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
893 return "HSCR_ESTABLISHED_WAITING";
894 case CIRCUIT_PURPOSE_C_REND_JOINED
:
895 return "HSCR_JOINED";
897 case CIRCUIT_PURPOSE_S_HSDIR_POST
:
898 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
899 return "HSSI_CONNECTING";
900 case CIRCUIT_PURPOSE_S_INTRO
:
901 return "HSSI_ESTABLISHED";
903 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
904 return "HSSR_CONNECTING";
905 case CIRCUIT_PURPOSE_S_REND_JOINED
:
906 return "HSSR_JOINED";
910 /** Return a human-readable string for the circuit purpose <b>purpose</b>. */
912 circuit_purpose_to_string(uint8_t purpose
)
918 case CIRCUIT_PURPOSE_OR
:
919 return "Circuit at relay";
920 case CIRCUIT_PURPOSE_INTRO_POINT
:
921 return "Acting as intro point";
922 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
923 return "Acting as rendezvous (pending)";
924 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
925 return "Acting as rendezvous (established)";
926 case CIRCUIT_PURPOSE_C_GENERAL
:
927 return "General-purpose client";
928 case CIRCUIT_PURPOSE_C_INTRODUCING
:
929 return "Hidden service client: Connecting to intro point";
930 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
931 return "Hidden service client: Waiting for ack from intro point";
932 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
933 return "Hidden service client: Received ack from intro point";
934 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
935 return "Hidden service client: Establishing rendezvous point";
936 case CIRCUIT_PURPOSE_C_REND_READY
:
937 return "Hidden service client: Pending rendezvous point";
938 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
939 return "Hidden service client: Pending rendezvous point (ack received)";
940 case CIRCUIT_PURPOSE_C_REND_JOINED
:
941 return "Hidden service client: Active rendezvous point";
942 case CIRCUIT_PURPOSE_C_HSDIR_GET
:
943 return "Hidden service client: Fetching HS descriptor";
945 case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
:
946 return "Measuring circuit timeout";
948 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
949 return "Hidden service: Establishing introduction point";
950 case CIRCUIT_PURPOSE_S_INTRO
:
951 return "Hidden service: Introduction point";
952 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
953 return "Hidden service: Connecting to rendezvous point";
954 case CIRCUIT_PURPOSE_S_REND_JOINED
:
955 return "Hidden service: Active rendezvous point";
956 case CIRCUIT_PURPOSE_S_HSDIR_POST
:
957 return "Hidden service: Uploading HS descriptor";
959 case CIRCUIT_PURPOSE_TESTING
:
960 return "Testing circuit";
962 case CIRCUIT_PURPOSE_CONTROLLER
:
963 return "Circuit made by controller";
965 case CIRCUIT_PURPOSE_PATH_BIAS_TESTING
:
966 return "Path-bias testing circuit";
968 case CIRCUIT_PURPOSE_HS_VANGUARDS
:
969 return "Hidden service: Pre-built vanguard circuit";
971 case CIRCUIT_PURPOSE_C_CIRCUIT_PADDING
:
972 return "Circuit kept open for padding";
975 tor_snprintf(buf
, sizeof(buf
), "UNKNOWN_%d", (int)purpose
);
980 /** Pick a reasonable package_window to start out for our circuits.
981 * Originally this was hard-coded at 1000, but now the consensus votes
982 * on the answer. See proposal 168. */
984 circuit_initial_package_window(void)
986 int32_t num
= networkstatus_get_param(NULL
, "circwindow", CIRCWINDOW_START
,
987 CIRCWINDOW_START_MIN
,
988 CIRCWINDOW_START_MAX
);
989 /* If the consensus tells us a negative number, we'd assert. */
991 num
= CIRCWINDOW_START
;
995 /** Initialize the common elements in a circuit_t, and add it to the global
998 init_circuit_base(circuit_t
*circ
)
1000 tor_gettimeofday(&circ
->timestamp_created
);
1002 // Gets reset when we send CREATE_FAST.
1003 // circuit_expire_building() expects these to be equal
1004 // until the orconn is built.
1005 circ
->timestamp_began
= circ
->timestamp_created
;
1007 circ
->package_window
= circuit_initial_package_window();
1008 circ
->deliver_window
= CIRCWINDOW_START
;
1009 circuit_reset_sendme_randomness(circ
);
1010 cell_queue_init(&circ
->n_chan_cells
);
1012 smartlist_add(circuit_get_global_list(), circ
);
1013 circ
->global_circuitlist_idx
= smartlist_len(circuit_get_global_list()) - 1;
1016 /** If we haven't yet decided on a good timeout value for circuit
1017 * building, we close idle circuits aggressively so we can get more
1018 * data points. These are the default, min, and max consensus values */
1019 #define DFLT_IDLE_TIMEOUT_WHILE_LEARNING (3*60)
1020 #define MIN_IDLE_TIMEOUT_WHILE_LEARNING (10)
1021 #define MAX_IDLE_TIMEOUT_WHILE_LEARNING (1000*60)
1023 /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
1024 * and <b>p_conn</b>. Add it to the global circuit list.
1027 origin_circuit_new(void)
1029 origin_circuit_t
*circ
;
1030 /* never zero, since a global ID of 0 is treated specially by the
1032 static uint32_t n_circuits_allocated
= 1;
1034 circ
= tor_malloc_zero(sizeof(origin_circuit_t
));
1035 circ
->base_
.magic
= ORIGIN_CIRCUIT_MAGIC
;
1037 circ
->next_stream_id
= crypto_rand_int(1<<16);
1038 circ
->global_identifier
= n_circuits_allocated
++;
1039 circ
->remaining_relay_early_cells
= MAX_RELAY_EARLY_CELLS_PER_CIRCUIT
;
1040 circ
->remaining_relay_early_cells
-= crypto_rand_int(2);
1042 init_circuit_base(TO_CIRCUIT(circ
));
1044 /* Add to origin-list. */
1045 circ
->global_origin_circuit_list_idx
= -1;
1046 circuit_add_to_origin_circuit_list(circ
);
1048 circuit_build_times_update_last_circ(get_circuit_build_times_mutable());
1050 if (! circuit_build_times_disabled(get_options()) &&
1051 circuit_build_times_needs_circuits(get_circuit_build_times())) {
1052 /* Circuits should be shorter lived if we need more of them
1053 * for learning a good build timeout */
1054 circ
->circuit_idle_timeout
=
1055 networkstatus_get_param(NULL
, "cbtlearntimeout",
1056 DFLT_IDLE_TIMEOUT_WHILE_LEARNING
,
1057 MIN_IDLE_TIMEOUT_WHILE_LEARNING
,
1058 MAX_IDLE_TIMEOUT_WHILE_LEARNING
);
1060 // This should always be larger than the current port prediction time
1061 // remaining, or else we'll end up with the case where a circuit times out
1062 // and another one is built, effectively doubling the timeout window.
1064 // We also randomize it by up to 5% more (ie 5% of 0 to 3600 seconds,
1065 // depending on how much circuit prediction time is remaining) so that
1066 // we don't close a bunch of unused circuits all at the same time.
1067 int prediction_time_remaining
=
1068 predicted_ports_prediction_time_remaining(time(NULL
));
1069 circ
->circuit_idle_timeout
= prediction_time_remaining
+1+
1070 crypto_rand_int(1+prediction_time_remaining
/20);
1072 if (circ
->circuit_idle_timeout
<= 0) {
1074 "Circuit chose a negative idle timeout of %d based on "
1075 "%d seconds of predictive building remaining.",
1076 circ
->circuit_idle_timeout
,
1077 prediction_time_remaining
);
1078 circ
->circuit_idle_timeout
=
1079 networkstatus_get_param(NULL
, "cbtlearntimeout",
1080 DFLT_IDLE_TIMEOUT_WHILE_LEARNING
,
1081 MIN_IDLE_TIMEOUT_WHILE_LEARNING
,
1082 MAX_IDLE_TIMEOUT_WHILE_LEARNING
);
1086 "Circuit %"PRIu32
" chose an idle timeout of %d based on "
1087 "%d seconds of predictive building remaining.",
1088 (circ
->global_identifier
),
1089 circ
->circuit_idle_timeout
,
1090 prediction_time_remaining
);
1093 tor_trace(TR_SUBSYS(circuit
), TR_EV(new_origin
), circ
);
1097 /** Allocate a new or_circuit_t, connected to <b>p_chan</b> as
1098 * <b>p_circ_id</b>. If <b>p_chan</b> is NULL, the circuit is unattached. */
1100 or_circuit_new(circid_t p_circ_id
, channel_t
*p_chan
)
1105 circ
= tor_malloc_zero(sizeof(or_circuit_t
));
1106 circ
->base_
.magic
= OR_CIRCUIT_MAGIC
;
1109 circuit_set_p_circid_chan(circ
, p_circ_id
, p_chan
);
1111 circ
->remaining_relay_early_cells
= MAX_RELAY_EARLY_CELLS_PER_CIRCUIT
;
1112 cell_queue_init(&circ
->p_chan_cells
);
1114 init_circuit_base(TO_CIRCUIT(circ
));
1116 tor_trace(TR_SUBSYS(circuit
), TR_EV(new_or
), circ
);
1120 /** Free all storage held in circ->testing_cell_stats */
1122 circuit_clear_testing_cell_stats(circuit_t
*circ
)
1124 if (!circ
|| !circ
->testing_cell_stats
)
1126 SMARTLIST_FOREACH(circ
->testing_cell_stats
, testing_cell_stats_entry_t
*,
1127 ent
, tor_free(ent
));
1128 smartlist_free(circ
->testing_cell_stats
);
1129 circ
->testing_cell_stats
= NULL
;
1132 /** Deallocate space associated with circ.
1135 circuit_free_(circuit_t
*circ
)
1137 circid_t n_circ_id
= 0;
1140 int should_free
= 1;
1144 /* We keep a copy of this so we can log its value before it gets unset. */
1145 n_circ_id
= circ
->n_circ_id
;
1147 circuit_clear_testing_cell_stats(circ
);
1149 /* Cleanup circuit from anything HS v3 related. We also do this when the
1150 * circuit is closed. This is to avoid any code path that free registered
1151 * circuits without closing them before. This needs to be done before the
1152 * hs identifier is freed. */
1153 hs_circ_cleanup_on_free(circ
);
1155 congestion_control_free(circ
->ccontrol
);
1157 if (CIRCUIT_IS_ORIGIN(circ
)) {
1158 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
1160 memlen
= sizeof(origin_circuit_t
);
1161 tor_assert(circ
->magic
== ORIGIN_CIRCUIT_MAGIC
);
1163 circuit_remove_from_origin_circuit_list(ocirc
);
1165 if (ocirc
->half_streams
) {
1166 SMARTLIST_FOREACH_BEGIN(ocirc
->half_streams
, half_edge_t
*,
1168 half_edge_free(half_conn
);
1169 } SMARTLIST_FOREACH_END(half_conn
);
1170 smartlist_free(ocirc
->half_streams
);
1173 if (ocirc
->build_state
) {
1174 extend_info_free(ocirc
->build_state
->chosen_exit
);
1176 tor_free(ocirc
->build_state
);
1178 /* Cancel before freeing, if we haven't already succeeded or failed. */
1179 if (ocirc
->guard_state
) {
1180 entry_guard_cancel(ô
->guard_state
);
1182 circuit_guard_state_free(ocirc
->guard_state
);
1184 circuit_clear_cpath(ocirc
);
1186 crypto_pk_free(ocirc
->intro_key
);
1188 /* Finally, free the identifier of the circuit and nullify it so multiple
1189 * cleanup will work. */
1190 hs_ident_circuit_free(ocirc
->hs_ident
);
1191 ocirc
->hs_ident
= NULL
;
1193 tor_free(ocirc
->dest_address
);
1194 if (ocirc
->socks_username
) {
1195 memwipe(ocirc
->socks_username
, 0x12, ocirc
->socks_username_len
);
1196 tor_free(ocirc
->socks_username
);
1198 if (ocirc
->socks_password
) {
1199 memwipe(ocirc
->socks_password
, 0x06, ocirc
->socks_password_len
);
1200 tor_free(ocirc
->socks_password
);
1202 addr_policy_list_free(ocirc
->prepend_policy
);
1204 or_circuit_t
*ocirc
= TO_OR_CIRCUIT(circ
);
1205 /* Remember cell statistics for this circuit before deallocating. */
1206 if (get_options()->CellStatistics
)
1207 rep_hist_buffer_stats_add_circ(circ
, time(NULL
));
1209 memlen
= sizeof(or_circuit_t
);
1210 tor_assert(circ
->magic
== OR_CIRCUIT_MAGIC
);
1212 should_free
= (ocirc
->workqueue_entry
== NULL
);
1214 relay_crypto_clear(ô
->crypto
);
1216 if (ocirc
->rend_splice
) {
1217 or_circuit_t
*other
= ocirc
->rend_splice
;
1218 tor_assert(other
->base_
.magic
== OR_CIRCUIT_MAGIC
);
1219 other
->rend_splice
= NULL
;
1222 /* remove from map. */
1223 circuit_set_p_circid_chan(ocirc
, 0, NULL
);
1225 /* Clear cell queue _after_ removing it from the map. Otherwise our
1226 * "active" checks will be violated. */
1227 cell_queue_clear(ô
->p_chan_cells
);
1230 extend_info_free(circ
->n_hop
);
1231 tor_free(circ
->n_chan_create_cell
);
1233 if (circ
->global_circuitlist_idx
!= -1) {
1234 int idx
= circ
->global_circuitlist_idx
;
1235 circuit_t
*c2
= smartlist_get(global_circuitlist
, idx
);
1236 tor_assert(c2
== circ
);
1237 smartlist_del(global_circuitlist
, idx
);
1238 if (idx
< smartlist_len(global_circuitlist
)) {
1239 c2
= smartlist_get(global_circuitlist
, idx
);
1240 c2
->global_circuitlist_idx
= idx
;
1244 /* Remove from map. */
1245 circuit_set_n_circid_chan(circ
, 0, NULL
);
1247 /* Clear cell queue _after_ removing it from the map. Otherwise our
1248 * "active" checks will be violated. */
1249 cell_queue_clear(&circ
->n_chan_cells
);
1251 /* Cleanup possible SENDME state. */
1252 if (circ
->sendme_last_digests
) {
1253 SMARTLIST_FOREACH(circ
->sendme_last_digests
, uint8_t *, d
, tor_free(d
));
1254 smartlist_free(circ
->sendme_last_digests
);
1257 log_info(LD_CIRC
, "Circuit %u (id: %" PRIu32
") has been freed.",
1259 CIRCUIT_IS_ORIGIN(circ
) ?
1260 TO_ORIGIN_CIRCUIT(circ
)->global_identifier
: 0);
1262 /* Free any circuit padding structures */
1263 circpad_circuit_free_all_machineinfos(circ
);
1265 /* Clear all dangling handle references. */
1266 circuit_handles_clear(circ
);
1268 /* Tracepoint. Data within the circuit object is recorded so do this before
1269 * the actual memory free. */
1270 tor_trace(TR_SUBSYS(circuit
), TR_EV(free
), circ
);
1273 memwipe(mem
, 0xAA, memlen
); /* poison memory */
1276 /* If we made it here, this is an or_circuit_t that still has a pending
1277 * cpuworker request which we weren't able to cancel. Instead, set up
1278 * the magic value so that when the reply comes back, we'll know to discard
1279 * the reply and free this structure.
1281 memwipe(mem
, 0xAA, memlen
);
1282 circ
->magic
= DEAD_CIRCUIT_MAGIC
;
1286 /** Deallocate the linked list circ-><b>cpath</b>, and remove the cpath from
1289 circuit_clear_cpath(origin_circuit_t
*circ
)
1291 crypt_path_t
*victim
, *head
, *cpath
;
1293 head
= cpath
= circ
->cpath
;
1298 /* it's a circular list, so we have to notice when we've
1299 * gone through it once. */
1300 while (cpath
->next
&& cpath
->next
!= head
) {
1302 cpath
= victim
->next
;
1311 /** Release all storage held by circuits. */
1313 circuit_free_all(void)
1315 smartlist_t
*lst
= circuit_get_global_list();
1317 SMARTLIST_FOREACH_BEGIN(lst
, circuit_t
*, tmp
) {
1318 if (! CIRCUIT_IS_ORIGIN(tmp
)) {
1319 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(tmp
);
1320 while (or_circ
->resolving_streams
) {
1321 edge_connection_t
*next_conn
;
1322 next_conn
= or_circ
->resolving_streams
->next_stream
;
1323 connection_free_(TO_CONN(or_circ
->resolving_streams
));
1324 or_circ
->resolving_streams
= next_conn
;
1327 tmp
->global_circuitlist_idx
= -1;
1328 circuit_about_to_free_atexit(tmp
);
1330 SMARTLIST_DEL_CURRENT(lst
, tmp
);
1331 } SMARTLIST_FOREACH_END(tmp
);
1333 smartlist_free(lst
);
1334 global_circuitlist
= NULL
;
1336 smartlist_free(global_origin_circuit_list
);
1337 global_origin_circuit_list
= NULL
;
1339 smartlist_free(circuits_pending_chans
);
1340 circuits_pending_chans
= NULL
;
1342 smartlist_free(circuits_pending_close
);
1343 circuits_pending_close
= NULL
;
1345 smartlist_free(circuits_pending_other_guards
);
1346 circuits_pending_other_guards
= NULL
;
1349 chan_circid_circuit_map_t
**elt
, **next
, *c
;
1350 for (elt
= HT_START(chan_circid_map
, &chan_circid_map
);
1354 next
= HT_NEXT_RMV(chan_circid_map
, &chan_circid_map
, elt
);
1356 tor_assert(c
->circuit
== NULL
);
1360 HT_CLEAR(chan_circid_map
, &chan_circid_map
);
1363 /** A helper function for circuit_dump_by_conn() below. Log a bunch
1364 * of information about circuit <b>circ</b>.
1367 circuit_dump_conn_details(int severity
,
1369 int conn_array_index
,
1371 circid_t this_circid
,
1372 circid_t other_circid
)
1374 tor_log(severity
, LD_CIRC
, "Conn %d has %s circuit: circID %u "
1375 "(other side %u), state %d (%s), born %ld:",
1376 conn_array_index
, type
, (unsigned)this_circid
, (unsigned)other_circid
,
1377 circ
->state
, circuit_state_to_string(circ
->state
),
1378 (long)circ
->timestamp_began
.tv_sec
);
1379 if (CIRCUIT_IS_ORIGIN(circ
)) { /* circ starts at this node */
1380 circuit_log_path(severity
, LD_CIRC
, TO_ORIGIN_CIRCUIT(circ
));
1384 /** Log, at severity <b>severity</b>, information about each circuit
1385 * that is connected to <b>conn</b>.
1388 circuit_dump_by_conn(connection_t
*conn
, int severity
)
1390 edge_connection_t
*tmpconn
;
1392 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
1393 circid_t n_circ_id
= circ
->n_circ_id
, p_circ_id
= 0;
1395 if (circ
->marked_for_close
) {
1399 if (!CIRCUIT_IS_ORIGIN(circ
)) {
1400 p_circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
1403 if (CIRCUIT_IS_ORIGIN(circ
)) {
1404 for (tmpconn
=TO_ORIGIN_CIRCUIT(circ
)->p_streams
; tmpconn
;
1405 tmpconn
=tmpconn
->next_stream
) {
1406 if (TO_CONN(tmpconn
) == conn
) {
1407 circuit_dump_conn_details(severity
, circ
, conn
->conn_array_index
,
1408 "App-ward", p_circ_id
, n_circ_id
);
1413 if (! CIRCUIT_IS_ORIGIN(circ
)) {
1414 for (tmpconn
=TO_OR_CIRCUIT(circ
)->n_streams
; tmpconn
;
1415 tmpconn
=tmpconn
->next_stream
) {
1416 if (TO_CONN(tmpconn
) == conn
) {
1417 circuit_dump_conn_details(severity
, circ
, conn
->conn_array_index
,
1418 "Exit-ward", n_circ_id
, p_circ_id
);
1423 SMARTLIST_FOREACH_END(circ
);
1426 /** Return the circuit whose global ID is <b>id</b>, or NULL if no
1427 * such circuit exists. */
1429 circuit_get_by_global_id(uint32_t id
)
1431 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
1432 if (CIRCUIT_IS_ORIGIN(circ
) &&
1433 TO_ORIGIN_CIRCUIT(circ
)->global_identifier
== id
) {
1434 if (circ
->marked_for_close
)
1437 return TO_ORIGIN_CIRCUIT(circ
);
1440 SMARTLIST_FOREACH_END(circ
);
1444 /** Return a circ such that:
1445 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
1446 * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
1447 * Return NULL if no such circuit exists.
1449 * If <b>found_entry_out</b> is provided, set it to true if we have a
1450 * placeholder entry for circid/chan, and leave it unset otherwise.
1452 static inline circuit_t
*
1453 circuit_get_by_circid_channel_impl(circid_t circ_id
, channel_t
*chan
,
1454 int *found_entry_out
)
1456 chan_circid_circuit_map_t search
;
1457 chan_circid_circuit_map_t
*found
;
1459 if (_last_circid_chan_ent
&&
1460 circ_id
== _last_circid_chan_ent
->circ_id
&&
1461 chan
== _last_circid_chan_ent
->chan
) {
1462 found
= _last_circid_chan_ent
;
1464 search
.circ_id
= circ_id
;
1466 found
= HT_FIND(chan_circid_map
, &chan_circid_map
, &search
);
1467 _last_circid_chan_ent
= found
;
1469 if (found
&& found
->circuit
) {
1471 "circuit_get_by_circid_channel_impl() returning circuit %p for"
1472 " circ_id %u, channel ID %"PRIu64
" (%p)",
1473 found
->circuit
, (unsigned)circ_id
,
1474 (chan
->global_identifier
), chan
);
1475 if (found_entry_out
)
1476 *found_entry_out
= 1;
1477 return found
->circuit
;
1481 "circuit_get_by_circid_channel_impl() found %s for"
1482 " circ_id %u, channel ID %"PRIu64
" (%p)",
1483 found
? "placeholder" : "nothing",
1485 (chan
->global_identifier
), chan
);
1487 if (found_entry_out
)
1488 *found_entry_out
= found
? 1 : 0;
1491 /* The rest of this checks for bugs. Disabled by default. */
1492 /* We comment it out because coverity complains otherwise.
1495 TOR_LIST_FOREACH(circ, &global_circuitlist, head) {
1496 if (! CIRCUIT_IS_ORIGIN(circ)) {
1497 or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
1498 if (or_circ->p_chan == chan && or_circ->p_circ_id == circ_id) {
1500 "circuit matches p_chan, but not in hash table (Bug!)");
1504 if (circ->n_chan == chan && circ->n_circ_id == circ_id) {
1506 "circuit matches n_chan, but not in hash table (Bug!)");
1514 /** Return a circ such that:
1515 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
1516 * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
1517 * - circ is not marked for close.
1518 * Return NULL if no such circuit exists.
1521 circuit_get_by_circid_channel(circid_t circ_id
, channel_t
*chan
)
1523 circuit_t
*circ
= circuit_get_by_circid_channel_impl(circ_id
, chan
, NULL
);
1524 if (!circ
|| circ
->marked_for_close
)
1530 /** Return a circ such that:
1531 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
1532 * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
1533 * Return NULL if no such circuit exists.
1536 circuit_get_by_circid_channel_even_if_marked(circid_t circ_id
,
1539 return circuit_get_by_circid_channel_impl(circ_id
, chan
, NULL
);
1542 /** Return true iff the circuit ID <b>circ_id</b> is currently used by a
1543 * circuit, marked or not, on <b>chan</b>, or if the circ ID is reserved until
1544 * a queued destroy cell can be sent.
1546 * (Return 1 if the circuit is present, marked or not; Return 2
1547 * if the circuit ID is pending a destroy.)
1550 circuit_id_in_use_on_channel(circid_t circ_id
, channel_t
*chan
)
1553 if (circuit_get_by_circid_channel_impl(circ_id
, chan
, &found
) != NULL
)
1560 /** Helper for debugging 12184. Returns the time since which 'circ_id' has
1561 * been marked unusable on 'chan'. */
1563 circuit_id_when_marked_unusable_on_channel(circid_t circ_id
, channel_t
*chan
)
1565 chan_circid_circuit_map_t search
;
1566 chan_circid_circuit_map_t
*found
;
1568 memset(&search
, 0, sizeof(search
));
1569 search
.circ_id
= circ_id
;
1572 found
= HT_FIND(chan_circid_map
, &chan_circid_map
, &search
);
1574 if (! found
|| found
->circuit
)
1577 return found
->made_placeholder_at
;
1580 /** Return the circuit that a given edge connection is using. */
1582 circuit_get_by_edge_conn(edge_connection_t
*conn
)
1586 circ
= conn
->on_circuit
;
1588 (CIRCUIT_IS_ORIGIN(circ
) ? circ
->magic
== ORIGIN_CIRCUIT_MAGIC
1589 : circ
->magic
== OR_CIRCUIT_MAGIC
));
1594 /** For each circuit that has <b>chan</b> as n_chan or p_chan, unlink the
1595 * circuit from the chan,circid map, and mark it for close if it hasn't
1596 * been marked already.
1599 circuit_unlink_all_from_channel(channel_t
*chan
, int reason
)
1601 smartlist_t
*detached
= smartlist_new();
1603 /* #define DEBUG_CIRCUIT_UNLINK_ALL */
1605 channel_unlink_all_circuits(chan
, detached
);
1607 #ifdef DEBUG_CIRCUIT_UNLINK_ALL
1609 smartlist_t
*detached_2
= smartlist_new();
1610 int mismatch
= 0, badlen
= 0;
1612 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
1613 if (circ
->n_chan
== chan
||
1614 (!CIRCUIT_IS_ORIGIN(circ
) &&
1615 TO_OR_CIRCUIT(circ
)->p_chan
== chan
)) {
1616 smartlist_add(detached_2
, circ
);
1619 SMARTLIST_FOREACH_END(circ
);
1621 if (smartlist_len(detached
) != smartlist_len(detached_2
)) {
1622 log_warn(LD_BUG
, "List of detached circuits had the wrong length! "
1623 "(got %d, should have gotten %d)",
1624 (int)smartlist_len(detached
),
1625 (int)smartlist_len(detached_2
));
1628 smartlist_sort_pointers(detached
);
1629 smartlist_sort_pointers(detached_2
);
1631 SMARTLIST_FOREACH(detached
, circuit_t
*, c
,
1632 if (c
!= smartlist_get(detached_2
, c_sl_idx
))
1637 log_warn(LD_BUG
, "Mismatch in list of detached circuits.");
1639 if (badlen
|| mismatch
) {
1640 smartlist_free(detached
);
1641 detached
= detached_2
;
1643 log_notice(LD_CIRC
, "List of %d circuits was as expected.",
1644 (int)smartlist_len(detached
));
1645 smartlist_free(detached_2
);
1648 #endif /* defined(DEBUG_CIRCUIT_UNLINK_ALL) */
1650 SMARTLIST_FOREACH_BEGIN(detached
, circuit_t
*, circ
) {
1652 if (circ
->n_chan
== chan
) {
1654 circuit_set_n_circid_chan(circ
, 0, NULL
);
1657 /* If we didn't request this closure, pass the remote
1658 * bit to mark_for_close. */
1659 if (chan
->reason_for_closing
!= CHANNEL_CLOSE_REQUESTED
)
1660 reason
|= END_CIRC_REASON_FLAG_REMOTE
;
1662 if (! CIRCUIT_IS_ORIGIN(circ
)) {
1663 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
1664 if (or_circ
->p_chan
== chan
) {
1665 circuit_set_p_circid_chan(or_circ
, 0, NULL
);
1670 log_warn(LD_BUG
, "Circuit on detached list which I had no reason "
1674 if (!circ
->marked_for_close
)
1675 circuit_mark_for_close(circ
, reason
);
1676 } SMARTLIST_FOREACH_END(circ
);
1678 smartlist_free(detached
);
1681 /** Return the first introduction circuit originating from the global circuit
1682 * list after <b>start</b> or at the start of the list if <b>start</b> is
1683 * NULL. Return NULL if no circuit is found.
1685 * If <b>want_client_circ</b> is true, then we are looking for client-side
1686 * introduction circuits: A client introduction point circuit has a purpose of
1687 * either CIRCUIT_PURPOSE_C_INTRODUCING, CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
1688 * or CIRCUIT_PURPOSE_C_INTRODUCE_ACKED. This does not return a circuit marked
1689 * for close, but it returns circuits regardless of their circuit state.
1691 * If <b>want_client_circ</b> is false, then we are looking for service-side
1692 * introduction circuits: A service introduction point circuit has a purpose of
1693 * either CIRCUIT_PURPOSE_S_ESTABLISH_INTRO or CIRCUIT_PURPOSE_S_INTRO. This
1694 * does not return circuits marked for close, or in any state other than open.
1697 circuit_get_next_intro_circ(const origin_circuit_t
*start
,
1698 bool want_client_circ
)
1701 smartlist_t
*lst
= circuit_get_global_list();
1704 idx
= TO_CIRCUIT(start
)->global_circuitlist_idx
+ 1;
1707 for ( ; idx
< smartlist_len(lst
); ++idx
) {
1708 circuit_t
*circ
= smartlist_get(lst
, idx
);
1710 /* Ignore a marked for close circuit or if the state is not open. */
1711 if (circ
->marked_for_close
) {
1715 /* Depending on whether we are looking for client or service circs, skip
1716 * circuits with other purposes. */
1717 if (want_client_circ
) {
1718 if (circ
->purpose
!= CIRCUIT_PURPOSE_C_INTRODUCING
&&
1719 circ
->purpose
!= CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
&&
1720 circ
->purpose
!= CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
) {
1723 } else { /* we are looking for service-side circs */
1724 if (circ
->state
!= CIRCUIT_STATE_OPEN
) {
1727 if (circ
->purpose
!= CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
&&
1728 circ
->purpose
!= CIRCUIT_PURPOSE_S_INTRO
) {
1733 /* The purposes we are looking for are only for origin circuits so the
1734 * following is valid. */
1735 return TO_ORIGIN_CIRCUIT(circ
);
1741 /** Return the first service rendezvous circuit originating from the global
1742 * circuit list after <b>start</b> or at the start of the list if <b>start</b>
1743 * is NULL. Return NULL if no circuit is found.
1745 * A service rendezvous point circuit has a purpose of either
1746 * CIRCUIT_PURPOSE_S_CONNECT_REND or CIRCUIT_PURPOSE_S_REND_JOINED. This does
1747 * not return a circuit marked for close and its state must be open. */
1749 circuit_get_next_service_rp_circ(origin_circuit_t
*start
)
1752 smartlist_t
*lst
= circuit_get_global_list();
1755 idx
= TO_CIRCUIT(start
)->global_circuitlist_idx
+ 1;
1758 for ( ; idx
< smartlist_len(lst
); ++idx
) {
1759 circuit_t
*circ
= smartlist_get(lst
, idx
);
1761 /* Ignore a marked for close circuit or purpose not matching a service
1762 * intro point or if the state is not open. */
1763 if (circ
->marked_for_close
|| circ
->state
!= CIRCUIT_STATE_OPEN
||
1764 (circ
->purpose
!= CIRCUIT_PURPOSE_S_CONNECT_REND
&&
1765 circ
->purpose
!= CIRCUIT_PURPOSE_S_REND_JOINED
)) {
1768 /* The purposes we are looking for are only for origin circuits so the
1769 * following is valid. */
1770 return TO_ORIGIN_CIRCUIT(circ
);
1776 /** Return the first circuit originating here in global_circuitlist after
1777 * <b>start</b> whose purpose is <b>purpose</b>. Return NULL if no circuit is
1778 * found. If <b>start</b> is NULL, begin at the start of the list. */
1780 circuit_get_next_by_purpose(origin_circuit_t
*start
, uint8_t purpose
)
1783 smartlist_t
*lst
= circuit_get_global_list();
1784 tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose
));
1788 idx
= TO_CIRCUIT(start
)->global_circuitlist_idx
+ 1;
1790 for ( ; idx
< smartlist_len(lst
); ++idx
) {
1791 circuit_t
*circ
= smartlist_get(lst
, idx
);
1793 if (circ
->marked_for_close
)
1795 if (circ
->purpose
!= purpose
)
1797 /* At this point we should be able to get a valid origin circuit because
1798 * the origin purpose we are looking for matches this circuit. */
1799 if (BUG(!CIRCUIT_PURPOSE_IS_ORIGIN(circ
->purpose
))) {
1802 return TO_ORIGIN_CIRCUIT(circ
);
1807 /** We might cannibalize this circuit: Return true if its last hop can be used
1808 * as a v3 rendezvous point. */
1810 circuit_can_be_cannibalized_for_v3_rp(const origin_circuit_t
*circ
)
1812 if (!circ
->build_state
) {
1816 extend_info_t
*chosen_exit
= circ
->build_state
->chosen_exit
;
1817 if (BUG(!chosen_exit
)) {
1821 const node_t
*rp_node
= node_get_by_id(chosen_exit
->identity_digest
);
1823 if (node_supports_v3_rendezvous_point(rp_node
)) {
1831 /** We are trying to create a circuit of purpose <b>purpose</b> and we are
1832 * looking for cannibalizable circuits. Return the circuit purpose we would be
1833 * willing to cannibalize. */
1835 get_circuit_purpose_needed_to_cannibalize(uint8_t purpose
)
1837 if (circuit_should_use_vanguards(purpose
)) {
1838 /* If we are using vanguards, then we should only cannibalize vanguard
1839 * circuits so that we get the same path construction logic. */
1840 return CIRCUIT_PURPOSE_HS_VANGUARDS
;
1842 /* If no vanguards are used just get a general circuit! */
1843 return CIRCUIT_PURPOSE_C_GENERAL
;
1847 /** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL,
1848 * has a timestamp_dirty value of 0, has flags matching the CIRCLAUNCH_*
1849 * flags in <b>flags</b>, and if info is defined, does not already use info
1850 * as any of its hops; or NULL if no circuit fits this description.
1852 * The <b>purpose</b> argument refers to the purpose of the circuit we want to
1853 * create, not the purpose of the circuit we want to cannibalize.
1855 * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits.
1857 * To "cannibalize" a circuit means to extend it an extra hop, and use it
1858 * for some other purpose than we had originally intended. We do this when
1859 * we want to perform some low-bandwidth task at a specific relay, and we
1860 * would like the circuit to complete as soon as possible. (If we were going
1861 * to use a lot of bandwidth, we wouldn't want a circuit with an extra hop.
1862 * If we didn't care about circuit completion latency, we would just build
1866 circuit_find_to_cannibalize(uint8_t purpose_to_produce
, extend_info_t
*info
,
1869 origin_circuit_t
*best
=NULL
;
1870 int need_uptime
= (flags
& CIRCLAUNCH_NEED_UPTIME
) != 0;
1871 int need_capacity
= (flags
& CIRCLAUNCH_NEED_CAPACITY
) != 0;
1872 int internal
= (flags
& CIRCLAUNCH_IS_INTERNAL
) != 0;
1873 const or_options_t
*options
= get_options();
1874 /* We want the circuit we are trying to cannibalize to have this purpose */
1875 int purpose_to_search_for
;
1877 /* Make sure we're not trying to create a onehop circ by
1878 * cannibalization. */
1879 tor_assert(!(flags
& CIRCLAUNCH_ONEHOP_TUNNEL
));
1881 purpose_to_search_for
= get_circuit_purpose_needed_to_cannibalize(
1882 purpose_to_produce
);
1884 tor_assert_nonfatal(purpose_to_search_for
== CIRCUIT_PURPOSE_C_GENERAL
||
1885 purpose_to_search_for
== CIRCUIT_PURPOSE_HS_VANGUARDS
);
1888 "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
1889 "capacity %d, internal %d",
1890 purpose_to_produce
, need_uptime
, need_capacity
, internal
);
1892 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ_
) {
1893 if (CIRCUIT_IS_ORIGIN(circ_
) &&
1894 circ_
->state
== CIRCUIT_STATE_OPEN
&&
1895 !circ_
->marked_for_close
&&
1896 circ_
->purpose
== purpose_to_search_for
&&
1897 !circ_
->timestamp_dirty
) {
1898 origin_circuit_t
*circ
= TO_ORIGIN_CIRCUIT(circ_
);
1900 /* Only cannibalize from reasonable length circuits. If we
1901 * want C_GENERAL, then only choose 3 hop circs. If we want
1902 * HS_VANGUARDS, only choose 4 hop circs.
1904 if (circ
->build_state
->desired_path_len
!=
1905 route_len_for_purpose(purpose_to_search_for
, NULL
)) {
1909 /* Ignore any circuits for which we can't use the Guard. It is possible
1910 * that the Guard was removed from the sampled set after the circuit
1911 * was created, so avoid using it. */
1912 if (!entry_guard_could_succeed(circ
->guard_state
)) {
1916 if ((!need_uptime
|| circ
->build_state
->need_uptime
) &&
1917 (!need_capacity
|| circ
->build_state
->need_capacity
) &&
1918 (internal
== circ
->build_state
->is_internal
) &&
1919 !circ
->unusable_for_new_conns
&&
1920 circ
->remaining_relay_early_cells
&&
1921 !circ
->build_state
->onehop_tunnel
&&
1922 !circ
->isolation_values_set
) {
1924 /* need to make sure we don't duplicate hops */
1925 crypt_path_t
*hop
= circ
->cpath
;
1926 const node_t
*ri1
= node_get_by_id(info
->identity_digest
);
1929 if (tor_memeq(hop
->extend_info
->identity_digest
,
1930 info
->identity_digest
, DIGEST_LEN
))
1933 (ri2
= node_get_by_id(hop
->extend_info
->identity_digest
))
1934 && nodes_in_same_family(ri1
, ri2
))
1937 } while (hop
!=circ
->cpath
);
1939 if (options
->ExcludeNodes
) {
1940 /* Make sure no existing nodes in the circuit are excluded for
1941 * general use. (This may be possible if StrictNodes is 0, and we
1942 * thought we needed to use an otherwise excluded node for, say, a
1943 * directory operation.) */
1944 crypt_path_t
*hop
= circ
->cpath
;
1946 if (routerset_contains_extendinfo(options
->ExcludeNodes
,
1950 } while (hop
!= circ
->cpath
);
1953 if ((flags
& CIRCLAUNCH_IS_V3_RP
) &&
1954 !circuit_can_be_cannibalized_for_v3_rp(circ
)) {
1955 log_debug(LD_GENERAL
, "Skipping uncannibalizable circuit for v3 "
1956 "rendezvous point.");
1960 if (!best
|| (best
->build_state
->need_uptime
&& !need_uptime
))
1966 SMARTLIST_FOREACH_END(circ_
);
1971 * Check whether any of the origin circuits that are waiting to see if
1972 * their guard is good enough to use can be upgraded to "ready". If so,
1973 * return a new smartlist containing them. Otherwise return NULL.
1976 circuit_find_circuits_to_upgrade_from_guard_wait(void)
1978 /* Only if some circuit is actually waiting on an upgrade should we
1979 * run the algorithm. */
1980 if (! circuits_pending_other_guards
||
1981 smartlist_len(circuits_pending_other_guards
)==0)
1983 /* Only if we have some origin circuits should we run the algorithm. */
1984 if (!global_origin_circuit_list
)
1987 /* Okay; we can pass our circuit list to entrynodes.c.*/
1988 smartlist_t
*result
= smartlist_new();
1989 int circuits_upgraded
= entry_guards_upgrade_waiting_circuits(
1990 get_guard_selection_info(),
1991 global_origin_circuit_list
,
1993 if (circuits_upgraded
&& smartlist_len(result
)) {
1996 smartlist_free(result
);
2001 /** Return the number of hops in circuit's path. If circ has no entries,
2002 * or is NULL, returns 0. */
2004 circuit_get_cpath_len(origin_circuit_t
*circ
)
2007 if (circ
&& circ
->cpath
) {
2008 crypt_path_t
*cpath
, *cpath_next
= NULL
;
2009 for (cpath
= circ
->cpath
; cpath_next
!= circ
->cpath
; cpath
= cpath_next
) {
2010 cpath_next
= cpath
->next
;
2017 /** Return the number of opened hops in circuit's path.
2018 * If circ has no entries, or is NULL, returns 0. */
2020 circuit_get_cpath_opened_len(const origin_circuit_t
*circ
)
2023 if (circ
&& circ
->cpath
) {
2024 crypt_path_t
*cpath
, *cpath_next
= NULL
;
2025 for (cpath
= circ
->cpath
;
2026 cpath
->state
== CPATH_STATE_OPEN
2027 && cpath_next
!= circ
->cpath
;
2028 cpath
= cpath_next
) {
2029 cpath_next
= cpath
->next
;
2036 /** Return the <b>hopnum</b>th hop in <b>circ</b>->cpath, or NULL if there
2037 * aren't that many hops in the list. <b>hopnum</b> starts at 1.
2038 * Returns NULL if <b>hopnum</b> is 0 or negative. */
2040 circuit_get_cpath_hop(origin_circuit_t
*circ
, int hopnum
)
2042 if (circ
&& circ
->cpath
&& hopnum
> 0) {
2043 crypt_path_t
*cpath
, *cpath_next
= NULL
;
2044 for (cpath
= circ
->cpath
; cpath_next
!= circ
->cpath
; cpath
= cpath_next
) {
2045 cpath_next
= cpath
->next
;
2053 /** Go through the circuitlist; mark-for-close each circuit that starts
2054 * at us but has not yet been used. */
2056 circuit_mark_all_unused_circs(void)
2058 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
2059 if (CIRCUIT_IS_ORIGIN(circ
) &&
2060 !circ
->marked_for_close
&&
2061 !circ
->timestamp_dirty
)
2062 circuit_mark_for_close(circ
, END_CIRC_REASON_FINISHED
);
2064 SMARTLIST_FOREACH_END(circ
);
2067 /** Go through the circuitlist; for each circuit that starts at us
2068 * and is dirty, frob its timestamp_dirty so we won't use it for any
2071 * This is useful for letting the user change pseudonyms, so new
2072 * streams will not be linkable to old streams.
2075 circuit_mark_all_dirty_circs_as_unusable(void)
2077 SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t
*, circ
) {
2078 if (CIRCUIT_IS_ORIGIN(circ
) &&
2079 !circ
->marked_for_close
&&
2080 circ
->timestamp_dirty
) {
2081 mark_circuit_unusable_for_new_conns(TO_ORIGIN_CIRCUIT(circ
));
2084 SMARTLIST_FOREACH_END(circ
);
2088 * Report any queued cells on or_circuits as written in our bandwidth
2089 * totals, for the specified channel direction.
2091 * When we close a circuit or clear its cell queues, we've read
2092 * data and recorded those bytes in our read statistics, but we're
2093 * not going to write it. This discrepancy can be used by an adversary
2094 * to infer information from our public relay statistics and perform
2095 * attacks such as guard discovery.
2097 * This function is in the critical path of circuit_mark_for_close().
2098 * It must be (and is) O(1)!
2100 * See https://bugs.torproject.org/tpo/core/tor/23512
2103 circuit_synchronize_written_or_bandwidth(const circuit_t
*c
,
2104 circuit_channel_direction_t dir
)
2108 uint64_t written_sync
;
2109 const channel_t
*chan
= NULL
;
2110 const or_circuit_t
*or_circ
;
2112 if (!CIRCUIT_IS_ORCIRC(c
))
2115 or_circ
= CONST_TO_OR_CIRCUIT(c
);
2117 if (dir
== CIRCUIT_N_CHAN
) {
2119 cells
= c
->n_chan_cells
.n
;
2121 chan
= or_circ
->p_chan
;
2122 cells
= or_circ
->p_chan_cells
.n
;
2125 /* If we still know the chan, determine real cell size. Otherwise,
2126 * assume it's a wide circid channel */
2128 cell_size
= get_cell_network_size(chan
->wide_circ_ids
);
2130 cell_size
= CELL_MAX_NETWORK_SIZE
;
2132 /* If we know the channel, find out if it's IPv6. */
2133 tor_addr_t remote_addr
;
2134 bool is_ipv6
= chan
&&
2135 channel_get_addr_if_possible(chan
, &remote_addr
) &&
2136 tor_addr_family(&remote_addr
) == AF_INET6
;
2138 /* The missing written bytes are the cell counts times their cell
2139 * size plus TLS per cell overhead */
2140 written_sync
= cells
*(cell_size
+TLS_PER_CELL_OVERHEAD
);
2142 /* Report the missing bytes as written, to avoid asymmetry.
2143 * We must use time() for consistency with rephist, even though on
2144 * some very old rare platforms, approx_time() may be faster. */
2145 bwhist_note_bytes_written(written_sync
, time(NULL
), is_ipv6
);
2148 /** Mark <b>circ</b> to be closed next time we call
2149 * circuit_close_all_marked(). Do any cleanup needed:
2150 * - If state is onionskin_pending, remove circ from the onion_pending
2152 * - If circ isn't open yet: call circuit_build_failed() if we're
2154 * - If purpose is C_INTRODUCE_ACK_WAIT, report the intro point
2155 * failure we just had to the hidden service client module.
2156 * - If purpose is C_INTRODUCING and <b>reason</b> isn't TIMEOUT,
2157 * report to the hidden service client module that the intro point
2158 * we just tried may be unreachable.
2159 * - Send appropriate destroys and edge_destroys for conns and
2160 * streams attached to circ.
2161 * - If circ->rend_splice is set (we are the midpoint of a joined
2162 * rendezvous stream), then mark the other circuit to close as well.
2165 circuit_mark_for_close_
, (circuit_t
*circ
, int reason
, int line
,
2168 int orig_reason
= reason
; /* Passed to the controller */
2169 assert_circuit_ok(circ
);
2173 /* Check whether the circuitpadding subsystem wants to block this close */
2174 if (circpad_marked_circuit_for_padding(circ
, reason
)) {
2178 if (circ
->marked_for_close
) {
2180 "Duplicate call to circuit_mark_for_close at %s:%d"
2181 " (first at %s:%d)", file
, line
,
2182 circ
->marked_for_close_file
, circ
->marked_for_close
);
2185 if (reason
== END_CIRC_AT_ORIGIN
) {
2186 if (!CIRCUIT_IS_ORIGIN(circ
)) {
2187 log_warn(LD_BUG
, "Specified 'at-origin' non-reason for ending circuit, "
2188 "but circuit was not at origin. (called %s:%d, purpose=%d)",
2189 file
, line
, circ
->purpose
);
2191 reason
= END_CIRC_REASON_NONE
;
2194 if (CIRCUIT_IS_ORIGIN(circ
)) {
2195 if (pathbias_check_close(TO_ORIGIN_CIRCUIT(circ
), reason
) == -1) {
2196 /* Don't close it yet, we need to test it first */
2200 /* We don't send reasons when closing circuits at the origin. */
2201 reason
= END_CIRC_REASON_NONE
;
2204 circuit_synchronize_written_or_bandwidth(circ
, CIRCUIT_N_CHAN
);
2205 circuit_synchronize_written_or_bandwidth(circ
, CIRCUIT_P_CHAN
);
2207 if (reason
& END_CIRC_REASON_FLAG_REMOTE
)
2208 reason
&= ~END_CIRC_REASON_FLAG_REMOTE
;
2210 if (reason
< END_CIRC_REASON_MIN_
|| reason
> END_CIRC_REASON_MAX_
) {
2211 if (!(orig_reason
& END_CIRC_REASON_FLAG_REMOTE
))
2212 log_warn(LD_BUG
, "Reason %d out of range at %s:%d", reason
, file
, line
);
2213 reason
= END_CIRC_REASON_NONE
;
2216 circ
->marked_for_close
= line
;
2217 circ
->marked_for_close_file
= file
;
2218 circ
->marked_for_close_reason
= reason
;
2219 circ
->marked_for_close_orig_reason
= orig_reason
;
2221 if (!CIRCUIT_IS_ORIGIN(circ
)) {
2222 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
2223 if (or_circ
->rend_splice
) {
2224 if (!or_circ
->rend_splice
->base_
.marked_for_close
) {
2225 /* do this after marking this circuit, to avoid infinite recursion. */
2226 circuit_mark_for_close(TO_CIRCUIT(or_circ
->rend_splice
), reason
);
2228 or_circ
->rend_splice
= NULL
;
2232 /* Notify the HS subsystem that this circuit is closing. */
2233 hs_circ_cleanup_on_close(circ
);
2236 if (circ
->ccontrol
) {
2237 if (circ
->ccontrol
->in_slow_start
) {
2238 /* If we are in slow start, only count the ss cwnd if we've sent
2239 * enough data to get RTT measurements such that we have a min
2240 * and a max RTT, and they are not the same. This prevents us from
2241 * averaging and reporting unused and low-use circuits here */
2242 if (circ
->ccontrol
->max_rtt_usec
!= circ
->ccontrol
->min_rtt_usec
) {
2243 cc_stats_circ_close_ss_cwnd_ma
=
2244 stats_update_running_avg(cc_stats_circ_close_ss_cwnd_ma
,
2245 circ
->ccontrol
->cwnd
);
2248 cc_stats_circ_close_cwnd_ma
=
2249 stats_update_running_avg(cc_stats_circ_close_cwnd_ma
,
2250 circ
->ccontrol
->cwnd
);
2254 if (circuits_pending_close
== NULL
)
2255 circuits_pending_close
= smartlist_new();
2257 smartlist_add(circuits_pending_close
, circ
);
2258 mainloop_schedule_postloop_cleanup();
2260 log_info(LD_GENERAL
, "Circuit %u (id: %" PRIu32
") marked for close at "
2261 "%s:%d (orig reason: %d, new reason: %d)",
2263 CIRCUIT_IS_ORIGIN(circ
) ?
2264 TO_ORIGIN_CIRCUIT(circ
)->global_identifier
: 0,
2265 file
, line
, orig_reason
, reason
);
2266 tor_trace(TR_SUBSYS(circuit
), TR_EV(mark_for_close
), circ
);
2269 /** Called immediately before freeing a marked circuit <b>circ</b> from
2270 * circuit_free_all() while shutting down Tor; this is a safe-at-shutdown
2271 * version of circuit_about_to_free(). It's important that it at least
2272 * do circuitmux_detach_circuit() when appropriate.
2275 circuit_about_to_free_atexit(circuit_t
*circ
)
2279 circuit_clear_cell_queue(circ
, circ
->n_chan
);
2280 circuitmux_detach_circuit(circ
->n_chan
->cmux
, circ
);
2281 circuit_set_n_circid_chan(circ
, 0, NULL
);
2284 if (! CIRCUIT_IS_ORIGIN(circ
)) {
2285 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
2287 if (or_circ
->p_chan
) {
2288 circuit_clear_cell_queue(circ
, or_circ
->p_chan
);
2289 circuitmux_detach_circuit(or_circ
->p_chan
->cmux
, circ
);
2290 circuit_set_p_circid_chan(or_circ
, 0, NULL
);
2295 /** Called immediately before freeing a marked circuit <b>circ</b>.
2296 * Disconnects the circuit from other data structures, launches events
2297 * as appropriate, and performs other housekeeping.
2300 circuit_about_to_free(circuit_t
*circ
)
2303 int reason
= circ
->marked_for_close_reason
;
2304 int orig_reason
= circ
->marked_for_close_orig_reason
;
2306 if (circ
->state
== CIRCUIT_STATE_ONIONSKIN_PENDING
) {
2307 onion_pending_remove(TO_OR_CIRCUIT(circ
));
2309 /* If the circuit ever became OPEN, we sent it to the reputation history
2310 * module then. If it isn't OPEN, we send it there now to remember which
2311 * links worked and which didn't.
2313 if (circ
->state
!= CIRCUIT_STATE_OPEN
&&
2314 circ
->state
!= CIRCUIT_STATE_GUARD_WAIT
) {
2315 if (CIRCUIT_IS_ORIGIN(circ
)) {
2316 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
2317 circuit_build_failed(ocirc
); /* take actions if necessary */
2320 if (circ
->state
== CIRCUIT_STATE_CHAN_WAIT
) {
2321 if (circuits_pending_chans
)
2322 smartlist_remove(circuits_pending_chans
, circ
);
2324 if (circuits_pending_other_guards
) {
2325 smartlist_remove(circuits_pending_other_guards
, circ
);
2327 if (CIRCUIT_IS_ORIGIN(circ
)) {
2328 circuit_event_status(TO_ORIGIN_CIRCUIT(circ
),
2329 (circ
->state
== CIRCUIT_STATE_OPEN
||
2330 circ
->state
== CIRCUIT_STATE_GUARD_WAIT
) ?
2331 CIRC_EVENT_CLOSED
:CIRC_EVENT_FAILED
,
2336 circuit_clear_cell_queue(circ
, circ
->n_chan
);
2337 /* Only send destroy if the channel isn't closing anyway */
2338 if (!CHANNEL_CONDEMNED(circ
->n_chan
)) {
2339 channel_send_destroy(circ
->n_circ_id
, circ
->n_chan
, reason
);
2341 circuitmux_detach_circuit(circ
->n_chan
->cmux
, circ
);
2342 circuit_set_n_circid_chan(circ
, 0, NULL
);
2345 if (! CIRCUIT_IS_ORIGIN(circ
)) {
2346 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
2347 edge_connection_t
*conn
;
2348 for (conn
=or_circ
->n_streams
; conn
; conn
=conn
->next_stream
)
2349 connection_edge_destroy(or_circ
->p_circ_id
, conn
);
2350 or_circ
->n_streams
= NULL
;
2352 while (or_circ
->resolving_streams
) {
2353 conn
= or_circ
->resolving_streams
;
2354 or_circ
->resolving_streams
= conn
->next_stream
;
2355 if (!conn
->base_
.marked_for_close
) {
2356 /* The client will see a DESTROY, and infer that the connections
2357 * are closing because the circuit is getting torn down. No need
2358 * to send an end cell. */
2359 conn
->edge_has_sent_end
= 1;
2360 conn
->end_reason
= END_STREAM_REASON_DESTROY
;
2361 conn
->end_reason
|= END_STREAM_REASON_FLAG_ALREADY_SENT_CLOSED
;
2362 connection_mark_for_close(TO_CONN(conn
));
2364 conn
->on_circuit
= NULL
;
2367 if (or_circ
->p_chan
) {
2368 circuit_clear_cell_queue(circ
, or_circ
->p_chan
);
2369 /* Only send destroy if the channel isn't closing anyway */
2370 if (!CHANNEL_CONDEMNED(or_circ
->p_chan
)) {
2371 channel_send_destroy(or_circ
->p_circ_id
, or_circ
->p_chan
, reason
);
2373 circuitmux_detach_circuit(or_circ
->p_chan
->cmux
, circ
);
2374 circuit_set_p_circid_chan(or_circ
, 0, NULL
);
2377 if (or_circ
->n_cells_discarded_at_end
) {
2378 time_t age
= approx_time() - circ
->timestamp_created
.tv_sec
;
2379 note_circ_closed_for_unrecognized_cells(
2380 age
, or_circ
->n_cells_discarded_at_end
);
2383 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
2384 edge_connection_t
*conn
;
2385 for (conn
=ocirc
->p_streams
; conn
; conn
=conn
->next_stream
)
2386 connection_edge_destroy(circ
->n_circ_id
, conn
);
2387 ocirc
->p_streams
= NULL
;
2391 /** Given a marked circuit <b>circ</b>, aggressively free its cell queues to
2392 * recover memory. */
2394 marked_circuit_free_cells(circuit_t
*circ
)
2396 if (!circ
->marked_for_close
) {
2397 log_warn(LD_BUG
, "Called on non-marked circuit");
2400 cell_queue_clear(&circ
->n_chan_cells
);
2401 if (! CIRCUIT_IS_ORIGIN(circ
)) {
2402 or_circuit_t
*orcirc
= TO_OR_CIRCUIT(circ
);
2403 cell_queue_clear(&orcirc
->p_chan_cells
);
2408 single_conn_free_bytes(connection_t
*conn
)
2412 result
+= buf_allocation(conn
->inbuf
);
2413 buf_clear(conn
->inbuf
);
2416 result
+= buf_allocation(conn
->outbuf
);
2417 buf_clear(conn
->outbuf
);
2419 if (conn
->type
== CONN_TYPE_DIR
) {
2420 dir_connection_t
*dir_conn
= TO_DIR_CONN(conn
);
2421 if (dir_conn
->compress_state
) {
2422 result
+= tor_compress_state_size(dir_conn
->compress_state
);
2423 tor_compress_free(dir_conn
->compress_state
);
2424 dir_conn
->compress_state
= NULL
;
2430 /** Aggressively free buffer contents on all the buffers of all streams in the
2431 * list starting at <b>stream</b>. Return the number of bytes recovered. */
2433 marked_circuit_streams_free_bytes(edge_connection_t
*stream
)
2436 for ( ; stream
; stream
= stream
->next_stream
) {
2437 connection_t
*conn
= TO_CONN(stream
);
2438 result
+= single_conn_free_bytes(conn
);
2439 if (conn
->linked_conn
) {
2440 result
+= single_conn_free_bytes(conn
->linked_conn
);
2446 /** Aggressively free buffer contents on all the buffers of all streams on
2447 * circuit <b>c</b>. Return the number of bytes recovered. */
2449 marked_circuit_free_stream_bytes(circuit_t
*c
)
2451 if (CIRCUIT_IS_ORIGIN(c
)) {
2452 return marked_circuit_streams_free_bytes(TO_ORIGIN_CIRCUIT(c
)->p_streams
);
2454 return marked_circuit_streams_free_bytes(TO_OR_CIRCUIT(c
)->n_streams
);
2458 /** Return the number of cells used by the circuit <b>c</b>'s cell queues. */
2460 n_cells_in_circ_queues(const circuit_t
*c
)
2462 size_t n
= c
->n_chan_cells
.n
;
2463 if (! CIRCUIT_IS_ORIGIN(c
)) {
2464 circuit_t
*cc
= (circuit_t
*) c
;
2465 n
+= TO_OR_CIRCUIT(cc
)->p_chan_cells
.n
;
2470 /** Return the number of bytes allocated for <b>c</b>'s half-open streams. */
2472 circuit_alloc_in_half_streams(const circuit_t
*c
)
2474 if (! CIRCUIT_IS_ORIGIN(c
)) {
2477 const origin_circuit_t
*ocirc
= CONST_TO_ORIGIN_CIRCUIT(c
);
2478 if (ocirc
->half_streams
)
2479 return smartlist_len(ocirc
->half_streams
) * sizeof(half_edge_t
);
2485 * Return the age of the oldest cell queued on <b>c</b>, in timestamp units.
2486 * Return 0 if there are no cells queued on c. Requires that <b>now</b> be
2487 * the current coarse timestamp.
2489 * This function will return incorrect results if the oldest cell queued on
2490 * the circuit is older than about 2**32 msec (about 49 days) old.
2493 circuit_max_queued_cell_age(const circuit_t
*c
, uint32_t now
)
2496 packed_cell_t
*cell
;
2498 if (NULL
!= (cell
= TOR_SIMPLEQ_FIRST(&c
->n_chan_cells
.head
)))
2499 age
= now
- cell
->inserted_timestamp
;
2501 if (! CIRCUIT_IS_ORIGIN(c
)) {
2502 const or_circuit_t
*orcirc
= CONST_TO_OR_CIRCUIT(c
);
2503 if (NULL
!= (cell
= TOR_SIMPLEQ_FIRST(&orcirc
->p_chan_cells
.head
))) {
2504 uint32_t age2
= now
- cell
->inserted_timestamp
;
2512 /** Return the age of the oldest buffer chunk on <b>conn</b>, where age is
2513 * taken in timestamp units before the time <b>now</b>. If the connection has
2514 * no data, treat it as having age zero.
2517 conn_get_buffer_age(const connection_t
*conn
, uint32_t now_ts
)
2519 uint32_t age
= 0, age2
;
2521 age2
= buf_get_oldest_chunk_timestamp(conn
->outbuf
, now_ts
);
2526 age2
= buf_get_oldest_chunk_timestamp(conn
->inbuf
, now_ts
);
2533 /** Return the age in timestamp units of the oldest buffer chunk on any stream
2534 * in the linked list <b>stream</b>, where age is taken in timestamp units
2535 * before the timestamp <b>now</b>. */
2537 circuit_get_streams_max_data_age(const edge_connection_t
*stream
, uint32_t now
)
2539 uint32_t age
= 0, age2
;
2540 for (; stream
; stream
= stream
->next_stream
) {
2541 const connection_t
*conn
= TO_CONN(stream
);
2542 age2
= conn_get_buffer_age(conn
, now
);
2545 if (conn
->linked_conn
) {
2546 age2
= conn_get_buffer_age(conn
->linked_conn
, now
);
2554 /** Return the age in timestamp units of the oldest buffer chunk on any stream
2555 * attached to the circuit <b>c</b>, where age is taken before the timestamp
2558 circuit_max_queued_data_age(const circuit_t
*c
, uint32_t now
)
2560 if (CIRCUIT_IS_ORIGIN(c
)) {
2561 return circuit_get_streams_max_data_age(
2562 CONST_TO_ORIGIN_CIRCUIT(c
)->p_streams
, now
);
2564 return circuit_get_streams_max_data_age(
2565 CONST_TO_OR_CIRCUIT(c
)->n_streams
, now
);
2569 /** Return the age of the oldest cell or stream buffer chunk on the circuit
2570 * <b>c</b>, where age is taken in timestamp units before the timestamp
2573 circuit_max_queued_item_age(const circuit_t
*c
, uint32_t now
)
2575 uint32_t cell_age
= circuit_max_queued_cell_age(c
, now
);
2576 uint32_t data_age
= circuit_max_queued_data_age(c
, now
);
2577 if (cell_age
> data_age
)
2583 /** Helper to sort a list of circuit_t by age of oldest item, in descending
2586 circuits_compare_by_oldest_queued_item_(const void **a_
, const void **b_
)
2588 const circuit_t
*a
= *a_
;
2589 const circuit_t
*b
= *b_
;
2590 uint32_t age_a
= a
->age_tmp
;
2591 uint32_t age_b
= b
->age_tmp
;
2595 else if (age_a
== age_b
)
2601 static uint32_t now_ts_for_buf_cmp
;
2603 /** Helper to sort a list of circuit_t by age of oldest item, in descending
2606 conns_compare_by_buffer_age_(const void **a_
, const void **b_
)
2608 const connection_t
*a
= *a_
;
2609 const connection_t
*b
= *b_
;
2610 time_t age_a
= conn_get_buffer_age(a
, now_ts_for_buf_cmp
);
2611 time_t age_b
= conn_get_buffer_age(b
, now_ts_for_buf_cmp
);
2615 else if (age_a
== age_b
)
2621 #define FRACTION_OF_DATA_TO_RETAIN_ON_OOM 0.90
2623 /** We're out of memory for cells, having allocated <b>current_allocation</b>
2624 * bytes' worth. Kill the 'worst' circuits until we're under
2625 * FRACTION_OF_DATA_TO_RETAIN_ON_OOM of our maximum usage.
2627 * Return the number of bytes removed. */
2629 circuits_handle_oom(size_t current_allocation
)
2631 smartlist_t
*circlist
;
2632 smartlist_t
*connection_array
= get_connection_array();
2634 size_t mem_to_recover
;
2635 size_t mem_recovered
=0;
2636 int n_circuits_killed
=0;
2637 int n_dirconns_killed
=0;
2638 int n_edgeconns_killed
= 0;
2640 log_notice(LD_GENERAL
, "We're low on memory (cell queues total alloc:"
2641 " %"TOR_PRIuSZ
" buffer total alloc: %" TOR_PRIuSZ
","
2642 " tor compress total alloc: %" TOR_PRIuSZ
2643 " (zlib: %" TOR_PRIuSZ
", zstd: %" TOR_PRIuSZ
","
2644 " lzma: %" TOR_PRIuSZ
"),"
2645 " rendezvous cache total alloc: %" TOR_PRIuSZ
"). Killing"
2646 " circuits withover-long queues. (This behavior is controlled by"
2647 " MaxMemInQueues.)",
2648 cell_queues_get_total_allocation(),
2649 buf_get_total_allocation(),
2650 tor_compress_get_total_allocation(),
2651 tor_zlib_get_total_allocation(),
2652 tor_zstd_get_total_allocation(),
2653 tor_lzma_get_total_allocation(),
2654 hs_cache_get_total_allocation());
2656 size_t mem_target
= (size_t)(get_options()->MaxMemInQueues
*
2657 FRACTION_OF_DATA_TO_RETAIN_ON_OOM
);
2658 if (current_allocation
<= mem_target
)
2660 mem_to_recover
= current_allocation
- mem_target
;
2663 now_ts
= monotime_coarse_get_stamp();
2665 circlist
= circuit_get_global_list();
2666 SMARTLIST_FOREACH_BEGIN(circlist
, circuit_t
*, circ
) {
2667 circ
->age_tmp
= circuit_max_queued_item_age(circ
, now_ts
);
2668 } SMARTLIST_FOREACH_END(circ
);
2670 /* This is O(n log n); there are faster algorithms we could use instead.
2671 * Let's hope this doesn't happen enough to be in the critical path. */
2672 smartlist_sort(circlist
, circuits_compare_by_oldest_queued_item_
);
2674 /* Fix up the indices before we run into trouble */
2675 SMARTLIST_FOREACH_BEGIN(circlist
, circuit_t
*, circ
) {
2676 circ
->global_circuitlist_idx
= circ_sl_idx
;
2677 } SMARTLIST_FOREACH_END(circ
);
2679 /* Now sort the connection array ... */
2680 now_ts_for_buf_cmp
= now_ts
;
2681 smartlist_sort(connection_array
, conns_compare_by_buffer_age_
);
2682 now_ts_for_buf_cmp
= 0;
2684 /* Fix up the connection array to its new order. */
2685 SMARTLIST_FOREACH_BEGIN(connection_array
, connection_t
*, conn
) {
2686 conn
->conn_array_index
= conn_sl_idx
;
2687 } SMARTLIST_FOREACH_END(conn
);
2689 /* Okay, now the worst circuits and connections are at the front of their
2690 * respective lists. Let's mark them, and reclaim their storage
2693 SMARTLIST_FOREACH_BEGIN(circlist
, circuit_t
*, circ
) {
2697 /* Free storage in any non-linked directory connections that have buffered
2698 * data older than this circuit. */
2699 while (conn_idx
< smartlist_len(connection_array
)) {
2700 connection_t
*conn
= smartlist_get(connection_array
, conn_idx
);
2701 uint32_t conn_age
= conn_get_buffer_age(conn
, now_ts
);
2702 if (conn_age
< circ
->age_tmp
) {
2705 /* Also consider edge connections so we don't accumulate bytes on the
2706 * outbuf due to a malicious destination holding off the read on us. */
2707 if ((conn
->type
== CONN_TYPE_DIR
&& conn
->linked_conn
== NULL
) ||
2708 CONN_IS_EDGE(conn
)) {
2709 if (!conn
->marked_for_close
)
2710 connection_mark_for_close(conn
);
2711 mem_recovered
+= single_conn_free_bytes(conn
);
2713 if (conn
->type
== CONN_TYPE_DIR
) {
2714 ++n_dirconns_killed
;
2716 ++n_edgeconns_killed
;
2719 if (mem_recovered
>= mem_to_recover
)
2720 goto done_recovering_mem
;
2725 /* Now, kill the circuit. */
2726 n
= n_cells_in_circ_queues(circ
);
2727 const size_t half_stream_alloc
= circuit_alloc_in_half_streams(circ
);
2728 if (! circ
->marked_for_close
) {
2729 circuit_mark_for_close(circ
, END_CIRC_REASON_RESOURCELIMIT
);
2731 marked_circuit_free_cells(circ
);
2732 freed
= marked_circuit_free_stream_bytes(circ
);
2734 ++n_circuits_killed
;
2736 mem_recovered
+= n
* packed_cell_mem_cost();
2737 mem_recovered
+= half_stream_alloc
;
2738 mem_recovered
+= freed
;
2740 if (mem_recovered
>= mem_to_recover
)
2741 goto done_recovering_mem
;
2742 } SMARTLIST_FOREACH_END(circ
);
2744 done_recovering_mem
:
2745 log_notice(LD_GENERAL
, "Removed %"TOR_PRIuSZ
" bytes by killing %d circuits; "
2746 "%d circuits remain alive. Also killed %d non-linked directory "
2747 "connections. Killed %d edge connections",
2750 smartlist_len(circlist
) - n_circuits_killed
,
2752 n_edgeconns_killed
);
2754 return mem_recovered
;
2757 /** Verify that circuit <b>c</b> has all of its invariants
2758 * correct. Trigger an assert if anything is invalid.
2761 assert_circuit_ok
,(const circuit_t
*c
))
2763 edge_connection_t
*conn
;
2764 const or_circuit_t
*or_circ
= NULL
;
2765 const origin_circuit_t
*origin_circ
= NULL
;
2768 tor_assert(c
->magic
== ORIGIN_CIRCUIT_MAGIC
|| c
->magic
== OR_CIRCUIT_MAGIC
);
2769 tor_assert(c
->purpose
>= CIRCUIT_PURPOSE_MIN_
&&
2770 c
->purpose
<= CIRCUIT_PURPOSE_MAX_
);
2772 if (CIRCUIT_IS_ORIGIN(c
))
2773 origin_circ
= CONST_TO_ORIGIN_CIRCUIT(c
);
2775 or_circ
= CONST_TO_OR_CIRCUIT(c
);
2778 tor_assert(!c
->n_hop
);
2781 /* We use the _impl variant here to make sure we don't fail on marked
2782 * circuits, which would not be returned by the regular function. */
2783 circuit_t
*c2
= circuit_get_by_circid_channel_impl(c
->n_circ_id
,
2785 tor_assert(c
== c2
);
2788 if (or_circ
&& or_circ
->p_chan
) {
2789 if (or_circ
->p_circ_id
) {
2792 circuit_get_by_circid_channel_impl(or_circ
->p_circ_id
,
2793 or_circ
->p_chan
, NULL
);
2794 tor_assert(c
== c2
);
2798 for (conn
= or_circ
->n_streams
; conn
; conn
= conn
->next_stream
)
2799 tor_assert(conn
->base_
.type
== CONN_TYPE_EXIT
);
2801 tor_assert(c
->deliver_window
>= 0);
2802 tor_assert(c
->package_window
>= 0);
2803 if (c
->state
== CIRCUIT_STATE_OPEN
||
2804 c
->state
== CIRCUIT_STATE_GUARD_WAIT
) {
2805 tor_assert(!c
->n_chan_create_cell
);
2807 relay_crypto_assert_ok(&or_circ
->crypto
);
2810 if (c
->state
== CIRCUIT_STATE_CHAN_WAIT
&& !c
->marked_for_close
) {
2811 tor_assert(circuits_pending_chans
&&
2812 smartlist_contains(circuits_pending_chans
, c
));
2814 tor_assert(!circuits_pending_chans
||
2815 !smartlist_contains(circuits_pending_chans
, c
));
2817 if (origin_circ
&& origin_circ
->cpath
) {
2818 cpath_assert_ok(origin_circ
->cpath
);
2820 if (c
->purpose
== CIRCUIT_PURPOSE_REND_ESTABLISHED
) {
2821 tor_assert(or_circ
);
2822 if (!c
->marked_for_close
) {
2823 tor_assert(or_circ
->rend_splice
);
2824 tor_assert(or_circ
->rend_splice
->rend_splice
== or_circ
);
2826 tor_assert(or_circ
->rend_splice
!= or_circ
);
2828 tor_assert(!or_circ
|| !or_circ
->rend_splice
);