[PATCH 0/3] libsepol: Speed up policy optimization

[PATCH 0/3] libsepol: Speed up policy optimization

[Ondrej Mosnacek]

This series contains two small changes (these don't seem to affect
performance measurably, but are nonetheless logical) and a patch that
changes how the policy optimization "type_map" helper structure is
represented, which speeds up the whole process.

Ondrej Mosnacek (3):
  libsepol: skip unnecessary check in build_type_map()
  libsepol: optimize inner loop in build_type_map()
  libsepol: speed up policy optimization

 libsepol/src/optimize.c | 119 +++++++++++++++++++++++++++++++---------
 1 file changed, 94 insertions(+), 25 deletions(-)

-- 
2.24.1

[PATCH 1/3] libsepol: skip unnecessary check in build_type_map()

[Ondrej Mosnacek]

I copy-pasted it from a different part of the code, which had to deal
with policydb that isn't final yet. Since we only deal with the final
kernel policy here, we can skip the check for the type datum being NULL.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 libsepol/src/optimize.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
index 1e5e97e8..4d835d47 100644
--- a/libsepol/src/optimize.c
+++ b/libsepol/src/optimize.c
@@ -40,8 +40,7 @@ static ebitmap_t *build_type_map(const policydb_t *p)
 		return NULL;
 
 	for (i = 0; i < p->p_types.nprim; i++) {
-		if (p->type_val_to_struct[i] &&
-		    p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
+		if (p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
 			if (ebitmap_cpy(&map[i], &p->type_attr_map[i]))
 				goto err;
 		} else {
-- 
2.24.1

Re: [PATCH 1/3] libsepol: skip unnecessary check in build_type_map()

[Stephen Smalley]

On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>
> I copy-pasted it from a different part of the code, which had to deal
> with policydb that isn't final yet. Since we only deal with the final
> kernel policy here, we can skip the check for the type datum being NULL.
>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>

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

Re: [PATCH 1/3] libsepol: skip unnecessary check in build_type_map()

[James Carter]

On Tue, Mar 17, 2020 at 2:20 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> >
> > I copy-pasted it from a different part of the code, which had to deal
> > with policydb that isn't final yet. Since we only deal with the final
> > kernel policy here, we can skip the check for the type datum being NULL.
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>
> Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Applied.
Thanks,
Jim

[PATCH 2/3] libsepol: optimize inner loop in build_type_map()

[Ondrej Mosnacek]

Only attributes can be a superset of another attribute, so we can skip
non-attributes right away.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 libsepol/src/optimize.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
index 4d835d47..2b5102af 100644
--- a/libsepol/src/optimize.c
+++ b/libsepol/src/optimize.c
@@ -50,6 +50,9 @@ static ebitmap_t *build_type_map(const policydb_t *p)
 			for (k = 0; k < p->p_types.nprim; k++) {
 				ebitmap_t *types_k = &p->attr_type_map[k];
 
+				if (p->type_val_to_struct[k]->flavor != TYPE_ATTRIB)
+					continue;
+
 				if (ebitmap_contains(types_k, types_i)) {
 					if (ebitmap_set_bit(&map[i], k, 1))
 						goto err;
-- 
2.24.1

Re: [PATCH 2/3] libsepol: optimize inner loop in build_type_map()

[James Carter]

On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>
> Only attributes can be a superset of another attribute, so we can skip
> non-attributes right away.
>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
>  libsepol/src/optimize.c | 3 +++
>  1 file changed, 3 insertions(+)
>
> diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
> index 4d835d47..2b5102af 100644
> --- a/libsepol/src/optimize.c
> +++ b/libsepol/src/optimize.c
> @@ -50,6 +50,9 @@ static ebitmap_t *build_type_map(const policydb_t *p)
>                         for (k = 0; k < p->p_types.nprim; k++) {
>                                 ebitmap_t *types_k = &p->attr_type_map[k];
>
> +                               if (p->type_val_to_struct[k]->flavor != TYPE_ATTRIB)
> +                                       continue;
> +

I haven't tested this yet, but I suspect that this is what is causing
the difference noted by Stephen. A type is a superset of itself.

Jim


>                                 if (ebitmap_contains(types_k, types_i)) {
>                                         if (ebitmap_set_bit(&map[i], k, 1))
>                                                 goto err;
> --
> 2.24.1
>

Re: [PATCH 2/3] libsepol: optimize inner loop in build_type_map()

[James Carter]

On Mon, Mar 2, 2020 at 10:24 AM James Carter <jwcart2@gmail.com> wrote:
>
> On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> >
> > Only attributes can be a superset of another attribute, so we can skip
> > non-attributes right away.
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> > ---
> >  libsepol/src/optimize.c | 3 +++
> >  1 file changed, 3 insertions(+)
> >
> > diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
> > index 4d835d47..2b5102af 100644
> > --- a/libsepol/src/optimize.c
> > +++ b/libsepol/src/optimize.c
> > @@ -50,6 +50,9 @@ static ebitmap_t *build_type_map(const policydb_t *p)
> >                         for (k = 0; k < p->p_types.nprim; k++) {
> >                                 ebitmap_t *types_k = &p->attr_type_map[k];
> >
> > +                               if (p->type_val_to_struct[k]->flavor != TYPE_ATTRIB)
> > +                                       continue;
> > +
>
> I haven't tested this yet, but I suspect that this is what is causing
> the difference noted by Stephen. A type is a superset of itself.
>

This is definitely what is causing the change. Your explanation is
correct. This prevents a type from being considered as a super set of
an attribute that only contains that type.

Jim

> Jim
>
>
> >                                 if (ebitmap_contains(types_k, types_i)) {
> >                                         if (ebitmap_set_bit(&map[i], k, 1))
> >                                                 goto err;
> > --
> > 2.24.1
> >

Re: [PATCH 2/3] libsepol: optimize inner loop in build_type_map()

[Stephen Smalley]

On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>
> Only attributes can be a superset of another attribute, so we can skip
> non-attributes right away.
>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>

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

Re: [PATCH 2/3] libsepol: optimize inner loop in build_type_map()

[James Carter]

On Tue, Mar 17, 2020 at 2:22 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> >
> > Only attributes can be a superset of another attribute, so we can skip
> > non-attributes right away.
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>
> Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Applied.
Thanks,
Jim

[PATCH 3/3] libsepol: speed up policy optimization

[Ondrej Mosnacek]

The iteration over the set ebitmap bits is not implemented very
efficiently in libsepol. It is slowing down the policy optimization
quite significantly, so convert the type_map from an array of ebitmaps
to an array of simple ordered vectors, which can be traveresed more
easily. The worse space efficiency of the vectors is less important than
the speed in this case.

After this change the duration of semodule -BN decreased from 6.4s to
5.5s on Fedora Rawhide x86_64 (and from 6.1s to 5.6s with the unconfined
module disabled).

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 libsepol/src/optimize.c | 113 ++++++++++++++++++++++++++++++++--------
 1 file changed, 90 insertions(+), 23 deletions(-)

diff --git a/libsepol/src/optimize.c b/libsepol/src/optimize.c
index 2b5102af..6826155c 100644
--- a/libsepol/src/optimize.c
+++ b/libsepol/src/optimize.c
@@ -31,22 +31,85 @@
 #include <sepol/policydb/policydb.h>
 #include <sepol/policydb/conditional.h>
 
+#define TYPE_VEC_INIT_SIZE 16
+
+struct type_vec {
+	uint32_t *types;
+	unsigned int count, capacity;
+};
+
+static int type_vec_init(struct type_vec *v)
+{
+	v->capacity = TYPE_VEC_INIT_SIZE;
+	v->count = 0;
+	v->types = malloc(v->capacity * sizeof(*v->types));
+	if (!v->types)
+		return -1;
+	return 0;
+}
+
+static void type_vec_destroy(struct type_vec *v)
+{
+	free(v->types);
+}
+
+static int type_vec_append(struct type_vec *v, uint32_t type)
+{
+	if (v->capacity == v->count) {
+		unsigned int new_capacity = v->capacity * 2;
+		uint32_t *new_types = realloc(v->types,
+					      new_capacity * sizeof(*v->types));
+		if (!new_types)
+			return -1;
+
+		v->types = new_types;
+		v->capacity = new_capacity;
+	}
+
+	v->types[v->count++] = type;
+	return 0;
+}
+
+static int type_vec_contains(const struct type_vec *v, uint32_t type)
+{
+	unsigned int s = 0, e = v->count;
+
+	while (s != e) {
+		unsigned int mid = (s + e) / 2;
+
+		if (v->types[mid] == type)
+			return 1;
+
+		if (v->types[mid] < type)
+			s = mid + 1;
+		else
+			e = mid;
+	}
+	return 0;
+}
+
 /* builds map: type/attribute -> {all attributes that are a superset of it} */
-static ebitmap_t *build_type_map(const policydb_t *p)
+static struct type_vec *build_type_map(const policydb_t *p)
 {
 	unsigned int i, k;
-	ebitmap_t *map = malloc(p->p_types.nprim * sizeof(ebitmap_t));
+	ebitmap_node_t *n;
+	struct type_vec *map = malloc(p->p_types.nprim * sizeof(*map));
 	if (!map)
 		return NULL;
 
 	for (i = 0; i < p->p_types.nprim; i++) {
+		if (type_vec_init(&map[i]))
+			goto err;
+
 		if (p->type_val_to_struct[i]->flavor != TYPE_ATTRIB) {
-			if (ebitmap_cpy(&map[i], &p->type_attr_map[i]))
-				goto err;
+			ebitmap_for_each_positive_bit(&p->type_attr_map[i],
+						      n, k) {
+				if (type_vec_append(&map[i], k))
+					goto err;
+			}
 		} else {
 			ebitmap_t *types_i = &p->attr_type_map[i];
 
-			ebitmap_init(&map[i]);
 			for (k = 0; k < p->p_types.nprim; k++) {
 				ebitmap_t *types_k = &p->attr_type_map[k];
 
@@ -54,7 +117,7 @@ static ebitmap_t *build_type_map(const policydb_t *p)
 					continue;
 
 				if (ebitmap_contains(types_k, types_i)) {
-					if (ebitmap_set_bit(&map[i], k, 1))
+					if (type_vec_append(&map[i], k))
 						goto err;
 				}
 			}
@@ -63,16 +126,16 @@ static ebitmap_t *build_type_map(const policydb_t *p)
 	return map;
 err:
 	for (k = 0; k <= i; k++)
-		ebitmap_destroy(&map[k]);
+		type_vec_destroy(&map[k]);
 	free(map);
 	return NULL;
 }
 
-static void destroy_type_map(const policydb_t *p, ebitmap_t *type_map)
+static void destroy_type_map(const policydb_t *p, struct type_vec *type_map)
 {
 	unsigned int i;
 	for (i = 0; i < p->p_types.nprim; i++)
-		ebitmap_destroy(&type_map[i]);
+		type_vec_destroy(&type_map[i]);
 	free(type_map);
 }
 
@@ -125,10 +188,11 @@ static int process_avtab_datum(uint16_t specified,
 
 /* checks if avtab contains a rule that covers the given rule */
 static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
-			       const ebitmap_t *type_map, unsigned char not_cond)
+			       const struct type_vec *type_map,
+			       unsigned char not_cond)
 {
 	unsigned int i, k, s_idx, t_idx;
-	ebitmap_node_t *snode, *tnode;
+	uint32_t st, tt;
 	avtab_datum_t *d1, *d2;
 	avtab_key_t key;
 
@@ -144,14 +208,17 @@ static int is_avrule_redundant(avtab_ptr_t entry, avtab_t *tab,
 
 	d1 = &entry->datum;
 
-	ebitmap_for_each_positive_bit(&type_map[s_idx], snode, i) {
-		key.source_type = i + 1;
+	for (i = 0; i < type_map[s_idx].count; i++) {
+		st = type_map[s_idx].types[i];
+		key.source_type = st + 1;
+
+		for (k = 0; k < type_map[t_idx].count; k++) {
+			tt = type_map[t_idx].types[k];
 
-		ebitmap_for_each_positive_bit(&type_map[t_idx], tnode, k) {
-			if (not_cond && s_idx == i && t_idx == k)
+			if (not_cond && s_idx == st && t_idx == tt)
 				continue;
 
-			key.target_type = k + 1;
+			key.target_type = tt + 1;
 
 			d2 = avtab_search(tab, &key);
 			if (!d2)
@@ -179,7 +246,7 @@ static int is_avrule_with_attr(avtab_ptr_t entry, policydb_t *p)
 
 /* checks if conditional list contains a rule that covers the given rule */
 static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
-				  const ebitmap_t *type_map)
+				  const struct type_vec *type_map)
 {
 	unsigned int s1, t1, c1, k1, s2, t2, c2, k2;
 
@@ -205,9 +272,9 @@ static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
 
 		if (s1 == s2 && t1 == t2)
 			continue;
-		if (!ebitmap_get_bit(&type_map[s1], s2))
+		if (!type_vec_contains(&type_map[s1], s2))
 			continue;
-		if (!ebitmap_get_bit(&type_map[t1], t2))
+		if (!type_vec_contains(&type_map[t1], t2))
 			continue;
 
 		if (process_avtab_datum(k1, &e1->datum, &e2->datum))
@@ -216,7 +283,7 @@ static int is_cond_rule_redundant(avtab_ptr_t e1, cond_av_list_t *list,
 	return 0;
 }
 
-static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
+static void optimize_avtab(policydb_t *p, const struct type_vec *type_map)
 {
 	avtab_t *tab = &p->te_avtab;
 	unsigned int i;
@@ -245,7 +312,7 @@ static void optimize_avtab(policydb_t *p, const ebitmap_t *type_map)
 
 /* find redundant rules in (*cond) and put them into (*del) */
 static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
-				  policydb_t *p, const ebitmap_t *type_map)
+				  policydb_t *p, const struct type_vec *type_map)
 {
 	cond_av_list_t **listp = cond;
 	cond_av_list_t *pcov = NULL;
@@ -294,7 +361,7 @@ static void optimize_cond_av_list(cond_av_list_t **cond, cond_av_list_t **del,
 	}
 }
 
-static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map)
+static void optimize_cond_avtab(policydb_t *p, const struct type_vec *type_map)
 {
 	avtab_t *tab = &p->te_cond_avtab;
 	unsigned int i;
@@ -363,7 +430,7 @@ static void optimize_cond_avtab(policydb_t *p, const ebitmap_t *type_map)
 
 int policydb_optimize(policydb_t *p)
 {
-	ebitmap_t *type_map;
+	struct type_vec *type_map;
 
 	if (p->policy_type != POLICY_KERN)
 		return -1;
-- 
2.24.1

Re: [PATCH 3/3] libsepol: speed up policy optimization

[Stephen Smalley]

On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>
> The iteration over the set ebitmap bits is not implemented very
> efficiently in libsepol. It is slowing down the policy optimization
> quite significantly, so convert the type_map from an array of ebitmaps
> to an array of simple ordered vectors, which can be traveresed more
> easily. The worse space efficiency of the vectors is less important than
> the speed in this case.
>
> After this change the duration of semodule -BN decreased from 6.4s to
> 5.5s on Fedora Rawhide x86_64 (and from 6.1s to 5.6s with the unconfined
> module disabled).
>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>

Sidebar: Wondering whether you would have gotten similar results by taking some
of the ebitmap optimization done in the kernel into libsepol. Regardless,

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

Re: [PATCH 3/3] libsepol: speed up policy optimization

[James Carter]

On Tue, Mar 17, 2020 at 2:25 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> >
> > The iteration over the set ebitmap bits is not implemented very
> > efficiently in libsepol. It is slowing down the policy optimization
> > quite significantly, so convert the type_map from an array of ebitmaps
> > to an array of simple ordered vectors, which can be traveresed more
> > easily. The worse space efficiency of the vectors is less important than
> > the speed in this case.
> >
> > After this change the duration of semodule -BN decreased from 6.4s to
> > 5.5s on Fedora Rawhide x86_64 (and from 6.1s to 5.6s with the unconfined
> > module disabled).
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>
> Sidebar: Wondering whether you would have gotten similar results by taking some
> of the ebitmap optimization done in the kernel into libsepol. Regardless,
>
> Acked-by: Stephen Smalley <stephen.smalley.work@gmail.com>

Applied.
Thanks,
Jim

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Stephen Smalley]

On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>
> This series contains two small changes (these don't seem to affect
> performance measurably, but are nonetheless logical) and a patch that
> changes how the policy optimization "type_map" helper structure is
> represented, which speeds up the whole process.
>
> Ondrej Mosnacek (3):
>   libsepol: skip unnecessary check in build_type_map()
>   libsepol: optimize inner loop in build_type_map()
>   libsepol: speed up policy optimization

Not a comment on the patches themselves, but this made me wonder if
the optimization support is actually tested by our travis
configuration.
Doesn't appear to be (e.g. no usage of -O/--optimize or semanage.conf
with optimize-policy true).

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Stephen Smalley]

On Fri, Feb 28, 2020 at 1:08 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> >
> > This series contains two small changes (these don't seem to affect
> > performance measurably, but are nonetheless logical) and a patch that
> > changes how the policy optimization "type_map" helper structure is
> > represented, which speeds up the whole process.
> >
> > Ondrej Mosnacek (3):
> >   libsepol: skip unnecessary check in build_type_map()
> >   libsepol: optimize inner loop in build_type_map()
> >   libsepol: speed up policy optimization
>
> Not a comment on the patches themselves, but this made me wonder if
> the optimization support is actually tested by our travis
> configuration.
> Doesn't appear to be (e.g. no usage of -O/--optimize or semanage.conf
> with optimize-policy true).

Adding optimize-policy = true to /etc/selinux/semanage.conf and
running semodule -BN before and after these patches yields different
binary kernel policy files (policy.32).
Is that expected?

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Stephen Smalley]

On Mon, Mar 2, 2020 at 9:50 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Fri, Feb 28, 2020 at 1:08 PM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> > >
> > > This series contains two small changes (these don't seem to affect
> > > performance measurably, but are nonetheless logical) and a patch that
> > > changes how the policy optimization "type_map" helper structure is
> > > represented, which speeds up the whole process.
> > >
> > > Ondrej Mosnacek (3):
> > >   libsepol: skip unnecessary check in build_type_map()
> > >   libsepol: optimize inner loop in build_type_map()
> > >   libsepol: speed up policy optimization
> >
> > Not a comment on the patches themselves, but this made me wonder if
> > the optimization support is actually tested by our travis
> > configuration.
> > Doesn't appear to be (e.g. no usage of -O/--optimize or semanage.conf
> > with optimize-policy true).
>
> Adding optimize-policy = true to /etc/selinux/semanage.conf and
> running semodule -BN before and after these patches yields different
> binary kernel policy files (policy.32).
> Is that expected?

Here is one example difference between the policies, along with what
was present in the original unoptimized policy:
$ sesearch -A -s guest_t -t guest_t -c context -p contains policy.32.unoptimized
allow guest_t guest_t:context contains;
allow guest_usertype guest_usertype:context contains;

$ sesearch -A -s guest_t -t guest_t -c context -p contains
policy.32.optimizedbefore
allow guest_t guest_t:context contains;

$ sesearch -A -s guest_t -t guest_t -c context -p contains
policy.32.optimizedafter
allow guest_usertype guest_usertype:context contains;

Seems like the code prior to these changes yielded a more optimal
policy since guest_usertype only has a single type in it.

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Ondrej Mosnacek]

On Mon, Mar 2, 2020 at 3:57 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
> On Mon, Mar 2, 2020 at 9:50 AM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Fri, Feb 28, 2020 at 1:08 PM Stephen Smalley
> > <stephen.smalley.work@gmail.com> wrote:
> > >
> > > On Thu, Feb 27, 2020 at 11:03 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> > > >
> > > > This series contains two small changes (these don't seem to affect
> > > > performance measurably, but are nonetheless logical) and a patch that
> > > > changes how the policy optimization "type_map" helper structure is
> > > > represented, which speeds up the whole process.
> > > >
> > > > Ondrej Mosnacek (3):
> > > >   libsepol: skip unnecessary check in build_type_map()
> > > >   libsepol: optimize inner loop in build_type_map()
> > > >   libsepol: speed up policy optimization
> > >
> > > Not a comment on the patches themselves, but this made me wonder if
> > > the optimization support is actually tested by our travis
> > > configuration.
> > > Doesn't appear to be (e.g. no usage of -O/--optimize or semanage.conf
> > > with optimize-policy true).

Yeah, there is currently no test for this. I have something hackish
that I used locally - I'll try to convert it to something more usable
an automated and integrate it into the repo.

> >
> > Adding optimize-policy = true to /etc/selinux/semanage.conf and
> > running semodule -BN before and after these patches yields different
> > binary kernel policy files (policy.32).
> > Is that expected?
>
> Here is one example difference between the policies, along with what
> was present in the original unoptimized policy:
> $ sesearch -A -s guest_t -t guest_t -c context -p contains policy.32.unoptimized
> allow guest_t guest_t:context contains;
> allow guest_usertype guest_usertype:context contains;
>
> $ sesearch -A -s guest_t -t guest_t -c context -p contains
> policy.32.optimizedbefore
> allow guest_t guest_t:context contains;
>
> $ sesearch -A -s guest_t -t guest_t -c context -p contains
> policy.32.optimizedafter
> allow guest_usertype guest_usertype:context contains;
>
> Seems like the code prior to these changes yielded a more optimal
> policy since guest_usertype only has a single type in it.

Hm... this is probably a consequence of the second patch. Types are no
longer considered a superset of an attribute containing a single type,
so the single-type rule gets removed instead of the attribute one...
But even before it picked the first rule only by chance (it was first
in order). I would say that picking a single-type rule over an
attribute rule in this case is outside of the scope of the algorithm.
Shouldn't the compiler automatically expand each attribute that has
less than 5 types in it? I recall seeing something in the code that
did this. I think this was in the CIL part of libsepol, so maybe it
applies only when compiling from CIL?

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

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Stephen Smalley]

On Mon, Mar 2, 2020 at 10:46 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> Hm... this is probably a consequence of the second patch. Types are no
> longer considered a superset of an attribute containing a single type,
> so the single-type rule gets removed instead of the attribute one...
> But even before it picked the first rule only by chance (it was first
> in order). I would say that picking a single-type rule over an
> attribute rule in this case is outside of the scope of the algorithm.
> Shouldn't the compiler automatically expand each attribute that has
> less than 5 types in it? I recall seeing something in the code that
> did this. I think this was in the CIL part of libsepol, so maybe it
> applies only when compiling from CIL?

secilc has -G and -X options for controlling expansion of attributes, but
there aren't equivalent settings in semanage.conf to control when
building modular policies.
Internally it all uses the libsepol CIL support so it ought to be fixable.
Looks like the default is 1 in cil_db_init() so it only happens when
the attribute has no types by default?

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Stephen Smalley]

On Mon, Mar 2, 2020 at 1:45 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Mon, Mar 2, 2020 at 10:46 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> > Hm... this is probably a consequence of the second patch. Types are no
> > longer considered a superset of an attribute containing a single type,
> > so the single-type rule gets removed instead of the attribute one...
> > But even before it picked the first rule only by chance (it was first
> > in order). I would say that picking a single-type rule over an
> > attribute rule in this case is outside of the scope of the algorithm.
> > Shouldn't the compiler automatically expand each attribute that has
> > less than 5 types in it? I recall seeing something in the code that
> > did this. I think this was in the CIL part of libsepol, so maybe it
> > applies only when compiling from CIL?
>
> secilc has -G and -X options for controlling expansion of attributes, but
> there aren't equivalent settings in semanage.conf to control when
> building modular policies.
> Internally it all uses the libsepol CIL support so it ought to be fixable.
> Looks like the default is 1 in cil_db_init() so it only happens when
> the attribute has no types by default?

Apparently that was to eliminate attributes that have no types at all.
Seems like we could add new options to semanage.conf to provide equivalents
to secilc -G and -X, and have semanage_direct_commit() call
cil_set_attrs_expand_generated()
and cil_set_attrs_expand_size() in the same manner as secilc does based on those
semanage.conf settings.

Could also look at increasing the default size to 5 or something and
see what impact that has on
Fedora policies.

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Ondrej Mosnacek]

On Mon, Mar 2, 2020 at 9:22 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
> On Mon, Mar 2, 2020 at 1:45 PM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Mon, Mar 2, 2020 at 10:46 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> > > Hm... this is probably a consequence of the second patch. Types are no
> > > longer considered a superset of an attribute containing a single type,
> > > so the single-type rule gets removed instead of the attribute one...
> > > But even before it picked the first rule only by chance (it was first
> > > in order). I would say that picking a single-type rule over an
> > > attribute rule in this case is outside of the scope of the algorithm.
> > > Shouldn't the compiler automatically expand each attribute that has
> > > less than 5 types in it? I recall seeing something in the code that
> > > did this. I think this was in the CIL part of libsepol, so maybe it
> > > applies only when compiling from CIL?
> >
> > secilc has -G and -X options for controlling expansion of attributes, but
> > there aren't equivalent settings in semanage.conf to control when
> > building modular policies.
> > Internally it all uses the libsepol CIL support so it ought to be fixable.
> > Looks like the default is 1 in cil_db_init() so it only happens when
> > the attribute has no types by default?

Okay, I don't know where I got the "5" boundary from... maybe my brain
just made it up.

>
> Apparently that was to eliminate attributes that have no types at all.
> Seems like we could add new options to semanage.conf to provide equivalents
> to secilc -G and -X, and have semanage_direct_commit() call
> cil_set_attrs_expand_generated()
> and cil_set_attrs_expand_size() in the same manner as secilc does based on those
> semanage.conf settings.
>
> Could also look at increasing the default size to 5 or something and
> see what impact that has on
> Fedora policies.

Well, for a start we could increase the default to 2, which should
only remove those attributes that have only one type. That has
practically no downsides (other than making it a bit harder to trace
the rule back to source policy) and would be just enough to make the
optimization work nicely.

I wouldn't change the default to higher values than that for now,
since such values already trade off policy size increase for rule
lookup performance, which is more of a gray area.

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

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Ondrej Mosnacek]

On Mon, Mar 2, 2020 at 10:08 PM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> On Mon, Mar 2, 2020 at 9:22 PM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> > On Mon, Mar 2, 2020 at 1:45 PM Stephen Smalley
> > <stephen.smalley.work@gmail.com> wrote:
[...]
> > > secilc has -G and -X options for controlling expansion of attributes, but
> > > there aren't equivalent settings in semanage.conf to control when
> > > building modular policies.
> > > Internally it all uses the libsepol CIL support so it ought to be fixable.
> > > Looks like the default is 1 in cil_db_init() so it only happens when
> > > the attribute has no types by default?
[...]
> >
> > Apparently that was to eliminate attributes that have no types at all.
> > Seems like we could add new options to semanage.conf to provide equivalents
> > to secilc -G and -X, and have semanage_direct_commit() call
> > cil_set_attrs_expand_generated()
> > and cil_set_attrs_expand_size() in the same manner as secilc does based on those
> > semanage.conf settings.
> >
> > Could also look at increasing the default size to 5 or something and
> > see what impact that has on
> > Fedora policies.
>
> Well, for a start we could increase the default to 2, which should
> only remove those attributes that have only one type. That has
> practically no downsides (other than making it a bit harder to trace
> the rule back to source policy) and would be just enough to make the
> optimization work nicely.

I played with this a bit by recompiling the local binary policy with
secilc and then comparing the CIL of both binary policies (I used this
script [1]) and the results are a bit confusing... There is no
difference in result between -X 0 and -X 1 [2] and in both cases it
removes some unused attributes (those are only referenced from
neverallow rules) that were in the original policy
(/etc/selinux/targeted/policy/policy.31 from my Fedora 31 machine),
but not in the one recompiled via checkpolicy -C + secilc... At least
I was able to confirm that secilc -X 2 really removes the attributes
that have only one type and reduces the policy size by a few
kilobytes.

I suspect that the reason for the unremoved attributes in the policy
built by semodule are due to a bug in libsepol: It seems that when it
starts with a cildb that has the neverallow rules in the input policy
+ has disable_neverallow set, it removes the rules but not the
attributes that are used only in them. Only when it reads the policy
again, it identifies these unused attributes (since there are no
longer any neverallow rules in the input) and removes them
unconditionally. It could be something else, but if I'm right then I
think libsepol should be fixed to remove the unused attributes right
away. I don't dare digging into the CIL code to investigate it, though
;)

[1] https://gitlab.com/omos/selinux-misc/-/blob/master/diffexpand.sh
[2] Okay, this part is not really confusing, sonce semodule should
already build the policy with an equivalent of -X 1, so -X 0 should
yield the same result.

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

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Stephen Smalley]

On Wed, Mar 4, 2020 at 4:07 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> I played with this a bit by recompiling the local binary policy with
> secilc and then comparing the CIL of both binary policies (I used this
> script [1]) and the results are a bit confusing... There is no
> difference in result between -X 0 and -X 1 [2] and in both cases it
> removes some unused attributes (those are only referenced from
> neverallow rules) that were in the original policy
> (/etc/selinux/targeted/policy/policy.31 from my Fedora 31 machine),
> but not in the one recompiled via checkpolicy -C + secilc... At least
> I was able to confirm that secilc -X 2 really removes the attributes
> that have only one type and reduces the policy size by a few
> kilobytes.
>
> I suspect that the reason for the unremoved attributes in the policy
> built by semodule are due to a bug in libsepol: It seems that when it
> starts with a cildb that has the neverallow rules in the input policy
> + has disable_neverallow set, it removes the rules but not the
> attributes that are used only in them. Only when it reads the policy
> again, it identifies these unused attributes (since there are no
> longer any neverallow rules in the input) and removes them
> unconditionally. It could be something else, but if I'm right then I
> think libsepol should be fixed to remove the unused attributes right
> away. I don't dare digging into the CIL code to investigate it, though
> ;)

