[PATCH 0/9] SELinux: Improve hash functions and sizing of hash tables

[PATCH 0/9] SELinux: Improve hash functions and sizing of hash tables

[siarhei.liakh]

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This patch set is the result of an actual customer support case where a client
of ours observed unacceptable variability of timings while sending UDP packets
via sendto() with SELinux enabled. The initial investigation centered around
kernel 3.10.108 in CentOS 6.5 environment. Combination of these patches with
some substantial tuning of newly added Kconfig options was able to reduce
*maximum* sendto() latency to about 160us, down from well over 2ms. Worst
latency was typically observed when a new SSH login was initiated concurrently
with the test program running a sendto() loop, thus causing an AVC miss with a
subsequent call to security_compute_av(), which would spend most of its time
iterating through policydb within context_struct_compute_av(). 

The original patch set was developed for linux kernel 3.10.108 and later ported
to newer versions. The patch set presented here is based off Linus' tree as of
April 7, 2020 and contains only a subset of the changes which are still relevant
to 5.6+ as many of the issues had already been addressed in different ways.

The patch set consists of 9 patches total and is meant to achieve two goals:
1. Replace most local copies of custom hash functions with generic hash
   functions already available in inlude/linux/*.h.
   
2. Replace hard-coded hash table sizing parameters with Kconfig tunables.

"Advanced Hashing" Kconfig option is the only dependency between the patches,
but other than that and any combination of them can be used.

Please CC me directly in all replies.

Siarhei Liakh (9):
  SELinux: Introduce "Advanced Hashing" Kconfig option
  SELinux: Use Bob Jenkins' lookup3 hash in AVC
  SELinux: Expose AVC sizing tunables via Kconfig
  SELinux: Replace custom hash in avtab with generic lookup3 from the
    library
  SELinux: Expose AVTab sizing tunables via Kconfig
  SELinux: Replace custom hash with generic lookup3 in policydb
  SELinux: Expose filename_tr hash table sizing via Kconfig
  SELinux: Replace custom hash with generic lookup3 in symtab
  SELinux: Expose netport hash table sizing via Kconfig

 security/selinux/Kconfig       | 83 ++++++++++++++++++++++++++++++++++
 security/selinux/avc.c         | 23 ++++++++--
 security/selinux/netport.c     |  4 +-
 security/selinux/ss/avtab.c    | 39 ++--------------
 security/selinux/ss/avtab.h    |  2 +-
 security/selinux/ss/policydb.c | 46 +++++++++++++++----
 security/selinux/ss/symtab.c   | 12 +++++
 7 files changed, 159 insertions(+), 50 deletions(-)

-- 
2.17.1

[PATCH 1/9] SELinux: Introduce "Advanced Hashing" Kconfig option

[siarhei.liakh]

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This patch introduces "Advanced Hashing" Kconfig option for SELinux,
which is used by subsequent patches to switch between faster, simpler
local hash functions and a bit slower, but much better ones from standard
Linux library. The patch only adds an option; hash function changes are
provided as separate patches, one per function changed.

Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
---
Please CC me directly in all replies.

 security/selinux/Kconfig | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
index 9e921fc72538..4b5c9fa510a1 100644
--- a/security/selinux/Kconfig
+++ b/security/selinux/Kconfig
@@ -61,6 +61,15 @@ config SECURITY_SELINUX_DEVELOP
 	  permissive mode (if permitted by the policy) via
 	  /sys/fs/selinux/enforce.
 
+config SECURITY_SELINUX_ADVANCED_HASHING
+	bool "Advanced hashing for primary hash tables"
+	depends on SECURITY_SELINUX
+	default n
+	help
+	  This enables better, but a little slower hashing functions in hash
+	  tables. New hashing function greatly reduces hash collisions, thus
+	  improving performance of large/complex SELinux configurations.
+
 config SECURITY_SELINUX_AVC_STATS
 	bool "NSA SELinux AVC Statistics"
 	depends on SECURITY_SELINUX
-- 
2.17.1

[PATCH 2/9] SELinux: Use Bob Jenkins' lookup3 hash in AVC

[siarhei.liakh]

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This patch allows use of lookup3 as a hash function within AVC with
following benefits:
1. lookup3 has much better bit avalanche properties as compared to local
version of custom hash function, thus reducing hash table collisions.
2. lookup3 is part of standard Linux library, thus provides a much better
long-term maintenance path

Here is an example of how lookup3 improves distribution of entries within AVC:
BJ's lookup3:
entries: 4962
buckets used: 2839/4096
longest chain: 7

Standard hash function:
entries: 4974
buckets used: 2582/4096
longest chain: 12

Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
---
Please CC me directly in all replies.

 security/selinux/avc.c | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index d18cb32a242a..b5893621290b 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -121,9 +121,24 @@ static struct kmem_cache *avc_xperms_data_cachep;
 static struct kmem_cache *avc_xperms_decision_cachep;
 static struct kmem_cache *avc_xperms_cachep;
 
+#ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING
+
+#include <linux/jhash.h>
+#define _avc_hash3(a, b, c) jhash_3words(a, b, c, 0)
+
+#else /* #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
+/*
+ * Original hashing function
+ */
+static inline u32 _avc_hash3(u32 a, u32 b, u32 c)
+{
+	return (a ^ (b << 2) ^ (c << 4));
+}
+#endif /* #else #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
+
 static inline int avc_hash(u32 ssid, u32 tsid, u16 tclass)
 {
-	return (ssid ^ (tsid<<2) ^ (tclass<<4)) & (AVC_CACHE_SLOTS - 1);
+	return _avc_hash3(ssid, tsid, tclass) & (AVC_CACHE_SLOTS - 1);
 }
 
 /**
-- 
2.17.1

[PATCH 3/9] SELinux: Expose AVC sizing tunables via Kconfig

[siarhei.liakh]

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This change exposes previously hardcoded AVC sizing tunables via Kconfig,
which provides a more convenient tuning mechanism for downstream distributions.
Default sizing is not affected.

Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
---
Please CC me directly in all replies.

 security/selinux/Kconfig | 32 ++++++++++++++++++++++++++++++++
 security/selinux/avc.c   |  6 +++---
 2 files changed, 35 insertions(+), 3 deletions(-)

diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
index 4b5c9fa510a1..3a736a1c6806 100644
--- a/security/selinux/Kconfig
+++ b/security/selinux/Kconfig
@@ -79,6 +79,38 @@ config SECURITY_SELINUX_AVC_STATS
 	  /sys/fs/selinux/avc/cache_stats, which may be monitored via
 	  tools such as avcstat.
 
+config SECURITY_SELINUX_AVC_DEF_THRESHOLD
+	int "Default value for AVC reclamation threshold"
+	depends on SECURITY_SELINUX
+	range 64 1048576
+	default "512"
+	help
+	  Reclamation threshold effectively sets a limit on AVC size.
+	  Increasing this number could improve performance of busy
+	  systems with lots of complex policies. Threshold value can
+	  also be changed at run-time via selinuxfs.
+
+config SECURITY_SELINUX_AVC_HASH_BITS
+	int "Number of slots (buckets) for AVC hash table, expressed as number of bits (i.e. 2^n)"
+	depends on SECURITY_SELINUX
+	range 1 32
+	default "9"
+	help
+	  This is a power of 2 representing the number of slots (buckets)
+	  used for AVC hash table. Smaller value reduces memory footprint
+	  at price of hash table lookup efficiency.
+
+config SECURITY_SELINUX_AVC_RECLAIM_COUNT
+	int "Number of AVC entries to reclaim in a single cycle"
+	depends on SECURITY_SELINUX
+	range 1 SECURITY_SELINUX_AVC_DEF_THRESHOLD
+	default "16"
+	help
+	  A single reclamation cycle will evict this many AVC entries
+	  from the cache. Small values may require multiple reclamation
+	  cycles to bring AVC size under the threshold. Large values may
+	  cause excessive latency of reclamation events.
+
 config SECURITY_SELINUX_CHECKREQPROT_VALUE
 	int "NSA SELinux checkreqprot default value"
 	depends on SECURITY_SELINUX
diff --git a/security/selinux/avc.c b/security/selinux/avc.c
index b5893621290b..80af3d1f31fd 100644
--- a/security/selinux/avc.c
+++ b/security/selinux/avc.c
@@ -31,9 +31,9 @@
 #include "avc_ss.h"
 #include "classmap.h"
 
-#define AVC_CACHE_SLOTS			512
-#define AVC_DEF_CACHE_THRESHOLD		512
-#define AVC_CACHE_RECLAIM		16
+#define AVC_CACHE_SLOTS			(1 << CONFIG_SECURITY_SELINUX_AVC_HASH_BITS)
+#define AVC_DEF_CACHE_THRESHOLD		CONFIG_SECURITY_SELINUX_AVC_DEF_THRESHOLD
+#define AVC_CACHE_RECLAIM		CONFIG_SECURITY_SELINUX_AVC_RECLAIM_COUNT
 
 #ifdef CONFIG_SECURITY_SELINUX_AVC_STATS
 #define avc_cache_stats_incr(field)	this_cpu_inc(avc_cache_stats.field)
-- 
2.17.1

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

[siarhei.liakh]

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.

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.
+/* 
+ * 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*
-- 
2.17.1

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

[Ondrej Mosnacek]

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.

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

[Siarhei Liakh]

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

[PATCH 5/9] SELinux: Expose AVTab sizing tunables via Kconfig

[siarhei.liakh]

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This change exposes previously hardcoded AVTab sizing tunables via Kconfig,
which provides a more convenient tuning mechanism for downstream distributions.
Default sizing is not affected.

Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
---
Please CC me directly in all replies.

 security/selinux/Kconfig    | 12 ++++++++++++
 security/selinux/ss/avtab.h |  2 +-
 2 files changed, 13 insertions(+), 1 deletion(-)

diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
index 3a736a1c6806..b7ced53ffd76 100644
--- a/security/selinux/Kconfig
+++ b/security/selinux/Kconfig
@@ -111,6 +111,18 @@ config SECURITY_SELINUX_AVC_RECLAIM_COUNT
 	  cycles to bring AVC size under the threshold. Large values may
 	  cause excessive latency of reclamation events.
 
+config SECURITY_SELINUX_AVTAB_HASH_BITS
+	int "Number of slots (buckets) for AVTab hash table, expressed as number of bits (i.e. 2^n)"
+	depends on SECURITY_SELINUX
+	range 1 32
+	default "16"
+	help
+	  This is a power of 2 representing the number of slots (buckets)
+	  used for AVTab hash table. AVTab is the core SELinux database
+	  holding all of the applicable rules. Smaller value reduces memory
+	  footprint at price of hash table lookup efficiency. One bucket
+	  per 10 to 100 rules is reasonable.
+
 config SECURITY_SELINUX_CHECKREQPROT_VALUE
 	int "NSA SELinux checkreqprot default value"
 	depends on SECURITY_SELINUX
diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index 5fdcb6696bcc..52b3f82ddacd 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -110,7 +110,7 @@ struct avtab_node *avtab_search_node(struct avtab *h, struct avtab_key *key);
 
 struct avtab_node *avtab_search_node_next(struct avtab_node *node, int specified);
 
-#define MAX_AVTAB_HASH_BITS 16
+#define MAX_AVTAB_HASH_BITS CONFIG_SECURITY_SELINUX_AVTAB_HASH_BITS
 #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
 
 #endif	/* _SS_AVTAB_H_ */
