2 * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
10 #ifndef OSSL_INTERNAL_QUIC_STREAM_MAP_H
11 # define OSSL_INTERNAL_QUIC_STREAM_MAP_H
14 # include "internal/e_os.h"
15 # include "internal/time.h"
16 # include "internal/quic_types.h"
17 # include "internal/quic_stream.h"
18 # include "internal/quic_fc.h"
19 # include <openssl/lhash.h>
21 # ifndef OPENSSL_NO_QUIC
27 * Logical QUIC stream composing all relevant send and receive components.
29 typedef struct quic_stream_st QUIC_STREAM
;
31 typedef struct quic_stream_list_node_st QUIC_STREAM_LIST_NODE
;
33 struct quic_stream_list_node_st
{
34 QUIC_STREAM_LIST_NODE
*prev
, *next
;
37 struct quic_stream_st
{
38 QUIC_STREAM_LIST_NODE active_node
; /* for use by QUIC_STREAM_MAP */
39 QUIC_STREAM_LIST_NODE accept_node
; /* accept queue of remotely-created streams */
40 QUIC_STREAM_LIST_NODE ready_for_gc_node
; /* queue of streams now ready for GC */
42 /* Temporary link used by TXP. */
43 QUIC_STREAM
*txp_next
;
46 * QUIC Stream ID. Do not assume that this encodes a type as this is a
47 * version-specific property and may change between QUIC versions; instead,
53 * Application Error Code (AEC) used for STOP_SENDING frame.
54 * This is only valid if stop_sending is 1.
56 uint64_t stop_sending_aec
;
59 * Application Error Code (AEC) used for RESET_STREAM frame.
60 * This is only valid if reset_stream is 1.
62 uint64_t reset_stream_aec
;
65 * Application Error Code (AEC) for incoming STOP_SENDING frame.
66 * This is only valid if peer_stop_sending is 1.
68 uint64_t peer_stop_sending_aec
;
71 * Application Error Code (AEC) for incoming RESET_STREAM frame.
72 * This is only valid if peer_reset_stream is 1.
74 uint64_t peer_reset_stream_aec
;
76 /* Temporary value used by TXP. */
77 uint64_t txp_txfc_new_credit_consumed
;
79 QUIC_SSTREAM
*sstream
; /* NULL if RX-only */
80 QUIC_RSTREAM
*rstream
; /* NULL if TX only */
81 QUIC_TXFC txfc
; /* NULL if RX-only */
82 QUIC_RXFC rxfc
; /* NULL if TX-only */
83 unsigned int type
: 8; /* QUIC_STREAM_INITIATOR_*, QUIC_STREAM_DIR_* */
84 unsigned int active
: 1;
87 * Has STOP_SENDING been requested (by us)? Note that this is not the same
88 * as want_stop_sending below, as a STOP_SENDING frame may already have been
89 * sent and fully acknowledged.
91 unsigned int stop_sending
: 1;
94 * Has RESET_STREAM been requested (by us)? Works identically to
95 * STOP_SENDING for transmission purposes.
97 unsigned int reset_stream
: 1;
99 /* Has our peer sent a STOP_SENDING frame? */
100 unsigned int peer_stop_sending
: 1;
101 /* Has our peer sent a RESET_STREAM frame? */
102 unsigned int peer_reset_stream
: 1;
104 /* Temporary flags used by TXP. */
105 unsigned int txp_sent_fc
: 1;
106 unsigned int txp_sent_stop_sending
: 1;
107 unsigned int txp_sent_reset_stream
: 1;
108 unsigned int txp_drained
: 1;
109 unsigned int txp_blocked
: 1;
111 /* Frame regeneration flags. */
112 unsigned int want_max_stream_data
: 1; /* used for regen only */
113 unsigned int want_stop_sending
: 1; /* used for gen or regen */
114 unsigned int want_reset_stream
: 1; /* used for gen or regen */
116 /* Flags set when frames *we* sent were acknowledged. */
117 unsigned int acked_stop_sending
: 1;
118 unsigned int acked_reset_stream
: 1;
120 /* A FIN has been retired from the rstream buffer. */
121 unsigned int recv_fin_retired
: 1;
124 * The stream's XSO has been deleted. Pending GC.
126 * Here is how stream deletion works:
128 * - A QUIC_STREAM cannot be deleted until it is neither in the accept
129 * queue nor has an associated XSO. This condition occurs when and only
130 * when deleted is true.
132 * - Once this is the case (i.e., no user-facing API object exposing the
133 * stream), we can delete the stream once we determine that all of our
134 * protocol obligations requiring us to keep the QUIC_STREAM around have
137 * The following frames relate to the streams layer for a specific
143 * Ignore for a deleted stream.
145 * (This is different from our obligation for a
146 * locally-initiated stream ID we have not created yet,
147 * which we must treat as a protocol error. This can be
148 * distinguished via a simple monotonic counter.)
151 * None, once we've decided to (someday) delete the stream.
155 * We cannot delete the stream until we have finished informing
156 * the peer that we are not going to be listening to it
160 * When we delete a stream we must have already had a FIN
161 * or RESET_STREAM we transmitted acknowledged by the peer.
162 * Thus we can ignore STOP_SENDING frames for deleted
163 * streams (if they occur, they are probably just
167 * _Acknowledged_ receipt of a STOP_SENDING frame by the
168 * peer (unless the peer's send part has already FIN'd).
172 * We cannot delete the stream until we have finished informing
173 * the peer that we are not going to be transmitting on it
177 * This indicates the peer is not going to send any more
178 * data on the stream. We don't need to care about this
179 * since once a stream is marked for deletion we don't care
180 * about any data it does send. We can ignore this for
181 * deleted streams. The important criterion is that the
182 * peer has been successfully delivered our STOP_SENDING
186 * _Acknowledged_ receipt of a RESET_STREAM frame or FIN by
192 * Ignore. Since we are not going to be sending any more
193 * data on a stream once it has been marked for deletion,
194 * we don't need to care about flow control information.
199 * In other words, our protocol obligation is simply:
202 * - the peer has acknowledged receipt of a STOP_SENDING frame sent
204 * - we have received a FIN and all preceding segments from the peer
206 * [NOTE: The actual criterion required here is simply 'we have
207 * received a FIN from the peer'. However, due to reordering and
208 * retransmissions we might subsequently receive non-FIN segments
209 * out of order. The FIN means we know the peer will stop
210 * transmitting on the stream at *some* point, but by sending
211 * STOP_SENDING we can avoid these needless retransmissions we
212 * will just ignore anyway. In actuality we could just handle all
213 * cases by sending a STOP_SENDING. The strategy we choose is to
214 * only avoid sending a STOP_SENDING and rely on a received FIN
215 * when we have received all preceding data, as this makes it
216 * reasonably certain no benefit would be gained by sending
219 * TODO(QUIC): Implement the latter case (currently we just
220 * always do STOP_SENDING).
224 * - we have drained our send stream (for a finished send stream)
225 * and got acknowledgement all parts of it including the FIN, or
226 * sent a RESET_STREAM frame and got acknowledgement of that frame.
228 * Once these conditions are met, we can GC the QUIC_STREAM.
231 unsigned int deleted
: 1;
232 /* Set to 1 once the above conditions are actually met. */
233 unsigned int ready_for_gc
: 1;
240 * The QUIC stream map:
242 * - maps stream IDs to QUIC_STREAM objects;
243 * - tracks which streams are 'active' (currently have data for transmission);
244 * - allows iteration over the active streams only.
247 typedef struct quic_stream_map_st
{
248 LHASH_OF(QUIC_STREAM
) *map
;
249 QUIC_STREAM_LIST_NODE active_list
;
250 QUIC_STREAM_LIST_NODE accept_list
;
251 QUIC_STREAM_LIST_NODE ready_for_gc_list
;
252 size_t rr_stepping
, rr_counter
, num_accept
;
254 uint64_t (*get_stream_limit_cb
)(int uni
, void *arg
);
255 void *get_stream_limit_cb_arg
;
256 QUIC_RXFC
*max_streams_bidi_rxfc
;
257 QUIC_RXFC
*max_streams_uni_rxfc
;
262 * get_stream_limit is a callback which is called to retrieve the current stream
263 * limit for streams created by us. This mechanism is not used for
264 * peer-initiated streams. If a stream's stream ID is x, a stream is allowed if
265 * (x >> 2) < returned limit value; i.e., the returned value is exclusive.
267 * If uni is 1, get the limit for locally-initiated unidirectional streams, else
268 * get the limit for locally-initiated bidirectional streams.
270 * If the callback is NULL, stream limiting is not applied.
271 * Stream limiting is used to determine if frames can currently be produced for
274 int ossl_quic_stream_map_init(QUIC_STREAM_MAP
*qsm
,
275 uint64_t (*get_stream_limit_cb
)(int uni
, void *arg
),
276 void *get_stream_limit_cb_arg
,
277 QUIC_RXFC
*max_streams_bidi_rxfc
,
278 QUIC_RXFC
*max_streams_uni_rxfc
,
282 * Any streams still in the map will be released as though
283 * ossl_quic_stream_map_release was called on them.
285 void ossl_quic_stream_map_cleanup(QUIC_STREAM_MAP
*qsm
);
287 #define QUIC_STREAM_INITIATOR_CLIENT 0
288 #define QUIC_STREAM_INITIATOR_SERVER 1
289 #define QUIC_STREAM_INITIATOR_MASK 1
291 #define QUIC_STREAM_DIR_BIDI 0
292 #define QUIC_STREAM_DIR_UNI 2
293 #define QUIC_STREAM_DIR_MASK 2
295 static ossl_inline ossl_unused
int ossl_quic_stream_is_server_init(QUIC_STREAM
*s
)
297 return (s
->type
& QUIC_STREAM_INITIATOR_MASK
) == QUIC_STREAM_INITIATOR_SERVER
;
300 static ossl_inline ossl_unused
int ossl_quic_stream_is_bidi(QUIC_STREAM
*s
)
302 return (s
->type
& QUIC_STREAM_DIR_MASK
) == QUIC_STREAM_DIR_BIDI
;
306 * Allocate a new stream. type is a combination of one QUIC_STREAM_INITIATOR_*
307 * value and one QUIC_STREAM_DIR_* value. Note that clients can e.g. allocate
308 * server-initiated streams as they will need to allocate a QUIC_STREAM
309 * structure to track any stream created by the server, etc.
311 * stream_id must be a valid value. Returns NULL if a stream already exists
314 QUIC_STREAM
*ossl_quic_stream_map_alloc(QUIC_STREAM_MAP
*qsm
,
319 * Releases a stream object. Note that this must only be done once the teardown
320 * process is entirely complete and the object will never be referenced again.
322 void ossl_quic_stream_map_release(QUIC_STREAM_MAP
*qsm
, QUIC_STREAM
*stream
);
325 * Calls visit_cb() for each stream in the map. visit_cb_arg is an opaque
326 * argument which is passed through.
328 void ossl_quic_stream_map_visit(QUIC_STREAM_MAP
*qsm
,
329 void (*visit_cb
)(QUIC_STREAM
*stream
, void *arg
),
333 * Retrieves a stream by stream ID. Returns NULL if it does not exist.
335 QUIC_STREAM
*ossl_quic_stream_map_get_by_id(QUIC_STREAM_MAP
*qsm
,
339 * Marks the given stream as active or inactive based on its state. Idempotent.
341 * When a stream is marked active, it becomes available in the iteration list,
342 * and when a stream is marked inactive, it no longer appears in the iteration
345 * Calling this function invalidates any iterator currently pointing at the
346 * given stream object, but iterators not currently pointing at the given stream
347 * object are not invalidated.
349 void ossl_quic_stream_map_update_state(QUIC_STREAM_MAP
*qsm
, QUIC_STREAM
*s
);
352 * Sets the RR stepping value, n. The RR rotation will be advanced every n
353 * packets. The default value is 1.
355 void ossl_quic_stream_map_set_rr_stepping(QUIC_STREAM_MAP
*qsm
, size_t stepping
);
358 * Resets the sending part of a stream.
360 * Returns 1 if the sending part of a stream was not already reset.
361 * Returns 0 otherwise, which need not be considered an error.
363 int ossl_quic_stream_map_reset_stream_send_part(QUIC_STREAM_MAP
*qsm
,
368 * Marks the receiving part of a stream for STOP_SENDING.
370 * Returns 1 if the receiving part of a stream was not already marked for
372 * Returns 0 otherwise, which need not be considered an error.
374 int ossl_quic_stream_map_stop_sending_recv_part(QUIC_STREAM_MAP
*qsm
,
379 * Adds a stream to the accept queue.
381 void ossl_quic_stream_map_push_accept_queue(QUIC_STREAM_MAP
*qsm
,
385 * Returns the next item to be popped from the accept queue, or NULL if it is
388 QUIC_STREAM
*ossl_quic_stream_map_peek_accept_queue(QUIC_STREAM_MAP
*qsm
);
391 * Removes a stream from the accept queue. rtt is the estimated connection RTT.
392 * The stream is retired for the purposes of MAX_STREAMS RXFC.
394 * Precondition: s is in the accept queue.
396 void ossl_quic_stream_map_remove_from_accept_queue(QUIC_STREAM_MAP
*qsm
,
400 /* Returns the length of the accept queue. */
401 size_t ossl_quic_stream_map_get_accept_queue_len(QUIC_STREAM_MAP
*qsm
);
404 * Delete streams ready for GC. Pointers to those QUIC_STREAM objects become
407 void ossl_quic_stream_map_gc(QUIC_STREAM_MAP
*qsm
);
410 * QUIC Stream Iterator
411 * ====================
413 * Allows the current set of active streams to be walked using a RR-based
414 * algorithm. Each time ossl_quic_stream_iter_init is called, the RR algorithm
415 * is stepped. The RR algorithm rotates the iteration order such that the next
416 * active stream is returned first after n calls to ossl_quic_stream_iter_init,
417 * where n is the stepping value configured via
418 * ossl_quic_stream_map_set_rr_stepping.
420 * Suppose there are three active streams and the configured stepping is n:
422 * Iteration 0n: [Stream 1] [Stream 2] [Stream 3]
423 * Iteration 1n: [Stream 2] [Stream 3] [Stream 1]
424 * Iteration 2n: [Stream 3] [Stream 1] [Stream 2]
427 typedef struct quic_stream_iter_st
{
428 QUIC_STREAM_MAP
*qsm
;
429 QUIC_STREAM
*first_stream
, *stream
;
433 * Initialise an iterator, advancing the RR algorithm as necessary (if
434 * advance_rr is 1). After calling this, it->stream will be the first stream in
435 * the iteration sequence, or NULL if there are no active streams.
437 void ossl_quic_stream_iter_init(QUIC_STREAM_ITER
*it
, QUIC_STREAM_MAP
*qsm
,
441 * Advances to next stream in iteration sequence. You do not need to call this
442 * immediately after calling ossl_quic_stream_iter_init(). If the end of the
443 * list is reached, it->stream will be NULL after calling this.
445 void ossl_quic_stream_iter_next(QUIC_STREAM_ITER
*it
);