1 /*
2 * Copyright (c) 2017 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 "voice_engine/transport_feedback_packet_loss_tracker.h"
12
13 #include <limits>
14 #include <utility>
15
16 #include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
17 #include "modules/rtp_rtcp/source/rtcp_packet/transport_feedback.h"
18 #include "rtc_base/checks.h"
19 #include "rtc_base/numerics/mod_ops.h"
20
21 namespace {
22 constexpr uint16_t kSeqNumHalf = 0x8000u;
UpdateCounter(size_t * counter,bool increment)23 void UpdateCounter(size_t* counter, bool increment) {
24 if (increment) {
25 RTC_DCHECK_LT(*counter, std::numeric_limits<std::size_t>::max());
26 ++(*counter);
27 } else {
28 RTC_DCHECK_GT(*counter, 0);
29 --(*counter);
30 }
31 }
32 } // namespace
33
34 namespace webrtc {
35
TransportFeedbackPacketLossTracker(int64_t max_window_size_ms,size_t plr_min_num_acked_packets,size_t rplr_min_num_acked_pairs)36 TransportFeedbackPacketLossTracker::TransportFeedbackPacketLossTracker(
37 int64_t max_window_size_ms,
38 size_t plr_min_num_acked_packets,
39 size_t rplr_min_num_acked_pairs)
40 : max_window_size_ms_(max_window_size_ms),
41 ref_packet_status_(packet_status_window_.begin()),
42 plr_state_(plr_min_num_acked_packets),
43 rplr_state_(rplr_min_num_acked_pairs) {
44 RTC_DCHECK_GT(max_window_size_ms, 0);
45 RTC_DCHECK_GT(plr_min_num_acked_packets, 0);
46 RTC_DCHECK_GT(rplr_min_num_acked_pairs, 0);
47 Reset();
48 }
49
Reset()50 void TransportFeedbackPacketLossTracker::Reset() {
51 acked_packets_ = 0;
52 plr_state_.Reset();
53 rplr_state_.Reset();
54 packet_status_window_.clear();
55 ref_packet_status_ = packet_status_window_.begin();
56 }
57
ReferenceSequenceNumber() const58 uint16_t TransportFeedbackPacketLossTracker::ReferenceSequenceNumber() const {
59 RTC_DCHECK(!packet_status_window_.empty());
60 return ref_packet_status_->first;
61 }
62
NewestSequenceNumber() const63 uint16_t TransportFeedbackPacketLossTracker::NewestSequenceNumber() const {
64 RTC_DCHECK(!packet_status_window_.empty());
65 return PreviousPacketStatus(packet_status_window_.end())->first;
66 }
67
OnPacketAdded(uint16_t seq_num,int64_t send_time_ms)68 void TransportFeedbackPacketLossTracker::OnPacketAdded(uint16_t seq_num,
69 int64_t send_time_ms) {
70 // Sanity - time can't flow backwards.
71 RTC_DCHECK(
72 packet_status_window_.empty() ||
73 PreviousPacketStatus(packet_status_window_.end())->second.send_time_ms <=
74 send_time_ms);
75
76 if (packet_status_window_.find(seq_num) != packet_status_window_.end() ||
77 (!packet_status_window_.empty() &&
78 ForwardDiff(seq_num, NewestSequenceNumber()) <= kSeqNumHalf)) {
79 // The only way for these two to happen is when the stream lies dormant for
80 // long enough for the sequence numbers to wrap. Everything in the window in
81 // such a case would be too old to use.
82 Reset();
83 }
84
85 // Maintain a window where the newest sequence number is at most 0x7fff away
86 // from the oldest, so that would could still distinguish old/new.
87 while (!packet_status_window_.empty() &&
88 ForwardDiff(ref_packet_status_->first, seq_num) >= kSeqNumHalf) {
89 RemoveOldestPacketStatus();
90 }
91
92 SentPacket sent_packet(send_time_ms, PacketStatus::Unacked);
93 packet_status_window_.insert(packet_status_window_.end(),
94 std::make_pair(seq_num, sent_packet));
95
96 if (packet_status_window_.size() == 1) {
97 ref_packet_status_ = packet_status_window_.cbegin();
98 }
99 }
100
OnPacketFeedbackVector(const std::vector<PacketFeedback> & packet_feedback_vector)101 void TransportFeedbackPacketLossTracker::OnPacketFeedbackVector(
102 const std::vector<PacketFeedback>& packet_feedback_vector) {
103 for (const PacketFeedback& packet : packet_feedback_vector) {
104 const auto& it = packet_status_window_.find(packet.sequence_number);
105
106 // Packets which aren't at least marked as unacked either do not belong to
107 // this media stream, or have been shifted out of window.
108 if (it == packet_status_window_.end())
109 continue;
110
111 const bool lost = packet.arrival_time_ms == PacketFeedback::kNotReceived;
112 const PacketStatus packet_status =
113 lost ? PacketStatus::Lost : PacketStatus::Received;
114
115 UpdatePacketStatus(it, packet_status);
116 }
117 }
118
119 rtc::Optional<float>
GetPacketLossRate() const120 TransportFeedbackPacketLossTracker::GetPacketLossRate() const {
121 return plr_state_.GetMetric();
122 }
123
124 rtc::Optional<float>
GetRecoverablePacketLossRate() const125 TransportFeedbackPacketLossTracker::GetRecoverablePacketLossRate() const {
126 return rplr_state_.GetMetric();
127 }
128
UpdatePacketStatus(SentPacketStatusMap::iterator it,PacketStatus new_status)129 void TransportFeedbackPacketLossTracker::UpdatePacketStatus(
130 SentPacketStatusMap::iterator it,
131 PacketStatus new_status) {
132 if (it->second.status != PacketStatus::Unacked) {
133 // Normally, packets are sent (inserted into window as "unacked"), then we
134 // receive one feedback for them.
135 // But it is possible that a packet would receive two feedbacks. Then:
136 if (it->second.status == PacketStatus::Lost &&
137 new_status == PacketStatus::Received) {
138 // If older status said that the packet was lost but newer one says it
139 // is received, we take the newer one.
140 UpdateMetrics(it, false);
141 it->second.status =
142 PacketStatus::Unacked; // For clarity; overwritten shortly.
143 } else {
144 // If the value is unchanged or if older status said that the packet was
145 // received but the newer one says it is lost, we ignore it.
146 // The standard allows for previously-reported packets to carry
147 // no report when the reports overlap, which also looks like the
148 // packet is being reported as lost.
149 return;
150 }
151 }
152
153 // Change from UNACKED to RECEIVED/LOST.
154 it->second.status = new_status;
155 UpdateMetrics(it, true);
156
157 // Remove packets from the beginning of the window until we only hold packets,
158 // be they acked or unacked, which are not more than |max_window_size_ms|
159 // older from the newest packet. (If the packet we're now inserting into the
160 // window isn't the newest, it would not trigger any removals; the newest
161 // already removed all relevant.)
162 while (ref_packet_status_ != packet_status_window_.end() &&
163 (it->second.send_time_ms - ref_packet_status_->second.send_time_ms) >
164 max_window_size_ms_) {
165 RemoveOldestPacketStatus();
166 }
167 }
168
RemoveOldestPacketStatus()169 void TransportFeedbackPacketLossTracker::RemoveOldestPacketStatus() {
170 UpdateMetrics(ref_packet_status_, false);
171 const auto it = ref_packet_status_;
172 ref_packet_status_ = NextPacketStatus(it);
173 packet_status_window_.erase(it);
174 }
175
UpdateMetrics(ConstPacketStatusIterator it,bool apply)176 void TransportFeedbackPacketLossTracker::UpdateMetrics(
177 ConstPacketStatusIterator it,
178 bool apply /* false = undo */) {
179 RTC_DCHECK(it != packet_status_window_.end());
180 // Metrics are dependent on feedbacks from the other side. We don't want
181 // to update the metrics each time a packet is sent, except for the case
182 // when it shifts old sent-but-unacked-packets out of window.
183 RTC_DCHECK(!apply || it->second.status != PacketStatus::Unacked);
184
185 if (it->second.status != PacketStatus::Unacked) {
186 UpdateCounter(&acked_packets_, apply);
187 }
188
189 UpdatePlr(it, apply);
190 UpdateRplr(it, apply);
191 }
192
UpdatePlr(ConstPacketStatusIterator it,bool apply)193 void TransportFeedbackPacketLossTracker::UpdatePlr(
194 ConstPacketStatusIterator it,
195 bool apply /* false = undo */) {
196 switch (it->second.status) {
197 case PacketStatus::Unacked:
198 return;
199 case PacketStatus::Received:
200 UpdateCounter(&plr_state_.num_received_packets_, apply);
201 break;
202 case PacketStatus::Lost:
203 UpdateCounter(&plr_state_.num_lost_packets_, apply);
204 break;
205 default:
206 RTC_NOTREACHED();
207 }
208 }
209
UpdateRplr(ConstPacketStatusIterator it,bool apply)210 void TransportFeedbackPacketLossTracker::UpdateRplr(
211 ConstPacketStatusIterator it,
212 bool apply /* false = undo */) {
213 if (it->second.status == PacketStatus::Unacked) {
214 // Unacked packets cannot compose a pair.
215 return;
216 }
217
218 // Previous packet and current packet might compose a pair.
219 if (it != ref_packet_status_) {
220 const auto& prev = PreviousPacketStatus(it);
221 if (prev->second.status != PacketStatus::Unacked) {
222 UpdateCounter(&rplr_state_.num_acked_pairs_, apply);
223 if (prev->second.status == PacketStatus::Lost &&
224 it->second.status == PacketStatus::Received) {
225 UpdateCounter(
226 &rplr_state_.num_recoverable_losses_, apply);
227 }
228 }
229 }
230
231 // Current packet and next packet might compose a pair.
232 const auto& next = NextPacketStatus(it);
233 if (next != packet_status_window_.end() &&
234 next->second.status != PacketStatus::Unacked) {
235 UpdateCounter(&rplr_state_.num_acked_pairs_, apply);
236 if (it->second.status == PacketStatus::Lost &&
237 next->second.status == PacketStatus::Received) {
238 UpdateCounter(&rplr_state_.num_recoverable_losses_, apply);
239 }
240 }
241 }
242
243 TransportFeedbackPacketLossTracker::ConstPacketStatusIterator
PreviousPacketStatus(ConstPacketStatusIterator it) const244 TransportFeedbackPacketLossTracker::PreviousPacketStatus(
245 ConstPacketStatusIterator it) const {
246 RTC_DCHECK(it != ref_packet_status_);
247 if (it == packet_status_window_.end()) {
248 // This is to make PreviousPacketStatus(packet_status_window_.end()) point
249 // to the last element.
250 it = ref_packet_status_;
251 }
252
253 if (it == packet_status_window_.begin()) {
254 // Due to the circular nature of sequence numbers, we let the iterator
255 // go to the end.
256 it = packet_status_window_.end();
257 }
258 return --it;
259 }
260
261 TransportFeedbackPacketLossTracker::ConstPacketStatusIterator
NextPacketStatus(ConstPacketStatusIterator it) const262 TransportFeedbackPacketLossTracker::NextPacketStatus(
263 ConstPacketStatusIterator it) const {
264 RTC_DCHECK(it != packet_status_window_.end());
265 ++it;
266 if (it == packet_status_window_.end()) {
267 // Due to the circular nature of sequence numbers, we let the iterator
268 // goes back to the beginning.
269 it = packet_status_window_.begin();
270 }
271 if (it == ref_packet_status_) {
272 // This is to make the NextPacketStatus of the last element to return the
273 // beyond-the-end iterator.
274 it = packet_status_window_.end();
275 }
276 return it;
277 }
278
279 // TODO(minyue): This method checks the states of this class do not misbehave.
280 // The method is used both in unit tests and a fuzzer test. The fuzzer test
281 // is present to help finding potential errors. Once the fuzzer test shows no
282 // error after long period, we can remove the fuzzer test, and move this method
283 // to unit test.
Validate() const284 void TransportFeedbackPacketLossTracker::Validate() const { // Testing only!
285 RTC_CHECK_EQ(plr_state_.num_received_packets_ + plr_state_.num_lost_packets_,
286 acked_packets_);
287 RTC_CHECK_LE(acked_packets_, packet_status_window_.size());
288 RTC_CHECK_LE(rplr_state_.num_recoverable_losses_,
289 rplr_state_.num_acked_pairs_);
290 RTC_CHECK_LE(rplr_state_.num_acked_pairs_, acked_packets_ - 1);
291
292 size_t unacked_packets = 0;
293 size_t received_packets = 0;
294 size_t lost_packets = 0;
295 size_t acked_pairs = 0;
296 size_t recoverable_losses = 0;
297
298 if (!packet_status_window_.empty()) {
299 ConstPacketStatusIterator it = ref_packet_status_;
300 do {
301 switch (it->second.status) {
302 case PacketStatus::Unacked:
303 ++unacked_packets;
304 break;
305 case PacketStatus::Received:
306 ++received_packets;
307 break;
308 case PacketStatus::Lost:
309 ++lost_packets;
310 break;
311 default:
312 RTC_NOTREACHED();
313 }
314
315 auto next = std::next(it);
316 if (next == packet_status_window_.end())
317 next = packet_status_window_.begin();
318
319 if (next != ref_packet_status_) { // If we have a next packet...
320 RTC_CHECK_GE(next->second.send_time_ms, it->second.send_time_ms);
321
322 if (it->second.status != PacketStatus::Unacked &&
323 next->second.status != PacketStatus::Unacked) {
324 ++acked_pairs;
325 if (it->second.status == PacketStatus::Lost &&
326 next->second.status == PacketStatus::Received) {
327 ++recoverable_losses;
328 }
329 }
330 }
331
332 RTC_CHECK_LT(ForwardDiff(ReferenceSequenceNumber(), it->first),
333 kSeqNumHalf);
334
335 it = next;
336 } while (it != ref_packet_status_);
337 }
338
339 RTC_CHECK_EQ(plr_state_.num_received_packets_, received_packets);
340 RTC_CHECK_EQ(plr_state_.num_lost_packets_, lost_packets);
341 RTC_CHECK_EQ(packet_status_window_.size(),
342 unacked_packets + received_packets + lost_packets);
343 RTC_CHECK_EQ(rplr_state_.num_acked_pairs_, acked_pairs);
344 RTC_CHECK_EQ(rplr_state_.num_recoverable_losses_, recoverable_losses);
345 }
346
347 rtc::Optional<float>
GetMetric() const348 TransportFeedbackPacketLossTracker::PlrState::GetMetric() const {
349 const size_t total = num_lost_packets_ + num_received_packets_;
350 if (total < min_num_acked_packets_) {
351 return rtc::nullopt;
352 } else {
353 return static_cast<float>(num_lost_packets_) / total;
354 }
355 }
356
357 rtc::Optional<float>
GetMetric() const358 TransportFeedbackPacketLossTracker::RplrState::GetMetric() const {
359 if (num_acked_pairs_ < min_num_acked_pairs_) {
360 return rtc::nullopt;
361 } else {
362 return static_cast<float>(num_recoverable_losses_) / num_acked_pairs_;
363 }
364 }
365
366 } // namespace webrtc
367