1 /* Copyright 2001 Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2007, 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
;
51 /** Helper: return a hash based on circuit ID and the pointer value of
52 * or_conn in <b>a</b>. */
53 static INLINE
unsigned int
54 _orconn_circid_entry_hash(orconn_circid_circuit_map_t
*a
)
56 return (((unsigned)a
->circ_id
)<<16) ^ (unsigned)(uintptr_t)(a
->or_conn
);
59 /** Map from [orconn,circid] to circuit. */
60 static HT_HEAD(orconn_circid_map
, orconn_circid_circuit_map_t
)
61 orconn_circid_circuit_map
= HT_INITIALIZER();
62 HT_PROTOTYPE(orconn_circid_map
, orconn_circid_circuit_map_t
, node
,
63 _orconn_circid_entry_hash
, _orconn_circid_entries_eq
);
64 HT_GENERATE(orconn_circid_map
, orconn_circid_circuit_map_t
, node
,
65 _orconn_circid_entry_hash
, _orconn_circid_entries_eq
, 0.6,
66 malloc
, realloc
, free
);
68 /** The most recently returned entry from circuit_get_by_circid_orconn;
69 * used to improve performance when many cells arrive in a row from the
72 orconn_circid_circuit_map_t
*_last_circid_orconn_ent
= NULL
;
75 circuit_set_circid_orconn_helper(circuit_t
*circ
, uint16_t id
,
76 or_connection_t
*conn
,
77 uint16_t old_id
, or_connection_t
*old_conn
)
79 orconn_circid_circuit_map_t search
;
80 orconn_circid_circuit_map_t
*found
;
82 if (_last_circid_orconn_ent
&&
83 ((old_id
== _last_circid_orconn_ent
->circ_id
&&
84 old_conn
== _last_circid_orconn_ent
->or_conn
) ||
85 (id
== _last_circid_orconn_ent
->circ_id
&&
86 conn
== _last_circid_orconn_ent
->or_conn
))) {
87 _last_circid_orconn_ent
= NULL
;
90 if (old_conn
) { /* we may need to remove it from the conn-circid map */
91 tor_assert(old_conn
->_base
.magic
== OR_CONNECTION_MAGIC
);
92 search
.circ_id
= old_id
;
93 search
.or_conn
= old_conn
;
94 found
= HT_REMOVE(orconn_circid_map
, &orconn_circid_circuit_map
, &search
);
97 --old_conn
->n_circuits
;
104 /* now add the new one to the conn-circid map */
106 search
.or_conn
= conn
;
107 found
= HT_FIND(orconn_circid_map
, &orconn_circid_circuit_map
, &search
);
109 found
->circuit
= circ
;
111 found
= tor_malloc_zero(sizeof(orconn_circid_circuit_map_t
));
113 found
->or_conn
= conn
;
114 found
->circuit
= circ
;
115 HT_INSERT(orconn_circid_map
, &orconn_circid_circuit_map
, found
);
120 /** Set the p_conn field of a circuit <b>circ</b>, along
121 * with the corresponding circuit ID, and add the circuit as appropriate
122 * to the (orconn,id)-\>circuit map. */
124 circuit_set_p_circid_orconn(or_circuit_t
*circ
, uint16_t id
,
125 or_connection_t
*conn
)
128 or_connection_t
*old_conn
;
130 old_id
= circ
->p_circ_id
;
131 old_conn
= circ
->p_conn
;
132 circ
->p_circ_id
= id
;
135 if (id
== old_id
&& conn
== old_conn
)
137 circuit_set_circid_orconn_helper(TO_CIRCUIT(circ
), id
, conn
,
141 /** Set the n_conn field of a circuit <b>circ</b>, along
142 * with the corresponding circuit ID, and add the circuit as appropriate
143 * to the (orconn,id)-\>circuit map. */
145 circuit_set_n_circid_orconn(circuit_t
*circ
, uint16_t id
,
146 or_connection_t
*conn
)
149 or_connection_t
*old_conn
;
151 old_id
= circ
->n_circ_id
;
152 old_conn
= circ
->n_conn
;
153 circ
->n_circ_id
= id
;
156 if (id
== old_id
&& conn
== old_conn
)
158 circuit_set_circid_orconn_helper(circ
, id
, conn
, old_id
, old_conn
);
161 /** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
162 * it from lists as appropriate. */
164 circuit_set_state(circuit_t
*circ
, int state
)
167 if (state
== circ
->state
)
169 if (!circuits_pending_or_conns
)
170 circuits_pending_or_conns
= smartlist_create();
171 if (circ
->state
== CIRCUIT_STATE_OR_WAIT
) {
172 /* remove from waiting-circuit list. */
173 smartlist_remove(circuits_pending_or_conns
, circ
);
175 if (state
== CIRCUIT_STATE_OR_WAIT
) {
176 /* add to waiting-circuit list. */
177 smartlist_add(circuits_pending_or_conns
, circ
);
182 /** Add <b>circ</b> to the global list of circuits. This is called only from
183 * within circuit_new.
186 circuit_add(circuit_t
*circ
)
188 if (!global_circuitlist
) { /* first one */
189 global_circuitlist
= circ
;
192 circ
->next
= global_circuitlist
;
193 global_circuitlist
= circ
;
197 /** Append to <b>out</b> the number of circuits in state OR_WAIT, waiting for
198 * the given connection. */
200 circuit_get_all_pending_on_or_conn(smartlist_t
*out
, or_connection_t
*or_conn
)
205 if (!circuits_pending_or_conns
)
208 SMARTLIST_FOREACH(circuits_pending_or_conns
, circuit_t
*, circ
,
210 if (circ
->marked_for_close
)
212 tor_assert(circ
->state
== CIRCUIT_STATE_OR_WAIT
);
214 !memcmp(or_conn
->identity_digest
, circ
->n_conn_id_digest
,
216 smartlist_add(out
, circ
);
221 /** Return the number of circuits in state OR_WAIT, waiting for the given
224 circuit_count_pending_on_or_conn(or_connection_t
*or_conn
)
227 smartlist_t
*sl
= smartlist_create();
228 circuit_get_all_pending_on_or_conn(sl
, or_conn
);
229 cnt
= smartlist_len(sl
);
231 log_debug(LD_CIRC
,"or_conn to %s, %d pending circs",
232 or_conn
->nickname
? or_conn
->nickname
: "NULL", cnt
);
236 /** Detach from the global circuit list, and deallocate, all
237 * circuits that have been marked for close.
240 circuit_close_all_marked(void)
244 while (global_circuitlist
&& global_circuitlist
->marked_for_close
) {
245 tmp
= global_circuitlist
->next
;
246 circuit_free(global_circuitlist
);
247 global_circuitlist
= tmp
;
250 tmp
= global_circuitlist
;
251 while (tmp
&& tmp
->next
) {
252 if (tmp
->next
->marked_for_close
) {
254 circuit_free(tmp
->next
);
256 /* Need to check new tmp->next; don't advance tmp. */
264 /** Return the head of the global linked list of circuits. */
266 _circuit_get_global_list(void)
268 return global_circuitlist
;
271 /** Function to make circ-\>state human-readable */
273 circuit_state_to_string(int state
)
277 case CIRCUIT_STATE_BUILDING
: return "doing handshakes";
278 case CIRCUIT_STATE_ONIONSKIN_PENDING
: return "processing the onion";
279 case CIRCUIT_STATE_OR_WAIT
: return "connecting to server";
280 case CIRCUIT_STATE_OPEN
: return "open";
282 log_warn(LD_BUG
, "Bug: unknown circuit state %d", state
);
283 tor_snprintf(buf
, sizeof(buf
), "unknown state [%d]", state
);
288 /** Initialize the common elements in a circuit_t, and add it to the global
291 init_circuit_base(circuit_t
*circ
)
293 circ
->timestamp_created
= time(NULL
);
295 circ
->package_window
= CIRCWINDOW_START
;
296 circ
->deliver_window
= CIRCWINDOW_START
;
301 /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
302 * and <b>p_conn</b>. Add it to the global circuit list.
305 origin_circuit_new(void)
307 origin_circuit_t
*circ
;
308 /* never zero, since a global ID of 0 is treated specially by the
310 static uint32_t n_circuits_allocated
= 1;
312 circ
= tor_malloc_zero(sizeof(origin_circuit_t
));
313 circ
->_base
.magic
= ORIGIN_CIRCUIT_MAGIC
;
315 circ
->next_stream_id
= crypto_rand_int(1<<16);
316 circ
->global_identifier
= n_circuits_allocated
++;
318 init_circuit_base(TO_CIRCUIT(circ
));
323 /** Allocate a new or_circuit_t, connected to <b>p_conn</b> as
324 * <b>p_circ_id</b>. If <b>p_conn</b> is NULL, the circuit is unattached. */
326 or_circuit_new(uint16_t p_circ_id
, or_connection_t
*p_conn
)
331 circ
= tor_malloc_zero(sizeof(or_circuit_t
));
332 circ
->_base
.magic
= OR_CIRCUIT_MAGIC
;
335 circuit_set_p_circid_orconn(circ
, p_circ_id
, p_conn
);
337 init_circuit_base(TO_CIRCUIT(circ
));
342 /** Deallocate space associated with circ.
345 circuit_free(circuit_t
*circ
)
349 if (CIRCUIT_IS_ORIGIN(circ
)) {
350 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
352 tor_assert(circ
->magic
== ORIGIN_CIRCUIT_MAGIC
);
353 if (ocirc
->build_state
) {
354 if (ocirc
->build_state
->chosen_exit
)
355 extend_info_free(ocirc
->build_state
->chosen_exit
);
356 if (ocirc
->build_state
->pending_final_cpath
)
357 circuit_free_cpath_node(ocirc
->build_state
->pending_final_cpath
);
359 tor_free(ocirc
->build_state
);
361 circuit_free_cpath(ocirc
->cpath
);
364 or_circuit_t
*ocirc
= TO_OR_CIRCUIT(circ
);
366 tor_assert(circ
->magic
== OR_CIRCUIT_MAGIC
);
369 crypto_free_cipher_env(ocirc
->p_crypto
);
371 crypto_free_digest_env(ocirc
->p_digest
);
373 crypto_free_cipher_env(ocirc
->n_crypto
);
375 crypto_free_digest_env(ocirc
->n_digest
);
377 if (ocirc
->rend_splice
) {
378 or_circuit_t
*other
= ocirc
->rend_splice
;
379 tor_assert(other
->_base
.magic
== OR_CIRCUIT_MAGIC
);
380 other
->rend_splice
= NULL
;
383 tor_free(circ
->onionskin
);
385 /* remove from map. */
386 circuit_set_p_circid_orconn(ocirc
, 0, NULL
);
389 /* Remove from map. */
390 circuit_set_n_circid_orconn(circ
, 0, NULL
);
392 memset(circ
, 0xAA, sizeof(circuit_t
)); /* poison memory */
396 /** Deallocate space associated with the linked list <b>cpath</b>. */
398 circuit_free_cpath(crypt_path_t
*cpath
)
400 crypt_path_t
*victim
, *head
=cpath
;
405 /* it's a doubly linked list, so we have to notice when we've
406 * gone through it once. */
407 while (cpath
->next
&& cpath
->next
!= head
) {
409 cpath
= victim
->next
;
410 circuit_free_cpath_node(victim
);
413 circuit_free_cpath_node(cpath
);
416 /** Release all storage held by circuits. */
418 circuit_free_all(void)
421 while (global_circuitlist
) {
422 next
= global_circuitlist
->next
;
423 if (! CIRCUIT_IS_ORIGIN(global_circuitlist
)) {
424 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(global_circuitlist
);
425 while (or_circ
->resolving_streams
) {
426 edge_connection_t
*next
;
427 next
= or_circ
->resolving_streams
->next_stream
;
428 connection_free(TO_CONN(or_circ
->resolving_streams
));
429 or_circ
->resolving_streams
= next
;
432 circuit_free(global_circuitlist
);
433 global_circuitlist
= next
;
435 if (circuits_pending_or_conns
) {
436 smartlist_free(circuits_pending_or_conns
);
437 circuits_pending_or_conns
= NULL
;
439 HT_CLEAR(orconn_circid_map
, &orconn_circid_circuit_map
);
442 /** Deallocate space associated with the cpath node <b>victim</b>. */
444 circuit_free_cpath_node(crypt_path_t
*victim
)
446 if (victim
->f_crypto
)
447 crypto_free_cipher_env(victim
->f_crypto
);
448 if (victim
->b_crypto
)
449 crypto_free_cipher_env(victim
->b_crypto
);
450 if (victim
->f_digest
)
451 crypto_free_digest_env(victim
->f_digest
);
452 if (victim
->b_digest
)
453 crypto_free_digest_env(victim
->b_digest
);
454 if (victim
->dh_handshake_state
)
455 crypto_dh_free(victim
->dh_handshake_state
);
456 if (victim
->extend_info
)
457 extend_info_free(victim
->extend_info
);
459 victim
->magic
= 0xDEADBEEFu
;
463 /** A helper function for circuit_dump_by_conn() below. Log a bunch
464 * of information about circuit <b>circ</b>.
467 circuit_dump_details(int severity
, circuit_t
*circ
, int conn_array_index
,
468 const char *type
, int this_circid
, int other_circid
)
470 log(severity
, LD_CIRC
, "Conn %d has %s circuit: circID %d (other side %d), "
471 "state %d (%s), born %d:",
472 conn_array_index
, type
, this_circid
, other_circid
, circ
->state
,
473 circuit_state_to_string(circ
->state
), (int)circ
->timestamp_created
);
474 if (CIRCUIT_IS_ORIGIN(circ
)) { /* circ starts at this node */
475 circuit_log_path(severity
, LD_CIRC
, TO_ORIGIN_CIRCUIT(circ
));
479 /** Log, at severity <b>severity</b>, information about each circuit
480 * that is connected to <b>conn</b>.
483 circuit_dump_by_conn(connection_t
*conn
, int severity
)
486 edge_connection_t
*tmpconn
;
488 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
489 circid_t n_circ_id
= circ
->n_circ_id
, p_circ_id
= 0;
490 if (circ
->marked_for_close
)
493 if (! CIRCUIT_IS_ORIGIN(circ
))
494 p_circ_id
= TO_OR_CIRCUIT(circ
)->p_circ_id
;
496 if (! CIRCUIT_IS_ORIGIN(circ
) && TO_OR_CIRCUIT(circ
)->p_conn
&&
497 TO_CONN(TO_OR_CIRCUIT(circ
)->p_conn
) == conn
)
498 circuit_dump_details(severity
, circ
, conn
->conn_array_index
, "App-ward",
499 p_circ_id
, n_circ_id
);
500 if (CIRCUIT_IS_ORIGIN(circ
)) {
501 for (tmpconn
=TO_ORIGIN_CIRCUIT(circ
)->p_streams
; tmpconn
;
502 tmpconn
=tmpconn
->next_stream
) {
503 if (TO_CONN(tmpconn
) == conn
) {
504 circuit_dump_details(severity
, circ
, conn
->conn_array_index
,
505 "App-ward", p_circ_id
, n_circ_id
);
509 if (circ
->n_conn
&& TO_CONN(circ
->n_conn
) == conn
)
510 circuit_dump_details(severity
, circ
, conn
->conn_array_index
, "Exit-ward",
511 n_circ_id
, p_circ_id
);
512 if (! CIRCUIT_IS_ORIGIN(circ
)) {
513 for (tmpconn
=TO_OR_CIRCUIT(circ
)->n_streams
; tmpconn
;
514 tmpconn
=tmpconn
->next_stream
) {
515 if (TO_CONN(tmpconn
) == conn
) {
516 circuit_dump_details(severity
, circ
, conn
->conn_array_index
,
517 "Exit-ward", n_circ_id
, p_circ_id
);
521 if (!circ
->n_conn
&& circ
->n_addr
&& circ
->n_port
&&
522 circ
->n_addr
== conn
->addr
&&
523 circ
->n_port
== conn
->port
&&
524 conn
->type
== CONN_TYPE_OR
&&
525 !memcmp(TO_OR_CONN(conn
)->identity_digest
, circ
->n_conn_id_digest
,
527 circuit_dump_details(severity
, circ
, conn
->conn_array_index
,
528 (circ
->state
== CIRCUIT_STATE_OPEN
&&
529 !CIRCUIT_IS_ORIGIN(circ
)) ?
530 "Endpoint" : "Pending",
531 n_circ_id
, p_circ_id
);
536 /** Return the circuit whose global ID is <b>id</b>, or NULL if no
537 * such circuit exists. */
539 circuit_get_by_global_id(uint32_t id
)
542 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
543 if (CIRCUIT_IS_ORIGIN(circ
) &&
544 TO_ORIGIN_CIRCUIT(circ
)->global_identifier
== id
) {
545 if (circ
->marked_for_close
)
548 return TO_ORIGIN_CIRCUIT(circ
);
554 /** Return a circ such that:
555 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
556 * - circ is attached to <b>conn</b>, either as p_conn or n_conn.
557 * Return NULL if no such circuit exists.
559 static INLINE circuit_t
*
560 circuit_get_by_circid_orconn_impl(uint16_t circ_id
, or_connection_t
*conn
)
562 orconn_circid_circuit_map_t search
;
563 orconn_circid_circuit_map_t
*found
;
565 if (_last_circid_orconn_ent
&&
566 circ_id
== _last_circid_orconn_ent
->circ_id
&&
567 conn
== _last_circid_orconn_ent
->or_conn
) {
568 found
= _last_circid_orconn_ent
;
570 search
.circ_id
= circ_id
;
571 search
.or_conn
= conn
;
572 found
= HT_FIND(orconn_circid_map
, &orconn_circid_circuit_map
, &search
);
573 _last_circid_orconn_ent
= found
;
575 if (found
&& found
->circuit
)
576 return found
->circuit
;
580 /* The rest of this checks for bugs. Disabled by default. */
583 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
584 if (! CIRCUIT_IS_ORIGIN(circ
)) {
585 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
586 if (or_circ
->p_conn
== conn
&& or_circ
->p_circ_id
== circ_id
) {
588 "circuit matches p_conn, but not in hash table (Bug!)");
592 if (circ
->n_conn
== conn
&& circ
->n_circ_id
== circ_id
) {
594 "circuit matches n_conn, but not in hash table (Bug!)");
602 /** Return a circ such that:
603 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
604 * - circ is attached to <b>conn</b>, either as p_conn or n_conn.
605 * - circ is not marked for close.
606 * Return NULL if no such circuit exists.
609 circuit_get_by_circid_orconn(uint16_t circ_id
, or_connection_t
*conn
)
611 circuit_t
*circ
= circuit_get_by_circid_orconn_impl(circ_id
, conn
);
612 if (!circ
|| circ
->marked_for_close
)
618 /** Return the circuit that a given edge connection is using. */
620 circuit_get_by_edge_conn(edge_connection_t
*conn
)
624 circ
= conn
->on_circuit
;
626 (CIRCUIT_IS_ORIGIN(circ
) ? circ
->magic
== ORIGIN_CIRCUIT_MAGIC
627 : circ
->magic
== OR_CIRCUIT_MAGIC
));
632 /** For each circuit that has <b>conn</b> as n_conn or p_conn, unlink the
633 * circuit from the orconn,circid map, and mark it for close if it hasn't
634 * been marked already.
637 circuit_unlink_all_from_or_conn(or_connection_t
*conn
, int reason
)
640 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
642 if (circ
->n_conn
== conn
) {
643 circuit_set_n_circid_orconn(circ
, 0, NULL
);
646 if (! CIRCUIT_IS_ORIGIN(circ
)) {
647 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
648 if (or_circ
->p_conn
== conn
) {
649 circuit_set_p_circid_orconn(or_circ
, 0, NULL
);
653 if (mark
&& !circ
->marked_for_close
)
654 circuit_mark_for_close(circ
, reason
);
658 /** Return a circ such that:
659 * - circ-\>rend_query is equal to <b>rend_query</b>, and
660 * - circ-\>purpose is equal to <b>purpose</b>.
662 * Return NULL if no such circuit exists.
665 circuit_get_by_rend_query_and_purpose(const char *rend_query
, uint8_t purpose
)
669 tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose
));
671 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
672 if (!circ
->marked_for_close
&&
673 circ
->purpose
== purpose
&&
674 !rend_cmp_service_ids(rend_query
, TO_ORIGIN_CIRCUIT(circ
)->rend_query
))
675 return TO_ORIGIN_CIRCUIT(circ
);
680 /** Return the first circuit originating here in global_circuitlist after
681 * <b>start</b> whose purpose is <b>purpose</b>, and where
682 * <b>digest</b> (if set) matches the rend_pk_digest field. Return NULL if no
683 * circuit is found. If <b>start</b> is NULL, begin at the start of the list.
686 circuit_get_next_by_pk_and_purpose(origin_circuit_t
*start
,
687 const char *digest
, uint8_t purpose
)
690 tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose
));
692 circ
= global_circuitlist
;
694 circ
= TO_CIRCUIT(start
)->next
;
696 for ( ; circ
; circ
= circ
->next
) {
697 if (circ
->marked_for_close
)
699 if (circ
->purpose
!= purpose
)
702 return TO_ORIGIN_CIRCUIT(circ
);
703 else if (!memcmp(TO_ORIGIN_CIRCUIT(circ
)->rend_pk_digest
,
705 return TO_ORIGIN_CIRCUIT(circ
);
710 /** Return the first OR circuit in the global list whose purpose is
711 * <b>purpose</b>, and whose rend_token is the <b>len</b>-byte
713 static or_circuit_t
*
714 circuit_get_by_rend_token_and_purpose(uint8_t purpose
, const char *token
,
718 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
719 if (! circ
->marked_for_close
&&
720 circ
->purpose
== purpose
&&
721 ! memcmp(TO_OR_CIRCUIT(circ
)->rend_token
, token
, len
))
722 return TO_OR_CIRCUIT(circ
);
727 /** Return the circuit waiting for a rendezvous with the provided cookie.
728 * Return NULL if no such circuit is found.
731 circuit_get_rendezvous(const char *cookie
)
733 return circuit_get_by_rend_token_and_purpose(
734 CIRCUIT_PURPOSE_REND_POINT_WAITING
,
735 cookie
, REND_COOKIE_LEN
);
738 /** Return the circuit waiting for intro cells of the given digest.
739 * Return NULL if no such circuit is found.
742 circuit_get_intro_point(const char *digest
)
744 return circuit_get_by_rend_token_and_purpose(
745 CIRCUIT_PURPOSE_INTRO_POINT
, digest
,
749 /** Return a circuit that is open, has specified <b>purpose</b>,
750 * has a timestamp_dirty value of 0, is uptime/capacity/internal
751 * if required, and if info is defined, does not already use info
752 * as any of its hops; or NULL if no circuit fits this description.
754 * If ! need_uptime, prefer returning non-uptime circuits.
757 circuit_find_to_cannibalize(uint8_t purpose
, extend_info_t
*info
,
759 int need_capacity
, int internal
)
762 origin_circuit_t
*best
=NULL
;
765 "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
766 "capacity %d, internal %d",
767 purpose
, need_uptime
, need_capacity
, internal
);
769 for (_circ
=global_circuitlist
; _circ
; _circ
= _circ
->next
) {
770 if (CIRCUIT_IS_ORIGIN(_circ
) &&
771 _circ
->state
== CIRCUIT_STATE_OPEN
&&
772 !_circ
->marked_for_close
&&
773 _circ
->purpose
== purpose
&&
774 !_circ
->timestamp_dirty
) {
775 origin_circuit_t
*circ
= TO_ORIGIN_CIRCUIT(_circ
);
776 if ((!need_uptime
|| circ
->build_state
->need_uptime
) &&
777 (!need_capacity
|| circ
->build_state
->need_capacity
) &&
778 (internal
== circ
->build_state
->is_internal
)) {
780 /* need to make sure we don't duplicate hops */
781 crypt_path_t
*hop
= circ
->cpath
;
783 if (!memcmp(hop
->extend_info
->identity_digest
,
784 info
->identity_digest
, DIGEST_LEN
))
787 } while (hop
!=circ
->cpath
);
789 if (!best
|| (best
->build_state
->need_uptime
&& !need_uptime
))
798 /** Return the number of hops in circuit's path. */
800 circuit_get_cpath_len(origin_circuit_t
*circ
)
803 if (circ
&& circ
->cpath
) {
804 crypt_path_t
*cpath
, *cpath_next
= NULL
;
805 for (cpath
= circ
->cpath
; cpath_next
!= circ
->cpath
; cpath
= cpath_next
) {
806 cpath_next
= cpath
->next
;
813 /** Go through the circuitlist; mark-for-close each circuit that starts
814 * at us but has not yet been used. */
816 circuit_mark_all_unused_circs(void)
820 for (circ
=global_circuitlist
; circ
; circ
= circ
->next
) {
821 if (CIRCUIT_IS_ORIGIN(circ
) &&
822 !circ
->marked_for_close
&&
823 !circ
->timestamp_dirty
)
824 circuit_mark_for_close(circ
, END_CIRC_REASON_FINISHED
);
828 /** Go through the circuitlist; for each circuit that starts at us
829 * and is dirty, frob its timestamp_dirty so we won't use it for any
832 * This is useful for letting the user change pseudonyms, so new
833 * streams will not be linkable to old streams.
836 circuit_expire_all_dirty_circs(void)
839 or_options_t
*options
= get_options();
841 for (circ
=global_circuitlist
; circ
; circ
= circ
->next
) {
842 if (CIRCUIT_IS_ORIGIN(circ
) &&
843 !circ
->marked_for_close
&&
844 circ
->timestamp_dirty
)
845 circ
->timestamp_dirty
-= options
->MaxCircuitDirtiness
;
849 /** Mark <b>circ</b> to be closed next time we call
850 * circuit_close_all_marked(). Do any cleanup needed:
851 * - If state is onionskin_pending, remove circ from the onion_pending
853 * - If circ isn't open yet: call circuit_build_failed() if we're
854 * the origin, and in either case call circuit_rep_hist_note_result()
856 * - If purpose is C_INTRODUCE_ACK_WAIT, remove the intro point we
857 * just tried from our list of intro points for that service
859 * - Send appropriate destroys and edge_destroys for conns and
860 * streams attached to circ.
861 * - If circ->rend_splice is set (we are the midpoint of a joined
862 * rendezvous stream), then mark the other circuit to close as well.
865 _circuit_mark_for_close(circuit_t
*circ
, int reason
, int line
,
868 int orig_reason
= reason
; /* Passed to the controller */
869 assert_circuit_ok(circ
);
873 if (circ
->marked_for_close
) {
875 "Duplicate call to circuit_mark_for_close at %s:%d"
876 " (first at %s:%d)", file
, line
,
877 circ
->marked_for_close_file
, circ
->marked_for_close
);
880 if (reason
== END_CIRC_AT_ORIGIN
) {
881 if (!CIRCUIT_IS_ORIGIN(circ
)) {
882 log_warn(LD_BUG
, "Specified 'at-origin' non-reason for ending circuit, "
883 "but circuit was not at origin. (called %s:%d, purpose=%d)",
884 file
, line
, circ
->purpose
);
886 reason
= END_CIRC_REASON_NONE
;
888 if (CIRCUIT_IS_ORIGIN(circ
)) {
889 /* We don't send reasons when closing circuits at the origin. */
890 reason
= END_CIRC_REASON_NONE
;
893 if (reason
& END_CIRC_REASON_FLAG_REMOTE
)
894 reason
&= ~END_CIRC_REASON_FLAG_REMOTE
;
896 if (reason
< _END_CIRC_REASON_MIN
|| reason
> _END_CIRC_REASON_MAX
) {
897 if (!(orig_reason
& END_CIRC_REASON_FLAG_REMOTE
))
898 log_warn(LD_BUG
, "Reason %d out of range at %s:%d", reason
, file
, line
);
899 reason
= END_CIRC_REASON_NONE
;
902 if (circ
->state
== CIRCUIT_STATE_ONIONSKIN_PENDING
) {
903 onion_pending_remove(TO_OR_CIRCUIT(circ
));
905 /* If the circuit ever became OPEN, we sent it to the reputation history
906 * module then. If it isn't OPEN, we send it there now to remember which
907 * links worked and which didn't.
909 if (circ
->state
!= CIRCUIT_STATE_OPEN
) {
910 if (CIRCUIT_IS_ORIGIN(circ
)) {
911 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
912 circuit_build_failed(ocirc
); /* take actions if necessary */
913 circuit_rep_hist_note_result(ocirc
);
916 if (circ
->state
== CIRCUIT_STATE_OR_WAIT
) {
917 if (circuits_pending_or_conns
)
918 smartlist_remove(circuits_pending_or_conns
, circ
);
920 if (CIRCUIT_IS_ORIGIN(circ
)) {
921 control_event_circuit_status(TO_ORIGIN_CIRCUIT(circ
),
922 (circ
->state
== CIRCUIT_STATE_OPEN
)?CIRC_EVENT_CLOSED
:CIRC_EVENT_FAILED
,
925 if (circ
->purpose
== CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
) {
926 origin_circuit_t
*ocirc
= TO_ORIGIN_CIRCUIT(circ
);
927 tor_assert(circ
->state
== CIRCUIT_STATE_OPEN
);
928 tor_assert(ocirc
->build_state
->chosen_exit
);
929 /* treat this like getting a nack from it */
930 log_info(LD_REND
, "Failed intro circ %s to %s (awaiting ack). "
931 "Removing from descriptor.",
932 safe_str(ocirc
->rend_query
),
933 safe_str(build_state_get_exit_nickname(ocirc
->build_state
)));
934 rend_client_remove_intro_point(ocirc
->build_state
->chosen_exit
,
938 connection_or_send_destroy(circ
->n_circ_id
, circ
->n_conn
, reason
);
940 if (! CIRCUIT_IS_ORIGIN(circ
)) {
941 or_circuit_t
*or_circ
= TO_OR_CIRCUIT(circ
);
942 edge_connection_t
*conn
;
943 for (conn
=or_circ
->n_streams
; conn
; conn
=conn
->next_stream
)
944 connection_edge_destroy(or_circ
->p_circ_id
, conn
);
946 while (or_circ
->resolving_streams
) {
947 conn
= or_circ
->resolving_streams
;
948 or_circ
->resolving_streams
= conn
->next_stream
;
949 if (!conn
->_base
.marked_for_close
) {
950 /* The client will see a DESTROY, and infer that the connections
951 * are closing because the circuit is getting torn down. No need
952 * to send an end cell. */
953 conn
->_base
.edge_has_sent_end
= 1;
954 conn
->end_reason
= END_STREAM_REASON_DESTROY
;
955 conn
->end_reason
|= END_STREAM_REASON_FLAG_ALREADY_SENT_CLOSED
;
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
);