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_PACKET_QUEUE2_H_
12 #define MODULES_PACING_PACKET_QUEUE2_H_
13 
14 #include <map>
15 #include <queue>
16 #include <set>
17 
18 #include "modules/pacing/packet_queue.h"
19 #include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
20 
21 namespace webrtc {
22 
23 class PacketQueue2 : public PacketQueue {
24  public:
25   explicit PacketQueue2(const Clock* clock);
26   ~PacketQueue2() override;
27 
28   using Packet = PacketQueue::Packet;
29 
30   void Push(const Packet& packet) override;
31   const Packet& BeginPop() override;
32   void CancelPop(const Packet& packet) override;
33   void FinalizePop(const Packet& packet) override;
34 
35   bool Empty() const override;
36   size_t SizeInPackets() const override;
37   uint64_t SizeInBytes() const override;
38 
39   int64_t OldestEnqueueTimeMs() const override;
40   int64_t AverageQueueTimeMs() const override;
41   void UpdateQueueTime(int64_t timestamp_ms) override;
42   void SetPauseState(bool paused, int64_t timestamp_ms) override;
43 
44   struct StreamPrioKey {
45     StreamPrioKey() = default;
StreamPrioKeyStreamPrioKey46     StreamPrioKey(RtpPacketSender::Priority priority, int64_t bytes)
47         : priority(priority), bytes(bytes) {}
48 
49     bool operator<(const StreamPrioKey& other) const {
50       if (priority != other.priority)
51         return priority < other.priority;
52       return bytes > other.bytes;
53     }
54 
55     const RtpPacketSender::Priority priority;
56     const size_t bytes;
57   };
58 
59   struct Stream {
60     Stream();
61 
62     virtual ~Stream();
63 
64     size_t bytes;
65     uint32_t ssrc;
66     std::priority_queue<Packet> packet_queue;
67 
68     // Whenever a packet is inserted for this stream we check if |priority_it|
69     // points to an element in |stream_priorities_|, and if it does it means
70     // this stream has already been scheduled, and if the scheduled priority is
71     // lower than the priority of the incoming packet we reschedule this stream
72     // with the higher priority.
73     std::multimap<StreamPrioKey, uint32_t>::iterator priority_it;
74   };
75 
76  private:
77   static constexpr size_t kMaxLeadingBytes = 1400;
78 
79   Stream* GetHighestPriorityStream();
80 
81   // Just used to verify correctness.
82   bool IsSsrcScheduled(uint32_t ssrc) const;
83 
84   const Clock* const clock_;
85   int64_t time_last_updated_;
86   rtc::Optional<Packet> pop_packet_;
87   rtc::Optional<Stream*> pop_stream_;
88 
89   bool paused_ = false;
90   size_t size_packets_ = 0;
91   size_t size_bytes_ = 0;
92   size_t max_bytes_ = kMaxLeadingBytes;
93   int64_t queue_time_sum_ms_ = 0;
94   int64_t pause_time_sum_ms_ = 0;
95 
96   // A map of streams used to prioritize from which stream to send next. We use
97   // a multimap instead of a priority_queue since the priority of a stream can
98   // change as a new packet is inserted, and a multimap allows us to remove and
99   // then reinsert a StreamPrioKey if the priority has increased.
100   std::multimap<StreamPrioKey, uint32_t> stream_priorities_;
101 
102   // A map of SSRCs to Streams.
103   std::map<uint32_t, Stream> streams_;
104 
105   // The enqueue time of every packet currently in the queue. Used to figure out
106   // the age of the oldest packet in the queue.
107   std::multiset<int64_t> enqueue_times_;
108 };
109 }  // namespace webrtc
110 
111 #endif  // MODULES_PACING_PACKET_QUEUE2_H_
112