// Copyright 2019 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/nqe/network_congestion_analyzer.h"

#include <map>
#include <unordered_map>

#include "base/macros.h"
#include "base/optional.h"
#include "base/test/simple_test_tick_clock.h"
#include "base/time/time.h"
#include "net/nqe/network_quality.h"
#include "net/nqe/network_quality_estimator_test_util.h"
#include "net/nqe/observation_buffer.h"
#include "net/test/test_with_task_environment.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace net {

namespace nqe {

namespace internal {

using NetworkCongestionAnalyzerTest = TestWithTaskEnvironment;

namespace {

constexpr float kEpsilon = 0.001f;

// These values should remain synchronized with the values in
// net/nqe/network_congestion_analyzer.cc.
constexpr int64_t kHighQueueingDelayMsec = 5000;
constexpr int64_t kMinEmptyQueueObservingTimeMsec = 1500;
constexpr base::TimeDelta
    kLowQueueingDelayThresholds[EFFECTIVE_CONNECTION_TYPE_LAST] = {
        base::TimeDelta::FromMilliseconds(400),
        base::TimeDelta::FromMilliseconds(400),
        base::TimeDelta::FromMilliseconds(400),
        base::TimeDelta::FromMilliseconds(400),
        base::TimeDelta::FromMilliseconds(40),
        base::TimeDelta::FromMilliseconds(15)};
static constexpr size_t kMinScoreForValidSamples = 50;

// Verifies that the network queueing delay is computed correctly based on RTT
// and downlink throughput observations.
TEST_F(NetworkCongestionAnalyzerTest, TestComputingQueueingDelay) {
  TestNetworkQualityEstimator network_quality_estimator;
  base::SimpleTestTickClock tick_clock;

  NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);
  std::map<uint64_t, CanonicalStats> recent_rtt_stats;
  std::map<uint64_t, CanonicalStats> historical_rtt_stats;
  int32_t downlink_kbps = nqe::internal::INVALID_RTT_THROUGHPUT;

  // Checks that no result is updated when providing empty RTT observations and
  // an invalid downlink throughput observation.
  analyzer.ComputeRecentQueueingDelay(recent_rtt_stats, historical_rtt_stats,
                                      downlink_kbps);
  EXPECT_TRUE(analyzer.recent_queueing_delay().is_zero());

  const uint64_t host_1 = 0x101010UL;
  const uint64_t host_2 = 0x202020UL;
  // Checks that the queueing delay is updated based on hosts with valid RTT
  // observations. For example, the computation should be done by using data
  // from host 1 only because host 2 does not provide a valid min RTT value.
  std::map<int32_t, int32_t> recent_stat_host_1 = {{kStatVal0p, 1100}};
  std::map<int32_t, int32_t> historical_stat_host_1 = {{kStatVal0p, 600}};
  CanonicalStats recent_rtt_host_1 =
      CanonicalStats(recent_stat_host_1, 1400, 5);
  CanonicalStats historical_rtt_host_1 =
      CanonicalStats(historical_stat_host_1, 1400, 15);

  std::map<int32_t, int32_t> recent_stat_host_2 = {{kStatVal0p, 1200}};
  std::map<int32_t, int32_t> historical_stat_host_2 = {{kStatVal50p, 1200}};
  CanonicalStats recent_rtt_host_2 =
      CanonicalStats(recent_stat_host_2, 1600, 3);
  CanonicalStats historical_rtt_host_2 =
      CanonicalStats(historical_stat_host_2, 1600, 8);
  recent_rtt_stats.emplace(host_1, recent_rtt_host_1);
  recent_rtt_stats.emplace(host_2, recent_rtt_host_2);
  historical_rtt_stats.emplace(host_1, historical_rtt_host_1);
  historical_rtt_stats.emplace(host_2, historical_rtt_host_2);

  analyzer.ComputeRecentQueueingDelay(recent_rtt_stats, historical_rtt_stats,
                                      downlink_kbps);
  EXPECT_EQ(800, analyzer.recent_queueing_delay().InMilliseconds());

