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