[PATCH 0/3] Improve check_assertions performance through hash tweaks

[PATCH 0/3] Improve check_assertions performance through hash tweaks

[John Brooks]

These changes improve the performance of libsepol's avtab as used by
check_assertions, especially for large policies. On Fedora, this reduces
the time to check assertions from over an hour (I never finished!) to
about 3 minutes.

There is a lot more low-hanging performance fruit here, but this makes
a decent start - and it should allow these assertions to be enabled as
part of the policy build again.

John Brooks (3):
  Build libsepol with -O2
  Use a better hash function for libsepol's avtab
  Tweak avtab hash table parameters for better performance

 libsepol/include/sepol/policydb/avtab.h |  4 ++--
 libsepol/src/Makefile                   |  2 +-
 libsepol/src/avtab.c                    | 39 ++++++++++++++++++++++++++++-----
 3 files changed, 36 insertions(+), 9 deletions(-)

-- 
1.9.3

[PATCH 1/3] Build libsepol with -O2

[John Brooks]

libsepol contains performance sensitive code; in particular, compiler
optimizations save a few minutes off of the optimized policydb hash
tables.
---
 libsepol/src/Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/libsepol/src/Makefile b/libsepol/src/Makefile
index 6450d67..059f198 100644
--- a/libsepol/src/Makefile
+++ b/libsepol/src/Makefile
@@ -22,7 +22,7 @@ OBJS= $(patsubst %.c,%.o,$(wildcard *.c))
 LOBJS= $(patsubst %.c,%.lo,$(wildcard *.c))
 CFLAGS ?= -Werror -Wall -W -Wundef -Wshadow -Wmissing-format-attribute
 
