QUIC Cleanup to remove pending_packets from QuicSentPacketManager and

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 "base/logging.h"
 #include "base/stl_util.h"
 #include "net/quic/congestion_control/pacing_sender.h"
 #include "net/quic/quic_ack_notifier_manager.h"
@@ skipping 127 matching lines @@
 void QuicSentPacketManager::OnRetransmittedPacket(
     QuicPacketSequenceNumber old_sequence_number,
     QuicPacketSequenceNumber new_sequence_number) {
   DCHECK(ContainsKey(unacked_packets_, old_sequence_number));
   DCHECK(ContainsKey(pending_retransmissions_, old_sequence_number));
   DCHECK(unacked_packets_.empty() ||
          unacked_packets_.rbegin()->first < new_sequence_number);
 
   pending_retransmissions_.erase(old_sequence_number);
   // TODO(ianswett): Discard and lose the packet lazily instead of immediately.
-
   UnackedPacketMap::iterator unacked_it =
       unacked_packets_.find(old_sequence_number);
-  RetransmittableFrames* frames = unacked_it->second.retransmittable_frames;
+  TransmissionInfo* transmission_info = &unacked_it->second;
+  RetransmittableFrames* frames = transmission_info->retransmittable_frames;
   DCHECK(frames);
 
   // A notifier may be waiting to hear about ACKs for the original sequence
   // number. Inform them that the sequence number has changed.
   ack_notifier_manager_.UpdateSequenceNumber(old_sequence_number,
                                              new_sequence_number);
 
   // We keep the old packet in the unacked packet list until it, or one of
   // the retransmissions of it are acked.
-  unacked_it->second.retransmittable_frames = NULL;
+  transmission_info->retransmittable_frames = NULL;
   unacked_packets_[new_sequence_number] =
-      TransmissionInfo(frames, GetSequenceNumberLength(old_sequence_number));
+      TransmissionInfo(frames, transmission_info->sequence_number_length);
 
   // Keep track of all sequence numbers that this packet
   // has been transmitted as.
   SequenceNumberSet* previous_transmissions =
-      unacked_it->second.previous_transmissions;
+      transmission_info->previous_transmissions;
   if (previous_transmissions == NULL) {
     // This is the first retransmission of this packet, so create a new entry.
     previous_transmissions = new SequenceNumberSet;
-    unacked_it->second.previous_transmissions = previous_transmissions;
+    transmission_info->previous_transmissions = previous_transmissions;
     previous_transmissions->insert(old_sequence_number);
   }
   previous_transmissions->insert(new_sequence_number);
   unacked_packets_[new_sequence_number].previous_transmissions =
       previous_transmissions;
 
   DCHECK(HasRetransmittableFrames(new_sequence_number));
 }
 
 bool QuicSentPacketManager::OnIncomingAck(
@@ skipping 86 matching lines @@
     if (sequence_number == newest_transmission) {
       break;
     }
 
     DCHECK(it->second.retransmittable_frames == NULL);
     previous_transmissions->erase(sequence_number);
     if (previous_transmissions->size() == 1) {
       unacked_packets_[newest_transmission].previous_transmissions = NULL;
       delete previous_transmissions;
     }
-    DCHECK(!ContainsKey(pending_packets_, it->first));
+    DCHECK(!it->second.pending);
     unacked_packets_.erase(it++);
     --num_to_clear;
   }
 }
 
 bool QuicSentPacketManager::HasRetransmittableFrames(
     QuicPacketSequenceNumber sequence_number) const {
   UnackedPacketMap::const_iterator it = unacked_packets_.find(sequence_number);
   if (it == unacked_packets_.end()) {
     return false;
   }
   const TransmissionInfo* transmission_info = &it->second;
   DCHECK(transmission_info);
 
   return transmission_info->retransmittable_frames != NULL;
 }
 
 void QuicSentPacketManager::RetransmitUnackedPackets(
     RetransmissionType retransmission_type) {
   if (unacked_packets_.empty()) {
     return;
   }
 
-  for (UnackedPacketMap::const_iterator unacked_it = unacked_packets_.begin();
+  for (UnackedPacketMap::iterator unacked_it = unacked_packets_.begin();
        unacked_it != unacked_packets_.end(); ++unacked_it) {
     const RetransmittableFrames* frames =
         unacked_it->second.retransmittable_frames;
     if (frames == NULL) {
       continue;
     }
     if (retransmission_type == ALL_PACKETS ||
         frames->encryption_level() == ENCRYPTION_INITIAL) {
       // TODO(satyamshekhar): Think about congestion control here.
       // Specifically, about the retransmission count of packets being sent
       // proactively to achieve 0 (minimal) RTT.
       if (unacked_it->second.retransmittable_frames) {
-        OnPacketAbandoned(unacked_it->first);
+        OnPacketAbandoned(unacked_it);
         MarkForRetransmission(unacked_it->first, NACK_RETRANSMISSION);
       } else {
         DiscardUnackedPacket(unacked_it->first);
       }
     }
   }
 }
 
 void QuicSentPacketManager::MarkForRetransmission(
     QuicPacketSequenceNumber sequence_number,
@@ skipping 12 matching lines @@
 bool QuicSentPacketManager::HasPendingRetransmissions() const {
   return !pending_retransmissions_.empty();
 }
 
 QuicSentPacketManager::PendingRetransmission
     QuicSentPacketManager::NextPendingRetransmission() {
   DCHECK(!pending_retransmissions_.empty());
   QuicPacketSequenceNumber sequence_number =
       pending_retransmissions_.begin()->first;
   DCHECK(ContainsKey(unacked_packets_, sequence_number));
-  const RetransmittableFrames* retransmittable_frames =
-      unacked_packets_[sequence_number].retransmittable_frames;
-  DCHECK(retransmittable_frames);
+  UnackedPacketMap::iterator unacked_it =
+      unacked_packets_.find(sequence_number);
+  CHECK(unacked_it != unacked_packets_.end());
+  const TransmissionInfo& transmission_info = unacked_it->second;
+  DCHECK(transmission_info.retransmittable_frames);
 
   return PendingRetransmission(sequence_number,
                                pending_retransmissions_.begin()->second,
-                               *retransmittable_frames,
-                               GetSequenceNumberLength(sequence_number));
+                               *transmission_info.retransmittable_frames,
+                               transmission_info.sequence_number_length);
 }
 
 bool QuicSentPacketManager::IsPreviousTransmission(
     QuicPacketSequenceNumber sequence_number) const {
   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 
-  UnackedPacketMap::const_iterator it = unacked_packets_.find(sequence_number);
-  if (it->second.previous_transmissions == NULL) {
+  UnackedPacketMap::const_iterator unacked_it =
+      unacked_packets_.find(sequence_number);
+  if (unacked_it == unacked_packets_.end()) {
+    return false;
+  }
+  const TransmissionInfo* transmission_info = &unacked_it->second;
+  if (transmission_info->previous_transmissions == NULL) {
     return false;
   }
 
-  SequenceNumberSet* previous_transmissions = it->second.previous_transmissions;
+  SequenceNumberSet* previous_transmissions =
+      transmission_info->previous_transmissions;
   DCHECK(!previous_transmissions->empty());
   return *previous_transmissions->rbegin() != sequence_number;
 }
 
 // static
 bool QuicSentPacketManager::HasCryptoHandshake(
     const TransmissionInfo& transmission_info) {
   if (transmission_info.retransmittable_frames == NULL) {
     return false;
   }
   return transmission_info.retransmittable_frames->HasCryptoHandshake() ==
       IS_HANDSHAKE;
 }
 
 QuicSentPacketManager::UnackedPacketMap::iterator
 QuicSentPacketManager::MarkPacketHandled(
     QuicPacketSequenceNumber sequence_number, ReceivedByPeer received_by_peer) {
   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 
   // If this packet is pending, remove it and inform the send algorithm.
-  if (pending_packets_.erase(sequence_number)) {
+  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
+  if (it->second.pending) {
     size_t bytes_sent = packet_history_map_[sequence_number]->bytes_sent();
     if (received_by_peer == RECEIVED_BY_PEER) {
       send_algorithm_->OnPacketAcked(sequence_number, bytes_sent, rtt_sample_);
     } else {
       // It's been abandoned.
       send_algorithm_->OnPacketAbandoned(sequence_number, bytes_sent);
     }
+    it->second.pending = false;
   }
 
   // If this packet has never been retransmitted, then simply drop it.
-  UnackedPacketMap::iterator previous_it =
-      unacked_packets_.find(sequence_number);
-  if (previous_it->second.previous_transmissions == NULL) {
-    ++previous_it;
+  if (it->second.previous_transmissions == NULL) {
+    ++it;
     DiscardPacket(sequence_number);
-    return previous_it;
+    return it;
   }
 
-  SequenceNumberSet* previous_transmissions =
-      previous_it->second.previous_transmissions;
+  SequenceNumberSet* previous_transmissions = it->second.previous_transmissions;
   DCHECK(!previous_transmissions->empty());
   SequenceNumberSet::reverse_iterator previous_transmissions_it =
       previous_transmissions->rbegin();
   QuicPacketSequenceNumber newest_transmission = *previous_transmissions_it;
   if (newest_transmission == sequence_number) {
     DiscardPacket(newest_transmission);
   } else {
-    UnackedPacketMap::iterator newest_it =
+    UnackedPacketMap::iterator unacked_it =
         unacked_packets_.find(newest_transmission);
-    if (HasCryptoHandshake(newest_it->second)) {
+    TransmissionInfo* transmission_info = &unacked_it->second;
+    if (HasCryptoHandshake(*transmission_info)) {
       --pending_crypto_packet_count_;
     }
     // If we have received an ack for a previous transmission of a packet,
     // we want to keep the "new" transmission of the packet unacked,
     // but prevent the data from being retransmitted.
-    delete newest_it->second.retransmittable_frames;
-    newest_it->second.retransmittable_frames = NULL;
-    newest_it->second.previous_transmissions = NULL;
+    delete transmission_info->retransmittable_frames;
+    transmission_info->retransmittable_frames = NULL;
+    transmission_info->previous_transmissions = NULL;
   }
 
   // Clear out information all previous transmissions.
   ++previous_transmissions_it;
   while (previous_transmissions_it != previous_transmissions->rend()) {
     QuicPacketSequenceNumber previous_transmission = *previous_transmissions_it;
     ++previous_transmissions_it;
     // If the packet was TLP retransmitted, the old copy was not yet considered
     // lost or abandoned, so do that now.
-    if (ContainsKey(pending_packets_, previous_transmission)) {
+    if (unacked_packets_[previous_transmission].pending) {
       send_algorithm_->OnPacketLost(previous_transmission, clock_->Now());
-      OnPacketAbandoned(previous_transmission);
+      OnPacketAbandoned(unacked_packets_.find(previous_transmission));
     }
     DiscardPacket(previous_transmission);
   }
 
   delete previous_transmissions;
 
   if (ContainsKey(pending_retransmissions_, newest_transmission)) {
     pending_retransmissions_.erase(newest_transmission);
-    if (!ContainsKey(pending_packets_, newest_transmission))  {
+    if (!unacked_packets_[newest_transmission].pending) {
       // If the newest transmission has already been marked for retransmission
       // and has already been abandoned, then we should remove it from
       // unacked_packets_, as well as cancel the retransmission.
       DCHECK(ContainsKey(unacked_packets_, newest_transmission));
       DCHECK(!unacked_packets_[newest_transmission].previous_transmissions);
       unacked_packets_.erase(newest_transmission);
     }
   }
 
   UnackedPacketMap::iterator next_unacked = unacked_packets_.begin();
   while (next_unacked != unacked_packets_.end() &&
          next_unacked->first < sequence_number) {
     ++next_unacked;
   }
   return next_unacked;
 }
 
 void QuicSentPacketManager::DiscardPacket(
     QuicPacketSequenceNumber sequence_number) {
   UnackedPacketMap::iterator unacked_it =
       unacked_packets_.find(sequence_number);
   DCHECK(unacked_it != unacked_packets_.end());
   // Ensure the packet is no longer pending when it's discarded.
-  DCHECK(!ContainsKey(pending_packets_, sequence_number));
+  DCHECK(!unacked_it->second.pending);
 
   RetransmittableFrames* retransmittable_frames =
       unacked_it->second.retransmittable_frames;
   if (HasCryptoHandshake(unacked_it->second)) {
     --pending_crypto_packet_count_;
   }
 
   // Delete the retransmittable frames.
   delete retransmittable_frames;
   unacked_packets_.erase(unacked_it);
   pending_retransmissions_.erase(sequence_number);
   return;
 }
 
 bool QuicSentPacketManager::IsUnacked(
     QuicPacketSequenceNumber sequence_number) const {
   return ContainsKey(unacked_packets_, sequence_number);
 }
 
-QuicSequenceNumberLength QuicSentPacketManager::GetSequenceNumberLength(
-    QuicPacketSequenceNumber sequence_number) const {
-  DCHECK(ContainsKey(unacked_packets_, sequence_number));
-
-  return unacked_packets_.find(sequence_number)->second.sequence_number_length;
-}
-
 bool QuicSentPacketManager::HasUnackedPackets() const {
   return !unacked_packets_.empty();
 }
 
+bool QuicSentPacketManager::HasPendingPackets() const {
+  for (UnackedPacketMap::const_reverse_iterator it =
+           unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
+    if (it->second.pending) {
+      return true;
+    }
+  }
+  return false;
+}
+
 size_t QuicSentPacketManager::GetNumRetransmittablePackets() const {
   size_t num_unacked_packets = 0;
   for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
        it != unacked_packets_.end(); ++it) {
     QuicPacketSequenceNumber sequence_number = it->first;
     if (HasRetransmittableFrames(sequence_number)) {
       ++num_unacked_packets;
     }
   }
   return num_unacked_packets;
@@ skipping 19 matching lines @@
   return unacked_packets;
 }
 
 bool QuicSentPacketManager::OnPacketSent(
     QuicPacketSequenceNumber sequence_number,
     QuicTime sent_time,
     QuicByteCount bytes,
     TransmissionType transmission_type,
     HasRetransmittableData has_retransmittable_data) {
   DCHECK_LT(0u, sequence_number);
-  DCHECK(!ContainsKey(pending_packets_, sequence_number));
   DCHECK(ContainsKey(unacked_packets_, sequence_number));
+  DCHECK(!unacked_packets_[sequence_number].pending);
   if (has_retransmittable_data == HAS_RETRANSMITTABLE_DATA) {
     DCHECK(unacked_packets_[sequence_number].retransmittable_frames);
   }
+  UnackedPacketMap::iterator it = unacked_packets_.find(sequence_number);
 
   // Only track packets the send algorithm wants us to track.
   if (!send_algorithm_->OnPacketSent(sent_time, sequence_number, bytes,
                                      transmission_type,
                                      has_retransmittable_data)) {
-    DCHECK(unacked_packets_[sequence_number].retransmittable_frames == NULL);
-    unacked_packets_.erase(sequence_number);
+    DCHECK(it->second.retransmittable_frames == NULL);
+    unacked_packets_.erase(it);
     // Do not reset the retransmission timer, since the packet isn't tracked.
     return false;
   }
 
-  // Set the retransmission timer for the first pending packet.
-  const bool set_retransmission_timer = pending_packets_.empty();
-  unacked_packets_[sequence_number].sent_time = sent_time;
+  const bool set_retransmission_timer = !HasPendingPackets();
+  it->second.sent_time = sent_time;
+  it->second.pending = true;
   packet_history_map_[sequence_number] =
       new SendAlgorithmInterface::SentPacket(bytes, sent_time);
-  pending_packets_.insert(sequence_number);
   CleanupPacketHistory();
 
   // Reset the retransmission timer anytime a packet is sent in tail loss probe
   // mode or before the crypto handshake has completed.
-  return GetRetransmissionMode() != RTO_MODE || set_retransmission_timer;
+  return set_retransmission_timer || GetRetransmissionMode() != RTO_MODE;
 }
 
 void QuicSentPacketManager::OnRetransmissionTimeout() {
-  DCHECK(!pending_packets_.empty());
+  DCHECK(HasPendingPackets());
   // Handshake retransmission, TLP, and RTO are implemented with a single alarm.
   // The handshake alarm is set when the handshake has not completed, and the
   // TLP and RTO alarms are set after that.
   // The TLP alarm is always set to run for under an RTO.
   switch (GetRetransmissionMode()) {
     case HANDSHAKE_MODE:
       RetransmitCryptoPackets();
       return;
     case TLP_MODE:
       // If no tail loss probe can be sent, because there are no retransmittable
       // packets, execute a conventional RTO to abandon old packets.
       RetransmitOldestPacket();
       return;
     case RTO_MODE:
       RetransmitAllPackets();
       return;
   }
 }
 
 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;
-  for (SequenceNumberSet::iterator it = pending_packets_.begin();
-       it != pending_packets_.end(); ) {
-    QuicPacketSequenceNumber sequence_number = *it;
+  for (UnackedPacketMap::iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it) {
+    QuicPacketSequenceNumber sequence_number = it->first;
     DCHECK(ContainsKey(packet_history_map_, sequence_number));
-    DCHECK(ContainsKey(unacked_packets_, sequence_number));
-    const RetransmittableFrames* frames =
-        unacked_packets_[sequence_number].retransmittable_frames;
+    const RetransmittableFrames* frames = it->second.retransmittable_frames;
     if (frames == NULL || frames->HasCryptoHandshake() != IS_HANDSHAKE) {
-      ++it;
       continue;
     }
     packet_retransmitted = true;
     MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
     // Abandon all the crypto retransmissions now so they're not lost later.
-    send_algorithm_->OnPacketAbandoned(
-        sequence_number, packet_history_map_[sequence_number]->bytes_sent());
-    pending_packets_.erase(it++);
+    OnPacketAbandoned(it);
   }
   DCHECK(packet_retransmitted) << "No crypto packets found to retransmit.";
 }
 
 void QuicSentPacketManager::RetransmitOldestPacket() {
   DCHECK_EQ(TLP_MODE, GetRetransmissionMode());
   ++consecutive_tlp_count_;
-  for (SequenceNumberSet::const_iterator it = pending_packets_.begin();
-       it != pending_packets_.end(); ++it) {
-    QuicPacketSequenceNumber sequence_number = *it;
-    DCHECK(ContainsKey(unacked_packets_, sequence_number));
-    const RetransmittableFrames* frames =
-        unacked_packets_[sequence_number].retransmittable_frames;
+  for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
+       it != unacked_packets_.end(); ++it) {
+    QuicPacketSequenceNumber sequence_number = it->first;
+    const RetransmittableFrames* frames = it->second.retransmittable_frames;
     if (frames == NULL) {
       continue;
     }
     DCHECK_NE(IS_HANDSHAKE, frames->HasCryptoHandshake());
     MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
     return;
   }
   DLOG(FATAL)
     << "No retransmittable packets, so RetransmitOldestPacket failed.";
 }
 
 void QuicSentPacketManager::RetransmitAllPackets() {
   // Abandon all retransmittable packets and packets older than the
   // retransmission delay.
 
   DVLOG(1) << "OnRetransmissionTimeout() fired with "
            << unacked_packets_.size() << " 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;
-  for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
+  for (UnackedPacketMap::iterator it = unacked_packets_.begin();
        it != unacked_packets_.end(); ++it) {
+    it->second.pending = false;
     if (it->second.retransmittable_frames != NULL) {
       packets_retransmitted = true;
       MarkForRetransmission(it->first, RTO_RETRANSMISSION);
     }
   }
 
-  pending_packets_.clear();
   send_algorithm_->OnRetransmissionTimeout(packets_retransmitted);
   if (packets_retransmitted) {
     ++consecutive_rto_count_;
   }
 }
 
 QuicSentPacketManager::RetransmissionTimeoutMode
     QuicSentPacketManager::GetRetransmissionMode() const {
-  DCHECK(!pending_packets_.empty());
+  DCHECK(HasPendingPackets());
   if (pending_crypto_packet_count_ > 0) {
     return HANDSHAKE_MODE;
   }
   if (consecutive_tlp_count_ < max_tail_loss_probes_) {
     // Ensure there are retransmittable frames.
-    for (SequenceNumberSet::const_iterator it = pending_packets_.begin();
-         it != pending_packets_.end(); ++it) {
-      if (HasRetransmittableFrames(*it)) {
+    for (UnackedPacketMap::const_reverse_iterator it =
+             unacked_packets_.rbegin(); it != unacked_packets_.rend(); ++it) {
+      if (it->second.pending && it->second.retransmittable_frames) {
         return TLP_MODE;
       }
     }
   }
   return RTO_MODE;
 }
 
-void QuicSentPacketManager::OnPacketAbandoned(
-    QuicPacketSequenceNumber sequence_number) {
-  SequenceNumberSet::iterator it = pending_packets_.find(sequence_number);
-  if (it != pending_packets_.end()) {
-    DCHECK(ContainsKey(packet_history_map_, sequence_number));
+void QuicSentPacketManager::OnPacketAbandoned(UnackedPacketMap::iterator it) {
+  DCHECK(it != unacked_packets_.end());
+  QuicPacketSequenceNumber sequence_number = it->first;
+  DCHECK(ContainsKey(packet_history_map_, sequence_number));
+  if (it->second.pending) {
     send_algorithm_->OnPacketAbandoned(
         sequence_number, packet_history_map_[sequence_number]->bytes_sent());
-    pending_packets_.erase(it);
+    it->second.pending = false;
   }
 }
 
 void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame(
     const QuicCongestionFeedbackFrame& frame,
     const QuicTime& feedback_receive_time) {
   send_algorithm_->OnIncomingQuicCongestionFeedbackFrame(
       frame, feedback_receive_time, packet_history_map_);
 }
 
 void QuicSentPacketManager::MaybeRetransmitOnAckFrame(
     const ReceivedPacketInfo& received_info,
     const QuicTime& ack_receive_time) {
   // Go through all pending packets up to the largest observed and see if any
   // need to be retransmitted or lost.
-  SequenceNumberSet::iterator it = pending_packets_.begin();
-  SequenceNumberSet::iterator it_upper =
-      pending_packets_.upper_bound(received_info.largest_observed);
-
   size_t num_retransmitted = 0;
-  SequenceNumberSet lost_packets;
-  while (it != it_upper) {
-    QuicPacketSequenceNumber sequence_number = *it;
+  UnackedPacketMap::iterator it = unacked_packets_.begin();
+  while (it != unacked_packets_.end() &&
+         it->first <= received_info.largest_observed) {
+    if (!it->second.pending) {
+      ++it;
+      continue;
+    }
+    QuicPacketSequenceNumber sequence_number = it->first;
     DVLOG(1) << "still missing packet " << sequence_number;
     // Acks must be handled previously, so ensure it's missing and not acked.
     DCHECK(IsAwaitingPacket(received_info, sequence_number));
     DCHECK(ContainsKey(packet_history_map_, sequence_number));
+    const TransmissionInfo& transmission_info = it->second;
     const SendAlgorithmInterface::SentPacket* sent_packet =
         packet_history_map_[sequence_number];
-    const TransmissionInfo& transmission_info =
-        unacked_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.
     // TODO(ianswett): This relies heavily on sequential reception of packets,
     // and makes an assumption that the congestion control uses TCP style nacks.
     size_t min_nacks = received_info.largest_observed - sequence_number;
     packet_history_map_[sequence_number]->Nack(min_nacks);
 
     size_t num_nacks_needed = kNumberOfNacksBeforeRetransmission;
     // Check for early retransmit(RFC5827) when the last packet gets acked and
     // the there are fewer than 4 pending packets.
-    // TODO(ianswett): Consider setting a retransmission timer instead of
-    // losing the packet and retransmitting immediately.  Also consider only
-    // invoking OnPacketLost and OnPacketAbandoned when they're actually
-    // retransmitted in case they arrive while queued.
-    if (pending_packets_.size() <= kNumberOfNacksBeforeRetransmission &&
-        transmission_info.retransmittable_frames &&
+    // TODO(ianswett): Set a retransmission timer instead of losing the packet
+    // and retransmitting immediately.  Also consider only invoking OnPacketLost
+    // and OnPacketAbandoned when they're actually retransmitted in case they
+    // arrive while queued for retransmission.
+    if (transmission_info.retransmittable_frames &&
         packet_history_map_.rbegin()->first == received_info.largest_observed) {
       num_nacks_needed = received_info.largest_observed - sequence_number;
     }
 
     if (sent_packet->nack_count() < num_nacks_needed) {
       ++it;
       continue;
     }
 
     // If the number of retransmissions has maxed out, don't lose or retransmit
     // any more packets.
     if (num_retransmitted >= kMaxRetransmissionsPerAck) {
       ++it;
       continue;
     }
 
-    lost_packets.insert(sequence_number);
+    // TODO(ianswett): OnPacketLost is also called from TCPCubicSender when
+    // an FEC packet is lost, but FEC loss information should be shared among
+    // congestion managers.  Additionally, if it's expected the FEC packet may
+    // repair the loss, it should be recorded as a loss to the congestion
+    // manager, but not retransmitted until it's known whether the FEC packet
+    // arrived.
+    send_algorithm_->OnPacketLost(sequence_number, ack_receive_time);
+    OnPacketAbandoned(it);
+
     if (transmission_info.retransmittable_frames) {
       ++num_retransmitted;
       MarkForRetransmission(sequence_number, NACK_RETRANSMISSION);
+      ++it;
     } else {
       // Since we will not retransmit this, we need to remove it from
       // unacked_packets_.   This is either the current transmission of
       // a packet whose previous transmission has been acked, or it
       // is a packet that has been TLP retransmitted.
       RemovePreviousTransmission(sequence_number);
-      unacked_packets_.erase(sequence_number);
+      unacked_packets_.erase(it++);
     }
-
-    ++it;
-  }
-  // Abandon packets after the loop over pending packets, because otherwise it
-  // changes the early retransmit logic and iteration.
-  for (SequenceNumberSet::const_iterator it = lost_packets.begin();
-       it != lost_packets.end(); ++it) {
-    // TODO(ianswett): OnPacketLost is also called from TCPCubicSender when
-    // an FEC packet is lost, but FEC loss information should be shared among
-    // congestion managers.  Additionally, if it's expected the FEC packet may
-    // repair the loss, it should be recorded as a loss to the congestion
-    // manager, but not retransmitted until it's known whether the FEC packet
-    // arrived.
-    QuicPacketSequenceNumber lost_packet = *it;
-    send_algorithm_->OnPacketLost(lost_packet, ack_receive_time);
-    OnPacketAbandoned(lost_packet);
   }
 }
 
 void QuicSentPacketManager::MaybeUpdateRTT(
     const ReceivedPacketInfo& received_info,
     const QuicTime& ack_receive_time) {
   // We calculate the RTT based on the highest ACKed sequence number, the lower
   // sequence numbers will include the ACK aggregation delay.
-  SendAlgorithmInterface::SentPacketsMap::iterator history_it =
-      packet_history_map_.find(received_info.largest_observed);
-  // TODO(satyamshekhar): largest_observed might be missing.
-  if (history_it == packet_history_map_.end()) {
+  UnackedPacketMap::iterator unacked_it =
+      unacked_packets_.find(received_info.largest_observed);
+  if (unacked_it == unacked_packets_.end()) {
+    return;
+  }
+  const TransmissionInfo* transmission_info = &unacked_it->second;
+  if (transmission_info == NULL) {
     return;
   }
 
-  QuicTime::Delta send_delta = ack_receive_time.Subtract(
-      history_it->second->send_timestamp());
+  QuicTime::Delta send_delta =
+      ack_receive_time.Subtract(transmission_info->sent_time);
   if (send_delta > received_info.delta_time_largest_observed) {
     rtt_sample_ = send_delta.Subtract(
         received_info.delta_time_largest_observed);
   } else if (rtt_sample_.IsInfinite()) {
     // Even though we received information from the peer suggesting
     // an invalid (negative) RTT, we can use the send delta as an
     // approximation until we get a better estimate.
     rtt_sample_ = send_delta;
   }
 }
@@ skipping 12 matching lines @@
 // delayed ack to get back to the QUIC peer before the sender's
 // retransmission timer triggers.  Since we do not know the
 // reverse-path one-way delay, we assume equal delays for forward and
 // reverse paths, and ensure that the timer is set to less than half
 // of the MinRTO.
 // There may be a value in making this delay adaptive with the help of
 // the sender and a signaling mechanism -- if the sender uses a
 // different MinRTO, we may get spurious retransmissions. May not have
 // any benefits, but if the delayed ack becomes a significant source
 // of (likely, tail) latency, then consider such a mechanism.
-
 const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() const {
   return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2);
 }
 
 const QuicTime QuicSentPacketManager::GetRetransmissionTime() const {
-  // There can't be any retransmittable packets if there are none pending.
-  if (pending_packets_.empty()) {
+  // Don't set the timer if there are no pending packets.
+  if (!HasPendingPackets()) {
     return QuicTime::Zero();
   }
   switch (GetRetransmissionMode()) {
     case HANDSHAKE_MODE:
       return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay());
     case TLP_MODE: {
       // TODO(ianswett): When CWND is available, it would be preferable to
       // set the timer based on the earliest retransmittable packet.
       // Base the updated timer on the send time of the last packet.
-      QuicPacketSequenceNumber last_pending_packet = *pending_packets_.rbegin();
-      const QuicTime& sent_time = packet_history_map_.find(
-          last_pending_packet)->second->send_timestamp();
+      UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
+      while (it != unacked_packets_.rend() &&
+             (!it->second.pending ||
+              it->second.retransmittable_frames == NULL)) {
+        ++it;
+      }
+      DCHECK(it != unacked_packets_.rend());
+      const QuicTime& sent_time = it->second.sent_time;
       const QuicTime tlp_time = sent_time.Add(GetTailLossProbeDelay());
       // Ensure the tlp timer never gets set to a time in the past.
       return QuicTime::Max(clock_->ApproximateNow(), tlp_time);
     }
     case RTO_MODE: {
-      QuicPacketSequenceNumber first_pending_packet = *pending_packets_.begin();
-      const QuicTime& sent_time = packet_history_map_.find(
-          first_pending_packet)->second->send_timestamp();
+      // The RTO is based on the first pending packet.
+      UnackedPacketMap::const_iterator it = unacked_packets_.begin();
+      while (it != unacked_packets_.end() && !it->second.pending) {
+        ++it;
+      }
+      DCHECK(it != unacked_packets_.end());
+      const QuicTime& sent_time = it->second.sent_time;
       // Always wait at least 1.5 * RTT after the first sent packet.
       QuicTime min_timeout = clock_->ApproximateNow().Add(
           SmoothedRtt().Multiply(1.5));
       QuicTime rto_timeout = sent_time.Add(GetRetransmissionDelay());
-
       return QuicTime::Max(min_timeout, rto_timeout);
     }
     default:
       DCHECK(false);
   }
   return QuicTime::Zero();
 }
 
 const QuicTime::Delta QuicSentPacketManager::GetCryptoRetransmissionDelay()
     const {
   // This is equivalent to the TailLossProbeDelay, but slightly more aggressive
   // because crypto handshake messages don't incur a delayed ack time.
   int64 delay_ms = max<int64>(kMinHandshakeTimeoutMs,
                               1.5 * SmoothedRtt().ToMilliseconds());
   return QuicTime::Delta::FromMilliseconds(
       delay_ms << consecutive_crypto_retransmission_count_);
 }
 
 const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const {
   QuicTime::Delta srtt = SmoothedRtt();
-  if (pending_packets_.size() == 1) {
+  size_t num_pending = 0;
+  for (UnackedPacketMap::const_reverse_iterator it = unacked_packets_.rbegin();
+       it != unacked_packets_.rend(); ++it) {
+    if (it->second.pending) {
+      ++num_pending;
+      if (num_pending > 1) {
+        break;
+      }
+    }
+  }
+  DCHECK_LT(0u, num_pending);
+  if (num_pending == 1) {
     return QuicTime::Delta::Max(
         srtt.Multiply(1.5).Add(DelayedAckTime()), srtt.Multiply(2));
   }
   return QuicTime::Delta::FromMilliseconds(
       max(kMinTailLossProbeTimeoutMs,
           static_cast<int64>(2 * srtt.ToMilliseconds())));
 }
 
 const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const {
   QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
@@ skipping 33 matching lines @@
       QuicTime::Delta::FromMilliseconds(kHistoryPeriodMs);
   QuicTime now = clock_->ApproximateNow();
 
   SendAlgorithmInterface::SentPacketsMap::iterator history_it =
       packet_history_map_.begin();
   for (; history_it != packet_history_map_.end(); ++history_it) {
     if (now.Subtract(history_it->second->send_timestamp()) <= kHistoryPeriod) {
       return;
     }
     // Don't remove packets which have not been acked.
-    if (ContainsKey(pending_packets_, history_it->first)) {
+    if (ContainsKey(unacked_packets_, history_it->first)) {
       continue;
     }
     delete history_it->second;
     packet_history_map_.erase(history_it);
     history_it = packet_history_map_.begin();
   }
 }
 
 void QuicSentPacketManager::MaybeEnablePacing() {
   if (!FLAGS_enable_quic_pacing) {
@@ skipping 19 matching lines @@
   }
   previous_transmissions->erase(sequence_number);
   if (previous_transmissions->size() == 1) {
     QuicPacketSequenceNumber current = *previous_transmissions->begin();
     unacked_packets_[current].previous_transmissions = NULL;
     delete previous_transmissions;
   }
 }
 
 }  // namespace net