Add QuicStream and friends to QUIC code.

net/quic/quic_stream_sequencer_test.cc

+// Copyright (c) 2012 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_stream_sequencer.h"
+
+#include <utility>
+#include <vector>
+
+#include "base/rand_util.h"
+#include "net/quic/reliable_quic_stream.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using base::StringPiece;
+using std::min;
+using std::pair;
+using std::vector;
+using testing::_;
+using testing::AnyNumber;
+using testing::InSequence;
+using testing::Return;
+using testing::StrEq;
+
+namespace net {
+
+class QuicStreamSequencerPeer : public QuicStreamSequencer {
+ public:
+  explicit QuicStreamSequencerPeer(ReliableQuicStream* stream)
+      : QuicStreamSequencer(stream) {
+  }
+
+  QuicStreamSequencerPeer(int32 max_mem, ReliableQuicStream* stream)
+      : QuicStreamSequencer(max_mem, stream) {}
+
+  virtual bool OnFrame(QuicStreamOffset byte_offset,
+                          const char* data,

[jar (doing other things), 2012/11/01 22:21:10]

nit: indent

[Ryan Hamilton, 2012/11/01 22:52:20]

Fixed upstream.

+                          uint32 data_len) {
+    QuicStreamFrame frame;
+    frame.stream_id = 1;
+    frame.offset = byte_offset;
+    frame.data = StringPiece(data, data_len);
+    return OnStreamFrame(frame);
+  }
+
+  void SetMemoryLimit(size_t limit) {
+    max_frame_memory_ = limit;
+  }
+
+  ReliableQuicStream* stream() { return stream_; }

[jar (doing other things), 2012/11/01 22:21:10]

nit: most of these should be const methods. line 52 might need a const return
type.

[Ryan Hamilton, 2012/11/01 22:52:20]

Fixed upstream.

+  uint64 num_bytes_consumed() { return num_bytes_consumed_; }
+  FrameMap* frames() { return &frames_; }
+  int32 max_frame_memory() { return max_frame_memory_; }
+  QuicStreamOffset close_offset() { return close_offset_; }
+};
+
+class MockStream : public ReliableQuicStream {
+ public:
+  MockStream(QuicSession* session, QuicStreamId id)
+      : ReliableQuicStream(id, session) {
+  }
+
+  MOCK_METHOD1(TerminateFromPeer, void(bool half_close));
+  MOCK_METHOD2(ProcessData, uint32(const char* data, uint32 data_len));
+  MOCK_METHOD1(Close, void(QuicErrorCode error));
+};
+
+namespace {
+
+static const char kPayload[] =
+    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+
+class QuicStreamSequencerTest : public ::testing::Test {
+ protected:
+  QuicStreamSequencerTest()
+      : session_(NULL),
+        stream_(session_,  1),
+        sequencer_(new QuicStreamSequencerPeer(&stream_)) {
+  }
+
+  QuicSession* session_;
+  testing::StrictMock<MockStream> stream_;
+  scoped_ptr<QuicStreamSequencerPeer> sequencer_;
+};
+
+TEST_F(QuicStreamSequencerTest, RejectOldFrame) {
+  EXPECT_CALL(stream_, ProcessData("abc", 3))
+      .WillOnce(Return(3));
+
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+  EXPECT_EQ(0u, sequencer_->frames()->size());
+  EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
+  // Nack this - it matches a past sequence number and we should not see it
+  // again.
+  EXPECT_FALSE(sequencer_->OnFrame(0, "def", 3));
+  EXPECT_EQ(0u, sequencer_->frames()->size());
+}
+
+TEST_F(QuicStreamSequencerTest, RejectOverlyLargeFrame) {
+  /*
+  EXPECT_DFATAL(sequencer_.reset(new QuicStreamSequencerPeer(2, &stream_)),
+                "Setting max frame memory to 2.  "
+                "Some frames will be impossible to handle.");
+
+  EXPECT_DEBUG_DEATH(sequencer_->OnFrame(0, "abc", 3), "");
+  */
+}
+
+TEST_F(QuicStreamSequencerTest, DropFramePastBuffering) {
+  sequencer_->SetMemoryLimit(3);
+
+  EXPECT_FALSE(sequencer_->OnFrame(3, "abc", 3));
+}
+
+TEST_F(QuicStreamSequencerTest, RejectBufferedFrame) {
+  EXPECT_CALL(stream_, ProcessData("abc", 3));
+
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+  EXPECT_EQ(1u, sequencer_->frames()->size());
+  EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
+  // Ignore this - it matches a buffered frame.
+  // Right now there's no checking that the payload is consistent.
+  EXPECT_FALSE(sequencer_->OnFrame(0, "def", 3));
+  EXPECT_EQ(1u, sequencer_->frames()->size());
+}
+
+TEST_F(QuicStreamSequencerTest, FullFrameConsumed) {
+  EXPECT_CALL(stream_, ProcessData("abc", 3))
+            .WillOnce(Return(3));

[jar (doing other things), 2012/11/01 22:21:10]

nit: indent

[Ryan Hamilton, 2012/11/01 22:52:20]

Fixed upstream.

+
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+  EXPECT_EQ(0u, sequencer_->frames()->size());
+  EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
+}
+
+TEST_F(QuicStreamSequencerTest, PartialFrameConsumed) {
+  EXPECT_CALL(stream_, ProcessData("abc", 3))
+            .WillOnce(Return(2));

[jar (doing other things), 2012/11/01 22:21:10]

nit: indent  (happens several more times).

[Ryan Hamilton, 2012/11/01 22:52:20]

Fixed upstream.

+
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+  EXPECT_EQ(1u, sequencer_->frames()->size());
+  EXPECT_EQ(2u, sequencer_->num_bytes_consumed());
+  EXPECT_EQ("c", sequencer_->frames()->find(2)->second);
+}
+
+TEST_F(QuicStreamSequencerTest, NextxFrameNotConsumed) {
+  EXPECT_CALL(stream_, ProcessData("abc", 3))
+            .WillOnce(Return(0));
+
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+  EXPECT_EQ(1u, sequencer_->frames()->size());
+  EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
+  EXPECT_EQ("abc", sequencer_->frames()->find(0)->second);
+}
+
+TEST_F(QuicStreamSequencerTest, FutureFrameNotProcessed) {
+  EXPECT_TRUE(sequencer_->OnFrame(3, "abc", 3));
+  EXPECT_EQ(1u, sequencer_->frames()->size());
+  EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
+  EXPECT_EQ("abc", sequencer_->frames()->find(3)->second);
+}
+
+TEST_F(QuicStreamSequencerTest, OutOfOrderFrameProcessed) {
+  // Buffer the first
+  EXPECT_TRUE(sequencer_->OnFrame(6, "ghi", 3));
+  EXPECT_EQ(1u, sequencer_->frames()->size());
+  EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
+  // Buffer the second
+  EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3));
+  EXPECT_EQ(2u, sequencer_->frames()->size());
+  EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
+
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData("abc", 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, ProcessData(StrEq("ghi"), 3)).WillOnce(Return(3));
+
+  // Ack right away
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+  EXPECT_EQ(9u, sequencer_->num_bytes_consumed());
+
+  EXPECT_EQ(0u, sequencer_->frames()->size());
+}
+
+TEST_F(QuicStreamSequencerTest, OutOfOrderFramesProcessedWithBuffering) {
+  sequencer_->SetMemoryLimit(9);
+
+  // Too far to buffer.
+  EXPECT_FALSE(sequencer_->OnFrame(9, "jkl", 3));
+
+  // We can afford to buffer this.
+  EXPECT_TRUE(sequencer_->OnFrame(6, "ghi", 3));
+  EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
+
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData("abc", 3)).WillOnce(Return(3));
+
+  // Ack right away
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+  EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
+
+  // We should be willing to buffer this now.
+  EXPECT_TRUE(sequencer_->OnFrame(9, "jkl", 3));
+  EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
+
+  EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, ProcessData(StrEq("ghi"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, ProcessData(StrEq("jkl"), 3)).WillOnce(Return(3));
+
+  EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3));
+  EXPECT_EQ(12u, sequencer_->num_bytes_consumed());
+  EXPECT_EQ(0u, sequencer_->frames()->size());
+}
+
+TEST_F(QuicStreamSequencerTest, OutOfOrderFramesBlockignWithReadv) {
+  sequencer_->SetMemoryLimit(9);
+  char buffer[20];
+  iovec iov[2];
+  iov[0].iov_base = &buffer[0];
+  iov[0].iov_len = 1;
+  iov[1].iov_base = &buffer[1];
+  iov[1].iov_len = 2;
+
+  // Push abc - process.
+  // Push jkl - buffer (not next data)
+  // Push def - don't process.
+  // Push mno - drop (too far out)
+  // Push ghi - buffer (def not processed)
+  // Read 2.
+  // Push mno - buffer (not all read)
+  // Read all
+  // Push pqr - process
+
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(0));
+  EXPECT_CALL(stream_, ProcessData(StrEq("pqr"), 3)).WillOnce(Return(3));
+
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+  EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3));
+  EXPECT_TRUE(sequencer_->OnFrame(9, "jkl", 3));
+  EXPECT_FALSE(sequencer_->OnFrame(12, "mno", 3));
+  EXPECT_TRUE(sequencer_->OnFrame(6, "ghi", 3));
+
+  // Read 3 bytes.
+  EXPECT_EQ(3u, sequencer_->Readv(iov, 2));
+  EXPECT_EQ(0, strncmp(buffer, "def", 3));
+
+  // Now we have space to bufer this.
+  EXPECT_TRUE(sequencer_->OnFrame(12, "mno", 3));
+
+  // Read the remaining 9 bytes.
+  iov[1].iov_len = 19;
+  EXPECT_EQ(9u, sequencer_->Readv(iov, 2));
+  EXPECT_EQ(0, strncmp(buffer, "ghijklmno", 9));
+
+  EXPECT_TRUE(sequencer_->OnFrame(15, "pqr", 3));
+}
+
+// Same as above, just using a different method for reading.
+TEST_F(QuicStreamSequencerTest, OutOfOrderFramesBlockignWithGetReadableRegion) {
+  sequencer_->SetMemoryLimit(9);
+  iovec iov[5];

[jar (doing other things), 2012/11/01 22:21:10]

nit: move closer to first use.

[Ryan Hamilton, 2012/11/01 22:52:20]

Fixed upstream.

+
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(0));
+  EXPECT_CALL(stream_, ProcessData(StrEq("pqr"), 3)).WillOnce(Return(3));
+
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+  EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3));
+  EXPECT_TRUE(sequencer_->OnFrame(9, "jkl", 3));
+  EXPECT_FALSE(sequencer_->OnFrame(12, "mno", 3));
+  EXPECT_TRUE(sequencer_->OnFrame(6, "ghi", 3));
+
+  // Read 3 bytes.
+  ASSERT_EQ(3u, sequencer_->GetReadableRegions(iov, 5));
+  ASSERT_EQ(3u, iov[0].iov_len);
+  ASSERT_EQ(3u, iov[1].iov_len);
+  ASSERT_EQ(3u, iov[2].iov_len);
+  ASSERT_EQ(0, memcmp(iov[0].iov_base, "def", 3));
+  ASSERT_EQ(0, memcmp(iov[1].iov_base, "ghi", 3));
+  ASSERT_EQ(0, memcmp(iov[2].iov_base, "jkl", 3));
+  sequencer_->AdvanceReadablePtr(3);
+
+  // Now we have space to bufer this.
+  EXPECT_TRUE(sequencer_->OnFrame(12, "mno", 3));
+
+  // Read the remaining 9 bytes.
+  ASSERT_EQ(3u, sequencer_->GetReadableRegions(iov, 5));
+  ASSERT_EQ(3u, iov[0].iov_len);
+  ASSERT_EQ(3u, iov[1].iov_len);
+  ASSERT_EQ(3u, iov[2].iov_len);
+  ASSERT_EQ(0, memcmp(iov[0].iov_base, "ghi", 3));
+  ASSERT_EQ(0, memcmp(iov[1].iov_base, "jkl", 3));
+  ASSERT_EQ(0, memcmp(iov[2].iov_base, "mno", 3));
+  sequencer_->AdvanceReadablePtr(9);
+
+  EXPECT_TRUE(sequencer_->OnFrame(15, "pqr", 3));
+}
+
+TEST_F(QuicStreamSequencerTest, BasicCloseOrdered) {
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+
+  EXPECT_CALL(stream_, TerminateFromPeer(false));
+  sequencer_->CloseStreamAtOffset(3, false);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+}
+
+TEST_F(QuicStreamSequencerTest, BasicHalfOrdered) {
+  InSequence s;
+
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+
+  EXPECT_CALL(stream_, TerminateFromPeer(true));
+  sequencer_->CloseStreamAtOffset(3, true);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+}
+
+TEST_F(QuicStreamSequencerTest, BasicCloseUnordered) {
+  sequencer_->CloseStreamAtOffset(3, false);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, TerminateFromPeer(false));
+
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+}
+
+TEST_F(QuicStreamSequencerTest, BasicHalfUnorderedWithFlush) {
+  sequencer_->CloseStreamAtOffset(6, true);
+  EXPECT_EQ(6u, sequencer_->close_offset());
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, TerminateFromPeer(true));
+
+  EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3));
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+}
+
+TEST_F(QuicStreamSequencerTest, BasicCloseUnorderedWithFlush) {
+  sequencer_->CloseStreamAtOffset(6, false);
+  EXPECT_EQ(6u, sequencer_->close_offset());
+
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, TerminateFromPeer(false));
+
+  EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3));
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+}
+
+TEST_F(QuicStreamSequencerTest, BasicHalfUnordered) {
+  sequencer_->CloseStreamAtOffset(3, true);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, TerminateFromPeer(true));
+
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+}
+
+TEST_F(QuicStreamSequencerTest, CloseStreamBeforeCloseEqual) {
+  sequencer_->CloseStreamAtOffset(3, true);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  sequencer_->CloseStreamAtOffset(3, false);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, TerminateFromPeer(false));
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+}
+
+TEST_F(QuicStreamSequencerTest, CloseBeforeTermianteEqual) {
+  sequencer_->CloseStreamAtOffset(3, false);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  sequencer_->CloseStreamAtOffset(3, true);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  InSequence s;
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
+  EXPECT_CALL(stream_, TerminateFromPeer(false));
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+}
+
+TEST_F(QuicStreamSequencerTest, TerminateWithReadv) {
+  char buffer[3];
+  iovec iov = { &buffer[0], 3 };

[jar (doing other things), 2012/11/01 22:21:10]

nit: move closer to first use. (next test as well)

[Ryan Hamilton, 2012/11/01 22:52:20]

Fixed upstream.

+
+  sequencer_->CloseStreamAtOffset(3, true);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  EXPECT_FALSE(sequencer_->IsHalfClosed());
+
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(0));
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+
+  int bytes_read = sequencer_->Readv(&iov, 1);
+  EXPECT_EQ(3, bytes_read);
+  EXPECT_TRUE(sequencer_->IsHalfClosed());
+  EXPECT_FALSE(sequencer_->IsClosed());
+}
+
+TEST_F(QuicStreamSequencerTest, CloseWithReadv) {
+  char buffer[3];
+  iovec iov = { &buffer[0], 3 };
+
+  sequencer_->CloseStreamAtOffset(3, false);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  EXPECT_FALSE(sequencer_->IsClosed());
+
+  EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(0));
+  EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3));
+
+  int bytes_read = sequencer_->Readv(&iov, 1);
+  EXPECT_EQ(3, bytes_read);
+  EXPECT_TRUE(sequencer_->IsHalfClosed());
+  EXPECT_TRUE(sequencer_->IsClosed());
+}
+
+TEST_F(QuicStreamSequencerTest, MutipleOffsets) {
+  sequencer_->CloseStreamAtOffset(3, false);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  EXPECT_CALL(stream_, Close(QUIC_MULTIPLE_TERMINATION_OFFSETS));
+  sequencer_->CloseStreamAtOffset(5, false);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  EXPECT_CALL(stream_, Close(QUIC_MULTIPLE_TERMINATION_OFFSETS));
+  sequencer_->CloseStreamAtOffset(1, false);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+
+  sequencer_->CloseStreamAtOffset(3, false);
+  EXPECT_EQ(3u, sequencer_->close_offset());
+}
+
+class QuicSequencerRandomTest : public QuicStreamSequencerTest {
+ public:
+  typedef pair<int, string> Frame;
+  typedef vector<Frame> FrameList;
+
+  void CreateFrames() {
+    int payload_size = arraysize(kPayload) - 1;
+    int remaining_payload = payload_size;
+    while (remaining_payload != 0) {
+      int size = min(OneToN(6), remaining_payload);
+      int idx = payload_size - remaining_payload;

[jar (doing other things), 2012/11/01 22:21:10]

nit: (assuming you went with the longer spelling in source code) idx-->index  
(throughout this file)

[Ryan Hamilton, 2012/11/01 22:52:20]

Fixed upstream.

+      list_.push_back(make_pair(idx, string(kPayload + idx, size)));
+      remaining_payload -= size;
+    }
+  }
+
+  QuicSequencerRandomTest() {
+    //int32 seed = ACMRandom::HostnamePidTimeSeed();
+    //LOG(INFO) << "**** The current seed is " << seed << " ****";
+    //random_.reset(new ACMRandom(seed));
+
+    CreateFrames();
+  }
+
+  int OneToN(int n) {
+    return base::RandInt(1, n);
+  }
+
+  int MaybeProcessMaybeBuffer(const char* data, uint32 len) {
+    int to_process = len;
+    if (base::RandUint64() % 2 != 0) {
+      to_process = base::RandInt(0, len);
+    }
+    output_.append(data, to_process);
+    LOG(ERROR) << output_;
+    return to_process;
+  }
+
+  string output_;
+  //scoped_ptr<ACMRandom> random_;
+  FrameList list_;
+};
+
+// All frames are processed as soon as we have sequential data.
+// Infinite buffering, so all frames are acked right away.
+TEST_F(QuicSequencerRandomTest, RandomFramesNoDroppingNoBackup) {
+  InSequence s;
+  for (size_t i = 0; i < list_.size(); ++i) {
+    string* data = &list_[i].second;
+    EXPECT_CALL(stream_, ProcessData(StrEq(*data), data->size()))
+        .WillOnce(Return(data->size()));
+  }
+
+  while (list_.size() != 0) {
+    int idx = OneToN(list_.size()) - 1;
+    LOG(ERROR) << "Sending index " << idx << " " << list_[idx].second.c_str();
+    EXPECT_TRUE(sequencer_->OnFrame(
+        list_[idx].first, list_[idx].second.c_str(),

[jar (doing other things), 2012/11/01 22:21:10]

nit: probably avoid c_str() (in favor of data()) unless really needed, to avoid
accidental mutation of string buffer.

[Ryan Hamilton, 2012/11/01 22:52:20]

Fixed upstream.

+        list_[idx].second.size()));
+    list_.erase(list_.begin() + idx);
+  }
+}
+
+// All frames are processed as soon as we have sequential data.
+// Buffering, so some frames are rejected.
+TEST_F(QuicSequencerRandomTest, RandomFramesDroppingNoBackup) {
+  sequencer_->SetMemoryLimit(26);
+
+  InSequence s;
+  for (size_t i = 0; i < list_.size(); ++i) {
+    string* data = &list_[i].second;
+    EXPECT_CALL(stream_, ProcessData(StrEq(*data), data->size()))
+        .WillOnce(Return(data->size()));
+  }
+
+  while (list_.size() != 0) {
+    int idx = OneToN(list_.size()) - 1;
+    LOG(ERROR) << "Sending index " << idx << " " << list_[idx].second.c_str();
+    bool acked = sequencer_->OnFrame(
+        list_[idx].first, list_[idx].second.c_str(),
+        list_[idx].second.size());
+    if (acked) {
+      list_.erase(list_.begin() + idx);
+    }
+  }
+}
+
+TEST_F(QuicSequencerRandomTest, RandomFramesNoDroppingBackup) {
+  char buffer[10];
+  iovec iov[2];
+  iov[0].iov_base = &buffer[0];
+  iov[0].iov_len = 5;
+  iov[1].iov_base = &buffer[5];
+  iov[1].iov_len = 5;
+
+  EXPECT_CALL(stream_, ProcessData(_, _))
+      .Times(AnyNumber())
+      .WillRepeatedly(Invoke(
+          this, &QuicSequencerRandomTest::MaybeProcessMaybeBuffer));
+
+  while (output_.size() != arraysize(kPayload) - 1) {
+    if (list_.size() != 0 && base::RandUint64() % 2 != 0) {  // Send data
+      int idx = OneToN(list_.size()) - 1;
+      ASSERT_TRUE(sequencer_->OnFrame(
+          list_[idx].first, list_[idx].second.c_str(),
+          list_[idx].second.size()));
+      list_.erase(list_.begin() + idx);
+    } else {  // Read data
+      int bytes_read = sequencer_->Readv(iov, 1);
+      output_.append(buffer, bytes_read);
+    }
+  }
+  EXPECT_EQ(0, strcmp(kPayload, output_.c_str()));
+}
+
+TEST_F(QuicSequencerRandomTest, RandomFramesNoDroppingBackupLocalBuffers) {
+  EXPECT_CALL(stream_, ProcessData(_, _))
+      .Times(AnyNumber())
+      .WillRepeatedly(Invoke(
+          this, &QuicSequencerRandomTest::MaybeProcessMaybeBuffer));
+
+  while (output_.size() != arraysize(kPayload) - 1) {
+    if (list_.size() != 0 && base::RandUint64() % 2 == 0) {  // Send data
+      int idx = OneToN(list_.size()) - 1;
+      ASSERT_TRUE(sequencer_->OnFrame(
+          list_[idx].first, list_[idx].second.c_str(),
+          list_[idx].second.size()));
+      list_.erase(list_.begin() + idx);
+    } else {  // Read data
+      bool has_bytes = sequencer_->HasBytesToRead();
+      iovec iov[2];
+      int iovs = sequencer_->GetReadableRegions(iov, 2);
+      int initial_size = output_.size();
+      if (has_bytes) {
+        ASSERT_LT(0, iovs);
+      } else {
+        ASSERT_EQ(0, iovs);
+      }
+      for (int i = 0; i < iovs; ++i) {
+        output_.append(static_cast<char*>(iov[i].iov_base), iov[i].iov_len);
+      }
+      sequencer_->AdvanceReadablePtr(output_.size() - initial_size);
+    }
+  }
+  EXPECT_EQ(0, strcmp(kPayload, output_.c_str()));
+}
+
+TEST_F(QuicSequencerRandomTest, RandomFramesDroppingBackup) {
+  sequencer_->SetMemoryLimit(26);
+
+  EXPECT_CALL(stream_, ProcessData(_, _))
+      .Times(AnyNumber())
+      .WillRepeatedly(Invoke(
+          this, &QuicSequencerRandomTest::MaybeProcessMaybeBuffer));
+
+  while (output_.size() != arraysize(kPayload) - 1) {
+    if (list_.size() != 0 && base::RandUint64() % 2 == 0) {  // Send data
+      int idx = OneToN(list_.size()) - 1;
+      if (sequencer_->OnFrame(list_[idx].first, list_[idx].second.c_str(),
+                                list_[idx].second.size())) {
+        list_.erase(list_.begin() + idx);
+      }
+    } else {  // Read data
+      iovec iov[2];
+      int iovs = sequencer_->GetReadableRegions(iov, 2);
+      int initial_size = output_.size();
+      for (int i = 0; i < iovs; ++i) {
+        output_.append(static_cast<char*>(iov[i].iov_base), iov[i].iov_len);
+      }
+      sequencer_->AdvanceReadablePtr(output_.size() - initial_size);
+    }
+  }
+  EXPECT_EQ(0, strcmp(kPayload, output_.c_str()));
+}
+
+}  // namespace
+
+}  // namespace net