Landing Recent QUIC Changes.

net/quic/quic_received_packet_manager.cc

 // Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/quic/quic_received_packet_manager.h"
 
 #include "base/logging.h"
 #include "base/stl_util.h"
 #include "net/base/linked_hash_map.h"
 #include "net/quic/quic_connection_stats.h"
@@ skipping 24 matching lines @@
 QuicReceivedPacketManager::EntropyTracker::~EntropyTracker() {}
 
 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyTracker::EntropyHash(
     QuicPacketSequenceNumber sequence_number) const {
   DCHECK_LE(sequence_number, largest_observed_);
   if (sequence_number == largest_observed_) {
     return packets_entropy_hash_;
   }
 
   DCHECK_GE(sequence_number, first_gap_);
-  ReceivedEntropyMap::const_iterator it =
-      packets_entropy_.upper_bound(sequence_number);
-  // When this map is empty we should only query entropy for
-  // largest_observed_, since no other entropy can be correctly
-  // calculated, because we're not storing the entropy for any prior packets.
-  // TODO(rtenneti): add support for LOG_IF_EVERY_N_SEC to chromium.
-  // LOG_IF_EVERY_N_SEC(DFATAL, it == packets_entropy_.end(), 10)
-  LOG_IF(DFATAL, it == packets_entropy_.end())
-      << "EntropyHash may be unknown. largest_received: "
-      << largest_observed_
-      << " sequence_number: " << sequence_number;
-
-  // TODO(satyamshekhar): Make this O(1).
+  DCHECK_EQ(first_gap_ + packets_entropy_.size() - 1, largest_observed_);
   QuicPacketEntropyHash hash = packets_entropy_hash_;
-  for (; it != packets_entropy_.end(); ++it) {
-    hash ^= it->second;
+  ReceivedEntropyHashes::const_reverse_iterator it = packets_entropy_.rbegin();
+  for (QuicPacketSequenceNumber i = 0;
+           i < (largest_observed_ - sequence_number); ++i, ++it) {
+    hash ^= it->first;
   }
   return hash;
 }
 
 void QuicReceivedPacketManager::EntropyTracker::RecordPacketEntropyHash(
     QuicPacketSequenceNumber sequence_number,
     QuicPacketEntropyHash entropy_hash) {
   if (sequence_number < first_gap_) {
     DVLOG(1) << "Ignoring received packet entropy for sequence_number:"
              << sequence_number << " less than largest_peer_sequence_number:"
              << first_gap_;
     return;
   }
+  // RecordPacketEntropyHash is only intended to be called once per packet.
+  DCHECK(sequence_number > largest_observed_ ||
+         !packets_entropy_[sequence_number - first_gap_].second);
 
+  packets_entropy_hash_ ^= entropy_hash;
+
+  // Optimize the typical case of no gaps.
+  if (sequence_number == largest_observed_ + 1 && packets_entropy_.empty()) {
+    ++first_gap_;
+    largest_observed_ = sequence_number;
+    return;
+  }
   if (sequence_number > largest_observed_) {
+    for (QuicPacketSequenceNumber i = 0;
+         i < (sequence_number - largest_observed_ - 1); ++i) {
+      packets_entropy_.push_back(make_pair(0, false));
+    }
+    packets_entropy_.push_back(make_pair(entropy_hash, true));
     largest_observed_ = sequence_number;
+  } else {
+    packets_entropy_[sequence_number - first_gap_] =
+        make_pair(entropy_hash, true);
+    AdvanceFirstGapAndGarbageCollectEntropyMap();
   }
 
-  packets_entropy_hash_ ^= entropy_hash;
   DVLOG(2) << "setting cumulative received entropy hash to: "
            << static_cast<int>(packets_entropy_hash_)
            << " updated with sequence number " << sequence_number
            << " entropy hash: " << static_cast<int>(entropy_hash);
-
-  packets_entropy_.insert(make_pair(sequence_number, entropy_hash));
-  AdvanceFirstGapAndGarbageCollectEntropyMap();
 }
 
 void QuicReceivedPacketManager::EntropyTracker::SetCumulativeEntropyUpTo(
     QuicPacketSequenceNumber sequence_number,
     QuicPacketEntropyHash entropy_hash) {
   DCHECK_LE(sequence_number, largest_observed_);
   if (sequence_number < first_gap_) {
     DVLOG(1) << "Ignoring set entropy at:" << sequence_number
              << " less than first_gap_:" << first_gap_;
     return;
   }
-  // Compute the current entropy based on the hash.
+  while (first_gap_ < sequence_number) {
+    ++first_gap_;
+    if (!packets_entropy_.empty()) {
+      packets_entropy_.pop_front();
+    }
+  }
+  // Compute the current entropy by XORing in all entropies received including
+  // and since sequence_number.
   packets_entropy_hash_ = entropy_hash;
-  ReceivedEntropyMap::iterator it =
-      packets_entropy_.lower_bound(sequence_number);
-  // TODO(satyamshekhar): Make this O(1).
-  for (; it != packets_entropy_.end(); ++it) {
-    packets_entropy_hash_ ^= it->second;
+  for (ReceivedEntropyHashes::const_iterator it = packets_entropy_.begin();
+           it != packets_entropy_.end(); ++it) {
+    packets_entropy_hash_ ^= it->first;
   }
-  // Update first_gap_ and discard old entropies.
-  first_gap_ = sequence_number;
-  packets_entropy_.erase(
-      packets_entropy_.begin(),
-      packets_entropy_.lower_bound(sequence_number));
 
   // Garbage collect entries from the beginning of the map.
   AdvanceFirstGapAndGarbageCollectEntropyMap();
 }
 
 void QuicReceivedPacketManager::EntropyTracker::
 AdvanceFirstGapAndGarbageCollectEntropyMap() {
-  while (!packets_entropy_.empty()) {
-    ReceivedEntropyMap::iterator it = packets_entropy_.begin();
-    if (it->first != first_gap_) {
-      DCHECK_GT(it->first, first_gap_);
-      break;
-    }
-    packets_entropy_.erase(it);
+  while (!packets_entropy_.empty() && packets_entropy_.front().second) {
     ++first_gap_;
+    packets_entropy_.pop_front();
   }
 }
 
 QuicReceivedPacketManager::QuicReceivedPacketManager(
     CongestionFeedbackType congestion_type,
     QuicConnectionStats* stats)
-    : peer_largest_observed_packet_(0),
-      least_packet_awaited_by_peer_(1),
-      peer_least_packet_awaiting_ack_(0),
+    : peer_least_packet_awaiting_ack_(0),
       time_largest_observed_(QuicTime::Zero()),
       receive_algorithm_(ReceiveAlgorithmInterface::Create(congestion_type)),
       stats_(stats) {
   ack_frame_.largest_observed = 0;
   ack_frame_.entropy_hash = 0;
 }
 
 QuicReceivedPacketManager::~QuicReceivedPacketManager() {}
 
 void QuicReceivedPacketManager::RecordPacketReceived(
@@ skipping 77 matching lines @@
 bool QuicReceivedPacketManager::GenerateCongestionFeedback(
     QuicCongestionFeedbackFrame* feedback) {
   return receive_algorithm_->GenerateCongestionFeedback(feedback);
 }
 
 QuicPacketEntropyHash QuicReceivedPacketManager::EntropyHash(
     QuicPacketSequenceNumber sequence_number) const {
   return entropy_tracker_.EntropyHash(sequence_number);
 }
 
-void QuicReceivedPacketManager::UpdatePacketInformationReceivedByPeer(
-    const QuicAckFrame& ack_frame) {
-  // ValidateAck should fail if largest_observed ever shrinks.
-  DCHECK_LE(peer_largest_observed_packet_, ack_frame.largest_observed);
-  peer_largest_observed_packet_ = ack_frame.largest_observed;
-
-  if (ack_frame.missing_packets.empty()) {
-    least_packet_awaited_by_peer_ = peer_largest_observed_packet_ + 1;
-  } else {
-    least_packet_awaited_by_peer_ = *(ack_frame.missing_packets.begin());
-  }
-}
-
 bool QuicReceivedPacketManager::DontWaitForPacketsBefore(
     QuicPacketSequenceNumber least_unacked) {
   ack_frame_.revived_packets.erase(
       ack_frame_.revived_packets.begin(),
       ack_frame_.revived_packets.lower_bound(least_unacked));
   size_t missing_packets_count = ack_frame_.missing_packets.size();
   ack_frame_.missing_packets.erase(
       ack_frame_.missing_packets.begin(),
       ack_frame_.missing_packets.lower_bound(least_unacked));
   return missing_packets_count != ack_frame_.missing_packets.size();
@@ skipping 12 matching lines @@
       entropy_tracker_.SetCumulativeEntropyUpTo(stop_waiting.least_unacked,
                                                 stop_waiting.entropy_hash);
     }
     peer_least_packet_awaiting_ack_ = stop_waiting.least_unacked;
   }
   DCHECK(ack_frame_.missing_packets.empty() ||
          *ack_frame_.missing_packets.begin() >=
              peer_least_packet_awaiting_ack_);
 }
 
-bool QuicReceivedPacketManager::HasMissingPackets() {
-  return !ack_frame_.missing_packets.empty();
-}
-
 bool QuicReceivedPacketManager::HasNewMissingPackets() {
-  return HasMissingPackets() &&
+  return !ack_frame_.missing_packets.empty() &&
       (ack_frame_.largest_observed -
        *ack_frame_.missing_packets.rbegin()) <= kMaxPacketsAfterNewMissing;
 }
 
 }  // namespace net