1 /*
2 * Copyright (c) 2012 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "modules/rtp_rtcp/source/rtp_packet_history.h"
12
13 #include <memory>
14 #include <utility>
15
16 #include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
17 #include "modules/rtp_rtcp/source/rtp_packet_to_send.h"
18 #include "system_wrappers/include/clock.h"
19 #include "test/gmock.h"
20 #include "test/gtest.h"
21
22 namespace webrtc {
23 namespace {
24 // Set a high sequence number so we'll suffer a wrap-around.
25 constexpr uint16_t kStartSeqNum = 65534u;
26
27 // Utility method for truncating sequence numbers to uint16.
To16u(size_t sequence_number)28 uint16_t To16u(size_t sequence_number) {
29 return static_cast<uint16_t>(sequence_number & 0xFFFF);
30 }
31 } // namespace
32
33 using StorageMode = RtpPacketHistory::StorageMode;
34
35 class RtpPacketHistoryTest : public ::testing::TestWithParam<bool> {
36 protected:
RtpPacketHistoryTest()37 RtpPacketHistoryTest()
38 : fake_clock_(123456),
39 hist_(&fake_clock_, /*enable_padding_prio=*/GetParam()) {}
40
41 SimulatedClock fake_clock_;
42 RtpPacketHistory hist_;
43
CreateRtpPacket(uint16_t seq_num)44 std::unique_ptr<RtpPacketToSend> CreateRtpPacket(uint16_t seq_num) {
45 // Payload, ssrc, timestamp and extensions are irrelevant for this tests.
46 std::unique_ptr<RtpPacketToSend> packet(new RtpPacketToSend(nullptr));
47 packet->SetSequenceNumber(seq_num);
48 packet->set_capture_time_ms(fake_clock_.TimeInMilliseconds());
49 packet->set_allow_retransmission(true);
50 return packet;
51 }
52 };
53
TEST_P(RtpPacketHistoryTest,SetStoreStatus)54 TEST_P(RtpPacketHistoryTest, SetStoreStatus) {
55 EXPECT_EQ(StorageMode::kDisabled, hist_.GetStorageMode());
56 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
57 EXPECT_EQ(StorageMode::kStoreAndCull, hist_.GetStorageMode());
58 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
59 EXPECT_EQ(StorageMode::kStoreAndCull, hist_.GetStorageMode());
60 hist_.SetStorePacketsStatus(StorageMode::kDisabled, 0);
61 EXPECT_EQ(StorageMode::kDisabled, hist_.GetStorageMode());
62 }
63
TEST_P(RtpPacketHistoryTest,ClearsHistoryAfterSetStoreStatus)64 TEST_P(RtpPacketHistoryTest, ClearsHistoryAfterSetStoreStatus) {
65 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
66 // Store a packet, but with send-time. It should then not be removed.
67 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum), absl::nullopt);
68 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
69
70 // Changing store status, even to the current one, will clear the history.
71 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
72 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
73 }
74
TEST_P(RtpPacketHistoryTest,StartSeqResetAfterReset)75 TEST_P(RtpPacketHistoryTest, StartSeqResetAfterReset) {
76 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
77 // Store a packet, but with send-time. It should then not be removed.
78 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum), absl::nullopt);
79 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
80
81 // Changing store status, to clear the history.
82 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
83 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
84
85 // Add a new packet.
86 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + 1)), absl::nullopt);
87 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 1)));
88
89 // Advance time past where packet expires.
90 fake_clock_.AdvanceTimeMilliseconds(
91 RtpPacketHistory::kPacketCullingDelayFactor *
92 RtpPacketHistory::kMinPacketDurationMs);
93
94 // Add one more packet and verify no state left from packet before reset.
95 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + 2)), absl::nullopt);
96 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
97 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 1)));
98 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 2)));
99 }
100
TEST_P(RtpPacketHistoryTest,NoStoreStatus)101 TEST_P(RtpPacketHistoryTest, NoStoreStatus) {
102 EXPECT_EQ(StorageMode::kDisabled, hist_.GetStorageMode());
103 std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
104 hist_.PutRtpPacket(std::move(packet), absl::nullopt);
105 // Packet should not be stored.
106 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
107 }
108
TEST_P(RtpPacketHistoryTest,GetRtpPacket_NotStored)109 TEST_P(RtpPacketHistoryTest, GetRtpPacket_NotStored) {
110 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
111 EXPECT_FALSE(hist_.GetPacketState(0));
112 }
113
TEST_P(RtpPacketHistoryTest,PutRtpPacket)114 TEST_P(RtpPacketHistoryTest, PutRtpPacket) {
115 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
116 std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
117
118 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
119 hist_.PutRtpPacket(std::move(packet), absl::nullopt);
120 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
121 }
122
TEST_P(RtpPacketHistoryTest,GetRtpPacket)123 TEST_P(RtpPacketHistoryTest, GetRtpPacket) {
124 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
125 int64_t capture_time_ms = 1;
126 std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
127 packet->set_capture_time_ms(capture_time_ms);
128 rtc::CopyOnWriteBuffer buffer = packet->Buffer();
129 hist_.PutRtpPacket(std::move(packet), absl::nullopt);
130
131 std::unique_ptr<RtpPacketToSend> packet_out =
132 hist_.GetPacketAndSetSendTime(kStartSeqNum);
133 EXPECT_TRUE(packet_out);
134 EXPECT_EQ(buffer, packet_out->Buffer());
135 EXPECT_EQ(capture_time_ms, packet_out->capture_time_ms());
136 }
137
TEST_P(RtpPacketHistoryTest,PacketStateIsCorrect)138 TEST_P(RtpPacketHistoryTest, PacketStateIsCorrect) {
139 const uint32_t kSsrc = 92384762;
140 const int64_t kRttMs = 100;
141 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
142 hist_.SetRtt(kRttMs);
143 std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
144 packet->SetSsrc(kSsrc);
145 packet->SetPayloadSize(1234);
146 const size_t packet_size = packet->size();
147
148 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
149
150 absl::optional<RtpPacketHistory::PacketState> state =
151 hist_.GetPacketState(kStartSeqNum);
152 ASSERT_TRUE(state);
153 EXPECT_EQ(state->rtp_sequence_number, kStartSeqNum);
154 EXPECT_EQ(state->send_time_ms, fake_clock_.TimeInMilliseconds());
155 EXPECT_EQ(state->capture_time_ms, fake_clock_.TimeInMilliseconds());
156 EXPECT_EQ(state->ssrc, kSsrc);
157 EXPECT_EQ(state->packet_size, packet_size);
158 EXPECT_EQ(state->times_retransmitted, 0u);
159
160 fake_clock_.AdvanceTimeMilliseconds(1);
161 EXPECT_TRUE(hist_.GetPacketAndSetSendTime(kStartSeqNum));
162 fake_clock_.AdvanceTimeMilliseconds(kRttMs + 1);
163
164 state = hist_.GetPacketState(kStartSeqNum);
165 ASSERT_TRUE(state);
166 EXPECT_EQ(state->times_retransmitted, 1u);
167 }
168
TEST_P(RtpPacketHistoryTest,MinResendTimeWithPacer)169 TEST_P(RtpPacketHistoryTest, MinResendTimeWithPacer) {
170 static const int64_t kMinRetransmitIntervalMs = 100;
171
172 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
173 hist_.SetRtt(kMinRetransmitIntervalMs);
174 int64_t capture_time_ms = fake_clock_.TimeInMilliseconds();
175 std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
176 size_t len = packet->size();
177 hist_.PutRtpPacket(std::move(packet), absl::nullopt);
178
179 // First transmission: TimeToSendPacket() call from pacer.
180 EXPECT_TRUE(hist_.GetPacketAndSetSendTime(kStartSeqNum));
181
182 // First retransmission - allow early retransmission.
183 fake_clock_.AdvanceTimeMilliseconds(1);
184
185 // With pacer there's two calls to history:
186 // 1) When the NACK request arrived, use GetPacketState() to see if the
187 // packet is there and verify RTT constraints. Then we use the ssrc
188 // and sequence number to enqueue the retransmission in the pacer
189 // 2) When the pacer determines that it is time to send the packet, it calls
190 // GetPacketAndSetSendTime().
191 absl::optional<RtpPacketHistory::PacketState> packet_state =
192 hist_.GetPacketState(kStartSeqNum);
193 EXPECT_TRUE(packet_state);
194 EXPECT_EQ(len, packet_state->packet_size);
195 EXPECT_EQ(capture_time_ms, packet_state->capture_time_ms);
196
197 // Retransmission was allowed, next send it from pacer.
198 EXPECT_TRUE(hist_.GetPacketAndSetSendTime(kStartSeqNum));
199
200 // Second retransmission - advance time to just before retransmission OK.
201 fake_clock_.AdvanceTimeMilliseconds(kMinRetransmitIntervalMs - 1);
202 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
203
204 // Advance time to just after retransmission OK.
205 fake_clock_.AdvanceTimeMilliseconds(1);
206 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
207 EXPECT_TRUE(hist_.GetPacketAndSetSendTime(kStartSeqNum));
208 }
209
TEST_P(RtpPacketHistoryTest,MinResendTimeWithoutPacer)210 TEST_P(RtpPacketHistoryTest, MinResendTimeWithoutPacer) {
211 static const int64_t kMinRetransmitIntervalMs = 100;
212
213 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
214 hist_.SetRtt(kMinRetransmitIntervalMs);
215 int64_t capture_time_ms = fake_clock_.TimeInMilliseconds();
216 std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
217 size_t len = packet->size();
218 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
219
220 // First retransmission - allow early retransmission.
221 fake_clock_.AdvanceTimeMilliseconds(1);
222 packet = hist_.GetPacketAndSetSendTime(kStartSeqNum);
223 EXPECT_TRUE(packet);
224 EXPECT_EQ(len, packet->size());
225 EXPECT_EQ(capture_time_ms, packet->capture_time_ms());
226
227 // Second retransmission - advance time to just before retransmission OK.
228 fake_clock_.AdvanceTimeMilliseconds(kMinRetransmitIntervalMs - 1);
229 EXPECT_FALSE(hist_.GetPacketAndSetSendTime(kStartSeqNum));
230
231 // Advance time to just after retransmission OK.
232 fake_clock_.AdvanceTimeMilliseconds(1);
233 EXPECT_TRUE(hist_.GetPacketAndSetSendTime(kStartSeqNum));
234 }
235
TEST_P(RtpPacketHistoryTest,RemovesOldestSentPacketWhenAtMaxSize)236 TEST_P(RtpPacketHistoryTest, RemovesOldestSentPacketWhenAtMaxSize) {
237 const size_t kMaxNumPackets = 10;
238 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, kMaxNumPackets);
239
240 // History does not allow removing packets within kMinPacketDurationMs,
241 // so in order to test capacity, make sure insertion spans this time.
242 const int64_t kPacketIntervalMs =
243 RtpPacketHistory::kMinPacketDurationMs / kMaxNumPackets;
244
245 // Add packets until the buffer is full.
246 for (size_t i = 0; i < kMaxNumPackets; ++i) {
247 std::unique_ptr<RtpPacketToSend> packet =
248 CreateRtpPacket(To16u(kStartSeqNum + i));
249 // Immediate mark packet as sent.
250 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
251 fake_clock_.AdvanceTimeMilliseconds(kPacketIntervalMs);
252 }
253
254 // First packet should still be there.
255 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
256
257 // History is full, oldest one should be overwritten.
258 std::unique_ptr<RtpPacketToSend> packet =
259 CreateRtpPacket(To16u(kStartSeqNum + kMaxNumPackets));
260 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
261
262 // Oldest packet should be gone, but packet after than one still present.
263 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
264 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 1)));
265 }
266
TEST_P(RtpPacketHistoryTest,RemovesOldestPacketWhenAtMaxCapacity)267 TEST_P(RtpPacketHistoryTest, RemovesOldestPacketWhenAtMaxCapacity) {
268 // Tests the absolute upper bound on number of stored packets. Don't allow
269 // storing more than this, even if packets have not yet been sent.
270 const size_t kMaxNumPackets = RtpPacketHistory::kMaxCapacity;
271 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull,
272 RtpPacketHistory::kMaxCapacity);
273
274 // Add packets until the buffer is full.
275 for (size_t i = 0; i < kMaxNumPackets; ++i) {
276 std::unique_ptr<RtpPacketToSend> packet =
277 CreateRtpPacket(To16u(kStartSeqNum + i));
278 // Don't mark packets as sent, preventing them from being removed.
279 hist_.PutRtpPacket(std::move(packet), absl::nullopt);
280 }
281
282 // First packet should still be there.
283 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
284
285 // History is full, oldest one should be overwritten.
286 std::unique_ptr<RtpPacketToSend> packet =
287 CreateRtpPacket(To16u(kStartSeqNum + kMaxNumPackets));
288 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
289
290 // Oldest packet should be gone, but packet after than one still present.
291 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
292 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 1)));
293 }
294
TEST_P(RtpPacketHistoryTest,RemovesLowestPrioPaddingWhenAtMaxCapacity)295 TEST_P(RtpPacketHistoryTest, RemovesLowestPrioPaddingWhenAtMaxCapacity) {
296 if (!GetParam()) {
297 // Padding prioritization is off, ignore this test.
298 return;
299 }
300
301 // Tests the absolute upper bound on number of packets in the prioritized
302 // set of potential padding packets.
303 const size_t kMaxNumPackets = RtpPacketHistory::kMaxPaddingtHistory;
304 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, kMaxNumPackets * 2);
305 hist_.SetRtt(1);
306
307 // Add packets until the max is reached, and then yet another one.
308 for (size_t i = 0; i < kMaxNumPackets + 1; ++i) {
309 std::unique_ptr<RtpPacketToSend> packet =
310 CreateRtpPacket(To16u(kStartSeqNum + i));
311 // Don't mark packets as sent, preventing them from being removed.
312 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
313 }
314
315 // Advance time to allow retransmission/padding.
316 fake_clock_.AdvanceTimeMilliseconds(1);
317
318 // The oldest packet will be least prioritized and has fallen out of the
319 // priority set.
320 for (size_t i = kMaxNumPackets - 1; i > 0; --i) {
321 auto packet = hist_.GetPayloadPaddingPacket();
322 ASSERT_TRUE(packet);
323 EXPECT_EQ(packet->SequenceNumber(), To16u(kStartSeqNum + i + 1));
324 }
325
326 // Wrap around to newest padding packet again.
327 auto packet = hist_.GetPayloadPaddingPacket();
328 ASSERT_TRUE(packet);
329 EXPECT_EQ(packet->SequenceNumber(), To16u(kStartSeqNum + kMaxNumPackets));
330 }
331
TEST_P(RtpPacketHistoryTest,DontRemoveUnsentPackets)332 TEST_P(RtpPacketHistoryTest, DontRemoveUnsentPackets) {
333 const size_t kMaxNumPackets = 10;
334 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, kMaxNumPackets);
335
336 // Add packets until the buffer is full.
337 for (size_t i = 0; i < kMaxNumPackets; ++i) {
338 // Mark packets as unsent.
339 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + i)), absl::nullopt);
340 }
341 fake_clock_.AdvanceTimeMilliseconds(RtpPacketHistory::kMinPacketDurationMs);
342
343 // First packet should still be there.
344 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
345
346 // History is full, but old packets not sent, so allow expansion.
347 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + kMaxNumPackets)),
348 fake_clock_.TimeInMilliseconds());
349 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
350
351 // Set all packet as sent and advance time past min packet duration time,
352 // otherwise packets till still be prevented from being removed.
353 for (size_t i = 0; i <= kMaxNumPackets; ++i) {
354 EXPECT_TRUE(hist_.GetPacketAndSetSendTime(To16u(kStartSeqNum + i)));
355 }
356 fake_clock_.AdvanceTimeMilliseconds(RtpPacketHistory::kMinPacketDurationMs);
357 // Add a new packet, this means the two oldest ones will be culled.
358 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + kMaxNumPackets + 1)),
359 fake_clock_.TimeInMilliseconds());
360 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
361 EXPECT_FALSE(hist_.GetPacketState(To16u(kStartSeqNum + 1)));
362 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 2)));
363 }
364
TEST_P(RtpPacketHistoryTest,DontRemoveTooRecentlyTransmittedPackets)365 TEST_P(RtpPacketHistoryTest, DontRemoveTooRecentlyTransmittedPackets) {
366 // Set size to remove old packets as soon as possible.
367 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
368
369 // Add a packet, marked as send, and advance time to just before removal time.
370 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
371 fake_clock_.TimeInMilliseconds());
372 fake_clock_.AdvanceTimeMilliseconds(RtpPacketHistory::kMinPacketDurationMs -
373 1);
374
375 // Add a new packet to trigger culling.
376 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + 1)),
377 fake_clock_.TimeInMilliseconds());
378 // First packet should still be there.
379 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
380
381 // Advance time to where packet will be eligible for removal and try again.
382 fake_clock_.AdvanceTimeMilliseconds(1);
383 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + 2)),
384 fake_clock_.TimeInMilliseconds());
385 // First packet should no be gone, but next one still there.
386 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
387 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 1)));
388 }
389
TEST_P(RtpPacketHistoryTest,DontRemoveTooRecentlyTransmittedPacketsHighRtt)390 TEST_P(RtpPacketHistoryTest, DontRemoveTooRecentlyTransmittedPacketsHighRtt) {
391 const int64_t kRttMs = RtpPacketHistory::kMinPacketDurationMs * 2;
392 const int64_t kPacketTimeoutMs =
393 kRttMs * RtpPacketHistory::kMinPacketDurationRtt;
394
395 // Set size to remove old packets as soon as possible.
396 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
397 hist_.SetRtt(kRttMs);
398
399 // Add a packet, marked as send, and advance time to just before removal time.
400 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
401 fake_clock_.TimeInMilliseconds());
402 fake_clock_.AdvanceTimeMilliseconds(kPacketTimeoutMs - 1);
403
404 // Add a new packet to trigger culling.
405 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + 1)),
406 fake_clock_.TimeInMilliseconds());
407 // First packet should still be there.
408 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
409
410 // Advance time to where packet will be eligible for removal and try again.
411 fake_clock_.AdvanceTimeMilliseconds(1);
412 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + 2)),
413 fake_clock_.TimeInMilliseconds());
414 // First packet should no be gone, but next one still there.
415 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
416 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 1)));
417 }
418
TEST_P(RtpPacketHistoryTest,RemovesOldWithCulling)419 TEST_P(RtpPacketHistoryTest, RemovesOldWithCulling) {
420 const size_t kMaxNumPackets = 10;
421 // Enable culling. Even without feedback, this can trigger early removal.
422 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, kMaxNumPackets);
423
424 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
425 fake_clock_.TimeInMilliseconds());
426
427 int64_t kMaxPacketDurationMs = RtpPacketHistory::kMinPacketDurationMs *
428 RtpPacketHistory::kPacketCullingDelayFactor;
429 fake_clock_.AdvanceTimeMilliseconds(kMaxPacketDurationMs - 1);
430
431 // First packet should still be there.
432 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
433
434 // Advance to where packet can be culled, even if buffer is not full.
435 fake_clock_.AdvanceTimeMilliseconds(1);
436 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + 1)),
437 fake_clock_.TimeInMilliseconds());
438
439 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
440 }
441
TEST_P(RtpPacketHistoryTest,RemovesOldWithCullingHighRtt)442 TEST_P(RtpPacketHistoryTest, RemovesOldWithCullingHighRtt) {
443 const size_t kMaxNumPackets = 10;
444 const int64_t kRttMs = RtpPacketHistory::kMinPacketDurationMs * 2;
445 // Enable culling. Even without feedback, this can trigger early removal.
446 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, kMaxNumPackets);
447 hist_.SetRtt(kRttMs);
448
449 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
450 fake_clock_.TimeInMilliseconds());
451
452 int64_t kMaxPacketDurationMs = kRttMs *
453 RtpPacketHistory::kMinPacketDurationRtt *
454 RtpPacketHistory::kPacketCullingDelayFactor;
455 fake_clock_.AdvanceTimeMilliseconds(kMaxPacketDurationMs - 1);
456
457 // First packet should still be there.
458 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum));
459
460 // Advance to where packet can be culled, even if buffer is not full.
461 fake_clock_.AdvanceTimeMilliseconds(1);
462 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + 1)),
463 fake_clock_.TimeInMilliseconds());
464
465 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum));
466 }
467
TEST_P(RtpPacketHistoryTest,CullWithAcks)468 TEST_P(RtpPacketHistoryTest, CullWithAcks) {
469 const int64_t kPacketLifetime = RtpPacketHistory::kMinPacketDurationMs *
470 RtpPacketHistory::kPacketCullingDelayFactor;
471
472 const int64_t start_time = fake_clock_.TimeInMilliseconds();
473 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
474
475 // Insert three packets 33ms apart, immediately mark them as sent.
476 std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
477 packet->SetPayloadSize(50);
478 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
479 hist_.GetPacketAndSetSendTime(kStartSeqNum);
480 fake_clock_.AdvanceTimeMilliseconds(33);
481 packet = CreateRtpPacket(To16u(kStartSeqNum + 1));
482 packet->SetPayloadSize(50);
483 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
484 hist_.GetPacketAndSetSendTime(To16u(kStartSeqNum + 1));
485 fake_clock_.AdvanceTimeMilliseconds(33);
486 packet = CreateRtpPacket(To16u(kStartSeqNum + 2));
487 packet->SetPayloadSize(50);
488 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
489 hist_.GetPacketAndSetSendTime(To16u(kStartSeqNum + 2));
490
491 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum).has_value());
492 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 1)).has_value());
493 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 2)).has_value());
494
495 // Remove middle one using ack, check that only that one is gone.
496 std::vector<uint16_t> acked_sequence_numbers = {To16u(kStartSeqNum + 1)};
497 hist_.CullAcknowledgedPackets(acked_sequence_numbers);
498
499 EXPECT_TRUE(hist_.GetPacketState(kStartSeqNum).has_value());
500 EXPECT_FALSE(hist_.GetPacketState(To16u(kStartSeqNum + 1)).has_value());
501 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 2)).has_value());
502
503 // Advance time to where second packet would have expired, verify first packet
504 // is removed.
505 int64_t second_packet_expiry_time = start_time + kPacketLifetime + 33 + 1;
506 fake_clock_.AdvanceTimeMilliseconds(second_packet_expiry_time -
507 fake_clock_.TimeInMilliseconds());
508 hist_.SetRtt(1); // Trigger culling of old packets.
509 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum).has_value());
510 EXPECT_FALSE(hist_.GetPacketState(To16u(kStartSeqNum + 1)).has_value());
511 EXPECT_TRUE(hist_.GetPacketState(To16u(kStartSeqNum + 2)).has_value());
512
513 // Advance to where last packet expires, verify all gone.
514 fake_clock_.AdvanceTimeMilliseconds(33);
515 hist_.SetRtt(1); // Trigger culling of old packets.
516 EXPECT_FALSE(hist_.GetPacketState(kStartSeqNum).has_value());
517 EXPECT_FALSE(hist_.GetPacketState(To16u(kStartSeqNum + 1)).has_value());
518 EXPECT_FALSE(hist_.GetPacketState(To16u(kStartSeqNum + 2)).has_value());
519 }
520
TEST_P(RtpPacketHistoryTest,SetsPendingTransmissionState)521 TEST_P(RtpPacketHistoryTest, SetsPendingTransmissionState) {
522 const int64_t kRttMs = RtpPacketHistory::kMinPacketDurationMs * 2;
523 hist_.SetRtt(kRttMs);
524
525 // Set size to remove old packets as soon as possible.
526 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
527
528 // Add a packet, without send time, indicating it's in pacer queue.
529 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
530 /* send_time_ms = */ absl::nullopt);
531
532 // Packet is pending transmission.
533 absl::optional<RtpPacketHistory::PacketState> packet_state =
534 hist_.GetPacketState(kStartSeqNum);
535 ASSERT_TRUE(packet_state.has_value());
536 EXPECT_TRUE(packet_state->pending_transmission);
537
538 // Packet sent, state should be back to non-pending.
539 EXPECT_TRUE(hist_.GetPacketAndSetSendTime(kStartSeqNum));
540 packet_state = hist_.GetPacketState(kStartSeqNum);
541 ASSERT_TRUE(packet_state.has_value());
542 EXPECT_FALSE(packet_state->pending_transmission);
543
544 // Time for a retransmission.
545 fake_clock_.AdvanceTimeMilliseconds(kRttMs);
546 EXPECT_TRUE(hist_.SetPendingTransmission(kStartSeqNum));
547 packet_state = hist_.GetPacketState(kStartSeqNum);
548 ASSERT_TRUE(packet_state.has_value());
549 EXPECT_TRUE(packet_state->pending_transmission);
550
551 // Packet sent.
552 EXPECT_TRUE(hist_.GetPacketAndSetSendTime(kStartSeqNum));
553 // Too early for retransmission.
554 ASSERT_FALSE(hist_.GetPacketState(kStartSeqNum).has_value());
555
556 // Retransmission allowed again, it's not in a pending state.
557 fake_clock_.AdvanceTimeMilliseconds(kRttMs);
558 packet_state = hist_.GetPacketState(kStartSeqNum);
559 ASSERT_TRUE(packet_state.has_value());
560 EXPECT_FALSE(packet_state->pending_transmission);
561 }
562
TEST_P(RtpPacketHistoryTest,GetPacketAndSetSent)563 TEST_P(RtpPacketHistoryTest, GetPacketAndSetSent) {
564 const int64_t kRttMs = RtpPacketHistory::kMinPacketDurationMs * 2;
565 hist_.SetRtt(kRttMs);
566
567 // Set size to remove old packets as soon as possible.
568 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
569
570 // Add a sent packet to the history.
571 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
572 fake_clock_.TimeInMicroseconds());
573
574 // Retransmission request, first retransmission is allowed immediately.
575 EXPECT_TRUE(hist_.GetPacketAndMarkAsPending(kStartSeqNum));
576
577 // Packet not yet sent, new retransmission not allowed.
578 fake_clock_.AdvanceTimeMilliseconds(kRttMs);
579 EXPECT_FALSE(hist_.GetPacketAndMarkAsPending(kStartSeqNum));
580
581 // Mark as sent, but too early for retransmission.
582 hist_.MarkPacketAsSent(kStartSeqNum);
583 EXPECT_FALSE(hist_.GetPacketAndMarkAsPending(kStartSeqNum));
584
585 // Enough time has passed, retransmission is allowed again.
586 fake_clock_.AdvanceTimeMilliseconds(kRttMs);
587 EXPECT_TRUE(hist_.GetPacketAndMarkAsPending(kStartSeqNum));
588 }
589
TEST_P(RtpPacketHistoryTest,GetPacketWithEncapsulation)590 TEST_P(RtpPacketHistoryTest, GetPacketWithEncapsulation) {
591 const uint32_t kSsrc = 92384762;
592 const int64_t kRttMs = RtpPacketHistory::kMinPacketDurationMs * 2;
593 hist_.SetRtt(kRttMs);
594
595 // Set size to remove old packets as soon as possible.
596 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
597
598 // Add a sent packet to the history, with a set SSRC.
599 std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(kStartSeqNum);
600 packet->SetSsrc(kSsrc);
601 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMicroseconds());
602
603 // Retransmission request, simulate an RTX-like encapsulation, were the packet
604 // is sent on a different SSRC.
605 std::unique_ptr<RtpPacketToSend> retransmit_packet =
606 hist_.GetPacketAndMarkAsPending(
607 kStartSeqNum, [](const RtpPacketToSend& packet) {
608 auto encapsulated_packet =
609 std::make_unique<RtpPacketToSend>(packet);
610 encapsulated_packet->SetSsrc(packet.Ssrc() + 1);
611 return encapsulated_packet;
612 });
613 ASSERT_TRUE(retransmit_packet);
614 EXPECT_EQ(retransmit_packet->Ssrc(), kSsrc + 1);
615 }
616
TEST_P(RtpPacketHistoryTest,GetPacketWithEncapsulationAbortOnNullptr)617 TEST_P(RtpPacketHistoryTest, GetPacketWithEncapsulationAbortOnNullptr) {
618 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
619
620 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
621 fake_clock_.TimeInMicroseconds());
622
623 // Retransmission request, but the encapsulator determines that this packet is
624 // not suitable for retransmission (bandwidth exhausted?) so the retransmit is
625 // aborted and the packet is not marked as pending.
626 EXPECT_FALSE(hist_.GetPacketAndMarkAsPending(
627 kStartSeqNum, [](const RtpPacketToSend&) { return nullptr; }));
628
629 // New try, this time getting the packet should work, and it should not be
630 // blocked due to any pending status.
631 EXPECT_TRUE(hist_.GetPacketAndMarkAsPending(kStartSeqNum));
632 }
633
TEST_P(RtpPacketHistoryTest,DontRemovePendingTransmissions)634 TEST_P(RtpPacketHistoryTest, DontRemovePendingTransmissions) {
635 const int64_t kRttMs = RtpPacketHistory::kMinPacketDurationMs * 2;
636 const int64_t kPacketTimeoutMs =
637 kRttMs * RtpPacketHistory::kMinPacketDurationRtt;
638
639 // Set size to remove old packets as soon as possible.
640 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
641 hist_.SetRtt(kRttMs);
642
643 // Add a sent packet.
644 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
645 fake_clock_.TimeInMilliseconds());
646
647 // Advance clock to just before packet timeout.
648 fake_clock_.AdvanceTimeMilliseconds(kPacketTimeoutMs - 1);
649 // Mark as enqueued in pacer.
650 EXPECT_TRUE(hist_.SetPendingTransmission(kStartSeqNum));
651
652 // Advance clock to where packet would have timed out. It should still
653 // be there and pending.
654 fake_clock_.AdvanceTimeMilliseconds(1);
655 absl::optional<RtpPacketHistory::PacketState> packet_state =
656 hist_.GetPacketState(kStartSeqNum);
657 ASSERT_TRUE(packet_state.has_value());
658 EXPECT_TRUE(packet_state->pending_transmission);
659
660 // Packet sent. Now it can be removed.
661 EXPECT_TRUE(hist_.GetPacketAndSetSendTime(kStartSeqNum));
662 hist_.SetRtt(kRttMs); // Force culling of old packets.
663 packet_state = hist_.GetPacketState(kStartSeqNum);
664 ASSERT_FALSE(packet_state.has_value());
665 }
666
TEST_P(RtpPacketHistoryTest,PrioritizedPayloadPadding)667 TEST_P(RtpPacketHistoryTest, PrioritizedPayloadPadding) {
668 if (!GetParam()) {
669 // Padding prioritization is off, ignore this test.
670 return;
671 }
672
673 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
674
675 // Add two sent packets, one millisecond apart.
676 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
677 fake_clock_.TimeInMilliseconds());
678 fake_clock_.AdvanceTimeMilliseconds(1);
679
680 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum + 1),
681 fake_clock_.TimeInMilliseconds());
682 fake_clock_.AdvanceTimeMilliseconds(1);
683
684 // Latest packet given equal retransmission count.
685 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(),
686 kStartSeqNum + 1);
687
688 // Older packet has lower retransmission count.
689 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(), kStartSeqNum);
690
691 // Equal retransmission count again, use newest packet.
692 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(),
693 kStartSeqNum + 1);
694
695 // Older packet has lower retransmission count.
696 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(), kStartSeqNum);
697
698 // Remove newest packet.
699 hist_.CullAcknowledgedPackets(std::vector<uint16_t>{kStartSeqNum + 1});
700
701 // Only older packet left.
702 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(), kStartSeqNum);
703
704 hist_.CullAcknowledgedPackets(std::vector<uint16_t>{kStartSeqNum});
705
706 EXPECT_EQ(hist_.GetPayloadPaddingPacket(), nullptr);
707 }
708
TEST_P(RtpPacketHistoryTest,NoPendingPacketAsPadding)709 TEST_P(RtpPacketHistoryTest, NoPendingPacketAsPadding) {
710 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
711
712 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
713 fake_clock_.TimeInMilliseconds());
714 fake_clock_.AdvanceTimeMilliseconds(1);
715
716 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(), kStartSeqNum);
717
718 // If packet is pending retransmission, don't try to use it as padding.
719 hist_.SetPendingTransmission(kStartSeqNum);
720 EXPECT_EQ(nullptr, hist_.GetPayloadPaddingPacket());
721
722 // Market it as no longer pending, should be usable as padding again.
723 hist_.GetPacketAndSetSendTime(kStartSeqNum);
724 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(), kStartSeqNum);
725 }
726
TEST_P(RtpPacketHistoryTest,PayloadPaddingWithEncapsulation)727 TEST_P(RtpPacketHistoryTest, PayloadPaddingWithEncapsulation) {
728 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 1);
729
730 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
731 fake_clock_.TimeInMilliseconds());
732 fake_clock_.AdvanceTimeMilliseconds(1);
733
734 // Aborted padding.
735 EXPECT_EQ(nullptr, hist_.GetPayloadPaddingPacket(
736 [](const RtpPacketToSend&) { return nullptr; }));
737
738 // Get copy of packet, but with sequence number modified.
739 auto padding_packet =
740 hist_.GetPayloadPaddingPacket([&](const RtpPacketToSend& packet) {
741 auto encapsulated_packet = std::make_unique<RtpPacketToSend>(packet);
742 encapsulated_packet->SetSequenceNumber(kStartSeqNum + 1);
743 return encapsulated_packet;
744 });
745 ASSERT_TRUE(padding_packet);
746 EXPECT_EQ(padding_packet->SequenceNumber(), kStartSeqNum + 1);
747 }
748
TEST_P(RtpPacketHistoryTest,NackAfterAckIsNoop)749 TEST_P(RtpPacketHistoryTest, NackAfterAckIsNoop) {
750 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 2);
751 // Add two sent packets.
752 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum),
753 fake_clock_.TimeInMilliseconds());
754 hist_.PutRtpPacket(CreateRtpPacket(kStartSeqNum + 1),
755 fake_clock_.TimeInMilliseconds());
756 // Remove newest one.
757 hist_.CullAcknowledgedPackets(std::vector<uint16_t>{kStartSeqNum + 1});
758 // Retransmission request for already acked packet, should be noop.
759 auto packet = hist_.GetPacketAndMarkAsPending(kStartSeqNum + 1);
760 EXPECT_EQ(packet.get(), nullptr);
761 }
762
TEST_P(RtpPacketHistoryTest,OutOfOrderInsertRemoval)763 TEST_P(RtpPacketHistoryTest, OutOfOrderInsertRemoval) {
764 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, 10);
765
766 // Insert packets, out of order, including both forwards and backwards
767 // sequence number wraps.
768 const int seq_offsets[] = {0, 1, -1, 2, -2, 3, -3};
769 const int64_t start_time_ms = fake_clock_.TimeInMilliseconds();
770
771 for (int offset : seq_offsets) {
772 uint16_t seq_no = To16u(kStartSeqNum + offset);
773 std::unique_ptr<RtpPacketToSend> packet = CreateRtpPacket(seq_no);
774 packet->SetPayloadSize(50);
775 hist_.PutRtpPacket(std::move(packet), fake_clock_.TimeInMilliseconds());
776 hist_.GetPacketAndSetSendTime(seq_no);
777 fake_clock_.AdvanceTimeMilliseconds(33);
778 }
779
780 // Check packet are there and remove them in the same out-of-order fashion.
781 int64_t expected_time_offset_ms = 0;
782 for (int offset : seq_offsets) {
783 uint16_t seq_no = To16u(kStartSeqNum + offset);
784 absl::optional<RtpPacketHistory::PacketState> packet_state =
785 hist_.GetPacketState(seq_no);
786 ASSERT_TRUE(packet_state.has_value());
787 EXPECT_EQ(packet_state->send_time_ms,
788 start_time_ms + expected_time_offset_ms);
789 std::vector<uint16_t> acked_sequence_numbers = {seq_no};
790 hist_.CullAcknowledgedPackets(acked_sequence_numbers);
791 expected_time_offset_ms += 33;
792 }
793 }
794
TEST_P(RtpPacketHistoryTest,UsesLastPacketAsPaddingWithPrioOff)795 TEST_P(RtpPacketHistoryTest, UsesLastPacketAsPaddingWithPrioOff) {
796 if (GetParam()) {
797 // Padding prioritization is enabled, ignore this test.
798 return;
799 }
800
801 const size_t kHistorySize = 10;
802 hist_.SetStorePacketsStatus(StorageMode::kStoreAndCull, kHistorySize);
803
804 EXPECT_EQ(hist_.GetPayloadPaddingPacket(), nullptr);
805
806 for (size_t i = 0; i < kHistorySize; ++i) {
807 hist_.PutRtpPacket(CreateRtpPacket(To16u(kStartSeqNum + i)),
808 fake_clock_.TimeInMilliseconds());
809 hist_.MarkPacketAsSent(To16u(kStartSeqNum + i));
810 fake_clock_.AdvanceTimeMilliseconds(1);
811
812 // Last packet always returned.
813 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(),
814 To16u(kStartSeqNum + i));
815 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(),
816 To16u(kStartSeqNum + i));
817 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(),
818 To16u(kStartSeqNum + i));
819 }
820
821 // Remove packets from the end, last in the list should be returned.
822 for (size_t i = kHistorySize - 1; i > 0; --i) {
823 hist_.CullAcknowledgedPackets(
824 std::vector<uint16_t>{To16u(kStartSeqNum + i)});
825
826 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(),
827 To16u(kStartSeqNum + i - 1));
828 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(),
829 To16u(kStartSeqNum + i - 1));
830 EXPECT_EQ(hist_.GetPayloadPaddingPacket()->SequenceNumber(),
831 To16u(kStartSeqNum + i - 1));
832 }
833
834 hist_.CullAcknowledgedPackets(std::vector<uint16_t>{kStartSeqNum});
835 EXPECT_EQ(hist_.GetPayloadPaddingPacket(), nullptr);
836 }
837
838 INSTANTIATE_TEST_SUITE_P(WithAndWithoutPaddingPrio,
839 RtpPacketHistoryTest,
840 ::testing::Bool());
841 } // namespace webrtc
842