// Copyright (c) 2012 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/congestion_control/quic_congestion_manager.h"

#include <algorithm>
#include <map>

#include "base/stl_util.h"
#include "net/quic/congestion_control/receive_algorithm_interface.h"
#include "net/quic/congestion_control/send_algorithm_interface.h"

namespace {
static const int kBitrateSmoothingPeriodMs = 1000;
static const int kHistoryPeriodMs = 5000;

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;
static const size_t kTailDropWindowSize = 5;
static const size_t kTailDropMaxRetransmissions = 4;

COMPILE_ASSERT(kHistoryPeriodMs >= kBitrateSmoothingPeriodMs,
               history_must_be_longer_or_equal_to_the_smoothing_period);
}  // namespace

using std::map;
using std::min;

namespace net {

QuicCongestionManager::QuicCongestionManager(
    const QuicClock* clock,
    CongestionFeedbackType type)
    : clock_(clock),
      receive_algorithm_(ReceiveAlgorithmInterface::Create(clock, type)),
      send_algorithm_(SendAlgorithmInterface::Create(clock, type)),
      largest_missing_(0),
      current_rtt_(QuicTime::Delta::Infinite()) {
}

QuicCongestionManager::~QuicCongestionManager() {
  STLDeleteValues(&packet_history_map_);
}

void QuicCongestionManager::SentPacket(QuicPacketSequenceNumber sequence_number,
                                       QuicTime sent_time,
                                       QuicByteCount bytes,
                                       Retransmission retransmission) {
  DCHECK(!ContainsKey(pending_packets_, sequence_number));
  send_algorithm_->SentPacket(sent_time, sequence_number, bytes,
                              retransmission);

  packet_history_map_[sequence_number] =
      new class SendAlgorithmInterface::SentPacket(bytes, sent_time);
  pending_packets_[sequence_number] = bytes;
  CleanupPacketHistory();
}

// Called when a packet is timed out.
void QuicCongestionManager::AbandoningPacket(
    QuicPacketSequenceNumber sequence_number) {
  PendingPacketsMap::iterator it = pending_packets_.find(sequence_number);
  if (it != pending_packets_.end()) {
    // Shouldn't this report loss as well? (decrease cgst window).
    send_algorithm_->AbandoningPacket(sequence_number, it->second);
    pending_packets_.erase(it);
  }
}

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

void QuicCongestionManager::OnIncomingAckFrame(const QuicAckFrame& frame,
                                               QuicTime ack_receive_time) {
  // We calculate the RTT based on the highest ACKed sequence number, the lower
  // sequence numbers will include the ACK aggregation delay.
  SendAlgorithmInterface::SentPacketsMap::iterator history_it =
      packet_history_map_.find(frame.received_info.largest_observed);
  // TODO(satyamshekhar): largest_observed might be missing.
  if (history_it != packet_history_map_.end() &&
      !frame.received_info.delta_time_largest_observed.IsInfinite()) {
    QuicTime::Delta send_delta = ack_receive_time.Subtract(
        history_it->second->SendTimestamp());
    if (send_delta > frame.received_info.delta_time_largest_observed) {
      current_rtt_ = send_delta.Subtract(
          frame.received_info.delta_time_largest_observed);
    }
  }
  // We want to.
  // * Get all packets lower(including) than largest_observed
  //   from pending_packets_.
  // * Remove all missing packets.
  // * Send each ACK in the list to send_algorithm_.
  PendingPacketsMap::iterator it, it_upper;
  it = pending_packets_.begin();
  it_upper = pending_packets_.upper_bound(frame.received_info.largest_observed);

  bool new_packet_loss_reported = false;
  while (it != it_upper) {
    QuicPacketSequenceNumber sequence_number = it->first;
    if (!IsAwaitingPacket(frame.received_info, sequence_number)) {
      // Not missing, hence implicitly acked.
      send_algorithm_->OnIncomingAck(sequence_number, it->second, current_rtt_);
      pending_packets_.erase(it++);  // Must be incremented post to work.
    } else {
      if (sequence_number > largest_missing_) {
        // We have a new loss reported.
        new_packet_loss_reported = true;
        largest_missing_ = sequence_number;
      }
      ++it;
    }
  }
  if (new_packet_loss_reported) {
    send_algorithm_->OnIncomingLoss(ack_receive_time);
  }
}

QuicTime::Delta QuicCongestionManager::TimeUntilSend(
    QuicTime now,
    Retransmission retransmission,
    HasRetransmittableData retransmittable,
    IsHandshake handshake) {
  return send_algorithm_->TimeUntilSend(now, retransmission, retransmittable,
                                        handshake);
}

bool QuicCongestionManager::GenerateCongestionFeedback(
    QuicCongestionFeedbackFrame* feedback) {
  return receive_algorithm_->GenerateCongestionFeedback(feedback);
}

void QuicCongestionManager::RecordIncomingPacket(
    QuicByteCount bytes,
    QuicPacketSequenceNumber sequence_number,
    QuicTime timestamp,
    bool revived) {
  receive_algorithm_->RecordIncomingPacket(bytes, sequence_number, timestamp,
                                           revived);
}

const QuicTime::Delta QuicCongestionManager::rtt() {
  return current_rtt_;
}

const QuicTime::Delta QuicCongestionManager::DefaultRetransmissionTime() {
  return QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
}

const QuicTime::Delta QuicCongestionManager::GetRetransmissionDelay(
    size_t unacked_packets_count,
    size_t number_retransmissions) {
  QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
  if (retransmission_delay.IsZero()) {
    // We are in the initial state, use default timeout values.
    if (unacked_packets_count <= kTailDropWindowSize) {
      if (number_retransmissions <= kTailDropMaxRetransmissions) {
        return QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
      }
      number_retransmissions -= kTailDropMaxRetransmissions;
    }
    retransmission_delay =
        QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
  }
  // Calcluate exponential back off.
  retransmission_delay = QuicTime::Delta::FromMilliseconds(
      retransmission_delay.ToMilliseconds() * static_cast<size_t>(
          (1 << min<size_t>(number_retransmissions, kMaxRetransmissions))));

  // TODO(rch): This code should move to |send_algorithm_|.
  if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
    return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
  }
  if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
    return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
  }
  return retransmission_delay;
}

const QuicTime::Delta QuicCongestionManager::SmoothedRtt() {
  return send_algorithm_->SmoothedRtt();
}

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

void QuicCongestionManager::CleanupPacketHistory() {
  const QuicTime::Delta kHistoryPeriod =
      QuicTime::Delta::FromMilliseconds(kHistoryPeriodMs);
  QuicTime now = clock_->ApproximateNow();

  SendAlgorithmInterface::SentPacketsMap::iterator history_it =
      packet_history_map_.begin();
  for (; history_it != packet_history_map_.end(); ++history_it) {
    if (now.Subtract(history_it->second->SendTimestamp()) <= kHistoryPeriod) {
      return;
    }
    delete history_it->second;
    packet_history_map_.erase(history_it);
    history_it = packet_history_map_.begin();
  }
}

}  // namespace net