| // 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 "base/strings/stringprintf.h" |
| #include "net/base/linked_hash_map.h" |
| #include "net/quic/crypto/crypto_protocol.h" |
| #include "net/quic/quic_bug_tracker.h" |
| #include "net/quic/quic_connection_stats.h" |
| #include "net/quic/quic_flags.h" |
| |
| 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( |
| QuicPacketNumber packet_number) const { |
| DCHECK_LE(packet_number, largest_observed_); |
| if (packet_number == largest_observed_) { |
| return packets_entropy_hash_; |
| } |
| |
| DCHECK_GE(packet_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 (QuicPacketNumber i = 0; i < (largest_observed_ - packet_number); |
| ++i, ++it) { |
| hash ^= it->first; |
| } |
| return hash; |
| } |
| |
| void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash( |
| QuicPacketNumber packet_number, |
| QuicPacketEntropyHash entropy_hash) { |
| if (packet_number < first_gap_) { |
| DVLOG(1) << "Ignoring received packet entropy for packet_number:" |
| << packet_number |
| << " less than largest_peer_packet_number:" << first_gap_; |
| return; |
| } |
| // RecordPacketEntropyHash is only intended to be called once per packet. |
| DCHECK(packet_number > largest_observed_ || |
| !packets_entropy_[packet_number - first_gap_].second); |
| |
| packets_entropy_hash_ ^= entropy_hash; |
| |
| // Optimize the typical case of no gaps. |
| if (packet_number == largest_observed_ + 1 && packets_entropy_.empty()) { |
| ++first_gap_; |
| largest_observed_ = packet_number; |
| return; |
| } |
| if (packet_number > largest_observed_) { |
| for (QuicPacketNumber i = 0; i < (packet_number - largest_observed_ - 1); |
| ++i) { |
| packets_entropy_.push_back(std::make_pair(0, false)); |
| } |
| packets_entropy_.push_back(std::make_pair(entropy_hash, true)); |
| largest_observed_ = packet_number; |
| } else { |
| packets_entropy_[packet_number - first_gap_] = |
| std::make_pair(entropy_hash, true); |
| AdvanceFirstGapAndGarbageCollectEntropyMap(); |
| } |
| |
| DVLOG(2) << "setting cumulative received entropy hash to: " |
| << static_cast<int>(packets_entropy_hash_) |
| << " updated with packet number " << packet_number |
| << " entropy hash: " << static_cast<int>(entropy_hash); |
| } |
| |
| void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo( |
| QuicPacketNumber packet_number, |
| QuicPacketEntropyHash entropy_hash) { |
| DCHECK_LE(packet_number, largest_observed_); |
| if (packet_number < first_gap_) { |
| DVLOG(1) << "Ignoring set entropy at:" << packet_number |
| << " less than first_gap_:" << first_gap_; |
| return; |
| } |
| while (first_gap_ < packet_number) { |
| ++first_gap_; |
| if (!packets_entropy_.empty()) { |
| packets_entropy_.pop_front(); |
| } |
| } |
| // Compute the current entropy by XORing in all entropies received including |
| // and since packet_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), |
| ack_frame_updated_(false), |
| time_largest_observed_(QuicTime::Zero()), |
| 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) { |
| QuicPacketNumber packet_number = header.packet_number; |
| DCHECK(IsAwaitingPacket(packet_number)); |
| if (!ack_frame_updated_) { |
| ack_frame_.received_packet_times.clear(); |
| } |
| ack_frame_updated_ = true; |
| if (ack_frame_.missing) { |
| // Adds the range of packet numbers from max(largest observed + 1, least |
| // awaiting ack) up to packet_number not including packet_number. |
| ack_frame_.packets.Add( |
| max(ack_frame_.largest_observed + 1, peer_least_packet_awaiting_ack_), |
| packet_number); |
| } else { |
| ack_frame_.packets.Add(header.packet_number); |
| } |
| |
| if (ack_frame_.largest_observed > packet_number) { |
| if (ack_frame_.missing) { |
| // We've gotten one of the out of order packets - remove it from our |
| // "missing packets" list. |
| DVLOG(1) << "Removing " << packet_number << " from missing list"; |
| ack_frame_.packets.Remove(packet_number); |
| } |
| |
| // Record how out of order stats. |
| ++stats_->packets_reordered; |
| stats_->max_sequence_reordering = |
| max(stats_->max_sequence_reordering, |
| ack_frame_.largest_observed - packet_number); |
| int64_t 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 (packet_number > ack_frame_.largest_observed) { |
| ack_frame_.largest_observed = packet_number; |
| time_largest_observed_ = receipt_time; |
| } |
| if (ack_frame_.missing) { |
| entropy_tracker_.RecordPacketEntropyHash(packet_number, |
| header.entropy_hash); |
| } |
| |
| ack_frame_.received_packet_times.push_back( |
| std::make_pair(packet_number, receipt_time)); |
| } |
| |
| bool QuicReceivedPacketManager::IsMissing(QuicPacketNumber packet_number) { |
| if (ack_frame_.missing) { |
| return ack_frame_.packets.Contains(packet_number); |
| } |
| return packet_number < ack_frame_.largest_observed && |
| !ack_frame_.packets.Contains(packet_number); |
| } |
| |
| bool QuicReceivedPacketManager::IsAwaitingPacket( |
| QuicPacketNumber packet_number) { |
| return ::net::IsAwaitingPacket(ack_frame_, packet_number, |
| peer_least_packet_awaiting_ack_); |
| } |
| |
| namespace { |
| struct isTooLarge { |
| explicit isTooLarge(QuicPacketNumber n) : largest_observed_(n) {} |
| QuicPacketNumber largest_observed_; |
| |
| // Return true if the packet in p is too different from largest_observed_ |
| // to express. |
| bool operator()(const std::pair<QuicPacketNumber, QuicTime>& p) const { |
| return largest_observed_ - p.first >= numeric_limits<uint8_t>::max(); |
| } |
| }; |
| } // namespace |
| |
| const QuicFrame QuicReceivedPacketManager::GetUpdatedAckFrame( |
| QuicTime approximate_now) { |
| ack_frame_updated_ = false; |
| if (ack_frame_.missing) { |
| ack_frame_.entropy_hash = EntropyHash(ack_frame_.largest_observed); |
| } |
| |
| if (time_largest_observed_ == QuicTime::Zero()) { |
| // We have received no packets. |
| ack_frame_.ack_delay_time = QuicTime::Delta::Infinite(); |
| } else { |
| // Ensure the delta is zero if approximate now is "in the past". |
| ack_frame_.ack_delay_time = |
| approximate_now < time_largest_observed_ |
| ? QuicTime::Delta::Zero() |
| : approximate_now.Subtract(time_largest_observed_); |
| } |
| |
| // Clear all packet times if any are too far from largest observed. |
| // It's expected this is extremely rare. |
| for (PacketTimeVector::iterator it = ack_frame_.received_packet_times.begin(); |
| it != ack_frame_.received_packet_times.end();) { |
| if (ack_frame_.largest_observed - it->first >= |
| numeric_limits<uint8_t>::max()) { |
| it = ack_frame_.received_packet_times.erase(it); |
| } else { |
| ++it; |
| } |
| } |
| |
| return QuicFrame(&ack_frame_); |
| } |
| |
| QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash( |
| QuicPacketNumber packet_number) const { |
| return entropy_tracker_.EntropyHash(packet_number); |
| } |
| |
| bool QuicReceivedPacketManager::DontWaitForPacketsBefore( |
| QuicPacketNumber least_unacked) { |
| peer_least_packet_awaiting_ack_ = least_unacked; |
| return ack_frame_.packets.RemoveUpTo(least_unacked); |
| } |
| |
| 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 packets_updated = DontWaitForPacketsBefore(stop_waiting.least_unacked); |
| if (packets_updated) { |
| if (ack_frame_.missing) { |
| 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); |
| } |
| // Ack frame gets updated because packets set is updated because of stop |
| // waiting frame. |
| ack_frame_updated_ = true; |
| } |
| } |
| DCHECK(ack_frame_.packets.Empty() || |
| ack_frame_.packets.Min() >= peer_least_packet_awaiting_ack_); |
| } |
| |
| bool QuicReceivedPacketManager::HasMissingPackets() const { |
| if (ack_frame_.missing) { |
| return !ack_frame_.packets.Empty(); |
| } |
| |
| return ack_frame_.packets.NumIntervals() > 1 || |
| (!ack_frame_.packets.Empty() && |
| ack_frame_.packets.Min() > |
| max(QuicPacketNumber(1), peer_least_packet_awaiting_ack_)); |
| } |
| |
| bool QuicReceivedPacketManager::HasNewMissingPackets() const { |
| if (ack_frame_.missing) { |
| return !ack_frame_.packets.Empty() && |
| (ack_frame_.largest_observed - ack_frame_.packets.Max()) <= |
| kMaxPacketsAfterNewMissing; |
| } |
| |
| return HasMissingPackets() && |
| ack_frame_.packets.LastIntervalLength() <= kMaxPacketsAfterNewMissing; |
| } |
| |
| size_t QuicReceivedPacketManager::NumTrackedPackets() const { |
| return entropy_tracker_.size(); |
| } |
| |
| void QuicReceivedPacketManager::SetVersion(QuicVersion version) { |
| ack_frame_.missing = version <= QUIC_VERSION_33; |
| } |
| |
| bool QuicReceivedPacketManager::ack_frame_updated() const { |
| return ack_frame_updated_; |
| } |
| |
| } // namespace net |