Subject: hpack static table question?

From: Greg Wilkins <[email-masked]>
Date: Mon, 2 Jun 2014 16:45:28 +0200

The hpack draft 7 says in 3.2.1 : "The referenced static entry is inserted
at the beginning of the header table".

I can't understand why this copy of a static entry to the dynamic table is
needed?   Doesn't this mean that the static entry will now be known by two
indexes?     Why is this copy needed?  Also If a badly written encoder kept
sending the static index reference, then it would be possible to fill up
the header table with duplicates of the static header?

I'm also struggling to work out why the indexing is done like:

          <----------  Index Address Space ---------->
          <-- Header  Table -->  <-- Static  Table -->
          +---+-----------+---+  +---+-----------+---+
          | 1 |    ...    | k |  |k+1|    ...    | n |
          +---+-----------+---+  +---+-----------+---+
          ^                   |
          |                   V
   Insertion Point       Drop Point

I would have thought it better to have the tables as:

          <----------  Index Address Space ---------->
          <-- Static  Table -->  <-- Header  Table -->
          +---+-----------+---+  +---+-----------+---+
          | 1 |    ...    | k |  |k+1|    ...    | n |
          +---+-----------+---+  +---+-----------+---+
                                 ^                   |
                                 |                   V
                            Insertion Point       Drop Point

This looks like a very deliberate decision made for good reason... but the
reason alludes me at the moment.

cheers

-- 
Greg Wilkins <[email-masked]>
http://eclipse.org/jetty HTTP, SPDY, Websocket server and client that scales
http://www.webtide.com  advice and support for jetty and cometd.

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 2 Jun 2014 18:07:24 +0300

On Mon, Jun 02, 2014 at 04:45:28PM +0200, Greg Wilkins wrote:
> indexes?     Why is this copy needed? 

AFAIK, to avoid needing having to keep state bits (2 per entry[1]) for the
static table.

Yeah, the static table is 61 entries, thus the amount of state needed would
be just 16 bytes.

[1] In set and emitted bits.

-Ilari

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 2 Jun 2014 17:17:46 +0200

Hmmmm, Currently there is no state I can see for the header table entries?
They are either in the table or not and the only eviction mechanism is due
to size.    There is no need to keep set/emitted bits, as that is for the
reference set and not the header table.

So I'm still missing something?

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Tue, 3 Jun 2014 00:22:39 +0900

> [1] In set and emitted bits.
​Another reason is that we can clear reference set when ​setting
SETTINGS_HEADER_TABLE_SIZE to 0 if we static entry is copied int dynamic
header table when it is referenced.

Best regards,
Tatsuhiro Tsujikawa

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 2 Jun 2014 17:45:12 +0200

Tatsuhiro,

sorry but I'm still not understanding.   If you want to clear the reference
set, there is a 1 byte code to send for that.   It makes little sense to
set the header table size to 0 just to clear the reference set.

This also raises another slight concern.  When the copied static entry in
the dynamic table is eventually evicted, then that field is also evicted
from the reference set.  Chances are that it will then be put straight back
in there.  Seams pointless?

So I'm still not getting why?

cheers

---

From: Jason Greene <[email-masked]>
Date: Mon, 2 Jun 2014 10:49:02 -0500

On Jun 2, 2014, at 9:45 AM, Greg Wilkins <[email-masked]> wrote:

> I can't understand why this copy of a static entry to the dynamic table is needed?   Doesn't this mean that the static entry will now be known by two indexes?    
> Why is this copy needed?  

Differential encoding. The subsequent requests no longer need to reference the static header and its value (even by index) once it has been copied into the header table.

--
Jason T. Greene
WildFly Lead / JBoss EAP Platform Architect
JBoss, a division of Red Hat

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Tue, 3 Jun 2014 01:05:00 +0900

On Tue, Jun 3, 2014 at 12:45 AM, Greg Wilkins <[email-masked]> wrote:

> Tatsuhiro,
>
> sorry but I'm still not understanding.   If you want to clear the
> reference set, there is a 1 byte code to send for that.   It makes little
> sense to set the header table size to 0 just to clear the reference set.
>
>
​You are mixing the capability of decoder and encoder.  Clearing header
table by sending SETTINGS_HEADER_TABLE_SIZE = 0 is done by decoder.  On the
other hand, sending context update to clear reference set is a job of
encoder.​  And we have different compression context for decoder and
encoder on each side.

