[PATCH 2/6] selinux: dump statistics for more hash tables

[PATCH 2/6] selinux: dump statistics for more hash tables

[Christian Göttsche]

Dump in the SELinux debug configuration the statistics for the
conditional rules avtab, the role transition, and class and common
permission hash tables.

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 security/selinux/ss/conditional.c | 3 +++
 security/selinux/ss/policydb.c    | 6 ++++++
 2 files changed, 9 insertions(+)

diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c
index 81ff676f209a..0dd17fe76286 100644
--- a/security/selinux/ss/conditional.c
+++ b/security/selinux/ss/conditional.c
@@ -171,6 +171,9 @@ int cond_init_bool_indexes(struct policydb *p)
 					      GFP_KERNEL);
 	if (!p->bool_val_to_struct)
 		return -ENOMEM;
+
+	avtab_hash_eval(&p->te_cond_avtab, "conditional_rules");
+
 	return 0;
 }
 
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 84f02d4f8093..932e383bcad6 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -1158,6 +1158,8 @@ static int common_read(struct policydb *p, struct symtab *s, void *fp)
 			goto bad;
 	}
 
+	hash_eval(&comdatum->permissions.table, "common_permissions");
+
 	rc = symtab_insert(s, key, comdatum);
 	if (rc)
 		goto bad;
@@ -1339,6 +1341,8 @@ static int class_read(struct policydb *p, struct symtab *s, void *fp)
 			goto bad;
 	}
 
+	hash_eval(&cladatum->permissions.table, "class_permissions");
+
 	rc = read_cons_helper(p, &cladatum->constraints, ncons, 0, fp);
 	if (rc)
 		goto bad;
@@ -2616,6 +2620,8 @@ int policydb_read(struct policydb *p, void *fp)
 		rtd = NULL;
 	}
 
+	hash_eval(&p->role_tr, "roletr");
+
 	rc = next_entry(buf, fp, sizeof(u32));
 	if (rc)
 		goto bad;
-- 
2.40.1

[PATCH 3/6] selinux: improve debug configuration

[Christian Göttsche]

If the SELinux debug configuration is enabled define the macro DEBUG
such that pr_debug() calls are always enabled, regardless of
CONFIG_DYNAMIC_DEBUG, since those message are the main reason for this
configuration in the first place.

Mention example usage in case CONFIG_DYNAMIC_DEBUG is enabled in the
help section of the configuration.

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 security/selinux/Kconfig  | 10 ++++++++++
 security/selinux/Makefile |  2 ++
 2 files changed, 12 insertions(+)

diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
index d30348fbe0df..61abc1e094a8 100644
--- a/security/selinux/Kconfig
+++ b/security/selinux/Kconfig
@@ -77,3 +77,13 @@ config SECURITY_SELINUX_DEBUG
 	  This enables debugging code designed to help SELinux kernel
 	  developers, unless you know what this does in the kernel code you
 	  should leave this disabled.
+
+	  To fine control the messages to be printed enable
+	  CONFIG_DYNAMIC_DEBUG and see
+	  Documentation/admin-guide/dynamic-debug-howto.rst for additional
+	  information.
+
+	  Example usage:
+
+		echo -n 'file "security/selinux/*" +p' > \
+			/proc/dynamic_debug/control
diff --git a/security/selinux/Makefile b/security/selinux/Makefile
index 836379639058..c47519ed8156 100644
--- a/security/selinux/Makefile
+++ b/security/selinux/Makefile
@@ -12,6 +12,8 @@ obj-$(CONFIG_SECURITY_SELINUX) := selinux.o
 
 ccflags-y := -I$(srctree)/security/selinux -I$(srctree)/security/selinux/include
 
+ccflags-$(CONFIG_SECURITY_SELINUX_DEBUG) += -DDEBUG
+
 selinux-y := avc.o hooks.o selinuxfs.o netlink.o nlmsgtab.o netif.o \
 	     netnode.o netport.o status.o \
 	     ss/ebitmap.o ss/hashtab.o ss/symtab.o ss/sidtab.o ss/avtab.o \
-- 
2.40.1

Re: [PATCH 3/6] selinux: improve debug configuration

[Stephen Smalley]

