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