// Copyright (c) 2015 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/third_party/quiche/src/quic/core/congestion_control/cubic_bytes.h"

#include <cstdint>

#include "net/third_party/quiche/src/quic/platform/api/quic_flags.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_str_cat.h"
#include "net/third_party/quiche/src/quic/platform/api/quic_test.h"
#include "net/third_party/quiche/src/quic/test_tools/mock_clock.h"

namespace quic {
namespace test {
namespace {

const float kBeta = 0.7f;          // Default Cubic backoff factor.
const float kBetaLastMax = 0.85f;  // Default Cubic backoff factor.
const uint32_t kNumConnections = 2;
const float kNConnectionBeta = (kNumConnections - 1 + kBeta) / kNumConnections;
const float kNConnectionBetaLastMax =
    (kNumConnections - 1 + kBetaLastMax) / kNumConnections;
const float kNConnectionAlpha = 3 * kNumConnections * kNumConnections *
                                (1 - kNConnectionBeta) / (1 + kNConnectionBeta);

}  // namespace

class CubicBytesTest : public QuicTest {
 protected:
  CubicBytesTest()
      : one_ms_(QuicTime::Delta::FromMilliseconds(1)),
        hundred_ms_(QuicTime::Delta::FromMilliseconds(100)),
        cubic_(&clock_) {}

  QuicByteCount RenoCwndInBytes(QuicByteCount current_cwnd) {
    QuicByteCount reno_estimated_cwnd =
        current_cwnd +
        kDefaultTCPMSS * (kNConnectionAlpha * kDefaultTCPMSS) / current_cwnd;
    return reno_estimated_cwnd;
  }

  QuicByteCount ConservativeCwndInBytes(QuicByteCount current_cwnd) {
    QuicByteCount conservative_cwnd = current_cwnd + kDefaultTCPMSS / 2;
    return conservative_cwnd;
  }

  QuicByteCount CubicConvexCwndInBytes(QuicByteCount initial_cwnd,
                                       QuicTime::Delta rtt,
                                       QuicTime::Delta elapsed_time) {
    const int64_t offset =
        ((elapsed_time + rtt).ToMicroseconds() << 10) / 1000000;
    const QuicByteCount delta_congestion_window =
        ((410 * offset * offset * offset) * kDefaultTCPMSS >> 40);
    const QuicByteCount cubic_cwnd = initial_cwnd + delta_congestion_window;
    return cubic_cwnd;
  }

  QuicByteCount LastMaxCongestionWindow() {
    return cubic_.last_max_congestion_window();
  }

  QuicTime::Delta MaxCubicTimeInterval() {
    return cubic_.MaxCubicTimeInterval();
  }

  const QuicTime::Delta one_ms_;
  const QuicTime::Delta hundred_ms_;
  MockClock clock_;
  CubicBytes cubic_;
};

// TODO(jokulik): The original "AboveOrigin" test, below, is very
// loose.  It's nearly impossible to make the test tighter without
// deploying the fix for convex mode.  Once cubic convex is deployed,
// replace "AboveOrigin" with this test.
TEST_F(CubicBytesTest, AboveOriginWithTighterBounds) {
  // Convex growth.
  const QuicTime::Delta rtt_min = hundred_ms_;
  int64_t rtt_min_ms = rtt_min.ToMilliseconds();
  float rtt_min_s = rtt_min_ms / 1000.0;
  QuicByteCount current_cwnd = 10 * kDefaultTCPMSS;
  const QuicByteCount initial_cwnd = current_cwnd;

  clock_.AdvanceTime(one_ms_);
  const QuicTime initial_time = clock_.ApproximateNow();
  const QuicByteCount expected_first_cwnd = RenoCwndInBytes(current_cwnd);
  current_cwnd = cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
                                                 rtt_min, initial_time);
  ASSERT_EQ(expected_first_cwnd, current_cwnd);

