designs/quic-design/quic-fifm.md

QUIC Frame-in-Flight Management
===============================

The QUIC frame-in-flight manager is responsible for tracking frames which were
sent which need to be regenerated if the packets they were placed into are
designated as lost by the ACK manager. The ACK manager works on the level of
packets, whereas the QUIC frame-in-flight manager (FIFM) works on the level of
frames.

The FIFM comprises three components, collectively known as the FIFM:

  - the Control Frame Queue (CFQ);
  - the Transmitted Packet Information Manager (TXPIM); and
  - the Frame-in-Flight Dispatcher (FIFD).

![](images/quic-fifm-overview.png "QUIC FIFM Overview")

These are introduced in turn below, but first we discuss the various QUIC frame
types to establish the need for each component.

Analysis of QUIC Frame Retransmission Requirements
--------------------------------------------------

### Frame Types

Standard QUIC uses the following frame types:

```plain
HANDSHAKE_DONE          GCR / REGEN
MAX_DATA                      REGEN
DATA_BLOCKED                  REGEN
MAX_STREAMS                   REGEN
STREAMS_BLOCKED               REGEN
NEW_CONNECTION_ID             GCR
RETIRE_CONNECTION_ID          GCR
PATH_CHALLENGE                  -
PATH_RESPONSE                   -
ACK                             -        (non-ACK-eliciting)
CONNECTION_CLOSE              special    (non-ACK-eliciting)
NEW_TOKEN                     GCR
CRYPTO                        GCR or special
RESET_STREAM                  REGEN
STOP_SENDING                  REGEN
MAX_STREAM_DATA               REGEN
STREAM_DATA_BLOCKED           REGEN
STREAM                        special
PING                           -
PADDING                        -         (non-ACK-eliciting)
```

The different frame types require various different ways of handling
retransmission in the event of loss:

  - **GCR** (Generic Control Frame Retransmission): The raw bytes of
    the encoded frame can simply be sent again. This retransmission system does
    not need to understand the specific frame type. A simple queue can be used,
    with each queue entry being an octet string representing an encoded frame.
    This queue can also be used for initial transmission of **GCR** frames, not
    just retransmissions.

  - **REGEN** (Regenerate): These frames can be marked for dynamic regeneration
    when a packet containing them is lost. This has the advantage of using
    up-to-date data at the time of transmission, so is preferred over `GCR` when
    possible.

  - Special — `STREAM`, `CRYPTO`: `STREAM` frame handling is handled as a
    special case by the QUIC Send Stream Manager. `CRYPTO` frame retransmission
    can also be handled using a QUIC Send Stream manager. (`CRYPTO` frames could
    also be handled via GCR, though suboptimally. We choose to use proper send
    stream management, just as for application data streams.)

  - Some frame types do not need to be retransmitted even if lost (`PING`,
    `PADDING`, `PATH_CHALLENGE`, `PATH_RESPONSE`).

  - Special — `CONNECTION_CLOSE`: This frame is a special case and is not
    retransmitted per se.

### Requirements

The following requirements are identified:

- Need for a generic control queue which can store encoded control frames.
  This control queue will handle both initial transmission and retransmission of
  most control frames which do not have special requirements.

- The ability to determine, when the ACK Manager determines that a packet has
  been acknowledged, lost or discarded:

  - What stream IDs were sent in a packet, and the logical ranges of application
    data bytes for each (which may not be one contiguous range).

    This is needed so that the QUIC Send Stream Manager for a given stream
    can be informed of lost or acked ranges in the stream.

  - The logical ranges of the CRYPTO stream which were sent in the packet
    (which may not be one contiguous range), for similar reasons.

  - Which stream IDs had a FIN bit set in the packet.

    This is needed so that the QUIC Send Stream Manager can be informed for a
    given stream whether a FIN was lost or acked.

  - What control frames using the **GCR** strategy were sent in the packet
    so that they can be requeued (if lost) or released (if acked or discarded).

  - For each type of frame using the **REGEN** strategy, a flag as to whether
    that frame type was contained in the packet (so that the flag can be set
    again if the packet was lost).

