diff options
author | Hugo Landau <hlandau@openssl.org> | 2023-03-02 15:35:10 +0000 |
---|---|---|
committer | Matt Caswell <matt@openssl.org> | 2023-05-01 11:03:54 +0100 |
commit | ab11c165f6d9ba1b98c85d4c9d1a906de0fcd13c (patch) | |
tree | c527305ced9cf6c2341c0f31916648fe2e29f877 /test | |
parent | f68fd1cebcc8dfbd57e3c1c7afd2bf1a5b26cbe9 (diff) |
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)
Diffstat (limited to 'test')
-rw-r--r-- | test/build.info | 6 | ||||
-rw-r--r-- | test/quic_cc_test.c | 604 | ||||
-rw-r--r-- | test/recipes/75-test_quic_cc.t | 19 |
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"]))); |