• Christian Göttsche's avatar
    selinux: improve role transition hashing · 37b7ea3c
    Christian Göttsche authored
    The number of buckets is calculated by performing a binary AND against
    the mask of the hash table, which is one less than its size (which is a
    power of two).  This leads to all top bits being discarded, e.g. with
    the Reference Policy on Debian there exists 376 entries, leading to a
    size of 512, discarding the top 23 bits.
    
    Use jhash to improve the hash table utilization:
    
        # current
        roletr:  376 entries and 124/512 buckets used,
                 longest chain length 8, sum of chain length^2 1496
    
        # patch
        roletr:  376 entries and 266/512 buckets used,
                 longest chain length 4, sum of chain length^2 646
    Signed-off-by: default avatarChristian Göttsche <cgzones@googlemail.com>
    Reviewed-by: default avatarStephen Smalley <stephen.smalley.work@gmail.com>
    [PM: line wrap in the commit description]
    Signed-off-by: default avatarPaul Moore <paul@paul-moore.com>
    37b7ea3c
policydb.c 75.7 KB