1 QUIC Frame-in-Flight Management 2 =============================== 3 4 The QUIC frame-in-flight manager is responsible for tracking frames which were 5 sent which need to be regenerated if the packets they were placed into are 6 designated as lost by the ACK manager. The ACK manager works on the level of 7 packets, whereas the QUIC frame-in-flight manager (FIFM) works on the level of 8 frames. 9 10 The FIFM comprises three components, collectively known as the FIFM: 11 12 - the Control Frame Queue (CFQ); 13 - the Transmitted Packet Information Manager (TXPIM); and 14 - the Frame-in-Flight Dispatcher (FIFD). 15 16  17 18 These are introduced in turn below, but first we discuss the various QUIC frame 19 types to establish the need for each component. 20 21 Analysis of QUIC Frame Retransmission Requirements 22 -------------------------------------------------- 23 24 ### Frame Types 25 26 Standard QUIC uses the following frame types: 27 28 ```plain 29 HANDSHAKE_DONE GCR / REGEN 30 MAX_DATA REGEN 31 DATA_BLOCKED REGEN 32 MAX_STREAMS REGEN 33 STREAMS_BLOCKED REGEN 34 NEW_CONNECTION_ID GCR 35 RETIRE_CONNECTION_ID GCR 36 PATH_CHALLENGE - 37 PATH_RESPONSE - 38 ACK - (non-ACK-eliciting) 39 CONNECTION_CLOSE special (non-ACK-eliciting) 40 NEW_TOKEN GCR 41 CRYPTO GCR or special 42 RESET_STREAM REGEN 43 STOP_SENDING REGEN 44 MAX_STREAM_DATA REGEN 45 STREAM_DATA_BLOCKED REGEN 46 STREAM special 47 PING - 48 PADDING - (non-ACK-eliciting) 49 ``` 50 51 The different frame types require various different ways of handling 52 retransmission in the event of loss: 53 54 - **GCR** (Generic Control Frame Retransmission): The raw bytes of 55 the encoded frame can simply be sent again. This retransmission system does 56 not need to understand the specific frame type. A simple queue can be used, 57 with each queue entry being an octet string representing an encoded frame. 58 This queue can also be used for initial transmission of **GCR** frames, not 59 just retransmissions. 60 61 - **REGEN** (Regenerate): These frames can be marked for dynamic regeneration 62 when a packet containing them is lost. This has the advantage of using 63 up-to-date data at the time of transmission, so is preferred over `GCR` when 64 possible. 65 66 - Special `STREAM`, `CRYPTO`: `STREAM` frame handling is handled as a 67 special case by the QUIC Send Stream Manager. `CRYPTO` frame retransmission 68 can also be handled using a QUIC Send Stream manager. (`CRYPTO` frames could 69 also be handled via GCR, though suboptimally. We choose to use proper send 70 stream management, just as for application data streams.) 71 72 - Some frame types do not need to be retransmitted even if lost (`PING`, 73 `PADDING`, `PATH_CHALLENGE`, `PATH_RESPONSE`). 74 75 - Special `CONNECTION_CLOSE`: This frame is a special case and is not 76 retransmitted per se. 77 78 ### Requirements 79 80 The following requirements are identified: 81 82 - Need for a generic control queue which can store encoded control frames. 83 This control queue will handle both initial transmission and retransmission of 84 most control frames which do not have special requirements. 85 86 - The ability to determine, when the ACK Manager determines that a packet has 87 been acknowledged, lost or discarded: 88 89 - What stream IDs were sent in a packet, and the logical ranges of application 90 data bytes for each (which may not be one contiguous range). 91 92 This is needed so that the QUIC Send Stream Manager for a given stream 93 can be informed of lost or acked ranges in the stream. 94 95 - The logical ranges of the CRYPTO stream which were sent in the packet 96 (which may not be one contiguous range), for similar reasons. 97 98 - Which stream IDs had a FIN bit set in the packet. 99 100 This is needed so that the QUIC Send Stream Manager can be informed for a 101 given stream whether a FIN was lost or acked. 102 103 - What control frames using the **GCR** strategy were sent in the packet 104 so that they can be requeued (if lost) or released (if acked or discarded). 105 106 - For each type of frame using the **REGEN** strategy, a flag as to whether 107 that frame type was contained in the packet (so that the flag can be set 108 again if the packet was lost). 109 110 The Control Frame Queue (CFQ) 111 ----------------------------- 112 113  114 115 The CFQ (`QUIC_CFQ`) stores encoded frames which can be blindly retransmitted in 116 the event that they are lost. It facilitates the GCR retransmission strategy. 117 One logical CFQ instance will be needed per PN space per connection. As an 118 optimisation, these three CFQ instances per connection are all modelled by a 119 single `QUIC_CFQ` instance. 120 121 Each frame in the CFQ is a simple opaque byte buffer, which has the following 122 metadata associated with it: 123 124 - An integral priority value, used to maintain priority ordering. 125 126 - The frame type, which is provided by the caller along with the buffer. 127 This can be determined from the encoded frame buffer, but this saves the 128 CFQ's users from needing to decode it. The CFQ itself does not use this 129 value. 130 131 - A state, which is either `NEW` or `TX`. Frames added to the CFQ have 132 the `NEW` state initially. When the frame is transmitted, it is transitioned 133 to the `TX` state. If the packet it was sent in is subsequently lost, 134 it is transitioned back to the `NEW` state. 135 136 Frames in the `NEW` state participate in a priority queue (the NEW queue) 137 according to their priority and the CFQ's NEW queue can be iterated in priority 138 order by callers. 139 140 When a packet containing a CFQ item is acknowledged, the CFQ is informed and the 141 CFQ item is released. A free callback provided when the buffer was added to the 142 CFQ is called, providing an opportunity to free or reuse the buffer. Buffers 143 provided to the CFQ as part of a CFQ item must remain allocated for the duration 144 of their membership of the CFQ. The CFQ maintains memory allocation of CFQ items 145 themselves internally. 146 147 ### API 148 149 ```c 150 /* 151 * QUIC Control Frame Queue Item 152 * ============================= 153 * 154 * The CFQ item structure has a public and a private part. This structure 155 * documents the public part. 156 */ 157 typedef struct quic_cfq_item_st QUIC_CFQ_ITEM; 158 159 struct quic_cfq_item_st { 160 /* 161 * These fields are not used by the CFQ, but are a convenience to assist the 162 * TXPIM in keeping a list of GCR control frames which were sent in a 163 * packet. They may be used for any purpose. 164 */ 165 QUIC_CFQ_ITEM *pkt_prev, *pkt_next; 166 167 /* All other fields are private; use ossl_quic_cfq_item_* accessors. */ 168 }; 169 170 #define QUIC_CFQ_STATE_NEW 0 171 #define QUIC_CFQ_STATE_TX 1 172 173 /* Returns the frame type of a CFQ item. */ 174 uint64_t ossl_quic_cfq_item_get_frame_type(QUIC_CFQ_ITEM *item); 175 176 /* Returns a pointer to the encoded buffer of a CFQ item. */ 177 const unsigned char *ossl_quic_cfq_item_get_encoded(QUIC_CFQ_ITEM *item); 178 179 /* Returns the length of the encoded buffer in bytes. */ 180 size_t ossl_quic_cfq_item_get_encoded_len(QUIC_CFQ_ITEM *item); 181 182 /* Returns the CFQ item state, a QUIC_CFQ_STATE_* value. */ 183 int ossl_quic_cfg_item_get_state(QUIC_CFQ_ITEM *item); 184 185 /* Returns the PN space for the CFQ item. */ 186 int ossl_quic_cfg_item_get_pn_space(QUIC_CFQ_ITEM *item); 187 188 /* 189 * QUIC Control Frame Queue 190 * ======================== 191 */ 192 typedef struct quic_cfq_st QUIC_CFQ; 193 194 QUIC_CFQ *ossl_quic_cfq_new(void); 195 void ossl_quic_cfq_free(QUIC_CFQ *cfq); 196 197 /* 198 * Input Side 199 * ---------- 200 */ 201 202 /* 203 * Enqueue a frame to the CFQ. encoded points to the opaque encoded frame. 204 * 205 * free_cb is called by the CFQ when the buffer is no longer needed; 206 * free_cb_arg is an opaque value passed to free_cb. 207 * 208 * priority determines the relative ordering of control frames in a packet. 209 * Higher numerical values for priority mean that a frame should come earlier in 210 * a packet. pn_space is a QUIC_PN_SPACE_* value. 211 * 212 * On success, returns a QUIC_CFQ_ITEM pointer which acts as a handle to 213 * the queued frame. On failure, returns NULL. 214 * 215 * The frame is initially in the TX state, so there is no need to call 216 * ossl_quic_cfq_mark_tx() immediately after calling this function. 217 * 218 * The frame type is duplicated as the frame_type argument here, even though it 219 * is also encoded into the buffer. This allows the caller to determine the 220 * frame type if desired without having to decode the frame. 221 */ 222 typedef void (cfq_free_cb)(unsigned char *buf, size_t buf_len, void *arg); 223 224 QUIC_CFQ_ITEM *ossl_quic_cfq_add_frame(QUIC_CFQ *cfq, 225 uint32_t priority, 226 uint32_t pn_space, 227 uint64_t frame_type, 228 const unsigned char *encoded, 229 size_t encoded_len, 230 cfq_free_cb *free_cb, 231 void *free_cb_arg); 232 233 /* 234 * Effects an immediate transition of the given CFQ item to the TX state. 235 */ 236 void ossl_quic_cfq_mark_tx(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item); 237 238 /* 239 * Effects an immediate transition of the given CFQ item to the NEW state, 240 * allowing the frame to be retransmitted. If priority is not UINT32_MAX, 241 * the priority is changed to the given value. 242 */ 243 void ossl_quic_cfq_mark_lost(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item, 244 uint32_t priority); 245 246 /* 247 * Releases a CFQ item. The item may be in either state (NEW or TX) prior to the 248 * call. The QUIC_CFQ_ITEM pointer must not be used following this call. 249 */ 250 void ossl_quic_cfq_release(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item); 251 252 /* 253 * Output Side 254 * ----------- 255 */ 256 257 /* 258 * Gets the highest priority CFQ item in the given PN space awaiting 259 * transmission. If there are none, returns NULL. 260 */ 261 QUIC_CFQ_ITEM *ossl_quic_cfq_get_priority_head(QUIC_CFQ *cfq, uint32_t pn_space); 262 263 /* 264 * Given a CFQ item, gets the next CFQ item awaiting transmission in priority 265 * order in the given PN space. In other words, given the return value of 266 * ossl_quic_cfq_get_priority_head(), returns the next-lower priority item. 267 * Returns NULL if the given item is the last item in priority order. 268 */ 269 QUIC_CFQ_ITEM *ossl_quic_cfq_item_get_priority_next(QUIC_CFQ_ITEM *item, 270 uint32_t pn_space); 271 ``` 272 273 The Transmitted Packet Information Manager (TXPIM) 274 -------------------------------------------------- 275 276  277 278 The Transmitted Packet Information Manager (`QUIC_TXPIM`) is responsible for 279 allocating and keeping bookkeeping structures for packets which have been 280 transmitted, but not yet acknowledged, deemed lost or discarded. It is a 281 self-contained memory pool handing out `QUIC_TXPIM_PKT` structures. Each 282 `QUIC_TXPIM_PKT` is a self-contained data structure intended for consumption by 283 the FIFM. 284 285 The `QUIC_TXPIM_PKT` structure can be used for: 286 287 - Keeping track of all GCR control frames which were transmitted 288 in each packet, via a linked list of `QUIC_CFQ_ITEM`s. 289 290 - Keeping track of all REGEN-strategy control frame types, via a flag 291 for each frame type indicating whether the packet contained 292 such a frame. 293 294 - Keeping track of all stream IDs sent in a given packet, and 295 what ranges of the logical stream were sent, and whether 296 a FIN was sent. 297 298 - Keeping track of what logical ranges of the CRYPTO stream were sent. 299 300 In order to avoid unnecessary allocations, the FIFM also incorporates the ACK 301 Manager's `QUIC_ACKM_TX_PKT` structure into its per-packet bookkeeping 302 structure. The intention is for the `QUIC_TXPIM_PKT` to be the principal 303 allocation made per transmitted packet. The TX packetiser will obtain 304 a `QUIC_TXPIM_PKT` structure from the TXPIM, fill in the structure including 305 the ACK Manager data, and submit it via the FIFD which we introduce below. 306 307 The TXPIM does do not anything with the `QUIC_TXPIM_PKT` structure itself other 308 than managing its allocation and manipulation. Constructive use of the data kept 309 in the TXPIM is made by the FIFD. 310 311 ### API 312 313 ```c 314 /* 315 * QUIC Transmitted Packet Information Manager 316 * =========================================== 317 */ 318 typedef struct quic_txpim_st QUIC_TXPIM; 319 320 typedef struct quic_txpim_pkt_st { 321 /* ACKM-specific data. Caller should fill this. */ 322 QUIC_ACKM_TX_PKT ackm_pkt; 323 324 /* Linked list of CFQ items in this packet. */ 325 QUIC_CFQ_ITEM *retx_head; 326 327 /* Reserved for FIFD use. */ 328 QUIC_FIFD *fifd; 329 330 /* Regenerate-strategy frames. */ 331 unsigned int had_handshake_done : 1; 332 unsigned int had_max_data_frame : 1; 333 unsigned int had_max_streams_bidi_frame : 1; 334 unsigned int had_max_streams_uni_frame : 1; 335 unsigned int had_ack_frame : 1; 336 337 /* Private data follows. */ 338 } QUIC_TXPIM_PKT; 339 340 /* Represents a range of bytes in an application or CRYPTO stream. */ 341 typedef struct quic_txpim_chunk_st { 342 /* The stream ID, or UINT64_MAX for the CRYPTO stream. */ 343 uint64_t stream_id; 344 /* 345 * The inclusive range of bytes in the stream. Exceptionally, if end < 346 * start, designates a frame of zero length (used for FIN-only frames). 347 */ 348 uint64_t start, end; 349 /* 350 * Whether a FIN was sent for this stream in the packet. Not valid for 351 * CRYPTO stream. 352 */ 353 unsigned int has_fin : 1; 354 } QUIC_TXPIM_CHUNK; 355 356 QUIC_TXPIM *ossl_quic_txpim_new(void); 357 void ossl_quic_txpim_free(QUIC_TXPIM *txpim); 358 359 /* 360 * Allocates a new QUIC_TXPIM_PKT structure from the pool. Returns NULL on 361 * failure. The returned structure is cleared of all data and is in a fresh 362 * initial state. 363 */ 364 QUIC_TXPIM_PKT *ossl_quic_txpim_pkt_alloc(QUIC_TXPIM *txpim); 365 366 /* 367 * Releases the TXPIM packet, returning it to the pool. 368 */ 369 void ossl_quic_txpim_pkt_release(QUIC_TXPIM *txpim, QUIC_TXPIM_PKT *fpkt); 370 371 /* Clears the chunk list of the packet, removing all entries. */ 372 void ossl_quic_txpim_pkt_clear_chunks(QUIC_TXPIM_PKT *fpkt); 373 374 /* Appends a chunk to the packet. The structure is copied. */ 375 int ossl_quic_txpim_pkt_append_chunk(QUIC_TXPIM_PKT *fpkt, 376 const QUIC_TXPIM_CHUNK *chunk); 377 378 /* Adds a CFQ item to the packet by prepending it to the retx_head list. */ 379 void ossl_quic_txpim_pkt_add_cfq_item(QUIC_TXPIM_PKT *fpkt, 380 QUIC_CFQ_ITEM *item); 381 382 /* 383 * Returns a pointer to an array of stream chunk information structures for the 384 * given packet. The caller must call ossl_quic_txpim_pkt_get_num_chunks() to 385 * determine the length of this array. 386 * 387 * The chunks are sorted by (stream_id, start) in ascending order. 388 */ 389 const QUIC_TXPIM_CHUNK *ossl_quic_txpim_pkt_get_chunks(QUIC_TXPIM_PKT *fpkt); 390 391 /* 392 * Returns the number of entries in the array returned by 393 * ossl_quic_txpim_pkt_get_chunks(). 394 */ 395 size_t ossl_quic_txpim_pkt_get_num_chunks(QUIC_TXPIM_PKT *fpkt); 396 397 /* 398 * Returns the number of QUIC_TXPIM_PKTs allocated by the given TXPIM that have 399 * yet to be returned to the TXPIM. 400 */ 401 size_t ossl_quic_txpim_get_in_use(QUIC_TXPIM *txpim); 402 ``` 403 404 The Frame-in-Flight Dispatcher (FIFD) 405 ------------------------------------- 406 407 Finally, the CFQ, TXPIM and some interfaces to the ACKM are tied together via 408 the FIFD (`QUIC_FIFD`). The FIFD is completely stateless and provides reasonable 409 implementations for the on-loss, on-acked and on-discarded callbacks issued by 410 the ACK Manager. 411 412 The FIFD is used by obtaining a packet structure from the TXPIM, filling it in, 413 and then calling `ossl_quic_fifd_pkt_commit()`. The FIFD submits the packet to 414 the ACK Manager as a transmitted packet and provides its own callback 415 implementations to the ACK Manager for the packet. Note that the 416 `QUIC_TXPIM_PKT` is returned to the free pool once any of these callbacks occur; 417 once a packet's fate is known (acked, lost or discarded), use is immediately 418 made of the information in the `QUIC_TXPIM_PKT` and the `QUIC_TXPIM_PKT` is 419 immediately released. CFQ items may be freed (on ACK or discard) or transitioned 420 back to the NEW state (on loss). 421 422 The FIFD consumes various dependencies so that it can inform the appropriate 423 subsystems in the event of a packet being acked, lost or discarded. In 424 particular: 425 426 - It references a CFQ used to manage CFQ items; 427 - It references an ACK manager which it informs of transmitted packets; 428 - It references a TXPIM which manages each `QUIC_TXPIM_PKT`; 429 - It is provided with a callback to obtain a QUIC Send Stream based on a stream 430 ID. Thus the caller of the FIFD may implement whatever strategy it likes 431 to map stream IDs to QUIC Send Stream instances. 432 - It is provided with a callback which is called when it thinks a frame 433 should be regenerated using the REGEN strategy. Some of these are specific 434 to a given stream, in which case a stream ID is specified. 435 436 All of the state is in the dependencies referenced by the FIFD. The FIFD itself 437 simply glues all of these parts together. 438 439 ### API 440 441 ```c 442 typedef struct quic_fifd_st { 443 /* (internals) */ 444 } QUIC_FIFD; 445 446 int ossl_quic_fifd_init(QUIC_FIFD *fifd, 447 QUIC_CFQ *cfq, 448 QUIC_ACKM *ackm, 449 QUIC_TXPIM *txpim, 450 /* stream_id is UINT64_MAX for the crypto stream */ 451 OSSL_QSS *(*get_qss_by_id)(uint64_t stream_id, 452 void *arg), 453 void *get_qss_by_id_arg, 454 /* stream_id is UINT64_MAX if not applicable */ 455 void (*regen_frame)(uint64_t frame_type, 456 uint64_t stream_id, 457 void *arg), 458 void *regen_frame_arg); 459 void ossl_quic_fifd_cleanup(QUIC_FIFD *fifd); /* (no-op) */ 460 461 int ossl_quic_fifd_pkt_commit(QUIC_FIFD *fifd, QUIC_TXPIM_PKT *pkt); 462 ``` 463 464 Typical Intended TX Packetiser Usage 465 ------------------------------------ 466 467 - TX Packetiser maintains flags for each REGEN-strategy frame type. 468 It sets this flag when the regenerate callback is issued by the FIFD 469 and clears it when transmitting a packet containing such a frame. 470 471 - TX Packetiser obtains a `QUIC_TXPIM_PKT` structure by calling 472 `ossl_quic_txpim_pkt_alloc()`. 473 474 - TX Packetiser fills in the ACKM part of the `QUIC_TXPIM_PKT` 475 (`QUIC_ACKM_TX_PKT`), except for the callback fields, which are handled by the 476 FIFD. 477 478 - TX Packetiser queries the ACK Manager to determine if an ACK frame 479 is desired, and if so adds it to the packet. 480 481 - TX Packetiser queries the CFQ to determine what control frames it places 482 in a packet. It does this before adding STREAM or CRYPTO frames (i.e., 483 all CFQ frames are considered of higher priority). For each such frame 484 it places in a packet, it: 485 486 - calls `ossl_quic_txpim_pkt_add_cfq_item()` on the TXPIM to log the CFQ item 487 as having been transmitted in the given packet, so that the CFQ item can be 488 released or requeued depending on the ultimate fate of the packet. 489 490 - For each STREAM or CRYPTO frame included in a packet, the TX Packetiser: 491 492 - informs the QUIC Send Stream instance for that stream that a range of bytes 493 has been transmitted; 494 495 - also informs the QUIC Send Stream instance if FIN was set on a STREAM frame. 496 497 - calls `ossl_quic_txpim_pkt_append_chunk()` to log a logical range of 498 the given application or crypto stream as having been sent, so that it can 499 be subsequently marked as acknowledged or lost depending on the ultimate 500 fate of the packet. 501 502 - TX Packetiser calls `ossl_quic_fifd_pkt_commit()`. The FIFD takes care 503 of submitting the packet to the ACK Manager and provides its own callback 504 implementation. It also takes care of informing the CFQ that any CFQ items 505 which were added via `ossl_quic_txpim_pkt_add_cfq_item()` have been 506 transmitted. 507 508 In the event of packet loss, ACK or discard, the appropriate QUIC Send Stream, 509 CFQ and regenerate callback calls are made. Regardless of the outcome, the 510 TXPIM is released. 511
Indexes created Sat Aug 22 00:26:31 UTC 2026