-- 
2.17.1

[PATCH 6/9] SELinux: Replace custom hash with generic lookup3 in policydb

[siarhei.liakh]

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This patch replaces local copy of custom hash function with existing
implementation of lookup3 from the standard Linux library. This change
allows to reduce the amount of custom code with has to be maintained, while
potentially improving overall performance of the hash table in question.

Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
---
Please CC me directly in all replies.

 security/selinux/ss/policydb.c | 43 +++++++++++++++++++++++++++-------
 1 file changed, 35 insertions(+), 8 deletions(-)

diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 70ecdc78efbd..0d03036ca20d 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -41,6 +41,10 @@
 #include "mls.h"
 #include "services.h"
 
+#ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING
+#include <linux/jhash.h>
+#endif /* #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
+
 #define _DEBUG_HASHES
 
 #ifdef DEBUG_HASHES
@@ -399,6 +403,27 @@ static int roles_init(struct policydb *p)
 	return rc;
 }
 
+#ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING
+
+static u32 filenametr_hash(struct hashtab *h, const void *k)
+{
+	const struct filename_trans_key *ft = k;
+	unsigned long hash;
+
+	hash = jhash_2words(ft->ttype, ft->tclass, 0);
+	hash = jhash(ft->name, strlen(ft->name), hash);
+	return hash & (h->size - 1);
+}
+
+static u32 rangetr_hash(struct hashtab *h, const void *k)
+{
+	const struct range_trans_key *key = k;
+	return jhash_3words(key->source_type, key->target_type,
+			key->target_class, 0) & (h->size - 1);
+}
+
+#else /* #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
+
 static u32 filenametr_hash(struct hashtab *h, const void *k)
 {
 	const struct filename_trans_key *ft = k;
@@ -414,6 +439,16 @@ static u32 filenametr_hash(struct hashtab *h, const void *k)
 	return hash & (h->size - 1);
 }
 
