blob: 5f47b3f8516ee6bc1cb79bd85d678579effacd53 [file] [log] [blame]
// 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