// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "net/quic/quic_sent_packet_manager.h"

#include <algorithm>

#include "base/logging.h"
#include "base/stl_util.h"
#include "net/quic/congestion_control/pacing_sender.h"
#include "net/quic/crypto/crypto_protocol.h"
#include "net/quic/quic_ack_notifier_manager.h"
#include "net/quic/quic_connection_stats.h"
#include "net/quic/quic_flags.h"
#include "net/quic/quic_utils_chromium.h"

using std::make_pair;
using std::max;
using std::min;

namespace net {
namespace {
static const int kDefaultRetransmissionTimeMs = 500;
// TCP RFC calls for 1 second RTO however Linux differs from this default and
// define the minimum RTO to 200ms, we will use the same until we have data to
// support a higher or lower value.
static const int kMinRetransmissionTimeMs = 200;
static const int kMaxRetransmissionTimeMs = 60000;
static const size_t kMaxRetransmissions = 10;

// Only exponentially back off the handshake timer 5 times due to a timeout.
static const size_t kMaxHandshakeRetransmissionBackoffs = 5;
static const size_t kMinHandshakeTimeoutMs = 10;

// Sends up to two tail loss probes before firing an RTO,
// per draft RFC draft-dukkipati-tcpm-tcp-loss-probe.
static const size_t kDefaultMaxTailLossProbes = 2;
static const int64 kMinTailLossProbeTimeoutMs = 10;

bool HasCryptoHandshake(
    const QuicUnackedPacketMap::TransmissionInfo& transmission_info) {
  if (transmission_info.retransmittable_frames == NULL) {
    return false;
  }
  return transmission_info.retransmittable_frames->HasCryptoHandshake() ==
      IS_HANDSHAKE;
}

}  // namespace

#define ENDPOINT (is_server_ ? "Server: " : " Client: ")

QuicSentPacketManager::QuicSentPacketManager(bool is_server,
                                             const QuicClock* clock,
                                             QuicConnectionStats* stats,
                                             CongestionFeedbackType type,
                                             LossDetectionType loss_type)
    : unacked_packets_(),
      is_server_(is_server),
      clock_(clock),
      stats_(stats),
      send_algorithm_(
          SendAlgorithmInterface::Create(clock, &rtt_stats_, type, stats)),
      loss_algorithm_(LossDetectionInterface::Create(loss_type)),
      largest_observed_(0),
      consecutive_rto_count_(0),
      consecutive_tlp_count_(0),
      consecutive_crypto_retransmission_count_(0),
      max_tail_loss_probes_(kDefaultMaxTailLossProbes),
      using_pacing_(false) {
}

QuicSentPacketManager::~QuicSentPacketManager() {
}

void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) {
  if (config.HasReceivedInitialRoundTripTimeUs() &&
      config.ReceivedInitialRoundTripTimeUs() > 0) {
    rtt_stats_.set_initial_rtt_us(min(kMaxInitialRoundTripTimeUs,
                                      config.ReceivedInitialRoundTripTimeUs()));
  }
  if (config.congestion_control() == kPACE) {
    MaybeEnablePacing();
  }
  if (config.HasReceivedLossDetection() &&
      config.ReceivedLossDetection() == kTIME) {
    loss_algorithm_.reset(LossDetectionInterface::Create(kTime));
  }
  send_algorithm_->SetFromConfig(config, is_server_);
}

// TODO(ianswett): Combine this method with OnPacketSent once packets are always
// sent in order and the connection tracks RetransmittableFrames for longer.
void QuicSentPacketManager::OnSerializedPacket(
    const SerializedPacket& serialized_packet) {
  if (serialized_packet.retransmittable_frames) {
    ack_notifier_manager_.OnSerializedPacket(serialized_packet);
  }

  unacked_packets_.AddPacket(serialized_packet);
}

