Subject: HPACK encoder/decoder memory bounding

From: Osama Mazahir <[email-masked]>
Date: Fri, 25 Oct 2013 02:09:09 +0000

Based on my understanding, the encoder and decoder have to have the exact same value for max-header-table-size so that the indices match.  So if the client advertises SETTINGS_HEADER_TABLE_SIZE=5MB then that means the client-decoder is using a header-table with maxsize=5MB.  Which means the server-encoder also has to use a header-table of maxsize=5MB.  But if the server only wants to use 4KB of encoder space then after storing 4KB worth of header name/values, it can only reuse from the initially stored 4KB or emit literals (either as-is or Huffman encoded).

So it seems to bound its memory usage, the server (in the above example) has to be choosy in what it adds to the server-encoder header-table because once something is added it cannot be removed (unless it decides to expand to 5MB+)?

Thanks,
--Osama.

---

From: Hervé Ruellan <[email-masked]>
Date: Fri, 25 Oct 2013 18:38:31 +0200

Hi Osama,

We discussed on this topic in the thread starting at:
http://lists.w3.org/Archives/Public/ietf-http-wg/2013OctDec/0221.html.

Basically, an encoder can choose to keep only the first 4 KB of its table,
discarding the rest. It will just not make any reference to the entries in
the table above the first 4 KB.
It the encoder wants also to reference the static table, this is more
complex (see the referred to thread for more details). It will work if the
maximum table size is 8 KB, and the encoder keeps only 4 KB of it, it will
not really work if the encoder wants to only keep 4 KB of a 5MB table.

Hervé.

On Fri, Oct 25, 2013 at 4:09 AM, Osama Mazahir <[email-masked]> wrote:

>  Based on my understanding, the encoder and decoder have to have the
> exact same value for max-header-table-size so that the indices match.  So
> if the client advertises SETTINGS_HEADER_TABLE_SIZE=5MB then that means the
> client-decoder is using a header-table with maxsize=5MB.  Which means the
> server-encoder also has to use a header-table of maxsize=5MB.  But if the
> server only wants to use 4KB of encoder space then after storing 4KB worth
> of header name/values, it can only reuse from the initially stored 4KB or
> emit literals (either as-is or Huffman encoded).****
>
> ** **
>
> So it seems to bound its memory usage, the server (in the above example)
> has to be choosy in what it adds to the server-encoder header-table because
> once something is added it cannot be removed (unless it decides to expand
> to 5MB+)?****
>
> ** **
>
> Thanks,****
>
> --Osama.****
>

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sat, 26 Oct 2013 01:37:22 +0900

On Fri, Oct 25, 2013 at 11:09 AM, Osama Mazahir <[email-masked]>wrote:

> **

Not necessarily.
They cannot be removed but eventually evicted. The encoder only uses
entries within first 4KB and it can push new headers to index-0. One tricky
part is that encoder must drop the entry from the reference table by
emitting indexed repr when the entry is in the reference set and out of
first 4KB.

The relevant discussion is
http://lists.w3.org/Archives/Public/ietf-http-wg/2013OctDec/0222.html

Best regards,
Tatsuhiro Tsujikawa

> **

---

From: Fred Akalin <[email-masked]>
Date: Fri, 25 Oct 2013 09:50:22 -0700

It seems tricky to me for an endpoint to use less than
SETTINGS_HEADER_TABLE_SIZE for its encoding state, especially since it
still has to use SETTINGS_HEADER_TABLE_SIZE for its decoding state.

Since we already need an ack for a header table size change, can we perhaps
piggyback a negotiated size (guaranteed to be <= the advertised size) onto
that ack? So a client can just send SETTINGS_HEADER_TABLE_SIZE=5MB, and a
memory-constraint server can ack with SETTINGS_HEADER_TABLE_SIZE=4K, and
both sides will then use 4K.

On Fri, Oct 25, 2013 at 9:38 AM, Hervé Ruellan <[email-masked]>wrote:

> On Fri, Oct 25, 2013 at 4:09 AM, Osama Mazahir <[email-masked]>wrote:
>

---

From: Roberto Peon <[email-masked]>
Date: Fri, 25 Oct 2013 09:55:32 -0700

Seems reasonable to me.
Make an issue so it can be discussed?
On Oct 25, 2013 9:52 AM, "Fred Akalin" <[email-masked]> wrote:

