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