On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> If the SELinux debug configuration is enabled define the macro DEBUG
> such that pr_debug() calls are always enabled, regardless of
> CONFIG_DYNAMIC_DEBUG, since those message are the main reason for this
> configuration in the first place.
>
> Mention example usage in case CONFIG_DYNAMIC_DEBUG is enabled in the
> help section of the configuration.
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>

Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Re: [PATCH 3/6] selinux: improve debug configuration

[Paul Moore]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 737 bytes --]

On Aug 18, 2023 Stephen Smalley <stephen.smalley.work@gmail.com> wrote:
> 
> If the SELinux debug configuration is enabled define the macro DEBUG
> such that pr_debug() calls are always enabled, regardless of
> CONFIG_DYNAMIC_DEBUG, since those message are the main reason for this
> configuration in the first place.
> 
> Mention example usage in case CONFIG_DYNAMIC_DEBUG is enabled in the
> help section of the configuration.
> 
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> ---
>  security/selinux/Kconfig  | 10 ++++++++++
>  security/selinux/Makefile |  2 ++
>  2 files changed, 12 insertions(+)

Merged into selinux/next, thanks!

--
paul-moore.com

[PATCH 4/6] selinux: simplify avtab slot calculation

[Christian Göttsche]

Instead of dividing by 8 and then performing log2 by hand, use a more
readable calculation.

The behavior of rounddown_pow_of_two() for an input of 0 is undefined,
so handle that case and small values manually to achieve the same
results.

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 security/selinux/ss/avtab.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)

diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 955cfe495606..1d1ffe085b35 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -298,13 +298,7 @@ int avtab_alloc(struct avtab *h, u32 nrules)
 	u32 nslot = 0;
 
 	if (nrules != 0) {
-		u32 shift = 1;
-		u32 work = nrules >> 3;
-		while (work) {
-			work >>= 1;
-			shift++;
-		}
-		nslot = 1 << shift;
+		nslot = nrules > 3 ? rounddown_pow_of_two(nrules / 2) : 2;
 		if (nslot > MAX_AVTAB_HASH_BUCKETS)
 			nslot = MAX_AVTAB_HASH_BUCKETS;
 
-- 
2.40.1

Re: [PATCH 4/6] selinux: simplify avtab slot calculation

[Stephen Smalley]

On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> Instead of dividing by 8 and then performing log2 by hand, use a more
> readable calculation.
>
> The behavior of rounddown_pow_of_two() for an input of 0 is undefined,
> so handle that case and small values manually to achieve the same
> results.
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>

Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Re: [PATCH 4/6] selinux: simplify avtab slot calculation

[Paul Moore]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 622 bytes --]

On Aug 18, 2023 Stephen Smalley <stephen.smalley.work@gmail.com> wrote:
> 
> Instead of dividing by 8 and then performing log2 by hand, use a more
> readable calculation.
> 
> The behavior of rounddown_pow_of_two() for an input of 0 is undefined,
> so handle that case and small values manually to achieve the same
> results.
> 
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> ---
>  security/selinux/ss/avtab.c | 8 +-------
>  1 file changed, 1 insertion(+), 7 deletions(-)

Much nicer, thanks.  Merged into selinux/next.

--
paul-moore.com

[PATCH 5/6] selinux: improve role transition hashing

[Christian Göttsche]

The number of buckets is calculated by performing a binary AND against
the mask of the hash table, which is one less than its size (which is a
power of two).  This leads to all top bits being discarded, e.g. with
the Reference Policy on Debian there exists 376 entries, leading to a
size of 512, discarding the top 23 bits.

Use jhash to improve the hash table utilization:

    # current
    roletr:  376 entries and 124/512 buckets used, longest chain length 8, sum of chain length^2 1496

    # patch
    roletr:  376 entries and 266/512 buckets used, longest chain length 4, sum of chain length^2 646

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 security/selinux/ss/policydb.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 932e383bcad6..dd4a9eff61be 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -491,7 +491,7 @@ static u32 role_trans_hash(const void *k)
 {
 	const struct role_trans_key *key = k;
 
-	return key->role + (key->type << 3) + (key->tclass << 5);
+	return jhash_3words(key->role, key->type, (u32)key->tclass << 16 | key->tclass, 0);
 }
 
 static int role_trans_cmp(const void *k1, const void *k2)
