quic_cc_test.c

/*
 * Copyright 2022-2023 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 do_free(NET_PKT *pkt)
{
    OPENSSL_free(pkt);
}

static void net_sim_cleanup(struct net_sim *s)
{
    ossl_pqueue_NET_PKT_pop_free(s->pkts, do_free);
}

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 (!TEST_true(!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;
    size_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;
    uint64_t diag_cur_bytes_in_flight = UINT64_MAX;
    uint64_t diag_cur_cwnd_size = UINT64_MAX;
    struct net_sim sim;
    OSSL_PARAM params[3], *p = params;

    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;

    *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
                                       &mdpl);
    *p++ = OSSL_PARAM_construct_end();

    if (!TEST_true(ccm->set_input_params(cc, params)))
        goto err;

    p = params;
    *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
                                       &diag_cur_bytes_in_flight);
    *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_CWND_SIZE,
                                       &diag_cur_cwnd_size);
    *p++ = OSSL_PARAM_construct_end();

    if (!TEST_true(ccm->bind_diagnostics(cc, params)))
        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;
            if (sz > SIZE_MAX)
                sz = SIZE_MAX;

            /*
             * 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, (size_t)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) {
            if (!TEST_uint64_t_eq(diag_cur_bytes_in_flight, 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_uint64_t_ne(diag_cur_bytes_in_flight, UINT64_MAX)
                || !TEST_uint64_t_ne(diag_cur_cwnd_size, UINT64_MAX))
                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 = %6llu kB/s, act=%6llu kB/s (error=%.02f%%)\n",
                  (unsigned long long)estimated_capacity,
                  (unsigned long long)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;
    OSSL_PARAM params[3], *p = params;
    size_t mdpl = 1472, diag_mdpl = SIZE_MAX;
    uint64_t diag_cur_bytes_in_flight = UINT64_MAX;

    fake_time = TIME_BASE;

    if (!TEST_ptr(cc = ccm->new(fake_now, NULL)))
        goto err;

    /* Test configuration of options. */
    *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
                                       &mdpl);
    *p++ = OSSL_PARAM_construct_end();

    if (!TEST_true(ccm->set_input_params(cc, params)))
        goto err;

    ccm->reset(cc);

    p = params;
    *p++ = OSSL_PARAM_construct_size_t(OSSL_CC_OPTION_MAX_DGRAM_PAYLOAD_LEN,
                                       &diag_mdpl);
    *p++ = OSSL_PARAM_construct_uint64(OSSL_CC_OPTION_CUR_BYTES_IN_FLIGHT,
                                       &diag_cur_bytes_in_flight);
    *p++ = OSSL_PARAM_construct_end();

    if (!TEST_true(ccm->bind_diagnostics(cc, params))
        || !TEST_size_t_eq(diag_mdpl, 1472))
        goto err;

    if (!TEST_uint64_t_ge(allowance = ccm->get_tx_allowance(cc), 1472))
        goto err;

    /* There is TX allowance so wakeup should be immediate */
    if (!TEST_true(ossl_time_is_zero(ccm->get_wakeup_deadline(cc))))
        goto err;

    /* No bytes should currently be in flight. */
    if (!TEST_uint64_t_eq(diag_cur_bytes_in_flight, 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 original 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;
}