blob: 70b7587c43911635c98b182d7566b04e40b30640 [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#include "net/dcsctp/rx/data_tracker.h"
11
Victor Boivie27d2be32021-05-29 19:20:1212#include <algorithm>
Victor Boivieb2d539b2021-04-01 21:36:0313#include <cstdint>
14#include <iterator>
15#include <set>
16#include <string>
17#include <utility>
18#include <vector>
19
Victor Boivie27d2be32021-05-29 19:20:1220#include "absl/algorithm/container.h"
Victor Boivieb2d539b2021-04-01 21:36:0321#include "absl/strings/string_view.h"
22#include "absl/types/optional.h"
23#include "net/dcsctp/common/sequence_numbers.h"
24#include "net/dcsctp/packet/chunk/sack_chunk.h"
25#include "net/dcsctp/timer/timer.h"
26#include "rtc_base/logging.h"
27#include "rtc_base/strings/string_builder.h"
28
29namespace dcsctp {
30
Victor Boiviec09c5812021-05-19 12:03:2231constexpr size_t DataTracker::kMaxDuplicateTsnReported;
32constexpr size_t DataTracker::kMaxGapAckBlocksReported;
33
Victor Boivie27d2be32021-05-29 19:20:1234bool DataTracker::AdditionalTsnBlocks::Add(UnwrappedTSN tsn) {
35 // Find any block to expand. It will look for any block that includes (also
36 // when expanded) the provided `tsn`. It will return the block that is greater
37 // than, or equal to `tsn`.
38 auto it = absl::c_lower_bound(
39 blocks_, tsn, [&](const TsnRange& elem, const UnwrappedTSN& t) {
40 return elem.last.next_value() < t;
41 });
42
43 if (it == blocks_.end()) {
44 // No matching block found. There is no greater than, or equal block - which
45 // means that this TSN is greater than any block. It can then be inserted at
46 // the end.
47 blocks_.emplace_back(tsn, tsn);
48 return true;
49 }
50
51 if (tsn >= it->first && tsn <= it->last) {
52 // It's already in this block.
53 return false;
54 }
55
56 if (it->last.next_value() == tsn) {
57 // This block can be expanded to the right, or merged with the next.
58 auto next_it = it + 1;
59 if (next_it != blocks_.end() && tsn.next_value() == next_it->first) {
60 // Expanding it would make it adjacent to next block - merge those.
61 it->last = next_it->last;
62 blocks_.erase(next_it);
63 return true;
64 }
65
66 // Expand to the right
67 it->last = tsn;
68 return true;
69 }
70
71 if (it->first == tsn.next_value()) {
72 // This block can be expanded to the left. Merging to the left would've been
73 // covered by the above "merge to the right". Both blocks (expand a
74 // right-most block to the left and expand a left-most block to the right)
75 // would match, but the left-most would be returned by std::lower_bound.
76 RTC_DCHECK(it == blocks_.begin() || (it - 1)->last.next_value() != tsn);
77
78 // Expand to the left.
79 it->first = tsn;
80 return true;
81 }
82
83 // Need to create a new block in the middle.
84 blocks_.emplace(it, tsn, tsn);
85 return true;
86}
87
88void DataTracker::AdditionalTsnBlocks::EraseTo(UnwrappedTSN tsn) {
89 // Find the block that is greater than or equals `tsn`.
90 auto it = absl::c_lower_bound(
91 blocks_, tsn, [&](const TsnRange& elem, const UnwrappedTSN& t) {
92 return elem.last < t;
93 });
94
95 // The block that is found is greater or equal (or possibly ::end, when no
96 // block is greater or equal). All blocks before this block can be safely
97 // removed. the TSN might be within this block, so possibly truncate it.
98 bool tsn_is_within_block = it != blocks_.end() && tsn >= it->first;
99 blocks_.erase(blocks_.begin(), it);
100
101 if (tsn_is_within_block) {
102 blocks_.front().first = tsn.next_value();
103 }
104}
105
106void DataTracker::AdditionalTsnBlocks::PopFront() {
107 RTC_DCHECK(!blocks_.empty());
108 blocks_.erase(blocks_.begin());
109}
110
Victor Boiviec54f6722021-04-13 09:23:16111bool DataTracker::IsTSNValid(TSN tsn) const {
112 UnwrappedTSN unwrapped_tsn = tsn_unwrapper_.PeekUnwrap(tsn);
113
114 // Note that this method doesn't return `false` for old DATA chunks, as those
115 // are actually valid, and receiving those may affect the generated SACK
116 // response (by setting "duplicate TSNs").
117
118 uint32_t difference =
119 UnwrappedTSN::Difference(unwrapped_tsn, last_cumulative_acked_tsn_);
120 if (difference > kMaxAcceptedOutstandingFragments) {
121 return false;
122 }
123 return true;
124}
125
Victor Boivie568bc232022-03-20 18:59:03126bool DataTracker::Observe(TSN tsn,
Victor Boivieb2d539b2021-04-01 21:36:03127 AnyDataChunk::ImmediateAckFlag immediate_ack) {
Victor Boivie568bc232022-03-20 18:59:03128 bool is_duplicate = false;
Victor Boivieb2d539b2021-04-01 21:36:03129 UnwrappedTSN unwrapped_tsn = tsn_unwrapper_.Unwrap(tsn);
Victor Boiviec54f6722021-04-13 09:23:16130
131 // IsTSNValid must be called prior to calling this method.
132 RTC_DCHECK(
133 UnwrappedTSN::Difference(unwrapped_tsn, last_cumulative_acked_tsn_) <=
134 kMaxAcceptedOutstandingFragments);
135
Victor Boivieb2d539b2021-04-01 21:36:03136 // Old chunk already seen before?
137 if (unwrapped_tsn <= last_cumulative_acked_tsn_) {
Victor Boiviec09c5812021-05-19 12:03:22138 if (duplicate_tsns_.size() < kMaxDuplicateTsnReported) {
139 duplicate_tsns_.insert(unwrapped_tsn.Wrap());
140 }
Victor Boivie5d4c3c52021-05-28 15:21:39141 // https://datatracker.ietf.org/doc/html/rfc4960#section-6.2
142 // "When a packet arrives with duplicate DATA chunk(s) and with no new DATA
143 // chunk(s), the endpoint MUST immediately send a SACK with no delay. If a
144 // packet arrives with duplicate DATA chunk(s) bundled with new DATA chunks,
145 // the endpoint MAY immediately send a SACK."
146 UpdateAckState(AckState::kImmediate, "duplicate data");
Victor Boivie568bc232022-03-20 18:59:03147 is_duplicate = true;
Victor Boivieb2d539b2021-04-01 21:36:03148 } else {
Victor Boivie5d4c3c52021-05-28 15:21:39149 if (unwrapped_tsn == last_cumulative_acked_tsn_.next_value()) {
150 last_cumulative_acked_tsn_ = unwrapped_tsn;
151 // The cumulative acked tsn may be moved even further, if a gap was
152 // filled.
Victor Boivie27d2be32021-05-29 19:20:12153 if (!additional_tsn_blocks_.empty() &&
154 additional_tsn_blocks_.front().first ==
155 last_cumulative_acked_tsn_.next_value()) {
156 last_cumulative_acked_tsn_ = additional_tsn_blocks_.front().last;
157 additional_tsn_blocks_.PopFront();
Victor Boivie5d4c3c52021-05-28 15:21:39158 }
159 } else {
Victor Boivie27d2be32021-05-29 19:20:12160 bool inserted = additional_tsn_blocks_.Add(unwrapped_tsn);
Victor Boivie5d4c3c52021-05-28 15:21:39161 if (!inserted) {
162 // Already seen before.
163 if (duplicate_tsns_.size() < kMaxDuplicateTsnReported) {
164 duplicate_tsns_.insert(unwrapped_tsn.Wrap());
165 }
166 // https://datatracker.ietf.org/doc/html/rfc4960#section-6.2
167 // "When a packet arrives with duplicate DATA chunk(s) and with no new
168 // DATA chunk(s), the endpoint MUST immediately send a SACK with no
169 // delay. If a packet arrives with duplicate DATA chunk(s) bundled with
170 // new DATA chunks, the endpoint MAY immediately send a SACK."
171 // No need to do this. SACKs are sent immediately on packet loss below.
Victor Boivie568bc232022-03-20 18:59:03172 is_duplicate = true;
Victor Boiviec09c5812021-05-19 12:03:22173 }
Victor Boivie3a45d322021-05-19 11:40:55174 }
Victor Boivieb2d539b2021-04-01 21:36:03175 }
176
177 // https://tools.ietf.org/html/rfc4960#section-6.7
178 // "Upon the reception of a new DATA chunk, an endpoint shall examine the
179 // continuity of the TSNs received. If the endpoint detects a gap in
180 // the received DATA chunk sequence, it SHOULD send a SACK with Gap Ack
181 // Blocks immediately. The data receiver continues sending a SACK after
182 // receipt of each SCTP packet that doesn't fill the gap."
Victor Boivie27d2be32021-05-29 19:20:12183 if (!additional_tsn_blocks_.empty()) {
Victor Boivieb2d539b2021-04-01 21:36:03184 UpdateAckState(AckState::kImmediate, "packet loss");
185 }
186
187 // https://tools.ietf.org/html/rfc7053#section-5.2
188 // "Upon receipt of an SCTP packet containing a DATA chunk with the I
189 // bit set, the receiver SHOULD NOT delay the sending of the corresponding
190 // SACK chunk, i.e., the receiver SHOULD immediately respond with the
191 // corresponding SACK chunk."
192 if (*immediate_ack) {
193 UpdateAckState(AckState::kImmediate, "immediate-ack bit set");
194 }
195
196 if (!seen_packet_) {
197 // https://tools.ietf.org/html/rfc4960#section-5.1
198 // "After the reception of the first DATA chunk in an association the
199 // endpoint MUST immediately respond with a SACK to acknowledge the DATA
200 // chunk."
201 seen_packet_ = true;
202 UpdateAckState(AckState::kImmediate, "first DATA chunk");
203 }
204
205 // https://tools.ietf.org/html/rfc4960#section-6.2
206 // "Specifically, an acknowledgement SHOULD be generated for at least
207 // every second packet (not every second DATA chunk) received, and SHOULD be
208 // generated within 200 ms of the arrival of any unacknowledged DATA chunk."
209 if (ack_state_ == AckState::kIdle) {
210 UpdateAckState(AckState::kBecomingDelayed, "received DATA when idle");
211 } else if (ack_state_ == AckState::kDelayed) {
212 UpdateAckState(AckState::kImmediate, "received DATA when already delayed");
213 }
Victor Boivie568bc232022-03-20 18:59:03214 return !is_duplicate;
Victor Boivieb2d539b2021-04-01 21:36:03215}
216
Victor Boiviea5574682023-09-25 11:32:59217bool DataTracker::HandleForwardTsn(TSN new_cumulative_ack) {
Victor Boivieb2d539b2021-04-01 21:36:03218 // ForwardTSN is sent to make the receiver (this socket) "forget" about partly
219 // received (or not received at all) data, up until `new_cumulative_ack`.
220
221 UnwrappedTSN unwrapped_tsn = tsn_unwrapper_.Unwrap(new_cumulative_ack);
222 UnwrappedTSN prev_last_cum_ack_tsn = last_cumulative_acked_tsn_;
223
224 // Old chunk already seen before?
225 if (unwrapped_tsn <= last_cumulative_acked_tsn_) {
226 // https://tools.ietf.org/html/rfc3758#section-3.6
227 // "Note, if the "New Cumulative TSN" value carried in the arrived
228 // FORWARD TSN chunk is found to be behind or at the current cumulative TSN
229 // point, the data receiver MUST treat this FORWARD TSN as out-of-date and
230 // MUST NOT update its Cumulative TSN. The receiver SHOULD send a SACK to
231 // its peer (the sender of the FORWARD TSN) since such a duplicate may
232 // indicate the previous SACK was lost in the network."
233 UpdateAckState(AckState::kImmediate,
234 "FORWARD_TSN new_cumulative_tsn was behind");
Victor Boiviea5574682023-09-25 11:32:59235 return false;
Victor Boivieb2d539b2021-04-01 21:36:03236 }
237
238 // https://tools.ietf.org/html/rfc3758#section-3.6
239 // "When a FORWARD TSN chunk arrives, the data receiver MUST first update
240 // its cumulative TSN point to the value carried in the FORWARD TSN chunk, and
241 // then MUST further advance its cumulative TSN point locally if possible, as
242 // shown by the following example..."
243
244 // The `new_cumulative_ack` will become the current
245 // `last_cumulative_acked_tsn_`, and if there have been prior "gaps" that are
246 // now overlapping with the new value, remove them.
247 last_cumulative_acked_tsn_ = unwrapped_tsn;
Victor Boivie27d2be32021-05-29 19:20:12248 additional_tsn_blocks_.EraseTo(unwrapped_tsn);
Victor Boivieb2d539b2021-04-01 21:36:03249
250 // See if the `last_cumulative_acked_tsn_` can be moved even further:
Victor Boivie27d2be32021-05-29 19:20:12251 if (!additional_tsn_blocks_.empty() &&
252 additional_tsn_blocks_.front().first ==
253 last_cumulative_acked_tsn_.next_value()) {
254 last_cumulative_acked_tsn_ = additional_tsn_blocks_.front().last;
255 additional_tsn_blocks_.PopFront();
Victor Boivieb2d539b2021-04-01 21:36:03256 }
257
258 RTC_DLOG(LS_VERBOSE) << log_prefix_ << "FORWARD_TSN, cum_ack_tsn="
259 << *prev_last_cum_ack_tsn.Wrap() << "->"
260 << *new_cumulative_ack << "->"
Victor Boivie27d2be32021-05-29 19:20:12261 << *last_cumulative_acked_tsn_.Wrap();
Victor Boivieb2d539b2021-04-01 21:36:03262
263 // https://tools.ietf.org/html/rfc3758#section-3.6
264 // "Any time a FORWARD TSN chunk arrives, for the purposes of sending a
265 // SACK, the receiver MUST follow the same rules as if a DATA chunk had been
266 // received (i.e., follow the delayed sack rules specified in ..."
267 if (ack_state_ == AckState::kIdle) {
268 UpdateAckState(AckState::kBecomingDelayed,
269 "received FORWARD_TSN when idle");
270 } else if (ack_state_ == AckState::kDelayed) {
271 UpdateAckState(AckState::kImmediate,
272 "received FORWARD_TSN when already delayed");
273 }
Victor Boiviea5574682023-09-25 11:32:59274 return true;
Victor Boivieb2d539b2021-04-01 21:36:03275}
276
277SackChunk DataTracker::CreateSelectiveAck(size_t a_rwnd) {
278 // Note that in SCTP, the receiver side is allowed to discard received data
279 // and signal that to the sender, but only chunks that have previously been
280 // reported in the gap-ack-blocks. However, this implementation will never do
281 // that. So this SACK produced is more like a NR-SACK as explained in
282 // https://ieeexplore.ieee.org/document/4697037 and which there is an RFC
283 // draft at https://tools.ietf.org/html/draft-tuexen-tsvwg-sctp-multipath-17.
Victor Boivie3a45d322021-05-19 11:40:55284 std::set<TSN> duplicate_tsns;
285 duplicate_tsns_.swap(duplicate_tsns);
Victor Boivieb2d539b2021-04-01 21:36:03286
287 return SackChunk(last_cumulative_acked_tsn_.Wrap(), a_rwnd,
Victor Boivie3a45d322021-05-19 11:40:55288 CreateGapAckBlocks(), std::move(duplicate_tsns));
Victor Boivieb2d539b2021-04-01 21:36:03289}
290
291std::vector<SackChunk::GapAckBlock> DataTracker::CreateGapAckBlocks() const {
Victor Boivie27d2be32021-05-29 19:20:12292 const auto& blocks = additional_tsn_blocks_.blocks();
Victor Boivieb2d539b2021-04-01 21:36:03293 std::vector<SackChunk::GapAckBlock> gap_ack_blocks;
Victor Boivie27d2be32021-05-29 19:20:12294 gap_ack_blocks.reserve(std::min(blocks.size(), kMaxGapAckBlocksReported));
295 for (size_t i = 0; i < blocks.size() && i < kMaxGapAckBlocksReported; ++i) {
296 auto start_diff =
297 UnwrappedTSN::Difference(blocks[i].first, last_cumulative_acked_tsn_);
298 auto end_diff =
299 UnwrappedTSN::Difference(blocks[i].last, last_cumulative_acked_tsn_);
300 gap_ack_blocks.emplace_back(static_cast<uint16_t>(start_diff),
301 static_cast<uint16_t>(end_diff));
Victor Boivieb2d539b2021-04-01 21:36:03302 }
Victor Boivie27d2be32021-05-29 19:20:12303
Victor Boivieb2d539b2021-04-01 21:36:03304 return gap_ack_blocks;
305}
306
307bool DataTracker::ShouldSendAck(bool also_if_delayed) {
308 if (ack_state_ == AckState::kImmediate ||
309 (also_if_delayed && (ack_state_ == AckState::kBecomingDelayed ||
310 ack_state_ == AckState::kDelayed))) {
311 UpdateAckState(AckState::kIdle, "sending SACK");
312 return true;
313 }
314
315 return false;
316}
317
318bool DataTracker::will_increase_cum_ack_tsn(TSN tsn) const {
319 UnwrappedTSN unwrapped = tsn_unwrapper_.PeekUnwrap(tsn);
320 return unwrapped == last_cumulative_acked_tsn_.next_value();
321}
322
323void DataTracker::ForceImmediateSack() {
324 ack_state_ = AckState::kImmediate;
325}
326
327void DataTracker::HandleDelayedAckTimerExpiry() {
328 UpdateAckState(AckState::kImmediate, "delayed ack timer expired");
329}
330
331void DataTracker::ObservePacketEnd() {
332 if (ack_state_ == AckState::kBecomingDelayed) {
333 UpdateAckState(AckState::kDelayed, "packet end");
334 }
335}
336
337void DataTracker::UpdateAckState(AckState new_state, absl::string_view reason) {
338 if (new_state != ack_state_) {
339 RTC_DLOG(LS_VERBOSE) << log_prefix_ << "State changed from "
340 << ToString(ack_state_) << " to "
341 << ToString(new_state) << " due to " << reason;
342 if (ack_state_ == AckState::kDelayed) {
343 delayed_ack_timer_.Stop();
344 } else if (new_state == AckState::kDelayed) {
345 delayed_ack_timer_.Start();
346 }
347 ack_state_ = new_state;
348 }
349}
350
351absl::string_view DataTracker::ToString(AckState ack_state) {
352 switch (ack_state) {
353 case AckState::kIdle:
354 return "IDLE";
355 case AckState::kBecomingDelayed:
356 return "BECOMING_DELAYED";
357 case AckState::kDelayed:
358 return "DELAYED";
359 case AckState::kImmediate:
360 return "IMMEDIATE";
361 }
362}
363
Sergey Sukhanov225cd472021-09-14 20:08:53364HandoverReadinessStatus DataTracker::GetHandoverReadiness() const {
365 HandoverReadinessStatus status;
366 if (!additional_tsn_blocks_.empty()) {
367 status.Add(HandoverUnreadinessReason::kDataTrackerTsnBlocksPending);
368 }
369 return status;
370}
371
372void DataTracker::AddHandoverState(DcSctpSocketHandoverState& state) {
373 state.rx.last_cumulative_acked_tsn = last_cumulative_acked_tsn().value();
374 state.rx.seen_packet = seen_packet_;
375}
376
Victor Boivie2cffde72022-06-27 20:35:37377void DataTracker::RestoreFromState(const DcSctpSocketHandoverState& state) {
378 // Validate that the component is in pristine state.
379 RTC_DCHECK(additional_tsn_blocks_.empty());
380 RTC_DCHECK(duplicate_tsns_.empty());
381 RTC_DCHECK(!seen_packet_);
382
383 seen_packet_ = state.rx.seen_packet;
384 last_cumulative_acked_tsn_ =
385 tsn_unwrapper_.Unwrap(TSN(state.rx.last_cumulative_acked_tsn));
386}
Victor Boivieb2d539b2021-04-01 21:36:03387} // namespace dcsctp