W3C home > Mailing lists > Public > ietf-http-wg@w3.org > July to September 2013

Re: HPACK substitution & header table pruning

From: Roberto Peon <grmocg@gmail.com>
Date: Mon, 26 Aug 2013 17:21:52 -0700
Message-ID: <CAP+FsNfpFmD3EsCXTjuarusbXNQfRn3WZA_eb8j1SZhqA-mgyA@mail.gmail.com>
To: Jesse Wilson <jesse@swank.ca>
Cc: HTTP Working Group <ietf-http-wg@w3.org>
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 <jesse@swank.ca> wrote:

> 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?
>
> Heres an example situation where the order of these operations is
> relevant. Suppose Ive 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!
>
Received on Tuesday, 27 August 2013 00:22:21 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 17:14:15 UTC