Debian Codegraph @

srtcore/list.cpp

raw
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 #include "platform_sys.h"
54
55 #include "list.h"
56 #include "packet.h"
57 #include "logging.h"
58
59 // Use "inline namespace" in C++11
60 namespace srt_logging
61 {
62 extern Logger qrlog;
63 extern Logger qslog;
64 extern Logger tslog;
65 }
66
67 using srt_logging::qrlog;
68 using srt_logging::qslog;
69 using srt_logging::tslog;
70
71 using namespace srt::sync;
72
73 srt::CSndLossList::CSndLossList(int size)
74 : m_caSeq()
75 , m_iHead(-1)
76 , m_iLength(0)
77 , m_iSize(size)
78 , m_iLastInsertPos(-1)
79 , m_ListLock()
80 {
81 m_caSeq = new Seq[size];
82
83 // -1 means there is no data in the node
84 for (int i = 0; i < size; ++i)
85 {
86 m_caSeq[i].seqstart = SRT_SEQNO_NONE;
87 m_caSeq[i].seqend = SRT_SEQNO_NONE;
88 }
89
90 // sender list needs mutex protection
91 setupMutex(m_ListLock, "LossList");
92 }
93
94 srt::CSndLossList::~CSndLossList()
95 {
96 delete[] m_caSeq;
97 releaseMutex(m_ListLock);
98 }
99
100 void srt::CSndLossList::traceState() const
101 {
102 traceState(std::cout) << "\n";
103 }
104
105 int srt::CSndLossList::insert(int32_t seqno1, int32_t seqno2)
106 {
107 if (seqno1 < 0 || seqno2 < 0 ) {
108 LOGC(qslog.Error, log << "IPE: Tried to insert negative seqno " << seqno1 << ":" << seqno2
109 << " into sender's loss list. Ignoring.");
110 return 0;
111 }
112
113 const int inserted_range = CSeqNo::seqlen(seqno1, seqno2);
114 if (inserted_range <= 0 || inserted_range >= m_iSize) {
115 LOGC(qslog.Error, log << "IPE: Tried to insert too big range of seqno: " << inserted_range << ". Ignoring. "
116 << "seqno " << seqno1 << ":" << seqno2);
117 return 0;
118 }
119
120 ScopedLock listguard(m_ListLock);
121
122 if (m_iLength == 0)
123 {
124 insertHead(0, seqno1, seqno2);
125 return m_iLength;
126 }
127
128 // Find the insert position in the non-empty list
129 const int origlen = m_iLength;
130 const int offset = CSeqNo::seqoff(m_caSeq[m_iHead].seqstart, seqno1);
131
132 if (offset >= m_iSize)
133 {
134 LOGC(qslog.Error, log << "IPE: New loss record is too far from the first record. Ignoring. "
135 << "First loss seqno " << m_caSeq[m_iHead].seqstart
136 << ", insert seqno " << seqno1 << ":" << seqno2);
137 return 0;
138 }
139
140 int loc = (m_iHead + offset + m_iSize) % m_iSize;
141
142 if (loc < 0)
143 {
144 const int offset_seqno2 = CSeqNo::seqoff(m_caSeq[m_iHead].seqstart, seqno2);
145 const int loc_seqno2 = (m_iHead + offset_seqno2 + m_iSize) % m_iSize;
146
147 if (loc_seqno2 < 0)
148 {
149 // The size of the CSndLossList should be at least the size of the flow window.
150 // It means that all the packets sender has sent should fit within m_iSize.
151 // If the new loss does not fit, there is some error.
152 LOGC(qslog.Error, log << "IPE: New loss record is too old. Ignoring. "
153 << "First loss seqno " << m_caSeq[m_iHead].seqstart
154 << ", insert seqno " << seqno1 << ":" << seqno2);
155 return 0;
156 }
157
158 loc = loc_seqno2;
159 }
160
161 if (offset < 0)
162 {
163 insertHead(loc, seqno1, seqno2);
164 }
165 else if (offset > 0)
166 {
167 if (seqno1 == m_caSeq[loc].seqstart)
168 {
169 const bool updated = updateElement(loc, seqno1, seqno2);
170 if (!updated)
171 return 0;
172 }
173 else
174 {
175 // Find the prior node.
176 // It should be the highest sequence number less than seqno1.
177 // 1. Start the search either from m_iHead, or from m_iLastInsertPos
178 int i = m_iHead;
179 if ((m_iLastInsertPos != -1) && (CSeqNo::seqcmp(m_caSeq[m_iLastInsertPos].seqstart, seqno1) < 0))
180 i = m_iLastInsertPos;
181
182 // 2. Find the highest sequence number less than seqno1.
183 while (m_caSeq[i].inext != -1 && CSeqNo::seqcmp(m_caSeq[m_caSeq[i].inext].seqstart, seqno1) < 0)
184 i = m_caSeq[i].inext;
185
186 // 3. Check if seqno1 overlaps with (seqbegin, seqend)
187 const int seqend = m_caSeq[i].seqend == SRT_SEQNO_NONE ? m_caSeq[i].seqstart : m_caSeq[i].seqend;
188
189 if (CSeqNo::seqcmp(seqend, seqno1) < 0 && CSeqNo::incseq(seqend) != seqno1)
190 {
191 // No overlap
192 // TODO: Here we should actually insert right after i, not at loc.
193 insertAfter(loc, i, seqno1, seqno2);
194 }
195 else
196 {
197 // TODO: Replace with updateElement(i, seqno1, seqno2).
198 // Some changes to updateElement(..) are required.
199 m_iLastInsertPos = i;
200 if (CSeqNo::seqcmp(seqend, seqno2) >= 0)
201 return 0;
202
203 // overlap, coalesce with prior node, insert(3, 7) to [2, 5], ... becomes [2, 7]
204 m_iLength += CSeqNo::seqlen(seqend, seqno2) - 1;
205 m_caSeq[i].seqend = seqno2;
206
207 loc = i;
208 }
209 }
210 }
211 else // offset == 0, loc == m_iHead
212 {
213 const bool updated = updateElement(m_iHead, seqno1, seqno2);
214 if (!updated)
215 return 0;
216 }
217
218 coalesce(loc);
219 return m_iLength - origlen;
220 }
221
222 void srt::CSndLossList::removeUpTo(int32_t seqno)
223 {
224 ScopedLock listguard(m_ListLock);
225
226 if (0 == m_iLength)
227 return;
228
229 // Remove all from the head pointer to a node with a larger seq. no. or the list is empty
230 int offset = CSeqNo::seqoff(m_caSeq[m_iHead].seqstart, seqno);
231 int loc = (m_iHead + offset + m_iSize) % m_iSize;
232
233 if (0 == offset)
234 {
235 // It is the head. Remove the head and point to the next node
236 loc = (loc + 1) % m_iSize;
237
238 if (SRT_SEQNO_NONE == m_caSeq[m_iHead].seqend)
239 loc = m_caSeq[m_iHead].inext;
240 else
241 {
242 m_caSeq[loc].seqstart = CSeqNo::incseq(seqno);
243 if (CSeqNo::seqcmp(m_caSeq[m_iHead].seqend, CSeqNo::incseq(seqno)) > 0)
244 m_caSeq[loc].seqend = m_caSeq[m_iHead].seqend;
245
246 m_caSeq[m_iHead].seqend = SRT_SEQNO_NONE;
247
248 m_caSeq[loc].inext = m_caSeq[m_iHead].inext;
249 }
250
251 m_caSeq[m_iHead].seqstart = SRT_SEQNO_NONE;
252
253 if (m_iLastInsertPos == m_iHead)
254 m_iLastInsertPos = -1;
255
256 m_iHead = loc;
257
258 m_iLength--;
259 }
260 else if (offset > 0)
261 {
262 int h = m_iHead;
263
264 if (seqno == m_caSeq[loc].seqstart)
265 {
266 // target node is not empty, remove part/all of the seqno in the node.
267 int temp = loc;
268 loc = (loc + 1) % m_iSize;
269
270 if (SRT_SEQNO_NONE == m_caSeq[temp].seqend)
271 m_iHead = m_caSeq[temp].inext;
272 else
273 {
274 // remove part, e.g., [3, 7] becomes [], [4, 7] after remove(3)
275 m_caSeq[loc].seqstart = CSeqNo::incseq(seqno);
276 if (CSeqNo::seqcmp(m_caSeq[temp].seqend, m_caSeq[loc].seqstart) > 0)
277 m_caSeq[loc].seqend = m_caSeq[temp].seqend;
278 m_iHead = loc;
279 m_caSeq[loc].inext = m_caSeq[temp].inext;
280 m_caSeq[temp].inext = loc;
281 m_caSeq[temp].seqend = SRT_SEQNO_NONE;
282 }
283 }
284 else
285 {
286 // target node is empty, check prior node
287 int i = m_iHead;
288 while ((-1 != m_caSeq[i].inext) && (CSeqNo::seqcmp(m_caSeq[m_caSeq[i].inext].seqstart, seqno) < 0))
289 i = m_caSeq[i].inext;
290
291 loc = (loc + 1) % m_iSize;
292
293 if (SRT_SEQNO_NONE == m_caSeq[i].seqend)
294 m_iHead = m_caSeq[i].inext;
295 else if (CSeqNo::seqcmp(m_caSeq[i].seqend, seqno) > 0)
296 {
297 // remove part/all seqno in the prior node
298 m_caSeq[loc].seqstart = CSeqNo::incseq(seqno);
299 if (CSeqNo::seqcmp(m_caSeq[i].seqend, m_caSeq[loc].seqstart) > 0)
300 m_caSeq[loc].seqend = m_caSeq[i].seqend;
301
302 m_caSeq[i].seqend = seqno;
303
304 m_caSeq[loc].inext = m_caSeq[i].inext;
305 m_caSeq[i].inext = loc;
306
307 m_iHead = loc;
308 }
309 else
310 m_iHead = m_caSeq[i].inext;
311 }
312
313 // Remove all nodes prior to the new head
314 while (h != m_iHead)
315 {
316 if (m_caSeq[h].seqend != SRT_SEQNO_NONE)
317 {
318 m_iLength -= CSeqNo::seqlen(m_caSeq[h].seqstart, m_caSeq[h].seqend);
319 m_caSeq[h].seqend = SRT_SEQNO_NONE;
320 }
321 else
322 m_iLength--;
323
324 m_caSeq[h].seqstart = SRT_SEQNO_NONE;
325
326 if (m_iLastInsertPos == h)
327 m_iLastInsertPos = -1;
328
329 h = m_caSeq[h].inext;
330 }
331 }
332 }
333
334 int srt::CSndLossList::getLossLength() const
335 {
336 ScopedLock listguard(m_ListLock);
337
338 return m_iLength;
339 }
340
341 int32_t srt::CSndLossList::popLostSeq()
342 {
343 ScopedLock listguard(m_ListLock);
344
345 if (0 == m_iLength)
346 {
347 SRT_ASSERT(m_iHead == -1);
348 return SRT_SEQNO_NONE;
349 }
350
351 if (m_iLastInsertPos == m_iHead)
352 m_iLastInsertPos = -1;
353
354 // return the first loss seq. no.
355 const int32_t seqno = m_caSeq[m_iHead].seqstart;
356
357 // head moves to the next node
358 if (SRT_SEQNO_NONE == m_caSeq[m_iHead].seqend)
359 {
360 //[3, SRT_SEQNO_NONE] becomes [], and head moves to next node in the list
361 m_caSeq[m_iHead].seqstart = SRT_SEQNO_NONE;
362 m_iHead = m_caSeq[m_iHead].inext;
363 }
364 else
365 {
366 // shift to next node, e.g., [3, 7] becomes [], [4, 7]
367 int loc = (m_iHead + 1) % m_iSize;
368
369 m_caSeq[loc].seqstart = CSeqNo::incseq(seqno);
370 if (CSeqNo::seqcmp(m_caSeq[m_iHead].seqend, m_caSeq[loc].seqstart) > 0)
371 m_caSeq[loc].seqend = m_caSeq[m_iHead].seqend;
372
373 m_caSeq[m_iHead].seqstart = SRT_SEQNO_NONE;
374 m_caSeq[m_iHead].seqend = SRT_SEQNO_NONE;
375
376 m_caSeq[loc].inext = m_caSeq[m_iHead].inext;
377 m_iHead = loc;
378 }
379
380 m_iLength--;
381
382 return seqno;
383 }
384
385 void srt::CSndLossList::insertHead(int pos, int32_t seqno1, int32_t seqno2)
386 {
387 SRT_ASSERT(pos >= 0);
388 m_caSeq[pos].seqstart = seqno1;
389 SRT_ASSERT(m_caSeq[pos].seqend == SRT_SEQNO_NONE);
390 if (seqno2 != seqno1)
391 m_caSeq[pos].seqend = seqno2;
392
393 // new node becomes head
394 m_caSeq[pos].inext = m_iHead;
395 m_iHead = pos;
396 m_iLastInsertPos = pos;
397
398 m_iLength += CSeqNo::seqlen(seqno1, seqno2);
399 }
400
401 void srt::CSndLossList::insertAfter(int pos, int pos_after, int32_t seqno1, int32_t seqno2)
402 {
403 m_caSeq[pos].seqstart = seqno1;
404 SRT_ASSERT(m_caSeq[pos].seqend == SRT_SEQNO_NONE);
405 if (seqno2 != seqno1)
406 m_caSeq[pos].seqend = seqno2;
407
408 m_caSeq[pos].inext = m_caSeq[pos_after].inext;
409 m_caSeq[pos_after].inext = pos;
410 m_iLastInsertPos = pos;
411
412 m_iLength += CSeqNo::seqlen(seqno1, seqno2);
413 }
414
415 void srt::CSndLossList::coalesce(int loc)
416 {
417 // coalesce with next node. E.g., [3, 7], ..., [6, 9] becomes [3, 9]
418 while ((m_caSeq[loc].inext != -1) && (m_caSeq[loc].seqend != SRT_SEQNO_NONE))
419 {
420 const int i = m_caSeq[loc].inext;
421 if (CSeqNo::seqcmp(m_caSeq[i].seqstart, CSeqNo::incseq(m_caSeq[loc].seqend)) > 0)
422 break;
423
424 // coalesce if there is overlap
425 if (m_caSeq[i].seqend != SRT_SEQNO_NONE)
426 {
427 if (CSeqNo::seqcmp(m_caSeq[i].seqend, m_caSeq[loc].seqend) > 0)
428 {
429 if (CSeqNo::seqcmp(m_caSeq[loc].seqend, m_caSeq[i].seqstart) >= 0)
430 m_iLength -= CSeqNo::seqlen(m_caSeq[i].seqstart, m_caSeq[loc].seqend);
431
432 m_caSeq[loc].seqend = m_caSeq[i].seqend;
433 }
434 else
435 m_iLength -= CSeqNo::seqlen(m_caSeq[i].seqstart, m_caSeq[i].seqend);
436 }
437 else
438 {
439 if (m_caSeq[i].seqstart == CSeqNo::incseq(m_caSeq[loc].seqend))
440 m_caSeq[loc].seqend = m_caSeq[i].seqstart;
441 else
442 m_iLength--;
443 }
444
445 m_caSeq[i].seqstart = SRT_SEQNO_NONE;
446 m_caSeq[i].seqend = SRT_SEQNO_NONE;
447 m_caSeq[loc].inext = m_caSeq[i].inext;
448 }
449 }
450
451 bool srt::CSndLossList::updateElement(int pos, int32_t seqno1, int32_t seqno2)
452 {
453 m_iLastInsertPos = pos;
454
455 if (seqno2 == SRT_SEQNO_NONE || seqno2 == seqno1)
456 return false;
457
458 if (m_caSeq[pos].seqend == SRT_SEQNO_NONE)
459 {
460 m_iLength += CSeqNo::seqlen(seqno1, seqno2) - 1;
461 m_caSeq[pos].seqend = seqno2;
462 return true;
463 }
464
465 // seqno2 <= m_caSeq[pos].seqend
466 if (CSeqNo::seqcmp(seqno2, m_caSeq[pos].seqend) <= 0)
467 return false;
468
469 // seqno2 > m_caSeq[pos].seqend
470 m_iLength += CSeqNo::seqlen(m_caSeq[pos].seqend, seqno2) - 1;
471 m_caSeq[pos].seqend = seqno2;
472 return true;
473 }
474
475 ////////////////////////////////////////////////////////////////////////////////
476
477 srt::CRcvLossList::CRcvLossList(int size)
478 : m_caSeq()
479 , m_iHead(-1)
480 , m_iTail(-1)
481 , m_iLength(0)
482 , m_iSize(size)
483 , m_iLargestSeq(SRT_SEQNO_NONE)
484 {
485 m_caSeq = new Seq[m_iSize];
486
487 // -1 means there is no data in the node
488 for (int i = 0; i < size; ++i)
489 {
490 m_caSeq[i].seqstart = SRT_SEQNO_NONE;
491 m_caSeq[i].seqend = SRT_SEQNO_NONE;
492 }
493 }
494
495 srt::CRcvLossList::~CRcvLossList()
496 {
497 delete[] m_caSeq;
498 }
499
500 int srt::CRcvLossList::insert(int32_t seqno1, int32_t seqno2)
501 {
502 SRT_ASSERT(seqno1 != SRT_SEQNO_NONE && seqno2 != SRT_SEQNO_NONE);
503 // Make sure that seqno2 isn't earlier than seqno1.
504 SRT_ASSERT(CSeqNo::seqcmp(seqno1, seqno2) <= 0);
505
506 // Data to be inserted must be larger than all those in the list
507 if (m_iLargestSeq != SRT_SEQNO_NONE && CSeqNo::seqcmp(seqno1, m_iLargestSeq) <= 0)
508 {
509 if (CSeqNo::seqcmp(seqno2, m_iLargestSeq) > 0)
510 {
511 LOGC(qrlog.Warn,
512 log << "RCV-LOSS/insert: seqno1=" << seqno1 << " too small, adjust to "
513 << CSeqNo::incseq(m_iLargestSeq));
514 seqno1 = CSeqNo::incseq(m_iLargestSeq);
515 }
516 else
517 {
518 LOGC(qrlog.Warn,
519 log << "RCV-LOSS/insert: (" << seqno1 << "," << seqno2
520 << ") to be inserted is too small: m_iLargestSeq=" << m_iLargestSeq << ", m_iLength=" << m_iLength
521 << ", m_iHead=" << m_iHead << ", m_iTail=" << m_iTail << " -- REJECTING");
522 return 0;
523 }
524 }
525 m_iLargestSeq = seqno2;
526
527 if (0 == m_iLength)
528 {
529 // insert data into an empty list
530 m_iHead = 0;
531 m_iTail = 0;
532 m_caSeq[m_iHead].seqstart = seqno1;
533 if (seqno2 != seqno1)
534 m_caSeq[m_iHead].seqend = seqno2;
535
536 m_caSeq[m_iHead].inext = -1;
537 m_caSeq[m_iHead].iprior = -1;
538 const int n = CSeqNo::seqlen(seqno1, seqno2);
539 m_iLength += n;
540 return n;
541 }
542
543 // otherwise searching for the position where the node should be
544 const int offset = CSeqNo::seqoff(m_caSeq[m_iHead].seqstart, seqno1);
545 if (offset < 0)
546 {
547 LOGC(qrlog.Error,
548 log << "RCV-LOSS/insert: IPE: new LOSS %(" << seqno1 << "-" << seqno2 << ") PREDATES HEAD %"
549 << m_caSeq[m_iHead].seqstart << " -- REJECTING");
550 return -1;
551 }
552
553 int loc = (m_iHead + offset) % m_iSize;
554
555 if ((SRT_SEQNO_NONE != m_caSeq[m_iTail].seqend) && (CSeqNo::incseq(m_caSeq[m_iTail].seqend) == seqno1))
556 {
557 // coalesce with prior node, e.g., [2, 5], [6, 7] becomes [2, 7]
558 loc = m_iTail;
559 m_caSeq[loc].seqend = seqno2;
560 }
561 else
562 {
563 // create new node
564 m_caSeq[loc].seqstart = seqno1;
565
566 if (seqno2 != seqno1)
567 m_caSeq[loc].seqend = seqno2;
568
569 m_caSeq[m_iTail].inext = loc;
570 m_caSeq[loc].iprior = m_iTail;
571 m_caSeq[loc].inext = -1;
572 m_iTail = loc;
573 }
574
575 const int n = CSeqNo::seqlen(seqno1, seqno2);
576 m_iLength += n;
577 return n;
578 }
579
580 bool srt::CRcvLossList::remove(int32_t seqno)
581 {
582 if (m_iLargestSeq == SRT_SEQNO_NONE || CSeqNo::seqcmp(seqno, m_iLargestSeq) > 0)
583 m_iLargestSeq = seqno;
584
585 if (0 == m_iLength)
586 return false;
587
588 // locate the position of "seqno" in the list
589 int offset = CSeqNo::seqoff(m_caSeq[m_iHead].seqstart, seqno);
590 if (offset < 0)
591 return false;
592
593 int loc = (m_iHead + offset) % m_iSize;
594
595 if (seqno == m_caSeq[loc].seqstart)
596 {
597 // This is a seq. no. that starts the loss sequence
598
599 if (SRT_SEQNO_NONE == m_caSeq[loc].seqend)
600 {
601 // there is only 1 loss in the sequence, delete it from the node
602 if (m_iHead == loc)
603 {
604 m_iHead = m_caSeq[m_iHead].inext;
605 if (-1 != m_iHead)
606 m_caSeq[m_iHead].iprior = -1;
607 else
608 m_iTail = -1;
609 }
610 else
611 {
612 m_caSeq[m_caSeq[loc].iprior].inext = m_caSeq[loc].inext;
613 if (-1 != m_caSeq[loc].inext)
614 m_caSeq[m_caSeq[loc].inext].iprior = m_caSeq[loc].iprior;
615 else
616 m_iTail = m_caSeq[loc].iprior;
617 }
618
619 m_caSeq[loc].seqstart = SRT_SEQNO_NONE;
620 }
621 else
622 {
623 // there are more than 1 loss in the sequence
624 // move the node to the next and update the starter as the next loss inSeqNo(seqno)
625
626 // find next node
627 int i = (loc + 1) % m_iSize;
628
629 // remove the "seqno" and change the starter as next seq. no.
630 m_caSeq[i].seqstart = CSeqNo::incseq(m_caSeq[loc].seqstart);
631
632 // process the sequence end
633 if (CSeqNo::seqcmp(m_caSeq[loc].seqend, CSeqNo::incseq(m_caSeq[loc].seqstart)) > 0)
634 m_caSeq[i].seqend = m_caSeq[loc].seqend;
635
636 // remove the current node
637 m_caSeq[loc].seqstart = SRT_SEQNO_NONE;
638 m_caSeq[loc].seqend = SRT_SEQNO_NONE;
639
640 // update list pointer
641 m_caSeq[i].inext = m_caSeq[loc].inext;
642 m_caSeq[i].iprior = m_caSeq[loc].iprior;
643
644 if (m_iHead == loc)
645 m_iHead = i;
646 else
647 m_caSeq[m_caSeq[i].iprior].inext = i;
648
649 if (m_iTail == loc)
650 m_iTail = i;
651 else
652 m_caSeq[m_caSeq[i].inext].iprior = i;
653 }
654
655 m_iLength--;
656 if (m_iLength == 0)
657 m_iLargestSeq = SRT_SEQNO_NONE;
658
659 return true;
660 }
661
662 // There is no loss sequence in the current position
663 // the "seqno" may be contained in a previous node
664
665 // searching previous node
666 int i = (loc - 1 + m_iSize) % m_iSize;
667 while (SRT_SEQNO_NONE == m_caSeq[i].seqstart)
668 i = (i - 1 + m_iSize) % m_iSize;
669
670 // not contained in this node, return
671 if ((SRT_SEQNO_NONE == m_caSeq[i].seqend) || (CSeqNo::seqcmp(seqno, m_caSeq[i].seqend) > 0))
672 return false;
673
674 if (seqno == m_caSeq[i].seqend)
675 {
676 // it is the sequence end
677
678 if (seqno == CSeqNo::incseq(m_caSeq[i].seqstart))
679 m_caSeq[i].seqend = SRT_SEQNO_NONE;
680 else
681 m_caSeq[i].seqend = CSeqNo::decseq(seqno);
682 }
683 else
684 {
685 // split the sequence
686
687 // construct the second sequence from CSeqNo::incseq(seqno) to the original sequence end
688 // located at "loc + 1"
689 loc = (loc + 1) % m_iSize;
690
691 m_caSeq[loc].seqstart = CSeqNo::incseq(seqno);
692 if (CSeqNo::seqcmp(m_caSeq[i].seqend, m_caSeq[loc].seqstart) > 0)
693 m_caSeq[loc].seqend = m_caSeq[i].seqend;
694
695 // the first (original) sequence is between the original sequence start to CSeqNo::decseq(seqno)
696 if (seqno == CSeqNo::incseq(m_caSeq[i].seqstart))
697 m_caSeq[i].seqend = SRT_SEQNO_NONE;
698 else
699 m_caSeq[i].seqend = CSeqNo::decseq(seqno);
700
701 // update the list pointer
702 m_caSeq[loc].inext = m_caSeq[i].inext;
703 m_caSeq[i].inext = loc;
704 m_caSeq[loc].iprior = i;
705
706 if (m_iTail == i)
707 m_iTail = loc;
708 else
709 m_caSeq[m_caSeq[loc].inext].iprior = loc;
710 }
711
712 m_iLength--;
713 if (m_iLength == 0)
714 m_iLargestSeq = SRT_SEQNO_NONE;
715
716 return true;
717 }
718
719 bool srt::CRcvLossList::remove(int32_t seqno1, int32_t seqno2)
720 {
721 if (CSeqNo::seqcmp(seqno1, seqno2) > 0)
722 {
723 return false;
724 }
725 for (int32_t i = seqno1; CSeqNo::seqcmp(i, seqno2) <= 0; i = CSeqNo::incseq(i))
726 {
727 remove(i);
728 }
729 return true;
730 }
731
732 int32_t srt::CRcvLossList::removeUpTo(int32_t seqno_last)
733 {
734 int32_t first = getFirstLostSeq();
735 if (first == SRT_SEQNO_NONE)
736 {
737 //HLOGC(tslog.Debug, log << "rcv-loss: DROP to %" << seqno_last << " - empty list");
738 return first; // empty, so nothing to remove
739 }
740
741 if (CSeqNo::seqcmp(seqno_last, first) < 0)
742 {
743 //HLOGC(tslog.Debug, log << "rcv-loss: DROP to %" << seqno_last << " - first %" << first << " is newer, exiting");
744 return first; // seqno_last older than first - nothing to remove
745 }
746
747 HLOGC(tslog.Debug, log << "rcv-loss: DROP to %" << seqno_last << " ...");
748
749 // NOTE: seqno_last is past-the-end here. Removed are only seqs
750 // that are earlier than this.
751 for (int32_t i = first; CSeqNo::seqcmp(i, seqno_last) <= 0; i = CSeqNo::incseq(i))
752 {
753 //HLOGC(tslog.Debug, log << "... removing %" << i);
754 remove(i);
755 }
756
757 return first;
758 }
759
760 bool srt::CRcvLossList::find(int32_t seqno1, int32_t seqno2) const
761 {
762 if (0 == m_iLength)
763 return false;
764
765 int p = m_iHead;
766
767 while (-1 != p)
768 {
769 if ((CSeqNo::seqcmp(m_caSeq[p].seqstart, seqno1) == 0) ||
770 ((CSeqNo::seqcmp(m_caSeq[p].seqstart, seqno1) > 0) && (CSeqNo::seqcmp(m_caSeq[p].seqstart, seqno2) <= 0)) ||
771 ((CSeqNo::seqcmp(m_caSeq[p].seqstart, seqno1) < 0) && (m_caSeq[p].seqend != SRT_SEQNO_NONE) &&
772 CSeqNo::seqcmp(m_caSeq[p].seqend, seqno1) >= 0))
773 return true;
774
775 p = m_caSeq[p].inext;
776 }
777
778 return false;
779 }
780
781 int srt::CRcvLossList::getLossLength() const
782 {
783 return m_iLength;
784 }
785
786 int32_t srt::CRcvLossList::getFirstLostSeq() const
787 {
788 if (0 == m_iLength)
789 return SRT_SEQNO_NONE;
790
791 return m_caSeq[m_iHead].seqstart;
792 }
793
794 void srt::CRcvLossList::getLossArray(int32_t* array, int& len, int limit)
795 {
796 len = 0;
797
798 int i = m_iHead;
799
800 while ((len < limit - 1) && (-1 != i))
801 {
802 array[len] = m_caSeq[i].seqstart;
803 if (SRT_SEQNO_NONE != m_caSeq[i].seqend)
804 {
805 // there are more than 1 loss in the sequence
806 array[len] |= LOSSDATA_SEQNO_RANGE_FIRST;
807 ++len;
808 array[len] = m_caSeq[i].seqend;
809 }
810
811 ++len;
812
813 i = m_caSeq[i].inext;
814 }
815 }
816
817 srt::CRcvFreshLoss::CRcvFreshLoss(int32_t seqlo, int32_t seqhi, int initial_age)
818 : ttl(initial_age)
819 , timestamp(steady_clock::now())
820 {
821 seq[0] = seqlo;
822 seq[1] = seqhi;
823 }
824
825 srt::CRcvFreshLoss::Emod srt::CRcvFreshLoss::revoke(int32_t sequence)
826 {
827 int32_t diffbegin = CSeqNo::seqcmp(sequence, seq[0]);
828 int32_t diffend = CSeqNo::seqcmp(sequence, seq[1]);
829
830 if (diffbegin < 0 || diffend > 0)
831 {
832 return NONE; // not within the range at all.
833 }
834
835 if (diffbegin == 0)
836 {
837 if (diffend == 0) // exactly at begin and end
838 {
839 return DELETE;
840 }
841
842 // only exactly at begin. Shrink the range
843 seq[0] = CSeqNo::incseq(seq[0]);
844 return STRIPPED;
845 }
846
847 if (diffend == 0) // exactly at end
848 {
849 seq[1] = CSeqNo::decseq(seq[1]);
850 return STRIPPED;
851 }
852
853 return SPLIT;
854 }
855
856 srt::CRcvFreshLoss::Emod srt::CRcvFreshLoss::revoke(int32_t lo, int32_t hi)
857 {
858 // This should only if the range lo-hi is anyhow covered by seq[0]-seq[1].
859
860 // Note: if the checked item contains sequences that are OLDER
861 // than the oldest sequence in this range, they should be deleted,
862 // even though this wasn't explicitly requested.
863
864 // LOHI: <lo, hi>
865 // ITEM: <lo, hi> <--- delete
866 // If the sequence range is older than the range to be revoked,
867 // delete it anyway.
868 if (lo != SRT_SEQNO_NONE && CSeqNo::seqcmp(lo, seq[1]) > 0)
869 return DELETE;
870 // IF <lo> is NONE, then rely simply on that item.hi <% arg.hi,
871 // which is a condition at the end.
872
873 // LOHI: <lo, hi>
874 // ITEM: <lo, hi> <-- NOTFOUND
875 // This element is newer than the given sequence, so match failed.
876 if (CSeqNo::seqcmp(hi, seq[0]) < 0)
877 return NONE;
878
879 // LOHI: <lo, hi>
880 // ITEM: <lo, ! hi>
881 // RESULT: <lo, hi>
882 // 2. If the 'hi' is in the middle (less than seq[1]), delete partially.
883 // That is, take care of this range for itself and return STRIPPED.
884 if (CSeqNo::seqcmp(hi, seq[1]) < 0)
885 {
886 seq[0] = CSeqNo::incseq(hi);
887 return STRIPPED;
888 }
889
890 // LOHI: <lo, hi>
891 // ITEM: <lo, ! hi>
892 // RESULT: DELETE.
893 // 3. Otherwise delete the record, even if this was covering only part of this range.
894 // This is not possible that the sequences OLDER THAN THIS are not required to be
895 // revoken together with this one.
896
897 return DELETE;
898 }
899
900 bool srt::CRcvFreshLoss::removeOne(std::deque<CRcvFreshLoss>& w_container, int32_t sequence, int* pw_had_ttl)
901 {
902 for (size_t i = 0; i < w_container.size(); ++i)
903 {
904 const int had_ttl = w_container[i].ttl;
905 Emod wh = w_container[i].revoke(sequence);
906
907 if (wh == NONE)
908 continue; // Not found. Search again.
909
910 if (wh == DELETE) // ... oo ... x ... o ... => ... oo ... o ...
911 {
912 // Removed the only element in the record - remove the record.
913 w_container.erase(w_container.begin() + i);
914 }
915 else if (wh == SPLIT) // ... ooxooo ... => ... oo ... ooo ...
916 {
917 // Create a new element that will hold the upper part of the range,
918 // and the found one modify to be the lower part of the range.
919
920 // Keep the current end-of-sequence value for the second element
921 int32_t next_end = w_container[i].seq[1];
922
923 // seq-1 set to the end of this element
924 w_container[i].seq[1] = CSeqNo::decseq(sequence);
925 // seq+1 set to the begin of the next element
926 int32_t next_begin = CSeqNo::incseq(sequence);
927
928 // Use position of the NEXT element because insertion happens BEFORE pointed element.
929 // Use the same TTL (will stay the same in the other one).
930 w_container.insert(w_container.begin() + i + 1,
931 CRcvFreshLoss(next_begin, next_end, w_container[i].ttl));
932 }
933 // For STRIPPED: ... xooo ... => ... ooo ...
934 // i.e. there's nothing to do.
935
936 // Every loss is unique. We're done here.
937 if (pw_had_ttl)
938 *pw_had_ttl = had_ttl;
939
940 return true;
941 }
942
943 if (pw_had_ttl)
944 *pw_had_ttl = 0;
945 return false;
946
947 }
948