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 #ifndef MODULES_PACING_ROUND_ROBIN_PACKET_QUEUE_H_ 12 #define MODULES_PACING_ROUND_ROBIN_PACKET_QUEUE_H_ 13 14 #include <stddef.h> 15 #include <stdint.h> 16 17 #include <list> 18 #include <map> 19 #include <memory> 20 #include <queue> 21 #include <set> 22 23 #include "absl/types/optional.h" 24 #include "api/transport/webrtc_key_value_config.h" 25 #include "api/units/data_size.h" 26 #include "api/units/time_delta.h" 27 #include "api/units/timestamp.h" 28 #include "modules/rtp_rtcp/include/rtp_rtcp_defines.h" 29 #include "modules/rtp_rtcp/source/rtp_packet_to_send.h" 30 #include "system_wrappers/include/clock.h" 31 32 namespace webrtc { 33 34 class RoundRobinPacketQueue { 35 public: 36 RoundRobinPacketQueue(Timestamp start_time, 37 const WebRtcKeyValueConfig* field_trials); 38 ~RoundRobinPacketQueue(); 39 40 void Push(int priority, 41 Timestamp enqueue_time, 42 uint64_t enqueue_order, 43 std::unique_ptr<RtpPacketToSend> packet); 44 std::unique_ptr<RtpPacketToSend> Pop(); 45 46 bool Empty() const; 47 size_t SizeInPackets() const; 48 DataSize Size() const; 49 // If the next packet, that would be returned by Pop() if called 50 // now, is an audio packet this method returns the enqueue time 51 // of that packet. If queue is empty or top packet is not audio, 52 // returns nullopt. 53 absl::optional<Timestamp> LeadingAudioPacketEnqueueTime() const; 54 55 Timestamp OldestEnqueueTime() const; 56 TimeDelta AverageQueueTime() const; 57 void UpdateQueueTime(Timestamp now); 58 void SetPauseState(bool paused, Timestamp now); 59 void SetIncludeOverhead(); 60 void SetTransportOverhead(DataSize overhead_per_packet); 61 62 private: 63 struct QueuedPacket { 64 public: 65 QueuedPacket(int priority, 66 Timestamp enqueue_time, 67 uint64_t enqueue_order, 68 std::multiset<Timestamp>::iterator enqueue_time_it, 69 std::unique_ptr<RtpPacketToSend> packet); 70 QueuedPacket(const QueuedPacket& rhs); 71 ~QueuedPacket(); 72 73 bool operator<(const QueuedPacket& other) const; 74 75 int Priority() const; 76 RtpPacketMediaType Type() const; 77 uint32_t Ssrc() const; 78 Timestamp EnqueueTime() const; 79 bool IsRetransmission() const; 80 uint64_t EnqueueOrder() const; 81 RtpPacketToSend* RtpPacket() const; 82 83 std::multiset<Timestamp>::iterator EnqueueTimeIterator() const; 84 void UpdateEnqueueTimeIterator(std::multiset<Timestamp>::iterator it); 85 void SubtractPauseTime(TimeDelta pause_time_sum); 86 87 private: 88 int priority_; 89 Timestamp enqueue_time_; // Absolute time of pacer queue entry. 90 uint64_t enqueue_order_; 91 bool is_retransmission_; // Cached for performance. 92 std::multiset<Timestamp>::iterator enqueue_time_it_; 93 // Raw pointer since priority_queue doesn't allow for moving 94 // out of the container. 95 RtpPacketToSend* owned_packet_; 96 }; 97 98 class PriorityPacketQueue : public std::priority_queue<QueuedPacket> { 99 public: 100 using const_iterator = container_type::const_iterator; 101 const_iterator begin() const; 102 const_iterator end() const; 103 }; 104 105 struct StreamPrioKey { StreamPrioKeyStreamPrioKey106 StreamPrioKey(int priority, DataSize size) 107 : priority(priority), size(size) {} 108 109 bool operator<(const StreamPrioKey& other) const { 110 if (priority != other.priority) 111 return priority < other.priority; 112 return size < other.size; 113 } 114 115 const int priority; 116 const DataSize size; 117 }; 118 119 struct Stream { 120 Stream(); 121 Stream(const Stream&); 122 123 virtual ~Stream(); 124 125 DataSize size; 126 uint32_t ssrc; 127 128 PriorityPacketQueue packet_queue; 129 130 // Whenever a packet is inserted for this stream we check if |priority_it| 131 // points to an element in |stream_priorities_|, and if it does it means 132 // this stream has already been scheduled, and if the scheduled priority is 133 // lower than the priority of the incoming packet we reschedule this stream 134 // with the higher priority. 135 std::multimap<StreamPrioKey, uint32_t>::iterator priority_it; 136 }; 137 138 void Push(QueuedPacket packet); 139 140 DataSize PacketSize(const QueuedPacket& packet) const; 141 void MaybePromoteSinglePacketToNormalQueue(); 142 143 Stream* GetHighestPriorityStream(); 144 145 // Just used to verify correctness. 146 bool IsSsrcScheduled(uint32_t ssrc) const; 147 148 DataSize transport_overhead_per_packet_; 149 150 Timestamp time_last_updated_; 151 152 bool paused_; 153 size_t size_packets_; 154 DataSize size_; 155 DataSize max_size_; 156 TimeDelta queue_time_sum_; 157 TimeDelta pause_time_sum_; 158 159 // A map of streams used to prioritize from which stream to send next. We use 160 // a multimap instead of a priority_queue since the priority of a stream can 161 // change as a new packet is inserted, and a multimap allows us to remove and 162 // then reinsert a StreamPrioKey if the priority has increased. 163 std::multimap<StreamPrioKey, uint32_t> stream_priorities_; 164 165 // A map of SSRCs to Streams. 166 std::map<uint32_t, Stream> streams_; 167 168 // The enqueue time of every packet currently in the queue. Used to figure out 169 // the age of the oldest packet in the queue. 170 std::multiset<Timestamp> enqueue_times_; 171 172 absl::optional<QueuedPacket> single_packet_queue_; 173 174 bool include_overhead_; 175 }; 176 } // namespace webrtc 177 178 #endif // MODULES_PACING_ROUND_ROBIN_PACKET_QUEUE_H_ 179