1 // Copyright (c) 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef QUICHE_QUIC_CORE_FRAMES_QUIC_ACK_FRAME_H_
6 #define QUICHE_QUIC_CORE_FRAMES_QUIC_ACK_FRAME_H_
7
8 #include <ostream>
9
10 #include "quiche/quic/core/quic_interval.h"
11 #include "quiche/quic/core/quic_interval_set.h"
12 #include "quiche/quic/core/quic_types.h"
13 #include "quiche/quic/platform/api/quic_export.h"
14 #include "quiche/quic/platform/api/quic_flags.h"
15
16 namespace quic {
17
18 // A sequence of packet numbers where each number is unique. Intended to be used
19 // in a sliding window fashion, where smaller old packet numbers are removed and
20 // larger new packet numbers are added, with the occasional random access.
21 class QUICHE_EXPORT PacketNumberQueue {
22 public:
23 PacketNumberQueue();
24 PacketNumberQueue(const PacketNumberQueue& other);
25 PacketNumberQueue(PacketNumberQueue&& other);
26 ~PacketNumberQueue();
27
28 PacketNumberQueue& operator=(const PacketNumberQueue& other);
29 PacketNumberQueue& operator=(PacketNumberQueue&& other);
30
31 using const_iterator = QuicIntervalSet<QuicPacketNumber>::const_iterator;
32 using const_reverse_iterator =
33 QuicIntervalSet<QuicPacketNumber>::const_reverse_iterator;
34
35 // Adds |packet_number| to the set of packets in the queue.
36 void Add(QuicPacketNumber packet_number);
37
38 // Adds packets between [lower, higher) to the set of packets in the queue.
39 // No-op if |higher| < |lower|.
40 // NOTE(wub): Only used in tests as of Nov 2019.
41 void AddRange(QuicPacketNumber lower, QuicPacketNumber higher);
42
43 // Removes packets with values less than |higher| from the set of packets in
44 // the queue. Returns true if packets were removed.
45 bool RemoveUpTo(QuicPacketNumber higher);
46
47 // Removes the smallest interval in the queue.
48 void RemoveSmallestInterval();
49
50 // Clear this packet number queue.
51 void Clear();
52
53 // Returns true if the queue contains |packet_number|.
54 bool Contains(QuicPacketNumber packet_number) const;
55
56 // Returns true if the queue is empty.
57 bool Empty() const;
58
59 // Returns the minimum packet number stored in the queue. It is undefined
60 // behavior to call this if the queue is empty.
61 QuicPacketNumber Min() const;
62
63 // Returns the maximum packet number stored in the queue. It is undefined
64 // behavior to call this if the queue is empty.
65 QuicPacketNumber Max() const;
66
67 // Returns the number of unique packets stored in the queue. Inefficient; only
68 // exposed for testing.
69 QuicPacketCount NumPacketsSlow() const;
70
71 // Returns the number of disjoint packet number intervals contained in the
72 // queue.
73 size_t NumIntervals() const;
74
75 // Returns the length of last interval.
76 QuicPacketCount LastIntervalLength() const;
77
78 // Returns iterators over the packet number intervals.
79 const_iterator begin() const;
80 const_iterator end() const;
81 const_reverse_iterator rbegin() const;
82 const_reverse_iterator rend() const;
83
84 friend QUICHE_EXPORT std::ostream& operator<<(std::ostream& os,
85 const PacketNumberQueue& q);
86
87 private:
88 QuicIntervalSet<QuicPacketNumber> packet_number_intervals_;
89 };
90
91 struct QUICHE_EXPORT QuicAckFrame {
92 QuicAckFrame();
93 QuicAckFrame(const QuicAckFrame& other);
94 ~QuicAckFrame();
95
96 void Clear();
97
98 friend QUICHE_EXPORT std::ostream& operator<<(std::ostream& os,
99 const QuicAckFrame& ack_frame);
100
101 // The highest packet number we've observed from the peer. When |packets| is
102 // not empty, it should always be equal to packets.Max(). The |LargestAcked|
103 // function ensures this invariant in debug mode.
104 QuicPacketNumber largest_acked;
105
106 // Time elapsed since largest_observed() was received until this Ack frame was
107 // sent.
108 QuicTime::Delta ack_delay_time = QuicTime::Delta::Infinite();
109
110 // Vector of <packet_number, time> for when packets arrived.
111 // For IETF versions, packet numbers and timestamps in this vector are both in
112 // ascending orders. Packets received out of order are not saved here.
113 PacketTimeVector received_packet_times;
114
115 // Set of packets.
116 PacketNumberQueue packets;
117
118 // ECN counters.
119 std::optional<QuicEcnCounts> ecn_counters;
120 };
121
122 // The highest acked packet number we've observed from the peer. If no packets
123 // have been observed, return 0.
LargestAcked(const QuicAckFrame & frame)124 inline QUICHE_EXPORT QuicPacketNumber LargestAcked(const QuicAckFrame& frame) {
125 QUICHE_DCHECK(frame.packets.Empty() ||
126 frame.packets.Max() == frame.largest_acked);
127 return frame.largest_acked;
128 }
129
130 // True if the packet number is greater than largest_observed or is listed
131 // as missing.
132 // Always returns false for packet numbers less than least_unacked.
133 QUICHE_EXPORT bool IsAwaitingPacket(
134 const QuicAckFrame& ack_frame, QuicPacketNumber packet_number,
135 QuicPacketNumber peer_least_packet_awaiting_ack);
136
137 } // namespace quic
138
139 #endif // QUICHE_QUIC_CORE_FRAMES_QUIC_ACK_FRAME_H_
140