path: root/security/selinux/Kconfig
diff options
authorJeff Vander Stoep <>2019-11-22 10:33:06 +0100
committerPaul Moore <>2019-12-09 16:14:51 -0500
commit66f8e2f03c02e812002f8e9e465681cc62edda5b (patch)
tree44851eca8f9b556373e095245eb60491eab48d73 /security/selinux/Kconfig
parente42617b825f8073569da76dc4510bfa019b1c35a (diff)
selinux: sidtab reverse lookup hash table
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 - 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. Signed-off-by: Jeff Vander Stoep <> Reported-by: Stephen Smalley <> Reported-by: Jovana Knezevic <> Reviewed-by: Stephen Smalley <> Tested-by: Stephen Smalley <> [PM: subj tweak, removed changelog from patch description] Signed-off-by: Paul Moore <>
Diffstat (limited to 'security/selinux/Kconfig')
1 files changed, 12 insertions, 0 deletions
diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
index 5711689deb6a..c9e576c430c2 100644
--- a/security/selinux/Kconfig
+++ b/security/selinux/Kconfig
via /selinux/checkreqprot if authorized by policy.
If you are unsure how to answer this question, answer 0.
+ int "NSA SELinux sidtab hashtable size"
+ range 8 13
+ default 9
+ help
+ This option sets the number of buckets used in the sidtab hashtable
+ to 2^SECURITY_SELINUX_SIDTAB_HASH_BITS buckets. The number of hash
+ collisions may be viewed at /sys/fs/selinux/ss/sidtab_hash_stats. If
+ chain lengths are high (e.g. > 20) then selecting a higher value here
+ will ensure that lookups times are short and stable.