-override CFLAGS += -I. -I../include -D_GNU_SOURCE
+override CFLAGS += -I. -I../include -D_GNU_SOURCE -O2
 
 ifneq ($(DISABLE_CIL),y)
 OBJS += $(sort $(patsubst %.c,%.o,$(wildcard $(CILDIR)/src/*.c) $(CIL_GENERATED)))
-- 
1.9.3

Re: [PATCH 1/3] Build libsepol with -O2

[Stephen Smalley]

On 01/07/2015 05:03 PM, John Brooks wrote:
> libsepol contains performance sensitive code; in particular, compiler
> optimizations save a few minutes off of the optimized policydb hash
> tables.
> ---
>  libsepol/src/Makefile | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/libsepol/src/Makefile b/libsepol/src/Makefile
> index 6450d67..059f198 100644
> --- a/libsepol/src/Makefile
> +++ b/libsepol/src/Makefile
> @@ -22,7 +22,7 @@ OBJS= $(patsubst %.c,%.o,$(wildcard *.c))
>  LOBJS= $(patsubst %.c,%.lo,$(wildcard *.c))
>  CFLAGS ?= -Werror -Wall -W -Wundef -Wshadow -Wmissing-format-attribute
>  
> -override CFLAGS += -I. -I../include -D_GNU_SOURCE
> +override CFLAGS += -I. -I../include -D_GNU_SOURCE -O2
>  
>  ifneq ($(DISABLE_CIL),y)
>  OBJS += $(sort $(patsubst %.c,%.o,$(wildcard $(CILDIR)/src/*.c) $(CIL_GENERATED)))
> 

Not sure we want this to always be set even if the caller specified
their own set of CFLAGS on the make command-line.

[PATCH 2/3] Use a better hash function for libsepol's avtab

[John Brooks]

This function, based on murmurhash3, has much better distribution than
the original. Using the current default of 4096 buckets, there are many
fewer collisions:

Before:
2893000 entries and 4096/4096 buckets used, longest chain length 1649
After:
2732000 entries and 4096/4096 buckets used, longest chain length 764

The difference becomes much more significant when buckets are increased.
A naive attempt to expand the current function to larger outputs doesn't
yield any significant improvement; so this function is a prerequisite
for increasing the bucket size.
---
 libsepol/src/avtab.c | 35 ++++++++++++++++++++++++++++++++---
 1 file changed, 32 insertions(+), 3 deletions(-)

diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
index ea947cb..9c01a8d 100644
--- a/libsepol/src/avtab.c
+++ b/libsepol/src/avtab.c
@@ -49,10 +49,39 @@
 #include "debug.h"
 #include "private.h"
 
-static inline int avtab_hash(struct avtab_key *keyp, uint16_t mask)
+/* Based on MurmurHash3, written by Austin Appleby and placed in the
+ * public domain.
+ */
+static inline int avtab_hash(struct avtab_key *keyp, uint32_t mask)
 {
-	return ((keyp->target_class + (keyp->target_type << 2) +
-		 (keyp->source_type << 9)) & mask);
+	uint32_t h1 = 0;
+
+	const uint32_t c1 = 0xcc9e2d51;
+	const uint32_t c2 = 0x1b873593;
+
+#define mix(n) { \
+	uint32_t k1 = n; \
+	k1 *= c1; \
+	k1 = (k1 << 15) | (k1 >> (32 - 15)); \
+	k1 *= c2; \
+	h1 ^= k1; \
+	h1 = (h1 << 13) | (h1 >> (32 - 13)); \
+	h1 = h1*5+0xe6546b64; \
+}
+
+	mix(keyp->target_class);
+	mix(keyp->target_type);
+	mix(keyp->source_type);
+
+#undef mix
+
+	h1 ^= h1 >> 16;
+	h1 *= 0x85ebca6b;
+	h1 ^= h1 >> 13;
+	h1 *= 0xc2b2ae35;
+	h1 ^= h1 >> 16;
+
+	return h1 & mask;
 }
 
 static avtab_ptr_t
-- 
1.9.3

Re: [PATCH 2/3] Use a better hash function for libsepol's avtab

[Stephen Smalley]

On 01/07/2015 05:03 PM, John Brooks wrote:
> This function, based on murmurhash3, has much better distribution than
> the original. Using the current default of 4096 buckets, there are many
> fewer collisions:
> 
> Before:
> 2893000 entries and 4096/4096 buckets used, longest chain length 1649
> After:
> 2732000 entries and 4096/4096 buckets used, longest chain length 764
> 
> The difference becomes much more significant when buckets are increased.
> A naive attempt to expand the current function to larger outputs doesn't
> yield any significant improvement; so this function is a prerequisite
> for increasing the bucket size.
> ---
>  libsepol/src/avtab.c | 35 ++++++++++++++++++++++++++++++++---
>  1 file changed, 32 insertions(+), 3 deletions(-)
> 
> diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
> index ea947cb..9c01a8d 100644
> --- a/libsepol/src/avtab.c
> +++ b/libsepol/src/avtab.c
> @@ -49,10 +49,39 @@
>  #include "debug.h"
>  #include "private.h"
>  
> -static inline int avtab_hash(struct avtab_key *keyp, uint16_t mask)
> +/* Based on MurmurHash3, written by Austin Appleby and placed in the
> + * public domain.
> + */
> +static inline int avtab_hash(struct avtab_key *keyp, uint32_t mask)
>  {
> -	return ((keyp->target_class + (keyp->target_type << 2) +
> -		 (keyp->source_type << 9)) & mask);
> +	uint32_t h1 = 0;
> +
> +	const uint32_t c1 = 0xcc9e2d51;
> +	const uint32_t c2 = 0x1b873593;
> +
> +#define mix(n) { \
> +	uint32_t k1 = n; \
> +	k1 *= c1; \
> +	k1 = (k1 << 15) | (k1 >> (32 - 15)); \
> +	k1 *= c2; \
> +	h1 ^= k1; \
> +	h1 = (h1 << 13) | (h1 >> (32 - 13)); \
> +	h1 = h1*5+0xe6546b64; \
> +}
> +
> +	mix(keyp->target_class);
> +	mix(keyp->target_type);
> +	mix(keyp->source_type);
> +
> +#undef mix
> +
> +	h1 ^= h1 >> 16;
> +	h1 *= 0x85ebca6b;
> +	h1 ^= h1 >> 13;
> +	h1 *= 0xc2b2ae35;
> +	h1 ^= h1 >> 16;
> +
> +	return h1 & mask;
>  }
>  
>  static avtab_ptr_t
> 

Thanks, this looks like a significant improvement for neverallow
checking.  I'm trying to make sure I understand what if any implications
it has for other uses of the avtab, since the neverallow checker is
unusual in that it fully expands all entries.

On Fedora 20 policy, checkpolicy -Mb
/etc/selinux/targeted/policy/policy.29 before and after this patch (with
avtabh_hash_eval called) shows:

before.txt:rules:  101401 entries and 8169/8192 buckets used, longest
chain length 84
betterhash.txt:rules:  101401 entries and 8192/8192 buckets used,
longest chain length 27

So that's a definite improvement.

Could you amend your code to define constants for the various magic
values used above?  Thanks.

Re: [PATCH 2/3] Use a better hash function for libsepol's avtab

[John Brooks]

On Jan 12, 2015, at 10:30 AM, Stephen Smalley <sds@tycho.nsa.gov> wrote:
> 
> On 01/07/2015 05:03 PM, John Brooks wrote:
>> This function, based on murmurhash3, has much better distribution than
>> the original. Using the current default of 4096 buckets, there are many
>> fewer collisions:
> 
> Thanks, this looks like a significant improvement for neverallow
> checking.  I'm trying to make sure I understand what if any implications
> it has for other uses of the avtab, since the neverallow checker is
> unusual in that it fully expands all entries.
> 
> On Fedora 20 policy, checkpolicy -Mb
> /etc/selinux/targeted/policy/policy.29 before and after this patch (with
> avtabh_hash_eval called) shows:
> 
> before.txt:rules:  101401 entries and 8169/8192 buckets used, longest
> chain length 84
> betterhash.txt:rules:  101401 entries and 8192/8192 buckets used,
> longest chain length 27
> 
> So that's a definite improvement.
> 
> Could you amend your code to define constants for the various magic
> values used above?  Thanks.

The magic values are nothing but magic from the original murmurhash3. They don’t have any useful names. I did remove ‘c1’ and ‘c2’ in favor of using their values inline, since each is only used once. Is that enough?

(Also, sorry for my last mail to this list; it was butchered by my mail client. Hopefully this one works.)

Re: [PATCH 2/3] Use a better hash function for libsepol's avtab

[Stephen Smalley]

On 01/12/2015 08:38 PM, John Brooks wrote:
> On Jan 12, 2015, at 10:30 AM, Stephen Smalley <sds@tycho.nsa.gov> wrote:
>>
>> On 01/07/2015 05:03 PM, John Brooks wrote:
>>> This function, based on murmurhash3, has much better distribution than
>>> the original. Using the current default of 4096 buckets, there are many
>>> fewer collisions:
>>
>> Thanks, this looks like a significant improvement for neverallow
>> checking.  I'm trying to make sure I understand what if any implications
>> it has for other uses of the avtab, since the neverallow checker is
>> unusual in that it fully expands all entries.
>>
>> On Fedora 20 policy, checkpolicy -Mb
>> /etc/selinux/targeted/policy/policy.29 before and after this patch (with
>> avtabh_hash_eval called) shows:
>>
>> before.txt:rules:  101401 entries and 8169/8192 buckets used, longest
>> chain length 84
>> betterhash.txt:rules:  101401 entries and 8192/8192 buckets used,
>> longest chain length 27
>>
>> So that's a definite improvement.
>>
>> Could you amend your code to define constants for the various magic
>> values used above?  Thanks.
> 
> The magic values are nothing but magic from the original murmurhash3. They don’t have any useful names. I did remove ‘c1’ and ‘c2’ in favor of using their values inline, since each is only used once. Is that enough?
> 
> (Also, sorry for my last mail to this list; it was butchered by my mail client. Hopefully this one works.)

Not sure what source you are using for murmurhash3, but the algorithm
from http://en.wikipedia.org/wiki/MurmurHash seems to define and use
symbolic names for most of the constants.  They aren't especially
meaningful but they help with readability, especially for the ones that
are used more than once in the algorithm.

[PATCH 3/3] Tweak avtab hash table parameters for better performance

[John Brooks]

Using the Fedora 20 targeted policy, running check_assertions requires
an avtab with around 22 million elements. With the default limit of 4096
buckets, performance is abysmal: it takes more than an hour to populate
the hash. Profiling shows most of that time under avtab_search_node.

This patch increases the hash from 13 to 20 bits and to a maximum of
1048576 buckets. The time for check_assertions on that policy is reduced
to about 3 minutes, which is enough to re-enable those checks as part of
the build process.

A full size table will allocate 4-8 MB of memory, up from 16-32 KB. In a
cursory review, these tables are usually short-lived and only 1-3 are
allocated together. Compared to the cost of entries in this table (up to
1 GB using the same policy), this isn't a significant increase.
---
 libsepol/include/sepol/policydb/avtab.h | 4 ++--
 libsepol/src/avtab.c                    | 4 +---
 2 files changed, 3 insertions(+), 5 deletions(-)

diff --git a/libsepol/include/sepol/policydb/avtab.h b/libsepol/include/sepol/policydb/avtab.h
index 6955ecf..158112f 100644
--- a/libsepol/include/sepol/policydb/avtab.h
+++ b/libsepol/include/sepol/policydb/avtab.h
@@ -81,7 +81,7 @@ typedef struct avtab {
 	avtab_ptr_t *htable;
 	uint32_t nel;		/* number of elements */
 	uint32_t nslot;         /* number of hash slots */
-	uint16_t mask;          /* mask to compute hash func */
+	uint32_t mask;          /* mask to compute hash func */
 } avtab_t;
 
 extern int avtab_init(avtab_t *);
@@ -117,7 +117,7 @@ extern avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key);
 
 extern avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified);
 
-#define MAX_AVTAB_HASH_BITS 13
+#define MAX_AVTAB_HASH_BITS 20
 #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
 #define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
 #define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
index 9c01a8d..65b3c48 100644
--- a/libsepol/src/avtab.c
+++ b/libsepol/src/avtab.c
@@ -329,7 +329,7 @@ int avtab_init(avtab_t * h)
 
 int avtab_alloc(avtab_t *h, uint32_t nrules)
 {
-	uint16_t mask = 0;
+	uint32_t mask = 0;
 	uint32_t shift = 0;
 	uint32_t work = nrules;
 	uint32_t nslot = 0;
@@ -341,8 +341,6 @@ int avtab_alloc(avtab_t *h, uint32_t nrules)
 		work  = work >> 1;
 		shift++;
 	}
-	if (shift > 2)
-		shift = shift - 2;
 	nslot = 1 << shift;
 	if (nslot > MAX_AVTAB_SIZE)
 		nslot = MAX_AVTAB_SIZE;
-- 
1.9.3

Re: [PATCH 3/3] Tweak avtab hash table parameters for better performance

[Stephen Smalley]

On 01/07/2015 05:03 PM, John Brooks wrote:
> Using the Fedora 20 targeted policy, running check_assertions requires
> an avtab with around 22 million elements. With the default limit of 4096
> buckets, performance is abysmal: it takes more than an hour to populate
> the hash. Profiling shows most of that time under avtab_search_node.
> 
> This patch increases the hash from 13 to 20 bits and to a maximum of
> 1048576 buckets. The time for check_assertions on that policy is reduced
> to about 3 minutes, which is enough to re-enable those checks as part of
> the build process.
> 
> A full size table will allocate 4-8 MB of memory, up from 16-32 KB. In a
> cursory review, these tables are usually short-lived and only 1-3 are
> allocated together. Compared to the cost of entries in this table (up to
> 1 GB using the same policy), this isn't a significant increase.
> ---
>  libsepol/include/sepol/policydb/avtab.h | 4 ++--
>  libsepol/src/avtab.c                    | 4 +---
>  2 files changed, 3 insertions(+), 5 deletions(-)
> 
> diff --git a/libsepol/include/sepol/policydb/avtab.h b/libsepol/include/sepol/policydb/avtab.h
> index 6955ecf..158112f 100644
> --- a/libsepol/include/sepol/policydb/avtab.h
> +++ b/libsepol/include/sepol/policydb/avtab.h
> @@ -81,7 +81,7 @@ typedef struct avtab {
>  	avtab_ptr_t *htable;
>  	uint32_t nel;		/* number of elements */
>  	uint32_t nslot;         /* number of hash slots */
> -	uint16_t mask;          /* mask to compute hash func */
> +	uint32_t mask;          /* mask to compute hash func */
>  } avtab_t;
>  
>  extern int avtab_init(avtab_t *);
> @@ -117,7 +117,7 @@ extern avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key);
>  
>  extern avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified);
>  
> -#define MAX_AVTAB_HASH_BITS 13
> +#define MAX_AVTAB_HASH_BITS 20
>  #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
>  #define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
>  #define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
> diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
> index 9c01a8d..65b3c48 100644
> --- a/libsepol/src/avtab.c
> +++ b/libsepol/src/avtab.c
> @@ -329,7 +329,7 @@ int avtab_init(avtab_t * h)
>  
>  int avtab_alloc(avtab_t *h, uint32_t nrules)
>  {
> -	uint16_t mask = 0;
> +	uint32_t mask = 0;
>  	uint32_t shift = 0;
>  	uint32_t work = nrules;
>  	uint32_t nslot = 0;
> @@ -341,8 +341,6 @@ int avtab_alloc(avtab_t *h, uint32_t nrules)
>  		work  = work >> 1;
>  		shift++;
>  	}
> -	if (shift > 2)
> -		shift = shift - 2;
>  	nslot = 1 << shift;
>  	if (nslot > MAX_AVTAB_SIZE)
>  		nslot = MAX_AVTAB_SIZE;
> 

