linux-kernel - Re: [PATCH v4 3/3] selinux: improve bucket distribution uniformity of avc

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <5fa2cff3acf5ae62cb76f157fb36b7a8@paul-moore.com>
Date: Thu, 23 Oct 2025 18:24:27 -0400
From: Paul Moore <paul@...l-moore.com>
To: Hongru Zhang <zhanghongru06@...il.com>, stephen.smalley.work@...il.com, omosnace@...hat.com
Cc: linux-kernel@...r.kernel.org, selinux@...r.kernel.org, zhanghongru@...omi.com
Subject: Re: [PATCH v4 3/3] selinux: improve bucket distribution uniformity of  avc_hash()

On Oct 23, 2025 Hongru Zhang <zhanghongru06@...il.com> wrote:
> 
> Reuse the already implemented MurmurHash3 algorithm. Under heavy stress
> testing (on an 8-core system sustaining over 50,000 authentication events
> per second), sample once per second and take the mean of 1800 samples:
> 
> 1. Bucket utilization rate and length of longest chain
> +--------------------------+-----------------------------------------+
> |                          | bucket utilization rate / longest chain |
> |                          +--------------------+--------------------+
> |                          |      no-patch      |     with-patch     |
> +--------------------------+--------------------+--------------------+
> |  512 nodes,  512 buckets |      52.5%/7.5     |     60.2%/5.7      |
> +--------------------------+--------------------+--------------------+
> | 1024 nodes,  512 buckets |      68.9%/12.1    |     80.2%/9.7      |
> +--------------------------+--------------------+--------------------+
> | 2048 nodes,  512 buckets |      83.7%/19.4    |     93.4%/16.3     |
> +--------------------------+--------------------+--------------------+
> | 8192 nodes, 8192 buckets |      49.5%/11.4    |     60.3%/7.4      |
> +--------------------------+--------------------+--------------------+
> 
> 2. avc_search_node latency (total latency of hash operation and table
> lookup)
> +--------------------------+-----------------------------------------+
> |                          |   latency of function avc_search_node   |
> |                          +--------------------+--------------------+
> |                          |      no-patch      |     with-patch     |
> +--------------------------+--------------------+--------------------+
> |  512 nodes,  512 buckets |        87ns        |        84ns        |
> +--------------------------+--------------------+--------------------+
> | 1024 nodes,  512 buckets |        97ns        |        96ns        |
> +--------------------------+--------------------+--------------------+
> | 2048 nodes,  512 buckets |       118ns        |       113ns        |
> +--------------------------+--------------------+--------------------+
> | 8192 nodes, 8192 buckets |       106ns        |        99ns        |
> +--------------------------+--------------------+--------------------+
> 
> Although MurmurHash3 has higher overhead than the bitwise operations in
> the original algorithm, the data shows that the MurmurHash3 achieves
> better distribution, reducing average lookup time. Consequently, the
> total latency of hashing and table lookup is lower than before.
> 
> Signed-off-by: Hongru Zhang <zhanghongru@...omi.com>
> ---
>  security/selinux/avc.c          |  3 ++-
>  security/selinux/include/hash.h | 11 ++++++-----
>  security/selinux/ss/avtab.c     |  6 ++++++
>  3 files changed, 14 insertions(+), 6 deletions(-)

Merged into selinux/dev, thanks!

--
paul-moore.com