[PATCH 82/90] Optimize expand_filename_trans() function

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


   This patch looks good to me. acked.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk/I/CAACgkQrlYvE4MpobMAxQCgkB0Na6PfHbE5ewqXnPjraUfi
VhwAoIVlEsiApylaOKnod/f9E9Uc0lkL
=TzM4
-----END PGP SIGNATURE-----
>From 90b0380c18508e23b33acda50b4d8e9e60cd3166 Mon Sep 17 00:00:00 2001
From: Adam Tkac <atkac@xxxxxxxxxx>
Date: Fri, 25 May 2012 17:55:08 +0200
Subject: [PATCH 82/90] Optimize expand_filename_trans() function, part2.

The expand_filename_trans() function consumed vast majority of time by comparsion
of two lists with dumb algorithm with O(n^2) complexity.

Now it chunks one list by it's filename_trans->stype value to limit length of
elements which needs to be walked when comparing filename_trans_t element with
this chunked list.

This change speeds-up se* commands by 80%.

Signed-off-by: Adam Tkac <atkac@xxxxxxxxxx>
Signed-off-by: Eric Paris <eparis@xxxxxxxxxx>
---
 libsepol/src/expand.c |  112 +++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 103 insertions(+), 9 deletions(-)

diff --git a/libsepol/src/expand.c b/libsepol/src/expand.c
index bef759c..5e52df3 100644
--- a/libsepol/src/expand.c
+++ b/libsepol/src/expand.c
@@ -49,6 +49,81 @@ typedef struct expand_state {
 	int expand_neverallow;
 } expand_state_t;
 
