1 /*
2 * Copyright (c) 2012 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 "webrtc/modules/rtp_rtcp/source/rtp_packet_history.h"
12
13 #include <assert.h>
14 #include <stdlib.h>
15 #include <string.h> // memset
16
17 #include <algorithm>
18 #include <limits>
19 #include <set>
20
21 #include "webrtc/base/checks.h"
22 #include "webrtc/base/logging.h"
23 #include "webrtc/modules/rtp_rtcp/source/rtp_utility.h"
24 #include "webrtc/system_wrappers/include/critical_section_wrapper.h"
25
26 namespace webrtc {
27
28 static const int kMinPacketRequestBytes = 50;
29
RTPPacketHistory(Clock * clock)30 RTPPacketHistory::RTPPacketHistory(Clock* clock)
31 : clock_(clock),
32 critsect_(CriticalSectionWrapper::CreateCriticalSection()),
33 store_(false),
34 prev_index_(0) {}
35
~RTPPacketHistory()36 RTPPacketHistory::~RTPPacketHistory() {
37 }
38
SetStorePacketsStatus(bool enable,uint16_t number_to_store)39 void RTPPacketHistory::SetStorePacketsStatus(bool enable,
40 uint16_t number_to_store) {
41 CriticalSectionScoped cs(critsect_.get());
42 if (enable) {
43 if (store_) {
44 LOG(LS_WARNING) << "Purging packet history in order to re-set status.";
45 Free();
46 }
47 assert(!store_);
48 Allocate(number_to_store);
49 } else {
50 Free();
51 }
52 }
53
Allocate(size_t number_to_store)54 void RTPPacketHistory::Allocate(size_t number_to_store) {
55 assert(number_to_store > 0);
56 assert(number_to_store <= kMaxHistoryCapacity);
57 store_ = true;
58 stored_packets_.resize(number_to_store);
59 }
60
Free()61 void RTPPacketHistory::Free() {
62 if (!store_) {
63 return;
64 }
65
66 stored_packets_.clear();
67
68 store_ = false;
69 prev_index_ = 0;
70 }
71
StorePackets() const72 bool RTPPacketHistory::StorePackets() const {
73 CriticalSectionScoped cs(critsect_.get());
74 return store_;
75 }
76
PutRTPPacket(const uint8_t * packet,size_t packet_length,int64_t capture_time_ms,StorageType type)77 int32_t RTPPacketHistory::PutRTPPacket(const uint8_t* packet,
78 size_t packet_length,
79 int64_t capture_time_ms,
80 StorageType type) {
81 CriticalSectionScoped cs(critsect_.get());
82 if (!store_) {
83 return 0;
84 }
85
86 assert(packet);
87 assert(packet_length > 3);
88
89 if (packet_length > IP_PACKET_SIZE) {
90 LOG(LS_WARNING) << "Failed to store RTP packet with length: "
91 << packet_length;
92 return -1;
93 }
94
95 const uint16_t seq_num = (packet[2] << 8) + packet[3];
96
97 // If index we're about to overwrite contains a packet that has not
98 // yet been sent (probably pending in paced sender), we need to expand
99 // the buffer.
100 if (stored_packets_[prev_index_].length > 0 &&
101 stored_packets_[prev_index_].send_time == 0) {
102 size_t current_size = static_cast<uint16_t>(stored_packets_.size());
103 if (current_size < kMaxHistoryCapacity) {
104 size_t expanded_size = std::max(current_size * 3 / 2, current_size + 1);
105 expanded_size = std::min(expanded_size, kMaxHistoryCapacity);
106 Allocate(expanded_size);
107 // Causes discontinuity, but that's OK-ish. FindSeqNum() will still work,
108 // but may be slower - at least until buffer has wrapped around once.
109 prev_index_ = current_size;
110 }
111 }
112
113 // Store packet
114 // TODO(sprang): Overhaul this class and get rid of this copy step.
115 // (Finally introduce the RtpPacket class?)
116 memcpy(stored_packets_[prev_index_].data, packet, packet_length);
117 stored_packets_[prev_index_].length = packet_length;
118
119 stored_packets_[prev_index_].sequence_number = seq_num;
120 stored_packets_[prev_index_].time_ms =
121 (capture_time_ms > 0) ? capture_time_ms : clock_->TimeInMilliseconds();
122 stored_packets_[prev_index_].send_time = 0; // Packet not sent.
123 stored_packets_[prev_index_].storage_type = type;
124 stored_packets_[prev_index_].has_been_retransmitted = false;
125
126 ++prev_index_;
127 if (prev_index_ >= stored_packets_.size()) {
128 prev_index_ = 0;
129 }
130 return 0;
131 }
132
HasRTPPacket(uint16_t sequence_number) const133 bool RTPPacketHistory::HasRTPPacket(uint16_t sequence_number) const {
134 CriticalSectionScoped cs(critsect_.get());
135 if (!store_) {
136 return false;
137 }
138
139 int32_t index = 0;
140 bool found = FindSeqNum(sequence_number, &index);
141 if (!found) {
142 return false;
143 }
144
145 if (stored_packets_[index].length == 0) {
146 // Invalid length.
147 return false;
148 }
149 return true;
150 }
151
SetSent(uint16_t sequence_number)152 bool RTPPacketHistory::SetSent(uint16_t sequence_number) {
153 CriticalSectionScoped cs(critsect_.get());
154 if (!store_) {
155 return false;
156 }
157
158 int32_t index = 0;
159 bool found = FindSeqNum(sequence_number, &index);
160 if (!found) {
161 return false;
162 }
163
164 // Send time already set.
165 if (stored_packets_[index].send_time != 0) {
166 return false;
167 }
168
169 stored_packets_[index].send_time = clock_->TimeInMilliseconds();
170 return true;
171 }
172
GetPacketAndSetSendTime(uint16_t sequence_number,int64_t min_elapsed_time_ms,bool retransmit,uint8_t * packet,size_t * packet_length,int64_t * stored_time_ms)173 bool RTPPacketHistory::GetPacketAndSetSendTime(uint16_t sequence_number,
174 int64_t min_elapsed_time_ms,
175 bool retransmit,
176 uint8_t* packet,
177 size_t* packet_length,
178 int64_t* stored_time_ms) {
179 CriticalSectionScoped cs(critsect_.get());
180 RTC_CHECK_GE(*packet_length, static_cast<size_t>(IP_PACKET_SIZE));
181 if (!store_)
182 return false;
183
184 int32_t index = 0;
185 bool found = FindSeqNum(sequence_number, &index);
186 if (!found) {
187 LOG(LS_WARNING) << "No match for getting seqNum " << sequence_number;
188 return false;
189 }
190
191 size_t length = stored_packets_[index].length;
192 assert(length <= IP_PACKET_SIZE);
193 if (length == 0) {
194 LOG(LS_WARNING) << "No match for getting seqNum " << sequence_number
195 << ", len " << length;
196 return false;
197 }
198
199 // Verify elapsed time since last retrieve, but only for retransmissions and
200 // always send packet upon first retransmission request.
201 int64_t now = clock_->TimeInMilliseconds();
202 if (min_elapsed_time_ms > 0 && retransmit &&
203 stored_packets_[index].has_been_retransmitted &&
204 ((now - stored_packets_[index].send_time) < min_elapsed_time_ms)) {
205 return false;
206 }
207
208 if (retransmit) {
209 if (stored_packets_[index].storage_type == kDontRetransmit) {
210 // No bytes copied since this packet shouldn't be retransmitted or is
211 // of zero size.
212 return false;
213 }
214 stored_packets_[index].has_been_retransmitted = true;
215 }
216 stored_packets_[index].send_time = clock_->TimeInMilliseconds();
217 GetPacket(index, packet, packet_length, stored_time_ms);
218 return true;
219 }
220
GetPacket(int index,uint8_t * packet,size_t * packet_length,int64_t * stored_time_ms) const221 void RTPPacketHistory::GetPacket(int index,
222 uint8_t* packet,
223 size_t* packet_length,
224 int64_t* stored_time_ms) const {
225 // Get packet.
226 size_t length = stored_packets_[index].length;
227 memcpy(packet, stored_packets_[index].data, length);
228 *packet_length = length;
229 *stored_time_ms = stored_packets_[index].time_ms;
230 }
231
GetBestFittingPacket(uint8_t * packet,size_t * packet_length,int64_t * stored_time_ms)232 bool RTPPacketHistory::GetBestFittingPacket(uint8_t* packet,
233 size_t* packet_length,
234 int64_t* stored_time_ms) {
235 CriticalSectionScoped cs(critsect_.get());
236 if (!store_)
237 return false;
238 int index = FindBestFittingPacket(*packet_length);
239 if (index < 0)
240 return false;
241 GetPacket(index, packet, packet_length, stored_time_ms);
242 return true;
243 }
244
245 // private, lock should already be taken
FindSeqNum(uint16_t sequence_number,int32_t * index) const246 bool RTPPacketHistory::FindSeqNum(uint16_t sequence_number,
247 int32_t* index) const {
248 uint16_t temp_sequence_number = 0;
249 if (prev_index_ > 0) {
250 *index = prev_index_ - 1;
251 temp_sequence_number = stored_packets_[*index].sequence_number;
252 } else {
253 *index = stored_packets_.size() - 1;
254 temp_sequence_number = stored_packets_[*index].sequence_number; // wrap
255 }
256
257 int32_t idx = (prev_index_ - 1) - (temp_sequence_number - sequence_number);
258 if (idx >= 0 && idx < static_cast<int>(stored_packets_.size())) {
259 *index = idx;
260 temp_sequence_number = stored_packets_[*index].sequence_number;
261 }
262
263 if (temp_sequence_number != sequence_number) {
264 // We did not found a match, search all.
265 for (uint16_t m = 0; m < stored_packets_.size(); m++) {
266 if (stored_packets_[m].sequence_number == sequence_number) {
267 *index = m;
268 temp_sequence_number = stored_packets_[*index].sequence_number;
269 break;
270 }
271 }
272 }
273 if (temp_sequence_number == sequence_number) {
274 // We found a match.
275 return true;
276 }
277 return false;
278 }
279
FindBestFittingPacket(size_t size) const280 int RTPPacketHistory::FindBestFittingPacket(size_t size) const {
281 if (size < kMinPacketRequestBytes || stored_packets_.empty())
282 return -1;
283 size_t min_diff = std::numeric_limits<size_t>::max();
284 int best_index = -1; // Returned unchanged if we don't find anything.
285 for (size_t i = 0; i < stored_packets_.size(); ++i) {
286 if (stored_packets_[i].length == 0)
287 continue;
288 size_t diff = (stored_packets_[i].length > size)
289 ? (stored_packets_[i].length - size)
290 : (size - stored_packets_[i].length);
291 if (diff < min_diff) {
292 min_diff = diff;
293 best_index = static_cast<int>(i);
294 }
295 }
296 return best_index;
297 }
298
StoredPacket()299 RTPPacketHistory::StoredPacket::StoredPacket() {}
300
301 } // namespace webrtc
302