After spending a lot of developer time recently doing repeated relinks of
policies after making minor changes we put some time into tracking down avenues
for improving performance in the SELinux libraries. On a reasonably modern HP
server a 'make load' of a precompiled SELinux Reference Policy takes roughly 96
seconds. The 'perf' tool pointed us to some undersized and overpopulated hash
tables in libsepol's hashtab.c and avtab.c. By implementing dynamic resizing for
those structures we were able to bring that down to a 19 second runtime (80%
performance improvement) at the cost of ~6% more memory overhead.
Signed-off-by: Matthew Robertson <Matthew.L.Robertson@xxxxxxxxxx>
---
After applying this fix, bzip2 takes up a disproportionate percentage of the
time for a policy load. By effectively disabling bzip2 (changing bzip_blocksize
in libsemanage to 0) we reduced load time to about 11 seconds--disabling
compression might not be a tenable solution but supporting a faster compression
option like gzip could be worth the trouble if the other fixes check out.
For reference, here are the numbers and perf reports we're looking at for the
policy loading step after a compile/install:
SELinux Reference Policy v2.20091117
libsepol v2.0.41
libsemanage v2.0.45
libselinux v2.0.94
libbz2 v1.0.5-4
ORIGINAL LIBRARIES: 96.0s
[full compile + load: 142s]
54.34% semodule /lib/libc-2.11.2.so [.] __strcmp_sse42
16.08% semodule /lib/libsepol.so.1 [.] hashtab_search
4.74% semodule /lib/libsepol.so.1 [.] symcmp
3.98% semodule /lib/libsepol.so.1 [.] strcmp@plt
3.76% semodule /lib/libbz2.so.1.0.4 [.] 0x0000000000b0bc
2.80% semodule /lib/libsepol.so.1 [.] avtab_search_node
2.72% semodule /lib/libbz2.so.1.0.4 [.] 0x000000000022d0
1.51% semodule /lib/libsepol.so.1 [.] ebitmap_set_bit
1.12% semodule /lib/libsepol.so.1 [.] hashtab_map
1.00% semodule /lib/libsepol.so.1 [.] symhash
0.95% semodule /lib/libbz2.so.1.0.4 [.] BZ2_decompress
0.90% semodule /lib/libbz2.so.1.0.4 [.] BZ2_compressBlock
0.68% semodule /lib/libc-2.11.2.so [.] __strlen_sse42
0.57% semodule /lib/libbz2.so.1.0.4 [.] BZ2_bzDecompress
DYNAMIC HASHING ENABLED, BZIP2 LEFT ENABLED: 19s, 80% improvement
[full compile + load: 70.5s, ~50% improvement]
28.57% semodule /lib/libbz2.so.1.0.4 [.] 0x0000000000b539
7.53% semodule /lib/libsepol.so.1 [.] ebitmap_set_bit
7.24% semodule /lib/libc-2.11.2.so [.] __strcmp_sse42
5.91% semodule /lib/libsepol.so.1 [.] hashtab_map
4.91% semodule /lib/libsepol.so.1 [.] symhash
4.66% semodule /lib/libsepol.so.1 [.] hashtab_search
4.58% semodule /lib/libbz2.so.1.0.4 [.] BZ2_decompress
4.46% semodule /lib/libbz2.so.1.0.4 [.] BZ2_compressBlock
4.38% semodule /lib/libsepol.so.1 [.] avtab_search_node
3.40% semodule /lib/libbz2.so.1.0.4 [.] 0x0000000000d1f9
2.29% semodule /lib/libbz2.so.1.0.4 [.] BZ2_bzDecompress
DYNAMIC HASHING ENABLED, BZIP2 DISABLED: 11 seconds, 88% improvement
[full compile + load: 62s, ~55% improvement]
13.39% semodule /lib/libsepol.so.1 [.] ebitmap_set_bit
12.77% semodule /lib/libc-2.11.2.so [.] __strcmp_sse42
10.44% semodule /lib/libsepol.so.1 [.] hashtab_map
8.91% semodule /lib/libsepol.so.1 [.] symhash
8.28% semodule /lib/libsepol.so.1 [.] hashtab_search
7.74% semodule /lib/libsepol.so.1 [.] avtab_search_node
libsepol/src/avtab.c | 48 ++++++++++++++++++++++----
libsepol/src/hashtab.c | 89 +++++++++++++++++++++++++++++++++--------------
2 files changed, 103 insertions(+), 34 deletions(-)
diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
index ea947cb..51abd04 100644
--- a/libsepol/src/avtab.c
+++ b/libsepol/src/avtab.c
@@ -78,17 +78,13 @@ avtab_insert_node(avtab_t * h, int hvalue, avtab_ptr_t prev, avtab_key_t * key,
return newnode;
}
-int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
+int avtab_insert__(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
{
- int hvalue;
avtab_ptr_t prev, cur, newnode;
+ int hvalue = avtab_hash(key, h->mask);
uint16_t specified =
key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
- if (!h || !h->htable)
- return SEPOL_ENOMEM;
-
- hvalue = avtab_hash(key, h->mask);
for (prev = NULL, cur = h->htable[hvalue];
cur; prev = cur, cur = cur->next) {
if (key->source_type == cur->key.source_type &&
@@ -110,8 +106,46 @@ int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
newnode = avtab_insert_node(h, hvalue, prev, key, datum);
if (!newnode)
return SEPOL_ENOMEM;
+ return SEPOL_OK;
+}
- return 0;
+int avtab_insert(avtab_t * h, avtab_key_t * key, avtab_datum_t * datum)
+{
+ int oldsize, i;
+ avtab_ptr_t prev, cur, *oldtbl, *newtbl;
+
+ if (!h || !h->htable)
+ return SEPOL_ENOMEM;
+
+ /* If we don't need to resize, just insert the new entry */
+ if (h->nslot * 3/4 > h->nel)
+ return avtab_insert__(h, key, datum);
+
+ /* Attempt to allocate a bigger table */
+ newtbl = (avtab_ptr_t*) calloc(sizeof(avtab_ptr_t), h->nslot * 2);
+ if (newtbl == NULL)
+ return avtab_insert__(h, key, datum);
+
+ /* Reinsert all elements into the new table */
+ h->nel = 0;
+ oldsize = h->nslot;
+ h->nslot *= 2;
+ h->mask = h->nslot - 1;
+ oldtbl = h->htable;
+ h->htable = newtbl;
+
+ for (i = 0; i < oldsize; i++) {
+ cur = oldtbl[i];
+ while (cur != NULL) {
+ avtab_insert(h, &(cur->key), &(cur->datum));
+ prev = cur;
+ cur = cur->next;
+ free (prev);
+ }
+ }
+ free (oldtbl);
+
+ return avtab_insert__(h, key, datum);
}
/* Unlike avtab_insert(), this function allow multiple insertions of the same
diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c
index c4be72c..943a2cd 100644
--- a/libsepol/src/hashtab.c
+++ b/libsepol/src/hashtab.c
@@ -63,41 +63,76 @@ hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h,
return p;
}
+int hashtab_insert__(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
+{
+ int hvalue = h->hash_value(h, key);
+ hashtab_ptr_t prev = NULL;
+ hashtab_ptr_t cur = h->htable[hvalue];
+ hashtab_ptr_t newnode;
+
+ while (cur && h->keycmp(h, key, cur->key) > 0) {
+ prev = cur;
+ cur = cur->next;
+ }
+
+ if (cur && (h->keycmp(h, key, cur->key) == 0))
+ return SEPOL_EEXIST;
+
+ newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
+ if (newnode == NULL)
+ return SEPOL_ENOMEM;
+ memset(newnode, 0, sizeof(struct hashtab_node));
+ newnode->key = key;
+ newnode->datum = datum;
+ if (prev) {
+ newnode->next = prev->next;
+ prev->next = newnode;
+ } else {
+ newnode->next = h->htable[hvalue];
+ h->htable[hvalue] = newnode;
+ }
+
+ h->nel++;
+ return SEPOL_OK;
+}
+
int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
{
- int hvalue;
- hashtab_ptr_t prev, cur, newnode;
+ hashtab_ptr_t *oldtbl, *newtbl;
+ int oldsize, i;
if (!h)
return SEPOL_ENOMEM;
- hvalue = h->hash_value(h, key);
- prev = NULL;
- cur = h->htable[hvalue];
- while (cur && h->keycmp(h, key, cur->key) > 0) {
- prev = cur;
- cur = cur->next;
- }
-
- if (cur && (h->keycmp(h, key, cur->key) == 0))
- return SEPOL_EEXIST;
-
- newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
- if (newnode == NULL)
- return SEPOL_ENOMEM;
- memset(newnode, 0, sizeof(struct hashtab_node));
- newnode->key = key;
- newnode->datum = datum;
- if (prev) {
- newnode->next = prev->next;
- prev->next = newnode;
- } else {
- newnode->next = h->htable[hvalue];
- h->htable[hvalue] = newnode;
+ /* If we don't need to resize, just insert the new entry */
+ if (h->size > h->nel)
+ return hashtab_insert__(h, key, datum);
+
+ /* Attempt to allocate a bigger table */
+ newtbl = (hashtab_ptr_t*) calloc(sizeof(hashtab_ptr_t), h->size * 8);
+ if (newtbl == NULL)
+ return hashtab_insert__(h, key, datum);
+
+ /* Reinsert all elements into the new table */
+ oldtbl = h->htable;
+ oldsize = h->size;
+ h->nel = 0;
+ h->size *= 8;
+ h->htable = newtbl;
+
+ for (i = 0; i < oldsize; i++) {
+ hashtab_ptr_t prev = NULL;
+ hashtab_ptr_t cur = oldtbl[i];
+ while (cur != NULL) {
+ hashtab_insert__(h, cur->key, cur->datum);
+ prev = cur;
+ cur = cur->next;
+ free(prev);
+ }
}
+ free(oldtbl);
- h->nel++;
- return SEPOL_OK;
+ return hashtab_insert__(h, key, datum);
}
int hashtab_remove(hashtab_t h, hashtab_key_t key,
--
1.7.0
--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@xxxxxxxxxxxxx with
the words "unsubscribe selinux" without quotes as the message.
