BUG: kernel softlockup due to too many SIDs/contexts

[stephensmalley]

As reported by yangjhong1 on selinux list, when too many SIDs/contexts have been allocated (e.g. 300000+ as a result of repeated docker container creations for 2 days), sidtab_search_context becomes very slow and can cause a kernel softlockup warning.
docker randomly selects a category pair for every container creation, so this can occur just from creating containers over time, even if old containers are removed promptly (category set reuse for removed containers will eventually occur but each selection is random). It can also occur from any other activity that allocates SIDs/contexts, even those that simply probe for context validity.
sidtab_search_context() is a reverse lookup in the sidtab and presently just walks the entire hash table.
At a minimum, we need to add a reverse hash table to help mitigate this, possibly using a SELinux hashtab or the core kernel's hashtable.h or rhashtable.h data structures. We might also want a fast check of the context category set to see if it has ever been previously used (i.e. maintain a ebitmap of used categories, and check whether it contains the context's category set) so that we can fail fast on a lookup of a new category set. However, the fact that we might need to support 300000+ SIDs/contexts also suggests that we should likely revisit the sidtab forward hash table since it is too small to efficiently handle that. That too is a candidate to be replaced by e.g. hashtable or rhashtable.
I can see both short term and long term fixes for this bug; short term might just be adding simple reverse hash table and perhaps a category ebitmap test; longer term might be reworking the forward hash and switching over to hashtable or rhashtable structures.

[stephensmalley]

Nothing new on this front, just dumping some notes here for later reference:

1. We need a good hash function for SELinux context structures. We
   don't already have one since normally we only go the other direction or
   only deal with a hash of type pairs, not full contexts. And since the
   only distinction for these docker-generated contexts will be the
   category sets, we need a hash function that incorporates the ebitmaps.
   I threw together a quick one that internally uses jhash but don't yet
   know anything about its performance or distribution characteristics.
   The other model would be to hash the context strings, but we don't
   presently keep those in the sidtab unless the context is unmapped (i.e.
   temporarily invalid under the current policy).

2. hashtab_insert assumes it can sleep (GFP_KERNEL allocation), whereas
   sidtab_insert has to support non-blocking use. Easy enough to
   introduce a variant that takes gfp flags, but had to be done.

3. hashtab_insert/search assume that the caller is handling locking; in
   the case of the policydb hashtabs, this is done via the policy read
   lock for searches and we only insert into new hashtabs during policy
   creation and then switch under write lock. The sidtab on the other
   hand was written to support lockless searches and a simple spinlock on
   inserts; I originally followed the guidance in Rusty's locking guide
   (Documentation/kernel-hacking/locking.rst) and used a wmb() within
   sidtab_insert so that _search could remain lockless. However, it looks
   to me like guidance has changed on barriers as per
   Documentation/memory-barriers.txt, we should probably be using
   smp_wmb() instead, and we are supposed to pair it with a read or data
   dependency barrier. This would mean that we not only need to amend
   hashtab_insert/search to use barriers appropriately for use within the
   sidtab but also fix the sidtab usage, and I'm not yet clear on exactly
   what that should look like.

4. The natural place to add entries to the reverse table is within
   sidtab_insert, when we are adding the forward lookup entry. However,
   some of the sidtab_insert() calls occur with contexts that are already
   mapped to the new policy (for the initial SIDs, loaded directly from
   policy) and others are with contexts that are mapped to the new policy
   in a later phase (for the SIDs cloned from the old sidtab during policy
   reload). We'd need to refactor the way this is done during policy
   reload to avoid this problem.

5. Duplicates are legitimately possible when inserting into the reverse
   table, due to initial SIDs potentially being mapped to the same context
   (e.g. many of the legacy ones are now mapped to unlabeled). So we have
   to ignore EEXIST from hashtab_insert, or otherwise distinguish when we
   should or should not accept this situation.

[WOnder93]

For reference, here is the original selinux ML thread:
https://lore.kernel.org/selinux/1BC3DBD98AD61A4A9B2569BC1C0B4437D5D1F3@DGGEMM506-MBS.china.huawei.com/T/

I believe this issue has been incidentally mitigated by the recently merged sidtab overhaul (see issue #38). Even though the asymptotic complexity of reverse sidtab lookup is still suboptimal (remains at O(n)), the operation is now implemented much more efficiently.

I used this bit of Python code to fill up sidtab with tons of entries:

for i in range(1024):
    for k in range(1024):
        f = open('/sys/fs/selinux/context', 'w')
        f.write('system_u:system_r:kernel_t:s0:c{0},c{1}'.format(i, k))
        f.close()
    print(i * 1024)

On a kernel without the #38 patch, after reaching ~280000 sidtab entries (which took over an hour), running echo -n 'unconfined_u:unconfined_r:unconfined_t:s0-s0:c0.c1023 unconfined_u' > /sys/fs/selinux/user took about 2 seconds to complete (due to the output buffer being too small it errors out with with -ERANGE, but only after the whole result has been already computed).

When I tried the same with a patched kernel, the fill up script advanced much faster and the write to /sys/fs/selinux/user finished in under a second, even after running the fill up script to completion (it took just 0.3 seconds with all the 1047552 entries).

I wasn't able to actually trigger the soft lockup even with an unpatched kernel (I suppose I'd need a much slower system and/or wait days for sidtab to reach enough entries), but hopefully it is now much much harder to trigger it in a practical scenario.

[stephensmalley]

Yes, I think we can close this issue and consider it fixed until/unless someone encounters the bug again.
As a side note, we would like to kill usage of /sys/fs/selinux/user by userspace, deprecate it, and remove it, see SELinuxProject/selinux#28