-- 
2.40.1

Re: [PATCH 5/6] selinux: improve role transition hashing

[Stephen Smalley]

On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> The number of buckets is calculated by performing a binary AND against
> the mask of the hash table, which is one less than its size (which is a
> power of two).  This leads to all top bits being discarded, e.g. with
> the Reference Policy on Debian there exists 376 entries, leading to a
> size of 512, discarding the top 23 bits.
>
> Use jhash to improve the hash table utilization:
>
>     # current
>     roletr:  376 entries and 124/512 buckets used, longest chain length 8, sum of chain length^2 1496
>
>     # patch
>     roletr:  376 entries and 266/512 buckets used, longest chain length 4, sum of chain length^2 646
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>

Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Re: [PATCH 5/6] selinux: improve role transition hashing

[Paul Moore]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 999 bytes --]

On Aug 18, 2023 =?UTF-8?q?Christian=20G=C3=B6ttsche?= <cgzones@googlemail.com> wrote:
> 
> The number of buckets is calculated by performing a binary AND against
> the mask of the hash table, which is one less than its size (which is a
> power of two).  This leads to all top bits being discarded, e.g. with
> the Reference Policy on Debian there exists 376 entries, leading to a
> size of 512, discarding the top 23 bits.
> 
> Use jhash to improve the hash table utilization:
> 
>     # current
>     roletr:  376 entries and 124/512 buckets used, longest chain length 8, sum of chain length^2 1496
> 
>     # patch
>     roletr:  376 entries and 266/512 buckets used, longest chain length 4, sum of chain length^2 646
> 
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> ---
>  security/selinux/ss/policydb.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)

Merged into selinux/next, thanks.

--
paul-moore.com

[PATCH 6/6] selinux: improve symtab string hashing

[Christian Göttsche]

The number of buckets is calculated by performing a binary AND against
the mask of the hash table, which is one less than its size (which is a
power of two).  This leads to all top bits being discarded, requiring
for short or similar inputs a hash function with a good avalanche
effect.

Use djb2a:

    # current
    common prefixes:  7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11
    classes:  134 entries and 100/256 buckets used, longest chain length 5, sum of chain length^2 234
    roles:  15 entries and 6/16 buckets used, longest chain length 5, sum of chain length^2 57
    types:  4448 entries and 3016/8192 buckets used, longest chain length 41, sum of chain length^2 14922
    users:  7 entries and 3/8 buckets used, longest chain length 3, sum of chain length^2 17
    bools:  306 entries and 221/512 buckets used, longest chain length 4, sum of chain length^2 524
    levels:  1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1
    categories:  1024 entries and 400/1024 buckets used, longest chain length 4, sum of chain length^2 2740

    # patch
    common prefixes:  7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11
    classes:  134 entries and 101/256 buckets used, longest chain length 3, sum of chain length^2 210
    roles:  15 entries and 9/16 buckets used, longest chain length 3, sum of chain length^2 31
    types:  4448 entries and 3459/8192 buckets used, longest chain length 5, sum of chain length^2 6778
    users:  7 entries and 5/8 buckets used, longest chain length 3, sum of chain length^2 13
    bools:  306 entries and 236/512 buckets used, longest chain length 5, sum of chain length^2 470
    levels:  1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1
    categories:  1024 entries and 518/1024 buckets used, longest chain length 7, sum of chain length^2 2992

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 security/selinux/ss/symtab.c | 18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)

diff --git a/security/selinux/ss/symtab.c b/security/selinux/ss/symtab.c
index 43d7f0319ccd..b6761b96eee4 100644
--- a/security/selinux/ss/symtab.c
+++ b/security/selinux/ss/symtab.c
@@ -11,16 +11,14 @@
 
 static unsigned int symhash(const void *key)
 {
-	const char *p, *keyp;
-	unsigned int size;
-	unsigned int val;
-
-	val = 0;
-	keyp = key;
-	size = strlen(keyp);
-	for (p = keyp; (p - keyp) < size; p++)
-		val = (val << 4 | (val >> (8*sizeof(unsigned int)-4))) ^ (*p);
-	return val;
+	/* djb2a */
+	unsigned int hash = 5381;
+	unsigned char c;
+
+	while ((c = *(const unsigned char *)key++))
+		hash = ((hash << 5) + hash) ^ c;
+
+	return hash;
 }
 
 static int symcmp(const void *key1, const void *key2)
