Public APIs for congestion control. More...

#include "core/crypto/onion_crypto.h"
#include "core/or/crypt_path_st.h"
#include "core/or/circuit_st.h"

Macros
#define	TLS_RECORD_MAX_CELLS ((16 * 1024) / CELL_MAX_NETWORK_SIZE)

#define	SBWS_ROUTE_LEN 2

#define	congestion_control_free(cc) FREE_AND_NULL(congestion_control_t, congestion_control_free_, cc)

Enumerations
enum	cc_path_t { CC_PATH_EXIT = 0 , CC_PATH_ONION = 1 , CC_PATH_ONION_SOS = 2 , CC_PATH_ONION_VG = 3 , CC_PATH_SBWS = 4 }

Functions
void	congestion_control_free_ (congestion_control_t *cc)

congestion_control_t *	congestion_control_new (const struct circuit_params_t *params, cc_path_t path)

int	congestion_control_dispatch_cc_alg (congestion_control_t cc, circuit_t circ)

void	congestion_control_note_cell_sent (congestion_control_t cc, const circuit_t circ, const crypt_path_t *cpath)

bool	congestion_control_update_circuit_estimates (congestion_control_t , const circuit_t )

int	congestion_control_get_package_window (const circuit_t , const crypt_path_t )

int	sendme_get_inc_count (const circuit_t , const crypt_path_t )

bool	circuit_sent_cell_for_sendme (const circuit_t , const crypt_path_t )

bool	is_monotime_clock_reliable (void)

void	congestion_control_new_consensus_params (const networkstatus_t *ns)

bool	congestion_control_enabled (void)

int	congestion_control_build_ext_request (uint8_t *msg_out, size_t msg_len_out)

int	congestion_control_parse_ext_request (const uint8_t *msg, const size_t msg_len)

int	congestion_control_build_ext_response (const circuit_params_t our_params, const circuit_params_t circ_params, uint8_t *msg_out, size_t msg_len_out)

int	congestion_control_parse_ext_response (const uint8_t msg, const size_t msg_len, circuit_params_t params_out)

bool	congestion_control_validate_sendme_increment (uint8_t sendme_inc)

char *	congestion_control_get_control_port_fields (const origin_circuit_t *)

uint64_t	congestion_control_get_num_rtt_reset (void)

uint64_t	congestion_control_get_num_clock_stalls (void)

static uint32_t	or_conn_highwatermark (void)

static uint32_t	or_conn_lowwatermark (void)

static int32_t	cell_queue_highwatermark (void)

static int32_t	cell_queue_lowwatermark (void)

static uint8_t	congestion_control_sendme_inc (void)

static uint64_t	n_count_ewma (uint64_t curr, uint64_t prev, uint64_t N)

static uint64_t	percent_max_mix (uint64_t a, uint64_t b, uint8_t pct_max)

Variables
uint64_t	cc_stats_circs_created

uint32_t	or_conn_highwater

uint32_t	or_conn_lowwater

int32_t	cell_queue_high

int32_t	cell_queue_low

uint8_t	cc_sendme_inc

Detailed Description

Public APIs for congestion control.

Definition in file congestion_control_common.h.

Macro Definition Documentation

◆ congestion_control_free

#define congestion_control_free ( cc ) FREE_AND_NULL(congestion_control_t, congestion_control_free_, cc)

Wrapper for the free function, set the CC pointer to NULL after free

Definition at line 38 of file congestion_control_common.h.

◆ SBWS_ROUTE_LEN

#define SBWS_ROUTE_LEN 2

The length of a path for sbws measurement

Definition at line 35 of file congestion_control_common.h.

◆ TLS_RECORD_MAX_CELLS

#define TLS_RECORD_MAX_CELLS ((16 * 1024) / CELL_MAX_NETWORK_SIZE)

Definition at line 18 of file congestion_control_common.h.

Enumeration Type Documentation

◆ cc_path_t

enum cc_path_t

Specifies the path type to help choose congestion control parameters. Since these paths are different lengths, they will need different queue parameters.

Definition at line 26 of file congestion_control_common.h.

Function Documentation

◆ cell_queue_highwatermark()

