Skip to contentSkip to conversation

selinux: sidtab: reverse lookup hash table

PATCH Superseded Jeff Vander Stoep 5 participants 11 messages Nov 7, 2019 – Nov 14, 2019 SELinux security module

v5 of 9 Superseded Latest is v9 →

lore
Share & tools
lore
#0 lore raw

PATCH v5 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:
-Moved to *_rcu variants of the various hashtable functions as suggested by Ondrej Mosnacek and Will Deacon. -Naming/spelling fixups.

---
 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        |  17 +-
 9 files changed, 302 insertions(+), 160 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 +129 -135

412 lines not on this page · raw message

security/selinux/ss/sidtab.h +12 -5
index 1f4763141aa1..f1f505df97ba 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;
@@ -49,6 +52,7 @@ union sidtab_entry_inner {
 
 struct sidtab_node_leaf {
 	struct sidtab_entry_leaf entries[SIDTAB_LEAF_ENTRIES];
+	struct rcu_head rcu;
 };
 
 struct sidtab_node_inner {
@@ -57,7 +61,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 +70,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 +88,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 +106,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

Note this should be v4, not v5.

Paul, please let me know if you'd prefer my change applied on top of Ondrej's
"selinux: cache the SID -> context string translation" patch.

maintainer
#2 lore raw
Quoted 4 lines · Jeffrey Vander Stoep

Note this should be v4, not v5.

Paul, please let me know if you'd prefer my change applied on top of Ondrej's
"selinux: cache the SID -> context string translation" patch.

Sorry for the delay, travel had me a bit backlogged. Regardless, don't worry about rebasing on other in-flight patches; unless it gets *really* messy I'll take care of that when I merge everything.

Signature · 2 lines
paul moore
www.paul-moore.com
#3 lore raw
In reply to Jeff Vander Stoep
Quoted 44 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.

Quoted 7 lines

V3:
-Add lock nesting notation.

V4:
-Moved to *_rcu variants of the various hashtable functions as suggested by Ondrej Mosnacek and Will Deacon. -Naming/spelling fixups.

This still triggers a splat for me in running Ondrej's reproducer (also ran selinux-testsuite first, not sure if that mattered):

SELinux: Converting 3784 SID table entries...
kernel: ------------[ cut here ]------------
syscall 1 left IRQs disabled

WARNING: CPU: 1 PID: 8313 at arch/x86/entry/common.c:261 syscall_return_slowpathModules linked in: crypto_user scsi_transport_iscsi xt_multiport bluetooth ecdh_kernel:  crc32_pclmul snd_hda_codec snd_hwdep snd_hda_core ghash_clmulni_intel sCPU: 1 PID: 8313 Comm: runcon Not tainted 5.4.0-rc1+ #57
Hardware name: Dell Inc. OptiPlex 7050/0NW6H5, BIOS 1.8.3 03/23/2018
RIP: 0010:syscall_return_slowpath+0x1e1/0x4a0
Code: ff ff e9 60 ff ff ff e8 2d ad 05 00 e9 2a ff ff ff 48 8d 7d 78 e8 cf cf 50RSP: 0018:ffff8885a6adff28 EFLAGS: 00010082
RAX: 0000000000000000 RBX: 0000000000000080 RCX: 0000000000000000
RDX: 0000000000000003 RSI: 0000000000000000 RDI: ffffed10b4d5bfd7
RBP: ffff8885a6adff58 R08: ffffffffaa219f90 R09: fffffbfff5883615
R10: fffffbfff5883614 R11: ffffffffac41b0a3 R12: 0000000000000000
R13: 0000000000000000 R14: 0000000000000000 R15: 0000000000000000
FS:  00007f3e32c67080(0000) GS:ffff888822a40000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007f3e32f145d0 CR3: 00000005a7476005 CR4: 00000000003606e0
DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
Call Trace:
kernel:  entry_SYSCALL_64_after_hwframe+0x49/0xbe
RIP: 0033:0x7f3e32e11467
Code: 64 89 02 48 c7 c0 ff ff ff ff eb bb 0f 1f 80 00 00 00 00 f3 0f 1e fa 64 8bRSP: 002b:00007ffec6482bc8 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
RAX: 000000000000002f RBX: 00007ffec6483d88 RCX: 00007f3e32e11467
RDX: 000000000000002f RSI: 000055b75e5a5600 RDI: 0000000000000003
RBP: 000055b75e5a5600 R08: 00000000ffffffff R09: 00007ffec6482a60
R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000003
R13: 00007ffec6483c4c R14: 0000000000000000 R15: 0000000000000000
irq event stamp: 7292
hardirqs last  enabled at (7291): [<ffffffffab26d9bb>] _raw_write_unlock_irqresthardirqs last disabled at (7292): [<ffffffffab26db61>] _raw_spin_lock_irqsave+0xsoftirqs last  enabled at (7036): [<ffffffffab600494>] __do_softirq+0x494/0x665
softirqs last disabled at (7025): [<ffffffffaa168b8f>] irq_exit+0x13f/0x160

kernel: ---[ end trace 1557497a64e0b001 ]---
kernel: ------------[ cut here ]------------

Some comments below. Recommend running it by the RCU wizards e.g. Paul McKenney too given the subtleties of getting RCU right.

<snip>

Quoted 5 lines
security/selinux/ss/sidtab.c +0 -0
index 7d49994e8d5f..c052e620246c 100644
@@ -17,26 +17,42 @@

<snip>

security/selinux/ss/sidtab.c line 49

Quoted 10 lines
security/selinux/ss/sidtab.c +10 -0
+static u32 context_to_sid(struct sidtab *s, struct context *context)
+{
+	struct sidtab_entry_leaf *entry;
+
+	rcu_read_lock();
+	hash_for_each_possible_rcu(s->context_to_sid, entry, list,
+				   context->hash) {
+		if (context_cmp(&entry->context, context)) {
+			rcu_read_unlock();
+			return entry->sid;

This looks unsafe to me; I would have assumed you need to at least save entry->sid to a temporary before rcu_read_unlock()?

Quoted 17 lines
security/selinux/ss/sidtab.c +4 -3
@@ -305,29 +284,36 @@ 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);
  			goto out_unlock;
  		}

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 +7 -1
+		dst_convert->sid = index_to_sid(count);
+		convert->target->count = count + 1;
 
  		/* at this point we know the insert won't fail */
-		convert->target->count = count + 1;
+		spin_lock_irqsave_nested(&convert->target->lock, flags,
+				SINGLE_DEPTH_NESTING);
+		hash_add_rcu(convert->target->context_to_sid,
+				&dst_convert->list, dst_convert->context.hash);
+		spin_unlock_irqrestore(&convert->target->lock, flags);

Still having a hard time understanding why we need to lock the target. The target here is always the newsidtab allocated by security_load_policy(), not yet exposed to any other threads in the system?

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 316

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. */
  	smp_store_release(&s->count, count + 1);
+	hash_add_rcu(s->context_to_sid, &dst->list, dst->context.hash);

Exactly what guarantee do we think we are getting from placing the hash_add_rcu() after the smp_store_release() on s->count, and is that guarantee well-founded?

security/selinux/ss/sidtab.c static void sidtab_destroy_tree(union sidtab_entry_inner entry, u32 level) · line 466

Quoted 6 lines
security/selinux/ss/sidtab.c +1 -1
@@ -474,7 +463,7 @@ static void sidtab_destroy_tree(union sidtab_entry_inner entry, u32 level)
 
  		for (i = 0; i < SIDTAB_LEAF_ENTRIES; i++)
  			context_destroy(&node->entries[i].context);
-		kfree(node);
+		kfree_rcu(node, rcu);

Is it safe to do this without having deleted it from the hash and without having taken the spinlock?

Quoted 10 lines
security/selinux/ss/sidtab.c +0 -0
  	}
  }
 
security/selinux/ss/sidtab.h +0 -0
index 1f4763141aa1..f1f505df97ba 100644
@@ -83,11 +88,11 @@ struct sidtab {
  	struct sidtab_convert_params *convert;

security/selinux/ss/sidtab.h struct sidtab { · line 95

Quoted 10 lines
security/selinux/ss/sidtab.h +3 -3
  	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);

Should this and/or any of the associated RCU-protected structures be marked with __rcu for sparse checking?

Quoted 3 lines
security/selinux/ss/sidtab.h +0 -0
  };
 
  int sidtab_init(struct sidtab *s);
#4 lore raw
Quoted 143 lines · Stephen Smalley
Quoted 44 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.

Quoted 7 lines

V3:
-Add lock nesting notation.

V4:
-Moved to *_rcu variants of the various hashtable functions as suggested by Ondrej Mosnacek and Will Deacon. -Naming/spelling fixups.

This still triggers a splat for me in running Ondrej's reproducer (also ran selinux-testsuite first, not sure if that mattered):

SELinux: Converting 3784 SID table entries...
kernel: ------------[ cut here ]------------
syscall 1 left IRQs disabled

WARNING: CPU: 1 PID: 8313 at arch/x86/entry/common.c:261

syscall_return_slowpathModules linked in: crypto_user scsi_transport_iscsi xt_multiport bluetooth ecdh_kernel: crc32_pclmul snd_hda_codec snd_hwdep snd_hda_core ghash_clmulni_intel sCPU: 1 PID:
8313 Comm: runcon Not tainted 5.4.0-rc1+ #57

Hardware name: Dell Inc. OptiPlex 7050/0NW6H5, BIOS 1.8.3 03/23/2018
RIP: 0010:syscall_return_slowpath+0x1e1/0x4a0
Code: ff ff e9 60 ff ff ff e8 2d ad 05 00 e9 2a ff ff ff 48 8d 7d 78 e8
cf cf 50RSP: 0018:ffff8885a6adff28 EFLAGS: 00010082
RAX: 0000000000000000 RBX: 0000000000000080 RCX: 0000000000000000
RDX: 0000000000000003 RSI: 0000000000000000 RDI: ffffed10b4d5bfd7
RBP: ffff8885a6adff58 R08: ffffffffaa219f90 R09: fffffbfff5883615
R10: fffffbfff5883614 R11: ffffffffac41b0a3 R12: 0000000000000000
R13: 0000000000000000 R14: 0000000000000000 R15: 0000000000000000
FS:  00007f3e32c67080(0000) GS:ffff888822a40000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007f3e32f145d0 CR3: 00000005a7476005 CR4: 00000000003606e0
DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
Call Trace:
kernel:  entry_SYSCALL_64_after_hwframe+0x49/0xbe
RIP: 0033:0x7f3e32e11467
Code: 64 89 02 48 c7 c0 ff ff ff ff eb bb 0f 1f 80 00 00 00 00 f3 0f 1e

fa 64 8bRSP: 002b:00007ffec6482bc8 EFLAGS: 00000246 ORIG_RAX:
0000000000000001
RAX: 000000000000002f RBX: 00007ffec6483d88 RCX: 00007f3e32e11467
RDX: 000000000000002f RSI: 000055b75e5a5600 RDI: 0000000000000003
RBP: 000055b75e5a5600 R08: 00000000ffffffff R09: 00007ffec6482a60
R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000003
R13: 00007ffec6483c4c R14: 0000000000000000 R15: 0000000000000000

irq event stamp: 7292
hardirqs last  enabled at (7291): [<ffffffffab26d9bb>]
_raw_write_unlock_irqresthardirqs last disabled at (7292):
[<ffffffffab26db61>] _raw_spin_lock_irqsave+0xsoftirqs last  enabled at
(7036): [<ffffffffab600494>] __do_softirq+0x494/0x665
softirqs last disabled at (7025): [<ffffffffaa168b8f>] irq_exit+0x13f/0x160

kernel: ---[ end trace 1557497a64e0b001 ]---
kernel: ------------[ cut here ]------------

Some comments below. Recommend running it by the RCU wizards e.g. Paul McKenney too given the subtleties of getting RCU right.

<snip>

Quoted 5 lines
security/selinux/ss/sidtab.c +0 -0
index 7d49994e8d5f..c052e620246c 100644
@@ -17,26 +17,42 @@

<snip>

security/selinux/ss/sidtab.c line 49

Quoted 10 lines
security/selinux/ss/sidtab.c +10 -0
+static u32 context_to_sid(struct sidtab *s, struct context *context)
+{
+     struct sidtab_entry_leaf *entry;
+
+     rcu_read_lock();
+     hash_for_each_possible_rcu(s->context_to_sid, entry, list,
+                                context->hash) {
+             if (context_cmp(&entry->context, context)) {
+                     rcu_read_unlock();
+                     return entry->sid;

This looks unsafe to me; I would have assumed you need to at least save entry->sid to a temporary before rcu_read_unlock()?

Quoted 20 lines
security/selinux/ss/sidtab.c +6 -3
@@ -305,29 +284,36 @@ 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);
                      goto out_unlock;
              }
+             dst_convert->sid = index_to_sid(count);
+             convert->target->count = count + 1;
 
Quoted 11 lines

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

Quoted 7 lines
security/selinux/ss/sidtab.c +5 -1
              /* at this point we know the insert won't fail */
-             convert->target->count = count + 1;
+             spin_lock_irqsave_nested(&convert->target->lock, flags,
+                             SINGLE_DEPTH_NESTING);
+             hash_add_rcu(convert->target->context_to_sid,
+                             &dst_convert->list, dst_convert->context.hash);
+             spin_unlock_irqrestore(&convert->target->lock, flags);

Still having a hard time understanding why we need to lock the target. The target here is always the newsidtab allocated by security_load_policy(), not yet exposed to any other threads in the system?

I believe this is to avoid a race with the hash_add() in sidtab_convert_hashtable(), which locks only the target table. However, I don't like the fact that we need to mess with inconsistent lock nesting here... I think it would be better to just lock the master's spinlock in sidtab_convert_hashtable() - it will then block more when entries would be added to sidtab, but that shouldn't be a big concern in practice.

Signature · 3 lines
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
#5 lore raw
Quoted 32 lines
Quoted 20 lines
Quoted 20 lines
security/selinux/ss/sidtab.c +6 -3
@@ -305,29 +284,36 @@ 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);
                      goto out_unlock;
              }
