quic: add a data structure for tracking lists of sent packets
Store in-flight packets in a ring buffer.
For golang/go#58547
Change-Id: I825c4e600bb496c2f8f6c195085aaae3e847445e
Reviewed-on: https://go-review.googlesource.com/c/net/+/499285
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Jonathan Amsterdam <jba@google.com>
Run-TryBot: Damien Neil <dneil@google.com>
diff --git a/internal/quic/sent_packet_list.go b/internal/quic/sent_packet_list.go
new file mode 100644
index 0000000..6fb712a
--- /dev/null
+++ b/internal/quic/sent_packet_list.go
@@ -0,0 +1,95 @@
+// 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
+
+// A sentPacketList is a ring buffer of sentPackets.
+//
+// Processing an ack for a packet causes all older packets past a small threshold
+// to be discarded (RFC 9002, Section 6.1.1), so the list of in-flight packets is
+// not sparse and will contain at most a few acked/lost packets we no longer
+// care about.
+type sentPacketList struct {
+ nextNum packetNumber // next packet number to add to the buffer
+ off int // offset of first packet in the buffer
+ size int // number of packets
+ p []*sentPacket
+}
+
+// start is the first packet in the list.
+func (s *sentPacketList) start() packetNumber {
+ return s.nextNum - packetNumber(s.size)
+}
+
+// end is one after the last packet in the list.
+// If the list is empty, start == end.
+func (s *sentPacketList) end() packetNumber {
+ return s.nextNum
+}
+
+// discard clears the list.
+func (s *sentPacketList) discard() {
+ *s = sentPacketList{}
+}
+
+// add appends a packet to the list.
+func (s *sentPacketList) add(sent *sentPacket) {
+ if s.nextNum != sent.num {
+ panic("inserting out-of-order packet")
+ }
+ s.nextNum++
+ if s.size >= len(s.p) {
+ s.grow()
+ }
+ i := (s.off + s.size) % len(s.p)
+ s.size++
+ s.p[i] = sent
+}
+
+// nth returns a packet by index.
+func (s *sentPacketList) nth(n int) *sentPacket {
+ index := (s.off + n) % len(s.p)
+ return s.p[index]
+}
+
+// num returns a packet by number.
+// It returns nil if the packet is not in the list.
+func (s *sentPacketList) num(num packetNumber) *sentPacket {
+ i := int(num - s.start())
+ if i < 0 || i >= s.size {
+ return nil
+ }
+ return s.nth(i)
+}
+
+// clean removes all acked or lost packets from the head of the list.
+func (s *sentPacketList) clean() {
+ for s.size > 0 {
+ sent := s.p[s.off]
+ if !sent.acked && !sent.lost {
+ return
+ }
+ sent.recycle()
+ s.p[s.off] = nil
+ s.off = (s.off + 1) % len(s.p)
+ s.size--
+ }
+ s.off = 0
+}
+
+// grow increases the buffer to hold more packaets.
+func (s *sentPacketList) grow() {
+ newSize := len(s.p) * 2
+ if newSize == 0 {
+ newSize = 64
+ }
+ p := make([]*sentPacket, newSize)
+ for i := 0; i < s.size; i++ {
+ p[i] = s.nth(i)
+ }
+ s.p = p
+ s.off = 0
+}
diff --git a/internal/quic/sent_packet_list_test.go b/internal/quic/sent_packet_list_test.go
new file mode 100644
index 0000000..2f7f4d2
--- /dev/null
+++ b/internal/quic/sent_packet_list_test.go
@@ -0,0 +1,107 @@
+// 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"
+
+func TestSentPacketListSlidingWindow(t *testing.T) {
+ // Record 1000 sent packets, acking everything outside the most recent 10.
+ list := &sentPacketList{}
+ const window = 10
+ for i := packetNumber(0); i < 1000; i++ {
+ list.add(&sentPacket{num: i})
+ if i < window {
+ continue
+ }
+ prev := i - window
+ sent := list.num(prev)
+ if sent == nil {
+ t.Fatalf("packet %v not in list", prev)
+ }
+ if sent.num != prev {
+ t.Fatalf("list.num(%v) = packet %v", prev, sent.num)
+ }
+ if got := list.nth(0); got != sent {
+ t.Fatalf("list.nth(0) != list.num(%v)", prev)
+ }
+ sent.acked = true
+ list.clean()
+ if got := list.num(prev); got != nil {
+ t.Fatalf("list.num(%v) = packet %v, expected it to be discarded", prev, got.num)
+ }
+ if got, want := list.start(), prev+1; got != want {
+ t.Fatalf("list.start() = %v, want %v", got, want)
+ }
+ if got, want := list.end(), i+1; got != want {
+ t.Fatalf("list.end() = %v, want %v", got, want)
+ }
+ if got, want := list.size, window; got != want {
+ t.Fatalf("list.size = %v, want %v", got, want)
+ }
+ }
+}
+
+func TestSentPacketListGrows(t *testing.T) {
+ // Record 1000 sent packets.
+ list := &sentPacketList{}
+ const count = 1000
+ for i := packetNumber(0); i < count; i++ {
+ list.add(&sentPacket{num: i})
+ }
+ if got, want := list.start(), packetNumber(0); got != want {
+ t.Fatalf("list.start() = %v, want %v", got, want)
+ }
+ if got, want := list.end(), packetNumber(count); got != want {
+ t.Fatalf("list.end() = %v, want %v", got, want)
+ }
+ if got, want := list.size, count; got != want {
+ t.Fatalf("list.size = %v, want %v", got, want)
+ }
+ for i := packetNumber(0); i < count; i++ {
+ sent := list.num(i)
+ if sent == nil {
+ t.Fatalf("packet %v not in list", i)
+ }
+ if sent.num != i {
+ t.Fatalf("list.num(%v) = packet %v", i, sent.num)
+ }
+ if got := list.nth(int(i)); got != sent {
+ t.Fatalf("list.nth(%v) != list.num(%v)", int(i), i)
+ }
+ }
+}
+
+func TestSentPacketListCleanAll(t *testing.T) {
+ list := &sentPacketList{}
+ // Record 10 sent packets.
+ const count = 10
+ for i := packetNumber(0); i < count; i++ {
+ list.add(&sentPacket{num: i})
+ }
+ // Mark all the packets as acked.
+ for i := packetNumber(0); i < count; i++ {
+ list.num(i).acked = true
+ }
+ list.clean()
+ if got, want := list.size, 0; got != want {
+ t.Fatalf("list.size = %v, want %v", got, want)
+ }
+ list.add(&sentPacket{num: 10})
+ if got, want := list.size, 1; got != want {
+ t.Fatalf("list.size = %v, want %v", got, want)
+ }
+ sent := list.num(10)
+ if sent == nil {
+ t.Fatalf("packet %v not in list", 10)
+ }
+ if sent.num != 10 {
+ t.Fatalf("list.num(10) = %v", sent.num)
+ }
+ if got := list.nth(0); got != sent {
+ t.Fatalf("list.nth(0) != list.num(10)")
+ }
+}
