net/quic/quic_sent_packet_manager.cc

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