From 3fb172ef0a635c2e705d3d1cb58624cfc6afd502 Mon Sep 17 00:00:00 2001 From: Pauli Date: Tue, 11 Oct 2022 21:00:50 +1100 Subject: [PATCH] QUIC: use list.h The demux and record RX implemented lists internally. This changes them over to using list.h. Reviewed-by: Tim Hudson Reviewed-by: Shane Lontis (Merged from https://github.com/openssl/openssl/pull/19377) --- include/internal/quic_demux.h | 8 +-- ssl/quic/quic_demux.c | 113 ++++++++---------------------- ssl/quic/quic_record_rx.c | 125 +++++++++++++--------------------- 3 files changed, 79 insertions(+), 167 deletions(-) diff --git a/include/internal/quic_demux.h b/include/internal/quic_demux.h index d6d3f35bf8..bc5b553582 100644 --- a/include/internal/quic_demux.h +++ b/include/internal/quic_demux.h @@ -14,6 +14,7 @@ # include "internal/quic_types.h" # include "internal/bio_addr.h" # include "internal/time.h" +# include "internal/list.h" /* * QUIC Demuxer @@ -86,7 +87,7 @@ typedef struct quic_urxe_st QUIC_URXE; #define QUIC_MAX_PKT_PER_URXE (sizeof(uint64_t) * 8) struct quic_urxe_st { - QUIC_URXE *prev, *next; + OSSL_LIST_MEMBER(urxe, QUIC_URXE); /* * The URXE data starts after this structure so we don't need a pointer. @@ -139,9 +140,8 @@ ossl_quic_urxe_data_end(const QUIC_URXE *e) } /* List structure tracking a queue of URXEs. */ -typedef struct quic_urxe_list_st { - QUIC_URXE *head, *tail; -} QUIC_URXE_LIST; +DEFINE_LIST_OF(urxe, QUIC_URXE); +typedef OSSL_LIST(urxe) QUIC_URXE_LIST; /* * List management helpers. These are used by the demuxer but can also be used diff --git a/ssl/quic/quic_demux.c b/ssl/quic/quic_demux.c index efb0997331..912cec2f23 100644 --- a/ssl/quic/quic_demux.c +++ b/ssl/quic/quic_demux.c @@ -14,59 +14,6 @@ #define DEMUX_MAX_MSGS_PER_CALL 32 -void ossl_quic_urxe_remove(QUIC_URXE_LIST *l, QUIC_URXE *e) -{ - /* Must be in list currently. */ - assert((e->prev != NULL || l->head == e) - && (e->next != NULL || l->tail == e)); - - if (e->prev != NULL) - e->prev->next = e->next; - if (e->next != NULL) - e->next->prev = e->prev; - - if (e == l->head) - l->head = e->next; - if (e == l->tail) - l->tail = e->prev; - - e->next = e->prev = NULL; -} - -void ossl_quic_urxe_insert_head(QUIC_URXE_LIST *l, QUIC_URXE *e) -{ - /* Must not be in list. */ - assert(e->prev == NULL && e->next == NULL); - - if (l->head == NULL) { - l->head = l->tail = e; - e->next = e->prev = NULL; - return; - } - - l->head->prev = e; - e->next = l->head; - e->prev = NULL; - l->head = e; -} - -void ossl_quic_urxe_insert_tail(QUIC_URXE_LIST *l, QUIC_URXE *e) -{ - /* Must not be in list. */ - assert(e->prev == NULL && e->next == NULL); - - if (l->tail == NULL) { - l->head = l->tail = e; - e->next = e->prev = NULL; - return; - } - - l->tail->next = e; - e->prev = l->tail; - e->next = NULL; - l->tail = e; -} - /* Structure used to track a given connection ID. */ typedef struct quic_demux_conn_st QUIC_DEMUX_CONN; @@ -124,7 +71,6 @@ struct quic_demux_st { * unconsumed data). These are moved to the pending list as they are filled. */ QUIC_URXE_LIST urx_free; - size_t num_urx_free; /* * List of URXEs which are filled with received encrypted data. These are @@ -181,12 +127,11 @@ static void demux_free_urxl(QUIC_URXE_LIST *l) { QUIC_URXE *e, *enext; - for (e = l->head; e != NULL; e = enext) { - enext = e->next; + for (e = ossl_list_urxe_head(l); e != NULL; e = enext) { + enext = ossl_list_urxe_next(e); + ossl_list_urxe_remove(l, e); OPENSSL_free(e); } - - l->head = l->tail = NULL; } void ossl_quic_demux_free(QUIC_DEMUX *demux) @@ -314,9 +259,9 @@ static QUIC_URXE *demux_alloc_urxe(size_t alloc_len) if (e == NULL) return NULL; - e->prev = e->next = NULL; + ossl_list_urxe_init_elem(e); e->alloc_len = alloc_len; - e->data_len = 0; + e->data_len = 0; return e; } @@ -324,13 +269,12 @@ static int demux_ensure_free_urxe(QUIC_DEMUX *demux, size_t min_num_free) { QUIC_URXE *e; - while (demux->num_urx_free < min_num_free) { + while (ossl_list_urxe_num(&demux->urx_free) < min_num_free) { e = demux_alloc_urxe(demux->default_urxe_alloc_len); if (e == NULL) return 0; - ossl_quic_urxe_insert_tail(&demux->urx_free, e); - ++demux->num_urx_free; + ossl_list_urxe_insert_tail(&demux->urx_free, e); } return 1; @@ -348,11 +292,11 @@ static int demux_recv(QUIC_DEMUX *demux) { BIO_MSG msg[DEMUX_MAX_MSGS_PER_CALL]; size_t rd, i; - QUIC_URXE *urxe = demux->urx_free.head, *unext; + QUIC_URXE *urxe = ossl_list_urxe_head(&demux->urx_free), *unext; OSSL_TIME now; /* This should never be called when we have any pending URXE. */ - assert(demux->urx_pending.head == NULL); + assert(ossl_list_urxe_head(&demux->urx_pending) == NULL); if (demux->net_bio == NULL) return 0; @@ -361,7 +305,8 @@ static int demux_recv(QUIC_DEMUX *demux) * Opportunistically receive as many messages as possible in a single * syscall, determined by how many free URXEs are available. */ - for (i = 0; i < (ossl_ssize_t)OSSL_NELEM(msg); ++i, urxe = urxe->next) { + for (i = 0; i < (ossl_ssize_t)OSSL_NELEM(msg); + ++i, urxe = ossl_list_urxe_next(urxe)) { if (urxe == NULL) { /* We need at least one URXE to receive into. */ if (!ossl_assert(i > 0)) @@ -386,17 +331,16 @@ static int demux_recv(QUIC_DEMUX *demux) now = demux->now != NULL ? demux->now(demux->now_arg) : ossl_time_zero(); - urxe = demux->urx_free.head; + urxe = ossl_list_urxe_head(&demux->urx_free); for (i = 0; i < rd; ++i, urxe = unext) { - unext = urxe->next; + unext = ossl_list_urxe_next(urxe); /* Set URXE with actual length of received datagram. */ urxe->data_len = msg[i].data_len; /* Time we received datagram. */ urxe->time = now; /* Move from free list to pending list. */ - ossl_quic_urxe_remove(&demux->urx_free, urxe); - --demux->num_urx_free; - ossl_quic_urxe_insert_tail(&demux->urx_pending, urxe); + ossl_list_urxe_remove(&demux->urx_free, urxe); + ossl_list_urxe_insert_tail(&demux->urx_pending, urxe); } return 1; @@ -434,7 +378,7 @@ static int demux_process_pending_urxe(QUIC_DEMUX *demux, QUIC_URXE *e) QUIC_DEMUX_CONN *conn; /* The next URXE we process should be at the head of the pending list. */ - if (!ossl_assert(e == demux->urx_pending.head)) + if (!ossl_assert(e == ossl_list_urxe_head(&demux->urx_pending))) return 0; conn = demux_identify_conn(demux, e); @@ -443,9 +387,8 @@ static int demux_process_pending_urxe(QUIC_DEMUX *demux, QUIC_URXE *e) * We could not identify a connection. We will never be able to process * this datagram, so get rid of it. */ - ossl_quic_urxe_remove(&demux->urx_pending, e); - ossl_quic_urxe_insert_tail(&demux->urx_free, e); - ++demux->num_urx_free; + ossl_list_urxe_remove(&demux->urx_pending, e); + ossl_list_urxe_insert_tail(&demux->urx_free, e); return 1; /* keep processing pending URXEs */ } @@ -453,7 +396,7 @@ static int demux_process_pending_urxe(QUIC_DEMUX *demux, QUIC_URXE *e) * Remove from list and invoke callback. The URXE now belongs to the * callback. (QUIC_DEMUX_CONN never has non-NULL cb.) */ - ossl_quic_urxe_remove(&demux->urx_pending, e); + ossl_list_urxe_remove(&demux->urx_pending, e); conn->cb(e, conn->cb_arg); return 1; } @@ -463,7 +406,7 @@ static int demux_process_pending_urxl(QUIC_DEMUX *demux) { QUIC_URXE *e; - while ((e = demux->urx_pending.head) != NULL) + while ((e = ossl_list_urxe_head(&demux->urx_pending)) != NULL) if (!demux_process_pending_urxe(demux, e)) return 0; @@ -478,7 +421,7 @@ int ossl_quic_demux_pump(QUIC_DEMUX *demux) { int ret; - if (demux->urx_pending.head == NULL) { + if (ossl_list_urxe_head(&demux->urx_pending) == NULL) { ret = demux_ensure_free_urxe(demux, DEMUX_MAX_MSGS_PER_CALL); if (ret != 1) return 0; @@ -490,7 +433,7 @@ int ossl_quic_demux_pump(QUIC_DEMUX *demux) /* * If demux_recv returned successfully, we should always have something. */ - assert(demux->urx_pending.head != NULL); + assert(ossl_list_urxe_head(&demux->urx_pending) != NULL); } return demux_process_pending_urxl(demux); @@ -510,7 +453,7 @@ int ossl_quic_demux_inject(QUIC_DEMUX *demux, if (ret != 1) return 0; - urxe = demux->urx_free.head; + urxe = ossl_list_urxe_head(&demux->urx_free); if (buf_len > urxe->alloc_len) return 0; @@ -528,9 +471,8 @@ int ossl_quic_demux_inject(QUIC_DEMUX *demux, BIO_ADDR_clear(&urxe->local); /* Move from free list to pending list. */ - ossl_quic_urxe_remove(&demux->urx_free, urxe); - --demux->num_urx_free; - ossl_quic_urxe_insert_tail(&demux->urx_pending, urxe); + ossl_list_urxe_remove(&demux->urx_free, urxe); + ossl_list_urxe_insert_tail(&demux->urx_pending, urxe); return demux_process_pending_urxl(demux); } @@ -539,7 +481,6 @@ int ossl_quic_demux_inject(QUIC_DEMUX *demux, void ossl_quic_demux_release_urxe(QUIC_DEMUX *demux, QUIC_URXE *e) { - assert(e->prev == NULL && e->next == NULL); - ossl_quic_urxe_insert_tail(&demux->urx_free, e); - ++demux->num_urx_free; + assert(ossl_list_urxe_prev(e) == NULL && ossl_list_urxe_next(e) == NULL); + ossl_list_urxe_insert_tail(&demux->urx_free, e); } diff --git a/ssl/quic/quic_record_rx.c b/ssl/quic/quic_record_rx.c index 636f6f8af4..e10dd58515 100644 --- a/ssl/quic/quic_record_rx.c +++ b/ssl/quic/quic_record_rx.c @@ -10,6 +10,7 @@ #include "internal/quic_record_rx.h" #include "quic_record_shared.h" #include "internal/common.h" +#include "internal/list.h" #include "../ssl_local.h" /* @@ -40,7 +41,7 @@ static ossl_inline int pkt_is_marked(const uint64_t *bitf, size_t pkt_idx) typedef struct rxe_st RXE; struct rxe_st { - RXE *prev, *next; + OSSL_LIST_MEMBER(rxe, RXE); size_t data_len, alloc_len; /* Extra fields for per-packet information. */ @@ -64,44 +65,14 @@ struct rxe_st { */ }; -typedef struct ossl_qrx_rxe_list_st { - RXE *head, *tail; -} RXE_LIST; +DEFINE_LIST_OF(rxe, RXE); +typedef OSSL_LIST(rxe) RXE_LIST; static ossl_inline unsigned char *rxe_data(const RXE *e) { return (unsigned char *)(e + 1); } -static void rxe_remove(RXE_LIST *l, RXE *e) -{ - if (e->prev != NULL) - e->prev->next = e->next; - if (e->next != NULL) - e->next->prev = e->prev; - - if (e == l->head) - l->head = e->next; - if (e == l->tail) - l->tail = e->prev; - - e->next = e->prev = NULL; -} - -static void rxe_insert_tail(RXE_LIST *l, RXE *e) -{ - if (l->tail == NULL) { - l->head = l->tail = e; - e->next = e->prev = NULL; - return; - } - - l->tail->next = e; - e->prev = l->tail; - e->next = NULL; - l->tail = e; -} - /* * QRL * === @@ -205,24 +176,21 @@ static void qrx_cleanup_rxl(RXE_LIST *l) { RXE *e, *enext; - for (e = l->head; e != NULL; e = enext) { - enext = e->next; + for (e = ossl_list_rxe_head(l); e != NULL; e = enext) { + enext = ossl_list_rxe_next(e); + ossl_list_rxe_remove(l, e); OPENSSL_free(e); } - - l->head = l->tail = NULL; } static void qrx_cleanup_urxl(OSSL_QRX *qrx, QUIC_URXE_LIST *l) { QUIC_URXE *e, *enext; - for (e = l->head; e != NULL; e = enext) { - enext = e->next; + for (e = ossl_list_urxe_head(l); e != NULL; e = enext) { + enext = ossl_list_urxe_next(e); ossl_quic_demux_release_urxe(qrx->demux, e); } - - l->head = l->tail = NULL; } void ossl_qrx_free(OSSL_QRX *qrx) @@ -253,7 +221,7 @@ static void qrx_on_rx(QUIC_URXE *urxe, void *arg) urxe->processed = 0; urxe->hpr_removed = 0; urxe->deferred = 0; - ossl_quic_urxe_insert_tail(&qrx->urx_pending, urxe); + ossl_list_urxe_insert_tail(&qrx->urx_pending, urxe); } int ossl_qrx_add_dst_conn_id(OSSL_QRX *qrx, @@ -275,9 +243,9 @@ static void qrx_requeue_deferred(OSSL_QRX *qrx) { QUIC_URXE *e; - while ((e = qrx->urx_deferred.head) != NULL) { - ossl_quic_urxe_remove(&qrx->urx_deferred, e); - ossl_quic_urxe_insert_head(&qrx->urx_pending, e); + while ((e = ossl_list_urxe_head(&qrx->urx_deferred)) != NULL) { + ossl_list_urxe_remove(&qrx->urx_deferred, e); + ossl_list_urxe_insert_head(&qrx->urx_pending, e); } } @@ -321,24 +289,25 @@ int ossl_qrx_discard_enc_level(OSSL_QRX *qrx, uint32_t enc_level) /* Returns 1 if there are one or more pending RXEs. */ int ossl_qrx_processed_read_pending(OSSL_QRX *qrx) { - return qrx->rx_pending.head != NULL; + return !ossl_list_rxe_is_empty(&qrx->rx_pending); } /* Returns 1 if there are yet-unprocessed packets. */ int ossl_qrx_unprocessed_read_pending(OSSL_QRX *qrx) { - return qrx->urx_pending.head != NULL || qrx->urx_deferred.head != NULL; + return !ossl_list_urxe_is_empty(&qrx->urx_pending) + || !ossl_list_urxe_is_empty(&qrx->urx_deferred); } /* Pop the next pending RXE. Returns NULL if no RXE is pending. */ static RXE *qrx_pop_pending_rxe(OSSL_QRX *qrx) { - RXE *rxe = qrx->rx_pending.head; + RXE *rxe = ossl_list_rxe_head(&qrx->rx_pending); if (rxe == NULL) return NULL; - rxe_remove(&qrx->rx_pending, rxe); + ossl_list_rxe_remove(&qrx->rx_pending, rxe); return rxe; } @@ -354,7 +323,7 @@ static RXE *qrx_alloc_rxe(size_t alloc_len) if (rxe == NULL) return NULL; - rxe->prev = rxe->next = NULL; + ossl_list_rxe_init_elem(rxe); rxe->alloc_len = alloc_len; rxe->data_len = 0; return rxe; @@ -371,14 +340,14 @@ static RXE *qrx_ensure_free_rxe(OSSL_QRX *qrx, size_t alloc_len) { RXE *rxe; - if (qrx->rx_free.head != NULL) - return qrx->rx_free.head; + if (ossl_list_rxe_head(&qrx->rx_free) != NULL) + return ossl_list_rxe_head(&qrx->rx_free); rxe = qrx_alloc_rxe(alloc_len); if (rxe == NULL) return NULL; - rxe_insert_tail(&qrx->rx_free, rxe); + ossl_list_rxe_insert_tail(&qrx->rx_free, rxe); return rxe; } @@ -389,7 +358,7 @@ static RXE *qrx_ensure_free_rxe(OSSL_QRX *qrx, size_t alloc_len) */ static RXE *qrx_resize_rxe(RXE_LIST *rxl, RXE *rxe, size_t n) { - RXE *rxe2; + RXE *rxe2, *p; /* Should never happen. */ if (rxe == NULL) @@ -398,26 +367,28 @@ static RXE *qrx_resize_rxe(RXE_LIST *rxl, RXE *rxe, size_t n) if (n >= SIZE_MAX - sizeof(RXE)) return NULL; + /* Remove the item from the list to avoid accessing freed memory */ + p = ossl_list_rxe_prev(rxe); + ossl_list_rxe_remove(rxl, rxe); + /* * NOTE: We do not clear old memory, although it does contain decrypted * data. */ rxe2 = OPENSSL_realloc(rxe, sizeof(RXE) + n); - if (rxe2 == NULL) - /* original RXE is still intact unchanged */ - return NULL; - - if (rxe != rxe2) { - if (rxl->head == rxe) - rxl->head = rxe2; - if (rxl->tail == rxe) - rxl->tail = rxe2; - if (rxe->prev != NULL) - rxe->prev->next = rxe2; - if (rxe->next != NULL) - rxe->next->prev = rxe2; + if (rxe2 == NULL || rxe == rxe2) { + if (p == NULL) + ossl_list_rxe_insert_head(rxl, rxe); + else + ossl_list_rxe_insert_after(rxl, p, rxe); + return rxe2; } + if (p == NULL) + ossl_list_rxe_insert_head(rxl, rxe2); + else + ossl_list_rxe_insert_after(rxl, p, rxe2); + rxe2->alloc_len = n; return rxe2; } @@ -439,8 +410,8 @@ static RXE *qrx_reserve_rxe(RXE_LIST *rxl, static void qrx_recycle_rxe(OSSL_QRX *qrx, RXE *rxe) { /* RXE should not be in any list */ - assert(rxe->prev == NULL && rxe->next == NULL); - rxe_insert_tail(&qrx->rx_free, rxe); + assert(ossl_list_rxe_prev(rxe) == NULL && ossl_list_rxe_next(rxe) == NULL); + ossl_list_rxe_insert_tail(&qrx->rx_free, rxe); } /* @@ -773,8 +744,8 @@ static int qrx_process_pkt(OSSL_QRX *qrx, QUIC_URXE *urxe, rxe->pn = QUIC_PN_INVALID; /* Move RXE to pending. */ - rxe_remove(&qrx->rx_free, rxe); - rxe_insert_tail(&qrx->rx_pending, rxe); + ossl_list_rxe_remove(&qrx->rx_free, rxe); + ossl_list_rxe_insert_tail(&qrx->rx_pending, rxe); return 0; /* success, did not defer */ } @@ -932,8 +903,8 @@ static int qrx_process_pkt(OSSL_QRX *qrx, QUIC_URXE *urxe, rxe->time = urxe->time; /* Move RXE to pending. */ - rxe_remove(&qrx->rx_free, rxe); - rxe_insert_tail(&qrx->rx_pending, rxe); + ossl_list_rxe_remove(&qrx->rx_free, rxe); + ossl_list_rxe_insert_tail(&qrx->rx_pending, rxe); return 0; /* success, did not defer; not distinguished from failure */ cannot_decrypt: @@ -1033,7 +1004,7 @@ static int qrx_process_one_urxe(OSSL_QRX *qrx, QUIC_URXE *e) int was_deferred; /* The next URXE we process should be at the head of the pending list. */ - if (!ossl_assert(e == qrx->urx_pending.head)) + if (!ossl_assert(e == ossl_list_urxe_head(&qrx->urx_pending))) return 0; /* @@ -1049,10 +1020,10 @@ static int qrx_process_one_urxe(OSSL_QRX *qrx, QUIC_URXE *e) * Remove the URXE from the pending list and return it to * either the free or deferred list. */ - ossl_quic_urxe_remove(&qrx->urx_pending, e); + ossl_list_urxe_remove(&qrx->urx_pending, e); if (was_deferred > 0 && (e->deferred || qrx->num_deferred < qrx->max_deferred)) { - ossl_quic_urxe_insert_tail(&qrx->urx_deferred, e); + ossl_list_urxe_insert_tail(&qrx->urx_deferred, e); if (!e->deferred) { e->deferred = 1; ++qrx->num_deferred; @@ -1073,7 +1044,7 @@ static int qrx_process_pending_urxl(OSSL_QRX *qrx) { QUIC_URXE *e; - while ((e = qrx->urx_pending.head) != NULL) + while ((e = ossl_list_urxe_head(&qrx->urx_pending)) != NULL) if (!qrx_process_one_urxe(qrx, e)) return 0; -- 2.34.1