Subject: Re: [quicwg/base-drafts] Clarify QPACK eviction races (#1237)

From: Martin Thomson <[email-masked]>
Date: Tue, 04 Sep 2018 23:27:31 -0700

martinthomson approved this pull request.

I have tried to be very specific in my suggestions, but feel free to take or leave.

> -entry remains unacknowledged.  If a new header to be inserted into the dynamic
-table would cause the eviction of such an entry, the encoder MUST NOT emit the
-insert instruction until the reference has been processed by the decoder and
-acknowledged.
-
-The encoder can emit a literal representation for the new header in order to
-avoid encoding delays, and MAY insert the header into the table later if
-desired.
-
-To ensure that the blocked eviction case is rare, references to the oldest
-entries in the dynamic table SHOULD be avoided.  When one of the oldest entries
-in the table is still actively used for references, the encoder SHOULD emit an
-Duplicate representation instead (see {{duplicate}}).
+The encoder MUST NOT emit an instruction that evicts an entry while a reference
+to that entry remains unacknowledged.  When the encoder encounters a blocked
+eviction, it emits a literal representation for the new header, and MAY insert

"When the encoder encounters a blocked eviction, ..." involves a logical leap, or an assumption about the structure of encoders that hasn't been explained.  We all assume that encoders emit new table modifications as the result of processing header blocks, but that isn't necessary.

Perhaps: "An encoder MUST NOT insert an entry into the dynamic table (or duplicate an existing entry) if that would cause an entry with unacknowledged references to be evicted.  For header blocks that might rely on the newly added entry, the encoder can use a literal representation and maybe insert the entry later."

> @@ -871,21 +871,38 @@ the decoder.
 
 ### Blocked Eviction

The title here might be better as "Blocked Dynamic Table Insertions".  Evictions don't get blocked, they are the immovable object here.  It's more the case that insertions are what get blocked.

> -acknowledged.
-
-The encoder can emit a literal representation for the new header in order to
-avoid encoding delays, and MAY insert the header into the table later if
-desired.
-
-To ensure that the blocked eviction case is rare, references to the oldest
-entries in the dynamic table SHOULD be avoided.  When one of the oldest entries
-in the table is still actively used for references, the encoder SHOULD emit an
-Duplicate representation instead (see {{duplicate}}).
+The encoder MUST NOT emit an instruction that evicts an entry while a reference
+to that entry remains unacknowledged.  When the encoder encounters a blocked
+eviction, it emits a literal representation for the new header, and MAY insert
+the header into the table later if desired.
+
+To ensure that blocked evictions are rare, the encoder SHOULD avoid referencing

"To ensure that the encoder is not prevented from adding new entries, the encoder can avoid referencing entries that are near the point at which they would be evicted.  Rather than ..."

+~~~~~~~~~~  drawing
+   +----------+---------------------------------+--------+
+   | Draining |          Referenceable          | Unused |
+   | Entries  |             Entries             | Space  |
+   +----------+---------------------------------+--------+
+   ^          ^                                 ^
+   |          |                                 |
+ Drop Point  Draining Index               Base Index /
+                                          Insertion Point
+~~~~~~~~~~
+{:#fig-eviction-prone title="Encoder's View of Dynamic Table with
+draining index"}

This has to be a single line.  Also, check whether You Want Title Case or Sentence case.  I think that we use Title Case elsewhere.

> +the header into the table later if desired.
+
+To ensure that blocked evictions are rare, the encoder SHOULD avoid referencing
+older entries that will be evicted soon.  Rather than reference such an entry,
+the encoder SHOULD emit a Duplicate instruction (see {{duplicate}}), and
+reference the duplicate instead.
+
+Determining which entries are too close to eviction to reference is an encoder
+preference.  One heuristic is to target a fixed amount of available space in the
+dynamic table: either unused space or space that can be reclaimed by evicting
+unreferenced entries.  To achieve this, the encoder can maintain a draining
+index, which is the smallest absolute index in the dynamic table that it will
+emit a reference for.  As new entries are inserted, the encoder increments the
+draining index such that the amount of unused space and space occupied by
+draining entries table is larger than its target threshold.  Draining entries
+will eventually become evictable as any references to them are acknowledged.

"As new entries are inserted, the encoder increases the draining index to maintain the section of the table that it will not reference.  Draining entries - entries with an absolute index lower than this the draining index - will not accumulate new references.  The number of unacknowledged references to draining entries will eventually become zero, making the entry available for eviction."

-- 
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/1237#pullrequestreview-152347354

---

From: Martin Thomson <[email-masked]>
Date: Wed, 12 Sep 2018 13:56:49 -0700

-- 
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/1237#pullrequestreview-154840354

---

From: afrind <[email-masked]>
Date: Wed, 12 Sep 2018 15:57:11 -0700

Merged #1237 into master.

-- 
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/1237#event-1842369848