circuitstats.c File Reference

Maintains and analyzes statistics about circuit built times, so we can tell how long we may need to wait for a fast circuit to be constructed. More...

#include "or.h"
#include "circuitbuild.h"
#include "circuitstats.h"
#include "config.h"
#include "confparse.h"
#include "control.h"
#include "crypto_rand.h"
#include "main.h"
#include "networkstatus.h"
#include "rendclient.h"
#include "rendservice.h"
#include "router.h"
#include "statefile.h"
#include "circuitlist.h"
#include "circuituse.h"
#include <math.h>

Include dependency graph for circuitstats.c:

Macros
#define	CIRCUITSTATS_PRIVATE
#define	CBT_BIN_TO_MS(bin)   ((bin)*CBT_BIN_WIDTH + (CBT_BIN_WIDTH/2))
#define	unit_tests   0
#define	CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP   (60*3)
#define	MAX_TIMEOUT   ((int32_t) (INT32_MAX/2))

Functions
const circuit_build_times_t *	get_circuit_build_times (void)
circuit_build_times_t *	get_circuit_build_times_mutable (void)
double	get_circuit_build_close_time_ms (void)
double	get_circuit_build_timeout_ms (void)
int	circuit_build_times_disabled (const or_options_t *options)
int	circuit_build_times_disabled_ (const or_options_t *options, int ignore_consensus)
int	circuit_build_times_enough_to_compute (const circuit_build_times_t *cbt)
double	circuit_build_times_quantile_cutoff (void)
int32_t	circuit_build_times_initial_timeout (void)
void	circuit_build_times_new_consensus_params (circuit_build_times_t *cbt, networkstatus_t *ns)
STATIC void	circuit_build_times_reset (circuit_build_times_t *cbt)
void	circuit_build_times_init (circuit_build_times_t *cbt)
void	circuit_build_times_free_timeouts (circuit_build_times_t *cbt)
void	circuit_build_times_mark_circ_as_measurement_only (origin_circuit_t *circ)
void	circuit_build_times_handle_completed_hop (origin_circuit_t *circ)
int	circuit_build_times_add_time (circuit_build_times_t *cbt, build_time_t btime)
void	circuit_build_times_update_state (const circuit_build_times_t *cbt, or_state_t *state)
int	circuit_build_times_parse_state (circuit_build_times_t *cbt, or_state_t *state)
STATIC int	circuit_build_times_update_alpha (circuit_build_times_t *cbt)
STATIC double	circuit_build_times_calculate_timeout (circuit_build_times_t *cbt, double quantile)
int	circuit_build_times_needs_circuits (const circuit_build_times_t *cbt)
int	circuit_build_times_needs_circuits_now (const circuit_build_times_t *cbt)
void	circuit_build_times_network_is_live (circuit_build_times_t *cbt)
void	circuit_build_times_network_circ_success (circuit_build_times_t *cbt)
int	circuit_build_times_network_check_live (const circuit_build_times_t *cbt)
STATIC int	circuit_build_times_network_check_changed (circuit_build_times_t *cbt)
double	circuit_build_times_timeout_rate (const circuit_build_times_t *cbt)
double	circuit_build_times_close_rate (const circuit_build_times_t *cbt)
int	circuit_build_times_count_close (circuit_build_times_t *cbt, int did_onehop, time_t start_time)
void	circuit_build_times_count_timeout (circuit_build_times_t *cbt, int did_onehop)
void	circuit_build_times_set_timeout (circuit_build_times_t *cbt)
void	circuit_build_times_update_last_circ (circuit_build_times_t *cbt)

Detailed Description

Maintains and analyzes statistics about circuit built times, so we can tell how long we may need to wait for a fast circuit to be constructed.

By keeping these statistics, a client learns when it should time out a slow circuit for being too slow, and when it should keep a circuit open in order to wait for it to complete.

The information here is kept in a circuit_built_times_t structure, which is currently a singleton, but doesn't need to be. It's updated by calls to circuit_build_times_count_timeout() from circuituse.c, circuit_build_times_count_close() from circuituse.c, and circuit_build_times_add_time() from circuitbuild.c, and inspected by other calls into this module, mostly from circuitlist.c. Observations are persisted to disk via the or_state_t-related calls.

Macro Definition Documentation

CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP

#define CIRCUIT_TIMEOUT_BEFORE_RECHECK_IP   (60*3)

How long should we be unreachable before we think we need to check if our published IP address has changed.

Function Documentation

circuit_build_times_add_time()

int circuit_build_times_add_time	(	circuit_build_times_t *	cbt,
		build_time_t	btime
	)

Add a new build time value time to the set of build times. Time units are milliseconds.

circuit_build_times cbt is a circular array, so loop around when array is full.

circuit_build_times_calculate_timeout()

