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 void 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 sequencer_->OnStreamFrame(frame); 116 } 117 118 void 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 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 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 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 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 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 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 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 OnFinFrame(3, "def"); 181 } 182 183 TEST_F(QuicStreamSequencerTest, BlockedThenFullFrameAndFinConsumed) { 184 sequencer_->SetBlockedUntilFlush(); 185 186 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 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 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 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 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 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 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 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 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 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 OnFrame(3, "def"); 281 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 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 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 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 446