void QuicSentPacketManager::OnRetransmittedPacket(
    QuicPacketSequenceNumber old_sequence_number,
    QuicPacketSequenceNumber new_sequence_number) {
  DCHECK(ContainsKey(pending_retransmissions_, old_sequence_number));

  pending_retransmissions_.erase(old_sequence_number);

  // A notifier may be waiting to hear about ACKs for the original sequence
  // number. Inform them that the sequence number has changed.
  ack_notifier_manager_.UpdateSequenceNumber(old_sequence_number,
                                             new_sequence_number);

  unacked_packets_.OnRetransmittedPacket(old_sequence_number,
                                         new_sequence_number);
}

void QuicSentPacketManager::OnIncomingAck(
    const ReceivedPacketInfo& received_info,
    QuicTime ack_receive_time) {
  // We rely on delta_time_largest_observed to compute an RTT estimate, so
  // we only update rtt when the largest observed gets acked.
  largest_observed_ = received_info.largest_observed;
  bool largest_observed_acked = unacked_packets_.IsUnacked(largest_observed_);
  MaybeUpdateRTT(received_info, ack_receive_time);
  HandleAckForSentPackets(received_info);
  MaybeRetransmitOnAckFrame(received_info, ack_receive_time);

  // Anytime we are making forward progress and have a new RTT estimate, reset
  // the backoff counters.
  if (largest_observed_acked) {
    // Reset all retransmit counters any time a new packet is acked.
    consecutive_rto_count_ = 0;
    consecutive_tlp_count_ = 0;
    consecutive_crypto_retransmission_count_ = 0;
  }
}

void QuicSentPacketManager::DiscardUnackedPacket(
    QuicPacketSequenceNumber sequence_number) {
  MarkPacketHandled(sequence_number, QuicTime::Delta::Zero(),
                    NOT_RECEIVED_BY_PEER);
}

void QuicSentPacketManager::HandleAckForSentPackets(
    const ReceivedPacketInfo& received_info) {
  // Go through the packets we have not received an ack for and see if this
  // incoming_ack shows they've been seen by the peer.
  QuicTime::Delta delta_largest_observed =
      received_info.delta_time_largest_observed;
  QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
  while (it != unacked_packets_.end()) {
    QuicPacketSequenceNumber sequence_number = it->first;
    if (sequence_number > received_info.largest_observed) {
      // These packets are still in flight.
      break;
    }

    if (IsAwaitingPacket(received_info, sequence_number)) {
      // Remove any packets not being tracked by the send algorithm, allowing
      // the high water mark to be raised if necessary.
      if (QuicUnackedPacketMap::IsSentAndNotPending(it->second)) {
        it = MarkPacketHandled(sequence_number, delta_largest_observed,
                               NOT_RECEIVED_BY_PEER);
      } else {
        ++it;
      }
      continue;
    }

    // Packet was acked, so remove it from our unacked packet list.
    DVLOG(1) << ENDPOINT <<"Got an ack for packet " << sequence_number;
    // If data is associated with the most recent transmission of this
    // packet, then inform the caller.
    it = MarkPacketHandled(sequence_number, delta_largest_observed,
                           RECEIVED_BY_PEER);
  }

  // Discard any retransmittable frames associated with revived packets.
  for (SequenceNumberSet::const_iterator revived_it =
           received_info.revived_packets.begin();
       revived_it != received_info.revived_packets.end(); ++revived_it) {
    MarkPacketRevived(*revived_it, delta_largest_observed);
  }

  // If we have received a truncated ack, then we need to
  // clear out some previous transmissions to allow the peer
  // to actually ACK new packets.
  if (received_info.is_truncated) {
    unacked_packets_.ClearPreviousRetransmissions(
        received_info.missing_packets.size() / 2);
  }
}

bool QuicSentPacketManager::HasRetransmittableFrames(
    QuicPacketSequenceNumber sequence_number) const {
  return unacked_packets_.HasRetransmittableFrames(sequence_number);
}