STATIC double circuit_build_times_calculate_timeout	(	circuit_build_times_t *	cbt,
		double	quantile
	)

This is the Pareto Quantile Function. It calculates the point x in the distribution such that F(x) = quantile (ie quantile*100% of the mass of the density function is below x on the curve).

We use it to calculate the timeout and also to generate synthetic values of time for circuits that timeout before completion.

See http://en.wikipedia.org/wiki/Quantile_function, http://en.wikipedia.org/wiki/Inverse_transform_sampling and http://en.wikipedia.org/wiki/Pareto_distribution#Generating_a_ random_sample_from_Pareto_distribution That's right. I'll cite wikipedia all day long.

Return value is in milliseconds, clamped to INT32_MAX.

Here is the call graph for this function:

circuit_build_times_close_rate()

double circuit_build_times_close_rate

(

const circuit_build_times_t *

cbt

)

Count the number of closed circuits in a set of cbt data.

circuit_build_times_count_close()

int circuit_build_times_count_close	(	circuit_build_times_t *	cbt,
		int	did_onehop,
		time_t	start_time
	)

Store a timeout as a synthetic value.

Returns true if the store was successful and we should possibly update our timeout estimate.

Here is the call graph for this function:

circuit_build_times_count_timeout()

void circuit_build_times_count_timeout	(	circuit_build_times_t *	cbt,
		int	did_onehop
	)

Update timeout counts to determine if we need to expire our build time history due to excessive timeouts.

We do not record any actual time values at this stage; we are only interested in recording the fact that a timeout happened. We record the time values via circuit_build_times_count_close() and circuit_build_times_add_time().

Here is the call graph for this function:

circuit_build_times_disabled()

int circuit_build_times_disabled

(

const or_options_t *

options

)

This function decides if CBT learning should be disabled. It returns true if one or more of the following conditions are met:

1. If the cbtdisabled consensus parameter is set.
2. If the torrc option LearnCircuitBuildTimeout is false.
3. If we are a directory authority
4. If we fail to write circuit build time history to our state file.
5. If we are compiled or configured in Tor2web mode
6. If we are configured in Single Onion mode

Here is the call graph for this function:

Here is the caller graph for this function:

circuit_build_times_disabled_()

int circuit_build_times_disabled_	(	const or_options_t *	options,
		int	ignore_consensus
	)

As circuit_build_times_disabled, but take options as an argument.

Here is the caller graph for this function:

circuit_build_times_enough_to_compute()

int circuit_build_times_enough_to_compute

(

const circuit_build_times_t *

cbt

)

Return true iff cbt has recorded enough build times that we want to start acting on the timeout it implies.

Here is the caller graph for this function:

circuit_build_times_free_timeouts()

void circuit_build_times_free_timeouts

(

circuit_build_times_t *

cbt

)

Free the saved timeouts, if the cbtdisabled consensus parameter got turned on or something.

circuit_build_times_handle_completed_hop()

void circuit_build_times_handle_completed_hop

(

origin_circuit_t *

circ

)

Perform the build time work that needs to be done when a circuit completes a hop.

This function decides if we should record a circuit's build time in our histogram data and other statistics, and if so, records it. It also will mark circuits that have already timed out as measurement-only circuits, so they can continue to build but not get used.

For this, we want to consider circuits that will eventually make it to the third hop. For circuits longer than 3 hops, we want to record their build time when they reach the third hop, but let them continue (and not count them later). For circuits that are exactly 3 hops, this will count them when they are completed. We do this so that CBT is always gathering statistics on circuits of the same length, regardless of their type.

Here is the call graph for this function:

circuit_build_times_init()

void circuit_build_times_init

(

circuit_build_times_t *

cbt

)

Initialize the buildtimes structure for first use.

Sets the initial timeout values based on either the config setting, the consensus param, or the default (CBT_DEFAULT_TIMEOUT_INITIAL_VALUE).

Here is the call graph for this function:

Here is the caller graph for this function:

circuit_build_times_initial_timeout()

int32_t circuit_build_times_initial_timeout

(

void

)

Retrieve and bounds-check the cbtinitialtimeout consensus parameter.

Effect: This is the timeout value to use before computing a timeout, in milliseconds.

circuit_build_times_mark_circ_as_measurement_only()

void circuit_build_times_mark_circ_as_measurement_only

(

origin_circuit_t *

circ

)

Mark this circuit as timed out, but change its purpose so that it continues to build, allowing us to measure its full build time.

Here is the call graph for this function:

circuit_build_times_needs_circuits()

int circuit_build_times_needs_circuits

(

const circuit_build_times_t *

cbt

)

Returns true if we need circuits to be built

Here is the call graph for this function:

Here is the caller graph for this function:

circuit_build_times_needs_circuits_now()

int circuit_build_times_needs_circuits_now

