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 "quiche/quic/core/frames/quic_ack_frame.h"
6
7 #include "quiche/quic/core/quic_constants.h"
8 #include "quiche/quic/core/quic_interval.h"
9 #include "quiche/quic/platform/api/quic_bug_tracker.h"
10 #include "quiche/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 QUICHE_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.has_value();
46 if (ack_frame.ecn_counters.has_value()) {
47 os << ", ect_0_count: " << ack_frame.ecn_counters->ect0
48 << ", ect_1_count: " << ack_frame.ecn_counters->ect1
49 << ", ecn_ce_count: " << ack_frame.ecn_counters->ce;
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(quic_bug_12614_1, 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() { packet_number_intervals_.Clear(); }
106
Contains(QuicPacketNumber packet_number) const107 bool PacketNumberQueue::Contains(QuicPacketNumber packet_number) const {
108 if (!packet_number.IsInitialized()) {
109 return false;
110 }
111 return packet_number_intervals_.Contains(packet_number);
112 }
113
Empty() const114 bool PacketNumberQueue::Empty() const {
115 return packet_number_intervals_.Empty();
116 }
117
Min() const118 QuicPacketNumber PacketNumberQueue::Min() const {
119 QUICHE_DCHECK(!Empty());
120 return packet_number_intervals_.begin()->min();
121 }
122
Max() const123 QuicPacketNumber PacketNumberQueue::Max() const {
124 QUICHE_DCHECK(!Empty());
125 return packet_number_intervals_.rbegin()->max() - 1;
126 }
127
NumPacketsSlow() const128 QuicPacketCount PacketNumberQueue::NumPacketsSlow() const {
129 QuicPacketCount n_packets = 0;
130 for (const auto& interval : packet_number_intervals_) {
131 n_packets += interval.Length();
132 }
133 return n_packets;
134 }
135
NumIntervals() const136 size_t PacketNumberQueue::NumIntervals() const {
137 return packet_number_intervals_.Size();
138 }
139
begin() const140 PacketNumberQueue::const_iterator PacketNumberQueue::begin() const {
141 return packet_number_intervals_.begin();
142 }
143
end() const144 PacketNumberQueue::const_iterator PacketNumberQueue::end() const {
145 return packet_number_intervals_.end();
146 }
147
rbegin() const148 PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rbegin() const {
149 return packet_number_intervals_.rbegin();
150 }
151
rend() const152 PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rend() const {
153 return packet_number_intervals_.rend();
154 }
155
LastIntervalLength() const156 QuicPacketCount PacketNumberQueue::LastIntervalLength() const {
157 QUICHE_DCHECK(!Empty());
158 return packet_number_intervals_.rbegin()->Length();
159 }
160
161 // Largest min...max range for packet numbers where we print the numbers
162 // explicitly. If bigger than this, we print as a range [a,d] rather
163 // than [a b c d]
164
operator <<(std::ostream & os,const PacketNumberQueue & q)165 std::ostream& operator<<(std::ostream& os, const PacketNumberQueue& q) {
166 for (const QuicInterval<QuicPacketNumber>& interval : q) {
167 // Print as a range if there is a pathological condition.
168 if ((interval.min() >= interval.max()) ||
169 (interval.max() - interval.min() > kMaxPrintRange)) {
170 // If min>max, it's really a bug, so QUIC_BUG it to
171 // catch it in development.
172 QUIC_BUG_IF(quic_bug_12614_2, interval.min() >= interval.max())
173 << "Ack Range minimum (" << interval.min() << "Not less than max ("
174 << interval.max() << ")";
175 // print range as min...max rather than full list.
176 // in the event of a bug, the list could be very big.
177 os << interval.min() << "..." << (interval.max() - 1) << " ";
178 } else {
179 for (QuicPacketNumber packet_number = interval.min();
180 packet_number < interval.max(); ++packet_number) {
181 os << packet_number << " ";
182 }
183 }
184 }
185 return os;
186 }
187
188 } // namespace quic
189