blob: 167f5a04e766d86fcfd14305536904d70e75e5e3 [file] [log] [blame]
* 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 <stddef.h>
#include <stdint.h>
#include <cstdint>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include "absl/strings/string_view.h"
#include "net/dcsctp/common/sequence_numbers.h"
#include "net/dcsctp/packet/chunk/data_common.h"
#include "net/dcsctp/packet/chunk/sack_chunk.h"
#include "net/dcsctp/packet/data.h"
#include "net/dcsctp/timer/timer.h"
namespace dcsctp {
// Keeps track of received DATA chunks and handles all logic for _when_ to
// create SACKs and also _how_ to generate them.
// It only uses TSNs to track delivery and doesn't need to be aware of streams.
// SACKs are optimally sent every second packet on connections with no packet
// loss. When packet loss is detected, it's sent for every packet. When SACKs
// are not sent directly, a timer is used to send a SACK delayed (by RTO/2, or
// 200ms, whatever is smallest).
class DataTracker {
// The maximum number of duplicate TSNs that will be reported in a SACK.
static constexpr size_t kMaxDuplicateTsnReported = 20;
// The maximum number of gap-ack-blocks that will be reported in a SACK.
static constexpr size_t kMaxGapAckBlocksReported = 20;
// The maximum number of accepted in-flight DATA chunks. This indicates the
// maximum difference from this buffer's last cumulative ack TSN, and any
// received data. Data received beyond this limit will be dropped, which will
// force the transmitter to send data that actually increases the last
// cumulative acked TSN.
static constexpr uint32_t kMaxAcceptedOutstandingFragments = 100000;
explicit DataTracker(absl::string_view log_prefix,
Timer* delayed_ack_timer,
TSN peer_initial_tsn)
: log_prefix_(std::string(log_prefix) + "dtrack: "),
tsn_unwrapper_.Unwrap(TSN(*peer_initial_tsn - 1))) {}
// Indicates if the provided TSN is valid. If this return false, the data
// should be dropped and not added to any other buffers, which essentially
// means that there is intentional packet loss.
bool IsTSNValid(TSN tsn) const;
// Call for every incoming data chunk.
void Observe(TSN tsn,
AnyDataChunk::ImmediateAckFlag immediate_ack =
// Called at the end of processing an SCTP packet.
void ObservePacketEnd();
// Called for incoming FORWARD-TSN/I-FORWARD-TSN chunks
void HandleForwardTsn(TSN new_cumulative_ack);
// Indicates if a SACK should be sent. There may be other reasons to send a
// SACK, but if this function indicates so, it should be sent as soon as
// possible. Calling this function will make it clear a flag so that if it's
// called again, it will probably return false.
// If the delayed ack timer is running, this method will return false _unless_
// `also_if_delayed` is set to true. Then it will return true as well.
bool ShouldSendAck(bool also_if_delayed = false);
// Returns the last cumulative ack TSN - the last seen data chunk's TSN
// value before any packet loss was detected.
TSN last_cumulative_acked_tsn() const {
return TSN(last_cumulative_acked_tsn_.Wrap());
// Returns true if the received `tsn` would increase the cumulative ack TSN.
bool will_increase_cum_ack_tsn(TSN tsn) const;
// Forces `ShouldSendSack` to return true.
void ForceImmediateSack();
// Note that this will clear `duplicates_`, so every SackChunk that is
// consumed must be sent.
SackChunk CreateSelectiveAck(size_t a_rwnd);
void HandleDelayedAckTimerExpiry();
enum class AckState {
// No need to send an ACK.
// Has received data chunks (but not yet end of packet).
// Has received data chunks and the end of a packet. Delayed ack timer is
// running and a SACK will be sent on expiry, or if DATA is sent, or after
// next packet with data.
// Send a SACK immediately after handling this packet.
// Represents ranges of TSNs that have been received that are not directly
// following the last cumulative acked TSN. This information is returned to
// the sender in the "gap ack blocks" in the SACK chunk. The blocks are always
// non-overlapping and non-adjacent.
class AdditionalTsnBlocks {
// Represents an inclusive range of received TSNs, i.e. [first, last].
struct TsnRange {
TsnRange(UnwrappedTSN first, UnwrappedTSN last)
: first(first), last(last) {}
UnwrappedTSN first;
UnwrappedTSN last;
// Adds a TSN to the set. This will try to expand any existing block and
// might merge blocks to ensure that all blocks are non-adjacent. If a
// current block can't be expanded, a new block is created.
// The return value indicates if `tsn` was added. If false is returned, the
// `tsn` was already represented in one of the blocks.
bool Add(UnwrappedTSN tsn);
// Erases all TSNs up to, and including `tsn`. This will remove all blocks
// that are completely below `tsn` and may truncate a block where `tsn` is
// within that block. In that case, the frontmost block's start TSN will be
// the next following tsn after `tsn`.
void EraseTo(UnwrappedTSN tsn);
// Removes the first block. Must not be called on an empty set.
void PopFront();
const std::vector<TsnRange>& blocks() const { return blocks_; }
bool empty() const { return blocks_.empty(); }
const TsnRange& front() const { return blocks_.front(); }
// A sorted vector of non-overlapping and non-adjacent blocks.
std::vector<TsnRange> blocks_;
std::vector<SackChunk::GapAckBlock> CreateGapAckBlocks() const;
void UpdateAckState(AckState new_state, absl::string_view reason);
static absl::string_view ToString(AckState ack_state);
const std::string log_prefix_;
// If a packet has ever been seen.
bool seen_packet_ = false;
Timer& delayed_ack_timer_;
AckState ack_state_ = AckState::kIdle;
UnwrappedTSN::Unwrapper tsn_unwrapper_;
// All TSNs up until (and including) this value have been seen.
UnwrappedTSN last_cumulative_acked_tsn_;
// Received TSNs that are not directly following `last_cumulative_acked_tsn_`.
AdditionalTsnBlocks additional_tsn_blocks_;
std::set<TSN> duplicate_tsns_;
} // namespace dcsctp