On Jul 18, 2010, at 4:11 PM, Kyle Moffett wrote:
> Hmm, it looks like this email never made it to the list (spamfilter
> maybe?) I'm re-forwarding it here:
Am I interpreting the code correctly, that a hashtable with with 512 buckets is used to lookup types?
On my development machine:
seinfo -t | wc -l
WARNING: This policy contained disabled aliases; they have been removed.
4820
Average bucket depth of 9.4 seems kind of high. Is there any harm in raising the #buckets while this patch is discussed on the list?
joe
>
> 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.
--
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.