+static u32 rangetr_hash(struct hashtab *h, const void *k)
+{
+	const struct range_trans *key = k;
+
+	return (key->source_type + (key->target_type << 3) +
+		(key->target_class << 5)) & (h->size - 1);
+}
+
+#endif /* #else #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
+
 static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
 {
 	const struct filename_trans_key *ft1 = k1;
@@ -432,14 +467,6 @@ static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
 
 }
 
-static u32 rangetr_hash(struct hashtab *h, const void *k)
-{
-	const struct range_trans *key = k;
-
-	return (key->source_type + (key->target_type << 3) +
-		(key->target_class << 5)) & (h->size - 1);
-}
-
 static int rangetr_cmp(struct hashtab *h, const void *k1, const void *k2)
 {
 	const struct range_trans *key1 = k1, *key2 = k2;
-- 
2.17.1

[PATCH 7/9] SELinux: Expose filename_tr hash table sizing via Kconfig

[siarhei.liakh]

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This change exposes previously hardcoded filename_tr sizing via Kconfig,
which provides a more convenient tuning mechanism for downstream distributions.
Default sizing is not affected.

Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
---
Please CC me directly in all replies.

 security/selinux/Kconfig       | 10 ++++++++++
 security/selinux/ss/policydb.c |  3 ++-
 2 files changed, 12 insertions(+), 1 deletion(-)

diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
index b7ced53ffd76..23ec741b1ce6 100644
--- a/security/selinux/Kconfig
+++ b/security/selinux/Kconfig
@@ -123,6 +123,16 @@ config SECURITY_SELINUX_AVTAB_HASH_BITS
 	  footprint at price of hash table lookup efficiency. One bucket
 	  per 10 to 100 rules is reasonable.
 
+config SECURITY_SELINUX_PDB_FILE_TR_HASH_BITS
+	int "Number of slots (buckets) for File Transitions hash table, expressed as number of bits (i.e. 2^n)"
+	depends on SECURITY_SELINUX
+	range 1 32
+	default "11"
+	help
+	  This is a power of 2 representing the number of slots (buckets)
+	  used for File Transitions hash table. Smaller value reduces memory
+	  footprint at price of hash table lookup efficiency.
+
 config SECURITY_SELINUX_CHECKREQPROT_VALUE
 	int "NSA SELinux checkreqprot default value"
 	depends on SECURITY_SELINUX
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 0d03036ca20d..f2d809dffb25 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -496,7 +496,8 @@ static int policydb_init(struct policydb *p)
 	cond_policydb_init(p);
 
 	p->filename_trans = hashtab_create(filenametr_hash, filenametr_cmp,
-					   (1 << 11));
+			   (1 << CONFIG_SECURITY_SELINUX_PDB_FILE_TR_HASH_BITS));
+
 	if (!p->filename_trans)
 		return -ENOMEM;
 
