loss.go

Documentation: golang.org/x/net/quic

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  //go:build go1.21
     6  
     7  package quic
     8  
     9  import (
    10  	"context"
    11  	"log/slog"
    12  	"math"
    13  	"time"
    14  )
    15  
    16  type lossState struct {
    17  	side connSide
    18  
    19  	// True when the handshake is confirmed.
    20  	// https://www.rfc-editor.org/rfc/rfc9001#section-4.1.2
    21  	handshakeConfirmed bool
    22  
    23  	// Peer's max_ack_delay transport parameter.
    24  	// https://www.rfc-editor.org/rfc/rfc9000.html#section-18.2-4.28.1
    25  	maxAckDelay time.Duration
    26  
    27  	// Time of the next event: PTO expiration (if ptoTimerArmed is true),
    28  	// or loss detection.
    29  	// The connection must call lossState.advance when the timer expires.
    30  	timer time.Time
    31  
    32  	// True when the PTO timer is set.
    33  	ptoTimerArmed bool
    34  
    35  	// True when the PTO timer has expired and a probe packet has not yet been sent.
    36  	ptoExpired bool
    37  
    38  	// Count of PTO expirations since the lack received acknowledgement.
    39  	// https://www.rfc-editor.org/rfc/rfc9002#section-6.2.1-9
    40  	ptoBackoffCount int
    41  
    42  	// Anti-amplification limit: Three times the amount of data received from
    43  	// the peer, less the amount of data sent.
    44  	//
    45  	// Set to antiAmplificationUnlimited (MaxInt) to disable the limit.
    46  	// The limit is always disabled for clients, and for servers after the
    47  	// peer's address is validated.
    48  	//
    49  	// Anti-amplification is per-address; this will need to change if/when we
    50  	// support address migration.
    51  	//
    52  	// https://www.rfc-editor.org/rfc/rfc9000#section-8-2
    53  	antiAmplificationLimit int
    54  
    55  	// Count of non-ack-eliciting packets (ACKs) sent since the last ack-eliciting one.
    56  	consecutiveNonAckElicitingPackets int
    57  
    58  	rtt   rttState
    59  	pacer pacerState
    60  	cc    *ccReno
    61  
    62  	// Per-space loss detection state.
    63  	spaces [numberSpaceCount]struct {
    64  		sentPacketList
    65  		maxAcked         packetNumber
    66  		lastAckEliciting packetNumber
    67  	}
    68  
    69  	// Temporary state used when processing an ACK frame.
    70  	ackFrameRTT                  time.Duration // RTT from latest packet in frame
    71  	ackFrameContainsAckEliciting bool          // newly acks an ack-eliciting packet?
    72  }
    73  
    74  const antiAmplificationUnlimited = math.MaxInt
    75  
    76  func (c *lossState) init(side connSide, maxDatagramSize int, now time.Time) {
    77  	c.side = side
    78  	if side == clientSide {
    79  		// Clients don't have an anti-amplification limit.
    80  		c.antiAmplificationLimit = antiAmplificationUnlimited
    81  	}
    82  	c.rtt.init()
    83  	c.cc = newReno(maxDatagramSize)
    84  	c.pacer.init(now, c.cc.congestionWindow, timerGranularity)
    85  
    86  	// Peer's assumed max_ack_delay, prior to receiving transport parameters.
    87  	// https://www.rfc-editor.org/rfc/rfc9000#section-18.2
    88  	c.maxAckDelay = 25 * time.Millisecond
    89  
    90  	for space := range c.spaces {
    91  		c.spaces[space].maxAcked = -1
    92  		c.spaces[space].lastAckEliciting = -1
    93  	}
    94  }
    95  
    96  // setMaxAckDelay sets the max_ack_delay transport parameter received from the peer.
    97  func (c *lossState) setMaxAckDelay(d time.Duration) {
    98  	if d >= (1<<14)*time.Millisecond {
    99  		// Values of 2^14 or greater are invalid.
   100  		// https://www.rfc-editor.org/rfc/rfc9000.html#section-18.2-4.28.1
   101  		return
   102  	}
   103  	c.maxAckDelay = d
   104  }
   105  
   106  // confirmHandshake indicates the handshake has been confirmed.
   107  func (c *lossState) confirmHandshake() {
   108  	c.handshakeConfirmed = true
   109  }
   110  
   111  // validateClientAddress disables the anti-amplification limit after
   112  // a server validates a client's address.
   113  func (c *lossState) validateClientAddress() {
   114  	c.antiAmplificationLimit = antiAmplificationUnlimited
   115  }
   116  
   117  // minDatagramSize is the minimum datagram size permitted by
   118  // anti-amplification protection.
   119  //
   120  // Defining a minimum size avoids the case where, say, anti-amplification
   121  // technically allows us to send a 1-byte datagram, but no such datagram
   122  // can be constructed.
   123  const minPacketSize = 128
   124  
   125  type ccLimit int
   126  
   127  const (
   128  	ccOK      = ccLimit(iota) // OK to send
   129  	ccBlocked                 // sending blocked by anti-amplification
   130  	ccLimited                 // sending blocked by congestion control
   131  	ccPaced                   // sending allowed by congestion, but delayed by pacer
   132  )
   133  
   134  // sendLimit reports whether sending is possible at this time.
   135  // When sending is pacing limited, it returns the next time a packet may be sent.
   136  func (c *lossState) sendLimit(now time.Time) (limit ccLimit, next time.Time) {
   137  	if c.antiAmplificationLimit < minPacketSize {
   138  		// When at the anti-amplification limit, we may not send anything.
   139  		return ccBlocked, time.Time{}
   140  	}
   141  	if c.ptoExpired {
   142  		// On PTO expiry, send a probe.
   143  		return ccOK, time.Time{}
   144  	}
   145  	if !c.cc.canSend() {
   146  		// Congestion control blocks sending.
   147  		return ccLimited, time.Time{}
   148  	}
   149  	if c.cc.bytesInFlight == 0 {
   150  		// If no bytes are in flight, send packet unpaced.
   151  		return ccOK, time.Time{}
   152  	}
   153  	canSend, next := c.pacer.canSend(now)
   154  	if !canSend {
   155  		// Pacer blocks sending.
   156  		return ccPaced, next
   157  	}
   158  	return ccOK, time.Time{}
   159  }
   160  
   161  // maxSendSize reports the maximum datagram size that may be sent.
   162  func (c *lossState) maxSendSize() int {
   163  	return min(c.antiAmplificationLimit, c.cc.maxDatagramSize)
   164  }
   165  
   166  // advance is called when time passes.
   167  // The lossf function is called for each packet newly detected as lost.
   168  func (c *lossState) advance(now time.Time, lossf func(numberSpace, *sentPacket, packetFate)) {
   169  	c.pacer.advance(now, c.cc.congestionWindow, c.rtt.smoothedRTT)
   170  	if c.ptoTimerArmed && !c.timer.IsZero() && !c.timer.After(now) {
   171  		c.ptoExpired = true
   172  		c.timer = time.Time{}
   173  		c.ptoBackoffCount++
   174  	}
   175  	c.detectLoss(now, lossf)
   176  }
   177  
   178  // nextNumber returns the next packet number to use in a space.
   179  func (c *lossState) nextNumber(space numberSpace) packetNumber {
   180  	return c.spaces[space].nextNum
   181  }
   182  
   183  // packetSent records a sent packet.
   184  func (c *lossState) packetSent(now time.Time, log *slog.Logger, space numberSpace, sent *sentPacket) {
   185  	sent.time = now
   186  	c.spaces[space].add(sent)
   187  	size := sent.size
   188  	if c.antiAmplificationLimit != antiAmplificationUnlimited {
   189  		c.antiAmplificationLimit = max(0, c.antiAmplificationLimit-size)
   190  	}
   191  	if sent.inFlight {
   192  		c.cc.packetSent(now, log, space, sent)
   193  		c.pacer.packetSent(now, size, c.cc.congestionWindow, c.rtt.smoothedRTT)
   194  		if sent.ackEliciting {
   195  			c.spaces[space].lastAckEliciting = sent.num
   196  			c.ptoExpired = false // reset expired PTO timer after sending probe
   197  		}
   198  		c.scheduleTimer(now)
   199  		if logEnabled(log, QLogLevelPacket) {
   200  			logBytesInFlight(log, c.cc.bytesInFlight)
   201  		}
   202  	}
   203  	if sent.ackEliciting {
   204  		c.consecutiveNonAckElicitingPackets = 0
   205  	} else {
   206  		c.consecutiveNonAckElicitingPackets++
   207  	}
   208  }
   209  
   210  // datagramReceived records a datagram (not packet!) received from the peer.
   211  func (c *lossState) datagramReceived(now time.Time, size int) {
   212  	if c.antiAmplificationLimit != antiAmplificationUnlimited {
   213  		c.antiAmplificationLimit += 3 * size
   214  		// Reset the PTO timer, possibly to a point in the past, in which
   215  		// case the caller should execute it immediately.
   216  		// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.2.1-2
   217  		c.scheduleTimer(now)
   218  		if c.ptoTimerArmed && !c.timer.IsZero() && !c.timer.After(now) {
   219  			c.ptoExpired = true
   220  			c.timer = time.Time{}
   221  		}
   222  	}
   223  }
   224  
   225  // receiveAckStart starts processing an ACK frame.
   226  // Call receiveAckRange for each range in the frame.
   227  // Call receiveAckFrameEnd after all ranges are processed.
   228  func (c *lossState) receiveAckStart() {
   229  	c.ackFrameContainsAckEliciting = false
   230  	c.ackFrameRTT = -1
   231  }
   232  
   233  // receiveAckRange processes a range within an ACK frame.
   234  // The ackf function is called for each newly-acknowledged packet.
   235  func (c *lossState) receiveAckRange(now time.Time, space numberSpace, rangeIndex int, start, end packetNumber, ackf func(numberSpace, *sentPacket, packetFate)) {
   236  	// Limit our range to the intersection of the ACK range and
   237  	// the in-flight packets we have state for.
   238  	if s := c.spaces[space].start(); start < s {
   239  		start = s
   240  	}
   241  	if e := c.spaces[space].end(); end > e {
   242  		end = e
   243  	}
   244  	if start >= end {
   245  		return
   246  	}
   247  	if rangeIndex == 0 {
   248  		// If the latest packet in the ACK frame is newly-acked,
   249  		// record the RTT in c.ackFrameRTT.
   250  		sent := c.spaces[space].num(end - 1)
   251  		if !sent.acked {
   252  			c.ackFrameRTT = max(0, now.Sub(sent.time))
   253  		}
   254  	}
   255  	for pnum := start; pnum < end; pnum++ {
   256  		sent := c.spaces[space].num(pnum)
   257  		if sent.acked || sent.lost {
   258  			continue
   259  		}
   260  		// This is a newly-acknowledged packet.
   261  		if pnum > c.spaces[space].maxAcked {
   262  			c.spaces[space].maxAcked = pnum
   263  		}
   264  		sent.acked = true
   265  		c.cc.packetAcked(now, sent)
   266  		ackf(space, sent, packetAcked)
   267  		if sent.ackEliciting {
   268  			c.ackFrameContainsAckEliciting = true
   269  		}
   270  	}
   271  }
   272  
   273  // receiveAckEnd finishes processing an ack frame.
   274  // The lossf function is called for each packet newly detected as lost.
   275  func (c *lossState) receiveAckEnd(now time.Time, log *slog.Logger, space numberSpace, ackDelay time.Duration, lossf func(numberSpace, *sentPacket, packetFate)) {
   276  	c.spaces[space].sentPacketList.clean()
   277  	// Update the RTT sample when the largest acknowledged packet in the ACK frame
   278  	// is newly acknowledged, and at least one newly acknowledged packet is ack-eliciting.
   279  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-5.1-2.2
   280  	if c.ackFrameRTT >= 0 && c.ackFrameContainsAckEliciting {
   281  		c.rtt.updateSample(now, c.handshakeConfirmed, space, c.ackFrameRTT, ackDelay, c.maxAckDelay)
   282  	}
   283  	// Reset the PTO backoff.
   284  	// Exception: A client does not reset the backoff on acks for Initial packets.
   285  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-9
   286  	if !(c.side == clientSide && space == initialSpace) {
   287  		c.ptoBackoffCount = 0
   288  	}
   289  	// If the client has set a PTO timer with no packets in flight
   290  	// we want to restart that timer now. Clearing c.timer does this.
   291  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.2.1-3
   292  	c.timer = time.Time{}
   293  	c.detectLoss(now, lossf)
   294  	c.cc.packetBatchEnd(now, log, space, &c.rtt, c.maxAckDelay)
   295  
   296  	if logEnabled(log, QLogLevelPacket) {
   297  		var ssthresh slog.Attr
   298  		if c.cc.slowStartThreshold != math.MaxInt {
   299  			ssthresh = slog.Int("ssthresh", c.cc.slowStartThreshold)
   300  		}
   301  		log.LogAttrs(context.Background(), QLogLevelPacket,
   302  			"recovery:metrics_updated",
   303  			slog.Duration("min_rtt", c.rtt.minRTT),
   304  			slog.Duration("smoothed_rtt", c.rtt.smoothedRTT),
   305  			slog.Duration("latest_rtt", c.rtt.latestRTT),
   306  			slog.Duration("rtt_variance", c.rtt.rttvar),
   307  			slog.Int("congestion_window", c.cc.congestionWindow),
   308  			slog.Int("bytes_in_flight", c.cc.bytesInFlight),
   309  			ssthresh,
   310  		)
   311  	}
   312  }
   313  
   314  // discardPackets declares that packets within a number space will not be delivered
   315  // and that data contained in them should be resent.
   316  // For example, after receiving a Retry packet we discard already-sent Initial packets.
   317  func (c *lossState) discardPackets(space numberSpace, log *slog.Logger, lossf func(numberSpace, *sentPacket, packetFate)) {
   318  	for i := 0; i < c.spaces[space].size; i++ {
   319  		sent := c.spaces[space].nth(i)
   320  		sent.lost = true
   321  		c.cc.packetDiscarded(sent)
   322  		lossf(numberSpace(space), sent, packetLost)
   323  	}
   324  	c.spaces[space].clean()
   325  	if logEnabled(log, QLogLevelPacket) {
   326  		logBytesInFlight(log, c.cc.bytesInFlight)
   327  	}
   328  }
   329  
   330  // discardKeys is called when dropping packet protection keys for a number space.
   331  func (c *lossState) discardKeys(now time.Time, log *slog.Logger, space numberSpace) {
   332  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.4
   333  	for i := 0; i < c.spaces[space].size; i++ {
   334  		sent := c.spaces[space].nth(i)
   335  		c.cc.packetDiscarded(sent)
   336  	}
   337  	c.spaces[space].discard()
   338  	c.spaces[space].maxAcked = -1
   339  	c.spaces[space].lastAckEliciting = -1
   340  	c.scheduleTimer(now)
   341  	if logEnabled(log, QLogLevelPacket) {
   342  		logBytesInFlight(log, c.cc.bytesInFlight)
   343  	}
   344  }
   345  
   346  func (c *lossState) lossDuration() time.Duration {
   347  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1.2
   348  	return max((9*max(c.rtt.smoothedRTT, c.rtt.latestRTT))/8, timerGranularity)
   349  }
   350  
   351  func (c *lossState) detectLoss(now time.Time, lossf func(numberSpace, *sentPacket, packetFate)) {
   352  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1.1-1
   353  	const lossThreshold = 3
   354  
   355  	lossTime := now.Add(-c.lossDuration())
   356  	for space := numberSpace(0); space < numberSpaceCount; space++ {
   357  		for i := 0; i < c.spaces[space].size; i++ {
   358  			sent := c.spaces[space].nth(i)
   359  			if sent.lost || sent.acked {
   360  				continue
   361  			}
   362  			// RFC 9002 Section 6.1 states that a packet is only declared lost if it
   363  			// is "in flight", which excludes packets that contain only ACK frames.
   364  			// However, we need some way to determine when to drop state for ACK-only
   365  			// packets, and the loss algorithm in Appendix A handles loss detection of
   366  			// not-in-flight packets identically to all others, so we do the same here.
   367  			switch {
   368  			case c.spaces[space].maxAcked-sent.num >= lossThreshold:
   369  				// Packet threshold
   370  				// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1.1
   371  				fallthrough
   372  			case sent.num <= c.spaces[space].maxAcked && !sent.time.After(lossTime):
   373  				// Time threshold
   374  				// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1.2
   375  				sent.lost = true
   376  				lossf(space, sent, packetLost)
   377  				if sent.inFlight {
   378  					c.cc.packetLost(now, space, sent, &c.rtt)
   379  				}
   380  			}
   381  			if !sent.lost {
   382  				break
   383  			}
   384  		}
   385  		c.spaces[space].clean()
   386  	}
   387  	c.scheduleTimer(now)
   388  }
   389  
   390  // scheduleTimer sets the loss or PTO timer.
   391  //
   392  // The connection is responsible for arranging for advance to be called after
   393  // the timer expires.
   394  //
   395  // The timer may be set to a point in the past, in which advance should be called
   396  // immediately. We don't do this here, because executing the timer can cause
   397  // packet loss events, and it's simpler for the connection if loss events only
   398  // occur when advancing time.
   399  func (c *lossState) scheduleTimer(now time.Time) {
   400  	c.ptoTimerArmed = false
   401  
   402  	// Loss timer for sent packets.
   403  	// The loss timer is only started once a later packet has been acknowledged,
   404  	// and takes precedence over the PTO timer.
   405  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.1.2
   406  	var oldestPotentiallyLost time.Time
   407  	for space := numberSpace(0); space < numberSpaceCount; space++ {
   408  		if c.spaces[space].size > 0 && c.spaces[space].start() <= c.spaces[space].maxAcked {
   409  			firstTime := c.spaces[space].nth(0).time
   410  			if oldestPotentiallyLost.IsZero() || firstTime.Before(oldestPotentiallyLost) {
   411  				oldestPotentiallyLost = firstTime
   412  			}
   413  		}
   414  	}
   415  	if !oldestPotentiallyLost.IsZero() {
   416  		c.timer = oldestPotentiallyLost.Add(c.lossDuration())
   417  		return
   418  	}
   419  
   420  	// PTO timer.
   421  	if c.ptoExpired {
   422  		// PTO timer has expired, don't restart it until we send a probe.
   423  		c.timer = time.Time{}
   424  		return
   425  	}
   426  	if c.antiAmplificationLimit >= 0 && c.antiAmplificationLimit < minPacketSize {
   427  		// Server is at its anti-amplification limit and can't send any more data.
   428  		// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.2.1-1
   429  		c.timer = time.Time{}
   430  		return
   431  	}
   432  	// Timer starts at the most recently sent ack-eliciting packet.
   433  	// Prior to confirming the handshake, we consider the Initial and Handshake
   434  	// number spaces; after, we consider only Application Data.
   435  	var last time.Time
   436  	if !c.handshakeConfirmed {
   437  		for space := initialSpace; space <= handshakeSpace; space++ {
   438  			sent := c.spaces[space].num(c.spaces[space].lastAckEliciting)
   439  			if sent == nil {
   440  				continue
   441  			}
   442  			if last.IsZero() || last.After(sent.time) {
   443  				last = sent.time
   444  			}
   445  		}
   446  	} else {
   447  		sent := c.spaces[appDataSpace].num(c.spaces[appDataSpace].lastAckEliciting)
   448  		if sent != nil {
   449  			last = sent.time
   450  		}
   451  	}
   452  	if last.IsZero() &&
   453  		c.side == clientSide &&
   454  		c.spaces[handshakeSpace].maxAcked < 0 &&
   455  		!c.handshakeConfirmed {
   456  		// The client must always set a PTO timer prior to receiving an ack for a
   457  		// handshake packet or the handshake being confirmed.
   458  		// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.2.1
   459  		if !c.timer.IsZero() {
   460  			// If c.timer is non-zero here, we've already set the PTO timer and
   461  			// should leave it as-is rather than moving it forward.
   462  			c.ptoTimerArmed = true
   463  			return
   464  		}
   465  		last = now
   466  	} else if last.IsZero() {
   467  		c.timer = time.Time{}
   468  		return
   469  	}
   470  	c.timer = last.Add(c.ptoPeriod())
   471  	c.ptoTimerArmed = true
   472  }
   473  
   474  func (c *lossState) ptoPeriod() time.Duration {
   475  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1
   476  	return c.ptoBasePeriod() << c.ptoBackoffCount
   477  }
   478  
   479  func (c *lossState) ptoBasePeriod() time.Duration {
   480  	// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1
   481  	pto := c.rtt.smoothedRTT + max(4*c.rtt.rttvar, timerGranularity)
   482  	if c.handshakeConfirmed {
   483  		// The max_ack_delay is the maximum amount of time the peer might delay sending
   484  		// an ack to us. We only take it into account for the Application Data space.
   485  		// https://www.rfc-editor.org/rfc/rfc9002.html#section-6.2.1-4
   486  		pto += c.maxAckDelay
   487  	}
   488  	return pto
   489  }
   490  
   491  func logBytesInFlight(log *slog.Logger, bytesInFlight int) {
   492  	log.LogAttrs(context.Background(), QLogLevelPacket,
   493  		"recovery:metrics_updated",
   494  		slog.Int("bytes_in_flight", bytesInFlight),
   495  	)
   496  }
   497
View as plain text