Subject: [quicwg/base-drafts] QPACK: Encode Largest Reference modulo MaxEntries (#1763)

From: afrind <[email-masked]>
Date: Mon, 17 Sep 2018 19:59:08 -0700

Fixes #1644
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/1763

-- Commit Summary --

  * QPACK: Encode Largest Reference modulo MaxEntries

-- File Changes --

    M draft-ietf-quic-qpack.md (60)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/1763.patch
https://github.com/quicwg/base-drafts/pull/1763.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763

---

From: MikkelFJ <[email-masked]>
Date: Mon, 17 Sep 2018 21:57:47 -0700

Can the modulo be comited effectively on low-end devices?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422255396

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 18 Sep 2018 05:27:32 -0700

Would it make sense to describe the table as a "ring buffer" rather than a FIFO buffer with index calculation using modulo?

I think doing so would simplify the text and help readers understand the design (OTOH the downside being that you might need to change more text; e.g. by renaming `largest_reference` to `base_index`).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422371719

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 18 Sep 2018 13:09:18 +0000 (UTC)

@mikkelfj 
> Can the modulo be computed effectively on low-end devices?

You can. Since the divisor that is applied to header_table_size is 32 / 2, the size of the ring buffer (or the value used for truncating the offset) will be power-of-two assuming that the header table size is also a power-of-two.

For example, the size of the ring buffer will be 256 if the header table size is 4,096.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422386376

---

From: afrind <[email-masked]>
Date: Tue, 18 Sep 2018 06:31:06 -0700

@kazuho #1657 addresses the same issue using the approach you suggest, eg: describing the dynamic table as a ring buffer rather than FIFO.  This PR is meant to contrast that, and we'll discuss them both at the interim.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422393992

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 18 Sep 2018 06:43:51 -0700

@afrind Oh. I missed the context. Thank you for clarifying that.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422398525

---

From: MikkelFJ <[email-masked]>
Date: Tue, 18 Sep 2018 06:58:28 -0700

@kazuho I'm asking because I'm not into the details, and it could be that the peer decided a non-power of two, but perhaps you only need to do it on you own tables.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422403641

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 18 Sep 2018 07:04:40 -0700

> For example, the size of the ring buffer will be 256 if the header table size is 4,096.

You don't need an array that large, as you can only have 4096 / 32 = 128 entries.  One can do with 128-element ring buffer.

> it could be that the peer decided a non-power of two

That is true.  Nevertheless, I think that we do not need to accommodate systems that cannot perform modulo division.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422405978

---

From: MikkelFJ <[email-masked]>
Date: Tue, 18 Sep 2018 07:07:46 -0700

http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0475e/Chdifaha.html

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422406879

---

From: MikkelFJ <[email-masked]>
Date: Tue, 18 Sep 2018 07:15:19 -0700

http://ww1.microchip.com/downloads/en/AppNotes/doc0936.pdf

That is about 250 cycles per 16 bit division.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422409850

---

From: afrind <[email-masked]>
Date: Tue, 18 Sep 2018 07:19:39 -0700

Since one cannot *really* have a table full of 0 byte entries, you practically don't need even a MaxEntries/32 size ring buffer.  It's a nice memory optimization to allocate say only half that many entries, and resize it when needed.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422411527

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 18 Sep 2018 07:36:10 -0700

@dtikhonov 
> You don't need an array that large, as you can only have 4096 / 32 = 128 entries. One can do with 128-element ring buffer.

Implementation-wise that's correct. OTOH, let me note that the table size needs to be 4096 / 16 = 256 entries spec-wise so that we do not have ambiguity in if the Largest Reference refers to an entry yet to be delivered.

@afrind 
> Since one cannot really have a table full of 0 byte entries, you practically don't need even a MaxEntries/32 size ring buffer. It's a nice memory optimization to allocate say only half that many entries, and resize it when needed.

That is true. The overhead is 25% compared to the size of the header table on 64-bit architectures assuming that the ring buffer is implemented as an array of pointers. I am not sure if that is a deal blocker, but it is certainly an overhead.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422418166

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 18 Sep 2018 07:39:06 -0700

@kazuho, yes, one needs a boolean flag in addition to the array of `MaxEntries` in size.  The benefit of having an array of exactly `MaxEntries` long is that it can serve a second purpose: storing lists of blocked headers at exactly the point when they would become unblocked.  This eliminates the need to store the blocked headers in a more involved data structure such as min-heap.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#issuecomment-422419734

---

From: Mike Bishop <[email-masked]>
Date: Wed, 26 Sep 2018 15:22:09 -0700

MikeBishop approved this pull request.

> @@ -149,7 +149,9 @@ peer's SETTINGS frame.
 
 Before a new entry is added to the dynamic table, entries are evicted from the
 end of the dynamic table until the size of the dynamic table is less than or
-equal to (maximum size - new entry size) or until the table is empty.
+equal to (maximum size - new entry size) or until the table is empty. The
+encoder MUST not evict a dynamic table entry unless it has first been

MUST NOT

> +### Calculating Table Size
+
+The size of the dynamic table is the sum of the size of its entries.
+
+The size of an entry is the sum of its name's length in octets (as defined in
+{{string-literals}}), its value's length in octets, and 32.
+
+The size of an entry is calculated using the length of its name and value
+without any Huffman encoding applied.
+
+`MaxEntries` is the maximum number of entries that the dynamic table can have.
+The smallest entry has empty name and value strings and has the size of 32.
+The MaxEntries is calculated as
+
+~~~
+   MaxEntries = floor( MaxTableSize / 32 )

