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