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