Here again, looking at impact on regular usage of the avtab (without
full expansion of all attributes), running checkpolicy -Mb
/etc/selinux/targeted/policy/policy.29 on Fedora 20 before and after
this patch, I see:

before.txt:rules:  101401 entries and 8169/8192 buckets used, longest
chain length 84

betterhash.txt:rules:  101401 entries and 8192/8192 buckets used,
longest chain length 27

tweakavtab.txt:rules:  101401 entries and 68460/131072 buckets used,
longest chain length 7

Seems like we're wasting a large number of buckets in that scenario.

Also, in the corresponding kernel code (security/selinux/ss/avtab.[hc]),
we've actually shrunk the hash bits from 13 to 11,

commit 6c9ff1013b7a21099da838eeef7c3f23ee347957
Author: Stephen Smalley <sds@tycho.nsa.gov>
Date:   Mon Mar 15 10:42:11 2010 -0400

    SELinux: Reduce max avtab size to avoid page allocation failures

    Reduce MAX_AVTAB_HASH_BITS so that the avtab allocation is an order 2
    allocation rather than an order 4 allocation on x86_64.  This
    addresses reports of page allocation failures:
    http://marc.info/?l=selinux&m=126757230625867&w=2
    https://bugzilla.redhat.com/show_bug.cgi?id=570433

    Reported-by:  Russell Coker <russell@coker.com.au>
    Signed-off-by:  Stephen D. Smalley <sds@tycho.nsa.gov>
    Acked-by: Eric Paris <eparis@redhat.com>
    Signed-off-by: James Morris <jmorris@namei.org>

That doesn't necessarily mean we can't increase it in libsepol, but
something to be aware of.  Of course the kernel never expands the rules
so it doesn't have this issue.

I've also considered reworking the libsepol check_assertions() code to
not expand the avtab in order to provide better traceback to the
original source allow rule that violated the neverallow.  This would
require more work by check_assertion_helper to check each attribute
associated with the source and target, just as with
context_struct_compute_av.

Re: [PATCH 3/3] Tweak avtab hash table parameters for better performance

[Stephen Smalley]

On 01/12/2015 12:47 PM, Stephen Smalley wrote:
> On 01/07/2015 05:03 PM, John Brooks wrote:
>> Using the Fedora 20 targeted policy, running check_assertions requires
>> an avtab with around 22 million elements. With the default limit of 4096
>> buckets, performance is abysmal: it takes more than an hour to populate
>> the hash. Profiling shows most of that time under avtab_search_node.
>>
>> This patch increases the hash from 13 to 20 bits and to a maximum of
>> 1048576 buckets. The time for check_assertions on that policy is reduced
>> to about 3 minutes, which is enough to re-enable those checks as part of
>> the build process.
>>
>> A full size table will allocate 4-8 MB of memory, up from 16-32 KB. In a
>> cursory review, these tables are usually short-lived and only 1-3 are
>> allocated together. Compared to the cost of entries in this table (up to
>> 1 GB using the same policy), this isn't a significant increase.
>> ---
>>  libsepol/include/sepol/policydb/avtab.h | 4 ++--
>>  libsepol/src/avtab.c                    | 4 +---
>>  2 files changed, 3 insertions(+), 5 deletions(-)
>>
>> diff --git a/libsepol/include/sepol/policydb/avtab.h b/libsepol/include/sepol/policydb/avtab.h
>> index 6955ecf..158112f 100644
>> --- a/libsepol/include/sepol/policydb/avtab.h
>> +++ b/libsepol/include/sepol/policydb/avtab.h
>> @@ -81,7 +81,7 @@ typedef struct avtab {
>>  	avtab_ptr_t *htable;
>>  	uint32_t nel;		/* number of elements */
>>  	uint32_t nslot;         /* number of hash slots */
>> -	uint16_t mask;          /* mask to compute hash func */
>> +	uint32_t mask;          /* mask to compute hash func */
>>  } avtab_t;
>>  
>>  extern int avtab_init(avtab_t *);
>> @@ -117,7 +117,7 @@ extern avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key);
>>  
>>  extern avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified);
>>  
>> -#define MAX_AVTAB_HASH_BITS 13
>> +#define MAX_AVTAB_HASH_BITS 20
>>  #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
>>  #define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
>>  #define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
>> diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
>> index 9c01a8d..65b3c48 100644
>> --- a/libsepol/src/avtab.c
>> +++ b/libsepol/src/avtab.c
>> @@ -329,7 +329,7 @@ int avtab_init(avtab_t * h)
>>  
>>  int avtab_alloc(avtab_t *h, uint32_t nrules)
>>  {
>> -	uint16_t mask = 0;
>> +	uint32_t mask = 0;
>>  	uint32_t shift = 0;
>>  	uint32_t work = nrules;
>>  	uint32_t nslot = 0;
>> @@ -341,8 +341,6 @@ int avtab_alloc(avtab_t *h, uint32_t nrules)
>>  		work  = work >> 1;
>>  		shift++;
>>  	}
>> -	if (shift > 2)
>> -		shift = shift - 2;
>>  	nslot = 1 << shift;
>>  	if (nslot > MAX_AVTAB_SIZE)
>>  		nslot = MAX_AVTAB_SIZE;
>>
> 
> Here again, looking at impact on regular usage of the avtab (without
> full expansion of all attributes), running checkpolicy -Mb
> /etc/selinux/targeted/policy/policy.29 on Fedora 20 before and after
> this patch, I see:
> 
> before.txt:rules:  101401 entries and 8169/8192 buckets used, longest
> chain length 84
> 
> betterhash.txt:rules:  101401 entries and 8192/8192 buckets used,
> longest chain length 27
> 
> tweakavtab.txt:rules:  101401 entries and 68460/131072 buckets used,
> longest chain length 7
> 
> Seems like we're wasting a large number of buckets in that scenario.
> 
> Also, in the corresponding kernel code (security/selinux/ss/avtab.[hc]),
> we've actually shrunk the hash bits from 13 to 11,
> 
> commit 6c9ff1013b7a21099da838eeef7c3f23ee347957
> Author: Stephen Smalley <sds@tycho.nsa.gov>
> Date:   Mon Mar 15 10:42:11 2010 -0400
> 
>     SELinux: Reduce max avtab size to avoid page allocation failures
> 
>     Reduce MAX_AVTAB_HASH_BITS so that the avtab allocation is an order 2
>     allocation rather than an order 4 allocation on x86_64.  This
>     addresses reports of page allocation failures:
>     http://marc.info/?l=selinux&m=126757230625867&w=2
>     https://bugzilla.redhat.com/show_bug.cgi?id=570433
> 
>     Reported-by:  Russell Coker <russell@coker.com.au>
>     Signed-off-by:  Stephen D. Smalley <sds@tycho.nsa.gov>
>     Acked-by: Eric Paris <eparis@redhat.com>
>     Signed-off-by: James Morris <jmorris@namei.org>
> 
> That doesn't necessarily mean we can't increase it in libsepol, but
> something to be aware of.  Of course the kernel never expands the rules
> so it doesn't have this issue.
> 
> I've also considered reworking the libsepol check_assertions() code to
> not expand the avtab in order to provide better traceback to the
> original source allow rule that violated the neverallow.  This would
> require more work by check_assertion_helper to check each attribute
> associated with the source and target, just as with
> context_struct_compute_av.

