src/net/quic/quic_stream_sequencer_test.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/quic/quic_stream_sequencer.h"
   6
   7 #include <utility>
   8 #include <vector>
   9
  10 #include "base/rand_util.h"
  11 #include "net/base/ip_endpoint.h"
  12 #include "net/quic/reliable_quic_stream.h"
  13 #include "net/quic/test_tools/quic_test_utils.h"
  14 #include "testing/gmock/include/gmock/gmock.h"
  15 #include "testing/gtest/include/gtest/gtest.h"
  16
  17 using base::StringPiece;
  18 using std::min;
  19 using std::pair;
  20 using std::vector;
  21 using testing::_;
  22 using testing::AnyNumber;
  23 using testing::InSequence;
  24 using testing::Return;
  25 using testing::StrEq;
  26
  27 namespace net {
  28 namespace test {
  29
  30 class QuicStreamSequencerPeer : public QuicStreamSequencer {
  31  public:
  32   explicit QuicStreamSequencerPeer(ReliableQuicStream* stream)
  33       : QuicStreamSequencer(stream) {
  34   }
  35
  36   QuicStreamSequencerPeer(int32 max_mem, ReliableQuicStream* stream)
  37       : QuicStreamSequencer(max_mem, stream) {
  38   }
  39
  40   virtual bool OnFinFrame(QuicStreamOffset byte_offset,
  41                           const char* data) {
  42     QuicStreamFrame frame;
  43     frame.stream_id = 1;
  44     frame.offset = byte_offset;
  45     frame.data = StringPiece(data);
  46     frame.fin = true;
  47     return OnStreamFrame(frame);
  48   }
  49
  50   virtual bool OnFrame(QuicStreamOffset byte_offset,
  51                        const char* data) {
  52     QuicStreamFrame frame;
  53     frame.stream_id = 1;
  54     frame.offset = byte_offset;
  55     frame.data = StringPiece(data);
  56     frame.fin = false;
  57     return OnStreamFrame(frame);
  58   }
  59
  60   void SetMemoryLimit(size_t limit) {
  61     max_frame_memory_ = limit;
  62   }
  63   uint64 num_bytes_consumed() const { return num_bytes_consumed_; }
  64   const FrameMap* frames() const { return &frames_; }
  65   QuicStreamOffset close_offset() const { return close_offset_; }
  66 };
  67
  68 class MockStream : public ReliableQuicStream {
  69  public:
  70   MockStream(QuicSession* session, QuicStreamId id)
  71       : ReliableQuicStream(id, session) {
  72   }
  73
  74   MOCK_METHOD1(TerminateFromPeer, void(bool half_close));
  75   MOCK_METHOD2(ProcessData, uint32(const char* data, uint32 data_len));
  76   MOCK_METHOD2(CloseConnectionWithDetails, void(QuicErrorCode error,
  77                                                 const string& details));
  78   MOCK_METHOD1(Close, void(QuicRstStreamErrorCode error));
  79   MOCK_METHOD0(OnCanWrite, void());
  80 };
  81
  82 namespace {
  83
  84 static const char kPayload[] =
  85     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  86
  87 class QuicStreamSequencerTest : public ::testing::Test {
  88  protected:
  89   QuicStreamSequencerTest()
  90       : connection_(new MockConnection(1, IPEndPoint(), false)),
  91         session_(connection_, true),
  92         stream_(&session_, 1),
  93         sequencer_(new QuicStreamSequencerPeer(&stream_)) {
  94   }
  95
  96   bool VerifyReadableRegions(const char** expected, size_t num_expected) {
  97     iovec iovecs[5];
  98     size_t num_iovecs = sequencer_->GetReadableRegions(iovecs,
  99                                                        arraysize(iovecs));
 100     return VerifyIovecs(iovecs, num_iovecs, expected, num_expected);
 101   }
 102
 103   bool VerifyIovecs(iovec* iovecs,
 104                     size_t num_iovecs,
 105                     const char** expected,
 106                     size_t num_expected) {
 107     if (num_expected != num_iovecs) {
 108       LOG(ERROR) << "Incorrect number of iovecs.  Expected: "
 109                  << num_expected << " Actual: " << num_iovecs;
 110       return false;
 111     }
 112     for (size_t i = 0; i < num_expected; ++i) {
 113       if (!VerifyIovec(iovecs[i], expected[i])) {
 114         return false;
 115       }
 116     }
 117     return true;
 118   }
 119
 120   bool VerifyIovec(const iovec& iovec, StringPiece expected) {
 121     if (iovec.iov_len != expected.length()) {
 122       LOG(ERROR) << "Invalid length: " << iovec.iov_len
 123                  << " vs " << expected.length();
 124       return false;
 125     }
 126     if (memcmp(iovec.iov_base, expected.data(), expected.length()) != 0) {
 127       LOG(ERROR) << "Invalid data: " << static_cast<char*>(iovec.iov_base)
 128                  << " vs " << expected.data();
 129       return false;
 130     }
 131     return true;
 132   }
 133
 134   MockConnection* connection_;
 135   MockSession session_;
 136   testing::StrictMock<MockStream> stream_;
 137   scoped_ptr<QuicStreamSequencerPeer> sequencer_;
 138 };
 139
 140 TEST_F(QuicStreamSequencerTest, RejectOldFrame) {
 141   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3))
 142       .WillOnce(Return(3));
 143
 144   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 145   EXPECT_EQ(0u, sequencer_->frames()->size());
 146   EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
 147   // Ignore this - it matches a past sequence number and we should not see it
 148   // again.
 149   EXPECT_TRUE(sequencer_->OnFrame(0, "def"));
 150   EXPECT_EQ(0u, sequencer_->frames()->size());
 151 }
 152
 153 TEST_F(QuicStreamSequencerTest, RejectOverlyLargeFrame) {
 154   // TODO(rch): enable when chromium supports EXPECT_DFATAL.
 155   /*
 156   EXPECT_DFATAL(sequencer_.reset(new QuicStreamSequencerPeer(2, &stream_)),
 157                 "Setting max frame memory to 2.  "
 158                 "Some frames will be impossible to handle.");
 159
 160   EXPECT_DEBUG_DEATH(sequencer_->OnFrame(0, "abc"), "");
 161   */
 162 }
 163
 164 TEST_F(QuicStreamSequencerTest, DropFramePastBuffering) {
 165   sequencer_->SetMemoryLimit(3);
 166
 167   EXPECT_FALSE(sequencer_->OnFrame(3, "abc"));
 168 }
 169
 170 TEST_F(QuicStreamSequencerTest, RejectBufferedFrame) {
 171   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3));
 172
 173   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 174   EXPECT_EQ(1u, sequencer_->frames()->size());
 175   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 176   // Ignore this - it matches a buffered frame.
 177   // Right now there's no checking that the payload is consistent.
 178   EXPECT_TRUE(sequencer_->OnFrame(0, "def"));
 179   EXPECT_EQ(1u, sequencer_->frames()->size());
 180 }
 181
 182 TEST_F(QuicStreamSequencerTest, FullFrameConsumed) {
 183   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
 184
 185   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 186   EXPECT_EQ(0u, sequencer_->frames()->size());
 187   EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
 188 }
 189
 190 TEST_F(QuicStreamSequencerTest, EmptyFrame) {
 191   EXPECT_CALL(stream_,
 192               CloseConnectionWithDetails(QUIC_INVALID_STREAM_FRAME, _));
 193   EXPECT_FALSE(sequencer_->OnFrame(0, ""));
 194   EXPECT_EQ(0u, sequencer_->frames()->size());
 195   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 196 }
 197
 198 TEST_F(QuicStreamSequencerTest, EmptyFinFrame) {
 199   EXPECT_CALL(stream_, TerminateFromPeer(true));
 200   EXPECT_TRUE(sequencer_->OnFinFrame(0, ""));
 201   EXPECT_EQ(0u, sequencer_->frames()->size());
 202   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 203 }
 204
 205 TEST_F(QuicStreamSequencerTest, PartialFrameConsumed) {
 206   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(2));
 207
 208   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 209   EXPECT_EQ(1u, sequencer_->frames()->size());
 210   EXPECT_EQ(2u, sequencer_->num_bytes_consumed());
 211   EXPECT_EQ("c", sequencer_->frames()->find(2)->second);
 212 }
 213
 214 TEST_F(QuicStreamSequencerTest, NextxFrameNotConsumed) {
 215   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(0));
 216
 217   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 218   EXPECT_EQ(1u, sequencer_->frames()->size());
 219   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 220   EXPECT_EQ("abc", sequencer_->frames()->find(0)->second);
 221 }
 222
 223 TEST_F(QuicStreamSequencerTest, FutureFrameNotProcessed) {
 224   EXPECT_TRUE(sequencer_->OnFrame(3, "abc"));
 225   EXPECT_EQ(1u, sequencer_->frames()->size());
 226   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 227   EXPECT_EQ("abc", sequencer_->frames()->find(3)->second);
 228 }
 229
 230 TEST_F(QuicStreamSequencerTest, OutOfOrderFrameProcessed) {
 231   // Buffer the first
 232   EXPECT_TRUE(sequencer_->OnFrame(6, "ghi"));
 233   EXPECT_EQ(1u, sequencer_->frames()->size());
 234   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 235   // Buffer the second
 236   EXPECT_TRUE(sequencer_->OnFrame(3, "def"));
 237   EXPECT_EQ(2u, sequencer_->frames()->size());
 238   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 239
 240   InSequence s;
 241   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
 242   EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3));
 243   EXPECT_CALL(stream_, ProcessData(StrEq("ghi"), 3)).WillOnce(Return(3));
 244
 245   // Ack right away
 246   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 247   EXPECT_EQ(9u, sequencer_->num_bytes_consumed());
 248
 249   EXPECT_EQ(0u, sequencer_->frames()->size());
 250 }
 251
 252 TEST_F(QuicStreamSequencerTest, OutOfOrderFramesProcessedWithBuffering) {
 253   sequencer_->SetMemoryLimit(9);
 254
 255   // Too far to buffer.
 256   EXPECT_FALSE(sequencer_->OnFrame(9, "jkl"));
 257
 258   // We can afford to buffer this.
 259   EXPECT_TRUE(sequencer_->OnFrame(6, "ghi"));
 260   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 261
 262   InSequence s;
 263   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
 264
 265   // Ack right away
 266   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 267   EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
 268
 269   // We should be willing to buffer this now.
 270   EXPECT_TRUE(sequencer_->OnFrame(9, "jkl"));
 271   EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
 272
 273   EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3));
 274   EXPECT_CALL(stream_, ProcessData(StrEq("ghi"), 3)).WillOnce(Return(3));
 275   EXPECT_CALL(stream_, ProcessData(StrEq("jkl"), 3)).WillOnce(Return(3));
 276
 277   EXPECT_TRUE(sequencer_->OnFrame(3, "def"));
 278   EXPECT_EQ(12u, sequencer_->num_bytes_consumed());
 279   EXPECT_EQ(0u, sequencer_->frames()->size());
 280 }
 281
 282 TEST_F(QuicStreamSequencerTest, OutOfOrderFramesBlockignWithReadv) {
 283   sequencer_->SetMemoryLimit(9);
 284   char buffer[20];
 285   iovec iov[2];
 286   iov[0].iov_base = &buffer[0];
 287   iov[0].iov_len = 1;
 288   iov[1].iov_base = &buffer[1];
 289   iov[1].iov_len = 2;
 290
 291   // Push abc - process.
 292   // Push jkl - buffer (not next data)
 293   // Push def - don't process.
 294   // Push mno - drop (too far out)
 295   // Push ghi - buffer (def not processed)
 296   // Read 2.
 297   // Push mno - buffer (not all read)
 298   // Read all
 299   // Push pqr - process
 300
 301   InSequence s;
 302   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
 303   EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(0));
 304   EXPECT_CALL(stream_, ProcessData(StrEq("pqr"), 3)).WillOnce(Return(3));
 305
 306   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 307   EXPECT_TRUE(sequencer_->OnFrame(3, "def"));
 308   EXPECT_TRUE(sequencer_->OnFrame(9, "jkl"));
 309   EXPECT_FALSE(sequencer_->OnFrame(12, "mno"));
 310   EXPECT_TRUE(sequencer_->OnFrame(6, "ghi"));
 311
 312   // Read 3 bytes.
 313   EXPECT_EQ(3, sequencer_->Readv(iov, 2));
 314   EXPECT_EQ(0, strncmp(buffer, "def", 3));
 315
 316   // Now we have space to bufer this.
 317   EXPECT_TRUE(sequencer_->OnFrame(12, "mno"));
 318
 319   // Read the remaining 9 bytes.
 320   iov[1].iov_len = 19;
 321   EXPECT_EQ(9, sequencer_->Readv(iov, 2));
 322   EXPECT_EQ(0, strncmp(buffer, "ghijklmno", 9));
 323
 324   EXPECT_TRUE(sequencer_->OnFrame(15, "pqr"));
 325 }
 326
 327 // Same as above, just using a different method for reading.
 328 TEST_F(QuicStreamSequencerTest, OutOfOrderFramesBlockignWithGetReadableRegion) {
 329   sequencer_->SetMemoryLimit(9);
 330
 331   InSequence s;
 332   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
 333   EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(0));
 334   EXPECT_CALL(stream_, ProcessData(StrEq("pqr"), 3)).WillOnce(Return(3));
 335
 336   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 337   EXPECT_TRUE(sequencer_->OnFrame(3, "def"));
 338   EXPECT_TRUE(sequencer_->OnFrame(9, "jkl"));
 339   EXPECT_FALSE(sequencer_->OnFrame(12, "mno"));
 340   EXPECT_TRUE(sequencer_->OnFrame(6, "ghi"));
 341
 342   // Read 3 bytes.
 343   const char* expected[] = {"def", "ghi", "jkl"};
 344   ASSERT_TRUE(VerifyReadableRegions(expected, arraysize(expected)));
 345   char buffer[9];
 346   iovec read_iov = { &buffer[0], 3 };
 347   ASSERT_EQ(3, sequencer_->Readv(&read_iov, 1));
 348
 349   // Now we have space to bufer this.
 350   EXPECT_TRUE(sequencer_->OnFrame(12, "mno"));
 351
 352   // Read the remaining 9 bytes.
 353   const char* expected2[] = {"ghi", "jkl", "mno"};
 354   ASSERT_TRUE(VerifyReadableRegions(expected2, arraysize(expected2)));
 355   read_iov.iov_len = 9;
 356   ASSERT_EQ(9, sequencer_->Readv(&read_iov, 1));
 357
 358   EXPECT_TRUE(sequencer_->OnFrame(15, "pqr"));
 359 }
 360
 361 // Same as above, just using a different method for reading.
 362 TEST_F(QuicStreamSequencerTest, MarkConsumed) {
 363   sequencer_->SetMemoryLimit(9);
 364
 365   InSequence s;
 366   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(0));
 367
 368   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 369   EXPECT_TRUE(sequencer_->OnFrame(3, "def"));
 370   EXPECT_TRUE(sequencer_->OnFrame(6, "ghi"));
 371
 372   // Peek into the data.
 373   const char* expected[] = {"abc", "def", "ghi"};
 374   ASSERT_TRUE(VerifyReadableRegions(expected, arraysize(expected)));
 375
 376   // Consume 1 byte.
 377   sequencer_->MarkConsumed(1);
 378   // Verify data.
 379   const char* expected2[] = {"bc", "def", "ghi"};
 380   ASSERT_TRUE(VerifyReadableRegions(expected2, arraysize(expected2)));
 381
 382   // Consume 2 bytes.
 383   sequencer_->MarkConsumed(2);
 384   // Verify data.
 385   const char* expected3[] = {"def", "ghi"};
 386   ASSERT_TRUE(VerifyReadableRegions(expected3, arraysize(expected3)));
 387
 388   // Consume 5 bytes.
 389   sequencer_->MarkConsumed(5);
 390   // Verify data.
 391   const char* expected4[] = {"i"};
 392   ASSERT_TRUE(VerifyReadableRegions(expected4, arraysize(expected4)));
 393 }
 394
 395 TEST_F(QuicStreamSequencerTest, MarkConsumedError) {
 396   // TODO(rch): enable when chromium supports EXPECT_DFATAL.
 397   /*
 398   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(0));
 399
 400   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 401   EXPECT_TRUE(sequencer_->OnFrame(9, "jklmnopqrstuvwxyz"));
 402
 403   // Peek into the data.  Only the first chunk should be readable
 404   // because of the missing data.
 405   const char* expected[] = {"abc"};
 406   ASSERT_TRUE(VerifyReadableRegions(expected, arraysize(expected)));
 407
 408   // Now, attempt to mark consumed more data than was readable
 409   // and expect the stream to be closed.
 410   EXPECT_CALL(stream_, Close(QUIC_ERROR_PROCESSING_STREAM));
 411   EXPECT_DFATAL(sequencer_->MarkConsumed(4),
 412                 "Invalid argument to MarkConsumed.  num_bytes_consumed_: 3 "
 413                 "end_offset: 4 offset: 9 length: 17");
 414   */
 415 }
 416
 417 TEST_F(QuicStreamSequencerTest, MarkConsumedWithMissingPacket) {
 418   InSequence s;
 419   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(0));
 420
 421   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 422   EXPECT_TRUE(sequencer_->OnFrame(3, "def"));
 423   // Missing packet: 6, ghi
 424   EXPECT_TRUE(sequencer_->OnFrame(9, "jkl"));
 425
 426   const char* expected[] = {"abc", "def"};
 427   ASSERT_TRUE(VerifyReadableRegions(expected, arraysize(expected)));
 428
 429   sequencer_->MarkConsumed(6);
 430 }
 431
 432 TEST_F(QuicStreamSequencerTest, BasicHalfCloseOrdered) {
 433   InSequence s;
 434
 435   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
 436   EXPECT_CALL(stream_, TerminateFromPeer(true));
 437   EXPECT_TRUE(sequencer_->OnFinFrame(0, "abc"));
 438
 439   EXPECT_EQ(3u, sequencer_->close_offset());
 440 }
 441
 442 TEST_F(QuicStreamSequencerTest, BasicHalfCloseUnorderedWithFlush) {
 443   sequencer_->OnFinFrame(6, "");
 444   EXPECT_EQ(6u, sequencer_->close_offset());
 445   InSequence s;
 446   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
 447   EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3));
 448   EXPECT_CALL(stream_, TerminateFromPeer(true));
 449
 450   EXPECT_TRUE(sequencer_->OnFrame(3, "def"));
 451   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 452 }
 453
 454 TEST_F(QuicStreamSequencerTest, BasicHalfUnordered) {
 455   sequencer_->OnFinFrame(3, "");
 456   EXPECT_EQ(3u, sequencer_->close_offset());
 457   InSequence s;
 458   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3));
 459   EXPECT_CALL(stream_, TerminateFromPeer(true));
 460
 461   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 462 }
 463
 464 TEST_F(QuicStreamSequencerTest, TerminateWithReadv) {
 465   char buffer[3];
 466
 467   sequencer_->OnFinFrame(3, "");
 468   EXPECT_EQ(3u, sequencer_->close_offset());
 469
 470   EXPECT_FALSE(sequencer_->IsHalfClosed());
 471
 472   EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(0));
 473   EXPECT_TRUE(sequencer_->OnFrame(0, "abc"));
 474
 475   iovec iov = { &buffer[0], 3 };
 476   int bytes_read = sequencer_->Readv(&iov, 1);
 477   EXPECT_EQ(3, bytes_read);
 478   EXPECT_TRUE(sequencer_->IsHalfClosed());
 479 }
 480
 481 TEST_F(QuicStreamSequencerTest, MutipleOffsets) {
 482   sequencer_->OnFinFrame(3, "");
 483   EXPECT_EQ(3u, sequencer_->close_offset());
 484
 485   EXPECT_CALL(stream_, Close(QUIC_MULTIPLE_TERMINATION_OFFSETS));
 486   sequencer_->OnFinFrame(5, "");
 487   EXPECT_EQ(3u, sequencer_->close_offset());
 488
 489   EXPECT_CALL(stream_, Close(QUIC_MULTIPLE_TERMINATION_OFFSETS));
 490   sequencer_->OnFinFrame(1, "");
 491   EXPECT_EQ(3u, sequencer_->close_offset());
 492
 493   sequencer_->OnFinFrame(3, "");
 494   EXPECT_EQ(3u, sequencer_->close_offset());
 495 }
 496
 497 class QuicSequencerRandomTest : public QuicStreamSequencerTest {
 498  public:
 499   typedef pair<int, string> Frame;
 500   typedef vector<Frame> FrameList;
 501
 502   void CreateFrames() {
 503     int payload_size = arraysize(kPayload) - 1;
 504     int remaining_payload = payload_size;
 505     while (remaining_payload != 0) {
 506       int size = min(OneToN(6), remaining_payload);
 507       int index = payload_size - remaining_payload;
 508       list_.push_back(make_pair(index, string(kPayload + index, size)));
 509       remaining_payload -= size;
 510     }
 511   }
 512
 513   QuicSequencerRandomTest() {
 514     CreateFrames();
 515   }
 516
 517   int OneToN(int n) {
 518     return base::RandInt(1, n);
 519   }
 520
 521   int MaybeProcessMaybeBuffer(const char* data, uint32 len) {
 522     int to_process = len;
 523     if (base::RandUint64() % 2 != 0) {
 524       to_process = base::RandInt(0, len);
 525     }
 526     output_.append(data, to_process);
 527     return to_process;
 528   }
 529
 530   string output_;
 531   FrameList list_;
 532 };
 533
 534 // All frames are processed as soon as we have sequential data.
 535 // Infinite buffering, so all frames are acked right away.
 536 TEST_F(QuicSequencerRandomTest, RandomFramesNoDroppingNoBackup) {
 537   InSequence s;
 538   for (size_t i = 0; i < list_.size(); ++i) {
 539     string* data = &list_[i].second;
 540     EXPECT_CALL(stream_, ProcessData(StrEq(*data), data->size()))
 541         .WillOnce(Return(data->size()));
 542   }
 543
 544   while (list_.size() != 0) {
 545     int index = OneToN(list_.size()) - 1;
 546     LOG(ERROR) << "Sending index " << index << " "
 547                << list_[index].second.data();
 548     EXPECT_TRUE(sequencer_->OnFrame(list_[index].first,
 549                                     list_[index].second.data()));
 550
 551     list_.erase(list_.begin() + index);
 552   }
 553 }
 554
 555 // All frames are processed as soon as we have sequential data.
 556 // Buffering, so some frames are rejected.
 557 TEST_F(QuicSequencerRandomTest, RandomFramesDroppingNoBackup) {
 558   sequencer_->SetMemoryLimit(26);
 559
 560   InSequence s;
 561   for (size_t i = 0; i < list_.size(); ++i) {
 562     string* data = &list_[i].second;
 563     EXPECT_CALL(stream_, ProcessData(StrEq(*data), data->size()))
 564         .WillOnce(Return(data->size()));
 565   }
 566
 567   while (list_.size() != 0) {
 568     int index = OneToN(list_.size()) - 1;
 569     LOG(ERROR) << "Sending index " << index << " "
 570                << list_[index].second.data();
 571     bool acked = sequencer_->OnFrame(list_[index].first,
 572                                      list_[index].second.data());
 573
 574     if (acked) {
 575       list_.erase(list_.begin() + index);
 576     }
 577   }
 578 }
 579
 580 }  // namespace
 581 }  // namespace test
 582 }  // namespace net