net/quic/quic_sent_packet_manager.cc

   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_sent_packet_manager.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/logging.h"
  10 #include "base/stl_util.h"
  11 #include "net/quic/congestion_control/pacing_sender.h"
  12 #include "net/quic/crypto/crypto_protocol.h"
  13 #include "net/quic/proto/cached_network_parameters.pb.h"
  14 #include "net/quic/quic_ack_notifier_manager.h"
  15 #include "net/quic/quic_connection_stats.h"
  16 #include "net/quic/quic_flags.h"
  17 #include "net/quic/quic_utils_chromium.h"
  18
  19 using std::max;
  20 using std::min;
  21
  22 namespace net {
  23
  24 // The length of the recent min rtt window in seconds. Windowing is disabled for
  25 // values less than or equal to 0.
  26 int32 FLAGS_quic_recent_min_rtt_window_s = 60;
  27
  28 namespace {
  29 static const int64 kDefaultRetransmissionTimeMs = 500;
  30 // TCP RFC calls for 1 second RTO however Linux differs from this default and
  31 // define the minimum RTO to 200ms, we will use the same until we have data to
  32 // support a higher or lower value.
  33 static const int64 kMinRetransmissionTimeMs = 200;
  34 static const int64 kMaxRetransmissionTimeMs = 60000;
  35 // Maximum number of exponential backoffs used for RTO timeouts.
  36 static const size_t kMaxRetransmissions = 10;
  37 // Maximum number of packets retransmitted upon an RTO.
  38 static const size_t kMaxRetransmissionsOnTimeout = 2;
  39
  40 // Ensure the handshake timer isnt't faster than 10ms.
  41 // This limits the tenth retransmitted packet to 10s after the initial CHLO.
  42 static const int64 kMinHandshakeTimeoutMs = 10;
  43
  44 // Sends up to two tail loss probes before firing an RTO,
  45 // per draft RFC draft-dukkipati-tcpm-tcp-loss-probe.
  46 static const size_t kDefaultMaxTailLossProbes = 2;
  47 static const int64 kMinTailLossProbeTimeoutMs = 10;
  48
  49 // Number of unpaced packets to send after quiescence.
  50 static const size_t kInitialUnpacedBurst = 10;
  51
  52 bool HasCryptoHandshake(const TransmissionInfo& transmission_info) {
  53   if (transmission_info.retransmittable_frames == nullptr) {
  54     return false;
  55   }
  56   return transmission_info.retransmittable_frames->HasCryptoHandshake() ==
  57       IS_HANDSHAKE;
  58 }
  59
  60 }  // namespace
  61
  62 #define ENDPOINT \
  63   (perspective_ == Perspective::IS_SERVER ? "Server: " : "Client: ")
  64
  65 QuicSentPacketManager::QuicSentPacketManager(
  66     Perspective perspective,
  67     const QuicClock* clock,
  68     QuicConnectionStats* stats,
  69     CongestionControlType congestion_control_type,
  70     LossDetectionType loss_type,
  71     bool is_secure)
  72     : unacked_packets_(&ack_notifier_manager_),
  73       perspective_(perspective),
  74       clock_(clock),
  75       stats_(stats),
  76       debug_delegate_(nullptr),
  77       network_change_visitor_(nullptr),
  78       initial_congestion_window_(is_secure ? kInitialCongestionWindowSecure
  79                                            : kInitialCongestionWindowInsecure),
  80       send_algorithm_(
  81           SendAlgorithmInterface::Create(clock,
  82                                          &rtt_stats_,
  83                                          congestion_control_type,
  84                                          stats,
  85                                          initial_congestion_window_)),
  86       loss_algorithm_(LossDetectionInterface::Create(loss_type)),
  87       n_connection_simulation_(false),
  88       receive_buffer_bytes_(kDefaultSocketReceiveBuffer),
  89       least_packet_awaited_by_peer_(1),
  90       first_rto_transmission_(0),
  91       consecutive_rto_count_(0),
  92       consecutive_tlp_count_(0),
  93       consecutive_crypto_retransmission_count_(0),
  94       pending_timer_transmission_count_(0),
  95       max_tail_loss_probes_(kDefaultMaxTailLossProbes),
  96       enable_half_rtt_tail_loss_probe_(false),
  97       using_pacing_(false),
  98       use_new_rto_(false),
  99       handshake_confirmed_(false) {}
 100
 101 QuicSentPacketManager::~QuicSentPacketManager() {
 102 }
 103
 104 void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) {
 105   if (config.HasReceivedInitialRoundTripTimeUs() &&
 106       config.ReceivedInitialRoundTripTimeUs() > 0) {
 107     rtt_stats_.set_initial_rtt_us(
 108         max(kMinInitialRoundTripTimeUs,
 109             min(kMaxInitialRoundTripTimeUs,
 110                 config.ReceivedInitialRoundTripTimeUs())));
 111   } else if (config.HasInitialRoundTripTimeUsToSend() &&
 112              config.GetInitialRoundTripTimeUsToSend() > 0) {
 113     rtt_stats_.set_initial_rtt_us(
 114         max(kMinInitialRoundTripTimeUs,
 115             min(kMaxInitialRoundTripTimeUs,
 116                 config.GetInitialRoundTripTimeUsToSend())));
 117   }
 118   // Initial RTT may have changed.
 119   if (network_change_visitor_ != nullptr) {
 120     network_change_visitor_->OnRttChange();
 121   }
 122   // TODO(ianswett): BBR is currently a server only feature.
 123   if (FLAGS_quic_allow_bbr &&
 124       config.HasReceivedConnectionOptions() &&
 125       ContainsQuicTag(config.ReceivedConnectionOptions(), kTBBR)) {
 126     if (FLAGS_quic_recent_min_rtt_window_s > 0) {
 127       rtt_stats_.set_recent_min_rtt_window(
 128           QuicTime::Delta::FromSeconds(FLAGS_quic_recent_min_rtt_window_s));
 129     }
 130     send_algorithm_.reset(SendAlgorithmInterface::Create(
 131         clock_, &rtt_stats_, kBBR, stats_, initial_congestion_window_));
 132   }
 133   if (config.HasReceivedConnectionOptions() &&
 134       ContainsQuicTag(config.ReceivedConnectionOptions(), kRENO)) {
 135     if (ContainsQuicTag(config.ReceivedConnectionOptions(), kBYTE)) {
 136       send_algorithm_.reset(SendAlgorithmInterface::Create(
 137           clock_, &rtt_stats_, kRenoBytes, stats_, initial_congestion_window_));
 138     } else {
 139       send_algorithm_.reset(SendAlgorithmInterface::Create(
 140           clock_, &rtt_stats_, kReno, stats_, initial_congestion_window_));
 141     }
 142   } else if (config.HasReceivedConnectionOptions() &&
 143              ContainsQuicTag(config.ReceivedConnectionOptions(), kBYTE)) {
 144     send_algorithm_.reset(SendAlgorithmInterface::Create(
 145         clock_, &rtt_stats_, kCubicBytes, stats_, initial_congestion_window_));
 146   }
 147   EnablePacing();
 148
 149   if (config.HasClientSentConnectionOption(k1CON, perspective_)) {
 150     send_algorithm_->SetNumEmulatedConnections(1);
 151   }
 152   if (config.HasClientSentConnectionOption(kNCON, perspective_)) {
 153     n_connection_simulation_ = true;
 154   }
 155   if (config.HasClientSentConnectionOption(kNTLP, perspective_)) {
 156     max_tail_loss_probes_ = 0;
 157   }
 158   if (config.HasClientSentConnectionOption(kTLPR, perspective_)) {
 159     enable_half_rtt_tail_loss_probe_ = true;
 160   }
 161   if (config.HasClientSentConnectionOption(kNRTO, perspective_)) {
 162     use_new_rto_ = true;
 163   }
 164   if (config.HasReceivedConnectionOptions() &&
 165       ContainsQuicTag(config.ReceivedConnectionOptions(), kTIME)) {
 166     loss_algorithm_.reset(LossDetectionInterface::Create(kTime));
 167   }
 168   if (config.HasReceivedSocketReceiveBuffer()) {
 169     receive_buffer_bytes_ =
 170         max(kMinSocketReceiveBuffer,
 171             static_cast<QuicByteCount>(config.ReceivedSocketReceiveBuffer()));
 172     QuicByteCount max_cwnd_bytes = static_cast<QuicByteCount>(
 173         receive_buffer_bytes_ * (FLAGS_quic_use_conservative_receive_buffer
 174                                      ? kConservativeReceiveBufferFraction
 175                                      : kUsableRecieveBufferFraction));
 176     if (FLAGS_quic_limit_max_cwnd) {
 177       max_cwnd_bytes =
 178           min(max_cwnd_bytes, kMaxCongestionWindow * kDefaultTCPMSS);
 179     }
 180     send_algorithm_->SetMaxCongestionWindow(max_cwnd_bytes);
 181   }
 182   send_algorithm_->SetFromConfig(config, perspective_);
 183
 184   if (network_change_visitor_ != nullptr) {
 185     network_change_visitor_->OnCongestionWindowChange();
 186   }
 187 }
 188
 189 void QuicSentPacketManager::ResumeConnectionState(
 190     const CachedNetworkParameters& cached_network_params,
 191     bool max_bandwidth_resumption) {
 192   if (cached_network_params.has_min_rtt_ms()) {
 193     uint32 initial_rtt_us =
 194         kNumMicrosPerMilli * cached_network_params.min_rtt_ms();
 195     rtt_stats_.set_initial_rtt_us(
 196         max(kMinInitialRoundTripTimeUs,
 197             min(kMaxInitialRoundTripTimeUs, initial_rtt_us)));
 198   }
 199   send_algorithm_->ResumeConnectionState(cached_network_params,
 200                                          max_bandwidth_resumption);
 201 }
 202
 203 void QuicSentPacketManager::SetNumOpenStreams(size_t num_streams) {
 204   if (n_connection_simulation_) {
 205     // Ensure the number of connections is between 1 and 5.
 206     send_algorithm_->SetNumEmulatedConnections(
 207         min<size_t>(5, max<size_t>(1, num_streams)));
 208   }
 209 }
 210
 211 void QuicSentPacketManager::OnIncomingAck(const QuicAckFrame& ack_frame,
 212                                           QuicTime ack_receive_time) {
 213   QuicByteCount bytes_in_flight = unacked_packets_.bytes_in_flight();
 214
 215   UpdatePacketInformationReceivedByPeer(ack_frame);
 216   bool rtt_updated = MaybeUpdateRTT(ack_frame, ack_receive_time);
 217   DCHECK_GE(ack_frame.largest_observed, unacked_packets_.largest_observed());
 218   unacked_packets_.IncreaseLargestObserved(ack_frame.largest_observed);
 219
 220   HandleAckForSentPackets(ack_frame);
 221   InvokeLossDetection(ack_receive_time);
 222   // Ignore losses in RTO mode.
 223   if (consecutive_rto_count_ > 0 && !use_new_rto_) {
 224     packets_lost_.clear();
 225   }
 226   MaybeInvokeCongestionEvent(rtt_updated, bytes_in_flight);
 227   unacked_packets_.RemoveObsoletePackets();
 228
 229   sustained_bandwidth_recorder_.RecordEstimate(
 230       send_algorithm_->InRecovery(),
 231       send_algorithm_->InSlowStart(),
 232       send_algorithm_->BandwidthEstimate(),
 233       ack_receive_time,
 234       clock_->WallNow(),
 235       rtt_stats_.smoothed_rtt());
 236
 237   // If we have received a truncated ack, then we need to clear out some
 238   // previous transmissions to allow the peer to actually ACK new packets.
 239   if (ack_frame.is_truncated && !FLAGS_quic_disable_truncated_ack_handling) {
 240     unacked_packets_.ClearAllPreviousRetransmissions();
 241   }
 242
 243   // Anytime we are making forward progress and have a new RTT estimate, reset
 244   // the backoff counters.
 245   if (rtt_updated) {
 246     if (consecutive_rto_count_ > 0) {
 247       // If the ack acknowledges data sent prior to the RTO,
 248       // the RTO was spurious.
 249       if (ack_frame.largest_observed < first_rto_transmission_) {
 250         // Replace SRTT with latest_rtt and increase the variance to prevent
 251         // a spurious RTO from happening again.
 252         rtt_stats_.ExpireSmoothedMetrics();
 253       } else {
 254         if (!use_new_rto_) {
 255           send_algorithm_->OnRetransmissionTimeout(true);
 256         }
 257       }
 258     }
 259     // Reset all retransmit counters any time a new packet is acked.
 260     consecutive_rto_count_ = 0;
 261     consecutive_tlp_count_ = 0;
 262     consecutive_crypto_retransmission_count_ = 0;
 263   }
 264
 265   if (debug_delegate_ != nullptr) {
 266     debug_delegate_->OnIncomingAck(ack_frame, ack_receive_time,
 267                                    unacked_packets_.largest_observed(),
 268                                    rtt_updated, GetLeastUnacked());
 269   }
 270 }
 271
 272 void QuicSentPacketManager::UpdatePacketInformationReceivedByPeer(
 273     const QuicAckFrame& ack_frame) {
 274   if (ack_frame.missing_packets.empty()) {
 275     least_packet_awaited_by_peer_ = ack_frame.largest_observed + 1;
 276   } else {
 277     least_packet_awaited_by_peer_ = *(ack_frame.missing_packets.begin());
 278   }
 279 }
 280
 281 void QuicSentPacketManager::MaybeInvokeCongestionEvent(
 282     bool rtt_updated, QuicByteCount bytes_in_flight) {
 283   if (!rtt_updated && packets_acked_.empty() && packets_lost_.empty()) {
 284     return;
 285   }
 286   send_algorithm_->OnCongestionEvent(rtt_updated, bytes_in_flight,
 287                                      packets_acked_, packets_lost_);
 288   packets_acked_.clear();
 289   packets_lost_.clear();
 290   if (network_change_visitor_ != nullptr) {
 291     network_change_visitor_->OnCongestionWindowChange();
 292   }
 293 }
 294
 295 void QuicSentPacketManager::HandleAckForSentPackets(
 296     const QuicAckFrame& ack_frame) {
 297   // Go through the packets we have not received an ack for and see if this
 298   // incoming_ack shows they've been seen by the peer.
 299   QuicTime::Delta delta_largest_observed =
 300       ack_frame.delta_time_largest_observed;
 301   QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
 302   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 303        it != unacked_packets_.end(); ++it, ++packet_number) {
 304     if (packet_number > ack_frame.largest_observed) {
 305       // These packets are still in flight.
 306       break;
 307     }
 308
 309     if (ContainsKey(ack_frame.missing_packets, packet_number)) {
 310       // Don't continue to increase the nack count for packets not in flight.
 311       if (!it->in_flight) {
 312         continue;
 313       }
 314       // Consider it multiple nacks when there is a gap between the missing
 315       // packet and the largest observed, since the purpose of a nack
 316       // threshold is to tolerate re-ordering.  This handles both StretchAcks
 317       // and Forward Acks.
 318       // The nack count only increases when the largest observed increases.
 319       QuicPacketCount min_nacks = ack_frame.largest_observed - packet_number;
 320       // Truncated acks can nack the largest observed, so use a min of 1.
 321       if (min_nacks == 0) {
 322         min_nacks = 1;
 323       }
 324       unacked_packets_.NackPacket(packet_number, min_nacks);
 325       continue;
 326     }
 327     // Packet was acked, so remove it from our unacked packet list.
 328     DVLOG(1) << ENDPOINT << "Got an ack for packet " << packet_number;
 329     // If data is associated with the most recent transmission of this
 330     // packet, then inform the caller.
 331     if (it->in_flight) {
 332       packets_acked_.push_back(std::make_pair(packet_number, *it));
 333     }
 334     MarkPacketHandled(packet_number, *it, delta_largest_observed);
 335   }
 336
 337   // Discard any retransmittable frames associated with revived packets.
 338   for (PacketNumberSet::const_iterator revived_it =
 339            ack_frame.revived_packets.begin();
 340        revived_it != ack_frame.revived_packets.end(); ++revived_it) {
 341     MarkPacketRevived(*revived_it, delta_largest_observed);
 342   }
 343 }
 344
 345 bool QuicSentPacketManager::HasRetransmittableFrames(
 346     QuicPacketNumber packet_number) const {
 347   return unacked_packets_.HasRetransmittableFrames(packet_number);
 348 }
 349
 350 void QuicSentPacketManager::RetransmitUnackedPackets(
 351     TransmissionType retransmission_type) {
 352   DCHECK(retransmission_type == ALL_UNACKED_RETRANSMISSION ||
 353          retransmission_type == ALL_INITIAL_RETRANSMISSION);
 354   QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
 355   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 356        it != unacked_packets_.end(); ++it, ++packet_number) {
 357     const RetransmittableFrames* frames = it->retransmittable_frames;
 358     if (frames != nullptr &&
 359         (retransmission_type == ALL_UNACKED_RETRANSMISSION ||
 360          frames->encryption_level() == ENCRYPTION_INITIAL)) {
 361       MarkForRetransmission(packet_number, retransmission_type);
 362     } else if (it->is_fec_packet) {
 363       // Remove FEC packets from the packet map, since we can't retransmit them.
 364       unacked_packets_.RemoveFromInFlight(packet_number);
 365     }
 366   }
 367 }
 368
 369 void QuicSentPacketManager::NeuterUnencryptedPackets() {
 370   QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
 371   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 372        it != unacked_packets_.end(); ++it, ++packet_number) {
 373     const RetransmittableFrames* frames = it->retransmittable_frames;
 374     if (frames != nullptr && frames->encryption_level() == ENCRYPTION_NONE) {
 375       // Once you're forward secure, no unencrypted packets will be sent, crypto
 376       // or otherwise. Unencrypted packets are neutered and abandoned, to ensure
 377       // they are not retransmitted or considered lost from a congestion control
 378       // perspective.
 379       pending_retransmissions_.erase(packet_number);
 380       unacked_packets_.RemoveFromInFlight(packet_number);
 381       unacked_packets_.RemoveRetransmittability(packet_number);
 382     }
 383   }
 384 }
 385
 386 void QuicSentPacketManager::MarkForRetransmission(
 387     QuicPacketNumber packet_number,
 388     TransmissionType transmission_type) {
 389   const TransmissionInfo& transmission_info =
 390       unacked_packets_.GetTransmissionInfo(packet_number);
 391   LOG_IF(DFATAL, transmission_info.retransmittable_frames == nullptr);
 392   // Both TLP and the new RTO leave the packets in flight and let the loss
 393   // detection decide if packets are lost.
 394   if (transmission_type != TLP_RETRANSMISSION &&
 395       transmission_type != RTO_RETRANSMISSION) {
 396     unacked_packets_.RemoveFromInFlight(packet_number);
 397   }
 398   // TODO(ianswett): Currently the RTO can fire while there are pending NACK
 399   // retransmissions for the same data, which is not ideal.
 400   if (ContainsKey(pending_retransmissions_, packet_number)) {
 401     return;
 402   }
 403
 404   pending_retransmissions_[packet_number] = transmission_type;
 405 }
 406
 407 void QuicSentPacketManager::RecordSpuriousRetransmissions(
 408     const PacketNumberList& all_transmissions,
 409     QuicPacketNumber acked_packet_number) {
 410   for (PacketNumberList::const_reverse_iterator it = all_transmissions.rbegin();
 411        it != all_transmissions.rend() && *it > acked_packet_number; ++it) {
 412     // ianswett: Prevents crash in b/20552846.
 413     if (*it < unacked_packets_.GetLeastUnacked() ||
 414         *it > unacked_packets_.largest_sent_packet()) {
 415       LOG(DFATAL) << "Retransmission out of range:" << *it
 416                   << " least unacked:" << unacked_packets_.GetLeastUnacked()
 417                   << " largest sent:" << unacked_packets_.largest_sent_packet();
 418       return;
 419     }
 420     const TransmissionInfo& retransmit_info =
 421         unacked_packets_.GetTransmissionInfo(*it);
 422
 423     stats_->bytes_spuriously_retransmitted += retransmit_info.bytes_sent;
 424     ++stats_->packets_spuriously_retransmitted;
 425     if (debug_delegate_ != nullptr) {
 426       debug_delegate_->OnSpuriousPacketRetransmission(
 427           retransmit_info.transmission_type, retransmit_info.bytes_sent);
 428     }
 429   }
 430 }
 431
 432 bool QuicSentPacketManager::HasPendingRetransmissions() const {
 433   return !pending_retransmissions_.empty();
 434 }
 435
 436 QuicSentPacketManager::PendingRetransmission
 437     QuicSentPacketManager::NextPendingRetransmission() {
 438   LOG_IF(DFATAL, pending_retransmissions_.empty())
 439       << "Unexpected call to PendingRetransmissions() with empty pending "
 440       << "retransmission list. Corrupted memory usage imminent.";
 441   QuicPacketNumber packet_number = pending_retransmissions_.begin()->first;
 442   TransmissionType transmission_type = pending_retransmissions_.begin()->second;
 443   if (unacked_packets_.HasPendingCryptoPackets()) {
 444     // Ensure crypto packets are retransmitted before other packets.
 445     for (const auto& pair : pending_retransmissions_) {
 446       if (HasCryptoHandshake(
 447               unacked_packets_.GetTransmissionInfo(pair.first))) {
 448         packet_number = pair.first;
 449         transmission_type = pair.second;
 450         break;
 451       }
 452     }
 453   }
 454   DCHECK(unacked_packets_.IsUnacked(packet_number)) << packet_number;
 455   const TransmissionInfo& transmission_info =
 456       unacked_packets_.GetTransmissionInfo(packet_number);
 457   DCHECK(transmission_info.retransmittable_frames);
 458
 459   return PendingRetransmission(packet_number, transmission_type,
 460                                *transmission_info.retransmittable_frames,
 461                                transmission_info.packet_number_length);
 462 }
 463
 464 void QuicSentPacketManager::MarkPacketRevived(
 465     QuicPacketNumber packet_number,
 466     QuicTime::Delta delta_largest_observed) {
 467   if (!unacked_packets_.IsUnacked(packet_number)) {
 468     return;
 469   }
 470
 471   const TransmissionInfo& transmission_info =
 472       unacked_packets_.GetTransmissionInfo(packet_number);
 473   QuicPacketNumber newest_transmission =
 474       transmission_info.all_transmissions == nullptr
 475           ? packet_number
 476           : *transmission_info.all_transmissions->rbegin();
 477   // This packet has been revived at the receiver. If we were going to
 478   // retransmit it, do not retransmit it anymore.
 479   pending_retransmissions_.erase(newest_transmission);
 480
 481   // The AckNotifierManager needs to be notified for revived packets,
 482   // since it indicates the packet arrived from the appliction's perspective.
 483   ack_notifier_manager_.OnPacketAcked(newest_transmission,
 484                                       delta_largest_observed);
 485
 486   unacked_packets_.RemoveRetransmittability(packet_number);
 487 }
 488
 489 void QuicSentPacketManager::MarkPacketHandled(
 490     QuicPacketNumber packet_number,
 491     const TransmissionInfo& info,
 492     QuicTime::Delta delta_largest_observed) {
 493   QuicPacketNumber newest_transmission =
 494       info.all_transmissions == nullptr ? packet_number
 495                                         : *info.all_transmissions->rbegin();
 496   // Remove the most recent packet, if it is pending retransmission.
 497   pending_retransmissions_.erase(newest_transmission);
 498
 499   // The AckNotifierManager needs to be notified about the most recent
 500   // transmission, since that's the one only one it tracks.
 501   ack_notifier_manager_.OnPacketAcked(newest_transmission,
 502                                       delta_largest_observed);
 503   if (newest_transmission != packet_number) {
 504     RecordSpuriousRetransmissions(*info.all_transmissions, packet_number);
 505     // Remove the most recent packet from flight if it's a crypto handshake
 506     // packet, since they won't be acked now that one has been processed.
 507     // Other crypto handshake packets won't be in flight, only the newest
 508     // transmission of a crypto packet is in flight at once.
 509     // TODO(ianswett): Instead of handling all crypto packets special,
 510     // only handle nullptr encrypted packets in a special way.
 511     if (HasCryptoHandshake(
 512         unacked_packets_.GetTransmissionInfo(newest_transmission))) {
 513       unacked_packets_.RemoveFromInFlight(newest_transmission);
 514     }
 515   }
 516
 517   unacked_packets_.RemoveFromInFlight(packet_number);
 518   unacked_packets_.RemoveRetransmittability(packet_number);
 519 }
 520
 521 bool QuicSentPacketManager::IsUnacked(QuicPacketNumber packet_number) const {
 522   return unacked_packets_.IsUnacked(packet_number);
 523 }
 524
 525 bool QuicSentPacketManager::HasUnackedPackets() const {
 526   return unacked_packets_.HasUnackedPackets();
 527 }
 528
 529 QuicPacketNumber QuicSentPacketManager::GetLeastUnacked() const {
 530   return unacked_packets_.GetLeastUnacked();
 531 }
 532
 533 bool QuicSentPacketManager::OnPacketSent(
 534     SerializedPacket* serialized_packet,
 535     QuicPacketNumber original_packet_number,
 536     QuicTime sent_time,
 537     QuicByteCount bytes,
 538     TransmissionType transmission_type,
 539     HasRetransmittableData has_retransmittable_data) {
 540   QuicPacketNumber packet_number = serialized_packet->packet_number;
 541   DCHECK_LT(0u, packet_number);
 542   DCHECK(!unacked_packets_.IsUnacked(packet_number));
 543   LOG_IF(DFATAL, bytes == 0) << "Cannot send empty packets.";
 544
 545   if (original_packet_number != 0) {
 546     PendingRetransmissionMap::iterator it =
 547         pending_retransmissions_.find(original_packet_number);
 548     if (it != pending_retransmissions_.end()) {
 549       pending_retransmissions_.erase(it);
 550     } else {
 551       DLOG(DFATAL) << "Expected packet number to be in "
 552                    << "pending_retransmissions_.  packet_number: "
 553                    << original_packet_number;
 554     }
 555     // Inform the ack notifier of retransmissions so it can calculate the
 556     // retransmit rate.
 557     ack_notifier_manager_.OnPacketRetransmitted(original_packet_number,
 558                                                 packet_number, bytes);
 559   }
 560
 561   if (pending_timer_transmission_count_ > 0) {
 562     --pending_timer_transmission_count_;
 563   }
 564
 565   // Only track packets as in flight that the send algorithm wants us to track.
 566   // Since FEC packets should also be counted towards the congestion window,
 567   // consider them as retransmittable for the purposes of congestion control.
 568   HasRetransmittableData has_congestion_controlled_data =
 569       serialized_packet->is_fec_packet ? HAS_RETRANSMITTABLE_DATA
 570                                        : has_retransmittable_data;
 571   const bool in_flight = send_algorithm_->OnPacketSent(
 572       sent_time, unacked_packets_.bytes_in_flight(), packet_number, bytes,
 573       has_congestion_controlled_data);
 574
 575   unacked_packets_.AddSentPacket(*serialized_packet, original_packet_number,
 576                                  transmission_type, sent_time, bytes,
 577                                  in_flight);
 578
 579   // Take ownership of the retransmittable frames before exiting.
 580   serialized_packet->retransmittable_frames = nullptr;
 581   // Reset the retransmission timer anytime a pending packet is sent.
 582   return in_flight;
 583 }
 584
 585 void QuicSentPacketManager::OnRetransmissionTimeout() {
 586   DCHECK(unacked_packets_.HasInFlightPackets());
 587   DCHECK_EQ(0u, pending_timer_transmission_count_);
 588   // Handshake retransmission, timer based loss detection, TLP, and RTO are
 589   // implemented with a single alarm. The handshake alarm is set when the
 590   // handshake has not completed, the loss alarm is set when the loss detection
 591   // algorithm says to, and the TLP and  RTO alarms are set after that.
 592   // The TLP alarm is always set to run for under an RTO.
 593   switch (GetRetransmissionMode()) {
 594     case HANDSHAKE_MODE:
 595       ++stats_->crypto_retransmit_count;
 596       RetransmitCryptoPackets();
 597       return;
 598     case LOSS_MODE: {
 599       ++stats_->loss_timeout_count;
 600       QuicByteCount bytes_in_flight = unacked_packets_.bytes_in_flight();
 601       InvokeLossDetection(clock_->Now());
 602       MaybeInvokeCongestionEvent(false, bytes_in_flight);
 603       return;
 604     }
 605     case TLP_MODE:
 606       // If no tail loss probe can be sent, because there are no retransmittable
 607       // packets, execute a conventional RTO to abandon old packets.
 608       ++stats_->tlp_count;
 609       ++consecutive_tlp_count_;
 610       pending_timer_transmission_count_ = 1;
 611       // TLPs prefer sending new data instead of retransmitting data, so
 612       // give the connection a chance to write before completing the TLP.
 613       return;
 614     case RTO_MODE:
 615       ++stats_->rto_count;
 616       RetransmitRtoPackets();
 617       return;
 618   }
 619 }
 620
 621 void QuicSentPacketManager::RetransmitCryptoPackets() {
 622   DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode());
 623   ++consecutive_crypto_retransmission_count_;
 624   bool packet_retransmitted = false;
 625   QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
 626   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 627        it != unacked_packets_.end(); ++it, ++packet_number) {
 628     // Only retransmit frames which are in flight, and therefore have been sent.
 629     if (!it->in_flight || it->retransmittable_frames == nullptr ||
 630         it->retransmittable_frames->HasCryptoHandshake() != IS_HANDSHAKE) {
 631       continue;
 632     }
 633     packet_retransmitted = true;
 634     MarkForRetransmission(packet_number, HANDSHAKE_RETRANSMISSION);
 635     ++pending_timer_transmission_count_;
 636   }
 637   DCHECK(packet_retransmitted) << "No crypto packets found to retransmit.";
 638 }
 639
 640 bool QuicSentPacketManager::MaybeRetransmitTailLossProbe() {
 641   if (pending_timer_transmission_count_ == 0) {
 642     return false;
 643   }
 644   QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
 645   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 646        it != unacked_packets_.end(); ++it, ++packet_number) {
 647     // Only retransmit frames which are in flight, and therefore have been sent.
 648     if (!it->in_flight || it->retransmittable_frames == nullptr) {
 649       continue;
 650     }
 651     if (!handshake_confirmed_) {
 652       DCHECK_NE(IS_HANDSHAKE, it->retransmittable_frames->HasCryptoHandshake());
 653     }
 654     MarkForRetransmission(packet_number, TLP_RETRANSMISSION);
 655     return true;
 656   }
 657   DLOG(ERROR)
 658       << "No retransmittable packets, so RetransmitOldestPacket failed.";
 659   return false;
 660 }
 661
 662 void QuicSentPacketManager::RetransmitRtoPackets() {
 663   LOG_IF(DFATAL, pending_timer_transmission_count_ > 0)
 664       << "Retransmissions already queued:" << pending_timer_transmission_count_;
 665   // Mark two packets for retransmission.
 666   QuicPacketNumber packet_number = unacked_packets_.GetLeastUnacked();
 667   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 668        it != unacked_packets_.end(); ++it, ++packet_number) {
 669     if (it->retransmittable_frames != nullptr &&
 670         pending_timer_transmission_count_ < kMaxRetransmissionsOnTimeout) {
 671       MarkForRetransmission(packet_number, RTO_RETRANSMISSION);
 672       ++pending_timer_transmission_count_;
 673     }
 674     // Abandon non-retransmittable data that's in flight to ensure it doesn't
 675     // fill up the congestion window.
 676     if (it->retransmittable_frames == nullptr && it->in_flight &&
 677         it->all_transmissions == nullptr) {
 678       unacked_packets_.RemoveFromInFlight(packet_number);
 679     }
 680   }
 681   if (pending_timer_transmission_count_ > 0) {
 682     if (consecutive_rto_count_ == 0) {
 683       first_rto_transmission_ = unacked_packets_.largest_sent_packet() + 1;
 684     }
 685     ++consecutive_rto_count_;
 686   }
 687 }
 688
 689 QuicSentPacketManager::RetransmissionTimeoutMode
 690     QuicSentPacketManager::GetRetransmissionMode() const {
 691   DCHECK(unacked_packets_.HasInFlightPackets());
 692   if (!handshake_confirmed_ && unacked_packets_.HasPendingCryptoPackets()) {
 693     return HANDSHAKE_MODE;
 694   }
 695   if (loss_algorithm_->GetLossTimeout() != QuicTime::Zero()) {
 696     return LOSS_MODE;
 697   }
 698   if (consecutive_tlp_count_ < max_tail_loss_probes_) {
 699     if (unacked_packets_.HasUnackedRetransmittableFrames()) {
 700       return TLP_MODE;
 701     }
 702   }
 703   return RTO_MODE;
 704 }
 705
 706 void QuicSentPacketManager::InvokeLossDetection(QuicTime time) {
 707   PacketNumberSet lost_packets = loss_algorithm_->DetectLostPackets(
 708       unacked_packets_, time, unacked_packets_.largest_observed(), rtt_stats_);
 709   for (PacketNumberSet::const_iterator it = lost_packets.begin();
 710        it != lost_packets.end(); ++it) {
 711     QuicPacketNumber packet_number = *it;
 712     const TransmissionInfo& transmission_info =
 713         unacked_packets_.GetTransmissionInfo(packet_number);
 714     // TODO(ianswett): If it's expected the FEC packet may repair the loss, it
 715     // should be recorded as a loss to the send algorithm, but not retransmitted
 716     // until it's known whether the FEC packet arrived.
 717     ++stats_->packets_lost;
 718     packets_lost_.push_back(std::make_pair(packet_number, transmission_info));
 719     DVLOG(1) << ENDPOINT << "Lost packet " << packet_number;
 720
 721     if (transmission_info.retransmittable_frames != nullptr) {
 722       MarkForRetransmission(packet_number, LOSS_RETRANSMISSION);
 723     } else {
 724       // Since we will not retransmit this, we need to remove it from
 725       // unacked_packets_.   This is either the current transmission of
 726       // a packet whose previous transmission has been acked, a packet that has
 727       // been TLP retransmitted, or an FEC packet.
 728       unacked_packets_.RemoveFromInFlight(packet_number);
 729     }
 730   }
 731 }
 732
 733 bool QuicSentPacketManager::MaybeUpdateRTT(
 734     const QuicAckFrame& ack_frame,
 735     const QuicTime& ack_receive_time) {
 736   // We rely on delta_time_largest_observed to compute an RTT estimate, so we
 737   // only update rtt when the largest observed gets acked.
 738   // NOTE: If ack is a truncated ack, then the largest observed is in fact
 739   // unacked, and may cause an RTT sample to be taken.
 740   if (!unacked_packets_.IsUnacked(ack_frame.largest_observed)) {
 741     return false;
 742   }
 743   // We calculate the RTT based on the highest ACKed packet number, the lower
 744   // packet numbers will include the ACK aggregation delay.
 745   const TransmissionInfo& transmission_info =
 746       unacked_packets_.GetTransmissionInfo(ack_frame.largest_observed);
 747   // Ensure the packet has a valid sent time.
 748   if (transmission_info.sent_time == QuicTime::Zero()) {
 749     LOG(DFATAL) << "Acked packet has zero sent time, largest_observed:"
 750                 << ack_frame.largest_observed;
 751     return false;
 752   }
 753
 754   QuicTime::Delta send_delta =
 755       ack_receive_time.Subtract(transmission_info.sent_time);
 756   rtt_stats_.UpdateRtt(
 757       send_delta, ack_frame.delta_time_largest_observed, ack_receive_time);
 758
 759   if (network_change_visitor_ != nullptr) {
 760     network_change_visitor_->OnRttChange();
 761   }
 762
 763   return true;
 764 }
 765
 766 QuicTime::Delta QuicSentPacketManager::TimeUntilSend(
 767     QuicTime now,
 768     HasRetransmittableData retransmittable) {
 769   // The TLP logic is entirely contained within QuicSentPacketManager, so the
 770   // send algorithm does not need to be consulted.
 771   if (pending_timer_transmission_count_ > 0) {
 772     return QuicTime::Delta::Zero();
 773   }
 774   return send_algorithm_->TimeUntilSend(
 775       now, unacked_packets_.bytes_in_flight(), retransmittable);
 776 }
 777
 778 // Uses a 25ms delayed ack timer. Also helps with better signaling
 779 // in low-bandwidth (< ~384 kbps), where an ack is sent per packet.
 780 // Ensures that the Delayed Ack timer is always set to a value lesser
 781 // than the retransmission timer's minimum value (MinRTO). We want the
 782 // delayed ack to get back to the QUIC peer before the sender's
 783 // retransmission timer triggers.  Since we do not know the
 784 // reverse-path one-way delay, we assume equal delays for forward and
 785 // reverse paths, and ensure that the timer is set to less than half
 786 // of the MinRTO.
 787 // There may be a value in making this delay adaptive with the help of
 788 // the sender and a signaling mechanism -- if the sender uses a
 789 // different MinRTO, we may get spurious retransmissions. May not have
 790 // any benefits, but if the delayed ack becomes a significant source
 791 // of (likely, tail) latency, then consider such a mechanism.
 792 const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() const {
 793   return QuicTime::Delta::FromMilliseconds(min(kMaxDelayedAckTimeMs,
 794                                                kMinRetransmissionTimeMs / 2));
 795 }
 796
 797 const QuicTime QuicSentPacketManager::GetRetransmissionTime() const {
 798   // Don't set the timer if there are no packets in flight or we've already
 799   // queued a tlp transmission and it hasn't been sent yet.
 800   if (!unacked_packets_.HasInFlightPackets() ||
 801       pending_timer_transmission_count_ > 0) {
 802     return QuicTime::Zero();
 803   }
 804   switch (GetRetransmissionMode()) {
 805     case HANDSHAKE_MODE:
 806       return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay());
 807     case LOSS_MODE:
 808       return loss_algorithm_->GetLossTimeout();
 809     case TLP_MODE: {
 810       // TODO(ianswett): When CWND is available, it would be preferable to
 811       // set the timer based on the earliest retransmittable packet.
 812       // Base the updated timer on the send time of the last packet.
 813       const QuicTime sent_time = unacked_packets_.GetLastPacketSentTime();
 814       const QuicTime tlp_time = sent_time.Add(GetTailLossProbeDelay());
 815       // Ensure the TLP timer never gets set to a time in the past.
 816       return QuicTime::Max(clock_->ApproximateNow(), tlp_time);
 817     }
 818     case RTO_MODE: {
 819       // The RTO is based on the first outstanding packet.
 820       const QuicTime sent_time = unacked_packets_.GetLastPacketSentTime();
 821       QuicTime rto_time = sent_time.Add(GetRetransmissionDelay());
 822       // Wait for TLP packets to be acked before an RTO fires.
 823       QuicTime tlp_time =
 824           unacked_packets_.GetLastPacketSentTime().Add(GetTailLossProbeDelay());
 825       return QuicTime::Max(tlp_time, rto_time);
 826     }
 827   }
 828   DCHECK(false);
 829   return QuicTime::Zero();
 830 }
 831
 832 const QuicTime::Delta QuicSentPacketManager::GetCryptoRetransmissionDelay()
 833     const {
 834   // This is equivalent to the TailLossProbeDelay, but slightly more aggressive
 835   // because crypto handshake messages don't incur a delayed ack time.
 836   QuicTime::Delta srtt = rtt_stats_.smoothed_rtt();
 837   if (srtt.IsZero()) {
 838     srtt = QuicTime::Delta::FromMicroseconds(rtt_stats_.initial_rtt_us());
 839   }
 840   int64 delay_ms = max(kMinHandshakeTimeoutMs,
 841                        static_cast<int64>(1.5 * srtt.ToMilliseconds()));
 842   return QuicTime::Delta::FromMilliseconds(
 843       delay_ms << consecutive_crypto_retransmission_count_);
 844 }
 845
 846 const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const {
 847   QuicTime::Delta srtt = rtt_stats_.smoothed_rtt();
 848   if (srtt.IsZero()) {
 849     srtt = QuicTime::Delta::FromMicroseconds(rtt_stats_.initial_rtt_us());
 850   }
 851   if (enable_half_rtt_tail_loss_probe_ && consecutive_tlp_count_ == 0u) {
 852     return QuicTime::Delta::FromMilliseconds(
 853         max(kMinTailLossProbeTimeoutMs,
 854             static_cast<int64>(0.5 * srtt.ToMilliseconds())));
 855   }
 856   if (!unacked_packets_.HasMultipleInFlightPackets()) {
 857     return QuicTime::Delta::Max(
 858         srtt.Multiply(2), srtt.Multiply(1.5).Add(
 859             QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs / 2)));
 860   }
 861   return QuicTime::Delta::FromMilliseconds(
 862       max(kMinTailLossProbeTimeoutMs,
 863           static_cast<int64>(2 * srtt.ToMilliseconds())));
 864 }
 865
 866 const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const {
 867   QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
 868   if (retransmission_delay.IsZero()) {
 869     // We are in the initial state, use default timeout values.
 870     retransmission_delay =
 871         QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
 872   } else if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
 873     retransmission_delay =
 874         QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
 875   }
 876
 877   // Calculate exponential back off.
 878   retransmission_delay = retransmission_delay.Multiply(
 879       1 << min<size_t>(consecutive_rto_count_, kMaxRetransmissions));
 880
 881   if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
 882     return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
 883   }
 884   return retransmission_delay;
 885 }
 886
 887 const RttStats* QuicSentPacketManager::GetRttStats() const {
 888   return &rtt_stats_;
 889 }
 890
 891 QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const {
 892   // TODO(ianswett): Remove BandwidthEstimate from SendAlgorithmInterface
 893   // and implement the logic here.
 894   return send_algorithm_->BandwidthEstimate();
 895 }
 896
 897 const QuicSustainedBandwidthRecorder&
 898 QuicSentPacketManager::SustainedBandwidthRecorder() const {
 899   return sustained_bandwidth_recorder_;
 900 }
 901
 902 QuicPacketCount QuicSentPacketManager::EstimateMaxPacketsInFlight(
 903     QuicByteCount max_packet_length) const {
 904   return send_algorithm_->GetCongestionWindow() / max_packet_length;
 905 }
 906
 907 QuicPacketCount QuicSentPacketManager::GetCongestionWindowInTcpMss() const {
 908   return send_algorithm_->GetCongestionWindow() / kDefaultTCPMSS;
 909 }
 910
 911 QuicByteCount QuicSentPacketManager::GetCongestionWindowInBytes() const {
 912   return send_algorithm_->GetCongestionWindow();
 913 }
 914
 915 QuicPacketCount QuicSentPacketManager::GetSlowStartThresholdInTcpMss() const {
 916   return send_algorithm_->GetSlowStartThreshold() / kDefaultTCPMSS;
 917 }
 918
 919 void QuicSentPacketManager::OnSerializedPacket(
 920     const SerializedPacket& serialized_packet) {
 921   ack_notifier_manager_.OnSerializedPacket(serialized_packet);
 922 }
 923
 924 void QuicSentPacketManager::CancelRetransmissionsForStream(
 925     QuicStreamId stream_id) {
 926   unacked_packets_.CancelRetransmissionsForStream(stream_id);
 927   PendingRetransmissionMap::iterator it = pending_retransmissions_.begin();
 928   while (it != pending_retransmissions_.end()) {
 929     if (HasRetransmittableFrames(it->first)) {
 930       ++it;
 931       continue;
 932     }
 933     it = pending_retransmissions_.erase(it);
 934   }
 935 }
 936
 937 void QuicSentPacketManager::EnablePacing() {
 938   // TODO(ianswett): Replace with a method which wraps the send algorithm in a
 939   // pacer every time a new algorithm is set.
 940   if (using_pacing_) {
 941     return;
 942   }
 943
 944   // Set up a pacing sender with a 1 millisecond alarm granularity, the same as
 945   // the default granularity of the Linux kernel's FQ qdisc.
 946   using_pacing_ = true;
 947   send_algorithm_.reset(
 948       new PacingSender(send_algorithm_.release(),
 949                        QuicTime::Delta::FromMilliseconds(1),
 950                        kInitialUnpacedBurst));
 951 }
 952
 953 }  // namespace net