-- 
2.40.1

Re: [PATCH 6/6] selinux: improve symtab string hashing

[Stephen Smalley]

On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> The number of buckets is calculated by performing a binary AND against
> the mask of the hash table, which is one less than its size (which is a
> power of two).  This leads to all top bits being discarded, requiring
> for short or similar inputs a hash function with a good avalanche
> effect.
>
> Use djb2a:
>
>     # current
>     common prefixes:  7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11
>     classes:  134 entries and 100/256 buckets used, longest chain length 5, sum of chain length^2 234
>     roles:  15 entries and 6/16 buckets used, longest chain length 5, sum of chain length^2 57
>     types:  4448 entries and 3016/8192 buckets used, longest chain length 41, sum of chain length^2 14922
>     users:  7 entries and 3/8 buckets used, longest chain length 3, sum of chain length^2 17
>     bools:  306 entries and 221/512 buckets used, longest chain length 4, sum of chain length^2 524
>     levels:  1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1
>     categories:  1024 entries and 400/1024 buckets used, longest chain length 4, sum of chain length^2 2740
>
>     # patch
>     common prefixes:  7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11
>     classes:  134 entries and 101/256 buckets used, longest chain length 3, sum of chain length^2 210
>     roles:  15 entries and 9/16 buckets used, longest chain length 3, sum of chain length^2 31
>     types:  4448 entries and 3459/8192 buckets used, longest chain length 5, sum of chain length^2 6778
>     users:  7 entries and 5/8 buckets used, longest chain length 3, sum of chain length^2 13
>     bools:  306 entries and 236/512 buckets used, longest chain length 5, sum of chain length^2 470
>     levels:  1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1
>     categories:  1024 entries and 518/1024 buckets used, longest chain length 7, sum of chain length^2 2992
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> ---
>  security/selinux/ss/symtab.c | 18 ++++++++----------
>  1 file changed, 8 insertions(+), 10 deletions(-)
>
> diff --git a/security/selinux/ss/symtab.c b/security/selinux/ss/symtab.c
> index 43d7f0319ccd..b6761b96eee4 100644
> --- a/security/selinux/ss/symtab.c
> +++ b/security/selinux/ss/symtab.c
> @@ -11,16 +11,14 @@
>
>  static unsigned int symhash(const void *key)
>  {
> -       const char *p, *keyp;
> -       unsigned int size;
> -       unsigned int val;
> -
> -       val = 0;
> -       keyp = key;
> -       size = strlen(keyp);
> -       for (p = keyp; (p - keyp) < size; p++)
> -               val = (val << 4 | (val >> (8*sizeof(unsigned int)-4))) ^ (*p);
> -       return val;
> +       /* djb2a */

Do we need/want something that specifies the author/license (I assume
public domain) of this code?

> +       unsigned int hash = 5381;
> +       unsigned char c;
> +
> +       while ((c = *(const unsigned char *)key++))
> +               hash = ((hash << 5) + hash) ^ c;
> +
> +       return hash;
>  }
>
>  static int symcmp(const void *key1, const void *key2)
> --
> 2.40.1
>

Re: [PATCH 6/6] selinux: improve symtab string hashing

[Paul Moore]

