quic: tracking of received packets and acks to send
RFC 9000, Section 13.2.
For golang/go#58547
Change-Id: I0aad4c03fabb9087964dc9030bb8777d5159360c
Reviewed-on: https://go-review.googlesource.com/c/net/+/506595
Run-TryBot: Damien Neil <dneil@google.com>
Reviewed-by: Jonathan Amsterdam <jba@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
diff --git a/internal/quic/acks.go b/internal/quic/acks.go
new file mode 100644
index 0000000..ba860ef
--- /dev/null
+++ b/internal/quic/acks.go
@@ -0,0 +1,184 @@
+// Copyright 2023 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+//go:build go1.21
+
+package quic
+
+import (
+ "time"
+)
+
+// ackState tracks packets received from a peer within a number space.
+// It handles packet deduplication (don't process the same packet twice) and
+// determines the timing and content of ACK frames.
+type ackState struct {
+ seen rangeset[packetNumber]
+
+ // The time at which we must send an ACK frame, even if we have no other data to send.
+ nextAck time.Time
+
+ // The time we received the largest-numbered packet in seen.
+ maxRecvTime time.Time
+
+ // The largest-numbered ack-eliciting packet in seen.
+ maxAckEliciting packetNumber
+
+ // The number of ack-eliciting packets in seen that we have not yet acknowledged.
+ unackedAckEliciting int
+}
+
+// shouldProcess reports whether a packet should be handled or discarded.
+func (acks *ackState) shouldProcess(num packetNumber) bool {
+ if packetNumber(acks.seen.min()) > num {
+ // We've discarded the state for this range of packet numbers.
+ // Discard the packet rather than potentially processing a duplicate.
+ // https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.3-5
+ return false
+ }
+ if acks.seen.contains(num) {
+ // Discard duplicate packets.
+ return false
+ }
+ return true
+}
+
+// receive records receipt of a packet.
+func (acks *ackState) receive(now time.Time, space numberSpace, num packetNumber, ackEliciting bool) {
+ if ackEliciting {
+ acks.unackedAckEliciting++
+ if acks.mustAckImmediately(space, num) {
+ acks.nextAck = now
+ } else if acks.nextAck.IsZero() {
+ // This packet does not need to be acknowledged immediately,
+ // but the ack must not be intentionally delayed by more than
+ // the max_ack_delay transport parameter we sent to the peer.
+ //
+ // We always delay acks by the maximum allowed, less the timer
+ // granularity. ("[max_ack_delay] SHOULD include the receiver's
+ // expected delays in alarms firing.")
+ //
+ // https://www.rfc-editor.org/rfc/rfc9000#section-18.2-4.28.1
+ acks.nextAck = now.Add(maxAckDelay - timerGranularity)
+ }
+ if num > acks.maxAckEliciting {
+ acks.maxAckEliciting = num
+ }
+ }
+
+ acks.seen.add(num, num+1)
+ if num == acks.seen.max() {
+ acks.maxRecvTime = now
+ }
+
+ // Limit the total number of ACK ranges by dropping older ranges.
+ //
+ // Remembering more ranges results in larger ACK frames.
+ //
+ // Remembering a large number of ranges could result in ACK frames becoming
+ // too large to fit in a packet, in which case we will silently drop older
+ // ranges during packet construction.
+ //
+ // Remembering fewer ranges can result in unnecessary retransmissions,
+ // since we cannot accept packets older than the oldest remembered range.
+ //
+ // The limit here is completely arbitrary. If it seems wrong, it probably is.
+ //
+ // https://www.rfc-editor.org/rfc/rfc9000#section-13.2.3
+ const maxAckRanges = 8
+ if overflow := acks.seen.numRanges() - maxAckRanges; overflow > 0 {
+ acks.seen.removeranges(0, overflow)
+ }
+}
+
+// mustAckImmediately reports whether an ack-eliciting packet must be acknowledged immediately,
+// or whether the ack may be deferred.
+func (acks *ackState) mustAckImmediately(space numberSpace, num packetNumber) bool {
+ // https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.1
+ if space != appDataSpace {
+ // "[...] all ack-eliciting Initial and Handshake packets [...]"
+ // https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.1-2
+ return true
+ }
+ if num < acks.maxAckEliciting {
+ // "[...] when the received packet has a packet number less than another
+ // ack-eliciting packet that has been received [...]"
+ // https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.1-8.1
+ return true
+ }
+ if acks.seen.rangeContaining(acks.maxAckEliciting).end != num {
+ // "[...] when the packet has a packet number larger than the highest-numbered
+ // ack-eliciting packet that has been received and there are missing packets
+ // between that packet and this packet."
+ // https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.1-8.2
+ //
+ // This case is a bit tricky. Let's say we've received:
+ // 0, ack-eliciting
+ // 1, ack-eliciting
+ // 3, NOT ack eliciting
+ //
+ // We have sent ACKs for 0 and 1. If we receive ack-eliciting packet 2,
+ // we do not need to send an immediate ACK, because there are no missing
+ // packets between it and the highest-numbered ack-eliciting packet (1).
+ // If we receive ack-eliciting packet 4, we do need to send an immediate ACK,
+ // because there's a gap (the missing packet 2).
+ //
+ // We check for this by looking up the ACK range which contains the
+ // highest-numbered ack-eliciting packet: [0, 1) in the above example.
+ // If the range ends just before the packet we are now processing,
+ // there are no gaps. If it does not, there must be a gap.
+ return true
+ }
+ if acks.unackedAckEliciting >= 2 {
+ // "[...] after receiving at least two ack-eliciting packets."
+ // https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.2
+ return true
+ }
+ return false
+}
+
+// shouldSendAck reports whether the connection should send an ACK frame at this time,
+// in an ACK-only packet if necessary.
+func (acks *ackState) shouldSendAck(now time.Time) bool {
+ return !acks.nextAck.IsZero() && !acks.nextAck.After(now)
+}
+
+// acksToSend returns the set of packet numbers to ACK at this time, and the current ack delay.
+// It may return acks even if shouldSendAck returns false, when there are unacked
+// ack-eliciting packets whose ack is being delayed.
+func (acks *ackState) acksToSend(now time.Time) (nums rangeset[packetNumber], ackDelay time.Duration) {
+ if acks.nextAck.IsZero() && acks.unackedAckEliciting == 0 {
+ return nil, 0
+ }
+ // "[...] the delays intentionally introduced between the time the packet with the
+ // largest packet number is received and the time an acknowledgement is sent."
+ // https://www.rfc-editor.org/rfc/rfc9000#section-13.2.5-1
+ delay := now.Sub(acks.maxRecvTime)
+ if delay < 0 {
+ delay = 0
+ }
+ return acks.seen, delay
+}
+
+// sentAck records that an ACK frame has been sent.
+func (acks *ackState) sentAck() {
+ acks.nextAck = time.Time{}
+ acks.unackedAckEliciting = 0
+}
+
+// handleAck records that an ack has been received for a ACK frame we sent
+// containing the given Largest Acknowledged field.
+func (acks *ackState) handleAck(largestAcked packetNumber) {
+ // We can stop acking packets less or equal to largestAcked.
+ // https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.4-1
+ //
+ // We rely on acks.seen containing the largest packet number that has been successfully
+ // processed, so we retain the range containing largestAcked and discard previous ones.
+ acks.seen.sub(0, acks.seen.rangeContaining(largestAcked).start)
+}
+
+// largestSeen reports the largest seen packet.
+func (acks *ackState) largestSeen() packetNumber {
+ return acks.seen.max()
+}
diff --git a/internal/quic/acks_test.go b/internal/quic/acks_test.go
new file mode 100644
index 0000000..4f10329
--- /dev/null
+++ b/internal/quic/acks_test.go
@@ -0,0 +1,248 @@
+// Copyright 2023 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+//go:build go1.21
+
+package quic
+
+import (
+ "testing"
+ "time"
+)
+
+func TestAcksDisallowDuplicate(t *testing.T) {
+ // Don't process a packet that we've seen before.
+ acks := ackState{}
+ now := time.Now()
+ receive := []packetNumber{0, 1, 2, 4, 7, 6, 9}
+ seen := map[packetNumber]bool{}
+ for i, pnum := range receive {
+ acks.receive(now, appDataSpace, pnum, true)
+ seen[pnum] = true
+ for ppnum := packetNumber(0); ppnum < 11; ppnum++ {
+ if got, want := acks.shouldProcess(ppnum), !seen[ppnum]; got != want {
+ t.Fatalf("after receiving %v: acks.shouldProcess(%v) = %v, want %v", receive[:i+1], ppnum, got, want)
+ }
+ }
+ }
+}
+
+func TestAcksDisallowDiscardedAckRanges(t *testing.T) {
+ // Don't process a packet with a number in a discarded range.
+ acks := ackState{}
+ now := time.Now()
+ for pnum := packetNumber(0); ; pnum += 2 {
+ acks.receive(now, appDataSpace, pnum, true)
+ send, _ := acks.acksToSend(now)
+ for ppnum := packetNumber(0); ppnum < packetNumber(send.min()); ppnum++ {
+ if acks.shouldProcess(ppnum) {
+ t.Fatalf("after limiting ack ranges to %v: acks.shouldProcess(%v) (in discarded range) = true, want false", send, ppnum)
+ }
+ }
+ if send.min() > 10 {
+ break
+ }
+ }
+}
+
+func TestAcksSent(t *testing.T) {
+ type packet struct {
+ pnum packetNumber
+ ackEliciting bool
+ }
+ for _, test := range []struct {
+ name string
+ space numberSpace
+
+ // ackedPackets and packets are packets that we receive.
+ // After receiving all packets in ackedPackets, we send an ack.
+ // Then we receive the subsequent packets in packets.
+ ackedPackets []packet
+ packets []packet
+
+ wantDelay time.Duration
+ wantAcks rangeset[packetNumber]
+ }{{
+ name: "no packets to ack",
+ space: initialSpace,
+ }, {
+ name: "non-ack-eliciting packets are not acked",
+ space: initialSpace,
+ packets: []packet{{
+ pnum: 0,
+ ackEliciting: false,
+ }},
+ }, {
+ name: "ack-eliciting Initial packets are acked immediately",
+ space: initialSpace,
+ packets: []packet{{
+ pnum: 0,
+ ackEliciting: true,
+ }},
+ wantAcks: rangeset[packetNumber]{{0, 1}},
+ wantDelay: 0,
+ }, {
+ name: "ack-eliciting Handshake packets are acked immediately",
+ space: handshakeSpace,
+ packets: []packet{{
+ pnum: 0,
+ ackEliciting: true,
+ }},
+ wantAcks: rangeset[packetNumber]{{0, 1}},
+ wantDelay: 0,
+ }, {
+ name: "ack-eliciting AppData packets are acked after max_ack_delay",
+ space: appDataSpace,
+ packets: []packet{{
+ pnum: 0,
+ ackEliciting: true,
+ }},
+ wantAcks: rangeset[packetNumber]{{0, 1}},
+ wantDelay: maxAckDelay - timerGranularity,
+ }, {
+ name: "reordered ack-eliciting packets are acked immediately",
+ space: appDataSpace,
+ ackedPackets: []packet{{
+ pnum: 1,
+ ackEliciting: true,
+ }},
+ packets: []packet{{
+ pnum: 0,
+ ackEliciting: true,
+ }},
+ wantAcks: rangeset[packetNumber]{{0, 2}},
+ wantDelay: 0,
+ }, {
+ name: "gaps in ack-eliciting packets are acked immediately",
+ space: appDataSpace,
+ packets: []packet{{
+ pnum: 1,
+ ackEliciting: true,
+ }},
+ wantAcks: rangeset[packetNumber]{{1, 2}},
+ wantDelay: 0,
+ }, {
+ name: "reordered non-ack-eliciting packets are not acked immediately",
+ space: appDataSpace,
+ ackedPackets: []packet{{
+ pnum: 1,
+ ackEliciting: true,
+ }},
+ packets: []packet{{
+ pnum: 2,
+ ackEliciting: true,
+ }, {
+ pnum: 0,
+ ackEliciting: false,
+ }, {
+ pnum: 4,
+ ackEliciting: false,
+ }},
+ wantAcks: rangeset[packetNumber]{{0, 3}, {4, 5}},
+ wantDelay: maxAckDelay - timerGranularity,
+ }, {
+ name: "immediate ack after two ack-eliciting packets are received",
+ space: appDataSpace,
+ packets: []packet{{
+ pnum: 0,
+ ackEliciting: true,
+ }, {
+ pnum: 1,
+ ackEliciting: true,
+ }},
+ wantAcks: rangeset[packetNumber]{{0, 2}},
+ wantDelay: 0,
+ }} {
+ t.Run(test.name, func(t *testing.T) {
+ acks := ackState{}
+ start := time.Date(2020, 1, 1, 0, 0, 0, 0, time.UTC)
+ for _, p := range test.ackedPackets {
+ t.Logf("receive %v.%v, ack-eliciting=%v", test.space, p.pnum, p.ackEliciting)
+ acks.receive(start, test.space, p.pnum, p.ackEliciting)
+ }
+ t.Logf("send an ACK frame")
+ acks.sentAck()
+ for _, p := range test.packets {
+ t.Logf("receive %v.%v, ack-eliciting=%v", test.space, p.pnum, p.ackEliciting)
+ acks.receive(start, test.space, p.pnum, p.ackEliciting)
+ }
+ switch {
+ case len(test.wantAcks) == 0:
+ // No ACK should be sent, even well after max_ack_delay.
+ if acks.shouldSendAck(start.Add(10 * maxAckDelay)) {
+ t.Errorf("acks.shouldSendAck(T+10*max_ack_delay) = true, want false")
+ }
+ case test.wantDelay > 0:
+ // No ACK should be sent before a delay.
+ if acks.shouldSendAck(start.Add(test.wantDelay - 1)) {
+ t.Errorf("acks.shouldSendAck(T+%v-1ns) = true, want false", test.wantDelay)
+ }
+ fallthrough
+ default:
+ // ACK should be sent after a delay.
+ if !acks.shouldSendAck(start.Add(test.wantDelay)) {
+ t.Errorf("acks.shouldSendAck(T+%v) = false, want true", test.wantDelay)
+ }
+ }
+ // acksToSend always reports the available packets that can be acked,
+ // and the amount of time that has passed since the most recent acked
+ // packet was received.
+ for _, delay := range []time.Duration{
+ 0,
+ test.wantDelay,
+ test.wantDelay + 1,
+ } {
+ gotNums, gotDelay := acks.acksToSend(start.Add(delay))
+ wantDelay := delay
+ if len(gotNums) == 0 {
+ wantDelay = 0
+ }
+ if !slicesEqual(gotNums, test.wantAcks) || gotDelay != wantDelay {
+ t.Errorf("acks.acksToSend(T+%v) = %v, %v; want %v, %v", delay, gotNums, gotDelay, test.wantAcks, wantDelay)
+ }
+ }
+ })
+ }
+}
+
+// slicesEqual reports whether two slices are equal.
+// Replace this with slices.Equal once the module go.mod is go1.17 or newer.
+func slicesEqual[E comparable](s1, s2 []E) bool {
+ if len(s1) != len(s2) {
+ return false
+ }
+ for i := range s1 {
+ if s1[i] != s2[i] {
+ return false
+ }
+ }
+ return true
+}
+
+func TestAcksDiscardAfterAck(t *testing.T) {
+ acks := ackState{}
+ now := time.Now()
+ acks.receive(now, appDataSpace, 0, true)
+ acks.receive(now, appDataSpace, 2, true)
+ acks.receive(now, appDataSpace, 4, true)
+ acks.receive(now, appDataSpace, 5, true)
+ acks.receive(now, appDataSpace, 6, true)
+ acks.handleAck(6) // discards all ranges prior to the one containing packet 6
+ acks.receive(now, appDataSpace, 7, true)
+ got, _ := acks.acksToSend(now)
+ if len(got) != 1 {
+ t.Errorf("acks.acksToSend contains ranges prior to last acknowledged ack; got %v, want 1 range", got)
+ }
+}
+
+func TestAcksLargestSeen(t *testing.T) {
+ acks := ackState{}
+ now := time.Now()
+ acks.receive(now, appDataSpace, 0, true)
+ acks.receive(now, appDataSpace, 4, true)
+ acks.receive(now, appDataSpace, 1, true)
+ if got, want := acks.largestSeen(), packetNumber(4); got != want {
+ t.Errorf("acks.largestSeen() = %v, want %v", got, want)
+ }
+}
diff --git a/internal/quic/rangeset.go b/internal/quic/rangeset.go
index 5339c5a..4966a99 100644
--- a/internal/quic/rangeset.go
+++ b/internal/quic/rangeset.go
@@ -154,6 +154,11 @@
return s[len(s)-1].end
}
+// numRanges returns the number of ranges in the rangeset.
+func (s rangeset[T]) numRanges() int {
+ return len(s)
+}
+
// isrange reports if the rangeset covers exactly the range [start, end).
func (s rangeset[T]) isrange(start, end T) bool {
switch len(s) {
diff --git a/internal/quic/rangeset_test.go b/internal/quic/rangeset_test.go
index 3080469..2027f14 100644
--- a/internal/quic/rangeset_test.go
+++ b/internal/quic/rangeset_test.go
@@ -295,3 +295,23 @@
}
}
}
+
+func TestRangesetNumRanges(t *testing.T) {
+ for _, test := range []struct {
+ s rangeset[int64]
+ want int
+ }{{
+ s: rangeset[int64]{},
+ want: 0,
+ }, {
+ s: rangeset[int64]{{0, 100}},
+ want: 1,
+ }, {
+ s: rangeset[int64]{{0, 100}, {200, 300}},
+ want: 2,
+ }} {
+ if got, want := test.s.numRanges(), test.want; got != want {
+ t.Errorf("%+v.numRanges() = %v, want %v", test.s, got, want)
+ }
+ }
+}