> in there.  Seams pointless?
​Sorry, I don't understand.  What is the problem here exactly?

Best regards,
Tatsuhiro Tsujikawa​

---

From: Cory Benfield <[email-masked]>
Date: Mon, 2 Jun 2014 17:20:34 +0100

On 2 June 2014 17:05, Tatsuhiro Tsujikawa <[email-masked]> wrote:
> Sorry, I don't understand.  What is the problem here exactly?

Let's get everyone on the same page.

Greg is concerned that he has to copy a header out of the static table
into the header table in order to add it to the reference set. He has
to do this because the spec states that references may only be to
headers in the header set without being clear of _why_ that's the
case.

Tatsuhiro has provided the most compelling reason so far, which is
that it enables the clearing of the reference set by the slightly
obscure means of setting the header table size to zero via HTTP/2
SETTINGS. I don't think anyone actually wants to do this.

I think the real question here is: why can't we have references to the
static table? What is the architectural reason that ruled it out?

---

From: Michael Sweet <[email-masked]>
Date: Mon, 02 Jun 2014 12:32:11 -0400

Cory,

On Jun 2, 2014, at 12:20 PM, Cory Benfield <[email-masked]> wrote:
> ...

Set the table size to 0 or clear the reference set?

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: Nicholas Hurley <[email-masked]>
Date: Mon, 2 Jun 2014 09:44:18 -0700

I was wondering this about a month back, when I was helping debug an issue
centered around this case (a copy of a static entry being evicted). So I
looked back in the list archives, and saw that basically, some people
wanted setting the table size to 0 to mean that literally no state was
kept, not even references to the static table. (I'm on my phone, so no link
to the thread, sorry.)

Personally, I think it's silly, too (it means that periodically I have to
send an indexed representation that I wouldn't have to if I could put
static :method GET headers in the reference set). But it's what we have,
and I have to re-send :method if some resources are POST anyway, so it's
not a big loss. This is why I didn't bring it up a month ago.

Personally, while I'm not a fan of this restriction, I'd rather keep the
spec as is so we can get to last call sooner.
--
Peace,
  -Nick

---

From: RUELLAN Herve <[email-masked]>
Date: Mon, 2 Jun 2014 16:48:37 +0000

The goal is to allow a receiver to limit the quantity of memory allocated for a given sender.

The size of the header table is limited by the SETTINGS_HEADER_TABLE_SIZE value. The computation of the size of the header table includes the length of the strings and 32 octets for the table structure overhead.

The memory allocated to the static table is fixed and can even be shared amongst all the senders.

However, there is no direct control over the memory used by the reference set. For items of the reference set belonging to the header table, there is an indirect control through the SETTINGS_HEADER_TABLE_SIZE value. To extent this indirect control to items belonging to the static table, it was decided to copy these items to the header table: in this way the memory used by the reference set is fully controlled by the SETTINGS_HEADER_TABLE_SIZE value.

Hervé.

PS: I will add this explanation to the spec.

> -----Original Message-----
> From: Cory Benfield [mailto:[email-masked]]
> Sent: lundi 2 juin 2014 18:21
> To: Tatsuhiro Tsujikawa
> Cc: Greg Wilkins; Ilari Liusvaara; HTTP Working Group
> Subject: Re: hpack static table question?
>

---

From: RUELLAN Herve <[email-masked]>
Date: Mon, 2 Jun 2014 16:51:57 +0000

I hope my previous email makes clear the reasoning for requiring this copy.

Yes this copy has a cost, both in bytes on the wire, and in CPU, but hopefully it closes a potential vector for attacks.

Hervé.

