blob: 255ce4dc10a7a4287ab497615d61471a4a74e29a [file] [log] [blame]
// Copyright 2013 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_received_packet_manager.h"
#include <limits>
#include <utility>
#include "base/logging.h"
#include "base/stl_util.h"
#include "net/base/linked_hash_map.h"
#include "net/quic/crypto/crypto_protocol.h"
#include "net/quic/quic_connection_stats.h"
using std::make_pair;
using std::max;
using std::min;
using std::numeric_limits;
namespace net {
namespace {
// The maximum number of packets to ack immediately after a missing packet for
// fast retransmission to kick in at the sender. This limit is created to
// reduce the number of acks sent that have no benefit for fast retransmission.
// Set to the number of nacks needed for fast retransmit plus one for protection
// against an ack loss
const size_t kMaxPacketsAfterNewMissing = 4;
}
QuicReceivedPacketManager::EntropyTracker::EntropyTracker()
: packets_entropy_hash_(0),
first_gap_(1),
largest_observed_(0) {
}
QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {}
QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash(
QuicPacketSequenceNumber sequence_number) const {
DCHECK_LE(sequence_number, largest_observed_);
if (sequence_number == largest_observed_) {
return packets_entropy_hash_;
}
DCHECK_GE(sequence_number, first_gap_);
DCHECK_EQ(first_gap_ + packets_entropy_.size() - 1, largest_observed_);
QuicPacketEntropyHash hash = packets_entropy_hash_;
ReceivedEntropyHashes::const_reverse_iterator it = packets_entropy_.rbegin();
for (QuicPacketSequenceNumber i = 0;
i < (largest_observed_ - sequence_number); ++i, ++it) {
hash ^= it->first;
}
return hash;
}
void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash(
QuicPacketSequenceNumber sequence_number,
QuicPacketEntropyHash entropy_hash) {
if (sequence_number < first_gap_) {
DVLOG(1) << "Ignoring received packet entropy for sequence_number:"
<< sequence_number << " less than largest_peer_sequence_number:"
<< first_gap_;
return;
}
// RecordPacketEntropyHash is only intended to be called once per packet.
DCHECK(sequence_number > largest_observed_ ||
!packets_entropy_[sequence_number - first_gap_].second);
packets_entropy_hash_ ^= entropy_hash;
// Optimize the typical case of no gaps.
if (sequence_number == largest_observed_ + 1 && packets_entropy_.empty()) {
++first_gap_;
largest_observed_ = sequence_number;
return;
}
if (sequence_number > largest_observed_) {
for (QuicPacketSequenceNumber i = 0;
i < (sequence_number - largest_observed_ - 1); ++i) {
packets_entropy_.push_back(make_pair(0, false));
}
packets_entropy_.push_back(make_pair(entropy_hash, true));
largest_observed_ = sequence_number;
} else {
packets_entropy_[sequence_number - first_gap_] =
make_pair(entropy_hash, true);
AdvanceFirstGapAndGarbageCollectEntropyMap();
}
DVLOG(2) << "setting cumulative received entropy hash to: "
<< static_cast<int>(packets_entropy_hash_)
<< " updated with sequence number " << sequence_number
<< " entropy hash: " << static_cast<int>(entropy_hash);
}
void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
QuicPacketSequenceNumber sequence_number,
QuicPacketEntropyHash entropy_hash) {
DCHECK_LE(sequence_number, largest_observed_);
if (sequence_number < first_gap_) {
DVLOG(1) << "Ignoring set entropy at:" << sequence_number
<< " less than first_gap_:" << first_gap_;
return;
}
while (first_gap_ < sequence_number) {
++first_gap_;
if (!packets_entropy_.empty()) {
packets_entropy_.pop_front();
}
}
// Compute the current entropy by XORing in all entropies received including
// and since sequence_number.
packets_entropy_hash_ = entropy_hash;
for (ReceivedEntropyHashes::const_iterator it = packets_entropy_.begin();
it != packets_entropy_.end(); ++it) {
packets_entropy_hash_ ^= it->first;
}
// Garbage collect entries from the beginning of the map.
AdvanceFirstGapAndGarbageCollectEntropyMap();
}
void QuicReceivedPacketManager::EntropyTracker::
AdvanceFirstGapAndGarbageCollectEntropyMap() {
while (!packets_entropy_.empty() && packets_entropy_.front().second) {
++first_gap_;
packets_entropy_.pop_front();
}
}
QuicReceivedPacketManager::QuicReceivedPacketManager(
QuicConnectionStats* stats)
: peer_least_packet_awaiting_ack_(0),
time_largest_observed_(QuicTime::Zero()),
receive_algorithm_(ReceiveAlgorithmInterface::Create(kTCP)),
stats_(stats) {
ack_frame_.largest_observed = 0;
ack_frame_.entropy_hash = 0;
}
QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
void QuicReceivedPacketManager::RecordPacketReceived(
QuicByteCount bytes,
const QuicPacketHeader& header,
QuicTime receipt_time) {
QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
DCHECK(IsAwaitingPacket(sequence_number));
InsertMissingPacketsBetween(
&ack_frame_,
max(ack_frame_.largest_observed + 1, peer_least_packet_awaiting_ack_),
sequence_number);
if (ack_frame_.largest_observed > sequence_number) {
// We've gotten one of the out of order packets - remove it from our
// "missing packets" list.
DVLOG(1) << "Removing " << sequence_number << " from missing list";
ack_frame_.missing_packets.erase(sequence_number);
// Record how out of order stats.
++stats_->packets_reordered;
uint32 sequence_gap = ack_frame_.largest_observed - sequence_number;
stats_->max_sequence_reordering =
max(stats_->max_sequence_reordering, sequence_gap);
uint32 reordering_time_us =
receipt_time.Subtract(time_largest_observed_).ToMicroseconds();
stats_->max_time_reordering_us = max(stats_->max_time_reordering_us,
reordering_time_us);
}
if (sequence_number > ack_frame_.largest_observed) {
ack_frame_.largest_observed = sequence_number;
time_largest_observed_ = receipt_time;
}
entropy_tracker_.RecordPacketEntropyHash(sequence_number,
header.entropy_hash);
receive_algorithm_->RecordIncomingPacket(
bytes, sequence_number, receipt_time);
received_packet_times_.push_back(
std::make_pair(sequence_number, receipt_time));
ack_frame_.revived_packets.erase(sequence_number);
}
void QuicReceivedPacketManager::RecordPacketRevived(
QuicPacketSequenceNumber sequence_number) {
LOG_IF(DFATAL, !IsAwaitingPacket(sequence_number));
ack_frame_.revived_packets.insert(sequence_number);
}
bool QuicReceivedPacketManager::IsMissing(
QuicPacketSequenceNumber sequence_number) {
return ContainsKey(ack_frame_.missing_packets, sequence_number);
}
bool QuicReceivedPacketManager::IsAwaitingPacket(
QuicPacketSequenceNumber sequence_number) {
return ::net::IsAwaitingPacket(ack_frame_, sequence_number);
}
namespace {
struct isTooLarge {
explicit isTooLarge(QuicPacketSequenceNumber n) : largest_observed_(n) {}
QuicPacketSequenceNumber largest_observed_;
// Return true if the packet in p is too different from largest_observed_
// to express.
bool operator() (
const std::pair<QuicPacketSequenceNumber, QuicTime>& p) const {
return largest_observed_ - p.first >= numeric_limits<uint8>::max();
}
};
} // namespace
void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
QuicAckFrame* ack_frame, QuicTime approximate_now) {
*ack_frame = ack_frame_;
ack_frame->entropy_hash = EntropyHash(ack_frame_.largest_observed);
if (time_largest_observed_ == QuicTime::Zero()) {
// We have received no packets.
ack_frame->delta_time_largest_observed = QuicTime::Delta::Infinite();
return;
}
if (approximate_now < time_largest_observed_) {
// Approximate now may well be "in the past".
ack_frame->delta_time_largest_observed = QuicTime::Delta::Zero();
return;
}
ack_frame->delta_time_largest_observed =
approximate_now.Subtract(time_largest_observed_);
// Remove all packets that are too far from largest_observed to express.
received_packet_times_.remove_if(isTooLarge(ack_frame_.largest_observed));
ack_frame->received_packet_times = received_packet_times_;
received_packet_times_.clear();
}
bool QuicReceivedPacketManager::GenerateCongestionFeedback(
QuicCongestionFeedbackFrame* feedback) {
return receive_algorithm_->GenerateCongestionFeedback(feedback);
}
QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
QuicPacketSequenceNumber sequence_number) const {
return entropy_tracker_.EntropyHash(sequence_number);
}
bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
QuicPacketSequenceNumber least_unacked) {
ack_frame_.revived_packets.erase(
ack_frame_.revived_packets.begin(),
ack_frame_.revived_packets.lower_bound(least_unacked));
size_t missing_packets_count = ack_frame_.missing_packets.size();
ack_frame_.missing_packets.erase(
ack_frame_.missing_packets.begin(),
ack_frame_.missing_packets.lower_bound(least_unacked));
return missing_packets_count != ack_frame_.missing_packets.size();
}
void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
const QuicStopWaitingFrame& stop_waiting) {
// ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
DCHECK_LE(peer_least_packet_awaiting_ack_, stop_waiting.least_unacked);
if (stop_waiting.least_unacked > peer_least_packet_awaiting_ack_) {
bool missed_packets = DontWaitForPacketsBefore(stop_waiting.least_unacked);
if (missed_packets) {
DVLOG(1) << "Updating entropy hashed since we missed packets";
// There were some missing packets that we won't ever get now. Recalculate
// the received entropy hash.
entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked,
stop_waiting.entropy_hash);
}
peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked;
}
DCHECK(ack_frame_.missing_packets.empty() ||
*ack_frame_.missing_packets.begin() >=
peer_least_packet_awaiting_ack_);
}
bool QuicReceivedPacketManager::HasNewMissingPackets() {
return !ack_frame_.missing_packets.empty() &&
(ack_frame_.largest_observed -
*ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
}
} // namespace net