-- 
2.17.1

Re: [PATCH 7/9] SELinux: Expose filename_tr hash table sizing via Kconfig

[Ondrej Mosnacek]

Hi Siarhei,

On Wed, Apr 8, 2020 at 8:24 PM <siarhei.liakh@concurrent-rt.com> wrote:
>
> From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
>
> This change exposes previously hardcoded filename_tr sizing via Kconfig,
> which provides a more convenient tuning mechanism for downstream distributions.
> Default sizing is not affected.
>
> Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
> ---
> Please CC me directly in all replies.
>
>  security/selinux/Kconfig       | 10 ++++++++++
>  security/selinux/ss/policydb.c |  3 ++-
>  2 files changed, 12 insertions(+), 1 deletion(-)
>
> diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
> index b7ced53ffd76..23ec741b1ce6 100644
> --- a/security/selinux/Kconfig
> +++ b/security/selinux/Kconfig
> @@ -123,6 +123,16 @@ config SECURITY_SELINUX_AVTAB_HASH_BITS
>           footprint at price of hash table lookup efficiency. One bucket
>           per 10 to 100 rules is reasonable.
>
> +config SECURITY_SELINUX_PDB_FILE_TR_HASH_BITS
> +       int "Number of slots (buckets) for File Transitions hash table, expressed as number of bits (i.e. 2^n)"
> +       depends on SECURITY_SELINUX
> +       range 1 32
> +       default "11"
> +       help
> +         This is a power of 2 representing the number of slots (buckets)
> +         used for File Transitions hash table. Smaller value reduces memory
> +         footprint at price of hash table lookup efficiency.
> +
>  config SECURITY_SELINUX_CHECKREQPROT_VALUE
>         int "NSA SELinux checkreqprot default value"
>         depends on SECURITY_SELINUX
> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index 0d03036ca20d..f2d809dffb25 100644
> --- a/security/selinux/ss/policydb.c
> +++ b/security/selinux/ss/policydb.c
> @@ -496,7 +496,8 @@ static int policydb_init(struct policydb *p)
>         cond_policydb_init(p);
>
>         p->filename_trans = hashtab_create(filenametr_hash, filenametr_cmp,
> -                                          (1 << 11));
> +                          (1 << CONFIG_SECURITY_SELINUX_PDB_FILE_TR_HASH_BITS));
> +
>         if (!p->filename_trans)
>                 return -ENOMEM;
>
> --
> 2.17.1

Note that this patch in particular won't be needed after (if) [1] gets
merged. Then for all policies built by new userspace the number of
elements will be known before the hashtab creation and it will be
passed to hashtab_create() directly (as is already done for the other
hashtabs). The hard-coded size will only be used in the
backwards-compat code path (when a policy built by an older userspace
is loaded) and thus won't be worth tuning any more.

[1] https://patchwork.kernel.org/patch/11462503/

--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

Re: [PATCH 7/9] SELinux: Expose filename_tr hash table sizing via Kconfig

[Siarhei Liakh]

The 04/14/2020 12:54, Ondrej Mosnacek wrote:
> Hi Siarhei,
> 
> On Wed, Apr 8, 2020 at 8:24 PM <siarhei.liakh@concurrent-rt.com> wrote:
> >
> > From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
> >
> > This change exposes previously hardcoded filename_tr sizing via Kconfig,
> > which provides a more convenient tuning mechanism for downstream distributions.
> > Default sizing is not affected.
> >
> > Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
> > ---
> > Please CC me directly in all replies.
> >
> >  security/selinux/Kconfig       | 10 ++++++++++
> >  security/selinux/ss/policydb.c |  3 ++-
> >  2 files changed, 12 insertions(+), 1 deletion(-)
> >
> > diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
> > index b7ced53ffd76..23ec741b1ce6 100644
> > --- a/security/selinux/Kconfig
> > +++ b/security/selinux/Kconfig
> > @@ -123,6 +123,16 @@ config SECURITY_SELINUX_AVTAB_HASH_BITS
> >           footprint at price of hash table lookup efficiency. One bucket
> >           per 10 to 100 rules is reasonable.
> >
> > +config SECURITY_SELINUX_PDB_FILE_TR_HASH_BITS
> > +       int "Number of slots (buckets) for File Transitions hash table, expressed as number of bits (i.e. 2^n)"
> > +       depends on SECURITY_SELINUX
> > +       range 1 32
> > +       default "11"
> > +       help
> > +         This is a power of 2 representing the number of slots (buckets)
> > +         used for File Transitions hash table. Smaller value reduces memory
> > +         footprint at price of hash table lookup efficiency.
> > +
> >  config SECURITY_SELINUX_CHECKREQPROT_VALUE
> >         int "NSA SELinux checkreqprot default value"
> >         depends on SECURITY_SELINUX
> > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > index 0d03036ca20d..f2d809dffb25 100644
> > --- a/security/selinux/ss/policydb.c
> > +++ b/security/selinux/ss/policydb.c
> > @@ -496,7 +496,8 @@ static int policydb_init(struct policydb *p)
> >         cond_policydb_init(p);
> >
> >         p->filename_trans = hashtab_create(filenametr_hash, filenametr_cmp,
> > -                                          (1 << 11));
> > +                          (1 << CONFIG_SECURITY_SELINUX_PDB_FILE_TR_HASH_BITS));
> > +
> >         if (!p->filename_trans)
> >                 return -ENOMEM;
> >
> > --
> > 2.17.1
> 
> Note that this patch in particular won't be needed after (if) [1] gets
> merged. Then for all policies built by new userspace the number of
> elements will be known before the hashtab creation and it will be
> passed to hashtab_create() directly (as is already done for the other
> hashtabs). The hard-coded size will only be used in the
> backwards-compat code path (when a policy built by an older userspace
> is loaded) and thus won't be worth tuning any more.
> 
> [1] https://patchwork.kernel.org/patch/11462503/

