Subject: Re: [quicwg/base-drafts] Separate instruction sets for QCRAM (#1141)

From: Mike Bishop <[email-masked]>
Date: Thu, 01 Mar 2018 15:32:23 +0000 (UTC)

MikeBishop commented on this pull request.

> @@ -127,23 +127,180 @@ considered blocked by the decoder and can not be processed until all entries in
 the range `[1, Depends Index]` have been added.  While blocked, header
 field data MUST remain in the blocked stream's flow control window.
 
-# HPACK extensions
+# Wire Format
+
+QCRAM instructions occur on three stream types, each of which uses a separate
+instruction space:
+
+ - Table updates are carried by HEADERS frames on the control stream, as defined
+   by {{QUIC-HTTP}}.  Frames on this stream modify the dynamic table state
+   without generating output to any particular request.
+ - Acknowledgement of header frame processing is carried by HEADER_ACK frames,
+   running from decoder to encoder.
+ - Finally, the contents of HEADERS and PUSH_PROMISE frames on request streams
+   reference the QPACK table state.

Ah, you caught me!  I cribbed much of this text from QPACK-05.  ;-)  Missed a name change.

-- 
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/1141#discussion_r171595234

---

From: Mike Bishop <[email-masked]>
Date: Thu, 01 Mar 2018 15:36:22 +0000 (UTC)

+In order to ensure table consistency and simplify update management, all table
+updates occur on the control stream rather than on request streams. Request
+streams contain only header blocks, which do not modify the state of the table.
+
+## Primitives
+
+The prefixed integer from Section 5.1 of [RFC7541] is used heavily throughout
+this document.  The string literal, defined by Section 5.2 of [RFC7541], is used
+with the following modification.
+
+HPACK defines string literals to begin on a byte boundary.  They begin with a
+single flag (indicating whether the string is Huffman-coded), followed by the
+Length encoded as a 7-bit prefix integer, and finally Length octets of data.
+
+QCRAM permits strings to begin other than on a byte boundary.  An "N-bit prefix

Yes, I wrestled with that, too.  I'm inclined to say that once we start changing the instruction space, wire compatibility isn't a goal.  And that's the choice we need to make about the path forward.  You're correct that it's only a four-byte prefix, but that can represent header names up to 15 octets long; a surprising number of registered headers are fifteen octets or fewer (though in fairness, many of these are already in the static table or could be if we update it).

The other advantage of this is that, if we want to depart from HPACK one more step, it enables us to zero-base the tables rather than one-base the 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/1141#discussion_r171596533

---

From: Mike Bishop <[email-masked]>
Date: Thu, 01 Mar 2018 15:43:15 +0000 (UTC)

-This replaces the HPACK instruction for Dynamic Table Size Update (see Section
-6.3 of {{RFC7541}}, which is not supported by HTTP over QUIC.
+For header blocks encoded in non-blocking mode, the encoder needs to forego
+indexed representations that refer to table updates which have not yet been
+acknowledged with {{feedback}}.  An implementation could extend the header table
+entry with a boolean to track acknowledgement state.  However, the number of

You're correct, and Martin's feedback had been to remove assumptions of particular implementation styles anyway.  I think I'll just drop that and say the encoder needs to not do it, and leave how to track that as an exercise for the implementer.

-- 
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/1141#discussion_r171598912

---

From: Mike Bishop <[email-masked]>
Date: Thu, 01 Mar 2018 15:43:53 +0000 (UTC)

> -indexed representations that refer to vulnerable entries (see
-{{overview-hol-avoidance}}).  An implementation could extend the header table
-entry with a boolean to track vulnerability.  However, the number of entries in
-the table that are vulnerable is likely to be small in practice, much less than
-the total number of entries, so a data tracking only vulnerable
-(un-acknowledged) entries, separate from the main header table, might be more
-space efficient.
-
-### Safe evictions
-
-Section {{evictions}} describes how QCRAM avoids invalid references that might
-result from out-of-order delivery.  When the encoder processes a HEADER_ACK, it
-dereferences table entries that were indexed in the acknowledged header.  To
-track which entries must be dereferenced, it can maintain a map from
-unacknowledged headers to lists of (absolute) indices.  The simplest place to
-store the actual reference count might be the table entries.  In practice the

I'll let you and @martinthomson fight that out; I took it out based on his review.  ;-)

-- 
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/1141#discussion_r171599120

---

From: Mike Bishop <[email-masked]>
Date: Thu, 01 Mar 2018 15:45:15 +0000 (UTC)

@MikeBishop pushed 1 commit.

f3c5e27  Alan's feedback

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1141/files/8fba82d18acb9ef5fb840e9448c3e18f9fe86bd9..f3c5e27112da3ea416eafc74a905acbc19fa72b8

---

From: Mike Bishop <[email-masked]>
Date: Thu, 01 Mar 2018 07:48:24 -0800

c107af1  HEADER_ACK isn't a stream (yet)

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1141/files/f3c5e27112da3ea416eafc74a905acbc19fa72b8..c107af18da9e697e3acb83f38e737a5556487f7d

---

From: Martin Thomson <[email-masked]>
Date: Thu, 01 Mar 2018 21:58:17 +0000 (UTC)

martinthomson commented on this pull request.

I would have been happy with you changing it.  How about we add something in a separate PR?

-- 
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/1141#discussion_r171706938

---

From: Mike Bishop <[email-masked]>
Date: Thu, 01 Mar 2018 22:34:21 +0000 (UTC)

Note that the text at 476-485 touches on this as well.

> An encoder MUST ensure that a header block which references a dynamic table
> entry is not received by the decoder after the referenced entry has already been
> evicted...
> 
> In order to enable this, the encoder will need to track outstanding
> (unacknowledged) header blocks and table updates using feedback received from
> the decoder.

Keeping a refcount on the table entry is away of tracking this information.  We can fill in more detail about a suggested implementation if we want.

-- 
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/1141#discussion_r171715942

---

From: krasic <[email-masked]>
Date: Fri, 09 Mar 2018 18:01:40 +0000 (UTC)

krasic commented on this pull request.

My two cents. 

I think this and other PRs paint a pretty clear picture of moving further away from HPACK looks like.   There are some wins here for sure, but I'm not sure any of them are large enough to convince me that the moving away from HPACK is a good trade-off.   I *think* I heard the opposite at the Seattle interim, folks seemed to be favoring pursuit of the smallest changes with the biggest impact.   If the bar is that major changes should come with a big win, I'm not convinced that has been demonstrated.

I don't feel super strongly, but I'd feel a lot better with feedback from the broader WG.   Are we ok with making QPACK largely a re-write, or do we value the possibility to share implementation bits with HPACK?

-- 
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/1141#discussion_r173523004

---

From: Martin Thomson <[email-masked]>
Date: Fri, 09 Mar 2018 22:41:38 +0000 (UTC)

>From my perspective, the encoding of instructions is not a big point of divergence.  As this is the top-level of the encoder, and we need new instructions anyway, I found that you need to have a different parser at this layer.  Given that the benefits are clear, I don't see why we shouldn't do it.

-- 
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/1141#discussion_r173587070

---

From: Mike Bishop <[email-masked]>
Date: Mon, 19 Mar 2018 10:33:43 +0000 (UTC)

a5be5fe  Heading level

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1141/files/8bedd22b1cdfbb981d2337b99c31a46f7f2290bf..a5be5fe8cd8a93cd34a33f6e1546e2403ce07960