test/quic_cc_test.c

   1 /*
   2  * Copyright 2022 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         return 0;
 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         return 0;
 189
 190     if (!TEST_true(ossl_pqueue_NET_PKT_push(s->pkts, pkt, &pkt->idx)))
 191         return 0;
 192
 193     return 1;
 194 }
 195
 196 static int net_sim_process_one(struct net_sim *s, int skip_forward)
 197 {
 198     NET_PKT *pkt = ossl_pqueue_NET_PKT_peek(s->pkts);
 199
 200     if (pkt == NULL)
 201         return 3;
 202
 203     /* Jump forward to the next significant point in time. */
 204     if (skip_forward && ossl_time_compare(pkt->next_time, fake_time) > 0)
 205         fake_time = pkt->next_time;
 206
 207     if (pkt->success && !pkt->arrived
 208         && ossl_time_compare(fake_time, pkt->arrive_time) >= 0) {
 209         /* Packet arrives */
 210         s->spare_capacity += pkt->size;
 211         pkt->arrived = 1;
 212
 213         ossl_pqueue_NET_PKT_pop(s->pkts);
 214         pkt->next_time = pkt->determination_time;
 215         if (!ossl_pqueue_NET_PKT_push(s->pkts, pkt, &pkt->idx))
 216             return 0;
 217
 218         return 1;
 219     }
 220
 221     if (ossl_time_compare(fake_time, pkt->determination_time) < 0)
 222         return 2;
 223
 224     if (!TEST_true(!pkt->success || pkt->arrived))
 225         return 0;
 226
 227     if (!pkt->success) {
 228         OSSL_CC_LOSS_INFO loss_info = {0};
 229
 230         loss_info.tx_time = pkt->tx_time;
 231         loss_info.tx_size = pkt->size;
 232
 233         if (!TEST_true(s->ccm->on_data_lost(s->cc, &loss_info)))
 234             return 0;
 235
 236         if (!TEST_true(s->ccm->on_data_lost_finished(s->cc, 0)))
 237             return 0;
 238
 239         s->total_lost += pkt->size;
 240         ossl_pqueue_NET_PKT_pop(s->pkts);
 241         OPENSSL_free(pkt);
 242     } else {
 243         OSSL_CC_ACK_INFO ack_info = {0};
 244
 245         ack_info.tx_time = pkt->tx_time;
 246         ack_info.tx_size = pkt->size;
 247
 248         if (!TEST_true(s->ccm->on_data_acked(s->cc, &ack_info)))
 249             return 0;
 250
 251         s->total_acked += pkt->size;
 252         ossl_pqueue_NET_PKT_pop(s->pkts);
 253         OPENSSL_free(pkt);
 254     }
 255
 256     return 1;
 257 }
 258
 259 static int net_sim_process(struct net_sim *s, size_t skip_forward)
 260 {
 261     int rc;
 262
 263     while ((rc = net_sim_process_one(s, skip_forward > 0 ? 1 : 0)) == 1)
 264         if (skip_forward > 0)
 265             --skip_forward;
 266
 267     return rc;
 268 }
 269
 270 /*
 271  * State Dumping Utilities
 272  * =======================
 273  *
 274  * Utilities for outputting CC state information.
 275  */
 276 #ifdef GENERATE_LOG
 277 static FILE *logfile;
 278 #endif
 279
 280 static int dump_state(const OSSL_CC_METHOD *ccm, OSSL_CC_DATA *cc,
 281                                   struct net_sim *s)
 282 {
 283 #ifdef GENERATE_LOG
 284     uint64_t cwnd_size, cur_bytes, state;
 285
 286     if (logfile == NULL)
 287         return 1;
 288
 289     if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_CWND_SIZE,
 290                                         &cwnd_size)))
 291         return 0;
 292
 293     if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
 294                                         &cur_bytes)))
 295         return 0;
 296
 297     if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_STATE,
 298                                         &state)))
 299         return 0;
 300
 301     fprintf(logfile, "%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,\"%c\"\n",
 302             ossl_time2ms(fake_time),
 303             ccm->get_tx_allowance(cc),
 304             cwnd_size,
 305             cur_bytes,
 306             s->total_acked,
 307             s->total_lost,
 308             s->capacity,
 309             s->spare_capacity,
 310             (char)state);
 311 #endif
 312
 313     return 1;
 314 }
 315
 316 /*
 317  * Simulation Test
 318  * ===============
 319  *
 320  * Simulator-based unit test in which we simulate a network with a certain
 321  * capacity. The average estimated channel capacity should not be too far from
 322  * the actual channel capacity.
 323  */
 324 static int test_simulate(void)
 325 {
 326     int testresult = 0;
 327     int rc;
 328     int have_sim = 0;
 329     const OSSL_CC_METHOD *ccm = &ossl_cc_newreno_method;
 330     OSSL_CC_DATA *cc = NULL;
 331     size_t mdpl = 1472;
 332     uint64_t total_sent = 0, total_to_send, allowance;
 333     uint64_t actual_capacity = 16000; /* B/s - 128kb/s */
 334     uint64_t cwnd_sample_sum = 0, cwnd_sample_count = 0;
 335     uint64_t diag_cur_bytes_in_flight = UINT64_MAX;
 336     uint64_t diag_cur_cwnd_size = UINT64_MAX;
 337     struct net_sim sim;
 338     OSSL_PARAM params[3], *p = params;
 339
 340     fake_time = TIME_BASE;
 341
 342     if (!TEST_ptr(cc = ccm->new(fake_now, NULL)))
 343         goto err;
 344
 345     if (!TEST_true(net_sim_init(&sim, ccm, cc, actual_capacity, 100)))
 346         goto err;
 347
 348     have_sim = 1;
 349
 350     *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
 351                                        &mdpl);
 352     *p++ = OSSL_PARAM_construct_end();
 353
 354     if (!TEST_true(ccm->set_input_params(cc, params)))
 355         goto err;
 356
 357     p = params;
 358     *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
 359                                        &diag_cur_bytes_in_flight);
 360     *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_CWND_SIZE,
 361                                        &diag_cur_cwnd_size);
 362     *p++ = OSSL_PARAM_construct_end();
 363
 364     if (!TEST_true(ccm->bind_diagnostics(cc, params)))
 365         goto err;
 366
 367     ccm->reset(cc);
 368
 369     if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), mdpl))
 370         goto err;
 371
 372     /*
 373      * Start generating traffic. Stop when we've sent 30 MiB.
 374      */
 375     total_to_send = 30 * 1024 * 1024;
 376
 377     while (total_sent < total_to_send) {
 378         /*
 379          * Assume we are bottlenecked by the network (which is the interesting
 380          * case for testing a congestion controller) and always fill our entire
 381          * TX allowance as and when it becomes available.
 382          */
 383         for (;;) {
 384             uint64_t sz;
 385
 386             dump_state(ccm, cc, &sim);
 387
 388             allowance = ccm->get_tx_allowance(cc);
 389             sz = allowance > mdpl ? mdpl : allowance;
 390             if (sz > SIZE_MAX)
 391                 sz = SIZE_MAX;
 392
 393             /*
 394              * QUIC minimum packet sizes, etc. mean that in practice we will not
 395              * consume the allowance exactly, so only send above a certain size.
 396              */
 397             if (sz < 30)
 398                 break;
 399
 400             step_time(7);
 401
 402             if (!TEST_true(net_sim_send(&sim, (size_t)sz)))
 403                 goto err;
 404
 405             total_sent += sz;
 406         }
 407
 408         /* Skip to next event. */
 409         rc = net_sim_process(&sim, 1);
 410         if (!TEST_int_gt(rc, 0))
 411             goto err;
 412
 413         /*
 414          * If we are out of any events to handle at all we definitely should
 415          * have at least one MDPL's worth of allowance as nothing is in flight.
 416          */
 417         if (rc == 3) {
 418             if (!TEST_uint64_t_eq(diag_cur_bytes_in_flight, 0))
 419                 goto err;
 420
 421             if (!TEST_uint64_t_ge(ccm->get_tx_allowance(cc), mdpl))
 422                 goto err;
 423         }
 424
 425         /* Update our average of the estimated channel capacity. */
 426         {
 427             uint64_t v = 1;
 428
 429             if (!TEST_uint64_t_ne(diag_cur_bytes_in_flight, UINT64_MAX)
 430                 || !TEST_uint64_t_ne(diag_cur_cwnd_size, UINT64_MAX))
 431                 goto err;
 432
 433             cwnd_sample_sum += v;
 434             ++cwnd_sample_count;
 435         }
 436     }
 437
 438     /*
 439      * Ensure estimated channel capacity is not too far off from actual channel
 440      * capacity.
 441      */
 442     {
 443         uint64_t estimated_capacity = cwnd_sample_sum / cwnd_sample_count;
 444
 445         double error = ((double)estimated_capacity / (double)actual_capacity) - 1.0;
 446
 447         TEST_info("est = %6lu kB/s, act=%6lu kB/s (error=%.02f%%)\n",
 448                   estimated_capacity, actual_capacity, error * 100.0);
 449
 450         /* Max 5% error */
 451         if (!TEST_double_le(error, 0.05))
 452             goto err;
 453     }
 454
 455     testresult = 1;
 456 err:
 457     if (have_sim)
 458         net_sim_cleanup(&sim);
 459
 460     if (cc != NULL)
 461         ccm->free(cc);
 462
 463 #ifdef GENERATE_LOG
 464     if (logfile != NULL)
 465         fflush(logfile);
 466 #endif
 467
 468     return testresult;
 469 }
 470
 471 /*
 472  * Sanity Test
 473  * ===========
 474  *
 475  * Basic test of the congestion control APIs.
 476  */
 477 static int test_sanity(void)
 478 {
 479     int testresult = 0;
 480     OSSL_CC_DATA *cc = NULL;
 481     const OSSL_CC_METHOD *ccm = &ossl_cc_newreno_method;
 482     OSSL_CC_LOSS_INFO loss_info = {0};
 483     OSSL_CC_ACK_INFO ack_info = {0};
 484     uint64_t allowance, allowance2;
 485     OSSL_PARAM params[3], *p = params;
 486     size_t mdpl = 1472, diag_mdpl = SIZE_MAX;
 487     uint64_t diag_cur_bytes_in_flight = UINT64_MAX;
 488
 489     fake_time = TIME_BASE;
 490
 491     if (!TEST_ptr(cc = ccm->new(fake_now, NULL)))
 492         goto err;
 493
 494     /* Test configuration of options. */
 495     *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
 496                                        &mdpl);
 497     *p++ = OSSL_PARAM_construct_end();
 498
 499     if (!TEST_true(ccm->set_input_params(cc, params)))
 500         goto err;
 501
 502     ccm->reset(cc);
 503
 504     p = params;
 505     *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
 506                                        &diag_mdpl);
 507     *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
 508                                        &diag_cur_bytes_in_flight);
 509     *p++ = OSSL_PARAM_construct_end();
 510
 511     if (!TEST_true(ccm->bind_diagnostics(cc, params))
 512         || !TEST_size_t_eq(diag_mdpl, 1472))
 513         goto err;
 514
 515     if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), 1472))
 516         goto err;
 517
 518     /*
 519      * No wakeups should be scheduled currently as we don't currently implement
 520      * pacing.
 521      */
 522     if (!TEST_true(ossl_time_is_infinite(ccm->get_wakeup_deadline(cc))))
 523         goto err;
 524
 525     /* No bytes should currently be in flight. */
 526     if (!TEST_uint64_t_eq(diag_cur_bytes_in_flight, 0))
 527         goto err;
 528
 529     /* Tell the CC we have sent some data. */
 530     if (!TEST_true(ccm->on_data_sent(cc, 1200)))
 531         goto err;
 532
 533     /* Allowance should have decreased. */
 534     if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance - 1200))
 535         goto err;
 536
 537     /* Acknowledge the data. */
 538     ack_info.tx_time = fake_time;
 539     ack_info.tx_size = 1200;
 540     step_time(100);
 541     if (!TEST_true(ccm->on_data_acked(cc, &ack_info)))
 542         goto err;
 543
 544     /* Allowance should have returned. */
 545     if (!TEST_uint64_t_ge(allowance2 = ccm->get_tx_allowance(cc), allowance))
 546         goto err;
 547
 548     /* Test invalidation. */
 549     if (!TEST_true(ccm->on_data_sent(cc, 1200)))
 550         goto err;
 551
 552     /* Allowance should have decreased. */
 553     if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance - 1200))
 554         goto err;
 555
 556     if (!TEST_true(ccm->on_data_invalidated(cc, 1200)))
 557         goto err;
 558
 559     /* Allowance should have returned. */
 560     if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance2))
 561         goto err;
 562
 563     /* Test loss. */
 564     if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), 1200 + 1300))
 565         goto err;
 566
 567     if (!TEST_true(ccm->on_data_sent(cc, 1200)))
 568         goto err;
 569
 570     if (!TEST_true(ccm->on_data_sent(cc, 1300)))
 571         goto err;
 572
 573     if (!TEST_uint64_t_eq(allowance2 = ccm->get_tx_allowance(cc),
 574                           allowance - 1200 - 1300))
 575         goto err;
 576
 577     loss_info.tx_time = fake_time;
 578     loss_info.tx_size = 1200;
 579     step_time(100);
 580
 581     if (!TEST_true(ccm->on_data_lost(cc, &loss_info)))
 582         goto err;
 583
 584     loss_info.tx_size = 1300;
 585     if (!TEST_true(ccm->on_data_lost(cc, &loss_info)))
 586         goto err;
 587
 588     if (!TEST_true(ccm->on_data_lost_finished(cc, 0)))
 589         goto err;
 590
 591     /* Allowance should have changed due to the lost calls */
 592     if (!TEST_uint64_t_ne(ccm->get_tx_allowance(cc), allowance2))
 593         goto err;
 594
 595     /* But it should not be as high as the original value */
 596     if (!TEST_uint64_t_lt(ccm->get_tx_allowance(cc), allowance))
 597         goto err;
 598
 599     testresult = 1;
 600
 601 err:
 602     if (cc != NULL)
 603         ccm->free(cc);
 604
 605     return testresult;
 606 }
 607
 608 int setup_tests(void)
 609 {
 610
 611 #ifdef GENERATE_LOG
 612     logfile = fopen("quic_cc_stats.csv", "w");
 613     fprintf(logfile,
 614         "\"Time\","
 615         "\"TX Allowance\","
 616         "\"CWND Size\","
 617         "\"Bytes in Flight\","
 618         "\"Total Acked\",\"Total Lost\","
 619         "\"Capacity\",\"Spare Capacity\","
 620         "\"State\"\n");
 621 #endif
 622
 623     ADD_TEST(test_simulate);
 624     ADD_TEST(test_sanity);
 625     return 1;
 626 }