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