static int32_t cell_queue_highwatermark ( void )

inlinestatic

Stop reading on edge connections when we have this many cells waiting on the appropriate queue.

Definition at line 113 of file congestion_control_common.h.

◆ cell_queue_lowwatermark()

static int32_t cell_queue_lowwatermark ( void )

inlinestatic

Start reading from edge connections again when we get down to this many cells.

Definition at line 121 of file congestion_control_common.h.

◆ circuit_sent_cell_for_sendme()

bool circuit_sent_cell_for_sendme	(	const circuit_t *	circ,
		const crypt_path_t *	layer_hint
	)

Return true iff the next cell we send will result in the other endpoint sending a SENDME.

We are able to know that because the package or inflight window value minus one cell (the possible SENDME cell) should be a multiple of the cells-per-sendme increment value (set via consensus parameter, negotiated for the circuit, and passed in as sendme_inc).

This function is used when recording a cell digest and this is done quite low in the stack when decrypting or encrypting a cell. The window is only updated once the cell is actually put in the outbuf.

Definition at line 570 of file congestion_control_common.c.

Referenced by congestion_control_note_cell_sent().

◆ congestion_control_build_ext_request()

int congestion_control_build_ext_request	(	uint8_t **	msg_out,
		size_t *	msg_len_out
	)

Build an extension field request to negotiate congestion control.

If congestion control is enabled, field TRUNNEL_EXT_TYPE_CC_FIELD_REQUEST is created in msg_out. It is a single 0-length field that signifies that we want to use congestion control. The length of msg_out is provided via msg_len_out.

If congestion control is not enabled, a payload with 0 extensions is created and returned.

If there is a failure building the request, -1 is returned, else 0.

*msg_out must be freed if the return value is 0.

Definition at line 1013 of file congestion_control_common.c.

Referenced by client_circ_negotiation_message().

◆ congestion_control_build_ext_response()

int congestion_control_build_ext_response	(	const circuit_params_t *	our_params,
		const circuit_params_t *	circ_params,
		uint8_t **	msg_out,
		size_t *	msg_len_out
	)

Given our observed parameters for circuits and congestion control, as well as the parameters for the resulting circuit, build a response payload using extension fields into *msg_out, with length specified in *msg_out_len.

If congestion control will be enabled, the extension field for TRUNNEL_EXT_TYPE_CC_FIELD_RESPONSE will contain the sendme_inc value.

If congestion control won't be enabled, an extension payload with 0 fields will be created.

Return 0 if an extension payload was created in *msg_out, and -1 on error.

*msg_out must be freed if the return value is 0.

WARNING: Called from CPU worker! Must not access any global state.

Definition at line 1133 of file congestion_control_common.c.

Referenced by negotiate_v3_ntor_server_circ_params().

◆ congestion_control_dispatch_cc_alg()

int congestion_control_dispatch_cc_alg	(	congestion_control_t *	cc,
		circuit_t *	circ
	)

Dispatch the sendme to the appropriate congestion control algorithm.

Definition at line 974 of file congestion_control_common.c.

◆ congestion_control_enabled()

bool congestion_control_enabled ( void )

Returns true if congestion control is enabled in the most recent consensus, or if __AlwaysCongestionControl is set to true.

Note that this function (and many many other functions) should not be called from the CPU worker threads when handling congestion control negotiation. Relevant values are marshaled into the circuit_params_t struct, in order to be used in worker threads without touching global state. Use those values in CPU worker threads, instead of calling this function.

The danger is still present, in your time, as it was in ours.

Definition at line 346 of file congestion_control_common.c.

Referenced by congestion_control_build_ext_request(), negotiate_v3_ntor_client_circ_params(), and setup_rendezvous_circ_congestion_control().

◆ congestion_control_free_()

void congestion_control_free_ ( congestion_control_t * cc )

Free a congestion control object and its associated state.

Definition at line 427 of file congestion_control_common.c.

◆ congestion_control_get_control_port_fields()

char * congestion_control_get_control_port_fields ( const origin_circuit_t * circ )

Returns a formatted string of fields containing congestion control information, for the CIRC_BW control port event.

