Subject: Removing dropped entry from ref set

From: Mike Bishop <[email-masked]>
Date: Mon, 23 Sep 2013 20:37:03 +0000

Found a corner case that I’m not sure HPACK handles, or if it does I’m not finding it and we might want to clarify….

Sequence of events:

  *
Header X is present in reference set and header table.
  *
Some other addition to the header table causes header X to be dropped.  (This could be a header that causes X to be dropped, or a substitution operation that replaces X.)

  *
Now the compressor wishes to remove X from the reference set.  How does it do so?

Per 3.2.1, the only operation that has the effect of removing an entry from the reference set is an indexed representation of a header already in the reference set.  But you can’t send the indexed representation of a header no longer in the header table.

To address it, we could say:

  *
Replacing X with another entry in the header table also replaces X in the reference set.  This makes perfect sense, but needs to be stated.
  *
Dropping X from the header table also drops it from the reference set.  This is more problematic, because the compressor can’t just pass over headers it wants to communicate which are already in the reference set.  Instead, it needs to leave them until the end, then check if they’re all still in the reference set.  If not, it needs to take another action to emit one or more, then check that all the remaining are still in the reference set…  This loops until the entire remaining set is still present.

Am I missing something simple here?

Sent from Windows Mail

---

From: Andrew Rockwell <[email-masked]>
Date: Mon, 23 Sep 2013 20:51:11 +0000

