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 "net/base/linked_hash_map.h"
   9
  10 using std::make_pair;
  11 using std::max;
  12 using std::min;
  13
  14 namespace net {
  15
  16 QuicReceivedPacketManager::QuicReceivedPacketManager()
  17     : packets_entropy_hash_(0),
  18       largest_sequence_number_(0),
  19       peer_largest_observed_packet_(0),
  20       least_packet_awaited_by_peer_(1),
  21       peer_least_packet_awaiting_ack_(0),
  22       time_largest_observed_(QuicTime::Zero()) {
  23   received_info_.largest_observed = 0;
  24   received_info_.entropy_hash = 0;
  25 }
  26
  27 QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
  28
  29 void QuicReceivedPacketManager::RecordPacketReceived(
  30     const QuicPacketHeader& header, QuicTime receipt_time) {
  31   QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
  32   DCHECK(IsAwaitingPacket(sequence_number));
  33
  34   InsertMissingPacketsBetween(
  35       &received_info_,
  36       max(received_info_.largest_observed + 1, peer_least_packet_awaiting_ack_),
  37       header.packet_sequence_number);
  38
  39   if (received_info_.largest_observed > header.packet_sequence_number) {
  40     // We've gotten one of the out of order packets - remove it from our
  41     // "missing packets" list.
  42     DVLOG(1) << "Removing " << sequence_number << " from missing list";
  43     received_info_.missing_packets.erase(sequence_number);
  44   }
  45   if (header.packet_sequence_number > received_info_.largest_observed) {
  46     received_info_.largest_observed = header.packet_sequence_number;
  47     time_largest_observed_ = receipt_time;
  48   }
  49   RecordPacketEntropyHash(sequence_number, header.entropy_hash);
  50 }
  51
  52 bool QuicReceivedPacketManager::IsAwaitingPacket(
  53     QuicPacketSequenceNumber sequence_number) {
  54   return ::net::IsAwaitingPacket(received_info_, sequence_number);
  55 }
  56
  57 void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
  58     ReceivedPacketInfo* received_info, QuicTime approximate_now) {
  59   *received_info = received_info_;
  60   received_info->entropy_hash = EntropyHash(received_info_.largest_observed);
  61   if (time_largest_observed_ == QuicTime::Zero()) {
  62     // We have not received any new higher sequence numbers since we sent our
  63     // last ACK.
  64     received_info->delta_time_largest_observed = QuicTime::Delta::Infinite();
  65   } else {
  66     received_info->delta_time_largest_observed =
  67         approximate_now.Subtract(time_largest_observed_);
  68
  69     time_largest_observed_ = QuicTime::Zero();
  70   }
  71 }
  72
  73 void QuicReceivedPacketManager::RecordPacketEntropyHash(
  74     QuicPacketSequenceNumber sequence_number,
  75     QuicPacketEntropyHash entropy_hash) {
  76   if (sequence_number < largest_sequence_number_) {
  77     DLOG(INFO) << "Ignoring received packet entropy for sequence_number:"
  78                << sequence_number << " less than largest_peer_sequence_number:"
  79                << largest_sequence_number_;
  80     return;
  81   }
  82   packets_entropy_.insert(make_pair(sequence_number, entropy_hash));
  83   packets_entropy_hash_ ^= entropy_hash;
  84   DVLOG(2) << "setting cumulative received entropy hash to: "
  85            << static_cast<int>(packets_entropy_hash_)
  86            << " updated with sequence number " << sequence_number
  87            << " entropy hash: " << static_cast<int>(entropy_hash);
  88 }
  89
  90 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
  91     QuicPacketSequenceNumber sequence_number) const {
  92   DCHECK_LE(sequence_number, received_info_.largest_observed);
  93   DCHECK_GE(sequence_number, largest_sequence_number_);
  94   if (sequence_number == received_info_.largest_observed) {
  95     return packets_entropy_hash_;
  96   }
  97
  98   ReceivedEntropyMap::const_iterator it =
  99       packets_entropy_.upper_bound(sequence_number);
 100   // When this map is empty we should only query entropy for
 101   // received_info_.largest_observed, since no other entropy can be correctly
 102   // calculated, because we're not storing the entropy for any prior packets.
 103   // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium.
 104   // LOG_IF_EVERY_N_SEC(DFATAL, it == packets_entropy_.end(), 10)
 105   LOG_IF(DFATAL, it == packets_entropy_.end())
 106       << "EntropyHash may be unknown. largest_received: "
 107       << received_info_.largest_observed
 108       << " sequence_number: " << sequence_number;
 109
 110   // TODO(satyamshekhar): Make this O(1).
 111   QuicPacketEntropyHash hash = packets_entropy_hash_;
 112   for (; it != packets_entropy_.end(); ++it) {
 113     hash ^= it->second;
 114   }
 115   return hash;
 116 }
 117
 118 void QuicReceivedPacketManager::RecalculateEntropyHash(
 119     QuicPacketSequenceNumber peer_least_unacked,
 120     QuicPacketEntropyHash entropy_hash) {
 121   DCHECK_LE(peer_least_unacked, received_info_.largest_observed);
 122   if (peer_least_unacked < largest_sequence_number_) {
 123     DLOG(INFO) << "Ignoring received peer_least_unacked:" << peer_least_unacked
 124                << " less than largest_peer_sequence_number:"
 125                << largest_sequence_number_;
 126     return;
 127   }
 128   largest_sequence_number_ = peer_least_unacked;
 129   packets_entropy_hash_ = entropy_hash;
 130   ReceivedEntropyMap::iterator it =
 131       packets_entropy_.lower_bound(peer_least_unacked);
 132   // TODO(satyamshekhar): Make this O(1).
 133   for (; it != packets_entropy_.end(); ++it) {
 134     packets_entropy_hash_ ^= it->second;
 135   }
 136   // Discard entropies before least unacked.
 137   packets_entropy_.erase(
 138       packets_entropy_.begin(),
 139       packets_entropy_.lower_bound(
 140           min(peer_least_unacked, received_info_.largest_observed)));
 141 }
 142
 143 void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer(
 144     const QuicAckFrame& incoming_ack) {
 145   // ValidateAck should fail if largest_observed ever shrinks.
 146   DCHECK_LE(peer_largest_observed_packet_,
 147             incoming_ack.received_info.largest_observed);
 148   peer_largest_observed_packet_ = incoming_ack.received_info.largest_observed;
 149
 150   if (incoming_ack.received_info.missing_packets.empty()) {
 151     least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1;
 152   } else {
 153     least_packet_awaited_by_peer_ =
 154         *(incoming_ack.received_info.missing_packets.begin());
 155   }
 156 }
 157
 158 bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
 159     QuicPacketSequenceNumber least_unacked) {
 160   size_t missing_packets_count = received_info_.missing_packets.size();
 161   received_info_.missing_packets.erase(
 162       received_info_.missing_packets.begin(),
 163       received_info_.missing_packets.lower_bound(least_unacked));
 164   return missing_packets_count != received_info_.missing_packets.size();
 165 }
 166
 167 void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
 168     const QuicAckFrame& incoming_ack) {
 169   // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
 170   DCHECK_LE(peer_least_packet_awaiting_ack_,
 171             incoming_ack.sent_info.least_unacked);
 172   if (incoming_ack.sent_info.least_unacked > peer_least_packet_awaiting_ack_) {
 173     bool missed_packets =
 174         DontWaitForPacketsBefore(incoming_ack.sent_info.least_unacked);
 175     if (missed_packets || incoming_ack.sent_info.least_unacked >
 176             received_info_.largest_observed + 1) {
 177       DVLOG(1) << "Updating entropy hashed since we missed packets";
 178       // There were some missing packets that we won't ever get now. Recalculate
 179       // the received entropy hash.
 180       RecalculateEntropyHash(incoming_ack.sent_info.least_unacked,
 181                              incoming_ack.sent_info.entropy_hash);
 182     }
 183     peer_least_packet_awaiting_ack_ = incoming_ack.sent_info.least_unacked;
 184   }
 185   DCHECK(received_info_.missing_packets.empty() ||
 186          *received_info_.missing_packets.begin() >=
 187              peer_least_packet_awaiting_ack_);
 188 }
 189
 190 size_t QuicReceivedPacketManager::GetNumMissingPackets() {
 191   return received_info_.missing_packets.size();
 192 }
 193
 194 }  // namespace net