(

const circuit_build_times_t *

cbt

)

Returns true if we should build a timeout test circuit right now.

Here is the call graph for this function:

circuit_build_times_network_check_changed()

STATIC int circuit_build_times_network_check_changed

(

circuit_build_times_t *

cbt

)

Returns true if we have seen more than MAX_RECENT_TIMEOUT_COUNT of the past RECENT_CIRCUITS time out after the first hop. Used to detect if the network connection has changed significantly, and if so, resets our circuit build timeout to the default.

Also resets the entire timeout history in this case and causes us to restart the process of building test circuits and estimating a new timeout.

circuit_build_times_network_check_live()

int circuit_build_times_network_check_live

(

const circuit_build_times_t *

cbt

)

When the network is not live, we do not record circuit build times.

The network is considered not live if there has been at least one circuit build that began and ended (had its close_ms measurement period expire) since we last received a cell.

Also has the side effect of rewinding the circuit time history in the case of recent liveness changes.

circuit_build_times_network_circ_success()

void circuit_build_times_network_circ_success

(

circuit_build_times_t *

cbt

)

Called to indicate that we "completed" a circuit. Because this circuit succeeded, it doesn't count as a timeout-after-the-first-hop.

(For the purposes of the cbt code, we consider a circuit "completed" if it has 3 hops, regardless of its final hop count. We do this because we're trying to answer the question, "how long should a circuit take to reach the 3-hop count".)

This is used by circuit_build_times_network_check_changed() to determine if we had too many recent timeouts and need to reset our learned timeout to something higher.

circuit_build_times_network_is_live()

void circuit_build_times_network_is_live

(

circuit_build_times_t *

cbt

)

Called to indicate that the network showed some signs of liveness, i.e. we received a cell.

This is used by circuit_build_times_network_check_live() to decide if we should record the circuit build timeout or not.

This function is called every time we receive a cell. Avoid syscalls, events, and other high-intensity work.

Here is the call graph for this function:

Here is the caller graph for this function:

circuit_build_times_new_consensus_params()

void circuit_build_times_new_consensus_params	(	circuit_build_times_t *	cbt,
		networkstatus_t *	ns
	)

This function is called when we get a consensus update.

It checks to see if we have changed any consensus parameters that require reallocation or discard of previous stats.

Here is the call graph for this function:

circuit_build_times_parse_state()

int circuit_build_times_parse_state	(	circuit_build_times_t *	cbt,
		or_state_t *	state
	)

Load histogram from state, shuffling the resulting array after we do so. Use this result to estimate parameters and calculate the timeout.

Return -1 on error.

Here is the call graph for this function:

circuit_build_times_quantile_cutoff()

double circuit_build_times_quantile_cutoff

(

void

)

Retrieve and bounds-check the cbtquantile consensus parameter.

Effect: This is the position on the quantile curve to use to set the timeout value. It is a percent (10-99).

circuit_build_times_reset()

STATIC void circuit_build_times_reset

(

circuit_build_times_t *

cbt

)

Reset the build time state.

Leave estimated parameters, timeout and network liveness intact for future use.

circuit_build_times_set_timeout()

void circuit_build_times_set_timeout

(

circuit_build_times_t *

cbt

)

Exposed function to compute a new timeout. Dispatches events and also filters out extremely high timeout values.

Here is the call graph for this function:

circuit_build_times_timeout_rate()

double circuit_build_times_timeout_rate

(

const circuit_build_times_t *

cbt

)

Count the number of timeouts in a set of cbt data.

circuit_build_times_update_alpha()

STATIC int circuit_build_times_update_alpha

(

circuit_build_times_t *

cbt

)

Estimates the Xm and Alpha parameters using http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation

The notable difference is that we use mode instead of min to estimate Xm. This is because our distribution is frechet-like. We claim this is an acceptable approximation because we are only concerned with the accuracy of the CDF of the tail.

circuit_build_times_update_state()

void circuit_build_times_update_state	(	const circuit_build_times_t *	cbt,
		or_state_t *	state
	)

Output a histogram of current circuit build times to the or_state_t state structure.

get_circuit_build_close_time_ms()

double get_circuit_build_close_time_ms

(

void

)

Return the time to wait before actually closing an under-construction, in milliseconds.

get_circuit_build_timeout_ms()

double get_circuit_build_timeout_ms

(

void

)

Return the time to wait before giving up on an under-construction circuit, in milliseconds.

Here is the caller graph for this function:

get_circuit_build_times()

const circuit_build_times_t* get_circuit_build_times

(

void

)

Return a pointer to the data structure describing our current circuit build time history and computations.

get_circuit_build_times_mutable()

circuit_build_times_t* get_circuit_build_times_mutable

(

void

)

As get_circuit_build_times, but return a mutable pointer.

Here is the caller graph for this function: