32 #define DUMP_REGIONS 0 // set to 1 to dump a visual representation of the regions list and sbb tree.
42 static void *ReallocFunc(
void *ptr,
const size_t size)
51 static void *CallocFunc(
const size_t nm,
const size_t sz)
63 #define CALLOC(cfg, n, s) (cfg)->Calloc ? (cfg)->Calloc((n), (s)) : CallocFunc((n), (s))
64 #define REALLOC(cfg, ptr, orig_s, s) \
65 (cfg)->Realloc ? (cfg)->Realloc((ptr), (orig_s), (s)) : ReallocFunc((ptr), (s))
66 #define FREE(cfg, ptr, s) \
67 (cfg)->Free ? (cfg)->Free((ptr), (s)) : SCFree((ptr))
94 const uint64_t lre = lookup->
offset + lookup->
len;
95 const uint64_t tre = intree->
offset + intree->
len;
98 else if (lookup->
offset < tre && lre <= tre)
112 const int comp = InclusiveCompare(elm, tmp);
117 }
else if (comp > 0) {
134 const uint64_t reg_o =
144 if (re < reg_o || reg_re <
offset) {
158 SCLogDebug(
"looking for first region matching %" PRIu64
"/%" PRIu64,
offset, data_re);
161 for (; r != NULL; r = r->
next) {
162 if (RegionsIntersect(cfg, r,
offset, data_re)) {
176 SCLogDebug(
"starting at %p/%" PRIu64
", offset %" PRIu64
", data_re %" PRIu64, r,
179 for (; r != NULL; r = r->
next) {
182 SCLogDebug(
"checking: %p/%" PRIu64
"/%" PRIu64
", offset %" PRIu64
"/%" PRIu64, r,
185 if (!RegionsIntersect(cfg, r,
offset, data_re))
201 for (; r != NULL; r = r->
next) {
202 if (!RegionsIntersect(cfg, r,
offset, data_re)) {
228 if (aux_r->
buf == NULL) {
229 FREE(cfg, aux_r,
sizeof(*aux_r));
262 int r = InitBuffer(sb, cfg);
286 FREE(cfg, r,
sizeof(*r));
336 (void)SBB_RB_INSERT(&sb->
sbb_tree, sbb);
345 sbb2->
len = data_len;
351 if (SBB_RB_INSERT(&sb->
sbb_tree, sbb2) != NULL) {
352 FREE(cfg, sbb2,
sizeof(*sbb2));
380 (void)SBB_RB_INSERT(&sb->
sbb_tree, sbb);
398 const uint64_t tr_re = tr->
offset + tr->
len;
419 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u REMOVED ECLIPSED (sa overlapped by tr)", tr,
421 SBB_RB_REMOVE(tree, tr);
431 }
else if (sa->
offset <= tr->
offset && sa_re >= tr_re) {
432 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u REMOVED ECLIPSED (tr overlapped by sa)", tr,
434 SBB_RB_REMOVE(tree, tr);
438 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
" bo %u sz %u", sa,
446 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
447 " bo %u sz %u BUF_OFFSET UPDATED",
458 sa_re >= tr->
offset && sa_re < tr_re)
462 uint32_t combined_len = (uint32_t)(sa->
len + tr->
len);
464 sa->
len = (uint32_t)(tr_re - sa->
offset);
467 SBB_RB_REMOVE(tree, tr);
471 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
" bo %u sz %u", sa,
479 SCLogDebug(
"-> (fwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
480 " bo %u sz %u BUF_OFFSET UPDATED",
496 const uint64_t tr_re = tr->
offset + tr->
len;
515 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u REMOVED ECLIPSED (sa overlapped by tr)", tr,
519 SBB_RB_REMOVE(tree, tr);
529 }
else if (sa->
offset <= tr->
offset && sa_re >= tr_re) {
530 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u REMOVED ECLIPSED (tr overlapped by sa)", tr,
534 SBB_RB_REMOVE(tree, tr);
538 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
" bo %u sz %u", sa,
547 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
548 " bo %u sz %u BUF_OFFSET UPDATED",
562 uint32_t combined_len = (uint32_t)(sa->
len + tr->
len);
564 sa->
len = (uint32_t)(sa_re - tr->
offset);
570 SBB_RB_REMOVE(tree, tr);
574 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
" bo %u sz %u", sa,
582 SCLogDebug(
"-> (bwd) tr %p %" PRIu64
"/%u region %p so %" PRIu64
583 " bo %u sz %u BUF_OFFSET UPDATED",
610 SCLogDebug(
"* insert failed: exact match in tree with %p %" PRIu64
"/%u", res, res->
offset,
618 if (SBB_RB_PREV(sbb) == NULL) {
621 ConsolidateBackward(sb, cfg, region, tree, sbb);
623 ConsolidateFwd(sb, cfg, region, tree, sbb);
667 if (sbb->
len >= shrink_by) {
668 sbb->
len -= shrink_by;
695 static inline uint32_t ToNextMultipleOf(
const uint32_t in,
const uint32_t
m)
699 const uint32_t x = in %
m;
707 static thread_local
bool g2s_warn_once =
false;
714 if (!g2s_warn_once) {
715 SCLogWarning(
"StreamingBuffer::GrowRegionToSize() tried to alloc %u bytes, exceeds "
718 g2s_warn_once =
true;
724 const uint32_t grow = ToNextMultipleOf(size, cfg->
buf_size);
726 if (grow <= region->buf_size) {
739 size_t diff = grow - region->
buf_size;
740 void *new_mem = ((
char *)ptr) + region->
buf_size;
741 memset(new_mem, 0, diff);
747 if (region->
buf_size > sb->buf_size_max) {
748 sb->buf_size_max = region->
buf_size;
757 return GrowRegionToSize(sb, cfg, &sb->
region, size);
797 static inline void StreamingBufferSlideToOffsetWithRegions(
803 SCLogDebug(
"slide_offset %" PRIu64, slide_offset);
808 const bool main_is_oow = RegionBeforeOffset(&sb->
region, slide_offset);
829 if (RegionBeforeOffset(r, slide_offset)) {
836 FREE(cfg, r,
sizeof(*r));
839 }
else if (RegionContainsOffset(r, slide_offset)) {
858 if (to_shift && to_shift != &sb->
region) {
870 FREE(cfg, to_shift,
sizeof(*to_shift));
878 SCLogDebug(
"shift start region %p", to_shift);
886 const uint32_t s = (uint32_t)(slide_offset - to_shift->
stream_offset);
888 const uint32_t new_data_size = to_shift->
buf_size - s;
889 uint32_t new_mem_size = ToNextMultipleOf(new_data_size, cfg->
buf_size);
900 const uint64_t next_re =
next->stream_offset +
next->buf_size;
902 const uint32_t mem_size =
903 ToNextMultipleOf((uint32_t)(next_re - slide_offset), cfg->
buf_size);
907 SCLogDebug(
"replace main with the next bigger region");
910 const uint32_t next_data_offset =
911 (uint32_t)(
next->stream_offset - slide_offset);
912 const uint32_t prev_buf_size =
next->buf_size;
914 const uint32_t start_data_offset =
917 if (start_data_offset > start->
buf_size) {
918 new_mem_size = new_data_size;
922 if (GrowRegionToSize(sb, cfg,
next, mem_size) != 0) {
923 new_mem_size = new_data_size;
932 memmove(
next->buf + next_data_offset,
next->buf, prev_buf_size);
939 const uint32_t start_data_size = start->
buf_size - start_data_offset;
940 memcpy(
next->buf, start->
buf + start_data_offset, start_data_size);
961 if (GrowRegionToSize(sb, cfg, start, mem_size) != 0) {
962 new_mem_size = new_data_size;
966 SCLogDebug(
"start->buf now size %u", mem_size);
971 SCLogDebug(
"s %u new_data_size %u", s, new_data_size);
972 memmove(start->
buf, start->
buf + s, new_data_size);
978 SCLogDebug(
"copy next->buf %p/%u to start->buf offset %u",
next->buf,
979 next->buf_size, new_data_size);
980 memcpy(start->
buf + new_data_size,
next->buf,
next->buf_size);
995 SCLogDebug(
"s %u new_data_size %u", s, new_data_size);
996 memmove(to_shift->
buf, to_shift->
buf + s, new_data_size);
1000 to_shift->
buf = ptr;
1004 if (s < to_shift->buf_offset)
1032 StreamingBufferSlideToOffsetWithRegions(sb, cfg,
offset);
1051 if (sb->
head != NULL) {
1055 SCLogDebug(
"sliding %u forward, size of original buffer left after slide %u", slide,
1071 SCLogDebug(
"sliding %u forward, size of original buffer left after slide %u", slide,
1093 uint64_t len64 =
len;
1094 if (len64 + buf_offset64 > UINT32_MAX) {
1101 StreamingBufferSegment *seg,
const uint8_t *data, uint32_t data_len)
1107 if (InitBuffer(sb, cfg) == -1)
1111 int r = DataFits(sb, data_len);
1115 }
else if (r == 0) {
1117 if (GrowToSize(sb, cfg, data_len) !=
SC_OK)
1125 if (DataFits(sb, data_len) != 1)
1130 seg->segment_len = data_len;
1135 return SBBUpdate(sb, cfg, &sb->
region, rel_offset, data_len);
1145 const uint8_t *data, uint32_t data_len)
1150 if (InitBuffer(sb, cfg) == -1)
1154 int r = DataFits(sb, data_len);
1158 }
else if (r == 0) {
1160 if (GrowToSize(sb, cfg, data_len) !=
SC_OK)
1174 return SBBUpdate(sb, cfg, &sb->
region, rel_offset, data_len);
1180 static int DataFitsAtOffset(
1183 const uint64_t offset64 =
offset;
1184 const uint64_t len64 =
len;
1185 if (offset64 + len64 > UINT32_MAX)
1187 return (
offset + len <= region->buf_size);
1190 #if defined(DEBUG) || defined(DEBUG_VALIDATION)
1223 #if defined(DEBUG) && DUMP_REGIONS == 1
1229 snprintf(gap,
sizeof(gap),
"[ gap:%" PRIu64
" ]",
1233 printf(
"[ %s offset:%" PRIu64
" size:%u offset:%u ]%s", r == &sb->
region ?
"main" :
"aux",
1237 bool at_least_one =
false;
1242 if (last_re != sbb->
offset) {
1243 printf(
"[ gap:%" PRIu64
" ]", sbb->
offset - last_re);
1245 printf(
"[ sbb offset:%" PRIu64
" len:%u ]", sbb->
offset, sbb->
len);
1246 at_least_one =
true;
1252 #if defined(DEBUG) || defined(DEBUG_VALIDATION)
1256 const uint8_t *_data = NULL;
1257 uint32_t _data_len = 0;
1272 uint32_t dst_buf_size)
1276 const uint64_t data_re = data_offset + data_len;
1277 SCLogDebug(
"sb %p dst %p src_start %p src_end %p data_offset %" PRIu64
1278 "/data_len %u/data_re %" PRIu64,
1279 sb,
dst, src_start, src_end, data_offset, data_len, data_re);
1285 const uint32_t dst_size = dst_buf_size;
1289 const uint32_t old_size =
dst->buf_size;
1291 const uint32_t dst_copy_offset = (uint32_t)(
dst->stream_offset - dst_offset);
1293 const uint32_t old_offset =
dst->buf_offset;
1294 SCLogDebug(
"old_size %u, old_offset %u, dst_copy_offset %u", old_size, old_offset,
1297 if ((retval = GrowRegionToSize(sb, cfg,
dst, dst_size)) !=
SC_OK) {
1304 if (dst_copy_offset != 0)
1305 memmove(
dst->buf + dst_copy_offset,
dst->buf, old_size);
1306 if (dst_offset !=
dst->stream_offset) {
1307 dst->stream_offset = dst_offset;
1309 dst->buf_offset = 0;
1314 new_offset += data_len;
1317 bool start_is_main =
false;
1318 if (src_start == &sb->
region) {
1321 start_is_main =
true;
1323 if (src_start !=
dst)
1325 if (src_start == src_end) {
1326 SCLogDebug(
"src_start == src_end == main, we're done");
1331 src_start = src_start->
next;
1341 SCLogDebug(
"skipping r %p as it is 'dst'", r);
1349 const uint32_t target_offset = (uint32_t)(r->
stream_offset - dst_offset);
1350 SCLogDebug(
"r %p: target_offset %u", r, target_offset);
1357 FREE(cfg, r,
sizeof(*r));
1377 if (start_is_main &&
dst != &sb->
region) {
1379 SCLogDebug(
"start_is_main && dst != main region");
1394 SCLogDebug(
"returning dst %p stream_offset %" PRIu64
" buf_offset %u buf_size %u",
dst,
1395 dst->stream_offset,
dst->buf_offset,
dst->buf_size);
1408 const uint64_t insert_re =
offset +
len;
1410 uint64_t insert_adjusted_re = insert_re;
1429 uint32_t new_buf_size = ToNextMultipleOf(
1430 (uint32_t)(insert_adjusted_re - insert_start_offset), cfg->
buf_size);
1440 new_buf_size = ToNextMultipleOf(
1441 (uint32_t)(insert_adjusted_re - insert_start_offset), cfg->
buf_size);
1448 sb, cfg, big, start, end,
offset,
len, start_prev, new_buf_size);
1461 SCLogDebug(
"no matching region found, append to %p (%s)", append,
1462 append == &sb->
region ?
"main" :
"aux");
1487 SCLogDebug(
"data_offset %" PRIu64
", data_len %u, re %" PRIu64, data_offset, data_len,
1488 data_offset + data_len);
1491 if (RegionsIntersect(cfg, &sb->
region, data_offset, data_offset + data_len)) {
1492 SCLogDebug(
"data_offset %" PRIu64
", data_len %u intersects with main region (next %p)",
1495 !RegionsIntersect(cfg, sb->
region.
next, data_offset, data_offset + data_len)) {
1497 "data_offset %" PRIu64
1498 ", data_len %u intersects with main region, no next or way before next region",
1499 data_offset, data_len);
1502 if ((r = InitBuffer(sb, cfg)) !=
SC_OK) {
1516 SCLogDebug(
"created new region %p with offset %" PRIu64
", size %u", aux_r,
1533 StreamingBufferSegment *seg,
const uint8_t *data, uint32_t data_len, uint64_t
offset)
1543 if (region == NULL) {
1547 const bool region_is_main = region == &sb->
region;
1549 SCLogDebug(
"inserting %" PRIu64
"/%u using %s region %p",
offset, data_len,
1550 region == &sb->
region ?
"main" :
"aux", region);
1554 int r = DataFitsAtOffset(region, data_len, rel_offset);
1558 }
else if (r == 0) {
1559 if ((r = GrowToSize(sb, cfg, (rel_offset + data_len))) !=
SC_OK)
1564 SCLogDebug(
"offset %" PRIu64
" data_len %u, rel_offset %u into region offset %" PRIu64
1565 ", buf_offset %u, buf_size %u",
1568 memcpy(region->
buf + rel_offset, data, data_len);
1569 seg->stream_offset =
offset;
1570 seg->segment_len = data_len;
1572 SCLogDebug(
"rel_offset %u region->stream_offset %" PRIu64
", buf_offset %u", rel_offset,
1578 if (region_is_main) {
1580 SCLogDebug(
"empty sbb list: block exactly what was expected, fall through");
1586 SCLogDebug(
"empty sbb list: block is within existing main data region");
1593 }
else if (rel_offset < sb->region.
buf_offset) {
1596 SCLogDebug(
"before expected offset: %u < sb->region.buf_offset %u", rel_offset,
1599 SCLogDebug(
"before expected offset, ends after: %u < sb->region.buf_offset "
1607 SCLogDebug(
"beyond expected offset: SBBInit");
1609 if ((r = SBBInit(sb, cfg, region, rel_offset, data_len)) !=
SC_OK)
1613 SCLogDebug(
"empty sbb list: invoking SBBInitLeadingGap");
1614 if ((r = SBBInitLeadingGap(sb, cfg,
offset, data_len)) !=
SC_OK)
1621 SCLogDebug(
"empty sbb list, no data in main: use SBBInit");
1622 if ((r = SBBInit(sb, cfg, region, rel_offset, data_len)) !=
SC_OK)
1626 SCLogDebug(
"empty sbb list: invoking SBBInitLeadingGap");
1627 if ((r = SBBInitLeadingGap(sb, cfg,
offset, data_len)) !=
SC_OK)
1639 if ((r = SBBUpdate(sb, cfg, region, rel_offset, data_len)) !=
SC_OK)
1653 const StreamingBufferSegment *seg)
1676 if (
offset >= r->stream_offset &&
offset < (r->stream_offset + r->buf_size)) {
1686 const uint8_t **data, uint32_t *data_len)
1689 SCLogDebug(
"first find our region (offset %" PRIu64
") -> %p", sbb->
offset, region);
1702 *data_len = sbb->
len;
1707 if (offset < sbb->
len) {
1708 *data = region->
buf;
1722 const uint8_t **data, uint32_t *data_len,
1740 *data = region->
buf + data_offset;
1741 if (data_offset + sbblen > region->
buf_size) {
1742 *data_len = region->
buf_size - data_offset;
1750 if (data_offset < sbblen) {
1751 *data = region->
buf;
1752 *data_len = sbblen - data_offset;
1764 const StreamingBufferSegment *seg,
1765 const uint8_t **data, uint32_t *data_len)
1775 *data_len = seg->segment_len;
1782 *data = region->
buf;
1783 *data_len = seg->segment_len -
offset;
1798 const StreamingBufferSegment *seg,
1799 const uint8_t *rawdata, uint32_t rawdata_len)
1801 const uint8_t *segdata = NULL;
1802 uint32_t segdata_len = 0;
1804 if (segdata && segdata_len &&
1805 segdata_len == rawdata_len &&
1806 memcmp(segdata, rawdata, segdata_len) == 0)
1814 const uint8_t **data, uint32_t *data_len,
1817 if (sb != NULL && sb->
region.
buf != NULL) {
1831 const uint8_t **data, uint32_t *data_len,
1839 *data = region->
buf + skip;
1854 const uint8_t *rawdata, uint32_t rawdata_len)
1856 const uint8_t *sbdata = NULL;
1857 uint32_t sbdata_len = 0;
1861 sbdata && sbdata_len &&
1862 sbdata_len == rawdata_len &&
1863 memcmp(sbdata, rawdata, sbdata_len) == 0)
1870 printf(
"wanted:\n");
1881 static void DumpSegment(
StreamingBuffer *sb, StreamingBufferSegment *seg)
1883 const uint8_t *data = NULL;
1884 uint32_t data_len = 0;
1886 if (data && data_len) {
1891 static int StreamingBufferTest02(
void)
1897 StreamingBufferSegment seg1;
1899 StreamingBufferSegment seg2;
1903 FAIL_IF(seg1.stream_offset != 0);
1904 FAIL_IF(seg2.stream_offset != 8);
1908 DumpSegment(sb, &seg1);
1909 DumpSegment(sb, &seg2);
1917 StreamingBufferSegment seg3;
1921 FAIL_IF(seg3.stream_offset != 16);
1926 DumpSegment(sb, &seg1);
1927 DumpSegment(sb, &seg2);
1928 DumpSegment(sb, &seg3);
1937 DumpSegment(sb, &seg1);
1938 DumpSegment(sb, &seg2);
1939 DumpSegment(sb, &seg3);
1947 static int StreamingBufferTest03(
void)
1953 StreamingBufferSegment seg1;
1955 StreamingBufferSegment seg2;
1959 FAIL_IF(seg1.stream_offset != 0);
1960 FAIL_IF(seg2.stream_offset != 14);
1964 DumpSegment(sb, &seg1);
1965 DumpSegment(sb, &seg2);
1970 StreamingBufferSegment seg3;
1974 FAIL_IF(seg3.stream_offset != 8);
1979 DumpSegment(sb, &seg1);
1980 DumpSegment(sb, &seg2);
1981 DumpSegment(sb, &seg3);
1991 DumpSegment(sb, &seg1);
1992 DumpSegment(sb, &seg2);
1993 DumpSegment(sb, &seg3);
2002 static int StreamingBufferTest04(
void)
2008 StreamingBufferSegment seg1;
2011 StreamingBufferSegment seg2;
2015 FAIL_IF(seg1.stream_offset != 0);
2016 FAIL_IF(seg2.stream_offset != 14);
2031 DumpSegment(sb, &seg1);
2032 DumpSegment(sb, &seg2);
2035 StreamingBufferSegment seg3;
2039 FAIL_IF(seg3.stream_offset != 8);
2050 DumpSegment(sb, &seg1);
2051 DumpSegment(sb, &seg2);
2052 DumpSegment(sb, &seg3);
2058 StreamingBufferSegment seg4;
2063 FAIL_IF(seg4.stream_offset != 124);
2075 DumpSegment(sb, &seg1);
2076 DumpSegment(sb, &seg2);
2077 DumpSegment(sb, &seg3);
2078 DumpSegment(sb, &seg4);
2093 static int StreamingBufferTest06(
void)
2099 StreamingBufferSegment seg1;
2101 StreamingBufferSegment seg2;
2108 StreamingBufferSegment seg3;
2115 StreamingBufferSegment seg4;
2122 StreamingBufferSegment seg5;
2134 StreamingBufferSegment seg6;
2151 static int StreamingBufferTest07(
void)
2157 StreamingBufferSegment seg1;
2159 StreamingBufferSegment seg2;
2166 StreamingBufferSegment seg3;
2173 StreamingBufferSegment seg4;
2180 StreamingBufferSegment seg5;
2192 StreamingBufferSegment seg6;
2209 static int StreamingBufferTest08(
void)
2215 StreamingBufferSegment seg1;
2217 StreamingBufferSegment seg2;
2224 StreamingBufferSegment seg3;
2231 StreamingBufferSegment seg4;
2238 StreamingBufferSegment seg5;
2250 StreamingBufferSegment seg6;
2267 static int StreamingBufferTest09(
void)
2273 StreamingBufferSegment seg1;
2275 StreamingBufferSegment seg2;
2282 StreamingBufferSegment seg3;
2289 StreamingBufferSegment seg4;
2296 StreamingBufferSegment seg5;
2308 StreamingBufferSegment seg6;
2325 static int StreamingBufferTest10(
void)
2331 StreamingBufferSegment seg1;
2334 StreamingBufferSegment seg2;
2337 StreamingBufferSegment seg3;
2343 StreamingBufferSegment seg4;
2346 StreamingBufferSegment seg5;
2349 StreamingBufferSegment seg6;
2356 StreamingBufferSegment seg7;
2367 StreamingBufferSegment seg8;
2383 static int StreamingBufferTest11(
void)
2389 StreamingBufferSegment seg1;
2391 StreamingBufferSegment seg2;
2392 unsigned int data_len = 0xffffffff;
2395 sb, &cfg, &seg2, (
const uint8_t *)
"abcdefghij", data_len, 100000) !=
SC_ELIMIT);
2400 static const char *dummy_conf_string =
"%YAML 1.1\n"
2410 static int StreamingBufferTest12(
void)
2423 StreamingBufferSegment seg1;
2426 StreamingBufferSegment seg2;
2428 (
const uint8_t *)
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ",
2451 UtRegisterTest(
"StreamingBufferTest11 Bug 6903", StreamingBufferTest11);
2452 UtRegisterTest(
"StreamingBufferTest12 Bug 6782", StreamingBufferTest12);