1 /* 2 * Copyright (c) 2022 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_PRIORITIZED_PACKET_QUEUE_H_ 12 #define MODULES_PACING_PRIORITIZED_PACKET_QUEUE_H_ 13 14 #include <stddef.h> 15 16 #include <deque> 17 #include <list> 18 #include <memory> 19 #include <unordered_map> 20 21 #include "api/units/data_size.h" 22 #include "api/units/time_delta.h" 23 #include "api/units/timestamp.h" 24 #include "modules/rtp_rtcp/source/rtp_packet_to_send.h" 25 26 namespace webrtc { 27 28 class PrioritizedPacketQueue { 29 public: 30 explicit PrioritizedPacketQueue(Timestamp creation_time); 31 PrioritizedPacketQueue(const PrioritizedPacketQueue&) = delete; 32 PrioritizedPacketQueue& operator=(const PrioritizedPacketQueue&) = delete; 33 34 // Add a packet to the queue. The enqueue time is used for queue time stats 35 // and to report the leading packet enqueue time per packet type. 36 void Push(Timestamp enqueue_time, std::unique_ptr<RtpPacketToSend> packet); 37 38 // Remove the next packet from the queue. Packets a prioritized first 39 // according to packet type, in the following order: 40 // - audio, retransmissions, video / fec, padding 41 // For each packet type, we use one FIFO-queue per SSRC and emit from 42 // those queues in a round-robin fashion. 43 std::unique_ptr<RtpPacketToSend> Pop(); 44 45 // Number of packets in the queue. 46 int SizeInPackets() const; 47 48 // Sum of all payload bytes in the queue, where the payload is calculated 49 // as `packet->payload_size() + packet->padding_size()`. 50 DataSize SizeInPayloadBytes() const; 51 52 // Convenience method for `SizeInPackets() == 0`. 53 bool Empty() const; 54 55 // Total packets in the queue per media type (RtpPacketMediaType values are 56 // used as lookup index). 57 const std::array<int, kNumMediaTypes>& SizeInPacketsPerRtpPacketMediaType() 58 const; 59 60 // The enqueue time of the next packet this queue will return via the Pop() 61 // method, for the given packet type. If queue has no packets, of that type, 62 // returns Timestamp::MinusInfinity(). 63 Timestamp LeadingPacketEnqueueTime(RtpPacketMediaType type) const; 64 65 // Enqueue time of the oldest packet in the queue, 66 // Timestamp::MinusInfinity() if queue is empty. 67 Timestamp OldestEnqueueTime() const; 68 69 // Average queue time for the packets currently in the queue. 70 // The queuing time is calculated from Push() to the last UpdateQueueTime() 71 // call - with any time spent in a paused state subtracted. 72 // Returns TimeDelta::Zero() for an empty queue. 73 TimeDelta AverageQueueTime() const; 74 75 // Called during packet processing or when pause stats changes. Since the 76 // AverageQueueTime() method does not look at the wall time, this method 77 // needs to be called before querying queue time. 78 void UpdateAverageQueueTime(Timestamp now); 79 80 // Set the pause state, while `paused` is true queuing time is not counted. 81 void SetPauseState(bool paused, Timestamp now); 82 83 private: 84 static constexpr int kNumPriorityLevels = 4; 85 86 class QueuedPacket { 87 public: 88 DataSize PacketSize() const; 89 90 std::unique_ptr<RtpPacketToSend> packet; 91 Timestamp enqueue_time; 92 std::list<Timestamp>::iterator enqueue_time_iterator; 93 }; 94 95 // Class containing packets for an RTP stream. 96 // For each priority level, packets are simply stored in a fifo queue. 97 class StreamQueue { 98 public: 99 explicit StreamQueue(Timestamp creation_time); 100 StreamQueue(StreamQueue&&) = default; 101 StreamQueue& operator=(StreamQueue&&) = default; 102 103 StreamQueue(const StreamQueue&) = delete; 104 StreamQueue& operator=(const StreamQueue&) = delete; 105 106 // Enqueue packet at the given priority level. Returns true if the packet 107 // count for that priority level went from zero to non-zero. 108 bool EnqueuePacket(QueuedPacket packet, int priority_level); 109 110 QueuedPacket DequePacket(int priority_level); 111 112 bool HasPacketsAtPrio(int priority_level) const; 113 bool IsEmpty() const; 114 Timestamp LeadingPacketEnqueueTime(int priority_level) const; 115 Timestamp LastEnqueueTime() const; 116 117 private: 118 std::deque<QueuedPacket> packets_[kNumPriorityLevels]; 119 Timestamp last_enqueue_time_; 120 }; 121 122 // Cumulative sum, over all packets, of time spent in the queue. 123 TimeDelta queue_time_sum_; 124 // Cumulative sum of time the queue has spent in a paused state. 125 TimeDelta pause_time_sum_; 126 // Total number of packets stored in this queue. 127 int size_packets_; 128 // Total number of packets stored in this queue per RtpPacketMediaType. 129 std::array<int, kNumMediaTypes> size_packets_per_media_type_; 130 // Sum of payload sizes for all packts stored in this queue. 131 DataSize size_payload_; 132 // The last time queue/pause time sums were updated. 133 Timestamp last_update_time_; 134 bool paused_; 135 136 // Last time `streams_` was culled for inactive streams. 137 Timestamp last_culling_time_; 138 139 // Map from SSRC to packet queues for the associated RTP stream. 140 std::unordered_map<uint32_t, std::unique_ptr<StreamQueue>> streams_; 141 142 // For each priority level, a queue of StreamQueues which have at least one 143 // packet pending for that prio level. 144 std::deque<StreamQueue*> streams_by_prio_[kNumPriorityLevels]; 145 146 // The first index into `stream_by_prio_` that is non-empty. 147 int top_active_prio_level_; 148 149 // Ordered list of enqueue times. Additions are always increasing and added to 150 // the end. QueuedPacket instances have a iterators into this list for fast 151 // removal. 152 std::list<Timestamp> enqueue_times_; 153 }; 154 155 } // namespace webrtc 156 157 #endif // MODULES_PACING_PRIORITIZED_PACKET_QUEUE_H_ 158