golang.net/quic/loss_test.go

// 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.

package quic

import (
	"fmt"
	"testing"
	"time"
)

func TestLossAntiAmplificationLimit(t *testing.T) {
	test := newLossTest(t, serverSide, lossTestOpts{})
	test.datagramReceived(1200)
	t.Logf("# consume anti-amplification capacity in a mix of packets")
	test.send(initialSpace, 0, sentPacket{
		size:         1200,
		ackEliciting: true,
		inFlight:     true,
	})
	test.send(initialSpace, 1, sentPacket{
		size:         1200,
		ackEliciting: false,
		inFlight:     false,
	})
	test.send(initialSpace, 2, sentPacket{
		size:         1200,
		ackEliciting: false,
		inFlight:     true,
	})
	t.Logf("# send blocked by anti-amplification limit")
	test.wantSendLimit(ccBlocked)

	t.Logf("# receiving a datagram unblocks server")
	test.datagramReceived(100)
	test.wantSendLimit(ccOK)

	t.Logf("# validating client address removes anti-amplification limit")
	test.validateClientAddress()
	test.wantSendLimit(ccOK)
}

func TestLossRTTSampleNotGenerated(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.send(initialSpace, 0, 1)
	test.send(initialSpace, 2, sentPacket{
		ackEliciting: false,
		inFlight:     false,
	})
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(initialSpace, 1)
	test.wantVar("latest_rtt", 10*time.Millisecond)
	t.Logf("# smoothed_rtt = latest_rtt")
	test.wantVar("smoothed_rtt", 10*time.Millisecond)
	t.Logf("# rttvar = latest_rtt / 2")
	test.wantVar("rttvar", 5*time.Millisecond)

	// "...an ACK frame SHOULD NOT be used to update RTT estimates if
	// it does not newly acknowledge the largest acknowledged packet."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-5.1-6
	t.Logf("# acks for older packets do not generate an RTT sample")
	test.advance(1 * time.Millisecond)
	test.ack(initialSpace, 1*time.Millisecond, i64range[packetNumber]{0, 2})
	test.wantAck(initialSpace, 0)
	test.wantVar("smoothed_rtt", 10*time.Millisecond)

	// "An RTT sample MUST NOT be generated on receiving an ACK frame
	// that does not newly acknowledge at least one ack-eliciting packet."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-5.1-7
	t.Logf("# acks for non-ack-eliciting packets do not generate an RTT sample")
	test.advance(1 * time.Millisecond)
	test.ack(initialSpace, 1*time.Millisecond, i64range[packetNumber]{0, 3})
	test.wantAck(initialSpace, 2)
	test.wantVar("smoothed_rtt", 10*time.Millisecond)
}

func TestLossMinRTT(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})

	// "min_rtt MUST be set to the latest_rtt on the first RTT sample."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-5.2-2
	t.Logf("# min_rtt set on first sample")
	test.send(initialSpace, 0)
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	test.wantVar("min_rtt", 10*time.Millisecond)

	// "min_rtt MUST be set to the lesser of min_rtt and latest_rtt [...]
	// on all other samples."
	t.Logf("# min_rtt does not increase")
	test.send(initialSpace, 1)
	test.advance(20 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 2})
	test.wantAck(initialSpace, 1)
	test.wantVar("min_rtt", 10*time.Millisecond)

	t.Logf("# min_rtt decreases")
	test.send(initialSpace, 2)
	test.advance(5 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 3})
	test.wantAck(initialSpace, 2)
	test.wantVar("min_rtt", 5*time.Millisecond)
}

func TestLossMinRTTAfterCongestion(t *testing.T) {
	// "Endpoints SHOULD set the min_rtt to the newest RTT sample
	// after persistent congestion is established."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-5.2-5
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	t.Logf("# establish initial RTT sample")
	test.send(initialSpace, 0, testSentPacketSize(1200))
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	test.wantVar("min_rtt", 10*time.Millisecond)

	t.Logf("# send two packets spanning persistent congestion duration")
	test.send(initialSpace, 1, testSentPacketSize(1200))
	t.Logf("# 2000ms >> persistent congestion duration")
	test.advance(2000 * time.Millisecond)
	test.wantPTOExpired()
	test.send(initialSpace, 2, testSentPacketSize(1200))

	t.Logf("# trigger loss of previous packets")
	test.advance(10 * time.Millisecond)
	test.send(initialSpace, 3, testSentPacketSize(1200))
	test.advance(20 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{3, 4})
	test.wantAck(initialSpace, 3)
	test.wantLoss(initialSpace, 1, 2)
	t.Logf("# persistent congestion detected")

	test.send(initialSpace, 4, testSentPacketSize(1200))
	test.advance(20 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{4, 5})
	test.wantAck(initialSpace, 4)

	t.Logf("# min_rtt set from first sample after persistent congestion")
	test.wantVar("min_rtt", 20*time.Millisecond)
}

func TestLossInitialRTTSample(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.setMaxAckDelay(2 * time.Millisecond)
	t.Logf("# initial smoothed_rtt and rtt values")
	test.wantVar("smoothed_rtt", 333*time.Millisecond)
	test.wantVar("rttvar", 333*time.Millisecond/2)

	// https://www.rfc-editor.org/rfc/rfc9002.html#section-5.3-11
	t.Logf("# first RTT sample")
	test.send(initialSpace, 0)
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	test.wantVar("latest_rtt", 10*time.Millisecond)
	t.Logf("# smoothed_rtt = latest_rtt")
	test.wantVar("smoothed_rtt", 10*time.Millisecond)
	t.Logf("# rttvar = latest_rtt / 2")
	test.wantVar("rttvar", 5*time.Millisecond)
}

