Skip to contentSkip to conversation

selinux: sidtab: reverse lookup hash table

PATCH Superseded Jeff Vander Stoep 2 participants 2 messages Nov 5, 2019 SELinux security module

v3 of 9 Superseded Latest is v9 →

lore
Share & tools
lore
#0 lore raw

PATCH v3 1/1 selinux: sidtab: reverse lookup hash table

This replaces the reverse table lookup and reverse cache with a hashtable which improves cache-miss reverese-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 ee1a84fd 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:
- Stephen Smally 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:
-Move the hash_add() and count increment to after an smp_wmb() statement to enforce that prior objects have been written before becoming available for lookups.
-Add lock nesting notation.

Change-Id I9b498100c94f05222c54e24f53eba76468f360fd
---
 security/selinux/Kconfig            |  12 ++
 security/selinux/include/security.h |   1 +
 security/selinux/selinuxfs.c        |  64 +++++++
 security/selinux/ss/context.h       |  11 +-
 security/selinux/ss/policydb.c      |   5 +
 security/selinux/ss/services.c      |  87 +++++++---
 security/selinux/ss/services.h      |   4 +-
 security/selinux/ss/sidtab.c        | 249 +++++++++++++---------------
 security/selinux/ss/sidtab.h        |  16 +-
 9 files changed, 287 insertions(+), 162 deletions(-)
security/selinux/Kconfig +12 -0
index 8af7a690eb40..5494379e1ac7 100644
@@ -99,3 +99,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 sitab hashtable
+	  to 2^SECURITY_SELINUX_SIDTAB_HASH_BITS buckets. The number of hash
+	  collisions may be viewed at /selinux/ss/sidtab_hash_stats. If chain
+	  lengths are high (e.g. > 20) than selecting a higher value here will
+	  ensure that lookups times are fast and stable.
security/selinux/include/security.h +1 -0
index 5c83f56144d2..69833cea69a8 100644
@@ -365,5 +365,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 +64 -0

88 lines not on this page · raw message

security/selinux/ss/context.h +10 -1
index 212e3479a0d9..80db6c7627a1 100644
@@ -30,6 +30,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)
@@ -135,12 +136,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;
@@ -149,6 +151,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)
@@ -159,5 +163,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 8eb89d1cb09e..6f692a4f0253 100644
@@ -920,6 +920,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 -22

185 lines not on this page · raw message

security/selinux/ss/services.h +3 -1
index f27c68a482bb..7ba391e81b81 100644
@@ -7,7 +7,7 @@
 #define _SS_SERVICES_H_
 
 #include "policydb.h"
