1 /* Copyright (c) 2001 Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4 * Copyright (c) 2007-2010, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
9 * \brief The actual details of building circuits.
12 #define CIRCUIT_PRIVATE
15 #include "circuitbuild.h"
16 #include "circuitlist.h"
17 #include "circuituse.h"
19 #include "connection.h"
20 #include "connection_edge.h"
21 #include "connection_or.h"
23 #include "directory.h"
25 #include "networkstatus.h"
31 #include "routerlist.h"
32 #include "routerparse.h"
38 #define MIN(a,b) ((a)<(b)?(a):(b))
41 #define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
43 /********* START VARIABLES **********/
44 /** Global list of circuit build times */
45 // FIXME: Add this as a member for entry_guard_t instead of global?
46 // Then we could do per-guard statistics, as guards are likely to
47 // vary in their own latency. The downside of this is that guards
48 // can change frequently, so we'd be building a lot more circuits
50 circuit_build_times_t circ_times
;
52 /** A global list of all circuits at this hop. */
53 extern circuit_t
*global_circuitlist
;
55 /** An entry_guard_t represents our information about a chosen long-term
56 * first hop, known as a "helper" node in the literature. We can't just
57 * use a routerinfo_t, since we want to remember these even when we
58 * don't have a directory. */
60 char nickname
[MAX_NICKNAME_LEN
+1];
61 char identity
[DIGEST_LEN
];
62 time_t chosen_on_date
; /**< Approximately when was this guard added?
63 * "0" if we don't know. */
64 char *chosen_by_version
; /**< What tor version added this guard? NULL
65 * if we don't know. */
66 unsigned int made_contact
: 1; /**< 0 if we have never connected to this
67 * router, 1 if we have. */
68 unsigned int can_retry
: 1; /**< Should we retry connecting to this entry,
69 * in spite of having it marked as unreachable?*/
70 time_t bad_since
; /**< 0 if this guard is currently usable, or the time at
71 * which it was observed to become (according to the
72 * directory or the user configuration) unusable. */
73 time_t unreachable_since
; /**< 0 if we can connect to this guard, or the
74 * time at which we first noticed we couldn't
76 time_t last_attempted
; /**< 0 if we can connect to this guard, or the time
77 * at which we last failed to connect to it. */
80 /** A list of our chosen entry guards. */
81 static smartlist_t
*entry_guards
= NULL
;
82 /** A value of 1 means that the entry_guards list has changed
83 * and those changes need to be flushed to disk. */
84 static int entry_guards_dirty
= 0;
86 /** If set, we're running the unit tests: we should avoid clobbering
87 * our state file or accessing get_options() or get_or_state() */
88 static int unit_tests
= 0;
90 /********* END VARIABLES ************/
92 static int circuit_deliver_create_cell(circuit_t
*circ
,
93 uint8_t cell_type
, const char *payload
);
94 static int onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
);
95 static crypt_path_t
*onion_next_hop_in_cpath(crypt_path_t
*cpath
);
96 static int onion_extend_cpath(origin_circuit_t
*circ
);
97 static int count_acceptable_routers(smartlist_t
*routers
);
98 static int onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
);
100 static void entry_guards_changed(void);
103 circuit_build_times_disabled(void)
108 int consensus_disabled
= networkstatus_get_param(NULL
, "cbtdisabled",
110 int config_disabled
= !get_options()->LearnCircuitBuildTimeout
;
111 int dirauth_disabled
= get_options()->AuthoritativeDir
;
112 int state_disabled
= (get_or_state()->LastWritten
== -1);
114 if (consensus_disabled
|| config_disabled
|| dirauth_disabled
||
117 "CircuitBuildTime learning is disabled. "
118 "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
119 consensus_disabled
, config_disabled
, dirauth_disabled
,
129 circuit_build_times_max_timeouts(void)
131 int32_t num
= networkstatus_get_param(NULL
, "cbtmaxtimeouts",
132 CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT
);
137 circuit_build_times_default_num_xm_modes(void)
139 int32_t num
= networkstatus_get_param(NULL
, "cbtnummodes",
140 CBT_DEFAULT_NUM_XM_MODES
);
145 circuit_build_times_min_circs_to_observe(void)
147 int32_t num
= networkstatus_get_param(NULL
, "cbtmincircs",
148 CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE
);
152 /** Return true iff <b>cbt</b> has recorded enough build times that we
153 * want to start acting on the timeout it implies. */
155 circuit_build_times_enough_to_compute(circuit_build_times_t
*cbt
)
157 return cbt
->total_build_times
>= circuit_build_times_min_circs_to_observe();
161 circuit_build_times_quantile_cutoff(void)
163 int32_t num
= networkstatus_get_param(NULL
, "cbtquantile",
164 CBT_DEFAULT_QUANTILE_CUTOFF
);
169 circuit_build_times_close_quantile(void)
171 int32_t num
= networkstatus_get_param(NULL
, "cbtclosequantile",
172 CBT_DEFAULT_CLOSE_QUANTILE
);
178 circuit_build_times_test_frequency(void)
180 int32_t num
= networkstatus_get_param(NULL
, "cbttestfreq",
181 CBT_DEFAULT_TEST_FREQUENCY
);
186 circuit_build_times_min_timeout(void)
188 int32_t num
= networkstatus_get_param(NULL
, "cbtmintimeout",
189 CBT_DEFAULT_TIMEOUT_MIN_VALUE
);
194 circuit_build_times_initial_timeout(void)
196 int32_t num
= networkstatus_get_param(NULL
, "cbtinitialtimeout",
197 CBT_DEFAULT_TIMEOUT_INITIAL_VALUE
);
202 circuit_build_times_recent_circuit_count(void)
204 int32_t num
= networkstatus_get_param(NULL
, "cbtrecentcount",
205 CBT_DEFAULT_RECENT_CIRCUITS
);
210 * This function is called when we get a consensus update.
212 * It checks to see if we have changed any consensus parameters
213 * that require reallocation or discard of previous stats.
216 circuit_build_times_new_consensus_params(circuit_build_times_t
*cbt
,
219 int32_t num
= networkstatus_get_param(ns
, "cbtrecentcount",
220 CBT_DEFAULT_RECENT_CIRCUITS
);
222 if (num
> 0 && num
!= cbt
->liveness
.num_recent_circs
) {
223 int8_t *recent_circs
;
224 log_notice(LD_CIRC
, "Changing recent timeout size from %d to %d",
225 cbt
->liveness
.num_recent_circs
, num
);
227 tor_assert(cbt
->liveness
.timeouts_after_firsthop
);
230 * Technically this is a circular array that we are reallocating
231 * and memcopying. However, since it only consists of either 1s
232 * or 0s, and is only used in a statistical test to determine when
233 * we should discard our history after a sufficient number of 1's
234 * have been reached, it is fine if order is not preserved or
237 * cbtrecentcount should only be changing in cases of severe network
238 * distress anyway, so memory correctness here is paramount over
239 * doing acrobatics to preserve the array.
241 recent_circs
= tor_malloc_zero(sizeof(int8_t)*num
);
242 memcpy(recent_circs
, cbt
->liveness
.timeouts_after_firsthop
,
243 sizeof(int8_t)*MIN(num
, cbt
->liveness
.num_recent_circs
));
245 // Adjust the index if it needs it.
246 if (num
< cbt
->liveness
.num_recent_circs
) {
247 cbt
->liveness
.after_firsthop_idx
= MIN(num
-1,
248 cbt
->liveness
.after_firsthop_idx
);
251 tor_free(cbt
->liveness
.timeouts_after_firsthop
);
252 cbt
->liveness
.timeouts_after_firsthop
= recent_circs
;
253 cbt
->liveness
.num_recent_circs
= num
;
257 /** Make a note that we're running unit tests (rather than running Tor
258 * itself), so we avoid clobbering our state file. */
260 circuitbuild_running_unit_tests(void)
266 * Return the initial default or configured timeout in milliseconds
269 circuit_build_times_get_initial_timeout(void)
272 if (!unit_tests
&& get_options()->CircuitBuildTimeout
) {
273 timeout
= get_options()->CircuitBuildTimeout
*1000;
274 if (timeout
< circuit_build_times_min_timeout()) {
275 log_warn(LD_CIRC
, "Config CircuitBuildTimeout too low. Setting to %ds",
276 circuit_build_times_min_timeout()/1000);
277 timeout
= circuit_build_times_min_timeout();
280 timeout
= circuit_build_times_initial_timeout();
286 * Reset the build time state.
288 * Leave estimated parameters, timeout and network liveness intact
292 circuit_build_times_reset(circuit_build_times_t
*cbt
)
294 memset(cbt
->circuit_build_times
, 0, sizeof(cbt
->circuit_build_times
));
295 cbt
->total_build_times
= 0;
296 cbt
->build_times_idx
= 0;
297 cbt
->have_computed_timeout
= 0;
301 * Initialize the buildtimes structure for first use.
303 * Sets the initial timeout values based on either the config setting,
304 * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
307 circuit_build_times_init(circuit_build_times_t
*cbt
)
309 memset(cbt
, 0, sizeof(*cbt
));
310 cbt
->liveness
.num_recent_circs
= circuit_build_times_recent_circuit_count();
311 cbt
->liveness
.timeouts_after_firsthop
= tor_malloc_zero(sizeof(int8_t)*
312 cbt
->liveness
.num_recent_circs
);
313 cbt
->close_ms
= cbt
->timeout_ms
= circuit_build_times_get_initial_timeout();
314 control_event_buildtimeout_set(cbt
, BUILDTIMEOUT_SET_EVENT_RESET
);
319 * Rewind our build time history by n positions.
322 circuit_build_times_rewind_history(circuit_build_times_t
*cbt
, int n
)
326 cbt
->build_times_idx
-= n
;
327 cbt
->build_times_idx
%= CBT_NCIRCUITS_TO_OBSERVE
;
329 for (i
= 0; i
< n
; i
++) {
330 cbt
->circuit_build_times
[(i
+cbt
->build_times_idx
)
331 %CBT_NCIRCUITS_TO_OBSERVE
]=0;
334 if (cbt
->total_build_times
> n
) {
335 cbt
->total_build_times
-= n
;
337 cbt
->total_build_times
= 0;
341 "Rewound history by %d places. Current index: %d. "
342 "Total: %d", n
, cbt
->build_times_idx
, cbt
->total_build_times
);
347 * Add a new build time value <b>time</b> to the set of build times. Time
348 * units are milliseconds.
350 * circuit_build_times <b>cbt</a> is a circular array, so loop around when
354 circuit_build_times_add_time(circuit_build_times_t
*cbt
, build_time_t time
)
356 if (time
<= 0 || time
> CBT_BUILD_TIME_MAX
) {
357 log_warn(LD_BUG
, "Circuit build time is too large (%u)."
358 "This is probably a bug.", time
);
359 tor_fragile_assert();
363 log_debug(LD_CIRC
, "Adding circuit build time %u", time
);
365 cbt
->circuit_build_times
[cbt
->build_times_idx
] = time
;
366 cbt
->build_times_idx
= (cbt
->build_times_idx
+ 1) % CBT_NCIRCUITS_TO_OBSERVE
;
367 if (cbt
->total_build_times
< CBT_NCIRCUITS_TO_OBSERVE
)
368 cbt
->total_build_times
++;
370 if ((cbt
->total_build_times
% CBT_SAVE_STATE_EVERY
) == 0) {
371 /* Save state every n circuit builds */
372 if (!unit_tests
&& !get_options()->AvoidDiskWrites
)
373 or_state_mark_dirty(get_or_state(), 0);
380 * Return maximum circuit build time
383 circuit_build_times_max(circuit_build_times_t
*cbt
)
386 build_time_t max_build_time
= 0;
387 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
388 if (cbt
->circuit_build_times
[i
] > max_build_time
389 && cbt
->circuit_build_times
[i
] != CBT_BUILD_ABANDONED
)
390 max_build_time
= cbt
->circuit_build_times
[i
];
392 return max_build_time
;
396 /** Return minimum circuit build time */
398 circuit_build_times_min(circuit_build_times_t
*cbt
)
401 build_time_t min_build_time
= CBT_BUILD_TIME_MAX
;
402 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
403 if (cbt
->circuit_build_times
[i
] && /* 0 <-> uninitialized */
404 cbt
->circuit_build_times
[i
] < min_build_time
)
405 min_build_time
= cbt
->circuit_build_times
[i
];
407 if (min_build_time
== CBT_BUILD_TIME_MAX
) {
408 log_warn(LD_CIRC
, "No build times less than CBT_BUILD_TIME_MAX!");
410 return min_build_time
;
415 * Calculate and return a histogram for the set of build times.
417 * Returns an allocated array of histrogram bins representing
418 * the frequency of index*CBT_BIN_WIDTH millisecond
419 * build times. Also outputs the number of bins in nbins.
421 * The return value must be freed by the caller.
424 circuit_build_times_create_histogram(circuit_build_times_t
*cbt
,
428 build_time_t max_build_time
= circuit_build_times_max(cbt
);
431 *nbins
= 1 + (max_build_time
/ CBT_BIN_WIDTH
);
432 histogram
= tor_malloc_zero(*nbins
* sizeof(build_time_t
));
434 // calculate histogram
435 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
436 if (cbt
->circuit_build_times
[i
] == 0
437 || cbt
->circuit_build_times
[i
] == CBT_BUILD_ABANDONED
)
438 continue; /* 0 <-> uninitialized */
440 c
= (cbt
->circuit_build_times
[i
] / CBT_BIN_WIDTH
);
448 * Return the Pareto start-of-curve parameter Xm.
450 * Because we are not a true Pareto curve, we compute this as the
451 * weighted average of the N=3 most frequent build time bins.
454 circuit_build_times_get_xm(circuit_build_times_t
*cbt
)
456 build_time_t i
, nbins
;
457 build_time_t
*nth_max_bin
;
458 int32_t bin_counts
=0;
459 build_time_t ret
= 0;
460 uint32_t *histogram
= circuit_build_times_create_histogram(cbt
, &nbins
);
462 int num_modes
= circuit_build_times_default_num_xm_modes();
464 // Only use one mode if < 1000 buildtimes. Not enough data
466 if (cbt
->total_build_times
< CBT_NCIRCUITS_TO_OBSERVE
)
469 nth_max_bin
= (build_time_t
*)tor_malloc_zero(num_modes
*sizeof(build_time_t
));
471 for (i
= 0; i
< nbins
; i
++) {
472 if (histogram
[i
] >= histogram
[nth_max_bin
[0]]) {
476 for (n
= 1; n
< num_modes
; n
++) {
477 if (histogram
[i
] >= histogram
[nth_max_bin
[n
]] &&
478 (!histogram
[nth_max_bin
[n
-1]]
479 || histogram
[i
] < histogram
[nth_max_bin
[n
-1]])) {
485 for (n
= 0; n
< num_modes
; n
++) {
486 bin_counts
+= histogram
[nth_max_bin
[n
]];
487 ret
+= CBT_BIN_TO_MS(nth_max_bin
[n
])*histogram
[nth_max_bin
[n
]];
488 log_info(LD_CIRC
, "Xm mode #%d: %u %u", n
, CBT_BIN_TO_MS(nth_max_bin
[n
]),
489 histogram
[nth_max_bin
[n
]]);
494 tor_free(nth_max_bin
);
500 * Output a histogram of current circuit build times to
501 * the or_state_t state structure.
504 circuit_build_times_update_state(circuit_build_times_t
*cbt
,
509 build_time_t nbins
= 0;
510 config_line_t
**next
, *line
;
512 histogram
= circuit_build_times_create_histogram(cbt
, &nbins
);
514 config_free_lines(state
->BuildtimeHistogram
);
515 next
= &state
->BuildtimeHistogram
;
518 state
->TotalBuildTimes
= cbt
->total_build_times
;
519 state
->CircuitBuildAbandonedCount
= 0;
521 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
522 if (cbt
->circuit_build_times
[i
] == CBT_BUILD_ABANDONED
)
523 state
->CircuitBuildAbandonedCount
++;
526 for (i
= 0; i
< nbins
; i
++) {
527 // compress the histogram by skipping the blanks
528 if (histogram
[i
] == 0) continue;
529 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
530 line
->key
= tor_strdup("CircuitBuildTimeBin");
531 line
->value
= tor_malloc(25);
532 tor_snprintf(line
->value
, 25, "%d %d",
533 CBT_BIN_TO_MS(i
), histogram
[i
]);
534 next
= &(line
->next
);
538 if (!get_options()->AvoidDiskWrites
)
539 or_state_mark_dirty(get_or_state(), 0);
546 * Shuffle the build times array.
548 * Stolen from http://en.wikipedia.org/wiki/Fisher\u2013Yates_shuffle
551 circuit_build_times_shuffle_and_store_array(circuit_build_times_t
*cbt
,
552 build_time_t
*raw_times
,
556 if (num_times
> CBT_NCIRCUITS_TO_OBSERVE
) {
557 log_notice(LD_CIRC
, "Decreasing circuit_build_times size from %d to %d",
558 num_times
, CBT_NCIRCUITS_TO_OBSERVE
);
561 /* This code can only be run on a compact array */
563 int k
= crypto_rand_int(n
+ 1); /* 0 <= k <= n. */
564 build_time_t tmp
= raw_times
[k
];
565 raw_times
[k
] = raw_times
[n
];
569 /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
570 * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
571 for (n
= 0; n
< MIN(num_times
, CBT_NCIRCUITS_TO_OBSERVE
); n
++) {
572 circuit_build_times_add_time(cbt
, raw_times
[n
]);
577 * Filter old synthetic timeouts that were created before the
578 * new right-censored Pareto calculation was deployed.
580 * Once all clients before 0.2.1.13-alpha are gone, this code
584 circuit_build_times_filter_timeouts(circuit_build_times_t
*cbt
)
586 int num_filtered
=0, i
=0;
587 double timeout_rate
= 0;
588 build_time_t max_timeout
= 0;
590 timeout_rate
= circuit_build_times_timeout_rate(cbt
);
591 max_timeout
= (build_time_t
)cbt
->close_ms
;
593 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
594 if (cbt
->circuit_build_times
[i
] > max_timeout
) {
595 build_time_t replaced
= cbt
->circuit_build_times
[i
];
597 cbt
->circuit_build_times
[i
] = CBT_BUILD_ABANDONED
;
599 log_debug(LD_CIRC
, "Replaced timeout %d with %d", replaced
,
600 cbt
->circuit_build_times
[i
]);
605 "We had %d timeouts out of %d build times, "
606 "and filtered %d above the max of %u",
607 (int)(cbt
->total_build_times
*timeout_rate
),
608 cbt
->total_build_times
, num_filtered
, max_timeout
);
614 * Load histogram from <b>state</b>, shuffling the resulting array
615 * after we do so. Use this result to estimate parameters and
616 * calculate the timeout.
618 * Return -1 on error.
621 circuit_build_times_parse_state(circuit_build_times_t
*cbt
,
625 uint32_t loaded_cnt
= 0, N
= 0;
628 build_time_t
*loaded_times
;
630 circuit_build_times_init(cbt
);
632 if (circuit_build_times_disabled()) {
636 /* build_time_t 0 means uninitialized */
637 loaded_times
= tor_malloc_zero(sizeof(build_time_t
)*state
->TotalBuildTimes
);
639 for (line
= state
->BuildtimeHistogram
; line
; line
= line
->next
) {
640 smartlist_t
*args
= smartlist_create();
641 smartlist_split_string(args
, line
->value
, " ",
642 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
643 if (smartlist_len(args
) < 2) {
644 log_warn(LD_GENERAL
, "Unable to parse circuit build times: "
645 "Too few arguments to CircuitBuildTime");
647 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
648 smartlist_free(args
);
651 const char *ms_str
= smartlist_get(args
,0);
652 const char *count_str
= smartlist_get(args
,1);
656 ms
= (build_time_t
)tor_parse_ulong(ms_str
, 0, 0,
657 CBT_BUILD_TIME_MAX
, &ok
, NULL
);
659 log_warn(LD_GENERAL
, "Unable to parse circuit build times: "
660 "Unparsable bin number");
662 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
663 smartlist_free(args
);
666 count
= (uint32_t)tor_parse_ulong(count_str
, 0, 0,
667 UINT32_MAX
, &ok
, NULL
);
669 log_warn(LD_GENERAL
, "Unable to parse circuit build times: "
670 "Unparsable bin count");
672 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
673 smartlist_free(args
);
677 if (loaded_cnt
+count
+state
->CircuitBuildAbandonedCount
678 > state
->TotalBuildTimes
) {
680 "Too many build times in state file. "
681 "Stopping short before %d",
683 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
684 smartlist_free(args
);
688 for (k
= 0; k
< count
; k
++) {
689 loaded_times
[loaded_cnt
++] = ms
;
692 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
693 smartlist_free(args
);
698 "Adding %d timeouts.", state
->CircuitBuildAbandonedCount
);
699 for (i
=0; i
< state
->CircuitBuildAbandonedCount
; i
++) {
700 loaded_times
[loaded_cnt
++] = CBT_BUILD_ABANDONED
;
703 if (loaded_cnt
!= state
->TotalBuildTimes
) {
705 "Corrupt state file? Build times count mismatch. "
706 "Read %d times, but file says %d", loaded_cnt
,
707 state
->TotalBuildTimes
);
709 circuit_build_times_reset(cbt
);
713 circuit_build_times_shuffle_and_store_array(cbt
, loaded_times
, loaded_cnt
);
715 /* Verify that we didn't overwrite any indexes */
716 for (i
=0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
717 if (!cbt
->circuit_build_times
[i
])
722 "Loaded %d/%d values from %d lines in circuit time histogram",
723 tot_values
, cbt
->total_build_times
, N
);
725 if (cbt
->total_build_times
!= tot_values
726 || cbt
->total_build_times
> CBT_NCIRCUITS_TO_OBSERVE
) {
728 "Corrupt state file? Shuffled build times mismatch. "
729 "Read %d times, but file says %d", tot_values
,
730 state
->TotalBuildTimes
);
732 circuit_build_times_reset(cbt
);
736 circuit_build_times_set_timeout(cbt
);
738 if (!state
->CircuitBuildAbandonedCount
&& cbt
->total_build_times
) {
739 circuit_build_times_filter_timeouts(cbt
);
743 tor_free(loaded_times
);
748 * Estimates the Xm and Alpha parameters using
749 * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
751 * The notable difference is that we use mode instead of min to estimate Xm.
752 * This is because our distribution is frechet-like. We claim this is
753 * an acceptable approximation because we are only concerned with the
754 * accuracy of the CDF of the tail.
757 circuit_build_times_update_alpha(circuit_build_times_t
*cbt
)
759 build_time_t
*x
=cbt
->circuit_build_times
;
761 int n
=0,i
=0,abandoned_count
=0;
762 build_time_t max_time
=0;
764 /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
765 /* We sort of cheat here and make our samples slightly more pareto-like
766 * and less frechet-like. */
767 cbt
->Xm
= circuit_build_times_get_xm(cbt
);
769 tor_assert(cbt
->Xm
> 0);
771 for (i
=0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
776 if (x
[i
] < cbt
->Xm
) {
777 a
+= tor_mathlog(cbt
->Xm
);
778 } else if (x
[i
] == CBT_BUILD_ABANDONED
) {
781 a
+= tor_mathlog(x
[i
]);
789 * We are erring and asserting here because this can only happen
790 * in codepaths other than startup. The startup state parsing code
791 * performs this same check, and resets state if it hits it. If we
792 * hit it at runtime, something serious has gone wrong.
794 if (n
!=cbt
->total_build_times
) {
795 log_err(LD_CIRC
, "Discrepancy in build times count: %d vs %d", n
,
796 cbt
->total_build_times
);
798 tor_assert(n
==cbt
->total_build_times
);
801 /* This can happen if Xm is actually the *maximum* value in the set.
802 * It can also happen if we've abandoned every single circuit somehow.
803 * In either case, tell the caller not to compute a new build timeout. */
805 "Could not determine largest build time (%d). "
806 "Xm is %dms and we've abandoned %d out of %d circuits.", max_time
,
807 cbt
->Xm
, abandoned_count
, n
);
811 a
+= abandoned_count
*tor_mathlog(max_time
);
813 a
-= n
*tor_mathlog(cbt
->Xm
);
814 // Estimator comes from Eq #4 in:
815 // "Bayesian estimation based on trimmed samples from Pareto populations"
816 // by Arturo J. Fernández. We are right-censored only.
817 a
= (n
-abandoned_count
)/a
;
825 * This is the Pareto Quantile Function. It calculates the point x
826 * in the distribution such that F(x) = quantile (ie quantile*100%
827 * of the mass of the density function is below x on the curve).
829 * We use it to calculate the timeout and also to generate synthetic
830 * values of time for circuits that timeout before completion.
832 * See http://en.wikipedia.org/wiki/Quantile_function,
833 * http://en.wikipedia.org/wiki/Inverse_transform_sampling and
834 * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
835 * random_sample_from_Pareto_distribution
836 * That's right. I'll cite wikipedia all day long.
838 * Return value is in milliseconds.
841 circuit_build_times_calculate_timeout(circuit_build_times_t
*cbt
,
845 tor_assert(quantile
>= 0);
846 tor_assert(1.0-quantile
> 0);
847 tor_assert(cbt
->Xm
> 0);
849 ret
= cbt
->Xm
/pow(1.0-quantile
,1.0/cbt
->alpha
);
850 if (ret
> INT32_MAX
) {
859 circuit_build_times_cdf(circuit_build_times_t
*cbt
, double x
)
862 tor_assert(cbt
->Xm
> 0);
863 ret
= 1.0-pow(cbt
->Xm
/x
,cbt
->alpha
);
864 tor_assert(0 <= ret
&& ret
<= 1.0);
869 * Generate a synthetic time using our distribution parameters.
871 * The return value will be within the [q_lo, q_hi) quantile points
875 circuit_build_times_generate_sample(circuit_build_times_t
*cbt
,
876 double q_lo
, double q_hi
)
878 double randval
= crypto_rand_double();
882 /* Generate between [q_lo, q_hi) */
883 /*XXXX This is what nextafter is supposed to be for; we should use it on the
884 * platforms that support it. */
885 q_hi
-= 1.0/(INT32_MAX
);
887 tor_assert(q_lo
>= 0);
888 tor_assert(q_hi
< 1);
889 tor_assert(q_lo
< q_hi
);
891 u
= q_lo
+ (q_hi
-q_lo
)*randval
;
893 tor_assert(0 <= u
&& u
< 1.0);
894 /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
896 tor_lround(circuit_build_times_calculate_timeout(cbt
, u
));
902 * Estimate an initial alpha parameter by solving the quantile
903 * function with a quantile point and a specific timeout value.
906 circuit_build_times_initial_alpha(circuit_build_times_t
*cbt
,
907 double quantile
, double timeout_ms
)
909 // Q(u) = Xm/((1-u)^(1/a))
910 // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
911 // CircBuildTimeout = Xm/((1-0.8))^(1/a))
912 // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
913 // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
914 // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
915 tor_assert(quantile
>= 0);
916 tor_assert(cbt
->Xm
> 0);
917 cbt
->alpha
= tor_mathlog(1.0-quantile
)/
918 (tor_mathlog(cbt
->Xm
)-tor_mathlog(timeout_ms
));
919 tor_assert(cbt
->alpha
> 0);
923 * Returns true if we need circuits to be built
926 circuit_build_times_needs_circuits(circuit_build_times_t
*cbt
)
928 /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
929 return !circuit_build_times_enough_to_compute(cbt
);
933 * Returns true if we should build a timeout test circuit
937 circuit_build_times_needs_circuits_now(circuit_build_times_t
*cbt
)
939 return circuit_build_times_needs_circuits(cbt
) &&
940 approx_time()-cbt
->last_circ_at
> circuit_build_times_test_frequency();
944 * Called to indicate that the network showed some signs of liveness,
945 * i.e. we received a cell.
947 * This is used by circuit_build_times_network_check_live() to decide
948 * if we should record the circuit build timeout or not.
950 * This function is called every time we receive a cell. Avoid
951 * syscalls, events, and other high-intensity work.
954 circuit_build_times_network_is_live(circuit_build_times_t
*cbt
)
956 time_t now
= approx_time();
957 if (cbt
->liveness
.nonlive_timeouts
> 0) {
959 "Tor now sees network activity. Restoring circuit build "
960 "timeout recording. Network was down for %d seconds "
961 "during %d circuit attempts.",
962 (int)(now
- cbt
->liveness
.network_last_live
),
963 cbt
->liveness
.nonlive_timeouts
);
965 cbt
->liveness
.network_last_live
= now
;
966 cbt
->liveness
.nonlive_timeouts
= 0;
970 * Called to indicate that we completed a circuit. Because this circuit
971 * succeeded, it doesn't count as a timeout-after-the-first-hop.
973 * This is used by circuit_build_times_network_check_changed() to determine
974 * if we had too many recent timeouts and need to reset our learned timeout
975 * to something higher.
978 circuit_build_times_network_circ_success(circuit_build_times_t
*cbt
)
980 cbt
->liveness
.timeouts_after_firsthop
[cbt
->liveness
.after_firsthop_idx
] = 0;
981 cbt
->liveness
.after_firsthop_idx
++;
982 cbt
->liveness
.after_firsthop_idx
%= cbt
->liveness
.num_recent_circs
;
986 * A circuit just timed out. If it failed after the first hop, record it
987 * in our history for later deciding if the network speed has changed.
989 * This is used by circuit_build_times_network_check_changed() to determine
990 * if we had too many recent timeouts and need to reset our learned timeout
991 * to something higher.
994 circuit_build_times_network_timeout(circuit_build_times_t
*cbt
,
998 cbt
->liveness
.timeouts_after_firsthop
[cbt
->liveness
.after_firsthop_idx
]=1;
999 cbt
->liveness
.after_firsthop_idx
++;
1000 cbt
->liveness
.after_firsthop_idx
%= cbt
->liveness
.num_recent_circs
;
1005 * A circuit was just forcibly closed. If there has been no recent network
1006 * activity at all, but this circuit was launched back when we thought the
1007 * network was live, increment the number of "nonlive" circuit timeouts.
1009 * This is used by circuit_build_times_network_check_live() to decide
1010 * if we should record the circuit build timeout or not.
1013 circuit_build_times_network_close(circuit_build_times_t
*cbt
,
1014 int did_onehop
, time_t start_time
)
1016 time_t now
= time(NULL
);
1018 * Check if this is a timeout that was for a circuit that spent its
1019 * entire existence during a time where we have had no network activity.
1021 if (cbt
->liveness
.network_last_live
< start_time
) {
1023 char last_live_buf
[ISO_TIME_LEN
+1];
1024 char start_time_buf
[ISO_TIME_LEN
+1];
1025 char now_buf
[ISO_TIME_LEN
+1];
1026 format_local_iso_time(last_live_buf
, cbt
->liveness
.network_last_live
);
1027 format_local_iso_time(start_time_buf
, start_time
);
1028 format_local_iso_time(now_buf
, now
);
1030 "Circuit somehow completed a hop while the network was "
1031 "not live. Network was last live at %s, but circuit launched "
1032 "at %s. It's now %s.", last_live_buf
, start_time_buf
,
1035 cbt
->liveness
.nonlive_timeouts
++;
1036 if (cbt
->liveness
.nonlive_timeouts
== 1) {
1038 "Tor has not observed any network activity for the past %d "
1039 "seconds. Disabling circuit build timeout code.",
1040 (int)(now
- cbt
->liveness
.network_last_live
));
1043 "Got non-live timeout. Current count is: %d",
1044 cbt
->liveness
.nonlive_timeouts
);
1050 * When the network is not live, we do not record circuit build times.
1052 * The network is considered not live if there has been at least one
1053 * circuit build that began and ended (had its close_ms measurement
1054 * period expire) since we last received a cell.
1056 * Also has the side effect of rewinding the circuit time history
1057 * in the case of recent liveness changes.
1060 circuit_build_times_network_check_live(circuit_build_times_t
*cbt
)
1062 if (cbt
->liveness
.nonlive_timeouts
> 0) {
1070 * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
1071 * the past RECENT_CIRCUITS time out after the first hop. Used to detect
1072 * if the network connection has changed significantly, and if so,
1073 * resets our circuit build timeout to the default.
1075 * Also resets the entire timeout history in this case and causes us
1076 * to restart the process of building test circuits and estimating a
1080 circuit_build_times_network_check_changed(circuit_build_times_t
*cbt
)
1082 int total_build_times
= cbt
->total_build_times
;
1083 int timeout_count
=0;
1086 /* how many of our recent circuits made it to the first hop but then
1088 for (i
= 0; i
< cbt
->liveness
.num_recent_circs
; i
++) {
1089 timeout_count
+= cbt
->liveness
.timeouts_after_firsthop
[i
];
1092 /* If 80% of our recent circuits are timing out after the first hop,
1093 * we need to re-estimate a new initial alpha and timeout. */
1094 if (timeout_count
< circuit_build_times_max_timeouts()) {
1098 circuit_build_times_reset(cbt
);
1099 memset(cbt
->liveness
.timeouts_after_firsthop
, 0,
1100 sizeof(*cbt
->liveness
.timeouts_after_firsthop
)*
1101 cbt
->liveness
.num_recent_circs
);
1102 cbt
->liveness
.after_firsthop_idx
= 0;
1104 /* Check to see if this has happened before. If so, double the timeout
1105 * to give people on abysmally bad network connections a shot at access */
1106 if (cbt
->timeout_ms
>= circuit_build_times_get_initial_timeout()) {
1107 if (cbt
->timeout_ms
> INT32_MAX
/2 || cbt
->close_ms
> INT32_MAX
/2) {
1108 log_warn(LD_CIRC
, "Insanely large circuit build timeout value. "
1109 "(timeout = %lfmsec, close = %lfmsec)",
1110 cbt
->timeout_ms
, cbt
->close_ms
);
1112 cbt
->timeout_ms
*= 2;
1116 cbt
->close_ms
= cbt
->timeout_ms
1117 = circuit_build_times_get_initial_timeout();
1120 control_event_buildtimeout_set(cbt
, BUILDTIMEOUT_SET_EVENT_RESET
);
1123 "Network connection speed appears to have changed. Resetting "
1124 "timeout to %lds after %d timeouts and %d buildtimes.",
1125 tor_lround(cbt
->timeout_ms
/1000), timeout_count
,
1132 * Count the number of timeouts in a set of cbt data.
1135 circuit_build_times_timeout_rate(const circuit_build_times_t
*cbt
)
1138 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
1139 if (cbt
->circuit_build_times
[i
] >= cbt
->timeout_ms
) {
1144 if (!cbt
->total_build_times
)
1147 return ((double)timeouts
)/cbt
->total_build_times
;
1151 * Count the number of closed circuits in a set of cbt data.
1154 circuit_build_times_close_rate(const circuit_build_times_t
*cbt
)
1157 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
1158 if (cbt
->circuit_build_times
[i
] == CBT_BUILD_ABANDONED
) {
1163 if (!cbt
->total_build_times
)
1166 return ((double)closed
)/cbt
->total_build_times
;
1170 * Store a timeout as a synthetic value.
1172 * Returns true if the store was successful and we should possibly
1173 * update our timeout estimate.
1176 circuit_build_times_count_close(circuit_build_times_t
*cbt
,
1180 if (circuit_build_times_disabled()) {
1181 cbt
->close_ms
= cbt
->timeout_ms
1182 = circuit_build_times_get_initial_timeout();
1186 /* Record this force-close to help determine if the network is dead */
1187 circuit_build_times_network_close(cbt
, did_onehop
, start_time
);
1189 /* Only count timeouts if network is live.. */
1190 if (!circuit_build_times_network_check_live(cbt
)) {
1194 circuit_build_times_add_time(cbt
, CBT_BUILD_ABANDONED
);
1199 * Update timeout counts to determine if we need to expire
1200 * our build time history due to excessive timeouts.
1202 * We do not record any actual time values at this stage;
1203 * we are only interested in recording the fact that a timeout
1204 * happened. We record the time values via
1205 * circuit_build_times_count_close() and circuit_build_times_add_time().
1208 circuit_build_times_count_timeout(circuit_build_times_t
*cbt
,
1211 if (circuit_build_times_disabled()) {
1212 cbt
->close_ms
= cbt
->timeout_ms
1213 = circuit_build_times_get_initial_timeout();
1217 /* Register the fact that a timeout just occurred. */
1218 circuit_build_times_network_timeout(cbt
, did_onehop
);
1220 /* If there are a ton of timeouts, we should reset
1221 * the circuit build timeout. */
1222 circuit_build_times_network_check_changed(cbt
);
1226 * Estimate a new timeout based on history and set our timeout
1227 * variable accordingly.
1230 circuit_build_times_set_timeout_worker(circuit_build_times_t
*cbt
)
1232 build_time_t max_time
;
1233 if (!circuit_build_times_enough_to_compute(cbt
))
1236 if (!circuit_build_times_update_alpha(cbt
))
1239 cbt
->timeout_ms
= circuit_build_times_calculate_timeout(cbt
,
1240 circuit_build_times_quantile_cutoff());
1242 cbt
->close_ms
= circuit_build_times_calculate_timeout(cbt
,
1243 circuit_build_times_close_quantile());
1245 max_time
= circuit_build_times_max(cbt
);
1247 /* Sometimes really fast guard nodes give us such a steep curve
1248 * that this ends up being not that much greater than timeout_ms.
1249 * Make it be at least 1 min to handle this case. */
1250 cbt
->close_ms
= MAX(cbt
->close_ms
, circuit_build_times_initial_timeout());
1252 if (cbt
->timeout_ms
> max_time
) {
1254 "Circuit build timeout of %dms is beyond the maximum build "
1255 "time we have ever observed. Capping it to %dms.",
1256 (int)cbt
->timeout_ms
, max_time
);
1257 cbt
->timeout_ms
= max_time
;
1260 if (max_time
< INT32_MAX
/2 && cbt
->close_ms
> 2*max_time
) {
1262 "Circuit build measurement period of %dms is more than twice "
1263 "the maximum build time we have ever observed. Capping it to "
1264 "%dms.", (int)cbt
->close_ms
, 2*max_time
);
1265 cbt
->close_ms
= 2*max_time
;
1268 cbt
->have_computed_timeout
= 1;
1273 * Exposed function to compute a new timeout. Dispatches events and
1274 * also filters out extremely high timeout values.
1277 circuit_build_times_set_timeout(circuit_build_times_t
*cbt
)
1279 long prev_timeout
= tor_lround(cbt
->timeout_ms
/1000);
1280 double timeout_rate
;
1282 if (!circuit_build_times_set_timeout_worker(cbt
))
1285 if (cbt
->timeout_ms
< circuit_build_times_min_timeout()) {
1286 log_warn(LD_CIRC
, "Set buildtimeout to low value %lfms. Setting to %dms",
1287 cbt
->timeout_ms
, circuit_build_times_min_timeout());
1288 cbt
->timeout_ms
= circuit_build_times_min_timeout();
1289 if (cbt
->close_ms
< cbt
->timeout_ms
) {
1290 /* This shouldn't happen because of MAX() in timeout_worker above,
1291 * but doing it just in case */
1292 cbt
->close_ms
= circuit_build_times_initial_timeout();
1296 control_event_buildtimeout_set(cbt
, BUILDTIMEOUT_SET_EVENT_COMPUTED
);
1298 timeout_rate
= circuit_build_times_timeout_rate(cbt
);
1300 if (prev_timeout
> tor_lround(cbt
->timeout_ms
/1000)) {
1302 "Based on %d circuit times, it looks like we don't need to "
1303 "wait so long for circuits to finish. We will now assume a "
1304 "circuit is too slow to use after waiting %ld seconds.",
1305 cbt
->total_build_times
,
1306 tor_lround(cbt
->timeout_ms
/1000));
1308 "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf",
1309 cbt
->timeout_ms
, cbt
->close_ms
, cbt
->Xm
, cbt
->alpha
,
1311 } else if (prev_timeout
< tor_lround(cbt
->timeout_ms
/1000)) {
1313 "Based on %d circuit times, it looks like we need to wait "
1314 "longer for circuits to finish. We will now assume a "
1315 "circuit is too slow to use after waiting %ld seconds.",
1316 cbt
->total_build_times
,
1317 tor_lround(cbt
->timeout_ms
/1000));
1319 "Circuit timeout data: %lfms, %lfms, Xm: %d, a: %lf, r: %lf",
1320 cbt
->timeout_ms
, cbt
->close_ms
, cbt
->Xm
, cbt
->alpha
,
1324 "Set circuit build timeout to %lds (%lfms, %lfms, Xm: %d, a: %lf,"
1325 " r: %lf) based on %d circuit times",
1326 tor_lround(cbt
->timeout_ms
/1000),
1327 cbt
->timeout_ms
, cbt
->close_ms
, cbt
->Xm
, cbt
->alpha
, timeout_rate
,
1328 cbt
->total_build_times
);
1332 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
1333 * and with the high bit specified by conn-\>circ_id_type, until we get
1334 * a circ_id that is not in use by any other circuit on that conn.
1336 * Return it, or 0 if can't get a unique circ_id.
1339 get_unique_circ_id_by_conn(or_connection_t
*conn
)
1341 circid_t test_circ_id
;
1342 circid_t attempts
=0;
1346 if (conn
->circ_id_type
== CIRC_ID_TYPE_NEITHER
) {
1347 log_warn(LD_BUG
, "Trying to pick a circuit ID for a connection from "
1348 "a client with no identity.");
1351 high_bit
= (conn
->circ_id_type
== CIRC_ID_TYPE_HIGHER
) ? 1<<15 : 0;
1353 /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
1354 * circID such that (high_bit|test_circ_id) is not already used. */
1355 test_circ_id
= conn
->next_circ_id
++;
1356 if (test_circ_id
== 0 || test_circ_id
>= 1<<15) {
1358 conn
->next_circ_id
= 2;
1360 if (++attempts
> 1<<15) {
1361 /* Make sure we don't loop forever if all circ_id's are used. This
1362 * matters because it's an external DoS opportunity.
1364 log_warn(LD_CIRC
,"No unused circ IDs. Failing.");
1367 test_circ_id
|= high_bit
;
1368 } while (circuit_id_in_use_on_orconn(test_circ_id
, conn
));
1369 return test_circ_id
;
1372 /** If <b>verbose</b> is false, allocate and return a comma-separated list of
1373 * the currently built elements of circuit_t. If <b>verbose</b> is true, also
1374 * list information about link status in a more verbose format using spaces.
1375 * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
1376 * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
1380 circuit_list_path_impl(origin_circuit_t
*circ
, int verbose
, int verbose_names
)
1383 smartlist_t
*elements
;
1384 const char *states
[] = {"closed", "waiting for keys", "open"};
1387 elements
= smartlist_create();
1390 const char *nickname
= build_state_get_exit_nickname(circ
->build_state
);
1392 tor_asprintf(&cp
, "%s%s circ (length %d%s%s):",
1393 circ
->build_state
->is_internal
? "internal" : "exit",
1394 circ
->build_state
->need_uptime
? " (high-uptime)" : "",
1395 circ
->build_state
->desired_path_len
,
1396 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" : ", exit ",
1397 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" :
1398 (nickname
?nickname
:"*unnamed*"));
1399 smartlist_add(elements
, cp
);
1410 if (!verbose
&& hop
->state
!= CPATH_STATE_OPEN
)
1412 if (!hop
->extend_info
)
1414 id
= hop
->extend_info
->identity_digest
;
1415 if (verbose_names
) {
1416 elt
= tor_malloc(MAX_VERBOSE_NICKNAME_LEN
+1);
1417 if ((ri
= router_get_by_digest(id
))) {
1418 router_get_verbose_nickname(elt
, ri
);
1419 } else if ((rs
= router_get_consensus_status_by_id(id
))) {
1420 routerstatus_get_verbose_nickname(elt
, rs
);
1421 } else if (is_legal_nickname(hop
->extend_info
->nickname
)) {
1423 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
1424 elt
[HEX_DIGEST_LEN
+1]= '~';
1425 strlcpy(elt
+HEX_DIGEST_LEN
+2,
1426 hop
->extend_info
->nickname
, MAX_NICKNAME_LEN
+1);
1429 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
1431 } else { /* ! verbose_names */
1432 if ((ri
= router_get_by_digest(id
)) &&
1434 elt
= tor_strdup(hop
->extend_info
->nickname
);
1436 elt
= tor_malloc(HEX_DIGEST_LEN
+2);
1438 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
1443 size_t len
= strlen(elt
)+2+strlen(states
[hop
->state
])+1;
1444 char *v
= tor_malloc(len
);
1445 tor_assert(hop
->state
<= 2);
1446 tor_snprintf(v
,len
,"%s(%s)",elt
,states
[hop
->state
]);
1447 smartlist_add(elements
, v
);
1450 smartlist_add(elements
, elt
);
1453 } while (hop
!= circ
->cpath
);
1455 s
= smartlist_join_strings(elements
, verbose
?" ":",", 0, NULL
);
1456 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
1457 smartlist_free(elements
);
1461 /** If <b>verbose</b> is false, allocate and return a comma-separated
1462 * list of the currently built elements of circuit_t. If
1463 * <b>verbose</b> is true, also list information about link status in
1464 * a more verbose format using spaces.
1467 circuit_list_path(origin_circuit_t
*circ
, int verbose
)
1469 return circuit_list_path_impl(circ
, verbose
, 0);
1472 /** Allocate and return a comma-separated list of the currently built elements
1473 * of circuit_t, giving each as a verbose nickname.
1476 circuit_list_path_for_controller(origin_circuit_t
*circ
)
1478 return circuit_list_path_impl(circ
, 0, 1);
1481 /** Log, at severity <b>severity</b>, the nicknames of each router in
1482 * circ's cpath. Also log the length of the cpath, and the intended
1486 circuit_log_path(int severity
, unsigned int domain
, origin_circuit_t
*circ
)
1488 char *s
= circuit_list_path(circ
,1);
1489 tor_log(severity
,domain
,"%s",s
);
1493 /** Tell the rep(utation)hist(ory) module about the status of the links
1494 * in circ. Hops that have become OPEN are marked as successfully
1495 * extended; the _first_ hop that isn't open (if any) is marked as
1498 /* XXXX Someday we should learn from OR circuits too. */
1500 circuit_rep_hist_note_result(origin_circuit_t
*circ
)
1503 char *prev_digest
= NULL
;
1504 routerinfo_t
*router
;
1506 if (!hop
) /* circuit hasn't started building yet. */
1508 if (server_mode(get_options())) {
1509 routerinfo_t
*me
= router_get_my_routerinfo();
1512 prev_digest
= me
->cache_info
.identity_digest
;
1515 router
= router_get_by_digest(hop
->extend_info
->identity_digest
);
1518 if (hop
->state
== CPATH_STATE_OPEN
)
1519 rep_hist_note_extend_succeeded(prev_digest
,
1520 router
->cache_info
.identity_digest
);
1522 rep_hist_note_extend_failed(prev_digest
,
1523 router
->cache_info
.identity_digest
);
1527 prev_digest
= router
->cache_info
.identity_digest
;
1532 } while (hop
!=circ
->cpath
);
1535 /** Pick all the entries in our cpath. Stop and return 0 when we're
1536 * happy, or return -1 if an error occurs. */
1538 onion_populate_cpath(origin_circuit_t
*circ
)
1542 r
= onion_extend_cpath(circ
);
1544 log_info(LD_CIRC
,"Generating cpath hop failed.");
1549 return 0; /* if r == 1 */
1552 /** Create and return a new origin circuit. Initialize its purpose and
1553 * build-state based on our arguments. The <b>flags</b> argument is a
1554 * bitfield of CIRCLAUNCH_* flags. */
1556 origin_circuit_init(uint8_t purpose
, int flags
)
1558 /* sets circ->p_circ_id and circ->p_conn */
1559 origin_circuit_t
*circ
= origin_circuit_new();
1560 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OR_WAIT
);
1561 circ
->build_state
= tor_malloc_zero(sizeof(cpath_build_state_t
));
1562 circ
->build_state
->onehop_tunnel
=
1563 ((flags
& CIRCLAUNCH_ONEHOP_TUNNEL
) ? 1 : 0);
1564 circ
->build_state
->need_uptime
=
1565 ((flags
& CIRCLAUNCH_NEED_UPTIME
) ? 1 : 0);
1566 circ
->build_state
->need_capacity
=
1567 ((flags
& CIRCLAUNCH_NEED_CAPACITY
) ? 1 : 0);
1568 circ
->build_state
->is_internal
=
1569 ((flags
& CIRCLAUNCH_IS_INTERNAL
) ? 1 : 0);
1570 circ
->_base
.purpose
= purpose
;
1574 /** Build a new circuit for <b>purpose</b>. If <b>exit</b>
1575 * is defined, then use that as your exit router, else choose a suitable
1578 * Also launch a connection to the first OR in the chosen path, if
1579 * it's not open already.
1582 circuit_establish_circuit(uint8_t purpose
, extend_info_t
*exit
, int flags
)
1584 origin_circuit_t
*circ
;
1587 circ
= origin_circuit_init(purpose
, flags
);
1589 if (onion_pick_cpath_exit(circ
, exit
) < 0 ||
1590 onion_populate_cpath(circ
) < 0) {
1591 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_NOPATH
);
1595 control_event_circuit_status(circ
, CIRC_EVENT_LAUNCHED
, 0);
1597 if ((err_reason
= circuit_handle_first_hop(circ
)) < 0) {
1598 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
1604 /** Start establishing the first hop of our circuit. Figure out what
1605 * OR we should connect to, and if necessary start the connection to
1606 * it. If we're already connected, then send the 'create' cell.
1607 * Return 0 for ok, -reason if circ should be marked-for-close. */
1609 circuit_handle_first_hop(origin_circuit_t
*circ
)
1611 crypt_path_t
*firsthop
;
1612 or_connection_t
*n_conn
;
1614 const char *msg
= NULL
;
1615 int should_launch
= 0;
1617 firsthop
= onion_next_hop_in_cpath(circ
->cpath
);
1618 tor_assert(firsthop
);
1619 tor_assert(firsthop
->extend_info
);
1621 /* now see if we're already connected to the first OR in 'route' */
1622 log_debug(LD_CIRC
,"Looking for firsthop '%s:%u'",
1623 fmt_addr(&firsthop
->extend_info
->addr
),
1624 firsthop
->extend_info
->port
);
1626 n_conn
= connection_or_get_for_extend(firsthop
->extend_info
->identity_digest
,
1627 &firsthop
->extend_info
->addr
,
1632 /* not currently connected in a useful way. */
1633 const char *name
= strlen(firsthop
->extend_info
->nickname
) ?
1634 firsthop
->extend_info
->nickname
: fmt_addr(&firsthop
->extend_info
->addr
);
1635 log_info(LD_CIRC
, "Next router is %s: %s ",
1636 safe_str_client(name
), msg
?msg
:"???");
1637 circ
->_base
.n_hop
= extend_info_dup(firsthop
->extend_info
);
1639 if (should_launch
) {
1640 if (circ
->build_state
->onehop_tunnel
)
1641 control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR
, 0);
1642 n_conn
= connection_or_connect(&firsthop
->extend_info
->addr
,
1643 firsthop
->extend_info
->port
,
1644 firsthop
->extend_info
->identity_digest
);
1645 if (!n_conn
) { /* connect failed, forget the whole thing */
1646 log_info(LD_CIRC
,"connect to firsthop failed. Closing.");
1647 return -END_CIRC_REASON_CONNECTFAILED
;
1651 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
1652 /* return success. The onion/circuit/etc will be taken care of
1653 * automatically (may already have been) whenever n_conn reaches
1654 * OR_CONN_STATE_OPEN.
1657 } else { /* it's already open. use it. */
1658 tor_assert(!circ
->_base
.n_hop
);
1659 circ
->_base
.n_conn
= n_conn
;
1660 log_debug(LD_CIRC
,"Conn open. Delivering first onion skin.");
1661 if ((err_reason
= circuit_send_next_onion_skin(circ
)) < 0) {
1662 log_info(LD_CIRC
,"circuit_send_next_onion_skin failed.");
1669 /** Find any circuits that are waiting on <b>or_conn</b> to become
1670 * open and get them to send their create cells forward.
1672 * Status is 1 if connect succeeded, or 0 if connect failed.
1675 circuit_n_conn_done(or_connection_t
*or_conn
, int status
)
1677 smartlist_t
*pending_circs
;
1680 log_debug(LD_CIRC
,"or_conn to %s/%s, status=%d",
1681 or_conn
->nickname
? or_conn
->nickname
: "NULL",
1682 or_conn
->_base
.address
, status
);
1684 pending_circs
= smartlist_create();
1685 circuit_get_all_pending_on_or_conn(pending_circs
, or_conn
);
1687 SMARTLIST_FOREACH_BEGIN(pending_circs
, circuit_t
*, circ
)
1689 /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
1690 * leaving them in in case it's possible for the status of a circuit to
1691 * change as we're going down the list. */
1692 if (circ
->marked_for_close
|| circ
->n_conn
|| !circ
->n_hop
||
1693 circ
->state
!= CIRCUIT_STATE_OR_WAIT
)
1696 if (tor_digest_is_zero(circ
->n_hop
->identity_digest
)) {
1697 /* Look at addr/port. This is an unkeyed connection. */
1698 if (!tor_addr_eq(&circ
->n_hop
->addr
, &or_conn
->_base
.addr
) ||
1699 circ
->n_hop
->port
!= or_conn
->_base
.port
)
1702 /* We expected a key. See if it's the right one. */
1703 if (memcmp(or_conn
->identity_digest
,
1704 circ
->n_hop
->identity_digest
, DIGEST_LEN
))
1707 if (!status
) { /* or_conn failed; close circ */
1708 log_info(LD_CIRC
,"or_conn failed. Closing circ.");
1709 circuit_mark_for_close(circ
, END_CIRC_REASON_OR_CONN_CLOSED
);
1712 log_debug(LD_CIRC
, "Found circ, sending create cell.");
1713 /* circuit_deliver_create_cell will set n_circ_id and add us to
1714 * orconn_circuid_circuit_map, so we don't need to call
1715 * set_circid_orconn here. */
1716 circ
->n_conn
= or_conn
;
1717 extend_info_free(circ
->n_hop
);
1720 if (CIRCUIT_IS_ORIGIN(circ
)) {
1722 circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ
))) < 0) {
1724 "send_next_onion_skin failed; circuit marked for closing.");
1725 circuit_mark_for_close(circ
, -err_reason
);
1727 /* XXX could this be bad, eg if next_onion_skin failed because conn
1731 /* pull the create cell out of circ->onionskin, and send it */
1732 tor_assert(circ
->n_conn_onionskin
);
1733 if (circuit_deliver_create_cell(circ
,CELL_CREATE
,
1734 circ
->n_conn_onionskin
)<0) {
1735 circuit_mark_for_close(circ
, END_CIRC_REASON_RESOURCELIMIT
);
1738 tor_free(circ
->n_conn_onionskin
);
1739 circuit_set_state(circ
, CIRCUIT_STATE_OPEN
);
1742 SMARTLIST_FOREACH_END(circ
);
1744 smartlist_free(pending_circs
);
1747 /** Find a new circid that isn't currently in use on the circ->n_conn
1749 * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
1750 * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
1752 * Return -1 if we failed to find a suitable circid, else return 0.
1755 circuit_deliver_create_cell(circuit_t
*circ
, uint8_t cell_type
,
1756 const char *payload
)
1762 tor_assert(circ
->n_conn
);
1763 tor_assert(payload
);
1764 tor_assert(cell_type
== CELL_CREATE
|| cell_type
== CELL_CREATE_FAST
);
1766 id
= get_unique_circ_id_by_conn(circ
->n_conn
);
1768 log_warn(LD_CIRC
,"failed to get unique circID.");
1771 log_debug(LD_CIRC
,"Chosen circID %u.", id
);
1772 circuit_set_n_circid_orconn(circ
, id
, circ
->n_conn
);
1774 memset(&cell
, 0, sizeof(cell_t
));
1775 cell
.command
= cell_type
;
1776 cell
.circ_id
= circ
->n_circ_id
;
1778 memcpy(cell
.payload
, payload
, ONIONSKIN_CHALLENGE_LEN
);
1779 append_cell_to_circuit_queue(circ
, circ
->n_conn
, &cell
,
1780 CELL_DIRECTION_OUT
, 0);
1782 if (CIRCUIT_IS_ORIGIN(circ
)) {
1783 /* mark it so it gets better rate limiting treatment. */
1784 circ
->n_conn
->client_used
= time(NULL
);
1790 /** We've decided to start our reachability testing. If all
1791 * is set, log this to the user. Return 1 if we did, or 0 if
1792 * we chose not to log anything. */
1794 inform_testing_reachability(void)
1797 routerinfo_t
*me
= router_get_my_routerinfo();
1800 control_event_server_status(LOG_NOTICE
,
1801 "CHECKING_REACHABILITY ORADDRESS=%s:%d",
1802 me
->address
, me
->or_port
);
1804 tor_snprintf(dirbuf
, sizeof(dirbuf
), " and DirPort %s:%d",
1805 me
->address
, me
->dir_port
);
1806 control_event_server_status(LOG_NOTICE
,
1807 "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
1808 me
->address
, me
->dir_port
);
1810 log_notice(LD_OR
, "Now checking whether ORPort %s:%d%s %s reachable... "
1811 "(this may take up to %d minutes -- look for log "
1812 "messages indicating success)",
1813 me
->address
, me
->or_port
,
1814 me
->dir_port
? dirbuf
: "",
1815 me
->dir_port
? "are" : "is",
1816 TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT
/60);
1821 /** Return true iff we should send a create_fast cell to start building a given
1824 should_use_create_fast_for_circuit(origin_circuit_t
*circ
)
1826 or_options_t
*options
= get_options();
1827 tor_assert(circ
->cpath
);
1828 tor_assert(circ
->cpath
->extend_info
);
1830 if (!circ
->cpath
->extend_info
->onion_key
)
1831 return 1; /* our hand is forced: only a create_fast will work. */
1832 if (!options
->FastFirstHopPK
)
1833 return 0; /* we prefer to avoid create_fast */
1834 if (server_mode(options
)) {
1835 /* We're a server, and we know an onion key. We can choose.
1836 * Prefer to blend in. */
1843 /** Return true if <b>circ</b> is the type of circuit we want to count
1844 * timeouts from. In particular, we want it to have not completed yet
1845 * (already completing indicates we cannibalized it), and we want it to
1846 * have exactly three hops.
1849 circuit_timeout_want_to_count_circ(origin_circuit_t
*circ
)
1851 return !circ
->has_opened
1852 && circ
->build_state
->desired_path_len
== DEFAULT_ROUTE_LEN
;
1855 /** This is the backbone function for building circuits.
1857 * If circ's first hop is closed, then we need to build a create
1858 * cell and send it forward.
1860 * Otherwise, we need to build a relay extend cell and send it
1863 * Return -reason if we want to tear down circ, else return 0.
1866 circuit_send_next_onion_skin(origin_circuit_t
*circ
)
1869 routerinfo_t
*router
;
1870 char payload
[2+4+DIGEST_LEN
+ONIONSKIN_CHALLENGE_LEN
];
1876 if (circ
->cpath
->state
== CPATH_STATE_CLOSED
) {
1879 log_debug(LD_CIRC
,"First skin; sending create cell.");
1880 if (circ
->build_state
->onehop_tunnel
)
1881 control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE
, 0);
1883 control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE
, 0);
1885 router
= router_get_by_digest(circ
->_base
.n_conn
->identity_digest
);
1886 fast
= should_use_create_fast_for_circuit(circ
);
1888 /* We are an OR and we know the right onion key: we should
1889 * send an old slow create cell.
1891 cell_type
= CELL_CREATE
;
1892 if (onion_skin_create(circ
->cpath
->extend_info
->onion_key
,
1893 &(circ
->cpath
->dh_handshake_state
),
1895 log_warn(LD_CIRC
,"onion_skin_create (first hop) failed.");
1896 return - END_CIRC_REASON_INTERNAL
;
1898 note_request("cell: create", 1);
1900 /* We are not an OR, and we're building the first hop of a circuit to a
1901 * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
1902 * and a DH operation. */
1903 cell_type
= CELL_CREATE_FAST
;
1904 memset(payload
, 0, sizeof(payload
));
1905 crypto_rand(circ
->cpath
->fast_handshake_state
,
1906 sizeof(circ
->cpath
->fast_handshake_state
));
1907 memcpy(payload
, circ
->cpath
->fast_handshake_state
,
1908 sizeof(circ
->cpath
->fast_handshake_state
));
1909 note_request("cell: create fast", 1);
1912 if (circuit_deliver_create_cell(TO_CIRCUIT(circ
), cell_type
, payload
) < 0)
1913 return - END_CIRC_REASON_RESOURCELIMIT
;
1915 circ
->cpath
->state
= CPATH_STATE_AWAITING_KEYS
;
1916 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
1917 log_info(LD_CIRC
,"First hop: finished sending %s cell to '%s'",
1918 fast
? "CREATE_FAST" : "CREATE",
1919 router
? router
->nickname
: "<unnamed>");
1921 tor_assert(circ
->cpath
->state
== CPATH_STATE_OPEN
);
1922 tor_assert(circ
->_base
.state
== CIRCUIT_STATE_BUILDING
);
1923 log_debug(LD_CIRC
,"starting to send subsequent skin.");
1924 hop
= onion_next_hop_in_cpath(circ
->cpath
);
1926 /* done building the circuit. whew. */
1927 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
1928 if (circuit_timeout_want_to_count_circ(circ
)) {
1931 tor_gettimeofday(&end
);
1932 timediff
= tv_mdiff(&circ
->_base
.highres_created
, &end
);
1935 * If the circuit build time is much greater than we would have cut
1936 * it off at, we probably had a suspend event along this codepath,
1937 * and we should discard the value.
1939 if (timediff
< 0 || timediff
> 2*circ_times
.close_ms
+1000) {
1940 log_notice(LD_CIRC
, "Strange value for circuit build time: %ldmsec. "
1941 "Assuming clock jump. Purpose %d", timediff
,
1942 circ
->_base
.purpose
);
1943 } else if (!circuit_build_times_disabled()) {
1944 /* Only count circuit times if the network is live */
1945 if (circuit_build_times_network_check_live(&circ_times
)) {
1946 circuit_build_times_add_time(&circ_times
, (build_time_t
)timediff
);
1947 circuit_build_times_set_timeout(&circ_times
);
1950 if (circ
->_base
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
1951 circuit_build_times_network_circ_success(&circ_times
);
1955 log_info(LD_CIRC
,"circuit built!");
1956 circuit_reset_failure_count(0);
1957 if (circ
->build_state
->onehop_tunnel
)
1958 control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS
, 0);
1959 if (!can_complete_circuit
&& !circ
->build_state
->onehop_tunnel
) {
1960 or_options_t
*options
= get_options();
1961 can_complete_circuit
=1;
1962 /* FFFF Log a count of known routers here */
1963 log_notice(LD_GENERAL
,
1964 "Tor has successfully opened a circuit. "
1965 "Looks like client functionality is working.");
1966 control_event_bootstrap(BOOTSTRAP_STATUS_DONE
, 0);
1967 control_event_client_status(LOG_NOTICE
, "CIRCUIT_ESTABLISHED");
1968 if (server_mode(options
) && !check_whether_orport_reachable()) {
1969 inform_testing_reachability();
1970 consider_testing_reachability(1, 1);
1973 circuit_rep_hist_note_result(circ
);
1974 circuit_has_opened(circ
); /* do other actions as necessary */
1976 /* We're done with measurement circuits here. Just close them */
1977 if (circ
->_base
.purpose
== CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
)
1978 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_FINISHED
);
1982 if (tor_addr_family(&hop
->extend_info
->addr
) != AF_INET
) {
1983 log_warn(LD_BUG
, "Trying to extend to a non-IPv4 address.");
1984 return - END_CIRC_REASON_INTERNAL
;
1987 set_uint32(payload
, tor_addr_to_ipv4n(&hop
->extend_info
->addr
));
1988 set_uint16(payload
+4, htons(hop
->extend_info
->port
));
1990 onionskin
= payload
+2+4;
1991 memcpy(payload
+2+4+ONIONSKIN_CHALLENGE_LEN
,
1992 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
1993 payload_len
= 2+4+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
;
1995 if (onion_skin_create(hop
->extend_info
->onion_key
,
1996 &(hop
->dh_handshake_state
), onionskin
) < 0) {
1997 log_warn(LD_CIRC
,"onion_skin_create failed.");
1998 return - END_CIRC_REASON_INTERNAL
;
2001 log_info(LD_CIRC
,"Sending extend relay cell.");
2002 note_request("cell: extend", 1);
2003 /* send it to hop->prev, because it will transfer
2004 * it to a create cell and then send to hop */
2005 if (relay_send_command_from_edge(0, TO_CIRCUIT(circ
),
2006 RELAY_COMMAND_EXTEND
,
2007 payload
, payload_len
, hop
->prev
) < 0)
2008 return 0; /* circuit is closed */
2010 hop
->state
= CPATH_STATE_AWAITING_KEYS
;
2015 /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
2016 * something has also gone wrong with our network: notify the user,
2017 * and abandon all not-yet-used circuits. */
2019 circuit_note_clock_jumped(int seconds_elapsed
)
2021 int severity
= server_mode(get_options()) ? LOG_WARN
: LOG_NOTICE
;
2022 tor_log(severity
, LD_GENERAL
, "Your system clock just jumped %d seconds %s; "
2023 "assuming established circuits no longer work.",
2024 seconds_elapsed
>=0 ? seconds_elapsed
: -seconds_elapsed
,
2025 seconds_elapsed
>=0 ? "forward" : "backward");
2026 control_event_general_status(LOG_WARN
, "CLOCK_JUMPED TIME=%d",
2028 can_complete_circuit
=0; /* so it'll log when it works again */
2029 control_event_client_status(severity
, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
2031 circuit_mark_all_unused_circs();
2032 circuit_expire_all_dirty_circs();
2035 /** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
2036 * skin and identity digest for the next hop. If we're already connected,
2037 * pass the onion skin to the next hop using a create cell; otherwise
2038 * launch a new OR connection, and <b>circ</b> will notice when the
2039 * connection succeeds or fails.
2041 * Return -1 if we want to warn and tear down the circuit, else return 0.
2044 circuit_extend(cell_t
*cell
, circuit_t
*circ
)
2046 or_connection_t
*n_conn
;
2049 char *id_digest
=NULL
;
2053 const char *msg
= NULL
;
2054 int should_launch
= 0;
2057 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2058 "n_conn already set. Bug/attack. Closing.");
2062 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2063 "conn to next hop already launched. Bug/attack. Closing.");
2067 if (!server_mode(get_options())) {
2068 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2069 "Got an extend cell, but running as a client. Closing.");
2073 relay_header_unpack(&rh
, cell
->payload
);
2075 if (rh
.length
< 4+2+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
) {
2076 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2077 "Wrong length %d on extend cell. Closing circuit.",
2082 n_addr32
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
));
2083 n_port
= ntohs(get_uint16(cell
->payload
+RELAY_HEADER_SIZE
+4));
2084 onionskin
= cell
->payload
+RELAY_HEADER_SIZE
+4+2;
2085 id_digest
= cell
->payload
+RELAY_HEADER_SIZE
+4+2+ONIONSKIN_CHALLENGE_LEN
;
2086 tor_addr_from_ipv4h(&n_addr
, n_addr32
);
2088 if (!n_port
|| !n_addr32
) {
2089 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2090 "Client asked me to extend to zero destination port or addr.");
2094 /* Check if they asked us for 0000..0000. We support using
2095 * an empty fingerprint for the first hop (e.g. for a bridge relay),
2096 * but we don't want to let people send us extend cells for empty
2097 * fingerprints -- a) because it opens the user up to a mitm attack,
2098 * and b) because it lets an attacker force the relay to hold open a
2099 * new TLS connection for each extend request. */
2100 if (tor_digest_is_zero(id_digest
)) {
2101 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2102 "Client asked me to extend without specifying an id_digest.");
2106 /* Next, check if we're being asked to connect to the hop that the
2107 * extend cell came from. There isn't any reason for that, and it can
2108 * assist circular-path attacks. */
2109 if (!memcmp(id_digest
, TO_OR_CIRCUIT(circ
)->p_conn
->identity_digest
,
2111 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2112 "Client asked me to extend back to the previous hop.");
2116 n_conn
= connection_or_get_for_extend(id_digest
,
2122 log_debug(LD_CIRC
|LD_OR
,"Next router (%s:%d): %s",
2123 fmt_addr(&n_addr
), (int)n_port
, msg
?msg
:"????");
2125 circ
->n_hop
= extend_info_alloc(NULL
/*nickname*/,
2130 circ
->n_conn_onionskin
= tor_malloc(ONIONSKIN_CHALLENGE_LEN
);
2131 memcpy(circ
->n_conn_onionskin
, onionskin
, ONIONSKIN_CHALLENGE_LEN
);
2132 circuit_set_state(circ
, CIRCUIT_STATE_OR_WAIT
);
2134 if (should_launch
) {
2135 /* we should try to open a connection */
2136 n_conn
= connection_or_connect(&n_addr
, n_port
, id_digest
);
2138 log_info(LD_CIRC
,"Launching n_conn failed. Closing circuit.");
2139 circuit_mark_for_close(circ
, END_CIRC_REASON_CONNECTFAILED
);
2142 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
2144 /* return success. The onion/circuit/etc will be taken care of
2145 * automatically (may already have been) whenever n_conn reaches
2146 * OR_CONN_STATE_OPEN.
2151 tor_assert(!circ
->n_hop
); /* Connection is already established. */
2152 circ
->n_conn
= n_conn
;
2153 log_debug(LD_CIRC
,"n_conn is %s:%u",
2154 n_conn
->_base
.address
,n_conn
->_base
.port
);
2156 if (circuit_deliver_create_cell(circ
, CELL_CREATE
, onionskin
) < 0)
2161 /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
2162 * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
2164 * - 20 to initialize f_digest
2165 * - 20 to initialize b_digest
2166 * - 16 to key f_crypto
2167 * - 16 to key b_crypto
2169 * (If 'reverse' is true, then f_XX and b_XX are swapped.)
2172 circuit_init_cpath_crypto(crypt_path_t
*cpath
, const char *key_data
,
2175 crypto_digest_env_t
*tmp_digest
;
2176 crypto_cipher_env_t
*tmp_crypto
;
2179 tor_assert(key_data
);
2180 tor_assert(!(cpath
->f_crypto
|| cpath
->b_crypto
||
2181 cpath
->f_digest
|| cpath
->b_digest
));
2183 cpath
->f_digest
= crypto_new_digest_env();
2184 crypto_digest_add_bytes(cpath
->f_digest
, key_data
, DIGEST_LEN
);
2185 cpath
->b_digest
= crypto_new_digest_env();
2186 crypto_digest_add_bytes(cpath
->b_digest
, key_data
+DIGEST_LEN
, DIGEST_LEN
);
2188 if (!(cpath
->f_crypto
=
2189 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
),1))) {
2190 log_warn(LD_BUG
,"Forward cipher initialization failed.");
2193 if (!(cpath
->b_crypto
=
2194 crypto_create_init_cipher(key_data
+(2*DIGEST_LEN
)+CIPHER_KEY_LEN
,0))) {
2195 log_warn(LD_BUG
,"Backward cipher initialization failed.");
2200 tmp_digest
= cpath
->f_digest
;
2201 cpath
->f_digest
= cpath
->b_digest
;
2202 cpath
->b_digest
= tmp_digest
;
2203 tmp_crypto
= cpath
->f_crypto
;
2204 cpath
->f_crypto
= cpath
->b_crypto
;
2205 cpath
->b_crypto
= tmp_crypto
;
2211 /** A created or extended cell came back to us on the circuit, and it included
2212 * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body
2213 * contains (the second DH key, plus KH). If <b>reply_type</b> is
2214 * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
2216 * Calculate the appropriate keys and digests, make sure KH is
2217 * correct, and initialize this hop of the cpath.
2219 * Return - reason if we want to mark circ for close, else return 0.
2222 circuit_finish_handshake(origin_circuit_t
*circ
, uint8_t reply_type
,
2225 char keys
[CPATH_KEY_MATERIAL_LEN
];
2228 if (circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
)
2231 hop
= onion_next_hop_in_cpath(circ
->cpath
);
2232 if (!hop
) { /* got an extended when we're all done? */
2233 log_warn(LD_PROTOCOL
,"got extended when circ already built? Closing.");
2234 return - END_CIRC_REASON_TORPROTOCOL
;
2237 tor_assert(hop
->state
== CPATH_STATE_AWAITING_KEYS
);
2239 if (reply_type
== CELL_CREATED
&& hop
->dh_handshake_state
) {
2240 if (onion_skin_client_handshake(hop
->dh_handshake_state
, reply
, keys
,
2241 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
2242 log_warn(LD_CIRC
,"onion_skin_client_handshake failed.");
2243 return -END_CIRC_REASON_TORPROTOCOL
;
2245 /* Remember hash of g^xy */
2246 memcpy(hop
->handshake_digest
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
2247 } else if (reply_type
== CELL_CREATED_FAST
&& !hop
->dh_handshake_state
) {
2248 if (fast_client_handshake(hop
->fast_handshake_state
, reply
, keys
,
2249 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
2250 log_warn(LD_CIRC
,"fast_client_handshake failed.");
2251 return -END_CIRC_REASON_TORPROTOCOL
;
2253 memcpy(hop
->handshake_digest
, reply
+DIGEST_LEN
, DIGEST_LEN
);
2255 log_warn(LD_PROTOCOL
,"CREATED cell type did not match CREATE cell type.");
2256 return -END_CIRC_REASON_TORPROTOCOL
;
2259 crypto_dh_free(hop
->dh_handshake_state
); /* don't need it anymore */
2260 hop
->dh_handshake_state
= NULL
;
2262 memset(hop
->fast_handshake_state
, 0, sizeof(hop
->fast_handshake_state
));
2264 if (circuit_init_cpath_crypto(hop
, keys
, 0)<0) {
2265 return -END_CIRC_REASON_TORPROTOCOL
;
2268 hop
->state
= CPATH_STATE_OPEN
;
2269 log_info(LD_CIRC
,"Finished building %scircuit hop:",
2270 (reply_type
== CELL_CREATED_FAST
) ? "fast " : "");
2271 circuit_log_path(LOG_INFO
,LD_CIRC
,circ
);
2272 control_event_circuit_status(circ
, CIRC_EVENT_EXTENDED
, 0);
2277 /** We received a relay truncated cell on circ.
2279 * Since we don't ask for truncates currently, getting a truncated
2280 * means that a connection broke or an extend failed. For now,
2281 * just give up: for circ to close, and return 0.
2284 circuit_truncated(origin_circuit_t
*circ
, crypt_path_t
*layer
)
2286 // crypt_path_t *victim;
2287 // connection_t *stream;
2292 /* XXX Since we don't ask for truncates currently, getting a truncated
2293 * means that a connection broke or an extend failed. For now,
2296 circuit_mark_for_close(TO_CIRCUIT(circ
),
2297 END_CIRC_REASON_FLAG_REMOTE
|END_CIRC_REASON_OR_CONN_CLOSED
);
2301 while (layer
->next
!= circ
->cpath
) {
2302 /* we need to clear out layer->next */
2303 victim
= layer
->next
;
2304 log_debug(LD_CIRC
, "Killing a layer of the cpath.");
2306 for (stream
= circ
->p_streams
; stream
; stream
=stream
->next_stream
) {
2307 if (stream
->cpath_layer
== victim
) {
2308 log_info(LD_APP
, "Marking stream %d for close because of truncate.",
2310 /* no need to send 'end' relay cells,
2311 * because the other side's already dead
2313 connection_mark_unattached_ap(stream
, END_STREAM_REASON_DESTROY
);
2317 layer
->next
= victim
->next
;
2318 circuit_free_cpath_node(victim
);
2321 log_info(LD_CIRC
, "finished");
2326 /** Given a response payload and keys, initialize, then send a created
2330 onionskin_answer(or_circuit_t
*circ
, uint8_t cell_type
, const char *payload
,
2334 crypt_path_t
*tmp_cpath
;
2336 tmp_cpath
= tor_malloc_zero(sizeof(crypt_path_t
));
2337 tmp_cpath
->magic
= CRYPT_PATH_MAGIC
;
2339 memset(&cell
, 0, sizeof(cell_t
));
2340 cell
.command
= cell_type
;
2341 cell
.circ_id
= circ
->p_circ_id
;
2343 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
2345 memcpy(cell
.payload
, payload
,
2346 cell_type
== CELL_CREATED
? ONIONSKIN_REPLY_LEN
: DIGEST_LEN
*2);
2348 log_debug(LD_CIRC
,"init digest forward 0x%.8x, backward 0x%.8x.",
2349 (unsigned int)get_uint32(keys
),
2350 (unsigned int)get_uint32(keys
+20));
2351 if (circuit_init_cpath_crypto(tmp_cpath
, keys
, 0)<0) {
2352 log_warn(LD_BUG
,"Circuit initialization failed");
2353 tor_free(tmp_cpath
);
2356 circ
->n_digest
= tmp_cpath
->f_digest
;
2357 circ
->n_crypto
= tmp_cpath
->f_crypto
;
2358 circ
->p_digest
= tmp_cpath
->b_digest
;
2359 circ
->p_crypto
= tmp_cpath
->b_crypto
;
2360 tmp_cpath
->magic
= 0;
2361 tor_free(tmp_cpath
);
2363 if (cell_type
== CELL_CREATED
)
2364 memcpy(circ
->handshake_digest
, cell
.payload
+DH_KEY_LEN
, DIGEST_LEN
);
2366 memcpy(circ
->handshake_digest
, cell
.payload
+DIGEST_LEN
, DIGEST_LEN
);
2368 circ
->is_first_hop
= (cell_type
== CELL_CREATED_FAST
);
2370 append_cell_to_circuit_queue(TO_CIRCUIT(circ
),
2371 circ
->p_conn
, &cell
, CELL_DIRECTION_IN
, 0);
2372 log_debug(LD_CIRC
,"Finished sending 'created' cell.");
2374 if (!is_local_addr(&circ
->p_conn
->_base
.addr
) &&
2375 !connection_or_nonopen_was_started_here(circ
->p_conn
)) {
2376 /* record that we could process create cells from a non-local conn
2377 * that we didn't initiate; presumably this means that create cells
2378 * can reach us too. */
2379 router_orport_found_reachable();
2385 /** Choose a length for a circuit of purpose <b>purpose</b>.
2386 * Default length is 3 + the number of endpoints that would give something
2387 * away. If the routerlist <b>routers</b> doesn't have enough routers
2388 * to handle the desired path length, return as large a path length as
2389 * is feasible, except if it's less than 2, in which case return -1.
2392 new_route_len(uint8_t purpose
, extend_info_t
*exit
,
2393 smartlist_t
*routers
)
2395 int num_acceptable_routers
;
2398 tor_assert(routers
);
2400 routelen
= DEFAULT_ROUTE_LEN
;
2402 purpose
!= CIRCUIT_PURPOSE_TESTING
&&
2403 purpose
!= CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
)
2406 num_acceptable_routers
= count_acceptable_routers(routers
);
2408 log_debug(LD_CIRC
,"Chosen route length %d (%d/%d routers suitable).",
2409 routelen
, num_acceptable_routers
, smartlist_len(routers
));
2411 if (num_acceptable_routers
< 2) {
2413 "Not enough acceptable routers (%d). Discarding this circuit.",
2414 num_acceptable_routers
);
2418 if (num_acceptable_routers
< routelen
) {
2419 log_info(LD_CIRC
,"Not enough routers: cutting routelen from %d to %d.",
2420 routelen
, num_acceptable_routers
);
2421 routelen
= num_acceptable_routers
;
2427 /** Fetch the list of predicted ports, dup it into a smartlist of
2428 * uint16_t's, remove the ones that are already handled by an
2429 * existing circuit, and return it.
2431 static smartlist_t
*
2432 circuit_get_unhandled_ports(time_t now
)
2434 smartlist_t
*source
= rep_hist_get_predicted_ports(now
);
2435 smartlist_t
*dest
= smartlist_create();
2439 for (i
= 0; i
< smartlist_len(source
); ++i
) {
2440 tmp
= tor_malloc(sizeof(uint16_t));
2441 memcpy(tmp
, smartlist_get(source
, i
), sizeof(uint16_t));
2442 smartlist_add(dest
, tmp
);
2445 circuit_remove_handled_ports(dest
);
2449 /** Return 1 if we already have circuits present or on the way for
2450 * all anticipated ports. Return 0 if we should make more.
2452 * If we're returning 0, set need_uptime and need_capacity to
2453 * indicate any requirements that the unhandled ports have.
2456 circuit_all_predicted_ports_handled(time_t now
, int *need_uptime
,
2461 smartlist_t
*sl
= circuit_get_unhandled_ports(now
);
2462 smartlist_t
*LongLivedServices
= get_options()->LongLivedPorts
;
2463 tor_assert(need_uptime
);
2464 tor_assert(need_capacity
);
2465 // Always predict need_capacity
2467 enough
= (smartlist_len(sl
) == 0);
2468 for (i
= 0; i
< smartlist_len(sl
); ++i
) {
2469 port
= smartlist_get(sl
, i
);
2470 if (smartlist_string_num_isin(LongLivedServices
, *port
))
2478 /** Return 1 if <b>router</b> can handle one or more of the ports in
2479 * <b>needed_ports</b>, else return 0.
2482 router_handles_some_port(routerinfo_t
*router
, smartlist_t
*needed_ports
)
2487 for (i
= 0; i
< smartlist_len(needed_ports
); ++i
) {
2488 addr_policy_result_t r
;
2489 /* alignment issues aren't a worry for this dereference, since
2490 needed_ports is explicitly a smartlist of uint16_t's */
2491 port
= *(uint16_t *)smartlist_get(needed_ports
, i
);
2493 r
= compare_addr_to_addr_policy(0, port
, router
->exit_policy
);
2494 if (r
!= ADDR_POLICY_REJECTED
&& r
!= ADDR_POLICY_PROBABLY_REJECTED
)
2500 /** Return true iff <b>conn</b> needs another general circuit to be
2503 ap_stream_wants_exit_attention(connection_t
*conn
)
2505 if (conn
->type
== CONN_TYPE_AP
&&
2506 conn
->state
== AP_CONN_STATE_CIRCUIT_WAIT
&&
2507 !conn
->marked_for_close
&&
2508 !(TO_EDGE_CONN(conn
)->want_onehop
) && /* ignore one-hop streams */
2509 !(TO_EDGE_CONN(conn
)->use_begindir
) && /* ignore targeted dir fetches */
2510 !(TO_EDGE_CONN(conn
)->chosen_exit_name
) && /* ignore defined streams */
2511 !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn
)) &&
2512 !circuit_stream_is_being_handled(TO_EDGE_CONN(conn
), 0,
2513 MIN_CIRCUITS_HANDLING_STREAM
))
2518 /** Return a pointer to a suitable router to be the exit node for the
2519 * general-purpose circuit we're about to build.
2521 * Look through the connection array, and choose a router that maximizes
2522 * the number of pending streams that can exit from this router.
2524 * Return NULL if we can't find any suitable routers.
2526 static routerinfo_t
*
2527 choose_good_exit_server_general(routerlist_t
*dir
, int need_uptime
,
2532 int n_pending_connections
= 0;
2533 smartlist_t
*connections
;
2534 int best_support
= -1;
2535 int n_best_support
=0;
2536 routerinfo_t
*router
;
2537 or_options_t
*options
= get_options();
2539 connections
= get_connection_array();
2541 /* Count how many connections are waiting for a circuit to be built.
2542 * We use this for log messages now, but in the future we may depend on it.
2544 SMARTLIST_FOREACH(connections
, connection_t
*, conn
,
2546 if (ap_stream_wants_exit_attention(conn
))
2547 ++n_pending_connections
;
2549 // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
2550 // n_pending_connections);
2551 /* Now we count, for each of the routers in the directory, how many
2552 * of the pending connections could possibly exit from that
2553 * router (n_supported[i]). (We can't be sure about cases where we
2554 * don't know the IP address of the pending connection.)
2556 * -1 means "Don't use this router at all."
2558 n_supported
= tor_malloc(sizeof(int)*smartlist_len(dir
->routers
));
2559 for (i
= 0; i
< smartlist_len(dir
->routers
); ++i
) {/* iterate over routers */
2560 router
= smartlist_get(dir
->routers
, i
);
2561 if (router_is_me(router
)) {
2562 n_supported
[i
] = -1;
2563 // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
2564 /* XXX there's probably a reverse predecessor attack here, but
2565 * it's slow. should we take this out? -RD
2569 if (!router
->is_running
|| router
->is_bad_exit
) {
2570 n_supported
[i
] = -1;
2571 continue; /* skip routers that are known to be down or bad exits */
2573 if (router_is_unreliable(router
, need_uptime
, need_capacity
, 0) &&
2574 (!options
->ExitNodes
||
2575 !routerset_contains_router(options
->ExitNodes
, router
))) {
2576 /* FFFF Someday, differentiate between a routerset that names
2577 * routers, and a routerset that names countries, and only do this
2578 * check if they've asked for specific exit relays. Or if the country
2579 * they ask for is rare. Or something. */
2580 n_supported
[i
] = -1;
2581 continue; /* skip routers that are not suitable, unless we have
2582 * ExitNodes set, in which case we asked for it */
2584 if (!(router
->is_valid
|| options
->_AllowInvalid
& ALLOW_INVALID_EXIT
)) {
2585 /* if it's invalid and we don't want it */
2586 n_supported
[i
] = -1;
2587 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
2588 // router->nickname, i);
2589 continue; /* skip invalid routers */
2591 if (options
->ExcludeSingleHopRelays
&& router
->allow_single_hop_exits
) {
2592 n_supported
[i
] = -1;
2595 if (router_exit_policy_rejects_all(router
)) {
2596 n_supported
[i
] = -1;
2597 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
2598 // router->nickname, i);
2599 continue; /* skip routers that reject all */
2602 /* iterate over connections */
2603 SMARTLIST_FOREACH(connections
, connection_t
*, conn
,
2605 if (!ap_stream_wants_exit_attention(conn
))
2606 continue; /* Skip everything but APs in CIRCUIT_WAIT */
2607 if (connection_ap_can_use_exit(TO_EDGE_CONN(conn
), router
, 1)) {
2609 // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
2610 // router->nickname, i, n_supported[i]);
2612 // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
2613 // router->nickname, i);
2615 }); /* End looping over connections. */
2616 if (n_pending_connections
> 0 && n_supported
[i
] == 0) {
2617 /* Leave best_support at -1 if that's where it is, so we can
2618 * distinguish it later. */
2621 if (n_supported
[i
] > best_support
) {
2622 /* If this router is better than previous ones, remember its index
2623 * and goodness, and start counting how many routers are this good. */
2624 best_support
= n_supported
[i
]; n_best_support
=1;
2625 // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
2626 // router->nickname);
2627 } else if (n_supported
[i
] == best_support
) {
2628 /* If this router is _as good_ as the best one, just increment the
2629 * count of equally good routers.*/
2634 "Found %d servers that might support %d/%d pending connections.",
2635 n_best_support
, best_support
>= 0 ? best_support
: 0,
2636 n_pending_connections
);
2638 /* If any routers definitely support any pending connections, choose one
2640 if (best_support
> 0) {
2641 smartlist_t
*supporting
= smartlist_create(), *use
= smartlist_create();
2643 for (i
= 0; i
< smartlist_len(dir
->routers
); i
++)
2644 if (n_supported
[i
] == best_support
)
2645 smartlist_add(supporting
, smartlist_get(dir
->routers
, i
));
2647 routersets_get_disjunction(use
, supporting
, options
->ExitNodes
,
2648 options
->_ExcludeExitNodesUnion
, 1);
2649 if (smartlist_len(use
) == 0 && options
->ExitNodes
&&
2650 !options
->StrictNodes
) { /* give up on exitnodes and try again */
2651 routersets_get_disjunction(use
, supporting
, NULL
,
2652 options
->_ExcludeExitNodesUnion
, 1);
2654 router
= routerlist_sl_choose_by_bandwidth(use
, WEIGHT_FOR_EXIT
);
2655 smartlist_free(use
);
2656 smartlist_free(supporting
);
2658 /* Either there are no pending connections, or no routers even seem to
2659 * possibly support any of them. Choose a router at random that satisfies
2660 * at least one predicted exit port. */
2663 smartlist_t
*needed_ports
, *supporting
, *use
;
2665 if (best_support
== -1) {
2666 if (need_uptime
|| need_capacity
) {
2668 "We couldn't find any live%s%s routers; falling back "
2669 "to list of all routers.",
2670 need_capacity
?", fast":"",
2671 need_uptime
?", stable":"");
2672 tor_free(n_supported
);
2673 return choose_good_exit_server_general(dir
, 0, 0);
2675 log_notice(LD_CIRC
, "All routers are down or won't exit%s -- "
2676 "choosing a doomed exit at random.",
2677 options
->_ExcludeExitNodesUnion
? " or are Excluded" : "");
2679 supporting
= smartlist_create();
2680 use
= smartlist_create();
2681 needed_ports
= circuit_get_unhandled_ports(time(NULL
));
2682 for (attempt
= 0; attempt
< 2; attempt
++) {
2683 /* try once to pick only from routers that satisfy a needed port,
2684 * then if there are none, pick from any that support exiting. */
2685 for (i
= 0; i
< smartlist_len(dir
->routers
); i
++) {
2686 router
= smartlist_get(dir
->routers
, i
);
2687 if (n_supported
[i
] != -1 &&
2688 (attempt
|| router_handles_some_port(router
, needed_ports
))) {
2689 // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
2690 // try, router->nickname);
2691 smartlist_add(supporting
, router
);
2695 routersets_get_disjunction(use
, supporting
, options
->ExitNodes
,
2696 options
->_ExcludeExitNodesUnion
, 1);
2697 if (smartlist_len(use
) == 0 && options
->ExitNodes
&&
2698 !options
->StrictNodes
) { /* give up on exitnodes and try again */
2699 routersets_get_disjunction(use
, supporting
, NULL
,
2700 options
->_ExcludeExitNodesUnion
, 1);
2702 /* FFF sometimes the above results in null, when the requested
2703 * exit node is considered down by the consensus. we should pick
2704 * it anyway, since the user asked for it. */
2705 router
= routerlist_sl_choose_by_bandwidth(use
, WEIGHT_FOR_EXIT
);
2708 smartlist_clear(supporting
);
2709 smartlist_clear(use
);
2711 SMARTLIST_FOREACH(needed_ports
, uint16_t *, cp
, tor_free(cp
));
2712 smartlist_free(needed_ports
);
2713 smartlist_free(use
);
2714 smartlist_free(supporting
);
2717 tor_free(n_supported
);
2719 log_info(LD_CIRC
, "Chose exit server '%s'", router
->nickname
);
2722 if (options
->ExitNodes
&& options
->StrictNodes
) {
2724 "No specified exit routers seem to be running, and "
2725 "StrictNodes is set: can't choose an exit.");
2730 /** Return a pointer to a suitable router to be the exit node for the
2731 * circuit of purpose <b>purpose</b> that we're about to build (or NULL
2732 * if no router is suitable).
2734 * For general-purpose circuits, pass it off to
2735 * choose_good_exit_server_general()
2737 * For client-side rendezvous circuits, choose a random node, weighted
2738 * toward the preferences in 'options'.
2740 static routerinfo_t
*
2741 choose_good_exit_server(uint8_t purpose
, routerlist_t
*dir
,
2742 int need_uptime
, int need_capacity
, int is_internal
)
2744 or_options_t
*options
= get_options();
2745 router_crn_flags_t flags
= 0;
2747 flags
|= CRN_NEED_UPTIME
;
2749 flags
|= CRN_NEED_CAPACITY
;
2752 case CIRCUIT_PURPOSE_C_GENERAL
:
2753 if (options
->_AllowInvalid
& ALLOW_INVALID_MIDDLE
)
2754 flags
|= CRN_ALLOW_INVALID
;
2755 if (is_internal
) /* pick it like a middle hop */
2756 return router_choose_random_node(NULL
, options
->ExcludeNodes
, flags
);
2758 return choose_good_exit_server_general(dir
,need_uptime
,need_capacity
);
2759 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
2760 if (options
->_AllowInvalid
& ALLOW_INVALID_RENDEZVOUS
)
2761 flags
|= CRN_ALLOW_INVALID
;
2762 return router_choose_random_node(NULL
, options
->ExcludeNodes
, flags
);
2764 log_warn(LD_BUG
,"Unhandled purpose %d", purpose
);
2765 tor_fragile_assert();
2769 /** Log a warning if the user specified an exit for the circuit that
2770 * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
2772 warn_if_last_router_excluded(origin_circuit_t
*circ
, const extend_info_t
*exit
)
2774 or_options_t
*options
= get_options();
2775 routerset_t
*rs
= options
->ExcludeNodes
;
2776 const char *description
;
2777 int domain
= LD_CIRC
;
2778 uint8_t purpose
= circ
->_base
.purpose
;
2780 if (circ
->build_state
->onehop_tunnel
)
2786 case CIRCUIT_PURPOSE_OR
:
2787 case CIRCUIT_PURPOSE_INTRO_POINT
:
2788 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
2789 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
2790 log_warn(LD_BUG
, "Called on non-origin circuit (purpose %d)",
2793 case CIRCUIT_PURPOSE_C_GENERAL
:
2794 if (circ
->build_state
->is_internal
)
2796 description
= "Requested exit node";
2797 rs
= options
->_ExcludeExitNodesUnion
;
2799 case CIRCUIT_PURPOSE_C_INTRODUCING
:
2800 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
2801 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
2802 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
2803 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
2804 case CIRCUIT_PURPOSE_S_REND_JOINED
:
2805 case CIRCUIT_PURPOSE_TESTING
:
2807 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
2808 case CIRCUIT_PURPOSE_C_REND_READY
:
2809 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
2810 case CIRCUIT_PURPOSE_C_REND_JOINED
:
2811 description
= "Chosen rendezvous point";
2814 case CIRCUIT_PURPOSE_CONTROLLER
:
2815 rs
= options
->_ExcludeExitNodesUnion
;
2816 description
= "Controller-selected circuit target";
2820 if (routerset_contains_extendinfo(rs
, exit
)) {
2821 log_fn(LOG_WARN
, domain
, "%s '%s' is in ExcludeNodes%s. Using anyway "
2822 "(circuit purpose %d).",
2823 description
,exit
->nickname
,
2824 rs
==options
->ExcludeNodes
?"":" or ExcludeExitNodes",
2826 circuit_log_path(LOG_WARN
, domain
, circ
);
2832 /** Decide a suitable length for circ's cpath, and pick an exit
2833 * router (or use <b>exit</b> if provided). Store these in the
2834 * cpath. Return 0 if ok, -1 if circuit should be closed. */
2836 onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
2838 cpath_build_state_t
*state
= circ
->build_state
;
2839 routerlist_t
*rl
= router_get_routerlist();
2841 if (state
->onehop_tunnel
) {
2842 log_debug(LD_CIRC
, "Launching a one-hop circuit for dir tunnel.");
2843 state
->desired_path_len
= 1;
2845 int r
= new_route_len(circ
->_base
.purpose
, exit
, rl
->routers
);
2846 if (r
< 1) /* must be at least 1 */
2848 state
->desired_path_len
= r
;
2851 if (exit
) { /* the circuit-builder pre-requested one */
2852 warn_if_last_router_excluded(circ
, exit
);
2853 log_info(LD_CIRC
,"Using requested exit node '%s'", exit
->nickname
);
2854 exit
= extend_info_dup(exit
);
2855 } else { /* we have to decide one */
2856 routerinfo_t
*router
=
2857 choose_good_exit_server(circ
->_base
.purpose
, rl
, state
->need_uptime
,
2858 state
->need_capacity
, state
->is_internal
);
2860 log_warn(LD_CIRC
,"failed to choose an exit server");
2863 exit
= extend_info_from_router(router
);
2865 state
->chosen_exit
= exit
;
2869 /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
2870 * hop to the cpath reflecting this. Don't send the next extend cell --
2871 * the caller will do this if it wants to.
2874 circuit_append_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
2876 cpath_build_state_t
*state
;
2880 state
= circ
->build_state
;
2882 extend_info_free(state
->chosen_exit
);
2883 state
->chosen_exit
= extend_info_dup(exit
);
2885 ++circ
->build_state
->desired_path_len
;
2886 onion_append_hop(&circ
->cpath
, exit
);
2890 /** Take an open <b>circ</b>, and add a new hop at the end, based on
2891 * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
2892 * send the next extend cell to begin connecting to that hop.
2895 circuit_extend_to_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
2898 warn_if_last_router_excluded(circ
, exit
);
2899 circuit_append_new_exit(circ
, exit
);
2900 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
2901 if ((err_reason
= circuit_send_next_onion_skin(circ
))<0) {
2902 log_warn(LD_CIRC
, "Couldn't extend circuit to new point '%s'.",
2904 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
2910 /** Return the number of routers in <b>routers</b> that are currently up
2911 * and available for building circuits through.
2914 count_acceptable_routers(smartlist_t
*routers
)
2920 n
= smartlist_len(routers
);
2922 r
= smartlist_get(routers
, i
);
2923 // log_debug(LD_CIRC,
2924 // "Contemplating whether router %d (%s) is a new option.",
2926 if (r
->is_running
== 0) {
2927 // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
2930 if (r
->is_valid
== 0) {
2931 // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
2933 /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
2934 * allows this node in some places, then we're getting an inaccurate
2935 * count. For now, be conservative and don't count it. But later we
2936 * should try to be smarter. */
2939 // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
2941 ; /* C requires an explicit statement after the label */
2947 /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
2948 * This function is used to extend cpath by another hop.
2951 onion_append_to_cpath(crypt_path_t
**head_ptr
, crypt_path_t
*new_hop
)
2954 new_hop
->next
= (*head_ptr
);
2955 new_hop
->prev
= (*head_ptr
)->prev
;
2956 (*head_ptr
)->prev
->next
= new_hop
;
2957 (*head_ptr
)->prev
= new_hop
;
2959 *head_ptr
= new_hop
;
2960 new_hop
->prev
= new_hop
->next
= new_hop
;
2964 /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
2965 * and <b>state</b> and the cpath <b>head</b> (currently populated only
2966 * to length <b>cur_len</b> to decide a suitable middle hop for a
2967 * circuit. In particular, make sure we don't pick the exit node or its
2968 * family, and make sure we don't duplicate any previous nodes or their
2970 static routerinfo_t
*
2971 choose_good_middle_server(uint8_t purpose
,
2972 cpath_build_state_t
*state
,
2977 routerinfo_t
*r
, *choice
;
2978 crypt_path_t
*cpath
;
2979 smartlist_t
*excluded
;
2980 or_options_t
*options
= get_options();
2981 router_crn_flags_t flags
= 0;
2982 tor_assert(_CIRCUIT_PURPOSE_MIN
<= purpose
&&
2983 purpose
<= _CIRCUIT_PURPOSE_MAX
);
2985 log_debug(LD_CIRC
, "Contemplating intermediate hop: random choice.");
2986 excluded
= smartlist_create();
2987 if ((r
= build_state_get_exit_router(state
))) {
2988 smartlist_add(excluded
, r
);
2989 routerlist_add_family(excluded
, r
);
2991 for (i
= 0, cpath
= head
; i
< cur_len
; ++i
, cpath
=cpath
->next
) {
2992 if ((r
= router_get_by_digest(cpath
->extend_info
->identity_digest
))) {
2993 smartlist_add(excluded
, r
);
2994 routerlist_add_family(excluded
, r
);
2998 if (state
->need_uptime
)
2999 flags
|= CRN_NEED_UPTIME
;
3000 if (state
->need_capacity
)
3001 flags
|= CRN_NEED_CAPACITY
;
3002 if (options
->_AllowInvalid
& ALLOW_INVALID_MIDDLE
)
3003 flags
|= CRN_ALLOW_INVALID
;
3004 choice
= router_choose_random_node(excluded
, options
->ExcludeNodes
, flags
);
3005 smartlist_free(excluded
);
3009 /** Pick a good entry server for the circuit to be built according to
3010 * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
3011 * router (if we're an OR), and respect firewall settings; if we're
3012 * configured to use entry guards, return one.
3014 * If <b>state</b> is NULL, we're choosing a router to serve as an entry
3015 * guard, not for any particular circuit.
3017 static routerinfo_t
*
3018 choose_good_entry_server(uint8_t purpose
, cpath_build_state_t
*state
)
3020 routerinfo_t
*r
, *choice
;
3021 smartlist_t
*excluded
;
3022 or_options_t
*options
= get_options();
3023 router_crn_flags_t flags
= CRN_NEED_GUARD
;
3025 if (state
&& options
->UseEntryGuards
&&
3026 (purpose
!= CIRCUIT_PURPOSE_TESTING
|| options
->BridgeRelay
)) {
3027 return choose_random_entry(state
);
3030 excluded
= smartlist_create();
3032 if (state
&& (r
= build_state_get_exit_router(state
))) {
3033 smartlist_add(excluded
, r
);
3034 routerlist_add_family(excluded
, r
);
3036 if (firewall_is_fascist_or()) {
3037 /*XXXX This could slow things down a lot; use a smarter implementation */
3038 /* exclude all ORs that listen on the wrong port, if anybody notices. */
3039 routerlist_t
*rl
= router_get_routerlist();
3042 for (i
=0; i
< smartlist_len(rl
->routers
); i
++) {
3043 r
= smartlist_get(rl
->routers
, i
);
3044 if (!fascist_firewall_allows_or(r
))
3045 smartlist_add(excluded
, r
);
3048 /* and exclude current entry guards, if applicable */
3049 if (options
->UseEntryGuards
&& entry_guards
) {
3050 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
3052 if ((r
= router_get_by_digest(entry
->identity
))) {
3053 smartlist_add(excluded
, r
);
3054 routerlist_add_family(excluded
, r
);
3060 if (state
->need_uptime
)
3061 flags
|= CRN_NEED_UPTIME
;
3062 if (state
->need_capacity
)
3063 flags
|= CRN_NEED_CAPACITY
;
3065 if (options
->_AllowInvalid
& ALLOW_INVALID_ENTRY
)
3066 flags
|= CRN_ALLOW_INVALID
;
3068 choice
= router_choose_random_node(excluded
, options
->ExcludeNodes
, flags
);
3069 smartlist_free(excluded
);
3073 /** Return the first non-open hop in cpath, or return NULL if all
3075 static crypt_path_t
*
3076 onion_next_hop_in_cpath(crypt_path_t
*cpath
)
3078 crypt_path_t
*hop
= cpath
;
3080 if (hop
->state
!= CPATH_STATE_OPEN
)
3083 } while (hop
!= cpath
);
3087 /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
3088 * based on <b>state</b>. Append the hop info to head_ptr.
3091 onion_extend_cpath(origin_circuit_t
*circ
)
3093 uint8_t purpose
= circ
->_base
.purpose
;
3094 cpath_build_state_t
*state
= circ
->build_state
;
3095 int cur_len
= circuit_get_cpath_len(circ
);
3096 extend_info_t
*info
= NULL
;
3098 if (cur_len
>= state
->desired_path_len
) {
3099 log_debug(LD_CIRC
, "Path is complete: %d steps long",
3100 state
->desired_path_len
);
3104 log_debug(LD_CIRC
, "Path is %d long; we want %d", cur_len
,
3105 state
->desired_path_len
);
3107 if (cur_len
== state
->desired_path_len
- 1) { /* Picking last node */
3108 info
= extend_info_dup(state
->chosen_exit
);
3109 } else if (cur_len
== 0) { /* picking first node */
3110 routerinfo_t
*r
= choose_good_entry_server(purpose
, state
);
3112 info
= extend_info_from_router(r
);
3115 choose_good_middle_server(purpose
, state
, circ
->cpath
, cur_len
);
3117 info
= extend_info_from_router(r
);
3121 log_warn(LD_CIRC
,"Failed to find node for hop %d of our path. Discarding "
3122 "this circuit.", cur_len
);
3126 log_debug(LD_CIRC
,"Chose router %s for hop %d (exit is %s)",
3127 info
->nickname
, cur_len
+1, build_state_get_exit_nickname(state
));
3129 onion_append_hop(&circ
->cpath
, info
);
3130 extend_info_free(info
);
3134 /** Create a new hop, annotate it with information about its
3135 * corresponding router <b>choice</b>, and append it to the
3136 * end of the cpath <b>head_ptr</b>. */
3138 onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
)
3140 crypt_path_t
*hop
= tor_malloc_zero(sizeof(crypt_path_t
));
3142 /* link hop into the cpath, at the end. */
3143 onion_append_to_cpath(head_ptr
, hop
);
3145 hop
->magic
= CRYPT_PATH_MAGIC
;
3146 hop
->state
= CPATH_STATE_CLOSED
;
3148 hop
->extend_info
= extend_info_dup(choice
);
3150 hop
->package_window
= circuit_initial_package_window();
3151 hop
->deliver_window
= CIRCWINDOW_START
;
3156 /** Allocate a new extend_info object based on the various arguments. */
3158 extend_info_alloc(const char *nickname
, const char *digest
,
3159 crypto_pk_env_t
*onion_key
,
3160 const tor_addr_t
*addr
, uint16_t port
)
3162 extend_info_t
*info
= tor_malloc_zero(sizeof(extend_info_t
));
3163 memcpy(info
->identity_digest
, digest
, DIGEST_LEN
);
3165 strlcpy(info
->nickname
, nickname
, sizeof(info
->nickname
));
3167 info
->onion_key
= crypto_pk_dup_key(onion_key
);
3168 tor_addr_copy(&info
->addr
, addr
);
3173 /** Allocate and return a new extend_info_t that can be used to build a
3174 * circuit to or through the router <b>r</b>. */
3176 extend_info_from_router(routerinfo_t
*r
)
3180 tor_addr_from_ipv4h(&addr
, r
->addr
);
3181 return extend_info_alloc(r
->nickname
, r
->cache_info
.identity_digest
,
3182 r
->onion_pkey
, &addr
, r
->or_port
);
3185 /** Release storage held by an extend_info_t struct. */
3187 extend_info_free(extend_info_t
*info
)
3191 crypto_free_pk_env(info
->onion_key
);
3195 /** Allocate and return a new extend_info_t with the same contents as
3198 extend_info_dup(extend_info_t
*info
)
3200 extend_info_t
*newinfo
;
3202 newinfo
= tor_malloc(sizeof(extend_info_t
));
3203 memcpy(newinfo
, info
, sizeof(extend_info_t
));
3204 if (info
->onion_key
)
3205 newinfo
->onion_key
= crypto_pk_dup_key(info
->onion_key
);
3207 newinfo
->onion_key
= NULL
;
3211 /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
3212 * If there is no chosen exit, or if we don't know the routerinfo_t for
3213 * the chosen exit, return NULL.
3216 build_state_get_exit_router(cpath_build_state_t
*state
)
3218 if (!state
|| !state
->chosen_exit
)
3220 return router_get_by_digest(state
->chosen_exit
->identity_digest
);
3223 /** Return the nickname for the chosen exit router in <b>state</b>. If
3224 * there is no chosen exit, or if we don't know the routerinfo_t for the
3225 * chosen exit, return NULL.
3228 build_state_get_exit_nickname(cpath_build_state_t
*state
)
3230 if (!state
|| !state
->chosen_exit
)
3232 return state
->chosen_exit
->nickname
;
3235 /** Check whether the entry guard <b>e</b> is usable, given the directory
3236 * authorities' opinion about the router (stored in <b>ri</b>) and the user's
3237 * configuration (in <b>options</b>). Set <b>e</b>->bad_since
3238 * accordingly. Return true iff the entry guard's status changes.
3240 * If it's not usable, set *<b>reason</b> to a static string explaining why.
3242 /*XXXX take a routerstatus, not a routerinfo. */
3244 entry_guard_set_status(entry_guard_t
*e
, routerinfo_t
*ri
,
3245 time_t now
, or_options_t
*options
, const char **reason
)
3247 char buf
[HEX_DIGEST_LEN
+1];
3252 /* Do we want to mark this guard as bad? */
3254 *reason
= "unlisted";
3255 else if (!ri
->is_running
)
3257 else if (options
->UseBridges
&& ri
->purpose
!= ROUTER_PURPOSE_BRIDGE
)
3258 *reason
= "not a bridge";
3259 else if (!options
->UseBridges
&& !ri
->is_possible_guard
&&
3260 !routerset_contains_router(options
->EntryNodes
,ri
))
3261 *reason
= "not recommended as a guard";
3262 else if (routerset_contains_router(options
->ExcludeNodes
, ri
))
3263 *reason
= "excluded";
3265 if (*reason
&& ! e
->bad_since
) {
3266 /* Router is newly bad. */
3267 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
3268 log_info(LD_CIRC
, "Entry guard %s (%s) is %s: marking as unusable.",
3269 e
->nickname
, buf
, *reason
);
3272 control_event_guard(e
->nickname
, e
->identity
, "BAD");
3274 } else if (!*reason
&& e
->bad_since
) {
3275 /* There's nothing wrong with the router any more. */
3276 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
3277 log_info(LD_CIRC
, "Entry guard %s (%s) is no longer unusable: "
3278 "marking as ok.", e
->nickname
, buf
);
3281 control_event_guard(e
->nickname
, e
->identity
, "GOOD");
3287 /** Return true iff enough time has passed since we last tried to connect
3288 * to the unreachable guard <b>e</b> that we're willing to try again. */
3290 entry_is_time_to_retry(entry_guard_t
*e
, time_t now
)
3293 if (e
->last_attempted
< e
->unreachable_since
)
3295 diff
= now
- e
->unreachable_since
;
3297 return now
> (e
->last_attempted
+ 60*60);
3298 else if (diff
< 3*24*60*60)
3299 return now
> (e
->last_attempted
+ 4*60*60);
3300 else if (diff
< 7*24*60*60)
3301 return now
> (e
->last_attempted
+ 18*60*60);
3303 return now
> (e
->last_attempted
+ 36*60*60);
3306 /** Return the router corresponding to <b>e</b>, if <b>e</b> is
3307 * working well enough that we are willing to use it as an entry
3308 * right now. (Else return NULL.) In particular, it must be
3309 * - Listed as either up or never yet contacted;
3310 * - Present in the routerlist;
3311 * - Listed as 'stable' or 'fast' by the current dirserver consensus,
3312 * if demanded by <b>need_uptime</b> or <b>need_capacity</b>
3313 * (unless it's a configured EntryNode);
3314 * - Allowed by our current ReachableORAddresses config option; and
3315 * - Currently thought to be reachable by us (unless <b>assume_reachable</b>
3318 * If the answer is no, set *<b>msg</b> to an explanation of why.
3320 static INLINE routerinfo_t
*
3321 entry_is_live(entry_guard_t
*e
, int need_uptime
, int need_capacity
,
3322 int assume_reachable
, const char **msg
)
3325 or_options_t
*options
= get_options();
3332 /* no good if it's unreachable, unless assume_unreachable or can_retry. */
3333 if (!assume_reachable
&& !e
->can_retry
&&
3334 e
->unreachable_since
&& !entry_is_time_to_retry(e
, time(NULL
))) {
3335 *msg
= "unreachable";
3338 r
= router_get_by_digest(e
->identity
);
3340 *msg
= "no descriptor";
3343 if (get_options()->UseBridges
&& r
->purpose
!= ROUTER_PURPOSE_BRIDGE
) {
3344 *msg
= "not a bridge";
3347 if (!get_options()->UseBridges
&& r
->purpose
!= ROUTER_PURPOSE_GENERAL
) {
3348 *msg
= "not general-purpose";
3351 if (options
->EntryNodes
&&
3352 routerset_contains_router(options
->EntryNodes
, r
)) {
3353 /* they asked for it, they get it */
3354 need_uptime
= need_capacity
= 0;
3356 if (router_is_unreliable(r
, need_uptime
, need_capacity
, 0)) {
3357 *msg
= "not fast/stable";
3360 if (!fascist_firewall_allows_or(r
)) {
3361 *msg
= "unreachable by config";
3367 /** Return the number of entry guards that we think are usable. */
3369 num_live_entry_guards(void)
3375 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
3377 if (entry_is_live(entry
, 0, 1, 0, &msg
))
3383 /** If <b>digest</b> matches the identity of any node in the
3384 * entry_guards list, return that node. Else return NULL. */
3385 static INLINE entry_guard_t
*
3386 is_an_entry_guard(const char *digest
)
3388 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
3389 if (!memcmp(digest
, entry
->identity
, DIGEST_LEN
))
3395 /** Dump a description of our list of entry guards to the log at level
3396 * <b>severity</b>. */
3398 log_entry_guards(int severity
)
3400 smartlist_t
*elements
= smartlist_create();
3403 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
3405 const char *msg
= NULL
;
3407 if (entry_is_live(e
, 0, 1, 0, &msg
))
3408 tor_asprintf(&cp
, "%s (up %s)",
3410 e
->made_contact
? "made-contact" : "never-contacted");
3412 tor_asprintf(&cp
, "%s (%s, %s)",
3414 e
->made_contact
? "made-contact" : "never-contacted");
3415 smartlist_add(elements
, cp
);
3418 s
= smartlist_join_strings(elements
, ",", 0, NULL
);
3419 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
3420 smartlist_free(elements
);
3421 log_fn(severity
,LD_CIRC
,"%s",s
);
3425 /** Called when one or more guards that we would previously have used for some
3426 * purpose are no longer in use because a higher-priority guard has become
3429 control_event_guard_deferred(void)
3431 /* XXXX We don't actually have a good way to figure out _how many_ entries
3432 * are live for some purpose. We need an entry_is_even_slightly_live()
3433 * function for this to work right. NumEntryGuards isn't reliable: if we
3434 * need guards with weird properties, we can have more than that number
3440 or_options_t
*options
= get_options();
3443 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
3445 if (entry_is_live(entry
, 0, 1, 0, &msg
)) {
3446 if (n
++ == options
->NumEntryGuards
) {
3447 control_event_guard(entry
->nickname
, entry
->identity
, "DEFERRED");
3455 /** Add a new (preferably stable and fast) router to our
3456 * entry_guards list. Return a pointer to the router if we succeed,
3457 * or NULL if we can't find any more suitable entries.
3459 * If <b>chosen</b> is defined, use that one, and if it's not
3460 * already in our entry_guards list, put it at the *beginning*.
3461 * Else, put the one we pick at the end of the list. */
3462 static routerinfo_t
*
3463 add_an_entry_guard(routerinfo_t
*chosen
, int reset_status
)
3465 routerinfo_t
*router
;
3466 entry_guard_t
*entry
;
3470 entry
= is_an_entry_guard(router
->cache_info
.identity_digest
);
3473 entry
->bad_since
= 0;
3474 entry
->can_retry
= 1;
3479 router
= choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL
, NULL
);
3483 entry
= tor_malloc_zero(sizeof(entry_guard_t
));
3484 log_info(LD_CIRC
, "Chose '%s' as new entry guard.", router
->nickname
);
3485 strlcpy(entry
->nickname
, router
->nickname
, sizeof(entry
->nickname
));
3486 memcpy(entry
->identity
, router
->cache_info
.identity_digest
, DIGEST_LEN
);
3487 /* Choose expiry time smudged over the past month. The goal here
3488 * is to a) spread out when Tor clients rotate their guards, so they
3489 * don't all select them on the same day, and b) avoid leaving a
3490 * precise timestamp in the state file about when we first picked
3491 * this guard. For details, see the Jan 2010 or-dev thread. */
3492 entry
->chosen_on_date
= time(NULL
) - crypto_rand_int(3600*24*30);
3493 entry
->chosen_by_version
= tor_strdup(VERSION
);
3494 if (chosen
) /* prepend */
3495 smartlist_insert(entry_guards
, 0, entry
);
3497 smartlist_add(entry_guards
, entry
);
3498 control_event_guard(entry
->nickname
, entry
->identity
, "NEW");
3499 control_event_guard_deferred();
3500 log_entry_guards(LOG_INFO
);
3504 /** If the use of entry guards is configured, choose more entry guards
3505 * until we have enough in the list. */
3507 pick_entry_guards(or_options_t
*options
)
3511 tor_assert(entry_guards
);
3513 while (num_live_entry_guards() < options
->NumEntryGuards
) {
3514 if (!add_an_entry_guard(NULL
, 0))
3519 entry_guards_changed();
3522 /** How long (in seconds) do we allow an entry guard to be nonfunctional,
3523 * unlisted, excluded, or otherwise nonusable before we give up on it? */
3524 #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
3526 /** Release all storage held by <b>e</b>. */
3528 entry_guard_free(entry_guard_t
*e
)
3532 tor_free(e
->chosen_by_version
);
3536 /** Remove any entry guard which was selected by an unknown version of Tor,
3537 * or which was selected by a version of Tor that's known to select
3538 * entry guards badly. */
3540 remove_obsolete_entry_guards(time_t now
)
3544 for (i
= 0; i
< smartlist_len(entry_guards
); ++i
) {
3545 entry_guard_t
*entry
= smartlist_get(entry_guards
, i
);
3546 const char *ver
= entry
->chosen_by_version
;
3547 const char *msg
= NULL
;
3549 int version_is_bad
= 0, date_is_bad
= 0;
3551 msg
= "does not say what version of Tor it was selected by";
3553 } else if (tor_version_parse(ver
, &v
)) {
3554 msg
= "does not seem to be from any recognized version of Tor";
3557 size_t len
= strlen(ver
)+5;
3558 char *tor_ver
= tor_malloc(len
);
3559 tor_snprintf(tor_ver
, len
, "Tor %s", ver
);
3560 if ((tor_version_as_new_as(tor_ver
, "0.1.0.10-alpha") &&
3561 !tor_version_as_new_as(tor_ver
, "0.1.2.16-dev")) ||
3562 (tor_version_as_new_as(tor_ver
, "0.2.0.0-alpha") &&
3563 !tor_version_as_new_as(tor_ver
, "0.2.0.6-alpha")) ||
3564 /* above are bug 440; below are bug 1217 */
3565 (tor_version_as_new_as(tor_ver
, "0.2.1.3-alpha") &&
3566 !tor_version_as_new_as(tor_ver
, "0.2.1.23")) ||
3567 (tor_version_as_new_as(tor_ver
, "0.2.2.0-alpha") &&
3568 !tor_version_as_new_as(tor_ver
, "0.2.2.7-alpha"))) {
3569 msg
= "was selected without regard for guard bandwidth";
3574 if (!version_is_bad
&& entry
->chosen_on_date
+ 3600*24*60 < now
) {
3575 /* It's been 2 months since the date listed in our state file. */
3576 msg
= "was selected several months ago";
3580 if (version_is_bad
|| date_is_bad
) { /* we need to drop it */
3581 char dbuf
[HEX_DIGEST_LEN
+1];
3583 base16_encode(dbuf
, sizeof(dbuf
), entry
->identity
, DIGEST_LEN
);
3584 log_fn(version_is_bad
? LOG_NOTICE
: LOG_INFO
, LD_CIRC
,
3585 "Entry guard '%s' (%s) %s. (Version=%s.) Replacing it.",
3586 entry
->nickname
, dbuf
, msg
, ver
?escaped(ver
):"none");
3587 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
3588 entry_guard_free(entry
);
3589 smartlist_del_keeporder(entry_guards
, i
--);
3590 log_entry_guards(LOG_INFO
);
3595 return changed
? 1 : 0;
3598 /** Remove all entry guards that have been down or unlisted for so
3599 * long that we don't think they'll come up again. Return 1 if we
3600 * removed any, or 0 if we did nothing. */
3602 remove_dead_entry_guards(time_t now
)
3604 char dbuf
[HEX_DIGEST_LEN
+1];
3605 char tbuf
[ISO_TIME_LEN
+1];
3609 for (i
= 0; i
< smartlist_len(entry_guards
); ) {
3610 entry_guard_t
*entry
= smartlist_get(entry_guards
, i
);
3611 if (entry
->bad_since
&&
3612 entry
->bad_since
+ ENTRY_GUARD_REMOVE_AFTER
< now
) {
3614 base16_encode(dbuf
, sizeof(dbuf
), entry
->identity
, DIGEST_LEN
);
3615 format_local_iso_time(tbuf
, entry
->bad_since
);
3616 log_info(LD_CIRC
, "Entry guard '%s' (%s) has been down or unlisted "
3617 "since %s local time; removing.",
3618 entry
->nickname
, dbuf
, tbuf
);
3619 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
3620 entry_guard_free(entry
);
3621 smartlist_del_keeporder(entry_guards
, i
);
3622 log_entry_guards(LOG_INFO
);
3627 return changed
? 1 : 0;
3630 /** A new directory or router-status has arrived; update the down/listed
3631 * status of the entry guards.
3633 * An entry is 'down' if the directory lists it as nonrunning.
3634 * An entry is 'unlisted' if the directory doesn't include it.
3636 * Don't call this on startup; only on a fresh download. Otherwise we'll
3637 * think that things are unlisted.
3640 entry_guards_compute_status(or_options_t
*options
, time_t now
)
3643 int severity
= LOG_DEBUG
;
3644 digestmap_t
*reasons
;
3649 if (options
->EntryNodes
) /* reshuffle the entry guard list if needed */
3650 entry_nodes_should_be_added();
3652 reasons
= digestmap_new();
3653 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, entry
)
3655 routerinfo_t
*r
= router_get_by_digest(entry
->identity
);
3656 const char *reason
= NULL
;
3657 if (entry_guard_set_status(entry
, r
, now
, options
, &reason
))
3660 if (entry
->bad_since
)
3663 digestmap_set(reasons
, entry
->identity
, (char*)reason
);
3665 SMARTLIST_FOREACH_END(entry
);
3667 if (remove_dead_entry_guards(now
))
3670 severity
= changed
? LOG_DEBUG
: LOG_INFO
;
3673 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, entry
) {
3674 const char *reason
= digestmap_get(reasons
, entry
->identity
);
3675 const char *live_msg
= "";
3676 routerinfo_t
*r
= entry_is_live(entry
, 0, 1, 0, &live_msg
);
3677 log_info(LD_CIRC
, "Summary: Entry '%s' is %s, %s%s%s, and %s%s.",
3679 entry
->unreachable_since
? "unreachable" : "reachable",
3680 entry
->bad_since
? "unusable" : "usable",
3682 reason
? reason
: "",
3683 r
? "live" : "not live / ",
3685 } SMARTLIST_FOREACH_END(entry
);
3686 log_info(LD_CIRC
, " (%d/%d entry guards are usable/new)",
3687 num_live_entry_guards(), smartlist_len(entry_guards
));
3688 log_entry_guards(LOG_INFO
);
3689 entry_guards_changed();
3692 digestmap_free(reasons
, NULL
);
3695 /** Called when a connection to an OR with the identity digest <b>digest</b>
3696 * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0).
3697 * If the OR is an entry, change that entry's up/down status.
3698 * Return 0 normally, or -1 if we want to tear down the new connection.
3700 * If <b>mark_relay_status</b>, also call router_set_status() on this
3703 * XXX022 change succeeded and mark_relay_status into 'int flags'.
3706 entry_guard_register_connect_status(const char *digest
, int succeeded
,
3707 int mark_relay_status
, time_t now
)
3710 int refuse_conn
= 0;
3711 int first_contact
= 0;
3712 entry_guard_t
*entry
= NULL
;
3714 char buf
[HEX_DIGEST_LEN
+1];
3719 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
3721 if (!memcmp(e
->identity
, digest
, DIGEST_LEN
)) {
3731 base16_encode(buf
, sizeof(buf
), entry
->identity
, DIGEST_LEN
);
3734 if (entry
->unreachable_since
) {
3735 log_info(LD_CIRC
, "Entry guard '%s' (%s) is now reachable again. Good.",
3736 entry
->nickname
, buf
);
3737 entry
->can_retry
= 0;
3738 entry
->unreachable_since
= 0;
3739 entry
->last_attempted
= now
;
3740 control_event_guard(entry
->nickname
, entry
->identity
, "UP");
3743 if (!entry
->made_contact
) {
3744 entry
->made_contact
= 1;
3745 first_contact
= changed
= 1;
3747 } else { /* ! succeeded */
3748 if (!entry
->made_contact
) {
3749 /* We've never connected to this one. */
3751 "Connection to never-contacted entry guard '%s' (%s) failed. "
3752 "Removing from the list. %d/%d entry guards usable/new.",
3753 entry
->nickname
, buf
,
3754 num_live_entry_guards()-1, smartlist_len(entry_guards
)-1);
3755 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
3756 entry_guard_free(entry
);
3757 smartlist_del_keeporder(entry_guards
, idx
);
3758 log_entry_guards(LOG_INFO
);
3760 } else if (!entry
->unreachable_since
) {
3761 log_info(LD_CIRC
, "Unable to connect to entry guard '%s' (%s). "
3762 "Marking as unreachable.", entry
->nickname
, buf
);
3763 entry
->unreachable_since
= entry
->last_attempted
= now
;
3764 control_event_guard(entry
->nickname
, entry
->identity
, "DOWN");
3766 entry
->can_retry
= 0; /* We gave it an early chance; no good. */
3768 char tbuf
[ISO_TIME_LEN
+1];
3769 format_iso_time(tbuf
, entry
->unreachable_since
);
3770 log_debug(LD_CIRC
, "Failed to connect to unreachable entry guard "
3771 "'%s' (%s). It has been unreachable since %s.",
3772 entry
->nickname
, buf
, tbuf
);
3773 entry
->last_attempted
= now
;
3774 entry
->can_retry
= 0; /* We gave it an early chance; no good. */
3778 /* if the caller asked us to, also update the is_running flags for this
3780 if (mark_relay_status
)
3781 router_set_status(digest
, succeeded
);
3783 if (first_contact
) {
3784 /* We've just added a new long-term entry guard. Perhaps the network just
3785 * came back? We should give our earlier entries another try too,
3786 * and close this connection so we don't use it before we've given
3787 * the others a shot. */
3788 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, {
3791 if (e
->made_contact
) {
3793 routerinfo_t
*r
= entry_is_live(e
, 0, 1, 1, &msg
);
3794 if (r
&& e
->unreachable_since
) {
3802 "Connected to new entry guard '%s' (%s). Marking earlier "
3803 "entry guards up. %d/%d entry guards usable/new.",
3804 entry
->nickname
, buf
,
3805 num_live_entry_guards(), smartlist_len(entry_guards
));
3806 log_entry_guards(LOG_INFO
);
3812 entry_guards_changed();
3813 return refuse_conn
? -1 : 0;
3816 /** When we try to choose an entry guard, should we parse and add
3817 * config's EntryNodes first? */
3818 static int should_add_entry_nodes
= 0;
3820 /** Called when the value of EntryNodes changes in our configuration. */
3822 entry_nodes_should_be_added(void)
3824 log_info(LD_CIRC
, "EntryNodes config option set. Putting configured "
3825 "relays at the front of the entry guard list.");
3826 should_add_entry_nodes
= 1;
3829 /** Add all nodes in EntryNodes that aren't currently guard nodes to the list
3830 * of guard nodes, at the front. */
3832 entry_guards_prepend_from_config(or_options_t
*options
)
3834 smartlist_t
*entry_routers
, *entry_fps
;
3835 smartlist_t
*old_entry_guards_on_list
, *old_entry_guards_not_on_list
;
3836 tor_assert(entry_guards
);
3838 should_add_entry_nodes
= 0;
3840 if (!options
->EntryNodes
) {
3841 /* It's possible that a controller set EntryNodes, thus making
3842 * should_add_entry_nodes set, then cleared it again, all before the
3843 * call to choose_random_entry() that triggered us. If so, just return.
3849 char *string
= routerset_to_string(options
->EntryNodes
);
3850 log_info(LD_CIRC
,"Adding configured EntryNodes '%s'.", string
);
3854 entry_routers
= smartlist_create();
3855 entry_fps
= smartlist_create();
3856 old_entry_guards_on_list
= smartlist_create();
3857 old_entry_guards_not_on_list
= smartlist_create();
3859 /* Split entry guards into those on the list and those not. */
3861 /* XXXX022 Now that we allow countries and IP ranges in EntryNodes, this is
3862 * potentially an enormous list. For now, we disable such values for
3863 * EntryNodes in options_validate(); really, this wants a better solution.
3864 * Perhaps we should do this calculation once whenever the list of routers
3865 * changes or the entrynodes setting changes.
3867 routerset_get_all_routers(entry_routers
, options
->EntryNodes
, 0);
3868 SMARTLIST_FOREACH(entry_routers
, routerinfo_t
*, ri
,
3869 smartlist_add(entry_fps
,ri
->cache_info
.identity_digest
));
3870 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, {
3871 if (smartlist_digest_isin(entry_fps
, e
->identity
))
3872 smartlist_add(old_entry_guards_on_list
, e
);
3874 smartlist_add(old_entry_guards_not_on_list
, e
);
3877 /* Remove all currently configured entry guards from entry_routers. */
3878 SMARTLIST_FOREACH(entry_routers
, routerinfo_t
*, ri
, {
3879 if (is_an_entry_guard(ri
->cache_info
.identity_digest
)) {
3880 SMARTLIST_DEL_CURRENT(entry_routers
, ri
);
3884 /* Now build the new entry_guards list. */
3885 smartlist_clear(entry_guards
);
3886 /* First, the previously configured guards that are in EntryNodes. */
3887 smartlist_add_all(entry_guards
, old_entry_guards_on_list
);
3888 /* Next, the rest of EntryNodes */
3889 SMARTLIST_FOREACH(entry_routers
, routerinfo_t
*, ri
, {
3890 add_an_entry_guard(ri
, 0);
3892 /* Finally, the remaining previously configured guards that are not in
3893 * EntryNodes, unless we're strict in which case we drop them */
3894 if (options
->StrictNodes
) {
3895 SMARTLIST_FOREACH(old_entry_guards_not_on_list
, entry_guard_t
*, e
,
3896 entry_guard_free(e
));
3898 smartlist_add_all(entry_guards
, old_entry_guards_not_on_list
);
3901 smartlist_free(entry_routers
);
3902 smartlist_free(entry_fps
);
3903 smartlist_free(old_entry_guards_on_list
);
3904 smartlist_free(old_entry_guards_not_on_list
);
3905 entry_guards_changed();
3908 /** Return 0 if we're fine adding arbitrary routers out of the
3909 * directory to our entry guard list, or return 1 if we have a
3910 * list already and we'd prefer to stick to it.
3913 entry_list_is_constrained(or_options_t
*options
)
3915 if (options
->EntryNodes
)
3917 if (options
->UseBridges
)
3922 /* Are we dead set against changing our entry guard list, or would we
3923 * change it if it means keeping Tor usable? */
3925 entry_list_is_totally_static(or_options_t
*options
)
3927 if (options
->EntryNodes
&& options
->StrictNodes
)
3929 if (options
->UseBridges
)
3934 /** Pick a live (up and listed) entry guard from entry_guards. If
3935 * <b>state</b> is non-NULL, this is for a specific circuit --
3936 * make sure not to pick this circuit's exit or any node in the
3937 * exit's family. If <b>state</b> is NULL, we're looking for a random
3938 * guard (likely a bridge). */
3940 choose_random_entry(cpath_build_state_t
*state
)
3942 or_options_t
*options
= get_options();
3943 smartlist_t
*live_entry_guards
= smartlist_create();
3944 smartlist_t
*exit_family
= smartlist_create();
3945 routerinfo_t
*chosen_exit
= state
?build_state_get_exit_router(state
) : NULL
;
3946 routerinfo_t
*r
= NULL
;
3947 int need_uptime
= state
? state
->need_uptime
: 0;
3948 int need_capacity
= state
? state
->need_capacity
: 0;
3949 int preferred_min
, consider_exit_family
= 0;
3952 smartlist_add(exit_family
, chosen_exit
);
3953 routerlist_add_family(exit_family
, chosen_exit
);
3954 consider_exit_family
= 1;
3958 entry_guards
= smartlist_create();
3960 if (should_add_entry_nodes
)
3961 entry_guards_prepend_from_config(options
);
3963 if (!entry_list_is_constrained(options
) &&
3964 smartlist_len(entry_guards
) < options
->NumEntryGuards
)
3965 pick_entry_guards(options
);
3968 smartlist_clear(live_entry_guards
);
3969 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
3972 r
= entry_is_live(entry
, need_uptime
, need_capacity
, 0, &msg
);
3974 continue; /* down, no point */
3975 if (consider_exit_family
&& smartlist_isin(exit_family
, r
))
3976 continue; /* avoid relays that are family members of our exit */
3977 if (options
->EntryNodes
&&
3978 !routerset_contains_router(options
->EntryNodes
, r
)) {
3979 /* We've come to the end of our preferred entry nodes. */
3980 if (smartlist_len(live_entry_guards
))
3981 goto choose_and_finish
; /* only choose from the ones we like */
3982 if (options
->StrictNodes
) {
3983 /* in theory this case should never happen, since
3984 * entry_guards_prepend_from_config() drops unwanted relays */
3985 tor_fragile_assert();
3988 "No relays from EntryNodes available. Using others.");
3991 smartlist_add(live_entry_guards
, r
);
3992 if (!entry
->made_contact
) {
3993 /* Always start with the first not-yet-contacted entry
3994 * guard. Otherwise we might add several new ones, pick
3995 * the second new one, and now we've expanded our entry
3996 * guard list without needing to. */
3997 goto choose_and_finish
;
3999 if (smartlist_len(live_entry_guards
) >= options
->NumEntryGuards
)
4000 break; /* we have enough */
4003 if (entry_list_is_constrained(options
)) {
4004 /* If we prefer the entry nodes we've got, and we have at least
4005 * one choice, that's great. Use it. */
4008 /* Try to have at least 2 choices available. This way we don't
4009 * get stuck with a single live-but-crummy entry and just keep
4011 * (We might get 2 live-but-crummy entry guards, but so be it.) */
4015 if (smartlist_len(live_entry_guards
) < preferred_min
) {
4016 if (!entry_list_is_totally_static(options
)) {
4017 /* still no? try adding a new entry then */
4018 /* XXX if guard doesn't imply fast and stable, then we need
4019 * to tell add_an_entry_guard below what we want, or it might
4020 * be a long time til we get it. -RD */
4021 r
= add_an_entry_guard(NULL
, 0);
4023 entry_guards_changed();
4024 /* XXX we start over here in case the new node we added shares
4025 * a family with our exit node. There's a chance that we'll just
4026 * load up on entry guards here, if the network we're using is
4027 * one big family. Perhaps we should teach add_an_entry_guard()
4028 * to understand nodes-to-avoid-if-possible? -RD */
4032 if (!r
&& need_uptime
) {
4033 need_uptime
= 0; /* try without that requirement */
4036 if (!r
&& need_capacity
) {
4037 /* still no? last attempt, try without requiring capacity */
4041 if (!r
&& entry_list_is_constrained(options
) && consider_exit_family
) {
4042 /* still no? if we're using bridges or have strictentrynodes
4043 * set, and our chosen exit is in the same family as all our
4044 * bridges/entry guards, then be flexible about families. */
4045 consider_exit_family
= 0;
4048 /* live_entry_guards may be empty below. Oh well, we tried. */
4052 if (entry_list_is_constrained(options
)) {
4053 /* We need to weight by bandwidth, because our bridges or entryguards
4054 * were not already selected proportional to their bandwidth. */
4055 r
= routerlist_sl_choose_by_bandwidth(live_entry_guards
, WEIGHT_FOR_GUARD
);
4057 /* We choose uniformly at random here, because choose_good_entry_server()
4058 * already weights its choices by bandwidth, so we don't want to
4059 * *double*-weight our guard selection. */
4060 r
= smartlist_choose(live_entry_guards
);
4062 smartlist_free(live_entry_guards
);
4063 smartlist_free(exit_family
);
4067 /** Parse <b>state</b> and learn about the entry guards it describes.
4068 * If <b>set</b> is true, and there are no errors, replace the global
4069 * entry_list with what we find.
4070 * On success, return 0. On failure, alloc into *<b>msg</b> a string
4071 * describing the error, and return -1.
4074 entry_guards_parse_state(or_state_t
*state
, int set
, char **msg
)
4076 entry_guard_t
*node
= NULL
;
4077 smartlist_t
*new_entry_guards
= smartlist_create();
4078 config_line_t
*line
;
4079 time_t now
= time(NULL
);
4080 const char *state_version
= state
->TorVersion
;
4081 digestmap_t
*added_by
= digestmap_new();
4084 for (line
= state
->EntryGuards
; line
; line
= line
->next
) {
4085 if (!strcasecmp(line
->key
, "EntryGuard")) {
4086 smartlist_t
*args
= smartlist_create();
4087 node
= tor_malloc_zero(sizeof(entry_guard_t
));
4088 /* all entry guards on disk have been contacted */
4089 node
->made_contact
= 1;
4090 smartlist_add(new_entry_guards
, node
);
4091 smartlist_split_string(args
, line
->value
, " ",
4092 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
4093 if (smartlist_len(args
)<2) {
4094 *msg
= tor_strdup("Unable to parse entry nodes: "
4095 "Too few arguments to EntryGuard");
4096 } else if (!is_legal_nickname(smartlist_get(args
,0))) {
4097 *msg
= tor_strdup("Unable to parse entry nodes: "
4098 "Bad nickname for EntryGuard");
4100 strlcpy(node
->nickname
, smartlist_get(args
,0), MAX_NICKNAME_LEN
+1);
4101 if (base16_decode(node
->identity
, DIGEST_LEN
, smartlist_get(args
,1),
4102 strlen(smartlist_get(args
,1)))<0) {
4103 *msg
= tor_strdup("Unable to parse entry nodes: "
4104 "Bad hex digest for EntryGuard");
4107 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
4108 smartlist_free(args
);
4111 } else if (!strcasecmp(line
->key
, "EntryGuardDownSince") ||
4112 !strcasecmp(line
->key
, "EntryGuardUnlistedSince")) {
4114 time_t last_try
= 0;
4116 *msg
= tor_strdup("Unable to parse entry nodes: "
4117 "EntryGuardDownSince/UnlistedSince without EntryGuard");
4120 if (parse_iso_time(line
->value
, &when
)<0) {
4121 *msg
= tor_strdup("Unable to parse entry nodes: "
4122 "Bad time in EntryGuardDownSince/UnlistedSince");
4126 /* It's a bad idea to believe info in the future: you can wind
4127 * up with timeouts that aren't allowed to happen for years. */
4130 if (strlen(line
->value
) >= ISO_TIME_LEN
+ISO_TIME_LEN
+1) {
4131 /* ignore failure */
4132 (void) parse_iso_time(line
->value
+ISO_TIME_LEN
+1, &last_try
);
4134 if (!strcasecmp(line
->key
, "EntryGuardDownSince")) {
4135 node
->unreachable_since
= when
;
4136 node
->last_attempted
= last_try
;
4138 node
->bad_since
= when
;
4140 } else if (!strcasecmp(line
->key
, "EntryGuardAddedBy")) {
4142 /* format is digest version date */
4143 if (strlen(line
->value
) < HEX_DIGEST_LEN
+1+1+1+ISO_TIME_LEN
) {
4144 log_warn(LD_BUG
, "EntryGuardAddedBy line is not long enough.");
4147 if (base16_decode(d
, sizeof(d
), line
->value
, HEX_DIGEST_LEN
)<0 ||
4148 line
->value
[HEX_DIGEST_LEN
] != ' ') {
4149 log_warn(LD_BUG
, "EntryGuardAddedBy line %s does not begin with "
4150 "hex digest", escaped(line
->value
));
4153 digestmap_set(added_by
, d
, tor_strdup(line
->value
+HEX_DIGEST_LEN
+1));
4155 log_warn(LD_BUG
, "Unexpected key %s", line
->key
);
4159 SMARTLIST_FOREACH(new_entry_guards
, entry_guard_t
*, e
,
4162 char *val
= digestmap_get(added_by
, e
->identity
);
4163 if (val
&& (sp
= strchr(val
, ' '))) {
4166 if (parse_iso_time(sp
, &when
)<0) {
4167 log_warn(LD_BUG
, "Can't read time %s in EntryGuardAddedBy", sp
);
4169 e
->chosen_by_version
= tor_strdup(val
);
4170 e
->chosen_on_date
= when
;
4173 if (state_version
) {
4174 e
->chosen_by_version
= tor_strdup(state_version
);
4175 e
->chosen_on_date
= time(NULL
) - crypto_rand_int(3600*24*30);
4181 SMARTLIST_FOREACH(new_entry_guards
, entry_guard_t
*, e
,
4182 entry_guard_free(e
));
4183 smartlist_free(new_entry_guards
);
4184 } else { /* !err && set */
4186 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
4187 entry_guard_free(e
));
4188 smartlist_free(entry_guards
);
4190 entry_guards
= new_entry_guards
;
4191 entry_guards_dirty
= 0;
4192 /* XXX022 hand new_entry_guards to this func, and move it up a
4193 * few lines, so we don't have to re-dirty it */
4194 if (remove_obsolete_entry_guards(now
))
4195 entry_guards_dirty
= 1;
4197 digestmap_free(added_by
, _tor_free
);
4198 return *msg
? -1 : 0;
4201 /** Our list of entry guards has changed, or some element of one
4202 * of our entry guards has changed. Write the changes to disk within
4203 * the next few minutes.
4206 entry_guards_changed(void)
4209 entry_guards_dirty
= 1;
4211 /* or_state_save() will call entry_guards_update_state(). */
4212 when
= get_options()->AvoidDiskWrites
? time(NULL
) + 3600 : time(NULL
)+600;
4213 or_state_mark_dirty(get_or_state(), when
);
4216 /** If the entry guard info has not changed, do nothing and return.
4217 * Otherwise, free the EntryGuards piece of <b>state</b> and create
4218 * a new one out of the global entry_guards list, and then mark
4219 * <b>state</b> dirty so it will get saved to disk.
4222 entry_guards_update_state(or_state_t
*state
)
4224 config_line_t
**next
, *line
;
4225 if (! entry_guards_dirty
)
4228 config_free_lines(state
->EntryGuards
);
4229 next
= &state
->EntryGuards
;
4232 entry_guards
= smartlist_create();
4233 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
4235 char dbuf
[HEX_DIGEST_LEN
+1];
4236 if (!e
->made_contact
)
4237 continue; /* don't write this one to disk */
4238 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
4239 line
->key
= tor_strdup("EntryGuard");
4240 line
->value
= tor_malloc(HEX_DIGEST_LEN
+MAX_NICKNAME_LEN
+2);
4241 base16_encode(dbuf
, sizeof(dbuf
), e
->identity
, DIGEST_LEN
);
4242 tor_snprintf(line
->value
,HEX_DIGEST_LEN
+MAX_NICKNAME_LEN
+2,
4243 "%s %s", e
->nickname
, dbuf
);
4244 next
= &(line
->next
);
4245 if (e
->unreachable_since
) {
4246 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
4247 line
->key
= tor_strdup("EntryGuardDownSince");
4248 line
->value
= tor_malloc(ISO_TIME_LEN
+1+ISO_TIME_LEN
+1);
4249 format_iso_time(line
->value
, e
->unreachable_since
);
4250 if (e
->last_attempted
) {
4251 line
->value
[ISO_TIME_LEN
] = ' ';
4252 format_iso_time(line
->value
+ISO_TIME_LEN
+1, e
->last_attempted
);
4254 next
= &(line
->next
);
4257 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
4258 line
->key
= tor_strdup("EntryGuardUnlistedSince");
4259 line
->value
= tor_malloc(ISO_TIME_LEN
+1);
4260 format_iso_time(line
->value
, e
->bad_since
);
4261 next
= &(line
->next
);
4263 if (e
->chosen_on_date
&& e
->chosen_by_version
&&
4264 !strchr(e
->chosen_by_version
, ' ')) {
4265 char d
[HEX_DIGEST_LEN
+1];
4266 char t
[ISO_TIME_LEN
+1];
4268 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
4269 line
->key
= tor_strdup("EntryGuardAddedBy");
4270 val_len
= (HEX_DIGEST_LEN
+1+strlen(e
->chosen_by_version
)
4272 line
->value
= tor_malloc(val_len
);
4273 base16_encode(d
, sizeof(d
), e
->identity
, DIGEST_LEN
);
4274 format_iso_time(t
, e
->chosen_on_date
);
4275 tor_snprintf(line
->value
, val_len
, "%s %s %s",
4276 d
, e
->chosen_by_version
, t
);
4277 next
= &(line
->next
);
4280 if (!get_options()->AvoidDiskWrites
)
4281 or_state_mark_dirty(get_or_state(), 0);
4282 entry_guards_dirty
= 0;
4285 /** If <b>question</b> is the string "entry-guards", then dump
4286 * to *<b>answer</b> a newly allocated string describing all of
4287 * the nodes in the global entry_guards list. See control-spec.txt
4289 * For backward compatibility, we also handle the string "helper-nodes".
4292 getinfo_helper_entry_guards(control_connection_t
*conn
,
4293 const char *question
, char **answer
,
4294 const char **errmsg
)
4299 if (!strcmp(question
,"entry-guards") ||
4300 !strcmp(question
,"helper-nodes")) {
4301 smartlist_t
*sl
= smartlist_create();
4302 char tbuf
[ISO_TIME_LEN
+1];
4303 char nbuf
[MAX_VERBOSE_NICKNAME_LEN
+1];
4305 entry_guards
= smartlist_create();
4306 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, e
) {
4307 size_t len
= MAX_VERBOSE_NICKNAME_LEN
+ISO_TIME_LEN
+32;
4308 char *c
= tor_malloc(len
);
4309 const char *status
= NULL
;
4313 if (!e
->made_contact
) {
4314 status
= "never-connected";
4315 } else if (e
->bad_since
) {
4316 when
= e
->bad_since
;
4317 status
= "unusable";
4322 ri
= router_get_by_digest(e
->identity
);
4324 router_get_verbose_nickname(nbuf
, ri
);
4327 base16_encode(nbuf
+1, sizeof(nbuf
)-1, e
->identity
, DIGEST_LEN
);
4328 /* e->nickname field is not very reliable if we don't know about
4329 * this router any longer; don't include it. */
4333 format_iso_time(tbuf
, when
);
4334 tor_snprintf(c
, len
, "%s %s %s\n", nbuf
, status
, tbuf
);
4336 tor_snprintf(c
, len
, "%s %s\n", nbuf
, status
);
4338 smartlist_add(sl
, c
);
4339 } SMARTLIST_FOREACH_END(e
);
4340 *answer
= smartlist_join_strings(sl
, "", 0, NULL
);
4341 SMARTLIST_FOREACH(sl
, char *, c
, tor_free(c
));
4347 /** Information about a configured bridge. Currently this just matches the
4348 * ones in the torrc file, but one day we may be able to learn about new
4349 * bridges on our own, and remember them in the state file. */
4351 /** Address of the bridge. */
4353 /** TLS port for the bridge. */
4355 /** Expected identity digest, or all zero bytes if we don't know what the
4356 * digest should be. */
4357 char identity
[DIGEST_LEN
];
4358 /** When should we next try to fetch a descriptor for this bridge? */
4359 download_status_t fetch_status
;
4362 /** A list of configured bridges. Whenever we actually get a descriptor
4363 * for one, we add it as an entry guard. */
4364 static smartlist_t
*bridge_list
= NULL
;
4366 /** Initialize the bridge list to empty, creating it if needed. */
4368 clear_bridge_list(void)
4371 bridge_list
= smartlist_create();
4372 SMARTLIST_FOREACH(bridge_list
, bridge_info_t
*, b
, tor_free(b
));
4373 smartlist_clear(bridge_list
);
4376 /** Return a bridge pointer if <b>ri</b> is one of our known bridges
4377 * (either by comparing keys if possible, else by comparing addr/port).
4378 * Else return NULL. */
4379 static bridge_info_t
*
4380 get_configured_bridge_by_addr_port_digest(tor_addr_t
*addr
, uint16_t port
,
4385 SMARTLIST_FOREACH_BEGIN(bridge_list
, bridge_info_t
*, bridge
)
4387 if (tor_digest_is_zero(bridge
->identity
) &&
4388 !tor_addr_compare(&bridge
->addr
, addr
, CMP_EXACT
) &&
4389 bridge
->port
== port
)
4391 if (!memcmp(bridge
->identity
, digest
, DIGEST_LEN
))
4394 SMARTLIST_FOREACH_END(bridge
);
4398 /** Wrapper around get_configured_bridge_by_addr_port_digest() to look
4399 * it up via router descriptor <b>ri</b>. */
4400 static bridge_info_t
*
4401 get_configured_bridge_by_routerinfo(routerinfo_t
*ri
)
4404 tor_addr_from_ipv4h(&addr
, ri
->addr
);
4405 return get_configured_bridge_by_addr_port_digest(&addr
,
4406 ri
->or_port
, ri
->cache_info
.identity_digest
);
4409 /** Return 1 if <b>ri</b> is one of our known bridges, else 0. */
4411 routerinfo_is_a_configured_bridge(routerinfo_t
*ri
)
4413 return get_configured_bridge_by_routerinfo(ri
) ? 1 : 0;
4416 /** We made a connection to a router at <b>addr</b>:<b>port</b>
4417 * without knowing its digest. Its digest turned out to be <b>digest</b>.
4418 * If it was a bridge, and we still don't know its digest, record it.
4421 learned_router_identity(tor_addr_t
*addr
, uint16_t port
, const char *digest
)
4423 bridge_info_t
*bridge
=
4424 get_configured_bridge_by_addr_port_digest(addr
, port
, digest
);
4425 if (bridge
&& tor_digest_is_zero(bridge
->identity
)) {
4426 memcpy(bridge
->identity
, digest
, DIGEST_LEN
);
4427 log_notice(LD_DIR
, "Learned fingerprint %s for bridge %s:%d",
4428 hex_str(digest
, DIGEST_LEN
), fmt_addr(addr
), port
);
4432 /** Remember a new bridge at <b>addr</b>:<b>port</b>. If <b>digest</b>
4433 * is set, it tells us the identity key too. */
4435 bridge_add_from_config(const tor_addr_t
*addr
, uint16_t port
, char *digest
)
4437 bridge_info_t
*b
= tor_malloc_zero(sizeof(bridge_info_t
));
4438 tor_addr_copy(&b
->addr
, addr
);
4441 memcpy(b
->identity
, digest
, DIGEST_LEN
);
4442 b
->fetch_status
.schedule
= DL_SCHED_BRIDGE
;
4444 bridge_list
= smartlist_create();
4445 smartlist_add(bridge_list
, b
);
4448 /** If <b>digest</b> is one of our known bridges, return it. */
4449 static bridge_info_t
*
4450 find_bridge_by_digest(const char *digest
)
4452 SMARTLIST_FOREACH(bridge_list
, bridge_info_t
*, bridge
,
4454 if (!memcmp(bridge
->identity
, digest
, DIGEST_LEN
))
4460 /** We need to ask <b>bridge</b> for its server descriptor. <b>address</b>
4461 * is a helpful string describing this bridge. */
4463 launch_direct_bridge_descriptor_fetch(bridge_info_t
*bridge
)
4467 if (connection_get_by_type_addr_port_purpose(
4468 CONN_TYPE_DIR
, &bridge
->addr
, bridge
->port
,
4469 DIR_PURPOSE_FETCH_SERVERDESC
))
4470 return; /* it's already on the way */
4472 address
= tor_dup_addr(&bridge
->addr
);
4473 directory_initiate_command(address
, &bridge
->addr
,
4475 0, /* does not matter */
4476 1, bridge
->identity
,
4477 DIR_PURPOSE_FETCH_SERVERDESC
,
4478 ROUTER_PURPOSE_BRIDGE
,
4479 0, "authority.z", NULL
, 0, 0);
4483 /** Fetching the bridge descriptor from the bridge authority returned a
4484 * "not found". Fall back to trying a direct fetch. */
4486 retry_bridge_descriptor_fetch_directly(const char *digest
)
4488 bridge_info_t
*bridge
= find_bridge_by_digest(digest
);
4490 return; /* not found? oh well. */
4492 launch_direct_bridge_descriptor_fetch(bridge
);
4495 /** For each bridge in our list for which we don't currently have a
4496 * descriptor, fetch a new copy of its descriptor -- either directly
4497 * from the bridge or via a bridge authority. */
4499 fetch_bridge_descriptors(or_options_t
*options
, time_t now
)
4501 int num_bridge_auths
= get_n_authorities(BRIDGE_AUTHORITY
);
4502 int ask_bridge_directly
;
4503 int can_use_bridge_authority
;
4508 SMARTLIST_FOREACH_BEGIN(bridge_list
, bridge_info_t
*, bridge
)
4510 if (!download_status_is_ready(&bridge
->fetch_status
, now
,
4511 IMPOSSIBLE_TO_DOWNLOAD
))
4512 continue; /* don't bother, no need to retry yet */
4514 /* schedule another fetch as if this one will fail, in case it does */
4515 download_status_failed(&bridge
->fetch_status
, 0);
4517 can_use_bridge_authority
= !tor_digest_is_zero(bridge
->identity
) &&
4519 ask_bridge_directly
= !can_use_bridge_authority
||
4520 !options
->UpdateBridgesFromAuthority
;
4521 log_debug(LD_DIR
, "ask_bridge_directly=%d (%d, %d, %d)",
4522 ask_bridge_directly
, tor_digest_is_zero(bridge
->identity
),
4523 !options
->UpdateBridgesFromAuthority
, !num_bridge_auths
);
4525 if (ask_bridge_directly
&&
4526 !fascist_firewall_allows_address_or(&bridge
->addr
, bridge
->port
)) {
4527 log_notice(LD_DIR
, "Bridge at '%s:%d' isn't reachable by our "
4528 "firewall policy. %s.", fmt_addr(&bridge
->addr
),
4530 can_use_bridge_authority
?
4531 "Asking bridge authority instead" : "Skipping");
4532 if (can_use_bridge_authority
)
4533 ask_bridge_directly
= 0;
4538 if (ask_bridge_directly
) {
4539 /* we need to ask the bridge itself for its descriptor. */
4540 launch_direct_bridge_descriptor_fetch(bridge
);
4542 /* We have a digest and we want to ask an authority. We could
4543 * combine all the requests into one, but that may give more
4544 * hints to the bridge authority than we want to give. */
4545 char resource
[10 + HEX_DIGEST_LEN
];
4546 memcpy(resource
, "fp/", 3);
4547 base16_encode(resource
+3, HEX_DIGEST_LEN
+1,
4548 bridge
->identity
, DIGEST_LEN
);
4549 memcpy(resource
+3+HEX_DIGEST_LEN
, ".z", 3);
4550 log_info(LD_DIR
, "Fetching bridge info '%s' from bridge authority.",
4552 directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC
,
4553 ROUTER_PURPOSE_BRIDGE
, resource
, 0);
4556 SMARTLIST_FOREACH_END(bridge
);
4559 /** We just learned a descriptor for a bridge. See if that
4560 * digest is in our entry guard list, and add it if not. */
4562 learned_bridge_descriptor(routerinfo_t
*ri
, int from_cache
)
4565 tor_assert(ri
->purpose
== ROUTER_PURPOSE_BRIDGE
);
4566 if (get_options()->UseBridges
) {
4567 int first
= !any_bridge_descriptors_known();
4568 bridge_info_t
*bridge
= get_configured_bridge_by_routerinfo(ri
);
4569 time_t now
= time(NULL
);
4572 if (bridge
) { /* if we actually want to use this one */
4573 /* it's here; schedule its re-fetch for a long time from now. */
4575 download_status_reset(&bridge
->fetch_status
);
4577 add_an_entry_guard(ri
, 1);
4578 log_notice(LD_DIR
, "new bridge descriptor '%s' (%s)", ri
->nickname
,
4579 from_cache
? "cached" : "fresh");
4580 /* set entry->made_contact so if it goes down we don't drop it from
4581 * our entry node list */
4582 entry_guard_register_connect_status(ri
->cache_info
.identity_digest
,
4585 routerlist_retry_directory_downloads(now
);
4590 /** Return 1 if any of our entry guards have descriptors that
4591 * are marked with purpose 'bridge' and are running. Else return 0.
4593 * We use this function to decide if we're ready to start building
4594 * circuits through our bridges, or if we need to wait until the
4595 * directory "server/authority" requests finish. */
4597 any_bridge_descriptors_known(void)
4599 tor_assert(get_options()->UseBridges
);
4600 return choose_random_entry(NULL
)!=NULL
? 1 : 0;
4603 /** Return 1 if there are any directory conns fetching bridge descriptors
4604 * that aren't marked for close. We use this to guess if we should tell
4605 * the controller that we have a problem. */
4607 any_pending_bridge_descriptor_fetches(void)
4609 smartlist_t
*conns
= get_connection_array();
4610 SMARTLIST_FOREACH(conns
, connection_t
*, conn
,
4612 if (conn
->type
== CONN_TYPE_DIR
&&
4613 conn
->purpose
== DIR_PURPOSE_FETCH_SERVERDESC
&&
4614 TO_DIR_CONN(conn
)->router_purpose
== ROUTER_PURPOSE_BRIDGE
&&
4615 !conn
->marked_for_close
&&
4616 conn
->linked
&& !conn
->linked_conn
->marked_for_close
) {
4617 log_debug(LD_DIR
, "found one: %s", conn
->address
);
4624 /** Return 1 if we have at least one descriptor for an entry guard
4625 * (bridge or member of EntryNodes) and all descriptors we know are
4626 * down. Else return 0. If <b>act</b> is 1, then mark the down guards
4627 * up; else just observe and report. */
4629 entries_retry_helper(or_options_t
*options
, int act
)
4633 int any_running
= 0;
4634 int purpose
= options
->UseBridges
?
4635 ROUTER_PURPOSE_BRIDGE
: ROUTER_PURPOSE_GENERAL
;
4637 entry_guards
= smartlist_create();
4638 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
4640 ri
= router_get_by_digest(e
->identity
);
4641 if (ri
&& ri
->purpose
== purpose
) {
4644 any_running
= 1; /* some entry is both known and running */
4646 /* Mark all current connections to this OR as unhealthy, since
4647 * otherwise there could be one that started 30 seconds
4648 * ago, and in 30 seconds it will time out, causing us to mark
4649 * the node down and undermine the retry attempt. We mark even
4650 * the established conns, since if the network just came back
4651 * we'll want to attach circuits to fresh conns. */
4652 connection_or_set_bad_connections(ri
->cache_info
.identity_digest
, 1);
4654 /* mark this entry node for retry */
4655 router_set_status(ri
->cache_info
.identity_digest
, 1);
4661 log_debug(LD_DIR
, "%d: any_known %d, any_running %d",
4662 act
, any_known
, any_running
);
4663 return any_known
&& !any_running
;
4666 /** Do we know any descriptors for our bridges / entrynodes, and are
4667 * all the ones we have descriptors for down? */
4669 entries_known_but_down(or_options_t
*options
)
4671 tor_assert(entry_list_is_constrained(options
));
4672 return entries_retry_helper(options
, 0);
4675 /** Mark all down known bridges / entrynodes up. */
4677 entries_retry_all(or_options_t
*options
)
4679 tor_assert(entry_list_is_constrained(options
));
4680 entries_retry_helper(options
, 1);
4683 /** Release all storage held by the list of entry guards and related
4684 * memory structs. */
4686 entry_guards_free_all(void)
4689 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
4690 entry_guard_free(e
));
4691 smartlist_free(entry_guards
);
4692 entry_guards
= NULL
;
4694 clear_bridge_list();
4695 smartlist_free(bridge_list
);