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