func TestLossSmoothedRTTIgnoresMaxAckDelayBeforeHandshakeConfirmed(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.setMaxAckDelay(1 * time.Millisecond)
	test.send(initialSpace, 0)
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	smoothedRTT := 10 * time.Millisecond
	rttvar := 5 * time.Millisecond

	// "[...] an endpoint [...] SHOULD ignore the peer's max_ack_delay
	// until the handshake is confirmed [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-5.3-7.2
	t.Logf("# subsequent RTT sample")
	test.send(handshakeSpace, 0)
	test.advance(20 * time.Millisecond)
	test.ack(handshakeSpace, 10*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(handshakeSpace, 0)
	test.wantVar("latest_rtt", 20*time.Millisecond)
	t.Logf("# ack_delay > max_ack_delay")
	t.Logf("# handshake not confirmed, so ignore max_ack_delay")
	t.Logf("# adjusted_rtt = latest_rtt - ackDelay")
	adjustedRTT := 10 * time.Millisecond
	t.Logf("# smoothed_rtt = 7/8 * smoothed_rtt + 1/8 * adjusted_rtt")
	smoothedRTT = (7*smoothedRTT + adjustedRTT) / 8
	test.wantVar("smoothed_rtt", smoothedRTT)
	rttvarSample := abs(smoothedRTT - adjustedRTT)
	t.Logf("# rttvar_sample = abs(smoothed_rtt - adjusted_rtt) = %v", rttvarSample)
	t.Logf("# rttvar = 3/4 * rttvar + 1/4 * rttvar_sample")
	rttvar = (3*rttvar + rttvarSample) / 4
	test.wantVar("rttvar", rttvar)
}

func TestLossSmoothedRTTUsesMaxAckDelayAfterHandshakeConfirmed(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.setMaxAckDelay(25 * time.Millisecond)
	test.send(initialSpace, 0)
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	smoothedRTT := 10 * time.Millisecond
	rttvar := 5 * time.Millisecond

	test.confirmHandshake()

	// "[...] an endpoint [...] MUST use the lesser of the acknowledgment
	// delay and the peer's max_ack_delay after the handshake is confirmed [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-5.3-7.3
	t.Logf("# subsequent RTT sample")
	test.send(handshakeSpace, 0)
	test.advance(50 * time.Millisecond)
	test.ack(handshakeSpace, 40*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(handshakeSpace, 0)
	test.wantVar("latest_rtt", 50*time.Millisecond)
	t.Logf("# ack_delay > max_ack_delay")
	t.Logf("# handshake confirmed, so adjusted_rtt clamps to max_ack_delay")
	t.Logf("# adjusted_rtt = max_ack_delay")
	adjustedRTT := 25 * time.Millisecond
	rttvarSample := abs(smoothedRTT - adjustedRTT)
	t.Logf("# rttvar_sample = abs(smoothed_rtt - adjusted_rtt) = %v", rttvarSample)
	t.Logf("# rttvar = 3/4 * rttvar + 1/4 * rttvar_sample")
	rttvar = (3*rttvar + rttvarSample) / 4
	test.wantVar("rttvar", rttvar)
	t.Logf("# smoothed_rtt = 7/8 * smoothed_rtt + 1/8 * adjusted_rtt")
	smoothedRTT = (7*smoothedRTT + adjustedRTT) / 8
	test.wantVar("smoothed_rtt", smoothedRTT)
}

func TestLossAckDelayReducesRTTBelowMinRTT(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.send(initialSpace, 0)
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	smoothedRTT := 10 * time.Millisecond
	rttvar := 5 * time.Millisecond

	// "[...] an endpoint [...] MUST NOT subtract the acknowledgment delay
	// from the RTT sample if the resulting value is smaller than the min_rtt."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-5.3-7.4
	t.Logf("# subsequent RTT sample")
	test.send(handshakeSpace, 0)
	test.advance(12 * time.Millisecond)
	test.ack(handshakeSpace, 4*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(handshakeSpace, 0)
	test.wantVar("latest_rtt", 12*time.Millisecond)
	t.Logf("# latest_rtt - ack_delay < min_rtt, so adjusted_rtt = latest_rtt")
	adjustedRTT := 12 * time.Millisecond
	rttvarSample := abs(smoothedRTT - adjustedRTT)
	t.Logf("# rttvar_sample = abs(smoothed_rtt - adjusted_rtt) = %v", rttvarSample)
	t.Logf("# rttvar = 3/4 * rttvar + 1/4 * rttvar_sample")
	rttvar = (3*rttvar + rttvarSample) / 4
	test.wantVar("rttvar", rttvar)
	t.Logf("# smoothed_rtt = 7/8 * smoothed_rtt + 1/8 * adjusted_rtt")
	smoothedRTT = (7*smoothedRTT + adjustedRTT) / 8
	test.wantVar("smoothed_rtt", smoothedRTT)
}

func TestLossPacketThreshold(t *testing.T) {
	// "[...] the packet was sent kPacketThreshold packets before an
	// acknowledged packet [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1.1
	test := newLossTest(t, clientSide, lossTestOpts{})
	t.Logf("# acking a packet triggers loss of packets sent kPacketThreshold earlier")
	test.send(appDataSpace, 0, 1, 2, 3, 4, 5, 6)
	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{4, 5})
	test.wantAck(appDataSpace, 4)
	test.wantLoss(appDataSpace, 0, 1)
}

func TestLossOutOfOrderAcks(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})
	t.Logf("# out of order acks, no loss")
	test.send(appDataSpace, 0, 1, 2)
	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{2, 3})
	test.wantAck(appDataSpace, 2)

	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(appDataSpace, 1)

	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(appDataSpace, 0)
}

func TestLossSendAndAck(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.send(appDataSpace, 0, 1, 2)
	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{0, 3})
	test.wantAck(appDataSpace, 0, 1, 2)
	// Redundant ACK doesn't trigger more ACK events.
	// (If we did get an extra ACK, the test cleanup would notice and complain.)
	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{0, 3})
}

func TestLossAckEveryOtherPacket(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.send(appDataSpace, 0, 1, 2, 3, 4, 5, 6)
	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(appDataSpace, 0)

	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{2, 3})
	test.wantAck(appDataSpace, 2)

	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{4, 5})
	test.wantAck(appDataSpace, 4)
	test.wantLoss(appDataSpace, 1)

	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{6, 7})
	test.wantAck(appDataSpace, 6)
	test.wantLoss(appDataSpace, 3)
}

func TestLossMultipleSpaces(t *testing.T) {
	// "Loss detection is separate per packet number space [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6-3
	test := newLossTest(t, clientSide, lossTestOpts{})
	t.Logf("# send packets in different spaces")
	test.send(initialSpace, 0, 1, 2)
	test.send(handshakeSpace, 0, 1, 2)
	test.send(appDataSpace, 0, 1, 2)

	t.Logf("# ack one packet in each space")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(initialSpace, 1)

	test.ack(handshakeSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(handshakeSpace, 1)

	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(appDataSpace, 1)

	t.Logf("# send more packets")
	test.send(initialSpace, 3, 4, 5)
	test.send(handshakeSpace, 3, 4, 5)
	test.send(appDataSpace, 3, 4, 5)

	t.Logf("# ack the last packet, triggering loss")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{5, 6})
	test.wantAck(initialSpace, 5)
	test.wantLoss(initialSpace, 0, 2)

	test.ack(handshakeSpace, 0*time.Millisecond, i64range[packetNumber]{5, 6})
	test.wantAck(handshakeSpace, 5)
	test.wantLoss(handshakeSpace, 0, 2)

	test.ack(appDataSpace, 0*time.Millisecond, i64range[packetNumber]{5, 6})
	test.wantAck(appDataSpace, 5)
	test.wantLoss(appDataSpace, 0, 2)
}

func TestLossTimeThresholdFirstPacketLost(t *testing.T) {
	// "[...] the packet [...] was sent long enough in the past."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1-3.2
	test := newLossTest(t, clientSide, lossTestOpts{})
	t.Logf("# packet 0 lost after time threshold passes")
	test.send(initialSpace, 0, 1)
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(initialSpace, 1)

	t.Logf("# latest_rtt == smoothed_rtt")
	test.wantVar("smoothed_rtt", 10*time.Millisecond)
	test.wantVar("latest_rtt", 10*time.Millisecond)
	t.Logf("# timeout = 9/8 * max(smoothed_rtt, latest_rtt) - time_since_packet_sent")
	test.wantTimeout(((10 * time.Millisecond * 9) / 8) - 10*time.Millisecond)

	test.advanceToLossTimer()
	test.wantLoss(initialSpace, 0)
}