Roberto clarified this a while ago:
“Any removal from the state set requires that anything that pointed to it be removed (else you'd segv or equivalent).
Thus, substitution or expiry always requires the corresponding reference-set entry to be removed.”

There’s a GitHub issue open tracking its inclusion into the spec, though it hasn’t seen any love in a bit: https://github.com/http2/http2-spec/issues/238

Andrew

From: Mike Bishop [mailto:[email-masked]]
Sent: Monday, September 23, 2013 1:37 PM
To: [email-masked]
Subject: Removing dropped entry from ref set

Sequence of events:

  *   Header X is present in reference set and header table.

  *   Some other addition to the header table causes header X to be dropped.  (This could be a header that causes X to be dropped, or a substitution operation that replaces X.)

  *   Now the compressor wishes to remove X from the reference set.  How does it do so?

  *   Replacing X with another entry in the header table also replaces X in the reference set.  This makes perfect sense, but needs to be stated.

  *   Dropping X from the header table also drops it from the reference set.  This is more problematic, because the compressor can’t just pass over headers it wants to communicate which are already in the reference set.  Instead, it needs to leave them until the end, then check if they’re all still in the reference set.  If not, it needs to take another action to emit one or more, then check that all the remaining are still in the reference set…  This loops until the entire remaining set is still present.

Sent from Windows Mail

---

From: Fred Akalin <[email-masked]>
Date: Mon, 23 Sep 2013 13:51:24 -0700

On Mon, Sep 23, 2013 at 1:37 PM, Mike Bishop
<[email-masked]>wrote:

>  Found a corner case that I’m not sure HPACK handles, or if it does I’m
> not finding it and we might want to clarify….
>
>  Sequence of events:
>
>    - Header X is present in reference set and header table.
>    - Some other addition to the header table causes header X to be
>    dropped.  (This could be a header that causes X to be dropped, or a
>    substitution operation that replaces X.)
>
>
>    - Now the compressor wishes to remove X from the reference set.  How
>    does it do so?
>
>
>  Per 3.2.1, the only operation that has the effect of removing an entry
> from the reference set is an indexed representation of a header already in
> the reference set.  But you can’t send the indexed representation of a
> header no longer in the header table.
>

>From 3.1.3: "A reference set is defined as an unordered set of references
to entries of the header table." I interpret this to mean that when an
entry is removed from the header table, it's removed from the reference set
also.

>    -  *Replacing X with another entry in the header table also replaces X
>    in the reference set.*  This makes perfect sense, but needs to be
>    stated.
>    -  *Dropping X from the header table also drops it from the reference
>    set.*  This is more problematic, because the compressor can’t just
>    pass over headers it wants to communicate which are already in the
>    reference set.  Instead, it needs to leave them until the end, then check
>    if they’re all still in the reference set.  If not, it needs to take
>    another action to emit one or more, then check that all the remaining are
>    still in the reference set…  This loops until the entire remaining set is
>    still present.
>
>
You'll need to take the appropriate action when an entry in the reference
set gets dropped, which is most likely explicitly emitting it before it
gets dropped. I ran into this same problem, which Tatsuhiro Tsujikawa
pointed out: see
https://github.com/akalin-chromium/httpbis-header-compression/issues/1 .

---

From: Mike Bishop <[email-masked]>
Date: Tue, 24 Sep 2013 02:12:38 +0000

Yes, that's a reasonable interpretation.  While the spec could be clearer, I think that's the correct reading.  That still leaves open the question about correct behavior, though.  You said "You'll need to take the appropriate action when an entry in the reference set gets dropped, which is most likely explicitly emitting it before it gets dropped."  Is this appropriate action on the part of the compressor, or the decompressor?

If the compressor, what action is that -- does it need to notice that an entry it cares about is going to be dropped and immediately encode two indexed references to it, forcing it to be emitted before it's dropped?  Or is it an appropriate action on the decompressor's part, which means the compressor needs to ensure that nothing in the reference set it wishes to remove falls off the list before it gets removed?

Sent from Windows Mail

From: Fred Akalin<mailto:[email-masked]>
Sent: ?Monday?, ?September? ?23?, ?2013 ?1?:?51? ?PM
To: Mike Bishop<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>

On Mon, Sep 23, 2013 at 1:37 PM, Mike Bishop <[email-masked]<mailto:[email-masked]>> wrote:
Found a corner case that I'm not sure HPACK handles, or if it does I'm not finding it and we might want to clarify....

Sequence of events:

  *

  *

Per 3.2.1, the only operation that has the effect of removing an entry from the reference set is an indexed representation of a header already in the reference set.  But you can't send the indexed representation of a header no longer in the header table.

>From 3.1.3: "A reference set is defined as an unordered set of references to entries of the header table." I interpret this to mean that when an entry is removed from the header table, it's removed from the reference set also.

  *
Replacing X with another entry in the header table also replaces X in the reference set.  This makes perfect sense, but needs to be stated.
  *
Dropping X from the header table also drops it from the reference set.  This is more problematic, because the compressor can't just pass over headers it wants to communicate which are already in the reference set.  Instead, it needs to leave them until the end, then check if they're all still in the reference set.  If not, it needs to take another action to emit one or more, then check that all the remaining are still in the reference set...  This loops until the entire remaining set is still present.

You'll need to take the appropriate action when an entry in the reference set gets dropped, which is most likely explicitly emitting it before it gets dropped. I ran into this same problem, which Tatsuhiro Tsujikawa pointed out: see https://github.com/akalin-chromium/httpbis-header-compression/issues/1 .

---

From: Roberto Peon <[email-masked]>
Date: Mon, 23 Sep 2013 19:27:34 -0700

The appropriate action is to remove the item, and then you are done. Tests
I did in the past indicated that inokicit expiry was better than explicit
expiry both in terms of on the wire size and in terms of reducing error
cases.

The compressor and decompressor must always make the same decision, so the
compressor needs to ensure that it emits what is necessary to encode the
correct data. This may well involve encoding data that used to be present
or was present when the first key/value was encoded but was dropped before
the encoder realized it could have used it.

This is one of the places where a better implementation of an encoder will
have a benefit-- it can construct a better ordering (which may toggle the
entry twice) in order to yield better compression.

-=R
On Sep 23, 2013 7:16 PM, "Mike Bishop" <[email-masked]> wrote:

>  Yes, that’s a reasonable interpretation.  While the spec could be
> clearer, I think that’s the correct reading.  That still leaves open the
> question about correct behavior, though.  You said “You'll need to take the
> appropriate action when an entry in the reference set gets dropped, which
> is most likely explicitly emitting it before it gets dropped.”  Is this
> appropriate action on the part of the compressor, or the decompressor?
>
>  If the compressor, what action is that -- does it need to notice that an
> entry it cares about is going to be dropped and immediately encode two
> indexed references to it, forcing it to be emitted before it’s dropped?  Or
> is it an appropriate action on the decompressor’s part, which means the
> compressor needs to ensure that nothing in the reference set it wishes to
> remove falls off the list before it gets removed?
>
>  Sent from Windows Mail
>
>   *From:* Fred Akalin <[email-masked]>
> *Sent:* Monday, September 23, 2013 1:51 PM
> *To:* Mike Bishop <[email-masked]>
> *Cc:* [email-masked]
>
>   On Mon, Sep 23, 2013 at 1:37 PM, Mike Bishop <
> [email-masked]> wrote:
>
>  >From 3.1.3: "A reference set is defined as an unordered set of
> references to entries of the header table." I interpret this to mean that
> when an entry is removed from the header table, it's removed from the
> reference set also.
>
>
>>    -  *Replacing X with another entry in the header table also replaces
>>    X in the reference set.*  This makes perfect sense, but needs to be
>>    stated.
>  You'll need to take the appropriate action when an entry in the
> reference set gets dropped, which is most likely explicitly emitting it
> before it gets dropped. I ran into this same problem, which Tatsuhiro
> Tsujikawa pointed out: see

---

From: Fred Akalin <[email-masked]>
Date: Mon, 23 Sep 2013 20:00:21 -0700

The responsibility is on the encoder. There's no room for decision on the
decoding side. The encoder could even encode it as a literal etc.

On Monday, September 23, 2013, Mike Bishop wrote:

>   *From:* Fred Akalin <javascript:_e({}, 'cvml', [email-masked]');>
> *Sent:* ‎Monday‎, ‎September‎ ‎23‎, ‎2013 ‎1‎:‎51‎ ‎PM
> *To:* Mike Bishop <javascript:_e({}, 'cvml',
> [email-masked]');>
> *Cc:* [email-masked] <javascript:_e({}, 'cvml',
> [email-masked]');>
>
>    another action to emit one or more, then check t
>
>

---

From: Gábor Molnár <[email-masked]>
Date: Tue, 24 Sep 2013 13:23:08 +0200

2013/9/24 Mike Bishop <[email-masked]>

> remove falls off the list before it gets removed?

That is the responsibility of the encoder. I would recommend having a look
at Tatsuhiro's encoder algorithm which deals with these corner cases
correctly:
http://lists.w3.org/Archives/Public/ietf-http-wg/2013JulSep/1135.html

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Tue, 24 Sep 2013 21:29:02 +0900

This question was asked several times in the list, which is a good
indication that the
clarification is desirable in the draft.

Best regards,

Tatsuhiro Tsujikawa

On Tue, Sep 24, 2013 at 5:51 AM, Andrew Rockwell <[email-masked]>wrote:

>  Roberto clarified this a while ago:****
>
> “Any removal from the state set requires that anything that pointed to it
> be removed (else you'd segv or equivalent).****
>
> Thus, substitution or expiry always requires the corresponding
> reference-set entry to be removed.”****
>
> ** **
>
> There’s a GitHub issue open tracking its inclusion into the spec, though
> it hasn’t seen any love in a bit:
> https://github.com/http2/http2-spec/issues/238
>
> Andrew****
>
> ** **
>
> *From:* Mike Bishop [mailto:[email-masked]]
> *Sent:* Monday, September 23, 2013 1:37 PM
> *To:* [email-masked]
> *Subject:* Removing dropped entry from ref set****
>
> ** **
>
> Found a corner case that I’m not sure HPACK handles, or if it does I’m not
> finding it and we might want to clarify….****
>
> ** **
>
> Sequence of events:****
>
>    - Header X is present in reference set and header table.****
>
>
>    substitution operation that replaces X.)****
>
>
>    does it do so?****
>  ** **
> header no longer in the header table.****
>
> ** **
>
> To address it, we could say:****
>
>    stated.****
>    still present.****
>  ** **
> Am I missing something simple here?****
>
> ** **
>
> Sent from Windows Mail****
>
> ** **
>