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

Re: HPACK substitution & header table pruning

From: James M Snell <jasnell@gmail.com>
Date: Mon, 26 Aug 2013 08:24:07 -0700
Message-ID: <CABP7RbfgN80Amgb8W5Vomx0B6GqqgOF1hkZ0mX0E3FAXP7rnEg@mail.gmail.com>
To: Jesse Wilson <jesse@swank.ca>
Cc: "ietf-http-wg@w3.org" <ietf-http-wg@w3.org>
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...

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

... 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

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




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, 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:
>
> 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!
Received on Monday, 26 August 2013 15:24:54 UTC

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