1 /* Copyright (c) 2001 Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2007, Roger Dingledine, Nick Mathewson. */
4 /* See LICENSE for licensing information */
6 const char circuitbuild_c_id
[] =
10 * \file circuitbuild.c
11 * \brief The actual details of building circuits.
16 /********* START VARIABLES **********/
18 /** A global list of all circuits at this hop. */
19 extern circuit_t
*global_circuitlist
;
21 /** An entry_guard_t represents our information about a chosen long-term
22 * first hop, known as a "helper" node in the literature. We can't just
23 * use a routerinfo_t, since we want to remember these even when we
24 * don't have a directory. */
26 char nickname
[MAX_NICKNAME_LEN
+1];
27 char identity
[DIGEST_LEN
];
28 unsigned int made_contact
: 1; /**< 0 if we have never connected to this
29 * router, 1 if we have. */
30 unsigned int can_retry
: 1; /**< Should we retry connecting to this entry,
31 * in spite of having it marked as unreachable?*/
32 time_t bad_since
; /**< 0 if this guard is currently usable, or the time at
33 * which it was observed to become (according to the
34 * directory or the user configuration) unusable. */
35 time_t unreachable_since
; /**< 0 if we can connect to this guard, or the
36 * time at which we first noticed we couldn't
38 time_t last_attempted
; /**< 0 if we can connect to this guard, or the time
39 * at which we last failed to connect to it. */
42 /** A list of our chosen entry guards. */
43 static smartlist_t
*entry_guards
= NULL
;
44 /** A value of 1 means that the entry_guards list has changed
45 * and those changes need to be flushed to disk. */
46 static int entry_guards_dirty
= 0;
48 /********* END VARIABLES ************/
50 static int circuit_deliver_create_cell(circuit_t
*circ
,
51 uint8_t cell_type
, const char *payload
);
52 static int onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
);
53 static crypt_path_t
*onion_next_hop_in_cpath(crypt_path_t
*cpath
);
54 static int onion_extend_cpath(origin_circuit_t
*circ
);
55 static int count_acceptable_routers(smartlist_t
*routers
);
56 static int onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
);
58 static routerinfo_t
*choose_random_entry(cpath_build_state_t
*state
);
59 static void entry_guards_changed(void);
61 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
62 * and with the high bit specified by conn-\>circ_id_type, until we get
63 * a circ_id that is not in use by any other circuit on that conn.
65 * Return it, or 0 if can't get a unique circ_id.
68 get_unique_circ_id_by_conn(or_connection_t
*conn
)
70 uint16_t test_circ_id
;
75 if (conn
->circ_id_type
== CIRC_ID_TYPE_NEITHER
) {
76 log_warn(LD_BUG
, "Bug: Trying to pick a circuit ID for a connection from "
77 "a client with no identity.");
80 high_bit
= (conn
->circ_id_type
== CIRC_ID_TYPE_HIGHER
) ? 1<<15 : 0;
82 /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
83 * circID such that (high_bit|test_circ_id) is not already used. */
84 test_circ_id
= conn
->next_circ_id
++;
85 if (test_circ_id
== 0 || test_circ_id
>= 1<<15) {
87 conn
->next_circ_id
= 2;
89 if (++attempts
> 1<<15) {
90 /* Make sure we don't loop forever if all circ_id's are used. This
91 * matters because it's an external DoS opportunity.
93 log_warn(LD_CIRC
,"No unused circ IDs. Failing.");
96 test_circ_id
|= high_bit
;
97 } while (circuit_get_by_circid_orconn(test_circ_id
, conn
));
101 /** If <b>verbose</b> is false, allocate and return a comma-separated list of
102 * the currently built elements of circuit_t. If <b>verbose</b> is true, also
103 * list information about link status in a more verbose format using spaces.
104 * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
105 * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
109 circuit_list_path_impl(origin_circuit_t
*circ
, int verbose
, int verbose_names
)
112 smartlist_t
*elements
;
113 const char *states
[] = {"closed", "waiting for keys", "open"};
117 elements
= smartlist_create();
120 const char *nickname
= build_state_get_exit_nickname(circ
->build_state
);
121 tor_snprintf(buf
, sizeof(buf
), "%s%s circ (length %d%s%s):",
122 circ
->build_state
->is_internal
? "internal" : "exit",
123 circ
->build_state
->need_uptime
? " (high-uptime)" : "",
124 circ
->build_state
->desired_path_len
,
125 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" : ", exit ",
126 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" :
127 (nickname
?nickname
:"*unnamed*"));
128 smartlist_add(elements
, tor_strdup(buf
));
137 if (!verbose
&& hop
->state
!= CPATH_STATE_OPEN
)
139 if (!hop
->extend_info
)
142 elt
= tor_malloc(MAX_VERBOSE_NICKNAME_LEN
+1);
143 if ((ri
= router_get_by_digest(hop
->extend_info
->identity_digest
))) {
144 router_get_verbose_nickname(elt
, ri
);
145 } else if (hop
->extend_info
->nickname
&&
146 is_legal_nickname(hop
->extend_info
->nickname
)) {
148 base16_encode(elt
+1, HEX_DIGEST_LEN
+1,
149 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
150 elt
[HEX_DIGEST_LEN
+1]= '~';
151 strlcpy(elt
+HEX_DIGEST_LEN
+2,
152 hop
->extend_info
->nickname
, MAX_NICKNAME_LEN
+1);
155 base16_encode(elt
+1, HEX_DIGEST_LEN
+1,
156 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
158 } else { /* ! verbose_names */
159 if ((ri
= router_get_by_digest(hop
->extend_info
->identity_digest
)) &&
161 elt
= tor_strdup(hop
->extend_info
->nickname
);
163 elt
= tor_malloc(HEX_DIGEST_LEN
+2);
165 base16_encode(elt
+1, HEX_DIGEST_LEN
+1,
166 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
171 size_t len
= strlen(elt
)+2+strlen(states
[hop
->state
])+1;
172 char *v
= tor_malloc(len
);
173 tor_assert(hop
->state
<= 2);
174 tor_snprintf(v
,len
,"%s(%s)",elt
,states
[hop
->state
]);
175 smartlist_add(elements
, v
);
178 smartlist_add(elements
, elt
);
181 } while (hop
!= circ
->cpath
);
183 s
= smartlist_join_strings(elements
, verbose
?" ":",", 0, NULL
);
184 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
185 smartlist_free(elements
);
189 /** If <b>verbose</b> is false, allocate and return a comma-separated
190 * list of the currently built elements of circuit_t. If
191 * <b>verbose</b> is true, also list information about link status in
192 * a more verbose format using spaces.
195 circuit_list_path(origin_circuit_t
*circ
, int verbose
)
197 return circuit_list_path_impl(circ
, verbose
, 0);
200 /** Allocate and return a comma-separated list of the currently built elements
201 * of circuit_t, giving each as a verbose nickname.
204 circuit_list_path_for_controller(origin_circuit_t
*circ
)
206 return circuit_list_path_impl(circ
, 0, 1);
209 /** Log, at severity <b>severity</b>, the nicknames of each router in
210 * circ's cpath. Also log the length of the cpath, and the intended
214 circuit_log_path(int severity
, unsigned int domain
, origin_circuit_t
*circ
)
216 char *s
= circuit_list_path(circ
,1);
217 log(severity
,domain
,"%s",s
);
221 /** Tell the rep(utation)hist(ory) module about the status of the links
222 * in circ. Hops that have become OPEN are marked as successfully
223 * extended; the _first_ hop that isn't open (if any) is marked as
226 /* XXXX Someday we should learn from OR circuits too. */
228 circuit_rep_hist_note_result(origin_circuit_t
*circ
)
231 char *prev_digest
= NULL
;
232 routerinfo_t
*router
;
234 if (!hop
) /* circuit hasn't started building yet. */
236 if (server_mode(get_options())) {
237 routerinfo_t
*me
= router_get_my_routerinfo();
240 prev_digest
= me
->cache_info
.identity_digest
;
243 router
= router_get_by_digest(hop
->extend_info
->identity_digest
);
246 if (hop
->state
== CPATH_STATE_OPEN
)
247 rep_hist_note_extend_succeeded(prev_digest
,
248 router
->cache_info
.identity_digest
);
250 rep_hist_note_extend_failed(prev_digest
,
251 router
->cache_info
.identity_digest
);
255 prev_digest
= router
->cache_info
.identity_digest
;
260 } while (hop
!=circ
->cpath
);
263 /** Pick all the entries in our cpath. Stop and return 0 when we're
264 * happy, or return -1 if an error occurs. */
266 onion_populate_cpath(origin_circuit_t
*circ
)
270 r
= onion_extend_cpath(circ
);
272 log_info(LD_CIRC
,"Generating cpath hop failed.");
277 return 0; /* if r == 1 */
280 /** Create and return a new origin circuit. Initialize its purpose and
281 * build-state based on our arguments. */
283 origin_circuit_init(uint8_t purpose
, int onehop_tunnel
,
284 int need_uptime
, int need_capacity
, int internal
)
286 /* sets circ->p_circ_id and circ->p_conn */
287 origin_circuit_t
*circ
= origin_circuit_new();
288 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OR_WAIT
);
289 circ
->build_state
= tor_malloc_zero(sizeof(cpath_build_state_t
));
290 circ
->build_state
->onehop_tunnel
= onehop_tunnel
;
291 circ
->build_state
->need_uptime
= need_uptime
;
292 circ
->build_state
->need_capacity
= need_capacity
;
293 circ
->build_state
->is_internal
= internal
;
294 circ
->_base
.purpose
= purpose
;
298 /** Build a new circuit for <b>purpose</b>. If <b>info</b>
299 * is defined, then use that as your exit router, else choose a suitable
302 * Also launch a connection to the first OR in the chosen path, if
303 * it's not open already.
306 circuit_establish_circuit(uint8_t purpose
, int onehop_tunnel
,
308 int need_uptime
, int need_capacity
, int internal
)
310 origin_circuit_t
*circ
;
313 circ
= origin_circuit_init(purpose
, onehop_tunnel
,
314 need_uptime
, need_capacity
, internal
);
316 if (onion_pick_cpath_exit(circ
, info
) < 0 ||
317 onion_populate_cpath(circ
) < 0) {
318 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_NOPATH
);
322 control_event_circuit_status(circ
, CIRC_EVENT_LAUNCHED
, 0);
324 if ((err_reason
= circuit_handle_first_hop(circ
)) < 0) {
325 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
331 /** Start establishing the first hop of our circuit. Figure out what
332 * OR we should connect to, and if necessary start the connection to
333 * it. If we're already connected, then send the 'create' cell.
334 * Return 0 for ok, -reason if circ should be marked-for-close. */
336 circuit_handle_first_hop(origin_circuit_t
*circ
)
338 crypt_path_t
*firsthop
;
339 or_connection_t
*n_conn
;
340 char tmpbuf
[INET_NTOA_BUF_LEN
];
344 firsthop
= onion_next_hop_in_cpath(circ
->cpath
);
345 tor_assert(firsthop
);
346 tor_assert(firsthop
->extend_info
);
348 /* now see if we're already connected to the first OR in 'route' */
349 in
.s_addr
= htonl(firsthop
->extend_info
->addr
);
350 tor_inet_ntoa(&in
, tmpbuf
, sizeof(tmpbuf
));
351 log_debug(LD_CIRC
,"Looking for firsthop '%s:%u'",tmpbuf
,
352 firsthop
->extend_info
->port
);
353 /* imprint the circuit with its future n_conn->id */
354 memcpy(circ
->_base
.n_conn_id_digest
, firsthop
->extend_info
->identity_digest
,
356 n_conn
= connection_or_get_by_identity_digest(
357 firsthop
->extend_info
->identity_digest
);
358 /* If we don't have an open conn, or the conn we have is obsolete
359 * (i.e. old or broken) and the other side will let us make a second
360 * connection without dropping it immediately... */
361 if (!n_conn
|| n_conn
->_base
.state
!= OR_CONN_STATE_OPEN
||
362 (n_conn
->_base
.or_is_obsolete
&&
363 router_digest_version_as_new_as(firsthop
->extend_info
->identity_digest
,
364 "0.1.1.9-alpha-cvs"))) {
365 /* not currently connected */
366 circ
->_base
.n_addr
= firsthop
->extend_info
->addr
;
367 circ
->_base
.n_port
= firsthop
->extend_info
->port
;
369 if (!n_conn
|| n_conn
->_base
.or_is_obsolete
) { /* launch the connection */
370 n_conn
= connection_or_connect(firsthop
->extend_info
->addr
,
371 firsthop
->extend_info
->port
,
372 firsthop
->extend_info
->identity_digest
);
373 if (!n_conn
) { /* connect failed, forget the whole thing */
374 log_info(LD_CIRC
,"connect to firsthop failed. Closing.");
375 return -END_CIRC_REASON_CONNECTFAILED
;
379 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
380 /* return success. The onion/circuit/etc will be taken care of
381 * automatically (may already have been) whenever n_conn reaches
382 * OR_CONN_STATE_OPEN.
385 } else { /* it's already open. use it. */
386 circ
->_base
.n_addr
= n_conn
->_base
.addr
;
387 circ
->_base
.n_port
= n_conn
->_base
.port
;
388 circ
->_base
.n_conn
= n_conn
;
389 log_debug(LD_CIRC
,"Conn open. Delivering first onion skin.");
390 if ((err_reason
= circuit_send_next_onion_skin(circ
)) < 0) {
391 log_info(LD_CIRC
,"circuit_send_next_onion_skin failed.");
398 /** Find any circuits that are waiting on <b>or_conn</b> to become
399 * open and get them to send their create cells forward.
401 * Status is 1 if connect succeeded, or 0 if connect failed.
404 circuit_n_conn_done(or_connection_t
*or_conn
, int status
)
406 smartlist_t
*pending_circs
;
409 log_debug(LD_CIRC
,"or_conn to %s, status=%d",
410 or_conn
->nickname
? or_conn
->nickname
: "NULL", status
);
412 pending_circs
= smartlist_create();
413 circuit_get_all_pending_on_or_conn(pending_circs
, or_conn
);
415 SMARTLIST_FOREACH(pending_circs
, circuit_t
*, circ
,
417 /* This check is redundant wrt get_all_pending_on_or_conn, but I'm
418 * leaving them in in case it's possible for the status of a circuit to
419 * change as we're going down the list. */
420 if (circ
->marked_for_close
|| circ
->n_conn
||
421 circ
->state
!= CIRCUIT_STATE_OR_WAIT
||
422 memcmp(or_conn
->identity_digest
, circ
->n_conn_id_digest
, DIGEST_LEN
))
424 if (!status
) { /* or_conn failed; close circ */
425 log_info(LD_CIRC
,"or_conn failed. Closing circ.");
426 circuit_mark_for_close(circ
, END_CIRC_REASON_OR_CONN_CLOSED
);
429 log_debug(LD_CIRC
, "Found circ, sending create cell.");
430 /* circuit_deliver_create_cell will set n_circ_id and add us to
431 * orconn_circuid_circuit_map, so we don't need to call
432 * set_circid_orconn here. */
433 circ
->n_conn
= or_conn
;
434 if (CIRCUIT_IS_ORIGIN(circ
)) {
436 circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ
))) < 0) {
438 "send_next_onion_skin failed; circuit marked for closing.");
439 circuit_mark_for_close(circ
, -err_reason
);
441 /* XXX could this be bad, eg if next_onion_skin failed because conn
445 /* pull the create cell out of circ->onionskin, and send it */
446 tor_assert(circ
->onionskin
);
447 if (circuit_deliver_create_cell(circ
,CELL_CREATE
,circ
->onionskin
)<0) {
448 circuit_mark_for_close(circ
, END_CIRC_REASON_RESOURCELIMIT
);
451 tor_free(circ
->onionskin
);
452 circuit_set_state(circ
, CIRCUIT_STATE_OPEN
);
456 smartlist_free(pending_circs
);
459 /** Find a new circid that isn't currently in use on the circ->n_conn
461 * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
462 * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
464 * Return -1 if we failed to find a suitable circid, else return 0.
467 circuit_deliver_create_cell(circuit_t
*circ
, uint8_t cell_type
,
474 tor_assert(circ
->n_conn
);
476 tor_assert(cell_type
== CELL_CREATE
|| cell_type
== CELL_CREATE_FAST
);
478 id
= get_unique_circ_id_by_conn(circ
->n_conn
);
480 log_warn(LD_CIRC
,"failed to get unique circID.");
483 log_debug(LD_CIRC
,"Chosen circID %u.", id
);
484 circuit_set_n_circid_orconn(circ
, id
, circ
->n_conn
);
486 memset(&cell
, 0, sizeof(cell_t
));
487 cell
.command
= cell_type
;
488 cell
.circ_id
= circ
->n_circ_id
;
490 memcpy(cell
.payload
, payload
, ONIONSKIN_CHALLENGE_LEN
);
491 connection_or_write_cell_to_buf(&cell
, circ
->n_conn
);
495 /** We've decided to start our reachability testing. If all
496 * is set, log this to the user. Return 1 if we did, or 0 if
497 * we chose not to log anything. */
499 inform_testing_reachability(void)
502 routerinfo_t
*me
= router_get_my_routerinfo();
506 tor_snprintf(dirbuf
, sizeof(dirbuf
), " and DirPort %s:%d",
507 me
->address
, me
->dir_port
);
508 log(LOG_NOTICE
, LD_OR
, "Now checking whether ORPort %s:%d%s %s reachable... "
509 "(this may take up to %d minutes -- look for log "
510 "messages indicating success)",
511 me
->address
, me
->or_port
,
512 me
->dir_port
? dirbuf
: "",
513 me
->dir_port
? "are" : "is",
514 TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT
/60);
518 /** Return true iff we should send a create_fast cell to build a circuit
519 * starting at <b>router</b>. (If <b>router</b> is NULL, we don't have
520 * information on the router, so assume true.) */
522 should_use_create_fast_for_router(routerinfo_t
*router
,
523 origin_circuit_t
*circ
)
525 or_options_t
*options
= get_options();
527 if (!options
->FastFirstHopPK
) /* create_fast is disabled */
529 if (router
&& router
->platform
&&
530 !tor_version_as_new_as(router
->platform
, "0.1.0.6-rc")) {
531 /* known not to work */
534 if (server_mode(options
) && circ
->cpath
->extend_info
->onion_key
) {
535 /* We're a server, and we know an onion key. We can choose.
536 * Prefer to blend in. */
543 /** This is the backbone function for building circuits.
545 * If circ's first hop is closed, then we need to build a create
546 * cell and send it forward.
548 * Otherwise, we need to build a relay extend cell and send it
551 * Return -reason if we want to tear down circ, else return 0.
554 circuit_send_next_onion_skin(origin_circuit_t
*circ
)
557 routerinfo_t
*router
;
558 char payload
[2+4+DIGEST_LEN
+ONIONSKIN_CHALLENGE_LEN
];
564 if (circ
->cpath
->state
== CPATH_STATE_CLOSED
) {
567 log_debug(LD_CIRC
,"First skin; sending create cell.");
569 router
= router_get_by_digest(circ
->_base
.n_conn
->identity_digest
);
570 fast
= should_use_create_fast_for_router(router
, circ
);
571 if (!fast
&& !circ
->cpath
->extend_info
->onion_key
) {
573 "Can't send create_fast, but have no onion key. Failing.");
574 return - END_CIRC_REASON_INTERNAL
;
577 /* We are an OR, or we are connecting to an old Tor: we should
578 * send an old slow create cell.
580 cell_type
= CELL_CREATE
;
581 if (onion_skin_create(circ
->cpath
->extend_info
->onion_key
,
582 &(circ
->cpath
->dh_handshake_state
),
584 log_warn(LD_CIRC
,"onion_skin_create (first hop) failed.");
585 return - END_CIRC_REASON_INTERNAL
;
588 /* We are not an OR, and we're building the first hop of a circuit to a
589 * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
590 * and a DH operation. */
591 cell_type
= CELL_CREATE_FAST
;
592 memset(payload
, 0, sizeof(payload
));
593 crypto_rand(circ
->cpath
->fast_handshake_state
,
594 sizeof(circ
->cpath
->fast_handshake_state
));
595 memcpy(payload
, circ
->cpath
->fast_handshake_state
,
596 sizeof(circ
->cpath
->fast_handshake_state
));
599 if (circuit_deliver_create_cell(TO_CIRCUIT(circ
), cell_type
, payload
) < 0)
600 return - END_CIRC_REASON_RESOURCELIMIT
;
602 circ
->cpath
->state
= CPATH_STATE_AWAITING_KEYS
;
603 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
604 log_info(LD_CIRC
,"First hop: finished sending %s cell to '%s'",
605 fast
? "CREATE_FAST" : "CREATE",
606 router
? router
->nickname
: "<unnamed>");
608 tor_assert(circ
->cpath
->state
== CPATH_STATE_OPEN
);
609 tor_assert(circ
->_base
.state
== CIRCUIT_STATE_BUILDING
);
610 log_debug(LD_CIRC
,"starting to send subsequent skin.");
611 hop
= onion_next_hop_in_cpath(circ
->cpath
);
613 /* done building the circuit. whew. */
614 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
615 log_info(LD_CIRC
,"circuit built!");
616 circuit_reset_failure_count(0);
617 if (!has_completed_circuit
&& !circ
->build_state
->onehop_tunnel
) {
618 or_options_t
*options
= get_options();
619 has_completed_circuit
=1;
620 /* FFFF Log a count of known routers here */
621 log(LOG_NOTICE
, LD_GENERAL
,
622 "Tor has successfully opened a circuit. "
623 "Looks like client functionality is working.");
624 control_event_client_status(LOG_NOTICE
, "CIRCUIT_ESTABLISHED");
625 if (server_mode(options
) && !check_whether_orport_reachable()) {
626 inform_testing_reachability();
627 consider_testing_reachability(1, 1);
630 circuit_rep_hist_note_result(circ
);
631 circuit_has_opened(circ
); /* do other actions as necessary */
635 set_uint32(payload
, htonl(hop
->extend_info
->addr
));
636 set_uint16(payload
+4, htons(hop
->extend_info
->port
));
638 onionskin
= payload
+2+4;
639 memcpy(payload
+2+4+ONIONSKIN_CHALLENGE_LEN
,
640 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
641 payload_len
= 2+4+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
;
643 if (onion_skin_create(hop
->extend_info
->onion_key
,
644 &(hop
->dh_handshake_state
), onionskin
) < 0) {
645 log_warn(LD_CIRC
,"onion_skin_create failed.");
646 return - END_CIRC_REASON_INTERNAL
;
649 log_debug(LD_CIRC
,"Sending extend relay cell.");
650 /* send it to hop->prev, because it will transfer
651 * it to a create cell and then send to hop */
652 if (connection_edge_send_command(NULL
, TO_CIRCUIT(circ
),
653 RELAY_COMMAND_EXTEND
,
654 payload
, payload_len
, hop
->prev
) < 0)
655 return 0; /* circuit is closed */
657 hop
->state
= CPATH_STATE_AWAITING_KEYS
;
662 /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
663 * something has also gone wrong with our network: notify the user,
664 * and abandon all not-yet-used circuits. */
666 circuit_note_clock_jumped(int seconds_elapsed
)
668 int severity
= server_mode(get_options()) ? LOG_WARN
: LOG_NOTICE
;
669 log(severity
, LD_GENERAL
, "Your clock just jumped %d seconds %s; "
670 "assuming established circuits no longer work.",
671 seconds_elapsed
>=0 ? seconds_elapsed
: -seconds_elapsed
,
672 seconds_elapsed
>=0 ? "forward" : "backward");
673 control_event_general_status(LOG_WARN
, "CLOCK_JUMPED TIME=%d",
675 has_completed_circuit
=0; /* so it'll log when it works again */
676 control_event_client_status(severity
, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
678 circuit_mark_all_unused_circs();
679 circuit_expire_all_dirty_circs();
682 /** Take the 'extend' cell, pull out addr/port plus the onion skin. Make
683 * sure we're connected to the next hop, and pass it the onion skin using
684 * a create cell. Return -1 if we want to warn and tear down the circuit,
688 circuit_extend(cell_t
*cell
, circuit_t
*circ
)
690 or_connection_t
*n_conn
;
693 char *id_digest
=NULL
;
696 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
697 "n_conn already set. Bug/attack. Closing.");
701 if (!server_mode(get_options())) {
702 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
703 "Got an extend cell, but running as a client. Closing.");
707 relay_header_unpack(&rh
, cell
->payload
);
709 if (rh
.length
< 4+2+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
) {
710 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
711 "Wrong length %d on extend cell. Closing circuit.",
716 circ
->n_addr
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
));
717 circ
->n_port
= ntohs(get_uint16(cell
->payload
+RELAY_HEADER_SIZE
+4));
719 onionskin
= cell
->payload
+RELAY_HEADER_SIZE
+4+2;
720 id_digest
= cell
->payload
+RELAY_HEADER_SIZE
+4+2+ONIONSKIN_CHALLENGE_LEN
;
721 n_conn
= connection_or_get_by_identity_digest(id_digest
);
723 /* If we don't have an open conn, or the conn we have is obsolete
724 * (i.e. old or broken) and the other side will let us make a second
725 * connection without dropping it immediately... */
726 if (!n_conn
|| n_conn
->_base
.state
!= OR_CONN_STATE_OPEN
||
727 (n_conn
->_base
.or_is_obsolete
&&
728 router_digest_version_as_new_as(id_digest
,"0.1.1.9-alpha-cvs"))) {
730 char tmpbuf
[INET_NTOA_BUF_LEN
];
731 in
.s_addr
= htonl(circ
->n_addr
);
732 tor_inet_ntoa(&in
,tmpbuf
,sizeof(tmpbuf
));
733 log_info(LD_CIRC
|LD_OR
,"Next router (%s:%d) not connected. Connecting.",
734 tmpbuf
, circ
->n_port
);
736 circ
->onionskin
= tor_malloc(ONIONSKIN_CHALLENGE_LEN
);
737 memcpy(circ
->onionskin
, onionskin
, ONIONSKIN_CHALLENGE_LEN
);
738 circuit_set_state(circ
, CIRCUIT_STATE_OR_WAIT
);
740 /* imprint the circuit with its future n_conn->id */
741 memcpy(circ
->n_conn_id_digest
, id_digest
, DIGEST_LEN
);
743 if (n_conn
&& !n_conn
->_base
.or_is_obsolete
) {
744 circ
->n_addr
= n_conn
->_base
.addr
;
745 circ
->n_port
= n_conn
->_base
.port
;
747 /* we should try to open a connection */
748 n_conn
= connection_or_connect(circ
->n_addr
, circ
->n_port
, id_digest
);
750 log_info(LD_CIRC
,"Launching n_conn failed. Closing circuit.");
751 circuit_mark_for_close(circ
, END_CIRC_REASON_CONNECTFAILED
);
754 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
756 /* return success. The onion/circuit/etc will be taken care of
757 * automatically (may already have been) whenever n_conn reaches
758 * OR_CONN_STATE_OPEN.
763 /* these may be different if the router connected to us from elsewhere */
764 circ
->n_addr
= n_conn
->_base
.addr
;
765 circ
->n_port
= n_conn
->_base
.port
;
767 circ
->n_conn
= n_conn
;
768 memcpy(circ
->n_conn_id_digest
, n_conn
->identity_digest
, DIGEST_LEN
);
769 log_debug(LD_CIRC
,"n_conn is %s:%u",
770 n_conn
->_base
.address
,n_conn
->_base
.port
);
772 if (circuit_deliver_create_cell(circ
, CELL_CREATE
, onionskin
) < 0)
777 /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
778 * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
780 * - 20 to initialize f_digest
781 * - 20 to initialize b_digest
782 * - 16 to key f_crypto
783 * - 16 to key b_crypto
785 * (If 'reverse' is true, then f_XX and b_XX are swapped.)
788 circuit_init_cpath_crypto(crypt_path_t
*cpath
, const char *key_data
,
791 crypto_digest_env_t
*tmp_digest
;
792 crypto_cipher_env_t
*tmp_crypto
;
795 tor_assert(key_data
);
796 tor_assert(!(cpath
->f_crypto
|| cpath
->b_crypto
||
797 cpath
->f_digest
|| cpath
->b_digest
));
799 cpath
->f_digest
= crypto_new_digest_env();
800 crypto_digest_add_bytes(cpath
->f_digest
, key_data
, DIGEST_LEN
);
801 cpath
->b_digest
= crypto_new_digest_env();
802 crypto_digest_add_bytes(cpath
->b_digest
, key_data
+DIGEST_LEN
, DIGEST_LEN
);
804 if (!(cpath
->f_crypto
=
805 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
),1))) {
806 log_warn(LD_BUG
,"Bug: forward cipher initialization failed.");
809 if (!(cpath
->b_crypto
=
810 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
)+CIPHER_KEY_LEN
,0))) {
811 log_warn(LD_BUG
,"Bug: backward cipher initialization failed.");
816 tmp_digest
= cpath
->f_digest
;
817 cpath
->f_digest
= cpath
->b_digest
;
818 cpath
->b_digest
= tmp_digest
;
819 tmp_crypto
= cpath
->f_crypto
;
820 cpath
->f_crypto
= cpath
->b_crypto
;
821 cpath
->b_crypto
= tmp_crypto
;
827 /** A created or extended cell came back to us on the circuit, and it included
828 * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body
829 * contains (the second DH key, plus KH). If <b>reply_type</b> is
830 * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
832 * Calculate the appropriate keys and digests, make sure KH is
833 * correct, and initialize this hop of the cpath.
835 * Return - reason if we want to mark circ for close, else return 0.
838 circuit_finish_handshake(origin_circuit_t
*circ
, uint8_t reply_type
,
841 char keys
[CPATH_KEY_MATERIAL_LEN
];
844 if (circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
)
847 hop
= onion_next_hop_in_cpath(circ
->cpath
);
848 if (!hop
) { /* got an extended when we're all done? */
849 log_warn(LD_PROTOCOL
,"got extended when circ already built? Closing.");
850 return - END_CIRC_REASON_TORPROTOCOL
;
853 tor_assert(hop
->state
== CPATH_STATE_AWAITING_KEYS
);
855 if (reply_type
== CELL_CREATED
&& hop
->dh_handshake_state
) {
856 if (onion_skin_client_handshake(hop
->dh_handshake_state
, reply
, keys
,
857 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
858 log_warn(LD_CIRC
,"onion_skin_client_handshake failed.");
859 return -END_CIRC_REASON_TORPROTOCOL
;
861 /* Remember hash of g^xy */
862 memcpy(hop
->handshake_digest
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
863 } else if (reply_type
== CELL_CREATED_FAST
&& !hop
->dh_handshake_state
) {
864 if (fast_client_handshake(hop
->fast_handshake_state
, reply
, keys
,
865 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
866 log_warn(LD_CIRC
,"fast_client_handshake failed.");
867 return -END_CIRC_REASON_TORPROTOCOL
;
869 memcpy(hop
->handshake_digest
, reply
+DIGEST_LEN
, DIGEST_LEN
);
871 log_warn(LD_PROTOCOL
,"CREATED cell type did not match CREATE cell type.");
872 return -END_CIRC_REASON_TORPROTOCOL
;
875 if (hop
->dh_handshake_state
) {
876 crypto_dh_free(hop
->dh_handshake_state
); /* don't need it anymore */
877 hop
->dh_handshake_state
= NULL
;
879 memset(hop
->fast_handshake_state
, 0, sizeof(hop
->fast_handshake_state
));
881 if (circuit_init_cpath_crypto(hop
, keys
, 0)<0) {
882 return -END_CIRC_REASON_TORPROTOCOL
;
885 hop
->state
= CPATH_STATE_OPEN
;
886 log_info(LD_CIRC
,"Finished building %scircuit hop:",
887 (reply_type
== CELL_CREATED_FAST
) ? "fast " : "");
888 circuit_log_path(LOG_INFO
,LD_CIRC
,circ
);
889 control_event_circuit_status(circ
, CIRC_EVENT_EXTENDED
, 0);
894 /** We received a relay truncated cell on circ.
896 * Since we don't ask for truncates currently, getting a truncated
897 * means that a connection broke or an extend failed. For now,
898 * just give up: for circ to close, and return 0.
901 circuit_truncated(origin_circuit_t
*circ
, crypt_path_t
*layer
)
903 // crypt_path_t *victim;
904 // connection_t *stream;
909 /* XXX Since we don't ask for truncates currently, getting a truncated
910 * means that a connection broke or an extend failed. For now,
913 circuit_mark_for_close(TO_CIRCUIT(circ
),
914 END_CIRC_REASON_FLAG_REMOTE
|END_CIRC_REASON_OR_CONN_CLOSED
);
918 while (layer
->next
!= circ
->cpath
) {
919 /* we need to clear out layer->next */
920 victim
= layer
->next
;
921 log_debug(LD_CIRC
, "Killing a layer of the cpath.");
923 for (stream
= circ
->p_streams
; stream
; stream
=stream
->next_stream
) {
924 if (stream
->cpath_layer
== victim
) {
925 log_info(LD_APP
, "Marking stream %d for close because of truncate.",
927 /* no need to send 'end' relay cells,
928 * because the other side's already dead
930 connection_mark_unattached_ap(stream
, END_STREAM_REASON_DESTROY
);
934 layer
->next
= victim
->next
;
935 circuit_free_cpath_node(victim
);
938 log_info(LD_CIRC
, "finished");
943 /** Given a response payload and keys, initialize, then send a created
947 onionskin_answer(or_circuit_t
*circ
, uint8_t cell_type
, const char *payload
,
951 crypt_path_t
*tmp_cpath
;
953 tmp_cpath
= tor_malloc_zero(sizeof(crypt_path_t
));
954 tmp_cpath
->magic
= CRYPT_PATH_MAGIC
;
956 memset(&cell
, 0, sizeof(cell_t
));
957 cell
.command
= cell_type
;
958 cell
.circ_id
= circ
->p_circ_id
;
960 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
962 memcpy(cell
.payload
, payload
,
963 cell_type
== CELL_CREATED
? ONIONSKIN_REPLY_LEN
: DIGEST_LEN
*2);
965 log_debug(LD_CIRC
,"init digest forward 0x%.8x, backward 0x%.8x.",
966 (unsigned int)*(uint32_t*)(keys
),
967 (unsigned int)*(uint32_t*)(keys
+20));
968 if (circuit_init_cpath_crypto(tmp_cpath
, keys
, 0)<0) {
969 log_warn(LD_BUG
,"Circuit initialization failed");
973 circ
->n_digest
= tmp_cpath
->f_digest
;
974 circ
->n_crypto
= tmp_cpath
->f_crypto
;
975 circ
->p_digest
= tmp_cpath
->b_digest
;
976 circ
->p_crypto
= tmp_cpath
->b_crypto
;
977 tmp_cpath
->magic
= 0;
980 if (cell_type
== CELL_CREATED
)
981 memcpy(circ
->handshake_digest
, cell
.payload
+DH_KEY_LEN
, DIGEST_LEN
);
983 memcpy(circ
->handshake_digest
, cell
.payload
+DIGEST_LEN
, DIGEST_LEN
);
985 circ
->is_first_hop
= (cell_type
== CELL_CREATED_FAST
);
987 connection_or_write_cell_to_buf(&cell
, circ
->p_conn
);
988 log_debug(LD_CIRC
,"Finished sending 'created' cell.");
990 if (!is_local_IP(circ
->p_conn
->_base
.addr
) &&
991 !connection_or_nonopen_was_started_here(circ
->p_conn
)) {
992 /* record that we could process create cells from a non-local conn
993 * that we didn't initiate; presumably this means that create cells
994 * can reach us too. */
995 router_orport_found_reachable();
1001 /** Choose a length for a circuit of purpose <b>purpose</b>.
1002 * Default length is 3 + the number of endpoints that would give something
1003 * away. If the routerlist <b>routers</b> doesn't have enough routers
1004 * to handle the desired path length, return as large a path length as
1005 * is feasible, except if it's less than 2, in which case return -1.
1008 new_route_len(uint8_t purpose
, extend_info_t
*exit
,
1009 smartlist_t
*routers
)
1011 int num_acceptable_routers
;
1014 tor_assert(routers
);
1021 purpose
!= CIRCUIT_PURPOSE_TESTING
&&
1022 purpose
!= CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
)
1025 log_debug(LD_CIRC
,"Chosen route length %d (%d routers available).",
1026 routelen
, smartlist_len(routers
));
1028 num_acceptable_routers
= count_acceptable_routers(routers
);
1030 if (num_acceptable_routers
< 2) {
1032 "Not enough acceptable routers (%d). Discarding this circuit.",
1033 num_acceptable_routers
);
1037 if (num_acceptable_routers
< routelen
) {
1038 log_info(LD_CIRC
,"Not enough routers: cutting routelen from %d to %d.",
1039 routelen
, num_acceptable_routers
);
1040 routelen
= num_acceptable_routers
;
1046 /** Fetch the list of predicted ports, dup it into a smartlist of
1047 * uint16_t's, remove the ones that are already handled by an
1048 * existing circuit, and return it.
1050 static smartlist_t
*
1051 circuit_get_unhandled_ports(time_t now
)
1053 smartlist_t
*source
= rep_hist_get_predicted_ports(now
);
1054 smartlist_t
*dest
= smartlist_create();
1058 for (i
= 0; i
< smartlist_len(source
); ++i
) {
1059 tmp
= tor_malloc(sizeof(uint16_t));
1060 memcpy(tmp
, smartlist_get(source
, i
), sizeof(uint16_t));
1061 smartlist_add(dest
, tmp
);
1064 circuit_remove_handled_ports(dest
);
1068 /** Return 1 if we already have circuits present or on the way for
1069 * all anticipated ports. Return 0 if we should make more.
1071 * If we're returning 0, set need_uptime and need_capacity to
1072 * indicate any requirements that the unhandled ports have.
1075 circuit_all_predicted_ports_handled(time_t now
, int *need_uptime
,
1080 smartlist_t
*sl
= circuit_get_unhandled_ports(now
);
1081 smartlist_t
*LongLivedServices
= get_options()->LongLivedPorts
;
1082 tor_assert(need_uptime
);
1083 tor_assert(need_capacity
);
1084 enough
= (smartlist_len(sl
) == 0);
1085 for (i
= 0; i
< smartlist_len(sl
); ++i
) {
1086 port
= smartlist_get(sl
, i
);
1087 if (smartlist_string_num_isin(LongLivedServices
, *port
))
1095 /** Return 1 if <b>router</b> can handle one or more of the ports in
1096 * <b>needed_ports</b>, else return 0.
1099 router_handles_some_port(routerinfo_t
*router
, smartlist_t
*needed_ports
)
1104 for (i
= 0; i
< smartlist_len(needed_ports
); ++i
) {
1105 addr_policy_result_t r
;
1106 port
= *(uint16_t *)smartlist_get(needed_ports
, i
);
1108 r
= compare_addr_to_addr_policy(0, port
, router
->exit_policy
);
1109 if (r
!= ADDR_POLICY_REJECTED
&& r
!= ADDR_POLICY_PROBABLY_REJECTED
)
1115 /** Return true iff <b>conn</b> is waiting for a general circuit to be
1118 ap_stream_wants_exit_attention(connection_t
*conn
)
1120 if (conn
->type
== CONN_TYPE_AP
&&
1121 conn
->state
== AP_CONN_STATE_CIRCUIT_WAIT
&&
1122 !conn
->marked_for_close
&&
1123 !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn
)) &&
1124 !circuit_stream_is_being_handled(TO_EDGE_CONN(conn
), 0,
1125 MIN_CIRCUITS_HANDLING_STREAM
))
1130 /** Return a pointer to a suitable router to be the exit node for the
1131 * general-purpose circuit we're about to build.
1133 * Look through the connection array, and choose a router that maximizes
1134 * the number of pending streams that can exit from this router.
1136 * Return NULL if we can't find any suitable routers.
1138 static routerinfo_t
*
1139 choose_good_exit_server_general(routerlist_t
*dir
, int need_uptime
,
1144 int n_pending_connections
= 0;
1145 connection_t
**carray
;
1147 int best_support
= -1;
1148 int n_best_support
=0;
1149 smartlist_t
*sl
, *preferredexits
, *excludedexits
;
1150 routerinfo_t
*router
;
1151 or_options_t
*options
= get_options();
1153 get_connection_array(&carray
, &n_connections
);
1155 /* Count how many connections are waiting for a circuit to be built.
1156 * We use this for log messages now, but in the future we may depend on it.
1158 for (i
= 0; i
< n_connections
; ++i
) {
1159 if (ap_stream_wants_exit_attention(carray
[i
]))
1160 ++n_pending_connections
;
1162 // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
1163 // n_pending_connections);
1164 /* Now we count, for each of the routers in the directory, how many
1165 * of the pending connections could possibly exit from that
1166 * router (n_supported[i]). (We can't be sure about cases where we
1167 * don't know the IP address of the pending connection.)
1169 n_supported
= tor_malloc(sizeof(int)*smartlist_len(dir
->routers
));
1170 for (i
= 0; i
< smartlist_len(dir
->routers
); ++i
) {/* iterate over routers */
1171 router
= smartlist_get(dir
->routers
, i
);
1172 if (router_is_me(router
)) {
1173 n_supported
[i
] = -1;
1174 // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
1175 /* XXX there's probably a reverse predecessor attack here, but
1176 * it's slow. should we take this out? -RD
1180 if (!router
->is_running
|| router
->is_bad_exit
) {
1181 n_supported
[i
] = -1;
1182 continue; /* skip routers that are known to be down or bad exits */
1184 if (router_is_unreliable(router
, need_uptime
, need_capacity
, 0)) {
1185 n_supported
[i
] = -1;
1186 continue; /* skip routers that are not suitable */
1188 if (!(router
->is_valid
|| options
->_AllowInvalid
& ALLOW_INVALID_EXIT
)) {
1189 /* if it's invalid and we don't want it */
1190 n_supported
[i
] = -1;
1191 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
1192 // router->nickname, i);
1193 continue; /* skip invalid routers */
1195 if (router_exit_policy_rejects_all(router
)) {
1196 n_supported
[i
] = -1;
1197 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
1198 // router->nickname, i);
1199 continue; /* skip routers that reject all */
1202 for (j
= 0; j
< n_connections
; ++j
) { /* iterate over connections */
1203 if (!ap_stream_wants_exit_attention(carray
[j
]))
1204 continue; /* Skip everything but APs in CIRCUIT_WAIT */
1205 if (connection_ap_can_use_exit(TO_EDGE_CONN(carray
[j
]), router
)) {
1207 // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
1208 // router->nickname, i, n_supported[i]);
1210 // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
1211 // router->nickname, i);
1213 } /* End looping over connections. */
1214 if (n_supported
[i
] > best_support
) {
1215 /* If this router is better than previous ones, remember its index
1216 * and goodness, and start counting how many routers are this good. */
1217 best_support
= n_supported
[i
]; n_best_support
=1;
1218 // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
1219 // router->nickname);
1220 } else if (n_supported
[i
] == best_support
) {
1221 /* If this router is _as good_ as the best one, just increment the
1222 * count of equally good routers.*/
1227 "Found %d servers that might support %d/%d pending connections.",
1228 n_best_support
, best_support
>= 0 ? best_support
: 0,
1229 n_pending_connections
);
1231 preferredexits
= smartlist_create();
1232 add_nickname_list_to_smartlist(preferredexits
,options
->ExitNodes
,1);
1234 excludedexits
= smartlist_create();
1235 add_nickname_list_to_smartlist(excludedexits
,options
->ExcludeNodes
,0);
1237 sl
= smartlist_create();
1239 /* If any routers definitely support any pending connections, choose one
1241 if (best_support
> 0) {
1242 for (i
= 0; i
< smartlist_len(dir
->routers
); i
++)
1243 if (n_supported
[i
] == best_support
)
1244 smartlist_add(sl
, smartlist_get(dir
->routers
, i
));
1246 smartlist_subtract(sl
,excludedexits
);
1247 if (options
->StrictExitNodes
|| smartlist_overlap(sl
,preferredexits
))
1248 smartlist_intersect(sl
,preferredexits
);
1249 router
= routerlist_sl_choose_by_bandwidth(sl
, 1);
1251 /* Either there are no pending connections, or no routers even seem to
1252 * possibly support any of them. Choose a router at random that satisfies
1253 * at least one predicted exit port. */
1256 smartlist_t
*needed_ports
= circuit_get_unhandled_ports(time(NULL
));
1258 if (best_support
== -1) {
1259 if (need_uptime
|| need_capacity
) {
1261 "We couldn't find any live%s%s routers; falling back "
1262 "to list of all routers.",
1263 need_capacity
?", fast":"",
1264 need_uptime
?", stable":"");
1265 smartlist_free(preferredexits
);
1266 smartlist_free(excludedexits
);
1268 tor_free(n_supported
);
1269 return choose_good_exit_server_general(dir
, 0, 0);
1271 log_notice(LD_CIRC
, "All routers are down or won't exit -- choosing a "
1272 "doomed exit at random.");
1274 for (try = 0; try < 2; try++) {
1275 /* try once to pick only from routers that satisfy a needed port,
1276 * then if there are none, pick from any that support exiting. */
1277 for (i
= 0; i
< smartlist_len(dir
->routers
); i
++) {
1278 router
= smartlist_get(dir
->routers
, i
);
1279 if (n_supported
[i
] != -1 &&
1280 (try || router_handles_some_port(router
, needed_ports
))) {
1281 // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
1282 // try, router->nickname);
1283 smartlist_add(sl
, router
);
1287 smartlist_subtract(sl
,excludedexits
);
1288 if (options
->StrictExitNodes
|| smartlist_overlap(sl
,preferredexits
))
1289 smartlist_intersect(sl
,preferredexits
);
1290 /* XXX sometimes the above results in null, when the requested
1291 * exit node is down. we should pick it anyway. */
1292 router
= routerlist_sl_choose_by_bandwidth(sl
, 1);
1296 SMARTLIST_FOREACH(needed_ports
, uint16_t *, cp
, tor_free(cp
));
1297 smartlist_free(needed_ports
);
1300 smartlist_free(preferredexits
);
1301 smartlist_free(excludedexits
);
1303 tor_free(n_supported
);
1305 log_info(LD_CIRC
, "Chose exit server '%s'", router
->nickname
);
1308 if (options
->StrictExitNodes
) {
1310 "No specified exit routers seem to be running, and "
1311 "StrictExitNodes is set: can't choose an exit.");
1316 /** Return a pointer to a suitable router to be the exit node for the
1317 * circuit of purpose <b>purpose</b> that we're about to build (or NULL
1318 * if no router is suitable).
1320 * For general-purpose circuits, pass it off to
1321 * choose_good_exit_server_general()
1323 * For client-side rendezvous circuits, choose a random node, weighted
1324 * toward the preferences in 'options'.
1326 static routerinfo_t
*
1327 choose_good_exit_server(uint8_t purpose
, routerlist_t
*dir
,
1328 int need_uptime
, int need_capacity
, int is_internal
)
1330 or_options_t
*options
= get_options();
1332 case CIRCUIT_PURPOSE_C_GENERAL
:
1333 if (is_internal
) /* pick it like a middle hop */
1334 return router_choose_random_node(NULL
, get_options()->ExcludeNodes
,
1335 NULL
, need_uptime
, need_capacity
, 0,
1336 get_options()->_AllowInvalid
& ALLOW_INVALID_MIDDLE
, 0, 0);
1338 return choose_good_exit_server_general(dir
,need_uptime
,need_capacity
);
1339 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
1340 return router_choose_random_node(
1341 options
->RendNodes
, options
->RendExcludeNodes
,
1342 NULL
, need_uptime
, need_capacity
, 0,
1343 options
->_AllowInvalid
& ALLOW_INVALID_RENDEZVOUS
, 0, 0);
1345 log_warn(LD_BUG
,"Bug: unhandled purpose %d", purpose
);
1346 tor_fragile_assert();
1350 /** Decide a suitable length for circ's cpath, and pick an exit
1351 * router (or use <b>exit</b> if provided). Store these in the
1352 * cpath. Return 0 if ok, -1 if circuit should be closed. */
1354 onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
1356 cpath_build_state_t
*state
= circ
->build_state
;
1357 routerlist_t
*rl
= router_get_routerlist();
1359 if (state
->onehop_tunnel
) {
1360 log_debug(LD_CIRC
, "Launching a one-hop circuit for dir tunnel.");
1361 state
->desired_path_len
= 1;
1363 int r
= new_route_len(circ
->_base
.purpose
, exit
, rl
->routers
);
1364 if (r
< 1) /* must be at least 1 */
1366 state
->desired_path_len
= r
;
1369 if (exit
) { /* the circuit-builder pre-requested one */
1370 log_info(LD_CIRC
,"Using requested exit node '%s'", exit
->nickname
);
1371 exit
= extend_info_dup(exit
);
1372 } else { /* we have to decide one */
1373 routerinfo_t
*router
=
1374 choose_good_exit_server(circ
->_base
.purpose
, rl
, state
->need_uptime
,
1375 state
->need_capacity
, state
->is_internal
);
1377 log_warn(LD_CIRC
,"failed to choose an exit server");
1380 exit
= extend_info_from_router(router
);
1382 state
->chosen_exit
= exit
;
1386 /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
1387 * hop to the cpath reflecting this. Don't send the next extend cell --
1388 * the caller will do this if it wants to.
1391 circuit_append_new_exit(origin_circuit_t
*circ
, extend_info_t
*info
)
1393 cpath_build_state_t
*state
;
1397 state
= circ
->build_state
;
1399 if (state
->chosen_exit
)
1400 extend_info_free(state
->chosen_exit
);
1401 state
->chosen_exit
= extend_info_dup(info
);
1403 ++circ
->build_state
->desired_path_len
;
1404 onion_append_hop(&circ
->cpath
, info
);
1408 /** Take an open <b>circ</b>, and add a new hop at the end, based on
1409 * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
1410 * send the next extend cell to begin connecting to that hop.
1413 circuit_extend_to_new_exit(origin_circuit_t
*circ
, extend_info_t
*info
)
1416 circuit_append_new_exit(circ
, info
);
1417 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
1418 if ((err_reason
= circuit_send_next_onion_skin(circ
))<0) {
1419 log_warn(LD_CIRC
, "Couldn't extend circuit to new point '%s'.",
1421 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
1427 /** Return the number of routers in <b>routers</b> that are currently up
1428 * and available for building circuits through.
1431 count_acceptable_routers(smartlist_t
*routers
)
1437 n
= smartlist_len(routers
);
1439 r
= smartlist_get(routers
, i
);
1440 // log_debug(LD_CIRC,
1441 // "Contemplating whether router %d (%s) is a new option.",
1443 if (r
->is_running
== 0) {
1444 // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
1447 if (r
->is_valid
== 0) {
1448 // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
1450 /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
1451 * allows this node in some places, then we're getting an inaccurate
1452 * count. For now, be conservative and don't count it. But later we
1453 * should try to be smarter. */
1456 // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
1458 ; /* C requires an explicit statement after the label */
1464 /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
1465 * This function is used to extend cpath by another hop.
1468 onion_append_to_cpath(crypt_path_t
**head_ptr
, crypt_path_t
*new_hop
)
1471 new_hop
->next
= (*head_ptr
);
1472 new_hop
->prev
= (*head_ptr
)->prev
;
1473 (*head_ptr
)->prev
->next
= new_hop
;
1474 (*head_ptr
)->prev
= new_hop
;
1476 *head_ptr
= new_hop
;
1477 new_hop
->prev
= new_hop
->next
= new_hop
;
1481 /** Pick a random server digest that's running a Tor version that
1482 * doesn't have the reachability bug. These are versions 0.1.1.21-cvs+
1483 * and 0.1.2.1-alpha+. Avoid picking authorities, since we're
1484 * probably already connected to them.
1486 * We only return one, so this doesn't become stupid when the
1487 * whole network has upgraded. */
1489 compute_preferred_testing_list(const char *answer
)
1491 smartlist_t
*choices
;
1492 routerlist_t
*rl
= router_get_routerlist();
1493 routerinfo_t
*router
;
1496 if (answer
) /* they have one in mind -- easy */
1497 return tor_strdup(answer
);
1499 choices
= smartlist_create();
1500 /* now count up our choices */
1501 SMARTLIST_FOREACH(rl
->routers
, routerinfo_t
*, r
,
1502 if (r
->is_running
&& r
->is_valid
&&
1503 ((tor_version_as_new_as(r
->platform
,"0.1.1.21-cvs") &&
1504 !tor_version_as_new_as(r
->platform
,"0.1.2.0-alpha-cvs")) ||
1505 tor_version_as_new_as(r
->platform
,"0.1.2.1-alpha")) &&
1506 !is_local_IP(r
->addr
) &&
1507 !router_get_trusteddirserver_by_digest(r
->cache_info
.identity_digest
))
1508 smartlist_add(choices
, r
));
1509 router
= smartlist_choose(choices
);
1510 smartlist_free(choices
);
1512 log_info(LD_CIRC
, "Looking for middle server that doesn't have the "
1513 "reachability bug, but didn't find one. Oh well.");
1516 log_info(LD_CIRC
, "Looking for middle server that doesn't have the "
1517 "reachability bug, and chose '%s'. Great.", router
->nickname
);
1518 s
= tor_malloc(HEX_DIGEST_LEN
+2);
1520 base16_encode(s
+1, HEX_DIGEST_LEN
+1,
1521 router
->cache_info
.identity_digest
, DIGEST_LEN
);
1525 /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
1526 * and <b>state</b> and the cpath <b>head</b> (currently populated only
1527 * to length <b>cur_len</b> to decide a suitable middle hop for a
1528 * circuit. In particular, make sure we don't pick the exit node or its
1529 * family, and make sure we don't duplicate any previous nodes or their
1531 static routerinfo_t
*
1532 choose_good_middle_server(uint8_t purpose
,
1533 cpath_build_state_t
*state
,
1538 routerinfo_t
*r
, *choice
;
1539 crypt_path_t
*cpath
;
1540 smartlist_t
*excluded
;
1541 or_options_t
*options
= get_options();
1542 char *preferred
= NULL
;
1543 tor_assert(_CIRCUIT_PURPOSE_MIN
<= purpose
&&
1544 purpose
<= _CIRCUIT_PURPOSE_MAX
);
1546 log_debug(LD_CIRC
, "Contemplating intermediate hop: random choice.");
1547 excluded
= smartlist_create();
1548 if ((r
= build_state_get_exit_router(state
))) {
1549 smartlist_add(excluded
, r
);
1550 routerlist_add_family(excluded
, r
);
1552 if ((r
= routerlist_find_my_routerinfo())) {
1553 smartlist_add(excluded
, r
);
1554 routerlist_add_family(excluded
, r
);
1556 for (i
= 0, cpath
= head
; i
< cur_len
; ++i
, cpath
=cpath
->next
) {
1557 if ((r
= router_get_by_digest(cpath
->extend_info
->identity_digest
))) {
1558 smartlist_add(excluded
, r
);
1559 routerlist_add_family(excluded
, r
);
1562 if (purpose
== CIRCUIT_PURPOSE_TESTING
)
1563 preferred
= compute_preferred_testing_list(options
->TestVia
);
1564 choice
= router_choose_random_node(preferred
,
1565 options
->ExcludeNodes
, excluded
,
1566 state
->need_uptime
, state
->need_capacity
, 0,
1567 options
->_AllowInvalid
& ALLOW_INVALID_MIDDLE
, 0, 0);
1569 tor_free(preferred
);
1570 smartlist_free(excluded
);
1574 /** Pick a good entry server for the circuit to be built according to
1575 * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
1576 * router (if we're an OR), and respect firewall settings; if we're
1577 * using entry_guards, return one.
1579 * If <b>state</b> is NULL, we're choosing routers to serve as entry
1580 * nodes, not for any particular circuit.
1582 static routerinfo_t
*
1583 choose_good_entry_server(uint8_t purpose
, cpath_build_state_t
*state
)
1585 routerinfo_t
*r
, *choice
;
1586 smartlist_t
*excluded
;
1587 or_options_t
*options
= get_options();
1588 (void)purpose
; /* not used yet. */
1590 if (state
&& options
->UseEntryGuards
) {
1591 return choose_random_entry(state
);
1594 excluded
= smartlist_create();
1596 if (state
&& (r
= build_state_get_exit_router(state
))) {
1597 smartlist_add(excluded
, r
);
1598 routerlist_add_family(excluded
, r
);
1600 if ((r
= routerlist_find_my_routerinfo())) {
1601 smartlist_add(excluded
, r
);
1602 routerlist_add_family(excluded
, r
);
1604 if (firewall_is_fascist_or()) {
1605 /* exclude all ORs that listen on the wrong port */
1606 routerlist_t
*rl
= router_get_routerlist();
1609 for (i
=0; i
< smartlist_len(rl
->routers
); i
++) {
1610 r
= smartlist_get(rl
->routers
, i
);
1611 if (!fascist_firewall_allows_address_or(r
->addr
,r
->or_port
))
1612 smartlist_add(excluded
, r
);
1615 /* and exclude current entry guards, if applicable */
1616 if (options
->UseEntryGuards
&& entry_guards
) {
1617 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
1619 if ((r
= router_get_by_digest(entry
->identity
)))
1620 smartlist_add(excluded
, r
);
1624 choice
= router_choose_random_node(
1625 NULL
, options
->ExcludeNodes
,
1626 excluded
, state
? state
->need_uptime
: 0,
1627 state
? state
->need_capacity
: 0,
1629 options
->_AllowInvalid
& ALLOW_INVALID_ENTRY
, 0, 0);
1630 smartlist_free(excluded
);
1634 /** Return the first non-open hop in cpath, or return NULL if all
1636 static crypt_path_t
*
1637 onion_next_hop_in_cpath(crypt_path_t
*cpath
)
1639 crypt_path_t
*hop
= cpath
;
1641 if (hop
->state
!= CPATH_STATE_OPEN
)
1644 } while (hop
!= cpath
);
1648 /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
1649 * based on <b>state</b>. Append the hop info to head_ptr.
1652 onion_extend_cpath(origin_circuit_t
*circ
)
1654 uint8_t purpose
= circ
->_base
.purpose
;
1655 cpath_build_state_t
*state
= circ
->build_state
;
1656 int cur_len
= circuit_get_cpath_len(circ
);
1657 extend_info_t
*info
= NULL
;
1659 if (cur_len
>= state
->desired_path_len
) {
1660 log_debug(LD_CIRC
, "Path is complete: %d steps long",
1661 state
->desired_path_len
);
1665 log_debug(LD_CIRC
, "Path is %d long; we want %d", cur_len
,
1666 state
->desired_path_len
);
1668 if (cur_len
== state
->desired_path_len
- 1) { /* Picking last node */
1669 info
= extend_info_dup(state
->chosen_exit
);
1670 } else if (cur_len
== 0) { /* picking first node */
1671 routerinfo_t
*r
= choose_good_entry_server(purpose
, state
);
1673 info
= extend_info_from_router(r
);
1676 choose_good_middle_server(purpose
, state
, circ
->cpath
, cur_len
);
1678 info
= extend_info_from_router(r
);
1682 log_warn(LD_CIRC
,"Failed to find node for hop %d of our path. Discarding "
1683 "this circuit.", cur_len
);
1687 log_debug(LD_CIRC
,"Chose router %s for hop %d (exit is %s)",
1688 info
->nickname
, cur_len
+1, build_state_get_exit_nickname(state
));
1690 onion_append_hop(&circ
->cpath
, info
);
1691 extend_info_free(info
);
1695 /** Create a new hop, annotate it with information about its
1696 * corresponding router <b>choice</b>, and append it to the
1697 * end of the cpath <b>head_ptr</b>. */
1699 onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
)
1701 crypt_path_t
*hop
= tor_malloc_zero(sizeof(crypt_path_t
));
1703 /* link hop into the cpath, at the end. */
1704 onion_append_to_cpath(head_ptr
, hop
);
1706 hop
->magic
= CRYPT_PATH_MAGIC
;
1707 hop
->state
= CPATH_STATE_CLOSED
;
1709 hop
->extend_info
= extend_info_dup(choice
);
1711 hop
->package_window
= CIRCWINDOW_START
;
1712 hop
->deliver_window
= CIRCWINDOW_START
;
1717 /** Allocate and return a new extend_info_t that can be used to build a
1718 * circuit to or through the router <b>r</b>. */
1720 extend_info_from_router(routerinfo_t
*r
)
1722 extend_info_t
*info
;
1724 info
= tor_malloc_zero(sizeof(extend_info_t
));
1725 strlcpy(info
->nickname
, r
->nickname
, sizeof(info
->nickname
));
1726 memcpy(info
->identity_digest
, r
->cache_info
.identity_digest
, DIGEST_LEN
);
1727 info
->onion_key
= crypto_pk_dup_key(r
->onion_pkey
);
1728 info
->addr
= r
->addr
;
1729 info
->port
= r
->or_port
;
1733 /** Allocate and return a new extend_info_t that can be used to build a
1734 * circuit to or through the router <b>r</b>. */
1736 extend_info_from_routerstatus(routerstatus_t
*s
)
1738 extend_info_t
*info
;
1740 info
= tor_malloc_zero(sizeof(extend_info_t
));
1741 strlcpy(info
->nickname
, s
->nickname
, sizeof(info
->nickname
));
1742 memcpy(info
->identity_digest
, s
->identity_digest
, DIGEST_LEN
);
1743 info
->onion_key
= NULL
; /* routerstatus doesn't know this */
1744 info
->addr
= s
->addr
;
1745 info
->port
= s
->or_port
;
1749 /** Release storage held by an extend_info_t struct. */
1751 extend_info_free(extend_info_t
*info
)
1754 if (info
->onion_key
)
1755 crypto_free_pk_env(info
->onion_key
);
1759 /** Allocate and return a new extend_info_t with the same contents as
1762 extend_info_dup(extend_info_t
*info
)
1764 extend_info_t
*newinfo
;
1766 newinfo
= tor_malloc(sizeof(extend_info_t
));
1767 memcpy(newinfo
, info
, sizeof(extend_info_t
));
1768 if (info
->onion_key
)
1769 newinfo
->onion_key
= crypto_pk_dup_key(info
->onion_key
);
1771 newinfo
->onion_key
= NULL
;
1775 /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
1776 * If there is no chosen exit, or if we don't know the routerinfo_t for
1777 * the chosen exit, return NULL.
1780 build_state_get_exit_router(cpath_build_state_t
*state
)
1782 if (!state
|| !state
->chosen_exit
)
1784 return router_get_by_digest(state
->chosen_exit
->identity_digest
);
1787 /** Return the nickname for the chosen exit router in <b>state</b>. If
1788 * there is no chosen exit, or if we don't know the routerinfo_t for the
1789 * chosen exit, return NULL.
1792 build_state_get_exit_nickname(cpath_build_state_t
*state
)
1794 if (!state
|| !state
->chosen_exit
)
1796 return state
->chosen_exit
->nickname
;
1799 /** Check whether the entry guard <b>e</b> is usable, given the directory
1800 * authorities' opinion about the rouer (stored in <b>ri</b>) and the user's
1801 * configuration (in <b>options</b>). Set <b>e</b>->bad_since
1802 * accordingly. Return true iff the entry guard's status changes. */
1804 entry_guard_set_status(entry_guard_t
*e
, routerinfo_t
*ri
,
1805 time_t now
, or_options_t
*options
)
1807 const char *reason
= NULL
;
1808 char buf
[HEX_DIGEST_LEN
+1];
1811 tor_assert(options
);
1813 /* Do we want to mark this guard as bad? */
1815 reason
= "unlisted";
1816 else if (!ri
->is_running
)
1818 else if (!ri
->is_possible_guard
&&
1819 !router_nickname_is_in_list(ri
, options
->EntryNodes
))
1820 reason
= "not recommended as a guard";
1821 else if (router_nickname_is_in_list(ri
, options
->ExcludeNodes
))
1822 reason
= "excluded";
1824 if (reason
&& ! e
->bad_since
) {
1825 /* Router is newly bad. */
1826 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
1827 log_info(LD_CIRC
, "Entry guard %s (%s) is %s: marking as unusable.",
1828 e
->nickname
, buf
, reason
);
1831 control_event_guard(e
->nickname
, e
->identity
, "BAD");
1833 } else if (!reason
&& e
->bad_since
) {
1834 /* There's nothing wrong with the router any more. */
1835 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
1836 log_info(LD_CIRC
, "Entry guard %s (%s) is no longer unusable: "
1837 "marking as ok.", e
->nickname
, buf
);
1840 control_event_guard(e
->nickname
, e
->identity
, "GOOD");
1847 /** Return true iff enough time has passed since we last tried connect to the
1848 * unreachable guard <b>e</b> that we're willing to try again. */
1850 entry_is_time_to_retry(entry_guard_t
*e
, time_t now
)
1853 if (e
->last_attempted
< e
->unreachable_since
)
1855 diff
= now
- e
->unreachable_since
;
1857 return now
> (e
->last_attempted
+ 60*60);
1858 else if (diff
< 3*24*60*60)
1859 return now
> (e
->last_attempted
+ 4*60*60);
1860 else if (diff
< 7*24*60*60)
1861 return now
> (e
->last_attempted
+ 18*60*60);
1863 return now
> (e
->last_attempted
+ 36*60*60);
1866 /** Return the router corresponding to <b>e</b>, if <b>e</b> is
1867 * working well enough that we are willing to use it as an entry
1868 * right now. (Else return NULL.) In particular, it must be
1869 * - Listed as either up or never yet contacted;
1870 * - Present in the routerlist;
1871 * - Listed as 'stable' or 'fast' by the current dirserver concensus,
1872 * if demanded by <b>need_uptime</b> or <b>need_capacity</b>;
1873 * (This check is currently redundant with the Guard flag, but in
1874 * the future that might change. Best to leave it in for now.)
1875 * - Allowed by our current ReachableAddresses config option; and
1876 * - Currently thought to be reachable by us (unless assume_reachable
1879 static INLINE routerinfo_t
*
1880 entry_is_live(entry_guard_t
*e
, int need_uptime
, int need_capacity
,
1881 int assume_reachable
)
1886 /* no good if it's unreachable, unless assume_unreachable or can_retry. */
1887 if ((!assume_reachable
&& !e
->can_retry
) &&
1888 e
->unreachable_since
&& !entry_is_time_to_retry(e
, time(NULL
)))
1890 r
= router_get_by_digest(e
->identity
);
1893 if (router_is_unreliable(r
, need_uptime
, need_capacity
, 0))
1895 if (firewall_is_fascist_or() &&
1896 !fascist_firewall_allows_address_or(r
->addr
,r
->or_port
))
1901 /** Return the number of entry guards that we think are usable. */
1903 num_live_entry_guards(void)
1908 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
1910 if (entry_is_live(entry
, 0, 1, 0))
1916 /** Return 1 if <b>digest</b> matches the identity of any node
1917 * in the entry_guards list. Else return 0. */
1919 is_an_entry_guard(const char *digest
)
1921 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
1922 if (!memcmp(digest
, entry
->identity
, DIGEST_LEN
))
1928 /** Dump a description of our list of entry guards to the log at level
1929 * <b>severity</b>. */
1931 log_entry_guards(int severity
)
1933 smartlist_t
*elements
= smartlist_create();
1937 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
1939 tor_snprintf(buf
, sizeof(buf
), "%s (%s%s)",
1941 e
->bad_since
? "down " : "up ",
1942 e
->made_contact
? "made-contact" : "never-contacted");
1943 smartlist_add(elements
, tor_strdup(buf
));
1946 s
= smartlist_join_strings(elements
, ",", 0, NULL
);
1947 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
1948 smartlist_free(elements
);
1949 log_fn(severity
,LD_CIRC
,"%s",s
);
1953 /** Called when one or more guards that we would previously have used for some
1954 * purpose are no longer in use because a higher-priority guard has become
1957 control_event_guard_deferred(void)
1959 /* XXXX We don't actually have a good way to figure out _how many_ entries
1960 * are live for some purpose. We need an entry_is_even_slightly_live()
1961 * function for this to work right. NumEntryGuards isn't reliable: if we
1962 * need guards with weird properties, we can have more than that number
1967 or_options_t
*options
= get_options();
1970 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
1972 if (entry_is_live(entry
, 0, 1, 0)) {
1973 if (n
++ == options
->NumEntryGuards
) {
1974 control_event_guard(entry
->nickname
, entry
->identity
, "DEFERRED");
1982 /** Add a new (preferably stable and fast) router to our
1983 * entry_guards list. Return a pointer to the router if we succeed,
1984 * or NULL if we can't find any more suitable entries.
1986 * If <b>chosen</b> is defined, use that one, and if it's not
1987 * already in our entry_guards list, put it at the *beginning*.
1988 * Else, put the one we pick at the end of the list. */
1989 static routerinfo_t
*
1990 add_an_entry_guard(routerinfo_t
*chosen
)
1992 routerinfo_t
*router
;
1993 entry_guard_t
*entry
;
1997 if (is_an_entry_guard(router
->cache_info
.identity_digest
))
2000 router
= choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL
, NULL
);
2004 entry
= tor_malloc_zero(sizeof(entry_guard_t
));
2005 log_info(LD_CIRC
, "Chose '%s' as new entry guard.", router
->nickname
);
2006 strlcpy(entry
->nickname
, router
->nickname
, sizeof(entry
->nickname
));
2007 memcpy(entry
->identity
, router
->cache_info
.identity_digest
, DIGEST_LEN
);
2008 if (chosen
) /* prepend */
2009 smartlist_insert(entry_guards
, 0, entry
);
2011 smartlist_add(entry_guards
, entry
);
2012 control_event_guard(entry
->nickname
, entry
->identity
, "NEW");
2013 control_event_guard_deferred();
2014 log_entry_guards(LOG_INFO
);
2018 /** If the use of entry guards is configured, choose more entry guards
2019 * until we have enough in the list. */
2021 pick_entry_guards(void)
2023 or_options_t
*options
= get_options();
2026 tor_assert(entry_guards
);
2028 while (num_live_entry_guards() < options
->NumEntryGuards
) {
2029 if (!add_an_entry_guard(NULL
))
2034 entry_guards_changed();
2037 /** Release all storage held by the list of entry guards. */
2039 entry_guards_free_all(void)
2042 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, tor_free(e
));
2043 smartlist_free(entry_guards
);
2044 entry_guards
= NULL
;
2048 /** How long (in seconds) do we allow an entry guard to be nonfunctional,
2049 * unlisted, excluded, or otherwise nonusable before we give up on it? */
2050 #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
2052 /** Remove all entry guards that have been down or unlisted for so
2053 * long that we don't think they'll come up again. Return 1 if we
2054 * removed any, or 0 if we did nothing. */
2056 remove_dead_entries(void)
2058 char dbuf
[HEX_DIGEST_LEN
+1];
2059 char tbuf
[ISO_TIME_LEN
+1];
2060 time_t now
= time(NULL
);
2064 for (i
= 0; i
< smartlist_len(entry_guards
); ) {
2065 entry_guard_t
*entry
= smartlist_get(entry_guards
, i
);
2066 if (entry
->bad_since
&&
2067 entry
->bad_since
+ ENTRY_GUARD_REMOVE_AFTER
< now
) {
2069 base16_encode(dbuf
, sizeof(dbuf
), entry
->identity
, DIGEST_LEN
);
2070 format_local_iso_time(tbuf
, entry
->bad_since
);
2071 log_info(LD_CIRC
, "Entry guard '%s' (%s) has been down or unlisted "
2072 "since %s local time; removing.",
2073 entry
->nickname
, dbuf
, tbuf
);
2074 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
2076 smartlist_del_keeporder(entry_guards
, i
);
2077 log_entry_guards(LOG_INFO
);
2082 return changed
? 1 : 0;
2085 /** A new directory or router-status has arrived; update the down/listed
2086 * status of the entry guards.
2088 * An entry is 'down' if the directory lists it as nonrunning.
2089 * An entry is 'unlisted' if the directory doesn't include it.
2092 entry_guards_compute_status(void)
2094 /* Don't call this on startup; only on a fresh download. Otherwise we'll
2095 * think that things are unlisted. */
2098 int severity
= LOG_INFO
;
2099 or_options_t
*options
;
2103 options
= get_options();
2107 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
2109 routerinfo_t
*r
= router_get_by_digest(entry
->identity
);
2110 if (entry_guard_set_status(entry
, r
, now
, options
))
2113 log_info(LD_CIRC
, "Summary: Entry '%s' is %s, %s and %s.",
2115 entry
->unreachable_since
? "unreachable" : "reachable",
2116 entry
->bad_since
? "unusable" : "usable",
2117 entry_is_live(entry
, 0, 1, 0) ? "live" : "not live");
2120 if (remove_dead_entries())
2124 log_fn(severity
, LD_CIRC
, " (%d/%d entry guards are usable/new)",
2125 num_live_entry_guards(), smartlist_len(entry_guards
));
2126 log_entry_guards(LOG_INFO
);
2127 entry_guards_changed();
2131 /** Called when a connection to an OR with the identity digest <b>digest</b>
2132 * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0).
2133 * If the OR is an entry, change that entry's up/down status.
2134 * Return 0 normally, or -1 if we want to tear down the new connection.
2137 entry_guard_register_connect_status(const char *digest
, int succeeded
,
2141 int refuse_conn
= 0;
2142 int first_contact
= 0;
2143 entry_guard_t
*entry
= NULL
;
2145 char buf
[HEX_DIGEST_LEN
+1];
2150 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2152 if (!memcmp(e
->identity
, digest
, DIGEST_LEN
)) {
2162 base16_encode(buf
, sizeof(buf
), entry
->identity
, DIGEST_LEN
);
2165 if (entry
->unreachable_since
) {
2166 log_info(LD_CIRC
, "Entry guard '%s' (%s) is now reachable again. Good.",
2167 entry
->nickname
, buf
);
2168 entry
->can_retry
= 0;
2169 entry
->unreachable_since
= 0;
2170 entry
->last_attempted
= now
;
2171 control_event_guard(entry
->nickname
, entry
->identity
, "UP");
2174 if (!entry
->made_contact
) {
2175 entry
->made_contact
= 1;
2176 first_contact
= changed
= 1;
2178 } else { /* ! succeeded */
2179 if (!entry
->made_contact
) {
2180 /* We've never connected to this one. */
2182 "Connection to never-contacted entry guard '%s' (%s) failed. "
2183 "Removing from the list. %d/%d entry guards usable/new.",
2184 entry
->nickname
, buf
,
2185 num_live_entry_guards()-1, smartlist_len(entry_guards
)-1);
2187 smartlist_del_keeporder(entry_guards
, idx
);
2188 log_entry_guards(LOG_INFO
);
2190 } else if (!entry
->unreachable_since
) {
2191 log_info(LD_CIRC
, "Unable to connect to entry guard '%s' (%s). "
2192 "Marking as unreachable.", entry
->nickname
, buf
);
2193 entry
->unreachable_since
= entry
->last_attempted
= now
;
2194 control_event_guard(entry
->nickname
, entry
->identity
, "DOWN");
2197 char tbuf
[ISO_TIME_LEN
+1];
2198 format_iso_time(tbuf
, entry
->unreachable_since
);
2199 log_debug(LD_CIRC
, "Failed to connect to unreachable entry guard "
2200 "'%s' (%s). It has been unreachable since %s.",
2201 entry
->nickname
, buf
, tbuf
);
2202 entry
->last_attempted
= now
;
2204 entry
->can_retry
= 0; /* We gave it an early chance; no good. */
2207 if (first_contact
) {
2208 /* We've just added a new long-term entry guard. Perhaps the network just
2209 * came back? We should give our earlier entries another try too,
2210 * and close this connection so we don't use it before we've given
2211 * the others a shot. */
2212 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, {
2215 if (e
->made_contact
) {
2216 routerinfo_t
*r
= entry_is_live(e
, 0, 1, 1);
2217 if (r
&& e
->unreachable_since
) {
2225 "Connected to new entry guard '%s' (%s). Marking earlier "
2226 "entry guards up. %d/%d entry guards usable/new.",
2227 entry
->nickname
, buf
,
2228 num_live_entry_guards(), smartlist_len(entry_guards
));
2229 log_entry_guards(LOG_INFO
);
2235 entry_guards_changed();
2236 return refuse_conn
? -1 : 0;
2239 /** When we try to choose an entry guard, should we parse and add
2240 * config's EntryNodes first? */
2241 static int should_add_entry_nodes
= 0;
2243 /** Called when the value of EntryNodes changes in our configuration. */
2245 entry_nodes_should_be_added(void)
2247 log_info(LD_CIRC
, "New EntryNodes config option detected. Will use.");
2248 should_add_entry_nodes
= 1;
2251 /** Add all nodes in EntryNodes that aren't currently guard nodes to the list
2252 * of guard nodes, at the front. */
2254 entry_guards_prepend_from_config(void)
2256 or_options_t
*options
= get_options();
2257 smartlist_t
*entry_routers
= smartlist_create();
2258 smartlist_t
*old_entry_guards_on_list
= smartlist_create();
2259 smartlist_t
*old_entry_guards_not_on_list
= smartlist_create();
2260 smartlist_t
*entry_fps
= smartlist_create();
2262 tor_assert(entry_guards
);
2263 tor_assert(options
->EntryNodes
);
2265 log_info(LD_CIRC
,"Adding configured EntryNodes '%s'.",
2266 options
->EntryNodes
);
2268 /* Split entry guards into those on the list and those not. */
2269 add_nickname_list_to_smartlist(entry_routers
, options
->EntryNodes
, 0);
2270 SMARTLIST_FOREACH(entry_routers
, routerinfo_t
*, ri
,
2271 smartlist_add(entry_fps
,ri
->cache_info
.identity_digest
));
2272 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, {
2273 if (smartlist_digest_isin(entry_fps
, e
->identity
))
2274 smartlist_add(old_entry_guards_on_list
, e
);
2276 smartlist_add(old_entry_guards_not_on_list
, e
);
2279 /* Remove all currently configured entry guards from entry_routers. */
2280 SMARTLIST_FOREACH(entry_routers
, routerinfo_t
*, ri
, {
2281 if (is_an_entry_guard(ri
->cache_info
.identity_digest
)) {
2282 smartlist_del(entry_routers
, ri_sl_idx
--);
2286 /* Now build the new entry_guards list. */
2287 smartlist_clear(entry_guards
);
2288 /* First, the previously configured guards that are in EntryNodes. */
2289 smartlist_add_all(entry_guards
, old_entry_guards_on_list
);
2290 /* Next, the rest of EntryNodes */
2291 SMARTLIST_FOREACH(entry_routers
, routerinfo_t
*, ri
, {
2292 add_an_entry_guard(ri
);
2294 /* Finally, the remaining EntryNodes, unless we're strict */
2295 if (options
->StrictEntryNodes
) {
2296 SMARTLIST_FOREACH(old_entry_guards_not_on_list
, entry_guard_t
*, e
,
2299 smartlist_add_all(entry_guards
, old_entry_guards_not_on_list
);
2302 should_add_entry_nodes
= 0;
2303 smartlist_free(entry_routers
);
2304 smartlist_free(entry_fps
);
2305 smartlist_free(old_entry_guards_on_list
);
2306 smartlist_free(old_entry_guards_not_on_list
);
2307 entry_guards_changed();
2310 /** Pick a live (up and listed) entry guard from entry_guards, and
2311 * make sure not to pick this circuit's exit. */
2312 static routerinfo_t
*
2313 choose_random_entry(cpath_build_state_t
*state
)
2315 or_options_t
*options
= get_options();
2316 smartlist_t
*live_entry_guards
= smartlist_create();
2317 routerinfo_t
*chosen_exit
= build_state_get_exit_router(state
);
2318 routerinfo_t
*r
= NULL
;
2319 int need_uptime
= state
->need_uptime
;
2320 int need_capacity
= state
->need_capacity
;
2323 entry_guards
= smartlist_create();
2325 if (should_add_entry_nodes
)
2326 entry_guards_prepend_from_config();
2328 if (!options
->StrictEntryNodes
&&
2330 smartlist_len(entry_guards
) < options
->NumEntryGuards
))
2331 pick_entry_guards();
2334 smartlist_clear(live_entry_guards
);
2335 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
2337 r
= entry_is_live(entry
, need_uptime
, need_capacity
, 0);
2338 if (r
&& r
!= chosen_exit
) {
2339 smartlist_add(live_entry_guards
, r
);
2340 if (smartlist_len(live_entry_guards
) >= options
->NumEntryGuards
)
2341 break; /* we have enough */
2345 /* Try to have at least 2 choices available. This way we don't
2346 * get stuck with a single live-but-crummy entry and just keep
2348 * (We might get 2 live-but-crummy entry guards, but so be it.) */
2349 if (smartlist_len(live_entry_guards
) < 2) {
2350 if (!options
->StrictEntryNodes
) {
2351 /* still no? try adding a new entry then */
2352 /* XXX if guard doesn't imply fast and stable, then we need
2353 * to tell add_an_entry_guard below what we want, or it might
2354 * be a long time til we get it. -RD */
2355 r
= add_an_entry_guard(NULL
);
2357 smartlist_add(live_entry_guards
, r
);
2358 entry_guards_changed();
2361 if (!r
&& need_uptime
) {
2362 need_uptime
= 0; /* try without that requirement */
2365 if (!r
&& need_capacity
) {
2366 /* still no? last attempt, try without requiring capacity */
2370 /* live_entry_guards will be empty below. Oh well, we tried. */
2373 r
= smartlist_choose(live_entry_guards
);
2374 smartlist_free(live_entry_guards
);
2378 /** Parse <b>state</b> and learn about the entry guards it describes.
2379 * If <b>set</b> is true, and there are no errors, replace the global
2380 * entry_list with what we find.
2381 * On success, return 0. On failure, alloc into *<b>msg</b> a string
2382 * describing the error, and return -1.
2385 entry_guards_parse_state(or_state_t
*state
, int set
, char **msg
)
2387 entry_guard_t
*node
= NULL
;
2388 smartlist_t
*new_entry_guards
= smartlist_create();
2389 config_line_t
*line
;
2392 for (line
= state
->EntryGuards
; line
; line
= line
->next
) {
2393 if (!strcasecmp(line
->key
, "EntryGuard")) {
2394 smartlist_t
*args
= smartlist_create();
2395 node
= tor_malloc_zero(sizeof(entry_guard_t
));
2396 /* all entry guards on disk have been contacted */
2397 node
->made_contact
= 1;
2398 smartlist_add(new_entry_guards
, node
);
2399 smartlist_split_string(args
, line
->value
, " ",
2400 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
2401 if (smartlist_len(args
)<2) {
2402 *msg
= tor_strdup("Unable to parse entry nodes: "
2403 "Too few arguments to EntryGuard");
2404 } else if (!is_legal_nickname(smartlist_get(args
,0))) {
2405 *msg
= tor_strdup("Unable to parse entry nodes: "
2406 "Bad nickname for EntryGuard");
2408 strlcpy(node
->nickname
, smartlist_get(args
,0), MAX_NICKNAME_LEN
+1);
2409 if (base16_decode(node
->identity
, DIGEST_LEN
, smartlist_get(args
,1),
2410 strlen(smartlist_get(args
,1)))<0) {
2411 *msg
= tor_strdup("Unable to parse entry nodes: "
2412 "Bad hex digest for EntryGuard");
2415 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
2416 smartlist_free(args
);
2421 time_t last_try
= 0;
2423 *msg
= tor_strdup("Unable to parse entry nodes: "
2424 "EntryGuardDownSince/UnlistedSince without EntryGuard");
2427 if (parse_iso_time(line
->value
, &when
)<0) {
2428 *msg
= tor_strdup("Unable to parse entry nodes: "
2429 "Bad time in EntryGuardDownSince/UnlistedSince");
2432 if (strlen(line
->value
) >= ISO_TIME_LEN
+ISO_TIME_LEN
+1) {
2433 /* ignore failure */
2434 parse_iso_time(line
->value
+ISO_TIME_LEN
+1, &last_try
);
2436 if (!strcasecmp(line
->key
, "EntryGuardDownSince")) {
2437 node
->unreachable_since
= when
;
2438 node
->last_attempted
= last_try
;
2440 node
->bad_since
= when
;
2446 SMARTLIST_FOREACH(new_entry_guards
, entry_guard_t
*, e
, tor_free(e
));
2447 smartlist_free(new_entry_guards
);
2448 } else { /* !*err && set */
2450 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, tor_free(e
));
2451 smartlist_free(entry_guards
);
2453 entry_guards
= new_entry_guards
;
2454 entry_guards_dirty
= 0;
2456 return *msg
? -1 : 0;
2459 /** Our list of entry guards has changed, or some element of one
2460 * of our entry guards has changed. Write the changes to disk within
2461 * the next few minutes.
2464 entry_guards_changed(void)
2467 entry_guards_dirty
= 1;
2469 /* or_state_save() will call entry_guards_update_state(). */
2470 when
= get_options()->AvoidDiskWrites
? time(NULL
) + 3600 : time(NULL
)+600;
2471 or_state_mark_dirty(get_or_state(), when
);
2474 /** If the entry guard info has not changed, do nothing and return.
2475 * Otherwise, free the EntryGuards piece of <b>state</b> and create
2476 * a new one out of the global entry_guards list, and then mark
2477 * <b>state</b> dirty so it will get saved to disk.
2480 entry_guards_update_state(or_state_t
*state
)
2482 config_line_t
**next
, *line
;
2483 if (! entry_guards_dirty
)
2486 config_free_lines(state
->EntryGuards
);
2487 next
= &state
->EntryGuards
;
2490 entry_guards
= smartlist_create();
2491 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2493 char dbuf
[HEX_DIGEST_LEN
+1];
2494 if (!e
->made_contact
)
2495 continue; /* don't write this one to disk */
2496 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2497 line
->key
= tor_strdup("EntryGuard");
2498 line
->value
= tor_malloc(HEX_DIGEST_LEN
+MAX_NICKNAME_LEN
+2);
2499 base16_encode(dbuf
, sizeof(dbuf
), e
->identity
, DIGEST_LEN
);
2500 tor_snprintf(line
->value
,HEX_DIGEST_LEN
+MAX_NICKNAME_LEN
+2,
2501 "%s %s", e
->nickname
, dbuf
);
2502 next
= &(line
->next
);
2503 if (e
->unreachable_since
) {
2504 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2505 line
->key
= tor_strdup("EntryGuardDownSince");
2506 line
->value
= tor_malloc(ISO_TIME_LEN
+1+ISO_TIME_LEN
+1);
2507 format_iso_time(line
->value
, e
->unreachable_since
);
2508 if (e
->last_attempted
) {
2509 line
->value
[ISO_TIME_LEN
] = ' ';
2510 format_iso_time(line
->value
+ISO_TIME_LEN
+1, e
->last_attempted
);
2512 next
= &(line
->next
);
2515 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2516 line
->key
= tor_strdup("EntryGuardUnlistedSince");
2517 line
->value
= tor_malloc(ISO_TIME_LEN
+1);
2518 format_iso_time(line
->value
, e
->bad_since
);
2519 next
= &(line
->next
);
2522 if (!get_options()->AvoidDiskWrites
)
2523 or_state_mark_dirty(get_or_state(), 0);
2524 entry_guards_dirty
= 0;
2527 /** If <b>question</b> is the string "entry-guards", then dump
2528 * to *<b>answer</b> a newly allocated string describing all of
2529 * the nodes in the global entry_guards list. See control-spec.txt
2531 * For backward compatibility, we also handle the string "helper-nodes".
2534 getinfo_helper_entry_guards(control_connection_t
*conn
,
2535 const char *question
, char **answer
)
2537 int use_long_names
= conn
->use_long_names
;
2539 if (!strcmp(question
,"entry-guards") ||
2540 !strcmp(question
,"helper-nodes")) {
2541 smartlist_t
*sl
= smartlist_create();
2542 char tbuf
[ISO_TIME_LEN
+1];
2543 char nbuf
[MAX_VERBOSE_NICKNAME_LEN
+1];
2545 entry_guards
= smartlist_create();
2546 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2548 size_t len
= MAX_VERBOSE_NICKNAME_LEN
+ISO_TIME_LEN
+32;
2549 char *c
= tor_malloc(len
);
2550 const char *status
= NULL
;
2552 if (!e
->made_contact
) {
2553 status
= "never-connected";
2554 } else if (e
->bad_since
) {
2555 when
= e
->bad_since
;
2556 status
= "unusable";
2560 if (use_long_names
) {
2561 routerinfo_t
*ri
= router_get_by_digest(e
->identity
);
2563 router_get_verbose_nickname(nbuf
, ri
);
2566 base16_encode(nbuf
+1, sizeof(nbuf
)-1, e
->identity
, DIGEST_LEN
);
2567 /* e->nickname field is not very reliable if we don't know about
2568 * this router any longer; don't include it. */
2571 base16_encode(nbuf
, sizeof(nbuf
), e
->identity
, DIGEST_LEN
);
2574 format_iso_time(tbuf
, when
);
2575 tor_snprintf(c
, len
, "%s %s %s\n", nbuf
, status
, tbuf
);
2577 tor_snprintf(c
, len
, "%s %s\n", nbuf
, status
);
2579 smartlist_add(sl
, c
);
2581 *answer
= smartlist_join_strings(sl
, "", 0, NULL
);
2582 SMARTLIST_FOREACH(sl
, char *, c
, tor_free(c
));