func (s *lossRecovery) filterSent(space packetSpace, filter func(*sentPacket) bool) {
	sent := s.sent[space]
	if len(sent) > 0 {
		n := 0
		for _, p := range sent {
			if !filter(p) {
				sent[n] = p
				n++
			}
		}
		for i := n; i < len(sent); i++ {
			sent[i] = nil
		}
		s.sent[space] = sent[:n]
	}
}
filterSent removes packet from sent[space] when the filter function returns true.
package transport
import (
	"bytes"
	"fmt"
	"sync"
	"time"
)
const (
	packetThreshold = 3
	timeThreshold = 8
	granularity = 1 * time.Millisecond
	initialRTT = 333 * time.Millisecond
	persistentCongestionThreshold = 3
	maxProbes = 2
	maxAmplificationFactor = 3
	maxUint64 = ^uint64(0)
	maxUint   = ^uint(0)
)
type sentPacket struct {
	packetNumber uint64     
	frames       []frame    
	timeSent     time.Time  
	timeLost     time.Time  
	sentBytes    uint       
	ackEliciting bool
	inFlight bool
}
func newSentPacket(pn uint64, tm time.Time) *sentPacket {
	s := sentPacketPool.Get().(*sentPacket)
	s.packetNumber = pn
	s.timeSent = tm
	return s
}
func (s *sentPacket) addFrame(f frame) {
	s.frames = append(s.frames, f)
	if !s.ackEliciting {
		switch f.(type) {
		case *ackFrame, *connectionCloseFrame:
		case *paddingFrame:
			s.inFlight = true
		default:
			s.inFlight = true
			s.ackEliciting = true
		}
	}
}
func (s *sentPacket) markLost(now time.Time) *sentPacket {
	s.timeLost = now
	sp := newSentPacket(s.packetNumber, s.timeSent)
	sp.inFlight = s.inFlight
	sp.ackEliciting = s.ackEliciting
	sp.sentBytes = s.sentBytes
	sp.timeLost = s.timeLost
	sp.frames, s.frames = s.frames, sp.frames
	return sp
}
func (s *sentPacket) String() string {
	var buf bytes.Buffer
	fmt.Fprintf(&buf, "packet_number=%d sent_bytes=%d ack_eliciting=%v in_flight=%v",
		s.packetNumber, s.sentBytes, s.ackEliciting, s.inFlight)
	if !s.timeLost.IsZero() {
		fmt.Fprintf(&buf, " lost_time=%v", s.timeLost)
	}
	for _, f := range s.frames {
		fmt.Fprintf(&buf, " %s", f)
	}
	return buf.String()
}
func freeSentPacket(s *sentPacket) {
	frames := s.frames
	for i, f := range frames {
		freeFrame(f)
		frames[i] = nil
	}
	*s = sentPacket{}
	s.frames = frames[:0]
	sentPacketPool.Put(s)
}
var sentPacketPool = sync.Pool{
	New: func() interface{} {
		return &sentPacket{}
	},
}
type lossRecovery struct {
	latestRTT   time.Duration  
	smoothedRTT time.Duration  
	rttVariance time.Duration  
	minRTT      time.Duration  
	maxAckDelay time.Duration
	lossDetectionTimer time.Time
	ptoCount uint8
	timeOfLastAckElicitingPacket [packetSpaceCount]time.Time
	largestAckedPacket [packetSpaceCount]uint64
	largestSentPacket [packetSpaceCount]uint64
	lossTime   [packetSpaceCount]time.Time
	lossProbes [packetSpaceCount]uint8
	sent  [packetSpaceCount][]*sentPacket
	lost  [packetSpaceCount][]*sentPacket
	acked [packetSpaceCount][]*sentPacket
	lastPacketSchedule time.Time
	lostPackets uint64
	lostBytes   uint64
	hasHandshakeKeys               bool
	peerCompletedAddressValidation bool
	handshakeConfirmed             bool
	enablePacing                   bool
	congestion congestionControl
}
func (s *lossRecovery) init() {
	for i := packetSpaceInitial; i < packetSpaceCount; i++ {
		s.largestAckedPacket[i] = maxUint64
	}
	s.rttVariance = initialRTT / 2
	s.congestion.init()
}
func (s *lossRecovery) onPacketSent(p *sentPacket, space packetSpace) {
	s.setPacketSchedule(p, space)
	s.sent[space] = append(s.sent[space], p)
	if p.packetNumber > s.largestSentPacket[space] {
		s.largestSentPacket[space] = p.packetNumber
	}
	if p.inFlight {
		if p.ackEliciting {
			s.timeOfLastAckElicitingPacket[space] = p.timeSent
		}
		s.congestion.onPacketSent(p.sentBytes, p.timeSent)
		s.setLossDetectionTimer(p.timeSent)
	}
}
func (s *lossRecovery) onAckReceived(ranges rangeSet, ackDelay time.Duration, space packetSpace, now time.Time) {
	largestAcked := ranges.largest()
	if largestAcked > s.largestSentPacket[space] {
		debug("invalid largest acknowledged packet number: largestAcked=%v largestSent=%v %v",
			largestAcked, s.largestSentPacket[space], ranges)
		return
	}
	if s.largestAckedPacket[space] == maxUint64 || s.largestAckedPacket[space] < largestAcked {
		s.largestAckedPacket[space] = largestAcked
	}
	ackedLen := len(s.acked[space])
	hasAckEliciting := false
	hasSpurious := false
	s.filterSent(space, func(p *sentPacket) bool {
		if ranges.contains(p.packetNumber) {
			if p.ackEliciting {
				hasAckEliciting = true
			}
			if p.inFlight && !p.timeLost.IsZero() {
				hasSpurious = true
				debug("spurious lost packet: %v", p)
			}
			s.acked[space] = append(s.acked[space], p)
			return true
		}
		return false
	})
	ackedPackets := s.acked[space][ackedLen:]
	if len(ackedPackets) == 0 {
		return
	}
	if hasSpurious {
		s.congestion.rollback()
	}
	if hasAckEliciting {
		largestPacket := ackedPackets[len(ackedPackets)-1]
		if largestPacket.packetNumber == largestAcked {
			latestRTT := now.Sub(largestPacket.timeSent)
			if space != packetSpaceApplication {
				ackDelay = 0
			}
			s.updateRTT(latestRTT, ackDelay)
		}
	}
	s.onPacketsAcked(ackedPackets, space, now)
	s.detectLostPackets(space, now)
	if s.ptoCount > 0 && s.peerCompletedAddressValidation {
		s.ptoCount = 0
		s.lossProbes[space] = 0
	}
	s.setLossDetectionTimer(now)
}
func (s *lossRecovery) updateRTT(latestRTT time.Duration, ackDelay time.Duration) {
	s.latestRTT = latestRTT
	if s.smoothedRTT == 0 {
		s.minRTT = latestRTT
		s.smoothedRTT = latestRTT
		s.rttVariance = latestRTT / 2
		return
	}
	if s.minRTT > latestRTT {
		s.minRTT = latestRTT
	}
	if s.handshakeConfirmed && ackDelay > s.maxAckDelay {
		ackDelay = s.maxAckDelay
	}
	adjustedRTT := latestRTT
	if adjustedRTT >= s.minRTT+ackDelay {
		adjustedRTT -= ackDelay
	}
	deltaRTT := s.smoothedRTT - adjustedRTT
	if deltaRTT < 0 {
		deltaRTT = -deltaRTT
	}
	s.rttVariance = s.rttVariance*3/4 + deltaRTT*1/4
	s.smoothedRTT = s.smoothedRTT*7/8 + adjustedRTT*1/8
}
func (s *lossRecovery) onPacketsAcked(packets []*sentPacket, space packetSpace, now time.Time) {
	rtt := s.roundTripTime()
	for _, p := range packets {
		if p.inFlight {
			s.congestion.onPacketAcked(p.sentBytes, p.timeSent, rtt, now)
		}
	}
}
func (s *lossRecovery) setLossDetectionTimer(now time.Time) {
	lossTime, _ := s.earliestLossTime()
	if !lossTime.IsZero() {
		s.lossDetectionTimer = lossTime
		return
	}
	if s.congestion.state.bytesInFlight == 0 && s.peerCompletedAddressValidation {
		s.lossDetectionTimer = time.Time{}
		return
	}
	timeout, _ := s.earliestProbeTime(now)
	s.lossDetectionTimer = timeout
	debug("set loss_timer=%v", timeout)
}
func (s *lossRecovery) onLossDetectionTimeout(now time.Time) {
	lossTime, space := s.earliestLossTime()
	if !lossTime.IsZero() {
		s.detectLostPackets(space, now)
		s.setLossDetectionTimer(now)
		return
	}
	s.ptoCount++
	probes := int(s.ptoCount)
	if probes > maxProbes {
		probes = maxProbes
	}
	_, space = s.earliestProbeTime(now)
	s.lossProbes[space] = uint8(probes)
	s.markResendAckElicitingPackets(space, probes, now)
	s.setLossDetectionTimer(now)
}
func (s *lossRecovery) detectLostPackets(space packetSpace, now time.Time) {
	lossDelay := s.roundTripTime()
	if lossDelay < s.latestRTT {
		lossDelay = s.latestRTT
	}
	lossDelay += lossDelay / timeThreshold
	if lossDelay < granularity {
		lossDelay = granularity
	}
	lostSendTime := now.Add(-lossDelay)
	largestAcked := s.largestAckedPacket[space]
	lossTime := time.Time{}
	lostLen := len(s.lost[space])
	s.filterSent(space, func(p *sentPacket) bool {
		if p.packetNumber > largestAcked {
			return false
		}
		if !p.timeLost.IsZero() {
			if p.timeLost.Before(lostSendTime) {
				freeSentPacket(p)
				return true
			}
			return false
		}
		if !p.timeSent.After(lostSendTime) || largestAcked >= p.packetNumber+packetThreshold {
			sp := p.markLost(now)
			s.lost[space] = append(s.lost[space], sp)
			return false
		}
		if p.ackEliciting {
			tm := p.timeSent.Add(lossDelay)
			if lossTime.IsZero() || lossTime.After(tm) {
				lossTime = tm
			}
		}
		return false
	})
	s.lossTime[space] = lossTime
	lostPackets := s.lost[space][lostLen:]
	if len(lostPackets) > 0 {
		s.onPacketsLost(lostPackets, space, now)
	}
}
func (s *lossRecovery) markResendAckElicitingPackets(space packetSpace, probes int, now time.Time) {
	sent := s.sent[space]
	for _, p := range sent {
		if p.ackEliciting && len(p.frames) > 0 {
			debug("mark packet lost for resending: %v", p)
			sp := p.markLost(now)
			s.lost[space] = append(s.lost[space], sp)
			probes--
			if probes == 0 {
				break
			}
		}
	}
}
func (s *lossRecovery) onPacketNumberSpaceDiscarded(space packetSpace, now time.Time) {
	var unackedBytes uint
	for _, p := range s.sent[space] {
		if p.inFlight {
			unackedBytes += p.sentBytes
		}
	}
	s.congestion.onPacketDiscarded(unackedBytes)
	s.sent[space] = nil
	s.lost[space] = nil
	s.acked[space] = nil
	s.timeOfLastAckElicitingPacket[space] = time.Time{}
	s.lossTime[space] = time.Time{}
	s.lossProbes[space] = 0
	s.ptoCount = 0
	s.setLossDetectionTimer(now)
}
func (s *lossRecovery) roundTripTime() time.Duration {
	if s.smoothedRTT > 0 {
		return s.smoothedRTT
	}
	return initialRTT
}
func (s *lossRecovery) probeTimeout() time.Duration {
	pto := s.roundTripTime() + s.maxAckDelay
	if s.rttVariance*4 > granularity {
		pto += s.rttVariance * 4
	} else {
		pto += granularity
	}
	return pto
}
func (s *lossRecovery) earliestLossTime() (time.Time, packetSpace) {
	space := packetSpaceInitial
	lossTime := s.lossTime[space]
	for i := space + 1; i < packetSpaceCount; i++ {
		tm := s.lossTime[i]
		if !tm.IsZero() && (lossTime.IsZero() || lossTime.After(tm)) {
			lossTime = tm
			space = i
		}
	}
	return lossTime, space
}
func (s *lossRecovery) earliestProbeTime(now time.Time) (time.Time, packetSpace) {
	duration := s.probeTimeout() * (1 << s.ptoCount)
	if s.congestion.state.bytesInFlight == 0 {
		if s.hasHandshakeKeys {
			return now.Add(duration), packetSpaceHandshake
		}
		return now.Add(duration), packetSpaceInitial
	}
	space := packetSpaceInitial
	timeout := time.Time{}
	for i := space; i < packetSpaceCount; i++ {
		if len(s.sent[i]) == 0 {
			continue
		}
		if space == packetSpaceApplication && !s.handshakeConfirmed {
			continue
		}
		tm := s.timeOfLastAckElicitingPacket[i]
		if !tm.IsZero() {
			tm = tm.Add(duration)
			if timeout.IsZero() || timeout.After(tm) {
				timeout = tm
				space = i
			}
		}
	}
	return timeout, space
}
func (s *lossRecovery) inPersistentCongestion(lostPackets []*sentPacket) bool {
	return false
}
func (s *lossRecovery) onPacketsLost(packets []*sentPacket, space packetSpace, now time.Time) {
	s.lostPackets += uint64(len(packets))
	sentTimeOfLastLoss := time.Time{}
	for _, p := range packets {
		debug("lost packet: %v", p)
		if p.inFlight {
			s.congestion.onPacketDiscarded(p.sentBytes)
			s.lostBytes += uint64(p.sentBytes)
			if sentTimeOfLastLoss.IsZero() || p.timeSent.After(sentTimeOfLastLoss) {
				sentTimeOfLastLoss = p.timeSent
			}
		}
	}
	if len(packets) > 1 && !sentTimeOfLastLoss.IsZero() {
		s.congestion.onCongestionEvent(sentTimeOfLastLoss, now)
	}
	if s.smoothedRTT == 0 {
		return
	}
	if s.inPersistentCongestion(packets) {
		s.congestion.collapseWindow()
	}
}