The Control Frame Queue (CFQ)
-----------------------------

![](images/quic-fifm-cfq.png "QUIC CFQ Overview")

The CFQ (`QUIC_CFQ`) stores encoded frames which can be blindly retransmitted in
the event that they are lost. It facilitates the GCR retransmission strategy.
One logical CFQ instance will be needed per PN space per connection. As an
optimisation, these three CFQ instances per connection are all modelled by a
single `QUIC_CFQ` instance.

Each frame in the CFQ is a simple opaque byte buffer, which has the following
metadata associated with it:

- An integral priority value, used to maintain priority ordering.

- The frame type, which is provided by the caller along with the buffer.
  This can be determined from the encoded frame buffer, but this saves the
  CFQ's users from needing to decode it. The CFQ itself does not use this
  value.

- A state, which is either `NEW` or `TX`. Frames added to the CFQ have
  the `NEW` state initially. When the frame is transmitted, it is transitioned
  to the `TX` state. If the packet it was sent in is subsequently lost,
  it is transitioned back to the `NEW` state.

Frames in the `NEW` state participate in a priority queue (the NEW queue)
according to their priority and the CFQ's NEW queue can be iterated in priority
order by callers.

When a packet containing a CFQ item is acknowledged, the CFQ is informed and the
CFQ item is released. A free callback provided when the buffer was added to the
CFQ is called, providing an opportunity to free or reuse the buffer. Buffers
provided to the CFQ as part of a CFQ item must remain allocated for the duration
of their membership of the CFQ. The CFQ maintains memory allocation of CFQ items
themselves internally.

### API

```c
/*
 * QUIC Control Frame Queue Item
 * =============================
 *
 * The CFQ item structure has a public and a private part. This structure
 * documents the public part.
 */
typedef struct quic_cfq_item_st QUIC_CFQ_ITEM;

struct quic_cfq_item_st {
    /*
     * These fields are not used by the CFQ, but are a convenience to assist the
     * TXPIM in keeping a list of GCR control frames which were sent in a
     * packet. They may be used for any purpose.
     */
    QUIC_CFQ_ITEM  *pkt_prev, *pkt_next;

    /* All other fields are private; use ossl_quic_cfq_item_* accessors. */
};

#define QUIC_CFQ_STATE_NEW      0
#define QUIC_CFQ_STATE_TX       1

/* Returns the frame type of a CFQ item. */
uint64_t ossl_quic_cfq_item_get_frame_type(QUIC_CFQ_ITEM *item);

/* Returns a pointer to the encoded buffer of a CFQ item. */
const unsigned char *ossl_quic_cfq_item_get_encoded(QUIC_CFQ_ITEM *item);

/* Returns the length of the encoded buffer in bytes. */
size_t ossl_quic_cfq_item_get_encoded_len(QUIC_CFQ_ITEM *item);

/* Returns the CFQ item state, a QUIC_CFQ_STATE_* value. */
int ossl_quic_cfg_item_get_state(QUIC_CFQ_ITEM *item);

/* Returns the PN space for the CFQ item. */
int ossl_quic_cfg_item_get_pn_space(QUIC_CFQ_ITEM *item);

/*
 * QUIC Control Frame Queue
 * ========================
 */
typedef struct quic_cfq_st QUIC_CFQ;

QUIC_CFQ *ossl_quic_cfq_new(void);
void ossl_quic_cfq_free(QUIC_CFQ *cfq);

/*
 * Input Side
 * ----------
 */

/*
 * Enqueue a frame to the CFQ. encoded points to the opaque encoded frame.
 *
 * free_cb is called by the CFQ when the buffer is no longer needed;
 * free_cb_arg is an opaque value passed to free_cb.
 *
 * priority determines the relative ordering of control frames in a packet.
 * Higher numerical values for priority mean that a frame should come earlier in
 * a packet. pn_space is a QUIC_PN_SPACE_* value.
 *
 * On success, returns a QUIC_CFQ_ITEM pointer which acts as a handle to
 * the queued frame. On failure, returns NULL.
 *
 * The frame is initially in the TX state, so there is no need to call
 * ossl_quic_cfq_mark_tx() immediately after calling this function.
 *
 * The frame type is duplicated as the frame_type argument here, even though it
 * is also encoded into the buffer. This allows the caller to determine the
 * frame type if desired without having to decode the frame.
 */
typedef void (cfq_free_cb)(unsigned char *buf, size_t buf_len, void *arg);

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);

/*
 * Effects an immediate transition of the given CFQ item to the TX state.
 */
void ossl_quic_cfq_mark_tx(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item);

/*
 * Effects an immediate transition of the given CFQ item to the NEW state,
 * allowing the frame to be retransmitted. If priority is not UINT32_MAX,
 * the priority is changed to the given value.
 */
void ossl_quic_cfq_mark_lost(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item,
                             uint32_t priority);

/*
 * 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);

/*
 * Output Side
 * -----------
 */

/*
 * Gets the highest priority CFQ item in the given PN space awaiting
 * transmission. If there are none, returns NULL.
 */
QUIC_CFQ_ITEM *ossl_quic_cfq_get_priority_head(QUIC_CFQ *cfq, uint32_t pn_space);

/*
 * Given a CFQ item, gets the next CFQ item awaiting transmission in priority
 * order in the given PN space. In other words, given the return value of
 * ossl_quic_cfq_get_priority_head(), returns the next-lower priority item.
 * Returns NULL if the given item is the last item in priority order.
 */
QUIC_CFQ_ITEM *ossl_quic_cfq_item_get_priority_next(QUIC_CFQ_ITEM *item,
                                                    uint32_t pn_space);
```

