1 /* Copyright (c) 2001 Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4 * Copyright (c) 2007-2012, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
9 * \brief The actual details of building circuits.
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"
29 #include "transports.h"
33 #include "routerlist.h"
34 #include "routerparse.h"
40 #define MIN(a,b) ((a)<(b)?(a):(b))
43 #define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
45 /********* START VARIABLES **********/
46 /** Global list of circuit build times */
47 // XXXX023: Add this as a member for entry_guard_t instead of global?
48 // Then we could do per-guard statistics, as guards are likely to
49 // vary in their own latency. The downside of this is that guards
50 // can change frequently, so we'd be building a lot more circuits
52 /* XXXX023 Make this static; add accessor functions. */
53 circuit_build_times_t circ_times
;
55 /** A global list of all circuits at this hop. */
56 extern circuit_t
*global_circuitlist
;
58 /** An entry_guard_t represents our information about a chosen long-term
59 * first hop, known as a "helper" node in the literature. We can't just
60 * use a node_t, since we want to remember these even when we
61 * don't have any directory info. */
63 char nickname
[MAX_NICKNAME_LEN
+1];
64 char identity
[DIGEST_LEN
];
65 time_t chosen_on_date
; /**< Approximately when was this guard added?
66 * "0" if we don't know. */
67 char *chosen_by_version
; /**< What tor version added this guard? NULL
68 * if we don't know. */
69 unsigned int made_contact
: 1; /**< 0 if we have never connected to this
70 * router, 1 if we have. */
71 unsigned int can_retry
: 1; /**< Should we retry connecting to this entry,
72 * in spite of having it marked as unreachable?*/
73 unsigned int path_bias_notice
: 1; /**< Did we alert the user about path bias
74 * for this node already? */
75 unsigned int path_bias_disabled
: 1; /**< Have we disabled this node because
76 * of path bias issues? */
77 time_t bad_since
; /**< 0 if this guard is currently usable, or the time at
78 * which it was observed to become (according to the
79 * directory or the user configuration) unusable. */
80 time_t unreachable_since
; /**< 0 if we can connect to this guard, or the
81 * time at which we first noticed we couldn't
83 time_t last_attempted
; /**< 0 if we can connect to this guard, or the time
84 * at which we last failed to connect to it. */
86 unsigned first_hops
; /**< Number of first hops this guard has completed */
87 unsigned circuit_successes
; /**< Number of successfully built circuits using
88 * this guard as first hop. */
91 /** Information about a configured bridge. Currently this just matches the
92 * ones in the torrc file, but one day we may be able to learn about new
93 * bridges on our own, and remember them in the state file. */
95 /** Address of the bridge. */
97 /** TLS port for the bridge. */
99 /** Boolean: We are re-parsing our bridge list, and we are going to remove
100 * this one if we don't find it in the list of configured bridges. */
101 unsigned marked_for_removal
: 1;
102 /** Expected identity digest, or all zero bytes if we don't know what the
103 * digest should be. */
104 char identity
[DIGEST_LEN
];
106 /** Name of pluggable transport protocol taken from its config line. */
107 char *transport_name
;
109 /** When should we next try to fetch a descriptor for this bridge? */
110 download_status_t fetch_status
;
113 /** A list of our chosen entry guards. */
114 static smartlist_t
*entry_guards
= NULL
;
115 /** A value of 1 means that the entry_guards list has changed
116 * and those changes need to be flushed to disk. */
117 static int entry_guards_dirty
= 0;
119 /** If set, we're running the unit tests: we should avoid clobbering
120 * our state file or accessing get_options() or get_or_state() */
121 static int unit_tests
= 0;
123 /********* END VARIABLES ************/
125 static int circuit_deliver_create_cell(circuit_t
*circ
,
126 uint8_t cell_type
, const char *payload
);
127 static int onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
);
128 static crypt_path_t
*onion_next_hop_in_cpath(crypt_path_t
*cpath
);
129 static int onion_extend_cpath(origin_circuit_t
*circ
);
130 static int count_acceptable_nodes(smartlist_t
*routers
);
131 static int onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
);
133 static void entry_guards_changed(void);
134 static entry_guard_t
*entry_guard_get_by_id_digest(const char *digest
);
136 static void bridge_free(bridge_info_t
*bridge
);
139 * This function decides if CBT learning should be disabled. It returns
140 * true if one or more of the following four conditions are met:
142 * 1. If the cbtdisabled consensus parameter is set.
143 * 2. If the torrc option LearnCircuitBuildTimeout is false.
144 * 3. If we are a directory authority
145 * 4. If we fail to write circuit build time history to our state file.
148 circuit_build_times_disabled(void)
153 int consensus_disabled
= networkstatus_get_param(NULL
, "cbtdisabled",
155 int config_disabled
= !get_options()->LearnCircuitBuildTimeout
;
156 int dirauth_disabled
= get_options()->AuthoritativeDir
;
157 int state_disabled
= did_last_state_file_write_fail() ? 1 : 0;
159 if (consensus_disabled
|| config_disabled
|| dirauth_disabled
||
162 "CircuitBuildTime learning is disabled. "
163 "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
164 consensus_disabled
, config_disabled
, dirauth_disabled
,
169 "CircuitBuildTime learning is not disabled. "
170 "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
171 consensus_disabled
, config_disabled
, dirauth_disabled
,
179 * Retrieve and bounds-check the cbtmaxtimeouts consensus paramter.
181 * Effect: When this many timeouts happen in the last 'cbtrecentcount'
182 * circuit attempts, the client should discard all of its history and
183 * begin learning a fresh timeout value.
186 circuit_build_times_max_timeouts(void)
188 int32_t cbt_maxtimeouts
;
190 cbt_maxtimeouts
= networkstatus_get_param(NULL
, "cbtmaxtimeouts",
191 CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT
,
192 CBT_MIN_MAX_RECENT_TIMEOUT_COUNT
,
193 CBT_MAX_MAX_RECENT_TIMEOUT_COUNT
);
195 if (!(get_options()->LearnCircuitBuildTimeout
)) {
197 "circuit_build_times_max_timeouts() called, cbtmaxtimeouts is"
202 return cbt_maxtimeouts
;
206 * Retrieve and bounds-check the cbtnummodes consensus paramter.
208 * Effect: This value governs how many modes to use in the weighted
209 * average calculation of Pareto parameter Xm. A value of 3 introduces
210 * some bias (2-5% of CDF) under ideal conditions, but allows for better
211 * performance in the event that a client chooses guard nodes of radically
212 * different performance characteristics.
215 circuit_build_times_default_num_xm_modes(void)
217 int32_t num
= networkstatus_get_param(NULL
, "cbtnummodes",
218 CBT_DEFAULT_NUM_XM_MODES
,
219 CBT_MIN_NUM_XM_MODES
,
220 CBT_MAX_NUM_XM_MODES
);
222 if (!(get_options()->LearnCircuitBuildTimeout
)) {
224 "circuit_build_times_default_num_xm_modes() called, cbtnummodes"
233 * Retrieve and bounds-check the cbtmincircs consensus paramter.
235 * Effect: This is the minimum number of circuits to build before
236 * computing a timeout.
239 circuit_build_times_min_circs_to_observe(void)
241 int32_t num
= networkstatus_get_param(NULL
, "cbtmincircs",
242 CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE
,
243 CBT_MIN_MIN_CIRCUITS_TO_OBSERVE
,
244 CBT_MAX_MIN_CIRCUITS_TO_OBSERVE
);
246 if (!(get_options()->LearnCircuitBuildTimeout
)) {
248 "circuit_build_times_min_circs_to_observe() called, cbtmincircs"
256 /** Return true iff <b>cbt</b> has recorded enough build times that we
257 * want to start acting on the timeout it implies. */
259 circuit_build_times_enough_to_compute(circuit_build_times_t
*cbt
)
261 return cbt
->total_build_times
>= circuit_build_times_min_circs_to_observe();
265 * Retrieve and bounds-check the cbtquantile consensus paramter.
267 * Effect: This is the position on the quantile curve to use to set the
268 * timeout value. It is a percent (10-99).
271 circuit_build_times_quantile_cutoff(void)
273 int32_t num
= networkstatus_get_param(NULL
, "cbtquantile",
274 CBT_DEFAULT_QUANTILE_CUTOFF
,
275 CBT_MIN_QUANTILE_CUTOFF
,
276 CBT_MAX_QUANTILE_CUTOFF
);
278 if (!(get_options()->LearnCircuitBuildTimeout
)) {
280 "circuit_build_times_quantile_cutoff() called, cbtquantile"
288 /* DOCDOC circuit_build_times_get_bw_scale */
290 circuit_build_times_get_bw_scale(networkstatus_t
*ns
)
292 return networkstatus_get_param(ns
, "bwweightscale",
295 BW_MAX_WEIGHT_SCALE
);
299 * Retrieve and bounds-check the cbtclosequantile consensus paramter.
301 * Effect: This is the position on the quantile curve to use to set the
302 * timeout value to use to actually close circuits. It is a percent
306 circuit_build_times_close_quantile(void)
309 /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */
310 int32_t min
= (int)tor_lround(100*circuit_build_times_quantile_cutoff());
311 param
= networkstatus_get_param(NULL
, "cbtclosequantile",
312 CBT_DEFAULT_CLOSE_QUANTILE
,
313 CBT_MIN_CLOSE_QUANTILE
,
314 CBT_MAX_CLOSE_QUANTILE
);
316 if (!(get_options()->LearnCircuitBuildTimeout
)) {
318 "circuit_build_times_close_quantile() called, cbtclosequantile"
323 log_warn(LD_DIR
, "Consensus parameter cbtclosequantile is "
324 "too small, raising to %d", min
);
327 return param
/ 100.0;
331 * Retrieve and bounds-check the cbttestfreq consensus paramter.
333 * Effect: Describes how often in seconds to build a test circuit to
334 * gather timeout values. Only applies if less than 'cbtmincircs'
335 * have been recorded.
338 circuit_build_times_test_frequency(void)
340 int32_t num
= networkstatus_get_param(NULL
, "cbttestfreq",
341 CBT_DEFAULT_TEST_FREQUENCY
,
342 CBT_MIN_TEST_FREQUENCY
,
343 CBT_MAX_TEST_FREQUENCY
);
345 if (!(get_options()->LearnCircuitBuildTimeout
)) {
347 "circuit_build_times_test_frequency() called, cbttestfreq is %d",
355 * Retrieve and bounds-check the cbtmintimeout consensus parameter.
357 * Effect: This is the minimum allowed timeout value in milliseconds.
358 * The minimum is to prevent rounding to 0 (we only check once
362 circuit_build_times_min_timeout(void)
364 int32_t num
= networkstatus_get_param(NULL
, "cbtmintimeout",
365 CBT_DEFAULT_TIMEOUT_MIN_VALUE
,
366 CBT_MIN_TIMEOUT_MIN_VALUE
,
367 CBT_MAX_TIMEOUT_MIN_VALUE
);
369 if (!(get_options()->LearnCircuitBuildTimeout
)) {
371 "circuit_build_times_min_timeout() called, cbtmintimeout is %d",
379 * Retrieve and bounds-check the cbtinitialtimeout consensus paramter.
381 * Effect: This is the timeout value to use before computing a timeout,
385 circuit_build_times_initial_timeout(void)
387 int32_t min
= circuit_build_times_min_timeout();
388 int32_t param
= networkstatus_get_param(NULL
, "cbtinitialtimeout",
389 CBT_DEFAULT_TIMEOUT_INITIAL_VALUE
,
390 CBT_MIN_TIMEOUT_INITIAL_VALUE
,
391 CBT_MAX_TIMEOUT_INITIAL_VALUE
);
393 if (!(get_options()->LearnCircuitBuildTimeout
)) {
395 "circuit_build_times_initial_timeout() called, "
396 "cbtinitialtimeout is %d",
401 log_warn(LD_DIR
, "Consensus parameter cbtinitialtimeout is too small, "
402 "raising to %d", min
);
409 * Retrieve and bounds-check the cbtrecentcount consensus paramter.
411 * Effect: This is the number of circuit build times to keep track of
412 * for deciding if we hit cbtmaxtimeouts and need to reset our state
413 * and learn a new timeout.
416 circuit_build_times_recent_circuit_count(networkstatus_t
*ns
)
419 num
= networkstatus_get_param(ns
, "cbtrecentcount",
420 CBT_DEFAULT_RECENT_CIRCUITS
,
421 CBT_MIN_RECENT_CIRCUITS
,
422 CBT_MAX_RECENT_CIRCUITS
);
424 if (!(get_options()->LearnCircuitBuildTimeout
)) {
426 "circuit_build_times_recent_circuit_count() called, "
427 "cbtrecentcount is %d",
435 * This function is called when we get a consensus update.
437 * It checks to see if we have changed any consensus parameters
438 * that require reallocation or discard of previous stats.
441 circuit_build_times_new_consensus_params(circuit_build_times_t
*cbt
,
447 * First check if we're doing adaptive timeouts at all; nothing to
448 * update if we aren't.
451 if (!circuit_build_times_disabled()) {
452 num
= circuit_build_times_recent_circuit_count(ns
);
455 if (num
!= cbt
->liveness
.num_recent_circs
) {
456 int8_t *recent_circs
;
457 log_notice(LD_CIRC
, "The Tor Directory Consensus has changed how many "
458 "circuits we must track to detect network failures from %d "
459 "to %d.", cbt
->liveness
.num_recent_circs
, num
);
461 tor_assert(cbt
->liveness
.timeouts_after_firsthop
||
462 cbt
->liveness
.num_recent_circs
== 0);
465 * Technically this is a circular array that we are reallocating
466 * and memcopying. However, since it only consists of either 1s
467 * or 0s, and is only used in a statistical test to determine when
468 * we should discard our history after a sufficient number of 1's
469 * have been reached, it is fine if order is not preserved or
472 * cbtrecentcount should only be changing in cases of severe network
473 * distress anyway, so memory correctness here is paramount over
474 * doing acrobatics to preserve the array.
476 recent_circs
= tor_malloc_zero(sizeof(int8_t)*num
);
477 if (cbt
->liveness
.timeouts_after_firsthop
&&
478 cbt
->liveness
.num_recent_circs
> 0) {
479 memcpy(recent_circs
, cbt
->liveness
.timeouts_after_firsthop
,
480 sizeof(int8_t)*MIN(num
, cbt
->liveness
.num_recent_circs
));
483 // Adjust the index if it needs it.
484 if (num
< cbt
->liveness
.num_recent_circs
) {
485 cbt
->liveness
.after_firsthop_idx
= MIN(num
-1,
486 cbt
->liveness
.after_firsthop_idx
);
489 tor_free(cbt
->liveness
.timeouts_after_firsthop
);
490 cbt
->liveness
.timeouts_after_firsthop
= recent_circs
;
491 cbt
->liveness
.num_recent_circs
= num
;
493 /* else no change, nothing to do */
494 } else { /* num == 0 */
496 * Weird. This probably shouldn't happen, so log a warning, but try
497 * to do something sensible anyway.
501 "The cbtrecentcircs consensus parameter came back zero! "
502 "This disables adaptive timeouts since we can't keep track of "
503 "any recent circuits.");
505 circuit_build_times_free_timeouts(cbt
);
509 * Adaptive timeouts are disabled; this might be because of the
510 * LearnCircuitBuildTimes config parameter, and hence permanent, or
511 * the cbtdisabled consensus parameter, so it may be a new condition.
512 * Treat it like getting num == 0 above and free the circuit history
516 circuit_build_times_free_timeouts(cbt
);
520 /** Make a note that we're running unit tests (rather than running Tor
521 * itself), so we avoid clobbering our state file. */
523 circuitbuild_running_unit_tests(void)
529 * Return the initial default or configured timeout in milliseconds
532 circuit_build_times_get_initial_timeout(void)
537 * Check if we have LearnCircuitBuildTimeout, and if we don't,
538 * always use CircuitBuildTimeout, no questions asked.
540 if (get_options()->LearnCircuitBuildTimeout
) {
541 if (!unit_tests
&& get_options()->CircuitBuildTimeout
) {
542 timeout
= get_options()->CircuitBuildTimeout
*1000;
543 if (timeout
< circuit_build_times_min_timeout()) {
544 log_warn(LD_CIRC
, "Config CircuitBuildTimeout too low. Setting to %ds",
545 circuit_build_times_min_timeout()/1000);
546 timeout
= circuit_build_times_min_timeout();
549 timeout
= circuit_build_times_initial_timeout();
552 timeout
= get_options()->CircuitBuildTimeout
*1000;
559 * Reset the build time state.
561 * Leave estimated parameters, timeout and network liveness intact
565 circuit_build_times_reset(circuit_build_times_t
*cbt
)
567 memset(cbt
->circuit_build_times
, 0, sizeof(cbt
->circuit_build_times
));
568 cbt
->total_build_times
= 0;
569 cbt
->build_times_idx
= 0;
570 cbt
->have_computed_timeout
= 0;
574 * Initialize the buildtimes structure for first use.
576 * Sets the initial timeout values based on either the config setting,
577 * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
580 circuit_build_times_init(circuit_build_times_t
*cbt
)
582 memset(cbt
, 0, sizeof(*cbt
));
584 * Check if we really are using adaptive timeouts, and don't keep
585 * track of this stuff if not.
587 if (!circuit_build_times_disabled()) {
588 cbt
->liveness
.num_recent_circs
=
589 circuit_build_times_recent_circuit_count(NULL
);
590 cbt
->liveness
.timeouts_after_firsthop
=
591 tor_malloc_zero(sizeof(int8_t)*cbt
->liveness
.num_recent_circs
);
593 cbt
->liveness
.num_recent_circs
= 0;
594 cbt
->liveness
.timeouts_after_firsthop
= NULL
;
596 cbt
->close_ms
= cbt
->timeout_ms
= circuit_build_times_get_initial_timeout();
597 control_event_buildtimeout_set(cbt
, BUILDTIMEOUT_SET_EVENT_RESET
);
601 * Free the saved timeouts, if the cbtdisabled consensus parameter got turned
606 circuit_build_times_free_timeouts(circuit_build_times_t
*cbt
)
610 if (cbt
->liveness
.timeouts_after_firsthop
) {
611 tor_free(cbt
->liveness
.timeouts_after_firsthop
);
614 cbt
->liveness
.num_recent_circs
= 0;
619 * Rewind our build time history by n positions.
622 circuit_build_times_rewind_history(circuit_build_times_t
*cbt
, int n
)
626 cbt
->build_times_idx
-= n
;
627 cbt
->build_times_idx
%= CBT_NCIRCUITS_TO_OBSERVE
;
629 for (i
= 0; i
< n
; i
++) {
630 cbt
->circuit_build_times
[(i
+cbt
->build_times_idx
)
631 %CBT_NCIRCUITS_TO_OBSERVE
]=0;
634 if (cbt
->total_build_times
> n
) {
635 cbt
->total_build_times
-= n
;
637 cbt
->total_build_times
= 0;
641 "Rewound history by %d places. Current index: %d. "
642 "Total: %d", n
, cbt
->build_times_idx
, cbt
->total_build_times
);
647 * Add a new build time value <b>time</b> to the set of build times. Time
648 * units are milliseconds.
650 * circuit_build_times <b>cbt</b> is a circular array, so loop around when
654 circuit_build_times_add_time(circuit_build_times_t
*cbt
, build_time_t time
)
656 if (time
<= 0 || time
> CBT_BUILD_TIME_MAX
) {
657 log_warn(LD_BUG
, "Circuit build time is too large (%u)."
658 "This is probably a bug.", time
);
659 tor_fragile_assert();
663 log_debug(LD_CIRC
, "Adding circuit build time %u", time
);
665 cbt
->circuit_build_times
[cbt
->build_times_idx
] = time
;
666 cbt
->build_times_idx
= (cbt
->build_times_idx
+ 1) % CBT_NCIRCUITS_TO_OBSERVE
;
667 if (cbt
->total_build_times
< CBT_NCIRCUITS_TO_OBSERVE
)
668 cbt
->total_build_times
++;
670 if ((cbt
->total_build_times
% CBT_SAVE_STATE_EVERY
) == 0) {
671 /* Save state every n circuit builds */
672 if (!unit_tests
&& !get_options()->AvoidDiskWrites
)
673 or_state_mark_dirty(get_or_state(), 0);
680 * Return maximum circuit build time
683 circuit_build_times_max(circuit_build_times_t
*cbt
)
686 build_time_t max_build_time
= 0;
687 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
688 if (cbt
->circuit_build_times
[i
] > max_build_time
689 && cbt
->circuit_build_times
[i
] != CBT_BUILD_ABANDONED
)
690 max_build_time
= cbt
->circuit_build_times
[i
];
692 return max_build_time
;
696 /** Return minimum circuit build time */
698 circuit_build_times_min(circuit_build_times_t
*cbt
)
701 build_time_t min_build_time
= CBT_BUILD_TIME_MAX
;
702 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
703 if (cbt
->circuit_build_times
[i
] && /* 0 <-> uninitialized */
704 cbt
->circuit_build_times
[i
] < min_build_time
)
705 min_build_time
= cbt
->circuit_build_times
[i
];
707 if (min_build_time
== CBT_BUILD_TIME_MAX
) {
708 log_warn(LD_CIRC
, "No build times less than CBT_BUILD_TIME_MAX!");
710 return min_build_time
;
715 * Calculate and return a histogram for the set of build times.
717 * Returns an allocated array of histrogram bins representing
718 * the frequency of index*CBT_BIN_WIDTH millisecond
719 * build times. Also outputs the number of bins in nbins.
721 * The return value must be freed by the caller.
724 circuit_build_times_create_histogram(circuit_build_times_t
*cbt
,
728 build_time_t max_build_time
= circuit_build_times_max(cbt
);
731 *nbins
= 1 + (max_build_time
/ CBT_BIN_WIDTH
);
732 histogram
= tor_malloc_zero(*nbins
* sizeof(build_time_t
));
734 // calculate histogram
735 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
736 if (cbt
->circuit_build_times
[i
] == 0
737 || cbt
->circuit_build_times
[i
] == CBT_BUILD_ABANDONED
)
738 continue; /* 0 <-> uninitialized */
740 c
= (cbt
->circuit_build_times
[i
] / CBT_BIN_WIDTH
);
748 * Return the Pareto start-of-curve parameter Xm.
750 * Because we are not a true Pareto curve, we compute this as the
751 * weighted average of the N most frequent build time bins. N is either
752 * 1 if we don't have enough circuit build time data collected, or
753 * determined by the consensus parameter cbtnummodes (default 3).
756 circuit_build_times_get_xm(circuit_build_times_t
*cbt
)
758 build_time_t i
, nbins
;
759 build_time_t
*nth_max_bin
;
760 int32_t bin_counts
=0;
761 build_time_t ret
= 0;
762 uint32_t *histogram
= circuit_build_times_create_histogram(cbt
, &nbins
);
764 int num_modes
= circuit_build_times_default_num_xm_modes();
766 tor_assert(nbins
> 0);
767 tor_assert(num_modes
> 0);
769 // Only use one mode if < 1000 buildtimes. Not enough data
771 if (cbt
->total_build_times
< CBT_NCIRCUITS_TO_OBSERVE
)
774 nth_max_bin
= (build_time_t
*)tor_malloc_zero(num_modes
*sizeof(build_time_t
));
776 /* Determine the N most common build times */
777 for (i
= 0; i
< nbins
; i
++) {
778 if (histogram
[i
] >= histogram
[nth_max_bin
[0]]) {
782 for (n
= 1; n
< num_modes
; n
++) {
783 if (histogram
[i
] >= histogram
[nth_max_bin
[n
]] &&
784 (!histogram
[nth_max_bin
[n
-1]]
785 || histogram
[i
] < histogram
[nth_max_bin
[n
-1]])) {
791 for (n
= 0; n
< num_modes
; n
++) {
792 bin_counts
+= histogram
[nth_max_bin
[n
]];
793 ret
+= CBT_BIN_TO_MS(nth_max_bin
[n
])*histogram
[nth_max_bin
[n
]];
794 log_info(LD_CIRC
, "Xm mode #%d: %u %u", n
, CBT_BIN_TO_MS(nth_max_bin
[n
]),
795 histogram
[nth_max_bin
[n
]]);
798 /* The following assert is safe, because we don't get called when we
799 * haven't observed at least CBT_MIN_MIN_CIRCUITS_TO_OBSERVE circuits. */
800 tor_assert(bin_counts
> 0);
804 tor_free(nth_max_bin
);
810 * Output a histogram of current circuit build times to
811 * the or_state_t state structure.
814 circuit_build_times_update_state(circuit_build_times_t
*cbt
,
819 build_time_t nbins
= 0;
820 config_line_t
**next
, *line
;
822 histogram
= circuit_build_times_create_histogram(cbt
, &nbins
);
824 config_free_lines(state
->BuildtimeHistogram
);
825 next
= &state
->BuildtimeHistogram
;
828 state
->TotalBuildTimes
= cbt
->total_build_times
;
829 state
->CircuitBuildAbandonedCount
= 0;
831 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
832 if (cbt
->circuit_build_times
[i
] == CBT_BUILD_ABANDONED
)
833 state
->CircuitBuildAbandonedCount
++;
836 for (i
= 0; i
< nbins
; i
++) {
837 // compress the histogram by skipping the blanks
838 if (histogram
[i
] == 0) continue;
839 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
840 line
->key
= tor_strdup("CircuitBuildTimeBin");
841 tor_asprintf(&line
->value
, "%d %d",
842 CBT_BIN_TO_MS(i
), histogram
[i
]);
843 next
= &(line
->next
);
847 if (!get_options()->AvoidDiskWrites
)
848 or_state_mark_dirty(get_or_state(), 0);
855 * Shuffle the build times array.
857 * Adapted from http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
860 circuit_build_times_shuffle_and_store_array(circuit_build_times_t
*cbt
,
861 build_time_t
*raw_times
,
864 uint32_t n
= num_times
;
865 if (num_times
> CBT_NCIRCUITS_TO_OBSERVE
) {
866 log_notice(LD_CIRC
, "The number of circuit times that this Tor version "
867 "uses to calculate build times is less than the number stored "
868 "in your state file. Decreasing the circuit time history from "
869 "%lu to %d.", (unsigned long)num_times
,
870 CBT_NCIRCUITS_TO_OBSERVE
);
874 log_warn(LD_CIRC
, "For some insane reasons, you had %lu circuit build "
875 "observations in your state file. That's far too many; probably "
876 "there's a bug here.", (unsigned long)n
);
880 /* This code can only be run on a compact array */
882 int k
= crypto_rand_int(n
+ 1); /* 0 <= k <= n. */
883 build_time_t tmp
= raw_times
[k
];
884 raw_times
[k
] = raw_times
[n
];
888 /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
889 * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
890 for (n
= 0; n
< MIN(num_times
, CBT_NCIRCUITS_TO_OBSERVE
); n
++) {
891 circuit_build_times_add_time(cbt
, raw_times
[n
]);
896 * Filter old synthetic timeouts that were created before the
897 * new right-censored Pareto calculation was deployed.
899 * Once all clients before 0.2.1.13-alpha are gone, this code
903 circuit_build_times_filter_timeouts(circuit_build_times_t
*cbt
)
905 int num_filtered
=0, i
=0;
906 double timeout_rate
= 0;
907 build_time_t max_timeout
= 0;
909 timeout_rate
= circuit_build_times_timeout_rate(cbt
);
910 max_timeout
= (build_time_t
)cbt
->close_ms
;
912 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
913 if (cbt
->circuit_build_times
[i
] > max_timeout
) {
914 build_time_t replaced
= cbt
->circuit_build_times
[i
];
916 cbt
->circuit_build_times
[i
] = CBT_BUILD_ABANDONED
;
918 log_debug(LD_CIRC
, "Replaced timeout %d with %d", replaced
,
919 cbt
->circuit_build_times
[i
]);
924 "We had %d timeouts out of %d build times, "
925 "and filtered %d above the max of %u",
926 (int)(cbt
->total_build_times
*timeout_rate
),
927 cbt
->total_build_times
, num_filtered
, max_timeout
);
933 * Load histogram from <b>state</b>, shuffling the resulting array
934 * after we do so. Use this result to estimate parameters and
935 * calculate the timeout.
937 * Return -1 on error.
940 circuit_build_times_parse_state(circuit_build_times_t
*cbt
,
944 uint32_t loaded_cnt
= 0, N
= 0;
947 build_time_t
*loaded_times
;
949 circuit_build_times_init(cbt
);
951 if (circuit_build_times_disabled()) {
955 /* build_time_t 0 means uninitialized */
956 loaded_times
= tor_malloc_zero(sizeof(build_time_t
)*state
->TotalBuildTimes
);
958 for (line
= state
->BuildtimeHistogram
; line
; line
= line
->next
) {
959 smartlist_t
*args
= smartlist_new();
960 smartlist_split_string(args
, line
->value
, " ",
961 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
962 if (smartlist_len(args
) < 2) {
963 log_warn(LD_GENERAL
, "Unable to parse circuit build times: "
964 "Too few arguments to CircuitBuildTime");
966 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
967 smartlist_free(args
);
970 const char *ms_str
= smartlist_get(args
,0);
971 const char *count_str
= smartlist_get(args
,1);
975 ms
= (build_time_t
)tor_parse_ulong(ms_str
, 0, 0,
976 CBT_BUILD_TIME_MAX
, &ok
, NULL
);
978 log_warn(LD_GENERAL
, "Unable to parse circuit build times: "
979 "Unparsable bin number");
981 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
982 smartlist_free(args
);
985 count
= (uint32_t)tor_parse_ulong(count_str
, 0, 0,
986 UINT32_MAX
, &ok
, NULL
);
988 log_warn(LD_GENERAL
, "Unable to parse circuit build times: "
989 "Unparsable bin count");
991 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
992 smartlist_free(args
);
996 if (loaded_cnt
+count
+state
->CircuitBuildAbandonedCount
997 > state
->TotalBuildTimes
) {
999 "Too many build times in state file. "
1000 "Stopping short before %d",
1002 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
1003 smartlist_free(args
);
1007 for (k
= 0; k
< count
; k
++) {
1008 loaded_times
[loaded_cnt
++] = ms
;
1011 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
1012 smartlist_free(args
);
1017 "Adding %d timeouts.", state
->CircuitBuildAbandonedCount
);
1018 for (i
=0; i
< state
->CircuitBuildAbandonedCount
; i
++) {
1019 loaded_times
[loaded_cnt
++] = CBT_BUILD_ABANDONED
;
1022 if (loaded_cnt
!= state
->TotalBuildTimes
) {
1024 "Corrupt state file? Build times count mismatch. "
1025 "Read %d times, but file says %d", loaded_cnt
,
1026 state
->TotalBuildTimes
);
1028 circuit_build_times_reset(cbt
);
1032 circuit_build_times_shuffle_and_store_array(cbt
, loaded_times
, loaded_cnt
);
1034 /* Verify that we didn't overwrite any indexes */
1035 for (i
=0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
1036 if (!cbt
->circuit_build_times
[i
])
1041 "Loaded %d/%d values from %d lines in circuit time histogram",
1042 tot_values
, cbt
->total_build_times
, N
);
1044 if (cbt
->total_build_times
!= tot_values
1045 || cbt
->total_build_times
> CBT_NCIRCUITS_TO_OBSERVE
) {
1047 "Corrupt state file? Shuffled build times mismatch. "
1048 "Read %d times, but file says %d", tot_values
,
1049 state
->TotalBuildTimes
);
1051 circuit_build_times_reset(cbt
);
1055 circuit_build_times_set_timeout(cbt
);
1057 if (!state
->CircuitBuildAbandonedCount
&& cbt
->total_build_times
) {
1058 circuit_build_times_filter_timeouts(cbt
);
1062 tor_free(loaded_times
);
1063 return err
? -1 : 0;
1067 * Estimates the Xm and Alpha parameters using
1068 * http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
1070 * The notable difference is that we use mode instead of min to estimate Xm.
1071 * This is because our distribution is frechet-like. We claim this is
1072 * an acceptable approximation because we are only concerned with the
1073 * accuracy of the CDF of the tail.
1076 circuit_build_times_update_alpha(circuit_build_times_t
*cbt
)
1078 build_time_t
*x
=cbt
->circuit_build_times
;
1080 int n
=0,i
=0,abandoned_count
=0;
1081 build_time_t max_time
=0;
1083 /* http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
1084 /* We sort of cheat here and make our samples slightly more pareto-like
1085 * and less frechet-like. */
1086 cbt
->Xm
= circuit_build_times_get_xm(cbt
);
1088 tor_assert(cbt
->Xm
> 0);
1090 for (i
=0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
1095 if (x
[i
] < cbt
->Xm
) {
1096 a
+= tor_mathlog(cbt
->Xm
);
1097 } else if (x
[i
] == CBT_BUILD_ABANDONED
) {
1100 a
+= tor_mathlog(x
[i
]);
1101 if (x
[i
] > max_time
)
1108 * We are erring and asserting here because this can only happen
1109 * in codepaths other than startup. The startup state parsing code
1110 * performs this same check, and resets state if it hits it. If we
1111 * hit it at runtime, something serious has gone wrong.
1113 if (n
!=cbt
->total_build_times
) {
1114 log_err(LD_CIRC
, "Discrepancy in build times count: %d vs %d", n
,
1115 cbt
->total_build_times
);
1117 tor_assert(n
==cbt
->total_build_times
);
1119 if (max_time
<= 0) {
1120 /* This can happen if Xm is actually the *maximum* value in the set.
1121 * It can also happen if we've abandoned every single circuit somehow.
1122 * In either case, tell the caller not to compute a new build timeout. */
1124 "Could not determine largest build time (%d). "
1125 "Xm is %dms and we've abandoned %d out of %d circuits.", max_time
,
1126 cbt
->Xm
, abandoned_count
, n
);
1130 a
+= abandoned_count
*tor_mathlog(max_time
);
1132 a
-= n
*tor_mathlog(cbt
->Xm
);
1133 // Estimator comes from Eq #4 in:
1134 // "Bayesian estimation based on trimmed samples from Pareto populations"
1135 // by Arturo J. Fernández. We are right-censored only.
1136 a
= (n
-abandoned_count
)/a
;
1144 * This is the Pareto Quantile Function. It calculates the point x
1145 * in the distribution such that F(x) = quantile (ie quantile*100%
1146 * of the mass of the density function is below x on the curve).
1148 * We use it to calculate the timeout and also to generate synthetic
1149 * values of time for circuits that timeout before completion.
1151 * See http://en.wikipedia.org/wiki/Quantile_function,
1152 * http://en.wikipedia.org/wiki/Inverse_transform_sampling and
1153 * http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
1154 * random_sample_from_Pareto_distribution
1155 * That's right. I'll cite wikipedia all day long.
1157 * Return value is in milliseconds.
1160 circuit_build_times_calculate_timeout(circuit_build_times_t
*cbt
,
1164 tor_assert(quantile
>= 0);
1165 tor_assert(1.0-quantile
> 0);
1166 tor_assert(cbt
->Xm
> 0);
1168 ret
= cbt
->Xm
/pow(1.0-quantile
,1.0/cbt
->alpha
);
1169 if (ret
> INT32_MAX
) {
1172 tor_assert(ret
> 0);
1178 circuit_build_times_cdf(circuit_build_times_t
*cbt
, double x
)
1181 tor_assert(cbt
->Xm
> 0);
1182 ret
= 1.0-pow(cbt
->Xm
/x
,cbt
->alpha
);
1183 tor_assert(0 <= ret
&& ret
<= 1.0);
1188 * Generate a synthetic time using our distribution parameters.
1190 * The return value will be within the [q_lo, q_hi) quantile points
1194 circuit_build_times_generate_sample(circuit_build_times_t
*cbt
,
1195 double q_lo
, double q_hi
)
1197 double randval
= crypto_rand_double();
1201 /* Generate between [q_lo, q_hi) */
1202 /*XXXX This is what nextafter is supposed to be for; we should use it on the
1203 * platforms that support it. */
1204 q_hi
-= 1.0/(INT32_MAX
);
1206 tor_assert(q_lo
>= 0);
1207 tor_assert(q_hi
< 1);
1208 tor_assert(q_lo
< q_hi
);
1210 u
= q_lo
+ (q_hi
-q_lo
)*randval
;
1212 tor_assert(0 <= u
&& u
< 1.0);
1213 /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
1214 ret
= (build_time_t
)
1215 tor_lround(circuit_build_times_calculate_timeout(cbt
, u
));
1216 tor_assert(ret
> 0);
1221 * Estimate an initial alpha parameter by solving the quantile
1222 * function with a quantile point and a specific timeout value.
1225 circuit_build_times_initial_alpha(circuit_build_times_t
*cbt
,
1226 double quantile
, double timeout_ms
)
1228 // Q(u) = Xm/((1-u)^(1/a))
1229 // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
1230 // CircBuildTimeout = Xm/((1-0.8))^(1/a))
1231 // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
1232 // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
1233 // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
1234 tor_assert(quantile
>= 0);
1235 tor_assert(cbt
->Xm
> 0);
1236 cbt
->alpha
= tor_mathlog(1.0-quantile
)/
1237 (tor_mathlog(cbt
->Xm
)-tor_mathlog(timeout_ms
));
1238 tor_assert(cbt
->alpha
> 0);
1242 * Returns true if we need circuits to be built
1245 circuit_build_times_needs_circuits(circuit_build_times_t
*cbt
)
1247 /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
1248 return !circuit_build_times_enough_to_compute(cbt
);
1252 * Returns true if we should build a timeout test circuit
1256 circuit_build_times_needs_circuits_now(circuit_build_times_t
*cbt
)
1258 return circuit_build_times_needs_circuits(cbt
) &&
1259 approx_time()-cbt
->last_circ_at
> circuit_build_times_test_frequency();
1263 * Called to indicate that the network showed some signs of liveness,
1264 * i.e. we received a cell.
1266 * This is used by circuit_build_times_network_check_live() to decide
1267 * if we should record the circuit build timeout or not.
1269 * This function is called every time we receive a cell. Avoid
1270 * syscalls, events, and other high-intensity work.
1273 circuit_build_times_network_is_live(circuit_build_times_t
*cbt
)
1275 time_t now
= approx_time();
1276 if (cbt
->liveness
.nonlive_timeouts
> 0) {
1278 "Tor now sees network activity. Restoring circuit build "
1279 "timeout recording. Network was down for %d seconds "
1280 "during %d circuit attempts.",
1281 (int)(now
- cbt
->liveness
.network_last_live
),
1282 cbt
->liveness
.nonlive_timeouts
);
1284 cbt
->liveness
.network_last_live
= now
;
1285 cbt
->liveness
.nonlive_timeouts
= 0;
1289 * Called to indicate that we completed a circuit. Because this circuit
1290 * succeeded, it doesn't count as a timeout-after-the-first-hop.
1292 * This is used by circuit_build_times_network_check_changed() to determine
1293 * if we had too many recent timeouts and need to reset our learned timeout
1294 * to something higher.
1297 circuit_build_times_network_circ_success(circuit_build_times_t
*cbt
)
1299 /* Check for NULLness because we might not be using adaptive timeouts */
1300 if (cbt
->liveness
.timeouts_after_firsthop
&&
1301 cbt
->liveness
.num_recent_circs
> 0) {
1302 cbt
->liveness
.timeouts_after_firsthop
[cbt
->liveness
.after_firsthop_idx
]
1304 cbt
->liveness
.after_firsthop_idx
++;
1305 cbt
->liveness
.after_firsthop_idx
%= cbt
->liveness
.num_recent_circs
;
1310 * A circuit just timed out. If it failed after the first hop, record it
1311 * in our history for later deciding if the network speed has changed.
1313 * This is used by circuit_build_times_network_check_changed() to determine
1314 * if we had too many recent timeouts and need to reset our learned timeout
1315 * to something higher.
1318 circuit_build_times_network_timeout(circuit_build_times_t
*cbt
,
1321 /* Check for NULLness because we might not be using adaptive timeouts */
1322 if (cbt
->liveness
.timeouts_after_firsthop
&&
1323 cbt
->liveness
.num_recent_circs
> 0) {
1325 cbt
->liveness
.timeouts_after_firsthop
[cbt
->liveness
.after_firsthop_idx
]
1327 cbt
->liveness
.after_firsthop_idx
++;
1328 cbt
->liveness
.after_firsthop_idx
%= cbt
->liveness
.num_recent_circs
;
1334 * A circuit was just forcibly closed. If there has been no recent network
1335 * activity at all, but this circuit was launched back when we thought the
1336 * network was live, increment the number of "nonlive" circuit timeouts.
1338 * This is used by circuit_build_times_network_check_live() to decide
1339 * if we should record the circuit build timeout or not.
1342 circuit_build_times_network_close(circuit_build_times_t
*cbt
,
1343 int did_onehop
, time_t start_time
)
1345 time_t now
= time(NULL
);
1347 * Check if this is a timeout that was for a circuit that spent its
1348 * entire existence during a time where we have had no network activity.
1350 if (cbt
->liveness
.network_last_live
< start_time
) {
1352 char last_live_buf
[ISO_TIME_LEN
+1];
1353 char start_time_buf
[ISO_TIME_LEN
+1];
1354 char now_buf
[ISO_TIME_LEN
+1];
1355 format_local_iso_time(last_live_buf
, cbt
->liveness
.network_last_live
);
1356 format_local_iso_time(start_time_buf
, start_time
);
1357 format_local_iso_time(now_buf
, now
);
1359 "Circuit somehow completed a hop while the network was "
1360 "not live. Network was last live at %s, but circuit launched "
1361 "at %s. It's now %s.", last_live_buf
, start_time_buf
,
1364 cbt
->liveness
.nonlive_timeouts
++;
1365 if (cbt
->liveness
.nonlive_timeouts
== 1) {
1367 "Tor has not observed any network activity for the past %d "
1368 "seconds. Disabling circuit build timeout recording.",
1369 (int)(now
- cbt
->liveness
.network_last_live
));
1372 "Got non-live timeout. Current count is: %d",
1373 cbt
->liveness
.nonlive_timeouts
);
1379 * When the network is not live, we do not record circuit build times.
1381 * The network is considered not live if there has been at least one
1382 * circuit build that began and ended (had its close_ms measurement
1383 * period expire) since we last received a cell.
1385 * Also has the side effect of rewinding the circuit time history
1386 * in the case of recent liveness changes.
1389 circuit_build_times_network_check_live(circuit_build_times_t
*cbt
)
1391 if (cbt
->liveness
.nonlive_timeouts
> 0) {
1399 * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
1400 * the past RECENT_CIRCUITS time out after the first hop. Used to detect
1401 * if the network connection has changed significantly, and if so,
1402 * resets our circuit build timeout to the default.
1404 * Also resets the entire timeout history in this case and causes us
1405 * to restart the process of building test circuits and estimating a
1409 circuit_build_times_network_check_changed(circuit_build_times_t
*cbt
)
1411 int total_build_times
= cbt
->total_build_times
;
1412 int timeout_count
=0;
1415 if (cbt
->liveness
.timeouts_after_firsthop
&&
1416 cbt
->liveness
.num_recent_circs
> 0) {
1417 /* how many of our recent circuits made it to the first hop but then
1419 for (i
= 0; i
< cbt
->liveness
.num_recent_circs
; i
++) {
1420 timeout_count
+= cbt
->liveness
.timeouts_after_firsthop
[i
];
1424 /* If 80% of our recent circuits are timing out after the first hop,
1425 * we need to re-estimate a new initial alpha and timeout. */
1426 if (timeout_count
< circuit_build_times_max_timeouts()) {
1430 circuit_build_times_reset(cbt
);
1431 if (cbt
->liveness
.timeouts_after_firsthop
&&
1432 cbt
->liveness
.num_recent_circs
> 0) {
1433 memset(cbt
->liveness
.timeouts_after_firsthop
, 0,
1434 sizeof(*cbt
->liveness
.timeouts_after_firsthop
)*
1435 cbt
->liveness
.num_recent_circs
);
1437 cbt
->liveness
.after_firsthop_idx
= 0;
1439 /* Check to see if this has happened before. If so, double the timeout
1440 * to give people on abysmally bad network connections a shot at access */
1441 if (cbt
->timeout_ms
>= circuit_build_times_get_initial_timeout()) {
1442 if (cbt
->timeout_ms
> INT32_MAX
/2 || cbt
->close_ms
> INT32_MAX
/2) {
1443 log_warn(LD_CIRC
, "Insanely large circuit build timeout value. "
1444 "(timeout = %fmsec, close = %fmsec)",
1445 cbt
->timeout_ms
, cbt
->close_ms
);
1447 cbt
->timeout_ms
*= 2;
1451 cbt
->close_ms
= cbt
->timeout_ms
1452 = circuit_build_times_get_initial_timeout();
1455 control_event_buildtimeout_set(cbt
, BUILDTIMEOUT_SET_EVENT_RESET
);
1458 "Your network connection speed appears to have changed. Resetting "
1459 "timeout to %lds after %d timeouts and %d buildtimes.",
1460 tor_lround(cbt
->timeout_ms
/1000), timeout_count
,
1467 * Count the number of timeouts in a set of cbt data.
1470 circuit_build_times_timeout_rate(const circuit_build_times_t
*cbt
)
1473 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
1474 if (cbt
->circuit_build_times
[i
] >= cbt
->timeout_ms
) {
1479 if (!cbt
->total_build_times
)
1482 return ((double)timeouts
)/cbt
->total_build_times
;
1486 * Count the number of closed circuits in a set of cbt data.
1489 circuit_build_times_close_rate(const circuit_build_times_t
*cbt
)
1492 for (i
= 0; i
< CBT_NCIRCUITS_TO_OBSERVE
; i
++) {
1493 if (cbt
->circuit_build_times
[i
] == CBT_BUILD_ABANDONED
) {
1498 if (!cbt
->total_build_times
)
1501 return ((double)closed
)/cbt
->total_build_times
;
1505 * Store a timeout as a synthetic value.
1507 * Returns true if the store was successful and we should possibly
1508 * update our timeout estimate.
1511 circuit_build_times_count_close(circuit_build_times_t
*cbt
,
1515 if (circuit_build_times_disabled()) {
1516 cbt
->close_ms
= cbt
->timeout_ms
1517 = circuit_build_times_get_initial_timeout();
1521 /* Record this force-close to help determine if the network is dead */
1522 circuit_build_times_network_close(cbt
, did_onehop
, start_time
);
1524 /* Only count timeouts if network is live.. */
1525 if (!circuit_build_times_network_check_live(cbt
)) {
1529 circuit_build_times_add_time(cbt
, CBT_BUILD_ABANDONED
);
1534 * Update timeout counts to determine if we need to expire
1535 * our build time history due to excessive timeouts.
1537 * We do not record any actual time values at this stage;
1538 * we are only interested in recording the fact that a timeout
1539 * happened. We record the time values via
1540 * circuit_build_times_count_close() and circuit_build_times_add_time().
1543 circuit_build_times_count_timeout(circuit_build_times_t
*cbt
,
1546 if (circuit_build_times_disabled()) {
1547 cbt
->close_ms
= cbt
->timeout_ms
1548 = circuit_build_times_get_initial_timeout();
1552 /* Register the fact that a timeout just occurred. */
1553 circuit_build_times_network_timeout(cbt
, did_onehop
);
1555 /* If there are a ton of timeouts, we should reset
1556 * the circuit build timeout. */
1557 circuit_build_times_network_check_changed(cbt
);
1561 * Estimate a new timeout based on history and set our timeout
1562 * variable accordingly.
1565 circuit_build_times_set_timeout_worker(circuit_build_times_t
*cbt
)
1567 build_time_t max_time
;
1568 if (!circuit_build_times_enough_to_compute(cbt
))
1571 if (!circuit_build_times_update_alpha(cbt
))
1574 cbt
->timeout_ms
= circuit_build_times_calculate_timeout(cbt
,
1575 circuit_build_times_quantile_cutoff());
1577 cbt
->close_ms
= circuit_build_times_calculate_timeout(cbt
,
1578 circuit_build_times_close_quantile());
1580 max_time
= circuit_build_times_max(cbt
);
1582 /* Sometimes really fast guard nodes give us such a steep curve
1583 * that this ends up being not that much greater than timeout_ms.
1584 * Make it be at least 1 min to handle this case. */
1585 cbt
->close_ms
= MAX(cbt
->close_ms
, circuit_build_times_initial_timeout());
1587 if (cbt
->timeout_ms
> max_time
) {
1589 "Circuit build timeout of %dms is beyond the maximum build "
1590 "time we have ever observed. Capping it to %dms.",
1591 (int)cbt
->timeout_ms
, max_time
);
1592 cbt
->timeout_ms
= max_time
;
1595 if (max_time
< INT32_MAX
/2 && cbt
->close_ms
> 2*max_time
) {
1597 "Circuit build measurement period of %dms is more than twice "
1598 "the maximum build time we have ever observed. Capping it to "
1599 "%dms.", (int)cbt
->close_ms
, 2*max_time
);
1600 cbt
->close_ms
= 2*max_time
;
1603 cbt
->have_computed_timeout
= 1;
1608 * Exposed function to compute a new timeout. Dispatches events and
1609 * also filters out extremely high timeout values.
1612 circuit_build_times_set_timeout(circuit_build_times_t
*cbt
)
1614 long prev_timeout
= tor_lround(cbt
->timeout_ms
/1000);
1615 double timeout_rate
;
1618 * Just return if we aren't using adaptive timeouts
1620 if (circuit_build_times_disabled())
1623 if (!circuit_build_times_set_timeout_worker(cbt
))
1626 if (cbt
->timeout_ms
< circuit_build_times_min_timeout()) {
1627 log_warn(LD_CIRC
, "Set buildtimeout to low value %fms. Setting to %dms",
1628 cbt
->timeout_ms
, circuit_build_times_min_timeout());
1629 cbt
->timeout_ms
= circuit_build_times_min_timeout();
1630 if (cbt
->close_ms
< cbt
->timeout_ms
) {
1631 /* This shouldn't happen because of MAX() in timeout_worker above,
1632 * but doing it just in case */
1633 cbt
->close_ms
= circuit_build_times_initial_timeout();
1637 control_event_buildtimeout_set(cbt
, BUILDTIMEOUT_SET_EVENT_COMPUTED
);
1639 timeout_rate
= circuit_build_times_timeout_rate(cbt
);
1641 if (prev_timeout
> tor_lround(cbt
->timeout_ms
/1000)) {
1643 "Based on %d circuit times, it looks like we don't need to "
1644 "wait so long for circuits to finish. We will now assume a "
1645 "circuit is too slow to use after waiting %ld seconds.",
1646 cbt
->total_build_times
,
1647 tor_lround(cbt
->timeout_ms
/1000));
1649 "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
1650 cbt
->timeout_ms
, cbt
->close_ms
, cbt
->Xm
, cbt
->alpha
,
1652 } else if (prev_timeout
< tor_lround(cbt
->timeout_ms
/1000)) {
1654 "Based on %d circuit times, it looks like we need to wait "
1655 "longer for circuits to finish. We will now assume a "
1656 "circuit is too slow to use after waiting %ld seconds.",
1657 cbt
->total_build_times
,
1658 tor_lround(cbt
->timeout_ms
/1000));
1660 "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
1661 cbt
->timeout_ms
, cbt
->close_ms
, cbt
->Xm
, cbt
->alpha
,
1665 "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f,"
1666 " r: %f) based on %d circuit times",
1667 tor_lround(cbt
->timeout_ms
/1000),
1668 cbt
->timeout_ms
, cbt
->close_ms
, cbt
->Xm
, cbt
->alpha
, timeout_rate
,
1669 cbt
->total_build_times
);
1673 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
1674 * and with the high bit specified by conn-\>circ_id_type, until we get
1675 * a circ_id that is not in use by any other circuit on that conn.
1677 * Return it, or 0 if can't get a unique circ_id.
1680 get_unique_circ_id_by_conn(or_connection_t
*conn
)
1682 circid_t test_circ_id
;
1683 circid_t attempts
=0;
1687 if (conn
->circ_id_type
== CIRC_ID_TYPE_NEITHER
) {
1688 log_warn(LD_BUG
, "Trying to pick a circuit ID for a connection from "
1689 "a client with no identity.");
1692 high_bit
= (conn
->circ_id_type
== CIRC_ID_TYPE_HIGHER
) ? 1<<15 : 0;
1694 /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
1695 * circID such that (high_bit|test_circ_id) is not already used. */
1696 test_circ_id
= conn
->next_circ_id
++;
1697 if (test_circ_id
== 0 || test_circ_id
>= 1<<15) {
1699 conn
->next_circ_id
= 2;
1701 if (++attempts
> 1<<15) {
1702 /* Make sure we don't loop forever if all circ_id's are used. This
1703 * matters because it's an external DoS opportunity.
1705 log_warn(LD_CIRC
,"No unused circ IDs. Failing.");
1708 test_circ_id
|= high_bit
;
1709 } while (circuit_id_in_use_on_orconn(test_circ_id
, conn
));
1710 return test_circ_id
;
1713 /** If <b>verbose</b> is false, allocate and return a comma-separated list of
1714 * the currently built elements of <b>circ</b>. If <b>verbose</b> is true, also
1715 * list information about link status in a more verbose format using spaces.
1716 * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
1717 * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
1721 circuit_list_path_impl(origin_circuit_t
*circ
, int verbose
, int verbose_names
)
1724 smartlist_t
*elements
;
1725 const char *states
[] = {"closed", "waiting for keys", "open"};
1728 elements
= smartlist_new();
1731 const char *nickname
= build_state_get_exit_nickname(circ
->build_state
);
1732 smartlist_add_asprintf(elements
, "%s%s circ (length %d%s%s):",
1733 circ
->build_state
->is_internal
? "internal" : "exit",
1734 circ
->build_state
->need_uptime
? " (high-uptime)" : "",
1735 circ
->build_state
->desired_path_len
,
1736 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" : ", last hop ",
1737 circ
->_base
.state
== CIRCUIT_STATE_OPEN
? "" :
1738 (nickname
?nickname
:"*unnamed*"));
1748 if (!verbose
&& hop
->state
!= CPATH_STATE_OPEN
)
1750 if (!hop
->extend_info
)
1752 id
= hop
->extend_info
->identity_digest
;
1753 if (verbose_names
) {
1754 elt
= tor_malloc(MAX_VERBOSE_NICKNAME_LEN
+1);
1755 if ((node
= node_get_by_id(id
))) {
1756 node_get_verbose_nickname(node
, elt
);
1757 } else if (is_legal_nickname(hop
->extend_info
->nickname
)) {
1759 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
1760 elt
[HEX_DIGEST_LEN
+1]= '~';
1761 strlcpy(elt
+HEX_DIGEST_LEN
+2,
1762 hop
->extend_info
->nickname
, MAX_NICKNAME_LEN
+1);
1765 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
1767 } else { /* ! verbose_names */
1768 node
= node_get_by_id(id
);
1769 if (node
&& node_is_named(node
)) {
1770 elt
= tor_strdup(node_get_nickname(node
));
1772 elt
= tor_malloc(HEX_DIGEST_LEN
+2);
1774 base16_encode(elt
+1, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
1779 tor_assert(hop
->state
<= 2);
1780 smartlist_add_asprintf(elements
,"%s(%s)",elt
,states
[hop
->state
]);
1783 smartlist_add(elements
, elt
);
1786 } while (hop
!= circ
->cpath
);
1788 s
= smartlist_join_strings(elements
, verbose
?" ":",", 0, NULL
);
1789 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
1790 smartlist_free(elements
);
1794 /** If <b>verbose</b> is false, allocate and return a comma-separated
1795 * list of the currently built elements of <b>circ</b>. If
1796 * <b>verbose</b> is true, also list information about link status in
1797 * a more verbose format using spaces.
1800 circuit_list_path(origin_circuit_t
*circ
, int verbose
)
1802 return circuit_list_path_impl(circ
, verbose
, 0);
1805 /** Allocate and return a comma-separated list of the currently built elements
1806 * of <b>circ</b>, giving each as a verbose nickname.
1809 circuit_list_path_for_controller(origin_circuit_t
*circ
)
1811 return circuit_list_path_impl(circ
, 0, 1);
1814 /** Log, at severity <b>severity</b>, the nicknames of each router in
1815 * <b>circ</b>'s cpath. Also log the length of the cpath, and the intended
1819 circuit_log_path(int severity
, unsigned int domain
, origin_circuit_t
*circ
)
1821 char *s
= circuit_list_path(circ
,1);
1822 tor_log(severity
,domain
,"%s",s
);
1826 /** Tell the rep(utation)hist(ory) module about the status of the links
1827 * in <b>circ</b>. Hops that have become OPEN are marked as successfully
1828 * extended; the _first_ hop that isn't open (if any) is marked as
1831 /* XXXX Someday we should learn from OR circuits too. */
1833 circuit_rep_hist_note_result(origin_circuit_t
*circ
)
1836 const char *prev_digest
= NULL
;
1838 if (!hop
) /* circuit hasn't started building yet. */
1840 if (server_mode(get_options())) {
1841 const routerinfo_t
*me
= router_get_my_routerinfo();
1844 prev_digest
= me
->cache_info
.identity_digest
;
1847 const node_t
*node
= node_get_by_id(hop
->extend_info
->identity_digest
);
1848 if (node
) { /* Why do we check this? We know the identity. -NM XXXX */
1850 if (hop
->state
== CPATH_STATE_OPEN
)
1851 rep_hist_note_extend_succeeded(prev_digest
, node
->identity
);
1853 rep_hist_note_extend_failed(prev_digest
, node
->identity
);
1857 prev_digest
= node
->identity
;
1862 } while (hop
!=circ
->cpath
);
1865 /** Pick all the entries in our cpath. Stop and return 0 when we're
1866 * happy, or return -1 if an error occurs. */
1868 onion_populate_cpath(origin_circuit_t
*circ
)
1872 r
= onion_extend_cpath(circ
);
1874 log_info(LD_CIRC
,"Generating cpath hop failed.");
1879 return 0; /* if r == 1 */
1882 /** Create and return a new origin circuit. Initialize its purpose and
1883 * build-state based on our arguments. The <b>flags</b> argument is a
1884 * bitfield of CIRCLAUNCH_* flags. */
1886 origin_circuit_init(uint8_t purpose
, int flags
)
1888 /* sets circ->p_circ_id and circ->p_conn */
1889 origin_circuit_t
*circ
= origin_circuit_new();
1890 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OR_WAIT
);
1891 circ
->build_state
= tor_malloc_zero(sizeof(cpath_build_state_t
));
1892 circ
->build_state
->onehop_tunnel
=
1893 ((flags
& CIRCLAUNCH_ONEHOP_TUNNEL
) ? 1 : 0);
1894 circ
->build_state
->need_uptime
=
1895 ((flags
& CIRCLAUNCH_NEED_UPTIME
) ? 1 : 0);
1896 circ
->build_state
->need_capacity
=
1897 ((flags
& CIRCLAUNCH_NEED_CAPACITY
) ? 1 : 0);
1898 circ
->build_state
->is_internal
=
1899 ((flags
& CIRCLAUNCH_IS_INTERNAL
) ? 1 : 0);
1900 circ
->_base
.purpose
= purpose
;
1904 /** Build a new circuit for <b>purpose</b>. If <b>exit</b>
1905 * is defined, then use that as your exit router, else choose a suitable
1908 * Also launch a connection to the first OR in the chosen path, if
1909 * it's not open already.
1912 circuit_establish_circuit(uint8_t purpose
, extend_info_t
*exit
, int flags
)
1914 origin_circuit_t
*circ
;
1917 circ
= origin_circuit_init(purpose
, flags
);
1919 if (onion_pick_cpath_exit(circ
, exit
) < 0 ||
1920 onion_populate_cpath(circ
) < 0) {
1921 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_NOPATH
);
1925 control_event_circuit_status(circ
, CIRC_EVENT_LAUNCHED
, 0);
1927 if ((err_reason
= circuit_handle_first_hop(circ
)) < 0) {
1928 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
1934 /** Start establishing the first hop of our circuit. Figure out what
1935 * OR we should connect to, and if necessary start the connection to
1936 * it. If we're already connected, then send the 'create' cell.
1937 * Return 0 for ok, -reason if circ should be marked-for-close. */
1939 circuit_handle_first_hop(origin_circuit_t
*circ
)
1941 crypt_path_t
*firsthop
;
1942 or_connection_t
*n_conn
;
1944 const char *msg
= NULL
;
1945 int should_launch
= 0;
1947 firsthop
= onion_next_hop_in_cpath(circ
->cpath
);
1948 tor_assert(firsthop
);
1949 tor_assert(firsthop
->extend_info
);
1951 /* now see if we're already connected to the first OR in 'route' */
1952 log_debug(LD_CIRC
,"Looking for firsthop '%s:%u'",
1953 fmt_addr(&firsthop
->extend_info
->addr
),
1954 firsthop
->extend_info
->port
);
1956 n_conn
= connection_or_get_for_extend(firsthop
->extend_info
->identity_digest
,
1957 &firsthop
->extend_info
->addr
,
1962 /* not currently connected in a useful way. */
1963 log_info(LD_CIRC
, "Next router is %s: %s",
1964 safe_str_client(extend_info_describe(firsthop
->extend_info
)),
1966 circ
->_base
.n_hop
= extend_info_dup(firsthop
->extend_info
);
1968 if (should_launch
) {
1969 if (circ
->build_state
->onehop_tunnel
)
1970 control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR
, 0);
1971 n_conn
= connection_or_connect(&firsthop
->extend_info
->addr
,
1972 firsthop
->extend_info
->port
,
1973 firsthop
->extend_info
->identity_digest
);
1974 if (!n_conn
) { /* connect failed, forget the whole thing */
1975 log_info(LD_CIRC
,"connect to firsthop failed. Closing.");
1976 return -END_CIRC_REASON_CONNECTFAILED
;
1980 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
1981 /* return success. The onion/circuit/etc will be taken care of
1982 * automatically (may already have been) whenever n_conn reaches
1983 * OR_CONN_STATE_OPEN.
1986 } else { /* it's already open. use it. */
1987 tor_assert(!circ
->_base
.n_hop
);
1988 circ
->_base
.n_conn
= n_conn
;
1989 log_debug(LD_CIRC
,"Conn open. Delivering first onion skin.");
1990 if ((err_reason
= circuit_send_next_onion_skin(circ
)) < 0) {
1991 log_info(LD_CIRC
,"circuit_send_next_onion_skin failed.");
1998 /** Find any circuits that are waiting on <b>or_conn</b> to become
1999 * open and get them to send their create cells forward.
2001 * Status is 1 if connect succeeded, or 0 if connect failed.
2004 circuit_n_conn_done(or_connection_t
*or_conn
, int status
)
2006 smartlist_t
*pending_circs
;
2009 log_debug(LD_CIRC
,"or_conn to %s/%s, status=%d",
2010 or_conn
->nickname
? or_conn
->nickname
: "NULL",
2011 or_conn
->_base
.address
, status
);
2013 pending_circs
= smartlist_new();
2014 circuit_get_all_pending_on_or_conn(pending_circs
, or_conn
);
2016 SMARTLIST_FOREACH_BEGIN(pending_circs
, circuit_t
*, circ
)
2018 /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
2019 * leaving them in in case it's possible for the status of a circuit to
2020 * change as we're going down the list. */
2021 if (circ
->marked_for_close
|| circ
->n_conn
|| !circ
->n_hop
||
2022 circ
->state
!= CIRCUIT_STATE_OR_WAIT
)
2025 if (tor_digest_is_zero(circ
->n_hop
->identity_digest
)) {
2026 /* Look at addr/port. This is an unkeyed connection. */
2027 if (!tor_addr_eq(&circ
->n_hop
->addr
, &or_conn
->_base
.addr
) ||
2028 circ
->n_hop
->port
!= or_conn
->_base
.port
)
2031 /* We expected a key. See if it's the right one. */
2032 if (tor_memneq(or_conn
->identity_digest
,
2033 circ
->n_hop
->identity_digest
, DIGEST_LEN
))
2036 if (!status
) { /* or_conn failed; close circ */
2037 log_info(LD_CIRC
,"or_conn failed. Closing circ.");
2038 circuit_mark_for_close(circ
, END_CIRC_REASON_OR_CONN_CLOSED
);
2041 log_debug(LD_CIRC
, "Found circ, sending create cell.");
2042 /* circuit_deliver_create_cell will set n_circ_id and add us to
2043 * orconn_circuid_circuit_map, so we don't need to call
2044 * set_circid_orconn here. */
2045 circ
->n_conn
= or_conn
;
2046 extend_info_free(circ
->n_hop
);
2049 if (CIRCUIT_IS_ORIGIN(circ
)) {
2051 circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ
))) < 0) {
2053 "send_next_onion_skin failed; circuit marked for closing.");
2054 circuit_mark_for_close(circ
, -err_reason
);
2056 /* XXX could this be bad, eg if next_onion_skin failed because conn
2060 /* pull the create cell out of circ->onionskin, and send it */
2061 tor_assert(circ
->n_conn_onionskin
);
2062 if (circuit_deliver_create_cell(circ
,CELL_CREATE
,
2063 circ
->n_conn_onionskin
)<0) {
2064 circuit_mark_for_close(circ
, END_CIRC_REASON_RESOURCELIMIT
);
2067 tor_free(circ
->n_conn_onionskin
);
2068 circuit_set_state(circ
, CIRCUIT_STATE_OPEN
);
2071 SMARTLIST_FOREACH_END(circ
);
2073 smartlist_free(pending_circs
);
2076 /** Find a new circid that isn't currently in use on the circ->n_conn
2078 * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
2079 * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
2081 * Return -1 if we failed to find a suitable circid, else return 0.
2084 circuit_deliver_create_cell(circuit_t
*circ
, uint8_t cell_type
,
2085 const char *payload
)
2091 tor_assert(circ
->n_conn
);
2092 tor_assert(payload
);
2093 tor_assert(cell_type
== CELL_CREATE
|| cell_type
== CELL_CREATE_FAST
);
2095 id
= get_unique_circ_id_by_conn(circ
->n_conn
);
2097 log_warn(LD_CIRC
,"failed to get unique circID.");
2100 log_debug(LD_CIRC
,"Chosen circID %u.", id
);
2101 circuit_set_n_circid_orconn(circ
, id
, circ
->n_conn
);
2103 memset(&cell
, 0, sizeof(cell_t
));
2104 cell
.command
= cell_type
;
2105 cell
.circ_id
= circ
->n_circ_id
;
2107 memcpy(cell
.payload
, payload
, ONIONSKIN_CHALLENGE_LEN
);
2108 append_cell_to_circuit_queue(circ
, circ
->n_conn
, &cell
,
2109 CELL_DIRECTION_OUT
, 0);
2111 if (CIRCUIT_IS_ORIGIN(circ
)) {
2112 /* mark it so it gets better rate limiting treatment. */
2113 circ
->n_conn
->client_used
= time(NULL
);
2119 /** We've decided to start our reachability testing. If all
2120 * is set, log this to the user. Return 1 if we did, or 0 if
2121 * we chose not to log anything. */
2123 inform_testing_reachability(void)
2126 const routerinfo_t
*me
= router_get_my_routerinfo();
2129 control_event_server_status(LOG_NOTICE
,
2130 "CHECKING_REACHABILITY ORADDRESS=%s:%d",
2131 me
->address
, me
->or_port
);
2133 tor_snprintf(dirbuf
, sizeof(dirbuf
), " and DirPort %s:%d",
2134 me
->address
, me
->dir_port
);
2135 control_event_server_status(LOG_NOTICE
,
2136 "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
2137 me
->address
, me
->dir_port
);
2139 log_notice(LD_OR
, "Now checking whether ORPort %s:%d%s %s reachable... "
2140 "(this may take up to %d minutes -- look for log "
2141 "messages indicating success)",
2142 me
->address
, me
->or_port
,
2143 me
->dir_port
? dirbuf
: "",
2144 me
->dir_port
? "are" : "is",
2145 TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT
/60);
2150 /** Return true iff we should send a create_fast cell to start building a given
2153 should_use_create_fast_for_circuit(origin_circuit_t
*circ
)
2155 const or_options_t
*options
= get_options();
2156 tor_assert(circ
->cpath
);
2157 tor_assert(circ
->cpath
->extend_info
);
2159 if (!circ
->cpath
->extend_info
->onion_key
)
2160 return 1; /* our hand is forced: only a create_fast will work. */
2161 if (!options
->FastFirstHopPK
)
2162 return 0; /* we prefer to avoid create_fast */
2163 if (public_server_mode(options
)) {
2164 /* We're a server, and we know an onion key. We can choose.
2165 * Prefer to blend our circuit into the other circuits we are
2166 * creating on behalf of others. */
2173 /** Return true if <b>circ</b> is the type of circuit we want to count
2174 * timeouts from. In particular, we want it to have not completed yet
2175 * (already completing indicates we cannibalized it), and we want it to
2176 * have exactly three hops.
2179 circuit_timeout_want_to_count_circ(origin_circuit_t
*circ
)
2181 return !circ
->has_opened
2182 && circ
->build_state
->desired_path_len
== DEFAULT_ROUTE_LEN
;
2185 /** This is the backbone function for building circuits.
2187 * If circ's first hop is closed, then we need to build a create
2188 * cell and send it forward.
2190 * Otherwise, we need to build a relay extend cell and send it
2193 * Return -reason if we want to tear down circ, else return 0.
2196 circuit_send_next_onion_skin(origin_circuit_t
*circ
)
2200 char payload
[2+4+DIGEST_LEN
+ONIONSKIN_CHALLENGE_LEN
];
2206 if (circ
->cpath
->state
== CPATH_STATE_CLOSED
) {
2209 log_debug(LD_CIRC
,"First skin; sending create cell.");
2210 if (circ
->build_state
->onehop_tunnel
)
2211 control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE
, 0);
2213 control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE
, 0);
2215 node
= node_get_by_id(circ
->_base
.n_conn
->identity_digest
);
2216 fast
= should_use_create_fast_for_circuit(circ
);
2218 /* We are an OR and we know the right onion key: we should
2219 * send an old slow create cell.
2221 cell_type
= CELL_CREATE
;
2222 if (onion_skin_create(circ
->cpath
->extend_info
->onion_key
,
2223 &(circ
->cpath
->dh_handshake_state
),
2225 log_warn(LD_CIRC
,"onion_skin_create (first hop) failed.");
2226 return - END_CIRC_REASON_INTERNAL
;
2228 note_request("cell: create", 1);
2230 /* We are not an OR, and we're building the first hop of a circuit to a
2231 * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
2232 * and a DH operation. */
2233 cell_type
= CELL_CREATE_FAST
;
2234 memset(payload
, 0, sizeof(payload
));
2235 crypto_rand((char*) circ
->cpath
->fast_handshake_state
,
2236 sizeof(circ
->cpath
->fast_handshake_state
));
2237 memcpy(payload
, circ
->cpath
->fast_handshake_state
,
2238 sizeof(circ
->cpath
->fast_handshake_state
));
2239 note_request("cell: create fast", 1);
2242 if (circuit_deliver_create_cell(TO_CIRCUIT(circ
), cell_type
, payload
) < 0)
2243 return - END_CIRC_REASON_RESOURCELIMIT
;
2245 circ
->cpath
->state
= CPATH_STATE_AWAITING_KEYS
;
2246 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
2247 log_info(LD_CIRC
,"First hop: finished sending %s cell to '%s'",
2248 fast
? "CREATE_FAST" : "CREATE",
2249 node
? node_describe(node
) : "<unnamed>");
2251 tor_assert(circ
->cpath
->state
== CPATH_STATE_OPEN
);
2252 tor_assert(circ
->_base
.state
== CIRCUIT_STATE_BUILDING
);
2253 log_debug(LD_CIRC
,"starting to send subsequent skin.");
2254 hop
= onion_next_hop_in_cpath(circ
->cpath
);
2256 /* done building the circuit. whew. */
2257 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
2258 if (circuit_timeout_want_to_count_circ(circ
)) {
2261 tor_gettimeofday(&end
);
2262 timediff
= tv_mdiff(&circ
->_base
.timestamp_created
, &end
);
2265 * If the circuit build time is much greater than we would have cut
2266 * it off at, we probably had a suspend event along this codepath,
2267 * and we should discard the value.
2269 if (timediff
< 0 || timediff
> 2*circ_times
.close_ms
+1000) {
2270 log_notice(LD_CIRC
, "Strange value for circuit build time: %ldmsec. "
2271 "Assuming clock jump. Purpose %d (%s)", timediff
,
2272 circ
->_base
.purpose
,
2273 circuit_purpose_to_string(circ
->_base
.purpose
));
2274 } else if (!circuit_build_times_disabled()) {
2275 /* Only count circuit times if the network is live */
2276 if (circuit_build_times_network_check_live(&circ_times
)) {
2277 circuit_build_times_add_time(&circ_times
, (build_time_t
)timediff
);
2278 circuit_build_times_set_timeout(&circ_times
);
2281 if (circ
->_base
.purpose
!= CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
) {
2282 circuit_build_times_network_circ_success(&circ_times
);
2286 log_info(LD_CIRC
,"circuit built!");
2287 circuit_reset_failure_count(0);
2288 /* Don't count cannibalized or onehop circs for path bias */
2289 if (circ
->build_state
->onehop_tunnel
|| circ
->has_opened
) {
2290 control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS
, 0);
2292 entry_guard_t
*guard
=
2293 entry_guard_get_by_id_digest(circ
->_base
.n_conn
->identity_digest
);
2296 guard
->circuit_successes
++;
2298 log_info(LD_PROTOCOL
, "Got success count %u/%u for guard %s=%s",
2299 guard
->circuit_successes
, guard
->first_hops
,
2300 guard
->nickname
, hex_str(guard
->identity
, DIGEST_LEN
));
2302 if (guard
->first_hops
< guard
->circuit_successes
) {
2303 log_warn(LD_BUG
, "Unexpectedly high circuit_successes (%u/%u) "
2305 guard
->circuit_successes
, guard
->first_hops
,
2310 if (!can_complete_circuit
&& !circ
->build_state
->onehop_tunnel
) {
2311 const or_options_t
*options
= get_options();
2312 can_complete_circuit
=1;
2313 /* FFFF Log a count of known routers here */
2314 log_notice(LD_GENERAL
,
2315 "Tor has successfully opened a circuit. "
2316 "Looks like client functionality is working.");
2317 control_event_bootstrap(BOOTSTRAP_STATUS_DONE
, 0);
2318 control_event_client_status(LOG_NOTICE
, "CIRCUIT_ESTABLISHED");
2319 clear_broken_connection_map(1);
2320 if (server_mode(options
) && !check_whether_orport_reachable()) {
2321 inform_testing_reachability();
2322 consider_testing_reachability(1, 1);
2325 circuit_rep_hist_note_result(circ
);
2326 circuit_has_opened(circ
); /* do other actions as necessary */
2328 /* We're done with measurement circuits here. Just close them */
2329 if (circ
->_base
.purpose
== CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
)
2330 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_FINISHED
);
2334 if (tor_addr_family(&hop
->extend_info
->addr
) != AF_INET
) {
2335 log_warn(LD_BUG
, "Trying to extend to a non-IPv4 address.");
2336 return - END_CIRC_REASON_INTERNAL
;
2339 set_uint32(payload
, tor_addr_to_ipv4n(&hop
->extend_info
->addr
));
2340 set_uint16(payload
+4, htons(hop
->extend_info
->port
));
2342 onionskin
= payload
+2+4;
2343 memcpy(payload
+2+4+ONIONSKIN_CHALLENGE_LEN
,
2344 hop
->extend_info
->identity_digest
, DIGEST_LEN
);
2345 payload_len
= 2+4+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
;
2347 if (onion_skin_create(hop
->extend_info
->onion_key
,
2348 &(hop
->dh_handshake_state
), onionskin
) < 0) {
2349 log_warn(LD_CIRC
,"onion_skin_create failed.");
2350 return - END_CIRC_REASON_INTERNAL
;
2353 log_info(LD_CIRC
,"Sending extend relay cell.");
2354 note_request("cell: extend", 1);
2355 /* send it to hop->prev, because it will transfer
2356 * it to a create cell and then send to hop */
2357 if (relay_send_command_from_edge(0, TO_CIRCUIT(circ
),
2358 RELAY_COMMAND_EXTEND
,
2359 payload
, payload_len
, hop
->prev
) < 0)
2360 return 0; /* circuit is closed */
2362 hop
->state
= CPATH_STATE_AWAITING_KEYS
;
2367 /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
2368 * something has also gone wrong with our network: notify the user,
2369 * and abandon all not-yet-used circuits. */
2371 circuit_note_clock_jumped(int seconds_elapsed
)
2373 int severity
= server_mode(get_options()) ? LOG_WARN
: LOG_NOTICE
;
2374 tor_log(severity
, LD_GENERAL
, "Your system clock just jumped %d seconds %s; "
2375 "assuming established circuits no longer work.",
2376 seconds_elapsed
>=0 ? seconds_elapsed
: -seconds_elapsed
,
2377 seconds_elapsed
>=0 ? "forward" : "backward");
2378 control_event_general_status(LOG_WARN
, "CLOCK_JUMPED TIME=%d",
2380 can_complete_circuit
=0; /* so it'll log when it works again */
2381 control_event_client_status(severity
, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
2383 circuit_mark_all_unused_circs();
2384 circuit_expire_all_dirty_circs();
2387 /** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
2388 * skin and identity digest for the next hop. If we're already connected,
2389 * pass the onion skin to the next hop using a create cell; otherwise
2390 * launch a new OR connection, and <b>circ</b> will notice when the
2391 * connection succeeds or fails.
2393 * Return -1 if we want to warn and tear down the circuit, else return 0.
2396 circuit_extend(cell_t
*cell
, circuit_t
*circ
)
2398 or_connection_t
*n_conn
;
2401 char *id_digest
=NULL
;
2405 const char *msg
= NULL
;
2406 int should_launch
= 0;
2409 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2410 "n_conn already set. Bug/attack. Closing.");
2414 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2415 "conn to next hop already launched. Bug/attack. Closing.");
2419 if (!server_mode(get_options())) {
2420 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2421 "Got an extend cell, but running as a client. Closing.");
2425 relay_header_unpack(&rh
, cell
->payload
);
2427 if (rh
.length
< 4+2+ONIONSKIN_CHALLENGE_LEN
+DIGEST_LEN
) {
2428 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2429 "Wrong length %d on extend cell. Closing circuit.",
2434 n_addr32
= ntohl(get_uint32(cell
->payload
+RELAY_HEADER_SIZE
));
2435 n_port
= ntohs(get_uint16(cell
->payload
+RELAY_HEADER_SIZE
+4));
2436 onionskin
= (char*) cell
->payload
+RELAY_HEADER_SIZE
+4+2;
2437 id_digest
= (char*) cell
->payload
+RELAY_HEADER_SIZE
+4+2+
2438 ONIONSKIN_CHALLENGE_LEN
;
2439 tor_addr_from_ipv4h(&n_addr
, n_addr32
);
2441 if (!n_port
|| !n_addr32
) {
2442 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2443 "Client asked me to extend to zero destination port or addr.");
2447 /* Check if they asked us for 0000..0000. We support using
2448 * an empty fingerprint for the first hop (e.g. for a bridge relay),
2449 * but we don't want to let people send us extend cells for empty
2450 * fingerprints -- a) because it opens the user up to a mitm attack,
2451 * and b) because it lets an attacker force the relay to hold open a
2452 * new TLS connection for each extend request. */
2453 if (tor_digest_is_zero(id_digest
)) {
2454 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2455 "Client asked me to extend without specifying an id_digest.");
2459 /* Next, check if we're being asked to connect to the hop that the
2460 * extend cell came from. There isn't any reason for that, and it can
2461 * assist circular-path attacks. */
2462 if (tor_memeq(id_digest
, TO_OR_CIRCUIT(circ
)->p_conn
->identity_digest
,
2464 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
2465 "Client asked me to extend back to the previous hop.");
2469 n_conn
= connection_or_get_for_extend(id_digest
,
2475 log_debug(LD_CIRC
|LD_OR
,"Next router (%s:%d): %s",
2476 fmt_addr(&n_addr
), (int)n_port
, msg
?msg
:"????");
2478 circ
->n_hop
= extend_info_alloc(NULL
/*nickname*/,
2483 circ
->n_conn_onionskin
= tor_malloc(ONIONSKIN_CHALLENGE_LEN
);
2484 memcpy(circ
->n_conn_onionskin
, onionskin
, ONIONSKIN_CHALLENGE_LEN
);
2485 circuit_set_state(circ
, CIRCUIT_STATE_OR_WAIT
);
2487 if (should_launch
) {
2488 /* we should try to open a connection */
2489 n_conn
= connection_or_connect(&n_addr
, n_port
, id_digest
);
2491 log_info(LD_CIRC
,"Launching n_conn failed. Closing circuit.");
2492 circuit_mark_for_close(circ
, END_CIRC_REASON_CONNECTFAILED
);
2495 log_debug(LD_CIRC
,"connecting in progress (or finished). Good.");
2497 /* return success. The onion/circuit/etc will be taken care of
2498 * automatically (may already have been) whenever n_conn reaches
2499 * OR_CONN_STATE_OPEN.
2504 tor_assert(!circ
->n_hop
); /* Connection is already established. */
2505 circ
->n_conn
= n_conn
;
2506 log_debug(LD_CIRC
,"n_conn is %s:%u",
2507 n_conn
->_base
.address
,n_conn
->_base
.port
);
2509 if (circuit_deliver_create_cell(circ
, CELL_CREATE
, onionskin
) < 0)
2514 /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
2515 * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
2517 * - 20 to initialize f_digest
2518 * - 20 to initialize b_digest
2519 * - 16 to key f_crypto
2520 * - 16 to key b_crypto
2522 * (If 'reverse' is true, then f_XX and b_XX are swapped.)
2525 circuit_init_cpath_crypto(crypt_path_t
*cpath
, const char *key_data
,
2528 crypto_digest_t
*tmp_digest
;
2529 crypto_cipher_t
*tmp_crypto
;
2532 tor_assert(key_data
);
2533 tor_assert(!(cpath
->f_crypto
|| cpath
->b_crypto
||
2534 cpath
->f_digest
|| cpath
->b_digest
));
2536 cpath
->f_digest
= crypto_digest_new();
2537 crypto_digest_add_bytes(cpath
->f_digest
, key_data
, DIGEST_LEN
);
2538 cpath
->b_digest
= crypto_digest_new();
2539 crypto_digest_add_bytes(cpath
->b_digest
, key_data
+DIGEST_LEN
, DIGEST_LEN
);
2541 if (!(cpath
->f_crypto
=
2542 crypto_cipher_new(key_data
+(2*DIGEST_LEN
)))) {
2543 log_warn(LD_BUG
,"Forward cipher initialization failed.");
2546 if (!(cpath
->b_crypto
=
2547 crypto_cipher_new(key_data
+(2*DIGEST_LEN
)+CIPHER_KEY_LEN
))) {
2548 log_warn(LD_BUG
,"Backward cipher initialization failed.");
2553 tmp_digest
= cpath
->f_digest
;
2554 cpath
->f_digest
= cpath
->b_digest
;
2555 cpath
->b_digest
= tmp_digest
;
2556 tmp_crypto
= cpath
->f_crypto
;
2557 cpath
->f_crypto
= cpath
->b_crypto
;
2558 cpath
->b_crypto
= tmp_crypto
;
2564 /** The minimum number of first hop completions before we start
2565 * thinking about warning about path bias and dropping guards */
2567 pathbias_get_min_circs(const or_options_t
*options
)
2569 #define DFLT_PATH_BIAS_MIN_CIRC 20
2570 if (options
->PathBiasCircThreshold
>= 5)
2571 return options
->PathBiasCircThreshold
;
2573 return networkstatus_get_param(NULL
, "pb_mincircs",
2574 DFLT_PATH_BIAS_MIN_CIRC
,
2579 pathbias_get_notice_rate(const or_options_t
*options
)
2581 #define DFLT_PATH_BIAS_NOTICE_PCT 40
2582 if (options
->PathBiasNoticeRate
>= 0.0)
2583 return options
->PathBiasNoticeRate
;
2585 return networkstatus_get_param(NULL
, "pb_noticepct",
2586 DFLT_PATH_BIAS_NOTICE_PCT
, 0, 100)/100.0;
2590 pathbias_get_disable_rate(const or_options_t
*options
)
2592 // XXX: This needs tuning based on use + experimentation before we set it
2593 #define DFLT_PATH_BIAS_DISABLE_PCT 0
2594 if (options
->PathBiasDisableRate
>= 0.0)
2595 return options
->PathBiasDisableRate
;
2597 return networkstatus_get_param(NULL
, "pb_disablepct",
2598 DFLT_PATH_BIAS_DISABLE_PCT
, 0, 100)/100.0;
2602 pathbias_get_scale_threshold(const or_options_t
*options
)
2604 #define DFLT_PATH_BIAS_SCALE_THRESHOLD 200
2605 if (options
->PathBiasScaleThreshold
>= 2)
2606 return options
->PathBiasScaleThreshold
;
2608 return networkstatus_get_param(NULL
, "pb_scalecircs",
2609 DFLT_PATH_BIAS_SCALE_THRESHOLD
, 10,
2614 pathbias_get_scale_factor(const or_options_t
*options
)
2616 #define DFLT_PATH_BIAS_SCALE_FACTOR 4
2617 if (options
->PathBiasScaleFactor
>= 1)
2618 return options
->PathBiasScaleFactor
;
2620 return networkstatus_get_param(NULL
, "pb_scalefactor",
2621 DFLT_PATH_BIAS_SCALE_THRESHOLD
, 1, INT32_MAX
);
2624 /** Increment the number of times we successfully extended a circuit to
2625 * 'guard', first checking if the failure rate is high enough that we should
2626 * eliminate the guard. Return -1 if the guard looks no good; return 0 if the
2627 * guard looks fine. */
2629 entry_guard_inc_first_hop_count(entry_guard_t
*guard
)
2631 const or_options_t
*options
= get_options();
2633 entry_guards_changed();
2635 if (guard
->first_hops
> (unsigned)pathbias_get_min_circs(options
)) {
2636 /* Note: We rely on the < comparison here to allow us to set a 0
2637 * rate and disable the feature entirely. If refactoring, don't
2639 if (guard
->circuit_successes
/((double)guard
->first_hops
)
2640 < pathbias_get_disable_rate(options
)) {
2642 log_warn(LD_PROTOCOL
,
2643 "Extremely low circuit success rate %u/%u for guard %s=%s. "
2644 "This might indicate an attack, or a bug.",
2645 guard
->circuit_successes
, guard
->first_hops
, guard
->nickname
,
2646 hex_str(guard
->identity
, DIGEST_LEN
));
2648 guard
->path_bias_disabled
= 1;
2649 guard
->bad_since
= approx_time();
2651 } else if (guard
->circuit_successes
/((double)guard
->first_hops
)
2652 < pathbias_get_notice_rate(options
)
2653 && !guard
->path_bias_notice
) {
2654 guard
->path_bias_notice
= 1;
2655 log_notice(LD_PROTOCOL
,
2656 "Low circuit success rate %u/%u for guard %s=%s.",
2657 guard
->circuit_successes
, guard
->first_hops
, guard
->nickname
,
2658 hex_str(guard
->identity
, DIGEST_LEN
));
2662 /* If we get a ton of circuits, just scale everything down */
2663 if (guard
->first_hops
> (unsigned)pathbias_get_scale_threshold(options
)) {
2664 const int scale_factor
= pathbias_get_scale_factor(options
);
2665 guard
->first_hops
/= scale_factor
;
2666 guard
->circuit_successes
/= scale_factor
;
2668 guard
->first_hops
++;
2669 log_info(LD_PROTOCOL
, "Got success count %u/%u for guard %s",
2670 guard
->circuit_successes
, guard
->first_hops
, guard
->nickname
);
2674 /** A created or extended cell came back to us on the circuit, and it included
2675 * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body
2676 * contains (the second DH key, plus KH). If <b>reply_type</b> is
2677 * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
2679 * Calculate the appropriate keys and digests, make sure KH is
2680 * correct, and initialize this hop of the cpath.
2682 * Return - reason if we want to mark circ for close, else return 0.
2685 circuit_finish_handshake(origin_circuit_t
*circ
, uint8_t reply_type
,
2686 const uint8_t *reply
)
2688 char keys
[CPATH_KEY_MATERIAL_LEN
];
2691 if (circ
->cpath
->state
== CPATH_STATE_AWAITING_KEYS
) {
2693 /* Don't count cannibalized or onehop circs for path bias */
2694 if (!circ
->has_opened
&& !circ
->build_state
->onehop_tunnel
) {
2695 entry_guard_t
*guard
;
2697 guard
= entry_guard_get_by_id_digest(
2698 circ
->_base
.n_conn
->identity_digest
);
2700 if (entry_guard_inc_first_hop_count(guard
) < 0) {
2701 /* Bogus guard; we already warned. */
2702 return -END_CIRC_REASON_TORPROTOCOL
;
2707 hop
= onion_next_hop_in_cpath(circ
->cpath
);
2708 if (!hop
) { /* got an extended when we're all done? */
2709 log_warn(LD_PROTOCOL
,"got extended when circ already built? Closing.");
2710 return - END_CIRC_REASON_TORPROTOCOL
;
2713 tor_assert(hop
->state
== CPATH_STATE_AWAITING_KEYS
);
2715 if (reply_type
== CELL_CREATED
&& hop
->dh_handshake_state
) {
2716 if (onion_skin_client_handshake(hop
->dh_handshake_state
, (char*)reply
,keys
,
2717 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
2718 log_warn(LD_CIRC
,"onion_skin_client_handshake failed.");
2719 return -END_CIRC_REASON_TORPROTOCOL
;
2721 /* Remember hash of g^xy */
2722 memcpy(hop
->handshake_digest
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
2723 } else if (reply_type
== CELL_CREATED_FAST
&& !hop
->dh_handshake_state
) {
2724 if (fast_client_handshake(hop
->fast_handshake_state
, reply
,
2726 DIGEST_LEN
*2+CIPHER_KEY_LEN
*2) < 0) {
2727 log_warn(LD_CIRC
,"fast_client_handshake failed.");
2728 return -END_CIRC_REASON_TORPROTOCOL
;
2730 memcpy(hop
->handshake_digest
, reply
+DIGEST_LEN
, DIGEST_LEN
);
2732 log_warn(LD_PROTOCOL
,"CREATED cell type did not match CREATE cell type.");
2733 return -END_CIRC_REASON_TORPROTOCOL
;
2736 crypto_dh_free(hop
->dh_handshake_state
); /* don't need it anymore */
2737 hop
->dh_handshake_state
= NULL
;
2739 memset(hop
->fast_handshake_state
, 0, sizeof(hop
->fast_handshake_state
));
2741 if (circuit_init_cpath_crypto(hop
, keys
, 0)<0) {
2742 return -END_CIRC_REASON_TORPROTOCOL
;
2745 hop
->state
= CPATH_STATE_OPEN
;
2746 log_info(LD_CIRC
,"Finished building %scircuit hop:",
2747 (reply_type
== CELL_CREATED_FAST
) ? "fast " : "");
2748 circuit_log_path(LOG_INFO
,LD_CIRC
,circ
);
2749 control_event_circuit_status(circ
, CIRC_EVENT_EXTENDED
, 0);
2754 /** We received a relay truncated cell on circ.
2756 * Since we don't ask for truncates currently, getting a truncated
2757 * means that a connection broke or an extend failed. For now,
2758 * just give up: for circ to close, and return 0.
2761 circuit_truncated(origin_circuit_t
*circ
, crypt_path_t
*layer
)
2763 // crypt_path_t *victim;
2764 // connection_t *stream;
2769 /* XXX Since we don't ask for truncates currently, getting a truncated
2770 * means that a connection broke or an extend failed. For now,
2773 circuit_mark_for_close(TO_CIRCUIT(circ
),
2774 END_CIRC_REASON_FLAG_REMOTE
|END_CIRC_REASON_OR_CONN_CLOSED
);
2778 while (layer
->next
!= circ
->cpath
) {
2779 /* we need to clear out layer->next */
2780 victim
= layer
->next
;
2781 log_debug(LD_CIRC
, "Killing a layer of the cpath.");
2783 for (stream
= circ
->p_streams
; stream
; stream
=stream
->next_stream
) {
2784 if (stream
->cpath_layer
== victim
) {
2785 log_info(LD_APP
, "Marking stream %d for close because of truncate.",
2787 /* no need to send 'end' relay cells,
2788 * because the other side's already dead
2790 connection_mark_unattached_ap(stream
, END_STREAM_REASON_DESTROY
);
2794 layer
->next
= victim
->next
;
2795 circuit_free_cpath_node(victim
);
2798 log_info(LD_CIRC
, "finished");
2803 /** Given a response payload and keys, initialize, then send a created
2807 onionskin_answer(or_circuit_t
*circ
, uint8_t cell_type
, const char *payload
,
2811 crypt_path_t
*tmp_cpath
;
2813 tmp_cpath
= tor_malloc_zero(sizeof(crypt_path_t
));
2814 tmp_cpath
->magic
= CRYPT_PATH_MAGIC
;
2816 memset(&cell
, 0, sizeof(cell_t
));
2817 cell
.command
= cell_type
;
2818 cell
.circ_id
= circ
->p_circ_id
;
2820 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_OPEN
);
2822 memcpy(cell
.payload
, payload
,
2823 cell_type
== CELL_CREATED
? ONIONSKIN_REPLY_LEN
: DIGEST_LEN
*2);
2825 log_debug(LD_CIRC
,"init digest forward 0x%.8x, backward 0x%.8x.",
2826 (unsigned int)get_uint32(keys
),
2827 (unsigned int)get_uint32(keys
+20));
2828 if (circuit_init_cpath_crypto(tmp_cpath
, keys
, 0)<0) {
2829 log_warn(LD_BUG
,"Circuit initialization failed");
2830 tor_free(tmp_cpath
);
2833 circ
->n_digest
= tmp_cpath
->f_digest
;
2834 circ
->n_crypto
= tmp_cpath
->f_crypto
;
2835 circ
->p_digest
= tmp_cpath
->b_digest
;
2836 circ
->p_crypto
= tmp_cpath
->b_crypto
;
2837 tmp_cpath
->magic
= 0;
2838 tor_free(tmp_cpath
);
2840 if (cell_type
== CELL_CREATED
)
2841 memcpy(circ
->handshake_digest
, cell
.payload
+DH_KEY_LEN
, DIGEST_LEN
);
2843 memcpy(circ
->handshake_digest
, cell
.payload
+DIGEST_LEN
, DIGEST_LEN
);
2845 circ
->is_first_hop
= (cell_type
== CELL_CREATED_FAST
);
2847 append_cell_to_circuit_queue(TO_CIRCUIT(circ
),
2848 circ
->p_conn
, &cell
, CELL_DIRECTION_IN
, 0);
2849 log_debug(LD_CIRC
,"Finished sending '%s' cell.",
2850 circ
->is_first_hop
? "created_fast" : "created");
2852 if (!is_local_addr(&circ
->p_conn
->_base
.addr
) &&
2853 !connection_or_nonopen_was_started_here(circ
->p_conn
)) {
2854 /* record that we could process create cells from a non-local conn
2855 * that we didn't initiate; presumably this means that create cells
2856 * can reach us too. */
2857 router_orport_found_reachable();
2863 /** Choose a length for a circuit of purpose <b>purpose</b>.
2864 * Default length is 3 + the number of endpoints that would give something
2865 * away. If the routerlist <b>routers</b> doesn't have enough routers
2866 * to handle the desired path length, return as large a path length as
2867 * is feasible, except if it's less than 2, in which case return -1.
2870 new_route_len(uint8_t purpose
, extend_info_t
*exit
,
2873 int num_acceptable_routers
;
2878 routelen
= DEFAULT_ROUTE_LEN
;
2880 purpose
!= CIRCUIT_PURPOSE_TESTING
&&
2881 purpose
!= CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
)
2884 num_acceptable_routers
= count_acceptable_nodes(nodes
);
2886 log_debug(LD_CIRC
,"Chosen route length %d (%d/%d routers suitable).",
2887 routelen
, num_acceptable_routers
, smartlist_len(nodes
));
2889 if (num_acceptable_routers
< 2) {
2891 "Not enough acceptable routers (%d). Discarding this circuit.",
2892 num_acceptable_routers
);
2896 if (num_acceptable_routers
< routelen
) {
2897 log_info(LD_CIRC
,"Not enough routers: cutting routelen from %d to %d.",
2898 routelen
, num_acceptable_routers
);
2899 routelen
= num_acceptable_routers
;
2905 /** Return a newly allocated list of uint16_t * for each predicted port not
2906 * handled by a current circuit. */
2907 static smartlist_t
*
2908 circuit_get_unhandled_ports(time_t now
)
2910 smartlist_t
*dest
= rep_hist_get_predicted_ports(now
);
2911 circuit_remove_handled_ports(dest
);
2915 /** Return 1 if we already have circuits present or on the way for
2916 * all anticipated ports. Return 0 if we should make more.
2918 * If we're returning 0, set need_uptime and need_capacity to
2919 * indicate any requirements that the unhandled ports have.
2922 circuit_all_predicted_ports_handled(time_t now
, int *need_uptime
,
2927 smartlist_t
*sl
= circuit_get_unhandled_ports(now
);
2928 smartlist_t
*LongLivedServices
= get_options()->LongLivedPorts
;
2929 tor_assert(need_uptime
);
2930 tor_assert(need_capacity
);
2931 // Always predict need_capacity
2933 enough
= (smartlist_len(sl
) == 0);
2934 for (i
= 0; i
< smartlist_len(sl
); ++i
) {
2935 port
= smartlist_get(sl
, i
);
2936 if (smartlist_string_num_isin(LongLivedServices
, *port
))
2944 /** Return 1 if <b>node</b> can handle one or more of the ports in
2945 * <b>needed_ports</b>, else return 0.
2948 node_handles_some_port(const node_t
*node
, smartlist_t
*needed_ports
)
2953 for (i
= 0; i
< smartlist_len(needed_ports
); ++i
) {
2954 addr_policy_result_t r
;
2955 /* alignment issues aren't a worry for this dereference, since
2956 needed_ports is explicitly a smartlist of uint16_t's */
2957 port
= *(uint16_t *)smartlist_get(needed_ports
, i
);
2960 r
= compare_tor_addr_to_node_policy(NULL
, port
, node
);
2963 if (r
!= ADDR_POLICY_REJECTED
&& r
!= ADDR_POLICY_PROBABLY_REJECTED
)
2969 /** Return true iff <b>conn</b> needs another general circuit to be
2972 ap_stream_wants_exit_attention(connection_t
*conn
)
2974 entry_connection_t
*entry
;
2975 if (conn
->type
!= CONN_TYPE_AP
)
2977 entry
= TO_ENTRY_CONN(conn
);
2979 if (conn
->state
== AP_CONN_STATE_CIRCUIT_WAIT
&&
2980 !conn
->marked_for_close
&&
2981 !(entry
->want_onehop
) && /* ignore one-hop streams */
2982 !(entry
->use_begindir
) && /* ignore targeted dir fetches */
2983 !(entry
->chosen_exit_name
) && /* ignore defined streams */
2984 !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn
)) &&
2985 !circuit_stream_is_being_handled(TO_ENTRY_CONN(conn
), 0,
2986 MIN_CIRCUITS_HANDLING_STREAM
))
2991 /** Return a pointer to a suitable router to be the exit node for the
2992 * general-purpose circuit we're about to build.
2994 * Look through the connection array, and choose a router that maximizes
2995 * the number of pending streams that can exit from this router.
2997 * Return NULL if we can't find any suitable routers.
2999 static const node_t
*
3000 choose_good_exit_server_general(int need_uptime
, int need_capacity
)
3003 int n_pending_connections
= 0;
3004 smartlist_t
*connections
;
3005 int best_support
= -1;
3006 int n_best_support
=0;
3007 const or_options_t
*options
= get_options();
3008 const smartlist_t
*the_nodes
;
3009 const node_t
*node
=NULL
;
3011 connections
= get_connection_array();
3013 /* Count how many connections are waiting for a circuit to be built.
3014 * We use this for log messages now, but in the future we may depend on it.
3016 SMARTLIST_FOREACH(connections
, connection_t
*, conn
,
3018 if (ap_stream_wants_exit_attention(conn
))
3019 ++n_pending_connections
;
3021 // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
3022 // n_pending_connections);
3023 /* Now we count, for each of the routers in the directory, how many
3024 * of the pending connections could possibly exit from that
3025 * router (n_supported[i]). (We can't be sure about cases where we
3026 * don't know the IP address of the pending connection.)
3028 * -1 means "Don't use this router at all."
3030 the_nodes
= nodelist_get_list();
3031 n_supported
= tor_malloc(sizeof(int)*smartlist_len(the_nodes
));
3032 SMARTLIST_FOREACH_BEGIN(the_nodes
, const node_t
*, node
) {
3033 const int i
= node_sl_idx
;
3034 if (router_digest_is_me(node
->identity
)) {
3035 n_supported
[i
] = -1;
3036 // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
3037 /* XXX there's probably a reverse predecessor attack here, but
3038 * it's slow. should we take this out? -RD
3042 if (!node_has_descriptor(node
)) {
3043 n_supported
[i
] = -1;
3046 if (!node
->is_running
|| node
->is_bad_exit
) {
3047 n_supported
[i
] = -1;
3048 continue; /* skip routers that are known to be down or bad exits */
3050 if (node_get_purpose(node
) != ROUTER_PURPOSE_GENERAL
) {
3051 /* never pick a non-general node as a random exit. */
3052 n_supported
[i
] = -1;
3055 if (routerset_contains_node(options
->_ExcludeExitNodesUnion
, node
)) {
3056 n_supported
[i
] = -1;
3057 continue; /* user asked us not to use it, no matter what */
3059 if (options
->ExitNodes
&&
3060 !routerset_contains_node(options
->ExitNodes
, node
)) {
3061 n_supported
[i
] = -1;
3062 continue; /* not one of our chosen exit nodes */
3065 if (node_is_unreliable(node
, need_uptime
, need_capacity
, 0)) {
3066 n_supported
[i
] = -1;
3067 continue; /* skip routers that are not suitable. Don't worry if
3068 * this makes us reject all the possible routers: if so,
3069 * we'll retry later in this function with need_update and
3070 * need_capacity set to 0. */
3072 if (!(node
->is_valid
|| options
->_AllowInvalid
& ALLOW_INVALID_EXIT
)) {
3073 /* if it's invalid and we don't want it */
3074 n_supported
[i
] = -1;
3075 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
3076 // router->nickname, i);
3077 continue; /* skip invalid routers */
3079 if (options
->ExcludeSingleHopRelays
&&
3080 node_allows_single_hop_exits(node
)) {
3081 n_supported
[i
] = -1;
3084 if (node_exit_policy_rejects_all(node
)) {
3085 n_supported
[i
] = -1;
3086 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
3087 // router->nickname, i);
3088 continue; /* skip routers that reject all */
3091 /* iterate over connections */
3092 SMARTLIST_FOREACH_BEGIN(connections
, connection_t
*, conn
) {
3093 if (!ap_stream_wants_exit_attention(conn
))
3094 continue; /* Skip everything but APs in CIRCUIT_WAIT */
3095 if (connection_ap_can_use_exit(TO_ENTRY_CONN(conn
), node
)) {
3097 // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
3098 // router->nickname, i, n_supported[i]);
3100 // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
3101 // router->nickname, i);
3103 } SMARTLIST_FOREACH_END(conn
);
3104 if (n_pending_connections
> 0 && n_supported
[i
] == 0) {
3105 /* Leave best_support at -1 if that's where it is, so we can
3106 * distinguish it later. */
3109 if (n_supported
[i
] > best_support
) {
3110 /* If this router is better than previous ones, remember its index
3111 * and goodness, and start counting how many routers are this good. */
3112 best_support
= n_supported
[i
]; n_best_support
=1;
3113 // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
3114 // router->nickname);
3115 } else if (n_supported
[i
] == best_support
) {
3116 /* If this router is _as good_ as the best one, just increment the
3117 * count of equally good routers.*/
3120 } SMARTLIST_FOREACH_END(node
);
3122 "Found %d servers that might support %d/%d pending connections.",
3123 n_best_support
, best_support
>= 0 ? best_support
: 0,
3124 n_pending_connections
);
3126 /* If any routers definitely support any pending connections, choose one
3128 if (best_support
> 0) {
3129 smartlist_t
*supporting
= smartlist_new();
3131 SMARTLIST_FOREACH(the_nodes
, const node_t
*, node
, {
3132 if (n_supported
[node_sl_idx
] == best_support
)
3133 smartlist_add(supporting
, (void*)node
);
3136 node
= node_sl_choose_by_bandwidth(supporting
, WEIGHT_FOR_EXIT
);
3137 smartlist_free(supporting
);
3139 /* Either there are no pending connections, or no routers even seem to
3140 * possibly support any of them. Choose a router at random that satisfies
3141 * at least one predicted exit port. */
3144 smartlist_t
*needed_ports
, *supporting
;
3146 if (best_support
== -1) {
3147 if (need_uptime
|| need_capacity
) {
3149 "We couldn't find any live%s%s routers; falling back "
3150 "to list of all routers.",
3151 need_capacity
?", fast":"",
3152 need_uptime
?", stable":"");
3153 tor_free(n_supported
);
3154 return choose_good_exit_server_general(0, 0);
3156 log_notice(LD_CIRC
, "All routers are down or won't exit%s -- "
3157 "choosing a doomed exit at random.",
3158 options
->_ExcludeExitNodesUnion
? " or are Excluded" : "");
3160 supporting
= smartlist_new();
3161 needed_ports
= circuit_get_unhandled_ports(time(NULL
));
3162 for (attempt
= 0; attempt
< 2; attempt
++) {
3163 /* try once to pick only from routers that satisfy a needed port,
3164 * then if there are none, pick from any that support exiting. */
3165 SMARTLIST_FOREACH_BEGIN(the_nodes
, const node_t
*, node
) {
3166 if (n_supported
[node_sl_idx
] != -1 &&
3167 (attempt
|| node_handles_some_port(node
, needed_ports
))) {
3168 // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
3169 // try, router->nickname);
3170 smartlist_add(supporting
, (void*)node
);
3172 } SMARTLIST_FOREACH_END(node
);
3174 node
= node_sl_choose_by_bandwidth(supporting
, WEIGHT_FOR_EXIT
);
3177 smartlist_clear(supporting
);
3178 /* If we reach this point, we can't actually support any unhandled
3179 * predicted ports, so clear all the remaining ones. */
3180 if (smartlist_len(needed_ports
))
3181 rep_hist_remove_predicted_ports(needed_ports
);
3183 SMARTLIST_FOREACH(needed_ports
, uint16_t *, cp
, tor_free(cp
));
3184 smartlist_free(needed_ports
);
3185 smartlist_free(supporting
);
3188 tor_free(n_supported
);
3190 log_info(LD_CIRC
, "Chose exit server '%s'", node_describe(node
));
3193 if (options
->ExitNodes
) {
3195 "No specified %sexit routers seem to be running: "
3196 "can't choose an exit.",
3197 options
->_ExcludeExitNodesUnion
? "non-excluded " : "");
3202 /** Return a pointer to a suitable router to be the exit node for the
3203 * circuit of purpose <b>purpose</b> that we're about to build (or NULL
3204 * if no router is suitable).
3206 * For general-purpose circuits, pass it off to
3207 * choose_good_exit_server_general()
3209 * For client-side rendezvous circuits, choose a random node, weighted
3210 * toward the preferences in 'options'.
3212 static const node_t
*
3213 choose_good_exit_server(uint8_t purpose
,
3214 int need_uptime
, int need_capacity
, int is_internal
)
3216 const or_options_t
*options
= get_options();
3217 router_crn_flags_t flags
= CRN_NEED_DESC
;
3219 flags
|= CRN_NEED_UPTIME
;
3221 flags
|= CRN_NEED_CAPACITY
;
3224 case CIRCUIT_PURPOSE_C_GENERAL
:
3225 if (options
->_AllowInvalid
& ALLOW_INVALID_MIDDLE
)
3226 flags
|= CRN_ALLOW_INVALID
;
3227 if (is_internal
) /* pick it like a middle hop */
3228 return router_choose_random_node(NULL
, options
->ExcludeNodes
, flags
);
3230 return choose_good_exit_server_general(need_uptime
,need_capacity
);
3231 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
3232 if (options
->_AllowInvalid
& ALLOW_INVALID_RENDEZVOUS
)
3233 flags
|= CRN_ALLOW_INVALID
;
3234 return router_choose_random_node(NULL
, options
->ExcludeNodes
, flags
);
3236 log_warn(LD_BUG
,"Unhandled purpose %d", purpose
);
3237 tor_fragile_assert();
3241 /** Log a warning if the user specified an exit for the circuit that
3242 * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
3244 warn_if_last_router_excluded(origin_circuit_t
*circ
, const extend_info_t
*exit
)
3246 const or_options_t
*options
= get_options();
3247 routerset_t
*rs
= options
->ExcludeNodes
;
3248 const char *description
;
3249 uint8_t purpose
= circ
->_base
.purpose
;
3251 if (circ
->build_state
->onehop_tunnel
)
3257 case CIRCUIT_PURPOSE_OR
:
3258 case CIRCUIT_PURPOSE_INTRO_POINT
:
3259 case CIRCUIT_PURPOSE_REND_POINT_WAITING
:
3260 case CIRCUIT_PURPOSE_REND_ESTABLISHED
:
3261 log_warn(LD_BUG
, "Called on non-origin circuit (purpose %d, %s)",
3263 circuit_purpose_to_string(purpose
));
3265 case CIRCUIT_PURPOSE_C_GENERAL
:
3266 if (circ
->build_state
->is_internal
)
3268 description
= "requested exit node";
3269 rs
= options
->_ExcludeExitNodesUnion
;
3271 case CIRCUIT_PURPOSE_C_INTRODUCING
:
3272 case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
:
3273 case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
:
3274 case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
:
3275 case CIRCUIT_PURPOSE_S_CONNECT_REND
:
3276 case CIRCUIT_PURPOSE_S_REND_JOINED
:
3277 case CIRCUIT_PURPOSE_TESTING
:
3279 case CIRCUIT_PURPOSE_C_ESTABLISH_REND
:
3280 case CIRCUIT_PURPOSE_C_REND_READY
:
3281 case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
:
3282 case CIRCUIT_PURPOSE_C_REND_JOINED
:
3283 description
= "chosen rendezvous point";
3285 case CIRCUIT_PURPOSE_CONTROLLER
:
3286 rs
= options
->_ExcludeExitNodesUnion
;
3287 description
= "controller-selected circuit target";
3291 if (routerset_contains_extendinfo(rs
, exit
)) {
3292 /* We should never get here if StrictNodes is set to 1. */
3293 if (options
->StrictNodes
) {
3294 log_warn(LD_BUG
, "Using %s '%s' which is listed in ExcludeNodes%s, "
3295 "even though StrictNodes is set. Please report. "
3296 "(Circuit purpose: %s)",
3297 description
, extend_info_describe(exit
),
3298 rs
==options
->ExcludeNodes
?"":" or ExcludeExitNodes",
3299 circuit_purpose_to_string(purpose
));
3301 log_warn(LD_CIRC
, "Using %s '%s' which is listed in "
3302 "ExcludeNodes%s, because no better options were available. To "
3303 "prevent this (and possibly break your Tor functionality), "
3304 "set the StrictNodes configuration option. "
3305 "(Circuit purpose: %s)",
3306 description
, extend_info_describe(exit
),
3307 rs
==options
->ExcludeNodes
?"":" or ExcludeExitNodes",
3308 circuit_purpose_to_string(purpose
));
3310 circuit_log_path(LOG_WARN
, LD_CIRC
, circ
);
3316 /** Decide a suitable length for circ's cpath, and pick an exit
3317 * router (or use <b>exit</b> if provided). Store these in the
3318 * cpath. Return 0 if ok, -1 if circuit should be closed. */
3320 onion_pick_cpath_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
3322 cpath_build_state_t
*state
= circ
->build_state
;
3324 if (state
->onehop_tunnel
) {
3325 log_debug(LD_CIRC
, "Launching a one-hop circuit for dir tunnel.");
3326 state
->desired_path_len
= 1;
3328 int r
= new_route_len(circ
->_base
.purpose
, exit
, nodelist_get_list());
3329 if (r
< 1) /* must be at least 1 */
3331 state
->desired_path_len
= r
;
3334 if (exit
) { /* the circuit-builder pre-requested one */
3335 warn_if_last_router_excluded(circ
, exit
);
3336 log_info(LD_CIRC
,"Using requested exit node '%s'",
3337 extend_info_describe(exit
));
3338 exit
= extend_info_dup(exit
);
3339 } else { /* we have to decide one */
3340 const node_t
*node
=
3341 choose_good_exit_server(circ
->_base
.purpose
, state
->need_uptime
,
3342 state
->need_capacity
, state
->is_internal
);
3344 log_warn(LD_CIRC
,"failed to choose an exit server");
3347 exit
= extend_info_from_node(node
, 0);
3350 state
->chosen_exit
= exit
;
3354 /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
3355 * hop to the cpath reflecting this. Don't send the next extend cell --
3356 * the caller will do this if it wants to.
3359 circuit_append_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
3361 cpath_build_state_t
*state
;
3365 state
= circ
->build_state
;
3367 extend_info_free(state
->chosen_exit
);
3368 state
->chosen_exit
= extend_info_dup(exit
);
3370 ++circ
->build_state
->desired_path_len
;
3371 onion_append_hop(&circ
->cpath
, exit
);
3375 /** Take an open <b>circ</b>, and add a new hop at the end, based on
3376 * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
3377 * send the next extend cell to begin connecting to that hop.
3380 circuit_extend_to_new_exit(origin_circuit_t
*circ
, extend_info_t
*exit
)
3383 warn_if_last_router_excluded(circ
, exit
);
3384 circuit_append_new_exit(circ
, exit
);
3385 circuit_set_state(TO_CIRCUIT(circ
), CIRCUIT_STATE_BUILDING
);
3386 if ((err_reason
= circuit_send_next_onion_skin(circ
))<0) {
3387 log_warn(LD_CIRC
, "Couldn't extend circuit to new point %s.",
3388 extend_info_describe(exit
));
3389 circuit_mark_for_close(TO_CIRCUIT(circ
), -err_reason
);
3395 /** Return the number of routers in <b>routers</b> that are currently up
3396 * and available for building circuits through.
3399 count_acceptable_nodes(smartlist_t
*nodes
)
3403 SMARTLIST_FOREACH_BEGIN(nodes
, const node_t
*, node
) {
3404 // log_debug(LD_CIRC,
3405 // "Contemplating whether router %d (%s) is a new option.",
3407 if (! node
->is_running
)
3408 // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
3410 if (! node
->is_valid
)
3411 // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
3413 if (! node_has_descriptor(node
))
3415 /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
3416 * allows this node in some places, then we're getting an inaccurate
3417 * count. For now, be conservative and don't count it. But later we
3418 * should try to be smarter. */
3420 } SMARTLIST_FOREACH_END(node
);
3422 // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
3427 /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
3428 * This function is used to extend cpath by another hop.
3431 onion_append_to_cpath(crypt_path_t
**head_ptr
, crypt_path_t
*new_hop
)
3434 new_hop
->next
= (*head_ptr
);
3435 new_hop
->prev
= (*head_ptr
)->prev
;
3436 (*head_ptr
)->prev
->next
= new_hop
;
3437 (*head_ptr
)->prev
= new_hop
;
3439 *head_ptr
= new_hop
;
3440 new_hop
->prev
= new_hop
->next
= new_hop
;
3444 /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
3445 * and <b>state</b> and the cpath <b>head</b> (currently populated only
3446 * to length <b>cur_len</b> to decide a suitable middle hop for a
3447 * circuit. In particular, make sure we don't pick the exit node or its
3448 * family, and make sure we don't duplicate any previous nodes or their
3450 static const node_t
*
3451 choose_good_middle_server(uint8_t purpose
,
3452 cpath_build_state_t
*state
,
3457 const node_t
*r
, *choice
;
3458 crypt_path_t
*cpath
;
3459 smartlist_t
*excluded
;
3460 const or_options_t
*options
= get_options();
3461 router_crn_flags_t flags
= CRN_NEED_DESC
;
3462 tor_assert(_CIRCUIT_PURPOSE_MIN
<= purpose
&&
3463 purpose
<= _CIRCUIT_PURPOSE_MAX
);
3465 log_debug(LD_CIRC
, "Contemplating intermediate hop: random choice.");
3466 excluded
= smartlist_new();
3467 if ((r
= build_state_get_exit_node(state
))) {
3468 nodelist_add_node_and_family(excluded
, r
);
3470 for (i
= 0, cpath
= head
; i
< cur_len
; ++i
, cpath
=cpath
->next
) {
3471 if ((r
= node_get_by_id(cpath
->extend_info
->identity_digest
))) {
3472 nodelist_add_node_and_family(excluded
, r
);
3476 if (state
->need_uptime
)
3477 flags
|= CRN_NEED_UPTIME
;
3478 if (state
->need_capacity
)
3479 flags
|= CRN_NEED_CAPACITY
;
3480 if (options
->_AllowInvalid
& ALLOW_INVALID_MIDDLE
)
3481 flags
|= CRN_ALLOW_INVALID
;
3482 choice
= router_choose_random_node(excluded
, options
->ExcludeNodes
, flags
);
3483 smartlist_free(excluded
);
3487 /** Pick a good entry server for the circuit to be built according to
3488 * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
3489 * router (if we're an OR), and respect firewall settings; if we're
3490 * configured to use entry guards, return one.
3492 * If <b>state</b> is NULL, we're choosing a router to serve as an entry
3493 * guard, not for any particular circuit.
3495 static const node_t
*
3496 choose_good_entry_server(uint8_t purpose
, cpath_build_state_t
*state
)
3498 const node_t
*choice
;
3499 smartlist_t
*excluded
;
3500 const or_options_t
*options
= get_options();
3501 router_crn_flags_t flags
= CRN_NEED_GUARD
|CRN_NEED_DESC
;
3504 if (state
&& options
->UseEntryGuards
&&
3505 (purpose
!= CIRCUIT_PURPOSE_TESTING
|| options
->BridgeRelay
)) {
3506 /* This is request for an entry server to use for a regular circuit,
3507 * and we use entry guard nodes. Just return one of the guard nodes. */
3508 return choose_random_entry(state
);
3511 excluded
= smartlist_new();
3513 if (state
&& (node
= build_state_get_exit_node(state
))) {
3514 /* Exclude the exit node from the state, if we have one. Also exclude its
3516 nodelist_add_node_and_family(excluded
, node
);
3518 if (firewall_is_fascist_or()) {
3519 /* Exclude all ORs that we can't reach through our firewall */
3520 smartlist_t
*nodes
= nodelist_get_list();
3521 SMARTLIST_FOREACH(nodes
, const node_t
*, node
, {
3522 if (!fascist_firewall_allows_node(node
))
3523 smartlist_add(excluded
, (void*)node
);
3526 /* and exclude current entry guards and their families, if applicable */
3527 if (options
->UseEntryGuards
&& entry_guards
) {
3528 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
3530 if ((node
= node_get_by_id(entry
->identity
))) {
3531 nodelist_add_node_and_family(excluded
, node
);
3537 if (state
->need_uptime
)
3538 flags
|= CRN_NEED_UPTIME
;
3539 if (state
->need_capacity
)
3540 flags
|= CRN_NEED_CAPACITY
;
3542 if (options
->_AllowInvalid
& ALLOW_INVALID_ENTRY
)
3543 flags
|= CRN_ALLOW_INVALID
;
3545 choice
= router_choose_random_node(excluded
, options
->ExcludeNodes
, flags
);
3546 smartlist_free(excluded
);
3550 /** Return the first non-open hop in cpath, or return NULL if all
3552 static crypt_path_t
*
3553 onion_next_hop_in_cpath(crypt_path_t
*cpath
)
3555 crypt_path_t
*hop
= cpath
;
3557 if (hop
->state
!= CPATH_STATE_OPEN
)
3560 } while (hop
!= cpath
);
3564 /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
3565 * based on <b>state</b>. Append the hop info to head_ptr.
3568 onion_extend_cpath(origin_circuit_t
*circ
)
3570 uint8_t purpose
= circ
->_base
.purpose
;
3571 cpath_build_state_t
*state
= circ
->build_state
;
3572 int cur_len
= circuit_get_cpath_len(circ
);
3573 extend_info_t
*info
= NULL
;
3575 if (cur_len
>= state
->desired_path_len
) {
3576 log_debug(LD_CIRC
, "Path is complete: %d steps long",
3577 state
->desired_path_len
);
3581 log_debug(LD_CIRC
, "Path is %d long; we want %d", cur_len
,
3582 state
->desired_path_len
);
3584 if (cur_len
== state
->desired_path_len
- 1) { /* Picking last node */
3585 info
= extend_info_dup(state
->chosen_exit
);
3586 } else if (cur_len
== 0) { /* picking first node */
3587 const node_t
*r
= choose_good_entry_server(purpose
, state
);
3589 /* If we're extending to a bridge, use the preferred address
3590 rather than the primary, for potentially extending to an IPv6
3592 int use_pref_addr
= (r
->ri
!= NULL
&&
3593 r
->ri
->purpose
== ROUTER_PURPOSE_BRIDGE
);
3594 info
= extend_info_from_node(r
, use_pref_addr
);
3599 choose_good_middle_server(purpose
, state
, circ
->cpath
, cur_len
);
3601 info
= extend_info_from_node(r
, 0);
3607 log_warn(LD_CIRC
,"Failed to find node for hop %d of our path. Discarding "
3608 "this circuit.", cur_len
);
3612 log_debug(LD_CIRC
,"Chose router %s for hop %d (exit is %s)",
3613 extend_info_describe(info
),
3614 cur_len
+1, build_state_get_exit_nickname(state
));
3616 onion_append_hop(&circ
->cpath
, info
);
3617 extend_info_free(info
);
3621 /** Create a new hop, annotate it with information about its
3622 * corresponding router <b>choice</b>, and append it to the
3623 * end of the cpath <b>head_ptr</b>. */
3625 onion_append_hop(crypt_path_t
**head_ptr
, extend_info_t
*choice
)
3627 crypt_path_t
*hop
= tor_malloc_zero(sizeof(crypt_path_t
));
3629 /* link hop into the cpath, at the end. */
3630 onion_append_to_cpath(head_ptr
, hop
);
3632 hop
->magic
= CRYPT_PATH_MAGIC
;
3633 hop
->state
= CPATH_STATE_CLOSED
;
3635 hop
->extend_info
= extend_info_dup(choice
);
3637 hop
->package_window
= circuit_initial_package_window();
3638 hop
->deliver_window
= CIRCWINDOW_START
;
3643 /** Allocate a new extend_info object based on the various arguments. */
3645 extend_info_alloc(const char *nickname
, const char *digest
,
3646 crypto_pk_t
*onion_key
,
3647 const tor_addr_t
*addr
, uint16_t port
)
3649 extend_info_t
*info
= tor_malloc_zero(sizeof(extend_info_t
));
3650 memcpy(info
->identity_digest
, digest
, DIGEST_LEN
);
3652 strlcpy(info
->nickname
, nickname
, sizeof(info
->nickname
));
3654 info
->onion_key
= crypto_pk_dup_key(onion_key
);
3655 tor_addr_copy(&info
->addr
, addr
);
3660 /** Allocate and return a new extend_info_t that can be used to build
3661 * a circuit to or through the router <b>r</b>. Use the primary
3662 * address of the router unless <b>for_direct_connect</b> is true, in
3663 * which case the preferred address is used instead. */
3665 extend_info_from_router(const routerinfo_t
*r
, int for_direct_connect
)
3670 if (for_direct_connect
)
3671 router_get_pref_orport(r
, &ap
);
3673 router_get_prim_orport(r
, &ap
);
3674 return extend_info_alloc(r
->nickname
, r
->cache_info
.identity_digest
,
3675 r
->onion_pkey
, &ap
.addr
, ap
.port
);
3678 /** Allocate and return a new extend_info that can be used to build a
3679 * circuit to or through the node <b>node</b>. Use the primary address
3680 * of the node unless <b>for_direct_connect</b> is true, in which case
3681 * the preferred address is used instead. May return NULL if there is
3682 * not enough info about <b>node</b> to extend to it--for example, if
3683 * there is no routerinfo_t or microdesc_t.
3686 extend_info_from_node(const node_t
*node
, int for_direct_connect
)
3689 return extend_info_from_router(node
->ri
, for_direct_connect
);
3690 } else if (node
->rs
&& node
->md
) {
3692 tor_addr_from_ipv4h(&addr
, node
->rs
->addr
);
3693 return extend_info_alloc(node
->rs
->nickname
,
3695 node
->md
->onion_pkey
,
3703 /** Release storage held by an extend_info_t struct. */
3705 extend_info_free(extend_info_t
*info
)
3709 crypto_pk_free(info
->onion_key
);
3713 /** Allocate and return a new extend_info_t with the same contents as
3716 extend_info_dup(extend_info_t
*info
)
3718 extend_info_t
*newinfo
;
3720 newinfo
= tor_malloc(sizeof(extend_info_t
));
3721 memcpy(newinfo
, info
, sizeof(extend_info_t
));
3722 if (info
->onion_key
)
3723 newinfo
->onion_key
= crypto_pk_dup_key(info
->onion_key
);
3725 newinfo
->onion_key
= NULL
;
3729 /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
3730 * If there is no chosen exit, or if we don't know the routerinfo_t for
3731 * the chosen exit, return NULL.
3734 build_state_get_exit_node(cpath_build_state_t
*state
)
3736 if (!state
|| !state
->chosen_exit
)
3738 return node_get_by_id(state
->chosen_exit
->identity_digest
);
3741 /** Return the nickname for the chosen exit router in <b>state</b>. If
3742 * there is no chosen exit, or if we don't know the routerinfo_t for the
3743 * chosen exit, return NULL.
3746 build_state_get_exit_nickname(cpath_build_state_t
*state
)
3748 if (!state
|| !state
->chosen_exit
)
3750 return state
->chosen_exit
->nickname
;
3753 /** Check whether the entry guard <b>e</b> is usable, given the directory
3754 * authorities' opinion about the router (stored in <b>ri</b>) and the user's
3755 * configuration (in <b>options</b>). Set <b>e</b>->bad_since
3756 * accordingly. Return true iff the entry guard's status changes.
3758 * If it's not usable, set *<b>reason</b> to a static string explaining why.
3761 entry_guard_set_status(entry_guard_t
*e
, const node_t
*node
,
3762 time_t now
, const or_options_t
*options
,
3763 const char **reason
)
3765 char buf
[HEX_DIGEST_LEN
+1];
3770 /* Do we want to mark this guard as bad? */
3772 *reason
= "unlisted";
3773 else if (!node
->is_running
)
3775 else if (options
->UseBridges
&& (!node
->ri
||
3776 node
->ri
->purpose
!= ROUTER_PURPOSE_BRIDGE
))
3777 *reason
= "not a bridge";
3778 else if (options
->UseBridges
&& !node_is_a_configured_bridge(node
))
3779 *reason
= "not a configured bridge";
3780 else if (!options
->UseBridges
&& !node
->is_possible_guard
&&
3781 !routerset_contains_node(options
->EntryNodes
,node
))
3782 *reason
= "not recommended as a guard";
3783 else if (routerset_contains_node(options
->ExcludeNodes
, node
))
3784 *reason
= "excluded";
3785 else if (e
->path_bias_disabled
)
3786 *reason
= "path-biased";
3788 if (*reason
&& ! e
->bad_since
) {
3789 /* Router is newly bad. */
3790 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
3791 log_info(LD_CIRC
, "Entry guard %s (%s) is %s: marking as unusable.",
3792 e
->nickname
, buf
, *reason
);
3795 control_event_guard(e
->nickname
, e
->identity
, "BAD");
3797 } else if (!*reason
&& e
->bad_since
) {
3798 /* There's nothing wrong with the router any more. */
3799 base16_encode(buf
, sizeof(buf
), e
->identity
, DIGEST_LEN
);
3800 log_info(LD_CIRC
, "Entry guard %s (%s) is no longer unusable: "
3801 "marking as ok.", e
->nickname
, buf
);
3804 control_event_guard(e
->nickname
, e
->identity
, "GOOD");
3810 /** Return true iff enough time has passed since we last tried to connect
3811 * to the unreachable guard <b>e</b> that we're willing to try again. */
3813 entry_is_time_to_retry(entry_guard_t
*e
, time_t now
)
3816 if (e
->last_attempted
< e
->unreachable_since
)
3818 diff
= now
- e
->unreachable_since
;
3820 return now
> (e
->last_attempted
+ 60*60);
3821 else if (diff
< 3*24*60*60)
3822 return now
> (e
->last_attempted
+ 4*60*60);
3823 else if (diff
< 7*24*60*60)
3824 return now
> (e
->last_attempted
+ 18*60*60);
3826 return now
> (e
->last_attempted
+ 36*60*60);
3829 /** Return the node corresponding to <b>e</b>, if <b>e</b> is
3830 * working well enough that we are willing to use it as an entry
3831 * right now. (Else return NULL.) In particular, it must be
3832 * - Listed as either up or never yet contacted;
3833 * - Present in the routerlist;
3834 * - Listed as 'stable' or 'fast' by the current dirserver consensus,
3835 * if demanded by <b>need_uptime</b> or <b>need_capacity</b>
3836 * (unless it's a configured EntryNode);
3837 * - Allowed by our current ReachableORAddresses config option; and
3838 * - Currently thought to be reachable by us (unless <b>assume_reachable</b>
3841 * If the answer is no, set *<b>msg</b> to an explanation of why.
3843 static INLINE
const node_t
*
3844 entry_is_live(entry_guard_t
*e
, int need_uptime
, int need_capacity
,
3845 int assume_reachable
, const char **msg
)
3848 const or_options_t
*options
= get_options();
3851 if (e
->path_bias_disabled
) {
3852 *msg
= "path-biased";
3859 /* no good if it's unreachable, unless assume_unreachable or can_retry. */
3860 if (!assume_reachable
&& !e
->can_retry
&&
3861 e
->unreachable_since
&& !entry_is_time_to_retry(e
, time(NULL
))) {
3862 *msg
= "unreachable";
3865 node
= node_get_by_id(e
->identity
);
3866 if (!node
|| !node_has_descriptor(node
)) {
3867 *msg
= "no descriptor";
3870 if (get_options()->UseBridges
) {
3871 if (node_get_purpose(node
) != ROUTER_PURPOSE_BRIDGE
) {
3872 *msg
= "not a bridge";
3875 if (!node_is_a_configured_bridge(node
)) {
3876 *msg
= "not a configured bridge";
3879 } else { /* !get_options()->UseBridges */
3880 if (node_get_purpose(node
) != ROUTER_PURPOSE_GENERAL
) {
3881 *msg
= "not general-purpose";
3885 if (routerset_contains_node(options
->EntryNodes
, node
)) {
3886 /* they asked for it, they get it */
3887 need_uptime
= need_capacity
= 0;
3889 if (node_is_unreliable(node
, need_uptime
, need_capacity
, 0)) {
3890 *msg
= "not fast/stable";
3893 if (!fascist_firewall_allows_node(node
)) {
3894 *msg
= "unreachable by config";
3900 /** Return the number of entry guards that we think are usable. */
3902 num_live_entry_guards(void)
3908 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
3910 if (entry_is_live(entry
, 0, 1, 0, &msg
))
3916 /** If <b>digest</b> matches the identity of any node in the
3917 * entry_guards list, return that node. Else return NULL. */
3918 static entry_guard_t
*
3919 entry_guard_get_by_id_digest(const char *digest
)
3921 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
3922 if (tor_memeq(digest
, entry
->identity
, DIGEST_LEN
))
3928 /** Dump a description of our list of entry guards to the log at level
3929 * <b>severity</b>. */
3931 log_entry_guards(int severity
)
3933 smartlist_t
*elements
= smartlist_new();
3936 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, e
)
3938 const char *msg
= NULL
;
3939 if (entry_is_live(e
, 0, 1, 0, &msg
))
3940 smartlist_add_asprintf(elements
, "%s [%s] (up %s)",
3942 hex_str(e
->identity
, DIGEST_LEN
),
3943 e
->made_contact
? "made-contact" : "never-contacted");
3945 smartlist_add_asprintf(elements
, "%s [%s] (%s, %s)",
3947 hex_str(e
->identity
, DIGEST_LEN
),
3949 e
->made_contact
? "made-contact" : "never-contacted");
3951 SMARTLIST_FOREACH_END(e
);
3953 s
= smartlist_join_strings(elements
, ",", 0, NULL
);
3954 SMARTLIST_FOREACH(elements
, char*, cp
, tor_free(cp
));
3955 smartlist_free(elements
);
3956 log_fn(severity
,LD_CIRC
,"%s",s
);
3960 /** Called when one or more guards that we would previously have used for some
3961 * purpose are no longer in use because a higher-priority guard has become
3964 control_event_guard_deferred(void)
3966 /* XXXX We don't actually have a good way to figure out _how many_ entries
3967 * are live for some purpose. We need an entry_is_even_slightly_live()
3968 * function for this to work right. NumEntryGuards isn't reliable: if we
3969 * need guards with weird properties, we can have more than that number
3975 const or_options_t
*options
= get_options();
3978 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, entry
,
3980 if (entry_is_live(entry
, 0, 1, 0, &msg
)) {
3981 if (n
++ == options
->NumEntryGuards
) {
3982 control_event_guard(entry
->nickname
, entry
->identity
, "DEFERRED");
3990 /** Add a new (preferably stable and fast) router to our
3991 * entry_guards list. Return a pointer to the router if we succeed,
3992 * or NULL if we can't find any more suitable entries.
3994 * If <b>chosen</b> is defined, use that one, and if it's not
3995 * already in our entry_guards list, put it at the *beginning*.
3996 * Else, put the one we pick at the end of the list. */
3997 static const node_t
*
3998 add_an_entry_guard(const node_t
*chosen
, int reset_status
, int prepend
)
4001 entry_guard_t
*entry
;
4005 entry
= entry_guard_get_by_id_digest(node
->identity
);
4008 entry
->bad_since
= 0;
4009 entry
->can_retry
= 1;
4014 node
= choose_good_entry_server(CIRCUIT_PURPOSE_C_GENERAL
, NULL
);
4018 entry
= tor_malloc_zero(sizeof(entry_guard_t
));
4019 log_info(LD_CIRC
, "Chose %s as new entry guard.",
4020 node_describe(node
));
4021 strlcpy(entry
->nickname
, node_get_nickname(node
), sizeof(entry
->nickname
));
4022 memcpy(entry
->identity
, node
->identity
, DIGEST_LEN
);
4023 /* Choose expiry time smudged over the past month. The goal here
4024 * is to a) spread out when Tor clients rotate their guards, so they
4025 * don't all select them on the same day, and b) avoid leaving a
4026 * precise timestamp in the state file about when we first picked
4027 * this guard. For details, see the Jan 2010 or-dev thread. */
4028 entry
->chosen_on_date
= time(NULL
) - crypto_rand_int(3600*24*30);
4029 entry
->chosen_by_version
= tor_strdup(VERSION
);
4031 smartlist_insert(entry_guards
, 0, entry
);
4033 smartlist_add(entry_guards
, entry
);
4034 control_event_guard(entry
->nickname
, entry
->identity
, "NEW");
4035 control_event_guard_deferred();
4036 log_entry_guards(LOG_INFO
);
4040 /** If the use of entry guards is configured, choose more entry guards
4041 * until we have enough in the list. */
4043 pick_entry_guards(const or_options_t
*options
)
4047 tor_assert(entry_guards
);
4049 while (num_live_entry_guards() < options
->NumEntryGuards
) {
4050 if (!add_an_entry_guard(NULL
, 0, 0))
4055 entry_guards_changed();
4058 /** How long (in seconds) do we allow an entry guard to be nonfunctional,
4059 * unlisted, excluded, or otherwise nonusable before we give up on it? */
4060 #define ENTRY_GUARD_REMOVE_AFTER (30*24*60*60)
4062 /** Release all storage held by <b>e</b>. */
4064 entry_guard_free(entry_guard_t
*e
)
4068 tor_free(e
->chosen_by_version
);
4072 /** Remove any entry guard which was selected by an unknown version of Tor,
4073 * or which was selected by a version of Tor that's known to select
4074 * entry guards badly, or which was selected more 2 months ago. */
4075 /* XXXX The "obsolete guards" and "chosen long ago guards" things should
4076 * probably be different functions. */
4078 remove_obsolete_entry_guards(time_t now
)
4082 for (i
= 0; i
< smartlist_len(entry_guards
); ++i
) {
4083 entry_guard_t
*entry
= smartlist_get(entry_guards
, i
);
4084 const char *ver
= entry
->chosen_by_version
;
4085 const char *msg
= NULL
;
4087 int version_is_bad
= 0, date_is_bad
= 0;
4089 msg
= "does not say what version of Tor it was selected by";
4091 } else if (tor_version_parse(ver
, &v
)) {
4092 msg
= "does not seem to be from any recognized version of Tor";
4095 char *tor_ver
= NULL
;
4096 tor_asprintf(&tor_ver
, "Tor %s", ver
);
4097 if ((tor_version_as_new_as(tor_ver
, "0.1.0.10-alpha") &&
4098 !tor_version_as_new_as(tor_ver
, "0.1.2.16-dev")) ||
4099 (tor_version_as_new_as(tor_ver
, "0.2.0.0-alpha") &&
4100 !tor_version_as_new_as(tor_ver
, "0.2.0.6-alpha")) ||
4101 /* above are bug 440; below are bug 1217 */
4102 (tor_version_as_new_as(tor_ver
, "0.2.1.3-alpha") &&
4103 !tor_version_as_new_as(tor_ver
, "0.2.1.23")) ||
4104 (tor_version_as_new_as(tor_ver
, "0.2.2.0-alpha") &&
4105 !tor_version_as_new_as(tor_ver
, "0.2.2.7-alpha"))) {
4106 msg
= "was selected without regard for guard bandwidth";
4111 if (!version_is_bad
&& entry
->chosen_on_date
+ 3600*24*60 < now
) {
4112 /* It's been 2 months since the date listed in our state file. */
4113 msg
= "was selected several months ago";
4117 if (version_is_bad
|| date_is_bad
) { /* we need to drop it */
4118 char dbuf
[HEX_DIGEST_LEN
+1];
4120 base16_encode(dbuf
, sizeof(dbuf
), entry
->identity
, DIGEST_LEN
);
4121 log_fn(version_is_bad
? LOG_NOTICE
: LOG_INFO
, LD_CIRC
,
4122 "Entry guard '%s' (%s) %s. (Version=%s.) Replacing it.",
4123 entry
->nickname
, dbuf
, msg
, ver
?escaped(ver
):"none");
4124 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
4125 entry_guard_free(entry
);
4126 smartlist_del_keeporder(entry_guards
, i
--);
4127 log_entry_guards(LOG_INFO
);
4132 return changed
? 1 : 0;
4135 /** Remove all entry guards that have been down or unlisted for so
4136 * long that we don't think they'll come up again. Return 1 if we
4137 * removed any, or 0 if we did nothing. */
4139 remove_dead_entry_guards(time_t now
)
4141 char dbuf
[HEX_DIGEST_LEN
+1];
4142 char tbuf
[ISO_TIME_LEN
+1];
4146 for (i
= 0; i
< smartlist_len(entry_guards
); ) {
4147 entry_guard_t
*entry
= smartlist_get(entry_guards
, i
);
4148 if (entry
->bad_since
&&
4149 ! entry
->path_bias_disabled
&&
4150 entry
->bad_since
+ ENTRY_GUARD_REMOVE_AFTER
< now
) {
4152 base16_encode(dbuf
, sizeof(dbuf
), entry
->identity
, DIGEST_LEN
);
4153 format_local_iso_time(tbuf
, entry
->bad_since
);
4154 log_info(LD_CIRC
, "Entry guard '%s' (%s) has been down or unlisted "
4155 "since %s local time; removing.",
4156 entry
->nickname
, dbuf
, tbuf
);
4157 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
4158 entry_guard_free(entry
);
4159 smartlist_del_keeporder(entry_guards
, i
);
4160 log_entry_guards(LOG_INFO
);
4165 return changed
? 1 : 0;
4168 /** A new directory or router-status has arrived; update the down/listed
4169 * status of the entry guards.
4171 * An entry is 'down' if the directory lists it as nonrunning.
4172 * An entry is 'unlisted' if the directory doesn't include it.
4174 * Don't call this on startup; only on a fresh download. Otherwise we'll
4175 * think that things are unlisted.
4178 entry_guards_compute_status(const or_options_t
*options
, time_t now
)
4181 digestmap_t
*reasons
;
4186 if (options
->EntryNodes
) /* reshuffle the entry guard list if needed */
4187 entry_nodes_should_be_added();
4189 reasons
= digestmap_new();
4190 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, entry
)
4192 const node_t
*r
= node_get_by_id(entry
->identity
);
4193 const char *reason
= NULL
;
4194 if (entry_guard_set_status(entry
, r
, now
, options
, &reason
))
4197 if (entry
->bad_since
)
4200 digestmap_set(reasons
, entry
->identity
, (char*)reason
);
4202 SMARTLIST_FOREACH_END(entry
);
4204 if (remove_dead_entry_guards(now
))
4206 if (remove_obsolete_entry_guards(now
))
4210 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, entry
) {
4211 const char *reason
= digestmap_get(reasons
, entry
->identity
);
4212 const char *live_msg
= "";
4213 const node_t
*r
= entry_is_live(entry
, 0, 1, 0, &live_msg
);
4214 log_info(LD_CIRC
, "Summary: Entry %s [%s] is %s, %s%s%s, and %s%s.",
4216 hex_str(entry
->identity
, DIGEST_LEN
),
4217 entry
->unreachable_since
? "unreachable" : "reachable",
4218 entry
->bad_since
? "unusable" : "usable",
4220 reason
? reason
: "",
4221 r
? "live" : "not live / ",
4223 } SMARTLIST_FOREACH_END(entry
);
4224 log_info(LD_CIRC
, " (%d/%d entry guards are usable/new)",
4225 num_live_entry_guards(), smartlist_len(entry_guards
));
4226 log_entry_guards(LOG_INFO
);
4227 entry_guards_changed();
4230 digestmap_free(reasons
, NULL
);
4233 /** Called when a connection to an OR with the identity digest <b>digest</b>
4234 * is established (<b>succeeded</b>==1) or has failed (<b>succeeded</b>==0).
4235 * If the OR is an entry, change that entry's up/down status.
4236 * Return 0 normally, or -1 if we want to tear down the new connection.
4238 * If <b>mark_relay_status</b>, also call router_set_status() on this
4241 * XXX023 change succeeded and mark_relay_status into 'int flags'.
4244 entry_guard_register_connect_status(const char *digest
, int succeeded
,
4245 int mark_relay_status
, time_t now
)
4248 int refuse_conn
= 0;
4249 int first_contact
= 0;
4250 entry_guard_t
*entry
= NULL
;
4252 char buf
[HEX_DIGEST_LEN
+1];
4257 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, e
) {
4259 if (tor_memeq(e
->identity
, digest
, DIGEST_LEN
)) {
4264 } SMARTLIST_FOREACH_END(e
);
4269 base16_encode(buf
, sizeof(buf
), entry
->identity
, DIGEST_LEN
);
4272 if (entry
->unreachable_since
) {
4273 log_info(LD_CIRC
, "Entry guard '%s' (%s) is now reachable again. Good.",
4274 entry
->nickname
, buf
);
4275 entry
->can_retry
= 0;
4276 entry
->unreachable_since
= 0;
4277 entry
->last_attempted
= now
;
4278 control_event_guard(entry
->nickname
, entry
->identity
, "UP");
4281 if (!entry
->made_contact
) {
4282 entry
->made_contact
= 1;
4283 first_contact
= changed
= 1;
4285 } else { /* ! succeeded */
4286 if (!entry
->made_contact
) {
4287 /* We've never connected to this one. */
4289 "Connection to never-contacted entry guard '%s' (%s) failed. "
4290 "Removing from the list. %d/%d entry guards usable/new.",
4291 entry
->nickname
, buf
,
4292 num_live_entry_guards()-1, smartlist_len(entry_guards
)-1);
4293 control_event_guard(entry
->nickname
, entry
->identity
, "DROPPED");
4294 entry_guard_free(entry
);
4295 smartlist_del_keeporder(entry_guards
, idx
);
4296 log_entry_guards(LOG_INFO
);
4298 } else if (!entry
->unreachable_since
) {
4299 log_info(LD_CIRC
, "Unable to connect to entry guard '%s' (%s). "
4300 "Marking as unreachable.", entry
->nickname
, buf
);
4301 entry
->unreachable_since
= entry
->last_attempted
= now
;
4302 control_event_guard(entry
->nickname
, entry
->identity
, "DOWN");
4304 entry
->can_retry
= 0; /* We gave it an early chance; no good. */
4306 char tbuf
[ISO_TIME_LEN
+1];
4307 format_iso_time(tbuf
, entry
->unreachable_since
);
4308 log_debug(LD_CIRC
, "Failed to connect to unreachable entry guard "
4309 "'%s' (%s). It has been unreachable since %s.",
4310 entry
->nickname
, buf
, tbuf
);
4311 entry
->last_attempted
= now
;
4312 entry
->can_retry
= 0; /* We gave it an early chance; no good. */
4316 /* if the caller asked us to, also update the is_running flags for this
4318 if (mark_relay_status
)
4319 router_set_status(digest
, succeeded
);
4321 if (first_contact
) {
4322 /* We've just added a new long-term entry guard. Perhaps the network just
4323 * came back? We should give our earlier entries another try too,
4324 * and close this connection so we don't use it before we've given
4325 * the others a shot. */
4326 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, {
4329 if (e
->made_contact
) {
4331 const node_t
*r
= entry_is_live(e
, 0, 1, 1, &msg
);
4332 if (r
&& e
->unreachable_since
) {
4340 "Connected to new entry guard '%s' (%s). Marking earlier "
4341 "entry guards up. %d/%d entry guards usable/new.",
4342 entry
->nickname
, buf
,
4343 num_live_entry_guards(), smartlist_len(entry_guards
));
4344 log_entry_guards(LOG_INFO
);
4350 entry_guards_changed();
4351 return refuse_conn
? -1 : 0;
4354 /** When we try to choose an entry guard, should we parse and add
4355 * config's EntryNodes first? */
4356 static int should_add_entry_nodes
= 0;
4358 /** Called when the value of EntryNodes changes in our configuration. */
4360 entry_nodes_should_be_added(void)
4362 log_info(LD_CIRC
, "EntryNodes config option set. Putting configured "
4363 "relays at the front of the entry guard list.");
4364 should_add_entry_nodes
= 1;
4367 /** Adjust the entry guards list so that it only contains entries from
4368 * EntryNodes, adding new entries from EntryNodes to the list as needed. */
4370 entry_guards_set_from_config(const or_options_t
*options
)
4372 smartlist_t
*entry_nodes
, *worse_entry_nodes
, *entry_fps
;
4373 smartlist_t
*old_entry_guards_on_list
, *old_entry_guards_not_on_list
;
4374 tor_assert(entry_guards
);
4376 should_add_entry_nodes
= 0;
4378 if (!options
->EntryNodes
) {
4379 /* It's possible that a controller set EntryNodes, thus making
4380 * should_add_entry_nodes set, then cleared it again, all before the
4381 * call to choose_random_entry() that triggered us. If so, just return.
4387 char *string
= routerset_to_string(options
->EntryNodes
);
4388 log_info(LD_CIRC
,"Adding configured EntryNodes '%s'.", string
);
4392 entry_nodes
= smartlist_new();
4393 worse_entry_nodes
= smartlist_new();
4394 entry_fps
= smartlist_new();
4395 old_entry_guards_on_list
= smartlist_new();
4396 old_entry_guards_not_on_list
= smartlist_new();
4398 /* Split entry guards into those on the list and those not. */
4400 routerset_get_all_nodes(entry_nodes
, options
->EntryNodes
,
4401 options
->ExcludeNodes
, 0);
4402 SMARTLIST_FOREACH(entry_nodes
, const node_t
*,node
,
4403 smartlist_add(entry_fps
, (void*)node
->identity
));
4405 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
, {
4406 if (smartlist_digest_isin(entry_fps
, e
->identity
))
4407 smartlist_add(old_entry_guards_on_list
, e
);
4409 smartlist_add(old_entry_guards_not_on_list
, e
);
4412 /* Remove all currently configured guard nodes, excluded nodes, unreachable
4413 * nodes, or non-Guard nodes from entry_nodes. */
4414 SMARTLIST_FOREACH_BEGIN(entry_nodes
, const node_t
*, node
) {
4415 if (entry_guard_get_by_id_digest(node
->identity
)) {
4416 SMARTLIST_DEL_CURRENT(entry_nodes
, node
);
4418 } else if (routerset_contains_node(options
->ExcludeNodes
, node
)) {
4419 SMARTLIST_DEL_CURRENT(entry_nodes
, node
);
4421 } else if (!fascist_firewall_allows_node(node
)) {
4422 SMARTLIST_DEL_CURRENT(entry_nodes
, node
);
4424 } else if (! node
->is_possible_guard
) {
4425 smartlist_add(worse_entry_nodes
, (node_t
*)node
);
4426 SMARTLIST_DEL_CURRENT(entry_nodes
, node
);
4428 } SMARTLIST_FOREACH_END(node
);
4430 /* Now build the new entry_guards list. */
4431 smartlist_clear(entry_guards
);
4432 /* First, the previously configured guards that are in EntryNodes. */
4433 smartlist_add_all(entry_guards
, old_entry_guards_on_list
);
4434 /* Next, scramble the rest of EntryNodes, putting the guards first. */
4435 smartlist_shuffle(entry_nodes
);
4436 smartlist_shuffle(worse_entry_nodes
);
4437 smartlist_add_all(entry_nodes
, worse_entry_nodes
);
4439 /* Next, the rest of EntryNodes */
4440 SMARTLIST_FOREACH_BEGIN(entry_nodes
, const node_t
*, node
) {
4441 add_an_entry_guard(node
, 0, 0);
4442 if (smartlist_len(entry_guards
) > options
->NumEntryGuards
* 10)
4444 } SMARTLIST_FOREACH_END(node
);
4445 log_notice(LD_GENERAL
, "%d entries in guards", smartlist_len(entry_guards
));
4446 /* Finally, free the remaining previously configured guards that are not in
4448 SMARTLIST_FOREACH(old_entry_guards_not_on_list
, entry_guard_t
*, e
,
4449 entry_guard_free(e
));
4451 smartlist_free(entry_nodes
);
4452 smartlist_free(worse_entry_nodes
);
4453 smartlist_free(entry_fps
);
4454 smartlist_free(old_entry_guards_on_list
);
4455 smartlist_free(old_entry_guards_not_on_list
);
4456 entry_guards_changed();
4459 /** Return 0 if we're fine adding arbitrary routers out of the
4460 * directory to our entry guard list, or return 1 if we have a
4461 * list already and we must stick to it.
4464 entry_list_is_constrained(const or_options_t
*options
)
4466 if (options
->EntryNodes
)
4468 if (options
->UseBridges
)
4473 /** Pick a live (up and listed) entry guard from entry_guards. If
4474 * <b>state</b> is non-NULL, this is for a specific circuit --
4475 * make sure not to pick this circuit's exit or any node in the
4476 * exit's family. If <b>state</b> is NULL, we're looking for a random
4477 * guard (likely a bridge). */
4479 choose_random_entry(cpath_build_state_t
*state
)
4481 const or_options_t
*options
= get_options();
4482 smartlist_t
*live_entry_guards
= smartlist_new();
4483 smartlist_t
*exit_family
= smartlist_new();
4484 const node_t
*chosen_exit
=
4485 state
?build_state_get_exit_node(state
) : NULL
;
4486 const node_t
*node
= NULL
;
4487 int need_uptime
= state
? state
->need_uptime
: 0;
4488 int need_capacity
= state
? state
->need_capacity
: 0;
4489 int preferred_min
, consider_exit_family
= 0;
4492 nodelist_add_node_and_family(exit_family
, chosen_exit
);
4493 consider_exit_family
= 1;
4497 entry_guards
= smartlist_new();
4499 if (should_add_entry_nodes
)
4500 entry_guards_set_from_config(options
);
4502 if (!entry_list_is_constrained(options
) &&
4503 smartlist_len(entry_guards
) < options
->NumEntryGuards
)
4504 pick_entry_guards(options
);
4507 smartlist_clear(live_entry_guards
);
4508 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, entry
) {
4510 node
= entry_is_live(entry
, need_uptime
, need_capacity
, 0, &msg
);
4512 continue; /* down, no point */
4513 if (node
== chosen_exit
)
4514 continue; /* don't pick the same node for entry and exit */
4515 if (consider_exit_family
&& smartlist_isin(exit_family
, node
))
4516 continue; /* avoid relays that are family members of our exit */
4517 #if 0 /* since EntryNodes is always strict now, this clause is moot */
4518 if (options
->EntryNodes
&&
4519 !routerset_contains_node(options
->EntryNodes
, node
)) {
4520 /* We've come to the end of our preferred entry nodes. */
4521 if (smartlist_len(live_entry_guards
))
4522 goto choose_and_finish
; /* only choose from the ones we like */
4523 if (options
->StrictNodes
) {
4524 /* in theory this case should never happen, since
4525 * entry_guards_set_from_config() drops unwanted relays */
4526 tor_fragile_assert();
4529 "No relays from EntryNodes available. Using others.");
4533 smartlist_add(live_entry_guards
, (void*)node
);
4534 if (!entry
->made_contact
) {
4535 /* Always start with the first not-yet-contacted entry
4536 * guard. Otherwise we might add several new ones, pick
4537 * the second new one, and now we've expanded our entry
4538 * guard list without needing to. */
4539 goto choose_and_finish
;
4541 if (smartlist_len(live_entry_guards
) >= options
->NumEntryGuards
)
4542 goto choose_and_finish
; /* we have enough */
4543 } SMARTLIST_FOREACH_END(entry
);
4545 if (entry_list_is_constrained(options
)) {
4546 /* If we prefer the entry nodes we've got, and we have at least
4547 * one choice, that's great. Use it. */
4550 /* Try to have at least 2 choices available. This way we don't
4551 * get stuck with a single live-but-crummy entry and just keep
4553 * (We might get 2 live-but-crummy entry guards, but so be it.) */
4557 if (smartlist_len(live_entry_guards
) < preferred_min
) {
4558 if (!entry_list_is_constrained(options
)) {
4559 /* still no? try adding a new entry then */
4560 /* XXX if guard doesn't imply fast and stable, then we need
4561 * to tell add_an_entry_guard below what we want, or it might
4562 * be a long time til we get it. -RD */
4563 node
= add_an_entry_guard(NULL
, 0, 0);
4565 entry_guards_changed();
4566 /* XXX we start over here in case the new node we added shares
4567 * a family with our exit node. There's a chance that we'll just
4568 * load up on entry guards here, if the network we're using is
4569 * one big family. Perhaps we should teach add_an_entry_guard()
4570 * to understand nodes-to-avoid-if-possible? -RD */
4574 if (!node
&& need_uptime
) {
4575 need_uptime
= 0; /* try without that requirement */
4578 if (!node
&& need_capacity
) {
4579 /* still no? last attempt, try without requiring capacity */
4584 /* Removing this retry logic: if we only allow one exit, and it is in the
4585 same family as all our entries, then we are just plain not going to win
4587 if (!node
&& entry_list_is_constrained(options
) && consider_exit_family
) {
4588 /* still no? if we're using bridges or have strictentrynodes
4589 * set, and our chosen exit is in the same family as all our
4590 * bridges/entry guards, then be flexible about families. */
4591 consider_exit_family
= 0;
4595 /* live_entry_guards may be empty below. Oh well, we tried. */
4599 if (entry_list_is_constrained(options
)) {
4600 /* We need to weight by bandwidth, because our bridges or entryguards
4601 * were not already selected proportional to their bandwidth. */
4602 node
= node_sl_choose_by_bandwidth(live_entry_guards
, WEIGHT_FOR_GUARD
);
4604 /* We choose uniformly at random here, because choose_good_entry_server()
4605 * already weights its choices by bandwidth, so we don't want to
4606 * *double*-weight our guard selection. */
4607 node
= smartlist_choose(live_entry_guards
);
4609 smartlist_free(live_entry_guards
);
4610 smartlist_free(exit_family
);
4614 /** Parse <b>state</b> and learn about the entry guards it describes.
4615 * If <b>set</b> is true, and there are no errors, replace the global
4616 * entry_list with what we find.
4617 * On success, return 0. On failure, alloc into *<b>msg</b> a string
4618 * describing the error, and return -1.
4621 entry_guards_parse_state(or_state_t
*state
, int set
, char **msg
)
4623 entry_guard_t
*node
= NULL
;
4624 smartlist_t
*new_entry_guards
= smartlist_new();
4625 config_line_t
*line
;
4626 time_t now
= time(NULL
);
4627 const char *state_version
= state
->TorVersion
;
4628 digestmap_t
*added_by
= digestmap_new();
4631 for (line
= state
->EntryGuards
; line
; line
= line
->next
) {
4632 if (!strcasecmp(line
->key
, "EntryGuard")) {
4633 smartlist_t
*args
= smartlist_new();
4634 node
= tor_malloc_zero(sizeof(entry_guard_t
));
4635 /* all entry guards on disk have been contacted */
4636 node
->made_contact
= 1;
4637 smartlist_add(new_entry_guards
, node
);
4638 smartlist_split_string(args
, line
->value
, " ",
4639 SPLIT_SKIP_SPACE
|SPLIT_IGNORE_BLANK
, 0);
4640 if (smartlist_len(args
)<2) {
4641 *msg
= tor_strdup("Unable to parse entry nodes: "
4642 "Too few arguments to EntryGuard");
4643 } else if (!is_legal_nickname(smartlist_get(args
,0))) {
4644 *msg
= tor_strdup("Unable to parse entry nodes: "
4645 "Bad nickname for EntryGuard");
4647 strlcpy(node
->nickname
, smartlist_get(args
,0), MAX_NICKNAME_LEN
+1);
4648 if (base16_decode(node
->identity
, DIGEST_LEN
, smartlist_get(args
,1),
4649 strlen(smartlist_get(args
,1)))<0) {
4650 *msg
= tor_strdup("Unable to parse entry nodes: "
4651 "Bad hex digest for EntryGuard");
4654 SMARTLIST_FOREACH(args
, char*, cp
, tor_free(cp
));
4655 smartlist_free(args
);
4658 } else if (!strcasecmp(line
->key
, "EntryGuardDownSince") ||
4659 !strcasecmp(line
->key
, "EntryGuardUnlistedSince")) {
4661 time_t last_try
= 0;
4663 *msg
= tor_strdup("Unable to parse entry nodes: "
4664 "EntryGuardDownSince/UnlistedSince without EntryGuard");
4667 if (parse_iso_time(line
->value
, &when
)<0) {
4668 *msg
= tor_strdup("Unable to parse entry nodes: "
4669 "Bad time in EntryGuardDownSince/UnlistedSince");
4673 /* It's a bad idea to believe info in the future: you can wind
4674 * up with timeouts that aren't allowed to happen for years. */
4677 if (strlen(line
->value
) >= ISO_TIME_LEN
+ISO_TIME_LEN
+1) {
4678 /* ignore failure */
4679 (void) parse_iso_time(line
->value
+ISO_TIME_LEN
+1, &last_try
);
4681 if (!strcasecmp(line
->key
, "EntryGuardDownSince")) {
4682 node
->unreachable_since
= when
;
4683 node
->last_attempted
= last_try
;
4685 node
->bad_since
= when
;
4687 } else if (!strcasecmp(line
->key
, "EntryGuardAddedBy")) {
4689 /* format is digest version date */
4690 if (strlen(line
->value
) < HEX_DIGEST_LEN
+1+1+1+ISO_TIME_LEN
) {
4691 log_warn(LD_BUG
, "EntryGuardAddedBy line is not long enough.");
4694 if (base16_decode(d
, sizeof(d
), line
->value
, HEX_DIGEST_LEN
)<0 ||
4695 line
->value
[HEX_DIGEST_LEN
] != ' ') {
4696 log_warn(LD_BUG
, "EntryGuardAddedBy line %s does not begin with "
4697 "hex digest", escaped(line
->value
));
4700 digestmap_set(added_by
, d
, tor_strdup(line
->value
+HEX_DIGEST_LEN
+1));
4701 } else if (!strcasecmp(line
->key
, "EntryGuardPathBias")) {
4702 const or_options_t
*options
= get_options();
4703 unsigned hop_cnt
, success_cnt
;
4705 if (tor_sscanf(line
->value
, "%u %u", &success_cnt
, &hop_cnt
) != 2) {
4706 log_warn(LD_GENERAL
, "Unable to parse guard path bias info: "
4707 "Misformated EntryGuardPathBias %s", escaped(line
->value
));
4711 node
->first_hops
= hop_cnt
;
4712 node
->circuit_successes
= success_cnt
;
4713 log_info(LD_GENERAL
, "Read %u/%u path bias for node %s",
4714 node
->circuit_successes
, node
->first_hops
, node
->nickname
);
4715 /* Note: We rely on the < comparison here to allow us to set a 0
4716 * rate and disable the feature entirely. If refactoring, don't
4718 if (node
->circuit_successes
/((double)node
->first_hops
)
4719 < pathbias_get_disable_rate(options
)) {
4720 node
->path_bias_disabled
= 1;
4721 log_info(LD_GENERAL
,
4722 "Path bias is too high (%u/%u); disabling node %s",
4723 node
->circuit_successes
, node
->first_hops
, node
->nickname
);
4727 log_warn(LD_BUG
, "Unexpected key %s", line
->key
);
4731 SMARTLIST_FOREACH(new_entry_guards
, entry_guard_t
*, e
,
4734 char *val
= digestmap_get(added_by
, e
->identity
);
4735 if (val
&& (sp
= strchr(val
, ' '))) {
4738 if (parse_iso_time(sp
, &when
)<0) {
4739 log_warn(LD_BUG
, "Can't read time %s in EntryGuardAddedBy", sp
);
4741 e
->chosen_by_version
= tor_strdup(val
);
4742 e
->chosen_on_date
= when
;
4745 if (state_version
) {
4746 e
->chosen_by_version
= tor_strdup(state_version
);
4747 e
->chosen_on_date
= time(NULL
) - crypto_rand_int(3600*24*30);
4750 if (node
->path_bias_disabled
&& !node
->bad_since
)
4751 node
->bad_since
= time(NULL
);
4755 SMARTLIST_FOREACH(new_entry_guards
, entry_guard_t
*, e
,
4756 entry_guard_free(e
));
4757 smartlist_free(new_entry_guards
);
4758 } else { /* !err && set */
4760 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
4761 entry_guard_free(e
));
4762 smartlist_free(entry_guards
);
4764 entry_guards
= new_entry_guards
;
4765 entry_guards_dirty
= 0;
4766 /* XXX023 hand new_entry_guards to this func, and move it up a
4767 * few lines, so we don't have to re-dirty it */
4768 if (remove_obsolete_entry_guards(now
))
4769 entry_guards_dirty
= 1;
4771 digestmap_free(added_by
, _tor_free
);
4772 return *msg
? -1 : 0;
4775 /** Our list of entry guards has changed, or some element of one
4776 * of our entry guards has changed. Write the changes to disk within
4777 * the next few minutes.
4780 entry_guards_changed(void)
4783 entry_guards_dirty
= 1;
4785 /* or_state_save() will call entry_guards_update_state(). */
4786 when
= get_options()->AvoidDiskWrites
? time(NULL
) + 3600 : time(NULL
)+600;
4787 or_state_mark_dirty(get_or_state(), when
);
4790 /** If the entry guard info has not changed, do nothing and return.
4791 * Otherwise, free the EntryGuards piece of <b>state</b> and create
4792 * a new one out of the global entry_guards list, and then mark
4793 * <b>state</b> dirty so it will get saved to disk.
4796 entry_guards_update_state(or_state_t
*state
)
4798 config_line_t
**next
, *line
;
4799 if (! entry_guards_dirty
)
4802 config_free_lines(state
->EntryGuards
);
4803 next
= &state
->EntryGuards
;
4806 entry_guards
= smartlist_new();
4807 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
4809 char dbuf
[HEX_DIGEST_LEN
+1];
4810 if (!e
->made_contact
)
4811 continue; /* don't write this one to disk */
4812 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
4813 line
->key
= tor_strdup("EntryGuard");
4814 base16_encode(dbuf
, sizeof(dbuf
), e
->identity
, DIGEST_LEN
);
4815 tor_asprintf(&line
->value
, "%s %s", e
->nickname
, dbuf
);
4816 next
= &(line
->next
);
4817 if (e
->unreachable_since
) {
4818 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
4819 line
->key
= tor_strdup("EntryGuardDownSince");
4820 line
->value
= tor_malloc(ISO_TIME_LEN
+1+ISO_TIME_LEN
+1);
4821 format_iso_time(line
->value
, e
->unreachable_since
);
4822 if (e
->last_attempted
) {
4823 line
->value
[ISO_TIME_LEN
] = ' ';
4824 format_iso_time(line
->value
+ISO_TIME_LEN
+1, e
->last_attempted
);
4826 next
= &(line
->next
);
4829 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
4830 line
->key
= tor_strdup("EntryGuardUnlistedSince");
4831 line
->value
= tor_malloc(ISO_TIME_LEN
+1);
4832 format_iso_time(line
->value
, e
->bad_since
);
4833 next
= &(line
->next
);
4835 if (e
->chosen_on_date
&& e
->chosen_by_version
&&
4836 !strchr(e
->chosen_by_version
, ' ')) {
4837 char d
[HEX_DIGEST_LEN
+1];
4838 char t
[ISO_TIME_LEN
+1];
4839 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
4840 line
->key
= tor_strdup("EntryGuardAddedBy");
4841 base16_encode(d
, sizeof(d
), e
->identity
, DIGEST_LEN
);
4842 format_iso_time(t
, e
->chosen_on_date
);
4843 tor_asprintf(&line
->value
, "%s %s %s",
4844 d
, e
->chosen_by_version
, t
);
4845 next
= &(line
->next
);
4847 if (e
->first_hops
) {
4848 *next
= line
= tor_malloc_zero(sizeof(config_line_t
));
4849 line
->key
= tor_strdup("EntryGuardPathBias");
4850 tor_asprintf(&line
->value
, "%u %u",
4851 e
->circuit_successes
, e
->first_hops
);
4852 next
= &(line
->next
);
4856 if (!get_options()->AvoidDiskWrites
)
4857 or_state_mark_dirty(get_or_state(), 0);
4858 entry_guards_dirty
= 0;
4861 /** If <b>question</b> is the string "entry-guards", then dump
4862 * to *<b>answer</b> a newly allocated string describing all of
4863 * the nodes in the global entry_guards list. See control-spec.txt
4865 * For backward compatibility, we also handle the string "helper-nodes".
4868 getinfo_helper_entry_guards(control_connection_t
*conn
,
4869 const char *question
, char **answer
,
4870 const char **errmsg
)
4875 if (!strcmp(question
,"entry-guards") ||
4876 !strcmp(question
,"helper-nodes")) {
4877 smartlist_t
*sl
= smartlist_new();
4878 char tbuf
[ISO_TIME_LEN
+1];
4879 char nbuf
[MAX_VERBOSE_NICKNAME_LEN
+1];
4881 entry_guards
= smartlist_new();
4882 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, e
) {
4883 const char *status
= NULL
;
4887 if (!e
->made_contact
) {
4888 status
= "never-connected";
4889 } else if (e
->bad_since
) {
4890 when
= e
->bad_since
;
4891 status
= "unusable";
4896 node
= node_get_by_id(e
->identity
);
4898 node_get_verbose_nickname(node
, nbuf
);
4901 base16_encode(nbuf
+1, sizeof(nbuf
)-1, e
->identity
, DIGEST_LEN
);
4902 /* e->nickname field is not very reliable if we don't know about
4903 * this router any longer; don't include it. */
4907 format_iso_time(tbuf
, when
);
4908 smartlist_add_asprintf(sl
, "%s %s %s\n", nbuf
, status
, tbuf
);
4910 smartlist_add_asprintf(sl
, "%s %s\n", nbuf
, status
);
4912 } SMARTLIST_FOREACH_END(e
);
4913 *answer
= smartlist_join_strings(sl
, "", 0, NULL
);
4914 SMARTLIST_FOREACH(sl
, char *, c
, tor_free(c
));
4920 /** A list of configured bridges. Whenever we actually get a descriptor
4921 * for one, we add it as an entry guard. Note that the order of bridges
4922 * in this list does not necessarily correspond to the order of bridges
4924 static smartlist_t
*bridge_list
= NULL
;
4926 /** Mark every entry of the bridge list to be removed on our next call to
4927 * sweep_bridge_list unless it has first been un-marked. */
4929 mark_bridge_list(void)
4932 bridge_list
= smartlist_new();
4933 SMARTLIST_FOREACH(bridge_list
, bridge_info_t
*, b
,
4934 b
->marked_for_removal
= 1);
4937 /** Remove every entry of the bridge list that was marked with
4938 * mark_bridge_list if it has not subsequently been un-marked. */
4940 sweep_bridge_list(void)
4943 bridge_list
= smartlist_new();
4944 SMARTLIST_FOREACH_BEGIN(bridge_list
, bridge_info_t
*, b
) {
4945 if (b
->marked_for_removal
) {
4946 SMARTLIST_DEL_CURRENT(bridge_list
, b
);
4949 } SMARTLIST_FOREACH_END(b
);
4952 /** Initialize the bridge list to empty, creating it if needed. */
4954 clear_bridge_list(void)
4957 bridge_list
= smartlist_new();
4958 SMARTLIST_FOREACH(bridge_list
, bridge_info_t
*, b
, bridge_free(b
));
4959 smartlist_clear(bridge_list
);
4962 /** Free the bridge <b>bridge</b>. */
4964 bridge_free(bridge_info_t
*bridge
)
4969 tor_free(bridge
->transport_name
);
4973 /** A list of pluggable transports found in torrc. */
4974 static smartlist_t
*transport_list
= NULL
;
4976 /** Mark every entry of the transport list to be removed on our next call to
4977 * sweep_transport_list unless it has first been un-marked. */
4979 mark_transport_list(void)
4981 if (!transport_list
)
4982 transport_list
= smartlist_new();
4983 SMARTLIST_FOREACH(transport_list
, transport_t
*, t
,
4984 t
->marked_for_removal
= 1);
4987 /** Remove every entry of the transport list that was marked with
4988 * mark_transport_list if it has not subsequently been un-marked. */
4990 sweep_transport_list(void)
4992 if (!transport_list
)
4993 transport_list
= smartlist_new();
4994 SMARTLIST_FOREACH_BEGIN(transport_list
, transport_t
*, t
) {
4995 if (t
->marked_for_removal
) {
4996 SMARTLIST_DEL_CURRENT(transport_list
, t
);
4999 } SMARTLIST_FOREACH_END(t
);
5002 /** Initialize the pluggable transports list to empty, creating it if
5005 clear_transport_list(void)
5007 if (!transport_list
)
5008 transport_list
= smartlist_new();
5009 SMARTLIST_FOREACH(transport_list
, transport_t
*, t
, transport_free(t
));
5010 smartlist_clear(transport_list
);
5013 /** Free the pluggable transport struct <b>transport</b>. */
5015 transport_free(transport_t
*transport
)
5020 tor_free(transport
->name
);
5021 tor_free(transport
);
5024 /** Returns the transport in our transport list that has the name <b>name</b>.
5025 * Else returns NULL. */
5027 transport_get_by_name(const char *name
)
5031 if (!transport_list
)
5034 SMARTLIST_FOREACH_BEGIN(transport_list
, transport_t
*, transport
) {
5035 if (!strcmp(transport
->name
, name
))
5037 } SMARTLIST_FOREACH_END(transport
);
5042 /** Returns a transport_t struct for a transport proxy supporting the
5043 protocol <b>name</b> listening at <b>addr</b>:<b>port</b> using
5044 SOCKS version <b>socks_ver</b>. */
5046 transport_new(const tor_addr_t
*addr
, uint16_t port
,
5047 const char *name
, int socks_ver
)
5049 transport_t
*t
= tor_malloc_zero(sizeof(transport_t
));
5051 tor_addr_copy(&t
->addr
, addr
);
5053 t
->name
= tor_strdup(name
);
5054 t
->socks_version
= socks_ver
;
5059 /** Resolve any conflicts that the insertion of transport <b>t</b>
5061 * Return 0 if <b>t</b> is OK and should be registered, 1 if there is
5062 * a transport identical to <b>t</b> already registered and -1 if
5063 * <b>t</b> cannot be added due to conflicts. */
5065 transport_resolve_conflicts(transport_t
*t
)
5067 /* This is how we resolve transport conflicts:
5069 If there is already a transport with the same name and addrport,
5070 we either have duplicate torrc lines OR we are here post-HUP and
5071 this transport was here pre-HUP as well. In any case, mark the
5072 old transport so that it doesn't get removed and ignore the new
5073 one. Our caller has to free the new transport so we return '1' to
5076 If there is already a transport with the same name but different
5078 * if it's marked for removal, it means that it either has a lower
5079 priority than 't' in torrc (otherwise the mark would have been
5080 cleared by the paragraph above), or it doesn't exist at all in
5081 the post-HUP torrc. We destroy the old transport and register 't'.
5082 * if it's *not* marked for removal, it means that it was newly
5083 added in the post-HUP torrc or that it's of higher priority, in
5084 this case we ignore 't'. */
5085 transport_t
*t_tmp
= transport_get_by_name(t
->name
);
5086 if (t_tmp
) { /* same name */
5087 if (tor_addr_eq(&t
->addr
, &t_tmp
->addr
) && (t
->port
== t_tmp
->port
)) {
5088 /* same name *and* addrport */
5089 t_tmp
->marked_for_removal
= 0;
5091 } else { /* same name but different addrport */
5092 if (t_tmp
->marked_for_removal
) { /* marked for removal */
5093 log_notice(LD_GENERAL
, "You tried to add transport '%s' at '%s:%u' "
5094 "but there was already a transport marked for deletion at "
5095 "'%s:%u'. We deleted the old transport and registered the "
5096 "new one.", t
->name
, fmt_addr(&t
->addr
), t
->port
,
5097 fmt_addr(&t_tmp
->addr
), t_tmp
->port
);
5098 smartlist_remove(transport_list
, t_tmp
);
5099 transport_free(t_tmp
);
5100 } else { /* *not* marked for removal */
5101 log_notice(LD_GENERAL
, "You tried to add transport '%s' at '%s:%u' "
5102 "but the same transport already exists at '%s:%u'. "
5103 "Skipping.", t
->name
, fmt_addr(&t
->addr
), t
->port
,
5104 fmt_addr(&t_tmp
->addr
), t_tmp
->port
);
5113 /** Add transport <b>t</b> to the internal list of pluggable
5115 * Returns 0 if the transport was added correctly, 1 if the same
5116 * transport was already registered (in this case the caller must
5117 * free the transport) and -1 if there was an error. */
5119 transport_add(transport_t
*t
)
5124 r
= transport_resolve_conflicts(t
);
5127 case 0: /* should register transport */
5128 if (!transport_list
)
5129 transport_list
= smartlist_new();
5130 smartlist_add(transport_list
, t
);
5132 default: /* let our caller know the return code */
5137 /** Remember a new pluggable transport proxy at <b>addr</b>:<b>port</b>.
5138 * <b>name</b> is set to the name of the protocol this proxy uses.
5139 * <b>socks_ver</b> is set to the SOCKS version of the proxy. */
5141 transport_add_from_config(const tor_addr_t
*addr
, uint16_t port
,
5142 const char *name
, int socks_ver
)
5144 transport_t
*t
= transport_new(addr
, port
, name
, socks_ver
);
5146 int r
= transport_add(t
);
5151 log_notice(LD_GENERAL
, "Could not add transport %s at %s:%u. Skipping.",
5152 t
->name
, fmt_addr(&t
->addr
), t
->port
);
5156 log_info(LD_GENERAL
, "Succesfully registered transport %s at %s:%u.",
5157 t
->name
, fmt_addr(&t
->addr
), t
->port
);
5158 transport_free(t
); /* falling */
5161 log_info(LD_GENERAL
, "Succesfully registered transport %s at %s:%u.",
5162 t
->name
, fmt_addr(&t
->addr
), t
->port
);
5167 /** Return a bridge pointer if <b>ri</b> is one of our known bridges
5168 * (either by comparing keys if possible, else by comparing addr/port).
5169 * Else return NULL. */
5170 static bridge_info_t
*
5171 get_configured_bridge_by_addr_port_digest(const tor_addr_t
*addr
,
5177 SMARTLIST_FOREACH_BEGIN(bridge_list
, bridge_info_t
*, bridge
)
5179 if (tor_digest_is_zero(bridge
->identity
) &&
5180 !tor_addr_compare(&bridge
->addr
, addr
, CMP_EXACT
) &&
5181 bridge
->port
== port
)
5183 if (digest
&& tor_memeq(bridge
->identity
, digest
, DIGEST_LEN
))
5186 SMARTLIST_FOREACH_END(bridge
);
5190 /** Wrapper around get_configured_bridge_by_addr_port_digest() to look
5191 * it up via router descriptor <b>ri</b>. */
5192 static bridge_info_t
*
5193 get_configured_bridge_by_routerinfo(const routerinfo_t
*ri
)
5197 router_get_pref_orport(ri
, &ap
);
5198 return get_configured_bridge_by_addr_port_digest(&ap
.addr
, ap
.port
,
5199 ri
->cache_info
.identity_digest
);
5202 /** Return 1 if <b>ri</b> is one of our known bridges, else 0. */
5204 routerinfo_is_a_configured_bridge(const routerinfo_t
*ri
)
5206 return get_configured_bridge_by_routerinfo(ri
) ? 1 : 0;
5209 /** Return 1 if <b>node</b> is one of our configured bridges, else 0. */
5211 node_is_a_configured_bridge(const node_t
*node
)
5213 int retval
= 0; /* Negative. */
5214 smartlist_t
*orports
= NULL
;
5219 orports
= node_get_all_orports(node
);
5220 if (orports
== NULL
)
5223 SMARTLIST_FOREACH_BEGIN(orports
, tor_addr_port_t
*, orport
) {
5224 if (get_configured_bridge_by_addr_port_digest(&orport
->addr
, orport
->port
,
5225 node
->identity
) != NULL
) {
5229 } SMARTLIST_FOREACH_END(orport
);
5232 if (orports
!= NULL
) {
5233 SMARTLIST_FOREACH(orports
, tor_addr_port_t
*, p
, tor_free(p
));
5234 smartlist_free(orports
);
5240 /** We made a connection to a router at <b>addr</b>:<b>port</b>
5241 * without knowing its digest. Its digest turned out to be <b>digest</b>.
5242 * If it was a bridge, and we still don't know its digest, record it.
5245 learned_router_identity(const tor_addr_t
*addr
, uint16_t port
,
5248 bridge_info_t
*bridge
=
5249 get_configured_bridge_by_addr_port_digest(addr
, port
, digest
);
5250 if (bridge
&& tor_digest_is_zero(bridge
->identity
)) {
5251 memcpy(bridge
->identity
, digest
, DIGEST_LEN
);
5252 log_notice(LD_DIR
, "Learned fingerprint %s for bridge %s:%d",
5253 hex_str(digest
, DIGEST_LEN
), fmt_addr(addr
), port
);
5257 /** Return true if <b>bridge</b> has the same identity digest as
5258 * <b>digest</b>. If <b>digest</b> is NULL, it matches
5259 * bridges with unspecified identity digests. */
5261 bridge_has_digest(const bridge_info_t
*bridge
, const char *digest
)
5264 return tor_memeq(digest
, bridge
->identity
, DIGEST_LEN
);
5266 return tor_digest_is_zero(bridge
->identity
);
5269 /** We are about to add a new bridge at <b>addr</b>:<b>port</b>, with optional
5270 * <b>digest</b> and <b>transport_name</b>. Mark for removal any previously
5271 * existing bridge with the same address and port, and warn the user as
5275 bridge_resolve_conflicts(const tor_addr_t
*addr
, uint16_t port
,
5276 const char *digest
, const char *transport_name
)
5278 /* Iterate the already-registered bridge list:
5280 If you find a bridge with the same adress and port, mark it for
5281 removal. It doesn't make sense to have two active bridges with
5282 the same IP:PORT. If the bridge in question has a different
5283 digest or transport than <b>digest</b>/<b>transport_name</b>,
5284 it's probably a misconfiguration and we should warn the user.
5286 SMARTLIST_FOREACH_BEGIN(bridge_list
, bridge_info_t
*, bridge
) {
5287 if (bridge
->marked_for_removal
)
5290 if (tor_addr_eq(&bridge
->addr
, addr
) && (bridge
->port
== port
)) {
5292 bridge
->marked_for_removal
= 1;
5294 if (!bridge_has_digest(bridge
, digest
) ||
5295 strcmp_opt(bridge
->transport_name
, transport_name
)) {
5297 char *bridge_description_new
, *bridge_description_old
;
5298 tor_asprintf(&bridge_description_new
, "%s:%u:%s:%s",
5299 fmt_addr(addr
), port
,
5300 digest
? hex_str(digest
, DIGEST_LEN
) : "",
5301 transport_name
? transport_name
: "");
5302 tor_asprintf(&bridge_description_old
, "%s:%u:%s:%s",
5303 fmt_addr(&bridge
->addr
), bridge
->port
,
5304 tor_digest_is_zero(bridge
->identity
) ?
5305 "" : hex_str(bridge
->identity
,DIGEST_LEN
),
5306 bridge
->transport_name
? bridge
->transport_name
: "");
5308 log_warn(LD_GENERAL
,"Tried to add bridge '%s', but we found a conflict"
5309 " with the already registered bridge '%s'. We will discard"
5310 " the old bridge and keep '%s'. If this is not what you"
5311 " wanted, please change your configuration file accordingly.",
5312 bridge_description_new
, bridge_description_old
,
5313 bridge_description_new
);
5315 tor_free(bridge_description_new
);
5316 tor_free(bridge_description_old
);
5319 } SMARTLIST_FOREACH_END(bridge
);
5322 /** Remember a new bridge at <b>addr</b>:<b>port</b>. If <b>digest</b>
5323 * is set, it tells us the identity key too. If we already had the
5324 * bridge in our list, unmark it, and don't actually add anything new.
5325 * If <b>transport_name</b> is non-NULL - the bridge is associated with a
5326 * pluggable transport - we assign the transport to the bridge. */
5328 bridge_add_from_config(const tor_addr_t
*addr
, uint16_t port
,
5329 const char *digest
, const char *transport_name
)
5333 bridge_resolve_conflicts(addr
, port
, digest
, transport_name
);
5335 b
= tor_malloc_zero(sizeof(bridge_info_t
));
5336 tor_addr_copy(&b
->addr
, addr
);
5339 memcpy(b
->identity
, digest
, DIGEST_LEN
);
5341 b
->transport_name
= tor_strdup(transport_name
);
5342 b
->fetch_status
.schedule
= DL_SCHED_BRIDGE
;
5344 bridge_list
= smartlist_new();
5346 smartlist_add(bridge_list
, b
);
5349 /** Return true iff <b>routerset</b> contains the bridge <b>bridge</b>. */
5351 routerset_contains_bridge(const routerset_t
*routerset
,
5352 const bridge_info_t
*bridge
)
5355 extend_info_t
*extinfo
;
5360 extinfo
= extend_info_alloc(
5361 NULL
, bridge
->identity
, NULL
, &bridge
->addr
, bridge
->port
);
5362 result
= routerset_contains_extendinfo(routerset
, extinfo
);
5363 extend_info_free(extinfo
);
5367 /** If <b>digest</b> is one of our known bridges, return it. */
5368 static bridge_info_t
*
5369 find_bridge_by_digest(const char *digest
)
5371 SMARTLIST_FOREACH(bridge_list
, bridge_info_t
*, bridge
,
5373 if (tor_memeq(bridge
->identity
, digest
, DIGEST_LEN
))
5379 /* DOCDOC find_transport_name_by_bridge_addrport */
5381 find_transport_name_by_bridge_addrport(const tor_addr_t
*addr
, uint16_t port
)
5386 SMARTLIST_FOREACH_BEGIN(bridge_list
, const bridge_info_t
*, bridge
) {
5387 if (tor_addr_eq(&bridge
->addr
, addr
) &&
5388 (bridge
->port
== port
))
5389 return bridge
->transport_name
;
5390 } SMARTLIST_FOREACH_END(bridge
);
5395 /** If <b>addr</b> and <b>port</b> match the address and port of a
5396 * bridge of ours that uses pluggable transports, place its transport
5397 * in <b>transport</b>.
5399 * Return 0 on success (found a transport, or found a bridge with no
5400 * transport, or found no bridge); return -1 if we should be using a
5401 * transport, but the transport could not be found.
5404 find_transport_by_bridge_addrport(const tor_addr_t
*addr
, uint16_t port
,
5405 const transport_t
**transport
)
5411 SMARTLIST_FOREACH_BEGIN(bridge_list
, const bridge_info_t
*, bridge
) {
5412 if (tor_addr_eq(&bridge
->addr
, addr
) &&
5413 (bridge
->port
== port
)) { /* bridge matched */
5414 if (bridge
->transport_name
) { /* it also uses pluggable transports */
5415 *transport
= transport_get_by_name(bridge
->transport_name
);
5416 if (*transport
== NULL
) { /* it uses pluggable transports, but
5417 the transport could not be found! */
5421 } else { /* bridge matched, but it doesn't use transports. */
5425 } SMARTLIST_FOREACH_END(bridge
);
5431 /** We need to ask <b>bridge</b> for its server descriptor. */
5433 launch_direct_bridge_descriptor_fetch(bridge_info_t
*bridge
)
5436 const or_options_t
*options
= get_options();
5438 if (connection_get_by_type_addr_port_purpose(
5439 CONN_TYPE_DIR
, &bridge
->addr
, bridge
->port
,
5440 DIR_PURPOSE_FETCH_SERVERDESC
))
5441 return; /* it's already on the way */
5443 if (routerset_contains_bridge(options
->ExcludeNodes
, bridge
)) {
5444 download_status_mark_impossible(&bridge
->fetch_status
);
5445 log_warn(LD_APP
, "Not using bridge at %s: it is in ExcludeNodes.",
5446 safe_str_client(fmt_addr(&bridge
->addr
)));
5450 address
= tor_dup_addr(&bridge
->addr
);
5452 directory_initiate_command(address
, &bridge
->addr
,
5454 0, /* does not matter */
5455 1, bridge
->identity
,
5456 DIR_PURPOSE_FETCH_SERVERDESC
,
5457 ROUTER_PURPOSE_BRIDGE
,
5458 0, "authority.z", NULL
, 0, 0);
5462 /** Fetching the bridge descriptor from the bridge authority returned a
5463 * "not found". Fall back to trying a direct fetch. */
5465 retry_bridge_descriptor_fetch_directly(const char *digest
)
5467 bridge_info_t
*bridge
= find_bridge_by_digest(digest
);
5469 return; /* not found? oh well. */
5471 launch_direct_bridge_descriptor_fetch(bridge
);
5474 /** For each bridge in our list for which we don't currently have a
5475 * descriptor, fetch a new copy of its descriptor -- either directly
5476 * from the bridge or via a bridge authority. */
5478 fetch_bridge_descriptors(const or_options_t
*options
, time_t now
)
5480 int num_bridge_auths
= get_n_authorities(BRIDGE_DIRINFO
);
5481 int ask_bridge_directly
;
5482 int can_use_bridge_authority
;
5487 /* If we still have unconfigured managed proxies, don't go and
5488 connect to a bridge. */
5489 if (pt_proxies_configuration_pending())
5492 SMARTLIST_FOREACH_BEGIN(bridge_list
, bridge_info_t
*, bridge
)
5494 if (!download_status_is_ready(&bridge
->fetch_status
, now
,
5495 IMPOSSIBLE_TO_DOWNLOAD
))
5496 continue; /* don't bother, no need to retry yet */
5497 if (routerset_contains_bridge(options
->ExcludeNodes
, bridge
)) {
5498 download_status_mark_impossible(&bridge
->fetch_status
);
5499 log_warn(LD_APP
, "Not using bridge at %s: it is in ExcludeNodes.",
5500 safe_str_client(fmt_addr(&bridge
->addr
)));
5504 /* schedule another fetch as if this one will fail, in case it does */
5505 download_status_failed(&bridge
->fetch_status
, 0);
5507 can_use_bridge_authority
= !tor_digest_is_zero(bridge
->identity
) &&
5509 ask_bridge_directly
= !can_use_bridge_authority
||
5510 !options
->UpdateBridgesFromAuthority
;
5511 log_debug(LD_DIR
, "ask_bridge_directly=%d (%d, %d, %d)",
5512 ask_bridge_directly
, tor_digest_is_zero(bridge
->identity
),
5513 !options
->UpdateBridgesFromAuthority
, !num_bridge_auths
);
5515 if (ask_bridge_directly
&&
5516 !fascist_firewall_allows_address_or(&bridge
->addr
, bridge
->port
)) {
5517 log_notice(LD_DIR
, "Bridge at '%s:%d' isn't reachable by our "
5518 "firewall policy. %s.", fmt_addr(&bridge
->addr
),
5520 can_use_bridge_authority
?
5521 "Asking bridge authority instead" : "Skipping");
5522 if (can_use_bridge_authority
)
5523 ask_bridge_directly
= 0;
5528 if (ask_bridge_directly
) {
5529 /* we need to ask the bridge itself for its descriptor. */
5530 launch_direct_bridge_descriptor_fetch(bridge
);
5532 /* We have a digest and we want to ask an authority. We could
5533 * combine all the requests into one, but that may give more
5534 * hints to the bridge authority than we want to give. */
5535 char resource
[10 + HEX_DIGEST_LEN
];
5536 memcpy(resource
, "fp/", 3);
5537 base16_encode(resource
+3, HEX_DIGEST_LEN
+1,
5538 bridge
->identity
, DIGEST_LEN
);
5539 memcpy(resource
+3+HEX_DIGEST_LEN
, ".z", 3);
5540 log_info(LD_DIR
, "Fetching bridge info '%s' from bridge authority.",
5542 directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC
,
5543 ROUTER_PURPOSE_BRIDGE
, resource
, 0);
5546 SMARTLIST_FOREACH_END(bridge
);
5549 /** If our <b>bridge</b> is configured to be a different address than
5550 * the bridge gives in <b>node</b>, rewrite the routerinfo
5551 * we received to use the address we meant to use. Now we handle
5552 * multihomed bridges better.
5555 rewrite_node_address_for_bridge(const bridge_info_t
*bridge
, node_t
*node
)
5557 /* XXXX move this function. */
5558 /* XXXX overridden addresses should really live in the node_t, so that the
5559 * routerinfo_t and the microdesc_t can be immutable. But we can only
5560 * do that safely if we know that no function that connects to an OR
5561 * does so through an address from any source other than node_get_addr().
5566 routerinfo_t
*ri
= node
->ri
;
5567 tor_addr_from_ipv4h(&addr
, ri
->addr
);
5569 if ((!tor_addr_compare(&bridge
->addr
, &addr
, CMP_EXACT
) &&
5570 bridge
->port
== ri
->or_port
) ||
5571 (!tor_addr_compare(&bridge
->addr
, &ri
->ipv6_addr
, CMP_EXACT
) &&
5572 bridge
->port
== ri
->ipv6_orport
)) {
5573 /* they match, so no need to do anything */
5575 if (tor_addr_family(&bridge
->addr
) == AF_INET
) {
5576 ri
->addr
= tor_addr_to_ipv4h(&bridge
->addr
);
5577 tor_free(ri
->address
);
5578 ri
->address
= tor_dup_ip(ri
->addr
);
5579 ri
->or_port
= bridge
->port
;
5581 "Adjusted bridge routerinfo for '%s' to match configured "
5583 ri
->nickname
, ri
->address
, ri
->or_port
);
5584 } else if (tor_addr_family(&bridge
->addr
) == AF_INET6
) {
5585 tor_addr_copy(&ri
->ipv6_addr
, &bridge
->addr
);
5586 ri
->ipv6_orport
= bridge
->port
;
5588 "Adjusted bridge routerinfo for '%s' to match configured "
5590 ri
->nickname
, fmt_addr(&ri
->ipv6_addr
), ri
->ipv6_orport
);
5592 log_err(LD_BUG
, "Address family not supported: %d.",
5593 tor_addr_family(&bridge
->addr
));
5598 /* Indicate that we prefer connecting to this bridge over the
5599 protocol that the bridge address indicates. Last bridge
5600 descriptor handled wins. */
5601 ri
->ipv6_preferred
= tor_addr_family(&bridge
->addr
) == AF_INET6
;
5603 /* XXXipv6 we lack support for falling back to another address for
5604 the same relay, warn the user */
5605 if (!tor_addr_is_null(&ri
->ipv6_addr
))
5608 router_get_pref_orport(ri
, &ap
);
5609 log_notice(LD_CONFIG
,
5610 "Bridge '%s' has both an IPv4 and an IPv6 address. "
5611 "Will prefer using its %s address (%s:%d).",
5613 ri
->ipv6_preferred
? "IPv6" : "IPv4",
5614 fmt_addr(&ap
.addr
), ap
.port
);
5618 routerstatus_t
*rs
= node
->rs
;
5619 tor_addr_from_ipv4h(&addr
, rs
->addr
);
5621 if (!tor_addr_compare(&bridge
->addr
, &addr
, CMP_EXACT
) &&
5622 bridge
->port
== rs
->or_port
) {
5623 /* they match, so no need to do anything */
5625 rs
->addr
= tor_addr_to_ipv4h(&bridge
->addr
);
5626 rs
->or_port
= bridge
->port
;
5628 "Adjusted bridge routerstatus for '%s' to match "
5629 "configured address %s:%d.",
5630 rs
->nickname
, fmt_addr(&bridge
->addr
), rs
->or_port
);
5635 /** We just learned a descriptor for a bridge. See if that
5636 * digest is in our entry guard list, and add it if not. */
5638 learned_bridge_descriptor(routerinfo_t
*ri
, int from_cache
)
5641 tor_assert(ri
->purpose
== ROUTER_PURPOSE_BRIDGE
);
5642 if (get_options()->UseBridges
) {
5643 int first
= !any_bridge_descriptors_known();
5644 bridge_info_t
*bridge
= get_configured_bridge_by_routerinfo(ri
);
5645 time_t now
= time(NULL
);
5646 router_set_status(ri
->cache_info
.identity_digest
, 1);
5648 if (bridge
) { /* if we actually want to use this one */
5650 /* it's here; schedule its re-fetch for a long time from now. */
5652 download_status_reset(&bridge
->fetch_status
);
5654 node
= node_get_mutable_by_id(ri
->cache_info
.identity_digest
);
5656 rewrite_node_address_for_bridge(bridge
, node
);
5657 add_an_entry_guard(node
, 1, 1);
5659 log_notice(LD_DIR
, "new bridge descriptor '%s' (%s): %s", ri
->nickname
,
5660 from_cache
? "cached" : "fresh", router_describe(ri
));
5661 /* set entry->made_contact so if it goes down we don't drop it from
5662 * our entry node list */
5663 entry_guard_register_connect_status(ri
->cache_info
.identity_digest
,
5666 routerlist_retry_directory_downloads(now
);
5671 /** Return 1 if any of our entry guards have descriptors that
5672 * are marked with purpose 'bridge' and are running. Else return 0.
5674 * We use this function to decide if we're ready to start building
5675 * circuits through our bridges, or if we need to wait until the
5676 * directory "server/authority" requests finish. */
5678 any_bridge_descriptors_known(void)
5680 tor_assert(get_options()->UseBridges
);
5681 return choose_random_entry(NULL
)!=NULL
? 1 : 0;
5684 /** Return 1 if there are any directory conns fetching bridge descriptors
5685 * that aren't marked for close. We use this to guess if we should tell
5686 * the controller that we have a problem. */
5688 any_pending_bridge_descriptor_fetches(void)
5690 smartlist_t
*conns
= get_connection_array();
5691 SMARTLIST_FOREACH(conns
, connection_t
*, conn
,
5693 if (conn
->type
== CONN_TYPE_DIR
&&
5694 conn
->purpose
== DIR_PURPOSE_FETCH_SERVERDESC
&&
5695 TO_DIR_CONN(conn
)->router_purpose
== ROUTER_PURPOSE_BRIDGE
&&
5696 !conn
->marked_for_close
&&
5698 conn
->linked_conn
&& !conn
->linked_conn
->marked_for_close
) {
5699 log_debug(LD_DIR
, "found one: %s", conn
->address
);
5706 /** Return 1 if we have at least one descriptor for an entry guard
5707 * (bridge or member of EntryNodes) and all descriptors we know are
5708 * down. Else return 0. If <b>act</b> is 1, then mark the down guards
5709 * up; else just observe and report. */
5711 entries_retry_helper(const or_options_t
*options
, int act
)
5715 int any_running
= 0;
5716 int need_bridges
= options
->UseBridges
!= 0;
5718 entry_guards
= smartlist_new();
5719 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, e
) {
5720 node
= node_get_by_id(e
->identity
);
5721 if (node
&& node_has_descriptor(node
) &&
5722 node_is_bridge(node
) == need_bridges
) {
5724 if (node
->is_running
)
5725 any_running
= 1; /* some entry is both known and running */
5727 /* Mark all current connections to this OR as unhealthy, since
5728 * otherwise there could be one that started 30 seconds
5729 * ago, and in 30 seconds it will time out, causing us to mark
5730 * the node down and undermine the retry attempt. We mark even
5731 * the established conns, since if the network just came back
5732 * we'll want to attach circuits to fresh conns. */
5733 connection_or_set_bad_connections(node
->identity
, 1);
5735 /* mark this entry node for retry */
5736 router_set_status(node
->identity
, 1);
5741 } SMARTLIST_FOREACH_END(e
);
5742 log_debug(LD_DIR
, "%d: any_known %d, any_running %d",
5743 act
, any_known
, any_running
);
5744 return any_known
&& !any_running
;
5747 /** Do we know any descriptors for our bridges / entrynodes, and are
5748 * all the ones we have descriptors for down? */
5750 entries_known_but_down(const or_options_t
*options
)
5752 tor_assert(entry_list_is_constrained(options
));
5753 return entries_retry_helper(options
, 0);
5756 /** Mark all down known bridges / entrynodes up. */
5758 entries_retry_all(const or_options_t
*options
)
5760 tor_assert(entry_list_is_constrained(options
));
5761 entries_retry_helper(options
, 1);
5764 /** Return true if we've ever had a bridge running a Tor version that can't
5765 * provide microdescriptors to us. In that case fall back to asking for
5766 * full descriptors. Eventually all bridges will support microdescriptors
5767 * and we can take this check out; see bug 4013. */
5769 any_bridges_dont_support_microdescriptors(void)
5772 static int ever_answered_yes
= 0;
5773 if (!get_options()->UseBridges
|| !entry_guards
)
5775 if (ever_answered_yes
)
5776 return 1; /* if we ever answer 'yes', always answer 'yes' */
5777 SMARTLIST_FOREACH_BEGIN(entry_guards
, entry_guard_t
*, e
) {
5778 node
= node_get_by_id(e
->identity
);
5779 if (node
&& node
->ri
&&
5780 node_is_bridge(node
) && node_is_a_configured_bridge(node
) &&
5781 !tor_version_supports_microdescriptors(node
->ri
->platform
)) {
5782 /* This is one of our current bridges, and we know enough about
5783 * it to know that it won't be able to answer our microdescriptor
5785 ever_answered_yes
= 1;
5788 } SMARTLIST_FOREACH_END(e
);
5792 /** Release all storage held by the list of entry guards and related
5793 * memory structs. */
5795 entry_guards_free_all(void)
5798 SMARTLIST_FOREACH(entry_guards
, entry_guard_t
*, e
,
5799 entry_guard_free(e
));
5800 smartlist_free(entry_guards
);
5801 entry_guards
= NULL
;
5803 clear_bridge_list();
5804 clear_transport_list();
5805 smartlist_free(bridge_list
);
5806 smartlist_free(transport_list
);
5808 transport_list
= NULL
;