QUIC TXPIM

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

6 files changed, 418 insertions, 2 deletions

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 <openssl/ssl.h>
+# 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 <stdlib.h>
+
+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"])));