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