Might also want to consider taking the ebitmap scanning optimization
done in the kernel to libsepol.  That would help with the
ebitmap_for_each_bit() loops.

Re: [PATCH 3/3] Tweak avtab hash table parameters for better performance

[Stephen Smalley]

On 01/12/2015 12:47 PM, Stephen Smalley wrote:
> On 01/07/2015 05:03 PM, John Brooks wrote:
>> Using the Fedora 20 targeted policy, running check_assertions requires
>> an avtab with around 22 million elements. With the default limit of 4096
>> buckets, performance is abysmal: it takes more than an hour to populate
>> the hash. Profiling shows most of that time under avtab_search_node.
>>
>> This patch increases the hash from 13 to 20 bits and to a maximum of
>> 1048576 buckets. The time for check_assertions on that policy is reduced
>> to about 3 minutes, which is enough to re-enable those checks as part of
>> the build process.
>>
>> A full size table will allocate 4-8 MB of memory, up from 16-32 KB. In a
>> cursory review, these tables are usually short-lived and only 1-3 are
>> allocated together. Compared to the cost of entries in this table (up to
>> 1 GB using the same policy), this isn't a significant increase.
>> ---
>>  libsepol/include/sepol/policydb/avtab.h | 4 ++--
>>  libsepol/src/avtab.c                    | 4 +---
>>  2 files changed, 3 insertions(+), 5 deletions(-)
>>
>> diff --git a/libsepol/include/sepol/policydb/avtab.h b/libsepol/include/sepol/policydb/avtab.h
>> index 6955ecf..158112f 100644
>> --- a/libsepol/include/sepol/policydb/avtab.h
>> +++ b/libsepol/include/sepol/policydb/avtab.h
>> @@ -81,7 +81,7 @@ typedef struct avtab {
>>  	avtab_ptr_t *htable;
>>  	uint32_t nel;		/* number of elements */
>>  	uint32_t nslot;         /* number of hash slots */
>> -	uint16_t mask;          /* mask to compute hash func */
>> +	uint32_t mask;          /* mask to compute hash func */
>>  } avtab_t;
>>  
>>  extern int avtab_init(avtab_t *);
>> @@ -117,7 +117,7 @@ extern avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key);
>>  
>>  extern avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified);
>>  
>> -#define MAX_AVTAB_HASH_BITS 13
>> +#define MAX_AVTAB_HASH_BITS 20
>>  #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
>>  #define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
>>  #define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
>> diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
>> index 9c01a8d..65b3c48 100644
>> --- a/libsepol/src/avtab.c
>> +++ b/libsepol/src/avtab.c
>> @@ -329,7 +329,7 @@ int avtab_init(avtab_t * h)
>>  
>>  int avtab_alloc(avtab_t *h, uint32_t nrules)
>>  {
>> -	uint16_t mask = 0;
>> +	uint32_t mask = 0;
>>  	uint32_t shift = 0;
>>  	uint32_t work = nrules;
>>  	uint32_t nslot = 0;
>> @@ -341,8 +341,6 @@ int avtab_alloc(avtab_t *h, uint32_t nrules)
>>  		work  = work >> 1;
>>  		shift++;
>>  	}
>> -	if (shift > 2)
>> -		shift = shift - 2;
>>  	nslot = 1 << shift;
>>  	if (nslot > MAX_AVTAB_SIZE)
>>  		nslot = MAX_AVTAB_SIZE;
>>
> 
> Here again, looking at impact on regular usage of the avtab (without
> full expansion of all attributes), running checkpolicy -Mb
> /etc/selinux/targeted/policy/policy.29 on Fedora 20 before and after
> this patch, I see:
> 
> before.txt:rules:  101401 entries and 8169/8192 buckets used, longest
> chain length 84
> 
> betterhash.txt:rules:  101401 entries and 8192/8192 buckets used,
> longest chain length 27
> 
> tweakavtab.txt:rules:  101401 entries and 68460/131072 buckets used,
> longest chain length 7

