1 /* 2 * Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 /* For generating debug statistics during congestion controller development. */ 11 /*#define GENERATE_LOG*/ 12 13 #include "testutil.h" 14 #include <openssl/ssl.h> 15 #include "internal/quic_cc.h" 16 #include "internal/priority_queue.h" 17 18 /* 19 * Time Simulation 20 * =============== 21 */ 22 static OSSL_TIME fake_time = {0}; 23 24 #define TIME_BASE (ossl_ticks2time(5 * OSSL_TIME_SECOND)) 25 26 static OSSL_TIME fake_now(void *arg) 27 { 28 return fake_time; 29 } 30 31 static void step_time(uint32_t ms) 32 { 33 fake_time = ossl_time_add(fake_time, ossl_ms2time(ms)); 34 } 35 36 /* 37 * Network Simulation 38 * ================== 39 * 40 * This is a simple 'network simulator' which emulates a network with a certain 41 * bandwidth and latency. Sending a packet into the network causes it to consume 42 * some capacity of the network until the packet exits the network. Note that 43 * the capacity is not known to the congestion controller as the entire point of 44 * a congestion controller is to correctly estimate this capacity and this is 45 * what we are testing. The network simulator does take care of informing the 46 * congestion controller of ack/loss events automatically but the caller is 47 * responsible for querying the congestion controller and choosing the size of 48 * simulated transmitted packets. 49 */ 50 typedef struct net_pkt_st { 51 /* 52 * The time at which the packet was sent. 53 */ 54 OSSL_TIME tx_time; 55 56 /* 57 * The time at which the simulated packet arrives at the RX side (success) 58 * or is dropped (!success). 59 */ 60 OSSL_TIME arrive_time; 61 62 /* 63 * The time at which the transmitting side makes a determination of 64 * acknowledgement (if success) or loss (if !success). 65 */ 66 OSSL_TIME determination_time; 67 68 /* 69 * Current earliest time there is something to be done for this packet. 70 * min(arrive_time, determination_time). 71 */ 72 OSSL_TIME next_time; 73 74 /* 1 if the packet will be successfully delivered, 0 if it is to be lost. */ 75 int success; 76 77 /* 1 if we have already processed packet arrival. */ 78 int arrived; 79 80 /* Size of simulated packet in bytes. */ 81 size_t size; 82 83 /* pqueue internal index. */ 84 size_t idx; 85 } NET_PKT; 86 87 DEFINE_PRIORITY_QUEUE_OF(NET_PKT); 88 89 static int net_pkt_cmp(const NET_PKT *a, const NET_PKT *b) 90 { 91 return ossl_time_compare(a->next_time, b->next_time); 92 } 93 94 struct net_sim { 95 const OSSL_CC_METHOD *ccm; 96 OSSL_CC_DATA *cc; 97 98 uint64_t capacity; /* bytes/s */ 99 uint64_t latency; /* ms */ 100 101 uint64_t spare_capacity; 102 PRIORITY_QUEUE_OF(NET_PKT) *pkts; 103 104 uint64_t total_acked, total_lost; /* bytes */ 105 }; 106 107 static int net_sim_init(struct net_sim *s, 108 const OSSL_CC_METHOD *ccm, OSSL_CC_DATA *cc, 109 uint64_t capacity, uint64_t latency) 110 { 111 s->ccm = ccm; 112 s->cc = cc; 113 114 s->capacity = capacity; 115 s->latency = latency; 116 117 s->spare_capacity = capacity; 118 119 s->total_acked = 0; 120 s->total_lost = 0; 121 122 if (!TEST_ptr(s->pkts = ossl_pqueue_NET_PKT_new(net_pkt_cmp))) 123 return 0; 124 125 return 1; 126 } 127 128 static void do_free(NET_PKT *pkt) 129 { 130 OPENSSL_free(pkt); 131 } 132 133 static void net_sim_cleanup(struct net_sim *s) 134 { 135 ossl_pqueue_NET_PKT_pop_free(s->pkts, do_free); 136 } 137 138 static int net_sim_process(struct net_sim *s, size_t skip_forward); 139 140 static int net_sim_send(struct net_sim *s, size_t sz) 141 { 142 NET_PKT *pkt = OPENSSL_zalloc(sizeof(*pkt)); 143 int success; 144 145 if (!TEST_ptr(pkt)) 146 return 0; 147 148 /* 149 * Ensure we have processed any events which have come due as these might 150 * increase our spare capacity. 151 */ 152 if (!TEST_true(net_sim_process(s, 0))) 153 goto err; 154 155 /* Do we have room for the packet in the network? */ 156 success = (sz <= s->spare_capacity); 157 158 pkt->tx_time = fake_time; 159 pkt->success = success; 160 if (success) { 161 /* This packet will arrive successfully after |latency| time. */ 162 pkt->arrive_time = ossl_time_add(pkt->tx_time, 163 ossl_ms2time(s->latency)); 164 /* Assume all received packets are acknowledged immediately. */ 165 pkt->determination_time = ossl_time_add(pkt->arrive_time, 166 ossl_ms2time(s->latency)); 167 pkt->next_time = pkt->arrive_time; 168 s->spare_capacity -= sz; 169 } else { 170 /* 171 * In our network model, assume all packets are dropped due to a 172 * bottleneck at the peer's NIC RX queue; thus dropping occurs after 173 * |latency|. 174 */ 175 pkt->arrive_time = ossl_time_add(pkt->tx_time, 176 ossl_ms2time(s->latency)); 177 /* 178 * It will take longer to detect loss than to detect acknowledgement. 179 */ 180 pkt->determination_time = ossl_time_add(pkt->tx_time, 181 ossl_ms2time(3 * s->latency)); 182 pkt->next_time = pkt->determination_time; 183 } 184 185 pkt->size = sz; 186 187 if (!TEST_true(s->ccm->on_data_sent(s->cc, sz))) 188 goto err; 189 190 if (!TEST_true(ossl_pqueue_NET_PKT_push(s->pkts, pkt, &pkt->idx))) 191 goto err; 192 193 return 1; 194 195 err: 196 OPENSSL_free(pkt); 197 return 0; 198 } 199 200 static int net_sim_process_one(struct net_sim *s, int skip_forward) 201 { 202 NET_PKT *pkt = ossl_pqueue_NET_PKT_peek(s->pkts); 203 204 if (pkt == NULL) 205 return 3; 206 207 /* Jump forward to the next significant point in time. */ 208 if (skip_forward && ossl_time_compare(pkt->next_time, fake_time) > 0) 209 fake_time = pkt->next_time; 210 211 if (pkt->success && !pkt->arrived 212 && ossl_time_compare(fake_time, pkt->arrive_time) >= 0) { 213 /* Packet arrives */ 214 s->spare_capacity += pkt->size; 215 pkt->arrived = 1; 216 217 ossl_pqueue_NET_PKT_pop(s->pkts); 218 pkt->next_time = pkt->determination_time; 219 if (!ossl_pqueue_NET_PKT_push(s->pkts, pkt, &pkt->idx)) 220 return 0; 221 222 return 1; 223 } 224 225 if (ossl_time_compare(fake_time, pkt->determination_time) < 0) 226 return 2; 227 228 if (!TEST_true(!pkt->success || pkt->arrived)) 229 return 0; 230 231 if (!pkt->success) { 232 OSSL_CC_LOSS_INFO loss_info = {0}; 233 234 loss_info.tx_time = pkt->tx_time; 235 loss_info.tx_size = pkt->size; 236 237 if (!TEST_true(s->ccm->on_data_lost(s->cc, &loss_info))) 238 return 0; 239 240 if (!TEST_true(s->ccm->on_data_lost_finished(s->cc, 0))) 241 return 0; 242 243 s->total_lost += pkt->size; 244 ossl_pqueue_NET_PKT_pop(s->pkts); 245 OPENSSL_free(pkt); 246 } else { 247 OSSL_CC_ACK_INFO ack_info = {0}; 248 249 ack_info.tx_time = pkt->tx_time; 250 ack_info.tx_size = pkt->size; 251 252 if (!TEST_true(s->ccm->on_data_acked(s->cc, &ack_info))) 253 return 0; 254 255 s->total_acked += pkt->size; 256 ossl_pqueue_NET_PKT_pop(s->pkts); 257 OPENSSL_free(pkt); 258 } 259 260 return 1; 261 } 262 263 static int net_sim_process(struct net_sim *s, size_t skip_forward) 264 { 265 int rc; 266 267 while ((rc = net_sim_process_one(s, skip_forward > 0 ? 1 : 0)) == 1) 268 if (skip_forward > 0) 269 --skip_forward; 270 271 return rc; 272 } 273 274 /* 275 * State Dumping Utilities 276 * ======================= 277 * 278 * Utilities for outputting CC state information. 279 */ 280 #ifdef GENERATE_LOG 281 static FILE *logfile; 282 #endif 283 284 static int dump_state(const OSSL_CC_METHOD *ccm, OSSL_CC_DATA *cc, 285 struct net_sim *s) 286 { 287 #ifdef GENERATE_LOG 288 uint64_t cwnd_size, cur_bytes, state; 289 290 if (logfile == NULL) 291 return 1; 292 293 if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_CWND_SIZE, 294 &cwnd_size))) 295 return 0; 296 297 if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT, 298 &cur_bytes))) 299 return 0; 300 301 if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_STATE, 302 &state))) 303 return 0; 304 305 fprintf(logfile, "%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,\"%c\"\n", 306 ossl_time2ms(fake_time), 307 ccm->get_tx_allowance(cc), 308 cwnd_size, 309 cur_bytes, 310 s->total_acked, 311 s->total_lost, 312 s->capacity, 313 s->spare_capacity, 314 (char)state); 315 #endif 316 317 return 1; 318 } 319 320 /* 321 * Simulation Test 322 * =============== 323 * 324 * Simulator-based unit test in which we simulate a network with a certain 325 * capacity. The average estimated channel capacity should not be too far from 326 * the actual channel capacity. 327 */ 328 static int test_simulate(void) 329 { 330 int testresult = 0; 331 int rc; 332 int have_sim = 0; 333 const OSSL_CC_METHOD *ccm = &ossl_cc_newreno_method; 334 OSSL_CC_DATA *cc = NULL; 335 size_t mdpl = 1472; 336 uint64_t total_sent = 0, total_to_send, allowance; 337 uint64_t actual_capacity = 16000; /* B/s - 128kb/s */ 338 uint64_t cwnd_sample_sum = 0, cwnd_sample_count = 0; 339 uint64_t diag_cur_bytes_in_flight = UINT64_MAX; 340 uint64_t diag_cur_cwnd_size = UINT64_MAX; 341 struct net_sim sim; 342 OSSL_PARAM params[3], *p = params; 343 344 fake_time = TIME_BASE; 345 346 if (!TEST_ptr(cc = ccm->new(fake_now, NULL))) 347 goto err; 348 349 if (!TEST_true(net_sim_init(&sim, ccm, cc, actual_capacity, 100))) 350 goto err; 351 352 have_sim = 1; 353 354 *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN, 355 &mdpl); 356 *p++ = OSSL_PARAM_construct_end(); 357 358 if (!TEST_true(ccm->set_input_params(cc, params))) 359 goto err; 360 361 p = params; 362 *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT, 363 &diag_cur_bytes_in_flight); 364 *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_CWND_SIZE, 365 &diag_cur_cwnd_size); 366 *p++ = OSSL_PARAM_construct_end(); 367 368 if (!TEST_true(ccm->bind_diagnostics(cc, params))) 369 goto err; 370 371 ccm->reset(cc); 372 373 if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), mdpl)) 374 goto err; 375 376 /* 377 * Start generating traffic. Stop when we've sent 30 MiB. 378 */ 379 total_to_send = 30 * 1024 * 1024; 380 381 while (total_sent < total_to_send) { 382 /* 383 * Assume we are bottlenecked by the network (which is the interesting 384 * case for testing a congestion controller) and always fill our entire 385 * TX allowance as and when it becomes available. 386 */ 387 for (;;) { 388 uint64_t sz; 389 390 dump_state(ccm, cc, &sim); 391 392 allowance = ccm->get_tx_allowance(cc); 393 sz = allowance > mdpl ? mdpl : allowance; 394 if (sz > SIZE_MAX) 395 sz = SIZE_MAX; 396 397 /* 398 * QUIC minimum packet sizes, etc. mean that in practice we will not 399 * consume the allowance exactly, so only send above a certain size. 400 */ 401 if (sz < 30) 402 break; 403 404 step_time(7); 405 406 if (!TEST_true(net_sim_send(&sim, (size_t)sz))) 407 goto err; 408 409 total_sent += sz; 410 } 411 412 /* Skip to next event. */ 413 rc = net_sim_process(&sim, 1); 414 if (!TEST_int_gt(rc, 0)) 415 goto err; 416 417 /* 418 * If we are out of any events to handle at all we definitely should 419 * have at least one MDPL's worth of allowance as nothing is in flight. 420 */ 421 if (rc == 3) { 422 if (!TEST_uint64_t_eq(diag_cur_bytes_in_flight, 0)) 423 goto err; 424 425 if (!TEST_uint64_t_ge(ccm->get_tx_allowance(cc), mdpl)) 426 goto err; 427 } 428 429 /* Update our average of the estimated channel capacity. */ 430 { 431 uint64_t v = 1; 432 433 if (!TEST_uint64_t_ne(diag_cur_bytes_in_flight, UINT64_MAX) 434 || !TEST_uint64_t_ne(diag_cur_cwnd_size, UINT64_MAX)) 435 goto err; 436 437 cwnd_sample_sum += v; 438 ++cwnd_sample_count; 439 } 440 } 441 442 /* 443 * Ensure estimated channel capacity is not too far off from actual channel 444 * capacity. 445 */ 446 { 447 uint64_t estimated_capacity = cwnd_sample_sum / cwnd_sample_count; 448 449 double error = ((double)estimated_capacity / (double)actual_capacity) - 1.0; 450 451 TEST_info("est = %6llu kB/s, act=%6llu kB/s (error=%.02f%%)\n", 452 (unsigned long long)estimated_capacity, 453 (unsigned long long)actual_capacity, 454 error * 100.0); 455 456 /* Max 5% error */ 457 if (!TEST_double_le(error, 0.05)) 458 goto err; 459 } 460 461 testresult = 1; 462 err: 463 if (have_sim) 464 net_sim_cleanup(&sim); 465 466 if (cc != NULL) 467 ccm->free(cc); 468 469 #ifdef GENERATE_LOG 470 if (logfile != NULL) 471 fflush(logfile); 472 #endif 473 474 return testresult; 475 } 476 477 /* 478 * Sanity Test 479 * =========== 480 * 481 * Basic test of the congestion control APIs. 482 */ 483 static int test_sanity(void) 484 { 485 int testresult = 0; 486 OSSL_CC_DATA *cc = NULL; 487 const OSSL_CC_METHOD *ccm = &ossl_cc_newreno_method; 488 OSSL_CC_LOSS_INFO loss_info = {0}; 489 OSSL_CC_ACK_INFO ack_info = {0}; 490 uint64_t allowance, allowance2; 491 OSSL_PARAM params[3], *p = params; 492 size_t mdpl = 1472, diag_mdpl = SIZE_MAX; 493 uint64_t diag_cur_bytes_in_flight = UINT64_MAX; 494 495 fake_time = TIME_BASE; 496 497 if (!TEST_ptr(cc = ccm->new(fake_now, NULL))) 498 goto err; 499 500 /* Test configuration of options. */ 501 *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN, 502 &mdpl); 503 *p++ = OSSL_PARAM_construct_end(); 504 505 if (!TEST_true(ccm->set_input_params(cc, params))) 506 goto err; 507 508 ccm->reset(cc); 509 510 p = params; 511 *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN, 512 &diag_mdpl); 513 *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT, 514 &diag_cur_bytes_in_flight); 515 *p++ = OSSL_PARAM_construct_end(); 516 517 if (!TEST_true(ccm->bind_diagnostics(cc, params)) 518 || !TEST_size_t_eq(diag_mdpl, 1472)) 519 goto err; 520 521 if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), 1472)) 522 goto err; 523 524 /* There is TX allowance so wakeup should be immediate */ 525 if (!TEST_true(ossl_time_is_zero(ccm->get_wakeup_deadline(cc)))) 526 goto err; 527 528 /* No bytes should currently be in flight. */ 529 if (!TEST_uint64_t_eq(diag_cur_bytes_in_flight, 0)) 530 goto err; 531 532 /* Tell the CC we have sent some data. */ 533 if (!TEST_true(ccm->on_data_sent(cc, 1200))) 534 goto err; 535 536 /* Allowance should have decreased. */ 537 if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance - 1200)) 538 goto err; 539 540 /* Acknowledge the data. */ 541 ack_info.tx_time = fake_time; 542 ack_info.tx_size = 1200; 543 step_time(100); 544 if (!TEST_true(ccm->on_data_acked(cc, &ack_info))) 545 goto err; 546 547 /* Allowance should have returned. */ 548 if (!TEST_uint64_t_ge(allowance2 = ccm->get_tx_allowance(cc), allowance)) 549 goto err; 550 551 /* Test invalidation. */ 552 if (!TEST_true(ccm->on_data_sent(cc, 1200))) 553 goto err; 554 555 /* Allowance should have decreased. */ 556 if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance - 1200)) 557 goto err; 558 559 if (!TEST_true(ccm->on_data_invalidated(cc, 1200))) 560 goto err; 561 562 /* Allowance should have returned. */ 563 if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance2)) 564 goto err; 565 566 /* Test loss. */ 567 if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), 1200 + 1300)) 568 goto err; 569 570 if (!TEST_true(ccm->on_data_sent(cc, 1200))) 571 goto err; 572 573 if (!TEST_true(ccm->on_data_sent(cc, 1300))) 574 goto err; 575 576 if (!TEST_uint64_t_eq(allowance2 = ccm->get_tx_allowance(cc), 577 allowance - 1200 - 1300)) 578 goto err; 579 580 loss_info.tx_time = fake_time; 581 loss_info.tx_size = 1200; 582 step_time(100); 583 584 if (!TEST_true(ccm->on_data_lost(cc, &loss_info))) 585 goto err; 586 587 loss_info.tx_size = 1300; 588 if (!TEST_true(ccm->on_data_lost(cc, &loss_info))) 589 goto err; 590 591 if (!TEST_true(ccm->on_data_lost_finished(cc, 0))) 592 goto err; 593 594 /* Allowance should have changed due to the lost calls */ 595 if (!TEST_uint64_t_ne(ccm->get_tx_allowance(cc), allowance2)) 596 goto err; 597 598 /* But it should not be as high as the original value */ 599 if (!TEST_uint64_t_lt(ccm->get_tx_allowance(cc), allowance)) 600 goto err; 601 602 testresult = 1; 603 604 err: 605 if (cc != NULL) 606 ccm->free(cc); 607 608 return testresult; 609 } 610 611 int setup_tests(void) 612 { 613 614 #ifdef GENERATE_LOG 615 logfile = fopen("quic_cc_stats.csv", "w"); 616 fprintf(logfile, 617 "\"Time\"," 618 "\"TX Allowance\"," 619 "\"CWND Size\"," 620 "\"Bytes in Flight\"," 621 "\"Total Acked\",\"Total Lost\"," 622 "\"Capacity\",\"Spare Capacity\"," 623 "\"State\"\n"); 624 #endif 625 626 ADD_TEST(test_simulate); 627 ADD_TEST(test_sanity); 628 return 1; 629 } 630