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

[Stephen Smalley <sds@tycho.nsa.gov>]

On 01/13/2015 08:50 AM, Stephen Smalley wrote:
> On 01/12/2015 08:25 PM, John Brooks wrote:
>> On Jan 12, 2015, at 10:47 AM, Stephen Smalley <sds@tycho.nsa.gov
>> <mailto:sds@tycho.nsa.gov>> 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.
> 
> Permission checks in the kernel are usually handled by the AVC (access
> vector cache), so the looking it up in the avtab is the slow path already.

That said, it wouldn't hurt to look at improving the hash function there
as well, and possibly for the AVC too.

One thing to note is that we never envisioned such large policies when
we created SELinux (the original example policy was much smaller).  The
Fedora policy unfortunately ships with every possible module/domain that
one could ever use included, and does not attempt to reduce the policy
to only the subset required for the given system.  Admittedly that is a
hard problem.  In the Android case, we were careful to keep the policy
small from the beginning, but there we have a much smaller and more
constrained userspace environment.