Tor  0.4.8.0-alpha-dev
congestion_control_common.h
Go to the documentation of this file.
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 
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 
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 
42 
43 struct circuit_params_t;
45  const struct circuit_params_t *params,
46  cc_path_t path);
47 
49  const circuit_t *circ,
50  const crypt_path_t *layer_hint);
51 
53  const circuit_t *circ,
54  const crypt_path_t *cpath);
55 
57  const circuit_t *,
58  const crypt_path_t *);
59 
61  const crypt_path_t *);
62 
63 int sendme_get_inc_count(const circuit_t *, const crypt_path_t *);
66 
68 
70 
71 int congestion_control_build_ext_request(uint8_t **msg_out,
72  size_t *msg_len_out);
73 int congestion_control_parse_ext_request(const uint8_t *msg,
74  const size_t msg_len);
76  const circuit_params_t *circ_params,
77  uint8_t **msg_out,
78  size_t *msg_len_out);
79 int congestion_control_parse_ext_response(const uint8_t *msg,
80  const size_t msg_len,
81  circuit_params_t *params_out);
82 bool congestion_control_validate_sendme_increment(uint8_t sendme_inc);
84 
87 
88 extern uint64_t cc_stats_circs_created;
89 
90 /* Ugh, C.. these are private. Use the getter instead, when
91  * external to the congestion control code. */
92 extern uint32_t or_conn_highwater;
93 extern uint32_t or_conn_lowwater;
94 extern int32_t cell_queue_high;
95 extern int32_t cell_queue_low;
96 extern uint8_t cc_sendme_inc;
97 
98 /** Stop writing on an orconn when its outbuf is this large */
99 static inline uint32_t
101 {
102  return or_conn_highwater;
103 }
104 
105 /** Resume writing on an orconn when its outbuf is less than this */
106 static inline uint32_t
108 {
109  return or_conn_lowwater;
110 }
111 
112 /** Stop reading on edge connections when we have this many cells
113  * waiting on the appropriate queue. */
114 static inline int32_t
116 {
117  return cell_queue_high;
118 }
119 
120 /** Start reading from edge connections again when we get down to this many
121  * cells. */
122 static inline int32_t
124 {
125  return cell_queue_low;
126 }
127 
128 /** Returns the sendme inc rate cached from the most recent consensus */
129 static inline uint8_t
131 {
132  return cc_sendme_inc;
133 }
134 
135 /**
136  * Compute an N-count EWMA, aka N-EWMA. N-EWMA is defined as:
137  * EWMA = alpha*value + (1-alpha)*EWMA_prev
138  * with alpha = 2/(N+1).
139  *
140  * This works out to:
141  * EWMA = value*2/(N+1) + EMA_prev*(N-1)/(N+1)
142  * = (value*2 + EWMA_prev*(N-1))/(N+1)
143  */
144 static inline uint64_t
145 n_count_ewma(uint64_t curr, uint64_t prev, uint64_t N)
146 {
147  if (prev == 0)
148  return curr;
149  else
150  return (2*curr + (N-1)*prev)/(N+1);
151 }
152 
153 /**
154  * Helper function that gives us a percentile weighted-average between
155  * two values. The pct_max argument specifies the percentage weight of the
156  * maximum of a and b, when computing this weighted-average.
157  *
158  * This also allows this function to be used as either MIN() or a MAX()
159  * by this parameterization. It is MIN() when pct_max==0;
160  * it is MAX() when pct_max==100; it is avg() when pct_max==50; it is a
161  * weighted-average for values in between.
162  */
163 static inline uint64_t
164 percent_max_mix(uint64_t a, uint64_t b, uint8_t pct_max)
165 {
166  uint64_t max = MAX(a, b);
167  uint64_t min = MIN(a, b);
168 
169  if (BUG(pct_max > 100)) {
170  return max;
171  }
172 
173  return pct_max*max/100 + (100-pct_max)*min/100;
174 }
175 
176 /* Private section starts. */
177 #ifdef TOR_CONGESTION_CONTROL_PRIVATE
178 
179 /*
180  * Unit tests declaractions.
181  */
182 #ifdef TOR_UNIT_TESTS
183 
185 
186 #endif /* defined(TOR_UNIT_TESTS) */
187 
188 #endif /* defined(TOR_CONGESTION_CONTROL_PRIVATE) */
189 
190 #endif /* !defined(TOR_CONGESTION_CONTROL_COMMON_H) */
Base circuit structure.
#define MAX(a, b)
Definition: cmp.h:22
void congestion_control_set_cc_enabled(void)
congestion_control_t * congestion_control_new(const circuit_params_t *params, cc_path_t path)
static uint32_t or_conn_highwatermark(void)
bool congestion_control_validate_sendme_increment(uint8_t sendme_inc)
char * congestion_control_get_control_port_fields(const origin_circuit_t *)
bool congestion_control_update_circuit_estimates(congestion_control_t *, const circuit_t *, const crypt_path_t *)
static uint64_t n_count_ewma(uint64_t curr, uint64_t prev, uint64_t N)
int sendme_get_inc_count(const circuit_t *, const crypt_path_t *)
void congestion_control_free_(congestion_control_t *cc)
int congestion_control_dispatch_cc_alg(congestion_control_t *cc, const circuit_t *circ, const crypt_path_t *layer_hint)
uint64_t congestion_control_get_num_clock_stalls(void)
uint64_t congestion_control_get_num_rtt_reset(void)
void congestion_control_note_cell_sent(congestion_control_t *cc, const circuit_t *circ, const crypt_path_t *cpath)
int congestion_control_get_package_window(const circuit_t *, const crypt_path_t *)
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_request(const uint8_t *msg, const size_t msg_len)
static uint64_t percent_max_mix(uint64_t a, uint64_t b, uint8_t pct_max)
static uint8_t congestion_control_sendme_inc(void)
static uint32_t or_conn_lowwatermark(void)
int congestion_control_build_ext_request(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_enabled(void)
bool circuit_sent_cell_for_sendme(const circuit_t *, const crypt_path_t *)
uint64_t cc_stats_circs_created
bool is_monotime_clock_reliable(void)
static int32_t cell_queue_highwatermark(void)
void congestion_control_new_consensus_params(const networkstatus_t *ns)
static int32_t cell_queue_lowwatermark(void)
Path structures for origin circuits.
Header file for onion_crypto.c.