James will have to confirm the details but IIRC we had to keep
attributes in the policy
when they are referenced by a neverallow in order to avoid breaking
Android because
it uses the attribute definition from the policy as part of CTS
validation of OEM policies
(it extracts the neverallows from the AOSP policy, extracts the binary
policy from the device,
and checks the neverallows against the device policy).

>
> [1] https://gitlab.com/omos/selinux-misc/-/blob/master/diffexpand.sh
> [2] Okay, this part is not really confusing, sonce semodule should
> already build the policy with an equivalent of -X 1, so -X 0 should
> yield the same result.

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[James Carter]

On Wed, Mar 4, 2020 at 9:25 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Wed, Mar 4, 2020 at 4:07 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> > I played with this a bit by recompiling the local binary policy with
> > secilc and then comparing the CIL of both binary policies (I used this
> > script [1]) and the results are a bit confusing... There is no
> > difference in result between -X 0 and -X 1 [2] and in both cases it
> > removes some unused attributes (those are only referenced from
> > neverallow rules) that were in the original policy
> > (/etc/selinux/targeted/policy/policy.31 from my Fedora 31 machine),
> > but not in the one recompiled via checkpolicy -C + secilc... At least
> > I was able to confirm that secilc -X 2 really removes the attributes
> > that have only one type and reduces the policy size by a few
> > kilobytes.
> >
> > I suspect that the reason for the unremoved attributes in the policy
> > built by semodule are due to a bug in libsepol: It seems that when it
> > starts with a cildb that has the neverallow rules in the input policy
> > + has disable_neverallow set, it removes the rules but not the
> > attributes that are used only in them. Only when it reads the policy
> > again, it identifies these unused attributes (since there are no
> > longer any neverallow rules in the input) and removes them
> > unconditionally. It could be something else, but if I'm right then I
> > think libsepol should be fixed to remove the unused attributes right
> > away. I don't dare digging into the CIL code to investigate it, though
> > ;)
>
> James will have to confirm the details but IIRC we had to keep
> attributes in the policy
> when they are referenced by a neverallow in order to avoid breaking
> Android because
> it uses the attribute definition from the policy as part of CTS
> validation of OEM policies
> (it extracts the neverallows from the AOSP policy, extracts the binary
> policy from the device,
> and checks the neverallows against the device policy).
>