func TestLossTimeThreshold(t *testing.T) {
	// "The time threshold is:
	// max(kTimeThreshold * max(smoothed_rtt, latest_rtt), kGranularity)"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1.2-2
	for _, tc := range []struct {
		name        string
		initialRTT  time.Duration
		latestRTT   time.Duration
		wantTimeout time.Duration
	}{{
		name:        "rtt increasing",
		initialRTT:  10 * time.Millisecond,
		latestRTT:   20 * time.Millisecond,
		wantTimeout: 20 * time.Millisecond * 9 / 8,
	}, {
		name:        "rtt decreasing",
		initialRTT:  10 * time.Millisecond,
		latestRTT:   5 * time.Millisecond,
		wantTimeout: ((7*10*time.Millisecond + 5*time.Millisecond) / 8) * 9 / 8,
	}, {
		name:        "rtt less than timer granularity",
		initialRTT:  500 * time.Microsecond,
		latestRTT:   500 * time.Microsecond,
		wantTimeout: 1 * time.Millisecond,
	}} {
		t.Run(tc.name, func(t *testing.T) {
			test := newLossTest(t, clientSide, lossTestOpts{})
			t.Logf("# first ack establishes smoothed_rtt")
			test.send(initialSpace, 0)
			test.advance(tc.initialRTT)
			test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
			test.wantAck(initialSpace, 0)

			t.Logf("# ack of packet 2 starts loss timer for packet 1")
			test.send(initialSpace, 1, 2)
			test.advance(tc.latestRTT)
			test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{2, 3})
			test.wantAck(initialSpace, 2)

			t.Logf("# smoothed_rtt = %v", test.c.rtt.smoothedRTT)
			t.Logf("# latest_rtt = %v", test.c.rtt.latestRTT)
			t.Logf("# timeout = max(9/8 * max(smoothed_rtt, latest_rtt), 1ms)")
			t.Logf("#           (measured since packet 1 sent)")
			test.wantTimeout(tc.wantTimeout - tc.latestRTT)

			t.Logf("# advancing to the loss time causes loss of packet 1")
			test.advanceToLossTimer()
			test.wantLoss(initialSpace, 1)
		})
	}
}

func TestLossPTONotAckEliciting(t *testing.T) {
	// "When an ack-eliciting packet is transmitted,
	// the sender schedules a timer for the PTO period [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-1
	test := newLossTest(t, clientSide, lossTestOpts{})
	t.Logf("# PTO timer for first packet")
	test.send(initialSpace, 0)
	test.wantVar("smoothed_rtt", 333*time.Millisecond) // initial value
	test.wantVar("rttvar", 333*time.Millisecond/2)     // initial value
	t.Logf("# PTO = smoothed_rtt + max(4*rttvar, 1ms)")
	test.wantTimeout(999 * time.Millisecond)

	t.Logf("# sending a non-ack-eliciting packet doesn't adjust PTO")
	test.advance(333 * time.Millisecond)
	test.send(initialSpace, 1, sentPacket{
		ackEliciting: false,
	})
	test.wantVar("smoothed_rtt", 333*time.Millisecond) // unchanged
	test.wantVar("rttvar", 333*time.Millisecond/2)     // unchanged
	test.wantTimeout(666 * time.Millisecond)
}

func TestLossPTOMaxAckDelay(t *testing.T) {
	// "When the PTO is armed for Initial or Handshake packet number spaces,
	// the max_ack_delay in the PTO period computation is set to 0 [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-4
	test := newLossTest(t, clientSide, lossTestOpts{})
	t.Logf("# PTO timer for first packet")
	test.send(initialSpace, 0)
	test.wantVar("smoothed_rtt", 333*time.Millisecond) // initial value
	test.wantVar("rttvar", 333*time.Millisecond/2)     // initial value
	t.Logf("# PTO = smoothed_rtt + max(4*rttvar, 1ms)")
	test.wantTimeout(999 * time.Millisecond)

	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)

	t.Logf("# PTO timer for handshake packet")
	test.send(handshakeSpace, 0)
	test.wantVar("smoothed_rtt", 10*time.Millisecond)
	test.wantVar("rttvar", 5*time.Millisecond)
	t.Logf("# PTO = smoothed_rtt + max(4*rttvar, 1ms)")
	test.wantTimeout(30 * time.Millisecond)

	test.advance(10 * time.Millisecond)
	test.ack(handshakeSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(handshakeSpace, 0)
	test.confirmHandshake()

	t.Logf("# PTO timer for appdata packet")
	test.send(appDataSpace, 0)
	test.wantVar("smoothed_rtt", 10*time.Millisecond)
	test.wantVar("rttvar", 3750*time.Microsecond)
	t.Logf("# PTO = smoothed_rtt + max(4*rttvar, 1ms) + max_ack_delay (25ms)")
	test.wantTimeout(50 * time.Millisecond)
}

func TestLossPTOUnderTimerGranularity(t *testing.T) {
	// "The PTO period MUST be at least kGranularity [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-5
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.send(initialSpace, 0)
	test.advance(10 * time.Microsecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)

	test.send(initialSpace, 1)
	test.wantVar("smoothed_rtt", 10*time.Microsecond)
	test.wantVar("rttvar", 5*time.Microsecond)
	t.Logf("# PTO = smoothed_rtt + max(4*rttvar, 1ms)")
	test.wantTimeout(10*time.Microsecond + 1*time.Millisecond)
}

func TestLossPTOMultipleSpaces(t *testing.T) {
	// "[...] the timer MUST be set to the earlier value of the Initial and Handshake
	// packet number spaces."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-6
	test := newLossTest(t, clientSide, lossTestOpts{})
	t.Logf("# PTO timer for first packet")
	test.send(initialSpace, 0)
	test.wantVar("smoothed_rtt", 333*time.Millisecond) // initial value
	test.wantVar("rttvar", 333*time.Millisecond/2)     // initial value
	t.Logf("# PTO = smoothed_rtt + max(4*rttvar, 1ms)")
	test.wantTimeout(999 * time.Millisecond)

	t.Logf("# Initial and Handshake packets in flight, first takes precedence")
	test.advance(333 * time.Millisecond)
	test.send(handshakeSpace, 0)
	test.wantTimeout(666 * time.Millisecond)

	t.Logf("# Initial packet acked, Handshake PTO timer armed")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	test.wantTimeout(999 * time.Millisecond)

	t.Logf("# send Initial, earlier Handshake PTO takes precedence")
	test.advance(333 * time.Millisecond)
	test.send(initialSpace, 1)
	test.wantTimeout(666 * time.Millisecond)
}

func TestLossPTOHandshakeConfirmation(t *testing.T) {
	// "An endpoint MUST NOT set its PTO timer for the Application Data
	// packet number space until the handshake is confirmed."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-7
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.send(initialSpace, 0)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)

	test.send(handshakeSpace, 0)
	test.ack(handshakeSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(handshakeSpace, 0)

	test.send(appDataSpace, 0)
	test.wantNoTimeout()
}

func TestLossPTOBackoffDoubles(t *testing.T) {
	// "When a PTO timer expires, the PTO backoff MUST be increased,
	// resulting in the PTO period being set to twice its current value."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-9
	test := newLossTest(t, serverSide, lossTestOpts{})
	test.datagramReceived(1200)
	test.send(initialSpace, 0)
	test.wantVar("smoothed_rtt", 333*time.Millisecond) // initial value
	test.wantVar("rttvar", 333*time.Millisecond/2)     // initial value
	t.Logf("# PTO = smoothed_rtt + max(4*rttvar, 1ms)")
	test.wantTimeout(999 * time.Millisecond)

	t.Logf("# wait for PTO timer expiration")
	test.advanceToLossTimer()
	test.wantPTOExpired()
	test.wantNoTimeout()

	t.Logf("# PTO timer doubles")
	test.send(initialSpace, 1)
	test.wantTimeout(2 * 999 * time.Millisecond)
	test.advanceToLossTimer()
	test.wantPTOExpired()
	test.wantNoTimeout()

	t.Logf("# PTO timer doubles again")
	test.send(initialSpace, 2)
	test.wantTimeout(4 * 999 * time.Millisecond)
	test.advanceToLossTimer()
	test.wantPTOExpired()
	test.wantNoTimeout()
}

