1 /* Copyright 2001 Matej Pfajfar, 2001-2004 Roger Dingledine. */
2 /* See LICENSE for licensing information */
7 * \brief Manage circuits and the global circuit list.
12 extern or_options_t options
; /* command-line and config-file options */
14 static int circuit_resume_edge_reading_helper(connection_t
*conn
,
16 crypt_path_t
*layer_hint
);
17 static void circuit_free_cpath_node(crypt_path_t
*victim
);
18 static uint16_t get_unique_circ_id_by_conn(connection_t
*conn
, int circ_id_type
);
19 static void circuit_rep_hist_note_result(circuit_t
*circ
);
21 void circuit_expire_old_circuits(void);
22 static void circuit_is_open(circuit_t
*circ
);
23 static void circuit_build_failed(circuit_t
*circ
);
24 static circuit_t
*circuit_establish_circuit(uint8_t purpose
, const char *exit_nickname
);
25 static void circuit_free(circuit_t
*circ
);
26 static void circuit_free_cpath(crypt_path_t
*cpath
);
28 /********* START VARIABLES **********/
30 /** A global (within this file) list of all circuits at this hop. */
31 static circuit_t
*global_circuitlist
=NULL
;
32 /** How many entries are in global_circuitlist? */
33 static int circuitlist_len
=0;
34 /** Array of strings to make circ-\>state human-readable */
35 char *circuit_state_to_string
[] = {
36 "doing handshakes", /* 0 */
37 "processing the onion", /* 1 */
38 "connecting to firsthop", /* 2 */
42 /********* END VARIABLES ************/
44 /** Add <b>circ</b> to the global list of circuits. This is called only from
47 static void circuit_add(circuit_t
*circ
) {
48 if(!global_circuitlist
) { /* first one */
49 global_circuitlist
= circ
;
52 circ
->next
= global_circuitlist
;
53 global_circuitlist
= circ
;
58 /** Detach from the global circuit list, and deallocate, all
59 * circuits that have been marked for close.
61 void circuit_close_all_marked()
65 while (global_circuitlist
&& global_circuitlist
->marked_for_close
) {
66 tmp
= global_circuitlist
->next
;
67 circuit_free(global_circuitlist
);
68 global_circuitlist
= tmp
;
71 tmp
= global_circuitlist
;
72 while (tmp
&& tmp
->next
) {
73 if (tmp
->next
->marked_for_close
) {
75 circuit_free(tmp
->next
);
77 /* Need to check new tmp->next; don't advance tmp. */
85 /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
86 * and <b>p_conn</b>. Add it to the global circuit list.
88 circuit_t
*circuit_new(uint16_t p_circ_id
, connection_t
*p_conn
) {
91 circ
= tor_malloc_zero(sizeof(circuit_t
));
92 circ
->magic
= CIRCUIT_MAGIC
;
94 circ
->timestamp_created
= time(NULL
);
96 circ
->p_circ_id
= p_circ_id
;
97 circ
->p_conn
= p_conn
;
99 circ
->state
= CIRCUIT_STATE_ONIONSKIN_PENDING
;
102 circ
->p_circ_id
= p_circ_id
;
103 /* circ->n_circ_id remains 0 because we haven't identified the next hop yet */
105 circ
->package_window
= CIRCWINDOW_START
;
106 circ
->deliver_window
= CIRCWINDOW_START
;
108 circ
->next_stream_id
= crypto_pseudo_rand_int(1<<16);
115 /** Deallocate space associated with circ.
117 static void circuit_free(circuit_t
*circ
) {
119 tor_assert(circ
->magic
== CIRCUIT_MAGIC
);
121 crypto_free_cipher_env(circ
->n_crypto
);
123 crypto_free_cipher_env(circ
->p_crypto
);
125 crypto_free_digest_env(circ
->n_digest
);
127 crypto_free_digest_env(circ
->p_digest
);
128 if(circ
->build_state
) {
129 tor_free(circ
->build_state
->chosen_exit
);
130 if (circ
->build_state
->pending_final_cpath
)
131 circuit_free_cpath_node(circ
->build_state
->pending_final_cpath
);
133 tor_free(circ
->build_state
);
134 circuit_free_cpath(circ
->cpath
);
135 if (circ
->rend_splice
) {
136 circ
->rend_splice
->rend_splice
= NULL
;
139 memset(circ
, 0xAA, sizeof(circuit_t
)); /* poison memory */
143 /** Deallocate space associated with the linked list <b>cpath</b>. */
144 static void circuit_free_cpath(crypt_path_t
*cpath
) {
145 crypt_path_t
*victim
, *head
=cpath
;
150 /* it's a doubly linked list, so we have to notice when we've
151 * gone through it once. */
152 while(cpath
->next
&& cpath
->next
!= head
) {
154 cpath
= victim
->next
;
155 circuit_free_cpath_node(victim
);
158 circuit_free_cpath_node(cpath
);
161 /** Deallocate space associated with the cpath node <b>victim</b>. */
162 static void circuit_free_cpath_node(crypt_path_t
*victim
) {
164 crypto_free_cipher_env(victim
->f_crypto
);
166 crypto_free_cipher_env(victim
->b_crypto
);
168 crypto_free_digest_env(victim
->f_digest
);
170 crypto_free_digest_env(victim
->b_digest
);
171 if(victim
->handshake_state
)
172 crypto_dh_free(victim
->handshake_state
);
176 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
177 * and with the high bit specified by circ_id_type (see
178 * decide_circ_id_type()), until we get a circ_id that is not in use
179 * by any other circuit on that conn.
181 * Return it, or 0 if can't get a unique circ_id.
183 static uint16_t get_unique_circ_id_by_conn(connection_t
*conn
, int circ_id_type
) {
184 uint16_t test_circ_id
;
188 tor_assert(conn
&& conn
->type
== CONN_TYPE_OR
);
189 high_bit
= (circ_id_type
== CIRC_ID_TYPE_HIGHER
) ? 1<<15 : 0;
191 /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
192 * circID such that (high_bit|test_circ_id) is not already used. */
193 test_circ_id
= conn
->next_circ_id
++;
194 if (test_circ_id
== 0 || test_circ_id
>= 1<<15) {
196 conn
->next_circ_id
= 2;
198 if(++attempts
> 1<<15) {
199 /* Make sure we don't loop forever if all circ_id's are used. This
200 * matters because it's an external DoS vulnerability.
202 log_fn(LOG_WARN
,"No unused circ IDs. Failing.");
205 test_circ_id
|= high_bit
;
206 } while(circuit_get_by_circ_id_conn(test_circ_id
, conn
));
210 /** Return a circ such that:
211 * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
212 * - circ is attached to <b>conn</b>, either as p_conn, n-conn, or
213 * in p_streams or n_streams.
214 * Return NULL if no such circuit exists.
216 circuit_t
*circuit_get_by_circ_id_conn(uint16_t circ_id
, connection_t
*conn
) {
218 connection_t
*tmpconn
;
220 for(circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
221 if (circ
->marked_for_close
)
224 if(circ
->p_circ_id
== circ_id
) {
225 if(circ
->p_conn
== conn
)
227 for(tmpconn
= circ
->p_streams
; tmpconn
; tmpconn
= tmpconn
->next_stream
) {
232 if(circ
->n_circ_id
== circ_id
) {
233 if(circ
->n_conn
== conn
)
235 for(tmpconn
= circ
->n_streams
; tmpconn
; tmpconn
= tmpconn
->next_stream
) {
239 for(tmpconn
= circ
->resolving_streams
; tmpconn
; tmpconn
= tmpconn
->next_stream
) {
248 /** Return a circ such that circ is attached to <b>conn</b>, either as
249 * p_conn, n-conn, or in p_streams or n_streams.
251 * Return NULL if no such circuit exists.
253 circuit_t
*circuit_get_by_conn(connection_t
*conn
) {
255 connection_t
*tmpconn
;
257 for(circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
258 if (circ
->marked_for_close
)
261 if(circ
->p_conn
== conn
)
263 if(circ
->n_conn
== conn
)
265 for(tmpconn
= circ
->p_streams
; tmpconn
; tmpconn
=tmpconn
->next_stream
)
268 for(tmpconn
= circ
->n_streams
; tmpconn
; tmpconn
=tmpconn
->next_stream
)
271 for(tmpconn
= circ
->resolving_streams
; tmpconn
; tmpconn
=tmpconn
->next_stream
)
278 /* Return 1 if <b>circ</b> could be returned by circuit_get_best().
281 static int circuit_is_acceptable(circuit_t
*circ
,
287 routerinfo_t
*exitrouter
;
289 if (!CIRCUIT_IS_ORIGIN(circ
))
290 return 0; /* this circ doesn't start at us */
291 if (must_be_open
&& (circ
->state
!= CIRCUIT_STATE_OPEN
|| !circ
->n_conn
))
292 return 0; /* ignore non-open circs */
293 if (circ
->marked_for_close
)
296 /* if this circ isn't our purpose, skip. */
297 if(purpose
== CIRCUIT_PURPOSE_C_REND_JOINED
&& !must_be_open
) {
298 if(circ
->purpose
!= CIRCUIT_PURPOSE_C_ESTABLISH_REND
&&
299 circ
->purpose
!= CIRCUIT_PURPOSE_C_REND_READY
&&
300 circ
->purpose
!= CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
&&
301 circ
->purpose
!= CIRCUIT_PURPOSE_C_REND_JOINED
)
303 } else if (purpose
== CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
&& !must_be_open
) {
304 if (circ
->purpose
!= CIRCUIT_PURPOSE_C_INTRODUCING
&&
305 circ
->purpose
!= CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
)
308 if(purpose
!= circ
->purpose
)
312 if(purpose
== CIRCUIT_PURPOSE_C_GENERAL
)
313 if(circ
->timestamp_dirty
&&
314 circ
->timestamp_dirty
+options
.NewCircuitPeriod
< now
)
318 /* decide if this circ is suitable for this conn */
320 /* for rend circs, circ->cpath->prev is not the last router in the
321 * circuit, it's the magical extra bob hop. so just check the nickname
322 * of the one we meant to finish at.
324 exitrouter
= router_get_by_nickname(circ
->build_state
->chosen_exit
);
327 log_fn(LOG_INFO
,"Skipping broken circ (exit router vanished)");
328 return 0; /* this circuit is screwed and doesn't know it yet */
331 if(purpose
== CIRCUIT_PURPOSE_C_GENERAL
) {
332 if(connection_ap_can_use_exit(conn
, exitrouter
) == ADDR_POLICY_REJECTED
) {
333 /* can't exit from this router */
336 } else { /* not general */
337 if(rend_cmp_service_ids(conn
->rend_query
, circ
->rend_query
) &&
338 (circ
->rend_query
[0] || purpose
!= CIRCUIT_PURPOSE_C_REND_JOINED
)) {
339 /* this circ is not for this conn, and it's not suitable
340 * for cannibalizing either */
348 /* Return 1 if circuit <b>a</b> is better than circuit <b>b</b> for
349 * <b>purpose</b>, and return 0 otherwise. Used by circuit_get_best.
351 static int circuit_is_better(circuit_t
*a
, circuit_t
*b
, uint8_t purpose
)
354 case CIRCUIT_PURPOSE_C_GENERAL
:
355 /* if it's used but less dirty it's best;
356 * else if it's more recently created it's best
358 if(b
->timestamp_dirty
) {
359 if(a
->timestamp_dirty
&&
360 a
->timestamp_dirty
> b
->timestamp_dirty
)
363 if(a
->timestamp_dirty
||
364 a
->timestamp_created
> b
->timestamp_created
)
368 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
369 /* the closer it is to ack_wait the better it is */
370 if(a
->purpose
> b
->purpose
)
373 case CIRCUIT_PURPOSE_C_REND_JOINED
:
374 /* the closer it is to rend_joined the better it is */
375 if(a
->purpose
> b
->purpose
)
382 /** Find the best circ that conn can use, preferably one which is
383 * dirty. Circ must not be too old.
385 * Conn must be defined.
387 * If must_be_open, ignore circs not in CIRCUIT_STATE_OPEN.
389 * circ_purpose specifies what sort of circuit we must have.
390 * It can be C_GENERAL, C_INTRODUCE_ACK_WAIT, or C_REND_JOINED.
392 * If it's REND_JOINED and must_be_open==0, then return the closest
393 * rendezvous-purposed circuit that you can find.
395 * If it's INTRODUCE_ACK_WAIT and must_be_open==0, then return the
396 * closest introduce-purposed circuit that you can find.
398 circuit_t
*circuit_get_best(connection_t
*conn
,
399 int must_be_open
, uint8_t purpose
) {
400 circuit_t
*circ
, *best
=NULL
;
401 time_t now
= time(NULL
);
405 tor_assert(purpose
== CIRCUIT_PURPOSE_C_GENERAL
||
406 purpose
== CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
||
407 purpose
== CIRCUIT_PURPOSE_C_REND_JOINED
);
409 for (circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
410 if (!circuit_is_acceptable(circ
,conn
,must_be_open
,purpose
,now
))
413 /* now this is an acceptable circ to hand back. but that doesn't
414 * mean it's the *best* circ to hand back. try to decide.
416 if(!best
|| circuit_is_better(circ
,best
,purpose
))
423 /** Return a circ such that:
424 * - circ-\>rend_query is equal to <b>rend_query</b>, and
425 * - circ-\>purpose is equal to <b>purpose</b>.
427 * Return NULL if no such circuit exists.
429 circuit_t
*circuit_get_by_rend_query_and_purpose(const char *rend_query
, uint8_t purpose
) {
432 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
433 if (!circ
->marked_for_close
&&
434 circ
->purpose
== purpose
&&
435 !rend_cmp_service_ids(rend_query
, circ
->rend_query
))
441 /** Return the first circuit in global_circuitlist after <b>start</b> whose
442 * rend_pk_digest field is <b>digest</b> and whose purpose is <b>purpose</b>. Returns
443 * NULL if no circuit is found. If <b>start</b> is NULL, begin at the start of
446 circuit_t
*circuit_get_next_by_pk_and_purpose(circuit_t
*start
,
447 const char *digest
, uint8_t purpose
)
451 circ
= global_circuitlist
;
455 for( ; circ
; circ
= circ
->next
) {
456 if (circ
->marked_for_close
)
458 if (circ
->purpose
!= purpose
)
460 if (!memcmp(circ
->rend_pk_digest
, digest
, DIGEST_LEN
))
466 /** Return the circuit waiting for a rendezvous with the provided cookie.
467 * Return NULL if no such circuit is found.
469 circuit_t
*circuit_get_rendezvous(const char *cookie
)
472 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
473 if (! circ
->marked_for_close
&&
474 circ
->purpose
== CIRCUIT_PURPOSE_REND_POINT_WAITING
&&
475 ! memcmp(circ
->rend_cookie
, cookie
, REND_COOKIE_LEN
) )
481 /** Circuits that were born at the end of their second might be expired
482 * after 30.1 seconds; circuits born at the beginning might be expired
483 * after closer to 31 seconds.
485 #define MIN_SECONDS_BEFORE_EXPIRING_CIRC 30
487 /** Close all circuits that start at us, aren't open, and were born
488 * at least MIN_SECONDS_BEFORE_EXPIRING_CIRC seconds ago.
490 void circuit_expire_building(time_t now
) {
491 circuit_t
*victim
, *circ
= global_circuitlist
;
496 if(!CIRCUIT_IS_ORIGIN(victim
))
497 continue; /* didn't originate here */
498 if(victim
->marked_for_close
)
499 continue; /* don't mess with marked circs */
500 if(victim
->timestamp_created
+ MIN_SECONDS_BEFORE_EXPIRING_CIRC
> now
)
501 continue; /* it's young still, don't mess with it */
503 /* some debug logs, to help track bugs */
504 if(victim
->purpose
>= CIRCUIT_PURPOSE_C_INTRODUCING
&&
505 victim
->purpose
<= CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
) {
506 if(!victim
->timestamp_dirty
)
507 log_fn(LOG_DEBUG
,"Considering %sopen purp %d to %s (circid %d). (clean).",
508 victim
->state
== CIRCUIT_STATE_OPEN
? "" : "non",
509 victim
->purpose
, victim
->build_state
->chosen_exit
,
512 log_fn(LOG_DEBUG
,"Considering %sopen purp %d to %s (circid %d). %d secs since dirty.",
513 victim
->state
== CIRCUIT_STATE_OPEN
? "" : "non",
514 victim
->purpose
, victim
->build_state
->chosen_exit
,
516 (int)(now
- victim
->timestamp_dirty
));
519 /* if circ is !open, or if it's open but purpose is a non-finished
520 * intro or rend, then mark it for close */
521 if(victim
->state
!= CIRCUIT_STATE_OPEN
||
522 victim
->purpose
== CIRCUIT_PURPOSE_C_ESTABLISH_REND
||
523 victim
->purpose
== CIRCUIT_PURPOSE_C_INTRODUCING
||
524 victim
->purpose
== CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
||
526 /* it's a rend_ready circ, but it's already picked a query */
527 (victim
->purpose
== CIRCUIT_PURPOSE_C_REND_READY
&&
528 victim
->rend_query
[0]) ||
530 /* c_rend_ready circs measure age since timestamp_dirty,
531 * because that's set when they switch purposes
533 /* rend and intro circs become dirty each time they
534 * make an introduction attempt. so timestamp_dirty
535 * will reflect the time since the last attempt.
537 ((victim
->purpose
== CIRCUIT_PURPOSE_C_REND_READY
||
538 victim
->purpose
== CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
||
539 victim
->purpose
== CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
) &&
540 victim
->timestamp_dirty
+ MIN_SECONDS_BEFORE_EXPIRING_CIRC
> now
)) {
542 log_fn(LOG_INFO
,"Abandoning circ %s:%d:%d (state %d:%s, purpose %d)",
543 victim
->n_conn
->address
, victim
->n_port
, victim
->n_circ_id
,
544 victim
->state
, circuit_state_to_string
[victim
->state
], victim
->purpose
);
546 log_fn(LOG_INFO
,"Abandoning circ %d (state %d:%s, purpose %d)", victim
->n_circ_id
,
547 victim
->state
, circuit_state_to_string
[victim
->state
], victim
->purpose
);
548 circuit_log_path(LOG_INFO
,victim
);
549 circuit_mark_for_close(victim
);
554 /** Count the number of circs originating here that aren't open, and
555 * that have the specified <b>purpose</b>. */
556 int circuit_count_building(uint8_t purpose
) {
560 for(circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
561 if(CIRCUIT_IS_ORIGIN(circ
) &&
562 circ
->state
!= CIRCUIT_STATE_OPEN
&&
563 circ
->purpose
== purpose
&&
564 !circ
->marked_for_close
)
570 /** How many circuits do we want simultaneously in-progress to handle
573 #define MIN_CIRCUITS_HANDLING_STREAM 2
575 /** Return 1 if at least MIN_CIRCUITS_HANDLING_STREAM non-open
576 * general-purpose circuits will have an acceptable exit node for
577 * conn. Else return 0.
579 int circuit_stream_is_being_handled(connection_t
*conn
) {
581 routerinfo_t
*exitrouter
;
583 time_t now
= time(NULL
);
585 for(circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
586 if(CIRCUIT_IS_ORIGIN(circ
) && circ
->state
!= CIRCUIT_STATE_OPEN
&&
587 !circ
->marked_for_close
&& circ
->purpose
== CIRCUIT_PURPOSE_C_GENERAL
&&
588 (!circ
->timestamp_dirty
||
589 circ
->timestamp_dirty
+ options
.NewCircuitPeriod
< now
)) {
590 exitrouter
= router_get_by_nickname(circ
->build_state
->chosen_exit
);
591 if(exitrouter
&& connection_ap_can_use_exit(conn
, exitrouter
) != ADDR_POLICY_REJECTED
)
592 if(++num
>= MIN_CIRCUITS_HANDLING_STREAM
)
599 /** Return the circuit that is open, has specified <b>purpose</b>,
600 * has a timestamp_dirty value of 0, and was created most recently,
601 * or NULL if no circuit fits this description.
604 circuit_get_youngest_clean_open(uint8_t purpose
) {
606 circuit_t
*youngest
=NULL
;
608 for(circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
609 if(CIRCUIT_IS_ORIGIN(circ
) && circ
->state
== CIRCUIT_STATE_OPEN
&&
610 !circ
->marked_for_close
&& circ
->purpose
== purpose
&&
611 !circ
->timestamp_dirty
&&
612 (!youngest
|| youngest
->timestamp_created
< circ
->timestamp_created
))
618 /** Build a new test circuit every 5 minutes */
619 #define TESTING_CIRCUIT_INTERVAL 300
621 /** This function is called once a second. Its job is to make sure
622 * all services we offer have enough circuits available. Some
623 * services just want enough circuits for current tasks, whereas
624 * others want a minimum set of idle circuits hanging around.
626 void circuit_build_needed_circs(time_t now
) {
627 static long time_to_new_circuit
= 0;
630 /* launch a new circ for any pending streams that need one */
631 connection_ap_attach_pending();
633 /* make sure any hidden services have enough intro points */
634 rend_services_introduce();
636 circ
= circuit_get_youngest_clean_open(CIRCUIT_PURPOSE_C_GENERAL
);
638 if(time_to_new_circuit
< now
) {
639 circuit_reset_failure_count();
640 time_to_new_circuit
= now
+ options
.NewCircuitPeriod
;
641 if(options
.SocksPort
)
643 circuit_expire_old_circuits();
645 if(options
.RunTesting
&& circ
&&
646 circ
->timestamp_created
+ TESTING_CIRCUIT_INTERVAL
< now
) {
647 log_fn(LOG_INFO
,"Creating a new testing circuit.");
648 circuit_launch_new(CIRCUIT_PURPOSE_C_GENERAL
, NULL
);
652 /** How many simultaneous in-progress general-purpose circuits do we
653 * want to be building at once, if there are no open general-purpose
656 #define CIRCUIT_MIN_BUILDING_GENERAL 3
657 /* if there's no open circ, and less than 3 are on the way,
658 * go ahead and try another. */
659 if(!circ
&& circuit_count_building(CIRCUIT_PURPOSE_C_GENERAL
)
660 < CIRCUIT_MIN_BUILDING_GENERAL
) {
661 circuit_launch_new(CIRCUIT_PURPOSE_C_GENERAL
, NULL
);
664 /* XXX count idle rendezvous circs and build more */
667 /** The circuit <b>circ</b> has received a circuit-level sendme
668 * (on hop <b>layer_hint</b>, if we're the OP). Go through all the
669 * attached streams and let them resume reading and packaging, if
670 * their stream windows allow it.
672 void circuit_resume_edge_reading(circuit_t
*circ
, crypt_path_t
*layer_hint
) {
674 log_fn(LOG_DEBUG
,"resuming");
676 /* have to check both n_streams and p_streams, to handle rendezvous */
677 if(circuit_resume_edge_reading_helper(circ
->n_streams
, circ
, layer_hint
) >= 0)
678 circuit_resume_edge_reading_helper(circ
->p_streams
, circ
, layer_hint
);
681 /** A helper function for circuit_resume_edge_reading() above.
682 * The arguments are the same, except that <b>conn</b> is the head
683 * of a linked list of edge streams that should each be considered.
686 circuit_resume_edge_reading_helper(connection_t
*conn
,
688 crypt_path_t
*layer_hint
) {
690 for( ; conn
; conn
=conn
->next_stream
) {
691 if((!layer_hint
&& conn
->package_window
> 0) ||
692 (layer_hint
&& conn
->package_window
> 0 && conn
->cpath_layer
== layer_hint
)) {
693 connection_start_reading(conn
);
694 /* handle whatever might still be on the inbuf */
695 connection_edge_package_raw_inbuf(conn
);
697 /* If the circuit won't accept any more data, return without looking
698 * at any more of the streams. Any connections that should be stopped
699 * have already been stopped by connection_edge_package_raw_inbuf. */
700 if(circuit_consider_stop_edge_reading(circ
, layer_hint
))
707 /** Check if the package window for <b>circ</b> is empty (at
708 * hop <b>layer_hint</b> if it's defined).
710 * If yes, tell edge streams to stop reading and return -1.
713 int circuit_consider_stop_edge_reading(circuit_t
*circ
, crypt_path_t
*layer_hint
) {
714 connection_t
*conn
= NULL
;
716 log_fn(LOG_DEBUG
,"considering");
717 if(!layer_hint
&& circ
->package_window
<= 0) {
718 log_fn(LOG_DEBUG
,"yes, not-at-origin. stopped.");
719 for(conn
= circ
->n_streams
; conn
; conn
=conn
->next_stream
)
720 connection_stop_reading(conn
);
722 } else if(layer_hint
&& layer_hint
->package_window
<= 0) {
723 log_fn(LOG_DEBUG
,"yes, at-origin. stopped.");
724 for(conn
= circ
->n_streams
; conn
; conn
=conn
->next_stream
)
725 if(conn
->cpath_layer
== layer_hint
)
726 connection_stop_reading(conn
);
727 for(conn
= circ
->p_streams
; conn
; conn
=conn
->next_stream
)
728 if(conn
->cpath_layer
== layer_hint
)
729 connection_stop_reading(conn
);
735 /** Check if the deliver_window for circuit <b>circ</b> (at hop
736 * <b>layer_hint</b> if it's defined) is low enough that we should
737 * send a circuit-level sendme back down the circuit. If so, send
738 * enough sendmes that the window would be overfull if we sent any
741 void circuit_consider_sending_sendme(circuit_t
*circ
, crypt_path_t
*layer_hint
) {
742 // log_fn(LOG_INFO,"Considering: layer_hint is %s",
743 // layer_hint ? "defined" : "null");
744 while((layer_hint
? layer_hint
->deliver_window
: circ
->deliver_window
) <
745 CIRCWINDOW_START
- CIRCWINDOW_INCREMENT
) {
746 log_fn(LOG_DEBUG
,"Queueing circuit sendme.");
748 layer_hint
->deliver_window
+= CIRCWINDOW_INCREMENT
;
750 circ
->deliver_window
+= CIRCWINDOW_INCREMENT
;
751 if(connection_edge_send_command(NULL
, circ
, RELAY_COMMAND_SENDME
,
752 NULL
, 0, layer_hint
) < 0) {
753 log_fn(LOG_WARN
,"connection_edge_send_command failed. Circuit's closed.");
754 return; /* the circuit's closed, don't continue */
759 /** Mark <b>circ</b> to be closed next time we call
760 * circuit_close_all_marked(). Do any cleanup needed:
761 * - If state is onionskin_pending, remove circ from the onion_pending
763 * - If circ isn't open yet, call circuit_build_failed() if we're
764 * the origin, and in case call circuit_rep_hist_note_result()
766 * - If purpose is C_INTRODUCE_ACK_WAIT, remove the intro point we
767 * just tried from our list of intro points for that service
769 * - Send appropriate destroys and edge_destroys for conns and
770 * streams attached to circ.
771 * - If circ->rend_splice is set (we are the midpoint of a joined
772 * rendezvous stream), then mark the other circuit to close as well.
774 int _circuit_mark_for_close(circuit_t
*circ
) {
777 assert_circuit_ok(circ
);
778 if (circ
->marked_for_close
)
781 if(circ
->state
== CIRCUIT_STATE_ONIONSKIN_PENDING
) {
782 onion_pending_remove(circ
);
784 /* If the circuit ever became OPEN, we sent it to the reputation history
785 * module then. If it isn't OPEN, we send it there now to remember which
786 * links worked and which didn't.
788 if (circ
->state
!= CIRCUIT_STATE_OPEN
) {
789 if(CIRCUIT_IS_ORIGIN(circ
))
790 circuit_build_failed(circ
); /* take actions if necessary */
791 circuit_rep_hist_note_result(circ
);
793 if (circ
->purpose
== CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
) {
794 tor_assert(circ
->state
== CIRCUIT_STATE_OPEN
);
795 /* treat this like getting a nack from it */
796 log_fn(LOG_INFO
,"Failed intro circ %s to %s (awaiting ack). Removing from descriptor.",
797 circ
->rend_query
, circ
->build_state
->chosen_exit
);
798 rend_client_remove_intro_point(circ
->build_state
->chosen_exit
, circ
->rend_query
);
802 connection_send_destroy(circ
->n_circ_id
, circ
->n_conn
);
803 for(conn
=circ
->n_streams
; conn
; conn
=conn
->next_stream
)
804 connection_edge_destroy(circ
->n_circ_id
, conn
);
805 while(circ
->resolving_streams
) {
806 conn
= circ
->resolving_streams
;
807 circ
->resolving_streams
= conn
->next_stream
;
808 log_fn(LOG_INFO
,"Freeing resolving-conn.");
809 connection_free(conn
);
812 connection_send_destroy(circ
->p_circ_id
, circ
->p_conn
);
813 for(conn
=circ
->p_streams
; conn
; conn
=conn
->next_stream
)
814 connection_edge_destroy(circ
->p_circ_id
, conn
);
816 circ
->marked_for_close
= 1;
818 if (circ
->rend_splice
&& !circ
->rend_splice
->marked_for_close
) {
819 /* do this after marking this circuit, to avoid infinite recursion. */
820 circuit_mark_for_close(circ
->rend_splice
);
821 circ
->rend_splice
= NULL
;
826 /** If the stream <b>conn</b> is a member of any of the linked
827 * lists of <b>circ</b>, then remove it from the list.
829 void circuit_detach_stream(circuit_t
*circ
, connection_t
*conn
) {
830 connection_t
*prevconn
;
832 tor_assert(circ
&& conn
);
834 if(conn
== circ
->p_streams
) {
835 circ
->p_streams
= conn
->next_stream
;
838 if(conn
== circ
->n_streams
) {
839 circ
->n_streams
= conn
->next_stream
;
842 if(conn
== circ
->resolving_streams
) {
843 circ
->resolving_streams
= conn
->next_stream
;
847 for(prevconn
= circ
->p_streams
;
848 prevconn
&& prevconn
->next_stream
&& prevconn
->next_stream
!= conn
;
849 prevconn
= prevconn
->next_stream
)
851 if(prevconn
&& prevconn
->next_stream
) {
852 prevconn
->next_stream
= conn
->next_stream
;
856 for(prevconn
= circ
->n_streams
;
857 prevconn
&& prevconn
->next_stream
&& prevconn
->next_stream
!= conn
;
858 prevconn
= prevconn
->next_stream
)
860 if(prevconn
&& prevconn
->next_stream
) {
861 prevconn
->next_stream
= conn
->next_stream
;
865 for(prevconn
= circ
->resolving_streams
;
866 prevconn
&& prevconn
->next_stream
&& prevconn
->next_stream
!= conn
;
867 prevconn
= prevconn
->next_stream
)
869 if(prevconn
&& prevconn
->next_stream
) {
870 prevconn
->next_stream
= conn
->next_stream
;
874 log_fn(LOG_ERR
,"edge conn not in circuit's list?");
875 tor_assert(0); /* should never get here */
878 /** Notify the global circuit list that <b>conn</b> is about to be
879 * removed and then freed.
881 * If it's an OR conn, then mark-for-close all the circuits that use
884 * If it's an edge conn, then detach it from its circ, so we don't
885 * try to reference it later.
887 void circuit_about_to_close_connection(connection_t
*conn
) {
888 /* currently, we assume it's too late to flush conn's buf here.
889 * down the road, maybe we'll consider that eof doesn't mean can't-write
895 /* We must close all the circuits on it. */
896 while((circ
= circuit_get_by_conn(conn
))) {
897 if(circ
->n_conn
== conn
) /* it's closing in front of us */
899 if(circ
->p_conn
== conn
) /* it's closing behind us */
901 circuit_mark_for_close(circ
);
907 /* It's an edge conn. Need to remove it from the linked list of
908 * conn's for this circuit. Confirm that 'end' relay command has
909 * been sent. But don't kill the circuit.
912 circ
= circuit_get_by_conn(conn
);
916 if(!conn
->has_sent_end
) {
917 log_fn(LOG_WARN
,"Edge connection hasn't sent end yet? Bug.");
918 connection_mark_for_close(conn
, END_STREAM_REASON_MISC
);
921 circuit_detach_stream(circ
, conn
);
926 /** Log, at severity <b>severity</b>, the nicknames of each router in
927 * circ's cpath. Also log the length of the cpath, and the intended
930 void circuit_log_path(int severity
, circuit_t
*circ
) {
933 struct crypt_path_t
*hop
;
934 char *states
[] = {"closed", "waiting for keys", "open"};
935 routerinfo_t
*router
;
936 tor_assert(CIRCUIT_IS_ORIGIN(circ
) && circ
->cpath
);
938 snprintf(s
, sizeof(buf
)-1, "circ (length %d, exit %s): ",
939 circ
->build_state
->desired_path_len
, circ
->build_state
->chosen_exit
);
942 s
= buf
+ strlen(buf
);
943 router
= router_get_by_addr_port(hop
->addr
,hop
->port
);
945 snprintf(s
, sizeof(buf
) - (s
- buf
), "%s(%s) ",
946 router
->nickname
, states
[hop
->state
]);
948 if(circ
->purpose
== CIRCUIT_PURPOSE_C_REND_JOINED
) {
949 snprintf(s
, sizeof(buf
) - (s
- buf
), "(rendjoin hop)");
951 snprintf(s
, sizeof(buf
) - (s
- buf
), "UNKNOWN ");
955 } while(hop
!=circ
->cpath
);
956 log_fn(severity
,"%s",buf
);
959 /** Tell the rep(utation)hist(ory) module about the status of the links
960 * in circ. Hops that have become OPEN are marked as successfully
961 * extended; the _first_ hop that isn't open (if any) is marked as
965 circuit_rep_hist_note_result(circuit_t
*circ
)
967 struct crypt_path_t
*hop
;
968 char *prev_nickname
= NULL
;
969 routerinfo_t
*router
;
973 * if !hop, then we're not the beginning of this circuit.
974 * for now, just forget about it. later, we should remember when
975 * extends-through-us failed, too.
979 if (options
.ORPort
) {
980 prev_nickname
= options
.Nickname
;
983 router
= router_get_by_addr_port(hop
->addr
,hop
->port
);
986 if (hop
->state
== CPATH_STATE_OPEN
)
987 rep_hist_note_extend_succeeded(prev_nickname
, router
->nickname
);
989 rep_hist_note_extend_failed(prev_nickname
, router
->nickname
);
993 prev_nickname
= router
->nickname
;
995 prev_nickname
= NULL
;
998 } while (hop
!=circ
->cpath
);
1001 /** A helper function for circuit_dump_by_conn() below. Log a bunch
1002 * of information about circuit <b>circ</b>.
1005 circuit_dump_details(int severity
, circuit_t
*circ
, int poll_index
,
1006 char *type
, int this_circid
, int other_circid
) {
1007 struct crypt_path_t
*hop
;
1008 log(severity
,"Conn %d has %s circuit: circID %d (other side %d), state %d (%s), born %d",
1009 poll_index
, type
, this_circid
, other_circid
, circ
->state
,
1010 circuit_state_to_string
[circ
->state
], (int)circ
->timestamp_created
);
1011 if(CIRCUIT_IS_ORIGIN(circ
)) { /* circ starts at this node */
1012 if(circ
->state
== CIRCUIT_STATE_BUILDING
)
1013 log(severity
,"Building: desired len %d, planned exit node %s.",
1014 circ
->build_state
->desired_path_len
, circ
->build_state
->chosen_exit
);
1015 for(hop
=circ
->cpath
;hop
->next
!= circ
->cpath
; hop
=hop
->next
)
1016 log(severity
,"hop: state %d, addr 0x%.8x, port %d", hop
->state
,
1017 (unsigned int)hop
->addr
,
1022 /** Log, at severity <b>severity</b>, information about each circuit
1023 * that is connected to <b>conn</b>.
1025 void circuit_dump_by_conn(connection_t
*conn
, int severity
) {
1027 connection_t
*tmpconn
;
1029 for(circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
1030 if(circ
->p_conn
== conn
)
1031 circuit_dump_details(severity
, circ
, conn
->poll_index
, "App-ward",
1032 circ
->p_circ_id
, circ
->n_circ_id
);
1033 for(tmpconn
=circ
->p_streams
; tmpconn
; tmpconn
=tmpconn
->next_stream
) {
1034 if(tmpconn
== conn
) {
1035 circuit_dump_details(severity
, circ
, conn
->poll_index
, "App-ward",
1036 circ
->p_circ_id
, circ
->n_circ_id
);
1039 if(circ
->n_conn
== conn
)
1040 circuit_dump_details(severity
, circ
, conn
->poll_index
, "Exit-ward",
1041 circ
->n_circ_id
, circ
->p_circ_id
);
1042 for(tmpconn
=circ
->n_streams
; tmpconn
; tmpconn
=tmpconn
->next_stream
) {
1043 if(tmpconn
== conn
) {
1044 circuit_dump_details(severity
, circ
, conn
->poll_index
, "Exit-ward",
1045 circ
->n_circ_id
, circ
->p_circ_id
);
1051 /** Don't keep more than 10 unused open circuits around. */
1052 #define MAX_UNUSED_OPEN_CIRCUITS 10
1054 /** Find each circuit that has been dirty for too long, and has
1055 * no streams on it: mark it for close.
1057 * Also, if there are more than MAX_UNUSED_OPEN_CIRCUITS open and
1058 * unused circuits, then mark the excess circs for close.
1060 void circuit_expire_old_circuits(void) {
1062 time_t now
= time(NULL
);
1063 smartlist_t
*unused_open_circs
;
1066 unused_open_circs
= smartlist_create();
1068 for (circ
= global_circuitlist
; circ
; circ
= circ
->next
) {
1069 if (circ
->marked_for_close
)
1071 /* If the circuit has been dirty for too long, and there are no streams
1072 * on it, mark it for close.
1074 if (circ
->timestamp_dirty
&&
1075 circ
->timestamp_dirty
+ options
.NewCircuitPeriod
< now
&&
1076 !circ
->p_conn
&& /* we're the origin */
1077 !circ
->p_streams
/* nothing attached */ ) {
1078 log_fn(LOG_DEBUG
,"Closing n_circ_id %d (dirty %d secs ago, purp %d)",circ
->n_circ_id
,
1079 (int)(now
- circ
->timestamp_dirty
), circ
->purpose
);
1080 /* (only general and purpose_c circs can get dirty) */
1081 tor_assert(!circ
->n_streams
);
1082 tor_assert(circ
->purpose
<= CIRCUIT_PURPOSE_C_REND_JOINED
);
1083 circuit_mark_for_close(circ
);
1084 } else if (!circ
->timestamp_dirty
&& CIRCUIT_IS_ORIGIN(circ
) &&
1085 circ
->state
== CIRCUIT_STATE_OPEN
&&
1086 circ
->purpose
== CIRCUIT_PURPOSE_C_GENERAL
) {
1087 /* Also, gather a list of open unused general circuits that we created.
1088 * Because we add elements to the front of global_circuitlist,
1089 * the last elements of unused_open_circs will be the oldest
1092 smartlist_add(unused_open_circs
, circ
);
1095 for (i
= MAX_UNUSED_OPEN_CIRCUITS
; i
< smartlist_len(unused_open_circs
); ++i
) {
1096 circuit_t
*circ
= smartlist_get(unused_open_circs
, i
);
1097 log_fn(LOG_DEBUG
,"Expiring excess clean circ (n_circ_id %d, purp %d)",
1098 circ
->n_circ_id
, circ
->purpose
);
1099 circuit_mark_for_close(circ
);
1101 smartlist_free(unused_open_circs
);
1104 /** The circuit <b>circ</b> has just become open. Take the next
1105 * step: for rendezvous circuits, we pass circ to the appropriate
1106 * function in rendclient or rendservice. For general circuits, we
1107 * call connection_ap_attach_pending, which looks for pending streams
1108 * that could use circ.
1110 static void circuit_is_open(circuit_t
*circ
) {
1112 switch(circ
->purpose
) {
1113 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
1114 rend_client_rendcirc_is_open(circ
);
1116 case CIRCUIT_PURPOSE_C_INTRODUCING
:
1117 rend_client_introcirc_is_open(circ
);
1119 case CIRCUIT_PURPOSE_C_GENERAL
:
1120 /* Tell any AP connections that have been waiting for a new
1121 * circuit that one is ready. */
1122 connection_ap_attach_pending();
1124 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
1125 /* at Bob, waiting for introductions */
1126 rend_service_intro_is_ready(circ
);
1128 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
1129 /* at Bob, connecting to rend point */
1130 rend_service_rendezvous_is_ready(circ
);
1133 log_fn(LOG_ERR
,"unhandled purpose %d",circ
->purpose
);
1138 /*~ Called whenever a circuit could not be successfully built.
1140 static void circuit_build_failed(circuit_t
*circ
) {
1142 /* we should examine circ and see if it failed because of
1143 * the last hop or an earlier hop. then use this info below.
1145 int failed_at_last_hop
= 0;
1146 /* If the last hop isn't open, and the second-to-last is, we failed
1147 * at the last hop. */
1149 circ
->cpath
->prev
->state
!= CPATH_STATE_OPEN
&&
1150 circ
->cpath
->prev
->prev
->state
== CPATH_STATE_OPEN
) {
1151 failed_at_last_hop
= 1;
1154 switch(circ
->purpose
) {
1155 case CIRCUIT_PURPOSE_C_GENERAL
:
1156 if (circ
->state
!= CIRCUIT_STATE_OPEN
) {
1157 /* If we never built the circuit, note it as a failure. */
1158 /* Note that we can't just check circ->cpath here, because if
1159 * circuit-building failed immediately, it won't be set yet. */
1160 circuit_increment_failure_count();
1163 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
1164 /* at Bob, waiting for introductions */
1165 if (circ
->state
!= CIRCUIT_STATE_OPEN
) {
1166 circuit_increment_failure_count();
1168 /* no need to care here, because bob will rebuild intro
1169 * points periodically. */
1171 case CIRCUIT_PURPOSE_C_INTRODUCING
:
1172 /* at Alice, connecting to intro point */
1173 /* Don't increment failure count, since Bob may have picked
1174 * the introduction point maliciously */
1175 /* Alice will pick a new intro point when this one dies, if
1176 * the stream in question still cares. No need to act here. */
1178 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
1179 /* at Alice, waiting for Bob */
1180 if (circ
->state
!= CIRCUIT_STATE_OPEN
) {
1181 circuit_increment_failure_count();
1183 /* Alice will pick a new rend point when this one dies, if
1184 * the stream in question still cares. No need to act here. */
1186 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
1187 /* at Bob, connecting to rend point */
1188 /* Don't increment failure count, since Alice may have picked
1189 * the rendezvous point maliciously */
1190 if (failed_at_last_hop
) {
1191 log_fn(LOG_INFO
,"Couldn't connect to Alice's chosen rend point %s. Sucks to be Alice.", circ
->build_state
->chosen_exit
);
1193 log_fn(LOG_INFO
,"Couldn't connect to Alice's chosen rend point %s, because an earlier node failed.",
1194 circ
->build_state
->chosen_exit
);
1195 rend_service_relaunch_rendezvous(circ
);
1199 /* Other cases are impossible, since this function is only called with
1200 * unbuilt circuits. */
1205 /** Number of consecutive failures so far; should only be touched by
1206 * circuit_launch_new and circuit_*_failure_count.
1208 static int n_circuit_failures
= 0;
1210 /** Don't retry launching a new circuit if we try this many times with no
1212 #define MAX_CIRCUIT_FAILURES 5
1214 /** Launch a new circuit and return a pointer to it. Return NULL if you failed. */
1215 circuit_t
*circuit_launch_new(uint8_t purpose
, const char *exit_nickname
) {
1217 if (n_circuit_failures
> MAX_CIRCUIT_FAILURES
) {
1218 /* too many failed circs in a row. don't try. */
1219 // log_fn(LOG_INFO,"%d failures so far, not trying.",n_circuit_failures);
1223 /* try a circ. if it fails, circuit_mark_for_close will increment n_circuit_failures */
1224 return circuit_establish_circuit(purpose
, exit_nickname
);
1227 /** Record another failure at opening a general circuit. When we have
1228 * too many, we'll stop trying for the remainder of this minute.
1230 void circuit_increment_failure_count(void) {
1231 ++n_circuit_failures
;
1232 log_fn(LOG_DEBUG
,"n_circuit_failures now %d.",n_circuit_failures
);
1235 /** Reset the failure count for opening general circuits. This means
1236 * we will try MAX_CIRCUIT_FAILURES times more (if necessary) before
1239 void circuit_reset_failure_count(void) {
1240 n_circuit_failures
= 0;
1243 /** Build a new circuit for <b>purpose</b>. If <b>exit_nickname</b>
1244 * is defined, then use that as your exit router, else choose a suitable
1247 * Also launch a connection to the first OR in the chosen path, if
1248 * it's not open already.
1250 static circuit_t
*circuit_establish_circuit(uint8_t purpose
,
1251 const char *exit_nickname
) {
1252 routerinfo_t
*firsthop
;
1253 connection_t
*n_conn
;
1256 circ
= circuit_new(0, NULL
); /* sets circ->p_circ_id and circ->p_conn */
1257 circ
->state
= CIRCUIT_STATE_OR_WAIT
;
1258 circ
->build_state
= onion_new_cpath_build_state(purpose
, exit_nickname
);
1259 circ
->purpose
= purpose
;
1261 if (! circ
->build_state
) {
1262 log_fn(LOG_INFO
,"Generating cpath failed.");
1263 circuit_mark_for_close(circ
);
1267 onion_extend_cpath(&circ
->cpath
, circ
->build_state
, &firsthop
);
1268 if(!CIRCUIT_IS_ORIGIN(circ
)) {
1269 log_fn(LOG_INFO
,"Generating first cpath hop failed.");
1270 circuit_mark_for_close(circ
);
1274 /* now see if we're already connected to the first OR in 'route' */
1276 log_fn(LOG_DEBUG
,"Looking for firsthop '%s:%u'",
1277 firsthop
->address
,firsthop
->or_port
);
1278 n_conn
= connection_twin_get_by_addr_port(firsthop
->addr
,firsthop
->or_port
);
1279 if(!n_conn
|| n_conn
->state
!= OR_CONN_STATE_OPEN
) { /* not currently connected */
1280 circ
->n_addr
= firsthop
->addr
;
1281 circ
->n_port
= firsthop
->or_port
;
1283 if(!n_conn
) { /* launch the connection */
1284 n_conn
= connection_or_connect(firsthop
);
1285 if(!n_conn
) { /* connect failed, forget the whole thing */
1286 log_fn(LOG_INFO
,"connect to firsthop failed. Closing.");
1287 circuit_mark_for_close(circ
);
1292 log_fn(LOG_DEBUG
,"connecting in progress (or finished). Good.");
1293 /* return success. The onion/circuit/etc will be taken care of automatically
1294 * (may already have been) whenever n_conn reaches OR_CONN_STATE_OPEN.
1297 } else { /* it (or a twin) is already open. use it. */
1298 circ
->n_addr
= n_conn
->addr
;
1299 circ
->n_port
= n_conn
->port
;
1300 circ
->n_conn
= n_conn
;
1301 log_fn(LOG_DEBUG
,"Conn open. Delivering first onion skin.");
1302 if(circuit_send_next_onion_skin(circ
) < 0) {
1303 log_fn(LOG_INFO
,"circuit_send_next_onion_skin failed.");
1304 circuit_mark_for_close(circ
);
1311 /** Find circuits that are waiting on <b>or_conn</b> to become open,
1312 * if any, and get them to send their create cells forward.
1314 void circuit_n_conn_open(connection_t
*or_conn
) {
1317 for(circ
=global_circuitlist
;circ
;circ
= circ
->next
) {
1318 if (circ
->marked_for_close
)
1320 if(CIRCUIT_IS_ORIGIN(circ
) && circ
->n_addr
== or_conn
->addr
&& circ
->n_port
== or_conn
->port
) {
1321 tor_assert(circ
->state
== CIRCUIT_STATE_OR_WAIT
);
1322 log_fn(LOG_DEBUG
,"Found circ %d, sending onion skin.", circ
->n_circ_id
);
1323 circ
->n_conn
= or_conn
;
1324 if(circuit_send_next_onion_skin(circ
) < 0) {
1325 log_fn(LOG_INFO
,"send_next_onion_skin failed; circuit marked for closing.");
1326 circuit_mark_for_close(circ
);
1328 /* XXX could this be bad, eg if next_onion_skin failed because conn died? */
1334 extern int has_completed_circuit
;
1336 /** This is the backbone function for building circuits.
1338 * If circ's first hop is closed, then we need to build a create
1339 * cell and send it forward.
1341 * Otherwise, we need to build a relay extend cell and send it
1344 * Return -1 if we want to tear down circ, else return 0.
1346 int circuit_send_next_onion_skin(circuit_t
*circ
) {
1349 routerinfo_t
*router
;
1352 char payload
[2+4+ONIONSKIN_CHALLENGE_LEN
];
1354 tor_assert(circ
&& CIRCUIT_IS_ORIGIN(circ
));
1356 if(circ
->cpath
->state
== CPATH_STATE_CLOSED
) {
1357 tor_assert(circ
->n_conn
&& circ
->n_conn
->type
== CONN_TYPE_OR
);
1359 log_fn(LOG_DEBUG
,"First skin; sending create cell.");
1360 circ_id_type
= decide_circ_id_type(options
.Nickname
,
1361 circ
->n_conn
->nickname
);
1362 circ
->n_circ_id
= get_unique_circ_id_by_conn(circ
->n_conn
, circ_id_type
);
1364 memset(&cell
, 0, sizeof(cell_t
));
1365 cell
.command
= CELL_CREATE
;
1366 cell
.circ_id
= circ
->n_circ_id
;
1368 router
= router_get_by_nickname(circ
->n_conn
->nickname
);
1370 log_fn(LOG_WARN
,"Couldn't find routerinfo for %s",
1371 circ
->n_conn
->nickname
);
1375 if(onion_skin_create(router
->onion_pkey
,
1376 &(circ
->cpath
->handshake_state
),
1377 cell
.payload
) < 0) {
1378 log_fn(LOG_WARN
,"onion_skin_create (first hop) failed.");
1382 connection_or_write_cell_to_buf(&cell
, circ
->n_conn
);
1384 circ
->cpath
->state
= CPATH_STATE_AWAITING_KEYS
;
1385 circ
->state
= CIRCUIT_STATE_BUILDING
;
1386 log_fn(LOG_DEBUG
,"first skin; finished sending create cell.");
1388 tor_assert(circ
->cpath
->state
== CPATH_STATE_OPEN
);
1389 tor_assert(circ
->state
== CIRCUIT_STATE_BUILDING
);
1390 log_fn(LOG_DEBUG
,"starting to send subsequent skin.");
1391 r
= onion_extend_cpath(&circ
->cpath
, circ
->build_state
, &router
);
1393 /* done building the circuit. whew. */
1394 circ
->state
= CIRCUIT_STATE_OPEN
;
1395 log_fn(LOG_INFO
,"circuit built!");
1396 circuit_reset_failure_count();
1397 if(!has_completed_circuit
) {
1398 has_completed_circuit
=1;
1399 log_fn(LOG_NOTICE
,"Tor has successfully opened a circuit. Looks like it's working.");
1401 circuit_rep_hist_note_result(circ
);
1402 circuit_is_open(circ
); /* do other actions as necessary */
1405 log_fn(LOG_INFO
,"Unable to extend circuit path.");
1408 hop
= circ
->cpath
->prev
;
1410 *(uint32_t*)payload
= htonl(hop
->addr
);
1411 *(uint16_t*)(payload
+4) = htons(hop
->port
);
1412 if(onion_skin_create(router
->onion_pkey
, &(hop
->handshake_state
), payload
+6) < 0) {
1413 log_fn(LOG_WARN
,"onion_skin_create failed.");
1417 log_fn(LOG_DEBUG
,"Sending extend relay cell.");
1418 /* send it to hop->prev, because it will transfer
1419 * it to a create cell and then send to hop */
1420 if(connection_edge_send_command(NULL
, circ
, RELAY_COMMAND_EXTEND
,
1421 payload
, sizeof(payload
), hop
->prev
) < 0)
1422 return 0; /* circuit is closed */
1424 hop
->state
= CPATH_STATE_AWAITING_KEYS
;
1429 /** Take the 'extend' cell, pull out addr/port plus the onion skin. Make
1430 * sure we're connected to the next hop, and pass it the onion skin in
1433 int circuit_extend(cell_t
*cell
, circuit_t
*circ
) {
1434 connection_t
*n_conn
;
1439 log_fn(LOG_WARN
,"n_conn already set. Bug/attack. Closing.");
1443 circ
->n_addr
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
));
1444 circ
->n_port
= ntohs(get_uint16(cell
->payload
+RELAY_HEADER_SIZE
+4));
1446 n_conn
= connection_twin_get_by_addr_port(circ
->n_addr
,circ
->n_port
);
1447 if(!n_conn
|| n_conn
->type
!= CONN_TYPE_OR
) {
1448 /* I've disabled making connections through OPs, but it's definitely
1449 * possible here. I'm not sure if it would be a bug or a feature.
1451 * Note also that this will close circuits where the onion has the same
1452 * router twice in a row in the path. I think that's ok.
1455 in
.s_addr
= htonl(circ
->n_addr
);
1456 log_fn(LOG_INFO
,"Next router (%s:%d) not connected. Closing.", inet_ntoa(in
), circ
->n_port
);
1457 #if 0 /* if we do truncateds, no need to kill circ */
1458 connection_edge_send_command(NULL
, circ
, RELAY_COMMAND_TRUNCATED
,
1462 circuit_mark_for_close(circ
);
1466 circ
->n_addr
= n_conn
->addr
; /* these are different if we found a twin instead */
1467 circ
->n_port
= n_conn
->port
;
1469 circ
->n_conn
= n_conn
;
1470 log_fn(LOG_DEBUG
,"n_conn is %s:%u",n_conn
->address
,n_conn
->port
);
1472 circ_id_type
= decide_circ_id_type(options
.Nickname
, n_conn
->nickname
);
1474 // log_fn(LOG_DEBUG,"circ_id_type = %u.",circ_id_type);
1475 circ
->n_circ_id
= get_unique_circ_id_by_conn(circ
->n_conn
, circ_id_type
);
1476 if(!circ
->n_circ_id
) {
1477 log_fn(LOG_WARN
,"failed to get unique circID.");
1480 log_fn(LOG_DEBUG
,"Chosen circID %u.",circ
->n_circ_id
);
1482 memset(&newcell
, 0, sizeof(cell_t
));
1483 newcell
.command
= CELL_CREATE
;
1484 newcell
.circ_id
= circ
->n_circ_id
;
1486 memcpy(newcell
.payload
, cell
->payload
+RELAY_HEADER_SIZE
+2+4,
1487 ONIONSKIN_CHALLENGE_LEN
);
1489 connection_or_write_cell_to_buf(&newcell
, circ
->n_conn
);
1493 /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
1494 * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
1496 * - 20 to initialize f_digest
1497 * - 20 to initialize b_digest
1498 * - 16 to key f_crypto
1499 * - 16 to key b_crypto
1501 * (If 'reverse' is true, then f_XX and b_XX are swapped.)
1503 int circuit_init_cpath_crypto(crypt_path_t
*cpath
, char *key_data
, int reverse
)
1505 crypto_digest_env_t
*tmp_digest
;
1506 crypto_cipher_env_t
*tmp_crypto
;
1508 tor_assert(cpath
&& key_data
);
1509 tor_assert(!(cpath
->f_crypto
|| cpath
->b_crypto
||
1510 cpath
->f_digest
|| cpath
->b_digest
));
1512 log_fn(LOG_DEBUG
,"hop init digest forward 0x%.8x, backward 0x%.8x.",
1513 (unsigned int)*(uint32_t*)key_data
, (unsigned int)*(uint32_t*)(key_data
+20));
1514 cpath
->f_digest
= crypto_new_digest_env();
1515 crypto_digest_add_bytes(cpath
->f_digest
, key_data
, DIGEST_LEN
);
1516 cpath
->b_digest
= crypto_new_digest_env();
1517 crypto_digest_add_bytes(cpath
->b_digest
, key_data
+DIGEST_LEN
, DIGEST_LEN
);
1519 log_fn(LOG_DEBUG
,"hop init cipher forward 0x%.8x, backward 0x%.8x.",
1520 (unsigned int)*(uint32_t*)(key_data
+40), (unsigned int)*(uint32_t*)(key_data
+40+16));
1521 if (!(cpath
->f_crypto
=
1522 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
),1))) {
1523 log(LOG_WARN
,"forward cipher initialization failed.");
1526 if (!(cpath
->b_crypto
=
1527 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
)+CIPHER_KEY_LEN
,0))) {
1528 log(LOG_WARN
,"backward cipher initialization failed.");
1533 tmp_digest
= cpath
->f_digest
;
1534 cpath
->f_digest
= cpath
->b_digest
;
1535 cpath
->b_digest
= tmp_digest
;
1536 tmp_crypto
= cpath
->f_crypto
;
1537 cpath
->f_crypto
= cpath
->b_crypto
;
1538 cpath
->b_crypto
= tmp_crypto
;
1544 /** A created or extended cell came back to us on the circuit,
1545 * and it included <b>reply</b> (the second DH key, plus KH).
1547 * Calculate the appropriate keys and digests, make sure KH is
1548 * correct, and initialize this hop of the cpath.
1550 * Return -1 if we want to mark circ for close, else return 0.
1552 int circuit_finish_handshake(circuit_t
*circ
, char *reply
) {
1553 unsigned char keys
[CPATH_KEY_MATERIAL_LEN
];
1556 tor_assert(CIRCUIT_IS_ORIGIN(circ
));
1557 if(circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
)
1560 for(hop
=circ
->cpath
->next
;
1561 hop
!= circ
->cpath
&& hop
->state
== CPATH_STATE_OPEN
;
1563 if(hop
== circ
->cpath
) { /* got an extended when we're all done? */
1564 log_fn(LOG_WARN
,"got extended when circ already built? Closing.");
1568 tor_assert(hop
->state
== CPATH_STATE_AWAITING_KEYS
);
1570 if(onion_skin_client_handshake(hop
->handshake_state
, reply
, keys
,
1571 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
1572 log_fn(LOG_WARN
,"onion_skin_client_handshake failed.");
1576 crypto_dh_free(hop
->handshake_state
); /* don't need it anymore */
1577 hop
->handshake_state
= NULL
;
1578 /* Remember hash of g^xy */
1579 memcpy(hop
->handshake_digest
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
1581 if (circuit_init_cpath_crypto(hop
, keys
, 0)<0) {
1585 hop
->state
= CPATH_STATE_OPEN
;
1586 log_fn(LOG_INFO
,"finished");
1587 circuit_log_path(LOG_INFO
,circ
);
1591 /** We received a relay truncated cell on circ.
1593 * Since we don't ask for truncates currently, getting a truncated
1594 * means that a connection broke or an extend failed. For now,
1595 * just give up: for circ to close, and return 0.
1597 int circuit_truncated(circuit_t
*circ
, crypt_path_t
*layer
) {
1598 crypt_path_t
*victim
;
1599 connection_t
*stream
;
1601 tor_assert(circ
&& CIRCUIT_IS_ORIGIN(circ
));
1604 /* XXX Since we don't ask for truncates currently, getting a truncated
1605 * means that a connection broke or an extend failed. For now,
1608 circuit_mark_for_close(circ
);
1611 while(layer
->next
!= circ
->cpath
) {
1612 /* we need to clear out layer->next */
1613 victim
= layer
->next
;
1614 log_fn(LOG_DEBUG
, "Killing a layer of the cpath.");
1616 for(stream
= circ
->p_streams
; stream
; stream
=stream
->next_stream
) {
1617 if(stream
->cpath_layer
== victim
) {
1618 log_fn(LOG_INFO
, "Marking stream %d for close.", stream
->stream_id
);
1619 /* no need to send 'end' relay cells,
1620 * because the other side's already dead
1622 connection_mark_for_close(stream
,0);
1626 layer
->next
= victim
->next
;
1627 circuit_free_cpath_node(victim
);
1630 log_fn(LOG_INFO
, "finished");
1634 /** Verify that cpath layer <b>cp</b> has all of its invariants
1635 * correct. Trigger an assert if anything is invalid.
1637 void assert_cpath_layer_ok(const crypt_path_t
*cp
)
1639 tor_assert(cp
->f_crypto
);
1640 tor_assert(cp
->b_crypto
);
1641 // tor_assert(cp->addr); /* these are zero for rendezvous extra-hops */
1642 // tor_assert(cp->port);
1645 case CPATH_STATE_CLOSED
:
1646 case CPATH_STATE_OPEN
:
1647 tor_assert(!cp
->handshake_state
);
1649 case CPATH_STATE_AWAITING_KEYS
:
1650 tor_assert(cp
->handshake_state
);
1655 tor_assert(cp
->package_window
>= 0);
1656 tor_assert(cp
->deliver_window
>= 0);
1659 /** Verify that cpath <b>cp</b> has all of its invariants
1660 * correct. Trigger an assert if anything is invalid.
1662 void assert_cpath_ok(const crypt_path_t
*cp
)
1668 assert_cpath_layer_ok(cp
);
1669 /* layers must be in sequence of: "open* awaiting? closed*" */
1671 if (cp
->prev
->state
== CPATH_STATE_OPEN
) {
1672 tor_assert(cp
->state
== CPATH_STATE_CLOSED
||
1673 cp
->state
== CPATH_STATE_AWAITING_KEYS
);
1675 tor_assert(cp
->state
== CPATH_STATE_CLOSED
);
1682 /** Verify that circuit <b>c</b> has all of its invariants
1683 * correct. Trigger an assert if anything is invalid.
1685 void assert_circuit_ok(const circuit_t
*c
)
1690 tor_assert(c
->magic
== CIRCUIT_MAGIC
);
1691 tor_assert(c
->purpose
>= _CIRCUIT_PURPOSE_MIN
&&
1692 c
->purpose
<= _CIRCUIT_PURPOSE_MAX
);
1695 tor_assert(c
->n_conn
->type
== CONN_TYPE_OR
);
1697 tor_assert(c
->p_conn
->type
== CONN_TYPE_OR
);
1698 for (conn
= c
->p_streams
; conn
; conn
= conn
->next_stream
)
1699 tor_assert(conn
->type
== CONN_TYPE_AP
);
1700 for (conn
= c
->n_streams
; conn
; conn
= conn
->next_stream
)
1701 tor_assert(conn
->type
== CONN_TYPE_EXIT
);
1703 tor_assert(c
->deliver_window
>= 0);
1704 tor_assert(c
->package_window
>= 0);
1705 if (c
->state
== CIRCUIT_STATE_OPEN
) {
1707 tor_assert(CIRCUIT_IS_ORIGIN(c
));
1708 tor_assert(!c
->n_crypto
);
1709 tor_assert(!c
->p_crypto
);
1710 tor_assert(!c
->n_digest
);
1711 tor_assert(!c
->p_digest
);
1713 tor_assert(!CIRCUIT_IS_ORIGIN(c
));
1714 tor_assert(c
->n_crypto
);
1715 tor_assert(c
->p_crypto
);
1716 tor_assert(c
->n_digest
);
1717 tor_assert(c
->p_digest
);
1721 //XXX assert_cpath_ok(c->cpath);
1723 if (c
->purpose
== CIRCUIT_PURPOSE_REND_ESTABLISHED
) {
1724 if (!c
->marked_for_close
) {
1725 tor_assert(c
->rend_splice
);
1726 tor_assert(c
->rend_splice
->rend_splice
== c
);
1728 tor_assert(c
->rend_splice
!= c
);
1730 tor_assert(!c
->rend_splice
);
1737 indent-tabs-mode:nil