The Transmitted Packet Information Manager (TXPIM)
--------------------------------------------------

![](images/quic-fifm-txpim.png "QUIC TXPIM Overview")

The Transmitted Packet Information Manager (`QUIC_TXPIM`) is responsible for
allocating and keeping bookkeeping structures for packets which have been
transmitted, but not yet acknowledged, deemed lost or discarded. It is a
self-contained memory pool handing out `QUIC_TXPIM_PKT` structures. Each
`QUIC_TXPIM_PKT` is a self-contained data structure intended for consumption by
the FIFM.

The `QUIC_TXPIM_PKT` structure can be used for:

  - Keeping track of all GCR control frames which were transmitted
    in each packet, via a linked list of `QUIC_CFQ_ITEM`s.

  - Keeping track of all REGEN-strategy control frame types, via a flag
    for each frame type indicating whether the packet contained
    such a frame.

  - Keeping track of all stream IDs sent in a given packet, and
    what ranges of the logical stream were sent, and whether
    a FIN was sent.

  - Keeping track of what logical ranges of the CRYPTO stream were sent.

In order to avoid unnecessary allocations, the FIFM also incorporates the ACK
Manager's `QUIC_ACKM_TX_PKT` structure into its per-packet bookkeeping
structure. The intention is for the `QUIC_TXPIM_PKT` to be the principal
allocation made per transmitted packet. The TX packetiser will obtain
a `QUIC_TXPIM_PKT` structure from the TXPIM, fill in the structure including
the ACK Manager data, and submit it via the FIFD which we introduce below.

The TXPIM does do not anything with the `QUIC_TXPIM_PKT` structure itself other
than managing its allocation and manipulation. Constructive use of the data kept
in the TXPIM is made by the FIFD.

### API

