27 #define DUMP_REGIONS 0 // set to 1 to dump a visual representation of the regions list and sbb tree.
39 #define CALLOC(cfg, n, s) \
40 (cfg)->Calloc ? (cfg)->Calloc((n), (s)) : SCCalloc((n), (s))
41 #define REALLOC(cfg, ptr, orig_s, s) \
42 (cfg)->Realloc ? (cfg)->Realloc((ptr), (orig_s), (s)) : SCRealloc((ptr), (s))
43 #define FREE(cfg, ptr, s) \
44 (cfg)->Free ? (cfg)->Free((ptr), (s)) : SCFree((ptr))
71 const uint64_t lre = lookup->
offset + lookup->
len;
72 const uint64_t tre = intree->
offset + intree->
len;
75 else if (lookup->
offset < tre && lre <= tre)
89 const int comp = InclusiveCompare(elm, tmp);
94 }
else if (comp > 0) {
116 if (aux_r->
buf == NULL) {
117 FREE(cfg, aux_r,
sizeof(*aux_r));
144 if (InitBuffer(sb, cfg) == 0) {
171 FREE(cfg, r,
sizeof(*r));
224 FREE(cfg, sbb,
sizeof(*sbb));
228 sbb2->
len = data_len;
277 const uint64_t tr_re = tr->
offset + tr->
len;
298 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u REMOVED ECLIPSED (sa overlapped by tr)", tr,
300 SBB_RB_REMOVE(tree, tr);
310 }
else if (sa->
offset <= tr->
offset && sa_re >= tr_re) {
311 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u REMOVED ECLIPSED (tr overlapped by sa)", tr,
313 SBB_RB_REMOVE(tree, tr);
317 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
" bo %u sz %u", sa,
324 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
325 " bo %u sz %u BUF_OFFSET UPDATED",
336 sa_re >= tr->
offset && sa_re < tr_re)
339 uint32_t combined_len = sa->
len + tr->
len;
343 SBB_RB_REMOVE(tree, tr);
347 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
" bo %u sz %u", sa,
354 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
355 " bo %u sz %u BUF_OFFSET UPDATED",
371 const uint64_t tr_re = tr->
offset + tr->
len;
390 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u REMOVED ECLIPSED (sa overlapped by tr)", tr,
394 SBB_RB_REMOVE(tree, tr);
404 }
else if (sa->
offset <= tr->
offset && sa_re >= tr_re) {
405 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u REMOVED ECLIPSED (tr overlapped by sa)", tr,
409 SBB_RB_REMOVE(tree, tr);
413 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
" bo %u sz %u", sa,
421 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
422 " bo %u sz %u BUF_OFFSET UPDATED",
435 uint32_t combined_len = sa->
len + tr->
len;
442 SBB_RB_REMOVE(tree, tr);
446 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
" bo %u sz %u", sa,
453 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
454 " bo %u sz %u BUF_OFFSET UPDATED",
480 SCLogDebug(
"* insert failed: exact match in tree with %p %" PRIu64
"/%u", res, res->
offset,
488 if (SBB_RB_PREV(sbb) == NULL) {
491 ConsolidateBackward(sb, cfg, region, tree, sbb);
493 ConsolidateFwd(sb, cfg, region, tree, sbb);
539 if (sbb->
len >= shrink_by) {
540 sbb->
len -= shrink_by;
567 static thread_local
bool g2s_warn_once =
false;
574 if (!g2s_warn_once) {
575 SCLogWarning(
"StreamingBuffer::GrowRegionToSize() tried to alloc %u bytes, exceeds "
578 g2s_warn_once =
true;
585 uint32_t base = size - x;
586 uint32_t grow = base + cfg->
buf_size;
594 size_t diff = grow - region->
buf_size;
595 void *new_mem = ((
char *)ptr) + region->
buf_size;
596 memset(new_mem, 0, diff);
602 if (region->
buf_size > sb->buf_size_max) {
603 sb->buf_size_max = region->
buf_size;
612 return GrowRegionToSize(sb, cfg, &sb->
region, size);
652 static inline void StreamingBufferSlideToOffsetWithRegions(
658 SCLogDebug(
"slide_offset %" PRIu64, slide_offset);
663 const bool main_is_oow = RegionBeforeOffset(&sb->
region, slide_offset);
684 if (RegionBeforeOffset(r, slide_offset)) {
691 FREE(cfg, r,
sizeof(*r));
694 }
else if (RegionContainsOffset(r, slide_offset)) {
713 SCLogDebug(
"shift start region %p", to_shift);
720 if (to_shift != &sb->
region) {
729 FREE(cfg, to_shift,
sizeof(*to_shift));
739 const uint32_t new_size = to_shift->
buf_size - s;
741 memmove(to_shift->
buf, to_shift->
buf + s, new_size);
746 if (s < to_shift->buf_offset)
773 StreamingBufferSlideToOffsetWithRegions(sb, cfg,
offset);
791 if (sb->
head != NULL) {
795 SCLogDebug(
"sliding %u forward, size of original buffer left after slide %u", slide,
811 SCLogDebug(
"sliding %u forward, size of original buffer left after slide %u", slide,
830 #define DATA_FITS(sb, len) ((sb)->region.buf_offset + (len) <= (sb)->region.buf_size)
836 if (InitBuffer(sb, cfg) == -1)
842 if (GrowToSize(sb, cfg, data_len) != 0)
851 StreamingBufferSegment *seg =
CALLOC(cfg, 1,
sizeof(StreamingBufferSegment));
855 seg->segment_len = data_len;
860 SBBUpdate(sb, cfg, &sb->
region, rel_offset, data_len);
868 StreamingBufferSegment *seg,
const uint8_t *data, uint32_t data_len)
873 if (InitBuffer(sb, cfg) == -1)
879 if (GrowToSize(sb, cfg, data_len) != 0)
890 seg->segment_len = data_len;
895 SBBUpdate(sb, cfg, &sb->
region, rel_offset, data_len);
904 const uint8_t *data, uint32_t data_len)
907 if (InitBuffer(sb, cfg) == -1)
913 if (GrowToSize(sb, cfg, data_len) != 0)
927 SBBUpdate(sb, cfg, &sb->
region, rel_offset, data_len);
932 #define DATA_FITS_AT_OFFSET(region, len, offset) ((offset) + (len) <= (region)->buf_size)
934 #if defined(DEBUG) || defined(DEBUG_VALIDATION)
968 #if DUMP_REGIONS == 1
974 snprintf(gap,
sizeof(gap),
"[ gap:%" PRIu64
" ]",
978 printf(
"[ %s offset:%" PRIu64
" size:%u offset:%u ]%s", r == &sb->
region ?
"main" :
"aux",
982 bool at_least_one =
false;
987 if (last_re != sbb->
offset) {
988 printf(
"[ gap:%" PRIu64
" ]", sbb->
offset - last_re);
990 printf(
"[ sbb offset:%" PRIu64
" len:%u ]", sbb->
offset, sbb->
len);
998 #if defined(DEBUG) || defined(DEBUG_VALIDATION)
1013 const uint64_t reg_o =
1023 if (re >= reg_o && re <= reg_re) {
1024 SCLogDebug(
"r %p is in-scope: %" PRIu64
" >= %" PRIu64
" && %" PRIu64
" <= %" PRIu64, r, re,
1040 SCLogDebug(
"looking for first region matching %" PRIu64
"/%" PRIu64,
offset, data_re);
1042 for (; r != NULL; r = r->
next) {
1043 if (RegionsIntersect(sb, cfg, r,
offset, data_re) ==
true)
1054 SCLogDebug(
"starting at %p/%" PRIu64
", offset %" PRIu64
", data_re %" PRIu64, r,
1057 for (; r != NULL; r = r->
next) {
1060 SCLogDebug(
"checking: %p/%" PRIu64
"/%" PRIu64
", offset %" PRIu64
"/%" PRIu64, r,
1063 if (!RegionsIntersect(sb, cfg, r,
offset, data_re))
1080 for (; r != NULL; r = r->
next) {
1081 if (!RegionsIntersect(sb, cfg, r,
offset, data_re)) {
1096 const uint64_t data_offset,
const uint32_t data_len)
1098 const uint64_t data_re = data_offset + data_len;
1099 SCLogDebug(
"sb %p dst %p src_start %p src_end %p data_offset %" PRIu64
1100 "/data_len %u/data_re %" PRIu64,
1101 sb,
dst, src_start, src_end, data_offset, data_len, data_re);
1107 const uint32_t dst_size = dst_re - dst_offset;
1108 SCLogDebug(
"dst_offset %" PRIu64
", dst_re %" PRIu64
", dst_size %u", dst_offset, dst_re,
1112 const uint32_t old_size =
dst->buf_size;
1113 const uint32_t dst_copy_offset =
dst->stream_offset - dst_offset;
1115 const uint32_t old_offset =
dst->buf_offset;
1116 SCLogDebug(
"old_size %u, old_offset %u, dst_copy_offset %u", old_size, old_offset,
1119 if (GrowRegionToSize(sb, cfg,
dst, dst_size) != 0)
1122 if (dst_copy_offset != 0)
1123 memmove(
dst->buf + dst_copy_offset,
dst->buf, old_size);
1124 dst->stream_offset = dst_offset;
1128 new_offset += data_len;
1131 bool start_is_main =
false;
1133 if (src_start == &sb->
region) {
1136 start_is_main =
true;
1138 if (src_start !=
dst)
1140 if (src_start == src_end) {
1141 SCLogDebug(
"src_start == src_end == main, we're done");
1146 src_start = src_start->
next;
1156 SCLogDebug(
"skipping r %p as it is 'dst'", r);
1163 const uint32_t target_offset = r->
stream_offset - dst_offset;
1164 SCLogDebug(
"r %p: target_offset %u", r, target_offset);
1169 FREE(cfg, r,
sizeof(*r));
1187 if (start_is_main &&
dst != &sb->
region) {
1189 SCLogDebug(
"start_is_main && dst != main region");
1204 SCLogDebug(
"returning dst %p stream_offset %" PRIu64
" buf_offset %u buf_size %u",
dst,
1205 dst->stream_offset,
dst->buf_offset,
dst->buf_size);
1227 BufferInsertAtRegionConsolidate(sb, cfg, big, start, end,
offset,
len);
1240 SCLogDebug(
"no matching region found, append to %p (%s)", append,
1241 append == &sb->
region ?
"main" :
"aux");
1262 const uint64_t data_offset)
1264 SCLogDebug(
"data_offset %" PRIu64
", data_len %u, re %" PRIu64, data_offset, data_len,
1265 data_offset + data_len);
1268 if (RegionsIntersect(sb, cfg, &sb->
region, data_offset, data_len)) {
1269 SCLogDebug(
"data_offset %" PRIu64
", data_len %u intersects with main region (next %p)",
1272 !RegionsIntersect(sb, cfg, sb->
region.
next, data_offset, data_len)) {
1274 "data_offset %" PRIu64
1275 ", data_len %u intersects with main region, no next or way before next region",
1276 data_offset, data_len);
1278 if (InitBuffer(sb, cfg) == -1)
1288 SCLogDebug(
"created new region %p with offset %" PRIu64
", size %u", aux_r,
1305 StreamingBufferSegment *seg,
const uint8_t *data, uint32_t data_len, uint64_t
offset)
1313 if (region == NULL) {
1317 const bool region_is_main = region == &sb->
region;
1319 SCLogDebug(
"inserting %" PRIu64
"/%u using %s region %p",
offset, data_len,
1320 region == &sb->
region ?
"main" :
"aux", region);
1324 if (GrowToSize(sb, cfg, (rel_offset + data_len)) != 0)
1329 SCLogDebug(
"offset %" PRIu64
" data_len %u, rel_offset %u into region offset %" PRIu64
1330 ", buf_offset %u, buf_size %u",
1333 memcpy(region->
buf + rel_offset, data, data_len);
1334 seg->stream_offset =
offset;
1335 seg->segment_len = data_len;
1337 SCLogDebug(
"rel_offset %u region->stream_offset %" PRIu64
", buf_offset %u", rel_offset,
1343 if (region_is_main) {
1345 SCLogDebug(
"empty sbb list: block exactly what was expected, fall through");
1351 SCLogDebug(
"empty sbb list: block is within existing main data region");
1358 }
else if (rel_offset < sb->region.
buf_offset) {
1361 SCLogDebug(
"before expected offset: %u < sb->region.buf_offset %u", rel_offset,
1364 SCLogDebug(
"before expected offset, ends after: %u < sb->region.buf_offset "
1372 SCLogDebug(
"beyond expected offset: SBBInit");
1374 SBBInit(sb, cfg, region, rel_offset, data_len);
1377 SCLogDebug(
"empty sbb list: invoking SBBInitLeadingGap");
1378 SBBInitLeadingGap(sb, cfg, region,
offset, data_len);
1384 SCLogDebug(
"empty sbb list, no data in main: use SBBInit");
1385 SBBInit(sb, cfg, region, rel_offset, data_len);
1388 SCLogDebug(
"empty sbb list: invoking SBBInitLeadingGap");
1389 SBBInitLeadingGap(sb, cfg, region,
offset, data_len);
1400 SBBUpdate(sb, cfg, region, rel_offset, data_len);
1413 const StreamingBufferSegment *seg)
1446 const uint8_t **data, uint32_t *data_len)
1450 SCLogDebug(
"first find our region (offset %" PRIu64
") -> %p", sbb->
offset, region);
1459 *data_len = sbb->
len;
1464 if (offset < sbb->
len) {
1465 *data = region->
buf;
1480 const uint8_t **data, uint32_t *data_len,
1497 *data = region->
buf + data_offset;
1498 if (data_offset + sbblen > region->
buf_size)
1499 *data_len = region->
buf_size - data_offset;
1502 BUG_ON(*data_len > sbblen);
1506 if (data_offset < sbblen) {
1507 *data = region->
buf;
1508 *data_len = sbblen - data_offset;
1509 BUG_ON(*data_len > sbblen);
1521 const StreamingBufferSegment *seg,
1522 const uint8_t **data, uint32_t *data_len)
1532 *data_len = seg->segment_len;
1538 *data = region->
buf;
1539 *data_len = seg->segment_len -
offset;
1555 const StreamingBufferSegment *seg,
1556 const uint8_t *rawdata, uint32_t rawdata_len)
1558 const uint8_t *segdata = NULL;
1559 uint32_t segdata_len = 0;
1561 if (segdata && segdata_len &&
1562 segdata_len == rawdata_len &&
1563 memcmp(segdata, rawdata, segdata_len) == 0)
1571 const uint8_t **data, uint32_t *data_len,
1574 if (sb != NULL && sb->
region.
buf != NULL) {
1588 const uint8_t **data, uint32_t *data_len,
1595 *data = region->
buf + skip;
1610 const uint8_t *rawdata, uint32_t rawdata_len)
1612 const uint8_t *sbdata = NULL;
1613 uint32_t sbdata_len = 0;
1617 sbdata && sbdata_len &&
1618 sbdata_len == rawdata_len &&
1619 memcmp(sbdata, rawdata, sbdata_len) == 0)
1626 printf(
"wanted:\n");
1637 static void DumpSegment(
StreamingBuffer *sb, StreamingBufferSegment *seg)
1639 const uint8_t *data = NULL;
1640 uint32_t data_len = 0;
1642 if (data && data_len) {
1647 static int StreamingBufferTest02(
void)
1653 StreamingBufferSegment seg1;
1655 StreamingBufferSegment seg2;
1659 FAIL_IF(seg1.stream_offset != 0);
1660 FAIL_IF(seg2.stream_offset != 8);
1664 DumpSegment(sb, &seg1);
1665 DumpSegment(sb, &seg2);
1673 StreamingBufferSegment seg3;
1677 FAIL_IF(seg3.stream_offset != 16);
1682 DumpSegment(sb, &seg1);
1683 DumpSegment(sb, &seg2);
1684 DumpSegment(sb, &seg3);
1693 DumpSegment(sb, &seg1);
1694 DumpSegment(sb, &seg2);
1695 DumpSegment(sb, &seg3);
1703 static int StreamingBufferTest03(
void)
1709 StreamingBufferSegment seg1;
1711 StreamingBufferSegment seg2;
1715 FAIL_IF(seg1.stream_offset != 0);
1716 FAIL_IF(seg2.stream_offset != 14);
1720 DumpSegment(sb, &seg1);
1721 DumpSegment(sb, &seg2);
1726 StreamingBufferSegment seg3;
1730 FAIL_IF(seg3.stream_offset != 8);
1735 DumpSegment(sb, &seg1);
1736 DumpSegment(sb, &seg2);
1737 DumpSegment(sb, &seg3);
1747 DumpSegment(sb, &seg1);
1748 DumpSegment(sb, &seg2);
1749 DumpSegment(sb, &seg3);
1758 static int StreamingBufferTest04(
void)
1764 StreamingBufferSegment seg1;
1767 StreamingBufferSegment seg2;
1771 FAIL_IF(seg1.stream_offset != 0);
1772 FAIL_IF(seg2.stream_offset != 14);
1787 DumpSegment(sb, &seg1);
1788 DumpSegment(sb, &seg2);
1791 StreamingBufferSegment seg3;
1795 FAIL_IF(seg3.stream_offset != 8);
1806 DumpSegment(sb, &seg1);
1807 DumpSegment(sb, &seg2);
1808 DumpSegment(sb, &seg3);
1814 StreamingBufferSegment seg4;
1819 FAIL_IF(seg4.stream_offset != 124);
1831 DumpSegment(sb, &seg1);
1832 DumpSegment(sb, &seg2);
1833 DumpSegment(sb, &seg3);
1834 DumpSegment(sb, &seg4);
1849 static int StreamingBufferTest06(
void)
1855 StreamingBufferSegment seg1;
1857 StreamingBufferSegment seg2;
1864 StreamingBufferSegment seg3;
1871 StreamingBufferSegment seg4;
1878 StreamingBufferSegment seg5;
1890 StreamingBufferSegment seg6;
1907 static int StreamingBufferTest07(
void)
1913 StreamingBufferSegment seg1;
1915 StreamingBufferSegment seg2;
1922 StreamingBufferSegment seg3;
1929 StreamingBufferSegment seg4;
1936 StreamingBufferSegment seg5;
1948 StreamingBufferSegment seg6;
1965 static int StreamingBufferTest08(
void)
1971 StreamingBufferSegment seg1;
1973 StreamingBufferSegment seg2;
1980 StreamingBufferSegment seg3;
1987 StreamingBufferSegment seg4;
1994 StreamingBufferSegment seg5;
2006 StreamingBufferSegment seg6;
2023 static int StreamingBufferTest09(
void)
2029 StreamingBufferSegment seg1;
2031 StreamingBufferSegment seg2;
2038 StreamingBufferSegment seg3;
2045 StreamingBufferSegment seg4;
2052 StreamingBufferSegment seg5;
2064 StreamingBufferSegment seg6;
2081 static int StreamingBufferTest10(
void)
2087 StreamingBufferSegment seg1;
2090 StreamingBufferSegment seg2;
2093 StreamingBufferSegment seg3;
2099 StreamingBufferSegment seg4;
2102 StreamingBufferSegment seg5;
2105 StreamingBufferSegment seg6;
2112 StreamingBufferSegment seg7;
2123 StreamingBufferSegment seg8;