]> git.baikalelectronics.ru Git - kernel.git/commit
selinux: Use a better hash function for avtab
authorJohn Brooks <john.brooks@jolla.com>
Tue, 24 Mar 2015 20:54:17 +0000 (16:54 -0400)
committerPaul Moore <pmoore@redhat.com>
Tue, 7 Apr 2015 00:16:21 +0000 (20:16 -0400)
commitb2f8fa146b1a4eb7e1e19a50fe8bed68f7227b14
treece88911dbfbfa42b6cfd4c06631a25b74f94d53a
parentf6042d2af97427850c90ee52f5adb5d9f1f83870
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>
security/selinux/ss/avtab.c
security/selinux/ss/avtab.h