As we discussed, I'm unconvinced that this should be `floor` instead of `ceil`.  This will generally not matter much in the real world, but could break in edge cases.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#pullrequestreview-159217302

---

From: afrind <[email-masked]>
Date: Thu, 27 Sep 2018 09:59:27 -0700

afrind commented on this pull request.

+

I implemented the encoding/decoding algorithm using floor for max entries, and (after bug fixing) it works correctly for all the edge cases.

> -safe to process the rest of the block.
+safe to process the rest of the block.  If Largest Reference is greater than
+zero, the encoder transforms it as follows before encoding:
+
+~~~
+   LargestReference = LargestReference mod 2*MaxEntries + 1
+~~~
+
+The decoder reconstructs the Largest Reference using the following algorithm:
+
+~~~
+   if LargestReference > 0:
+      LargestReference -= 1
+      CurrentWrapped = TableLargestAbsoluteIndex mod 2*MaxEntries
+
+      if CurrentWrapped > LargestReference + MaxEntries:

There's a couple bugs here.  It should be >= not >, and there is another case: the decoder's largest index has wrapped more times than LR.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#pullrequestreview-159545226

---

From: afrind <[email-masked]>
Date: Thu, 27 Sep 2018 10:50:20 -0700

@afrind pushed 1 commit.

35ecdeb  s/MUST not/MUST NOT/

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763/files/00e13d93a5771defe558855c6cdcfdf29a10ab20..35ecdebb02e52b37d91957d7130aa77e26adadbd

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 28 Sep 2018 13:07:52 +0000 (UTC)

dtikhonov commented on this pull request.

+encoder MUST NOT evict a dynamic table entry unless it has first been

This is a much stricter limit than the one in the original proposal (#1644), which limits the number of unacked insertions to `MaxEntries`.  This restriction is used to prevent encoder from doing silly things.  I understand that we want this in, but I'd rather we did not put more than one change into a single commit.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#pullrequestreview-159850829

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 28 Sep 2018 06:13:41 -0700

+      if CurrentWrapped >= LargestReference + MaxEntries:

It seems this range is one too long: `[ LargestReference - MaxEntries, LargestReference + MaxEntries ]` is `2 * MaxEntries + 1` long, while the actual valid range is at most `2 * MaxEntries`.  I don't yet know whether this is a problem, as I have to get used to this version of the logic.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#pullrequestreview-159853030

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 28 Sep 2018 06:14:56 -0700

+

Why would it be `ceil`?  Integer division calls for `floor`.  What kind of edge cases do you mean, @MikeBishop?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#discussion_r221247967

---

From: afrind <[email-masked]>
Date: Fri, 28 Sep 2018 08:24:46 -0700

Ah.  That's a subtle difference I had missed.  This PR already has a couple things in it (how to calculate table size, for example).

If you have a more compact or straightforward way to express the logic I'll happily accept it.  I agree this is hard to read.  I wrote the conditionals using addition rather than subtraction to avoid underflow/negative number cases.

In my C++ code I also have an error check that LargestReference on the wire is in the range [0, 2*MaxEntries +1].  Perhaps we need a line saying that receiving an LR outside the valid range must result in a connection error?

That said, I'm pretty sure it works - I wrote a script to test it with a lot (~100B combinations) of different table sizes, decoder base and largest reference values and I get the correct decoded LR each time.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#discussion_r221289630

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 28 Sep 2018 15:48:33 +0000 (UTC)

I see.  I usually squash my commits when merging from a branch.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#discussion_r221299003

---

From: Dmitri Tikhonov <[email-masked]>
Date: Fri, 28 Sep 2018 15:49:03 +0000 (UTC)

OK.  As long as it works.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#discussion_r221299167

---

From: Mike Bishop <[email-masked]>
Date: Fri, 28 Sep 2018 09:25:20 -0700

It makes sense -- if it can be either `MaxEntries` greater *or* `MaxEntries` lesser, then you have `2*MaxEntries + 1` items, counting the one you're currently on.  There's always ambiguity at the far end -- the end values in the range are equivalent -- but because those ambiguous entries are always MaxEntries away, they can't be sent without evicting something unacknowledged or referencing something already evicted, both of which are prohibited.

+

I was concerned that the doubling could cause this to give us one less entry than we need, but after playing with some edge table sizes for a few minutes, this seems to work.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#pullrequestreview-159931664

---

From: afrind <[email-masked]>
Date: Fri, 28 Sep 2018 12:08:39 -0700

I think the phantom entry is `decoder base - MaxEntries`.  The encoder can be a full MaxEntries *ahead* of the decoder, but cannot reference a header MaxEntries less than decoder base, it has necessarily been evicted.  

As such, the second conditional should read 

`else if CurrentWrapped + MaxEntries < LargestReference`

My verification script had a bug that prevented it from testing this exact edge case!  It is the case where CurrentWrapped == MaxEntries - 1 and LargestReference = 2*MaxEntries - 1.  CurrentWrapped + MaxEntries identifies an entry the decoder does not yet have.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#discussion_r221353662

---

From: afrind <[email-masked]>
Date: Fri, 28 Sep 2018 14:00:36 -0700

@afrind pushed 1 commit.

0b39ceb  Fix another edge case

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763/files/35ecdebb02e52b37d91957d7130aa77e26adadbd..0b39ceb4830f4249060948bffe4a85d708f830c0