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 TCPHdr *tcph = PacketGetTCP(p);
254  const int records = TCP_GET_SACK_CNT(p);
255  const uint8_t *data = TCP_GET_SACK_PTR(p, tcph);
256 
257  if (records == 0 || data == NULL)
258  SCReturnInt(0);
259 
260  TCPOptSackRecord rec[records], *sack_rec = rec;
261  memcpy(&rec, data, sizeof(TCPOptSackRecord) * records);
262 
263  uint32_t first_le = 0;
264  uint32_t first_re = 0;
265 
266  for (int record = 0; record < records; record++) {
267  const uint32_t le = SCNtohl(sack_rec->le);
268  const uint32_t re = SCNtohl(sack_rec->re);
269 
270  if (!first_le)
271  first_le = le;
272  if (!first_re)
273  first_re = re;
274 
275  SCLogDebug("%p last_ack %u, left edge %u, right edge %u pkt ACK %u", sack_rec,
276  stream->last_ack, le, re, TCP_GET_RAW_ACK(tcph));
277 
278  /* RFC 2883 D-SACK */
279  if (SEQ_LT(le, TCP_GET_RAW_ACK(tcph))) {
280  SCLogDebug("packet: %" PRIu64 ": D-SACK? %u-%u before ACK %u", p->pcap_cnt, le, re,
281  TCP_GET_RAW_ACK(tcph));
283  goto next;
284  } else if (record == 1) { // 2nd record
285  if (SEQ_GEQ(first_le, le) && SEQ_LEQ(first_re, re)) {
286  SCLogDebug("packet: %" PRIu64 ": D-SACK? %u-%u inside 2nd range %u-%u ACK %u",
287  p->pcap_cnt, first_le, first_re, le, re, TCP_GET_RAW_ACK(tcph));
289  }
290  goto next;
291  }
292 
293  if (SEQ_LEQ(re, stream->last_ack)) {
294  SCLogDebug("record before last_ack");
295  goto next;
296  }
297 
298  if (SEQ_GT(re, stream->next_win)) {
299  SCLogDebug("record %u:%u beyond next_win %u",
300  le, re, stream->next_win);
301  goto next;
302  }
303 
304  if (SEQ_GEQ(le, re)) {
305  SCLogDebug("invalid record: le >= re");
306  goto next;
307  }
308 
309  if (StreamTcpSackInsertRange(stream, le, re) == -1) {
310  SCReturnInt(-1);
311  }
312 
313  next:
314  sack_rec++;
315  }
316  StreamTcpSackPruneList(stream);
317 #ifdef DEBUG
318  StreamTcpSackPrintList(stream);
319 #endif
320  SCReturnInt(0);
321 }
322 
323 static inline int CompareOverlap(
324  struct StreamTcpSackRecord *lookup, struct StreamTcpSackRecord *intree)
325 {
326  if (lookup->re <= intree->le) // entirely before
327  return -1;
328  else if (lookup->re >= intree->le && lookup->le < intree->re) // (some) overlap
329  return 0;
330  else
331  return 1; // entirely after
332 }
333 
334 static struct StreamTcpSackRecord *FindOverlap(
335  struct TCPSACK *head, struct StreamTcpSackRecord *elm)
336 {
337  SCLogDebug("looking up le:%u re:%u", elm->le, elm->re);
338 
339  struct StreamTcpSackRecord *tmp = RB_ROOT(head);
340  struct StreamTcpSackRecord *res = NULL;
341  while (tmp) {
342  SCLogDebug("compare with le:%u re:%u", tmp->le, tmp->re);
343  const int comp = CompareOverlap(elm, tmp);
344  SCLogDebug("compare result: %d", comp);
345  if (comp < 0) {
346  res = tmp;
347  tmp = RB_LEFT(tmp, rb);
348  } else if (comp > 0) {
349  tmp = RB_RIGHT(tmp, rb);
350  } else {
351  return tmp;
352  }
353  }
354  return res;
355 }
356 
358 {
359  const TCPHdr *tcph = PacketGetTCP(p);
360  const int records = TCP_GET_SACK_CNT(p);
361  const uint8_t *data = TCP_GET_SACK_PTR(p, tcph);
362  if (records > 0 && data != NULL) {
363  int sack_outdated = 0;
364  TCPOptSackRecord rec[records], *sack_rec = rec;
365  memcpy(&rec, data, sizeof(TCPOptSackRecord) * records);
366  for (int record = 0; record < records; record++) {
367  const uint32_t le = SCNtohl(sack_rec->le);
368  const uint32_t re = SCNtohl(sack_rec->re);
369  SCLogDebug("%p last_ack %u, left edge %u, right edge %u", sack_rec, stream->last_ack,
370  le, re);
371 
372  struct StreamTcpSackRecord lookup = { .le = le, .re = re };
373  struct StreamTcpSackRecord *res = FindOverlap(&stream->sack_tree, &lookup);
374  SCLogDebug("res %p", res);
375  if (res) {
376  if (le >= res->le && re <= res->re) {
377  SCLogDebug("SACK rec le:%u re:%u eclipsed by in tree le:%u re:%u", le, re,
378  res->le, res->re);
379  sack_outdated++;
380  } else {
381  SCLogDebug("SACK rec le:%u re:%u SACKs new DATA vs in tree le:%u re:%u", le, re,
382  res->le, res->re);
383  }
384  } else {
385  SCLogDebug("SACK rec le:%u re:%u SACKs new DATA. No match in tree", le, re);
386  }
387  sack_rec++;
388  }
389 #ifdef DEBUG
390  StreamTcpSackPrintList(stream);
391 #endif
392  if (records != sack_outdated) {
393  // SACK tree needs updating
394  return false;
395  } else {
396  // SACK list is packet is completely outdated
397  return true;
398  }
399  }
400  return false;
401 }
402 
404 {
405  SCEnter();
406 
407  StreamTcpSackRecord *rec = NULL, *safe = NULL;
408  RB_FOREACH_SAFE(rec, TCPSACK, &stream->sack_tree, safe) {
409  if (SEQ_LT(rec->re, stream->last_ack)) {
410  SCLogDebug("removing le %u re %u", rec->le, rec->re);
411  stream->sack_size -= (rec->re - rec->le);
412  TCPSACK_RB_REMOVE(&stream->sack_tree, rec);
413  StreamTcpSackRecordFree(rec);
414 
415  } else if (SEQ_LT(rec->le, stream->last_ack)) {
416  SCLogDebug("adjusting record to le %u re %u", rec->le, rec->re);
417  /* last ack inside this record, update */
418  stream->sack_size -= (rec->re - rec->le);
419  rec->le = stream->last_ack;
420  stream->sack_size += (rec->re - rec->le);
421  break;
422  } else {
423  SCLogDebug("record beyond last_ack, nothing to do. Bailing out.");
424  break;
425  }
426  }
427 #ifdef DEBUG
428  StreamTcpSackPrintList(stream);
429 #endif
430  SCReturn;
431 }
432 
433 /**
434  * \brief Free SACK tree from a stream
435  *
436  * \param stream Stream to cleanup
437  */
439 {
440  SCEnter();
441 
442  StreamTcpSackRecord *rec = NULL, *safe = NULL;
443  RB_FOREACH_SAFE(rec, TCPSACK, &stream->sack_tree, safe) {
444  stream->sack_size -= (rec->re - rec->le);
445  TCPSACK_RB_REMOVE(&stream->sack_tree, rec);
446  StreamTcpSackRecordFree(rec);
447  }
448 
449  SCReturn;
450 }
451 
452 
453 #ifdef UNITTESTS
454 
455 /**
456  * \test Test the insertion of SACK ranges.
457  *
458  * \retval On success it returns 1 and on failure 0.
459  */
460 
461 static int StreamTcpSackTest01 (void)
462 {
463  TcpStream stream;
464  memset(&stream, 0, sizeof(stream));
465  stream.window = 100;
466 
467  StreamTcpSackInsertRange(&stream, 1, 10);
468  FAIL_IF_NOT(stream.sack_size == 9);
469  StreamTcpSackInsertRange(&stream, 10, 20);
470  FAIL_IF_NOT(stream.sack_size == 19);
471  StreamTcpSackInsertRange(&stream, 10, 20);
472  FAIL_IF_NOT(stream.sack_size == 19);
473  StreamTcpSackInsertRange(&stream, 1, 20);
474  FAIL_IF_NOT(stream.sack_size == 19);
475 #ifdef DEBUG
476  StreamTcpSackPrintList(&stream);
477 #endif /* DEBUG */
478 
479  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
480  FAIL_IF_NULL(rec);
481 
482  FAIL_IF(rec->le != 1);
483  FAIL_IF(rec->re != 20);
484 
485  FAIL_IF(StreamTcpSackedSize(&stream) != 19);
486  StreamTcpSackFreeList(&stream);
487  PASS;
488 }
489 
490 /**
491  * \test Test the insertion of SACK ranges.
492  *
493  * \retval On success it returns 1 and on failure 0.
494  */
495 
496 static int StreamTcpSackTest02 (void)
497 {
498  TcpStream stream;
499  memset(&stream, 0, sizeof(stream));
500  stream.window = 100;
501 
502  StreamTcpSackInsertRange(&stream, 10, 20);
503  StreamTcpSackInsertRange(&stream, 1, 20);
504 #ifdef DEBUG
505  StreamTcpSackPrintList(&stream);
506 #endif /* DEBUG */
507 
508  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
509  FAIL_IF_NULL(rec);
510 
511  FAIL_IF(rec->le != 1);
512  FAIL_IF(rec->re != 20);
513 
514  FAIL_IF(StreamTcpSackedSize(&stream) != 19);
515  StreamTcpSackFreeList(&stream);
516  PASS;
517 }
518 
519 /**
520  * \test Test the insertion of SACK ranges.
521  *
522  * \retval On success it returns 1 and on failure 0.
523  */
524 
525 static int StreamTcpSackTest03 (void)
526 {
527  TcpStream stream;
528  memset(&stream, 0, sizeof(stream));
529  stream.window = 100;
530 
531  StreamTcpSackInsertRange(&stream, 10, 20);
532  StreamTcpSackInsertRange(&stream, 5, 15);
533 #ifdef DEBUG
534  StreamTcpSackPrintList(&stream);
535 #endif /* DEBUG */
536  StreamTcpSackInsertRange(&stream, 15, 25);
537 #ifdef DEBUG
538  StreamTcpSackPrintList(&stream);
539 #endif /* DEBUG */
540 
541  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
542  FAIL_IF_NULL(rec);
543 
544  FAIL_IF(rec->le != 5);
545  FAIL_IF(rec->re != 25);
546 
547  FAIL_IF(StreamTcpSackedSize(&stream) != 20);
548  StreamTcpSackFreeList(&stream);
549  PASS;
550 }
551 
552 /**
553  * \test Test the insertion of SACK ranges.
554  *
555  * \retval On success it returns 1 and on failure 0.
556  */
557 
558 static int StreamTcpSackTest04 (void)
559 {
560  TcpStream stream;
561  memset(&stream, 0, sizeof(stream));
562  stream.window = 100;
563 
564  StreamTcpSackInsertRange(&stream, 0, 20);
565  StreamTcpSackInsertRange(&stream, 30, 50);
566  StreamTcpSackInsertRange(&stream, 10, 25);
567 #ifdef DEBUG
568  StreamTcpSackPrintList(&stream);
569 #endif /* DEBUG */
570 
571  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
572  FAIL_IF_NULL(rec);
573 
574  FAIL_IF(rec->le != 0);
575  FAIL_IF(rec->re != 25);
576 
577  FAIL_IF(StreamTcpSackedSize(&stream) != 45);
578  StreamTcpSackFreeList(&stream);
579  PASS;
580 }
581 
582 /**
583  * \test Test the insertion of SACK ranges.
584  *
585  * \retval On success it returns 1 and on failure 0.
586  */
587 
588 static int StreamTcpSackTest05 (void)
589 {
590  TcpStream stream;
591  memset(&stream, 0, sizeof(stream));
592  stream.window = 100;
593 
594  StreamTcpSackInsertRange(&stream, 0, 20);
595  StreamTcpSackInsertRange(&stream, 30, 50);
596  StreamTcpSackInsertRange(&stream, 10, 35);
597 #ifdef DEBUG
598  StreamTcpSackPrintList(&stream);
599 #endif /* DEBUG */
600 
601  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
602  FAIL_IF_NULL(rec);
603 
604  FAIL_IF(rec->le != 0);
605  FAIL_IF(rec->re != 50);
606 
607  FAIL_IF(StreamTcpSackedSize(&stream) != 50);
608  StreamTcpSackFreeList(&stream);
609  PASS;
610 }
611 
612 /**
613  * \test Test the insertion of SACK ranges.
614  *
615  * \retval On success it returns 1 and on failure 0.
616  */
617 
618 static int StreamTcpSackTest06 (void)
619 {
620  TcpStream stream;
621  memset(&stream, 0, sizeof(stream));
622  stream.window = 100;
623 
624  StreamTcpSackInsertRange(&stream, 0, 9);
625  StreamTcpSackInsertRange(&stream, 11, 19);
626  StreamTcpSackInsertRange(&stream, 21, 29);
627  StreamTcpSackInsertRange(&stream, 31, 39);
628  StreamTcpSackInsertRange(&stream, 0, 40);
629 #ifdef DEBUG
630  StreamTcpSackPrintList(&stream);
631 #endif /* DEBUG */
632 
633  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
634  FAIL_IF_NULL(rec);
635 
636  FAIL_IF(rec->le != 0);
637  FAIL_IF(rec->re != 40);
638 
639  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
640  StreamTcpSackFreeList(&stream);
641  PASS;
642 }
643 
644 /**
645  * \test Test the pruning of SACK ranges.
646  *
647  * \retval On success it returns 1 and on failure 0.
648  */
649 
650 static int StreamTcpSackTest07 (void)
651 {
652  TcpStream stream;
653  memset(&stream, 0, sizeof(stream));
654  stream.window = 100;
655 
656  StreamTcpSackInsertRange(&stream, 0, 9);
657  StreamTcpSackInsertRange(&stream, 11, 19);
658  StreamTcpSackInsertRange(&stream, 21, 29);
659  StreamTcpSackInsertRange(&stream, 31, 39);
660  StreamTcpSackInsertRange(&stream, 0, 40);
661 #ifdef DEBUG
662  StreamTcpSackPrintList(&stream);
663 #endif /* DEBUG */
664 
665  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
666  FAIL_IF_NULL(rec);
667  FAIL_IF(rec->le != 0);
668  FAIL_IF(rec->re != 40);
669  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
670 
671  stream.last_ack = 10;
672  StreamTcpSackPruneList(&stream);
673  FAIL_IF(StreamTcpSackedSize(&stream) != 30);
674 
675  StreamTcpSackFreeList(&stream);
676  PASS;
677 }
678 
679 /**
680  * \test Test the pruning of SACK ranges.
681  *
682  * \retval On success it returns 1 and on failure 0.
683  */
684 
685 static int StreamTcpSackTest08 (void)
686 {
687  TcpStream stream;
688  memset(&stream, 0, sizeof(stream));
689  stream.window = 100;
690 
691  StreamTcpSackInsertRange(&stream, 0, 9);
692  StreamTcpSackInsertRange(&stream, 11, 19);
693  StreamTcpSackInsertRange(&stream, 21, 29);
694  StreamTcpSackInsertRange(&stream, 31, 39);
695  StreamTcpSackInsertRange(&stream, 0, 40);
696 #ifdef DEBUG
697  StreamTcpSackPrintList(&stream);
698 #endif /* DEBUG */
699 
700  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
701  FAIL_IF_NULL(rec);
702  FAIL_IF(rec->le != 0);
703  FAIL_IF(rec->re != 40);
704  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
705 
706  stream.last_ack = 41;
707  StreamTcpSackPruneList(&stream);
708  FAIL_IF(StreamTcpSackedSize(&stream) != 0);
709 
710  StreamTcpSackFreeList(&stream);
711  PASS;
712 }
713 
714 /**
715  * \test Test the pruning of SACK ranges.
716  *
717  * \retval On success it returns 1 and on failure 0.
718  */
719 
720 static int StreamTcpSackTest09 (void)
721 {
722  TcpStream stream;
723  memset(&stream, 0, sizeof(stream));
724  stream.window = 100;
725 
726  StreamTcpSackInsertRange(&stream, 0, 9);
727  StreamTcpSackInsertRange(&stream, 11, 19);
728  StreamTcpSackInsertRange(&stream, 21, 29);
729  StreamTcpSackInsertRange(&stream, 31, 39);
730  StreamTcpSackInsertRange(&stream, 0, 40);
731 
732 #ifdef DEBUG
733  StreamTcpSackPrintList(&stream);
734 #endif /* DEBUG */
735 
736  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
737  FAIL_IF_NULL(rec);
738  FAIL_IF(rec->le != 0);
739  FAIL_IF(rec->re != 40);
740  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
741 
742  stream.last_ack = 39;
743  StreamTcpSackPruneList(&stream);
744  FAIL_IF(StreamTcpSackedSize(&stream) != 1);
745 
746  StreamTcpSackFreeList(&stream);
747  PASS;
748 }
749 
750 /**
751  * \test Test the pruning of SACK ranges.
752  *
753  * \retval On success it returns 1 and on failure 0.
754  */
755 
756 static int StreamTcpSackTest10 (void)
757 {
758  TcpStream stream;
759  memset(&stream, 0, sizeof(stream));
760  stream.window = 1000;
761 
762  StreamTcpSackInsertRange(&stream, 100, 119);
763  StreamTcpSackInsertRange(&stream, 111, 119);
764  StreamTcpSackInsertRange(&stream, 121, 129);
765  StreamTcpSackInsertRange(&stream, 131, 139);
766  StreamTcpSackInsertRange(&stream, 100, 140);
767 #ifdef DEBUG
768  StreamTcpSackPrintList(&stream);
769 #endif /* DEBUG */
770 
771  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
772  FAIL_IF_NULL(rec);
773  FAIL_IF(rec->le != 100);
774  FAIL_IF(rec->re != 140);
775  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
776 
777  stream.last_ack = 99;
778  StreamTcpSackPruneList(&stream);
779  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
780 
781  StreamTcpSackFreeList(&stream);
782  PASS;
783 }
784 
785 /**
786  * \test Test the pruning of SACK ranges.
787  *
788  * \retval On success it returns 1 and on failure 0.
789  */
790 
791 static int StreamTcpSackTest11 (void)
792 {
793  TcpStream stream;
794  memset(&stream, 0, sizeof(stream));
795  stream.window = 1000;
796 
797  StreamTcpSackInsertRange(&stream, 100, 119);
798  StreamTcpSackInsertRange(&stream, 111, 119);
799  StreamTcpSackInsertRange(&stream, 121, 129);
800  StreamTcpSackInsertRange(&stream, 131, 139);
801  StreamTcpSackInsertRange(&stream, 101, 140);
802 #ifdef DEBUG
803  StreamTcpSackPrintList(&stream);
804 #endif /* DEBUG */
805 
806  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
807  FAIL_IF_NULL(rec);
808  FAIL_IF(rec->le != 100);
809  FAIL_IF(rec->re != 140);
810  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
811 
812  stream.last_ack = 99;
813  StreamTcpSackPruneList(&stream);
814  FAIL_IF(StreamTcpSackedSize(&stream) != 40);
815 
816  StreamTcpSackFreeList(&stream);
817  PASS;
818 }
819 
820 /**
821  * \test Test the pruning of SACK ranges.
822  *
823  * \retval On success it returns 1 and on failure 0.
824  */
825 
826 static int StreamTcpSackTest12 (void)
827 {
828  TcpStream stream;
829  memset(&stream, 0, sizeof(stream));
830  stream.window = 2000;
831 
832  StreamTcpSackInsertRange(&stream, 800, 1000);
833  StreamTcpSackInsertRange(&stream, 700, 900);
834  StreamTcpSackInsertRange(&stream, 600, 800);
835  StreamTcpSackInsertRange(&stream, 500, 700);
836  StreamTcpSackInsertRange(&stream, 100, 600);
837 #ifdef DEBUG
838  StreamTcpSackPrintList(&stream);
839 #endif /* DEBUG */
840 
841  StreamTcpSackRecord *rec = RB_MIN(TCPSACK, &stream.sack_tree);
842  FAIL_IF_NULL(rec);
843  FAIL_IF(rec->le != 100);
844  FAIL_IF(rec->re != 1000);
845  FAIL_IF(StreamTcpSackedSize(&stream) != 900);
846 
847  StreamTcpSackInsertRange(&stream, 0, 1000);
848  FAIL_IF(StreamTcpSackedSize(&stream) != 1000);
849 
850  stream.last_ack = 500;
851  StreamTcpSackPruneList(&stream);
852  FAIL_IF(StreamTcpSackedSize(&stream) != 500);
853 
854  StreamTcpSackFreeList(&stream);
855  PASS;
856 }
857 
858 /**
859  * \test Test the insertion on out of window condition.
860  *
861  * \retval On success it returns 1 and on failure 0.
862  */
863 
864 static int StreamTcpSackTest13 (void) {
865  TcpStream stream;
866  memset(&stream, 0, sizeof(stream));
867  stream.last_ack = 10000;
868  stream.window = 2000;
869 
870  for (int i = 0; i < 10; i++) {
871  StreamTcpSackInsertRange(&stream, 100+(20*i), 110+(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 /**
884  * \test Test the insertion of out of window condition.
885  *
886  * \retval On success it returns 1 and on failure 0.
887  */
888 
889 static int StreamTcpSackTest14 (void) {
890  TcpStream stream;
891  memset(&stream, 0, sizeof(stream));
892  stream.last_ack = 1000;
893  stream.window = 2000;
894 
895  for (int i = 0; i < 10; i++) {
896  StreamTcpSackInsertRange(&stream, 4000+(20*i), 4010+(20*i));
897  }
898 #ifdef DEBUG
899  StreamTcpSackPrintList(&stream);
900 #endif /* DEBUG */
901 
902  FAIL_IF(StreamTcpSackedSize(&stream) != 0);
903 
904  StreamTcpSackFreeList(&stream);
905  PASS;
906 }
907 
908 #endif /* UNITTESTS */
909 
911 {
912 #ifdef UNITTESTS
913  UtRegisterTest("StreamTcpSackTest01 -- Insertion", StreamTcpSackTest01);
914  UtRegisterTest("StreamTcpSackTest02 -- Insertion", StreamTcpSackTest02);
915  UtRegisterTest("StreamTcpSackTest03 -- Insertion", StreamTcpSackTest03);
916  UtRegisterTest("StreamTcpSackTest04 -- Insertion", StreamTcpSackTest04);
917  UtRegisterTest("StreamTcpSackTest05 -- Insertion", StreamTcpSackTest05);
918  UtRegisterTest("StreamTcpSackTest06 -- Insertion", StreamTcpSackTest06);
919  UtRegisterTest("StreamTcpSackTest07 -- Pruning", StreamTcpSackTest07);
920  UtRegisterTest("StreamTcpSackTest08 -- Pruning", StreamTcpSackTest08);
921  UtRegisterTest("StreamTcpSackTest09 -- Pruning", StreamTcpSackTest09);
922  UtRegisterTest("StreamTcpSackTest10 -- Pruning", StreamTcpSackTest10);
923  UtRegisterTest("StreamTcpSackTest11 -- Insertion && Pruning",
924  StreamTcpSackTest11);
925  UtRegisterTest("StreamTcpSackTest12 -- Insertion && Pruning",
926  StreamTcpSackTest12);
927  UtRegisterTest("StreamTcpSackTest13 -- Insertion out of window",
928  StreamTcpSackTest13);
929  UtRegisterTest("StreamTcpSackTest14 -- Insertion out of window",
930  StreamTcpSackTest14);
931 #endif
932 }
StreamTcpIncrMemuse
void StreamTcpIncrMemuse(uint64_t size)
Definition: stream-tcp.c:228
TcpStream_
Definition: stream-tcp-private.h:106
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:269
Packet_::pcap_cnt
uint64_t pcap_cnt
Definition: decode.h:618
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:438
STREAM_PKT_FLAG_DSACK
#define STREAM_PKT_FLAG_DSACK
Definition: stream-tcp-private.h:318
RB_LEFT
#define RB_LEFT(elm, field)
Definition: tree.h:322
StreamTcpSackRegisterTests
void StreamTcpSackRegisterTests(void)
Definition: stream-tcp-sack.c:910
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:47
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:115
StreamTcpCheckMemcap
int StreamTcpCheckMemcap(uint64_t size)
Check if alloc'ing "size" would mean we're over memcap.
Definition: stream-tcp.c:268
PASS
#define PASS
Pass the test.
Definition: util-unittest.h:105
RB_ROOT
#define RB_ROOT(head)
Definition: tree.h:326
RB_FOREACH_SAFE
#define RB_FOREACH_SAFE(x, name, head, y)
Definition: tree.h:791
SCEnter
#define SCEnter(...)
Definition: util-debug.h:271
TcpStream_::sack_tree
struct TCPSACK sack_tree
Definition: stream-tcp-private.h:141
TcpStream_::next_win
uint32_t next_win
Definition: stream-tcp-private.h:116
RB_FOREACH
#define RB_FOREACH(x, name, head)
Definition: tree.h:781
SCReturn
#define SCReturn
Definition: util-debug.h:273
Packet_
Definition: decode.h:491
TCP_GET_SACK_CNT
#define TCP_GET_SACK_CNT(p)
Definition: decode-tcp.h:104
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:117
TCPOptSackRecord_
Definition: decode-tcp.h:143
TCP_GET_SACK_PTR
#define TCP_GET_SACK_PTR(p, tcph)
Definition: decode-tcp.h:103
TcpStream_::sack_size
uint32_t sack_size
Definition: stream-tcp-private.h:139
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:260
StreamTcpSackPacketIsOutdated
bool StreamTcpSackPacketIsOutdated(TcpStream *stream, Packet *p)
Definition: stream-tcp-sack.c:357
suricata-common.h
SEQ_GT
#define SEQ_GT(a, b)
Definition: stream-tcp-private.h:259
RB_GENERATE
RB_GENERATE(TCPSACK, StreamTcpSackRecord, rb, TcpSackCompare)
TCPOptSackRecord_::le
uint32_t le
Definition: decode-tcp.h:144
SCMalloc
#define SCMalloc(sz)
Definition: util-mem.h:47
TCPOptSackRecord_::re
uint32_t re
Definition: decode-tcp.h:145
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:413
SEQ_LT
#define SEQ_LT(a, b)
Definition: stream-tcp-private.h:257
SEQ_EQ
#define SEQ_EQ(a, b)
Definition: stream-tcp-private.h:256
STREAM_PKT_FLAG_SET
#define STREAM_PKT_FLAG_SET(p, f)
Definition: stream-tcp-private.h:324
SEQ_LEQ
#define SEQ_LEQ(a, b)
Definition: stream-tcp-private.h:258
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
TCP_GET_RAW_ACK
#define TCP_GET_RAW_ACK(tcph)
Definition: decode-tcp.h:81
SCReturnInt
#define SCReturnInt(x)
Definition: util-debug.h:275
StreamTcpSackRecord::re
uint32_t re
Definition: stream-tcp-private.h:48
StreamTcpDecrMemuse
void StreamTcpDecrMemuse(uint64_t size)
Definition: stream-tcp.c:235
StreamTcpSackRecord
Definition: stream-tcp-private.h:46
TCPHdr_
Definition: decode-tcp.h:149
StreamTcpSackPruneList
void StreamTcpSackPruneList(TcpStream *stream)
Definition: stream-tcp-sack.c:403