blob: 90cdc3eba63c9a36a4dc6b10416dc65424739e91 [file] [log] [blame]
// Copyright 2014 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/quic/quic_unacked_packet_map.h"
#include "base/logging.h"
#include "base/stl_util.h"
#include "net/quic/quic_bug_tracker.h"
#include "net/quic/quic_connection_stats.h"
#include "net/quic/quic_flags.h"
#include "net/quic/quic_utils.h"
#include "net/quic/quic_utils_chromium.h"
using std::max;
namespace net {
QuicUnackedPacketMap::QuicUnackedPacketMap()
: largest_sent_packet_(0),
largest_observed_(0),
least_unacked_(1),
bytes_in_flight_(0),
pending_crypto_packet_count_(0) {}
QuicUnackedPacketMap::~QuicUnackedPacketMap() {
QuicPacketNumber index = least_unacked_;
for (UnackedPacketMap::iterator it = unacked_packets_.begin();
it != unacked_packets_.end(); ++it, ++index) {
QuicUtils::DeleteFrames(&it->retransmittable_frames);
}
}
void QuicUnackedPacketMap::AddSentPacket(SerializedPacket* packet,
QuicPacketNumber old_packet_number,
TransmissionType transmission_type,
QuicTime sent_time,
bool set_in_flight) {
QuicPacketNumber packet_number = packet->packet_number;
QuicPacketLength bytes_sent = packet->encrypted_length;
QUIC_BUG_IF(largest_sent_packet_ >= packet_number) << packet_number;
DCHECK_GE(packet_number, least_unacked_ + unacked_packets_.size());
while (least_unacked_ + unacked_packets_.size() < packet_number) {
unacked_packets_.push_back(TransmissionInfo());
unacked_packets_.back().is_unackable = true;
}
const bool has_crypto_handshake =
packet->has_crypto_handshake == IS_HANDSHAKE;
TransmissionInfo info(packet->encryption_level, packet->packet_number_length,
transmission_type, sent_time, bytes_sent,
has_crypto_handshake, packet->num_padding_bytes);
if (old_packet_number > 0) {
TransferRetransmissionInfo(old_packet_number, packet_number,
transmission_type, &info);
}
largest_sent_packet_ = packet_number;
if (set_in_flight) {
bytes_in_flight_ += bytes_sent;
info.in_flight = true;
}
unacked_packets_.push_back(info);
// Swap the ack listeners and retransmittable frames to avoid allocations.
// TODO(ianswett): Could use emplace_back when Chromium can.
if (old_packet_number == 0) {
if (has_crypto_handshake) {
++pending_crypto_packet_count_;
}
packet->retransmittable_frames.swap(
unacked_packets_.back().retransmittable_frames);
unacked_packets_.back().ack_listeners.swap(packet->listeners);
}
}
void QuicUnackedPacketMap::RemoveObsoletePackets() {
while (!unacked_packets_.empty()) {
if (!IsPacketUseless(least_unacked_, unacked_packets_.front())) {
break;
}
unacked_packets_.pop_front();
++least_unacked_;
}
}
void QuicUnackedPacketMap::TransferRetransmissionInfo(
QuicPacketNumber old_packet_number,
QuicPacketNumber new_packet_number,
TransmissionType transmission_type,
TransmissionInfo* info) {
if (old_packet_number < least_unacked_ ||
old_packet_number > largest_sent_packet_) {
QUIC_BUG << "Old TransmissionInfo no longer exists for:"
<< old_packet_number << " least_unacked:" << least_unacked_
<< " largest_sent:" << largest_sent_packet_;
return;
}
DCHECK_GE(new_packet_number, least_unacked_ + unacked_packets_.size());
DCHECK_NE(NOT_RETRANSMISSION, transmission_type);
TransmissionInfo* transmission_info =
&unacked_packets_.at(old_packet_number - least_unacked_);
QuicFrames* frames = &transmission_info->retransmittable_frames;
for (AckListenerWrapper& wrapper : transmission_info->ack_listeners) {
wrapper.ack_listener->OnPacketRetransmitted(wrapper.length);
}
// Swap the frames and preserve num_padding_bytes and has_crypto_handshake.
frames->swap(info->retransmittable_frames);
info->has_crypto_handshake = transmission_info->has_crypto_handshake;
transmission_info->has_crypto_handshake = false;
info->num_padding_bytes = transmission_info->num_padding_bytes;
// Transfer the AckListeners if any are present.
info->ack_listeners.swap(transmission_info->ack_listeners);
QUIC_BUG_IF(frames == nullptr)
<< "Attempt to retransmit packet with no "
<< "retransmittable frames: " << old_packet_number;
// Don't link old transmissions to new ones when version or
// encryption changes.
if (transmission_type == ALL_INITIAL_RETRANSMISSION ||
transmission_type == ALL_UNACKED_RETRANSMISSION) {
transmission_info->is_unackable = true;
} else {
transmission_info->retransmission = new_packet_number;
}
// Proactively remove obsolete packets so the least unacked can be raised.
RemoveObsoletePackets();
}
bool QuicUnackedPacketMap::HasRetransmittableFrames(
QuicPacketNumber packet_number) const {
DCHECK_GE(packet_number, least_unacked_);
DCHECK_LT(packet_number, least_unacked_ + unacked_packets_.size());
return !unacked_packets_[packet_number - least_unacked_]
.retransmittable_frames.empty();
}
void QuicUnackedPacketMap::RemoveRetransmittability(TransmissionInfo* info) {
while (info->retransmission != 0) {
const QuicPacketNumber retransmission = info->retransmission;
info->retransmission = 0;
info = &unacked_packets_[retransmission - least_unacked_];
}
MaybeRemoveRetransmittableFrames(info);
}
void QuicUnackedPacketMap::RemoveRetransmittability(
QuicPacketNumber packet_number) {
DCHECK_GE(packet_number, least_unacked_);
DCHECK_LT(packet_number, least_unacked_ + unacked_packets_.size());
TransmissionInfo* info = &unacked_packets_[packet_number - least_unacked_];
RemoveRetransmittability(info);
}
void QuicUnackedPacketMap::MaybeRemoveRetransmittableFrames(
TransmissionInfo* transmission_info) {
if (transmission_info->has_crypto_handshake) {
DCHECK(!transmission_info->retransmittable_frames.empty());
DCHECK_LT(0u, pending_crypto_packet_count_);
--pending_crypto_packet_count_;
transmission_info->has_crypto_handshake = false;
}
QuicUtils::DeleteFrames(&transmission_info->retransmittable_frames);
}
void QuicUnackedPacketMap::IncreaseLargestObserved(
QuicPacketNumber largest_observed) {
DCHECK_LE(largest_observed_, largest_observed);
largest_observed_ = largest_observed;
}
bool QuicUnackedPacketMap::IsPacketUsefulForMeasuringRtt(
QuicPacketNumber packet_number,
const TransmissionInfo& info) const {
// Packet can be used for RTT measurement if it may yet be acked as the
// largest observed packet by the receiver.
return !info.is_unackable && packet_number > largest_observed_;
}
bool QuicUnackedPacketMap::IsPacketUsefulForCongestionControl(
const TransmissionInfo& info) const {
// Packet contributes to congestion control if it is considered inflight.
return info.in_flight;
}
bool QuicUnackedPacketMap::IsPacketUsefulForRetransmittableData(
const TransmissionInfo& info) const {
// Packet may have retransmittable frames, or the data may have been
// retransmitted with a new packet number.
return !info.retransmittable_frames.empty() ||
// Allow for an extra 1 RTT before stopping to track old packets.
info.retransmission > largest_observed_;
}
bool QuicUnackedPacketMap::IsPacketUseless(QuicPacketNumber packet_number,
const TransmissionInfo& info) const {
return !IsPacketUsefulForMeasuringRtt(packet_number, info) &&
!IsPacketUsefulForCongestionControl(info) &&
!IsPacketUsefulForRetransmittableData(info);
}
bool QuicUnackedPacketMap::IsUnacked(QuicPacketNumber packet_number) const {
if (packet_number < least_unacked_ ||
packet_number >= least_unacked_ + unacked_packets_.size()) {
return false;
}
return !IsPacketUseless(packet_number,
unacked_packets_[packet_number - least_unacked_]);
}
void QuicUnackedPacketMap::NotifyAndClearListeners(
std::list<AckListenerWrapper>* ack_listeners,
QuicTime::Delta ack_delay_time) {
for (const AckListenerWrapper& wrapper : *ack_listeners) {
wrapper.ack_listener->OnPacketAcked(wrapper.length, ack_delay_time);
}
ack_listeners->clear();
}
void QuicUnackedPacketMap::NotifyAndClearListeners(
QuicPacketNumber packet_number,
QuicTime::Delta ack_delay_time) {
DCHECK_GE(packet_number, least_unacked_);
DCHECK_LT(packet_number, least_unacked_ + unacked_packets_.size());
TransmissionInfo* info = &unacked_packets_[packet_number - least_unacked_];
NotifyAndClearListeners(&info->ack_listeners, ack_delay_time);
}
void QuicUnackedPacketMap::RemoveFromInFlight(TransmissionInfo* info) {
if (info->in_flight) {
QUIC_BUG_IF(bytes_in_flight_ < info->bytes_sent);
bytes_in_flight_ -= info->bytes_sent;
info->in_flight = false;
}
}
void QuicUnackedPacketMap::RemoveFromInFlight(QuicPacketNumber packet_number) {
DCHECK_GE(packet_number, least_unacked_);
DCHECK_LT(packet_number, least_unacked_ + unacked_packets_.size());
TransmissionInfo* info = &unacked_packets_[packet_number - least_unacked_];
RemoveFromInFlight(info);
}
void QuicUnackedPacketMap::RestoreToInFlight(QuicPacketNumber packet_number) {
DCHECK_GE(packet_number, least_unacked_);
DCHECK_LT(packet_number, least_unacked_ + unacked_packets_.size());
TransmissionInfo* info = &unacked_packets_[packet_number - least_unacked_];
DCHECK(!info->is_unackable);
bytes_in_flight_ += info->bytes_sent;
info->in_flight = true;
}
void QuicUnackedPacketMap::CancelRetransmissionsForStream(
QuicStreamId stream_id) {
QuicPacketNumber packet_number = least_unacked_;
for (UnackedPacketMap::iterator it = unacked_packets_.begin();
it != unacked_packets_.end(); ++it, ++packet_number) {
QuicFrames* frames = &it->retransmittable_frames;
if (frames->empty()) {
continue;
}
QuicUtils::RemoveFramesForStream(frames, stream_id);
if (frames->empty()) {
RemoveRetransmittability(packet_number);
}
}
}
bool QuicUnackedPacketMap::HasUnackedPackets() const {
return !unacked_packets_.empty();
}
bool QuicUnackedPacketMap::HasInFlightPackets() const {
return bytes_in_flight_ > 0;
}
const TransmissionInfo& QuicUnackedPacketMap::GetTransmissionInfo(
QuicPacketNumber packet_number) const {
return unacked_packets_[packet_number - least_unacked_];
}
TransmissionInfo* QuicUnackedPacketMap::GetMutableTransmissionInfo(
QuicPacketNumber packet_number) {
return &unacked_packets_[packet_number - least_unacked_];
}
QuicTime QuicUnackedPacketMap::GetLastPacketSentTime() const {
UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
while (it != unacked_packets_.rend()) {
if (it->in_flight) {
QUIC_BUG_IF(it->sent_time == QuicTime::Zero())
<< "Sent time can never be zero for a packet in flight.";
return it->sent_time;
}
++it;
}
QUIC_BUG << "GetLastPacketSentTime requires in flight packets.";
return QuicTime::Zero();
}
size_t QuicUnackedPacketMap::GetNumUnackedPacketsDebugOnly() const {
size_t unacked_packet_count = 0;
QuicPacketNumber packet_number = least_unacked_;
for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
it != unacked_packets_.end(); ++it, ++packet_number) {
if (!IsPacketUseless(packet_number, *it)) {
++unacked_packet_count;
}
}
return unacked_packet_count;
}
bool QuicUnackedPacketMap::HasMultipleInFlightPackets() const {
if (bytes_in_flight_ > kDefaultTCPMSS) {
return true;
}
size_t num_in_flight = 0;
for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
it != unacked_packets_.rend(); ++it) {
if (it->in_flight) {
++num_in_flight;
}
if (num_in_flight > 1) {
return true;
}
}
return false;
}
bool QuicUnackedPacketMap::HasPendingCryptoPackets() const {
return pending_crypto_packet_count_ > 0;
}
bool QuicUnackedPacketMap::HasUnackedRetransmittableFrames() const {
for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
it != unacked_packets_.rend(); ++it) {
if (it->in_flight && !it->retransmittable_frames.empty()) {
return true;
}
}
return false;
}
QuicPacketNumber QuicUnackedPacketMap::GetLeastUnacked() const {
return least_unacked_;
}
} // namespace net