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 #ifndef MODULES_RTP_RTCP_SOURCE_RTP_PACKET_HISTORY_H_
12 #define MODULES_RTP_RTCP_SOURCE_RTP_PACKET_HISTORY_H_
13 
14 #include <deque>
15 #include <map>
16 #include <memory>
17 #include <set>
18 #include <vector>
19 
20 #include "api/function_view.h"
21 #include "modules/rtp_rtcp/include/rtp_rtcp_defines.h"
22 #include "rtc_base/constructor_magic.h"
23 #include "rtc_base/synchronization/mutex.h"
24 #include "rtc_base/thread_annotations.h"
25 
26 namespace webrtc {
27 
28 class Clock;
29 class RtpPacketToSend;
30 
31 class RtpPacketHistory {
32  public:
33   enum class StorageMode {
34     kDisabled,     // Don't store any packets.
35     kStoreAndCull  // Store up to |number_to_store| packets, but try to remove
36                    // packets as they time out or as signaled as received.
37   };
38 
39   // Snapshot indicating the state of a packet in the history.
40   struct PacketState {
41     PacketState();
42     PacketState(const PacketState&);
43     ~PacketState();
44 
45     uint16_t rtp_sequence_number = 0;
46     absl::optional<int64_t> send_time_ms;
47     int64_t capture_time_ms = 0;
48     uint32_t ssrc = 0;
49     size_t packet_size = 0;
50     // Number of times RE-transmitted, ie not including the first transmission.
51     size_t times_retransmitted = 0;
52     bool pending_transmission = false;
53   };
54 
55   // Maximum number of packets we ever allow in the history.
56   static constexpr size_t kMaxCapacity = 9600;
57   // Maximum number of entries in prioritized queue of padding packets.
58   static constexpr size_t kMaxPaddingtHistory = 63;
59   // Don't remove packets within max(1000ms, 3x RTT).
60   static constexpr int64_t kMinPacketDurationMs = 1000;
61   static constexpr int kMinPacketDurationRtt = 3;
62   // With kStoreAndCull, always remove packets after 3x max(1000ms, 3x rtt).
63   static constexpr int kPacketCullingDelayFactor = 3;
64 
65   RtpPacketHistory(Clock* clock, bool enable_padding_prio);
66   ~RtpPacketHistory();
67 
68   // Set/get storage mode. Note that setting the state will clear the history,
69   // even if setting the same state as is currently used.
70   void SetStorePacketsStatus(StorageMode mode, size_t number_to_store);
71   StorageMode GetStorageMode() const;
72 
73   // Set RTT, used to avoid premature retransmission and to prevent over-writing
74   // a packet in the history before we are reasonably sure it has been received.
75   void SetRtt(int64_t rtt_ms);
76 
77   // If |send_time| is set, packet was sent without using pacer, so state will
78   // be set accordingly.
79   void PutRtpPacket(std::unique_ptr<RtpPacketToSend> packet,
80                     absl::optional<int64_t> send_time_ms);
81 
82   // Gets stored RTP packet corresponding to the input |sequence number|.
83   // Returns nullptr if packet is not found or was (re)sent too recently.
84   std::unique_ptr<RtpPacketToSend> GetPacketAndSetSendTime(
85       uint16_t sequence_number);
86 
87   // Gets stored RTP packet corresponding to the input |sequence number|.
88   // Returns nullptr if packet is not found or was (re)sent too recently.
89   // If a packet copy is returned, it will be marked as pending transmission but
90   // does not update send time, that must be done by MarkPacketAsSent().
91   std::unique_ptr<RtpPacketToSend> GetPacketAndMarkAsPending(
92       uint16_t sequence_number);
93 
94   // In addition to getting packet and marking as sent, this method takes an
95   // encapsulator function that takes a reference to the packet and outputs a
96   // copy that may be wrapped in a container, eg RTX.
97   // If the the encapsulator returns nullptr, the retransmit is aborted and the
98   // packet will not be marked as pending.
99   std::unique_ptr<RtpPacketToSend> GetPacketAndMarkAsPending(
100       uint16_t sequence_number,
101       rtc::FunctionView<std::unique_ptr<RtpPacketToSend>(
102           const RtpPacketToSend&)> encapsulate);
103 
104   // Updates the send time for the given packet and increments the transmission
105   // counter. Marks the packet as no longer being in the pacer queue.
106   void MarkPacketAsSent(uint16_t sequence_number);
107 
108   // Similar to GetPacketAndSetSendTime(), but only returns a snapshot of the
109   // current state for packet, and never updates internal state.
110   absl::optional<PacketState> GetPacketState(uint16_t sequence_number) const;
111 
112   // Get the packet (if any) from the history, that is deemed most likely to
113   // the remote side. This is calculated from heuristics such as packet age
114   // and times retransmitted. Updated the send time of the packet, so is not
115   // a const method.
116   std::unique_ptr<RtpPacketToSend> GetPayloadPaddingPacket();
117 
118   // Same as GetPayloadPaddingPacket(void), but adds an encapsulation
119   // that can be used for instance to encapsulate the packet in an RTX
120   // container, or to abort getting the packet if the function returns
121   // nullptr.
122   std::unique_ptr<RtpPacketToSend> GetPayloadPaddingPacket(
123       rtc::FunctionView<std::unique_ptr<RtpPacketToSend>(
124           const RtpPacketToSend&)> encapsulate);
125 
126   // Cull packets that have been acknowledged as received by the remote end.
127   void CullAcknowledgedPackets(rtc::ArrayView<const uint16_t> sequence_numbers);
128 
129   // Mark packet as queued for transmission. This will prevent premature
130   // removal or duplicate retransmissions in the pacer queue.
131   // Returns true if status was set, false if packet was not found.
132   bool SetPendingTransmission(uint16_t sequence_number);
133 
134   // Remove all pending packets from the history, but keep storage mode and
135   // capacity.
136   void Clear();
137 
138  private:
139   struct MoreUseful;
140   class StoredPacket;
141   using PacketPrioritySet = std::set<StoredPacket*, MoreUseful>;
142 
143   class StoredPacket {
144    public:
145     StoredPacket(std::unique_ptr<RtpPacketToSend> packet,
146                  absl::optional<int64_t> send_time_ms,
147                  uint64_t insert_order);
148     StoredPacket(StoredPacket&&);
149     StoredPacket& operator=(StoredPacket&&);
150     ~StoredPacket();
151 
insert_order()152     uint64_t insert_order() const { return insert_order_; }
times_retransmitted()153     size_t times_retransmitted() const { return times_retransmitted_; }
154     void IncrementTimesRetransmitted(PacketPrioritySet* priority_set);
155 
156     // The time of last transmission, including retransmissions.
157     absl::optional<int64_t> send_time_ms_;
158 
159     // The actual packet.
160     std::unique_ptr<RtpPacketToSend> packet_;
161 
162     // True if the packet is currently in the pacer queue pending transmission.
163     bool pending_transmission_;
164 
165    private:
166     // Unique number per StoredPacket, incremented by one for each added
167     // packet. Used to sort on insert order.
168     uint64_t insert_order_;
169 
170     // Number of times RE-transmitted, ie excluding the first transmission.
171     size_t times_retransmitted_;
172   };
173   struct MoreUseful {
174     bool operator()(StoredPacket* lhs, StoredPacket* rhs) const;
175   };
176 
177   // Helper method used by GetPacketAndSetSendTime() and GetPacketState() to
178   // check if packet has too recently been sent.
179   bool VerifyRtt(const StoredPacket& packet, int64_t now_ms) const
180       RTC_EXCLUSIVE_LOCKS_REQUIRED(lock_);
181   void Reset() RTC_EXCLUSIVE_LOCKS_REQUIRED(lock_);
182   void CullOldPackets(int64_t now_ms) RTC_EXCLUSIVE_LOCKS_REQUIRED(lock_);
183   // Removes the packet from the history, and context/mapping that has been
184   // stored. Returns the RTP packet instance contained within the StoredPacket.
185   std::unique_ptr<RtpPacketToSend> RemovePacket(int packet_index)
186       RTC_EXCLUSIVE_LOCKS_REQUIRED(lock_);
187   int GetPacketIndex(uint16_t sequence_number) const
188       RTC_EXCLUSIVE_LOCKS_REQUIRED(lock_);
189   StoredPacket* GetStoredPacket(uint16_t sequence_number)
190       RTC_EXCLUSIVE_LOCKS_REQUIRED(lock_);
191   static PacketState StoredPacketToPacketState(
192       const StoredPacket& stored_packet);
193 
194   Clock* const clock_;
195   const bool enable_padding_prio_;
196   mutable Mutex lock_;
197   size_t number_to_store_ RTC_GUARDED_BY(lock_);
198   StorageMode mode_ RTC_GUARDED_BY(lock_);
199   int64_t rtt_ms_ RTC_GUARDED_BY(lock_);
200 
201   // Queue of stored packets, ordered by sequence number, with older packets in
202   // the front and new packets being added to the back. Note that there may be
203   // wrap-arounds so the back may have a lower sequence number.
204   // Packets may also be removed out-of-order, in which case there will be
205   // instances of StoredPacket with |packet_| set to nullptr. The first and last
206   // entry in the queue will however always be populated.
207   std::deque<StoredPacket> packet_history_ RTC_GUARDED_BY(lock_);
208 
209   // Total number of packets with inserted.
210   uint64_t packets_inserted_ RTC_GUARDED_BY(lock_);
211   // Objects from |packet_history_| ordered by "most likely to be useful", used
212   // in GetPayloadPaddingPacket().
213   PacketPrioritySet padding_priority_ RTC_GUARDED_BY(lock_);
214 
215   RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(RtpPacketHistory);
216 };
217 }  // namespace webrtc
218 #endif  // MODULES_RTP_RTCP_SOURCE_RTP_PACKET_HISTORY_H_
219