1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "quiche/quic/core/quic_stream_sequencer.h"
6
7 #include <algorithm>
8 #include <cstdint>
9 #include <memory>
10 #include <string>
11 #include <utility>
12 #include <vector>
13
14 #include "absl/base/macros.h"
15 #include "absl/strings/string_view.h"
16 #include "quiche/quic/core/quic_stream.h"
17 #include "quiche/quic/core/quic_utils.h"
18 #include "quiche/quic/platform/api/quic_expect_bug.h"
19 #include "quiche/quic/platform/api/quic_flags.h"
20 #include "quiche/quic/platform/api/quic_logging.h"
21 #include "quiche/quic/platform/api/quic_test.h"
22 #include "quiche/quic/test_tools/quic_stream_sequencer_peer.h"
23 #include "quiche/quic/test_tools/quic_test_utils.h"
24
25 using testing::_;
26 using testing::AnyNumber;
27 using testing::InSequence;
28
29 namespace quic {
30 namespace test {
31
32 class MockStream : public QuicStreamSequencer::StreamInterface {
33 public:
34 MOCK_METHOD(void, OnFinRead, (), (override));
35 MOCK_METHOD(void, OnDataAvailable, (), (override));
36 MOCK_METHOD(void, OnUnrecoverableError,
37 (QuicErrorCode error, const std::string& details), (override));
38 MOCK_METHOD(void, OnUnrecoverableError,
39 (QuicErrorCode error, QuicIetfTransportErrorCodes ietf_error,
40 const std::string& details),
41 (override));
42 MOCK_METHOD(void, ResetWithError, (QuicResetStreamError error), (override));
43 MOCK_METHOD(void, AddBytesConsumed, (QuicByteCount bytes), (override));
44
id() const45 QuicStreamId id() const override { return 1; }
version() const46 ParsedQuicVersion version() const override {
47 return CurrentSupportedVersions()[0];
48 }
49 };
50
51 namespace {
52
53 static const char kPayload[] =
54 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
55
56 class QuicStreamSequencerTest : public QuicTest {
57 public:
ConsumeData(size_t num_bytes)58 void ConsumeData(size_t num_bytes) {
59 char buffer[1024];
60 ASSERT_GT(ABSL_ARRAYSIZE(buffer), num_bytes);
61 struct iovec iov;
62 iov.iov_base = buffer;
63 iov.iov_len = num_bytes;
64 ASSERT_EQ(num_bytes, sequencer_->Readv(&iov, 1));
65 }
66
67 protected:
QuicStreamSequencerTest()68 QuicStreamSequencerTest()
69 : stream_(), sequencer_(new QuicStreamSequencer(&stream_)) {}
70
71 // Verify that the data in first region match with the expected[0].
VerifyReadableRegion(const std::vector<std::string> & expected)72 bool VerifyReadableRegion(const std::vector<std::string>& expected) {
73 return VerifyReadableRegion(*sequencer_, expected);
74 }
75
76 // Verify that the data in each of currently readable regions match with each
77 // item given in |expected|.
VerifyReadableRegions(const std::vector<std::string> & expected)78 bool VerifyReadableRegions(const std::vector<std::string>& expected) {
79 return VerifyReadableRegions(*sequencer_, expected);
80 }
81
VerifyIovecs(iovec * iovecs,size_t num_iovecs,const std::vector<std::string> & expected)82 bool VerifyIovecs(iovec* iovecs, size_t num_iovecs,
83 const std::vector<std::string>& expected) {
84 return VerifyIovecs(*sequencer_, iovecs, num_iovecs, expected);
85 }
86
VerifyReadableRegion(const QuicStreamSequencer & sequencer,const std::vector<std::string> & expected)87 bool VerifyReadableRegion(const QuicStreamSequencer& sequencer,
88 const std::vector<std::string>& expected) {
89 iovec iovecs[1];
90 if (sequencer.GetReadableRegions(iovecs, 1)) {
91 return (VerifyIovecs(sequencer, iovecs, 1,
92 std::vector<std::string>{expected[0]}));
93 }
94 return false;
95 }
96
97 // Verify that the data in each of currently readable regions match with each
98 // item given in |expected|.
VerifyReadableRegions(const QuicStreamSequencer & sequencer,const std::vector<std::string> & expected)99 bool VerifyReadableRegions(const QuicStreamSequencer& sequencer,
100 const std::vector<std::string>& expected) {
101 iovec iovecs[5];
102 size_t num_iovecs =
103 sequencer.GetReadableRegions(iovecs, ABSL_ARRAYSIZE(iovecs));
104 return VerifyReadableRegion(sequencer, expected) &&
105 VerifyIovecs(sequencer, iovecs, num_iovecs, expected);
106 }
107
VerifyIovecs(const QuicStreamSequencer &,iovec * iovecs,size_t num_iovecs,const std::vector<std::string> & expected)108 bool VerifyIovecs(const QuicStreamSequencer& /*sequencer*/, iovec* iovecs,
109 size_t num_iovecs,
110 const std::vector<std::string>& expected) {
111 int start_position = 0;
112 for (size_t i = 0; i < num_iovecs; ++i) {
113 if (!VerifyIovec(iovecs[i],
114 expected[0].substr(start_position, iovecs[i].iov_len))) {
115 return false;
116 }
117 start_position += iovecs[i].iov_len;
118 }
119 return true;
120 }
121
VerifyIovec(const iovec & iovec,absl::string_view expected)122 bool VerifyIovec(const iovec& iovec, absl::string_view expected) {
123 if (iovec.iov_len != expected.length()) {
124 QUIC_LOG(ERROR) << "Invalid length: " << iovec.iov_len << " vs "
125 << expected.length();
126 return false;
127 }
128 if (memcmp(iovec.iov_base, expected.data(), expected.length()) != 0) {
129 QUIC_LOG(ERROR) << "Invalid data: " << static_cast<char*>(iovec.iov_base)
130 << " vs " << expected;
131 return false;
132 }
133 return true;
134 }
135
OnFinFrame(QuicStreamOffset byte_offset,const char * data)136 void OnFinFrame(QuicStreamOffset byte_offset, const char* data) {
137 QuicStreamFrame frame;
138 frame.stream_id = 1;
139 frame.offset = byte_offset;
140 frame.data_buffer = data;
141 frame.data_length = strlen(data);
142 frame.fin = true;
143 sequencer_->OnStreamFrame(frame);
144 }
145
OnFrame(QuicStreamOffset byte_offset,const char * data)146 void OnFrame(QuicStreamOffset byte_offset, const char* data) {
147 QuicStreamFrame frame;
148 frame.stream_id = 1;
149 frame.offset = byte_offset;
150 frame.data_buffer = data;
151 frame.data_length = strlen(data);
152 frame.fin = false;
153 sequencer_->OnStreamFrame(frame);
154 }
155
NumBufferedBytes()156 size_t NumBufferedBytes() {
157 return QuicStreamSequencerPeer::GetNumBufferedBytes(sequencer_.get());
158 }
159
160 testing::StrictMock<MockStream> stream_;
161 std::unique_ptr<QuicStreamSequencer> sequencer_;
162 };
163
164 // TODO(rch): reorder these tests so they build on each other.
165
TEST_F(QuicStreamSequencerTest,RejectOldFrame)166 TEST_F(QuicStreamSequencerTest, RejectOldFrame) {
167 EXPECT_CALL(stream_, AddBytesConsumed(3));
168 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
169 ConsumeData(3);
170 }));
171
172 OnFrame(0, "abc");
173
174 EXPECT_EQ(0u, NumBufferedBytes());
175 EXPECT_EQ(3u, sequencer_->NumBytesConsumed());
176 // Ignore this - it matches a past packet number and we should not see it
177 // again.
178 OnFrame(0, "def");
179 EXPECT_EQ(0u, NumBufferedBytes());
180 }
181
TEST_F(QuicStreamSequencerTest,RejectBufferedFrame)182 TEST_F(QuicStreamSequencerTest, RejectBufferedFrame) {
183 EXPECT_CALL(stream_, OnDataAvailable());
184
185 OnFrame(0, "abc");
186 EXPECT_EQ(3u, NumBufferedBytes());
187 EXPECT_EQ(0u, sequencer_->NumBytesConsumed());
188
189 // Ignore this - it matches a buffered frame.
190 // Right now there's no checking that the payload is consistent.
191 OnFrame(0, "def");
192 EXPECT_EQ(3u, NumBufferedBytes());
193 }
194
TEST_F(QuicStreamSequencerTest,FullFrameConsumed)195 TEST_F(QuicStreamSequencerTest, FullFrameConsumed) {
196 EXPECT_CALL(stream_, AddBytesConsumed(3));
197 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
198 ConsumeData(3);
199 }));
200
201 OnFrame(0, "abc");
202 EXPECT_EQ(0u, NumBufferedBytes());
203 EXPECT_EQ(3u, sequencer_->NumBytesConsumed());
204 }
205
TEST_F(QuicStreamSequencerTest,BlockedThenFullFrameConsumed)206 TEST_F(QuicStreamSequencerTest, BlockedThenFullFrameConsumed) {
207 sequencer_->SetBlockedUntilFlush();
208
209 OnFrame(0, "abc");
210 EXPECT_EQ(3u, NumBufferedBytes());
211 EXPECT_EQ(0u, sequencer_->NumBytesConsumed());
212
213 EXPECT_CALL(stream_, AddBytesConsumed(3));
214 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
215 ConsumeData(3);
216 }));
217 sequencer_->SetUnblocked();
218 EXPECT_EQ(0u, NumBufferedBytes());
219 EXPECT_EQ(3u, sequencer_->NumBytesConsumed());
220
221 EXPECT_CALL(stream_, AddBytesConsumed(3));
222 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
223 ConsumeData(3);
224 }));
225 EXPECT_FALSE(sequencer_->IsClosed());
226 EXPECT_FALSE(sequencer_->IsAllDataAvailable());
227 OnFinFrame(3, "def");
228 EXPECT_TRUE(sequencer_->IsClosed());
229 EXPECT_TRUE(sequencer_->IsAllDataAvailable());
230 }
231
TEST_F(QuicStreamSequencerTest,BlockedThenFullFrameAndFinConsumed)232 TEST_F(QuicStreamSequencerTest, BlockedThenFullFrameAndFinConsumed) {
233 sequencer_->SetBlockedUntilFlush();
234
235 OnFinFrame(0, "abc");
236 EXPECT_EQ(3u, NumBufferedBytes());
237 EXPECT_EQ(0u, sequencer_->NumBytesConsumed());
238
239 EXPECT_CALL(stream_, AddBytesConsumed(3));
240 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
241 ConsumeData(3);
242 }));
243 EXPECT_FALSE(sequencer_->IsClosed());
244 EXPECT_TRUE(sequencer_->IsAllDataAvailable());
245 sequencer_->SetUnblocked();
246 EXPECT_TRUE(sequencer_->IsClosed());
247 EXPECT_EQ(0u, NumBufferedBytes());
248 EXPECT_EQ(3u, sequencer_->NumBytesConsumed());
249 }
250
TEST_F(QuicStreamSequencerTest,EmptyFrame)251 TEST_F(QuicStreamSequencerTest, EmptyFrame) {
252 if (!stream_.version().HasIetfQuicFrames()) {
253 EXPECT_CALL(stream_,
254 OnUnrecoverableError(QUIC_EMPTY_STREAM_FRAME_NO_FIN, _));
255 }
256 OnFrame(0, "");
257 EXPECT_EQ(0u, NumBufferedBytes());
258 EXPECT_EQ(0u, sequencer_->NumBytesConsumed());
259 }
260
TEST_F(QuicStreamSequencerTest,EmptyFinFrame)261 TEST_F(QuicStreamSequencerTest, EmptyFinFrame) {
262 EXPECT_CALL(stream_, OnDataAvailable());
263 OnFinFrame(0, "");
264 EXPECT_EQ(0u, NumBufferedBytes());
265 EXPECT_EQ(0u, sequencer_->NumBytesConsumed());
266 EXPECT_TRUE(sequencer_->IsAllDataAvailable());
267 }
268
TEST_F(QuicStreamSequencerTest,PartialFrameConsumed)269 TEST_F(QuicStreamSequencerTest, PartialFrameConsumed) {
270 EXPECT_CALL(stream_, AddBytesConsumed(2));
271 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
272 ConsumeData(2);
273 }));
274
275 OnFrame(0, "abc");
276 EXPECT_EQ(1u, NumBufferedBytes());
277 EXPECT_EQ(2u, sequencer_->NumBytesConsumed());
278 }
279
TEST_F(QuicStreamSequencerTest,NextxFrameNotConsumed)280 TEST_F(QuicStreamSequencerTest, NextxFrameNotConsumed) {
281 EXPECT_CALL(stream_, OnDataAvailable());
282
283 OnFrame(0, "abc");
284 EXPECT_EQ(3u, NumBufferedBytes());
285 EXPECT_EQ(0u, sequencer_->NumBytesConsumed());
286 }
287
TEST_F(QuicStreamSequencerTest,FutureFrameNotProcessed)288 TEST_F(QuicStreamSequencerTest, FutureFrameNotProcessed) {
289 OnFrame(3, "abc");
290 EXPECT_EQ(3u, NumBufferedBytes());
291 EXPECT_EQ(0u, sequencer_->NumBytesConsumed());
292 }
293
TEST_F(QuicStreamSequencerTest,OutOfOrderFrameProcessed)294 TEST_F(QuicStreamSequencerTest, OutOfOrderFrameProcessed) {
295 // Buffer the first
296 OnFrame(6, "ghi");
297 EXPECT_EQ(3u, NumBufferedBytes());
298 EXPECT_EQ(0u, sequencer_->NumBytesConsumed());
299 EXPECT_EQ(3u, sequencer_->NumBytesBuffered());
300 // Buffer the second
301 OnFrame(3, "def");
302 EXPECT_EQ(6u, NumBufferedBytes());
303 EXPECT_EQ(0u, sequencer_->NumBytesConsumed());
304 EXPECT_EQ(6u, sequencer_->NumBytesBuffered());
305
306 EXPECT_CALL(stream_, AddBytesConsumed(9));
307 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
308 ConsumeData(9);
309 }));
310
311 // Now process all of them at once.
312 OnFrame(0, "abc");
313 EXPECT_EQ(9u, sequencer_->NumBytesConsumed());
314 EXPECT_EQ(0u, sequencer_->NumBytesBuffered());
315
316 EXPECT_EQ(0u, NumBufferedBytes());
317 }
318
TEST_F(QuicStreamSequencerTest,BasicHalfCloseOrdered)319 TEST_F(QuicStreamSequencerTest, BasicHalfCloseOrdered) {
320 InSequence s;
321
322 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
323 ConsumeData(3);
324 }));
325 EXPECT_CALL(stream_, AddBytesConsumed(3));
326 OnFinFrame(0, "abc");
327
328 EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
329 }
330
TEST_F(QuicStreamSequencerTest,BasicHalfCloseUnorderedWithFlush)331 TEST_F(QuicStreamSequencerTest, BasicHalfCloseUnorderedWithFlush) {
332 OnFinFrame(6, "");
333 EXPECT_EQ(6u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
334
335 OnFrame(3, "def");
336 EXPECT_CALL(stream_, AddBytesConsumed(6));
337 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
338 ConsumeData(6);
339 }));
340 EXPECT_FALSE(sequencer_->IsClosed());
341 OnFrame(0, "abc");
342 EXPECT_TRUE(sequencer_->IsClosed());
343 }
344
TEST_F(QuicStreamSequencerTest,BasicHalfUnordered)345 TEST_F(QuicStreamSequencerTest, BasicHalfUnordered) {
346 OnFinFrame(3, "");
347 EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
348
349 EXPECT_CALL(stream_, AddBytesConsumed(3));
350 EXPECT_CALL(stream_, OnDataAvailable()).WillOnce(testing::Invoke([this]() {
351 ConsumeData(3);
352 }));
353 EXPECT_FALSE(sequencer_->IsClosed());
354 OnFrame(0, "abc");
355 EXPECT_TRUE(sequencer_->IsClosed());
356 }
357
TEST_F(QuicStreamSequencerTest,TerminateWithReadv)358 TEST_F(QuicStreamSequencerTest, TerminateWithReadv) {
359 char buffer[3];
360
361 OnFinFrame(3, "");
362 EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
363
364 EXPECT_FALSE(sequencer_->IsClosed());
365
366 EXPECT_CALL(stream_, OnDataAvailable());
367 OnFrame(0, "abc");
368
369 EXPECT_CALL(stream_, AddBytesConsumed(3));
370 iovec iov = {&buffer[0], 3};
371 int bytes_read = sequencer_->Readv(&iov, 1);
372 EXPECT_EQ(3, bytes_read);
373 EXPECT_TRUE(sequencer_->IsClosed());
374 }
375
TEST_F(QuicStreamSequencerTest,MultipleOffsets)376 TEST_F(QuicStreamSequencerTest, MultipleOffsets) {
377 OnFinFrame(3, "");
378 EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
379
380 EXPECT_CALL(stream_, OnUnrecoverableError(
381 QUIC_STREAM_SEQUENCER_INVALID_STATE,
382 "Stream 1 received new final offset: 1, which is "
383 "different from close offset: 3"));
384 OnFinFrame(1, "");
385 }
386
387 class QuicSequencerRandomTest : public QuicStreamSequencerTest {
388 public:
389 using Frame = std::pair<int, std::string>;
390 using FrameList = std::vector<Frame>;
391
CreateFrames()392 void CreateFrames() {
393 int payload_size = ABSL_ARRAYSIZE(kPayload) - 1;
394 int remaining_payload = payload_size;
395 while (remaining_payload != 0) {
396 int size = std::min(OneToN(6), remaining_payload);
397 int index = payload_size - remaining_payload;
398 list_.push_back(
399 std::make_pair(index, std::string(kPayload + index, size)));
400 remaining_payload -= size;
401 }
402 }
403
QuicSequencerRandomTest()404 QuicSequencerRandomTest() {
405 uint64_t seed = QuicRandom::GetInstance()->RandUint64();
406 QUIC_LOG(INFO) << "**** The current seed is " << seed << " ****";
407 random_.set_seed(seed);
408
409 CreateFrames();
410 }
411
OneToN(int n)412 int OneToN(int n) { return random_.RandUint64() % n + 1; }
413
ReadAvailableData()414 void ReadAvailableData() {
415 // Read all available data
416 char output[ABSL_ARRAYSIZE(kPayload) + 1];
417 iovec iov;
418 iov.iov_base = output;
419 iov.iov_len = ABSL_ARRAYSIZE(output);
420 int bytes_read = sequencer_->Readv(&iov, 1);
421 EXPECT_NE(0, bytes_read);
422 output_.append(output, bytes_read);
423 }
424
425 std::string output_;
426 // Data which peek at using GetReadableRegion if we back up.
427 std::string peeked_;
428 SimpleRandom random_;
429 FrameList list_;
430 };
431
432 // All frames are processed as soon as we have sequential data.
433 // Infinite buffering, so all frames are acked right away.
TEST_F(QuicSequencerRandomTest,RandomFramesNoDroppingNoBackup)434 TEST_F(QuicSequencerRandomTest, RandomFramesNoDroppingNoBackup) {
435 EXPECT_CALL(stream_, OnDataAvailable())
436 .Times(AnyNumber())
437 .WillRepeatedly(
438 Invoke(this, &QuicSequencerRandomTest::ReadAvailableData));
439 QuicByteCount total_bytes_consumed = 0;
440 EXPECT_CALL(stream_, AddBytesConsumed(_))
441 .Times(AnyNumber())
442 .WillRepeatedly(
443 testing::Invoke([&total_bytes_consumed](QuicByteCount bytes) {
444 total_bytes_consumed += bytes;
445 }));
446
447 while (!list_.empty()) {
448 int index = OneToN(list_.size()) - 1;
449 QUIC_LOG(ERROR) << "Sending index " << index << " " << list_[index].second;
450 OnFrame(list_[index].first, list_[index].second.data());
451
452 list_.erase(list_.begin() + index);
453 }
454
455 ASSERT_EQ(ABSL_ARRAYSIZE(kPayload) - 1, output_.size());
456 EXPECT_EQ(kPayload, output_);
457 EXPECT_EQ(ABSL_ARRAYSIZE(kPayload) - 1, total_bytes_consumed);
458 }
459
TEST_F(QuicSequencerRandomTest,RandomFramesNoDroppingBackup)460 TEST_F(QuicSequencerRandomTest, RandomFramesNoDroppingBackup) {
461 char buffer[10];
462 iovec iov[2];
463 iov[0].iov_base = &buffer[0];
464 iov[0].iov_len = 5;
465 iov[1].iov_base = &buffer[5];
466 iov[1].iov_len = 5;
467
468 EXPECT_CALL(stream_, OnDataAvailable()).Times(AnyNumber());
469 QuicByteCount total_bytes_consumed = 0;
470 EXPECT_CALL(stream_, AddBytesConsumed(_))
471 .Times(AnyNumber())
472 .WillRepeatedly(
473 testing::Invoke([&total_bytes_consumed](QuicByteCount bytes) {
474 total_bytes_consumed += bytes;
475 }));
476
477 while (output_.size() != ABSL_ARRAYSIZE(kPayload) - 1) {
478 if (!list_.empty() && OneToN(2) == 1) { // Send data
479 int index = OneToN(list_.size()) - 1;
480 OnFrame(list_[index].first, list_[index].second.data());
481 list_.erase(list_.begin() + index);
482 } else { // Read data
483 bool has_bytes = sequencer_->HasBytesToRead();
484 iovec peek_iov[20];
485 int iovs_peeked = sequencer_->GetReadableRegions(peek_iov, 20);
486 if (has_bytes) {
487 ASSERT_LT(0, iovs_peeked);
488 ASSERT_TRUE(sequencer_->GetReadableRegion(peek_iov));
489 } else {
490 ASSERT_EQ(0, iovs_peeked);
491 ASSERT_FALSE(sequencer_->GetReadableRegion(peek_iov));
492 }
493 int total_bytes_to_peek = ABSL_ARRAYSIZE(buffer);
494 for (int i = 0; i < iovs_peeked; ++i) {
495 int bytes_to_peek =
496 std::min<int>(peek_iov[i].iov_len, total_bytes_to_peek);
497 peeked_.append(static_cast<char*>(peek_iov[i].iov_base), bytes_to_peek);
498 total_bytes_to_peek -= bytes_to_peek;
499 if (total_bytes_to_peek == 0) {
500 break;
501 }
502 }
503 int bytes_read = sequencer_->Readv(iov, 2);
504 output_.append(buffer, bytes_read);
505 ASSERT_EQ(output_.size(), peeked_.size());
506 }
507 }
508 EXPECT_EQ(std::string(kPayload), output_);
509 EXPECT_EQ(std::string(kPayload), peeked_);
510 EXPECT_EQ(ABSL_ARRAYSIZE(kPayload) - 1, total_bytes_consumed);
511 }
512
513 // Same as above, just using a different method for reading.
TEST_F(QuicStreamSequencerTest,MarkConsumed)514 TEST_F(QuicStreamSequencerTest, MarkConsumed) {
515 InSequence s;
516 EXPECT_CALL(stream_, OnDataAvailable());
517
518 OnFrame(0, "abc");
519 OnFrame(3, "def");
520 OnFrame(6, "ghi");
521
522 // abcdefghi buffered.
523 EXPECT_EQ(9u, sequencer_->NumBytesBuffered());
524
525 // Peek into the data.
526 std::vector<std::string> expected = {"abcdefghi"};
527 ASSERT_TRUE(VerifyReadableRegions(expected));
528
529 // Consume 1 byte.
530 EXPECT_CALL(stream_, AddBytesConsumed(1));
531 sequencer_->MarkConsumed(1);
532 // Verify data.
533 std::vector<std::string> expected2 = {"bcdefghi"};
534 ASSERT_TRUE(VerifyReadableRegions(expected2));
535 EXPECT_EQ(8u, sequencer_->NumBytesBuffered());
536
537 // Consume 2 bytes.
538 EXPECT_CALL(stream_, AddBytesConsumed(2));
539 sequencer_->MarkConsumed(2);
540 // Verify data.
541 std::vector<std::string> expected3 = {"defghi"};
542 ASSERT_TRUE(VerifyReadableRegions(expected3));
543 EXPECT_EQ(6u, sequencer_->NumBytesBuffered());
544
545 // Consume 5 bytes.
546 EXPECT_CALL(stream_, AddBytesConsumed(5));
547 sequencer_->MarkConsumed(5);
548 // Verify data.
549 std::vector<std::string> expected4{"i"};
550 ASSERT_TRUE(VerifyReadableRegions(expected4));
551 EXPECT_EQ(1u, sequencer_->NumBytesBuffered());
552 }
553
TEST_F(QuicStreamSequencerTest,MarkConsumedError)554 TEST_F(QuicStreamSequencerTest, MarkConsumedError) {
555 EXPECT_CALL(stream_, OnDataAvailable());
556
557 OnFrame(0, "abc");
558 OnFrame(9, "jklmnopqrstuvwxyz");
559
560 // Peek into the data. Only the first chunk should be readable because of the
561 // missing data.
562 std::vector<std::string> expected{"abc"};
563 ASSERT_TRUE(VerifyReadableRegions(expected));
564
565 // Now, attempt to mark consumed more data than was readable and expect the
566 // stream to be closed.
567 EXPECT_QUIC_BUG(
568 {
569 EXPECT_CALL(stream_, ResetWithError(QuicResetStreamError::FromInternal(
570 QUIC_ERROR_PROCESSING_STREAM)));
571 sequencer_->MarkConsumed(4);
572 },
573 "Invalid argument to MarkConsumed."
574 " expect to consume: 4, but not enough bytes available.");
575 }
576
TEST_F(QuicStreamSequencerTest,MarkConsumedWithMissingPacket)577 TEST_F(QuicStreamSequencerTest, MarkConsumedWithMissingPacket) {
578 InSequence s;
579 EXPECT_CALL(stream_, OnDataAvailable());
580
581 OnFrame(0, "abc");
582 OnFrame(3, "def");
583 // Missing packet: 6, ghi.
584 OnFrame(9, "jkl");
585
586 std::vector<std::string> expected = {"abcdef"};
587 ASSERT_TRUE(VerifyReadableRegions(expected));
588
589 EXPECT_CALL(stream_, AddBytesConsumed(6));
590 sequencer_->MarkConsumed(6);
591 }
592
TEST_F(QuicStreamSequencerTest,Move)593 TEST_F(QuicStreamSequencerTest, Move) {
594 InSequence s;
595 EXPECT_CALL(stream_, OnDataAvailable());
596
597 OnFrame(0, "abc");
598 OnFrame(3, "def");
599 OnFrame(6, "ghi");
600
601 // abcdefghi buffered.
602 EXPECT_EQ(9u, sequencer_->NumBytesBuffered());
603
604 // Peek into the data.
605 std::vector<std::string> expected = {"abcdefghi"};
606 ASSERT_TRUE(VerifyReadableRegions(expected));
607
608 QuicStreamSequencer sequencer2(std::move(*sequencer_));
609 ASSERT_TRUE(VerifyReadableRegions(sequencer2, expected));
610 }
611
TEST_F(QuicStreamSequencerTest,OverlappingFramesReceived)612 TEST_F(QuicStreamSequencerTest, OverlappingFramesReceived) {
613 // The peer should never send us non-identical stream frames which contain
614 // overlapping byte ranges - if they do, we close the connection.
615 QuicStreamId id = 1;
616
617 QuicStreamFrame frame1(id, false, 1, absl::string_view("hello"));
618 sequencer_->OnStreamFrame(frame1);
619
620 QuicStreamFrame frame2(id, false, 2, absl::string_view("hello"));
621 EXPECT_CALL(stream_, OnUnrecoverableError(QUIC_OVERLAPPING_STREAM_DATA, _))
622 .Times(0);
623 sequencer_->OnStreamFrame(frame2);
624 }
625
TEST_F(QuicStreamSequencerTest,DataAvailableOnOverlappingFrames)626 TEST_F(QuicStreamSequencerTest, DataAvailableOnOverlappingFrames) {
627 QuicStreamId id = 1;
628 const std::string data(1000, '.');
629
630 // Received [0, 1000).
631 QuicStreamFrame frame1(id, false, 0, data);
632 EXPECT_CALL(stream_, OnDataAvailable());
633 sequencer_->OnStreamFrame(frame1);
634 // Consume [0, 500).
635 EXPECT_CALL(stream_, AddBytesConsumed(500));
636 QuicStreamSequencerTest::ConsumeData(500);
637 EXPECT_EQ(500u, sequencer_->NumBytesConsumed());
638 EXPECT_EQ(500u, sequencer_->NumBytesBuffered());
639
640 // Received [500, 1500).
641 QuicStreamFrame frame2(id, false, 500, data);
642 // Do not call OnDataAvailable as there are readable bytes left in the buffer.
643 EXPECT_CALL(stream_, OnDataAvailable()).Times(0);
644 sequencer_->OnStreamFrame(frame2);
645 // Consume [1000, 1500).
646 EXPECT_CALL(stream_, AddBytesConsumed(1000));
647 QuicStreamSequencerTest::ConsumeData(1000);
648 EXPECT_EQ(1500u, sequencer_->NumBytesConsumed());
649 EXPECT_EQ(0u, sequencer_->NumBytesBuffered());
650
651 // Received [1498, 1503).
652 QuicStreamFrame frame3(id, false, 1498, absl::string_view("hello"));
653 EXPECT_CALL(stream_, OnDataAvailable());
654 sequencer_->OnStreamFrame(frame3);
655 EXPECT_CALL(stream_, AddBytesConsumed(3));
656 QuicStreamSequencerTest::ConsumeData(3);
657 EXPECT_EQ(1503u, sequencer_->NumBytesConsumed());
658 EXPECT_EQ(0u, sequencer_->NumBytesBuffered());
659
660 // Received [1000, 1005).
661 QuicStreamFrame frame4(id, false, 1000, absl::string_view("hello"));
662 EXPECT_CALL(stream_, OnDataAvailable()).Times(0);
663 sequencer_->OnStreamFrame(frame4);
664 EXPECT_EQ(1503u, sequencer_->NumBytesConsumed());
665 EXPECT_EQ(0u, sequencer_->NumBytesBuffered());
666 }
667
TEST_F(QuicStreamSequencerTest,OnDataAvailableWhenReadableBytesIncrease)668 TEST_F(QuicStreamSequencerTest, OnDataAvailableWhenReadableBytesIncrease) {
669 sequencer_->set_level_triggered(true);
670 QuicStreamId id = 1;
671
672 // Received [0, 5).
673 QuicStreamFrame frame1(id, false, 0, "hello");
674 EXPECT_CALL(stream_, OnDataAvailable());
675 sequencer_->OnStreamFrame(frame1);
676 EXPECT_EQ(5u, sequencer_->NumBytesBuffered());
677
678 // Without consuming the buffer bytes, continue receiving [5, 11).
679 QuicStreamFrame frame2(id, false, 5, " world");
680 // OnDataAvailable should still be called because there are more data to read.
681 EXPECT_CALL(stream_, OnDataAvailable());
682 sequencer_->OnStreamFrame(frame2);
683 EXPECT_EQ(11u, sequencer_->NumBytesBuffered());
684
685 // Without consuming the buffer bytes, continue receiving [12, 13).
686 QuicStreamFrame frame3(id, false, 5, "a");
687 // OnDataAvailable shouldn't be called becasue there are still only 11 bytes
688 // available.
689 EXPECT_CALL(stream_, OnDataAvailable()).Times(0);
690 sequencer_->OnStreamFrame(frame3);
691 EXPECT_EQ(11u, sequencer_->NumBytesBuffered());
692 }
693
TEST_F(QuicStreamSequencerTest,ReadSingleFrame)694 TEST_F(QuicStreamSequencerTest, ReadSingleFrame) {
695 EXPECT_CALL(stream_, OnDataAvailable());
696 OnFrame(0u, "abc");
697 std::string actual;
698 EXPECT_CALL(stream_, AddBytesConsumed(3));
699 sequencer_->Read(&actual);
700 EXPECT_EQ("abc", actual);
701 EXPECT_EQ(0u, sequencer_->NumBytesBuffered());
702 }
703
TEST_F(QuicStreamSequencerTest,ReadMultipleFramesWithMissingFrame)704 TEST_F(QuicStreamSequencerTest, ReadMultipleFramesWithMissingFrame) {
705 EXPECT_CALL(stream_, OnDataAvailable());
706 OnFrame(0u, "abc");
707 OnFrame(3u, "def");
708 OnFrame(6u, "ghi");
709 OnFrame(10u, "xyz"); // Byte 9 is missing.
710 std::string actual;
711 EXPECT_CALL(stream_, AddBytesConsumed(9));
712 sequencer_->Read(&actual);
713 EXPECT_EQ("abcdefghi", actual);
714 EXPECT_EQ(3u, sequencer_->NumBytesBuffered());
715 }
716
TEST_F(QuicStreamSequencerTest,ReadAndAppendToString)717 TEST_F(QuicStreamSequencerTest, ReadAndAppendToString) {
718 EXPECT_CALL(stream_, OnDataAvailable());
719 OnFrame(0u, "def");
720 OnFrame(3u, "ghi");
721 std::string actual = "abc";
722 EXPECT_CALL(stream_, AddBytesConsumed(6));
723 sequencer_->Read(&actual);
724 EXPECT_EQ("abcdefghi", actual);
725 EXPECT_EQ(0u, sequencer_->NumBytesBuffered());
726 }
727
TEST_F(QuicStreamSequencerTest,StopReading)728 TEST_F(QuicStreamSequencerTest, StopReading) {
729 EXPECT_CALL(stream_, OnDataAvailable()).Times(0);
730 EXPECT_CALL(stream_, OnFinRead());
731
732 EXPECT_CALL(stream_, AddBytesConsumed(0));
733 sequencer_->StopReading();
734
735 EXPECT_CALL(stream_, AddBytesConsumed(3));
736 OnFrame(0u, "abc");
737 EXPECT_CALL(stream_, AddBytesConsumed(3));
738 OnFrame(3u, "def");
739 EXPECT_CALL(stream_, AddBytesConsumed(3));
740 OnFinFrame(6u, "ghi");
741 }
742
TEST_F(QuicStreamSequencerTest,StopReadingWithLevelTriggered)743 TEST_F(QuicStreamSequencerTest, StopReadingWithLevelTriggered) {
744 EXPECT_CALL(stream_, AddBytesConsumed(0));
745 EXPECT_CALL(stream_, AddBytesConsumed(3)).Times(3);
746 EXPECT_CALL(stream_, OnDataAvailable()).Times(0);
747 EXPECT_CALL(stream_, OnFinRead());
748
749 sequencer_->set_level_triggered(true);
750 sequencer_->StopReading();
751
752 OnFrame(0u, "abc");
753 OnFrame(3u, "def");
754 OnFinFrame(6u, "ghi");
755 }
756
757 // Regression test for https://crbug.com/992486.
TEST_F(QuicStreamSequencerTest,CorruptFinFrames)758 TEST_F(QuicStreamSequencerTest, CorruptFinFrames) {
759 EXPECT_CALL(stream_, OnUnrecoverableError(
760 QUIC_STREAM_SEQUENCER_INVALID_STATE,
761 "Stream 1 received new final offset: 1, which is "
762 "different from close offset: 2"));
763
764 OnFinFrame(2u, "");
765 OnFinFrame(0u, "a");
766 EXPECT_FALSE(sequencer_->HasBytesToRead());
767 }
768
769 // Regression test for crbug.com/1015693
TEST_F(QuicStreamSequencerTest,ReceiveFinLessThanHighestOffset)770 TEST_F(QuicStreamSequencerTest, ReceiveFinLessThanHighestOffset) {
771 EXPECT_CALL(stream_, OnDataAvailable()).Times(1);
772 EXPECT_CALL(stream_, OnUnrecoverableError(
773 QUIC_STREAM_SEQUENCER_INVALID_STATE,
774 "Stream 1 received fin with offset: 0, which "
775 "reduces current highest offset: 3"));
776 OnFrame(0u, "abc");
777 OnFinFrame(0u, "");
778 }
779
780 } // namespace
781 } // namespace test
782 } // namespace quic
783