Steve is correct, we keep attributes that appear in neverallow rules
to avoid breaking Android. We also keep attributes that appear in
typeattributesets for attributes that appear in neverallow rules.

See commits 67b410e80f0917bf1b378997cac0dddf1e6406f7 (libsepol/cil:
Keep attributes used by generated attributes in neverallow rules) and
0be23c3f15fdbef35a57d8586aeeae9b1f7606cc (libsepol/cil: Add ability to
expand some attributes in binary policy) for more details.

Jim

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Ondrej Mosnacek]

On Wed, Mar 4, 2020 at 4:32 PM James Carter <jwcart2@gmail.com> wrote:
> On Wed, Mar 4, 2020 at 9:25 AM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Wed, Mar 4, 2020 at 4:07 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> > > I played with this a bit by recompiling the local binary policy with
> > > secilc and then comparing the CIL of both binary policies (I used this
> > > script [1]) and the results are a bit confusing... There is no
> > > difference in result between -X 0 and -X 1 [2] and in both cases it
> > > removes some unused attributes (those are only referenced from
> > > neverallow rules) that were in the original policy
> > > (/etc/selinux/targeted/policy/policy.31 from my Fedora 31 machine),
> > > but not in the one recompiled via checkpolicy -C + secilc... At least
> > > I was able to confirm that secilc -X 2 really removes the attributes
> > > that have only one type and reduces the policy size by a few
> > > kilobytes.
> > >
> > > I suspect that the reason for the unremoved attributes in the policy
> > > built by semodule are due to a bug in libsepol: It seems that when it
> > > starts with a cildb that has the neverallow rules in the input policy
> > > + has disable_neverallow set, it removes the rules but not the
> > > attributes that are used only in them. Only when it reads the policy
> > > again, it identifies these unused attributes (since there are no
> > > longer any neverallow rules in the input) and removes them
> > > unconditionally. It could be something else, but if I'm right then I
> > > think libsepol should be fixed to remove the unused attributes right
> > > away. I don't dare digging into the CIL code to investigate it, though
> > > ;)
> >
> > James will have to confirm the details but IIRC we had to keep
> > attributes in the policy
> > when they are referenced by a neverallow in order to avoid breaking
> > Android because
> > it uses the attribute definition from the policy as part of CTS
> > validation of OEM policies
> > (it extracts the neverallows from the AOSP policy, extracts the binary
> > policy from the device,
> > and checks the neverallows against the device policy).
> >
>
> Steve is correct, we keep attributes that appear in neverallow rules
> to avoid breaking Android. We also keep attributes that appear in
> typeattributesets for attributes that appear in neverallow rules.
>
> See commits 67b410e80f0917bf1b378997cac0dddf1e6406f7 (libsepol/cil:
> Keep attributes used by generated attributes in neverallow rules) and
> 0be23c3f15fdbef35a57d8586aeeae9b1f7606cc (libsepol/cil: Add ability to
> expand some attributes in binary policy) for more details.

OK, so it is actually expected behavior. Fortunately bumping the
attrs_expand_size to 2 doesn't interfere with this logic (I compared
the binary policies produced by semodule -B with and without the patch
[1] and the neverallow-only attributes were not removed).

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

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

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Stephen Smalley]

On Mon, Mar 2, 2020 at 10:46 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> Yeah, there is currently no test for this. I have something hackish
> that I used locally - I'll try to convert it to something more usable
> an automated and integrate it into the repo.

FWIW, my "test" in this case was to generate unoptimized and optimized
policies before and after the patches,
and use cmp as a first level check on whether the kernel policy was
completely unchanged by the patches, and then when
cmp failed on the old and new optimized policies, I used checkpolicy
-M -F -o policy.conf -b policy.32 to decompile each of the
optimized policies to policy.conf sources, and then I diff'd the two
policy.conf files to see if/where they actually differed.
(normally I'd use sediff for this kind of thing but in this case we
want to see non-semantic differences between the policies wrt
optimization, not just semantic differences, and also sediff took too
much time and memory on Fedora policies until recent changes
by James that I don't think have made their way into an official release yet.)

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Ondrej Mosnacek]

On Thu, Feb 27, 2020 at 5:02 PM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> This series contains two small changes (these don't seem to affect
> performance measurably, but are nonetheless logical) and a patch that
> changes how the policy optimization "type_map" helper structure is
> represented, which speeds up the whole process.
>
> Ondrej Mosnacek (3):
>   libsepol: skip unnecessary check in build_type_map()
>   libsepol: optimize inner loop in build_type_map()
>   libsepol: speed up policy optimization
>
>  libsepol/src/optimize.c | 119 +++++++++++++++++++++++++++++++---------
>  1 file changed, 94 insertions(+), 25 deletions(-)
>
> --
> 2.24.1

