OLD | NEW |
(Empty) | |
| 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/rand_util.h" |
| 11 #include "net/quic/reliable_quic_stream.h" |
| 12 #include "testing/gmock/include/gmock/gmock.h" |
| 13 #include "testing/gtest/include/gtest/gtest.h" |
| 14 |
| 15 using base::StringPiece; |
| 16 using std::min; |
| 17 using std::pair; |
| 18 using std::vector; |
| 19 using testing::_; |
| 20 using testing::AnyNumber; |
| 21 using testing::InSequence; |
| 22 using testing::Return; |
| 23 using testing::StrEq; |
| 24 |
| 25 namespace net { |
| 26 |
| 27 class QuicStreamSequencerPeer : public QuicStreamSequencer { |
| 28 public: |
| 29 explicit QuicStreamSequencerPeer(ReliableQuicStream* stream) |
| 30 : QuicStreamSequencer(stream) { |
| 31 } |
| 32 |
| 33 QuicStreamSequencerPeer(int32 max_mem, ReliableQuicStream* stream) |
| 34 : QuicStreamSequencer(max_mem, stream) {} |
| 35 |
| 36 virtual bool OnFrame(QuicStreamOffset byte_offset, |
| 37 const char* data, |
| 38 uint32 data_len) { |
| 39 QuicStreamFrame frame; |
| 40 frame.stream_id = 1; |
| 41 frame.offset = byte_offset; |
| 42 frame.data = StringPiece(data, data_len); |
| 43 return OnStreamFrame(frame); |
| 44 } |
| 45 |
| 46 void SetMemoryLimit(size_t limit) { |
| 47 max_frame_memory_ = limit; |
| 48 } |
| 49 |
| 50 ReliableQuicStream* stream() { return stream_; } |
| 51 uint64 num_bytes_consumed() { return num_bytes_consumed_; } |
| 52 FrameMap* frames() { return &frames_; } |
| 53 int32 max_frame_memory() { return max_frame_memory_; } |
| 54 QuicStreamOffset close_offset() { return close_offset_; } |
| 55 }; |
| 56 |
| 57 class MockStream : public ReliableQuicStream { |
| 58 public: |
| 59 MockStream(QuicSession* session, QuicStreamId id) |
| 60 : ReliableQuicStream(id, session) { |
| 61 } |
| 62 |
| 63 MOCK_METHOD1(TerminateFromPeer, void(bool half_close)); |
| 64 MOCK_METHOD2(ProcessData, uint32(const char* data, uint32 data_len)); |
| 65 MOCK_METHOD1(Close, void(QuicErrorCode error)); |
| 66 }; |
| 67 |
| 68 namespace { |
| 69 |
| 70 static const char kPayload[] = |
| 71 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; |
| 72 |
| 73 class QuicStreamSequencerTest : public ::testing::Test { |
| 74 protected: |
| 75 QuicStreamSequencerTest() |
| 76 : session_(NULL), |
| 77 stream_(session_, 1), |
| 78 sequencer_(new QuicStreamSequencerPeer(&stream_)) { |
| 79 } |
| 80 |
| 81 QuicSession* session_; |
| 82 testing::StrictMock<MockStream> stream_; |
| 83 scoped_ptr<QuicStreamSequencerPeer> sequencer_; |
| 84 }; |
| 85 |
| 86 TEST_F(QuicStreamSequencerTest, RejectOldFrame) { |
| 87 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)) |
| 88 .WillOnce(Return(3)); |
| 89 |
| 90 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 91 EXPECT_EQ(0u, sequencer_->frames()->size()); |
| 92 EXPECT_EQ(3u, sequencer_->num_bytes_consumed()); |
| 93 // Nack this - it matches a past sequence number and we should not see it |
| 94 // again. |
| 95 EXPECT_FALSE(sequencer_->OnFrame(0, "def", 3)); |
| 96 EXPECT_EQ(0u, sequencer_->frames()->size()); |
| 97 } |
| 98 |
| 99 TEST_F(QuicStreamSequencerTest, RejectOverlyLargeFrame) { |
| 100 /* |
| 101 EXPECT_DFATAL(sequencer_.reset(new QuicStreamSequencerPeer(2, &stream_)), |
| 102 "Setting max frame memory to 2. " |
| 103 "Some frames will be impossible to handle."); |
| 104 |
| 105 EXPECT_DEBUG_DEATH(sequencer_->OnFrame(0, "abc", 3), ""); |
| 106 */ |
| 107 } |
| 108 |
| 109 TEST_F(QuicStreamSequencerTest, DropFramePastBuffering) { |
| 110 sequencer_->SetMemoryLimit(3); |
| 111 |
| 112 EXPECT_FALSE(sequencer_->OnFrame(3, "abc", 3)); |
| 113 } |
| 114 |
| 115 TEST_F(QuicStreamSequencerTest, RejectBufferedFrame) { |
| 116 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)); |
| 117 |
| 118 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 119 EXPECT_EQ(1u, sequencer_->frames()->size()); |
| 120 EXPECT_EQ(0u, sequencer_->num_bytes_consumed()); |
| 121 // Ignore this - it matches a buffered frame. |
| 122 // Right now there's no checking that the payload is consistent. |
| 123 EXPECT_FALSE(sequencer_->OnFrame(0, "def", 3)); |
| 124 EXPECT_EQ(1u, sequencer_->frames()->size()); |
| 125 } |
| 126 |
| 127 TEST_F(QuicStreamSequencerTest, FullFrameConsumed) { |
| 128 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)) |
| 129 .WillOnce(Return(3)); |
| 130 |
| 131 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 132 EXPECT_EQ(0u, sequencer_->frames()->size()); |
| 133 EXPECT_EQ(3u, sequencer_->num_bytes_consumed()); |
| 134 } |
| 135 |
| 136 TEST_F(QuicStreamSequencerTest, PartialFrameConsumed) { |
| 137 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)) |
| 138 .WillOnce(Return(2)); |
| 139 |
| 140 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 141 EXPECT_EQ(1u, sequencer_->frames()->size()); |
| 142 EXPECT_EQ(2u, sequencer_->num_bytes_consumed()); |
| 143 EXPECT_EQ("c", sequencer_->frames()->find(2)->second); |
| 144 } |
| 145 |
| 146 TEST_F(QuicStreamSequencerTest, NextxFrameNotConsumed) { |
| 147 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)) |
| 148 .WillOnce(Return(0)); |
| 149 |
| 150 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 151 EXPECT_EQ(1u, sequencer_->frames()->size()); |
| 152 EXPECT_EQ(0u, sequencer_->num_bytes_consumed()); |
| 153 EXPECT_EQ("abc", sequencer_->frames()->find(0)->second); |
| 154 } |
| 155 |
| 156 TEST_F(QuicStreamSequencerTest, FutureFrameNotProcessed) { |
| 157 EXPECT_TRUE(sequencer_->OnFrame(3, "abc", 3)); |
| 158 EXPECT_EQ(1u, sequencer_->frames()->size()); |
| 159 EXPECT_EQ(0u, sequencer_->num_bytes_consumed()); |
| 160 EXPECT_EQ("abc", sequencer_->frames()->find(3)->second); |
| 161 } |
| 162 |
| 163 TEST_F(QuicStreamSequencerTest, OutOfOrderFrameProcessed) { |
| 164 // Buffer the first |
| 165 EXPECT_TRUE(sequencer_->OnFrame(6, "ghi", 3)); |
| 166 EXPECT_EQ(1u, sequencer_->frames()->size()); |
| 167 EXPECT_EQ(0u, sequencer_->num_bytes_consumed()); |
| 168 // Buffer the second |
| 169 EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3)); |
| 170 EXPECT_EQ(2u, sequencer_->frames()->size()); |
| 171 EXPECT_EQ(0u, sequencer_->num_bytes_consumed()); |
| 172 |
| 173 InSequence s; |
| 174 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 175 EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3)); |
| 176 EXPECT_CALL(stream_, ProcessData(StrEq("ghi"), 3)).WillOnce(Return(3)); |
| 177 |
| 178 // Ack right away |
| 179 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 180 EXPECT_EQ(9u, sequencer_->num_bytes_consumed()); |
| 181 |
| 182 EXPECT_EQ(0u, sequencer_->frames()->size()); |
| 183 } |
| 184 |
| 185 TEST_F(QuicStreamSequencerTest, OutOfOrderFramesProcessedWithBuffering) { |
| 186 sequencer_->SetMemoryLimit(9); |
| 187 |
| 188 // Too far to buffer. |
| 189 EXPECT_FALSE(sequencer_->OnFrame(9, "jkl", 3)); |
| 190 |
| 191 // We can afford to buffer this. |
| 192 EXPECT_TRUE(sequencer_->OnFrame(6, "ghi", 3)); |
| 193 EXPECT_EQ(0u, sequencer_->num_bytes_consumed()); |
| 194 |
| 195 InSequence s; |
| 196 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 197 |
| 198 // Ack right away |
| 199 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 200 EXPECT_EQ(3u, sequencer_->num_bytes_consumed()); |
| 201 |
| 202 // We should be willing to buffer this now. |
| 203 EXPECT_TRUE(sequencer_->OnFrame(9, "jkl", 3)); |
| 204 EXPECT_EQ(3u, sequencer_->num_bytes_consumed()); |
| 205 |
| 206 EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3)); |
| 207 EXPECT_CALL(stream_, ProcessData(StrEq("ghi"), 3)).WillOnce(Return(3)); |
| 208 EXPECT_CALL(stream_, ProcessData(StrEq("jkl"), 3)).WillOnce(Return(3)); |
| 209 |
| 210 EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3)); |
| 211 EXPECT_EQ(12u, sequencer_->num_bytes_consumed()); |
| 212 EXPECT_EQ(0u, sequencer_->frames()->size()); |
| 213 } |
| 214 |
| 215 TEST_F(QuicStreamSequencerTest, BasicCloseOrdered) { |
| 216 InSequence s; |
| 217 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 218 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 219 |
| 220 EXPECT_CALL(stream_, TerminateFromPeer(false)); |
| 221 sequencer_->CloseStreamAtOffset(3, false); |
| 222 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 223 } |
| 224 |
| 225 TEST_F(QuicStreamSequencerTest, BasicHalfOrdered) { |
| 226 InSequence s; |
| 227 |
| 228 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 229 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 230 |
| 231 EXPECT_CALL(stream_, TerminateFromPeer(true)); |
| 232 sequencer_->CloseStreamAtOffset(3, true); |
| 233 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 234 } |
| 235 |
| 236 TEST_F(QuicStreamSequencerTest, BasicCloseUnordered) { |
| 237 sequencer_->CloseStreamAtOffset(3, false); |
| 238 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 239 |
| 240 InSequence s; |
| 241 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 242 EXPECT_CALL(stream_, TerminateFromPeer(false)); |
| 243 |
| 244 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 245 } |
| 246 |
| 247 TEST_F(QuicStreamSequencerTest, BasicHalfUnorderedWithFlush) { |
| 248 sequencer_->CloseStreamAtOffset(6, true); |
| 249 EXPECT_EQ(6u, sequencer_->close_offset()); |
| 250 InSequence s; |
| 251 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 252 EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3)); |
| 253 EXPECT_CALL(stream_, TerminateFromPeer(true)); |
| 254 |
| 255 EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3)); |
| 256 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 257 } |
| 258 |
| 259 TEST_F(QuicStreamSequencerTest, BasicCloseUnorderedWithFlush) { |
| 260 sequencer_->CloseStreamAtOffset(6, false); |
| 261 EXPECT_EQ(6u, sequencer_->close_offset()); |
| 262 |
| 263 InSequence s; |
| 264 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 265 EXPECT_CALL(stream_, ProcessData(StrEq("def"), 3)).WillOnce(Return(3)); |
| 266 EXPECT_CALL(stream_, TerminateFromPeer(false)); |
| 267 |
| 268 EXPECT_TRUE(sequencer_->OnFrame(3, "def", 3)); |
| 269 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 270 } |
| 271 |
| 272 TEST_F(QuicStreamSequencerTest, BasicHalfUnordered) { |
| 273 sequencer_->CloseStreamAtOffset(3, true); |
| 274 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 275 InSequence s; |
| 276 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 277 EXPECT_CALL(stream_, TerminateFromPeer(true)); |
| 278 |
| 279 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 280 } |
| 281 |
| 282 TEST_F(QuicStreamSequencerTest, CloseStreamBeforeCloseEqual) { |
| 283 sequencer_->CloseStreamAtOffset(3, true); |
| 284 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 285 |
| 286 sequencer_->CloseStreamAtOffset(3, false); |
| 287 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 288 |
| 289 InSequence s; |
| 290 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 291 EXPECT_CALL(stream_, TerminateFromPeer(false)); |
| 292 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 293 } |
| 294 |
| 295 TEST_F(QuicStreamSequencerTest, CloseBeforeTermianteEqual) { |
| 296 sequencer_->CloseStreamAtOffset(3, false); |
| 297 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 298 |
| 299 sequencer_->CloseStreamAtOffset(3, true); |
| 300 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 301 |
| 302 InSequence s; |
| 303 EXPECT_CALL(stream_, ProcessData(StrEq("abc"), 3)).WillOnce(Return(3)); |
| 304 EXPECT_CALL(stream_, TerminateFromPeer(false)); |
| 305 EXPECT_TRUE(sequencer_->OnFrame(0, "abc", 3)); |
| 306 } |
| 307 |
| 308 TEST_F(QuicStreamSequencerTest, MutipleOffsets) { |
| 309 sequencer_->CloseStreamAtOffset(3, false); |
| 310 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 311 |
| 312 EXPECT_CALL(stream_, Close(QUIC_MULTIPLE_TERMINATION_OFFSETS)); |
| 313 sequencer_->CloseStreamAtOffset(5, false); |
| 314 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 315 |
| 316 EXPECT_CALL(stream_, Close(QUIC_MULTIPLE_TERMINATION_OFFSETS)); |
| 317 sequencer_->CloseStreamAtOffset(1, false); |
| 318 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 319 |
| 320 sequencer_->CloseStreamAtOffset(3, false); |
| 321 EXPECT_EQ(3u, sequencer_->close_offset()); |
| 322 } |
| 323 |
| 324 class QuicSequencerRandomTest : public QuicStreamSequencerTest { |
| 325 public: |
| 326 typedef pair<int, string> Frame; |
| 327 typedef vector<Frame> FrameList; |
| 328 |
| 329 void CreateFrames() { |
| 330 int payload_size = arraysize(kPayload) - 1; |
| 331 int remaining_payload = payload_size; |
| 332 while (remaining_payload != 0) { |
| 333 int size = min(OneToN(6), remaining_payload); |
| 334 int idx = payload_size - remaining_payload; |
| 335 list_.push_back(make_pair(idx, string(kPayload + idx, size))); |
| 336 remaining_payload -= size; |
| 337 } |
| 338 } |
| 339 |
| 340 QuicSequencerRandomTest() { |
| 341 //int32 seed = ACMRandom::HostnamePidTimeSeed(); |
| 342 //LOG(INFO) << "**** The current seed is " << seed << " ****"; |
| 343 //random_.reset(new ACMRandom(seed)); |
| 344 |
| 345 CreateFrames(); |
| 346 } |
| 347 |
| 348 int OneToN(int n) { |
| 349 return base::RandInt(1, n); |
| 350 } |
| 351 |
| 352 int MaybeProcessMaybeBuffer(const char* data, uint32 len) { |
| 353 int to_process = len; |
| 354 if (base::RandUint64() % 2 != 0) { |
| 355 to_process = base::RandInt(0, len); |
| 356 } |
| 357 output_.append(data, to_process); |
| 358 LOG(ERROR) << output_; |
| 359 return to_process; |
| 360 } |
| 361 |
| 362 string output_; |
| 363 //scoped_ptr<ACMRandom> random_; |
| 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_, ProcessData(StrEq(*data), data->size())) |
| 374 .WillOnce(Return(data->size())); |
| 375 } |
| 376 |
| 377 while (list_.size() != 0) { |
| 378 int idx = OneToN(list_.size()) - 1; |
| 379 LOG(ERROR) << "Sending index " << idx << " " << list_[idx].second.c_str(); |
| 380 EXPECT_TRUE(sequencer_->OnFrame( |
| 381 list_[idx].first, list_[idx].second.c_str(), |
| 382 list_[idx].second.size())); |
| 383 list_.erase(list_.begin() + idx); |
| 384 } |
| 385 } |
| 386 |
| 387 // All frames are processed as soon as we have sequential data. |
| 388 // Buffering, so some frames are rejected. |
| 389 TEST_F(QuicSequencerRandomTest, RandomFramesDroppingNoBackup) { |
| 390 sequencer_->SetMemoryLimit(26); |
| 391 |
| 392 InSequence s; |
| 393 for (size_t i = 0; i < list_.size(); ++i) { |
| 394 string* data = &list_[i].second; |
| 395 EXPECT_CALL(stream_, ProcessData(StrEq(*data), data->size())) |
| 396 .WillOnce(Return(data->size())); |
| 397 } |
| 398 |
| 399 while (list_.size() != 0) { |
| 400 int idx = OneToN(list_.size()) - 1; |
| 401 LOG(ERROR) << "Sending index " << idx << " " << list_[idx].second.c_str(); |
| 402 bool acked = sequencer_->OnFrame( |
| 403 list_[idx].first, list_[idx].second.c_str(), |
| 404 list_[idx].second.size()); |
| 405 if (acked) { |
| 406 list_.erase(list_.begin() + idx); |
| 407 } |
| 408 } |
| 409 } |
| 410 |
| 411 } // namespace |
| 412 |
| 413 } // namespace net |
OLD | NEW |