linux-kernel - Re: [PATCH] selinux: Make avc cache slot size configurable during boot

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAEjxPJ5JFqSMGSg5KEYd40JhLkgUo6g0uykDkXdKW3q5F1JtjQ@mail.gmail.com>
Date: Fri, 19 Sep 2025 10:33:21 -0400
From: Stephen Smalley <stephen.smalley.work@...il.com>
To: Hongru Zhang <zhanghongru06@...il.com>
Cc: linux-kernel@...r.kernel.org, omosnace@...hat.com, paul@...l-moore.com, 
	selinux@...r.kernel.org, zhanghongru@...omi.com
Subject: Re: [PATCH] selinux: Make avc cache slot size configurable during boot

On Fri, Sep 19, 2025 at 9:58 AM Hongru Zhang <zhanghongru06@...il.com> wrote:
>
> > > Baseline: 512 nodes, 512 buckets, original avc_hash
> > > A: 512 nodes, 512 buckets
> > > B: 8192 nodes, 8192 buckets
> > > C: 8192 nodes, 8192 buckets, original avc_hash
> > > D: 8192 nodes, 4096 buckets ("large number" of nodes in limited buckets)
> > >
> > > 1. /sys/fs/selinux/avc/hash_stats
> > >         a. assess the effectiveness of the optimized algorithm based on A, B
> > >                 and Baseline. Expect bucket utilization rate: A ~= B > Baseline.
> > > 2. total latency of hash operation and table lookup
> > >         a. A vs Baseline: expect A is no obvious latency increasing
> > >         b. B vs A: expect B is close to A
> > >         c. C vs B: expect B is no worse than C
> > >         c. D vs C: see if we can save some memory with no obvious latency increasing
> >
> > Thank you, looking forward to the results. Fun fact: the current
> > avc_hash() function logic hasn't been changed since SELinux was first
> > merged into Linux 2.6.0-test3.
>
> Yes, I also noticed that. I tried MurmurHash3 and another algorithm (refered to as Muladd below),
> it seems performance of Muladd > MurmurHash3 > current algorithm. How
> about using Muladd?
>
> Implementation of Muladd:
> static inline u32 avc_hash(u32 ssid, u32 tsid, u16 tclass)
> {
>         return (ssid * 0x9E3779B9 + tsid * 0x85EBCA77 + tclass * 0xC2B2AE35) & (avc_cache_slots - 1);
> }

Can you cite the source of this hash function? Is it public domain or
otherwise GPLv2-compatible?

>
> Note: all test results are based on patch "selinux: Make avc cache slot size configurable during boot"
>
> Here are the results:
> 1. Bucket utilization rate and length of longest chain
> +--------------------------+-----------------------------------------+
> |                          | Bucket utilization rate / longest chain |
> |                          +------------+---------------+------------+
> |                          |  original  |  MurmurHash3  |   Muladd   |
> +--------------------------+------------+---------------+------------+
> |  512 nodes,  512 buckets | 52.5%/7.5  |   60.2%/5.7 * | 58.2%/6.2 *|
> +--------------------------+------------+---------------+------------+
> | 1024 nodes,  512 buckets | 68.9%/12.1 |   80.2%/9.7   | 82.4%/8.9  |
> +--------------------------+------------+---------------+------------+
> | 2048 nodes,  512 buckets | 83.7%/19.4 |   93.4%/16.3  | 94.8%/15.2 |
> +--------------------------+------------+---------------+------------+
> | 8192 nodes, 8192 buckets | 49.5%/11.4 |   60.3%/7.4   | 61.9%/6.6  |
> +--------------------------+------------+---------------+------------+
>
> 2. avc_search_node latency (total latency of hash operation and table lookup)
> +--------------------------+-----------------------------------------+
> |                          |   latency of function avc_search_node   |
> |                          +------------+---------------+------------+
> |                          |  original  |  MurmurHash3  |   Muladd   |
> +--------------------------+------------+---------------+------------+
> |  512 nodes,  512 buckets |    87ns    |      84ns *   |    79ns *  |
> +--------------------------+------------+---------------+------------+
> | 1024 nodes,  512 buckets |    97ns    |      96ns     |    91ns    |
> +--------------------------+------------+---------------+------------+
> | 2048 nodes,  512 buckets |   118ns    |     113ns     |   110ns    |
> +--------------------------+------------+---------------+------------+
> | 8192 nodes, 8192 buckets |   106ns    |      99ns     |    94ns    |
> +--------------------------+------------+---------------+------------+
>
> The values in the starred cells could be because MurmurHash3 has greater
> overhead than Muladd.
>
> Details:
> url: https://gist.github.com/zhr250/198717da076a808b5cc78762f27be77e