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