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