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