Re: [RFC PATCH v4 2/2] selinux: overhaul sidtab to fix bug and improve performance

[Paul Moore <paul@paul-moore.com>]

On Thu, Dec 6, 2018 at 4:36 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> On Wed, Dec 5, 2018 at 11:53 PM Paul Moore <paul@paul-moore.com> wrote:
> > On Fri, Nov 30, 2018 at 10:24 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> > > Before this patch, during a policy reload the sidtab would become frozen
> > > and trying to map a new context to SID would be unable to add a new
> > > entry to sidtab and fail with -ENOMEM.
> > >
> > > Such failures are usually propagated into userspace, which has no way of
> > > distignuishing them from actual allocation failures and thus doesn't
> > > handle them gracefully. Such situation can be triggered e.g. by the
> > > following reproducer:
> > >
> > >     while true; do load_policy; echo -n .; sleep 0.1; done &
> > >     for (( i = 0; i < 1024; i++ )); do
> > >         runcon -l s0:c$i echo -n x || break
> > >         # or:
> > >         # chcon -l s0:c$i <some_file> || break
> > >     done
> > >
> > > This patch overhauls the sidtab so it doesn't need to be frozen during
> > > policy reload, thus solving the above problem.
> > >
> > > The new SID table leverages the fact that SIDs are allocated
> > > sequentially and are never invalidated and stores them in linear buckets
> > > indexed by a tree structure. This brings several advantages:
> > >   1. Fast SID -> context lookup - this lookup can now be done in
> > >      logarithmic time complexity (usually in less than 4 array lookups)
> > >      and can still be done safely without locking.
> > >   2. No need to re-search the whole table on reverse lookup miss - after
> > >      acquiring the spinlock only the newly added entries need to be
> > >      searched, which means that reverse lookups that end up inserting a
> > >      new entry are now about twice as fast.
> > >   3. No need to freeze sidtab during policy reload - it is now possible
> > >      to handle insertion of new entries even during sidtab conversion.
> > >
> > > The tree structure of the new sidtab is able to grow automatically to up
> > > to about 2^31 entries (at which point it should not have more than about
> > > 4 tree levels). The old sidtab had a theoretical capacity of almost 2^32
> > > entries, but half of that is still more than enough since by that point
> > > the reverse table lookups would become unusably slow anyway...
> > >
> > > The number of entries per tree node is selected automatically so that
> > > each node fits into a single page, which should be the easiest size for
> > > kmalloc() to handle.
> > >
> > > Note that the cache for reverse lookup is preserved with equivalent
> > > logic. The only difference is that instead of storing pointers to the
> > > hash table nodes it stores just the indices of the cached entries.
> > >
> > > The new cache ensures that the indices are loaded/stored atomically, but
> > > it still has the drawback that concurrent cache updates may mess up the
> > > contents of the cache. Such situation however only reduces its
> > > effectivity, not the correctness of lookups.
> > >
> > > Tested by selinux-testsuite and thoroughly tortured by this simple
> > > stress test:
> > > ```
> > > function rand_cat() {
> > >         echo $(( $RANDOM % 1024 ))
> > > }
> > >
> > > function do_work() {
> > >         while true; do
> > >                 echo -n "system_u:system_r:kernel_t:s0:c$(rand_cat),c$(rand_cat)" \
> > >                         >/sys/fs/selinux/context 2>/dev/null || true
> > >         done
> > > }
> > >
> > > do_work >/dev/null &
> > > do_work >/dev/null &
> > > do_work >/dev/null &
> > >
> > > while load_policy; do echo -n .; sleep 0.1; done
> > >
> > > kill %1
> > > kill %2
> > > kill %3
> > > ```
> > >
> > > Reported-by: Orion Poplawski <orion@nwra.com>
> > > Reported-by: Li Kun <hw.likun@huawei.com>
> > > Link: https://github.com/SELinuxProject/selinux-kernel/issues/38
> > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> > > ---
> > >  security/selinux/ss/mls.c      |  23 +-
> > >  security/selinux/ss/mls.h      |   3 +-
> > >  security/selinux/ss/services.c | 120 +++----
> > >  security/selinux/ss/sidtab.c   | 556 ++++++++++++++++++++-------------
> > >  security/selinux/ss/sidtab.h   |  80 +++--
> > >  5 files changed, 459 insertions(+), 323 deletions(-)
> >
> > This also looks okay on quick inspection, and once again I know you
> > and Stephen have gone over this a lot, so I've merged it into
> > selinux/next.  However, I had to basically merge all of sidtab.c by
> > hand so please double check it still looks correct to you; I've gone
> > over it a few times and it looks like it matches, but it's easy to
> > miss something small.
>
> Thank you, I ran a diff with meld between the fixed and original
> versions and I can confirm there are only whitespace/comment
> differences.

Great, thanks for checking.

> Just one small nit though: I think you used a "bad" format fro the
> multiline comment in sidtab_convert(). Or at least Linus seems to hate
> it [1] :) OTOH, Documentation/process/coding-style.rst [2] still lists
> it as the preferred format for networking code... Not that it would
> bother me, but that e-mail has stuck in my mind and now I almost
> always notice the comment styles.

Part of this comes from my own personal preference, part comes from
starting working on Linux in the networking stack.  While I do care a
lot about line lengths, I don't care too much about multi-line comment
styles :)

-- 
paul moore
www.paul-moore.com