Landing Recent QUIC Changes.

net/quic/quic_sent_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_sent_packet_manager.h"
 
 #include <algorithm>
 
 #include "base/logging.h"
 #include "base/stl_util.h"
@@ skipping 126 matching lines @@
   }
 }
 
 // TODO(ianswett): Combine this method with OnPacketSent once packets are always
 // sent in order and the connection tracks RetransmittableFrames for longer.
 void QuicSentPacketManager::OnSerializedPacket(
     const SerializedPacket& serialized_packet) {
   if (serialized_packet.retransmittable_frames) {
     ack_notifier_manager_.OnSerializedPacket(serialized_packet);
   }
+  unacked_packets_.AddPacket(serialized_packet);
 
-  unacked_packets_.AddPacket(serialized_packet);
+  if (debug_delegate_ != NULL) {
+    debug_delegate_->OnSerializedPacket(serialized_packet);
+  }
 }
 
 void QuicSentPacketManager::OnRetransmittedPacket(
     QuicPacketSequenceNumber old_sequence_number,
     QuicPacketSequenceNumber new_sequence_number) {
   TransmissionType transmission_type;
   PendingRetransmissionMap::iterator it =
       pending_retransmissions_.find(old_sequence_number);
   if (it != pending_retransmissions_.end()) {
     transmission_type = it->second;
@@ skipping 28 matching lines @@
   UpdatePacketInformationReceivedByPeer(ack_frame);
   // We rely on delta_time_largest_observed to compute an RTT estimate, so
   // we only update rtt when the largest observed gets acked.
   bool largest_observed_acked = MaybeUpdateRTT(ack_frame, ack_receive_time);
   DCHECK_GE(ack_frame.largest_observed, unacked_packets_.largest_observed());
   unacked_packets_.IncreaseLargestObserved(ack_frame.largest_observed);
 
   HandleAckForSentPackets(ack_frame);
   InvokeLossDetection(ack_receive_time);
   MaybeInvokeCongestionEvent(largest_observed_acked, bytes_in_flight);
+  unacked_packets_.RemoveObsoletePackets();
 
   sustained_bandwidth_recorder_.RecordEstimate(
       send_algorithm_->InRecovery(),
       send_algorithm_->InSlowStart(),
       send_algorithm_->BandwidthEstimate(),
       ack_receive_time,
       clock_->WallNow(),
       rtt_stats_.SmoothedRtt());
 
   // If we have received a truncated ack, then we need to clear out some
@@ skipping 43 matching lines @@
     network_change_visitor_->OnCongestionWindowChange(GetCongestionWindow());
   }
 }
 
 void QuicSentPacketManager::HandleAckForSentPackets(
     const QuicAckFrame& ack_frame) {
   // Go through the packets we have not received an ack for and see if this
   // incoming_ack shows they've been seen by the peer.
   QuicTime::Delta delta_largest_observed =
       ack_frame.delta_time_largest_observed;
-  QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-  while (it != unacked_packets_.end()) {
-    QuicPacketSequenceNumber sequence_number = it->first;
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
+  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
     if (sequence_number > ack_frame.largest_observed) {
       // These packets are still in flight.
       break;
     }
 
-    if (IsAwaitingPacket(ack_frame, sequence_number)) {
+    if (ContainsKey(ack_frame.missing_packets, sequence_number)) {
       // Consider it multiple nacks when there is a gap between the missing
       // packet and the largest observed, since the purpose of a nack
       // threshold is to tolerate re-ordering.  This handles both StretchAcks
       // and Forward Acks.
       // The nack count only increases when the largest observed increases.
       size_t min_nacks = ack_frame.largest_observed - sequence_number;
       // Truncated acks can nack the largest observed, so use a min of 1.
       if (min_nacks == 0) {
         min_nacks = 1;
       }
       unacked_packets_.NackPacket(sequence_number, min_nacks);
-      ++it;
       continue;
     }
     // Packet was acked, so remove it from our unacked packet list.
     DVLOG(1) << ENDPOINT << "Got an ack for packet " << sequence_number;
     // If data is associated with the most recent transmission of this
     // packet, then inform the caller.
-    if (it->second.in_flight) {
-      packets_acked_[sequence_number] = it->second;
+    if (it->in_flight) {
+      packets_acked_[sequence_number] = *it;
     }
-    it = MarkPacketHandled(it, delta_largest_observed);
+    MarkPacketHandled(sequence_number, *it, delta_largest_observed);
   }
 
   // Discard any retransmittable frames associated with revived packets.
   for (SequenceNumberSet::const_iterator revived_it =
            ack_frame.revived_packets.begin();
        revived_it != ack_frame.revived_packets.end(); ++revived_it) {
     MarkPacketRevived(*revived_it, delta_largest_observed);
   }
 }
 
 bool QuicSentPacketManager::HasRetransmittableFrames(
     QuicPacketSequenceNumber sequence_number) const {
   return unacked_packets_.HasRetransmittableFrames(sequence_number);
 }
 
 void QuicSentPacketManager::RetransmitUnackedPackets(
     RetransmissionType retransmission_type) {
-  QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-  while (it != unacked_packets_.end()) {
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
+  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
+    const RetransmittableFrames* frames = it->retransmittable_frames;
     // TODO(ianswett): Consider adding a new retransmission type which removes
     // all these old packets from unacked and retransmits them as new sequence
     // numbers with no connection to the previous ones.
     if (frames != NULL && (retransmission_type == ALL_PACKETS ||
                            frames->encryption_level() == ENCRYPTION_INITIAL)) {
-      MarkForRetransmission(it->first, ALL_UNACKED_RETRANSMISSION);
+      MarkForRetransmission(sequence_number, ALL_UNACKED_RETRANSMISSION);
     }
-    ++it;
   }
 }
 
 void QuicSentPacketManager::NeuterUnencryptedPackets() {
-  QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-  while (it != unacked_packets_.end()) {
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
-    QuicPacketSequenceNumber sequence_number = it->first;
-    ++it;
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
+  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
+    const RetransmittableFrames* frames = it->retransmittable_frames;
     if (frames != NULL && frames->encryption_level() == ENCRYPTION_NONE) {
       // Once you're forward secure, no unencrypted packets will be sent, crypto
       // or otherwise. Unencrypted packets are neutered and abandoned, to ensure
       // they are not retransmitted or considered lost from a congestion control
       // perspective.
       pending_retransmissions_.erase(sequence_number);
       unacked_packets_.RemoveFromInFlight(sequence_number);
-      // RemoveRetransmittibility is safe because only the newest sequence
-      // number can have frames.
       unacked_packets_.RemoveRetransmittability(sequence_number);
     }
   }
 }
 
 void QuicSentPacketManager::MarkForRetransmission(
     QuicPacketSequenceNumber sequence_number,
     TransmissionType transmission_type) {
   const TransmissionInfo& transmission_info =
       unacked_packets_.GetTransmissionInfo(sequence_number);
   LOG_IF(DFATAL, transmission_info.retransmittable_frames == NULL);
   if (transmission_type != TLP_RETRANSMISSION) {
     unacked_packets_.RemoveFromInFlight(sequence_number);
   }
   // TODO(ianswett): Currently the RTO can fire while there are pending NACK
   // retransmissions for the same data, which is not ideal.
   if (ContainsKey(pending_retransmissions_, sequence_number)) {
     return;
   }
 
   pending_retransmissions_[sequence_number] = transmission_type;
 }
 
 void QuicSentPacketManager::RecordSpuriousRetransmissions(
-    const SequenceNumberSet& all_transmissions,
+    const SequenceNumberList& all_transmissions,
     QuicPacketSequenceNumber acked_sequence_number) {
   if (acked_sequence_number < first_rto_transmission_) {
     // Cancel all pending RTO transmissions and restore their in flight status.
     // Replace SRTT with latest_rtt and increase the variance to prevent
     // a spurious RTO from happening again.
     rtt_stats_.ExpireSmoothedMetrics();
     for (PendingRetransmissionMap::const_iterator it =
              pending_retransmissions_.begin();
          it != pending_retransmissions_.end(); ++it) {
       DCHECK_EQ(it->second, RTO_RETRANSMISSION);
       unacked_packets_.RestoreInFlight(it->first);
     }
     pending_retransmissions_.clear();
     send_algorithm_->RevertRetransmissionTimeout();
     first_rto_transmission_ = 0;
     ++stats_->spurious_rto_count;
   }
-  for (SequenceNumberSet::const_iterator
-           it = all_transmissions.upper_bound(acked_sequence_number),
-           end = all_transmissions.end();
-       it != end;
-       ++it) {
+  for (SequenceNumberList::const_reverse_iterator it =
+           all_transmissions.rbegin();
+       it != all_transmissions.rend() && *it > acked_sequence_number; ++it) {
     const TransmissionInfo& retransmit_info =
         unacked_packets_.GetTransmissionInfo(*it);
 
     stats_->bytes_spuriously_retransmitted += retransmit_info.bytes_sent;
     ++stats_->packets_spuriously_retransmitted;
     if (debug_delegate_ != NULL) {
       debug_delegate_->OnSpuriousPacketRetransmition(
           retransmit_info.transmission_type,
           retransmit_info.bytes_sent);
     }
@@ skipping 37 matching lines @@
 void QuicSentPacketManager::MarkPacketRevived(
     QuicPacketSequenceNumber sequence_number,
     QuicTime::Delta delta_largest_observed) {
   if (!unacked_packets_.IsUnacked(sequence_number)) {
     return;
   }
 
   const TransmissionInfo& transmission_info =
       unacked_packets_.GetTransmissionInfo(sequence_number);
   QuicPacketSequenceNumber newest_transmission =
-      *transmission_info.all_transmissions->rbegin();
+      transmission_info.all_transmissions == NULL ?
+          sequence_number : *transmission_info.all_transmissions->rbegin();
   // This packet has been revived at the receiver. If we were going to
   // retransmit it, do not retransmit it anymore.
   pending_retransmissions_.erase(newest_transmission);
 
   // The AckNotifierManager needs to be notified for revived packets,
   // since it indicates the packet arrived from the appliction's perspective.
   if (transmission_info.retransmittable_frames) {
     ack_notifier_manager_.OnPacketAcked(
         newest_transmission, delta_largest_observed);
   }
 
   unacked_packets_.RemoveRetransmittability(sequence_number);
 }
 
-QuicUnackedPacketMap::const_iterator QuicSentPacketManager::MarkPacketHandled(
-    QuicUnackedPacketMap::const_iterator it,
+void QuicSentPacketManager::MarkPacketHandled(
+    QuicPacketSequenceNumber sequence_number,
+    const TransmissionInfo& info,
     QuicTime::Delta delta_largest_observed) {
-  LOG_IF(DFATAL, it == unacked_packets_.end())
-      << "MarkPacketHandled must be passed a valid iterator entry.";
-  const QuicPacketSequenceNumber sequence_number = it->first;
-  const TransmissionInfo& transmission_info = it->second;
-
   QuicPacketSequenceNumber newest_transmission =
-      *transmission_info.all_transmissions->rbegin();
+      info.all_transmissions == NULL ?
+          sequence_number : *info.all_transmissions->rbegin();
   // Remove the most recent packet, if it is pending retransmission.
   pending_retransmissions_.erase(newest_transmission);
 
-  // Notify observers about the ACKed packet.
-  {
-    // The AckNotifierManager needs to be notified about the most recent
-    // transmission, since that's the one only one it tracks.
-    ack_notifier_manager_.OnPacketAcked(newest_transmission,
-                                        delta_largest_observed);
-    if (newest_transmission != sequence_number) {
-      RecordSpuriousRetransmissions(*transmission_info.all_transmissions,
-                                    sequence_number);
+  // The AckNotifierManager needs to be notified about the most recent
+  // transmission, since that's the one only one it tracks.
+  ack_notifier_manager_.OnPacketAcked(newest_transmission,
+                                      delta_largest_observed);
+  if (newest_transmission != sequence_number) {
+    RecordSpuriousRetransmissions(*info.all_transmissions, sequence_number);
+    // Remove the most recent packet from flight if it's a crypto handshake
+    // packet, since they won't be acked now that one has been processed.
+    // Other crypto handshake packets won't be in flight, only the newest
+    // transmission of a crypto packet is in flight at once.
+    // TODO(ianswett): Instead of handling all crypto packets special,
+    // only handle NULL encrypted packets in a special way.
+    if (HasCryptoHandshake(
+        unacked_packets_.GetTransmissionInfo(newest_transmission))) {
+      unacked_packets_.RemoveFromInFlight(newest_transmission);
     }
   }
 
-  // Two cases for MarkPacketHandled:
-  // 1) Handle the most recent or a crypto packet, so remove all transmissions.
-  // 2) Handle old transmission, keep all other pending transmissions,
-  //    but disassociate them from one another.
-
-  // If it's a crypto handshake packet, discard it and all retransmissions,
-  // since they won't be acked now that one has been processed.
-  // TODO(ianswett): Instead of handling all crypto packets in a special way,
-  // only handle NULL encrypted packets in a special way.
-  if (HasCryptoHandshake(
-          unacked_packets_.GetTransmissionInfo(newest_transmission))) {
-    unacked_packets_.RemoveFromInFlight(newest_transmission);
-  }
   unacked_packets_.RemoveFromInFlight(sequence_number);
   unacked_packets_.RemoveRetransmittability(sequence_number);
-
-  QuicUnackedPacketMap::const_iterator next_unacked = unacked_packets_.begin();
-  while (next_unacked != unacked_packets_.end() &&
-         next_unacked->first <= sequence_number) {
-    ++next_unacked;
-  }
-  return next_unacked;
 }
 
 bool QuicSentPacketManager::IsUnacked(
     QuicPacketSequenceNumber sequence_number) const {
   return unacked_packets_.IsUnacked(sequence_number);
 }
 
 bool QuicSentPacketManager::HasUnackedPackets() const {
   return unacked_packets_.HasUnackedPackets();
 }
 
 QuicPacketSequenceNumber
 QuicSentPacketManager::GetLeastUnackedSentPacket() const {
-  return unacked_packets_.GetLeastUnackedSentPacket();
+  return unacked_packets_.GetLeastUnacked();
 }
 
 bool QuicSentPacketManager::OnPacketSent(
     QuicPacketSequenceNumber sequence_number,
     QuicTime sent_time,
     QuicByteCount bytes,
     TransmissionType transmission_type,
     HasRetransmittableData has_retransmittable_data) {
   DCHECK_LT(0u, sequence_number);
   DCHECK(unacked_packets_.IsUnacked(sequence_number));
@@ skipping 13 matching lines @@
   // Only track packets as in flight that the send algorithm wants us to track.
   const bool in_flight =
       send_algorithm_->OnPacketSent(sent_time,
                                     unacked_packets_.bytes_in_flight(),
                                     sequence_number,
                                     bytes,
                                     has_retransmittable_data);
   unacked_packets_.SetSent(sequence_number, sent_time, bytes, in_flight);
 
   if (debug_delegate_ != NULL) {
-    debug_delegate_->OnSentPacket(sequence_number, sent_time, bytes);
+    debug_delegate_->OnSentPacket(
+        sequence_number, sent_time, bytes, transmission_type);
   }
 
   // Reset the retransmission timer anytime a pending packet is sent.
   return in_flight;
 }
 
 void QuicSentPacketManager::OnRetransmissionTimeout() {
   DCHECK(unacked_packets_.HasInFlightPackets());
   DCHECK_EQ(0u, pending_timer_transmission_count_);
   // Handshake retransmission, timer based loss detection, TLP, and RTO are
@@ skipping 29 matching lines @@
   }
 }
 
 void QuicSentPacketManager::RetransmitCryptoPackets() {
   DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode());
   // TODO(ianswett): Typical TCP implementations only retransmit 5 times.
   consecutive_crypto_retransmission_count_ =
       min(kMaxHandshakeRetransmissionBackoffs,
           consecutive_crypto_retransmission_count_ + 1);
   bool packet_retransmitted = false;
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-       it != unacked_packets_.end(); ++it) {
-    QuicPacketSequenceNumber sequence_number = it->first;
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
     // Only retransmit frames which are in flight, and therefore have been sent.
-    if (!it->second.in_flight || frames == NULL ||
-        frames->HasCryptoHandshake() != IS_HANDSHAKE) {
+    if (!it->in_flight || it->retransmittable_frames == NULL ||
+        it->retransmittable_frames->HasCryptoHandshake() != IS_HANDSHAKE) {
       continue;
     }
     packet_retransmitted = true;
     MarkForRetransmission(sequence_number, HANDSHAKE_RETRANSMISSION);
     ++pending_timer_transmission_count_;
   }
   DCHECK(packet_retransmitted) << "No crypto packets found to retransmit.";
 }
 
 bool QuicSentPacketManager::MaybeRetransmitTailLossProbe() {
   if (pending_timer_transmission_count_ == 0) {
     return false;
   }
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-       it != unacked_packets_.end(); ++it) {
-    QuicPacketSequenceNumber sequence_number = it->first;
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
     // Only retransmit frames which are in flight, and therefore have been sent.
-    if (!it->second.in_flight || frames == NULL) {
+    if (!it->in_flight || it->retransmittable_frames == NULL) {
       continue;
     }
     if (!handshake_confirmed_) {
-      DCHECK_NE(IS_HANDSHAKE, frames->HasCryptoHandshake());
+      DCHECK_NE(IS_HANDSHAKE, it->retransmittable_frames->HasCryptoHandshake());
     }
     MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
     return true;
   }
   DLOG(FATAL)
     << "No retransmittable packets, so RetransmitOldestPacket failed.";
   return false;
 }
 
 void QuicSentPacketManager::RetransmitAllPackets() {
   DVLOG(1) << "RetransmitAllPackets() called with "
-           << unacked_packets_.GetNumUnackedPackets() << " unacked packets.";
+           << unacked_packets_.GetNumUnackedPacketsDebugOnly()
+           << " unacked packets.";
   // Request retransmission of all retransmittable packets when the RTO
   // fires, and let the congestion manager decide how many to send
   // immediately and the remaining packets will be queued.
   // Abandon any non-retransmittable packets that are sufficiently old.
   bool packets_retransmitted = false;
-  QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
-  while (it != unacked_packets_.end()) {
-    const RetransmittableFrames* frames = it->second.retransmittable_frames;
-    QuicPacketSequenceNumber sequence_number = it->first;
-    ++it;
-    if (frames != NULL) {
+  QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked();
+  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it, ++sequence_number) {
+    if (it->retransmittable_frames != NULL) {
       packets_retransmitted = true;
       MarkForRetransmission(sequence_number, RTO_RETRANSMISSION);
     } else {
       unacked_packets_.RemoveFromInFlight(sequence_number);
     }
   }
 
   send_algorithm_->OnRetransmissionTimeout(packets_retransmitted);
   if (packets_retransmitted) {
     if (consecutive_rto_count_ == 0) {
@@ skipping 226 matching lines @@
 
   // Set up a pacing sender with a 5 millisecond alarm granularity.
   using_pacing_ = true;
   send_algorithm_.reset(
       new PacingSender(send_algorithm_.release(),
                        QuicTime::Delta::FromMilliseconds(5),
                        kInitialUnpacedBurst));
 }
 
 }  // namespace net