[PATCH 4/9] SELinux: Replace custom hash in avtab with generic lookup3 from the library

From: siarhei.liakh@concurrent-rt.com
To: selinux@vger.kernel.org
Cc: colin.king@canonical.com, eparis@parisplace.org,
	gregkh@linuxfoundation.org, jeffv@google.com,
	omosnace@redhat.com, paul@paul-moore.com,
	stephen.smalley.work@gmail.com, tglx@linutronix.de
Subject: [PATCH 4/9] SELinux: Replace custom hash in avtab with generic lookup3 from the library
Date: Wed,  8 Apr 2020 14:24:11 -0400	[thread overview]
Message-ID: <20200408182416.30995-5-siarhei.liakh@concurrent-rt.com> (raw)
In-Reply-To: <20200408182416.30995-1-siarhei.liakh@concurrent-rt.com>

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This patch replaces local copy of custom implementation of MurmurHash3 in
avtab.c with existing generic implementation of lookup3 from the standard
Linux library. The library version of hash used to mix 3 x u32 values is
comparable to the custom implementation in run time complexity and bit
avalanche. This change allows to reduce the amount of custom code with has
to be maintained, while preserving overall performance of the hash table
in question.

Before (MurmurHash3):
rules:  282731 entries and 64534/65536 buckets used, longest chain length 17
sum of chain length^2 1522043

After (lookup3):
rules:  282731 entries and 64572/65536 buckets used, longest chain length 16
sum of chain length^2 1517651

Please note that either hash can show a slight [dis]advantage over the other
depending purely on actual rule sets loaded and number of buckets configured.

Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
---
Please CC me directly in all replies.

 security/selinux/ss/avtab.c | 39 +++++--------------------------------
 1 file changed, 5 insertions(+), 34 deletions(-)

diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 01b300a4a882..58f0de17e463 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -20,49 +20,20 @@
 #include <linux/kernel.h>
 #include <linux/slab.h>
 #include <linux/errno.h>
+#include <linux/jhash.h>
 #include "avtab.h"
 #include "policydb.h"
 
 static struct kmem_cache *avtab_node_cachep;
 static struct kmem_cache *avtab_xperms_cachep;
 
-/* Based on MurmurHash3, written by Austin Appleby and placed in the
- * public domain.
+/* 
+ * Use existing Bob Jenkins' lookup3 hash from the library
  */
 static inline int avtab_hash(struct avtab_key *keyp, u32 mask)
 {
-	static const u32 c1 = 0xcc9e2d51;
-	static const u32 c2 = 0x1b873593;
-	static const u32 r1 = 15;
-	static const u32 r2 = 13;
-	static const u32 m  = 5;
-	static const u32 n  = 0xe6546b64;
-
-	u32 hash = 0;
-
-#define mix(input) { \
-	u32 v = input; \
-	v *= c1; \
-	v = (v << r1) | (v >> (32 - r1)); \
-	v *= c2; \
-	hash ^= v; \
-	hash = (hash << r2) | (hash >> (32 - r2)); \
-	hash = hash * m + n; \
-}
-
-	mix(keyp->target_class);
-	mix(keyp->target_type);
-	mix(keyp->source_type);
-
-#undef mix
-
-	hash ^= hash >> 16;
-	hash *= 0x85ebca6b;
-	hash ^= hash >> 13;
-	hash *= 0xc2b2ae35;
-	hash ^= hash >> 16;
-
-	return hash & mask;
+	return jhash_3words(keyp->target_class, keyp->target_type,
+				keyp->source_type) & mask;
 }
 
 static struct avtab_node*
-- 
2.17.1

