Subject: Header Compression Clarifications

From: James M Snell <[email-masked]>
Date: Tue, 2 Jul 2013 14:42:49 -0700

Need just a few simple clarifications...

1. Can the Header Table include duplicates? For instance, if the
sender sends a Literal With Incremental or Substitution Indexing for a
name+value that already exists in the Header Table. The sender
shouldn't do this, but a buggy/malicious sender might. It's obviously
bad behavior but it's not yet clear if it's an error.

2. If the sender sends a Literal with Substitution Indexing
referencing an Index position that is not yet currently filled. This
ought to be an error but it's not specified. For instance, let's
suppose the Header Table has five entries (Index #0...4) currently and
the sender sends a Substitution instruction referencing index #5.
Obviously the sender is doing something wrong.

3. The Header Compression draft currently requires that header name
matching in the header table be case *insensitive*. However, the
current HTTP/2 implementation draft only says that HTTP Header Field
names are lower cased. There is no indication in the main HTTP/2
specification indicating that ALL header names (even hypothetical
non-HTTP headers that may come around later) must be lowercased.

---

From: Roberto Peon <[email-masked]>
Date: Tue, 2 Jul 2013 14:54:44 -0700

1: There is currently no prohibition against this.
2: seems reasonable
3: I think we should change that so we only deal with lowercased keys
consistently.

---

From: James M Snell <[email-masked]>
Date: Tue, 2 Jul 2013 15:05:20 -0700

Also...

4. On the eviction strategy... The spec currently states: "When an
entry is added to the header table, if the header table size is
greater than the limit, the table size is reduced by dropping the
entries at the beginning of the table until the header table size
becomes lower than or equal to the limit.  Dropping entries from the
beginning of the table causes a renumbering of the remaining entries."

Does the size check and adjustment occur BEFORE or AFTER adding the
new entry to the table? The difference is critical for proper
implementation of the Indexing with Substitution case.  Example:

Existing table (max size 15)

  0: FOO = 123
  1: BAR = 321
  2: BA = Z

Substitute: TESTING = FOO at Index #0 ...

If the size check and adjustment occurs BEFORE substitution, we end up
removing the first two existing indexes, causing BA = Z to be
renumbered as #0, then do the substitution which ends up replacing BA
= Z leaving "TESTING = FOO" as the only thing left in the buffer.

If the size check occurs AFTER substitution, we replace "FOO = 123"
with "TESTING = FOO" then immediately drop it from the table, leaving
"BAR = 321" as 0 and "BA = Z" as 1.

Pseudocode for first case:

  Entry entry
  While (Buffer.Size + entry.Size > MAX_SIZE):
    Buffer.Pop()
  Buffer.replace(0, entry)

Pseudocode for second case:

  Entry entry
  Buffer.replace(0, entry)
  While (Buffer.Size > MAX_SIZE):
    Buffer.Pop()

---

From: James M Snell <[email-masked]>
Date: Tue, 2 Jul 2013 15:50:58 -0700

On Tue, Jul 2, 2013 at 3:11 PM, Roberto Peon <[email-masked]> wrote:
> It should be before as this guarantees that the maximum memory size is not
> exceeded.
> The other approach offers no such guarantee, and becomes an interesting
> attack vector.

Well, I agree but... just teasing out edge cases while I write up unit
tests... Consider a simplistic example:

Header Table, Max size = 15

1  A = B
2  C = D
3  E = F
4  G = H
5  I = J

Substitute #5 with FOOBARBAZ = 123456

If we reserve before... items 1-5 to be removed and the table to be
emptied... Then we attempt to do the substitution, index #5 no longer
exists... In the previous question, we already established that
attempting to substitute an index that currently does not exist should
result in an error.

- James

>
> -=R
>
>
> On Tue, Jul 2, 2013 at 3:05 PM, James M Snell <[email-masked]> wrote:
>>
>> Also...
>>

---

From: Roberto Peon <[email-masked]>
Date: Tue, 2 Jul 2013 15:52:01 -0700

yup. That'd mean you couldn't insert that in substitution mode, which seems
fine.
-=R

---

From: Roberto Peon <[email-masked]>
Date: Tue, 2 Jul 2013 15:53:08 -0700

Herve is probably not available yet, but I suspect he might argue the other
way...
-=R

On Tue, Jul 2, 2013 at 3:52 PM, Roberto Peon <[email-masked]> wrote:

> yup. That'd mean you couldn't insert that in substitution mode, which
> seems fine.
> -=R
>
>

---

From: Roberto Peon <[email-masked]>
Date: Tue, 2 Jul 2013 16:00:01 -0700

I take that back-- ( I didn't have a substitution mode in delta, so I have
to page back in discussions with Herve from some time ago now :) )
What should be illegal is referencing a slot which doesn't have anything in
it.

