1 /*
2  *  Copyright (c) 2016 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/video_coding/deprecated/nack_module.h"
12 
13 #include <algorithm>
14 #include <cstdint>
15 #include <cstring>
16 #include <memory>
17 
18 #include "system_wrappers/include/clock.h"
19 #include "test/field_trial.h"
20 #include "test/gtest.h"
21 
22 namespace webrtc {
23 class TestNackModule : public ::testing::TestWithParam<bool>,
24                        public NackSender,
25                        public KeyFrameRequestSender {
26  protected:
TestNackModule()27   TestNackModule()
28       : clock_(new SimulatedClock(0)),
29         field_trial_(GetParam()
30                          ? "WebRTC-ExponentialNackBackoff/enabled:true/"
31                          : "WebRTC-ExponentialNackBackoff/enabled:false/"),
32         nack_module_(clock_.get(), this, this),
33         keyframes_requested_(0) {}
34 
SetUp()35   void SetUp() override { nack_module_.UpdateRtt(kDefaultRttMs); }
36 
SendNack(const std::vector<uint16_t> & sequence_numbers,bool buffering_allowed)37   void SendNack(const std::vector<uint16_t>& sequence_numbers,
38                 bool buffering_allowed) override {
39     sent_nacks_.insert(sent_nacks_.end(), sequence_numbers.begin(),
40                        sequence_numbers.end());
41   }
42 
RequestKeyFrame()43   void RequestKeyFrame() override { ++keyframes_requested_; }
44 
45   static constexpr int64_t kDefaultRttMs = 20;
46   std::unique_ptr<SimulatedClock> clock_;
47   test::ScopedFieldTrials field_trial_;
48   DEPRECATED_NackModule nack_module_;
49   std::vector<uint16_t> sent_nacks_;
50   int keyframes_requested_;
51 };
52 
TEST_P(TestNackModule,NackOnePacket)53 TEST_P(TestNackModule, NackOnePacket) {
54   nack_module_.OnReceivedPacket(1, false, false);
55   nack_module_.OnReceivedPacket(3, false, false);
56   EXPECT_EQ(1u, sent_nacks_.size());
57   EXPECT_EQ(2, sent_nacks_[0]);
58 }
59 
TEST_P(TestNackModule,WrappingSeqNum)60 TEST_P(TestNackModule, WrappingSeqNum) {
61   nack_module_.OnReceivedPacket(0xfffe, false, false);
62   nack_module_.OnReceivedPacket(1, false, false);
63   EXPECT_EQ(2u, sent_nacks_.size());
64   EXPECT_EQ(0xffff, sent_nacks_[0]);
65   EXPECT_EQ(0, sent_nacks_[1]);
66 }
67 
TEST_P(TestNackModule,WrappingSeqNumClearToKeyframe)68 TEST_P(TestNackModule, WrappingSeqNumClearToKeyframe) {
69   nack_module_.OnReceivedPacket(0xfffe, false, false);
70   nack_module_.OnReceivedPacket(1, false, false);
71   EXPECT_EQ(2u, sent_nacks_.size());
72   EXPECT_EQ(0xffff, sent_nacks_[0]);
73   EXPECT_EQ(0, sent_nacks_[1]);
74 
75   sent_nacks_.clear();
76   nack_module_.OnReceivedPacket(2, true, false);
77   EXPECT_EQ(0u, sent_nacks_.size());
78 
79   nack_module_.OnReceivedPacket(501, true, false);
80   EXPECT_EQ(498u, sent_nacks_.size());
81   for (int seq_num = 3; seq_num < 501; ++seq_num)
82     EXPECT_EQ(seq_num, sent_nacks_[seq_num - 3]);
83 
84   sent_nacks_.clear();
85   nack_module_.OnReceivedPacket(1001, false, false);
86   EXPECT_EQ(499u, sent_nacks_.size());
87   for (int seq_num = 502; seq_num < 1001; ++seq_num)
88     EXPECT_EQ(seq_num, sent_nacks_[seq_num - 502]);
89 
90   sent_nacks_.clear();
91   clock_->AdvanceTimeMilliseconds(100);
92   nack_module_.Process();
93   EXPECT_EQ(999u, sent_nacks_.size());
94   EXPECT_EQ(0xffff, sent_nacks_[0]);
95   EXPECT_EQ(0, sent_nacks_[1]);
96   for (int seq_num = 3; seq_num < 501; ++seq_num)
97     EXPECT_EQ(seq_num, sent_nacks_[seq_num - 1]);
98   for (int seq_num = 502; seq_num < 1001; ++seq_num)
99     EXPECT_EQ(seq_num, sent_nacks_[seq_num - 2]);
100 
101   // Adding packet 1004 will cause the nack list to reach it's max limit.
102   // It will then clear all nacks up to the next keyframe (seq num 2),
103   // thus removing 0xffff and 0 from the nack list.
104   sent_nacks_.clear();
105   nack_module_.OnReceivedPacket(1004, false, false);
106   EXPECT_EQ(2u, sent_nacks_.size());
107   EXPECT_EQ(1002, sent_nacks_[0]);
108   EXPECT_EQ(1003, sent_nacks_[1]);
109 
110   sent_nacks_.clear();
111   clock_->AdvanceTimeMilliseconds(100);
112   nack_module_.Process();
113   EXPECT_EQ(999u, sent_nacks_.size());
114   for (int seq_num = 3; seq_num < 501; ++seq_num)
115     EXPECT_EQ(seq_num, sent_nacks_[seq_num - 3]);
116   for (int seq_num = 502; seq_num < 1001; ++seq_num)
117     EXPECT_EQ(seq_num, sent_nacks_[seq_num - 4]);
118 
119   // Adding packet 1007 will cause the nack module to overflow again, thus
120   // clearing everything up to 501 which is the next keyframe.
121   nack_module_.OnReceivedPacket(1007, false, false);
122   sent_nacks_.clear();
123   clock_->AdvanceTimeMilliseconds(100);
124   nack_module_.Process();
125   EXPECT_EQ(503u, sent_nacks_.size());
126   for (int seq_num = 502; seq_num < 1001; ++seq_num)
127     EXPECT_EQ(seq_num, sent_nacks_[seq_num - 502]);
128   EXPECT_EQ(1005, sent_nacks_[501]);
129   EXPECT_EQ(1006, sent_nacks_[502]);
130 }
131 
TEST_P(TestNackModule,DontBurstOnTimeSkip)132 TEST_P(TestNackModule, DontBurstOnTimeSkip) {
133   nack_module_.Process();
134   clock_->AdvanceTimeMilliseconds(20);
135   EXPECT_EQ(0, nack_module_.TimeUntilNextProcess());
136   nack_module_.Process();
137 
138   clock_->AdvanceTimeMilliseconds(100);
139   EXPECT_EQ(0, nack_module_.TimeUntilNextProcess());
140   nack_module_.Process();
141   EXPECT_EQ(20, nack_module_.TimeUntilNextProcess());
142 
143   clock_->AdvanceTimeMilliseconds(19);
144   EXPECT_EQ(1, nack_module_.TimeUntilNextProcess());
145   clock_->AdvanceTimeMilliseconds(2);
146   nack_module_.Process();
147   EXPECT_EQ(19, nack_module_.TimeUntilNextProcess());
148 
149   clock_->AdvanceTimeMilliseconds(19);
150   EXPECT_EQ(0, nack_module_.TimeUntilNextProcess());
151   nack_module_.Process();
152 
153   clock_->AdvanceTimeMilliseconds(21);
154   EXPECT_EQ(0, nack_module_.TimeUntilNextProcess());
155   nack_module_.Process();
156   EXPECT_EQ(19, nack_module_.TimeUntilNextProcess());
157 }
158 
TEST_P(TestNackModule,ResendNack)159 TEST_P(TestNackModule, ResendNack) {
160   nack_module_.OnReceivedPacket(1, false, false);
161   nack_module_.OnReceivedPacket(3, false, false);
162   size_t expected_nacks_sent = 1;
163   EXPECT_EQ(expected_nacks_sent, sent_nacks_.size());
164   EXPECT_EQ(2, sent_nacks_[0]);
165 
166   if (GetParam()) {
167     // Retry has to wait at least 5ms by default.
168     nack_module_.UpdateRtt(1);
169     clock_->AdvanceTimeMilliseconds(4);
170     nack_module_.Process();  // Too early.
171     EXPECT_EQ(expected_nacks_sent, sent_nacks_.size());
172 
173     clock_->AdvanceTimeMilliseconds(1);
174     nack_module_.Process();  // Now allowed.
175     EXPECT_EQ(++expected_nacks_sent, sent_nacks_.size());
176   } else {
177     nack_module_.UpdateRtt(1);
178     clock_->AdvanceTimeMilliseconds(1);
179     nack_module_.Process();  // Fast retransmit allowed.
180     EXPECT_EQ(++expected_nacks_sent, sent_nacks_.size());
181   }
182 
183   // N:th try has to wait b^(N-1) * rtt by default.
184   const double b = GetParam() ? 1.25 : 1.0;
185   for (int i = 2; i < 10; ++i) {
186     // Change RTT, above the 40ms max for exponential backoff.
187     TimeDelta rtt = TimeDelta::Millis(160);  // + (i * 10 - 40)
188     nack_module_.UpdateRtt(rtt.ms());
189 
190     // RTT gets capped at 160ms in backoff calculations.
191     TimeDelta expected_backoff_delay =
192         std::pow(b, i - 1) * std::min(rtt, TimeDelta::Millis(160));
193 
194     // Move to one millisecond before next allowed NACK.
195     clock_->AdvanceTimeMilliseconds(expected_backoff_delay.ms() - 1);
196     nack_module_.Process();
197     EXPECT_EQ(expected_nacks_sent, sent_nacks_.size());
198 
199     // Move to one millisecond after next allowed NACK.
200     // After rather than on to avoid rounding errors.
201     clock_->AdvanceTimeMilliseconds(2);
202     nack_module_.Process();  // Now allowed.
203     EXPECT_EQ(++expected_nacks_sent, sent_nacks_.size());
204   }
205 
206   // Giving up after 10 tries.
207   clock_->AdvanceTimeMilliseconds(3000);
208   nack_module_.Process();
209   EXPECT_EQ(expected_nacks_sent, sent_nacks_.size());
210 }
211 
TEST_P(TestNackModule,ResendPacketMaxRetries)212 TEST_P(TestNackModule, ResendPacketMaxRetries) {
213   nack_module_.OnReceivedPacket(1, false, false);
214   nack_module_.OnReceivedPacket(3, false, false);
215   EXPECT_EQ(1u, sent_nacks_.size());
216   EXPECT_EQ(2, sent_nacks_[0]);
217 
218   int backoff_factor = 1;
219   for (size_t retries = 1; retries < 10; ++retries) {
220     // Exponential backoff, so that we don't reject NACK because of time.
221     clock_->AdvanceTimeMilliseconds(backoff_factor * kDefaultRttMs);
222     backoff_factor *= 2;
223     nack_module_.Process();
224     EXPECT_EQ(retries + 1, sent_nacks_.size());
225   }
226 
227   clock_->AdvanceTimeMilliseconds(backoff_factor * kDefaultRttMs);
228   nack_module_.Process();
229   EXPECT_EQ(10u, sent_nacks_.size());
230 }
231 
TEST_P(TestNackModule,TooLargeNackList)232 TEST_P(TestNackModule, TooLargeNackList) {
233   nack_module_.OnReceivedPacket(0, false, false);
234   nack_module_.OnReceivedPacket(1001, false, false);
235   EXPECT_EQ(1000u, sent_nacks_.size());
236   EXPECT_EQ(0, keyframes_requested_);
237   nack_module_.OnReceivedPacket(1003, false, false);
238   EXPECT_EQ(1000u, sent_nacks_.size());
239   EXPECT_EQ(1, keyframes_requested_);
240   nack_module_.OnReceivedPacket(1004, false, false);
241   EXPECT_EQ(1000u, sent_nacks_.size());
242   EXPECT_EQ(1, keyframes_requested_);
243 }
244 
TEST_P(TestNackModule,TooLargeNackListWithKeyFrame)245 TEST_P(TestNackModule, TooLargeNackListWithKeyFrame) {
246   nack_module_.OnReceivedPacket(0, false, false);
247   nack_module_.OnReceivedPacket(1, true, false);
248   nack_module_.OnReceivedPacket(1001, false, false);
249   EXPECT_EQ(999u, sent_nacks_.size());
250   EXPECT_EQ(0, keyframes_requested_);
251   nack_module_.OnReceivedPacket(1003, false, false);
252   EXPECT_EQ(1000u, sent_nacks_.size());
253   EXPECT_EQ(0, keyframes_requested_);
254   nack_module_.OnReceivedPacket(1005, false, false);
255   EXPECT_EQ(1000u, sent_nacks_.size());
256   EXPECT_EQ(1, keyframes_requested_);
257 }
258 
TEST_P(TestNackModule,ClearUpTo)259 TEST_P(TestNackModule, ClearUpTo) {
260   nack_module_.OnReceivedPacket(0, false, false);
261   nack_module_.OnReceivedPacket(100, false, false);
262   EXPECT_EQ(99u, sent_nacks_.size());
263 
264   sent_nacks_.clear();
265   clock_->AdvanceTimeMilliseconds(100);
266   nack_module_.ClearUpTo(50);
267   nack_module_.Process();
268   EXPECT_EQ(50u, sent_nacks_.size());
269   EXPECT_EQ(50, sent_nacks_[0]);
270 }
271 
TEST_P(TestNackModule,ClearUpToWrap)272 TEST_P(TestNackModule, ClearUpToWrap) {
273   nack_module_.OnReceivedPacket(0xfff0, false, false);
274   nack_module_.OnReceivedPacket(0xf, false, false);
275   EXPECT_EQ(30u, sent_nacks_.size());
276 
277   sent_nacks_.clear();
278   clock_->AdvanceTimeMilliseconds(100);
279   nack_module_.ClearUpTo(0);
280   nack_module_.Process();
281   EXPECT_EQ(15u, sent_nacks_.size());
282   EXPECT_EQ(0, sent_nacks_[0]);
283 }
284 
TEST_P(TestNackModule,PacketNackCount)285 TEST_P(TestNackModule, PacketNackCount) {
286   EXPECT_EQ(0, nack_module_.OnReceivedPacket(0, false, false));
287   EXPECT_EQ(0, nack_module_.OnReceivedPacket(2, false, false));
288   EXPECT_EQ(1, nack_module_.OnReceivedPacket(1, false, false));
289 
290   sent_nacks_.clear();
291   nack_module_.UpdateRtt(100);
292   EXPECT_EQ(0, nack_module_.OnReceivedPacket(5, false, false));
293   clock_->AdvanceTimeMilliseconds(100);
294   nack_module_.Process();
295   clock_->AdvanceTimeMilliseconds(125);
296   nack_module_.Process();
297   EXPECT_EQ(3, nack_module_.OnReceivedPacket(3, false, false));
298   EXPECT_EQ(3, nack_module_.OnReceivedPacket(4, false, false));
299   EXPECT_EQ(0, nack_module_.OnReceivedPacket(4, false, false));
300 }
301 
TEST_P(TestNackModule,NackListFullAndNoOverlapWithKeyframes)302 TEST_P(TestNackModule, NackListFullAndNoOverlapWithKeyframes) {
303   const int kMaxNackPackets = 1000;
304   const unsigned int kFirstGap = kMaxNackPackets - 20;
305   const unsigned int kSecondGap = 200;
306   uint16_t seq_num = 0;
307   nack_module_.OnReceivedPacket(seq_num++, true, false);
308   seq_num += kFirstGap;
309   nack_module_.OnReceivedPacket(seq_num++, true, false);
310   EXPECT_EQ(kFirstGap, sent_nacks_.size());
311   sent_nacks_.clear();
312   seq_num += kSecondGap;
313   nack_module_.OnReceivedPacket(seq_num, true, false);
314   EXPECT_EQ(kSecondGap, sent_nacks_.size());
315 }
316 
TEST_P(TestNackModule,HandleFecRecoveredPacket)317 TEST_P(TestNackModule, HandleFecRecoveredPacket) {
318   nack_module_.OnReceivedPacket(1, false, false);
319   nack_module_.OnReceivedPacket(4, false, true);
320   EXPECT_EQ(0u, sent_nacks_.size());
321   nack_module_.OnReceivedPacket(5, false, false);
322   EXPECT_EQ(2u, sent_nacks_.size());
323 }
324 
TEST_P(TestNackModule,SendNackWithoutDelay)325 TEST_P(TestNackModule, SendNackWithoutDelay) {
326   nack_module_.OnReceivedPacket(0, false, false);
327   nack_module_.OnReceivedPacket(100, false, false);
328   EXPECT_EQ(99u, sent_nacks_.size());
329 }
330 
331 INSTANTIATE_TEST_SUITE_P(WithAndWithoutBackoff,
332                          TestNackModule,
333                          ::testing::Values(true, false));
334 
335 class TestNackModuleWithFieldTrial : public ::testing::Test,
336                                      public NackSender,
337                                      public KeyFrameRequestSender {
338  protected:
TestNackModuleWithFieldTrial()339   TestNackModuleWithFieldTrial()
340       : nack_delay_field_trial_("WebRTC-SendNackDelayMs/10/"),
341         clock_(new SimulatedClock(0)),
342         nack_module_(clock_.get(), this, this),
343         keyframes_requested_(0) {}
344 
SendNack(const std::vector<uint16_t> & sequence_numbers,bool buffering_allowed)345   void SendNack(const std::vector<uint16_t>& sequence_numbers,
346                 bool buffering_allowed) override {
347     sent_nacks_.insert(sent_nacks_.end(), sequence_numbers.begin(),
348                        sequence_numbers.end());
349   }
350 
RequestKeyFrame()351   void RequestKeyFrame() override { ++keyframes_requested_; }
352 
353   test::ScopedFieldTrials nack_delay_field_trial_;
354   std::unique_ptr<SimulatedClock> clock_;
355   DEPRECATED_NackModule nack_module_;
356   std::vector<uint16_t> sent_nacks_;
357   int keyframes_requested_;
358 };
359 
TEST_F(TestNackModuleWithFieldTrial,SendNackWithDelay)360 TEST_F(TestNackModuleWithFieldTrial, SendNackWithDelay) {
361   nack_module_.OnReceivedPacket(0, false, false);
362   nack_module_.OnReceivedPacket(100, false, false);
363   EXPECT_EQ(0u, sent_nacks_.size());
364   clock_->AdvanceTimeMilliseconds(10);
365   nack_module_.OnReceivedPacket(106, false, false);
366   EXPECT_EQ(99u, sent_nacks_.size());
367   clock_->AdvanceTimeMilliseconds(10);
368   nack_module_.OnReceivedPacket(109, false, false);
369   EXPECT_EQ(104u, sent_nacks_.size());
370 }
371 }  // namespace webrtc
372