diff options
| author | John Brooks <john.brooks@jolla.com> | 2015-03-24 16:54:17 -0400 |
|---|---|---|
| committer | Paul Moore <pmoore@redhat.com> | 2015-04-06 20:16:21 -0400 |
| commit | 33ebc1932a07efd8728975750409741940334489 (patch) | |
| tree | ce88911dbfbfa42b6cfd4c06631a25b74f94d53a /security | |
| parent | ba39db6e0519aa8362dbda6523ceb69349a18dc3 (diff) | |
| download | linux-33ebc1932a07efd8728975750409741940334489.tar.bz2 | |
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')
| -rw-r--r-- | security/selinux/ss/avtab.c | 41 | ||||
| -rw-r--r-- | security/selinux/ss/avtab.h | 2 |
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 */ }; |