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 <limits>
      8 #include <utility>
      9 
     10 #include "base/logging.h"
     11 #include "base/stl_util.h"
     12 #include "net/base/linked_hash_map.h"
     13 #include "net/quic/crypto/crypto_protocol.h"
     14 #include "net/quic/quic_connection_stats.h"
     15 
     16 using std::make_pair;
     17 using std::max;
     18 using std::min;
     19 using std::numeric_limits;
     20 
     21 namespace net {
     22 
     23 namespace {
     24 
     25 // The maximum number of packets to ack immediately after a missing packet for
     26 // fast retransmission to kick in at the sender.  This limit is created to
     27 // reduce the number of acks sent that have no benefit for fast retransmission.
     28 // Set to the number of nacks needed for fast retransmit plus one for protection
     29 // against an ack loss
     30 const size_t kMaxPacketsAfterNewMissing = 4;
     31 
     32 }
     33 
     34 QuicReceivedPacketManager::EntropyTracker::EntropyTracker()
     35     :  packets_entropy_hash_(0),
     36        first_gap_(1),
     37        largest_observed_(0) {
     38 }
     39 
     40 QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {}
     41 
     42 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash(
     43     QuicPacketSequenceNumber sequence_number) const {
     44   DCHECK_LE(sequence_number, largest_observed_);
     45   if (sequence_number == largest_observed_) {
     46     return packets_entropy_hash_;
     47   }
     48 
     49   DCHECK_GE(sequence_number, first_gap_);
     50   DCHECK_EQ(first_gap_ + packets_entropy_.size() - 1, largest_observed_);
     51   QuicPacketEntropyHash hash = packets_entropy_hash_;
     52   ReceivedEntropyHashes::const_reverse_iterator it = packets_entropy_.rbegin();
     53   for (QuicPacketSequenceNumber i = 0;
     54            i < (largest_observed_ - sequence_number); ++i, ++it) {
     55     hash ^= it->first;
     56   }
     57   return hash;
     58 }
     59 
     60 void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash(
     61     QuicPacketSequenceNumber sequence_number,
     62     QuicPacketEntropyHash entropy_hash) {
     63   if (sequence_number < first_gap_) {
     64     DVLOG(1) << "Ignoring received packet entropy for sequence_number:"
     65              << sequence_number << " less than largest_peer_sequence_number:"
     66              << first_gap_;
     67     return;
     68   }
     69   // RecordPacketEntropyHash is only intended to be called once per packet.
     70   DCHECK(sequence_number > largest_observed_ ||
     71          !packets_entropy_[sequence_number - first_gap_].second);
     72 
     73   packets_entropy_hash_ ^= entropy_hash;
     74 
     75   // Optimize the typical case of no gaps.
     76   if (sequence_number == largest_observed_ + 1 && packets_entropy_.empty()) {
     77     ++first_gap_;
     78     largest_observed_ = sequence_number;
     79     return;
     80   }
     81   if (sequence_number > largest_observed_) {
     82     for (QuicPacketSequenceNumber i = 0;
     83          i < (sequence_number - largest_observed_ - 1); ++i) {
     84       packets_entropy_.push_back(make_pair(0, false));
     85     }
     86     packets_entropy_.push_back(make_pair(entropy_hash, true));
     87     largest_observed_ = sequence_number;
     88   } else {
     89     packets_entropy_[sequence_number - first_gap_] =
     90         make_pair(entropy_hash, true);
     91     AdvanceFirstGapAndGarbageCollectEntropyMap();
     92   }
     93 
     94   DVLOG(2) << "setting cumulative received entropy hash to: "
     95            << static_cast<int>(packets_entropy_hash_)
     96            << " updated with sequence number " << sequence_number
     97            << " entropy hash: " << static_cast<int>(entropy_hash);
     98 }
     99 
    100 void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
    101     QuicPacketSequenceNumber sequence_number,
    102     QuicPacketEntropyHash entropy_hash) {
    103   DCHECK_LE(sequence_number, largest_observed_);
    104   if (sequence_number < first_gap_) {
    105     DVLOG(1) << "Ignoring set entropy at:" << sequence_number
    106              << " less than first_gap_:" << first_gap_;
    107     return;
    108   }
    109   while (first_gap_ < sequence_number) {
    110     ++first_gap_;
    111     if (!packets_entropy_.empty()) {
    112       packets_entropy_.pop_front();
    113     }
    114   }
    115   // Compute the current entropy by XORing in all entropies received including
    116   // and since sequence_number.
    117   packets_entropy_hash_ = entropy_hash;
    118   for (ReceivedEntropyHashes::const_iterator it = packets_entropy_.begin();
    119            it != packets_entropy_.end(); ++it) {
    120     packets_entropy_hash_ ^= it->first;
    121   }
    122 
    123   // Garbage collect entries from the beginning of the map.
    124   AdvanceFirstGapAndGarbageCollectEntropyMap();
    125 }
    126 
    127 void QuicReceivedPacketManager::EntropyTracker::
    128 AdvanceFirstGapAndGarbageCollectEntropyMap() {
    129   while (!packets_entropy_.empty() && packets_entropy_.front().second) {
    130     ++first_gap_;
    131     packets_entropy_.pop_front();
    132   }
    133 }
    134 
    135 QuicReceivedPacketManager::QuicReceivedPacketManager(
    136     QuicConnectionStats* stats)
    137     : peer_least_packet_awaiting_ack_(0),
    138       time_largest_observed_(QuicTime::Zero()),
    139       receive_algorithm_(ReceiveAlgorithmInterface::Create(kTCP)),
    140       stats_(stats) {
    141   ack_frame_.largest_observed = 0;
    142   ack_frame_.entropy_hash = 0;
    143 }
    144 
    145 QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
    146 
    147 void QuicReceivedPacketManager::RecordPacketReceived(
    148     QuicByteCount bytes,
    149     const QuicPacketHeader& header,
    150     QuicTime receipt_time) {
    151   QuicPacketSequenceNumber sequence_number = header.packet_sequence_number;
    152   DCHECK(IsAwaitingPacket(sequence_number));
    153 
    154   InsertMissingPacketsBetween(
    155       &ack_frame_,
    156       max(ack_frame_.largest_observed + 1, peer_least_packet_awaiting_ack_),
    157       sequence_number);
    158 
    159   if (ack_frame_.largest_observed > sequence_number) {
    160     // We've gotten one of the out of order packets - remove it from our
    161     // "missing packets" list.
    162     DVLOG(1) << "Removing " << sequence_number << " from missing list";
    163     ack_frame_.missing_packets.erase(sequence_number);
    164 
    165     // Record how out of order stats.
    166     ++stats_->packets_reordered;
    167     uint32 sequence_gap = ack_frame_.largest_observed - sequence_number;
    168     stats_->max_sequence_reordering =
    169         max(stats_->max_sequence_reordering, sequence_gap);
    170     uint32 reordering_time_us =
    171         receipt_time.Subtract(time_largest_observed_).ToMicroseconds();
    172     stats_->max_time_reordering_us = max(stats_->max_time_reordering_us,
    173                                          reordering_time_us);
    174   }
    175   if (sequence_number > ack_frame_.largest_observed) {
    176     ack_frame_.largest_observed = sequence_number;
    177     time_largest_observed_ = receipt_time;
    178   }
    179   entropy_tracker_.RecordPacketEntropyHash(sequence_number,
    180                                            header.entropy_hash);
    181 
    182   receive_algorithm_->RecordIncomingPacket(
    183       bytes, sequence_number, receipt_time);
    184 
    185   received_packet_times_.push_back(
    186       std::make_pair(sequence_number, receipt_time));
    187 
    188   ack_frame_.revived_packets.erase(sequence_number);
    189 }
    190 
    191 void QuicReceivedPacketManager::RecordPacketRevived(
    192     QuicPacketSequenceNumber sequence_number) {
    193   LOG_IF(DFATAL, !IsAwaitingPacket(sequence_number));
    194   ack_frame_.revived_packets.insert(sequence_number);
    195 }
    196 
    197 bool QuicReceivedPacketManager::IsMissing(
    198     QuicPacketSequenceNumber sequence_number) {
    199   return ContainsKey(ack_frame_.missing_packets, sequence_number);
    200 }
    201 
    202 bool QuicReceivedPacketManager::IsAwaitingPacket(
    203     QuicPacketSequenceNumber sequence_number) {
    204   return ::net::IsAwaitingPacket(ack_frame_, sequence_number);
    205 }
    206 
    207 namespace {
    208 struct isTooLarge {
    209   explicit isTooLarge(QuicPacketSequenceNumber n) : largest_observed_(n) {}
    210   QuicPacketSequenceNumber largest_observed_;
    211 
    212   // Return true if the packet in p is too different from largest_observed_
    213   // to express.
    214   bool operator() (
    215       const std::pair<QuicPacketSequenceNumber, QuicTime>& p) const {
    216     return largest_observed_ - p.first >= numeric_limits<uint8>::max();
    217   }
    218 };
    219 }  // namespace
    220 
    221 void QuicReceivedPacketManager::UpdateReceivedPacketInfo(
    222     QuicAckFrame* ack_frame, QuicTime approximate_now) {
    223   *ack_frame = ack_frame_;
    224   ack_frame->entropy_hash = EntropyHash(ack_frame_.largest_observed);
    225 
    226   if (time_largest_observed_ == QuicTime::Zero()) {
    227     // We have received no packets.
    228     ack_frame->delta_time_largest_observed = QuicTime::Delta::Infinite();
    229     return;
    230   }
    231 
    232   if (approximate_now < time_largest_observed_) {
    233     // Approximate now may well be "in the past".
    234     ack_frame->delta_time_largest_observed = QuicTime::Delta::Zero();
    235     return;
    236   }
    237 
    238   ack_frame->delta_time_largest_observed =
    239       approximate_now.Subtract(time_largest_observed_);
    240 
    241   // Remove all packets that are too far from largest_observed to express.
    242   received_packet_times_.remove_if(isTooLarge(ack_frame_.largest_observed));
    243 
    244   ack_frame->received_packet_times = received_packet_times_;
    245   received_packet_times_.clear();
    246 }
    247 
    248 bool QuicReceivedPacketManager::GenerateCongestionFeedback(
    249     QuicCongestionFeedbackFrame* feedback) {
    250   return receive_algorithm_->GenerateCongestionFeedback(feedback);
    251 }
    252 
    253 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
    254     QuicPacketSequenceNumber sequence_number) const {
    255   return entropy_tracker_.EntropyHash(sequence_number);
    256 }
    257 
    258 bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
    259     QuicPacketSequenceNumber least_unacked) {
    260   ack_frame_.revived_packets.erase(
    261       ack_frame_.revived_packets.begin(),
    262       ack_frame_.revived_packets.lower_bound(least_unacked));
    263   size_t missing_packets_count = ack_frame_.missing_packets.size();
    264   ack_frame_.missing_packets.erase(
    265       ack_frame_.missing_packets.begin(),
    266       ack_frame_.missing_packets.lower_bound(least_unacked));
    267   return missing_packets_count != ack_frame_.missing_packets.size();
    268 }
    269 
    270 void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
    271     const QuicStopWaitingFrame& stop_waiting) {
    272   // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
    273   DCHECK_LE(peer_least_packet_awaiting_ack_, stop_waiting.least_unacked);
    274   if (stop_waiting.least_unacked > peer_least_packet_awaiting_ack_) {
    275     bool missed_packets = DontWaitForPacketsBefore(stop_waiting.least_unacked);
    276     if (missed_packets) {
    277       DVLOG(1) << "Updating entropy hashed since we missed packets";
    278       // There were some missing packets that we won't ever get now. Recalculate
    279       // the received entropy hash.
    280       entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked,
    281                                                 stop_waiting.entropy_hash);
    282     }
    283     peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked;
    284   }
    285   DCHECK(ack_frame_.missing_packets.empty() ||
    286          *ack_frame_.missing_packets.begin() >=
    287              peer_least_packet_awaiting_ack_);
    288 }
    289 
    290 bool QuicReceivedPacketManager::HasNewMissingPackets() {
    291   return !ack_frame_.missing_packets.empty() &&
    292       (ack_frame_.largest_observed -
    293        *ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
    294 }
    295 
    296 }  // namespace net
    297