blob: 9991ee6139f7344184dd8c173d8404d1a817946e [file] [log] [blame]
Victor Boivieb2d539b2021-04-01 21:36:031/*
2 * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10#ifndef NET_DCSCTP_RX_DATA_TRACKER_H_
11#define NET_DCSCTP_RX_DATA_TRACKER_H_
12
13#include <stddef.h>
14#include <stdint.h>
15
16#include <cstdint>
17#include <set>
18#include <string>
Victor Boivie27d2be32021-05-29 19:20:1219#include <utility>
Victor Boivieb2d539b2021-04-01 21:36:0320#include <vector>
21
22#include "absl/strings/string_view.h"
23#include "net/dcsctp/common/sequence_numbers.h"
24#include "net/dcsctp/packet/chunk/data_common.h"
25#include "net/dcsctp/packet/chunk/sack_chunk.h"
26#include "net/dcsctp/packet/data.h"
Sergey Sukhanov225cd472021-09-14 20:08:5327#include "net/dcsctp/public/dcsctp_handover_state.h"
Victor Boivieb2d539b2021-04-01 21:36:0328#include "net/dcsctp/timer/timer.h"
29
30namespace dcsctp {
31
32// Keeps track of received DATA chunks and handles all logic for _when_ to
33// create SACKs and also _how_ to generate them.
34//
35// It only uses TSNs to track delivery and doesn't need to be aware of streams.
36//
37// SACKs are optimally sent every second packet on connections with no packet
38// loss. When packet loss is detected, it's sent for every packet. When SACKs
39// are not sent directly, a timer is used to send a SACK delayed (by RTO/2, or
40// 200ms, whatever is smallest).
41class DataTracker {
42 public:
Victor Boiviec09c5812021-05-19 12:03:2243 // The maximum number of duplicate TSNs that will be reported in a SACK.
44 static constexpr size_t kMaxDuplicateTsnReported = 20;
45 // The maximum number of gap-ack-blocks that will be reported in a SACK.
46 static constexpr size_t kMaxGapAckBlocksReported = 20;
47
Victor Boiviec54f6722021-04-13 09:23:1648 // The maximum number of accepted in-flight DATA chunks. This indicates the
49 // maximum difference from this buffer's last cumulative ack TSN, and any
50 // received data. Data received beyond this limit will be dropped, which will
51 // force the transmitter to send data that actually increases the last
52 // cumulative acked TSN.
Victor Boivie261eec52021-05-29 19:27:2353 static constexpr uint32_t kMaxAcceptedOutstandingFragments = 100000;
Victor Boiviec54f6722021-04-13 09:23:1654
Sergey Sukhanov225cd472021-09-14 20:08:5355 DataTracker(absl::string_view log_prefix,
56 Timer* delayed_ack_timer,
Victor Boivie2cffde72022-06-27 20:35:3757 TSN peer_initial_tsn)
Victor Boivie4fbf5552022-09-09 10:25:3258 : log_prefix_(log_prefix),
Victor Boivie2cffde72022-06-27 20:35:3759 seen_packet_(false),
Victor Boivieb2d539b2021-04-01 21:36:0360 delayed_ack_timer_(*delayed_ack_timer),
Victor Boivie2cffde72022-06-27 20:35:3761 last_cumulative_acked_tsn_(
62 tsn_unwrapper_.Unwrap(TSN(*peer_initial_tsn - 1))) {}
Victor Boivieb2d539b2021-04-01 21:36:0363
Victor Boiviec54f6722021-04-13 09:23:1664 // Indicates if the provided TSN is valid. If this return false, the data
65 // should be dropped and not added to any other buffers, which essentially
66 // means that there is intentional packet loss.
67 bool IsTSNValid(TSN tsn) const;
68
Victor Boivie568bc232022-03-20 18:59:0369 // Call for every incoming data chunk. Returns `true` if `tsn` was seen for
70 // the first time, and `false` if it has been seen before (a duplicate `tsn`).
71 bool Observe(TSN tsn,
Victor Boivieb2d539b2021-04-01 21:36:0372 AnyDataChunk::ImmediateAckFlag immediate_ack =
73 AnyDataChunk::ImmediateAckFlag(false));
74 // Called at the end of processing an SCTP packet.
75 void ObservePacketEnd();
76
Victor Boiviea5574682023-09-25 11:32:5977 // Called for incoming FORWARD-TSN/I-FORWARD-TSN chunks. Indicates if the
78 // chunk had any effect.
79 bool HandleForwardTsn(TSN new_cumulative_ack);
Victor Boivieb2d539b2021-04-01 21:36:0380
81 // Indicates if a SACK should be sent. There may be other reasons to send a
82 // SACK, but if this function indicates so, it should be sent as soon as
83 // possible. Calling this function will make it clear a flag so that if it's
84 // called again, it will probably return false.
85 //
86 // If the delayed ack timer is running, this method will return false _unless_
87 // `also_if_delayed` is set to true. Then it will return true as well.
88 bool ShouldSendAck(bool also_if_delayed = false);
89
90 // Returns the last cumulative ack TSN - the last seen data chunk's TSN
91 // value before any packet loss was detected.
92 TSN last_cumulative_acked_tsn() const {
93 return TSN(last_cumulative_acked_tsn_.Wrap());
94 }
95
Victor Boivieb847a432023-09-27 16:01:1896 bool IsLaterThanCumulativeAckedTsn(TSN tsn) const {
97 return tsn_unwrapper_.PeekUnwrap(tsn) > last_cumulative_acked_tsn_;
98 }
99
Victor Boivieb2d539b2021-04-01 21:36:03100 // Returns true if the received `tsn` would increase the cumulative ack TSN.
101 bool will_increase_cum_ack_tsn(TSN tsn) const;
102
103 // Forces `ShouldSendSack` to return true.
104 void ForceImmediateSack();
105
106 // Note that this will clear `duplicates_`, so every SackChunk that is
107 // consumed must be sent.
108 SackChunk CreateSelectiveAck(size_t a_rwnd);
109
110 void HandleDelayedAckTimerExpiry();
111
Sergey Sukhanov225cd472021-09-14 20:08:53112 HandoverReadinessStatus GetHandoverReadiness() const;
113
114 void AddHandoverState(DcSctpSocketHandoverState& state);
Victor Boivie2cffde72022-06-27 20:35:37115 void RestoreFromState(const DcSctpSocketHandoverState& state);
Sergey Sukhanov225cd472021-09-14 20:08:53116
Victor Boivieb2d539b2021-04-01 21:36:03117 private:
118 enum class AckState {
119 // No need to send an ACK.
120 kIdle,
121
122 // Has received data chunks (but not yet end of packet).
123 kBecomingDelayed,
124
125 // Has received data chunks and the end of a packet. Delayed ack timer is
126 // running and a SACK will be sent on expiry, or if DATA is sent, or after
127 // next packet with data.
128 kDelayed,
129
130 // Send a SACK immediately after handling this packet.
131 kImmediate,
132 };
Victor Boivie27d2be32021-05-29 19:20:12133
134 // Represents ranges of TSNs that have been received that are not directly
135 // following the last cumulative acked TSN. This information is returned to
136 // the sender in the "gap ack blocks" in the SACK chunk. The blocks are always
137 // non-overlapping and non-adjacent.
138 class AdditionalTsnBlocks {
139 public:
140 // Represents an inclusive range of received TSNs, i.e. [first, last].
141 struct TsnRange {
142 TsnRange(UnwrappedTSN first, UnwrappedTSN last)
143 : first(first), last(last) {}
144 UnwrappedTSN first;
145 UnwrappedTSN last;
146 };
147
148 // Adds a TSN to the set. This will try to expand any existing block and
149 // might merge blocks to ensure that all blocks are non-adjacent. If a
150 // current block can't be expanded, a new block is created.
151 //
152 // The return value indicates if `tsn` was added. If false is returned, the
153 // `tsn` was already represented in one of the blocks.
154 bool Add(UnwrappedTSN tsn);
155
156 // Erases all TSNs up to, and including `tsn`. This will remove all blocks
157 // that are completely below `tsn` and may truncate a block where `tsn` is
158 // within that block. In that case, the frontmost block's start TSN will be
159 // the next following tsn after `tsn`.
160 void EraseTo(UnwrappedTSN tsn);
161
162 // Removes the first block. Must not be called on an empty set.
163 void PopFront();
164
165 const std::vector<TsnRange>& blocks() const { return blocks_; }
166
167 bool empty() const { return blocks_.empty(); }
168
169 const TsnRange& front() const { return blocks_.front(); }
170
171 private:
172 // A sorted vector of non-overlapping and non-adjacent blocks.
173 std::vector<TsnRange> blocks_;
174 };
175
Victor Boivieb2d539b2021-04-01 21:36:03176 std::vector<SackChunk::GapAckBlock> CreateGapAckBlocks() const;
177 void UpdateAckState(AckState new_state, absl::string_view reason);
178 static absl::string_view ToString(AckState ack_state);
179
Victor Boivie4fbf5552022-09-09 10:25:32180 const absl::string_view log_prefix_;
Victor Boivieb2d539b2021-04-01 21:36:03181 // If a packet has ever been seen.
Sergey Sukhanov225cd472021-09-14 20:08:53182 bool seen_packet_;
Victor Boivieb2d539b2021-04-01 21:36:03183 Timer& delayed_ack_timer_;
184 AckState ack_state_ = AckState::kIdle;
185 UnwrappedTSN::Unwrapper tsn_unwrapper_;
186
187 // All TSNs up until (and including) this value have been seen.
188 UnwrappedTSN last_cumulative_acked_tsn_;
189 // Received TSNs that are not directly following `last_cumulative_acked_tsn_`.
Victor Boivie27d2be32021-05-29 19:20:12190 AdditionalTsnBlocks additional_tsn_blocks_;
Victor Boivie3a45d322021-05-19 11:40:55191 std::set<TSN> duplicate_tsns_;
Victor Boivieb2d539b2021-04-01 21:36:03192};
193} // namespace dcsctp
194
195#endif // NET_DCSCTP_RX_DATA_TRACKER_H_