Re: [PATCH 4/9] SELinux: Replace custom hash in avtab with generic lookup3 from the library

[Siarhei Liakh <siarhei.liakh@concurrent-rt.com>]

The 04/14/2020 12:58, Ondrej Mosnacek wrote:
> Hi,
> 
> On Wed, Apr 8, 2020 at 8:24 PM <siarhei.liakh@concurrent-rt.com> wrote:
> >
> > From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
> >
> > 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).

Good to hear that :-)
 
> >
> > Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
> > ---
> > 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.

Will do.

> > + * 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.)

Yes, that was fixed before the patches were sent out, as it would not compile
otherwise.

> 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.

Will do.
Thank you for your feedback!

-- 
Siarhei Liakh
Concurrent Real-Time