Skip to contentSkip to conversation

selinux: sidtab: reverse lookup hash table

PATCH In review Jeff Vander Stoep 2 participants 2 messages Nov 7, 2019 – Nov 15, 2019 SELinux security module

lore
Share & tools
lore
#0 lore raw

PATCH 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.

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 use of rcu_head/kfree_rcu(), they're unnecessary because hashtable objects are never removed when read/add operations are occurring.
-Remove nested locking. Use lock of active sidtab to gate access to the new sidtab.

---
 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      |  83 +++++++--
 security/selinux/ss/services.h      |   4 +-
 security/selinux/ss/sidtab.c        | 264 ++++++++++++++--------------
 security/selinux/ss/sidtab.h        |  16 +-
 9 files changed, 300 insertions(+), 161 deletions(-)
security/selinux/Kconfig +12 -0
index 5711689deb6a..c9e576c430c2 100644
@@ -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
index ae840634e3c7..8c0dbbd076c6 100644
@@ -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
index 513e67f48878..3ba044fe02ed 100644
@@ -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
index e20624a68f5d..e369b0092cdf 100644
@@ -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 +65 -18

175 lines not on this page · raw message

security/selinux/ss/services.h +3 -1
index 9a36de860368..fc40640a9725 100644
@@ -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 +128 -136

411 lines not on this page · raw message

security/selinux/ss/sidtab.h +11 -5
index 1f4763141aa1..e2809401c417 100644
@@ -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.24.0.rc1.363.gb1bccd3e3d-goog
maintainer
#1 lore raw
Quoted 73 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.

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 use of rcu_head/kfree_rcu(), they're unnecessary because hashtable objects are never removed when read/add operations are occurring.
-Remove nested locking. Use lock of active sidtab to gate access to the new sidtab.

---
 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      |  83 +++++++--
 security/selinux/ss/services.h      |   4 +-
 security/selinux/ss/sidtab.c        | 264 ++++++++++++++--------------
 security/selinux/ss/sidtab.h        |  16 +-
 9 files changed, 300 insertions(+), 161 deletions(-)

...

security/selinux/ss/context.h static inline int context_cmp(struct context *c1, struct context *c2) · line 201

Quoted 11 lines
security/selinux/ss/context.h +3 -0
index 513e67f48878..3ba044fe02ed 100644
@@ -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));

While we can obviously use any hash function we want here, is there any value in sticking with an algorithm similar to symhash()? Or alternatively, and beyond the scope of this patch, it is worth converting symhash() to use full_name_hash()? Or should we just leave everything well enough alone ;)

Quoted 52 lines
security/selinux/ss/sidtab.c +36 -1
index 7d49994e8d5f..e705a3bc4d0d 100644
@@ -47,14 +64,61 @@ int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context)
 
        entry = &s->isids[sid - 1];
 
-       rc = context_cpy(&entry->context, context);
+       rc = context_cpy(&entry->leaf.context, context);
        if (rc)
                return rc;
 
        entry->set = 1;
+
+       /*
+        * Multiple initial sids may map to the same context. Check that this
+        * context is not already represented in the context_to_sid hashtable
+        * to avoid duplicate entries and long linked lists upon hash
+        * collision.
+        */
+       if (!context_to_sid(s, context)) {
+               entry->leaf.sid = sid;
+               hash_add(s->context_to_sid, &entry->leaf.list, context->hash);
+       }
+
        return 0;
 }
 
+int sidtab_hash_stats(struct sidtab *sidtab, char *page)
+{
+       int i;
+       int chain_len = 0;
+       int slots_used = 0;
+       int entries = 0;
+       int max_chain_len = 0;
+       int cur_bucket = 0;
+       struct sidtab_entry_leaf *entry;
+
+       rcu_read_lock();
+       hash_for_each_rcu(sidtab->context_to_sid, i, entry, list) {
+               entries++;
+               if (i == cur_bucket) {
+                       chain_len++;
+                       if (chain_len == 1)
+                               slots_used++;
+               } else {
+                       cur_bucket = i;
+                       if (chain_len > max_chain_len)
+                               max_chain_len = chain_len;
+                       chain_len = 0;
+               }

security/selinux/ss/sidtab.c int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context) · line 119

Quoted 10 lines
security/selinux/ss/sidtab.c +10 -0
+       }
+       rcu_read_unlock();
+
+       if (chain_len > max_chain_len)
+               max_chain_len = chain_len;
+
+       return scnprintf(page, PAGE_SIZE, "context_to_sid:  %d entries and "
+                        "%d/%d buckets used, longest chain length %d\n",
+                        entries, slots_used, SIDTAB_HASH_BUCKETS,
+                        max_chain_len);

I wonder if there is value in sticking to the format currently in use with /sys/fs/selinux/avc/hash_stats?

Signature · 2 lines
paul moore
www.paul-moore.com