Subject: HPACK substitution & header table pruning

From: Jesse Wilson <[email-masked]>
Date: Mon, 26 Aug 2013 10:44:20 -0400

I'm attempting to implement HTTP/2.0 for
OkHttp<http://square.github.io/okhttp/>,
Square's HTTP client for Android and Java.

I'd like to clarify how header table pruning works with
replacement-by-index. The doc
says<http://http2.github.io/compression-spec/compression-spec.html#rfc.section.3.2.3>
:

When the modification of the header table is the replacement of an existing
entry, the replaced entry is the one indicated in the literal
representation before any entry is removed from the header table. *If the
entry to be replaced is removed* from the header table when performing the
size adjustment, the replacement entry is inserted at the beginning of the
header table.

Is the entry to be replaced removed before pruning-from-0 begins? Or does
all pruning happen, and then the replacement happens?

Here‘s an example situation where the order of these operations is
relevant. Suppose I’ve got a headers table containing 4 entries, each 1024
bytes. The max size of this table is 4096.

   0  A: <value> (entry size: 1024)
   1  B: <value> (entry size: 1024)
   2  C: <value> (entry size: 1024)
   3  D: <value> (entry size: 1024)

At this point I receive a literal header with substitution indexing “E” at
index 2 and entry size 2048. This will replace C.

If I prune first, I remove A and B. Substituting yields this new headers
table:

   0  E: <value> (entry size: 2048)
   1  D: <value> (entry size: 1024)

If I remove the replaced entry C first, I get a different result:

   0  B: <value> (entry size: 1024)
   1  E: <value> (entry size: 2048)
   2  D: <value> (entry size: 1024)

Another way to look at it is whether I'm pruning until currentSize +
size(E) <= max or until currentSize - size(C) + size(E) <= max.

Thanks!

---

From: James M Snell <[email-masked]>
Date: Mon, 26 Aug 2013 08:24:07 -0700

You would prune first, then replace... but, for substitution indexing
you use your second calculation to determine what needs to be pruned.

In your example, you would...

... first, determine that sizeof( A + B + D + E - C ) > max, and
therefore drop A first.

0 B: <value> (entry size: 1024)
1 C: <value> (entry size: 1024)
2 D: <value> (entry size: 1024)

... second, determine that sizeof ( B + D + E - C) <= max, no more
evictions are required.
... you would then replace C (now at #1, but originally at #2) with E...  giving

On Mon, Aug 26, 2013 at 7:44 AM, Jesse Wilson <[email-masked]> wrote:
> I'm attempting to implement HTTP/2.0 for OkHttp, Square's HTTP client for
> Android and Java.
>
> replacement-by-index. The doc says:
>
> entry, the replaced entry is the one indicated in the literal representation
> before any entry is removed from the header table. If the entry to be
> replaced is removed from the header table when performing the size
> adjustment, the replacement entry is inserted at the beginning of the header
> table.
>
> Here‘s an example situation where the order of these operations is relevant.
> Suppose I’ve got a headers table containing 4 entries, each 1024 bytes. The
> max size of this table is 4096.
>
> Another way to look at it is whether I'm pruning until currentSize + size(E)
> <= max or until currentSize - size(C) + size(E) <= max.
>
> Thanks!

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 26 Aug 2013 19:32:45 +0300

On Mon, Aug 26, 2013 at 10:44:20AM -0400, Jesse Wilson wrote:
> replacement-by-index.

Some other corner cases of HPACK / interaction with HTTP2:

- Literal Header with Substitution Indexing with indexed name pointing
  to entry which will be pruned.

  E.g. 01 01 <value>  When that operation causes the first entry to be
  pruned.

  * I presume the name is saved before pruning.

- What does 8+ in diagrams mean? 8-bit prefix? 0-bit prefix?

  * I presume 0-bit prefix, since one such field is mentioned to be 0-bit
  prefix in text.

- Parameter negotiation (yes I realize it is not part of spec):

  Does encoder have a way to bid down the context size?

  There seems to be some mechanism for bid-down for renegotiation,
  but initial negotiation seems to be fuzzier.

  Because of memory limitations for encoder, implementation
  limitations for encoder or unreasonable context size...

  * E.g. encoder using 16-bit offsets, only allowing up to 65535
    byte contexts...
  * E.g. remote peer signaling 4GB compression window...

-Ilari

---

From: Roberto Peon <[email-masked]>
Date: Mon, 26 Aug 2013 17:21:52 -0700

As James has already said, you prune then replace.
If must be this way, else you're violating the guarantee about how much
memory you're using (by however long the new key-value is).

It should look something like:

while  not enough_space_in_header_table_for_an_extra(key.size() +
val.size() + 32):
  expire_oldest_entry();

If substituting, then, if the key index points to the element being
replaced, the space necessary is only val.size(). If the key index points
elsewhere, it would be key.size() + val.size() [32 excluded, since we've
already paid for this slot]

Thus (this only handles making space for stuff, not the whole state
machine):
for op in ops:
  if op is substitution:
    if key_idx == dst_idx:
      size_needed = val.size()
    else:
      size_needed = key.size() + val.size()
  else:
    size_needed = key.size() + val.size() + 32
  while not state_table.empty() and current_size + size_needed > max_size:
    entry = state_table.oldest_entry()
    current_size -= entry.key() + entry.val() + 32
    delete entry
  # handle inserting entry
-=R

On Mon, Aug 26, 2013 at 7:44 AM, Jesse Wilson <[email-masked]> wrote:

> I'm attempting to implement HTTP/2.0 for OkHttp<http://square.github.io/okhttp/>,
> replacement-by-index. The doc says<http://http2.github.io/compression-spec/compression-spec.html#rfc.section.3.2.3>
> :
>
> When the modification of the header table is the replacement of an
> existing entry, the replaced entry is the one indicated in the literal
> entry to be replaced is removed* from the header table when performing
> the size adjustment, the replacement entry is inserted at the beginning of
> the header table.
>

---

From: Martin Thomson <[email-masked]>
Date: Tue, 27 Aug 2013 09:54:13 -0700

>   expire_oldest_entry();

You need to expand on this a little, noting that for substitution, the
expiration of entries with lower indices than the substitution index
causes the substitution index to be reduced.  If the substituted index
is removed, then it's key must be retained and the new entry is
inserted at the start of the table.

> If substituting, then, if the key index points to the element being replaced, the space necessary is only val.size().

...less the size of the value that is being replaced.
...unless the substitution entry is evicted, at which point the
evaluation becomes identical to insertion again.

So I don't think your code is quite right.