sent_packet_list.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  // A sentPacketList is a ring buffer of sentPackets.
     8  //
     9  // Processing an ack for a packet causes all older packets past a small threshold
    10  // to be discarded (RFC 9002, Section 6.1.1), so the list of in-flight packets is
    11  // not sparse and will contain at most a few acked/lost packets we no longer
    12  // care about.
    13  type sentPacketList struct {
    14  	nextNum packetNumber // next packet number to add to the buffer
    15  	off     int          // offset of first packet in the buffer
    16  	size    int          // number of packets
    17  	p       []*sentPacket
    18  }
    19  
    20  // start is the first packet in the list.
    21  func (s *sentPacketList) start() packetNumber {
    22  	return s.nextNum - packetNumber(s.size)
    23  }
    24  
    25  // end is one after the last packet in the list.
    26  // If the list is empty, start == end.
    27  func (s *sentPacketList) end() packetNumber {
    28  	return s.nextNum
    29  }
    30  
    31  // discard clears the list.
    32  func (s *sentPacketList) discard() {
    33  	*s = sentPacketList{}
    34  }
    35  
    36  // add appends a packet to the list.
    37  func (s *sentPacketList) add(sent *sentPacket) {
    38  	if s.nextNum != sent.num {
    39  		panic("inserting out-of-order packet")
    40  	}
    41  	s.nextNum++
    42  	if s.size >= len(s.p) {
    43  		s.grow()
    44  	}
    45  	i := (s.off + s.size) % len(s.p)
    46  	s.size++
    47  	s.p[i] = sent
    48  }
    49  
    50  // nth returns a packet by index.
    51  func (s *sentPacketList) nth(n int) *sentPacket {
    52  	index := (s.off + n) % len(s.p)
    53  	return s.p[index]
    54  }
    55  
    56  // num returns a packet by number.
    57  // It returns nil if the packet is not in the list.
    58  func (s *sentPacketList) num(num packetNumber) *sentPacket {
    59  	i := int(num - s.start())
    60  	if i < 0 || i >= s.size {
    61  		return nil
    62  	}
    63  	return s.nth(i)
    64  }
    65  
    66  // clean removes all acked or lost packets from the head of the list.
    67  func (s *sentPacketList) clean() {
    68  	for s.size > 0 {
    69  		sent := s.p[s.off]
    70  		if sent.state == sentPacketSent {
    71  			return
    72  		}
    73  		sent.recycle()
    74  		s.p[s.off] = nil
    75  		s.off = (s.off + 1) % len(s.p)
    76  		s.size--
    77  	}
    78  	s.off = 0
    79  }
    80  
    81  // grow increases the buffer to hold more packaets.
    82  func (s *sentPacketList) grow() {
    83  	newSize := len(s.p) * 2
    84  	if newSize == 0 {
    85  		newSize = 64
    86  	}
    87  	p := make([]*sentPacket, newSize)
    88  	for i := 0; i < s.size; i++ {
    89  		p[i] = s.nth(i)
    90  	}
    91  	s.p = p
    92  	s.off = 0
    93  }
    94
View as plain text