• John Brooks's avatar
    selinux: Use a better hash function for avtab · 33ebc193
    John Brooks authored
    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: default avatarJohn Brooks <john.brooks@jolla.com>
    Signed-off-by: default avatarStephen Smalley <sds@tycho.nsa.gov>
    Signed-off-by: default avatarPaul Moore <pmoore@redhat.com>
    33ebc193
avtab.h 2.87 KB