test/quic_cc_test.c

   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 }