Trying this on the Android policy, I get:
before.txt:rules:  6033 entries and 1811/2048 buckets used, longest
chain length 25

betterhash.txt:rules:  6033 entries and 1923/2048 buckets used, longest
chain length 11

tweakavtab.txt:rules:  6033 entries and 4232/8192 buckets used, longest
chain length 6

Also makes sepolicy-analyze neverallow feasible on Fedora policy;
previously I could only run it on Android policy and expect it to
complete in a sane amount of time.

Re: [PATCH 3/3] Tweak avtab hash table parameters for better performance

[John Brooks]

[-- Attachment #1: Type: text/plain, Size: 2336 bytes --]

On Jan 12, 2015, at 10:47 AM, Stephen Smalley <sds@tycho.nsa.gov<mailto:sds@tycho.nsa.gov>> wrote:

On 01/07/2015 05:03 PM, John Brooks wrote:
@@ -341,8 +341,6 @@ int avtab_alloc(avtab_t *h, uint32_t nrules)
work  = work >> 1;
shift++;
}
- if (shift > 2)
- shift = shift - 2;
nslot = 1 << shift;
if (nslot > MAX_AVTAB_SIZE)
nslot = MAX_AVTAB_SIZE;


tweakavtab.txt:rules:  101401 entries and 68460/131072 buckets used,
longest chain length 7

Seems like we're wasting a large number of buckets in that scenario.

Good catch. It looks like this is caused by the segment I highlighted above, removing the shift adjustment.

changed-nslot.txt:rules:  100967 entries and 68321/131072 buckets used, longest chain length 8
original-nslot.txt:rules:  100967 entries and 31017/32768 buckets used, longest chain length 13

So, one bucket is allocated per 2-4 elements. The change I actually wanted to make is to the definition of MAX_AVTAB_SIZE: it should be 2x MAX_AVTAB_HASH_BUCKETS to allow allocating a hash with maximum buckets, and that nslot bounding should use MAX_AVTAB_HASH_BUCKETS.


Also, in the corresponding kernel code (security/selinux/ss/avtab.[hc]),
we've actually shrunk the hash bits from 13 to 11,

Interesting. I wonder what the kernel hash eval looks like - it might benefit from a better hash function as well.


I've also considered reworking the libsepol check_assertions() code to
not expand the avtab in order to provide better traceback to the
original source allow rule that violated the neverallow.  This would
require more work by check_assertion_helper to check each attribute
associated with the source and target, just as with
context_struct_compute_av.

Yeah; I expect there is a lot of room for algorithmic improvement here. I wish I had time to understand and fix it. We could probably get this running on the order of seconds instead of minutes, and using _much_ less memory.

Even after these patches, expand_module spends 60% in avtab_search_node (and 13% malloc_consolidate, the rest is trivial). Next step would be to reduce the number of elements or lookups.

One interesting note: this fully expanded table is built twice under expand_module, for hierarchy_check_constraints and check_assertions. We could cut runtime almost in half by reusing the table.

[-- Attachment #2: Type: text/html, Size: 14040 bytes --]

Re: [PATCH 3/3] Tweak avtab hash table parameters for better performance

[Stephen Smalley]

On 01/12/2015 08:25 PM, John Brooks wrote:
> On Jan 12, 2015, at 10:47 AM, Stephen Smalley <sds@tycho.nsa.gov
> <mailto:sds@tycho.nsa.gov>> wrote:
>>
>> On 01/07/2015 05:03 PM, John Brooks wrote:
>>> @@ -341,8 +341,6 @@ int avtab_alloc(avtab_t *h, uint32_t nrules)
>>> work  = work >> 1;
>>> shift++;
>>> }
>>> -if (shift > 2)
>>> -shift = shift - 2;
>>> nslot = 1 << shift;
>>> if (nslot > MAX_AVTAB_SIZE)
>>> nslot = MAX_AVTAB_SIZE;
>>>
>>
>> tweakavtab.txt:rules:  101401 entries and 68460/131072 buckets used,
>> longest chain length 7
>>
>> Seems like we're wasting a large number of buckets in that scenario.
> 
> Good catch. It looks like this is caused by the segment I highlighted
> above, removing the shift adjustment.
> 
> changed-nslot.txt:rules:  100967 entries and 68321/131072 buckets used,
> longest chain length 8
> original-nslot.txt:rules:  100967 entries and 31017/32768 buckets used,
> longest chain length 13
> 
> So, one bucket is allocated per 2-4 elements. The change I actually
> wanted to make is to the definition of MAX_AVTAB_SIZE: it should be 2x
> MAX_AVTAB_HASH_BUCKETS to allow allocating a hash with maximum buckets,
> and that nslot bounding should use MAX_AVTAB_HASH_BUCKETS.
> 
>>
>> Also, in the corresponding kernel code (security/selinux/ss/avtab.[hc]),
>> we've actually shrunk the hash bits from 13 to 11,
> 
> Interesting. I wonder what the kernel hash eval looks like - it might
> benefit from a better hash function as well.

Permission checks in the kernel are usually handled by the AVC (access
vector cache), so the looking it up in the avtab is the slow path already.