+typedef struct {
+	filename_trans_t **table;	/* filename_trans chunks with same stype */
+	filename_trans_t **ends;	/* pointers to ends of **table chunks */
+	uint32_t length;		/* length of the table */
+} linear_probe_t;
+
+static int linear_probe_create(linear_probe_t *probe, uint32_t length)
+{
+	probe->table = malloc(sizeof(*probe->table) * length);
+	if (probe->table == NULL)
+		return -1;
+	memset(probe->table, 0, sizeof(*probe->table) * length);
+
+	probe->ends = malloc(sizeof(*probe->ends) * length);
+	if (probe->ends == NULL)
+		return -1;
+	memset(probe->ends, 0, sizeof(*probe->ends) * length);
+
+	probe->length = length;
+
+	return 0;
+}
+
+static void linear_probe_destroy(linear_probe_t *probe)
+{
+	if (probe->length == 0)
+		return;
+
+	free(probe->table);
+	free(probe->ends);
+	memset(probe, 0, sizeof(*probe));
+}
+
+static void linear_probe_insert(linear_probe_t *probe, uint32_t key,
+				filename_trans_t *data)
+{
+	assert(probe->length > key);
+
+	if (probe->table[key] != NULL) {
+		data->next = probe->table[key];
+		probe->table[key] = data;
+	} else {
+		probe->table[key] = probe->ends[key] = data;
+	}
+}
+
+static filename_trans_t *linear_probe_find(linear_probe_t *probe, uint32_t key)
+{
+	assert(probe->length > key);
+
+	return probe->table[key];
+}
+
+/* Returns all chunks stored in the *probe as single-linked list */
+static filename_trans_t *linear_probe_dump(linear_probe_t *probe,
+					   filename_trans_t **endp)
+{
+	uint32_t i;
+	filename_trans_t *result = NULL;
+	filename_trans_t *end = NULL;
+
+	for (i = 0; i < probe->length; i++) {
+		if (probe->table[i] != NULL) {
+			if (end == NULL)
+				end = probe->ends[i];
+			probe->ends[i]->next = result;
+			result = probe->table[i];
+			probe->table[i] = probe->ends[i] = NULL;
+		}
+	}
+
+	*endp = end;
+	return result;
+}
+
 static void expand_state_init(expand_state_t * state)
 {
 	memset(state, 0, sizeof(expand_state_t));
@@ -1352,10 +1427,20 @@ static int copy_role_trans(expand_state_t * state, role_trans_rule_t * rules)
 static int expand_filename_trans(expand_state_t *state, filename_trans_rule_t *rules)
 {
 	unsigned int i, j;
-	filename_trans_t *new_trans, *cur_trans;
+	filename_trans_t *new_trans, *cur_trans, *end;
 	filename_trans_rule_t *cur_rule;
 	ebitmap_t stypes, ttypes;
 	ebitmap_node_t *snode, *tnode;
+	linear_probe_t probe;
+
+	/*
+	 * Linear probing speeds-up finding filename_trans rules with certain
+	 * "stype" value.
+	 */
+	if (linear_probe_create(&probe, 4096)) { /* Assume 4096 is enough for most cases */
+		ERR(state->handle, "Out of memory!");
+		return -1;
+	}
 
 	cur_rule = rules;
 	while (cur_rule) {
@@ -1378,6 +1463,14 @@ static int expand_filename_trans(expand_state_t *state, filename_trans_rule_t *r
 
 		mapped_otype = state->typemap[cur_rule->otype - 1];
 
+		if (ebitmap_length(&stypes) > probe.length) {
+			linear_probe_destroy(&probe);
+			if (linear_probe_create(&probe, ebitmap_length(&stypes))) {
+				ERR(state->handle, "Out of memory!");
+				return -1;
+			}
+		}
+
 		ebitmap_for_each_bit(&stypes, snode, i) {
 			if (!ebitmap_node_get_bit(snode, i))
 				continue;
@@ -1385,16 +1478,14 @@ static int expand_filename_trans(expand_state_t *state, filename_trans_rule_t *r
 				if (!ebitmap_node_get_bit(tnode, j))
 					continue;
 
-				cur_trans = state->out->filename_trans;
-				while (cur_trans) {
-					if ((cur_trans->stype == i + 1) &&
-					    (cur_trans->ttype == j + 1) &&
+				cur_trans = linear_probe_find(&probe, i);
+				while (cur_trans != NULL) {
+					if ((cur_trans->ttype == j + 1) &&
 					    (cur_trans->tclass == cur_rule->tclass) &&
 					    (!strcmp(cur_trans->name, cur_rule->name))) {
 						/* duplicate rule, who cares */
 						if (cur_trans->otype == mapped_otype)
 							break;
-
 						ERR(state->handle, "Conflicting filename trans rules %s %s %s : %s otype1:%s otype2:%s",
 						    cur_trans->name,
 						    state->out->p_type_val_to_name[i],
@@ -1402,7 +1493,7 @@ static int expand_filename_trans(expand_state_t *state, filename_trans_rule_t *r
 						    state->out->p_class_val_to_name[cur_trans->tclass - 1],
 						    state->out->p_type_val_to_name[cur_trans->otype - 1],
 						    state->out->p_type_val_to_name[mapped_otype - 1]);
-						    
+
 						return -1;
 					}
 					cur_trans = cur_trans->next;
@@ -1417,8 +1508,6 @@ static int expand_filename_trans(expand_state_t *state, filename_trans_rule_t *r
 					return -1;
 				}
 				memset(new_trans, 0, sizeof(*new_trans));
-				new_trans->next = state->out->filename_trans;
-				state->out->filename_trans = new_trans;
 
 				new_trans->name = strdup(cur_rule->name);
 				if (!new_trans->name) {
@@ -1429,9 +1518,14 @@ static int expand_filename_trans(expand_state_t *state, filename_trans_rule_t *r
 				new_trans->ttype = j + 1;
 				new_trans->tclass = cur_rule->tclass;
 				new_trans->otype = mapped_otype;
+				linear_probe_insert(&probe, i, new_trans);
 			}
 		}
 
+		cur_trans = linear_probe_dump(&probe, &end);
+		end->next = state->out->filename_trans;
+		state->out->filename_trans = cur_trans;
+
 		ebitmap_destroy(&stypes);
 		ebitmap_destroy(&ttypes);
 
-- 
1.7.10.2


[Index of Archives]     [Selinux Refpolicy]     [Linux SGX]     [Fedora Users]     [Fedora Desktop]     [Yosemite Photos]     [Yosemite Camping]     [Yosemite Campsites]     [KDE Users]     [Gnome Users]

  Powered by Linux