src/core/or/congestion_control_common.h

   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 int congestion_control_build_ext_request(uint8_t **msg_out,
  70                                          size_t *msg_len_out);
  71 int congestion_control_parse_ext_request(const uint8_t *msg,
  72                                          const size_t msg_len);
  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 uint8_t *msg,
  78                                           const size_t msg_len,
  79                                           circuit_params_t *params_out);
  80 bool congestion_control_validate_sendme_increment(uint8_t sendme_inc);
  81 char *congestion_control_get_control_port_fields(const origin_circuit_t *);
  82
  83 uint64_t congestion_control_get_num_rtt_reset(void);
  84 uint64_t congestion_control_get_num_clock_stalls(void);
  85
  86 extern uint64_t cc_stats_circs_created;
  87
  88 /* Ugh, C.. these are private. Use the getter instead, when
  89  * external to the congestion control code. */
  90 extern uint32_t or_conn_highwater;
  91 extern uint32_t or_conn_lowwater;
  92 extern int32_t cell_queue_high;
  93 extern int32_t cell_queue_low;
  94 extern uint8_t cc_sendme_inc;
  95
  96 /** Stop writing on an orconn when its outbuf is this large */
  97 static inline uint32_t
  98 or_conn_highwatermark(void)
  99 {
 100   return or_conn_highwater;
 101 }
 102
 103 /** Resume writing on an orconn when its outbuf is less than this */
 104 static inline uint32_t
 105 or_conn_lowwatermark(void)
 106 {
 107   return or_conn_lowwater;
 108 }
 109
 110 /** Stop reading on edge connections when we have this many cells
 111  * waiting on the appropriate queue. */
 112 static inline int32_t
 113 cell_queue_highwatermark(void)
 114 {
 115   return cell_queue_high;
 116 }
 117
 118 /** Start reading from edge connections again when we get down to this many
 119  * cells. */
 120 static inline int32_t
 121 cell_queue_lowwatermark(void)
 122 {
 123   return cell_queue_low;
 124 }
 125
 126 /** Returns the sendme inc rate cached from the most recent consensus */
 127 static inline uint8_t
 128 congestion_control_sendme_inc(void)
 129 {
 130   return cc_sendme_inc;
 131 }
 132
 133 /**
 134  * Compute an N-count EWMA, aka N-EWMA. N-EWMA is defined as:
 135  *  EWMA = alpha*value + (1-alpha)*EWMA_prev
 136  * with alpha = 2/(N+1).
 137  *
 138  * This works out to:
 139  *  EWMA = value*2/(N+1) + EMA_prev*(N-1)/(N+1)
 140  *       = (value*2 + EWMA_prev*(N-1))/(N+1)
 141  */
 142 static inline uint64_t
 143 n_count_ewma(uint64_t curr, uint64_t prev, uint64_t N)
 144 {
 145   if (prev == 0)
 146     return curr;
 147   else
 148     return (2*curr + (N-1)*prev)/(N+1);
 149 }
 150
 151 /**
 152  * Helper function that gives us a percentile weighted-average between
 153  * two values. The pct_max argument specifies the percentage weight of the
 154  * maximum of a and b, when computing this weighted-average.
 155  *
 156  * This also allows this function to be used as either MIN() or a MAX()
 157  * by this parameterization. It is MIN() when pct_max==0;
 158  * it is MAX() when pct_max==100; it is avg() when pct_max==50; it is a
 159  * weighted-average for values in between.
 160  */
 161 static inline uint64_t
 162 percent_max_mix(uint64_t a, uint64_t b, uint8_t pct_max)
 163 {
 164   uint64_t max = MAX(a, b);
 165   uint64_t min = MIN(a, b);
 166
 167   if (BUG(pct_max > 100)) {
 168     return max;
 169   }
 170
 171   return pct_max*max/100 + (100-pct_max)*min/100;
 172 }
 173
 174 /* Private section starts. */
 175 #ifdef TOR_CONGESTION_CONTROL_COMMON_PRIVATE
 176 STATIC uint64_t congestion_control_update_circuit_rtt(congestion_control_t *,
 177                                                       uint64_t);
 178
 179 STATIC bool time_delta_stalled_or_jumped(const congestion_control_t *cc,
 180                                   uint64_t old_delta, uint64_t new_delta);
 181
 182 STATIC void enqueue_timestamp(smartlist_t *timestamps_u64,
 183                                      uint64_t timestamp_usec);
 184
 185 /*
 186  * Unit tests declaractions.
 187  */
 188 #ifdef TOR_UNIT_TESTS
 189
 190 extern bool is_monotime_clock_broken;
 191 extern cc_alg_t cc_alg;
 192 void congestion_control_set_cc_enabled(void);
 193 void congestion_control_set_cc_disabled(void);
 194
 195 #endif /* defined(TOR_UNIT_TESTS) */
 196
 197 #endif /* defined(TOR_CONGESTION_CONTROL_PRIVATE) */
 198
 199 #endif /* !defined(TOR_CONGESTION_CONTROL_COMMON_H) */