Subject: All changes but huffman encoding integrated + a question

From: Roberto Peon <[email-masked]>
Date: Tue, 15 Oct 2013 19:25:26 -0700

Just wanted to let people know that the github version of the compression
spec includes all issues but huffman encoding (Herve and Jeff-- thanks)!

I believe there is a potential ambiguity though, which I'm not sure if
people realize or care about (and so asking here before potentially
throwing mud in clear water)...

When adding a new header to the header table, one must first evict entries.
When using the indexed-name literal header representation, it is possible
that one may be evicting the entry that contains the name which the new
addition would need (and which needed to be examined in order to determine
the amount of space to free up in the first place).

There are two obvious resolutions:
1) Require that the name be kept in these circumstances (possibly by
copying somewhere (ideally into the end of the buffer)). If the storage for
the header table was a ring buffer, one would simply increment the '0'
index without copying.
This is my preference.

2) Make this illegal; This makes the encoder more complex as the encoder
must attempt to do this encoding and then check to see if actually fit
every time it does this kind of header representation.

What do people think?

-=R

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Wed, 16 Oct 2013 11:43:13 +0900

> the header table was a ring buffer, one would simply increment the '0'
+1
I actually did this in nghttp2 implementation (well, it does not use ring
buffer at the moment, just keep reference of entry in indexed name, so that
I get no segmentation fault).

Best regards,

Tatsuhiro Tsujikawa

---

From: Martin Thomson <[email-masked]>
Date: Tue, 15 Oct 2013 20:35:05 -0700

On 15 October 2013 19:25, Roberto Peon <[email-masked]> wrote:
> must attempt to do this encoding and then check to see if actually fit every
> time it does this kind of header representation.

Not to want to contradict Tatsuhiro, but I thought that you argued
pretty strongly for this one.  Something about a linear memory model.
I got the impression that this was OK with people, mainly because it
was perfectly consistent: evict, then add.

Did something change?

---

From: Roberto Peon <[email-masked]>
Date: Tue, 15 Oct 2013 21:07:07 -0700

The problem here occurs when one is evicting what one is adding.

This can be handled without ever using more memory that allocated to the
compression context. One can also deal with this by copying just the name
(as opposed to the whole name+value-list), if one is willing to trade size
for complexity.

A ring buffer *is* a linear memory model-- it requires only a linear range
of memory. When I talk about a linear memory model without heap
fragmentation, this is what I am talking about.

-=R
On Oct 15, 2013 8:35 PM, "Martin Thomson" <[email-masked]> wrote:

> every

---

From: Fred Akalin <[email-masked]>
Date: Tue, 15 Oct 2013 21:25:25 -0700

+1 to #1, too. I didn't run into this yet because I passed around strings
by value, but I can imagine this coming up for an optimized implementation.

---

From: Martin Thomson <[email-masked]>
Date: Tue, 15 Oct 2013 21:51:58 -0700

> (as opposed to the whole name+value-list), if one is willing to trade size

Well, you were the one arguing for 2 before.  If you're happy with
either, that's good.

---

From: RUELLAN Herve <[email-masked]>
Date: Thu, 17 Oct 2013 14:43:59 +0000

I think that these two resolutions are linked to the order in which eviction and addition occurs.

In 1), we add, then evict.

In 2), we evict, then add.

The current spec states 2), without a clearly specifying what an index for the header name means when there is an eviction.

1) may be slightly easier for the encoder, but is slightly more complex for a decoder.
1) would also make the spec slightly easier to read.

I've no strong opinion one way or another.

Hervé.

> -----Original Message-----
> From: Roberto Peon [mailto:[email-masked]]
> Sent: mercredi 16 octobre 2013 04:25
> To: HTTP Working Group
> Subject: All changes but huffman encoding integrated + a question
> 
> I believe there is a potential ambiguity though, which I'm not sure if people
> realize or care about (and so asking here before potentially throwing mud in
> clear water)...
> 
> addition would need (and which needed to be examined in order to
> determine the amount of space to free up in the first place).
> 
> 1) Require that the name be kept in these circumstances (possibly by copying
> somewhere (ideally into the end of the buffer)). If the storage for the
> header table was a ring buffer, one would simply increment the '0' index
> without copying.
> This is my preference.
>

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Oct 2013 10:59:21 -0700

Add-then-evict generally implies that the amount of memory consumed is
potentially 2X the stated max size.
The proposed #1 boils down more to Evict or Move, then Add
-=R

On Thu, Oct 17, 2013 at 7:43 AM, RUELLAN Herve
<[email-masked]>wrote:

> The current spec states 2), without a clearly specifying what an index for
> the header name means when there is an eviction.
>
> people
> copying

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 18 Oct 2013 11:02:18 +0000

I think that #1 is a smart implementation of add then evict.

I agree that a naïve implementation of add then evict could consume 2x the max size. I think that a smart implementation can avoid this.

Hervé.

> Sent: jeudi 17 octobre 2013 19:59
> To: RUELLAN Herve
> Cc: HTTP Working Group
> Subject: Re: All changes but huffman encoding integrated + a question
> 
> The proposed #1 boils down more to Evict or Move, then Add -=R
> 
> 
> <[email-masked]> wrote:
> 
> 
> 	The current spec states 2), without a clearly specifying what an index
> for the header name means when there is an eviction.
>