paced_sender.cc revision 0b9e29c87da2d9c1a3792d2c87197b0688b68e4e 
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/pacing/paced_sender.h"
12
13#include <assert.h>
14
15#include <map>
16#include <queue>
17#include <set>
18
19#include "webrtc/modules/include/module_common_types.h"
20#include "webrtc/modules/pacing/bitrate_prober.h"
21#include "webrtc/system_wrappers/include/clock.h"
22#include "webrtc/system_wrappers/include/critical_section_wrapper.h"
23#include "webrtc/system_wrappers/include/field_trial.h"
24#include "webrtc/system_wrappers/include/logging.h"
25
26namespace {
27// Time limit in milliseconds between packet bursts.
28const int64_t kMinPacketLimitMs = 5;
29
30// Upper cap on process interval, in case process has not been called in a long
31// time.
32const int64_t kMaxIntervalTimeMs = 30;
33
34}  // namespace
35
36namespace webrtc {
37namespace paced_sender {
38struct Packet {
39  Packet(RtpPacketSender::Priority priority,
40         uint32_t ssrc,
41         uint16_t seq_number,
42         int64_t capture_time_ms,
43         int64_t enqueue_time_ms,
44         size_t length_in_bytes,
45         bool retransmission,
46         uint64_t enqueue_order)
47      : priority(priority),
48        ssrc(ssrc),
49        sequence_number(seq_number),
50        capture_time_ms(capture_time_ms),
51        enqueue_time_ms(enqueue_time_ms),
52        bytes(length_in_bytes),
53        retransmission(retransmission),
54        enqueue_order(enqueue_order) {}
55
56  RtpPacketSender::Priority priority;
57  uint32_t ssrc;
58  uint16_t sequence_number;
59  int64_t capture_time_ms;
60  int64_t enqueue_time_ms;
61  size_t bytes;
62  bool retransmission;
63  uint64_t enqueue_order;
64  std::list<Packet>::iterator this_it;
65};
66
67// Used by priority queue to sort packets.
68struct Comparator {
69  bool operator()(const Packet* first, const Packet* second) {
70    // Highest prio = 0.
71    if (first->priority != second->priority)
72      return first->priority > second->priority;
73
74    // Retransmissions go first.
75    if (second->retransmission && !first->retransmission)
76      return true;
77
78    // Older frames have higher prio.
79    if (first->capture_time_ms != second->capture_time_ms)
80      return first->capture_time_ms > second->capture_time_ms;
81
82    return first->enqueue_order > second->enqueue_order;
83  }
84};
85
86// Class encapsulating a priority queue with some extensions.
87class PacketQueue {
88 public:
89  PacketQueue() : bytes_(0) {}
90  virtual ~PacketQueue() {}
91
92  void Push(const Packet& packet) {
93    if (!AddToDupeSet(packet)) {
94      return;
95    }
96    // Store packet in list, use pointers in priority queue for cheaper moves.
97    // Packets have a handle to its own iterator in the list, for easy removal
98    // when popping from queue.
99    packet_list_.push_front(packet);
100    std::list<Packet>::iterator it = packet_list_.begin();
101    it->this_it = it;          // Handle for direct removal from list.
102    prio_queue_.push(&(*it));  // Pointer into list.
103    bytes_ += packet.bytes;
104  }
105
106  const Packet& BeginPop() {
107    const Packet& packet = *prio_queue_.top();
108    prio_queue_.pop();
109    return packet;
110  }
111
112  void CancelPop(const Packet& packet) { prio_queue_.push(&(*packet.this_it)); }
113
114  void FinalizePop(const Packet& packet) {
115    RemoveFromDupeSet(packet);
116    bytes_ -= packet.bytes;
117    packet_list_.erase(packet.this_it);
118  }
119
120  bool Empty() const { return prio_queue_.empty(); }
121
122  size_t SizeInPackets() const { return prio_queue_.size(); }
123
124  uint64_t SizeInBytes() const { return bytes_; }
125
126  int64_t OldestEnqueueTime() const {
127    std::list<Packet>::const_reverse_iterator it = packet_list_.rbegin();
128    if (it == packet_list_.rend())
129      return 0;
130    return it->enqueue_time_ms;
131  }
132
133 private:
134  // Try to add a packet to the set of ssrc/seqno identifiers currently in the
135  // queue. Return true if inserted, false if this is a duplicate.
136  bool AddToDupeSet(const Packet& packet) {
137    SsrcSeqNoMap::iterator it = dupe_map_.find(packet.ssrc);
138    if (it == dupe_map_.end()) {
139      // First for this ssrc, just insert.
140      dupe_map_[packet.ssrc].insert(packet.sequence_number);
141      return true;
142    }
143
144    // Insert returns a pair, where second is a bool set to true if new element.
145    return it->second.insert(packet.sequence_number).second;
146  }
147
148  void RemoveFromDupeSet(const Packet& packet) {
149    SsrcSeqNoMap::iterator it = dupe_map_.find(packet.ssrc);
150    assert(it != dupe_map_.end());
151    it->second.erase(packet.sequence_number);
152    if (it->second.empty()) {
153      dupe_map_.erase(it);
154    }
155  }
156
157  // List of packets, in the order the were enqueued. Since dequeueing may
158  // occur out of order, use list instead of vector.
159  std::list<Packet> packet_list_;
160  // Priority queue of the packets, sorted according to Comparator.
161  // Use pointers into list, to avoid moving whole struct within heap.
162  std::priority_queue<Packet*, std::vector<Packet*>, Comparator> prio_queue_;
163  // Total number of bytes in the queue.
164  uint64_t bytes_;
165  // Map<ssrc, set<seq_no> >, for checking duplicates.
166  typedef std::map<uint32_t, std::set<uint16_t> > SsrcSeqNoMap;
167  SsrcSeqNoMap dupe_map_;
168};
169
170class IntervalBudget {
171 public:
172  explicit IntervalBudget(int initial_target_rate_kbps)
173      : target_rate_kbps_(initial_target_rate_kbps),
174        bytes_remaining_(0) {}
175
176  void set_target_rate_kbps(int target_rate_kbps) {
177    target_rate_kbps_ = target_rate_kbps;
178    bytes_remaining_ =
179        std::max(-kWindowMs * target_rate_kbps_ / 8, bytes_remaining_);
180  }
181
182  void IncreaseBudget(int64_t delta_time_ms) {
183    int64_t bytes = target_rate_kbps_ * delta_time_ms / 8;
184    if (bytes_remaining_ < 0) {
185      // We overused last interval, compensate this interval.
186      bytes_remaining_ = bytes_remaining_ + bytes;
187    } else {
188      // If we underused last interval we can't use it this interval.
189      bytes_remaining_ = bytes;
190    }
191  }
192
193  void UseBudget(size_t bytes) {
194    bytes_remaining_ = std::max(bytes_remaining_ - static_cast<int>(bytes),
195                                -kWindowMs * target_rate_kbps_ / 8);
196  }
197
198  size_t bytes_remaining() const {
199    return static_cast<size_t>(std::max(0, bytes_remaining_));
200  }
201
202  int target_rate_kbps() const { return target_rate_kbps_; }
203
204 private:
205  static const int kWindowMs = 500;
206
207  int target_rate_kbps_;
208  int bytes_remaining_;
209};
210}  // namespace paced_sender
211
212const float PacedSender::kDefaultPaceMultiplier = 2.5f;
213
214PacedSender::PacedSender(Clock* clock,
215                         Callback* callback,
216                         int bitrate_kbps,
217                         int max_bitrate_kbps,
218                         int min_bitrate_kbps)
219    : clock_(clock),
220      callback_(callback),
221      critsect_(CriticalSectionWrapper::CreateCriticalSection()),
222      paused_(false),
223      probing_enabled_(true),
224      media_budget_(new paced_sender::IntervalBudget(max_bitrate_kbps)),
225      padding_budget_(new paced_sender::IntervalBudget(min_bitrate_kbps)),
226      prober_(new BitrateProber()),
227      bitrate_bps_(1000 * bitrate_kbps),
228      time_last_update_us_(clock->TimeInMicroseconds()),
229      packets_(new paced_sender::PacketQueue()),
230      packet_counter_(0) {
231  UpdateBytesPerInterval(kMinPacketLimitMs);
232}
233
234PacedSender::~PacedSender() {}
235
236void PacedSender::Pause() {
237  CriticalSectionScoped cs(critsect_.get());
238  paused_ = true;
239}
240
241void PacedSender::Resume() {
242  CriticalSectionScoped cs(critsect_.get());
243  paused_ = false;
244}
245
246void PacedSender::SetProbingEnabled(bool enabled) {
247  assert(packet_counter_ == 0);
248  probing_enabled_ = enabled;
249}
250
251void PacedSender::UpdateBitrate(int bitrate_kbps,
252                                int max_bitrate_kbps,
253                                int min_bitrate_kbps) {
254  CriticalSectionScoped cs(critsect_.get());
255  media_budget_->set_target_rate_kbps(max_bitrate_kbps);
256  padding_budget_->set_target_rate_kbps(min_bitrate_kbps);
257  bitrate_bps_ = 1000 * bitrate_kbps;
258}
259
260void PacedSender::InsertPacket(RtpPacketSender::Priority priority,
261                               uint32_t ssrc,
262                               uint16_t sequence_number,
263                               int64_t capture_time_ms,
264                               size_t bytes,
265                               bool retransmission) {
266  CriticalSectionScoped cs(critsect_.get());
267
268  if (probing_enabled_ && !prober_->IsProbing()) {
269    prober_->SetEnabled(true);
270  }
271  prober_->MaybeInitializeProbe(bitrate_bps_);
272
273  if (capture_time_ms < 0) {
274    capture_time_ms = clock_->TimeInMilliseconds();
275  }
276
277  packets_->Push(paced_sender::Packet(
278      priority, ssrc, sequence_number, capture_time_ms,
279      clock_->TimeInMilliseconds(), bytes, retransmission, packet_counter_++));
280}
281
282int64_t PacedSender::ExpectedQueueTimeMs() const {
283  CriticalSectionScoped cs(critsect_.get());
284  int target_rate = media_budget_->target_rate_kbps();
285  assert(target_rate > 0);
286  return static_cast<int64_t>(packets_->SizeInBytes() * 8 / target_rate);
287}
288
289size_t PacedSender::QueueSizePackets() const {
290  CriticalSectionScoped cs(critsect_.get());
291  return packets_->SizeInPackets();
292}
293
294int64_t PacedSender::QueueInMs() const {
295  CriticalSectionScoped cs(critsect_.get());
296
297  int64_t oldest_packet = packets_->OldestEnqueueTime();
298  if (oldest_packet == 0)
299    return 0;
300
301  return clock_->TimeInMilliseconds() - oldest_packet;
302}
303
304int64_t PacedSender::TimeUntilNextProcess() {
305  CriticalSectionScoped cs(critsect_.get());
306  if (prober_->IsProbing()) {
307    int64_t ret = prober_->TimeUntilNextProbe(clock_->TimeInMilliseconds());
308    if (ret >= 0) {
309      return ret;
310    }
311  }
312  int64_t elapsed_time_us = clock_->TimeInMicroseconds() - time_last_update_us_;
313  int64_t elapsed_time_ms = (elapsed_time_us + 500) / 1000;
314  return std::max<int64_t>(kMinPacketLimitMs - elapsed_time_ms, 0);
315}
316
317int32_t PacedSender::Process() {
318  int64_t now_us = clock_->TimeInMicroseconds();
319  CriticalSectionScoped cs(critsect_.get());
320  int64_t elapsed_time_ms = (now_us - time_last_update_us_ + 500) / 1000;
321  time_last_update_us_ = now_us;
322  if (paused_)
323    return 0;
324  if (elapsed_time_ms > 0) {
325    int64_t delta_time_ms = std::min(kMaxIntervalTimeMs, elapsed_time_ms);
326    UpdateBytesPerInterval(delta_time_ms);
327  }
328  while (!packets_->Empty()) {
329    if (media_budget_->bytes_remaining() == 0 && !prober_->IsProbing()) {
330      return 0;
331    }
332
333    // Since we need to release the lock in order to send, we first pop the
334    // element from the priority queue but keep it in storage, so that we can
335    // reinsert it if send fails.
336    const paced_sender::Packet& packet = packets_->BeginPop();
337    if (SendPacket(packet)) {
338      // Send succeeded, remove it from the queue.
339      packets_->FinalizePop(packet);
340      if (prober_->IsProbing()) {
341        return 0;
342      }
343    } else {
344      // Send failed, put it back into the queue.
345      packets_->CancelPop(packet);
346      return 0;
347    }
348  }
349
350  if (!packets_->Empty())
351    return 0;
352
353  size_t padding_needed;
354  if (prober_->IsProbing())
355    padding_needed = prober_->RecommendedPacketSize();
356  else
357    padding_needed = padding_budget_->bytes_remaining();
358
359  if (padding_needed > 0)
360    SendPadding(static_cast<size_t>(padding_needed));
361  return 0;
362}
363
364bool PacedSender::SendPacket(const paced_sender::Packet& packet) {
365  critsect_->Leave();
366  const bool success = callback_->TimeToSendPacket(packet.ssrc,
367                                                   packet.sequence_number,
368                                                   packet.capture_time_ms,
369                                                   packet.retransmission);
370  critsect_->Enter();
371
372  if (success) {
373    // Update media bytes sent.
374    prober_->PacketSent(clock_->TimeInMilliseconds(), packet.bytes);
375    media_budget_->UseBudget(packet.bytes);
376    padding_budget_->UseBudget(packet.bytes);
377  }
378
379  return success;
380}
381
382void PacedSender::SendPadding(size_t padding_needed) {
383  critsect_->Leave();
384  size_t bytes_sent = callback_->TimeToSendPadding(padding_needed);
385  critsect_->Enter();
386
387  if (bytes_sent > 0) {
388    prober_->PacketSent(clock_->TimeInMilliseconds(), bytes_sent);
389    media_budget_->UseBudget(bytes_sent);
390    padding_budget_->UseBudget(bytes_sent);
391  }
392}
393
394void PacedSender::UpdateBytesPerInterval(int64_t delta_time_ms) {
395  media_budget_->IncreaseBudget(delta_time_ms);
396  padding_budget_->IncreaseBudget(delta_time_ms);
397}
398}  // namespace webrtc
399