```c
/*
 * QUIC Transmitted Packet Information Manager
 * ===========================================
 */
typedef struct quic_txpim_st QUIC_TXPIM;

typedef struct quic_txpim_pkt_st {
    /* ACKM-specific data. Caller should fill this. */
    QUIC_ACKM_TX_PKT    ackm_pkt;

    /* Linked list of CFQ items in this packet. */
    QUIC_CFQ_ITEM      *retx_head;

    /* Reserved for FIFD use. */
    QUIC_FIFD          *fifd;

    /* Regenerate-strategy frames. */
    unsigned int        had_handshake_done          : 1;
    unsigned int        had_max_data_frame          : 1;
    unsigned int        had_max_streams_bidi_frame  : 1;
    unsigned int        had_max_streams_uni_frame   : 1;
    unsigned int        had_ack_frame               : 1;

    /* Private data follows. */
} QUIC_TXPIM_PKT;

/* Represents a range of bytes in an application or CRYPTO stream. */
typedef struct quic_txpim_chunk_st {
    /* The stream ID, or UINT64_MAX for the CRYPTO stream. */
    uint64_t        stream_id;
    /*
     * The inclusive range of bytes in the stream. Exceptionally, if end <
     * start, designates a frame of zero length (used for FIN-only frames).
     */
    uint64_t        start, end;
    /*
     * Whether a FIN was sent for this stream in the packet. Not valid for
     * CRYPTO stream.
     */
    unsigned int    has_fin : 1;
} QUIC_TXPIM_CHUNK;

QUIC_TXPIM *ossl_quic_txpim_new(void);
void ossl_quic_txpim_free(QUIC_TXPIM *txpim);

/*
 * Allocates a new QUIC_TXPIM_PKT structure from the pool. Returns NULL on
 * failure. The returned structure is cleared of all data and is in a fresh
 * initial state.
 */
QUIC_TXPIM_PKT *ossl_quic_txpim_pkt_alloc(QUIC_TXPIM *txpim);

/*
 * Releases the TXPIM packet, returning it to the pool.
 */
void ossl_quic_txpim_pkt_release(QUIC_TXPIM *txpim, QUIC_TXPIM_PKT *fpkt);

/* Clears the chunk list of the packet, removing all entries. */
void ossl_quic_txpim_pkt_clear_chunks(QUIC_TXPIM_PKT *fpkt);

/* Appends a chunk to the packet. The structure is copied. */
int ossl_quic_txpim_pkt_append_chunk(QUIC_TXPIM_PKT *fpkt,
                                    const QUIC_TXPIM_CHUNK *chunk);

/* Adds a CFQ item to the packet by prepending it to the retx_head list. */
void ossl_quic_txpim_pkt_add_cfq_item(QUIC_TXPIM_PKT *fpkt,
                                      QUIC_CFQ_ITEM *item);

/*
 * Returns a pointer to an array of stream chunk information structures for the
 * given packet. The caller must call ossl_quic_txpim_pkt_get_num_chunks() to
 * determine the length of this array.
 *
 * The chunks are sorted by (stream_id, start) in ascending order.
 */
const QUIC_TXPIM_CHUNK *ossl_quic_txpim_pkt_get_chunks(QUIC_TXPIM_PKT *fpkt);

/*
 * Returns the number of entries in the array returned by
 * ossl_quic_txpim_pkt_get_chunks().
 */
size_t ossl_quic_txpim_pkt_get_num_chunks(QUIC_TXPIM_PKT *fpkt);

/*
 * Returns the number of QUIC_TXPIM_PKTs allocated by the given TXPIM that have
 * yet to be returned to the TXPIM.
 */
size_t ossl_quic_txpim_get_in_use(QUIC_TXPIM *txpim);
```

The Frame-in-Flight Dispatcher (FIFD)
-------------------------------------

Finally, the CFQ, TXPIM and some interfaces to the ACKM are tied together via
the FIFD (`QUIC_FIFD`). The FIFD is completely stateless and provides reasonable
implementations for the on-loss, on-acked and on-discarded callbacks issued by
the ACK Manager.

The FIFD is used by obtaining a packet structure from the TXPIM, filling it in,
and then calling `ossl_quic_fifd_pkt_commit()`. The FIFD submits the packet to
the ACK Manager as a transmitted packet and provides its own callback
implementations to the ACK Manager for the packet. Note that the
`QUIC_TXPIM_PKT` is returned to the free pool once any of these callbacks occur;
once a packet's fate is known (acked, lost or discarded), use is immediately
made of the information in the `QUIC_TXPIM_PKT` and the `QUIC_TXPIM_PKT` is
immediately released. CFQ items may be freed (on ACK or discard) or transitioned
back to the NEW state (on loss).