+             dst_convert->sid = index_to_sid(count);
+             convert->target->count = count + 1;
 
Quoted 11 lines

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

Quoted 7 lines
security/selinux/ss/sidtab.c +5 -1
              /* at this point we know the insert won't fail */
-             convert->target->count = count + 1;
+             spin_lock_irqsave_nested(&convert->target->lock, flags,
+                             SINGLE_DEPTH_NESTING);
+             hash_add_rcu(convert->target->context_to_sid,
+                             &dst_convert->list, dst_convert->context.hash);
+             spin_unlock_irqrestore(&convert->target->lock, flags);

Still having a hard time understanding why we need to lock the target. The target here is always the newsidtab allocated by security_load_policy(), not yet exposed to any other threads in the system?

Quoted 8 lines

I believe this is to avoid a race with the hash_add() in sidtab_convert_hashtable(), which locks only the target table. However, I don't like the fact that we need to mess with inconsistent lock nesting here... I think it would be better to just lock the master's spinlock in sidtab_convert_hashtable() - it will then block more when entries would be added to sidtab, but that shouldn't be a big concern in practice.

I'll try that. Thanks.

#6 lore raw
In reply to Stephen Smalley
Quoted 49 lines · Stephen Smalley
Quoted 47 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.

Quoted 7 lines
Quoted 4 lines

