Home | History | Annotate | Download | only in quic 
      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
    240