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-2010, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
9 * \brief Manage the global circuit list.
13 #include "circuitbuild.h"
14 #include "circuitlist.h"
15 #include "circuituse.h"
16 #include "connection.h"
18 #include "connection_edge.h"
19 #include "connection_or.h"
21 #include "rendclient.h"
22 #include "rendcommon.h"
23 #include "routerlist.h"
26 /********* START VARIABLES **********/
28 /** A global list of all circuits at this hop. */
29 circuit_t
*global_circuitlist
=NULL
;
31 /** A list of all the circuits in CIRCUIT_STATE_OR_WAIT. */
32 static smartlist_t
*circuits_pending_or_conns
=NULL
;
34 static void circuit_free(circuit_t
*circ
);
35 static void circuit_free_cpath(crypt_path_t
*cpath
);
36 static void circuit_free_cpath_node(crypt_path_t
*victim
);
38 /********* END VARIABLES ************/
40 /** A map from OR connection and circuit ID to circuit. (Lookup performance is
41 * very important here, since we need to do it every time a cell arrives.) */
42 typedef struct orconn_circid_circuit_map_t
{
43 HT_ENTRY(orconn_circid_circuit_map_t
) node
;
44 or_connection_t
*or_conn
;
47 } orconn_circid_circuit_map_t
;
49 /** Helper for hash tables: compare the OR connection and circuit ID for a and
50 * b, and return less than, equal to, or greater than zero appropriately.
53 _orconn_circid_entries_eq(orconn_circid_circuit_map_t
*a
,
54 orconn_circid_circuit_map_t
*b
)
56 return a
->or_conn
== b
->or_conn
&& a
->circ_id
== b
->circ_id
;
59 /** Helper: return a hash based on circuit ID and the pointer value of
60 * or_conn in <b>a</b>. */
61 static INLINE
unsigned int
62 _orconn_circid_entry_hash(orconn_circid_circuit_map_t
*a
)
64 return (((unsigned)a
->circ_id
)<<8) ^ (unsigned)(uintptr_t)(a
->or_conn
);
67 /** Map from [orconn,circid] to circuit. */
68 static HT_HEAD(orconn_circid_map
, orconn_circid_circuit_map_t
)
69 orconn_circid_circuit_map
= HT_INITIALIZER();
70 HT_PROTOTYPE(orconn_circid_map
, orconn_circid_circuit_map_t
, node
,
71 _orconn_circid_entry_hash
, _orconn_circid_entries_eq
)
72 HT_GENERATE(orconn_circid_map
, orconn_circid_circuit_map_t
, node
,
73 _orconn_circid_entry_hash
, _orconn_circid_entries_eq
, 0.6,
74 malloc
, realloc
, free
)
76 /** The most recently returned entry from circuit_get_by_circid_orconn;
77 * used to improve performance when many cells arrive in a row from the
80 orconn_circid_circuit_map_t
*_last_circid_orconn_ent
= NULL
;
82 /** Implementation helper for circuit_set_{p,n}_circid_orconn: A circuit ID
83 * and/or or_connection for circ has just changed from <b>old_conn, old_id</b>
84 * to <b>conn, id</b>. Adjust the conn,circid map as appropriate, removing
85 * the old entry (if any) and adding a new one. If <b>active</b> is true,
86 * remove the circuit from the list of active circuits on old_conn and add it
87 * to the list of active circuits on conn.
88 * XXX "active" isn't an arg anymore */
90 circuit_set_circid_orconn_helper(circuit_t
*circ
, int direction
,
92 or_connection_t
*conn
)
94 orconn_circid_circuit_map_t search
;
95 orconn_circid_circuit_map_t
*found
;
96 or_connection_t
*old_conn
, **conn_ptr
;
97 circid_t old_id
, *circid_ptr
;
98 int was_active
, make_active
;
100 if (direction
== CELL_DIRECTION_OUT
) {
101 conn_ptr
= &circ
->n_conn
;
102 circid_ptr
= &circ
->n_circ_id
;
103 was_active
= circ
->next_active_on_n_conn
!= NULL
;
104 make_active
= circ
->n_conn_cells
.n
> 0;
106 or_circuit_t
*c
= TO_OR_CIRCUIT(circ
);
107 conn_ptr
= &c
->p_conn
;
108 circid_ptr
= &c
->p_circ_id
;
109 was_active
= c
->next_active_on_p_conn
!= NULL
;
110 make_active
= c
->p_conn_cells
.n
> 0;
112 old_conn
= *conn_ptr
;
113 old_id
= *circid_ptr
;
115 if (id
== old_id
&& conn
== old_conn
)
118 if (_last_circid_orconn_ent
&&
119 ((old_id
== _last_circid_orconn_ent
->circ_id
&&
120 old_conn
== _last_circid_orconn_ent
->or_conn
) ||
121 (id
== _last_circid_orconn_ent
->circ_id
&&
122 conn
== _last_circid_orconn_ent
->or_conn
))) {
123 _last_circid_orconn_ent
= NULL
;
126 if (old_conn
) { /* we may need to remove it from the conn-circid map */
127 tor_assert(old_conn
->_base
.magic
== OR_CONNECTION_MAGIC
);
128 search
.circ_id
= old_id
;
129 search
.or_conn
= old_conn
;
130 found
= HT_REMOVE(orconn_circid_map
, &orconn_circid_circuit_map
, &search
);
133 --old_conn
->n_circuits
;
135 if (was_active
&& old_conn
!= conn
)
136 make_circuit_inactive_on_conn(circ
,old_conn
);
139 /* Change the values only after we have possibly made the circuit inactive
140 * on the previous conn. */
147 /* now add the new one to the conn-circid map */
149 search
.or_conn
= conn
;
150 found
= HT_FIND(orconn_circid_map
, &orconn_circid_circuit_map
, &search
);
152 found
->circuit
= circ
;
154 found
= tor_malloc_zero(sizeof(orconn_circid_circuit_map_t
));
156 found
->or_conn
= conn
;
157 found
->circuit
= circ
;
158 HT_INSERT(orconn_circid_map
, &orconn_circid_circuit_map
, found
);
160 if (make_active
&& old_conn
!= conn
)
161 make_circuit_active_on_conn(circ
,conn
);
166 /** Set the p_conn field of a circuit <b>circ</b>, along
167 * with the corresponding circuit ID, and add the circuit as appropriate
168 * to the (orconn,id)-\>circuit map. */
170 circuit_set_p_circid_orconn(or_circuit_t
*circ
, circid_t id
,
171 or_connection_t
*conn
)
173 circuit_set_circid_orconn_helper(TO_CIRCUIT(circ
), CELL_DIRECTION_IN
,
177 tor_assert(bool_eq(circ
->p_conn_cells
.n
, circ
->next_active_on_p_conn
));
180 /** Set the n_conn field of a circuit <b>circ</b>, along
181 * with the corresponding circuit ID, and add the circuit as appropriate
182 * to the (orconn,id)-\>circuit map. */
184 circuit_set_n_circid_orconn(circuit_t
*circ
, circid_t id
,
185 or_connection_t
*conn
)
187 circuit_set_circid_orconn_helper(circ
, CELL_DIRECTION_OUT
, id
, conn
);
190 tor_assert(bool_eq(circ
->n_conn_cells
.n
, circ
->next_active_on_n_conn
));
193 /** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
194 * it from lists as appropriate. */
196 circuit_set_state(circuit_t
*circ
, uint8_t state
)
199 if (state
== circ
->state
)
201 if (!circuits_pending_or_conns
)
202 circuits_pending_or_conns
= smartlist_create();
203 if (circ
->state
== CIRCUIT_STATE_OR_WAIT
) {
204 /* remove from waiting-circuit list. */
205 smartlist_remove(circuits_pending_or_conns
, circ
);
207 if (state
== CIRCUIT_STATE_OR_WAIT
) {
208 /* add to waiting-circuit list. */
209 smartlist_add(circuits_pending_or_conns
, circ
);
211 if (state
== CIRCUIT_STATE_OPEN
)
212 tor_assert(!circ
->n_conn_onionskin
);
216 /** Add <b>circ</b> to the global list of circuits. This is called only from
217 * within circuit_new.
220 circuit_add(circuit_t
*circ
)
222 if (!global_circuitlist
) { /* first one */
223 global_circuitlist
= circ
;
226 circ
->next
= global_circuitlist
;
227 global_circuitlist
= circ
;
231 /** Append to <b>out</b> all circuits in state OR_WAIT waiting for
232 * the given connection. */
234 circuit_get_all_pending_on_or_conn(smartlist_t
*out
, or_connection_t
*or_conn
)
239 if (!circuits_pending_or_conns
)
242 SMARTLIST_FOREACH_BEGIN(circuits_pending_or_conns
, circuit_t
*, circ
) {
243 if (circ
->marked_for_close
)
247 tor_assert(circ
->state
== CIRCUIT_STATE_OR_WAIT
);
248 if (tor_digest_is_zero(circ
->n_hop
->identity_digest
)) {
249 /* Look at addr/port. This is an unkeyed connection. */
250 if (!tor_addr_eq(&circ
->n_hop
->addr
, &or_conn
->_base
.addr
) ||
251 circ
->n_hop
->port
!= or_conn
->_base
.port
)
254 /* We expected a key. See if it's the right one. */
255 if (memcmp(or_conn
->identity_digest
,
256 circ
->n_hop
->identity_digest
, DIGEST_LEN
))
259 smartlist_add(out
, circ
);
260 } SMARTLIST_FOREACH_END(circ
);
263 /** Return the number of circuits in state OR_WAIT, waiting for the given
266 circuit_count_pending_on_or_conn(or_connection_t
*or_conn
)
269 smartlist_t
*sl
= smartlist_create();
270 circuit_get_all_pending_on_or_conn(sl
, or_conn
);
271 cnt
= smartlist_len(sl
);
273 log_debug(LD_CIRC
,"or_conn to %s, %d pending circs",
274 or_conn
->nickname
? or_conn
->nickname
: "NULL", cnt
);
278 /** Detach from the global circuit list, and deallocate, all
279 * circuits that have been marked for close.
282 circuit_close_all_marked(void)
286 while (global_circuitlist
&& global_circuitlist
->marked_for_close
) {
287 tmp
= global_circuitlist
->next
;
288 circuit_free(global_circuitlist
);
289 global_circuitlist
= tmp
;
292 tmp
= global_circuitlist
;
293 while (tmp
&& tmp
->next
) {
294 if (tmp
->next
->marked_for_close
) {
296 circuit_free(tmp
->next
);
298 /* Need to check new tmp->next; don't advance tmp. */
306 /** Return the head of the global linked list of circuits. */
308 _circuit_get_global_list(void)
310 return global_circuitlist
;
313 /** Function to make circ-\>state human-readable */
315 circuit_state_to_string(int state
)
319 case CIRCUIT_STATE_BUILDING
: return "doing handshakes";
320 case CIRCUIT_STATE_ONIONSKIN_PENDING
: return "processing the onion";
321 case CIRCUIT_STATE_OR_WAIT
: return "connecting to server";
322 case CIRCUIT_STATE_OPEN
: return "open";
324 log_warn(LD_BUG
, "Unknown circuit state %d", state
);
325 tor_snprintf(buf
, sizeof(buf
), "unknown state [%d]", state
);
330 /** Map a circuit purpose to a string suitable to be displayed to a
333 circuit_purpose_to_controller_string(uint8_t purpose
)
337 case CIRCUIT_PURPOSE_OR
:
338 case CIRCUIT_PURPOSE_INTRO_POINT
:
339 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
340 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
341 return "SERVER"; /* A controller should never see these, actually. */
343 case CIRCUIT_PURPOSE_C_GENERAL
:
345 case CIRCUIT_PURPOSE_C_INTRODUCING
:
346 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
347 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
348 return "HS_CLIENT_INTRO";
350 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
351 case CIRCUIT_PURPOSE_C_REND_READY
:
352 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
353 case CIRCUIT_PURPOSE_C_REND_JOINED
:
354 return "HS_CLIENT_REND";
356 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
357 case CIRCUIT_PURPOSE_S_INTRO
:
358 return "HS_SERVICE_INTRO";
360 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
361 case CIRCUIT_PURPOSE_S_REND_JOINED
:
362 return "HS_SERVICE_REND";
364 case CIRCUIT_PURPOSE_TESTING
:
366 case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
:
368 case CIRCUIT_PURPOSE_CONTROLLER
:
372 tor_snprintf(buf
, sizeof(buf
), "UNKNOWN_%d", (int)purpose
);
377 /** Pick a reasonable package_window to start out for our circuits.
378 * Originally this was hard-coded at 1000, but now the consensus votes
379 * on the answer. See proposal 168. */
381 circuit_initial_package_window(void)
383 int32_t num
= networkstatus_get_param(NULL
, "circwindow", CIRCWINDOW_START
);
384 /* If the consensus tells us a negative number, we'd assert. */
386 num
= CIRCWINDOW_START
;
390 /** Initialize the common elements in a circuit_t, and add it to the global
393 init_circuit_base(circuit_t
*circ
)
395 circ
->timestamp_created
= time(NULL
);
396 tor_gettimeofday(&circ
->highres_created
);
398 circ
->package_window
= circuit_initial_package_window();
399 circ
->deliver_window
= CIRCWINDOW_START
;
401 /* Initialize the cell_ewma_t structure */
402 circ
->n_cell_ewma
.last_adjusted_tick
= cell_ewma_get_tick();
403 circ
->n_cell_ewma
.cell_count
= 0.0;
404 circ
->n_cell_ewma
.heap_index
= -1;
405 circ
->n_cell_ewma
.is_for_p_conn
= 0;
410 /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
411 * and <b>p_conn</b>. Add it to the global circuit list.
414 origin_circuit_new(void)
416 origin_circuit_t
*circ
;
417 /* never zero, since a global ID of 0 is treated specially by the
419 static uint32_t n_circuits_allocated
= 1;
421 circ
= tor_malloc_zero(sizeof(origin_circuit_t
));
422 circ
->_base
.magic
= ORIGIN_CIRCUIT_MAGIC
;
424 circ
->next_stream_id
= crypto_rand_int(1<<16);
425 circ
->global_identifier
= n_circuits_allocated
++;
426 circ
->remaining_relay_early_cells
= MAX_RELAY_EARLY_CELLS_PER_CIRCUIT
;
427 circ
->remaining_relay_early_cells
-= crypto_rand_int(2);
429 init_circuit_base(TO_CIRCUIT(circ
));
431 circ_times
.last_circ_at
= approx_time();
436 /** Allocate a new or_circuit_t, connected to <b>p_conn</b> as
437 * <b>p_circ_id</b>. If <b>p_conn</b> is NULL, the circuit is unattached. */
439 or_circuit_new(circid_t p_circ_id
, or_connection_t
*p_conn
)
444 circ
= tor_malloc_zero(sizeof(or_circuit_t
));
445 circ
->_base
.magic
= OR_CIRCUIT_MAGIC
;
448 circuit_set_p_circid_orconn(circ
, p_circ_id
, p_conn
);
450 circ
->remaining_relay_early_cells
= MAX_RELAY_EARLY_CELLS_PER_CIRCUIT
;
452 init_circuit_base(TO_CIRCUIT(circ
));
454 /* Initialize the cell_ewma_t structure */
456 /* Initialize the cell counts to 0 */
457 circ
->p_cell_ewma
.cell_count
= 0.0;
458 circ
->p_cell_ewma
.last_adjusted_tick
= cell_ewma_get_tick();
459 circ
->p_cell_ewma
.is_for_p_conn
= 1;
461 /* It's not in any heap yet. */
462 circ
->p_cell_ewma
.heap_index
= -1;
467 /** Deallocate space associated with circ.
470 circuit_free(circuit_t
*circ
)
477 if (CIRCUIT_IS_ORIGIN(circ
)) {
478 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
480 memlen
= sizeof(origin_circuit_t
);
481 tor_assert(circ
->magic
== ORIGIN_CIRCUIT_MAGIC
);
482 if (ocirc
->build_state
) {
483 extend_info_free(ocirc
->build_state
->chosen_exit
);
484 circuit_free_cpath_node(ocirc
->build_state
->pending_final_cpath
);
486 tor_free(ocirc
->build_state
);
488 circuit_free_cpath(ocirc
->cpath
);
490 crypto_free_pk_env(ocirc
->intro_key
);
491 rend_data_free(ocirc
->rend_data
);
493 or_circuit_t
*ocirc
= TO_OR_CIRCUIT(circ
);
494 /* Remember cell statistics for this circuit before deallocating. */
495 if (get_options()->CellStatistics
)
496 rep_hist_buffer_stats_add_circ(circ
, time(NULL
));
498 memlen
= sizeof(or_circuit_t
);
499 tor_assert(circ
->magic
== OR_CIRCUIT_MAGIC
);
501 crypto_free_cipher_env(ocirc
->p_crypto
);
502 crypto_free_digest_env(ocirc
->p_digest
);
503 crypto_free_cipher_env(ocirc
->n_crypto
);
504 crypto_free_digest_env(ocirc
->n_digest
);
506 if (ocirc
->rend_splice
) {
507 or_circuit_t
*other
= ocirc
->rend_splice
;
508 tor_assert(other
->_base
.magic
== OR_CIRCUIT_MAGIC
);
509 other
->rend_splice
= NULL
;
512 /* remove from map. */
513 circuit_set_p_circid_orconn(ocirc
, 0, NULL
);
515 /* Clear cell queue _after_ removing it from the map. Otherwise our
516 * "active" checks will be violated. */
517 cell_queue_clear(ô
->p_conn_cells
);
520 extend_info_free(circ
->n_hop
);
521 tor_free(circ
->n_conn_onionskin
);
523 /* Remove from map. */
524 circuit_set_n_circid_orconn(circ
, 0, NULL
);
526 /* Clear cell queue _after_ removing it from the map. Otherwise our
527 * "active" checks will be violated. */
528 cell_queue_clear(&circ
->n_conn_cells
);
530 memset(mem
, 0xAA, memlen
); /* poison memory */
534 /** Deallocate space associated with the linked list <b>cpath</b>. */
536 circuit_free_cpath(crypt_path_t
*cpath
)
538 crypt_path_t
*victim
, *head
=cpath
;
543 /* it's a doubly linked list, so we have to notice when we've
544 * gone through it once. */
545 while (cpath
->next
&& cpath
->next
!= head
) {
547 cpath
= victim
->next
;
548 circuit_free_cpath_node(victim
);
551 circuit_free_cpath_node(cpath
);
554 /** Release all storage held by circuits. */
556 circuit_free_all(void)
559 while (global_circuitlist
) {
560 next
= global_circuitlist
->next
;
561 if (! CIRCUIT_IS_ORIGIN(global_circuitlist
)) {
562 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(global_circuitlist
);
563 while (or_circ
->resolving_streams
) {
564 edge_connection_t
*next_conn
;
565 next_conn
= or_circ
->resolving_streams
->next_stream
;
566 connection_free(TO_CONN(or_circ
->resolving_streams
));
567 or_circ
->resolving_streams
= next_conn
;
570 circuit_free(global_circuitlist
);
571 global_circuitlist
= next
;
574 smartlist_free(circuits_pending_or_conns
);
575 circuits_pending_or_conns
= NULL
;
577 HT_CLEAR(orconn_circid_map
, &orconn_circid_circuit_map
);
580 /** Deallocate space associated with the cpath node <b>victim</b>. */
582 circuit_free_cpath_node(crypt_path_t
*victim
)
587 crypto_free_cipher_env(victim
->f_crypto
);
588 crypto_free_cipher_env(victim
->b_crypto
);
589 crypto_free_digest_env(victim
->f_digest
);
590 crypto_free_digest_env(victim
->b_digest
);
591 crypto_dh_free(victim
->dh_handshake_state
);
592 extend_info_free(victim
->extend_info
);
594 memset(victim
, 0xBB, sizeof(crypt_path_t
)); /* poison memory */
598 /** A helper function for circuit_dump_by_conn() below. Log a bunch
599 * of information about circuit <b>circ</b>.
602 circuit_dump_details(int severity
, circuit_t
*circ
, int conn_array_index
,
603 const char *type
, int this_circid
, int other_circid
)
605 log(severity
, LD_CIRC
, "Conn %d has %s circuit: circID %d (other side %d), "
606 "state %d (%s), born %d:",
607 conn_array_index
, type
, this_circid
, other_circid
, circ
->state
,
608 circuit_state_to_string(circ
->state
), (int)circ
->timestamp_created
);
609 if (CIRCUIT_IS_ORIGIN(circ
)) { /* circ starts at this node */
610 circuit_log_path(severity
, LD_CIRC
, TO_ORIGIN_CIRCUIT(circ
));
614 /** Log, at severity <b>severity</b>, information about each circuit
615 * that is connected to <b>conn</b>.
618 circuit_dump_by_conn(connection_t
*conn
, int severity
)
621 edge_connection_t
*tmpconn
;
623 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
624 circid_t n_circ_id
= circ
->n_circ_id
, p_circ_id
= 0;
625 if (circ
->marked_for_close
)
628 if (! CIRCUIT_IS_ORIGIN(circ
))
629 p_circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
631 if (! CIRCUIT_IS_ORIGIN(circ
) && TO_OR_CIRCUIT(circ
)->p_conn
&&
632 TO_CONN(TO_OR_CIRCUIT(circ
)->p_conn
) == conn
)
633 circuit_dump_details(severity
, circ
, conn
->conn_array_index
, "App-ward",
634 p_circ_id
, n_circ_id
);
635 if (CIRCUIT_IS_ORIGIN(circ
)) {
636 for (tmpconn
=TO_ORIGIN_CIRCUIT(circ
)->p_streams
; tmpconn
;
637 tmpconn
=tmpconn
->next_stream
) {
638 if (TO_CONN(tmpconn
) == conn
) {
639 circuit_dump_details(severity
, circ
, conn
->conn_array_index
,
640 "App-ward", p_circ_id
, n_circ_id
);
644 if (circ
->n_conn
&& TO_CONN(circ
->n_conn
) == conn
)
645 circuit_dump_details(severity
, circ
, conn
->conn_array_index
, "Exit-ward",
646 n_circ_id
, p_circ_id
);
647 if (! CIRCUIT_IS_ORIGIN(circ
)) {
648 for (tmpconn
=TO_OR_CIRCUIT(circ
)->n_streams
; tmpconn
;
649 tmpconn
=tmpconn
->next_stream
) {
650 if (TO_CONN(tmpconn
) == conn
) {
651 circuit_dump_details(severity
, circ
, conn
->conn_array_index
,
652 "Exit-ward", n_circ_id
, p_circ_id
);
656 if (!circ
->n_conn
&& circ
->n_hop
&&
657 tor_addr_eq(&circ
->n_hop
->addr
, &conn
->addr
) &&
658 circ
->n_hop
->port
== conn
->port
&&
659 conn
->type
== CONN_TYPE_OR
&&
660 !memcmp(TO_OR_CONN(conn
)->identity_digest
,
661 circ
->n_hop
->identity_digest
, DIGEST_LEN
)) {
662 circuit_dump_details(severity
, circ
, conn
->conn_array_index
,
663 (circ
->state
== CIRCUIT_STATE_OPEN
&&
664 !CIRCUIT_IS_ORIGIN(circ
)) ?
665 "Endpoint" : "Pending",
666 n_circ_id
, p_circ_id
);
671 /** Return the circuit whose global ID is <b>id</b>, or NULL if no
672 * such circuit exists. */
674 circuit_get_by_global_id(uint32_t id
)
677 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
678 if (CIRCUIT_IS_ORIGIN(circ
) &&
679 TO_ORIGIN_CIRCUIT(circ
)->global_identifier
== id
) {
680 if (circ
->marked_for_close
)
683 return TO_ORIGIN_CIRCUIT(circ
);
689 /** Return a circ such that:
690 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
691 * - circ is attached to <b>conn</b>, either as p_conn or n_conn.
692 * Return NULL if no such circuit exists.
694 static INLINE circuit_t
*
695 circuit_get_by_circid_orconn_impl(circid_t circ_id
, or_connection_t
*conn
)
697 orconn_circid_circuit_map_t search
;
698 orconn_circid_circuit_map_t
*found
;
700 if (_last_circid_orconn_ent
&&
701 circ_id
== _last_circid_orconn_ent
->circ_id
&&
702 conn
== _last_circid_orconn_ent
->or_conn
) {
703 found
= _last_circid_orconn_ent
;
705 search
.circ_id
= circ_id
;
706 search
.or_conn
= conn
;
707 found
= HT_FIND(orconn_circid_map
, &orconn_circid_circuit_map
, &search
);
708 _last_circid_orconn_ent
= found
;
710 if (found
&& found
->circuit
)
711 return found
->circuit
;
715 /* The rest of this checks for bugs. Disabled by default. */
718 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
719 if (! CIRCUIT_IS_ORIGIN(circ
)) {
720 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
721 if (or_circ
->p_conn
== conn
&& or_circ
->p_circ_id
== circ_id
) {
723 "circuit matches p_conn, but not in hash table (Bug!)");
727 if (circ
->n_conn
== conn
&& circ
->n_circ_id
== circ_id
) {
729 "circuit matches n_conn, but not in hash table (Bug!)");
737 /** Return a circ such that:
738 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
739 * - circ is attached to <b>conn</b>, either as p_conn or n_conn.
740 * - circ is not marked for close.
741 * Return NULL if no such circuit exists.
744 circuit_get_by_circid_orconn(circid_t circ_id
, or_connection_t
*conn
)
746 circuit_t
*circ
= circuit_get_by_circid_orconn_impl(circ_id
, conn
);
747 if (!circ
|| circ
->marked_for_close
)
753 /** Return true iff the circuit ID <b>circ_id</b> is currently used by a
754 * circuit, marked or not, on <b>conn</b>. */
756 circuit_id_in_use_on_orconn(circid_t circ_id
, or_connection_t
*conn
)
758 return circuit_get_by_circid_orconn_impl(circ_id
, conn
) != NULL
;
761 /** Return the circuit that a given edge connection is using. */
763 circuit_get_by_edge_conn(edge_connection_t
*conn
)
767 circ
= conn
->on_circuit
;
769 (CIRCUIT_IS_ORIGIN(circ
) ? circ
->magic
== ORIGIN_CIRCUIT_MAGIC
770 : circ
->magic
== OR_CIRCUIT_MAGIC
));
775 /** For each circuit that has <b>conn</b> as n_conn or p_conn, unlink the
776 * circuit from the orconn,circid map, and mark it for close if it hasn't
777 * been marked already.
780 circuit_unlink_all_from_or_conn(or_connection_t
*conn
, int reason
)
784 connection_or_unlink_all_active_circs(conn
);
786 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
788 if (circ
->n_conn
== conn
) {
789 circuit_set_n_circid_orconn(circ
, 0, NULL
);
792 if (! CIRCUIT_IS_ORIGIN(circ
)) {
793 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
794 if (or_circ
->p_conn
== conn
) {
795 circuit_set_p_circid_orconn(or_circ
, 0, NULL
);
799 if (mark
&& !circ
->marked_for_close
)
800 circuit_mark_for_close(circ
, reason
);
804 /** Return a circ such that:
805 * - circ-\>rend_data-\>query is equal to <b>rend_query</b>, and
806 * - circ-\>purpose is equal to <b>purpose</b>.
808 * Return NULL if no such circuit exists.
811 circuit_get_by_rend_query_and_purpose(const char *rend_query
, uint8_t purpose
)
815 tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose
));
817 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
818 if (!circ
->marked_for_close
&&
819 circ
->purpose
== purpose
) {
820 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
821 if (ocirc
->rend_data
&&
822 !rend_cmp_service_ids(rend_query
,
823 ocirc
->rend_data
->onion_address
))
830 /** Return the first circuit originating here in global_circuitlist after
831 * <b>start</b> whose purpose is <b>purpose</b>, and where
832 * <b>digest</b> (if set) matches the rend_pk_digest field. Return NULL if no
833 * circuit is found. If <b>start</b> is NULL, begin at the start of the list.
836 circuit_get_next_by_pk_and_purpose(origin_circuit_t
*start
,
837 const char *digest
, uint8_t purpose
)
840 tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose
));
842 circ
= global_circuitlist
;
844 circ
= TO_CIRCUIT(start
)->next
;
846 for ( ; circ
; circ
= circ
->next
) {
847 if (circ
->marked_for_close
)
849 if (circ
->purpose
!= purpose
)
852 return TO_ORIGIN_CIRCUIT(circ
);
853 else if (TO_ORIGIN_CIRCUIT(circ
)->rend_data
&&
854 !memcmp(TO_ORIGIN_CIRCUIT(circ
)->rend_data
->rend_pk_digest
,
856 return TO_ORIGIN_CIRCUIT(circ
);
861 /** Return the first OR circuit in the global list whose purpose is
862 * <b>purpose</b>, and whose rend_token is the <b>len</b>-byte
864 static or_circuit_t
*
865 circuit_get_by_rend_token_and_purpose(uint8_t purpose
, const char *token
,
869 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
870 if (! circ
->marked_for_close
&&
871 circ
->purpose
== purpose
&&
872 ! memcmp(TO_OR_CIRCUIT(circ
)->rend_token
, token
, len
))
873 return TO_OR_CIRCUIT(circ
);
878 /** Return the circuit waiting for a rendezvous with the provided cookie.
879 * Return NULL if no such circuit is found.
882 circuit_get_rendezvous(const char *cookie
)
884 return circuit_get_by_rend_token_and_purpose(
885 CIRCUIT_PURPOSE_REND_POINT_WAITING
,
886 cookie
, REND_COOKIE_LEN
);
889 /** Return the circuit waiting for intro cells of the given digest.
890 * Return NULL if no such circuit is found.
893 circuit_get_intro_point(const char *digest
)
895 return circuit_get_by_rend_token_and_purpose(
896 CIRCUIT_PURPOSE_INTRO_POINT
, digest
,
900 /** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL,
901 * has a timestamp_dirty value of 0, has flags matching the CIRCLAUNCH_*
902 * flags in <b>flags</b>, and if info is defined, does not already use info
903 * as any of its hops; or NULL if no circuit fits this description.
905 * The <b>purpose</b> argument (currently ignored) refers to the purpose of
906 * the circuit we want to create, not the purpose of the circuit we want to
909 * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits.
912 circuit_find_to_cannibalize(uint8_t purpose
, extend_info_t
*info
,
916 origin_circuit_t
*best
=NULL
;
917 int need_uptime
= (flags
& CIRCLAUNCH_NEED_UPTIME
) != 0;
918 int need_capacity
= (flags
& CIRCLAUNCH_NEED_CAPACITY
) != 0;
919 int internal
= (flags
& CIRCLAUNCH_IS_INTERNAL
) != 0;
921 /* Make sure we're not trying to create a onehop circ by
922 * cannibalization. */
923 tor_assert(!(flags
& CIRCLAUNCH_ONEHOP_TUNNEL
));
926 "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
927 "capacity %d, internal %d",
928 purpose
, need_uptime
, need_capacity
, internal
);
930 for (_circ
=global_circuitlist
; _circ
; _circ
= _circ
->next
) {
931 if (CIRCUIT_IS_ORIGIN(_circ
) &&
932 _circ
->state
== CIRCUIT_STATE_OPEN
&&
933 !_circ
->marked_for_close
&&
934 _circ
->purpose
== CIRCUIT_PURPOSE_C_GENERAL
&&
935 !_circ
->timestamp_dirty
) {
936 origin_circuit_t
*circ
= TO_ORIGIN_CIRCUIT(_circ
);
937 if ((!need_uptime
|| circ
->build_state
->need_uptime
) &&
938 (!need_capacity
|| circ
->build_state
->need_capacity
) &&
939 (internal
== circ
->build_state
->is_internal
) &&
940 circ
->remaining_relay_early_cells
&&
941 !circ
->build_state
->onehop_tunnel
) {
943 /* need to make sure we don't duplicate hops */
944 crypt_path_t
*hop
= circ
->cpath
;
945 routerinfo_t
*ri1
= router_get_by_digest(info
->identity_digest
);
948 if (!memcmp(hop
->extend_info
->identity_digest
,
949 info
->identity_digest
, DIGEST_LEN
))
952 (ri2
= router_get_by_digest(hop
->extend_info
->identity_digest
))
953 && routers_in_same_family(ri1
, ri2
))
956 } while (hop
!=circ
->cpath
);
958 if (!best
|| (best
->build_state
->need_uptime
&& !need_uptime
))
967 /** Return the number of hops in circuit's path. */
969 circuit_get_cpath_len(origin_circuit_t
*circ
)
972 if (circ
&& circ
->cpath
) {
973 crypt_path_t
*cpath
, *cpath_next
= NULL
;
974 for (cpath
= circ
->cpath
; cpath_next
!= circ
->cpath
; cpath
= cpath_next
) {
975 cpath_next
= cpath
->next
;
982 /** Return the <b>hopnum</b>th hop in <b>circ</b>->cpath, or NULL if there
983 * aren't that many hops in the list. */
985 circuit_get_cpath_hop(origin_circuit_t
*circ
, int hopnum
)
987 if (circ
&& circ
->cpath
&& hopnum
> 0) {
988 crypt_path_t
*cpath
, *cpath_next
= NULL
;
989 for (cpath
= circ
->cpath
; cpath_next
!= circ
->cpath
; cpath
= cpath_next
) {
990 cpath_next
= cpath
->next
;
998 /** Go through the circuitlist; mark-for-close each circuit that starts
999 * at us but has not yet been used. */
1001 circuit_mark_all_unused_circs(void)
1005 for (circ
=global_circuitlist
; circ
; circ
= circ
->next
) {
1006 if (CIRCUIT_IS_ORIGIN(circ
) &&
1007 !circ
->marked_for_close
&&
1008 !circ
->timestamp_dirty
)
1009 circuit_mark_for_close(circ
, END_CIRC_REASON_FINISHED
);
1013 /** Go through the circuitlist; for each circuit that starts at us
1014 * and is dirty, frob its timestamp_dirty so we won't use it for any
1017 * This is useful for letting the user change pseudonyms, so new
1018 * streams will not be linkable to old streams.
1021 circuit_expire_all_dirty_circs(void)
1024 or_options_t
*options
= get_options();
1026 for (circ
=global_circuitlist
; circ
; circ
= circ
->next
) {
1027 if (CIRCUIT_IS_ORIGIN(circ
) &&
1028 !circ
->marked_for_close
&&
1029 circ
->timestamp_dirty
)
1030 circ
->timestamp_dirty
-= options
->MaxCircuitDirtiness
;
1034 /** Mark <b>circ</b> to be closed next time we call
1035 * circuit_close_all_marked(). Do any cleanup needed:
1036 * - If state is onionskin_pending, remove circ from the onion_pending
1038 * - If circ isn't open yet: call circuit_build_failed() if we're
1039 * the origin, and in either case call circuit_rep_hist_note_result()
1041 * - If purpose is C_INTRODUCE_ACK_WAIT, remove the intro point we
1042 * just tried from our list of intro points for that service
1044 * - Send appropriate destroys and edge_destroys for conns and
1045 * streams attached to circ.
1046 * - If circ->rend_splice is set (we are the midpoint of a joined
1047 * rendezvous stream), then mark the other circuit to close as well.
1050 _circuit_mark_for_close(circuit_t
*circ
, int reason
, int line
,
1053 int orig_reason
= reason
; /* Passed to the controller */
1054 assert_circuit_ok(circ
);
1058 if (circ
->marked_for_close
) {
1059 log(LOG_WARN
,LD_BUG
,
1060 "Duplicate call to circuit_mark_for_close at %s:%d"
1061 " (first at %s:%d)", file
, line
,
1062 circ
->marked_for_close_file
, circ
->marked_for_close
);
1065 if (reason
== END_CIRC_AT_ORIGIN
) {
1066 if (!CIRCUIT_IS_ORIGIN(circ
)) {
1067 log_warn(LD_BUG
, "Specified 'at-origin' non-reason for ending circuit, "
1068 "but circuit was not at origin. (called %s:%d, purpose=%d)",
1069 file
, line
, circ
->purpose
);
1071 reason
= END_CIRC_REASON_NONE
;
1073 if (CIRCUIT_IS_ORIGIN(circ
)) {
1074 /* We don't send reasons when closing circuits at the origin. */
1075 reason
= END_CIRC_REASON_NONE
;
1078 if (reason
& END_CIRC_REASON_FLAG_REMOTE
)
1079 reason
&= ~END_CIRC_REASON_FLAG_REMOTE
;
1081 if (reason
< _END_CIRC_REASON_MIN
|| reason
> _END_CIRC_REASON_MAX
) {
1082 if (!(orig_reason
& END_CIRC_REASON_FLAG_REMOTE
))
1083 log_warn(LD_BUG
, "Reason %d out of range at %s:%d", reason
, file
, line
);
1084 reason
= END_CIRC_REASON_NONE
;
1087 if (circ
->state
== CIRCUIT_STATE_ONIONSKIN_PENDING
) {
1088 onion_pending_remove(TO_OR_CIRCUIT(circ
));
1090 /* If the circuit ever became OPEN, we sent it to the reputation history
1091 * module then. If it isn't OPEN, we send it there now to remember which
1092 * links worked and which didn't.
1094 if (circ
->state
!= CIRCUIT_STATE_OPEN
) {
1095 if (CIRCUIT_IS_ORIGIN(circ
)) {
1096 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
1097 circuit_build_failed(ocirc
); /* take actions if necessary */
1098 circuit_rep_hist_note_result(ocirc
);
1101 if (circ
->state
== CIRCUIT_STATE_OR_WAIT
) {
1102 if (circuits_pending_or_conns
)
1103 smartlist_remove(circuits_pending_or_conns
, circ
);
1105 if (CIRCUIT_IS_ORIGIN(circ
)) {
1106 control_event_circuit_status(TO_ORIGIN_CIRCUIT(circ
),
1107 (circ
->state
== CIRCUIT_STATE_OPEN
)?CIRC_EVENT_CLOSED
:CIRC_EVENT_FAILED
,
1110 if (circ
->purpose
== CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
) {
1111 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
1112 tor_assert(circ
->state
== CIRCUIT_STATE_OPEN
);
1113 tor_assert(ocirc
->build_state
->chosen_exit
);
1114 tor_assert(ocirc
->rend_data
);
1115 /* treat this like getting a nack from it */
1116 log_info(LD_REND
, "Failed intro circ %s to %s (awaiting ack). "
1117 "Removing from descriptor.",
1118 safe_str_client(ocirc
->rend_data
->onion_address
),
1119 safe_str_client(build_state_get_exit_nickname(ocirc
->build_state
)));
1120 rend_client_remove_intro_point(ocirc
->build_state
->chosen_exit
,
1124 connection_or_send_destroy(circ
->n_circ_id
, circ
->n_conn
, reason
);
1126 if (! CIRCUIT_IS_ORIGIN(circ
)) {
1127 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
1128 edge_connection_t
*conn
;
1129 for (conn
=or_circ
->n_streams
; conn
; conn
=conn
->next_stream
)
1130 connection_edge_destroy(or_circ
->p_circ_id
, conn
);
1131 or_circ
->n_streams
= NULL
;
1133 while (or_circ
->resolving_streams
) {
1134 conn
= or_circ
->resolving_streams
;
1135 or_circ
->resolving_streams
= conn
->next_stream
;
1136 if (!conn
->_base
.marked_for_close
) {
1137 /* The client will see a DESTROY, and infer that the connections
1138 * are closing because the circuit is getting torn down. No need
1139 * to send an end cell. */
1140 conn
->edge_has_sent_end
= 1;
1141 conn
->end_reason
= END_STREAM_REASON_DESTROY
;
1142 conn
->end_reason
|= END_STREAM_REASON_FLAG_ALREADY_SENT_CLOSED
;
1143 connection_mark_for_close(TO_CONN(conn
));
1145 conn
->on_circuit
= NULL
;
1148 if (or_circ
->p_conn
)
1149 connection_or_send_destroy(or_circ
->p_circ_id
, or_circ
->p_conn
, reason
);
1151 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
1152 edge_connection_t
*conn
;
1153 for (conn
=ocirc
->p_streams
; conn
; conn
=conn
->next_stream
)
1154 connection_edge_destroy(circ
->n_circ_id
, conn
);
1155 ocirc
->p_streams
= NULL
;
1158 circ
->marked_for_close
= line
;
1159 circ
->marked_for_close_file
= file
;
1161 if (!CIRCUIT_IS_ORIGIN(circ
)) {
1162 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
1163 if (or_circ
->rend_splice
) {
1164 if (!or_circ
->rend_splice
->_base
.marked_for_close
) {
1165 /* do this after marking this circuit, to avoid infinite recursion. */
1166 circuit_mark_for_close(TO_CIRCUIT(or_circ
->rend_splice
), reason
);
1168 or_circ
->rend_splice
= NULL
;
1173 /** Verify that cpath layer <b>cp</b> has all of its invariants
1174 * correct. Trigger an assert if anything is invalid.
1177 assert_cpath_layer_ok(const crypt_path_t
*cp
)
1179 // tor_assert(cp->addr); /* these are zero for rendezvous extra-hops */
1180 // tor_assert(cp->port);
1182 tor_assert(cp
->magic
== CRYPT_PATH_MAGIC
);
1185 case CPATH_STATE_OPEN
:
1186 tor_assert(cp
->f_crypto
);
1187 tor_assert(cp
->b_crypto
);
1189 case CPATH_STATE_CLOSED
:
1190 tor_assert(!cp
->dh_handshake_state
);
1192 case CPATH_STATE_AWAITING_KEYS
:
1193 /* tor_assert(cp->dh_handshake_state); */
1196 log_fn(LOG_ERR
, LD_BUG
, "Unexpected state %d", cp
->state
);
1199 tor_assert(cp
->package_window
>= 0);
1200 tor_assert(cp
->deliver_window
>= 0);
1203 /** Verify that cpath <b>cp</b> has all of its invariants
1204 * correct. Trigger an assert if anything is invalid.
1207 assert_cpath_ok(const crypt_path_t
*cp
)
1209 const crypt_path_t
*start
= cp
;
1212 assert_cpath_layer_ok(cp
);
1213 /* layers must be in sequence of: "open* awaiting? closed*" */
1215 if (cp
->state
== CPATH_STATE_AWAITING_KEYS
) {
1216 tor_assert(cp
->prev
->state
== CPATH_STATE_OPEN
);
1217 } else if (cp
->state
== CPATH_STATE_OPEN
) {
1218 tor_assert(cp
->prev
->state
== CPATH_STATE_OPEN
);
1223 } while (cp
!= start
);
1226 /** Verify that circuit <b>c</b> has all of its invariants
1227 * correct. Trigger an assert if anything is invalid.
1230 assert_circuit_ok(const circuit_t
*c
)
1232 edge_connection_t
*conn
;
1233 const or_circuit_t
*or_circ
= NULL
;
1234 const origin_circuit_t
*origin_circ
= NULL
;
1237 tor_assert(c
->magic
== ORIGIN_CIRCUIT_MAGIC
|| c
->magic
== OR_CIRCUIT_MAGIC
);
1238 tor_assert(c
->purpose
>= _CIRCUIT_PURPOSE_MIN
&&
1239 c
->purpose
<= _CIRCUIT_PURPOSE_MAX
);
1242 /* Having a separate variable for this pleases GCC 4.2 in ways I hope I
1243 * never understand. -NM. */
1244 circuit_t
*nonconst_circ
= (circuit_t
*) c
;
1245 if (CIRCUIT_IS_ORIGIN(c
))
1246 origin_circ
= TO_ORIGIN_CIRCUIT(nonconst_circ
);
1248 or_circ
= TO_OR_CIRCUIT(nonconst_circ
);
1252 tor_assert(!c
->n_hop
);
1255 /* We use the _impl variant here to make sure we don't fail on marked
1256 * circuits, which would not be returned by the regular function. */
1257 circuit_t
*c2
= circuit_get_by_circid_orconn_impl(c
->n_circ_id
,
1259 tor_assert(c
== c2
);
1262 if (or_circ
&& or_circ
->p_conn
) {
1263 if (or_circ
->p_circ_id
) {
1265 circuit_t
*c2
= circuit_get_by_circid_orconn_impl(or_circ
->p_circ_id
,
1267 tor_assert(c
== c2
);
1271 for (conn
= or_circ
->n_streams
; conn
; conn
= conn
->next_stream
)
1272 tor_assert(conn
->_base
.type
== CONN_TYPE_EXIT
);
1274 tor_assert(c
->deliver_window
>= 0);
1275 tor_assert(c
->package_window
>= 0);
1276 if (c
->state
== CIRCUIT_STATE_OPEN
) {
1277 tor_assert(!c
->n_conn_onionskin
);
1279 tor_assert(or_circ
->n_crypto
);
1280 tor_assert(or_circ
->p_crypto
);
1281 tor_assert(or_circ
->n_digest
);
1282 tor_assert(or_circ
->p_digest
);
1285 if (c
->state
== CIRCUIT_STATE_OR_WAIT
&& !c
->marked_for_close
) {
1286 tor_assert(circuits_pending_or_conns
&&
1287 smartlist_isin(circuits_pending_or_conns
, c
));
1289 tor_assert(!circuits_pending_or_conns
||
1290 !smartlist_isin(circuits_pending_or_conns
, c
));
1292 if (origin_circ
&& origin_circ
->cpath
) {
1293 assert_cpath_ok(origin_circ
->cpath
);
1295 if (c
->purpose
== CIRCUIT_PURPOSE_REND_ESTABLISHED
) {
1296 tor_assert(or_circ
);
1297 if (!c
->marked_for_close
) {
1298 tor_assert(or_circ
->rend_splice
);
1299 tor_assert(or_circ
->rend_splice
->rend_splice
== or_circ
);
1301 tor_assert(or_circ
->rend_splice
!= or_circ
);
1303 tor_assert(!or_circ
|| !or_circ
->rend_splice
);