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