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