| // Copyright (c) 2016 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "net/third_party/quiche/src/quic/core/frames/quic_ack_frame.h" |
| |
| #include "net/third_party/quiche/src/quic/core/quic_constants.h" |
| #include "net/third_party/quiche/src/quic/platform/api/quic_bug_tracker.h" |
| #include "net/third_party/quiche/src/quic/platform/api/quic_flag_utils.h" |
| #include "net/third_party/quiche/src/quic/platform/api/quic_interval.h" |
| |
| namespace quic { |
| |
| namespace { |
| |
| const QuicPacketCount kMaxPrintRange = 128; |
| |
| uint64_t PacketNumberIntervalLength( |
| const QuicInterval<QuicPacketNumber>& interval) { |
| if (interval.Empty()) { |
| return 0u; |
| } |
| return interval.max() - interval.min(); |
| } |
| } // namespace |
| |
| bool IsAwaitingPacket(const QuicAckFrame& ack_frame, |
| QuicPacketNumber packet_number, |
| QuicPacketNumber peer_least_packet_awaiting_ack) { |
| DCHECK(packet_number.IsInitialized()); |
| return (!peer_least_packet_awaiting_ack.IsInitialized() || |
| packet_number >= peer_least_packet_awaiting_ack) && |
| !ack_frame.packets.Contains(packet_number); |
| } |
| |
| QuicAckFrame::QuicAckFrame() |
| : ack_delay_time(QuicTime::Delta::Infinite()), |
| ecn_counters_populated(false), |
| ect_0_count(0), |
| ect_1_count(0), |
| ecn_ce_count(0) {} |
| |
| QuicAckFrame::QuicAckFrame(const QuicAckFrame& other) = default; |
| |
| QuicAckFrame::~QuicAckFrame() {} |
| |
| std::ostream& operator<<(std::ostream& os, const QuicAckFrame& ack_frame) { |
| os << "{ largest_acked: " << LargestAcked(ack_frame) |
| << ", ack_delay_time: " << ack_frame.ack_delay_time.ToMicroseconds() |
| << ", packets: [ " << ack_frame.packets << " ]" |
| << ", received_packets: [ "; |
| for (const std::pair<QuicPacketNumber, QuicTime>& p : |
| ack_frame.received_packet_times) { |
| os << p.first << " at " << p.second.ToDebuggingValue() << " "; |
| } |
| os << " ]"; |
| os << ", ecn_counters_populated: " << ack_frame.ecn_counters_populated; |
| if (ack_frame.ecn_counters_populated) { |
| os << ", ect_0_count: " << ack_frame.ect_0_count |
| << ", ect_1_count: " << ack_frame.ect_1_count |
| << ", ecn_ce_count: " << ack_frame.ecn_ce_count; |
| } |
| |
| os << " }\n"; |
| return os; |
| } |
| |
| void QuicAckFrame::Clear() { |
| largest_acked.Clear(); |
| ack_delay_time = QuicTime::Delta::Infinite(); |
| received_packet_times.clear(); |
| packets.Clear(); |
| } |
| |
| PacketNumberQueue::PacketNumberQueue() {} |
| PacketNumberQueue::PacketNumberQueue(const PacketNumberQueue& other) = default; |
| PacketNumberQueue::PacketNumberQueue(PacketNumberQueue&& other) = default; |
| PacketNumberQueue::~PacketNumberQueue() {} |
| |
| PacketNumberQueue& PacketNumberQueue::operator=( |
| const PacketNumberQueue& other) = default; |
| PacketNumberQueue& PacketNumberQueue::operator=(PacketNumberQueue&& other) = |
| default; |
| |
| void PacketNumberQueue::Add(QuicPacketNumber packet_number) { |
| if (!packet_number.IsInitialized()) { |
| return; |
| } |
| // Check if the deque is empty |
| if (packet_number_deque_.empty()) { |
| packet_number_deque_.push_front( |
| QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1)); |
| return; |
| } |
| QuicInterval<QuicPacketNumber> back = packet_number_deque_.back(); |
| |
| // Check for the typical case, |
| // when the next packet in order is acked |
| if (back.max() == packet_number) { |
| packet_number_deque_.back().SetMax(packet_number + 1); |
| return; |
| } |
| // Check if the next packet in order is skipped |
| if (back.max() < packet_number) { |
| packet_number_deque_.push_back( |
| QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1)); |
| return; |
| } |
| |
| QuicInterval<QuicPacketNumber> front = packet_number_deque_.front(); |
| // Check if the packet can be popped on the front |
| if (front.min() > packet_number + 1) { |
| packet_number_deque_.push_front( |
| QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1)); |
| return; |
| } |
| if (front.min() == packet_number + 1) { |
| packet_number_deque_.front().SetMin(packet_number); |
| return; |
| } |
| |
| int i = packet_number_deque_.size() - 1; |
| // Iterating through the queue backwards |
| // to find a proper place for the packet |
| while (i >= 0) { |
| QuicInterval<QuicPacketNumber> packet_interval = packet_number_deque_[i]; |
| DCHECK(packet_interval.min() < packet_interval.max()); |
| // Check if the packet is contained in an interval already |
| if (packet_interval.Contains(packet_number)) { |
| return; |
| } |
| |
| // Check if the packet can extend an interval. |
| if (packet_interval.max() == packet_number) { |
| packet_number_deque_[i].SetMax(packet_number + 1); |
| return; |
| } |
| // Check if the packet can extend an interval |
| // and merge two intervals if needed. |
| // There is no need to merge an interval in the previous |
| // if statement, as all merges will happen here. |
| if (packet_interval.min() == packet_number + 1) { |
| packet_number_deque_[i].SetMin(packet_number); |
| if (i > 0 && packet_number == packet_number_deque_[i - 1].max()) { |
| packet_number_deque_[i - 1].SetMax(packet_interval.max()); |
| packet_number_deque_.erase(packet_number_deque_.begin() + i); |
| } |
| return; |
| } |
| |
| // Check if we need to make a new interval for the packet |
| if (packet_interval.max() < packet_number + 1) { |
| packet_number_deque_.insert( |
| packet_number_deque_.begin() + i + 1, |
| QuicInterval<QuicPacketNumber>(packet_number, packet_number + 1)); |
| return; |
| } |
| i--; |
| } |
| } |
| |
| void PacketNumberQueue::AddRange(QuicPacketNumber lower, |
| QuicPacketNumber higher) { |
| if (!lower.IsInitialized() || !higher.IsInitialized() || lower >= higher) { |
| return; |
| } |
| if (packet_number_deque_.empty()) { |
| packet_number_deque_.push_front( |
| QuicInterval<QuicPacketNumber>(lower, higher)); |
| return; |
| } |
| QuicInterval<QuicPacketNumber> back = packet_number_deque_.back(); |
| |
| if (back.max() == lower) { |
| // Check for the typical case, |
| // when the next packet in order is acked |
| packet_number_deque_.back().SetMax(higher); |
| return; |
| } |
| if (back.max() < lower) { |
| // Check if the next packet in order is skipped |
| packet_number_deque_.push_back( |
| QuicInterval<QuicPacketNumber>(lower, higher)); |
| return; |
| } |
| QuicInterval<QuicPacketNumber> front = packet_number_deque_.front(); |
| // Check if the packets are being added in reverse order |
| if (front.min() == higher) { |
| packet_number_deque_.front().SetMin(lower); |
| } else if (front.min() > higher) { |
| packet_number_deque_.push_front( |
| QuicInterval<QuicPacketNumber>(lower, higher)); |
| |
| } else { |
| // Ranges must be above or below all existing ranges. |
| QUIC_BUG << "AddRange only supports adding packets above or below the " |
| << "current min:" << Min() << " and max:" << Max() |
| << ", but adding [" << lower << "," << higher << ")"; |
| } |
| } |
| |
| bool PacketNumberQueue::RemoveUpTo(QuicPacketNumber higher) { |
| if (!higher.IsInitialized() || Empty()) { |
| return false; |
| } |
| const QuicPacketNumber old_min = Min(); |
| while (!packet_number_deque_.empty()) { |
| QuicInterval<QuicPacketNumber> front = packet_number_deque_.front(); |
| if (front.max() < higher) { |
| packet_number_deque_.pop_front(); |
| } else if (front.min() < higher && front.max() >= higher) { |
| packet_number_deque_.front().SetMin(higher); |
| if (front.max() == higher) { |
| packet_number_deque_.pop_front(); |
| } |
| break; |
| } else { |
| break; |
| } |
| } |
| |
| return Empty() || old_min != Min(); |
| } |
| |
| void PacketNumberQueue::RemoveSmallestInterval() { |
| QUIC_BUG_IF(packet_number_deque_.size() < 2) |
| << (Empty() ? "No intervals to remove." |
| : "Can't remove the last interval."); |
| packet_number_deque_.pop_front(); |
| } |
| |
| void PacketNumberQueue::Clear() { |
| packet_number_deque_.clear(); |
| } |
| |
| bool PacketNumberQueue::Contains(QuicPacketNumber packet_number) const { |
| if (!packet_number.IsInitialized() || packet_number_deque_.empty()) { |
| return false; |
| } |
| if (packet_number_deque_.front().min() > packet_number || |
| packet_number_deque_.back().max() <= packet_number) { |
| return false; |
| } |
| for (QuicInterval<QuicPacketNumber> interval : packet_number_deque_) { |
| if (interval.Contains(packet_number)) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| bool PacketNumberQueue::Empty() const { |
| return packet_number_deque_.empty(); |
| } |
| |
| QuicPacketNumber PacketNumberQueue::Min() const { |
| DCHECK(!Empty()); |
| return packet_number_deque_.front().min(); |
| } |
| |
| QuicPacketNumber PacketNumberQueue::Max() const { |
| DCHECK(!Empty()); |
| return packet_number_deque_.back().max() - 1; |
| } |
| |
| QuicPacketCount PacketNumberQueue::NumPacketsSlow() const { |
| QuicPacketCount n_packets = 0; |
| for (QuicInterval<QuicPacketNumber> interval : packet_number_deque_) { |
| n_packets += PacketNumberIntervalLength(interval); |
| } |
| return n_packets; |
| } |
| |
| size_t PacketNumberQueue::NumIntervals() const { |
| return packet_number_deque_.size(); |
| } |
| |
| PacketNumberQueue::const_iterator PacketNumberQueue::begin() const { |
| return packet_number_deque_.begin(); |
| } |
| |
| PacketNumberQueue::const_iterator PacketNumberQueue::end() const { |
| return packet_number_deque_.end(); |
| } |
| |
| PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rbegin() const { |
| return packet_number_deque_.rbegin(); |
| } |
| |
| PacketNumberQueue::const_reverse_iterator PacketNumberQueue::rend() const { |
| return packet_number_deque_.rend(); |
| } |
| |
| QuicPacketCount PacketNumberQueue::LastIntervalLength() const { |
| DCHECK(!Empty()); |
| return PacketNumberIntervalLength(packet_number_deque_.back()); |
| } |
| |
| // Largest min...max range for packet numbers where we print the numbers |
| // explicitly. If bigger than this, we print as a range [a,d] rather |
| // than [a b c d] |
| |
| std::ostream& operator<<(std::ostream& os, const PacketNumberQueue& q) { |
| for (const QuicInterval<QuicPacketNumber>& interval : q) { |
| // Print as a range if there is a pathological condition. |
| if ((interval.min() >= interval.max()) || |
| (interval.max() - interval.min() > kMaxPrintRange)) { |
| // If min>max, it's really a bug, so QUIC_BUG it to |
| // catch it in development. |
| QUIC_BUG_IF(interval.min() >= interval.max()) |
| << "Ack Range minimum (" << interval.min() << "Not less than max (" |
| << interval.max() << ")"; |
| // print range as min...max rather than full list. |
| // in the event of a bug, the list could be very big. |
| os << interval.min() << "..." << (interval.max() - 1) << " "; |
| } else { |
| for (QuicPacketNumber packet_number = interval.min(); |
| packet_number < interval.max(); ++packet_number) { |
| os << packet_number << " "; |
| } |
| } |
| } |
| return os; |
| } |
| |
| } // namespace quic |