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