Move shared files in net/quic/ into net/quic/core/

net/quic/quic_received_packet_manager.cc

-// 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 - 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 - 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_;
-}
-
-QuicPacketNumber QuicReceivedPacketManager::GetLargestObserved() const {
-  return ack_frame_.largest_observed;
-}
-
-}  // namespace net