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 for Android: free password hash cracker in your pocket

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

Message-ID: <CAEjxPJ6upN5e7XD9HC970pKvHox-qPjZLdzm=bV-tu8GgFrYoA@mail.gmail.com>
Date: Thu, 11 Sep 2025 09:23: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 Thu, Sep 11, 2025 at 9:07 AM Hongru Zhang <zhanghongru06@...il.com> wrote:
>
> > >  static inline u32 avc_hash(u32 ssid, u32 tsid, u16 tclass)
> > >  {
> > > -       return (ssid ^ (tsid<<2) ^ (tclass<<4)) & (AVC_CACHE_SLOTS - 1);
> > > +       return (ssid ^ (tsid<<2) ^ (tclass<<4)) & (avc_cache_slots - 1);
> >
> > If you are making the number of buckets adjustable, you should also
> > change the hash function to better deal with multiple numbers of
>
> Thank you for the advice. When running the test model, I sampled
> /sys/fs/selinux/avc/hash_stats once per second for a total of 1800 times
> and analyzed the distribution uniformity of the hash algorithm using the
> sampled data.
>
> Baseline: 512 nodes, 512 buckets
> Comparison: 8192 nodes, 8192 buckets
>
> Metrics (Average value over 1800 samples):
> * Bucket utilization rate (higher -> better, same chain length assumed)
>         * Baseline: 52.5%
>         * Comparison: 49.5%
> * Max chain length (lower -> better, positive correlation with worst-case latency)
>         * Baseline: 7.5
>         * Comparison: 11.4
>
> Experimental results show that scaling buckets and nodes from 512 to 8192:
> 1. The distribution uniformity under the current hash algorithm does not
> degrade significantly;
> 2. The maximum chain length rise significantly, potentially degrading
> worst-case performance (ignoring other code in avc_search_node function).
>
> Details:
> url: https://gist.github.com/zhr250/cb7ebca61ff5455098082677d75b1795
>
> I will modify the hash algorithm in the avc_hash function and collect data
> again to see if we can achieve performance improvements.

If you look elsewhere in the SELinux code, you'll see that others have
been converting other hash tables to using the jhash functions, so may
want to try those here too.