Subject: [quicwg/base-drafts] lost_pn can no longer be negative (#2621)

From: ianswett <[email-masked]>
Date: Mon, 15 Apr 2019 08:38:34 -0700

And 0 is a valid packet number, so defaulting largest_acked_packet to 0 is inherently incorrect.

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

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

-- Commit Summary --

  * lost_pn can no longer be negative

-- File Changes --

    M draft-ietf-quic-recovery.md (5)

-- Patch Links --

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

---

From: Marten Seemann <[email-masked]>
Date: Mon, 15 Apr 2019 08:40:47 -0700

marten-seemann requested changes on this pull request.

You'll also have to change the first line of `OnAckReceived(ack, pn_space)`.

I'm wondering if it wouldn't be easier to initialize it to -1 instead.

-- 
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/2621#pullrequestreview-226726973

---

From: ianswett <[email-masked]>
Date: Mon, 15 Apr 2019 08:43:09 -0700

@ianswett pushed 1 commit.

3f82654290ca90a0ad1f5c7914942d573485bc3b  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2621/files/b84d5cba6993fc8158d14df876ba12ca14ec7312..3f82654290ca90a0ad1f5c7914942d573485bc3b

---

From: ianswett <[email-masked]>
Date: Mon, 15 Apr 2019 08:46:51 -0700

I prefer to initialize to -1, but previously some people were really opposed to allowing packet numbers and other variables in this pseudocode be signed.

If variables are signed, then we don't really need to do anything here, but it would be more correct to initialize largest_acked_packet[pn_space] to -1.

-- 
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/2621#issuecomment-483308056

---

From: Marten Seemann <[email-masked]>
Date: Mon, 15 Apr 2019 08:59:31 -0700

I'd still prefer -1. We're now adding two `if`s just to catch the special case of `infinite` (which is not a valid unsigned value anyway).

-- 
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/2621#issuecomment-483313136

---

From: ianswett <[email-masked]>
Date: Mon, 15 Apr 2019 09:36:06 -0700

@marten-seemann take a look at #2623 

-- 
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/2621#issuecomment-483326609

---

From: Jana Iyengar <[email-masked]>
Date: Mon, 15 Apr 2019 14:01:06 -0700

janaiyengar commented on this pull request.

This also doesn't solve the problem where:
```lost_pn = largest_acked_packet[pn_space] - kPacketThreshold```
results in a negative `lost_pn`.  My suggestions would be:
1. Initialize lost_pn to infinite
2. When setting `lost_pn`, use the following code:
```
if largest_acked_packet[pn_space] >= kPacketThreshold:
    lost_pn_threshold = largest_acked_packet[pn_space] - kPacketThreshold
```
3. Change the condition below on line 1279 to:
```
(lost_pn != infinite && unacked.packet_number <= lost_pn)
```

> @@ -1273,7 +1276,8 @@ DetectLostPackets(pn_space):
 
     // Mark packet as lost, or set time when it should be marked.
     if (unacked.time_sent <= lost_send_time ||
-        unacked.packet_number <= lost_pn):
+        (largest_acked_packet[pn_space] != infinite &&

DetectLostPackets is only ever called after at least one ACK has been received for this pn_space, so instead of checking for this here, I think this should be an assert() up at the top of the function.

-- 
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/2621#pullrequestreview-226874189

---

From: ianswett <[email-masked]>
Date: Mon, 15 Apr 2019 14:39:12 -0700

I'll note that infinite is not a valid unsigned integer either, so I'm increasingly not in love with the complexity this causes vs just using signed integers.  QUIC only supports 62 bit ints on the wire, so signed integers are not an implementation burden.

-- 
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/2621#issuecomment-483428908

---

From: Jana Iyengar <[email-masked]>
Date: Mon, 15 Apr 2019 16:56:28 -0700

@ianswett: UINT64_MAX is commonly used as infinite. FWIW, I don't think it's a lot of complexity. Implementations have to handle special case conditions (such as initial state) anyways, and writing it down doesn't make implementations more complex.

Good point about 62 bits, but I'm generally wary of implementing PN as a signed int. You'd have to check for < 0 in all sorts of places then.

-- 
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/2621#issuecomment-483460528

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 15 Apr 2019 17:17:29 -0700

> Good point about 62 bits, but I'm generally wary of implementing PN as a signed int. You'd have to check for < 0 in all sorts of places then.

Yeah, we do not need to check < 0 for things we receive, because the encodings don't allow you to transfer negative numbers. So I think use of -1 does not introduce complexity.

-- 
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/2621#issuecomment-483464639

---

From: MikkelFJ <[email-masked]>
Date: Mon, 15 Apr 2019 21:53:05 -0700

I’m not following closely but in C signed integers are undefined for operations modulo their size. I.e. overflow leads to random results, and this is not theoretical - optimizers take advantage.

-- 
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/2621#issuecomment-483510369

---

From: ianswett <[email-masked]>
Date: Tue, 16 Apr 2019 07:08:26 -0700

Yes, the original issue was about underflow(ie: negative numbers), not overflow.  In practice, even a signed int64 is not going to overflow in any of this pseudocode, because packet numbers are 62 bits.

-- 
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/2621#issuecomment-483675042

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 17 Apr 2019 11:10:38 -0700

I prefer to treat uninitialized values explicitly. If it can be swept under an existing branch is not a feature. I think we should prefer clarity here, and IMO dealing with uninitialized values explicitly is clearer to an implementer.  That said, my opinion here is not strong.  I might be in the rough here -- If others in this discussion think that -1 is clearer, I can certainly live with using -1.

-- 
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/2621#issuecomment-484201785

---

From: MikkelFJ <[email-masked]>
Date: Wed, 17 Apr 2019 12:14:59 -0700

I'm with @janaiyengar - especially if there is no precedence elsewhere.

-- 
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/2621#issuecomment-484224226

---

From: ianswett <[email-masked]>
Date: Wed, 17 Apr 2019 19:26:13 +0000 (UTC)

4a41f2f8dfb30dce304d73a80786cba93bc11d97  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2621/files/3f82654290ca90a0ad1f5c7914942d573485bc3b..4a41f2f8dfb30dce304d73a80786cba93bc11d97

---

From: ianswett <[email-masked]>
Date: Wed, 17 Apr 2019 19:27:06 +0000 (UTC)

2cb16a5cf4e3e2d1e032bcd9faf14d816d135546  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2621/files/4a41f2f8dfb30dce304d73a80786cba93bc11d97..2cb16a5cf4e3e2d1e032bcd9faf14d816d135546

---

From: ianswett <[email-masked]>
Date: Wed, 17 Apr 2019 12:28:20 -0700

12bc3155910e45af37ae1b7bcd4caadbf4a910fc  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2621/files/2cb16a5cf4e3e2d1e032bcd9faf14d816d135546..12bc3155910e45af37ae1b7bcd4caadbf4a910fc

---

From: ianswett <[email-masked]>
Date: Wed, 17 Apr 2019 19:30:10 +0000 (UTC)

I changed the pseudocode to no longer subtract, because the alternatives were becoming overly complex.

-- 
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/2621#issuecomment-484229151

---

From: Jana Iyengar <[email-masked]>
Date: Fri, 19 Apr 2019 12:34:55 -0700

janaiyengar approved this pull request.

I like this. I prefer this fix to the others.

-- 
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/2621#pullrequestreview-228802874

---

From: ianswett <[email-masked]>
Date: Fri, 19 Apr 2019 12:46:34 -0700

I find this new version ok and it fixes the issue, so let's go with 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/2621#issuecomment-484997087

---

From: ianswett <[email-masked]>
Date: Fri, 19 Apr 2019 12:46:41 -0700

Merged #2621 into ianswett-no-crypto-data.

-- 
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/2621#event-2288893927

---

From: Martin Thomson <[email-masked]>
Date: Tue, 23 Apr 2019 20:08:38 -0700

martinthomson commented on this pull request.

> @@ -1076,8 +1076,11 @@ Pseudocode for OnAckReceived and UpdateRtt follow:
 
 ~~~
 OnAckReceived(ack, pn_space):
-  largest_acked_packet[pn_space] =
-      max(largest_acked_packet[pn_space], ack.largest_acked)
+  if (largest_acked_packet[pn_space] == infinite):

Would NaN be better?

-- 
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/2621#pullrequestreview-229882188

---

From: ianswett <[email-masked]>
Date: Tue, 23 Apr 2019 20:10:10 -0700

ianswett commented on this pull request.

 ~~~

Probably yes.  I'll make a PR for 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/2621#discussion_r277941593

---

From: ianswett <[email-masked]>
Date: Tue, 23 Apr 2019 20:17:02 -0700

~~~

I don't know what happened, but somehow this was merged, yet I don't see the relevant changes in the text.  Did another change inadvertently revert this?

-- 
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/2621#discussion_r277942473

---

From: MikkelFJ <[email-masked]>
Date: Tue, 23 Apr 2019 22:53:08 -0700

mikkelfj commented on this pull request.

 ~~~

> Would NaN be better?

I don't think so since NaN != NaN

-- 
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/2621#discussion_r277963423

---

From: MikkelFJ <[email-masked]>
Date: Tue, 23 Apr 2019 22:54:22 -0700

~~~

Oh why we didn't we just reserve 0 for uninitialized ...

-- 
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/2621#discussion_r277963645

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 23 Apr 2019 23:29:50 -0700

kazuho commented on this pull request.

 ~~~

> I don't think so since NaN != NaN

`largest_acked_packet[pn_space] is NaN` (or something similar) would do the trick.

-- 
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/2621#discussion_r277970692

---

From: MikkelFJ <[email-masked]>
Date: Tue, 23 Apr 2019 23:47:33 -0700

~~~

`is_uninitialized(largest_acked_packet[pn_space])`

-- 
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/2621#discussion_r277975331

---

From: ianswett <[email-masked]>
Date: Wed, 24 Apr 2019 08:07:34 -0700

~~~

Due to an error in my use of Github, you can now have this discussion on #2651

-- 
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/2621#discussion_r278174798