Re: [PATCH 3/3] Tweak avtab hash table parameters for better performance

[John Brooks <john.brooks@xxxxxxxxx>]

On Jan 12, 2015, at 10:47 AM, Stephen Smalley <sds@xxxxxxxxxxxxx> wrote:

On 01/07/2015 05:03 PM, John Brooks wrote:

@@ -341,8 +341,6 @@ int avtab_alloc(avtab_t *h, uint32_t nrules)
work  = work >> 1;
shift++;
}
- if (shift > 2)
- shift = shift - 2;
nslot = 1 << shift;
if (nslot > MAX_AVTAB_SIZE)
nslot = MAX_AVTAB_SIZE;

tweakavtab.txt:rules:  101401 entries and 68460/131072 buckets used,
longest chain length 7

Seems like we're wasting a large number of buckets in that scenario.

Good catch. It looks like this is caused by the segment I highlighted above, removing the shift adjustment.

changed-nslot.txt:rules:  100967 entries and 68321/131072 buckets used, longest chain length 8

original-nslot.txt:rules:  100967 entries and 31017/32768 buckets used, longest chain length 13

So, one bucket is allocated per 2-4 elements. The change I actually wanted to make is to the definition of MAX_AVTAB_SIZE: it should be 2x MAX_AVTAB_HASH_BUCKETS to allow allocating a hash with maximum buckets, and that nslot bounding should use MAX_AVTAB_HASH_BUCKETS.

Also, in the corresponding kernel code (security/selinux/ss/avtab.[hc]),
we've actually shrunk the hash bits from 13 to 11,

Interesting. I wonder what the kernel hash eval looks like - it might benefit from a better hash function as well.

I've also considered reworking the libsepol check_assertions() code to
not expand the avtab in order to provide better traceback to the
original source allow rule that violated the neverallow.  This would
require more work by check_assertion_helper to check each attribute
associated with the source and target, just as with
context_struct_compute_av.

Yeah; I expect there is a lot of room for algorithmic improvement here. I wish I had time to understand and fix it. We could probably get this running on the order of seconds instead of minutes, and using _much_ less memory.

Even after these patches, expand_module spends 60% in avtab_search_node (and 13% malloc_consolidate, the rest is trivial). Next step would be to reduce the number of elements or lookups.

One interesting note: this fully expanded table is built twice under expand_module, for hierarchy_check_constraints and check_assertions. We could cut runtime almost in half by reusing the table.

_______________________________________________
Selinux mailing list
Selinux@xxxxxxxxxxxxx
To unsubscribe, send email to Selinux-leave@xxxxxxxxxxxxx.
To get help, send an email containing "help" to Selinux-request@xxxxxxxxxxxxx.