Repository: quic-go/quic-go
Pull request #4934 (2025-01-26 13:37:33)

ackhandler: add path probe tracking logic to sent packet history

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/quic-go/quic-go/pull/4934?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go) Report
Attention: Patch coverage is `97.22222%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 83.67%. Comparing base [(`b098a75`)](https://app.codecov.io/gh/quic-go/quic-go/commit/b098a75cf3a05f66725aa265bf19dc851e902e51?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go) to head [(`02a1381`)](https://app.codecov.io/gh/quic-go/quic-go/commit/02a1381543b559e924f4d46817ecc90107918ee5?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go).

| [Files with missing lines](https://app.codecov.io/gh/quic-go/quic-go/pull/4934?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go) | Patch % | Lines |
|---|---|---|
| [internal/ackhandler/sent\_packet\_history.go](https://app.codecov.io/gh/quic-go/quic-go/pull/4934?src=pr&el=tree&filepath=internal%2Fackhandler%2Fsent_packet_history.go&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go#diff-aW50ZXJuYWwvYWNraGFuZGxlci9zZW50X3BhY2tldF9oaXN0b3J5Lmdv) | 97.14% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/quic-go/quic-go/pull/4934?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go) |

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##           master    #4934      +/-   ##
==========================================
- Coverage   83.76%   83.67%   -0.09%     
==========================================
  Files         152      149       -3     
  Lines       16290    15975     -315     
==========================================
- Hits        13644    13366     -278     
+ Misses       2123     2100      -23     
+ Partials      523      509      -14     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/quic-go/quic-go/pull/4934?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=quic-go).


Patch:
diff --git a/internal/ackhandler/packet.go b/internal/ackhandler/packet.go
index 5f43689b..c634939a 100644
--- a/internal/ackhandler/packet.go
+++ b/internal/ackhandler/packet.go
@@ -22,10 +22,11 @@ type packet struct {
 	includedInBytesInFlight bool
 	declaredLost            bool
 	skippedPacket           bool
+	isPathProbePacket       bool
 }
 
 func (p *packet) outstanding() bool {
-	return !p.declaredLost && !p.skippedPacket && !p.IsPathMTUProbePacket
+	return !p.declaredLost && !p.skippedPacket && !p.IsPathMTUProbePacket && !p.isPathProbePacket
 }
 
 var packetPool = sync.Pool{New: func() any { return &packet{} }}
diff --git a/internal/ackhandler/sent_packet_history.go b/internal/ackhandler/sent_packet_history.go
index 27dede15..a608f504 100644
--- a/internal/ackhandler/sent_packet_history.go
+++ b/internal/ackhandler/sent_packet_history.go
@@ -7,7 +7,8 @@ import (
 )
 
 type sentPacketHistory struct {
-	packets []*packet
+	packets          []*packet
+	pathProbePackets []*packet
 
 	numOutstanding int
 
@@ -32,11 +33,11 @@ func (h *sentPacketHistory) checkSequentialPacketNumberUse(pn protocol.PacketNum
 			panic("non-sequential packet number use")
 		}
 	}
+	h.highestPacketNumber = pn
 }
 
 func (h *sentPacketHistory) SkippedPacket(pn protocol.PacketNumber) {
 	h.checkSequentialPacketNumberUse(pn)
-	h.highestPacketNumber = pn
 	h.packets = append(h.packets, &packet{
 		PacketNumber:  pn,
 		skippedPacket: true,
@@ -45,7 +46,6 @@ func (h *sentPacketHistory) SkippedPacket(pn protocol.PacketNumber) {
 
 func (h *sentPacketHistory) SentNonAckElicitingPacket(pn protocol.PacketNumber) {
 	h.checkSequentialPacketNumberUse(pn)
-	h.highestPacketNumber = pn
 	if len(h.packets) > 0 {
 		h.packets = append(h.packets, nil)
 	}
@@ -53,21 +53,37 @@ func (h *sentPacketHistory) SentNonAckElicitingPacket(pn protocol.PacketNumber)
 
 func (h *sentPacketHistory) SentAckElicitingPacket(p *packet) {
 	h.checkSequentialPacketNumberUse(p.PacketNumber)
-	h.highestPacketNumber = p.PacketNumber
 	h.packets = append(h.packets, p)
 	if p.outstanding() {
 		h.numOutstanding++
 	}
 }
 
+func (h *sentPacketHistory) SentPathProbePacket(p *packet) {
+	h.checkSequentialPacketNumberUse(p.PacketNumber)
+	h.packets = append(h.packets, &packet{
+		PacketNumber:      p.PacketNumber,
+		isPathProbePacket: true,
+	})
+	h.pathProbePackets = append(h.pathProbePackets, p)
+}
+
 // Iterate iterates through all packets.
 func (h *sentPacketHistory) Iterate(cb func(*packet) (cont bool)) {
 	for _, p := range h.packets {
 		if p == nil {
 			continue
 		}
-		cont := cb(p)
-		if !cont {
+		if cont := cb(p); !cont {
+			return
+		}
+	}
+}
+
+// IteratePathProbes iterates through all packets.
+func (h *sentPacketHistory) IteratePathProbes(cb func(*packet) (cont bool)) {
+	for _, p := range h.pathProbePackets {
+		if cont := cb(p); !cont {
 			return
 		}
 	}
@@ -86,6 +102,14 @@ func (h *sentPacketHistory) FirstOutstanding() *packet {
 	return nil
 }
 
+// FirstOutstandingPathProbe returns the first outstanding path probe packet
+func (h *sentPacketHistory) FirstOutstandingPathProbe() *packet {
+	if len(h.pathProbePackets) == 0 {
+		return nil
+	}
+	return h.pathProbePackets[0]
+}
+
 func (h *sentPacketHistory) Len() int {
 	return len(h.packets)
 }
@@ -121,6 +145,27 @@ func (h *sentPacketHistory) Remove(pn protocol.PacketNumber) error {
 	return nil
 }
 
+// RemovePathProbe removes a path probe packet.
+// It scales O(N), but that's ok, since we don't expect to send many path probe packets.
+// It is not valid to call this function in IteratePathProbes.
+func (h *sentPacketHistory) RemovePathProbe(pn protocol.PacketNumber) *packet {
+	var packetToDelete *packet
+	idx := -1
+	for i, p := range h.pathProbePackets {
+		if p.PacketNumber == pn {
+			packetToDelete = p
+			idx = i
+			break
+		}
+	}
+	if idx != -1 {
+		// don't use slices.Delete, because it zeros the deleted element
+		copy(h.pathProbePackets[idx:], h.pathProbePackets[idx+1:])
+		h.pathProbePackets = h.pathProbePackets[:len(h.pathProbePackets)-1]
+	}
+	return packetToDelete
+}
+
 // getIndex gets the index of packet p in the packets slice.
 func (h *sentPacketHistory) getIndex(p protocol.PacketNumber) (int, bool) {
 	if len(h.packets) == 0 {
@@ -141,6 +186,10 @@ func (h *sentPacketHistory) HasOutstandingPackets() bool {
 	return h.numOutstanding > 0
 }
 
+func (h *sentPacketHistory) HasOutstandingPathProbes() bool {
+	return len(h.pathProbePackets) > 0
+}
+
 // delete all nil entries at the beginning of the packets slice
 func (h *sentPacketHistory) cleanupStart() {
 	for i, p := range h.packets {


Test patch:
diff --git a/internal/ackhandler/sent_packet_history_test.go b/internal/ackhandler/sent_packet_history_test.go
index c0ef7ce1..06e2d97a 100644
--- a/internal/ackhandler/sent_packet_history_test.go
+++ b/internal/ackhandler/sent_packet_history_test.go
@@ -204,3 +204,95 @@ func TestSentPacketHistoryDeleteWhileIterating(t *testing.T) {
 	require.Equal(t, []protocol.PacketNumber{1, 3, 5}, hist.getPacketNumbers())
 	require.Equal(t, []protocol.PacketNumber{2}, hist.getSkippedPacketNumbers())
 }
+
+func TestSentPacketHistoryPathProbes(t *testing.T) {
+	hist := newSentPacketHistory(true)
+	hist.SentAckElicitingPacket(&packet{PacketNumber: 0})
+	hist.SentAckElicitingPacket(&packet{PacketNumber: 1})
+	hist.SentPathProbePacket(&packet{PacketNumber: 2})
+	hist.SentAckElicitingPacket(&packet{PacketNumber: 3})
+	hist.SentAckElicitingPacket(&packet{PacketNumber: 4})
+	hist.SentPathProbePacket(&packet{PacketNumber: 5})
+
+	getPacketsInHistory := func(t *testing.T) []protocol.PacketNumber {
+		t.Helper()
+		var pns []protocol.PacketNumber
+		hist.Iterate(func(p *packet) bool {
+			pns = append(pns, p.PacketNumber)
+			switch p.PacketNumber {
+			case 2, 5:
+				require.True(t, p.isPathProbePacket)
+			default:
+				require.False(t, p.isPathProbePacket)
+			}
+			return true
+		})
+		return pns
+	}
+
+	getPacketsInPathProbeHistory := func(t *testing.T) []protocol.PacketNumber {
+		t.Helper()
+		var pns []protocol.PacketNumber
+		hist.IteratePathProbes(func(p *packet) bool {
+			pns = append(pns, p.PacketNumber)
+			return true
+		})
+		return pns
+	}
+
+	require.Equal(t, []protocol.PacketNumber{0, 1, 2, 3, 4, 5}, getPacketsInHistory(t))
+	require.Equal(t, []protocol.PacketNumber{2, 5}, getPacketsInPathProbeHistory(t))
+
+	// Removing packets from the regular packet history might happen before the path probe
+	// is declared lost, as the original path might have a smaller RTT than the path timeout.
+	// Therefore, the path probe packet is not removed from the path probe history.
+	require.NoError(t, hist.Remove(0))
+	require.NoError(t, hist.Remove(1))
+	require.NoError(t, hist.Remove(2))
+	require.NoError(t, hist.Remove(3))
+	require.Equal(t, []protocol.PacketNumber{4, 5}, getPacketsInHistory(t))
+	require.Equal(t, []protocol.PacketNumber{2, 5}, getPacketsInPathProbeHistory(t))
+	require.True(t, hist.HasOutstandingPackets())
+	require.True(t, hist.HasOutstandingPathProbes())
+	firstOutstanding := hist.FirstOutstanding()
+	require.NotNil(t, firstOutstanding)
+	require.Equal(t, protocol.PacketNumber(4), firstOutstanding.PacketNumber)
+	firstOutStandingPathProbe := hist.FirstOutstandingPathProbe()
+	require.NotNil(t, firstOutStandingPathProbe)
+	require.Equal(t, protocol.PacketNumber(2), firstOutStandingPathProbe.PacketNumber)
+
+	hist.RemovePathProbe(2)
+	require.Equal(t, []protocol.PacketNumber{4, 5}, getPacketsInHistory(t))
+	require.Equal(t, []protocol.PacketNumber{5}, getPacketsInPathProbeHistory(t))
+	require.True(t, hist.HasOutstandingPathProbes())
+	firstOutStandingPathProbe = hist.FirstOutstandingPathProbe()
+	require.NotNil(t, firstOutStandingPathProbe)
+	require.Equal(t, protocol.PacketNumber(5), firstOutStandingPathProbe.PacketNumber)
+
+	hist.RemovePathProbe(5)
+	require.Equal(t, []protocol.PacketNumber{4, 5}, getPacketsInHistory(t))
+	require.Empty(t, getPacketsInPathProbeHistory(t))
+	require.True(t, hist.HasOutstandingPackets())
+	require.False(t, hist.HasOutstandingPathProbes())
+	require.Nil(t, hist.FirstOutstandingPathProbe())
+
+	require.NoError(t, hist.Remove(4))
+	require.NoError(t, hist.Remove(5))
+	require.Empty(t, getPacketsInHistory(t))
+	require.False(t, hist.HasOutstandingPackets())
+	require.Nil(t, hist.FirstOutstanding())
+
+	// path probe packets are considered outstanding
+	hist.SentPathProbePacket(&packet{PacketNumber: 6})
+	require.False(t, hist.HasOutstandingPackets())
+	require.True(t, hist.HasOutstandingPathProbes())
+	firstOutStandingPathProbe = hist.FirstOutstandingPathProbe()
+	require.NotNil(t, firstOutStandingPathProbe)
+	require.Equal(t, protocol.PacketNumber(6), firstOutStandingPathProbe.PacketNumber)
+
+	hist.RemovePathProbe(6)
+	require.False(t, hist.HasOutstandingPackets())
+	require.Nil(t, hist.FirstOutstanding())
+	require.False(t, hist.HasOutstandingPathProbes())
+	require.Nil(t, hist.FirstOutstandingPathProbe())
+}