How QPACK Dynamic Table Works in XQUIC's HTTP/3 Implementation

XQUIC implements the QPACK dynamic table as a synchronized FIFO buffer living on both encoder and decoder sides, using a 2-D hash table for lookups and ring memory for storage, while coordinating via SET_DYNAMIC_TABLE_CAPACITY and INSERT_COUNT_INCREMENT instructions to enable efficient HTTP/3 header compression without head-of-line blocking.

XQUIC, Alibaba’s open-source QUIC protocol stack, implements RFC 9204’s QPACK specification to compress HTTP/3 headers. The QPACK dynamic table stores recently transmitted header name-value pairs on both client and server, allowing subsequent requests to reference entries by index rather than transmitting full strings. This mechanism reduces wire size while respecting QUIC’s multiplexed stream constraints through careful synchronization between encoder and decoder states.

Core Data Structure of the Dynamic Table

At the heart of XQUIC’s implementation lies the xqc_dtable_t structure defined in src/http3/qpack/dtable/xqc_dtable.c. This structure wraps three specialized utilities to balance fast lookup with memory-efficient storage:

• 2-D hash table (ht2d): Maps name-value pairs to their table indices for duplicate detection
• Ring array (entries): Maintains FIFO ordering required for proper eviction semantics
• Ring memory (rmem): Provides contiguous storage for the actual name and value strings

/* src/http3/qpack/dtable/xqc_dtable.c */
typedef struct xqc_dtable_s {
    xqc_2d_hash_table_t    *ht2d;      /* name/value → entry */
    xqc_rarray_t           *entries;   /* ordered FIFO of entries */
    xqc_ring_mem_t         *rmem;      /* raw bytes of name/value strings */
    uint64_t                insert_cnt;/* total inserts since creation */
    uint64_t                first_idx; /* absolute index of the first entry */
    size_t                  capacity;  /* max bytes (name+value+32) */
    size_t                  used;      /* current occupied bytes */
    uint64_t                byte_sum;  /* sum of all sizes (for eviction) */
    uint64_t                min_ref;   /* lowest still‑referenced index */
    xqc_log_t              *log;
} xqc_dtable_t;

The capacity field represents the max dynamic table capacity advertised by the peer via HTTP/3 SETTINGS. Crucially, min_ref tracks the lowest index still referenced by in-flight streams, ensuring the encoder never evicts entries that blocked streams depend on—a safety guarantee required by the QPACK specification.

Encoder-Side Dynamic Table Operations

The encoder manages the dynamic table through a lifecycle that balances insertion opportunities against memory constraints and peer acknowledgment state.

Table Creation and Capacity Management

When xqc_encoder_create initializes the encoder in src/http3/qpack/xqc_encoder.c, it allocates the dynamic table with need_hash = 1 because the encoder must detect duplicate entries for optimal compression. The encoder maintains two capacity values:

1. Maximum capacity (max_entries): Immutable limit set by xqc_encoder_set_max_dtable_cap when processing the peer’s initial SETTINGS frame
2. Effective capacity (enc->dtable_cap): Current operating limit set via xqc_encoder_set_dtable_cap, which recomputes name and entry size limits and emits a SET_DYNAMIC_TABLE_CAPACITY instruction to the decoder

Entry Insertion and Eviction

When encoding headers, the encoder evaluates whether to insert a new entry based on enc->name_len_limit and enc->entry_size_limit. If insertion is permitted, xqc_dtable_add (line 393 in xqc_dtable.c) allocates space in ring memory, stores the strings, and updates the 2-D hash table.

If adding an entry would exceed enc->dtable_cap, xqc_dtable_make_space (lines 336-385) triggers eviction. The function repeatedly calls xqc_dtable_pop_entry, but only removes entries whose absolute index is less than enc->min_ref, guaranteeing that in-flight references remain valid.

Blocked Stream Handling

When a header block references a dynamic entry with an index greater than the current Known Received Count (krc), the stream enters a blocked state. The encoder adds the stream to enc->blocked_list via xqc_encoder_add_blocked_stream (lines 197-226) and avoids insertions that would increase the Required Insert Count. Once the decoder acknowledges receipt via INSERT_COUNT_INCREMENT, xqc_encoder_unblock_streams resumes the flow.

Decoder-Side Dynamic Table Operations

The decoder maintains a mirror of the dynamic table but operates with different constraints and responsibilities.

Table Creation Without Hash Table

In src/http3/qpack/xqc_decoder.c, xqc_decoder_create (lines 23-31) initializes the dynamic table without the 2-D hash structure. The decoder only needs to retrieve entries by absolute index, not look up name-value pairs, reducing memory overhead.

Processing Encoder Instructions

As the decoder receives encoder instructions on the QPACK control stream, xqc_qpack_on_encoder_ins in src/http3/qpack/xqc_qpack.c (lines 53-78) dispatches to specific handlers:

• INSERT_WITH_NAME_REF: xqc_decoder_insert_name_ref adds an entry referencing the static table or existing dynamic entry
• INSERT_LITERAL: xqc_decoder_insert_literal inserts a literal name-value pair
• DUPLICATE: xqc_decoder_duplicate copies an existing dynamic entry to the front

Required Insert Count Validation

Before decoding a header block, the decoder validates the Required Insert Count (RIC) encoded in the field section prefix. In xqc_decoder_dec_header → xqc_rep_decode_prefix (line 176), if RIC > insert_cnt, the decoder returns blocked = true, forcing the application to wait for additional encoder instructions before decoding can proceed.