I can see this series marked as "Changes Requested" in patchwork - is
there anything requested other than a test for policy optimization?
After 692716fc5fd5 ("libsepol/cil: raise default attrs_expand_size to
2") the second no longer leads to a different output (with expand size
>=2).

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

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Stephen Smalley]

On Fri, Mar 13, 2020 at 7:53 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>
> On Thu, Feb 27, 2020 at 5:02 PM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> > This series contains two small changes (these don't seem to affect
> > performance measurably, but are nonetheless logical) and a patch that
> > changes how the policy optimization "type_map" helper structure is
> > represented, which speeds up the whole process.
> >
> > Ondrej Mosnacek (3):
> >   libsepol: skip unnecessary check in build_type_map()
> >   libsepol: optimize inner loop in build_type_map()
> >   libsepol: speed up policy optimization
> >
> >  libsepol/src/optimize.c | 119 +++++++++++++++++++++++++++++++---------
> >  1 file changed, 94 insertions(+), 25 deletions(-)
> >
> > --
> > 2.24.1
>
> I can see this series marked as "Changes Requested" in patchwork - is
> there anything requested other than a test for policy optimization?
> After 692716fc5fd5 ("libsepol/cil: raise default attrs_expand_size to
> 2") the second no longer leads to a different output (with expand size
> >=2).