> From: Nicholas Hurley [mailto:[email-masked]]
> Sent: lundi 2 juin 2014 18:44
> To: Cory Benfield
> Cc: Greg Wilkins; IETF HTTP WG; Ilari Liusvaara; Tatsuhiro Tsujikawa
> centered around this case (a copy of a static entry being evicted). So I looked
> back in the list archives, and saw that basically, some people wanted setting the
> table size to 0 to mean that literally no state was kept, not even references to
> the static table. (I'm on my phone, so no link to the thread, sorry.)
> 
> Personally, I think it's silly, too (it means that periodically I have to send an
> indexed representation that I wouldn't have to if I could put static :method GET
> headers in the reference set). But it's what we have, and I have to re-send
> :method if some resources are POST anyway, so it's not a big loss. This is why I
> didn't bring it up a month ago.
> 
> Personally, while I'm not a fan of this restriction, I'd rather keep the spec as is
> so we can get to last call sooner.
> --
> Peace,
>   -Nick
>

---

From: Roberto Peon <[email-masked]>
Date: Mon, 2 Jun 2014 09:54:01 -0700

This was for safety. This ensures that entries in the reference set get
counted, even if the reference set is composed solely of members from the
static table.

This method was the simplest method for doing so.

-=R

---

From: Roberto Peon <[email-masked]>
Date: Mon, 2 Jun 2014 09:59:16 -0700

To expand on what Herve (and I) were saying, by treating these static
headers like all other headers, the size of the reference set becomes
constrained by the total memory size, and thus an implementation can cause
the state to be cleared, or never allocated while allowing indexed
representations to be used by the encoder.
 Additionally, assuming one doesn't optimize the copying away (which is
certainly possible) it becomes possible to use a circular buffer to hold
all of the data in the compressor. This reduces memory fragmentation and
can improve CPU cache latency.

IIRC, this was put in 2 or 3 drafts ago. It seemed much cleaner than
dealing with multiple thresholds (one for ref data, one for memory).

-=R

On Mon, Jun 2, 2014 at 9:54 AM, Roberto Peon <[email-masked]> wrote:

>> The hpack draft 7 says in 3.2.1 : "The referenced static entry is
>> inserted at the beginning of the header table".
>>
>> I can't understand why this copy of a static entry to the dynamic table
>> is needed?   Doesn't this mean that the static entry will now be known by
>> two indexes?     Why is this copy needed?  Also If a badly written encoder
>> kept sending the static index reference, then it would be possible to fill
>> up the header table with duplicates of the static header?
>>
>> This looks like a very deliberate decision made for good reason... but
>> the reason alludes me at the moment.
>>
>> cheers
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> --

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 2 Jun 2014 19:59:05 +0200

Guys,

thanks for the explanations. I think I kind of understand now, although I
don't think it really looks "much cleaner" to the proverbial fresh eyes.

Note that I'm not all that worried about the occasional resend of a static
index, or the copy or even the reference set size.   My concern is simply
that a moderately complex design is well justified, well explained and
actually achieves the purpose for which it was intended.

To paraphrase the responses to ensure that I've got it,   the decision to
copy references to static entries to the dynamic table was done so that a
limit on the header table size is also effectively a limit on the reference
set.

In extreme, if the header table size is set to 0, then the reference set
will also have to be empty because there will be no entries for it to
reference.     Known headers will still be able to be sent as index's into
the static table, they will just never make it into the reference set
because they will never fit into the header table.

However, I'm not so sure that this solution really does limit the size of
the reference set, because it can contain duplicates.   Let say that the
header table has exactly one entry in it, then there is nothing to stop a
header block sending repeated references to it so that the reference set
become arbitrarily large with duplicate references?   Personally I'm in
favour of limiting headers to one frame, so that would have an implicit
limit on the size of the reference set as you can only fit in so many index
references into one frame.

cheers

PS.  Anybody care to explain why the static index's are on top of the
dynamic index's?  Is this simply to try to ensure that the dynamic
references are more likely to fit into a 7+bit integer once they are copied?

---

From: Roberto Peon <[email-masked]>
Date: Mon, 2 Jun 2014 11:26:53 -0700

Any time it is indexed, a copy gets put into the header table, eventually
expunging something.
The spec requires that stored references are only to entries in the header
table.
These two couple to give the guarantee about reference set size.

This is supposed to be the relevant chunk (from section 3.1.3), which can
perhaps be made clearer?

