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/quic_connection_stats.h"
  11
  12 using std::make_pair;
  13 using std::max;
  14 using std::min;
  15
  16 namespace net {
  17
  18 namespace {
  19
  20 // The maximum number of packets to ack immediately after a missing packet for
  21 // fast retransmission to kick in at the sender.  This limit is created to
  22 // reduce the number of acks sent that have no benefit for fast retransmission.
  23 // Set to the number of nacks needed for fast retransmit plus one for protection
  24 // against an ack loss
  25 const size_t kMaxPacketsAfterNewMissing = 4;
  26
  27 }
  28
  29 QuicReceivedPacketManager::EntropyTracker::EntropyTracker()
  30     :  packets_entropy_hash_(0),
  31        first_gap_(1),
  32        largest_observed_(0) {
  33 }
  34
  35 QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {}
  36
  37 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash(
  38     QuicPacketSequenceNumber sequence_number) const {
  39   DCHECK_LE(sequence_number, largest_observed_);
  40   if (sequence_number == largest_observed_) {
  41     return packets_entropy_hash_;
  42   }
  43
  44   DCHECK_GE(sequence_number, first_gap_);
  45   ReceivedEntropyMap::const_iterator it =
  46       packets_entropy_.upper_bound(sequence_number);
  47   // When this map is empty we should only query entropy for
  48   // largest_observed_, since no other entropy can be correctly
  49   // calculated, because we're not storing the entropy for any prior packets.
  50   // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium.
  51   // LOG_IF_EVERY_N_SEC(DFATAL, it == packets_entropy_.end(), 10)
  52   LOG_IF(DFATAL, it == packets_entropy_.end())
  53       << "EntropyHash may be unknown. largest_received: "
  54       << largest_observed_
  55       << " sequence_number: " << sequence_number;
  56
  57   // TODO(satyamshekhar): Make this O(1).
  58   QuicPacketEntropyHash hash = packets_entropy_hash_;
  59   for (; it != packets_entropy_.end(); ++it) {
  60     hash ^= it->second;
  61   }
  62   return hash;
  63 }
  64
  65 void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash(
  66     QuicPacketSequenceNumber sequence_number,
  67     QuicPacketEntropyHash entropy_hash) {
  68   if (sequence_number < first_gap_) {
  69     DVLOG(1) << "Ignoring received packet entropy for sequence_number:"
  70              << sequence_number << " less than largest_peer_sequence_number:"
  71              << first_gap_;
  72     return;
  73   }
  74
  75   if (sequence_number > largest_observed_) {
  76     largest_observed_ = sequence_number;
  77   }
  78
  79   packets_entropy_hash_ ^= entropy_hash;
  80   DVLOG(2) << "setting cumulative received entropy hash to: "
  81            << static_cast<int>(packets_entropy_hash_)
  82            << " updated with sequence number " << sequence_number
  83            << " entropy hash: " << static_cast<int>(entropy_hash);
  84
  85   packets_entropy_.insert(make_pair(sequence_number, entropy_hash));
  86   AdvanceFirstGapAndGarbageCollectEntropyMap();
  87 }
  88
  89 void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
  90     QuicPacketSequenceNumber sequence_number,
  91     QuicPacketEntropyHash entropy_hash) {
  92   DCHECK_LE(sequence_number, largest_observed_);
  93   if (sequence_number < first_gap_) {
  94     DVLOG(1) << "Ignoring set entropy at:" << sequence_number
  95              << " less than first_gap_:" << first_gap_;
  96     return;
  97   }
  98   // Compute the current entropy based on the hash.
  99   packets_entropy_hash_ = entropy_hash;
 100   ReceivedEntropyMap::iterator it =
 101       packets_entropy_.lower_bound(sequence_number);
 102   // TODO(satyamshekhar): Make this O(1).
 103   for (; it != packets_entropy_.end(); ++it) {
 104     packets_entropy_hash_ ^= it->second;
 105   }
 106   // Update first_gap_ and discard old entropies.
 107   first_gap_ = sequence_number;
 108   packets_entropy_.erase(
 109       packets_entropy_.begin(),
 110       packets_entropy_.lower_bound(sequence_number));
 111
 112   // Garbage collect entries from the beginning of the map.
 113   AdvanceFirstGapAndGarbageCollectEntropyMap();
 114 }
 115
 116 void QuicReceivedPacketManager::EntropyTracker::
 117 AdvanceFirstGapAndGarbageCollectEntropyMap() {
 118   while (!packets_entropy_.empty()) {
 119     ReceivedEntropyMap::iterator it = packets_entropy_.begin();
 120     if (it->first != first_gap_) {
 121       DCHECK_GT(it->first, first_gap_);
 122       break;
 123     }
 124     packets_entropy_.erase(it);
 125     ++first_gap_;
 126   }
 127 }
 128
 129 QuicReceivedPacketManager::QuicReceivedPacketManager(
 130     CongestionFeedbackType congestion_type,
 131     QuicConnectionStats* stats)
 132     : peer_largest_observed_packet_(0),
 133       least_packet_awaited_by_peer_(1),
 134       peer_least_packet_awaiting_ack_(0),
 135       time_largest_observed_(QuicTime::Zero()),
 136       receive_algorithm_(ReceiveAlgorithmInterface::Create(congestion_type)),
 137       stats_(stats) {
 138   received_info_.largest_observed = 0;
 139   received_info_.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       &received_info_,
 153       max(received_info_.largest_observed + 1, peer_least_packet_awaiting_ack_),
 154       sequence_number);
 155
 156   if (received_info_.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     received_info_.missing_packets.erase(sequence_number);
 161
 162     // Record how out of order stats.
 163     ++stats_->packets_reordered;
 164     uint32 sequence_gap = received_info_.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 > received_info_.largest_observed) {
 173     received_info_.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
 183 void QuicReceivedPacketManager::RecordPacketRevived(
 184     QuicPacketSequenceNumber sequence_number) {
 185   LOG_IF(DFATAL, !IsAwaitingPacket(sequence_number));
 186   received_info_.revived_packets.insert(sequence_number);
 187 }
 188
 189 bool QuicReceivedPacketManager::IsMissing(
 190     QuicPacketSequenceNumber sequence_number) {
 191   return ContainsKey(received_info_.missing_packets, sequence_number);
 192 }
 193
 194 bool QuicReceivedPacketManager::IsAwaitingPacket(
 195     QuicPacketSequenceNumber sequence_number) {
 196   return ::net::IsAwaitingPacket(received_info_, sequence_number);
 197 }
 198
 199 void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
 200     ReceivedPacketInfo* received_info,
 201     QuicTime approximate_now) {
 202   *received_info = received_info_;
 203   received_info->entropy_hash = EntropyHash(received_info_.largest_observed);
 204
 205   if (time_largest_observed_ == QuicTime::Zero()) {
 206     // We have received no packets.
 207     received_info->delta_time_largest_observed = QuicTime::Delta::Infinite();
 208     return;
 209   }
 210
 211   if (approximate_now < time_largest_observed_) {
 212     // Approximate now may well be "in the past".
 213     received_info->delta_time_largest_observed = QuicTime::Delta::Zero();
 214     return;
 215   }
 216
 217   received_info->delta_time_largest_observed =
 218       approximate_now.Subtract(time_largest_observed_);
 219 }
 220
 221 bool QuicReceivedPacketManager::GenerateCongestionFeedback(
 222     QuicCongestionFeedbackFrame* feedback) {
 223   return receive_algorithm_->GenerateCongestionFeedback(feedback);
 224 }
 225
 226 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
 227     QuicPacketSequenceNumber sequence_number) const {
 228   return entropy_tracker_.EntropyHash(sequence_number);
 229 }
 230
 231 void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer(
 232     const ReceivedPacketInfo& received_info) {
 233   // ValidateAck should fail if largest_observed ever shrinks.
 234   DCHECK_LE(peer_largest_observed_packet_, received_info.largest_observed);
 235   peer_largest_observed_packet_ = received_info.largest_observed;
 236
 237   if (received_info.missing_packets.empty()) {
 238     least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1;
 239   } else {
 240     least_packet_awaited_by_peer_ = *(received_info.missing_packets.begin());
 241   }
 242 }
 243
 244 bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
 245     QuicPacketSequenceNumber least_unacked) {
 246   received_info_.revived_packets.erase(
 247       received_info_.revived_packets.begin(),
 248       received_info_.revived_packets.lower_bound(least_unacked));
 249   size_t missing_packets_count = received_info_.missing_packets.size();
 250   received_info_.missing_packets.erase(
 251       received_info_.missing_packets.begin(),
 252       received_info_.missing_packets.lower_bound(least_unacked));
 253   return missing_packets_count != received_info_.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(received_info_.missing_packets.empty() ||
 272          *received_info_.missing_packets.begin() >=
 273              peer_least_packet_awaiting_ack_);
 274 }
 275
 276 bool QuicReceivedPacketManager::HasMissingPackets() {
 277   return !received_info_.missing_packets.empty();
 278 }
 279
 280 bool QuicReceivedPacketManager::HasNewMissingPackets() {
 281   return HasMissingPackets() &&
 282       (received_info_.largest_observed -
 283        *received_info_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
 284 }
 285
 286 }  // namespace net