QUIC Congestion Control: Tests

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/20423)

3 files changed, 628 insertions, 1 deletions

diff --git a/test/build.info b/test/build.info
index 4599770106..b3588040c2 100644
--- a/test/build.info
+++ b/test/build.info
@@ -1088,13 +1088,17 @@ ENDIF
     PROGRAMS{noinst}=quic_wire_test quic_ackm_test quic_record_test
     PROGRAMS{noinst}=quic_fc_test quic_stream_test quic_cfq_test quic_txpim_test
     PROGRAMS{noinst}=quic_fifd_test quic_txp_test quic_tserver_test
-    PROGRAMS{noinst}=quic_client_test
+    PROGRAMS{noinst}=quic_client_test quic_cc_test
   ENDIF
 
   SOURCE[quic_ackm_test]=quic_ackm_test.c
   INCLUDE[quic_ackm_test]=../include ../apps/include
   DEPEND[quic_ackm_test]=../libcrypto.a ../libssl.a libtestutil.a
 
+  SOURCE[quic_cc_test]=quic_cc_test.c
+  INCLUDE[quic_cc_test]=../include ../apps/include
+  DEPEND[quic_cc_test]=../libcrypto.a ../libssl.a libtestutil.a
+
   SOURCE[cert_comp_test]=cert_comp_test.c helpers/ssltestlib.c
   INCLUDE[cert_comp_test]=../include ../apps/include ..
   DEPEND[cert_comp_test]=../libcrypto ../libssl libtestutil.a
