// Copyright 2016 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 "quiche/quic/core/congestion_control/bandwidth_sampler.h"

#include <algorithm>
#include <cstdint>
#include <set>
#include <string>

#include "quiche/quic/core/quic_bandwidth.h"
#include "quiche/quic/core/quic_time.h"
#include "quiche/quic/core/quic_types.h"
#include "quiche/quic/platform/api/quic_flags.h"
#include "quiche/quic/platform/api/quic_logging.h"
#include "quiche/quic/platform/api/quic_test.h"
#include "quiche/quic/test_tools/mock_clock.h"

namespace quic {
namespace test {

class BandwidthSamplerPeer {
 public:
  static size_t GetNumberOfTrackedPackets(const BandwidthSampler& sampler) {
    return sampler.connection_state_map_.number_of_present_entries();
  }

  static QuicByteCount GetPacketSize(const BandwidthSampler& sampler,
                                     QuicPacketNumber packet_number) {
    return sampler.connection_state_map_.GetEntry(packet_number)->size();
  }
};

const QuicByteCount kRegularPacketSize = 1280;
// Enforce divisibility for some of the tests.
static_assert((kRegularPacketSize & 31) == 0,
              "kRegularPacketSize has to be five times divisible by 2");

struct TestParameters {
  bool overestimate_avoidance;
};

// Used by ::testing::PrintToStringParamName().
std::string PrintToString(const TestParameters& p) {
  return p.overestimate_avoidance ? "enable_overestimate_avoidance"
                                  : "no_enable_overestimate_avoidance";
}

// A test fixture with utility methods for BandwidthSampler tests.
class BandwidthSamplerTest : public QuicTestWithParam<TestParameters> {
 protected:
  BandwidthSamplerTest()
      : sampler_(nullptr, /*max_height_tracker_window_length=*/0),
        sampler_app_limited_at_start_(sampler_.is_app_limited()),
        bytes_in_flight_(0),
        max_bandwidth_(QuicBandwidth::Zero()),
        est_bandwidth_upper_bound_(QuicBandwidth::Infinite()),
        round_trip_count_(0) {
    // Ensure that the clock does not start at zero.
    clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));
    if (GetParam().overestimate_avoidance) {
      sampler_.EnableOverestimateAvoidance();
    }
  }

  MockClock clock_;
  BandwidthSampler sampler_;
  bool sampler_app_limited_at_start_;
  QuicByteCount bytes_in_flight_;
  QuicBandwidth max_bandwidth_;  // Max observed bandwidth from acks.
  QuicBandwidth est_bandwidth_upper_bound_;
  QuicRoundTripCount round_trip_count_;  // Needed to calculate extra_acked.

  QuicByteCount PacketsToBytes(QuicPacketCount packet_count) {
    return packet_count * kRegularPacketSize;
  }

  void SendPacketInner(uint64_t packet_number, QuicByteCount bytes,
                       HasRetransmittableData has_retransmittable_data) {
    sampler_.OnPacketSent(clock_.Now(), QuicPacketNumber(packet_number), bytes,
                          bytes_in_flight_, has_retransmittable_data);
    if (has_retransmittable_data == HAS_RETRANSMITTABLE_DATA) {
      bytes_in_flight_ += bytes;
    }
  }

  void SendPacket(uint64_t packet_number) {
    SendPacketInner(packet_number, kRegularPacketSize,
                    HAS_RETRANSMITTABLE_DATA);
  }

  BandwidthSample AckPacketInner(uint64_t packet_number) {
    QuicByteCount size = BandwidthSamplerPeer::GetPacketSize(
        sampler_, QuicPacketNumber(packet_number));
    bytes_in_flight_ -= size;
    BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent(
        clock_.Now(), {MakeAckedPacket(packet_number)}, {}, max_bandwidth_,
        est_bandwidth_upper_bound_, round_trip_count_);
    max_bandwidth_ = std::max(max_bandwidth_, sample.sample_max_bandwidth);
    BandwidthSample bandwidth_sample;
    bandwidth_sample.bandwidth = sample.sample_max_bandwidth;
    bandwidth_sample.rtt = sample.sample_rtt;
    bandwidth_sample.state_at_send = sample.last_packet_send_state;
    EXPECT_TRUE(bandwidth_sample.state_at_send.is_valid);
    return bandwidth_sample;
  }

  AckedPacket MakeAckedPacket(uint64_t packet_number) const {
    QuicByteCount size = BandwidthSamplerPeer::GetPacketSize(
        sampler_, QuicPacketNumber(packet_number));
    return AckedPacket(QuicPacketNumber(packet_number), size, clock_.Now());
  }

