[2/9] SELinux: Use Bob Jenkins' lookup3 hash in AVC

Commit Message

Siarhei Liakh April 8, 2020, 6:24 p.m. UTC

From: Siarhei Liakh <[e-mail]>

This patch allows use of lookup3 as a hash function within AVC with
following benefits:
1. lookup3 has much better bit avalanche properties as compared to local
version of custom hash function, thus reducing hash table collisions.
2. lookup3 is part of standard Linux library, thus provides a much better
long-term maintenance path

Here is an example of how lookup3 improves distribution of entries within AVC:
BJ's lookup3:
entries: 4962
buckets used: 2839/4096
longest chain: 7

Standard hash function:
entries: 4974
buckets used: 2582/4096
longest chain: 12

Signed-off-by: Siarhei Liakh <[e-mail]>
---
Please CC me directly in all replies.

 security/selinux/avc.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

Patch

diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index d18cb32a242a..b5893621290b 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -121,9 +121,24 @@  static struct kmem_cache *avc_xperms_data_cachep;
 static struct kmem_cache *avc_xperms_decision_cachep;
 static struct kmem_cache *avc_xperms_cachep;
 
+#ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING
+
+#include <linux/jhash.h>
+#define _avc_hash3(a, b, c) jhash_3words(a, b, c, 0)
+
+#else /* #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
+/*
+ * Original hashing function
+ */
+static inline u32 _avc_hash3(u32 a, u32 b, u32 c)
+{
+	return (a ^ (b << 2) ^ (c << 4));
+}
+#endif /* #else #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
+
 static inline int avc_hash(u32 ssid, u32 tsid, u16 tclass)
 {
-	return (ssid ^ (tsid<<2) ^ (tclass<<4)) & (AVC_CACHE_SLOTS - 1);
+	return _avc_hash3(ssid, tsid, tclass) & (AVC_CACHE_SLOTS - 1);
 }
 
 /**