On 01/12/2015 12:47 PM, Stephen Smalley wrote:
> On 01/07/2015 05:03 PM, John Brooks wrote:
>> Using the Fedora 20 targeted policy, running check_assertions requires
>> an avtab with around 22 million elements. With the default limit of 4096
>> buckets, performance is abysmal: it takes more than an hour to populate
>> the hash. Profiling shows most of that time under avtab_search_node.
>>
>> This patch increases the hash from 13 to 20 bits and to a maximum of
>> 1048576 buckets. The time for check_assertions on that policy is reduced
>> to about 3 minutes, which is enough to re-enable those checks as part of
>> the build process.
>>
>> A full size table will allocate 4-8 MB of memory, up from 16-32 KB. In a
>> cursory review, these tables are usually short-lived and only 1-3 are
>> allocated together. Compared to the cost of entries in this table (up to
>> 1 GB using the same policy), this isn't a significant increase.
>> ---
>> libsepol/include/sepol/policydb/avtab.h | 4 ++--
>> libsepol/src/avtab.c | 4 +---
>> 2 files changed, 3 insertions(+), 5 deletions(-)
>>
>> diff --git a/libsepol/include/sepol/policydb/avtab.h b/libsepol/include/sepol/policydb/avtab.h
>> index 6955ecf..158112f 100644
>> --- a/libsepol/include/sepol/policydb/avtab.h
>> +++ b/libsepol/include/sepol/policydb/avtab.h
>> @@ -81,7 +81,7 @@ typedef struct avtab {
>> avtab_ptr_t *htable;
>> uint32_t nel; /* number of elements */
>> uint32_t nslot; /* number of hash slots */
>> - uint16_t mask; /* mask to compute hash func */
>> + uint32_t mask; /* mask to compute hash func */
>> } avtab_t;
>>
>> extern int avtab_init(avtab_t *);
>> @@ -117,7 +117,7 @@ extern avtab_ptr_t avtab_search_node(avtab_t * h, avtab_key_t * key);
>>
>> extern avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified);
>>
>> -#define MAX_AVTAB_HASH_BITS 13
>> +#define MAX_AVTAB_HASH_BITS 20
>> #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
>> #define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
>> #define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
>> diff --git a/libsepol/src/avtab.c b/libsepol/src/avtab.c
>> index 9c01a8d..65b3c48 100644
>> --- a/libsepol/src/avtab.c
>> +++ b/libsepol/src/avtab.c
>> @@ -329,7 +329,7 @@ int avtab_init(avtab_t * h)
>>
>> int avtab_alloc(avtab_t *h, uint32_t nrules)
>> {
>> - uint16_t mask = 0;
>> + uint32_t mask = 0;
>> uint32_t shift = 0;
>> uint32_t work = nrules;
>> uint32_t nslot = 0;
>> @@ -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;
>>
>
> Here again, looking at impact on regular usage of the avtab (without
> full expansion of all attributes), running checkpolicy -Mb
> /etc/selinux/targeted/policy/policy.29 on Fedora 20 before and after
> this patch, I see:
>
> before.txt:rules: 101401 entries and 8169/8192 buckets used, longest
> chain length 84
>
> betterhash.txt:rules: 101401 entries and 8192/8192 buckets used,
> longest chain length 27
>
> 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.
>
> Also, in the corresponding kernel code (security/selinux/ss/avtab.[hc]),
> we've actually shrunk the hash bits from 13 to 11,
>
> commit 6c9ff1013b7a21099da838eeef7c3f23ee347957
> Author: Stephen Smalley <sds@xxxxxxxxxxxxx>
> Date: Mon Mar 15 10:42:11 2010 -0400
>
> SELinux: Reduce max avtab size to avoid page allocation failures
>
> Reduce MAX_AVTAB_HASH_BITS so that the avtab allocation is an order 2
> allocation rather than an order 4 allocation on x86_64. This
> addresses reports of page allocation failures:
> http://marc.info/?l=selinux&m=126757230625867&w=2
> https://bugzilla.redhat.com/show_bug.cgi?id=570433
>
> Reported-by: Russell Coker <russell@xxxxxxxxxxxx>
> Signed-off-by: Stephen D. Smalley <sds@xxxxxxxxxxxxx>
> Acked-by: Eric Paris <eparis@xxxxxxxxxx>
> Signed-off-by: James Morris <jmorris@xxxxxxxxx>
>
> That doesn't necessarily mean we can't increase it in libsepol, but
> something to be aware of. Of course the kernel never expands the rules
> so it doesn't have this issue.
>
> 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.
Might also want to consider taking the ebitmap scanning optimization
done in the kernel to libsepol. That would help with the
ebitmap_for_each_bit() loops.
_______________________________________________
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.
