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 <algorithm>
12 #include <limits>
13
14 #include "modules/video_coding/nack_module.h"
15
16 #include "modules/utility/include/process_thread.h"
17 #include "rtc_base/checks.h"
18 #include "rtc_base/logging.h"
19
20 namespace webrtc {
21
22 namespace {
23 const int kMaxPacketAge = 10000;
24 const int kMaxNackPackets = 1000;
25 const int kDefaultRttMs = 100;
26 const int kMaxNackRetries = 10;
27 const int kProcessFrequency = 50;
28 const int kProcessIntervalMs = 1000 / kProcessFrequency;
29 const int kMaxReorderedPackets = 128;
30 const int kNumReorderingBuckets = 10;
31 } // namespace
32
NackInfo()33 NackModule::NackInfo::NackInfo()
34 : seq_num(0), send_at_seq_num(0), sent_at_time(-1), retries(0) {}
35
NackInfo(uint16_t seq_num,uint16_t send_at_seq_num)36 NackModule::NackInfo::NackInfo(uint16_t seq_num, uint16_t send_at_seq_num)
37 : seq_num(seq_num),
38 send_at_seq_num(send_at_seq_num),
39 sent_at_time(-1),
40 retries(0) {}
41
NackModule(Clock * clock,NackSender * nack_sender,KeyFrameRequestSender * keyframe_request_sender)42 NackModule::NackModule(Clock* clock,
43 NackSender* nack_sender,
44 KeyFrameRequestSender* keyframe_request_sender)
45 : clock_(clock),
46 nack_sender_(nack_sender),
47 keyframe_request_sender_(keyframe_request_sender),
48 reordering_histogram_(kNumReorderingBuckets, kMaxReorderedPackets),
49 initialized_(false),
50 rtt_ms_(kDefaultRttMs),
51 newest_seq_num_(0),
52 next_process_time_ms_(-1) {
53 RTC_DCHECK(clock_);
54 RTC_DCHECK(nack_sender_);
55 RTC_DCHECK(keyframe_request_sender_);
56 }
57
OnReceivedPacket(const VCMPacket & packet)58 int NackModule::OnReceivedPacket(const VCMPacket& packet) {
59 rtc::CritScope lock(&crit_);
60 uint16_t seq_num = packet.seqNum;
61 // TODO(philipel): When the packet includes information whether it is
62 // retransmitted or not, use that value instead. For
63 // now set it to true, which will cause the reordering
64 // statistics to never be updated.
65 bool is_retransmitted = true;
66 bool is_keyframe =
67 packet.is_first_packet_in_frame && packet.frameType == kVideoFrameKey;
68
69 if (!initialized_) {
70 newest_seq_num_ = seq_num;
71 if (is_keyframe)
72 keyframe_list_.insert(seq_num);
73 initialized_ = true;
74 return 0;
75 }
76
77 // Since the |newest_seq_num_| is a packet we have actually received we know
78 // that packet has never been Nacked.
79 if (seq_num == newest_seq_num_)
80 return 0;
81
82 if (AheadOf(newest_seq_num_, seq_num)) {
83 // An out of order packet has been received.
84 auto nack_list_it = nack_list_.find(seq_num);
85 int nacks_sent_for_packet = 0;
86 if (nack_list_it != nack_list_.end()) {
87 nacks_sent_for_packet = nack_list_it->second.retries;
88 nack_list_.erase(nack_list_it);
89 }
90 if (!is_retransmitted)
91 UpdateReorderingStatistics(seq_num);
92 return nacks_sent_for_packet;
93 }
94 AddPacketsToNack(newest_seq_num_ + 1, seq_num);
95 newest_seq_num_ = seq_num;
96
97 // Keep track of new keyframes.
98 if (is_keyframe)
99 keyframe_list_.insert(seq_num);
100
101 // And remove old ones so we don't accumulate keyframes.
102 auto it = keyframe_list_.lower_bound(seq_num - kMaxPacketAge);
103 if (it != keyframe_list_.begin())
104 keyframe_list_.erase(keyframe_list_.begin(), it);
105
106 // Are there any nacks that are waiting for this seq_num.
107 std::vector<uint16_t> nack_batch = GetNackBatch(kSeqNumOnly);
108 if (!nack_batch.empty())
109 nack_sender_->SendNack(nack_batch);
110
111 return 0;
112 }
113
ClearUpTo(uint16_t seq_num)114 void NackModule::ClearUpTo(uint16_t seq_num) {
115 rtc::CritScope lock(&crit_);
116 nack_list_.erase(nack_list_.begin(), nack_list_.lower_bound(seq_num));
117 keyframe_list_.erase(keyframe_list_.begin(),
118 keyframe_list_.lower_bound(seq_num));
119 }
120
UpdateRtt(int64_t rtt_ms)121 void NackModule::UpdateRtt(int64_t rtt_ms) {
122 rtc::CritScope lock(&crit_);
123 rtt_ms_ = rtt_ms;
124 }
125
Clear()126 void NackModule::Clear() {
127 rtc::CritScope lock(&crit_);
128 nack_list_.clear();
129 keyframe_list_.clear();
130 }
131
TimeUntilNextProcess()132 int64_t NackModule::TimeUntilNextProcess() {
133 return std::max<int64_t>(next_process_time_ms_ - clock_->TimeInMilliseconds(),
134 0);
135 }
136
Process()137 void NackModule::Process() {
138 if (nack_sender_) {
139 std::vector<uint16_t> nack_batch;
140 {
141 rtc::CritScope lock(&crit_);
142 nack_batch = GetNackBatch(kTimeOnly);
143 }
144
145 if (!nack_batch.empty())
146 nack_sender_->SendNack(nack_batch);
147 }
148
149 // Update the next_process_time_ms_ in intervals to achieve
150 // the targeted frequency over time. Also add multiple intervals
151 // in case of a skip in time as to not make uneccessary
152 // calls to Process in order to catch up.
153 int64_t now_ms = clock_->TimeInMilliseconds();
154 if (next_process_time_ms_ == -1) {
155 next_process_time_ms_ = now_ms + kProcessIntervalMs;
156 } else {
157 next_process_time_ms_ = next_process_time_ms_ + kProcessIntervalMs +
158 (now_ms - next_process_time_ms_) /
159 kProcessIntervalMs * kProcessIntervalMs;
160 }
161 }
162
RemovePacketsUntilKeyFrame()163 bool NackModule::RemovePacketsUntilKeyFrame() {
164 while (!keyframe_list_.empty()) {
165 auto it = nack_list_.lower_bound(*keyframe_list_.begin());
166
167 if (it != nack_list_.begin()) {
168 // We have found a keyframe that actually is newer than at least one
169 // packet in the nack list.
170 RTC_DCHECK(it != nack_list_.end());
171 nack_list_.erase(nack_list_.begin(), it);
172 return true;
173 }
174
175 // If this keyframe is so old it does not remove any packets from the list,
176 // remove it from the list of keyframes and try the next keyframe.
177 keyframe_list_.erase(keyframe_list_.begin());
178 }
179 return false;
180 }
181
AddPacketsToNack(uint16_t seq_num_start,uint16_t seq_num_end)182 void NackModule::AddPacketsToNack(uint16_t seq_num_start,
183 uint16_t seq_num_end) {
184 // Remove old packets.
185 auto it = nack_list_.lower_bound(seq_num_end - kMaxPacketAge);
186 nack_list_.erase(nack_list_.begin(), it);
187
188 // If the nack list is too large, remove packets from the nack list until
189 // the latest first packet of a keyframe. If the list is still too large,
190 // clear it and request a keyframe.
191 uint16_t num_new_nacks = ForwardDiff(seq_num_start, seq_num_end);
192 if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
193 while (RemovePacketsUntilKeyFrame() &&
194 nack_list_.size() + num_new_nacks > kMaxNackPackets) {
195 }
196
197 if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
198 nack_list_.clear();
199 RTC_LOG(LS_WARNING) << "NACK list full, clearing NACK"
200 " list and requesting keyframe.";
201 keyframe_request_sender_->RequestKeyFrame();
202 return;
203 }
204 }
205
206 for (uint16_t seq_num = seq_num_start; seq_num != seq_num_end; ++seq_num) {
207 NackInfo nack_info(seq_num, seq_num + WaitNumberOfPackets(0.5));
208 RTC_DCHECK(nack_list_.find(seq_num) == nack_list_.end());
209 nack_list_[seq_num] = nack_info;
210 }
211 }
212
GetNackBatch(NackFilterOptions options)213 std::vector<uint16_t> NackModule::GetNackBatch(NackFilterOptions options) {
214 bool consider_seq_num = options != kTimeOnly;
215 bool consider_timestamp = options != kSeqNumOnly;
216 int64_t now_ms = clock_->TimeInMilliseconds();
217 std::vector<uint16_t> nack_batch;
218 auto it = nack_list_.begin();
219 while (it != nack_list_.end()) {
220 if (consider_seq_num && it->second.sent_at_time == -1 &&
221 AheadOrAt(newest_seq_num_, it->second.send_at_seq_num)) {
222 nack_batch.emplace_back(it->second.seq_num);
223 ++it->second.retries;
224 it->second.sent_at_time = now_ms;
225 if (it->second.retries >= kMaxNackRetries) {
226 RTC_LOG(LS_WARNING) << "Sequence number " << it->second.seq_num
227 << " removed from NACK list due to max retries.";
228 it = nack_list_.erase(it);
229 } else {
230 ++it;
231 }
232 continue;
233 }
234
235 if (consider_timestamp && it->second.sent_at_time + rtt_ms_ <= now_ms) {
236 nack_batch.emplace_back(it->second.seq_num);
237 ++it->second.retries;
238 it->second.sent_at_time = now_ms;
239 if (it->second.retries >= kMaxNackRetries) {
240 RTC_LOG(LS_WARNING) << "Sequence number " << it->second.seq_num
241 << " removed from NACK list due to max retries.";
242 it = nack_list_.erase(it);
243 } else {
244 ++it;
245 }
246 continue;
247 }
248 ++it;
249 }
250 return nack_batch;
251 }
252
UpdateReorderingStatistics(uint16_t seq_num)253 void NackModule::UpdateReorderingStatistics(uint16_t seq_num) {
254 RTC_DCHECK(AheadOf(newest_seq_num_, seq_num));
255 uint16_t diff = ReverseDiff(newest_seq_num_, seq_num);
256 reordering_histogram_.Add(diff);
257 }
258
WaitNumberOfPackets(float probability) const259 int NackModule::WaitNumberOfPackets(float probability) const {
260 if (reordering_histogram_.NumValues() == 0)
261 return 0;
262 return reordering_histogram_.InverseCdf(probability);
263 }
264
265 } // namespace webrtc
266