Re: HPACK substitution & header table pruning

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?
>
> 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!
>