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