congestion_control_common.h (6282B)
1 /* Copyright (c) 2019-2021, The Tor Project, Inc. */ 2 /* See LICENSE for licensing information */ 3 4 /** 5 * \file congestion_control_common.h 6 * \brief Public APIs for congestion control 7 **/ 8 9 #ifndef TOR_CONGESTION_CONTROL_COMMON_H 10 #define TOR_CONGESTION_CONTROL_COMMON_H 11 12 #include "core/crypto/onion_crypto.h" 13 #include "core/or/crypt_path_st.h" 14 #include "core/or/circuit_st.h" 15 16 /* The maximum whole number of cells that can fit in a 17 * full TLS record. This is 31. */ 18 #define TLS_RECORD_MAX_CELLS ((16 * 1024) / CELL_MAX_NETWORK_SIZE) 19 20 typedef struct congestion_control_t congestion_control_t; 21 22 /** 23 * Specifies the path type to help choose congestion control 24 * parameters. Since these paths are different lengths, they 25 * will need different queue parameters. */ 26 typedef enum { 27 CC_PATH_EXIT = 0, 28 CC_PATH_ONION = 1, 29 CC_PATH_ONION_SOS = 2, 30 CC_PATH_ONION_VG = 3, 31 CC_PATH_SBWS = 4, 32 } cc_path_t; 33 34 /** The length of a path for sbws measurement */ 35 #define SBWS_ROUTE_LEN 2 36 37 /** Wrapper for the free function, set the CC pointer to NULL after free */ 38 #define congestion_control_free(cc) \ 39 FREE_AND_NULL(congestion_control_t, congestion_control_free_, cc) 40 41 void congestion_control_free_(congestion_control_t *cc); 42 43 struct circuit_params_t; 44 congestion_control_t *congestion_control_new( 45 const struct circuit_params_t *params, 46 cc_path_t path); 47 48 int congestion_control_dispatch_cc_alg(congestion_control_t *cc, 49 circuit_t *circ); 50 51 void congestion_control_note_cell_sent(congestion_control_t *cc, 52 const circuit_t *circ, 53 const crypt_path_t *cpath); 54 55 bool congestion_control_update_circuit_estimates(congestion_control_t *, 56 const circuit_t *); 57 58 int congestion_control_get_package_window(const circuit_t *, 59 const crypt_path_t *); 60 61 int sendme_get_inc_count(const circuit_t *, const crypt_path_t *); 62 bool circuit_sent_cell_for_sendme(const circuit_t *, const crypt_path_t *); 63 bool is_monotime_clock_reliable(void); 64 65 void congestion_control_new_consensus_params(const networkstatus_t *ns); 66 67 bool congestion_control_enabled(void); 68 69 struct trn_extension_st; 70 int congestion_control_build_ext_request(struct trn_extension_st *ext); 71 72 int congestion_control_parse_ext_request(const struct trn_extension_st *ext); 73 int congestion_control_build_ext_response(const circuit_params_t *our_params, 74 const circuit_params_t *circ_params, 75 uint8_t **msg_out, 76 size_t *msg_len_out); 77 int congestion_control_parse_ext_response(const struct trn_extension_st *ext, 78 circuit_params_t *params_out); 79 bool congestion_control_validate_sendme_increment(uint8_t sendme_inc); 80 char *congestion_control_get_control_port_fields(const origin_circuit_t *); 81 82 uint64_t congestion_control_get_num_rtt_reset(void); 83 uint64_t congestion_control_get_num_clock_stalls(void); 84 85 extern uint64_t cc_stats_circs_created; 86 87 /* Ugh, C.. these are private. Use the getter instead, when 88 * external to the congestion control code. */ 89 extern uint32_t or_conn_highwater; 90 extern uint32_t or_conn_lowwater; 91 extern int32_t cell_queue_high; 92 extern int32_t cell_queue_low; 93 extern uint8_t cc_sendme_inc; 94 95 /** Stop writing on an orconn when its outbuf is this large */ 96 static inline uint32_t 97 or_conn_highwatermark(void) 98 { 99 return or_conn_highwater; 100 } 101 102 /** Resume writing on an orconn when its outbuf is less than this */ 103 static inline uint32_t 104 or_conn_lowwatermark(void) 105 { 106 return or_conn_lowwater; 107 } 108 109 /** Stop reading on edge connections when we have this many cells 110 * waiting on the appropriate queue. */ 111 static inline int32_t 112 cell_queue_highwatermark(void) 113 { 114 return cell_queue_high; 115 } 116 117 /** Start reading from edge connections again when we get down to this many 118 * cells. */ 119 static inline int32_t 120 cell_queue_lowwatermark(void) 121 { 122 return cell_queue_low; 123 } 124 125 /** Returns the sendme inc rate cached from the most recent consensus */ 126 static inline uint8_t 127 congestion_control_sendme_inc(void) 128 { 129 return cc_sendme_inc; 130 } 131 132 /** 133 * Compute an N-count EWMA, aka N-EWMA. N-EWMA is defined as: 134 * EWMA = alpha*value + (1-alpha)*EWMA_prev 135 * with alpha = 2/(N+1). 136 * 137 * This works out to: 138 * EWMA = value*2/(N+1) + EMA_prev*(N-1)/(N+1) 139 * = (value*2 + EWMA_prev*(N-1))/(N+1) 140 */ 141 static inline uint64_t 142 n_count_ewma(uint64_t curr, uint64_t prev, uint64_t N) 143 { 144 if (prev == 0) 145 return curr; 146 else 147 return (2*curr + (N-1)*prev)/(N+1); 148 } 149 150 /** 151 * Helper function that gives us a percentile weighted-average between 152 * two values. The pct_max argument specifies the percentage weight of the 153 * maximum of a and b, when computing this weighted-average. 154 * 155 * This also allows this function to be used as either MIN() or a MAX() 156 * by this parameterization. It is MIN() when pct_max==0; 157 * it is MAX() when pct_max==100; it is avg() when pct_max==50; it is a 158 * weighted-average for values in between. 159 */ 160 static inline uint64_t 161 percent_max_mix(uint64_t a, uint64_t b, uint8_t pct_max) 162 { 163 uint64_t max = MAX(a, b); 164 uint64_t min = MIN(a, b); 165 166 if (BUG(pct_max > 100)) { 167 return max; 168 } 169 170 return pct_max*max/100 + (100-pct_max)*min/100; 171 } 172 173 /* Private section starts. */ 174 #ifdef TOR_CONGESTION_CONTROL_COMMON_PRIVATE 175 STATIC uint64_t congestion_control_update_circuit_rtt(congestion_control_t *, 176 uint64_t); 177 178 STATIC bool time_delta_stalled_or_jumped(const congestion_control_t *cc, 179 uint64_t old_delta, uint64_t new_delta); 180 181 STATIC void enqueue_timestamp(smartlist_t *timestamps_u64, 182 uint64_t timestamp_usec); 183 184 /* 185 * Unit tests declaractions. 186 */ 187 #ifdef TOR_UNIT_TESTS 188 189 extern bool is_monotime_clock_broken; 190 extern cc_alg_t cc_alg; 191 void congestion_control_set_cc_enabled(void); 192 void congestion_control_set_cc_disabled(void); 193 194 #endif /* defined(TOR_UNIT_TESTS) */ 195 196 #endif /* defined(TOR_CONGESTION_CONTROL_PRIVATE) */ 197 198 #endif /* !defined(TOR_CONGESTION_CONTROL_COMMON_H) */