func TestLossPTOBackoffResetOnAck(t *testing.T) {
	// "The PTO backoff factor is reset when an acknowledgment is received [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-9
	test := newLossTest(t, serverSide, lossTestOpts{})
	test.datagramReceived(1200)

	t.Logf("# first ack establishes smoothed_rtt = 10ms")
	test.send(initialSpace, 0)
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	t.Logf("# set rttvar for simplicity")
	test.setRTTVar(0)

	t.Logf("# send packet 1 and wait for PTO")
	test.send(initialSpace, 1)
	test.wantTimeout(11 * time.Millisecond)
	test.advanceToLossTimer()
	test.wantPTOExpired()
	test.wantNoTimeout()

	t.Logf("# send packet 2 & 3, PTO doubles")
	test.send(initialSpace, 2, 3)
	test.wantTimeout(22 * time.Millisecond)

	test.advance(10 * time.Millisecond)
	t.Logf("# check remaining PTO (22ms - 10ms elapsed)")
	test.wantTimeout(12 * time.Millisecond)

	t.Logf("# ACK to packet 2 resets PTO")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 3})
	test.wantAck(initialSpace, 1)
	test.wantAck(initialSpace, 2)

	t.Logf("# check remaining PTO (11ms - 10ms elapsed)")
	test.wantTimeout(1 * time.Millisecond)
}

func TestLossPTOBackoffNotResetOnClientInitialAck(t *testing.T) {
	// "[...] a client does not reset the PTO backoff factor on
	// receiving acknowledgments in Initial packets."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-9
	test := newLossTest(t, clientSide, lossTestOpts{})

	t.Logf("# first ack establishes smoothed_rtt = 10ms")
	test.send(initialSpace, 0)
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	t.Logf("# set rttvar for simplicity")
	test.setRTTVar(0)

	t.Logf("# send packet 1 and wait for PTO")
	test.send(initialSpace, 1)
	test.wantTimeout(11 * time.Millisecond)
	test.advanceToLossTimer()
	test.wantPTOExpired()
	test.wantNoTimeout()

	t.Logf("# send more packets, PTO doubles")
	test.send(initialSpace, 2, 3)
	test.send(handshakeSpace, 0)
	test.wantTimeout(22 * time.Millisecond)

	test.advance(10 * time.Millisecond)
	t.Logf("# check remaining PTO (22ms - 10ms elapsed)")
	test.wantTimeout(12 * time.Millisecond)

	// TODO: Is this right? 6.2.1-9 says we don't reset the PTO *backoff*, not the PTO.
	// 6.2.1-8 says we reset the PTO timer when an ack-eliciting packet is sent *or
	// acknowledged*, but the pseudocode in appendix A doesn't appear to do the latter.
	t.Logf("# ACK to Initial packet does not reset PTO for client")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 3})
	test.wantAck(initialSpace, 1)
	test.wantAck(initialSpace, 2)
	t.Logf("# check remaining PTO (22ms - 10ms elapsed)")
	test.wantTimeout(12 * time.Millisecond)

	t.Logf("# ACK to handshake packet does reset PTO")
	test.ack(handshakeSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(handshakeSpace, 0)
	t.Logf("# check remaining PTO (12ms - 10ms elapsed)")
	test.wantTimeout(1 * time.Millisecond)
}

func TestLossPTONotSetWhenLossTimerSet(t *testing.T) {
	// "The PTO timer MUST NOT be set if a timer is set
	// for time threshold loss detection [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-12
	test := newLossTest(t, serverSide, lossTestOpts{})
	test.datagramReceived(1200)
	t.Logf("# PTO timer set for first packets sent")
	test.send(initialSpace, 0, 1)
	test.wantVar("smoothed_rtt", 333*time.Millisecond) // initial value
	test.wantVar("rttvar", 333*time.Millisecond/2)     // initial value
	t.Logf("# PTO = smoothed_rtt + max(4*rttvar, 1ms)")
	test.wantTimeout(999 * time.Millisecond)

	t.Logf("# ack of packet 1 starts loss timer for 0, PTO overridden")
	test.advance(333 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(initialSpace, 1)

	t.Logf("# latest_rtt == smoothed_rtt")
	test.wantVar("smoothed_rtt", 333*time.Millisecond)
	test.wantVar("latest_rtt", 333*time.Millisecond)
	t.Logf("# timeout = 9/8 * max(smoothed_rtt, latest_rtt) - time_since_packet_sent")
	test.wantTimeout(((333 * time.Millisecond * 9) / 8) - 333*time.Millisecond)
}

func TestLossDiscardingKeysResetsTimers(t *testing.T) {
	// "When Initial or Handshake keys are discarded,
	// the PTO and loss detection timers MUST be reset"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.2-3
	test := newLossTest(t, clientSide, lossTestOpts{})

	t.Logf("# handshake packet sent 1ms after initial")
	test.send(initialSpace, 0, 1)
	test.advance(1 * time.Millisecond)
	test.send(handshakeSpace, 0, 1)
	test.advance(9 * time.Millisecond)

	t.Logf("# ack of Initial packet 2 starts loss timer for packet 1")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(initialSpace, 1)

	test.advance(1 * time.Millisecond)
	t.Logf("# smoothed_rtt = %v", 10*time.Millisecond)
	t.Logf("# latest_rtt = %v", 10*time.Millisecond)
	t.Logf("# timeout = max(9/8 * max(smoothed_rtt, latest_rtt), 1ms)")
	t.Logf("#           (measured since Initial packet 1 sent)")
	test.wantTimeout((10 * time.Millisecond * 9 / 8) - 11*time.Millisecond)

	t.Logf("# ack of Handshake packet 2 starts loss timer for packet 1")
	test.ack(handshakeSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(handshakeSpace, 1)

	t.Logf("# dropping Initial keys sets timer to Handshake timeout")
	test.discardKeys(initialSpace)
	test.wantTimeout((10 * time.Millisecond * 9 / 8) - 10*time.Millisecond)
}

func TestLossNoPTOAtAntiAmplificationLimit(t *testing.T) {
	// "If no additional data can be sent [because the server is at the
	// anti-amplification limit], the server's PTO timer MUST NOT be armed [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.2.1-1
	test := newLossTest(t, serverSide, lossTestOpts{
		maxDatagramSize: 1 << 20, // large initial congestion window
	})
	test.datagramReceived(1200)
	test.send(initialSpace, 0, sentPacket{
		ackEliciting: true,
		inFlight:     true,
		size:         1200,
	})
	test.wantTimeout(999 * time.Millisecond)

	t.Logf("PTO timer should be disabled when at the anti-amplification limit")
	test.send(initialSpace, 1, sentPacket{
		ackEliciting: false,
		inFlight:     true,
		size:         2 * 1200,
	})
	test.wantNoTimeout()

	// "When the server receives a datagram from the client, the amplification
	// limit is increased and the server resets the PTO timer."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.2.1-2
	t.Logf("PTO timer should be reset when datagrams are received")
	test.datagramReceived(1200)
	test.wantTimeout(999 * time.Millisecond)

	// "If the PTO timer is then set to a time in the past, it is executed immediately."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.2.1-2
	test.send(initialSpace, 2, sentPacket{
		ackEliciting: true,
		inFlight:     true,
		size:         3 * 1200,
	})
	test.wantNoTimeout()
	t.Logf("resetting expired PTO timer should exeute immediately")
	test.advance(1000 * time.Millisecond)
	test.datagramReceived(1200)
	test.wantPTOExpired()
	test.wantNoTimeout()
}

func TestLossClientSetsPTOWhenHandshakeUnacked(t *testing.T) {
	// "[...] the client MUST set the PTO timer if the client has not
	// received an acknowledgment for any of its Handshake packets and
	// the handshake is not confirmed [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.2.1-3
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.send(initialSpace, 0)

	test.wantVar("smoothed_rtt", 333*time.Millisecond) // initial value
	test.wantVar("rttvar", 333*time.Millisecond/2)     // initial value
	t.Logf("# PTO = smoothed_rtt + max(4*rttvar, 1ms)")
	test.wantTimeout(999 * time.Millisecond)

	test.advance(333 * time.Millisecond)
	test.wantTimeout(666 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	t.Logf("# PTO timer set for a client before handshake ack even if no packets in flight")
	test.wantTimeout(999 * time.Millisecond)

	test.advance(333 * time.Millisecond)
	test.wantTimeout(666 * time.Millisecond)
}

func TestLossKeysDiscarded(t *testing.T) {
	// "The sender MUST discard all recovery state associated with
	// [packets in number spaces with discarded keys] and MUST remove
	// them from the count of bytes in flight."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.4-1
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.send(initialSpace, 0, testSentPacketSize(1200))
	test.send(initialSpace, 1, testSentPacketSize(1200)) // will be acked
	test.send(initialSpace, 2, testSentPacketSize(1200))
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(initialSpace, 1)
	test.send(handshakeSpace, 0, testSentPacketSize(600))
	test.send(handshakeSpace, 1, testSentPacketSize(600)) // will be acked
	test.send(handshakeSpace, 2, testSentPacketSize(600))
	test.ack(handshakeSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(handshakeSpace, 1)
	test.wantVar("bytes_in_flight", 1200+1200+600+600) // 3600

	test.discardKeys(initialSpace)
	test.wantVar("bytes_in_flight", 600+600) // 1200

	test.discardKeys(handshakeSpace)
	test.wantVar("bytes_in_flight", 0)
}

func TestLossDiscardPackets(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{})
	test.send(initialSpace, 0, testSentPacketSize(1200))
	test.send(initialSpace, 1, testSentPacketSize(1200)) // will be acked
	test.send(initialSpace, 2, testSentPacketSize(1200))
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(initialSpace, 1)

	test.discardPackets(initialSpace)
	test.wantLoss(initialSpace, 0)
	test.wantLoss(initialSpace, 2)
	test.wantVar("bytes_in_flight", 0)
}

func TestLossInitialCongestionWindow(t *testing.T) {
	// "Endpoints SHOULD use an initial congestion window of [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.2-1

	// "[...] 10 times the maximum datagram size [...]"
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	t.Logf("# congestion_window = 10*max_datagram_size (1200)")
	test.wantVar("congestion_window", 12000)

	// "[...] while limiting the window to the larger of 14720 bytes [...]"
	test = newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1500,
	})
	t.Logf("# congestion_window limited to 14720 bytes")
	test.wantVar("congestion_window", 14720)

	// "[...] or twice the maximum datagram size."
	test = newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 10000,
	})
	t.Logf("# congestion_window limited to 2*max_datagram_size (10000)")
	test.wantVar("congestion_window", 20000)

	for _, tc := range []struct {
		maxDatagramSize  int
		wantInitialBurst int
	}{{
		// "[...] 10 times the maximum datagram size [...]"
		maxDatagramSize:  1200,
		wantInitialBurst: 12000,
	}, {
		// "[...] while limiting the window to the larger of 14720 bytes [...]"
		maxDatagramSize:  1500,
		wantInitialBurst: 14720,
	}, {
		// "[...] or twice the maximum datagram size."
		maxDatagramSize:  10000,
		wantInitialBurst: 20000,
	}} {
		t.Run(fmt.Sprintf("max_datagram_size=%v", tc.maxDatagramSize), func(t *testing.T) {
			test := newLossTest(t, clientSide, lossTestOpts{
				maxDatagramSize: tc.maxDatagramSize,
			})

			var num packetNumber
			window := tc.wantInitialBurst
			for window >= tc.maxDatagramSize {
				t.Logf("# %v bytes of initial congestion window remain", window)
				test.send(initialSpace, num, sentPacket{
					ackEliciting: true,
					inFlight:     true,
					size:         tc.maxDatagramSize,
				})
				window -= tc.maxDatagramSize
				num++
			}
			t.Logf("# congestion window (%v) < max_datagram_size, congestion control blocks send", window)
			test.wantSendLimit(ccLimited)
		})
	}
}

