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