The FIFD consumes various dependencies so that it can inform the appropriate
subsystems in the event of a packet being acked, lost or discarded. In
particular:

- It references a CFQ used to manage CFQ items;
- It references an ACK manager which it informs of transmitted packets;
- It references a TXPIM which manages each `QUIC_TXPIM_PKT`;
- It is provided with a callback to obtain a QUIC Send Stream based on a stream
  ID. Thus the caller of the FIFD may implement whatever strategy it likes
  to map stream IDs to QUIC Send Stream instances.
- It is provided with a callback which is called when it thinks a frame
  should be regenerated using the REGEN strategy. Some of these are specific
  to a given stream, in which case a stream ID is specified.

All of the state is in the dependencies referenced by the FIFD. The FIFD itself
simply glues all of these parts together.

### API

```c
typedef struct quic_fifd_st {
  /* (internals) */
} QUIC_FIFD;

int ossl_quic_fifd_init(QUIC_FIFD *fifd,
                        QUIC_CFQ *cfq,
                        QUIC_ACKM *ackm,
                        QUIC_TXPIM *txpim,
                        /* stream_id is UINT64_MAX for the crypto stream */
                        OSSL_QSS *(*get_qss_by_id)(uint64_t stream_id,
                                                   void *arg),
                        void *get_qss_by_id_arg,
                        /* stream_id is UINT64_MAX if not applicable */
                        void (*regen_frame)(uint64_t frame_type,
                                            uint64_t stream_id,
                                            void *arg),
                        void *regen_frame_arg);
void ossl_quic_fifd_cleanup(QUIC_FIFD *fifd); /* (no-op) */

int ossl_quic_fifd_pkt_commit(QUIC_FIFD *fifd, QUIC_TXPIM_PKT *pkt);
```

Typical Intended TX Packetiser Usage
------------------------------------

- TX Packetiser maintains flags for each REGEN-strategy frame type.
  It sets this flag when the regenerate callback is issued by the FIFD
  and clears it when transmitting a packet containing such a frame.

- TX Packetiser obtains a `QUIC_TXPIM_PKT` structure by calling
  `ossl_quic_txpim_pkt_alloc()`.

- TX Packetiser fills in the ACKM part of the `QUIC_TXPIM_PKT`
  (`QUIC_ACKM_TX_PKT`), except for the callback fields, which are handled by the
  FIFD.

- TX Packetiser queries the ACK Manager to determine if an ACK frame
  is desired, and if so adds it to the packet.

- TX Packetiser queries the CFQ to determine what control frames it places
  in a packet. It does this before adding STREAM or CRYPTO frames (i.e.,
  all CFQ frames are considered of higher priority). For each such frame
  it places in a packet, it:

  - calls `ossl_quic_txpim_pkt_add_cfq_item()` on the TXPIM to log the CFQ item
    as having been transmitted in the given packet, so that the CFQ item can be
    released or requeued depending on the ultimate fate of the packet.

- For each STREAM or CRYPTO frame included in a packet, the TX Packetiser:

  - informs the QUIC Send Stream instance for that stream that a range of bytes
    has been transmitted;

  - also informs the QUIC Send Stream instance if FIN was set on a STREAM frame.

  - calls `ossl_quic_txpim_pkt_append_chunk()` to log a logical range of
    the given application or crypto stream as having been sent, so that it can
    be subsequently marked as acknowledged or lost depending on the ultimate
    fate of the packet.

- TX Packetiser calls `ossl_quic_fifd_pkt_commit()`. The FIFD takes care
  of submitting the packet to the ACK Manager and provides its own callback
  implementation. It also takes care of informing the CFQ that any CFQ items
  which were added via `ossl_quic_txpim_pkt_add_cfq_item()` have been
  transmitted.

  In the event of packet loss, ACK or discard, the appropriate QUIC Send Stream,
  CFQ and regenerate callback calls are made. Regardless of the outcome, the
  TXPIM is released.