void QuicSentPacketManager::RetransmitUnackedPackets(
    RetransmissionType retransmission_type) {
  QuicUnackedPacketMap::const_iterator unacked_it = unacked_packets_.begin();
  while (unacked_it != unacked_packets_.end()) {
    const RetransmittableFrames* frames =
        unacked_it->second.retransmittable_frames;
    // Only mark it as handled if it can't be retransmitted and there are no
    // pending retransmissions which would be cleared.
    if (frames == NULL && unacked_it->second.all_transmissions->size() == 1 &&
        retransmission_type == ALL_PACKETS) {
      unacked_it = MarkPacketHandled(unacked_it->first, QuicTime::Delta::Zero(),
                                     NOT_RECEIVED_BY_PEER);
      continue;
    }
    // If it had no other transmissions, we handle it above.  If it has
    // other transmissions, one of them must have retransmittable frames,
    // so that gets resolved the same way as other retransmissions.
    // TODO(ianswett): Consider adding a new retransmission type which removes
    // all these old packets from unacked and retransmits them as new sequence
    // numbers with no connection to the previous ones.
    if (frames != NULL && (retransmission_type == ALL_PACKETS ||
                           frames->encryption_level() == ENCRYPTION_INITIAL)) {
      OnPacketAbandoned(unacked_it->first);
      MarkForRetransmission(unacked_it->first, ALL_UNACKED_RETRANSMISSION);
    }
    ++unacked_it;
  }
}

void QuicSentPacketManager::NeuterUnencryptedPackets() {
  QuicUnackedPacketMap::const_iterator unacked_it = unacked_packets_.begin();
  while (unacked_it != unacked_packets_.end()) {
    const RetransmittableFrames* frames =
        unacked_it->second.retransmittable_frames;
    if (frames != NULL && frames->encryption_level() == ENCRYPTION_NONE) {
      // Since once you're forward secure, no unencrypted packets will be sent,
      // crypto or otherwise. Unencrypted packets are neutered and abandoned, to
      // ensure they are not retransmitted or considered lost from a congestion
      // control perspective.
      pending_retransmissions_.erase(unacked_it->first);
      unacked_packets_.NeuterPacket(unacked_it->first);
      OnPacketAbandoned(unacked_it->first);
    }
    ++unacked_it;
  }
}

void QuicSentPacketManager::MarkForRetransmission(
    QuicPacketSequenceNumber sequence_number,
    TransmissionType transmission_type) {
  const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
      unacked_packets_.GetTransmissionInfo(sequence_number);
  LOG_IF(DFATAL, transmission_info.retransmittable_frames == NULL);
  // TODO(ianswett): Currently the RTO can fire while there are pending NACK
  // retransmissions for the same data, which is not ideal.
  if (ContainsKey(pending_retransmissions_, sequence_number)) {
    return;
  }

  pending_retransmissions_[sequence_number] = transmission_type;
}

bool QuicSentPacketManager::HasPendingRetransmissions() const {
  return !pending_retransmissions_.empty();
}

QuicSentPacketManager::PendingRetransmission
    QuicSentPacketManager::NextPendingRetransmission() {
  DCHECK(!pending_retransmissions_.empty());
  QuicPacketSequenceNumber sequence_number =
      pending_retransmissions_.begin()->first;
  TransmissionType transmission_type = pending_retransmissions_.begin()->second;
  if (unacked_packets_.HasPendingCryptoPackets()) {
    // Ensure crypto packets are retransmitted before other packets.
    PendingRetransmissionMap::const_iterator it =
        pending_retransmissions_.begin();
    do {
      if (HasCryptoHandshake(
              unacked_packets_.GetTransmissionInfo(it->first))) {
        sequence_number = it->first;
        transmission_type = it->second;
        break;
      }
      ++it;
    } while (it != pending_retransmissions_.end());
  }
  DCHECK(unacked_packets_.IsUnacked(sequence_number));
  const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
      unacked_packets_.GetTransmissionInfo(sequence_number);
  DCHECK(transmission_info.retransmittable_frames);

  return PendingRetransmission(sequence_number,
                               transmission_type,
                               *transmission_info.retransmittable_frames,
                               transmission_info.sequence_number_length);
}

void QuicSentPacketManager::MarkPacketRevived(
    QuicPacketSequenceNumber sequence_number,
    QuicTime::Delta delta_largest_observed) {
  if (!unacked_packets_.IsUnacked(sequence_number)) {
    return;
  }
  // This packet has been revived at the receiver. If we were going to
  // retransmit it, do not retransmit it anymore.
  pending_retransmissions_.erase(sequence_number);

  const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
      unacked_packets_.GetTransmissionInfo(sequence_number);
  // The AckNotifierManager needs to be notified for revived packets,
  // since it indicates the packet arrived from the appliction's perspective.
  if (transmission_info.retransmittable_frames) {
    ack_notifier_manager_.OnPacketAcked(
        sequence_number, delta_largest_observed);
  }

  if (!transmission_info.pending) {
    unacked_packets_.RemovePacket(sequence_number);
  } else {
    unacked_packets_.NeuterPacket(sequence_number);
  }
}

QuicUnackedPacketMap::const_iterator QuicSentPacketManager::MarkPacketHandled(
    QuicPacketSequenceNumber sequence_number,
    QuicTime::Delta delta_largest_observed, ReceivedByPeer received_by_peer) {
  if (!unacked_packets_.IsUnacked(sequence_number)) {
    LOG(DFATAL) << "Packet is not unacked: " << sequence_number;
    return unacked_packets_.end();
  }
  const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
      unacked_packets_.GetTransmissionInfo(sequence_number);
  // If this packet is pending, remove it and inform the send algorithm.
  if (transmission_info.pending) {
    if (received_by_peer == RECEIVED_BY_PEER) {
      send_algorithm_->OnPacketAcked(sequence_number,
                                     transmission_info.bytes_sent);
    } else {
      // It's been abandoned.
      send_algorithm_->OnPacketAbandoned(sequence_number,
                                         transmission_info.bytes_sent);
    }
    unacked_packets_.SetNotPending(sequence_number);
  }

  SequenceNumberSet all_transmissions = *transmission_info.all_transmissions;
  SequenceNumberSet::reverse_iterator all_transmissions_it =
      all_transmissions.rbegin();
  QuicPacketSequenceNumber newest_transmission = *all_transmissions_it;
  if (newest_transmission != sequence_number) {
    stats_->bytes_spuriously_retransmitted += transmission_info.bytes_sent;
    ++stats_->packets_spuriously_retransmitted;
  }

  // The AckNotifierManager needs to be notified about the most recent
  // transmission, since that's the one only one it tracks.
  ack_notifier_manager_.OnPacketAcked(newest_transmission,
                                      delta_largest_observed);

  bool has_crypto_handshake = HasCryptoHandshake(
      unacked_packets_.GetTransmissionInfo(newest_transmission));
  while (all_transmissions_it != all_transmissions.rend()) {
    QuicPacketSequenceNumber previous_transmission = *all_transmissions_it;
    const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
        unacked_packets_.GetTransmissionInfo(previous_transmission);
    // If this packet was marked for retransmission, don't bother retransmitting
    // it anymore.
    pending_retransmissions_.erase(previous_transmission);
    if (has_crypto_handshake) {
      // If it's a crypto handshake packet, discard it and all retransmissions,
      // since they won't be acked now that one has been processed.
      if (transmission_info.pending) {
        OnPacketAbandoned(previous_transmission);
      }
      unacked_packets_.SetNotPending(previous_transmission);
    }
    if (!transmission_info.pending) {
      unacked_packets_.RemovePacket(previous_transmission);
    } else {
      unacked_packets_.NeuterPacket(previous_transmission);
    }
    ++all_transmissions_it;
  }

  QuicUnackedPacketMap::const_iterator next_unacked = unacked_packets_.begin();
  while (next_unacked != unacked_packets_.end() &&
         next_unacked->first < sequence_number) {
    ++next_unacked;
  }
  return next_unacked;
}

