Line data Source code
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-2021, The Tor Project, Inc. */
5 : /* See LICENSE for licensing information */
6 :
7 : /**
8 : * \file circuitstats.c
9 : *
10 : * \brief Maintains and analyzes statistics about circuit built times, so we
11 : * can tell how long we may need to wait for a fast circuit to be constructed.
12 : *
13 : * By keeping these statistics, a client learns when it should time out a slow
14 : * circuit for being too slow, and when it should keep a circuit open in order
15 : * to wait for it to complete.
16 : *
17 : * The information here is kept in a circuit_built_times_t structure, which is
18 : * currently a singleton, but doesn't need to be. It's updated by calls to
19 : * circuit_build_times_count_timeout() from circuituse.c,
20 : * circuit_build_times_count_close() from circuituse.c, and
21 : * circuit_build_times_add_time() from circuitbuild.c, and inspected by other
22 : * calls into this module, mostly from circuitlist.c. Observations are
23 : * persisted to disk via the or_state_t-related calls.
24 : */
25 :
26 : #define CIRCUITSTATS_PRIVATE
27 :
28 : #include "core/or/or.h"
29 : #include "core/or/circuitbuild.h"
30 : #include "core/or/circuitstats.h"
31 : #include "app/config/config.h"
32 : #include "lib/confmgt/confmgt.h"
33 : #include "feature/control/control_events.h"
34 : #include "lib/crypt_ops/crypto_rand.h"
35 : #include "core/mainloop/mainloop.h"
36 : #include "feature/nodelist/networkstatus.h"
37 : #include "feature/relay/router.h"
38 : #include "app/config/statefile.h"
39 : #include "core/or/circuitlist.h"
40 : #include "core/or/circuituse.h"
41 : #include "lib/math/fp.h"
42 : #include "lib/time/tvdiff.h"
43 : #include "lib/encoding/confline.h"
44 : #include "feature/dirauth/authmode.h"
45 : #include "feature/hs/hs_service.h"
46 : #include "feature/relay/relay_periodic.h"
47 :
48 : #include "core/or/crypt_path_st.h"
49 : #include "core/or/origin_circuit_st.h"
50 : #include "app/config/or_state_st.h"
51 :
52 : #undef log
53 : #include <math.h>
54 :
55 : static void circuit_build_times_scale_circ_counts(circuit_build_times_t *cbt);
56 :
57 : #define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
58 :
59 : /** Global list of circuit build times */
60 : // XXXX: Add this as a member for entry_guard_t instead of global?
61 : // Then we could do per-guard statistics, as guards are likely to
62 : // vary in their own latency. The downside of this is that guards
63 : // can change frequently, so we'd be building a lot more circuits
64 : // most likely.
65 : static circuit_build_times_t circ_times;
66 :
67 : #ifdef TOR_UNIT_TESTS
68 : /** If set, we're running the unit tests: we should avoid clobbering
69 : * our state file or accessing get_options() or get_or_state() */
70 : static int unit_tests = 0;
71 : #else
72 : #define unit_tests 0
73 : #endif /* defined(TOR_UNIT_TESTS) */
74 :
75 : /** Return a pointer to the data structure describing our current circuit
76 : * build time history and computations. */
77 : const circuit_build_times_t *
78 163 : get_circuit_build_times(void)
79 : {
80 163 : return &circ_times;
81 : }
82 :
83 : /** As get_circuit_build_times, but return a mutable pointer. */
84 : circuit_build_times_t *
85 421 : get_circuit_build_times_mutable(void)
86 : {
87 421 : return &circ_times;
88 : }
89 :
90 : /** Return the time to wait before actually closing an under-construction, in
91 : * milliseconds. */
92 : double
93 28 : get_circuit_build_close_time_ms(void)
94 : {
95 28 : return circ_times.close_ms;
96 : }
97 :
98 : /** Return the time to wait before giving up on an under-construction circuit,
99 : * in milliseconds. */
100 : double
101 29 : get_circuit_build_timeout_ms(void)
102 : {
103 29 : return circ_times.timeout_ms;
104 : }
105 :
106 : /**
107 : * This function decides if CBT learning should be disabled. It returns
108 : * true if one or more of the following conditions are met:
109 : *
110 : * 1. If the cbtdisabled consensus parameter is set.
111 : * 2. If the torrc option LearnCircuitBuildTimeout is false.
112 : * 3. If we are a directory authority
113 : * 4. If we fail to write circuit build time history to our state file.
114 : * 5. If we are configured in Single Onion mode
115 : */
116 : int
117 2094 : circuit_build_times_disabled(const or_options_t *options)
118 : {
119 2094 : return circuit_build_times_disabled_(options, 0);
120 : }
121 :
122 : /** As circuit_build_times_disabled, but take options as an argument. */
123 : int
124 2094 : circuit_build_times_disabled_(const or_options_t *options,
125 : int ignore_consensus)
126 : {
127 2094 : if (unit_tests) {
128 : return 0;
129 : } else {
130 378 : int consensus_disabled =
131 189 : ignore_consensus ? 0 : networkstatus_get_param(NULL, "cbtdisabled",
132 : 0, 0, 1);
133 189 : int config_disabled = !options->LearnCircuitBuildTimeout;
134 189 : int dirauth_disabled = authdir_mode(options);
135 189 : int state_disabled = did_last_state_file_write_fail() ? 1 : 0;
136 : /* LearnCircuitBuildTimeout and Single Onion Services are
137 : * incompatible in two ways:
138 : *
139 : * - LearnCircuitBuildTimeout results in a low CBT, which
140 : * Single Onion use of one-hop intro and rendezvous circuits lowers
141 : * much further, producing *far* too many timeouts.
142 : *
143 : * - The adaptive CBT code does not update its timeout estimate
144 : * using build times for single-hop circuits.
145 : *
146 : * If we fix both of these issues someday, we should test
147 : * these modes with LearnCircuitBuildTimeout on again. */
148 189 : int single_onion_disabled = hs_service_allow_non_anonymous_connection(
149 : options);
150 :
151 189 : if (consensus_disabled || config_disabled || dirauth_disabled ||
152 189 : state_disabled || single_onion_disabled) {
153 : #if 0
154 : log_debug(LD_CIRC,
155 : "CircuitBuildTime learning is disabled. "
156 : "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
157 : consensus_disabled, config_disabled, dirauth_disabled,
158 : state_disabled);
159 : #endif /* 0 */
160 : return 1;
161 : } else {
162 : #if 0
163 : log_debug(LD_CIRC,
164 : "CircuitBuildTime learning is not disabled. "
165 : "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
166 : consensus_disabled, config_disabled, dirauth_disabled,
167 : state_disabled);
168 : #endif /* 0 */
169 189 : return 0;
170 : }
171 : }
172 : }
173 :
174 : /**
175 : * Retrieve and bounds-check the cbtmaxtimeouts consensus parameter.
176 : *
177 : * Effect: When this many timeouts happen in the last 'cbtrecentcount'
178 : * circuit attempts, the client should discard all of its history and
179 : * begin learning a fresh timeout value.
180 : */
181 : static int32_t
182 1902 : circuit_build_times_max_timeouts(void)
183 : {
184 1902 : int32_t cbt_maxtimeouts;
185 :
186 1902 : cbt_maxtimeouts = networkstatus_get_param(NULL, "cbtmaxtimeouts",
187 : CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT,
188 : CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
189 : CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);
190 :
191 1902 : if (!(get_options()->LearnCircuitBuildTimeout)) {
192 0 : log_debug(LD_BUG,
193 : "circuit_build_times_max_timeouts() called, cbtmaxtimeouts is"
194 : " %d",
195 : cbt_maxtimeouts);
196 : }
197 :
198 1902 : return cbt_maxtimeouts;
199 : }
200 :
201 : /**
202 : * Retrieve and bounds-check the cbtnummodes consensus parameter.
203 : *
204 : * Effect: This value governs how many modes to use in the weighted
205 : * average calculation of Pareto parameter Xm. Analysis of pairs of
206 : * geographically near, far, and mixed guaeds has shown that a value of
207 : * 10 introduces some allows for the actual timeout rate to be within
208 : * 2-7% of the cutoff quantile, for quantiles between 60-80%.
209 : */
210 : static int32_t
211 17 : circuit_build_times_default_num_xm_modes(void)
212 : {
213 17 : int32_t num = networkstatus_get_param(NULL, "cbtnummodes",
214 : CBT_DEFAULT_NUM_XM_MODES,
215 : CBT_MIN_NUM_XM_MODES,
216 : CBT_MAX_NUM_XM_MODES);
217 :
218 17 : if (!(get_options()->LearnCircuitBuildTimeout)) {
219 0 : log_debug(LD_BUG,
220 : "circuit_build_times_default_num_xm_modes() called, cbtnummodes"
221 : " is %d",
222 : num);
223 : }
224 :
225 17 : return num;
226 : }
227 :
228 : /**
229 : * Retrieve and bounds-check the cbtmincircs consensus parameter.
230 : *
231 : * Effect: This is the minimum number of circuits to build before
232 : * computing a timeout.
233 : */
234 : static int32_t
235 150 : circuit_build_times_min_circs_to_observe(void)
236 : {
237 150 : int32_t num = networkstatus_get_param(NULL, "cbtmincircs",
238 : CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE,
239 : CBT_MIN_MIN_CIRCUITS_TO_OBSERVE,
240 : CBT_MAX_MIN_CIRCUITS_TO_OBSERVE);
241 :
242 150 : if (!(get_options()->LearnCircuitBuildTimeout)) {
243 0 : log_debug(LD_BUG,
244 : "circuit_build_times_min_circs_to_observe() called, cbtmincircs"
245 : " is %d",
246 : num);
247 : }
248 :
249 150 : return num;
250 : }
251 :
252 : /** Return true iff <b>cbt</b> has recorded enough build times that we
253 : * want to start acting on the timeout it implies. */
254 : int
255 150 : circuit_build_times_enough_to_compute(const circuit_build_times_t *cbt)
256 : {
257 150 : return cbt->total_build_times >= circuit_build_times_min_circs_to_observe();
258 : }
259 :
260 : /**
261 : * Retrieve and bounds-check the cbtquantile consensus parameter.
262 : *
263 : * Effect: This is the position on the quantile curve to use to set the
264 : * timeout value. It is a percent (10-99).
265 : */
266 : double
267 9 : circuit_build_times_quantile_cutoff(void)
268 : {
269 9 : int32_t num = networkstatus_get_param(NULL, "cbtquantile",
270 : CBT_DEFAULT_QUANTILE_CUTOFF,
271 : CBT_MIN_QUANTILE_CUTOFF,
272 : CBT_MAX_QUANTILE_CUTOFF);
273 :
274 9 : if (!(get_options()->LearnCircuitBuildTimeout)) {
275 0 : log_debug(LD_BUG,
276 : "circuit_build_times_quantile_cutoff() called, cbtquantile"
277 : " is %d",
278 : num);
279 : }
280 :
281 9 : return num/100.0;
282 : }
283 :
284 : /**
285 : * Retrieve and bounds-check the cbtclosequantile consensus parameter.
286 : *
287 : * Effect: This is the position on the quantile curve to use to set the
288 : * timeout value to use to actually close circuits. It is a percent
289 : * (0-99).
290 : */
291 : static double
292 3 : circuit_build_times_close_quantile(void)
293 : {
294 3 : int32_t param;
295 : /* Cast is safe - circuit_build_times_quantile_cutoff() is capped */
296 3 : int32_t min = (int)tor_lround(100*circuit_build_times_quantile_cutoff());
297 3 : param = networkstatus_get_param(NULL, "cbtclosequantile",
298 : CBT_DEFAULT_CLOSE_QUANTILE,
299 : CBT_MIN_CLOSE_QUANTILE,
300 : CBT_MAX_CLOSE_QUANTILE);
301 :
302 3 : if (!(get_options()->LearnCircuitBuildTimeout)) {
303 0 : log_debug(LD_BUG,
304 : "circuit_build_times_close_quantile() called, cbtclosequantile"
305 : " is %d", param);
306 : }
307 :
308 3 : if (param < min) {
309 0 : log_warn(LD_DIR, "Consensus parameter cbtclosequantile is "
310 : "too small, raising to %d", min);
311 0 : param = min;
312 : }
313 3 : return param / 100.0;
314 : }
315 :
316 : /**
317 : * Retrieve and bounds-check the cbttestfreq consensus parameter.
318 : *
319 : * Effect: Describes how often in seconds to build a test circuit to
320 : * gather timeout values. Only applies if less than 'cbtmincircs'
321 : * have been recorded.
322 : */
323 : static int32_t
324 1 : circuit_build_times_test_frequency(void)
325 : {
326 1 : int32_t num = networkstatus_get_param(NULL, "cbttestfreq",
327 : CBT_DEFAULT_TEST_FREQUENCY,
328 : CBT_MIN_TEST_FREQUENCY,
329 : CBT_MAX_TEST_FREQUENCY);
330 :
331 1 : if (!(get_options()->LearnCircuitBuildTimeout)) {
332 0 : log_debug(LD_BUG,
333 : "circuit_build_times_test_frequency() called, cbttestfreq is %d",
334 : num);
335 : }
336 :
337 1 : return num;
338 : }
339 :
340 : /**
341 : * Retrieve and bounds-check the cbtmintimeout consensus parameter.
342 : *
343 : * Effect: This is the minimum allowed timeout value in milliseconds.
344 : * The minimum is to prevent rounding to 0 (we only check once
345 : * per second).
346 : */
347 : static int32_t
348 116 : circuit_build_times_min_timeout(void)
349 : {
350 116 : int32_t num = networkstatus_get_param(NULL, "cbtmintimeout",
351 : CBT_DEFAULT_TIMEOUT_MIN_VALUE,
352 : CBT_MIN_TIMEOUT_MIN_VALUE,
353 : CBT_MAX_TIMEOUT_MIN_VALUE);
354 :
355 116 : if (!(get_options()->LearnCircuitBuildTimeout)) {
356 0 : log_debug(LD_BUG,
357 : "circuit_build_times_min_timeout() called, cbtmintimeout is %d",
358 : num);
359 : }
360 116 : return num;
361 : }
362 :
363 : /**
364 : * Retrieve and bounds-check the cbtinitialtimeout consensus parameter.
365 : *
366 : * Effect: This is the timeout value to use before computing a timeout,
367 : * in milliseconds.
368 : */
369 : int32_t
370 113 : circuit_build_times_initial_timeout(void)
371 : {
372 113 : int32_t min = circuit_build_times_min_timeout();
373 113 : int32_t param = networkstatus_get_param(NULL, "cbtinitialtimeout",
374 : CBT_DEFAULT_TIMEOUT_INITIAL_VALUE,
375 : CBT_MIN_TIMEOUT_INITIAL_VALUE,
376 : CBT_MAX_TIMEOUT_INITIAL_VALUE);
377 :
378 113 : if (!(get_options()->LearnCircuitBuildTimeout)) {
379 0 : log_debug(LD_BUG,
380 : "circuit_build_times_initial_timeout() called, "
381 : "cbtinitialtimeout is %d",
382 : param);
383 : }
384 :
385 113 : if (param < min) {
386 0 : log_warn(LD_DIR, "Consensus parameter cbtinitialtimeout is too small, "
387 : "raising to %d", min);
388 0 : param = min;
389 : }
390 113 : return param;
391 : }
392 :
393 : /**
394 : * Retrieve and bounds-check the cbtrecentcount consensus parameter.
395 : *
396 : * Effect: This is the number of circuit build times to keep track of
397 : * for deciding if we hit cbtmaxtimeouts and need to reset our state
398 : * and learn a new timeout.
399 : */
400 : static int32_t
401 15 : circuit_build_times_recent_circuit_count(const networkstatus_t *ns)
402 : {
403 15 : int32_t num;
404 15 : num = networkstatus_get_param(ns, "cbtrecentcount",
405 : CBT_DEFAULT_RECENT_CIRCUITS,
406 : CBT_MIN_RECENT_CIRCUITS,
407 : CBT_MAX_RECENT_CIRCUITS);
408 :
409 15 : if (!(get_options()->LearnCircuitBuildTimeout)) {
410 0 : log_debug(LD_BUG,
411 : "circuit_build_times_recent_circuit_count() called, "
412 : "cbtrecentcount is %d",
413 : num);
414 : }
415 :
416 15 : return num;
417 : }
418 :
419 : /**
420 : * This function is called when we get a consensus update.
421 : *
422 : * It checks to see if we have changed any consensus parameters
423 : * that require reallocation or discard of previous stats.
424 : */
425 : void
426 5 : circuit_build_times_new_consensus_params(circuit_build_times_t *cbt,
427 : const networkstatus_t *ns)
428 : {
429 5 : int32_t num;
430 :
431 : /*
432 : * First check if we're doing adaptive timeouts at all; nothing to
433 : * update if we aren't.
434 : */
435 :
436 5 : if (!circuit_build_times_disabled(get_options())) {
437 5 : num = circuit_build_times_recent_circuit_count(ns);
438 :
439 5 : if (num > 0) {
440 5 : if (num != cbt->liveness.num_recent_circs) {
441 5 : int8_t *recent_circs;
442 5 : if (cbt->liveness.num_recent_circs > 0) {
443 0 : log_notice(LD_CIRC, "The Tor Directory Consensus has changed how "
444 : "many circuits we must track to detect network failures "
445 : "from %d to %d.", cbt->liveness.num_recent_circs, num);
446 : } else {
447 5 : log_notice(LD_CIRC, "Upon receiving a consensus directory, "
448 : "re-enabling circuit-based network failure detection.");
449 : }
450 :
451 5 : tor_assert(cbt->liveness.timeouts_after_firsthop ||
452 : cbt->liveness.num_recent_circs == 0);
453 :
454 : /*
455 : * Technically this is a circular array that we are reallocating
456 : * and memcopying. However, since it only consists of either 1s
457 : * or 0s, and is only used in a statistical test to determine when
458 : * we should discard our history after a sufficient number of 1's
459 : * have been reached, it is fine if order is not preserved or
460 : * elements are lost.
461 : *
462 : * cbtrecentcount should only be changing in cases of severe network
463 : * distress anyway, so memory correctness here is paramount over
464 : * doing acrobatics to preserve the array.
465 : */
466 5 : recent_circs = tor_calloc(num, sizeof(int8_t));
467 5 : if (cbt->liveness.timeouts_after_firsthop &&
468 0 : cbt->liveness.num_recent_circs > 0) {
469 5 : memcpy(recent_circs, cbt->liveness.timeouts_after_firsthop,
470 0 : sizeof(int8_t)*MIN(num, cbt->liveness.num_recent_circs));
471 : }
472 :
473 : // Adjust the index if it needs it.
474 5 : if (num < cbt->liveness.num_recent_circs) {
475 0 : cbt->liveness.after_firsthop_idx = MIN(num-1,
476 : cbt->liveness.after_firsthop_idx);
477 : }
478 :
479 5 : tor_free(cbt->liveness.timeouts_after_firsthop);
480 5 : cbt->liveness.timeouts_after_firsthop = recent_circs;
481 5 : cbt->liveness.num_recent_circs = num;
482 : }
483 : /* else no change, nothing to do */
484 : } else { /* num == 0 */
485 : /*
486 : * Weird. This probably shouldn't happen, so log a warning, but try
487 : * to do something sensible anyway.
488 : */
489 :
490 0 : log_warn(LD_CIRC,
491 : "The cbtrecentcircs consensus parameter came back zero! "
492 : "This disables adaptive timeouts since we can't keep track of "
493 : "any recent circuits.");
494 :
495 0 : circuit_build_times_free_timeouts(cbt);
496 : }
497 : } else {
498 : /*
499 : * Adaptive timeouts are disabled; this might be because of the
500 : * LearnCircuitBuildTimes config parameter, and hence permanent, or
501 : * the cbtdisabled consensus parameter, so it may be a new condition.
502 : * Treat it like getting num == 0 above and free the circuit history
503 : * if we have any.
504 : */
505 :
506 0 : circuit_build_times_free_timeouts(cbt);
507 : }
508 5 : }
509 :
510 : /**
511 : * Return the initial default or configured timeout in milliseconds
512 : */
513 : static double
514 110 : circuit_build_times_get_initial_timeout(void)
515 : {
516 110 : double timeout;
517 110 : const or_options_t *options = get_options();
518 :
519 : /*
520 : * Check if we have LearnCircuitBuildTimeout, and if we don't,
521 : * always use CircuitBuildTimeout, no questions asked.
522 : */
523 110 : if (!unit_tests && options->CircuitBuildTimeout) {
524 0 : timeout = options->CircuitBuildTimeout*1000;
525 0 : if (!circuit_build_times_disabled(options) &&
526 0 : timeout < circuit_build_times_min_timeout()) {
527 0 : log_warn(LD_CIRC, "Config CircuitBuildTimeout too low. Setting to %ds",
528 : circuit_build_times_min_timeout()/1000);
529 0 : timeout = circuit_build_times_min_timeout();
530 : }
531 : } else {
532 110 : timeout = circuit_build_times_initial_timeout();
533 : }
534 :
535 110 : return timeout;
536 : }
537 :
538 : /**
539 : * Reset the build time state.
540 : *
541 : * Leave estimated parameters, timeout and network liveness intact
542 : * for future use.
543 : */
544 : void
545 102 : circuit_build_times_reset(circuit_build_times_t *cbt)
546 : {
547 102 : memset(cbt->circuit_build_times, 0, sizeof(cbt->circuit_build_times));
548 102 : cbt->total_build_times = 0;
549 102 : cbt->build_times_idx = 0;
550 102 : cbt->have_computed_timeout = 0;
551 :
552 : // Reset timeout and close counts
553 102 : cbt->num_circ_succeeded = 0;
554 102 : cbt->num_circ_closed = 0;
555 102 : cbt->num_circ_timeouts = 0;
556 102 : }
557 :
558 : /**
559 : * Initialize the buildtimes structure for first use.
560 : *
561 : * Sets the initial timeout values based on either the config setting,
562 : * the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).
563 : */
564 : void
565 10 : circuit_build_times_init(circuit_build_times_t *cbt)
566 : {
567 10 : memset(cbt, 0, sizeof(*cbt));
568 : /*
569 : * Check if we really are using adaptive timeouts, and don't keep
570 : * track of this stuff if not.
571 : */
572 10 : if (!circuit_build_times_disabled(get_options())) {
573 20 : cbt->liveness.num_recent_circs =
574 10 : circuit_build_times_recent_circuit_count(NULL);
575 10 : cbt->liveness.timeouts_after_firsthop =
576 10 : tor_calloc(cbt->liveness.num_recent_circs, sizeof(int8_t));
577 : } else {
578 0 : cbt->liveness.num_recent_circs = 0;
579 0 : cbt->liveness.timeouts_after_firsthop = NULL;
580 : }
581 10 : cbt->close_ms = cbt->timeout_ms = circuit_build_times_get_initial_timeout();
582 10 : cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
583 10 : }
584 :
585 : /**
586 : * Free the saved timeouts, if the cbtdisabled consensus parameter got turned
587 : * on or something.
588 : */
589 :
590 : void
591 246 : circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
592 : {
593 246 : if (!cbt) return;
594 :
595 246 : if (cbt->liveness.timeouts_after_firsthop) {
596 11 : tor_free(cbt->liveness.timeouts_after_firsthop);
597 : }
598 :
599 246 : cbt->liveness.num_recent_circs = 0;
600 : }
601 :
602 : #if 0
603 : /**
604 : * Rewind our build time history by n positions.
605 : */
606 : static void
607 : circuit_build_times_rewind_history(circuit_build_times_t *cbt, int n)
608 : {
609 : int i = 0;
610 :
611 : cbt->build_times_idx -= n;
612 : cbt->build_times_idx %= CBT_NCIRCUITS_TO_OBSERVE;
613 :
614 : for (i = 0; i < n; i++) {
615 : cbt->circuit_build_times[(i+cbt->build_times_idx)
616 : %CBT_NCIRCUITS_TO_OBSERVE]=0;
617 : }
618 :
619 : if (cbt->total_build_times > n) {
620 : cbt->total_build_times -= n;
621 : } else {
622 : cbt->total_build_times = 0;
623 : }
624 :
625 : log_info(LD_CIRC,
626 : "Rewound history by %d places. Current index: %d. "
627 : "Total: %d", n, cbt->build_times_idx, cbt->total_build_times);
628 : }
629 : #endif /* 0 */
630 :
631 : /**
632 : * Mark this circuit as timed out, but change its purpose
633 : * so that it continues to build, allowing us to measure
634 : * its full build time.
635 : */
636 : void
637 1 : circuit_build_times_mark_circ_as_measurement_only(origin_circuit_t *circ)
638 : {
639 1 : circuit_event_status(circ,
640 : CIRC_EVENT_FAILED,
641 : END_CIRC_REASON_TIMEOUT);
642 1 : circuit_change_purpose(TO_CIRCUIT(circ),
643 : CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT);
644 : /* Record this event to check for too many timeouts
645 : * in a row. This function does not record a time value yet
646 : * (we do that later); it only counts the fact that we did
647 : * have a timeout. We also want to avoid double-counting
648 : * already "relaxed" circuits, which are counted in
649 : * circuit_expire_building(). */
650 1 : if (!circ->relaxed_timeout) {
651 1 : int first_hop_succeeded = circ->cpath &&
652 1 : circ->cpath->state == CPATH_STATE_OPEN;
653 :
654 1 : circuit_build_times_count_timeout(
655 : get_circuit_build_times_mutable(),
656 : first_hop_succeeded);
657 : }
658 1 : }
659 :
660 : /**
661 : * Perform the build time work that needs to be done when a circuit
662 : * completes a hop.
663 : *
664 : * This function decides if we should record a circuit's build time
665 : * in our histogram data and other statistics, and if so, records it.
666 : * It also will mark circuits that have already timed out as
667 : * measurement-only circuits, so they can continue to build but
668 : * not get used.
669 : *
670 : * For this, we want to consider circuits that will eventually make
671 : * it to the third hop. For circuits longer than 3 hops, we want to
672 : * record their build time when they reach the third hop, but let
673 : * them continue (and not count them later). For circuits that are
674 : * exactly 3 hops, this will count them when they are completed. We
675 : * do this so that CBT is always gathering statistics on circuits
676 : * of the same length, regardless of their type.
677 : */
678 : void
679 18 : circuit_build_times_handle_completed_hop(origin_circuit_t *circ)
680 : {
681 18 : struct timeval end;
682 18 : long timediff;
683 :
684 : /* If circuit build times are disabled, let circuit_expire_building()
685 : * handle it.. */
686 18 : if (circuit_build_times_disabled(get_options())) {
687 9 : return;
688 : }
689 :
690 : /* Is this a circuit for which the timeout applies in a straight-forward
691 : * way? If so, handle it below. If not, just return (and let
692 : * circuit_expire_building() eventually take care of it).
693 : */
694 18 : if (!circuit_timeout_want_to_count_circ(circ)) {
695 : return;
696 : }
697 :
698 9 : tor_gettimeofday(&end);
699 9 : timediff = tv_mdiff(&circ->base_.timestamp_began, &end);
700 :
701 : /* Check if we would have timed out already. If so, change the
702 : * purpose here. But don't do any timeout handling here if there
703 : * are no circuits opened yet. Save it for circuit_expire_building()
704 : * (to allow it to handle timeout "relaxing" over there). */
705 15 : if (timediff > get_circuit_build_timeout_ms() &&
706 6 : circuit_any_opened_circuits_cached()) {
707 :
708 : /* Circuits are allowed to last longer for measurement.
709 : * Switch their purpose and wait. */
710 3 : if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
711 1 : log_info(LD_CIRC,
712 : "Deciding to timeout circuit %"PRIu32"\n",
713 : (circ->global_identifier));
714 1 : circuit_build_times_mark_circ_as_measurement_only(circ);
715 : }
716 : }
717 :
718 : /* If the circuit is built to exactly the DEFAULT_ROUTE_LEN,
719 : * add it to our buildtimes. */
720 9 : if (circuit_get_cpath_opened_len(circ) == DEFAULT_ROUTE_LEN) {
721 : /* If the circuit build time is much greater than we would have cut
722 : * it off at, we probably had a suspend event along this codepath,
723 : * and we should discard the value.
724 : */
725 3 : if (timediff < 0 ||
726 3 : timediff > 2*get_circuit_build_close_time_ms()+1000) {
727 0 : log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. "
728 : "Assuming clock jump. Purpose %d (%s)", timediff,
729 : circ->base_.purpose,
730 : circuit_purpose_to_string(circ->base_.purpose));
731 : } else {
732 : /* Only count circuit times if the network is live */
733 3 : if (circuit_build_times_network_check_live(
734 : get_circuit_build_times())) {
735 3 : circuit_build_times_add_time(get_circuit_build_times_mutable(),
736 : (build_time_t)timediff);
737 3 : circuit_build_times_set_timeout(get_circuit_build_times_mutable());
738 : }
739 :
740 3 : if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
741 2 : circuit_build_times_network_circ_success(
742 : get_circuit_build_times_mutable());
743 : }
744 : }
745 : }
746 : }
747 :
748 : /**
749 : * Add a new build time value <b>time</b> to the set of build times. Time
750 : * units are milliseconds.
751 : *
752 : * circuit_build_times <b>cbt</b> is a circular array, so loop around when
753 : * array is full.
754 : */
755 : int
756 4203 : circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t btime)
757 : {
758 4203 : if (btime <= 0 || btime > CBT_BUILD_TIME_MAX) {
759 0 : log_warn(LD_BUG, "Circuit build time is too large (%u)."
760 : "This is probably a bug.", btime);
761 0 : tor_fragile_assert();
762 0 : return -1;
763 : }
764 :
765 4203 : log_debug(LD_CIRC, "Adding circuit build time %u", btime);
766 :
767 4203 : cbt->circuit_build_times[cbt->build_times_idx] = btime;
768 4203 : cbt->build_times_idx = (cbt->build_times_idx + 1) % CBT_NCIRCUITS_TO_OBSERVE;
769 4203 : if (cbt->total_build_times < CBT_NCIRCUITS_TO_OBSERVE)
770 4203 : cbt->total_build_times++;
771 :
772 4203 : if ((cbt->total_build_times % CBT_SAVE_STATE_EVERY) == 0) {
773 : /* Save state every n circuit builds */
774 420 : if (!unit_tests && !get_options()->AvoidDiskWrites)
775 0 : or_state_mark_dirty(get_or_state(), 0);
776 : }
777 :
778 : return 0;
779 : }
780 :
781 : /**
782 : * Return maximum circuit build time
783 : */
784 : static build_time_t
785 25 : circuit_build_times_max(const circuit_build_times_t *cbt)
786 : {
787 25 : int i = 0;
788 25 : build_time_t max_build_time = 0;
789 25025 : for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
790 25000 : if (cbt->circuit_build_times[i] > max_build_time
791 326 : && cbt->circuit_build_times[i] != CBT_BUILD_ABANDONED)
792 206 : max_build_time = cbt->circuit_build_times[i];
793 : }
794 25 : return max_build_time;
795 : }
796 :
797 : #if 0
798 : /** Return minimum circuit build time */
799 : build_time_t
800 : circuit_build_times_min(circuit_build_times_t *cbt)
801 : {
802 : int i = 0;
803 : build_time_t min_build_time = CBT_BUILD_TIME_MAX;
804 : for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
805 : if (cbt->circuit_build_times[i] && /* 0 <-> uninitialized */
806 : cbt->circuit_build_times[i] < min_build_time)
807 : min_build_time = cbt->circuit_build_times[i];
808 : }
809 : if (min_build_time == CBT_BUILD_TIME_MAX) {
810 : log_warn(LD_CIRC, "No build times less than CBT_BUILD_TIME_MAX!");
811 : }
812 : return min_build_time;
813 : }
814 : #endif /* 0 */
815 :
816 : /**
817 : * Calculate and return a histogram for the set of build times.
818 : *
819 : * Returns an allocated array of histrogram bins representing
820 : * the frequency of index*CBT_BIN_WIDTH millisecond
821 : * build times. Also outputs the number of bins in nbins.
822 : *
823 : * The return value must be freed by the caller.
824 : */
825 : static uint32_t *
826 22 : circuit_build_times_create_histogram(const circuit_build_times_t *cbt,
827 : build_time_t *nbins)
828 : {
829 22 : uint32_t *histogram;
830 22 : build_time_t max_build_time = circuit_build_times_max(cbt);
831 22 : int i, c;
832 :
833 22 : *nbins = 1 + (max_build_time / CBT_BIN_WIDTH);
834 22 : histogram = tor_calloc(*nbins, sizeof(build_time_t));
835 :
836 : // calculate histogram
837 22044 : for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
838 42200 : if (cbt->circuit_build_times[i] == 0
839 22000 : || cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
840 20200 : continue; /* 0 <-> uninitialized */
841 :
842 1800 : c = (cbt->circuit_build_times[i] / CBT_BIN_WIDTH);
843 1800 : histogram[c]++;
844 : }
845 :
846 22 : return histogram;
847 : }
848 :
849 : /**
850 : * Return the Pareto start-of-curve parameter Xm.
851 : *
852 : * Because we are not a true Pareto curve, we compute this as the
853 : * weighted average of the 10 most frequent build time bins. This
854 : * heuristic allowed for the actual timeout rate to be closest
855 : * to the chosen quantile cutoff, for quantiles 60-80%, out of
856 : * many variant approaches (see #40157 for analysis).
857 : */
858 : STATIC build_time_t
859 17 : circuit_build_times_get_xm(circuit_build_times_t *cbt)
860 : {
861 17 : build_time_t nbins = 0;
862 17 : build_time_t *nth_max_bin;
863 17 : build_time_t xm_total = 0;
864 17 : build_time_t Xm = 0;
865 17 : int32_t xm_counts=0;
866 17 : int num_modes = circuit_build_times_default_num_xm_modes();
867 17 : uint32_t *histogram = circuit_build_times_create_histogram(cbt, &nbins);
868 :
869 17 : tor_assert(nbins > 0);
870 17 : tor_assert(num_modes > 0);
871 :
872 17 : nth_max_bin = tor_calloc(num_modes, sizeof(build_time_t));
873 :
874 : /* Determine the N most common build times, by selecting the
875 : * nth largest mode, counting it, and removing it from the histogram. */
876 175 : for (int n = 0; n < num_modes; n++) {
877 : /* Get nth mode */
878 30852766 : for (build_time_t i = 0; i < nbins; i++) {
879 30852608 : if (histogram[i] > histogram[nth_max_bin[n]]) {
880 154 : nth_max_bin[n] = i;
881 : }
882 : }
883 :
884 : /* Update average */
885 158 : xm_counts += histogram[nth_max_bin[n]];
886 158 : xm_total += CBT_BIN_TO_MS(nth_max_bin[n])*histogram[nth_max_bin[n]];
887 :
888 : /* Prevent from re-counting this value */
889 158 : histogram[nth_max_bin[n]] = 0;
890 : }
891 :
892 : /* xm_counts can become zero if all of our last CBT_NCIRCUITS_TO_OBSERVE
893 : * circuits were abandoned before they completed. This shouldn't happen,
894 : * though. We should have reset/re-learned a lower timeout first. */
895 17 : if (xm_counts == 0) {
896 0 : log_warn(LD_CIRC,
897 : "No valid circuit build time data out of %d times, %u modes, "
898 : "have_timeout=%d, %lfms", cbt->total_build_times, num_modes,
899 : cbt->have_computed_timeout, cbt->timeout_ms);
900 0 : goto done;
901 : }
902 :
903 17 : Xm = xm_total / xm_counts;
904 :
905 17 : done:
906 17 : tor_free(histogram);
907 17 : tor_free(nth_max_bin);
908 :
909 17 : return Xm;
910 : }
911 :
912 : /**
913 : * Output a histogram of current circuit build times to
914 : * the or_state_t state structure.
915 : */
916 : void
917 5 : circuit_build_times_update_state(const circuit_build_times_t *cbt,
918 : or_state_t *state)
919 : {
920 5 : uint32_t *histogram;
921 5 : build_time_t i = 0;
922 5 : build_time_t nbins = 0;
923 5 : config_line_t **next, *line;
924 :
925 5 : histogram = circuit_build_times_create_histogram(cbt, &nbins);
926 : // write to state
927 5 : config_free_lines(state->BuildtimeHistogram);
928 5 : next = &state->BuildtimeHistogram;
929 5 : *next = NULL;
930 :
931 5 : state->TotalBuildTimes = cbt->total_build_times;
932 5 : state->CircuitBuildAbandonedCount = 0;
933 :
934 5005 : for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
935 5000 : if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED)
936 0 : state->CircuitBuildAbandonedCount++;
937 : }
938 :
939 615979 : for (i = 0; i < nbins; i++) {
940 : // compress the histogram by skipping the blanks
941 615974 : if (histogram[i] == 0) continue;
942 96 : *next = line = tor_malloc_zero(sizeof(config_line_t));
943 96 : line->key = tor_strdup("CircuitBuildTimeBin");
944 96 : tor_asprintf(&line->value, "%d %d",
945 96 : CBT_BIN_TO_MS(i), histogram[i]);
946 96 : next = &(line->next);
947 : }
948 :
949 5 : if (!unit_tests) {
950 4 : if (!get_options()->AvoidDiskWrites)
951 4 : or_state_mark_dirty(get_or_state(), 0);
952 : }
953 :
954 5 : tor_free(histogram);
955 5 : }
956 :
957 : /**
958 : * Shuffle the build times array.
959 : *
960 : * Adapted from https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
961 : */
962 : static void
963 5 : circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt,
964 : build_time_t *raw_times,
965 : uint32_t num_times)
966 : {
967 5 : uint32_t n = num_times;
968 5 : if (num_times > CBT_NCIRCUITS_TO_OBSERVE) {
969 0 : log_notice(LD_CIRC, "The number of circuit times that this Tor version "
970 : "uses to calculate build times is less than the number stored "
971 : "in your state file. Decreasing the circuit time history from "
972 : "%lu to %d.", (unsigned long)num_times,
973 : CBT_NCIRCUITS_TO_OBSERVE);
974 : }
975 :
976 5 : if (n > INT_MAX-1) {
977 0 : log_warn(LD_CIRC, "For some insane reasons, you had %lu circuit build "
978 : "observations in your state file. That's far too many; probably "
979 : "there's a bug here.", (unsigned long)n);
980 0 : n = INT_MAX-1;
981 : }
982 :
983 : /* This code can only be run on a compact array */
984 104 : while (n-- > 1) {
985 99 : int k = crypto_rand_int(n + 1); /* 0 <= k <= n. */
986 99 : build_time_t tmp = raw_times[k];
987 99 : raw_times[k] = raw_times[n];
988 99 : raw_times[n] = tmp;
989 : }
990 :
991 : /* Since the times are now shuffled, take a random CBT_NCIRCUITS_TO_OBSERVE
992 : * subset (ie the first CBT_NCIRCUITS_TO_OBSERVE values) */
993 105 : for (n = 0; n < MIN(num_times, CBT_NCIRCUITS_TO_OBSERVE); n++) {
994 100 : circuit_build_times_add_time(cbt, raw_times[n]);
995 : }
996 5 : }
997 :
998 : /**
999 : * Load histogram from <b>state</b>, shuffling the resulting array
1000 : * after we do so. Use this result to estimate parameters and
1001 : * calculate the timeout.
1002 : *
1003 : * Return -1 on error.
1004 : */
1005 : int
1006 5 : circuit_build_times_parse_state(circuit_build_times_t *cbt,
1007 : or_state_t *state)
1008 : {
1009 5 : int tot_values = 0;
1010 5 : uint32_t loaded_cnt = 0, N = 0;
1011 5 : config_line_t *line;
1012 5 : int i;
1013 5 : build_time_t *loaded_times;
1014 5 : int err = 0;
1015 5 : circuit_build_times_init(cbt);
1016 :
1017 5 : if (circuit_build_times_disabled(get_options())) {
1018 : return 0;
1019 : }
1020 :
1021 : /* build_time_t 0 means uninitialized */
1022 5 : loaded_times = tor_calloc(state->TotalBuildTimes, sizeof(build_time_t));
1023 :
1024 101 : for (line = state->BuildtimeHistogram; line; line = line->next) {
1025 96 : smartlist_t *args = smartlist_new();
1026 96 : smartlist_split_string(args, line->value, " ",
1027 : SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
1028 96 : if (smartlist_len(args) < 2) {
1029 0 : log_warn(LD_GENERAL, "Unable to parse circuit build times: "
1030 : "Too few arguments to CircuitBuildTime");
1031 0 : err = 1;
1032 0 : SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
1033 0 : smartlist_free(args);
1034 0 : break;
1035 : } else {
1036 96 : const char *ms_str = smartlist_get(args,0);
1037 96 : const char *count_str = smartlist_get(args,1);
1038 96 : uint32_t count, k;
1039 96 : build_time_t ms;
1040 96 : int ok;
1041 96 : ms = (build_time_t)tor_parse_ulong(ms_str, 10, 0,
1042 : CBT_BUILD_TIME_MAX, &ok, NULL);
1043 96 : if (!ok) {
1044 0 : log_warn(LD_GENERAL, "Unable to parse circuit build times: "
1045 : "Unparsable bin number");
1046 0 : err = 1;
1047 0 : SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
1048 0 : smartlist_free(args);
1049 0 : break;
1050 : }
1051 96 : count = (uint32_t)tor_parse_ulong(count_str, 10, 0,
1052 : UINT32_MAX, &ok, NULL);
1053 96 : if (!ok) {
1054 0 : log_warn(LD_GENERAL, "Unable to parse circuit build times: "
1055 : "Unparsable bin count");
1056 0 : err = 1;
1057 0 : SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
1058 0 : smartlist_free(args);
1059 0 : break;
1060 : }
1061 :
1062 96 : if (loaded_cnt+count+ (unsigned)state->CircuitBuildAbandonedCount
1063 96 : > (unsigned) state->TotalBuildTimes) {
1064 0 : log_warn(LD_CIRC,
1065 : "Too many build times in state file. "
1066 : "Stopping short before %d",
1067 : loaded_cnt+count);
1068 0 : SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
1069 0 : smartlist_free(args);
1070 0 : break;
1071 : }
1072 :
1073 196 : for (k = 0; k < count; k++) {
1074 100 : loaded_times[loaded_cnt++] = ms;
1075 : }
1076 96 : N++;
1077 288 : SMARTLIST_FOREACH(args, char*, cp, tor_free(cp));
1078 96 : smartlist_free(args);
1079 : }
1080 : }
1081 :
1082 5 : log_info(LD_CIRC,
1083 : "Adding %d timeouts.", state->CircuitBuildAbandonedCount);
1084 10 : for (i=0; i < state->CircuitBuildAbandonedCount; i++) {
1085 0 : loaded_times[loaded_cnt++] = CBT_BUILD_ABANDONED;
1086 : }
1087 :
1088 5 : if (loaded_cnt != (unsigned)state->TotalBuildTimes) {
1089 0 : log_warn(LD_CIRC,
1090 : "Corrupt state file? Build times count mismatch. "
1091 : "Read %d times, but file says %d", loaded_cnt,
1092 : state->TotalBuildTimes);
1093 0 : err = 1;
1094 0 : circuit_build_times_reset(cbt);
1095 0 : goto done;
1096 : }
1097 :
1098 5 : circuit_build_times_shuffle_and_store_array(cbt, loaded_times, loaded_cnt);
1099 :
1100 : /* Verify that we didn't overwrite any indexes */
1101 110 : for (i=0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
1102 105 : if (!cbt->circuit_build_times[i])
1103 : break;
1104 100 : tot_values++;
1105 : }
1106 5 : log_info(LD_CIRC,
1107 : "Loaded %d/%d values from %d lines in circuit time histogram",
1108 : tot_values, cbt->total_build_times, N);
1109 :
1110 5 : if (cbt->total_build_times != tot_values
1111 : || cbt->total_build_times > CBT_NCIRCUITS_TO_OBSERVE) {
1112 0 : log_warn(LD_CIRC,
1113 : "Corrupt state file? Shuffled build times mismatch. "
1114 : "Read %d times, but file says %d", tot_values,
1115 : state->TotalBuildTimes);
1116 0 : err = 1;
1117 0 : circuit_build_times_reset(cbt);
1118 0 : goto done;
1119 : }
1120 :
1121 5 : circuit_build_times_set_timeout(cbt);
1122 :
1123 5 : done:
1124 5 : tor_free(loaded_times);
1125 5 : return err ? -1 : 0;
1126 : }
1127 :
1128 : /**
1129 : * Estimates the Xm and Alpha parameters using
1130 : * https://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
1131 : *
1132 : * The notable difference is that we use mode instead of min to estimate Xm.
1133 : * This is because our distribution is frechet-like. We claim this is
1134 : * an acceptable approximation because we are only concerned with the
1135 : * accuracy of the CDF of the tail.
1136 : */
1137 : STATIC int
1138 11 : circuit_build_times_update_alpha(circuit_build_times_t *cbt)
1139 : {
1140 11 : build_time_t *x=cbt->circuit_build_times;
1141 11 : double a = 0;
1142 11 : int n=0,i=0,abandoned_count=0;
1143 :
1144 : /* https://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation */
1145 : /* We sort of cheat here and make our samples slightly more pareto-like
1146 : * and less frechet-like. */
1147 11 : cbt->Xm = circuit_build_times_get_xm(cbt);
1148 :
1149 : /* If Xm came back 0, then too many circuits were abandoned. */
1150 11 : if (cbt->Xm == 0)
1151 : return 0;
1152 :
1153 : tor_assert(cbt->Xm > 0);
1154 :
1155 11011 : for (i=0; i< CBT_NCIRCUITS_TO_OBSERVE; i++) {
1156 11000 : if (!x[i]) {
1157 9840 : continue;
1158 : }
1159 :
1160 1160 : if (x[i] < cbt->Xm) {
1161 455 : a += tor_mathlog(cbt->Xm);
1162 455 : n++;
1163 705 : } else if (x[i] == CBT_BUILD_ABANDONED) {
1164 60 : abandoned_count++;
1165 : } else {
1166 645 : a += tor_mathlog(x[i]);
1167 645 : n++;
1168 : }
1169 : }
1170 :
1171 : /*
1172 : * We are erring and asserting here because this can only happen
1173 : * in codepaths other than startup. The startup state parsing code
1174 : * performs this same check, and resets state if it hits it. If we
1175 : * hit it at runtime, something serious has gone wrong.
1176 : */
1177 11 : if (n!=cbt->total_build_times-abandoned_count) {
1178 0 : log_err(LD_CIRC, "Discrepancy in build times count: %d vs %d", n,
1179 : cbt->total_build_times);
1180 : }
1181 11 : tor_assert_nonfatal(n==cbt->total_build_times-abandoned_count);
1182 :
1183 : /* This is the "Maximum Likelihood Estimator" for parameter alpha of a Pareto
1184 : * Distribution. See:
1185 : * https://en.wikipedia.org/wiki/Pareto_distribution#Estimation_of_parameters
1186 : *
1187 : * The division in the estimator is done with subtraction outside the ln(),
1188 : * with the sum occurring in the for loop above.
1189 : *
1190 : * This done is to avoid the precision issues of logs of small values.
1191 : */
1192 11 : a -= n*tor_mathlog(cbt->Xm);
1193 11 : a = n/a;
1194 :
1195 11 : cbt->alpha = a;
1196 :
1197 11 : return 1;
1198 : }
1199 :
1200 : /**
1201 : * This is the Pareto Quantile Function. It calculates the point x
1202 : * in the distribution such that F(x) = quantile (ie quantile*100%
1203 : * of the mass of the density function is below x on the curve).
1204 : *
1205 : * We use it to calculate the timeout and also to generate synthetic
1206 : * values of time for circuits that timeout before completion.
1207 : *
1208 : * See https://en.wikipedia.org/wiki/Quantile_function,
1209 : * https://en.wikipedia.org/wiki/Inverse_transform_sampling and
1210 : * https://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_
1211 : * random_sample_from_Pareto_distribution
1212 : * That's right. I'll cite wikipedia all day long.
1213 : *
1214 : * Return value is in milliseconds, clamped to INT32_MAX.
1215 : */
1216 : STATIC double
1217 4208 : circuit_build_times_calculate_timeout(circuit_build_times_t *cbt,
1218 : double quantile)
1219 : {
1220 4208 : double ret;
1221 4208 : tor_assert(quantile >= 0);
1222 4208 : tor_assert(1.0-quantile > 0);
1223 4208 : tor_assert(cbt->Xm > 0);
1224 :
1225 : /* If either alpha or p are 0, we would divide by zero, yielding an
1226 : * infinite (double) result; which would be clamped to INT32_MAX.
1227 : * Instead, initialise ret to INT32_MAX, and skip over these
1228 : * potentially illegal/trapping divides by zero.
1229 : */
1230 4208 : ret = INT32_MAX;
1231 :
1232 4208 : if (cbt->alpha > 0) {
1233 4158 : double p;
1234 4158 : p = pow(1.0-quantile,1.0/cbt->alpha);
1235 4158 : if (p > 0) {
1236 4158 : ret = cbt->Xm/p;
1237 : }
1238 : }
1239 :
1240 4208 : if (ret > INT32_MAX) {
1241 0 : ret = INT32_MAX;
1242 : }
1243 4208 : tor_assert(ret > 0);
1244 4208 : return ret;
1245 : }
1246 :
1247 : #ifdef TOR_UNIT_TESTS
1248 : /** Pareto CDF */
1249 : double
1250 4 : circuit_build_times_cdf(circuit_build_times_t *cbt, double x)
1251 : {
1252 4 : double ret;
1253 4 : tor_assert(cbt->Xm > 0);
1254 4 : ret = 1.0-pow(cbt->Xm/x,cbt->alpha);
1255 4 : tor_assert(0 <= ret && ret <= 1.0);
1256 4 : return ret;
1257 : }
1258 : #endif /* defined(TOR_UNIT_TESTS) */
1259 :
1260 : #ifdef TOR_UNIT_TESTS
1261 : /**
1262 : * Generate a synthetic time using our distribution parameters.
1263 : *
1264 : * The return value will be within the [q_lo, q_hi) quantile points
1265 : * on the CDF.
1266 : */
1267 : build_time_t
1268 4100 : circuit_build_times_generate_sample(circuit_build_times_t *cbt,
1269 : double q_lo, double q_hi)
1270 : {
1271 4100 : double randval = crypto_rand_double();
1272 4100 : build_time_t ret;
1273 4100 : double u;
1274 :
1275 : /* Generate between [q_lo, q_hi) */
1276 : /*XXXX This is what nextafter is supposed to be for; we should use it on the
1277 : * platforms that support it. */
1278 4100 : q_hi -= 1.0/(INT32_MAX);
1279 :
1280 4100 : tor_assert(q_lo >= 0);
1281 4100 : tor_assert(q_hi < 1);
1282 4100 : tor_assert(q_lo < q_hi);
1283 :
1284 4100 : u = q_lo + (q_hi-q_lo)*randval;
1285 :
1286 4100 : tor_assert(0 <= u && u < 1.0);
1287 : /* circuit_build_times_calculate_timeout returns <= INT32_MAX */
1288 8200 : ret = (build_time_t)
1289 4100 : tor_lround(circuit_build_times_calculate_timeout(cbt, u));
1290 4100 : tor_assert(ret > 0);
1291 4100 : return ret;
1292 : }
1293 : #endif /* defined(TOR_UNIT_TESTS) */
1294 :
1295 : #ifdef TOR_UNIT_TESTS
1296 : /**
1297 : * Estimate an initial alpha parameter by solving the quantile
1298 : * function with a quantile point and a specific timeout value.
1299 : */
1300 : void
1301 1 : circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
1302 : double quantile, double timeout_ms)
1303 : {
1304 : // Q(u) = Xm/((1-u)^(1/a))
1305 : // Q(0.8) = Xm/((1-0.8))^(1/a)) = CircBuildTimeout
1306 : // CircBuildTimeout = Xm/((1-0.8))^(1/a))
1307 : // CircBuildTimeout = Xm*((1-0.8))^(-1/a))
1308 : // ln(CircBuildTimeout) = ln(Xm)+ln(((1-0.8)))*(-1/a)
1309 : // -ln(1-0.8)/(ln(CircBuildTimeout)-ln(Xm))=a
1310 1 : tor_assert(quantile >= 0);
1311 1 : tor_assert(cbt->Xm > 0);
1312 1 : cbt->alpha = tor_mathlog(1.0-quantile)/
1313 1 : (tor_mathlog(cbt->Xm)-tor_mathlog(timeout_ms));
1314 1 : tor_assert(cbt->alpha > 0);
1315 1 : }
1316 : #endif /* defined(TOR_UNIT_TESTS) */
1317 :
1318 : /**
1319 : * Returns true if we need circuits to be built
1320 : */
1321 : int
1322 140 : circuit_build_times_needs_circuits(const circuit_build_times_t *cbt)
1323 : {
1324 : /* Return true if < MIN_CIRCUITS_TO_OBSERVE */
1325 140 : return !circuit_build_times_enough_to_compute(cbt);
1326 : }
1327 :
1328 : /**
1329 : * Returns true if we should build a timeout test circuit
1330 : * right now.
1331 : */
1332 : int
1333 1 : circuit_build_times_needs_circuits_now(const circuit_build_times_t *cbt)
1334 : {
1335 1 : return circuit_build_times_needs_circuits(cbt) &&
1336 1 : approx_time()-cbt->last_circ_at > circuit_build_times_test_frequency();
1337 : }
1338 :
1339 : /**
1340 : * How long should we be unreachable before we think we need to check if
1341 : * our published IP address has changed.
1342 : */
1343 : #define CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP (60*3)
1344 :
1345 : /**
1346 : * Called to indicate that the network showed some signs of liveness,
1347 : * i.e. we received a cell.
1348 : *
1349 : * This is used by circuit_build_times_network_check_live() to decide
1350 : * if we should record the circuit build timeout or not.
1351 : *
1352 : * This function is called every time we receive a cell. Avoid
1353 : * syscalls, events, and other high-intensity work.
1354 : */
1355 : void
1356 121 : circuit_build_times_network_is_live(circuit_build_times_t *cbt)
1357 : {
1358 121 : time_t now = approx_time();
1359 : // XXXX this should use pubsub
1360 121 : if (cbt->liveness.nonlive_timeouts > 0) {
1361 100 : time_t time_since_live = now - cbt->liveness.network_last_live;
1362 100 : log_notice(LD_CIRC,
1363 : "Tor now sees network activity. Restoring circuit build "
1364 : "timeout recording. Network was down for %d seconds "
1365 : "during %d circuit attempts.",
1366 : (int)time_since_live,
1367 : cbt->liveness.nonlive_timeouts);
1368 100 : if (time_since_live > CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP)
1369 100 : reschedule_descriptor_update_check();
1370 : }
1371 121 : cbt->liveness.network_last_live = now;
1372 121 : cbt->liveness.nonlive_timeouts = 0;
1373 :
1374 : /* Tell control.c */
1375 121 : control_event_network_liveness_update(1);
1376 121 : }
1377 :
1378 : /**
1379 : * Non-destructively scale all of our circuit success, timeout, and close
1380 : * counts down by a factor of two. Scaling in this way preserves the
1381 : * ratios between succeeded vs timed out vs closed circuits, so that
1382 : * our statistics don't change when we scale.
1383 : *
1384 : * This is used only in the rare event that we build more than
1385 : * INT32_MAX circuits. Since the num_circ_* variables are
1386 : * uint32_t, we won't even be close to overflowing them.
1387 : */
1388 : void
1389 0 : circuit_build_times_scale_circ_counts(circuit_build_times_t *cbt)
1390 : {
1391 0 : cbt->num_circ_succeeded /= 2;
1392 0 : cbt->num_circ_timeouts /= 2;
1393 0 : cbt->num_circ_closed /= 2;
1394 0 : }
1395 :
1396 : /**
1397 : * Called to indicate that we "completed" a circuit. Because this circuit
1398 : * succeeded, it doesn't count as a timeout-after-the-first-hop.
1399 : *
1400 : * (For the purposes of the cbt code, we consider a circuit "completed" if
1401 : * it has 3 hops, regardless of its final hop count. We do this because
1402 : * we're trying to answer the question, "how long should a circuit take to
1403 : * reach the 3-hop count".)
1404 : *
1405 : * This is used by circuit_build_times_network_check_changed() to determine
1406 : * if we had too many recent timeouts and need to reset our learned timeout
1407 : * to something higher.
1408 : */
1409 : void
1410 4002 : circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
1411 : {
1412 : // Count circuit success
1413 4002 : cbt->num_circ_succeeded++;
1414 :
1415 : // If we're going to wrap int32, scale everything
1416 4002 : if (cbt->num_circ_succeeded >= INT32_MAX) {
1417 0 : circuit_build_times_scale_circ_counts(cbt);
1418 : }
1419 :
1420 : /* Check for NULLness because we might not be using adaptive timeouts */
1421 4002 : if (cbt->liveness.timeouts_after_firsthop &&
1422 4002 : cbt->liveness.num_recent_circs > 0) {
1423 4002 : cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
1424 4002 : = 0;
1425 4002 : cbt->liveness.after_firsthop_idx++;
1426 4002 : cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
1427 : }
1428 4002 : }
1429 :
1430 : /**
1431 : * A circuit just timed out. If it failed after the first hop, record it
1432 : * in our history for later deciding if the network speed has changed.
1433 : *
1434 : * This is used by circuit_build_times_network_check_changed() to determine
1435 : * if we had too many recent timeouts and need to reset our learned timeout
1436 : * to something higher.
1437 : */
1438 : static void
1439 1802 : circuit_build_times_network_timeout(circuit_build_times_t *cbt,
1440 : int did_onehop)
1441 : {
1442 : // Count circuit timeout
1443 1802 : cbt->num_circ_timeouts++;
1444 :
1445 : // If we're going to wrap int32, scale everything
1446 1802 : if (cbt->num_circ_timeouts >= INT32_MAX) {
1447 0 : circuit_build_times_scale_circ_counts(cbt);
1448 : }
1449 :
1450 : /* Check for NULLness because we might not be using adaptive timeouts */
1451 1802 : if (cbt->liveness.timeouts_after_firsthop &&
1452 1802 : cbt->liveness.num_recent_circs > 0) {
1453 1802 : if (did_onehop) {
1454 1802 : cbt->liveness.timeouts_after_firsthop[cbt->liveness.after_firsthop_idx]
1455 1802 : = 1;
1456 1802 : cbt->liveness.after_firsthop_idx++;
1457 1802 : cbt->liveness.after_firsthop_idx %= cbt->liveness.num_recent_circs;
1458 : }
1459 : }
1460 1802 : }
1461 :
1462 : /**
1463 : * A circuit was just forcibly closed. If there has been no recent network
1464 : * activity at all, but this circuit was launched back when we thought the
1465 : * network was live, increment the number of "nonlive" circuit timeouts.
1466 : *
1467 : * This is used by circuit_build_times_network_check_live() to decide
1468 : * if we should record the circuit build timeout or not.
1469 : */
1470 : static void
1471 100 : circuit_build_times_network_close(circuit_build_times_t *cbt,
1472 : int did_onehop, time_t start_time)
1473 : {
1474 100 : time_t now = time(NULL);
1475 :
1476 : // Count circuit close
1477 100 : cbt->num_circ_closed++;
1478 :
1479 : // If we're going to wrap int32, scale everything
1480 100 : if (cbt->num_circ_closed >= INT32_MAX) {
1481 0 : circuit_build_times_scale_circ_counts(cbt);
1482 : }
1483 :
1484 : /*
1485 : * Check if this is a timeout that was for a circuit that spent its
1486 : * entire existence during a time where we have had no network activity.
1487 : */
1488 100 : if (cbt->liveness.network_last_live < start_time) {
1489 100 : if (did_onehop) {
1490 0 : char last_live_buf[ISO_TIME_LEN+1];
1491 0 : char start_time_buf[ISO_TIME_LEN+1];
1492 0 : char now_buf[ISO_TIME_LEN+1];
1493 0 : format_local_iso_time(last_live_buf, cbt->liveness.network_last_live);
1494 0 : format_local_iso_time(start_time_buf, start_time);
1495 0 : format_local_iso_time(now_buf, now);
1496 0 : log_notice(LD_CIRC,
1497 : "A circuit somehow completed a hop while the network was "
1498 : "not live. The network was last live at %s, but the circuit "
1499 : "launched at %s. It's now %s. This could mean your clock "
1500 : "changed.", last_live_buf, start_time_buf, now_buf);
1501 : }
1502 100 : cbt->liveness.nonlive_timeouts++;
1503 100 : if (cbt->liveness.nonlive_timeouts == 1) {
1504 100 : log_notice(LD_CIRC,
1505 : "Tor has not observed any network activity for the past %d "
1506 : "seconds. Disabling circuit build timeout recording.",
1507 : (int)(now - cbt->liveness.network_last_live));
1508 :
1509 : /* Tell control.c */
1510 100 : control_event_network_liveness_update(0);
1511 : } else {
1512 0 : log_info(LD_CIRC,
1513 : "Got non-live timeout. Current count is: %d",
1514 : cbt->liveness.nonlive_timeouts);
1515 : }
1516 : }
1517 100 : }
1518 :
1519 : /**
1520 : * When the network is not live, we do not record circuit build times.
1521 : *
1522 : * The network is considered not live if there has been at least one
1523 : * circuit build that began and ended (had its close_ms measurement
1524 : * period expire) since we last received a cell.
1525 : *
1526 : * Also has the side effect of rewinding the circuit time history
1527 : * in the case of recent liveness changes.
1528 : */
1529 : int
1530 403 : circuit_build_times_network_check_live(const circuit_build_times_t *cbt)
1531 : {
1532 403 : if (cbt->liveness.nonlive_timeouts > 0) {
1533 200 : return 0;
1534 : }
1535 :
1536 : return 1;
1537 : }
1538 :
1539 : /**
1540 : * Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of
1541 : * the past RECENT_CIRCUITS time out after the first hop. Used to detect
1542 : * if the network connection has changed significantly, and if so,
1543 : * resets our circuit build timeout to the default.
1544 : *
1545 : * Also resets the entire timeout history in this case and causes us
1546 : * to restart the process of building test circuits and estimating a
1547 : * new timeout.
1548 : */
1549 : STATIC int
1550 1902 : circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
1551 : {
1552 1902 : int total_build_times = cbt->total_build_times;
1553 1902 : int timeout_count=0;
1554 1902 : int i;
1555 :
1556 1902 : if (cbt->liveness.timeouts_after_firsthop &&
1557 1902 : cbt->liveness.num_recent_circs > 0) {
1558 : /* how many of our recent circuits made it to the first hop but then
1559 : * timed out? */
1560 39942 : for (i = 0; i < cbt->liveness.num_recent_circs; i++) {
1561 38040 : timeout_count += cbt->liveness.timeouts_after_firsthop[i];
1562 : }
1563 : }
1564 :
1565 : /* If 80% of our recent circuits are timing out after the first hop,
1566 : * we need to re-estimate a new initial alpha and timeout. */
1567 1902 : if (timeout_count < circuit_build_times_max_timeouts()) {
1568 : return 0;
1569 : }
1570 :
1571 100 : circuit_build_times_reset(cbt);
1572 100 : if (cbt->liveness.timeouts_after_firsthop &&
1573 100 : cbt->liveness.num_recent_circs > 0) {
1574 100 : memset(cbt->liveness.timeouts_after_firsthop, 0,
1575 : sizeof(*cbt->liveness.timeouts_after_firsthop)*
1576 : cbt->liveness.num_recent_circs);
1577 : }
1578 100 : cbt->liveness.after_firsthop_idx = 0;
1579 :
1580 : #define MAX_TIMEOUT ((int32_t) (INT32_MAX/2))
1581 : /* Check to see if this has happened before. If so, double the timeout
1582 : * to give clients on abysmally bad network connections a shot at access */
1583 100 : if (cbt->timeout_ms >= circuit_build_times_get_initial_timeout()) {
1584 100 : if (cbt->timeout_ms > MAX_TIMEOUT || cbt->close_ms > MAX_TIMEOUT) {
1585 0 : log_warn(LD_CIRC, "Insanely large circuit build timeout value. "
1586 : "(timeout = %fmsec, close = %fmsec)",
1587 : cbt->timeout_ms, cbt->close_ms);
1588 : } else {
1589 100 : cbt->timeout_ms *= 2;
1590 100 : cbt->close_ms *= 2;
1591 : }
1592 : } else {
1593 0 : cbt->close_ms = cbt->timeout_ms
1594 0 : = circuit_build_times_get_initial_timeout();
1595 : }
1596 : #undef MAX_TIMEOUT
1597 :
1598 100 : cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
1599 :
1600 100 : log_notice(LD_CIRC,
1601 : "Your network connection speed appears to have changed. Resetting "
1602 : "timeout to %ldms after %d timeouts and %d buildtimes.",
1603 : tor_lround(cbt->timeout_ms), timeout_count, total_build_times);
1604 :
1605 100 : return 1;
1606 : }
1607 :
1608 : /**
1609 : * Count the number of timeouts in a set of cbt data.
1610 : */
1611 : double
1612 3 : circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
1613 : {
1614 3 : int i=0,timeouts=0;
1615 3003 : for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
1616 3000 : if (cbt->circuit_build_times[i] >= cbt->timeout_ms) {
1617 60 : timeouts++;
1618 : }
1619 : }
1620 :
1621 3 : if (!cbt->total_build_times)
1622 : return 0;
1623 :
1624 3 : return ((double)timeouts)/cbt->total_build_times;
1625 : }
1626 :
1627 : /**
1628 : * Count the number of closed circuits in a set of cbt data.
1629 : */
1630 : double
1631 0 : circuit_build_times_close_rate(const circuit_build_times_t *cbt)
1632 : {
1633 0 : int i=0,closed=0;
1634 0 : for (i = 0; i < CBT_NCIRCUITS_TO_OBSERVE; i++) {
1635 0 : if (cbt->circuit_build_times[i] == CBT_BUILD_ABANDONED) {
1636 0 : closed++;
1637 : }
1638 : }
1639 :
1640 0 : if (!cbt->total_build_times)
1641 : return 0;
1642 :
1643 0 : return ((double)closed)/cbt->total_build_times;
1644 : }
1645 :
1646 : /**
1647 : * Store a timeout as a synthetic value.
1648 : *
1649 : * Returns true if the store was successful and we should possibly
1650 : * update our timeout estimate.
1651 : */
1652 : int
1653 100 : circuit_build_times_count_close(circuit_build_times_t *cbt,
1654 : int did_onehop,
1655 : time_t start_time)
1656 : {
1657 100 : if (circuit_build_times_disabled(get_options())) {
1658 0 : cbt->close_ms = cbt->timeout_ms
1659 0 : = circuit_build_times_get_initial_timeout();
1660 0 : return 0;
1661 : }
1662 :
1663 : /* Record this force-close to help determine if the network is dead */
1664 100 : circuit_build_times_network_close(cbt, did_onehop, start_time);
1665 :
1666 : /* Only count timeouts if network is live.. */
1667 100 : if (!circuit_build_times_network_check_live(cbt)) {
1668 : return 0;
1669 : }
1670 :
1671 0 : circuit_build_times_add_time(cbt, CBT_BUILD_ABANDONED);
1672 0 : return 1;
1673 : }
1674 :
1675 : /**
1676 : * Update timeout counts to determine if we need to expire
1677 : * our build time history due to excessive timeouts.
1678 : *
1679 : * We do not record any actual time values at this stage;
1680 : * we are only interested in recording the fact that a timeout
1681 : * happened. We record the time values via
1682 : * circuit_build_times_count_close() and circuit_build_times_add_time().
1683 : */
1684 : void
1685 1802 : circuit_build_times_count_timeout(circuit_build_times_t *cbt,
1686 : int did_onehop)
1687 : {
1688 1802 : if (circuit_build_times_disabled(get_options())) {
1689 0 : cbt->close_ms = cbt->timeout_ms
1690 0 : = circuit_build_times_get_initial_timeout();
1691 0 : return;
1692 : }
1693 :
1694 : /* Register the fact that a timeout just occurred. */
1695 1802 : circuit_build_times_network_timeout(cbt, did_onehop);
1696 :
1697 : /* If there are a ton of timeouts, we should reset
1698 : * the circuit build timeout. */
1699 1802 : circuit_build_times_network_check_changed(cbt);
1700 : }
1701 :
1702 : /**
1703 : * Estimate a new timeout based on history and set our timeout
1704 : * variable accordingly.
1705 : */
1706 : static int
1707 10 : circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
1708 : {
1709 10 : build_time_t max_time;
1710 10 : if (!circuit_build_times_enough_to_compute(cbt))
1711 : return 0;
1712 :
1713 3 : if (!circuit_build_times_update_alpha(cbt))
1714 : return 0;
1715 :
1716 3 : cbt->timeout_ms = circuit_build_times_calculate_timeout(cbt,
1717 : circuit_build_times_quantile_cutoff());
1718 :
1719 3 : cbt->close_ms = circuit_build_times_calculate_timeout(cbt,
1720 : circuit_build_times_close_quantile());
1721 :
1722 3 : max_time = circuit_build_times_max(cbt);
1723 :
1724 3 : if (cbt->timeout_ms > max_time) {
1725 0 : log_info(LD_CIRC,
1726 : "Circuit build timeout of %dms is beyond the maximum build "
1727 : "time we have ever observed. Capping it to %dms.",
1728 : (int)cbt->timeout_ms, max_time);
1729 0 : cbt->timeout_ms = max_time;
1730 : }
1731 :
1732 3 : if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
1733 0 : log_info(LD_CIRC,
1734 : "Circuit build measurement period of %dms is more than twice "
1735 : "the maximum build time we have ever observed. Capping it to "
1736 : "%dms.", (int)cbt->close_ms, 2*max_time);
1737 0 : cbt->close_ms = 2*max_time;
1738 : }
1739 :
1740 : /* Sometimes really fast guard nodes give us such a steep curve
1741 : * that this ends up being not that much greater than timeout_ms.
1742 : * Make it be at least 1 min to handle this case. */
1743 3 : cbt->close_ms = MAX(cbt->close_ms, circuit_build_times_initial_timeout());
1744 :
1745 3 : cbt->have_computed_timeout = 1;
1746 3 : return 1;
1747 : }
1748 :
1749 : /**
1750 : * Exposed function to compute a new timeout. Dispatches events and
1751 : * also filters out extremely high timeout values.
1752 : */
1753 : void
1754 10 : circuit_build_times_set_timeout(circuit_build_times_t *cbt)
1755 : {
1756 10 : long prev_timeout = tor_lround(cbt->timeout_ms/1000);
1757 10 : double timeout_rate;
1758 :
1759 : /*
1760 : * Just return if we aren't using adaptive timeouts
1761 : */
1762 10 : if (circuit_build_times_disabled(get_options()))
1763 : return;
1764 :
1765 10 : if (!circuit_build_times_set_timeout_worker(cbt))
1766 : return;
1767 :
1768 3 : if (cbt->timeout_ms < circuit_build_times_min_timeout()) {
1769 0 : log_notice(LD_CIRC, "Set buildtimeout to low value %fms. Setting to %dms",
1770 : cbt->timeout_ms, circuit_build_times_min_timeout());
1771 0 : cbt->timeout_ms = circuit_build_times_min_timeout();
1772 0 : if (cbt->close_ms < cbt->timeout_ms) {
1773 : /* This shouldn't happen because of MAX() in timeout_worker above,
1774 : * but doing it just in case */
1775 0 : cbt->close_ms = circuit_build_times_initial_timeout();
1776 : }
1777 : }
1778 :
1779 3 : cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
1780 :
1781 3 : timeout_rate = circuit_build_times_timeout_rate(cbt);
1782 :
1783 3 : if (prev_timeout > tor_lround(cbt->timeout_ms/1000)) {
1784 2 : log_info(LD_CIRC,
1785 : "Based on %d circuit times, it looks like we don't need to "
1786 : "wait so long for circuits to finish. We will now assume a "
1787 : "circuit is too slow to use after waiting %ld milliseconds.",
1788 : cbt->total_build_times,
1789 : tor_lround(cbt->timeout_ms));
1790 2 : log_info(LD_CIRC,
1791 : "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
1792 : cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
1793 : timeout_rate);
1794 1 : } else if (prev_timeout < tor_lround(cbt->timeout_ms/1000)) {
1795 0 : log_info(LD_CIRC,
1796 : "Based on %d circuit times, it looks like we need to wait "
1797 : "longer for circuits to finish. We will now assume a "
1798 : "circuit is too slow to use after waiting %ld milliseconds.",
1799 : cbt->total_build_times,
1800 : tor_lround(cbt->timeout_ms));
1801 0 : log_info(LD_CIRC,
1802 : "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
1803 : cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha,
1804 : timeout_rate);
1805 : } else {
1806 1 : log_info(LD_CIRC,
1807 : "Set circuit build timeout to %ldms (%fms, %fms, Xm: %d, a: %f,"
1808 : " r: %f) based on %d circuit times",
1809 : tor_lround(cbt->timeout_ms),
1810 : cbt->timeout_ms, cbt->close_ms, cbt->Xm, cbt->alpha, timeout_rate,
1811 : cbt->total_build_times);
1812 : }
1813 : }
1814 :
1815 : #ifdef TOR_UNIT_TESTS
1816 : /** Make a note that we're running unit tests (rather than running Tor
1817 : * itself), so we avoid clobbering our state file. */
1818 : void
1819 1 : circuitbuild_running_unit_tests(void)
1820 : {
1821 1 : unit_tests = 1;
1822 1 : }
1823 : #endif /* defined(TOR_UNIT_TESTS) */
1824 :
1825 : void
1826 139 : circuit_build_times_update_last_circ(circuit_build_times_t *cbt)
1827 : {
1828 139 : cbt->last_circ_at = approx_time();
1829 139 : }
|
