1package ackhandler
2
3import (
4	"github.com/lucas-clemente/quic-go/internal/protocol"
5	"github.com/lucas-clemente/quic-go/internal/utils"
6	"github.com/lucas-clemente/quic-go/internal/wire"
7	. "github.com/onsi/ginkgo"
8	. "github.com/onsi/gomega"
9)
10
11var _ = Describe("receivedPacketHistory", func() {
12	var (
13		hist *receivedPacketHistory
14	)
15
16	BeforeEach(func() {
17		hist = newReceivedPacketHistory()
18	})
19
20	Context("ranges", func() {
21		It("adds the first packet", func() {
22			hist.ReceivedPacket(4)
23			Expect(hist.ranges.Len()).To(Equal(1))
24			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 4}))
25		})
26
27		It("doesn't care about duplicate packets", func() {
28			hist.ReceivedPacket(4)
29			Expect(hist.ranges.Len()).To(Equal(1))
30			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 4}))
31		})
32
33		It("adds a few consecutive packets", func() {
34			hist.ReceivedPacket(4)
35			hist.ReceivedPacket(5)
36			hist.ReceivedPacket(6)
37			Expect(hist.ranges.Len()).To(Equal(1))
38			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 6}))
39		})
40
41		It("doesn't care about a duplicate packet contained in an existing range", func() {
42			hist.ReceivedPacket(4)
43			hist.ReceivedPacket(5)
44			hist.ReceivedPacket(6)
45			hist.ReceivedPacket(5)
46			Expect(hist.ranges.Len()).To(Equal(1))
47			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 6}))
48		})
49
50		It("extends a range at the front", func() {
51			hist.ReceivedPacket(4)
52			hist.ReceivedPacket(3)
53			Expect(hist.ranges.Len()).To(Equal(1))
54			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 3, End: 4}))
55		})
56
57		It("creates a new range when a packet is lost", func() {
58			hist.ReceivedPacket(4)
59			hist.ReceivedPacket(6)
60			Expect(hist.ranges.Len()).To(Equal(2))
61			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 4}))
62			Expect(hist.ranges.Back().Value).To(Equal(utils.PacketInterval{Start: 6, End: 6}))
63		})
64
65		It("creates a new range in between two ranges", func() {
66			hist.ReceivedPacket(4)
67			hist.ReceivedPacket(10)
68			Expect(hist.ranges.Len()).To(Equal(2))
69			hist.ReceivedPacket(7)
70			Expect(hist.ranges.Len()).To(Equal(3))
71			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 4}))
72			Expect(hist.ranges.Front().Next().Value).To(Equal(utils.PacketInterval{Start: 7, End: 7}))
73			Expect(hist.ranges.Back().Value).To(Equal(utils.PacketInterval{Start: 10, End: 10}))
74		})
75
76		It("creates a new range before an existing range for a belated packet", func() {
77			hist.ReceivedPacket(6)
78			hist.ReceivedPacket(4)
79			Expect(hist.ranges.Len()).To(Equal(2))
80			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 4}))
81			Expect(hist.ranges.Back().Value).To(Equal(utils.PacketInterval{Start: 6, End: 6}))
82		})
83
84		It("extends a previous range at the end", func() {
85			hist.ReceivedPacket(4)
86			hist.ReceivedPacket(7)
87			hist.ReceivedPacket(5)
88			Expect(hist.ranges.Len()).To(Equal(2))
89			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 5}))
90			Expect(hist.ranges.Back().Value).To(Equal(utils.PacketInterval{Start: 7, End: 7}))
91		})
92
93		It("extends a range at the front", func() {
94			hist.ReceivedPacket(4)
95			hist.ReceivedPacket(7)
96			hist.ReceivedPacket(6)
97			Expect(hist.ranges.Len()).To(Equal(2))
98			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 4}))
99			Expect(hist.ranges.Back().Value).To(Equal(utils.PacketInterval{Start: 6, End: 7}))
100		})
101
102		It("closes a range", func() {
103			hist.ReceivedPacket(6)
104			hist.ReceivedPacket(4)
105			Expect(hist.ranges.Len()).To(Equal(2))
106			hist.ReceivedPacket(5)
107			Expect(hist.ranges.Len()).To(Equal(1))
108			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 6}))
109		})
110
111		It("closes a range in the middle", func() {
112			hist.ReceivedPacket(1)
113			hist.ReceivedPacket(10)
114			hist.ReceivedPacket(4)
115			hist.ReceivedPacket(6)
116			Expect(hist.ranges.Len()).To(Equal(4))
117			hist.ReceivedPacket(5)
118			Expect(hist.ranges.Len()).To(Equal(3))
119			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 1, End: 1}))
120			Expect(hist.ranges.Front().Next().Value).To(Equal(utils.PacketInterval{Start: 4, End: 6}))
121			Expect(hist.ranges.Back().Value).To(Equal(utils.PacketInterval{Start: 10, End: 10}))
122		})
123	})
124
125	Context("deleting", func() {
126		It("does nothing when the history is empty", func() {
127			hist.DeleteBelow(5)
128			Expect(hist.ranges.Len()).To(BeZero())
129		})
130
131		It("deletes a range", func() {
132			hist.ReceivedPacket(4)
133			hist.ReceivedPacket(5)
134			hist.ReceivedPacket(10)
135			hist.DeleteBelow(6)
136			Expect(hist.ranges.Len()).To(Equal(1))
137			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 10, End: 10}))
138		})
139
140		It("deletes multiple ranges", func() {
141			hist.ReceivedPacket(1)
142			hist.ReceivedPacket(5)
143			hist.ReceivedPacket(10)
144			hist.DeleteBelow(8)
145			Expect(hist.ranges.Len()).To(Equal(1))
146			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 10, End: 10}))
147		})
148
149		It("adjusts a range, if packets are delete from an existing range", func() {
150			hist.ReceivedPacket(3)
151			hist.ReceivedPacket(4)
152			hist.ReceivedPacket(5)
153			hist.ReceivedPacket(6)
154			hist.ReceivedPacket(7)
155			hist.DeleteBelow(5)
156			Expect(hist.ranges.Len()).To(Equal(1))
157			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 5, End: 7}))
158		})
159
160		It("adjusts a range, if only one packet remains in the range", func() {
161			hist.ReceivedPacket(4)
162			hist.ReceivedPacket(5)
163			hist.ReceivedPacket(10)
164			hist.DeleteBelow(5)
165			Expect(hist.ranges.Len()).To(Equal(2))
166			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 5, End: 5}))
167			Expect(hist.ranges.Back().Value).To(Equal(utils.PacketInterval{Start: 10, End: 10}))
168		})
169
170		It("keeps a one-packet range, if deleting up to the packet directly below", func() {
171			hist.ReceivedPacket(4)
172			hist.DeleteBelow(4)
173			Expect(hist.ranges.Len()).To(Equal(1))
174			Expect(hist.ranges.Front().Value).To(Equal(utils.PacketInterval{Start: 4, End: 4}))
175		})
176
177		Context("DoS protection", func() {
178			It("doesn't create more than MaxTrackedReceivedAckRanges ranges", func() {
179				for i := protocol.PacketNumber(1); i <= protocol.MaxTrackedReceivedAckRanges; i++ {
180					err := hist.ReceivedPacket(2 * i)
181					Expect(err).ToNot(HaveOccurred())
182				}
183				err := hist.ReceivedPacket(2*protocol.MaxTrackedReceivedAckRanges + 2)
184				Expect(err).To(MatchError(errTooManyOutstandingReceivedAckRanges))
185			})
186
187			It("doesn't consider already deleted ranges for MaxTrackedReceivedAckRanges", func() {
188				for i := protocol.PacketNumber(1); i <= protocol.MaxTrackedReceivedAckRanges; i++ {
189					err := hist.ReceivedPacket(2 * i)
190					Expect(err).ToNot(HaveOccurred())
191				}
192				err := hist.ReceivedPacket(2*protocol.MaxTrackedReceivedAckRanges + 2)
193				Expect(err).To(MatchError(errTooManyOutstandingReceivedAckRanges))
194				hist.DeleteBelow(protocol.MaxTrackedReceivedAckRanges) // deletes about half of the ranges
195				err = hist.ReceivedPacket(2*protocol.MaxTrackedReceivedAckRanges + 4)
196				Expect(err).ToNot(HaveOccurred())
197			})
198		})
199	})
200
201	Context("ACK range export", func() {
202		It("returns nil if there are no ranges", func() {
203			Expect(hist.GetAckRanges()).To(BeNil())
204		})
205
206		It("gets a single ACK range", func() {
207			hist.ReceivedPacket(4)
208			hist.ReceivedPacket(5)
209			ackRanges := hist.GetAckRanges()
210			Expect(ackRanges).To(HaveLen(1))
211			Expect(ackRanges[0]).To(Equal(wire.AckRange{Smallest: 4, Largest: 5}))
212		})
213
214		It("gets multiple ACK ranges", func() {
215			hist.ReceivedPacket(4)
216			hist.ReceivedPacket(5)
217			hist.ReceivedPacket(6)
218			hist.ReceivedPacket(1)
219			hist.ReceivedPacket(11)
220			hist.ReceivedPacket(10)
221			hist.ReceivedPacket(2)
222			ackRanges := hist.GetAckRanges()
223			Expect(ackRanges).To(HaveLen(3))
224			Expect(ackRanges[0]).To(Equal(wire.AckRange{Smallest: 10, Largest: 11}))
225			Expect(ackRanges[1]).To(Equal(wire.AckRange{Smallest: 4, Largest: 6}))
226			Expect(ackRanges[2]).To(Equal(wire.AckRange{Smallest: 1, Largest: 2}))
227		})
228	})
229
230	Context("Getting the highest ACK range", func() {
231		It("returns the zero value if there are no ranges", func() {
232			Expect(hist.GetHighestAckRange()).To(BeZero())
233		})
234
235		It("gets a single ACK range", func() {
236			hist.ReceivedPacket(4)
237			hist.ReceivedPacket(5)
238			Expect(hist.GetHighestAckRange()).To(Equal(wire.AckRange{Smallest: 4, Largest: 5}))
239		})
240
241		It("gets the highest of multiple ACK ranges", func() {
242			hist.ReceivedPacket(3)
243			hist.ReceivedPacket(6)
244			hist.ReceivedPacket(7)
245			Expect(hist.GetHighestAckRange()).To(Equal(wire.AckRange{Smallest: 6, Largest: 7}))
246		})
247	})
248})
249