diff mbox series

[3/3] libsepol: speed up policy optimization

Message ID 20200227160257.340737-4-omosnace@redhat.com (mailing list archive)
State Accepted
Headers show
Series libsepol: Speed up policy optimization | expand

Commit Message

Ondrej Mosnacek Feb. 27, 2020, 4:02 p.m. UTC 
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(-)

Comments

Stephen Smalley March 17, 2020, 6:24 p.m. UTC | #1 
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>
James Carter March 19, 2020, 7:39 p.m. UTC | #2 
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
diff mbox series

Patch

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;