/*
 *  Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
 *
 *  Use of this source code is governed by a BSD-style license
 *  that can be found in the LICENSE file in the root of the source
 *  tree. An additional intellectual property rights grant can be found
 *  in the file PATENTS.  All contributing project authors may
 *  be found in the AUTHORS file in the root of the source tree.
 */
#include "net/dcsctp/tx/outstanding_data.h"

#include <algorithm>
#include <set>
#include <utility>
#include <vector>

#include "api/units/time_delta.h"
#include "api/units/timestamp.h"
#include "net/dcsctp/common/math.h"
#include "net/dcsctp/common/sequence_numbers.h"
#include "net/dcsctp/public/types.h"
#include "rtc_base/checks.h"
#include "rtc_base/logging.h"

namespace dcsctp {
using ::webrtc::Timestamp;

// The number of times a packet must be NACKed before it's retransmitted.
// See https://tools.ietf.org/html/rfc4960#section-7.2.4
constexpr uint8_t kNumberOfNacksForRetransmission = 3;

// Returns how large a chunk will be, serialized, carrying the data
size_t OutstandingData::GetSerializedChunkSize(const Data& data) const {
  return RoundUpTo4(data_chunk_header_size_ + data.size());
}

void OutstandingData::Item::Ack() {
  if (lifecycle_ != Lifecycle::kAbandoned) {
    lifecycle_ = Lifecycle::kActive;
  }
  ack_state_ = AckState::kAcked;
}

OutstandingData::Item::NackAction OutstandingData::Item::Nack(
    bool retransmit_now) {
  ack_state_ = AckState::kNacked;
  ++nack_count_;
  if (!should_be_retransmitted() && !is_abandoned() &&
      (retransmit_now || nack_count_ >= kNumberOfNacksForRetransmission)) {
    // Nacked enough times - it's considered lost.
    if (num_retransmissions_ < *max_retransmissions_) {
      lifecycle_ = Lifecycle::kToBeRetransmitted;
      return NackAction::kRetransmit;
    }
    Abandon();
    return NackAction::kAbandon;
  }
  return NackAction::kNothing;
}

void OutstandingData::Item::MarkAsRetransmitted() {
  lifecycle_ = Lifecycle::kActive;
  ack_state_ = AckState::kUnacked;

  nack_count_ = 0;
  ++num_retransmissions_;
}

void OutstandingData::Item::Abandon() {
  RTC_DCHECK(!expires_at_.IsPlusInfinity() ||
             max_retransmissions_ != MaxRetransmits::NoLimit());
  lifecycle_ = Lifecycle::kAbandoned;
}

bool OutstandingData::Item::has_expired(Timestamp now) const {
  return expires_at_ <= now;
}

bool OutstandingData::IsConsistent() const {
  size_t actual_unacked_bytes = 0;
  size_t actual_unacked_items = 0;

  std::set<UnwrappedTSN> combined_to_be_retransmitted;
  combined_to_be_retransmitted.insert(to_be_retransmitted_.begin(),
                                      to_be_retransmitted_.end());
  combined_to_be_retransmitted.insert(to_be_fast_retransmitted_.begin(),
                                      to_be_fast_retransmitted_.end());

  std::set<UnwrappedTSN> actual_combined_to_be_retransmitted;
  UnwrappedTSN tsn = last_cumulative_tsn_ack_;
  for (const Item& item : outstanding_data_) {
    tsn.Increment();
    if (item.is_outstanding()) {
      actual_unacked_bytes += GetSerializedChunkSize(item.data());
      ++actual_unacked_items;
    }

    if (item.should_be_retransmitted()) {
      actual_combined_to_be_retransmitted.insert(tsn);
    }
  }

  return actual_unacked_bytes == unacked_bytes_ &&
         actual_unacked_items == unacked_items_ &&
         actual_combined_to_be_retransmitted == combined_to_be_retransmitted;
}

void OutstandingData::AckChunk(AckInfo& ack_info,
                               UnwrappedTSN tsn,
                               Item& item) {
  if (!item.is_acked()) {
    size_t serialized_size = GetSerializedChunkSize(item.data());
    ack_info.bytes_acked += serialized_size;
    if (item.is_outstanding()) {
      unacked_bytes_ -= serialized_size;
      --unacked_items_;
    }
    if (item.should_be_retransmitted()) {
      RTC_DCHECK(to_be_fast_retransmitted_.find(tsn) ==
                 to_be_fast_retransmitted_.end());
      to_be_retransmitted_.erase(tsn);
    }
    item.Ack();
    ack_info.highest_tsn_acked = std::max(ack_info.highest_tsn_acked, tsn);
  }
}

OutstandingData::AckInfo OutstandingData::HandleSack(
    UnwrappedTSN cumulative_tsn_ack,
    rtc::ArrayView<const SackChunk::GapAckBlock> gap_ack_blocks,
    bool is_in_fast_recovery) {
  OutstandingData::AckInfo ack_info(cumulative_tsn_ack);
  // Erase all items up to cumulative_tsn_ack.
  RemoveAcked(cumulative_tsn_ack, ack_info);

  // ACK packets reported in the gap ack blocks
  AckGapBlocks(cumulative_tsn_ack, gap_ack_blocks, ack_info);

  // NACK and possibly mark for retransmit chunks that weren't acked.
  NackBetweenAckBlocks(cumulative_tsn_ack, gap_ack_blocks, is_in_fast_recovery,
                       ack_info);

  RTC_DCHECK(IsConsistent());
  return ack_info;
}

OutstandingData::Item& OutstandingData::GetItem(UnwrappedTSN tsn) {
  RTC_DCHECK(tsn > last_cumulative_tsn_ack_);
  RTC_DCHECK(tsn < next_tsn());
  int index = UnwrappedTSN::Difference(tsn, last_cumulative_tsn_ack_) - 1;
  RTC_DCHECK(index >= 0);
  RTC_DCHECK(index < static_cast<int>(outstanding_data_.size()));
  return outstanding_data_[index];
}

const OutstandingData::Item& OutstandingData::GetItem(UnwrappedTSN tsn) const {
  RTC_DCHECK(tsn > last_cumulative_tsn_ack_);
  RTC_DCHECK(tsn < next_tsn());
  int index = UnwrappedTSN::Difference(tsn, last_cumulative_tsn_ack_) - 1;
  RTC_DCHECK(index >= 0);
  RTC_DCHECK(index < static_cast<int>(outstanding_data_.size()));
  return outstanding_data_[index];
}

void OutstandingData::RemoveAcked(UnwrappedTSN cumulative_tsn_ack,
                                  AckInfo& ack_info) {
  while (!outstanding_data_.empty() &&
         last_cumulative_tsn_ack_ < cumulative_tsn_ack) {
    UnwrappedTSN tsn = last_cumulative_tsn_ack_.next_value();
    Item& item = outstanding_data_.front();
    AckChunk(ack_info, tsn, item);
    if (item.lifecycle_id().IsSet()) {
      RTC_DCHECK(item.data().is_end);
      if (item.is_abandoned()) {
        ack_info.abandoned_lifecycle_ids.push_back(item.lifecycle_id());
      } else {
        ack_info.acked_lifecycle_ids.push_back(item.lifecycle_id());
      }
    }
    outstanding_data_.pop_front();
    last_cumulative_tsn_ack_.Increment();
  }

  stream_reset_breakpoint_tsns_.erase(stream_reset_breakpoint_tsns_.begin(),
                                      stream_reset_breakpoint_tsns_.upper_bound(
                                          cumulative_tsn_ack.next_value()));
}

void OutstandingData::AckGapBlocks(
    UnwrappedTSN cumulative_tsn_ack,
    rtc::ArrayView<const SackChunk::GapAckBlock> gap_ack_blocks,
    AckInfo& ack_info) {
  // Mark all non-gaps as ACKED (but they can't be removed) as (from RFC)
  // "SCTP considers the information carried in the Gap Ack Blocks in the
  // SACK chunk as advisory.". Note that when NR-SACK is supported, this can be
  // handled differently.

  for (auto& block : gap_ack_blocks) {
    UnwrappedTSN start = UnwrappedTSN::AddTo(cumulative_tsn_ack, block.start);
    UnwrappedTSN end = UnwrappedTSN::AddTo(cumulative_tsn_ack, block.end);
    for (UnwrappedTSN tsn = start; tsn <= end; tsn = tsn.next_value()) {
      if (tsn > last_cumulative_tsn_ack_ && tsn < next_tsn()) {
        Item& item = GetItem(tsn);
        AckChunk(ack_info, tsn, item);
      }
    }
  }
}

void OutstandingData::NackBetweenAckBlocks(
    UnwrappedTSN cumulative_tsn_ack,
    rtc::ArrayView<const SackChunk::GapAckBlock> gap_ack_blocks,
    bool is_in_fast_recovery,
    OutstandingData::AckInfo& ack_info) {
  // Mark everything between the blocks as NACKED/TO_BE_RETRANSMITTED.
  // https://tools.ietf.org/html/rfc4960#section-7.2.4
  // "Mark the DATA chunk(s) with three miss indications for retransmission."
  // "For each incoming SACK, miss indications are incremented only for
  // missing TSNs prior to the highest TSN newly acknowledged in the SACK."
  //
  // What this means is that only when there is a increasing stream of data
  // received and there are new packets seen (since last time), packets that are
  // in-flight and between gaps should be nacked. This means that SCTP relies on
  // the T3-RTX-timer to re-send packets otherwise.
  UnwrappedTSN max_tsn_to_nack = ack_info.highest_tsn_acked;
  if (is_in_fast_recovery && cumulative_tsn_ack > last_cumulative_tsn_ack_) {
    // https://tools.ietf.org/html/rfc4960#section-7.2.4
    // "If an endpoint is in Fast Recovery and a SACK arrives that advances
    // the Cumulative TSN Ack Point, the miss indications are incremented for
    // all TSNs reported missing in the SACK."
    max_tsn_to_nack = UnwrappedTSN::AddTo(
        cumulative_tsn_ack,
        gap_ack_blocks.empty() ? 0 : gap_ack_blocks.rbegin()->end);
  }

  UnwrappedTSN prev_block_last_acked = cumulative_tsn_ack;
  for (auto& block : gap_ack_blocks) {
    UnwrappedTSN cur_block_first_acked =
        UnwrappedTSN::AddTo(cumulative_tsn_ack, block.start);
    for (UnwrappedTSN tsn = prev_block_last_acked.next_value();
         tsn < cur_block_first_acked && tsn <= max_tsn_to_nack;
         tsn = tsn.next_value()) {
      ack_info.has_packet_loss |=
          NackItem(tsn, /*retransmit_now=*/false,
                   /*do_fast_retransmit=*/!is_in_fast_recovery);
    }
    prev_block_last_acked = UnwrappedTSN::AddTo(cumulative_tsn_ack, block.end);
  }

  // Note that packets are not NACKED which are above the highest gap-ack-block
  // (or above the cumulative ack TSN if no gap-ack-blocks) as only packets
  // up until the highest_tsn_acked (see above) should be considered when
  // NACKing.
}

bool OutstandingData::NackItem(UnwrappedTSN tsn,
                               bool retransmit_now,
                               bool do_fast_retransmit) {
  Item& item = GetItem(tsn);
  if (item.is_outstanding()) {
    unacked_bytes_ -= GetSerializedChunkSize(item.data());
    --unacked_items_;
  }

  switch (item.Nack(retransmit_now)) {
    case Item::NackAction::kNothing:
      return false;
    case Item::NackAction::kRetransmit:
      if (do_fast_retransmit) {
        to_be_fast_retransmitted_.insert(tsn);
      } else {
        to_be_retransmitted_.insert(tsn);
      }
      RTC_DLOG(LS_VERBOSE) << *tsn.Wrap() << " marked for retransmission";
      break;
    case Item::NackAction::kAbandon:
      RTC_DLOG(LS_VERBOSE) << *tsn.Wrap() << " Nacked, resulted in abandoning";
      AbandonAllFor(item);
      break;
  }
  return true;
}

void OutstandingData::AbandonAllFor(const Item& item) {
  // Erase all remaining chunks from the producer, if any.
  if (discard_from_send_queue_(item.data().stream_id, item.message_id())) {
    // There were remaining chunks to be produced for this message. Since the
    // receiver may have already received all chunks (up till now) for this
    // message, we can't just FORWARD-TSN to the last fragment in this
    // (abandoned) message and start sending a new message, as the receiver will
    // then see a new message before the end of the previous one was seen (or
    // skipped over). So create a new fragment, representing the end, that the
    // received will never see as it is abandoned immediately and used as cum
    // TSN in the sent FORWARD-TSN.
    Data message_end(item.data().stream_id, item.data().ssn, item.data().mid,
                     item.data().fsn, item.data().ppid, std::vector<uint8_t>(),
                     Data::IsBeginning(false), Data::IsEnd(true),
                     item.data().is_unordered);
    UnwrappedTSN tsn = next_tsn();
    Item& added_item = outstanding_data_.emplace_back(
        item.message_id(), std::move(message_end), Timestamp::Zero(),
        MaxRetransmits(0), Timestamp::PlusInfinity(), LifecycleId::NotSet());

    // The added chunk shouldn't be included in `unacked_bytes`, so set it
    // as acked.
    added_item.Ack();
    RTC_DLOG(LS_VERBOSE) << "Adding unsent end placeholder for message at tsn="
                         << *tsn.Wrap();
  }

  UnwrappedTSN tsn = last_cumulative_tsn_ack_;
  for (Item& other : outstanding_data_) {
    tsn.Increment();
    if (!other.is_abandoned() &&
        other.data().stream_id == item.data().stream_id &&
        other.message_id() == item.message_id()) {
      RTC_DLOG(LS_VERBOSE) << "Marking chunk " << *tsn.Wrap()
                           << " as abandoned";
      if (other.should_be_retransmitted()) {
        to_be_fast_retransmitted_.erase(tsn);
        to_be_retransmitted_.erase(tsn);
      }
      other.Abandon();
    }
  }
}

std::vector<std::pair<TSN, Data>> OutstandingData::ExtractChunksThatCanFit(
    std::set<UnwrappedTSN>& chunks,
    size_t max_size) {
  std::vector<std::pair<TSN, Data>> result;

  for (auto it = chunks.begin(); it != chunks.end();) {
    UnwrappedTSN tsn = *it;
    Item& item = GetItem(tsn);
    RTC_DCHECK(item.should_be_retransmitted());
    RTC_DCHECK(!item.is_outstanding());
    RTC_DCHECK(!item.is_abandoned());
    RTC_DCHECK(!item.is_acked());

    size_t serialized_size = GetSerializedChunkSize(item.data());
    if (serialized_size <= max_size) {
      item.MarkAsRetransmitted();
      result.emplace_back(tsn.Wrap(), item.data().Clone());
      max_size -= serialized_size;
      unacked_bytes_ += serialized_size;
      ++unacked_items_;
      it = chunks.erase(it);
    } else {
      ++it;
    }
    // No point in continuing if the packet is full.
    if (max_size <= data_chunk_header_size_) {
      break;
    }
  }
  return result;
}

std::vector<std::pair<TSN, Data>>
OutstandingData::GetChunksToBeFastRetransmitted(size_t max_size) {
  std::vector<std::pair<TSN, Data>> result =
      ExtractChunksThatCanFit(to_be_fast_retransmitted_, max_size);

  // https://datatracker.ietf.org/doc/html/rfc4960#section-7.2.4
  // "Those TSNs marked for retransmission due to the Fast-Retransmit algorithm
  // that did not fit in the sent datagram carrying K other TSNs are also marked
  // as ineligible for a subsequent Fast Retransmit.  However, as they are
  // marked for retransmission they will be retransmitted later on as soon as
  // cwnd allows."
  if (!to_be_fast_retransmitted_.empty()) {
    to_be_retransmitted_.insert(to_be_fast_retransmitted_.begin(),
                                to_be_fast_retransmitted_.end());
    to_be_fast_retransmitted_.clear();
  }

  RTC_DCHECK(IsConsistent());
  return result;
}

std::vector<std::pair<TSN, Data>> OutstandingData::GetChunksToBeRetransmitted(
    size_t max_size) {
  // Chunks scheduled for fast retransmission must be sent first.
  RTC_DCHECK(to_be_fast_retransmitted_.empty());
  return ExtractChunksThatCanFit(to_be_retransmitted_, max_size);
}

void OutstandingData::ExpireOutstandingChunks(Timestamp now) {
  UnwrappedTSN tsn = last_cumulative_tsn_ack_;
  for (const Item& item : outstanding_data_) {
    tsn.Increment();
    // Chunks that are nacked can be expired. Care should be taken not to expire
    // unacked (in-flight) chunks as they might have been received, but the SACK
    // is either delayed or in-flight and may be received later.
    if (item.is_abandoned()) {
      // Already abandoned.
    } else if (item.is_nacked() && item.has_expired(now)) {
      RTC_DLOG(LS_VERBOSE) << "Marking nacked chunk " << *tsn.Wrap()
                           << " and message " << *item.data().mid
                           << " as expired";
      AbandonAllFor(item);
    } else {
      // A non-expired chunk. No need to iterate any further.
      break;
    }
  }
  RTC_DCHECK(IsConsistent());
}

UnwrappedTSN OutstandingData::highest_outstanding_tsn() const {
  return UnwrappedTSN::AddTo(last_cumulative_tsn_ack_,
                             outstanding_data_.size());
}

std::optional<UnwrappedTSN> OutstandingData::Insert(
    OutgoingMessageId message_id,
    const Data& data,
    Timestamp time_sent,
    MaxRetransmits max_retransmissions,
    Timestamp expires_at,
    LifecycleId lifecycle_id) {
  // All chunks are always padded to be even divisible by 4.
  size_t chunk_size = GetSerializedChunkSize(data);
  unacked_bytes_ += chunk_size;
  ++unacked_items_;
  UnwrappedTSN tsn = next_tsn();
  Item& item = outstanding_data_.emplace_back(message_id, data.Clone(),
                                              time_sent, max_retransmissions,
                                              expires_at, lifecycle_id);

  if (item.has_expired(time_sent)) {
    // No need to send it - it was expired when it was in the send
    // queue.
    RTC_DLOG(LS_VERBOSE) << "Marking freshly produced chunk " << *tsn.Wrap()
                         << " and message " << *item.data().mid
                         << " as expired";
    AbandonAllFor(item);
    RTC_DCHECK(IsConsistent());
    return std::nullopt;
  }

  RTC_DCHECK(IsConsistent());
  return tsn;
}

void OutstandingData::NackAll() {
  UnwrappedTSN tsn = last_cumulative_tsn_ack_;
  // A two-pass algorithm is needed, as NackItem will invalidate iterators.
  std::vector<UnwrappedTSN> tsns_to_nack;
  for (Item& item : outstanding_data_) {
    tsn.Increment();
    if (!item.is_acked()) {
      tsns_to_nack.push_back(tsn);
    }
  }

  for (UnwrappedTSN tsn : tsns_to_nack) {
    NackItem(tsn, /*retransmit_now=*/true,
             /*do_fast_retransmit=*/false);
  }

  RTC_DCHECK(IsConsistent());
}

webrtc::TimeDelta OutstandingData::MeasureRTT(Timestamp now,
                                              UnwrappedTSN tsn) const {
  if (tsn > last_cumulative_tsn_ack_ && tsn < next_tsn()) {
    const Item& item = GetItem(tsn);
    if (!item.has_been_retransmitted()) {
      // https://tools.ietf.org/html/rfc4960#section-6.3.1
      // "Karn's algorithm: RTT measurements MUST NOT be made using
      // packets that were retransmitted (and thus for which it is ambiguous
      // whether the reply was for the first instance of the chunk or for a
      // later instance)"
      return now - item.time_sent();
    }
  }
  return webrtc::TimeDelta::PlusInfinity();
}

std::vector<std::pair<TSN, OutstandingData::State>>
OutstandingData::GetChunkStatesForTesting() const {
  std::vector<std::pair<TSN, State>> states;
  states.emplace_back(last_cumulative_tsn_ack_.Wrap(), State::kAcked);
  UnwrappedTSN tsn = last_cumulative_tsn_ack_;
  for (const Item& item : outstanding_data_) {
    tsn.Increment();
    State state;
    if (item.is_abandoned()) {
      state = State::kAbandoned;
    } else if (item.should_be_retransmitted()) {
      state = State::kToBeRetransmitted;
    } else if (item.is_acked()) {
      state = State::kAcked;
    } else if (item.is_outstanding()) {
      state = State::kInFlight;
    } else {
      state = State::kNacked;
    }

    states.emplace_back(tsn.Wrap(), state);
  }
  return states;
}

bool OutstandingData::ShouldSendForwardTsn() const {
  if (!outstanding_data_.empty()) {
    return outstanding_data_.front().is_abandoned();
  }
  return false;
}

ForwardTsnChunk OutstandingData::CreateForwardTsn() const {
  std::map<StreamID, SSN> skipped_per_ordered_stream;
  UnwrappedTSN new_cumulative_ack = last_cumulative_tsn_ack_;

  UnwrappedTSN tsn = last_cumulative_tsn_ack_;
  for (const Item& item : outstanding_data_) {
    tsn.Increment();
    if (stream_reset_breakpoint_tsns_.contains(tsn) ||
        (tsn != new_cumulative_ack.next_value()) || !item.is_abandoned()) {
      break;
    }
    new_cumulative_ack = tsn;
    if (!item.data().is_unordered &&
        item.data().ssn > skipped_per_ordered_stream[item.data().stream_id]) {
      skipped_per_ordered_stream[item.data().stream_id] = item.data().ssn;
    }
  }

  std::vector<ForwardTsnChunk::SkippedStream> skipped_streams;
  skipped_streams.reserve(skipped_per_ordered_stream.size());
  for (const auto& [stream_id, ssn] : skipped_per_ordered_stream) {
    skipped_streams.emplace_back(stream_id, ssn);
  }
  return ForwardTsnChunk(new_cumulative_ack.Wrap(), std::move(skipped_streams));
}

IForwardTsnChunk OutstandingData::CreateIForwardTsn() const {
  std::map<std::pair<IsUnordered, StreamID>, MID> skipped_per_stream;
  UnwrappedTSN new_cumulative_ack = last_cumulative_tsn_ack_;

  UnwrappedTSN tsn = last_cumulative_tsn_ack_;
  for (const Item& item : outstanding_data_) {
    tsn.Increment();
    if (stream_reset_breakpoint_tsns_.contains(tsn) ||
        (tsn != new_cumulative_ack.next_value()) || !item.is_abandoned()) {
      break;
    }
    new_cumulative_ack = tsn;
    std::pair<IsUnordered, StreamID> stream_id =
        std::make_pair(item.data().is_unordered, item.data().stream_id);

    if (item.data().mid > skipped_per_stream[stream_id]) {
      skipped_per_stream[stream_id] = item.data().mid;
    }
  }

  std::vector<IForwardTsnChunk::SkippedStream> skipped_streams;
  skipped_streams.reserve(skipped_per_stream.size());
  for (const auto& [stream, mid] : skipped_per_stream) {
    skipped_streams.emplace_back(stream.first, stream.second, mid);
  }

  return IForwardTsnChunk(new_cumulative_ack.Wrap(),
                          std::move(skipped_streams));
}

void OutstandingData::ResetSequenceNumbers(UnwrappedTSN last_cumulative_tsn) {
  RTC_DCHECK(outstanding_data_.empty());
  last_cumulative_tsn_ack_ = last_cumulative_tsn;
}

void OutstandingData::BeginResetStreams() {
  stream_reset_breakpoint_tsns_.insert(next_tsn());
}
}  // namespace dcsctp