  LostPacket MakeLostPacket(uint64_t packet_number) const {
    return LostPacket(QuicPacketNumber(packet_number),
                      BandwidthSamplerPeer::GetPacketSize(
                          sampler_, QuicPacketNumber(packet_number)));
  }

  // Acknowledge receipt of a packet and expect it to be not app-limited.
  QuicBandwidth AckPacket(uint64_t packet_number) {
    BandwidthSample sample = AckPacketInner(packet_number);
    return sample.bandwidth;
  }

  BandwidthSampler::CongestionEventSample OnCongestionEvent(
      std::set<uint64_t> acked_packet_numbers,
      std::set<uint64_t> lost_packet_numbers) {
    AckedPacketVector acked_packets;
    for (auto it = acked_packet_numbers.begin();
         it != acked_packet_numbers.end(); ++it) {
      acked_packets.push_back(MakeAckedPacket(*it));
      bytes_in_flight_ -= acked_packets.back().bytes_acked;
    }

    LostPacketVector lost_packets;
    for (auto it = lost_packet_numbers.begin(); it != lost_packet_numbers.end();
         ++it) {
      lost_packets.push_back(MakeLostPacket(*it));
      bytes_in_flight_ -= lost_packets.back().bytes_lost;
    }

    BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent(
        clock_.Now(), acked_packets, lost_packets, max_bandwidth_,
        est_bandwidth_upper_bound_, round_trip_count_);
    max_bandwidth_ = std::max(max_bandwidth_, sample.sample_max_bandwidth);
    return sample;
  }

  SendTimeState LosePacket(uint64_t packet_number) {
    QuicByteCount size = BandwidthSamplerPeer::GetPacketSize(
        sampler_, QuicPacketNumber(packet_number));
    bytes_in_flight_ -= size;
    LostPacket lost_packet(QuicPacketNumber(packet_number), size);
    BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent(
        clock_.Now(), {}, {lost_packet}, max_bandwidth_,
        est_bandwidth_upper_bound_, round_trip_count_);
    EXPECT_TRUE(sample.last_packet_send_state.is_valid);
    EXPECT_EQ(sample.sample_max_bandwidth, QuicBandwidth::Zero());
    EXPECT_EQ(sample.sample_rtt, QuicTime::Delta::Infinite());
    return sample.last_packet_send_state;
  }

  // Sends one packet and acks it.  Then, send 20 packets.  Finally, send
  // another 20 packets while acknowledging previous 20.
  void Send40PacketsAndAckFirst20(QuicTime::Delta time_between_packets) {
    // Send 20 packets at a constant inter-packet time.
    for (int i = 1; i <= 20; i++) {
      SendPacket(i);
      clock_.AdvanceTime(time_between_packets);
    }

    // Ack packets 1 to 20, while sending new packets at the same rate as
    // before.
    for (int i = 1; i <= 20; i++) {
      AckPacket(i);
      SendPacket(i + 20);
      clock_.AdvanceTime(time_between_packets);
    }
  }
};

INSTANTIATE_TEST_SUITE_P(
    BandwidthSamplerTests, BandwidthSamplerTest,
    testing::Values(TestParameters{/*overestimate_avoidance=*/false},
                    TestParameters{/*overestimate_avoidance=*/true}),
    testing::PrintToStringParamName());

// Test the sampler in a simple stop-and-wait sender setting.
TEST_P(BandwidthSamplerTest, SendAndWait) {
  QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);
  QuicBandwidth expected_bandwidth =
      QuicBandwidth::FromBytesPerSecond(kRegularPacketSize * 100);

  // Send packets at the constant bandwidth.
  for (int i = 1; i < 20; i++) {
    SendPacket(i);
    clock_.AdvanceTime(time_between_packets);
    QuicBandwidth current_sample = AckPacket(i);
    EXPECT_EQ(expected_bandwidth, current_sample);
  }

  // Send packets at the exponentially decreasing bandwidth.
  for (int i = 20; i < 25; i++) {
    time_between_packets = time_between_packets * 2;
    expected_bandwidth = expected_bandwidth * 0.5;

    SendPacket(i);
    clock_.AdvanceTime(time_between_packets);
    QuicBandwidth current_sample = AckPacket(i);
    EXPECT_EQ(expected_bandwidth, current_sample);
  }
  sampler_.RemoveObsoletePackets(QuicPacketNumber(25));

  EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  EXPECT_EQ(0u, bytes_in_flight_);
}

