Suricata

Adding additional context from further testing with flamegraphs -

1. Firewall-Mode Performance Regression — CPU Flame Graph Analysis

Date: 2026-10-02 Build under test: Suricata 8.0.6 Goal: Identify the CPU bottleneck behind the firewall-mode PPS regression first observed in an initial e2e experiment as described on this redmine, using local CPU flame-graph profiling of the same 8.0.6 build.

We found three compounding per-packet costs:

1. Broad-rule matching (no content ⇒ not Hyperscan-prefilterable, matched individually): firewall rules → `DetectRulePacketRules`/`DetectAddressMatchIPv4`; IPS rules → `IPOnlyMatchPacket`/`DetectPortLookupGroup`.
2. Per-packet alert-queue qsort gated on `EngineModeIsFirewall()` (`AlertQueueSortHelperFirewall`, `detect-engine-alert.c:638`) — fires in firewall mode even with 0 firewall rules.
3. Per-packet candidate-array sort `QuickSortSigIntId` (`detect-engine-prefilter.c:288`, O(n²)-prone fixed-pivot quicksort).

Evidence: four runs. FW + firewall rules (Run C, detect 87.6%); FW + 50k IPS rules (Run E, detect 69.9%); system mode, same 50k rules + same load (Run D, detect 2.9%). This matches gamma experiment 1 (FW + 50k IPS → 189k PPS vs system 3.2M) AND experiment 2 (FW + 0 rules → fast). Logging (~2%) and Hyperscan/MPM content scanning (~0%) are not the bottleneck.

1. Summary for the ticket

In firewall mode (`firewall.enabled: true`), two per-packet `qsort`/quicksort operations scale with the number of broad, non-fast-pattern rules that co-match a packet, and dominate CPU under rule-heavy policies. Measured sort inputs under load: alert queue median 4,419 / max 11,447 elements sorted per packet; prefilter candidate array up to ~2,105 elements sorted per packet. The same run in IPS (non-firewall) mode spends ~0% in these paths because grouping/prefilter keep the arrays tiny. Net effect in a representative test: ~3.2M PPS (IPS mode) → ~189k PPS (firewall mode) with the same rules.

1. Finding 1 — per-packet alert-queue sort gated on engine mode

`src/detect-engine-alert.c`, `PacketAlertFinalizeProcessQueue()` (~L635–643):

```c
const bool have_fw_rules = EngineModeIsFirewall();
if (det_ctx->alert_queue_size > 1) {
qsort(det_ctx->alert_queue, det_ctx->alert_queue_size, sizeof(PacketAlert),
have_fw_rules ? AlertQueueSortHelperFirewall : AlertQueueSortHelper);
}
```

- `have_fw_rules = EngineModeIsFirewall()` is true for the whole run in firewall mode, independent of whether any firewall rules matched this packet.
- With broad `alert`/`pass` rules (e.g. `alert ip any any > any any`), every match is appended to `alert_queue`, so the queue reaches thousands of entries, and `qsort` runs on it every packet (flame graph: `AlertQueueSortHelperFirewall` ~15% + libc `msort_with_tmp`/`qsort_r` ~9%).
`AlertQueueSortHelperFirewall` differs from the non-fw comparator only by adding a leading `detect_table` comparison; the dominant cost is the element count, not the comparator.

Fix options:

1. Skip/short-circuit the sort when the queue is already ordered, or when `alert_queue_size` is below a threshold.
2. Insert alerts in sorted position (the queue is appended then fully re-sorted; an insertion-ordered or bucketed append avoids the O(n log n) per-packet qsort).
3. Bound the per-packet alert queue for broad rules, or avoid enqueuing non-logging `pass`/`accept` matches that are only used for verdict (not for the alert log).
4. Re-evaluate whether broad IP/port-only `alert` rules need to flow through the per-packet alert queue at all in firewall mode.

1. Finding 2 — per-packet prefilter candidate-array quicksort

`src/detect-engine-prefilter.c`:

- `QuickSortSigIntId()` (L69–91): recursive, fixed middle pivot (`SigIntId p = sids[n/2]`). On this data the pivot halved cleanly (observed 524→262→131), i.e. O(n log n); but a fixed-middle pivot is O(n²) on sorted/reverse-sorted input, and prefilter sids are frequently near-sorted (assigned in rule order), so the worst case is reachable with other policies.
- Called per packet/tx at three sites (L286–289 `DetectRunPrefilterTx`, `PrefilterPostRuleMatch`, `Prefilter`) whenever `rule_id_array_cnt > 1`.
- Broad no-fast-pattern rules enter the candidate array via `PrefilterPktNonPF` / `PrefilterTxNonPF` (one `PrefilterAddSids` per matching rule), so the array grows to ~2,100 entries and is sorted every packet.

Key observation — the sort exists only to enable dedup. The sole consumer (`src/detect.c:343`, `DetectPrefilterCopyDeduplicate`-style loop) walks the sorted array skipping adjacent duplicates (`if (id != previous_id)`), i.e. the array is sorted purely so dedup is an O(n) adjacent-compare. That makes the sort replaceable:

Fix options:

1. Counting/bitmap dedup (eliminates the sort): `SigIntId` is bounded by the signature count. A per-thread bitset (or generation-stamped `uint32` array) sized to `DetectEngineGetMaxSigId()` lets both dedup and ordered emit happen in O(n + k) with no comparison sort. This removes `QuickSortSigIntId` from the per-packet path entirely and is the highest-leverage fix.
2. Radix sort on the bounded-width `SigIntId` key: O(n) and immune to the fixed-pivot worst case.
3. At minimum, harden the pivot (median-of-three or randomized) + switch to insertion sort for small `n`, to remove the O(n²) worst case — but this does not address the fundamental "sort thousands of elements per packet" cost.

1. Framing for the ticket

The deeper issue is that broad, non-fast-pattern rules bypass MPM prefiltering and become per-packet candidates, which then drive both sorts. Upstream may also want to consider port/CIDR-indexing broad firewall/IP-only rules so they are not linearly evaluated and enqueued per packet (`DetectRulePacketRules` 30–34%, `DetectAddressMatchIPv4` 14–18%, `IPOnlyMatchPacket` 21% in the IPS-rule case). The two sort fixes above are the most self-contained, high-impact changes; the indexing change is larger but attacks the root (candidate/alert volume).

I see the PR is in review - do we think we will be able to get the change merged in the next couple days?