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

Message-ID: <CAEjxPJ4naa66Aum5YO0jntY5-reXxF5Z-=JYTcmb7WFCBODAHg@mail.gmail.com>
Date: Thu, 11 Sep 2025 09:25:38 -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:23 AM Stephen Smalley
<stephen.smalley.work@...il.com> wrote:
>
> 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.

Or you could follow the example of ss/avtab.c which was converted to
MurmurHash3.