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