func TestLossBytesInFlight(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	t.Logf("# sent packets are added to bytes_in_flight")
	test.wantVar("bytes_in_flight", 0)
	test.send(initialSpace, 0, testSentPacketSize(1200))
	test.wantVar("bytes_in_flight", 1200)
	test.send(initialSpace, 1, testSentPacketSize(800))
	test.wantVar("bytes_in_flight", 2000)

	t.Logf("# acked packets are removed from bytes_in_flight")
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{1, 2})
	test.wantAck(initialSpace, 1)
	test.wantVar("bytes_in_flight", 1200)

	t.Logf("# lost packets are removed from bytes_in_flight")
	test.advanceToLossTimer()
	test.wantLoss(initialSpace, 0)
	test.wantVar("bytes_in_flight", 0)
}

func TestLossCongestionWindowLimit(t *testing.T) {
	// "An endpoint MUST NOT send a packet if it would cause bytes_in_flight
	// [...] to be larger than the congestion window [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7-7
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	t.Logf("# consume the initial congestion window")
	test.send(initialSpace, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, testSentPacketSize(1200))
	test.wantSendLimit(ccLimited)

	t.Logf("# give the pacer bucket time to refill")
	test.advance(333 * time.Millisecond) // initial RTT

	t.Logf("# sending limited by congestion window, not the pacer")
	test.wantVar("congestion_window", 12000)
	test.wantVar("bytes_in_flight", 12000)
	test.wantVar("pacer_bucket", 12000)
	test.wantSendLimit(ccLimited)

	t.Logf("# receiving an ack opens up the congestion window")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	test.wantSendLimit(ccOK)
}

func TestLossCongestionStates(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	t.Logf("# consume the initial congestion window")
	test.send(initialSpace, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, testSentPacketSize(1200))
	test.wantSendLimit(ccLimited)
	test.wantVar("congestion_window", 12000)

	// "While a sender is in slow start, the congestion window
	// increases by the number of bytes acknowledged [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.1-2
	test.advance(333 * time.Millisecond)
	t.Logf("# congestion window increases by number of bytes acked (1200)")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	test.wantVar("congestion_window", 13200) // 12000 + 1200

	t.Logf("# congestion window increases by number of bytes acked (2400)")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 3})
	test.wantAck(initialSpace, 1, 2)
	test.wantVar("congestion_window", 15600) // 12000 + 3*1200

	// TODO: ECN-CE count

	// "The sender MUST exit slow start and enter a recovery period
	// when a packet is lost [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.1-3
	t.Logf("# loss of a packet triggers entry to a recovery period")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{6, 7})
	test.wantAck(initialSpace, 6)
	test.wantLoss(initialSpace, 3)

	// "On entering a recovery period, a sender MUST set the slow start
	// threshold to half the value of the congestion window when loss is detected."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2-2
	t.Logf("# slow_start_threshold = congestion_window / 2")
	test.wantVar("slow_start_threshold", 7800) // 15600/2

	// "[...] a single packet can be sent prior to reduction [of the congestion window]."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2-3
	test.send(initialSpace, 10, testSentPacketSize(1200))

	// "The congestion window MUST be set to the reduced value of the slow start
	// threshold before exiting the recovery period."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2-2
	t.Logf("# congestion window reduced to slow start threshold")
	test.wantVar("congestion_window", 7800)

	t.Logf("# acks for packets sent before recovery started do not affect congestion")
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 10})
	test.wantAck(initialSpace, 4, 5, 7, 8, 9)
	test.wantVar("slow_start_threshold", 7800)
	test.wantVar("congestion_window", 7800)

	// "A recovery period ends and the sender enters congestion avoidance when
	// a packet sent during the recovery period is acknowledged."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.2-5
	t.Logf("# recovery ends and congestion avoidance begins when packet 10 is acked")
	test.advance(333 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 11})
	test.wantAck(initialSpace, 10)

	// "[...] limit the increase to the congestion window to at most one
	// maximum datagram size for each congestion window that is acknowledged."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.3-2
	t.Logf("# after processing acks for one congestion window's worth of data...")
	test.send(initialSpace, 11, 12, 13, 14, 15, 16, testSentPacketSize(1200))
	test.advance(333 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 17})
	test.wantAck(initialSpace, 11, 12, 13, 14, 15, 16)
	t.Logf("# ...congestion window increases by max_datagram_size")
	test.wantVar("congestion_window", 9000) // 7800 + 1200

	// "The sender exits congestion avoidance and enters a recovery period
	// when a packet is lost [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.3.3-3
	test.send(initialSpace, 17, 18, 19, 20, 21, testSentPacketSize(1200))
	test.advance(333 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{18, 21})
	test.wantAck(initialSpace, 18, 19, 20)
	test.wantLoss(initialSpace, 17)
	t.Logf("# slow_start_threshold = congestion_window / 2")
	test.wantVar("slow_start_threshold", 4500)
}

