src/test/test_congestion_control.c

   1 #include "core/or/or.h"
   2 #include "test/test.h"
   3 #include "test/log_test_helpers.h"
   4 #include "lib/testsupport/testsupport.h"
   5 #include "test/fakecircs.h"
   6 #include "test/rng_test_helpers.h"
   7
   8 #include "lib/time/compat_time.h"
   9
  10 #include "core/or/circuitlist.h"
  11 #include "core/or/circuitmux.h"
  12 #include "core/or/channel.h"
  13
  14 #define TOR_CONGESTION_CONTROL_COMMON_PRIVATE
  15 #define TOR_CONGESTION_CONTROL_PRIVATE
  16 #include "core/or/congestion_control_st.h"
  17 #include "core/or/congestion_control_common.h"
  18 #include "core/or/congestion_control_vegas.h"
  19
  20 void test_congestion_control_rtt(void *arg);
  21 void test_congestion_control_clock(void *arg);
  22 void test_congestion_control_vegas_cwnd(void *arg);
  23
  24 static void
  25 circuitmux_attach_circuit_mock(circuitmux_t *cmux, circuit_t *circ,
  26                                cell_direction_t direction);
  27
  28 static void
  29 circuitmux_attach_circuit_mock(circuitmux_t *cmux, circuit_t *circ,
  30                                cell_direction_t direction)
  31 {
  32   (void)cmux;
  33   (void)circ;
  34   (void)direction;
  35
  36   return;
  37 }
  38
  39 /* =============== Clock Heuristic Test Vectors =============== */
  40
  41 typedef struct clock_vec
  42 {
  43   uint64_t old_delta_in;
  44   uint64_t new_delta_in;
  45   bool in_slow_start_in;
  46   bool cached_result_out;
  47   bool result_out;
  48 } clock_vec_t;
  49
  50 static void
  51 run_clock_test_vec(congestion_control_t *cc,
  52              clock_vec_t *vec, size_t vec_len)
  53 {
  54   for (size_t i = 0; i < vec_len; i++) {
  55     cc->in_slow_start = vec[i].in_slow_start_in;
  56     cc->ewma_rtt_usec = vec[i].old_delta_in*1000;
  57     bool ret = time_delta_stalled_or_jumped(cc,
  58                                             vec[i].old_delta_in,
  59                                             vec[i].new_delta_in);
  60
  61     tt_int_op(ret, OP_EQ, vec[i].result_out);
  62     tt_int_op(is_monotime_clock_broken, OP_EQ, vec[i].cached_result_out);
  63   }
  64
  65  done:
  66   is_monotime_clock_broken = false;
  67 }
  68
  69 /**
  70  * This test verifies the behavior of Section 2.1.1 of
  71  * Prop#324 (CLOCK_HEURISTICS).
  72  *
  73  * It checks that we declare the clock value stalled,
  74  * and cache that value, on various time deltas.
  75  *
  76  * It also verifies that our heuristics behave correctly
  77  * with respect to slow start and large clock jumps/stalls.
  78  */
  79 void
  80 test_congestion_control_clock(void *arg)
  81 {
  82   (void)arg;
  83   clock_vec_t vect1[] =
  84     {
  85       {0, 1, 1, 0, 0}, // old delta 0, slow start -> false
  86       {0, 0, 1, 1, 1}, // New delta 0 -> cache true, return true
  87       {1, 1, 1, 1, 0}, // In slow start -> keep cache, but return false
  88       {1, 4999, 0, 0, 0}, // Not slow start, edge -> update cache, and false
  89       {4999, 1, 0, 0, 0}, // Not slow start, other edge -> false
  90       {5001, 1, 0, 0, 0}, // Not slow start w/ -5000x -> use cache (false)
  91       {5001, 0, 0, 1, 1}, // New delta 0 -> cache true, return true
  92       {5001, 1, 0, 1, 1}, // Not slow start w/ -5000x -> use cache (true)
  93       {5001, 1, 1, 1, 0}, // In slow start w/ -5000x -> false
  94       {0, 5001, 0, 1, 0}, // Not slow start w/ no EWMA -> false
  95       {1, 5001, 1, 1, 0}, // In slow start w/ +5000x -> false
  96       {1, 1, 0, 0, 0}, // Not slow start -> update cache to false
  97       {5001, 1, 0, 0, 0}, // Not slow start w/ -5000x -> use cache (false)
  98       {1, 5001, 0, 0, 1}, // Not slow start w/ +5000x -> true
  99       {0, 5001, 0, 0, 0}, // Not slow start w/ no EWMA -> false
 100       {5001, 1, 1, 0, 0}, // In slow start w/ -5000x change -> false
 101       {1, 1, 0, 0, 0} // Not slow start -> false
 102     };
 103
 104   circuit_params_t params;
 105
 106   params.cc_enabled = 1;
 107   params.sendme_inc_cells = TLS_RECORD_MAX_CELLS;
 108   cc_alg = CC_ALG_VEGAS;
 109   congestion_control_t *cc = congestion_control_new(&params, CC_PATH_EXIT);
 110
 111   run_clock_test_vec(cc, vect1, sizeof(vect1)/sizeof(clock_vec_t));
 112
 113   congestion_control_free(cc);
 114 }
 115
 116 /* =========== RTT Test Vectors ================== */
 117
 118 typedef struct rtt_vec {
 119   uint64_t sent_usec_in;
 120   uint64_t got_sendme_usec_in;
 121   uint64_t cwnd_in;
 122   bool ss_in;
 123   uint64_t curr_rtt_usec_out;
 124   uint64_t ewma_rtt_usec_out;
 125   uint64_t min_rtt_usec_out;
 126 } rtt_vec_t;
 127
 128 static void
 129 run_rtt_test_vec(congestion_control_t *cc,
 130                  rtt_vec_t *vec, size_t vec_len)
 131 {
 132   for (size_t i = 0; i < vec_len; i++) {
 133     enqueue_timestamp(cc->sendme_pending_timestamps,
 134                       vec[i].sent_usec_in);
 135   }
 136
 137   for (size_t i = 0; i < vec_len; i++) {
 138     cc->cwnd = vec[i].cwnd_in;
 139     cc->in_slow_start = vec[i].ss_in;
 140     uint64_t curr_rtt_usec = congestion_control_update_circuit_rtt(cc,
 141                                          vec[i].got_sendme_usec_in);
 142
 143     tt_int_op(curr_rtt_usec, OP_EQ, vec[i].curr_rtt_usec_out);
 144     tt_int_op(cc->min_rtt_usec, OP_EQ, vec[i].min_rtt_usec_out);
 145     tt_int_op(cc->ewma_rtt_usec, OP_EQ, vec[i].ewma_rtt_usec_out);
 146   }
 147  done:
 148   is_monotime_clock_broken = false;
 149 }
 150
 151 /**
 152  * This test validates current, EWMA, and minRTT calculation
 153  * from Sections 2.1 of Prop#324.
 154  *
 155  * We also do NOT exercise the sendme pacing code here. See
 156  * test_sendme_is_next() for that, in test_sendme.c.
 157  */
 158 void
 159 test_congestion_control_rtt(void *arg)
 160 {
 161   (void)arg;
 162   rtt_vec_t vect1[] = {
 163     {100000, 200000, 124, 1, 100000, 100000, 100000},
 164     {200000, 300000, 124, 1, 100000, 100000, 100000},
 165     {350000, 500000, 124, 1, 150000, 133333, 100000},
 166     {500000, 550000, 124, 1, 50000,  77777, 77777},
 167     {600000, 700000, 124, 1, 100000, 92592, 77777},
 168     {700000, 750000, 124, 1, 50000, 64197, 64197},
 169     {750000, 875000, 124, 0, 125000, 104732, 104732},
 170     {875000, 900000, 124, 0, 25000, 51577, 104732},
 171     {900000, 950000, 200, 0, 50000, 50525, 50525}
 172   };
 173
 174   circuit_params_t params;
 175   congestion_control_t *cc = NULL;
 176
 177   params.cc_enabled = 1;
 178   params.sendme_inc_cells = TLS_RECORD_MAX_CELLS;
 179   cc_alg = CC_ALG_VEGAS;
 180
 181   cc = congestion_control_new(&params, CC_PATH_EXIT);
 182   run_rtt_test_vec(cc, vect1, sizeof(vect1)/sizeof(rtt_vec_t));
 183   congestion_control_free(cc);
 184
 185   return;
 186 }
 187
 188 /* =========== Vegas CWND Test Vectors ============== */
 189
 190 typedef struct cwnd_vec {
 191   uint64_t sent_usec_in;
 192   uint64_t got_sendme_usec_in;
 193   bool or_conn_blocked_in;
 194   uint64_t inflight_in;
 195   uint64_t ewma_rtt_usec_out;
 196   uint64_t min_rtt_usec_out;
 197   uint64_t cwnd_out;
 198   bool in_slow_start_out;
 199   bool cwnd_full_out;
 200   bool blocked_chan_out;
 201 } cwnd_vec_t;
 202
 203 static void
 204 run_vegas_cwnd_test_vec(congestion_control_t *cc,
 205                         circuit_t *circ,
 206                         cwnd_vec_t *vec, size_t vec_len)
 207 {
 208   for (size_t i = 0; i < vec_len; i++) {
 209     enqueue_timestamp(cc->sendme_pending_timestamps,
 210                       vec[i].sent_usec_in);
 211   }
 212
 213   for (size_t i = 0; i < vec_len; i++) {
 214     log_notice(LD_CIRC, "Step %d", (int)i);
 215     monotime_set_mock_time_nsec(vec[i].got_sendme_usec_in*1000);
 216     circ->circuit_blocked_on_p_chan = vec[i].or_conn_blocked_in;
 217     cc->inflight = vec[i].inflight_in;
 218
 219     congestion_control_vegas_process_sendme(cc, circ);
 220
 221     /* If the or conn was blocked, ensure we updated our
 222      * CC state */
 223     if (vec[i].or_conn_blocked_in) {
 224       tt_int_op(cc->next_cc_event, OP_EQ, CWND_UPDATE_RATE(cc));
 225     }
 226
 227     tt_int_op(cc->ewma_rtt_usec, OP_EQ, vec[i].ewma_rtt_usec_out);
 228     tt_int_op(cc->min_rtt_usec, OP_EQ, vec[i].min_rtt_usec_out);
 229     tt_int_op(cc->cwnd, OP_EQ, vec[i].cwnd_out);
 230
 231     tt_int_op(cc->in_slow_start, OP_EQ, vec[i].in_slow_start_out);
 232     tt_int_op(cc->cwnd_full, OP_EQ, vec[i].cwnd_full_out);
 233     tt_int_op(cc->blocked_chan, OP_EQ, vec[i].blocked_chan_out);
 234   }
 235
 236  done:
 237   is_monotime_clock_broken = false;
 238 }
 239
 240 /**
 241  * This test validates congestion window updates for the
 242  * TOR_VEGAS congestion control algorithm, from Section 3.3
 243  * of Prop#324.
 244  *
 245  * It tests updates as a function of the timestamp of the
 246  * cell that would trigger a sendme and the sendme arrival
 247  * timestamp, and as a function of orconn blocking.
 248  *
 249  * It ensures that at least one test vector caused a cwnd update
 250  * due to a blocked OR connection. The orconn blocking logic is
 251  * simulated -- we do NOT actually exercise the orconn code here.
 252  *
 253  * We also do NOT exercise the sendme pacing code here. See
 254  * test_sendme_is_next() for that, in test_sendme.c.
 255  *
 256  * We also do NOT exercise the negotiation code here. See
 257  * test_ntor3_handshake() for that, in test_ntor_v3.c.
 258  */
 259 void
 260 test_congestion_control_vegas_cwnd(void *arg)
 261 {
 262   (void)arg;
 263   circuit_params_t params;
 264   /* Replay of RTT edge case checks, plus some extra to exit
 265    * slow start via RTT, and exercise full/not full */
 266   cwnd_vec_t vect1[] = {
 267     {100000, 200000, 0, 124, 100000, 100000, 155, 1, 0, 0},
 268     {200000, 300000, 0, 155, 100000, 100000, 186, 1, 1, 0},
 269     {350000, 500000, 0, 186, 133333, 100000, 217, 1, 1, 0},
 270     {500000, 550000, 0, 217, 77777, 77777, 248, 1, 1, 0},
 271     {600000, 700000, 0, 248, 92592, 77777, 279, 1, 1, 0},
 272     {700000, 750000, 0, 279, 64197, 64197, 310, 1, 0, 0}, // Fullness expiry
 273     {750000, 875000, 0, 310, 104732, 64197, 341, 1, 1, 0},
 274     {875000, 900000, 0, 341, 51577, 51577, 372, 1, 1, 0},
 275     {900000, 950000, 0, 279, 50525, 50525, 403, 1, 1, 0},
 276     {950000, 1000000, 0, 279, 50175, 50175, 434, 1, 1, 0},
 277     {1000000, 1050000, 0, 279, 50058, 50058, 465, 1, 1, 0},
 278     {1050000, 1100000, 0, 279, 50019, 50019, 496, 1, 1, 0},
 279     {1100000, 1150000, 0, 279, 50006, 50006, 527, 1, 1, 0},
 280     {1150000, 1200000, 0, 279, 50002, 50002, 558, 1, 1, 0},
 281     {1200000, 1250000, 0, 550, 50000, 50000, 589, 1, 1, 0},
 282     {1250000, 1300000, 0, 550, 50000, 50000, 620, 1, 0, 0}, // Fullness expiry
 283     {1300000, 1350000, 0, 550, 50000, 50000, 635, 1, 1, 0},
 284     {1350000, 1400000, 0, 550, 50000, 50000, 650, 1, 1, 0},
 285     {1400000, 1450000, 0, 150, 50000, 50000, 650, 1, 0, 0}, // cwnd not full
 286     {1450000, 1500000, 0, 150, 50000, 50000, 650, 1, 0, 0}, // cwnd not full
 287     {1500000, 1550000, 0, 550, 50000, 50000, 664, 1, 1, 0}, // cwnd full
 288     {1500000, 1600000, 0, 550, 83333, 50000, 584, 0, 1, 0}, // gamma exit
 289     {1600000, 1650000, 0, 550, 61111, 50000, 585, 0, 1, 0}, // alpha
 290     {1650000, 1700000, 0, 550, 53703, 50000, 586, 0, 1, 0},
 291     {1700000, 1750000, 0, 100, 51234, 50000, 586, 0, 0, 0}, // alpha, not full
 292     {1750000, 1900000, 0, 100, 117078, 50000, 559, 0, 0, 0}, // delta, not full
 293     {1900000, 2000000, 0, 100, 105692, 50000, 558, 0, 0, 0}, // beta, not full
 294     {2000000, 2075000, 0, 500, 85230, 50000, 558, 0, 1, 0}, // no change
 295     {2075000, 2125000, 1, 500, 61743, 50000, 557, 0, 1, 1}, // beta, blocked
 296     {2125000, 2150000, 0, 500, 37247, 37247, 558, 0, 1, 0}, // alpha
 297     {2150000, 2350000, 0, 500, 145749, 37247, 451, 0, 1, 0} // delta
 298   };
 299   /* Test exiting slow start via blocked orconn */
 300   cwnd_vec_t vect2[] = {
 301       {100000, 200000, 0, 124, 100000, 100000, 155, 1, 0, 0},
 302       {200000, 300000, 0, 155, 100000, 100000, 186, 1, 1, 0},
 303       {350000, 500000, 0, 186, 133333, 100000, 217, 1, 1, 0},
 304       {500000, 550000, 1, 217, 77777, 77777, 403, 0, 1, 1}, // ss exit, blocked
 305       {600000, 700000, 0, 248, 92592, 77777, 404, 0, 1, 0}, // alpha
 306       {700000, 750000, 1, 404, 64197, 64197, 403, 0, 0, 1}, // blocked beta
 307       {750000, 875000, 0, 403, 104732, 64197, 404, 0, 1, 0}
 308   };
 309   /* Real upload 1 */
 310   cwnd_vec_t vect3[] = {
 311       { 18258527, 19002938, 0, 83, 744411, 744411, 155, 1, 0, 0 },
 312       { 18258580, 19254257, 0, 52, 911921, 744411, 186, 1, 1, 0 },
 313       { 20003224, 20645298, 0, 164, 732023, 732023, 217, 1, 1, 0 },
 314       { 20003367, 21021444, 0, 133, 922725, 732023, 248, 1, 1, 0 },
 315       { 20003845, 21265508, 0, 102, 1148683, 732023, 279, 1, 1, 0 },
 316       { 20003975, 21429157, 0, 71, 1333015, 732023, 310, 1, 0, 0 },
 317       { 20004309, 21707677, 0, 40, 1579917, 732023, 310, 1, 0, 0 }
 318   };
 319   /* Real upload 2 */
 320   cwnd_vec_t vect4[] = {
 321       { 358297091, 358854163, 0, 83, 557072, 557072, 155, 1, 0, 0 },
 322       { 358297649, 359123845, 0, 52, 736488, 557072, 186, 1, 1, 0 },
 323       { 359492879, 359995330, 0, 186, 580463, 557072, 217, 1, 1, 0 },
 324       { 359493043, 360489243, 0, 217, 857621, 557072, 248, 1, 1, 0 },
 325       { 359493232, 360489673, 0, 248, 950167, 557072, 279, 1, 1, 0 },
 326       { 359493795, 360489971, 0, 279, 980839, 557072, 310, 1, 0, 0 },
 327       { 359493918, 360490248, 0, 310, 991166, 557072, 341, 1, 1, 0 },
 328       { 359494029, 360716465, 0, 341, 1145346, 557072, 372, 1, 1, 0 },
 329       { 359996888, 360948867, 0, 372, 1016434, 557072, 403, 1, 1, 0 },
 330       { 359996979, 360949330, 0, 403, 973712, 557072, 434, 1, 1, 0 },
 331       { 360489528, 361113615, 0, 434, 740628, 557072, 465, 1, 1, 0 },
 332       { 360489656, 361281604, 0, 465, 774841, 557072, 496, 1, 1, 0 },
 333       { 360489837, 361500461, 0, 496, 932029, 557072, 482, 0, 1, 0 },
 334       { 360489963, 361500631, 0, 482, 984455, 557072, 482, 0, 1, 0 },
 335       { 360490117, 361842481, 0, 482, 1229727, 557072, 481, 0, 1, 0 }
 336   };
 337
 338   congestion_control_t *cc = NULL;
 339   channel_t dummy_channel = {0};
 340
 341   MOCK(circuitmux_attach_circuit, circuitmux_attach_circuit_mock);
 342   testing_enable_reproducible_rng();
 343
 344   monotime_init();
 345   monotime_enable_test_mocking();
 346   monotime_set_mock_time_nsec(0);
 347
 348   dummy_channel.cmux = circuitmux_alloc();
 349   circuit_t *circ = TO_CIRCUIT(new_fake_orcirc(&dummy_channel,
 350                                                &dummy_channel));
 351   circ->purpose = CIRCUIT_PURPOSE_OR;
 352
 353   params.cc_enabled = 1;
 354   params.sendme_inc_cells = TLS_RECORD_MAX_CELLS;
 355   cc_alg = CC_ALG_VEGAS;
 356
 357   cc = congestion_control_new(&params, CC_PATH_EXIT);
 358   run_vegas_cwnd_test_vec(cc, circ, vect1,
 359                           sizeof(vect1)/sizeof(cwnd_vec_t));
 360   congestion_control_free(cc);
 361
 362   cc = congestion_control_new(&params, CC_PATH_EXIT);
 363   run_vegas_cwnd_test_vec(cc, circ, vect2,
 364                           sizeof(vect2)/sizeof(cwnd_vec_t));
 365   congestion_control_free(cc);
 366
 367   cc = congestion_control_new(&params, CC_PATH_EXIT);
 368   run_vegas_cwnd_test_vec(cc, circ, vect3,
 369                           sizeof(vect3)/sizeof(cwnd_vec_t));
 370   congestion_control_free(cc);
 371
 372   cc = congestion_control_new(&params, CC_PATH_EXIT);
 373   run_vegas_cwnd_test_vec(cc, circ, vect4,
 374                           sizeof(vect4)/sizeof(cwnd_vec_t));
 375   congestion_control_free(cc);
 376
 377  //done:
 378   circuitmux_free(dummy_channel.cmux);
 379   return;
 380 }
 381
 382 #define TEST_CONGESTION_CONTROL(name, flags) \
 383     { #name, test_##name, (flags), NULL, NULL }
 384
 385 struct testcase_t congestion_control_tests[] = {
 386   TEST_CONGESTION_CONTROL(congestion_control_clock, TT_FORK),
 387   TEST_CONGESTION_CONTROL(congestion_control_rtt, TT_FORK),
 388   TEST_CONGESTION_CONTROL(congestion_control_vegas_cwnd, TT_FORK),
 389   END_OF_TESTCASES
 390 };