TEST_P(BandwidthSamplerTest, SendTimeState) {
  QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);

  // Send packets 1-5.
  for (int i = 1; i <= 5; i++) {
    SendPacket(i);
    EXPECT_EQ(PacketsToBytes(i), sampler_.total_bytes_sent());
    clock_.AdvanceTime(time_between_packets);
  }

  // Ack packet 1.
  SendTimeState send_time_state = AckPacketInner(1).state_at_send;
  EXPECT_EQ(PacketsToBytes(1), send_time_state.total_bytes_sent);
  EXPECT_EQ(0u, send_time_state.total_bytes_acked);
  EXPECT_EQ(0u, send_time_state.total_bytes_lost);
  EXPECT_EQ(PacketsToBytes(1), sampler_.total_bytes_acked());

  // Lose packet 2.
  send_time_state = LosePacket(2);
  EXPECT_EQ(PacketsToBytes(2), send_time_state.total_bytes_sent);
  EXPECT_EQ(0u, send_time_state.total_bytes_acked);
  EXPECT_EQ(0u, send_time_state.total_bytes_lost);
  EXPECT_EQ(PacketsToBytes(1), sampler_.total_bytes_lost());

  // Lose packet 3.
  send_time_state = LosePacket(3);
  EXPECT_EQ(PacketsToBytes(3), send_time_state.total_bytes_sent);
  EXPECT_EQ(0u, send_time_state.total_bytes_acked);
  EXPECT_EQ(0u, send_time_state.total_bytes_lost);
  EXPECT_EQ(PacketsToBytes(2), sampler_.total_bytes_lost());

  // Send packets 6-10.
  for (int i = 6; i <= 10; i++) {
    SendPacket(i);
    EXPECT_EQ(PacketsToBytes(i), sampler_.total_bytes_sent());
    clock_.AdvanceTime(time_between_packets);
  }

  // Ack all inflight packets.
  QuicPacketCount acked_packet_count = 1;
  EXPECT_EQ(PacketsToBytes(acked_packet_count), sampler_.total_bytes_acked());
  for (int i = 4; i <= 10; i++) {
    send_time_state = AckPacketInner(i).state_at_send;
    ++acked_packet_count;
    EXPECT_EQ(PacketsToBytes(acked_packet_count), sampler_.total_bytes_acked());
    EXPECT_EQ(PacketsToBytes(i), send_time_state.total_bytes_sent);
    if (i <= 5) {
      EXPECT_EQ(0u, send_time_state.total_bytes_acked);
      EXPECT_EQ(0u, send_time_state.total_bytes_lost);
    } else {
      EXPECT_EQ(PacketsToBytes(1), send_time_state.total_bytes_acked);
      EXPECT_EQ(PacketsToBytes(2), send_time_state.total_bytes_lost);
    }

    // This equation works because there is no neutered bytes.
    EXPECT_EQ(send_time_state.total_bytes_sent -
                  send_time_state.total_bytes_acked -
                  send_time_state.total_bytes_lost,
              send_time_state.bytes_in_flight);

    clock_.AdvanceTime(time_between_packets);
  }
}

// Test the sampler during regular windowed sender scenario with fixed
// CWND of 20.
TEST_P(BandwidthSamplerTest, SendPaced) {
  const QuicTime::Delta time_between_packets =
      QuicTime::Delta::FromMilliseconds(1);
  QuicBandwidth expected_bandwidth =
      QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize);

  Send40PacketsAndAckFirst20(time_between_packets);

  // Ack the packets 21 to 40, arriving at the correct bandwidth.
  QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
  for (int i = 21; i <= 40; i++) {
    last_bandwidth = AckPacket(i);
    EXPECT_EQ(expected_bandwidth, last_bandwidth) << "i is " << i;
    clock_.AdvanceTime(time_between_packets);
  }
  sampler_.RemoveObsoletePackets(QuicPacketNumber(41));

  EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  EXPECT_EQ(0u, bytes_in_flight_);
}

// Test the sampler in a scenario where 50% of packets is consistently lost.
TEST_P(BandwidthSamplerTest, SendWithLosses) {
  const QuicTime::Delta time_between_packets =
      QuicTime::Delta::FromMilliseconds(1);
  QuicBandwidth expected_bandwidth =
      QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize) * 0.5;

  // Send 20 packets, each 1 ms apart.
  for (int i = 1; i <= 20; i++) {
    SendPacket(i);
    clock_.AdvanceTime(time_between_packets);
  }

  // Ack packets 1 to 20, losing every even-numbered packet, while sending new
  // packets at the same rate as before.
  for (int i = 1; i <= 20; i++) {
    if (i % 2 == 0) {
      AckPacket(i);
    } else {
      LosePacket(i);
    }
    SendPacket(i + 20);
    clock_.AdvanceTime(time_between_packets);
  }

  // Ack the packets 21 to 40 with the same loss pattern.
  QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
  for (int i = 21; i <= 40; i++) {
    if (i % 2 == 0) {
      last_bandwidth = AckPacket(i);
      EXPECT_EQ(expected_bandwidth, last_bandwidth);
    } else {
      LosePacket(i);
    }
    clock_.AdvanceTime(time_between_packets);
  }
  sampler_.RemoveObsoletePackets(QuicPacketNumber(41));

  EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  EXPECT_EQ(0u, bytes_in_flight_);
}

