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);
670 if (sbb->
len >= shrink_by) {
671 sbb->
len -= shrink_by;
698 static inline uint32_t ToNextMultipleOf(
const uint32_t in,
const uint32_t
m)
702 const uint32_t x = in %
m;
710 static thread_local
bool g2s_warn_once =
false;
717 if (!g2s_warn_once) {
718 SCLogWarning(
"StreamingBuffer::GrowRegionToSize() tried to alloc %u bytes, exceeds "
721 g2s_warn_once =
true;
727 const uint32_t grow = ToNextMultipleOf(size, cfg->
buf_size);
729 if (grow <= region->buf_size) {
742 size_t diff = grow - region->
buf_size;
743 void *new_mem = ((
char *)ptr) + region->
buf_size;
744 memset(new_mem, 0, diff);
750 if (region->
buf_size > sb->buf_size_max) {
751 sb->buf_size_max = region->
buf_size;
760 return GrowRegionToSize(sb, cfg, &sb->
region, size);
800 static inline void StreamingBufferSlideToOffsetWithRegions(
806 SCLogDebug(
"slide_offset %" PRIu64, slide_offset);
811 const bool main_is_oow = RegionBeforeOffset(&sb->
region, slide_offset);
832 if (RegionBeforeOffset(r, slide_offset)) {
839 FREE(cfg, r,
sizeof(*r));
842 }
else if (RegionContainsOffset(r, slide_offset)) {
861 if (to_shift && to_shift != &sb->
region) {
873 FREE(cfg, to_shift,
sizeof(*to_shift));
881 SCLogDebug(
"shift start region %p", to_shift);
889 const uint32_t s = (uint32_t)(slide_offset - to_shift->
stream_offset);
891 const uint32_t new_data_size = to_shift->
buf_size - s;
892 uint32_t new_mem_size = ToNextMultipleOf(new_data_size, cfg->
buf_size);
903 const uint64_t next_re =
next->stream_offset +
next->buf_size;
905 const uint32_t mem_size =
906 ToNextMultipleOf((uint32_t)(next_re - slide_offset), cfg->
buf_size);
910 SCLogDebug(
"replace main with the next bigger region");
913 const uint32_t next_data_offset =
914 (uint32_t)(
next->stream_offset - slide_offset);
915 const uint32_t prev_buf_size =
next->buf_size;
917 const uint32_t start_data_offset =
920 if (start_data_offset > start->
buf_size) {
921 new_mem_size = new_data_size;
925 if (GrowRegionToSize(sb, cfg,
next, mem_size) != 0) {
926 new_mem_size = new_data_size;
935 memmove(
next->buf + next_data_offset,
next->buf, prev_buf_size);
942 const uint32_t start_data_size = start->
buf_size - start_data_offset;
943 memcpy(
next->buf, start->
buf + start_data_offset, start_data_size);
964 if (GrowRegionToSize(sb, cfg, start, mem_size) != 0) {
965 new_mem_size = new_data_size;
969 SCLogDebug(
"start->buf now size %u", mem_size);
974 SCLogDebug(
"s %u new_data_size %u", s, new_data_size);
975 memmove(start->
buf, start->
buf + s, new_data_size);
981 SCLogDebug(
"copy next->buf %p/%u to start->buf offset %u",
next->buf,
982 next->buf_size, new_data_size);
983 memcpy(start->
buf + new_data_size,
next->buf,
next->buf_size);
998 SCLogDebug(
"s %u new_data_size %u", s, new_data_size);
999 memmove(to_shift->
buf, to_shift->
buf + s, new_data_size);
1003 to_shift->
buf = ptr;
1007 if (s < to_shift->buf_offset)
1035 StreamingBufferSlideToOffsetWithRegions(sb, cfg,
offset);
1054 if (sb->
head != NULL) {
1058 SCLogDebug(
"sliding %u forward, size of original buffer left after slide %u", slide,
1074 SCLogDebug(
"sliding %u forward, size of original buffer left after slide %u", slide,
1096 uint64_t len64 =
len;
1097 if (len64 + buf_offset64 > UINT32_MAX) {
1104 StreamingBufferSegment *seg,
const uint8_t *data, uint32_t data_len)
1110 if (InitBuffer(sb, cfg) == -1)
1114 int r = DataFits(sb, data_len);
1118 }
else if (r == 0) {
1120 if (GrowToSize(sb, cfg, data_len) !=
SC_OK)
1128 if (DataFits(sb, data_len) != 1)
1133 seg->segment_len = data_len;
1138 return SBBUpdate(sb, cfg, &sb->
region, rel_offset, data_len);
1148 const uint8_t *data, uint32_t data_len)
1153 if (InitBuffer(sb, cfg) == -1)
1157 int r = DataFits(sb, data_len);
1161 }
else if (r == 0) {
1163 if (GrowToSize(sb, cfg, data_len) !=
SC_OK)
1177 return SBBUpdate(sb, cfg, &sb->
region, rel_offset, data_len);
1183 static int DataFitsAtOffset(
1186 const uint64_t offset64 =
offset;
1187 const uint64_t len64 =
len;
1188 if (offset64 + len64 > UINT32_MAX)
1190 return (
offset + len <= region->buf_size);
1193 #if defined(DEBUG) || defined(DEBUG_VALIDATION)
1226 #if defined(DEBUG) && DUMP_REGIONS == 1
1232 snprintf(gap,
sizeof(gap),
"[ gap:%" PRIu64
" ]",
1236 printf(
"[ %s offset:%" PRIu64
" size:%u offset:%u ]%s", r == &sb->
region ?
"main" :
"aux",
1240 bool at_least_one =
false;
1245 if (last_re != sbb->
offset) {
1246 printf(
"[ gap:%" PRIu64
" ]", sbb->
offset - last_re);
1248 printf(
"[ sbb offset:%" PRIu64
" len:%u ]", sbb->
offset, sbb->
len);
1249 at_least_one =
true;
1255 #if defined(DEBUG) || defined(DEBUG_VALIDATION)
1259 const uint8_t *_data = NULL;
1260 uint32_t _data_len = 0;
1275 uint32_t dst_buf_size)
1279 const uint64_t data_re = data_offset + data_len;
1280 SCLogDebug(
"sb %p dst %p src_start %p src_end %p data_offset %" PRIu64
1281 "/data_len %u/data_re %" PRIu64,
1282 sb,
dst, src_start, src_end, data_offset, data_len, data_re);
1288 const uint32_t dst_size = dst_buf_size;
1292 const uint32_t old_size =
dst->buf_size;
1294 const uint32_t dst_copy_offset = (uint32_t)(
dst->stream_offset - dst_offset);
1296 const uint32_t old_offset =
dst->buf_offset;
1297 SCLogDebug(
"old_size %u, old_offset %u, dst_copy_offset %u", old_size, old_offset,
1300 if ((retval = GrowRegionToSize(sb, cfg,
dst, dst_size)) !=
SC_OK) {
1307 if (dst_copy_offset != 0)
1308 memmove(
dst->buf + dst_copy_offset,
dst->buf, old_size);
1309 if (dst_offset !=
dst->stream_offset) {
1310 dst->stream_offset = dst_offset;
1312 dst->buf_offset = 0;
1317 new_offset += data_len;
1320 bool start_is_main =
false;
1321 if (src_start == &sb->
region) {
1324 start_is_main =
true;
1326 if (src_start !=
dst)
1328 if (src_start == src_end) {
1329 SCLogDebug(
"src_start == src_end == main, we're done");
1334 src_start = src_start->
next;
1344 SCLogDebug(
"skipping r %p as it is 'dst'", r);
1352 const uint32_t target_offset = (uint32_t)(r->
stream_offset - dst_offset);
1353 SCLogDebug(
"r %p: target_offset %u", r, target_offset);
1360 FREE(cfg, r,
sizeof(*r));
1380 if (start_is_main &&
dst != &sb->
region) {
1382 SCLogDebug(
"start_is_main && dst != main region");
1397 SCLogDebug(
"returning dst %p stream_offset %" PRIu64
" buf_offset %u buf_size %u",
dst,
1398 dst->stream_offset,
dst->buf_offset,
dst->buf_size);
1411 const uint64_t insert_re =
offset +
len;
1413 uint64_t insert_adjusted_re = insert_re;
1432 uint32_t new_buf_size = ToNextMultipleOf(
1433 (uint32_t)(insert_adjusted_re - insert_start_offset), cfg->
buf_size);
1443 new_buf_size = ToNextMultipleOf(
1444 (uint32_t)(insert_adjusted_re - insert_start_offset), cfg->
buf_size);
1451 sb, cfg, big, start, end,
offset,
len, start_prev, new_buf_size);
1464 SCLogDebug(
"no matching region found, append to %p (%s)", append,
1465 append == &sb->
region ?
"main" :
"aux");
1490 SCLogDebug(
"data_offset %" PRIu64
", data_len %u, re %" PRIu64, data_offset, data_len,
1491 data_offset + data_len);
1494 if (RegionsIntersect(cfg, &sb->
region, data_offset, data_offset + data_len)) {
1495 SCLogDebug(
"data_offset %" PRIu64
", data_len %u intersects with main region (next %p)",
1498 !RegionsIntersect(cfg, sb->
region.
next, data_offset, data_offset + data_len)) {
1500 "data_offset %" PRIu64
1501 ", data_len %u intersects with main region, no next or way before next region",
1502 data_offset, data_len);
1505 if ((r = InitBuffer(sb, cfg)) !=
SC_OK) {
1519 SCLogDebug(
"created new region %p with offset %" PRIu64
", size %u", aux_r,
1536 StreamingBufferSegment *seg,
const uint8_t *data, uint32_t data_len, uint64_t
offset)
1546 if (region == NULL) {
1550 const bool region_is_main = region == &sb->
region;
1552 SCLogDebug(
"inserting %" PRIu64
"/%u using %s region %p",
offset, data_len,
1553 region == &sb->
region ?
"main" :
"aux", region);
1557 int r = DataFitsAtOffset(region, data_len, rel_offset);
1561 }
else if (r == 0) {
1562 if ((r = GrowToSize(sb, cfg, (rel_offset + data_len))) !=
SC_OK)
1567 SCLogDebug(
"offset %" PRIu64
" data_len %u, rel_offset %u into region offset %" PRIu64
1568 ", buf_offset %u, buf_size %u",
1571 memcpy(region->
buf + rel_offset, data, data_len);
1572 seg->stream_offset =
offset;
1573 seg->segment_len = data_len;
1575 SCLogDebug(
"rel_offset %u region->stream_offset %" PRIu64
", buf_offset %u", rel_offset,
1581 if (region_is_main) {
1583 SCLogDebug(
"empty sbb list: block exactly what was expected, fall through");
1589 SCLogDebug(
"empty sbb list: block is within existing main data region");
1596 }
else if (rel_offset < sb->region.
buf_offset) {
1599 SCLogDebug(
"before expected offset: %u < sb->region.buf_offset %u", rel_offset,
1602 SCLogDebug(
"before expected offset, ends after: %u < sb->region.buf_offset "
1610 SCLogDebug(
"beyond expected offset: SBBInit");
1612 if ((r = SBBInit(sb, cfg, region, rel_offset, data_len)) !=
SC_OK)
1616 SCLogDebug(
"empty sbb list: invoking SBBInitLeadingGap");
1617 if ((r = SBBInitLeadingGap(sb, cfg,
offset, data_len)) !=
SC_OK)
1624 SCLogDebug(
"empty sbb list, no data in main: use SBBInit");
1625 if ((r = SBBInit(sb, cfg, region, rel_offset, data_len)) !=
SC_OK)
1629 SCLogDebug(
"empty sbb list: invoking SBBInitLeadingGap");
1630 if ((r = SBBInitLeadingGap(sb, cfg,
offset, data_len)) !=
SC_OK)
1642 if ((r = SBBUpdate(sb, cfg, region, rel_offset, data_len)) !=
SC_OK)
1656 const StreamingBufferSegment *seg)
1679 if (
offset >= r->stream_offset &&
offset < (r->stream_offset + r->buf_size)) {
1689 const uint8_t **data, uint32_t *data_len)
1692 SCLogDebug(
"first find our region (offset %" PRIu64
") -> %p", sbb->
offset, region);
1705 *data_len = sbb->
len;
1710 if (offset < sbb->
len) {
1711 *data = region->
buf;
1725 const uint8_t **data, uint32_t *data_len,
1743 *data = region->
buf + data_offset;
1744 if (data_offset + sbblen > region->
buf_size) {
1745 *data_len = region->
buf_size - data_offset;
1753 if (data_offset < sbblen) {
1754 *data = region->
buf;
1755 *data_len = sbblen - data_offset;
1767 const StreamingBufferSegment *seg,
1768 const uint8_t **data, uint32_t *data_len)
1778 *data_len = seg->segment_len;
1785 *data = region->
buf;
1786 *data_len = seg->segment_len -
offset;
1801 const StreamingBufferSegment *seg,
1802 const uint8_t *rawdata, uint32_t rawdata_len)
1804 const uint8_t *segdata = NULL;
1805 uint32_t segdata_len = 0;
1807 if (segdata && segdata_len &&
1808 segdata_len == rawdata_len &&
1809 memcmp(segdata, rawdata, segdata_len) == 0)
1817 const uint8_t **data, uint32_t *data_len,
1820 if (sb != NULL && sb->
region.
buf != NULL) {
1834 const uint8_t **data, uint32_t *data_len,
1842 *data = region->
buf + skip;
1857 const uint8_t *rawdata, uint32_t rawdata_len)
1859 const uint8_t *sbdata = NULL;
1860 uint32_t sbdata_len = 0;
1864 sbdata && sbdata_len &&
1865 sbdata_len == rawdata_len &&
1866 memcmp(sbdata, rawdata, sbdata_len) == 0)
1873 printf(
"wanted:\n");
1884 static void DumpSegment(
StreamingBuffer *sb, StreamingBufferSegment *seg)
1886 const uint8_t *data = NULL;
1887 uint32_t data_len = 0;
1889 if (data && data_len) {
1894 static int StreamingBufferTest02(
void)
1900 StreamingBufferSegment seg1;
1902 StreamingBufferSegment seg2;
1906 FAIL_IF(seg1.stream_offset != 0);
1907 FAIL_IF(seg2.stream_offset != 8);
1911 DumpSegment(sb, &seg1);
1912 DumpSegment(sb, &seg2);
1920 StreamingBufferSegment seg3;
1924 FAIL_IF(seg3.stream_offset != 16);
1929 DumpSegment(sb, &seg1);
1930 DumpSegment(sb, &seg2);
1931 DumpSegment(sb, &seg3);
1940 DumpSegment(sb, &seg1);
1941 DumpSegment(sb, &seg2);
1942 DumpSegment(sb, &seg3);
1950 static int StreamingBufferTest03(
void)
1956 StreamingBufferSegment seg1;
1958 StreamingBufferSegment seg2;
1962 FAIL_IF(seg1.stream_offset != 0);
1963 FAIL_IF(seg2.stream_offset != 14);
1967 DumpSegment(sb, &seg1);
1968 DumpSegment(sb, &seg2);
1973 StreamingBufferSegment seg3;
1977 FAIL_IF(seg3.stream_offset != 8);
1982 DumpSegment(sb, &seg1);
1983 DumpSegment(sb, &seg2);
1984 DumpSegment(sb, &seg3);
1994 DumpSegment(sb, &seg1);
1995 DumpSegment(sb, &seg2);
1996 DumpSegment(sb, &seg3);
2005 static int StreamingBufferTest04(
void)
2011 StreamingBufferSegment seg1;
2014 StreamingBufferSegment seg2;
2018 FAIL_IF(seg1.stream_offset != 0);
2019 FAIL_IF(seg2.stream_offset != 14);
2034 DumpSegment(sb, &seg1);
2035 DumpSegment(sb, &seg2);
2038 StreamingBufferSegment seg3;
2042 FAIL_IF(seg3.stream_offset != 8);
2053 DumpSegment(sb, &seg1);
2054 DumpSegment(sb, &seg2);
2055 DumpSegment(sb, &seg3);
2061 StreamingBufferSegment seg4;
2066 FAIL_IF(seg4.stream_offset != 124);
2078 DumpSegment(sb, &seg1);
2079 DumpSegment(sb, &seg2);
2080 DumpSegment(sb, &seg3);
2081 DumpSegment(sb, &seg4);
2096 static int StreamingBufferTest06(
void)
2102 StreamingBufferSegment seg1;
2104 StreamingBufferSegment seg2;
2111 StreamingBufferSegment seg3;
2118 StreamingBufferSegment seg4;
2125 StreamingBufferSegment seg5;
2137 StreamingBufferSegment seg6;
2154 static int StreamingBufferTest07(
void)
2160 StreamingBufferSegment seg1;
2162 StreamingBufferSegment seg2;
2169 StreamingBufferSegment seg3;
2176 StreamingBufferSegment seg4;
2183 StreamingBufferSegment seg5;
2195 StreamingBufferSegment seg6;
2212 static int StreamingBufferTest08(
void)
2218 StreamingBufferSegment seg1;
2220 StreamingBufferSegment seg2;
2227 StreamingBufferSegment seg3;
2234 StreamingBufferSegment seg4;
2241 StreamingBufferSegment seg5;
2253 StreamingBufferSegment seg6;
2270 static int StreamingBufferTest09(
void)
2276 StreamingBufferSegment seg1;
2278 StreamingBufferSegment seg2;
2285 StreamingBufferSegment seg3;
2292 StreamingBufferSegment seg4;
2299 StreamingBufferSegment seg5;
2311 StreamingBufferSegment seg6;
2328 static int StreamingBufferTest10(
void)
2334 StreamingBufferSegment seg1;
2337 StreamingBufferSegment seg2;
2340 StreamingBufferSegment seg3;
2346 StreamingBufferSegment seg4;
2349 StreamingBufferSegment seg5;
2352 StreamingBufferSegment seg6;
2359 StreamingBufferSegment seg7;
2370 StreamingBufferSegment seg8;
2386 static int StreamingBufferTest11(
void)
2392 StreamingBufferSegment seg1;
2394 StreamingBufferSegment seg2;
2395 unsigned int data_len = 0xffffffff;
2398 sb, &cfg, &seg2, (
const uint8_t *)
"abcdefghij", data_len, 100000) !=
SC_ELIMIT);
2403 static const char *dummy_conf_string =
"%YAML 1.1\n"
2413 static int StreamingBufferTest12(
void)
2426 StreamingBufferSegment seg1;
2429 StreamingBufferSegment seg2;
2431 (
const uint8_t *)
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ",
2454 UtRegisterTest(
"StreamingBufferTest11 Bug 6903", StreamingBufferTest11);
2455 UtRegisterTest(
"StreamingBufferTest12 Bug 6782", StreamingBufferTest12);