HPAX.resize/2 does not satisfy the requirements of HTTP/2 SETTINGS_MAX_HEADER_LIST_SIZE settings updates

[mtrudel]

As identified at mtrudel/bandit#392, calling HPAX.resize/2 does not correctly perform the steps needed to handle HTTP/2 settings updates that change the SETTINGS_MAX_HEADER_LIST_SIZE value.

What the RFCS say

RFC9113§4.3.1 describes the process¹ of how changes to SETTINGS_MAX_HEADER_LIST_SIZE are undertaken in terms of the decoder and encoder ends of an HPACK context:

0. At the beginning of a connection, the default value of max table size is taken to be 4096; as such, the following logic applies even to initial SETTINGS frame exchange.
1. The decoder specifies a value for this setting via a SETTINGS frame. This setting indicates the maximum value of the maximum table size that the decoder is willing to accept. The decoder does not yet change its HPACK context in any way.
2. The encoder end is then free to select any value up to this value for the maximum table size.
3. The encoder then sends an ACK to the SETTINGS frame and simultaneously updates its HPACK context with this new maximum table size.
4. Upon receipt of the SETTINGS ACK, the decoder then updates its max table size to the size it sent in the SETTINGS frame.
5. If the encoder did not choose a strictly smaller size than the one sent by the decoder in step 1, then the encoder and decoder now have a shared understanding of the maximum table size (and have both truncated existing records as necessary to satisfy it). We're done.
6. If the encoder did choose a strictly smaller size in step 2, it must send that size via a dynamic table size update by prefixing it to the next encoded block it sends.
7. Upon receipt of this dynamic table size update, the decoder end updates its maximum table size to this value (first checking to ensure that it's not larger than what it originally sent in step 1). The encoder and decoder now have a shared understanding of the maximum table size (and have both truncated existing records as necessary to satisfy it). We're done.

How HPAX should be used (and what it should be doing)

• On the encoder, application-level calls to HPAX.resize/2 should be made when the encoder receives a settings frame from the decoder, with the application passing a value no larger than the value specified in the settings frame.

  • HPAX should update its max table size to the specified value, possibly evicting values as needed.
  • If the new value set is strictly less than the table's previous max value, then a dynamic table size update message must be sent at the beginning of the next encoded block.

• On the decoder, application-level calls to HPAX.resize/2 should be made when the decoder receives a settings ACK (NOT when the settings frame is sent), with the application passing in the exact value from the settings frame that was acknowledged, possibly evicting records as needed.

• The decoder should process dynamic table size update messages by first ensuring that the message is not increasing the maximum size of the table. It should then be setting the table's max size to the value indicated, possibly evicting records as needed.

Where HPAX currently falls short

HPAX's current implementation is insufficient in the following two ways:

1. The behaviour of HPAX.Table.resize/2 does not update the max table size, it only evicts entries to decrease the size of the contents of the table. We should be updating max_table_size as part of the resize behaviour.
2. Setting side the max_table_size issue above, the current behaviour of HPAX.resize/2 is insufficient on the encoder side. If the max size has decreased, we must send a dynamic table size update to the decoder.

There are four existing calls to HPAX.resize/2 across all of HPAX's hex dependents:

1. https://github.com/mtrudel/bandit/blob/898afdce7af2f0d14a09d50d88e7ef7a73fb0e88/lib/bandit/http2/connection.ex#L101 (the originator of this issue; this is the encoder receiving a settings frame from the decoder)
2. https://github.com/elixir-mint/mint/blob/main/lib/mint/http2.ex#L1801 (this is the encoder receiving a settings frame from the decoder)
3. https://github.com/lucacorti/ankh/blob/3d0e65845a869d00d82611d77feb11e1b31995ff/lib/ankh/protocol/http2.ex#L829 (yet another case of the encoder receiving a settings frame from the decoder)
4. https://github.com/lucacorti/ankh/blob/3d0e65845a869d00d82611d77feb11e1b31995ff/lib/ankh/protocol/http2.ex#L437 (This one is different, and handles the decoder sending a settings frame. Note that it incorrectly does so at the time the settings frame is sent and not when it is acknowledged (@lucacorti)).

Proposed Solution

Based on the above, I propose that we should:

1. Move the existing HPAX.Table.resize/2 function to a private HPAX.Table.evict_to_max_size/2 since it is used in table addition (its current behaviour is correct for this purpose).

2. Create a new HPAX.Table.resize/2 implementation that calls HPAX.Table.evict_to_max_size/2 and also sets the value of max_table_size as indicated. This will correctly implement the behaviour required when it is called on the decoder (both explicitly by the application upon receipt of settings frame asks, and also as part of receiving a dynamic table size update).

3. Add logic to HPAX.Table.resize/2 to set a flag on the table whenever the table max size is adjusted downward. This flag should be checked when encoding, and if set the encoding should have a dynamic table size update prepended (and the flag subsequently cleared). There is no need to discriminate between encoder and decoder users here, since decoders will never be encoding (and so the flag is vestigial in this case).

I'm happy to undertake this work, but given its subtlety I think it's good to have multiple people think through it and ensure it's a sensible solution.

Footnotes

1. Of note, this process was not specified as part of the original RFC 7540; details were only added in RFC 9113 (see Appendix B). ↩

[lucacorti]

@mtrudel thanks for the heads up!

[mtrudel]

I'm most of the way through this work and I've come to the realization that I think we need something like a protocol_max_table_size field on table. The need comes from a strict read of https://www.rfc-editor.org/rfc/rfc7541#section-6.3, specifically:

The new maximum size [of a dynamic table size update] MUST be lower than or equal to the limit
determined by the protocol using HPACK. A value that exceeds this
limit MUST be treated as a decoding error. In HTTP/2, this limit is
the last value of the SETTINGS_HEADER_TABLE_SIZE parameter

HPAX currently checks the size of such updates against max_table_size, which isn't correct. The current implementation prevents dynamic table size update (DTSU) messages from increasing the max table size at all, when the protocol is clear that increases up to the protocol negotiated max value are supported (indeed, this is how DTSUs can be used to empty out the decoder's table per https://www.rfc-editor.org/rfc/rfc7541#section-4.2).

So what we actually need in Table is:

• size to reflect the size of the entries currently in the table (per https://www.rfc-editor.org/rfc/rfc7541#section-4.1)
• max_table_size to reflect the maximum allowable size of the table before we end up truncating
• protocol_max_table_size to reflect an upper bound on max table size changes that will be accepted in DTSU messages

HPAX.resize/2 calls should be setting protocol_max_table_size (as well as decreasing max_table_size and truncating entries if necessary). Support for DTSU decoding should compare the given size against protocol_max_table_size (instead of max_table_size) when validating the value.