test_congestion_control.c (14396B)
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(¶ms, 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(¶ms, 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(¶ms, 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(¶ms, 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(¶ms, 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(¶ms, 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 };