1 /* Copyright 2001 Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. */
4 /* See LICENSE for licensing information */
6 const char circuitlist_c_id
[] =
11 * \brief Manage the global circuit list.
16 #include "../common/ht.h"
18 /********* START VARIABLES **********/
20 /** A global list of all circuits at this hop. */
21 circuit_t
*global_circuitlist
=NULL
;
23 /** A list of all the circuits in CIRCUIT_STATE_OR_WAIT. */
24 static smartlist_t
*circuits_pending_or_conns
=NULL
;
26 static void circuit_free(circuit_t
*circ
);
27 static void circuit_free_cpath(crypt_path_t
*cpath
);
28 static void circuit_free_cpath_node(crypt_path_t
*victim
);
30 /********* END VARIABLES ************/
32 /** A map from OR connection and circuit ID to circuit. (Lookup performance is
33 * very important here, since we need to do it every time a cell arrives.) */
34 typedef struct orconn_circid_circuit_map_t
{
35 HT_ENTRY(orconn_circid_circuit_map_t
) node
;
36 or_connection_t
*or_conn
;
39 } orconn_circid_circuit_map_t
;
41 /** Helper for hash tables: compare the OR connection and circuit ID for a and
42 * b, and return less than, equal to, or greater than zero appropriately.
45 _orconn_circid_entries_eq(orconn_circid_circuit_map_t
*a
,
46 orconn_circid_circuit_map_t
*b
)
48 return a
->or_conn
== b
->or_conn
&& a
->circ_id
== b
->circ_id
;
52 static INLINE
unsigned int
53 _orconn_circid_entry_hash(orconn_circid_circuit_map_t
*a
)
55 return (((unsigned)a
->circ_id
)<<16) ^ (unsigned)(uintptr_t)(a
->or_conn
);
59 static HT_HEAD(orconn_circid_map
, orconn_circid_circuit_map_t
)
60 orconn_circid_circuit_map
= HT_INITIALIZER();
61 HT_PROTOTYPE(orconn_circid_map
, orconn_circid_circuit_map_t
, node
,
62 _orconn_circid_entry_hash
, _orconn_circid_entries_eq
);
63 HT_GENERATE(orconn_circid_map
, orconn_circid_circuit_map_t
, node
,
64 _orconn_circid_entry_hash
, _orconn_circid_entries_eq
, 0.6,
65 malloc
, realloc
, free
);
67 /** The most recently returned entry from circuit_get_by_circid_orconn;
68 * used to improve performance when many cells arrive in a row from the
71 orconn_circid_circuit_map_t
*_last_circid_orconn_ent
= NULL
;
74 circuit_set_circid_orconn_helper(circuit_t
*circ
, uint16_t id
,
75 or_connection_t
*conn
,
76 uint16_t old_id
, or_connection_t
*old_conn
)
78 orconn_circid_circuit_map_t search
;
79 orconn_circid_circuit_map_t
*found
;
81 if (_last_circid_orconn_ent
&&
82 ((old_id
== _last_circid_orconn_ent
->circ_id
&&
83 old_conn
== _last_circid_orconn_ent
->or_conn
) ||
84 (id
== _last_circid_orconn_ent
->circ_id
&&
85 conn
== _last_circid_orconn_ent
->or_conn
))) {
86 _last_circid_orconn_ent
= NULL
;
89 if (old_conn
) { /* we may need to remove it from the conn-circid map */
90 tor_assert(old_conn
->_base
.magic
== OR_CONNECTION_MAGIC
);
91 search
.circ_id
= old_id
;
92 search
.or_conn
= old_conn
;
93 found
= HT_REMOVE(orconn_circid_map
, &orconn_circid_circuit_map
, &search
);
96 --old_conn
->n_circuits
;
103 /* now add the new one to the conn-circid map */
105 search
.or_conn
= conn
;
106 found
= HT_FIND(orconn_circid_map
, &orconn_circid_circuit_map
, &search
);
108 found
->circuit
= circ
;
110 found
= tor_malloc_zero(sizeof(orconn_circid_circuit_map_t
));
112 found
->or_conn
= conn
;
113 found
->circuit
= circ
;
114 HT_INSERT(orconn_circid_map
, &orconn_circid_circuit_map
, found
);
119 /** Set the p_conn field of a circuit <b>circ</b>, along
120 * with the corresponding circuit ID, and add the circuit as appropriate
121 * to the (orconn,id)-\>circuit map. */
123 circuit_set_p_circid_orconn(or_circuit_t
*circ
, uint16_t id
,
124 or_connection_t
*conn
)
127 or_connection_t
*old_conn
;
129 old_id
= circ
->p_circ_id
;
130 old_conn
= circ
->p_conn
;
131 circ
->p_circ_id
= id
;
134 if (id
== old_id
&& conn
== old_conn
)
136 circuit_set_circid_orconn_helper(TO_CIRCUIT(circ
), id
, conn
,
140 /** Set the n_conn field of a circuit <b>circ</b>, along
141 * with the corresponding circuit ID, and add the circuit as appropriate
142 * to the (orconn,id)-\>circuit map. */
144 circuit_set_n_circid_orconn(circuit_t
*circ
, uint16_t id
,
145 or_connection_t
*conn
)
148 or_connection_t
*old_conn
;
150 old_id
= circ
->n_circ_id
;
151 old_conn
= circ
->n_conn
;
152 circ
->n_circ_id
= id
;
155 if (id
== old_id
&& conn
== old_conn
)
157 circuit_set_circid_orconn_helper(circ
, id
, conn
, old_id
, old_conn
);
160 /** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
161 * it from lists as appropriate. */
163 circuit_set_state(circuit_t
*circ
, int state
)
166 if (state
== circ
->state
)
168 if (!circuits_pending_or_conns
)
169 circuits_pending_or_conns
= smartlist_create();
170 if (circ
->state
== CIRCUIT_STATE_OR_WAIT
) {
171 /* remove from waiting-circuit list. */
172 smartlist_remove(circuits_pending_or_conns
, circ
);
174 if (state
== CIRCUIT_STATE_OR_WAIT
) {
175 /* add to waiting-circuit list. */
176 smartlist_add(circuits_pending_or_conns
, circ
);
181 /** Add <b>circ</b> to the global list of circuits. This is called only from
182 * within circuit_new.
185 circuit_add(circuit_t
*circ
)
187 if (!global_circuitlist
) { /* first one */
188 global_circuitlist
= circ
;
191 circ
->next
= global_circuitlist
;
192 global_circuitlist
= circ
;
196 /** Append to <b>out</b> the number of circuits in state OR_WAIT, waiting for
197 * the given connection. */
199 circuit_get_all_pending_on_or_conn(smartlist_t
*out
, or_connection_t
*or_conn
)
204 if (!circuits_pending_or_conns
)
207 SMARTLIST_FOREACH(circuits_pending_or_conns
, circuit_t
*, circ
,
209 if (circ
->marked_for_close
)
211 tor_assert(circ
->state
== CIRCUIT_STATE_OR_WAIT
);
213 !memcmp(or_conn
->identity_digest
, circ
->n_conn_id_digest
,
215 smartlist_add(out
, circ
);
220 /** Return the number of circuits in state OR_WAIT, waiting for the given
223 circuit_count_pending_on_or_conn(or_connection_t
*or_conn
)
226 smartlist_t
*sl
= smartlist_create();
227 circuit_get_all_pending_on_or_conn(sl
, or_conn
);
228 cnt
= smartlist_len(sl
);
230 log_debug(LD_CIRC
,"or_conn to %s, %d pending circs",
231 or_conn
->nickname
? or_conn
->nickname
: "NULL", cnt
);
235 /** Detach from the global circuit list, and deallocate, all
236 * circuits that have been marked for close.
239 circuit_close_all_marked(void)
243 while (global_circuitlist
&& global_circuitlist
->marked_for_close
) {
244 tmp
= global_circuitlist
->next
;
245 circuit_free(global_circuitlist
);
246 global_circuitlist
= tmp
;
249 tmp
= global_circuitlist
;
250 while (tmp
&& tmp
->next
) {
251 if (tmp
->next
->marked_for_close
) {
253 circuit_free(tmp
->next
);
255 /* Need to check new tmp->next; don't advance tmp. */
263 /** Return the head of the global linked list of circuits. */
265 _circuit_get_global_list(void)
267 return global_circuitlist
;
270 /** Function to make circ-\>state human-readable */
272 circuit_state_to_string(int state
)
276 case CIRCUIT_STATE_BUILDING
: return "doing handshakes";
277 case CIRCUIT_STATE_ONIONSKIN_PENDING
: return "processing the onion";
278 case CIRCUIT_STATE_OR_WAIT
: return "connecting to server";
279 case CIRCUIT_STATE_OPEN
: return "open";
281 log_warn(LD_BUG
, "Bug: unknown circuit state %d", state
);
282 tor_snprintf(buf
, sizeof(buf
), "unknown state [%d]", state
);
287 /** Initialize the common elements in a circuit_t, and add it to the global
290 init_circuit_base(circuit_t
*circ
)
292 circ
->timestamp_created
= time(NULL
);
294 circ
->package_window
= CIRCWINDOW_START
;
295 circ
->deliver_window
= CIRCWINDOW_START
;
300 /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
301 * and <b>p_conn</b>. Add it to the global circuit list.
304 origin_circuit_new(void)
306 origin_circuit_t
*circ
;
307 /* never zero, since a global ID of 0 is treated specially by the
309 static uint32_t n_circuits_allocated
= 1;
311 circ
= tor_malloc_zero(sizeof(origin_circuit_t
));
312 circ
->_base
.magic
= ORIGIN_CIRCUIT_MAGIC
;
314 circ
->next_stream_id
= crypto_rand_int(1<<16);
315 circ
->global_identifier
= n_circuits_allocated
++;
317 init_circuit_base(TO_CIRCUIT(circ
));
324 or_circuit_new(uint16_t p_circ_id
, or_connection_t
*p_conn
)
329 circ
= tor_malloc_zero(sizeof(or_circuit_t
));
330 circ
->_base
.magic
= OR_CIRCUIT_MAGIC
;
333 circuit_set_p_circid_orconn(circ
, p_circ_id
, p_conn
);
335 init_circuit_base(TO_CIRCUIT(circ
));
340 /** Deallocate space associated with circ.
343 circuit_free(circuit_t
*circ
)
347 if (CIRCUIT_IS_ORIGIN(circ
)) {
348 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
350 tor_assert(circ
->magic
== ORIGIN_CIRCUIT_MAGIC
);
351 if (ocirc
->build_state
) {
352 if (ocirc
->build_state
->chosen_exit
)
353 extend_info_free(ocirc
->build_state
->chosen_exit
);
354 if (ocirc
->build_state
->pending_final_cpath
)
355 circuit_free_cpath_node(ocirc
->build_state
->pending_final_cpath
);
357 tor_free(ocirc
->build_state
);
359 circuit_free_cpath(ocirc
->cpath
);
362 or_circuit_t
*ocirc
= TO_OR_CIRCUIT(circ
);
364 tor_assert(circ
->magic
== OR_CIRCUIT_MAGIC
);
367 crypto_free_cipher_env(ocirc
->p_crypto
);
369 crypto_free_digest_env(ocirc
->p_digest
);
371 crypto_free_cipher_env(ocirc
->n_crypto
);
373 crypto_free_digest_env(ocirc
->n_digest
);
375 if (ocirc
->rend_splice
) {
376 or_circuit_t
*other
= ocirc
->rend_splice
;
377 tor_assert(other
->_base
.magic
== OR_CIRCUIT_MAGIC
);
378 other
->rend_splice
= NULL
;
381 tor_free(circ
->onionskin
);
383 /* remove from map. */
384 circuit_set_p_circid_orconn(ocirc
, 0, NULL
);
387 /* Remove from map. */
388 circuit_set_n_circid_orconn(circ
, 0, NULL
);
390 memset(circ
, 0xAA, sizeof(circuit_t
)); /* poison memory */
394 /** Deallocate space associated with the linked list <b>cpath</b>. */
396 circuit_free_cpath(crypt_path_t
*cpath
)
398 crypt_path_t
*victim
, *head
=cpath
;
403 /* it's a doubly linked list, so we have to notice when we've
404 * gone through it once. */
405 while (cpath
->next
&& cpath
->next
!= head
) {
407 cpath
= victim
->next
;
408 circuit_free_cpath_node(victim
);
411 circuit_free_cpath_node(cpath
);
414 /** Release all storage held by circuits. */
416 circuit_free_all(void)
419 while (global_circuitlist
) {
420 next
= global_circuitlist
->next
;
421 if (! CIRCUIT_IS_ORIGIN(global_circuitlist
)) {
422 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(global_circuitlist
);
423 while (or_circ
->resolving_streams
) {
424 edge_connection_t
*next
;
425 next
= or_circ
->resolving_streams
->next_stream
;
426 connection_free(TO_CONN(or_circ
->resolving_streams
));
427 or_circ
->resolving_streams
= next
;
430 circuit_free(global_circuitlist
);
431 global_circuitlist
= next
;
433 if (circuits_pending_or_conns
) {
434 smartlist_free(circuits_pending_or_conns
);
435 circuits_pending_or_conns
= NULL
;
437 HT_CLEAR(orconn_circid_map
, &orconn_circid_circuit_map
);
440 /** Deallocate space associated with the cpath node <b>victim</b>. */
442 circuit_free_cpath_node(crypt_path_t
*victim
)
444 if (victim
->f_crypto
)
445 crypto_free_cipher_env(victim
->f_crypto
);
446 if (victim
->b_crypto
)
447 crypto_free_cipher_env(victim
->b_crypto
);
448 if (victim
->f_digest
)
449 crypto_free_digest_env(victim
->f_digest
);
450 if (victim
->b_digest
)
451 crypto_free_digest_env(victim
->b_digest
);
452 if (victim
->dh_handshake_state
)
453 crypto_dh_free(victim
->dh_handshake_state
);
454 if (victim
->extend_info
)
455 extend_info_free(victim
->extend_info
);
457 victim
->magic
= 0xDEADBEEFu
;
461 /** A helper function for circuit_dump_by_conn() below. Log a bunch
462 * of information about circuit <b>circ</b>.
465 circuit_dump_details(int severity
, circuit_t
*circ
, int conn_array_index
,
466 const char *type
, int this_circid
, int other_circid
)
468 log(severity
, LD_CIRC
, "Conn %d has %s circuit: circID %d (other side %d), "
469 "state %d (%s), born %d:",
470 conn_array_index
, type
, this_circid
, other_circid
, circ
->state
,
471 circuit_state_to_string(circ
->state
), (int)circ
->timestamp_created
);
472 if (CIRCUIT_IS_ORIGIN(circ
)) { /* circ starts at this node */
473 circuit_log_path(severity
, LD_CIRC
, TO_ORIGIN_CIRCUIT(circ
));
477 /** Log, at severity <b>severity</b>, information about each circuit
478 * that is connected to <b>conn</b>.
481 circuit_dump_by_conn(connection_t
*conn
, int severity
)
484 edge_connection_t
*tmpconn
;
486 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
487 circid_t n_circ_id
= circ
->n_circ_id
, p_circ_id
= 0;
488 if (circ
->marked_for_close
)
491 if (! CIRCUIT_IS_ORIGIN(circ
))
492 p_circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
494 if (! CIRCUIT_IS_ORIGIN(circ
) && TO_OR_CIRCUIT(circ
)->p_conn
&&
495 TO_CONN(TO_OR_CIRCUIT(circ
)->p_conn
) == conn
)
496 circuit_dump_details(severity
, circ
, conn
->conn_array_index
, "App-ward",
497 p_circ_id
, n_circ_id
);
498 if (CIRCUIT_IS_ORIGIN(circ
)) {
499 for (tmpconn
=TO_ORIGIN_CIRCUIT(circ
)->p_streams
; tmpconn
;
500 tmpconn
=tmpconn
->next_stream
) {
501 if (TO_CONN(tmpconn
) == conn
) {
502 circuit_dump_details(severity
, circ
, conn
->conn_array_index
,
503 "App-ward", p_circ_id
, n_circ_id
);
507 if (circ
->n_conn
&& TO_CONN(circ
->n_conn
) == conn
)
508 circuit_dump_details(severity
, circ
, conn
->conn_array_index
, "Exit-ward",
509 n_circ_id
, p_circ_id
);
510 if (! CIRCUIT_IS_ORIGIN(circ
)) {
511 for (tmpconn
=TO_OR_CIRCUIT(circ
)->n_streams
; tmpconn
;
512 tmpconn
=tmpconn
->next_stream
) {
513 if (TO_CONN(tmpconn
) == conn
) {
514 circuit_dump_details(severity
, circ
, conn
->conn_array_index
,
515 "Exit-ward", n_circ_id
, p_circ_id
);
519 if (!circ
->n_conn
&& circ
->n_addr
&& circ
->n_port
&&
520 circ
->n_addr
== conn
->addr
&&
521 circ
->n_port
== conn
->port
&&
522 conn
->type
== CONN_TYPE_OR
&&
523 !memcmp(TO_OR_CONN(conn
)->identity_digest
, circ
->n_conn_id_digest
,
525 circuit_dump_details(severity
, circ
, conn
->conn_array_index
,
526 (circ
->state
== CIRCUIT_STATE_OPEN
&&
527 !CIRCUIT_IS_ORIGIN(circ
)) ?
528 "Endpoint" : "Pending",
529 n_circ_id
, p_circ_id
);
534 /** Return the circuit whose global ID is <b>id</b>, or NULL if no
535 * such circuit exists. */
537 circuit_get_by_global_id(uint32_t id
)
540 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
541 if (CIRCUIT_IS_ORIGIN(circ
) &&
542 TO_ORIGIN_CIRCUIT(circ
)->global_identifier
== id
) {
543 if (circ
->marked_for_close
)
546 return TO_ORIGIN_CIRCUIT(circ
);
552 /** Return a circ such that:
553 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
554 * - circ is attached to <b>conn</b>, either as p_conn or n_conn.
555 * Return NULL if no such circuit exists.
557 static INLINE circuit_t
*
558 circuit_get_by_circid_orconn_impl(uint16_t circ_id
, or_connection_t
*conn
)
560 orconn_circid_circuit_map_t search
;
561 orconn_circid_circuit_map_t
*found
;
563 if (_last_circid_orconn_ent
&&
564 circ_id
== _last_circid_orconn_ent
->circ_id
&&
565 conn
== _last_circid_orconn_ent
->or_conn
) {
566 found
= _last_circid_orconn_ent
;
568 search
.circ_id
= circ_id
;
569 search
.or_conn
= conn
;
570 found
= HT_FIND(orconn_circid_map
, &orconn_circid_circuit_map
, &search
);
571 _last_circid_orconn_ent
= found
;
573 if (found
&& found
->circuit
)
574 return found
->circuit
;
578 /* The rest of this checks for bugs. Disabled by default. */
581 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
582 if (! CIRCUIT_IS_ORIGIN(circ
)) {
583 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
584 if (or_circ
->p_conn
== conn
&& or_circ
->p_circ_id
== circ_id
) {
586 "circuit matches p_conn, but not in hash table (Bug!)");
590 if (circ
->n_conn
== conn
&& circ
->n_circ_id
== circ_id
) {
592 "circuit matches n_conn, but not in hash table (Bug!)");
600 /** Return a circ such that:
601 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
602 * - circ is attached to <b>conn</b>, either as p_conn or n_conn.
603 * - circ is not marked for close.
604 * Return NULL if no such circuit exists.
607 circuit_get_by_circid_orconn(uint16_t circ_id
, or_connection_t
*conn
)
609 circuit_t
*circ
= circuit_get_by_circid_orconn_impl(circ_id
, conn
);
610 if (!circ
|| circ
->marked_for_close
)
616 /** Return the circuit that a given edge connection is using. */
618 circuit_get_by_edge_conn(edge_connection_t
*conn
)
622 circ
= conn
->on_circuit
;
624 (CIRCUIT_IS_ORIGIN(circ
) ? circ
->magic
== ORIGIN_CIRCUIT_MAGIC
625 : circ
->magic
== OR_CIRCUIT_MAGIC
));
630 /** For each circuit that has <b>conn</b> as n_conn or p_conn, unlink the
631 * circuit from the orconn,circid map, and mark it for close if it hasn't
632 * been marked already.
635 circuit_unlink_all_from_or_conn(or_connection_t
*conn
, int reason
)
638 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
640 if (circ
->n_conn
== conn
) {
641 circuit_set_n_circid_orconn(circ
, 0, NULL
);
644 if (! CIRCUIT_IS_ORIGIN(circ
)) {
645 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
646 if (or_circ
->p_conn
== conn
) {
647 circuit_set_p_circid_orconn(or_circ
, 0, NULL
);
651 if (mark
&& !circ
->marked_for_close
)
652 circuit_mark_for_close(circ
, reason
);
656 /** Return a circ such that:
657 * - circ-\>rend_query is equal to <b>rend_query</b>, and
658 * - circ-\>purpose is equal to <b>purpose</b>.
660 * Return NULL if no such circuit exists.
663 circuit_get_by_rend_query_and_purpose(const char *rend_query
, uint8_t purpose
)
667 tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose
));
669 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
670 if (!circ
->marked_for_close
&&
671 circ
->purpose
== purpose
&&
672 !rend_cmp_service_ids(rend_query
, TO_ORIGIN_CIRCUIT(circ
)->rend_query
))
673 return TO_ORIGIN_CIRCUIT(circ
);
678 /** Return the first circuit originating here in global_circuitlist after
679 * <b>start</b> whose purpose is <b>purpose</b> is purpose, and where
680 * <b>digest</b> (if set) matches the rend_pk_digest field. Return NULL if no
681 * circuit is found. If <b>start</b> is NULL, begin at the start of the list.
684 circuit_get_next_by_pk_and_purpose(origin_circuit_t
*start
,
685 const char *digest
, uint8_t purpose
)
688 tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose
));
690 circ
= global_circuitlist
;
692 circ
= TO_CIRCUIT(start
)->next
;
694 for ( ; circ
; circ
= circ
->next
) {
695 if (circ
->marked_for_close
)
697 if (circ
->purpose
!= purpose
)
700 return TO_ORIGIN_CIRCUIT(circ
);
701 else if (!memcmp(TO_ORIGIN_CIRCUIT(circ
)->rend_pk_digest
,
703 return TO_ORIGIN_CIRCUIT(circ
);
708 /** Return the first OR circuit in the global list whose purpose is
709 * <b>purpose</b>, and whose rend_token is the <b>len</b>-byte
711 static or_circuit_t
*
712 circuit_get_by_rend_token_and_purpose(uint8_t purpose
, const char *token
,
716 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
717 if (! circ
->marked_for_close
&&
718 circ
->purpose
== purpose
&&
719 ! memcmp(TO_OR_CIRCUIT(circ
)->rend_token
, token
, len
))
720 return TO_OR_CIRCUIT(circ
);
725 /** Return the circuit waiting for a rendezvous with the provided cookie.
726 * Return NULL if no such circuit is found.
729 circuit_get_rendezvous(const char *cookie
)
731 return circuit_get_by_rend_token_and_purpose(
732 CIRCUIT_PURPOSE_REND_POINT_WAITING
,
733 cookie
, REND_COOKIE_LEN
);
736 /** Return the circuit waiting for intro cells of the given digest.
737 * Return NULL if no such circuit is found.
740 circuit_get_intro_point(const char *digest
)
742 return circuit_get_by_rend_token_and_purpose(
743 CIRCUIT_PURPOSE_INTRO_POINT
, digest
,
747 /** Return a circuit that is open, has specified <b>purpose</b>,
748 * has a timestamp_dirty value of 0, is uptime/capacity/internal
749 * if required, and if info is defined, does not already use info
750 * as any of its hops; or NULL if no circuit fits this description.
752 * Return need_uptime circuits if that is requested; and if it's not
753 * requested, return non-uptime circuits if possible, else either.
755 * Only return internal circuits if that is requested.
758 circuit_find_to_cannibalize(uint8_t purpose
, extend_info_t
*info
,
760 int need_capacity
, int internal
)
763 origin_circuit_t
*best
=NULL
;
766 "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
767 "capacity %d, internal %d",
768 purpose
, need_uptime
, need_capacity
, internal
);
770 for (_circ
=global_circuitlist
; _circ
; _circ
= _circ
->next
) {
771 if (CIRCUIT_IS_ORIGIN(_circ
) &&
772 _circ
->state
== CIRCUIT_STATE_OPEN
&&
773 !_circ
->marked_for_close
&&
774 _circ
->purpose
== purpose
&&
775 !_circ
->timestamp_dirty
) {
776 origin_circuit_t
*circ
= TO_ORIGIN_CIRCUIT(_circ
);
777 if ((!need_uptime
|| circ
->build_state
->need_uptime
) &&
778 (!need_capacity
|| circ
->build_state
->need_capacity
) &&
779 (internal
== circ
->build_state
->is_internal
)) {
781 /* need to make sure we don't duplicate hops */
782 crypt_path_t
*hop
= circ
->cpath
;
784 if (!memcmp(hop
->extend_info
->identity_digest
,
785 info
->identity_digest
, DIGEST_LEN
))
788 } while (hop
!=circ
->cpath
);
790 if (!best
|| (best
->build_state
->need_uptime
&& !need_uptime
))
799 /** Return the number of hops in circuit's path. */
801 circuit_get_cpath_len(origin_circuit_t
*circ
)
804 if (circ
&& circ
->cpath
) {
805 crypt_path_t
*cpath
, *cpath_next
= NULL
;
806 for (cpath
= circ
->cpath
; cpath_next
!= circ
->cpath
; cpath
= cpath_next
) {
807 cpath_next
= cpath
->next
;
814 /** Go through the circuitlist; mark-for-close each circuit that starts
815 * at us but has not yet been used. */
817 circuit_mark_all_unused_circs(void)
821 for (circ
=global_circuitlist
; circ
; circ
= circ
->next
) {
822 if (CIRCUIT_IS_ORIGIN(circ
) &&
823 !circ
->marked_for_close
&&
824 !circ
->timestamp_dirty
)
825 circuit_mark_for_close(circ
, END_CIRC_REASON_FINISHED
);
829 /** Go through the circuitlist; for each circuit that starts at us
830 * and is dirty, frob its timestamp_dirty so we won't use it for any
833 * This is useful for letting the user change pseudonyms, so new
834 * streams will not be linkable to old streams.
837 circuit_expire_all_dirty_circs(void)
840 or_options_t
*options
= get_options();
842 for (circ
=global_circuitlist
; circ
; circ
= circ
->next
) {
843 if (CIRCUIT_IS_ORIGIN(circ
) &&
844 !circ
->marked_for_close
&&
845 circ
->timestamp_dirty
)
846 circ
->timestamp_dirty
-= options
->MaxCircuitDirtiness
;
850 /** Mark <b>circ</b> to be closed next time we call
851 * circuit_close_all_marked(). Do any cleanup needed:
852 * - If state is onionskin_pending, remove circ from the onion_pending
854 * - If circ isn't open yet: call circuit_build_failed() if we're
855 * the origin, and in either case call circuit_rep_hist_note_result()
857 * - If purpose is C_INTRODUCE_ACK_WAIT, remove the intro point we
858 * just tried from our list of intro points for that service
860 * - Send appropriate destroys and edge_destroys for conns and
861 * streams attached to circ.
862 * - If circ->rend_splice is set (we are the midpoint of a joined
863 * rendezvous stream), then mark the other circuit to close as well.
866 _circuit_mark_for_close(circuit_t
*circ
, int reason
, int line
,
869 int orig_reason
= reason
; /* Passed to the controller */
870 assert_circuit_ok(circ
);
874 if (circ
->marked_for_close
) {
876 "Duplicate call to circuit_mark_for_close at %s:%d"
877 " (first at %s:%d)", file
, line
,
878 circ
->marked_for_close_file
, circ
->marked_for_close
);
881 if (reason
== END_CIRC_AT_ORIGIN
) {
882 if (!CIRCUIT_IS_ORIGIN(circ
)) {
883 log_warn(LD_BUG
, "Specified 'at-origin' non-reason for ending circuit, "
884 "but circuit was not at origin. (called %s:%d, purpose=%d)",
885 file
, line
, circ
->purpose
);
887 reason
= END_CIRC_REASON_NONE
;
888 } else if (CIRCUIT_IS_ORIGIN(circ
) && reason
< _END_CIRC_REASON_MIN
) {
889 /* We don't send reasons when closing circuits at the origin, but we want
890 * to track them anyway so we can give them to the controller. */
891 reason
= END_CIRC_REASON_NONE
;
894 if (reason
& END_CIRC_REASON_FLAG_REMOTE
)
895 reason
&= ~END_CIRC_REASON_FLAG_REMOTE
;
897 if (reason
< _END_CIRC_REASON_MIN
|| reason
> _END_CIRC_REASON_MAX
) {
898 if (!(orig_reason
& END_CIRC_REASON_FLAG_REMOTE
))
899 log_warn(LD_BUG
, "Reason %d out of range at %s:%d", reason
, file
, line
);
900 reason
= END_CIRC_REASON_NONE
;
903 if (circ
->state
== CIRCUIT_STATE_ONIONSKIN_PENDING
) {
904 onion_pending_remove(TO_OR_CIRCUIT(circ
));
906 /* If the circuit ever became OPEN, we sent it to the reputation history
907 * module then. If it isn't OPEN, we send it there now to remember which
908 * links worked and which didn't.
910 if (circ
->state
!= CIRCUIT_STATE_OPEN
) {
911 if (CIRCUIT_IS_ORIGIN(circ
)) {
912 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
913 circuit_build_failed(ocirc
); /* take actions if necessary */
914 circuit_rep_hist_note_result(ocirc
);
917 if (circ
->state
== CIRCUIT_STATE_OR_WAIT
) {
918 if (circuits_pending_or_conns
)
919 smartlist_remove(circuits_pending_or_conns
, circ
);
921 if (CIRCUIT_IS_ORIGIN(circ
)) {
922 control_event_circuit_status(TO_ORIGIN_CIRCUIT(circ
),
923 (circ
->state
== CIRCUIT_STATE_OPEN
)?CIRC_EVENT_CLOSED
:CIRC_EVENT_FAILED
,
926 if (circ
->purpose
== CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
) {
927 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
928 tor_assert(circ
->state
== CIRCUIT_STATE_OPEN
);
929 tor_assert(ocirc
->build_state
->chosen_exit
);
930 /* treat this like getting a nack from it */
931 log_info(LD_REND
, "Failed intro circ %s to %s (awaiting ack). "
932 "Removing from descriptor.",
933 safe_str(ocirc
->rend_query
),
934 safe_str(build_state_get_exit_nickname(ocirc
->build_state
)));
935 rend_client_remove_intro_point(ocirc
->build_state
->chosen_exit
,
939 connection_or_send_destroy(circ
->n_circ_id
, circ
->n_conn
, reason
);
941 if (! CIRCUIT_IS_ORIGIN(circ
)) {
942 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
943 edge_connection_t
*conn
;
944 for (conn
=or_circ
->n_streams
; conn
; conn
=conn
->next_stream
)
945 connection_edge_destroy(or_circ
->p_circ_id
, conn
);
947 while (or_circ
->resolving_streams
) {
948 conn
= or_circ
->resolving_streams
;
949 or_circ
->resolving_streams
= conn
->next_stream
;
950 if (!conn
->_base
.marked_for_close
) {
951 /* The other side will see a DESTROY, and infer that the connections
952 * are closing because the circuit is getting torn down. No need
953 * to send an end cell. */
954 conn
->_base
.edge_has_sent_end
= 1;
955 conn
->end_reason
= END_STREAM_REASON_DESTROY
;
956 connection_mark_for_close(TO_CONN(conn
));
958 conn
->on_circuit
= NULL
;
962 connection_or_send_destroy(or_circ
->p_circ_id
, or_circ
->p_conn
, reason
);
964 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
965 edge_connection_t
*conn
;
966 for (conn
=ocirc
->p_streams
; conn
; conn
=conn
->next_stream
)
967 connection_edge_destroy(circ
->n_circ_id
, conn
);
970 circ
->marked_for_close
= line
;
971 circ
->marked_for_close_file
= file
;
973 if (! CIRCUIT_IS_ORIGIN(circ
)) {
974 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
975 if (or_circ
->rend_splice
) {
976 if (!or_circ
->rend_splice
->_base
.marked_for_close
) {
977 /* do this after marking this circuit, to avoid infinite recursion. */
978 circuit_mark_for_close(TO_CIRCUIT(or_circ
->rend_splice
), reason
);
980 or_circ
->rend_splice
= NULL
;
985 /** Verify that cpath layer <b>cp</b> has all of its invariants
986 * correct. Trigger an assert if anything is invalid.
989 assert_cpath_layer_ok(const crypt_path_t
*cp
)
991 // tor_assert(cp->addr); /* these are zero for rendezvous extra-hops */
992 // tor_assert(cp->port);
994 tor_assert(cp
->magic
== CRYPT_PATH_MAGIC
);
997 case CPATH_STATE_OPEN
:
998 tor_assert(cp
->f_crypto
);
999 tor_assert(cp
->b_crypto
);
1001 case CPATH_STATE_CLOSED
:
1002 tor_assert(!cp
->dh_handshake_state
);
1004 case CPATH_STATE_AWAITING_KEYS
:
1005 /* tor_assert(cp->dh_handshake_state); */
1008 log_fn(LOG_ERR
, LD_BUG
, "Unexpected state %d", cp
->state
);
1011 tor_assert(cp
->package_window
>= 0);
1012 tor_assert(cp
->deliver_window
>= 0);
1015 /** Verify that cpath <b>cp</b> has all of its invariants
1016 * correct. Trigger an assert if anything is invalid.
1019 assert_cpath_ok(const crypt_path_t
*cp
)
1021 const crypt_path_t
*start
= cp
;
1024 assert_cpath_layer_ok(cp
);
1025 /* layers must be in sequence of: "open* awaiting? closed*" */
1027 if (cp
->state
== CPATH_STATE_AWAITING_KEYS
) {
1028 tor_assert(cp
->prev
->state
== CPATH_STATE_OPEN
);
1029 } else if (cp
->state
== CPATH_STATE_OPEN
) {
1030 tor_assert(cp
->prev
->state
== CPATH_STATE_OPEN
);
1035 } while (cp
!= start
);
1038 /** Verify that circuit <b>c</b> has all of its invariants
1039 * correct. Trigger an assert if anything is invalid.
1042 assert_circuit_ok(const circuit_t
*c
)
1044 edge_connection_t
*conn
;
1045 const or_circuit_t
*or_circ
= NULL
;
1046 const origin_circuit_t
*origin_circ
= NULL
;
1049 tor_assert(c
->magic
== ORIGIN_CIRCUIT_MAGIC
|| c
->magic
== OR_CIRCUIT_MAGIC
);
1050 tor_assert(c
->purpose
>= _CIRCUIT_PURPOSE_MIN
&&
1051 c
->purpose
<= _CIRCUIT_PURPOSE_MAX
);
1053 if (CIRCUIT_IS_ORIGIN(c
))
1054 origin_circ
= TO_ORIGIN_CIRCUIT((circuit_t
*)c
);
1056 or_circ
= TO_OR_CIRCUIT((circuit_t
*)c
);
1059 tor_assert(!memcmp(c
->n_conn
->identity_digest
, c
->n_conn_id_digest
,
1062 tor_assert(c
== circuit_get_by_circid_orconn(c
->n_circ_id
, c
->n_conn
));
1064 if (or_circ
&& or_circ
->p_conn
) {
1065 if (or_circ
->p_circ_id
)
1066 tor_assert(c
== circuit_get_by_circid_orconn(or_circ
->p_circ_id
,
1069 #if 0 /* false now that rendezvous exits are attached to p_streams */
1071 for (conn
= origin_circ
->p_streams
; conn
; conn
= conn
->next_stream
)
1072 tor_assert(conn
->_base
.type
== CONN_TYPE_AP
);
1075 for (conn
= or_circ
->n_streams
; conn
; conn
= conn
->next_stream
)
1076 tor_assert(conn
->_base
.type
== CONN_TYPE_EXIT
);
1078 tor_assert(c
->deliver_window
>= 0);
1079 tor_assert(c
->package_window
>= 0);
1080 if (c
->state
== CIRCUIT_STATE_OPEN
) {
1081 tor_assert(!c
->onionskin
);
1083 tor_assert(or_circ
->n_crypto
);
1084 tor_assert(or_circ
->p_crypto
);
1085 tor_assert(or_circ
->n_digest
);
1086 tor_assert(or_circ
->p_digest
);
1089 if (c
->state
== CIRCUIT_STATE_OR_WAIT
&& !c
->marked_for_close
) {
1090 tor_assert(circuits_pending_or_conns
&&
1091 smartlist_isin(circuits_pending_or_conns
, c
));
1093 tor_assert(!circuits_pending_or_conns
||
1094 !smartlist_isin(circuits_pending_or_conns
, c
));
1096 if (origin_circ
&& origin_circ
->cpath
) {
1097 assert_cpath_ok(origin_circ
->cpath
);
1099 if (c
->purpose
== CIRCUIT_PURPOSE_REND_ESTABLISHED
) {
1100 tor_assert(or_circ
);
1101 if (!c
->marked_for_close
) {
1102 tor_assert(or_circ
->rend_splice
);
1103 tor_assert(or_circ
->rend_splice
->rend_splice
== or_circ
);
1105 tor_assert(or_circ
->rend_splice
!= or_circ
);
1107 tor_assert(!or_circ
|| !or_circ
->rend_splice
);