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