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
21using base::StringPiece;
22using std::map;
23using std::min;
24using std::pair;
25using std::vector;
26using testing::_;
27using testing::AnyNumber;
28using testing::InSequence;
29using testing::Return;
30using testing::StrEq;
31
32namespace net {
33namespace test {
34
35class 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
55namespace {
56
57static const char kPayload[] =
58    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
59
60class 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
134TEST_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
146TEST_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
158TEST_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
166TEST_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
183TEST_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
197TEST_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
205TEST_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
212TEST_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
221TEST_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
230TEST_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
237TEST_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
262TEST_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
272TEST_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
284TEST_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
294TEST_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
311TEST_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
327class 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.
366TEST_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
383TEST_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
429TEST_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