  // Checks that the queueing delay is updated correctly based on all hosts when
  // RTT observations and the throughput observation are valid.
  historical_rtt_stats[host_2].canonical_pcts[kStatVal0p] = 1000;
  downlink_kbps = 120;
  analyzer.ComputeRecentQueueingDelay(recent_rtt_stats, historical_rtt_stats,
                                      downlink_kbps);
  EXPECT_EQ(700, analyzer.recent_queueing_delay().InMilliseconds());
  EXPECT_NEAR(7.0, analyzer.recent_queue_length().value_or(0), kEpsilon);
}

}  // namespace

// Verifies that a measurement period starts correctly when an empty queue
// observation shows up. An empty queue observation is made when the queueing
// delay is low and the number of in-flight requests is also low.
TEST_F(NetworkCongestionAnalyzerTest, TestStartingNewMeasurementPeriod) {
  TestNetworkQualityEstimator network_quality_estimator;
  base::SimpleTestTickClock tick_clock;

  network_quality_estimator.set_effective_connection_type(
      EFFECTIVE_CONNECTION_TYPE_2G);
  NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);
  base::TimeDelta low_queueing_delay_sample =
      kLowQueueingDelayThresholds[EFFECTIVE_CONNECTION_TYPE_2G];

  // Checks that a new measurement period starts immediately if the queueing
  // delay is low and the number of in-flight requests are equal or less than 1.
  EXPECT_FALSE(
      analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 2));
  EXPECT_TRUE(analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 1));
  EXPECT_TRUE(analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 0));

  // Checks that a new measurement period starts after waiting for a sufficient
  // time interval when the number of in-flight requests is 2.
  EXPECT_FALSE(
      analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 2));
  tick_clock.Advance(
      base::TimeDelta::FromMilliseconds(kMinEmptyQueueObservingTimeMsec / 2));
  EXPECT_FALSE(
      analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 2));
  tick_clock.Advance(
      base::TimeDelta::FromMilliseconds(kMinEmptyQueueObservingTimeMsec / 2));
  EXPECT_TRUE(analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 2));
}

// Verifies that the peak queueing delay is correctly mapped to the count of
// in-flight requests that are responsible for that delay.
TEST_F(NetworkCongestionAnalyzerTest, TestUpdatePeakDelayMapping) {
  TestNetworkQualityEstimator network_quality_estimator;
  base::SimpleTestTickClock tick_clock;

  network_quality_estimator.set_effective_connection_type(
      EFFECTIVE_CONNECTION_TYPE_2G);
  NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);
  EXPECT_EQ(base::nullopt,
            analyzer.count_inflight_requests_causing_high_delay());

  // Checks that the count of in-flight requests for peak queueing delay is
  // correctly recorded.
  // Case #1: the peak queueing delay was observed after the max count (7) of
  // in-flight requests was observed.
  const size_t expected_count_requests_1 = 7;
  std::vector<std::pair<base::TimeDelta, size_t>> queueing_delay_samples_1 = {
      std::make_pair(base::TimeDelta::FromMilliseconds(10), 1),
      std::make_pair(base::TimeDelta::FromMilliseconds(10), 3),
      std::make_pair(base::TimeDelta::FromMilliseconds(400), 5),
      std::make_pair(base::TimeDelta::FromMilliseconds(800),
                     expected_count_requests_1),
      std::make_pair(base::TimeDelta::FromMilliseconds(kHighQueueingDelayMsec),
                     5),
      std::make_pair(base::TimeDelta::FromMilliseconds(1000), 3),
      std::make_pair(base::TimeDelta::FromMilliseconds(700), 3),
      std::make_pair(base::TimeDelta::FromMilliseconds(600), 1),
      std::make_pair(base::TimeDelta::FromMilliseconds(300), 0),
  };
  for (const auto& sample : queueing_delay_samples_1) {
    analyzer.UpdatePeakDelayMapping(sample.first, sample.second);
  }
  EXPECT_EQ(expected_count_requests_1,
            analyzer.count_inflight_requests_causing_high_delay().value_or(0));

  // Case #2: the peak queueing delay is observed before the max count (11) of
  // in-flight requests was observed. The 8 requests should be responsible for
  // the peak queueing delay.
  const size_t expected_count_requests_2 = 10;
  std::vector<std::pair<base::TimeDelta, size_t>> queueing_delay_samples_2 = {
      std::make_pair(base::TimeDelta::FromMilliseconds(10), 1),
      std::make_pair(base::TimeDelta::FromMilliseconds(10), 3),
      std::make_pair(base::TimeDelta::FromMilliseconds(400), 5),
      std::make_pair(base::TimeDelta::FromMilliseconds(800), 5),
      std::make_pair(base::TimeDelta::FromMilliseconds(kHighQueueingDelayMsec),
                     expected_count_requests_2),
      std::make_pair(base::TimeDelta::FromMilliseconds(3000), 11),
      std::make_pair(base::TimeDelta::FromMilliseconds(700), 3),
      std::make_pair(base::TimeDelta::FromMilliseconds(600), 1),
      std::make_pair(base::TimeDelta::FromMilliseconds(300), 0),
  };
  for (const auto& sample : queueing_delay_samples_2) {
    analyzer.UpdatePeakDelayMapping(sample.first, sample.second);
  }
  EXPECT_EQ(expected_count_requests_2,
            analyzer.count_inflight_requests_causing_high_delay().value_or(0));
}

