summaryrefslogtreecommitdiffstats
path: root/security/selinux
diff options
context:
space:
mode:
authorJohn Brooks <john.brooks@jolla.com>2015-03-24 21:54:17 +0100
committerPaul Moore <pmoore@redhat.com>2015-04-07 02:16:21 +0200
commit33ebc1932a07efd8728975750409741940334489 (patch)
treece88911dbfbfa42b6cfd4c06631a25b74f94d53a /security/selinux
parentselinux: convert avtab hash table to flex_array (diff)
downloadlinux-33ebc1932a07efd8728975750409741940334489.tar.xz
linux-33ebc1932a07efd8728975750409741940334489.zip
selinux: Use a better hash function for avtab
This function, based on murmurhash3, has much better distribution than the original. Using the current default of 2048 buckets, there are many fewer collisions: Before: 101421 entries and 2048/2048 buckets used, longest chain length 374 After: 101421 entries and 2048/2048 buckets used, longest chain length 81 The difference becomes much more significant when buckets are increased. A naive attempt to expand the current function to larger outputs doesn't yield any significant improvement; so this function is a prerequisite for increasing the bucket size. sds: Adapted from the original patches for libsepol to the kernel. Signed-off-by: John Brooks <john.brooks@jolla.com> Signed-off-by: Stephen Smalley <sds@tycho.nsa.gov> Signed-off-by: Paul Moore <pmoore@redhat.com>
Diffstat (limited to 'security/selinux')
-rw-r--r--security/selinux/ss/avtab.c41
-rw-r--r--security/selinux/ss/avtab.h2
2 files changed, 38 insertions, 5 deletions
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 3ea0198fc964..b64f2772b030 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -25,10 +25,43 @@
static struct kmem_cache *avtab_node_cachep;
-static inline int avtab_hash(struct avtab_key *keyp, u16 mask)
+/* Based on MurmurHash3, written by Austin Appleby and placed in the
+ * public domain.
+ */
+static inline int avtab_hash(struct avtab_key *keyp, u32 mask)
{
- return ((keyp->target_class + (keyp->target_type << 2) +
- (keyp->source_type << 9)) & 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;
}
static struct avtab_node*
@@ -256,7 +289,7 @@ int avtab_init(struct avtab *h)
int avtab_alloc(struct avtab *h, u32 nrules)
{
- u16 mask = 0;
+ u32 mask = 0;
u32 shift = 0;
u32 work = nrules;
u32 nslot = 0;
diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index 9318b2b8f6c9..6d794a2eee57 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -56,7 +56,7 @@ struct avtab {
struct flex_array *htable;
u32 nel; /* number of elements */
u32 nslot; /* number of hash slots */
- u16 mask; /* mask to compute hash func */
+ u32 mask; /* mask to compute hash func */
};