1package ackhandler 2 3import ( 4 "time" 5 6 "github.com/lucas-clemente/quic-go/internal/protocol" 7 "github.com/lucas-clemente/quic-go/internal/utils" 8 "github.com/lucas-clemente/quic-go/internal/wire" 9 10 . "github.com/onsi/ginkgo" 11 . "github.com/onsi/gomega" 12) 13 14var _ = Describe("Received Packet Tracker", func() { 15 var ( 16 tracker *receivedPacketTracker 17 rttStats *utils.RTTStats 18 ) 19 20 BeforeEach(func() { 21 rttStats = &utils.RTTStats{} 22 tracker = newReceivedPacketTracker(rttStats, utils.DefaultLogger, protocol.VersionWhatever) 23 }) 24 25 Context("accepting packets", func() { 26 It("saves the time when each packet arrived", func() { 27 tracker.ReceivedPacket(protocol.PacketNumber(3), protocol.ECNNon, time.Now(), true) 28 Expect(tracker.largestObservedReceivedTime).To(BeTemporally("~", time.Now(), 10*time.Millisecond)) 29 }) 30 31 It("updates the largestObserved and the largestObservedReceivedTime", func() { 32 now := time.Now() 33 tracker.largestObserved = 3 34 tracker.largestObservedReceivedTime = now.Add(-1 * time.Second) 35 tracker.ReceivedPacket(5, protocol.ECNNon, now, true) 36 Expect(tracker.largestObserved).To(Equal(protocol.PacketNumber(5))) 37 Expect(tracker.largestObservedReceivedTime).To(Equal(now)) 38 }) 39 40 It("doesn't update the largestObserved and the largestObservedReceivedTime for a belated packet", func() { 41 now := time.Now() 42 timestamp := now.Add(-1 * time.Second) 43 tracker.largestObserved = 5 44 tracker.largestObservedReceivedTime = timestamp 45 tracker.ReceivedPacket(4, protocol.ECNNon, now, true) 46 Expect(tracker.largestObserved).To(Equal(protocol.PacketNumber(5))) 47 Expect(tracker.largestObservedReceivedTime).To(Equal(timestamp)) 48 }) 49 }) 50 51 Context("ACKs", func() { 52 Context("queueing ACKs", func() { 53 receiveAndAck10Packets := func() { 54 for i := 1; i <= 10; i++ { 55 tracker.ReceivedPacket(protocol.PacketNumber(i), protocol.ECNNon, time.Time{}, true) 56 } 57 Expect(tracker.GetAckFrame(true)).ToNot(BeNil()) 58 Expect(tracker.ackQueued).To(BeFalse()) 59 } 60 61 It("always queues an ACK for the first packet", func() { 62 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 63 Expect(tracker.ackQueued).To(BeTrue()) 64 Expect(tracker.GetAlarmTimeout()).To(BeZero()) 65 Expect(tracker.GetAckFrame(true).DelayTime).To(BeNumerically("~", 0, time.Second)) 66 }) 67 68 It("works with packet number 0", func() { 69 tracker.ReceivedPacket(0, protocol.ECNNon, time.Now(), true) 70 Expect(tracker.ackQueued).To(BeTrue()) 71 Expect(tracker.GetAlarmTimeout()).To(BeZero()) 72 Expect(tracker.GetAckFrame(true).DelayTime).To(BeNumerically("~", 0, time.Second)) 73 }) 74 75 It("sets ECN flags", func() { 76 tracker.ReceivedPacket(0, protocol.ECT0, time.Now(), true) 77 pn := protocol.PacketNumber(1) 78 for i := 0; i < 2; i++ { 79 tracker.ReceivedPacket(pn, protocol.ECT1, time.Now(), true) 80 pn++ 81 } 82 for i := 0; i < 3; i++ { 83 tracker.ReceivedPacket(pn, protocol.ECNCE, time.Now(), true) 84 pn++ 85 } 86 ack := tracker.GetAckFrame(false) 87 Expect(ack.ECT0).To(BeEquivalentTo(1)) 88 Expect(ack.ECT1).To(BeEquivalentTo(2)) 89 Expect(ack.ECNCE).To(BeEquivalentTo(3)) 90 }) 91 92 It("queues an ACK for every second ack-eliciting packet", func() { 93 receiveAndAck10Packets() 94 p := protocol.PacketNumber(11) 95 for i := 0; i <= 20; i++ { 96 tracker.ReceivedPacket(p, protocol.ECNNon, time.Time{}, true) 97 Expect(tracker.ackQueued).To(BeFalse()) 98 p++ 99 tracker.ReceivedPacket(p, protocol.ECNNon, time.Time{}, true) 100 Expect(tracker.ackQueued).To(BeTrue()) 101 p++ 102 // dequeue the ACK frame 103 Expect(tracker.GetAckFrame(true)).ToNot(BeNil()) 104 } 105 }) 106 107 It("resets the counter when a non-queued ACK frame is generated", func() { 108 receiveAndAck10Packets() 109 rcvTime := time.Now() 110 tracker.ReceivedPacket(11, protocol.ECNNon, rcvTime, true) 111 Expect(tracker.GetAckFrame(false)).ToNot(BeNil()) 112 tracker.ReceivedPacket(12, protocol.ECNNon, rcvTime, true) 113 Expect(tracker.GetAckFrame(true)).To(BeNil()) 114 tracker.ReceivedPacket(13, protocol.ECNNon, rcvTime, true) 115 Expect(tracker.GetAckFrame(false)).ToNot(BeNil()) 116 }) 117 118 It("only sets the timer when receiving a ack-eliciting packets", func() { 119 receiveAndAck10Packets() 120 tracker.ReceivedPacket(11, protocol.ECNNon, time.Now(), false) 121 Expect(tracker.ackQueued).To(BeFalse()) 122 Expect(tracker.GetAlarmTimeout()).To(BeZero()) 123 rcvTime := time.Now().Add(10 * time.Millisecond) 124 tracker.ReceivedPacket(12, protocol.ECNNon, rcvTime, true) 125 Expect(tracker.ackQueued).To(BeFalse()) 126 Expect(tracker.GetAlarmTimeout()).To(Equal(rcvTime.Add(protocol.MaxAckDelay))) 127 }) 128 129 It("queues an ACK if it was reported missing before", func() { 130 receiveAndAck10Packets() 131 tracker.ReceivedPacket(11, protocol.ECNNon, time.Now(), true) 132 tracker.ReceivedPacket(13, protocol.ECNNon, time.Now(), true) 133 ack := tracker.GetAckFrame(true) // ACK: 1-11 and 13, missing: 12 134 Expect(ack).ToNot(BeNil()) 135 Expect(ack.HasMissingRanges()).To(BeTrue()) 136 Expect(tracker.ackQueued).To(BeFalse()) 137 tracker.ReceivedPacket(12, protocol.ECNNon, time.Now(), true) 138 Expect(tracker.ackQueued).To(BeTrue()) 139 }) 140 141 It("doesn't queue an ACK if it was reported missing before, but is below the threshold", func() { 142 receiveAndAck10Packets() 143 // 11 is missing 144 tracker.ReceivedPacket(12, protocol.ECNNon, time.Now(), true) 145 tracker.ReceivedPacket(13, protocol.ECNNon, time.Now(), true) 146 ack := tracker.GetAckFrame(true) // ACK: 1-10, 12-13 147 Expect(ack).ToNot(BeNil()) 148 // now receive 11 149 tracker.IgnoreBelow(12) 150 tracker.ReceivedPacket(11, protocol.ECNNon, time.Now(), false) 151 ack = tracker.GetAckFrame(true) 152 Expect(ack).To(BeNil()) 153 }) 154 155 It("doesn't recognize in-order packets as out-of-order after raising the threshold", func() { 156 receiveAndAck10Packets() 157 Expect(tracker.lastAck.LargestAcked()).To(Equal(protocol.PacketNumber(10))) 158 Expect(tracker.ackQueued).To(BeFalse()) 159 tracker.IgnoreBelow(11) 160 tracker.ReceivedPacket(11, protocol.ECNNon, time.Now(), true) 161 Expect(tracker.GetAckFrame(true)).To(BeNil()) 162 }) 163 164 It("recognizes out-of-order packets after raising the threshold", func() { 165 receiveAndAck10Packets() 166 Expect(tracker.lastAck.LargestAcked()).To(Equal(protocol.PacketNumber(10))) 167 Expect(tracker.ackQueued).To(BeFalse()) 168 tracker.IgnoreBelow(11) 169 tracker.ReceivedPacket(12, protocol.ECNNon, time.Now(), true) 170 ack := tracker.GetAckFrame(true) 171 Expect(ack).ToNot(BeNil()) 172 Expect(ack.AckRanges).To(Equal([]wire.AckRange{{Smallest: 12, Largest: 12}})) 173 }) 174 175 It("doesn't queue an ACK if for non-ack-eliciting packets arriving out-of-order", func() { 176 receiveAndAck10Packets() 177 tracker.ReceivedPacket(11, protocol.ECNNon, time.Now(), true) 178 Expect(tracker.GetAckFrame(true)).To(BeNil()) 179 tracker.ReceivedPacket(13, protocol.ECNNon, time.Now(), false) // receive a non-ack-eliciting packet out-of-order 180 Expect(tracker.GetAckFrame(true)).To(BeNil()) 181 }) 182 183 It("doesn't queue an ACK if packets arrive out-of-order, but haven't been acknowledged yet", func() { 184 receiveAndAck10Packets() 185 Expect(tracker.lastAck).ToNot(BeNil()) 186 tracker.ReceivedPacket(12, protocol.ECNNon, time.Now(), false) 187 Expect(tracker.GetAckFrame(true)).To(BeNil()) 188 // 11 is received out-of-order, but this hasn't been reported in an ACK frame yet 189 tracker.ReceivedPacket(11, protocol.ECNNon, time.Now(), true) 190 Expect(tracker.GetAckFrame(true)).To(BeNil()) 191 }) 192 }) 193 194 Context("ACK generation", func() { 195 It("generates an ACK for an ack-eliciting packet, if no ACK is queued yet", func() { 196 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 197 // The first packet is always acknowledged. 198 Expect(tracker.GetAckFrame(true)).ToNot(BeNil()) 199 }) 200 201 It("doesn't generate ACK for a non-ack-eliciting packet, if no ACK is queued yet", func() { 202 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 203 // The first packet is always acknowledged. 204 Expect(tracker.GetAckFrame(true)).ToNot(BeNil()) 205 206 tracker.ReceivedPacket(2, protocol.ECNNon, time.Now(), false) 207 Expect(tracker.GetAckFrame(false)).To(BeNil()) 208 tracker.ReceivedPacket(3, protocol.ECNNon, time.Now(), true) 209 ack := tracker.GetAckFrame(false) 210 Expect(ack).ToNot(BeNil()) 211 Expect(ack.LowestAcked()).To(Equal(protocol.PacketNumber(1))) 212 Expect(ack.LargestAcked()).To(Equal(protocol.PacketNumber(3))) 213 }) 214 215 Context("for queued ACKs", func() { 216 BeforeEach(func() { 217 tracker.ackQueued = true 218 }) 219 220 It("generates a simple ACK frame", func() { 221 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 222 tracker.ReceivedPacket(2, protocol.ECNNon, time.Now(), true) 223 ack := tracker.GetAckFrame(true) 224 Expect(ack).ToNot(BeNil()) 225 Expect(ack.LargestAcked()).To(Equal(protocol.PacketNumber(2))) 226 Expect(ack.LowestAcked()).To(Equal(protocol.PacketNumber(1))) 227 Expect(ack.HasMissingRanges()).To(BeFalse()) 228 }) 229 230 It("generates an ACK for packet number 0", func() { 231 tracker.ReceivedPacket(0, protocol.ECNNon, time.Now(), true) 232 ack := tracker.GetAckFrame(true) 233 Expect(ack).ToNot(BeNil()) 234 Expect(ack.LargestAcked()).To(Equal(protocol.PacketNumber(0))) 235 Expect(ack.LowestAcked()).To(Equal(protocol.PacketNumber(0))) 236 Expect(ack.HasMissingRanges()).To(BeFalse()) 237 }) 238 239 It("sets the delay time", func() { 240 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 241 tracker.ReceivedPacket(2, protocol.ECNNon, time.Now().Add(-1337*time.Millisecond), true) 242 ack := tracker.GetAckFrame(true) 243 Expect(ack).ToNot(BeNil()) 244 Expect(ack.DelayTime).To(BeNumerically("~", 1337*time.Millisecond, 50*time.Millisecond)) 245 }) 246 247 It("uses a 0 delay time if the delay would be negative", func() { 248 tracker.ReceivedPacket(0, protocol.ECNNon, time.Now().Add(time.Hour), true) 249 ack := tracker.GetAckFrame(true) 250 Expect(ack).ToNot(BeNil()) 251 Expect(ack.DelayTime).To(BeZero()) 252 }) 253 254 It("saves the last sent ACK", func() { 255 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 256 ack := tracker.GetAckFrame(true) 257 Expect(ack).ToNot(BeNil()) 258 Expect(tracker.lastAck).To(Equal(ack)) 259 tracker.ReceivedPacket(2, protocol.ECNNon, time.Now(), true) 260 tracker.ackQueued = true 261 ack = tracker.GetAckFrame(true) 262 Expect(ack).ToNot(BeNil()) 263 Expect(tracker.lastAck).To(Equal(ack)) 264 }) 265 266 It("generates an ACK frame with missing packets", func() { 267 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 268 tracker.ReceivedPacket(4, protocol.ECNNon, time.Now(), true) 269 ack := tracker.GetAckFrame(true) 270 Expect(ack).ToNot(BeNil()) 271 Expect(ack.LargestAcked()).To(Equal(protocol.PacketNumber(4))) 272 Expect(ack.LowestAcked()).To(Equal(protocol.PacketNumber(1))) 273 Expect(ack.AckRanges).To(Equal([]wire.AckRange{ 274 {Smallest: 4, Largest: 4}, 275 {Smallest: 1, Largest: 1}, 276 })) 277 }) 278 279 It("generates an ACK for packet number 0 and other packets", func() { 280 tracker.ReceivedPacket(0, protocol.ECNNon, time.Now(), true) 281 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 282 tracker.ReceivedPacket(3, protocol.ECNNon, time.Now(), true) 283 ack := tracker.GetAckFrame(true) 284 Expect(ack).ToNot(BeNil()) 285 Expect(ack.LargestAcked()).To(Equal(protocol.PacketNumber(3))) 286 Expect(ack.LowestAcked()).To(Equal(protocol.PacketNumber(0))) 287 Expect(ack.AckRanges).To(Equal([]wire.AckRange{ 288 {Smallest: 3, Largest: 3}, 289 {Smallest: 0, Largest: 1}, 290 })) 291 }) 292 293 It("doesn't add delayed packets to the packetHistory", func() { 294 tracker.IgnoreBelow(7) 295 tracker.ReceivedPacket(4, protocol.ECNNon, time.Now(), true) 296 tracker.ReceivedPacket(10, protocol.ECNNon, time.Now(), true) 297 ack := tracker.GetAckFrame(true) 298 Expect(ack).ToNot(BeNil()) 299 Expect(ack.LargestAcked()).To(Equal(protocol.PacketNumber(10))) 300 Expect(ack.LowestAcked()).To(Equal(protocol.PacketNumber(10))) 301 }) 302 303 It("deletes packets from the packetHistory when a lower limit is set", func() { 304 for i := 1; i <= 12; i++ { 305 tracker.ReceivedPacket(protocol.PacketNumber(i), protocol.ECNNon, time.Now(), true) 306 } 307 tracker.IgnoreBelow(7) 308 // check that the packets were deleted from the receivedPacketHistory by checking the values in an ACK frame 309 ack := tracker.GetAckFrame(true) 310 Expect(ack).ToNot(BeNil()) 311 Expect(ack.LargestAcked()).To(Equal(protocol.PacketNumber(12))) 312 Expect(ack.LowestAcked()).To(Equal(protocol.PacketNumber(7))) 313 Expect(ack.HasMissingRanges()).To(BeFalse()) 314 }) 315 316 // TODO: remove this test when dropping support for STOP_WAITINGs 317 It("handles a lower limit of 0", func() { 318 tracker.IgnoreBelow(0) 319 tracker.ReceivedPacket(1337, protocol.ECNNon, time.Now(), true) 320 ack := tracker.GetAckFrame(true) 321 Expect(ack).ToNot(BeNil()) 322 Expect(ack.LargestAcked()).To(Equal(protocol.PacketNumber(1337))) 323 }) 324 325 It("resets all counters needed for the ACK queueing decision when sending an ACK", func() { 326 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 327 tracker.ackAlarm = time.Now().Add(-time.Minute) 328 Expect(tracker.GetAckFrame(true)).ToNot(BeNil()) 329 Expect(tracker.GetAlarmTimeout()).To(BeZero()) 330 Expect(tracker.ackElicitingPacketsReceivedSinceLastAck).To(BeZero()) 331 Expect(tracker.ackQueued).To(BeFalse()) 332 }) 333 334 It("doesn't generate an ACK when none is queued and the timer is not set", func() { 335 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 336 tracker.ackQueued = false 337 tracker.ackAlarm = time.Time{} 338 Expect(tracker.GetAckFrame(true)).To(BeNil()) 339 }) 340 341 It("doesn't generate an ACK when none is queued and the timer has not yet expired", func() { 342 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 343 tracker.ackQueued = false 344 tracker.ackAlarm = time.Now().Add(time.Minute) 345 Expect(tracker.GetAckFrame(true)).To(BeNil()) 346 }) 347 348 It("generates an ACK when the timer has expired", func() { 349 tracker.ReceivedPacket(1, protocol.ECNNon, time.Now(), true) 350 tracker.ackQueued = false 351 tracker.ackAlarm = time.Now().Add(-time.Minute) 352 Expect(tracker.GetAckFrame(true)).ToNot(BeNil()) 353 }) 354 }) 355 }) 356 }) 357}) 358