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