V4:
-Moved to *_rcu variants of the various hashtable functions as suggested by Ondrej Mosnacek and Will Deacon. -Naming/spelling fixups.

This still triggers a splat for me in running Ondrej's reproducer (also ran selinux-testsuite first, not sure if that mattered):

Sorry, I am unable to reproduce this using Ondrej's reproducer. :(

I am sharing the same "flags" variable between the nested locks. That seems like a bug. Anyway, based on Ondrej's reply I'll go with a different approach and keep
the current sidtab locked.

Quoted 40 lines

SELinux: Converting 3784 SID table entries...
kernel: ------------[ cut here ]------------
syscall 1 left IRQs disabled

WARNING: CPU: 1 PID: 8313 at arch/x86/entry/common.c:261

syscall_return_slowpathModules linked in: crypto_user scsi_transport_iscsi xt_multiport bluetooth ecdh_kernel: crc32_pclmul snd_hda_codec snd_hwdep snd_hda_core ghash_clmulni_intel sCPU: 1 PID:
8313 Comm: runcon Not tainted 5.4.0-rc1+ #57

Hardware name: Dell Inc. OptiPlex 7050/0NW6H5, BIOS 1.8.3 03/23/2018
RIP: 0010:syscall_return_slowpath+0x1e1/0x4a0
Code: ff ff e9 60 ff ff ff e8 2d ad 05 00 e9 2a ff ff ff 48 8d 7d 78 e8
cf cf 50RSP: 0018:ffff8885a6adff28 EFLAGS: 00010082
RAX: 0000000000000000 RBX: 0000000000000080 RCX: 0000000000000000
RDX: 0000000000000003 RSI: 0000000000000000 RDI: ffffed10b4d5bfd7
RBP: ffff8885a6adff58 R08: ffffffffaa219f90 R09: fffffbfff5883615
R10: fffffbfff5883614 R11: ffffffffac41b0a3 R12: 0000000000000000
R13: 0000000000000000 R14: 0000000000000000 R15: 0000000000000000
FS:  00007f3e32c67080(0000) GS:ffff888822a40000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007f3e32f145d0 CR3: 00000005a7476005 CR4: 00000000003606e0
DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
Call Trace:
kernel:  entry_SYSCALL_64_after_hwframe+0x49/0xbe
RIP: 0033:0x7f3e32e11467
Code: 64 89 02 48 c7 c0 ff ff ff ff eb bb 0f 1f 80 00 00 00 00 f3 0f 1e