> Since we already need an ack for a header table size change, can we
> perhaps piggyback a negotiated size (guaranteed to be <= the advertised
> size) onto that ack? So a client can just send
> SETTINGS_HEADER_TABLE_SIZE=5MB, and a memory-constraint server can ack with
> SETTINGS_HEADER_TABLE_SIZE=4K, and both sides will then use 4K.
>
>
>> Basically, an encoder can choose to keep only the first 4 KB of its
>> table, discarding the rest. It will just not make any reference to the
>> entries in the table above the first 4 KB.

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sat, 26 Oct 2013 02:37:09 +0900

> SETTINGS_HEADER_TABLE_SIZE=4K, and both sides will then use 4K.
+1
This greatly simplifies the things.

Best regards,
Tatsuhiro Tsujikawa

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Oct 2013 10:46:46 -0700

> This greatly simplifies the things.

It does not simplify things.  Primarily because settings become
negotiable, which is a significant complication.  Is this the only
setting that is negotiable?  How do we signal that settings are
negotiable?

At worst, the cost to an encoder of an increased header table size
setting is an inability to use the static header table.  That means,
worst case, the encoder has to send a few more literals on the wire.
This is not significantly worse than sending
SETTINGS_HEADER_TABLE_SIZE=0.  In some respects, it's actually better.

---

From: Fred Akalin <[email-masked]>
Date: Fri, 25 Oct 2013 11:11:09 -0700

Filed https://github.com/http2/http2-spec/issues/300

> setting that is negotiable?  How do we signal that settings are

SETTINGS_HEADER_TABLE_SIZE is already special, since it requires an ack. It
doesn't seem that much more onerous to make it negotiable.

> SETTINGS_HEADER_TABLE_SIZE=0.  In some respects, it's actually better.

Remember that the setting applies to both contexts, so the other endpoint
is forced to keep a full-size context for the decoding state, or close the
connection. That doesn't seem good.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Oct 2013 11:18:13 -0700

> doesn't seem that much more onerous to make it negotiable.

All settings require an ACK.

> Remember that the setting applies to both contexts, so the other endpoint is
> forced to keep a full-size context for the decoding state, or close the

An encoder is not forced to track the entire table.  It only needs to
track the entries it wishes to use again.

Unless it wants to use the static table, in which case it has to track
the size of all the entries.  But it has a measure of control over
that too, since it decides what is added to the table in the first
place.

---

From: Fred Akalin <[email-masked]>
Date: Fri, 25 Oct 2013 11:25:48 -0700

> All settings require an ACK.

I see, I must have misunderstood something somewhere.

> is

Right, if I get a SETTINGS_HEADER_TABLE_SIZE=4MB and I can only afford to
store 4k, I can choose to encode things in such a way as to avoid using
more than 4k, avoiding the static table, etc. However, once I ack that
setting, the other endpoint will presumably use the entire 4MB for its
encoding state, so I'm forced to use 4MB for my own decoding state. Which
seems like a problem.

---

From: Mike Bishop <[email-masked]>
Date: Fri, 25 Oct 2013 18:31:12 +0000

No, the settings are one-way.  If the other side’s decoder is advertising 4MB, you’re allowed to encode against that 4MB space.  However, you’re free to encode using less if you want.  What the encoder MUST track is:
•             The size of each entry before the section it wishes to use (but not the contents)
•             The section of the header table it wishes to use, entirely at its discretion
•             The size of each entry beyond the section it wishes to use (but not the contents), only if it wishes to reference the static table

In reality, the first is likely to be an empty set (the server will probably be using most recent entries first), the second is entirely under the server’s control; the third should be manageably small (a few hundred bytes at most) and can be discarded in extreme need.

However, the fact that the remote decoder advertises 4MB is independent of your own decode – you can advertise as small a decoder window as you want, and the other side’s encoder must obey.

From: Fred Akalin [mailto:[email-masked]]
Sent: Friday, October 25, 2013 11:26 AM
To: Martin Thomson
Cc: Tatsuhiro Tsujikawa; Hervé Ruellan; Osama Mazahir; HTTP Working Group
Subject: Re: HPACK encoder/decoder memory bounding

On Fri, Oct 25, 2013 at 11:18 AM, Martin Thomson <[email-masked]<mailto:[email-masked]>> wrote:

Right, if I get a SETTINGS_HEADER_TABLE_SIZE=4MB and I can only afford to store 4k, I can choose to encode things in such a way as to avoid using more than 4k, avoiding the static table, etc. However, once I ack that setting, the other endpoint will presumably use the entire 4MB for its encoding state, so I'm forced to use 4MB for my own decoding state. Which seems like a problem.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Oct 2013 11:42:31 -0700

