src/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::QuicReceivedPacketManager(
  30     CongestionFeedbackType congestion_type,
  31     QuicConnectionStats* stats)
  32     : packets_entropy_hash_(0),
  33       largest_sequence_number_(0),
  34       peer_largest_observed_packet_(0),
  35       least_packet_awaited_by_peer_(1),
  36       peer_least_packet_awaiting_ack_(0),
  37       time_largest_observed_(QuicTime::Zero()),
  38       receive_algorithm_(ReceiveAlgorithmInterface::Create(congestion_type)),
  39       stats_(stats) {
  40   received_info_.largest_observed = 0;
  41   received_info_.entropy_hash = 0;
  42 }
  43
  44 QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
  45
  46 void QuicReceivedPacketManager::RecordPacketReceived(
  47     QuicByteCount bytes,
  48     const QuicPacketHeader& header,
  49     QuicTime receipt_time) {
  50   QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
  51   DCHECK(IsAwaitingPacket(sequence_number));
  52
  53   InsertMissingPacketsBetween(
  54       &received_info_,
  55       max(received_info_.largest_observed + 1, peer_least_packet_awaiting_ack_),
  56       header.packet_sequence_number);
  57
  58   if (received_info_.largest_observed > header.packet_sequence_number) {
  59     // We've gotten one of the out of order packets - remove it from our
  60     // "missing packets" list.
  61     DVLOG(1) << "Removing " << sequence_number << " from missing list";
  62     received_info_.missing_packets.erase(sequence_number);
  63
  64     // Record how out of order stats.
  65     ++stats_->packets_reordered;
  66     uint32 sequence_gap = received_info_.largest_observed - sequence_number;
  67     stats_->max_sequence_reordering =
  68         max(stats_->max_sequence_reordering, sequence_gap);
  69     uint32 reordering_time_us =
  70         receipt_time.Subtract(time_largest_observed_).ToMicroseconds();
  71     stats_->max_time_reordering_us = max(stats_->max_time_reordering_us,
  72                                          reordering_time_us);
  73   }
  74   if (header.packet_sequence_number > received_info_.largest_observed) {
  75     received_info_.largest_observed = header.packet_sequence_number;
  76     time_largest_observed_ = receipt_time;
  77   }
  78   RecordPacketEntropyHash(sequence_number, header.entropy_hash);
  79
  80   receive_algorithm_->RecordIncomingPacket(
  81       bytes, sequence_number, receipt_time);
  82 }
  83
  84 void QuicReceivedPacketManager::RecordPacketRevived(
  85     QuicPacketSequenceNumber sequence_number) {
  86   LOG_IF(DFATAL, !IsAwaitingPacket(sequence_number));
  87   received_info_.revived_packets.insert(sequence_number);
  88 }
  89
  90 bool QuicReceivedPacketManager::IsMissing(
  91     QuicPacketSequenceNumber sequence_number) {
  92   return ContainsKey(received_info_.missing_packets, sequence_number);
  93 }
  94
  95 bool QuicReceivedPacketManager::IsAwaitingPacket(
  96     QuicPacketSequenceNumber sequence_number) {
  97   return ::net::IsAwaitingPacket(received_info_, sequence_number);
  98 }
  99
 100 void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
 101     ReceivedPacketInfo* received_info,
 102     QuicTime approximate_now) {
 103   *received_info = received_info_;
 104   received_info->entropy_hash = EntropyHash(received_info_.largest_observed);
 105
 106   if (time_largest_observed_ == QuicTime::Zero()) {
 107     // We have received no packets.
 108     received_info->delta_time_largest_observed = QuicTime::Delta::Infinite();
 109     return;
 110   }
 111
 112   if (approximate_now < time_largest_observed_) {
 113     // Approximate now may well be "in the past".
 114     received_info->delta_time_largest_observed = QuicTime::Delta::Zero();
 115     return;
 116   }
 117
 118   received_info->delta_time_largest_observed =
 119       approximate_now.Subtract(time_largest_observed_);
 120 }
 121
 122 void QuicReceivedPacketManager::RecordPacketEntropyHash(
 123     QuicPacketSequenceNumber sequence_number,
 124     QuicPacketEntropyHash entropy_hash) {
 125   if (sequence_number < largest_sequence_number_) {
 126     DVLOG(1) << "Ignoring received packet entropy for sequence_number:"
 127              << sequence_number << " less than largest_peer_sequence_number:"
 128              << largest_sequence_number_;
 129     return;
 130   }
 131   packets_entropy_.insert(make_pair(sequence_number, entropy_hash));
 132   packets_entropy_hash_ ^= entropy_hash;
 133   DVLOG(2) << "setting cumulative received entropy hash to: "
 134            << static_cast<int>(packets_entropy_hash_)
 135            << " updated with sequence number " << sequence_number
 136            << " entropy hash: " << static_cast<int>(entropy_hash);
 137 }
 138
 139 bool QuicReceivedPacketManager::GenerateCongestionFeedback(
 140     QuicCongestionFeedbackFrame* feedback) {
 141   return receive_algorithm_->GenerateCongestionFeedback(feedback);
 142 }
 143
 144 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
 145     QuicPacketSequenceNumber sequence_number) const {
 146   DCHECK_LE(sequence_number, received_info_.largest_observed);
 147   DCHECK_GE(sequence_number, largest_sequence_number_);
 148   if (sequence_number == received_info_.largest_observed) {
 149     return packets_entropy_hash_;
 150   }
 151
 152   ReceivedEntropyMap::const_iterator it =
 153       packets_entropy_.upper_bound(sequence_number);
 154   // When this map is empty we should only query entropy for
 155   // received_info_.largest_observed, since no other entropy can be correctly
 156   // calculated, because we're not storing the entropy for any prior packets.
 157   // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium.
 158   // LOG_IF_EVERY_N_SEC(DFATAL, it == packets_entropy_.end(), 10)
 159   LOG_IF(DFATAL, it == packets_entropy_.end())
 160       << "EntropyHash may be unknown. largest_received: "
 161       << received_info_.largest_observed
 162       << " sequence_number: " << sequence_number;
 163
 164   // TODO(satyamshekhar): Make this O(1).
 165   QuicPacketEntropyHash hash = packets_entropy_hash_;
 166   for (; it != packets_entropy_.end(); ++it) {
 167     hash ^= it->second;
 168   }
 169   return hash;
 170 }
 171
 172 void QuicReceivedPacketManager::RecalculateEntropyHash(
 173     QuicPacketSequenceNumber peer_least_unacked,
 174     QuicPacketEntropyHash entropy_hash) {
 175   DCHECK_LE(peer_least_unacked, received_info_.largest_observed);
 176   if (peer_least_unacked < largest_sequence_number_) {
 177     DVLOG(1) << "Ignoring received peer_least_unacked:" << peer_least_unacked
 178              << " less than largest_peer_sequence_number:"
 179              << largest_sequence_number_;
 180     return;
 181   }
 182   largest_sequence_number_ = peer_least_unacked;
 183   packets_entropy_hash_ = entropy_hash;
 184   ReceivedEntropyMap::iterator it =
 185       packets_entropy_.lower_bound(peer_least_unacked);
 186   // TODO(satyamshekhar): Make this O(1).
 187   for (; it != packets_entropy_.end(); ++it) {
 188     packets_entropy_hash_ ^= it->second;
 189   }
 190   // Discard entropies before least unacked.
 191   packets_entropy_.erase(
 192       packets_entropy_.begin(),
 193       packets_entropy_.lower_bound(
 194           min(peer_least_unacked, received_info_.largest_observed)));
 195 }
 196
 197 void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer(
 198     const ReceivedPacketInfo& received_info) {
 199   // ValidateAck should fail if largest_observed ever shrinks.
 200   DCHECK_LE(peer_largest_observed_packet_, received_info.largest_observed);
 201   peer_largest_observed_packet_ = received_info.largest_observed;
 202
 203   if (received_info.missing_packets.empty()) {
 204     least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1;
 205   } else {
 206     least_packet_awaited_by_peer_ = *(received_info.missing_packets.begin());
 207   }
 208 }
 209
 210 bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
 211     QuicPacketSequenceNumber least_unacked) {
 212   received_info_.revived_packets.erase(
 213       received_info_.revived_packets.begin(),
 214       received_info_.revived_packets.lower_bound(least_unacked));
 215   size_t missing_packets_count = received_info_.missing_packets.size();
 216   received_info_.missing_packets.erase(
 217       received_info_.missing_packets.begin(),
 218       received_info_.missing_packets.lower_bound(least_unacked));
 219   return missing_packets_count != received_info_.missing_packets.size();
 220 }
 221
 222 void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
 223     const QuicStopWaitingFrame& stop_waiting) {
 224   // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
 225   DCHECK_LE(peer_least_packet_awaiting_ack_, stop_waiting.least_unacked);
 226   if (stop_waiting.least_unacked > peer_least_packet_awaiting_ack_) {
 227     bool missed_packets = DontWaitForPacketsBefore(stop_waiting.least_unacked);
 228     if (missed_packets || stop_waiting.least_unacked >
 229             received_info_.largest_observed + 1) {
 230       DVLOG(1) << "Updating entropy hashed since we missed packets";
 231       // There were some missing packets that we won't ever get now. Recalculate
 232       // the received entropy hash.
 233       RecalculateEntropyHash(stop_waiting.least_unacked,
 234                              stop_waiting.entropy_hash);
 235     }
 236     peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked;
 237   }
 238   DCHECK(received_info_.missing_packets.empty() ||
 239          *received_info_.missing_packets.begin() >=
 240              peer_least_packet_awaiting_ack_);
 241 }
 242
 243 bool QuicReceivedPacketManager::HasMissingPackets() {
 244   return !received_info_.missing_packets.empty();
 245 }
 246
 247 bool QuicReceivedPacketManager::HasNewMissingPackets() {
 248   return HasMissingPackets() &&
 249       (received_info_.largest_observed -
 250        *received_info_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
 251 }
 252
 253 }  // namespace net