1package wire 2 3import ( 4 "bytes" 5 "io" 6 "math" 7 "time" 8 9 "github.com/lucas-clemente/quic-go/internal/protocol" 10 . "github.com/onsi/ginkgo" 11 . "github.com/onsi/gomega" 12) 13 14var _ = Describe("ACK Frame (for IETF QUIC)", func() { 15 Context("parsing", func() { 16 It("parses an ACK frame without any ranges", func() { 17 data := []byte{0x2} 18 data = append(data, encodeVarInt(100)...) // largest acked 19 data = append(data, encodeVarInt(0)...) // delay 20 data = append(data, encodeVarInt(0)...) // num blocks 21 data = append(data, encodeVarInt(10)...) // first ack block 22 b := bytes.NewReader(data) 23 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 24 Expect(err).ToNot(HaveOccurred()) 25 Expect(frame.LargestAcked()).To(Equal(protocol.PacketNumber(100))) 26 Expect(frame.LowestAcked()).To(Equal(protocol.PacketNumber(90))) 27 Expect(frame.HasMissingRanges()).To(BeFalse()) 28 Expect(b.Len()).To(BeZero()) 29 }) 30 31 It("parses an ACK frame that only acks a single packet", func() { 32 data := []byte{0x2} 33 data = append(data, encodeVarInt(55)...) // largest acked 34 data = append(data, encodeVarInt(0)...) // delay 35 data = append(data, encodeVarInt(0)...) // num blocks 36 data = append(data, encodeVarInt(0)...) // first ack block 37 b := bytes.NewReader(data) 38 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 39 Expect(err).ToNot(HaveOccurred()) 40 Expect(frame.LargestAcked()).To(Equal(protocol.PacketNumber(55))) 41 Expect(frame.LowestAcked()).To(Equal(protocol.PacketNumber(55))) 42 Expect(frame.HasMissingRanges()).To(BeFalse()) 43 Expect(b.Len()).To(BeZero()) 44 }) 45 46 It("accepts an ACK frame that acks all packets from 0 to largest", func() { 47 data := []byte{0x2} 48 data = append(data, encodeVarInt(20)...) // largest acked 49 data = append(data, encodeVarInt(0)...) // delay 50 data = append(data, encodeVarInt(0)...) // num blocks 51 data = append(data, encodeVarInt(20)...) // first ack block 52 b := bytes.NewReader(data) 53 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 54 Expect(err).ToNot(HaveOccurred()) 55 Expect(frame.LargestAcked()).To(Equal(protocol.PacketNumber(20))) 56 Expect(frame.LowestAcked()).To(Equal(protocol.PacketNumber(0))) 57 Expect(frame.HasMissingRanges()).To(BeFalse()) 58 Expect(b.Len()).To(BeZero()) 59 }) 60 61 It("rejects an ACK frame that has a first ACK block which is larger than LargestAcked", func() { 62 data := []byte{0x2} 63 data = append(data, encodeVarInt(20)...) // largest acked 64 data = append(data, encodeVarInt(0)...) // delay 65 data = append(data, encodeVarInt(0)...) // num blocks 66 data = append(data, encodeVarInt(21)...) // first ack block 67 b := bytes.NewReader(data) 68 _, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 69 Expect(err).To(MatchError("invalid first ACK range")) 70 }) 71 72 It("parses an ACK frame that has a single block", func() { 73 data := []byte{0x2} 74 data = append(data, encodeVarInt(1000)...) // largest acked 75 data = append(data, encodeVarInt(0)...) // delay 76 data = append(data, encodeVarInt(1)...) // num blocks 77 data = append(data, encodeVarInt(100)...) // first ack block 78 data = append(data, encodeVarInt(98)...) // gap 79 data = append(data, encodeVarInt(50)...) // ack block 80 b := bytes.NewReader(data) 81 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 82 Expect(err).ToNot(HaveOccurred()) 83 Expect(frame.LargestAcked()).To(Equal(protocol.PacketNumber(1000))) 84 Expect(frame.LowestAcked()).To(Equal(protocol.PacketNumber(750))) 85 Expect(frame.HasMissingRanges()).To(BeTrue()) 86 Expect(frame.AckRanges).To(Equal([]AckRange{ 87 {Largest: 1000, Smallest: 900}, 88 {Largest: 800, Smallest: 750}, 89 })) 90 Expect(b.Len()).To(BeZero()) 91 }) 92 93 It("parses an ACK frame that has a multiple blocks", func() { 94 data := []byte{0x2} 95 data = append(data, encodeVarInt(100)...) // largest acked 96 data = append(data, encodeVarInt(0)...) // delay 97 data = append(data, encodeVarInt(2)...) // num blocks 98 data = append(data, encodeVarInt(0)...) // first ack block 99 data = append(data, encodeVarInt(0)...) // gap 100 data = append(data, encodeVarInt(0)...) // ack block 101 data = append(data, encodeVarInt(1)...) // gap 102 data = append(data, encodeVarInt(1)...) // ack block 103 b := bytes.NewReader(data) 104 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 105 Expect(err).ToNot(HaveOccurred()) 106 Expect(frame.LargestAcked()).To(Equal(protocol.PacketNumber(100))) 107 Expect(frame.LowestAcked()).To(Equal(protocol.PacketNumber(94))) 108 Expect(frame.HasMissingRanges()).To(BeTrue()) 109 Expect(frame.AckRanges).To(Equal([]AckRange{ 110 {Largest: 100, Smallest: 100}, 111 {Largest: 98, Smallest: 98}, 112 {Largest: 95, Smallest: 94}, 113 })) 114 Expect(b.Len()).To(BeZero()) 115 }) 116 117 It("uses the ack delay exponent", func() { 118 const delayTime = 1 << 10 * time.Millisecond 119 buf := &bytes.Buffer{} 120 f := &AckFrame{ 121 AckRanges: []AckRange{{Smallest: 1, Largest: 1}}, 122 DelayTime: delayTime, 123 } 124 Expect(f.Write(buf, versionIETFFrames)).To(Succeed()) 125 for i := uint8(0); i < 8; i++ { 126 b := bytes.NewReader(buf.Bytes()) 127 frame, err := parseAckFrame(b, protocol.AckDelayExponent+i, versionIETFFrames) 128 Expect(err).ToNot(HaveOccurred()) 129 Expect(frame.DelayTime).To(Equal(delayTime * (1 << i))) 130 } 131 }) 132 133 It("gracefully handles overflows of the delay time", func() { 134 data := []byte{0x2} 135 data = append(data, encodeVarInt(100)...) // largest acked 136 data = append(data, encodeVarInt(math.MaxUint64/5)...) // delay 137 data = append(data, encodeVarInt(0)...) // num blocks 138 data = append(data, encodeVarInt(0)...) // first ack block 139 b := bytes.NewReader(data) 140 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 141 Expect(err).ToNot(HaveOccurred()) 142 Expect(frame.DelayTime).To(BeNumerically(">", 0)) 143 // The maximum encodable duration is ~292 years. 144 Expect(frame.DelayTime.Hours()).To(BeNumerically("~", 292*365*24, 365*24)) 145 }) 146 147 It("errors on EOF", func() { 148 data := []byte{0x2} 149 data = append(data, encodeVarInt(1000)...) // largest acked 150 data = append(data, encodeVarInt(0)...) // delay 151 data = append(data, encodeVarInt(1)...) // num blocks 152 data = append(data, encodeVarInt(100)...) // first ack block 153 data = append(data, encodeVarInt(98)...) // gap 154 data = append(data, encodeVarInt(50)...) // ack block 155 _, err := parseAckFrame(bytes.NewReader(data), protocol.AckDelayExponent, versionIETFFrames) 156 Expect(err).NotTo(HaveOccurred()) 157 for i := range data { 158 _, err := parseAckFrame(bytes.NewReader(data[0:i]), protocol.AckDelayExponent, versionIETFFrames) 159 Expect(err).To(MatchError(io.EOF)) 160 } 161 }) 162 163 Context("ACK_ECN", func() { 164 It("parses", func() { 165 data := []byte{0x3} 166 data = append(data, encodeVarInt(100)...) // largest acked 167 data = append(data, encodeVarInt(0)...) // delay 168 data = append(data, encodeVarInt(0)...) // num blocks 169 data = append(data, encodeVarInt(10)...) // first ack block 170 data = append(data, encodeVarInt(0x42)...) // ECT(0) 171 data = append(data, encodeVarInt(0x12345)...) // ECT(1) 172 data = append(data, encodeVarInt(0x12345678)...) // ECN-CE 173 b := bytes.NewReader(data) 174 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 175 Expect(err).ToNot(HaveOccurred()) 176 Expect(frame.LargestAcked()).To(Equal(protocol.PacketNumber(100))) 177 Expect(frame.LowestAcked()).To(Equal(protocol.PacketNumber(90))) 178 Expect(frame.HasMissingRanges()).To(BeFalse()) 179 Expect(b.Len()).To(BeZero()) 180 }) 181 182 It("errors on EOF", func() { 183 data := []byte{0x3} 184 data = append(data, encodeVarInt(1000)...) // largest acked 185 data = append(data, encodeVarInt(0)...) // delay 186 data = append(data, encodeVarInt(1)...) // num blocks 187 data = append(data, encodeVarInt(100)...) // first ack block 188 data = append(data, encodeVarInt(98)...) // gap 189 data = append(data, encodeVarInt(50)...) // ack block 190 data = append(data, encodeVarInt(0x42)...) // ECT(0) 191 data = append(data, encodeVarInt(0x12345)...) // ECT(1) 192 data = append(data, encodeVarInt(0x12345678)...) // ECN-CE 193 _, err := parseAckFrame(bytes.NewReader(data), protocol.AckDelayExponent, versionIETFFrames) 194 Expect(err).NotTo(HaveOccurred()) 195 for i := range data { 196 _, err := parseAckFrame(bytes.NewReader(data[0:i]), protocol.AckDelayExponent, versionIETFFrames) 197 Expect(err).To(MatchError(io.EOF)) 198 } 199 }) 200 }) 201 }) 202 203 Context("when writing", func() { 204 It("writes a simple frame", func() { 205 buf := &bytes.Buffer{} 206 f := &AckFrame{ 207 AckRanges: []AckRange{{Smallest: 100, Largest: 1337}}, 208 } 209 Expect(f.Write(buf, versionIETFFrames)).To(Succeed()) 210 expected := []byte{0x2} 211 expected = append(expected, encodeVarInt(1337)...) // largest acked 212 expected = append(expected, 0) // delay 213 expected = append(expected, encodeVarInt(0)...) // num ranges 214 expected = append(expected, encodeVarInt(1337-100)...) 215 Expect(buf.Bytes()).To(Equal(expected)) 216 }) 217 218 It("writes an ACK-ECN frame", func() { 219 buf := &bytes.Buffer{} 220 f := &AckFrame{ 221 AckRanges: []AckRange{{Smallest: 10, Largest: 2000}}, 222 ECT0: 13, 223 ECT1: 37, 224 ECNCE: 12345, 225 } 226 Expect(f.Write(buf, versionIETFFrames)).To(Succeed()) 227 Expect(f.Length(versionIETFFrames)).To(BeEquivalentTo(buf.Len())) 228 expected := []byte{0x3} 229 expected = append(expected, encodeVarInt(2000)...) // largest acked 230 expected = append(expected, 0) // delay 231 expected = append(expected, encodeVarInt(0)...) // num ranges 232 expected = append(expected, encodeVarInt(2000-10)...) 233 expected = append(expected, encodeVarInt(13)...) 234 expected = append(expected, encodeVarInt(37)...) 235 expected = append(expected, encodeVarInt(12345)...) 236 Expect(buf.Bytes()).To(Equal(expected)) 237 }) 238 239 It("writes a frame that acks a single packet", func() { 240 buf := &bytes.Buffer{} 241 f := &AckFrame{ 242 AckRanges: []AckRange{{Smallest: 0x2eadbeef, Largest: 0x2eadbeef}}, 243 DelayTime: 18 * time.Millisecond, 244 } 245 Expect(f.Write(buf, versionIETFFrames)).To(Succeed()) 246 Expect(f.Length(versionIETFFrames)).To(BeEquivalentTo(buf.Len())) 247 b := bytes.NewReader(buf.Bytes()) 248 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 249 Expect(err).ToNot(HaveOccurred()) 250 Expect(frame).To(Equal(f)) 251 Expect(frame.HasMissingRanges()).To(BeFalse()) 252 Expect(frame.DelayTime).To(Equal(f.DelayTime)) 253 Expect(b.Len()).To(BeZero()) 254 }) 255 256 It("writes a frame that acks many packets", func() { 257 buf := &bytes.Buffer{} 258 f := &AckFrame{ 259 AckRanges: []AckRange{{Smallest: 0x1337, Largest: 0x2eadbeef}}, 260 } 261 Expect(f.Write(buf, versionIETFFrames)).To(Succeed()) 262 Expect(f.Length(versionIETFFrames)).To(BeEquivalentTo(buf.Len())) 263 b := bytes.NewReader(buf.Bytes()) 264 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 265 Expect(err).ToNot(HaveOccurred()) 266 Expect(frame).To(Equal(f)) 267 Expect(frame.HasMissingRanges()).To(BeFalse()) 268 Expect(b.Len()).To(BeZero()) 269 }) 270 271 It("writes a frame with a a single gap", func() { 272 buf := &bytes.Buffer{} 273 f := &AckFrame{ 274 AckRanges: []AckRange{ 275 {Smallest: 400, Largest: 1000}, 276 {Smallest: 100, Largest: 200}, 277 }, 278 } 279 Expect(f.validateAckRanges()).To(BeTrue()) 280 err := f.Write(buf, versionIETFFrames) 281 Expect(err).ToNot(HaveOccurred()) 282 Expect(f.Length(versionIETFFrames)).To(BeEquivalentTo(buf.Len())) 283 b := bytes.NewReader(buf.Bytes()) 284 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 285 Expect(err).ToNot(HaveOccurred()) 286 Expect(frame).To(Equal(f)) 287 Expect(frame.HasMissingRanges()).To(BeTrue()) 288 Expect(b.Len()).To(BeZero()) 289 }) 290 291 It("writes a frame with multiple ranges", func() { 292 buf := &bytes.Buffer{} 293 f := &AckFrame{ 294 AckRanges: []AckRange{ 295 {Smallest: 10, Largest: 10}, 296 {Smallest: 8, Largest: 8}, 297 {Smallest: 5, Largest: 6}, 298 {Smallest: 1, Largest: 3}, 299 }, 300 } 301 Expect(f.validateAckRanges()).To(BeTrue()) 302 Expect(f.Write(buf, versionIETFFrames)).To(Succeed()) 303 Expect(f.Length(versionIETFFrames)).To(BeEquivalentTo(buf.Len())) 304 b := bytes.NewReader(buf.Bytes()) 305 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 306 Expect(err).ToNot(HaveOccurred()) 307 Expect(frame).To(Equal(f)) 308 Expect(frame.HasMissingRanges()).To(BeTrue()) 309 Expect(b.Len()).To(BeZero()) 310 }) 311 312 It("limits the maximum size of the ACK frame", func() { 313 buf := &bytes.Buffer{} 314 const numRanges = 1000 315 ackRanges := make([]AckRange, numRanges) 316 for i := protocol.PacketNumber(1); i <= numRanges; i++ { 317 ackRanges[numRanges-i] = AckRange{Smallest: 2 * i, Largest: 2 * i} 318 } 319 f := &AckFrame{AckRanges: ackRanges} 320 Expect(f.validateAckRanges()).To(BeTrue()) 321 Expect(f.Write(buf, versionIETFFrames)).To(Succeed()) 322 Expect(f.Length(versionIETFFrames)).To(BeEquivalentTo(buf.Len())) 323 // make sure the ACK frame is *a little bit* smaller than the MaxAckFrameSize 324 Expect(buf.Len()).To(BeNumerically(">", protocol.MaxAckFrameSize-5)) 325 Expect(buf.Len()).To(BeNumerically("<=", protocol.MaxAckFrameSize)) 326 b := bytes.NewReader(buf.Bytes()) 327 frame, err := parseAckFrame(b, protocol.AckDelayExponent, versionIETFFrames) 328 Expect(err).ToNot(HaveOccurred()) 329 Expect(frame.HasMissingRanges()).To(BeTrue()) 330 Expect(b.Len()).To(BeZero()) 331 Expect(len(frame.AckRanges)).To(BeNumerically("<", numRanges)) // make sure we dropped some ranges 332 }) 333 }) 334 335 Context("ACK range validator", func() { 336 It("rejects ACKs without ranges", func() { 337 Expect((&AckFrame{}).validateAckRanges()).To(BeFalse()) 338 }) 339 340 It("accepts an ACK without NACK Ranges", func() { 341 ack := AckFrame{ 342 AckRanges: []AckRange{{Smallest: 1, Largest: 7}}, 343 } 344 Expect(ack.validateAckRanges()).To(BeTrue()) 345 }) 346 347 It("rejects ACK ranges with Smallest greater than Largest", func() { 348 ack := AckFrame{ 349 AckRanges: []AckRange{ 350 {Smallest: 8, Largest: 10}, 351 {Smallest: 4, Largest: 3}, 352 }, 353 } 354 Expect(ack.validateAckRanges()).To(BeFalse()) 355 }) 356 357 It("rejects ACK ranges in the wrong order", func() { 358 ack := AckFrame{ 359 AckRanges: []AckRange{ 360 {Smallest: 2, Largest: 2}, 361 {Smallest: 6, Largest: 7}, 362 }, 363 } 364 Expect(ack.validateAckRanges()).To(BeFalse()) 365 }) 366 367 It("rejects with overlapping ACK ranges", func() { 368 ack := AckFrame{ 369 AckRanges: []AckRange{ 370 {Smallest: 5, Largest: 7}, 371 {Smallest: 2, Largest: 5}, 372 }, 373 } 374 Expect(ack.validateAckRanges()).To(BeFalse()) 375 }) 376 377 It("rejects ACK ranges that are part of a larger ACK range", func() { 378 ack := AckFrame{ 379 AckRanges: []AckRange{ 380 {Smallest: 4, Largest: 7}, 381 {Smallest: 5, Largest: 6}, 382 }, 383 } 384 Expect(ack.validateAckRanges()).To(BeFalse()) 385 }) 386 387 It("rejects with directly adjacent ACK ranges", func() { 388 ack := AckFrame{ 389 AckRanges: []AckRange{ 390 {Smallest: 5, Largest: 7}, 391 {Smallest: 2, Largest: 4}, 392 }, 393 } 394 Expect(ack.validateAckRanges()).To(BeFalse()) 395 }) 396 397 It("accepts an ACK with one lost packet", func() { 398 ack := AckFrame{ 399 AckRanges: []AckRange{ 400 {Smallest: 5, Largest: 10}, 401 {Smallest: 1, Largest: 3}, 402 }, 403 } 404 Expect(ack.validateAckRanges()).To(BeTrue()) 405 }) 406 407 It("accepts an ACK with multiple lost packets", func() { 408 ack := AckFrame{ 409 AckRanges: []AckRange{ 410 {Smallest: 15, Largest: 20}, 411 {Smallest: 10, Largest: 12}, 412 {Smallest: 1, Largest: 3}, 413 }, 414 } 415 Expect(ack.validateAckRanges()).To(BeTrue()) 416 }) 417 }) 418 419 Context("check if ACK frame acks a certain packet", func() { 420 It("works with an ACK without any ranges", func() { 421 f := AckFrame{ 422 AckRanges: []AckRange{{Smallest: 5, Largest: 10}}, 423 } 424 Expect(f.AcksPacket(1)).To(BeFalse()) 425 Expect(f.AcksPacket(4)).To(BeFalse()) 426 Expect(f.AcksPacket(5)).To(BeTrue()) 427 Expect(f.AcksPacket(8)).To(BeTrue()) 428 Expect(f.AcksPacket(10)).To(BeTrue()) 429 Expect(f.AcksPacket(11)).To(BeFalse()) 430 Expect(f.AcksPacket(20)).To(BeFalse()) 431 }) 432 433 It("works with an ACK with multiple ACK ranges", func() { 434 f := AckFrame{ 435 AckRanges: []AckRange{ 436 {Smallest: 15, Largest: 20}, 437 {Smallest: 5, Largest: 8}, 438 }, 439 } 440 Expect(f.AcksPacket(4)).To(BeFalse()) 441 Expect(f.AcksPacket(5)).To(BeTrue()) 442 Expect(f.AcksPacket(6)).To(BeTrue()) 443 Expect(f.AcksPacket(7)).To(BeTrue()) 444 Expect(f.AcksPacket(8)).To(BeTrue()) 445 Expect(f.AcksPacket(9)).To(BeFalse()) 446 Expect(f.AcksPacket(14)).To(BeFalse()) 447 Expect(f.AcksPacket(15)).To(BeTrue()) 448 Expect(f.AcksPacket(18)).To(BeTrue()) 449 Expect(f.AcksPacket(19)).To(BeTrue()) 450 Expect(f.AcksPacket(20)).To(BeTrue()) 451 Expect(f.AcksPacket(21)).To(BeFalse()) 452 }) 453 }) 454}) 455