bool QuicSentPacketManager::IsUnacked(
    QuicPacketSequenceNumber sequence_number) const {
  return unacked_packets_.IsUnacked(sequence_number);
}

bool QuicSentPacketManager::HasUnackedPackets() const {
  return unacked_packets_.HasUnackedPackets();
}

QuicPacketSequenceNumber
QuicSentPacketManager::GetLeastUnackedSentPacket() const {
  return unacked_packets_.GetLeastUnackedSentPacket();
}

bool QuicSentPacketManager::OnPacketSent(
    QuicPacketSequenceNumber sequence_number,
    QuicTime sent_time,
    QuicByteCount bytes,
    TransmissionType transmission_type,
    HasRetransmittableData has_retransmittable_data) {
  DCHECK_LT(0u, sequence_number);
  LOG_IF(DFATAL, bytes == 0) << "Cannot send empty packets.";
  // In rare circumstances, the packet could be serialized, sent, and then acked
  // before OnPacketSent is called.
  if (!unacked_packets_.IsUnacked(sequence_number)) {
    return false;
  }

  // Only track packets as pending that the send algorithm wants us to track.
  if (!send_algorithm_->OnPacketSent(sent_time, sequence_number, bytes,
                                     has_retransmittable_data)) {
    unacked_packets_.SetSent(sequence_number, sent_time, bytes, false);
    // Do not reset the retransmission timer, since the packet isn't tracked.
    return false;
  }

  const bool set_retransmission_timer = !unacked_packets_.HasPendingPackets();

  unacked_packets_.SetSent(sequence_number, sent_time, bytes, true);

  // Reset the retransmission timer anytime a packet is sent in tail loss probe
  // mode or before the crypto handshake has completed.
  return set_retransmission_timer || GetRetransmissionMode() != RTO_MODE;
}

void QuicSentPacketManager::OnRetransmissionTimeout() {
  DCHECK(unacked_packets_.HasPendingPackets());
  // Handshake retransmission, timer based loss detection, TLP, and RTO are
  // implemented with a single alarm. The handshake alarm is set when the
  // handshake has not completed, the loss alarm is set when the loss detection
  // algorithm says to, and the TLP and  RTO alarms are set after that.
  // The TLP alarm is always set to run for under an RTO.
  switch (GetRetransmissionMode()) {
    case HANDSHAKE_MODE:
      ++stats_->crypto_retransmit_count;
      RetransmitCryptoPackets();
      return;
    case LOSS_MODE:
      ++stats_->loss_timeout_count;
      InvokeLossDetection(clock_->Now());
      return;
    case TLP_MODE:
      // If no tail loss probe can be sent, because there are no retransmittable
      // packets, execute a conventional RTO to abandon old packets.
      ++stats_->tlp_count;
      RetransmitOldestPacket();
      return;
    case RTO_MODE:
      ++stats_->rto_count;
      RetransmitAllPackets();
      return;
  }
}

void QuicSentPacketManager::RetransmitCryptoPackets() {
  DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode());
  // TODO(ianswett): Typical TCP implementations only retransmit 5 times.
  consecutive_crypto_retransmission_count_ =
      min(kMaxHandshakeRetransmissionBackoffs,
          consecutive_crypto_retransmission_count_ + 1);
  bool packet_retransmitted = false;
  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
       it != unacked_packets_.end(); ++it) {
    QuicPacketSequenceNumber sequence_number = it->first;
    const RetransmittableFrames* frames = it->second.retransmittable_frames;
    // Only retransmit frames which are pending, and therefore have been sent.
    if (!it->second.pending || frames == NULL ||
        frames->HasCryptoHandshake() != IS_HANDSHAKE) {
      continue;
    }
    packet_retransmitted = true;
    MarkForRetransmission(sequence_number, HANDSHAKE_RETRANSMISSION);
    // Abandon all the crypto retransmissions now so they're not lost later.
    OnPacketAbandoned(sequence_number);
  }
  DCHECK(packet_retransmitted) << "No crypto packets found to retransmit.";
}

