[PATCH v3 0/3] selinux: avtab arrays and refactors

[PATCH v3 0/3] selinux: avtab arrays and refactors

[Jacob Satterfield]

As the refpolicy and the default Fedora policy continue to grow in
size, especially with regard to rules / access vectors, the memory
usage of the policydb and runtime to search through it increases.
Looking at /proc/slabinfo indicates that the avtab_node_cachep
kmem_cache is significantly responsible for overall memory usage and
was a good target for optimizations. Running "perf stat" on the
"load_policy" command shows that a majority of time is spent adding
rules into the avtab.

This patch series is an attempt at optimizing these hot spots within
the security server implementation to help it scale with  additional
rules in the future.

All patches are independent of each other.

Patches 1-2 are refactors of the internal avtab.c interfaces and code
paths with no logic changes. It removes duplicative code and
homogenizes access patterns.

Patch 3 changes avtab to use arrays instead of a kmem_cache for the
individual nodes of the hashtable.

Changelog:

v3:
- selinux: simplify avtab_insert_node() prototype
  - dropped, already merged
- selinux: avtab iteration macros
  - reverted changes to avtab_destroy() which created a UAF bug
- selinux: refactor avtab_node comparisons
  - fixed indent issues in avtab_node_cmp()
  - removed unlikely() macro in avtab_insert()

v2:
- selinux: use arrays for avtab hashtable nodes
  - rewritten to use pointers instead of indices
  - NULL_NODE_IDX and NODES_ARRAY_IDX macros removed
  - getter functions removed
  - two-pass algorithm used to compute cond. table size prior to
    allocating the array
- selinux: hweight optimization in avtab_read_item
  - dropped, already merged
- selinux: shrink conditional avtab node array
  - dropped, not needed due to new allocation approach
- selinux: refactor avtab_node comparisons
  - newly added
- selinux: avtab iteration macros
  - newly added
- selinux: simplify avtab_insert_node() prototype
  - newly added

Jacob Satterfield (3):
  selinux: refactor avtab_node comparisons
  selinux: avtab iteration macros
  selinux: use arrays for avtab hashtable nodes

 security/selinux/ss/avtab.c       | 176 ++++++++++++++----------------
 security/selinux/ss/avtab.h       |   4 +-
 security/selinux/ss/conditional.c |  37 +++++--
 security/selinux/ss/conditional.h |   2 +-
 4 files changed, 112 insertions(+), 107 deletions(-)

-- 
2.41.0

[PATCH v3 1/3] selinux: refactor avtab_node comparisons

[Jacob Satterfield]

In four separate functions within avtab, the same comparison logic is
used. The only difference is how the result is handled or whether there
is a unique specifier value to be checked for or used.

Extracting this functionality into the avtab_node_cmp() function unifies
the comparison logic between searching and insertion and gets rid of
duplicative code so that the implementation is easier to maintain.

Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com>
Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
---
 security/selinux/ss/avtab.c | 101 +++++++++++++++---------------------
 1 file changed, 41 insertions(+), 60 deletions(-)

diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 8751a602ead2..697eb4352439 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -96,12 +96,34 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst,
 	return newnode;
 }
 
