Tor 0.4.9.1-alpha-dev
|
Common code used by all congestion control algorithms. More...
#include "core/or/or.h"
#include "core/crypto/onion_crypto.h"
#include "core/or/circuitlist.h"
#include "core/or/crypt_path.h"
#include "core/or/or_circuit_st.h"
#include "core/or/origin_circuit_st.h"
#include "core/or/channel.h"
#include "core/mainloop/connection.h"
#include "core/or/sendme.h"
#include "core/or/congestion_control_st.h"
#include "core/or/congestion_control_common.h"
#include "core/or/congestion_control_vegas.h"
#include "core/or/conflux.h"
#include "core/or/conflux_util.h"
#include "core/or/trace_probes_cc.h"
#include "lib/time/compat_time.h"
#include "feature/nodelist/networkstatus.h"
#include "app/config/config.h"
#include "trunnel/congestion_control.h"
#include "trunnel/extension.h"
Go to the source code of this file.
Macros | |
#define | TOR_CONGESTION_CONTROL_COMMON_PRIVATE |
#define | TOR_CONGESTION_CONTROL_PRIVATE |
#define | SENDME_INC_DFLT (TLS_RECORD_MAX_CELLS) |
#define | CIRCWINDOW_INIT (4*SENDME_INC_DFLT) |
#define | CC_ALG_DFLT (CC_ALG_VEGAS) |
#define | CC_ALG_DFLT_ALWAYS (CC_ALG_VEGAS) |
#define | CWND_INC_DFLT (1) |
#define | CWND_INC_PCT_SS_DFLT (100) |
#define | CWND_INC_RATE_DFLT (SENDME_INC_DFLT) |
#define | CWND_MIN_DFLT (CIRCWINDOW_INIT) |
#define | CWND_MAX_DFLT (INT32_MAX) |
#define | BWE_SENDME_MIN_DFLT (5) |
#define | N_EWMA_CWND_PCT_DFLT (50) |
#define | N_EWMA_MAX_DFLT (10) |
#define | N_EWMA_SS_DFLT (2) |
#define | RTT_RESET_PCT_DFLT (100) |
#define | WESTWOOD_BDP_ALG BDP_ALG_PIECEWISE |
#define | VEGAS_BDP_MIX_ALG BDP_ALG_PIECEWISE |
#define | NOLA_BDP_ALG BDP_ALG_PIECEWISE |
#define | OR_CONN_HIGHWATER_DFLT (32*1024) |
#define | OR_CONN_LOWWATER_DFLT (16*1024) |
#define | CELL_QUEUE_LOW_DFLT (10) |
#define | CELL_QUEUE_HIGH_DFLT (256) |
#define | CELL_QUEUE_HIGH_MIN (1) |
#define | CELL_QUEUE_HIGH_MAX (1000) |
#define | CELL_QUEUE_LOW_MIN (1) |
#define | CELL_QUEUE_LOW_MAX (1000) |
#define | OR_CONN_HIGHWATER_MIN (CELL_PAYLOAD_SIZE) |
#define | OR_CONN_HIGHWATER_MAX (INT32_MAX) |
#define | OR_CONN_LOWWATER_MIN (CELL_PAYLOAD_SIZE) |
#define | OR_CONN_LOWWATER_MAX (INT32_MAX) |
#define | CWND_MAX_MIN 500 |
#define | CWND_MAX_MAX (INT32_MAX) |
#define | RTT_RESET_PCT_MIN (0) |
#define | RTT_RESET_PCT_MAX (100) |
#define | SENDME_INC_MIN 1 |
#define | SENDME_INC_MAX (254) |
#define | CC_ALG_MIN 0 |
#define | CC_ALG_MAX (NUM_CC_ALGS-1) |
#define | BWE_SENDME_MIN_MIN 2 |
#define | BWE_SENDME_MIN_MAX (20) |
#define | N_EWMA_CWND_PCT_MIN 1 |
#define | N_EWMA_CWND_PCT_MAX (255) |
#define | N_EWMA_MAX_MIN 2 |
#define | N_EWMA_MAX_MAX (INT32_MAX) |
#define | N_EWMA_SS_MIN 2 |
#define | N_EWMA_SS_MAX (INT32_MAX) |
#define | CWND_INIT_MIN SENDME_INC_DFLT |
#define | CWND_INIT_MAX (10000) |
#define | CWND_INC_PCT_SS_MIN 1 |
#define | CWND_INC_PCT_SS_MAX (500) |
#define | CWND_INC_MIN 1 |
#define | CWND_INC_MAX (1000) |
#define | CWND_INC_RATE_MIN 1 |
#define | CWND_INC_RATE_MAX (250) |
#define | CWND_MIN_MIN SENDME_INC_DFLT |
#define | CWND_MIN_MAX (1000) |
#define | DELTA_DISCREPENCY_RATIO_MAX 5000 |
#define | MAX_SENDME_INC_NEGOTIATE_FACTOR 2 |
Variables | |
static uint64_t | num_rtt_reset |
static uint64_t | num_clock_stalls |
static uint32_t | cwnd_max = CWND_MAX_DFLT |
int32_t | cell_queue_high = CELL_QUEUE_HIGH_DFLT |
int32_t | cell_queue_low = CELL_QUEUE_LOW_DFLT |
uint32_t | or_conn_highwater = OR_CONN_HIGHWATER_DFLT |
uint32_t | or_conn_lowwater = OR_CONN_LOWWATER_DFLT |
uint8_t | cc_sendme_inc = SENDME_INC_DFLT |
STATIC cc_alg_t | cc_alg = CC_ALG_DFLT |
static uint8_t | n_ewma_cwnd_pct = N_EWMA_CWND_PCT_DFLT |
static uint8_t | n_ewma_max = N_EWMA_MAX_DFLT |
static uint8_t | n_ewma_ss = N_EWMA_SS_DFLT |
static uint8_t | bwe_sendme_min = BWE_SENDME_MIN_DFLT |
static uint8_t | rtt_reset_pct = RTT_RESET_PCT_DFLT |
uint64_t | cc_stats_circs_created = 0 |
STATIC bool | is_monotime_clock_broken = false |
Common code used by all congestion control algorithms.
Definition in file congestion_control_common.c.
#define BWE_SENDME_MIN_DFLT (5) |
Definition at line 53 of file congestion_control_common.c.
#define CC_ALG_DFLT (CC_ALG_VEGAS) |
Definition at line 43 of file congestion_control_common.c.
#define CC_ALG_DFLT_ALWAYS (CC_ALG_VEGAS) |
Definition at line 44 of file congestion_control_common.c.
#define CELL_QUEUE_HIGH_DFLT (256) |
Definition at line 85 of file congestion_control_common.c.
#define CELL_QUEUE_LOW_DFLT (10) |
Definition at line 84 of file congestion_control_common.c.
#define CIRCWINDOW_INIT (4*SENDME_INC_DFLT) |
Definition at line 41 of file congestion_control_common.c.
#define CWND_INC_DFLT (1) |
Definition at line 46 of file congestion_control_common.c.
#define CWND_INC_PCT_SS_DFLT (100) |
Definition at line 47 of file congestion_control_common.c.
#define CWND_INC_RATE_DFLT (SENDME_INC_DFLT) |
Definition at line 48 of file congestion_control_common.c.
#define CWND_MAX_DFLT (INT32_MAX) |
Definition at line 51 of file congestion_control_common.c.
#define CWND_MIN_DFLT (CIRCWINDOW_INIT) |
Definition at line 50 of file congestion_control_common.c.
#define N_EWMA_CWND_PCT_DFLT (50) |
Definition at line 55 of file congestion_control_common.c.
#define N_EWMA_MAX_DFLT (10) |
Definition at line 56 of file congestion_control_common.c.
#define N_EWMA_SS_DFLT (2) |
Definition at line 57 of file congestion_control_common.c.
#define NOLA_BDP_ALG BDP_ALG_PIECEWISE |
Definition at line 65 of file congestion_control_common.c.
#define OR_CONN_HIGHWATER_DFLT (32*1024) |
Definition at line 76 of file congestion_control_common.c.
#define OR_CONN_LOWWATER_DFLT (16*1024) |
Definition at line 77 of file congestion_control_common.c.
#define RTT_RESET_PCT_DFLT (100) |
Definition at line 59 of file congestion_control_common.c.
#define SENDME_INC_DFLT (TLS_RECORD_MAX_CELLS) |
Definition at line 40 of file congestion_control_common.c.
#define TOR_CONGESTION_CONTROL_COMMON_PRIVATE |
Definition at line 9 of file congestion_control_common.c.
#define TOR_CONGESTION_CONTROL_PRIVATE |
Definition at line 10 of file congestion_control_common.c.
#define VEGAS_BDP_MIX_ALG BDP_ALG_PIECEWISE |
Definition at line 64 of file congestion_control_common.c.
#define WESTWOOD_BDP_ALG BDP_ALG_PIECEWISE |
Definition at line 63 of file congestion_control_common.c.
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().
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().
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().
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.
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().
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.
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.
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().
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().
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.
|
static |
Allocate and initialize fields in congestion control object.
cc_alg is the negotiated congestion control algorithm.
sendme_inc is the number of packaged cells that a sendme cell acks. This parameter will come from circuit negotiation.
Definition at line 398 of file congestion_control_common.c.
|
static |
Set congestion control parameters on a circuit's congestion control object based on values from the consensus.
cc_alg is the negotiated congestion control algorithm.
sendme_inc is the number of packaged cells that a sendme cell acks. This parameter will come from circuit negotiation.
Definition at line 267 of file congestion_control_common.c.
Referenced by congestion_control_init().
congestion_control_t * congestion_control_new | ( | const circuit_params_t * | params, |
cc_path_t | path | ||
) |
Allocate and initialize a new congestion control object
Definition at line 412 of file congestion_control_common.c.
Referenced by hs_circ_setup_congestion_control().
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.
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.
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().
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().
|
static |
Called when we get a SENDME. Updates the bandwidth-delay-product (BDP) estimates of a circuit. Several methods of computing BDP are used, depending on scenario. While some congestion control algorithms only use one of these methods, we update them all because it's quick and easy.
Returns true if we were able to update BDP, false otherwise.
Definition at line 848 of file congestion_control_common.c.
Referenced by 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().
STATIC uint64_t congestion_control_update_circuit_rtt | ( | congestion_control_t * | cc, |
uint64_t | now_usec | ||
) |
Called when we get a SENDME. Updates circuit RTT by pulling off a timestamp of when we sent the CIRCWINDOW_INCREMENT-th cell from the queue of such timestamps, and comparing that to current time.
Also updates min, max, and EWMA of RTT.
Returns the current circuit RTT in usecs, or 0 if it could not be measured (due to clock jump, stall, etc).
Definition at line 782 of file congestion_control_common.c.
Referenced by congestion_control_update_circuit_estimates().
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().
|
inlinestatic |
Dequeue a u64 monotime usec timestamp from the front of a smartlist of pointers to 64.
Definition at line 455 of file congestion_control_common.c.
Referenced by congestion_control_update_circuit_rtt().
|
inline |
Enqueue a u64 timestamp to the end of a queue of timestamps.
Definition at line 442 of file congestion_control_common.c.
Referenced by congestion_control_note_cell_sent().
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().
|
inlinestatic |
Returns the number N of N-count EWMA, for averaging RTT and BDP over N SENDME acks.
This N is bracketed between a divisor of the number of acks in a CWND and a max value. It is always at least 2.
Definition at line 480 of file congestion_control_common.c.
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().
|
static |
Returns true if we have enough time data to use heuristics to compare RTT to a baseline.
Definition at line 676 of file congestion_control_common.c.
STATIC bool time_delta_stalled_or_jumped | ( | const congestion_control_t * | cc, |
uint64_t | old_delta, | ||
uint64_t | new_delta | ||
) |
Returns true if the monotime delta is 0, or is significantly different than the previous delta. Either case indicates that the monotime time source stalled or jumped.
Also caches the clock state in the is_monotime_clock_broken flag, so we can also provide a is_monotime_clock_reliable() function, used by flow control rate timing.
Definition at line 700 of file congestion_control_common.c.
Referenced by congestion_control_update_circuit_rtt().
|
static |
Minimum number of sendmes before we begin BDP estimates
Definition at line 123 of file congestion_control_common.c.
Definition at line 103 of file congestion_control_common.c.
uint8_t cc_sendme_inc = SENDME_INC_DFLT |
Definition at line 102 of file congestion_control_common.c.
uint64_t cc_stats_circs_created = 0 |
Metric to count the number of congestion control circuits
Definition at line 132 of file congestion_control_common.c.
int32_t cell_queue_high = CELL_QUEUE_HIGH_DFLT |
Definition at line 98 of file congestion_control_common.c.
int32_t cell_queue_low = CELL_QUEUE_LOW_DFLT |
Definition at line 99 of file congestion_control_common.c.
|
static |
Definition at line 97 of file congestion_control_common.c.
STATIC bool is_monotime_clock_broken = false |
Definition at line 688 of file congestion_control_common.c.
|
static |
Number of cwnd worth of sendme acks to smooth RTT and BDP with, using N_EWMA
Definition at line 108 of file congestion_control_common.c.
|
static |
Maximum number N for the N-count EWMA averaging of RTT and BDP.
Definition at line 113 of file congestion_control_common.c.
|
static |
Maximum number N for the N-count EWMA averaging of RTT in Slow Start.
Definition at line 118 of file congestion_control_common.c.
Referenced by n_ewma_count().
|
static |
Definition at line 94 of file congestion_control_common.c.
|
static |
Definition at line 91 of file congestion_control_common.c.
uint32_t or_conn_highwater = OR_CONN_HIGHWATER_DFLT |
Definition at line 100 of file congestion_control_common.c.
uint32_t or_conn_lowwater = OR_CONN_LOWWATER_DFLT |
Definition at line 101 of file congestion_control_common.c.
|
static |
Percentage of the current RTT to use when resetting the minimum RTT for a circuit. (RTT is reset when the cwnd hits cwnd_min).
Definition at line 129 of file congestion_control_common.c.