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, 100)/100.0;
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. Note that
1082 * we must be careful of the values we use here, as the
1083 * code only scales in the event of no integer truncation.
1086 pathbias_get_scale_factor(const or_options_t
*options
)
1088 #define DFLT_PATH_BIAS_SCALE_FACTOR 2
1089 if (options
->PathBiasScaleFactor
>= 1)
1090 return options
->PathBiasScaleFactor
;
1092 return networkstatus_get_param(NULL
, "pb_scalefactor",
1093 DFLT_PATH_BIAS_SCALE_FACTOR
, 1, INT32_MAX
);
1097 * The mult factor is the numerator for our scaling
1098 * of circuit counts for our path bias window. It
1099 * allows us to scale by fractions.
1102 pathbias_get_mult_factor(const or_options_t
*options
)
1104 #define DFLT_PATH_BIAS_MULT_FACTOR 1
1105 if (options
->PathBiasMultFactor
>= 1)
1106 return options
->PathBiasMultFactor
;
1108 return networkstatus_get_param(NULL
, "pb_multfactor",
1109 DFLT_PATH_BIAS_MULT_FACTOR
, 1,
1110 pathbias_get_scale_factor(options
));
1114 * If this parameter is set to a true value (default), we use the
1115 * successful_circuits_closed. Otherwise, we use the success_count.
1118 pathbias_use_close_counts(const or_options_t
*options
)
1120 #define DFLT_PATH_BIAS_USE_CLOSE_COUNTS 1
1121 if (options
->PathBiasUseCloseCounts
>= 0)
1122 return options
->PathBiasUseCloseCounts
;
1124 return networkstatus_get_param(NULL
, "pb_useclosecounts",
1125 DFLT_PATH_BIAS_USE_CLOSE_COUNTS
, 0, 1);
1129 * Convert a Guard's path state to string.
1132 pathbias_state_to_string(path_state_t state
)
1135 case PATH_STATE_NEW_CIRC
:
1137 case PATH_STATE_BUILD_ATTEMPTED
:
1138 return "build attempted";
1139 case PATH_STATE_BUILD_SUCCEEDED
:
1140 return "build succeeded";
1141 case PATH_STATE_USE_SUCCEEDED
:
1142 return "use succeeded";
1149 * This function decides if a circuit has progressed far enough to count
1150 * as a circuit "attempt". As long as end-to-end tagging is possible,
1151 * we assume the adversary will use it over hop-to-hop failure. Therefore,
1152 * we only need to account bias for the last hop. This should make us
1153 * much more resilient to ambient circuit failure, and also make that
1154 * failure easier to measure (we only need to measure Exit failure rates).
1157 pathbias_is_new_circ_attempt(origin_circuit_t
*circ
)
1159 #define N2N_TAGGING_IS_POSSIBLE
1160 #ifdef N2N_TAGGING_IS_POSSIBLE
1161 /* cpath is a circular list. We want circs with more than one hop,
1162 * and the second hop must be waiting for keys still (it's just
1163 * about to get them). */
1164 return circ
->cpath
->next
!= circ
->cpath
&&
1165 circ
->cpath
->next
->state
== CPATH_STATE_AWAITING_KEYS
;
1167 /* If tagging attacks are no longer possible, we probably want to
1168 * count bias from the first hop. However, one could argue that
1169 * timing-based tagging is still more useful than per-hop failure.
1170 * In which case, we'd never want to use this.
1172 return circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
;
1177 * Decide if the path bias code should count a circuit.
1179 * @returns 1 if we should count it, 0 otherwise.
1182 pathbias_should_count(origin_circuit_t
*circ
)
1184 #define PATHBIAS_COUNT_INTERVAL (600)
1185 static ratelim_t count_limit
=
1186 RATELIM_INIT(PATHBIAS_COUNT_INTERVAL
);
1187 char *rate_msg
= NULL
;
1189 /* We can't do path bias accounting without entry guards.
1190 * Testing and controller circuits also have no guards.
1192 * We also don't count server-side rends, because their
1193 * endpoint could be chosen maliciously.
1194 * Similarly, we can't count client-side intro attempts,
1195 * because clients can be manipulated into connecting to
1196 * malicious intro points. */
1197 if (get_options()->UseEntryGuards
== 0 ||
1198 circ
->base_
.purpose
== CIRCUIT_PURPOSE_TESTING
||
1199 circ
->base_
.purpose
== CIRCUIT_PURPOSE_CONTROLLER
||
1200 circ
->base_
.purpose
== CIRCUIT_PURPOSE_S_CONNECT_REND
||
1201 circ
->base_
.purpose
== CIRCUIT_PURPOSE_S_REND_JOINED
||
1202 (circ
->base_
.purpose
>= CIRCUIT_PURPOSE_C_INTRODUCING
&&
1203 circ
->base_
.purpose
<= CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
)) {
1207 /* Completely ignore one hop circuits */
1208 if (circ
->build_state
->onehop_tunnel
||
1209 circ
->build_state
->desired_path_len
== 1) {
1210 /* Check for inconsistency */
1211 if (circ
->build_state
->desired_path_len
!= 1 ||
1212 !circ
->build_state
->onehop_tunnel
) {
1213 if ((rate_msg
= rate_limit_log(&count_limit
, approx_time()))) {
1215 "One-hop circuit has length %d. Path state is %s. "
1216 "Circuit is a %s currently %s.%s",
1217 circ
->build_state
->desired_path_len
,
1218 pathbias_state_to_string(circ
->path_state
),
1219 circuit_purpose_to_string(circ
->base_
.purpose
),
1220 circuit_state_to_string(circ
->base_
.state
),
1224 tor_fragile_assert();
1233 * Check our circuit state to see if this is a successful circuit attempt.
1234 * If so, record it in the current guard's path bias circ_attempt count.
1236 * Also check for several potential error cases for bug #6475.
1239 pathbias_count_circ_attempt(origin_circuit_t
*circ
)
1241 #define CIRC_ATTEMPT_NOTICE_INTERVAL (600)
1242 static ratelim_t circ_attempt_notice_limit
=
1243 RATELIM_INIT(CIRC_ATTEMPT_NOTICE_INTERVAL
);
1244 char *rate_msg
= NULL
;
1246 if (!pathbias_should_count(circ
)) {
1250 if (pathbias_is_new_circ_attempt(circ
)) {
1251 /* Help track down the real cause of bug #6475: */
1252 if (circ
->has_opened
&& circ
->path_state
!= PATH_STATE_BUILD_ATTEMPTED
) {
1253 if ((rate_msg
= rate_limit_log(&circ_attempt_notice_limit
,
1256 "Opened circuit is in strange path state %s. "
1257 "Circuit is a %s currently %s.%s",
1258 pathbias_state_to_string(circ
->path_state
),
1259 circuit_purpose_to_string(circ
->base_
.purpose
),
1260 circuit_state_to_string(circ
->base_
.state
),
1266 /* Don't re-count cannibalized circs.. */
1267 if (!circ
->has_opened
) {
1268 entry_guard_t
*guard
= NULL
;
1270 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1271 guard
= entry_guard_get_by_id_digest(
1272 circ
->cpath
->extend_info
->identity_digest
);
1273 } else if (circ
->base_
.n_chan
) {
1275 entry_guard_get_by_id_digest(circ
->base_
.n_chan
->identity_digest
);
1279 if (circ
->path_state
== PATH_STATE_NEW_CIRC
) {
1280 circ
->path_state
= PATH_STATE_BUILD_ATTEMPTED
;
1282 if (entry_guard_inc_circ_attempt_count(guard
) < 0) {
1283 /* Bogus guard; we already warned. */
1284 return -END_CIRC_REASON_TORPROTOCOL
;
1287 if ((rate_msg
= rate_limit_log(&circ_attempt_notice_limit
,
1290 "Unopened circuit has strange path state %s. "
1291 "Circuit is a %s currently %s.%s",
1292 pathbias_state_to_string(circ
->path_state
),
1293 circuit_purpose_to_string(circ
->base_
.purpose
),
1294 circuit_state_to_string(circ
->base_
.state
),
1300 if ((rate_msg
= rate_limit_log(&circ_attempt_notice_limit
,
1303 "Unopened circuit has no known guard. "
1304 "Circuit is a %s currently %s.%s",
1305 circuit_purpose_to_string(circ
->base_
.purpose
),
1306 circuit_state_to_string(circ
->base_
.state
),
1313 /* Help track down the real cause of bug #6475: */
1314 if (circ
->path_state
== PATH_STATE_NEW_CIRC
) {
1315 if ((rate_msg
= rate_limit_log(&circ_attempt_notice_limit
,
1318 "A %s circuit is in cpath state %d (opened: %d). "
1319 "Circuit is a %s currently %s.%s",
1320 pathbias_state_to_string(circ
->path_state
),
1321 circ
->cpath
->state
, circ
->has_opened
,
1322 circuit_purpose_to_string(circ
->base_
.purpose
),
1323 circuit_state_to_string(circ
->base_
.state
),
1334 * Check our circuit state to see if this is a successful circuit
1335 * completion. If so, record it in the current guard's path bias
1338 * Also check for several potential error cases for bug #6475.
1341 pathbias_count_build_success(origin_circuit_t
*circ
)
1343 #define SUCCESS_NOTICE_INTERVAL (600)
1344 static ratelim_t success_notice_limit
=
1345 RATELIM_INIT(SUCCESS_NOTICE_INTERVAL
);
1346 char *rate_msg
= NULL
;
1347 entry_guard_t
*guard
= NULL
;
1349 if (!pathbias_should_count(circ
)) {
1353 /* Don't count cannibalized/reused circs for path bias
1354 * build success.. They get counted under use success */
1355 if (!circ
->has_opened
) {
1356 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1357 guard
= entry_guard_get_by_id_digest(
1358 circ
->cpath
->extend_info
->identity_digest
);
1362 if (circ
->path_state
== PATH_STATE_BUILD_ATTEMPTED
) {
1363 circ
->path_state
= PATH_STATE_BUILD_SUCCEEDED
;
1364 guard
->circ_successes
++;
1366 log_info(LD_CIRC
, "Got success count %lf/%lf for guard %s=%s",
1367 guard
->circ_successes
, guard
->circ_attempts
,
1368 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
));
1370 if ((rate_msg
= rate_limit_log(&success_notice_limit
,
1373 "Succeeded circuit is in strange path state %s. "
1374 "Circuit is a %s currently %s.%s",
1375 pathbias_state_to_string(circ
->path_state
),
1376 circuit_purpose_to_string(circ
->base_
.purpose
),
1377 circuit_state_to_string(circ
->base_
.state
),
1383 if (guard
->circ_attempts
< guard
->circ_successes
) {
1384 log_notice(LD_BUG
, "Unexpectedly high successes counts (%lf/%lf) "
1386 guard
->circ_successes
, guard
->circ_attempts
,
1387 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
));
1389 /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1390 * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1391 * No need to log that case. */
1392 } else if (circ
->base_
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
1393 if ((rate_msg
= rate_limit_log(&success_notice_limit
,
1396 "Completed circuit has no known guard. "
1397 "Circuit is a %s currently %s.%s",
1398 circuit_purpose_to_string(circ
->base_
.purpose
),
1399 circuit_state_to_string(circ
->base_
.state
),
1405 if (circ
->path_state
< PATH_STATE_BUILD_SUCCEEDED
) {
1406 if ((rate_msg
= rate_limit_log(&success_notice_limit
,
1409 "Opened circuit is in strange path state %s. "
1410 "Circuit is a %s currently %s.%s",
1411 pathbias_state_to_string(circ
->path_state
),
1412 circuit_purpose_to_string(circ
->base_
.purpose
),
1413 circuit_state_to_string(circ
->base_
.state
),
1422 * Check if a circuit was used and/or closed successfully.
1425 pathbias_check_close(origin_circuit_t
*ocirc
, int reason
)
1427 circuit_t
*circ
= ô
->base_
;
1429 if (!pathbias_should_count(ocirc
)) {
1433 if (ocirc
->path_state
== PATH_STATE_BUILD_SUCCEEDED
) {
1434 if (circ
->timestamp_dirty
) {
1435 /* Any circuit where there were attempted streams but no successful
1436 * streams could be bias */
1437 // XXX: May open up attacks if the adversary can force connections
1438 // on unresponsive hosts to use new circs. Vidalia displayes a "Retrying"
1439 // state.. Can we use that? Does optimistic data change this?
1442 "Circuit %d closed without successful use for reason %d. "
1443 "Circuit purpose %d currently %s.",
1444 ocirc
->global_identifier
,
1445 reason
, circ
->purpose
, circuit_state_to_string(circ
->state
));
1446 pathbias_count_unusable(ocirc
);
1448 if (reason
& END_CIRC_REASON_FLAG_REMOTE
) {
1449 /* Unused remote circ close reasons all could be bias */
1451 "Circuit %d remote-closed without successful use for reason %d. "
1452 "Circuit purpose %d currently %s.",
1453 ocirc
->global_identifier
,
1454 reason
, circ
->purpose
, circuit_state_to_string(circ
->state
));
1455 pathbias_count_collapse(ocirc
);
1456 } else if ((reason
& ~END_CIRC_REASON_FLAG_REMOTE
)
1457 == END_CIRC_REASON_CHANNEL_CLOSED
&&
1459 circ
->n_chan
->reason_for_closing
1460 != CHANNEL_CLOSE_REQUESTED
) {
1461 /* If we didn't close the channel ourselves, it could be bias */
1462 /* FIXME: Only count bias if the network is live?
1463 * What about clock jumps/suspends? */
1465 "Circuit %d's channel closed without successful use for reason "
1466 "%d, channel reason %d. Circuit purpose %d currently %s.",
1467 ocirc
->global_identifier
,
1468 reason
, circ
->n_chan
->reason_for_closing
,
1469 circ
->purpose
, circuit_state_to_string(circ
->state
));
1470 pathbias_count_collapse(ocirc
);
1472 pathbias_count_successful_close(ocirc
);
1475 } else if (ocirc
->path_state
== PATH_STATE_USE_SUCCEEDED
) {
1476 pathbias_count_successful_close(ocirc
);
1481 * Count a successfully closed circuit.
1484 pathbias_count_successful_close(origin_circuit_t
*circ
)
1486 entry_guard_t
*guard
= NULL
;
1487 if (!pathbias_should_count(circ
)) {
1491 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1492 guard
= entry_guard_get_by_id_digest(
1493 circ
->cpath
->extend_info
->identity_digest
);
1497 /* In the long run: circuit_success ~= successful_circuit_close +
1498 * circ_failure + stream_failure */
1499 guard
->successful_circuits_closed
++;
1500 entry_guards_changed();
1501 } else if (circ
->base_
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
1502 /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1503 * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1504 * No need to log that case. */
1506 "Successfully closed circuit has no known guard. "
1507 "Circuit is a %s currently %s",
1508 circuit_purpose_to_string(circ
->base_
.purpose
),
1509 circuit_state_to_string(circ
->base_
.state
));
1514 * Count a circuit that fails after it is built, but before it can
1515 * carry any traffic.
1517 * This is needed because there are ways to destroy a
1518 * circuit after it has successfully completed. Right now, this is
1519 * used for purely informational/debugging purposes.
1522 pathbias_count_collapse(origin_circuit_t
*circ
)
1524 entry_guard_t
*guard
= NULL
;
1525 if (!pathbias_should_count(circ
)) {
1529 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1530 guard
= entry_guard_get_by_id_digest(
1531 circ
->cpath
->extend_info
->identity_digest
);
1535 guard
->collapsed_circuits
++;
1536 entry_guards_changed();
1537 } else if (circ
->base_
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
1538 /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1539 * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1540 * No need to log that case. */
1542 "Destroyed circuit has no known guard. "
1543 "Circuit is a %s currently %s",
1544 circuit_purpose_to_string(circ
->base_
.purpose
),
1545 circuit_state_to_string(circ
->base_
.state
));
1550 pathbias_count_unusable(origin_circuit_t
*circ
)
1552 entry_guard_t
*guard
= NULL
;
1553 if (!pathbias_should_count(circ
)) {
1557 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1558 guard
= entry_guard_get_by_id_digest(
1559 circ
->cpath
->extend_info
->identity_digest
);
1563 guard
->unusable_circuits
++;
1564 entry_guards_changed();
1565 } else if (circ
->base_
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
1566 /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
1567 * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
1568 * No need to log that case. */
1570 "Stream-failing circuit has no known guard. "
1571 "Circuit is a %s currently %s",
1572 circuit_purpose_to_string(circ
->base_
.purpose
),
1573 circuit_state_to_string(circ
->base_
.state
));
1578 * Count timeouts for path bias log messages.
1580 * These counts are purely informational.
1583 pathbias_count_timeout(origin_circuit_t
*circ
)
1585 entry_guard_t
*guard
= NULL
;
1587 if (!pathbias_should_count(circ
)) {
1591 /* For hidden service circs, they can actually be used
1592 * successfully and then time out later (because
1593 * the other side declines to use them). */
1594 if (circ
->path_state
== PATH_STATE_USE_SUCCEEDED
) {
1598 if (circ
->cpath
&& circ
->cpath
->extend_info
) {
1599 guard
= entry_guard_get_by_id_digest(
1600 circ
->cpath
->extend_info
->identity_digest
);
1605 entry_guards_changed();
1611 pathbias_get_closed_count(entry_guard_t
*guard
)
1613 circuit_t
*circ
= global_circuitlist
;
1614 int open_circuits
= 0;
1616 /* Count currently open circuits. Give them the benefit of the doubt */
1617 for ( ; circ
; circ
= circ
->next
) {
1618 origin_circuit_t
*ocirc
= NULL
;
1619 if (!CIRCUIT_IS_ORIGIN(circ
) || /* didn't originate here */
1620 circ
->marked_for_close
) /* already counted */
1623 ocirc
= TO_ORIGIN_CIRCUIT(circ
);
1625 if (!ocirc
->cpath
|| !ocirc
->cpath
->extend_info
)
1628 if (ocirc
->path_state
>= PATH_STATE_BUILD_SUCCEEDED
&&
1629 (memcmp(guard
->identity
,
1630 ocirc
->cpath
->extend_info
->identity_digest
,
1637 return guard
->successful_circuits_closed
+ open_circuits
;
1641 * This function checks the consensus parameters to decide
1642 * if it should return guard->circ_successes or
1643 * guard->successful_circuits_closed.
1646 pathbias_get_success_count(entry_guard_t
*guard
)
1648 if (pathbias_use_close_counts(get_options())) {
1649 return pathbias_get_closed_count(guard
);
1651 return guard
->circ_successes
;
1655 /** Increment the number of times we successfully extended a circuit to
1656 * 'guard', first checking if the failure rate is high enough that we should
1657 * eliminate the guard. Return -1 if the guard looks no good; return 0 if the
1658 * guard looks fine. */
1660 entry_guard_inc_circ_attempt_count(entry_guard_t
*guard
)
1662 const or_options_t
*options
= get_options();
1664 entry_guards_changed();
1666 if (guard
->circ_attempts
> pathbias_get_min_circs(options
)) {
1667 /* Note: We rely on the < comparison here to allow us to set a 0
1668 * rate and disable the feature entirely. If refactoring, don't
1670 if (pathbias_get_success_count(guard
)/guard
->circ_attempts
1671 < pathbias_get_extreme_rate(options
)) {
1672 /* Dropping is currently disabled by default. */
1673 if (pathbias_get_dropguards(options
)) {
1674 if (!guard
->path_bias_disabled
) {
1676 "Your Guard %s=%s is failing an extremely large amount of "
1677 "circuits. To avoid potential route manipluation attacks, "
1678 "Tor has disabled use of this guard. "
1679 "Success counts are %d/%d. %d circuits completed, %d "
1680 "were unusable, %d collapsed, and %d timed out. For "
1681 "reference, your timeout cutoff is %ld seconds.",
1682 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
),
1683 (int)pathbias_get_closed_count(guard
),
1684 (int)guard
->circ_attempts
, (int)guard
->circ_successes
,
1685 (int)guard
->unusable_circuits
,
1686 (int)guard
->collapsed_circuits
, (int)guard
->timeouts
,
1687 (long)circ_times
.close_ms
/1000);
1688 guard
->path_bias_disabled
= 1;
1689 guard
->bad_since
= approx_time();
1692 } else if (!guard
->path_bias_extreme
) {
1693 guard
->path_bias_extreme
= 1;
1695 "Your Guard %s=%s is failing an extremely large amount of "
1696 "circuits. This could indicate a route manipulation attack, "
1697 "extreme network overload, or a bug. "
1698 "Success counts are %d/%d. %d circuits completed, %d "
1699 "were unusable, %d collapsed, and %d timed out. For "
1700 "reference, your timeout cutoff is %ld seconds.",
1701 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
),
1702 (int)pathbias_get_closed_count(guard
),
1703 (int)guard
->circ_attempts
, (int)guard
->circ_successes
,
1704 (int)guard
->unusable_circuits
,
1705 (int)guard
->collapsed_circuits
, (int)guard
->timeouts
,
1706 (long)circ_times
.close_ms
/1000);
1708 } else if (pathbias_get_success_count(guard
)/((double)guard
->circ_attempts
)
1709 < pathbias_get_warn_rate(options
)) {
1710 if (!guard
->path_bias_warned
) {
1711 guard
->path_bias_warned
= 1;
1713 "Your Guard %s=%s is failing a very large amount of "
1714 "circuits. Most likely this means the Tor network is "
1715 "overloaded, but it could also mean an attack against "
1716 "you or the potentially the guard itself. "
1717 "Success counts are %d/%d. %d circuits completed, %d "
1718 "were unusable, %d collapsed, and %d timed out. For "
1719 "reference, your timeout cutoff is %ld seconds.",
1720 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
),
1721 (int)pathbias_get_closed_count(guard
),
1722 (int)guard
->circ_attempts
, (int)guard
->circ_successes
,
1723 (int)guard
->unusable_circuits
,
1724 (int)guard
->collapsed_circuits
, (int)guard
->timeouts
,
1725 (long)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 %d/%d. %d circuits completed, %d "
1735 "were unusable, %d collapsed, and %d timed out. For "
1736 "reference, your timeout cutoff is %ld seconds.",
1737 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
),
1738 (int)pathbias_get_closed_count(guard
),
1739 (int)guard
->circ_attempts
, (int)guard
->circ_successes
,
1740 (int)guard
->unusable_circuits
,
1741 (int)guard
->collapsed_circuits
, (int)guard
->timeouts
,
1742 (long)circ_times
.close_ms
/1000);
1747 /* If we get a ton of circuits, just scale everything down */
1748 if (guard
->circ_attempts
> pathbias_get_scale_threshold(options
)) {
1749 const int scale_factor
= pathbias_get_scale_factor(options
);
1750 const int mult_factor
= pathbias_get_mult_factor(options
);
1752 "Scaling pathbias counts to (%lf/%lf)*(%d/%d) for guard %s=%s",
1753 guard
->circ_successes
, guard
->circ_attempts
,
1754 mult_factor
, scale_factor
, guard
->nickname
,
1755 hex_str(guard
->identity
, DIGEST_LEN
));
1757 guard
->circ_attempts
*= mult_factor
;
1758 guard
->circ_successes
*= mult_factor
;
1759 guard
->timeouts
*= mult_factor
;
1760 guard
->successful_circuits_closed
*= mult_factor
;
1761 guard
->collapsed_circuits
*= mult_factor
;
1762 guard
->unusable_circuits
*= mult_factor
;
1764 guard
->circ_attempts
/= scale_factor
;
1765 guard
->circ_successes
/= scale_factor
;
1766 guard
->timeouts
/= scale_factor
;
1767 guard
->successful_circuits_closed
/= scale_factor
;
1768 guard
->collapsed_circuits
/= scale_factor
;
1769 guard
->unusable_circuits
/= scale_factor
;
1771 guard
->circ_attempts
++;
1772 log_info(LD_CIRC
, "Got success count %lf/%lf for guard %s=%s",
1773 guard
->circ_successes
, guard
->circ_attempts
, guard
->nickname
,
1774 hex_str(guard
->identity
, DIGEST_LEN
));
1778 /** A created or extended cell came back to us on the circuit, and it included
1779 * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body
1780 * contains (the second DH key, plus KH). If <b>reply_type</b> is
1781 * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
1783 * Calculate the appropriate keys and digests, make sure KH is
1784 * correct, and initialize this hop of the cpath.
1786 * Return - reason if we want to mark circ for close, else return 0.
1789 circuit_finish_handshake(origin_circuit_t
*circ
, uint8_t reply_type
,
1790 const uint8_t *reply
)
1792 char keys
[CPATH_KEY_MATERIAL_LEN
];
1796 if ((rv
= pathbias_count_circ_attempt(circ
)) < 0)
1799 if (circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
) {
1802 hop
= onion_next_hop_in_cpath(circ
->cpath
);
1803 if (!hop
) { /* got an extended when we're all done? */
1804 log_warn(LD_PROTOCOL
,"got extended when circ already built? Closing.");
1805 return - END_CIRC_REASON_TORPROTOCOL
;
1808 tor_assert(hop
->state
== CPATH_STATE_AWAITING_KEYS
);
1810 if (reply_type
== CELL_CREATED
&& hop
->dh_handshake_state
) {
1811 if (onion_skin_client_handshake(hop
->dh_handshake_state
, (char*)reply
,keys
,
1812 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
1813 log_warn(LD_CIRC
,"onion_skin_client_handshake failed.");
1814 return -END_CIRC_REASON_TORPROTOCOL
;
1816 /* Remember hash of g^xy */
1817 memcpy(hop
->handshake_digest
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
1818 } else if (reply_type
== CELL_CREATED_FAST
&& !hop
->dh_handshake_state
) {
1819 if (fast_client_handshake(hop
->fast_handshake_state
, reply
,
1821 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
1822 log_warn(LD_CIRC
,"fast_client_handshake failed.");
1823 return -END_CIRC_REASON_TORPROTOCOL
;
1825 memcpy(hop
->handshake_digest
, reply
+DIGEST_LEN
, DIGEST_LEN
);
1827 log_warn(LD_PROTOCOL
,"CREATED cell type did not match CREATE cell type.");
1828 return -END_CIRC_REASON_TORPROTOCOL
;
1831 crypto_dh_free(hop
->dh_handshake_state
); /* don't need it anymore */
1832 hop
->dh_handshake_state
= NULL
;
1834 memset(hop
->fast_handshake_state
, 0, sizeof(hop
->fast_handshake_state
));
1836 if (circuit_init_cpath_crypto(hop
, keys
, 0)<0) {
1837 return -END_CIRC_REASON_TORPROTOCOL
;
1840 hop
->state
= CPATH_STATE_OPEN
;
1841 log_info(LD_CIRC
,"Finished building %scircuit hop:",
1842 (reply_type
== CELL_CREATED_FAST
) ? "fast " : "");
1843 circuit_log_path(LOG_INFO
,LD_CIRC
,circ
);
1844 control_event_circuit_status(circ
, CIRC_EVENT_EXTENDED
, 0);
1849 /** We received a relay truncated cell on circ.
1851 * Since we don't ask for truncates currently, getting a truncated
1852 * means that a connection broke or an extend failed. For now,
1853 * just give up: for circ to close, and return 0.
1856 circuit_truncated(origin_circuit_t
*circ
, crypt_path_t
*layer
, int reason
)
1858 // crypt_path_t *victim;
1859 // connection_t *stream;
1864 /* XXX Since we don't ask for truncates currently, getting a truncated
1865 * means that a connection broke or an extend failed. For now,
1868 circuit_mark_for_close(TO_CIRCUIT(circ
),
1869 END_CIRC_REASON_FLAG_REMOTE
|reason
);
1873 while (layer
->next
!= circ
->cpath
) {
1874 /* we need to clear out layer->next */
1875 victim
= layer
->next
;
1876 log_debug(LD_CIRC
, "Killing a layer of the cpath.");
1878 for (stream
= circ
->p_streams
; stream
; stream
=stream
->next_stream
) {
1879 if (stream
->cpath_layer
== victim
) {
1880 log_info(LD_APP
, "Marking stream %d for close because of truncate.",
1882 /* no need to send 'end' relay cells,
1883 * because the other side's already dead
1885 connection_mark_unattached_ap(stream
, END_STREAM_REASON_DESTROY
);
1889 layer
->next
= victim
->next
;
1890 circuit_free_cpath_node(victim
);
1893 log_info(LD_CIRC
, "finished");
1898 /** Given a response payload and keys, initialize, then send a created
1902 onionskin_answer(or_circuit_t
*circ
, uint8_t cell_type
, const char *payload
,
1906 crypt_path_t
*tmp_cpath
;
1908 tmp_cpath
= tor_malloc_zero(sizeof(crypt_path_t
));
1909 tmp_cpath
->magic
= CRYPT_PATH_MAGIC
;
1911 memset(&cell
, 0, sizeof(cell_t
));
1912 cell
.command
= cell_type
;
1913 cell
.circ_id
= circ
->p_circ_id
;
1915 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
1917 memcpy(cell
.payload
, payload
,
1918 cell_type
== CELL_CREATED
? ONIONSKIN_REPLY_LEN
: DIGEST_LEN
*2);
1920 log_debug(LD_CIRC
,"init digest forward 0x%.8x, backward 0x%.8x.",
1921 (unsigned int)get_uint32(keys
),
1922 (unsigned int)get_uint32(keys
+20));
1923 if (circuit_init_cpath_crypto(tmp_cpath
, keys
, 0)<0) {
1924 log_warn(LD_BUG
,"Circuit initialization failed");
1925 tor_free(tmp_cpath
);
1928 circ
->n_digest
= tmp_cpath
->f_digest
;
1929 circ
->n_crypto
= tmp_cpath
->f_crypto
;
1930 circ
->p_digest
= tmp_cpath
->b_digest
;
1931 circ
->p_crypto
= tmp_cpath
->b_crypto
;
1932 tmp_cpath
->magic
= 0;
1933 tor_free(tmp_cpath
);
1935 if (cell_type
== CELL_CREATED
)
1936 memcpy(circ
->handshake_digest
, cell
.payload
+DH_KEY_LEN
, DIGEST_LEN
);
1938 memcpy(circ
->handshake_digest
, cell
.payload
+DIGEST_LEN
, DIGEST_LEN
);
1940 circ
->is_first_hop
= (cell_type
== CELL_CREATED_FAST
);
1942 append_cell_to_circuit_queue(TO_CIRCUIT(circ
),
1943 circ
->p_chan
, &cell
, CELL_DIRECTION_IN
, 0);
1944 log_debug(LD_CIRC
,"Finished sending '%s' cell.",
1945 circ
->is_first_hop
? "created_fast" : "created");
1947 if (!channel_is_local(circ
->p_chan
) &&
1948 !channel_is_outgoing(circ
->p_chan
)) {
1949 /* record that we could process create cells from a non-local conn
1950 * that we didn't initiate; presumably this means that create cells
1951 * can reach us too. */
1952 router_orport_found_reachable();
1958 /** Choose a length for a circuit of purpose <b>purpose</b>.
1959 * Default length is 3 + the number of endpoints that would give something
1960 * away. If the routerlist <b>routers</b> doesn't have enough routers
1961 * to handle the desired path length, return as large a path length as
1962 * is feasible, except if it's less than 2, in which case return -1.
1965 new_route_len(uint8_t purpose
, extend_info_t
*exit
,
1968 int num_acceptable_routers
;
1973 routelen
= DEFAULT_ROUTE_LEN
;
1975 purpose
!= CIRCUIT_PURPOSE_TESTING
&&
1976 purpose
!= CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
)
1979 num_acceptable_routers
= count_acceptable_nodes(nodes
);
1981 log_debug(LD_CIRC
,"Chosen route length %d (%d/%d routers suitable).",
1982 routelen
, num_acceptable_routers
, smartlist_len(nodes
));
1984 if (num_acceptable_routers
< 2) {
1986 "Not enough acceptable routers (%d). Discarding this circuit.",
1987 num_acceptable_routers
);
1991 if (num_acceptable_routers
< routelen
) {
1992 log_info(LD_CIRC
,"Not enough routers: cutting routelen from %d to %d.",
1993 routelen
, num_acceptable_routers
);
1994 routelen
= num_acceptable_routers
;
2000 /** Return a newly allocated list of uint16_t * for each predicted port not
2001 * handled by a current circuit. */
2002 static smartlist_t
*
2003 circuit_get_unhandled_ports(time_t now
)
2005 smartlist_t
*dest
= rep_hist_get_predicted_ports(now
);
2006 circuit_remove_handled_ports(dest
);
2010 /** Return 1 if we already have circuits present or on the way for
2011 * all anticipated ports. Return 0 if we should make more.
2013 * If we're returning 0, set need_uptime and need_capacity to
2014 * indicate any requirements that the unhandled ports have.
2017 circuit_all_predicted_ports_handled(time_t now
, int *need_uptime
,
2022 smartlist_t
*sl
= circuit_get_unhandled_ports(now
);
2023 smartlist_t
*LongLivedServices
= get_options()->LongLivedPorts
;
2024 tor_assert(need_uptime
);
2025 tor_assert(need_capacity
);
2026 // Always predict need_capacity
2028 enough
= (smartlist_len(sl
) == 0);
2029 for (i
= 0; i
< smartlist_len(sl
); ++i
) {
2030 port
= smartlist_get(sl
, i
);
2031 if (smartlist_string_num_isin(LongLivedServices
, *port
))
2039 /** Return 1 if <b>node</b> can handle one or more of the ports in
2040 * <b>needed_ports</b>, else return 0.
2043 node_handles_some_port(const node_t
*node
, smartlist_t
*needed_ports
)
2048 for (i
= 0; i
< smartlist_len(needed_ports
); ++i
) {
2049 addr_policy_result_t r
;
2050 /* alignment issues aren't a worry for this dereference, since
2051 needed_ports is explicitly a smartlist of uint16_t's */
2052 port
= *(uint16_t *)smartlist_get(needed_ports
, i
);
2055 r
= compare_tor_addr_to_node_policy(NULL
, port
, node
);
2058 if (r
!= ADDR_POLICY_REJECTED
&& r
!= ADDR_POLICY_PROBABLY_REJECTED
)
2064 /** Return true iff <b>conn</b> needs another general circuit to be
2067 ap_stream_wants_exit_attention(connection_t
*conn
)
2069 entry_connection_t
*entry
;
2070 if (conn
->type
!= CONN_TYPE_AP
)
2072 entry
= TO_ENTRY_CONN(conn
);
2074 if (conn
->state
== AP_CONN_STATE_CIRCUIT_WAIT
&&
2075 !conn
->marked_for_close
&&
2076 !(entry
->want_onehop
) && /* ignore one-hop streams */
2077 !(entry
->use_begindir
) && /* ignore targeted dir fetches */
2078 !(entry
->chosen_exit_name
) && /* ignore defined streams */
2079 !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn
)) &&
2080 !circuit_stream_is_being_handled(TO_ENTRY_CONN(conn
), 0,
2081 MIN_CIRCUITS_HANDLING_STREAM
))
2086 /** Return a pointer to a suitable router to be the exit node for the
2087 * general-purpose circuit we're about to build.
2089 * Look through the connection array, and choose a router that maximizes
2090 * the number of pending streams that can exit from this router.
2092 * Return NULL if we can't find any suitable routers.
2094 static const node_t
*
2095 choose_good_exit_server_general(int need_uptime
, int need_capacity
)
2098 int n_pending_connections
= 0;
2099 smartlist_t
*connections
;
2100 int best_support
= -1;
2101 int n_best_support
=0;
2102 const or_options_t
*options
= get_options();
2103 const smartlist_t
*the_nodes
;
2104 const node_t
*node
=NULL
;
2106 connections
= get_connection_array();
2108 /* Count how many connections are waiting for a circuit to be built.
2109 * We use this for log messages now, but in the future we may depend on it.
2111 SMARTLIST_FOREACH(connections
, connection_t
*, conn
,
2113 if (ap_stream_wants_exit_attention(conn
))
2114 ++n_pending_connections
;
2116 // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
2117 // n_pending_connections);
2118 /* Now we count, for each of the routers in the directory, how many
2119 * of the pending connections could possibly exit from that
2120 * router (n_supported[i]). (We can't be sure about cases where we
2121 * don't know the IP address of the pending connection.)
2123 * -1 means "Don't use this router at all."
2125 the_nodes
= nodelist_get_list();
2126 n_supported
= tor_malloc(sizeof(int)*smartlist_len(the_nodes
));
2127 SMARTLIST_FOREACH_BEGIN(the_nodes
, const node_t
*, node
) {
2128 const int i
= node_sl_idx
;
2129 if (router_digest_is_me(node
->identity
)) {
2130 n_supported
[i
] = -1;
2131 // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
2132 /* XXX there's probably a reverse predecessor attack here, but
2133 * it's slow. should we take this out? -RD
2137 if (!node_has_descriptor(node
)) {
2138 n_supported
[i
] = -1;
2141 if (!node
->is_running
|| node
->is_bad_exit
) {
2142 n_supported
[i
] = -1;
2143 continue; /* skip routers that are known to be down or bad exits */
2145 if (node_get_purpose(node
) != ROUTER_PURPOSE_GENERAL
) {
2146 /* never pick a non-general node as a random exit. */
2147 n_supported
[i
] = -1;
2150 if (routerset_contains_node(options
->ExcludeExitNodesUnion_
, node
)) {
2151 n_supported
[i
] = -1;
2152 continue; /* user asked us not to use it, no matter what */
2154 if (options
->ExitNodes
&&
2155 !routerset_contains_node(options
->ExitNodes
, node
)) {
2156 n_supported
[i
] = -1;
2157 continue; /* not one of our chosen exit nodes */
2160 if (node_is_unreliable(node
, need_uptime
, need_capacity
, 0)) {
2161 n_supported
[i
] = -1;
2162 continue; /* skip routers that are not suitable. Don't worry if
2163 * this makes us reject all the possible routers: if so,
2164 * we'll retry later in this function with need_update and
2165 * need_capacity set to 0. */
2167 if (!(node
->is_valid
|| options
->AllowInvalid_
& ALLOW_INVALID_EXIT
)) {
2168 /* if it's invalid and we don't want it */
2169 n_supported
[i
] = -1;
2170 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
2171 // router->nickname, i);
2172 continue; /* skip invalid routers */
2174 if (options
->ExcludeSingleHopRelays
&&
2175 node_allows_single_hop_exits(node
)) {
2176 n_supported
[i
] = -1;
2179 if (node_exit_policy_rejects_all(node
)) {
2180 n_supported
[i
] = -1;
2181 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
2182 // router->nickname, i);
2183 continue; /* skip routers that reject all */
2186 /* iterate over connections */
2187 SMARTLIST_FOREACH_BEGIN(connections
, connection_t
*, conn
) {
2188 if (!ap_stream_wants_exit_attention(conn
))
2189 continue; /* Skip everything but APs in CIRCUIT_WAIT */
2190 if (connection_ap_can_use_exit(TO_ENTRY_CONN(conn
), node
)) {
2192 // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
2193 // router->nickname, i, n_supported[i]);
2195 // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
2196 // router->nickname, i);
2198 } SMARTLIST_FOREACH_END(conn
);
2199 if (n_pending_connections
> 0 && n_supported
[i
] == 0) {
2200 /* Leave best_support at -1 if that's where it is, so we can
2201 * distinguish it later. */
2204 if (n_supported
[i
] > best_support
) {
2205 /* If this router is better than previous ones, remember its index
2206 * and goodness, and start counting how many routers are this good. */
2207 best_support
= n_supported
[i
]; n_best_support
=1;
2208 // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
2209 // router->nickname);
2210 } else if (n_supported
[i
] == best_support
) {
2211 /* If this router is _as good_ as the best one, just increment the
2212 * count of equally good routers.*/
2215 } SMARTLIST_FOREACH_END(node
);
2217 "Found %d servers that might support %d/%d pending connections.",
2218 n_best_support
, best_support
>= 0 ? best_support
: 0,
2219 n_pending_connections
);
2221 /* If any routers definitely support any pending connections, choose one
2223 if (best_support
> 0) {
2224 smartlist_t
*supporting
= smartlist_new();
2226 SMARTLIST_FOREACH(the_nodes
, const node_t
*, node
, {
2227 if (n_supported
[node_sl_idx
] == best_support
)
2228 smartlist_add(supporting
, (void*)node
);
2231 node
= node_sl_choose_by_bandwidth(supporting
, WEIGHT_FOR_EXIT
);
2232 smartlist_free(supporting
);
2234 /* Either there are no pending connections, or no routers even seem to
2235 * possibly support any of them. Choose a router at random that satisfies
2236 * at least one predicted exit port. */
2239 smartlist_t
*needed_ports
, *supporting
;
2241 if (best_support
== -1) {
2242 if (need_uptime
|| need_capacity
) {
2244 "We couldn't find any live%s%s routers; falling back "
2245 "to list of all routers.",
2246 need_capacity
?", fast":"",
2247 need_uptime
?", stable":"");
2248 tor_free(n_supported
);
2249 return choose_good_exit_server_general(0, 0);
2251 log_notice(LD_CIRC
, "All routers are down or won't exit%s -- "
2252 "choosing a doomed exit at random.",
2253 options
->ExcludeExitNodesUnion_
? " or are Excluded" : "");
2255 supporting
= smartlist_new();
2256 needed_ports
= circuit_get_unhandled_ports(time(NULL
));
2257 for (attempt
= 0; attempt
< 2; attempt
++) {
2258 /* try once to pick only from routers that satisfy a needed port,
2259 * then if there are none, pick from any that support exiting. */
2260 SMARTLIST_FOREACH_BEGIN(the_nodes
, const node_t
*, node
) {
2261 if (n_supported
[node_sl_idx
] != -1 &&
2262 (attempt
|| node_handles_some_port(node
, needed_ports
))) {
2263 // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
2264 // try, router->nickname);
2265 smartlist_add(supporting
, (void*)node
);
2267 } SMARTLIST_FOREACH_END(node
);
2269 node
= node_sl_choose_by_bandwidth(supporting
, WEIGHT_FOR_EXIT
);
2272 smartlist_clear(supporting
);
2273 /* If we reach this point, we can't actually support any unhandled
2274 * predicted ports, so clear all the remaining ones. */
2275 if (smartlist_len(needed_ports
))
2276 rep_hist_remove_predicted_ports(needed_ports
);
2278 SMARTLIST_FOREACH(needed_ports
, uint16_t *, cp
, tor_free(cp
));
2279 smartlist_free(needed_ports
);
2280 smartlist_free(supporting
);
2283 tor_free(n_supported
);
2285 log_info(LD_CIRC
, "Chose exit server '%s'", node_describe(node
));
2288 if (options
->ExitNodes
) {
2290 "No specified %sexit routers seem to be running: "
2291 "can't choose an exit.",
2292 options
->ExcludeExitNodesUnion_
? "non-excluded " : "");
2297 /** Return a pointer to a suitable router to be the exit node for the
2298 * circuit of purpose <b>purpose</b> that we're about to build (or NULL
2299 * if no router is suitable).
2301 * For general-purpose circuits, pass it off to
2302 * choose_good_exit_server_general()
2304 * For client-side rendezvous circuits, choose a random node, weighted
2305 * toward the preferences in 'options'.
2307 static const node_t
*
2308 choose_good_exit_server(uint8_t purpose
,
2309 int need_uptime
, int need_capacity
, int is_internal
)
2311 const or_options_t
*options
= get_options();
2312 router_crn_flags_t flags
= CRN_NEED_DESC
;
2314 flags
|= CRN_NEED_UPTIME
;
2316 flags
|= CRN_NEED_CAPACITY
;
2319 case CIRCUIT_PURPOSE_C_GENERAL
:
2320 if (options
->AllowInvalid_
& ALLOW_INVALID_MIDDLE
)
2321 flags
|= CRN_ALLOW_INVALID
;
2322 if (is_internal
) /* pick it like a middle hop */
2323 return router_choose_random_node(NULL
, options
->ExcludeNodes
, flags
);
2325 return choose_good_exit_server_general(need_uptime
,need_capacity
);
2326 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
2327 if (options
->AllowInvalid_
& ALLOW_INVALID_RENDEZVOUS
)
2328 flags
|= CRN_ALLOW_INVALID
;
2329 return router_choose_random_node(NULL
, options
->ExcludeNodes
, flags
);
2331 log_warn(LD_BUG
,"Unhandled purpose %d", purpose
);
2332 tor_fragile_assert();
2336 /** Log a warning if the user specified an exit for the circuit that
2337 * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
2339 warn_if_last_router_excluded(origin_circuit_t
*circ
, const extend_info_t
*exit
)
2341 const or_options_t
*options
= get_options();
2342 routerset_t
*rs
= options
->ExcludeNodes
;
2343 const char *description
;
2344 uint8_t purpose
= circ
->base_
.purpose
;
2346 if (circ
->build_state
->onehop_tunnel
)
2352 case CIRCUIT_PURPOSE_OR
:
2353 case CIRCUIT_PURPOSE_INTRO_POINT
:
2354 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
2355 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
2356 log_warn(LD_BUG
, "Called on non-origin circuit (purpose %d, %s)",
2358 circuit_purpose_to_string(purpose
));
2360 case CIRCUIT_PURPOSE_C_GENERAL
:
2361 if (circ
->build_state
->is_internal
)
2363 description
= "requested exit node";
2364 rs
= options
->ExcludeExitNodesUnion_
;
2366 case CIRCUIT_PURPOSE_C_INTRODUCING
:
2367 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
2368 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
2369 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
2370 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
2371 case CIRCUIT_PURPOSE_S_REND_JOINED
:
2372 case CIRCUIT_PURPOSE_TESTING
:
2374 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
2375 case CIRCUIT_PURPOSE_C_REND_READY
:
2376 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
2377 case CIRCUIT_PURPOSE_C_REND_JOINED
:
2378 description
= "chosen rendezvous point";
2380 case CIRCUIT_PURPOSE_CONTROLLER
:
2381 rs
= options
->ExcludeExitNodesUnion_
;
2382 description
= "controller-selected circuit target";
2386 if (routerset_contains_extendinfo(rs
, exit
)) {
2387 /* We should never get here if StrictNodes is set to 1. */
2388 if (options
->StrictNodes
) {
2389 log_warn(LD_BUG
, "Using %s '%s' which is listed in ExcludeNodes%s, "
2390 "even though StrictNodes is set. Please report. "
2391 "(Circuit purpose: %s)",
2392 description
, extend_info_describe(exit
),
2393 rs
==options
->ExcludeNodes
?"":" or ExcludeExitNodes",
2394 circuit_purpose_to_string(purpose
));
2396 log_warn(LD_CIRC
, "Using %s '%s' which is listed in "
2397 "ExcludeNodes%s, because no better options were available. To "
2398 "prevent this (and possibly break your Tor functionality), "
2399 "set the StrictNodes configuration option. "
2400 "(Circuit purpose: %s)",
2401 description
, extend_info_describe(exit
),
2402 rs
==options
->ExcludeNodes
?"":" or ExcludeExitNodes",
2403 circuit_purpose_to_string(purpose
));
2405 circuit_log_path(LOG_WARN
, LD_CIRC
, circ
);
2411 /** Decide a suitable length for circ's cpath, and pick an exit
2412 * router (or use <b>exit</b> if provided). Store these in the
2413 * cpath. Return 0 if ok, -1 if circuit should be closed. */
2415 onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
2417 cpath_build_state_t
*state
= circ
->build_state
;
2419 if (state
->onehop_tunnel
) {
2420 log_debug(LD_CIRC
, "Launching a one-hop circuit for dir tunnel.");
2421 state
->desired_path_len
= 1;
2423 int r
= new_route_len(circ
->base_
.purpose
, exit
, nodelist_get_list());
2424 if (r
< 1) /* must be at least 1 */
2426 state
->desired_path_len
= r
;
2429 if (exit
) { /* the circuit-builder pre-requested one */
2430 warn_if_last_router_excluded(circ
, exit
);
2431 log_info(LD_CIRC
,"Using requested exit node '%s'",
2432 extend_info_describe(exit
));
2433 exit
= extend_info_dup(exit
);
2434 } else { /* we have to decide one */
2435 const node_t
*node
=
2436 choose_good_exit_server(circ
->base_
.purpose
, state
->need_uptime
,
2437 state
->need_capacity
, state
->is_internal
);
2439 log_warn(LD_CIRC
,"failed to choose an exit server");
2442 exit
= extend_info_from_node(node
, 0);
2445 state
->chosen_exit
= exit
;
2449 /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
2450 * hop to the cpath reflecting this. Don't send the next extend cell --
2451 * the caller will do this if it wants to.
2454 circuit_append_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
2456 cpath_build_state_t
*state
;
2460 state
= circ
->build_state
;
2462 extend_info_free(state
->chosen_exit
);
2463 state
->chosen_exit
= extend_info_dup(exit
);
2465 ++circ
->build_state
->desired_path_len
;
2466 onion_append_hop(&circ
->cpath
, exit
);
2470 /** Take an open <b>circ</b>, and add a new hop at the end, based on
2471 * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
2472 * send the next extend cell to begin connecting to that hop.
2475 circuit_extend_to_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
2478 warn_if_last_router_excluded(circ
, exit
);
2479 circuit_append_new_exit(circ
, exit
);
2480 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
2481 if ((err_reason
= circuit_send_next_onion_skin(circ
))<0) {
2482 log_warn(LD_CIRC
, "Couldn't extend circuit to new point %s.",
2483 extend_info_describe(exit
));
2484 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
2488 /* Set timestamp_dirty, so we can check it for path use bias */
2489 if (!circ
->base_
.timestamp_dirty
)
2490 circ
->base_
.timestamp_dirty
= time(NULL
);
2495 /** Return the number of routers in <b>routers</b> that are currently up
2496 * and available for building circuits through.
2499 count_acceptable_nodes(smartlist_t
*nodes
)
2503 SMARTLIST_FOREACH_BEGIN(nodes
, const node_t
*, node
) {
2504 // log_debug(LD_CIRC,
2505 // "Contemplating whether router %d (%s) is a new option.",
2507 if (! node
->is_running
)
2508 // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
2510 if (! node
->is_valid
)
2511 // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
2513 if (! node_has_descriptor(node
))
2515 /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
2516 * allows this node in some places, then we're getting an inaccurate
2517 * count. For now, be conservative and don't count it. But later we
2518 * should try to be smarter. */
2520 } SMARTLIST_FOREACH_END(node
);
2522 // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
2527 /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
2528 * This function is used to extend cpath by another hop.
2531 onion_append_to_cpath(crypt_path_t
**head_ptr
, crypt_path_t
*new_hop
)
2534 new_hop
->next
= (*head_ptr
);
2535 new_hop
->prev
= (*head_ptr
)->prev
;
2536 (*head_ptr
)->prev
->next
= new_hop
;
2537 (*head_ptr
)->prev
= new_hop
;
2539 *head_ptr
= new_hop
;
2540 new_hop
->prev
= new_hop
->next
= new_hop
;
2544 /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
2545 * and <b>state</b> and the cpath <b>head</b> (currently populated only
2546 * to length <b>cur_len</b> to decide a suitable middle hop for a
2547 * circuit. In particular, make sure we don't pick the exit node or its
2548 * family, and make sure we don't duplicate any previous nodes or their
2550 static const node_t
*
2551 choose_good_middle_server(uint8_t purpose
,
2552 cpath_build_state_t
*state
,
2557 const node_t
*r
, *choice
;
2558 crypt_path_t
*cpath
;
2559 smartlist_t
*excluded
;
2560 const or_options_t
*options
= get_options();
2561 router_crn_flags_t flags
= CRN_NEED_DESC
;
2562 tor_assert(CIRCUIT_PURPOSE_MIN_
<= purpose
&&
2563 purpose
<= CIRCUIT_PURPOSE_MAX_
);
2565 log_debug(LD_CIRC
, "Contemplating intermediate hop: random choice.");
2566 excluded
= smartlist_new();
2567 if ((r
= build_state_get_exit_node(state
))) {
2568 nodelist_add_node_and_family(excluded
, r
);
2570 for (i
= 0, cpath
= head
; i
< cur_len
; ++i
, cpath
=cpath
->next
) {
2571 if ((r
= node_get_by_id(cpath
->extend_info
->identity_digest
))) {
2572 nodelist_add_node_and_family(excluded
, r
);
2576 if (state
->need_uptime
)
2577 flags
|= CRN_NEED_UPTIME
;
2578 if (state
->need_capacity
)
2579 flags
|= CRN_NEED_CAPACITY
;
2580 if (options
->AllowInvalid_
& ALLOW_INVALID_MIDDLE
)
2581 flags
|= CRN_ALLOW_INVALID
;
2582 choice
= router_choose_random_node(excluded
, options
->ExcludeNodes
, flags
);
2583 smartlist_free(excluded
);
2587 /** Pick a good entry server for the circuit to be built according to
2588 * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
2589 * router (if we're an OR), and respect firewall settings; if we're
2590 * configured to use entry guards, return one.
2592 * If <b>state</b> is NULL, we're choosing a router to serve as an entry
2593 * guard, not for any particular circuit.
2595 /* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
2597 choose_good_entry_server(uint8_t purpose
, cpath_build_state_t
*state
)
2599 const node_t
*choice
;
2600 smartlist_t
*excluded
;
2601 const or_options_t
*options
= get_options();
2602 router_crn_flags_t flags
= CRN_NEED_GUARD
|CRN_NEED_DESC
;
2605 if (state
&& options
->UseEntryGuards
&&
2606 (purpose
!= CIRCUIT_PURPOSE_TESTING
|| options
->BridgeRelay
)) {
2607 /* This request is for an entry server to use for a regular circuit,
2608 * and we use entry guard nodes. Just return one of the guard nodes. */
2609 return choose_random_entry(state
);
2612 excluded
= smartlist_new();
2614 if (state
&& (node
= build_state_get_exit_node(state
))) {
2615 /* Exclude the exit node from the state, if we have one. Also exclude its
2617 nodelist_add_node_and_family(excluded
, node
);
2619 if (firewall_is_fascist_or()) {
2620 /* Exclude all ORs that we can't reach through our firewall */
2621 smartlist_t
*nodes
= nodelist_get_list();
2622 SMARTLIST_FOREACH(nodes
, const node_t
*, node
, {
2623 if (!fascist_firewall_allows_node(node
))
2624 smartlist_add(excluded
, (void*)node
);
2627 /* and exclude current entry guards and their families, if applicable */
2628 if (options
->UseEntryGuards
) {
2629 SMARTLIST_FOREACH(get_entry_guards(), const entry_guard_t
*, entry
,
2631 if ((node
= node_get_by_id(entry
->identity
))) {
2632 nodelist_add_node_and_family(excluded
, node
);
2638 if (state
->need_uptime
)
2639 flags
|= CRN_NEED_UPTIME
;
2640 if (state
->need_capacity
)
2641 flags
|= CRN_NEED_CAPACITY
;
2643 if (options
->AllowInvalid_
& ALLOW_INVALID_ENTRY
)
2644 flags
|= CRN_ALLOW_INVALID
;
2646 choice
= router_choose_random_node(excluded
, options
->ExcludeNodes
, flags
);
2647 smartlist_free(excluded
);
2651 /** Return the first non-open hop in cpath, or return NULL if all
2653 static crypt_path_t
*
2654 onion_next_hop_in_cpath(crypt_path_t
*cpath
)
2656 crypt_path_t
*hop
= cpath
;
2658 if (hop
->state
!= CPATH_STATE_OPEN
)
2661 } while (hop
!= cpath
);
2665 /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
2666 * based on <b>state</b>. Append the hop info to head_ptr.
2669 onion_extend_cpath(origin_circuit_t
*circ
)
2671 uint8_t purpose
= circ
->base_
.purpose
;
2672 cpath_build_state_t
*state
= circ
->build_state
;
2673 int cur_len
= circuit_get_cpath_len(circ
);
2674 extend_info_t
*info
= NULL
;
2676 if (cur_len
>= state
->desired_path_len
) {
2677 log_debug(LD_CIRC
, "Path is complete: %d steps long",
2678 state
->desired_path_len
);
2682 log_debug(LD_CIRC
, "Path is %d long; we want %d", cur_len
,
2683 state
->desired_path_len
);
2685 if (cur_len
== state
->desired_path_len
- 1) { /* Picking last node */
2686 info
= extend_info_dup(state
->chosen_exit
);
2687 } else if (cur_len
== 0) { /* picking first node */
2688 const node_t
*r
= choose_good_entry_server(purpose
, state
);
2690 /* If we're a client, use the preferred address rather than the
2691 primary address, for potentially connecting to an IPv6 OR
2693 info
= extend_info_from_node(r
, server_mode(get_options()) == 0);
2698 choose_good_middle_server(purpose
, state
, circ
->cpath
, cur_len
);
2700 info
= extend_info_from_node(r
, 0);
2706 log_warn(LD_CIRC
,"Failed to find node for hop %d of our path. Discarding "
2707 "this circuit.", cur_len
);
2711 log_debug(LD_CIRC
,"Chose router %s for hop %d (exit is %s)",
2712 extend_info_describe(info
),
2713 cur_len
+1, build_state_get_exit_nickname(state
));
2715 onion_append_hop(&circ
->cpath
, info
);
2716 extend_info_free(info
);
2720 /** Create a new hop, annotate it with information about its
2721 * corresponding router <b>choice</b>, and append it to the
2722 * end of the cpath <b>head_ptr</b>. */
2724 onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
)
2726 crypt_path_t
*hop
= tor_malloc_zero(sizeof(crypt_path_t
));
2728 /* link hop into the cpath, at the end. */
2729 onion_append_to_cpath(head_ptr
, hop
);
2731 hop
->magic
= CRYPT_PATH_MAGIC
;
2732 hop
->state
= CPATH_STATE_CLOSED
;
2734 hop
->extend_info
= extend_info_dup(choice
);
2736 hop
->package_window
= circuit_initial_package_window();
2737 hop
->deliver_window
= CIRCWINDOW_START
;
2742 /** Allocate a new extend_info object based on the various arguments. */
2744 extend_info_new(const char *nickname
, const char *digest
,
2745 crypto_pk_t
*onion_key
,
2746 const tor_addr_t
*addr
, uint16_t port
)
2748 extend_info_t
*info
= tor_malloc_zero(sizeof(extend_info_t
));
2749 memcpy(info
->identity_digest
, digest
, DIGEST_LEN
);
2751 strlcpy(info
->nickname
, nickname
, sizeof(info
->nickname
));
2753 info
->onion_key
= crypto_pk_dup_key(onion_key
);
2754 tor_addr_copy(&info
->addr
, addr
);
2759 /** Allocate and return a new extend_info that can be used to build a
2760 * circuit to or through the node <b>node</b>. Use the primary address
2761 * of the node (i.e. its IPv4 address) unless
2762 * <b>for_direct_connect</b> is true, in which case the preferred
2763 * address is used instead. May return NULL if there is not enough
2764 * info about <b>node</b> to extend to it--for example, if there is no
2765 * routerinfo_t or microdesc_t.
2768 extend_info_from_node(const node_t
*node
, int for_direct_connect
)
2772 if (node
->ri
== NULL
&& (node
->rs
== NULL
|| node
->md
== NULL
))
2775 if (for_direct_connect
)
2776 node_get_pref_orport(node
, &ap
);
2778 node_get_prim_orport(node
, &ap
);
2780 log_debug(LD_CIRC
, "using %s for %s",
2781 fmt_addrport(&ap
.addr
, ap
.port
),
2782 node
->ri
? node
->ri
->nickname
: node
->rs
->nickname
);
2785 return extend_info_new(node
->ri
->nickname
,
2787 node
->ri
->onion_pkey
,
2790 else if (node
->rs
&& node
->md
)
2791 return extend_info_new(node
->rs
->nickname
,
2793 node
->md
->onion_pkey
,
2800 /** Release storage held by an extend_info_t struct. */
2802 extend_info_free(extend_info_t
*info
)
2806 crypto_pk_free(info
->onion_key
);
2810 /** Allocate and return a new extend_info_t with the same contents as
2813 extend_info_dup(extend_info_t
*info
)
2815 extend_info_t
*newinfo
;
2817 newinfo
= tor_malloc(sizeof(extend_info_t
));
2818 memcpy(newinfo
, info
, sizeof(extend_info_t
));
2819 if (info
->onion_key
)
2820 newinfo
->onion_key
= crypto_pk_dup_key(info
->onion_key
);
2822 newinfo
->onion_key
= NULL
;
2826 /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
2827 * If there is no chosen exit, or if we don't know the routerinfo_t for
2828 * the chosen exit, return NULL.
2831 build_state_get_exit_node(cpath_build_state_t
*state
)
2833 if (!state
|| !state
->chosen_exit
)
2835 return node_get_by_id(state
->chosen_exit
->identity_digest
);
2838 /** Return the nickname for the chosen exit router in <b>state</b>. If
2839 * there is no chosen exit, or if we don't know the routerinfo_t for the
2840 * chosen exit, return NULL.
2843 build_state_get_exit_nickname(cpath_build_state_t
*state
)
2845 if (!state
|| !state
->chosen_exit
)
2847 return state
->chosen_exit
->nickname
;