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

#include "quiche/quic/core/congestion_control/bandwidth_sampler.h"
#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_flag_utils.h"
#include "quiche/quic/platform/api/quic_flags.h"
#include "quiche/quic/platform/api/quic_logging.h"

namespace quic {

RoundTripCounter::RoundTripCounter() : round_trip_count_(0) {}

void RoundTripCounter::OnPacketSent(QuicPacketNumber packet_number) {
  QUICHE_DCHECK(!last_sent_packet_.IsInitialized() ||
                last_sent_packet_ < packet_number);
  last_sent_packet_ = packet_number;
}

bool RoundTripCounter::OnPacketsAcked(QuicPacketNumber last_acked_packet) {
  if (!end_of_round_trip_.IsInitialized() ||
      last_acked_packet > end_of_round_trip_) {
    round_trip_count_++;
    end_of_round_trip_ = last_sent_packet_;
    return true;
  }
  return false;
}

void RoundTripCounter::RestartRound() {
  end_of_round_trip_ = last_sent_packet_;
}

MinRttFilter::MinRttFilter(QuicTime::Delta initial_min_rtt,
                           QuicTime initial_min_rtt_timestamp)
    : min_rtt_(initial_min_rtt),
      min_rtt_timestamp_(initial_min_rtt_timestamp) {}

void MinRttFilter::Update(QuicTime::Delta sample_rtt, QuicTime now) {
  if (sample_rtt < min_rtt_ || min_rtt_timestamp_ == QuicTime::Zero()) {
    min_rtt_ = sample_rtt;
    min_rtt_timestamp_ = now;
  }
}

void MinRttFilter::ForceUpdate(QuicTime::Delta sample_rtt, QuicTime now) {
  min_rtt_ = sample_rtt;
  min_rtt_timestamp_ = now;
}

Bbr2NetworkModel::Bbr2NetworkModel(const Bbr2Params* params,
                                   QuicTime::Delta initial_rtt,
                                   QuicTime initial_rtt_timestamp,
                                   float cwnd_gain, float pacing_gain,
                                   const BandwidthSampler* old_sampler)
    : params_(params),
      bandwidth_sampler_([](QuicRoundTripCount max_height_tracker_window_length,
                            const BandwidthSampler* old_sampler) {
        if (old_sampler != nullptr) {
          return BandwidthSampler(*old_sampler);
        }
        return BandwidthSampler(/*unacked_packet_map=*/nullptr,
                                max_height_tracker_window_length);
      }(params->initial_max_ack_height_filter_window, old_sampler)),
      min_rtt_filter_(initial_rtt, initial_rtt_timestamp),
      cwnd_gain_(cwnd_gain),
      pacing_gain_(pacing_gain) {}

void Bbr2NetworkModel::OnPacketSent(QuicTime sent_time,
                                    QuicByteCount bytes_in_flight,
                                    QuicPacketNumber packet_number,
                                    QuicByteCount bytes,
                                    HasRetransmittableData is_retransmittable) {
  // Updating the min here ensures a more realistic (0) value when flows exit
  // quiescence.
  if (bytes_in_flight < min_bytes_in_flight_in_round_) {
    min_bytes_in_flight_in_round_ = bytes_in_flight;
  }
  if (bytes_in_flight + bytes >= inflight_hi_) {
    inflight_hi_limited_in_round_ = true;
  }
  round_trip_counter_.OnPacketSent(packet_number);

  bandwidth_sampler_.OnPacketSent(sent_time, packet_number, bytes,
                                  bytes_in_flight, is_retransmittable);
}

void Bbr2NetworkModel::OnCongestionEventStart(
    QuicTime event_time, const AckedPacketVector& acked_packets,
    const LostPacketVector& lost_packets,
    Bbr2CongestionEvent* congestion_event) {
  const QuicByteCount prior_bytes_acked = total_bytes_acked();
  const QuicByteCount prior_bytes_lost = total_bytes_lost();

  congestion_event->event_time = event_time;
  congestion_event->end_of_round_trip =
      acked_packets.empty() ? false
                            : round_trip_counter_.OnPacketsAcked(
                                  acked_packets.rbegin()->packet_number);

  BandwidthSamplerInterface::CongestionEventSample sample =
      bandwidth_sampler_.OnCongestionEvent(event_time, acked_packets,
                                           lost_packets, MaxBandwidth(),
                                           bandwidth_lo(), RoundTripCount());

  if (sample.extra_acked == 0) {
    cwnd_limited_before_aggregation_epoch_ =
        congestion_event->prior_bytes_in_flight >= congestion_event->prior_cwnd;
  }

  if (sample.last_packet_send_state.is_valid) {
    congestion_event->last_packet_send_state = sample.last_packet_send_state;
  }

  // Avoid updating |max_bandwidth_filter_| if a) this is a loss-only event, or
  // b) all packets in |acked_packets| did not generate valid samples. (e.g. ack
  // of ack-only packets). In both cases, total_bytes_acked() will not change.
  if (prior_bytes_acked != total_bytes_acked()) {
    QUIC_LOG_IF(WARNING, sample.sample_max_bandwidth.IsZero())
        << total_bytes_acked() - prior_bytes_acked << " bytes from "
        << acked_packets.size()
        << " packets have been acked, but sample_max_bandwidth is zero.";
    congestion_event->sample_max_bandwidth = sample.sample_max_bandwidth;
    if (!sample.sample_is_app_limited ||
        sample.sample_max_bandwidth > MaxBandwidth()) {
      max_bandwidth_filter_.Update(congestion_event->sample_max_bandwidth);
    }
  }

  if (!sample.sample_rtt.IsInfinite()) {
    congestion_event->sample_min_rtt = sample.sample_rtt;
    min_rtt_filter_.Update(congestion_event->sample_min_rtt, event_time);
  }

  congestion_event->bytes_acked = total_bytes_acked() - prior_bytes_acked;
  congestion_event->bytes_lost = total_bytes_lost() - prior_bytes_lost;

  if (congestion_event->prior_bytes_in_flight >=
      congestion_event->bytes_acked + congestion_event->bytes_lost) {
    congestion_event->bytes_in_flight =
        congestion_event->prior_bytes_in_flight -
        congestion_event->bytes_acked - congestion_event->bytes_lost;
  } else {
    QUIC_LOG_FIRST_N(ERROR, 1)
        << "prior_bytes_in_flight:" << congestion_event->prior_bytes_in_flight
        << " is smaller than the sum of bytes_acked:"
        << congestion_event->bytes_acked
        << " and bytes_lost:" << congestion_event->bytes_lost;
    congestion_event->bytes_in_flight = 0;
  }

  if (congestion_event->bytes_lost > 0) {
    bytes_lost_in_round_ += congestion_event->bytes_lost;
    loss_events_in_round_++;
  }

  if (congestion_event->bytes_acked > 0 &&
      congestion_event->last_packet_send_state.is_valid &&
      total_bytes_acked() >
          congestion_event->last_packet_send_state.total_bytes_acked) {
    QuicByteCount bytes_delivered =
        total_bytes_acked() -
        congestion_event->last_packet_send_state.total_bytes_acked;
    max_bytes_delivered_in_round_ =
        std::max(max_bytes_delivered_in_round_, bytes_delivered);
  }
  // TODO(ianswett) Consider treating any bytes lost as decreasing inflight,
  // because it's a sign of overutilization, not underutilization.
  if (congestion_event->bytes_in_flight < min_bytes_in_flight_in_round_) {
    min_bytes_in_flight_in_round_ = congestion_event->bytes_in_flight;
  }

  // |bandwidth_latest_| and |inflight_latest_| only increased within a round.
  if (sample.sample_max_bandwidth > bandwidth_latest_) {
    bandwidth_latest_ = sample.sample_max_bandwidth;
  }

  if (sample.sample_max_inflight > inflight_latest_) {
    inflight_latest_ = sample.sample_max_inflight;
  }

  // Adapt lower bounds(bandwidth_lo and inflight_lo).
  AdaptLowerBounds(*congestion_event);

  if (!congestion_event->end_of_round_trip) {
    return;
  }

  if (!sample.sample_max_bandwidth.IsZero()) {
    bandwidth_latest_ = sample.sample_max_bandwidth;
  }

  if (sample.sample_max_inflight > 0) {
    inflight_latest_ = sample.sample_max_inflight;
  }
}

void Bbr2NetworkModel::AdaptLowerBounds(
    const Bbr2CongestionEvent& congestion_event) {
  if (Params().bw_lo_mode_ == Bbr2Params::DEFAULT) {
    if (!congestion_event.end_of_round_trip ||
        congestion_event.is_probing_for_bandwidth) {
      return;
    }

    if (bytes_lost_in_round_ > 0) {
      if (bandwidth_lo_.IsInfinite()) {
        bandwidth_lo_ = MaxBandwidth();
      }
      bandwidth_lo_ =
          std::max(bandwidth_latest_, bandwidth_lo_ * (1.0 - Params().beta));
      QUIC_DVLOG(3) << "bandwidth_lo_ updated to " << bandwidth_lo_
                    << ", bandwidth_latest_ is " << bandwidth_latest_;

      if (Params().ignore_inflight_lo) {
        return;
      }
      if (inflight_lo_ == inflight_lo_default()) {
        inflight_lo_ = congestion_event.prior_cwnd;
      }
      inflight_lo_ = std::max<QuicByteCount>(
          inflight_latest_, inflight_lo_ * (1.0 - Params().beta));
    }
    return;
  }

  // Params().bw_lo_mode_ != Bbr2Params::DEFAULT
  if (congestion_event.bytes_lost == 0) {
    return;
  }
  // Ignore losses from packets sent when probing for more bandwidth in
  // STARTUP or PROBE_UP when they're lost in DRAIN or PROBE_DOWN.
  if (pacing_gain_ < 1) {
    return;
  }
  // Decrease bandwidth_lo whenever there is loss.
  // Set bandwidth_lo_ if it is not yet set.
  if (bandwidth_lo_.IsInfinite()) {
    bandwidth_lo_ = MaxBandwidth();
  }
  // Save bandwidth_lo_ if it hasn't already been saved.
  if (prior_bandwidth_lo_.IsZero()) {
    prior_bandwidth_lo_ = bandwidth_lo_;
  }
  switch (Params().bw_lo_mode_) {
    case Bbr2Params::MIN_RTT_REDUCTION:
      bandwidth_lo_ =
          bandwidth_lo_ - QuicBandwidth::FromBytesAndTimeDelta(
                              congestion_event.bytes_lost, MinRtt());
      break;
    case Bbr2Params::INFLIGHT_REDUCTION: {
      // Use a max of BDP and inflight to avoid starving app-limited flows.
      const QuicByteCount effective_inflight =
          std::max(BDP(), congestion_event.prior_bytes_in_flight);
      // This could use bytes_lost_in_round if the bandwidth_lo_ was saved
      // when entering 'recovery', but this BBRv2 implementation doesn't have
      // recovery defined.
      bandwidth_lo_ =
          bandwidth_lo_ * ((effective_inflight - congestion_event.bytes_lost) /
                           static_cast<double>(effective_inflight));
      break;
    }
    case Bbr2Params::CWND_REDUCTION:
      bandwidth_lo_ =
          bandwidth_lo_ *
          ((congestion_event.prior_cwnd - congestion_event.bytes_lost) /
           static_cast<double>(congestion_event.prior_cwnd));
      break;
    case Bbr2Params::DEFAULT:
      QUIC_BUG(quic_bug_10466_1) << "Unreachable case DEFAULT.";
  }
  QuicBandwidth last_bandwidth = bandwidth_latest_;
  // sample_max_bandwidth will be Zero() if the loss is triggered by a timer
  // expiring.  Ideally we'd use the most recent bandwidth sample,
  // but bandwidth_latest is safer than Zero().
  if (!congestion_event.sample_max_bandwidth.IsZero()) {
    // bandwidth_latest_ is the max bandwidth for the round, but to allow
    // fast, conservation style response to loss, use the last sample.
    last_bandwidth = congestion_event.sample_max_bandwidth;
  }
  if (pacing_gain_ > Params().startup_full_bw_threshold) {
    // In STARTUP, pacing_gain_ is applied to bandwidth_lo_ in
    // UpdatePacingRate, so this backs that multiplication out to allow the
    // pacing rate to decrease, but not below
    // last_bandwidth * startup_full_bw_threshold.
    // TODO(ianswett): Consider altering pacing_gain_ when in STARTUP instead.
    bandwidth_lo_ = std::max(
        bandwidth_lo_,
        last_bandwidth * (Params().startup_full_bw_threshold / pacing_gain_));
  } else {
    // Ensure bandwidth_lo isn't lower than last_bandwidth.
    bandwidth_lo_ = std::max(bandwidth_lo_, last_bandwidth);
  }
  // If it's the end of the round, ensure bandwidth_lo doesn't decrease more
  // than beta.
  if (congestion_event.end_of_round_trip) {
    bandwidth_lo_ =
        std::max(bandwidth_lo_, prior_bandwidth_lo_ * (1.0 - Params().beta));
    prior_bandwidth_lo_ = QuicBandwidth::Zero();
  }
  // These modes ignore inflight_lo as well.
}

void Bbr2NetworkModel::OnCongestionEventFinish(
    QuicPacketNumber least_unacked_packet,
    const Bbr2CongestionEvent& congestion_event) {
  if (congestion_event.end_of_round_trip) {
    OnNewRound();
  }

  bandwidth_sampler_.RemoveObsoletePackets(least_unacked_packet);
}

void Bbr2NetworkModel::UpdateNetworkParameters(QuicTime::Delta rtt) {
  if (!rtt.IsZero()) {
    min_rtt_filter_.Update(rtt, MinRttTimestamp());
  }
}

bool Bbr2NetworkModel::MaybeExpireMinRtt(
    const Bbr2CongestionEvent& congestion_event) {
  if (congestion_event.event_time <
      (MinRttTimestamp() + Params().probe_rtt_period)) {
    return false;
  }
  if (congestion_event.sample_min_rtt.IsInfinite()) {
    return false;
  }
  QUIC_DVLOG(3) << "Replacing expired min rtt of " << min_rtt_filter_.Get()
                << " by " << congestion_event.sample_min_rtt << "  @ "
                << congestion_event.event_time;
  min_rtt_filter_.ForceUpdate(congestion_event.sample_min_rtt,
                              congestion_event.event_time);
  return true;
}

bool Bbr2NetworkModel::IsInflightTooHigh(
    const Bbr2CongestionEvent& congestion_event,
    int64_t max_loss_events) const {
  const SendTimeState& send_state = congestion_event.last_packet_send_state;
  if (!send_state.is_valid) {
    // Not enough information.
    return false;
  }

  if (loss_events_in_round() < max_loss_events) {
    return false;
  }

  const QuicByteCount inflight_at_send = BytesInFlight(send_state);
  // TODO(wub): Consider total_bytes_lost() - send_state.total_bytes_lost, which
  // is the total bytes lost when the largest numbered packet was inflight.
  // bytes_lost_in_round_, OTOH, is the total bytes lost in the "current" round.
  const QuicByteCount bytes_lost_in_round = bytes_lost_in_round_;

  QUIC_DVLOG(3) << "IsInflightTooHigh: loss_events_in_round:"
                << loss_events_in_round()

                << " bytes_lost_in_round:" << bytes_lost_in_round
                << ", lost_in_round_threshold:"
                << inflight_at_send * Params().loss_threshold;

  if (inflight_at_send > 0 && bytes_lost_in_round > 0) {
    QuicByteCount lost_in_round_threshold =
        inflight_at_send * Params().loss_threshold;
    if (bytes_lost_in_round > lost_in_round_threshold) {
      return true;
    }
  }

  return false;
}

void Bbr2NetworkModel::RestartRoundEarly() {
  OnNewRound();
  round_trip_counter_.RestartRound();
}

void Bbr2NetworkModel::OnNewRound() {
  bytes_lost_in_round_ = 0;
  loss_events_in_round_ = 0;
  max_bytes_delivered_in_round_ = 0;
  min_bytes_in_flight_in_round_ = std::numeric_limits<uint64_t>::max();
  inflight_hi_limited_in_round_ = false;
}

void Bbr2NetworkModel::cap_inflight_lo(QuicByteCount cap) {
  if (Params().ignore_inflight_lo) {
    return;
  }
  if (inflight_lo_ != inflight_lo_default() && inflight_lo_ > cap) {
    inflight_lo_ = cap;
  }
}

QuicByteCount Bbr2NetworkModel::inflight_hi_with_headroom() const {
  QuicByteCount headroom = inflight_hi_ * Params().inflight_hi_headroom;

  return inflight_hi_ > headroom ? inflight_hi_ - headroom : 0;
}

bool Bbr2NetworkModel::HasBandwidthGrowth(
    const Bbr2CongestionEvent& congestion_event) {
  QUICHE_DCHECK(!full_bandwidth_reached_);
  QUICHE_DCHECK(congestion_event.end_of_round_trip);

  QuicBandwidth threshold =
      full_bandwidth_baseline_ * Params().startup_full_bw_threshold;

  if (MaxBandwidth() >= threshold) {
    QUIC_DVLOG(3) << " CheckBandwidthGrowth at end of round. max_bandwidth:"
                  << MaxBandwidth() << ", threshold:" << threshold
                  << " (Still growing)  @ " << congestion_event.event_time;
    full_bandwidth_baseline_ = MaxBandwidth();
    rounds_without_bandwidth_growth_ = 0;
    return true;
  }
  ++rounds_without_bandwidth_growth_;

  // full_bandwidth_reached is only set to true when not app-limited, except
  // when exit_startup_on_persistent_queue is true.
  if (rounds_without_bandwidth_growth_ >= Params().startup_full_bw_rounds &&
      !congestion_event.last_packet_send_state.is_app_limited) {
    full_bandwidth_reached_ = true;
  }
  QUIC_DVLOG(3) << " CheckBandwidthGrowth at end of round. max_bandwidth:"
                << MaxBandwidth() << ", threshold:" << threshold
                << " rounds_without_growth:" << rounds_without_bandwidth_growth_
                << " full_bw_reached:" << full_bandwidth_reached_ << "  @ "
                << congestion_event.event_time;

  return false;
}

bool Bbr2NetworkModel::CheckPersistentQueue(
    const Bbr2CongestionEvent& congestion_event, float bdp_gain) {
  QUICHE_DCHECK(congestion_event.end_of_round_trip);
  QUICHE_DCHECK_NE(min_bytes_in_flight_in_round_,
                   std::numeric_limits<uint64_t>::max());
  QuicByteCount target = bdp_gain * BDP();
  if (bdp_gain >= 2) {
    // Use a more conservative threshold for STARTUP because CWND gain is 2.
    if (target <= QueueingThresholdExtraBytes()) {
      return false;
    }
    target -= QueueingThresholdExtraBytes();
  } else {
    target += QueueingThresholdExtraBytes();
  }
  if (min_bytes_in_flight_in_round_ > target) {
    full_bandwidth_reached_ = true;
    return true;
  }
  return false;
}

}  // namespace quic