void QuicSentPacketManager::RetransmitOldestPacket() {
  DCHECK_EQ(TLP_MODE, GetRetransmissionMode());
  ++consecutive_tlp_count_;
  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
       it != unacked_packets_.end(); ++it) {
    QuicPacketSequenceNumber sequence_number = it->first;
    const RetransmittableFrames* frames = it->second.retransmittable_frames;
    // Only retransmit frames which are pending, and therefore have been sent.
    if (!it->second.pending || frames == NULL) {
      continue;
    }
    DCHECK_NE(IS_HANDSHAKE, frames->HasCryptoHandshake());
    MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
    return;
  }
  DLOG(FATAL)
    << "No retransmittable packets, so RetransmitOldestPacket failed.";
}

void QuicSentPacketManager::RetransmitAllPackets() {
  // Abandon all retransmittable packets and packets older than the
  // retransmission delay.

  DVLOG(1) << "OnRetransmissionTimeout() fired with "
           << unacked_packets_.GetNumUnackedPackets() << " unacked packets.";

  // Request retransmission of all retransmittable packets when the RTO
  // fires, and let the congestion manager decide how many to send
  // immediately and the remaining packets will be queued.
  // Abandon any non-retransmittable packets that are sufficiently old.
  bool packets_retransmitted = false;
  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
       it != unacked_packets_.end(); ++it) {
    unacked_packets_.SetNotPending(it->first);
    if (it->second.retransmittable_frames != NULL) {
      packets_retransmitted = true;
      MarkForRetransmission(it->first, RTO_RETRANSMISSION);
    }
  }

  send_algorithm_->OnRetransmissionTimeout(packets_retransmitted);
  if (packets_retransmitted) {
    ++consecutive_rto_count_;
  }
}

QuicSentPacketManager::RetransmissionTimeoutMode
    QuicSentPacketManager::GetRetransmissionMode() const {
  DCHECK(unacked_packets_.HasPendingPackets());
  if (unacked_packets_.HasPendingCryptoPackets()) {
    return HANDSHAKE_MODE;
  }
  if (loss_algorithm_->GetLossTimeout() != QuicTime::Zero()) {
    return LOSS_MODE;
  }
  if (consecutive_tlp_count_ < max_tail_loss_probes_) {
    if (unacked_packets_.HasUnackedRetransmittableFrames()) {
      return TLP_MODE;
    }
  }
  return RTO_MODE;
}

void QuicSentPacketManager::OnPacketAbandoned(
    QuicPacketSequenceNumber sequence_number) {
  const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
      unacked_packets_.GetTransmissionInfo(sequence_number);
  if (transmission_info.pending) {
    LOG_IF(DFATAL, transmission_info.bytes_sent == 0);
    send_algorithm_->OnPacketAbandoned(sequence_number,
                                       transmission_info.bytes_sent);
    unacked_packets_.SetNotPending(sequence_number);
  }
}

void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame(
    const QuicCongestionFeedbackFrame& frame,
    const QuicTime& feedback_receive_time) {
  send_algorithm_->OnIncomingQuicCongestionFeedbackFrame(
      frame, feedback_receive_time);
}

