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 #include "net/third_party/quiche/src/quic/core/frames/quic_ack_frame.h"
6
7 #include "net/third_party/quiche/src/quic/core/quic_constants.h"
8 #include "net/third_party/quiche/src/quic/core/quic_interval.h"
9 #include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h"
10 #include "net/third_party/quiche/src/quic/platform/api/quic_flag_utils.h"
11
12 namespace quic {
13
14 namespace {
15
16 const QuicPacketCount kMaxPrintRange = 128;
17
18 } // namespace
19
IsAwaitingPacket(const QuicAckFrame & ack_frame,QuicPacketNumber packet_number,QuicPacketNumber peer_least_packet_awaiting_ack)20 bool IsAwaitingPacket(const QuicAckFrame& ack_frame,
21 QuicPacketNumber packet_number,
22 QuicPacketNumber peer_least_packet_awaiting_ack) {
23 DCHECK(packet_number.IsInitialized());
24 return (!peer_least_packet_awaiting_ack.IsInitialized() ||
25 packet_number >= peer_least_packet_awaiting_ack) &&
26 !ack_frame.packets.Contains(packet_number);
27 }
28
29 QuicAckFrame::QuicAckFrame() = default;
30
31 QuicAckFrame::QuicAckFrame(const QuicAckFrame& other) = default;
32
~QuicAckFrame()33 QuicAckFrame::~QuicAckFrame() {}
34
operator <<(std::ostream & os,const QuicAckFrame & ack_frame)35 std::ostream& operator<<(std::ostream& os, const QuicAckFrame& ack_frame) {
36 os << "{ largest_acked: " << LargestAcked(ack_frame)
37 << ", ack_delay_time: " << ack_frame.ack_delay_time.ToMicroseconds()
38 << ", packets: [ " << ack_frame.packets << " ]"
39 << ", received_packets: [ ";
40 for (const std::pair<QuicPacketNumber, QuicTime>& p :
41 ack_frame.received_packet_times) {
42 os << p.first << " at " << p.second.ToDebuggingValue() << " ";
43 }
44 os << " ]";
45 os << ", ecn_counters_populated: " << ack_frame.ecn_counters_populated;
46 if (ack_frame.ecn_counters_populated) {
47 os << ", ect_0_count: " << ack_frame.ect_0_count
48 << ", ect_1_count: " << ack_frame.ect_1_count
49 << ", ecn_ce_count: " << ack_frame.ecn_ce_count;
50 }
51
52 os << " }\n";
53 return os;
54 }
55
Clear()56 void QuicAckFrame::Clear() {
57 largest_acked.Clear();
58 ack_delay_time = QuicTime::Delta::Infinite();
59 received_packet_times.clear();
60 packets.Clear();
61 }
62
PacketNumberQueue()63 PacketNumberQueue::PacketNumberQueue() {}
64 PacketNumberQueue::PacketNumberQueue(const PacketNumberQueue& other) = default;
65 PacketNumberQueue::PacketNumberQueue(PacketNumberQueue&& other) = default;
~PacketNumberQueue()66 PacketNumberQueue::~PacketNumberQueue() {}
67
68 PacketNumberQueue& PacketNumberQueue::operator=(
69 const PacketNumberQueue& other) = default;
70 PacketNumberQueue& PacketNumberQueue::operator=(PacketNumberQueue&& other) =
71 default;
72
Add(QuicPacketNumber packet_number)73 void PacketNumberQueue::Add(QuicPacketNumber packet_number) {
74 if (!packet_number.IsInitialized()) {
75 return;
76 }
77 packet_number_intervals_.AddOptimizedForAppend(packet_number,
78 packet_number + 1);
79 }
80
AddRange(QuicPacketNumber lower,QuicPacketNumber higher)81 void PacketNumberQueue::AddRange(QuicPacketNumber lower,
82 QuicPacketNumber higher) {
83 if (!lower.IsInitialized() || !higher.IsInitialized() || lower >= higher) {
84 return;
85 }
86
87 packet_number_intervals_.AddOptimizedForAppend(lower, higher);
88 }
89
RemoveUpTo(QuicPacketNumber higher)90 bool PacketNumberQueue::RemoveUpTo(QuicPacketNumber higher) {
91 if (!higher.IsInitialized() || Empty()) {
92 return false;
93 }
94 return packet_number_intervals_.TrimLessThan(higher);
95 }
96
RemoveSmallestInterval()97 void PacketNumberQueue::RemoveSmallestInterval() {
98 // TODO(wub): Move this QUIC_BUG to upper level.
99 QUIC_BUG_IF(packet_number_intervals_.Size() < 2)
100 << (Empty() ? "No intervals to remove."
101 : "Can't remove the last interval.");
102 packet_number_intervals_.PopFront();
103 }
104
Clear()105 void PacketNumberQueue::Clear() {
106 packet_number_intervals_.Clear();
107 }
108
Contains(QuicPacketNumber packet_number) const109 bool PacketNumberQueue::Contains(QuicPacketNumber packet_number) const {
110 if (!packet_number.IsInitialized()) {
111 return false;
112 }
113 return packet_number_intervals_.Contains(packet_number);
114 }
115
Empty() const116 bool PacketNumberQueue::Empty() const {
117 return packet_number_intervals_.Empty();
118 }
119
Min() const120 QuicPacketNumber PacketNumberQueue::Min() const {
121 DCHECK(!Empty());
122 return packet_number_intervals_.begin()->min();
123 }
124
Max() const125 QuicPacketNumber PacketNumberQueue::Max() const {
126 DCHECK(!Empty());
127 return packet_number_intervals_.rbegin()->max() - 1;
128 }
129
NumPacketsSlow() const130 QuicPacketCount PacketNumberQueue::NumPacketsSlow() const {
131 QuicPacketCount n_packets = 0;
132 for (const auto& interval : packet_number_intervals_) {
133 n_packets += interval.Length();
134 }
135 return n_packets;
136 }
137
NumIntervals() const138 size_t PacketNumberQueue::NumIntervals() const {
139 return packet_number_intervals_.Size();
140 }
141
begin() const142 PacketNumberQueue::const_iterator PacketNumberQueue::begin() const {
143 return packet_number_intervals_.begin();
144 }
145
end() const146 PacketNumberQueue::const_iterator PacketNumberQueue::end() const {
147 return packet_number_intervals_.end();
148 }
149
rbegin() const150 PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rbegin() const {
151 return packet_number_intervals_.rbegin();
152 }
153
rend() const154 PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rend() const {
155 return packet_number_intervals_.rend();
156 }
157
LastIntervalLength() const158 QuicPacketCount PacketNumberQueue::LastIntervalLength() const {
159 DCHECK(!Empty());
160 return packet_number_intervals_.rbegin()->Length();
161 }
162
163 // Largest min...max range for packet numbers where we print the numbers
164 // explicitly. If bigger than this, we print as a range [a,d] rather
165 // than [a b c d]
166
operator <<(std::ostream & os,const PacketNumberQueue & q)167 std::ostream& operator<<(std::ostream& os, const PacketNumberQueue& q) {
168 for (const QuicInterval<QuicPacketNumber>& interval : q) {
169 // Print as a range if there is a pathological condition.
170 if ((interval.min() >= interval.max()) ||
171 (interval.max() - interval.min() > kMaxPrintRange)) {
172 // If min>max, it's really a bug, so QUIC_BUG it to
173 // catch it in development.
174 QUIC_BUG_IF(interval.min() >= interval.max())
175 << "Ack Range minimum (" << interval.min() << "Not less than max ("
176 << interval.max() << ")";
177 // print range as min...max rather than full list.
178 // in the event of a bug, the list could be very big.
179 os << interval.min() << "..." << (interval.max() - 1) << " ";
180 } else {
181 for (QuicPacketNumber packet_number = interval.min();
182 packet_number < interval.max(); ++packet_number) {
183 os << packet_number << " ";
184 }
185 }
186 }
187 return os;
188 }
189
190 } // namespace quic
191