-#include "sidtab.h"
+#include "context.h"
 
 /* Mapping for a single class */
 struct selinux_mapping {
@@ -38,4 +38,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 +116 -133

392 lines not on this page · raw message

security/selinux/ss/sidtab.h +11 -5
index 285d68b824b9..f23640fe29b5 100644
@@ -12,12 +12,15 @@
 
 #include <linux/spinlock_types.h>
 #include <linux/log2.h>
+#include <linux/hashtable.h>
 
 #include "context.h"
 #include "flask.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
#1 lore raw
Quoted 2 lines · Jeff Vander Stoep

This replaces the reverse table lookup and reverse cache with a hashtable which improves cache-miss reverese-lookup times from

reverse

Quoted 6 lines

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.

Quoted 7 lines

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 ee1a84fd which removed the need to keep the current sidtab locked

Preferred style is "commit <12+ chars of sha1> ("title line")"; checkpatch.pl would have caught it except for the line break between commit and the hash I think. ala commit ee1a84fdfeed ("selinux: overhaul sidtab to fix bug and improve performance")
This ensures that the commit is unambiguously identified and the reader gets an idea of what it is without having to go look.

Quoted 8 lines

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:
- Stephen Smally on the selinux bug tracker.

Smalley (although I don't think I'm the original reporter, came from a mailing list email IIRC)

<snip>

Quoted 4 lines

V3:
-Move the hash_add() and count increment to after an smp_wmb() statement to enforce that prior objects have been written before becoming available for lookups.

smp_wmb() is SMP-conditional; wmb() is mandatory per memory-barriers.txt. I thought we needed wmb() for the old sidtab hash table update to avoid reordering even on the UP case. And I think memory-barriers.txt recommends pairing every write barrier with a corresponding read barrier for the reader code, which my code lacked (since memory-barriers.txt didn't exist at the time and I was just following the guidance from other docs), so presumably you want/need that.

Quoted 1 line

-Add lock nesting notation.

Is it truly needed locking nesting or can we get rid of it as suggested by Ondrej?

Patch wouldn't apply for me (on selinux/next); not sure why but some comments below.

Quoted 2 lines

Change-Id: I9b498100c94f05222c54e24f53eba76468f360fd

Don't include AOSP Change-Ids in upstream patches.

<snip>

Quoted 6 lines
security/selinux/Kconfig +0 -0
index 8af7a690eb40..5494379e1ac7 100644
@@ -99,3 +99,15 @@ config SECURITY_SELINUX_CHECKREQPROT_VALUE
  	  via /selinux/checkreqprot if authorized by policy.

security/selinux/Kconfig config SECURITY_SELINUX_CHECKREQPROT_VALUE · line 109

Quoted 10 lines
security/selinux/Kconfig +8 -0
 
  	  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 sitab hashtable

sidtab

security/selinux/Kconfig config SECURITY_SELINUX_CHECKREQPROT_VALUE · line 111

Quoted 2 lines
security/selinux/Kconfig +2 -0
+	  to 2^SECURITY_SELINUX_SIDTAB_HASH_BITS buckets. The number of hash
+	  collisions may be viewed at /selinux/ss/sidtab_hash_stats. If chain

Since Linux 3.0, selinuxfs is mounted on /sys/fs/selinux rather than /selinux so it would be /sys/fs/selinux/ss/sidtab_hash_stats. The other config option help texts are out of date but don't worry about those in this patch.

Quoted 2 lines
security/selinux/Kconfig +2 -0
+	  lengths are high (e.g. > 20) than selecting a higher value here will
+	  ensure that lookups times are fast and stable.

<snip>

Quoted 4 lines
security/selinux/selinuxfs.c +0 -0
index 7eff19c41bcb..4bb4ff027042 100644

<snip>

security/selinux/selinuxfs.c static int sel_make_avc_files(struct dentry *dir) · line 1605

Quoted 5 lines
security/selinux/selinuxfs.c +1 -0
@@ -1576,6 +1602,7 @@ static int sel_make_avc_files(struct dentry *dir)
  		{ "cache_threshold",
  		  &sel_avc_cache_threshold_ops, S_IRUGO|S_IWUSR },
  		{ "hash_stats", &sel_avc_hash_stats_ops, S_IRUGO },
+		{ "sidtab_hash_stats", &sel_sidtab_hash_stats_ops, S_IRUGO },

Still awaiting a verdict from Paul on whether we should conform to checkpatch.pl warning on symbolic modes or stick with them for consistency until such a time as we convert them en masse?

Quoted 16 lines
security/selinux/selinuxfs.c +9 -0
  #ifdef CONFIG_SECURITY_SELINUX_AVC_STATS
  		{ "cache_stats", &sel_avc_cache_stats_ops, S_IRUGO },
  #endif
@@ -1601,6 +1628,35 @@ static int sel_make_avc_files(struct dentry *dir)
  	return 0;
  }
 
+static int sel_make_ss_files(struct dentry *dir)
+{
+	struct super_block *sb = dir->d_sb;
+	struct selinux_fs_info *fsi = sb->s_fs_info;
+	int i;
+	static struct tree_descr files[] = {
+		{ "sidtab_hash_stats", &sel_sidtab_hash_stats_ops, S_IRUGO },
+	};
+

security/selinux/selinuxfs.c static int sel_make_avc_files(struct dentry *dir) · line 1649

Quoted 10 lines
security/selinux/selinuxfs.c +10 -0
+	for (i = 0; i < ARRAY_SIZE(files); i++) {
+		struct inode *inode;
+		struct dentry *dentry;
+
+		dentry = d_alloc_name(dir, files[i].name);
+		if (!dentry)
+			return -ENOMEM;
+
+		inode = sel_make_inode(dir->d_sb, S_IFREG|files[i].mode);
+		if (!inode)

dput(dentry); here (got fixed elsewhere recently IIRC).

Quoted 13 lines
security/selinux/selinuxfs.c +10 -0
+			return -ENOMEM;
+
+		inode->i_fop = files[i].ops;
+		inode->i_ino = ++fsi->last_ino;
+		d_add(dentry, inode);
+	}
+
+	return 0;
+}
+
  static ssize_t sel_read_initcon(struct file *file, char __user *buf,
  				size_t count, loff_t *ppos)
  {

<snip>

Quoted 4 lines
security/selinux/ss/services.c +0 -0
index 62e6a53f4ac9..9578fb3e994f 100644

<snip>

security/selinux/ss/services.c static int string_to_context_struct(struct policydb *pol, · line 1452

Quoted 8 lines
security/selinux/ss/services.c +1 -0
@@ -1433,6 +1446,7 @@ static int string_to_context_struct(struct policydb *pol,
  	rc = -EINVAL;
  	if (!policydb_context_isvalid(pol, ctx))
  		goto out;
+
  	rc = 0;
  out:
  	if (rc)

Avoid unrelated whitespace changes

Quoted 11 lines
security/selinux/ss/services.c +7 -0
@@ -1440,6 +1454,42 @@ static int string_to_context_struct(struct policydb *pol,
  	return rc;
  }
 
+int context_add_hash(struct policydb *policydb,
+		     struct context *context)
+{
+	int rc;
+	char *str;
+	int len;
+

security/selinux/ss/services.c static int string_to_context_struct(struct policydb *pol, · line 1473

Quoted 10 lines
security/selinux/ss/services.c +10 -0
+	if (context->str) {
+		context->hash = context_compute_hash(context->str);
+	} else {
+		rc = context_struct_to_string(policydb, context,
+					      &str, &len);
+		if (rc)
+			return rc;
+		context->hash = context_compute_hash(str);
+		kfree(str);
+	}

I'm guessing that KCSAN is going to complain about this and other existing cases in our code that rely on atomic load/store of naturally-aligned word-sized values. At some point we'll probably need to convert them all to using READ_ONCE/WRITE_ONCE or similar constructs when we do this outside of a spinlock or write lock (as here). Offhand, this may only be a problem for the cases where we are passing in a context structure that is part of the active policydb, as in security_port_sid() and other callers, since it is then a shared structure that could be visible to other threads. Same issue already exists however for the sid field there so not really new.

Quoted 3 lines
security/selinux/ss/services.c +3 -0
+	return 0;
+}
+

<snip>

Quoted 26 lines
security/selinux/ss/sidtab.c +3 -4
index 9d156d5156da..2267878da626 100644
@@ -16,26 +16,37 @@
  #include "security.h"
  #include "sidtab.h"
 
+#define index_to_sid(index) (index + SECINITSID_NUM + 1)
+#define sid_to_index(sid) (sid - (SECINITSID_NUM + 1))
+
  int sidtab_init(struct sidtab *s)
  {
  	u32 i;
 
  	memset(s->roots, 0, sizeof(s->roots));
 
-	/* max count is SIDTAB_MAX so valid index is always < SIDTAB_MAX */
-	for (i = 0; i < SIDTAB_RCACHE_SIZE; i++)
-		s->rcache[i] = SIDTAB_MAX;
-
  	for (i = 0; i < SECINITSID_NUM; i++)
  		s->isids[i].set = 0;
 
  	s->count = 0;
  	s->convert = NULL;

security/selinux/ss/sidtab.c line 42

Quoted 10 lines
security/selinux/ss/sidtab.c +5 -0
+	hash_init(s->context_to_sid);
 
  	spin_lock_init(&s->lock);
  	return 0;
  }
 
+static u32 context_to_sid(struct sidtab *s, struct context *context)
+{
+	struct sidtab_entry_leaf *entry;
+

I think we need a read barrier or ACQUIRE operation of some kind here or in the callers to ensure that the hash is in a good state.

Quoted 10 lines
security/selinux/ss/sidtab.c +7 -0
+	hash_for_each_possible(s->context_to_sid, entry, list, context->hash) {
+		if (context_cmp(&entry->context, context))
+			return entry->sid;
+	}
+	return 0;
+}
+
  int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context)
  {
  	struct sidtab_isid_entry *entry;

<snip>

Quoted 15 lines
security/selinux/ss/sidtab.c +4 -3
@@ -304,29 +274,35 @@ static int sidtab_reverse_lookup(struct sidtab *s, struct context *context,
  		rc = -ENOMEM;
  		dst_convert = sidtab_do_lookup(convert->target, count, 1);
  		if (!dst_convert) {
-			context_destroy(dst);
+			context_destroy(&dst->context);
  			goto out_unlock;
  		}
 
-		rc = convert->func(context, dst_convert, convert->args);
+		rc = convert->func(context, &dst_convert->context,
+				convert->args);
  		if (rc) {
-			context_destroy(dst);
+			context_destroy(&dst->context);

security/selinux/ss/sidtab.c static int sidtab_reverse_lookup(struct sidtab *s, struct context *context, · line 294

Quoted 10 lines
security/selinux/ss/sidtab.c +5 -0
  			goto out_unlock;
  		}
+		dst_convert->sid = index_to_sid(count);
 
  		/* at this point we know the insert won't fail */
+		spin_lock_irqsave(&convert->target->lock, flags);
  		convert->target->count = count + 1;
+		hash_add(convert->target->context_to_sid,
+			 &dst_convert->list, dst_convert->context.hash);
+		spin_unlock_irqrestore(&convert->target->lock, flags);

As Ondrej asked, do we need to take this lock?

Quoted 4 lines
security/selinux/ss/sidtab.c +0 -0
  	}
 
  	if (context->len)
  		pr_info("SELinux:  Context %s is not valid (left unmapped).\n",

security/selinux/ss/sidtab.c static int sidtab_reverse_lookup(struct sidtab *s, struct context *context, · line 305

Quoted 10 lines
security/selinux/ss/sidtab.c +3 -3
  			context->str);
 
-	sidtab_rcache_push(s, count);
-	*index = count;
+	*sid = index_to_sid(count);
 
-	/* write entries before writing new count */
+	/* Write entries before updating count and inserting into hashtable. */
  	smp_store_release(&s->count, count + 1);
+	hash_add(s->context_to_sid, &dst->list, dst->context.hash);

I think we need a separate acquire/release or write/read barrier pairing for the reverse hash table that is independent of the one for the forward table.

Quoted 3 lines
security/selinux/ss/sidtab.c +0 -0
  	rc = 0;
  out_unlock: