1 // Copyright (c) 2017 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/third_party/quiche/src/quic/core/quic_stream_send_buffer.h"
6 
7 #include <string>
8 
9 #include "net/third_party/quiche/src/quic/core/quic_data_writer.h"
10 #include "net/third_party/quiche/src/quic/core/quic_simple_buffer_allocator.h"
11 #include "net/third_party/quiche/src/quic/core/quic_utils.h"
12 #include "net/third_party/quiche/src/quic/platform/api/quic_expect_bug.h"
13 #include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
14 #include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
15 #include "net/third_party/quiche/src/quic/platform/api/quic_test_mem_slice_vector.h"
16 #include "net/third_party/quiche/src/quic/test_tools/quic_stream_send_buffer_peer.h"
17 #include "net/third_party/quiche/src/quic/test_tools/quic_test_utils.h"
18 #include "net/third_party/quiche/src/common/platform/api/quiche_string_piece.h"
19 
20 namespace quic {
21 namespace test {
22 namespace {
23 
MakeIovec(quiche::QuicheStringPiece data)24 struct iovec MakeIovec(quiche::QuicheStringPiece data) {
25   struct iovec iov = {const_cast<char*>(data.data()),
26                       static_cast<size_t>(data.size())};
27   return iov;
28 }
29 
30 class QuicStreamSendBufferTest : public QuicTest {
31  public:
QuicStreamSendBufferTest()32   QuicStreamSendBufferTest() : send_buffer_(&allocator_) {
33     EXPECT_EQ(0u, send_buffer_.size());
34     EXPECT_EQ(0u, send_buffer_.stream_bytes_written());
35     EXPECT_EQ(0u, send_buffer_.stream_bytes_outstanding());
36     std::string data1(1536, 'a');
37     std::string data2 = std::string(256, 'b') + std::string(256, 'c');
38     struct iovec iov[2];
39     iov[0] = MakeIovec(quiche::QuicheStringPiece(data1));
40     iov[1] = MakeIovec(quiche::QuicheStringPiece(data2));
41 
42     QuicUniqueBufferPtr buffer1 = MakeUniqueBuffer(&allocator_, 1024);
43     memset(buffer1.get(), 'c', 1024);
44     QuicMemSlice slice1(std::move(buffer1), 1024);
45     QuicUniqueBufferPtr buffer2 = MakeUniqueBuffer(&allocator_, 768);
46     memset(buffer2.get(), 'd', 768);
47     QuicMemSlice slice2(std::move(buffer2), 768);
48 
49     // The stream offset should be 0 since nothing is written.
50     EXPECT_EQ(0u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
51 
52     // Save all data.
53     SetQuicFlag(FLAGS_quic_send_buffer_max_data_slice_size, 1024);
54     send_buffer_.SaveStreamData(iov, 2, 0, 2048);
55     send_buffer_.SaveMemSlice(std::move(slice1));
56     EXPECT_TRUE(slice1.empty());
57     send_buffer_.SaveMemSlice(std::move(slice2));
58     EXPECT_TRUE(slice2.empty());
59 
60     EXPECT_EQ(4u, send_buffer_.size());
61     // At this point, the whole buffer looks like:
62     // |      a * 1536      |b * 256|         c * 1280        |  d * 768  |
63     // |    slice1     |     slice2       |      slice3       |   slice4  |
64   }
65 
WriteAllData()66   void WriteAllData() {
67     // Write all data.
68     char buf[4000];
69     QuicDataWriter writer(4000, buf, quiche::HOST_BYTE_ORDER);
70     send_buffer_.WriteStreamData(0, 3840u, &writer);
71 
72     send_buffer_.OnStreamDataConsumed(3840u);
73     EXPECT_EQ(3840u, send_buffer_.stream_bytes_written());
74     EXPECT_EQ(3840u, send_buffer_.stream_bytes_outstanding());
75   }
76 
77   SimpleBufferAllocator allocator_;
78   QuicStreamSendBuffer send_buffer_;
79 };
80 
TEST_F(QuicStreamSendBufferTest,CopyDataToBuffer)81 TEST_F(QuicStreamSendBufferTest, CopyDataToBuffer) {
82   char buf[4000];
83   QuicDataWriter writer(4000, buf, quiche::HOST_BYTE_ORDER);
84   std::string copy1(1024, 'a');
85   std::string copy2 =
86       std::string(512, 'a') + std::string(256, 'b') + std::string(256, 'c');
87   std::string copy3(1024, 'c');
88   std::string copy4(768, 'd');
89 
90   ASSERT_TRUE(send_buffer_.WriteStreamData(0, 1024, &writer));
91   EXPECT_EQ(copy1, quiche::QuicheStringPiece(buf, 1024));
92   ASSERT_TRUE(send_buffer_.WriteStreamData(1024, 1024, &writer));
93   EXPECT_EQ(copy2, quiche::QuicheStringPiece(buf + 1024, 1024));
94   ASSERT_TRUE(send_buffer_.WriteStreamData(2048, 1024, &writer));
95   EXPECT_EQ(copy3, quiche::QuicheStringPiece(buf + 2048, 1024));
96   ASSERT_TRUE(send_buffer_.WriteStreamData(3072, 768, &writer));
97   EXPECT_EQ(copy4, quiche::QuicheStringPiece(buf + 3072, 768));
98 
99   // Test data piece across boundries.
100   QuicDataWriter writer2(4000, buf, quiche::HOST_BYTE_ORDER);
101   std::string copy5 =
102       std::string(536, 'a') + std::string(256, 'b') + std::string(232, 'c');
103   ASSERT_TRUE(send_buffer_.WriteStreamData(1000, 1024, &writer2));
104   EXPECT_EQ(copy5, quiche::QuicheStringPiece(buf, 1024));
105   ASSERT_TRUE(send_buffer_.WriteStreamData(2500, 1024, &writer2));
106   std::string copy6 = std::string(572, 'c') + std::string(452, 'd');
107   EXPECT_EQ(copy6, quiche::QuicheStringPiece(buf + 1024, 1024));
108 
109   // Invalid data copy.
110   QuicDataWriter writer3(4000, buf, quiche::HOST_BYTE_ORDER);
111   EXPECT_FALSE(send_buffer_.WriteStreamData(3000, 1024, &writer3));
112   EXPECT_QUIC_BUG(send_buffer_.WriteStreamData(0, 4000, &writer3),
113                   "Writer fails to write.");
114 
115   send_buffer_.OnStreamDataConsumed(3840);
116   EXPECT_EQ(3840u, send_buffer_.stream_bytes_written());
117   EXPECT_EQ(3840u, send_buffer_.stream_bytes_outstanding());
118 }
119 
120 // Regression test for b/143491027.
TEST_F(QuicStreamSendBufferTest,WriteStreamDataContainsBothRetransmissionAndNewData)121 TEST_F(QuicStreamSendBufferTest,
122        WriteStreamDataContainsBothRetransmissionAndNewData) {
123   std::string copy1(1024, 'a');
124   std::string copy2 =
125       std::string(512, 'a') + std::string(256, 'b') + std::string(256, 'c');
126   std::string copy3 = std::string(1024, 'c') + std::string(100, 'd');
127   char buf[6000];
128   QuicDataWriter writer(6000, buf, quiche::HOST_BYTE_ORDER);
129   // Write more than one slice.
130   EXPECT_EQ(0, QuicStreamSendBufferPeer::write_index(&send_buffer_));
131   ASSERT_TRUE(send_buffer_.WriteStreamData(0, 1024, &writer));
132   EXPECT_EQ(copy1, quiche::QuicheStringPiece(buf, 1024));
133   EXPECT_EQ(1, QuicStreamSendBufferPeer::write_index(&send_buffer_));
134 
135   // Retransmit the first frame and also send new data.
136   ASSERT_TRUE(send_buffer_.WriteStreamData(0, 2048, &writer));
137   EXPECT_EQ(copy1 + copy2, quiche::QuicheStringPiece(buf + 1024, 2048));
138 
139   // Write new data.
140   EXPECT_EQ(2048u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
141   ASSERT_TRUE(send_buffer_.WriteStreamData(2048, 50, &writer));
142   EXPECT_EQ(std::string(50, 'c'),
143             quiche::QuicheStringPiece(buf + 1024 + 2048, 50));
144   EXPECT_EQ(3072u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
145   ASSERT_TRUE(send_buffer_.WriteStreamData(2048, 1124, &writer));
146   EXPECT_EQ(copy3, quiche::QuicheStringPiece(buf + 1024 + 2048 + 50, 1124));
147   EXPECT_EQ(3840u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
148 }
149 
TEST_F(QuicStreamSendBufferTest,RemoveStreamFrame)150 TEST_F(QuicStreamSendBufferTest, RemoveStreamFrame) {
151   WriteAllData();
152 
153   QuicByteCount newly_acked_length;
154   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(1024, 1024, &newly_acked_length));
155   EXPECT_EQ(1024u, newly_acked_length);
156   EXPECT_EQ(4u, send_buffer_.size());
157 
158   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(2048, 1024, &newly_acked_length));
159   EXPECT_EQ(1024u, newly_acked_length);
160   EXPECT_EQ(4u, send_buffer_.size());
161 
162   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(0, 1024, &newly_acked_length));
163   EXPECT_EQ(1024u, newly_acked_length);
164 
165   // Send buffer is cleaned up in order.
166   EXPECT_EQ(1u, send_buffer_.size());
167   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(3072, 768, &newly_acked_length));
168   EXPECT_EQ(768u, newly_acked_length);
169   EXPECT_EQ(0u, send_buffer_.size());
170 }
171 
TEST_F(QuicStreamSendBufferTest,RemoveStreamFrameAcrossBoundries)172 TEST_F(QuicStreamSendBufferTest, RemoveStreamFrameAcrossBoundries) {
173   WriteAllData();
174 
175   QuicByteCount newly_acked_length;
176   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(2024, 576, &newly_acked_length));
177   EXPECT_EQ(576u, newly_acked_length);
178   EXPECT_EQ(4u, send_buffer_.size());
179 
180   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(0, 1000, &newly_acked_length));
181   EXPECT_EQ(1000u, newly_acked_length);
182   EXPECT_EQ(4u, send_buffer_.size());
183 
184   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(1000, 1024, &newly_acked_length));
185   EXPECT_EQ(1024u, newly_acked_length);
186   // Send buffer is cleaned up in order.
187   EXPECT_EQ(2u, send_buffer_.size());
188 
189   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(2600, 1024, &newly_acked_length));
190   EXPECT_EQ(1024u, newly_acked_length);
191   EXPECT_EQ(1u, send_buffer_.size());
192 
193   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(3624, 216, &newly_acked_length));
194   EXPECT_EQ(216u, newly_acked_length);
195   EXPECT_EQ(0u, send_buffer_.size());
196 }
197 
TEST_F(QuicStreamSendBufferTest,AckStreamDataMultipleTimes)198 TEST_F(QuicStreamSendBufferTest, AckStreamDataMultipleTimes) {
199   WriteAllData();
200   QuicByteCount newly_acked_length;
201   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(100, 1500, &newly_acked_length));
202   EXPECT_EQ(1500u, newly_acked_length);
203   EXPECT_EQ(4u, send_buffer_.size());
204 
205   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(2000, 500, &newly_acked_length));
206   EXPECT_EQ(500u, newly_acked_length);
207   EXPECT_EQ(4u, send_buffer_.size());
208 
209   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(0, 2600, &newly_acked_length));
210   EXPECT_EQ(600u, newly_acked_length);
211   // Send buffer is cleaned up in order.
212   EXPECT_EQ(2u, send_buffer_.size());
213 
214   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(2200, 1640, &newly_acked_length));
215   EXPECT_EQ(1240u, newly_acked_length);
216   EXPECT_EQ(0u, send_buffer_.size());
217 
218   EXPECT_FALSE(send_buffer_.OnStreamDataAcked(4000, 100, &newly_acked_length));
219 }
220 
TEST_F(QuicStreamSendBufferTest,AckStreamDataOutOfOrder)221 TEST_F(QuicStreamSendBufferTest, AckStreamDataOutOfOrder) {
222   WriteAllData();
223   QuicByteCount newly_acked_length;
224   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(500, 1000, &newly_acked_length));
225   EXPECT_EQ(1000u, newly_acked_length);
226   EXPECT_EQ(4u, send_buffer_.size());
227   EXPECT_EQ(3840u, QuicStreamSendBufferPeer::TotalLength(&send_buffer_));
228 
229   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(1200, 1000, &newly_acked_length));
230   EXPECT_EQ(700u, newly_acked_length);
231   EXPECT_EQ(4u, send_buffer_.size());
232   // Slice 2 gets fully acked.
233   EXPECT_EQ(2816u, QuicStreamSendBufferPeer::TotalLength(&send_buffer_));
234 
235   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(2000, 1840, &newly_acked_length));
236   EXPECT_EQ(1640u, newly_acked_length);
237   EXPECT_EQ(4u, send_buffer_.size());
238   // Slices 3 and 4 get fully acked.
239   EXPECT_EQ(1024u, QuicStreamSendBufferPeer::TotalLength(&send_buffer_));
240 
241   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(0, 1000, &newly_acked_length));
242   EXPECT_EQ(500u, newly_acked_length);
243   EXPECT_EQ(0u, send_buffer_.size());
244   EXPECT_EQ(0u, QuicStreamSendBufferPeer::TotalLength(&send_buffer_));
245 }
246 
TEST_F(QuicStreamSendBufferTest,PendingRetransmission)247 TEST_F(QuicStreamSendBufferTest, PendingRetransmission) {
248   WriteAllData();
249   EXPECT_TRUE(send_buffer_.IsStreamDataOutstanding(0, 3840));
250   EXPECT_FALSE(send_buffer_.HasPendingRetransmission());
251   // Lost data [0, 1200).
252   send_buffer_.OnStreamDataLost(0, 1200);
253   // Lost data [1500, 2000).
254   send_buffer_.OnStreamDataLost(1500, 500);
255   EXPECT_TRUE(send_buffer_.HasPendingRetransmission());
256 
257   EXPECT_EQ(StreamPendingRetransmission(0, 1200),
258             send_buffer_.NextPendingRetransmission());
259   // Retransmit data [0, 500).
260   send_buffer_.OnStreamDataRetransmitted(0, 500);
261   EXPECT_TRUE(send_buffer_.IsStreamDataOutstanding(0, 500));
262   EXPECT_EQ(StreamPendingRetransmission(500, 700),
263             send_buffer_.NextPendingRetransmission());
264   // Ack data [500, 1200).
265   QuicByteCount newly_acked_length = 0;
266   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(500, 700, &newly_acked_length));
267   EXPECT_FALSE(send_buffer_.IsStreamDataOutstanding(500, 700));
268   EXPECT_TRUE(send_buffer_.HasPendingRetransmission());
269   EXPECT_EQ(StreamPendingRetransmission(1500, 500),
270             send_buffer_.NextPendingRetransmission());
271   // Retransmit data [1500, 2000).
272   send_buffer_.OnStreamDataRetransmitted(1500, 500);
273   EXPECT_FALSE(send_buffer_.HasPendingRetransmission());
274 
275   // Lost [200, 800).
276   send_buffer_.OnStreamDataLost(200, 600);
277   EXPECT_TRUE(send_buffer_.HasPendingRetransmission());
278   // Verify [200, 500) is considered as lost, as [500, 800) has been acked.
279   EXPECT_EQ(StreamPendingRetransmission(200, 300),
280             send_buffer_.NextPendingRetransmission());
281 
282   // Verify 0 length data is not outstanding.
283   EXPECT_FALSE(send_buffer_.IsStreamDataOutstanding(100, 0));
284   // Verify partially acked data is outstanding.
285   EXPECT_TRUE(send_buffer_.IsStreamDataOutstanding(400, 800));
286 }
287 
TEST_F(QuicStreamSendBufferTest,EndOffset)288 TEST_F(QuicStreamSendBufferTest, EndOffset) {
289   char buf[4000];
290   QuicDataWriter writer(4000, buf, quiche::HOST_BYTE_ORDER);
291 
292   EXPECT_EQ(1024u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
293   ASSERT_TRUE(send_buffer_.WriteStreamData(0, 1024, &writer));
294   // Last offset we've seen is 1024
295   EXPECT_EQ(1024u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
296 
297   ASSERT_TRUE(send_buffer_.WriteStreamData(1024, 512, &writer));
298   // Last offset is now 2048 as that's the end of the next slice.
299   EXPECT_EQ(2048u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
300   send_buffer_.OnStreamDataConsumed(1024);
301 
302   // If data in 1st slice gets ACK'ed, it shouldn't change the indexed slice
303   QuicByteCount newly_acked_length;
304   EXPECT_TRUE(send_buffer_.OnStreamDataAcked(0, 1024, &newly_acked_length));
305   // Last offset is still 2048.
306   EXPECT_EQ(2048u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
307 
308   ASSERT_TRUE(
309       send_buffer_.WriteStreamData(1024 + 512, 3840 - 1024 - 512, &writer));
310 
311   // Last offset is end offset of last slice.
312   EXPECT_EQ(3840u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
313   QuicUniqueBufferPtr buffer = MakeUniqueBuffer(&allocator_, 60);
314   memset(buffer.get(), 'e', 60);
315   QuicMemSlice slice(std::move(buffer), 60);
316   send_buffer_.SaveMemSlice(std::move(slice));
317 
318   EXPECT_EQ(3840u, QuicStreamSendBufferPeer::EndOffset(&send_buffer_));
319 }
320 
TEST_F(QuicStreamSendBufferTest,SaveMemSliceSpan)321 TEST_F(QuicStreamSendBufferTest, SaveMemSliceSpan) {
322   SimpleBufferAllocator allocator;
323   QuicStreamSendBuffer send_buffer(&allocator);
324 
325   char data[1024];
326   std::vector<std::pair<char*, size_t>> buffers;
327   for (size_t i = 0; i < 10; ++i) {
328     buffers.push_back(std::make_pair(data, 1024));
329   }
330   QuicTestMemSliceVector vector(buffers);
331 
332   EXPECT_EQ(10 * 1024u, send_buffer.SaveMemSliceSpan(vector.span()));
333   EXPECT_EQ(10u, send_buffer.size());
334 }
335 
TEST_F(QuicStreamSendBufferTest,SaveEmptyMemSliceSpan)336 TEST_F(QuicStreamSendBufferTest, SaveEmptyMemSliceSpan) {
337   SimpleBufferAllocator allocator;
338   QuicStreamSendBuffer send_buffer(&allocator);
339 
340   char data[1024];
341   std::vector<std::pair<char*, size_t>> buffers;
342   for (size_t i = 0; i < 10; ++i) {
343     buffers.push_back(std::make_pair(data, 1024));
344   }
345   buffers.push_back(std::make_pair(nullptr, 0));
346   QuicTestMemSliceVector vector(buffers);
347 
348   EXPECT_EQ(10 * 1024u, send_buffer.SaveMemSliceSpan(vector.span()));
349   // Verify the empty slice does not get saved.
350   EXPECT_EQ(10u, send_buffer.size());
351 }
352 
353 }  // namespace
354 }  // namespace test
355 }  // namespace quic
356