void QuicSentPacketManager::MaybeRetransmitOnAckFrame(
    const ReceivedPacketInfo& received_info,
    const QuicTime& ack_receive_time) {
  // Go through all pending packets up to the largest observed and count nacks.
  for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
       it != unacked_packets_.end() &&
           it->first <= received_info.largest_observed; ++it) {
    if (!it->second.pending) {
      continue;
    }
    QuicPacketSequenceNumber sequence_number = it->first;
    DVLOG(1) << "still missing packet " << sequence_number;
    // Acks must be handled previously, so ensure it's missing and not acked.
    DCHECK(IsAwaitingPacket(received_info, sequence_number));

    // Consider it multiple nacks when there is a gap between the missing packet
    // and the largest observed, since the purpose of a nack threshold is to
    // tolerate re-ordering.  This handles both StretchAcks and Forward Acks.
    // The nack count only increases when the largest observed increases.
    size_t min_nacks = received_info.largest_observed - sequence_number;
    // Truncated acks can nack the largest observed, so set the nack count to 1.
    if (min_nacks == 0) {
      min_nacks = 1;
    }
    unacked_packets_.NackPacket(sequence_number, min_nacks);
  }

  InvokeLossDetection(ack_receive_time);
}

void QuicSentPacketManager::InvokeLossDetection(QuicTime time) {
  SequenceNumberSet lost_packets =
      loss_algorithm_->DetectLostPackets(unacked_packets_,
                                         time,
                                         largest_observed_,
                                         rtt_stats_);
  for (SequenceNumberSet::const_iterator it = lost_packets.begin();
       it != lost_packets.end(); ++it) {
    QuicPacketSequenceNumber sequence_number = *it;
    // TODO(ianswett): If it's expected the FEC packet may repair the loss, it
    // should be recorded as a loss to the send algorithm, but not retransmitted
    // until it's known whether the FEC packet arrived.
    ++stats_->packets_lost;
    send_algorithm_->OnPacketLost(sequence_number, time);
    OnPacketAbandoned(sequence_number);

    if (unacked_packets_.HasRetransmittableFrames(sequence_number)) {
      MarkForRetransmission(sequence_number, LOSS_RETRANSMISSION);
    } else {
      // Since we will not retransmit this, we need to remove it from
      // unacked_packets_.   This is either the current transmission of
      // a packet whose previous transmission has been acked, or it
      // is a packet that has been TLP retransmitted.
      unacked_packets_.RemovePacket(sequence_number);
    }
  }
}

void QuicSentPacketManager::MaybeUpdateRTT(
    const ReceivedPacketInfo& received_info,
    const QuicTime& ack_receive_time) {
  if (!unacked_packets_.IsUnacked(received_info.largest_observed)) {
    return;
  }
  // We calculate the RTT based on the highest ACKed sequence number, the lower
  // sequence numbers will include the ACK aggregation delay.
  const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
      unacked_packets_.GetTransmissionInfo(received_info.largest_observed);
  // Don't update the RTT if it hasn't been sent.
  if (transmission_info.sent_time == QuicTime::Zero()) {
    return;
  }

  QuicTime::Delta send_delta =
      ack_receive_time.Subtract(transmission_info.sent_time);
  rtt_stats_.UpdateRtt(
      send_delta, received_info.delta_time_largest_observed, ack_receive_time);
  send_algorithm_->OnRttUpdated(received_info.largest_observed);
}

QuicTime::Delta QuicSentPacketManager::TimeUntilSend(
    QuicTime now,
    TransmissionType transmission_type,
    HasRetransmittableData retransmittable) {
  // The TLP logic is entirely contained within QuicSentPacketManager, so the
  // send algorithm does not need to be consulted.
  if (transmission_type == TLP_RETRANSMISSION) {
    return QuicTime::Delta::Zero();
  }
  return send_algorithm_->TimeUntilSend(now, retransmittable);
}

// Ensures that the Delayed Ack timer is always set to a value lesser
// than the retransmission timer's minimum value (MinRTO). We want the
// delayed ack to get back to the QUIC peer before the sender's
// retransmission timer triggers.  Since we do not know the
// reverse-path one-way delay, we assume equal delays for forward and
// reverse paths, and ensure that the timer is set to less than half
// of the MinRTO.
// There may be a value in making this delay adaptive with the help of
// the sender and a signaling mechanism -- if the sender uses a
// different MinRTO, we may get spurious retransmissions. May not have
// any benefits, but if the delayed ack becomes a significant source
// of (likely, tail) latency, then consider such a mechanism.
const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() const {
  return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2);
}