func TestLossMinimumCongestionWindow(t *testing.T) {
	// "The RECOMMENDED [minimum congestion window] is 2 * max_datagram_size."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.2-4
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	test.send(initialSpace, 0, 1, 2, 3, testSentPacketSize(1200))
	test.wantVar("congestion_window", 12000)

	t.Logf("# enter recovery")
	test.advance(333 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{3, 4})
	test.wantAck(initialSpace, 3)
	test.wantLoss(initialSpace, 0)
	test.wantVar("congestion_window", 6000)

	t.Logf("# enter congestion avoidance and return to recovery")
	test.send(initialSpace, 4, 5, 6, 7)
	test.advance(333 * time.Millisecond)
	test.wantLoss(initialSpace, 1, 2)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{7, 8})
	test.wantAck(initialSpace, 7)
	test.wantLoss(initialSpace, 4)
	test.wantVar("congestion_window", 3000)

	t.Logf("# enter congestion avoidance and return to recovery")
	test.send(initialSpace, 8, 9, 10, 11)
	test.advance(333 * time.Millisecond)
	test.wantLoss(initialSpace, 5, 6)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{11, 12})
	test.wantAck(initialSpace, 11)
	test.wantLoss(initialSpace, 8)
	t.Logf("# congestion window does not fall below 2*max_datagram_size")
	test.wantVar("congestion_window", 2400)

	t.Logf("# enter congestion avoidance and return to recovery")
	test.send(initialSpace, 12, 13, 14, 15)
	test.advance(333 * time.Millisecond)
	test.wantLoss(initialSpace, 9, 10)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{15, 16})
	test.wantAck(initialSpace, 15)
	test.wantLoss(initialSpace, 12)
	t.Logf("# congestion window does not fall below 2*max_datagram_size")
	test.wantVar("congestion_window", 2400)
}

func TestLossPersistentCongestion(t *testing.T) {
	// "When persistent congestion is declared, the sender's congestion
	// window MUST be reduced to the minimum congestion window [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.6.2-6
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	test.send(initialSpace, 0, testSentPacketSize(1200))
	test.c.cc.setUnderutilized(nil, true)

	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)

	t.Logf("# set rttvar for simplicity")
	test.setRTTVar(0)
	test.wantVar("smoothed_rtt", 10*time.Millisecond)
	t.Logf("# persistent congestion duration = 3*(smoothed_rtt + timerGranularity + max_ack_delay)")
	t.Logf("# persistent congestion duration = 108ms")

	t.Logf("# sending packets 1-5 over 108ms")
	test.send(initialSpace, 1, testSentPacketSize(1200))

	test.advance(11 * time.Millisecond) // total 11ms
	test.wantPTOExpired()
	test.send(initialSpace, 2, testSentPacketSize(1200))

	test.advance(22 * time.Millisecond) // total 33ms
	test.wantPTOExpired()
	test.send(initialSpace, 3, testSentPacketSize(1200))

	test.advance(44 * time.Millisecond) // total 77ms
	test.wantPTOExpired()
	test.send(initialSpace, 4, testSentPacketSize(1200))

	test.advance(31 * time.Millisecond) // total 108ms
	test.send(initialSpace, 5, testSentPacketSize(1200))
	t.Logf("# 108ms between packets 1-5")

	test.wantVar("congestion_window", 12000)
	t.Logf("# triggering loss of packets 1-5")
	test.send(initialSpace, 6, 7, 8, testSentPacketSize(1200))
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{8, 9})
	test.wantAck(initialSpace, 8)
	test.wantLoss(initialSpace, 1, 2, 3, 4, 5)

	t.Logf("# lost packets spanning persistent congestion duration")
	t.Logf("# congestion_window = 2 * max_datagram_size (minimum)")
	test.wantVar("congestion_window", 2400)
}

func TestLossSimplePersistentCongestion(t *testing.T) {
	// Simpler version of TestLossPersistentCongestion which acts as a
	// base for subsequent tests.
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})

	t.Logf("# establish initial RTT sample")
	test.send(initialSpace, 0, testSentPacketSize(1200))
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)

	t.Logf("# send two packets spanning persistent congestion duration")
	test.send(initialSpace, 1, testSentPacketSize(1200))
	t.Logf("# 2000ms >> persistent congestion duration")
	test.advance(2000 * time.Millisecond)
	test.wantPTOExpired()
	test.send(initialSpace, 2, testSentPacketSize(1200))

	t.Logf("# trigger loss of previous packets")
	test.advance(10 * time.Millisecond)
	test.send(initialSpace, 3, testSentPacketSize(1200))
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{3, 4})
	test.wantAck(initialSpace, 3)
	test.wantLoss(initialSpace, 1, 2)

	t.Logf("# persistent congestion detected")
	test.wantVar("congestion_window", 2400)
}

func TestLossPersistentCongestionAckElicitingPackets(t *testing.T) {
	// "These two packets MUST be ack-eliciting [...]"
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.6.2-3
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})

	t.Logf("# establish initial RTT sample")
	test.send(initialSpace, 0, testSentPacketSize(1200))
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)

	t.Logf("# send two packets spanning persistent congestion duration")
	test.send(initialSpace, 1, testSentPacketSize(1200))
	t.Logf("# 2000ms >> persistent congestion duration")
	test.advance(2000 * time.Millisecond)
	test.wantPTOExpired()
	test.send(initialSpace, 2, sentPacket{
		inFlight:     true,
		ackEliciting: false,
		size:         1200,
	})
	test.send(initialSpace, 3, testSentPacketSize(1200)) // PTO probe

	t.Logf("# trigger loss of previous packets")
	test.advance(10 * time.Millisecond)
	test.send(initialSpace, 4, testSentPacketSize(1200))
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{3, 5})
	test.wantAck(initialSpace, 3)
	test.wantAck(initialSpace, 4)
	test.wantLoss(initialSpace, 1, 2)

	t.Logf("# persistent congestion not detected: packet 2 is not ack-eliciting")
	test.wantVar("congestion_window", (12000+1200+1200-1200)/2)
}