On 25 October 2013 11:31, Mike Bishop <[email-masked]> wrote:
> However, the fact that the remote decoder advertises 4MB is independent of
> your own decode – you can advertise as small a decoder window as you want,
> and the other side’s encoder must obey.

That's the key point.  I thought that that was understood already, sorry Fred.

---

From: Fred Akalin <[email-masked]>
Date: Fri, 25 Oct 2013 11:42:24 -0700

Okay, I was misunderstanding that, too! I think I'm clear on everything
now. In that case, I guess there's not a great need for negotiating that
parameter, then.

On Fri, Oct 25, 2013 at 11:31 AM, Mike Bishop
<[email-masked]>wrote:

>  No, the settings are one-way.  If the other side’s decoder is
> advertising 4MB, you’re allowed to encode against that 4MB space.  However,
> you’re free to encode using less if you want.  What the encoder MUST track
> is:****
>
> •             The size of each entry before the section it wishes to use
> (but not the contents)****
>
> •             The section of the header table it wishes to use, entirely
> at its discretion****
>
> •             The size of each entry beyond the section it wishes to use
> (but not the contents), only if it wishes to reference the static table***
> *
>
> ** **
>
> In reality, the first is likely to be an empty set (the server will
> probably be using most recent entries first), the second is entirely under
> the server’s control; the third should be manageably small (a few hundred
> bytes at most) and can be discarded in extreme need.****
>
> ** **
>
> and the other side’s encoder must obey.****
>
> ** **
>
> *From:* Fred Akalin [mailto:[email-masked]]
> *Sent:* Friday, October 25, 2013 11:26 AM
> *To:* Martin Thomson
> *Cc:* Tatsuhiro Tsujikawa; Hervé Ruellan; Osama Mazahir; HTTP Working
> Group
> *Subject:* Re: HPACK encoder/decoder memory bounding****
>
> ** **
>
> On Fri, Oct 25, 2013 at 11:18 AM, Martin Thomson <[email-masked]>
> wrote:****
>
> > doesn't seem that much more onerous to make it negotiable.****
>
> All settings require an ACK.****
>
>  ** **
>
> I see, I must have misunderstood something somewhere.****
>
> ** **
>
> > connection. That doesn't seem good.****
>
> place.****
> seems like a problem.****
>

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Oct 2013 11:44:11 -0700

On 25 October 2013 11:42, Fred Akalin <[email-masked]> wrote:
> I think I'm clear on everything now.

Let me know if you think that there is anything unclear in the
draft(s).  I'm happy to fix anything that is even slightly ambiguous
or vague.

---

From: Fred Akalin <[email-masked]>
Date: Fri, 25 Oct 2013 11:46:50 -0700

I went back and checked the draft and the setting description was clear; I
just glossed over the key phrase '...used to decode header blocks.'

I thought about suggesting that _DECODE_ be put in the settings name, but I
don't know if that would actually be clearer. And the other settings are
"one-way" anyway.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Oct 2013 11:55:07 -0700

> just glossed over the key phrase '...used to decode header blocks.'

Actually, I just scanned, and thought that perhaps this might help:

            Settings are not negotiated.  Settings are sent
independently by both peers.  Different
            values for the same setting can be advertised by each
peer.  For example, a client might
            set a high initial flow control window, whereas a server
might set a lower value to
            conserve resources.

Also:

   SETTINGS_HEADER_TABLE_SIZE:
                    Allows the sender to inform the remote endpoint of
the size of the header
                    compression table used to decode header blocks.
The space available for
                    encoding cannot be changed; it is determined by
the setting sent by the peer
                    that receives the header blocks.  The initial
value is 4096 bytes.

How does that sound?

---

From: Fred Akalin <[email-masked]>
Date: Fri, 25 Oct 2013 12:10:49 -0700

> might set a lower value to

Perhaps:

"Settings apply only to the sending peer, and different ..." instead of
"Settings are sent independently by both peers."?

>                     that receives the header blocks.  The initial

sgtm.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Oct 2013 12:29:07 -0700

> "Settings are sent independently by both peers."?

Sold.

---

From: Mike Bishop <[email-masked]>
Date: Fri, 25 Oct 2013 19:45:31 +0000

That introduces a new confusion around "apply" -- the setting I send reflects my expectation of your behavior.  Does that apply to me (the sending peer) because it's my state, or apply to you because you're the one who has to comply?  I think I prefer Martin's wording, focusing on them being sent individually -- let the descriptions of individual settings express who they "apply" to.