fa 64 8bRSP: 002b:00007ffec6482bc8 EFLAGS: 00000246 ORIG_RAX:
0000000000000001
RAX: 000000000000002f RBX: 00007ffec6483d88 RCX: 00007f3e32e11467
RDX: 000000000000002f RSI: 000055b75e5a5600 RDI: 0000000000000003
RBP: 000055b75e5a5600 R08: 00000000ffffffff R09: 00007ffec6482a60
R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000003
R13: 00007ffec6483c4c R14: 0000000000000000 R15: 0000000000000000

irq event stamp: 7292
hardirqs last  enabled at (7291): [<ffffffffab26d9bb>]
_raw_write_unlock_irqresthardirqs last disabled at (7292):
[<ffffffffab26db61>] _raw_spin_lock_irqsave+0xsoftirqs last  enabled at
(7036): [<ffffffffab600494>] __do_softirq+0x494/0x665
softirqs last disabled at (7025): [<ffffffffaa168b8f>] irq_exit+0x13f/0x160
Quoted 5 lines

kernel: ---[ end trace 1557497a64e0b001 ]---
kernel: ------------[ cut here ]------------

Some comments below. Recommend running it by the RCU wizards e.g. Paul McKenney too given the subtleties of getting RCU right.

Sure, I've also cc'ed Will Deacon.

