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>
diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index 9318b2b..6d794a2 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -56,7 +56,7 @@
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 */
};