func TestLossNoPersistentCongestionWithoutRTTSample(t *testing.T) {
	// "The persistent congestion period SHOULD NOT start until there
	// is at least one RTT sample."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.6.2-4
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})

	t.Logf("# packets sent before initial RTT sample")
	test.send(initialSpace, 0, testSentPacketSize(1200))
	test.advance(2000 * time.Millisecond)
	test.wantPTOExpired()
	test.send(initialSpace, 1, testSentPacketSize(1200))

	test.advance(10 * time.Millisecond)
	test.send(initialSpace, 2, testSentPacketSize(1200))

	t.Logf("# first ack establishes RTT sample")
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{2, 3})
	test.wantAck(initialSpace, 2)
	test.wantLoss(initialSpace, 0, 1)

	t.Logf("# loss of packets before initial RTT sample does not cause persistent congestion")
	test.wantVar("congestion_window", 12000/2)
}

func TestLossPacerRefillRate(t *testing.T) {
	// "A sender SHOULD pace sending of all in-flight packets based on
	// input from the congestion controller."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.7-1
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	t.Logf("# consume the initial congestion window")
	test.send(initialSpace, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, testSentPacketSize(1200))
	test.wantSendLimit(ccLimited)
	test.wantVar("pacer_bucket", 0)
	test.wantVar("congestion_window", 12000)

	t.Logf("# first RTT sample establishes smoothed_rtt")
	rtt := 100 * time.Millisecond
	test.advance(rtt)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 10})
	test.wantAck(initialSpace, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
	test.wantVar("congestion_window", 24000) // 12000 + 10*1200
	test.wantVar("smoothed_rtt", rtt)

	t.Logf("# advance 1 RTT to let the pacer bucket refill completely")
	test.advance(100 * time.Millisecond)
	t.Logf("# pacer_bucket = initial_congestion_window")
	test.wantVar("pacer_bucket", 12000)

	t.Logf("# consume capacity from the pacer bucket")
	test.send(initialSpace, 10, testSentPacketSize(1200))
	test.wantVar("pacer_bucket", 10800) // 12000 - 1200
	test.send(initialSpace, 11, testSentPacketSize(600))
	test.wantVar("pacer_bucket", 10200) // 10800 - 600
	test.send(initialSpace, 12, testSentPacketSize(600))
	test.wantVar("pacer_bucket", 9600) // 10200 - 600
	test.send(initialSpace, 13, 14, 15, 16, testSentPacketSize(1200))
	test.wantVar("pacer_bucket", 4800) // 9600 - 4*1200

	t.Logf("# advance 1/10 of an RTT, bucket refills")
	test.advance(rtt / 10)
	t.Logf("# pacer_bucket += 1.25 * (1/10) * congestion_window")
	t.Logf("#              += 3000")
	test.wantVar("pacer_bucket", 7800)
}

func TestLossPacerNextSendTime(t *testing.T) {
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	t.Logf("# consume the initial congestion window")
	test.send(initialSpace, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, testSentPacketSize(1200))
	test.wantSendLimit(ccLimited)
	test.wantVar("pacer_bucket", 0)
	test.wantVar("congestion_window", 12000)

	t.Logf("# first RTT sample establishes smoothed_rtt")
	rtt := 100 * time.Millisecond
	test.advance(rtt)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 10})
	test.wantAck(initialSpace, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
	test.wantVar("congestion_window", 24000) // 12000 + 10*1200
	test.wantVar("smoothed_rtt", rtt)

	t.Logf("# advance 1 RTT to let the pacer bucket refill completely")
	test.advance(100 * time.Millisecond)
	t.Logf("# pacer_bucket = initial_congestion_window")
	test.wantVar("pacer_bucket", 12000)

	t.Logf("# consume the refilled pacer bucket")
	test.send(initialSpace, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, testSentPacketSize(1200))
	test.wantSendLimit(ccPaced)

	t.Logf("# refill rate = 1.25 * congestion_window / rtt")
	test.wantSendDelay(rtt / 25) // rtt / (1.25 * 24000 / 1200)

	t.Logf("# no capacity available yet")
	test.advance(rtt / 50)
	test.wantVar("pacer_bucket", -600)
	test.wantSendLimit(ccPaced)

	t.Logf("# capacity available")
	test.advance(rtt / 50)
	test.wantVar("pacer_bucket", 0)
	test.wantSendLimit(ccOK)
}

func TestLossCongestionWindowUnderutilized(t *testing.T) {
	// "When bytes in flight is smaller than the congestion window
	// and sending is not pacing limited [...] the congestion window
	// SHOULD NOT be increased in either slow start or congestion avoidance."
	// https://www.rfc-editor.org/rfc/rfc9002.html#section-7.8-1
	test := newLossTest(t, clientSide, lossTestOpts{
		maxDatagramSize: 1200,
	})
	test.send(initialSpace, 0, testSentPacketSize(1200))
	test.setUnderutilized(true)
	t.Logf("# underutilized: %v", test.c.cc.underutilized)
	test.wantVar("congestion_window", 12000)

	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 1})
	test.wantAck(initialSpace, 0)
	t.Logf("# congestion window does not increase, because window is underutilized")
	test.wantVar("congestion_window", 12000)

	t.Logf("# refill pacer bucket")
	test.advance(10 * time.Millisecond)
	test.wantVar("pacer_bucket", 12000)

	test.send(initialSpace, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, testSentPacketSize(1200))
	test.setUnderutilized(false)
	test.advance(10 * time.Millisecond)
	test.ack(initialSpace, 0*time.Millisecond, i64range[packetNumber]{0, 11})
	test.wantAck(initialSpace, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
	t.Logf("# congestion window increases")
	test.wantVar("congestion_window", 24000)
}

type lossTest struct {
	t      *testing.T
	c      lossState
	now    time.Time
	fates  map[spaceNum]packetFate
	failed bool
}

type lossTestOpts struct {
	maxDatagramSize int
}

func newLossTest(t *testing.T, side connSide, opts lossTestOpts) *lossTest {
	c := &lossTest{
		t:     t,
		now:   time.Date(2000, 1, 1, 0, 0, 0, 0, time.UTC),
		fates: make(map[spaceNum]packetFate),
	}
	maxDatagramSize := 1200
	if opts.maxDatagramSize != 0 {
		maxDatagramSize = opts.maxDatagramSize
	}
	c.c.init(side, maxDatagramSize, c.now)
	t.Cleanup(func() {
		if !c.failed {
			c.checkUnexpectedEvents()
		}
	})
	return c
}

type spaceNum struct {
	space numberSpace
	num   packetNumber
}

func (c *lossTest) checkUnexpectedEvents() {
	c.t.Helper()
	for sn, fate := range c.fates {
		c.t.Errorf("ERROR: unexpected %v: %v %v", fate, sn.space, sn.num)
	}
	if c.c.ptoExpired {
		c.t.Errorf("ERROR: PTO timer unexpectedly expired")
	}
}

func (c *lossTest) setSmoothedRTT(d time.Duration) {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.t.Logf("set smoothed_rtt to %v", d)
	c.c.rtt.smoothedRTT = d
}

func (c *lossTest) setRTTVar(d time.Duration) {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.t.Logf("set rttvar to %v", d)
	c.c.rtt.rttvar = d
}

func (c *lossTest) setUnderutilized(v bool) {
	c.t.Logf("set congestion window underutilized: %v", v)
	c.c.cc.setUnderutilized(nil, v)
}

func (c *lossTest) advance(d time.Duration) {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.t.Logf("advance time %v", d)
	c.now = c.now.Add(d)
	c.c.advance(c.now, c.onAckOrLoss)
}