Quoted 9 lines

<snip>

Quoted 5 lines
security/selinux/ss/sidtab.c +0 -0
index 7d49994e8d5f..c052e620246c 100644
@@ -17,26 +17,42 @@

<snip>

Quoted 13 lines

security/selinux/ss/sidtab.c line 49

Quoted 10 lines
security/selinux/ss/sidtab.c +10 -0
+static u32 context_to_sid(struct sidtab *s, struct context *context)
+{
+     struct sidtab_entry_leaf *entry;
+
+     rcu_read_lock();
+     hash_for_each_possible_rcu(s->context_to_sid, entry, list,
+                                context->hash) {
+             if (context_cmp(&entry->context, context)) {
+                     rcu_read_unlock();
+                     return entry->sid;

This looks unsafe to me; I would have assumed you need to at least save entry->sid to a temporary before rcu_read_unlock()?

Good point.

Quoted 21 lines
Quoted 21 lines
security/selinux/ss/sidtab.c +6 -3
@@ -305,29 +284,36 @@ 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);
                      goto out_unlock;
              }
+             dst_convert->sid = index_to_sid(count);
+             convert->target->count = count + 1;
 
Quoted 11 lines

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

Quoted 7 lines
security/selinux/ss/sidtab.c +5 -1
              /* at this point we know the insert won't fail */
-             convert->target->count = count + 1;
+             spin_lock_irqsave_nested(&convert->target->lock, flags,
+                             SINGLE_DEPTH_NESTING);
+             hash_add_rcu(convert->target->context_to_sid,
+                             &dst_convert->list, dst_convert->context.hash);
+             spin_unlock_irqrestore(&convert->target->lock, flags);

Still having a hard time understanding why we need to lock the target. The target here is always the newsidtab allocated by security_load_policy(), not yet exposed to any other threads in the system?

It is exposed to other threads, for example in sidtab_context_to_sid() which can be
triggered by calls from userspace like restorecon, runcon, etc.

That means that hash_add_rcu can be called simultaneously on newsidtab in sidtab_convert_hashtable() and sidtab_context_to_sid().

The previous implementation avoided this issue because sidtab_convert() and sidtab_context_to_sid() wrote to non-overlapping parts of the newsidtab tree so no locking was necessary.

Quoted 11 lines
Quoted 11 lines
security/selinux/ss/sidtab.c +1 -2
      }
 
      if (context->len)
              pr_info("SELinux:  Context %s is not valid (left unmapped).\n",
                      context->str);
 
