net/quic/quic_received_packet_manager.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/quic/quic_received_packet_manager.h"
   6
   7 #include <limits>
   8 #include <utility>
   9
  10 #include "base/logging.h"
  11 #include "base/stl_util.h"
  12 #include "net/base/linked_hash_map.h"
  13 #include "net/quic/crypto/crypto_protocol.h"
  14 #include "net/quic/quic_connection_stats.h"
  15
  16 using std::max;
  17 using std::min;
  18 using std::numeric_limits;
  19
  20 namespace net {
  21
  22 namespace {
  23
  24 // The maximum number of packets to ack immediately after a missing packet for
  25 // fast retransmission to kick in at the sender.  This limit is created to
  26 // reduce the number of acks sent that have no benefit for fast retransmission.
  27 // Set to the number of nacks needed for fast retransmit plus one for protection
  28 // against an ack loss
  29 const size_t kMaxPacketsAfterNewMissing = 4;
  30
  31 }
  32
  33 QuicReceivedPacketManager::EntropyTracker::EntropyTracker()
  34     :  packets_entropy_hash_(0),
  35        first_gap_(1),
  36        largest_observed_(0) {
  37 }
  38
  39 QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {}
  40
  41 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash(
  42     QuicPacketNumber packet_number) const {
  43   DCHECK_LE(packet_number, largest_observed_);
  44   if (packet_number == largest_observed_) {
  45     return packets_entropy_hash_;
  46   }
  47
  48   DCHECK_GE(packet_number, first_gap_);
  49   DCHECK_EQ(first_gap_ + packets_entropy_.size() - 1, largest_observed_);
  50   QuicPacketEntropyHash hash = packets_entropy_hash_;
  51   ReceivedEntropyHashes::const_reverse_iterator it = packets_entropy_.rbegin();
  52   for (QuicPacketNumber i = 0; i < (largest_observed_ - packet_number);
  53        ++i, ++it) {
  54     hash ^= it->first;
  55   }
  56   return hash;
  57 }
  58
  59 void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash(
  60     QuicPacketNumber packet_number,
  61     QuicPacketEntropyHash entropy_hash) {
  62   if (packet_number < first_gap_) {
  63     DVLOG(1) << "Ignoring received packet entropy for packet_number:"
  64              << packet_number
  65              << " less than largest_peer_packet_number:" << first_gap_;
  66     return;
  67   }
  68   // RecordPacketEntropyHash is only intended to be called once per packet.
  69   DCHECK(packet_number > largest_observed_ ||
  70          !packets_entropy_[packet_number - first_gap_].second);
  71
  72   packets_entropy_hash_ ^= entropy_hash;
  73
  74   // Optimize the typical case of no gaps.
  75   if (packet_number == largest_observed_ + 1 && packets_entropy_.empty()) {
  76     ++first_gap_;
  77     largest_observed_ = packet_number;
  78     return;
  79   }
  80   if (packet_number > largest_observed_) {
  81     for (QuicPacketNumber i = 0; i < (packet_number - largest_observed_ - 1);
  82          ++i) {
  83       packets_entropy_.push_back(std::make_pair(0, false));
  84     }
  85     packets_entropy_.push_back(std::make_pair(entropy_hash, true));
  86     largest_observed_ = packet_number;
  87   } else {
  88     packets_entropy_[packet_number - first_gap_] =
  89         std::make_pair(entropy_hash, true);
  90     AdvanceFirstGapAndGarbageCollectEntropyMap();
  91   }
  92
  93   DVLOG(2) << "setting cumulative received entropy hash to: "
  94            << static_cast<int>(packets_entropy_hash_)
  95            << " updated with packet number " << packet_number
  96            << " entropy hash: " << static_cast<int>(entropy_hash);
  97 }
  98
  99 void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
 100     QuicPacketNumber packet_number,
 101     QuicPacketEntropyHash entropy_hash) {
 102   DCHECK_LE(packet_number, largest_observed_);
 103   if (packet_number < first_gap_) {
 104     DVLOG(1) << "Ignoring set entropy at:" << packet_number
 105              << " less than first_gap_:" << first_gap_;
 106     return;
 107   }
 108   while (first_gap_ < packet_number) {
 109     ++first_gap_;
 110     if (!packets_entropy_.empty()) {
 111       packets_entropy_.pop_front();
 112     }
 113   }
 114   // Compute the current entropy by XORing in all entropies received including
 115   // and since packet_number.
 116   packets_entropy_hash_ = entropy_hash;
 117   for (ReceivedEntropyHashes::const_iterator it = packets_entropy_.begin();
 118            it != packets_entropy_.end(); ++it) {
 119     packets_entropy_hash_ ^= it->first;
 120   }
 121
 122   // Garbage collect entries from the beginning of the map.
 123   AdvanceFirstGapAndGarbageCollectEntropyMap();
 124 }
 125
 126 void QuicReceivedPacketManager::EntropyTracker::
 127 AdvanceFirstGapAndGarbageCollectEntropyMap() {
 128   while (!packets_entropy_.empty() && packets_entropy_.front().second) {
 129     ++first_gap_;
 130     packets_entropy_.pop_front();
 131   }
 132 }
 133
 134 QuicReceivedPacketManager::QuicReceivedPacketManager(QuicConnectionStats* stats)
 135     : peer_least_packet_awaiting_ack_(0),
 136       time_largest_observed_(QuicTime::Zero()),
 137       stats_(stats) {
 138   ack_frame_.largest_observed = 0;
 139   ack_frame_.entropy_hash = 0;
 140 }
 141
 142 QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
 143
 144 void QuicReceivedPacketManager::RecordPacketReceived(
 145     QuicByteCount bytes,
 146     const QuicPacketHeader& header,
 147     QuicTime receipt_time) {
 148   QuicPacketNumber packet_number = header.packet_packet_number;
 149   DCHECK(IsAwaitingPacket(packet_number));
 150
 151   InsertMissingPacketsBetween(&ack_frame_, max(ack_frame_.largest_observed + 1,
 152                                                peer_least_packet_awaiting_ack_),
 153                               packet_number);
 154
 155   if (ack_frame_.largest_observed > packet_number) {
 156     // We've gotten one of the out of order packets - remove it from our
 157     // "missing packets" list.
 158     DVLOG(1) << "Removing " << packet_number << " from missing list";
 159     ack_frame_.missing_packets.erase(packet_number);
 160
 161     // Record how out of order stats.
 162     ++stats_->packets_reordered;
 163     stats_->max_sequence_reordering =
 164         max(stats_->max_sequence_reordering,
 165             ack_frame_.largest_observed - packet_number);
 166     int64 reordering_time_us =
 167         receipt_time.Subtract(time_largest_observed_).ToMicroseconds();
 168     stats_->max_time_reordering_us = max(stats_->max_time_reordering_us,
 169                                          reordering_time_us);
 170   }
 171   if (packet_number > ack_frame_.largest_observed) {
 172     ack_frame_.largest_observed = packet_number;
 173     time_largest_observed_ = receipt_time;
 174   }
 175   entropy_tracker_.RecordPacketEntropyHash(packet_number, header.entropy_hash);
 176
 177   received_packet_times_.push_back(std::make_pair(packet_number, receipt_time));
 178
 179   ack_frame_.revived_packets.erase(packet_number);
 180 }
 181
 182 void QuicReceivedPacketManager::RecordPacketRevived(
 183     QuicPacketNumber packet_number) {
 184   LOG_IF(DFATAL, !IsAwaitingPacket(packet_number));
 185   ack_frame_.revived_packets.insert(packet_number);
 186 }
 187
 188 bool QuicReceivedPacketManager::IsMissing(QuicPacketNumber packet_number) {
 189   return ContainsKey(ack_frame_.missing_packets, packet_number);
 190 }
 191
 192 bool QuicReceivedPacketManager::IsAwaitingPacket(
 193     QuicPacketNumber packet_number) {
 194   return ::net::IsAwaitingPacket(ack_frame_, packet_number);
 195 }
 196
 197 namespace {
 198 struct isTooLarge {
 199   explicit isTooLarge(QuicPacketNumber n) : largest_observed_(n) {}
 200   QuicPacketNumber largest_observed_;
 201
 202   // Return true if the packet in p is too different from largest_observed_
 203   // to express.
 204   bool operator()(const std::pair<QuicPacketNumber, QuicTime>& p) const {
 205     return largest_observed_ - p.first >= numeric_limits<uint8>::max();
 206   }
 207 };
 208 }  // namespace
 209
 210 void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
 211     QuicAckFrame* ack_frame, QuicTime approximate_now) {
 212   *ack_frame = ack_frame_;
 213   ack_frame->entropy_hash = EntropyHash(ack_frame_.largest_observed);
 214
 215   if (time_largest_observed_ == QuicTime::Zero()) {
 216     // We have received no packets.
 217     ack_frame->delta_time_largest_observed = QuicTime::Delta::Infinite();
 218     return;
 219   }
 220
 221   // Ensure the delta is zero if approximate now is "in the past".
 222   ack_frame->delta_time_largest_observed =
 223       approximate_now < time_largest_observed_ ?
 224           QuicTime::Delta::Zero() :
 225           approximate_now.Subtract(time_largest_observed_);
 226
 227   // Remove all packets that are too far from largest_observed to express.
 228   received_packet_times_.remove_if(isTooLarge(ack_frame_.largest_observed));
 229
 230   ack_frame->received_packet_times.clear();
 231   ack_frame->received_packet_times.swap(received_packet_times_);
 232 }
 233
 234 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
 235     QuicPacketNumber packet_number) const {
 236   return entropy_tracker_.EntropyHash(packet_number);
 237 }
 238
 239 bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
 240     QuicPacketNumber least_unacked) {
 241   ack_frame_.revived_packets.erase(
 242       ack_frame_.revived_packets.begin(),
 243       ack_frame_.revived_packets.lower_bound(least_unacked));
 244   size_t missing_packets_count = ack_frame_.missing_packets.size();
 245   ack_frame_.missing_packets.erase(
 246       ack_frame_.missing_packets.begin(),
 247       ack_frame_.missing_packets.lower_bound(least_unacked));
 248   return missing_packets_count != ack_frame_.missing_packets.size();
 249 }
 250
 251 void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
 252     const QuicStopWaitingFrame& stop_waiting) {
 253   // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
 254   DCHECK_LE(peer_least_packet_awaiting_ack_, stop_waiting.least_unacked);
 255   if (stop_waiting.least_unacked > peer_least_packet_awaiting_ack_) {
 256     bool missed_packets = DontWaitForPacketsBefore(stop_waiting.least_unacked);
 257     if (missed_packets) {
 258       DVLOG(1) << "Updating entropy hashed since we missed packets";
 259       // There were some missing packets that we won't ever get now. Recalculate
 260       // the received entropy hash.
 261       entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked,
 262                                                 stop_waiting.entropy_hash);
 263     }
 264     peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked;
 265   }
 266   DCHECK(ack_frame_.missing_packets.empty() ||
 267          *ack_frame_.missing_packets.begin() >=
 268              peer_least_packet_awaiting_ack_);
 269 }
 270
 271 bool QuicReceivedPacketManager::HasNewMissingPackets() const {
 272   return !ack_frame_.missing_packets.empty() &&
 273       (ack_frame_.largest_observed -
 274        *ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
 275 }
 276
 277 size_t QuicReceivedPacketManager::NumTrackedPackets() const {
 278   return entropy_tracker_.size();
 279 }
 280
 281 }  // namespace net