// Test the sampler in a scenario where the 50% of packets are not
// congestion controlled (specifically, non-retransmittable data is not
// congestion controlled).  Should be functionally consistent in behavior with
// the SendWithLosses test.
TEST_P(BandwidthSamplerTest, NotCongestionControlled) {
  const QuicTime::Delta time_between_packets =
      QuicTime::Delta::FromMilliseconds(1);
  QuicBandwidth expected_bandwidth =
      QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize) * 0.5;

  // Send 20 packets, each 1 ms apart. Every even packet is not congestion
  // controlled.
  for (int i = 1; i <= 20; i++) {
    SendPacketInner(
        i, kRegularPacketSize,
        i % 2 == 0 ? HAS_RETRANSMITTABLE_DATA : NO_RETRANSMITTABLE_DATA);
    clock_.AdvanceTime(time_between_packets);
  }

  // Ensure only congestion controlled packets are tracked.
  EXPECT_EQ(10u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));

  // Ack packets 2 to 21, ignoring every even-numbered packet, while sending new
  // packets at the same rate as before.
  for (int i = 1; i <= 20; i++) {
    if (i % 2 == 0) {
      AckPacket(i);
    }
    SendPacketInner(
        i + 20, kRegularPacketSize,
        i % 2 == 0 ? HAS_RETRANSMITTABLE_DATA : NO_RETRANSMITTABLE_DATA);
    clock_.AdvanceTime(time_between_packets);
  }

  // Ack the packets 22 to 41 with the same congestion controlled pattern.
  QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
  for (int i = 21; i <= 40; i++) {
    if (i % 2 == 0) {
      last_bandwidth = AckPacket(i);
      EXPECT_EQ(expected_bandwidth, last_bandwidth);
    }
    clock_.AdvanceTime(time_between_packets);
  }
  sampler_.RemoveObsoletePackets(QuicPacketNumber(41));

  // Since only congestion controlled packets are entered into the map, it has
  // to be empty at this point.
  EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  EXPECT_EQ(0u, bytes_in_flight_);
}

// Simulate a situation where ACKs arrive in burst and earlier than usual, thus
// producing an ACK rate which is higher than the original send rate.
TEST_P(BandwidthSamplerTest, CompressedAck) {
  const QuicTime::Delta time_between_packets =
      QuicTime::Delta::FromMilliseconds(1);
  QuicBandwidth expected_bandwidth =
      QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize);

  Send40PacketsAndAckFirst20(time_between_packets);

  // Simulate an RTT somewhat lower than the one for 1-to-21 transmission.
  clock_.AdvanceTime(time_between_packets * 15);

  // Ack the packets 21 to 40 almost immediately at once.
  QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
  QuicTime::Delta ridiculously_small_time_delta =
      QuicTime::Delta::FromMicroseconds(20);
  for (int i = 21; i <= 40; i++) {
    last_bandwidth = AckPacket(i);
    clock_.AdvanceTime(ridiculously_small_time_delta);
  }
  EXPECT_EQ(expected_bandwidth, last_bandwidth);

  sampler_.RemoveObsoletePackets(QuicPacketNumber(41));

  EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  EXPECT_EQ(0u, bytes_in_flight_);
}

// Tests receiving ACK packets in the reverse order.
TEST_P(BandwidthSamplerTest, ReorderedAck) {
  const QuicTime::Delta time_between_packets =
      QuicTime::Delta::FromMilliseconds(1);
  QuicBandwidth expected_bandwidth =
      QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize);

  Send40PacketsAndAckFirst20(time_between_packets);

  // Ack the packets 21 to 40 in the reverse order, while sending packets 41 to
  // 60.
  QuicBandwidth last_bandwidth = QuicBandwidth::Zero();
  for (int i = 0; i < 20; i++) {
    last_bandwidth = AckPacket(40 - i);
    EXPECT_EQ(expected_bandwidth, last_bandwidth);
    SendPacket(41 + i);
    clock_.AdvanceTime(time_between_packets);
  }

  // Ack the packets 41 to 60, now in the regular order.
  for (int i = 41; i <= 60; i++) {
    last_bandwidth = AckPacket(i);
    EXPECT_EQ(expected_bandwidth, last_bandwidth);
    clock_.AdvanceTime(time_between_packets);
  }
  sampler_.RemoveObsoletePackets(QuicPacketNumber(61));

  EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  EXPECT_EQ(0u, bytes_in_flight_);
}

