// Copyright 2014 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/send_algorithm_simulator.h"

#include <limits>

#include "base/logging.h"
#include "base/rand_util.h"
#include "net/quic/crypto/quic_random.h"

using std::list;
using std::max;
using std::min;

namespace net {

namespace {

const QuicByteCount kPacketSize = 1200;

}  // namespace

SendAlgorithmSimulator::SendAlgorithmSimulator(
    SendAlgorithmInterface* send_algorithm,
    MockClock* clock,
    RttStats* rtt_stats,
    QuicBandwidth bandwidth,
    QuicTime::Delta rtt)
    : send_algorithm_(send_algorithm),
      clock_(clock),
      rtt_stats_(rtt_stats),
      next_sent_(1),
      last_acked_(0),
      next_acked_(1),
      lose_next_ack_(false),
      bytes_in_flight_(0),
      forward_loss_rate_(0),
      reverse_loss_rate_(0),
      loss_correlation_(0),
      bandwidth_(bandwidth),
      rtt_(rtt),
      buffer_size_(1000000),
      max_cwnd_(0),
      min_cwnd_(100000),
      max_cwnd_drop_(0),
      last_cwnd_(0) {
  uint32 seed = base::RandInt(0, std::numeric_limits<int32>::max());
  DVLOG(1) << "Seeding SendAlgorithmSimulator with " << seed;
  simple_random_.set_seed(seed);
}

SendAlgorithmSimulator::~SendAlgorithmSimulator() {}

// Sends the specified number of bytes as quickly as possible and returns the
// average bandwidth in bytes per second.  The time elapsed is based on
// waiting for all acks to arrive.
QuicBandwidth SendAlgorithmSimulator::SendBytes(size_t num_bytes) {
  const QuicTime start_time = clock_->Now();
  size_t bytes_acked = 0;
  while (bytes_acked < num_bytes) {
    DVLOG(1) << "bytes_acked:" << bytes_acked << " bytes_in_flight_:"
             << bytes_in_flight_ << " CWND(bytes):"
             << send_algorithm_->GetCongestionWindow();
    // Determine the times of next send and of the next ack arrival.
    QuicTime::Delta send_delta = send_algorithm_->TimeUntilSend(
        clock_->Now(), bytes_in_flight_, HAS_RETRANSMITTABLE_DATA);
    // If we've already sent enough bytes, wait for them to be acked.
    if (bytes_acked + bytes_in_flight_ >= num_bytes) {
      send_delta = QuicTime::Delta::Infinite();
    }
    QuicTime::Delta ack_delta = NextAckDelta();
    // If both times are infinite, fire a TLP.
    if (ack_delta.IsInfinite() && send_delta.IsInfinite()) {
      DVLOG(1) << "Both times are infinite, simulating a TLP.";
      // TODO(ianswett): Use a more sophisticated TLP timer.
      clock_->AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
      SendDataNow();
    } else if (ack_delta < send_delta) {
      DVLOG(1) << "Handling ack, advancing time:"
               << ack_delta.ToMicroseconds() << "us";
      // Ack data all the data up to ack time and lose any missing sequence
      // numbers.
      clock_->AdvanceTime(ack_delta);
      bytes_acked += HandlePendingAck();
    } else {
      DVLOG(1) << "Sending, advancing time:"
               << send_delta.ToMicroseconds() << "us";
      clock_->AdvanceTime(send_delta);
      SendDataNow();
    }
    RecordStats();
  }
  return QuicBandwidth::FromBytesAndTimeDelta(
      num_bytes, clock_->Now().Subtract(start_time));
}

// NextAck takes into account packet loss in both forward and reverse
// direction, as well as correlated losses.  And it assumes the receiver acks
// every other packet when there is no loss.
QuicTime::Delta SendAlgorithmSimulator::NextAckDelta() {
  if (sent_packets_.empty() || AllPacketsLost()) {
    DVLOG(1) << "No outstanding packets to cause acks. sent_packets_.size():"
             << sent_packets_.size();
    return QuicTime::Delta::Infinite();
  }

  // If necessary, determine next_acked_.
  // This is only done once to ensure multiple calls return the same time.
  FindNextAcked();

  // If only one packet is acked, simulate a delayed ack.
  if (next_acked_ - last_acked_ == 1) {
    return sent_packets_.front().ack_time.Add(
        QuicTime::Delta::FromMilliseconds(100)).Subtract(clock_->Now());
  }
  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
       it != sent_packets_.end(); ++it) {
    if (next_acked_ == it->sequence_number) {
      return it->ack_time.Subtract(clock_->Now());
    }
  }
  LOG(DFATAL) << "Error, next_acked_: " << next_acked_
              << " should have been found in sent_packets_";
  return QuicTime::Delta::Infinite();
}

bool SendAlgorithmSimulator::AllPacketsLost() {
  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
       it != sent_packets_.end(); ++it) {
    if (it->ack_time.IsInitialized()) {
      return false;
    }
  }
  return true;
}