-----Original Message-----
From: Martin Thomson [mailto:[email-masked]] 
Sent: Friday, October 25, 2013 12:29 PM
To: Fred Akalin
Cc: Mike Bishop; Tatsuhiro Tsujikawa; Hervé Ruellan; Osama Mazahir; HTTP Working Group
Subject: Re: HPACK encoder/decoder memory bounding

On 25 October 2013 12:10, Fred Akalin <[email-masked]> wrote:
> Perhaps:
>
> "Settings apply only to the sending peer, and different ..." instead 
> of "Settings are sent independently by both peers."?

Sold.

---

From: Martin Thomson <[email-masked]>
Date: Fri, 25 Oct 2013 13:33:02 -0700

On 25 October 2013 12:45, Mike Bishop <[email-masked]> wrote:
> That introduces a new confusion around "apply" -- the setting I send reflects my expectation of your behavior.

Yes, the setting I send is about me, but it constrains your behaviour.

Maybe that's what I need to say...

---

From: Fred Akalin <[email-masked]>
Date: Fri, 25 Oct 2013 16:17:20 -0700

What about something like: "Each endpoint has its own set of settings
values, but also keeps track of its peer's set. An endpoint sends a
SETTINGS frame to inform the other endpoint of changes to its set."

A bit wordy, I guess.

On Fri, Oct 25, 2013 at 1:33 PM, Martin Thomson <[email-masked]>wrote:

> > That introduces a new confusion around "apply" -- the setting I send
> reflects my expectation of your behavior.
>

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sat, 26 Oct 2013 09:58:18 +0900

A bit related question, when does the sender of SETTINGS apply its change?
Before ACK is introduced, it is applied on transmittion. Now is it when ACK
is received?  It seems so because sender-decoder may use different value of
table size without this which lead currupted decoding. This means that
sender has to keep track of all in-flight SETTINGS.

Best regsrds,
Tatsuhiro Tsujikawa

---

From: Fred Akalin <[email-masked]>
Date: Fri, 25 Oct 2013 23:19:09 -0700

As I understand it, it applies it when the ACK is received; that was one of
the reasons to introduce the ACK.

---

From: Roberto Peon <[email-masked]>
Date: Sat, 26 Oct 2013 09:17:34 -0700

Correct .

The decoder always gets to request an encoder size change, and as soon as
the request change as taken effect at the encoder, an ACK is inserted into
the outgoing stream.

The decoder may then allocate/deallocate state (depending on the direction
of the change, upwards vs downwards) when it receives the ACK.
-=R

On Fri, Oct 25, 2013 at 11:19 PM, Fred Akalin <[email-masked]> wrote:

> As I understand it, it applies it when the ACK is received; that was one
> of the reasons to introduce the ACK.
>
>
> On Fri, Oct 25, 2013 at 5:58 PM, Tatsuhiro Tsujikawa <
> [email-masked]> wrote:
>
>> A bit related question, when does the sender of SETTINGS apply its
>> change? Before ACK is introduced, it is applied on transmittion. Now is it
>> when ACK is received?  It seems so because sender-decoder may use different
>> value of table size without this which lead currupted decoding. This means
>> that sender has to keep track of all in-flight SETTINGS.
>>
>> Best regsrds,
>> Tatsuhiro Tsujikawa
>>

---

From: Martin Thomson <[email-masked]>
Date: Sat, 26 Oct 2013 13:37:37 -0700

> of the change, upwards vs downwards) when it receives the ACK.

Not "may", MUST.  Otherwise it doesn't work ;)

---

From: Roberto Peon <[email-masked]>
Date: Sat, 26 Oct 2013 15:04:15 -0700

Yes yes. :)

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Sun, 27 Oct 2013 13:01:15 +0900

Thank you for clarifying that.
I feel it would be good to state explicitly that sender of SETTINGS without
ACK applies its change on the reception of SETTINGS with ACK, because, as I
understand, while the draft 07 states about the timing of application for
receiver,  it does not for the sender.

Best regards,
Tatsuhiro Tsujikawa

---

From: Martin Thomson <[email-masked]>
Date: Sun, 27 Oct 2013 13:45:27 -0700

> receiver,  it does not for the sender.

That is a good suggestion.

https://github.com/http2/http2-spec/commit/ed887feed8c7f0088ebddb92cbbb2fa54e4efbc9