From d77aea591650cd3bfe7c25cbb6955011bb21b416 Mon Sep 17 00:00:00 2001 From: Hugo Landau Date: Thu, 15 Sep 2022 12:29:10 +0100 Subject: [PATCH] QUIC TXPIM Reviewed-by: Tomas Mraz Reviewed-by: Matt Caswell (Merged from https://github.com/openssl/openssl/pull/19206) --- include/internal/quic_txpim.h | 109 +++++++++++++++ ssl/quic/build.info | 2 +- ssl/quic/quic_txpim.c | 217 ++++++++++++++++++++++++++++++ test/build.info | 6 +- test/quic_txpim_test.c | 67 +++++++++ test/recipes/70-test_quic_txpim.t | 19 +++ 6 files changed, 418 insertions(+), 2 deletions(-) create mode 100644 include/internal/quic_txpim.h create mode 100644 ssl/quic/quic_txpim.c create mode 100644 test/quic_txpim_test.c create mode 100644 test/recipes/70-test_quic_txpim.t diff --git a/include/internal/quic_txpim.h b/include/internal/quic_txpim.h new file mode 100644 index 0000000000..623004e79d --- /dev/null +++ b/include/internal/quic_txpim.h @@ -0,0 +1,109 @@ +/* + * 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 + */ + +#ifndef OSSL_QUIC_TXPIM_H +# define OSSL_QUIC_TXPIM_H + +# include +# include "internal/quic_types.h" +# include "internal/quic_cfq.h" +# include "internal/quic_ackm.h" + +/* + * QUIC Transmitted Packet Information Manager + * =========================================== + */ +typedef struct quic_txpim_st QUIC_TXPIM; +typedef struct quic_fifd_st QUIC_FIFD; + +typedef struct quic_txpim_pkt_st { + /* ACKM-specific data. Caller should fill this. */ + OSSL_ACKM_TX_PKT ackm_pkt; + + /* Linked list of CFQ items in this packet. */ + QUIC_CFQ_ITEM *retx_head; + + /* Reserved for FIFD use. */ + QUIC_FIFD *fifd; + + /* Regenerate-strategy frames. */ + unsigned int had_handshake_done_frame : 1; + unsigned int had_max_data_frame : 1; + unsigned int had_max_streams_frame : 1; + unsigned int had_ack_frame : 1; + + /* Private data follows. */ +} QUIC_TXPIM_PKT; + +/* Represents a range of bytes in an application or CRYPTO stream. */ +typedef struct quic_txpim_chunk_st { + /* The stream ID, or UINT64_MAX for the CRYPTO stream. */ + uint64_t stream_id; + /* + * The inclusive range of bytes in the stream. Exceptionally, if end < + * start, designates a frame of zero length (used for FIN-only frames). + */ + uint64_t start, end; + /* + * Whether a FIN was sent for this stream in the packet. Not valid for + * CRYPTO stream. + */ + unsigned int has_fin : 1; +} QUIC_TXPIM_CHUNK; + +QUIC_TXPIM *ossl_quic_txpim_new(void); + +/* + * Frees the TXPIM. All QUIC_TXPIM_PKTs which have been handed out by the TXPIM + * must be released via a call to ossl_quic_txpim_pkt_release() before calling + * this function. + */ +void ossl_quic_txpim_free(QUIC_TXPIM *txpim); + +/* + * Allocates a new QUIC_TXPIM_PKT structure from the pool. Returns NULL on + * failure. The returned structure is cleared of all data and is in a fresh + * initial state. + */ +QUIC_TXPIM_PKT *ossl_quic_txpim_pkt_alloc(QUIC_TXPIM *txpim); + +/* + * Releases the TXPIM packet, returning it to the pool. + */ +void ossl_quic_txpim_pkt_release(QUIC_TXPIM *txpim, QUIC_TXPIM_PKT *fpkt); + +/* Clears the chunk list of the packet, removing all entries. */ +void ossl_quic_txpim_pkt_clear_chunks(QUIC_TXPIM_PKT *fpkt); + +/* Appends a chunk to the packet. The structure is copied. */ +int ossl_quic_txpim_pkt_append_chunk(QUIC_TXPIM_PKT *fpkt, + const QUIC_TXPIM_CHUNK *chunk); + +/* Adds a CFQ item to the packet by prepending it to the retx_head list. */ +void ossl_quic_txpim_pkt_add_cfq_item(QUIC_TXPIM_PKT *fpkt, + QUIC_CFQ_ITEM *item); + +/* + * Returns a pointer to an array of stream chunk information structures for the + * given packet. The caller must call ossl_quic_txpim_pkt_get_num_chunks() to + * determine the length of this array. The returned pointer is invalidated + * if the chunk list is mutated, for example via a call to + * ossl_quic_txpim_pkt_append_chunk() or ossl_quic_txpim_pkt_clear_chunks(). + * + * The chunks are sorted by (stream_id, start) in ascending order. + */ +const QUIC_TXPIM_CHUNK *ossl_quic_txpim_pkt_get_chunks(QUIC_TXPIM_PKT *fpkt); + +/* + * Returns the number of entries in the array returned by + * ossl_quic_txpim_pkt_get_chunks(). + */ +size_t ossl_quic_txpim_pkt_get_num_chunks(QUIC_TXPIM_PKT *fpkt); + +#endif diff --git a/ssl/quic/build.info b/ssl/quic/build.info index c4d5ad504d..1f228cb6d7 100644 --- a/ssl/quic/build.info +++ b/ssl/quic/build.info @@ -5,4 +5,4 @@ SOURCE[$LIBSSL]=cc_dummy.c quic_demux.c quic_record_rx.c SOURCE[$LIBSSL]=quic_record_tx.c quic_record_util.c quic_record_shared.c quic_wire_pkt.c SOURCE[$LIBSSL]=quic_record_rx_wrap.c quic_rx_depack.c SOURCE[$LIBSSL]=quic_fc.c uint_set.c quic_stream.c -SOURCE[$LIBSSL]=quic_cfq.c +SOURCE[$LIBSSL]=quic_cfq.c quic_txpim.c diff --git a/ssl/quic/quic_txpim.c b/ssl/quic/quic_txpim.c new file mode 100644 index 0000000000..38b16a4561 --- /dev/null +++ b/ssl/quic/quic_txpim.c @@ -0,0 +1,217 @@ +/* + * 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 + */ + +#include "internal/quic_txpim.h" +#include + +typedef struct quic_txpim_pkt_ex_st QUIC_TXPIM_PKT_EX; + +struct quic_txpim_pkt_ex_st { + QUIC_TXPIM_PKT public; + QUIC_TXPIM_PKT_EX *prev, *next; + QUIC_TXPIM_CHUNK *chunks; + size_t num_chunks, alloc_chunks; + unsigned int chunks_need_sort : 1; +}; + +typedef struct quic_txpim_pkt_ex_list { + QUIC_TXPIM_PKT_EX *head, *tail; +} QUIC_TXPIM_PKT_EX_LIST; + +struct quic_txpim_st { + QUIC_TXPIM_PKT_EX_LIST free_list; + size_t in_use; +}; + +#define MAX_ALLOC_CHUNKS 512 + +QUIC_TXPIM *ossl_quic_txpim_new(void) +{ + QUIC_TXPIM *txpim = OPENSSL_zalloc(sizeof(*txpim)); + if (txpim == NULL) + return NULL; + + return txpim; +} + +static void free_list(QUIC_TXPIM_PKT_EX_LIST *l) +{ + QUIC_TXPIM_PKT_EX *n, *nnext; + + for (n = l->head; n != NULL; n = nnext) { + nnext = n->next; + + OPENSSL_free(n->chunks); + OPENSSL_free(n); + } + + l->head = l->tail = NULL; +} + +void ossl_quic_txpim_free(QUIC_TXPIM *txpim) +{ + if (txpim == NULL) + return; + + assert(txpim->in_use == 0); + free_list(&txpim->free_list); + OPENSSL_free(txpim); +} + +static void list_remove(QUIC_TXPIM_PKT_EX_LIST *l, QUIC_TXPIM_PKT_EX *n) +{ + if (l->head == n) + l->head = n->next; + if (l->tail == n) + l->tail = n->prev; + if (n->prev != NULL) + n->prev->next = n->next; + if (n->next != NULL) + n->next->prev = n->prev; + n->prev = n->next = NULL; +} + +static void list_insert_tail(QUIC_TXPIM_PKT_EX_LIST *l, QUIC_TXPIM_PKT_EX *n) +{ + n->prev = l->tail; + n->next = NULL; + l->tail = n; + if (n->prev != NULL) + n->prev->next = n; + if (l->head == NULL) + l->head = n; +} + +static QUIC_TXPIM_PKT_EX *txpim_get_free(QUIC_TXPIM *txpim) +{ + QUIC_TXPIM_PKT_EX *ex = txpim->free_list.head; + + if (ex != NULL) + return ex; + + ex = OPENSSL_zalloc(sizeof(*ex)); + if (ex == NULL) + return NULL; + + list_insert_tail(&txpim->free_list, ex); + return ex; +} + +static void txpim_clear(QUIC_TXPIM_PKT_EX *ex) +{ + memset(&ex->public.ackm_pkt, 0, sizeof(ex->public.ackm_pkt)); + ossl_quic_txpim_pkt_clear_chunks(&ex->public); + ex->public.retx_head = NULL; + ex->public.fifd = NULL; + ex->public.had_handshake_done_frame = 0; + ex->public.had_max_data_frame = 0; + ex->public.had_max_streams_frame = 0; + ex->public.had_ack_frame = 0; +} + +QUIC_TXPIM_PKT *ossl_quic_txpim_pkt_alloc(QUIC_TXPIM *txpim) +{ + QUIC_TXPIM_PKT_EX *ex = txpim_get_free(txpim); + + if (ex == NULL) + return NULL; + + txpim_clear(ex); + list_remove(&txpim->free_list, ex); + ++txpim->in_use; + return &ex->public; +} + +void ossl_quic_txpim_pkt_release(QUIC_TXPIM *txpim, QUIC_TXPIM_PKT *fpkt) +{ + QUIC_TXPIM_PKT_EX *ex = (QUIC_TXPIM_PKT_EX *)fpkt; + + assert(txpim->in_use > 0); + --txpim->in_use; + list_insert_tail(&txpim->free_list, ex); +} + +void ossl_quic_txpim_pkt_add_cfq_item(QUIC_TXPIM_PKT *fpkt, + QUIC_CFQ_ITEM *item) +{ + item->pkt_next = fpkt->retx_head; + item->pkt_prev = NULL; + fpkt->retx_head = item; +} + +void ossl_quic_txpim_pkt_clear_chunks(QUIC_TXPIM_PKT *fpkt) +{ + QUIC_TXPIM_PKT_EX *ex = (QUIC_TXPIM_PKT_EX *)fpkt; + + ex->num_chunks = 0; +} + +int ossl_quic_txpim_pkt_append_chunk(QUIC_TXPIM_PKT *fpkt, + const QUIC_TXPIM_CHUNK *chunk) +{ + QUIC_TXPIM_PKT_EX *ex = (QUIC_TXPIM_PKT_EX *)fpkt; + QUIC_TXPIM_CHUNK *new_chunk; + size_t new_alloc_chunks = ex->alloc_chunks; + + if (ex->num_chunks == ex->alloc_chunks) { + new_alloc_chunks = (ex->alloc_chunks == 0) ? 4 : ex->alloc_chunks * 8 / 5; + if (new_alloc_chunks > MAX_ALLOC_CHUNKS) + new_alloc_chunks = MAX_ALLOC_CHUNKS; + if (ex->num_chunks == new_alloc_chunks) + return 0; + + new_chunk = OPENSSL_realloc(ex->chunks, + new_alloc_chunks * sizeof(QUIC_TXPIM_CHUNK)); + if (new_chunk == NULL) + return 0; + + ex->chunks = new_chunk; + ex->alloc_chunks = new_alloc_chunks; + } + + ex->chunks[ex->num_chunks++] = *chunk; + ex->chunks_need_sort = 1; + return 1; +} + +static int compare(const void *a, const void *b) +{ + const QUIC_TXPIM_CHUNK *ac = a, *bc = b; + + if (ac->stream_id < bc->stream_id) + return -1; + else if (ac->stream_id > bc->stream_id) + return 1; + + if (ac->start < bc->start) + return -1; + else if (ac->start > bc->start) + return 1; + + return 0; +} + +const QUIC_TXPIM_CHUNK *ossl_quic_txpim_pkt_get_chunks(QUIC_TXPIM_PKT *fpkt) +{ + QUIC_TXPIM_PKT_EX *ex = (QUIC_TXPIM_PKT_EX *)fpkt; + + if (ex->chunks_need_sort) { + qsort(ex->chunks, ex->num_chunks, sizeof(QUIC_TXPIM_CHUNK), compare); + ex->chunks_need_sort = 0; + } + + return ex->chunks; +} + +size_t ossl_quic_txpim_pkt_get_num_chunks(QUIC_TXPIM_PKT *fpkt) +{ + QUIC_TXPIM_PKT_EX *ex = (QUIC_TXPIM_PKT_EX *)fpkt; + + return ex->num_chunks; +} diff --git a/test/build.info b/test/build.info index cd72179be1..728fc11166 100644 --- a/test/build.info +++ b/test/build.info @@ -304,6 +304,10 @@ IF[{- !$disabled{tests} -}] INCLUDE[quic_cfq_test]=../include ../apps/include DEPEND[quic_cfq_test]=../libcrypto.a ../libssl.a libtestutil.a + SOURCE[quic_txpim_test]=quic_txpim_test.c + INCLUDE[quic_txpim_test]=../include ../apps/include + DEPEND[quic_txpim_test]=../libcrypto.a ../libssl.a libtestutil.a + SOURCE[asynctest]=asynctest.c INCLUDE[asynctest]=../include ../apps/include DEPEND[asynctest]=../libcrypto @@ -1028,7 +1032,7 @@ ENDIF ENDIF IF[{- !$disabled{'quic'} -}] - PROGRAMS{noinst}=quicapitest quic_wire_test quic_ackm_test quic_record_test quic_fc_test quic_stream_test quic_cfq_test + PROGRAMS{noinst}=quicapitest quic_wire_test quic_ackm_test quic_record_test quic_fc_test quic_stream_test quic_cfq_test quic_txpim_test ENDIF SOURCE[quicapitest]=quicapitest.c helpers/ssltestlib.c diff --git a/test/quic_txpim_test.c b/test/quic_txpim_test.c new file mode 100644 index 0000000000..84f870312b --- /dev/null +++ b/test/quic_txpim_test.c @@ -0,0 +1,67 @@ +/* + * 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 + */ + +#include "internal/packet.h" +#include "internal/quic_txpim.h" +#include "testutil.h" + +static int test_txpim(void) +{ + int testresult = 0; + QUIC_TXPIM *txpim; + size_t i, j; + QUIC_TXPIM_PKT *pkts[10] = {NULL}; + QUIC_TXPIM_CHUNK chunks[3]; + const QUIC_TXPIM_CHUNK *rchunks; + + if (!TEST_ptr(txpim = ossl_quic_txpim_new())) + goto err; + + for (i = 0; i < OSSL_NELEM(pkts); ++i) { + if (!TEST_ptr(pkts[i] = ossl_quic_txpim_pkt_alloc(txpim))) + goto err; + + if (!TEST_size_t_eq(ossl_quic_txpim_pkt_get_num_chunks(pkts[i]), 0)) + goto err; + + for (j = 0; j < OSSL_NELEM(chunks); ++j) { + chunks[j].stream_id = 100 - j; + chunks[j].start = 1000 * i + j * 10; + chunks[j].end = chunks[j].start + 5; + + if (!TEST_true(ossl_quic_txpim_pkt_append_chunk(pkts[i], chunks + j))) + goto err; + } + + if (!TEST_size_t_eq(ossl_quic_txpim_pkt_get_num_chunks(pkts[i]), + OSSL_NELEM(chunks))) + goto err; + + rchunks = ossl_quic_txpim_pkt_get_chunks(pkts[i]); + if (!TEST_uint64_t_eq(rchunks[0].stream_id, 98) + || !TEST_uint64_t_eq(rchunks[1].stream_id, 99) + || !TEST_uint64_t_eq(rchunks[2].stream_id, 100)) + goto err; + } + + testresult = 1; +err: + for (i = 0; i < OSSL_NELEM(pkts); ++i) + if (txpim != NULL && pkts[i] != NULL) + ossl_quic_txpim_pkt_release(txpim, pkts[i]); + + ossl_quic_txpim_free(txpim); + return testresult; +} + +int setup_tests(void) +{ + ADD_TEST(test_txpim); + return 1; +} diff --git a/test/recipes/70-test_quic_txpim.t b/test/recipes/70-test_quic_txpim.t new file mode 100644 index 0000000000..071394cec3 --- /dev/null +++ b/test/recipes/70-test_quic_txpim.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_txpim"); + +plan skip_all => "QUIC protocol is not supported by this OpenSSL build" + if disabled('quic'); + +plan tests => 1; + +ok(run(test(["quic_txpim_test"]))); -- 2.39.2