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(
 136     QuicConnectionStats* stats)
 137     : peer_least_packet_awaiting_ack_(0),
 138       time_largest_observed_(QuicTime::Zero()),
 139       receive_algorithm_(ReceiveAlgorithmInterface::Create(kTCP)),
 140       stats_(stats) {
 141   ack_frame_.largest_observed = 0;
 142   ack_frame_.entropy_hash = 0;
 143 }
 144
 145 QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
 146
 147 void QuicReceivedPacketManager::RecordPacketReceived(
 148     QuicByteCount bytes,
 149     const QuicPacketHeader& header,
 150     QuicTime receipt_time) {
 151   QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
 152   DCHECK(IsAwaitingPacket(sequence_number));
 153
 154   InsertMissingPacketsBetween(
 155       &ack_frame_,
 156       max(ack_frame_.largest_observed + 1, peer_least_packet_awaiting_ack_),
 157       sequence_number);
 158
 159   if (ack_frame_.largest_observed > sequence_number) {
 160     // We've gotten one of the out of order packets - remove it from our
 161     // "missing packets" list.
 162     DVLOG(1) << "Removing " << sequence_number << " from missing list";
 163     ack_frame_.missing_packets.erase(sequence_number);
 164
 165     // Record how out of order stats.
 166     ++stats_->packets_reordered;
 167     uint32 sequence_gap = ack_frame_.largest_observed - sequence_number;
 168     stats_->max_sequence_reordering =
 169         max(stats_->max_sequence_reordering, sequence_gap);
 170     uint32 reordering_time_us =
 171         receipt_time.Subtract(time_largest_observed_).ToMicroseconds();
 172     stats_->max_time_reordering_us = max(stats_->max_time_reordering_us,
 173                                          reordering_time_us);
 174   }
 175   if (sequence_number > ack_frame_.largest_observed) {
 176     ack_frame_.largest_observed = sequence_number;
 177     time_largest_observed_ = receipt_time;
 178   }
 179   entropy_tracker_.RecordPacketEntropyHash(sequence_number,
 180                                            header.entropy_hash);
 181
 182   receive_algorithm_->RecordIncomingPacket(
 183       bytes, sequence_number, receipt_time);
 184
 185   received_packet_times_.push_back(
 186       std::make_pair(sequence_number, receipt_time));
 187
 188   ack_frame_.revived_packets.erase(sequence_number);
 189 }
 190
 191 void QuicReceivedPacketManager::RecordPacketRevived(
 192     QuicPacketSequenceNumber sequence_number) {
 193   LOG_IF(DFATAL, !IsAwaitingPacket(sequence_number));
 194   ack_frame_.revived_packets.insert(sequence_number);
 195 }
 196
 197 bool QuicReceivedPacketManager::IsMissing(
 198     QuicPacketSequenceNumber sequence_number) {
 199   return ContainsKey(ack_frame_.missing_packets, sequence_number);
 200 }
 201
 202 bool QuicReceivedPacketManager::IsAwaitingPacket(
 203     QuicPacketSequenceNumber sequence_number) {
 204   return ::net::IsAwaitingPacket(ack_frame_, sequence_number);
 205 }
 206
 207 namespace {
 208 struct isTooLarge {
 209   explicit isTooLarge(QuicPacketSequenceNumber n) : largest_observed_(n) {}
 210   QuicPacketSequenceNumber largest_observed_;
 211
 212   // Return true if the packet in p is too different from largest_observed_
 213   // to express.
 214   bool operator() (
 215       const std::pair<QuicPacketSequenceNumber, QuicTime>& p) const {
 216     return largest_observed_ - p.first >= numeric_limits<uint8>::max();
 217   }
 218 };
 219 }  // namespace
 220
 221 void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
 222     QuicAckFrame* ack_frame, QuicTime approximate_now) {
 223   *ack_frame = ack_frame_;
 224   ack_frame->entropy_hash = EntropyHash(ack_frame_.largest_observed);
 225
 226   if (time_largest_observed_ == QuicTime::Zero()) {
 227     // We have received no packets.
 228     ack_frame->delta_time_largest_observed = QuicTime::Delta::Infinite();
 229     return;
 230   }
 231
 232   if (approximate_now < time_largest_observed_) {
 233     // Approximate now may well be "in the past".
 234     ack_frame->delta_time_largest_observed = QuicTime::Delta::Zero();
 235     return;
 236   }
 237
 238   ack_frame->delta_time_largest_observed =
 239       approximate_now.Subtract(time_largest_observed_);
 240
 241   // Remove all packets that are too far from largest_observed to express.
 242   received_packet_times_.remove_if(isTooLarge(ack_frame_.largest_observed));
 243
 244   ack_frame->received_packet_times = received_packet_times_;
 245   received_packet_times_.clear();
 246 }
 247
 248 bool QuicReceivedPacketManager::GenerateCongestionFeedback(
 249     QuicCongestionFeedbackFrame* feedback) {
 250   return receive_algorithm_->GenerateCongestionFeedback(feedback);
 251 }
 252
 253 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
 254     QuicPacketSequenceNumber sequence_number) const {
 255   return entropy_tracker_.EntropyHash(sequence_number);
 256 }
 257
 258 bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
 259     QuicPacketSequenceNumber least_unacked) {
 260   ack_frame_.revived_packets.erase(
 261       ack_frame_.revived_packets.begin(),
 262       ack_frame_.revived_packets.lower_bound(least_unacked));
 263   size_t missing_packets_count = ack_frame_.missing_packets.size();
 264   ack_frame_.missing_packets.erase(
 265       ack_frame_.missing_packets.begin(),
 266       ack_frame_.missing_packets.lower_bound(least_unacked));
 267   return missing_packets_count != ack_frame_.missing_packets.size();
 268 }
 269
 270 void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
 271     const QuicStopWaitingFrame& stop_waiting) {
 272   // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
 273   DCHECK_LE(peer_least_packet_awaiting_ack_, stop_waiting.least_unacked);
 274   if (stop_waiting.least_unacked > peer_least_packet_awaiting_ack_) {
 275     bool missed_packets = DontWaitForPacketsBefore(stop_waiting.least_unacked);
 276     if (missed_packets) {
 277       DVLOG(1) << "Updating entropy hashed since we missed packets";
 278       // There were some missing packets that we won't ever get now. Recalculate
 279       // the received entropy hash.
 280       entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked,
 281                                                 stop_waiting.entropy_hash);
 282     }
 283     peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked;
 284   }
 285   DCHECK(ack_frame_.missing_packets.empty() ||
 286          *ack_frame_.missing_packets.begin() >=
 287              peer_least_packet_awaiting_ack_);
 288 }
 289
 290 bool QuicReceivedPacketManager::HasNewMissingPackets() {
 291   return !ack_frame_.missing_packets.empty() &&
 292       (ack_frame_.largest_observed -
 293        *ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
 294 }
 295
 296 }  // namespace net