blob: 039b7b46e60050df7a2dad9750450662fc2fbac6 [file] [log] [blame]
// 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.
//go:build go1.21
package quic
import (
// ackState tracks packets received from a peer within a number space.
// It handles packet deduplication (don't process the same packet twice) and
// determines the timing and content of ACK frames.
type ackState struct {
seen rangeset[packetNumber]
// The time at which we must send an ACK frame, even if we have no other data to send.
nextAck time.Time
// The time we received the largest-numbered packet in seen.
maxRecvTime time.Time
// The largest-numbered ack-eliciting packet in seen.
maxAckEliciting packetNumber
// The number of ack-eliciting packets in seen that we have not yet acknowledged.
unackedAckEliciting int
// shouldProcess reports whether a packet should be handled or discarded.
func (acks *ackState) shouldProcess(num packetNumber) bool {
if packetNumber(acks.seen.min()) > num {
// We've discarded the state for this range of packet numbers.
// Discard the packet rather than potentially processing a duplicate.
return false
if acks.seen.contains(num) {
// Discard duplicate packets.
return false
return true
// receive records receipt of a packet.
func (acks *ackState) receive(now time.Time, space numberSpace, num packetNumber, ackEliciting bool) {
if ackEliciting {
if acks.mustAckImmediately(space, num) {
acks.nextAck = now
} else if acks.nextAck.IsZero() {
// This packet does not need to be acknowledged immediately,
// but the ack must not be intentionally delayed by more than
// the max_ack_delay transport parameter we sent to the peer.
// We always delay acks by the maximum allowed, less the timer
// granularity. ("[max_ack_delay] SHOULD include the receiver's
// expected delays in alarms firing.")
acks.nextAck = now.Add(maxAckDelay - timerGranularity)
if num > acks.maxAckEliciting {
acks.maxAckEliciting = num
acks.seen.add(num, num+1)
if num == acks.seen.max() {
acks.maxRecvTime = now
// Limit the total number of ACK ranges by dropping older ranges.
// Remembering more ranges results in larger ACK frames.
// Remembering a large number of ranges could result in ACK frames becoming
// too large to fit in a packet, in which case we will silently drop older
// ranges during packet construction.
// Remembering fewer ranges can result in unnecessary retransmissions,
// since we cannot accept packets older than the oldest remembered range.
// The limit here is completely arbitrary. If it seems wrong, it probably is.
const maxAckRanges = 8
if overflow := acks.seen.numRanges() - maxAckRanges; overflow > 0 {
acks.seen.removeranges(0, overflow)
// mustAckImmediately reports whether an ack-eliciting packet must be acknowledged immediately,
// or whether the ack may be deferred.
func (acks *ackState) mustAckImmediately(space numberSpace, num packetNumber) bool {
if space != appDataSpace {
// "[...] all ack-eliciting Initial and Handshake packets [...]"
return true
if num < acks.maxAckEliciting {
// "[...] when the received packet has a packet number less than another
// ack-eliciting packet that has been received [...]"
return true
if acks.seen.rangeContaining(acks.maxAckEliciting).end != num {
// "[...] when the packet has a packet number larger than the highest-numbered
// ack-eliciting packet that has been received and there are missing packets
// between that packet and this packet."
// This case is a bit tricky. Let's say we've received:
// 0, ack-eliciting
// 1, ack-eliciting
// 3, NOT ack eliciting
// We have sent ACKs for 0 and 1. If we receive ack-eliciting packet 2,
// we do not need to send an immediate ACK, because there are no missing
// packets between it and the highest-numbered ack-eliciting packet (1).
// If we receive ack-eliciting packet 4, we do need to send an immediate ACK,
// because there's a gap (the missing packet 2).
// We check for this by looking up the ACK range which contains the
// highest-numbered ack-eliciting packet: [0, 1) in the above example.
// If the range ends just before the packet we are now processing,
// there are no gaps. If it does not, there must be a gap.
return true
// "[...] SHOULD send an ACK frame after receiving at least two ack-eliciting packets."
// This ack frequency takes a substantial toll on performance, however.
// Follow the behavior of Google QUICHE:
// Ack every other packet for the first 100 packets, and then ack every 10th packet.
// This keeps ack frequency high during the beginning of slow start when CWND is
// increasing rapidly.
packetsBeforeAck := 2
if acks.seen.max() > 100 {
packetsBeforeAck = 10
return acks.unackedAckEliciting >= packetsBeforeAck
// shouldSendAck reports whether the connection should send an ACK frame at this time,
// in an ACK-only packet if necessary.
func (acks *ackState) shouldSendAck(now time.Time) bool {
return !acks.nextAck.IsZero() && !acks.nextAck.After(now)
// acksToSend returns the set of packet numbers to ACK at this time, and the current ack delay.
// It may return acks even if shouldSendAck returns false, when there are unacked
// ack-eliciting packets whose ack is being delayed.
func (acks *ackState) acksToSend(now time.Time) (nums rangeset[packetNumber], ackDelay time.Duration) {
if acks.nextAck.IsZero() && acks.unackedAckEliciting == 0 {
return nil, 0
// "[...] the delays intentionally introduced between the time the packet with the
// largest packet number is received and the time an acknowledgement is sent."
delay := now.Sub(acks.maxRecvTime)
if delay < 0 {
delay = 0
return acks.seen, delay
// sentAck records that an ACK frame has been sent.
func (acks *ackState) sentAck() {
acks.nextAck = time.Time{}
acks.unackedAckEliciting = 0
// handleAck records that an ack has been received for a ACK frame we sent
// containing the given Largest Acknowledged field.
func (acks *ackState) handleAck(largestAcked packetNumber) {
// We can stop acking packets less or equal to largestAcked.
// We rely on acks.seen containing the largest packet number that has been successfully
// processed, so we retain the range containing largestAcked and discard previous ones.
acks.seen.sub(0, acks.seen.rangeContaining(largestAcked).start)
// largestSeen reports the largest seen packet.
func (acks *ackState) largestSeen() packetNumber {
return acks.seen.max()