To limit the memory requirements on the decoder side for handling the
   reference set, only entries within the header table can be contained
   in the reference set.  To still allow entries from the static table
   to take advantage of the differential encoding, when a header field
   is represented as a reference to an entry of the static table, this
   entry is inserted into the header table (see Section 3.2.1
<http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07#section-3.2.1>).

-=R

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 2 Jun 2014 21:18:03 +0200

Roberto,

that clause from 3.1.3 is clear enough in what an impl must do, I just
don't see how it achieve a limit on the reference set size.

Consider a setup that has a small header table size that will fit just a
single field into in.  This decoder then receives a header frame that
contains a reference to header 4 (static :path:/).  This is copied into the
header table at index 1 (evicting anything else that was in there) and is
added to the reference set.  Now say that the rest of the header frame is
full of many many duplicates of a reference to index 1.  For each reference
another entry is made into the reference set pointing to the copied static
entry.    This can continue for ever and represents unlimited growth of the
reference set.

If this kind of duplicate attack is not a problem, then I don't think we
need to limit the size of the reference set, because without such
duplicates, then every entry in the reference set is going to be much
smaller than each entry in the header set.   Thus a limit on the header set
size is effectively a limit on the reference set size, without the need to
copy.

So either I'm still missing something or this a complex mechanism that does
not achieve what it is intended to do.

cheers

---

From: Roberto Peon <[email-masked]>
Date: Mon, 2 Jun 2014 12:47:26 -0700

Lemme try to explain the whole thing :)
1) Every header table entry has an 'overhead' associated with it, thus even
zero-length strings have size.
2) Every entry always points to a header table entry (thus,has a
cost-in-bytes associated)
3) Every entry in the reference set is unique-- there is no way to have a
duplicate in there.

In your example:
index 4 becomes a reference to the first entry in the table.
Each duplicate reference causes the previous first entry to be evicted and
replaced.
Lets assume that the max-table-size is 42 here.
Since the cost-in-bytes of the entry are (strlen(":path") + strlen("/") +
32) == 38, one entry fits into the table, but two do not. Referencing the
static index again will cause the previous entry in the table to be evicted.
Referencing the header-table entry will cause it to be removed if it is
already present, and added if it isn't.
Any time an entry is removed from the header table, the reference to it in
the reference set must be removed (can't have dangling references!).

-=R

On Mon, Jun 2, 2014 at 12:18 PM, Greg Wilkins <[email-masked]> wrote:

> So either I'm still missing something or this a complex mechanism that
> does not achieve what it is intended to do.
>
> cheers
>
>
> --

---

From: Greg Wilkins <[email-masked]>
Date: Mon, 2 Jun 2014 22:34:25 +0200

Roberto

Thanks for sticking with me - I've got it now!

What I was missing was that a reference to an entry already in the
reference set removes it rather than duplicates it!

It's not the most obvious of emergent behaviours - at least not to this
little black duck, and seams a bit unnecessary as there are only 13 static
entries with values, so allowing those into the reference set without
copying is hardly going to use much memory.

I'd prefer to just allow references to the static table and as I said
before, the limit on the header table size would naturally put a limit on
the reference set (even more so, now I've understood why there are no
duplicates).  But then it's not a big deal either.... if we end up changing
hpack for other reasons, then I'd advocate dropping the copy.
thanks again!

On 2 June 2014 21:47, Roberto Peon <[email-masked]> wrote:

> 1) Every header table entry has an 'overhead' associated with it, thus
> even zero-length strings have size.

---

From: Greg Wilkins <[email-masked]>
Date: Tue, 3 Jun 2014 16:30:23 +0200

Sorry more (hopefully not dumb) questions on the static table.

There appears to be no way to send an static indexed header field without
adding to the reference set.  So to actually use one of the following
static fields:

          | 2     | :method                     | GET          |
          | 3     | :method                     | POST         |
          | 4     | :path                       | /            |
          | 5     | :path                       | /index.html  |
          | 6     | :scheme                     | http         |
          | 7     | :scheme                     | https        |
          | 8     | :status                     | 200          |
          | 9     | :status                     | 204          |
          | 10    | :status                     | 206          |
          | 11    | :status                     | 304          |
          | 12    | :status                     | 400          |
          | 13    | :status                     | 404          |
          | 14    | :status                     | 500          |