Acknowledgment and Synchronization

After successfully decoding, the decoder sends INSERT_COUNT_INCREMENT via xqc_qpack_notify_insert_cnt_increment and SECTION_ACK via xqc_qpack_notify_section_ack (lines 45-71 in xqc_qpack.c). These instructions allow the encoder to advance krc and unblock waiting streams.

Synchronizing Encoder and Decoder States

XQUIC keeps the dynamic tables consistent through four critical instruction types exchanged between peers:

Instruction	Direction	Purpose
SET_DYNAMIC_TABLE_CAPACITY	Encoder → Decoder	Advertises the effective capacity limit; decoder stores max_ents for RIC validation
INSERT_WITH_NAME_REF / INSERT_LITERAL / DUPLICATE	Encoder → Decoder	Adds entries to the decoder’s table; encoder updates its own table and tracks acknowledgment state
INSERT_COUNT_INCREMENT	Decoder → Encoder	Signals that increment new entries are acknowledged; encoder updates krc and evicts eligible entries
SECTION_ACK	Decoder → Encoder	Confirms complete processing of a specific stream’s header block; clears blocked-stream state

All instruction parsing logic resides in src/http3/qpack/xqc_qpack.c within xqc_qpack_process_encoder and xqc_qpack_process_decoder, which handle raw byte parsing and callback invocation.

Practical Implementation Example

The following pattern demonstrates the complete lifecycle of QPACK dynamic table usage in XQUIC:

/* 1️⃣ Create a QPACK handler with local capacity limits */
xqc_qpack_ins_cb_t ins_cb = {
    .get_buf_cb  = my_get_ins_buf,   /* allocate buffer for instructions */
    .write_ins_cb = my_write_ins,    /* send on the control stream */
};
xqc_qpack_t *qpk = xqc_qpack_create(16*1024, 16*1024, log, &ins_cb, NULL);

/* 2️⃣ Set effective capacity after receiving peer SETTINGS */
xqc_qpack_set_dtable_cap(qpk, 8*1024);   /* effective cap = min(local, peer) */

/* 3️⃣ Encode headers using the dynamic table */
xqc_http_headers_t hdrs = {0};             /* populate with :method, :path, etc. */
xqc_var_buf_t *rep_buf = my_rep_buf();       /* buffer for encoded field section */
xqc_qpack_enc_headers(qpk, stream_id, &hdrs, rep_buf);

/* 4️⃣ Send encoded field section on the request stream */

/* 5️⃣ Decode on the server side */
xqc_rep_ctx_t *req_ctx = xqc_qpack_create_req_ctx(stream_id);
xqc_http_headers_t decoded = {0};
xqc_bool_t blocked = XQC_FALSE;
xqc_qpack_dec_headers(qpk, req_ctx,
                      rep_buf->data, rep_buf->data_len,
                      &decoded, XQC_TRUE, &blocked);

/* 6️⃣ Handle blocking: if blocked == true, wait for INSERT_COUNT_INCREMENT 
   from the encoder, then retry step 5 */

Summary

• Dynamic table structure: XQUIC uses xqc_dtable_t combining a 2-D hash table for encoder lookups, a ring array for FIFO ordering, and ring memory for compact string storage.
• Encoder responsibilities: Manages capacity limits via xqc_encoder_set_dtable_cap, inserts entries through xqc_dtable_add, and evicts only entries below min_ref to protect in-flight references.
• Decoder responsibilities: Maintains entry storage without hashing, validates Required Insert Count against current insert_cnt, and acknowledges progress via INSERT_COUNT_INCREMENT.
• Synchronization mechanism: Explicit QPACK instructions ensure both sides share identical table states while respecting HTTP/3’s requirement to avoid head-of-line blocking on individual streams.

Frequently Asked Questions

How does XQUIC prevent evicting dynamic table entries that are still in use?

XQUIC tracks the min_ref field in xqc_dtable_t, which represents the lowest absolute index still referenced by any in-flight header block. During eviction in xqc_dtable_make_space, entries are only removed if their index is strictly less than enc->min_ref. This guarantees that blocked streams waiting for acknowledgments never encounter missing references.

What is the difference between the encoder's maximum capacity and effective capacity?

The maximum capacity (max_entries) is an immutable limit set once when the encoder receives the peer’s initial SETTINGS frame via xqc_encoder_set_max_dtable_cap. The effective capacity (enc->dtable_cap) is the currently active limit set by xqc_encoder_set_dtable_cap, which may be lower than the maximum to conserve memory or match updated peer constraints. The effective capacity determines actual insertion limits and triggers SET_DYNAMIC_TABLE_CAPACITY instructions.

Why does the XQUIC decoder not use a 2-D hash table for the dynamic table?

The decoder only needs to retrieve existing entries by their absolute index when processing encoded header blocks with dynamic references. Unlike the encoder, which must detect duplicate name-value pairs to avoid redundant insertions, the decoder never performs lookups by content. Omitting the 2-D hash table in xqc_decoder_create reduces memory footprint while maintaining full specification compliance.

How does XQUIC handle streams blocked on dynamic table references?

When the encoder generates a header block referencing an entry with an index greater than the decoder’s known received count (krc), it adds the stream to enc->blocked_list via xqc_encoder_add_blocked_stream. The encoder then avoids insertions that would increase the Required Insert Count for that stream. Once the decoder acknowledges receipt of the missing entries via INSERT_COUNT_INCREMENT, xqc_encoder_unblock_streams removes the stream from the blocked list and allows encoding to proceed.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}