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