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