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