func (c *lossTest) advanceToLossTimer() {
	c.t.Helper()
	c.checkUnexpectedEvents()
	d := c.c.timer.Sub(c.now)
	c.t.Logf("advance time %v (up to loss timer)", d)
	if d < 0 {
		c.t.Fatalf("loss timer is in the past")
	}
	c.now = c.c.timer
	c.c.advance(c.now, c.onAckOrLoss)
}

type testSentPacketSize int

func (c *lossTest) send(spaceID numberSpace, opts ...any) {
	c.t.Helper()
	c.checkUnexpectedEvents()
	var nums []packetNumber
	prototype := sentPacket{
		ackEliciting: true,
		inFlight:     true,
	}
	for _, o := range opts {
		switch o := o.(type) {
		case sentPacket:
			prototype = o
		case testSentPacketSize:
			prototype.size = int(o)
		case int:
			nums = append(nums, packetNumber(o))
		case packetNumber:
			nums = append(nums, o)
		case i64range[packetNumber]:
			for num := o.start; num < o.end; num++ {
				nums = append(nums, num)
			}
		}
	}
	c.t.Logf("send %v %v", spaceID, nums)
	limit, _ := c.c.sendLimit(c.now)
	if prototype.inFlight && limit != ccOK {
		c.t.Fatalf("congestion control blocks sending packet")
	}
	if !prototype.inFlight && limit == ccBlocked {
		c.t.Fatalf("congestion control blocks sending packet")
	}
	for _, num := range nums {
		sent := &sentPacket{}
		*sent = prototype
		sent.num = num
		c.c.packetSent(c.now, nil, spaceID, sent)
	}
}

func (c *lossTest) datagramReceived(size int) {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.t.Logf("receive %v-byte datagram", size)
	c.c.datagramReceived(c.now, size)
}

func (c *lossTest) ack(spaceID numberSpace, ackDelay time.Duration, rs ...i64range[packetNumber]) {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.c.receiveAckStart()
	var acked rangeset[packetNumber]
	for _, r := range rs {
		c.t.Logf("ack %v delay=%v [%v,%v)", spaceID, ackDelay, r.start, r.end)
		acked.add(r.start, r.end)
	}
	for i, r := range rs {
		c.t.Logf("ack %v delay=%v [%v,%v)", spaceID, ackDelay, r.start, r.end)
		c.c.receiveAckRange(c.now, spaceID, i, r.start, r.end, c.onAckOrLoss)
	}
	c.c.receiveAckEnd(c.now, nil, spaceID, ackDelay, c.onAckOrLoss)
}

func (c *lossTest) onAckOrLoss(space numberSpace, sent *sentPacket, fate packetFate) {
	c.t.Logf("%v %v %v", fate, space, sent.num)
	if _, ok := c.fates[spaceNum{space, sent.num}]; ok {
		c.t.Errorf("ERROR: duplicate %v for %v %v", fate, space, sent.num)
	}
	c.fates[spaceNum{space, sent.num}] = fate
}

func (c *lossTest) confirmHandshake() {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.t.Logf("confirm handshake")
	c.c.confirmHandshake()
}

func (c *lossTest) validateClientAddress() {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.t.Logf("validate client address")
	c.c.validateClientAddress()
}

func (c *lossTest) discardKeys(spaceID numberSpace) {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.t.Logf("discard %s keys", spaceID)
	c.c.discardKeys(c.now, nil, spaceID)
}

func (c *lossTest) discardPackets(spaceID numberSpace) {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.t.Logf("discard packets in %s", spaceID)
	c.c.discardPackets(spaceID, nil, c.onAckOrLoss)
}

func (c *lossTest) setMaxAckDelay(d time.Duration) {
	c.t.Helper()
	c.checkUnexpectedEvents()
	c.t.Logf("set max_ack_delay = %v", d)
	c.c.setMaxAckDelay(d)
}

func (c *lossTest) wantAck(spaceID numberSpace, nums ...packetNumber) {
	c.t.Helper()
	for _, num := range nums {
		if c.fates[spaceNum{spaceID, num}] != packetAcked {
			c.t.Fatalf("expected ack for %v %v\n", spaceID, num)
		}
		delete(c.fates, spaceNum{spaceID, num})
	}
}

func (c *lossTest) wantLoss(spaceID numberSpace, nums ...packetNumber) {
	c.t.Helper()
	for _, num := range nums {
		if c.fates[spaceNum{spaceID, num}] != packetLost {
			c.t.Fatalf("expected loss of %v %v\n", spaceID, num)
		}
		delete(c.fates, spaceNum{spaceID, num})
	}
}

func (c *lossTest) wantPTOExpired() {
	c.t.Helper()
	if !c.c.ptoExpired {
		c.t.Fatalf("expected PTO timer to expire")
	} else {
		c.t.Logf("PTO TIMER EXPIRED")
	}
	c.c.ptoExpired = false
}

func (l ccLimit) String() string {
	switch l {
	case ccOK:
		return "ccOK"
	case ccBlocked:
		return "ccBlocked"
	case ccLimited:
		return "ccLimited"
	case ccPaced:
		return "ccPaced"
	}
	return "BUG"
}

func (c *lossTest) wantSendLimit(want ccLimit) {
	c.t.Helper()
	if got, _ := c.c.sendLimit(c.now); got != want {
		c.t.Fatalf("congestion control send limit is %v, want %v", got, want)
	}
}

func (c *lossTest) wantSendDelay(want time.Duration) {
	c.t.Helper()
	limit, next := c.c.sendLimit(c.now)
	if limit != ccPaced {
		c.t.Fatalf("congestion control limit is %v, want %v", limit, ccPaced)
	}
	got := next.Sub(c.now)
	if got != want {
		c.t.Fatalf("delay until next send is %v, want %v", got, want)
	}
}

func (c *lossTest) wantVar(name string, want any) {
	c.t.Helper()
	var got any
	switch name {
	case "latest_rtt":
		got = c.c.rtt.latestRTT
	case "min_rtt":
		got = c.c.rtt.minRTT
	case "smoothed_rtt":
		got = c.c.rtt.smoothedRTT
	case "rttvar":
		got = c.c.rtt.rttvar
	case "congestion_window":
		got = c.c.cc.congestionWindow
	case "slow_start_threshold":
		got = c.c.cc.slowStartThreshold
	case "bytes_in_flight":
		got = c.c.cc.bytesInFlight
	case "pacer_bucket":
		got = c.c.pacer.bucket
	default:
		c.t.Fatalf("unknown var %q", name)
	}
	if got != want {
		c.t.Fatalf("%v = %v, want %v\n", name, got, want)
	} else {
		c.t.Logf("%v = %v", name, got)
	}
}

func (c *lossTest) wantTimeout(want time.Duration) {
	c.t.Helper()
	if c.c.timer.IsZero() {
		c.t.Fatalf("loss detection timer is not set, want %v", want)
	}
	got := c.c.timer.Sub(c.now)
	if got != want {
		c.t.Fatalf("loss detection timer expires in %v, want %v", got, want)
	}
	c.t.Logf("loss detection timer expires in %v", got)
}

func (c *lossTest) wantNoTimeout() {
	c.t.Helper()
	if !c.c.timer.IsZero() {
		d := c.c.timer.Sub(c.now)
		c.t.Fatalf("loss detection timer expires in %v, want not set", d)
	}
	c.t.Logf("loss detection timer is not set")
}

func (f packetFate) String() string {
	switch f {
	case packetAcked:
		return "ACK"
	case packetLost:
		return "LOSS"
	default:
		panic("unknown packetFate")
	}
}