// Copyright (c) 2017 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/quic_control_frame_manager.h"

#include <string>

#include "absl/strings/str_cat.h"
#include "quiche/quic/core/frames/quic_ack_frequency_frame.h"
#include "quiche/quic/core/frames/quic_frame.h"
#include "quiche/quic/core/frames/quic_new_connection_id_frame.h"
#include "quiche/quic/core/frames/quic_retire_connection_id_frame.h"
#include "quiche/quic/core/quic_constants.h"
#include "quiche/quic/core/quic_session.h"
#include "quiche/quic/core/quic_types.h"
#include "quiche/quic/core/quic_utils.h"
#include "quiche/quic/platform/api/quic_bug_tracker.h"
#include "quiche/quic/platform/api/quic_flag_utils.h"
#include "quiche/quic/platform/api/quic_flags.h"

namespace quic {

namespace {

// The maximum number of buffered control frames which are waiting to be ACKed
// or sent for the first time.
const size_t kMaxNumControlFrames = 1000;

}  // namespace

QuicControlFrameManager::QuicControlFrameManager(QuicSession* session)
    : last_control_frame_id_(kInvalidControlFrameId),
      least_unacked_(1),
      least_unsent_(1),
      delegate_(session) {}

QuicControlFrameManager::~QuicControlFrameManager() {
  while (!control_frames_.empty()) {
    DeleteFrame(&control_frames_.front());
    control_frames_.pop_front();
  }
}

void QuicControlFrameManager::WriteOrBufferQuicFrame(QuicFrame frame) {
  const bool had_buffered_frames = HasBufferedFrames();
  control_frames_.emplace_back(frame);
  if (control_frames_.size() > kMaxNumControlFrames) {
    delegate_->OnControlFrameManagerError(
        QUIC_TOO_MANY_BUFFERED_CONTROL_FRAMES,
        absl::StrCat("More than ", kMaxNumControlFrames,
                     "buffered control frames, least_unacked: ", least_unacked_,
                     ", least_unsent_: ", least_unsent_));
    return;
  }
  if (had_buffered_frames) {
    return;
  }
  WriteBufferedFrames();
}

void QuicControlFrameManager::WriteOrBufferRstStream(
    QuicStreamId id, QuicResetStreamError error,
    QuicStreamOffset bytes_written) {
  QUIC_DVLOG(1) << "Writing RST_STREAM_FRAME";
  WriteOrBufferQuicFrame((QuicFrame(new QuicRstStreamFrame(
      ++last_control_frame_id_, id, error, bytes_written))));
}

void QuicControlFrameManager::WriteOrBufferGoAway(
    QuicErrorCode error, QuicStreamId last_good_stream_id,
    const std::string& reason) {
  QUIC_DVLOG(1) << "Writing GOAWAY_FRAME";
  WriteOrBufferQuicFrame(QuicFrame(new QuicGoAwayFrame(
      ++last_control_frame_id_, error, last_good_stream_id, reason)));
}

void QuicControlFrameManager::WriteOrBufferWindowUpdate(
    QuicStreamId id, QuicStreamOffset byte_offset) {
  QUIC_DVLOG(1) << "Writing WINDOW_UPDATE_FRAME";
  WriteOrBufferQuicFrame(QuicFrame(
      QuicWindowUpdateFrame(++last_control_frame_id_, id, byte_offset)));
}

void QuicControlFrameManager::WriteOrBufferBlocked(
    QuicStreamId id, QuicStreamOffset byte_offset) {
  QUIC_DVLOG(1) << "Writing BLOCKED_FRAME";
  if (GetQuicReloadableFlag(quic_include_offset_in_blocked_frames)) {
    QUIC_RELOADABLE_FLAG_COUNT(quic_include_offset_in_blocked_frames);
    WriteOrBufferQuicFrame(
        QuicFrame(QuicBlockedFrame(++last_control_frame_id_, id, byte_offset)));
  } else {
    WriteOrBufferQuicFrame(
        QuicFrame(QuicBlockedFrame(++last_control_frame_id_, id, 0)));
  }
}

void QuicControlFrameManager::WriteOrBufferStreamsBlocked(QuicStreamCount count,
                                                          bool unidirectional) {
  QUIC_DVLOG(1) << "Writing STREAMS_BLOCKED Frame";
  QUIC_CODE_COUNT(quic_streams_blocked_transmits);
  WriteOrBufferQuicFrame(QuicFrame(QuicStreamsBlockedFrame(
      ++last_control_frame_id_, count, unidirectional)));
}

void QuicControlFrameManager::WriteOrBufferMaxStreams(QuicStreamCount count,
                                                      bool unidirectional) {
  QUIC_DVLOG(1) << "Writing MAX_STREAMS Frame";
  QUIC_CODE_COUNT(quic_max_streams_transmits);
  WriteOrBufferQuicFrame(QuicFrame(
      QuicMaxStreamsFrame(++last_control_frame_id_, count, unidirectional)));
}

void QuicControlFrameManager::WriteOrBufferStopSending(
    QuicResetStreamError error, QuicStreamId stream_id) {
  QUIC_DVLOG(1) << "Writing STOP_SENDING_FRAME";
  WriteOrBufferQuicFrame(QuicFrame(
      QuicStopSendingFrame(++last_control_frame_id_, stream_id, error)));
}

void QuicControlFrameManager::WriteOrBufferHandshakeDone() {
  QUIC_DVLOG(1) << "Writing HANDSHAKE_DONE";
  WriteOrBufferQuicFrame(
      QuicFrame(QuicHandshakeDoneFrame(++last_control_frame_id_)));
}

void QuicControlFrameManager::WriteOrBufferAckFrequency(
    const QuicAckFrequencyFrame& ack_frequency_frame) {
  QUIC_DVLOG(1) << "Writing ACK_FREQUENCY frame";
  QuicControlFrameId control_frame_id = ++last_control_frame_id_;
  // Using the control_frame_id for sequence_number here leaves gaps in
  // sequence_number.
  WriteOrBufferQuicFrame(
      QuicFrame(new QuicAckFrequencyFrame(control_frame_id,
                                          /*sequence_number=*/control_frame_id,
                                          ack_frequency_frame.packet_tolerance,
                                          ack_frequency_frame.max_ack_delay)));
}

void QuicControlFrameManager::WriteOrBufferNewConnectionId(
    const QuicConnectionId& connection_id, uint64_t sequence_number,
    uint64_t retire_prior_to,
    const StatelessResetToken& stateless_reset_token) {
  QUIC_DVLOG(1) << "Writing NEW_CONNECTION_ID frame";
  WriteOrBufferQuicFrame(QuicFrame(new QuicNewConnectionIdFrame(
      ++last_control_frame_id_, connection_id, sequence_number,
      stateless_reset_token, retire_prior_to)));
}

void QuicControlFrameManager::WriteOrBufferRetireConnectionId(
    uint64_t sequence_number) {
  QUIC_DVLOG(1) << "Writing RETIRE_CONNECTION_ID frame";
  WriteOrBufferQuicFrame(QuicFrame(new QuicRetireConnectionIdFrame(
      ++last_control_frame_id_, sequence_number)));
}

void QuicControlFrameManager::WriteOrBufferNewToken(absl::string_view token) {
  QUIC_DVLOG(1) << "Writing NEW_TOKEN frame";
  WriteOrBufferQuicFrame(
      QuicFrame(new QuicNewTokenFrame(++last_control_frame_id_, token)));
}

void QuicControlFrameManager::OnControlFrameSent(const QuicFrame& frame) {
  QuicControlFrameId id = GetControlFrameId(frame);
  if (id == kInvalidControlFrameId) {
    QUIC_BUG(quic_bug_12727_1)
        << "Send or retransmit a control frame with invalid control frame id";
    return;
  }
  if (frame.type == WINDOW_UPDATE_FRAME) {
    QuicStreamId stream_id = frame.window_update_frame.stream_id;
    if (window_update_frames_.contains(stream_id) &&
        id > window_update_frames_[stream_id]) {
      // Consider the older window update of the same stream as acked.
      OnControlFrameIdAcked(window_update_frames_[stream_id]);
    }
    window_update_frames_[stream_id] = id;
  }
  if (pending_retransmissions_.contains(id)) {
    // This is retransmitted control frame.
    pending_retransmissions_.erase(id);
    return;
  }
  if (id > least_unsent_) {
    QUIC_BUG(quic_bug_10517_1)
        << "Try to send control frames out of order, id: " << id
        << " least_unsent: " << least_unsent_;
    delegate_->OnControlFrameManagerError(
        QUIC_INTERNAL_ERROR, "Try to send control frames out of order");
    return;
  }
  ++least_unsent_;
}

bool QuicControlFrameManager::OnControlFrameAcked(const QuicFrame& frame) {
  QuicControlFrameId id = GetControlFrameId(frame);
  if (!OnControlFrameIdAcked(id)) {
    return false;
  }
  if (frame.type == WINDOW_UPDATE_FRAME) {
    QuicStreamId stream_id = frame.window_update_frame.stream_id;
    if (window_update_frames_.contains(stream_id) &&
        window_update_frames_[stream_id] == id) {
      window_update_frames_.erase(stream_id);
    }
  }
  return true;
}

void QuicControlFrameManager::OnControlFrameLost(const QuicFrame& frame) {
  QuicControlFrameId id = GetControlFrameId(frame);
  if (id == kInvalidControlFrameId) {
    // Frame does not have a valid control frame ID, ignore it.
    return;
  }
  if (id >= least_unsent_) {
    QUIC_BUG(quic_bug_10517_2) << "Try to mark unsent control frame as lost";
    delegate_->OnControlFrameManagerError(
        QUIC_INTERNAL_ERROR, "Try to mark unsent control frame as lost");
    return;
  }
  if (id < least_unacked_ ||
      GetControlFrameId(control_frames_.at(id - least_unacked_)) ==
          kInvalidControlFrameId) {
    // This frame has already been acked.
    return;
  }
  if (!pending_retransmissions_.contains(id)) {
    pending_retransmissions_[id] = true;
    QUIC_BUG_IF(quic_bug_12727_2,
                pending_retransmissions_.size() > control_frames_.size())
        << "least_unacked_: " << least_unacked_
        << ", least_unsent_: " << least_unsent_;
  }
}

bool QuicControlFrameManager::IsControlFrameOutstanding(
    const QuicFrame& frame) const {
  QuicControlFrameId id = GetControlFrameId(frame);
  if (id == kInvalidControlFrameId) {
    // Frame without a control frame ID should not be retransmitted.
    return false;
  }
  // Consider this frame is outstanding if it does not get acked.
  return id < least_unacked_ + control_frames_.size() && id >= least_unacked_ &&
         GetControlFrameId(control_frames_.at(id - least_unacked_)) !=
             kInvalidControlFrameId;
}

bool QuicControlFrameManager::HasPendingRetransmission() const {
  return !pending_retransmissions_.empty();
}

bool QuicControlFrameManager::WillingToWrite() const {
  return HasPendingRetransmission() || HasBufferedFrames();
}

QuicFrame QuicControlFrameManager::NextPendingRetransmission() const {
  QUIC_BUG_IF(quic_bug_12727_3, pending_retransmissions_.empty())
      << "Unexpected call to NextPendingRetransmission() with empty pending "
      << "retransmission list.";
  QuicControlFrameId id = pending_retransmissions_.begin()->first;
  return control_frames_.at(id - least_unacked_);
}

void QuicControlFrameManager::OnCanWrite() {
  if (HasPendingRetransmission()) {
    // Exit early to allow streams to write pending retransmissions if any.
    WritePendingRetransmission();
    return;
  }
  WriteBufferedFrames();
}

bool QuicControlFrameManager::RetransmitControlFrame(const QuicFrame& frame,
                                                     TransmissionType type) {
  QUICHE_DCHECK(type == PTO_RETRANSMISSION || type == PROBING_RETRANSMISSION);
  QuicControlFrameId id = GetControlFrameId(frame);
  if (id == kInvalidControlFrameId) {
    // Frame does not have a valid control frame ID, ignore it. Returns true
    // to allow writing following frames.
    return true;
  }
  if (id >= least_unsent_) {
    QUIC_BUG(quic_bug_10517_3) << "Try to retransmit unsent control frame";
    delegate_->OnControlFrameManagerError(
        QUIC_INTERNAL_ERROR, "Try to retransmit unsent control frame");
    return false;
  }
  if (id < least_unacked_ ||
      GetControlFrameId(control_frames_.at(id - least_unacked_)) ==
          kInvalidControlFrameId) {
    // This frame has already been acked.
    return true;
  }
  QuicFrame copy = CopyRetransmittableControlFrame(frame);
  QUIC_DVLOG(1) << "control frame manager is forced to retransmit frame: "
                << frame;
  if (delegate_->WriteControlFrame(copy, type)) {
    return true;
  }
  DeleteFrame(&copy);
  return false;
}

void QuicControlFrameManager::WriteBufferedFrames() {
  while (HasBufferedFrames()) {
    QuicFrame frame_to_send =
        control_frames_.at(least_unsent_ - least_unacked_);
    QuicFrame copy = CopyRetransmittableControlFrame(frame_to_send);
    if (!delegate_->WriteControlFrame(copy, NOT_RETRANSMISSION)) {
      // Connection is write blocked.
      DeleteFrame(&copy);
      break;
    }
    OnControlFrameSent(frame_to_send);
  }
}

void QuicControlFrameManager::WritePendingRetransmission() {
  while (HasPendingRetransmission()) {
    QuicFrame pending = NextPendingRetransmission();
    QuicFrame copy = CopyRetransmittableControlFrame(pending);
    if (!delegate_->WriteControlFrame(copy, LOSS_RETRANSMISSION)) {
      // Connection is write blocked.
      DeleteFrame(&copy);
      break;
    }
    OnControlFrameSent(pending);
  }
}

bool QuicControlFrameManager::OnControlFrameIdAcked(QuicControlFrameId id) {
  if (id == kInvalidControlFrameId) {
    // Frame does not have a valid control frame ID, ignore it.
    return false;
  }
  if (id >= least_unsent_) {
    QUIC_BUG(quic_bug_10517_4) << "Try to ack unsent control frame";
    delegate_->OnControlFrameManagerError(QUIC_INTERNAL_ERROR,
                                          "Try to ack unsent control frame");
    return false;
  }
  if (id < least_unacked_ ||
      GetControlFrameId(control_frames_.at(id - least_unacked_)) ==
          kInvalidControlFrameId) {
    // This frame has already been acked.
    return false;
  }

  // Set control frame ID of acked frames to 0.
  SetControlFrameId(kInvalidControlFrameId,
                    &control_frames_.at(id - least_unacked_));
  // Remove acked control frames from pending retransmissions.
  pending_retransmissions_.erase(id);
  // Clean up control frames queue and increment least_unacked_.
  while (!control_frames_.empty() &&
         GetControlFrameId(control_frames_.front()) == kInvalidControlFrameId) {
    DeleteFrame(&control_frames_.front());
    control_frames_.pop_front();
    ++least_unacked_;
  }
  return true;
}

bool QuicControlFrameManager::HasBufferedFrames() const {
  return least_unsent_ < least_unacked_ + control_frames_.size();
}

}  // namespace quic