// Test the app-limited logic.
TEST_P(BandwidthSamplerTest, AppLimited) {
  const QuicTime::Delta time_between_packets =
      QuicTime::Delta::FromMilliseconds(1);
  QuicBandwidth expected_bandwidth =
      QuicBandwidth::FromKBytesPerSecond(kRegularPacketSize);

  // Send 20 packets at a constant inter-packet time.
  for (int i = 1; i <= 20; i++) {
    SendPacket(i);
    clock_.AdvanceTime(time_between_packets);
  }

  // Ack packets 1 to 20, while sending new packets at the same rate as
  // before.
  for (int i = 1; i <= 20; i++) {
    BandwidthSample sample = AckPacketInner(i);
    EXPECT_EQ(sample.state_at_send.is_app_limited,
              sampler_app_limited_at_start_);
    SendPacket(i + 20);
    clock_.AdvanceTime(time_between_packets);
  }

  // We are now app-limited. Ack 21 to 40 as usual, but do not send anything for
  // now.
  sampler_.OnAppLimited();
  for (int i = 21; i <= 40; i++) {
    BandwidthSample sample = AckPacketInner(i);
    EXPECT_FALSE(sample.state_at_send.is_app_limited);
    EXPECT_EQ(expected_bandwidth, sample.bandwidth);
    clock_.AdvanceTime(time_between_packets);
  }

  // Enter quiescence.
  clock_.AdvanceTime(QuicTime::Delta::FromSeconds(1));

  // Send packets 41 to 60, all of which would be marked as app-limited.
  for (int i = 41; i <= 60; i++) {
    SendPacket(i);
    clock_.AdvanceTime(time_between_packets);
  }

  // Ack packets 41 to 60, while sending packets 61 to 80.  41 to 60 should be
  // app-limited and underestimate the bandwidth due to that.
  for (int i = 41; i <= 60; i++) {
    BandwidthSample sample = AckPacketInner(i);
    EXPECT_TRUE(sample.state_at_send.is_app_limited);
    EXPECT_LT(sample.bandwidth, 0.7f * expected_bandwidth);

    SendPacket(i + 20);
    clock_.AdvanceTime(time_between_packets);
  }

  // Run out of packets, and then ack packet 61 to 80, all of which should have
  // correct non-app-limited samples.
  for (int i = 61; i <= 80; i++) {
    BandwidthSample sample = AckPacketInner(i);
    EXPECT_FALSE(sample.state_at_send.is_app_limited);
    EXPECT_EQ(sample.bandwidth, expected_bandwidth);
    clock_.AdvanceTime(time_between_packets);
  }
  sampler_.RemoveObsoletePackets(QuicPacketNumber(81));

  EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  EXPECT_EQ(0u, bytes_in_flight_);
}

// Test the samples taken at the first flight of packets sent.
TEST_P(BandwidthSamplerTest, FirstRoundTrip) {
  const QuicTime::Delta time_between_packets =
      QuicTime::Delta::FromMilliseconds(1);
  const QuicTime::Delta rtt = QuicTime::Delta::FromMilliseconds(800);
  const int num_packets = 10;
  const QuicByteCount num_bytes = kRegularPacketSize * num_packets;
  const QuicBandwidth real_bandwidth =
      QuicBandwidth::FromBytesAndTimeDelta(num_bytes, rtt);

  for (int i = 1; i <= 10; i++) {
    SendPacket(i);
    clock_.AdvanceTime(time_between_packets);
  }

  clock_.AdvanceTime(rtt - num_packets * time_between_packets);

  QuicBandwidth last_sample = QuicBandwidth::Zero();
  for (int i = 1; i <= 10; i++) {
    QuicBandwidth sample = AckPacket(i);
    EXPECT_GT(sample, last_sample);
    last_sample = sample;
    clock_.AdvanceTime(time_between_packets);
  }

  // The final measured sample for the first flight of sample is expected to be
  // smaller than the real bandwidth, yet it should not lose more than 10%. The
  // specific value of the error depends on the difference between the RTT and
  // the time it takes to exhaust the congestion window (i.e. in the limit when
  // all packets are sent simultaneously, last sample would indicate the real
  // bandwidth).
  EXPECT_LT(last_sample, real_bandwidth);
  EXPECT_GT(last_sample, 0.9f * real_bandwidth);
}

