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