If it does have something in it, you continue popping stuff until you can
put it in. That may end up clearing the table entirely.

We do need to clarify what happens when you attempt to stick something in
there which is, ont its own + entry overhead > max state size (I think the
safest thing is that we declare that a protocol error).

So, an example:
Imagine that you're replacing entry #10 with something 10 characters long.
The previous entry in that slot was 5 characters long, and the table was
already at max size.
This implies that you need to get rid of 5 characters before replacing.
Assuming that items 1 and 2 are the oldest items and item 1 is 3 chars, and
item 2 is 3 chars, you need to pop two.

You now stick the 10 characters into what was formerly entry #10.

-=R

---

From: James M Snell <[email-masked]>
Date: Tue, 2 Jul 2013 16:37:44 -0700

On Tue, Jul 2, 2013 at 4:00 PM, Roberto Peon <[email-masked]> wrote:
[snip]
>[snip]

That's problematic too. Let's go back to my example:

1  A = B
2  C = D
3  E = F
4  G = H
5  I = J

Obviously, we end up popping all five entries, saying "stick the new
characters into what was formerly entry #5" does not make any sense
because the thing that was "formerly entry #5" no longer exists.

Now a variation on the same problem:

Header Table, Max size = 20

1  A = B
2  C = D
3  E = F
4  G = H
5  I = J
6  K = L
7  M = N

Substitute #3 with FOOBARBAZ = 123456

We begin popping things off to make room before doing the
substitution... 4 entries are removed, including the item being
replaced... leaving

1  I = J
2  K = L
3  M = N

What exactly do we replace? Are we replacing "M = N" (the current #3)?
If so, how does that sync up with the "thing that was formerly entry
#3" idea?

I think the only reliable approach is to substitute AFTER freeing up
space, substitute into whatever is in the index position after freeing
up space, and if nothing is in that space, return an error. This means
that the sender has to be careful to avoid getting into this state in
the first place, which means very careful control over when and how
substitution is being used. Given the current eviction strategy, that
would be the most reliable approach I think. So in the two examples
above, the first case returns an error and the second case results in
"M = N" being replaced.

---

From: Roberto Peon <[email-masked]>
Date: Tue, 2 Jul 2013 17:07:42 -0700

The biggest reason that I don't like this is that it requires the encoder
keep more state.
I prefer to make this simple by having an easy-to-follow rule for when it
the slot it would have replaced would have been evicted (once all
predecessors to that slot have been evicted, then elements following the
element-to-be-replaced are removed, leaving the new element at the head of
the list).

The pseudo code for this is:

if not replacement_idx or new_element_size > max_table_size:
  PROTOCOL_ERROR()
if max_table_size ==new_element_size:
  table.clear()
  table[0] = new_element
  return

# above is boilerplate true for any algorithm

table[replacement_idx].clear()
table[replacement_idx].pin()
first_non_pinned = 0
while new_element_size + table_byte_size() > max_table_size:
    if table[first_non_pinned].pinned():
      ++first_non_pinned
       continue
      table[first_non_pinned].pop()

This adds some small complexity here, but it makes encoding significantly
easier (you can have a naive encoder which leaps without looking, which is
far less complicated than having to look before leap, and may still prove
reasonable in terms of compressor efficiency).

I admit that I'm attracted to your idea. I just am afraid of what it makes
the encoder look like :)
-=R