-     sidtab_rcache_push(s, count);
-     *index = count;
+     *sid = index_to_sid(count);
 
Quoted 8 lines

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

Quoted 4 lines
security/selinux/ss/sidtab.c +2 -1
-     /* write entries before writing new count */
+     /* Write entries before updating count. */
      smp_store_release(&s->count, count + 1);
+     hash_add_rcu(s->context_to_sid, &dst->list, dst->context.hash);

Exactly what guarantee do we think we are getting from placing the hash_add_rcu() after the smp_store_release() on s->count, and is that guarantee well-founded?

None at all. I could move the hash_add_rcu() to before the smp_store_release(). The ordering
of these two statements is not important.

Quoted 10 lines

security/selinux/ss/sidtab.c static void sidtab_destroy_tree(union sidtab_entry_inner entry, u32 level) · line 466

Quoted 7 lines
security/selinux/ss/sidtab.c +1 -1
@@ -474,7 +463,7 @@ static void sidtab_destroy_tree(union sidtab_entry_inner entry, u32 level)
 
              for (i = 0; i < SIDTAB_LEAF_ENTRIES; i++)
                      context_destroy(&node->entries[i].context);
-             kfree(node);
+             kfree_rcu(node, rcu);

Is it safe to do this without having deleted it from the hash and without having taken the spinlock?

Yes and yes.

At this point we've already shifted over to using the new sidtab so only this thread has access to the oldsidtab.
The objects within the sidtab are entirely shared between the tree and the hashtable so we should just free
them once. Calling hash_del_rcu() before hand is just going to move pointers around on a list of objects which
will all be deleted anyways.

Quoted 13 lines
Quoted 13 lines
security/selinux/ss/sidtab.c +0 -0
      }
  }
 
