Hello all,
I've just finished two optimizations which speeds-up libsepol's
expand_filename_trans() function. Various se* commands (like setsebool,
semodule) now consumes only 15% of CPU time compared to current
expand_filename_trans() implementation.
The first patch is fairly simple and straightforward.
The second patch improves main expand_filename_trans() headache, comparsion of
two linked lists. It chunks the second list by filename_trans->stype value and
now algorithm walks only through piece of list where all elements have matching
filename_trans->stype value.
As an example, semodule run time is greatly decreased on my machine:
Original libsepol:
# time /usr/sbin/semodule -b /etc/selinux/targeted/modules/active/base.pp
real 1m54.548s
user 1m51.535s
sys 0m0.875s
After the first patch:
# time /usr/sbin/semodule -b /etc/selinux/targeted/modules/active/base.pp
real 1m43.243s
user 1m40.247s
sys 0m0.902s
Both patches applied:
# time /usr/sbin/semodule -b /etc/selinux/targeted/modules/active/base.pp
real 0m20.752s
user 0m18.508s
sys 0m0.984s
Any comments are welcomed.
Regards, Adam
--
Adam Tkac, Red Hat, Inc.
>From 1909d076f7339f9e8e581a858e4d618df57fa221 Mon Sep 17 00:00:00 2001
From: Adam Tkac <atkac@xxxxxxxxxx>
Date: Fri, 25 May 2012 17:42:08 +0200
Subject: [PATCH 1/2] Optimize expand_filename_trans() function, part1.
Currently expand_filename_trans() function use much CPU time to find
end of the state->out->filename_trans list. This is not needed because
data can be prepended instead of appended to the list.
This ends with 10% speed-up of various se* commands (semodule, setsebool).
Signed-off-by: Adam Tkac <atkac@xxxxxxxxxx>
---
libsepol/src/expand.c | 14 +++-----------
1 file changed, 3 insertions(+), 11 deletions(-)
diff --git a/libsepol/src/expand.c b/libsepol/src/expand.c
index 73b9107..53cca33 100644
--- a/libsepol/src/expand.c
+++ b/libsepol/src/expand.c
@@ -1352,16 +1352,11 @@ 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, *tail, *cur_trans;
+ filename_trans_t *new_trans, *cur_trans;
filename_trans_rule_t *cur_rule;
ebitmap_t stypes, ttypes;
ebitmap_node_t *snode, *tnode;
- /* start at the end of the list */
- tail = state->out->filename_trans;
- while (tail && tail->next)
- tail = tail->next;
-
cur_rule = rules;
while (cur_rule) {
uint32_t mapped_otype;
@@ -1422,11 +1417,8 @@ static int expand_filename_trans(expand_state_t *state, filename_trans_rule_t *r
return -1;
}
memset(new_trans, 0, sizeof(*new_trans));
- if (tail)
- tail->next = new_trans;
- else
- state->out->filename_trans = new_trans;
- tail = 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) {
--
1.7.10.2
>From 4aa82f34bc253f48e353e11a12ff04335e2102ea Mon Sep 17 00:00:00 2001
From: Adam Tkac <atkac@xxxxxxxxxx>
Date: Fri, 25 May 2012 17:55:08 +0200
Subject: [PATCH 2/2] 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>
---
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 53cca33..6201596 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