const QuicTime QuicSentPacketManager::GetRetransmissionTime() const {
  // Don't set the timer if there are no pending packets.
  if (!unacked_packets_.HasPendingPackets()) {
    return QuicTime::Zero();
  }
  switch (GetRetransmissionMode()) {
    case HANDSHAKE_MODE:
      return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay());
    case LOSS_MODE:
      return loss_algorithm_->GetLossTimeout();
    case TLP_MODE: {
      // TODO(ianswett): When CWND is available, it would be preferable to
      // set the timer based on the earliest retransmittable packet.
      // Base the updated timer on the send time of the last packet.
      const QuicTime sent_time = unacked_packets_.GetLastPacketSentTime();
      const QuicTime tlp_time = sent_time.Add(GetTailLossProbeDelay());
      // Ensure the tlp timer never gets set to a time in the past.
      return QuicTime::Max(clock_->ApproximateNow(), tlp_time);
    }
    case RTO_MODE: {
      // The RTO is based on the first pending packet.
      const QuicTime sent_time =
          unacked_packets_.GetFirstPendingPacketSentTime();
      QuicTime rto_timeout = sent_time.Add(GetRetransmissionDelay());
      // Always wait at least 1.5 * RTT from now.
      QuicTime min_timeout = clock_->ApproximateNow().Add(
          rtt_stats_.SmoothedRtt().Multiply(1.5));

      return QuicTime::Max(min_timeout, rto_timeout);
    }
  }
  DCHECK(false);
  return QuicTime::Zero();
}

const QuicTime::Delta QuicSentPacketManager::GetCryptoRetransmissionDelay()
    const {
  // This is equivalent to the TailLossProbeDelay, but slightly more aggressive
  // because crypto handshake messages don't incur a delayed ack time.
  int64 delay_ms = max<int64>(kMinHandshakeTimeoutMs,
                              1.5 * rtt_stats_.SmoothedRtt().ToMilliseconds());
  return QuicTime::Delta::FromMilliseconds(
      delay_ms << consecutive_crypto_retransmission_count_);
}

const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const {
  QuicTime::Delta srtt = rtt_stats_.SmoothedRtt();
  if (!unacked_packets_.HasMultiplePendingPackets()) {
    return QuicTime::Delta::Max(
        srtt.Multiply(1.5).Add(DelayedAckTime()), srtt.Multiply(2));
  }
  return QuicTime::Delta::FromMilliseconds(
      max(kMinTailLossProbeTimeoutMs,
          static_cast<int64>(2 * srtt.ToMilliseconds())));
}

const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const {
  QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
  // TODO(rch): This code should move to |send_algorithm_|.
  if (retransmission_delay.IsZero()) {
    // We are in the initial state, use default timeout values.
    retransmission_delay =
        QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
  } else if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
    retransmission_delay =
        QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
  }

  // Calculate exponential back off.
  retransmission_delay = retransmission_delay.Multiply(
      1 << min<size_t>(consecutive_rto_count_, kMaxRetransmissions));

  if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
    return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
  }
  return retransmission_delay;
}

const RttStats* QuicSentPacketManager::GetRttStats() const {
  return &rtt_stats_;
}

QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const {
  return send_algorithm_->BandwidthEstimate();
}

QuicByteCount QuicSentPacketManager::GetCongestionWindow() const {
  return send_algorithm_->GetCongestionWindow();
}

void QuicSentPacketManager::MaybeEnablePacing() {
  if (!FLAGS_enable_quic_pacing) {
    return;
  }

  if (using_pacing_) {
    return;
  }

  using_pacing_ = true;
  send_algorithm_.reset(
      new PacingSender(send_algorithm_.release(),
                       QuicTime::Delta::FromMicroseconds(1)));
}

}  // namespace net