// Test sampler's ability to remove obsolete packets.
TEST_P(BandwidthSamplerTest, RemoveObsoletePackets) {
  SendPacket(1);
  SendPacket(2);
  SendPacket(3);
  SendPacket(4);
  SendPacket(5);

  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(100));

  EXPECT_EQ(5u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  sampler_.RemoveObsoletePackets(QuicPacketNumber(4));
  EXPECT_EQ(2u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  LosePacket(4);
  sampler_.RemoveObsoletePackets(QuicPacketNumber(5));

  EXPECT_EQ(1u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
  AckPacket(5);

  sampler_.RemoveObsoletePackets(QuicPacketNumber(6));

  EXPECT_EQ(0u, BandwidthSamplerPeer::GetNumberOfTrackedPackets(sampler_));
}

TEST_P(BandwidthSamplerTest, NeuterPacket) {
  SendPacket(1);
  EXPECT_EQ(0u, sampler_.total_bytes_neutered());

  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10));
  sampler_.OnPacketNeutered(QuicPacketNumber(1));
  EXPECT_LT(0u, sampler_.total_bytes_neutered());
  EXPECT_EQ(0u, sampler_.total_bytes_acked());

  // If packet 1 is acked it should not produce a bandwidth sample.
  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10));
  BandwidthSampler::CongestionEventSample sample = sampler_.OnCongestionEvent(
      clock_.Now(),
      {AckedPacket(QuicPacketNumber(1), kRegularPacketSize, clock_.Now())}, {},
      max_bandwidth_, est_bandwidth_upper_bound_, round_trip_count_);
  EXPECT_EQ(0u, sampler_.total_bytes_acked());
  EXPECT_EQ(QuicBandwidth::Zero(), sample.sample_max_bandwidth);
  EXPECT_FALSE(sample.sample_is_app_limited);
  EXPECT_EQ(QuicTime::Delta::Infinite(), sample.sample_rtt);
  EXPECT_EQ(0u, sample.sample_max_inflight);
  EXPECT_EQ(0u, sample.extra_acked);
}

TEST_P(BandwidthSamplerTest, CongestionEventSampleDefaultValues) {
  // Make sure a default constructed CongestionEventSample has the correct
  // initial values for BandwidthSampler::OnCongestionEvent() to work.
  BandwidthSampler::CongestionEventSample sample;

  EXPECT_EQ(QuicBandwidth::Zero(), sample.sample_max_bandwidth);
  EXPECT_FALSE(sample.sample_is_app_limited);
  EXPECT_EQ(QuicTime::Delta::Infinite(), sample.sample_rtt);
  EXPECT_EQ(0u, sample.sample_max_inflight);
  EXPECT_EQ(0u, sample.extra_acked);
}

// 1) Send 2 packets, 2) Ack both in 1 event, 3) Repeat.
TEST_P(BandwidthSamplerTest, TwoAckedPacketsPerEvent) {
  QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);
  QuicBandwidth sending_rate = QuicBandwidth::FromBytesAndTimeDelta(
      kRegularPacketSize, time_between_packets);

  for (uint64_t i = 1; i < 21; i++) {
    SendPacket(i);
    clock_.AdvanceTime(time_between_packets);
    if (i % 2 != 0) {
      continue;
    }

    BandwidthSampler::CongestionEventSample sample =
        OnCongestionEvent({i - 1, i}, {});
    EXPECT_EQ(sending_rate, sample.sample_max_bandwidth);
    EXPECT_EQ(time_between_packets, sample.sample_rtt);
    EXPECT_EQ(2 * kRegularPacketSize, sample.sample_max_inflight);
    EXPECT_TRUE(sample.last_packet_send_state.is_valid);
    EXPECT_EQ(2 * kRegularPacketSize,
              sample.last_packet_send_state.bytes_in_flight);
    EXPECT_EQ(i * kRegularPacketSize,
              sample.last_packet_send_state.total_bytes_sent);
    EXPECT_EQ((i - 2) * kRegularPacketSize,
              sample.last_packet_send_state.total_bytes_acked);
    EXPECT_EQ(0u, sample.last_packet_send_state.total_bytes_lost);
    sampler_.RemoveObsoletePackets(QuicPacketNumber(i - 2));
  }
}

