Tor  0.4.5.0-alpha-dev
circuitstats.h
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.h
9  * \brief Header file for circuitstats.c
10  **/
11 
12 #ifndef TOR_CIRCUITSTATS_H
13 #define TOR_CIRCUITSTATS_H
14 
18 double get_circuit_build_timeout_ms(void);
19 
20 int circuit_build_times_disabled(const or_options_t *options);
22  int ignore_consensus);
23 
24 /** A build_time_t is milliseconds */
25 typedef uint32_t build_time_t;
26 
29  or_state_t *state);
31  or_state_t *state);
33  int did_onehop);
35  int did_onehop, time_t start_time);
38  build_time_t time);
41 
46  const networkstatus_t *ns);
49 
50 void circuit_build_times_update_last_circ(circuit_build_times_t *cbt);
53 
54 /** Total size of the circuit timeout history to accumulate.
55  * 1000 is approx 2.5 days worth of continual-use circuits. */
56 #define CBT_NCIRCUITS_TO_OBSERVE 1000
57 
58 /** Width of the histogram bins in milliseconds */
59 #define CBT_BIN_WIDTH ((build_time_t)50)
60 
61 /** Number of modes to use in the weighted-avg computation of Xm */
62 #define CBT_DEFAULT_NUM_XM_MODES 3
63 #define CBT_MIN_NUM_XM_MODES 1
64 #define CBT_MAX_NUM_XM_MODES 20
65 
66 /**
67  * CBT_BUILD_ABANDONED is our flag value to represent a force-closed
68  * circuit (Aka a 'right-censored' pareto value).
69  */
70 #define CBT_BUILD_ABANDONED ((build_time_t)(INT32_MAX-1))
71 #define CBT_BUILD_TIME_MAX ((build_time_t)(INT32_MAX))
72 
73 /** Save state every 10 circuits */
74 #define CBT_SAVE_STATE_EVERY 10
75 
76 /* Circuit build times consensus parameters */
77 
78 /**
79  * How long to wait before actually closing circuits that take too long to
80  * build in terms of CDF quantile.
81  */
82 #define CBT_DEFAULT_CLOSE_QUANTILE 95
83 #define CBT_MIN_CLOSE_QUANTILE CBT_MIN_QUANTILE_CUTOFF
84 #define CBT_MAX_CLOSE_QUANTILE CBT_MAX_QUANTILE_CUTOFF
85 
86 /**
87  * How many circuits count as recent when considering if the
88  * connection has gone gimpy or changed.
89  */
90 #define CBT_DEFAULT_RECENT_CIRCUITS 20
91 #define CBT_MIN_RECENT_CIRCUITS 3
92 #define CBT_MAX_RECENT_CIRCUITS 1000
93 
94 /**
95  * Maximum count of timeouts that finish the first hop in the past
96  * RECENT_CIRCUITS before calculating a new timeout.
97  *
98  * This tells us whether to abandon timeout history and set
99  * the timeout back to whatever circuit_build_times_get_initial_timeout()
100  * gives us.
101  */
102 #define CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT (CBT_DEFAULT_RECENT_CIRCUITS*9/10)
103 #define CBT_MIN_MAX_RECENT_TIMEOUT_COUNT 3
104 #define CBT_MAX_MAX_RECENT_TIMEOUT_COUNT 10000
105 
106 /** Minimum circuits before estimating a timeout */
107 #define CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE 100
108 #define CBT_MIN_MIN_CIRCUITS_TO_OBSERVE 1
109 #define CBT_MAX_MIN_CIRCUITS_TO_OBSERVE 10000
110 
111 /** Cutoff percentile on the CDF for our timeout estimation. */
112 #define CBT_DEFAULT_QUANTILE_CUTOFF 80
113 #define CBT_MIN_QUANTILE_CUTOFF 10
114 #define CBT_MAX_QUANTILE_CUTOFF 99
116 
117 /** How often in seconds should we build a test circuit */
118 #define CBT_DEFAULT_TEST_FREQUENCY 10
119 #define CBT_MIN_TEST_FREQUENCY 1
120 #define CBT_MAX_TEST_FREQUENCY INT32_MAX
121 
122 /** Lowest allowable value for CircuitBuildTimeout in milliseconds */
123 #define CBT_DEFAULT_TIMEOUT_MIN_VALUE (1500)
124 #define CBT_MIN_TIMEOUT_MIN_VALUE 500
125 #define CBT_MAX_TIMEOUT_MIN_VALUE INT32_MAX
126 
127 /** Initial circuit build timeout in milliseconds */
128 #define CBT_DEFAULT_TIMEOUT_INITIAL_VALUE (60*1000)
129 #define CBT_MIN_TIMEOUT_INITIAL_VALUE CBT_MIN_TIMEOUT_MIN_VALUE
130 #define CBT_MAX_TIMEOUT_INITIAL_VALUE INT32_MAX
132 
133 #if CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT < CBT_MIN_MAX_RECENT_TIMEOUT_COUNT
134 #error "RECENT_CIRCUITS is set too low."
135 #endif
136 
137 #ifdef CIRCUITSTATS_PRIVATE
139  double quantile);
141 
142 /* Network liveness functions */
144  circuit_build_times_t *cbt);
145 #endif /* defined(CIRCUITSTATS_PRIVATE) */
146 
147 #ifdef TOR_UNIT_TESTS
148 build_time_t circuit_build_times_generate_sample(circuit_build_times_t *cbt,
149  double q_lo, double q_hi);
150 double circuit_build_times_cdf(circuit_build_times_t *cbt, double x);
151 void circuit_build_times_initial_alpha(circuit_build_times_t *cbt,
152  double quantile, double time_ms);
153 void circuitbuild_running_unit_tests(void);
154 #endif /* defined(TOR_UNIT_TESTS) */
155 
156 /* Network liveness functions */
160 
161 /** Information about the state of our local network connection */
162 typedef struct {
163  /** The timestamp we last completed a TLS handshake or received a cell */
165  /** If the network is not live, how many timeouts has this caused? */
167  /** Circular array of circuits that have made it to the first hop. Slot is
168  * 1 if circuit timed out, 0 if circuit succeeded */
170  /** Number of elements allocated for the above array */
172  /** Index into circular array. */
175 
176 /** Structure for circuit build times history */
178  /** The circular array of recorded build times in milliseconds */
180  /** Current index in the circuit_build_times circular array */
182  /** Total number of build times accumulated. Max CBT_NCIRCUITS_TO_OBSERVE */
184  /** Information about the state of our local network connection */
186  /** Last time we built a circuit. Used to decide to build new test circs */
187  time_t last_circ_at;
188  /** "Minimum" value of our pareto distribution (actually mode) */
190  /** alpha exponent for pareto dist. */
191  double alpha;
192  /** Have we computed a timeout? */
194  /** The exact value for that timeout in milliseconds. Stored as a double
195  * to maintain precision from calculations to and from quantile value. */
196  double timeout_ms;
197  /** How long we wait before actually closing the circuit. */
198  double close_ms;
199  /** Total succeeded counts. Old measurements may be scaled downward if
200  * we've seen a lot of circuits. */
202  /** Total timeout counts. Old measurements may be scaled downward if
203  * we've seen a lot of circuits. */
205  /** Total closed counts. Old measurements may be scaled downward if
206  * we've seen a lot of circuits.*/
207  uint32_t num_circ_closed;
208 
209 };
210 
211 #endif /* !defined(TOR_CIRCUITSTATS_H) */
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
circuit_build_times_quantile_cutoff
double circuit_build_times_quantile_cutoff(void)
Definition: circuitstats.c:268
build_time_t
uint32_t build_time_t
Definition: circuitstats.h:25
network_liveness_t::nonlive_timeouts
int nonlive_timeouts
Definition: circuitstats.h:166
circuit_build_times_network_is_live
void circuit_build_times_network_is_live(circuit_build_times_t *cbt)
Definition: circuitstats.c:1418
circuit_build_times_t::last_circ_at
time_t last_circ_at
Definition: circuitstats.h:187
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_needs_circuits
int circuit_build_times_needs_circuits(const circuit_build_times_t *cbt)
Definition: circuitstats.c:1384
circuit_build_times_handle_completed_hop
void circuit_build_times_handle_completed_hop(origin_circuit_t *circ)
Definition: circuitstats.c:680
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_t::close_ms
double close_ms
Definition: circuitstats.h:198
circuit_build_times_close_rate
double circuit_build_times_close_rate(const circuit_build_times_t *cbt)
Definition: circuitstats.c:1694
circuit_build_times_disabled_
int circuit_build_times_disabled_(const or_options_t *options, int ignore_consensus)
Definition: circuitstats.c:125
circuit_build_times_enough_to_compute
int circuit_build_times_enough_to_compute(const circuit_build_times_t *cbt)
Definition: circuitstats.c:256
circuit_build_times_t::num_circ_succeeded
uint32_t num_circ_succeeded
Definition: circuitstats.h:201
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
network_liveness_t::network_last_live
time_t network_last_live
Definition: circuitstats.h:164
circuit_build_times_initial_timeout
int32_t circuit_build_times_initial_timeout(void)
Definition: circuitstats.c:371
network_liveness_t::num_recent_circs
int num_recent_circs
Definition: circuitstats.h:171
circuit_build_times_t
Definition: circuitstats.h:177
origin_circuit_t
Definition: origin_circuit_st.h:79
circuit_build_times_init
void circuit_build_times_init(circuit_build_times_t *cbt)
Definition: circuitstats.c:566
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
circuit_build_times_t::timeout_ms
double timeout_ms
Definition: circuitstats.h:196
network_liveness_t
Definition: circuitstats.h:162
circuit_build_times_count_timeout
void circuit_build_times_count_timeout(circuit_build_times_t *cbt, int did_onehop)
Definition: circuitstats.c:1748
circuit_build_times_disabled
int circuit_build_times_disabled(const or_options_t *options)
Definition: circuitstats.c:118
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_needs_circuits_now
int circuit_build_times_needs_circuits_now(const circuit_build_times_t *cbt)
Definition: circuitstats.c:1395
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
CBT_NCIRCUITS_TO_OBSERVE
#define CBT_NCIRCUITS_TO_OBSERVE
Definition: circuitstats.h:56
get_circuit_build_timeout_ms
double get_circuit_build_timeout_ms(void)
Definition: circuitstats.c:102
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
circuit_build_times_network_circ_success
void circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
Definition: circuitstats.c:1472
circuit_build_times_network_check_changed
STATIC int circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
Definition: circuitstats.c:1612
circuit_build_times_parse_state
int circuit_build_times_parse_state(circuit_build_times_t *cbt, or_state_t *state)
Definition: circuitstats.c:1055
circuit_build_times_free_timeouts
void circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
Definition: circuitstats.c:592
network_liveness_t::after_firsthop_idx
int after_firsthop_idx
Definition: circuitstats.h:173
get_circuit_build_times_mutable
circuit_build_times_t * get_circuit_build_times_mutable(void)
Definition: circuitstats.c:86
circuit_build_times_add_time
int circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t time)
Definition: circuitstats.c:757
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_t::build_times_idx
int build_times_idx
Definition: circuitstats.h:181
circuit_build_times_reset
void circuit_build_times_reset(circuit_build_times_t *cbt)
Definition: circuitstats.c:546
circuit_build_times_set_timeout
void circuit_build_times_set_timeout(circuit_build_times_t *cbt)
Definition: circuitstats.c:1817
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
circuit_build_times_network_check_live
int circuit_build_times_network_check_live(const circuit_build_times_t *cbt)
Definition: circuitstats.c:1592
circuit_build_times_t::total_build_times
int total_build_times
Definition: circuitstats.h:183
get_circuit_build_times
const circuit_build_times_t * get_circuit_build_times(void)
Definition: circuitstats.c:79
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
circuit_build_times_t::alpha
double alpha
Definition: circuitstats.h:191