security/selinux/ss/sidtab.h +0 -0
index 1f4763141aa1..f1f505df97ba 100644
@@ -83,11 +88,11 @@ struct sidtab {
      struct sidtab_convert_params *convert;
      spinlock_t lock;
 
Quoted 11 lines

security/selinux/ss/sidtab.h struct sidtab { · line 95

Quoted 8 lines
security/selinux/ss/sidtab.h +3 -3
-     /* 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);

Should this and/or any of the associated RCU-protected structures be marked with __rcu for sparse checking?

I'm unsure what you mean.

Quoted 6 lines
Quoted 4 lines
security/selinux/ss/sidtab.h +0 -0
  };
 
  int sidtab_init(struct sidtab *s);
#7 lore raw
In reply to Jeff Vander Stoep
Quoted 44 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.

Quoted 6 lines

V3:
-Add lock nesting notation.

V4:
-Moved to *_rcu variants of the various hashtable functions as suggested by Ondrej Mosnacek and Will Deacon.

I may be misunderstanding the purpose of RCU, but isn't all this RCU stuff a big overkill when these entries are never removed? (Well, they are removed when the sidtab is being destroyed, at which point however no other threads are accessing them any more.) In my understanding, RCU basically makes sure that objects that you dereference in an RCU critical section are not destroyed until you leave it. Yes, it also helps you to dereference/update them safely, but that can be achieved on its own in a simpler way. Instead of using RCU here, I would instead suggest looking into adding an equivalent of list_for_each_entry_lockless()* for hlist and maybe introduce some suitable hlist_add_something() function that ensures consistency w.r.t. the lockless traversal (perhaps the WRITE_ONCE() in hlist_add() is already sufficient, but I'm not sure...).

Quoted 16 lines

-Naming/spelling fixups.

---
 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        |  17 +-
 9 files changed, 302 insertions(+), 160 deletions(-)

<snip>

Signature · 3 lines
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
#8 lore raw
Quoted 57 lines · Ondrej Mosnacek
Quoted 44 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.

Quoted 6 lines

V3:
-Add lock nesting notation.

V4:
-Moved to *_rcu variants of the various hashtable functions as suggested by Ondrej Mosnacek and Will Deacon.

I may be misunderstanding the purpose of RCU, but isn't all this RCU stuff a big overkill when these entries are never removed? (Well, they are removed when the sidtab is being destroyed, at which point however no other threads are accessing them any more.) In my understanding, RCU basically makes sure that objects that you dereference in an RCU

Quoted 8 lines

critical section are not destroyed until you leave it. Yes, it also helps you to dereference/update them safely, but that can be achieved on its own in a simpler way. Instead of using RCU here, I would instead suggest looking into adding an equivalent of list_for_each_entry_lockless()* for hlist and maybe introduce some suitable hlist_add_something() function that ensures consistency w.r.t. the lockless traversal (perhaps the WRITE_ONCE() in hlist_add() is already sufficient, but I'm not sure...).

If you use the existing _rcu accessors you will get correctly enforced dependency ordering on the reader side and correctly placed release ordering on the updater side. I don't think that's a big overkill, and you can use the RCU accessors to achieve the lockless traversal.

hlist_add() is not safe against a concurrent traversal because the WRITE_ONCE() provides no memory ordering guarantees, allowing the readers to see an uninitialised node.

How exactly would list_for_each_entry_lockless() and hlist_add_something() differ from the RCU variants, assuming they're implemented correctly?

Will

#9 lore raw
Quoted 67 lines · Will Deacon
Quoted 57 lines · Ondrej Mosnacek
Quoted 44 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.

Quoted 6 lines

V3:
-Add lock nesting notation.

V4:
-Moved to *_rcu variants of the various hashtable functions as suggested by Ondrej Mosnacek and Will Deacon.

I may be misunderstanding the purpose of RCU, but isn't all this RCU stuff a big overkill when these entries are never removed? (Well, they are removed when the sidtab is being destroyed, at which point however no other threads are accessing them any more.) In my understanding, RCU basically makes sure that objects that you dereference in an RCU

Quoted 8 lines

critical section are not destroyed until you leave it. Yes, it also helps you to dereference/update them safely, but that can be achieved on its own in a simpler way. Instead of using RCU here, I would instead suggest looking into adding an equivalent of list_for_each_entry_lockless()* for hlist and maybe introduce some suitable hlist_add_something() function that ensures consistency w.r.t. the lockless traversal (perhaps the WRITE_ONCE() in hlist_add() is already sufficient, but I'm not sure...).

Quoted 4 lines

If you use the existing _rcu accessors you will get correctly enforced dependency ordering on the reader side and correctly placed release ordering on the updater side. I don't think that's a big overkill, and you can use the RCU accessors to achieve the lockless traversal.

OK, but you don't need the read_lock()/unlock(), rcu_head field in the entries, and kfree_rcu(), right?

Quoted 4 lines

hlist_add() is not safe against a concurrent traversal because the WRITE_ONCE() provides no memory ordering guarantees, allowing the readers to see an uninitialised node.

Right, so we would need a new function that does smp_store_release() instead.

Quoted 3 lines

How exactly would list_for_each_entry_lockless() and hlist_add_something() differ from the RCU variants, assuming they're implemented correctly?

Looking at the implementation of rcu_dereference() and rcu_assign_pointer(), they would probably be practically the same, except the rcu_read_lock_held() check in rcu_dereference(). That and they would clearly communicate that they are not doing actual RCU, but just allow lockless traversal of an add-only hlist.

--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

#10 lore raw
Quoted 7 lines
Quoted 4 lines

If you use the existing _rcu accessors you will get correctly enforced dependency ordering on the reader side and correctly placed release ordering on the updater side. I don't think that's a big overkill, and you can use the RCU accessors to achieve the lockless traversal.

OK, but you don't need the read_lock()/unlock(), rcu_head field in the entries, and kfree_rcu(), right?

Hmm... I can get rid of rcu_head/kfree_rcu in any case because we never remove items during normal use so we don't require the "rcu grace period".

Quoted 24 lines
Quoted 5 lines

hlist_add() is not safe against a concurrent traversal because the WRITE_ONCE() provides no memory ordering guarantees, allowing the readers to see an uninitialised node.

Right, so we would need a new function that does smp_store_release() instead.

Quoted 3 lines

How exactly would list_for_each_entry_lockless() and hlist_add_something() differ from the RCU variants, assuming they're implemented correctly?

Looking at the implementation of rcu_dereference() and rcu_assign_pointer(), they would probably be practically the same, except the rcu_read_lock_held() check in rcu_dereference(). That and they would clearly communicate that they are not doing actual RCU, but just allow lockless traversal of an add-only hlist.

--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.