Create a new data structure StreamSequencerBuffer for QuicStreamSequencer. Currently QuicStreamSequ…

net/quic/stream_sequencer_buffer_test.cc

+// Copyright (c) 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/quic/stream_sequencer_buffer.h"
+
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/rand_util.h"
+#include "net/quic/test_tools/mock_clock.h"
+#include "net/quic/test_tools/quic_test_utils.h"
+#include "net/test/gtest_util.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gmock_mutant.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using std::min;
+
+namespace net {
+
+namespace test {
+
+
+char GetCharFromIOVecs(size_t offset, iovec iov[],
+                       size_t count) {
+  size_t start_offset = 0;
+  for (size_t i = 0; i < count; i++) {
+    if (iov[i].iov_len == 0) {
+      continue;
+    }
+    size_t end_offset = start_offset + iov[i].iov_len - 1;
+    if (offset >= start_offset && offset <= end_offset) {
+      const char* buf = reinterpret_cast<const char*>(iov[i].iov_base);
+      return buf[offset - start_offset];
+    }
+    start_offset += iov[i].iov_len;
+  }
+  LOG(ERROR) << "Could not locate char at offset " << offset << " in "
+             << count << " iovecs";
+  for (size_t i = 0; i < count; ++i) {
+    LOG(ERROR) << "  iov[" << i << "].iov_len = " << iov[i].iov_len;
+  }
+  return '\0';
+}
+
+static const size_t kBlockSizeBytes = StreamSequencerBuffer::kBlockSizeBytes;
+typedef StreamSequencerBuffer::BufferBlock BufferBlock;
+typedef StreamSequencerBuffer::Gap Gap;
+typedef StreamSequencerBuffer::FrameInfo FrameInfo;
+
+class StreamSequencerBufferPeer {
+ public:
+  explicit StreamSequencerBufferPeer(StreamSequencerBuffer* buffer)
+      : buffer_(buffer) {}
+
+  // Read from this buffer_->into the given destination buffer_-> up to the
+  // size of the destination. Returns the number of bytes read. Reading from
+  // an empty buffer_->returns 0.
+  size_t Read(char* dest_buffer, size_t size) {
+    iovec dest;
+    dest.iov_base = dest_buffer, dest.iov_len = size;
+    return buffer_->Readv(&dest, 1);
+  }
+
+  // If buffer is empty, the blocks_ array must be empty, which means all
+  // blocks are deallocated.
+  bool CheckEmptyInvariants() {
+    return !buffer_->Empty() || IsBlockArrayEmpty();
+  }
+
+  bool IsBlockArrayEmpty() {
+    size_t count = buffer_->blocks_count_;
+    for (size_t i = 0; i < count; i++) {
+      if (buffer_->blocks_[i] != nullptr) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  bool CheckInitialState() {
+    EXPECT_TRUE(buffer_->Empty() && buffer_->total_bytes_read_ == 0 &&
+                buffer_->num_bytes_buffered_ == 0);
+    return CheckBufferInvariants();
+  }
+
+  bool CheckBufferInvariants() {
+    size_t data_span{buffer_->gaps_.back().begin_offset -
+                     buffer_->total_bytes_read_};
+    bool capacity_sane = data_span <= buffer_->max_buffer_capacity_bytes_ &&
+                         data_span >= buffer_->num_bytes_buffered_;
+    if (!capacity_sane) {
+      LOG(ERROR) << "data span is larger than capacity.";
+      LOG(ERROR) << "total read: " << buffer_->total_bytes_read_
+                 << " last byte: " << buffer_->gaps_.back().begin_offset;
+    }
+    bool total_read_sane =
+        buffer_->gaps_.front().begin_offset >= buffer_->total_bytes_read_;
+    if (!total_read_sane) {
+      LOG(ERROR) << "read across 1st gap.";
+    }
+    bool read_offset_sane = buffer_->ReadOffset() < kBlockSizeBytes;
+    if (!capacity_sane) {
+      LOG(ERROR) << "read offset go beyond 1st block";
+    }
+    bool block_match_capacity =
+        (buffer_->max_buffer_capacity_bytes_ <=
+         buffer_->blocks_count_ * kBlockSizeBytes) &&
+        (buffer_->max_buffer_capacity_bytes_ >
+         (buffer_->blocks_count_ - 1) * kBlockSizeBytes);
+    if (!capacity_sane) {
+      LOG(ERROR) << "block number not match capcaity.";
+    }
+    bool block_retired_when_empty = CheckEmptyInvariants();
+    if (!block_retired_when_empty) {
+      LOG(ERROR) << "block is not retired after use.";
+    }
+    return capacity_sane && total_read_sane && read_offset_sane &&
+           block_match_capacity && block_retired_when_empty;
+  }
+
+  size_t GetInBlockOffset(QuicStreamOffset offset) {
+    return buffer_->GetInBlockOffset(offset);
+  }
+
+  BufferBlock* GetBlock(size_t index) { return buffer_->blocks_[index]; }
+
+  int GapSize() { return buffer_->gaps_.size(); }
+
+  std::list<Gap> GetGaps() { return buffer_->gaps_; }
+
+  size_t max_buffer_capacity() { return buffer_->max_buffer_capacity_bytes_; }
+
+  size_t ReadableBytes() { return buffer_->ReadableBytes(); }
+
+  std::map<QuicStreamOffset, FrameInfo>* frame_arrival_time_map() {
+    return &(buffer_->frame_arrival_time_map_);
+  }
+
+ private:
+  StreamSequencerBuffer* buffer_;
+};
+
+namespace {
+
+class StreamSequencerBufferTest : public testing::Test {
+ public:
+  void SetUp() override { Initialize(); }
+
+  void ResetMaxCapacityBytes(size_t max_capacity_bytes) {
+    max_capacity_bytes_ = max_capacity_bytes;
+    Initialize();
+  }
+
+ protected:
+  void Initialize() {
+    buffer_.reset(new StreamSequencerBuffer(max_capacity_bytes_));
+    helper_.reset(new StreamSequencerBufferPeer(buffer_.get()));
+  }
+
+  // Use 2.5 here to make sure the buffer has more than one block and its end
+  // doesn't align with the end of a block in order to test all the offset
+  // calculation.
+  size_t max_capacity_bytes_ = 2.5 * kBlockSizeBytes;
+
+  MockClock clock_;
+  std::unique_ptr<StreamSequencerBuffer> buffer_;
+  std::unique_ptr<StreamSequencerBufferPeer> helper_;
+};
+
+TEST_F(StreamSequencerBufferTest, InitializationWithDifferentSizes) {
+  const size_t kCapacity = 2 * StreamSequencerBuffer::kBlockSizeBytes;
+  ResetMaxCapacityBytes(kCapacity);
+  EXPECT_EQ(max_capacity_bytes_, helper_->max_buffer_capacity());
+  EXPECT_TRUE(helper_->CheckInitialState());
+
+  const size_t kCapacity1 = 8 * StreamSequencerBuffer::kBlockSizeBytes;
+  ResetMaxCapacityBytes(kCapacity1);
+  EXPECT_EQ(kCapacity1, helper_->max_buffer_capacity());
+  EXPECT_TRUE(helper_->CheckInitialState());
+}
+
+TEST_F(StreamSequencerBufferTest, ClearOnEmpty) {
+  buffer_->Clear();
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, OnStreamData0length) {
+  std::string source;
+  size_t written;
+  EXPECT_DFATAL(buffer_->OnStreamData(800, source,
+                                      clock_.ApproximateNow(), &written),
+                "Attempted to write 0 bytes of data.");
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, OnStreamDataWithinBlock) {
+  std::string source(1024, 'a');
+  size_t written;
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t = clock_.ApproximateNow();
+  EXPECT_EQ(QUIC_NO_ERROR,
+            buffer_->OnStreamData(800, source, t, &written));
+  BufferBlock* block_ptr = helper_->GetBlock(0);
+  for (size_t i = 0; i < source.size(); ++i) {
+    ASSERT_EQ('a', block_ptr->buffer[helper_->GetInBlockOffset(800) + i]);
+  }
+  EXPECT_EQ(2, helper_->GapSize());
+  std::list<Gap> gaps = helper_->GetGaps();
+  EXPECT_EQ(800u, gaps.front().end_offset);
+  EXPECT_EQ(1824u, gaps.back().begin_offset);
+  auto frame_map = helper_->frame_arrival_time_map();
+  EXPECT_EQ(1u, frame_map->size());
+  EXPECT_EQ(800u, frame_map->begin()->first);
+  EXPECT_EQ(t, (*frame_map)[800].timestamp);
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, OnStreamDataWithOverlap) {
+  std::string source(1024, 'a');
+  // Write something into [800, 1824)
+  size_t written;
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t1 = clock_.ApproximateNow();
+  EXPECT_EQ(QUIC_NO_ERROR,
+            buffer_->OnStreamData(800, source, t1, &written));
+  // Try to write to [0, 1024) and [1024, 2048).
+  // But no byte will be written since overlap.
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t2 = clock_.ApproximateNow();
+  EXPECT_EQ(QUIC_INVALID_STREAM_DATA,
+            buffer_->OnStreamData(0, source, t2, &written));
+  EXPECT_EQ(QUIC_INVALID_STREAM_DATA,
+            buffer_->OnStreamData(1024, source, t2, &written));
+  auto frame_map = helper_->frame_arrival_time_map();
+  EXPECT_EQ(1u, frame_map->size());
+  EXPECT_EQ(t1, (*frame_map)[800].timestamp);
+}
+
+TEST_F(StreamSequencerBufferTest, OnStreamDataOverlapAndDuplicateCornerCases) {
+  std::string source(1024, 'a');
+  // Write something into [800, 1824)
+  size_t written;
+  buffer_->OnStreamData(800, source, clock_.ApproximateNow(), &written);
+  source = std::string(800, 'b');
+  // Try to write to [1, 801), but should fail due to overlapping
+  EXPECT_EQ(QUIC_INVALID_STREAM_DATA,
+            buffer_->OnStreamData(1, source, clock_.ApproximateNow(),
+                                  &written));
+  // write to [0, 800)
+  EXPECT_EQ(QUIC_NO_ERROR,
+            buffer_->OnStreamData(0, source, clock_.ApproximateNow(),
+                                  &written));
+  // Try to write one byte to [1823, 1824), but should count as duplicate
+  std::string one_byte = "c";
+  EXPECT_EQ(
+      QUIC_NO_ERROR,
+      buffer_->OnStreamData(1823, one_byte, clock_.ApproximateNow(), &written));
+  EXPECT_EQ(0u, written);
+  // write one byte to [1824, 1825)
+  EXPECT_EQ(
+      QUIC_NO_ERROR,
+      buffer_->OnStreamData(1824, one_byte, clock_.ApproximateNow(), &written));
+  auto frame_map = helper_->frame_arrival_time_map();
+  EXPECT_EQ(3u, frame_map->size());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, OnStreamDataWithoutOverlap) {
+  std::string source(1024, 'a');
+  // Write something into [800, 1824).
+  size_t written;
+  EXPECT_EQ(QUIC_NO_ERROR,
+        buffer_->OnStreamData(800, source, clock_.ApproximateNow(), &written));
+  source = std::string(100, 'b');
+  // Write something into [kBlockSizeBytes * 2 - 20, kBlockSizeBytes * 2 + 80).
+  EXPECT_EQ(QUIC_NO_ERROR,
+            buffer_->OnStreamData(kBlockSizeBytes * 2 - 20, source,
+                                  clock_.ApproximateNow(), &written));
+  EXPECT_EQ(3, helper_->GapSize());
+  EXPECT_EQ(1024u + 100u, buffer_->BytesBuffered());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, OnStreamDataTillEnd) {
+  // Write 50 bytes to the end.
+  const size_t kBytesToWrite = 50;
+  std::string source(kBytesToWrite, 'a');
+  size_t written;
+  EXPECT_EQ(QUIC_NO_ERROR,
+            buffer_->OnStreamData(max_capacity_bytes_ - kBytesToWrite,
+                                  source,
+                                  clock_.ApproximateNow(), &written));
+  EXPECT_EQ(50u, buffer_->BytesBuffered());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, OnStreamDataTillEndCorner) {
+  // Write 1 byte to the end.
+  const size_t kBytesToWrite = 1;
+  std::string source(kBytesToWrite, 'a');
+  size_t written;
+  EXPECT_EQ(QUIC_NO_ERROR,
+            buffer_->OnStreamData(max_capacity_bytes_ - kBytesToWrite,
+                                  source, clock_.ApproximateNow(), &written));
+  EXPECT_EQ(1u, buffer_->BytesBuffered());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, OnStreamDataBeyondCapacity) {
+  std::string source(60, 'a');
+  size_t written;
+  EXPECT_EQ(QUIC_INTERNAL_ERROR,
+            buffer_->OnStreamData(max_capacity_bytes_ - 50, source,
+                                  clock_.ApproximateNow(), &written));
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+
+  source = "b";
+  EXPECT_EQ(QUIC_INTERNAL_ERROR,
+            buffer_->OnStreamData(max_capacity_bytes_, source,
+                                  clock_.ApproximateNow(), &written));
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+
+  EXPECT_EQ(QUIC_INTERNAL_ERROR,
+            buffer_->OnStreamData(max_capacity_bytes_ * 1000, source,
+                                  clock_.ApproximateNow(), &written));
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+  EXPECT_EQ(0u, buffer_->BytesBuffered());
+}
+
+TEST_F(StreamSequencerBufferTest, Readv100Bytes) {
+  std::string source(1024, 'a');
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t1 = clock_.ApproximateNow();
+  // Write something into [kBlockSizeBytes, kBlockSizeBytes + 1024).
+  size_t written;
+  buffer_->OnStreamData(kBlockSizeBytes, source, t1, &written);
+  EXPECT_FALSE(buffer_->HasBytesToRead());
+  source = std::string{100, 'b'};
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t2 = clock_.ApproximateNow();
+  // Write something into [0, 100).
+  buffer_->OnStreamData(0, source, t2, &written);
+  EXPECT_TRUE(buffer_->HasBytesToRead());
+  EXPECT_EQ(2u, helper_->frame_arrival_time_map()->size());
+  // Read into a iovec array with total capacity of 120 bytes.
+  char dest[120];
+  iovec iovecs[3]{iovec{dest, 40}, iovec{dest + 40, 40}, iovec{dest + 80, 40}};
+  size_t read = buffer_->Readv(iovecs, 3);
+  EXPECT_EQ(100u, read);
+  EXPECT_EQ(100u, buffer_->BytesConsumed());
+  EXPECT_EQ(source, std::string(dest, read));
+  EXPECT_EQ(1u, helper_->frame_arrival_time_map()->size());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, ReadvAcrossBlocks) {
+  std::string source(kBlockSizeBytes + 50, 'a');
+  // Write 1st block to full and extand 50 bytes to next block.
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  EXPECT_EQ(source.size(), helper_->ReadableBytes());
+  // Iteratively read 512 bytes from buffer_-> Overwrite dest[] each time.
+  char dest[512];
+  while (helper_->ReadableBytes()) {
+    std::fill(dest, dest + 512, 0);
+    iovec iovecs[2]{iovec{dest, 256}, iovec{dest + 256, 256}};
+    buffer_->Readv(iovecs, 2);
+  }
+  // The last read only reads the rest 50 bytes in 2nd block.
+  EXPECT_EQ(std::string(50, 'a'), std::string(dest, 50));
+  EXPECT_EQ(0, dest[50]) << "Dest[50] shouln't be filled.";
+  EXPECT_EQ(source.size(), buffer_->BytesConsumed());
+  EXPECT_TRUE(buffer_->Empty());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, ClearAfterRead) {
+  std::string source(kBlockSizeBytes + 50, 'a');
+  // Write 1st block to full with 'a'.
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  // Read first 512 bytes from buffer to make space at the beginning.
+  char dest[512]{0};
+  const iovec iov{dest, 512};
+  buffer_->Readv(&iov, 1);
+  // Clear() should make buffer empty while preserving BytesConsumed()
+  buffer_->Clear();
+  EXPECT_TRUE(buffer_->Empty());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, OnStreamDataAcrossLastBlockAndFillCapacity) {
+  std::string source(kBlockSizeBytes + 50, 'a');
+  // Write 1st block to full with 'a'.
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  // Read first 512 bytes from buffer to make space at the beginning.
+  char dest[512]{0};
+  const iovec iov{dest, 512};
+  buffer_->Readv(&iov, 1);
+  EXPECT_EQ(source.size(), written);
+
+  // Write more than half block size of bytes in the last block with 'b', which
+  // will wrap to the beginning and reaches the full capacity.
+  source = std::string(0.5 * kBlockSizeBytes + 512, 'b');
+  EXPECT_EQ(QUIC_NO_ERROR,
+            buffer_->OnStreamData(2 * kBlockSizeBytes, source,
+                                  clock_.ApproximateNow(), &written));
+  EXPECT_EQ(source.size(), written);
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest,
+       OnStreamDataAcrossLastBlockAndExceedCapacity) {
+  std::string source(kBlockSizeBytes + 50, 'a');
+  // Write 1st block to full.
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  // Read first 512 bytes from buffer to make space at the beginning.
+  char dest[512]{0};
+  const iovec iov{dest, 512};
+  buffer_->Readv(&iov, 1);
+
+  // Try to write from [max_capacity_bytes_ - 0.5 * kBlockSizeBytes,
+  // max_capacity_bytes_ +  512 + 1). But last bytes exceeds current capacity.
+  source = std::string(0.5 * kBlockSizeBytes + 512 + 1, 'b');
+  EXPECT_EQ(QUIC_INTERNAL_ERROR,
+            buffer_->OnStreamData(2 * kBlockSizeBytes, source,
+                                  clock_.ApproximateNow(), &written));
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, ReadvAcrossLastBlock) {
+  // Write to full capacity and read out 512 bytes at beginning and continue
+  // appending 256 bytes.
+  std::string source(max_capacity_bytes_, 'a');
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t = clock_.ApproximateNow();
+  size_t written;
+  buffer_->OnStreamData(0, source, t, &written);
+  char dest[512]{0};
+  const iovec iov{dest, 512};
+  buffer_->Readv(&iov, 1);
+  source = std::string(256, 'b');
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t2 = clock_.ApproximateNow();
+  buffer_->OnStreamData(max_capacity_bytes_, source, t2, &written);
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+  EXPECT_EQ(2u, helper_->frame_arrival_time_map()->size());
+
+  // Read all data out.
+  std::unique_ptr<char[]> dest1{new char[max_capacity_bytes_]{0}};
+  const iovec iov1{dest1.get(), max_capacity_bytes_};
+  EXPECT_EQ(max_capacity_bytes_ - 512 + 256, buffer_->Readv(&iov1, 1));
+  EXPECT_EQ(max_capacity_bytes_ + 256, buffer_->BytesConsumed());
+  EXPECT_TRUE(buffer_->Empty());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+  EXPECT_EQ(0u, helper_->frame_arrival_time_map()->size());
+}
+
+TEST_F(StreamSequencerBufferTest, ReadvEmpty) {
+  char dest[512]{0};
+  iovec iov{dest, 512};
+  size_t read = buffer_->Readv(&iov, 1);
+  EXPECT_EQ(0u, read);
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionsEmpty) {
+  iovec iovs[2];
+  int iov_count = buffer_->GetReadableRegions(iovs, 2);
+  EXPECT_EQ(0, iov_count);
+  EXPECT_EQ(nullptr, iovs[iov_count].iov_base);
+  EXPECT_EQ(0u, iovs[iov_count].iov_len);
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionsBlockedByGap) {
+  // Write into [1, 1024).
+  std::string source(1023, 'a');
+  size_t written;
+  buffer_->OnStreamData(1, source, clock_.ApproximateNow(), &written);
+  // Try to get readable regions, but none is there.
+  iovec iovs[2];
+  int iov_count = buffer_->GetReadableRegions(iovs, 2);
+  EXPECT_EQ(0, iov_count);
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionsTillEndOfBlock) {
+  // Write first block to full with [0, 256) 'a' and the rest 'b' then read out
+  // [0, 256)
+  std::string source(kBlockSizeBytes, 'a');
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  char dest[256];
+  helper_->Read(dest, 256);
+  // Get readable region from [256, 1024)
+  iovec iovs[2];
+  int iov_count = buffer_->GetReadableRegions(iovs, 2);
+  EXPECT_EQ(1, iov_count);
+  EXPECT_EQ(std::string(kBlockSizeBytes - 256, 'a'),
+    std::string(reinterpret_cast<const char*>(iovs[0].iov_base), iovs[0].iov_len));
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionsWithinOneBlock) {
+  // Write into [0, 1024) and then read out [0, 256)
+  std::string source(1024, 'a');
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  char dest[256];
+  helper_->Read(dest, 256);
+  // Get readable region from [256, 1024)
+  iovec iovs[2];
+  int iov_count = buffer_->GetReadableRegions(iovs, 2);
+  EXPECT_EQ(1, iov_count);
+  EXPECT_EQ(std::string(1024 - 256, 'a'),
+    std::string(reinterpret_cast<const char*>(iovs[0].iov_base), iovs[0].iov_len));
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionsAcrossBlockWithLongIOV) {
+  // Write into [0, 2 * kBlockSizeBytes + 1024) and then read out [0, 1024)
+  std::string source(2 * kBlockSizeBytes + 1024, 'a');
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  char dest[1024];
+  helper_->Read(dest, 1024);
+
+  iovec iovs[4];
+  int iov_count = buffer_->GetReadableRegions(iovs, 4);
+  EXPECT_EQ(3, iov_count);
+  EXPECT_EQ(kBlockSizeBytes - 1024, iovs[0].iov_len);
+  EXPECT_EQ(kBlockSizeBytes, iovs[1].iov_len);
+  EXPECT_EQ(1024u, iovs[2].iov_len);
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionsWithMultipleIOVsAcrossEnd) {
+  // Write into [0, 2 * kBlockSizeBytes + 1024) and then read out [0, 1024)
+  // and then append 1024 + 512 bytes.
+  std::string source(2.5 * kBlockSizeBytes - 1024, 'a');
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  char dest[1024];
+  helper_->Read(dest, 1024);
+  // Write across the end.
+  source = std::string(1024 + 512, 'b');
+  buffer_->OnStreamData(2.5 * kBlockSizeBytes - 1024, source,
+                        clock_.ApproximateNow(), &written);
+  // Use short iovec's.
+  iovec iovs[2];
+  int iov_count = buffer_->GetReadableRegions(iovs, 2);
+  EXPECT_EQ(2, iov_count);
+  EXPECT_EQ(kBlockSizeBytes - 1024, iovs[0].iov_len);
+  EXPECT_EQ(kBlockSizeBytes, iovs[1].iov_len);
+  // Use long iovec's and wrap the end of buffer.
+  iovec iovs1[5];
+  EXPECT_EQ(4, buffer_->GetReadableRegions(iovs1, 5));
+  EXPECT_EQ(0.5 * kBlockSizeBytes, iovs1[2].iov_len);
+  EXPECT_EQ(512u, iovs1[3].iov_len);
+  EXPECT_EQ(std::string(512, 'b'),
+    std::string(reinterpret_cast<const char*>(iovs1[3].iov_base), iovs1[3].iov_len));
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionEmpty) {
+  iovec iov;
+  QuicTime t = QuicTime::Zero();
+  EXPECT_FALSE(buffer_->GetReadableRegion(&iov, &t));
+  EXPECT_EQ(nullptr, iov.iov_base);
+  EXPECT_EQ(0u, iov.iov_len);
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionBeforeGap) {
+  // Write into [1, 1024).
+  std::string source(1023, 'a');
+  size_t written;
+  buffer_->OnStreamData(1, source, clock_.ApproximateNow(), &written);
+  // GetReadableRegion should return false because range  [0,1) hasn't been
+  // filled yet.
+  iovec iov;
+  QuicTime t = QuicTime::Zero();
+  EXPECT_FALSE(buffer_->GetReadableRegion(&iov, &t));
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionTillEndOfBlock) {
+  // Write into [0, kBlockSizeBytes + 1) and then read out [0, 256)
+  std::string source(kBlockSizeBytes + 1, 'a');
+  size_t written;
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t = clock_.ApproximateNow();
+  buffer_->OnStreamData(0, source, t, &written);
+  char dest[256];
+  helper_->Read(dest, 256);
+  // Get readable region from [256, 1024)
+  iovec iov;
+  QuicTime t2 = QuicTime::Zero();
+  EXPECT_TRUE(buffer_->GetReadableRegion(&iov, &t2));
+  EXPECT_EQ(t, t2);
+  EXPECT_EQ(std::string(kBlockSizeBytes - 256, 'a'),
+            std::string(reinterpret_cast<const char*>(iov.iov_base), iov.iov_len));
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionTillGap) {
+  // Write into [0, kBlockSizeBytes - 1) and then read out [0, 256)
+  std::string source(kBlockSizeBytes - 1, 'a');
+  size_t written;
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t = clock_.ApproximateNow();
+  buffer_->OnStreamData(0, source, t, &written);
+  char dest[256];
+  helper_->Read(dest, 256);
+  // Get readable region from [256, 1023)
+  iovec iov;
+  QuicTime t2 = QuicTime::Zero();
+  EXPECT_TRUE(buffer_->GetReadableRegion(&iov, &t2));
+  EXPECT_EQ(t, t2);
+  EXPECT_EQ(std::string(kBlockSizeBytes - 1 - 256, 'a'),
+            std::string(reinterpret_cast<const char*>(iov.iov_base), iov.iov_len));
+}
+
+TEST_F(StreamSequencerBufferTest, GetReadableRegionByArrivalTime) {
+  // Write into [0, kBlockSizeBytes - 100) and then read out [0, 256)
+  std::string source(kBlockSizeBytes - 100, 'a');
+  size_t written;
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t = clock_.ApproximateNow();
+  buffer_->OnStreamData(0, source, t, &written);
+  char dest[256];
+  helper_->Read(dest, 256);
+  // Write into [kBlockSizeBytes - 100, kBlockSizeBytes - 50)] in same time
+  std::string source2(50, 'b');
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  buffer_->OnStreamData(kBlockSizeBytes - 100, source2, t, &written);
+
+  // Write into [kBlockSizeBytes - 50, kBlockSizeBytes)] in another time
+  std::string source3(50, 'c');
+  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
+  QuicTime t3 = clock_.ApproximateNow();
+  buffer_->OnStreamData(kBlockSizeBytes - 50, source3, t3, &written);
+
+  // Get readable region from [256, 1024 - 50)
+  iovec iov;
+  QuicTime t4 = QuicTime::Zero();
+  EXPECT_TRUE(buffer_->GetReadableRegion(&iov, &t4));
+  EXPECT_EQ(t, t4);
+  EXPECT_EQ(std::string(kBlockSizeBytes - 100 -256, 'a') + source2,
+            std::string(reinterpret_cast<const char*>(iov.iov_base), iov.iov_len));
+}
+
+TEST_F(StreamSequencerBufferTest, MarkConsumedInOneBlock) {
+  // Write into [0, 1024) and then read out [0, 256)
+  std::string source(1024, 'a');
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  char dest[256];
+  helper_->Read(dest, 256);
+
+  EXPECT_TRUE(buffer_->MarkConsumed(512));
+  EXPECT_EQ(256u + 512u, buffer_->BytesConsumed());
+  EXPECT_EQ(256u, helper_->ReadableBytes());
+  EXPECT_EQ(1u, helper_->frame_arrival_time_map()->size());
+  buffer_->MarkConsumed(256);
+  EXPECT_EQ(0u, helper_->frame_arrival_time_map()->size());
+  EXPECT_TRUE(buffer_->Empty());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, MarkConsumedNotEnoughBytes) {
+  // Write into [0, 1024) and then read out [0, 256)
+  std::string source(1024, 'a');
+  size_t written;
+  QuicTime t = clock_.ApproximateNow();
+  buffer_->OnStreamData(0, source, t, &written);
+  char dest[256];
+  helper_->Read(dest, 256);
+
+  // Consume 1st 512 bytes
+  EXPECT_TRUE(buffer_->MarkConsumed(512));
+  EXPECT_EQ(256u + 512u, buffer_->BytesConsumed());
+  EXPECT_EQ(256u, helper_->ReadableBytes());
+  // Try to consume one bytes more than available. Should return false.
+  EXPECT_FALSE(buffer_->MarkConsumed(257));
+  EXPECT_EQ(256u + 512u, buffer_->BytesConsumed());
+  QuicTime t2 = QuicTime::Zero();
+  iovec iov;
+  EXPECT_TRUE(buffer_->GetReadableRegion(&iov, &t2));
+  EXPECT_EQ(t, t2);
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, MarkConsumedAcrossBlock) {
+  // Write into [0, 2 * kBlockSizeBytes + 1024) and then read out [0, 1024)
+  std::string source(2 * kBlockSizeBytes + 1024, 'a');
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  char dest[1024];
+  helper_->Read(dest, 1024);
+
+  buffer_->MarkConsumed(2 * kBlockSizeBytes);
+  EXPECT_EQ(source.size(), buffer_->BytesConsumed());
+  EXPECT_TRUE(buffer_->Empty());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, MarkConsumedAcrossEnd) {
+  // Write into [0, 2.5 * kBlockSizeBytes - 1024) and then read out [0, 1024)
+  // and then append 1024 + 512 bytes.
+  std::string source(2.5 * kBlockSizeBytes - 1024, 'a');
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  char dest[1024];
+  helper_->Read(dest, 1024);
+  source = std::string(1024 + 512, 'b');
+  buffer_->OnStreamData(2.5 * kBlockSizeBytes - 1024, source,
+                        clock_.ApproximateNow(), &written);
+  EXPECT_EQ(1024u, buffer_->BytesConsumed());
+
+  // Consume to the end of 2nd block.
+  buffer_->MarkConsumed(2 * kBlockSizeBytes - 1024);
+  EXPECT_EQ(2 * kBlockSizeBytes, buffer_->BytesConsumed());
+  // Consume across the physical end of buffer
+  buffer_->MarkConsumed(0.5 * kBlockSizeBytes + 500);
+  EXPECT_EQ(max_capacity_bytes_ + 500, buffer_->BytesConsumed());
+  EXPECT_EQ(12u, helper_->ReadableBytes());
+  // Consume to the logical end of buffer
+  buffer_->MarkConsumed(12);
+  EXPECT_EQ(max_capacity_bytes_ + 512, buffer_->BytesConsumed());
+  EXPECT_TRUE(buffer_->Empty());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+TEST_F(StreamSequencerBufferTest, FlushBufferedFrames) {
+  // Write into [0, 2.5 * kBlockSizeBytes - 1024) and then read out [0, 1024).
+  std::string source(max_capacity_bytes_ - 1024, 'a');
+  size_t written;
+  buffer_->OnStreamData(0, source, clock_.ApproximateNow(), &written);
+  char dest[1024];
+  helper_->Read(dest, 1024);
+  EXPECT_EQ(1024u, buffer_->BytesConsumed());
+  // Write [1024, 512) to the physical beginning.
+  source = std::string(512, 'b');
+  buffer_->OnStreamData(max_capacity_bytes_, source,
+                        clock_.ApproximateNow(), &written);
+  EXPECT_EQ(512u, written);
+  EXPECT_EQ(max_capacity_bytes_ - 1024 + 512, buffer_->FlushBufferedFrames());
+  EXPECT_EQ(max_capacity_bytes_ + 512, buffer_->BytesConsumed());
+  EXPECT_TRUE(buffer_->Empty());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+  // Clear buffer at this point should still preserve BytesConsumed().
+  buffer_->Clear();
+  EXPECT_EQ(max_capacity_bytes_ + 512, buffer_->BytesConsumed());
+  EXPECT_TRUE(helper_->CheckBufferInvariants());
+}
+
+class StreamSequencerBufferRandomIOTest : public StreamSequencerBufferTest {
+ public:
+  typedef std::pair<QuicStreamOffset, size_t> OffsetSizePair;
+
+  void SetUp() override {
+    // Test against a larger capacity then above tests. Also make sure the last
+    // block is partially available to use.
+    max_capacity_bytes_ = 6.25 * kBlockSizeBytes;
+    // Stream to be buffered should be larger than the capacity to test wrap
+    // around.
+    bytes_to_buffer_ = 2 * max_capacity_bytes_;
+    Initialize();
+
+    uint32 seed = base::RandInt(0, std::numeric_limits<int32>::max());
+    LOG(INFO) << "RandomWriteAndProcessInPlace test seed is " << seed;
+    rng_.set_seed(seed);
+  }
+
+  // Create an out-of-order source stream with given size to populate
+  // shuffled_buf_.
+  void CreateSourceAndShuffle(size_t max_chunk_size_bytes) {
+    max_chunk_size_bytes_ = max_chunk_size_bytes;
+    std::unique_ptr<OffsetSizePair[]> chopped_stream(
+        new OffsetSizePair[bytes_to_buffer_]);
+
+    // Split stream into small chunks with random length. chopped_stream will be
+    // populated with segmented stream chunks.
+    size_t start_chopping_offset = 0;
+    size_t iterations = 0;
+    while (start_chopping_offset < bytes_to_buffer_) {
+      size_t max_chunk = min<size_t>(max_chunk_size_bytes_,
+                                     bytes_to_buffer_ - start_chopping_offset);
+      size_t chunk_size = rng_.RandUint64() % max_chunk + 1;
+      chopped_stream[iterations] = OffsetSizePair(start_chopping_offset,
+                                                  chunk_size);
+      start_chopping_offset += chunk_size;
+      ++iterations;
+    }
+    DCHECK(start_chopping_offset == bytes_to_buffer_);
+    size_t chunk_num = iterations;
+
+    // Randomly change the sequence of in-ordered OffsetSizePairs to make a
+    // out-of-order array of OffsetSizePairs.
+    for (int i = chunk_num - 1; i >= 0; --i) {
+      size_t random_idx = rng_.RandUint64() % (i + 1);
+      DVLOG(1) << "chunk offset " << chopped_stream[random_idx].first
+               << " size " << chopped_stream[random_idx].second;
+      shuffled_buf_.push_front(chopped_stream[random_idx]);
+      chopped_stream[random_idx] = chopped_stream[i];
+  }
+}
+
+  // Write the currently first chunk of data in the out-of-order stream into
+  // StreamSequencerBuffer. If current chuck cannot be written into buffer
+  // because it goes beyond current capacity, move it to the end of
+  // shuffled_buf_ and write it later.
+  void WriteNextChunkToBuffer() {
+    OffsetSizePair& chunk = shuffled_buf_.front();
+    QuicStreamOffset offset = chunk.first;
+    const size_t num_to_write = chunk.second;
+    std::unique_ptr<char[]> write_buf{new char[max_chunk_size_bytes_]};
+    for (size_t i = 0; i < num_to_write; ++i) {
+      write_buf[i] = (offset + i) % 256;
+    }
+    base::StringPiece string_piece_w(write_buf.get(), num_to_write);
+    size_t written;
+    auto result = buffer_->OnStreamData(offset, string_piece_w,
+                                        clock_.ApproximateNow(), &written);
+    if (result == QUIC_NO_ERROR) {
+      shuffled_buf_.pop_front();
+      total_bytes_written_ += num_to_write;
+    } else {
+      // This chunk offset exceeds window size.
+      shuffled_buf_.push_back(chunk);
+      shuffled_buf_.pop_front();
+    }
+    DVLOG(1) << " write at offset: " << offset
+             << " len to write: " << num_to_write
+             << " write result: " << result
+             << " left over: " << shuffled_buf_.size();
+  }
+
+ protected:
+  std::list<OffsetSizePair> shuffled_buf_;
+  size_t max_chunk_size_bytes_;
+  QuicStreamOffset bytes_to_buffer_;
+  size_t total_bytes_written_ = 0;
+  size_t total_bytes_read_ = 0;
+  SimpleRandom rng_;
+};
+
+TEST_F(StreamSequencerBufferRandomIOTest, RandomWriteAndReadv) {
+  // Set kMaxReadSize larger than kBlockSizeBytes to test both small and large
+  // read.
+  const size_t kMaxReadSize = kBlockSizeBytes * 2;
+  // kNumReads is larger than 1 to test how multiple read destinations work.
+  const size_t kNumReads = 2;
+  // Since write and read operation have equal possibility to be called. Bytes
+  // to be written into and read out of should roughly the same.
+  const size_t kMaxWriteSize = kNumReads * kMaxReadSize;
+  size_t iterations = 0;
+
+  CreateSourceAndShuffle(kMaxWriteSize);
+
+  while ((!shuffled_buf_.empty() || total_bytes_read_ < bytes_to_buffer_) &&
+         iterations <= 2 * bytes_to_buffer_) {
+    uint8 next_action = shuffled_buf_.empty() ? uint8{1} : rng_.RandUint64() % 2;
+    DVLOG(1) << "iteration: " << iterations;
+    switch (next_action) {
+      case 0: {  // write
+        WriteNextChunkToBuffer();
+        ASSERT_TRUE(helper_->CheckBufferInvariants());
+        break;
+      }
+      case 1: {  // readv
+        std::unique_ptr<char[][kMaxReadSize]> read_buf{
+            new char[kNumReads][kMaxReadSize]};
+        iovec dest_iov[kNumReads];
+        size_t num_to_read = 0;
+        for (size_t i = 0; i < kNumReads; ++i) {
+          dest_iov[i].iov_base =
+              reinterpret_cast<void*>(const_cast<char*>(read_buf[i]));
+          dest_iov[i].iov_len = rng_.RandUint64() % kMaxReadSize;
+          num_to_read += dest_iov[i].iov_len;
+        }
+        size_t actually_read = buffer_->Readv(dest_iov, kNumReads);
+        ASSERT_LE(actually_read, num_to_read);
+        DVLOG(1) << " read from offset: " << total_bytes_read_
+                 << " size: " << num_to_read
+                 << " actual read: " << actually_read;
+        for (size_t i = 0; i < actually_read; ++i) {
+          char ch = (i + total_bytes_read_) % 256;
+          ASSERT_EQ(ch, GetCharFromIOVecs(i,
+                                                          dest_iov, kNumReads))
+              << " at iteration " << iterations;
+        }
+        total_bytes_read_ += actually_read;
+        ASSERT_EQ(total_bytes_read_, buffer_->BytesConsumed());
+        ASSERT_TRUE(helper_->CheckBufferInvariants());
+        break;
+      }
+    }
+    ++iterations;
+    ASSERT_LE(total_bytes_read_, total_bytes_written_);
+  }
+  EXPECT_LT(iterations, bytes_to_buffer_) << "runaway test";
+  EXPECT_LE(bytes_to_buffer_, total_bytes_read_)
+                                                << "iterations: " << iterations;
+  EXPECT_LE(bytes_to_buffer_, total_bytes_written_);
+}
+
+TEST_F(StreamSequencerBufferRandomIOTest, RandomWriteAndConsumeInPlace) {
+  // The value 4 is chosen such that the max write size is no larger than the
+  // maximum buffer capacity.
+  const size_t kMaxNumReads = 4;
+  // Adjust write amount be roughly equal to that GetReadableRegions() can get.
+  const size_t kMaxWriteSize = kMaxNumReads * kBlockSizeBytes;
+  ASSERT_LE(kMaxWriteSize, max_capacity_bytes_);
+  size_t iterations = 0;
+
+  CreateSourceAndShuffle(kMaxWriteSize);
+
+  while ((!shuffled_buf_.empty() || total_bytes_read_ < bytes_to_buffer_) &&
+         iterations <= 2 * bytes_to_buffer_) {
+    uint8 next_action = shuffled_buf_.empty() ? uint8{1} : rng_.RandUint64() % 2;
+    DVLOG(1) << "iteration: " << iterations;
+    switch (next_action) {
+      case 0: {   // write
+        WriteNextChunkToBuffer();
+        ASSERT_TRUE(helper_->CheckBufferInvariants());
+        break;
+      }
+      case 1: {   // GetReadableRegions and then MarkConsumed
+        size_t num_read = rng_.RandUint64() % kMaxNumReads + 1;
+        iovec dest_iov[kMaxNumReads];
+        ASSERT_TRUE(helper_->CheckBufferInvariants());
+        size_t actually_num_read = buffer_->GetReadableRegions(dest_iov, num_read);
+        ASSERT_LE(actually_num_read, num_read);
+        size_t avail_bytes = 0;
+        for (size_t i = 0; i < actually_num_read; ++i) {
+          avail_bytes += dest_iov[i].iov_len;
+        }
+        // process random number of bytes (check the value of each byte).
+        size_t bytes_to_process = rng_.RandUint64() % (avail_bytes + 1);
+        size_t bytes_processed = 0;
+        for (size_t i = 0; i < actually_num_read; ++i) {
+          size_t bytes_in_block = min<size_t>(
+              bytes_to_process - bytes_processed, dest_iov[i].iov_len);
+          if (bytes_in_block == 0) {
+            break;
+          }
+          for (size_t j = 0; j < bytes_in_block; ++j) {
+            ASSERT_LE(bytes_processed, bytes_to_process);
+            char char_expected =
+                (buffer_->BytesConsumed() + bytes_processed) % 256;
+            ASSERT_EQ(char_expected,
+                      reinterpret_cast<const char*>(dest_iov[i].iov_base)[j])
+                << " at iteration " << iterations;
+            ++bytes_processed;
+          }
+        }
+
+        buffer_->MarkConsumed(bytes_processed);
+
+        DVLOG(1) << "iteration " << iterations << ": try to get " << num_read
+                 << " readable regions, actually get " << actually_num_read
+                 << " from offset: " << total_bytes_read_
+                 << "\nprocesse bytes: " << bytes_processed;
+        total_bytes_read_ += bytes_processed;
+        ASSERT_EQ(total_bytes_read_, buffer_->BytesConsumed());
+        ASSERT_TRUE(helper_->CheckBufferInvariants());
+        break;
+      }
+    }
+    ++iterations;
+    ASSERT_LE(total_bytes_read_, total_bytes_written_);
+  }
+  EXPECT_LT(iterations, bytes_to_buffer_) << "runaway test";
+  EXPECT_LE(bytes_to_buffer_, total_bytes_read_)
+                                            << "iterations: " << iterations;
+  EXPECT_LE(bytes_to_buffer_, total_bytes_written_);
+}
+
+}  // anonymous namespace
+
+}  // namespace test
+
+}  // namespace net