This is excellent news!
Unfortunately, my clients tend to have really long product life cycles, meaning
that even with new kernels they will still have old userspace tools. I guess
I'll just keep these patches in our local tree...

Thank you!

-- 
Siarhei Liakh
Concurrent Real-Time

[PATCH 8/9] SELinux: Replace custom hash with generic lookup3 in symtab

[siarhei.liakh]

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This patch replaces local copy of custom hash function with existing
implementation of lookup3 from the standard Linux library. This change
allows to reduce the amount of custom code with has to be maintained, while
potentially improving overall performance of the hash table in question.

Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
---
Please CC me directly in all replies.

 security/selinux/ss/symtab.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/security/selinux/ss/symtab.c b/security/selinux/ss/symtab.c
index dc2ce94165d3..8d189d7683d1 100644
--- a/security/selinux/ss/symtab.c
+++ b/security/selinux/ss/symtab.c
@@ -9,6 +9,16 @@
 #include <linux/errno.h>
 #include "symtab.h"
 
+#ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING
+#include <linux/jhash.h>
+
+static unsigned int symhash(struct hashtab *h, const void *key)
+{
+	return jhash(key, strlen((const char *) key), 0) & (h->size - 1);
+}
+
+#else /* #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
+
 static unsigned int symhash(struct hashtab *h, const void *key)
 {
 	const char *p, *keyp;
@@ -23,6 +33,8 @@ static unsigned int symhash(struct hashtab *h, const void *key)
 	return val & (h->size - 1);
 }
 
