From 0847e63ee5d58d824390aadcbcf10281c45900c4 Mon Sep 17 00:00:00 2001 From: Hugo Landau Date: Tue, 18 Apr 2023 19:30:56 +0100 Subject: QUIC QSM: Stream garbage collection This allows QUIC_STREAM objects to be deleted when they are no longer needed. Reviewed-by: Matt Caswell Reviewed-by: Tomas Mraz (Merged from https://github.com/openssl/openssl/pull/20765) --- include/internal/quic_stream.h | 6 ++ include/internal/quic_stream_map.h | 119 ++++++++++++++++++++++++++++++++++++- ssl/quic/quic_channel.c | 3 + ssl/quic/quic_sstream.c | 21 +++++++ ssl/quic/quic_stream_map.c | 68 +++++++++++++++++++-- 5 files changed, 210 insertions(+), 7 deletions(-) diff --git a/include/internal/quic_stream.h b/include/internal/quic_stream.h index 42d6ed2d7d..a1e88a4ab6 100644 --- a/include/internal/quic_stream.h +++ b/include/internal/quic_stream.h @@ -253,6 +253,12 @@ void ossl_quic_sstream_fin(QUIC_SSTREAM *qss); */ int ossl_quic_sstream_get_final_size(QUIC_SSTREAM *qss, uint64_t *final_size); +/* + * Returns 1 iff all bytes (and any FIN, if any) which have been appended to the + * QUIC_SSTREAM so far, and any FIN (if any), have been both sent and acked. + */ +int ossl_quic_sstream_is_totally_acked(QUIC_SSTREAM *qss); + /* * Resizes the internal ring buffer. All stream data is preserved safely. * diff --git a/include/internal/quic_stream_map.h b/include/internal/quic_stream_map.h index 0f2732a6fc..5d21c60185 100644 --- a/include/internal/quic_stream_map.h +++ b/include/internal/quic_stream_map.h @@ -37,6 +37,7 @@ struct quic_stream_list_node_st { struct quic_stream_st { QUIC_STREAM_LIST_NODE active_node; /* for use by QUIC_STREAM_MAP */ QUIC_STREAM_LIST_NODE accept_node; /* accept queue of remotely-created streams */ + QUIC_STREAM_LIST_NODE ready_for_gc_node; /* queue of streams now ready for GC */ /* Temporary link used by TXP. */ QUIC_STREAM *txp_next; @@ -119,8 +120,117 @@ struct quic_stream_st { /* A FIN has been retired from the rstream buffer. */ unsigned int recv_fin_retired : 1; - /* The stream's XSO has been deleted. Pending GC. */ + /* + * The stream's XSO has been deleted. Pending GC. + * + * Here is how stream deletion works: + * + * - A QUIC_STREAM cannot be deleted until it is neither in the accept + * queue nor has an associated XSO. This condition occurs when and only + * when deleted is true. + * + * - Once there is the case (i.e., no user-facing API object exposing the + * stream), we can delete the stream once we determine that all of our + * protocol obligations requiring us to keep the QUIC_STREAM around have + * been met. + * + * The following frames relate to the streams layer for a specific + * stream: + * + * STREAM + * + * RX Obligations: + * Ignore for a deleted stream. + * + * (This is different from our obligation for a + * locally-initiated stream ID we have not created yet, + * which we must treat as a protocol error. This can be + * distinguished via a simple monotonic counter.) + * + * TX Obligations: + * None, once we've decided to (someday) delete the stream. + * + * STOP_SENDING + * + * We cannot delete the stream until we have finished informing + * the peer that we are not going to be listening to it + * anymore. + * + * RX Obligations: + * When we delete a stream we must have already had a FIN + * or RESET_STREAM we transmitted acknowledged by the peer. + * Thus we can ignore STOP_SENDING frames for deleted + * streams (if they occur, they are probably just + * retransmissions). + * + * TX Obligations: + * _Acknowledged_ receipt of a STOP_SENDING frame by the + * peer (unless the peer's send part has already FIN'd). + * + * RESET_STREAM + * + * We cannot delete the stream until we have finished informing + * the peer that we are not going to be transmitting on it + * anymore. + * + * RX Obligations: + * This indicates the peer is not going to send any more + * data on the stream. We don't need to care about this + * since once a stream is marked for deletion we don't care + * about any data it does send. We can ignore this for + * deleted streams. The important criterion is that the + * peer has been successfully delivered our STOP_SENDING + * frame. + * + * TX Obligations: + * _Acknowledged_ receipt of a RESET_STREAM frame or FIN by + * the peer. + * + * MAX_STREAM_DATA + * + * RX Obligations: + * Ignore. Since we are not going to be sending any more + * data on a stream once it has been marked for deletion, + * we don't need to care about flow control information. + * + * TX Obligations: + * None. + * + * In other words, our protocol obligation is simply: + * + * - either: + * - the peer has acknowledged receipt of a STOP_SENDING frame sent + * by us; -or- + * - we have received a FIN and all preceding segments from the peer + * + * [NOTE: The actual criterion required here is simply 'we have + * received a FIN from the peer'. However, due to reordering and + * retransmissions we might subsequently receive non-FIN segments + * out of order. The FIN means we know the peer will stop + * transmitting on the stream at *some* point, but by sending + * STOP_SENDING we can avoid these needless retransmissions we + * will just ignore anyway. In actuality we could just handle all + * cases by sending a STOP_SENDING. The strategy we choose is to + * only avoid sending a STOP_SENDING and rely on a received FIN + * when we have received all preceding data, as this makes it + * reasonably certain no benefit would be gained by sending + * STOP_SENDING.] + * + * TODO(QUIC): Implement the latter case (currently we just + * always do STOP_SENDING). + * + * and; + * + * - we have drained our send stream (for a finished send stream) + * and got acknowledgement all parts of it including the FIN, or + * sent a RESET_STREAM frame and got acknowledgement of that frame. + * + * Once these conditions are met, we can GC the QUIC_STREAM. + * + */ unsigned int deleted : 1; + /* Set to 1 once the above conditions are actually met. */ + unsigned int ready_for_gc : 1; }; /* @@ -138,6 +248,7 @@ typedef struct quic_stream_map_st { LHASH_OF(QUIC_STREAM) *map; QUIC_STREAM_LIST_NODE active_list; QUIC_STREAM_LIST_NODE accept_list; + QUIC_STREAM_LIST_NODE ready_for_gc_list; size_t rr_stepping, rr_counter, num_accept; QUIC_STREAM *rr_cur; uint64_t (*get_stream_limit_cb)(int uni, void *arg); @@ -287,6 +398,12 @@ void ossl_quic_stream_map_remove_from_accept_queue(QUIC_STREAM_MAP *qsm, /* Returns the length of the accept queue. */ size_t ossl_quic_stream_map_get_accept_queue_len(QUIC_STREAM_MAP *qsm); +/* + * Delete streams ready for GC. Pointers to those QUIC_STREAM objects become + * invalid. + */ +void ossl_quic_stream_map_gc(QUIC_STREAM_MAP *qsm); + /* * QUIC Stream Iterator * ==================== diff --git a/ssl/quic/quic_channel.c b/ssl/quic/quic_channel.c index ec0364ee68..7e55b7b5c6 100644 --- a/ssl/quic/quic_channel.c +++ b/ssl/quic/quic_channel.c @@ -1372,6 +1372,9 @@ static void ch_tick(QUIC_TICK_RESULT *res, void *arg, uint32_t flags) /* Write any data to the network due to be sent. */ ch_tx(ch); + /* Do stream GC. */ + ossl_quic_stream_map_gc(&ch->qsm); + /* Determine the time at which we should next be ticked. */ res->tick_deadline = ch_determine_next_tick_deadline(ch); diff --git a/ssl/quic/quic_sstream.c b/ssl/quic/quic_sstream.c index a0ef4e9eae..0e15dde51d 100644 --- a/ssl/quic/quic_sstream.c +++ b/ssl/quic/quic_sstream.c @@ -372,6 +372,27 @@ size_t ossl_quic_sstream_get_buffer_avail(QUIC_SSTREAM *qss) return ring_buf_avail(&qss->ring_buf); } +int ossl_quic_sstream_is_totally_acked(QUIC_SSTREAM *qss) +{ + UINT_RANGE r; + uint64_t cur_size; + + if ((qss->have_final_size && !qss->acked_final_size) + || ossl_list_uint_set_num(&qss->acked_set) != 1) + return 0; + + r = ossl_list_uint_set_head(&qss->acked_set)->range; + cur_size = qss->ring_buf.head_offset; + + /* + * The invariants of UINT_SET guarantee a single list element if we have a + * single contiguous range, which is what we should have if everything has + * been acked. + */ + assert(r.end + 1 <= cur_size); + return r.start == 0 && r.end + 1 == cur_size; +} + void ossl_quic_sstream_adjust_iov(size_t len, OSSL_QTX_IOVEC *iov, size_t num_iov) diff --git a/ssl/quic/quic_stream_map.c b/ssl/quic/quic_stream_map.c index cbc947398f..9fc5ca9f87 100644 --- a/ssl/quic/quic_stream_map.c +++ b/ssl/quic/quic_stream_map.c @@ -53,12 +53,16 @@ static QUIC_STREAM *list_next(QUIC_STREAM_LIST_NODE *l, QUIC_STREAM_LIST_NODE *n return (QUIC_STREAM *)(((char *)n) - off); } -#define active_next(l, s) list_next((l), &(s)->active_node, \ - offsetof(QUIC_STREAM, active_node)) -#define accept_next(l, s) list_next((l), &(s)->accept_node, \ - offsetof(QUIC_STREAM, accept_node)) -#define accept_head(l) list_next((l), (l), \ - offsetof(QUIC_STREAM, accept_node)) +#define active_next(l, s) list_next((l), &(s)->active_node, \ + offsetof(QUIC_STREAM, active_node)) +#define accept_next(l, s) list_next((l), &(s)->accept_node, \ + offsetof(QUIC_STREAM, accept_node)) +#define ready_for_gc_next(l, s) list_next((l), &(s)->ready_for_gc_node, \ + offsetof(QUIC_STREAM, ready_for_gc_node)) +#define accept_head(l) list_next((l), (l), \ + offsetof(QUIC_STREAM, accept_node)) +#define ready_for_gc_head(l) list_next((l), (l), \ + offsetof(QUIC_STREAM, ready_for_gc_node)) static unsigned long hash_stream(const QUIC_STREAM *s) { @@ -83,6 +87,8 @@ int ossl_quic_stream_map_init(QUIC_STREAM_MAP *qsm, qsm->map = lh_QUIC_STREAM_new(hash_stream, cmp_stream); qsm->active_list.prev = qsm->active_list.next = &qsm->active_list; qsm->accept_list.prev = qsm->accept_list.next = &qsm->accept_list; + qsm->ready_for_gc_list.prev = qsm->ready_for_gc_list.next + = &qsm->ready_for_gc_list; qsm->rr_stepping = 1; qsm->rr_counter = 0; qsm->rr_cur = NULL; @@ -145,6 +151,13 @@ void ossl_quic_stream_map_release(QUIC_STREAM_MAP *qsm, QUIC_STREAM *stream) if (stream == NULL) return; + if (stream->active_node.next != NULL) + list_remove(&qsm->active_list, &stream->active_node); + if (stream->accept_node.next != NULL) + list_remove(&qsm->accept_list, &stream->accept_node); + if (stream->ready_for_gc_node.next != NULL) + list_remove(&qsm->ready_for_gc_list, &stream->ready_for_gc_node); + ossl_quic_sstream_free(stream->sstream); stream->sstream = NULL; @@ -228,6 +241,31 @@ static int stream_has_data_to_send(QUIC_STREAM *s) return (shdr.is_fin && shdr.len == 0) || shdr.offset < fc_limit; } +static int qsm_ready_for_gc(QUIC_STREAM_MAP *qsm, QUIC_STREAM *qs) +{ + int recv_stream_fully_drained = 0; /* TODO(QUIC): Optimisation */ + + /* + * If sstream has no FIN, we auto-reset it at marked-for-deletion time, so + * we don't need to worry about that here. + */ + assert(!qs->deleted + || qs->sstream == NULL + || qs->reset_stream + || ossl_quic_sstream_get_final_size(qs, NULL)); + + return + qs->deleted + && (qs->rstream == NULL + || recv_stream_fully_drained + || qs->acked_stop_sending) + && (qs->sstream == NULL + || (!qs->reset_stream + && ossl_quic_sstream_is_totally_acked(qs->sstream)) + || (qs->reset_stream + && qs->acked_reset_stream)); +} + void ossl_quic_stream_map_update_state(QUIC_STREAM_MAP *qsm, QUIC_STREAM *s) { int should_be_active, allowed_by_stream_limit = 1; @@ -243,8 +281,15 @@ void ossl_quic_stream_map_update_state(QUIC_STREAM_MAP *qsm, QUIC_STREAM *s) allowed_by_stream_limit = (stream_ordinal < stream_limit); } + if (!s->ready_for_gc) { + s->ready_for_gc = qsm_ready_for_gc(qsm, s); + if (s->ready_for_gc) + list_insert_tail(&qsm->ready_for_gc_list, &s->ready_for_gc_node); + } + should_be_active = allowed_by_stream_limit + && !s->ready_for_gc && ((!s->peer_reset_stream && s->rstream != NULL && (s->want_max_stream_data || ossl_quic_rxfc_has_cwm_changed(&s->rxfc, 0))) @@ -325,6 +370,17 @@ size_t ossl_quic_stream_map_get_accept_queue_len(QUIC_STREAM_MAP *qsm) return qsm->num_accept; } +void ossl_quic_stream_map_gc(QUIC_STREAM_MAP *qsm) +{ + QUIC_STREAM *qs, *qsn; + + for (qs = ready_for_gc_head(&qsm->ready_for_gc_list); qs != NULL; qs = qsn) { + qsn = ready_for_gc_next(&qsm->ready_for_gc_list, qs); + + ossl_quic_stream_map_release(qsm, qs); + } +} + /* * QUIC Stream Iterator * ==================== -- cgit v1.2.1