Land 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 "base/logging.h"
 #include "base/stl_util.h"
 #include "net/quic/congestion_control/pacing_sender.h"
 #include "net/quic/quic_ack_notifier_manager.h"
 
 using std::make_pair;
 using std::max;
 using std::min;
 
 // TODO(rtenneti): Remove this.
 // Do not flip this flag until the flakiness of the
 // net/tools/quic/end_to_end_test is fixed.
 // If true, then QUIC connections will track the retransmission history of a
 // packet so that an ack of a previous transmission will ack the data of all
 // other transmissions.
 bool FLAGS_track_retransmission_history = false;
 
-// A test-only flag to prevent the RTO from backing off when multiple sequential
-// tail drops occur.
-bool FLAGS_limit_rto_increase_for_tests = false;
-
 // Do not remove this flag until the Finch-trials described in b/11706275
 // are complete.
 // If true, QUIC connections will support the use of a pacing algorithm when
 // sending packets, in an attempt to reduce packet loss.  The client must also
 // request pacing for the server to enable it.
 bool FLAGS_enable_quic_pacing = false;
 
 namespace net {
 namespace {
 static const int kBitrateSmoothingPeriodMs = 1000;
@@ skipping 214 matching lines @@
 void QuicSentPacketManager::ClearPreviousRetransmissions(size_t num_to_clear) {
   UnackedPacketMap::iterator it = unacked_packets_.begin();
   while (it != unacked_packets_.end() && num_to_clear > 0) {
     QuicPacketSequenceNumber sequence_number = it->first;
     // If this is not a previous transmission then there is no point
     // in clearing out any further packets, because it will not affect
     // the high water mark.
     SequenceNumberSet* previous_transmissions =
         it->second.previous_transmissions;
     if (previous_transmissions == NULL) {
+      if (it->second.retransmittable_frames == NULL) {
+        // This is a current transmission, but a previous transmission has
+        // been acked, so it's safe to remove.
+        it = MarkPacketHandled(sequence_number, NOT_RECEIVED_BY_PEER);
+        --num_to_clear;
+        continue;
+      }
       break;
     }
     QuicPacketSequenceNumber newest_transmission =
         *previous_transmissions->rbegin();
     if (sequence_number == newest_transmission) {
       break;
     }
 
     DCHECK(it->second.retransmittable_frames == NULL);
     previous_transmissions->erase(sequence_number);
@@ skipping 143 matching lines @@
         unacked_packets_.find(newest_transmission);
     if (HasCryptoHandshake(newest_it->second)) {
       --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;
-    pending_retransmissions_.erase(newest_transmission);
   }
 
   // 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)) {
       send_algorithm_->OnPacketLost(previous_transmission, clock_->Now());
       OnPacketAbandoned(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 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) {
@@ skipping 165 matching lines @@
     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.
-  QuicTime::Delta retransmission_delay = GetRetransmissionDelay();
-  QuicTime max_send_time =
-      clock_->ApproximateNow().Subtract(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();
        it != unacked_packets_.end(); ++it) {
     if (it->second.retransmittable_frames != NULL) {
-      OnPacketAbandoned(it->first);
       packets_retransmitted = true;
       MarkForRetransmission(it->first, RTO_RETRANSMISSION);
-    } else if (it->second.sent_time <= max_send_time) {
-      OnPacketAbandoned(it->first);
     }
   }
 
-  // Only inform the send algorithm of an RTO if data was retransmitted.
+  pending_packets_.clear();
+  send_algorithm_->OnRetransmissionTimeout(packets_retransmitted);
   if (packets_retransmitted) {
     ++consecutive_rto_count_;
-    send_algorithm_->OnRetransmissionTimeout();
   }
 }
 
 QuicSentPacketManager::RetransmissionTimeoutMode
     QuicSentPacketManager::GetRetransmissionMode() const {
   DCHECK(!pending_packets_.empty());
   if (pending_crypto_packet_count_ > 0) {
     return HANDSHAKE_MODE;
   }
   if (consecutive_tlp_count_ < max_tail_loss_probes_) {
@@ skipping 77 matching lines @@
     // 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);
     if (transmission_info.retransmittable_frames) {
       ++num_retransmitted;
-      MarkForRetransmission(*it, NACK_RETRANSMISSION);
+      MarkForRetransmission(sequence_number, NACK_RETRANSMISSION);
+    } 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);
     }
 
     ++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.
-    send_algorithm_->OnPacketLost(*it, ack_receive_time);
-    OnPacketAbandoned(*it);
+    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);
@@ skipping 70 matching lines @@
       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 {
+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) {
     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 {
-  size_t number_retransmissions = consecutive_rto_count_;
-  // TODO(ianswett): Remove this flag now that EndToEndTest is no longer flaky.
-  if (FLAGS_limit_rto_increase_for_tests) {
-    const size_t kTailDropWindowSize = 5;
-    const size_t kTailDropMaxRetransmissions = 4;
-    if (pending_packets_.size() <= kTailDropWindowSize) {
-      // Avoid exponential backoff of RTO when there are only a few packets
-      // outstanding.  This helps avoid the situation where fake packet loss
-      // causes a packet and it's retransmission to be dropped causing
-      // test timouts.
-      if (number_retransmissions <= kTailDropMaxRetransmissions) {
-        number_retransmissions = 0;
-      } else {
-        number_retransmissions -= kTailDropMaxRetransmissions;
-      }
-    }
-  }
-
   QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
   if (retransmission_delay.IsZero()) {
     // We are in the initial state, use default timeout values.
     retransmission_delay =
         QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
   }
   // Calculate exponential back off.
   retransmission_delay = retransmission_delay.Multiply(
-      1 << min<size_t>(number_retransmissions, kMaxRetransmissions));
+      1 << min<size_t>(consecutive_rto_count_, kMaxRetransmissions));
 
   // TODO(rch): This code should move to |send_algorithm_|.
   if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
     return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
   }
   if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
     return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
   }
   return retransmission_delay;
 }
@@ skipping 39 matching lines @@
   if (using_pacing_) {
     return;
   }
 
   using_pacing_ = true;
   send_algorithm_.reset(
       new PacingSender(send_algorithm_.release(),
                        QuicTime::Delta::FromMicroseconds(1)));
 }
 
+void QuicSentPacketManager::RemovePreviousTransmission(
+    QuicPacketSequenceNumber sequence_number) {
+  SequenceNumberSet* previous_transmissions =
+      unacked_packets_[sequence_number].previous_transmissions;
+  if (!previous_transmissions) {
+    return;
+  }
+  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