1 /* 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> 19 #include <utility> 20 #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" 27 #include "net/dcsctp/public/dcsctp_handover_state.h" 28 #include "net/dcsctp/timer/timer.h" 29 30 namespace 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). 41 class DataTracker { 42 public: 43 // 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 48 // 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. 53 static constexpr uint32_t kMaxAcceptedOutstandingFragments = 100000; 54 DataTracker(absl::string_view log_prefix,Timer * delayed_ack_timer,TSN peer_initial_tsn)55 DataTracker(absl::string_view log_prefix, 56 Timer* delayed_ack_timer, 57 TSN peer_initial_tsn) 58 : log_prefix_(std::string(log_prefix) + "dtrack: "), 59 seen_packet_(false), 60 delayed_ack_timer_(*delayed_ack_timer), 61 last_cumulative_acked_tsn_( 62 tsn_unwrapper_.Unwrap(TSN(*peer_initial_tsn - 1))) {} 63 64 // 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 69 // 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, 72 AnyDataChunk::ImmediateAckFlag immediate_ack = 73 AnyDataChunk::ImmediateAckFlag(false)); 74 // Called at the end of processing an SCTP packet. 75 void ObservePacketEnd(); 76 77 // Called for incoming FORWARD-TSN/I-FORWARD-TSN chunks 78 void HandleForwardTsn(TSN new_cumulative_ack); 79 80 // Indicates if a SACK should be sent. There may be other reasons to send a 81 // SACK, but if this function indicates so, it should be sent as soon as 82 // possible. Calling this function will make it clear a flag so that if it's 83 // called again, it will probably return false. 84 // 85 // If the delayed ack timer is running, this method will return false _unless_ 86 // `also_if_delayed` is set to true. Then it will return true as well. 87 bool ShouldSendAck(bool also_if_delayed = false); 88 89 // Returns the last cumulative ack TSN - the last seen data chunk's TSN 90 // value before any packet loss was detected. last_cumulative_acked_tsn()91 TSN last_cumulative_acked_tsn() const { 92 return TSN(last_cumulative_acked_tsn_.Wrap()); 93 } 94 95 // Returns true if the received `tsn` would increase the cumulative ack TSN. 96 bool will_increase_cum_ack_tsn(TSN tsn) const; 97 98 // Forces `ShouldSendSack` to return true. 99 void ForceImmediateSack(); 100 101 // Note that this will clear `duplicates_`, so every SackChunk that is 102 // consumed must be sent. 103 SackChunk CreateSelectiveAck(size_t a_rwnd); 104 105 void HandleDelayedAckTimerExpiry(); 106 107 HandoverReadinessStatus GetHandoverReadiness() const; 108 109 void AddHandoverState(DcSctpSocketHandoverState& state); 110 void RestoreFromState(const DcSctpSocketHandoverState& state); 111 112 private: 113 enum class AckState { 114 // No need to send an ACK. 115 kIdle, 116 117 // Has received data chunks (but not yet end of packet). 118 kBecomingDelayed, 119 120 // Has received data chunks and the end of a packet. Delayed ack timer is 121 // running and a SACK will be sent on expiry, or if DATA is sent, or after 122 // next packet with data. 123 kDelayed, 124 125 // Send a SACK immediately after handling this packet. 126 kImmediate, 127 }; 128 129 // Represents ranges of TSNs that have been received that are not directly 130 // following the last cumulative acked TSN. This information is returned to 131 // the sender in the "gap ack blocks" in the SACK chunk. The blocks are always 132 // non-overlapping and non-adjacent. 133 class AdditionalTsnBlocks { 134 public: 135 // Represents an inclusive range of received TSNs, i.e. [first, last]. 136 struct TsnRange { TsnRangeTsnRange137 TsnRange(UnwrappedTSN first, UnwrappedTSN last) 138 : first(first), last(last) {} 139 UnwrappedTSN first; 140 UnwrappedTSN last; 141 }; 142 143 // Adds a TSN to the set. This will try to expand any existing block and 144 // might merge blocks to ensure that all blocks are non-adjacent. If a 145 // current block can't be expanded, a new block is created. 146 // 147 // The return value indicates if `tsn` was added. If false is returned, the 148 // `tsn` was already represented in one of the blocks. 149 bool Add(UnwrappedTSN tsn); 150 151 // Erases all TSNs up to, and including `tsn`. This will remove all blocks 152 // that are completely below `tsn` and may truncate a block where `tsn` is 153 // within that block. In that case, the frontmost block's start TSN will be 154 // the next following tsn after `tsn`. 155 void EraseTo(UnwrappedTSN tsn); 156 157 // Removes the first block. Must not be called on an empty set. 158 void PopFront(); 159 blocks()160 const std::vector<TsnRange>& blocks() const { return blocks_; } 161 empty()162 bool empty() const { return blocks_.empty(); } 163 front()164 const TsnRange& front() const { return blocks_.front(); } 165 166 private: 167 // A sorted vector of non-overlapping and non-adjacent blocks. 168 std::vector<TsnRange> blocks_; 169 }; 170 171 std::vector<SackChunk::GapAckBlock> CreateGapAckBlocks() const; 172 void UpdateAckState(AckState new_state, absl::string_view reason); 173 static absl::string_view ToString(AckState ack_state); 174 175 const std::string log_prefix_; 176 // If a packet has ever been seen. 177 bool seen_packet_; 178 Timer& delayed_ack_timer_; 179 AckState ack_state_ = AckState::kIdle; 180 UnwrappedTSN::Unwrapper tsn_unwrapper_; 181 182 // All TSNs up until (and including) this value have been seen. 183 UnwrappedTSN last_cumulative_acked_tsn_; 184 // Received TSNs that are not directly following `last_cumulative_acked_tsn_`. 185 AdditionalTsnBlocks additional_tsn_blocks_; 186 std::set<TSN> duplicate_tsns_; 187 }; 188 } // namespace dcsctp 189 190 #endif // NET_DCSCTP_RX_DATA_TRACKER_H_ 191