TEST_P(BandwidthSamplerTest, LoseEveryOtherPacket) {
  QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);
  QuicBandwidth sending_rate = QuicBandwidth::FromBytesAndTimeDelta(
      kRegularPacketSize, time_between_packets);

  for (uint64_t i = 1; i < 21; i++) {
    SendPacket(i);
    clock_.AdvanceTime(time_between_packets);
    if (i % 2 != 0) {
      continue;
    }

    // Ack packet i and lose i-1.
    BandwidthSampler::CongestionEventSample sample =
        OnCongestionEvent({i}, {i - 1});
    // Losing 50% packets means sending rate is twice the bandwidth.
    EXPECT_EQ(sending_rate, sample.sample_max_bandwidth * 2);
    EXPECT_EQ(time_between_packets, sample.sample_rtt);
    EXPECT_EQ(kRegularPacketSize, sample.sample_max_inflight);
    EXPECT_TRUE(sample.last_packet_send_state.is_valid);
    EXPECT_EQ(2 * kRegularPacketSize,
              sample.last_packet_send_state.bytes_in_flight);
    EXPECT_EQ(i * kRegularPacketSize,
              sample.last_packet_send_state.total_bytes_sent);
    EXPECT_EQ((i - 2) * kRegularPacketSize / 2,
              sample.last_packet_send_state.total_bytes_acked);
    EXPECT_EQ((i - 2) * kRegularPacketSize / 2,
              sample.last_packet_send_state.total_bytes_lost);
    sampler_.RemoveObsoletePackets(QuicPacketNumber(i - 2));
  }
}

TEST_P(BandwidthSamplerTest, AckHeightRespectBandwidthEstimateUpperBound) {
  QuicTime::Delta time_between_packets = QuicTime::Delta::FromMilliseconds(10);
  QuicBandwidth first_packet_sending_rate =
      QuicBandwidth::FromBytesAndTimeDelta(kRegularPacketSize,
                                           time_between_packets);

  // Send packets 1 to 4 and ack packet 1.
  SendPacket(1);
  clock_.AdvanceTime(time_between_packets);
  SendPacket(2);
  SendPacket(3);
  SendPacket(4);
  BandwidthSampler::CongestionEventSample sample = OnCongestionEvent({1}, {});
  EXPECT_EQ(first_packet_sending_rate, sample.sample_max_bandwidth);
  EXPECT_EQ(first_packet_sending_rate, max_bandwidth_);

  // Ack packet 2, 3 and 4, all of which uses S(1) to calculate ack rate since
  // there were no acks at the time they were sent.
  round_trip_count_++;
  est_bandwidth_upper_bound_ = first_packet_sending_rate * 0.3;
  clock_.AdvanceTime(time_between_packets);
  sample = OnCongestionEvent({2, 3, 4}, {});
  EXPECT_EQ(first_packet_sending_rate * 2, sample.sample_max_bandwidth);
  EXPECT_EQ(max_bandwidth_, sample.sample_max_bandwidth);

  EXPECT_LT(2 * kRegularPacketSize, sample.extra_acked);
}

class MaxAckHeightTrackerTest : public QuicTest {
 protected:
  MaxAckHeightTrackerTest() : tracker_(/*initial_filter_window=*/10) {
    tracker_.SetAckAggregationBandwidthThreshold(1.8);
    tracker_.SetStartNewAggregationEpochAfterFullRound(true);
  }

  // Run a full aggregation episode, which is one or more aggregated acks,
  // followed by a quiet period in which no ack happens.
  // After this function returns, the time is set to the earliest point at which
  // any ack event will cause tracker_.Update() to start a new aggregation.
  void AggregationEpisode(QuicBandwidth aggregation_bandwidth,
                          QuicTime::Delta aggregation_duration,
                          QuicByteCount bytes_per_ack,
                          bool expect_new_aggregation_epoch) {
    ASSERT_GE(aggregation_bandwidth, bandwidth_);
    const QuicTime start_time = now_;

    const QuicByteCount aggregation_bytes =
        aggregation_bandwidth * aggregation_duration;

    const int num_acks = aggregation_bytes / bytes_per_ack;
    ASSERT_EQ(aggregation_bytes, num_acks * bytes_per_ack)
        << "aggregation_bytes: " << aggregation_bytes << " ["
        << aggregation_bandwidth << " in " << aggregation_duration
        << "], bytes_per_ack: " << bytes_per_ack;

    const QuicTime::Delta time_between_acks = QuicTime::Delta::FromMicroseconds(
        aggregation_duration.ToMicroseconds() / num_acks);
    ASSERT_EQ(aggregation_duration, num_acks * time_between_acks)
        << "aggregation_bytes: " << aggregation_bytes
        << ", num_acks: " << num_acks
        << ", time_between_acks: " << time_between_acks;

    // The total duration of aggregation time and quiet period.
    const QuicTime::Delta total_duration = QuicTime::Delta::FromMicroseconds(
        aggregation_bytes * 8 * 1000000 / bandwidth_.ToBitsPerSecond());
    ASSERT_EQ(aggregation_bytes, total_duration * bandwidth_)
        << "total_duration: " << total_duration
        << ", bandwidth_: " << bandwidth_;

    QuicByteCount last_extra_acked = 0;
    for (QuicByteCount bytes = 0; bytes < aggregation_bytes;
         bytes += bytes_per_ack) {
      QuicByteCount extra_acked = tracker_.Update(
          bandwidth_, true, RoundTripCount(), last_sent_packet_number_,
          last_acked_packet_number_, now_, bytes_per_ack);
      QUIC_VLOG(1) << "T" << now_ << ": Update after " << bytes_per_ack
                   << " bytes acked, " << extra_acked << " extra bytes acked";
      // |extra_acked| should be 0 if either
      // [1] We are at the beginning of a aggregation epoch(bytes==0) and the
      //     the current tracker implementation can identify it, or
      // [2] We are not really aggregating acks.
      if ((bytes == 0 && expect_new_aggregation_epoch) ||  // [1]
          (aggregation_bandwidth == bandwidth_)) {         // [2]
        EXPECT_EQ(0u, extra_acked);
      } else {
        EXPECT_LT(last_extra_acked, extra_acked);
      }
      now_ = now_ + time_between_acks;
      last_extra_acked = extra_acked;
    }

    // Advance past the quiet period.
    const QuicTime time_after_aggregation = now_;
    now_ = start_time + total_duration;
    QUIC_VLOG(1) << "Advanced time from " << time_after_aggregation << " to "
                 << now_ << ". Aggregation time["
                 << (time_after_aggregation - start_time) << "], Quiet time["
                 << (now_ - time_after_aggregation) << "].";
  }

