Hi,
On Wed, Apr 8, 2020 at 8:24 PM <siarhei.liakh@xxxxxxxxxxxxxxxxx> wrote:
>
> From: Siarhei Liakh <siarhei.liakh@xxxxxxxxxxxxxxxxx>
>
> This patch replaces local copy of custom implementation of MurmurHash3 in
> avtab.c with existing generic implementation of lookup3 from the standard
> Linux library. The library version of hash used to mix 3 x u32 values is
> comparable to the custom implementation in run time complexity and bit
> avalanche. This change allows to reduce the amount of custom code with has
> to be maintained, while preserving overall performance of the hash table
> in question.
>
> Before (MurmurHash3):
> rules: 282731 entries and 64534/65536 buckets used, longest chain length 17
> sum of chain length^2 1522043
>
> After (lookup3):
> rules: 282731 entries and 64572/65536 buckets used, longest chain length 16
> sum of chain length^2 1517651
>
> Please note that either hash can show a slight [dis]advantage over the other
> depending purely on actual rule sets loaded and number of buckets configured.
FWIW, I did a quick check comparing the duration of
context_struct_compute_av() (triggered by forcing AVC misses) with and
without this patch (i.e. its fixed version - see below) and there
seems to be no measurable difference. I didn't compare the bucket
occupancy stats, but I expect them to be equivalent or slightly
better, as data from your commit message also shows. So considering
that it removes a chunk of ugly code while not regressing in
performance, I'm in favor of this patch (assuming issues below are
fixed).
>
> Signed-off-by: Siarhei Liakh <siarhei.liakh@xxxxxxxxxxxxxxxxx>
> ---
> Please CC me directly in all replies.
>
> security/selinux/ss/avtab.c | 39 +++++--------------------------------
> 1 file changed, 5 insertions(+), 34 deletions(-)
>
> diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
> index 01b300a4a882..58f0de17e463 100644
> --- a/security/selinux/ss/avtab.c
> +++ b/security/selinux/ss/avtab.c
> @@ -20,49 +20,20 @@
> #include <linux/kernel.h>
> #include <linux/slab.h>
> #include <linux/errno.h>
> +#include <linux/jhash.h>
> #include "avtab.h"
> #include "policydb.h"
>
> static struct kmem_cache *avtab_node_cachep;
> static struct kmem_cache *avtab_xperms_cachep;
>
> -/* Based on MurmurHash3, written by Austin Appleby and placed in the
> - * public domain.
> +/*
Your patch has a trailing space after the '*' in the above line.
Please remove it.
> + * Use existing Bob Jenkins' lookup3 hash from the library
> */
> static inline int avtab_hash(struct avtab_key *keyp, u32 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;
> + return jhash_3words(keyp->target_class, keyp->target_type,
> + keyp->source_type) & mask;
This function takes 4 arguments, not 3. (I can see you mentioned in
your reply to Paul that you accidentally sent an older version of the
patches, so I hope you have this already fixed in the final version.)
Also, please align the second line properly (start of
"keyp->source_type" should be aligned with the end of "jhash_3words("
on the previous line). Please also check for similar whitespace issues
in the rest of the patches, since I didn't have a closer look at those
yet.
Thanks,
> }
>
> static struct avtab_node*
> --
> 2.17.1
>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