void SendAlgorithmSimulator::FindNextAcked() {
  // TODO(ianswett): Add a simpler mode which acks every packet.
  bool packets_lost = false;
  if (next_acked_ == last_acked_) {
    // Determine if the next ack is lost only once, to ensure determinism.
    lose_next_ack_ =
        reverse_loss_rate_ * kuint64max > simple_random_.RandUint64();
  }
  bool two_acks_remaining = lose_next_ack_;
  next_acked_ = last_acked_;
  // Remove any packets that are simulated as lost.
  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
      it != sent_packets_.end(); ++it) {
    // Lost packets don't trigger an ack.
    if (it->ack_time  == QuicTime::Zero()) {
      packets_lost = true;
      continue;
    }
    // Buffer dropped packets are skipped automatically, but still end up
    // being lost and cause acks to be sent immediately.
    if (next_acked_ < it->sequence_number - 1) {
      packets_lost = true;
    }
    next_acked_ = it->sequence_number;
    if (packets_lost || (next_acked_ - last_acked_) % 2 == 0) {
      if (two_acks_remaining) {
        two_acks_remaining = false;
      } else {
        break;
      }
    }
  }
  DVLOG(1) << "FindNextAcked found next_acked_:" << next_acked_
           << " last_acked:" << last_acked_;
}

int SendAlgorithmSimulator::HandlePendingAck() {
  DCHECK_LT(last_acked_, next_acked_);
  SendAlgorithmInterface::CongestionMap acked_packets;
  SendAlgorithmInterface::CongestionMap lost_packets;
  // Some entries may be missing from the sent_packets_ array, if they were
  // dropped due to buffer overruns.
  SentPacket largest_observed = sent_packets_.front();
  while (last_acked_ < next_acked_) {
    ++last_acked_;
    TransmissionInfo info = TransmissionInfo();
    info.bytes_sent = kPacketSize;
    info.in_flight = true;
    // If it's missing from the array, it's a loss.
    if (sent_packets_.front().sequence_number > last_acked_) {
      DVLOG(1) << "Lost packet:" << last_acked_
               << " dropped by buffer overflow.";
      lost_packets[last_acked_] = info;
      continue;
    }
    if (sent_packets_.front().ack_time.IsInitialized()) {
      acked_packets[last_acked_] = info;
    } else {
      lost_packets[last_acked_] = info;
    }
    // Remove all packets from the front to next_acked_.
    largest_observed = sent_packets_.front();
    sent_packets_.pop_front();
  }

  DCHECK(largest_observed.ack_time.IsInitialized());
  rtt_stats_->UpdateRtt(
      largest_observed.ack_time.Subtract(largest_observed.send_time),
      QuicTime::Delta::Zero(),
      clock_->Now());
  send_algorithm_->OnCongestionEvent(
      true, bytes_in_flight_, acked_packets, lost_packets);
  DCHECK_LE(kPacketSize * (acked_packets.size() + lost_packets.size()),
            bytes_in_flight_);
  bytes_in_flight_ -=
      kPacketSize * (acked_packets.size() + lost_packets.size());
  return acked_packets.size() * kPacketSize;
}

void SendAlgorithmSimulator::SendDataNow() {
  DVLOG(1) << "Sending packet:" << next_sent_ << " bytes_in_flight:"
           << bytes_in_flight_;
  send_algorithm_->OnPacketSent(
      clock_->Now(), bytes_in_flight_,
      next_sent_, kPacketSize, HAS_RETRANSMITTABLE_DATA);
  // Lose the packet immediately if the buffer is full.
  if (sent_packets_.size() * kPacketSize < buffer_size_) {
    // TODO(ianswett): This buffer simulation is an approximation.
    // An ack time of zero means loss.
    bool packet_lost =
        forward_loss_rate_ * kuint64max > simple_random_.RandUint64();
    // Handle correlated loss.
    if (!sent_packets_.empty() &&
        !sent_packets_.back().ack_time.IsInitialized() &&
        loss_correlation_ * kuint64max > simple_random_.RandUint64()) {
      packet_lost = true;
    }

    QuicTime ack_time = clock_->Now().Add(rtt_);
    // If the number of bytes in flight are less than the bdp, there's
    // no buffering delay.  Bytes lost from the buffer are not counted.
    QuicByteCount bdp = bandwidth_.ToBytesPerPeriod(rtt_);
    if (sent_packets_.size() * kPacketSize > bdp) {
      QuicByteCount qsize = sent_packets_.size() * kPacketSize - bdp;
      ack_time = ack_time.Add(bandwidth_.TransferTime(qsize));
    }
    // If the packet is lost, give it an ack time of Zero.
    sent_packets_.push_back(SentPacket(
        next_sent_, clock_->Now(), packet_lost ? QuicTime::Zero() : ack_time));
  }
  ++next_sent_;
  bytes_in_flight_ += kPacketSize;
}

void SendAlgorithmSimulator::RecordStats() {
  QuicByteCount cwnd = send_algorithm_->GetCongestionWindow();
  max_cwnd_ = max(max_cwnd_, cwnd);
  min_cwnd_ = min(min_cwnd_, cwnd);
  if (last_cwnd_ > cwnd) {
    max_cwnd_drop_ = max(max_cwnd_drop_, last_cwnd_ - cwnd);
  }
  last_cwnd_ = cwnd;
}

// Advance the time by |delta| without sending anything.
void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) {
  clock_->AdvanceTime(delta);
}

// Elapsed time from the start of the connection.
QuicTime SendAlgorithmSimulator::ElapsedTime() {
  return clock_->Now();
}

}  // namespace net