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

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

On 11/18/19 9:20 AM, Stephen Smalley wrote:
> 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.

Hmm...are you always setting context->hash before inserting the entry?
Contexts loaded from the policydb won't have them...

> 
>>
>>
>>>
>>> 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(-)
>>>
>