On Sun, 2010-07-18 at 17:11 -0400, Kyle Moffett wrote: > Hmm, it looks like this email never made it to the list (spamfilter > maybe?) I'm re-forwarding it here: He doesn't appear to be subscribed to the list, and I don't see the original posting even on the approval list. Can he or you re-post it in an appliable form (looks like the original patch wasn't generated against the top-level selinux git repo and re-forwarding further mangled it)? Thanks. > Cheers, > Kyle Moffett > > On Fri, Jul 16, 2010 at 17:50, Matthew Robertson > <Matthew.L.Robertson@xxxxxxxxxx> wrote: > > 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. > > > > 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 > > > > Signed-off-by: Matthew Robertson <Matthew.L.Robertson@xxxxxxxxxx> > > --- > > src/avtab.c | 52 +++++++++++++++++++++++++++----- > > src/hashtab.c | 91 +++++++++++++++++++++++++++++++++++++++----------------- > > 2 files changed, 106 insertions(+), 37 deletions(-) > > > > diff --git a/src/avtab.c b/src/avtab.c > > index ea947cb..2db931e 100644 > > --- a/src/avtab.c > > +++ b/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; > > + avtab_ptr_t prev, cur; > > + 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, newnode, *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/src/hashtab.c b/src/hashtab.c > > index c4be72c..e06d808 100644 > > --- a/src/hashtab.c > > +++ b/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 hashtab_insert__(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum) > > { > > - int hvalue; > > - hashtab_ptr_t prev, cur, newnode; > > + 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) > > +{ > > + 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. -- Stephen Smalley National Security Agency -- 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.