acks.go

     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  package quic
     6  
     7  import (
     8  	"time"
     9  )
    10  
    11  // ackState tracks packets received from a peer within a number space.
    12  // It handles packet deduplication (don't process the same packet twice) and
    13  // determines the timing and content of ACK frames.
    14  type ackState struct {
    15  	seen rangeset[packetNumber]
    16  
    17  	// The time at which we must send an ACK frame, even if we have no other data to send.
    18  	nextAck time.Time
    19  
    20  	// The time we received the largest-numbered packet in seen.
    21  	maxRecvTime time.Time
    22  
    23  	// The largest-numbered ack-eliciting packet in seen.
    24  	maxAckEliciting packetNumber
    25  
    26  	// The number of ack-eliciting packets in seen that we have not yet acknowledged.
    27  	unackedAckEliciting int
    28  
    29  	// Total ECN counters for this packet number space.
    30  	ecn ecnCounts
    31  }
    32  
    33  type ecnCounts struct {
    34  	t0 int
    35  	t1 int
    36  	ce int
    37  }
    38  
    39  // shouldProcess reports whether a packet should be handled or discarded.
    40  func (acks *ackState) shouldProcess(num packetNumber) bool {
    41  	if packetNumber(acks.seen.min()) > num {
    42  		// We've discarded the state for this range of packet numbers.
    43  		// Discard the packet rather than potentially processing a duplicate.
    44  		// https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.3-5
    45  		return false
    46  	}
    47  	if acks.seen.contains(num) {
    48  		// Discard duplicate packets.
    49  		return false
    50  	}
    51  	return true
    52  }
    53  
    54  // receive records receipt of a packet.
    55  func (acks *ackState) receive(now time.Time, space numberSpace, num packetNumber, ackEliciting bool, ecn ecnBits) {
    56  	if ackEliciting {
    57  		acks.unackedAckEliciting++
    58  		if acks.mustAckImmediately(space, num, ecn) {
    59  			acks.nextAck = now
    60  		} else if acks.nextAck.IsZero() {
    61  			// This packet does not need to be acknowledged immediately,
    62  			// but the ack must not be intentionally delayed by more than
    63  			// the max_ack_delay transport parameter we sent to the peer.
    64  			//
    65  			// We always delay acks by the maximum allowed, less the timer
    66  			// granularity. ("[max_ack_delay] SHOULD include the receiver's
    67  			// expected delays in alarms firing.")
    68  			//
    69  			// https://www.rfc-editor.org/rfc/rfc9000#section-18.2-4.28.1
    70  			acks.nextAck = now.Add(maxAckDelay - timerGranularity)
    71  		}
    72  		if num > acks.maxAckEliciting {
    73  			acks.maxAckEliciting = num
    74  		}
    75  	}
    76  
    77  	acks.seen.add(num, num+1)
    78  	if num == acks.seen.max() {
    79  		acks.maxRecvTime = now
    80  	}
    81  
    82  	switch ecn {
    83  	case ecnECT0:
    84  		acks.ecn.t0++
    85  	case ecnECT1:
    86  		acks.ecn.t1++
    87  	case ecnCE:
    88  		acks.ecn.ce++
    89  	}
    90  
    91  	// Limit the total number of ACK ranges by dropping older ranges.
    92  	//
    93  	// Remembering more ranges results in larger ACK frames.
    94  	//
    95  	// Remembering a large number of ranges could result in ACK frames becoming
    96  	// too large to fit in a packet, in which case we will silently drop older
    97  	// ranges during packet construction.
    98  	//
    99  	// Remembering fewer ranges can result in unnecessary retransmissions,
   100  	// since we cannot accept packets older than the oldest remembered range.
   101  	//
   102  	// The limit here is completely arbitrary. If it seems wrong, it probably is.
   103  	//
   104  	// https://www.rfc-editor.org/rfc/rfc9000#section-13.2.3
   105  	const maxAckRanges = 8
   106  	if overflow := acks.seen.numRanges() - maxAckRanges; overflow > 0 {
   107  		acks.seen.removeranges(0, overflow)
   108  	}
   109  }
   110  
   111  // mustAckImmediately reports whether an ack-eliciting packet must be acknowledged immediately,
   112  // or whether the ack may be deferred.
   113  func (acks *ackState) mustAckImmediately(space numberSpace, num packetNumber, ecn ecnBits) bool {
   114  	// https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.1
   115  	if space != appDataSpace {
   116  		// "[...] all ack-eliciting Initial and Handshake packets [...]"
   117  		// https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.1-2
   118  		return true
   119  	}
   120  	if num < acks.maxAckEliciting {
   121  		// "[...] when the received packet has a packet number less than another
   122  		// ack-eliciting packet that has been received [...]"
   123  		// https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.1-8.1
   124  		return true
   125  	}
   126  	if acks.seen.rangeContaining(acks.maxAckEliciting).end != num {
   127  		// "[...] when the packet has a packet number larger than the highest-numbered
   128  		// ack-eliciting packet that has been received and there are missing packets
   129  		// between that packet and this packet."
   130  		// https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.1-8.2
   131  		//
   132  		// This case is a bit tricky. Let's say we've received:
   133  		//   0, ack-eliciting
   134  		//   1, ack-eliciting
   135  		//   3, NOT ack eliciting
   136  		//
   137  		// We have sent ACKs for 0 and 1. If we receive ack-eliciting packet 2,
   138  		// we do not need to send an immediate ACK, because there are no missing
   139  		// packets between it and the highest-numbered ack-eliciting packet (1).
   140  		// If we receive ack-eliciting packet 4, we do need to send an immediate ACK,
   141  		// because there's a gap (the missing packet 2).
   142  		//
   143  		// We check for this by looking up the ACK range which contains the
   144  		// highest-numbered ack-eliciting packet: [0, 1) in the above example.
   145  		// If the range ends just before the packet we are now processing,
   146  		// there are no gaps. If it does not, there must be a gap.
   147  		return true
   148  	}
   149  	// "[...] packets marked with the ECN Congestion Experienced (CE) codepoint
   150  	// in the IP header SHOULD be acknowledged immediately [...]"
   151  	// https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.1-9
   152  	if ecn == ecnCE {
   153  		return true
   154  	}
   155  	// "[...] SHOULD send an ACK frame after receiving at least two ack-eliciting packets."
   156  	// https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.2
   157  	//
   158  	// This ack frequency takes a substantial toll on performance, however.
   159  	// Follow the behavior of Google QUICHE:
   160  	// Ack every other packet for the first 100 packets, and then ack every 10th packet.
   161  	// This keeps ack frequency high during the beginning of slow start when CWND is
   162  	// increasing rapidly.
   163  	packetsBeforeAck := 2
   164  	if acks.seen.max() > 100 {
   165  		packetsBeforeAck = 10
   166  	}
   167  	return acks.unackedAckEliciting >= packetsBeforeAck
   168  }
   169  
   170  // shouldSendAck reports whether the connection should send an ACK frame at this time,
   171  // in an ACK-only packet if necessary.
   172  func (acks *ackState) shouldSendAck(now time.Time) bool {
   173  	return !acks.nextAck.IsZero() && !acks.nextAck.After(now)
   174  }
   175  
   176  // acksToSend returns the set of packet numbers to ACK at this time, and the current ack delay.
   177  // It may return acks even if shouldSendAck returns false, when there are unacked
   178  // ack-eliciting packets whose ack is being delayed.
   179  func (acks *ackState) acksToSend(now time.Time) (nums rangeset[packetNumber], ackDelay time.Duration) {
   180  	if acks.nextAck.IsZero() && acks.unackedAckEliciting == 0 {
   181  		return nil, 0
   182  	}
   183  	// "[...] the delays intentionally introduced between the time the packet with the
   184  	// largest packet number is received and the time an acknowledgement is sent."
   185  	// https://www.rfc-editor.org/rfc/rfc9000#section-13.2.5-1
   186  	delay := now.Sub(acks.maxRecvTime)
   187  	if delay < 0 {
   188  		delay = 0
   189  	}
   190  	return acks.seen, delay
   191  }
   192  
   193  // sentAck records that an ACK frame has been sent.
   194  func (acks *ackState) sentAck() {
   195  	acks.nextAck = time.Time{}
   196  	acks.unackedAckEliciting = 0
   197  }
   198  
   199  // handleAck records that an ack has been received for a ACK frame we sent
   200  // containing the given Largest Acknowledged field.
   201  func (acks *ackState) handleAck(largestAcked packetNumber) {
   202  	// We can stop acking packets less or equal to largestAcked.
   203  	// https://www.rfc-editor.org/rfc/rfc9000.html#section-13.2.4-1
   204  	//
   205  	// We rely on acks.seen containing the largest packet number that has been successfully
   206  	// processed, so we retain the range containing largestAcked and discard previous ones.
   207  	acks.seen.sub(0, acks.seen.rangeContaining(largestAcked).start)
   208  }
   209  
   210  // largestSeen reports the largest seen packet.
   211  func (acks *ackState) largestSeen() packetNumber {
   212  	return acks.seen.max()
   213  }
   214
View as plain text