Subject: [quicwg/base-drafts] consider making the varint encoding unique (#2299)

From: Marten Seemann <[email-masked]>
Date: Sun, 06 Jan 2019 02:58:54 -0800

Our varint encoding has the unpleasant property that it's possible to encode numbers in multiple ways. This leads to rather clumsy language when it comes to the frame encoding:
> The Frame Type field uses a variable length integer encoding (see Section 16) with one exception. To ensure simple and efficient implementations of frame parsing, a frame type MUST use the shortest possible encoding. Though a two-, four- or eight-byte encoding of the frame types defined in this document is possible, the Frame Type field for these frames is encoded on a single byte.

The easy fix for this is to make the varint encoding unique, such that every number can only be encoded in a single way. This is a very straightforward change from what we have today:
The 1-byte numbers would still encode the values from 0 to 63, but the 2-byte numbers would encode the values between 64 and 16,447 (instead of encoding the range between 0 and 16,383), etc.

While a simplification of the spec is the main advantage of this change, it has the nice property that it slightly increases the encoding efficiency.

-- 
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/issues/2299

---

From: MikkelFJ <[email-masked]>
Date: Sun, 06 Jan 2019 11:04:53 +0000 (UTC)

I have also argued for this in the past, but it breaks down when conservatively allocate to bytes for a length that is unknown. Then you'd have to memmove if the length only require one byte.

-- 
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/issues/2299#issuecomment-451732895

---

From: Marten Seemann <[email-masked]>
Date: Sun, 06 Jan 2019 03:09:41 -0800

Sure. Don't do that! It's definitely possible to use varints everywhere (I have a (roughly) draft-17 compliant implementation, I'm always using the shortest possible varint encoding, and I don't need to memmove anywhere in order to achieve 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/issues/2299#issuecomment-451733146

---

From: ianswett <[email-masked]>
Date: Sun, 06 Jan 2019 05:08:55 -0800

Conceptually this is nice and I think @ekr has mentioned this as well in the past.

But as @mikkelfj said, we'd have to carefully think through whether it causes some packetization headaches in practice.  Thinking through our current gQUIC implementation, I don't think it would cause problems.  I guess one could always add a byte or two of padding if the number was shorter than the reserved length?

This prevents or makes very awkward (for better or worse) picking fixed serialization sizes for specific cases(ie: ack blocks and gaps are always 2 bytes) and writing serialization code that assumes 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/issues/2299#issuecomment-451740417

---

From: Dmitri Tikhonov <[email-masked]>
Date: Sun, 06 Jan 2019 08:02:18 -0800

There are places where the shortest possible encoding is an important property to have, such as frame types. There are also places where it is not important, such as long header's payload length.

Losing the flexibility afforded by allowing fixed-size varints is one way to fix the clumsy language. The other way is to fix the clumsy language.

I suggest we add a definition for the shortest possible varint encoding to [Section 16](https://tools.ietf.org/html/draft-ietf-quic-transport-17#section-16)&mdash;we can call it _minimal_ varint encoding or something of the sort&mdash;and reference it in other parts of the documents as appropriate.

-- 
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/issues/2299#issuecomment-451752836

---

From: Marten Seemann <[email-masked]>
Date: Sun, 06 Jan 2019 08:25:47 -0800

> Losing the flexibility afforded by allowing fixed-size varints is one way to fix the clumsy language. The other way is to fix the clumsy language.

It's not only the language that's clumsy. The fact that we have to make this distinction at all is clumsy.
I see little value in having flexibility where it's not needed, especially if it adds weird corner cases elsewhere. I'm aware that reserving a longer value and filling it in later is a lazy way to implement the varint encoding, but I didn't find it particularly hard to write my code in a way that allows me to always use the optimal encoding.

-- 
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/issues/2299#issuecomment-451754606

---

From: Kazuho Oku <[email-masked]>
Date: Sun, 06 Jan 2019 09:53:45 -0800

I have a mixed feeling about the proposal. Generally speaking, I prefer using a canonical encoding.

OTOH, there are cases that you do not know the length beforehand, and IIRC we have in the past built consensus based on the fact that people can use 2-byte varint for expressing values between 0 to 63.

FWIW, the fields that would be problemsome would be: length field of long header packets, frame lengths of HEADERS and PUSH_PROMISE frames. The lengths are determined after building the contents, and therefore the length of the lengths cannot be predetermined.

-- 
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/issues/2299#issuecomment-451760731

---

From: Nick Banks <[email-masked]>
Date: Sun, 06 Jan 2019 10:13:45 -0800

In WinQuic we have a special function just for encoding a varint explicitly two bytes that we use for the payload length in long headers. It would be **extremely difficult** to update this code to always use the shortest encoding without having to memmove the entire payload after it has been written to the packet buffer.

Looking up at the requirement for shortest possible frame type, I don't understand why that's even necessary to require this. Obviously it's more efficient on the wire, but as far as implementation processing efficiency goes, it would make little difference in the grand scheme of things (a majority of all CPU will be spent in encryption/decryption). So, we can recommend the shortest encoding, but I don't think we should kill the connection if a particular implementation does always use that.

I'd prefer to leave the varint as is and remove any requirements for a particular encoding length.

-- 
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/issues/2299#issuecomment-451762140

---

From: MikkelFJ <[email-masked]>
Date: Sun, 06 Jan 2019 11:40:55 -0800

> Looking up at the requirement for shortest possible frame type, I don't understand why that's even necessary to require this. 

This is because it allows for efficient switch constructs when decoding the frames. This avoids additional complexity during decode. There is difference between enumerations such as frame types, and length values. Enumerations should be uniquely encoded whereas it could be argued that lengths need not due to the memmov issue.

I'm not sure that vast overhead goes to decryption because this is typically 3 cycles per byte so you could easily double the time overhead if you have many small frames that are processed inefficiently.

-- 
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/issues/2299#issuecomment-451768597

---

From: ianswett <[email-masked]>
Date: Sun, 06 Jan 2019 11:43:37 -0800

Good point on long header packets.  I think we should consider changing the long header length to 2 byte lengths if we did this.

Given this is introducing churn and I'm not clear it's adding a lot of value, I'd say we shouldn't do this at the moment.

-- 
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/issues/2299#issuecomment-451768799

---

From: MikkelFJ <[email-masked]>
Date: Sun, 06 Jan 2019 11:48:25 -0800

@ianswett I was almost about to propose the same thing. This would make all encodings canonical - I think there is value in that. The reason I hesitated is that perhaps there are cases where 1 byte lengths makes a difference even if lazy implementations use 2 bytes.

I think ACK block count were not mentioned in this discussion. This is the most important case I can think of.

-- 
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/issues/2299#issuecomment-451769122

---

From: Martin Thomson <[email-masked]>
Date: Sun, 06 Jan 2019 16:02:45 -0800

I'm pretty sure that this was a case where @ekr said that a canonical encoding would be silly.  That's certainly my view.

I believe that this would be a fairly significant hit both in terms of code complexity and performance.  If you think that you can make the case, I think we might start with a PR [here](https://github.com/martinthomson/quic-int) to show that a) the code is simple enough, and b) the performance is tolerable.  Then there is the point about churn.

The requirement on minimal encodings for frame types exists so that a frame decoder can be more efficient, as @mikkelfj says.  I'm reluctant to add that requirement in too many places though (even in the h3 cases we are currently considering).

-- 
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/issues/2299#issuecomment-451788047

---

From: janaiyengar <[email-masked]>
Date: Mon, 07 Jan 2019 17:43:03 -0800

I think we should leave this as it is, primarily for the reason that this is an unnecessary constraint.  The efficiency argument isn't strong for non-frame use cases, and the loss of flexibility can be an issue. @larseggert might have trouble with forcing packet lengths to be minimally represented, for the same reason as @nibanks.

On changing the long header packet size to 2 bytes, we discussed in #1577 and decided against 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/issues/2299#issuecomment-452144881

---

From: Martin Thomson <[email-masked]>
Date: Mon, 07 Jan 2019 21:20:01 -0800

I'm seeing fair support for closing with no action, but I'm happy to leave this until we meet in Tokyo.  Does anyone want to add anything?  I'll close if there is no new information or argument.

-- 
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/issues/2299#issuecomment-452178980

---

From: Subodh Iyengar <[email-masked]>
Date: Wed, 09 Jan 2019 09:43:43 -0800

I've mentioned this previously that this might be good to do, but I also have mixed feelings now because of the reasons @nibanks mentioned about pre-reserving the length. It would seem nasty to work around 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/issues/2299#issuecomment-452784862

---

From: ianswett <[email-masked]>
Date: Thu, 10 Jan 2019 12:40:22 -0800

I'd rather close this with no action at this point.  I can't see us getting to consensus to do this in v1.

-- 
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/issues/2299#issuecomment-453245429

---

From: Lars Eggert <[email-masked]>
Date: Tue, 15 Jan 2019 22:54:00 -0800

I'm OK with closing, but it is *not* difficult to know how long a packet number will need to be, and to leave space for it.
```
   The sender MUST use a packet number size able to represent more than
   twice as large a range than the difference between the largest
   acknowledged packet and packet number being sent.
```

-- 
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/issues/2299#issuecomment-454672073

---

From: MikkelFJ <[email-masked]>
Date: Wed, 16 Jan 2019 01:03:04 -0800

@larseggert The problem is with formatting ACK frames in-place.

-- 
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/issues/2299#issuecomment-454703272

---

From: Lars Eggert <[email-masked]>
Date: Wed, 16 Jan 2019 01:48:51 -0800

Depends on your data structures. My ACKing code doesn't have this issue.

-- 
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/issues/2299#issuecomment-454717219

---

From: ianswett <[email-masked]>
Date: Wed, 16 Jan 2019 07:50:21 -0800

I think long header packets are the largest issue I'm aware of as @nibanks pointed out above.

ACK frames are a bit annoying, but 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/issues/2299#issuecomment-454828853

---

From: Lars Eggert <[email-masked]>
Date: Wed, 16 Jan 2019 09:33:32 -0800

Well, as I said, I'm not objecting to closing this now

-- 
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/issues/2299#issuecomment-454868732

---

From: Marten Seemann <[email-masked]>
Date: Wed, 16 Jan 2019 18:20:03 -0800

Not feeling strongly about this issue, but for how many implementations would this change actually be difficult to implement? So far, the only definitive statement was about WinQuic. Does this apply to other implementations as well, or is this something that's limited to one implementation?

-- 
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/issues/2299#issuecomment-455017560

---

From: ianswett <[email-masked]>
Date: Wed, 16 Jan 2019 18:21:56 -0800

I believe @DavidSchinazi indicated it'd be more difficult in our coalesced packets implementation, but I'll let him confirm.

-- 
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/issues/2299#issuecomment-455017904

---

From: Martin Thomson <[email-masked]>
Date: Wed, 16 Jan 2019 18:27:48 -0800

At this stage, I think that one objection is sufficient.  The advantage of a minimal encoding is in wire efficiency.  Something that can be achieved with the current scheme, and not guaranteed with the proposed one (because there are ample ways in which to suboptimally encode packets, PADDING notwithstanding).

Add the unproven performance characteristics, and I'm not seeing much incentive to change anything.

-- 
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/issues/2299#issuecomment-455018996

---

From: MikkelFJ <[email-masked]>
Date: Wed, 16 Jan 2019 23:45:50 -0800

I don't disagree. But I'd like to add that non-canonical form should only apply to lengths, not enumerations such as frame headers or error codes, as a general principle. The latter can be inconvenient to process if not predictable and have no benefit of being written non-canonical (other than being robust against implementation mistakes).

-- 
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/issues/2299#issuecomment-455073611

---

From: David Schinazi <[email-masked]>
Date: Thu, 17 Jan 2019 12:00:38 -0800

@ianswett yes it would make the code slightly more complicated on the send path for long headers, but not insurmountable. I don't feel too strongly either way about this one.

-- 
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/issues/2299#issuecomment-455311967

---

From: MikkelFJ <[email-masked]>
Date: Thu, 17 Jan 2019 20:23:57 +0000 (UTC)

Honestly, if it is _only_ about long headers length field, then by all means make it canonical. There are so few of those packages, and memmove is relatively cheap, especially compared to the handshake. Furthermore, you can special case those packets to start at an offset and move the preceding data down, or even write them after the length. Typically you can even with benefit use a vectored write with a separate buffer for the header. And for higher level languages that care less about performance, you can just concatenate two buffers.

If it were post handshake with lots of data it would be different. This hangs on ACK's being easy to generate with known lengths.

-- 
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/issues/2299#issuecomment-455319128

---

From: MikkelFJ <[email-masked]>
Date: Thu, 17 Jan 2019 12:33:28 -0800

A canonical length means you use memcmp and hash keys directly, for example for the token length + token.

-- 
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/issues/2299#issuecomment-455321159

---

From: janaiyengar <[email-masked]>
Date: Thu, 17 Jan 2019 13:07:35 -0800

I'm disinclined to pull for a change that doesn't have strong proponents. @nibanks seems to have a strong reservation against this change. On balance, I'm supportive of closing this issue.

-- 
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/issues/2299#issuecomment-455332264

---

From: Nick Banks <[email-masked]>
Date: Thu, 17 Jan 2019 22:05:28 +0000 (UTC)

Yeah, I'd prefer not to take a change for this, at this 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/issues/2299#issuecomment-455349338

---

From: David Schinazi <[email-masked]>
Date: Thu, 17 Jan 2019 22:10:46 +0000 (UTC)

(somehow I accidentally deleted my earlier comment, so I'm reposting it)

@ianswett This would add complexity to our long header write path, but it wouldn't be insurmountable. I personally don't have a strong opinion on this change either way.

-- 
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/issues/2299#issuecomment-455350870

---

From: Christian Huitema <[email-masked]>
Date: Sat, 19 Jan 2019 17:05:50 -0800

I would rather leave the spec as is. There are places where short encoding is natural, but there are also many place in picoquic in which the code reserves two bytes, encode an element, find the coded length, and then update the length. Yes there are workarounds but as many said, please keep the rules flexible.

-- 
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/issues/2299#issuecomment-455828497

---

From: Martin Thomson <[email-masked]>
Date: Wed, 30 Jan 2019 16:38:37 -0800

@marten-seemann is happy closing this.  We will not enforce minimum-length encoding.

-- 
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/issues/2299#issuecomment-459168427

---

From: Martin Thomson <[email-masked]>
Date: Wed, 30 Jan 2019 16:38:38 -0800

Closed #2299.

-- 
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/issues/2299#event-2108123190