suricata
stream-tcp-sack.c
Go to the documentation of this file.
1 /* Copyright (C) 2007-2011 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Victor Julien <victor@inliniac.net>
22  *
23  * Stream engine TCP SACK handling.
24  */
25 
26 #include "suricata-common.h"
27 #include "stream-tcp.h"
28 #include "stream-tcp-private.h"
29 #include "stream-tcp-sack.h"
30 #include "util-unittest.h"
31 
33 
35 {
36  if (SEQ_GT(a->le, b->le))
37  return 1;
38  else if (SEQ_LT(a->le, b->le))
39  return -1;
40  else {
41  if (SEQ_EQ(a->re, b->re))
42  return 0;
43  else if (SEQ_GT(a->re, b->re))
44  return 1;
45  else
46  return -1;
47  }
48 }
49 #ifdef DEBUG
50 static void StreamTcpSackPrintList(TcpStream *stream)
51 {
52  SCLogDebug("size %u", stream->sack_size);
53  StreamTcpSackRecord *rec = NULL;
54  RB_FOREACH(rec, TCPSACK, &stream->sack_tree) {
55  SCLogDebug("- record %8u - %8u", rec->le, rec->re);
56  }
57 }
58 #endif /* DEBUG */
59 
60 static inline StreamTcpSackRecord *StreamTcpSackRecordAlloc(void)
61 {
62  if (StreamTcpCheckMemcap((uint32_t)sizeof(StreamTcpSackRecord)) == 0)
63  return NULL;
64 
65  StreamTcpSackRecord *rec = SCMalloc(sizeof(*rec));
66  if (unlikely(rec == NULL))
67  return NULL;
68 
69  StreamTcpIncrMemuse((uint64_t)sizeof(*rec));
70  return rec;
71 }
72 
73 static inline void StreamTcpSackRecordFree(StreamTcpSackRecord *rec)
74 {
75  SCFree(rec);
76  StreamTcpDecrMemuse((uint64_t)sizeof(*rec));
77 }
78 
79 static inline void ConsolidateFwd(TcpStream *stream, struct TCPSACK *tree, struct StreamTcpSackRecord *sa)
80 {
81  struct StreamTcpSackRecord *tr, *s = sa;
82  RB_FOREACH_FROM(tr, TCPSACK, s) {
83  if (sa == tr)
84  continue;
85  SCLogDebug("-> (fwd) tr %p %u/%u", tr, tr->le, tr->re);
86 
87  if (SEQ_LT(sa->re, tr->le))
88  break; // entirely before
89 
90  if (SEQ_GEQ(sa->le, tr->le) && SEQ_LEQ(sa->re, tr->re)) {
91  stream->sack_size -= (tr->re - tr->le);
92  stream->sack_size -= (sa->re - sa->le);
93  sa->re = tr->re;
94  sa->le = tr->le;
95  stream->sack_size += (sa->re - sa->le);
96  SCLogDebug("-> (fwd) tr %p %u/%u REMOVED ECLIPSED2", tr, tr->le, tr->re);
97  TCPSACK_RB_REMOVE(tree, tr);
98  StreamTcpSackRecordFree(tr);
99  /*
100  sa: [ ]
101  tr: [ ]
102  sa: [ ]
103  tr: [ ]
104  sa: [ ]
105  tr: [ ]
106  */
107  } else if (SEQ_LEQ(sa->le, tr->le) && SEQ_GEQ(sa->re, tr->re)) {
108  SCLogDebug("-> (fwd) tr %p %u/%u REMOVED ECLIPSED", tr, tr->le, tr->re);
109  stream->sack_size -= (tr->re - tr->le);
110  TCPSACK_RB_REMOVE(tree, tr);
111  StreamTcpSackRecordFree(tr);
112  /*
113  sa: [ ]
114  tr: [ ]
115  sa: [ ]
116  tr: [ ]
117  */
118  } else if (SEQ_LT(sa->le, tr->le) && // starts before
119  SEQ_GEQ(sa->re, tr->le) && SEQ_LT(sa->re, tr->re) // ends inside
120  ) {
121  // merge
122  stream->sack_size -= (tr->re - tr->le);
123  stream->sack_size -= (sa->re - sa->le);
124  sa->re = tr->re;
125  stream->sack_size += (sa->re - sa->le);
126  SCLogDebug("-> (fwd) tr %p %u/%u REMOVED MERGED", tr, tr->le, tr->re);
127  TCPSACK_RB_REMOVE(tree, tr);
128  StreamTcpSackRecordFree(tr);
129  }
130  }
131 }
132 
133 static inline void ConsolidateBackward(TcpStream *stream,
134  struct TCPSACK *tree, struct StreamTcpSackRecord *sa)
135 {
136  struct StreamTcpSackRecord *tr, *s = sa;
137  RB_FOREACH_REVERSE_FROM(tr, TCPSACK, s) {
138  if (sa == tr)
139  continue;
140  SCLogDebug("-> (bwd) tr %p %u/%u", tr, tr->le, tr->re);
141 
142  if (SEQ_GT(sa->le, tr->re))
143  break; // entirely after
144  if (SEQ_GEQ(sa->le, tr->le) && SEQ_LEQ(sa->re, tr->re)) {
145  stream->sack_size -= (tr->re - tr->le);
146  stream->sack_size -= (sa->re - sa->le);
147  sa->re = tr->re;
148  sa->le = tr->le;
149  stream->sack_size += (sa->re - sa->le);
150  SCLogDebug("-> (bwd) tr %p %u/%u REMOVED ECLIPSED2", tr, tr->le, tr->re);
151  TCPSACK_RB_REMOVE(tree, tr);
152  StreamTcpSackRecordFree(tr);
153  /*
154  sa: [ ]
155  tr: [ ]
156  sa: [ ]
157  tr: [ ]
158  sa: [ ]
159  tr: [ ]
160  */
161  } else if (SEQ_LEQ(sa->le, tr->le) && SEQ_GEQ(sa->re, tr->re)) {
162  SCLogDebug("-> (bwd) tr %p %u/%u REMOVED ECLIPSED", tr, tr->le, tr->re);
163  stream->sack_size -= (tr->re - tr->le);
164  TCPSACK_RB_REMOVE(tree, tr);
165  StreamTcpSackRecordFree(tr);
166  /*
167  sa: [ ]
168  tr: [ ]
169  sa: [ ]
170  tr: [ ]
171  */
172  } else if (SEQ_GT(sa->le, tr->le) && SEQ_GT(sa->re, tr->re) && SEQ_LEQ(sa->le,tr->re)) {
173  // merge
174  stream->sack_size -= (tr->re - tr->le);
175  stream->sack_size -= (sa->re - sa->le);
176  sa->le = tr->le;
177  stream->sack_size += (sa->re - sa->le);
178  SCLogDebug("-> (bwd) tr %p %u/%u REMOVED MERGED", tr, tr->le, tr->re);
179  TCPSACK_RB_REMOVE(tree, tr);
180  StreamTcpSackRecordFree(tr);
181  }
182  }
183 }
184 
185 static int Insert(TcpStream *stream, struct TCPSACK *tree, uint32_t le, uint32_t re)
186 {
187  SCLogDebug("inserting: %u-%u", le, re);
188 
189  struct StreamTcpSackRecord *sa = StreamTcpSackRecordAlloc();
190  if (unlikely(sa == NULL))
191  return -1;
192  sa->le = le;
193  sa->re = re;
194  struct StreamTcpSackRecord *res = TCPSACK_RB_INSERT(tree, sa);
195  if (res) {
196  // exact overlap
197  SCLogDebug("* insert failed: exact match in tree with %p %u/%u", res, res->le, res->re);
198  StreamTcpSackRecordFree(sa);
199  return 0;
200  }
201  stream->sack_size += (re - le);
202  ConsolidateBackward(stream, tree, sa);
203  ConsolidateFwd(stream, tree, sa);
204  return 0;
205 }
206 
207 /**
208  * \brief insert a SACK range
209  *
210  * \param le left edge in host order
211  * \param re right edge in host order
212  *
213  * \retval 0 all is good
214  * \retval -1 error
215  */
216 static int StreamTcpSackInsertRange(TcpStream *stream, uint32_t le, uint32_t re)
217 {
218  SCLogDebug("le %u, re %u", le, re);
219 #ifdef DEBUG
220  StreamTcpSackPrintList(stream);
221 #endif
222 
223  /* if to the left of last_ack then ignore */
224  if (SEQ_LT(re, stream->last_ack)) {
225  SCLogDebug("too far left. discarding");
226  SCReturnInt(0);
227  }
228  /* if to the right of the tcp window then ignore */
229  if (SEQ_GT(le, (stream->last_ack + stream->window))) {
230  SCLogDebug("too far right. discarding");
231  SCReturnInt(0);
232  }
233 
234  if (Insert(stream, &stream->sack_tree, le, re) < 0)
235  SCReturnInt(-1);
236 
237  SCReturnInt(0);
238 }
239 
240 /**
241  * \brief Update stream with SACK records from a TCP packet.
242  *
243  * \param stream The stream to update.
244  * \param p packet to get the SACK records from
245  *
246  * \retval -1 error
247  * \retval 0 ok
248  */
250 {
251  SCEnter();
252 
253  const int records = TCP_GET_SACK_CNT(p);
254  const uint8_t *data = TCP_GET_SACK_PTR(p);
255 
256  if (records == 0 || data == NULL)
257  SCReturnInt(0);
258 
259  TCPOptSackRecord rec[records], *sack_rec = rec;
260  memcpy(&rec, data, sizeof(TCPOptSackRecord) * records);
261 
262  for (int record = 0; record < records; record++) {
263  const uint32_t le = SCNtohl(sack_rec->le);
264  const uint32_t re = SCNtohl(sack_rec->re);
265 
266  SCLogDebug("%p last_ack %u, left edge %u, right edge %u", sack_rec,
267  stream->last_ack, le, re);
268 
269  if (SEQ_LEQ(re, stream->last_ack)) {
270  SCLogDebug("record before last_ack");
271  goto next;
272  }
273 
274  if (SEQ_GT(re, stream->next_win)) {
275  SCLogDebug("record %u:%u beyond next_win %u",
276  le, re, stream->next_win);
277  goto next;
278  }
279 
280  if (SEQ_GEQ(le, re)) {
281  SCLogDebug("invalid record: le >= re");
282  goto next;
283  }
284 
285  if (StreamTcpSackInsertRange(stream, le, re) == -1) {
286  SCReturnInt(-1);
287  }
288 
289  next:
290  sack_rec++;
291  }
292  StreamTcpSackPruneList(stream);
293 #ifdef DEBUG
294  StreamTcpSackPrintList(stream);
295 #endif
296  SCReturnInt(0);
297 }
298 
299 static inline int CompareOverlap(
300  struct StreamTcpSackRecord *lookup, struct StreamTcpSackRecord *intree)
301 {
302  if (lookup->re <= intree->le) // entirely before
303  return -1;
304  else if (lookup->re >= intree->le && lookup->le < intree->re) // (some) overlap
305  return 0;
306  else
307  return 1; // entirely after
308 }
309 
310 static struct StreamTcpSackRecord *FindOverlap(
311  struct TCPSACK *head, struct StreamTcpSackRecord *elm)
312 {
313  SCLogDebug("looking up le:%u re:%u", elm->le, elm->re);
314 
315  struct StreamTcpSackRecord *tmp = RB_ROOT(head);
316  struct StreamTcpSackRecord *res = NULL;
317  while (tmp) {
318  SCLogDebug("compare with le:%u re:%u", tmp->le, tmp->re);
319  const int comp = CompareOverlap(elm, tmp);
320  SCLogDebug("compare result: %d", comp);
321  if (comp < 0) {
322  res = tmp;
323  tmp = RB_LEFT(tmp, rb);
324  } else if (comp > 0) {
325  tmp = RB_RIGHT(tmp, rb);
326  } else {
327  return tmp;
328  }
329  }
330  return res;
331 }
332 
334 {
335  const int records = TCP_GET_SACK_CNT(p);
336  const uint8_t *data = TCP_GET_SACK_PTR(p);
337  if (records > 0 && data != NULL) {
338  int sack_outdated = 0;
339  TCPOptSackRecord rec[records], *sack_rec = rec;
340  memcpy(&rec, data, sizeof(TCPOptSackRecord) * records);
341  for (int record = 0; record < records; record++) {
342  const uint32_t le = SCNtohl(sack_rec->le);
343  const uint32_t re = SCNtohl(sack_rec->re);
344  SCLogDebug("%p last_ack %u, left edge %u, right edge %u", sack_rec, stream->last_ack,
345  le, re);
346 
347  struct StreamTcpSackRecord lookup = { .le = le, .re = re };
348  struct StreamTcpSackRecord *res = FindOverlap(&stream->sack_tree, &lookup);
349  SCLogDebug("res %p", res);
350  if (res) {
351  if (le >= res->le && re <= res->re) {
352  SCLogDebug("SACK rec le:%u re:%u eclipsed by in tree le:%u re:%u", le, re,
353  res->le, res->re);
354  sack_outdated++;
355  } else {
356  SCLogDebug("SACK rec le:%u re:%u SACKs new DATA vs in tree le:%u re:%u", le, re,
357  res->le, res->re);
358  }
359  } else {
360  SCLogDebug("SACK rec le:%u re:%u SACKs new DATA. No match in tree", le, re);
361  }
362  sack_rec++;
363  }
364 #ifdef DEBUG
365  StreamTcpSackPrintList(stream);
366 #endif
367  if (records != sack_outdated) {
368  // SACK tree needs updating
369  return false;
370  } else {
371  // SACK list is packet is completely outdated
372  return true;
373  }
374  }
375  return false;
376 }
377 
379 {
380  SCEnter();
381 
382  StreamTcpSackRecord *rec = NULL, *safe = NULL;
383  RB_FOREACH_SAFE(rec, TCPSACK, &stream->sack_tree, safe) {
384  if (SEQ_LT(rec->re, stream->last_ack)) {
385  SCLogDebug("removing le %u re %u", rec->le, rec->re);
386  stream->sack_size -= (rec->re - rec->le);
387  TCPSACK_RB_REMOVE(&stream->sack_tree, rec);
388  StreamTcpSackRecordFree(rec);
389 
390  } else if (SEQ_LT(rec->le, stream->last_ack)) {
391  SCLogDebug("adjusting record to le %u re %u", rec->le, rec->re);
392  /* last ack inside this record, update */
393  stream->sack_size -= (rec->re - rec->le);
394  rec->le = stream->last_ack;
395  stream->sack_size += (rec->re - rec->le);
396  break;
397  } else {
398  SCLogDebug("record beyond last_ack, nothing to do. Bailing out.");
399  break;
400  }
401  }
402 #ifdef DEBUG
403  StreamTcpSackPrintList(stream);
404 #endif
405  SCReturn;
406 }
407 
408 /**
409  * \brief Free SACK tree from a stream
410  *
411  * \param stream Stream to cleanup
412  */
414 {
415  SCEnter();
416 
417  StreamTcpSackRecord *rec = NULL, *safe = NULL;
418  RB_FOREACH_SAFE(rec, TCPSACK, &stream->sack_tree, safe) {
419  stream->sack_size -= (rec->re - rec->le);
420  TCPSACK_RB_REMOVE(&stream->sack_tree, rec);
421  StreamTcpSackRecordFree(rec);
422  }
423 
424  SCReturn;
425 }
426 
427 
428 #ifdef UNITTESTS
429 
430 /**
431  * \test Test the insertion of SACK ranges.
432  *
433  * \retval On success it returns 1 and on failure 0.
434  */
435 
436 static int StreamTcpSackTest01 (void)
437 {
438  TcpStream stream;
439  memset(&stream, 0, sizeof(stream));
440  stream.window = 100;
441 
442  StreamTcpSackInsertRange(&stream, 1, 10);
443  FAIL_IF_NOT(stream.sack_size == 9);
444  StreamTcpSackInsertRange(&stream, 10, 20);
445  FAIL_IF_NOT(stream.sack_size == 19);
446  StreamTcpSackInsertRange(&stream, 10, 20);
447  FAIL_IF_NOT(stream.sack_size == 19);
448  StreamTcpSackInsertRange(&stream, 1, 20);
449  FAIL_IF_NOT(stream.sack_size == 19);
450 #ifdef DEBUG
451  StreamTcpSackPrintList(&stream);
452 #endif /* DEBUG */
453 
454  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
455  FAIL_IF_NULL(rec);
456 
457  FAIL_IF(rec->le != 1);
458  FAIL_IF(rec->re != 20);
459 
460  FAIL_IF(StreamTcpSackedSize(&stream) != 19);
461  StreamTcpSackFreeList(&stream);
462  PASS;
463 }
464 
465 /**
466  * \test Test the insertion of SACK ranges.
467  *
468  * \retval On success it returns 1 and on failure 0.
469  */
470 
471 static int StreamTcpSackTest02 (void)
472 {
473  TcpStream stream;
474  memset(&stream, 0, sizeof(stream));
475  stream.window = 100;
476 
477  StreamTcpSackInsertRange(&stream, 10, 20);
478  StreamTcpSackInsertRange(&stream, 1, 20);
479 #ifdef DEBUG
480  StreamTcpSackPrintList(&stream);
481 #endif /* DEBUG */
482 
483  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
484  FAIL_IF_NULL(rec);
485 
486  FAIL_IF(rec->le != 1);
487  FAIL_IF(rec->re != 20);
488 
489  FAIL_IF(StreamTcpSackedSize(&stream) != 19);
490  StreamTcpSackFreeList(&stream);
491  PASS;
492 }
493 
494 /**
495  * \test Test the insertion of SACK ranges.
496  *
497  * \retval On success it returns 1 and on failure 0.
498  */
499 
500 static int StreamTcpSackTest03 (void)
501 {
502  TcpStream stream;
503  memset(&stream, 0, sizeof(stream));
504  stream.window = 100;
505 
506  StreamTcpSackInsertRange(&stream, 10, 20);
507  StreamTcpSackInsertRange(&stream, 5, 15);
508 #ifdef DEBUG
509  StreamTcpSackPrintList(&stream);
510 #endif /* DEBUG */
511  StreamTcpSackInsertRange(&stream, 15, 25);
512 #ifdef DEBUG
513  StreamTcpSackPrintList(&stream);
514 #endif /* DEBUG */
515 
516  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
517  FAIL_IF_NULL(rec);
518 
519  FAIL_IF(rec->le != 5);
520  FAIL_IF(rec->re != 25);
521 
522  FAIL_IF(StreamTcpSackedSize(&stream) != 20);
523  StreamTcpSackFreeList(&stream);
524  PASS;
525 }
526 
527 /**
528  * \test Test the insertion of SACK ranges.
529  *
530  * \retval On success it returns 1 and on failure 0.
531  */
532 
533 static int StreamTcpSackTest04 (void)
534 {
535  TcpStream stream;
536  memset(&stream, 0, sizeof(stream));
537  stream.window = 100;
538 
539  StreamTcpSackInsertRange(&stream, 0, 20);
540  StreamTcpSackInsertRange(&stream, 30, 50);
541  StreamTcpSackInsertRange(&stream, 10, 25);
542 #ifdef DEBUG
543  StreamTcpSackPrintList(&stream);
544 #endif /* DEBUG */
545 
546  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
547  FAIL_IF_NULL(rec);
548 
549  FAIL_IF(rec->le != 0);
550  FAIL_IF(rec->re != 25);
551 
552  FAIL_IF(StreamTcpSackedSize(&stream) != 45);
553  StreamTcpSackFreeList(&stream);
554  PASS;
555 }
556 
557 /**
558  * \test Test the insertion of SACK ranges.
559  *
560  * \retval On success it returns 1 and on failure 0.
561  */
562 
563 static int StreamTcpSackTest05 (void)
564 {
565  TcpStream stream;
566  memset(&stream, 0, sizeof(stream));
567  stream.window = 100;
568 
569  StreamTcpSackInsertRange(&stream, 0, 20);
570  StreamTcpSackInsertRange(&stream, 30, 50);
571  StreamTcpSackInsertRange(&stream, 10, 35);
572 #ifdef DEBUG
573  StreamTcpSackPrintList(&stream);
574 #endif /* DEBUG */
575 
576  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
577  FAIL_IF_NULL(rec);
578 
579  FAIL_IF(rec->le != 0);
580  FAIL_IF(rec->re != 50);
581 
582  FAIL_IF(StreamTcpSackedSize(&stream) != 50);
583  StreamTcpSackFreeList(&stream);
584  PASS;
585 }
586 
587 /**
588  * \test Test the insertion of SACK ranges.
589  *
590  * \retval On success it returns 1 and on failure 0.
591  */
592 
593 static int StreamTcpSackTest06 (void)
594 {
595  TcpStream stream;
596  memset(&stream, 0, sizeof(stream));
597  stream.window = 100;
598 
599  StreamTcpSackInsertRange(&stream, 0, 9);
600  StreamTcpSackInsertRange(&stream, 11, 19);
601  StreamTcpSackInsertRange(&stream, 21, 29);
602  StreamTcpSackInsertRange(&stream, 31, 39);
603  StreamTcpSackInsertRange(&stream, 0, 40);
604 #ifdef DEBUG
605  StreamTcpSackPrintList(&stream);
606 #endif /* DEBUG */
607 
608  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
609  FAIL_IF_NULL(rec);
610 
611  FAIL_IF(rec->le != 0);
612  FAIL_IF(rec->re != 40);
613 
614  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
615  StreamTcpSackFreeList(&stream);
616  PASS;
617 }
618 
619 /**
620  * \test Test the pruning of SACK ranges.
621  *
622  * \retval On success it returns 1 and on failure 0.
623  */
624 
625 static int StreamTcpSackTest07 (void)
626 {
627  TcpStream stream;
628  memset(&stream, 0, sizeof(stream));
629  stream.window = 100;
630 
631  StreamTcpSackInsertRange(&stream, 0, 9);
632  StreamTcpSackInsertRange(&stream, 11, 19);
633  StreamTcpSackInsertRange(&stream, 21, 29);
634  StreamTcpSackInsertRange(&stream, 31, 39);
635  StreamTcpSackInsertRange(&stream, 0, 40);
636 #ifdef DEBUG
637  StreamTcpSackPrintList(&stream);
638 #endif /* DEBUG */
639 
640  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
641  FAIL_IF_NULL(rec);
642  FAIL_IF(rec->le != 0);
643  FAIL_IF(rec->re != 40);
644  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
645 
646  stream.last_ack = 10;
647  StreamTcpSackPruneList(&stream);
648  FAIL_IF(StreamTcpSackedSize(&stream) != 30);
649 
650  StreamTcpSackFreeList(&stream);
651  PASS;
652 }
653 
654 /**
655  * \test Test the pruning of SACK ranges.
656  *
657  * \retval On success it returns 1 and on failure 0.
658  */
659 
660 static int StreamTcpSackTest08 (void)
661 {
662  TcpStream stream;
663  memset(&stream, 0, sizeof(stream));
664  stream.window = 100;
665 
666  StreamTcpSackInsertRange(&stream, 0, 9);
667  StreamTcpSackInsertRange(&stream, 11, 19);
668  StreamTcpSackInsertRange(&stream, 21, 29);
669  StreamTcpSackInsertRange(&stream, 31, 39);
670  StreamTcpSackInsertRange(&stream, 0, 40);
671 #ifdef DEBUG
672  StreamTcpSackPrintList(&stream);
673 #endif /* DEBUG */
674 
675  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
676  FAIL_IF_NULL(rec);
677  FAIL_IF(rec->le != 0);
678  FAIL_IF(rec->re != 40);
679  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
680 
681  stream.last_ack = 41;
682  StreamTcpSackPruneList(&stream);
683  FAIL_IF(StreamTcpSackedSize(&stream) != 0);
684 
685  StreamTcpSackFreeList(&stream);
686  PASS;
687 }
688 
689 /**
690  * \test Test the pruning of SACK ranges.
691  *
692  * \retval On success it returns 1 and on failure 0.
693  */
694 
695 static int StreamTcpSackTest09 (void)
696 {
697  TcpStream stream;
698  memset(&stream, 0, sizeof(stream));
699  stream.window = 100;
700 
701  StreamTcpSackInsertRange(&stream, 0, 9);
702  StreamTcpSackInsertRange(&stream, 11, 19);
703  StreamTcpSackInsertRange(&stream, 21, 29);
704  StreamTcpSackInsertRange(&stream, 31, 39);
705  StreamTcpSackInsertRange(&stream, 0, 40);
706 
707 #ifdef DEBUG
708  StreamTcpSackPrintList(&stream);
709 #endif /* DEBUG */
710 
711  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
712  FAIL_IF_NULL(rec);
713  FAIL_IF(rec->le != 0);
714  FAIL_IF(rec->re != 40);
715  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
716 
717  stream.last_ack = 39;
718  StreamTcpSackPruneList(&stream);
719  FAIL_IF(StreamTcpSackedSize(&stream) != 1);
720 
721  StreamTcpSackFreeList(&stream);
722  PASS;
723 }
724 
725 /**
726  * \test Test the pruning of SACK ranges.
727  *
728  * \retval On success it returns 1 and on failure 0.
729  */
730 
731 static int StreamTcpSackTest10 (void)
732 {
733  TcpStream stream;
734  memset(&stream, 0, sizeof(stream));
735  stream.window = 1000;
736 
737  StreamTcpSackInsertRange(&stream, 100, 119);
738  StreamTcpSackInsertRange(&stream, 111, 119);
739  StreamTcpSackInsertRange(&stream, 121, 129);
740  StreamTcpSackInsertRange(&stream, 131, 139);
741  StreamTcpSackInsertRange(&stream, 100, 140);
742 #ifdef DEBUG
743  StreamTcpSackPrintList(&stream);
744 #endif /* DEBUG */
745 
746  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
747  FAIL_IF_NULL(rec);
748  FAIL_IF(rec->le != 100);
749  FAIL_IF(rec->re != 140);
750  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
751 
752  stream.last_ack = 99;
753  StreamTcpSackPruneList(&stream);
754  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
755 
756  StreamTcpSackFreeList(&stream);
757  PASS;
758 }
759 
760 /**
761  * \test Test the pruning of SACK ranges.
762  *
763  * \retval On success it returns 1 and on failure 0.
764  */
765 
766 static int StreamTcpSackTest11 (void)
767 {
768  TcpStream stream;
769  memset(&stream, 0, sizeof(stream));
770  stream.window = 1000;
771 
772  StreamTcpSackInsertRange(&stream, 100, 119);
773  StreamTcpSackInsertRange(&stream, 111, 119);
774  StreamTcpSackInsertRange(&stream, 121, 129);
775  StreamTcpSackInsertRange(&stream, 131, 139);
776  StreamTcpSackInsertRange(&stream, 101, 140);
777 #ifdef DEBUG
778  StreamTcpSackPrintList(&stream);
779 #endif /* DEBUG */
780 
781  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
782  FAIL_IF_NULL(rec);
783  FAIL_IF(rec->le != 100);
784  FAIL_IF(rec->re != 140);
785  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
786 
787  stream.last_ack = 99;
788  StreamTcpSackPruneList(&stream);
789  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
790 
791  StreamTcpSackFreeList(&stream);
792  PASS;
793 }
794 
795 /**
796  * \test Test the pruning of SACK ranges.
797  *
798  * \retval On success it returns 1 and on failure 0.
799  */
800 
801 static int StreamTcpSackTest12 (void)
802 {
803  TcpStream stream;
804  memset(&stream, 0, sizeof(stream));
805  stream.window = 2000;
806 
807  StreamTcpSackInsertRange(&stream, 800, 1000);
808  StreamTcpSackInsertRange(&stream, 700, 900);
809  StreamTcpSackInsertRange(&stream, 600, 800);
810  StreamTcpSackInsertRange(&stream, 500, 700);
811  StreamTcpSackInsertRange(&stream, 100, 600);
812 #ifdef DEBUG
813  StreamTcpSackPrintList(&stream);
814 #endif /* DEBUG */
815 
816  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
817  FAIL_IF_NULL(rec);
818  FAIL_IF(rec->le != 100);
819  FAIL_IF(rec->re != 1000);
820  FAIL_IF(StreamTcpSackedSize(&stream) != 900);
821 
822  StreamTcpSackInsertRange(&stream, 0, 1000);
823  FAIL_IF(StreamTcpSackedSize(&stream) != 1000);
824 
825  stream.last_ack = 500;
826  StreamTcpSackPruneList(&stream);
827  FAIL_IF(StreamTcpSackedSize(&stream) != 500);
828 
829  StreamTcpSackFreeList(&stream);
830  PASS;
831 }
832 
833 /**
834  * \test Test the insertion on out of window condition.
835  *
836  * \retval On success it returns 1 and on failure 0.
837  */
838 
839 static int StreamTcpSackTest13 (void) {
840  TcpStream stream;
841  memset(&stream, 0, sizeof(stream));
842  stream.last_ack = 10000;
843  stream.window = 2000;
844 
845  for (int i = 0; i < 10; i++) {
846  StreamTcpSackInsertRange(&stream, 100+(20*i), 110+(20*i));
847  }
848 #ifdef DEBUG
849  StreamTcpSackPrintList(&stream);
850 #endif /* DEBUG */
851 
852  FAIL_IF(StreamTcpSackedSize(&stream) != 0);
853 
854  StreamTcpSackFreeList(&stream);
855  PASS;
856 }
857 
858 /**
859  * \test Test the insertion of out of window condition.
860  *
861  * \retval On success it returns 1 and on failure 0.
862  */
863 
864 static int StreamTcpSackTest14 (void) {
865  TcpStream stream;
866  memset(&stream, 0, sizeof(stream));
867  stream.last_ack = 1000;
868  stream.window = 2000;
869 
870  for (int i = 0; i < 10; i++) {
871  StreamTcpSackInsertRange(&stream, 4000+(20*i), 4010+(20*i));
872  }
873 #ifdef DEBUG
874  StreamTcpSackPrintList(&stream);
875 #endif /* DEBUG */
876 
877  FAIL_IF(StreamTcpSackedSize(&stream) != 0);
878 
879  StreamTcpSackFreeList(&stream);
880  PASS;
881 }
882 
883 #endif /* UNITTESTS */
884 
886 {
887 #ifdef UNITTESTS
888  UtRegisterTest("StreamTcpSackTest01 -- Insertion", StreamTcpSackTest01);
889  UtRegisterTest("StreamTcpSackTest02 -- Insertion", StreamTcpSackTest02);
890  UtRegisterTest("StreamTcpSackTest03 -- Insertion", StreamTcpSackTest03);
891  UtRegisterTest("StreamTcpSackTest04 -- Insertion", StreamTcpSackTest04);
892  UtRegisterTest("StreamTcpSackTest05 -- Insertion", StreamTcpSackTest05);
893  UtRegisterTest("StreamTcpSackTest06 -- Insertion", StreamTcpSackTest06);
894  UtRegisterTest("StreamTcpSackTest07 -- Pruning", StreamTcpSackTest07);
895  UtRegisterTest("StreamTcpSackTest08 -- Pruning", StreamTcpSackTest08);
896  UtRegisterTest("StreamTcpSackTest09 -- Pruning", StreamTcpSackTest09);
897  UtRegisterTest("StreamTcpSackTest10 -- Pruning", StreamTcpSackTest10);
898  UtRegisterTest("StreamTcpSackTest11 -- Insertion && Pruning",
899  StreamTcpSackTest11);
900  UtRegisterTest("StreamTcpSackTest12 -- Insertion && Pruning",
901  StreamTcpSackTest12);
902  UtRegisterTest("StreamTcpSackTest13 -- Insertion out of window",
903  StreamTcpSackTest13);
904  UtRegisterTest("StreamTcpSackTest14 -- Insertion out of window",
905  StreamTcpSackTest14);
906 #endif
907 }
StreamTcpIncrMemuse
void StreamTcpIncrMemuse(uint64_t size)
Definition: stream-tcp.c:128
TcpStream_
Definition: stream-tcp-private.h:94
FAIL_IF_NULL
#define FAIL_IF_NULL(expr)
Fail a test if expression evaluates to NULL.
Definition: util-unittest.h:89
stream-tcp.h
unlikely
#define unlikely(expr)
Definition: util-optimize.h:35
UtRegisterTest
void UtRegisterTest(const char *name, int(*TestFn)(void))
Register unit test.
Definition: util-unittest.c:103
SCLogDebug
#define SCLogDebug(...)
Definition: util-debug.h:298
next
struct HtpBodyChunk_ * next
Definition: app-layer-htp.h:0
StreamTcpSackFreeList
void StreamTcpSackFreeList(TcpStream *stream)
Free SACK tree from a stream.
Definition: stream-tcp-sack.c:413
RB_LEFT
#define RB_LEFT(elm, field)
Definition: tree.h:322
StreamTcpSackRegisterTests
void StreamTcpSackRegisterTests(void)
Definition: stream-tcp-sack.c:885
RB_MIN
#define RB_MIN(name, x)
Definition: tree.h:778
util-unittest.h
FAIL_IF_NOT
#define FAIL_IF_NOT(expr)
Fail a test if expression evaluates to false.
Definition: util-unittest.h:82
StreamTcpSackRecord::le
uint32_t le
Definition: stream-tcp-private.h:50
TcpSackCompare
int TcpSackCompare(struct StreamTcpSackRecord *a, struct StreamTcpSackRecord *b)
Definition: stream-tcp-sack.c:34
TcpStream_::last_ack
uint32_t last_ack
Definition: stream-tcp-private.h:103
StreamTcpCheckMemcap
int StreamTcpCheckMemcap(uint64_t size)
Check if alloc'ing "size" would mean we're over memcap.
Definition: stream-tcp.c:168
PASS
#define PASS
Pass the test.
Definition: util-unittest.h:105
RB_ROOT
#define RB_ROOT(head)
Definition: tree.h:326
res
PoolThreadReserved res
Definition: stream-tcp-private.h:0
RB_FOREACH_SAFE
#define RB_FOREACH_SAFE(x, name, head, y)
Definition: tree.h:791
SCEnter
#define SCEnter(...)
Definition: util-debug.h:300
TcpStream_::sack_tree
struct TCPSACK sack_tree
Definition: stream-tcp-private.h:128
TcpStream_::next_win
uint32_t next_win
Definition: stream-tcp-private.h:104
RB_FOREACH
#define RB_FOREACH(x, name, head)
Definition: tree.h:781
SCReturn
#define SCReturn
Definition: util-debug.h:302
Packet_
Definition: decode.h:414
TCP_GET_SACK_CNT
#define TCP_GET_SACK_CNT(p)
Definition: decode-tcp.h:106
StreamTcpSackUpdatePacket
int StreamTcpSackUpdatePacket(TcpStream *stream, Packet *p)
Update stream with SACK records from a TCP packet.
Definition: stream-tcp-sack.c:249
stream-tcp-sack.h
stream-tcp-private.h
TcpStream_::window
uint32_t window
Definition: stream-tcp-private.h:105
TCPOptSackRecord_
Definition: decode-tcp.h:136
TcpStream_::sack_size
uint32_t sack_size
Definition: stream-tcp-private.h:126
FAIL_IF
#define FAIL_IF(expr)
Fail a test if expression evaluates to true.
Definition: util-unittest.h:71
SEQ_GEQ
#define SEQ_GEQ(a, b)
Definition: stream-tcp-private.h:241
StreamTcpSackPacketIsOutdated
bool StreamTcpSackPacketIsOutdated(TcpStream *stream, Packet *p)
Definition: stream-tcp-sack.c:333
suricata-common.h
SEQ_GT
#define SEQ_GT(a, b)
Definition: stream-tcp-private.h:240
RB_GENERATE
RB_GENERATE(TCPSACK, StreamTcpSackRecord, rb, TcpSackCompare)
TCPOptSackRecord_::le
uint32_t le
Definition: decode-tcp.h:137
SCMalloc
#define SCMalloc(sz)
Definition: util-mem.h:47
TCPOptSackRecord_::re
uint32_t re
Definition: decode-tcp.h:138
TCP_GET_SACK_PTR
#define TCP_GET_SACK_PTR(p)
Definition: decode-tcp.h:105
RB_RIGHT
#define RB_RIGHT(elm, field)
Definition: tree.h:323
head
Flow * head
Definition: flow-hash.h:1
SCFree
#define SCFree(p)
Definition: util-mem.h:61
SCNtohl
#define SCNtohl(x)
Definition: suricata-common.h:394
SEQ_LT
#define SEQ_LT(a, b)
Definition: stream-tcp-private.h:238
SEQ_EQ
#define SEQ_EQ(a, b)
Definition: stream-tcp-private.h:237
SEQ_LEQ
#define SEQ_LEQ(a, b)
Definition: stream-tcp-private.h:239
RB_FOREACH_REVERSE_FROM
#define RB_FOREACH_REVERSE_FROM(x, name, y)
Definition: tree.h:801
RB_FOREACH_FROM
#define RB_FOREACH_FROM(x, name, y)
Definition: tree.h:786
SCReturnInt
#define SCReturnInt(x)
Definition: util-debug.h:304
StreamTcpSackRecord::re
uint32_t re
Definition: stream-tcp-private.h:51
StreamTcpDecrMemuse
void StreamTcpDecrMemuse(uint64_t size)
Definition: stream-tcp.c:135
StreamTcpSackRecord
Definition: stream-tcp-private.h:49
StreamTcpSackPruneList
void StreamTcpSackPruneList(TcpStream *stream)
Definition: stream-tcp-sack.c:378