lkml.org 
[lkml]   [2025]   [Sep]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [PATCH] selinux: Make avc cache slot size configurable during boot
On Thu, Sep 11, 2025 at 9:23 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Thu, Sep 11, 2025 at 9:07 AM Hongru Zhang <zhanghongru06@gmail.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.

\
 
 \ /
  Last update: 2025-09-11 15:28    [from the cache]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and my Meterkast|Read the blog