// Verifies that the network congestion analyzer can correctly determine whether
// a queueing delay sample is low or not under different effective connection
// types (ECTs).
TEST_F(NetworkCongestionAnalyzerTest, TestDetectLowQueueingDelay) {
  TestNetworkQualityEstimator network_quality_estimator;
  base::SimpleTestTickClock tick_clock;
  NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);

  // Checks that computations are done correctly under all different ECTs.
  for (int i = 0; i != net::EFFECTIVE_CONNECTION_TYPE_LAST; ++i) {
    auto type = static_cast<net::EffectiveConnectionType>(i);
    network_quality_estimator.set_effective_connection_type(type);
    base::TimeDelta low_queueing_delay = kLowQueueingDelayThresholds[type];

    EXPECT_TRUE(analyzer.IsQueueingDelayLow(low_queueing_delay));
    EXPECT_FALSE(analyzer.IsQueueingDelayLow(
        low_queueing_delay + base::TimeDelta::FromMilliseconds(1)));
  }
}

// Verifies that the network congestion analyzer can correctly bucketize the
// peak queueing delay samples, and map the peak queueing delay samples to their
// corresponding queueing delay levels from Level1 to Level10.
TEST_F(NetworkCongestionAnalyzerTest, TestComputeQueueingDelayLevel) {
  TestNetworkQualityEstimator network_quality_estimator;
  base::SimpleTestTickClock tick_clock;
  NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);

  std::vector<std::pair<base::TimeDelta, size_t>> queueing_delay_level_samples =
      {std::make_pair(base::TimeDelta::FromMilliseconds(0), 1),
       std::make_pair(base::TimeDelta::FromMilliseconds(25), 1),
       std::make_pair(base::TimeDelta::FromMilliseconds(35), 2),
       std::make_pair(base::TimeDelta::FromMilliseconds(55), 2),
       std::make_pair(base::TimeDelta::FromMilliseconds(65), 3),
       std::make_pair(base::TimeDelta::FromMilliseconds(115), 3),
       std::make_pair(base::TimeDelta::FromMilliseconds(125), 4),
       std::make_pair(base::TimeDelta::FromMilliseconds(245), 4),
       std::make_pair(base::TimeDelta::FromMilliseconds(255), 5),
       std::make_pair(base::TimeDelta::FromMilliseconds(495), 5),
       std::make_pair(base::TimeDelta::FromMilliseconds(505), 6),
       std::make_pair(base::TimeDelta::FromMilliseconds(995), 6),
       std::make_pair(base::TimeDelta::FromMilliseconds(1005), 7),
       std::make_pair(base::TimeDelta::FromMilliseconds(1995), 7),
       std::make_pair(base::TimeDelta::FromMilliseconds(2005), 8),
       std::make_pair(base::TimeDelta::FromMilliseconds(3995), 8),
       std::make_pair(base::TimeDelta::FromMilliseconds(4005), 9),
       std::make_pair(base::TimeDelta::FromMilliseconds(7995), 9),
       std::make_pair(base::TimeDelta::FromMilliseconds(8005), 10),
       std::make_pair(base::TimeDelta::FromMilliseconds(20000), 10)};

  // Checks that all queueing delay samples are correctly mapped to
  // their corresponding levels.
  for (const auto& sample : queueing_delay_level_samples) {
    EXPECT_EQ(sample.second,
              analyzer.ComputePeakQueueingDelayLevel(sample.first));
  }
}

