1 /* Copyright (c) 2001 Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2006, 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 uint8_t made_contact
; /**< 0 if we have never connected to this router,
30 time_t bad_since
; /**< 0 if this guard is currently usable, or the time at
31 * which it was observed to become (according to the
32 * directory or the user configuration) unusable. */
33 time_t unreachable_since
; /**< 0 if we can connect to this guard, or the
34 * time at which we first noticed we couldn't
36 time_t last_attempted
; /**< 0 if we can connect to this guard, or the time
37 * at which we last failed to connect to it. */
40 /** A list of our chosen entry guards. */
41 static smartlist_t
*entry_guards
= NULL
;
42 /** A value of 1 means that the entry_guards list has changed
43 * and those changes need to be flushed to disk. */
44 static int entry_guards_dirty
= 0;
46 /********* END VARIABLES ************/
48 static int circuit_deliver_create_cell(circuit_t
*circ
,
49 uint8_t cell_type
, const char *payload
);
50 static int onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
);
51 static crypt_path_t
*onion_next_hop_in_cpath(crypt_path_t
*cpath
);
52 static int onion_extend_cpath(origin_circuit_t
*circ
);
53 static int count_acceptable_routers(smartlist_t
*routers
);
54 static int onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
);
56 static routerinfo_t
*choose_random_entry(cpath_build_state_t
*state
);
57 static void entry_guards_changed(void);
59 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
60 * and with the high bit specified by conn-\>circ_id_type, until we get
61 * a circ_id that is not in use by any other circuit on that conn.
63 * Return it, or 0 if can't get a unique circ_id.
66 get_unique_circ_id_by_conn(or_connection_t
*conn
)
68 uint16_t test_circ_id
;
73 high_bit
= (conn
->circ_id_type
== CIRC_ID_TYPE_HIGHER
) ? 1<<15 : 0;
75 /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
76 * circID such that (high_bit|test_circ_id) is not already used. */
77 test_circ_id
= conn
->next_circ_id
++;
78 if (test_circ_id
== 0 || test_circ_id
>= 1<<15) {
80 conn
->next_circ_id
= 2;
82 if (++attempts
> 1<<15) {
83 /* Make sure we don't loop forever if all circ_id's are used. This
84 * matters because it's an external DoS opportunity.
86 log_warn(LD_CIRC
,"No unused circ IDs. Failing.");
89 test_circ_id
|= high_bit
;
90 } while (circuit_get_by_circid_orconn(test_circ_id
, conn
));
94 /** If <b>verbose</b> is false, allocate and return a comma-separated list of
95 * the currently built elements of circuit_t. If <b>verbose</b> is true, also
96 * list information about link status in a more verbose format using spaces.
97 * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
98 * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
102 circuit_list_path_impl(origin_circuit_t
*circ
, int verbose
, int verbose_names
)
105 smartlist_t
*elements
;
106 const char *states
[] = {"closed", "waiting for keys", "open"};
110 elements
= smartlist_create();
113 const char *nickname
= build_state_get_exit_nickname(circ
->build_state
);
114 tor_snprintf(buf
, sizeof(buf
), "%s%s circ (length %d%s%s):",
115 circ
->build_state
->is_internal
? "internal" : "exit",
116 circ
->build_state
->need_uptime
? " (high-uptime)" : "",
117 circ
->build_state
->desired_path_len
,
118 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" : ", exit ",
119 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" :
120 (nickname
?nickname
:"*unnamed*"));
121 smartlist_add(elements
, tor_strdup(buf
));
130 if (!verbose
&& hop
->state
!= CPATH_STATE_OPEN
)
132 if (!hop
->extend_info
)
135 elt
= tor_malloc(MAX_VERBOSE_NICKNAME_LEN
+1);
136 if ((ri
= router_get_by_digest(hop
->extend_info
->identity_digest
))) {
137 router_get_verbose_nickname(elt
, ri
);
138 } else if (hop
->extend_info
->nickname
&&
139 is_legal_nickname(hop
->extend_info
->nickname
)) {
141 base16_encode(elt
+1, HEX_DIGEST_LEN
+1,
142 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
143 elt
[HEX_DIGEST_LEN
+1]= '~';
144 strlcpy(elt
+HEX_DIGEST_LEN
+2,
145 hop
->extend_info
->nickname
, MAX_NICKNAME_LEN
+1);
148 base16_encode(elt
+1, HEX_DIGEST_LEN
+1,
149 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
151 } else { /* ! verbose_names */
152 if ((ri
= router_get_by_digest(hop
->extend_info
->identity_digest
)) &&
154 elt
= tor_strdup(hop
->extend_info
->nickname
);
156 elt
= tor_malloc(HEX_DIGEST_LEN
+2);
158 base16_encode(elt
+1, HEX_DIGEST_LEN
+1,
159 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
164 size_t len
= strlen(elt
)+2+strlen(states
[hop
->state
])+1;
165 char *v
= tor_malloc(len
);
166 tor_assert(hop
->state
<= 2);
167 tor_snprintf(v
,len
,"%s(%s)",elt
,states
[hop
->state
]);
168 smartlist_add(elements
, v
);
171 smartlist_add(elements
, elt
);
174 } while (hop
!= circ
->cpath
);
176 s
= smartlist_join_strings(elements
, verbose
?" ":",", 0, NULL
);
177 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
178 smartlist_free(elements
);
182 /** If <b>verbose</b> is false, allocate and return a comma-separated
183 * list of the currently built elements of circuit_t. If
184 * <b>verbose</b> is true, also list information about link status in
185 * a more verbose format using spaces.
188 circuit_list_path(origin_circuit_t
*circ
, int verbose
)
190 return circuit_list_path_impl(circ
, verbose
, 0);
193 /** Allocate and return a comma-separated list of the currently built elements
194 * of circuit_t, giving each as a verbose nickname.
197 circuit_list_path_for_controller(origin_circuit_t
*circ
)
199 return circuit_list_path_impl(circ
, 0, 1);
202 /** Log, at severity <b>severity</b>, the nicknames of each router in
203 * circ's cpath. Also log the length of the cpath, and the intended
207 circuit_log_path(int severity
, unsigned int domain
, origin_circuit_t
*circ
)
209 char *s
= circuit_list_path(circ
,1);
210 log(severity
,domain
,"%s",s
);
214 /** Tell the rep(utation)hist(ory) module about the status of the links
215 * in circ. Hops that have become OPEN are marked as successfully
216 * extended; the _first_ hop that isn't open (if any) is marked as
219 /* XXXX Someday we should learn from OR circuits too. */
221 circuit_rep_hist_note_result(origin_circuit_t
*circ
)
224 char *prev_digest
= NULL
;
225 routerinfo_t
*router
;
227 if (!hop
) /* circuit hasn't started building yet. */
229 if (server_mode(get_options())) {
230 routerinfo_t
*me
= router_get_my_routerinfo();
233 prev_digest
= me
->cache_info
.identity_digest
;
236 router
= router_get_by_digest(hop
->extend_info
->identity_digest
);
239 if (hop
->state
== CPATH_STATE_OPEN
)
240 rep_hist_note_extend_succeeded(prev_digest
,
241 router
->cache_info
.identity_digest
);
243 rep_hist_note_extend_failed(prev_digest
,
244 router
->cache_info
.identity_digest
);
248 prev_digest
= router
->cache_info
.identity_digest
;
253 } while (hop
!=circ
->cpath
);
256 /** Pick all the entries in our cpath. Stop and return 0 when we're
257 * happy, or return -1 if an error occurs. */
259 onion_populate_cpath(origin_circuit_t
*circ
)
263 r
= onion_extend_cpath(circ
);
265 log_info(LD_CIRC
,"Generating cpath hop failed.");
270 return 0; /* if r == 1 */
273 /** Create and return a new origin circuit. Initialize its purpose and
274 * build-state based on our arguments. */
276 origin_circuit_init(uint8_t purpose
, int onehop_tunnel
,
277 int need_uptime
, int need_capacity
, int internal
)
279 /* sets circ->p_circ_id and circ->p_conn */
280 origin_circuit_t
*circ
= origin_circuit_new();
281 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OR_WAIT
);
282 circ
->build_state
= tor_malloc_zero(sizeof(cpath_build_state_t
));
283 circ
->build_state
->onehop_tunnel
= onehop_tunnel
;
284 circ
->build_state
->need_uptime
= need_uptime
;
285 circ
->build_state
->need_capacity
= need_capacity
;
286 circ
->build_state
->is_internal
= internal
;
287 circ
->_base
.purpose
= purpose
;
291 /** Build a new circuit for <b>purpose</b>. If <b>info</b>
292 * is defined, then use that as your exit router, else choose a suitable
295 * Also launch a connection to the first OR in the chosen path, if
296 * it's not open already.
299 circuit_establish_circuit(uint8_t purpose
, int onehop_tunnel
,
301 int need_uptime
, int need_capacity
, int internal
)
303 origin_circuit_t
*circ
;
306 circ
= origin_circuit_init(purpose
, onehop_tunnel
,
307 need_uptime
, need_capacity
, internal
);
309 if (onion_pick_cpath_exit(circ
, info
) < 0 ||
310 onion_populate_cpath(circ
) < 0) {
311 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_NOPATH
);
315 control_event_circuit_status(circ
, CIRC_EVENT_LAUNCHED
, 0);
317 if ((err_reason
= circuit_handle_first_hop(circ
)) < 0) {
318 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
324 /** Start establishing the first hop of our circuit. Figure out what
325 * OR we should connect to, and if necessary start the connection to
326 * it. If we're already connected, then send the 'create' cell.
327 * Return 0 for ok, -reason if circ should be marked-for-close. */
329 circuit_handle_first_hop(origin_circuit_t
*circ
)
331 crypt_path_t
*firsthop
;
332 or_connection_t
*n_conn
;
333 char tmpbuf
[INET_NTOA_BUF_LEN
];
337 firsthop
= onion_next_hop_in_cpath(circ
->cpath
);
338 tor_assert(firsthop
);
339 tor_assert(firsthop
->extend_info
);
341 /* now see if we're already connected to the first OR in 'route' */
342 in
.s_addr
= htonl(firsthop
->extend_info
->addr
);
343 tor_inet_ntoa(&in
, tmpbuf
, sizeof(tmpbuf
));
344 log_debug(LD_CIRC
,"Looking for firsthop '%s:%u'",tmpbuf
,
345 firsthop
->extend_info
->port
);
346 /* imprint the circuit with its future n_conn->id */
347 memcpy(circ
->_base
.n_conn_id_digest
, firsthop
->extend_info
->identity_digest
,
349 n_conn
= connection_or_get_by_identity_digest(
350 firsthop
->extend_info
->identity_digest
);
351 /* If we don't have an open conn, or the conn we have is obsolete
352 * (i.e. old or broken) and the other side will let us make a second
353 * connection without dropping it immediately... */
354 if (!n_conn
|| n_conn
->_base
.state
!= OR_CONN_STATE_OPEN
||
355 (n_conn
->_base
.or_is_obsolete
&&
356 router_digest_version_as_new_as(firsthop
->extend_info
->identity_digest
,
357 "0.1.1.9-alpha-cvs"))) {
358 /* not currently connected */
359 circ
->_base
.n_addr
= firsthop
->extend_info
->addr
;
360 circ
->_base
.n_port
= firsthop
->extend_info
->port
;
362 if (!n_conn
|| n_conn
->_base
.or_is_obsolete
) { /* launch the connection */
363 n_conn
= connection_or_connect(firsthop
->extend_info
->addr
,
364 firsthop
->extend_info
->port
,
365 firsthop
->extend_info
->identity_digest
);
366 if (!n_conn
) { /* connect failed, forget the whole thing */
367 log_info(LD_CIRC
,"connect to firsthop failed. Closing.");
368 return -END_CIRC_REASON_CONNECTFAILED
;
372 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
373 /* return success. The onion/circuit/etc will be taken care of
374 * automatically (may already have been) whenever n_conn reaches
375 * OR_CONN_STATE_OPEN.
378 } else { /* it's already open. use it. */
379 circ
->_base
.n_addr
= n_conn
->_base
.addr
;
380 circ
->_base
.n_port
= n_conn
->_base
.port
;
381 circ
->_base
.n_conn
= n_conn
;
382 log_debug(LD_CIRC
,"Conn open. Delivering first onion skin.");
383 if ((err_reason
= circuit_send_next_onion_skin(circ
)) < 0) {
384 log_info(LD_CIRC
,"circuit_send_next_onion_skin failed.");
391 /** Find any circuits that are waiting on <b>or_conn</b> to become
392 * open and get them to send their create cells forward.
394 * Status is 1 if connect succeeded, or 0 if connect failed.
397 circuit_n_conn_done(or_connection_t
*or_conn
, int status
)
399 smartlist_t
*pending_circs
;
402 log_debug(LD_CIRC
,"or_conn to %s, status=%d",
403 or_conn
->nickname
? or_conn
->nickname
: "NULL", status
);
405 pending_circs
= smartlist_create();
406 circuit_get_all_pending_on_or_conn(pending_circs
, or_conn
);
408 SMARTLIST_FOREACH(pending_circs
, circuit_t
*, circ
,
410 /* This check is redundant wrt get_all_pending_on_or_conn, but I'm
411 * leaving them in in case it's possible for the status of a circuit to
412 * change as we're going down the list. */
413 if (circ
->marked_for_close
|| circ
->n_conn
||
414 circ
->state
!= CIRCUIT_STATE_OR_WAIT
||
415 memcmp(or_conn
->identity_digest
, circ
->n_conn_id_digest
, DIGEST_LEN
))
417 if (!status
) { /* or_conn failed; close circ */
418 log_info(LD_CIRC
,"or_conn failed. Closing circ.");
419 circuit_mark_for_close(circ
, END_CIRC_REASON_OR_CONN_CLOSED
);
422 log_debug(LD_CIRC
, "Found circ, sending create cell.");
423 /* circuit_deliver_create_cell will set n_circ_id and add us to
424 * orconn_circuid_circuit_map, so we don't need to call
425 * set_circid_orconn here. */
426 circ
->n_conn
= or_conn
;
427 if (CIRCUIT_IS_ORIGIN(circ
)) {
429 circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ
))) < 0) {
431 "send_next_onion_skin failed; circuit marked for closing.");
432 circuit_mark_for_close(circ
, -err_reason
);
434 /* XXX could this be bad, eg if next_onion_skin failed because conn
438 /* pull the create cell out of circ->onionskin, and send it */
439 tor_assert(circ
->onionskin
);
440 if (circuit_deliver_create_cell(circ
,CELL_CREATE
,circ
->onionskin
)<0) {
441 circuit_mark_for_close(circ
, END_CIRC_REASON_RESOURCELIMIT
);
444 tor_free(circ
->onionskin
);
445 circuit_set_state(circ
, CIRCUIT_STATE_OPEN
);
449 smartlist_free(pending_circs
);
452 /** Find a new circid that isn't currently in use on the circ->n_conn
454 * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
455 * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
457 * Return -1 if we failed to find a suitable circid, else return 0.
460 circuit_deliver_create_cell(circuit_t
*circ
, uint8_t cell_type
,
467 tor_assert(circ
->n_conn
);
469 tor_assert(cell_type
== CELL_CREATE
|| cell_type
== CELL_CREATE_FAST
);
471 id
= get_unique_circ_id_by_conn(circ
->n_conn
);
473 log_warn(LD_CIRC
,"failed to get unique circID.");
476 log_debug(LD_CIRC
,"Chosen circID %u.", id
);
477 circuit_set_n_circid_orconn(circ
, id
, circ
->n_conn
);
479 memset(&cell
, 0, sizeof(cell_t
));
480 cell
.command
= cell_type
;
481 cell
.circ_id
= circ
->n_circ_id
;
483 memcpy(cell
.payload
, payload
, ONIONSKIN_CHALLENGE_LEN
);
484 connection_or_write_cell_to_buf(&cell
, circ
->n_conn
);
488 /** We've decided to start our reachability testing. If all
489 * is set, log this to the user. Return 1 if we did, or 0 if
490 * we chose not to log anything. */
492 inform_testing_reachability(void)
495 routerinfo_t
*me
= router_get_my_routerinfo();
499 tor_snprintf(dirbuf
, sizeof(dirbuf
), " and DirPort %s:%d",
500 me
->address
, me
->dir_port
);
501 log(LOG_NOTICE
, LD_OR
, "Now checking whether ORPort %s:%d%s %s reachable... "
502 "(this may take up to %d minutes -- look for log "
503 "messages indicating success)",
504 me
->address
, me
->or_port
,
505 me
->dir_port
? dirbuf
: "",
506 me
->dir_port
? "are" : "is",
507 TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT
/60);
511 /** Return true iff we should send a create_fast cell to build a circuit
512 * starting at <b>router</b>. (If <b>router</b> is NULL, we don't have
513 * information on the router, so assume true.) */
515 should_use_create_fast_for_router(routerinfo_t
*router
,
516 origin_circuit_t
*circ
)
518 or_options_t
*options
= get_options();
520 if (!options
->FastFirstHopPK
) /* create_fast is disabled */
522 if (router
&& router
->platform
&&
523 !tor_version_as_new_as(router
->platform
, "0.1.0.6-rc")) {
524 /* known not to work */
527 if (server_mode(options
) && circ
->cpath
->extend_info
->onion_key
) {
528 /* We're a server, and we know an onion key. We can choose.
529 * Prefer to blend in. */
536 /** This is the backbone function for building circuits.
538 * If circ's first hop is closed, then we need to build a create
539 * cell and send it forward.
541 * Otherwise, we need to build a relay extend cell and send it
544 * Return -reason if we want to tear down circ, else return 0.
547 circuit_send_next_onion_skin(origin_circuit_t
*circ
)
550 routerinfo_t
*router
;
551 char payload
[2+4+DIGEST_LEN
+ONIONSKIN_CHALLENGE_LEN
];
557 if (circ
->cpath
->state
== CPATH_STATE_CLOSED
) {
560 log_debug(LD_CIRC
,"First skin; sending create cell.");
562 router
= router_get_by_digest(circ
->_base
.n_conn
->identity_digest
);
563 fast
= should_use_create_fast_for_router(router
, circ
);
564 if (!fast
&& !circ
->cpath
->extend_info
->onion_key
) {
566 "Can't send create_fast, but have no onion key. Failing.");
567 return - END_CIRC_REASON_INTERNAL
;
570 /* We are an OR, or we are connecting to an old Tor: we should
571 * send an old slow create cell.
573 cell_type
= CELL_CREATE
;
574 if (onion_skin_create(circ
->cpath
->extend_info
->onion_key
,
575 &(circ
->cpath
->dh_handshake_state
),
577 log_warn(LD_CIRC
,"onion_skin_create (first hop) failed.");
578 return - END_CIRC_REASON_INTERNAL
;
581 /* We are not an OR, and we're building the first hop of a circuit to a
582 * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
583 * and a DH operation. */
584 cell_type
= CELL_CREATE_FAST
;
585 memset(payload
, 0, sizeof(payload
));
586 crypto_rand(circ
->cpath
->fast_handshake_state
,
587 sizeof(circ
->cpath
->fast_handshake_state
));
588 memcpy(payload
, circ
->cpath
->fast_handshake_state
,
589 sizeof(circ
->cpath
->fast_handshake_state
));
592 if (circuit_deliver_create_cell(TO_CIRCUIT(circ
), cell_type
, payload
) < 0)
593 return - END_CIRC_REASON_RESOURCELIMIT
;
595 circ
->cpath
->state
= CPATH_STATE_AWAITING_KEYS
;
596 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
597 log_info(LD_CIRC
,"First hop: finished sending %s cell to '%s'",
598 fast
? "CREATE_FAST" : "CREATE",
599 router
? router
->nickname
: "<unnamed>");
601 tor_assert(circ
->cpath
->state
== CPATH_STATE_OPEN
);
602 tor_assert(circ
->_base
.state
== CIRCUIT_STATE_BUILDING
);
603 log_debug(LD_CIRC
,"starting to send subsequent skin.");
604 hop
= onion_next_hop_in_cpath(circ
->cpath
);
606 /* done building the circuit. whew. */
607 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
608 log_info(LD_CIRC
,"circuit built!");
609 circuit_reset_failure_count(0);
610 if (!has_completed_circuit
&& !circ
->build_state
->onehop_tunnel
) {
611 or_options_t
*options
= get_options();
612 has_completed_circuit
=1;
613 /* FFFF Log a count of known routers here */
614 log(LOG_NOTICE
, LD_GENERAL
,
615 "Tor has successfully opened a circuit. "
616 "Looks like client functionality is working.");
617 control_event_client_status(LOG_NOTICE
, "CIRCUIT_ESTABLISHED");
618 if (server_mode(options
) && !check_whether_orport_reachable()) {
619 inform_testing_reachability();
620 consider_testing_reachability(1, 1);
623 circuit_rep_hist_note_result(circ
);
624 circuit_has_opened(circ
); /* do other actions as necessary */
628 set_uint32(payload
, htonl(hop
->extend_info
->addr
));
629 set_uint16(payload
+4, htons(hop
->extend_info
->port
));
631 onionskin
= payload
+2+4;
632 memcpy(payload
+2+4+ONIONSKIN_CHALLENGE_LEN
,
633 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
634 payload_len
= 2+4+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
;
636 if (onion_skin_create(hop
->extend_info
->onion_key
,
637 &(hop
->dh_handshake_state
), onionskin
) < 0) {
638 log_warn(LD_CIRC
,"onion_skin_create failed.");
639 return - END_CIRC_REASON_INTERNAL
;
642 log_debug(LD_CIRC
,"Sending extend relay cell.");
643 /* send it to hop->prev, because it will transfer
644 * it to a create cell and then send to hop */
645 if (connection_edge_send_command(NULL
, TO_CIRCUIT(circ
),
646 RELAY_COMMAND_EXTEND
,
647 payload
, payload_len
, hop
->prev
) < 0)
648 return 0; /* circuit is closed */
650 hop
->state
= CPATH_STATE_AWAITING_KEYS
;
655 /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
656 * something has also gone wrong with our network: notify the user,
657 * and abandon all not-yet-used circuits. */
659 circuit_note_clock_jumped(int seconds_elapsed
)
661 int severity
= server_mode(get_options()) ? LOG_WARN
: LOG_NOTICE
;
662 log(severity
, LD_GENERAL
, "Your clock just jumped %d seconds %s; "
663 "assuming established circuits no longer work.",
664 seconds_elapsed
>=0 ? seconds_elapsed
: -seconds_elapsed
,
665 seconds_elapsed
>=0 ? "forward" : "backward");
666 control_event_general_status(LOG_WARN
, "CLOCK_JUMPED TIME=%d",
668 has_completed_circuit
=0; /* so it'll log when it works again */
669 control_event_client_status(severity
, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
671 circuit_mark_all_unused_circs();
672 circuit_expire_all_dirty_circs();
675 /** Take the 'extend' cell, pull out addr/port plus the onion skin. Make
676 * sure we're connected to the next hop, and pass it the onion skin using
677 * a create cell. Return -1 if we want to warn and tear down the circuit,
681 circuit_extend(cell_t
*cell
, circuit_t
*circ
)
683 or_connection_t
*n_conn
;
686 char *id_digest
=NULL
;
689 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
690 "n_conn already set. Bug/attack. Closing.");
694 if (!server_mode(get_options())) {
695 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
696 "Got an extend cell, but running as a client. Closing.");
700 relay_header_unpack(&rh
, cell
->payload
);
702 if (rh
.length
< 4+2+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
) {
703 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
704 "Wrong length %d on extend cell. Closing circuit.",
709 circ
->n_addr
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
));
710 circ
->n_port
= ntohs(get_uint16(cell
->payload
+RELAY_HEADER_SIZE
+4));
712 onionskin
= cell
->payload
+RELAY_HEADER_SIZE
+4+2;
713 id_digest
= cell
->payload
+RELAY_HEADER_SIZE
+4+2+ONIONSKIN_CHALLENGE_LEN
;
714 n_conn
= connection_or_get_by_identity_digest(id_digest
);
716 /* If we don't have an open conn, or the conn we have is obsolete
717 * (i.e. old or broken) and the other side will let us make a second
718 * connection without dropping it immediately... */
719 if (!n_conn
|| n_conn
->_base
.state
!= OR_CONN_STATE_OPEN
||
720 (n_conn
->_base
.or_is_obsolete
&&
721 router_digest_version_as_new_as(id_digest
,"0.1.1.9-alpha-cvs"))) {
723 char tmpbuf
[INET_NTOA_BUF_LEN
];
724 in
.s_addr
= htonl(circ
->n_addr
);
725 tor_inet_ntoa(&in
,tmpbuf
,sizeof(tmpbuf
));
726 log_info(LD_CIRC
|LD_OR
,"Next router (%s:%d) not connected. Connecting.",
727 tmpbuf
, circ
->n_port
);
729 circ
->onionskin
= tor_malloc(ONIONSKIN_CHALLENGE_LEN
);
730 memcpy(circ
->onionskin
, onionskin
, ONIONSKIN_CHALLENGE_LEN
);
731 circuit_set_state(circ
, CIRCUIT_STATE_OR_WAIT
);
733 /* imprint the circuit with its future n_conn->id */
734 memcpy(circ
->n_conn_id_digest
, id_digest
, DIGEST_LEN
);
736 if (n_conn
&& !n_conn
->_base
.or_is_obsolete
) {
737 circ
->n_addr
= n_conn
->_base
.addr
;
738 circ
->n_port
= n_conn
->_base
.port
;
740 /* we should try to open a connection */
741 n_conn
= connection_or_connect(circ
->n_addr
, circ
->n_port
, id_digest
);
743 log_info(LD_CIRC
,"Launching n_conn failed. Closing circuit.");
744 circuit_mark_for_close(circ
, END_CIRC_REASON_CONNECTFAILED
);
747 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
749 /* return success. The onion/circuit/etc will be taken care of
750 * automatically (may already have been) whenever n_conn reaches
751 * OR_CONN_STATE_OPEN.
756 /* these may be different if the router connected to us from elsewhere */
757 circ
->n_addr
= n_conn
->_base
.addr
;
758 circ
->n_port
= n_conn
->_base
.port
;
760 circ
->n_conn
= n_conn
;
761 memcpy(circ
->n_conn_id_digest
, n_conn
->identity_digest
, DIGEST_LEN
);
762 log_debug(LD_CIRC
,"n_conn is %s:%u",
763 n_conn
->_base
.address
,n_conn
->_base
.port
);
765 if (circuit_deliver_create_cell(circ
, CELL_CREATE
, onionskin
) < 0)
770 /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
771 * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
773 * - 20 to initialize f_digest
774 * - 20 to initialize b_digest
775 * - 16 to key f_crypto
776 * - 16 to key b_crypto
778 * (If 'reverse' is true, then f_XX and b_XX are swapped.)
781 circuit_init_cpath_crypto(crypt_path_t
*cpath
, const char *key_data
,
784 crypto_digest_env_t
*tmp_digest
;
785 crypto_cipher_env_t
*tmp_crypto
;
788 tor_assert(key_data
);
789 tor_assert(!(cpath
->f_crypto
|| cpath
->b_crypto
||
790 cpath
->f_digest
|| cpath
->b_digest
));
792 cpath
->f_digest
= crypto_new_digest_env();
793 crypto_digest_add_bytes(cpath
->f_digest
, key_data
, DIGEST_LEN
);
794 cpath
->b_digest
= crypto_new_digest_env();
795 crypto_digest_add_bytes(cpath
->b_digest
, key_data
+DIGEST_LEN
, DIGEST_LEN
);
797 if (!(cpath
->f_crypto
=
798 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
),1))) {
799 log_warn(LD_BUG
,"Bug: forward cipher initialization failed.");
802 if (!(cpath
->b_crypto
=
803 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
)+CIPHER_KEY_LEN
,0))) {
804 log_warn(LD_BUG
,"Bug: backward cipher initialization failed.");
809 tmp_digest
= cpath
->f_digest
;
810 cpath
->f_digest
= cpath
->b_digest
;
811 cpath
->b_digest
= tmp_digest
;
812 tmp_crypto
= cpath
->f_crypto
;
813 cpath
->f_crypto
= cpath
->b_crypto
;
814 cpath
->b_crypto
= tmp_crypto
;
820 /** A created or extended cell came back to us on the circuit, and it included
821 * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body
822 * contains (the second DH key, plus KH). If <b>reply_type</b> is
823 * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
825 * Calculate the appropriate keys and digests, make sure KH is
826 * correct, and initialize this hop of the cpath.
828 * Return - reason if we want to mark circ for close, else return 0.
831 circuit_finish_handshake(origin_circuit_t
*circ
, uint8_t reply_type
,
834 char keys
[CPATH_KEY_MATERIAL_LEN
];
837 if (circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
)
840 hop
= onion_next_hop_in_cpath(circ
->cpath
);
841 if (!hop
) { /* got an extended when we're all done? */
842 log_warn(LD_PROTOCOL
,"got extended when circ already built? Closing.");
843 return - END_CIRC_REASON_TORPROTOCOL
;
846 tor_assert(hop
->state
== CPATH_STATE_AWAITING_KEYS
);
848 if (reply_type
== CELL_CREATED
&& hop
->dh_handshake_state
) {
849 if (onion_skin_client_handshake(hop
->dh_handshake_state
, reply
, keys
,
850 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
851 log_warn(LD_CIRC
,"onion_skin_client_handshake failed.");
852 return -END_CIRC_REASON_TORPROTOCOL
;
854 /* Remember hash of g^xy */
855 memcpy(hop
->handshake_digest
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
856 } else if (reply_type
== CELL_CREATED_FAST
&& !hop
->dh_handshake_state
) {
857 if (fast_client_handshake(hop
->fast_handshake_state
, reply
, keys
,
858 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
859 log_warn(LD_CIRC
,"fast_client_handshake failed.");
860 return -END_CIRC_REASON_TORPROTOCOL
;
862 memcpy(hop
->handshake_digest
, reply
+DIGEST_LEN
, DIGEST_LEN
);
864 log_warn(LD_PROTOCOL
,"CREATED cell type did not match CREATE cell type.");
865 return -END_CIRC_REASON_TORPROTOCOL
;
868 if (hop
->dh_handshake_state
) {
869 crypto_dh_free(hop
->dh_handshake_state
); /* don't need it anymore */
870 hop
->dh_handshake_state
= NULL
;
872 memset(hop
->fast_handshake_state
, 0, sizeof(hop
->fast_handshake_state
));
874 if (circuit_init_cpath_crypto(hop
, keys
, 0)<0) {
875 return -END_CIRC_REASON_TORPROTOCOL
;
878 hop
->state
= CPATH_STATE_OPEN
;
879 log_info(LD_CIRC
,"Finished building %scircuit hop:",
880 (reply_type
== CELL_CREATED_FAST
) ? "fast " : "");
881 circuit_log_path(LOG_INFO
,LD_CIRC
,circ
);
882 control_event_circuit_status(circ
, CIRC_EVENT_EXTENDED
, 0);
887 /** We received a relay truncated cell on circ.
889 * Since we don't ask for truncates currently, getting a truncated
890 * means that a connection broke or an extend failed. For now,
891 * just give up: for circ to close, and return 0.
894 circuit_truncated(origin_circuit_t
*circ
, crypt_path_t
*layer
)
896 // crypt_path_t *victim;
897 // connection_t *stream;
902 /* XXX Since we don't ask for truncates currently, getting a truncated
903 * means that a connection broke or an extend failed. For now,
906 circuit_mark_for_close(TO_CIRCUIT(circ
),
907 END_CIRC_REASON_FLAG_REMOTE
|END_CIRC_REASON_OR_CONN_CLOSED
);
911 while (layer
->next
!= circ
->cpath
) {
912 /* we need to clear out layer->next */
913 victim
= layer
->next
;
914 log_debug(LD_CIRC
, "Killing a layer of the cpath.");
916 for (stream
= circ
->p_streams
; stream
; stream
=stream
->next_stream
) {
917 if (stream
->cpath_layer
== victim
) {
918 log_info(LD_APP
, "Marking stream %d for close because of truncate.",
920 /* no need to send 'end' relay cells,
921 * because the other side's already dead
923 connection_mark_unattached_ap(stream
, END_STREAM_REASON_DESTROY
);
927 layer
->next
= victim
->next
;
928 circuit_free_cpath_node(victim
);
931 log_info(LD_CIRC
, "finished");
936 /** Given a response payload and keys, initialize, then send a created
940 onionskin_answer(or_circuit_t
*circ
, uint8_t cell_type
, const char *payload
,
944 crypt_path_t
*tmp_cpath
;
946 tmp_cpath
= tor_malloc_zero(sizeof(crypt_path_t
));
947 tmp_cpath
->magic
= CRYPT_PATH_MAGIC
;
949 memset(&cell
, 0, sizeof(cell_t
));
950 cell
.command
= cell_type
;
951 cell
.circ_id
= circ
->p_circ_id
;
953 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
955 memcpy(cell
.payload
, payload
,
956 cell_type
== CELL_CREATED
? ONIONSKIN_REPLY_LEN
: DIGEST_LEN
*2);
958 log_debug(LD_CIRC
,"init digest forward 0x%.8x, backward 0x%.8x.",
959 (unsigned int)*(uint32_t*)(keys
),
960 (unsigned int)*(uint32_t*)(keys
+20));
961 if (circuit_init_cpath_crypto(tmp_cpath
, keys
, 0)<0) {
962 log_warn(LD_BUG
,"Circuit initialization failed");
966 circ
->n_digest
= tmp_cpath
->f_digest
;
967 circ
->n_crypto
= tmp_cpath
->f_crypto
;
968 circ
->p_digest
= tmp_cpath
->b_digest
;
969 circ
->p_crypto
= tmp_cpath
->b_crypto
;
970 tmp_cpath
->magic
= 0;
973 if (cell_type
== CELL_CREATED
)
974 memcpy(circ
->handshake_digest
, cell
.payload
+DH_KEY_LEN
, DIGEST_LEN
);
976 memcpy(circ
->handshake_digest
, cell
.payload
+DIGEST_LEN
, DIGEST_LEN
);
978 circ
->is_first_hop
= (cell_type
== CELL_CREATED_FAST
);
980 connection_or_write_cell_to_buf(&cell
, circ
->p_conn
);
981 log_debug(LD_CIRC
,"Finished sending 'created' cell.");
983 if (!is_local_IP(circ
->p_conn
->_base
.addr
) &&
984 !connection_or_nonopen_was_started_here(circ
->p_conn
)) {
985 /* record that we could process create cells from a non-local conn
986 * that we didn't initiate; presumably this means that create cells
987 * can reach us too. */
988 router_orport_found_reachable();
994 /** Choose a length for a circuit of purpose <b>purpose</b>.
995 * Default length is 3 + the number of endpoints that would give something
996 * away. If the routerlist <b>routers</b> doesn't have enough routers
997 * to handle the desired path length, return as large a path length as
998 * is feasible, except if it's less than 2, in which case return -1.
1001 new_route_len(double cw
, uint8_t purpose
, extend_info_t
*exit
,
1002 smartlist_t
*routers
)
1004 int num_acceptable_routers
;
1007 tor_assert(cw
>= 0.);
1008 tor_assert(cw
< 1.);
1009 tor_assert(routers
);
1016 purpose
!= CIRCUIT_PURPOSE_TESTING
&&
1017 purpose
!= CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
)
1020 log_debug(LD_CIRC
,"Chosen route length %d (%d routers available).",
1021 routelen
, smartlist_len(routers
));
1023 num_acceptable_routers
= count_acceptable_routers(routers
);
1025 if (num_acceptable_routers
< 2) {
1027 "Not enough acceptable routers (%d). Discarding this circuit.",
1028 num_acceptable_routers
);
1032 if (num_acceptable_routers
< routelen
) {
1033 log_info(LD_CIRC
,"Not enough routers: cutting routelen from %d to %d.",
1034 routelen
, num_acceptable_routers
);
1035 routelen
= num_acceptable_routers
;
1041 /** Fetch the list of predicted ports, dup it into a smartlist of
1042 * uint16_t's, remove the ones that are already handled by an
1043 * existing circuit, and return it.
1045 static smartlist_t
*
1046 circuit_get_unhandled_ports(time_t now
)
1048 smartlist_t
*source
= rep_hist_get_predicted_ports(now
);
1049 smartlist_t
*dest
= smartlist_create();
1053 for (i
= 0; i
< smartlist_len(source
); ++i
) {
1054 tmp
= tor_malloc(sizeof(uint16_t));
1055 memcpy(tmp
, smartlist_get(source
, i
), sizeof(uint16_t));
1056 smartlist_add(dest
, tmp
);
1059 circuit_remove_handled_ports(dest
);
1063 /** Return 1 if we already have circuits present or on the way for
1064 * all anticipated ports. Return 0 if we should make more.
1066 * If we're returning 0, set need_uptime and need_capacity to
1067 * indicate any requirements that the unhandled ports have.
1070 circuit_all_predicted_ports_handled(time_t now
, int *need_uptime
,
1075 smartlist_t
*sl
= circuit_get_unhandled_ports(now
);
1076 smartlist_t
*LongLivedServices
= get_options()->LongLivedPorts
;
1077 tor_assert(need_uptime
);
1078 tor_assert(need_capacity
);
1079 enough
= (smartlist_len(sl
) == 0);
1080 for (i
= 0; i
< smartlist_len(sl
); ++i
) {
1081 port
= smartlist_get(sl
, i
);
1082 if (smartlist_string_num_isin(LongLivedServices
, *port
))
1090 /** Return 1 if <b>router</b> can handle one or more of the ports in
1091 * <b>needed_ports</b>, else return 0.
1094 router_handles_some_port(routerinfo_t
*router
, smartlist_t
*needed_ports
)
1099 for (i
= 0; i
< smartlist_len(needed_ports
); ++i
) {
1100 addr_policy_result_t r
;
1101 port
= *(uint16_t *)smartlist_get(needed_ports
, i
);
1103 r
= compare_addr_to_addr_policy(0, port
, router
->exit_policy
);
1104 if (r
!= ADDR_POLICY_REJECTED
&& r
!= ADDR_POLICY_PROBABLY_REJECTED
)
1112 ap_stream_wants_exit_attention(connection_t
*conn
)
1114 if (conn
->type
== CONN_TYPE_AP
&&
1115 conn
->state
== AP_CONN_STATE_CIRCUIT_WAIT
&&
1116 !conn
->marked_for_close
&&
1117 !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn
)) &&
1118 !circuit_stream_is_being_handled(TO_EDGE_CONN(conn
), 0,
1119 MIN_CIRCUITS_HANDLING_STREAM
))
1124 /** Return a pointer to a suitable router to be the exit node for the
1125 * general-purpose circuit we're about to build.
1127 * Look through the connection array, and choose a router that maximizes
1128 * the number of pending streams that can exit from this router.
1130 * Return NULL if we can't find any suitable routers.
1132 static routerinfo_t
*
1133 choose_good_exit_server_general(routerlist_t
*dir
, int need_uptime
,
1138 int n_pending_connections
= 0;
1139 connection_t
**carray
;
1141 int best_support
= -1;
1142 int n_best_support
=0;
1143 smartlist_t
*sl
, *preferredexits
, *excludedexits
;
1144 routerinfo_t
*router
;
1145 or_options_t
*options
= get_options();
1147 get_connection_array(&carray
, &n_connections
);
1149 /* Count how many connections are waiting for a circuit to be built.
1150 * We use this for log messages now, but in the future we may depend on it.
1152 for (i
= 0; i
< n_connections
; ++i
) {
1153 if (ap_stream_wants_exit_attention(carray
[i
]))
1154 ++n_pending_connections
;
1156 // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
1157 // n_pending_connections);
1158 /* Now we count, for each of the routers in the directory, how many
1159 * of the pending connections could possibly exit from that
1160 * router (n_supported[i]). (We can't be sure about cases where we
1161 * don't know the IP address of the pending connection.)
1163 n_supported
= tor_malloc(sizeof(int)*smartlist_len(dir
->routers
));
1164 for (i
= 0; i
< smartlist_len(dir
->routers
); ++i
) {/* iterate over routers */
1165 router
= smartlist_get(dir
->routers
, i
);
1166 if (router_is_me(router
)) {
1167 n_supported
[i
] = -1;
1168 // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
1169 /* XXX there's probably a reverse predecessor attack here, but
1170 * it's slow. should we take this out? -RD
1174 if (!router
->is_running
|| router
->is_bad_exit
) {
1175 n_supported
[i
] = -1;
1176 continue; /* skip routers that are known to be down or bad exits */
1178 if (router_is_unreliable(router
, need_uptime
, need_capacity
, 0)) {
1179 n_supported
[i
] = -1;
1180 continue; /* skip routers that are not suitable */
1182 if (!(router
->is_valid
|| options
->_AllowInvalid
& ALLOW_INVALID_EXIT
)) {
1183 /* if it's invalid and we don't want it */
1184 n_supported
[i
] = -1;
1185 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
1186 // router->nickname, i);
1187 continue; /* skip invalid routers */
1189 if (router_exit_policy_rejects_all(router
)) {
1190 n_supported
[i
] = -1;
1191 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
1192 // router->nickname, i);
1193 continue; /* skip routers that reject all */
1196 for (j
= 0; j
< n_connections
; ++j
) { /* iterate over connections */
1197 if (!ap_stream_wants_exit_attention(carray
[j
]))
1198 continue; /* Skip everything but APs in CIRCUIT_WAIT */
1199 if (connection_ap_can_use_exit(TO_EDGE_CONN(carray
[j
]), router
)) {
1201 // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
1202 // router->nickname, i, n_supported[i]);
1204 // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
1205 // router->nickname, i);
1207 } /* End looping over connections. */
1208 if (n_supported
[i
] > best_support
) {
1209 /* If this router is better than previous ones, remember its index
1210 * and goodness, and start counting how many routers are this good. */
1211 best_support
= n_supported
[i
]; n_best_support
=1;
1212 // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
1213 // router->nickname);
1214 } else if (n_supported
[i
] == best_support
) {
1215 /* If this router is _as good_ as the best one, just increment the
1216 * count of equally good routers.*/
1221 "Found %d servers that might support %d/%d pending connections.",
1222 n_best_support
, best_support
>= 0 ? best_support
: 0,
1223 n_pending_connections
);
1225 preferredexits
= smartlist_create();
1226 add_nickname_list_to_smartlist(preferredexits
,options
->ExitNodes
,1,1,1);
1228 excludedexits
= smartlist_create();
1229 add_nickname_list_to_smartlist(excludedexits
,options
->ExcludeNodes
,0,0,1);
1231 sl
= smartlist_create();
1233 /* If any routers definitely support any pending connections, choose one
1235 if (best_support
> 0) {
1236 for (i
= 0; i
< smartlist_len(dir
->routers
); i
++)
1237 if (n_supported
[i
] == best_support
)
1238 smartlist_add(sl
, smartlist_get(dir
->routers
, i
));
1240 smartlist_subtract(sl
,excludedexits
);
1241 if (options
->StrictExitNodes
|| smartlist_overlap(sl
,preferredexits
))
1242 smartlist_intersect(sl
,preferredexits
);
1243 router
= routerlist_sl_choose_by_bandwidth(sl
, 1);
1245 /* Either there are no pending connections, or no routers even seem to
1246 * possibly support any of them. Choose a router at random that satisfies
1247 * at least one predicted exit port. */
1250 smartlist_t
*needed_ports
= circuit_get_unhandled_ports(time(NULL
));
1252 if (best_support
== -1) {
1253 if (need_uptime
|| need_capacity
) {
1255 "We couldn't find any live%s%s routers; falling back "
1256 "to list of all routers.",
1257 need_capacity
?", fast":"",
1258 need_uptime
?", stable":"");
1259 smartlist_free(preferredexits
);
1260 smartlist_free(excludedexits
);
1262 tor_free(n_supported
);
1263 return choose_good_exit_server_general(dir
, 0, 0);
1265 log_notice(LD_CIRC
, "All routers are down or won't exit -- choosing a "
1266 "doomed exit at random.");
1268 for (try = 0; try < 2; try++) {
1269 /* try once to pick only from routers that satisfy a needed port,
1270 * then if there are none, pick from any that support exiting. */
1271 for (i
= 0; i
< smartlist_len(dir
->routers
); i
++) {
1272 router
= smartlist_get(dir
->routers
, i
);
1273 if (n_supported
[i
] != -1 &&
1274 (try || router_handles_some_port(router
, needed_ports
))) {
1275 // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
1276 // try, router->nickname);
1277 smartlist_add(sl
, router
);
1281 smartlist_subtract(sl
,excludedexits
);
1282 if (options
->StrictExitNodes
|| smartlist_overlap(sl
,preferredexits
))
1283 smartlist_intersect(sl
,preferredexits
);
1284 /* XXX sometimes the above results in null, when the requested
1285 * exit node is down. we should pick it anyway. */
1286 router
= routerlist_sl_choose_by_bandwidth(sl
, 1);
1290 SMARTLIST_FOREACH(needed_ports
, uint16_t *, cp
, tor_free(cp
));
1291 smartlist_free(needed_ports
);
1294 smartlist_free(preferredexits
);
1295 smartlist_free(excludedexits
);
1297 tor_free(n_supported
);
1299 log_info(LD_CIRC
, "Chose exit server '%s'", router
->nickname
);
1302 if (options
->StrictExitNodes
) {
1304 "No specified exit routers seem to be running, and "
1305 "StrictExitNodes is set: can't choose an exit.");
1310 /** Return a pointer to a suitable router to be the exit node for the
1311 * circuit of purpose <b>purpose</b> that we're about to build (or NULL
1312 * if no router is suitable).
1314 * For general-purpose circuits, pass it off to
1315 * choose_good_exit_server_general()
1317 * For client-side rendezvous circuits, choose a random node, weighted
1318 * toward the preferences in 'options'.
1320 static routerinfo_t
*
1321 choose_good_exit_server(uint8_t purpose
, routerlist_t
*dir
,
1322 int need_uptime
, int need_capacity
, int is_internal
)
1324 or_options_t
*options
= get_options();
1326 case CIRCUIT_PURPOSE_C_GENERAL
:
1327 if (is_internal
) /* pick it like a middle hop */
1328 return router_choose_random_node(NULL
, get_options()->ExcludeNodes
,
1329 NULL
, need_uptime
, need_capacity
, 0,
1330 get_options()->_AllowInvalid
& ALLOW_INVALID_MIDDLE
, 0, 0);
1332 return choose_good_exit_server_general(dir
,need_uptime
,need_capacity
);
1333 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
1334 return router_choose_random_node(
1335 options
->RendNodes
, options
->RendExcludeNodes
,
1336 NULL
, need_uptime
, need_capacity
, 0,
1337 options
->_AllowInvalid
& ALLOW_INVALID_RENDEZVOUS
, 0, 0);
1339 log_warn(LD_BUG
,"Bug: unhandled purpose %d", purpose
);
1340 tor_fragile_assert();
1344 /** Decide a suitable length for circ's cpath, and pick an exit
1345 * router (or use <b>exit</b> if provided). Store these in the
1346 * cpath. Return 0 if ok, -1 if circuit should be closed. */
1348 onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
1350 cpath_build_state_t
*state
= circ
->build_state
;
1351 routerlist_t
*rl
= router_get_routerlist();
1353 if (state
->onehop_tunnel
) {
1354 log_debug(LD_CIRC
, "Launching a one-hop circuit for dir tunnel.");
1355 state
->desired_path_len
= 1;
1357 int r
= new_route_len(get_options()->PathlenCoinWeight
,
1358 circ
->_base
.purpose
, exit
, rl
->routers
);
1359 if (r
< 1) /* must be at least 1 */
1361 state
->desired_path_len
= r
;
1364 if (exit
) { /* the circuit-builder pre-requested one */
1365 log_info(LD_CIRC
,"Using requested exit node '%s'", exit
->nickname
);
1366 exit
= extend_info_dup(exit
);
1367 } else { /* we have to decide one */
1368 routerinfo_t
*router
=
1369 choose_good_exit_server(circ
->_base
.purpose
, rl
, state
->need_uptime
,
1370 state
->need_capacity
, state
->is_internal
);
1372 log_warn(LD_CIRC
,"failed to choose an exit server");
1375 exit
= extend_info_from_router(router
);
1377 state
->chosen_exit
= exit
;
1381 /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
1382 * hop to the cpath reflecting this. Don't send the next extend cell --
1383 * the caller will do this if it wants to.
1386 circuit_append_new_exit(origin_circuit_t
*circ
, extend_info_t
*info
)
1388 cpath_build_state_t
*state
;
1392 state
= circ
->build_state
;
1394 if (state
->chosen_exit
)
1395 extend_info_free(state
->chosen_exit
);
1396 state
->chosen_exit
= extend_info_dup(info
);
1398 ++circ
->build_state
->desired_path_len
;
1399 onion_append_hop(&circ
->cpath
, info
);
1403 /** Take an open <b>circ</b>, and add a new hop at the end, based on
1404 * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
1405 * send the next extend cell to begin connecting to that hop.
1408 circuit_extend_to_new_exit(origin_circuit_t
*circ
, extend_info_t
*info
)
1411 circuit_append_new_exit(circ
, info
);
1412 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
1413 if ((err_reason
= circuit_send_next_onion_skin(circ
))<0) {
1414 log_warn(LD_CIRC
, "Couldn't extend circuit to new point '%s'.",
1416 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
1422 /** Return the number of routers in <b>routers</b> that are currently up
1423 * and available for building circuits through.
1426 count_acceptable_routers(smartlist_t
*routers
)
1432 n
= smartlist_len(routers
);
1434 r
= smartlist_get(routers
, i
);
1435 // log_debug(LD_CIRC,
1436 // "Contemplating whether router %d (%s) is a new option.",
1438 if (r
->is_running
== 0) {
1439 // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
1442 if (r
->is_valid
== 0) {
1443 // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
1445 /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
1446 * allows this node in some places, then we're getting an inaccurate
1447 * count. For now, be conservative and don't count it. But later we
1448 * should try to be smarter. */
1451 // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
1453 ; /* C requires an explicit statement after the label */
1459 /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
1460 * This function is used to extend cpath by another hop.
1463 onion_append_to_cpath(crypt_path_t
**head_ptr
, crypt_path_t
*new_hop
)
1466 new_hop
->next
= (*head_ptr
);
1467 new_hop
->prev
= (*head_ptr
)->prev
;
1468 (*head_ptr
)->prev
->next
= new_hop
;
1469 (*head_ptr
)->prev
= new_hop
;
1471 *head_ptr
= new_hop
;
1472 new_hop
->prev
= new_hop
->next
= new_hop
;
1476 /** Pick a random server digest that's running a Tor version that
1477 * doesn't have the reachability bug. These are versions 0.1.1.21-cvs+
1478 * and 0.1.2.1-alpha+. Avoid picking authorities, since we're
1479 * probably already connected to them.
1481 * We only return one, so this doesn't become stupid when the
1482 * whole network has upgraded. */
1484 compute_preferred_testing_list(const char *answer
)
1486 smartlist_t
*choices
;
1487 routerlist_t
*rl
= router_get_routerlist();
1488 routerinfo_t
*router
;
1491 if (answer
) /* they have one in mind -- easy */
1492 return tor_strdup(answer
);
1494 choices
= smartlist_create();
1495 /* now count up our choices */
1496 SMARTLIST_FOREACH(rl
->routers
, routerinfo_t
*, r
,
1497 if (r
->is_running
&& r
->is_valid
&&
1498 ((tor_version_as_new_as(r
->platform
,"0.1.1.21-cvs") &&
1499 !tor_version_as_new_as(r
->platform
,"0.1.2.0-alpha-cvs")) ||
1500 tor_version_as_new_as(r
->platform
,"0.1.2.1-alpha")) &&
1501 !is_local_IP(r
->addr
) &&
1502 !router_get_trusteddirserver_by_digest(r
->cache_info
.identity_digest
))
1503 smartlist_add(choices
, r
));
1504 router
= smartlist_choose(choices
);
1505 smartlist_free(choices
);
1507 log_info(LD_CIRC
, "Looking for middle server that doesn't have the "
1508 "reachability bug, but didn't find one. Oh well.");
1511 log_info(LD_CIRC
, "Looking for middle server that doesn't have the "
1512 "reachability bug, and chose '%s'. Great.", router
->nickname
);
1513 s
= tor_malloc(HEX_DIGEST_LEN
+2);
1515 base16_encode(s
+1, HEX_DIGEST_LEN
+1,
1516 router
->cache_info
.identity_digest
, DIGEST_LEN
);
1520 /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
1521 * and <b>state</b> and the cpath <b>head</b> (currently populated only
1522 * to length <b>cur_len</b> to decide a suitable middle hop for a
1523 * circuit. In particular, make sure we don't pick the exit node or its
1524 * family, and make sure we don't duplicate any previous nodes or their
1526 static routerinfo_t
*
1527 choose_good_middle_server(uint8_t purpose
,
1528 cpath_build_state_t
*state
,
1533 routerinfo_t
*r
, *choice
;
1534 crypt_path_t
*cpath
;
1535 smartlist_t
*excluded
;
1536 or_options_t
*options
= get_options();
1537 char *preferred
= NULL
;
1538 tor_assert(_CIRCUIT_PURPOSE_MIN
<= purpose
&&
1539 purpose
<= _CIRCUIT_PURPOSE_MAX
);
1541 log_debug(LD_CIRC
, "Contemplating intermediate hop: random choice.");
1542 excluded
= smartlist_create();
1543 if ((r
= build_state_get_exit_router(state
))) {
1544 smartlist_add(excluded
, r
);
1545 routerlist_add_family(excluded
, r
);
1547 if ((r
= routerlist_find_my_routerinfo())) {
1548 smartlist_add(excluded
, r
);
1549 routerlist_add_family(excluded
, r
);
1551 for (i
= 0, cpath
= head
; i
< cur_len
; ++i
, cpath
=cpath
->next
) {
1552 if ((r
= router_get_by_digest(cpath
->extend_info
->identity_digest
))) {
1553 smartlist_add(excluded
, r
);
1554 routerlist_add_family(excluded
, r
);
1557 if (purpose
== CIRCUIT_PURPOSE_TESTING
)
1558 preferred
= compute_preferred_testing_list(options
->TestVia
);
1559 choice
= router_choose_random_node(preferred
,
1560 options
->ExcludeNodes
, excluded
,
1561 state
->need_uptime
, state
->need_capacity
, 0,
1562 options
->_AllowInvalid
& ALLOW_INVALID_MIDDLE
, 0, 0);
1564 tor_free(preferred
);
1565 smartlist_free(excluded
);
1569 /** Pick a good entry server for the circuit to be built according to
1570 * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
1571 * router (if we're an OR), and respect firewall settings; if we're
1572 * using entry_guards, return one.
1574 * If <b>state</b> is NULL, we're choosing routers to serve as entry
1575 * nodes, not for any particular circuit.
1577 static routerinfo_t
*
1578 choose_good_entry_server(uint8_t purpose
, cpath_build_state_t
*state
)
1580 routerinfo_t
*r
, *choice
;
1581 smartlist_t
*excluded
;
1582 or_options_t
*options
= get_options();
1583 (void)purpose
; /* not used yet. */
1585 if (state
&& options
->UseEntryGuards
) {
1586 return choose_random_entry(state
);
1589 excluded
= smartlist_create();
1591 if (state
&& (r
= build_state_get_exit_router(state
))) {
1592 smartlist_add(excluded
, r
);
1593 routerlist_add_family(excluded
, r
);
1595 if ((r
= routerlist_find_my_routerinfo())) {
1596 smartlist_add(excluded
, r
);
1597 routerlist_add_family(excluded
, r
);
1599 if (firewall_is_fascist_or()) {
1600 /* exclude all ORs that listen on the wrong port */
1601 routerlist_t
*rl
= router_get_routerlist();
1604 for (i
=0; i
< smartlist_len(rl
->routers
); i
++) {
1605 r
= smartlist_get(rl
->routers
, i
);
1606 if (!fascist_firewall_allows_address_or(r
->addr
,r
->or_port
))
1607 smartlist_add(excluded
, r
);
1610 /* and exclude current entry guards, if applicable */
1611 if (options
->UseEntryGuards
&& entry_guards
) {
1612 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
1614 if ((r
= router_get_by_digest(entry
->identity
)))
1615 smartlist_add(excluded
, r
);
1619 choice
= router_choose_random_node(
1620 NULL
, options
->ExcludeNodes
,
1621 excluded
, state
? state
->need_uptime
: 0,
1622 state
? state
->need_capacity
: 0,
1624 options
->_AllowInvalid
& ALLOW_INVALID_ENTRY
, 0, 0);
1625 smartlist_free(excluded
);
1629 /** Return the first non-open hop in cpath, or return NULL if all
1631 static crypt_path_t
*
1632 onion_next_hop_in_cpath(crypt_path_t
*cpath
)
1634 crypt_path_t
*hop
= cpath
;
1636 if (hop
->state
!= CPATH_STATE_OPEN
)
1639 } while (hop
!= cpath
);
1643 /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
1644 * based on <b>state</b>. Append the hop info to head_ptr.
1647 onion_extend_cpath(origin_circuit_t
*circ
)
1649 uint8_t purpose
= circ
->_base
.purpose
;
1650 cpath_build_state_t
*state
= circ
->build_state
;
1651 int cur_len
= circuit_get_cpath_len(circ
);
1652 extend_info_t
*info
= NULL
;
1654 if (cur_len
>= state
->desired_path_len
) {
1655 log_debug(LD_CIRC
, "Path is complete: %d steps long",
1656 state
->desired_path_len
);
1660 log_debug(LD_CIRC
, "Path is %d long; we want %d", cur_len
,
1661 state
->desired_path_len
);
1663 if (cur_len
== state
->desired_path_len
- 1) { /* Picking last node */
1664 info
= extend_info_dup(state
->chosen_exit
);
1665 } else if (cur_len
== 0) { /* picking first node */
1666 routerinfo_t
*r
= choose_good_entry_server(purpose
, state
);
1668 info
= extend_info_from_router(r
);
1671 choose_good_middle_server(purpose
, state
, circ
->cpath
, cur_len
);
1673 info
= extend_info_from_router(r
);
1677 log_warn(LD_CIRC
,"Failed to find node for hop %d of our path. Discarding "
1678 "this circuit.", cur_len
);
1682 log_debug(LD_CIRC
,"Chose router %s for hop %d (exit is %s)",
1683 info
->nickname
, cur_len
+1, build_state_get_exit_nickname(state
));
1685 onion_append_hop(&circ
->cpath
, info
);
1686 extend_info_free(info
);
1690 /** Create a new hop, annotate it with information about its
1691 * corresponding router <b>choice</b>, and append it to the
1692 * end of the cpath <b>head_ptr</b>. */
1694 onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
)
1696 crypt_path_t
*hop
= tor_malloc_zero(sizeof(crypt_path_t
));
1698 /* link hop into the cpath, at the end. */
1699 onion_append_to_cpath(head_ptr
, hop
);
1701 hop
->magic
= CRYPT_PATH_MAGIC
;
1702 hop
->state
= CPATH_STATE_CLOSED
;
1704 hop
->extend_info
= extend_info_dup(choice
);
1706 hop
->package_window
= CIRCWINDOW_START
;
1707 hop
->deliver_window
= CIRCWINDOW_START
;
1712 /** Allocate and return a new extend_info_t that can be used to build a
1713 * circuit to or through the router <b>r</b>. */
1715 extend_info_from_router(routerinfo_t
*r
)
1717 extend_info_t
*info
;
1719 info
= tor_malloc_zero(sizeof(extend_info_t
));
1720 strlcpy(info
->nickname
, r
->nickname
, sizeof(info
->nickname
));
1721 memcpy(info
->identity_digest
, r
->cache_info
.identity_digest
, DIGEST_LEN
);
1722 info
->onion_key
= crypto_pk_dup_key(r
->onion_pkey
);
1723 info
->addr
= r
->addr
;
1724 info
->port
= r
->or_port
;
1728 /** Allocate and return a new extend_info_t that can be used to build a
1729 * circuit to or through the router <b>r</b>. */
1731 extend_info_from_routerstatus(routerstatus_t
*s
)
1733 extend_info_t
*info
;
1735 info
= tor_malloc_zero(sizeof(extend_info_t
));
1736 strlcpy(info
->nickname
, s
->nickname
, sizeof(info
->nickname
));
1737 memcpy(info
->identity_digest
, s
->identity_digest
, DIGEST_LEN
);
1738 info
->onion_key
= NULL
; /* routerstatus doesn't include this! */
1739 info
->addr
= s
->addr
;
1740 info
->port
= s
->or_port
;
1744 /** Release storage held by an extend_info_t struct. */
1746 extend_info_free(extend_info_t
*info
)
1749 if (info
->onion_key
)
1750 crypto_free_pk_env(info
->onion_key
);
1754 /** Allocate and return a new extend_info_t with the same contents as
1757 extend_info_dup(extend_info_t
*info
)
1759 extend_info_t
*newinfo
;
1761 newinfo
= tor_malloc(sizeof(extend_info_t
));
1762 memcpy(newinfo
, info
, sizeof(extend_info_t
));
1763 if (info
->onion_key
)
1764 newinfo
->onion_key
= crypto_pk_dup_key(info
->onion_key
);
1766 newinfo
->onion_key
= NULL
;
1770 /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
1771 * If there is no chosen exit, or if we don't know the routerinfo_t for
1772 * the chosen exit, return NULL.
1775 build_state_get_exit_router(cpath_build_state_t
*state
)
1777 if (!state
|| !state
->chosen_exit
)
1779 return router_get_by_digest(state
->chosen_exit
->identity_digest
);
1782 /** Return the nickname for the chosen exit router in <b>state</b>. If
1783 * there is no chosen exit, or if we don't know the routerinfo_t for the
1784 * chosen exit, return NULL.
1787 build_state_get_exit_nickname(cpath_build_state_t
*state
)
1789 if (!state
|| !state
->chosen_exit
)
1791 return state
->chosen_exit
->nickname
;
1794 /** Check whether the entry guard <b>e</b> is usable, given the directory
1795 * authorities' opinion about the rouer (stored in <b>ri</b>) and the user's
1796 * configuration (in <b>options</b>). Set <b>e</b>->bad_since
1797 * accordingly. Return true iff the entry guard's status changes. */
1799 entry_guard_set_status(entry_guard_t
*e
, routerinfo_t
*ri
,
1800 time_t now
, or_options_t
*options
)
1802 const char *reason
= NULL
;
1803 char buf
[HEX_DIGEST_LEN
+1];
1806 tor_assert(options
);
1808 /* Do we want to mark this guard as bad? */
1810 reason
= "unlisted";
1811 else if (!ri
->is_running
)
1813 else if (!ri
->is_possible_guard
&&
1814 !router_nickname_is_in_list(ri
, options
->EntryNodes
))
1815 reason
= "not recommended as a guard";
1816 else if (router_nickname_is_in_list(ri
, options
->ExcludeNodes
))
1817 reason
= "excluded";
1819 if (reason
&& ! e
->bad_since
) {
1820 /* Router is newly bad. */
1821 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
1822 log_info(LD_CIRC
, "Entry guard %s (%s) is %s: marking as unusable.",
1823 e
->nickname
, buf
, reason
);
1826 control_event_guard(e
->nickname
, e
->identity
, "BAD");
1828 } else if (!reason
&& e
->bad_since
) {
1829 /* There's nothing wrong with the router any more. */
1830 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
1831 log_info(LD_CIRC
, "Entry guard %s (%s) is no longer unusable: "
1832 "marking as ok.", e
->nickname
, buf
);
1835 control_event_guard(e
->nickname
, e
->identity
, "GOOD");
1842 /** Return true iff enough time has passed since we last tried connect to the
1843 * unreachable guard <b>e</b> that we're willing to try again. */
1845 entry_is_time_to_retry(entry_guard_t
*e
, time_t now
)
1848 if (e
->last_attempted
< e
->unreachable_since
)
1850 diff
= now
- e
->unreachable_since
;
1852 return now
> (e
->last_attempted
+ 60*60);
1853 else if (diff
< 3*24*60*60)
1854 return now
> (e
->last_attempted
+ 4*60*60);
1855 else if (diff
< 7*24*60*60)
1856 return now
> (e
->last_attempted
+ 18*60*60);
1858 return now
> (e
->last_attempted
+ 36*60*60);
1861 /** Return the router corresponding to <b>e</b>, if <b>e</b> is
1862 * working well enough that we are willing to use it as an entry
1863 * right now. (Else return NULL.) In particular, it must be
1864 * - Listed as either up or never yet contacted;
1865 * - Present in the routerlist;
1866 * - Listed as 'stable' or 'fast' by the current dirserver concensus,
1867 * if demanded by <b>need_uptime</b> or <b>need_capacity</b>;
1868 * (This check is currently redundant with the Guard flag, but in
1869 * the future that might change. Best to leave it in for now.)
1870 * - Allowed by our current ReachableAddresses config option; and
1871 * - Currently thought to be reachable by us (unless assume_reachable
1874 static INLINE routerinfo_t
*
1875 entry_is_live(entry_guard_t
*e
, int need_uptime
, int need_capacity
,
1876 int assume_reachable
)
1881 if (!assume_reachable
&&
1882 e
->unreachable_since
&& !entry_is_time_to_retry(e
, time(NULL
)))
1884 r
= router_get_by_digest(e
->identity
);
1887 if (router_is_unreliable(r
, need_uptime
, need_capacity
, 0))
1889 if (firewall_is_fascist_or() &&
1890 !fascist_firewall_allows_address_or(r
->addr
,r
->or_port
))
1895 /** Return the number of entry guards that we think are usable. */
1897 num_live_entry_guards(void)
1902 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
1904 if (entry_is_live(entry
, 0, 1, 0))
1910 /** Return 1 if <b>digest</b> matches the identity of any node
1911 * in the entry_guards list. Else return 0. */
1913 is_an_entry_guard(const char *digest
)
1915 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
1916 if (!memcmp(digest
, entry
->identity
, DIGEST_LEN
))
1922 /** Dump a description of our list of entry guards to the log at level
1923 * <b>severity</b>. */
1925 log_entry_guards(int severity
)
1927 smartlist_t
*elements
= smartlist_create();
1931 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
1933 tor_snprintf(buf
, sizeof(buf
), "%s (%s%s)",
1935 e
->bad_since
? "down " : "up ",
1936 e
->made_contact
? "made-contact" : "never-contacted");
1937 smartlist_add(elements
, tor_strdup(buf
));
1940 s
= smartlist_join_strings(elements
, ",", 0, NULL
);
1941 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
1942 smartlist_free(elements
);
1943 log_fn(severity
,LD_CIRC
,"%s",s
);
1947 /** Called when one or more guards that we would previously have used for some
1948 * purpose are no longer in use because a higher-priority guard has become
1951 control_event_guard_deferred(void)
1953 /* XXXX We don't actually have a good way to figure out _how many_ entries
1954 * are live for some purpose. We need an entry_is_even_slightly_live()
1955 * function for this to work right. NumEntryGuards isn't reliable: if we
1956 * need guards with weird properties, we can have more than that number
1961 or_options_t
*options
= get_options();
1964 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
1966 if (entry_is_live(entry
, 0, 1, 0)) {
1967 if (n
++ == options
->NumEntryGuards
) {
1968 control_event_guard(entry
->nickname
, entry
->identity
, "DEFERRED");
1977 #define NUM_ENTRY_PICK_TRIES 100
1979 /** Add a new (preferably stable and fast) router to our
1980 * entry_guards list. Return a pointer to the router if we succeed,
1981 * or NULL if we can't find any more suitable entries.
1983 * If <b>chosen</b> is defined, use that one, and if it's not
1984 * already in our entry_guards list, put it at the *beginning*.
1985 * Else, put the one we pick at the end of the list. */
1986 static routerinfo_t
*
1987 add_an_entry_guard(routerinfo_t
*chosen
)
1989 routerinfo_t
*router
;
1990 entry_guard_t
*entry
;
1994 if (is_an_entry_guard(router
->cache_info
.identity_digest
))
1997 router
= choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL
, NULL
);
2001 entry
= tor_malloc_zero(sizeof(entry_guard_t
));
2002 log_info(LD_CIRC
, "Chose '%s' as new entry guard.", router
->nickname
);
2003 strlcpy(entry
->nickname
, router
->nickname
, sizeof(entry
->nickname
));
2004 memcpy(entry
->identity
, router
->cache_info
.identity_digest
, DIGEST_LEN
);
2005 if (chosen
) /* prepend */
2006 smartlist_insert(entry_guards
, 0, entry
);
2008 smartlist_add(entry_guards
, entry
);
2009 control_event_guard(entry
->nickname
, entry
->identity
, "NEW");
2010 control_event_guard_deferred();
2011 log_entry_guards(LOG_INFO
);
2015 /** If the use of entry guards is configured, choose more entry guards
2016 * until we have enough in the list. */
2018 pick_entry_guards(void)
2020 or_options_t
*options
= get_options();
2023 tor_assert(entry_guards
);
2025 while (num_live_entry_guards() < options
->NumEntryGuards
) {
2026 if (!add_an_entry_guard(NULL
))
2031 entry_guards_changed();
2034 /** Release all storage held by the list of entry guards. */
2036 entry_guards_free_all(void)
2039 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, tor_free(e
));
2040 smartlist_free(entry_guards
);
2041 entry_guards
= NULL
;
2045 /** How long (in seconds) do we allow an entry guard to be nonfunctional,
2046 * unlisted, excluded, or otherwise nonusable before we give up on it? */
2047 #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
2049 /** Remove all entry guards that have been down or unlisted for so
2050 * long that we don't think they'll come up again. Return 1 if we
2051 * removed any, or 0 if we did nothing. */
2053 remove_dead_entries(void)
2055 char dbuf
[HEX_DIGEST_LEN
+1];
2056 char tbuf
[ISO_TIME_LEN
+1];
2057 time_t now
= time(NULL
);
2061 for (i
= 0; i
< smartlist_len(entry_guards
); ) {
2062 entry_guard_t
*entry
= smartlist_get(entry_guards
, i
);
2063 if (entry
->bad_since
&&
2064 entry
->bad_since
+ ENTRY_GUARD_REMOVE_AFTER
< now
) {
2066 base16_encode(dbuf
, sizeof(dbuf
), entry
->identity
, DIGEST_LEN
);
2067 format_local_iso_time(tbuf
, entry
->bad_since
);
2068 log_info(LD_CIRC
, "Entry guard '%s' (%s) has been down or unlisted "
2069 "since %s local time; removing.",
2070 entry
->nickname
, dbuf
, tbuf
);
2071 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
2073 smartlist_del_keeporder(entry_guards
, i
);
2074 log_entry_guards(LOG_INFO
);
2079 return changed
? 1 : 0;
2082 /** A new directory or router-status has arrived; update the down/listed
2083 * status of the entry guards.
2085 * An entry is 'down' if the directory lists it as nonrunning.
2086 * An entry is 'unlisted' if the directory doesn't include it.
2089 entry_guards_compute_status(void)
2091 /* Don't call this on startup; only on a fresh download. Otherwise we'll
2092 * think that things are unlisted. */
2095 int severity
= LOG_INFO
;
2096 or_options_t
*options
;
2100 options
= get_options();
2104 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
2106 routerinfo_t
*r
= router_get_by_digest(entry
->identity
);
2107 if (entry_guard_set_status(entry
, r
, now
, options
))
2110 log_info(LD_CIRC
, "Summary: Entry '%s' is %s, %s and %s.",
2112 entry
->unreachable_since
? "unreachable" : "reachable",
2113 entry
->bad_since
? "unusable" : "usable",
2114 entry_is_live(entry
, 0, 1, 0) ? "live" : "not live");
2117 if (remove_dead_entries())
2121 log_fn(severity
, LD_CIRC
, " (%d/%d entry guards are usable/new)",
2122 num_live_entry_guards(), smartlist_len(entry_guards
));
2123 log_entry_guards(LOG_INFO
);
2124 entry_guards_changed();
2128 /** Called when a connection to an OR with the identity digest <b>digest</b>
2129 * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0).
2130 * If the OR is an entry, change that entry's up/down status.
2131 * Return 0 normally, or -1 if we want to tear down the new connection.
2134 entry_guard_register_connect_status(const char *digest
, int succeeded
,
2138 int refuse_conn
= 0;
2139 int first_contact
= 0;
2140 entry_guard_t
*entry
= NULL
;
2142 char buf
[HEX_DIGEST_LEN
+1];
2147 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2149 if (!memcmp(e
->identity
, digest
, DIGEST_LEN
)) {
2159 base16_encode(buf
, sizeof(buf
), entry
->identity
, DIGEST_LEN
);
2162 if (entry
->unreachable_since
) {
2163 log_info(LD_CIRC
, "Entry guard '%s' (%s) is now reachable again. Good.",
2164 entry
->nickname
, buf
);
2165 entry
->unreachable_since
= 0;
2166 entry
->last_attempted
= now
;
2167 control_event_guard(entry
->nickname
, entry
->identity
, "UP");
2170 if (!entry
->made_contact
) {
2171 entry
->made_contact
= 1;
2172 first_contact
= changed
= 1;
2174 } else { /* ! succeeded */
2175 if (!entry
->made_contact
) {
2176 /* We've never connected to this one. */
2178 "Connection to never-contacted entry guard '%s' (%s) failed. "
2179 "Removing from the list. %d/%d entry guards usable/new.",
2180 entry
->nickname
, buf
,
2181 num_live_entry_guards()-1, smartlist_len(entry_guards
)-1);
2183 smartlist_del_keeporder(entry_guards
, idx
);
2184 log_entry_guards(LOG_INFO
);
2186 } else if (!entry
->unreachable_since
) {
2187 log_info(LD_CIRC
, "Unable to connect to entry guard '%s' (%s). "
2188 "Marking as unreachable.", entry
->nickname
, buf
);
2189 entry
->unreachable_since
= entry
->last_attempted
= now
;
2190 control_event_guard(entry
->nickname
, entry
->identity
, "DOWN");
2193 char tbuf
[ISO_TIME_LEN
+1];
2194 format_iso_time(tbuf
, entry
->unreachable_since
);
2195 log_debug(LD_CIRC
, "Failed to connect to unreachable entry guard "
2196 "'%s' (%s). It has been unreachable since %s.",
2197 entry
->nickname
, buf
, tbuf
);
2198 entry
->last_attempted
= now
;
2202 if (first_contact
) {
2203 /* We've just added a new long-term entry guard. Perhaps the network just
2204 * came back? We should give our earlier entries another try too,
2205 * and close this connection so we don't use it before we've given
2206 * the others a shot. */
2207 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, {
2211 if (e
->made_contact
) {
2212 r
= entry_is_live(e
, 0, 1, 1);
2213 if (r
&& !r
->is_running
) {
2215 /* XXXX012 I think this might be broken; when picking entry nodes,
2216 * we only look at unreachable_since and is_time_to_retry, and we
2217 * pay no attention to is_running. If this is indeed the case, we
2218 * can fix the bug by adding a retry_as_entry flag to
2219 * routerinfo_t. -NM */
2226 "Connected to new entry guard '%s' (%s). Marking earlier "
2227 "entry guards up. %d/%d entry guards usable/new.",
2228 entry
->nickname
, buf
,
2229 num_live_entry_guards(), smartlist_len(entry_guards
));
2230 log_entry_guards(LOG_INFO
);
2236 entry_guards_changed();
2237 return refuse_conn
? -1 : 0;
2240 /** When we try to choose an entry guard, should we parse and add
2241 * config's EntryNodes first? */
2242 static int should_add_entry_nodes
= 0;
2244 /** Called when the value of EntryNodes changes in our configuration. */
2246 entry_nodes_should_be_added(void)
2248 log_info(LD_CIRC
, "New EntryNodes config option detected. Will use.");
2249 should_add_entry_nodes
= 1;
2252 /** Add all nodes in EntryNodes that aren't currently guard nodes to the list
2253 * of guard nodes, at the front. */
2255 entry_guards_prepend_from_config(void)
2257 int missed_some
= 0;
2259 or_options_t
*options
= get_options();
2260 smartlist_t
*routers
= smartlist_create();
2261 smartlist_t
*tmp
= smartlist_create();
2263 tor_assert(entry_guards
);
2264 tor_assert(options
->EntryNodes
);
2266 if (options
->StrictEntryNodes
) {
2267 log_info(LD_CIRC
,"Clearing old entry guards");
2268 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, tor_free(e
));
2269 smartlist_clear(entry_guards
);
2270 entry_guards_changed();
2273 add_nickname_list_to_smartlist(routers
, options
->EntryNodes
,
2276 /* take a moment first to notice whether we got them all */
2277 log_info(LD_CIRC
,"Adding configured EntryNodes '%s'.",
2278 options
->EntryNodes
);
2279 smartlist_split_string(tmp
, options
->EntryNodes
, ",",
2280 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
2281 missed_some
= smartlist_len(routers
) != smartlist_len(tmp
);
2282 SMARTLIST_FOREACH(tmp
, char *, nick
, tor_free(nick
));
2283 smartlist_free(tmp
);
2285 for (idx
= smartlist_len(routers
)-1 ; idx
>= 0; idx
--) {
2286 /* pick off the last one, turn it into a router, prepend it
2287 * to our entry_guards list. If we can't find it, set missed_some
2289 routerinfo_t
*r
= smartlist_get(routers
, idx
);
2290 add_an_entry_guard(r
);
2294 should_add_entry_nodes
= 0; /* whew, we're done */
2296 smartlist_free(routers
);
2299 /** Pick a live (up and listed) entry guard from entry_guards, and
2300 * make sure not to pick this circuit's exit. */
2301 static routerinfo_t
*
2302 choose_random_entry(cpath_build_state_t
*state
)
2304 or_options_t
*options
= get_options();
2305 smartlist_t
*live_entry_guards
= smartlist_create();
2306 routerinfo_t
*chosen_exit
= build_state_get_exit_router(state
);
2307 routerinfo_t
*r
= NULL
;
2308 int need_uptime
= state
->need_uptime
;
2309 int need_capacity
= state
->need_capacity
;
2312 entry_guards
= smartlist_create();
2314 if (should_add_entry_nodes
)
2315 entry_guards_prepend_from_config();
2317 if (!options
->StrictEntryNodes
&&
2319 smartlist_len(entry_guards
) < options
->NumEntryGuards
))
2320 pick_entry_guards();
2323 smartlist_clear(live_entry_guards
);
2324 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
2326 r
= entry_is_live(entry
, need_uptime
, need_capacity
, 0);
2327 if (r
&& r
!= chosen_exit
) {
2328 smartlist_add(live_entry_guards
, r
);
2329 if (smartlist_len(live_entry_guards
) >= options
->NumEntryGuards
)
2330 break; /* we have enough */
2334 /* Try to have at least 2 choices available. This way we don't
2335 * get stuck with a single live-but-crummy entry and just keep
2337 * (We might get 2 live-but-crummy entry guards, but so be it.) */
2338 if (smartlist_len(live_entry_guards
) < 2) {
2339 if (!options
->StrictEntryNodes
) {
2340 /* still no? try adding a new entry then */
2341 /* XXX if guard doesn't imply fast and stable, then we need
2342 * to tell add_an_entry_guard below what we want, or it might
2343 * be a long time til we get it. -RD */
2344 r
= add_an_entry_guard(NULL
);
2346 smartlist_add(live_entry_guards
, r
);
2347 entry_guards_changed();
2350 if (!r
&& need_uptime
) {
2351 need_uptime
= 0; /* try without that requirement */
2354 if (!r
&& need_capacity
) {
2355 /* still no? last attempt, try without requiring capacity */
2359 /* live_entry_guards will be empty below. Oh well, we tried. */
2362 r
= smartlist_choose(live_entry_guards
);
2363 smartlist_free(live_entry_guards
);
2367 /** Parse <b>state</b> and learn about the entry guards it describes.
2368 * If <b>set</b> is true, and there are no errors, replace the global
2369 * entry_list with what we find.
2370 * On success, return 0. On failure, alloc into *<b>msg</b> a string
2371 * describing the error, and return -1.
2374 entry_guards_parse_state(or_state_t
*state
, int set
, char **msg
)
2376 entry_guard_t
*node
= NULL
;
2377 smartlist_t
*new_entry_guards
= smartlist_create();
2378 config_line_t
*line
;
2381 for (line
= state
->EntryGuards
; line
; line
= line
->next
) {
2382 if (!strcasecmp(line
->key
, "EntryGuard")) {
2383 smartlist_t
*args
= smartlist_create();
2384 node
= tor_malloc_zero(sizeof(entry_guard_t
));
2385 /* all entry guards on disk have been contacted */
2386 node
->made_contact
= 1;
2387 smartlist_add(new_entry_guards
, node
);
2388 smartlist_split_string(args
, line
->value
, " ",
2389 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
2390 if (smartlist_len(args
)<2) {
2391 *msg
= tor_strdup("Unable to parse entry nodes: "
2392 "Too few arguments to EntryGuard");
2393 } else if (!is_legal_nickname(smartlist_get(args
,0))) {
2394 *msg
= tor_strdup("Unable to parse entry nodes: "
2395 "Bad nickname for EntryGuard");
2397 strlcpy(node
->nickname
, smartlist_get(args
,0), MAX_NICKNAME_LEN
+1);
2398 if (base16_decode(node
->identity
, DIGEST_LEN
, smartlist_get(args
,1),
2399 strlen(smartlist_get(args
,1)))<0) {
2400 *msg
= tor_strdup("Unable to parse entry nodes: "
2401 "Bad hex digest for EntryGuard");
2404 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
2405 smartlist_free(args
);
2410 time_t last_try
= 0;
2412 *msg
= tor_strdup("Unable to parse entry nodes: "
2413 "EntryGuardDownSince/UnlistedSince without EntryGuard");
2416 if (parse_iso_time(line
->value
, &when
)<0) {
2417 *msg
= tor_strdup("Unable to parse entry nodes: "
2418 "Bad time in EntryGuardDownSince/UnlistedSince");
2421 if (strlen(line
->value
) >= ISO_TIME_LEN
+ISO_TIME_LEN
+1) {
2422 /* ignore failure */
2423 parse_iso_time(line
->value
+ISO_TIME_LEN
+1, &last_try
);
2425 if (!strcasecmp(line
->key
, "EntryGuardDownSince")) {
2426 node
->unreachable_since
= when
;
2427 node
->last_attempted
= last_try
;
2429 node
->bad_since
= when
;
2435 SMARTLIST_FOREACH(new_entry_guards
, entry_guard_t
*, e
, tor_free(e
));
2436 smartlist_free(new_entry_guards
);
2437 } else { /* !*err && set */
2439 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, tor_free(e
));
2440 smartlist_free(entry_guards
);
2442 entry_guards
= new_entry_guards
;
2443 entry_guards_dirty
= 0;
2445 return *msg
? -1 : 0;
2448 /** Our list of entry guards has changed, or some element of one
2449 * of our entry guards has changed. Write the changes to disk within
2450 * the next few minutes.
2453 entry_guards_changed(void)
2456 entry_guards_dirty
= 1;
2458 /* or_state_save() will call entry_guards_update_state(). */
2459 when
= get_options()->AvoidDiskWrites
? time(NULL
) + 3600 : time(NULL
)+600;
2460 or_state_mark_dirty(get_or_state(), when
);
2463 /** If the entry guard info has not changed, do nothing and return.
2464 * Otherwise, free the EntryGuards piece of <b>state</b> and create
2465 * a new one out of the global entry_guards list, and then mark
2466 * <b>state</b> dirty so it will get saved to disk.
2469 entry_guards_update_state(or_state_t
*state
)
2471 config_line_t
**next
, *line
;
2472 if (! entry_guards_dirty
)
2475 config_free_lines(state
->EntryGuards
);
2476 next
= &state
->EntryGuards
;
2479 entry_guards
= smartlist_create();
2480 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2482 char dbuf
[HEX_DIGEST_LEN
+1];
2483 if (!e
->made_contact
)
2484 continue; /* don't write this one to disk */
2485 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2486 line
->key
= tor_strdup("EntryGuard");
2487 line
->value
= tor_malloc(HEX_DIGEST_LEN
+MAX_NICKNAME_LEN
+2);
2488 base16_encode(dbuf
, sizeof(dbuf
), e
->identity
, DIGEST_LEN
);
2489 tor_snprintf(line
->value
,HEX_DIGEST_LEN
+MAX_NICKNAME_LEN
+2,
2490 "%s %s", e
->nickname
, dbuf
);
2491 next
= &(line
->next
);
2492 if (e
->unreachable_since
) {
2493 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2494 line
->key
= tor_strdup("EntryGuardDownSince");
2495 line
->value
= tor_malloc(ISO_TIME_LEN
+1+ISO_TIME_LEN
+1);
2496 format_iso_time(line
->value
, e
->unreachable_since
);
2497 if (e
->last_attempted
) {
2498 line
->value
[ISO_TIME_LEN
] = ' ';
2499 format_iso_time(line
->value
+ISO_TIME_LEN
+1, e
->last_attempted
);
2501 next
= &(line
->next
);
2504 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
2505 line
->key
= tor_strdup("EntryGuardUnlistedSince");
2506 line
->value
= tor_malloc(ISO_TIME_LEN
+1);
2507 format_iso_time(line
->value
, e
->bad_since
);
2508 next
= &(line
->next
);
2511 if (!get_options()->AvoidDiskWrites
)
2512 or_state_mark_dirty(get_or_state(), 0);
2513 entry_guards_dirty
= 0;
2516 /** If <b>question</b> is the string "entry-guards", then dump
2517 * to *<b>answer</b> a newly allocated string describing all of
2518 * the nodes in the global entry_guards list. See control-spec.txt
2520 * For backward compatibility, we also handle the string "helper-nodes".
2523 getinfo_helper_entry_guards(control_connection_t
*conn
,
2524 const char *question
, char **answer
)
2526 int use_long_names
= conn
->use_long_names
;
2528 if (!strcmp(question
,"entry-guards") ||
2529 !strcmp(question
,"helper-nodes")) {
2530 smartlist_t
*sl
= smartlist_create();
2531 char tbuf
[ISO_TIME_LEN
+1];
2532 char nbuf
[MAX_VERBOSE_NICKNAME_LEN
+1];
2534 entry_guards
= smartlist_create();
2535 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
2537 size_t len
= MAX_VERBOSE_NICKNAME_LEN
+ISO_TIME_LEN
+32;
2538 char *c
= tor_malloc(len
);
2539 const char *status
= NULL
;
2541 if (!e
->made_contact
) {
2542 status
= "never-connected";
2543 } else if (e
->bad_since
) {
2544 when
= e
->bad_since
;
2545 status
= "unusable";
2549 if (use_long_names
) {
2550 routerinfo_t
*ri
= router_get_by_digest(e
->identity
);
2552 router_get_verbose_nickname(nbuf
, ri
);
2555 base16_encode(nbuf
+1, sizeof(nbuf
)-1, e
->identity
, DIGEST_LEN
);
2556 /* e->nickname field is not very reliable if we don't know about
2557 * this router any longer; don't include it. */
2560 base16_encode(nbuf
, sizeof(nbuf
), e
->identity
, DIGEST_LEN
);
2563 format_iso_time(tbuf
, when
);
2564 tor_snprintf(c
, len
, "%s %s %s\n", nbuf
, status
, tbuf
);
2566 tor_snprintf(c
, len
, "%s %s\n", nbuf
, status
);
2568 smartlist_add(sl
, c
);
2570 *answer
= smartlist_join_strings(sl
, "", 0, NULL
);
2571 SMARTLIST_FOREACH(sl
, char *, c
, tor_free(c
));