On Thu, Sep 7, 2023 at 1:44 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
> On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
> <cgzones@googlemail.com> wrote:
> >
> > The number of buckets is calculated by performing a binary AND against
> > the mask of the hash table, which is one less than its size (which is a
> > power of two).  This leads to all top bits being discarded, requiring
> > for short or similar inputs a hash function with a good avalanche
> > effect.
> >
> > Use djb2a:
> >
> >     # current
> >     common prefixes:  7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11
> >     classes:  134 entries and 100/256 buckets used, longest chain length 5, sum of chain length^2 234
> >     roles:  15 entries and 6/16 buckets used, longest chain length 5, sum of chain length^2 57
> >     types:  4448 entries and 3016/8192 buckets used, longest chain length 41, sum of chain length^2 14922
> >     users:  7 entries and 3/8 buckets used, longest chain length 3, sum of chain length^2 17
> >     bools:  306 entries and 221/512 buckets used, longest chain length 4, sum of chain length^2 524
> >     levels:  1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1
> >     categories:  1024 entries and 400/1024 buckets used, longest chain length 4, sum of chain length^2 2740
> >
> >     # patch
> >     common prefixes:  7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11
> >     classes:  134 entries and 101/256 buckets used, longest chain length 3, sum of chain length^2 210
> >     roles:  15 entries and 9/16 buckets used, longest chain length 3, sum of chain length^2 31
> >     types:  4448 entries and 3459/8192 buckets used, longest chain length 5, sum of chain length^2 6778
> >     users:  7 entries and 5/8 buckets used, longest chain length 3, sum of chain length^2 13
> >     bools:  306 entries and 236/512 buckets used, longest chain length 5, sum of chain length^2 470
> >     levels:  1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1
> >     categories:  1024 entries and 518/1024 buckets used, longest chain length 7, sum of chain length^2 2992
> >
> > Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> > ---
> >  security/selinux/ss/symtab.c | 18 ++++++++----------
> >  1 file changed, 8 insertions(+), 10 deletions(-)
> >
> > diff --git a/security/selinux/ss/symtab.c b/security/selinux/ss/symtab.c
> > index 43d7f0319ccd..b6761b96eee4 100644
> > --- a/security/selinux/ss/symtab.c
> > +++ b/security/selinux/ss/symtab.c
> > @@ -11,16 +11,14 @@
> >
> >  static unsigned int symhash(const void *key)
> >  {
> > -       const char *p, *keyp;
> > -       unsigned int size;
> > -       unsigned int val;
> > -
> > -       val = 0;
> > -       keyp = key;
> > -       size = strlen(keyp);
> > -       for (p = keyp; (p - keyp) < size; p++)
> > -               val = (val << 4 | (val >> (8*sizeof(unsigned int)-4))) ^ (*p);
> > -       return val;
> > +       /* djb2a */
>
> Do we need/want something that specifies the author/license (I assume
> public domain) of this code?

It would be a good idea, yes.  I spent some time looking around, and
while there are many references to djb2 (and the djb2a xor version), I
had a hard time finding an explicit license statement from DJB.
However, in the cdb v0.75 release there is a source file, cdb_hash.c,
which has effectively the same hash (same algorithm, different
implementation) with a "/* Public domain. */" statement at the top.
IANAL, but I think that is good enough.

Christian, can you update this patch comments with this info?

http://cr.yp.to/cdb.html

> > +       unsigned int hash = 5381;
> > +       unsigned char c;
> > +
> > +       while ((c = *(const unsigned char *)key++))
> > +               hash = ((hash << 5) + hash) ^ c;
> > +
> > +       return hash;
> >  }
> >
> >  static int symcmp(const void *key1, const void *key2)
> > --
> > 2.40.1

-- 
paul-moore.com

Re: [PATCH 6/6] selinux: improve symtab string hashing

[Stephen Smalley]

On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> The number of buckets is calculated by performing a binary AND against
> the mask of the hash table, which is one less than its size (which is a
> power of two).  This leads to all top bits being discarded, requiring
> for short or similar inputs a hash function with a good avalanche
> effect.
>
> Use djb2a:
>
>     # current
>     common prefixes:  7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11
>     classes:  134 entries and 100/256 buckets used, longest chain length 5, sum of chain length^2 234
>     roles:  15 entries and 6/16 buckets used, longest chain length 5, sum of chain length^2 57
>     types:  4448 entries and 3016/8192 buckets used, longest chain length 41, sum of chain length^2 14922
>     users:  7 entries and 3/8 buckets used, longest chain length 3, sum of chain length^2 17
>     bools:  306 entries and 221/512 buckets used, longest chain length 4, sum of chain length^2 524
>     levels:  1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1
>     categories:  1024 entries and 400/1024 buckets used, longest chain length 4, sum of chain length^2 2740
>
>     # patch
>     common prefixes:  7 entries and 5/8 buckets used, longest chain length 2, sum of chain length^2 11
>     classes:  134 entries and 101/256 buckets used, longest chain length 3, sum of chain length^2 210
>     roles:  15 entries and 9/16 buckets used, longest chain length 3, sum of chain length^2 31
>     types:  4448 entries and 3459/8192 buckets used, longest chain length 5, sum of chain length^2 6778
>     users:  7 entries and 5/8 buckets used, longest chain length 3, sum of chain length^2 13
>     bools:  306 entries and 236/512 buckets used, longest chain length 5, sum of chain length^2 470
>     levels:  1 entries and 1/1 buckets used, longest chain length 1, sum of chain length^2 1
>     categories:  1024 entries and 518/1024 buckets used, longest chain length 7, sum of chain length^2 2992
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>