// Verifies that the mapping sample is correctly evaluated with the computation
// of the count-delay mapping score. Also, verifies that samples are inserted
// into the cache when their mapping scores exceed the threshold.
TEST_F(NetworkCongestionAnalyzerTest, TestComputePeakDelayMappingSampleScore) {
  TestNetworkQualityEstimator network_quality_estimator;
  base::SimpleTestTickClock tick_clock;
  NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);

  // Insert these samples into the cache. They are used to evaluate whether a
  // new sample is valid or not.
  std::map<size_t, base::TimeDelta> cached_requests_count_peak_delay_sample = {
      {1, base::TimeDelta::FromMilliseconds(100)},
      {2, base::TimeDelta::FromMilliseconds(200)},
      {3, base::TimeDelta::FromMilliseconds(300)},
      {4, base::TimeDelta::FromMilliseconds(400)},
      {5, base::TimeDelta::FromMilliseconds(500)},
      {6, base::TimeDelta::FromMilliseconds(600)},
      {7, base::TimeDelta::FromMilliseconds(700)},
      {8, base::TimeDelta::FromMilliseconds(800)},
      {9, base::TimeDelta::FromMilliseconds(900)},
      {10, base::TimeDelta::FromMilliseconds(1000)}};

  for (const auto& sample : cached_requests_count_peak_delay_sample) {
    analyzer.count_inflight_requests_for_peak_queueing_delay_ = sample.first;
    analyzer.peak_queueing_delay_ = sample.second;
    analyzer.UpdateRequestsCountAndPeakQueueingDelayMapping();
  }

  // Checks that the scores are correctly computed.
  std::vector<std::pair<size_t, base::TimeDelta>> mapping_sample = {
      std::make_pair(1, base::TimeDelta::FromMilliseconds(100)),
      std::make_pair(2, base::TimeDelta::FromMilliseconds(200)),
      std::make_pair(3, base::TimeDelta::FromMilliseconds(400)),
      std::make_pair(4, base::TimeDelta::FromMilliseconds(800)),
      std::make_pair(5, base::TimeDelta::FromMilliseconds(400)),
      std::make_pair(6, base::TimeDelta::FromMilliseconds(200)),
      std::make_pair(7, base::TimeDelta::FromMilliseconds(200)),
      std::make_pair(8, base::TimeDelta::FromMilliseconds(200)),
      std::make_pair(9, base::TimeDelta::FromMilliseconds(200)),
      std::make_pair(10, base::TimeDelta::FromMilliseconds(900)),
      std::make_pair(11, base::TimeDelta::FromMilliseconds(500))};
  std::vector<size_t> ground_truth_mapping_score = {100, 100, 90, 60, 90, 60,
                                                    50,  40,  30, 90, 40};

  EXPECT_EQ(mapping_sample.size(), ground_truth_mapping_score.size());
  EXPECT_EQ(10u, analyzer.count_peak_queueing_delay_mapping_sample_);

  for (size_t i = 0; i < mapping_sample.size(); ++i) {
    EXPECT_EQ(analyzer.ComputePeakDelayMappingSampleScore(
                  mapping_sample[i].first, mapping_sample[i].second),
              ground_truth_mapping_score[i]);
  }

  // Checks that only samples with a score higher than a threshold would be
  // inserted into the cache.
  size_t inserted_samples_count = 0;
  size_t samples_count_before = 0;
  bool is_inserted = false;
  for (const auto& sample : mapping_sample) {
    samples_count_before =
        analyzer.count_inflight_requests_to_queueing_delay_[sample.first]
            .size();
    is_inserted =
        analyzer.ComputePeakDelayMappingSampleScore(sample.first, sample.second)
            .value_or(0) >= kMinScoreForValidSamples;
    // Inserts the new sample.
    analyzer.count_inflight_requests_for_peak_queueing_delay_ = sample.first;
    analyzer.peak_queueing_delay_ = sample.second;
    analyzer.UpdateRequestsCountAndPeakQueueingDelayMapping();
    if (is_inserted) {
      ++inserted_samples_count;
      EXPECT_EQ(
          samples_count_before + 1,
          analyzer.count_inflight_requests_to_queueing_delay_[sample.first]
              .size());
    } else {
      EXPECT_EQ(
          samples_count_before,
          analyzer.count_inflight_requests_to_queueing_delay_[sample.first]
              .size());
    }
  }

  EXPECT_EQ(10u + inserted_samples_count,
            analyzer.count_peak_queueing_delay_mapping_sample_);
}

}  // namespace internal

}  // namespace nqe

}  // namespace net