Go to the documentation of this file.
26 #define CIRCUITSTATS_PRIVATE
58 #define CBT_BIN_TO_MS(bin) ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
71 static int unit_tests = 0;
126 int ignore_consensus)
131 int consensus_disabled =
149 int single_onion_disabled = rend_service_allow_non_anonymous_connection(
152 if (consensus_disabled || config_disabled || dirauth_disabled ||
153 state_disabled || single_onion_disabled) {
156 "CircuitBuildTime learning is disabled. "
157 "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
158 consensus_disabled, config_disabled, dirauth_disabled,
165 "CircuitBuildTime learning is not disabled. "
166 "Consensus=%d, Config=%d, AuthDir=%d, StateFile=%d",
167 consensus_disabled, config_disabled, dirauth_disabled,
185 int32_t cbt_maxtimeouts;
189 CBT_MIN_MAX_RECENT_TIMEOUT_COUNT,
190 CBT_MAX_MAX_RECENT_TIMEOUT_COUNT);
194 "circuit_build_times_max_timeouts() called, cbtmaxtimeouts is"
199 return cbt_maxtimeouts;
216 CBT_MIN_NUM_XM_MODES,
217 CBT_MAX_NUM_XM_MODES);
221 "circuit_build_times_default_num_xm_modes() called, cbtnummodes"
240 CBT_MIN_MIN_CIRCUITS_TO_OBSERVE,
241 CBT_MAX_MIN_CIRCUITS_TO_OBSERVE);
245 "circuit_build_times_min_circs_to_observe() called, cbtmincircs"
272 CBT_MIN_QUANTILE_CUTOFF,
273 CBT_MAX_QUANTILE_CUTOFF);
277 "circuit_build_times_quantile_cutoff() called, cbtquantile"
300 CBT_MIN_CLOSE_QUANTILE,
301 CBT_MAX_CLOSE_QUANTILE);
305 "circuit_build_times_close_quantile() called, cbtclosequantile"
310 log_warn(
LD_DIR,
"Consensus parameter cbtclosequantile is "
311 "too small, raising to %d", min);
314 return param / 100.0;
329 CBT_MIN_TEST_FREQUENCY,
330 CBT_MAX_TEST_FREQUENCY);
334 "circuit_build_times_test_frequency() called, cbttestfreq is %d",
353 CBT_MIN_TIMEOUT_MIN_VALUE,
354 CBT_MAX_TIMEOUT_MIN_VALUE);
358 "circuit_build_times_min_timeout() called, cbtmintimeout is %d",
376 CBT_MIN_TIMEOUT_INITIAL_VALUE,
377 CBT_MAX_TIMEOUT_INITIAL_VALUE);
381 "circuit_build_times_initial_timeout() called, "
382 "cbtinitialtimeout is %d",
387 log_warn(
LD_DIR,
"Consensus parameter cbtinitialtimeout is too small, "
388 "raising to %d", min);
407 CBT_MIN_RECENT_CIRCUITS,
408 CBT_MAX_RECENT_CIRCUITS);
412 "circuit_build_times_recent_circuit_count() called, "
413 "cbtrecentcount is %d",
442 int8_t *recent_circs;
444 log_notice(
LD_CIRC,
"The Tor Directory Consensus has changed how "
445 "many circuits we must track to detect network failures "
448 log_notice(
LD_CIRC,
"Upon receiving a consensus directory, "
449 "re-enabling circuit-based network failure detection.");
467 recent_circs = tor_calloc(num,
sizeof(int8_t));
475 if (num < cbt->liveness.num_recent_circs) {
492 "The cbtrecentcircs consensus parameter came back zero! "
493 "This disables adaptive timeouts since we can't keep track of "
494 "any recent circuits.");
528 log_warn(
LD_CIRC,
"Config CircuitBuildTimeout too low. Setting to %ds",
568 memset(cbt, 0,
sizeof(*cbt));
583 cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
615 for (i = 0; i < n; i++) {
627 "Rewound history by %d places. Current index: %d. "
642 END_CIRC_REASON_TIMEOUT);
652 int first_hop_succeeded = circ->
cpath &&
657 first_hop_succeeded);
713 "Deciding to timeout circuit %"PRIu32
"\n",
728 log_notice(
LD_CIRC,
"Strange value for circuit build time: %ldmsec. "
729 "Assuming clock jump. Purpose %d (%s)", timediff,
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);
766 log_debug(
LD_CIRC,
"Adding circuit build time %u", btime);
795 return max_build_time;
810 if (min_build_time == CBT_BUILD_TIME_MAX) {
811 log_warn(
LD_CIRC,
"No build times less than CBT_BUILD_TIME_MAX!");
813 return min_build_time;
863 int32_t bin_counts=0;
877 nth_max_bin = tor_calloc(num_modes,
sizeof(
build_time_t));
880 for (i = 0; i < nbins; i++) {
881 if (histogram[i] >= histogram[nth_max_bin[0]]) {
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]])) {
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]]);
904 if (bin_counts == 0) {
907 "No valid circuit build time data out of %d times, %u modes, "
944 state->CircuitBuildAbandonedCount = 0;
948 state->CircuitBuildAbandonedCount++;
951 for (i = 0; i < nbins; i++) {
953 if (histogram[i] == 0)
continue;
955 line->key = tor_strdup(
"CircuitBuildTimeBin");
957 CBT_BIN_TO_MS(i), histogram[i]);
958 next = &(line->next);
979 uint32_t n = num_times;
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,
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);
999 raw_times[k] = raw_times[n];
1020 int num_filtered=0, i=0;
1021 double timeout_rate = 0;
1033 log_debug(
LD_CIRC,
"Replaced timeout %d with %d", replaced,
1039 "We had %d timeouts out of %d build times, "
1040 "and filtered %d above the max of %u",
1044 return num_filtered;
1059 uint32_t loaded_cnt = 0, N = 0;
1071 loaded_times = tor_calloc(state->TotalBuildTimes,
sizeof(
build_time_t));
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");
1082 smartlist_free(args);
1085 const char *ms_str = smartlist_get(args,0);
1086 const char *count_str = smartlist_get(args,1);
1091 CBT_BUILD_TIME_MAX, &ok, NULL);
1093 log_warn(
LD_GENERAL,
"Unable to parse circuit build times: "
1094 "Unparsable bin number");
1097 smartlist_free(args);
1101 UINT32_MAX, &ok, NULL);
1103 log_warn(
LD_GENERAL,
"Unable to parse circuit build times: "
1104 "Unparsable bin count");
1107 smartlist_free(args);
1111 if (loaded_cnt+count+ (
unsigned)state->CircuitBuildAbandonedCount
1112 > (
unsigned) state->TotalBuildTimes) {
1114 "Too many build times in state file. "
1115 "Stopping short before %d",
1118 smartlist_free(args);
1122 for (k = 0; k < count; k++) {
1123 loaded_times[loaded_cnt++] = ms;
1127 smartlist_free(args);
1132 "Adding %d timeouts.", state->CircuitBuildAbandonedCount);
1133 for (i=0; i < state->CircuitBuildAbandonedCount; i++) {
1137 if (loaded_cnt != (
unsigned)state->TotalBuildTimes) {
1139 "Corrupt state file? Build times count mismatch. "
1140 "Read %d times, but file says %d", loaded_cnt,
1141 state->TotalBuildTimes);
1156 "Loaded %d/%d values from %d lines in circuit time histogram",
1162 "Corrupt state file? Shuffled build times mismatch. "
1163 "Read %d times, but file says %d", tot_values,
1164 state->TotalBuildTimes);
1178 return err ? -1 : 0;
1195 int n=0,i=0,abandoned_count=0;
1214 if (x[i] < cbt->
Xm) {
1220 if (x[i] > max_time)
1233 log_err(
LD_CIRC,
"Discrepancy in build times count: %d vs %d", n,
1238 if (max_time <= 0) {
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);
1255 a = (n-abandoned_count)/a;
1294 if (cbt->
alpha > 0) {
1296 p = pow(1.0-quantile,1.0/cbt->
alpha);
1302 if (ret > INT32_MAX) {
1309 #ifdef TOR_UNIT_TESTS
1316 ret = 1.0-pow(cbt->
Xm/x,cbt->
alpha);
1322 #ifdef TOR_UNIT_TESTS
1331 double q_lo,
double q_hi)
1340 q_hi -= 1.0/(INT32_MAX);
1346 u = q_lo + (q_hi-q_lo)*randval;
1357 #ifdef TOR_UNIT_TESTS
1364 double quantile,
double timeout_ms)
1405 #define CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP (60*3)
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,
1534 int did_onehop, time_t start_time)
1536 time_t now = time(NULL);
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];
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);
1567 "Tor has not observed any network activity for the past %d "
1568 "seconds. Disabling circuit build timeout recording.",
1575 "Got non-live timeout. Current count is: %d",
1615 int timeout_count=0;
1642 #define MAX_TIMEOUT ((int32_t) (INT32_MAX/2))
1647 log_warn(
LD_CIRC,
"Insanely large circuit build timeout value. "
1648 "(timeout = %fmsec, close = %fmsec)",
1660 cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_RESET);
1663 "Your network connection speed appears to have changed. Resetting "
1664 "timeout to %lds after %d timeouts and %d buildtimes.",
1789 "Circuit build timeout of %dms is beyond the maximum build "
1790 "time we have ever observed. Capping it to %dms.",
1795 if (max_time < INT32_MAX/2 && cbt->close_ms > 2*max_time) {
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);
1820 double timeout_rate;
1832 log_info(
LD_CIRC,
"Set buildtimeout to low value %fms. Setting to %dms",
1842 cbt_control_event_buildtimeout_set(cbt, BUILDTIMEOUT_SET_EVENT_COMPUTED);
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.",
1854 "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
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.",
1865 "Circuit timeout data: %fms, %fms, Xm: %d, a: %f, r: %f",
1870 "Set circuit build timeout to %lds (%fms, %fms, Xm: %d, a: %f,"
1871 " r: %f) based on %d circuit times",
1878 #ifdef TOR_UNIT_TESTS
1882 circuitbuild_running_unit_tests(
void)
void circuit_build_times_update_state(const circuit_build_times_t *cbt, or_state_t *state)
circuit_build_times_t * get_circuit_build_times_mutable(void)
uint32_t num_circ_timeouts
int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, int flags, int max)
void or_state_mark_dirty(or_state_t *state, time_t when)
double get_circuit_build_close_time_ms(void)
double circuit_build_times_timeout_rate(const circuit_build_times_t *cbt)
static int32_t circuit_build_times_max_timeouts(void)
unsigned int relaxed_timeout
#define CBT_SAVE_STATE_EVERY
int circuit_build_times_network_check_live(const circuit_build_times_t *cbt)
double circuit_build_times_quantile_cutoff(void)
void circuit_build_times_handle_completed_hop(origin_circuit_t *circ)
Header file for router.c.
void circuit_build_times_free_timeouts(circuit_build_times_t *cbt)
#define DEFAULT_ROUTE_LEN
#define CBT_DEFAULT_RECENT_CIRCUITS
Header file for circuituse.c.
static int circuit_build_times_set_timeout_worker(circuit_build_times_t *cbt)
void circuit_build_times_init(circuit_build_times_t *cbt)
#define tor_fragile_assert()
void reschedule_descriptor_update_check(void)
#define CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE
static void circuit_build_times_network_timeout(circuit_build_times_t *cbt, int did_onehop)
STATIC double circuit_build_times_calculate_timeout(circuit_build_times_t *cbt, double quantile)
static int32_t circuit_build_times_min_circs_to_observe(void)
static int32_t circuit_build_times_recent_circuit_count(const networkstatus_t *ns)
static int32_t circuit_build_times_default_num_xm_modes(void)
int circuit_build_times_parse_state(circuit_build_times_t *cbt, or_state_t *state)
smartlist_t * smartlist_new(void)
#define CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT
#define SMARTLIST_FOREACH(sl, type, var, cmd)
or_state_t * get_or_state(void)
int crypto_rand_int(unsigned int max)
uint32_t num_circ_succeeded
static int circuit_build_times_filter_timeouts(circuit_build_times_t *cbt)
Header file for networkstatus.c.
uint32_t global_identifier
int8_t * timeouts_after_firsthop
void circuit_build_times_set_timeout(circuit_build_times_t *cbt)
int32_t circuit_build_times_initial_timeout(void)
int circuit_build_times_enough_to_compute(const circuit_build_times_t *cbt)
Header file for circuitlist.c.
Header file for mainloop.c.
Path structures for origin circuits.
static void circuit_build_times_scale_circ_counts(circuit_build_times_t *cbt)
void circuit_build_times_count_timeout(circuit_build_times_t *cbt, int did_onehop)
int LearnCircuitBuildTimeout
static double circuit_build_times_get_initial_timeout(void)
#define CBT_BUILD_ABANDONED
void circuit_build_times_network_is_live(circuit_build_times_t *cbt)
double get_circuit_build_timeout_ms(void)
void circuit_change_purpose(circuit_t *circ, uint8_t new_purpose)
struct timeval timestamp_began
#define CBT_DEFAULT_TIMEOUT_INITIAL_VALUE
#define CBT_DEFAULT_TIMEOUT_MIN_VALUE
Header file for directory authority mode.
#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
int did_last_state_file_write_fail(void)
int circuit_timeout_want_to_count_circ(const origin_circuit_t *circ)
double circuit_build_times_close_rate(const circuit_build_times_t *cbt)
void tor_gettimeofday(struct timeval *timeval)
const circuit_build_times_t * get_circuit_build_times(void)
Header file for rendservice.c.
Header file for circuitstats.c.
int have_computed_timeout
STATIC int circuit_build_times_update_alpha(circuit_build_times_t *cbt)
static build_time_t circuit_build_times_get_xm(circuit_build_times_t *cbt)
int control_event_network_liveness_update(int liveness)
Common functions for using (pseudo-)random number generators.
Header file for control_events.c.
const or_options_t * get_options(void)
void circuit_build_times_new_consensus_params(circuit_build_times_t *cbt, const networkstatus_t *ns)
The or_state_t structure, which represents Tor's state file.
Header file for circuitbuild.c.
static int32_t circuit_build_times_test_frequency(void)
Header for feature/relay/relay_periodic.c.
int circuit_any_opened_circuits_cached(void)
static void circuit_build_times_shuffle_and_store_array(circuit_build_times_t *cbt, build_time_t *raw_times, uint32_t num_times)
static uint32_t * circuit_build_times_create_histogram(const circuit_build_times_t *cbt, build_time_t *nbins)
static double circuit_build_times_close_quantile(void)
void circuit_build_times_mark_circ_as_measurement_only(origin_circuit_t *circ)
#define CBT_NCIRCUITS_TO_OBSERVE
int circuit_build_times_needs_circuits(const circuit_build_times_t *cbt)
long tor_lround(double d)
int circuit_get_cpath_opened_len(const origin_circuit_t *circ)
static void circuit_build_times_network_close(circuit_build_times_t *cbt, int did_onehop, time_t start_time)
long tv_mdiff(const struct timeval *start, const struct timeval *end)
static circuit_build_times_t circ_times
STATIC int circuit_build_times_network_check_changed(circuit_build_times_t *cbt)
int tor_asprintf(char **strp, const char *fmt,...)
#define CBT_DEFAULT_CLOSE_QUANTILE
double crypto_rand_double(void)
int circuit_build_times_disabled_(const or_options_t *options, int ignore_consensus)
int circuit_build_times_count_close(circuit_build_times_t *cbt, int did_onehop, time_t start_time)
int circuit_build_times_add_time(circuit_build_times_t *cbt, build_time_t btime)
void format_local_iso_time(char *buf, time_t t)
unsigned long tor_parse_ulong(const char *s, int base, unsigned long min, unsigned long max, int *ok, char **next)
Header file for config.c.
void circuit_build_times_network_circ_success(circuit_build_times_t *cbt)
#define CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP
#define CBT_DEFAULT_TEST_FREQUENCY
void circuit_build_times_reset(circuit_build_times_t *cbt)
static int32_t circuit_build_times_min_timeout(void)
network_liveness_t liveness
int circuit_build_times_needs_circuits_now(const circuit_build_times_t *cbt)
#define CBT_DEFAULT_QUANTILE_CUTOFF
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)
build_time_t circuit_build_times[CBT_NCIRCUITS_TO_OBSERVE]
Origin circuit structure.
#define CBT_DEFAULT_NUM_XM_MODES
struct config_line_t * BuildtimeHistogram
Header file for rendclient.c.
int circuit_build_times_disabled(const or_options_t *options)
int authdir_mode(const or_options_t *options)
double tor_mathlog(double d)
const char * circuit_purpose_to_string(uint8_t purpose)
static build_time_t circuit_build_times_max(const circuit_build_times_t *cbt)
Master header file for Tor-specific functionality.
int circuit_event_status(origin_circuit_t *circ, circuit_status_event_t tp, int reason_code)