> 
>>
>> I've also considered reworking the libsepol check_assertions() code to
>> not expand the avtab in order to provide better traceback to the
>> original source allow rule that violated the neverallow.  This would
>> require more work by check_assertion_helper to check each attribute
>> associated with the source and target, just as with
>> context_struct_compute_av.
> 
> Yeah; I expect there is a lot of room for algorithmic improvement here.
> I wish I had time to understand and fix it. We could probably get this
> running on the order of seconds instead of minutes, and using _much_
> less memory.
> 
> Even after these patches, expand_module spends 60% in avtab_search_node
> (and 13% malloc_consolidate, the rest is trivial). Next step would be to
> reduce the number of elements or lookups.
> 
> One interesting note: this fully expanded table is built twice under
> expand_module, for hierarchy_check_constraints and check_assertions. We
> could cut runtime almost in half by reusing the table.

Yes, they were originally written to permit running them independently,
so certainly when they are both run, we could avoid that duplication.

Re: [PATCH 3/3] Tweak avtab hash table parameters for better performance

[Stephen Smalley]

On 01/13/2015 08:50 AM, Stephen Smalley wrote:
> On 01/12/2015 08:25 PM, John Brooks wrote:
>> On Jan 12, 2015, at 10:47 AM, Stephen Smalley <sds@tycho.nsa.gov
>> <mailto:sds@tycho.nsa.gov>> wrote:
>>>
>>> On 01/07/2015 05:03 PM, John Brooks wrote:
>>>> @@ -341,8 +341,6 @@ int avtab_alloc(avtab_t *h, uint32_t nrules)
>>>> work  = work >> 1;
>>>> shift++;
>>>> }
>>>> -if (shift > 2)
>>>> -shift = shift - 2;
>>>> nslot = 1 << shift;
>>>> if (nslot > MAX_AVTAB_SIZE)
>>>> nslot = MAX_AVTAB_SIZE;
>>>>
>>>
>>> tweakavtab.txt:rules:  101401 entries and 68460/131072 buckets used,
>>> longest chain length 7
>>>
>>> Seems like we're wasting a large number of buckets in that scenario.
>>
>> Good catch. It looks like this is caused by the segment I highlighted
>> above, removing the shift adjustment.
>>
>> changed-nslot.txt:rules:  100967 entries and 68321/131072 buckets used,
>> longest chain length 8
>> original-nslot.txt:rules:  100967 entries and 31017/32768 buckets used,
>> longest chain length 13
>>
>> So, one bucket is allocated per 2-4 elements. The change I actually
>> wanted to make is to the definition of MAX_AVTAB_SIZE: it should be 2x
>> MAX_AVTAB_HASH_BUCKETS to allow allocating a hash with maximum buckets,
>> and that nslot bounding should use MAX_AVTAB_HASH_BUCKETS.
>>
>>>
>>> Also, in the corresponding kernel code (security/selinux/ss/avtab.[hc]),
>>> we've actually shrunk the hash bits from 13 to 11,
>>
>> Interesting. I wonder what the kernel hash eval looks like - it might
>> benefit from a better hash function as well.
> 
> Permission checks in the kernel are usually handled by the AVC (access
> vector cache), so the looking it up in the avtab is the slow path already.

That said, it wouldn't hurt to look at improving the hash function there
as well, and possibly for the AVC too.

One thing to note is that we never envisioned such large policies when
we created SELinux (the original example policy was much smaller).  The
Fedora policy unfortunately ships with every possible module/domain that
one could ever use included, and does not attempt to reduce the policy
to only the subset required for the given system.  Admittedly that is a
hard problem.  In the Android case, we were careful to keep the policy
small from the beginning, but there we have a much smaller and more
constrained userspace environment.

[PATCH v2 0/3] Improve check_assertions performance through hash tweaks

[John Brooks]

Updated to not override environment with -O2, improved readability of the hash
implementation, and restored avtab_alloc's behavior of allocating a fraction of
the expected number of elements as buckets for better efficiency in small hashes.

John Brooks (3):
  Build libsepol with -O2
  Use a better hash function for libsepol's avtab
  Tweak avtab hash table parameters for better performance

 libsepol/include/sepol/policydb/avtab.h |  7 ++---
 libsepol/src/Makefile                   |  2 +-
 libsepol/src/avtab.c                    | 45 ++++++++++++++++++++++++++++-----
 3 files changed, 44 insertions(+), 10 deletions(-)

-- 
1.9.3

[PATCH v2 1/3] Build libsepol with -O2

[John Brooks]

libsepol contains performance sensitive code; in particular, compiler
optimizations save a few minutes off of the optimized policydb hash
tables.

Signed-off-by: John Brooks <john.brooks@jolla.com>
---
 libsepol/src/Makefile | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/libsepol/src/Makefile b/libsepol/src/Makefile
index 6450d67..db6c2ba 100644
--- a/libsepol/src/Makefile
+++ b/libsepol/src/Makefile
@@ -20,7 +20,7 @@ LIBMAP=libsepol.map
 LIBSO=$(TARGET).$(LIBVERSION)
 OBJS= $(patsubst %.c,%.o,$(wildcard *.c))
 LOBJS= $(patsubst %.c,%.lo,$(wildcard *.c))
-CFLAGS ?= -Werror -Wall -W -Wundef -Wshadow -Wmissing-format-attribute
+CFLAGS ?= -Werror -Wall -W -Wundef -Wshadow -Wmissing-format-attribute -O2
 
 override CFLAGS += -I. -I../include -D_GNU_SOURCE
 
-- 
1.9.3

[PATCH v2 2/3] Use a better hash function for libsepol's avtab

[John Brooks]

This function, based on murmurhash3, has much better distribution than
the original. Using the current default of 4096 buckets, there are many
fewer collisions:

Before:
2893000 entries and 4096/4096 buckets used, longest chain length 1649
After:
2732000 entries and 4096/4096 buckets used, longest chain length 764

