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-2011, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
9 * \brief The actual details of building circuits.
14 /********* START VARIABLES **********/
16 /** A global list of all circuits at this hop. */
17 extern circuit_t
*global_circuitlist
;
19 /** An entry_guard_t represents our information about a chosen long-term
20 * first hop, known as a "helper" node in the literature. We can't just
21 * use a routerinfo_t, since we want to remember these even when we
22 * don't have a directory. */
24 char nickname
[MAX_NICKNAME_LEN
+1];
25 char identity
[DIGEST_LEN
];
26 time_t chosen_on_date
; /**< Approximately when was this guard added?
27 * "0" if we don't know. */
28 char *chosen_by_version
; /**< What tor version added this guard? NULL
29 * if we don't know. */
30 unsigned int made_contact
: 1; /**< 0 if we have never connected to this
31 * router, 1 if we have. */
32 unsigned int can_retry
: 1; /**< Should we retry connecting to this entry,
33 * in spite of having it marked as unreachable?*/
34 time_t bad_since
; /**< 0 if this guard is currently usable, or the time at
35 * which it was observed to become (according to the
36 * directory or the user configuration) unusable. */
37 time_t unreachable_since
; /**< 0 if we can connect to this guard, or the
38 * time at which we first noticed we couldn't
40 time_t last_attempted
; /**< 0 if we can connect to this guard, or the time
41 * at which we last failed to connect to it. */
44 /** A list of our chosen entry guards. */
45 static smartlist_t
*entry_guards
= NULL
;
46 /** A value of 1 means that the entry_guards list has changed
47 * and those changes need to be flushed to disk. */
48 static int entry_guards_dirty
= 0;
50 /********* END VARIABLES ************/
52 static int circuit_deliver_create_cell(circuit_t
*circ
,
53 uint8_t cell_type
, const char *payload
);
54 static int onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
);
55 static crypt_path_t
*onion_next_hop_in_cpath(crypt_path_t
*cpath
);
56 static int onion_extend_cpath(origin_circuit_t
*circ
);
57 static int count_acceptable_routers(smartlist_t
*routers
);
58 static int onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
);
60 static void entry_guards_changed(void);
62 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
63 * and with the high bit specified by conn-\>circ_id_type, until we get
64 * a circ_id that is not in use by any other circuit on that conn.
66 * Return it, or 0 if can't get a unique circ_id.
69 get_unique_circ_id_by_conn(or_connection_t
*conn
)
71 circid_t test_circ_id
;
76 if (conn
->circ_id_type
== CIRC_ID_TYPE_NEITHER
) {
77 log_warn(LD_BUG
, "Trying to pick a circuit ID for a connection from "
78 "a client with no identity.");
81 high_bit
= (conn
->circ_id_type
== CIRC_ID_TYPE_HIGHER
) ? 1<<15 : 0;
83 /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
84 * circID such that (high_bit|test_circ_id) is not already used. */
85 test_circ_id
= conn
->next_circ_id
++;
86 if (test_circ_id
== 0 || test_circ_id
>= 1<<15) {
88 conn
->next_circ_id
= 2;
90 if (++attempts
> 1<<15) {
91 /* Make sure we don't loop forever if all circ_id's are used. This
92 * matters because it's an external DoS opportunity.
94 log_warn(LD_CIRC
,"No unused circ IDs. Failing.");
97 test_circ_id
|= high_bit
;
98 } while (circuit_id_in_use_on_orconn(test_circ_id
, conn
));
102 /** If <b>verbose</b> is false, allocate and return a comma-separated list of
103 * the currently built elements of circuit_t. If <b>verbose</b> is true, also
104 * list information about link status in a more verbose format using spaces.
105 * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
106 * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
110 circuit_list_path_impl(origin_circuit_t
*circ
, int verbose
, int verbose_names
)
113 smartlist_t
*elements
;
114 const char *states
[] = {"closed", "waiting for keys", "open"};
118 elements
= smartlist_create();
121 const char *nickname
= build_state_get_exit_nickname(circ
->build_state
);
122 tor_snprintf(buf
, sizeof(buf
), "%s%s circ (length %d%s%s):",
123 circ
->build_state
->is_internal
? "internal" : "exit",
124 circ
->build_state
->need_uptime
? " (high-uptime)" : "",
125 circ
->build_state
->desired_path_len
,
126 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" : ", exit ",
127 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" :
128 (nickname
?nickname
:"*unnamed*"));
129 smartlist_add(elements
, tor_strdup(buf
));
140 if (!verbose
&& hop
->state
!= CPATH_STATE_OPEN
)
142 if (!hop
->extend_info
)
144 id
= hop
->extend_info
->identity_digest
;
146 elt
= tor_malloc(MAX_VERBOSE_NICKNAME_LEN
+1);
147 if ((ri
= router_get_by_digest(id
))) {
148 router_get_verbose_nickname(elt
, ri
);
149 } else if ((rs
= router_get_consensus_status_by_id(id
))) {
150 routerstatus_get_verbose_nickname(elt
, rs
);
151 } else if (hop
->extend_info
->nickname
&&
152 is_legal_nickname(hop
->extend_info
->nickname
)) {
154 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
155 elt
[HEX_DIGEST_LEN
+1]= '~';
156 strlcpy(elt
+HEX_DIGEST_LEN
+2,
157 hop
->extend_info
->nickname
, MAX_NICKNAME_LEN
+1);
160 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
162 } else { /* ! verbose_names */
163 if ((ri
= router_get_by_digest(id
)) &&
165 elt
= tor_strdup(hop
->extend_info
->nickname
);
167 elt
= tor_malloc(HEX_DIGEST_LEN
+2);
169 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
174 size_t len
= strlen(elt
)+2+strlen(states
[hop
->state
])+1;
175 char *v
= tor_malloc(len
);
176 tor_assert(hop
->state
<= 2);
177 tor_snprintf(v
,len
,"%s(%s)",elt
,states
[hop
->state
]);
178 smartlist_add(elements
, v
);
181 smartlist_add(elements
, elt
);
184 } while (hop
!= circ
->cpath
);
186 s
= smartlist_join_strings(elements
, verbose
?" ":",", 0, NULL
);
187 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
188 smartlist_free(elements
);
192 /** If <b>verbose</b> is false, allocate and return a comma-separated
193 * list of the currently built elements of circuit_t. If
194 * <b>verbose</b> is true, also list information about link status in
195 * a more verbose format using spaces.
198 circuit_list_path(origin_circuit_t
*circ
, int verbose
)
200 return circuit_list_path_impl(circ
, verbose
, 0);
203 /** Allocate and return a comma-separated list of the currently built elements
204 * of circuit_t, giving each as a verbose nickname.
207 circuit_list_path_for_controller(origin_circuit_t
*circ
)
209 return circuit_list_path_impl(circ
, 0, 1);
212 /** Log, at severity <b>severity</b>, the nicknames of each router in
213 * circ's cpath. Also log the length of the cpath, and the intended
217 circuit_log_path(int severity
, unsigned int domain
, origin_circuit_t
*circ
)
219 char *s
= circuit_list_path(circ
,1);
220 log(severity
,domain
,"%s",s
);
224 /** Tell the rep(utation)hist(ory) module about the status of the links
225 * in circ. Hops that have become OPEN are marked as successfully
226 * extended; the _first_ hop that isn't open (if any) is marked as
229 /* XXXX Someday we should learn from OR circuits too. */
231 circuit_rep_hist_note_result(origin_circuit_t
*circ
)
234 char *prev_digest
= NULL
;
235 routerinfo_t
*router
;
237 if (!hop
) /* circuit hasn't started building yet. */
239 if (server_mode(get_options())) {
240 routerinfo_t
*me
= router_get_my_routerinfo();
243 prev_digest
= me
->cache_info
.identity_digest
;
246 router
= router_get_by_digest(hop
->extend_info
->identity_digest
);
249 if (hop
->state
== CPATH_STATE_OPEN
)
250 rep_hist_note_extend_succeeded(prev_digest
,
251 router
->cache_info
.identity_digest
);
253 rep_hist_note_extend_failed(prev_digest
,
254 router
->cache_info
.identity_digest
);
258 prev_digest
= router
->cache_info
.identity_digest
;
263 } while (hop
!=circ
->cpath
);
266 /** Pick all the entries in our cpath. Stop and return 0 when we're
267 * happy, or return -1 if an error occurs. */
269 onion_populate_cpath(origin_circuit_t
*circ
)
273 r
= onion_extend_cpath(circ
);
275 log_info(LD_CIRC
,"Generating cpath hop failed.");
280 return 0; /* if r == 1 */
283 /** Create and return a new origin circuit. Initialize its purpose and
284 * build-state based on our arguments. The <b>flags</b> argument is a
285 * bitfield of CIRCLAUNCH_* flags. */
287 origin_circuit_init(uint8_t purpose
, int flags
)
289 /* sets circ->p_circ_id and circ->p_conn */
290 origin_circuit_t
*circ
= origin_circuit_new();
291 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OR_WAIT
);
292 circ
->build_state
= tor_malloc_zero(sizeof(cpath_build_state_t
));
293 circ
->build_state
->onehop_tunnel
=
294 ((flags
& CIRCLAUNCH_ONEHOP_TUNNEL
) ? 1 : 0);
295 circ
->build_state
->need_uptime
=
296 ((flags
& CIRCLAUNCH_NEED_UPTIME
) ? 1 : 0);
297 circ
->build_state
->need_capacity
=
298 ((flags
& CIRCLAUNCH_NEED_CAPACITY
) ? 1 : 0);
299 circ
->build_state
->is_internal
=
300 ((flags
& CIRCLAUNCH_IS_INTERNAL
) ? 1 : 0);
301 circ
->_base
.purpose
= purpose
;
305 /** Build a new circuit for <b>purpose</b>. If <b>exit</b>
306 * is defined, then use that as your exit router, else choose a suitable
309 * Also launch a connection to the first OR in the chosen path, if
310 * it's not open already.
313 circuit_establish_circuit(uint8_t purpose
, extend_info_t
*exit
, int flags
)
315 origin_circuit_t
*circ
;
318 circ
= origin_circuit_init(purpose
, flags
);
320 if (onion_pick_cpath_exit(circ
, exit
) < 0 ||
321 onion_populate_cpath(circ
) < 0) {
322 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_NOPATH
);
326 control_event_circuit_status(circ
, CIRC_EVENT_LAUNCHED
, 0);
328 if ((err_reason
= circuit_handle_first_hop(circ
)) < 0) {
329 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
335 /** Start establishing the first hop of our circuit. Figure out what
336 * OR we should connect to, and if necessary start the connection to
337 * it. If we're already connected, then send the 'create' cell.
338 * Return 0 for ok, -reason if circ should be marked-for-close. */
340 circuit_handle_first_hop(origin_circuit_t
*circ
)
342 crypt_path_t
*firsthop
;
343 or_connection_t
*n_conn
;
345 const char *msg
= NULL
;
346 int should_launch
= 0;
348 firsthop
= onion_next_hop_in_cpath(circ
->cpath
);
349 tor_assert(firsthop
);
350 tor_assert(firsthop
->extend_info
);
352 /* now see if we're already connected to the first OR in 'route' */
353 log_debug(LD_CIRC
,"Looking for firsthop '%s:%u'",
354 fmt_addr(&firsthop
->extend_info
->addr
),
355 firsthop
->extend_info
->port
);
357 n_conn
= connection_or_get_for_extend(firsthop
->extend_info
->identity_digest
,
358 &firsthop
->extend_info
->addr
,
363 /* not currently connected in a useful way. */
364 const char *name
= firsthop
->extend_info
->nickname
?
365 firsthop
->extend_info
->nickname
: fmt_addr(&firsthop
->extend_info
->addr
);
366 log_info(LD_CIRC
, "Next router is %s: %s ", safe_str(name
), msg
?msg
:"???");
367 circ
->_base
.n_hop
= extend_info_dup(firsthop
->extend_info
);
370 if (circ
->build_state
->onehop_tunnel
)
371 control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR
, 0);
372 n_conn
= connection_or_connect(&firsthop
->extend_info
->addr
,
373 firsthop
->extend_info
->port
,
374 firsthop
->extend_info
->identity_digest
);
375 if (!n_conn
) { /* connect failed, forget the whole thing */
376 log_info(LD_CIRC
,"connect to firsthop failed. Closing.");
377 return -END_CIRC_REASON_CONNECTFAILED
;
381 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
382 /* return success. The onion/circuit/etc will be taken care of
383 * automatically (may already have been) whenever n_conn reaches
384 * OR_CONN_STATE_OPEN.
387 } else { /* it's already open. use it. */
388 tor_assert(!circ
->_base
.n_hop
);
389 circ
->_base
.n_conn
= n_conn
;
390 log_debug(LD_CIRC
,"Conn open. Delivering first onion skin.");
391 if ((err_reason
= circuit_send_next_onion_skin(circ
)) < 0) {
392 log_info(LD_CIRC
,"circuit_send_next_onion_skin failed.");
399 /** Find any circuits that are waiting on <b>or_conn</b> to become
400 * open and get them to send their create cells forward.
402 * Status is 1 if connect succeeded, or 0 if connect failed.
405 circuit_n_conn_done(or_connection_t
*or_conn
, int status
)
407 smartlist_t
*pending_circs
;
410 log_debug(LD_CIRC
,"or_conn to %s/%s, status=%d",
411 or_conn
->nickname
? or_conn
->nickname
: "NULL",
412 or_conn
->_base
.address
, status
);
414 pending_circs
= smartlist_create();
415 circuit_get_all_pending_on_or_conn(pending_circs
, or_conn
);
417 SMARTLIST_FOREACH_BEGIN(pending_circs
, circuit_t
*, circ
)
419 /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
420 * leaving them in in case it's possible for the status of a circuit to
421 * change as we're going down the list. */
422 if (circ
->marked_for_close
|| circ
->n_conn
|| !circ
->n_hop
||
423 circ
->state
!= CIRCUIT_STATE_OR_WAIT
)
426 if (tor_digest_is_zero(circ
->n_hop
->identity_digest
)) {
427 /* Look at addr/port. This is an unkeyed connection. */
428 if (!tor_addr_eq(&circ
->n_hop
->addr
, &or_conn
->_base
.addr
) ||
429 circ
->n_hop
->port
!= or_conn
->_base
.port
)
432 /* We expected a key. See if it's the right one. */
433 if (memcmp(or_conn
->identity_digest
,
434 circ
->n_hop
->identity_digest
, DIGEST_LEN
))
437 if (!status
) { /* or_conn failed; close circ */
438 log_info(LD_CIRC
,"or_conn failed. Closing circ.");
439 circuit_mark_for_close(circ
, END_CIRC_REASON_OR_CONN_CLOSED
);
442 log_debug(LD_CIRC
, "Found circ, sending create cell.");
443 /* circuit_deliver_create_cell will set n_circ_id and add us to
444 * orconn_circuid_circuit_map, so we don't need to call
445 * set_circid_orconn here. */
446 circ
->n_conn
= or_conn
;
447 extend_info_free(circ
->n_hop
);
450 if (CIRCUIT_IS_ORIGIN(circ
)) {
452 circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ
))) < 0) {
454 "send_next_onion_skin failed; circuit marked for closing.");
455 circuit_mark_for_close(circ
, -err_reason
);
457 /* XXX could this be bad, eg if next_onion_skin failed because conn
461 /* pull the create cell out of circ->onionskin, and send it */
462 tor_assert(circ
->n_conn_onionskin
);
463 if (circuit_deliver_create_cell(circ
,CELL_CREATE
,
464 circ
->n_conn_onionskin
)<0) {
465 circuit_mark_for_close(circ
, END_CIRC_REASON_RESOURCELIMIT
);
468 tor_free(circ
->n_conn_onionskin
);
469 circuit_set_state(circ
, CIRCUIT_STATE_OPEN
);
472 SMARTLIST_FOREACH_END(circ
);
474 smartlist_free(pending_circs
);
477 /** Find a new circid that isn't currently in use on the circ->n_conn
479 * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
480 * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
482 * Return -1 if we failed to find a suitable circid, else return 0.
485 circuit_deliver_create_cell(circuit_t
*circ
, uint8_t cell_type
,
492 tor_assert(circ
->n_conn
);
494 tor_assert(cell_type
== CELL_CREATE
|| cell_type
== CELL_CREATE_FAST
);
496 id
= get_unique_circ_id_by_conn(circ
->n_conn
);
498 log_warn(LD_CIRC
,"failed to get unique circID.");
501 log_debug(LD_CIRC
,"Chosen circID %u.", id
);
502 circuit_set_n_circid_orconn(circ
, id
, circ
->n_conn
);
504 memset(&cell
, 0, sizeof(cell_t
));
505 cell
.command
= cell_type
;
506 cell
.circ_id
= circ
->n_circ_id
;
508 memcpy(cell
.payload
, payload
, ONIONSKIN_CHALLENGE_LEN
);
509 append_cell_to_circuit_queue(circ
, circ
->n_conn
, &cell
, CELL_DIRECTION_OUT
);
511 if (CIRCUIT_IS_ORIGIN(circ
)) {
512 /* mark it so it gets better rate limiting treatment. */
513 circ
->n_conn
->client_used
= time(NULL
);
519 /** We've decided to start our reachability testing. If all
520 * is set, log this to the user. Return 1 if we did, or 0 if
521 * we chose not to log anything. */
523 inform_testing_reachability(void)
526 routerinfo_t
*me
= router_get_my_routerinfo();
529 control_event_server_status(LOG_NOTICE
,
530 "CHECKING_REACHABILITY ORADDRESS=%s:%d",
531 me
->address
, me
->or_port
);
533 tor_snprintf(dirbuf
, sizeof(dirbuf
), " and DirPort %s:%d",
534 me
->address
, me
->dir_port
);
535 control_event_server_status(LOG_NOTICE
,
536 "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
537 me
->address
, me
->dir_port
);
539 log(LOG_NOTICE
, LD_OR
, "Now checking whether ORPort %s:%d%s %s reachable... "
540 "(this may take up to %d minutes -- look for log "
541 "messages indicating success)",
542 me
->address
, me
->or_port
,
543 me
->dir_port
? dirbuf
: "",
544 me
->dir_port
? "are" : "is",
545 TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT
/60);
550 /** Return true iff we should send a create_fast cell to start building a given
553 should_use_create_fast_for_circuit(origin_circuit_t
*circ
)
555 or_options_t
*options
= get_options();
556 tor_assert(circ
->cpath
);
557 tor_assert(circ
->cpath
->extend_info
);
559 if (!circ
->cpath
->extend_info
->onion_key
)
560 return 1; /* our hand is forced: only a create_fast will work. */
561 if (!options
->FastFirstHopPK
)
562 return 0; /* we prefer to avoid create_fast */
563 if (server_mode(options
)) {
564 /* We're a server, and we know an onion key. We can choose.
565 * Prefer to blend in. */
572 /** This is the backbone function for building circuits.
574 * If circ's first hop is closed, then we need to build a create
575 * cell and send it forward.
577 * Otherwise, we need to build a relay extend cell and send it
580 * Return -reason if we want to tear down circ, else return 0.
583 circuit_send_next_onion_skin(origin_circuit_t
*circ
)
586 routerinfo_t
*router
;
587 char payload
[2+4+DIGEST_LEN
+ONIONSKIN_CHALLENGE_LEN
];
593 if (circ
->cpath
->state
== CPATH_STATE_CLOSED
) {
596 log_debug(LD_CIRC
,"First skin; sending create cell.");
597 if (circ
->build_state
->onehop_tunnel
)
598 control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE
, 0);
600 control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE
, 0);
602 router
= router_get_by_digest(circ
->_base
.n_conn
->identity_digest
);
603 fast
= should_use_create_fast_for_circuit(circ
);
605 /* We are an OR and we know the right onion key: we should
606 * send an old slow create cell.
608 cell_type
= CELL_CREATE
;
609 if (onion_skin_create(circ
->cpath
->extend_info
->onion_key
,
610 &(circ
->cpath
->dh_handshake_state
),
612 log_warn(LD_CIRC
,"onion_skin_create (first hop) failed.");
613 return - END_CIRC_REASON_INTERNAL
;
615 note_request("cell: create", 1);
617 /* We are not an OR, and we're building the first hop of a circuit to a
618 * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
619 * and a DH operation. */
620 cell_type
= CELL_CREATE_FAST
;
621 memset(payload
, 0, sizeof(payload
));
622 crypto_rand((char*) circ
->cpath
->fast_handshake_state
,
623 sizeof(circ
->cpath
->fast_handshake_state
));
624 memcpy(payload
, circ
->cpath
->fast_handshake_state
,
625 sizeof(circ
->cpath
->fast_handshake_state
));
626 note_request("cell: create fast", 1);
629 if (circuit_deliver_create_cell(TO_CIRCUIT(circ
), cell_type
, payload
) < 0)
630 return - END_CIRC_REASON_RESOURCELIMIT
;
632 circ
->cpath
->state
= CPATH_STATE_AWAITING_KEYS
;
633 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
634 log_info(LD_CIRC
,"First hop: finished sending %s cell to '%s'",
635 fast
? "CREATE_FAST" : "CREATE",
636 router
? router
->nickname
: "<unnamed>");
638 tor_assert(circ
->cpath
->state
== CPATH_STATE_OPEN
);
639 tor_assert(circ
->_base
.state
== CIRCUIT_STATE_BUILDING
);
640 log_debug(LD_CIRC
,"starting to send subsequent skin.");
641 hop
= onion_next_hop_in_cpath(circ
->cpath
);
643 /* done building the circuit. whew. */
644 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
645 log_info(LD_CIRC
,"circuit built!");
646 circuit_reset_failure_count(0);
647 if (circ
->build_state
->onehop_tunnel
)
648 control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS
, 0);
649 if (!has_completed_circuit
&& !circ
->build_state
->onehop_tunnel
) {
650 or_options_t
*options
= get_options();
651 has_completed_circuit
=1;
652 /* FFFF Log a count of known routers here */
653 log(LOG_NOTICE
, LD_GENERAL
,
654 "Tor has successfully opened a circuit. "
655 "Looks like client functionality is working.");
656 control_event_bootstrap(BOOTSTRAP_STATUS_DONE
, 0);
657 control_event_client_status(LOG_NOTICE
, "CIRCUIT_ESTABLISHED");
658 if (server_mode(options
) && !check_whether_orport_reachable()) {
659 inform_testing_reachability();
660 consider_testing_reachability(1, 1);
663 circuit_rep_hist_note_result(circ
);
664 circuit_has_opened(circ
); /* do other actions as necessary */
668 if (tor_addr_family(&hop
->extend_info
->addr
) != AF_INET
) {
669 log_warn(LD_BUG
, "Trying to extend to a non-IPv4 address.");
670 return - END_CIRC_REASON_INTERNAL
;
673 set_uint32(payload
, tor_addr_to_ipv4n(&hop
->extend_info
->addr
));
674 set_uint16(payload
+4, htons(hop
->extend_info
->port
));
676 onionskin
= payload
+2+4;
677 memcpy(payload
+2+4+ONIONSKIN_CHALLENGE_LEN
,
678 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
679 payload_len
= 2+4+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
;
681 if (onion_skin_create(hop
->extend_info
->onion_key
,
682 &(hop
->dh_handshake_state
), onionskin
) < 0) {
683 log_warn(LD_CIRC
,"onion_skin_create failed.");
684 return - END_CIRC_REASON_INTERNAL
;
687 log_info(LD_CIRC
,"Sending extend relay cell.");
688 note_request("cell: extend", 1);
689 /* send it to hop->prev, because it will transfer
690 * it to a create cell and then send to hop */
691 if (relay_send_command_from_edge(0, TO_CIRCUIT(circ
),
692 RELAY_COMMAND_EXTEND
,
693 payload
, payload_len
, hop
->prev
) < 0)
694 return 0; /* circuit is closed */
696 hop
->state
= CPATH_STATE_AWAITING_KEYS
;
701 /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
702 * something has also gone wrong with our network: notify the user,
703 * and abandon all not-yet-used circuits. */
705 circuit_note_clock_jumped(int seconds_elapsed
)
707 int severity
= server_mode(get_options()) ? LOG_WARN
: LOG_NOTICE
;
708 log(severity
, LD_GENERAL
, "Your system clock just jumped %d seconds %s; "
709 "assuming established circuits no longer work.",
710 seconds_elapsed
>=0 ? seconds_elapsed
: -seconds_elapsed
,
711 seconds_elapsed
>=0 ? "forward" : "backward");
712 control_event_general_status(LOG_WARN
, "CLOCK_JUMPED TIME=%d",
714 has_completed_circuit
=0; /* so it'll log when it works again */
715 control_event_client_status(severity
, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
717 circuit_mark_all_unused_circs();
718 circuit_expire_all_dirty_circs();
721 /** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
722 * skin and identity digest for the next hop. If we're already connected,
723 * pass the onion skin to the next hop using a create cell; otherwise
724 * launch a new OR connection, and <b>circ</b> will notice when the
725 * connection succeeds or fails.
727 * Return -1 if we want to warn and tear down the circuit, else return 0.
730 circuit_extend(cell_t
*cell
, circuit_t
*circ
)
732 or_connection_t
*n_conn
;
735 char *id_digest
=NULL
;
739 const char *msg
= NULL
;
740 int should_launch
= 0;
743 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
744 "n_conn already set. Bug/attack. Closing.");
748 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
749 "conn to next hop already launched. Bug/attack. Closing.");
753 if (!server_mode(get_options())) {
754 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
755 "Got an extend cell, but running as a client. Closing.");
759 relay_header_unpack(&rh
, cell
->payload
);
761 if (rh
.length
< 4+2+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
) {
762 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
763 "Wrong length %d on extend cell. Closing circuit.",
768 n_addr32
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
));
769 n_port
= ntohs(get_uint16(cell
->payload
+RELAY_HEADER_SIZE
+4));
770 onionskin
= (char*) cell
->payload
+RELAY_HEADER_SIZE
+4+2;
771 id_digest
= (char*) cell
->payload
+RELAY_HEADER_SIZE
+4+2+
772 ONIONSKIN_CHALLENGE_LEN
;
773 tor_addr_from_ipv4h(&n_addr
, n_addr32
);
775 if (!n_port
|| !n_addr32
) {
776 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
777 "Client asked me to extend to zero destination port or addr.");
781 /* Check if they asked us for 0000..0000. We support using
782 * an empty fingerprint for the first hop (e.g. for a bridge relay),
783 * but we don't want to let people send us extend cells for empty
784 * fingerprints -- a) because it opens the user up to a mitm attack,
785 * and b) because it lets an attacker force the relay to hold open a
786 * new TLS connection for each extend request. */
787 if (tor_digest_is_zero(id_digest
)) {
788 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
789 "Client asked me to extend without specifying an id_digest.");
793 /* Next, check if we're being asked to connect to the hop that the
794 * extend cell came from. There isn't any reason for that, and it can
795 * assist circular-path attacks. */
796 if (!memcmp(id_digest
, TO_OR_CIRCUIT(circ
)->p_conn
->identity_digest
,
798 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
799 "Client asked me to extend back to the previous hop.");
803 n_conn
= connection_or_get_for_extend(id_digest
,
809 log_debug(LD_CIRC
|LD_OR
,"Next router (%s:%d): %s",
810 fmt_addr(&n_addr
), (int)n_port
, msg
?msg
:"????");
812 circ
->n_hop
= extend_info_alloc(NULL
/*nickname*/,
817 circ
->n_conn_onionskin
= tor_malloc(ONIONSKIN_CHALLENGE_LEN
);
818 memcpy(circ
->n_conn_onionskin
, onionskin
, ONIONSKIN_CHALLENGE_LEN
);
819 circuit_set_state(circ
, CIRCUIT_STATE_OR_WAIT
);
822 /* we should try to open a connection */
823 n_conn
= connection_or_connect(&n_addr
, n_port
, id_digest
);
825 log_info(LD_CIRC
,"Launching n_conn failed. Closing circuit.");
826 circuit_mark_for_close(circ
, END_CIRC_REASON_CONNECTFAILED
);
829 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
831 /* return success. The onion/circuit/etc will be taken care of
832 * automatically (may already have been) whenever n_conn reaches
833 * OR_CONN_STATE_OPEN.
838 tor_assert(!circ
->n_hop
); /* Connection is already established. */
839 circ
->n_conn
= n_conn
;
840 log_debug(LD_CIRC
,"n_conn is %s:%u",
841 n_conn
->_base
.address
,n_conn
->_base
.port
);
843 if (circuit_deliver_create_cell(circ
, CELL_CREATE
, onionskin
) < 0)
848 /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
849 * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
851 * - 20 to initialize f_digest
852 * - 20 to initialize b_digest
853 * - 16 to key f_crypto
854 * - 16 to key b_crypto
856 * (If 'reverse' is true, then f_XX and b_XX are swapped.)
859 circuit_init_cpath_crypto(crypt_path_t
*cpath
, const char *key_data
,
862 crypto_digest_env_t
*tmp_digest
;
863 crypto_cipher_env_t
*tmp_crypto
;
866 tor_assert(key_data
);
867 tor_assert(!(cpath
->f_crypto
|| cpath
->b_crypto
||
868 cpath
->f_digest
|| cpath
->b_digest
));
870 cpath
->f_digest
= crypto_new_digest_env();
871 crypto_digest_add_bytes(cpath
->f_digest
, key_data
, DIGEST_LEN
);
872 cpath
->b_digest
= crypto_new_digest_env();
873 crypto_digest_add_bytes(cpath
->b_digest
, key_data
+DIGEST_LEN
, DIGEST_LEN
);
875 if (!(cpath
->f_crypto
=
876 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
),1))) {
877 log_warn(LD_BUG
,"Forward cipher initialization failed.");
880 if (!(cpath
->b_crypto
=
881 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
)+CIPHER_KEY_LEN
,0))) {
882 log_warn(LD_BUG
,"Backward cipher initialization failed.");
887 tmp_digest
= cpath
->f_digest
;
888 cpath
->f_digest
= cpath
->b_digest
;
889 cpath
->b_digest
= tmp_digest
;
890 tmp_crypto
= cpath
->f_crypto
;
891 cpath
->f_crypto
= cpath
->b_crypto
;
892 cpath
->b_crypto
= tmp_crypto
;
898 /** A created or extended cell came back to us on the circuit, and it included
899 * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body
900 * contains (the second DH key, plus KH). If <b>reply_type</b> is
901 * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
903 * Calculate the appropriate keys and digests, make sure KH is
904 * correct, and initialize this hop of the cpath.
906 * Return - reason if we want to mark circ for close, else return 0.
909 circuit_finish_handshake(origin_circuit_t
*circ
, uint8_t reply_type
,
910 const uint8_t *reply
)
912 char keys
[CPATH_KEY_MATERIAL_LEN
];
915 if (circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
)
918 hop
= onion_next_hop_in_cpath(circ
->cpath
);
919 if (!hop
) { /* got an extended when we're all done? */
920 log_warn(LD_PROTOCOL
,"got extended when circ already built? Closing.");
921 return - END_CIRC_REASON_TORPROTOCOL
;
924 tor_assert(hop
->state
== CPATH_STATE_AWAITING_KEYS
);
926 if (reply_type
== CELL_CREATED
&& hop
->dh_handshake_state
) {
927 if (onion_skin_client_handshake(hop
->dh_handshake_state
, (char*)reply
,keys
,
928 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
929 log_warn(LD_CIRC
,"onion_skin_client_handshake failed.");
930 return -END_CIRC_REASON_TORPROTOCOL
;
932 /* Remember hash of g^xy */
933 memcpy(hop
->handshake_digest
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
934 } else if (reply_type
== CELL_CREATED_FAST
&& !hop
->dh_handshake_state
) {
935 if (fast_client_handshake(hop
->fast_handshake_state
, reply
,
937 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
938 log_warn(LD_CIRC
,"fast_client_handshake failed.");
939 return -END_CIRC_REASON_TORPROTOCOL
;
941 memcpy(hop
->handshake_digest
, reply
+DIGEST_LEN
, DIGEST_LEN
);
943 log_warn(LD_PROTOCOL
,"CREATED cell type did not match CREATE cell type.");
944 return -END_CIRC_REASON_TORPROTOCOL
;
947 if (hop
->dh_handshake_state
) {
948 crypto_dh_free(hop
->dh_handshake_state
); /* don't need it anymore */
949 hop
->dh_handshake_state
= NULL
;
951 memset(hop
->fast_handshake_state
, 0, sizeof(hop
->fast_handshake_state
));
953 if (circuit_init_cpath_crypto(hop
, keys
, 0)<0) {
954 return -END_CIRC_REASON_TORPROTOCOL
;
957 hop
->state
= CPATH_STATE_OPEN
;
958 log_info(LD_CIRC
,"Finished building %scircuit hop:",
959 (reply_type
== CELL_CREATED_FAST
) ? "fast " : "");
960 circuit_log_path(LOG_INFO
,LD_CIRC
,circ
);
961 control_event_circuit_status(circ
, CIRC_EVENT_EXTENDED
, 0);
966 /** We received a relay truncated cell on circ.
968 * Since we don't ask for truncates currently, getting a truncated
969 * means that a connection broke or an extend failed. For now,
970 * just give up: for circ to close, and return 0.
973 circuit_truncated(origin_circuit_t
*circ
, crypt_path_t
*layer
)
975 // crypt_path_t *victim;
976 // connection_t *stream;
981 /* XXX Since we don't ask for truncates currently, getting a truncated
982 * means that a connection broke or an extend failed. For now,
985 circuit_mark_for_close(TO_CIRCUIT(circ
),
986 END_CIRC_REASON_FLAG_REMOTE
|END_CIRC_REASON_OR_CONN_CLOSED
);
990 while (layer
->next
!= circ
->cpath
) {
991 /* we need to clear out layer->next */
992 victim
= layer
->next
;
993 log_debug(LD_CIRC
, "Killing a layer of the cpath.");
995 for (stream
= circ
->p_streams
; stream
; stream
=stream
->next_stream
) {
996 if (stream
->cpath_layer
== victim
) {
997 log_info(LD_APP
, "Marking stream %d for close because of truncate.",
999 /* no need to send 'end' relay cells,
1000 * because the other side's already dead
1002 connection_mark_unattached_ap(stream
, END_STREAM_REASON_DESTROY
);
1006 layer
->next
= victim
->next
;
1007 circuit_free_cpath_node(victim
);
1010 log_info(LD_CIRC
, "finished");
1015 /** Given a response payload and keys, initialize, then send a created
1019 onionskin_answer(or_circuit_t
*circ
, uint8_t cell_type
, const char *payload
,
1023 crypt_path_t
*tmp_cpath
;
1025 tmp_cpath
= tor_malloc_zero(sizeof(crypt_path_t
));
1026 tmp_cpath
->magic
= CRYPT_PATH_MAGIC
;
1028 memset(&cell
, 0, sizeof(cell_t
));
1029 cell
.command
= cell_type
;
1030 cell
.circ_id
= circ
->p_circ_id
;
1032 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
1034 memcpy(cell
.payload
, payload
,
1035 cell_type
== CELL_CREATED
? ONIONSKIN_REPLY_LEN
: DIGEST_LEN
*2);
1037 log_debug(LD_CIRC
,"init digest forward 0x%.8x, backward 0x%.8x.",
1038 (unsigned int)*(uint32_t*)(keys
),
1039 (unsigned int)*(uint32_t*)(keys
+20));
1040 if (circuit_init_cpath_crypto(tmp_cpath
, keys
, 0)<0) {
1041 log_warn(LD_BUG
,"Circuit initialization failed");
1042 tor_free(tmp_cpath
);
1045 circ
->n_digest
= tmp_cpath
->f_digest
;
1046 circ
->n_crypto
= tmp_cpath
->f_crypto
;
1047 circ
->p_digest
= tmp_cpath
->b_digest
;
1048 circ
->p_crypto
= tmp_cpath
->b_crypto
;
1049 tmp_cpath
->magic
= 0;
1050 tor_free(tmp_cpath
);
1052 if (cell_type
== CELL_CREATED
)
1053 memcpy(circ
->handshake_digest
, cell
.payload
+DH_KEY_LEN
, DIGEST_LEN
);
1055 memcpy(circ
->handshake_digest
, cell
.payload
+DIGEST_LEN
, DIGEST_LEN
);
1057 circ
->is_first_hop
= (cell_type
== CELL_CREATED_FAST
);
1059 append_cell_to_circuit_queue(TO_CIRCUIT(circ
),
1060 circ
->p_conn
, &cell
, CELL_DIRECTION_IN
);
1061 log_debug(LD_CIRC
,"Finished sending 'created' cell.");
1063 if (!is_local_addr(&circ
->p_conn
->_base
.addr
) &&
1064 !connection_or_nonopen_was_started_here(circ
->p_conn
)) {
1065 /* record that we could process create cells from a non-local conn
1066 * that we didn't initiate; presumably this means that create cells
1067 * can reach us too. */
1068 router_orport_found_reachable();
1074 /** Choose a length for a circuit of purpose <b>purpose</b>.
1075 * Default length is 3 + the number of endpoints that would give something
1076 * away. If the routerlist <b>routers</b> doesn't have enough routers
1077 * to handle the desired path length, return as large a path length as
1078 * is feasible, except if it's less than 2, in which case return -1.
1081 new_route_len(uint8_t purpose
, extend_info_t
*exit
,
1082 smartlist_t
*routers
)
1084 int num_acceptable_routers
;
1087 tor_assert(routers
);
1091 purpose
!= CIRCUIT_PURPOSE_TESTING
&&
1092 purpose
!= CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
)
1095 num_acceptable_routers
= count_acceptable_routers(routers
);
1097 log_debug(LD_CIRC
,"Chosen route length %d (%d/%d routers suitable).",
1098 routelen
, num_acceptable_routers
, smartlist_len(routers
));
1100 if (num_acceptable_routers
< 2) {
1102 "Not enough acceptable routers (%d). Discarding this circuit.",
1103 num_acceptable_routers
);
1107 if (num_acceptable_routers
< routelen
) {
1108 log_info(LD_CIRC
,"Not enough routers: cutting routelen from %d to %d.",
1109 routelen
, num_acceptable_routers
);
1110 routelen
= num_acceptable_routers
;
1116 /** Fetch the list of predicted ports, dup it into a smartlist of
1117 * uint16_t's, remove the ones that are already handled by an
1118 * existing circuit, and return it.
1120 static smartlist_t
*
1121 circuit_get_unhandled_ports(time_t now
)
1123 smartlist_t
*source
= rep_hist_get_predicted_ports(now
);
1124 smartlist_t
*dest
= smartlist_create();
1128 for (i
= 0; i
< smartlist_len(source
); ++i
) {
1129 tmp
= tor_malloc(sizeof(uint16_t));
1130 memcpy(tmp
, smartlist_get(source
, i
), sizeof(uint16_t));
1131 smartlist_add(dest
, tmp
);
1134 circuit_remove_handled_ports(dest
);
1138 /** Return 1 if we already have circuits present or on the way for
1139 * all anticipated ports. Return 0 if we should make more.
1141 * If we're returning 0, set need_uptime and need_capacity to
1142 * indicate any requirements that the unhandled ports have.
1145 circuit_all_predicted_ports_handled(time_t now
, int *need_uptime
,
1150 smartlist_t
*sl
= circuit_get_unhandled_ports(now
);
1151 smartlist_t
*LongLivedServices
= get_options()->LongLivedPorts
;
1152 tor_assert(need_uptime
);
1153 tor_assert(need_capacity
);
1154 enough
= (smartlist_len(sl
) == 0);
1155 for (i
= 0; i
< smartlist_len(sl
); ++i
) {
1156 port
= smartlist_get(sl
, i
);
1157 if (smartlist_string_num_isin(LongLivedServices
, *port
))
1165 /** Return 1 if <b>router</b> can handle one or more of the ports in
1166 * <b>needed_ports</b>, else return 0.
1169 router_handles_some_port(routerinfo_t
*router
, smartlist_t
*needed_ports
)
1174 for (i
= 0; i
< smartlist_len(needed_ports
); ++i
) {
1175 addr_policy_result_t r
;
1176 port
= *(uint16_t *)smartlist_get(needed_ports
, i
);
1178 r
= compare_addr_to_addr_policy(0, port
, router
->exit_policy
);
1179 if (r
!= ADDR_POLICY_REJECTED
&& r
!= ADDR_POLICY_PROBABLY_REJECTED
)
1185 /** Return true iff <b>conn</b> needs another general circuit to be
1188 ap_stream_wants_exit_attention(connection_t
*conn
)
1190 if (conn
->type
== CONN_TYPE_AP
&&
1191 conn
->state
== AP_CONN_STATE_CIRCUIT_WAIT
&&
1192 !conn
->marked_for_close
&&
1193 !(TO_EDGE_CONN(conn
)->want_onehop
) && /* ignore one-hop streams */
1194 !(TO_EDGE_CONN(conn
)->use_begindir
) && /* ignore targeted dir fetches */
1195 !(TO_EDGE_CONN(conn
)->chosen_exit_name
) && /* ignore defined streams */
1196 !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn
)) &&
1197 !circuit_stream_is_being_handled(TO_EDGE_CONN(conn
), 0,
1198 MIN_CIRCUITS_HANDLING_STREAM
))
1203 /** Return a pointer to a suitable router to be the exit node for the
1204 * general-purpose circuit we're about to build.
1206 * Look through the connection array, and choose a router that maximizes
1207 * the number of pending streams that can exit from this router.
1209 * Return NULL if we can't find any suitable routers.
1211 static routerinfo_t
*
1212 choose_good_exit_server_general(routerlist_t
*dir
, int need_uptime
,
1217 int n_pending_connections
= 0;
1218 smartlist_t
*connections
;
1219 int best_support
= -1;
1220 int n_best_support
=0;
1221 routerinfo_t
*router
;
1222 or_options_t
*options
= get_options();
1224 connections
= get_connection_array();
1226 /* Count how many connections are waiting for a circuit to be built.
1227 * We use this for log messages now, but in the future we may depend on it.
1229 SMARTLIST_FOREACH(connections
, connection_t
*, conn
,
1231 if (ap_stream_wants_exit_attention(conn
))
1232 ++n_pending_connections
;
1234 // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
1235 // n_pending_connections);
1236 /* Now we count, for each of the routers in the directory, how many
1237 * of the pending connections could possibly exit from that
1238 * router (n_supported[i]). (We can't be sure about cases where we
1239 * don't know the IP address of the pending connection.)
1241 * -1 means "Don't use this router at all."
1243 n_supported
= tor_malloc(sizeof(int)*smartlist_len(dir
->routers
));
1244 for (i
= 0; i
< smartlist_len(dir
->routers
); ++i
) {/* iterate over routers */
1245 router
= smartlist_get(dir
->routers
, i
);
1246 if (router_is_me(router
)) {
1247 n_supported
[i
] = -1;
1248 // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
1249 /* XXX there's probably a reverse predecessor attack here, but
1250 * it's slow. should we take this out? -RD
1254 if (!router
->is_running
|| router
->is_bad_exit
) {
1255 n_supported
[i
] = -1;
1256 continue; /* skip routers that are known to be down or bad exits */
1258 if (router_is_unreliable(router
, need_uptime
, need_capacity
, 0)) {
1259 n_supported
[i
] = -1;
1260 continue; /* skip routers that are not suitable */
1262 if (!(router
->is_valid
|| options
->_AllowInvalid
& ALLOW_INVALID_EXIT
)) {
1263 /* if it's invalid and we don't want it */
1264 n_supported
[i
] = -1;
1265 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
1266 // router->nickname, i);
1267 continue; /* skip invalid routers */
1269 if (options
->ExcludeSingleHopRelays
&& router
->allow_single_hop_exits
) {
1270 n_supported
[i
] = -1;
1273 if (router_exit_policy_rejects_all(router
)) {
1274 n_supported
[i
] = -1;
1275 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
1276 // router->nickname, i);
1277 continue; /* skip routers that reject all */
1280 /* iterate over connections */
1281 SMARTLIST_FOREACH(connections
, connection_t
*, conn
,
1283 if (!ap_stream_wants_exit_attention(conn
))
1284 continue; /* Skip everything but APs in CIRCUIT_WAIT */
1285 if (connection_ap_can_use_exit(TO_EDGE_CONN(conn
), router
)) {
1287 // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
1288 // router->nickname, i, n_supported[i]);
1290 // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
1291 // router->nickname, i);
1293 }); /* End looping over connections. */
1294 if (n_pending_connections
> 0 && n_supported
[i
] == 0) {
1295 /* Leave best_support at -1 if that's where it is, so we can
1296 * distinguish it later. */
1299 if (n_supported
[i
] > best_support
) {
1300 /* If this router is better than previous ones, remember its index
1301 * and goodness, and start counting how many routers are this good. */
1302 best_support
= n_supported
[i
]; n_best_support
=1;
1303 // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
1304 // router->nickname);
1305 } else if (n_supported
[i
] == best_support
) {
1306 /* If this router is _as good_ as the best one, just increment the
1307 * count of equally good routers.*/
1312 "Found %d servers that might support %d/%d pending connections.",
1313 n_best_support
, best_support
>= 0 ? best_support
: 0,
1314 n_pending_connections
);
1316 /* If any routers definitely support any pending connections, choose one
1318 if (best_support
> 0) {
1319 smartlist_t
*supporting
= smartlist_create(), *use
= smartlist_create();
1321 for (i
= 0; i
< smartlist_len(dir
->routers
); i
++)
1322 if (n_supported
[i
] == best_support
)
1323 smartlist_add(supporting
, smartlist_get(dir
->routers
, i
));
1325 routersets_get_disjunction(use
, supporting
, options
->ExitNodes
,
1326 options
->_ExcludeExitNodesUnion
, 1);
1327 if (smartlist_len(use
) == 0 && !options
->StrictExitNodes
) {
1328 routersets_get_disjunction(use
, supporting
, NULL
,
1329 options
->_ExcludeExitNodesUnion
, 1);
1331 router
= routerlist_sl_choose_by_bandwidth(use
, WEIGHT_FOR_EXIT
);
1332 smartlist_free(use
);
1333 smartlist_free(supporting
);
1335 /* Either there are no pending connections, or no routers even seem to
1336 * possibly support any of them. Choose a router at random that satisfies
1337 * at least one predicted exit port. */
1340 smartlist_t
*needed_ports
, *supporting
, *use
;
1342 if (best_support
== -1) {
1343 if (need_uptime
|| need_capacity
) {
1345 "We couldn't find any live%s%s routers; falling back "
1346 "to list of all routers.",
1347 need_capacity
?", fast":"",
1348 need_uptime
?", stable":"");
1349 tor_free(n_supported
);
1350 return choose_good_exit_server_general(dir
, 0, 0);
1352 log_notice(LD_CIRC
, "All routers are down or won't exit -- choosing a "
1353 "doomed exit at random.");
1355 supporting
= smartlist_create();
1356 use
= smartlist_create();
1357 needed_ports
= circuit_get_unhandled_ports(time(NULL
));
1358 for (try = 0; try < 2; try++) {
1359 /* try once to pick only from routers that satisfy a needed port,
1360 * then if there are none, pick from any that support exiting. */
1361 for (i
= 0; i
< smartlist_len(dir
->routers
); i
++) {
1362 router
= smartlist_get(dir
->routers
, i
);
1363 if (n_supported
[i
] != -1 &&
1364 (try || router_handles_some_port(router
, needed_ports
))) {
1365 // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
1366 // try, router->nickname);
1367 smartlist_add(supporting
, router
);
1371 routersets_get_disjunction(use
, supporting
, options
->ExitNodes
,
1372 options
->_ExcludeExitNodesUnion
, 1);
1373 if (smartlist_len(use
) == 0 && !options
->StrictExitNodes
) {
1374 routersets_get_disjunction(use
, supporting
, NULL
,
1375 options
->_ExcludeExitNodesUnion
, 1);
1377 /* XXX sometimes the above results in null, when the requested
1378 * exit node is down. we should pick it anyway. */
1379 router
= routerlist_sl_choose_by_bandwidth(use
, WEIGHT_FOR_EXIT
);
1382 smartlist_clear(supporting
);
1383 smartlist_clear(use
);
1385 SMARTLIST_FOREACH(needed_ports
, uint16_t *, cp
, tor_free(cp
));
1386 smartlist_free(needed_ports
);
1387 smartlist_free(use
);
1388 smartlist_free(supporting
);
1391 tor_free(n_supported
);
1393 log_info(LD_CIRC
, "Chose exit server '%s'", router
->nickname
);
1396 if (options
->StrictExitNodes
) {
1398 "No specified exit routers seem to be running, and "
1399 "StrictExitNodes is set: can't choose an exit.");
1404 /** Return a pointer to a suitable router to be the exit node for the
1405 * circuit of purpose <b>purpose</b> that we're about to build (or NULL
1406 * if no router is suitable).
1408 * For general-purpose circuits, pass it off to
1409 * choose_good_exit_server_general()
1411 * For client-side rendezvous circuits, choose a random node, weighted
1412 * toward the preferences in 'options'.
1414 static routerinfo_t
*
1415 choose_good_exit_server(uint8_t purpose
, routerlist_t
*dir
,
1416 int need_uptime
, int need_capacity
, int is_internal
)
1418 or_options_t
*options
= get_options();
1419 router_crn_flags_t flags
= 0;
1421 flags
|= CRN_NEED_UPTIME
;
1423 flags
|= CRN_NEED_CAPACITY
;
1426 case CIRCUIT_PURPOSE_C_GENERAL
:
1427 if (options
->_AllowInvalid
& ALLOW_INVALID_MIDDLE
)
1428 flags
|= CRN_ALLOW_INVALID
;
1429 if (is_internal
) /* pick it like a middle hop */
1430 return router_choose_random_node(NULL
, NULL
,
1431 options
->ExcludeNodes
, flags
);
1433 return choose_good_exit_server_general(dir
,need_uptime
,need_capacity
);
1434 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
1435 if (options
->_AllowInvalid
& ALLOW_INVALID_RENDEZVOUS
)
1436 flags
|= CRN_ALLOW_INVALID
;
1437 return router_choose_random_node(NULL
, NULL
,
1438 options
->ExcludeNodes
, flags
);
1440 log_warn(LD_BUG
,"Unhandled purpose %d", purpose
);
1441 tor_fragile_assert();
1445 /** Log a warning if the user specified an exit for the circuit that
1446 * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
1448 warn_if_last_router_excluded(origin_circuit_t
*circ
, const extend_info_t
*exit
)
1450 or_options_t
*options
= get_options();
1451 routerset_t
*rs
= options
->ExcludeNodes
;
1452 const char *description
;
1453 int domain
= LD_CIRC
;
1454 uint8_t purpose
= circ
->_base
.purpose
;
1456 if (circ
->build_state
->onehop_tunnel
)
1462 case CIRCUIT_PURPOSE_OR
:
1463 case CIRCUIT_PURPOSE_INTRO_POINT
:
1464 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
1465 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
1466 log_warn(LD_BUG
, "Called on non-origin circuit (purpose %d)",
1469 case CIRCUIT_PURPOSE_C_GENERAL
:
1470 if (circ
->build_state
->is_internal
)
1472 description
= "Requested exit node";
1473 rs
= options
->_ExcludeExitNodesUnion
;
1475 case CIRCUIT_PURPOSE_C_INTRODUCING
:
1476 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
1477 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
1478 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
1479 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
1480 case CIRCUIT_PURPOSE_S_REND_JOINED
:
1481 case CIRCUIT_PURPOSE_TESTING
:
1483 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
1484 case CIRCUIT_PURPOSE_C_REND_READY
:
1485 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
1486 case CIRCUIT_PURPOSE_C_REND_JOINED
:
1487 description
= "Chosen rendezvous point";
1490 case CIRCUIT_PURPOSE_CONTROLLER
:
1491 rs
= options
->_ExcludeExitNodesUnion
;
1492 description
= "Controller-selected circuit target";
1496 if (routerset_contains_extendinfo(rs
, exit
)) {
1497 log_fn(LOG_WARN
, domain
, "%s '%s' is in ExcludeNodes%s. Using anyway "
1498 "(circuit purpose %d).",
1499 description
,exit
->nickname
,
1500 rs
==options
->ExcludeNodes
?"":" or ExcludeExitNodes",
1502 circuit_log_path(LOG_WARN
, domain
, circ
);
1508 /** Decide a suitable length for circ's cpath, and pick an exit
1509 * router (or use <b>exit</b> if provided). Store these in the
1510 * cpath. Return 0 if ok, -1 if circuit should be closed. */
1512 onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
1514 cpath_build_state_t
*state
= circ
->build_state
;
1515 routerlist_t
*rl
= router_get_routerlist();
1517 if (state
->onehop_tunnel
) {
1518 log_debug(LD_CIRC
, "Launching a one-hop circuit for dir tunnel.");
1519 state
->desired_path_len
= 1;
1521 int r
= new_route_len(circ
->_base
.purpose
, exit
, rl
->routers
);
1522 if (r
< 1) /* must be at least 1 */
1524 state
->desired_path_len
= r
;
1527 if (exit
) { /* the circuit-builder pre-requested one */
1528 warn_if_last_router_excluded(circ
, exit
);
1529 log_info(LD_CIRC
,"Using requested exit node '%s'", exit
->nickname
);
1530 exit
= extend_info_dup(exit
);
1531 } else { /* we have to decide one */
1532 routerinfo_t
*router
=
1533 choose_good_exit_server(circ
->_base
.purpose
, rl
, state
->need_uptime
,
1534 state
->need_capacity
, state
->is_internal
);
1536 log_warn(LD_CIRC
,"failed to choose an exit server");
1539 exit
= extend_info_from_router(router
);
1541 state
->chosen_exit
= exit
;
1545 /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
1546 * hop to the cpath reflecting this. Don't send the next extend cell --
1547 * the caller will do this if it wants to.
1550 circuit_append_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
1552 cpath_build_state_t
*state
;
1556 state
= circ
->build_state
;
1558 if (state
->chosen_exit
)
1559 extend_info_free(state
->chosen_exit
);
1560 state
->chosen_exit
= extend_info_dup(exit
);
1562 ++circ
->build_state
->desired_path_len
;
1563 onion_append_hop(&circ
->cpath
, exit
);
1567 /** Take an open <b>circ</b>, and add a new hop at the end, based on
1568 * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
1569 * send the next extend cell to begin connecting to that hop.
1572 circuit_extend_to_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
1575 warn_if_last_router_excluded(circ
, exit
);
1576 circuit_append_new_exit(circ
, exit
);
1577 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
1578 if ((err_reason
= circuit_send_next_onion_skin(circ
))<0) {
1579 log_warn(LD_CIRC
, "Couldn't extend circuit to new point '%s'.",
1581 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
1587 /** Return the number of routers in <b>routers</b> that are currently up
1588 * and available for building circuits through.
1591 count_acceptable_routers(smartlist_t
*routers
)
1597 n
= smartlist_len(routers
);
1599 r
= smartlist_get(routers
, i
);
1600 // log_debug(LD_CIRC,
1601 // "Contemplating whether router %d (%s) is a new option.",
1603 if (r
->is_running
== 0) {
1604 // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
1607 if (r
->is_valid
== 0) {
1608 // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
1610 /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
1611 * allows this node in some places, then we're getting an inaccurate
1612 * count. For now, be conservative and don't count it. But later we
1613 * should try to be smarter. */
1616 // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
1618 ; /* C requires an explicit statement after the label */
1624 /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
1625 * This function is used to extend cpath by another hop.
1628 onion_append_to_cpath(crypt_path_t
**head_ptr
, crypt_path_t
*new_hop
)
1631 new_hop
->next
= (*head_ptr
);
1632 new_hop
->prev
= (*head_ptr
)->prev
;
1633 (*head_ptr
)->prev
->next
= new_hop
;
1634 (*head_ptr
)->prev
= new_hop
;
1636 *head_ptr
= new_hop
;
1637 new_hop
->prev
= new_hop
->next
= new_hop
;
1641 /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
1642 * and <b>state</b> and the cpath <b>head</b> (currently populated only
1643 * to length <b>cur_len</b> to decide a suitable middle hop for a
1644 * circuit. In particular, make sure we don't pick the exit node or its
1645 * family, and make sure we don't duplicate any previous nodes or their
1647 static routerinfo_t
*
1648 choose_good_middle_server(uint8_t purpose
,
1649 cpath_build_state_t
*state
,
1654 routerinfo_t
*r
, *choice
;
1655 crypt_path_t
*cpath
;
1656 smartlist_t
*excluded
;
1657 or_options_t
*options
= get_options();
1658 router_crn_flags_t flags
= 0;
1659 tor_assert(_CIRCUIT_PURPOSE_MIN
<= purpose
&&
1660 purpose
<= _CIRCUIT_PURPOSE_MAX
);
1662 log_debug(LD_CIRC
, "Contemplating intermediate hop: random choice.");
1663 excluded
= smartlist_create();
1664 if ((r
= build_state_get_exit_router(state
))) {
1665 smartlist_add(excluded
, r
);
1666 routerlist_add_family(excluded
, r
);
1668 for (i
= 0, cpath
= head
; i
< cur_len
; ++i
, cpath
=cpath
->next
) {
1669 if ((r
= router_get_by_digest(cpath
->extend_info
->identity_digest
))) {
1670 smartlist_add(excluded
, r
);
1671 routerlist_add_family(excluded
, r
);
1675 if (state
->need_uptime
)
1676 flags
|= CRN_NEED_UPTIME
;
1677 if (state
->need_capacity
)
1678 flags
|= CRN_NEED_CAPACITY
;
1679 if (options
->_AllowInvalid
& ALLOW_INVALID_MIDDLE
)
1680 flags
|= CRN_ALLOW_INVALID
;
1681 choice
= router_choose_random_node(NULL
,
1682 excluded
, options
->ExcludeNodes
, flags
);
1683 smartlist_free(excluded
);
1687 /** Pick a good entry server for the circuit to be built according to
1688 * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
1689 * router (if we're an OR), and respect firewall settings; if we're
1690 * configured to use entry guards, return one.
1692 * If <b>state</b> is NULL, we're choosing a router to serve as an entry
1693 * guard, not for any particular circuit.
1695 static routerinfo_t
*
1696 choose_good_entry_server(uint8_t purpose
, cpath_build_state_t
*state
)
1698 routerinfo_t
*r
, *choice
;
1699 smartlist_t
*excluded
;
1700 or_options_t
*options
= get_options();
1701 router_crn_flags_t flags
= CRN_NEED_GUARD
;
1703 if (state
&& options
->UseEntryGuards
&&
1704 (purpose
!= CIRCUIT_PURPOSE_TESTING
|| options
->BridgeRelay
)) {
1705 return choose_random_entry(state
);
1708 excluded
= smartlist_create();
1710 if (state
&& (r
= build_state_get_exit_router(state
))) {
1711 smartlist_add(excluded
, r
);
1712 routerlist_add_family(excluded
, r
);
1714 if (firewall_is_fascist_or()) {
1715 /*XXXX This could slow things down a lot; use a smarter implementation */
1716 /* exclude all ORs that listen on the wrong port, if anybody notices. */
1717 routerlist_t
*rl
= router_get_routerlist();
1720 for (i
=0; i
< smartlist_len(rl
->routers
); i
++) {
1721 r
= smartlist_get(rl
->routers
, i
);
1722 if (!fascist_firewall_allows_or(r
))
1723 smartlist_add(excluded
, r
);
1726 /* and exclude current entry guards, if applicable */
1727 if (options
->UseEntryGuards
&& entry_guards
) {
1728 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
1730 if ((r
= router_get_by_digest(entry
->identity
))) {
1731 smartlist_add(excluded
, r
);
1732 routerlist_add_family(excluded
, r
);
1738 if (state
->need_uptime
)
1739 flags
|= CRN_NEED_UPTIME
;
1740 if (state
->need_capacity
)
1741 flags
|= CRN_NEED_CAPACITY
;
1743 if (options
->_AllowInvalid
& ALLOW_INVALID_ENTRY
)
1744 flags
|= CRN_ALLOW_INVALID
;
1746 choice
= router_choose_random_node(
1749 options
->ExcludeNodes
,
1751 smartlist_free(excluded
);
1755 /** Return the first non-open hop in cpath, or return NULL if all
1757 static crypt_path_t
*
1758 onion_next_hop_in_cpath(crypt_path_t
*cpath
)
1760 crypt_path_t
*hop
= cpath
;
1762 if (hop
->state
!= CPATH_STATE_OPEN
)
1765 } while (hop
!= cpath
);
1769 /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
1770 * based on <b>state</b>. Append the hop info to head_ptr.
1773 onion_extend_cpath(origin_circuit_t
*circ
)
1775 uint8_t purpose
= circ
->_base
.purpose
;
1776 cpath_build_state_t
*state
= circ
->build_state
;
1777 int cur_len
= circuit_get_cpath_len(circ
);
1778 extend_info_t
*info
= NULL
;
1780 if (cur_len
>= state
->desired_path_len
) {
1781 log_debug(LD_CIRC
, "Path is complete: %d steps long",
1782 state
->desired_path_len
);
1786 log_debug(LD_CIRC
, "Path is %d long; we want %d", cur_len
,
1787 state
->desired_path_len
);
1789 if (cur_len
== state
->desired_path_len
- 1) { /* Picking last node */
1790 info
= extend_info_dup(state
->chosen_exit
);
1791 } else if (cur_len
== 0) { /* picking first node */
1792 routerinfo_t
*r
= choose_good_entry_server(purpose
, state
);
1794 info
= extend_info_from_router(r
);
1797 choose_good_middle_server(purpose
, state
, circ
->cpath
, cur_len
);
1799 info
= extend_info_from_router(r
);
1803 log_warn(LD_CIRC
,"Failed to find node for hop %d of our path. Discarding "
1804 "this circuit.", cur_len
);
1808 log_debug(LD_CIRC
,"Chose router %s for hop %d (exit is %s)",
1809 info
->nickname
, cur_len
+1, build_state_get_exit_nickname(state
));
1811 onion_append_hop(&circ
->cpath
, info
);
1812 extend_info_free(info
);
1816 /** Create a new hop, annotate it with information about its
1817 * corresponding router <b>choice</b>, and append it to the
1818 * end of the cpath <b>head_ptr</b>. */
1820 onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
)
1822 crypt_path_t
*hop
= tor_malloc_zero(sizeof(crypt_path_t
));
1824 /* link hop into the cpath, at the end. */
1825 onion_append_to_cpath(head_ptr
, hop
);
1827 hop
->magic
= CRYPT_PATH_MAGIC
;
1828 hop
->state
= CPATH_STATE_CLOSED
;
1830 hop
->extend_info
= extend_info_dup(choice
);
1832 hop
->package_window
= circuit_initial_package_window();
1833 hop
->deliver_window
= CIRCWINDOW_START
;
1838 /** Allocate a new extend_info object based on the various arguments. */
1840 extend_info_alloc(const char *nickname
, const char *digest
,
1841 crypto_pk_env_t
*onion_key
,
1842 const tor_addr_t
*addr
, uint16_t port
)
1844 extend_info_t
*info
= tor_malloc_zero(sizeof(extend_info_t
));
1845 memcpy(info
->identity_digest
, digest
, DIGEST_LEN
);
1847 strlcpy(info
->nickname
, nickname
, sizeof(info
->nickname
));
1849 info
->onion_key
= crypto_pk_dup_key(onion_key
);
1850 tor_addr_copy(&info
->addr
, addr
);
1855 /** Allocate and return a new extend_info_t that can be used to build a
1856 * circuit to or through the router <b>r</b>. */
1858 extend_info_from_router(routerinfo_t
*r
)
1862 tor_addr_from_ipv4h(&addr
, r
->addr
);
1863 return extend_info_alloc(r
->nickname
, r
->cache_info
.identity_digest
,
1864 r
->onion_pkey
, &addr
, r
->or_port
);
1867 /** Release storage held by an extend_info_t struct. */
1869 extend_info_free(extend_info_t
*info
)
1872 if (info
->onion_key
)
1873 crypto_free_pk_env(info
->onion_key
);
1877 /** Allocate and return a new extend_info_t with the same contents as
1880 extend_info_dup(extend_info_t
*info
)
1882 extend_info_t
*newinfo
;
1884 newinfo
= tor_malloc(sizeof(extend_info_t
));
1885 memcpy(newinfo
, info
, sizeof(extend_info_t
));
1886 if (info
->onion_key
)
1887 newinfo
->onion_key
= crypto_pk_dup_key(info
->onion_key
);
1889 newinfo
->onion_key
= NULL
;
1893 /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
1894 * If there is no chosen exit, or if we don't know the routerinfo_t for
1895 * the chosen exit, return NULL.
1898 build_state_get_exit_router(cpath_build_state_t
*state
)
1900 if (!state
|| !state
->chosen_exit
)
1902 return router_get_by_digest(state
->chosen_exit
->identity_digest
);
1905 /** Return the nickname for the chosen exit router in <b>state</b>. If
1906 * there is no chosen exit, or if we don't know the routerinfo_t for the
1907 * chosen exit, return NULL.
1910 build_state_get_exit_nickname(cpath_build_state_t
*state
)
1912 if (!state
|| !state
->chosen_exit
)
1914 return state
->chosen_exit
->nickname
;
1917 /** Check whether the entry guard <b>e</b> is usable, given the directory
1918 * authorities' opinion about the router (stored in <b>ri</b>) and the user's
1919 * configuration (in <b>options</b>). Set <b>e</b>->bad_since
1920 * accordingly. Return true iff the entry guard's status changes.
1922 * If it's not usable, set *<b>reason</b> to a static string explaining why.
1924 /*XXXX take a routerstatus, not a routerinfo. */
1926 entry_guard_set_status(entry_guard_t
*e
, routerinfo_t
*ri
,
1927 time_t now
, or_options_t
*options
, const char **reason
)
1929 char buf
[HEX_DIGEST_LEN
+1];
1932 tor_assert(options
);
1936 /* Do we want to mark this guard as bad? */
1938 *reason
= "unlisted";
1939 else if (!ri
->is_running
)
1941 else if (options
->UseBridges
&& ri
->purpose
!= ROUTER_PURPOSE_BRIDGE
)
1942 *reason
= "not a bridge";
1943 else if (!options
->UseBridges
&& !ri
->is_possible_guard
&&
1944 !routerset_contains_router(options
->EntryNodes
,ri
))
1945 *reason
= "not recommended as a guard";
1946 else if (routerset_contains_router(options
->ExcludeNodes
, ri
))
1947 *reason
= "excluded";
1949 if (*reason
&& ! e
->bad_since
) {
1950 /* Router is newly bad. */
1951 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
1952 log_info(LD_CIRC
, "Entry guard %s (%s) is %s: marking as unusable.",
1953 e
->nickname
, buf
, *reason
);
1956 control_event_guard(e
->nickname
, e
->identity
, "BAD");
1958 } else if (!*reason
&& e
->bad_since
) {
1959 /* There's nothing wrong with the router any more. */
1960 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
1961 log_info(LD_CIRC
, "Entry guard %s (%s) is no longer unusable: "
1962 "marking as ok.", e
->nickname
, buf
);
1965 control_event_guard(e
->nickname
, e
->identity
, "GOOD");
1971 /** Return true iff enough time has passed since we last tried to connect
1972 * to the unreachable guard <b>e</b> that we're willing to try again. */
1974 entry_is_time_to_retry(entry_guard_t
*e
, time_t now
)
1977 if (e
->last_attempted
< e
->unreachable_since
)
1979 diff
= now
- e
->unreachable_since
;
1981 return now
> (e
->last_attempted
+ 60*60);
1982 else if (diff
< 3*24*60*60)
1983 return now
> (e
->last_attempted
+ 4*60*60);
1984 else if (diff
< 7*24*60*60)
1985 return now
> (e
->last_attempted
+ 18*60*60);
1987 return now
> (e
->last_attempted
+ 36*60*60);
1990 /** Return the router corresponding to <b>e</b>, if <b>e</b> is
1991 * working well enough that we are willing to use it as an entry
1992 * right now. (Else return NULL.) In particular, it must be
1993 * - Listed as either up or never yet contacted;
1994 * - Present in the routerlist;
1995 * - Listed as 'stable' or 'fast' by the current dirserver consensus,
1996 * if demanded by <b>need_uptime</b> or <b>need_capacity</b>;
1997 * (This check is currently redundant with the Guard flag, but in
1998 * the future that might change. Best to leave it in for now.)
1999 * - Allowed by our current ReachableORAddresses config option; and
2000 * - Currently thought to be reachable by us (unless assume_reachable
2003 static INLINE routerinfo_t
*
2004 entry_is_live(entry_guard_t
*e
, int need_uptime
, int need_capacity
,
2005 int assume_reachable
)
2010 /* no good if it's unreachable, unless assume_unreachable or can_retry. */
2011 if (!assume_reachable
&& !e
->can_retry
&&
2012 e
->unreachable_since
&& !entry_is_time_to_retry(e
, time(NULL
)))
2014 r
= router_get_by_digest(e
->identity
);
2017 if (get_options()->UseBridges
&& r
->purpose
!= ROUTER_PURPOSE_BRIDGE
)
2019 if (!get_options()->UseBridges
&& r
->purpose
!= ROUTER_PURPOSE_GENERAL
)
2021 if (router_is_unreliable(r
, need_uptime
, need_capacity
, 0))
2023 if (!fascist_firewall_allows_or(r
))
2028 /** Return the number of entry guards that we think are usable. */
2030 num_live_entry_guards(void)
2035 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
2037 if (entry_is_live(entry
, 0, 1, 0))
2043 /** If <b>digest</b> matches the identity of any node in the
2044 * entry_guards list, return that node. Else return NULL. */
2045 static INLINE entry_guard_t
*
2046 is_an_entry_guard(const char *digest
)
2048 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
2049 if (!memcmp(digest
, entry
->identity
, DIGEST_LEN
))
2055 /** Dump a description of our list of entry guards to the log at level
2056 * <b>severity</b>. */
2058 log_entry_guards(int severity
)
2060 smartlist_t
*elements
= smartlist_create();
2064 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2066 tor_snprintf(buf
, sizeof(buf
), "%s (%s%s)",
2068 entry_is_live(e
, 0, 1, 0) ? "up " : "down ",
2069 e
->made_contact
? "made-contact" : "never-contacted");
2070 smartlist_add(elements
, tor_strdup(buf
));
2073 s
= smartlist_join_strings(elements
, ",", 0, NULL
);
2074 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
2075 smartlist_free(elements
);
2076 log_fn(severity
,LD_CIRC
,"%s",s
);
2080 /** Called when one or more guards that we would previously have used for some
2081 * purpose are no longer in use because a higher-priority guard has become
2084 control_event_guard_deferred(void)
2086 /* XXXX We don't actually have a good way to figure out _how many_ entries
2087 * are live for some purpose. We need an entry_is_even_slightly_live()
2088 * function for this to work right. NumEntryGuards isn't reliable: if we
2089 * need guards with weird properties, we can have more than that number
2094 or_options_t
*options
= get_options();
2097 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
2099 if (entry_is_live(entry
, 0, 1, 0)) {
2100 if (n
++ == options
->NumEntryGuards
) {
2101 control_event_guard(entry
->nickname
, entry
->identity
, "DEFERRED");
2109 /** Add a new (preferably stable and fast) router to our
2110 * entry_guards list. Return a pointer to the router if we succeed,
2111 * or NULL if we can't find any more suitable entries.
2113 * If <b>chosen</b> is defined, use that one, and if it's not
2114 * already in our entry_guards list, put it at the *beginning*.
2115 * Else, put the one we pick at the end of the list. */
2116 static routerinfo_t
*
2117 add_an_entry_guard(routerinfo_t
*chosen
, int reset_status
)
2119 routerinfo_t
*router
;
2120 entry_guard_t
*entry
;
2124 entry
= is_an_entry_guard(router
->cache_info
.identity_digest
);
2127 entry
->bad_since
= 0;
2128 entry
->can_retry
= 1;
2133 router
= choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL
, NULL
);
2137 entry
= tor_malloc_zero(sizeof(entry_guard_t
));
2138 log_info(LD_CIRC
, "Chose '%s' as new entry guard.", router
->nickname
);
2139 strlcpy(entry
->nickname
, router
->nickname
, sizeof(entry
->nickname
));
2140 memcpy(entry
->identity
, router
->cache_info
.identity_digest
, DIGEST_LEN
);
2141 /* Choose expiry time smudged over the past month. The goal here
2142 * is to a) spread out when Tor clients rotate their guards, so they
2143 * don't all select them on the same day, and b) avoid leaving a
2144 * precise timestamp in the state file about when we first picked
2145 * this guard. For details, see the Jan 2010 or-dev thread. */
2146 entry
->chosen_on_date
= time(NULL
) - crypto_rand_int(3600*24*30);
2147 entry
->chosen_by_version
= tor_strdup(VERSION
);
2148 if (chosen
) /* prepend */
2149 smartlist_insert(entry_guards
, 0, entry
);
2151 smartlist_add(entry_guards
, entry
);
2152 control_event_guard(entry
->nickname
, entry
->identity
, "NEW");
2153 control_event_guard_deferred();
2154 log_entry_guards(LOG_INFO
);
2158 /** If the use of entry guards is configured, choose more entry guards
2159 * until we have enough in the list. */
2161 pick_entry_guards(void)
2163 or_options_t
*options
= get_options();
2166 tor_assert(entry_guards
);
2168 while (num_live_entry_guards() < options
->NumEntryGuards
) {
2169 if (!add_an_entry_guard(NULL
, 0))
2174 entry_guards_changed();
2177 /** How long (in seconds) do we allow an entry guard to be nonfunctional,
2178 * unlisted, excluded, or otherwise nonusable before we give up on it? */
2179 #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
2181 /** Release all storage held by <b>e</b>. */
2183 entry_guard_free(entry_guard_t
*e
)
2186 tor_free(e
->chosen_by_version
);
2190 /** Remove any entry guard which was selected by an unknown version of Tor,
2191 * or which was selected by a version of Tor that's known to select
2192 * entry guards badly. */
2194 remove_obsolete_entry_guards(void)
2197 time_t now
= time(NULL
);
2199 for (i
= 0; i
< smartlist_len(entry_guards
); ++i
) {
2200 entry_guard_t
*entry
= smartlist_get(entry_guards
, i
);
2201 const char *ver
= entry
->chosen_by_version
;
2202 const char *msg
= NULL
;
2204 int version_is_bad
= 0, date_is_bad
= 0;
2206 msg
= "does not say what version of Tor it was selected by";
2208 } else if (tor_version_parse(ver
, &v
)) {
2209 msg
= "does not seem to be from any recognized version of Tor";
2212 size_t len
= strlen(ver
)+5;
2213 char *tor_ver
= tor_malloc(len
);
2214 tor_snprintf(tor_ver
, len
, "Tor %s", ver
);
2215 if ((tor_version_as_new_as(tor_ver
, "0.1.0.10-alpha") &&
2216 !tor_version_as_new_as(tor_ver
, "0.1.2.16-dev")) ||
2217 (tor_version_as_new_as(tor_ver
, "0.2.0.0-alpha") &&
2218 !tor_version_as_new_as(tor_ver
, "0.2.0.6-alpha")) ||
2219 /* above are bug 440; below are bug 1217 */
2220 (tor_version_as_new_as(tor_ver
, "0.2.1.3-alpha") &&
2221 !tor_version_as_new_as(tor_ver
, "0.2.1.23")) ||
2222 (tor_version_as_new_as(tor_ver
, "0.2.2.0-alpha") &&
2223 !tor_version_as_new_as(tor_ver
, "0.2.2.7-alpha"))) {
2224 msg
= "was selected without regard for guard bandwidth";
2229 if (!version_is_bad
&& entry
->chosen_on_date
+ 3600*24*60 < now
) {
2230 /* It's been 2 months since the date listed in our state file. */
2231 msg
= "was selected several months ago";
2235 if (version_is_bad
|| date_is_bad
) { /* we need to drop it */
2236 char dbuf
[HEX_DIGEST_LEN
+1];
2238 base16_encode(dbuf
, sizeof(dbuf
), entry
->identity
, DIGEST_LEN
);
2239 log_fn(version_is_bad
? LOG_NOTICE
: LOG_INFO
, LD_CIRC
,
2240 "Entry guard '%s' (%s) %s. (Version=%s.) Replacing it.",
2241 entry
->nickname
, dbuf
, msg
, ver
?escaped(ver
):"none");
2242 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
2243 entry_guard_free(entry
);
2244 smartlist_del_keeporder(entry_guards
, i
--);
2245 log_entry_guards(LOG_INFO
);
2250 return changed
? 1 : 0;
2253 /** Remove all entry guards that have been down or unlisted for so
2254 * long that we don't think they'll come up again. Return 1 if we
2255 * removed any, or 0 if we did nothing. */
2257 remove_dead_entry_guards(void)
2259 char dbuf
[HEX_DIGEST_LEN
+1];
2260 char tbuf
[ISO_TIME_LEN
+1];
2261 time_t now
= time(NULL
);
2265 for (i
= 0; i
< smartlist_len(entry_guards
); ) {
2266 entry_guard_t
*entry
= smartlist_get(entry_guards
, i
);
2267 if (entry
->bad_since
&&
2268 entry
->bad_since
+ ENTRY_GUARD_REMOVE_AFTER
< now
) {
2270 base16_encode(dbuf
, sizeof(dbuf
), entry
->identity
, DIGEST_LEN
);
2271 format_local_iso_time(tbuf
, entry
->bad_since
);
2272 log_info(LD_CIRC
, "Entry guard '%s' (%s) has been down or unlisted "
2273 "since %s local time; removing.",
2274 entry
->nickname
, dbuf
, tbuf
);
2275 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
2276 entry_guard_free(entry
);
2277 smartlist_del_keeporder(entry_guards
, i
);
2278 log_entry_guards(LOG_INFO
);
2283 return changed
? 1 : 0;
2286 /** A new directory or router-status has arrived; update the down/listed
2287 * status of the entry guards.
2289 * An entry is 'down' if the directory lists it as nonrunning.
2290 * An entry is 'unlisted' if the directory doesn't include it.
2292 * Don't call this on startup; only on a fresh download. Otherwise we'll
2293 * think that things are unlisted.
2296 entry_guards_compute_status(void)
2300 int severity
= LOG_DEBUG
;
2301 or_options_t
*options
;
2302 digestmap_t
*reasons
;
2306 options
= get_options();
2310 reasons
= digestmap_new();
2311 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, entry
)
2313 routerinfo_t
*r
= router_get_by_digest(entry
->identity
);
2314 const char *reason
= NULL
;
2315 if (entry_guard_set_status(entry
, r
, now
, options
, &reason
))
2318 if (entry
->bad_since
)
2321 digestmap_set(reasons
, entry
->identity
, (char*)reason
);
2323 SMARTLIST_FOREACH_END(entry
);
2325 if (remove_dead_entry_guards())
2328 severity
= changed
? LOG_DEBUG
: LOG_INFO
;
2331 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, entry
) {
2332 const char *reason
= digestmap_get(reasons
, entry
->identity
);
2333 log_info(LD_CIRC
, "Summary: Entry '%s' is %s, %s%s%s, and %s.",
2335 entry
->unreachable_since
? "unreachable" : "reachable",
2336 entry
->bad_since
? "unusable" : "usable",
2338 reason
? reason
: "",
2339 entry_is_live(entry
, 0, 1, 0) ? "live" : "not live");
2340 } SMARTLIST_FOREACH_END(entry
);
2341 log_info(LD_CIRC
, " (%d/%d entry guards are usable/new)",
2342 num_live_entry_guards(), smartlist_len(entry_guards
));
2343 log_entry_guards(LOG_INFO
);
2344 entry_guards_changed();
2347 digestmap_free(reasons
, NULL
);
2350 /** Called when a connection to an OR with the identity digest <b>digest</b>
2351 * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0).
2352 * If the OR is an entry, change that entry's up/down status.
2353 * Return 0 normally, or -1 if we want to tear down the new connection.
2355 * If <b>mark_relay_status</b>, also call router_set_status() on this
2358 * XXX022 change succeeded and mark_relay_status into 'int flags'.
2361 entry_guard_register_connect_status(const char *digest
, int succeeded
,
2362 int mark_relay_status
, time_t now
)
2365 int refuse_conn
= 0;
2366 int first_contact
= 0;
2367 entry_guard_t
*entry
= NULL
;
2369 char buf
[HEX_DIGEST_LEN
+1];
2374 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2376 if (!memcmp(e
->identity
, digest
, DIGEST_LEN
)) {
2386 base16_encode(buf
, sizeof(buf
), entry
->identity
, DIGEST_LEN
);
2389 if (entry
->unreachable_since
) {
2390 log_info(LD_CIRC
, "Entry guard '%s' (%s) is now reachable again. Good.",
2391 entry
->nickname
, buf
);
2392 entry
->can_retry
= 0;
2393 entry
->unreachable_since
= 0;
2394 entry
->last_attempted
= now
;
2395 control_event_guard(entry
->nickname
, entry
->identity
, "UP");
2398 if (!entry
->made_contact
) {
2399 entry
->made_contact
= 1;
2400 first_contact
= changed
= 1;
2402 } else { /* ! succeeded */
2403 if (!entry
->made_contact
) {
2404 /* We've never connected to this one. */
2406 "Connection to never-contacted entry guard '%s' (%s) failed. "
2407 "Removing from the list. %d/%d entry guards usable/new.",
2408 entry
->nickname
, buf
,
2409 num_live_entry_guards()-1, smartlist_len(entry_guards
)-1);
2410 entry_guard_free(entry
);
2411 smartlist_del_keeporder(entry_guards
, idx
);
2412 log_entry_guards(LOG_INFO
);
2414 } else if (!entry
->unreachable_since
) {
2415 log_info(LD_CIRC
, "Unable to connect to entry guard '%s' (%s). "
2416 "Marking as unreachable.", entry
->nickname
, buf
);
2417 entry
->unreachable_since
= entry
->last_attempted
= now
;
2418 control_event_guard(entry
->nickname
, entry
->identity
, "DOWN");
2420 entry
->can_retry
= 0; /* We gave it an early chance; no good. */
2422 char tbuf
[ISO_TIME_LEN
+1];
2423 format_iso_time(tbuf
, entry
->unreachable_since
);
2424 log_debug(LD_CIRC
, "Failed to connect to unreachable entry guard "
2425 "'%s' (%s). It has been unreachable since %s.",
2426 entry
->nickname
, buf
, tbuf
);
2427 entry
->last_attempted
= now
;
2428 entry
->can_retry
= 0; /* We gave it an early chance; no good. */
2432 /* if the caller asked us to, also update the is_running flags for this
2434 if (mark_relay_status
)
2435 router_set_status(digest
, succeeded
);
2437 if (first_contact
) {
2438 /* We've just added a new long-term entry guard. Perhaps the network just
2439 * came back? We should give our earlier entries another try too,
2440 * and close this connection so we don't use it before we've given
2441 * the others a shot. */
2442 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, {
2445 if (e
->made_contact
) {
2446 routerinfo_t
*r
= entry_is_live(e
, 0, 1, 1);
2447 if (r
&& e
->unreachable_since
) {
2455 "Connected to new entry guard '%s' (%s). Marking earlier "
2456 "entry guards up. %d/%d entry guards usable/new.",
2457 entry
->nickname
, buf
,
2458 num_live_entry_guards(), smartlist_len(entry_guards
));
2459 log_entry_guards(LOG_INFO
);
2465 entry_guards_changed();
2466 return refuse_conn
? -1 : 0;
2469 /** When we try to choose an entry guard, should we parse and add
2470 * config's EntryNodes first? */
2471 static int should_add_entry_nodes
= 0;
2473 /** Called when the value of EntryNodes changes in our configuration. */
2475 entry_nodes_should_be_added(void)
2477 log_info(LD_CIRC
, "New EntryNodes config option detected. Will use.");
2478 should_add_entry_nodes
= 1;
2481 /** Add all nodes in EntryNodes that aren't currently guard nodes to the list
2482 * of guard nodes, at the front. */
2484 entry_guards_prepend_from_config(void)
2486 or_options_t
*options
= get_options();
2487 smartlist_t
*entry_routers
, *entry_fps
;
2488 smartlist_t
*old_entry_guards_on_list
, *old_entry_guards_not_on_list
;
2489 tor_assert(entry_guards
);
2491 should_add_entry_nodes
= 0;
2493 if (!options
->EntryNodes
) {
2494 /* It's possible that a controller set EntryNodes, thus making
2495 * should_add_entry_nodes set, then cleared it again, all before the
2496 * call to choose_random_entry() that triggered us. If so, just return.
2501 if (options
->EntryNodes
) {
2502 char *string
= routerset_to_string(options
->EntryNodes
);
2503 log_info(LD_CIRC
,"Adding configured EntryNodes '%s'.", string
);
2507 entry_routers
= smartlist_create();
2508 entry_fps
= smartlist_create();
2509 old_entry_guards_on_list
= smartlist_create();
2510 old_entry_guards_not_on_list
= smartlist_create();
2512 /* Split entry guards into those on the list and those not. */
2514 /* XXXX022 Now that we allow countries and IP ranges in EntryNodes, this is
2515 * potentially an enormous list. For now, we disable such values for
2516 * EntryNodes in options_validate(); really, this wants a better solution.
2517 * Perhaps we should do this calculation once whenever the list of routers
2518 * changes or the entrynodes setting changes.
2520 routerset_get_all_routers(entry_routers
, options
->EntryNodes
, 0);
2521 SMARTLIST_FOREACH(entry_routers
, routerinfo_t
*, ri
,
2522 smartlist_add(entry_fps
,ri
->cache_info
.identity_digest
));
2523 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, {
2524 if (smartlist_digest_isin(entry_fps
, e
->identity
))
2525 smartlist_add(old_entry_guards_on_list
, e
);
2527 smartlist_add(old_entry_guards_not_on_list
, e
);
2530 /* Remove all currently configured entry guards from entry_routers. */
2531 SMARTLIST_FOREACH(entry_routers
, routerinfo_t
*, ri
, {
2532 if (is_an_entry_guard(ri
->cache_info
.identity_digest
)) {
2533 SMARTLIST_DEL_CURRENT(entry_routers
, ri
);
2537 /* Now build the new entry_guards list. */
2538 smartlist_clear(entry_guards
);
2539 /* First, the previously configured guards that are in EntryNodes. */
2540 smartlist_add_all(entry_guards
, old_entry_guards_on_list
);
2541 /* Next, the rest of EntryNodes */
2542 SMARTLIST_FOREACH(entry_routers
, routerinfo_t
*, ri
, {
2543 add_an_entry_guard(ri
, 0);
2545 /* Finally, the remaining EntryNodes, unless we're strict */
2546 if (options
->StrictEntryNodes
) {
2547 SMARTLIST_FOREACH(old_entry_guards_not_on_list
, entry_guard_t
*, e
,
2548 entry_guard_free(e
));
2550 smartlist_add_all(entry_guards
, old_entry_guards_not_on_list
);
2553 smartlist_free(entry_routers
);
2554 smartlist_free(entry_fps
);
2555 smartlist_free(old_entry_guards_on_list
);
2556 smartlist_free(old_entry_guards_not_on_list
);
2557 entry_guards_changed();
2560 /** Return 1 if we're fine adding arbitrary routers out of the
2561 * directory to our entry guard list. Else return 0. */
2563 entry_list_can_grow(or_options_t
*options
)
2565 if (options
->StrictEntryNodes
)
2567 if (options
->UseBridges
)
2572 /** Pick a live (up and listed) entry guard from entry_guards. If
2573 * <b>state</b> is non-NULL, this is for a specific circuit --
2574 * make sure not to pick this circuit's exit or any node in the
2575 * exit's family. If <b>state</b> is NULL, we're looking for a random
2576 * guard (likely a bridge). */
2578 choose_random_entry(cpath_build_state_t
*state
)
2580 or_options_t
*options
= get_options();
2581 smartlist_t
*live_entry_guards
= smartlist_create();
2582 smartlist_t
*exit_family
= smartlist_create();
2583 routerinfo_t
*chosen_exit
= state
?build_state_get_exit_router(state
) : NULL
;
2584 routerinfo_t
*r
= NULL
;
2585 int need_uptime
= state
? state
->need_uptime
: 0;
2586 int need_capacity
= state
? state
->need_capacity
: 0;
2587 int consider_exit_family
= 0;
2590 smartlist_add(exit_family
, chosen_exit
);
2591 routerlist_add_family(exit_family
, chosen_exit
);
2592 consider_exit_family
= 1;
2596 entry_guards
= smartlist_create();
2598 if (should_add_entry_nodes
)
2599 entry_guards_prepend_from_config();
2601 if (entry_list_can_grow(options
) &&
2603 smartlist_len(entry_guards
) < options
->NumEntryGuards
))
2604 pick_entry_guards();
2607 smartlist_clear(live_entry_guards
);
2608 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
2610 r
= entry_is_live(entry
, need_uptime
, need_capacity
, 0);
2611 if (r
&& (!consider_exit_family
|| !smartlist_isin(exit_family
, r
))) {
2612 smartlist_add(live_entry_guards
, r
);
2613 if (!entry
->made_contact
) {
2614 /* Always start with the first not-yet-contacted entry
2615 * guard. Otherwise we might add several new ones, pick
2616 * the second new one, and now we've expanded our entry
2617 * guard list without needing to. */
2618 goto choose_and_finish
;
2620 if (smartlist_len(live_entry_guards
) >= options
->NumEntryGuards
)
2621 break; /* we have enough */
2625 /* Try to have at least 2 choices available. This way we don't
2626 * get stuck with a single live-but-crummy entry and just keep
2628 * (We might get 2 live-but-crummy entry guards, but so be it.) */
2629 if (smartlist_len(live_entry_guards
) < 2) {
2630 if (entry_list_can_grow(options
)) {
2631 /* still no? try adding a new entry then */
2632 /* XXX if guard doesn't imply fast and stable, then we need
2633 * to tell add_an_entry_guard below what we want, or it might
2634 * be a long time til we get it. -RD */
2635 r
= add_an_entry_guard(NULL
, 0);
2637 entry_guards_changed();
2638 /* XXX we start over here in case the new node we added shares
2639 * a family with our exit node. There's a chance that we'll just
2640 * load up on entry guards here, if the network we're using is
2641 * one big family. Perhaps we should teach add_an_entry_guard()
2642 * to understand nodes-to-avoid-if-possible? -RD */
2646 if (!r
&& need_uptime
) {
2647 need_uptime
= 0; /* try without that requirement */
2650 if (!r
&& need_capacity
) {
2651 /* still no? last attempt, try without requiring capacity */
2655 if (!r
&& !entry_list_can_grow(options
) && consider_exit_family
) {
2656 /* still no? if we're using bridges or have strictentrynodes
2657 * set, and our chosen exit is in the same family as all our
2658 * bridges/entry guards, then be flexible about families. */
2659 consider_exit_family
= 0;
2662 /* live_entry_guards may be empty below. Oh well, we tried. */
2666 if (entry_list_can_grow(options
)) {
2667 /* We choose uniformly at random here, because choose_good_entry_server()
2668 * already weights its choices by bandwidth, so we don't want to
2669 * *double*-weight our guard selection. */
2670 r
= smartlist_choose(live_entry_guards
);
2672 /* We need to weight by bandwidth, because our bridges or entryguards
2673 * were not already selected proportional to their bandwidth. */
2674 r
= routerlist_sl_choose_by_bandwidth(live_entry_guards
, WEIGHT_FOR_GUARD
);
2676 smartlist_free(live_entry_guards
);
2677 smartlist_free(exit_family
);
2681 /** Parse <b>state</b> and learn about the entry guards it describes.
2682 * If <b>set</b> is true, and there are no errors, replace the global
2683 * entry_list with what we find.
2684 * On success, return 0. On failure, alloc into *<b>msg</b> a string
2685 * describing the error, and return -1.
2688 entry_guards_parse_state(or_state_t
*state
, int set
, char **msg
)
2690 entry_guard_t
*node
= NULL
;
2691 smartlist_t
*new_entry_guards
= smartlist_create();
2692 config_line_t
*line
;
2693 time_t now
= time(NULL
);
2694 const char *state_version
= state
->TorVersion
;
2695 digestmap_t
*added_by
= digestmap_new();
2698 for (line
= state
->EntryGuards
; line
; line
= line
->next
) {
2699 if (!strcasecmp(line
->key
, "EntryGuard")) {
2700 smartlist_t
*args
= smartlist_create();
2701 node
= tor_malloc_zero(sizeof(entry_guard_t
));
2702 /* all entry guards on disk have been contacted */
2703 node
->made_contact
= 1;
2704 smartlist_add(new_entry_guards
, node
);
2705 smartlist_split_string(args
, line
->value
, " ",
2706 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
2707 if (smartlist_len(args
)<2) {
2708 *msg
= tor_strdup("Unable to parse entry nodes: "
2709 "Too few arguments to EntryGuard");
2710 } else if (!is_legal_nickname(smartlist_get(args
,0))) {
2711 *msg
= tor_strdup("Unable to parse entry nodes: "
2712 "Bad nickname for EntryGuard");
2714 strlcpy(node
->nickname
, smartlist_get(args
,0), MAX_NICKNAME_LEN
+1);
2715 if (base16_decode(node
->identity
, DIGEST_LEN
, smartlist_get(args
,1),
2716 strlen(smartlist_get(args
,1)))<0) {
2717 *msg
= tor_strdup("Unable to parse entry nodes: "
2718 "Bad hex digest for EntryGuard");
2721 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
2722 smartlist_free(args
);
2725 } else if (!strcasecmp(line
->key
, "EntryGuardDownSince") ||
2726 !strcasecmp(line
->key
, "EntryGuardUnlistedSince")) {
2728 time_t last_try
= 0;
2730 *msg
= tor_strdup("Unable to parse entry nodes: "
2731 "EntryGuardDownSince/UnlistedSince without EntryGuard");
2734 if (parse_iso_time(line
->value
, &when
)<0) {
2735 *msg
= tor_strdup("Unable to parse entry nodes: "
2736 "Bad time in EntryGuardDownSince/UnlistedSince");
2740 /* It's a bad idea to believe info in the future: you can wind
2741 * up with timeouts that aren't allowed to happen for years. */
2744 if (strlen(line
->value
) >= ISO_TIME_LEN
+ISO_TIME_LEN
+1) {
2745 /* ignore failure */
2746 (void) parse_iso_time(line
->value
+ISO_TIME_LEN
+1, &last_try
);
2748 if (!strcasecmp(line
->key
, "EntryGuardDownSince")) {
2749 node
->unreachable_since
= when
;
2750 node
->last_attempted
= last_try
;
2752 node
->bad_since
= when
;
2754 } else if (!strcasecmp(line
->key
, "EntryGuardAddedBy")) {
2756 /* format is digest version date */
2757 if (strlen(line
->value
) < HEX_DIGEST_LEN
+1+1+1+ISO_TIME_LEN
) {
2758 log_warn(LD_BUG
, "EntryGuardAddedBy line is not long enough.");
2761 if (base16_decode(d
, sizeof(d
), line
->value
, HEX_DIGEST_LEN
)<0 ||
2762 line
->value
[HEX_DIGEST_LEN
] != ' ') {
2763 log_warn(LD_BUG
, "EntryGuardAddedBy line %s does not begin with "
2764 "hex digest", escaped(line
->value
));
2767 digestmap_set(added_by
, d
, tor_strdup(line
->value
+HEX_DIGEST_LEN
+1));
2769 log_warn(LD_BUG
, "Unexpected key %s", line
->key
);
2773 SMARTLIST_FOREACH(new_entry_guards
, entry_guard_t
*, e
,
2776 char *val
= digestmap_get(added_by
, e
->identity
);
2777 if (val
&& (sp
= strchr(val
, ' '))) {
2780 if (parse_iso_time(sp
, &when
)<0) {
2781 log_warn(LD_BUG
, "Can't read time %s in EntryGuardAddedBy", sp
);
2783 e
->chosen_by_version
= tor_strdup(val
);
2784 e
->chosen_on_date
= when
;
2787 if (state_version
) {
2788 e
->chosen_by_version
= tor_strdup(state_version
);
2789 e
->chosen_on_date
= time(NULL
) - crypto_rand_int(3600*24*30);
2795 SMARTLIST_FOREACH(new_entry_guards
, entry_guard_t
*, e
,
2796 entry_guard_free(e
));
2797 smartlist_free(new_entry_guards
);
2798 } else { /* !err && set */
2800 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2801 entry_guard_free(e
));
2802 smartlist_free(entry_guards
);
2804 entry_guards
= new_entry_guards
;
2805 entry_guards_dirty
= 0;
2806 /* XXX022 hand new_entry_guards to this func, and move it up a
2807 * few lines, so we don't have to re-dirty it */
2808 if (remove_obsolete_entry_guards())
2809 entry_guards_dirty
= 1;
2811 digestmap_free(added_by
, _tor_free
);
2812 return *msg
? -1 : 0;
2815 /** Our list of entry guards has changed, or some element of one
2816 * of our entry guards has changed. Write the changes to disk within
2817 * the next few minutes.
2820 entry_guards_changed(void)
2823 entry_guards_dirty
= 1;
2825 /* or_state_save() will call entry_guards_update_state(). */
2826 when
= get_options()->AvoidDiskWrites
? time(NULL
) + 3600 : time(NULL
)+600;
2827 or_state_mark_dirty(get_or_state(), when
);
2830 /** If the entry guard info has not changed, do nothing and return.
2831 * Otherwise, free the EntryGuards piece of <b>state</b> and create
2832 * a new one out of the global entry_guards list, and then mark
2833 * <b>state</b> dirty so it will get saved to disk.
2836 entry_guards_update_state(or_state_t
*state
)
2838 config_line_t
**next
, *line
;
2839 if (! entry_guards_dirty
)
2842 config_free_lines(state
->EntryGuards
);
2843 next
= &state
->EntryGuards
;
2846 entry_guards
= smartlist_create();
2847 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2849 char dbuf
[HEX_DIGEST_LEN
+1];
2850 if (!e
->made_contact
)
2851 continue; /* don't write this one to disk */
2852 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2853 line
->key
= tor_strdup("EntryGuard");
2854 line
->value
= tor_malloc(HEX_DIGEST_LEN
+MAX_NICKNAME_LEN
+2);
2855 base16_encode(dbuf
, sizeof(dbuf
), e
->identity
, DIGEST_LEN
);
2856 tor_snprintf(line
->value
,HEX_DIGEST_LEN
+MAX_NICKNAME_LEN
+2,
2857 "%s %s", e
->nickname
, dbuf
);
2858 next
= &(line
->next
);
2859 if (e
->unreachable_since
) {
2860 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2861 line
->key
= tor_strdup("EntryGuardDownSince");
2862 line
->value
= tor_malloc(ISO_TIME_LEN
+1+ISO_TIME_LEN
+1);
2863 format_iso_time(line
->value
, e
->unreachable_since
);
2864 if (e
->last_attempted
) {
2865 line
->value
[ISO_TIME_LEN
] = ' ';
2866 format_iso_time(line
->value
+ISO_TIME_LEN
+1, e
->last_attempted
);
2868 next
= &(line
->next
);
2871 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2872 line
->key
= tor_strdup("EntryGuardUnlistedSince");
2873 line
->value
= tor_malloc(ISO_TIME_LEN
+1);
2874 format_iso_time(line
->value
, e
->bad_since
);
2875 next
= &(line
->next
);
2877 if (e
->chosen_on_date
&& e
->chosen_by_version
&&
2878 !strchr(e
->chosen_by_version
, ' ')) {
2879 char d
[HEX_DIGEST_LEN
+1];
2880 char t
[ISO_TIME_LEN
+1];
2882 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2883 line
->key
= tor_strdup("EntryGuardAddedBy");
2884 val_len
= (HEX_DIGEST_LEN
+1+strlen(e
->chosen_by_version
)
2886 line
->value
= tor_malloc(val_len
);
2887 base16_encode(d
, sizeof(d
), e
->identity
, DIGEST_LEN
);
2888 format_iso_time(t
, e
->chosen_on_date
);
2889 tor_snprintf(line
->value
, val_len
, "%s %s %s",
2890 d
, e
->chosen_by_version
, t
);
2891 next
= &(line
->next
);
2894 if (!get_options()->AvoidDiskWrites
)
2895 or_state_mark_dirty(get_or_state(), 0);
2896 entry_guards_dirty
= 0;
2899 /** If <b>question</b> is the string "entry-guards", then dump
2900 * to *<b>answer</b> a newly allocated string describing all of
2901 * the nodes in the global entry_guards list. See control-spec.txt
2903 * For backward compatibility, we also handle the string "helper-nodes".
2906 getinfo_helper_entry_guards(control_connection_t
*conn
,
2907 const char *question
, char **answer
)
2909 int use_long_names
= conn
->use_long_names
;
2911 if (!strcmp(question
,"entry-guards") ||
2912 !strcmp(question
,"helper-nodes")) {
2913 smartlist_t
*sl
= smartlist_create();
2914 char tbuf
[ISO_TIME_LEN
+1];
2915 char nbuf
[MAX_VERBOSE_NICKNAME_LEN
+1];
2917 entry_guards
= smartlist_create();
2918 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2920 size_t len
= MAX_VERBOSE_NICKNAME_LEN
+ISO_TIME_LEN
+32;
2921 char *c
= tor_malloc(len
);
2922 const char *status
= NULL
;
2924 if (!e
->made_contact
) {
2925 status
= "never-connected";
2926 } else if (e
->bad_since
) {
2927 when
= e
->bad_since
;
2928 status
= "unusable";
2932 if (use_long_names
) {
2933 routerinfo_t
*ri
= router_get_by_digest(e
->identity
);
2935 router_get_verbose_nickname(nbuf
, ri
);
2938 base16_encode(nbuf
+1, sizeof(nbuf
)-1, e
->identity
, DIGEST_LEN
);
2939 /* e->nickname field is not very reliable if we don't know about
2940 * this router any longer; don't include it. */
2943 base16_encode(nbuf
, sizeof(nbuf
), e
->identity
, DIGEST_LEN
);
2946 format_iso_time(tbuf
, when
);
2947 tor_snprintf(c
, len
, "%s %s %s\n", nbuf
, status
, tbuf
);
2949 tor_snprintf(c
, len
, "%s %s\n", nbuf
, status
);
2951 smartlist_add(sl
, c
);
2953 *answer
= smartlist_join_strings(sl
, "", 0, NULL
);
2954 SMARTLIST_FOREACH(sl
, char *, c
, tor_free(c
));
2960 /** Information about a configured bridge. Currently this just matches the
2961 * ones in the torrc file, but one day we may be able to learn about new
2962 * bridges on our own, and remember them in the state file. */
2964 /** Address of the bridge. */
2966 /** TLS port for the bridge. */
2968 /** Expected identity digest, or all zero bytes if we don't know what the
2969 * digest should be. */
2970 char identity
[DIGEST_LEN
];
2971 /** When should we next try to fetch a descriptor for this bridge? */
2972 download_status_t fetch_status
;
2975 /** A list of configured bridges. Whenever we actually get a descriptor
2976 * for one, we add it as an entry guard. */
2977 static smartlist_t
*bridge_list
= NULL
;
2979 /** Initialize the bridge list to empty, creating it if needed. */
2981 clear_bridge_list(void)
2984 bridge_list
= smartlist_create();
2985 SMARTLIST_FOREACH(bridge_list
, bridge_info_t
*, b
, tor_free(b
));
2986 smartlist_clear(bridge_list
);
2989 /** Return a bridge pointer if <b>ri</b> is one of our known bridges
2990 * (either by comparing keys if possible, else by comparing addr/port).
2991 * Else return NULL. */
2992 static bridge_info_t
*
2993 routerinfo_get_configured_bridge(routerinfo_t
*ri
)
2997 SMARTLIST_FOREACH_BEGIN(bridge_list
, bridge_info_t
*, bridge
)
2999 if (tor_digest_is_zero(bridge
->identity
) &&
3000 tor_addr_eq_ipv4h(&bridge
->addr
, ri
->addr
) &&
3001 bridge
->port
== ri
->or_port
)
3003 if (!memcmp(bridge
->identity
, ri
->cache_info
.identity_digest
,
3007 SMARTLIST_FOREACH_END(bridge
);
3011 /** Return 1 if <b>ri</b> is one of our known bridges, else 0. */
3013 routerinfo_is_a_configured_bridge(routerinfo_t
*ri
)
3015 return routerinfo_get_configured_bridge(ri
) ? 1 : 0;
3018 /** Remember a new bridge at <b>addr</b>:<b>port</b>. If <b>digest</b>
3019 * is set, it tells us the identity key too. */
3021 bridge_add_from_config(const tor_addr_t
*addr
, uint16_t port
, char *digest
)
3023 bridge_info_t
*b
= tor_malloc_zero(sizeof(bridge_info_t
));
3024 tor_addr_copy(&b
->addr
, addr
);
3027 memcpy(b
->identity
, digest
, DIGEST_LEN
);
3028 b
->fetch_status
.schedule
= DL_SCHED_BRIDGE
;
3030 bridge_list
= smartlist_create();
3031 smartlist_add(bridge_list
, b
);
3034 /** If <b>digest</b> is one of our known bridges, return it. */
3035 static bridge_info_t
*
3036 find_bridge_by_digest(const char *digest
)
3038 SMARTLIST_FOREACH(bridge_list
, bridge_info_t
*, bridge
,
3040 if (!memcmp(bridge
->identity
, digest
, DIGEST_LEN
))
3046 /** We need to ask <b>bridge</b> for its server descriptor. <b>address</b>
3047 * is a helpful string describing this bridge. */
3049 launch_direct_bridge_descriptor_fetch(bridge_info_t
*bridge
)
3053 if (connection_get_by_type_addr_port_purpose(
3054 CONN_TYPE_DIR
, &bridge
->addr
, bridge
->port
,
3055 DIR_PURPOSE_FETCH_SERVERDESC
))
3056 return; /* it's already on the way */
3058 address
= tor_dup_addr(&bridge
->addr
);
3059 directory_initiate_command(address
, &bridge
->addr
,
3061 0, /* does not matter */
3062 1, bridge
->identity
,
3063 DIR_PURPOSE_FETCH_SERVERDESC
,
3064 ROUTER_PURPOSE_BRIDGE
,
3065 0, "authority.z", NULL
, 0, 0);
3069 /** Fetching the bridge descriptor from the bridge authority returned a
3070 * "not found". Fall back to trying a direct fetch. */
3072 retry_bridge_descriptor_fetch_directly(const char *digest
)
3074 bridge_info_t
*bridge
= find_bridge_by_digest(digest
);
3076 return; /* not found? oh well. */
3078 launch_direct_bridge_descriptor_fetch(bridge
);
3081 /** For each bridge in our list for which we don't currently have a
3082 * descriptor, fetch a new copy of its descriptor -- either directly
3083 * from the bridge or via a bridge authority. */
3085 fetch_bridge_descriptors(time_t now
)
3087 or_options_t
*options
= get_options();
3088 int num_bridge_auths
= get_n_authorities(BRIDGE_AUTHORITY
);
3089 int ask_bridge_directly
;
3090 int can_use_bridge_authority
;
3095 SMARTLIST_FOREACH_BEGIN(bridge_list
, bridge_info_t
*, bridge
)
3097 if (!download_status_is_ready(&bridge
->fetch_status
, now
,
3098 IMPOSSIBLE_TO_DOWNLOAD
))
3099 continue; /* don't bother, no need to retry yet */
3101 /* schedule another fetch as if this one will fail, in case it does */
3102 download_status_failed(&bridge
->fetch_status
, 0);
3104 can_use_bridge_authority
= !tor_digest_is_zero(bridge
->identity
) &&
3106 ask_bridge_directly
= !can_use_bridge_authority
||
3107 !options
->UpdateBridgesFromAuthority
;
3108 log_debug(LD_DIR
, "ask_bridge_directly=%d (%d, %d, %d)",
3109 ask_bridge_directly
, tor_digest_is_zero(bridge
->identity
),
3110 !options
->UpdateBridgesFromAuthority
, !num_bridge_auths
);
3112 if (ask_bridge_directly
&&
3113 !fascist_firewall_allows_address_or(&bridge
->addr
, bridge
->port
)) {
3114 log_notice(LD_DIR
, "Bridge at '%s:%d' isn't reachable by our "
3115 "firewall policy. %s.", fmt_addr(&bridge
->addr
),
3117 can_use_bridge_authority
?
3118 "Asking bridge authority instead" : "Skipping");
3119 if (can_use_bridge_authority
)
3120 ask_bridge_directly
= 0;
3125 if (ask_bridge_directly
) {
3126 /* we need to ask the bridge itself for its descriptor. */
3127 launch_direct_bridge_descriptor_fetch(bridge
);
3129 /* We have a digest and we want to ask an authority. We could
3130 * combine all the requests into one, but that may give more
3131 * hints to the bridge authority than we want to give. */
3132 char resource
[10 + HEX_DIGEST_LEN
];
3133 memcpy(resource
, "fp/", 3);
3134 base16_encode(resource
+3, HEX_DIGEST_LEN
+1,
3135 bridge
->identity
, DIGEST_LEN
);
3136 memcpy(resource
+3+HEX_DIGEST_LEN
, ".z", 3);
3137 log_info(LD_DIR
, "Fetching bridge info '%s' from bridge authority.",
3139 directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC
,
3140 ROUTER_PURPOSE_BRIDGE
, resource
, 0);
3143 SMARTLIST_FOREACH_END(bridge
);
3146 /** We just learned a descriptor for a bridge. See if that
3147 * digest is in our entry guard list, and add it if not. */
3149 learned_bridge_descriptor(routerinfo_t
*ri
, int from_cache
)
3152 tor_assert(ri
->purpose
== ROUTER_PURPOSE_BRIDGE
);
3153 if (get_options()->UseBridges
) {
3154 int first
= !any_bridge_descriptors_known();
3155 bridge_info_t
*bridge
= routerinfo_get_configured_bridge(ri
);
3156 time_t now
= time(NULL
);
3159 if (bridge
) { /* if we actually want to use this one */
3160 /* it's here; schedule its re-fetch for a long time from now. */
3162 download_status_reset(&bridge
->fetch_status
);
3164 add_an_entry_guard(ri
, 1);
3165 log_notice(LD_DIR
, "new bridge descriptor '%s' (%s)", ri
->nickname
,
3166 from_cache
? "cached" : "fresh");
3167 /* set entry->made_contact so if it goes down we don't drop it from
3168 * our entry node list */
3169 entry_guard_register_connect_status(ri
->cache_info
.identity_digest
,
3172 routerlist_retry_directory_downloads(now
);
3177 /** Return 1 if any of our entry guards have descriptors that
3178 * are marked with purpose 'bridge' and are running. Else return 0.
3180 * We use this function to decide if we're ready to start building
3181 * circuits through our bridges, or if we need to wait until the
3182 * directory "server/authority" requests finish. */
3184 any_bridge_descriptors_known(void)
3186 tor_assert(get_options()->UseBridges
);
3187 return choose_random_entry(NULL
)!=NULL
? 1 : 0;
3190 /** Return 1 if there are any directory conns fetching bridge descriptors
3191 * that aren't marked for close. We use this to guess if we should tell
3192 * the controller that we have a problem. */
3194 any_pending_bridge_descriptor_fetches(void)
3196 smartlist_t
*conns
= get_connection_array();
3197 SMARTLIST_FOREACH(conns
, connection_t
*, conn
,
3199 if (conn
->type
== CONN_TYPE_DIR
&&
3200 conn
->purpose
== DIR_PURPOSE_FETCH_SERVERDESC
&&
3201 TO_DIR_CONN(conn
)->router_purpose
== ROUTER_PURPOSE_BRIDGE
&&
3202 !conn
->marked_for_close
&&
3203 conn
->linked
&& !conn
->linked_conn
->marked_for_close
) {
3204 log_debug(LD_DIR
, "found one: %s", conn
->address
);
3211 /** Return 1 if we have at least one descriptor for a bridge and
3212 * all descriptors we know are down. Else return 0. If <b>act</b> is
3213 * 1, then mark the down bridges up; else just observe and report. */
3215 bridges_retry_helper(int act
)
3219 int any_running
= 0;
3221 entry_guards
= smartlist_create();
3222 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
3224 ri
= router_get_by_digest(e
->identity
);
3225 if (ri
&& ri
->purpose
== ROUTER_PURPOSE_BRIDGE
) {
3228 any_running
= 1; /* some bridge is both known and running */
3229 else if (act
) { /* mark it for retry */
3236 log_debug(LD_DIR
, "%d: any_known %d, any_running %d",
3237 act
, any_known
, any_running
);
3238 return any_known
&& !any_running
;
3241 /** Do we know any descriptors for our bridges, and are they all
3244 bridges_known_but_down(void)
3246 return bridges_retry_helper(0);
3249 /** Mark all down known bridges up. */
3251 bridges_retry_all(void)
3253 bridges_retry_helper(1);
3256 /** Release all storage held by the list of entry guards and related
3257 * memory structs. */
3259 entry_guards_free_all(void)
3262 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
3263 entry_guard_free(e
));
3264 smartlist_free(entry_guards
);
3265 entry_guards
= NULL
;
3267 clear_bridge_list();
3268 smartlist_free(bridge_list
);