| Message ID | 20200408182416.30995-5-siarhei.liakh@concurrent-rt.com (mailing list archive) |
|---|---|
| State | Changes Requested |
| Headers | show |
| Series | [1/9] SELinux: Introduce "Advanced Hashing" Kconfig option | expand |
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). > > 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. > + * 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.
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!
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. +/* + * 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; } static struct avtab_node*