1 /*
2 * Copyright (c) 2015 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/congestion_controller/rtp/transport_feedback_adapter.h"
12
13 #include <stdlib.h>
14
15 #include <algorithm>
16 #include <cmath>
17 #include <utility>
18
19 #include "absl/algorithm/container.h"
20 #include "api/units/timestamp.h"
21 #include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
22 #include "modules/rtp_rtcp/source/rtcp_packet/transport_feedback.h"
23 #include "rtc_base/checks.h"
24 #include "rtc_base/logging.h"
25
26 namespace webrtc {
27
28 constexpr TimeDelta kSendTimeHistoryWindow = TimeDelta::Seconds(60);
29
AddInFlightPacketBytes(const PacketFeedback & packet)30 void InFlightBytesTracker::AddInFlightPacketBytes(
31 const PacketFeedback& packet) {
32 RTC_DCHECK(packet.sent.send_time.IsFinite());
33 auto it = in_flight_data_.find(packet.network_route);
34 if (it != in_flight_data_.end()) {
35 it->second += packet.sent.size;
36 } else {
37 in_flight_data_.insert({packet.network_route, packet.sent.size});
38 }
39 }
40
RemoveInFlightPacketBytes(const PacketFeedback & packet)41 void InFlightBytesTracker::RemoveInFlightPacketBytes(
42 const PacketFeedback& packet) {
43 if (packet.sent.send_time.IsInfinite())
44 return;
45 auto it = in_flight_data_.find(packet.network_route);
46 if (it != in_flight_data_.end()) {
47 RTC_DCHECK_GE(it->second, packet.sent.size);
48 it->second -= packet.sent.size;
49 if (it->second.IsZero())
50 in_flight_data_.erase(it);
51 }
52 }
53
GetOutstandingData(const rtc::NetworkRoute & network_route) const54 DataSize InFlightBytesTracker::GetOutstandingData(
55 const rtc::NetworkRoute& network_route) const {
56 auto it = in_flight_data_.find(network_route);
57 if (it != in_flight_data_.end()) {
58 return it->second;
59 } else {
60 return DataSize::Zero();
61 }
62 }
63
64 // Comparator for consistent map with NetworkRoute as key.
operator ()(const rtc::NetworkRoute & a,const rtc::NetworkRoute & b) const65 bool InFlightBytesTracker::NetworkRouteComparator::operator()(
66 const rtc::NetworkRoute& a,
67 const rtc::NetworkRoute& b) const {
68 if (a.local.network_id() != b.local.network_id())
69 return a.local.network_id() < b.local.network_id();
70 if (a.remote.network_id() != b.remote.network_id())
71 return a.remote.network_id() < b.remote.network_id();
72
73 if (a.local.adapter_id() != b.local.adapter_id())
74 return a.local.adapter_id() < b.local.adapter_id();
75 if (a.remote.adapter_id() != b.remote.adapter_id())
76 return a.remote.adapter_id() < b.remote.adapter_id();
77
78 if (a.local.uses_turn() != b.local.uses_turn())
79 return a.local.uses_turn() < b.local.uses_turn();
80 if (a.remote.uses_turn() != b.remote.uses_turn())
81 return a.remote.uses_turn() < b.remote.uses_turn();
82
83 return a.connected < b.connected;
84 }
85
86 TransportFeedbackAdapter::TransportFeedbackAdapter() = default;
87
88
AddPacket(const RtpPacketSendInfo & packet_info,size_t overhead_bytes,Timestamp creation_time)89 void TransportFeedbackAdapter::AddPacket(const RtpPacketSendInfo& packet_info,
90 size_t overhead_bytes,
91 Timestamp creation_time) {
92 PacketFeedback packet;
93 packet.creation_time = creation_time;
94 packet.sent.sequence_number =
95 seq_num_unwrapper_.Unwrap(packet_info.transport_sequence_number);
96 packet.sent.size = DataSize::Bytes(packet_info.length + overhead_bytes);
97 packet.sent.audio = packet_info.packet_type == RtpPacketMediaType::kAudio;
98 packet.network_route = network_route_;
99 packet.sent.pacing_info = packet_info.pacing_info;
100
101 while (!history_.empty() &&
102 creation_time - history_.begin()->second.creation_time >
103 kSendTimeHistoryWindow) {
104 // TODO(sprang): Warn if erasing (too many) old items?
105 if (history_.begin()->second.sent.sequence_number > last_ack_seq_num_)
106 in_flight_.RemoveInFlightPacketBytes(history_.begin()->second);
107 history_.erase(history_.begin());
108 }
109 history_.insert(std::make_pair(packet.sent.sequence_number, packet));
110 }
111
ProcessSentPacket(const rtc::SentPacket & sent_packet)112 absl::optional<SentPacket> TransportFeedbackAdapter::ProcessSentPacket(
113 const rtc::SentPacket& sent_packet) {
114 auto send_time = Timestamp::Millis(sent_packet.send_time_ms);
115 // TODO(srte): Only use one way to indicate that packet feedback is used.
116 if (sent_packet.info.included_in_feedback || sent_packet.packet_id != -1) {
117 int64_t unwrapped_seq_num =
118 seq_num_unwrapper_.Unwrap(sent_packet.packet_id);
119 auto it = history_.find(unwrapped_seq_num);
120 if (it != history_.end()) {
121 bool packet_retransmit = it->second.sent.send_time.IsFinite();
122 it->second.sent.send_time = send_time;
123 last_send_time_ = std::max(last_send_time_, send_time);
124 // TODO(srte): Don't do this on retransmit.
125 if (!pending_untracked_size_.IsZero()) {
126 if (send_time < last_untracked_send_time_)
127 RTC_LOG(LS_WARNING)
128 << "appending acknowledged data for out of order packet. (Diff: "
129 << ToString(last_untracked_send_time_ - send_time) << " ms.)";
130 it->second.sent.prior_unacked_data += pending_untracked_size_;
131 pending_untracked_size_ = DataSize::Zero();
132 }
133 if (!packet_retransmit) {
134 if (it->second.sent.sequence_number > last_ack_seq_num_)
135 in_flight_.AddInFlightPacketBytes(it->second);
136 it->second.sent.data_in_flight = GetOutstandingData();
137 return it->second.sent;
138 }
139 }
140 } else if (sent_packet.info.included_in_allocation) {
141 if (send_time < last_send_time_) {
142 RTC_LOG(LS_WARNING) << "ignoring untracked data for out of order packet.";
143 }
144 pending_untracked_size_ +=
145 DataSize::Bytes(sent_packet.info.packet_size_bytes);
146 last_untracked_send_time_ = std::max(last_untracked_send_time_, send_time);
147 }
148 return absl::nullopt;
149 }
150
151 absl::optional<TransportPacketsFeedback>
ProcessTransportFeedback(const rtcp::TransportFeedback & feedback,Timestamp feedback_receive_time)152 TransportFeedbackAdapter::ProcessTransportFeedback(
153 const rtcp::TransportFeedback& feedback,
154 Timestamp feedback_receive_time) {
155 if (feedback.GetPacketStatusCount() == 0) {
156 RTC_LOG(LS_INFO) << "Empty transport feedback packet received.";
157 return absl::nullopt;
158 }
159
160 TransportPacketsFeedback msg;
161 msg.feedback_time = feedback_receive_time;
162
163 msg.prior_in_flight = in_flight_.GetOutstandingData(network_route_);
164 msg.packet_feedbacks =
165 ProcessTransportFeedbackInner(feedback, feedback_receive_time);
166 if (msg.packet_feedbacks.empty())
167 return absl::nullopt;
168
169 auto it = history_.find(last_ack_seq_num_);
170 if (it != history_.end()) {
171 msg.first_unacked_send_time = it->second.sent.send_time;
172 }
173 msg.data_in_flight = in_flight_.GetOutstandingData(network_route_);
174
175 return msg;
176 }
177
SetNetworkRoute(const rtc::NetworkRoute & network_route)178 void TransportFeedbackAdapter::SetNetworkRoute(
179 const rtc::NetworkRoute& network_route) {
180 network_route_ = network_route;
181 }
182
GetOutstandingData() const183 DataSize TransportFeedbackAdapter::GetOutstandingData() const {
184 return in_flight_.GetOutstandingData(network_route_);
185 }
186
187 std::vector<PacketResult>
ProcessTransportFeedbackInner(const rtcp::TransportFeedback & feedback,Timestamp feedback_receive_time)188 TransportFeedbackAdapter::ProcessTransportFeedbackInner(
189 const rtcp::TransportFeedback& feedback,
190 Timestamp feedback_receive_time) {
191 // Add timestamp deltas to a local time base selected on first packet arrival.
192 // This won't be the true time base, but makes it easier to manually inspect
193 // time stamps.
194 if (last_timestamp_.IsInfinite()) {
195 current_offset_ = feedback_receive_time;
196 } else {
197 // TODO(srte): We shouldn't need to do rounding here.
198 const TimeDelta delta = feedback.GetBaseDelta(last_timestamp_)
199 .RoundDownTo(TimeDelta::Millis(1));
200 // Protect against assigning current_offset_ negative value.
201 if (delta < Timestamp::Zero() - current_offset_) {
202 RTC_LOG(LS_WARNING) << "Unexpected feedback timestamp received.";
203 current_offset_ = feedback_receive_time;
204 } else {
205 current_offset_ += delta;
206 }
207 }
208 last_timestamp_ = feedback.BaseTime();
209
210 std::vector<PacketResult> packet_result_vector;
211 packet_result_vector.reserve(feedback.GetPacketStatusCount());
212
213 size_t failed_lookups = 0;
214 size_t ignored = 0;
215 TimeDelta packet_offset = TimeDelta::Zero();
216 for (const auto& packet : feedback.GetAllPackets()) {
217 int64_t seq_num = seq_num_unwrapper_.Unwrap(packet.sequence_number());
218
219 if (seq_num > last_ack_seq_num_) {
220 // Starts at history_.begin() if last_ack_seq_num_ < 0, since any valid
221 // sequence number is >= 0.
222 for (auto it = history_.upper_bound(last_ack_seq_num_);
223 it != history_.upper_bound(seq_num); ++it) {
224 in_flight_.RemoveInFlightPacketBytes(it->second);
225 }
226 last_ack_seq_num_ = seq_num;
227 }
228
229 auto it = history_.find(seq_num);
230 if (it == history_.end()) {
231 ++failed_lookups;
232 continue;
233 }
234
235 if (it->second.sent.send_time.IsInfinite()) {
236 // TODO(srte): Fix the tests that makes this happen and make this a
237 // DCHECK.
238 RTC_DLOG(LS_ERROR)
239 << "Received feedback before packet was indicated as sent";
240 continue;
241 }
242
243 PacketFeedback packet_feedback = it->second;
244 if (packet.received()) {
245 packet_offset += packet.delta();
246 packet_feedback.receive_time =
247 current_offset_ + packet_offset.RoundDownTo(TimeDelta::Millis(1));
248 // Note: Lost packets are not removed from history because they might be
249 // reported as received by a later feedback.
250 history_.erase(it);
251 }
252 if (packet_feedback.network_route == network_route_) {
253 PacketResult result;
254 result.sent_packet = packet_feedback.sent;
255 result.receive_time = packet_feedback.receive_time;
256 packet_result_vector.push_back(result);
257 } else {
258 ++ignored;
259 }
260 }
261
262 if (failed_lookups > 0) {
263 RTC_LOG(LS_WARNING) << "Failed to lookup send time for " << failed_lookups
264 << " packet" << (failed_lookups > 1 ? "s" : "")
265 << ". Send time history too small?";
266 }
267 if (ignored > 0) {
268 RTC_LOG(LS_INFO) << "Ignoring " << ignored
269 << " packets because they were sent on a different route.";
270 }
271
272 return packet_result_vector;
273 }
274
275 } // namespace webrtc
276