An origin circuit can have a ccontrol object directly on it, if it is an onion service, or onion client. Exit-bound clients will have the ccontrol on the cpath associated with their exit (the last one in the cpath list).

WARNING: This function does not support leaky-pipe topology. It is to be used for control port information only.

Definition at line 1313 of file congestion_control_common.c.

◆ congestion_control_get_num_clock_stalls()

uint64_t congestion_control_get_num_clock_stalls ( void )

Return the number of clock stalls that have been done.

Definition at line 143 of file congestion_control_common.c.

Referenced by fill_cc_counters_values().

◆ congestion_control_get_num_rtt_reset()

uint64_t congestion_control_get_num_rtt_reset ( void )

Return the number of RTT reset that have been done.

Definition at line 136 of file congestion_control_common.c.

Referenced by fill_cc_counters_values().

◆ congestion_control_get_package_window()

int congestion_control_get_package_window	(	const circuit_t *	circ,
		const crypt_path_t *	cpath
	)

Get a package window from either old sendme logic, or congestion control.

A package window is how many cells you can still send.

Definition at line 504 of file congestion_control_common.c.

◆ congestion_control_new_consensus_params()

void congestion_control_new_consensus_params ( const networkstatus_t * ns )

Update global congestion control related consensus parameter values, every consensus update.

Definition at line 153 of file congestion_control_common.c.

◆ congestion_control_note_cell_sent()

void congestion_control_note_cell_sent	(	congestion_control_t *	cc,
		const circuit_t *	circ,
		const crypt_path_t *	cpath
	)

Call-in to tell congestion control code that this circuit sent a cell.

This updates the 'inflight' counter, and if this is a cell that will cause the other end to send a SENDME, record the current time in a list of pending timestamps, so that we can later compute the circuit RTT when the SENDME comes back.

Definition at line 630 of file congestion_control_common.c.

◆ congestion_control_parse_ext_request()

int congestion_control_parse_ext_request	(	const uint8_t *	msg,
		const size_t	msg_len
	)

Parse a congestion control ntorv3 request payload for extensions.

On parsing failure, -1 is returned.

If congestion control request is present, return 1. If it is not present, return 0.

WARNING: Called from CPU worker! Must not access any global state.

Definition at line 1072 of file congestion_control_common.c.

Referenced by negotiate_v3_ntor_server_circ_params().

◆ congestion_control_parse_ext_response()

int congestion_control_parse_ext_response	(	const uint8_t *	msg,
		const size_t	msg_len,
		circuit_params_t *	params_out
	)

Return 1 if CC is enabled which also will set the SENDME increment into our params_out. Return 0 if CC is disabled. Else, return -1 on error.

Definition at line 1231 of file congestion_control_common.c.

Referenced by negotiate_v3_ntor_client_circ_params().

◆ congestion_control_sendme_inc()

static uint8_t congestion_control_sendme_inc ( void )

inlinestatic

Returns the sendme inc rate cached from the most recent consensus

Definition at line 128 of file congestion_control_common.h.

Referenced by build_service_desc_encrypted(), congestion_control_validate_sendme_increment(), and hs_service_new_consensus_params().

◆ congestion_control_update_circuit_estimates()

bool congestion_control_update_circuit_estimates	(	congestion_control_t *	cc,
		const circuit_t *	circ
	)

Upon receipt of a SENDME, pop the oldest timestamp off the timestamp list, and use this to update RTT.

Returns true if circuit estimates were successfully updated, false otherwise.

Definition at line 661 of file congestion_control_common.c.

Referenced by congestion_control_vegas_process_sendme().

◆ congestion_control_validate_sendme_increment()

bool congestion_control_validate_sendme_increment ( uint8_t sendme_inc )

Return true iff the given sendme increment is within the acceptable margins.

Definition at line 1210 of file congestion_control_common.c.

Referenced by congestion_control_parse_ext_response().

◆ is_monotime_clock_reliable()

bool is_monotime_clock_reliable ( void )

Is the monotime clock stalled according to any circuits?

Definition at line 766 of file congestion_control_common.c.

Referenced by stream_drain_rate_changed().

◆ n_count_ewma()

