Re: [PATCH v3 2/2] selinux: improve bucket distribution uniformity of avc_hash()

[Paul Moore <paul@paul-moore.com>]

On Sep 26, 2025 Hongru Zhang <zhanghongru06@gmail.com> wrote:
> 
> 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     |     58.2%/6.2      |
> +--------------------------+--------------------+--------------------+
> | 1024 nodes,  512 buckets |      68.9%/12.1    |     82.4%/8.9      |
> +--------------------------+--------------------+--------------------+
> | 2048 nodes,  512 buckets |      83.7%/19.4    |     94.8%/15.2     |
> +--------------------------+--------------------+--------------------+
> | 8192 nodes, 8192 buckets |      49.5%/11.4    |     61.9%/6.6      |
> +--------------------------+--------------------+--------------------+
> 
> 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        |        79ns        |
> +--------------------------+--------------------+--------------------+
> | 1024 nodes,  512 buckets |        97ns        |        91ns        |
> +--------------------------+--------------------+--------------------+
> | 2048 nodes,  512 buckets |       118ns        |       110ns        |
> +--------------------------+--------------------+--------------------+
> | 8192 nodes, 8192 buckets |       106ns        |        94ns        |
> +--------------------------+--------------------+--------------------+
> 
> Although the multiplication in the new hash algorithm has higher overhead
> than the bitwise operations in the original algorithm, the data shows
> that the new algorithm 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@xiaomi.com>
> Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> ---
>  security/selinux/avc.c | 17 ++++++++++++++++-
>  1 file changed, 16 insertions(+), 1 deletion(-)

My understanding from previous iterations of this patch is that this new
hash function was AI generated and hasn't really gone through the any
rigorus analysis beyond the performance measurements above, is that
correct?  I'm not opposed to using AI to assist in patch development or
algorithm creation, especially if there is some acknowledgement in the
commit description, but I do hold the patches to the same standard as
any other proposed change.  For this reason, I would expect some third
party review of the hash function by someone with enough experience to
provide a reasonable analysis of the hash function in comparison to
other existing options.

... and yes, I do recognize that the existing AVC hash function likely
did not have to go through the same level of scrutiny, but it has the
significant advantage of being a known quantity, problems and all.

If you want to change the AVC hash to something else with better
performance, I suggest sticking with a well known hash algorithm,
ideally one already present in the kernel; that is going to be the
quickest path towards acceptance.

--
paul-moore.com