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