static uint64_t n_count_ewma	(	uint64_t	curr,
		uint64_t	prev,
		uint64_t	N
	)

inlinestatic

Compute an N-count EWMA, aka N-EWMA. N-EWMA is defined as: EWMA = alpha*value + (1-alpha)*EWMA_prev with alpha = 2/(N+1).

This works out to: EWMA = value*2/(N+1) + EMA_prev*(N-1)/(N+1) = (value*2 + EWMA_prev*(N-1))/(N+1)

Definition at line 143 of file congestion_control_common.h.

◆ or_conn_highwatermark()

static uint32_t or_conn_highwatermark ( void )

inlinestatic

Stop writing on an orconn when its outbuf is this large

Definition at line 98 of file congestion_control_common.h.

◆ or_conn_lowwatermark()

static uint32_t or_conn_lowwatermark ( void )

inlinestatic

Resume writing on an orconn when its outbuf is less than this

Definition at line 105 of file congestion_control_common.h.

◆ percent_max_mix()

static uint64_t percent_max_mix	(	uint64_t	a,
		uint64_t	b,
		uint8_t	pct_max
	)

inlinestatic

Helper function that gives us a percentile weighted-average between two values. The pct_max argument specifies the percentage weight of the maximum of a and b, when computing this weighted-average.

This also allows this function to be used as either MIN() or a MAX() by this parameterization. It is MIN() when pct_max==0; it is MAX() when pct_max==100; it is avg() when pct_max==50; it is a weighted-average for values in between.

Definition at line 162 of file congestion_control_common.h.

◆ sendme_get_inc_count()

int sendme_get_inc_count	(	const circuit_t *	circ,
		const crypt_path_t *	layer_hint
	)

Returns the number of cells that are acked by every sendme.

Definition at line 539 of file congestion_control_common.c.

Referenced by sendme_circuit_consider_sending().

Variable Documentation

◆ cc_sendme_inc

uint8_t cc_sendme_inc

extern

Definition at line 102 of file congestion_control_common.c.

◆ cc_stats_circs_created

uint64_t cc_stats_circs_created

extern

Metric to count the number of congestion control circuits

Definition at line 132 of file congestion_control_common.c.

◆ cell_queue_high

int32_t cell_queue_high

extern

Definition at line 98 of file congestion_control_common.c.

◆ cell_queue_low

int32_t cell_queue_low

extern

Definition at line 99 of file congestion_control_common.c.

◆ or_conn_highwater

uint32_t or_conn_highwater

extern

Definition at line 100 of file congestion_control_common.c.

◆ or_conn_lowwater

uint32_t or_conn_lowwater

extern

Definition at line 101 of file congestion_control_common.c.

Macros

Enumerations

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ congestion_control_free

◆ SBWS_ROUTE_LEN

◆ TLS_RECORD_MAX_CELLS

Enumeration Type Documentation

◆ cc_path_t

Function Documentation

◆ cell_queue_highwatermark()

◆ cell_queue_lowwatermark()

◆ circuit_sent_cell_for_sendme()

◆ congestion_control_build_ext_request()

◆ congestion_control_build_ext_response()

◆ congestion_control_dispatch_cc_alg()

◆ congestion_control_enabled()

◆ congestion_control_free_()

◆ congestion_control_get_control_port_fields()

◆ congestion_control_get_num_clock_stalls()

◆ congestion_control_get_num_rtt_reset()

◆ congestion_control_get_package_window()

◆ congestion_control_new_consensus_params()

◆ congestion_control_note_cell_sent()

◆ congestion_control_parse_ext_request()

◆ congestion_control_parse_ext_response()

◆ congestion_control_sendme_inc()

◆ congestion_control_update_circuit_estimates()

◆ congestion_control_validate_sendme_increment()

◆ is_monotime_clock_reliable()

◆ n_count_ewma()

◆ or_conn_highwatermark()

◆ or_conn_lowwatermark()

◆ percent_max_mix()

◆ sendme_get_inc_count()

Variable Documentation

◆ cc_sendme_inc

◆ cc_stats_circs_created

◆ cell_queue_high

◆ cell_queue_low

◆ or_conn_highwater

◆ or_conn_lowwater