+#endif /* #else #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
+
 static int symcmp(struct hashtab *h, const void *key1, const void *key2)
 {
 	const char *keyp1, *keyp2;
-- 
2.17.1

Re: [PATCH 8/9] SELinux: Replace custom hash with generic lookup3 in symtab

[Ondrej Mosnacek]

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 hash function with existing
> implementation of lookup3 from the standard Linux library. This change
> allows to reduce the amount of custom code with has to be maintained, while
> potentially improving overall performance of the hash table in question.
>
> Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
> ---
> Please CC me directly in all replies.
>
>  security/selinux/ss/symtab.c | 12 ++++++++++++
>  1 file changed, 12 insertions(+)
>
> diff --git a/security/selinux/ss/symtab.c b/security/selinux/ss/symtab.c
> index dc2ce94165d3..8d189d7683d1 100644
> --- a/security/selinux/ss/symtab.c
> +++ b/security/selinux/ss/symtab.c
> @@ -9,6 +9,16 @@
>  #include <linux/errno.h>
>  #include "symtab.h"
>
> +#ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING
> +#include <linux/jhash.h>
> +
> +static unsigned int symhash(struct hashtab *h, const void *key)
> +{
> +       return jhash(key, strlen((const char *) key), 0) & (h->size - 1);

Did you consider using full_name_hash() here instead? It is used in
other places (mainly filesystem code) to hash strings. I wonder how it
compares to jhash both in terms of speed and in terms of randomness of
the resulting hash. It would be nice if you could do some benchmarks
and provide some numbers to support the choice.

> +}
> +
> +#else /* #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
> +
>  static unsigned int symhash(struct hashtab *h, const void *key)
>  {
>         const char *p, *keyp;
> @@ -23,6 +33,8 @@ static unsigned int symhash(struct hashtab *h, const void *key)
>         return val & (h->size - 1);
>  }
>
> +#endif /* #else #ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING */
> +
>  static int symcmp(struct hashtab *h, const void *key1, const void *key2)
>  {
>         const char *keyp1, *keyp2;
> --
> 2.17.1
>

--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

Re: [PATCH 8/9] SELinux: Replace custom hash with generic lookup3 in symtab

[Siarhei Liakh]

The 04/14/2020 13:06, 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 hash function with existing
> > implementation of lookup3 from the standard Linux library. This change
> > allows to reduce the amount of custom code with has to be maintained, while
> > potentially improving overall performance of the hash table in question.
> >
> > Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
> > ---
> > Please CC me directly in all replies.
> >
> >  security/selinux/ss/symtab.c | 12 ++++++++++++
> >  1 file changed, 12 insertions(+)
> >
> > diff --git a/security/selinux/ss/symtab.c b/security/selinux/ss/symtab.c
> > index dc2ce94165d3..8d189d7683d1 100644
> > --- a/security/selinux/ss/symtab.c
> > +++ b/security/selinux/ss/symtab.c
> > @@ -9,6 +9,16 @@
> >  #include <linux/errno.h>
> >  #include "symtab.h"
> >
> > +#ifdef CONFIG_SECURITY_SELINUX_ADVANCED_HASHING
> > +#include <linux/jhash.h>
> > +
> > +static unsigned int symhash(struct hashtab *h, const void *key)
> > +{
> > +       return jhash(key, strlen((const char *) key), 0) & (h->size - 1);
> 
> Did you consider using full_name_hash() here instead? It is used in
> other places (mainly filesystem code) to hash strings. I wonder how it
> compares to jhash both in terms of speed and in terms of randomness of
> the resulting hash. It would be nice if you could do some benchmarks
> and provide some numbers to support the choice.

No, I have not considered other hashes, as my goal is to simply eliminate local
copies of custom hashes in favor of existing ones from the Linux library. So,
any other standard has will do, as far as I am concerned... However, this whole
conversation brings up an interesting point: looks like we need an official
hashing guide with benchmarks and references to official sources/research behind
each hash function available. Sounds like an excellent project for some student
somewhere! :-)

I'll see what I can quickly put together within the scope of this discussion,
though.
 
Thank you!

-- 
Siarhei Liakh
Concurrent Real-Time

[PATCH 9/9] SELinux: Expose netport hash table sizing via Kconfig

[siarhei.liakh]

From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>

This change exposes previously hardcoded netport sizing tunables via Kconfig,
which provides a more convenient tuning mechanism for downstream distributions.
Default sizing is not affected.

Signed-off-by: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
---
Please CC me directly in all replies.

 security/selinux/Kconfig   | 20 ++++++++++++++++++++
 security/selinux/netport.c |  4 ++--
 2 files changed, 22 insertions(+), 2 deletions(-)

diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
index 23ec741b1ce6..d65626142bcf 100644
--- a/security/selinux/Kconfig
+++ b/security/selinux/Kconfig
@@ -133,6 +133,26 @@ config SECURITY_SELINUX_PDB_FILE_TR_HASH_BITS
 	  used for File Transitions hash table. Smaller value reduces memory
 	  footprint at price of hash table lookup efficiency.
 
+config SECURITY_SELINUX_NETPORT_HASH_BITS
+	int "Number of slots (buckets) for Netport hash table, expressed as number of bits (i.e. 2^n)"
+	depends on SECURITY_SELINUX
+	range 1 16
+	default "8"
+	help
+	  This is a power of 2 representing the number of slots (buckets)
+	  used for Netport hash table. Smaller value reduces memory
+	  footprint at price of hash table lookup efficiency.
+
+config SECURITY_SELINUX_NETPORT_HASH_BLIMIT
+	int "Bucket size limit for Netport hash table."
+	depends on SECURITY_SELINUX
+	range 1 131072
+	default "16"
+	help
+	  This is a an upper limit on number of entries a bucket can hold
+	  within Netport hash. Lower values conserve memory at price of
+	  more expensive lookups when a Netport cache miss occurs.
+
 config SECURITY_SELINUX_CHECKREQPROT_VALUE
 	int "NSA SELinux checkreqprot default value"
 	depends on SECURITY_SELINUX
diff --git a/security/selinux/netport.c b/security/selinux/netport.c
index de727f7489b7..ef8e9abcadf7 100644
--- a/security/selinux/netport.c
+++ b/security/selinux/netport.c
@@ -32,8 +32,8 @@
 #include "netport.h"
 #include "objsec.h"
 
-#define SEL_NETPORT_HASH_SIZE       256
-#define SEL_NETPORT_HASH_BKT_LIMIT   16
+#define SEL_NETPORT_HASH_SIZE (1 << CONFIG_SECURITY_SELINUX_NETPORT_HASH_BITS)
+#define SEL_NETPORT_HASH_BKT_LIMIT CONFIG_SECURITY_SELINUX_NETPORT_HASH_BLIMIT
 
 struct sel_netport_bkt {
 	int size;
-- 
2.17.1

Re: [PATCH 0/9] SELinux: Improve hash functions and sizing of hash tables

[Paul Moore]

On Wed, Apr 8, 2020 at 2:24 PM <siarhei.liakh@concurrent-rt.com> wrote:
> From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
>
> This patch set is the result of an actual customer support case where a client
> of ours observed unacceptable variability of timings while sending UDP packets
> via sendto() with SELinux enabled. The initial investigation centered around
> kernel 3.10.108 in CentOS 6.5 environment. Combination of these patches with
> some substantial tuning of newly added Kconfig options was able to reduce
> *maximum* sendto() latency to about 160us, down from well over 2ms. Worst
> latency was typically observed when a new SSH login was initiated concurrently
> with the test program running a sendto() loop, thus causing an AVC miss with a
> subsequent call to security_compute_av(), which would spend most of its time
> iterating through policydb within context_struct_compute_av().
>
> The original patch set was developed for linux kernel 3.10.108 and later ported
> to newer versions. The patch set presented here is based off Linus' tree as of
> April 7, 2020 and contains only a subset of the changes which are still relevant
> to 5.6+ as many of the issues had already been addressed in different ways.
>
> The patch set consists of 9 patches total and is meant to achieve two goals:
> 1. Replace most local copies of custom hash functions with generic hash
>    functions already available in inlude/linux/*.h.
>
> 2. Replace hard-coded hash table sizing parameters with Kconfig tunables.
>
> "Advanced Hashing" Kconfig option is the only dependency between the patches,
> but other than that and any combination of them can be used.

I haven't yet looked at these patches in detail, but a few quick thoughts:

* I would be very curious to see what the performance improvement is
on a current kernel build from either selinux/next or Linus' tree.
Performance numbers from an extremely old commercial distribution
aren't of much interest to mainline development.

* In general I'm a fan of reducing the number of Kconfig options
whenever possible in favor of the system auto-tuning based on usage
(e.g. the loaded policy).  Obviously this isn't possible in some
cases, but I worry that there is always a risk that if we expose a
build knob there is a risk it will be mis-configured.  My initial
reaction is that this patch set exposes way too many things as Kconfig
knobs.  As an aside, I also worry about runtime tunables, but to a
much lesser extent (the risk is less, the benefits greater, etc.).

* The AVC hash table improvement doesn't exactly look like a
sea-change, have you tried it on multiple policies and work loads?  I
wonder if the small improvement you saw changes on different workloads
and/or policies.

* In general I agree with your statement about using common code, e.g.
hash functions, to improve code quality, maintenance, etc. but the
hashing functions you are replacing are rather trivial and easily
maintained.  Not to mention their performance in the SELinux code is a
well known quantity at this point.

I'll take a closer look at these patches, likely next week after the
merge window closes, but in the meantime if you could provide some
more current performance numbers with a better explanation of the
workloads I think it would be helpful.

Thank you.

-- 
paul moore
www.paul-moore.com

Re: [PATCH 0/9] SELinux: Improve hash functions and sizing of hash tables

[Siarhei Liakh]

The 04/09/2020 09:41, Paul Moore wrote:
> On Wed, Apr 8, 2020 at 2:24 PM <siarhei.liakh@concurrent-rt.com> wrote:
> > From: Siarhei Liakh <siarhei.liakh@concurrent-rt.com>
> >
> > This patch set is the result of an actual customer support case where a client
> > of ours observed unacceptable variability of timings while sending UDP packets
> > via sendto() with SELinux enabled. The initial investigation centered around
> > kernel 3.10.108 in CentOS 6.5 environment. Combination of these patches with
> > some substantial tuning of newly added Kconfig options was able to reduce
> > *maximum* sendto() latency to about 160us, down from well over 2ms. Worst
> > latency was typically observed when a new SSH login was initiated concurrently
> > with the test program running a sendto() loop, thus causing an AVC miss with a
> > subsequent call to security_compute_av(), which would spend most of its time
> > iterating through policydb within context_struct_compute_av().
> >
> > The original patch set was developed for linux kernel 3.10.108 and later ported
> > to newer versions. The patch set presented here is based off Linus' tree as of
> > April 7, 2020 and contains only a subset of the changes which are still relevant
> > to 5.6+ as many of the issues had already been addressed in different ways.
> >
> > The patch set consists of 9 patches total and is meant to achieve two goals:
> > 1. Replace most local copies of custom hash functions with generic hash
> >    functions already available in inlude/linux/*.h.
> >
> > 2. Replace hard-coded hash table sizing parameters with Kconfig tunables.
> >
> > "Advanced Hashing" Kconfig option is the only dependency between the patches,
> > but other than that and any combination of them can be used.
> 
> I haven't yet looked at these patches in detail, but a few quick thoughts:

Looks like I sent you a snapshot with a couple of minor porting errors before I
fixed them. You can still look at the patches since the errors do not change
the logic, just hold off on compiling. Apologies for the mix-up, I'll send out
another version soon.

Just wanted to provide some additional background so we can better understand
each other. I focus primarily on real-time aspects of the system, so pretty
much everything I write here has to be viewed in that context. For example,
while I would like to get average performance numbers improved, I am much more
concerned with extreme outliers. Such frame of thinking, to some degree, could
be considered similar to the primary reason why Linux prefers heapsort over
quicksort: while quicksort is faster on average, it also suffers from a
pathological worst-case scenario of O(n^2).

I understand that real-time Linux is a small niche. However, I do believe that
at least some of the changes I suggest would be useful to general public also.
Although I would be really happy if my patches were to get accepted, I think
of them more as conversation starters rather than actual finished product.

> * I would be very curious to see what the performance improvement is
> on a current kernel build from either selinux/next or Linus' tree.

I've got a Fedora 32 beta box installed, so I will get some benchmark numbers
for Linus' tree with default F32 policies soon.

> Performance numbers from an extremely old commercial distribution
> aren't of much interest to mainline development.

I get that. My point is that some of the inefficiencies (at least from my
standpoint) had been in the kernel for a long time and are still there today.
As much as I'd love to get our clients off ancient release, they have their
own reasons to use it, thus fixing my point of reference to something old.
 
> * In general I'm a fan of reducing the number of Kconfig options
> whenever possible in favor of the system auto-tuning based on usage
> (e.g. the loaded policy).  Obviously this isn't possible in some
> cases, but I worry that there is always a risk that if we expose a
> build knob there is a risk it will be mis-configured.  My initial
> reaction is that this patch set exposes way too many things as Kconfig
> knobs.  As an aside, I also worry about runtime tunables, but to a
> much lesser extent (the risk is less, the benefits greater, etc.).

Sure. My point is that hardcoded sizing is inconvenient so it would be nice
to fix it in some way. Moving stuff into Kconfig was the easiest way to do
it in my case, but I am open to better suggestions.

> * The AVC hash table improvement doesn't exactly look like a
> sea-change, 

Correct. However, old hash reliably produces about 40% collision rate while
a new one has distribution which is demonstrably better and it gets even more
so with liarger number of buckets (which, admittedly, is not necessarily what
a typical end-user would use).

> have you tried it on multiple policies and work loads?  I
> wonder if the small improvement you saw changes on different workloads
> and/or policies.

I am not an expert on SELinux (be that kernel or usersace side of business),
so I make do whith what is readily available to me: whatever comes with
the distribuition by default (meaning Targeted policy from CentOS), or
whatever a client is willing to provide us (if anything at all). Further,
as our client had discovered issues under particular workload, that is the
one I am using to benchmark my fixes. That said, I am willing to run a
better test suite if you have one ready.

> * In general I agree with your statement about using common code, e.g.
> hash functions, to improve code quality, maintenance, etc. but the
> hashing functions you are replacing are rather trivial and easily
> maintained.  Not to mention their performance in the SELinux code is a
> well known quantity at this point.

Here is my take on it: proper hash functions are just as hard to come up
with as locking and encryption schemes. Please consider following three points:

1. In 2006 Thomas Gleixner discovered that standard known-good hash_64()
is actually not that good. A very interesting discussion followed:
https://lwn.net/Articles/687494/
https://lore.kernel.org/lkml/20160428163525.495514517@linutronix.de/
https://lore.kernel.org/lkml/20160430205235.24232.qmail@ns.horizon.com/

2. A simple custom hash had already been deemed inadequate and replaced in
avtab.c with (unfortunately) a custom version of known good generic hash:
commit 33ebc1932a07efd8728975750409741940334489
Author: John Brooks <john.brooks@jolla.com>
Date:   Tue Mar 24 16:54:17 2015 -0400

3. We already have at least three ways to do essentially the same thing:

/* _OLD_ AVTab hash - see point #2 above */
static inline int avtab_hash(struct avtab_key *keyp, u32 mask)
{
       return ((keyp->target_class + (keyp->target_type << 2) +
                (keyp->source_type << 9)) & mask);
}

static u32 rangetr_hash(struct hashtab *h, const void *k)
{
        const struct range_trans *key = k;

        return (key->source_type + (key->target_type << 3) +
                (key->target_class << 5)) & (h->size - 1);
}

static inline int avc_hash(u32 ssid, u32 tsid, u16 tclass)
{
        return (ssid ^ (tsid<<2) ^ (tclass<<4)) & (AVC_CACHE_SLOTS - 1);
}

Yet another local copy of a simple custom hash is already being suggested for
future use in SELinux:

+static u32 role_trans_hash(struct hashtab *h, const void *k)
+{
+	const struct role_trans_key *key = k;
+
+	return (key->role + (key->type << 3) + (key->tclass << 5)) &
+		(h->size - 1);
+}

https://lore.kernel.org/selinux/20200407182858.1149087-1-omosnace@redhat.com/

So, as a kernel developer looking at SELinux for the first time in attempt to
resolve a real issue for a real custoer, I have the following questions:
- Why do we need so many ways to hash 3x 32-bit values?
- Why avtab hash was deemed to be bad, but not the other ones? Was it due to
unfortunate chice of shift constants?
- Why avc hash is using XOR while rangetr is using addition? Why shift (2, 4)
vs (3, 5)?
- Why not just use known-good jhash_3words() everywhere and be done with it?

> I'll take a closer look at these patches, likely next week after the
> merge window closes, but in the meantime if you could provide some
> more current performance numbers with a better explanation of the
> workloads I think it would be helpful.

Thank you for making time for this. I'll get you some numbers.
I really hope a better Linux for everyone will come out of this.

Thank you!
-- 
Siarhei Liakh
Concurrent Real-Time

Re: [PATCH 0/9] SELinux: Improve hash functions and sizing of hash tables

[Paul Moore]

On Mon, Apr 13, 2020 at 4:43 PM Siarhei Liakh
<siarhei.liakh@concurrent-rt.com> wrote:
> Looks like I sent you a snapshot with a couple of minor porting errors before I
> fixed them. You can still look at the patches since the errors do not change
> the logic, just hold off on compiling. Apologies for the mix-up, I'll send out
> another version soon.

...

> I've got a Fedora 32 beta box installed, so I will get some benchmark numbers
> for Linus' tree with default F32 policies soon.

Okay, once you've got some updated numbers and a revised patchset we
can revisit this.

-- 
paul moore
www.paul-moore.com

Re: [PATCH 0/9] SELinux: Improve hash functions and sizing of hash tables

[Siarhei Liakh]

The 04/14/2020 17:50, Paul Moore wrote:
> On Mon, Apr 13, 2020 at 4:43 PM Siarhei Liakh
> <siarhei.liakh@concurrent-rt.com> wrote:
> > Looks like I sent you a snapshot with a couple of minor porting errors before I
> > fixed them. You can still look at the patches since the errors do not change
> > the logic, just hold off on compiling. Apologies for the mix-up, I'll send out
> > another version soon.
> 
> ...
> 
> > I've got a Fedora 32 beta box installed, so I will get some benchmark numbers
> > for Linus' tree with default F32 policies soon.
> 
> Okay, once you've got some updated numbers and a revised patchset we
> can revisit this.

I've posted a revised patch set here:
https://lore.kernel.org/selinux/20200429202941.18320-1-siarhei.liakh@concurrent-rt.com/

Please let me knwo what you think.
Thank you!

-- 
Siarhei Liakh
Concurrent Real-Time