Re: [PATCH v7] selinux: sidtab: reverse lookup hash table

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

On 11/18/19 9:19 AM, Stephen Smalley wrote:
> On 11/18/19 7:21 AM, Jeff Vander Stoep wrote:
>> This replaces the reverse table lookup and reverse cache with a
>> hashtable which improves cache-miss reverse-lookup times from
>> O(n) to O(1)* and maintains the same performance as a reverse
>> cache hit.
>>
>> This reduces the time needed to add a new sidtab entry from ~500us
>> to 5us on a Pixel 3 when there are ~10,000 sidtab entries.
>>
>> The implementation uses the kernel's generic hashtable API,
>> It uses the context's string represtation as the hash source,
>> and the kernels generic string hashing algorithm full_name_hash()
>> to reduce the string to a 32 bit value.
>>
>> This change also maintains the improvement introduced in
>> commit ee1a84fdfeed ("selinux: overhaul sidtab to fix bug and improve
>> performance") which removed the need to keep the current sidtab
>> locked during policy reload. It does however introduce periodic
>> locking of the target sidtab while converting the hashtable. Sidtab
>> entries are never modified or removed, so the context struct stored
>> in the sid_to_context tree can also be used for the context_to_sid
>> hashtable to reduce memory usage.
>>
>> This bug was reported by:
>> - On the selinux bug tracker.
>>    BUG: kernel softlockup due to too many SIDs/contexts #37
>>    https://github.com/SELinuxProject/selinux-kernel/issues/37
>> - Jovana Knezevic on Android's bugtracker.
>>    Bug: 140252993
>>    "During multi-user performance testing, we create and remove users
>>    many times. selinux_android_restorecon_pkgdir goes from 1ms to over
>>    20ms after about 200 user creations and removals. Accumulated over
>>    ~280 packages, that adds a significant time to user creation,
>>    making perf benchmarks unreliable."
>>
>> * Hashtable lookup is only O(1) when n < the number of buckets.
>>
>> Changes in V2:
>> -The hashtable uses sidtab_entry_leaf objects directly so these
>> objects are shared between the sid_to_context lookup tree and the
>> context_to_sid hashtable. This simplifies memory allocation and
>> was suggested by Ondrej Mosnacek.
>> -The new sidtab hash stats file in selinuxfs has been moved out of
>> the avc dir and into a new "ss" dir.
>>
>> V3:
>> -Add lock nesting notation.
>>
>> V4/V5:
>> -Moved to *_rcu variants of the various hashtable functions
>> as suggested by Will Deacon.
>> -Naming/spelling fixups.
>>
>> V6
>> -Remove nested locking. Use lock of active sidtab to gate
>> access to the new sidtab.
>> -Remove use of rcu_head/kfree_rcu(), they're unnecessary because
>> hashtable objects are never removed when read/add operations are
>> occurring. Why is this safe? Quoting Ondrej Mosnacek from the
>> selinux mailing list:
>> "It is not visible in this patch, but the sidtab (along with other
>> policy-lifetime structures) is protected by a big fat read-write lock.
>> The only places where sidtab_destroy() is called are (a) error paths
>> when initializing a new sidtab (here the sidtab isn't shared yet, so
>> no race) and (b) when freeing the old sidtab during policy reload - in
>> this case it is happening after a policy write-locked critical
>> section, which had removed the old sidtab pointer from the shared
>> structures, so at that point all sidtab readers will already be
>> accessing the new sidtab and the old one is visible only by the thread
>> doing the destruction."
>>
>> V7
>> -Change format of /sys/fs/selinux/ss/sidtab_hash_stats to match
>> /sys/fs/selinux/avc/hash_stats.
>> -Add __rcu annotation to rcu pointers.
>> -Test with CONFIG_SPARSE_RCU_POINTER and CONFIG_PROVE_RCU.
>> -Add rcu@vger.kernel.org and Paul McKenney to Cc for review of the
>> RCU logic.
> 
> Also, the hash function doesn't seem to be very good; after booting 
> Fedora with this patch, cat /sys/fs/selinux/ss/sidtab_hash_stats shows:
> entries: 2571
> buckets used: 152/512
> longest chain: 1008

Curiously, running load_policy to reload policy once after boot improves 
the situation markedly:
$ cat /sys/fs/selinux/ss/sidtab_hash_stats
entries: 2587
buckets used: 490/512
longest chain: 13

I'm not clear on what is happening there.

> 
> 
>>
>> Signed-off-by: Jeff Vander Stoep <jeffv@google.com>
>> Reported-by: Stephen Smalley <sds@tycho.nsa.gov>
>> Reported-by: Jovana Knezevic <jovanak@google.com>
>> ---
>>   security/selinux/Kconfig            |  12 ++
>>   security/selinux/include/security.h |   1 +
>>   security/selinux/selinuxfs.c        |  65 +++++++
>>   security/selinux/ss/context.h       |  11 +-
>>   security/selinux/ss/policydb.c      |   5 +
>>   security/selinux/ss/services.c      |  83 +++++++--
>>   security/selinux/ss/services.h      |   4 +-
>>   security/selinux/ss/sidtab.c        | 263 ++++++++++++++--------------
>>   security/selinux/ss/sidtab.h        |  18 +-
>>   9 files changed, 300 insertions(+), 162 deletions(-)
>>