  QuicRoundTripCount RoundTripCount() const {
    return (now_ - QuicTime::Zero()).ToMicroseconds() / rtt_.ToMicroseconds();
  }

  MaxAckHeightTracker tracker_;
  QuicBandwidth bandwidth_ = QuicBandwidth::FromBytesPerSecond(10 * 1000);
  QuicTime now_ = QuicTime::Zero() + QuicTime::Delta::FromMilliseconds(1);
  QuicTime::Delta rtt_ = QuicTime::Delta::FromMilliseconds(60);
  QuicPacketNumber last_sent_packet_number_;
  QuicPacketNumber last_acked_packet_number_;
};

TEST_F(MaxAckHeightTrackerTest, VeryAggregatedLargeAck) {
  AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
                     1200, true);
  AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
                     1200, true);
  now_ = now_ - QuicTime::Delta::FromMilliseconds(1);

  if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) {
    AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
                       1200, true);
    EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs());
  } else {
    AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
                       1200, false);
    EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
  }
}

TEST_F(MaxAckHeightTrackerTest, VeryAggregatedSmallAcks) {
  AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), 300,
                     true);
  AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6), 300,
                     true);
  now_ = now_ - QuicTime::Delta::FromMilliseconds(1);

  if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) {
    AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
                       300, true);
    EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs());
  } else {
    AggregationEpisode(bandwidth_ * 20, QuicTime::Delta::FromMilliseconds(6),
                       300, false);
    EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
  }
}

TEST_F(MaxAckHeightTrackerTest, SomewhatAggregatedLargeAck) {
  AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
                     1000, true);
  AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
                     1000, true);
  now_ = now_ - QuicTime::Delta::FromMilliseconds(1);

  if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) {
    AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
                       1000, true);
    EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs());
  } else {
    AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
                       1000, false);
    EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
  }
}

TEST_F(MaxAckHeightTrackerTest, SomewhatAggregatedSmallAcks) {
  AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), 100,
                     true);
  AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), 100,
                     true);
  now_ = now_ - QuicTime::Delta::FromMilliseconds(1);

  if (tracker_.ack_aggregation_bandwidth_threshold() > 1.1) {
    AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
                       100, true);
    EXPECT_EQ(3u, tracker_.num_ack_aggregation_epochs());
  } else {
    AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50),
                       100, false);
    EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
  }
}

TEST_F(MaxAckHeightTrackerTest, NotAggregated) {
  AggregationEpisode(bandwidth_, QuicTime::Delta::FromMilliseconds(100), 100,
                     true);
  EXPECT_LT(2u, tracker_.num_ack_aggregation_epochs());
}

TEST_F(MaxAckHeightTrackerTest, StartNewEpochAfterAFullRound) {
  last_sent_packet_number_ = QuicPacketNumber(10);
  AggregationEpisode(bandwidth_ * 2, QuicTime::Delta::FromMilliseconds(50), 100,
                     true);

  last_acked_packet_number_ = QuicPacketNumber(11);
  // Update with a tiny bandwidth causes a very low expected bytes acked, which
  // in turn causes the current epoch to continue if the |tracker_| doesn't
  // check the packet numbers.
  tracker_.Update(bandwidth_ * 0.1, true, RoundTripCount(),
                  last_sent_packet_number_, last_acked_packet_number_, now_,
                  100);

  EXPECT_EQ(2u, tracker_.num_ack_aggregation_epochs());
}

}  // namespace test
}  // namespace quic