Assuming this is in fact public domain,
Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>

[PATCH 1/6] selinux: print sum of chain lengths^2 for hash tables

[Christian Göttsche]

Print the sum of chain lengths squared as a metric for hash tables to
provide more insights, similar to avtabs.

While on it add a comma in the avtab message to improve readability of
the output.

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 security/selinux/ss/avtab.c    | 2 +-
 security/selinux/ss/hashtab.c  | 5 +++++
 security/selinux/ss/hashtab.h  | 1 +
 security/selinux/ss/policydb.c | 4 ++--
 4 files changed, 9 insertions(+), 3 deletions(-)

diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 86d98a8e291b..955cfe495606 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -349,7 +349,7 @@ void avtab_hash_eval(struct avtab *h, const char *tag)
 	}
 
 	pr_debug("SELinux: %s:  %d entries and %d/%d buckets used, "
-	       "longest chain length %d sum of chain length^2 %llu\n",
+	       "longest chain length %d, sum of chain length^2 %llu\n",
 	       tag, h->nel, slots_used, h->nslot, max_chain_len,
 	       chain2_len_sum);
 }
diff --git a/security/selinux/ss/hashtab.c b/security/selinux/ss/hashtab.c
index ac5cdddfbf78..c05d8346a94a 100644
--- a/security/selinux/ss/hashtab.c
+++ b/security/selinux/ss/hashtab.c
@@ -107,10 +107,12 @@ int hashtab_map(struct hashtab *h,
 void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
 {
 	u32 i, chain_len, slots_used, max_chain_len;
+	u64 chain2_len_sum;
 	struct hashtab_node *cur;
 
 	slots_used = 0;
 	max_chain_len = 0;
+	chain2_len_sum = 0;
 	for (i = 0; i < h->size; i++) {
 		cur = h->htable[i];
 		if (cur) {
@@ -123,11 +125,14 @@ void hashtab_stat(struct hashtab *h, struct hashtab_info *info)
 
 			if (chain_len > max_chain_len)
 				max_chain_len = chain_len;
+
+			chain2_len_sum += (u64)chain_len * chain_len;
 		}
 	}
 
 	info->slots_used = slots_used;
 	info->max_chain_len = max_chain_len;
+	info->chain2_len_sum = chain2_len_sum;
 }
 #endif /* CONFIG_SECURITY_SELINUX_DEBUG */
 
diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h
index f9713b56d3d0..09b0a3744937 100644
--- a/security/selinux/ss/hashtab.h
+++ b/security/selinux/ss/hashtab.h
@@ -38,6 +38,7 @@ struct hashtab {
 struct hashtab_info {
 	u32 slots_used;
 	u32 max_chain_len;
+	u64 chain2_len_sum;
 };
 
 /*
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 28bd75dc6f71..84f02d4f8093 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -684,9 +684,9 @@ static void hash_eval(struct hashtab *h, const char *hash_name)
 	struct hashtab_info info;
 
 	hashtab_stat(h, &info);
-	pr_debug("SELinux: %s:  %d entries and %d/%d buckets used, longest chain length %d\n",
+	pr_debug("SELinux: %s:  %d entries and %d/%d buckets used, longest chain length %d, sum of chain length^2 %llu\n",
 		 hash_name, h->nel, info.slots_used, h->size,
-		 info.max_chain_len);
+		 info.max_chain_len, info.chain2_len_sum);
 }
 
 static void symtab_hash_eval(struct symtab *s)
-- 
2.40.1

Re: [PATCH 1/6] selinux: print sum of chain lengths^2 for hash tables

[Stephen Smalley]

On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> Print the sum of chain lengths squared as a metric for hash tables to
> provide more insights, similar to avtabs.
>
> While on it add a comma in the avtab message to improve readability of
> the output.
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>

Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Re: [PATCH 1/6] selinux: print sum of chain lengths^2 for hash tables

[Paul Moore]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 690 bytes --]

On Aug 18, 2023 Stephen Smalley <stephen.smalley.work@gmail.com> wrote:
> 
> Print the sum of chain lengths squared as a metric for hash tables to
> provide more insights, similar to avtabs.
> 
> While on it add a comma in the avtab message to improve readability of
> the output.
> 
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> ---
>  security/selinux/ss/avtab.c    | 2 +-
>  security/selinux/ss/hashtab.c  | 5 +++++
>  security/selinux/ss/hashtab.h  | 1 +
>  security/selinux/ss/policydb.c | 4 ++--
>  4 files changed, 9 insertions(+), 3 deletions(-)

Merged into selinux/next, thanks.

--
paul-moore.com

Re: [PATCH 2/6] selinux: dump statistics for more hash tables

[Stephen Smalley]

On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> Dump in the SELinux debug configuration the statistics for the
> conditional rules avtab, the role transition, and class and common
> permission hash tables.
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> ---

> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index 84f02d4f8093..932e383bcad6 100644
> --- a/security/selinux/ss/policydb.c
> +++ b/security/selinux/ss/policydb.c
> @@ -1158,6 +1158,8 @@ static int common_read(struct policydb *p, struct symtab *s, void *fp)
>                         goto bad;
>         }
>
> +       hash_eval(&comdatum->permissions.table, "common_permissions");
> +
>         rc = symtab_insert(s, key, comdatum);
>         if (rc)
>                 goto bad;
> @@ -1339,6 +1341,8 @@ static int class_read(struct policydb *p, struct symtab *s, void *fp)
>                         goto bad;
>         }
>
> +       hash_eval(&cladatum->permissions.table, "class_permissions");
> +
>         rc = read_cons_helper(p, &cladatum->constraints, ncons, 0, fp);
>         if (rc)
>                 goto bad;

Do we want to embed the actual common and class keys in the output to
distinguish among the multiple common and class permissions tables?

Re: [PATCH 2/6] selinux: dump statistics for more hash tables

[Paul Moore]

On Thu, Sep 7, 2023 at 1:42 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
> On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
> <cgzones@googlemail.com> wrote:
> >
> > Dump in the SELinux debug configuration the statistics for the
> > conditional rules avtab, the role transition, and class and common
> > permission hash tables.
> >
> > Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> > ---
>
> > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > index 84f02d4f8093..932e383bcad6 100644
> > --- a/security/selinux/ss/policydb.c
> > +++ b/security/selinux/ss/policydb.c
> > @@ -1158,6 +1158,8 @@ static int common_read(struct policydb *p, struct symtab *s, void *fp)
> >                         goto bad;
> >         }
> >
> > +       hash_eval(&comdatum->permissions.table, "common_permissions");
> > +
> >         rc = symtab_insert(s, key, comdatum);
> >         if (rc)
> >                 goto bad;
> > @@ -1339,6 +1341,8 @@ static int class_read(struct policydb *p, struct symtab *s, void *fp)
> >                         goto bad;
> >         }
> >
> > +       hash_eval(&cladatum->permissions.table, "class_permissions");
> > +
> >         rc = read_cons_helper(p, &cladatum->constraints, ncons, 0, fp);
> >         if (rc)
> >                 goto bad;
>
> Do we want to embed the actual common and class keys in the output to
> distinguish among the multiple common and class permissions tables?

That seems reasonable, were you thinking of just adding it to the
hash_eval()'s hash name string, e.g. "common_permissions[XXX]"?

-- 
paul-moore.com

Re: [PATCH 2/6] selinux: dump statistics for more hash tables

[Stephen Smalley]

On Wed, Sep 13, 2023 at 12:12 PM Paul Moore <paul@paul-moore.com> wrote:
>
> On Thu, Sep 7, 2023 at 1:42 PM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> > On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
> > <cgzones@googlemail.com> wrote:
> > >
> > > Dump in the SELinux debug configuration the statistics for the
> > > conditional rules avtab, the role transition, and class and common
> > > permission hash tables.
> > >
> > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> > > ---
> >
> > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > > index 84f02d4f8093..932e383bcad6 100644
> > > --- a/security/selinux/ss/policydb.c
> > > +++ b/security/selinux/ss/policydb.c
> > > @@ -1158,6 +1158,8 @@ static int common_read(struct policydb *p, struct symtab *s, void *fp)
> > >                         goto bad;
> > >         }
> > >
> > > +       hash_eval(&comdatum->permissions.table, "common_permissions");
> > > +
> > >         rc = symtab_insert(s, key, comdatum);
> > >         if (rc)
> > >                 goto bad;
> > > @@ -1339,6 +1341,8 @@ static int class_read(struct policydb *p, struct symtab *s, void *fp)
> > >                         goto bad;
> > >         }
> > >
> > > +       hash_eval(&cladatum->permissions.table, "class_permissions");
> > > +
> > >         rc = read_cons_helper(p, &cladatum->constraints, ncons, 0, fp);
> > >         if (rc)
> > >                 goto bad;
> >
> > Do we want to embed the actual common and class keys in the output to
> > distinguish among the multiple common and class permissions tables?
>
> That seems reasonable, were you thinking of just adding it to the
> hash_eval()'s hash name string, e.g. "common_permissions[XXX]"?

Yes, otherwise you get a bunch of common_permissions and
class_permissions lines with no way to correlate.

Re: [PATCH 2/6] selinux: dump statistics for more hash tables

[Paul Moore]

On Wed, Sep 13, 2023 at 2:03 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
> On Wed, Sep 13, 2023 at 12:12 PM Paul Moore <paul@paul-moore.com> wrote:
> > On Thu, Sep 7, 2023 at 1:42 PM Stephen Smalley
> > <stephen.smalley.work@gmail.com> wrote:
> > > On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
> > > <cgzones@googlemail.com> wrote:
> > > >
> > > > Dump in the SELinux debug configuration the statistics for the
> > > > conditional rules avtab, the role transition, and class and common
> > > > permission hash tables.
> > > >
> > > > Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> > > > ---
> > >
> > > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > > > index 84f02d4f8093..932e383bcad6 100644
> > > > --- a/security/selinux/ss/policydb.c
> > > > +++ b/security/selinux/ss/policydb.c
> > > > @@ -1158,6 +1158,8 @@ static int common_read(struct policydb *p, struct symtab *s, void *fp)
> > > >                         goto bad;
> > > >         }
> > > >
> > > > +       hash_eval(&comdatum->permissions.table, "common_permissions");
> > > > +
> > > >         rc = symtab_insert(s, key, comdatum);
> > > >         if (rc)
> > > >                 goto bad;
> > > > @@ -1339,6 +1341,8 @@ static int class_read(struct policydb *p, struct symtab *s, void *fp)
> > > >                         goto bad;
> > > >         }
> > > >
> > > > +       hash_eval(&cladatum->permissions.table, "class_permissions");
> > > > +
> > > >         rc = read_cons_helper(p, &cladatum->constraints, ncons, 0, fp);
> > > >         if (rc)
> > > >                 goto bad;
> > >
> > > Do we want to embed the actual common and class keys in the output to
> > > distinguish among the multiple common and class permissions tables?
> >
> > That seems reasonable, were you thinking of just adding it to the
> > hash_eval()'s hash name string, e.g. "common_permissions[XXX]"?
>
> Yes, otherwise you get a bunch of common_permissions and
> class_permissions lines with no way to correlate.

Agreed, I was asking more to determine how you envisioned the keys in
the output.

Christian, instead of creating the combined string in the caller I
would suggest adding a third parameter to the hash_eval() function and
having hash_eval() add the extra info (if present, NULL should be
acceptable) to the output.  This should ensure no extra work is done
when debug is disabled.

-- 
paul-moore.com

Re: [PATCH 2/6] selinux: dump statistics for more hash tables

[Stephen Smalley]

On Fri, Aug 18, 2023 at 11:12 AM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> Dump in the SELinux debug configuration the statistics for the
> conditional rules avtab, the role transition, and class and common
> permission hash tables.
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>

Aside from the question I asked, which I have no strong opinion about,
Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>