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 "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   // |largest_received_sequence_number_|.
    102   // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium.
    103   // LOG_IF_EVERY_N_SEC(WARNING, it != packets_entropy_.end(), 10)
    104   LOG_IF(WARNING, it != packets_entropy_.end())
    105       << "largest_received: " << received_info_.largest_observed
    106       << " sequence_number: " << sequence_number;
    107 
    108   // TODO(satyamshekhar): Make this O(1).
    109   QuicPacketEntropyHash hash = packets_entropy_hash_;
    110   for (; it != packets_entropy_.end(); ++it) {
    111     hash ^= it->second;
    112   }
    113   return hash;
    114 }
    115 
    116 void QuicReceivedPacketManager::RecalculateEntropyHash(
    117     QuicPacketSequenceNumber peer_least_unacked,
    118     QuicPacketEntropyHash entropy_hash) {
    119   DCHECK_LE(peer_least_unacked, received_info_.largest_observed);
    120   if (peer_least_unacked < largest_sequence_number_) {
    121     DLOG(INFO) << "Ignoring received peer_least_unacked:" << peer_least_unacked
    122                << " less than largest_peer_sequence_number:"
    123                << largest_sequence_number_;
    124     return;
    125   }
    126   largest_sequence_number_ = peer_least_unacked;
    127   packets_entropy_hash_ = entropy_hash;
    128   ReceivedEntropyMap::iterator it =
    129       packets_entropy_.lower_bound(peer_least_unacked);
    130   // TODO(satyamshekhar): Make this O(1).
    131   for (; it != packets_entropy_.end(); ++it) {
    132     packets_entropy_hash_ ^= it->second;
    133   }
    134   // Discard entropies before least unacked.
    135   packets_entropy_.erase(
    136       packets_entropy_.begin(),
    137       packets_entropy_.lower_bound(
    138           min(peer_least_unacked, received_info_.largest_observed)));
    139 }
    140 
    141 void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer(
    142     const QuicAckFrame& incoming_ack) {
    143   // ValidateAck should fail if largest_observed ever shrinks.
    144   DCHECK_LE(peer_largest_observed_packet_,
    145             incoming_ack.received_info.largest_observed);
    146   peer_largest_observed_packet_ = incoming_ack.received_info.largest_observed;
    147 
    148   if (incoming_ack.received_info.missing_packets.empty()) {
    149     least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1;
    150   } else {
    151     least_packet_awaited_by_peer_ =
    152         *(incoming_ack.received_info.missing_packets.begin());
    153   }
    154 }
    155 
    156 bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
    157     QuicPacketSequenceNumber least_unacked) {
    158   size_t missing_packets_count = received_info_.missing_packets.size();
    159   received_info_.missing_packets.erase(
    160       received_info_.missing_packets.begin(),
    161       received_info_.missing_packets.lower_bound(least_unacked));
    162   return missing_packets_count != received_info_.missing_packets.size();
    163 }
    164 
    165 void QuicReceivedPacketManager::UpdatePacketInformationSentByPeer(
    166     const QuicAckFrame& incoming_ack) {
    167   // ValidateAck() should fail if peer_least_packet_awaiting_ack_ shrinks.
    168   DCHECK_LE(peer_least_packet_awaiting_ack_,
    169             incoming_ack.sent_info.least_unacked);
    170   if (incoming_ack.sent_info.least_unacked > peer_least_packet_awaiting_ack_) {
    171     bool missed_packets =
    172         DontWaitForPacketsBefore(incoming_ack.sent_info.least_unacked);
    173     if (missed_packets || incoming_ack.sent_info.least_unacked >
    174             received_info_.largest_observed + 1) {
    175       DVLOG(1) << "Updating entropy hashed since we missed packets";
    176       // There were some missing packets that we won't ever get now. Recalculate
    177       // the received entropy hash.
    178       RecalculateEntropyHash(incoming_ack.sent_info.least_unacked,
    179                              incoming_ack.sent_info.entropy_hash);
    180     }
    181     peer_least_packet_awaiting_ack_ = incoming_ack.sent_info.least_unacked;
    182   }
    183   DCHECK(received_info_.missing_packets.empty() ||
    184          *received_info_.missing_packets.begin() >=
    185              peer_least_packet_awaiting_ack_);
    186 }
    187 
    188 }  // namespace net
    189