---

From: James M Snell <[email-masked]>
Date: Tue, 2 Jul 2013 17:18:03 -0700

So to make sure I have it right... Given the two examples I gave...

  1  A = B
  2  C = D
  3  E = F
  4  G = H
  5  I = J

The result would be a Header table with one item "FOOBARBAZ = 123456"

And...

  1  A = B
  2  C = D
  3  E = F
  4  G = H
  5  I = J
  6  K = L
  7  M = N

The result would be a Header table with three items...

  FOOBARBAZ = 123456
  K = L
  M = N

Is that correct?

---

From: Roberto Peon <[email-masked]>
Date: Tue, 2 Jul 2013 17:27:38 -0700

Correct (assuming the overhead per item was assumed to be zero, which isn't
the case, but is good in example-land :) )

-=R

On Tue, Jul 2, 2013 at 5:18 PM, James M Snell <[email-masked]> wrote:

> >> > Assuming that items 1 and 2 are the oldest items and item 1 is 3
> chars,
> >> > and

---

From: James M Snell <[email-masked]>
Date: Tue, 2 Jul 2013 17:36:24 -0700

Yes, I was simplifying :-) I think that rule should work..
particularly in that it allows me to avoid having to check for as many
of these weird edge cases.

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 4 Jul 2013 13:02:12 +0000

+1

Hervé.

> -----Original Message-----
> From: Roberto Peon [mailto:[email-masked]]
> Sent: mardi 2 juillet 2013 23:55
> To: James M Snell
> Cc: [email-masked]
> Subject: Re: Header Compression Clarifications
>

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 4 Jul 2013 13:09:42 +0000

Trying to catch on the discussion, I see three proposals for solving the problem of substitution and eviction.

1. Size adjustment BEFORE doing the substitution.
This has several edge case problems as James showed and would lead to complex implementations.

2. Size adjustment AFTER doing the substitution.
The problem is that the new entry may be dropped just after adding it.

