From: Hongru Zhang <zhanghongru@xiaomi.com>
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:
+--------------------------+-----------------------------------------+
| | 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 |
+--------------------------+--------------------+--------------------+
Signed-off-by: Hongru Zhang <zhanghongru@xiaomi.com>
---
security/selinux/avc.c | 16 +++++++++++++++-
1 file changed, 15 insertions(+), 1 deletion(-)
diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index 7a7f88012865..d08f30d57bac 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -146,9 +146,23 @@ static struct kmem_cache *avc_xperms_data_cachep __ro_after_init;
static struct kmem_cache *avc_xperms_decision_cachep __ro_after_init;
static struct kmem_cache *avc_xperms_cachep __ro_after_init;
+/*
+ * Advantages of this hash design:
+ * - Minimized collisions: Different inputs won't produce similar
+ * contributions
+ * - Bit diffusion: Each constant effectively scrambles input bits
+ * - Mathematical guarantee: These constants are theoretically analyzed
+ * and empirically validated
+ * - Complementarity: Three constants complement each other at the
+ * binary level
+ */
+#define C1 0x9E3779B9 /* 2^32 * Golden Ratio, classic constant for Knuth's
+ multiplicative hashing */
+#define C2 0x85EBCA77 /* Large prime-like properties */
+#define C3 0xC2B2AE35 /* Large prime-like properties, MurmurHash3 constant */
static inline u32 avc_hash(u32 ssid, u32 tsid, u16 tclass)
{
- return (ssid ^ (tsid<<2) ^ (tclass<<4)) & (avc_cache_slots - 1);
+ return (ssid * C1 + tsid * C2 + tclass * C3) & (avc_cache_slots - 1);
}
/**
--
2.43.0On Tue, Sep 23, 2025 at 10:56 PM Hongru Zhang <zhanghongru06@gmail.com> wrote:
>
> From: Hongru Zhang <zhanghongru@xiaomi.com>
>
> 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:
> +--------------------------+-----------------------------------------+
> | | 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 |
> +--------------------------+--------------------+--------------------+
>
> Signed-off-by: Hongru Zhang <zhanghongru@xiaomi.com>
Can you re-run the latency tests from the 1st patch and provide the
results with this one applied?
Also, checkpatch.pl reports the following warnings; please fix:
WARNING: Block comments use * on subsequent lines
#47: FILE: security/selinux/avc.c:160:
+#define C1 0x9E3779B9 /* 2^32 * Golden Ratio, classic constant for Knuth's
+ multiplicative hashing */
WARNING: Block comments use a trailing */ on a separate line
#47: FILE: security/selinux/avc.c:160:
+ multiplicative hashing */
total: 0 errors, 2 warnings, 24 lines checked
> ---
> security/selinux/avc.c | 16 +++++++++++++++-
> 1 file changed, 15 insertions(+), 1 deletion(-)
>
> diff --git a/security/selinux/avc.c b/security/selinux/avc.c
> index 7a7f88012865..d08f30d57bac 100644
> --- a/security/selinux/avc.c
> +++ b/security/selinux/avc.c
> @@ -146,9 +146,23 @@ static struct kmem_cache *avc_xperms_data_cachep __ro_after_init;
> static struct kmem_cache *avc_xperms_decision_cachep __ro_after_init;
> static struct kmem_cache *avc_xperms_cachep __ro_after_init;
>
> +/*
> + * Advantages of this hash design:
> + * - Minimized collisions: Different inputs won't produce similar
> + * contributions
> + * - Bit diffusion: Each constant effectively scrambles input bits
> + * - Mathematical guarantee: These constants are theoretically analyzed
> + * and empirically validated
> + * - Complementarity: Three constants complement each other at the
> + * binary level
> + */
> +#define C1 0x9E3779B9 /* 2^32 * Golden Ratio, classic constant for Knuth's
> + multiplicative hashing */
> +#define C2 0x85EBCA77 /* Large prime-like properties */
> +#define C3 0xC2B2AE35 /* Large prime-like properties, MurmurHash3 constant */
> static inline u32 avc_hash(u32 ssid, u32 tsid, u16 tclass)
> {
> - return (ssid ^ (tsid<<2) ^ (tclass<<4)) & (avc_cache_slots - 1);
> + return (ssid * C1 + tsid * C2 + tclass * C3) & (avc_cache_slots - 1);
> }
>
> /**
> --
> 2.43.0
>
> Can you re-run the latency tests from the 1st patch and provide the > results with this one applied? > Also, checkpatch.pl reports the following warnings; please fix: > WARNING: Block comments use * on subsequent lines > #47: FILE: security/selinux/avc.c:160: > +#define C1 0x9E3779B9 /* 2^32 * Golden Ratio, classic constant for Knuth's > + multiplicative hashing */ > > WARNING: Block comments use a trailing */ on a separate line > #47: FILE: security/selinux/avc.c:160: > + multiplicative hashing */ > > total: 0 errors, 2 warnings, 24 lines checked Thanks for the suggestions. I'll update latency results to changelog, fix the warnings, and then submit a new version.
© 2016 - 2025 Red Hat, Inc.