1 /* Copyright (c) 2001 Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4 * Copyright (c) 2007-2012, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
9 * \brief The actual details of building circuits.
14 #include "circuitbuild.h"
15 #include "circuitlist.h"
16 #include "circuitstats.h"
17 #include "circuituse.h"
20 #include "confparse.h"
21 #include "connection.h"
22 #include "connection_edge.h"
23 #include "connection_or.h"
25 #include "directory.h"
26 #include "entrynodes.h"
28 #include "networkstatus.h"
32 #include "transports.h"
36 #include "routerlist.h"
37 #include "routerparse.h"
38 #include "routerset.h"
42 #define MIN(a,b) ((a)<(b)?(a):(b))
45 /********* START VARIABLES **********/
47 /** A global list of all circuits at this hop. */
48 extern circuit_t
*global_circuitlist
;
50 /********* END VARIABLES ************/
52 static channel_t
* channel_connect_for_circuit(const tor_addr_t
*addr
,
54 const char *id_digest
);
55 static int circuit_deliver_create_cell(circuit_t
*circ
,
56 uint8_t cell_type
, const char *payload
);
57 static int onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
);
58 static crypt_path_t
*onion_next_hop_in_cpath(crypt_path_t
*cpath
);
59 static int onion_extend_cpath(origin_circuit_t
*circ
);
60 static int count_acceptable_nodes(smartlist_t
*routers
);
61 static int onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
);
62 static int entry_guard_inc_circ_attempt_count(entry_guard_t
*guard
);
63 static void pathbias_count_build_success(origin_circuit_t
*circ
);
64 static void pathbias_count_successful_close(origin_circuit_t
*circ
);
65 static void pathbias_count_collapse(origin_circuit_t
*circ
);
66 static void pathbias_count_unusable(origin_circuit_t
*circ
);
68 /** This function tries to get a channel to the specified endpoint,
69 * and then calls command_setup_channel() to give it the right
73 channel_connect_for_circuit(const tor_addr_t
*addr
, uint16_t port
,
74 const char *id_digest
)
78 chan
= channel_connect(addr
, port
, id_digest
);
79 if (chan
) command_setup_channel(chan
);
84 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
85 * and with the high bit specified by conn-\>circ_id_type, until we get
86 * a circ_id that is not in use by any other circuit on that conn.
88 * Return it, or 0 if can't get a unique circ_id.
91 get_unique_circ_id_by_chan(channel_t
*chan
)
93 circid_t test_circ_id
;
99 if (chan
->circ_id_type
== CIRC_ID_TYPE_NEITHER
) {
101 "Trying to pick a circuit ID for a connection from "
102 "a client with no identity.");
106 (chan
->circ_id_type
== CIRC_ID_TYPE_HIGHER
) ? 1<<15 : 0;
108 /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
109 * circID such that (high_bit|test_circ_id) is not already used. */
110 test_circ_id
= chan
->next_circ_id
++;
111 if (test_circ_id
== 0 || test_circ_id
>= 1<<15) {
113 chan
->next_circ_id
= 2;
115 if (++attempts
> 1<<15) {
116 /* Make sure we don't loop forever if all circ_id's are used. This
117 * matters because it's an external DoS opportunity.
119 log_warn(LD_CIRC
,"No unused circ IDs. Failing.");
122 test_circ_id
|= high_bit
;
123 } while (circuit_id_in_use_on_channel(test_circ_id
, chan
));
127 /** If <b>verbose</b> is false, allocate and return a comma-separated list of
128 * the currently built elements of <b>circ</b>. If <b>verbose</b> is true, also
129 * list information about link status in a more verbose format using spaces.
130 * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
131 * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
135 circuit_list_path_impl(origin_circuit_t
*circ
, int verbose
, int verbose_names
)
138 smartlist_t
*elements
;
139 const char *states
[] = {"closed", "waiting for keys", "open"};
142 elements
= smartlist_new();
145 const char *nickname
= build_state_get_exit_nickname(circ
->build_state
);
146 smartlist_add_asprintf(elements
, "%s%s circ (length %d%s%s):",
147 circ
->build_state
->is_internal
? "internal" : "exit",
148 circ
->build_state
->need_uptime
? " (high-uptime)" : "",
149 circ
->build_state
->desired_path_len
,
150 circ
->base_
.state
== CIRCUIT_STATE_OPEN
? "" : ", last hop ",
151 circ
->base_
.state
== CIRCUIT_STATE_OPEN
? "" :
152 (nickname
?nickname
:"*unnamed*"));
162 if (!verbose
&& hop
->state
!= CPATH_STATE_OPEN
)
164 if (!hop
->extend_info
)
166 id
= hop
->extend_info
->identity_digest
;
168 elt
= tor_malloc(MAX_VERBOSE_NICKNAME_LEN
+1);
169 if ((node
= node_get_by_id(id
))) {
170 node_get_verbose_nickname(node
, elt
);
171 } else if (is_legal_nickname(hop
->extend_info
->nickname
)) {
173 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
174 elt
[HEX_DIGEST_LEN
+1]= '~';
175 strlcpy(elt
+HEX_DIGEST_LEN
+2,
176 hop
->extend_info
->nickname
, MAX_NICKNAME_LEN
+1);
179 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
181 } else { /* ! verbose_names */
182 node
= node_get_by_id(id
);
183 if (node
&& node_is_named(node
)) {
184 elt
= tor_strdup(node_get_nickname(node
));
186 elt
= tor_malloc(HEX_DIGEST_LEN
+2);
188 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
193 tor_assert(hop
->state
<= 2);
194 smartlist_add_asprintf(elements
,"%s(%s)",elt
,states
[hop
->state
]);
197 smartlist_add(elements
, elt
);
200 } while (hop
!= circ
->cpath
);
202 s
= smartlist_join_strings(elements
, verbose
?" ":",", 0, NULL
);
203 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
204 smartlist_free(elements
);
208 /** If <b>verbose</b> is false, allocate and return a comma-separated
209 * list of the currently built elements of <b>circ</b>. If
210 * <b>verbose</b> is true, also list information about link status in
211 * a more verbose format using spaces.
214 circuit_list_path(origin_circuit_t
*circ
, int verbose
)
216 return circuit_list_path_impl(circ
, verbose
, 0);
219 /** Allocate and return a comma-separated list of the currently built elements
220 * of <b>circ</b>, giving each as a verbose nickname.
223 circuit_list_path_for_controller(origin_circuit_t
*circ
)
225 return circuit_list_path_impl(circ
, 0, 1);
228 /** Log, at severity <b>severity</b>, the nicknames of each router in
229 * <b>circ</b>'s cpath. Also log the length of the cpath, and the intended
233 circuit_log_path(int severity
, unsigned int domain
, origin_circuit_t
*circ
)
235 char *s
= circuit_list_path(circ
,1);
236 tor_log(severity
,domain
,"%s",s
);
240 /** Tell the rep(utation)hist(ory) module about the status of the links
241 * in <b>circ</b>. Hops that have become OPEN are marked as successfully
242 * extended; the _first_ hop that isn't open (if any) is marked as
245 /* XXXX Someday we should learn from OR circuits too. */
247 circuit_rep_hist_note_result(origin_circuit_t
*circ
)
250 const char *prev_digest
= NULL
;
252 if (!hop
) /* circuit hasn't started building yet. */
254 if (server_mode(get_options())) {
255 const routerinfo_t
*me
= router_get_my_routerinfo();
258 prev_digest
= me
->cache_info
.identity_digest
;
261 const node_t
*node
= node_get_by_id(hop
->extend_info
->identity_digest
);
262 if (node
) { /* Why do we check this? We know the identity. -NM XXXX */
264 if (hop
->state
== CPATH_STATE_OPEN
)
265 rep_hist_note_extend_succeeded(prev_digest
, node
->identity
);
267 rep_hist_note_extend_failed(prev_digest
, node
->identity
);
271 prev_digest
= node
->identity
;
276 } while (hop
!=circ
->cpath
);
279 /** Pick all the entries in our cpath. Stop and return 0 when we're
280 * happy, or return -1 if an error occurs. */
282 onion_populate_cpath(origin_circuit_t
*circ
)
286 r
= onion_extend_cpath(circ
);
288 log_info(LD_CIRC
,"Generating cpath hop failed.");
293 return 0; /* if r == 1 */
296 /** Create and return a new origin circuit. Initialize its purpose and
297 * build-state based on our arguments. The <b>flags</b> argument is a
298 * bitfield of CIRCLAUNCH_* flags. */
300 origin_circuit_init(uint8_t purpose
, int flags
)
302 /* sets circ->p_circ_id and circ->p_chan */
303 origin_circuit_t
*circ
= origin_circuit_new();
304 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_CHAN_WAIT
);
305 circ
->build_state
= tor_malloc_zero(sizeof(cpath_build_state_t
));
306 circ
->build_state
->onehop_tunnel
=
307 ((flags
& CIRCLAUNCH_ONEHOP_TUNNEL
) ? 1 : 0);
308 circ
->build_state
->need_uptime
=
309 ((flags
& CIRCLAUNCH_NEED_UPTIME
) ? 1 : 0);
310 circ
->build_state
->need_capacity
=
311 ((flags
& CIRCLAUNCH_NEED_CAPACITY
) ? 1 : 0);
312 circ
->build_state
->is_internal
=
313 ((flags
& CIRCLAUNCH_IS_INTERNAL
) ? 1 : 0);
314 circ
->base_
.purpose
= purpose
;
318 /** Build a new circuit for <b>purpose</b>. If <b>exit</b>
319 * is defined, then use that as your exit router, else choose a suitable
322 * Also launch a connection to the first OR in the chosen path, if
323 * it's not open already.
326 circuit_establish_circuit(uint8_t purpose
, extend_info_t
*exit
, int flags
)
328 origin_circuit_t
*circ
;
331 circ
= origin_circuit_init(purpose
, flags
);
333 if (onion_pick_cpath_exit(circ
, exit
) < 0 ||
334 onion_populate_cpath(circ
) < 0) {
335 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_NOPATH
);
339 control_event_circuit_status(circ
, CIRC_EVENT_LAUNCHED
, 0);
341 if ((err_reason
= circuit_handle_first_hop(circ
)) < 0) {
342 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
348 /** Start establishing the first hop of our circuit. Figure out what
349 * OR we should connect to, and if necessary start the connection to
350 * it. If we're already connected, then send the 'create' cell.
351 * Return 0 for ok, -reason if circ should be marked-for-close. */
353 circuit_handle_first_hop(origin_circuit_t
*circ
)
355 crypt_path_t
*firsthop
;
358 const char *msg
= NULL
;
359 int should_launch
= 0;
361 firsthop
= onion_next_hop_in_cpath(circ
->cpath
);
362 tor_assert(firsthop
);
363 tor_assert(firsthop
->extend_info
);
365 /* now see if we're already connected to the first OR in 'route' */
366 log_debug(LD_CIRC
,"Looking for firsthop '%s'",
367 fmt_addrport(&firsthop
->extend_info
->addr
,
368 firsthop
->extend_info
->port
));
370 n_chan
= channel_get_for_extend(firsthop
->extend_info
->identity_digest
,
371 &firsthop
->extend_info
->addr
,
376 /* not currently connected in a useful way. */
377 log_info(LD_CIRC
, "Next router is %s: %s",
378 safe_str_client(extend_info_describe(firsthop
->extend_info
)),
380 circ
->base_
.n_hop
= extend_info_dup(firsthop
->extend_info
);
383 if (circ
->build_state
->onehop_tunnel
)
384 control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR
, 0);
385 n_chan
= channel_connect_for_circuit(
386 &firsthop
->extend_info
->addr
,
387 firsthop
->extend_info
->port
,
388 firsthop
->extend_info
->identity_digest
);
389 if (!n_chan
) { /* connect failed, forget the whole thing */
390 log_info(LD_CIRC
,"connect to firsthop failed. Closing.");
391 return -END_CIRC_REASON_CONNECTFAILED
;
395 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
396 /* return success. The onion/circuit/etc will be taken care of
397 * automatically (may already have been) whenever n_chan reaches
398 * OR_CONN_STATE_OPEN.
401 } else { /* it's already open. use it. */
402 tor_assert(!circ
->base_
.n_hop
);
403 circ
->base_
.n_chan
= n_chan
;
404 log_debug(LD_CIRC
,"Conn open. Delivering first onion skin.");
405 if ((err_reason
= circuit_send_next_onion_skin(circ
)) < 0) {
406 log_info(LD_CIRC
,"circuit_send_next_onion_skin failed.");
413 /** Find any circuits that are waiting on <b>or_conn</b> to become
414 * open and get them to send their create cells forward.
416 * Status is 1 if connect succeeded, or 0 if connect failed.
419 circuit_n_chan_done(channel_t
*chan
, int status
)
421 smartlist_t
*pending_circs
;
426 log_debug(LD_CIRC
,"chan to %s/%s, status=%d",
427 chan
->nickname
? chan
->nickname
: "NULL",
428 channel_get_canonical_remote_descr(chan
), status
);
430 pending_circs
= smartlist_new();
431 circuit_get_all_pending_on_channel(pending_circs
, chan
);
433 SMARTLIST_FOREACH_BEGIN(pending_circs
, circuit_t
*, circ
)
435 /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
436 * leaving them in in case it's possible for the status of a circuit to
437 * change as we're going down the list. */
438 if (circ
->marked_for_close
|| circ
->n_chan
|| !circ
->n_hop
||
439 circ
->state
!= CIRCUIT_STATE_CHAN_WAIT
)
442 if (tor_digest_is_zero(circ
->n_hop
->identity_digest
)) {
443 /* Look at addr/port. This is an unkeyed connection. */
444 if (!channel_matches_extend_info(chan
, circ
->n_hop
))
447 /* We expected a key. See if it's the right one. */
448 if (tor_memneq(chan
->identity_digest
,
449 circ
->n_hop
->identity_digest
, DIGEST_LEN
))
452 if (!status
) { /* chan failed; close circ */
453 log_info(LD_CIRC
,"Channel failed; closing circ.");
454 circuit_mark_for_close(circ
, END_CIRC_REASON_CHANNEL_CLOSED
);
457 log_debug(LD_CIRC
, "Found circ, sending create cell.");
458 /* circuit_deliver_create_cell will set n_circ_id and add us to
459 * chan_circuid_circuit_map, so we don't need to call
460 * set_circid_chan here. */
462 extend_info_free(circ
->n_hop
);
465 if (CIRCUIT_IS_ORIGIN(circ
)) {
467 circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ
))) < 0) {
469 "send_next_onion_skin failed; circuit marked for closing.");
470 circuit_mark_for_close(circ
, -err_reason
);
472 /* XXX could this be bad, eg if next_onion_skin failed because conn
476 /* pull the create cell out of circ->onionskin, and send it */
477 tor_assert(circ
->n_chan_onionskin
);
478 if (circuit_deliver_create_cell(circ
,CELL_CREATE
,
479 circ
->n_chan_onionskin
)<0) {
480 circuit_mark_for_close(circ
, END_CIRC_REASON_RESOURCELIMIT
);
483 tor_free(circ
->n_chan_onionskin
);
484 circuit_set_state(circ
, CIRCUIT_STATE_OPEN
);
487 SMARTLIST_FOREACH_END(circ
);
489 smartlist_free(pending_circs
);
492 /** Find a new circid that isn't currently in use on the circ->n_chan
494 * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
495 * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
497 * Return -1 if we failed to find a suitable circid, else return 0.
500 circuit_deliver_create_cell(circuit_t
*circ
, uint8_t cell_type
,
507 tor_assert(circ
->n_chan
);
509 tor_assert(cell_type
== CELL_CREATE
|| cell_type
== CELL_CREATE_FAST
);
511 id
= get_unique_circ_id_by_chan(circ
->n_chan
);
513 log_warn(LD_CIRC
,"failed to get unique circID.");
516 log_debug(LD_CIRC
,"Chosen circID %u.", id
);
517 circuit_set_n_circid_chan(circ
, id
, circ
->n_chan
);
519 memset(&cell
, 0, sizeof(cell_t
));
520 cell
.command
= cell_type
;
521 cell
.circ_id
= circ
->n_circ_id
;
523 memcpy(cell
.payload
, payload
, ONIONSKIN_CHALLENGE_LEN
);
524 append_cell_to_circuit_queue(circ
, circ
->n_chan
, &cell
,
525 CELL_DIRECTION_OUT
, 0);
527 if (CIRCUIT_IS_ORIGIN(circ
)) {
528 /* Update began timestamp for circuits starting their first hop */
529 if (TO_ORIGIN_CIRCUIT(circ
)->cpath
->state
== CPATH_STATE_CLOSED
) {
530 if (circ
->n_chan
->state
!= CHANNEL_STATE_OPEN
) {
532 "Got first hop for a circuit without an opened channel. "
533 "State: %s.", channel_state_to_string(circ
->n_chan
->state
));
534 tor_fragile_assert();
537 tor_gettimeofday(&circ
->timestamp_began
);
540 /* mark it so it gets better rate limiting treatment. */
541 channel_timestamp_client(circ
->n_chan
);
547 /** We've decided to start our reachability testing. If all
548 * is set, log this to the user. Return 1 if we did, or 0 if
549 * we chose not to log anything. */
551 inform_testing_reachability(void)
554 const routerinfo_t
*me
= router_get_my_routerinfo();
557 control_event_server_status(LOG_NOTICE
,
558 "CHECKING_REACHABILITY ORADDRESS=%s:%d",
559 me
->address
, me
->or_port
);
561 tor_snprintf(dirbuf
, sizeof(dirbuf
), " and DirPort %s:%d",
562 me
->address
, me
->dir_port
);
563 control_event_server_status(LOG_NOTICE
,
564 "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
565 me
->address
, me
->dir_port
);
567 log_notice(LD_OR
, "Now checking whether ORPort %s:%d%s %s reachable... "
568 "(this may take up to %d minutes -- look for log "
569 "messages indicating success)",
570 me
->address
, me
->or_port
,
571 me
->dir_port
? dirbuf
: "",
572 me
->dir_port
? "are" : "is",
573 TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT
/60);
578 /** Return true iff we should send a create_fast cell to start building a given
581 should_use_create_fast_for_circuit(origin_circuit_t
*circ
)
583 const or_options_t
*options
= get_options();
584 tor_assert(circ
->cpath
);
585 tor_assert(circ
->cpath
->extend_info
);
587 if (!circ
->cpath
->extend_info
->onion_key
)
588 return 1; /* our hand is forced: only a create_fast will work. */
589 if (!options
->FastFirstHopPK
)
590 return 0; /* we prefer to avoid create_fast */
591 if (public_server_mode(options
)) {
592 /* We're a server, and we know an onion key. We can choose.
593 * Prefer to blend our circuit into the other circuits we are
594 * creating on behalf of others. */
601 /** Return true if <b>circ</b> is the type of circuit we want to count
602 * timeouts from. In particular, we want it to have not completed yet
603 * (already completing indicates we cannibalized it), and we want it to
604 * have exactly three hops.
607 circuit_timeout_want_to_count_circ(origin_circuit_t
*circ
)
609 return !circ
->has_opened
610 && circ
->build_state
->desired_path_len
== DEFAULT_ROUTE_LEN
;
613 /** This is the backbone function for building circuits.
615 * If circ's first hop is closed, then we need to build a create
616 * cell and send it forward.
618 * Otherwise, we need to build a relay extend cell and send it
621 * Return -reason if we want to tear down circ, else return 0.
624 circuit_send_next_onion_skin(origin_circuit_t
*circ
)
628 char payload
[2+4+DIGEST_LEN
+ONIONSKIN_CHALLENGE_LEN
];
634 if (circ
->cpath
->state
== CPATH_STATE_CLOSED
) {
637 log_debug(LD_CIRC
,"First skin; sending create cell.");
638 if (circ
->build_state
->onehop_tunnel
)
639 control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE
, 0);
641 control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE
, 0);
643 node
= node_get_by_id(circ
->base_
.n_chan
->identity_digest
);
644 fast
= should_use_create_fast_for_circuit(circ
);
646 /* We are an OR and we know the right onion key: we should
647 * send an old slow create cell.
649 cell_type
= CELL_CREATE
;
650 if (onion_skin_create(circ
->cpath
->extend_info
->onion_key
,
651 &(circ
->cpath
->dh_handshake_state
),
653 log_warn(LD_CIRC
,"onion_skin_create (first hop) failed.");
654 return - END_CIRC_REASON_INTERNAL
;
656 note_request("cell: create", 1);
658 /* We are not an OR, and we're building the first hop of a circuit to a
659 * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
660 * and a DH operation. */
661 cell_type
= CELL_CREATE_FAST
;
662 memset(payload
, 0, sizeof(payload
));
663 crypto_rand((char*) circ
->cpath
->fast_handshake_state
,
664 sizeof(circ
->cpath
->fast_handshake_state
));
665 memcpy(payload
, circ
->cpath
->fast_handshake_state
,
666 sizeof(circ
->cpath
->fast_handshake_state
));
667 note_request("cell: create fast", 1);
670 if (circuit_deliver_create_cell(TO_CIRCUIT(circ
), cell_type
, payload
) < 0)
671 return - END_CIRC_REASON_RESOURCELIMIT
;
673 circ
->cpath
->state
= CPATH_STATE_AWAITING_KEYS
;
674 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
675 log_info(LD_CIRC
,"First hop: finished sending %s cell to '%s'",
676 fast
? "CREATE_FAST" : "CREATE",
677 node
? node_describe(node
) : "<unnamed>");
679 tor_assert(circ
->cpath
->state
== CPATH_STATE_OPEN
);
680 tor_assert(circ
->base_
.state
== CIRCUIT_STATE_BUILDING
);
681 log_debug(LD_CIRC
,"starting to send subsequent skin.");
682 hop
= onion_next_hop_in_cpath(circ
->cpath
);
684 /* done building the circuit. whew. */
685 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
686 if (circuit_timeout_want_to_count_circ(circ
)) {
689 tor_gettimeofday(&end
);
690 timediff
= tv_mdiff(&circ
->base_
.timestamp_began
, &end
);
693 * If the circuit build time is much greater than we would have cut
694 * it off at, we probably had a suspend event along this codepath,
695 * and we should discard the value.
697 if (timediff
< 0 || timediff
> 2*circ_times
.close_ms
+1000) {
698 log_notice(LD_CIRC
, "Strange value for circuit build time: %ldmsec. "
699 "Assuming clock jump. Purpose %d (%s)", timediff
,
701 circuit_purpose_to_string(circ
->base_
.purpose
));
702 } else if (!circuit_build_times_disabled()) {
703 /* Only count circuit times if the network is live */
704 if (circuit_build_times_network_check_live(&circ_times
)) {
705 circuit_build_times_add_time(&circ_times
, (build_time_t
)timediff
);
706 circuit_build_times_set_timeout(&circ_times
);
709 if (circ
->base_
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
710 circuit_build_times_network_circ_success(&circ_times
);
714 log_info(LD_CIRC
,"circuit built!");
715 circuit_reset_failure_count(0);
717 if (circ
->build_state
->onehop_tunnel
|| circ
->has_opened
) {
718 control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS
, 0);
721 if (!can_complete_circuit
&& !circ
->build_state
->onehop_tunnel
) {
722 const or_options_t
*options
= get_options();
723 can_complete_circuit
=1;
724 /* FFFF Log a count of known routers here */
725 log_notice(LD_GENERAL
,
726 "Tor has successfully opened a circuit. "
727 "Looks like client functionality is working.");
728 control_event_bootstrap(BOOTSTRAP_STATUS_DONE
, 0);
729 control_event_client_status(LOG_NOTICE
, "CIRCUIT_ESTABLISHED");
730 clear_broken_connection_map(1);
731 if (server_mode(options
) && !check_whether_orport_reachable()) {
732 inform_testing_reachability();
733 consider_testing_reachability(1, 1);
737 pathbias_count_build_success(circ
);
738 circuit_rep_hist_note_result(circ
);
739 circuit_has_opened(circ
); /* do other actions as necessary */
741 /* We're done with measurement circuits here. Just close them */
742 if (circ
->base_
.purpose
== CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
743 /* If a measurement circ ever gets back to us, consider it
744 * succeeded for path bias */
745 circ
->path_state
= PATH_STATE_USE_SUCCEEDED
;
746 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_FINISHED
);
751 if (tor_addr_family(&hop
->extend_info
->addr
) != AF_INET
) {
752 log_warn(LD_BUG
, "Trying to extend to a non-IPv4 address.");
753 return - END_CIRC_REASON_INTERNAL
;
756 set_uint32(payload
, tor_addr_to_ipv4n(&hop
->extend_info
->addr
));
757 set_uint16(payload
+4, htons(hop
->extend_info
->port
));
759 onionskin
= payload
+2+4;
760 memcpy(payload
+2+4+ONIONSKIN_CHALLENGE_LEN
,
761 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
762 payload_len
= 2+4+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
;
764 if (onion_skin_create(hop
->extend_info
->onion_key
,
765 &(hop
->dh_handshake_state
), onionskin
) < 0) {
766 log_warn(LD_CIRC
,"onion_skin_create failed.");
767 return - END_CIRC_REASON_INTERNAL
;
770 log_info(LD_CIRC
,"Sending extend relay cell.");
771 note_request("cell: extend", 1);
772 /* send it to hop->prev, because it will transfer
773 * it to a create cell and then send to hop */
774 if (relay_send_command_from_edge(0, TO_CIRCUIT(circ
),
775 RELAY_COMMAND_EXTEND
,
776 payload
, payload_len
, hop
->prev
) < 0)
777 return 0; /* circuit is closed */
779 hop
->state
= CPATH_STATE_AWAITING_KEYS
;
784 /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
785 * something has also gone wrong with our network: notify the user,
786 * and abandon all not-yet-used circuits. */
788 circuit_note_clock_jumped(int seconds_elapsed
)
790 int severity
= server_mode(get_options()) ? LOG_WARN
: LOG_NOTICE
;
791 tor_log(severity
, LD_GENERAL
, "Your system clock just jumped %d seconds %s; "
792 "assuming established circuits no longer work.",
793 seconds_elapsed
>=0 ? seconds_elapsed
: -seconds_elapsed
,
794 seconds_elapsed
>=0 ? "forward" : "backward");
795 control_event_general_status(LOG_WARN
, "CLOCK_JUMPED TIME=%d",
797 can_complete_circuit
=0; /* so it'll log when it works again */
798 control_event_client_status(severity
, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
800 circuit_mark_all_unused_circs();
801 circuit_expire_all_dirty_circs();
804 /** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
805 * skin and identity digest for the next hop. If we're already connected,
806 * pass the onion skin to the next hop using a create cell; otherwise
807 * launch a new OR connection, and <b>circ</b> will notice when the
808 * connection succeeds or fails.
810 * Return -1 if we want to warn and tear down the circuit, else return 0.
813 circuit_extend(cell_t
*cell
, circuit_t
*circ
)
818 char *id_digest
=NULL
;
822 const char *msg
= NULL
;
823 int should_launch
= 0;
826 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
827 "n_chan already set. Bug/attack. Closing.");
831 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
832 "conn to next hop already launched. Bug/attack. Closing.");
836 if (!server_mode(get_options())) {
837 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
838 "Got an extend cell, but running as a client. Closing.");
842 relay_header_unpack(&rh
, cell
->payload
);
844 if (rh
.length
< 4+2+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
) {
845 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
846 "Wrong length %d on extend cell. Closing circuit.",
851 n_addr32
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
));
852 n_port
= ntohs(get_uint16(cell
->payload
+RELAY_HEADER_SIZE
+4));
853 onionskin
= (char*) cell
->payload
+RELAY_HEADER_SIZE
+4+2;
854 id_digest
= (char*) cell
->payload
+RELAY_HEADER_SIZE
+4+2+
855 ONIONSKIN_CHALLENGE_LEN
;
856 tor_addr_from_ipv4h(&n_addr
, n_addr32
);
858 if (!n_port
|| !n_addr32
) {
859 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
860 "Client asked me to extend to zero destination port or addr.");
864 if (tor_addr_is_internal(&n_addr
, 0) &&
865 !get_options()->ExtendAllowPrivateAddresses
) {
866 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
867 "Client asked me to extend to a private address");
871 /* Check if they asked us for 0000..0000. We support using
872 * an empty fingerprint for the first hop (e.g. for a bridge relay),
873 * but we don't want to let people send us extend cells for empty
874 * fingerprints -- a) because it opens the user up to a mitm attack,
875 * and b) because it lets an attacker force the relay to hold open a
876 * new TLS connection for each extend request. */
877 if (tor_digest_is_zero(id_digest
)) {
878 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
879 "Client asked me to extend without specifying an id_digest.");
883 /* Next, check if we're being asked to connect to the hop that the
884 * extend cell came from. There isn't any reason for that, and it can
885 * assist circular-path attacks. */
886 if (tor_memeq(id_digest
,
887 TO_OR_CIRCUIT(circ
)->p_chan
->identity_digest
,
889 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
890 "Client asked me to extend back to the previous hop.");
894 n_chan
= channel_get_for_extend(id_digest
,
900 log_debug(LD_CIRC
|LD_OR
,"Next router (%s): %s",
901 fmt_addrport(&n_addr
, n_port
), msg
?msg
:"????");
903 circ
->n_hop
= extend_info_new(NULL
/*nickname*/,
908 circ
->n_chan_onionskin
= tor_malloc(ONIONSKIN_CHALLENGE_LEN
);
909 memcpy(circ
->n_chan_onionskin
, onionskin
, ONIONSKIN_CHALLENGE_LEN
);
910 circuit_set_state(circ
, CIRCUIT_STATE_CHAN_WAIT
);
913 /* we should try to open a connection */
914 n_chan
= channel_connect_for_circuit(&n_addr
, n_port
, id_digest
);
916 log_info(LD_CIRC
,"Launching n_chan failed. Closing circuit.");
917 circuit_mark_for_close(circ
, END_CIRC_REASON_CONNECTFAILED
);
920 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
922 /* return success. The onion/circuit/etc will be taken care of
923 * automatically (may already have been) whenever n_chan reaches
924 * OR_CONN_STATE_OPEN.
929 tor_assert(!circ
->n_hop
); /* Connection is already established. */
930 circ
->n_chan
= n_chan
;
933 channel_get_canonical_remote_descr(n_chan
));
935 if (circuit_deliver_create_cell(circ
, CELL_CREATE
, onionskin
) < 0)
940 /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
941 * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
943 * - 20 to initialize f_digest
944 * - 20 to initialize b_digest
945 * - 16 to key f_crypto
946 * - 16 to key b_crypto
948 * (If 'reverse' is true, then f_XX and b_XX are swapped.)
951 circuit_init_cpath_crypto(crypt_path_t
*cpath
, const char *key_data
,
954 crypto_digest_t
*tmp_digest
;
955 crypto_cipher_t
*tmp_crypto
;
958 tor_assert(key_data
);
959 tor_assert(!(cpath
->f_crypto
|| cpath
->b_crypto
||
960 cpath
->f_digest
|| cpath
->b_digest
));
962 cpath
->f_digest
= crypto_digest_new();
963 crypto_digest_add_bytes(cpath
->f_digest
, key_data
, DIGEST_LEN
);
964 cpath
->b_digest
= crypto_digest_new();
965 crypto_digest_add_bytes(cpath
->b_digest
, key_data
+DIGEST_LEN
, DIGEST_LEN
);
967 if (!(cpath
->f_crypto
=
968 crypto_cipher_new(key_data
+(2*DIGEST_LEN
)))) {
969 log_warn(LD_BUG
,"Forward cipher initialization failed.");
972 if (!(cpath
->b_crypto
=
973 crypto_cipher_new(key_data
+(2*DIGEST_LEN
)+CIPHER_KEY_LEN
))) {
974 log_warn(LD_BUG
,"Backward cipher initialization failed.");
979 tmp_digest
= cpath
->f_digest
;
980 cpath
->f_digest
= cpath
->b_digest
;
981 cpath
->b_digest
= tmp_digest
;
982 tmp_crypto
= cpath
->f_crypto
;
983 cpath
->f_crypto
= cpath
->b_crypto
;
984 cpath
->b_crypto
= tmp_crypto
;
990 /** The minimum number of circuit attempts before we start
991 * thinking about warning about path bias and dropping guards */
993 pathbias_get_min_circs(const or_options_t
*options
)
995 #define DFLT_PATH_BIAS_MIN_CIRC 150
996 if (options
->PathBiasCircThreshold
>= 5)
997 return options
->PathBiasCircThreshold
;
999 return networkstatus_get_param(NULL
, "pb_mincircs",
1000 DFLT_PATH_BIAS_MIN_CIRC
,
1004 /** The circuit success rate below which we issue a notice */
1006 pathbias_get_notice_rate(const or_options_t
*options
)
1008 #define DFLT_PATH_BIAS_NOTICE_PCT 70
1009 if (options
->PathBiasNoticeRate
>= 0.0)
1010 return options
->PathBiasNoticeRate
;
1012 return networkstatus_get_param(NULL
, "pb_noticepct",
1013 DFLT_PATH_BIAS_NOTICE_PCT
, 0, 100)/100.0;
1016 /* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
1017 /** The circuit success rate below which we issue a warn */
1019 pathbias_get_warn_rate(const or_options_t
*options
)
1021 #define DFLT_PATH_BIAS_WARN_PCT 50
1022 if (options
->PathBiasWarnRate
>= 0.0)
1023 return options
->PathBiasWarnRate
;
1025 return networkstatus_get_param(NULL
, "pb_warnpct",
1026 DFLT_PATH_BIAS_WARN_PCT
, 0, 100)/100.0;
1029 /* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
1031 * The extreme rate is the rate at which we would drop the guard,
1032 * if pb_dropguard is also set. Otherwise we just warn.
1035 pathbias_get_extreme_rate(const or_options_t
*options
)
1037 #define DFLT_PATH_BIAS_EXTREME_PCT 30
1038 if (options
->PathBiasExtremeRate
>= 0.0)
1039 return options
->PathBiasExtremeRate
;
1041 return networkstatus_get_param(NULL
, "pb_extremepct",
1042 DFLT_PATH_BIAS_EXTREME_PCT
, 0, 100)/100.0;
1045 /* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
1047 * If 1, we actually disable use of guards that fall below
1051 pathbias_get_dropguards(const or_options_t
*options
)
1053 #define DFLT_PATH_BIAS_DROP_GUARDS 0
1054 if (options
->PathBiasDropGuards
>= 0)
1055 return options
->PathBiasDropGuards
;
1057 return networkstatus_get_param(NULL
, "pb_dropguards",
1058 DFLT_PATH_BIAS_DROP_GUARDS
, 0, 1);
1062 * This is the number of circuits at which we scale our
1063 * counts by mult_factor/scale_factor. Note, this count is
1064 * not exact, as we only perform the scaling in the event
1065 * of no integer truncation.
1068 pathbias_get_scale_threshold(const or_options_t
*options
)
1070 #define DFLT_PATH_BIAS_SCALE_THRESHOLD 300
1071 if (options
->PathBiasScaleThreshold
>= 10)
1072 return options
->PathBiasScaleThreshold
;
1074 return networkstatus_get_param(NULL
, "pb_scalecircs",
1075 DFLT_PATH_BIAS_SCALE_THRESHOLD
, 10,
1080 * The scale factor is the denominator for our scaling
1081 * of circuit counts for our path bias window.
1083 * Note that our use of doubles for the path bias state
1084 * file means that powers of 2 work best here.
1087 pathbias_get_scale_factor(const or_options_t
*options
)
1089 #define DFLT_PATH_BIAS_SCALE_FACTOR 2
1090 if (options
->PathBiasScaleFactor
>= 1)
1091 return options
->PathBiasScaleFactor
;
1093 return networkstatus_get_param(NULL
, "pb_scalefactor",
1094 DFLT_PATH_BIAS_SCALE_FACTOR
, 1, INT32_MAX
);
1098 * The mult factor is the numerator for our scaling
1099 * of circuit counts for our path bias window. It
1100 * allows us to scale by fractions.
1103 pathbias_get_mult_factor(const or_options_t
*options
)
1105 #define DFLT_PATH_BIAS_MULT_FACTOR 1
1106 if (options
->PathBiasMultFactor
>= 1)
1107 return options
->PathBiasMultFactor
;
1109 return networkstatus_get_param(NULL
, "pb_multfactor",
1110 DFLT_PATH_BIAS_MULT_FACTOR
, 1,
1111 pathbias_get_scale_factor(options
));
1115 * If this parameter is set to a true value (default), we use the
1116 * successful_circuits_closed. Otherwise, we use the success_count.
1119 pathbias_use_close_counts(const or_options_t
*options
)
1121 #define DFLT_PATH_BIAS_USE_CLOSE_COUNTS 1
1122 if (options
->PathBiasUseCloseCounts
>= 0)
1123 return options
->PathBiasUseCloseCounts
;
1125 return networkstatus_get_param(NULL
, "pb_useclosecounts",
1126 DFLT_PATH_BIAS_USE_CLOSE_COUNTS
, 0, 1);
1130 * Convert a Guard's path state to string.
1133 pathbias_state_to_string(path_state_t state
)
1136 case PATH_STATE_NEW_CIRC
:
1138 case PATH_STATE_BUILD_ATTEMPTED
:
1139 return "build attempted";
1140 case PATH_STATE_BUILD_SUCCEEDED
:
1141 return "build succeeded";
1142 case PATH_STATE_USE_SUCCEEDED
:
1143 return "use succeeded";
1144 case PATH_STATE_USE_FAILED
:
1145 return "use failed";
1152 * This function decides if a circuit has progressed far enough to count
1153 * as a circuit "attempt". As long as end-to-end tagging is possible,
1154 * we assume the adversary will use it over hop-to-hop failure. Therefore,
1155 * we only need to account bias for the last hop. This should make us
1156 * much more resilient to ambient circuit failure, and also make that
1157 * failure easier to measure (we only need to measure Exit failure rates).
1160 pathbias_is_new_circ_attempt(origin_circuit_t
*circ
)
1162 #define N2N_TAGGING_IS_POSSIBLE
1163 #ifdef N2N_TAGGING_IS_POSSIBLE
1164 /* cpath is a circular list. We want circs with more than one hop,
1165 * and the second hop must be waiting for keys still (it's just
1166 * about to get them). */
1167 return circ
->cpath
->next
!= circ
->cpath
&&
1168 circ
->cpath
->next
->state
== CPATH_STATE_AWAITING_KEYS
;
1170 /* If tagging attacks are no longer possible, we probably want to
1171 * count bias from the first hop. However, one could argue that
1172 * timing-based tagging is still more useful than per-hop failure.
1173 * In which case, we'd never want to use this.
1175 return circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
;
1180 * Decide if the path bias code should count a circuit.
1182 * @returns 1 if we should count it, 0 otherwise.
1185 pathbias_should_count(origin_circuit_t
*circ
)
1187 #define PATHBIAS_COUNT_INTERVAL (600)
1188 static ratelim_t count_limit
=
1189 RATELIM_INIT(PATHBIAS_COUNT_INTERVAL
);
1190 char *rate_msg
= NULL
;
1192 /* We can't do path bias accounting without entry guards.
1193 * Testing and controller circuits also have no guards.
1195 * We also don't count server-side rends, because their
1196 * endpoint could be chosen maliciously.
1197 * Similarly, we can't count client-side intro attempts,
1198 * because clients can be manipulated into connecting to
1199 * malicious intro points. */
1200 if (get_options()->UseEntryGuards
== 0 ||
1201 circ
->base_
.purpose
== CIRCUIT_PURPOSE_TESTING
||
1202 circ
->base_
.purpose
== CIRCUIT_PURPOSE_CONTROLLER
||
1203 circ
->base_
.purpose
== CIRCUIT_PURPOSE_S_CONNECT_REND
||
1204 circ
->base_
.purpose
== CIRCUIT_PURPOSE_S_REND_JOINED
||
1205 (circ
->base_
.purpose
>= CIRCUIT_PURPOSE_C_INTRODUCING
&&
1206 circ
->base_
.purpose
<= CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
)) {
1210 /* Completely ignore one hop circuits */
1211 if (circ
->build_state
->onehop_tunnel
||
1212 circ
->build_state
->desired_path_len
== 1) {
1213 /* Check for inconsistency */
1214 if (circ
->build_state
->desired_path_len
!= 1 ||
1215 !circ
->build_state
->onehop_tunnel
) {
1216 if ((rate_msg
= rate_limit_log(&count_limit
, approx_time()))) {
1218 "One-hop circuit has length %d. Path state is %s. "
1219 "Circuit is a %s currently %s.%s",
1220 circ
->build_state
->desired_path_len
,
1221 pathbias_state_to_string(circ
->path_state
),
1222 circuit_purpose_to_string(circ
->base_
.purpose
),
1223 circuit_state_to_string(circ
->base_
.state
),
1227 tor_fragile_assert();
1236 * Check our circuit state to see if this is a successful circuit attempt.
1237 * If so, record it in the current guard's path bias circ_attempt count.
1239 * Also check for several potential error cases for bug #6475.
1242 pathbias_count_circ_attempt(origin_circuit_t
*circ
)
1244 #define CIRC_ATTEMPT_NOTICE_INTERVAL (600)
1245 static ratelim_t circ_attempt_notice_limit
=
1246 RATELIM_INIT(CIRC_ATTEMPT_NOTICE_INTERVAL
);
1247 char *rate_msg
= NULL
;
1249 if (!pathbias_should_count(circ
)) {
1253 if (pathbias_is_new_circ_attempt(circ
)) {
1254 /* Help track down the real cause of bug #6475: */
1255 if (circ
->has_opened
&& circ
->path_state
!= PATH_STATE_BUILD_ATTEMPTED
) {
1256 if ((rate_msg
= rate_limit_log(&circ_attempt_notice_limit
,
1259 "Opened circuit is in strange path state %s. "
1260 "Circuit is a %s currently %s.%s",
1261 pathbias_state_to_string(circ
->path_state
),
1262 circuit_purpose_to_string(circ
->base_
.purpose
),
1263 circuit_state_to_string(circ
->base_
.state
),
1269 /* Don't re-count cannibalized circs.. */
1270 if (!circ
->has_opened
) {
1271 entry_guard_t
*guard
= NULL
;
1273 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1274 guard
= entry_guard_get_by_id_digest(
1275 circ
->cpath
->extend_info
->identity_digest
);
1276 } else if (circ
->base_
.n_chan
) {
1278 entry_guard_get_by_id_digest(circ
->base_
.n_chan
->identity_digest
);
1282 if (circ
->path_state
== PATH_STATE_NEW_CIRC
) {
1283 circ
->path_state
= PATH_STATE_BUILD_ATTEMPTED
;
1285 if (entry_guard_inc_circ_attempt_count(guard
) < 0) {
1286 /* Bogus guard; we already warned. */
1287 return -END_CIRC_REASON_TORPROTOCOL
;
1290 if ((rate_msg
= rate_limit_log(&circ_attempt_notice_limit
,
1293 "Unopened circuit has strange path state %s. "
1294 "Circuit is a %s currently %s.%s",
1295 pathbias_state_to_string(circ
->path_state
),
1296 circuit_purpose_to_string(circ
->base_
.purpose
),
1297 circuit_state_to_string(circ
->base_
.state
),
1303 if ((rate_msg
= rate_limit_log(&circ_attempt_notice_limit
,
1306 "Unopened circuit has no known guard. "
1307 "Circuit is a %s currently %s.%s",
1308 circuit_purpose_to_string(circ
->base_
.purpose
),
1309 circuit_state_to_string(circ
->base_
.state
),
1321 * Check our circuit state to see if this is a successful circuit
1322 * completion. If so, record it in the current guard's path bias
1325 * Also check for several potential error cases for bug #6475.
1328 pathbias_count_build_success(origin_circuit_t
*circ
)
1330 #define SUCCESS_NOTICE_INTERVAL (600)
1331 static ratelim_t success_notice_limit
=
1332 RATELIM_INIT(SUCCESS_NOTICE_INTERVAL
);
1333 char *rate_msg
= NULL
;
1334 entry_guard_t
*guard
= NULL
;
1336 if (!pathbias_should_count(circ
)) {
1340 /* Don't count cannibalized/reused circs for path bias
1341 * build success.. They get counted under use success */
1342 if (!circ
->has_opened
) {
1343 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1344 guard
= entry_guard_get_by_id_digest(
1345 circ
->cpath
->extend_info
->identity_digest
);
1349 if (circ
->path_state
== PATH_STATE_BUILD_ATTEMPTED
) {
1350 circ
->path_state
= PATH_STATE_BUILD_SUCCEEDED
;
1351 guard
->circ_successes
++;
1353 log_info(LD_CIRC
, "Got success count %lf/%lf for guard %s=%s",
1354 guard
->circ_successes
, guard
->circ_attempts
,
1355 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
));
1357 if ((rate_msg
= rate_limit_log(&success_notice_limit
,
1360 "Succeeded circuit is in strange path state %s. "
1361 "Circuit is a %s currently %s.%s",
1362 pathbias_state_to_string(circ
->path_state
),
1363 circuit_purpose_to_string(circ
->base_
.purpose
),
1364 circuit_state_to_string(circ
->base_
.state
),
1370 if (guard
->circ_attempts
< guard
->circ_successes
) {
1371 log_notice(LD_BUG
, "Unexpectedly high successes counts (%lf/%lf) "
1373 guard
->circ_successes
, guard
->circ_attempts
,
1374 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
));
1376 /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1377 * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1378 * No need to log that case. */
1379 } else if (circ
->base_
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
1380 if ((rate_msg
= rate_limit_log(&success_notice_limit
,
1383 "Completed circuit has no known guard. "
1384 "Circuit is a %s currently %s.%s",
1385 circuit_purpose_to_string(circ
->base_
.purpose
),
1386 circuit_state_to_string(circ
->base_
.state
),
1392 if (circ
->path_state
< PATH_STATE_BUILD_SUCCEEDED
) {
1393 if ((rate_msg
= rate_limit_log(&success_notice_limit
,
1396 "Opened circuit is in strange path state %s. "
1397 "Circuit is a %s currently %s.%s",
1398 pathbias_state_to_string(circ
->path_state
),
1399 circuit_purpose_to_string(circ
->base_
.purpose
),
1400 circuit_state_to_string(circ
->base_
.state
),
1409 * Check if a circuit was used and/or closed successfully.
1412 pathbias_check_close(origin_circuit_t
*ocirc
, int reason
)
1414 circuit_t
*circ
= ô
->base_
;
1416 if (!pathbias_should_count(ocirc
)) {
1420 if (ocirc
->path_state
== PATH_STATE_BUILD_SUCCEEDED
) {
1421 if (circ
->timestamp_dirty
) {
1422 /* Any circuit where there were attempted streams but no successful
1423 * streams could be bias */
1425 "Circuit %d closed without successful use for reason %d. "
1426 "Circuit purpose %d currently %d,%s. Len %d.",
1427 ocirc
->global_identifier
,
1428 reason
, circ
->purpose
, ocirc
->has_opened
,
1429 circuit_state_to_string(circ
->state
),
1430 ocirc
->build_state
->desired_path_len
);
1431 pathbias_count_unusable(ocirc
);
1433 if (reason
& END_CIRC_REASON_FLAG_REMOTE
) {
1434 /* Unused remote circ close reasons all could be bias */
1436 "Circuit %d remote-closed without successful use for reason %d. "
1437 "Circuit purpose %d currently %d,%s. Len %d.",
1438 ocirc
->global_identifier
,
1439 reason
, circ
->purpose
, ocirc
->has_opened
,
1440 circuit_state_to_string(circ
->state
),
1441 ocirc
->build_state
->desired_path_len
);
1442 pathbias_count_collapse(ocirc
);
1443 } else if ((reason
& ~END_CIRC_REASON_FLAG_REMOTE
)
1444 == END_CIRC_REASON_CHANNEL_CLOSED
&&
1446 circ
->n_chan
->reason_for_closing
1447 != CHANNEL_CLOSE_REQUESTED
) {
1448 /* If we didn't close the channel ourselves, it could be bias */
1449 /* XXX: Only count bias if the network is live?
1450 * What about clock jumps/suspends? */
1452 "Circuit %d's channel closed without successful use for reason "
1453 "%d, channel reason %d. Circuit purpose %d currently %d,%s. Len "
1454 "%d.", ocirc
->global_identifier
,
1455 reason
, circ
->n_chan
->reason_for_closing
,
1456 circ
->purpose
, ocirc
->has_opened
,
1457 circuit_state_to_string(circ
->state
),
1458 ocirc
->build_state
->desired_path_len
);
1459 pathbias_count_collapse(ocirc
);
1461 pathbias_count_successful_close(ocirc
);
1464 } else if (ocirc
->path_state
== PATH_STATE_USE_SUCCEEDED
) {
1465 pathbias_count_successful_close(ocirc
);
1470 * Count a successfully closed circuit.
1473 pathbias_count_successful_close(origin_circuit_t
*circ
)
1475 entry_guard_t
*guard
= NULL
;
1476 if (!pathbias_should_count(circ
)) {
1480 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1481 guard
= entry_guard_get_by_id_digest(
1482 circ
->cpath
->extend_info
->identity_digest
);
1486 /* In the long run: circuit_success ~= successful_circuit_close +
1487 * circ_failure + stream_failure */
1488 guard
->successful_circuits_closed
++;
1489 entry_guards_changed();
1490 } else if (circ
->base_
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
1491 /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1492 * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1493 * No need to log that case. */
1495 "Successfully closed circuit has no known guard. "
1496 "Circuit is a %s currently %s",
1497 circuit_purpose_to_string(circ
->base_
.purpose
),
1498 circuit_state_to_string(circ
->base_
.state
));
1503 * Count a circuit that fails after it is built, but before it can
1504 * carry any traffic.
1506 * This is needed because there are ways to destroy a
1507 * circuit after it has successfully completed. Right now, this is
1508 * used for purely informational/debugging purposes.
1511 pathbias_count_collapse(origin_circuit_t
*circ
)
1513 entry_guard_t
*guard
= NULL
;
1514 if (!pathbias_should_count(circ
)) {
1518 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1519 guard
= entry_guard_get_by_id_digest(
1520 circ
->cpath
->extend_info
->identity_digest
);
1524 guard
->collapsed_circuits
++;
1525 entry_guards_changed();
1526 } else if (circ
->base_
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
1527 /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1528 * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1529 * No need to log that case. */
1531 "Destroyed circuit has no known guard. "
1532 "Circuit is a %s currently %s",
1533 circuit_purpose_to_string(circ
->base_
.purpose
),
1534 circuit_state_to_string(circ
->base_
.state
));
1539 pathbias_count_unusable(origin_circuit_t
*circ
)
1541 entry_guard_t
*guard
= NULL
;
1542 if (!pathbias_should_count(circ
)) {
1546 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1547 guard
= entry_guard_get_by_id_digest(
1548 circ
->cpath
->extend_info
->identity_digest
);
1552 guard
->unusable_circuits
++;
1553 entry_guards_changed();
1554 } else if (circ
->base_
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
1555 /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1556 * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1557 * No need to log that case. */
1559 "Stream-failing circuit has no known guard. "
1560 "Circuit is a %s currently %s",
1561 circuit_purpose_to_string(circ
->base_
.purpose
),
1562 circuit_state_to_string(circ
->base_
.state
));
1567 * Count timeouts for path bias log messages.
1569 * These counts are purely informational.
1572 pathbias_count_timeout(origin_circuit_t
*circ
)
1574 entry_guard_t
*guard
= NULL
;
1576 if (!pathbias_should_count(circ
)) {
1580 /* For hidden service circs, they can actually be used
1581 * successfully and then time out later (because
1582 * the other side declines to use them). */
1583 if (circ
->path_state
== PATH_STATE_USE_SUCCEEDED
) {
1587 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1588 guard
= entry_guard_get_by_id_digest(
1589 circ
->cpath
->extend_info
->identity_digest
);
1594 entry_guards_changed();
1599 * Return the number of circuits counted as successfully closed for
1602 * Also add in the currently open circuits to give them the benefit
1606 pathbias_get_closed_count(entry_guard_t
*guard
)
1608 circuit_t
*circ
= global_circuitlist
;
1609 int open_circuits
= 0;
1611 /* Count currently open circuits. Give them the benefit of the doubt */
1612 for ( ; circ
; circ
= circ
->next
) {
1613 origin_circuit_t
*ocirc
= NULL
;
1614 if (!CIRCUIT_IS_ORIGIN(circ
) || /* didn't originate here */
1615 circ
->marked_for_close
) /* already counted */
1618 ocirc
= TO_ORIGIN_CIRCUIT(circ
);
1620 if (!ocirc
->cpath
|| !ocirc
->cpath
->extend_info
)
1623 if (ocirc
->path_state
>= PATH_STATE_BUILD_SUCCEEDED
&&
1624 fast_memeq(guard
->identity
,
1625 ocirc
->cpath
->extend_info
->identity_digest
,
1631 return guard
->successful_circuits_closed
+ open_circuits
;
1635 * This function checks the consensus parameters to decide
1636 * if it should return guard->circ_successes or
1637 * guard->successful_circuits_closed.
1640 pathbias_get_success_count(entry_guard_t
*guard
)
1642 if (pathbias_use_close_counts(get_options())) {
1643 return pathbias_get_closed_count(guard
);
1645 return guard
->circ_successes
;
1649 /** Increment the number of times we successfully extended a circuit to
1650 * 'guard', first checking if the failure rate is high enough that we should
1651 * eliminate the guard. Return -1 if the guard looks no good; return 0 if the
1652 * guard looks fine. */
1654 entry_guard_inc_circ_attempt_count(entry_guard_t
*guard
)
1656 const or_options_t
*options
= get_options();
1658 entry_guards_changed();
1660 if (guard
->circ_attempts
> pathbias_get_min_circs(options
)) {
1661 /* Note: We rely on the < comparison here to allow us to set a 0
1662 * rate and disable the feature entirely. If refactoring, don't
1664 if (pathbias_get_success_count(guard
)/guard
->circ_attempts
1665 < pathbias_get_extreme_rate(options
)) {
1666 /* Dropping is currently disabled by default. */
1667 if (pathbias_get_dropguards(options
)) {
1668 if (!guard
->path_bias_disabled
) {
1670 "Your Guard %s=%s is failing an extremely large amount of "
1671 "circuits. To avoid potential route manipluation attacks, "
1672 "Tor has disabled use of this guard. "
1673 "Success counts are %ld/%ld. %ld circuits completed, %ld "
1674 "were unusable, %ld collapsed, and %ld timed out. For "
1675 "reference, your timeout cutoff is %ld seconds.",
1676 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
),
1677 tor_lround(pathbias_get_closed_count(guard
)),
1678 tor_lround(guard
->circ_attempts
),
1679 tor_lround(guard
->circ_successes
),
1680 tor_lround(guard
->unusable_circuits
),
1681 tor_lround(guard
->collapsed_circuits
),
1682 tor_lround(guard
->timeouts
),
1683 tor_lround(circ_times
.close_ms
/1000));
1684 guard
->path_bias_disabled
= 1;
1685 guard
->bad_since
= approx_time();
1688 } else if (!guard
->path_bias_extreme
) {
1689 guard
->path_bias_extreme
= 1;
1691 "Your Guard %s=%s is failing an extremely large amount of "
1692 "circuits. This could indicate a route manipulation attack, "
1693 "extreme network overload, or a bug. "
1694 "Success counts are %ld/%ld. %ld circuits completed, %ld "
1695 "were unusable, %ld collapsed, and %ld timed out. For "
1696 "reference, your timeout cutoff is %ld seconds.",
1697 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
),
1698 tor_lround(pathbias_get_closed_count(guard
)),
1699 tor_lround(guard
->circ_attempts
),
1700 tor_lround(guard
->circ_successes
),
1701 tor_lround(guard
->unusable_circuits
),
1702 tor_lround(guard
->collapsed_circuits
),
1703 tor_lround(guard
->timeouts
),
1704 tor_lround(circ_times
.close_ms
/1000));
1706 } else if (pathbias_get_success_count(guard
)/((double)guard
->circ_attempts
)
1707 < pathbias_get_warn_rate(options
)) {
1708 if (!guard
->path_bias_warned
) {
1709 guard
->path_bias_warned
= 1;
1711 "Your Guard %s=%s is failing a very large amount of "
1712 "circuits. Most likely this means the Tor network is "
1713 "overloaded, but it could also mean an attack against "
1714 "you or the potentially the guard itself. "
1715 "Success counts are %ld/%ld. %ld circuits completed, %ld "
1716 "were unusable, %ld collapsed, and %ld timed out. For "
1717 "reference, your timeout cutoff is %ld seconds.",
1718 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
),
1719 tor_lround(pathbias_get_closed_count(guard
)),
1720 tor_lround(guard
->circ_attempts
),
1721 tor_lround(guard
->circ_successes
),
1722 tor_lround(guard
->unusable_circuits
),
1723 tor_lround(guard
->collapsed_circuits
),
1724 tor_lround(guard
->timeouts
),
1725 tor_lround(circ_times
.close_ms
/1000));
1727 } else if (pathbias_get_success_count(guard
)/((double)guard
->circ_attempts
)
1728 < pathbias_get_notice_rate(options
)) {
1729 if (!guard
->path_bias_noticed
) {
1730 guard
->path_bias_noticed
= 1;
1732 "Your Guard %s=%s is failing more circuits than usual. "
1733 "Most likely this means the Tor network is overloaded. "
1734 "Success counts are %ld/%ld. %ld circuits completed, %ld "
1735 "were unusable, %ld collapsed, and %ld timed out. For "
1736 "reference, your timeout cutoff is %ld seconds.",
1737 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
),
1738 tor_lround(pathbias_get_closed_count(guard
)),
1739 tor_lround(guard
->circ_attempts
),
1740 tor_lround(guard
->circ_successes
),
1741 tor_lround(guard
->unusable_circuits
),
1742 tor_lround(guard
->collapsed_circuits
),
1743 tor_lround(guard
->timeouts
),
1744 tor_lround(circ_times
.close_ms
/1000));
1749 /* If we get a ton of circuits, just scale everything down */
1750 if (guard
->circ_attempts
> pathbias_get_scale_threshold(options
)) {
1751 const int scale_factor
= pathbias_get_scale_factor(options
);
1752 const int mult_factor
= pathbias_get_mult_factor(options
);
1754 "Scaling pathbias counts to (%lf/%lf)*(%d/%d) for guard %s=%s",
1755 guard
->circ_successes
, guard
->circ_attempts
,
1756 mult_factor
, scale_factor
, guard
->nickname
,
1757 hex_str(guard
->identity
, DIGEST_LEN
));
1759 guard
->circ_attempts
*= mult_factor
;
1760 guard
->circ_successes
*= mult_factor
;
1761 guard
->timeouts
*= mult_factor
;
1762 guard
->successful_circuits_closed
*= mult_factor
;
1763 guard
->collapsed_circuits
*= mult_factor
;
1764 guard
->unusable_circuits
*= mult_factor
;
1766 guard
->circ_attempts
/= scale_factor
;
1767 guard
->circ_successes
/= scale_factor
;
1768 guard
->timeouts
/= scale_factor
;
1769 guard
->successful_circuits_closed
/= scale_factor
;
1770 guard
->collapsed_circuits
/= scale_factor
;
1771 guard
->unusable_circuits
/= scale_factor
;
1773 guard
->circ_attempts
++;
1774 log_info(LD_CIRC
, "Got success count %lf/%lf for guard %s=%s",
1775 guard
->circ_successes
, guard
->circ_attempts
, guard
->nickname
,
1776 hex_str(guard
->identity
, DIGEST_LEN
));
1780 /** A created or extended cell came back to us on the circuit, and it included
1781 * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body
1782 * contains (the second DH key, plus KH). If <b>reply_type</b> is
1783 * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
1785 * Calculate the appropriate keys and digests, make sure KH is
1786 * correct, and initialize this hop of the cpath.
1788 * Return - reason if we want to mark circ for close, else return 0.
1791 circuit_finish_handshake(origin_circuit_t
*circ
, uint8_t reply_type
,
1792 const uint8_t *reply
)
1794 char keys
[CPATH_KEY_MATERIAL_LEN
];
1798 if ((rv
= pathbias_count_circ_attempt(circ
)) < 0)
1801 if (circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
) {
1804 hop
= onion_next_hop_in_cpath(circ
->cpath
);
1805 if (!hop
) { /* got an extended when we're all done? */
1806 log_warn(LD_PROTOCOL
,"got extended when circ already built? Closing.");
1807 return - END_CIRC_REASON_TORPROTOCOL
;
1810 tor_assert(hop
->state
== CPATH_STATE_AWAITING_KEYS
);
1812 if (reply_type
== CELL_CREATED
&& hop
->dh_handshake_state
) {
1813 if (onion_skin_client_handshake(hop
->dh_handshake_state
, (char*)reply
,keys
,
1814 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
1815 log_warn(LD_CIRC
,"onion_skin_client_handshake failed.");
1816 return -END_CIRC_REASON_TORPROTOCOL
;
1818 /* Remember hash of g^xy */
1819 memcpy(hop
->handshake_digest
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
1820 } else if (reply_type
== CELL_CREATED_FAST
&& !hop
->dh_handshake_state
) {
1821 if (fast_client_handshake(hop
->fast_handshake_state
, reply
,
1823 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
1824 log_warn(LD_CIRC
,"fast_client_handshake failed.");
1825 return -END_CIRC_REASON_TORPROTOCOL
;
1827 memcpy(hop
->handshake_digest
, reply
+DIGEST_LEN
, DIGEST_LEN
);
1829 log_warn(LD_PROTOCOL
,"CREATED cell type did not match CREATE cell type.");
1830 return -END_CIRC_REASON_TORPROTOCOL
;
1833 crypto_dh_free(hop
->dh_handshake_state
); /* don't need it anymore */
1834 hop
->dh_handshake_state
= NULL
;
1836 memset(hop
->fast_handshake_state
, 0, sizeof(hop
->fast_handshake_state
));
1838 if (circuit_init_cpath_crypto(hop
, keys
, 0)<0) {
1839 return -END_CIRC_REASON_TORPROTOCOL
;
1842 hop
->state
= CPATH_STATE_OPEN
;
1843 log_info(LD_CIRC
,"Finished building %scircuit hop:",
1844 (reply_type
== CELL_CREATED_FAST
) ? "fast " : "");
1845 circuit_log_path(LOG_INFO
,LD_CIRC
,circ
);
1846 control_event_circuit_status(circ
, CIRC_EVENT_EXTENDED
, 0);
1851 /** We received a relay truncated cell on circ.
1853 * Since we don't ask for truncates currently, getting a truncated
1854 * means that a connection broke or an extend failed. For now,
1855 * just give up: for circ to close, and return 0.
1858 circuit_truncated(origin_circuit_t
*circ
, crypt_path_t
*layer
, int reason
)
1860 // crypt_path_t *victim;
1861 // connection_t *stream;
1866 /* XXX Since we don't ask for truncates currently, getting a truncated
1867 * means that a connection broke or an extend failed. For now,
1870 circuit_mark_for_close(TO_CIRCUIT(circ
),
1871 END_CIRC_REASON_FLAG_REMOTE
|reason
);
1875 while (layer
->next
!= circ
->cpath
) {
1876 /* we need to clear out layer->next */
1877 victim
= layer
->next
;
1878 log_debug(LD_CIRC
, "Killing a layer of the cpath.");
1880 for (stream
= circ
->p_streams
; stream
; stream
=stream
->next_stream
) {
1881 if (stream
->cpath_layer
== victim
) {
1882 log_info(LD_APP
, "Marking stream %d for close because of truncate.",
1884 /* no need to send 'end' relay cells,
1885 * because the other side's already dead
1887 connection_mark_unattached_ap(stream
, END_STREAM_REASON_DESTROY
);
1891 layer
->next
= victim
->next
;
1892 circuit_free_cpath_node(victim
);
1895 log_info(LD_CIRC
, "finished");
1900 /** Given a response payload and keys, initialize, then send a created
1904 onionskin_answer(or_circuit_t
*circ
, uint8_t cell_type
, const char *payload
,
1908 crypt_path_t
*tmp_cpath
;
1910 tmp_cpath
= tor_malloc_zero(sizeof(crypt_path_t
));
1911 tmp_cpath
->magic
= CRYPT_PATH_MAGIC
;
1913 memset(&cell
, 0, sizeof(cell_t
));
1914 cell
.command
= cell_type
;
1915 cell
.circ_id
= circ
->p_circ_id
;
1917 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
1919 memcpy(cell
.payload
, payload
,
1920 cell_type
== CELL_CREATED
? ONIONSKIN_REPLY_LEN
: DIGEST_LEN
*2);
1922 log_debug(LD_CIRC
,"init digest forward 0x%.8x, backward 0x%.8x.",
1923 (unsigned int)get_uint32(keys
),
1924 (unsigned int)get_uint32(keys
+20));
1925 if (circuit_init_cpath_crypto(tmp_cpath
, keys
, 0)<0) {
1926 log_warn(LD_BUG
,"Circuit initialization failed");
1927 tor_free(tmp_cpath
);
1930 circ
->n_digest
= tmp_cpath
->f_digest
;
1931 circ
->n_crypto
= tmp_cpath
->f_crypto
;
1932 circ
->p_digest
= tmp_cpath
->b_digest
;
1933 circ
->p_crypto
= tmp_cpath
->b_crypto
;
1934 tmp_cpath
->magic
= 0;
1935 tor_free(tmp_cpath
);
1937 if (cell_type
== CELL_CREATED
)
1938 memcpy(circ
->handshake_digest
, cell
.payload
+DH_KEY_LEN
, DIGEST_LEN
);
1940 memcpy(circ
->handshake_digest
, cell
.payload
+DIGEST_LEN
, DIGEST_LEN
);
1942 circ
->is_first_hop
= (cell_type
== CELL_CREATED_FAST
);
1944 append_cell_to_circuit_queue(TO_CIRCUIT(circ
),
1945 circ
->p_chan
, &cell
, CELL_DIRECTION_IN
, 0);
1946 log_debug(LD_CIRC
,"Finished sending '%s' cell.",
1947 circ
->is_first_hop
? "created_fast" : "created");
1949 if (!channel_is_local(circ
->p_chan
) &&
1950 !channel_is_outgoing(circ
->p_chan
)) {
1951 /* record that we could process create cells from a non-local conn
1952 * that we didn't initiate; presumably this means that create cells
1953 * can reach us too. */
1954 router_orport_found_reachable();
1960 /** Choose a length for a circuit of purpose <b>purpose</b>.
1961 * Default length is 3 + the number of endpoints that would give something
1962 * away. If the routerlist <b>routers</b> doesn't have enough routers
1963 * to handle the desired path length, return as large a path length as
1964 * is feasible, except if it's less than 2, in which case return -1.
1967 new_route_len(uint8_t purpose
, extend_info_t
*exit
,
1970 int num_acceptable_routers
;
1975 routelen
= DEFAULT_ROUTE_LEN
;
1977 purpose
!= CIRCUIT_PURPOSE_TESTING
&&
1978 purpose
!= CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
)
1981 num_acceptable_routers
= count_acceptable_nodes(nodes
);
1983 log_debug(LD_CIRC
,"Chosen route length %d (%d/%d routers suitable).",
1984 routelen
, num_acceptable_routers
, smartlist_len(nodes
));
1986 if (num_acceptable_routers
< 2) {
1988 "Not enough acceptable routers (%d). Discarding this circuit.",
1989 num_acceptable_routers
);
1993 if (num_acceptable_routers
< routelen
) {
1994 log_info(LD_CIRC
,"Not enough routers: cutting routelen from %d to %d.",
1995 routelen
, num_acceptable_routers
);
1996 routelen
= num_acceptable_routers
;
2002 /** Return a newly allocated list of uint16_t * for each predicted port not
2003 * handled by a current circuit. */
2004 static smartlist_t
*
2005 circuit_get_unhandled_ports(time_t now
)
2007 smartlist_t
*dest
= rep_hist_get_predicted_ports(now
);
2008 circuit_remove_handled_ports(dest
);
2012 /** Return 1 if we already have circuits present or on the way for
2013 * all anticipated ports. Return 0 if we should make more.
2015 * If we're returning 0, set need_uptime and need_capacity to
2016 * indicate any requirements that the unhandled ports have.
2019 circuit_all_predicted_ports_handled(time_t now
, int *need_uptime
,
2024 smartlist_t
*sl
= circuit_get_unhandled_ports(now
);
2025 smartlist_t
*LongLivedServices
= get_options()->LongLivedPorts
;
2026 tor_assert(need_uptime
);
2027 tor_assert(need_capacity
);
2028 // Always predict need_capacity
2030 enough
= (smartlist_len(sl
) == 0);
2031 for (i
= 0; i
< smartlist_len(sl
); ++i
) {
2032 port
= smartlist_get(sl
, i
);
2033 if (smartlist_string_num_isin(LongLivedServices
, *port
))
2041 /** Return 1 if <b>node</b> can handle one or more of the ports in
2042 * <b>needed_ports</b>, else return 0.
2045 node_handles_some_port(const node_t
*node
, smartlist_t
*needed_ports
)
2050 for (i
= 0; i
< smartlist_len(needed_ports
); ++i
) {
2051 addr_policy_result_t r
;
2052 /* alignment issues aren't a worry for this dereference, since
2053 needed_ports is explicitly a smartlist of uint16_t's */
2054 port
= *(uint16_t *)smartlist_get(needed_ports
, i
);
2057 r
= compare_tor_addr_to_node_policy(NULL
, port
, node
);
2060 if (r
!= ADDR_POLICY_REJECTED
&& r
!= ADDR_POLICY_PROBABLY_REJECTED
)
2066 /** Return true iff <b>conn</b> needs another general circuit to be
2069 ap_stream_wants_exit_attention(connection_t
*conn
)
2071 entry_connection_t
*entry
;
2072 if (conn
->type
!= CONN_TYPE_AP
)
2074 entry
= TO_ENTRY_CONN(conn
);
2076 if (conn
->state
== AP_CONN_STATE_CIRCUIT_WAIT
&&
2077 !conn
->marked_for_close
&&
2078 !(entry
->want_onehop
) && /* ignore one-hop streams */
2079 !(entry
->use_begindir
) && /* ignore targeted dir fetches */
2080 !(entry
->chosen_exit_name
) && /* ignore defined streams */
2081 !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn
)) &&
2082 !circuit_stream_is_being_handled(TO_ENTRY_CONN(conn
), 0,
2083 MIN_CIRCUITS_HANDLING_STREAM
))
2088 /** Return a pointer to a suitable router to be the exit node for the
2089 * general-purpose circuit we're about to build.
2091 * Look through the connection array, and choose a router that maximizes
2092 * the number of pending streams that can exit from this router.
2094 * Return NULL if we can't find any suitable routers.
2096 static const node_t
*
2097 choose_good_exit_server_general(int need_uptime
, int need_capacity
)
2100 int n_pending_connections
= 0;
2101 smartlist_t
*connections
;
2102 int best_support
= -1;
2103 int n_best_support
=0;
2104 const or_options_t
*options
= get_options();
2105 const smartlist_t
*the_nodes
;
2106 const node_t
*node
=NULL
;
2108 connections
= get_connection_array();
2110 /* Count how many connections are waiting for a circuit to be built.
2111 * We use this for log messages now, but in the future we may depend on it.
2113 SMARTLIST_FOREACH(connections
, connection_t
*, conn
,
2115 if (ap_stream_wants_exit_attention(conn
))
2116 ++n_pending_connections
;
2118 // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
2119 // n_pending_connections);
2120 /* Now we count, for each of the routers in the directory, how many
2121 * of the pending connections could possibly exit from that
2122 * router (n_supported[i]). (We can't be sure about cases where we
2123 * don't know the IP address of the pending connection.)
2125 * -1 means "Don't use this router at all."
2127 the_nodes
= nodelist_get_list();
2128 n_supported
= tor_malloc(sizeof(int)*smartlist_len(the_nodes
));
2129 SMARTLIST_FOREACH_BEGIN(the_nodes
, const node_t
*, node
) {
2130 const int i
= node_sl_idx
;
2131 if (router_digest_is_me(node
->identity
)) {
2132 n_supported
[i
] = -1;
2133 // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
2134 /* XXX there's probably a reverse predecessor attack here, but
2135 * it's slow. should we take this out? -RD
2139 if (!node_has_descriptor(node
)) {
2140 n_supported
[i
] = -1;
2143 if (!node
->is_running
|| node
->is_bad_exit
) {
2144 n_supported
[i
] = -1;
2145 continue; /* skip routers that are known to be down or bad exits */
2147 if (node_get_purpose(node
) != ROUTER_PURPOSE_GENERAL
) {
2148 /* never pick a non-general node as a random exit. */
2149 n_supported
[i
] = -1;
2152 if (routerset_contains_node(options
->ExcludeExitNodesUnion_
, node
)) {
2153 n_supported
[i
] = -1;
2154 continue; /* user asked us not to use it, no matter what */
2156 if (options
->ExitNodes
&&
2157 !routerset_contains_node(options
->ExitNodes
, node
)) {
2158 n_supported
[i
] = -1;
2159 continue; /* not one of our chosen exit nodes */
2162 if (node_is_unreliable(node
, need_uptime
, need_capacity
, 0)) {
2163 n_supported
[i
] = -1;
2164 continue; /* skip routers that are not suitable. Don't worry if
2165 * this makes us reject all the possible routers: if so,
2166 * we'll retry later in this function with need_update and
2167 * need_capacity set to 0. */
2169 if (!(node
->is_valid
|| options
->AllowInvalid_
& ALLOW_INVALID_EXIT
)) {
2170 /* if it's invalid and we don't want it */
2171 n_supported
[i
] = -1;
2172 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
2173 // router->nickname, i);
2174 continue; /* skip invalid routers */
2176 if (options
->ExcludeSingleHopRelays
&&
2177 node_allows_single_hop_exits(node
)) {
2178 n_supported
[i
] = -1;
2181 if (node_exit_policy_rejects_all(node
)) {
2182 n_supported
[i
] = -1;
2183 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
2184 // router->nickname, i);
2185 continue; /* skip routers that reject all */
2188 /* iterate over connections */
2189 SMARTLIST_FOREACH_BEGIN(connections
, connection_t
*, conn
) {
2190 if (!ap_stream_wants_exit_attention(conn
))
2191 continue; /* Skip everything but APs in CIRCUIT_WAIT */
2192 if (connection_ap_can_use_exit(TO_ENTRY_CONN(conn
), node
)) {
2194 // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
2195 // router->nickname, i, n_supported[i]);
2197 // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
2198 // router->nickname, i);
2200 } SMARTLIST_FOREACH_END(conn
);
2201 if (n_pending_connections
> 0 && n_supported
[i
] == 0) {
2202 /* Leave best_support at -1 if that's where it is, so we can
2203 * distinguish it later. */
2206 if (n_supported
[i
] > best_support
) {
2207 /* If this router is better than previous ones, remember its index
2208 * and goodness, and start counting how many routers are this good. */
2209 best_support
= n_supported
[i
]; n_best_support
=1;
2210 // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
2211 // router->nickname);
2212 } else if (n_supported
[i
] == best_support
) {
2213 /* If this router is _as good_ as the best one, just increment the
2214 * count of equally good routers.*/
2217 } SMARTLIST_FOREACH_END(node
);
2219 "Found %d servers that might support %d/%d pending connections.",
2220 n_best_support
, best_support
>= 0 ? best_support
: 0,
2221 n_pending_connections
);
2223 /* If any routers definitely support any pending connections, choose one
2225 if (best_support
> 0) {
2226 smartlist_t
*supporting
= smartlist_new();
2228 SMARTLIST_FOREACH(the_nodes
, const node_t
*, node
, {
2229 if (n_supported
[node_sl_idx
] == best_support
)
2230 smartlist_add(supporting
, (void*)node
);
2233 node
= node_sl_choose_by_bandwidth(supporting
, WEIGHT_FOR_EXIT
);
2234 smartlist_free(supporting
);
2236 /* Either there are no pending connections, or no routers even seem to
2237 * possibly support any of them. Choose a router at random that satisfies
2238 * at least one predicted exit port. */
2241 smartlist_t
*needed_ports
, *supporting
;
2243 if (best_support
== -1) {
2244 if (need_uptime
|| need_capacity
) {
2246 "We couldn't find any live%s%s routers; falling back "
2247 "to list of all routers.",
2248 need_capacity
?", fast":"",
2249 need_uptime
?", stable":"");
2250 tor_free(n_supported
);
2251 return choose_good_exit_server_general(0, 0);
2253 log_notice(LD_CIRC
, "All routers are down or won't exit%s -- "
2254 "choosing a doomed exit at random.",
2255 options
->ExcludeExitNodesUnion_
? " or are Excluded" : "");
2257 supporting
= smartlist_new();
2258 needed_ports
= circuit_get_unhandled_ports(time(NULL
));
2259 for (attempt
= 0; attempt
< 2; attempt
++) {
2260 /* try once to pick only from routers that satisfy a needed port,
2261 * then if there are none, pick from any that support exiting. */
2262 SMARTLIST_FOREACH_BEGIN(the_nodes
, const node_t
*, node
) {
2263 if (n_supported
[node_sl_idx
] != -1 &&
2264 (attempt
|| node_handles_some_port(node
, needed_ports
))) {
2265 // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
2266 // try, router->nickname);
2267 smartlist_add(supporting
, (void*)node
);
2269 } SMARTLIST_FOREACH_END(node
);
2271 node
= node_sl_choose_by_bandwidth(supporting
, WEIGHT_FOR_EXIT
);
2274 smartlist_clear(supporting
);
2275 /* If we reach this point, we can't actually support any unhandled
2276 * predicted ports, so clear all the remaining ones. */
2277 if (smartlist_len(needed_ports
))
2278 rep_hist_remove_predicted_ports(needed_ports
);
2280 SMARTLIST_FOREACH(needed_ports
, uint16_t *, cp
, tor_free(cp
));
2281 smartlist_free(needed_ports
);
2282 smartlist_free(supporting
);
2285 tor_free(n_supported
);
2287 log_info(LD_CIRC
, "Chose exit server '%s'", node_describe(node
));
2290 if (options
->ExitNodes
) {
2292 "No specified %sexit routers seem to be running: "
2293 "can't choose an exit.",
2294 options
->ExcludeExitNodesUnion_
? "non-excluded " : "");
2299 /** Return a pointer to a suitable router to be the exit node for the
2300 * circuit of purpose <b>purpose</b> that we're about to build (or NULL
2301 * if no router is suitable).
2303 * For general-purpose circuits, pass it off to
2304 * choose_good_exit_server_general()
2306 * For client-side rendezvous circuits, choose a random node, weighted
2307 * toward the preferences in 'options'.
2309 static const node_t
*
2310 choose_good_exit_server(uint8_t purpose
,
2311 int need_uptime
, int need_capacity
, int is_internal
)
2313 const or_options_t
*options
= get_options();
2314 router_crn_flags_t flags
= CRN_NEED_DESC
;
2316 flags
|= CRN_NEED_UPTIME
;
2318 flags
|= CRN_NEED_CAPACITY
;
2321 case CIRCUIT_PURPOSE_C_GENERAL
:
2322 if (options
->AllowInvalid_
& ALLOW_INVALID_MIDDLE
)
2323 flags
|= CRN_ALLOW_INVALID
;
2324 if (is_internal
) /* pick it like a middle hop */
2325 return router_choose_random_node(NULL
, options
->ExcludeNodes
, flags
);
2327 return choose_good_exit_server_general(need_uptime
,need_capacity
);
2328 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
2329 if (options
->AllowInvalid_
& ALLOW_INVALID_RENDEZVOUS
)
2330 flags
|= CRN_ALLOW_INVALID
;
2331 return router_choose_random_node(NULL
, options
->ExcludeNodes
, flags
);
2333 log_warn(LD_BUG
,"Unhandled purpose %d", purpose
);
2334 tor_fragile_assert();
2338 /** Log a warning if the user specified an exit for the circuit that
2339 * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
2341 warn_if_last_router_excluded(origin_circuit_t
*circ
, const extend_info_t
*exit
)
2343 const or_options_t
*options
= get_options();
2344 routerset_t
*rs
= options
->ExcludeNodes
;
2345 const char *description
;
2346 uint8_t purpose
= circ
->base_
.purpose
;
2348 if (circ
->build_state
->onehop_tunnel
)
2354 case CIRCUIT_PURPOSE_OR
:
2355 case CIRCUIT_PURPOSE_INTRO_POINT
:
2356 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
2357 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
2358 log_warn(LD_BUG
, "Called on non-origin circuit (purpose %d, %s)",
2360 circuit_purpose_to_string(purpose
));
2362 case CIRCUIT_PURPOSE_C_GENERAL
:
2363 if (circ
->build_state
->is_internal
)
2365 description
= "requested exit node";
2366 rs
= options
->ExcludeExitNodesUnion_
;
2368 case CIRCUIT_PURPOSE_C_INTRODUCING
:
2369 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
2370 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
2371 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
2372 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
2373 case CIRCUIT_PURPOSE_S_REND_JOINED
:
2374 case CIRCUIT_PURPOSE_TESTING
:
2376 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
2377 case CIRCUIT_PURPOSE_C_REND_READY
:
2378 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
2379 case CIRCUIT_PURPOSE_C_REND_JOINED
:
2380 description
= "chosen rendezvous point";
2382 case CIRCUIT_PURPOSE_CONTROLLER
:
2383 rs
= options
->ExcludeExitNodesUnion_
;
2384 description
= "controller-selected circuit target";
2388 if (routerset_contains_extendinfo(rs
, exit
)) {
2389 /* We should never get here if StrictNodes is set to 1. */
2390 if (options
->StrictNodes
) {
2391 log_warn(LD_BUG
, "Using %s '%s' which is listed in ExcludeNodes%s, "
2392 "even though StrictNodes is set. Please report. "
2393 "(Circuit purpose: %s)",
2394 description
, extend_info_describe(exit
),
2395 rs
==options
->ExcludeNodes
?"":" or ExcludeExitNodes",
2396 circuit_purpose_to_string(purpose
));
2398 log_warn(LD_CIRC
, "Using %s '%s' which is listed in "
2399 "ExcludeNodes%s, because no better options were available. To "
2400 "prevent this (and possibly break your Tor functionality), "
2401 "set the StrictNodes configuration option. "
2402 "(Circuit purpose: %s)",
2403 description
, extend_info_describe(exit
),
2404 rs
==options
->ExcludeNodes
?"":" or ExcludeExitNodes",
2405 circuit_purpose_to_string(purpose
));
2407 circuit_log_path(LOG_WARN
, LD_CIRC
, circ
);
2413 /** Decide a suitable length for circ's cpath, and pick an exit
2414 * router (or use <b>exit</b> if provided). Store these in the
2415 * cpath. Return 0 if ok, -1 if circuit should be closed. */
2417 onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
2419 cpath_build_state_t
*state
= circ
->build_state
;
2421 if (state
->onehop_tunnel
) {
2422 log_debug(LD_CIRC
, "Launching a one-hop circuit for dir tunnel.");
2423 state
->desired_path_len
= 1;
2425 int r
= new_route_len(circ
->base_
.purpose
, exit
, nodelist_get_list());
2426 if (r
< 1) /* must be at least 1 */
2428 state
->desired_path_len
= r
;
2431 if (exit
) { /* the circuit-builder pre-requested one */
2432 warn_if_last_router_excluded(circ
, exit
);
2433 log_info(LD_CIRC
,"Using requested exit node '%s'",
2434 extend_info_describe(exit
));
2435 exit
= extend_info_dup(exit
);
2436 } else { /* we have to decide one */
2437 const node_t
*node
=
2438 choose_good_exit_server(circ
->base_
.purpose
, state
->need_uptime
,
2439 state
->need_capacity
, state
->is_internal
);
2441 log_warn(LD_CIRC
,"failed to choose an exit server");
2444 exit
= extend_info_from_node(node
, 0);
2447 state
->chosen_exit
= exit
;
2451 /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
2452 * hop to the cpath reflecting this. Don't send the next extend cell --
2453 * the caller will do this if it wants to.
2456 circuit_append_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
2458 cpath_build_state_t
*state
;
2462 state
= circ
->build_state
;
2464 extend_info_free(state
->chosen_exit
);
2465 state
->chosen_exit
= extend_info_dup(exit
);
2467 ++circ
->build_state
->desired_path_len
;
2468 onion_append_hop(&circ
->cpath
, exit
);
2472 /** Take an open <b>circ</b>, and add a new hop at the end, based on
2473 * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
2474 * send the next extend cell to begin connecting to that hop.
2477 circuit_extend_to_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
2480 warn_if_last_router_excluded(circ
, exit
);
2481 circuit_append_new_exit(circ
, exit
);
2482 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
2483 if ((err_reason
= circuit_send_next_onion_skin(circ
))<0) {
2484 log_warn(LD_CIRC
, "Couldn't extend circuit to new point %s.",
2485 extend_info_describe(exit
));
2486 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
2490 /* Set timestamp_dirty, so we can check it for path use bias */
2491 if (!circ
->base_
.timestamp_dirty
)
2492 circ
->base_
.timestamp_dirty
= time(NULL
);
2497 /** Return the number of routers in <b>routers</b> that are currently up
2498 * and available for building circuits through.
2501 count_acceptable_nodes(smartlist_t
*nodes
)
2505 SMARTLIST_FOREACH_BEGIN(nodes
, const node_t
*, node
) {
2506 // log_debug(LD_CIRC,
2507 // "Contemplating whether router %d (%s) is a new option.",
2509 if (! node
->is_running
)
2510 // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
2512 if (! node
->is_valid
)
2513 // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
2515 if (! node_has_descriptor(node
))
2517 /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
2518 * allows this node in some places, then we're getting an inaccurate
2519 * count. For now, be conservative and don't count it. But later we
2520 * should try to be smarter. */
2522 } SMARTLIST_FOREACH_END(node
);
2524 // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
2529 /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
2530 * This function is used to extend cpath by another hop.
2533 onion_append_to_cpath(crypt_path_t
**head_ptr
, crypt_path_t
*new_hop
)
2536 new_hop
->next
= (*head_ptr
);
2537 new_hop
->prev
= (*head_ptr
)->prev
;
2538 (*head_ptr
)->prev
->next
= new_hop
;
2539 (*head_ptr
)->prev
= new_hop
;
2541 *head_ptr
= new_hop
;
2542 new_hop
->prev
= new_hop
->next
= new_hop
;
2546 /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
2547 * and <b>state</b> and the cpath <b>head</b> (currently populated only
2548 * to length <b>cur_len</b> to decide a suitable middle hop for a
2549 * circuit. In particular, make sure we don't pick the exit node or its
2550 * family, and make sure we don't duplicate any previous nodes or their
2552 static const node_t
*
2553 choose_good_middle_server(uint8_t purpose
,
2554 cpath_build_state_t
*state
,
2559 const node_t
*r
, *choice
;
2560 crypt_path_t
*cpath
;
2561 smartlist_t
*excluded
;
2562 const or_options_t
*options
= get_options();
2563 router_crn_flags_t flags
= CRN_NEED_DESC
;
2564 tor_assert(CIRCUIT_PURPOSE_MIN_
<= purpose
&&
2565 purpose
<= CIRCUIT_PURPOSE_MAX_
);
2567 log_debug(LD_CIRC
, "Contemplating intermediate hop: random choice.");
2568 excluded
= smartlist_new();
2569 if ((r
= build_state_get_exit_node(state
))) {
2570 nodelist_add_node_and_family(excluded
, r
);
2572 for (i
= 0, cpath
= head
; i
< cur_len
; ++i
, cpath
=cpath
->next
) {
2573 if ((r
= node_get_by_id(cpath
->extend_info
->identity_digest
))) {
2574 nodelist_add_node_and_family(excluded
, r
);
2578 if (state
->need_uptime
)
2579 flags
|= CRN_NEED_UPTIME
;
2580 if (state
->need_capacity
)
2581 flags
|= CRN_NEED_CAPACITY
;
2582 if (options
->AllowInvalid_
& ALLOW_INVALID_MIDDLE
)
2583 flags
|= CRN_ALLOW_INVALID
;
2584 choice
= router_choose_random_node(excluded
, options
->ExcludeNodes
, flags
);
2585 smartlist_free(excluded
);
2589 /** Pick a good entry server for the circuit to be built according to
2590 * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
2591 * router (if we're an OR), and respect firewall settings; if we're
2592 * configured to use entry guards, return one.
2594 * If <b>state</b> is NULL, we're choosing a router to serve as an entry
2595 * guard, not for any particular circuit.
2597 /* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
2599 choose_good_entry_server(uint8_t purpose
, cpath_build_state_t
*state
)
2601 const node_t
*choice
;
2602 smartlist_t
*excluded
;
2603 const or_options_t
*options
= get_options();
2604 router_crn_flags_t flags
= CRN_NEED_GUARD
|CRN_NEED_DESC
;
2607 if (state
&& options
->UseEntryGuards
&&
2608 (purpose
!= CIRCUIT_PURPOSE_TESTING
|| options
->BridgeRelay
)) {
2609 /* This request is for an entry server to use for a regular circuit,
2610 * and we use entry guard nodes. Just return one of the guard nodes. */
2611 return choose_random_entry(state
);
2614 excluded
= smartlist_new();
2616 if (state
&& (node
= build_state_get_exit_node(state
))) {
2617 /* Exclude the exit node from the state, if we have one. Also exclude its
2619 nodelist_add_node_and_family(excluded
, node
);
2621 if (firewall_is_fascist_or()) {
2622 /* Exclude all ORs that we can't reach through our firewall */
2623 smartlist_t
*nodes
= nodelist_get_list();
2624 SMARTLIST_FOREACH(nodes
, const node_t
*, node
, {
2625 if (!fascist_firewall_allows_node(node
))
2626 smartlist_add(excluded
, (void*)node
);
2629 /* and exclude current entry guards and their families, if applicable */
2630 if (options
->UseEntryGuards
) {
2631 SMARTLIST_FOREACH(get_entry_guards(), const entry_guard_t
*, entry
,
2633 if ((node
= node_get_by_id(entry
->identity
))) {
2634 nodelist_add_node_and_family(excluded
, node
);
2640 if (state
->need_uptime
)
2641 flags
|= CRN_NEED_UPTIME
;
2642 if (state
->need_capacity
)
2643 flags
|= CRN_NEED_CAPACITY
;
2645 if (options
->AllowInvalid_
& ALLOW_INVALID_ENTRY
)
2646 flags
|= CRN_ALLOW_INVALID
;
2648 choice
= router_choose_random_node(excluded
, options
->ExcludeNodes
, flags
);
2649 smartlist_free(excluded
);
2653 /** Return the first non-open hop in cpath, or return NULL if all
2655 static crypt_path_t
*
2656 onion_next_hop_in_cpath(crypt_path_t
*cpath
)
2658 crypt_path_t
*hop
= cpath
;
2660 if (hop
->state
!= CPATH_STATE_OPEN
)
2663 } while (hop
!= cpath
);
2667 /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
2668 * based on <b>state</b>. Append the hop info to head_ptr.
2671 onion_extend_cpath(origin_circuit_t
*circ
)
2673 uint8_t purpose
= circ
->base_
.purpose
;
2674 cpath_build_state_t
*state
= circ
->build_state
;
2675 int cur_len
= circuit_get_cpath_len(circ
);
2676 extend_info_t
*info
= NULL
;
2678 if (cur_len
>= state
->desired_path_len
) {
2679 log_debug(LD_CIRC
, "Path is complete: %d steps long",
2680 state
->desired_path_len
);
2684 log_debug(LD_CIRC
, "Path is %d long; we want %d", cur_len
,
2685 state
->desired_path_len
);
2687 if (cur_len
== state
->desired_path_len
- 1) { /* Picking last node */
2688 info
= extend_info_dup(state
->chosen_exit
);
2689 } else if (cur_len
== 0) { /* picking first node */
2690 const node_t
*r
= choose_good_entry_server(purpose
, state
);
2692 /* If we're a client, use the preferred address rather than the
2693 primary address, for potentially connecting to an IPv6 OR
2695 info
= extend_info_from_node(r
, server_mode(get_options()) == 0);
2700 choose_good_middle_server(purpose
, state
, circ
->cpath
, cur_len
);
2702 info
= extend_info_from_node(r
, 0);
2708 log_warn(LD_CIRC
,"Failed to find node for hop %d of our path. Discarding "
2709 "this circuit.", cur_len
);
2713 log_debug(LD_CIRC
,"Chose router %s for hop %d (exit is %s)",
2714 extend_info_describe(info
),
2715 cur_len
+1, build_state_get_exit_nickname(state
));
2717 onion_append_hop(&circ
->cpath
, info
);
2718 extend_info_free(info
);
2722 /** Create a new hop, annotate it with information about its
2723 * corresponding router <b>choice</b>, and append it to the
2724 * end of the cpath <b>head_ptr</b>. */
2726 onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
)
2728 crypt_path_t
*hop
= tor_malloc_zero(sizeof(crypt_path_t
));
2730 /* link hop into the cpath, at the end. */
2731 onion_append_to_cpath(head_ptr
, hop
);
2733 hop
->magic
= CRYPT_PATH_MAGIC
;
2734 hop
->state
= CPATH_STATE_CLOSED
;
2736 hop
->extend_info
= extend_info_dup(choice
);
2738 hop
->package_window
= circuit_initial_package_window();
2739 hop
->deliver_window
= CIRCWINDOW_START
;
2744 /** Allocate a new extend_info object based on the various arguments. */
2746 extend_info_new(const char *nickname
, const char *digest
,
2747 crypto_pk_t
*onion_key
,
2748 const tor_addr_t
*addr
, uint16_t port
)
2750 extend_info_t
*info
= tor_malloc_zero(sizeof(extend_info_t
));
2751 memcpy(info
->identity_digest
, digest
, DIGEST_LEN
);
2753 strlcpy(info
->nickname
, nickname
, sizeof(info
->nickname
));
2755 info
->onion_key
= crypto_pk_dup_key(onion_key
);
2756 tor_addr_copy(&info
->addr
, addr
);
2761 /** Allocate and return a new extend_info that can be used to build a
2762 * circuit to or through the node <b>node</b>. Use the primary address
2763 * of the node (i.e. its IPv4 address) unless
2764 * <b>for_direct_connect</b> is true, in which case the preferred
2765 * address is used instead. May return NULL if there is not enough
2766 * info about <b>node</b> to extend to it--for example, if there is no
2767 * routerinfo_t or microdesc_t.
2770 extend_info_from_node(const node_t
*node
, int for_direct_connect
)
2774 if (node
->ri
== NULL
&& (node
->rs
== NULL
|| node
->md
== NULL
))
2777 if (for_direct_connect
)
2778 node_get_pref_orport(node
, &ap
);
2780 node_get_prim_orport(node
, &ap
);
2782 log_debug(LD_CIRC
, "using %s for %s",
2783 fmt_addrport(&ap
.addr
, ap
.port
),
2784 node
->ri
? node
->ri
->nickname
: node
->rs
->nickname
);
2787 return extend_info_new(node
->ri
->nickname
,
2789 node
->ri
->onion_pkey
,
2792 else if (node
->rs
&& node
->md
)
2793 return extend_info_new(node
->rs
->nickname
,
2795 node
->md
->onion_pkey
,
2802 /** Release storage held by an extend_info_t struct. */
2804 extend_info_free(extend_info_t
*info
)
2808 crypto_pk_free(info
->onion_key
);
2812 /** Allocate and return a new extend_info_t with the same contents as
2815 extend_info_dup(extend_info_t
*info
)
2817 extend_info_t
*newinfo
;
2819 newinfo
= tor_malloc(sizeof(extend_info_t
));
2820 memcpy(newinfo
, info
, sizeof(extend_info_t
));
2821 if (info
->onion_key
)
2822 newinfo
->onion_key
= crypto_pk_dup_key(info
->onion_key
);
2824 newinfo
->onion_key
= NULL
;
2828 /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
2829 * If there is no chosen exit, or if we don't know the routerinfo_t for
2830 * the chosen exit, return NULL.
2833 build_state_get_exit_node(cpath_build_state_t
*state
)
2835 if (!state
|| !state
->chosen_exit
)
2837 return node_get_by_id(state
->chosen_exit
->identity_digest
);
2840 /** Return the nickname for the chosen exit router in <b>state</b>. If
2841 * there is no chosen exit, or if we don't know the routerinfo_t for the
2842 * chosen exit, return NULL.
2845 build_state_get_exit_nickname(cpath_build_state_t
*state
)
2847 if (!state
|| !state
->chosen_exit
)
2849 return state
->chosen_exit
->nickname
;