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