+static int avtab_node_cmp(const struct avtab_key *key1,
+			  const struct avtab_key *key2)
+{
+	u16 specified = key1->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
+
+	if (key1->source_type == key2->source_type &&
+	    key1->target_type == key2->target_type &&
+	    key1->target_class == key2->target_class &&
+	    (specified & key2->specified))
+		return 0;
+	if (key1->source_type < key2->source_type)
+		return -1;
+	if (key1->source_type == key2->source_type &&
+	    key1->target_type < key2->target_type)
+		return -1;
+	if (key1->source_type == key2->source_type &&
+	    key1->target_type == key2->target_type &&
+	    key1->target_class < key2->target_class)
+		return -1;
+	return 1;
+}
+
 static int avtab_insert(struct avtab *h, const struct avtab_key *key,
 			const struct avtab_datum *datum)
 {
 	u32 hvalue;
 	struct avtab_node *prev, *cur, *newnode;
-	u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
+	int cmp;
 
 	if (!h || !h->nslot || h->nel == U32_MAX)
 		return -EINVAL;
@@ -110,23 +132,11 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key,
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {
-		if (key->source_type == cur->key.source_type &&
-		    key->target_type == cur->key.target_type &&
-		    key->target_class == cur->key.target_class &&
-		    (specified & cur->key.specified)) {
-			/* extended perms may not be unique */
-			if (specified & AVTAB_XPERMS)
-				break;
+		cmp = avtab_node_cmp(key, &cur->key);
+		/* extended perms may not be unique */
+		if (cmp == 0 && !(key->specified & AVTAB_XPERMS))
 			return -EEXIST;
-		}
-		if (key->source_type < cur->key.source_type)
-			break;
-		if (key->source_type == cur->key.source_type &&
-		    key->target_type < cur->key.target_type)
-			break;
-		if (key->source_type == cur->key.source_type &&
-		    key->target_type == cur->key.target_type &&
-		    key->target_class < cur->key.target_class)
+		if (cmp <= 0)
 			break;
 	}
 
@@ -148,7 +158,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
 {
 	u32 hvalue;
 	struct avtab_node *prev, *cur;
-	u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
+	int cmp;
 
 	if (!h || !h->nslot || h->nel == U32_MAX)
 		return NULL;
@@ -156,19 +166,8 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {
-		if (key->source_type == cur->key.source_type &&
-		    key->target_type == cur->key.target_type &&
-		    key->target_class == cur->key.target_class &&
-		    (specified & cur->key.specified))
-			break;
-		if (key->source_type < cur->key.source_type)
-			break;
-		if (key->source_type == cur->key.source_type &&
-		    key->target_type < cur->key.target_type)
-			break;
-		if (key->source_type == cur->key.source_type &&
-		    key->target_type == cur->key.target_type &&
-		    key->target_class < cur->key.target_class)
+		cmp = avtab_node_cmp(key, &cur->key);
+		if (cmp <= 0)
 			break;
 	}
 	return avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue],
@@ -183,7 +182,7 @@ struct avtab_node *avtab_search_node(struct avtab *h,
 {
 	u32 hvalue;
 	struct avtab_node *cur;
-	u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
+	int cmp;
 
 	if (!h || !h->nslot)
 		return NULL;
@@ -191,20 +190,10 @@ struct avtab_node *avtab_search_node(struct avtab *h,
 	hvalue = avtab_hash(key, h->mask);
 	for (cur = h->htable[hvalue]; cur;
 	     cur = cur->next) {
-		if (key->source_type == cur->key.source_type &&
-		    key->target_type == cur->key.target_type &&
-		    key->target_class == cur->key.target_class &&
-		    (specified & cur->key.specified))
+		cmp = avtab_node_cmp(key, &cur->key);
+		if (cmp == 0)
 			return cur;
-
-		if (key->source_type < cur->key.source_type)
-			break;
-		if (key->source_type == cur->key.source_type &&
-		    key->target_type < cur->key.target_type)
-			break;
-		if (key->source_type == cur->key.source_type &&
-		    key->target_type == cur->key.target_type &&
-		    key->target_class < cur->key.target_class)
+		if (cmp < 0)
 			break;
 	}
 	return NULL;
@@ -213,27 +202,19 @@ struct avtab_node *avtab_search_node(struct avtab *h,
 struct avtab_node*
 avtab_search_node_next(struct avtab_node *node, u16 specified)
 {
+	struct avtab_key tmp_key;
 	struct avtab_node *cur;
+	int cmp;
 
 	if (!node)
 		return NULL;
-
-	specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
+	tmp_key = node->key;
+	tmp_key.specified = specified;
 	for (cur = node->next; cur; cur = cur->next) {
-		if (node->key.source_type == cur->key.source_type &&
-		    node->key.target_type == cur->key.target_type &&
-		    node->key.target_class == cur->key.target_class &&
-		    (specified & cur->key.specified))
+		cmp = avtab_node_cmp(&tmp_key, &cur->key);
+		if (cmp == 0)
 			return cur;
-
-		if (node->key.source_type < cur->key.source_type)
-			break;
-		if (node->key.source_type == cur->key.source_type &&
-		    node->key.target_type < cur->key.target_type)
-			break;
-		if (node->key.source_type == cur->key.source_type &&
-		    node->key.target_type == cur->key.target_type &&
-		    node->key.target_class < cur->key.target_class)
+		if (cmp < 0)
 			break;
 	}
 	return NULL;
-- 
2.41.0

Re: [PATCH v3 1/3] selinux: refactor avtab_node comparisons

[Stephen Smalley]

On Wed, Oct 18, 2023 at 1:58 PM Jacob Satterfield
<jsatterfield.linux@gmail.com> wrote:
>
> In four separate functions within avtab, the same comparison logic is
> used. The only difference is how the result is handled or whether there
> is a unique specifier value to be checked for or used.
>
> Extracting this functionality into the avtab_node_cmp() function unifies
> the comparison logic between searching and insertion and gets rid of
> duplicative code so that the implementation is easier to maintain.
>
> Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com>
> Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Nit: You can't retain a Reviewed-by line if you make any changes to
the previously reviewed patch.
That said, having re-reviewed this one, you can add my Reviewed-by tag
to your next one if there are no changes.

> ---
>  security/selinux/ss/avtab.c | 101 +++++++++++++++---------------------
>  1 file changed, 41 insertions(+), 60 deletions(-)
>
> diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
> index 8751a602ead2..697eb4352439 100644
> --- a/security/selinux/ss/avtab.c
> +++ b/security/selinux/ss/avtab.c
> @@ -96,12 +96,34 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst,
>         return newnode;
>  }
>
> +static int avtab_node_cmp(const struct avtab_key *key1,
> +                         const struct avtab_key *key2)
> +{
> +       u16 specified = key1->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> +
> +       if (key1->source_type == key2->source_type &&
> +           key1->target_type == key2->target_type &&
> +           key1->target_class == key2->target_class &&
> +           (specified & key2->specified))
> +               return 0;
> +       if (key1->source_type < key2->source_type)
> +               return -1;
> +       if (key1->source_type == key2->source_type &&
> +           key1->target_type < key2->target_type)
> +               return -1;
> +       if (key1->source_type == key2->source_type &&
> +           key1->target_type == key2->target_type &&
> +           key1->target_class < key2->target_class)
> +               return -1;
> +       return 1;
> +}
> +
>  static int avtab_insert(struct avtab *h, const struct avtab_key *key,
>                         const struct avtab_datum *datum)
>  {
>         u32 hvalue;
>         struct avtab_node *prev, *cur, *newnode;
> -       u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> +       int cmp;
>
>         if (!h || !h->nslot || h->nel == U32_MAX)
>                 return -EINVAL;
> @@ -110,23 +132,11 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key,
>         for (prev = NULL, cur = h->htable[hvalue];
>              cur;
>              prev = cur, cur = cur->next) {
> -               if (key->source_type == cur->key.source_type &&
> -                   key->target_type == cur->key.target_type &&
> -                   key->target_class == cur->key.target_class &&
> -                   (specified & cur->key.specified)) {
> -                       /* extended perms may not be unique */
> -                       if (specified & AVTAB_XPERMS)
> -                               break;
> +               cmp = avtab_node_cmp(key, &cur->key);
> +               /* extended perms may not be unique */
> +               if (cmp == 0 && !(key->specified & AVTAB_XPERMS))
>                         return -EEXIST;
> -               }
> -               if (key->source_type < cur->key.source_type)
> -                       break;
> -               if (key->source_type == cur->key.source_type &&
> -                   key->target_type < cur->key.target_type)
> -                       break;
> -               if (key->source_type == cur->key.source_type &&
> -                   key->target_type == cur->key.target_type &&
> -                   key->target_class < cur->key.target_class)
> +               if (cmp <= 0)
>                         break;
>         }
>
> @@ -148,7 +158,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
>  {
>         u32 hvalue;
>         struct avtab_node *prev, *cur;
> -       u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> +       int cmp;
>
>         if (!h || !h->nslot || h->nel == U32_MAX)
>                 return NULL;
> @@ -156,19 +166,8 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
>         for (prev = NULL, cur = h->htable[hvalue];
>              cur;
>              prev = cur, cur = cur->next) {
> -               if (key->source_type == cur->key.source_type &&
> -                   key->target_type == cur->key.target_type &&
> -                   key->target_class == cur->key.target_class &&
> -                   (specified & cur->key.specified))
> -                       break;
> -               if (key->source_type < cur->key.source_type)
> -                       break;
> -               if (key->source_type == cur->key.source_type &&
> -                   key->target_type < cur->key.target_type)
> -                       break;
> -               if (key->source_type == cur->key.source_type &&
> -                   key->target_type == cur->key.target_type &&
> -                   key->target_class < cur->key.target_class)
> +               cmp = avtab_node_cmp(key, &cur->key);
> +               if (cmp <= 0)
>                         break;
>         }
>         return avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue],
> @@ -183,7 +182,7 @@ struct avtab_node *avtab_search_node(struct avtab *h,
>  {
>         u32 hvalue;
>         struct avtab_node *cur;
> -       u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> +       int cmp;
>
>         if (!h || !h->nslot)
>                 return NULL;
> @@ -191,20 +190,10 @@ struct avtab_node *avtab_search_node(struct avtab *h,
>         hvalue = avtab_hash(key, h->mask);
>         for (cur = h->htable[hvalue]; cur;
>              cur = cur->next) {
> -               if (key->source_type == cur->key.source_type &&
> -                   key->target_type == cur->key.target_type &&
> -                   key->target_class == cur->key.target_class &&
> -                   (specified & cur->key.specified))
> +               cmp = avtab_node_cmp(key, &cur->key);
> +               if (cmp == 0)
>                         return cur;
> -
> -               if (key->source_type < cur->key.source_type)
> -                       break;
> -               if (key->source_type == cur->key.source_type &&
> -                   key->target_type < cur->key.target_type)
> -                       break;
> -               if (key->source_type == cur->key.source_type &&
> -                   key->target_type == cur->key.target_type &&
> -                   key->target_class < cur->key.target_class)
> +               if (cmp < 0)
>                         break;
>         }
>         return NULL;
> @@ -213,27 +202,19 @@ struct avtab_node *avtab_search_node(struct avtab *h,
>  struct avtab_node*
>  avtab_search_node_next(struct avtab_node *node, u16 specified)
>  {
> +       struct avtab_key tmp_key;
>         struct avtab_node *cur;
> +       int cmp;
>
>         if (!node)
>                 return NULL;
> -
> -       specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> +       tmp_key = node->key;
> +       tmp_key.specified = specified;
>         for (cur = node->next; cur; cur = cur->next) {
> -               if (node->key.source_type == cur->key.source_type &&
> -                   node->key.target_type == cur->key.target_type &&
> -                   node->key.target_class == cur->key.target_class &&
> -                   (specified & cur->key.specified))
> +               cmp = avtab_node_cmp(&tmp_key, &cur->key);
> +               if (cmp == 0)
>                         return cur;
> -
> -               if (node->key.source_type < cur->key.source_type)
> -                       break;
> -               if (node->key.source_type == cur->key.source_type &&
> -                   node->key.target_type < cur->key.target_type)
> -                       break;
> -               if (node->key.source_type == cur->key.source_type &&
> -                   node->key.target_type == cur->key.target_type &&
> -                   node->key.target_class < cur->key.target_class)
> +               if (cmp < 0)
>                         break;
>         }
>         return NULL;
> --
> 2.41.0
>

Re: [PATCH v3 1/3] selinux: refactor avtab_node comparisons

[Jacob Satterfield]

On Fri, Oct 20, 2023 at 9:52 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Wed, Oct 18, 2023 at 1:58 PM Jacob Satterfield
> <jsatterfield.linux@gmail.com> wrote:
> >
> > In four separate functions within avtab, the same comparison logic is
> > used. The only difference is how the result is handled or whether there
> > is a unique specifier value to be checked for or used.
> >
> > Extracting this functionality into the avtab_node_cmp() function unifies
> > the comparison logic between searching and insertion and gets rid of
> > duplicative code so that the implementation is easier to maintain.
> >
> > Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com>
> > Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
>
> Nit: You can't retain a Reviewed-by line if you make any changes to
> the previously reviewed patch.
> That said, having re-reviewed this one, you can add my Reviewed-by tag
> to your next one if there are no changes.
>

My apologies. Understood for the future.

Thanks for the re-review.

> > ---
> >  security/selinux/ss/avtab.c | 101 +++++++++++++++---------------------
> >  1 file changed, 41 insertions(+), 60 deletions(-)
> >
> > diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
> > index 8751a602ead2..697eb4352439 100644
> > --- a/security/selinux/ss/avtab.c
> > +++ b/security/selinux/ss/avtab.c
> > @@ -96,12 +96,34 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst,
> >         return newnode;
> >  }
> >
> > +static int avtab_node_cmp(const struct avtab_key *key1,
> > +                         const struct avtab_key *key2)
> > +{
> > +       u16 specified = key1->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > +
> > +       if (key1->source_type == key2->source_type &&
> > +           key1->target_type == key2->target_type &&
> > +           key1->target_class == key2->target_class &&
> > +           (specified & key2->specified))
> > +               return 0;
> > +       if (key1->source_type < key2->source_type)
> > +               return -1;
> > +       if (key1->source_type == key2->source_type &&
> > +           key1->target_type < key2->target_type)
> > +               return -1;
> > +       if (key1->source_type == key2->source_type &&
> > +           key1->target_type == key2->target_type &&
> > +           key1->target_class < key2->target_class)
> > +               return -1;
> > +       return 1;
> > +}
> > +
> >  static int avtab_insert(struct avtab *h, const struct avtab_key *key,
> >                         const struct avtab_datum *datum)
> >  {
> >         u32 hvalue;
> >         struct avtab_node *prev, *cur, *newnode;
> > -       u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > +       int cmp;
> >
> >         if (!h || !h->nslot || h->nel == U32_MAX)
> >                 return -EINVAL;
> > @@ -110,23 +132,11 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key,
> >         for (prev = NULL, cur = h->htable[hvalue];
> >              cur;
> >              prev = cur, cur = cur->next) {
> > -               if (key->source_type == cur->key.source_type &&
> > -                   key->target_type == cur->key.target_type &&
> > -                   key->target_class == cur->key.target_class &&
> > -                   (specified & cur->key.specified)) {
> > -                       /* extended perms may not be unique */
> > -                       if (specified & AVTAB_XPERMS)
> > -                               break;
> > +               cmp = avtab_node_cmp(key, &cur->key);
> > +               /* extended perms may not be unique */
> > +               if (cmp == 0 && !(key->specified & AVTAB_XPERMS))
> >                         return -EEXIST;
> > -               }
> > -               if (key->source_type < cur->key.source_type)
> > -                       break;
> > -               if (key->source_type == cur->key.source_type &&
> > -                   key->target_type < cur->key.target_type)
> > -                       break;
> > -               if (key->source_type == cur->key.source_type &&
> > -                   key->target_type == cur->key.target_type &&
> > -                   key->target_class < cur->key.target_class)
> > +               if (cmp <= 0)
> >                         break;
> >         }
> >
> > @@ -148,7 +158,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
> >  {
> >         u32 hvalue;
> >         struct avtab_node *prev, *cur;
> > -       u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > +       int cmp;
> >
> >         if (!h || !h->nslot || h->nel == U32_MAX)
> >                 return NULL;
> > @@ -156,19 +166,8 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
> >         for (prev = NULL, cur = h->htable[hvalue];
> >              cur;
> >              prev = cur, cur = cur->next) {
> > -               if (key->source_type == cur->key.source_type &&
> > -                   key->target_type == cur->key.target_type &&
> > -                   key->target_class == cur->key.target_class &&
> > -                   (specified & cur->key.specified))
> > -                       break;
> > -               if (key->source_type < cur->key.source_type)
> > -                       break;
> > -               if (key->source_type == cur->key.source_type &&
> > -                   key->target_type < cur->key.target_type)
> > -                       break;
> > -               if (key->source_type == cur->key.source_type &&
> > -                   key->target_type == cur->key.target_type &&
> > -                   key->target_class < cur->key.target_class)
> > +               cmp = avtab_node_cmp(key, &cur->key);
> > +               if (cmp <= 0)
> >                         break;
> >         }
> >         return avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue],
> > @@ -183,7 +182,7 @@ struct avtab_node *avtab_search_node(struct avtab *h,
> >  {
> >         u32 hvalue;
> >         struct avtab_node *cur;
> > -       u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > +       int cmp;
> >
> >         if (!h || !h->nslot)
> >                 return NULL;
> > @@ -191,20 +190,10 @@ struct avtab_node *avtab_search_node(struct avtab *h,
> >         hvalue = avtab_hash(key, h->mask);
> >         for (cur = h->htable[hvalue]; cur;
> >              cur = cur->next) {
> > -               if (key->source_type == cur->key.source_type &&
> > -                   key->target_type == cur->key.target_type &&
> > -                   key->target_class == cur->key.target_class &&
> > -                   (specified & cur->key.specified))
> > +               cmp = avtab_node_cmp(key, &cur->key);
> > +               if (cmp == 0)
> >                         return cur;
> > -
> > -               if (key->source_type < cur->key.source_type)
> > -                       break;
> > -               if (key->source_type == cur->key.source_type &&
> > -                   key->target_type < cur->key.target_type)
> > -                       break;
> > -               if (key->source_type == cur->key.source_type &&
> > -                   key->target_type == cur->key.target_type &&
> > -                   key->target_class < cur->key.target_class)
> > +               if (cmp < 0)
> >                         break;
> >         }
> >         return NULL;
> > @@ -213,27 +202,19 @@ struct avtab_node *avtab_search_node(struct avtab *h,
> >  struct avtab_node*
> >  avtab_search_node_next(struct avtab_node *node, u16 specified)
> >  {
> > +       struct avtab_key tmp_key;
> >         struct avtab_node *cur;
> > +       int cmp;
> >
> >         if (!node)
> >                 return NULL;
> > -
> > -       specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > +       tmp_key = node->key;
> > +       tmp_key.specified = specified;
> >         for (cur = node->next; cur; cur = cur->next) {
> > -               if (node->key.source_type == cur->key.source_type &&
> > -                   node->key.target_type == cur->key.target_type &&
> > -                   node->key.target_class == cur->key.target_class &&
> > -                   (specified & cur->key.specified))
> > +               cmp = avtab_node_cmp(&tmp_key, &cur->key);
> > +               if (cmp == 0)
> >                         return cur;
> > -
> > -               if (node->key.source_type < cur->key.source_type)
> > -                       break;
> > -               if (node->key.source_type == cur->key.source_type &&
> > -                   node->key.target_type < cur->key.target_type)
> > -                       break;
> > -               if (node->key.source_type == cur->key.source_type &&
> > -                   node->key.target_type == cur->key.target_type &&
> > -                   node->key.target_class < cur->key.target_class)
> > +               if (cmp < 0)
> >                         break;
> >         }
> >         return NULL;
> > --
> > 2.41.0
> >

[PATCH v3 2/3] selinux: avtab iteration macros

[Jacob Satterfield]

Similar to the list_for_each macros in list.h, this patch adds two
macros that iterates an avtab_node linked list (avtab_chain_for_each and
avtab_chain_for_each_prev). This has two benefits: it reduces the amount
of duplicative code for iteration and it makes changes to the underlying
hashtable data structure easier as there are fewer places to update.

Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com>
---
 security/selinux/ss/avtab.c | 28 ++++++++++++----------------
 1 file changed, 12 insertions(+), 16 deletions(-)

diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 697eb4352439..f0d448e7807a 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -27,6 +27,13 @@
 static struct kmem_cache *avtab_node_cachep __ro_after_init;
 static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
 
+#define avtab_chain_for_each(pos, tab, slot) \
+	for (pos = (tab)->htable[slot]; pos; pos = pos->next)
+
+#define avtab_chain_for_each_prev(pos, prev, tab, slot) \
+	for (prev = NULL, pos = (tab)->htable[slot]; pos; \
+	prev = pos, pos = pos->next)
+
 /* Based on MurmurHash3, written by Austin Appleby and placed in the
  * public domain.
  */
@@ -129,9 +136,7 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key,
 		return -EINVAL;
 
 	hvalue = avtab_hash(key, h->mask);
-	for (prev = NULL, cur = h->htable[hvalue];
-	     cur;
-	     prev = cur, cur = cur->next) {
+	avtab_chain_for_each_prev(cur, prev, h, hvalue) {
 		cmp = avtab_node_cmp(key, &cur->key);
 		/* extended perms may not be unique */
 		if (cmp == 0 && !(key->specified & AVTAB_XPERMS))
@@ -163,9 +168,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
 	if (!h || !h->nslot || h->nel == U32_MAX)
 		return NULL;
 	hvalue = avtab_hash(key, h->mask);
-	for (prev = NULL, cur = h->htable[hvalue];
-	     cur;
-	     prev = cur, cur = cur->next) {
+	avtab_chain_for_each_prev(cur, prev, h, hvalue) {
 		cmp = avtab_node_cmp(key, &cur->key);
 		if (cmp <= 0)
 			break;
@@ -180,16 +183,13 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
 struct avtab_node *avtab_search_node(struct avtab *h,
 				     const struct avtab_key *key)
 {
-	u32 hvalue;
 	struct avtab_node *cur;
 	int cmp;
 
 	if (!h || !h->nslot)
 		return NULL;
 
-	hvalue = avtab_hash(key, h->mask);
-	for (cur = h->htable[hvalue]; cur;
-	     cur = cur->next) {
+	avtab_chain_for_each(cur, h, avtab_hash(key, h->mask)) {
 		cmp = avtab_node_cmp(key, &cur->key);
 		if (cmp == 0)
 			return cur;
@@ -229,7 +229,6 @@ void avtab_destroy(struct avtab *h)
 		return;
 
 	for (i = 0; i < h->nslot; i++) {
-		cur = h->htable[i];
 		while (cur) {
 			temp = cur;
 			cur = cur->next;
@@ -307,10 +306,8 @@ void avtab_hash_eval(struct avtab *h, const char *tag)
 		if (cur) {
 			slots_used++;
 			chain_len = 0;
-			while (cur) {
+			avtab_chain_for_each(cur, h, i)
 				chain_len++;
-				cur = cur->next;
-			}
 
 			if (chain_len > max_chain_len)
 				max_chain_len = chain_len;
@@ -593,8 +590,7 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp)
 		return rc;
 
 	for (i = 0; i < a->nslot; i++) {
-		for (cur = a->htable[i]; cur;
-		     cur = cur->next) {
+		avtab_chain_for_each(cur, a, i) {
 			rc = avtab_write_item(p, cur, fp);
 			if (rc)
 				return rc;
-- 
2.41.0

Re: [PATCH v3 2/3] selinux: avtab iteration macros

[Jacob Satterfield]

On Wed, Oct 18, 2023 at 1:58 PM Jacob Satterfield
<jsatterfield.linux@gmail.com> wrote:
>
> Similar to the list_for_each macros in list.h, this patch adds two
> macros that iterates an avtab_node linked list (avtab_chain_for_each and
> avtab_chain_for_each_prev). This has two benefits: it reduces the amount
> of duplicative code for iteration and it makes changes to the underlying
> hashtable data structure easier as there are fewer places to update.
>
> Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com>
> ---
>  security/selinux/ss/avtab.c | 28 ++++++++++++----------------
>  1 file changed, 12 insertions(+), 16 deletions(-)
>
> diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
> index 697eb4352439..f0d448e7807a 100644
> --- a/security/selinux/ss/avtab.c
> +++ b/security/selinux/ss/avtab.c
> @@ -27,6 +27,13 @@
>  static struct kmem_cache *avtab_node_cachep __ro_after_init;
>  static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
>
> +#define avtab_chain_for_each(pos, tab, slot) \
> +       for (pos = (tab)->htable[slot]; pos; pos = pos->next)
> +
> +#define avtab_chain_for_each_prev(pos, prev, tab, slot) \
> +       for (prev = NULL, pos = (tab)->htable[slot]; pos; \
> +       prev = pos, pos = pos->next)
> +
>  /* Based on MurmurHash3, written by Austin Appleby and placed in the
>   * public domain.
>   */
> @@ -129,9 +136,7 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key,
>                 return -EINVAL;
>
>         hvalue = avtab_hash(key, h->mask);
> -       for (prev = NULL, cur = h->htable[hvalue];
> -            cur;
> -            prev = cur, cur = cur->next) {
> +       avtab_chain_for_each_prev(cur, prev, h, hvalue) {
>                 cmp = avtab_node_cmp(key, &cur->key);
>                 /* extended perms may not be unique */
>                 if (cmp == 0 && !(key->specified & AVTAB_XPERMS))
> @@ -163,9 +168,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
>         if (!h || !h->nslot || h->nel == U32_MAX)
>                 return NULL;
>         hvalue = avtab_hash(key, h->mask);
> -       for (prev = NULL, cur = h->htable[hvalue];
> -            cur;
> -            prev = cur, cur = cur->next) {
> +       avtab_chain_for_each_prev(cur, prev, h, hvalue) {
>                 cmp = avtab_node_cmp(key, &cur->key);
>                 if (cmp <= 0)
>                         break;
> @@ -180,16 +183,13 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
>  struct avtab_node *avtab_search_node(struct avtab *h,
>                                      const struct avtab_key *key)
>  {
> -       u32 hvalue;
>         struct avtab_node *cur;
>         int cmp;
>
>         if (!h || !h->nslot)
>                 return NULL;
>
> -       hvalue = avtab_hash(key, h->mask);
> -       for (cur = h->htable[hvalue]; cur;
> -            cur = cur->next) {
> +       avtab_chain_for_each(cur, h, avtab_hash(key, h->mask)) {
>                 cmp = avtab_node_cmp(key, &cur->key);
>                 if (cmp == 0)
>                         return cur;
> @@ -229,7 +229,6 @@ void avtab_destroy(struct avtab *h)
>                 return;
>
>         for (i = 0; i < h->nslot; i++) {
> -               cur = h->htable[i];

This line can't be deleted. It will be restored in the next spin.

>                 while (cur) {
>                         temp = cur;
>                         cur = cur->next;
> @@ -307,10 +306,8 @@ void avtab_hash_eval(struct avtab *h, const char *tag)
>                 if (cur) {
>                         slots_used++;
>                         chain_len = 0;
> -                       while (cur) {
> +                       avtab_chain_for_each(cur, h, i)
>                                 chain_len++;
> -                               cur = cur->next;
> -                       }
>
>                         if (chain_len > max_chain_len)
>                                 max_chain_len = chain_len;
> @@ -593,8 +590,7 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp)
>                 return rc;
>
>         for (i = 0; i < a->nslot; i++) {
> -               for (cur = a->htable[i]; cur;
> -                    cur = cur->next) {
> +               avtab_chain_for_each(cur, a, i) {
>                         rc = avtab_write_item(p, cur, fp);
>                         if (rc)
>                                 return rc;
> --
> 2.41.0
>

[PATCH v3 3/3] selinux: use arrays for avtab hashtable nodes

[Jacob Satterfield]

The current avtab hashtable employs a separate chaining collision
resolution strategy where each bucket/chain holds an ordered linked list
of pointers to kmem_cache allocated avtab_node elements.

On Fedora 38 (x86_64) using the default policy, avtab_node_cachep
uses 573 slabs each containing 170 objects totaling 2,337,840 bytes.
A call to kmem_cache_zalloc() is required for every single rule, which
in the default policy is currently 96,730 and continually rising.

When both sets of avtab_node (regular and cond.) are turned into arrays
with the hash table slot indexing into it rather than a pointer, then
this results in only 2 additional kvcalloc() calls and the complete
removal of the kmem_cache itself.

Due to how conditional rules are written in the binary policy, the
code responsible for loading does not know how many conditional rules
there are before creating the avtab structure. Instead, it was using the
number of elements in the non-conditional avtab as a hint and allocates
the hash table based on it. Therefore, a two-pass algorithm is now used
to calculate the rule count before allocating the avtab nodes array.
With the current refpolicy and default Fedora policy, this causes the
number of hash slots for the conditional array to become 4096 instead of
32768. This results in a savings of 224KB of heap memory.

The caching characteristics of iterating a single array are better due
to locality of reference. Running "perf stat -r 100 -d load_policy"
has shown a runtime reduction of around 10% on a Fedora 38 x86_64 VM
with this single patch. Future patches focused on improving the hash
table's collision resolution strategy and array layout (struct-of-arrays
vs. array-of-structs) may elicit even more caching and therefore runtime
performance improvements.

Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com>
---
 security/selinux/ss/avtab.c       | 47 ++++++++++++++++++++-----------
 security/selinux/ss/avtab.h       |  4 ++-
 security/selinux/ss/conditional.c | 37 ++++++++++++++++--------
 security/selinux/ss/conditional.h |  2 +-
 4 files changed, 59 insertions(+), 31 deletions(-)

diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index f0d448e7807a..aabe04fc4d04 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -24,7 +24,6 @@
 #include "avtab.h"
 #include "policydb.h"
 
-static struct kmem_cache *avtab_node_cachep __ro_after_init;
 static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
 
 #define avtab_chain_for_each(pos, tab, slot) \
@@ -79,17 +78,15 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst,
 {
 	struct avtab_node *newnode;
 	struct avtab_extended_perms *xperms;
-	newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
-	if (newnode == NULL)
+	if (h->nel == h->nnodes)
 		return NULL;
+	newnode = &h->nodes[h->nel];
 	newnode->key = *key;
 
 	if (key->specified & AVTAB_XPERMS) {
 		xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL);
-		if (xperms == NULL) {
-			kmem_cache_free(avtab_node_cachep, newnode);
+		if (xperms == NULL)
 			return NULL;
-		}
 		*xperms = *(datum->u.xperms);
 		newnode->datum.u.xperms = xperms;
 	} else {
@@ -235,11 +232,13 @@ void avtab_destroy(struct avtab *h)
 			if (temp->key.specified & AVTAB_XPERMS)
 				kmem_cache_free(avtab_xperms_cachep,
 						temp->datum.u.xperms);
-			kmem_cache_free(avtab_node_cachep, temp);
 		}
 	}
 	kvfree(h->htable);
+	kvfree(h->nodes);
 	h->htable = NULL;
+	h->nodes = NULL;
+	h->nnodes = 0;
 	h->nel = 0;
 	h->nslot = 0;
 	h->mask = 0;
@@ -248,20 +247,28 @@ void avtab_destroy(struct avtab *h)
 void avtab_init(struct avtab *h)
 {
 	h->htable = NULL;
+	h->nodes = NULL;
+	h->nnodes = 0;
 	h->nel = 0;
 	h->nslot = 0;
 	h->mask = 0;
 }
 
-static int avtab_alloc_common(struct avtab *h, u32 nslot)
+static int avtab_alloc_common(struct avtab *h, u32 nslot, u32 nrules)
 {
 	if (!nslot)
 		return 0;
 
-	h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL);
+	h->htable = kvcalloc(nslot, sizeof(*h->htable), GFP_KERNEL);
 	if (!h->htable)
 		return -ENOMEM;
-
+	h->nodes = kvcalloc(nrules, sizeof(*h->nodes), GFP_KERNEL);
+	if (!h->nodes) {
+		kvfree(h->htable);
+		h->htable = NULL;
+		return -ENOMEM;
+	}
+	h->nnodes = nrules;
 	h->nslot = nslot;
 	h->mask = nslot - 1;
 	return 0;
@@ -277,7 +284,7 @@ int avtab_alloc(struct avtab *h, u32 nrules)
 		if (nslot > MAX_AVTAB_HASH_BUCKETS)
 			nslot = MAX_AVTAB_HASH_BUCKETS;
 
-		rc = avtab_alloc_common(h, nslot);
+		rc = avtab_alloc_common(h, nslot, nrules);
 		if (rc)
 			return rc;
 	}
@@ -288,7 +295,7 @@ int avtab_alloc(struct avtab *h, u32 nrules)
 
 int avtab_alloc_dup(struct avtab *new, const struct avtab *orig)
 {
-	return avtab_alloc_common(new, orig->nslot);
+	return avtab_alloc_common(new, orig->nslot, orig->nel);
 }
 
 #ifdef CONFIG_SECURITY_SELINUX_DEBUG
@@ -337,7 +344,7 @@ static const uint16_t spec_order[] = {
 int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		    int (*insertf)(struct avtab *a, const struct avtab_key *k,
 				   const struct avtab_datum *d, void *p),
-		    void *p)
+		    void *p, u32 *nrules)
 {
 	__le16 buf16[4];
 	u16 enabled;
@@ -411,6 +418,10 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 			if (val & spec_order[i]) {
 				key.specified = spec_order[i] | enabled;
 				datum.u.data = le32_to_cpu(buf32[items++]);
+				if (nrules) {
+					(*nrules)++;
+					continue;
+				}
 				rc = insertf(a, &key, &datum, p);
 				if (rc)
 					return rc;
@@ -489,6 +500,11 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		pr_err("SELinux: avtab: invalid type\n");
 		return -EINVAL;
 	}
+
+	if (nrules) {
+		(*nrules)++;
+		return 0;
+	}
 	return insertf(a, &key, &datum, p);
 }
 
@@ -522,7 +538,7 @@ int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
 		goto bad;
 
 	for (i = 0; i < nel; i++) {
-		rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
+		rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL, NULL);
 		if (rc) {
 			if (rc == -ENOMEM)
 				pr_err("SELinux: avtab: out of memory\n");
@@ -602,9 +618,6 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp)
 
 void __init avtab_cache_init(void)
 {
-	avtab_node_cachep = kmem_cache_create("avtab_node",
-					      sizeof(struct avtab_node),
-					      0, SLAB_PANIC, NULL);
 	avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms",
 						sizeof(struct avtab_extended_perms),
 						0, SLAB_PANIC, NULL);
diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index 3c3904bf02b0..5e465be6f057 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -82,6 +82,8 @@ struct avtab_node {
 
 struct avtab {
 	struct avtab_node **htable;
+	struct avtab_node *nodes;
+	u32 nnodes;	/* number of nodes */
 	u32 nel;	/* number of elements */
 	u32 nslot;      /* number of hash slots */
 	u32 mask;       /* mask to compute hash func */
@@ -104,7 +106,7 @@ struct policydb;
 int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		    int (*insert)(struct avtab *a, const struct avtab_key *k,
 				  const struct avtab_datum *d, void *p),
-		    void *p);
+		    void *p, u32 *nrules);
 
 int avtab_read(struct avtab *a, void *fp, struct policydb *pol);
 int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp);
diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c
index 81ff676f209a..bbd35b35b79d 100644
--- a/security/selinux/ss/conditional.c
+++ b/security/selinux/ss/conditional.c
@@ -140,7 +140,7 @@ void cond_policydb_init(struct policydb *p)
 static void cond_node_destroy(struct cond_node *node)
 {
 	kfree(node->expr.nodes);
-	/* the avtab_ptr_t nodes are destroyed by the avtab */
+	/* the actual nodes were destroyed by avtab_destroy() */
 	kfree(node->true_list.nodes);
 	kfree(node->false_list.nodes);
 }
@@ -323,7 +323,8 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k,
 
 static int cond_read_av_list(struct policydb *p, void *fp,
 			     struct cond_av_list *list,
-			     struct cond_av_list *other)
+			     struct cond_av_list *other,
+			     u32 *nrules)
 {
 	int rc;
 	__le32 buf[1];
@@ -347,7 +348,7 @@ static int cond_read_av_list(struct policydb *p, void *fp,
 	for (i = 0; i < len; i++) {
 		data.dst = &list->nodes[i];
 		rc = avtab_read_item(&p->te_cond_avtab, fp, p, cond_insertf,
-				     &data);
+				     &data, nrules);
 		if (rc) {
 			kfree(list->nodes);
 			list->nodes = NULL;
@@ -373,7 +374,8 @@ static int expr_node_isvalid(struct policydb *p, struct cond_expr_node *expr)
 	return 1;
 }
 
-static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp)
+static int cond_read_node(struct policydb *p, struct cond_node *node,
+			  void *fp, u32 *nrules)
 {
 	__le32 buf[2];
 	u32 i, len;
@@ -407,16 +409,17 @@ static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp)
 			return -EINVAL;
 	}
 
-	rc = cond_read_av_list(p, fp, &node->true_list, NULL);
+	rc = cond_read_av_list(p, fp, &node->true_list, NULL, nrules);
 	if (rc)
 		return rc;
-	return cond_read_av_list(p, fp, &node->false_list, &node->true_list);
+	return cond_read_av_list(p, fp, &node->false_list, &node->true_list, nrules);
 }
 
-int cond_read_list(struct policydb *p, void *fp)
+int cond_read_list(struct policydb *p, struct policy_file *fp)
 {
 	__le32 buf[1];
-	u32 i, len;
+	struct policy_file tmp_fp;
+	u32 i, len, nrules;
 	int rc;
 
 	rc = next_entry(buf, fp, sizeof(buf));
@@ -428,15 +431,25 @@ int cond_read_list(struct policydb *p, void *fp)
 	p->cond_list = kcalloc(len, sizeof(*p->cond_list), GFP_KERNEL);
 	if (!p->cond_list)
 		return -ENOMEM;
+	p->cond_list_len = len;
+
+	/* first pass to only calculate the avrule count */
+	tmp_fp = *fp;
+	nrules = 0;
+	for (i = 0; i < len; i++) {
+		rc = cond_read_node(p, &p->cond_list[i], &tmp_fp, &nrules);
+		if (rc)
+			goto err;
+		cond_node_destroy(&p->cond_list[i]);
+	}
 
-	rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel);
+	rc = avtab_alloc(&(p->te_cond_avtab), nrules);
 	if (rc)
 		goto err;
 
-	p->cond_list_len = len;
-
+	/* second pass to read in the conditional nodes */
 	for (i = 0; i < len; i++) {
-		rc = cond_read_node(p, &p->cond_list[i], fp);
+		rc = cond_read_node(p, &p->cond_list[i], fp, NULL);
 		if (rc)
 			goto err;
 	}
diff --git a/security/selinux/ss/conditional.h b/security/selinux/ss/conditional.h
index 5a7b51278dc6..62a12d00cac9 100644
--- a/security/selinux/ss/conditional.h
+++ b/security/selinux/ss/conditional.h
@@ -70,7 +70,7 @@ int cond_destroy_bool(void *key, void *datum, void *p);
 int cond_index_bool(void *key, void *datum, void *datap);
 
 int cond_read_bool(struct policydb *p, struct symtab *s, void *fp);
-int cond_read_list(struct policydb *p, void *fp);
+int cond_read_list(struct policydb *p, struct policy_file *fp);
 int cond_write_bool(void *key, void *datum, void *ptr);
 int cond_write_list(struct policydb *p, void *fp);
 
-- 
2.41.0

Re: [PATCH v3 3/3] selinux: use arrays for avtab hashtable nodes

[Stephen Smalley]

On Wed, Oct 18, 2023 at 1:58 PM Jacob Satterfield
<jsatterfield.linux@gmail.com> wrote:
>
> The current avtab hashtable employs a separate chaining collision
> resolution strategy where each bucket/chain holds an ordered linked list
> of pointers to kmem_cache allocated avtab_node elements.
>
> On Fedora 38 (x86_64) using the default policy, avtab_node_cachep
> uses 573 slabs each containing 170 objects totaling 2,337,840 bytes.
> A call to kmem_cache_zalloc() is required for every single rule, which
> in the default policy is currently 96,730 and continually rising.
>
> When both sets of avtab_node (regular and cond.) are turned into arrays
> with the hash table slot indexing into it rather than a pointer, then
> this results in only 2 additional kvcalloc() calls and the complete
> removal of the kmem_cache itself.
>
> Due to how conditional rules are written in the binary policy, the
> code responsible for loading does not know how many conditional rules
> there are before creating the avtab structure. Instead, it was using the
> number of elements in the non-conditional avtab as a hint and allocates
> the hash table based on it. Therefore, a two-pass algorithm is now used
> to calculate the rule count before allocating the avtab nodes array.
> With the current refpolicy and default Fedora policy, this causes the
> number of hash slots for the conditional array to become 4096 instead of
> 32768. This results in a savings of 224KB of heap memory.
>
> The caching characteristics of iterating a single array are better due
> to locality of reference. Running "perf stat -r 100 -d load_policy"
> has shown a runtime reduction of around 10% on a Fedora 38 x86_64 VM
> with this single patch. Future patches focused on improving the hash
> table's collision resolution strategy and array layout (struct-of-arrays
> vs. array-of-structs) may elicit even more caching and therefore runtime
> performance improvements.
>
> Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com>

Assuming you fix the previous patch,
Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>

> ---
>  security/selinux/ss/avtab.c       | 47 ++++++++++++++++++++-----------
>  security/selinux/ss/avtab.h       |  4 ++-
>  security/selinux/ss/conditional.c | 37 ++++++++++++++++--------
>  security/selinux/ss/conditional.h |  2 +-
>  4 files changed, 59 insertions(+), 31 deletions(-)
>
> diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
> index f0d448e7807a..aabe04fc4d04 100644
> --- a/security/selinux/ss/avtab.c
> +++ b/security/selinux/ss/avtab.c
> @@ -24,7 +24,6 @@
>  #include "avtab.h"
>  #include "policydb.h"
>
> -static struct kmem_cache *avtab_node_cachep __ro_after_init;
>  static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
>
>  #define avtab_chain_for_each(pos, tab, slot) \
> @@ -79,17 +78,15 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst,
>  {
>         struct avtab_node *newnode;
>         struct avtab_extended_perms *xperms;
> -       newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
> -       if (newnode == NULL)
> +       if (h->nel == h->nnodes)
>                 return NULL;
> +       newnode = &h->nodes[h->nel];
>         newnode->key = *key;
>
>         if (key->specified & AVTAB_XPERMS) {
>                 xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL);
> -               if (xperms == NULL) {
> -                       kmem_cache_free(avtab_node_cachep, newnode);
> +               if (xperms == NULL)
>                         return NULL;
> -               }
>                 *xperms = *(datum->u.xperms);
>                 newnode->datum.u.xperms = xperms;
>         } else {
> @@ -235,11 +232,13 @@ void avtab_destroy(struct avtab *h)
>                         if (temp->key.specified & AVTAB_XPERMS)
>                                 kmem_cache_free(avtab_xperms_cachep,
>                                                 temp->datum.u.xperms);
> -                       kmem_cache_free(avtab_node_cachep, temp);
>                 }
>         }
>         kvfree(h->htable);
> +       kvfree(h->nodes);
>         h->htable = NULL;
> +       h->nodes = NULL;
> +       h->nnodes = 0;
>         h->nel = 0;
>         h->nslot = 0;
>         h->mask = 0;
> @@ -248,20 +247,28 @@ void avtab_destroy(struct avtab *h)
>  void avtab_init(struct avtab *h)
>  {
>         h->htable = NULL;
> +       h->nodes = NULL;
> +       h->nnodes = 0;
>         h->nel = 0;
>         h->nslot = 0;
>         h->mask = 0;
>  }
>
> -static int avtab_alloc_common(struct avtab *h, u32 nslot)
> +static int avtab_alloc_common(struct avtab *h, u32 nslot, u32 nrules)
>  {
>         if (!nslot)
>                 return 0;
>
> -       h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL);
> +       h->htable = kvcalloc(nslot, sizeof(*h->htable), GFP_KERNEL);
>         if (!h->htable)
>                 return -ENOMEM;
> -
> +       h->nodes = kvcalloc(nrules, sizeof(*h->nodes), GFP_KERNEL);
> +       if (!h->nodes) {
> +               kvfree(h->htable);
> +               h->htable = NULL;
> +               return -ENOMEM;
> +       }
> +       h->nnodes = nrules;
>         h->nslot = nslot;
>         h->mask = nslot - 1;
>         return 0;
> @@ -277,7 +284,7 @@ int avtab_alloc(struct avtab *h, u32 nrules)
>                 if (nslot > MAX_AVTAB_HASH_BUCKETS)
>                         nslot = MAX_AVTAB_HASH_BUCKETS;
>
> -               rc = avtab_alloc_common(h, nslot);
> +               rc = avtab_alloc_common(h, nslot, nrules);
>                 if (rc)
>                         return rc;
>         }
> @@ -288,7 +295,7 @@ int avtab_alloc(struct avtab *h, u32 nrules)
>
>  int avtab_alloc_dup(struct avtab *new, const struct avtab *orig)
>  {
> -       return avtab_alloc_common(new, orig->nslot);
> +       return avtab_alloc_common(new, orig->nslot, orig->nel);
>  }
>
>  #ifdef CONFIG_SECURITY_SELINUX_DEBUG
> @@ -337,7 +344,7 @@ static const uint16_t spec_order[] = {
>  int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
>                     int (*insertf)(struct avtab *a, const struct avtab_key *k,
>                                    const struct avtab_datum *d, void *p),
> -                   void *p)
> +                   void *p, u32 *nrules)
>  {
>         __le16 buf16[4];
>         u16 enabled;
> @@ -411,6 +418,10 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
>                         if (val & spec_order[i]) {
>                                 key.specified = spec_order[i] | enabled;
>                                 datum.u.data = le32_to_cpu(buf32[items++]);
> +                               if (nrules) {
> +                                       (*nrules)++;
> +                                       continue;
> +                               }
>                                 rc = insertf(a, &key, &datum, p);
>                                 if (rc)
>                                         return rc;
> @@ -489,6 +500,11 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
>                 pr_err("SELinux: avtab: invalid type\n");
>                 return -EINVAL;
>         }
> +
> +       if (nrules) {
> +               (*nrules)++;
> +               return 0;
> +       }
>         return insertf(a, &key, &datum, p);
>  }
>
> @@ -522,7 +538,7 @@ int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
>                 goto bad;
>
>         for (i = 0; i < nel; i++) {
> -               rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
> +               rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL, NULL);
>                 if (rc) {
>                         if (rc == -ENOMEM)
>                                 pr_err("SELinux: avtab: out of memory\n");
> @@ -602,9 +618,6 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp)
>
>  void __init avtab_cache_init(void)
>  {
> -       avtab_node_cachep = kmem_cache_create("avtab_node",
> -                                             sizeof(struct avtab_node),
> -                                             0, SLAB_PANIC, NULL);
>         avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms",
>                                                 sizeof(struct avtab_extended_perms),
>                                                 0, SLAB_PANIC, NULL);
> diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
> index 3c3904bf02b0..5e465be6f057 100644
> --- a/security/selinux/ss/avtab.h
> +++ b/security/selinux/ss/avtab.h
> @@ -82,6 +82,8 @@ struct avtab_node {
>
>  struct avtab {
>         struct avtab_node **htable;
> +       struct avtab_node *nodes;
> +       u32 nnodes;     /* number of nodes */
>         u32 nel;        /* number of elements */
>         u32 nslot;      /* number of hash slots */
>         u32 mask;       /* mask to compute hash func */
> @@ -104,7 +106,7 @@ struct policydb;
>  int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
>                     int (*insert)(struct avtab *a, const struct avtab_key *k,
>                                   const struct avtab_datum *d, void *p),
> -                   void *p);
> +                   void *p, u32 *nrules);
>
>  int avtab_read(struct avtab *a, void *fp, struct policydb *pol);
>  int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp);
> diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c
> index 81ff676f209a..bbd35b35b79d 100644
> --- a/security/selinux/ss/conditional.c
> +++ b/security/selinux/ss/conditional.c
> @@ -140,7 +140,7 @@ void cond_policydb_init(struct policydb *p)
>  static void cond_node_destroy(struct cond_node *node)
>  {
>         kfree(node->expr.nodes);
> -       /* the avtab_ptr_t nodes are destroyed by the avtab */
> +       /* the actual nodes were destroyed by avtab_destroy() */
>         kfree(node->true_list.nodes);
>         kfree(node->false_list.nodes);
>  }
> @@ -323,7 +323,8 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k,
>
>  static int cond_read_av_list(struct policydb *p, void *fp,
>                              struct cond_av_list *list,
> -                            struct cond_av_list *other)
> +                            struct cond_av_list *other,
> +                            u32 *nrules)
>  {
>         int rc;
>         __le32 buf[1];
> @@ -347,7 +348,7 @@ static int cond_read_av_list(struct policydb *p, void *fp,
>         for (i = 0; i < len; i++) {
>                 data.dst = &list->nodes[i];
>                 rc = avtab_read_item(&p->te_cond_avtab, fp, p, cond_insertf,
> -                                    &data);
> +                                    &data, nrules);
>                 if (rc) {
>                         kfree(list->nodes);
>                         list->nodes = NULL;
> @@ -373,7 +374,8 @@ static int expr_node_isvalid(struct policydb *p, struct cond_expr_node *expr)
>         return 1;
>  }
>
> -static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp)
> +static int cond_read_node(struct policydb *p, struct cond_node *node,
> +                         void *fp, u32 *nrules)
>  {
>         __le32 buf[2];
>         u32 i, len;
> @@ -407,16 +409,17 @@ static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp)
>                         return -EINVAL;
>         }
>
> -       rc = cond_read_av_list(p, fp, &node->true_list, NULL);
> +       rc = cond_read_av_list(p, fp, &node->true_list, NULL, nrules);
>         if (rc)
>                 return rc;
> -       return cond_read_av_list(p, fp, &node->false_list, &node->true_list);
> +       return cond_read_av_list(p, fp, &node->false_list, &node->true_list, nrules);
>  }
>
> -int cond_read_list(struct policydb *p, void *fp)
> +int cond_read_list(struct policydb *p, struct policy_file *fp)
>  {
>         __le32 buf[1];
> -       u32 i, len;
> +       struct policy_file tmp_fp;
> +       u32 i, len, nrules;
>         int rc;
>
>         rc = next_entry(buf, fp, sizeof(buf));
> @@ -428,15 +431,25 @@ int cond_read_list(struct policydb *p, void *fp)
>         p->cond_list = kcalloc(len, sizeof(*p->cond_list), GFP_KERNEL);
>         if (!p->cond_list)
>                 return -ENOMEM;
> +       p->cond_list_len = len;
> +
> +       /* first pass to only calculate the avrule count */
> +       tmp_fp = *fp;
> +       nrules = 0;
> +       for (i = 0; i < len; i++) {
> +               rc = cond_read_node(p, &p->cond_list[i], &tmp_fp, &nrules);
> +               if (rc)
> +                       goto err;
> +               cond_node_destroy(&p->cond_list[i]);
> +       }
>
> -       rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel);
> +       rc = avtab_alloc(&(p->te_cond_avtab), nrules);
>         if (rc)
>                 goto err;
>
> -       p->cond_list_len = len;
> -
> +       /* second pass to read in the conditional nodes */
>         for (i = 0; i < len; i++) {
> -               rc = cond_read_node(p, &p->cond_list[i], fp);
> +               rc = cond_read_node(p, &p->cond_list[i], fp, NULL);
>                 if (rc)
>                         goto err;
>         }
> diff --git a/security/selinux/ss/conditional.h b/security/selinux/ss/conditional.h
> index 5a7b51278dc6..62a12d00cac9 100644
> --- a/security/selinux/ss/conditional.h
> +++ b/security/selinux/ss/conditional.h
> @@ -70,7 +70,7 @@ int cond_destroy_bool(void *key, void *datum, void *p);
>  int cond_index_bool(void *key, void *datum, void *datap);
>
>  int cond_read_bool(struct policydb *p, struct symtab *s, void *fp);
> -int cond_read_list(struct policydb *p, void *fp);
> +int cond_read_list(struct policydb *p, struct policy_file *fp);
>  int cond_write_bool(void *key, void *datum, void *ptr);
>  int cond_write_list(struct policydb *p, void *fp);
>
> --
> 2.41.0
>

Re: [PATCH v3 3/3] selinux: use arrays for avtab hashtable nodes

[Jacob Satterfield]

On Fri, Oct 20, 2023 at 10:00 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Wed, Oct 18, 2023 at 1:58 PM Jacob Satterfield
> <jsatterfield.linux@gmail.com> wrote:
> >
> > The current avtab hashtable employs a separate chaining collision
> > resolution strategy where each bucket/chain holds an ordered linked list
> > of pointers to kmem_cache allocated avtab_node elements.
> >
> > On Fedora 38 (x86_64) using the default policy, avtab_node_cachep
> > uses 573 slabs each containing 170 objects totaling 2,337,840 bytes.
> > A call to kmem_cache_zalloc() is required for every single rule, which
> > in the default policy is currently 96,730 and continually rising.
> >
> > When both sets of avtab_node (regular and cond.) are turned into arrays
> > with the hash table slot indexing into it rather than a pointer, then
> > this results in only 2 additional kvcalloc() calls and the complete
> > removal of the kmem_cache itself.
> >
> > Due to how conditional rules are written in the binary policy, the
> > code responsible for loading does not know how many conditional rules
> > there are before creating the avtab structure. Instead, it was using the
> > number of elements in the non-conditional avtab as a hint and allocates
> > the hash table based on it. Therefore, a two-pass algorithm is now used
> > to calculate the rule count before allocating the avtab nodes array.
> > With the current refpolicy and default Fedora policy, this causes the
> > number of hash slots for the conditional array to become 4096 instead of
> > 32768. This results in a savings of 224KB of heap memory.
> >
> > The caching characteristics of iterating a single array are better due
> > to locality of reference. Running "perf stat -r 100 -d load_policy"
> > has shown a runtime reduction of around 10% on a Fedora 38 x86_64 VM
> > with this single patch. Future patches focused on improving the hash
> > table's collision resolution strategy and array layout (struct-of-arrays
> > vs. array-of-structs) may elicit even more caching and therefore runtime
> > performance improvements.
> >
> > Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com>
>
> Assuming you fix the previous patch,
> Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
>

Thanks for the review.

However after running this patch through clang-analyzer, I have
discovered this patch creates an edge-case that results in a null
pointer dereference within avtab_destroy(). The patch is simple and
will be included within the next spin.

diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index eb69fda4f504..cdc509e715ea 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -222,7 +222,7 @@ void avtab_destroy(struct avtab *h)
        u32 i;
        struct avtab_node *cur, *temp;

-       if (!h)
+       if (!h || !h->htable)
                return;

        for (i = 0; i < h->nslot; i++) {

> > ---
> >  security/selinux/ss/avtab.c       | 47 ++++++++++++++++++++-----------
> >  security/selinux/ss/avtab.h       |  4 ++-
> >  security/selinux/ss/conditional.c | 37 ++++++++++++++++--------
> >  security/selinux/ss/conditional.h |  2 +-
> >  4 files changed, 59 insertions(+), 31 deletions(-)
> >
> > diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
> > index f0d448e7807a..aabe04fc4d04 100644
> > --- a/security/selinux/ss/avtab.c
> > +++ b/security/selinux/ss/avtab.c
> > @@ -24,7 +24,6 @@
> >  #include "avtab.h"
> >  #include "policydb.h"
> >
> > -static struct kmem_cache *avtab_node_cachep __ro_after_init;
> >  static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
> >
> >  #define avtab_chain_for_each(pos, tab, slot) \
> > @@ -79,17 +78,15 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst,
> >  {
> >         struct avtab_node *newnode;
> >         struct avtab_extended_perms *xperms;
> > -       newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
> > -       if (newnode == NULL)
> > +       if (h->nel == h->nnodes)
> >                 return NULL;
> > +       newnode = &h->nodes[h->nel];
> >         newnode->key = *key;
> >
> >         if (key->specified & AVTAB_XPERMS) {
> >                 xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL);
> > -               if (xperms == NULL) {
> > -                       kmem_cache_free(avtab_node_cachep, newnode);
> > +               if (xperms == NULL)
> >                         return NULL;
> > -               }
> >                 *xperms = *(datum->u.xperms);
> >                 newnode->datum.u.xperms = xperms;
> >         } else {
> > @@ -235,11 +232,13 @@ void avtab_destroy(struct avtab *h)
> >                         if (temp->key.specified & AVTAB_XPERMS)
> >                                 kmem_cache_free(avtab_xperms_cachep,
> >                                                 temp->datum.u.xperms);
> > -                       kmem_cache_free(avtab_node_cachep, temp);
> >                 }
> >         }
> >         kvfree(h->htable);
> > +       kvfree(h->nodes);
> >         h->htable = NULL;
> > +       h->nodes = NULL;
> > +       h->nnodes = 0;
> >         h->nel = 0;
> >         h->nslot = 0;
> >         h->mask = 0;
> > @@ -248,20 +247,28 @@ void avtab_destroy(struct avtab *h)
> >  void avtab_init(struct avtab *h)
> >  {
> >         h->htable = NULL;
> > +       h->nodes = NULL;
> > +       h->nnodes = 0;
> >         h->nel = 0;
> >         h->nslot = 0;
> >         h->mask = 0;
> >  }
> >
> > -static int avtab_alloc_common(struct avtab *h, u32 nslot)
> > +static int avtab_alloc_common(struct avtab *h, u32 nslot, u32 nrules)
> >  {
> >         if (!nslot)
> >                 return 0;
> >
> > -       h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL);
> > +       h->htable = kvcalloc(nslot, sizeof(*h->htable), GFP_KERNEL);
> >         if (!h->htable)
> >                 return -ENOMEM;
> > -
> > +       h->nodes = kvcalloc(nrules, sizeof(*h->nodes), GFP_KERNEL);
> > +       if (!h->nodes) {
> > +               kvfree(h->htable);
> > +               h->htable = NULL;
> > +               return -ENOMEM;
> > +       }
> > +       h->nnodes = nrules;
> >         h->nslot = nslot;
> >         h->mask = nslot - 1;
> >         return 0;
> > @@ -277,7 +284,7 @@ int avtab_alloc(struct avtab *h, u32 nrules)
> >                 if (nslot > MAX_AVTAB_HASH_BUCKETS)
> >                         nslot = MAX_AVTAB_HASH_BUCKETS;
> >
> > -               rc = avtab_alloc_common(h, nslot);
> > +               rc = avtab_alloc_common(h, nslot, nrules);
> >                 if (rc)
> >                         return rc;
> >         }
> > @@ -288,7 +295,7 @@ int avtab_alloc(struct avtab *h, u32 nrules)
> >
> >  int avtab_alloc_dup(struct avtab *new, const struct avtab *orig)
> >  {
> > -       return avtab_alloc_common(new, orig->nslot);
> > +       return avtab_alloc_common(new, orig->nslot, orig->nel);
> >  }
> >
> >  #ifdef CONFIG_SECURITY_SELINUX_DEBUG
> > @@ -337,7 +344,7 @@ static const uint16_t spec_order[] = {
> >  int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
> >                     int (*insertf)(struct avtab *a, const struct avtab_key *k,
> >                                    const struct avtab_datum *d, void *p),
> > -                   void *p)
> > +                   void *p, u32 *nrules)
> >  {
> >         __le16 buf16[4];
> >         u16 enabled;
> > @@ -411,6 +418,10 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
> >                         if (val & spec_order[i]) {
> >                                 key.specified = spec_order[i] | enabled;
> >                                 datum.u.data = le32_to_cpu(buf32[items++]);
> > +                               if (nrules) {
> > +                                       (*nrules)++;
> > +                                       continue;
> > +                               }
> >                                 rc = insertf(a, &key, &datum, p);
> >                                 if (rc)
> >                                         return rc;
> > @@ -489,6 +500,11 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
> >                 pr_err("SELinux: avtab: invalid type\n");
> >                 return -EINVAL;
> >         }
> > +
> > +       if (nrules) {
> > +               (*nrules)++;
> > +               return 0;
> > +       }
> >         return insertf(a, &key, &datum, p);
> >  }
> >
> > @@ -522,7 +538,7 @@ int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
> >                 goto bad;
> >
> >         for (i = 0; i < nel; i++) {
> > -               rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL);
> > +               rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL, NULL);
> >                 if (rc) {
> >                         if (rc == -ENOMEM)
> >                                 pr_err("SELinux: avtab: out of memory\n");
> > @@ -602,9 +618,6 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp)
> >
> >  void __init avtab_cache_init(void)
> >  {
> > -       avtab_node_cachep = kmem_cache_create("avtab_node",
> > -                                             sizeof(struct avtab_node),
> > -                                             0, SLAB_PANIC, NULL);
> >         avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms",
> >                                                 sizeof(struct avtab_extended_perms),
> >                                                 0, SLAB_PANIC, NULL);
> > diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
> > index 3c3904bf02b0..5e465be6f057 100644
> > --- a/security/selinux/ss/avtab.h
> > +++ b/security/selinux/ss/avtab.h
> > @@ -82,6 +82,8 @@ struct avtab_node {
> >
> >  struct avtab {
> >         struct avtab_node **htable;
> > +       struct avtab_node *nodes;
> > +       u32 nnodes;     /* number of nodes */
> >         u32 nel;        /* number of elements */
> >         u32 nslot;      /* number of hash slots */
> >         u32 mask;       /* mask to compute hash func */
> > @@ -104,7 +106,7 @@ struct policydb;
> >  int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
> >                     int (*insert)(struct avtab *a, const struct avtab_key *k,
> >                                   const struct avtab_datum *d, void *p),
> > -                   void *p);
> > +                   void *p, u32 *nrules);
> >
> >  int avtab_read(struct avtab *a, void *fp, struct policydb *pol);
> >  int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp);
> > diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c
> > index 81ff676f209a..bbd35b35b79d 100644
> > --- a/security/selinux/ss/conditional.c
> > +++ b/security/selinux/ss/conditional.c
> > @@ -140,7 +140,7 @@ void cond_policydb_init(struct policydb *p)
> >  static void cond_node_destroy(struct cond_node *node)
> >  {
> >         kfree(node->expr.nodes);
> > -       /* the avtab_ptr_t nodes are destroyed by the avtab */
> > +       /* the actual nodes were destroyed by avtab_destroy() */
> >         kfree(node->true_list.nodes);
> >         kfree(node->false_list.nodes);
> >  }
> > @@ -323,7 +323,8 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k,
> >
> >  static int cond_read_av_list(struct policydb *p, void *fp,
> >                              struct cond_av_list *list,
> > -                            struct cond_av_list *other)
> > +                            struct cond_av_list *other,
> > +                            u32 *nrules)
> >  {
> >         int rc;
> >         __le32 buf[1];
> > @@ -347,7 +348,7 @@ static int cond_read_av_list(struct policydb *p, void *fp,
> >         for (i = 0; i < len; i++) {
> >                 data.dst = &list->nodes[i];
> >                 rc = avtab_read_item(&p->te_cond_avtab, fp, p, cond_insertf,
> > -                                    &data);
> > +                                    &data, nrules);
> >                 if (rc) {
> >                         kfree(list->nodes);
> >                         list->nodes = NULL;
> > @@ -373,7 +374,8 @@ static int expr_node_isvalid(struct policydb *p, struct cond_expr_node *expr)
> >         return 1;
> >  }
> >
> > -static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp)
> > +static int cond_read_node(struct policydb *p, struct cond_node *node,
> > +                         void *fp, u32 *nrules)
> >  {
> >         __le32 buf[2];
> >         u32 i, len;
> > @@ -407,16 +409,17 @@ static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp)
> >                         return -EINVAL;
> >         }
> >
> > -       rc = cond_read_av_list(p, fp, &node->true_list, NULL);
> > +       rc = cond_read_av_list(p, fp, &node->true_list, NULL, nrules);
> >         if (rc)
> >                 return rc;
> > -       return cond_read_av_list(p, fp, &node->false_list, &node->true_list);
> > +       return cond_read_av_list(p, fp, &node->false_list, &node->true_list, nrules);
> >  }
> >
> > -int cond_read_list(struct policydb *p, void *fp)
> > +int cond_read_list(struct policydb *p, struct policy_file *fp)
> >  {
> >         __le32 buf[1];
> > -       u32 i, len;
> > +       struct policy_file tmp_fp;
> > +       u32 i, len, nrules;
> >         int rc;
> >
> >         rc = next_entry(buf, fp, sizeof(buf));
> > @@ -428,15 +431,25 @@ int cond_read_list(struct policydb *p, void *fp)
> >         p->cond_list = kcalloc(len, sizeof(*p->cond_list), GFP_KERNEL);
> >         if (!p->cond_list)
> >                 return -ENOMEM;
> > +       p->cond_list_len = len;
> > +
> > +       /* first pass to only calculate the avrule count */
> > +       tmp_fp = *fp;
> > +       nrules = 0;
> > +       for (i = 0; i < len; i++) {
> > +               rc = cond_read_node(p, &p->cond_list[i], &tmp_fp, &nrules);
> > +               if (rc)
> > +                       goto err;
> > +               cond_node_destroy(&p->cond_list[i]);
> > +       }
> >
> > -       rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel);
> > +       rc = avtab_alloc(&(p->te_cond_avtab), nrules);
> >         if (rc)
> >                 goto err;
> >
> > -       p->cond_list_len = len;
> > -
> > +       /* second pass to read in the conditional nodes */
> >         for (i = 0; i < len; i++) {
> > -               rc = cond_read_node(p, &p->cond_list[i], fp);
> > +               rc = cond_read_node(p, &p->cond_list[i], fp, NULL);
> >                 if (rc)
> >                         goto err;
> >         }
> > diff --git a/security/selinux/ss/conditional.h b/security/selinux/ss/conditional.h
> > index 5a7b51278dc6..62a12d00cac9 100644
> > --- a/security/selinux/ss/conditional.h
> > +++ b/security/selinux/ss/conditional.h
> > @@ -70,7 +70,7 @@ int cond_destroy_bool(void *key, void *datum, void *p);
> >  int cond_index_bool(void *key, void *datum, void *datap);
> >
> >  int cond_read_bool(struct policydb *p, struct symtab *s, void *fp);
> > -int cond_read_list(struct policydb *p, void *fp);
> > +int cond_read_list(struct policydb *p, struct policy_file *fp);
> >  int cond_write_bool(void *key, void *datum, void *ptr);
> >  int cond_write_list(struct policydb *p, void *fp);
> >
> > --
> > 2.41.0
> >