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

From: Mike Bishop <[email-masked]>
Date: Tue, 27 Feb 2018 01:33:58 +0000 (UTC)

Fixes #1123 by introducing a split instruction space between HEADERS-on-Control, HEADER_ACK, and HEADERS/PUSH_PROMISE-on-Request/Push streams.  Explicitly does not attempt to address #1122 (yet), so HEADER_ACK frames are still on the control stream, discrete frames, etc.  Did a little rearranging in the process to make this flow a little better, though there are still some sections that feel out-of-place ({{index-encoding}}).

Note that I have opted to use a static/dynamic bit.  Not only does that make explaining #1130 much simpler, but the number of bytes consumed to reference any given entry should be roughly equivalent given this instruction set.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Separate instruction sets

-- File Changes --

    M draft-ietf-quic-qcram.md (306)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/1141.patch
https://github.com/quicwg/base-drafts/pull/1141.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/1141

---

From: Martin Thomson <[email-masked]>
Date: Tue, 27 Feb 2018 03:18:14 +0000 (UTC)

martinthomson commented on this pull request.

Feel free to push back on some of the comments.  I'm probably drawing on a whole tapestry of issues.

I think that with this split, we also need a clearer split in terminology.

I propose using "header block" to refer to the representation instructions.  That is, the thing that goes in HEADERS/PUSH_PROMISE.

Then "table update" is the thing that goes on the header streams (or control stream if you prefer).

> +# 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.
+
+This section describes the instructions which are possible on each stream type.
+
+In order to ensure table consistency, all modifications of the header table

This also simplifies table updates.  Is that worth pointing out?

> +   +---+---+-----------------------+
+   | H |     Value Length (7+)     |
+   +---+---------------------------+
+   | Value String (Length octets)  |
+   +-------------------------------+
+~~~~~~~~~~
+{: title="Insert Header Field -- Indexed Name"}
+
+Otherwise, the header field name is represented as a string literal (see Section
+5.2 of [RFC7541]). A value 0 is used in place of the table reference, followed
+by the header field name.
+
+~~~~~~~~~~ drawing
+     0   1   2   3   4   5   6   7
+   +---+---+---+---+---+---+---+---+
+   | 1 |             0             |

I think that you need to include the S bit here explicitly.  Saying that it must be zero is fine, but if you don't show it, it gets a little weird.  11000000 is then invalid, which wastes a codepoint.  That is unfortunate, but I guess there isn't much value in trying to reclaim that in any way.

> +   reference the QPACK table state.
+
+This section describes the instructions which are possible on each stream type.
+
+In order to ensure table consistency, all modifications of the header table
+occur on the control stream rather than on request streams. Request streams
+contain only indexed and literal header entries.
+
+## HEADERS Frames on the Control Stream
+
+### Insert
+
+An addition to the header table starts with the '1' one-bit pattern. If the
+header field name matches the header field name of an entry stored in the static
+table or the dynamic table, the header field name can be represented using the
+index of that entry. In this case, the `S` bit indicates whether the reference

I think that you need to introduce the concept better first.  That is,

"An insertion can reference an existing table entry and use its name.  The `S` bit is used to indicate whether the entry is in the static table (where `S` is set to 1) or the dynamic table (where `S` is 0).  The index that follows is an integer with a **6**-bit prefix.

> +This section describes the instructions which are possible on each stream type.
+
+In order to ensure table consistency, all modifications of the header table
+occur on the control stream rather than on request streams. Request streams
+contain only indexed and literal header entries.
+
+## HEADERS Frames on the Control Stream
+
+### Insert
+
+An addition to the header table starts with the '1' one-bit pattern. If the
+header field name matches the header field name of an entry stored in the static
+table or the dynamic table, the header field name can be represented using the
+index of that entry. In this case, the `S` bit indicates whether the reference
+is to the static (S=1) or dynamic (S=0) table and the index of the entry is
+represented as an integer with an 7-bit prefix (see Section 5.1 of [RFC7541]).

