1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
/*
* 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.
*/
#ifndef NET_DCSCTP_RX_DATA_TRACKER_H_
#define NET_DCSCTP_RX_DATA_TRACKER_H_
#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 {
public:
// 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: "),
delayed_ack_timer_(*delayed_ack_timer),
last_cumulative_acked_tsn_(
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 =
AnyDataChunk::ImmediateAckFlag(false));
// 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();
private:
enum class AckState {
// No need to send an ACK.
kIdle,
// Has received data chunks (but not yet end of packet).
kBecomingDelayed,
// 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.
kDelayed,
// Send a SACK immediately after handling this packet.
kImmediate,
};
// 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 {
public:
// 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(); }
private:
// 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
#endif // NET_DCSCTP_RX_DATA_TRACKER_H_
|
