QUIC CFQ

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

2 files changed, 340 insertions, 0 deletions

diff --git a/ssl/quic/build.info b/ssl/quic/build.info
index 017100407d..c4d5ad504d 100644
--- a/ssl/quic/build.info
+++ b/ssl/quic/build.info
@@ -5,3 +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
diff --git a/ssl/quic/quic_cfq.c b/ssl/quic/quic_cfq.c
new file mode 100644
index 0000000000..cdd621458c
--- /dev/null
+++ b/ssl/quic/quic_cfq.c
@@ -0,0 +1,339 @@
+/*
+ * 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_cfq.h"
+
+typedef struct quic_cfq_item_ex_st QUIC_CFQ_ITEM_EX;
+
+struct quic_cfq_item_ex_st {
+    QUIC_CFQ_ITEM           public;
+    QUIC_CFQ_ITEM_EX       *prev, *next;
+    unsigned char          *encoded;
+    cfq_free_cb            *free_cb;
+    void                   *free_cb_arg;
+    uint64_t                frame_type;
+    size_t                  encoded_len;
+    uint32_t                priority, pn_space;
+    char                    state;
+};
+
+uint64_t ossl_quic_cfq_item_get_frame_type(QUIC_CFQ_ITEM *item)
+{
+    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
+
+    return ex->frame_type;
+}
+
+const unsigned char *ossl_quic_cfq_item_get_encoded(QUIC_CFQ_ITEM *item)
+{
+    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
+
+    return ex->encoded;
+}
+
+size_t ossl_quic_cfq_item_get_encoded_len(QUIC_CFQ_ITEM *item)
+{
+    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
+
+    return ex->encoded_len;
+}
+
+int ossl_quic_cfq_item_get_state(QUIC_CFQ_ITEM *item)
+{
+    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
+
+    return ex->state;
+}
+
+uint32_t ossl_quic_cfq_item_get_pn_space(QUIC_CFQ_ITEM *item)
+{
+    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
+
+    return ex->pn_space;
+}
+
+typedef struct quic_cfq_item_list_st {
+    QUIC_CFQ_ITEM_EX *head, *tail;
+} QUIC_CFQ_ITEM_LIST;
+
+struct quic_cfq_st {
+    /* 
+     * Invariant: A CFQ item is always in exactly one of these lists, never more
+     * or less than one.
+     *
+     * Invariant: The list the CFQ item is determined exactly by the state field
+     * of the item.
+     */
+    QUIC_CFQ_ITEM_LIST                      new_list, tx_list, free_list;
+};
+
+static int compare(const QUIC_CFQ_ITEM_EX *a, const QUIC_CFQ_ITEM_EX *b)
+{
+    if (a->pn_space < b->pn_space)
+        return -1;
+    else if (a->pn_space > b->pn_space)
+        return 1;
+
+    if (a->priority > b->priority)
+        return -1;
+    else if (a->priority < b->priority)
+        return 1;
+
+    return 0;
+}
+
+static void list_remove(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_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_head(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_EX *n)
+{
+    n->next = l->head;
+    n->prev = NULL;
+    l->head = n;
+    if (n->next != NULL)
+        n->next->prev = n;
+    if (l->tail == NULL)
+        l->tail = n;
+}
+
+static void list_insert_tail(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_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 void list_insert_after(QUIC_CFQ_ITEM_LIST *l,
+                              QUIC_CFQ_ITEM_EX *ref,
+                              QUIC_CFQ_ITEM_EX *n)
+{
+    n->prev = ref;
+    n->next = ref->next;
+    if (ref->next != NULL)
+        ref->next->prev = n;
+    ref->next = n;
+    if (l->tail == ref)
+        l->tail = n;
+}
+
+static void list_insert_sorted(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_EX *n,
+                               int (*cmp)(const QUIC_CFQ_ITEM_EX *a,
+                                          const QUIC_CFQ_ITEM_EX *b))
+{
+    QUIC_CFQ_ITEM_EX *p = l->head, *pprev = NULL;
+
+    if (p == NULL) {
+        l->head = l->tail = n;
+        n->prev = n->next = NULL;
+        return;
+    }
+
+    for (; p != NULL && cmp(p, n) < 0; pprev = p, p = p->next);
+
+    if (p == NULL)
+        list_insert_tail(l, n);
+    else if (pprev == NULL)
+        list_insert_head(l, n);
+    else
+        list_insert_after(l, pprev, n);
+}
+
+QUIC_CFQ *ossl_quic_cfq_new(void)
+{
+    QUIC_CFQ *cfq = OPENSSL_zalloc(sizeof(*cfq));
+    if (cfq == NULL)
+        return NULL;
+
+    return cfq;
+}
+
+static void clear_item(QUIC_CFQ_ITEM_EX *item)
+{
+    if (item->free_cb != NULL) {
+        item->free_cb(item->encoded, item->encoded_len, item->free_cb_arg);
+
+        item->free_cb       = NULL;
+        item->encoded       = NULL;
+        item->encoded_len   = 0;
+    }
+
+    item->state = -1;
+}
+
+static void free_list_items(QUIC_CFQ_ITEM_LIST *l)
+{
+    QUIC_CFQ_ITEM_EX *p, *pnext;
+
+    for (p = l->head; p != NULL; p = pnext) {
+        pnext = p->next;
+        clear_item(p);
+        OPENSSL_free(p);
+    }
+}
+
+void ossl_quic_cfq_free(QUIC_CFQ *cfq)
+{
+    if (cfq == NULL)
+        return;
+
+    free_list_items(&cfq->new_list);
+    free_list_items(&cfq->tx_list);
+    free_list_items(&cfq->free_list);
+    OPENSSL_free(cfq);
+}
+
+static QUIC_CFQ_ITEM_EX *cfq_get_free(QUIC_CFQ *cfq)
+{
+    QUIC_CFQ_ITEM_EX *item = cfq->free_list.head;
+
+    if (item != NULL)
+        return item;
+
+    item = OPENSSL_zalloc(sizeof(*item));
+    if (item == NULL)
+        return NULL;
+
+    item->state = -1;
+    list_insert_tail(&cfq->free_list, item);
+    return item;
+}
+
+QUIC_CFQ_ITEM *ossl_quic_cfq_add_frame(QUIC_CFQ            *cfq,
+                                       uint32_t             priority,
+                                       uint32_t             pn_space,
+                                       uint64_t             frame_type,
+                                       const unsigned char *encoded,
+                                       size_t               encoded_len,
+                                       cfq_free_cb         *free_cb,
+                                       void                *free_cb_arg)
+{
+    QUIC_CFQ_ITEM_EX *item = cfq_get_free(cfq);
+
+    if (item == NULL)
+        return NULL;
+
+    item->priority      = priority;
+    item->frame_type    = frame_type;
+    item->pn_space      = pn_space;
+    item->encoded       = (unsigned char *)encoded;
+    item->encoded_len   = encoded_len;
+    item->free_cb       = free_cb;
+    item->free_cb_arg   = free_cb_arg;
+
+    item->state = QUIC_CFQ_STATE_NEW;
+    list_remove(&cfq->free_list, item);
+    list_insert_sorted(&cfq->new_list, item, compare);
+    return &item->public;
+}
+
+void ossl_quic_cfq_mark_tx(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item)
+{
+    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
+
+    switch (ex->state) {
+    case QUIC_CFQ_STATE_NEW:
+        list_remove(&cfq->new_list, ex);
+        list_insert_tail(&cfq->tx_list, ex);
+        ex->state = QUIC_CFQ_STATE_TX;
+        break;
+    case QUIC_CFQ_STATE_TX:
+        break; /* nothing to do */
+    default:
+        assert(0); /* invalid state (e.g. in free state) */
+        break;
+    }
+}
+
+void ossl_quic_cfq_mark_lost(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item,
+                             uint32_t priority)
+{
+    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
+
+    switch (ex->state) {
+    case QUIC_CFQ_STATE_NEW:
+        if (priority != UINT32_MAX && priority != ex->priority) {
+            list_remove(&cfq->new_list, ex);
+            ex->priority = priority;
+            list_insert_sorted(&cfq->new_list, ex, compare);
+        }
+        break; /* nothing to do */
+    case QUIC_CFQ_STATE_TX:
+        if (priority != UINT32_MAX)
+            ex->priority = priority;
+        list_remove(&cfq->tx_list, ex);
+        list_insert_sorted(&cfq->new_list, ex, compare);
+        ex->state = QUIC_CFQ_STATE_NEW;
+        break;
+    default:
+        assert(0); /* invalid state (e.g. in free state) */
+        break;
+    }
+}
+
+/*
+ * Releases a CFQ item. The item may be in either state (NEW or TX) prior to the
+ * call. The QUIC_CFQ_ITEM pointer must not be used following this call.
+ */
+void ossl_quic_cfq_release(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item)
+{
+    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
+    switch (ex->state) {
+    case QUIC_CFQ_STATE_NEW:
+        list_remove(&cfq->new_list, ex);
+        list_insert_tail(&cfq->free_list, ex);
+        clear_item(ex);
+        break;
+    case QUIC_CFQ_STATE_TX:
+        list_remove(&cfq->tx_list, ex);
+        list_insert_tail(&cfq->free_list, ex);
+        clear_item(ex);
+        break;
+    default:
+        assert(0); /* invalid state (e.g. in free state) */
+        break;
+    }
+}
+
+QUIC_CFQ_ITEM *ossl_quic_cfq_get_priority_head(QUIC_CFQ *cfq, uint32_t pn_space)
+{
+    QUIC_CFQ_ITEM_EX *item = cfq->new_list.head;
+
+    for (; item != NULL && item->pn_space != pn_space; item = item->next);
+
+    return &item->public;
+}
+
+QUIC_CFQ_ITEM *ossl_quic_cfq_item_get_priority_next(QUIC_CFQ_ITEM *item,
+                                                    uint32_t pn_space)
+{
+    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
+
+    if (ex == NULL)
+        return NULL;
+
+     ex = ex->next;
+
+     for (; ex != NULL && ex->pn_space != pn_space; ex = ex->next);
+
+     return &ex->public;
+}