| 1 |
/* |
| 2 |
* SRT - Secure, Reliable, Transport |
| 3 |
* Copyright (c) 2018 Haivision Systems Inc. |
| 4 |
* |
| 5 |
* This Source Code Form is subject to the terms of the Mozilla Public |
| 6 |
* License, v. 2.0. If a copy of the MPL was not distributed with this |
| 7 |
* file, You can obtain one at http://mozilla.org/MPL/2.0/. |
| 8 |
* |
| 9 |
*/ |
| 10 |
|
| 11 |
/***************************************************************************** |
| 12 |
Copyright (c) 2001 - 2011, The Board of Trustees of the University of Illinois. |
| 13 |
All rights reserved. |
| 14 |
|
| 15 |
Redistribution and use in source and binary forms, with or without |
| 16 |
modification, are permitted provided that the following conditions are |
| 17 |
met: |
| 18 |
|
| 19 |
* Redistributions of source code must retain the above |
| 20 |
copyright notice, this list of conditions and the |
| 21 |
following disclaimer. |
| 22 |
|
| 23 |
* Redistributions in binary form must reproduce the |
| 24 |
above copyright notice, this list of conditions |
| 25 |
and the following disclaimer in the documentation |
| 26 |
and/or other materials provided with the distribution. |
| 27 |
|
| 28 |
* Neither the name of the University of Illinois |
| 29 |
nor the names of its contributors may be used to |
| 30 |
endorse or promote products derived from this |
| 31 |
software without specific prior written permission. |
| 32 |
|
| 33 |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS |
| 34 |
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, |
| 35 |
THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| 36 |
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
| 37 |
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
| 38 |
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
| 39 |
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 40 |
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 41 |
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 42 |
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 43 |
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 44 |
*****************************************************************************/ |
| 45 |
|
| 46 |
/***************************************************************************** |
| 47 |
written by |
| 48 |
Yunhong Gu, last updated 01/22/2011 |
| 49 |
modified by |
| 50 |
Haivision Systems Inc. |
| 51 |
*****************************************************************************/ |
| 52 |
|
| 53 |
#ifndef INC_SRT_LIST_H |
| 54 |
#define INC_SRT_LIST_H |
| 55 |
|
| 56 |
#include <deque> |
| 57 |
|
| 58 |
#include "udt.h" |
| 59 |
#include "common.h" |
| 60 |
|
| 61 |
namespace srt { |
| 62 |
|
| 63 |
class CSndLossList |
| 64 |
{ |
| 65 |
public: |
| 66 |
CSndLossList(int size = 1024); |
| 67 |
~CSndLossList(); |
| 68 |
|
| 69 |
/// Insert a seq. no. into the sender loss list. |
| 70 |
/// @param [in] seqno1 sequence number starts. |
| 71 |
/// @param [in] seqno2 sequence number ends. |
| 72 |
/// @return number of packets that are not in the list previously. |
| 73 |
int insert(int32_t seqno1, int32_t seqno2); |
| 74 |
|
| 75 |
/// Remove the given sequence number and all numbers that precede it. |
| 76 |
/// @param [in] seqno sequence number. |
| 77 |
void removeUpTo(int32_t seqno); |
| 78 |
|
| 79 |
/// Read the loss length.∏ |
| 80 |
/// @return The length of the list. |
| 81 |
int getLossLength() const; |
| 82 |
|
| 83 |
/// Read the first (smallest) loss seq. no. in the list and remove it. |
| 84 |
/// @return The seq. no. or -1 if the list is empty. |
| 85 |
int32_t popLostSeq(); |
| 86 |
|
| 87 |
template <class Stream> |
| 88 |
Stream& traceState(Stream& sout) const |
| 89 |
{ |
| 90 |
int pos = m_iHead; |
| 91 |
while (pos != SRT_SEQNO_NONE) |
| 92 |
{ |
| 93 |
sout << "[" << pos << "]:" << m_caSeq[pos].seqstart; |
| 94 |
if (m_caSeq[pos].seqend != SRT_SEQNO_NONE) |
| 95 |
sout << ":" << m_caSeq[pos].seqend; |
| 96 |
if (m_caSeq[pos].inext == -1) |
| 97 |
sout << "=|"; |
| 98 |
else |
| 99 |
sout << "->[" << m_caSeq[pos].inext << "]"; |
| 100 |
sout << ", "; |
| 101 |
pos = m_caSeq[pos].inext; |
| 102 |
} |
| 103 |
sout << " {len:" << m_iLength << " head:" << m_iHead << " last:" << m_iLastInsertPos << "}"; |
| 104 |
return sout; |
| 105 |
} |
| 106 |
void traceState() const; |
| 107 |
|
| 108 |
// Debug/unittest support. |
| 109 |
|
| 110 |
int head() const { return m_iHead; } |
| 111 |
int next(int loc) const { return m_caSeq[loc].inext; } |
| 112 |
int last() const { return m_iLastInsertPos; } |
| 113 |
|
| 114 |
private: |
| 115 |
struct Seq |
| 116 |
{ |
| 117 |
int32_t seqstart; // sequence number starts |
| 118 |
int32_t seqend; // sequence number ends |
| 119 |
int inext; // index of the next node in the list |
| 120 |
} * m_caSeq; |
| 121 |
|
| 122 |
int m_iHead; // first node |
| 123 |
int m_iLength; // loss length |
| 124 |
const int m_iSize; // size of the static array |
| 125 |
int m_iLastInsertPos; // position of last insert node |
| 126 |
|
| 127 |
mutable srt::sync::Mutex m_ListLock; // used to synchronize list operation |
| 128 |
|
| 129 |
private: |
| 130 |
/// Inserts an element to the beginning and updates head pointer. |
| 131 |
/// No lock. |
| 132 |
void insertHead(int pos, int32_t seqno1, int32_t seqno2); |
| 133 |
|
| 134 |
/// Inserts an element after previous element. |
| 135 |
/// No lock. |
| 136 |
void insertAfter(int pos, int pos_after, int32_t seqno1, int32_t seqno2); |
| 137 |
|
| 138 |
/// Check if it is possible to coalesce element at loc with further elements. |
| 139 |
/// @param loc - last changed location |
| 140 |
void coalesce(int loc); |
| 141 |
|
| 142 |
/// Update existing element with the new range (increase only) |
| 143 |
/// @param pos position of the element being updated |
| 144 |
/// @param seqno1 first sequence number in range |
| 145 |
/// @param seqno2 last sequence number in range (SRT_SEQNO_NONE if no range) |
| 146 |
bool updateElement(int pos, int32_t seqno1, int32_t seqno2); |
| 147 |
|
| 148 |
static const int LOC_NONE = -1; |
| 149 |
|
| 150 |
private: |
| 151 |
CSndLossList(const CSndLossList&); |
| 152 |
CSndLossList& operator=(const CSndLossList&); |
| 153 |
}; |
| 154 |
|
| 155 |
//////////////////////////////////////////////////////////////////////////////// |
| 156 |
|
| 157 |
class CRcvLossList |
| 158 |
{ |
| 159 |
public: |
| 160 |
CRcvLossList(int size = 1024); |
| 161 |
~CRcvLossList(); |
| 162 |
|
| 163 |
/// Insert a series of loss seq. no. between "seqno1" and "seqno2" into the receiver's loss list. |
| 164 |
/// @param [in] seqno1 sequence number starts. |
| 165 |
/// @param [in] seqno2 sequence number ends. |
| 166 |
/// @return length of the loss record inserted (seqlen(seqno1, seqno2)), -1 on error. |
| 167 |
int insert(int32_t seqno1, int32_t seqno2); |
| 168 |
|
| 169 |
/// Remove a loss seq. no. from the receiver's loss list. |
| 170 |
/// @param [in] seqno sequence number. |
| 171 |
/// @return if the packet is removed (true) or no such lost packet is found (false). |
| 172 |
|
| 173 |
bool remove(int32_t seqno); |
| 174 |
|
| 175 |
/// Remove all packets between seqno1 and seqno2. |
| 176 |
/// @param [in] seqno1 start sequence number. |
| 177 |
/// @param [in] seqno2 end sequence number. |
| 178 |
/// @return if the packet is removed (true) or no such lost packet is found (false). |
| 179 |
|
| 180 |
bool remove(int32_t seqno1, int32_t seqno2); |
| 181 |
|
| 182 |
|
| 183 |
/// Remove all numbers that precede the given sequence number. |
| 184 |
/// @param [in] seqno sequence number. |
| 185 |
/// @return the first removed sequence number |
| 186 |
int32_t removeUpTo(int32_t seqno); |
| 187 |
|
| 188 |
/// Find if there is any lost packets whose sequence number falling seqno1 and seqno2. |
| 189 |
/// @param [in] seqno1 start sequence number. |
| 190 |
/// @param [in] seqno2 end sequence number. |
| 191 |
/// @return True if found; otherwise false. |
| 192 |
|
| 193 |
bool find(int32_t seqno1, int32_t seqno2) const; |
| 194 |
|
| 195 |
/// Read the loss length. |
| 196 |
/// @return the length of the list. |
| 197 |
|
| 198 |
int getLossLength() const; |
| 199 |
|
| 200 |
/// Read the first (smallest) seq. no. in the list. |
| 201 |
/// @return the sequence number or -1 if the list is empty. |
| 202 |
|
| 203 |
int32_t getFirstLostSeq() const; |
| 204 |
|
| 205 |
/// Get a encoded loss array for NAK report. |
| 206 |
/// @param [out] array the result list of seq. no. to be included in NAK. |
| 207 |
/// @param [out] len physical length of the result array. |
| 208 |
/// @param [in] limit maximum length of the array. |
| 209 |
|
| 210 |
void getLossArray(int32_t* array, int& len, int limit); |
| 211 |
|
| 212 |
private: |
| 213 |
struct Seq |
| 214 |
{ |
| 215 |
int32_t seqstart; // sequence number starts |
| 216 |
int32_t seqend; // sequence number ends |
| 217 |
int inext; // index of the next node in the list |
| 218 |
int iprior; // index of the previous node in the list |
| 219 |
} * m_caSeq; |
| 220 |
|
| 221 |
int m_iHead; // first node in the list |
| 222 |
int m_iTail; // last node in the list; |
| 223 |
int m_iLength; // loss length |
| 224 |
int m_iSize; // size of the static array |
| 225 |
int m_iLargestSeq; // largest seq ever seen |
| 226 |
|
| 227 |
private: |
| 228 |
CRcvLossList(const CRcvLossList&); |
| 229 |
CRcvLossList& operator=(const CRcvLossList&); |
| 230 |
|
| 231 |
public: |
| 232 |
struct iterator |
| 233 |
{ |
| 234 |
int32_t head; |
| 235 |
Seq* seq; |
| 236 |
|
| 237 |
iterator(Seq* str, int32_t v) |
| 238 |
: head(v) |
| 239 |
, seq(str) |
| 240 |
{ |
| 241 |
} |
| 242 |
|
| 243 |
iterator next() const |
| 244 |
{ |
| 245 |
if (head == -1) |
| 246 |
return *this; // should report error, but we can only throw exception, so simply ignore it. |
| 247 |
|
| 248 |
return iterator(seq, seq[head].inext); |
| 249 |
} |
| 250 |
|
| 251 |
iterator& operator++() |
| 252 |
{ |
| 253 |
*this = next(); |
| 254 |
return *this; |
| 255 |
} |
| 256 |
|
| 257 |
iterator operator++(int) |
| 258 |
{ |
| 259 |
iterator old(seq, head); |
| 260 |
*this = next(); |
| 261 |
return old; |
| 262 |
} |
| 263 |
|
| 264 |
bool operator==(const iterator& second) const |
| 265 |
{ |
| 266 |
// Ignore seq - should be the same and this is only a sanity check. |
| 267 |
return head == second.head; |
| 268 |
} |
| 269 |
|
| 270 |
bool operator!=(const iterator& second) const { return !(*this == second); } |
| 271 |
|
| 272 |
std::pair<int32_t, int32_t> operator*() { return std::make_pair(seq[head].seqstart, seq[head].seqend); } |
| 273 |
}; |
| 274 |
|
| 275 |
iterator begin() { return iterator(m_caSeq, m_iHead); } |
| 276 |
iterator end() { return iterator(m_caSeq, -1); } |
| 277 |
}; |
| 278 |
|
| 279 |
struct CRcvFreshLoss |
| 280 |
{ |
| 281 |
int32_t seq[2]; |
| 282 |
int ttl; |
| 283 |
srt::sync::steady_clock::time_point timestamp; |
| 284 |
|
| 285 |
CRcvFreshLoss(int32_t seqlo, int32_t seqhi, int initial_ttl); |
| 286 |
|
| 287 |
// Don't WTF when looking at this. The Windows system headers define |
| 288 |
// a publicly visible preprocessor macro with that name. REALLY! |
| 289 |
#ifdef DELETE |
| 290 |
#undef DELETE |
| 291 |
#endif |
| 292 |
enum Emod |
| 293 |
{ |
| 294 |
NONE, //< the given sequence was not found in this range |
| 295 |
STRIPPED, //< it was equal to first or last, already taken care of |
| 296 |
SPLIT, //< found in the middle, you have to split this range into two |
| 297 |
DELETE //< This was a range of one element exactly equal to sequence. Simply delete it. |
| 298 |
}; |
| 299 |
|
| 300 |
Emod revoke(int32_t sequence); |
| 301 |
Emod revoke(int32_t lo, int32_t hi); |
| 302 |
|
| 303 |
static bool removeOne(std::deque<CRcvFreshLoss>& w_container, int32_t sequence, int* had_ttl = NULL); |
| 304 |
}; |
| 305 |
|
| 306 |
} // namespace srt |
| 307 |
|
| 308 |
#endif |