selinux: sidtab: reverse lookup hash table
Subsystems (2)
PATCH v8 1/1 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.
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 [email protected] and Paul McKenney to Cc for review of the RCU logic.
V8
-Removed the __rcu annotation added in V7. The annotation is intended to be applied to pointers to an object, however the objects referenced in the rcu hashtable are allocated and stored 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. -Fixed two more places where the context hash needs to be added in convert_context().
-Moved two more function calls from sidtab_context_to_sid() to context_struct_to_sid().
-Verified on Android and Fedora 31.
--- 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 | 98 ++++++++--- security/selinux/ss/services.h | 4 +- security/selinux/ss/sidtab.c | 263 ++++++++++++++-------------- security/selinux/ss/sidtab.h | 16 +- 9 files changed, 308 insertions(+), 167 deletions(-)
security/selinux/Kconfig +12 -0
@@ -85,3 +85,15 @@ config SECURITY_SELINUX_CHECKREQPROT_VALUE via /selinux/checkreqprot if authorized by policy. If you are unsure how to answer this question, answer 0. + +config SECURITY_SELINUX_SIDTAB_HASH_BITS + int "NSA SELinux sidtab hashtable size" + depends on SECURITY_SELINUX + 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.
security/selinux/include/security.h +1 -0
@@ -395,5 +395,6 @@ extern int selinux_nlmsg_lookup(u16 sclass, u16 nlmsg_type, u32 *perm);extern void avtab_cache_init (void );extern void ebitmap_cache_init (void );extern void hashtab_cache_init (void ); +extern int security_sidtab_hash_stats (struct selinux_state *state,char *page);#endif /* _SELINUX_SECURITY_H_ */
security/selinux/selinuxfs.c +65 -0
83 lines not on this page · raw message
security/selinux/ss/context.h +10 -1
@@ -31,6 +31,7 @@ struct context {u32 len;/* length of string in bytes */ struct mls_range range;char *str;/* string representation if context cannot be mapped. */ +u32 hash;/* a hash of the string representation */ };static inline void mls_context_init (struct context *c)
@@ -168,12 +169,13 @@ static inline int context_cpy(struct context *dst, struct context *src)kfree (dst->str);return rc; } + dst->hash = src->hash;return 0 ; }static inline void context_destroy (struct context *c) { - c->user = c->role = c->type =0 ; + c->user = c->role = c->type = c->hash =0 ;kfree (c->str); c->str =NULL ; c->len =0 ;
@@ -182,6 +184,8 @@ static inline void context_destroy(struct context *c)static inline int context_cmp (struct context *c1,struct context *c2) { +if (c1->hash && c2->hash && (c1->hash != c2->hash)) +return 0 ;if (c1->len && c2->len)return (c1->len == c2->len && !strcmp (c1->str, c2->str));if (c1->len || c2->len)
@@ -192,5 +196,10 @@ static inline int context_cmp(struct context *c1, struct context *c2) mls_context_cmp(c1, c2)); } +static inline unsigned int context_compute_hash (const char *s) +{ +return full_name_hash (NULL , s,strlen (s)); +} +#endif /* _SS_CONTEXT_H_ */
security/selinux/ss/policydb.c +5 -0
@@ -878,6 +878,11 @@ int policydb_load_isids(struct policydb *p, struct sidtab *s)sidtab_destroy (s); goto out; } + rc =context_add_hash (p, &c->context[0 ]); +if (rc) { +sidtab_destroy (s); + goto out; + } rc =sidtab_set_initial (s, c->sid[0 ], &c->context[0 ]);if (rc) {
security/selinux/ss/services.c +74 -24
243 lines not on this page · raw message
security/selinux/ss/services.h +3 -1
@@ -8,7 +8,7 @@#define _SS_SERVICES_H_#include "policydb.h" -#include "sidtab.h" +#include "context.h" /* Mapping for a single class */ struct selinux_mapping {
@@ -39,4 +39,6 @@ void services_compute_xperms_drivers(struct extended_perms *xperms,void services_compute_xperms_decision (struct extended_perms_decision *xpermd,struct avtab_node *node); +int context_add_hash (struct policydb *policydb,struct context *context); +#endif /* _SS_SERVICES_H_ */
security/selinux/ss/sidtab.c +127 -136
410 lines not on this page · raw message
security/selinux/ss/sidtab.h +11 -5
@@ -13,11 +13,14 @@#include <linux/spinlock_types.h> #include <linux/log2.h> +#include <linux/hashtable.h> #include "context.h" struct sidtab_entry_leaf { +u32 sid;struct context context; +struct hlist_node list; };struct sidtab_node_inner ;
@@ -57,7 +60,7 @@ struct sidtab_node_inner {struct sidtab_isid_entry {int set; -struct context context; +struct sidtab_entry_leaf leaf; };struct sidtab_convert_params {
@@ -66,7 +69,8 @@ struct sidtab_convert_params {struct sidtab *target; }; -#define SIDTAB_RCACHE_SIZE 3 +#define SIDTAB_HASH_BITS CONFIG_SECURITY_SELINUX_SIDTAB_HASH_BITS +#define SIDTAB_HASH_BUCKETS (1 << SIDTAB_HASH_BITS)struct sidtab {/*
@@ -83,11 +87,11 @@ struct sidtab {struct sidtab_convert_params *convert;spinlock_t lock; -/* reverse lookup cache - access atomically via {READ|WRITE}_ONCE() */ -u32 rcache[SIDTAB_RCACHE_SIZE ]; -/* index == SID - 1 (no entry for SECSID_NULL) */ struct sidtab_isid_entry isids[SECINITSID_NUM ]; + +/* Hash table for fast reverse context-to-sid lookups. */ +DECLARE_HASHTABLE (context_to_sid,SIDTAB_HASH_BITS ); };int sidtab_init (struct sidtab *s);
@@ -101,6 +105,8 @@ int sidtab_context_to_sid(struct sidtab *s, struct context *context, u32 *sid);void sidtab_destroy (struct sidtab *s); +int sidtab_hash_stats (struct sidtab *sidtab,char *page); +#endif /* _SS_SIDTAB_H_ */
Signature · 1 line
2.23.0
Quoted 108 lines · Jeff Vander Stoep
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.Sidtab entries are never modified or removed, so the context struct stored in the
sid_to_contexttree can also be used for thecontext_to_sidhashtable 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_pkgdirgoes 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 usessidtab_entry_leafobjects directly so these objects are shared between thesid_to_contextlookup tree and thecontext_to_sidhashtable. 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*_rcuvariants 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 wheresidtab_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_statsto match/sys/fs/selinux/avc/hash_stats.(quoted diff) +0
-3-Add __rcu annotation to rcu pointers. -Test with CONFIG_SPARSE_RCU_POINTER and CONFIG_PROVE_RCU. -Add [email protected] and Paul McKenney to Cc for review of theRCU logic.
V8
-Removed the__rcuannotation added in V7. The annotation is intended to be applied to pointers to an object, however the objects referenced in the rcu hashtable are allocated and stored in an array.
-Fixed bug where multiple SIDs were receiving the same hash due tosecurity_get_user_sids()reusing the same context struct without callingcontext_init()on it. This bug was discovered and root-caused by Stephen Smalley. -Fixed two more places where the context hash needs to be added inconvert_context().
-Moved two more function calls fromsidtab_context_to_sid()tocontext_struct_to_sid().
-Verified on Android and Fedora 31.Signed-off-by Jeff Vander Stoep <[email protected]>Reported-by Jovana Knezevic <[email protected]>--- 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 | 98 ++++++++--- security/selinux/ss/services.h | 4 +- security/selinux/ss/sidtab.c | 263 ++++++++++++++-------------- security/selinux/ss/sidtab.h | 16 +- 9 files changed, 308 insertions(+), 167 deletions(-)security/selinux/ss/services.c +0
-0
security/selinux/ss/services.c static int string_to_context_struct(struct policydb *pol, · line 1402
Quoted 8 lines
security/selinux/ss/services.c +2
-0@@ -1384,6 +1395,8 @@ static int string_to_context_struct(struct policydb *pol,int rc =0 ;context_init (ctx); +/* hash the string before it gets mutated */ + ctx->hash =context_compute_hash (scontext);/* Parse the security context. */
I still don't think this is correct/safe. The problem is that string_to_context_struct() can be called with a security context string in a non-canonical form, i.e. not the same string that would be produced by context_struct_to_string() on the resulting context. This can occur if a userspace program passes in a context that uses an alias name or that uses a non-compact form of the category set (e.g. c0,c1,c2 versus c0.c2). I think we can only set the hashes from the strings produced by context_struct_to_string() if we want to ensure consistency. If we leave the hash unset here, it will still be set later by context_struct_to_sid() or convert_context() so it should be fine.