diff --git a/test/quic_cc_test.c b/test/quic_cc_test.c
new file mode 100644
index 0000000000..e3e5e87d38
--- /dev/null
+++ b/test/quic_cc_test.c
@@ -0,0 +1,604 @@
+/*
+ * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+/* For generating debug statistics during congestion controller development. */
+/*#define GENERATE_LOG*/
+
+#include "testutil.h"
+#include <openssl/ssl.h>
+#include "internal/quic_cc.h"
+#include "internal/priority_queue.h"
+
+/*
+ * Time Simulation
+ * ===============
+ */
+static OSSL_TIME fake_time = {0};
+
+#define TIME_BASE (ossl_ticks2time(5 * OSSL_TIME_SECOND))
+
+static OSSL_TIME fake_now(void *arg)
+{
+    return fake_time;
+}
+
+static void step_time(uint32_t ms)
+{
+    fake_time = ossl_time_add(fake_time, ossl_ms2time(ms));
+}
+
+/*
+ * Network Simulation
+ * ==================
+ *
+ * This is a simple 'network simulator' which emulates a network with a certain
+ * bandwidth and latency. Sending a packet into the network causes it to consume
+ * some capacity of the network until the packet exits the network. Note that
+ * the capacity is not known to the congestion controller as the entire point of
+ * a congestion controller is to correctly estimate this capacity and this is
+ * what we are testing. The network simulator does take care of informing the
+ * congestion controller of ack/loss events automatically but the caller is
+ * responsible for querying the congestion controller and choosing the size of
+ * simulated transmitted packets.
+ */
+typedef struct net_pkt_st {
+    /*
+     * The time at which the packet was sent.
+     */
+    OSSL_TIME   tx_time;
+
+    /*
+     * The time at which the simulated packet arrives at the RX side (success)
+     * or is dropped (!success).
+     */
+    OSSL_TIME   arrive_time;
+
+    /*
+     * The time at which the transmitting side makes a determination of
+     * acknowledgement (if success) or loss (if !success).
+     */
+    OSSL_TIME   determination_time;
+
+    /*
+     * Current earliest time there is something to be done for this packet.
+     * min(arrive_time, determination_time).
+     */
+    OSSL_TIME   next_time;
+
+    /* 1 if the packet will be successfully delivered, 0 if it is to be lost. */
+    int         success;
+
+    /* 1 if we have already processed packet arrival. */
+    int         arrived;
+
+    /* Size of simulated packet in bytes. */
+    size_t      size;
+
+    /* pqueue internal index. */
+    size_t      idx;
+} NET_PKT;
+
+DEFINE_PRIORITY_QUEUE_OF(NET_PKT);
+
+static int net_pkt_cmp(const NET_PKT *a, const NET_PKT *b)
+{
+    return ossl_time_compare(a->next_time, b->next_time);
+}
+
+struct net_sim {
+    const OSSL_CC_METHOD *ccm;
+    OSSL_CC_DATA         *cc;
+
+    uint64_t capacity; /* bytes/s */
+    uint64_t latency;  /* ms */
+
+    uint64_t spare_capacity;
+    PRIORITY_QUEUE_OF(NET_PKT) *pkts;
+
+    uint64_t total_acked, total_lost; /* bytes */
+};
+
+static int net_sim_init(struct net_sim *s,
+                        const OSSL_CC_METHOD *ccm, OSSL_CC_DATA *cc,
+                        uint64_t capacity, uint64_t latency)
+{
+    s->ccm              = ccm;
+    s->cc               = cc;
+
+    s->capacity         = capacity;
+    s->latency          = latency;
+
+    s->spare_capacity   = capacity;
+
+    s->total_acked      = 0;
+    s->total_lost       = 0;
+
+    if (!TEST_ptr(s->pkts = ossl_pqueue_NET_PKT_new(net_pkt_cmp)))
+        return 0;
+
+    return 1;
+}
+
+static void net_sim_cleanup(struct net_sim *s)
+{
+    NET_PKT *pkt;
+
+    while ((pkt = ossl_pqueue_NET_PKT_pop(s->pkts)) != NULL)
+        OPENSSL_free(pkt);
+
+    ossl_pqueue_NET_PKT_free(s->pkts);
+}
+
+static int net_sim_process(struct net_sim *s, size_t skip_forward);
+
+static int net_sim_send(struct net_sim *s, size_t sz)
+{
+    NET_PKT *pkt = OPENSSL_zalloc(sizeof(*pkt));
+    int success;
+
+    if (!TEST_ptr(pkt))
+        return 0;
+
+    /*
+     * Ensure we have processed any events which have come due as these might
+     * increase our spare capacity.
+     */
+    if (!TEST_true(net_sim_process(s, 0)))
+        return 0;
+
+    /* Do we have room for the packet in the network? */
+    success = (sz <= s->spare_capacity);
+
+    pkt->tx_time = fake_time;
+    pkt->success = success;
+    if (success) {
+        /* This packet will arrive successfully after |latency| time. */
+        pkt->arrive_time        = ossl_time_add(pkt->tx_time,
+                                                ossl_ms2time(s->latency));
+        /* Assume all received packets are acknowledged immediately. */
+        pkt->determination_time = ossl_time_add(pkt->arrive_time,
+                                                ossl_ms2time(s->latency));
+        pkt->next_time          = pkt->arrive_time;
+        s->spare_capacity      -= sz;
+    } else {
+        /*
+         * In our network model, assume all packets are dropped due to a
+         * bottleneck at the peer's NIC RX queue; thus dropping occurs after
+         * |latency|.
+         */
+        pkt->arrive_time        = ossl_time_add(pkt->tx_time,
+                                                ossl_ms2time(s->latency));
+        /*
+         * It will take longer to detect loss than to detect acknowledgement.
+         */
+        pkt->determination_time = ossl_time_add(pkt->tx_time,
+                                                ossl_ms2time(3 * s->latency));
+        pkt->next_time          = pkt->determination_time;
+    }
+
+    pkt->size = sz;
+
+    if (!TEST_true(s->ccm->on_data_sent(s->cc, sz)))
+        return 0;
+
+    if (!TEST_true(ossl_pqueue_NET_PKT_push(s->pkts, pkt, &pkt->idx)))
+        return 0;
+
+    return 1;
+}
+
+static int net_sim_process_one(struct net_sim *s, int skip_forward)
+{
+    NET_PKT *pkt = ossl_pqueue_NET_PKT_peek(s->pkts);
+
+    if (pkt == NULL)
+        return 3;
+
+    /* Jump forward to the next significant point in time. */
+    if (skip_forward && ossl_time_compare(pkt->next_time, fake_time) > 0)
+        fake_time = pkt->next_time;
+
+    if (pkt->success && !pkt->arrived
+        && ossl_time_compare(fake_time, pkt->arrive_time) >= 0) {
+        /* Packet arrives */
+        s->spare_capacity += pkt->size;
+        pkt->arrived = 1;
+
+        ossl_pqueue_NET_PKT_pop(s->pkts);
+        pkt->next_time = pkt->determination_time;
+        if (!ossl_pqueue_NET_PKT_push(s->pkts, pkt, &pkt->idx))
+            return 0;
+
+        return 1;
+    }
+
+    if (ossl_time_compare(fake_time, pkt->determination_time) < 0)
+        return 2;
+
+    if (!ossl_assert(!pkt->success || pkt->arrived))
+        return 0;
+
+    if (!pkt->success) {
+        OSSL_CC_LOSS_INFO loss_info = {0};
+
+        loss_info.tx_time = pkt->tx_time;
+        loss_info.tx_size = pkt->size;
+
+        if (!TEST_true(s->ccm->on_data_lost(s->cc, &loss_info)))
+            return 0;
+
+        if (!TEST_true(s->ccm->on_data_lost_finished(s->cc, 0)))
+            return 0;
+
+        s->total_lost += pkt->size;
+        ossl_pqueue_NET_PKT_pop(s->pkts);
+        OPENSSL_free(pkt);
+    } else {
+        OSSL_CC_ACK_INFO ack_info = {0};
+
+        ack_info.tx_time = pkt->tx_time;
+        ack_info.tx_size = pkt->size;
+
+        if (!TEST_true(s->ccm->on_data_acked(s->cc, &ack_info)))
+            return 0;
+
+        s->total_acked += pkt->size;
+        ossl_pqueue_NET_PKT_pop(s->pkts);
+        OPENSSL_free(pkt);
+    }
+
+    return 1;
+}
+
+static int net_sim_process(struct net_sim *s, size_t skip_forward)
+{
+    int rc;
+
+    while ((rc = net_sim_process_one(s, skip_forward > 0 ? 1 : 0)) == 1)
+        if (skip_forward > 0)
+            --skip_forward;
+
+    return rc;
+}
+
+/*
+ * State Dumping Utilities
+ * =======================
+ *
+ * Utilities for outputting CC state information.
+ */
+#ifdef GENERATE_LOG
+static FILE *logfile;
+#endif
+
+static int dump_state(const OSSL_CC_METHOD *ccm, OSSL_CC_DATA *cc,
+                                  struct net_sim *s)
+{
+#ifdef GENERATE_LOG
+    uint64_t cwnd_size, cur_bytes, state;
+
+    if (logfile == NULL)
+        return 1;
+
+    if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_CWND_SIZE,
+                                        &cwnd_size)))
+        return 0;
+
+    if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
+                                        &cur_bytes)))
+        return 0;
+
+    if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_STATE,
+                                        &state)))
+        return 0;
+
+    fprintf(logfile, "%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,%10lu,\"%c\"\n",
+            ossl_time2ms(fake_time),
+            ccm->get_tx_allowance(cc),
+            cwnd_size,
+            cur_bytes,
+            s->total_acked,
+            s->total_lost,
+            s->capacity,
+            s->spare_capacity,
+            (char)state);
+#endif
+
+    return 1;
+}
+
+/*
+ * Simulation Test
+ * ===============
+ *
+ * Simulator-based unit test in which we simulate a network with a certain
+ * capacity. The average estimated channel capacity should not be too far from
+ * the actual channel capacity.
+ */
+static int test_simulate(void)
+{
+    int testresult = 0;
+    int rc;
+    int have_sim = 0;
+    const OSSL_CC_METHOD *ccm = &ossl_cc_newreno_method;
+    OSSL_CC_DATA *cc = NULL;
+    uint64_t mdpl = 1472;
+    uint64_t total_sent = 0, total_to_send, allowance;
+    uint64_t actual_capacity = 16000; /* B/s - 128kb/s */
+    uint64_t cwnd_sample_sum = 0, cwnd_sample_count = 0;
+    struct net_sim sim;
+
+    fake_time = TIME_BASE;
+
+    if (!TEST_ptr(cc = ccm->new(fake_now, NULL)))
+        goto err;
+
+    if (!TEST_true(net_sim_init(&sim, ccm, cc, actual_capacity, 100)))
+        goto err;
+
+    have_sim = 1;
+
+    if (!TEST_true(ccm->set_option_uint(cc, OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
+                                        mdpl)))
+        goto err;
+
+    ccm->reset(cc);
+
+    if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), mdpl))
+        goto err;
+
+    /*
+     * Start generating traffic. Stop when we've sent 30 MiB.
+     */
+    total_to_send = 30 * 1024 * 1024;
+
+    while (total_sent < total_to_send) {
+        /*
+         * Assume we are bottlenecked by the network (which is the interesting
+         * case for testing a congestion controller) and always fill our entire
+         * TX allowance as and when it becomes available.
+         */
+        for (;;) {
+            uint64_t sz;
+
+            dump_state(ccm, cc, &sim);
+
+            allowance = ccm->get_tx_allowance(cc);
+            sz = allowance > mdpl ? mdpl : allowance;
+
+            /*
+             * QUIC minimum packet sizes, etc. mean that in practice we will not
+             * consume the allowance exactly, so only send above a certain size.
+             */
+            if (sz < 30)
+                break;
+
+            step_time(7);
+
+            if (!TEST_true(net_sim_send(&sim, sz)))
+                goto err;
+
+            total_sent += sz;
+        }
+
+        /* Skip to next event. */
+        rc = net_sim_process(&sim, 1);
+        if (!TEST_int_gt(rc, 0))
+            goto err;
+
+        /*
+         * If we are out of any events to handle at all we definitely should
+         * have at least one MDPL's worth of allowance as nothing is in flight.
+         */
+        if (rc == 3) {
+            uint64_t v = 1;
+
+            if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
+                                                &v)))
+                goto err;
+
+            if (!TEST_uint64_t_eq(v, 0))
+                goto err;
+
+            if (!TEST_uint64_t_ge(ccm->get_tx_allowance(cc), mdpl))
+                goto err;
+        }
+
+        /* Update our average of the estimated channel capacity. */
+        {
+            uint64_t v = 1;
+
+            if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_CWND_SIZE,
+                                                &v)))
+                goto err;
+
+            cwnd_sample_sum += v;
+            ++cwnd_sample_count;
+        }
+    }
+
+    /*
+     * Ensure estimated channel capacity is not too far off from actual channel
+     * capacity.
+     */
+    {
+        uint64_t estimated_capacity = cwnd_sample_sum / cwnd_sample_count;
+
+        double error = ((double)estimated_capacity / (double)actual_capacity) - 1.0;
+
+        TEST_info("est = %6lu kB/s, act=%6lu kB/s (error=%.02f%%)\n",
+                  estimated_capacity, actual_capacity, error * 100.0);
+
+        /* Max 5% error */
+        if (!TEST_double_le(error, 0.05))
+            goto err;
+    }
+
+    testresult = 1;
+err:
+    if (have_sim)
+        net_sim_cleanup(&sim);
+
+    if (cc != NULL)
+        ccm->free(cc);
+
+#ifdef GENERATE_LOG
+    if (logfile != NULL)
+        fflush(logfile);
+#endif
+
+    return testresult;
+}
+
+/*
+ * Sanity Test
+ * ===========
+ *
+ * Basic test of the congestion control APIs.
+ */
+static int test_sanity(void)
+{
+    int testresult = 0;
+    OSSL_CC_DATA *cc = NULL;
+    const OSSL_CC_METHOD *ccm = &ossl_cc_newreno_method;
+    OSSL_CC_LOSS_INFO loss_info = {0};
+    OSSL_CC_ACK_INFO ack_info = {0};
+    uint64_t allowance, allowance2, v = 1;
+
+    fake_time = TIME_BASE;
+
+    if (!TEST_ptr(cc = ccm->new(fake_now, NULL)))
+        goto err;
+
+    /* Test configuration of options. */
+    if (!TEST_true(ccm->set_option_uint(cc, OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
+                                        1472)))
+        goto err;
+
+    ccm->reset(cc);
+
+    if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
+                                        &v))
+        || !TEST_uint64_t_eq(v, 1472))
+        goto err;
+
+    if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), 1472))
+        goto err;
+
+    /*
+     * No wakeups should be scheduled currently as we don't currently implement
+     * pacing.
+     */
+    if (!TEST_true(ossl_time_is_infinite(ccm->get_wakeup_deadline(cc))))
+        goto err;
+
+    /* No bytes should currently be in flight. */
+    if (!TEST_true(ccm->get_option_uint(cc, OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
+                                        &v))
+        || !TEST_uint64_t_eq(v, 0))
+        goto err;
+
+    /* Tell the CC we have sent some data. */
+    if (!TEST_true(ccm->on_data_sent(cc, 1200)))
+        goto err;
+
+    /* Allowance should have decreased. */
+    if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance - 1200))
+        goto err;
+
+    /* Acknowledge the data. */
+    ack_info.tx_time = fake_time;
+    ack_info.tx_size = 1200;
+    step_time(100);
+    if (!TEST_true(ccm->on_data_acked(cc, &ack_info)))
+        goto err;
+
+    /* Allowance should have returned. */
+    if (!TEST_uint64_t_ge(allowance2 = ccm->get_tx_allowance(cc), allowance))
+        goto err;
+
+    /* Test invalidation. */
+    if (!TEST_true(ccm->on_data_sent(cc, 1200)))
+        goto err;
+
+    /* Allowance should have decreased. */
+    if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance - 1200))
+        goto err;
+
+    if (!TEST_true(ccm->on_data_invalidated(cc, 1200)))
+        goto err;
+
+    /* Allowance should have returned. */
+    if (!TEST_uint64_t_eq(ccm->get_tx_allowance(cc), allowance2))
+        goto err;
+
+    /* Test loss. */
+    if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), 1200 + 1300))
+        goto err;
+
+    if (!TEST_true(ccm->on_data_sent(cc, 1200)))
+        goto err;
+
+    if (!TEST_true(ccm->on_data_sent(cc, 1300)))
+        goto err;
+
+    if (!TEST_uint64_t_eq(allowance2 = ccm->get_tx_allowance(cc),
+                          allowance - 1200 - 1300))
+        goto err;
+
+    loss_info.tx_time = fake_time;
+    loss_info.tx_size = 1200;
+    step_time(100);
+
+    if (!TEST_true(ccm->on_data_lost(cc, &loss_info)))
+        goto err;
+
+    loss_info.tx_size = 1300;
+    if (!TEST_true(ccm->on_data_lost(cc, &loss_info)))
+        goto err;
+
+    if (!TEST_true(ccm->on_data_lost_finished(cc, 0)))
+        goto err;
+
+    /* Allowance should have changed due to the lost calls */
+    if (!TEST_uint64_t_ne(ccm->get_tx_allowance(cc), allowance2))
+        goto err;
+
+    /* But it should not be as high as the origina value */
+    if (!TEST_uint64_t_lt(ccm->get_tx_allowance(cc), allowance))
+        goto err;
+
+    testresult = 1;
+
+err:
+    if (cc != NULL)
+        ccm->free(cc);
+
+    return testresult;
+}
+
+int setup_tests(void)
+{
+
+#ifdef GENERATE_LOG
+    logfile = fopen("quic_cc_stats.csv", "w");
+    fprintf(logfile,
+        "\"Time\","
+        "\"TX Allowance\","
+        "\"CWND Size\","
+        "\"Bytes in Flight\","
+        "\"Total Acked\",\"Total Lost\","
+        "\"Capacity\",\"Spare Capacity\","
+        "\"State\"\n");
+#endif
+
+    ADD_TEST(test_simulate);
+    ADD_TEST(test_sanity);
+    return 1;
+}
diff --git a/test/recipes/75-test_quic_cc.t b/test/recipes/75-test_quic_cc.t
new file mode 100644
index 0000000000..97f4151779
--- /dev/null
+++ b/test/recipes/75-test_quic_cc.t
@@ -0,0 +1,19 @@
+#! /usr/bin/env perl
+# Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
+#
+# Licensed under the Apache License 2.0 (the "License").  You may not use
+# this file except in compliance with the License.  You can obtain a copy
+# in the file LICENSE in the source distribution or at
+# https://www.openssl.org/source/license.html
+
+use OpenSSL::Test;
+use OpenSSL::Test::Utils;
+
+setup("test_quic_cc");
+
+plan skip_all => "QUIC protocol is not supported by this OpenSSL build"
+    if disabled('quic');
+
+plan tests => 1;
+
+ok(run(test(["quic_cc_test"])));