I suppose you could move it back to New.

Re: [PATCH 0/3] libsepol: Speed up policy optimization

[Stephen Smalley]

On Fri, Mar 13, 2020 at 3:07 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Fri, Mar 13, 2020 at 7:53 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> >
> > On Thu, Feb 27, 2020 at 5:02 PM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> > > This series contains two small changes (these don't seem to affect
> > > performance measurably, but are nonetheless logical) and a patch that
> > > changes how the policy optimization "type_map" helper structure is
> > > represented, which speeds up the whole process.
> > >
> > > Ondrej Mosnacek (3):
> > >   libsepol: skip unnecessary check in build_type_map()
> > >   libsepol: optimize inner loop in build_type_map()
> > >   libsepol: speed up policy optimization
> > >
> > >  libsepol/src/optimize.c | 119 +++++++++++++++++++++++++++++++---------
> > >  1 file changed, 94 insertions(+), 25 deletions(-)
> > >
> > > --
> > > 2.24.1
> >
> > I can see this series marked as "Changes Requested" in patchwork - is
> > there anything requested other than a test for policy optimization?
> > After 692716fc5fd5 ("libsepol/cil: raise default attrs_expand_size to
> > 2") the second no longer leads to a different output (with expand size
> > >=2).
>
> I suppose you could move it back to New.

I can confirm that it no longer yields a different kernel policy.

Tested-by: Stephen Smalley <sds@tycho.nsa.gov>