  // Normal TCP phase.
  // The maximum number of expected Reno RTTs is calculated by
  // finding the point where the cubic curve and the reno curve meet.
  const int max_reno_rtts =
      std::sqrt(kNConnectionAlpha / (.4 * rtt_min_s * rtt_min_s * rtt_min_s)) -
      2;
  for (int i = 0; i < max_reno_rtts; ++i) {
    // Alternatively, we expect it to increase by one, every time we
    // receive current_cwnd/Alpha acks back.  (This is another way of
    // saying we expect cwnd to increase by approximately Alpha once
    // we receive current_cwnd number ofacks back).
    const uint64_t num_acks_this_epoch =
        current_cwnd / kDefaultTCPMSS / kNConnectionAlpha;
    const QuicByteCount initial_cwnd_this_epoch = current_cwnd;
    for (QuicPacketCount n = 0; n < num_acks_this_epoch; ++n) {
      // Call once per ACK.
      const QuicByteCount expected_next_cwnd = RenoCwndInBytes(current_cwnd);
      current_cwnd = cubic_.CongestionWindowAfterAck(
          kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
      ASSERT_EQ(expected_next_cwnd, current_cwnd);
    }
    // Our byte-wise Reno implementation is an estimate.  We expect
    // the cwnd to increase by approximately one MSS every
    // cwnd/kDefaultTCPMSS/Alpha acks, but it may be off by as much as
    // half a packet for smaller values of current_cwnd.
    const QuicByteCount cwnd_change_this_epoch =
        current_cwnd - initial_cwnd_this_epoch;
    ASSERT_NEAR(kDefaultTCPMSS, cwnd_change_this_epoch, kDefaultTCPMSS / 2);
    clock_.AdvanceTime(hundred_ms_);
  }

  for (int i = 0; i < 54; ++i) {
    const uint64_t max_acks_this_epoch = current_cwnd / kDefaultTCPMSS;
    const QuicTime::Delta interval = QuicTime::Delta::FromMicroseconds(
        hundred_ms_.ToMicroseconds() / max_acks_this_epoch);
    for (QuicPacketCount n = 0; n < max_acks_this_epoch; ++n) {
      clock_.AdvanceTime(interval);
      current_cwnd = cubic_.CongestionWindowAfterAck(
          kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
      const QuicByteCount expected_cwnd = CubicConvexCwndInBytes(
          initial_cwnd, rtt_min, (clock_.ApproximateNow() - initial_time));
      // If we allow per-ack updates, every update is a small cubic update.
      ASSERT_EQ(expected_cwnd, current_cwnd);
    }
  }
  const QuicByteCount expected_cwnd = CubicConvexCwndInBytes(
      initial_cwnd, rtt_min, (clock_.ApproximateNow() - initial_time));
  current_cwnd = cubic_.CongestionWindowAfterAck(
      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
  ASSERT_EQ(expected_cwnd, current_cwnd);
}

// TODO(ianswett): This test was disabled when all fixes were enabled, but it
// may be worth fixing.
TEST_F(CubicBytesTest, DISABLED_AboveOrigin) {
  // Convex growth.
  const QuicTime::Delta rtt_min = hundred_ms_;
  QuicByteCount current_cwnd = 10 * kDefaultTCPMSS;
  // Without the signed-integer, cubic-convex fix, we start out in the
  // wrong mode.
  QuicPacketCount expected_cwnd = RenoCwndInBytes(current_cwnd);
  // Initialize the state.
  clock_.AdvanceTime(one_ms_);
  ASSERT_EQ(expected_cwnd,
            cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
                                            rtt_min, clock_.ApproximateNow()));
  current_cwnd = expected_cwnd;
  const QuicPacketCount initial_cwnd = expected_cwnd;
  // Normal TCP phase.
  for (int i = 0; i < 48; ++i) {
    for (QuicPacketCount n = 1;
         n < current_cwnd / kDefaultTCPMSS / kNConnectionAlpha; ++n) {
      // Call once per ACK.
      ASSERT_NEAR(
          current_cwnd,
          cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd, rtt_min,
                                          clock_.ApproximateNow()),
          kDefaultTCPMSS);
    }
    clock_.AdvanceTime(hundred_ms_);
    current_cwnd = cubic_.CongestionWindowAfterAck(
        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
    // When we fix convex mode and the uint64 arithmetic, we
    // increase the expected_cwnd only after after the first 100ms,
    // rather than after the initial 1ms.
    expected_cwnd += kDefaultTCPMSS;
    ASSERT_NEAR(expected_cwnd, current_cwnd, kDefaultTCPMSS);
  }
  // Cubic phase.
  for (int i = 0; i < 52; ++i) {
    for (QuicPacketCount n = 1; n < current_cwnd / kDefaultTCPMSS; ++n) {
      // Call once per ACK.
      ASSERT_NEAR(
          current_cwnd,
          cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd, rtt_min,
                                          clock_.ApproximateNow()),
          kDefaultTCPMSS);
    }
    clock_.AdvanceTime(hundred_ms_);
    current_cwnd = cubic_.CongestionWindowAfterAck(
        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
  }
  // Total time elapsed so far; add min_rtt (0.1s) here as well.
  float elapsed_time_s = 10.0f + 0.1f;
  // |expected_cwnd| is initial value of cwnd + K * t^3, where K = 0.4.
  expected_cwnd =
      initial_cwnd / kDefaultTCPMSS +
      (elapsed_time_s * elapsed_time_s * elapsed_time_s * 410) / 1024;
  EXPECT_EQ(expected_cwnd, current_cwnd / kDefaultTCPMSS);
}

// Constructs an artificial scenario to ensure that cubic-convex
// increases are truly fine-grained:
//
// - After starting the epoch, this test advances the elapsed time
// sufficiently far that cubic will do small increases at less than
// MaxCubicTimeInterval() intervals.
//
// - Sets an artificially large initial cwnd to prevent Reno from the
// convex increases on every ack.
TEST_F(CubicBytesTest, AboveOriginFineGrainedCubing) {
  // Start the test with an artificially large cwnd to prevent Reno
  // from over-taking cubic.
  QuicByteCount current_cwnd = 1000 * kDefaultTCPMSS;
  const QuicByteCount initial_cwnd = current_cwnd;
  const QuicTime::Delta rtt_min = hundred_ms_;
  clock_.AdvanceTime(one_ms_);
  QuicTime initial_time = clock_.ApproximateNow();

  // Start the epoch and then artificially advance the time.
  current_cwnd = cubic_.CongestionWindowAfterAck(
      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
  clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(600));
  current_cwnd = cubic_.CongestionWindowAfterAck(
      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());

  // We expect the algorithm to perform only non-zero, fine-grained cubic
  // increases on every ack in this case.
  for (int i = 0; i < 100; ++i) {
    clock_.AdvanceTime(QuicTime::Delta::FromMilliseconds(10));
    const QuicByteCount expected_cwnd = CubicConvexCwndInBytes(
        initial_cwnd, rtt_min, (clock_.ApproximateNow() - initial_time));
    const QuicByteCount next_cwnd = cubic_.CongestionWindowAfterAck(
        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
    // Make sure we are performing cubic increases.
    ASSERT_EQ(expected_cwnd, next_cwnd);
    // Make sure that these are non-zero, less-than-packet sized
    // increases.
    ASSERT_GT(next_cwnd, current_cwnd);
    const QuicByteCount cwnd_delta = next_cwnd - current_cwnd;
    ASSERT_GT(kDefaultTCPMSS * .1, cwnd_delta);

    current_cwnd = next_cwnd;
  }
}

// Constructs an artificial scenario to show what happens when we
// allow per-ack updates, rather than limititing update freqency.  In
// this scenario, the first two acks of the epoch produce the same
// cwnd.  When we limit per-ack updates, this would cause the
// cessation of cubic updates for 30ms.  When we allow per-ack
// updates, the window continues to grow on every ack.
TEST_F(CubicBytesTest, PerAckUpdates) {
  // Start the test with a large cwnd and RTT, to force the first
  // increase to be a cubic increase.
  QuicPacketCount initial_cwnd_packets = 150;
  QuicByteCount current_cwnd = initial_cwnd_packets * kDefaultTCPMSS;
  const QuicTime::Delta rtt_min = 350 * one_ms_;

  // Initialize the epoch
  clock_.AdvanceTime(one_ms_);
  // Keep track of the growth of the reno-equivalent cwnd.
  QuicByteCount reno_cwnd = RenoCwndInBytes(current_cwnd);
  current_cwnd = cubic_.CongestionWindowAfterAck(
      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
  const QuicByteCount initial_cwnd = current_cwnd;

  // Simulate the return of cwnd packets in less than
  // MaxCubicInterval() time.
  const QuicPacketCount max_acks = initial_cwnd_packets / kNConnectionAlpha;
  const QuicTime::Delta interval = QuicTime::Delta::FromMicroseconds(
      MaxCubicTimeInterval().ToMicroseconds() / (max_acks + 1));

  // In this scenario, the first increase is dictated by the cubic
  // equation, but it is less than one byte, so the cwnd doesn't
  // change.  Normally, without per-ack increases, any cwnd plateau
  // will cause the cwnd to be pinned for MaxCubicTimeInterval().  If
  // we enable per-ack updates, the cwnd will continue to grow,
  // regardless of the temporary plateau.
  clock_.AdvanceTime(interval);
  reno_cwnd = RenoCwndInBytes(reno_cwnd);
  ASSERT_EQ(current_cwnd,
            cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
                                            rtt_min, clock_.ApproximateNow()));
  for (QuicPacketCount i = 1; i < max_acks; ++i) {
    clock_.AdvanceTime(interval);
    const QuicByteCount next_cwnd = cubic_.CongestionWindowAfterAck(
        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
    reno_cwnd = RenoCwndInBytes(reno_cwnd);
    // The window shoud increase on every ack.
    ASSERT_LT(current_cwnd, next_cwnd);
    ASSERT_EQ(reno_cwnd, next_cwnd);
    current_cwnd = next_cwnd;
  }

  // After all the acks are returned from the epoch, we expect the
  // cwnd to have increased by nearly one packet.  (Not exactly one
  // packet, because our byte-wise Reno algorithm is always a slight
  // under-estimation).  Without per-ack updates, the current_cwnd
  // would otherwise be unchanged.
  const QuicByteCount minimum_expected_increase = kDefaultTCPMSS * .9;
  EXPECT_LT(minimum_expected_increase + initial_cwnd, current_cwnd);
}

TEST_F(CubicBytesTest, LossEvents) {
  const QuicTime::Delta rtt_min = hundred_ms_;
  QuicByteCount current_cwnd = 422 * kDefaultTCPMSS;
  // Without the signed-integer, cubic-convex fix, we mistakenly
  // increment cwnd after only one_ms_ and a single ack.
  QuicPacketCount expected_cwnd = RenoCwndInBytes(current_cwnd);
  // Initialize the state.
  clock_.AdvanceTime(one_ms_);
  EXPECT_EQ(expected_cwnd,
            cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
                                            rtt_min, clock_.ApproximateNow()));

  // On the first loss, the last max congestion window is set to the
  // congestion window before the loss.
  QuicByteCount pre_loss_cwnd = current_cwnd;
  ASSERT_EQ(0u, LastMaxCongestionWindow());
  expected_cwnd = static_cast<QuicByteCount>(current_cwnd * kNConnectionBeta);
  EXPECT_EQ(expected_cwnd,
            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
  ASSERT_EQ(pre_loss_cwnd, LastMaxCongestionWindow());
  current_cwnd = expected_cwnd;

  // On the second loss, the current congestion window has not yet
  // reached the last max congestion window.  The last max congestion
  // window will be reduced by an additional backoff factor to allow
  // for competition.
  pre_loss_cwnd = current_cwnd;
  expected_cwnd = static_cast<QuicByteCount>(current_cwnd * kNConnectionBeta);
  ASSERT_EQ(expected_cwnd,
            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
  current_cwnd = expected_cwnd;
  EXPECT_GT(pre_loss_cwnd, LastMaxCongestionWindow());
  QuicByteCount expected_last_max =
      static_cast<QuicByteCount>(pre_loss_cwnd * kNConnectionBetaLastMax);
  EXPECT_EQ(expected_last_max, LastMaxCongestionWindow());
  EXPECT_LT(expected_cwnd, LastMaxCongestionWindow());
  // Simulate an increase, and check that we are below the origin.
  current_cwnd = cubic_.CongestionWindowAfterAck(
      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
  EXPECT_GT(LastMaxCongestionWindow(), current_cwnd);

  // On the final loss, simulate the condition where the congestion
  // window had a chance to grow nearly to the last congestion window.
  current_cwnd = LastMaxCongestionWindow() - 1;
  pre_loss_cwnd = current_cwnd;
  expected_cwnd = static_cast<QuicByteCount>(current_cwnd * kNConnectionBeta);
  EXPECT_EQ(expected_cwnd,
            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
  expected_last_max = pre_loss_cwnd;
  ASSERT_EQ(expected_last_max, LastMaxCongestionWindow());
}

TEST_F(CubicBytesTest, BelowOrigin) {
  // Concave growth.
  const QuicTime::Delta rtt_min = hundred_ms_;
  QuicByteCount current_cwnd = 422 * kDefaultTCPMSS;
  // Without the signed-integer, cubic-convex fix, we mistakenly
  // increment cwnd after only one_ms_ and a single ack.
  QuicPacketCount expected_cwnd = RenoCwndInBytes(current_cwnd);
  // Initialize the state.
  clock_.AdvanceTime(one_ms_);
  EXPECT_EQ(expected_cwnd,
            cubic_.CongestionWindowAfterAck(kDefaultTCPMSS, current_cwnd,
                                            rtt_min, clock_.ApproximateNow()));
  expected_cwnd = static_cast<QuicPacketCount>(current_cwnd * kNConnectionBeta);
  EXPECT_EQ(expected_cwnd,
            cubic_.CongestionWindowAfterPacketLoss(current_cwnd));
  current_cwnd = expected_cwnd;
  // First update after loss to initialize the epoch.
  current_cwnd = cubic_.CongestionWindowAfterAck(
      kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
  // Cubic phase.
  for (int i = 0; i < 40; ++i) {
    clock_.AdvanceTime(hundred_ms_);
    current_cwnd = cubic_.CongestionWindowAfterAck(
        kDefaultTCPMSS, current_cwnd, rtt_min, clock_.ApproximateNow());
  }
  expected_cwnd = 553632;
  EXPECT_EQ(expected_cwnd, current_cwnd);
}

}  // namespace test
}  // namespace quic