relnote: refactoring the buffering logic in QUIC's stream sequencer.

Add a wrapper class QuicFrameList for underlying buffered_frames_ list in
QuicStreamSequencer to prepare for future changes of data structure for
buffered_frames_. It shares the same interface with its substitution
StreamSequencerBuffer.

Merge internal change: 104518889

R=rch@chromium.org
BUG=

Review URL: https://codereview.chromium.org/1400293002

Cr-Commit-Position: refs/heads/master@{#354361}

7 files changed, 341 insertions, 204 deletions

diff --git a/net/net.gypi b/net/net.gypi
index 3ec18c0..79b1e2c 100644
--- a/net/net.gypi
+++ b/net/net.gypi
@@ -333,6 +333,8 @@
       'quic/quic_flags.h',
       'quic/quic_flow_controller.cc',
       'quic/quic_flow_controller.h',
+      'quic/quic_frame_list.cc',
+      'quic/quic_frame_list.h',
       'quic/quic_framer.cc',
       'quic/quic_framer.h',
       'quic/quic_packet_creator.cc',
diff --git a/net/quic/quic_frame_list.cc b/net/quic/quic_frame_list.cc
new file mode 100644
index 0000000..a69c7c6
--- /dev/null
+++ b/net/quic/quic_frame_list.cc
@@ -0,0 +1,198 @@
+// 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/quic_frame_list.h"
+
+#include "base/logging.h"
+
+namespace net {
+
+QuicFrameList::FrameData::FrameData(QuicStreamOffset offset, string segment)
+    : offset(offset), segment(segment) {}
+
+QuicFrameList::QuicFrameList() {}
+
+QuicFrameList::~QuicFrameList() {
+  Clear();
+}
+
+QuicErrorCode QuicFrameList::WriteAtOffset(QuicStreamOffset offset,
+                                           StringPiece data,
+                                           size_t* const bytes_written) {
+  *bytes_written = 0;
+  const size_t data_len = data.size();
+  auto insertion_point = FindInsertionPoint(offset, data_len);
+  if (IsDuplicate(offset, data_len, insertion_point)) {
+    return QUIC_NO_ERROR;
+  }
+
+  if (FrameOverlapsBufferedData(offset, data_len, insertion_point)) {
+    return QUIC_INVALID_STREAM_DATA;
+  }
+
+  DVLOG(1) << "Buffering stream data at offset " << offset;
+  // Inserting an empty string and then copying to avoid the extra copy.
+  insertion_point = frame_list_.insert(insertion_point, FrameData(offset, ""));
+  data.CopyToString(&insertion_point->segment);
+  *bytes_written = data_len;
+  return QUIC_NO_ERROR;
+}
+
+// Finds the place the frame should be inserted.  If an identical frame is
+// present, stops on the identical frame.
+list<QuicFrameList::FrameData>::iterator QuicFrameList::FindInsertionPoint(
+    QuicStreamOffset offset,
+    size_t len) {
+  if (frame_list_.empty()) {
+    return frame_list_.begin();
+  }
+  // If it's after all buffered_frames, return the end.
+  if (offset >=
+      (frame_list_.rbegin()->offset + frame_list_.rbegin()->segment.length())) {
+    return frame_list_.end();
+  }
+  auto iter = frame_list_.begin();
+  // Only advance the iterator if the data begins after the already received
+  // frame.  If the new frame overlaps with an existing frame, the iterator will
+  // still point to the frame it overlaps with.
+  while (iter != frame_list_.end() &&
+         offset >= iter->offset + iter->segment.length()) {
+    ++iter;
+  }
+  return iter;
+}
+
+// Returns true if |frame| contains data which overlaps buffered data
+// (indicating an invalid stream frame has been received).
+bool QuicFrameList::FrameOverlapsBufferedData(
+    QuicStreamOffset offset,
+    size_t data_len,
+    list<FrameData>::const_iterator insertion_point) const {
+  if (frame_list_.empty() || insertion_point == frame_list_.end()) {
+    return false;
+  }
+  // If there is a buffered frame with a higher starting offset, then check to
+  // see if the new frame overlaps the beginning of the higher frame.
+  if (offset < insertion_point->offset &&
+      offset + data_len > insertion_point->offset) {
+    DVLOG(1) << "New frame overlaps next frame: " << offset << " + " << data_len
+             << " > " << insertion_point->offset;
+    return true;
+  }
+  // If there is a buffered frame with a lower starting offset, then check to
+  // see if the buffered frame runs into the new frame.
+  if (offset >= insertion_point->offset &&
+      offset < insertion_point->offset + insertion_point->segment.length()) {
+    DVLOG(1) << "Preceeding frame overlaps new frame: "
+             << insertion_point->offset << " + "
+             << insertion_point->segment.length() << " > " << offset;
+    return true;
+  }
+
+  return false;
+}
+
+// Returns true if the sequencer has received this frame before.
+bool QuicFrameList::IsDuplicate(
+    QuicStreamOffset offset,
+    size_t data_len,
+    list<FrameData>::const_iterator insertion_point) const {
+  // A frame is duplicate if the frame offset is smaller than the bytes consumed
+  // or identical to an already received frame.
+  return offset < total_bytes_read_ || (insertion_point != frame_list_.end() &&
+                                        offset == insertion_point->offset);
+}
+
+int QuicFrameList::GetReadableRegions(struct iovec* iov, int iov_len) const {
+  list<FrameData>::const_iterator it = frame_list_.begin();
+  int index = 0;
+  QuicStreamOffset offset = total_bytes_read_;
+  while (it != frame_list_.end() && index < iov_len) {
+    if (it->offset != offset) {
+      return index;
+    }
+
+    iov[index].iov_base =
+        static_cast<void*>(const_cast<char*>(it->segment.data()));
+    iov[index].iov_len = it->segment.size();
+    offset += it->segment.size();
+
+    ++index;
+    ++it;
+  }
+  return index;
+}
+
+bool QuicFrameList::IncreaseTotalReadAndInvalidate(size_t bytes_used) {
+  size_t end_offset = total_bytes_read_ + bytes_used;
+  while (!frame_list_.empty() && end_offset != total_bytes_read_) {
+    list<FrameData>::iterator it = frame_list_.begin();
+    if (it->offset != total_bytes_read_) {
+      return false;
+    }
+
+    if (it->offset + it->segment.length() <= end_offset) {
+      total_bytes_read_ += it->segment.length();
+      // This chunk is entirely consumed.
+      frame_list_.erase(it);
+      continue;
+    }
+
+    // Partially consume this frame.
+    size_t delta = end_offset - it->offset;
+    total_bytes_read_ += delta;
+    string new_data = it->segment.substr(delta);
+    frame_list_.erase(it);
+    frame_list_.push_front(FrameData(total_bytes_read_, new_data));
+    break;
+  }
+  return true;
+}
+
+size_t QuicFrameList::ReadvAndInvalidate(const struct iovec* iov,
+                                         size_t iov_len) {
+  list<FrameData>::iterator it = frame_list_.begin();
+  size_t iov_index = 0;
+  size_t iov_offset = 0;
+  size_t frame_offset = 0;
+  QuicStreamOffset initial_bytes_consumed = total_bytes_read_;
+
+  while (iov_index < iov_len && it != frame_list_.end() &&
+         it->offset == total_bytes_read_) {
+    int bytes_to_read = std::min(iov[iov_index].iov_len - iov_offset,
+                                 it->segment.size() - frame_offset);
+
+    char* iov_ptr = static_cast<char*>(iov[iov_index].iov_base) + iov_offset;
+    memcpy(iov_ptr, it->segment.data() + frame_offset, bytes_to_read);
+    frame_offset += bytes_to_read;
+    iov_offset += bytes_to_read;
+
+    if (iov[iov_index].iov_len == iov_offset) {
+      // We've filled this buffer.
+      iov_offset = 0;
+      ++iov_index;
+    }
+    if (it->segment.size() == frame_offset) {
+      // We've copied this whole frame
+      total_bytes_read_ += it->segment.size();
+      frame_list_.erase(it);
+      it = frame_list_.begin();
+      frame_offset = 0;
+    }
+  }
+  // Done copying.  If there is a partial frame, update it.
+  if (frame_offset != 0) {
+    frame_list_.push_front(
+        FrameData(it->offset + frame_offset, it->segment.substr(frame_offset)));
+    frame_list_.erase(it);
+    total_bytes_read_ += frame_offset;
+  }
+  return total_bytes_read_ - initial_bytes_consumed;
+}
+
+bool QuicFrameList::HasBytesToRead() const {
+  return !frame_list_.empty() &&
+         frame_list_.begin()->offset == total_bytes_read_;
+}
+}  // namespace net_quic
diff --git a/net/quic/quic_frame_list.h b/net/quic/quic_frame_list.h
new file mode 100644
index 0000000..55ee804
--- /dev/null
+++ b/net/quic/quic_frame_list.h
@@ -0,0 +1,99 @@
+// 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.
+
+#ifndef NET_QUIC_QUIC_FRAME_LIST_H_
+#define NET_QUIC_QUIC_FRAME_LIST_H_
+
+#include "net/quic/quic_frame_list.h"
+#include "net/quic/quic_protocol.h"
+
+using base::StringPiece;
+using std::string;
+using std::list;
+
+namespace net {
+
+namespace test {
+class QuicStreamSequencerPeer;
+}
+
+class NET_EXPORT_PRIVATE QuicFrameList {
+ public:
+  // A contiguous segment received by a QUIC stream.
+  struct FrameData {
+    FrameData(QuicStreamOffset offset, string segment);
+
+    const QuicStreamOffset offset;
+    string segment;
+  };
+
+  explicit QuicFrameList();
+
+  ~QuicFrameList();
+
+  // Clear the buffer such that it is in its initial, newly constructed state.
+  void Clear() { frame_list_.clear(); }
+
+  // Returns true if there is nothing to read in this buffer.
+  bool Empty() const { return frame_list_.empty(); }
+
+  // Write the supplied data to this buffer. If the write was successful,
+  // return the number of bytes written in |bytes_written|.
+  // Return QUIC_INVALID_STREAM_DATA if |data| overlaps with existing data.
+  // No data will be written.
+  // Return QUIC_NO_ERROR, if |data| is duplicated with data written previously,
+  // and |bytes_written| = 0
+  QuicErrorCode WriteAtOffset(QuicStreamOffset offset,
+                              StringPiece data,
+                              size_t* bytes_written);
+
+  // Read from this buffer into given iovec array, upto number of iov_len iovec
+  // objects.
+  // Returns the number of bytes read into iov.
+  size_t ReadvAndInvalidate(const struct iovec* iov, size_t iov_len);
+
+  // Returns the readable region of valid data in iovec format. The readable
+  // region is the buffer region where there is valid data not yet read by
+  // client. ReadAndInvalidate() and WriteAtOffset() change the readable region.
+  // The return value of this function is the number of iovec entries
+  // filled into in iov. If the region is empty, one iovec entry with 0 length
+  // is returned, and the function returns 0. If there are more readable
+  // regions than iov_size, the function only processes the first
+  // iov_size of them.
+  int GetReadableRegions(struct iovec* iov, int iov_len) const;
+
+  // Called after GetReadableRegions() to accumulate total_bytes_read_ and free
+  // up block when all data in it have been read out.
+  // Pre-requisite: bytes_used <= ReadableBytes()
+  bool IncreaseTotalReadAndInvalidate(size_t bytes_used);
+
+  // Whether there are bytes can be read out (offset == total_bytes_read_)
+  bool HasBytesToRead() const;
+
+  size_t size() const { return frame_list_.size(); }
+
+  QuicStreamOffset total_bytes_read() const { return total_bytes_read_; }
+
+ private:
+  friend class test::QuicStreamSequencerPeer;
+
+  list<FrameData>::iterator FindInsertionPoint(QuicStreamOffset offset,
+                                               size_t len);
+
+  bool FrameOverlapsBufferedData(
+      QuicStreamOffset offset,
+      size_t data_len,
+      list<FrameData>::const_iterator insertion_point) const;
+
+  bool IsDuplicate(QuicStreamOffset offset,
+                   size_t data_len,
+                   list<FrameData>::const_iterator insertion_point) const;
+
+  list<FrameData> frame_list_;
+  QuicStreamOffset total_bytes_read_ = 0;
+};
+
+}  // namespace net_quic
+
+#endif  // NET_QUIC_QUIC_FRAME_LIST_H_
diff --git a/net/quic/quic_stream_sequencer.cc b/net/quic/quic_stream_sequencer.cc
index bd1bc6e..3989c4f 100644
--- a/net/quic/quic_stream_sequencer.cc
+++ b/net/quic/quic_stream_sequencer.cc
@@ -9,6 +9,7 @@
 #include <utility>
 
 #include "base/logging.h"
+#include "net/quic/quic_frame_list.h"
 #include "net/quic/reliable_quic_stream.h"
 
 using std::min;
@@ -17,10 +18,6 @@ using std::string;
 
 namespace net {
 
-QuicStreamSequencer::FrameData::FrameData(QuicStreamOffset offset,
-                                          const string& segment)
-    : offset(offset), segment(segment) {}
-
 QuicStreamSequencer::QuicStreamSequencer(ReliableQuicStream* quic_stream)
     : stream_(quic_stream),
       num_bytes_consumed_(0),
@@ -29,27 +26,12 @@ QuicStreamSequencer::QuicStreamSequencer(ReliableQuicStream* quic_stream)
       num_bytes_buffered_(0),
       num_frames_received_(0),
       num_duplicate_frames_received_(0),
-      num_early_frames_received_(0) {
-}
+      num_early_frames_received_(0) {}
 
-QuicStreamSequencer::~QuicStreamSequencer() {
-}
+QuicStreamSequencer::~QuicStreamSequencer() {}
 
 void QuicStreamSequencer::OnStreamFrame(const QuicStreamFrame& frame) {
   ++num_frames_received_;
-  FrameList::iterator insertion_point = FindInsertionPoint(frame);
-  if (IsDuplicate(frame, insertion_point)) {
-    ++num_duplicate_frames_received_;
-    // Silently ignore duplicates.
-    return;
-  }
-
-  if (FrameOverlapsBufferedData(frame, insertion_point)) {
-    stream_->CloseConnectionWithDetails(
-        QUIC_INVALID_STREAM_FRAME, "Stream frame overlaps with buffered data.");
-    return;
-  }
-
   const QuicStreamOffset byte_offset = frame.offset;
   const size_t data_len = frame.data.length();
   if (data_len == 0 && !frame.fin) {
@@ -65,16 +47,25 @@ void QuicStreamSequencer::OnStreamFrame(const QuicStreamFrame& frame) {
       return;
     }
   }
+  size_t bytes_written;
+  QuicErrorCode result =
+      buffered_frames_.WriteAtOffset(byte_offset, frame.data, &bytes_written);
+
+  if (result == QUIC_INVALID_STREAM_DATA) {
+    stream_->CloseConnectionWithDetails(
+        QUIC_INVALID_STREAM_FRAME, "Stream frame overlaps with buffered data.");
+    return;
+  }
+  if (result == QUIC_NO_ERROR && bytes_written == 0) {
+    ++num_duplicate_frames_received_;
+    // Silently ignore duplicates.
+    return;
+  }
 
   if (byte_offset > num_bytes_consumed_) {
     ++num_early_frames_received_;
   }
 
-  DVLOG(1) << "Buffering stream data at offset " << byte_offset;
-  // Inserting an empty string and then copying to avoid the extra copy.
-  insertion_point =
-      buffered_frames_.insert(insertion_point, FrameData(byte_offset, ""));
-  frame.data.CopyToString(&insertion_point->segment);
   num_bytes_buffered_ += data_len;
 
   if (blocked_) {
@@ -103,13 +94,12 @@ void QuicStreamSequencer::CloseStreamAtOffset(QuicStreamOffset offset) {
 bool QuicStreamSequencer::MaybeCloseStream() {
   if (!blocked_ && IsClosed()) {
     DVLOG(1) << "Passing up termination, as we've processed "
-             << num_bytes_consumed_ << " of " << close_offset_
-             << " bytes.";
+             << num_bytes_consumed_ << " of " << close_offset_ << " bytes.";
     // This will cause the stream to consume the fin.
     // Technically it's an error if num_bytes_consumed isn't exactly
     // equal, but error handling seems silly at this point.
     stream_->OnDataAvailable();
-    buffered_frames_.clear();
+    buffered_frames_.Clear();
     num_bytes_buffered_ = 0;
     return true;
   }
@@ -118,163 +108,36 @@ bool QuicStreamSequencer::MaybeCloseStream() {
 
 int QuicStreamSequencer::GetReadableRegions(iovec* iov, size_t iov_len) const {
   DCHECK(!blocked_);
-  FrameList::const_iterator it = buffered_frames_.begin();
-  size_t index = 0;
-  QuicStreamOffset offset = num_bytes_consumed_;
-  while (it != buffered_frames_.end() && index < iov_len) {
-    if (it->offset != offset) {
-      return index;
-    }
-
-    iov[index].iov_base =
-        static_cast<void*>(const_cast<char*>(it->segment.data()));
-    iov[index].iov_len = it->segment.size();
-    offset += it->segment.size();
-
-    ++index;
-    ++it;
-  }
-  return index;
+  return buffered_frames_.GetReadableRegions(iov, iov_len);
 }
 
 int QuicStreamSequencer::Readv(const struct iovec* iov, size_t iov_len) {
   DCHECK(!blocked_);
-  FrameList::iterator it = buffered_frames_.begin();
-  size_t iov_index = 0;
-  size_t iov_offset = 0;
-  size_t frame_offset = 0;
-  QuicStreamOffset initial_bytes_consumed = num_bytes_consumed_;
-
-  while (iov_index < iov_len && it != buffered_frames_.end() &&
-         it->offset == num_bytes_consumed_) {
-    int bytes_to_read = min(iov[iov_index].iov_len - iov_offset,
-                            it->segment.size() - frame_offset);
-
-    char* iov_ptr = static_cast<char*>(iov[iov_index].iov_base) + iov_offset;
-    memcpy(iov_ptr, it->segment.data() + frame_offset, bytes_to_read);
-    frame_offset += bytes_to_read;
-    iov_offset += bytes_to_read;
-
-    if (iov[iov_index].iov_len == iov_offset) {
-      // We've filled this buffer.
-      iov_offset = 0;
-      ++iov_index;
-    }
-    if (it->segment.size() == frame_offset) {
-      // We've copied this whole frame
-      RecordBytesConsumed(it->segment.size());
-      buffered_frames_.erase(it);
-      it = buffered_frames_.begin();
-      frame_offset = 0;
-    }
-  }
-  // Done copying.  If there is a partial frame, update it.
-  if (frame_offset != 0) {
-    buffered_frames_.push_front(
-        FrameData(it->offset + frame_offset, it->segment.substr(frame_offset)));
-    buffered_frames_.erase(it);
-    RecordBytesConsumed(frame_offset);
-  }
-  return static_cast<int>(num_bytes_consumed_ - initial_bytes_consumed);
+  size_t bytes_read = buffered_frames_.ReadvAndInvalidate(iov, iov_len);
+  RecordBytesConsumed(bytes_read);
+  return static_cast<int>(bytes_read);
 }
 
 bool QuicStreamSequencer::HasBytesToRead() const {
-  return !buffered_frames_.empty() &&
-         buffered_frames_.begin()->offset == num_bytes_consumed_;
+  return buffered_frames_.HasBytesToRead();
 }
 
 bool QuicStreamSequencer::IsClosed() const {
   return num_bytes_consumed_ >= close_offset_;
 }
 
-QuicStreamSequencer::FrameList::iterator
-QuicStreamSequencer::FindInsertionPoint(const QuicStreamFrame& frame) {
-  if (buffered_frames_.empty()) {
-    return buffered_frames_.begin();
-  }
-  // If it's after all buffered_frames, return the end.
-  if (frame.offset >= (buffered_frames_.rbegin()->offset +
-                       buffered_frames_.rbegin()->segment.length())) {
-    return buffered_frames_.end();
-  }
-  FrameList::iterator iter = buffered_frames_.begin();
-  // Only advance the iterator if the data begins after the already received
-  // frame.  If the new frame overlaps with an existing frame, the iterator will
-  // still point to the frame it overlaps with.
-  while (iter != buffered_frames_.end() &&
-         frame.offset >= iter->offset + iter->segment.length()) {
-    ++iter;
-  }
-  return iter;
-}
-
-bool QuicStreamSequencer::FrameOverlapsBufferedData(
-    const QuicStreamFrame& frame,
-    FrameList::const_iterator insertion_point) const {
-  if (buffered_frames_.empty() || insertion_point == buffered_frames_.end()) {
-    return false;
-  }
-  // If there is a buffered frame with a higher starting offset, then check to
-  // see if the new frame overlaps the beginning of the higher frame.
-  if (frame.offset < insertion_point->offset &&
-      frame.offset + frame.data.length() > insertion_point->offset) {
-    DVLOG(1) << "New frame overlaps next frame: " << frame.offset << " + "
-             << frame.data.size() << " > " << insertion_point->offset;
-    return true;
-  }
-  // If there is a buffered frame with a lower starting offset, then check to
-  // see if the buffered frame runs into the new frame.
-  if (frame.offset >= insertion_point->offset &&
-      frame.offset <
-          insertion_point->offset + insertion_point->segment.length()) {
-    DVLOG(1) << "Preceeding frame overlaps new frame: "
-             << insertion_point->offset << " + "
-             << insertion_point->segment.length() << " > " << frame.offset;
-    return true;
-  }
-
-  return false;
-}
-
 void QuicStreamSequencer::MarkConsumed(size_t num_bytes_consumed) {
   DCHECK(!blocked_);
-  size_t end_offset = num_bytes_consumed_ + num_bytes_consumed;
-  while (!buffered_frames_.empty() && end_offset != num_bytes_consumed_) {
-    FrameList::iterator it = buffered_frames_.begin();
-    if (it->offset != num_bytes_consumed_) {
-      LOG(DFATAL) << "Invalid argument to MarkConsumed. "
-                  << " num_bytes_consumed_: " << num_bytes_consumed_
-                  << " end_offset: " << end_offset << " offset: " << it->offset
-                  << " length: " << it->segment.length();
-      stream_->Reset(QUIC_ERROR_PROCESSING_STREAM);
-      return;
-    }
-
-    if (it->offset + it->segment.length() <= end_offset) {
-      RecordBytesConsumed(it->segment.length());
-      // This chunk is entirely consumed.
-      buffered_frames_.erase(it);
-      continue;
-    }
-
-    // Partially consume this frame.
-    size_t delta = end_offset - it->offset;
-    RecordBytesConsumed(delta);
-    string new_data = it->segment.substr(delta);
-    buffered_frames_.erase(it);
-    buffered_frames_.push_front(FrameData(num_bytes_consumed_, new_data));
-    break;
+  bool result =
+      buffered_frames_.IncreaseTotalReadAndInvalidate(num_bytes_consumed);
+  if (!result) {
+    LOG(DFATAL) << "Invalid argument to MarkConsumed."
+                << " expect to consume: " << num_bytes_consumed
+                << ", but not enough bytes available.";
+    stream_->Reset(QUIC_ERROR_PROCESSING_STREAM);
+    return;
   }
-}
-
-bool QuicStreamSequencer::IsDuplicate(
-    const QuicStreamFrame& frame,
-    FrameList::const_iterator insertion_point) const {
-  // A frame is duplicate if the frame offset is smaller than the bytes consumed
-  // or identical to an already received frame.
-  return frame.offset < num_bytes_consumed_ ||
-         (insertion_point != buffered_frames_.end() &&
-          frame.offset == insertion_point->offset);
+  RecordBytesConsumed(num_bytes_consumed);
 }
 
 void QuicStreamSequencer::SetBlockedUntilFlush() {
diff --git a/net/quic/quic_stream_sequencer.h b/net/quic/quic_stream_sequencer.h
index 60a950b..a1bdd32 100644
--- a/net/quic/quic_stream_sequencer.h
+++ b/net/quic/quic_stream_sequencer.h
@@ -9,7 +9,7 @@
 #include <string>
 
 #include "base/basictypes.h"
-#include "net/base/iovec.h"
+#include "net/quic/quic_frame_list.h"
 #include "net/quic/quic_protocol.h"
 
 namespace net {
@@ -25,19 +25,6 @@ class ReliableQuicStream;
 // up to the next layer.
 class NET_EXPORT_PRIVATE QuicStreamSequencer {
  public:
-  // A contiguous segment received by a QUIC stream.
-  struct FrameData {
-    FrameData(QuicStreamOffset offset, const std::string& segment);
-
-    const QuicStreamOffset offset;
-    std::string segment;
-  };
-
-  // TODO(alyssar) use something better than strings.
-  // Maybe write new frames into a ring buffer, and keep track of consumed
-  // bytes, and gaps.
-  typedef std::list<FrameData> FrameList;
-
   explicit QuicStreamSequencer(ReliableQuicStream* quic_stream);
   virtual ~QuicStreamSequencer();
 
@@ -93,20 +80,6 @@ class NET_EXPORT_PRIVATE QuicStreamSequencer {
  private:
   friend class test::QuicStreamSequencerPeer;
 
-  // Finds the place the frame should be inserted.  If an identical frame is
-  // present, stops on the identical frame.
-  FrameList::iterator FindInsertionPoint(const QuicStreamFrame& frame);
-
-  // Returns true if |frame| contains data which overlaps buffered data
-  // (indicating an invalid stream frame has been received).
-  bool FrameOverlapsBufferedData(
-      const QuicStreamFrame& frame,
-      FrameList::const_iterator insertion_point) const;
-
-  // Returns true if the sequencer has received this frame before.
-  bool IsDuplicate(const QuicStreamFrame& frame,
-                   FrameList::const_iterator insertion_point) const;
-
   // Wait until we've seen 'offset' bytes, and then terminate the stream.
   void CloseStreamAtOffset(QuicStreamOffset offset);
 
@@ -125,7 +98,7 @@ class NET_EXPORT_PRIVATE QuicStreamSequencer {
   QuicStreamOffset num_bytes_consumed_;
 
   // Stores buffered frames in offset order.
-  FrameList buffered_frames_;
+  QuicFrameList buffered_frames_;
 
   // The offset, if any, we got a stream termination for.  When this many bytes
   // have been processed, the sequencer will be closed.
diff --git a/net/quic/quic_stream_sequencer_test.cc b/net/quic/quic_stream_sequencer_test.cc
index 994ce84..a91929b 100644
--- a/net/quic/quic_stream_sequencer_test.cc
+++ b/net/quic/quic_stream_sequencer_test.cc
@@ -523,8 +523,8 @@ TEST_F(QuicStreamSequencerTest, MarkConsumedError) {
   // stream to be closed.
   EXPECT_CALL(stream_, Reset(QUIC_ERROR_PROCESSING_STREAM));
   EXPECT_DFATAL(sequencer_->MarkConsumed(4),
-                "Invalid argument to MarkConsumed.  num_bytes_consumed_: 3 "
-                "end_offset: 4 offset: 9 length: 17");
+                "Invalid argument to MarkConsumed."
+                " expect to consume: 4, but not enough bytes available.");
 }
 
 TEST_F(QuicStreamSequencerTest, MarkConsumedWithMissingPacket) {
diff --git a/net/quic/test_tools/quic_stream_sequencer_peer.cc b/net/quic/test_tools/quic_stream_sequencer_peer.cc
index 591a2e9..0d2c61b 100644
--- a/net/quic/test_tools/quic_stream_sequencer_peer.cc
+++ b/net/quic/test_tools/quic_stream_sequencer_peer.cc
@@ -22,9 +22,11 @@ size_t QuicStreamSequencerPeer::GetNumBufferedFrames(
 bool QuicStreamSequencerPeer::FrameOverlapsBufferedData(
     QuicStreamSequencer* sequencer,
     const QuicStreamFrame& frame) {
-  QuicStreamSequencer::FrameList::iterator it =
-      sequencer->FindInsertionPoint(frame);
-  return sequencer->FrameOverlapsBufferedData(frame, it);
+  list<QuicFrameList::FrameData>::iterator it =
+      sequencer->buffered_frames_.FindInsertionPoint(frame.offset,
+                                                     frame.data.length());
+  return sequencer->buffered_frames_.FrameOverlapsBufferedData(
+      frame.offset, frame.data.length(), it);
 }
 
 // static