Suricata

https://github.com/OISF/suricata/pull/15857

Thanks for the detailed analysis. The underflow is real, but I want to clarify why the - 1 is intentional, because the reasoning hinges on a detail of our comparator that isn't obvious.

Why frag_offset - 1: our comparator never returns 0.

The argument that RB_NFIND does an inclusive (>=) search is only true for a comparator that returns 0 on equality. DefragRbFragCompare doesn't:

```
int DefragRbFragCompare(struct Frag_ *a, struct Frag_ *b) {
if (a->offset < b->offset) {
return -1;
}
return 1; // equal offsets return 1, never 0
}
```

RB_NFIND only follows the left branch (recording a candidate) when cmp(key, node) < 0, and returns early only on cmp == 0, which is unreachable here. So in practice RB_NFIND returns the first node with offset strictly greater than key.offset, not >=.

That changes the meaning of the search key:

1. key.offset = frag_offset → first node with offset > frag_offset → skips a fragment already sitting at exactly frag_offset.
2. key.offset = frag_offset - 1 → first node with offset >= frag_offset → includes a same-offset fragment as next.

So the - 1 isn't trying to locate "the fragment right before" — it compensates for the strictly-greater NFIND so that an existing fragment at the same offset is still found. Removing it (or picking frag_offset - 8 on the multiples-of-8 assumption) would change overlap handling for duplicate-offset fragments. This is also why the exact value matters as 1, not the fragment stride.

The underflow itself is benign, though real.

It's reached when a first fragment (frag_offset 0) arrives out of order into an already-non-empty tree. frag_offset - 1 promotes to int -1 and narrows to uint16_t 65535. Tracing it:

1. key.offset = 65535 → no node has offset > 65535 → next NULL
2. the next == NULL branch runs: prev = RB_MIN(...), then iterate forward

For an offset-0 fragment this is correct — it can overlap any earlier fragment, so scanning from RB_MIN is exactly what's needed. So the "extra code to find the first neighbor" you observed is doing the right work; it's not picking the wrong fragments, and the O(n) scan is inherent to an offset-0 fragment rather than an artifact of the underflow.

Proposed fix.

Even though it's functionally harmless, the wrap-around trips -fsanitize=implicit-conversion, so it's worth making explicit without changing behavior

```
Frag key = {
.offset = frag_offset ? frag_offset - 1 : 0,
};
```

For frag_offset == 0, key.offset = 0 makes RB_NFIND return the first node with offset > 0, and prev resolves back to RB_MIN in every case. So the loop starts on the same fragment the wrap path reached. Same iteration order, no 65535 detour, no sanitizer trip.

Happy to add a unit test that inserts an offset-0 fragment after higher-offset ones to lock this path down.

Samaresh Kumar singh wrote in #note-4:

Thanks for the detailed analysis. The underflow is real, but I want to clarify why the - 1 is intentional, because the reasoning hinges on a detail of our comparator that isn't obvious.

Why frag_offset - 1: our comparator never returns 0.

The argument that RB_NFIND does an inclusive (>=) search is only true for a comparator that returns 0 on equality. DefragRbFragCompare doesn't:

```
int DefragRbFragCompare(struct Frag_ *a, struct Frag_ *b) {
if (a->offset < b->offset) {
return -1;
}
return 1; // equal offsets return 1, never 0
}
```

Now that's makes sense! Thanks! It's seems like I overlooked this detail.

Proposed fix.

Even though it's functionally harmless, the wrap-around trips -fsanitize=implicit-conversion, so it's worth making explicit without changing behavior

```
Frag key = {
.offset = frag_offset ? frag_offset - 1 : 0,
};
```

Maybe add some comment describing why offset must be decreased?

For an offset-0 fragment this is correct — it can overlap any earlier fragment, so scanning from RB_MIN is exactly what's needed. So the "extra code to find the first neighbor" you observed is doing the right work; it's not picking the wrong fragments, and the O(n) scan is inherent to an offset-0 fragment rather than an artifact of the underflow.

I'm concerned about different scenario:

        Frag key = {
            .offset = frag_offset - 1,
        };
        next = RB_NFIND(IP_FRAGMENTS, &tracker->fragment_tree, &key);
        if (next == NULL) {
            prev = RB_MIN(IP_FRAGMENTS, &tracker->fragment_tree);
            next = IP_FRAGMENTS_RB_NEXT(prev);
        } else {
            prev = IP_FRAGMENTS_RB_PREV(next);
            if (prev == NULL) {
                prev = next;
                next = IP_FRAGMENTS_RB_NEXT(prev);
            }
        }

When a fragment arrives after all existing fragments, RB_NFIND() returns NULL, but the code treats it as if the fragment should be searched from the beginning of the tree. This may cause unnecessary traversal of all fragments instead of directly identifying the last fragment as prev. In worst case scenario the whole defragmentation process is O(n^2). So shouldn't be this handled through IP_FRAGMENTS_RB_PREV with reverse traversal?