The difference becomes much more significant when buckets are increased.
A naive attempt to expand the current function to larger outputs doesn't
yield any significant improvement; so this function is a prerequisite
for increasing the bucket size.

Signed-off-by: John Brooks <john.brooks@jolla.com>
---
 libsepol/src/avtab.c | 39 ++++++++++++++++++++++++++++++++++++---
 1 file changed, 36 insertions(+), 3 deletions(-)

diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
index ea947cb..86e782c 100644
--- a/libsepol/src/avtab.c
+++ b/libsepol/src/avtab.c
@@ -49,10 +49,43 @@
 #include "debug.h"
 #include "private.h"
 
-static inline int avtab_hash(struct avtab_key *keyp, uint16_t mask)
+/* Based on MurmurHash3, written by Austin Appleby and placed in the
+ * public domain.
+ */
+static inline int avtab_hash(struct avtab_key *keyp, uint32_t mask)
 {
-	return ((keyp->target_class + (keyp->target_type << 2) +
-		 (keyp->source_type << 9)) & mask);
+	static const uint32_t c1 = 0xcc9e2d51;
+	static const uint32_t c2 = 0x1b873593;
+	static const uint32_t r1 = 15;
+	static const uint32_t r2 = 13;
+	static const uint32_t m  = 5;
+	static const uint32_t n  = 0xe6546b64;
+
+	uint32_t hash = 0;
+
+#define mix(input) { \
+	uint32_t 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;
 }
 
 static avtab_ptr_t
-- 
1.9.3

[PATCH v2 3/3] Tweak avtab hash table parameters for better performance

[John Brooks]

Using the Fedora 20 targeted policy, running check_assertions requires
an avtab with around 22 million elements. With the default limit of 4096
buckets, performance is abysmal: it takes more than an hour to populate
the hash. Profiling shows most of that time under avtab_search_node.

This patch increases the hash from 13 to 20 bits and to a maximum of
1048576 buckets. The time for check_assertions on that policy is reduced
to about 3 minutes, which is enough to re-enable those checks as part of
the build process.

A full size table will allocate 4-8 MB of memory, up from 16-32 KB. In a
cursory review, these tables are usually short-lived and only 1-3 are
allocated together. Compared to the cost of entries in this table (up to
1 GB using the same policy), this isn't a significant increase.

Signed-off-by: John Brooks <john.brooks@jolla.com>
---
 libsepol/include/sepol/policydb/avtab.h | 7 ++++---
 libsepol/src/avtab.c                    | 6 +++---
 2 files changed, 7 insertions(+), 6 deletions(-)

diff --git a/libsepol/include/sepol/policydb/avtab.h b/libsepol/include/sepol/policydb/avtab.h
index 6955ecf..bb6e79f 100644
--- a/libsepol/include/sepol/policydb/avtab.h
+++ b/libsepol/include/sepol/policydb/avtab.h
@@ -81,7 +81,7 @@ typedef struct avtab {
 	avtab_ptr_t *htable;
 	uint32_t nel;		/* number of elements */
 	uint32_t nslot;         /* number of hash slots */
-	uint16_t mask;          /* mask to compute hash func */
+	uint32_t mask;          /* mask to compute hash func */
 } avtab_t;
 
 extern int avtab_init(avtab_t *);
@@ -117,10 +117,11 @@ extern avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key);
 
 extern avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified);
 
-#define MAX_AVTAB_HASH_BITS 13
+#define MAX_AVTAB_HASH_BITS 20
 #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
 #define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
-#define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
+/* avtab_alloc uses one bucket per 2-4 elements, so adjust to get maximum buckets */
+#define MAX_AVTAB_SIZE (MAX_AVTAB_HASH_BUCKETS << 1)
 
 #endif				/* _AVTAB_H_ */
 
diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
index 86e782c..d6041d4 100644
--- a/libsepol/src/avtab.c
+++ b/libsepol/src/avtab.c
@@ -333,7 +333,7 @@ int avtab_init(avtab_t * h)
 
 int avtab_alloc(avtab_t *h, uint32_t nrules)
 {
-	uint16_t mask = 0;
+	uint32_t mask = 0;
 	uint32_t shift = 0;
 	uint32_t work = nrules;
 	uint32_t nslot = 0;
@@ -348,8 +348,8 @@ int avtab_alloc(avtab_t *h, uint32_t nrules)
 	if (shift > 2)
 		shift = shift - 2;
 	nslot = 1 << shift;
-	if (nslot > MAX_AVTAB_SIZE)
-		nslot = MAX_AVTAB_SIZE;
+	if (nslot > MAX_AVTAB_HASH_BUCKETS)
+		nslot = MAX_AVTAB_HASH_BUCKETS;
 	mask = nslot - 1;
 
 	h->htable = calloc(nslot, sizeof(avtab_ptr_t));
-- 
1.9.3

Re: [PATCH v2 0/3] Improve check_assertions performance through hash tweaks

[Stephen Smalley]

On 01/14/2015 07:24 PM, John Brooks wrote:
> Updated to not override environment with -O2, improved readability of the hash
> implementation, and restored avtab_alloc's behavior of allocating a fraction of
> the expected number of elements as buckets for better efficiency in small hashes.
> 
> John Brooks (3):
>   Build libsepol with -O2
>   Use a better hash function for libsepol's avtab
>   Tweak avtab hash table parameters for better performance
> 
>  libsepol/include/sepol/policydb/avtab.h |  7 ++---
>  libsepol/src/Makefile                   |  2 +-
>  libsepol/src/avtab.c                    | 45 ++++++++++++++++++++++++++++-----
>  3 files changed, 44 insertions(+), 10 deletions(-)

Thanks, all three patches applied.