From: Paul Moore <paul@paul-moore.com>
To: Jeff Vander Stoep <jeffv@google.com>
Cc: selinux@vger.kernel.org, omosnace@redhat.com,
Stephen Smalley <sds@tycho.nsa.gov>,
will@kernel.org, paulmck@kernel.org, rcu@vger.kernel.org,
Jovana Knezevic <jovanak@google.com>
Subject: Re: [PATCH v9] selinux: sidtab: reverse lookup hash table
Date: Mon, 2 Dec 2019 19:32:45 -0500 [thread overview]
Message-ID: <CAHC9VhQ-piMePyfOeLsrAtgSCG5iWjk9xFbjOvURe3WLD-z89g@mail.gmail.com> (raw)
In-Reply-To: <20191122093306.17335-1-jeffv@google.com>
On Fri, Nov 22, 2019 at 4:33 AM Jeff Vander Stoep <jeffv@google.com> 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.
>
> V8
> -Removed the __rcu annotation used in V7. The annotation is
> intended to be applied to pointers to an object, however the
> objects referenced in the rcu hashtable are allocated in an
> array.
> -Fixed bug where multiple SIDs were receiving the same hash
> due to security_get_user_sids() reusing the same context
> struct without calling context_init() on it. This bug was
> discovered and root-caused by Stephen Smalley.
>
> V9
> -Do not compute the hash in string_to_context_struct
> because this string representation is non-canonical.
>
> 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 | 96 +++++++---
> security/selinux/ss/services.h | 4 +-
> security/selinux/ss/sidtab.c | 263 ++++++++++++++--------------
> security/selinux/ss/sidtab.h | 16 +-
> 9 files changed, 306 insertions(+), 167 deletions(-)
Thanks Jeff, as well as everyone else who contributed reviews and feedback.
I've pulled this into a working branch and I'll be merging it with the
other sidtab patches before posting it to a "next-queue" branch for
review later this week. When done, I'll send a note to the list, as
well as the relevant patch authors; your help in reviewing the merge
would be greatly appreciated.
--
paul moore
www.paul-moore.com
next prev parent reply other threads:[~2019-12-03 0:33 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-11-22 9:33 [PATCH v9] selinux: sidtab: reverse lookup hash table Jeff Vander Stoep
2019-11-22 14:21 ` Stephen Smalley
2019-12-03 0:32 ` Paul Moore [this message]
2019-12-04 9:11 ` Ondrej Mosnacek
2019-12-04 15:48 ` Stephen Smalley
2019-12-04 23:52 ` Paul Moore
2019-12-05 11:48 ` Ondrej Mosnacek
2019-12-05 14:08 ` Paul Moore
2019-12-05 17:41 ` Paul Moore
2019-12-05 18:10 ` Stephen Smalley
2019-12-05 18:14 ` Paul Moore
2019-12-06 0:50 ` Paul Moore
2019-12-06 13:45 ` Stephen Smalley
2019-12-06 15:08 ` Paul Moore
2019-12-09 21:17 ` Paul Moore
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAHC9VhQ-piMePyfOeLsrAtgSCG5iWjk9xFbjOvURe3WLD-z89g@mail.gmail.com \
--to=paul@paul-moore.com \
--cc=jeffv@google.com \
--cc=jovanak@google.com \
--cc=omosnace@redhat.com \
--cc=paulmck@kernel.org \
--cc=rcu@vger.kernel.org \
--cc=sds@tycho.nsa.gov \
--cc=selinux@vger.kernel.org \
--cc=will@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).