6-bit

> +
+In order to ensure table consistency, all modifications of the header table
+occur on the control stream rather than on request streams. Request streams
+contain only indexed and literal header entries.
+
+## HEADERS Frames on the Control Stream
+
+### Insert
+
+An addition to the header table starts with the '1' one-bit pattern. If the
+header field name matches the header field name of an entry stored in the static
+table or the dynamic table, the header field name can be represented using the
+index of that entry. In this case, the `S` bit indicates whether the reference
+is to the static (S=1) or dynamic (S=0) table and the index of the entry is
+represented as an integer with an 7-bit prefix (see Section 5.1 of [RFC7541]).
+This value is always non-zero.

Table indices are always non-zero.  A zero index is reserved for literal names.

> +### Duplicate {#indexed-duplicate}
+
+An entry currently in the dynamic table can be re-inserted into the dynamic
+table without resending the header.
+
+~~~~~~~~~~ drawing
+     0   1   2   3   4   5   6   7
+   +---+---+---+---+---+---+---+---+
+   | 0 |         Index (7+)        |
+   +---+---------------------------+
+~~~~~~~~~~
+{:#fig-index-with-duplication title="Duplicate"}
+
+This is useful to mitigate the eviction of older entries which are frequently
+referenced, both to avoid the need to resend the header and to avoid the entry
+in the table blocking the ability to insert new headers.

You also need to point out that 10000000 is invalid.

> +   |  Name String (Length octets)  |
+   +---+---------------------------+
+   | H |     Value Length (7+)     |
+   +---+---------------------------+
+   | Value String (Length octets)  |
+   +-------------------------------+
+~~~~~~~~~~
+{: title="Insert Header Field -- New Name"}
+
+Either form of header field name representation is followed by the header field
+value represented as a string literal (see Section 5.2 of [RFC7541]).
+
+### Duplicate {#indexed-duplicate}
+
+An entry currently in the dynamic table can be re-inserted into the dynamic
+table without resending the header.

I wonder if it isn't worth your while to include a section on indices and their representation and use.  This really needs to be more explicit about the fact that "Index" refers to the dynamic table.

-## Header Block Prefix {#absolute-index}
+The frame payload contains contains a variable-length integer (as defined in
+{{QUIC-TRANSPORT}}) which indicates the stream on which the header block was
+processed. The same Stream ID can be identified multiple times, as multiple
+header-containing blocks can be sent on a single stream in the case of

"header blocks"

-## Header Block Prefix {#absolute-index}
+The frame payload contains contains a variable-length integer (as defined in
+{{QUIC-TRANSPORT}}) which indicates the stream on which the header block was
+processed. The same Stream ID can be identified multiple times, as multiple
+header-containing blocks can be sent on a single stream in the case of
+intermediate responses, trailers, pushed requests, etc. as well as on the

The complete set is: headers and trailers for requests.  Responses can be *(1XX,PUSH_PROMISE), Status, *PUSH_PROMISE ?Trailers. Why not list the entire set?

Or are you trying to retain the weaselly language that we ended up with in 7540 about other HEADERS frames - because the compromise that we made there doesn't work for QUIC.

-## Header Block Prefix {#absolute-index}
+The frame payload contains contains a variable-length integer (as defined in
+{{QUIC-TRANSPORT}}) which indicates the stream on which the header block was
+processed. The same Stream ID can be identified multiple times, as multiple
+header-containing blocks can be sent on a single stream in the case of
+intermediate responses, trailers, pushed requests, etc. as well as on the
+Control Streams.  Since header frames on each stream are received and processed

I don't understand the part about "on the Control Streams"  I would cut it, unless you think it is important.

> @@ -178,7 +274,7 @@ is the largest (absolute) index referenced by the following header block.  To
 help keep the prefix smaller, `Depends Index` is converted to a relative value:
 `Depends = Base Index - Depends Index`.
 
-## Hybrid absolute-relative indexing {#overview-absolute}
+#### Hybrid absolute-relative indexing {#overview-absolute}

h3 is fine.

> @@ -178,7 +274,7 @@ is the largest (absolute) index referenced by the following header block.  To
 help keep the prefix smaller, `Depends Index` is converted to a relative value:
 `Depends = Base Index - Depends Index`.
 
-## Hybrid absolute-relative indexing {#overview-absolute}
+#### Hybrid absolute-relative indexing {#overview-absolute}

BTW, this section is still basically incomprehensible.  Either way, I think that you want to move this elsewhere (in another PR if you must) and be much clearer about how indexing works.  In practice, it is fairly straightforward, but every time I try to read this text, it only makes things worse.

The way that I would characterize this:

Static indices reference the static table directly.

Dynamic indices reference the dynamic table.  Because the dynamic table changes constantly, indices are all made relative to a point in the table that doesn't change.  This is called the base.  The base is a count of the number of insertions into the dynamic table.  Base always increases.  

Header blocks use indices that are relative to a base that is declared at the start of the header block encoding.  If the current base of the decoder table is greater than the base associated with an index, then more updates have been added since the encoder created the header block.  The index into the current table is increased by the difference.  That is:
```
current_index = relative_index + table.base - header_block.base
```

A decoder should always wait until the current base of its table is less than the base of a header block, because this indicates that there are indices in the header block that reference table updates that haven't yet been received.   (TODO: decide whether a decoder can force an encoder into a non-blocking mode, or to control how many header blocks can block.)

Note that I have used the term "header block" to refer to what goes in HEADERS/PUSH_PROMISE.  I think that we should refer to the thing that makes changes to the table as a table update.

> @@ -223,15 +319,111 @@ It is an error if the HPACK decoder encounters an indexed representation that
 refers to an entry missing from the table, and the connection MUST be closed
 with the `HTTP_HPACK_DECOMPRESSION_FAILED` error code.
 
-## Preventing Eviction Races {#evictions}
+### Instructions
+
+#### Indexed Header Field Representation
+
+An indexed header field representation identifies an entry in either the static
+table or the dynamic table and causes that header field to be added to the
+decoded header list, as described in Section 3.2 of [RFC7541].
+
+~~~~~~~~~~ drawing
+  0   1   2   3   4   5   6   7
++---+---+---+---+---+---+---+---+
+| 1 | S |      Index (6+)       |
++---+---------------------------+

This line has only one +.

> +
+~~~~~~~~~~ drawing
+  0   1   2   3   4   5   6   7
++---+---+---+---+---+---+---+---+
+| 1 | S |      Index (6+)       |
++---+---------------------------+
+~~~~~~~~~~
+{: title="Indexed Header Field"}
+
+An indexed header field starts with the '1' 1-bit pattern, followed by the `S`
+bit indicating whether the reference is into the static (S=1) or dynamic (S=0)
+table. Finally, the index of the matching header field is represented as an
+integer with a 6-bit prefix (see Section 5.1 of [RFC7541]).
+
+The index value of 0 is not used.  It MUST be treated as a decoding error if
+found in an indexed header field representation.

For later:  It might be possible to allow an index of 0 for one or other table.  The efficiency gains are likely minuscule, but it might simplify some things.

For instance, if it the dynamic table started at zero, then you could populate static[0] with the empty string and condition the name literal on getting the empty string.  For me, that would reduce the odd -1 condition (arrays are zero indexed and HPACK is weird), but it might not be worth doing if you have both this and HPACK to worry about.

> +
+The second bit, 'N', indicates whether an intermediary is permitted to add this
+header to the dynamic header table on subsequent hops. When the 'N' bit is set,
+the encoded header MUST always be encoded with this specific literal
+representation. In particular, when a peer sends a header field that it received
+represented as a literal header field with the 'N' bit set, it MUST use the same
+representation to forward this header field.  This bit is intended for
+protecting header field values that are not to be put at risk by compressing
+them (see Section 7.1 of [RFC7541] for more details).
+
+If the header field name matches the header field name of an entry stored in the
+static table or the dynamic table, the header field name can be represented
+using the index of that entry. In this case, the `S` bit indicates whether the
+reference is to the static (S=1) or dynamic (S=0) table and the index of the
+entry is represented as an integer with an 5-bit prefix (see Section 5.1 of
+[RFC7541]). This value is always non-zero.

You can't guarantee that it be non-zero, so you should say what to do if it is zero.

-### Blocked Evictions
+An encoder MUST ensure that an indexed representation is not received by the

Or a literal with an indexed name...

-### Blocked Evictions
+An encoder MUST ensure that an indexed representation is not received by the
+encoder after the referenced entry has already been evicted, and might wish to
+ensure that the decoder will not suffer head-of-line blocking when encoding
+particular references.
+
+In order to enable this, the encoder MUST track outstanding (unacknowledged)
+header blocks on request streams and MAY track outstanding header blocks on the
+control stream.

See above comment about "header blocks" and terminology.

-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 vulnerable entries (see
+{{overview-hol-avoidance}}).  An implementation could extend the header table

This notion of vulnerable entries is unnecessarily obfuscation in this design.  This is simpler than this: an encoder can't use an insertion until it is acknowledged with HEADER_ACK.

The predecessor QCRAM might have needed this indirection because it coupled different streams together in complicated ways.  This is no longer true.

-# Performance considerations
+To track blocked streams, an ordered map (e.g. multi-map) from `Depends Index`
+values to streams can be used.  Whenever the decoder processes a header block on
+the control stream, it can drain any members of the blocked streams map that now
+have their dependencies satisfied.

Why this complication?  The encoder only needs to track the number of insertions that have been acknowledged.

It gets more complicated if you want to limit the number of blocked decoders, but I'm not yet convinced that we need that feature.  In that case, you only track header blocks that might be blocked and what they block on.

-- 
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#pullrequestreview-99540844

---

From: Mike Bishop <[email-masked]>
Date: Tue, 27 Feb 2018 17:35:02 +0000 (UTC)

MikeBishop commented on this pull request.

Side-thought sparked by your comment.  There are effectively four instructions:

1. Insert with static table name reference
2. Insert with dynamic table name reference
3. Insert with no reference
4. Duplicate (a.k.a. insert with name+value reference)

We're effectively using two bit prefixes for (1)/(2-3), a sentinel value in the index to differentiate (2)/(3), and (4) gets a single-bit instruction code even though it's the least common.

We could save a few bytes by using two-bit codes for everything and dropping the sentinel zeros for (3), except that HPACK defines string literals to begin on a byte boundary.

-- 
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_r171004404

---

From: Mike Bishop <[email-masked]>
Date: Tue, 27 Feb 2018 17:47:20 +0000 (UTC)

That's a separate planned PR.  As Alan has noted, there are at least three ways indexes are encoded/used, so it's worth explaining.

-- 
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_r171008169

---

From: Mike Bishop <[email-masked]>
Date: Tue, 27 Feb 2018 17:51:07 +0000 (UTC)

That's subject to #1122.  If the table updates are carried as frames on the control stream, you need these to know how far the decoder has processed.  If we decide on a different framing mechanism for the table updates, I'll remove the reference to the control stream here.

-- 
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_r171009397

---

From: Mike Bishop <[email-masked]>
Date: Tue, 27 Feb 2018 17:52:23 +0000 (UTC)

Yes, another PR.  I wanted to do this one first, because if we eliminate the conjoined static+dynamic table from the instruction set, that PR gets easier.

-- 
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_r171009831

---

From: Mike Bishop <[email-masked]>
Date: Tue, 27 Feb 2018 17:54:55 +0000 (UTC)

+~~~~~~~~~~ drawing
+  0   1   2   3   4   5   6   7

Yes.  I believe this is a natural fallout from the fact that string literals always start on a byte boundary.  It winds up being easier to have a sentinel value than unused bits.

If you can start strings not on a boundary, then you can eliminate the sentinel and permit 0 as a valid index in each table.

-- 
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_r171010645

---

From: Mike Bishop <[email-masked]>
Date: Tue, 27 Feb 2018 10:07:26 -0800

@MikeBishop pushed 1 commit.

875c5e5  Martin'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/2c904781a4cfa7f16c0ca2c905182d74aa7d7c6f..875c5e5f43b035c7ce5a4f1b6ba839a36ce28eb8

---

From: Martin Thomson <[email-masked]>
Date: Tue, 27 Feb 2018 23:52:13 +0000 (UTC)

Having a string literal with a 6-bit prefix would be a little bit annoying to implement, but no more than 15 minutes of hacking (to add the extra argument).  And it would save a whole byte for most, if not all insertions that need a new name.  Names longer than 62 octets are - if not completely unknown - very rare.  I like the idea.

-- 
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_r171105623

---

From: Martin Thomson <[email-masked]>
Date: Wed, 28 Feb 2018 03:13:10 +0000 (UTC)

A couple of extra observations.

+Either form of header field name representation is followed by the header field
+value represented as a string literal (see Section 5.2 of [RFC7541]).
+
+
+# Encoding Strategies
+
+## Reference Tracking
+
+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, and might wish to ensure that the decoder will not suffer head-of-line
+blocking when encoding particular references.
+
+In order to enable this, the encoder MUST track outstanding (unacknowledged)
+header blocks and MAY track outstanding table updates.

If you explain why each one is tracked, then you might reach the conclusion - as I did - that 2119 language doesn't make sense here.

The encoder tracks outstanding unacknowledged header blocks so that it can avoid causing evictions that might arrive at the decoder before the entries are needed.  The encoder tracks unacknowledged table updates as well so that it can ensure that it never references a table entry that has not been received by the decoder.

> +## Reference Tracking
+
+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, and might wish to ensure that the decoder will not suffer head-of-line
+blocking when encoding particular references.
+
+In order to enable this, the encoder MUST track outstanding (unacknowledged)
+header blocks and MAY track outstanding table updates.
+
+When the encoder receives feedback from the decoder, 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 number of entries in the table with
+a non-zero reference count is likely to stay quite small.  A data structure

You don't actually need to maintain a reference count, it's only one potential way of doing this (admittedly, a pretty reasonable one).  I'd prefer not to reference (or assume) a particular implementation strategy here.

-- 
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#pullrequestreview-99932204

---

From: Mike Bishop <[email-masked]>
Date: Wed, 28 Feb 2018 16:45:34 +0000 (UTC)

@MikeBishop pushed 6 commits.

7f8adb6  Opcodes without sentinel values
3431c5c  Non-byte-aligned string literals
a0c1a31  Actually use prefix terminology
d4065fd  Martin's feedback
7f495bb  Table size change
f9083c8  Merge pull request #1144 from quicwg/qcram_instructions_opcodes

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

---

From: Mike Bishop <[email-masked]>
Date: Wed, 28 Feb 2018 16:57:45 +0000 (UTC)

8694ad3  Less prescriptive

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

---

From: Mike Bishop <[email-masked]>
Date: Wed, 28 Feb 2018 17:27:58 +0000 (UTC)

29c12b0  No sentinels on request streams either

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

---

From: Mike Bishop <[email-masked]>
Date: Wed, 28 Feb 2018 09:22:12 -0800

Unfortunately, getting rid of the sentinels on request streams isn't as clearly good.

- Indexed representations are unchanged
- Name-Indexed representations now have only four bits for the length, which means you're going to consume an extra byte if the index is 16-31
- Literal representations now only have four bits for the name length, which means you save a byte only if the name is less than 16 octets.  (Though most registered ones are.)

-- 
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#issuecomment-369314128

---

From: Martin Thomson <[email-masked]>
Date: Wed, 28 Feb 2018 22:42:09 +0000 (UTC)

Hmm, this is getting to be pretty large now.  It's a lot of things all wrapped up.  Perhaps now is a good time to reissue a summary of the changes and ask for wider 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#issuecomment-369409340

---

From: Mike Bishop <[email-masked]>
Date: Wed, 28 Feb 2018 23:37:10 +0000 (UTC)

8fba82d  +++

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

---

From: afrind <[email-masked]>
Date: Wed, 28 Feb 2018 21:17:53 -0800

afrind 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
+

You use QPACK here and QCRAM elsewhere. 

+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

I see how we're saving bytes by doing this.  But it may not save that many bytes on the wire, since it's only used when inserting an entry with no matching name, in one case with only a 4 bit prefix.  Given the adoption of QCRAM was driven by similarity to HPACK, I think we should have clear reasons and/or data for divergence.

Or is separating the control stream instruction space already divergent enough that minimizing changes is no longer a goal?

> +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
+string literal" begins with the same Huffman flag, followed by the length
+encoded as an (N-1)-bit prefix integer.  The remainder of the string literal is
+unmodified.
+
+A string literal without a prefix length noted is an 8-bit prefix string literal
+and follows the definitions in [RFC7541] without modification.
+
+## HEADERS Frames on the Control Stream
+
+Table updates can add a table entry, possibly using existing entries to avoid
+transmitting redundant information.  The name can be transmitted as a reference
+to an existing entry in either table or as a string literal. For entries which

...in either the static or dynamic table... might be more clear

+   +---+---+---+---+---+---+---+---+
+   | 0 | 0 | 0 |    Index (5+)     |
+   +---+---+---+-------------------+
+~~~~~~~~~~
+{:#fig-index-with-duplication title="Duplicate"}
+
+The existing entry is re-inserted into the dynamic table without resending
+either the name or the value. This is useful to mitigate the eviction of older
+entries which are frequently referenced, both to avoid the need to resend the
+header and to avoid the entry in the table blocking the ability to insert new
+headers.
+
+### Dynamic Table Size Update
+
+A dynamic table size update signals a change to the size of the dynamic table.

I guess it's implicit that this is the encoder informing the decoder of a change table size, since all of these instructions are in that direction, but mentioning it explicitly might be more clear.

> +| 0 | 0 | 1 |   Max size (5+)   |
++---+---+---+-------------------+
+~~~~~~~~~~
+{:#fig-size-change title="Maximum Dynamic Table Size Change"}
+
+A dynamic table size update starts with the '001' 3-bit pattern, followed by the
+new maximum size, represented as an integer with a 5-bit prefix (see Section
+5.1 of [RFC7541]).
+
+The new maximum size MUST be lower than or equal to the limit determined by the
+protocol using QCRAM.  A value that exceeds this limit MUST be treated as a
+decoding error.  In HTTP/QUIC, this limit is the value of the
+SETTINGS_HEADER_TABLE_SIZE parameter (see [QUIC-HTTP]) received from the
+decoder.
+
+Reducing the maximum size of the dynamic table can cause entries to

Do you need to mention that the encoder cannot reduce the size of the table if it would cause entries with non-zero unacknowledged references to be evicted?

-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

I think booleans per header entry is a holdover from out-of-order QCRAM.  I was tracking this by having the encoder store the max base index acknowledged by the decoder, and a queue of base indexes for each outstanding control-stream HEADERS frame.

> -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 think this little chunk about holding refcounts per header table entry is useful.

-- 
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#pullrequestreview-100312256