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/logging.h"
  11 #include "base/rand_util.h"
  12 #include "net/base/ip_endpoint.h"
  13 #include "net/quic/quic_utils.h"
  14 #include "net/quic/reliable_quic_stream.h"
  15 #include "net/quic/test_tools/quic_stream_sequencer_peer.h"
  16 #include "net/quic/test_tools/quic_test_utils.h"
  17 #include "net/test/gtest_util.h"
  18 #include "testing/gmock/include/gmock/gmock.h"
  19 #include "testing/gtest/include/gtest/gtest.h"
  20
  21 using base::StringPiece;
  22 using std::map;
  23 using std::min;
  24 using std::pair;
  25 using std::string;
  26 using std::vector;
  27 using testing::_;
  28 using testing::AnyNumber;
  29 using testing::InSequence;
  30 using testing::Return;
  31 using testing::StrEq;
  32
  33 namespace net {
  34 namespace test {
  35
  36 class MockStream : public ReliableQuicStream {
  37  public:
  38   MockStream(QuicSession* session, QuicStreamId id)
  39       : ReliableQuicStream(id, session) {
  40   }
  41
  42   MOCK_METHOD0(OnFinRead, void());
  43   MOCK_METHOD2(ProcessRawData, uint32(const char* data, uint32 data_len));
  44   MOCK_METHOD2(CloseConnectionWithDetails, void(QuicErrorCode error,
  45                                                 const string& details));
  46   MOCK_METHOD1(Reset, void(QuicRstStreamErrorCode error));
  47   MOCK_METHOD0(OnCanWrite, void());
  48   QuicPriority EffectivePriority() const override {
  49     return QuicUtils::HighestPriority();
  50   }
  51   virtual bool IsFlowControlEnabled() const {
  52     return true;
  53   }
  54 };
  55
  56 namespace {
  57
  58 static const char kPayload[] =
  59     "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  60
  61 class QuicStreamSequencerTest : public ::testing::Test {
  62  protected:
  63   QuicStreamSequencerTest()
  64       : connection_(new MockConnection(false)),
  65         session_(connection_),
  66         stream_(&session_, 1),
  67         sequencer_(new QuicStreamSequencer(&stream_)),
  68         buffered_frames_(
  69             QuicStreamSequencerPeer::GetBufferedFrames(sequencer_.get())) {
  70   }
  71
  72   bool VerifyIovecs(iovec* iovecs,
  73                     size_t num_iovecs,
  74                     const char** expected,
  75                     size_t num_expected) {
  76     if (num_expected != num_iovecs) {
  77       LOG(ERROR) << "Incorrect number of iovecs.  Expected: "
  78                  << num_expected << " Actual: " << num_iovecs;
  79       return false;
  80     }
  81     for (size_t i = 0; i < num_expected; ++i) {
  82       if (!VerifyIovec(iovecs[i], expected[i])) {
  83         return false;
  84       }
  85     }
  86     return true;
  87   }
  88
  89   bool VerifyIovec(const iovec& iovec, StringPiece expected) {
  90     if (iovec.iov_len != expected.length()) {
  91       LOG(ERROR) << "Invalid length: " << iovec.iov_len
  92                  << " vs " << expected.length();
  93       return false;
  94     }
  95     if (memcmp(iovec.iov_base, expected.data(), expected.length()) != 0) {
  96       LOG(ERROR) << "Invalid data: " << static_cast<char*>(iovec.iov_base)
  97                  << " vs " << expected.data();
  98       return false;
  99     }
 100     return true;
 101   }
 102
 103   void OnFinFrame(QuicStreamOffset byte_offset, const char* data) {
 104     QuicStreamFrame frame;
 105     frame.stream_id = 1;
 106     frame.offset = byte_offset;
 107     frame.data.Append(const_cast<char*>(data), strlen(data));
 108     frame.fin = true;
 109     sequencer_->OnStreamFrame(frame);
 110   }
 111
 112   void OnFrame(QuicStreamOffset byte_offset, const char* data) {
 113     QuicStreamFrame frame;
 114     frame.stream_id = 1;
 115     frame.offset = byte_offset;
 116     frame.data.Append(const_cast<char*>(data), strlen(data));
 117     frame.fin = false;
 118     sequencer_->OnStreamFrame(frame);
 119   }
 120
 121   MockConnection* connection_;
 122   MockSession session_;
 123   testing::StrictMock<MockStream> stream_;
 124   scoped_ptr<QuicStreamSequencer> sequencer_;
 125   map<QuicStreamOffset, string>* buffered_frames_;
 126 };
 127
 128 TEST_F(QuicStreamSequencerTest, RejectOldFrame) {
 129   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(3));
 130
 131   OnFrame(0, "abc");
 132   EXPECT_EQ(0u, buffered_frames_->size());
 133   EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
 134   // Ignore this - it matches a past sequence number and we should not see it
 135   // again.
 136   OnFrame(0, "def");
 137   EXPECT_EQ(0u, buffered_frames_->size());
 138 }
 139
 140 TEST_F(QuicStreamSequencerTest, RejectBufferedFrame) {
 141   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3));
 142
 143   OnFrame(0, "abc");
 144   EXPECT_EQ(1u, buffered_frames_->size());
 145   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 146   // Ignore this - it matches a buffered frame.
 147   // Right now there's no checking that the payload is consistent.
 148   OnFrame(0, "def");
 149   EXPECT_EQ(1u, buffered_frames_->size());
 150 }
 151
 152 TEST_F(QuicStreamSequencerTest, FullFrameConsumed) {
 153   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(3));
 154
 155   OnFrame(0, "abc");
 156   EXPECT_EQ(0u, buffered_frames_->size());
 157   EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
 158 }
 159
 160 TEST_F(QuicStreamSequencerTest, BlockedThenFullFrameConsumed) {
 161   sequencer_->SetBlockedUntilFlush();
 162
 163   OnFrame(0, "abc");
 164   EXPECT_EQ(1u, buffered_frames_->size());
 165   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 166
 167   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(3));
 168   sequencer_->FlushBufferedFrames();
 169   EXPECT_EQ(0u, buffered_frames_->size());
 170   EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
 171
 172   EXPECT_CALL(stream_, ProcessRawData(StrEq("def"), 3)).WillOnce(Return(3));
 173   EXPECT_CALL(stream_, OnFinRead());
 174   OnFinFrame(3, "def");
 175 }
 176
 177 TEST_F(QuicStreamSequencerTest, BlockedThenFullFrameAndFinConsumed) {
 178   sequencer_->SetBlockedUntilFlush();
 179
 180   OnFinFrame(0, "abc");
 181   EXPECT_EQ(1u, buffered_frames_->size());
 182   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 183
 184   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(3));
 185   EXPECT_CALL(stream_, OnFinRead());
 186   sequencer_->FlushBufferedFrames();
 187   EXPECT_EQ(0u, buffered_frames_->size());
 188   EXPECT_EQ(3u, sequencer_->num_bytes_consumed());
 189 }
 190
 191 TEST_F(QuicStreamSequencerTest, EmptyFrame) {
 192   EXPECT_CALL(stream_,
 193               CloseConnectionWithDetails(QUIC_INVALID_STREAM_FRAME, _));
 194   OnFrame(0, "");
 195   EXPECT_EQ(0u, buffered_frames_->size());
 196   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 197 }
 198
 199 TEST_F(QuicStreamSequencerTest, EmptyFinFrame) {
 200   EXPECT_CALL(stream_, OnFinRead());
 201   OnFinFrame(0, "");
 202   EXPECT_EQ(0u, buffered_frames_->size());
 203   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 204 }
 205
 206 TEST_F(QuicStreamSequencerTest, PartialFrameConsumed) {
 207   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(2));
 208
 209   OnFrame(0, "abc");
 210   EXPECT_EQ(1u, buffered_frames_->size());
 211   EXPECT_EQ(2u, sequencer_->num_bytes_consumed());
 212   EXPECT_EQ("c", buffered_frames_->find(2)->second);
 213 }
 214
 215 TEST_F(QuicStreamSequencerTest, NextxFrameNotConsumed) {
 216   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(0));
 217
 218   OnFrame(0, "abc");
 219   EXPECT_EQ(1u, buffered_frames_->size());
 220   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 221   EXPECT_EQ("abc", buffered_frames_->find(0)->second);
 222   EXPECT_EQ(0, sequencer_->num_early_frames_received());
 223 }
 224
 225 TEST_F(QuicStreamSequencerTest, FutureFrameNotProcessed) {
 226   OnFrame(3, "abc");
 227   EXPECT_EQ(1u, buffered_frames_->size());
 228   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 229   EXPECT_EQ("abc", buffered_frames_->find(3)->second);
 230   EXPECT_EQ(1, sequencer_->num_early_frames_received());
 231 }
 232
 233 TEST_F(QuicStreamSequencerTest, OutOfOrderFrameProcessed) {
 234   // Buffer the first
 235   OnFrame(6, "ghi");
 236   EXPECT_EQ(1u, buffered_frames_->size());
 237   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 238   EXPECT_EQ(3u, sequencer_->num_bytes_buffered());
 239   // Buffer the second
 240   OnFrame(3, "def");
 241   EXPECT_EQ(2u, buffered_frames_->size());
 242   EXPECT_EQ(0u, sequencer_->num_bytes_consumed());
 243   EXPECT_EQ(6u, sequencer_->num_bytes_buffered());
 244
 245   InSequence s;
 246   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(3));
 247   EXPECT_CALL(stream_, ProcessRawData(StrEq("def"), 3)).WillOnce(Return(3));
 248   EXPECT_CALL(stream_, ProcessRawData(StrEq("ghi"), 3)).WillOnce(Return(3));
 249
 250   // Ack right away
 251   OnFrame(0, "abc");
 252   EXPECT_EQ(9u, sequencer_->num_bytes_consumed());
 253   EXPECT_EQ(0u, sequencer_->num_bytes_buffered());
 254
 255   EXPECT_EQ(0u, buffered_frames_->size());
 256 }
 257
 258 TEST_F(QuicStreamSequencerTest, BasicHalfCloseOrdered) {
 259   InSequence s;
 260
 261   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(3));
 262   EXPECT_CALL(stream_, OnFinRead());
 263   OnFinFrame(0, "abc");
 264
 265   EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
 266 }
 267
 268 TEST_F(QuicStreamSequencerTest, BasicHalfCloseUnorderedWithFlush) {
 269   OnFinFrame(6, "");
 270   EXPECT_EQ(6u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
 271   InSequence s;
 272   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(3));
 273   EXPECT_CALL(stream_, ProcessRawData(StrEq("def"), 3)).WillOnce(Return(3));
 274   EXPECT_CALL(stream_, OnFinRead());
 275
 276   OnFrame(3, "def");
 277   OnFrame(0, "abc");
 278 }
 279
 280 TEST_F(QuicStreamSequencerTest, BasicHalfUnordered) {
 281   OnFinFrame(3, "");
 282   EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
 283   InSequence s;
 284   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(3));
 285   EXPECT_CALL(stream_, OnFinRead());
 286
 287   OnFrame(0, "abc");
 288 }
 289
 290 TEST_F(QuicStreamSequencerTest, TerminateWithReadv) {
 291   char buffer[3];
 292
 293   OnFinFrame(3, "");
 294   EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
 295
 296   EXPECT_FALSE(sequencer_->IsClosed());
 297
 298   EXPECT_CALL(stream_, ProcessRawData(StrEq("abc"), 3)).WillOnce(Return(0));
 299   OnFrame(0, "abc");
 300
 301   iovec iov = {&buffer[0], 3};
 302   int bytes_read = sequencer_->Readv(&iov, 1);
 303   EXPECT_EQ(3, bytes_read);
 304   EXPECT_TRUE(sequencer_->IsClosed());
 305 }
 306
 307 TEST_F(QuicStreamSequencerTest, MutipleOffsets) {
 308   OnFinFrame(3, "");
 309   EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
 310
 311   EXPECT_CALL(stream_, Reset(QUIC_MULTIPLE_TERMINATION_OFFSETS));
 312   OnFinFrame(5, "");
 313   EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
 314
 315   EXPECT_CALL(stream_, Reset(QUIC_MULTIPLE_TERMINATION_OFFSETS));
 316   OnFinFrame(1, "");
 317   EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
 318
 319   OnFinFrame(3, "");
 320   EXPECT_EQ(3u, QuicStreamSequencerPeer::GetCloseOffset(sequencer_.get()));
 321 }
 322
 323 class QuicSequencerRandomTest : public QuicStreamSequencerTest {
 324  public:
 325   typedef pair<int, string> Frame;
 326   typedef vector<Frame> FrameList;
 327
 328   void CreateFrames() {
 329     int payload_size = arraysize(kPayload) - 1;
 330     int remaining_payload = payload_size;
 331     while (remaining_payload != 0) {
 332       int size = min(OneToN(6), remaining_payload);
 333       int index = payload_size - remaining_payload;
 334       list_.push_back(std::make_pair(index, string(kPayload + index, size)));
 335       remaining_payload -= size;
 336     }
 337   }
 338
 339   QuicSequencerRandomTest() {
 340     CreateFrames();
 341   }
 342
 343   int OneToN(int n) {
 344     return base::RandInt(1, n);
 345   }
 346
 347   int MaybeProcessMaybeBuffer(const char* data, uint32 len) {
 348     int to_process = len;
 349     if (base::RandUint64() % 2 != 0) {
 350       to_process = base::RandInt(0, len);
 351     }
 352     output_.append(data, to_process);
 353     return to_process;
 354   }
 355
 356   string output_;
 357   FrameList list_;
 358 };
 359
 360 // All frames are processed as soon as we have sequential data.
 361 // Infinite buffering, so all frames are acked right away.
 362 TEST_F(QuicSequencerRandomTest, RandomFramesNoDroppingNoBackup) {
 363   InSequence s;
 364   for (size_t i = 0; i < list_.size(); ++i) {
 365     string* data = &list_[i].second;
 366     EXPECT_CALL(stream_, ProcessRawData(StrEq(*data), data->size()))
 367         .WillOnce(Return(data->size()));
 368   }
 369
 370   while (!list_.empty()) {
 371     int index = OneToN(list_.size()) - 1;
 372     LOG(ERROR) << "Sending index " << index << " " << list_[index].second;
 373     OnFrame(list_[index].first, list_[index].second.data());
 374
 375     list_.erase(list_.begin() + index);
 376   }
 377 }
 378
 379 TEST_F(QuicStreamSequencerTest, FrameOverlapsBufferedData) {
 380   // Ensure that FrameOverlapsBufferedData returns appropriate responses when
 381   // there is existing data buffered.
 382
 383   map<QuicStreamOffset, string>* buffered_frames =
 384       QuicStreamSequencerPeer::GetBufferedFrames(sequencer_.get());
 385
 386   const int kBufferedOffset = 10;
 387   const int kBufferedDataLength = 3;
 388   const int kNewDataLength = 3;
 389   IOVector data = MakeIOVector(string(kNewDataLength, '.'));
 390
 391   // No overlap if no buffered frames.
 392   EXPECT_TRUE(buffered_frames_->empty());
 393   EXPECT_FALSE(sequencer_->FrameOverlapsBufferedData(
 394       QuicStreamFrame(1, false, kBufferedOffset - 1, data)));
 395
 396   // Add a buffered frame.
 397   buffered_frames->insert(
 398       std::make_pair(kBufferedOffset, string(kBufferedDataLength, '.')));
 399
 400   // New byte range partially overlaps with buffered frame, start offset
 401   // preceeding buffered frame.
 402   EXPECT_TRUE(sequencer_->FrameOverlapsBufferedData(
 403       QuicStreamFrame(1, false, kBufferedOffset - 1, data)));
 404   EXPECT_TRUE(sequencer_->FrameOverlapsBufferedData(
 405       QuicStreamFrame(1, false, kBufferedOffset - kNewDataLength + 1, data)));
 406
 407   // New byte range partially overlaps with buffered frame, start offset
 408   // inside existing buffered frame.
 409   EXPECT_TRUE(sequencer_->FrameOverlapsBufferedData(
 410       QuicStreamFrame(1, false, kBufferedOffset + 1, data)));
 411   EXPECT_TRUE(sequencer_->FrameOverlapsBufferedData(QuicStreamFrame(
 412       1, false, kBufferedOffset + kBufferedDataLength - 1, data)));
 413
 414   // New byte range entirely outside of buffered frames, start offset preceeding
 415   // buffered frame.
 416   EXPECT_FALSE(sequencer_->FrameOverlapsBufferedData(
 417       QuicStreamFrame(1, false, kBufferedOffset - kNewDataLength, data)));
 418
 419   // New byte range entirely outside of buffered frames, start offset later than
 420   // buffered frame.
 421   EXPECT_FALSE(sequencer_->FrameOverlapsBufferedData(QuicStreamFrame(
 422       1, false, kBufferedOffset + kBufferedDataLength, data)));
 423 }
 424
 425 TEST_F(QuicStreamSequencerTest, DontAcceptOverlappingFrames) {
 426   // The peer should never send us non-identical stream frames which contain
 427   // overlapping byte ranges - if they do, we close the connection.
 428
 429   QuicStreamFrame frame1(kClientDataStreamId1, false, 1, MakeIOVector("hello"));
 430   sequencer_->OnStreamFrame(frame1);
 431
 432   QuicStreamFrame frame2(kClientDataStreamId1, false, 2, MakeIOVector("hello"));
 433   EXPECT_TRUE(sequencer_->FrameOverlapsBufferedData(frame2));
 434   EXPECT_CALL(stream_, CloseConnectionWithDetails(QUIC_INVALID_STREAM_FRAME, _))
 435       .Times(1);
 436   sequencer_->OnStreamFrame(frame2);
 437 }
 438
 439 }  // namespace
 440 }  // namespace test
 441 }  // namespace net