it is a bit of a rigmarole:

   - You firstly send it as a indexed reference to the static table.
   - This is copied to the dynamic table, probably evicting an entry from
   the header table and possibly from the reference set.
   - The entry is then added to the reference set.
   - On the next message, you then very likely need to remove it (because
   one would hope that all your requests are not for /index.html nor all your
   responses 404s), so you have to send an indexed request again, this time to
   the index it currently has in the dynamic table.
   - Finally, you potentially now need to resend the header that was
   evicted from the headerset and reference table to get back to where you
   were... oh but dang that now evicts something else and so on and so forth
   until the unwanted 404 is eventually evicted!

Am I missing something again?

I'm thinking that if we really have to copy static entries into the header
table, then we need to be able to emit a static field without having it
included in the reference set.   Otherwise instead of being a single octet
to send a common status code, we are going to have to send at least 2 but
probably many more: as if the header table is >128 then static indexes will
not fit in a single byte and we'll also have to replace entries that have
been needlessly evicted.

Actually for status's like 404, it is better to send them as literal fields
never indexed with an indexed name.   To send :status:404 this way is just
(assuming empty header table):

  0x18 // literal never indexed, with static index 8==status:
  0x82 // huffman encoded 2 byte value
  0x8020 // 404 huffman encoded

So 4 bytes, but no evictions from the header table.   This could be 5 bytes
if the header table is large and thus the static index is >128  (why aren't
the static index's 1-61???)

On 2 June 2014 22:34, Greg Wilkins <[email-masked]> wrote:

>> Each duplicate reference causes the previous first entry to be evicted
>> and replaced.
>> Any time an entry is removed from the header table, the reference to it
>> in the reference set must be removed (can't have dangling references!).
>>
>> -=R
>>
>>

---

From: Greg Wilkins <[email-masked]>
Date: Tue, 3 Jun 2014 17:46:48 +0200

... and while I'm on a roll with my sweating of the small stuff in hpack....

The forever changing index's of common header fields makes encoding like
playing whack-a-mole and takes away some good optimisations available in
the server.

For example, if you know that several 10s of thousands of times in the next
1000ms you are going to send headers like:

  Date: Mon, 21 Oct 2013 20:13:22 GMT
  Server: Jetty/9.2.0
  Accept-Ranges: bytes

then you don't naively format the date and generate the exact bytes for
each and every response header.  You pre-generate the bytes for each field
and just to a block array copy to each response that needs them, then
regenerate the byte array for the data just 1 per second for all responses.

But with hpack, you can't do that because even though the huffman encoding
is always the same, the actual index of the header names will be constantly
changing and different for each connection. It is even moderately expensive
to just lookup to see if these headers are in the reference set and then if
they are in the header table so you know if you should use a dynamic index
or the static one, then you have to calculate the static one.

So currently I'm thinking that jetty wont use the index names for these
headers and send them in the more verbose literal form (which probably will
generate more garbage in the client - but hey not my problem:)

Hopefully such fields will be able to mostly live in the reference set, so
repetitions of sending them on the same connection can be limited - but I
was hoping to use that freed up CPU and bandwidth to server more
connections!

I'm really not feeling the luv'n for this copy the static field
whack-a-mole changing index thang!

It is implementable, but is it really worth it to limit the size of
something that was already size limited?

cheers

On 3 June 2014 16:30, Greg Wilkins <[email-masked]> wrote:

> Actually for status's like 404, it is better to send them as literal
> fields never indexed with an indexed name.   To send :status:404 this way
> is just (assuming empty header table):
>
> So 4 bytes, but no evictions from the header table.   This could be 5
> bytes if the header table is large and thus the static index is >128  (why
> aren't the static index's 1-61???)
>
>
>
>
>>> 3) Every entry in the reference set is unique-- there is no way to have
>>> a duplicate in there.
>>>
>>> In your example:
>>> Since the cost-in-bytes of the entry are (strlen(":path") + strlen("/")
>>> + 32) == 38, one entry fits into the table, but two do not. Referencing the
>>>> Consider a setup that has a small header table size that will fit just
>>>> a single field into in.  This decoder then receives a header frame that
>>>> If this kind of duplicate attack is not a problem, then I don't think
>>>> we need to limit the size of the reference set, because without such