1 // Copyright (c) 2015 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_buffer.h"
6 
7 #include <algorithm>
8 #include <cstddef>
9 #include <cstdint>
10 #include <map>
11 #include <string>
12 #include <utility>
13 
14 #include "absl/strings/str_cat.h"
15 #include "absl/strings/string_view.h"
16 #include "quiche/quic/platform/api/quic_logging.h"
17 #include "quiche/quic/platform/api/quic_test.h"
18 #include "quiche/quic/test_tools/quic_stream_sequencer_buffer_peer.h"
19 #include "quiche/quic/test_tools/quic_test_utils.h"
20 
21 namespace quic {
22 
23 namespace test {
24 
IovecToStringPiece(iovec iov)25 absl::string_view IovecToStringPiece(iovec iov) {
26   return absl::string_view(reinterpret_cast<const char*>(iov.iov_base),
27                            iov.iov_len);
28 }
29 
GetCharFromIOVecs(size_t offset,iovec iov[],size_t count)30 char GetCharFromIOVecs(size_t offset, iovec iov[], size_t count) {
31   size_t start_offset = 0;
32   for (size_t i = 0; i < count; i++) {
33     if (iov[i].iov_len == 0) {
34       continue;
35     }
36     size_t end_offset = start_offset + iov[i].iov_len - 1;
37     if (offset >= start_offset && offset <= end_offset) {
38       const char* buf = reinterpret_cast<const char*>(iov[i].iov_base);
39       return buf[offset - start_offset];
40     }
41     start_offset += iov[i].iov_len;
42   }
43   QUIC_LOG(ERROR) << "Could not locate char at offset " << offset << " in "
44                   << count << " iovecs";
45   for (size_t i = 0; i < count; ++i) {
46     QUIC_LOG(ERROR) << "  iov[" << i << "].iov_len = " << iov[i].iov_len;
47   }
48   return '\0';
49 }
50 
51 const size_t kMaxNumGapsAllowed = 2 * kMaxPacketGap;
52 
53 static const size_t kBlockSizeBytes =
54     QuicStreamSequencerBuffer::kBlockSizeBytes;
55 using BufferBlock = QuicStreamSequencerBuffer::BufferBlock;
56 
57 namespace {
58 
59 class QuicStreamSequencerBufferTest : public QuicTest {
60  public:
SetUp()61   void SetUp() override { Initialize(); }
62 
ResetMaxCapacityBytes(size_t max_capacity_bytes)63   void ResetMaxCapacityBytes(size_t max_capacity_bytes) {
64     max_capacity_bytes_ = max_capacity_bytes;
65     Initialize();
66   }
67 
68  protected:
Initialize()69   void Initialize() {
70     buffer_ =
71         std::make_unique<QuicStreamSequencerBuffer>((max_capacity_bytes_));
72     helper_ = std::make_unique<QuicStreamSequencerBufferPeer>((buffer_.get()));
73   }
74 
75   // Use 8.5 here to make sure that the buffer has more than
76   // QuicStreamSequencerBuffer::kInitialBlockCount block and its end doesn't
77   // align with the end of a block in order to test all the offset calculation.
78   size_t max_capacity_bytes_ = 8.5 * kBlockSizeBytes;
79 
80   std::unique_ptr<QuicStreamSequencerBuffer> buffer_;
81   std::unique_ptr<QuicStreamSequencerBufferPeer> helper_;
82   size_t written_ = 0;
83   std::string error_details_;
84 };
85 
TEST_F(QuicStreamSequencerBufferTest,InitializeWithMaxRecvWindowSize)86 TEST_F(QuicStreamSequencerBufferTest, InitializeWithMaxRecvWindowSize) {
87   ResetMaxCapacityBytes(16 * 1024 * 1024);  // 16MB
88   EXPECT_EQ(2 * 1024u,                      // 16MB / 8KB = 2K
89             helper_->max_blocks_count());
90   EXPECT_EQ(max_capacity_bytes_, helper_->max_buffer_capacity());
91   EXPECT_TRUE(helper_->CheckInitialState());
92 }
93 
TEST_F(QuicStreamSequencerBufferTest,InitializationWithDifferentSizes)94 TEST_F(QuicStreamSequencerBufferTest, InitializationWithDifferentSizes) {
95   const size_t kCapacity = 16 * QuicStreamSequencerBuffer::kBlockSizeBytes;
96   ResetMaxCapacityBytes(kCapacity);
97   EXPECT_EQ(max_capacity_bytes_, helper_->max_buffer_capacity());
98   EXPECT_TRUE(helper_->CheckInitialState());
99 
100   const size_t kCapacity1 = 32 * QuicStreamSequencerBuffer::kBlockSizeBytes;
101   ResetMaxCapacityBytes(kCapacity1);
102   EXPECT_EQ(kCapacity1, helper_->max_buffer_capacity());
103   EXPECT_TRUE(helper_->CheckInitialState());
104 }
105 
TEST_F(QuicStreamSequencerBufferTest,ClearOnEmpty)106 TEST_F(QuicStreamSequencerBufferTest, ClearOnEmpty) {
107   buffer_->Clear();
108   EXPECT_TRUE(helper_->CheckBufferInvariants());
109 }
110 
TEST_F(QuicStreamSequencerBufferTest,OnStreamData0length)111 TEST_F(QuicStreamSequencerBufferTest, OnStreamData0length) {
112   QuicErrorCode error =
113       buffer_->OnStreamData(800, "", &written_, &error_details_);
114   EXPECT_THAT(error, IsError(QUIC_EMPTY_STREAM_FRAME_NO_FIN));
115   EXPECT_TRUE(helper_->CheckBufferInvariants());
116 }
117 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataWithinBlock)118 TEST_F(QuicStreamSequencerBufferTest, OnStreamDataWithinBlock) {
119   EXPECT_FALSE(helper_->IsBufferAllocated());
120   std::string source(1024, 'a');
121   EXPECT_THAT(buffer_->OnStreamData(800, source, &written_, &error_details_),
122               IsQuicNoError());
123   BufferBlock* block_ptr = helper_->GetBlock(0);
124   for (size_t i = 0; i < source.size(); ++i) {
125     ASSERT_EQ('a', block_ptr->buffer[helper_->GetInBlockOffset(800) + i]);
126   }
127   EXPECT_EQ(2, helper_->IntervalSize());
128   EXPECT_EQ(0u, helper_->ReadableBytes());
129   EXPECT_EQ(1u, helper_->bytes_received().Size());
130   EXPECT_EQ(800u, helper_->bytes_received().begin()->min());
131   EXPECT_EQ(1824u, helper_->bytes_received().begin()->max());
132   EXPECT_TRUE(helper_->CheckBufferInvariants());
133   EXPECT_TRUE(helper_->IsBufferAllocated());
134 }
135 
TEST_F(QuicStreamSequencerBufferTest,Move)136 TEST_F(QuicStreamSequencerBufferTest, Move) {
137   EXPECT_FALSE(helper_->IsBufferAllocated());
138   std::string source(1024, 'a');
139   EXPECT_THAT(buffer_->OnStreamData(800, source, &written_, &error_details_),
140               IsQuicNoError());
141   BufferBlock* block_ptr = helper_->GetBlock(0);
142   for (size_t i = 0; i < source.size(); ++i) {
143     ASSERT_EQ('a', block_ptr->buffer[helper_->GetInBlockOffset(800) + i]);
144   }
145 
146   QuicStreamSequencerBuffer buffer2(std::move(*buffer_));
147   QuicStreamSequencerBufferPeer helper2(&buffer2);
148 
149   EXPECT_FALSE(helper_->IsBufferAllocated());
150 
151   EXPECT_EQ(2, helper2.IntervalSize());
152   EXPECT_EQ(0u, helper2.ReadableBytes());
153   EXPECT_EQ(1u, helper2.bytes_received().Size());
154   EXPECT_EQ(800u, helper2.bytes_received().begin()->min());
155   EXPECT_EQ(1824u, helper2.bytes_received().begin()->max());
156   EXPECT_TRUE(helper2.CheckBufferInvariants());
157   EXPECT_TRUE(helper2.IsBufferAllocated());
158 }
159 
TEST_F(QuicStreamSequencerBufferTest,DISABLED_OnStreamDataInvalidSource)160 TEST_F(QuicStreamSequencerBufferTest, DISABLED_OnStreamDataInvalidSource) {
161   // Pass in an invalid source, expects to return error.
162   absl::string_view source;
163   source = absl::string_view(nullptr, 1024);
164   EXPECT_THAT(buffer_->OnStreamData(800, source, &written_, &error_details_),
165               IsError(QUIC_STREAM_SEQUENCER_INVALID_STATE));
166   EXPECT_EQ(0u, error_details_.find(absl::StrCat(
167                     "QuicStreamSequencerBuffer error: OnStreamData() "
168                     "dest == nullptr: ",
169                     false, " source == nullptr: ", true)));
170 }
171 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataWithOverlap)172 TEST_F(QuicStreamSequencerBufferTest, OnStreamDataWithOverlap) {
173   std::string source(1024, 'a');
174   // Write something into [800, 1824)
175   EXPECT_THAT(buffer_->OnStreamData(800, source, &written_, &error_details_),
176               IsQuicNoError());
177   // Try to write to [0, 1024) and [1024, 2048).
178   EXPECT_THAT(buffer_->OnStreamData(0, source, &written_, &error_details_),
179               IsQuicNoError());
180   EXPECT_THAT(buffer_->OnStreamData(1024, source, &written_, &error_details_),
181               IsQuicNoError());
182 }
183 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataOverlapAndDuplicateCornerCases)184 TEST_F(QuicStreamSequencerBufferTest,
185        OnStreamDataOverlapAndDuplicateCornerCases) {
186   std::string source(1024, 'a');
187   // Write something into [800, 1824)
188   buffer_->OnStreamData(800, source, &written_, &error_details_);
189   source = std::string(800, 'b');
190   std::string one_byte = "c";
191   // Write [1, 801).
192   EXPECT_THAT(buffer_->OnStreamData(1, source, &written_, &error_details_),
193               IsQuicNoError());
194   // Write [0, 800).
195   EXPECT_THAT(buffer_->OnStreamData(0, source, &written_, &error_details_),
196               IsQuicNoError());
197   // Write [1823, 1824).
198   EXPECT_THAT(buffer_->OnStreamData(1823, one_byte, &written_, &error_details_),
199               IsQuicNoError());
200   EXPECT_EQ(0u, written_);
201   // write one byte to [1824, 1825)
202   EXPECT_THAT(buffer_->OnStreamData(1824, one_byte, &written_, &error_details_),
203               IsQuicNoError());
204   EXPECT_TRUE(helper_->CheckBufferInvariants());
205 }
206 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataWithoutOverlap)207 TEST_F(QuicStreamSequencerBufferTest, OnStreamDataWithoutOverlap) {
208   std::string source(1024, 'a');
209   // Write something into [800, 1824).
210   EXPECT_THAT(buffer_->OnStreamData(800, source, &written_, &error_details_),
211               IsQuicNoError());
212   source = std::string(100, 'b');
213   // Write something into [kBlockSizeBytes * 2 - 20, kBlockSizeBytes * 2 + 80).
214   EXPECT_THAT(buffer_->OnStreamData(kBlockSizeBytes * 2 - 20, source, &written_,
215                                     &error_details_),
216               IsQuicNoError());
217   EXPECT_EQ(3, helper_->IntervalSize());
218   EXPECT_EQ(1024u + 100u, buffer_->BytesBuffered());
219   EXPECT_TRUE(helper_->CheckBufferInvariants());
220 }
221 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataInLongStreamWithOverlap)222 TEST_F(QuicStreamSequencerBufferTest, OnStreamDataInLongStreamWithOverlap) {
223   // Assume a stream has already buffered almost 4GB.
224   uint64_t total_bytes_read = pow(2, 32) - 1;
225   helper_->set_total_bytes_read(total_bytes_read);
226   helper_->AddBytesReceived(0, total_bytes_read);
227 
228   // Three new out of order frames arrive.
229   const size_t kBytesToWrite = 100;
230   std::string source(kBytesToWrite, 'a');
231   // Frame [2^32 + 500, 2^32 + 600).
232   QuicStreamOffset offset = pow(2, 32) + 500;
233   EXPECT_THAT(buffer_->OnStreamData(offset, source, &written_, &error_details_),
234               IsQuicNoError());
235   EXPECT_EQ(2, helper_->IntervalSize());
236 
237   // Frame [2^32 + 700, 2^32 + 800).
238   offset = pow(2, 32) + 700;
239   EXPECT_THAT(buffer_->OnStreamData(offset, source, &written_, &error_details_),
240               IsQuicNoError());
241   EXPECT_EQ(3, helper_->IntervalSize());
242 
243   // Another frame [2^32 + 300, 2^32 + 400).
244   offset = pow(2, 32) + 300;
245   EXPECT_THAT(buffer_->OnStreamData(offset, source, &written_, &error_details_),
246               IsQuicNoError());
247   EXPECT_EQ(4, helper_->IntervalSize());
248 }
249 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataTillEnd)250 TEST_F(QuicStreamSequencerBufferTest, OnStreamDataTillEnd) {
251   // Write 50 bytes to the end.
252   const size_t kBytesToWrite = 50;
253   std::string source(kBytesToWrite, 'a');
254   EXPECT_THAT(buffer_->OnStreamData(max_capacity_bytes_ - kBytesToWrite, source,
255                                     &written_, &error_details_),
256               IsQuicNoError());
257   EXPECT_EQ(50u, buffer_->BytesBuffered());
258   EXPECT_TRUE(helper_->CheckBufferInvariants());
259 }
260 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataTillEndCorner)261 TEST_F(QuicStreamSequencerBufferTest, OnStreamDataTillEndCorner) {
262   // Write 1 byte to the end.
263   const size_t kBytesToWrite = 1;
264   std::string source(kBytesToWrite, 'a');
265   EXPECT_THAT(buffer_->OnStreamData(max_capacity_bytes_ - kBytesToWrite, source,
266                                     &written_, &error_details_),
267               IsQuicNoError());
268   EXPECT_EQ(1u, buffer_->BytesBuffered());
269   EXPECT_TRUE(helper_->CheckBufferInvariants());
270 }
271 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataBeyondCapacity)272 TEST_F(QuicStreamSequencerBufferTest, OnStreamDataBeyondCapacity) {
273   std::string source(60, 'a');
274   EXPECT_THAT(buffer_->OnStreamData(max_capacity_bytes_ - 50, source, &written_,
275                                     &error_details_),
276               IsError(QUIC_INTERNAL_ERROR));
277   EXPECT_TRUE(helper_->CheckBufferInvariants());
278 
279   source = "b";
280   EXPECT_THAT(buffer_->OnStreamData(max_capacity_bytes_, source, &written_,
281                                     &error_details_),
282               IsError(QUIC_INTERNAL_ERROR));
283   EXPECT_TRUE(helper_->CheckBufferInvariants());
284 
285   EXPECT_THAT(buffer_->OnStreamData(max_capacity_bytes_ * 1000, source,
286                                     &written_, &error_details_),
287               IsError(QUIC_INTERNAL_ERROR));
288   EXPECT_TRUE(helper_->CheckBufferInvariants());
289 
290   // Disallow current_gap != gaps_.end()
291   EXPECT_THAT(buffer_->OnStreamData(static_cast<QuicStreamOffset>(-1), source,
292                                     &written_, &error_details_),
293               IsError(QUIC_INTERNAL_ERROR));
294   EXPECT_TRUE(helper_->CheckBufferInvariants());
295 
296   // Disallow offset + size overflow
297   source = "bbb";
298   EXPECT_THAT(buffer_->OnStreamData(static_cast<QuicStreamOffset>(-2), source,
299                                     &written_, &error_details_),
300               IsError(QUIC_INTERNAL_ERROR));
301   EXPECT_TRUE(helper_->CheckBufferInvariants());
302   EXPECT_EQ(0u, buffer_->BytesBuffered());
303 }
304 
TEST_F(QuicStreamSequencerBufferTest,Readv100Bytes)305 TEST_F(QuicStreamSequencerBufferTest, Readv100Bytes) {
306   std::string source(1024, 'a');
307   // Write something into [kBlockSizeBytes, kBlockSizeBytes + 1024).
308   buffer_->OnStreamData(kBlockSizeBytes, source, &written_, &error_details_);
309   EXPECT_FALSE(buffer_->HasBytesToRead());
310   source = std::string(100, 'b');
311   // Write something into [0, 100).
312   buffer_->OnStreamData(0, source, &written_, &error_details_);
313   EXPECT_TRUE(buffer_->HasBytesToRead());
314   // Read into a iovec array with total capacity of 120 bytes.
315   char dest[120];
316   iovec iovecs[3]{iovec{dest, 40}, iovec{dest + 40, 40}, iovec{dest + 80, 40}};
317   size_t read;
318   EXPECT_THAT(buffer_->Readv(iovecs, 3, &read, &error_details_),
319               IsQuicNoError());
320   QUIC_LOG(ERROR) << error_details_;
321   EXPECT_EQ(100u, read);
322   EXPECT_EQ(100u, buffer_->BytesConsumed());
323   EXPECT_EQ(source, absl::string_view(dest, read));
324   // The first block should be released as its data has been read out.
325   EXPECT_EQ(nullptr, helper_->GetBlock(0));
326   EXPECT_TRUE(helper_->CheckBufferInvariants());
327 }
328 
TEST_F(QuicStreamSequencerBufferTest,ReadvAcrossBlocks)329 TEST_F(QuicStreamSequencerBufferTest, ReadvAcrossBlocks) {
330   std::string source(kBlockSizeBytes + 50, 'a');
331   // Write 1st block to full and extand 50 bytes to next block.
332   buffer_->OnStreamData(0, source, &written_, &error_details_);
333   EXPECT_EQ(source.size(), helper_->ReadableBytes());
334   // Iteratively read 512 bytes from buffer_-> Overwrite dest[] each time.
335   char dest[512];
336   while (helper_->ReadableBytes()) {
337     std::fill(dest, dest + 512, 0);
338     iovec iovecs[2]{iovec{dest, 256}, iovec{dest + 256, 256}};
339     size_t read;
340     EXPECT_THAT(buffer_->Readv(iovecs, 2, &read, &error_details_),
341                 IsQuicNoError());
342   }
343   // The last read only reads the rest 50 bytes in 2nd block.
344   EXPECT_EQ(std::string(50, 'a'), std::string(dest, 50));
345   EXPECT_EQ(0, dest[50]) << "Dest[50] shouln't be filled.";
346   EXPECT_EQ(source.size(), buffer_->BytesConsumed());
347   EXPECT_TRUE(buffer_->Empty());
348   EXPECT_TRUE(helper_->CheckBufferInvariants());
349 }
350 
TEST_F(QuicStreamSequencerBufferTest,ClearAfterRead)351 TEST_F(QuicStreamSequencerBufferTest, ClearAfterRead) {
352   std::string source(kBlockSizeBytes + 50, 'a');
353   // Write 1st block to full with 'a'.
354   buffer_->OnStreamData(0, source, &written_, &error_details_);
355   // Read first 512 bytes from buffer to make space at the beginning.
356   char dest[512]{0};
357   const iovec iov{dest, 512};
358   size_t read;
359   EXPECT_THAT(buffer_->Readv(&iov, 1, &read, &error_details_), IsQuicNoError());
360   // Clear() should make buffer empty while preserving BytesConsumed()
361   buffer_->Clear();
362   EXPECT_TRUE(buffer_->Empty());
363   EXPECT_TRUE(helper_->CheckBufferInvariants());
364 }
365 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataAcrossLastBlockAndFillCapacity)366 TEST_F(QuicStreamSequencerBufferTest,
367        OnStreamDataAcrossLastBlockAndFillCapacity) {
368   std::string source(kBlockSizeBytes + 50, 'a');
369   // Write 1st block to full with 'a'.
370   buffer_->OnStreamData(0, source, &written_, &error_details_);
371   // Read first 512 bytes from buffer to make space at the beginning.
372   char dest[512]{0};
373   const iovec iov{dest, 512};
374   size_t read;
375   EXPECT_THAT(buffer_->Readv(&iov, 1, &read, &error_details_), IsQuicNoError());
376   EXPECT_EQ(source.size(), written_);
377 
378   // Write more than half block size of bytes in the last block with 'b', which
379   // will wrap to the beginning and reaches the full capacity.
380   source = std::string(0.5 * kBlockSizeBytes + 512, 'b');
381   EXPECT_THAT(buffer_->OnStreamData(2 * kBlockSizeBytes, source, &written_,
382                                     &error_details_),
383               IsQuicNoError());
384   EXPECT_EQ(source.size(), written_);
385   EXPECT_TRUE(helper_->CheckBufferInvariants());
386 }
387 
TEST_F(QuicStreamSequencerBufferTest,OnStreamDataAcrossLastBlockAndExceedCapacity)388 TEST_F(QuicStreamSequencerBufferTest,
389        OnStreamDataAcrossLastBlockAndExceedCapacity) {
390   std::string source(kBlockSizeBytes + 50, 'a');
391   // Write 1st block to full.
392   buffer_->OnStreamData(0, source, &written_, &error_details_);
393   // Read first 512 bytes from buffer to make space at the beginning.
394   char dest[512]{0};
395   const iovec iov{dest, 512};
396   size_t read;
397   EXPECT_THAT(buffer_->Readv(&iov, 1, &read, &error_details_), IsQuicNoError());
398 
399   // Try to write from [max_capacity_bytes_ - 0.5 * kBlockSizeBytes,
400   // max_capacity_bytes_ +  512 + 1). But last bytes exceeds current capacity.
401   source = std::string(0.5 * kBlockSizeBytes + 512 + 1, 'b');
402   EXPECT_THAT(buffer_->OnStreamData(8 * kBlockSizeBytes, source, &written_,
403                                     &error_details_),
404               IsError(QUIC_INTERNAL_ERROR));
405   EXPECT_TRUE(helper_->CheckBufferInvariants());
406 }
407 
TEST_F(QuicStreamSequencerBufferTest,ReadvAcrossLastBlock)408 TEST_F(QuicStreamSequencerBufferTest, ReadvAcrossLastBlock) {
409   // Write to full capacity and read out 512 bytes at beginning and continue
410   // appending 256 bytes.
411   std::string source(max_capacity_bytes_, 'a');
412   buffer_->OnStreamData(0, source, &written_, &error_details_);
413   char dest[512]{0};
414   const iovec iov{dest, 512};
415   size_t read;
416   EXPECT_THAT(buffer_->Readv(&iov, 1, &read, &error_details_), IsQuicNoError());
417   source = std::string(256, 'b');
418   buffer_->OnStreamData(max_capacity_bytes_, source, &written_,
419                         &error_details_);
420   EXPECT_TRUE(helper_->CheckBufferInvariants());
421 
422   // Read all data out.
423   std::unique_ptr<char[]> dest1{new char[max_capacity_bytes_]};
424   dest1[0] = 0;
425   const iovec iov1{dest1.get(), max_capacity_bytes_};
426   EXPECT_THAT(buffer_->Readv(&iov1, 1, &read, &error_details_),
427               IsQuicNoError());
428   EXPECT_EQ(max_capacity_bytes_ - 512 + 256, read);
429   EXPECT_EQ(max_capacity_bytes_ + 256, buffer_->BytesConsumed());
430   EXPECT_TRUE(buffer_->Empty());
431   EXPECT_TRUE(helper_->CheckBufferInvariants());
432 }
433 
TEST_F(QuicStreamSequencerBufferTest,ReadvEmpty)434 TEST_F(QuicStreamSequencerBufferTest, ReadvEmpty) {
435   char dest[512]{0};
436   iovec iov{dest, 512};
437   size_t read;
438   EXPECT_THAT(buffer_->Readv(&iov, 1, &read, &error_details_), IsQuicNoError());
439   EXPECT_EQ(0u, read);
440   EXPECT_TRUE(helper_->CheckBufferInvariants());
441 }
442 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionsEmpty)443 TEST_F(QuicStreamSequencerBufferTest, GetReadableRegionsEmpty) {
444   iovec iovs[2];
445   int iov_count = buffer_->GetReadableRegions(iovs, 2);
446   EXPECT_EQ(0, iov_count);
447   EXPECT_EQ(nullptr, iovs[iov_count].iov_base);
448   EXPECT_EQ(0u, iovs[iov_count].iov_len);
449 }
450 
TEST_F(QuicStreamSequencerBufferTest,ReleaseWholeBuffer)451 TEST_F(QuicStreamSequencerBufferTest, ReleaseWholeBuffer) {
452   // Tests that buffer is not deallocated unless ReleaseWholeBuffer() is called.
453   std::string source(100, 'b');
454   // Write something into [0, 100).
455   buffer_->OnStreamData(0, source, &written_, &error_details_);
456   EXPECT_TRUE(buffer_->HasBytesToRead());
457   char dest[120];
458   iovec iovecs[3]{iovec{dest, 40}, iovec{dest + 40, 40}, iovec{dest + 80, 40}};
459   size_t read;
460   EXPECT_THAT(buffer_->Readv(iovecs, 3, &read, &error_details_),
461               IsQuicNoError());
462   EXPECT_EQ(100u, read);
463   EXPECT_EQ(100u, buffer_->BytesConsumed());
464   EXPECT_TRUE(helper_->CheckBufferInvariants());
465   EXPECT_TRUE(helper_->IsBufferAllocated());
466   buffer_->ReleaseWholeBuffer();
467   EXPECT_FALSE(helper_->IsBufferAllocated());
468 }
469 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionsBlockedByGap)470 TEST_F(QuicStreamSequencerBufferTest, GetReadableRegionsBlockedByGap) {
471   // Write into [1, 1024).
472   std::string source(1023, 'a');
473   buffer_->OnStreamData(1, source, &written_, &error_details_);
474   // Try to get readable regions, but none is there.
475   iovec iovs[2];
476   int iov_count = buffer_->GetReadableRegions(iovs, 2);
477   EXPECT_EQ(0, iov_count);
478 }
479 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionsTillEndOfBlock)480 TEST_F(QuicStreamSequencerBufferTest, GetReadableRegionsTillEndOfBlock) {
481   // Write first block to full with [0, 256) 'a' and the rest 'b' then read out
482   // [0, 256)
483   std::string source(kBlockSizeBytes, 'a');
484   buffer_->OnStreamData(0, source, &written_, &error_details_);
485   char dest[256];
486   helper_->Read(dest, 256);
487   // Get readable region from [256, 1024)
488   iovec iovs[2];
489   int iov_count = buffer_->GetReadableRegions(iovs, 2);
490   EXPECT_EQ(1, iov_count);
491   EXPECT_EQ(std::string(kBlockSizeBytes - 256, 'a'),
492             IovecToStringPiece(iovs[0]));
493 }
494 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionsWithinOneBlock)495 TEST_F(QuicStreamSequencerBufferTest, GetReadableRegionsWithinOneBlock) {
496   // Write into [0, 1024) and then read out [0, 256)
497   std::string source(1024, 'a');
498   buffer_->OnStreamData(0, source, &written_, &error_details_);
499   char dest[256];
500   helper_->Read(dest, 256);
501   // Get readable region from [256, 1024)
502   iovec iovs[2];
503   int iov_count = buffer_->GetReadableRegions(iovs, 2);
504   EXPECT_EQ(1, iov_count);
505   EXPECT_EQ(std::string(1024 - 256, 'a'), IovecToStringPiece(iovs[0]));
506 }
507 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionsAcrossBlockWithLongIOV)508 TEST_F(QuicStreamSequencerBufferTest,
509        GetReadableRegionsAcrossBlockWithLongIOV) {
510   // Write into [0, 2 * kBlockSizeBytes + 1024) and then read out [0, 1024)
511   std::string source(2 * kBlockSizeBytes + 1024, 'a');
512   buffer_->OnStreamData(0, source, &written_, &error_details_);
513   char dest[1024];
514   helper_->Read(dest, 1024);
515 
516   iovec iovs[4];
517   int iov_count = buffer_->GetReadableRegions(iovs, 4);
518   EXPECT_EQ(3, iov_count);
519   EXPECT_EQ(kBlockSizeBytes - 1024, iovs[0].iov_len);
520   EXPECT_EQ(kBlockSizeBytes, iovs[1].iov_len);
521   EXPECT_EQ(1024u, iovs[2].iov_len);
522 }
523 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionsWithMultipleIOVsAcrossEnd)524 TEST_F(QuicStreamSequencerBufferTest,
525        GetReadableRegionsWithMultipleIOVsAcrossEnd) {
526   // Write into [0, 8.5 * kBlockSizeBytes - 1024) and then read out [0, 1024)
527   // and then append 1024 + 512 bytes.
528   std::string source(8.5 * kBlockSizeBytes - 1024, 'a');
529   buffer_->OnStreamData(0, source, &written_, &error_details_);
530   char dest[1024];
531   helper_->Read(dest, 1024);
532   // Write across the end.
533   source = std::string(1024 + 512, 'b');
534   buffer_->OnStreamData(8.5 * kBlockSizeBytes - 1024, source, &written_,
535                         &error_details_);
536   // Use short iovec's.
537   iovec iovs[2];
538   int iov_count = buffer_->GetReadableRegions(iovs, 2);
539   EXPECT_EQ(2, iov_count);
540   EXPECT_EQ(kBlockSizeBytes - 1024, iovs[0].iov_len);
541   EXPECT_EQ(kBlockSizeBytes, iovs[1].iov_len);
542   // Use long iovec's and wrap the end of buffer.
543   iovec iovs1[11];
544   EXPECT_EQ(10, buffer_->GetReadableRegions(iovs1, 11));
545   EXPECT_EQ(0.5 * kBlockSizeBytes, iovs1[8].iov_len);
546   EXPECT_EQ(512u, iovs1[9].iov_len);
547   EXPECT_EQ(std::string(512, 'b'), IovecToStringPiece(iovs1[9]));
548 }
549 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionEmpty)550 TEST_F(QuicStreamSequencerBufferTest, GetReadableRegionEmpty) {
551   iovec iov;
552   EXPECT_FALSE(buffer_->GetReadableRegion(&iov));
553   EXPECT_EQ(nullptr, iov.iov_base);
554   EXPECT_EQ(0u, iov.iov_len);
555 }
556 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionBeforeGap)557 TEST_F(QuicStreamSequencerBufferTest, GetReadableRegionBeforeGap) {
558   // Write into [1, 1024).
559   std::string source(1023, 'a');
560   buffer_->OnStreamData(1, source, &written_, &error_details_);
561   // GetReadableRegion should return false because range  [0,1) hasn't been
562   // filled yet.
563   iovec iov;
564   EXPECT_FALSE(buffer_->GetReadableRegion(&iov));
565 }
566 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionTillEndOfBlock)567 TEST_F(QuicStreamSequencerBufferTest, GetReadableRegionTillEndOfBlock) {
568   // Write into [0, kBlockSizeBytes + 1) and then read out [0, 256)
569   std::string source(kBlockSizeBytes + 1, 'a');
570   buffer_->OnStreamData(0, source, &written_, &error_details_);
571   char dest[256];
572   helper_->Read(dest, 256);
573   // Get readable region from [256, 1024)
574   iovec iov;
575   EXPECT_TRUE(buffer_->GetReadableRegion(&iov));
576   EXPECT_EQ(std::string(kBlockSizeBytes - 256, 'a'), IovecToStringPiece(iov));
577 }
578 
TEST_F(QuicStreamSequencerBufferTest,GetReadableRegionTillGap)579 TEST_F(QuicStreamSequencerBufferTest, GetReadableRegionTillGap) {
580   // Write into [0, kBlockSizeBytes - 1) and then read out [0, 256)
581   std::string source(kBlockSizeBytes - 1, 'a');
582   buffer_->OnStreamData(0, source, &written_, &error_details_);
583   char dest[256];
584   helper_->Read(dest, 256);
585   // Get readable region from [256, 1023)
586   iovec iov;
587   EXPECT_TRUE(buffer_->GetReadableRegion(&iov));
588   EXPECT_EQ(std::string(kBlockSizeBytes - 1 - 256, 'a'),
589             IovecToStringPiece(iov));
590 }
591 
TEST_F(QuicStreamSequencerBufferTest,PeekEmptyBuffer)592 TEST_F(QuicStreamSequencerBufferTest, PeekEmptyBuffer) {
593   iovec iov;
594   EXPECT_FALSE(buffer_->PeekRegion(0, &iov));
595   EXPECT_FALSE(buffer_->PeekRegion(1, &iov));
596   EXPECT_FALSE(buffer_->PeekRegion(100, &iov));
597 }
598 
TEST_F(QuicStreamSequencerBufferTest,PeekSingleBlock)599 TEST_F(QuicStreamSequencerBufferTest, PeekSingleBlock) {
600   std::string source(kBlockSizeBytes, 'a');
601   buffer_->OnStreamData(0, source, &written_, &error_details_);
602 
603   iovec iov;
604   EXPECT_TRUE(buffer_->PeekRegion(0, &iov));
605   EXPECT_EQ(source, IovecToStringPiece(iov));
606 
607   // Peeking again gives the same result.
608   EXPECT_TRUE(buffer_->PeekRegion(0, &iov));
609   EXPECT_EQ(source, IovecToStringPiece(iov));
610 
611   // Peek at a different offset.
612   EXPECT_TRUE(buffer_->PeekRegion(100, &iov));
613   EXPECT_EQ(absl::string_view(source).substr(100), IovecToStringPiece(iov));
614 
615   // Peeking at or after FirstMissingByte() returns false.
616   EXPECT_FALSE(buffer_->PeekRegion(kBlockSizeBytes, &iov));
617   EXPECT_FALSE(buffer_->PeekRegion(kBlockSizeBytes + 1, &iov));
618 }
619 
TEST_F(QuicStreamSequencerBufferTest,PeekTwoWritesInSingleBlock)620 TEST_F(QuicStreamSequencerBufferTest, PeekTwoWritesInSingleBlock) {
621   const size_t length1 = 1024;
622   std::string source1(length1, 'a');
623   buffer_->OnStreamData(0, source1, &written_, &error_details_);
624 
625   iovec iov;
626   EXPECT_TRUE(buffer_->PeekRegion(0, &iov));
627   EXPECT_EQ(source1, IovecToStringPiece(iov));
628 
629   // The second frame goes into the same block.
630   const size_t length2 = 800;
631   std::string source2(length2, 'b');
632   buffer_->OnStreamData(length1, source2, &written_, &error_details_);
633 
634   EXPECT_TRUE(buffer_->PeekRegion(length1, &iov));
635   EXPECT_EQ(source2, IovecToStringPiece(iov));
636 
637   // Peek with an offset inside the first write.
638   const QuicStreamOffset offset1 = 500;
639   EXPECT_TRUE(buffer_->PeekRegion(offset1, &iov));
640   EXPECT_EQ(absl::string_view(source1).substr(offset1),
641             IovecToStringPiece(iov).substr(0, length1 - offset1));
642   EXPECT_EQ(absl::string_view(source2),
643             IovecToStringPiece(iov).substr(length1 - offset1));
644 
645   // Peek with an offset inside the second write.
646   const QuicStreamOffset offset2 = 1500;
647   EXPECT_TRUE(buffer_->PeekRegion(offset2, &iov));
648   EXPECT_EQ(absl::string_view(source2).substr(offset2 - length1),
649             IovecToStringPiece(iov));
650 
651   // Peeking at or after FirstMissingByte() returns false.
652   EXPECT_FALSE(buffer_->PeekRegion(length1 + length2, &iov));
653   EXPECT_FALSE(buffer_->PeekRegion(length1 + length2 + 1, &iov));
654 }
655 
TEST_F(QuicStreamSequencerBufferTest,PeekBufferWithMultipleBlocks)656 TEST_F(QuicStreamSequencerBufferTest, PeekBufferWithMultipleBlocks) {
657   const size_t length1 = 1024;
658   std::string source1(length1, 'a');
659   buffer_->OnStreamData(0, source1, &written_, &error_details_);
660 
661   iovec iov;
662   EXPECT_TRUE(buffer_->PeekRegion(0, &iov));
663   EXPECT_EQ(source1, IovecToStringPiece(iov));
664 
665   const size_t length2 = kBlockSizeBytes + 2;
666   std::string source2(length2, 'b');
667   buffer_->OnStreamData(length1, source2, &written_, &error_details_);
668 
669   // Peek with offset 0 returns the entire block.
670   EXPECT_TRUE(buffer_->PeekRegion(0, &iov));
671   EXPECT_EQ(kBlockSizeBytes, iov.iov_len);
672   EXPECT_EQ(source1, IovecToStringPiece(iov).substr(0, length1));
673   EXPECT_EQ(absl::string_view(source2).substr(0, kBlockSizeBytes - length1),
674             IovecToStringPiece(iov).substr(length1));
675 
676   EXPECT_TRUE(buffer_->PeekRegion(length1, &iov));
677   EXPECT_EQ(absl::string_view(source2).substr(0, kBlockSizeBytes - length1),
678             IovecToStringPiece(iov));
679 
680   EXPECT_TRUE(buffer_->PeekRegion(kBlockSizeBytes, &iov));
681   EXPECT_EQ(absl::string_view(source2).substr(kBlockSizeBytes - length1),
682             IovecToStringPiece(iov));
683 
684   // Peeking at or after FirstMissingByte() returns false.
685   EXPECT_FALSE(buffer_->PeekRegion(length1 + length2, &iov));
686   EXPECT_FALSE(buffer_->PeekRegion(length1 + length2 + 1, &iov));
687 }
688 
TEST_F(QuicStreamSequencerBufferTest,PeekAfterConsumed)689 TEST_F(QuicStreamSequencerBufferTest, PeekAfterConsumed) {
690   std::string source1(kBlockSizeBytes, 'a');
691   buffer_->OnStreamData(0, source1, &written_, &error_details_);
692 
693   iovec iov;
694   EXPECT_TRUE(buffer_->PeekRegion(0, &iov));
695   EXPECT_EQ(source1, IovecToStringPiece(iov));
696 
697   // Consume some data.
698   EXPECT_TRUE(buffer_->MarkConsumed(1024));
699 
700   // Peeking into consumed data fails.
701   EXPECT_FALSE(buffer_->PeekRegion(0, &iov));
702   EXPECT_FALSE(buffer_->PeekRegion(512, &iov));
703 
704   EXPECT_TRUE(buffer_->PeekRegion(1024, &iov));
705   EXPECT_EQ(absl::string_view(source1).substr(1024), IovecToStringPiece(iov));
706 
707   EXPECT_TRUE(buffer_->PeekRegion(1500, &iov));
708   EXPECT_EQ(absl::string_view(source1).substr(1500), IovecToStringPiece(iov));
709 
710   // Consume rest of block.
711   EXPECT_TRUE(buffer_->MarkConsumed(kBlockSizeBytes - 1024));
712 
713   // Read new data.
714   std::string source2(300, 'b');
715   buffer_->OnStreamData(kBlockSizeBytes, source2, &written_, &error_details_);
716 
717   // Peek into new data.
718   EXPECT_TRUE(buffer_->PeekRegion(kBlockSizeBytes, &iov));
719   EXPECT_EQ(source2, IovecToStringPiece(iov));
720 
721   EXPECT_TRUE(buffer_->PeekRegion(kBlockSizeBytes + 128, &iov));
722   EXPECT_EQ(absl::string_view(source2).substr(128), IovecToStringPiece(iov));
723 
724   // Peeking into consumed data still fails.
725   EXPECT_FALSE(buffer_->PeekRegion(0, &iov));
726   EXPECT_FALSE(buffer_->PeekRegion(512, &iov));
727   EXPECT_FALSE(buffer_->PeekRegion(1024, &iov));
728   EXPECT_FALSE(buffer_->PeekRegion(1500, &iov));
729 }
730 
TEST_F(QuicStreamSequencerBufferTest,PeekContinously)731 TEST_F(QuicStreamSequencerBufferTest, PeekContinously) {
732   std::string source1(kBlockSizeBytes, 'a');
733   buffer_->OnStreamData(0, source1, &written_, &error_details_);
734 
735   iovec iov;
736   EXPECT_TRUE(buffer_->PeekRegion(0, &iov));
737   EXPECT_EQ(source1, IovecToStringPiece(iov));
738 
739   std::string source2(kBlockSizeBytes, 'b');
740   buffer_->OnStreamData(kBlockSizeBytes, source2, &written_, &error_details_);
741 
742   EXPECT_TRUE(buffer_->PeekRegion(kBlockSizeBytes, &iov));
743   EXPECT_EQ(source2, IovecToStringPiece(iov));
744 
745   // First block is still there.
746   EXPECT_TRUE(buffer_->PeekRegion(0, &iov));
747   EXPECT_EQ(source1, IovecToStringPiece(iov));
748 }
749 
TEST_F(QuicStreamSequencerBufferTest,MarkConsumedInOneBlock)750 TEST_F(QuicStreamSequencerBufferTest, MarkConsumedInOneBlock) {
751   // Write into [0, 1024) and then read out [0, 256)
752   std::string source(1024, 'a');
753   buffer_->OnStreamData(0, source, &written_, &error_details_);
754   char dest[256];
755   helper_->Read(dest, 256);
756 
757   EXPECT_TRUE(buffer_->MarkConsumed(512));
758   EXPECT_EQ(256u + 512u, buffer_->BytesConsumed());
759   EXPECT_EQ(256u, helper_->ReadableBytes());
760   buffer_->MarkConsumed(256);
761   EXPECT_TRUE(buffer_->Empty());
762   EXPECT_TRUE(helper_->CheckBufferInvariants());
763 }
764 
TEST_F(QuicStreamSequencerBufferTest,MarkConsumedNotEnoughBytes)765 TEST_F(QuicStreamSequencerBufferTest, MarkConsumedNotEnoughBytes) {
766   // Write into [0, 1024) and then read out [0, 256)
767   std::string source(1024, 'a');
768   buffer_->OnStreamData(0, source, &written_, &error_details_);
769   char dest[256];
770   helper_->Read(dest, 256);
771 
772   // Consume 1st 512 bytes
773   EXPECT_TRUE(buffer_->MarkConsumed(512));
774   EXPECT_EQ(256u + 512u, buffer_->BytesConsumed());
775   EXPECT_EQ(256u, helper_->ReadableBytes());
776   // Try to consume one bytes more than available. Should return false.
777   EXPECT_FALSE(buffer_->MarkConsumed(257));
778   EXPECT_EQ(256u + 512u, buffer_->BytesConsumed());
779   iovec iov;
780   EXPECT_TRUE(buffer_->GetReadableRegion(&iov));
781   EXPECT_TRUE(helper_->CheckBufferInvariants());
782 }
783 
TEST_F(QuicStreamSequencerBufferTest,MarkConsumedAcrossBlock)784 TEST_F(QuicStreamSequencerBufferTest, MarkConsumedAcrossBlock) {
785   // Write into [0, 2 * kBlockSizeBytes + 1024) and then read out [0, 1024)
786   std::string source(2 * kBlockSizeBytes + 1024, 'a');
787   buffer_->OnStreamData(0, source, &written_, &error_details_);
788   char dest[1024];
789   helper_->Read(dest, 1024);
790 
791   buffer_->MarkConsumed(2 * kBlockSizeBytes);
792   EXPECT_EQ(source.size(), buffer_->BytesConsumed());
793   EXPECT_TRUE(buffer_->Empty());
794   EXPECT_TRUE(helper_->CheckBufferInvariants());
795 }
796 
TEST_F(QuicStreamSequencerBufferTest,MarkConsumedAcrossEnd)797 TEST_F(QuicStreamSequencerBufferTest, MarkConsumedAcrossEnd) {
798   // Write into [0, 8.5 * kBlockSizeBytes - 1024) and then read out [0, 1024)
799   // and then append 1024 + 512 bytes.
800   std::string source(8.5 * kBlockSizeBytes - 1024, 'a');
801   buffer_->OnStreamData(0, source, &written_, &error_details_);
802   char dest[1024];
803   helper_->Read(dest, 1024);
804   source = std::string(1024 + 512, 'b');
805   buffer_->OnStreamData(8.5 * kBlockSizeBytes - 1024, source, &written_,
806                         &error_details_);
807   EXPECT_EQ(1024u, buffer_->BytesConsumed());
808 
809   // Consume to the end of 8th block.
810   buffer_->MarkConsumed(8 * kBlockSizeBytes - 1024);
811   EXPECT_EQ(8 * kBlockSizeBytes, buffer_->BytesConsumed());
812   // Consume across the physical end of buffer
813   buffer_->MarkConsumed(0.5 * kBlockSizeBytes + 500);
814   EXPECT_EQ(max_capacity_bytes_ + 500, buffer_->BytesConsumed());
815   EXPECT_EQ(12u, helper_->ReadableBytes());
816   // Consume to the logical end of buffer
817   buffer_->MarkConsumed(12);
818   EXPECT_EQ(max_capacity_bytes_ + 512, buffer_->BytesConsumed());
819   EXPECT_TRUE(buffer_->Empty());
820   EXPECT_TRUE(helper_->CheckBufferInvariants());
821 }
822 
TEST_F(QuicStreamSequencerBufferTest,FlushBufferedFrames)823 TEST_F(QuicStreamSequencerBufferTest, FlushBufferedFrames) {
824   // Write into [0, 8.5 * kBlockSizeBytes - 1024) and then read out [0, 1024).
825   std::string source(max_capacity_bytes_ - 1024, 'a');
826   buffer_->OnStreamData(0, source, &written_, &error_details_);
827   char dest[1024];
828   helper_->Read(dest, 1024);
829   EXPECT_EQ(1024u, buffer_->BytesConsumed());
830   // Write [1024, 512) to the physical beginning.
831   source = std::string(512, 'b');
832   buffer_->OnStreamData(max_capacity_bytes_, source, &written_,
833                         &error_details_);
834   EXPECT_EQ(512u, written_);
835   EXPECT_EQ(max_capacity_bytes_ - 1024 + 512, buffer_->FlushBufferedFrames());
836   EXPECT_EQ(max_capacity_bytes_ + 512, buffer_->BytesConsumed());
837   EXPECT_TRUE(buffer_->Empty());
838   EXPECT_TRUE(helper_->CheckBufferInvariants());
839   // Clear buffer at this point should still preserve BytesConsumed().
840   buffer_->Clear();
841   EXPECT_EQ(max_capacity_bytes_ + 512, buffer_->BytesConsumed());
842   EXPECT_TRUE(helper_->CheckBufferInvariants());
843 }
844 
TEST_F(QuicStreamSequencerBufferTest,TooManyGaps)845 TEST_F(QuicStreamSequencerBufferTest, TooManyGaps) {
846   // Make sure max capacity is large enough that it is possible to have more
847   // than |kMaxNumGapsAllowed| number of gaps.
848   max_capacity_bytes_ = 3 * kBlockSizeBytes;
849   // Feed buffer with 1-byte discontiguous frames. e.g. [1,2), [3,4), [5,6)...
850   for (QuicStreamOffset begin = 1; begin <= max_capacity_bytes_; begin += 2) {
851     QuicErrorCode rs =
852         buffer_->OnStreamData(begin, "a", &written_, &error_details_);
853 
854     QuicStreamOffset last_straw = 2 * kMaxNumGapsAllowed - 1;
855     if (begin == last_straw) {
856       EXPECT_THAT(rs, IsError(QUIC_TOO_MANY_STREAM_DATA_INTERVALS));
857       EXPECT_EQ("Too many data intervals received for this stream.",
858                 error_details_);
859       break;
860     }
861   }
862 }
863 
864 class QuicStreamSequencerBufferRandomIOTest
865     : public QuicStreamSequencerBufferTest {
866  public:
867   using OffsetSizePair = std::pair<QuicStreamOffset, size_t>;
868 
SetUp()869   void SetUp() override {
870     // Test against a larger capacity then above tests. Also make sure the last
871     // block is partially available to use.
872     max_capacity_bytes_ = 8.25 * kBlockSizeBytes;
873     // Stream to be buffered should be larger than the capacity to test wrap
874     // around.
875     bytes_to_buffer_ = 2 * max_capacity_bytes_;
876     Initialize();
877 
878     uint64_t seed = QuicRandom::GetInstance()->RandUint64();
879     QUIC_LOG(INFO) << "**** The current seed is " << seed << " ****";
880     rng_.set_seed(seed);
881   }
882 
883   // Create an out-of-order source stream with given size to populate
884   // shuffled_buf_.
CreateSourceAndShuffle(size_t max_chunk_size_bytes)885   void CreateSourceAndShuffle(size_t max_chunk_size_bytes) {
886     max_chunk_size_bytes_ = max_chunk_size_bytes;
887     std::unique_ptr<OffsetSizePair[]> chopped_stream(
888         new OffsetSizePair[bytes_to_buffer_]);
889 
890     // Split stream into small chunks with random length. chopped_stream will be
891     // populated with segmented stream chunks.
892     size_t start_chopping_offset = 0;
893     size_t iterations = 0;
894     while (start_chopping_offset < bytes_to_buffer_) {
895       size_t max_chunk = std::min<size_t>(
896           max_chunk_size_bytes_, bytes_to_buffer_ - start_chopping_offset);
897       size_t chunk_size = rng_.RandUint64() % max_chunk + 1;
898       chopped_stream[iterations] =
899           OffsetSizePair(start_chopping_offset, chunk_size);
900       start_chopping_offset += chunk_size;
901       ++iterations;
902     }
903     QUICHE_DCHECK(start_chopping_offset == bytes_to_buffer_);
904     size_t chunk_num = iterations;
905 
906     // Randomly change the sequence of in-ordered OffsetSizePairs to make a
907     // out-of-order array of OffsetSizePairs.
908     for (int i = chunk_num - 1; i >= 0; --i) {
909       size_t random_idx = rng_.RandUint64() % (i + 1);
910       QUIC_DVLOG(1) << "chunk offset " << chopped_stream[random_idx].first
911                     << " size " << chopped_stream[random_idx].second;
912       shuffled_buf_.push_front(chopped_stream[random_idx]);
913       chopped_stream[random_idx] = chopped_stream[i];
914     }
915   }
916 
917   // Write the currently first chunk of data in the out-of-order stream into
918   // QuicStreamSequencerBuffer. If current chuck cannot be written into buffer
919   // because it goes beyond current capacity, move it to the end of
920   // shuffled_buf_ and write it later.
WriteNextChunkToBuffer()921   void WriteNextChunkToBuffer() {
922     OffsetSizePair& chunk = shuffled_buf_.front();
923     QuicStreamOffset offset = chunk.first;
924     const size_t num_to_write = chunk.second;
925     std::unique_ptr<char[]> write_buf{new char[max_chunk_size_bytes_]};
926     for (size_t i = 0; i < num_to_write; ++i) {
927       write_buf[i] = (offset + i) % 256;
928     }
929     absl::string_view string_piece_w(write_buf.get(), num_to_write);
930     auto result = buffer_->OnStreamData(offset, string_piece_w, &written_,
931                                         &error_details_);
932     if (result == QUIC_NO_ERROR) {
933       shuffled_buf_.pop_front();
934       total_bytes_written_ += num_to_write;
935     } else {
936       // This chunk offset exceeds window size.
937       shuffled_buf_.push_back(chunk);
938       shuffled_buf_.pop_front();
939     }
940     QUIC_DVLOG(1) << " write at offset: " << offset
941                   << " len to write: " << num_to_write
942                   << " write result: " << result
943                   << " left over: " << shuffled_buf_.size();
944   }
945 
946  protected:
947   std::list<OffsetSizePair> shuffled_buf_;
948   size_t max_chunk_size_bytes_;
949   QuicStreamOffset bytes_to_buffer_;
950   size_t total_bytes_written_ = 0;
951   size_t total_bytes_read_ = 0;
952   SimpleRandom rng_;
953 };
954 
TEST_F(QuicStreamSequencerBufferRandomIOTest,RandomWriteAndReadv)955 TEST_F(QuicStreamSequencerBufferRandomIOTest, RandomWriteAndReadv) {
956   // Set kMaxReadSize larger than kBlockSizeBytes to test both small and large
957   // read.
958   const size_t kMaxReadSize = kBlockSizeBytes * 2;
959   // kNumReads is larger than 1 to test how multiple read destinations work.
960   const size_t kNumReads = 2;
961   // Since write and read operation have equal possibility to be called. Bytes
962   // to be written into and read out of should roughly the same.
963   const size_t kMaxWriteSize = kNumReads * kMaxReadSize;
964   size_t iterations = 0;
965 
966   CreateSourceAndShuffle(kMaxWriteSize);
967 
968   while ((!shuffled_buf_.empty() || total_bytes_read_ < bytes_to_buffer_) &&
969          iterations <= 2 * bytes_to_buffer_) {
970     uint8_t next_action =
971         shuffled_buf_.empty() ? uint8_t{1} : rng_.RandUint64() % 2;
972     QUIC_DVLOG(1) << "iteration: " << iterations;
973     switch (next_action) {
974       case 0: {  // write
975         WriteNextChunkToBuffer();
976         ASSERT_TRUE(helper_->CheckBufferInvariants());
977         break;
978       }
979       case 1: {  // readv
980         std::unique_ptr<char[][kMaxReadSize]> read_buf{
981             new char[kNumReads][kMaxReadSize]};
982         iovec dest_iov[kNumReads];
983         size_t num_to_read = 0;
984         for (size_t i = 0; i < kNumReads; ++i) {
985           dest_iov[i].iov_base =
986               reinterpret_cast<void*>(const_cast<char*>(read_buf[i]));
987           dest_iov[i].iov_len = rng_.RandUint64() % kMaxReadSize;
988           num_to_read += dest_iov[i].iov_len;
989         }
990         size_t actually_read;
991         EXPECT_THAT(buffer_->Readv(dest_iov, kNumReads, &actually_read,
992                                    &error_details_),
993                     IsQuicNoError());
994         ASSERT_LE(actually_read, num_to_read);
995         QUIC_DVLOG(1) << " read from offset: " << total_bytes_read_
996                       << " size: " << num_to_read
997                       << " actual read: " << actually_read;
998         for (size_t i = 0; i < actually_read; ++i) {
999           char ch = (i + total_bytes_read_) % 256;
1000           ASSERT_EQ(ch, GetCharFromIOVecs(i, dest_iov, kNumReads))
1001               << " at iteration " << iterations;
1002         }
1003         total_bytes_read_ += actually_read;
1004         ASSERT_EQ(total_bytes_read_, buffer_->BytesConsumed());
1005         ASSERT_TRUE(helper_->CheckBufferInvariants());
1006         break;
1007       }
1008     }
1009     ++iterations;
1010     ASSERT_LE(total_bytes_read_, total_bytes_written_);
1011   }
1012   EXPECT_LT(iterations, bytes_to_buffer_) << "runaway test";
1013   EXPECT_LE(bytes_to_buffer_, total_bytes_read_)
1014       << "iterations: " << iterations;
1015   EXPECT_LE(bytes_to_buffer_, total_bytes_written_);
1016 }
1017 
TEST_F(QuicStreamSequencerBufferRandomIOTest,RandomWriteAndConsumeInPlace)1018 TEST_F(QuicStreamSequencerBufferRandomIOTest, RandomWriteAndConsumeInPlace) {
1019   // The value 4 is chosen such that the max write size is no larger than the
1020   // maximum buffer capacity.
1021   const size_t kMaxNumReads = 4;
1022   // Adjust write amount be roughly equal to that GetReadableRegions() can get.
1023   const size_t kMaxWriteSize = kMaxNumReads * kBlockSizeBytes;
1024   ASSERT_LE(kMaxWriteSize, max_capacity_bytes_);
1025   size_t iterations = 0;
1026 
1027   CreateSourceAndShuffle(kMaxWriteSize);
1028 
1029   while ((!shuffled_buf_.empty() || total_bytes_read_ < bytes_to_buffer_) &&
1030          iterations <= 2 * bytes_to_buffer_) {
1031     uint8_t next_action =
1032         shuffled_buf_.empty() ? uint8_t{1} : rng_.RandUint64() % 2;
1033     QUIC_DVLOG(1) << "iteration: " << iterations;
1034     switch (next_action) {
1035       case 0: {  // write
1036         WriteNextChunkToBuffer();
1037         ASSERT_TRUE(helper_->CheckBufferInvariants());
1038         break;
1039       }
1040       case 1: {  // GetReadableRegions and then MarkConsumed
1041         size_t num_read = rng_.RandUint64() % kMaxNumReads + 1;
1042         iovec dest_iov[kMaxNumReads];
1043         ASSERT_TRUE(helper_->CheckBufferInvariants());
1044         size_t actually_num_read =
1045             buffer_->GetReadableRegions(dest_iov, num_read);
1046         ASSERT_LE(actually_num_read, num_read);
1047         size_t avail_bytes = 0;
1048         for (size_t i = 0; i < actually_num_read; ++i) {
1049           avail_bytes += dest_iov[i].iov_len;
1050         }
1051         // process random number of bytes (check the value of each byte).
1052         size_t bytes_to_process = rng_.RandUint64() % (avail_bytes + 1);
1053         size_t bytes_processed = 0;
1054         for (size_t i = 0; i < actually_num_read; ++i) {
1055           size_t bytes_in_block = std::min<size_t>(
1056               bytes_to_process - bytes_processed, dest_iov[i].iov_len);
1057           if (bytes_in_block == 0) {
1058             break;
1059           }
1060           for (size_t j = 0; j < bytes_in_block; ++j) {
1061             ASSERT_LE(bytes_processed, bytes_to_process);
1062             char char_expected =
1063                 (buffer_->BytesConsumed() + bytes_processed) % 256;
1064             ASSERT_EQ(char_expected,
1065                       reinterpret_cast<const char*>(dest_iov[i].iov_base)[j])
1066                 << " at iteration " << iterations;
1067             ++bytes_processed;
1068           }
1069         }
1070 
1071         buffer_->MarkConsumed(bytes_processed);
1072 
1073         QUIC_DVLOG(1) << "iteration " << iterations << ": try to get "
1074                       << num_read << " readable regions, actually get "
1075                       << actually_num_read
1076                       << " from offset: " << total_bytes_read_
1077                       << "\nprocesse bytes: " << bytes_processed;
1078         total_bytes_read_ += bytes_processed;
1079         ASSERT_EQ(total_bytes_read_, buffer_->BytesConsumed());
1080         ASSERT_TRUE(helper_->CheckBufferInvariants());
1081         break;
1082       }
1083     }
1084     ++iterations;
1085     ASSERT_LE(total_bytes_read_, total_bytes_written_);
1086   }
1087   EXPECT_LT(iterations, bytes_to_buffer_) << "runaway test";
1088   EXPECT_LE(bytes_to_buffer_, total_bytes_read_)
1089       << "iterations: " << iterations;
1090   EXPECT_LE(bytes_to_buffer_, total_bytes_written_);
1091 }
1092 
TEST_F(QuicStreamSequencerBufferTest,GrowBlockSizeOnDemand)1093 TEST_F(QuicStreamSequencerBufferTest, GrowBlockSizeOnDemand) {
1094   max_capacity_bytes_ = 1024 * kBlockSizeBytes;
1095   std::string source_of_one_block(kBlockSizeBytes, 'a');
1096   Initialize();
1097 
1098   ASSERT_EQ(helper_->current_blocks_count(), 0u);
1099 
1100   // A minimum of 8 blocks are allocated
1101   buffer_->OnStreamData(0, source_of_one_block, &written_, &error_details_);
1102   ASSERT_EQ(helper_->current_blocks_count(), 8u);
1103 
1104   // Number of blocks doesn't grow if the data is within the capacity.
1105   buffer_->OnStreamData(kBlockSizeBytes * 7, source_of_one_block, &written_,
1106                         &error_details_);
1107   ASSERT_EQ(helper_->current_blocks_count(), 8u);
1108 
1109   // Number of blocks grows by a factor of 4 normally.
1110   buffer_->OnStreamData(kBlockSizeBytes * 8, "a", &written_, &error_details_);
1111   ASSERT_EQ(helper_->current_blocks_count(), 32u);
1112 
1113   // Number of blocks grow to the demanded size of 140 instead of 128 since
1114   // that's not enough.
1115   buffer_->OnStreamData(kBlockSizeBytes * 139, source_of_one_block, &written_,
1116                         &error_details_);
1117   ASSERT_EQ(helper_->current_blocks_count(), 140u);
1118 
1119   // Number of blocks grows by a factor of 4 normally.
1120   buffer_->OnStreamData(kBlockSizeBytes * 140, source_of_one_block, &written_,
1121                         &error_details_);
1122   ASSERT_EQ(helper_->current_blocks_count(), 560u);
1123 
1124   // max_capacity_bytes is reached and number of blocks is capped.
1125   buffer_->OnStreamData(kBlockSizeBytes * 560, source_of_one_block, &written_,
1126                         &error_details_);
1127   ASSERT_EQ(helper_->current_blocks_count(), 1024u);
1128 
1129   // max_capacity_bytes is reached and number of blocks is capped.
1130   buffer_->OnStreamData(kBlockSizeBytes * 1025, source_of_one_block, &written_,
1131                         &error_details_);
1132   ASSERT_EQ(helper_->current_blocks_count(), 1024u);
1133 }
1134 
1135 }  // anonymous namespace
1136 
1137 }  // namespace test
1138 
1139 }  // namespace quic
1140