Subject: [REGRESSION] selinux: ~90% throughput drop in System V IPC (msg) since commit 7edea6e8c8e8

[Stephen Smalley]

On Mon, Aug 3, 2026 at 8:17 PM Jiri Vozar <jvozar at redhat.com> wrote:
>
> Hi,
>
> Commit 7edea6e8c8e8 ("selinux: beef up isvalid checks") introduces a new
> loop in mls_level_isvalid() that causes ~89-94% throughput regression in
> System V IPC message queue operations (msgsnd/msgrcv).
>
> The regression affects all architectures (x86_64, aarch64, ppc64le) and
> is independent of SELinux enforcement mode (enforcing vs permissive).
>
> Upstream commit:
> https://github.com/torvalds/linux/commit/7edea6e8c8e8944e060da6b0b81d66db8d5fffcc
> Merge commit:    https://github.com/torvalds/linux/commit/231e9d447ea9
> (selinux-pr-20260615)
> First affected:  v7.2-rc1
>
> ## Regression data
>
> Measured with stress-ng msg stressor across multiple machines and
> architectures. The percentage is throughput change vs a v6.12 baseline:
>
>   NUMA config | Max drop | Avg drop | Hosts affected
>   ------------|----------|----------|-------------------
>   1 NUMA      |  -94%    |  -91.5%  | aarch64 5/5, ppc64le 3/3, x86_64 6/21
>   2 NUMA      |  -94%    |  -92%    | x86_64 5 hosts
>   4 NUMA      |  -94%    |  -90%    | x86_64 4 hosts
>   8 NUMA      |  -89%    |  -89%    | x86_64 1 host
>
> Architecture-independent — confirms the regression is in the kernel code
> path, not hardware-specific.
>
> ## Root cause
>
> The new loop in security/selinux/ss/mls.c mls_level_isvalid():
>
>     ebitmap_for_each_positive_bit(&levdatum->level.cat, node, bit) {
>         if (!sym_name(p, SYM_CATS, bit))
>             return false;
>     }
>
> iterates over every set bit in the category bitmap (~1024 bits in
> standard MCS policy with c0.c1023 range). Each iteration calls
> _find_next_bit() + sym_name() (array dereference into
> p->sym_val_to_name[SYM_CATS]).
>
> The function is called on every IPC operation via:
>
>     msgsnd() -> security_msg_msg_alloc() -> selinux_msg_msg_alloc_security()
>       -> security_context_to_sid_core() -> mls_context_isvalid()
>         -> mls_range_isvalid() -> mls_level_isvalid() (x2 per range)
>
> This adds ~2048 iterations of bitmap scanning + array lookups per IPC
> operation. SELinux permissive mode does not help (~0.6% difference)
> because the overhead is in the validation path, not the enforcement
> decision.
>
> ## Perf profile evidence
>
> Single-threaded stress-ng --msg 1 -t 60 on x86_64:
>   - Baseline (v6.12): ~67,000 msg ops/sec
>   - Regressed (v7.2-rc4): ~7,400 msg ops/sec (-89%)
>
> perf top on the regressed kernel shows _find_next_bit and sym_name
> dominating kernel CPU time during the msg workload.
>
> ## How to reproduce
>
> On any machine with kernel >= v7.2 and SELinux enabled:
>
>     # Install stress-ng
>     dnf install -y stress-ng
>
>     # Run the msg stressor
>     stress-ng --msg 1 -t 60 --metrics-brief
>
>     # Compare with SELinux disabled (requires reboot with selinux=0):
>     stress-ng --msg 1 -t 60 --metrics-brief
>
> Expected: ~67,000 bogo-ops/sec (as on v6.12)
> Actual:   ~7,400 bogo-ops/sec (on v7.2) — approximately 89% drop
>
> The regression affects any workload that uses System V IPC message queues
> at high frequency. Other IPC stressors (sem, shm) may also be affected
> to a lesser degree.
>
> ## Suggested fix
>
> The ebitmap_for_each_positive_bit loop validates that every category bit
> has a corresponding name in the policy symbol table. This is a property
> of the policy itself and does not change at runtime. The validation
> should be moved to policy load time in
> security/selinux/ss/policydb_validate.c (e.g. in validate_level()) and
> removed from the hot path in mls_level_isvalid().

Thanks for the report, should be fixed by:
https://lore.kernel.org/selinux/20260804135700.3713-1-stephen.smalley.work@gmail.com/