3. Size adjustment BEFORE doing the substitution with pinning of the replaced entry (Roberto's proposal).

I think that 2 and 3 are in fact close together.
With 2, a bad encoder could just have its new entry dropped from the table just after adding it. However a good encoder could use an algorithm like the one propose in 3 to find the right entry to replace and prevent dropping the new entry.
On the decoder side, 2 is simpler.

Taking James' example for what a "good" encoder should do.
With existing table (max size 15)
  0: FOO = 123
  1: BAR = 321
  2: BA = Z

The encoder wants to substitute: TESTING = FOO at Index #0 (because entry #0 is old or whatever).
It detects that index #0 and #1 need to be dropped, and therefore adjust the substitution to replace Index #2.
It then can apply the substitution, and after that adjust the size.

So my preference is for the second solution. True, it can lead to under-optimal usage of the header table. But I'm not in favor of making all implementations more complex to help optimize bad implementations.
We should however warn implementers of this problem.

Hervé.

> From: James M Snell [mailto:[email-masked]]
> Sent: mercredi 3 juillet 2013 02:36
> To: Roberto Peon
> Cc: [email-masked]
> particularly in that it allows me to avoid having to check for as many of these
> weird edge cases.
> 
> > Correct (assuming the overhead per item was assumed to be zero, which
> > isn't the case, but is good in example-land :) )
> >
> > -=R
> >
> >
> >> > The biggest reason that I don't like this is that it requires the
> >> > encoder keep more state.
> >> > I prefer to make this simple by having an easy-to-follow rule for
> >> > when it the slot it would have replaced would have been evicted
> >> > (once all predecessors to that slot have been evicted, then
> >> > elements following the element-to-be-replaced are removed, leaving
> >> > the new element at the head of the list).
> >> >
> >> > This adds some small complexity here, but it makes encoding
> >> > significantly easier (you can have a naive encoder which leaps
> >> > without looking, which is far less complicated than having to look
> >> > before leap, and may still prove reasonable in terms of compressor
> >> > efficiency).
> >> >
> >> > I admit that I'm attracted to your idea. I just am afraid of what
> >> > it makes the encoder look like :) -=R
> >> >
> >> >
> >> >> > The previous entry in that slot was 5 characters long, and the
> >> >> > table was already at max size.
> >> >> > chars, and item 2 is 3 chars, you need to pop two.
> >> >> >
> >> >> Obviously, we end up popping all five entries, saying "stick the
> >> >> new characters into what was formerly entry #5" does not make any
> >> >> sense because the thing that was "formerly entry #5" no longer exists.
> >> >>
> >> >> If so, how does that sync up with the "thing that was formerly
> >> >> entry #3" idea?
> >> >>
> >> >> I think the only reliable approach is to substitute AFTER freeing
> >> >> up space, substitute into whatever is in the index position after
> >> >> freeing up space, and if nothing is in that space, return an
> >> >> error. This means that the sender has to be careful to avoid
> >> >> getting into this state in the first place, which means very
> >> >> careful control over when and how substitution is being used.
> >> >> Given the current eviction strategy, that would be the most
> >> >> reliable approach I think. So in the two examples above, the first
> >> >> case returns an error and the second case results in "M = N" being
> replaced.
> >> >
> >> >
> >
> >

---

From: Michael Sweet <[email-masked]>
Date: Thu, 04 Jul 2013 09:47:50 -0400

What about simply not allowing indexing for name/value pairs that exceed SETTINGS_MAX_BUFFER_SIZE?  Both sides could still send "long" literal name/value pairs but they would not disrupt the header table.  When combined with #2 or #3 that should yield consistent and useful results.

>>>>>> case returns an error and the second case results in "M = N" being

_________________________________________________________
Michael Sweet, Senior Printing System Engineer, PWG Chair

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 4 Jul 2013 14:06:41 +0000

I'm not sure I understand correctly your comment.

One of the goal of the eviction mechanism is to provide a solution to the possible problem of header table fragmentation over long-lasting connections: if the header table is full of very small entries, then substituting a long entry to one of these small entries will make the header table grow over its maximum allowed size. The eviction mechanism enable to allow for such a substitution while still keeping the header table under its maximum allowed size.

Hervé.

> From: Michael Sweet [mailto:[email-masked]]
> Sent: jeudi 4 juillet 2013 15:48
> To: RUELLAN Herve
> Cc: James M Snell; Roberto Peon; [email-masked]
> What about simply not allowing indexing for name/value pairs that exceed
> SETTINGS_MAX_BUFFER_SIZE?  Both sides could still send "long" literal
> name/value pairs but they would not disrupt the header table.  When
> combined with #2 or #3 that should yield consistent and useful results.
> 
> 
> > With 2, a bad encoder could just have its new entry dropped from the table
> just after adding it. However a good encoder could use an algorithm like the
> one propose in 3 to find the right entry to replace and prevent dropping the
> new entry.
> > So my preference is for the second solution. True, it can lead to under-
> optimal usage of the header table. But I'm not in favor of making all
> implementations more complex to help optimize bad implementations.
> >> particularly in that it allows me to avoid having to check for as
> >> many of these weird edge cases.
> >>
> >>> Correct (assuming the overhead per item was assumed to be zero,
> >>> which isn't the case, but is good in example-land :) )
> >>>
> >>> -=R
> >>>
> >>>
> >>>>>> reliable approach I think. So in the two examples above, the
> >>>>>> first case returns an error and the second case results in "M =
> >>>>>> N" being
> >> replaced.
> >>>>>
> >>>>>
> >>>
> >>>
> >
>

---

From: Michael Sweet <[email-masked]>
Date: Thu, 04 Jul 2013 10:47:12 -0400

Hervé,

> One of the goal of the eviction mechanism is to provide a solution to the possible problem of header table fragmentation over long-lasting connections: if the header table is full of very small ent…

Right, I am just addressing the "I want to add a name/value pair that is 100 bytes long but the header table size is 50 bytes." - what happens if you try substitution/incremental indexing with a name/value pair that is larger than the header table?

We *could* just say that doing so empties the header table and doesn't add the pair to it (because it won't fit), but I don't think that is particularly useful.

Instead I am suggesting that such name/value pairs must always use the Literal Header without Indexing representation - that allows for header name reuse (e.g. cookie) and otherwise preserves the header table.  Otherwise I see certain headers (e.g. cookie) effectively killing any benefits of the header compression scheme.

---

From: James M Snell <[email-masked]>
Date: Thu, 4 Jul 2013 07:56:52 -0700

Adding a header that is too large for the table to hold individually after
eviction ought to be a compression error.
On Jul 4, 2013 7:47 AM, "Michael Sweet" <[email-masked]> wrote:

> > One of the goal of the eviction mechanism is to provide a solution to
> the possible problem of header table fragmentation over long-lasting
> connections: if the header table is full of very small entries, then
> substituting a long entry to one of these small entries will make the
> header table grow over its maximum allowed size. The eviction mechanism
> enable to allow for such a substitution while still keeping the header
> table under its maximum allowed size.
>
> Right, I am just addressing the "I want to add a name/value pair that is
> 100 bytes long but the header table size is 50 bytes." - what happens if
> you try substitution/incremental indexing with a name/value pair that is
> larger than the header table?
>
> We *could* just say that doing so empties the header table and doesn't add
> the pair to it (because it won't fit), but I don't think that is
> particularly useful.
>
> Instead I am suggesting that such name/value pairs must always use the
> Literal Header without Indexing representation - that allows for header
> name reuse (e.g. cookie) and otherwise preserves the header table.
>  Otherwise I see certain headers (e.g. cookie) effectively killing any
> benefits of the header compression scheme.
>
>
> >
> > Hervé.
> >
> >>> Trying to catch on the discussion, I see three proposals for solving
> the
> >> problem of substitution and eviction.
> >>>
> >>> It detects that index #0 and #1 need to be dropped, and therefore
> adjust
> >> the substitution to replace Index #2.

---

From: Michael Sweet <[email-masked]>
Date: Thu, 04 Jul 2013 11:08:57 -0400

I agree, but we don't talk about errors in the current draft nor do we talk about what the client or server does to recover...  As a first step it would be useful to say what you do for such headers...

On Jul 4, 2013, at 10:56 AM, James M Snell <[email-masked]> wrote:
> Adding a header that is too large for the table to hold individually after eviction ought to be a compression error.
>

---

From: Amos Jeffries <[email-masked]>
Date: Fri, 05 Jul 2013 03:34:08 +1200

On 5/07/2013 2:47 a.m., Michael Sweet wrote:
> Hervé,
>
> On Jul 4, 2013, at 10:06 AM, RUELLAN Herve wrote:

+1. This sounds like a useful and clean solution to that particular 
class of edge case.

Amos

---

From: Roberto Peon <[email-masked]>
Date: Thu, 4 Jul 2013 11:07:28 -0700

The approach of add-then-enforce guarantee has a glaring and huge problem--
 it cannot guarantee the amount of memory I'll use.
I'd much rather deal with some small complexity (demonstrably not big) here
and have that guarantee.
-=R

On Thu, Jul 4, 2013 at 6:09 AM, RUELLAN Herve <[email-masked]>wrote:

> just after adding it. However a good encoder could use an algorithm like
> the one propose in 3 to find the right entry to replace and prevent
> dropping the new entry.
> So my preference is for the second solution. True, it can lead to
> under-optimal usage of the header table. But I'm not in favor of making all

---

From: James M Snell <[email-masked]>
Date: Thu, 4 Jul 2013 11:22:53 -0700

+1..  The additional complexity is minimal.
On Jul 4, 2013 11:07 AM, "Roberto Peon" <[email-masked]> wrote:

> The approach of add-then-enforce guarantee has a glaring and huge
> problem--  it cannot guarantee the amount of memory I'll use.
> I'd much rather deal with some small complexity (demonstrably not big)
> here and have that guarantee.
> -=R
>
>
>> With 2, a bad encoder could just have its new entry dropped from the
>> table just after adding it. However a good encoder could use an algorithm
>> like the one propose in 3 to find the right entry to replace and prevent
>> dropping the new entry.

---

From: Gábor Molnár <[email-masked]>
Date: Thu, 04 Jul 2013 23:28:16 +0200

Let's consider the memory management of a real implementation. When there's
an incoming "Literal Header Representation with Substitution Indexing" ,
the implementation first needs to assemble the header name and value
*somewhere* in memory. After that, it probably passes around pointers to
these buffers and the header table is just an array of pointers plus
administration data.

I think there's two interesting consequences of this:
 * since the new header is already in the memory somewhere, it doesn't
really matter if we do add-then-enforce or enforce-then-add, both the old
header table and the new name-value pair has to fit into the memory
 * the size of name-value pairs should be bounded as well

I'm not very experienced in using programming languages with manual memory
management, so please correct me if that's not a reasonable model for a C
implementation for example.

2013/7/4 Roberto Peon <[email-masked]>

---

From: Gábor Molnár <[email-masked]>
Date: Fri, 05 Jul 2013 04:44:19 +0200

2013/7/4 Gábor Molnár <[email-masked]>

> Let's consider the memory management of a real implementation. When
> there's an incoming "Literal Header Representation with Substitution
> Indexing" , the implementation first needs to assemble the header name and
> value *somewhere* in memory. After that, it probably passes around pointers
> to these buffers and the header table is just an array of pointers plus
> administration data.
>

Just realized that bounding the size of name-value pairs is probably not an
option, since HTTP does not limit
header name/value length.

>> On Thu, Jul 4, 2013 at 6:09 AM, RUELLAN Herve <[email-masked]
>> > wrote:
>>
>>> first

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 5 Jul 2013 08:35:16 +0000

If you need to guarantee the amount of memory used in the add-then-enforce approach, you can use an algorithm similar to the one you proposed:

first_non_pinned = 0
while new_element_size + table_byte_size() > max_table_size:
  table[first_non_pinned].pop()
  if first_non_pinned == replacement_idx:
    new_element.clear()
    break # Should not insert new_element in table

So the question is: do we want this small complexity in all cases, or only for memory constrained cases?

Hervé.

> Sent: jeudi 4 juillet 2013 20:07
> To: RUELLAN Herve
> Cc: James M Snell; [email-masked]
> On Thu, Jul 4, 2013 at 6:09 AM, RUELLAN Herve
> <[email-masked]> wrote:
> 
> 
> 	With 2, a bad encoder could just have its new entry dropped from
> the table just after adding it. However a good encoder could use an algorithm
> adjust the substitution to replace Index #2.
> 	> >> On Tue, Jul 2, 2013 at 5:07 PM, Roberto Peon
> <[email-masked]>
> 	> wrote:
> 	> >> > On Tue, Jul 2, 2013 at 4:37 PM, James M Snell
> <[email-masked]>
> 	> wrote:
> 	> >> >>
> 	> >> >> On Tue, Jul 2, 2013 at 4:00 PM, Roberto Peon
> <[email-masked]>
> 	> wrote:
> 	> >> >> [snip]
> 	> >> >> >
> 	> >> >> > So, an example:
> 	> >> >> What exactly do we replace? Are we replacing "M = N" (the
> current
> 	> #3)?