selinux: sidtab: reverse lookup hash table
PATCH v2 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.
-Move the hash_add() statement to after the smp_store_release() to ensure that the contents have been written before the object becomes available in the hashtable.
-The new sidtab hash stats file in selinuxfs has been moved out of the avc dir and into a new "ss" dir.
--- 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
@@ -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 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
@@ -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 +64 -0
88 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 +65 -22
185 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 +116 -133
392 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.24.0.rc1.363.gb1bccd3e3d-goog
Quoted 35 lines · Jeff Vander Stoep
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
ee1a84fdwhich 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 thesid_to_contexttree can also be used for thecontext_to_sidhashtable 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_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.
Quoted 7 lines
Changes in V2:
-The hashtable usessidtab_entry_leafobjects directly so these objects are shared between thesid_to_contextlookup tree and thecontext_to_sidhashtable.
-Move thehash_add()statement to after thesmp_store_release()to ensure that the contents have been written before the object becomes available in the hashtable.
Don't forget to cc Paul and anyone who commented previously (e.g. Ondrej).
I could be wrong, but I think that only helps if we also do a smp_load_acquire() prior to reading/walking the hash table and if there is an actual data dependency between the target of the store/load and what we are trying to protect here. I don't think that's the case here. So I don't think you can or should piggyback on the existing load_acquire/store_release pair. Ondrej can correct me if I am wrong (entirely possible).
I also get this splat upon running Ondrej's reproducer for the bug fixed by his sidtab rewrite.
Reproducer:
while true; do load_policy; echo -n .; sleep 0.1; done &
for (( i = 0; i < 1024; i++ )); do
runcon -l s0:c$i echo -n x || break
# or:
# chcon -l s0:c$i <some_file> || break
doneSplat:
6>[ 1070.843961] SELinux: Converting 3927 SID table entries...
<4>[ 1070.858060]
<4>[ 1070.858064] ============================================
<4>[ 1070.858066] WARNING: possible recursive locking detected
<4>[ 1070.858068] 5.4.0-rc1+ #50 Not tainted
<4>[ 1070.858070] --------------------------------------------
<4>[ 1070.858072] runcon/13122 is trying to acquire lock:
<4>[ 1070.858074] ffff88869467c248 (&(&s->lock)->rlock){..-.}, at: sidtab_context_to_sid+0x379/0x700
<4>[ 1070.858080]
<4>[ 1070.858080] but task is already holding lock:
<4>[ 1070.858082] ffff8886e608c248 (&(&s->lock)->rlock){..-.}, at: sidtab_context_to_sid+0x64/0x700
<4>[ 1070.858086]
<4>[ 1070.858086] other info that might help us debug this:
<4>[ 1070.858088] Possible unsafe locking scenario:
<4>[ 1070.858088]
<4>[ 1070.858089] CPU0
<4>[ 1070.858090] ----
<4>[ 1070.858091] lock(&(&s->lock)->rlock);
<4>[ 1070.858093] lock(&(&s->lock)->rlock);
<4>[ 1070.858095]
<4>[ 1070.858095] *** DEADLOCK ***
<4>[ 1070.858095]
<4>[ 1070.858097] May be due to missing lock nesting notation
<4>[ 1070.858097]
<4>[ 1070.858099] 3 locks held by runcon/13122:
<4>[ 1070.858100] #0: ffff8887fa97c820 (sb_writers#9){.+.+}, at: vfs_write+0x215/0x280
<4>[ 1070.858105] #1: ffffffffae0230e8 (&selinux_ss.policy_rwlock){.+.?}, at: security_context_to_sid_core+0x2c0/0x340
<4>[ 1070.858109] #2: ffff8886e608c248 (&(&s->lock)->rlock){..-.}, at: sidtab_context_to_sid+0x64/0x700
<4>[ 1070.858113]
<4>[ 1070.858113] stack backtrace:
<4>[ 1070.858116] CPU: 1 PID: 13122 Comm: runcon Not tainted 5.4.0-rc1+ #50
<4>[ 1070.858118] Hardware name: Dell Inc. OptiPlex 7050/0NW6H5, BIOS 1.8.3 03/23/2018
<4>[ 1070.858120] Call Trace:
<4>[ 1070.858124] dump_stack+0x9a/0xf0
<4>[ 1070.858128] __lock_acquire.cold+0x12e/0x212
<4>[ 1070.858136] ? lockdep_hardirqs_on+0x260/0x260
<4>[ 1070.858142] lock_acquire+0xe5/0x210
<4>[ 1070.858160] ? sidtab_context_to_sid+0x379/0x700
<4>[ 1070.858164] _raw_spin_lock_irqsave+0x44/0x60
<4>[ 1070.858166] ? sidtab_context_to_sid+0x379/0x700
<4>[ 1070.858169] sidtab_context_to_sid+0x379/0x700
<4>[ 1070.858173] ? security_compute_sid.part.0+0x960/0x960
<4>[ 1070.858177] security_context_to_sid_core+0x177/0x340
<4>[ 1070.858180] ? context_to_sid.isra.0+0x60/0x60
<4>[ 1070.858182] ? match_held_lock+0x1b/0x240
<4>[ 1070.858200] ? __might_fault+0x6f/0xd0
<4>[ 1070.858203] security_context_to_sid+0x12/0x20
<4>[ 1070.858206] sel_write_context+0x19b/0x200
<4>[ 1070.858209] ? selinux_transaction_write+0xa0/0xa0
<4>[ 1070.858213] ? _copy_from_user+0xa1/0xd0
<4>[ 1070.858216] ? selinux_transaction_write+0xa0/0xa0
<4>[ 1070.858218] selinux_transaction_write+0x72/0xa0
<4>[ 1070.858221] vfs_write+0x12f/0x280
<4>[ 1070.858224] ksys_write+0xc3/0x160
<4>[ 1070.858227] ? __ia32_sys_read+0x50/0x50
<4>[ 1070.858230] ? lockdep_hardirqs_off+0xbe/0x100
<4>[ 1070.858232] ? mark_held_locks+0x24/0x90
<4>[ 1070.858236] do_syscall_64+0x74/0xd0
<4>[ 1070.858239] entry_SYSCALL_64_after_hwframe+0x49/0xbe
<4>[ 1070.858242] RIP: 0033:0x7f7e94d3a467
<4>[ 1070.858245] 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 8b 04 25 18 00 00 00 85 c0 75 10 b8 01 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 51 c3 48 83 ec 28 48 89 54 24 18 48 89 74 24
<4>[ 1070.858247] RSP: 002b:00007ffd48dbae78 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
<4>[ 1070.858250] RAX: ffffffffffffffda RBX: 00007ffd48dbc038 RCX: 00007f7e94d3a467
<4>[ 1070.858252] RDX: 000000000000002f RSI: 000055e32f081600 RDI: 0000000000000003
<4>[ 1070.858254] RBP: 000055e32f081600 R08: 00000000ffffffff R09: 00007ffd48dbad10
<4>[ 1070.858255] R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000003
<4>[ 1070.858257] R13: 00007ffd48dbbefc R14: 0000000000000000 R15: 0000000000000000Quoted 18 lines
-The new sidtab hash stats file in selinuxfs has been moved out of the avc dir and into a new "ss" dir.
Signed-off-by Jeff Vander Stoep <[email protected]>Reported-by Stephen Smalley <[email protected]>Reported-by Jovana Knezevic <[email protected]>--- 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(-)
<snip>
Is it actually a deadlock, or just missing nesting annotation? I'm unable to reproduce (and this was one of my test cases). On my device I use:
while true; do load_policy /vendor/etc/selinux/precompiled_sepolicy; echo -n .; sleep 0.1; done &
for i in $(seq 1 256);
do
runcon u:r:untrusted_app:s0:c$i,c256 echo -n x || break
done
dmesg is full of:
<snip>
[ 73.731342] c4 8041 SELinux: Converting 1694 SID table entries... [ 73.740946] c4 8041 SELinux: policy capability network_peer_controls=1 [ 73.747800] c4 8041 SELinux: policy capability open_perms=1 [ 73.759296] c4 8041 SELinux: policy capability always_check_network=0 [ 73.771677] c4 8041 SELinux: policy capability nnp_nosuid_transition=1 [ 73.957571] c3 8049 SELinux: Converting 1700 SID table entries... [ 73.968435] c4 8049 SELinux: policy capability network_peer_controls=1 [ 73.975278] c4 8049 SELinux: policy capability open_perms=1 [ 73.986776] c4 8049 SELinux: policy capability always_check_network=0 [ 73.999145] c4 8049 SELinux: policy capability nnp_nosuid_transition=1
<snip>
Quoted 171 lines · Stephen Smalley
Quoted 35 lines · Jeff Vander Stoep
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
ee1a84fdwhich 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 thesid_to_contexttree can also be used for thecontext_to_sidhashtable 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_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.
Quoted 7 lines
Changes in V2:
-The hashtable usessidtab_entry_leafobjects directly so these objects are shared between thesid_to_contextlookup tree and thecontext_to_sidhashtable.
-Move thehash_add()statement to after thesmp_store_release()to ensure that the contents have been written before the object becomes available in the hashtable.Don't forget to cc Paul and anyone who commented previously (e.g. Ondrej).
I could be wrong, but I think that only helps if we also do a
smp_load_acquire()prior to reading/walking the hash table and if there is an actual data dependency between the target of the store/load and
what we are trying to protect here. I don't think that's the case
here. So I don't think you can or should piggyback on the existing load_acquire/store_release pair. Ondrej can correct me if I am wrong (entirely possible).I also get this splat upon running Ondrej's reproducer for the bug fixed by his sidtab rewrite.
Reproducer:
while true; do load_policy; echo -n .; sleep 0.1; done & for (( i = 0; i < 1024; i++ )); do runcon -l s0:c$i echo -n x || break # or: # chcon -l s0:c$i <some_file> || break doneSplat:
6>[ 1070.843961] SELinux: Converting 3927 SID table entries...
<4>[ 1070.858060] <4>[ 1070.858064] ============================================ <4>[ 1070.858066] WARNING: possible recursive locking detected <4>[ 1070.858068] 5.4.0-rc1+ #50 Not tainted <4>[ 1070.858070] -------------------------------------------- <4>[ 1070.858072] runcon/13122 is trying to acquire lock: <4>[ 1070.858074] ffff88869467c248 (&(&s->lock)->rlock){..-.}, at: sidtab_context_to_sid+0x379/0x700 <4>[ 1070.858080] <4>[ 1070.858080] but task is already holding lock: <4>[ 1070.858082] ffff8886e608c248 (&(&s->lock)->rlock){..-.}, at: sidtab_context_to_sid+0x64/0x700 <4>[ 1070.858086] <4>[ 1070.858086] other info that might help us debug this: <4>[ 1070.858088] Possible unsafe locking scenario: <4>[ 1070.858088] <4>[ 1070.858089] CPU0 <4>[ 1070.858090] ---- <4>[ 1070.858091] lock(&(&s->lock)->rlock); <4>[ 1070.858093] lock(&(&s->lock)->rlock); <4>[ 1070.858095] <4>[ 1070.858095] *** DEADLOCK *** <4>[ 1070.858095] <4>[ 1070.858097] May be due to missing lock nesting notation <4>[ 1070.858097] <4>[ 1070.858099] 3 locks held by runcon/13122: <4>[ 1070.858100] #0: ffff8887fa97c820 (sb_writers#9){.+.+}, at: vfs_write+0x215/0x280 <4>[ 1070.858105] #1: ffffffffae0230e8 (&selinux_ss.policy_rwlock){.+.?}, at: security_context_to_sid_core+0x2c0/0x340 <4>[ 1070.858109] #2: ffff8886e608c248 (&(&s->lock)->rlock){..-.}, at: sidtab_context_to_sid+0x64/0x700 <4>[ 1070.858113] <4>[ 1070.858113] stack backtrace: <4>[ 1070.858116] CPU: 1 PID: 13122 Comm: runcon Not tainted 5.4.0-rc1+ #50 <4>[ 1070.858118] Hardware name: Dell Inc. OptiPlex 7050/0NW6H5, BIOS 1.8.3 03/23/2018 <4>[ 1070.858120] Call Trace: <4>[ 1070.858124] dump_stack+0x9a/0xf0 <4>[ 1070.858128] __lock_acquire.cold+0x12e/0x212 <4>[ 1070.858136] ? lockdep_hardirqs_on+0x260/0x260 <4>[ 1070.858142] lock_acquire+0xe5/0x210 <4>[ 1070.858160] ? sidtab_context_to_sid+0x379/0x700 <4>[ 1070.858164] _raw_spin_lock_irqsave+0x44/0x60 <4>[ 1070.858166] ? sidtab_context_to_sid+0x379/0x700 <4>[ 1070.858169] sidtab_context_to_sid+0x379/0x700 <4>[ 1070.858173] ? security_compute_sid.part.0+0x960/0x960 <4>[ 1070.858177] security_context_to_sid_core+0x177/0x340 <4>[ 1070.858180] ? context_to_sid.isra.0+0x60/0x60 <4>[ 1070.858182] ? match_held_lock+0x1b/0x240 <4>[ 1070.858200] ? __might_fault+0x6f/0xd0 <4>[ 1070.858203] security_context_to_sid+0x12/0x20 <4>[ 1070.858206] sel_write_context+0x19b/0x200 <4>[ 1070.858209] ? selinux_transaction_write+0xa0/0xa0 <4>[ 1070.858213] ? _copy_from_user+0xa1/0xd0 <4>[ 1070.858216] ? selinux_transaction_write+0xa0/0xa0 <4>[ 1070.858218] selinux_transaction_write+0x72/0xa0 <4>[ 1070.858221] vfs_write+0x12f/0x280 <4>[ 1070.858224] ksys_write+0xc3/0x160 <4>[ 1070.858227] ? __ia32_sys_read+0x50/0x50 <4>[ 1070.858230] ? lockdep_hardirqs_off+0xbe/0x100 <4>[ 1070.858232] ? mark_held_locks+0x24/0x90 <4>[ 1070.858236] do_syscall_64+0x74/0xd0 <4>[ 1070.858239] entry_SYSCALL_64_after_hwframe+0x49/0xbe <4>[ 1070.858242] RIP: 0033:0x7f7e94d3a467 <4>[ 1070.858245] 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 8b 04 25 18 00 00 00 85 c0 75 10 b8 01 00 00 00 0f 05 <48> 3d 00 f0 ff ff 77 51 c3 48 83 ec 28 48 89 54 24 18 48 89 74 24 <4>[ 1070.858247] RSP: 002b:00007ffd48dbae78 EFLAGS: 00000246 ORIG_RAX: 0000000000000001 <4>[ 1070.858250] RAX: ffffffffffffffda RBX: 00007ffd48dbc038 RCX: 00007f7e94d3a467 <4>[ 1070.858252] RDX: 000000000000002f RSI: 000055e32f081600 RDI: 0000000000000003 <4>[ 1070.858254] RBP: 000055e32f081600 R08: 00000000ffffffff R09: 00007ffd48dbad10 <4>[ 1070.858255] R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000000003 <4>[ 1070.858257] R13: 00007ffd48dbbefc R14: 0000000000000000 R15:0000000000000000
Quoted 18 lines
-The new sidtab hash stats file in selinuxfs has been moved out of the avc dir and into a new "ss" dir.
Signed-off-by Jeff Vander Stoep <[email protected]>Reported-by Stephen Smalley <[email protected]>Reported-by Jovana Knezevic <[email protected]>--- 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(-)<snip>
Quoted 69 lines · Jeff Vander Stoep
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
ee1a84fdwhich 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 thesid_to_contexttree can also be used for thecontext_to_sidhashtable 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_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.
-Move thehash_add()statement to after thesmp_store_release()to ensure that the contents have been written before the object becomes available in the hashtable.
-The new sidtab hash stats file in selinuxfs has been moved out of the avc dir and into a new "ss" dir.Signed-off-by Jeff Vander Stoep <[email protected]>Reported-by Stephen Smalley <[email protected]>Reported-by Jovana Knezevic <[email protected]>--- 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 +1
-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. +
security/selinux/Kconfig config SECURITY_SELINUX_CHECKREQPROT_VALUE · line 98
Quoted 10 lines
security/selinux/Kconfig +10
-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
s/than/then/
security/selinux/Kconfig config SECURITY_SELINUX_CHECKREQPROT_VALUE · line 99
Quoted 1 line
security/selinux/Kconfig +1
-0+ ensure that lookups times are fast and stable.
lookup times are short and stable
<snip>
Quoted 29 lines
security/selinux/ss/sidtab.c +4
-4@@ -17,26 +17,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 ; +hash_init (s->context_to_sid);spin_lock_init (&s->lock);
security/selinux/ss/sidtab.c line 46
Quoted 10 lines
security/selinux/ss/sidtab.c +7
-0return 0 ; } +static u32 context_to_sid (struct sidtab *s,struct context *context) +{ +struct sidtab_entry_leaf *entry; + +hash_for_each_possible (s->context_to_sid, entry, list, context->hash) { +if (context_cmp (&entry->context, context)) +return entry->sid;
For this to be semantically safe against entries being added, it would need the hlist head -> first member to be read with smp_load_acquire(). Probably in practice you would always get fresh data when dereferencing a pointer, but I don't think we should rely on that... In fact it looks like hash_for_each_possible() wasn't really written with lockless traversal in mind - I checked a few random places that call it and they all either do it under some lock or expect the table to be immutable. I believe you will need to introduce a new equivalents of hash_add()/hlist_add_head() (that does smp_store_release() instead of WRITE_ONCE(), because the 'next' pointer of the node being added must be written before the head's first pointer is set to point to the new node) and hash_for_each_possible()/hlist_for_each_entry() (that loads (head)->first with smp_load_acquire()).
Then again, I'm not an expert on this synchronization stuff, so I might be wrong... But you will have to prove it :)
security/selinux/ss/sidtab.c line 50
Quoted 4 lines
security/selinux/ss/sidtab.c +4
-0+ } +return 0 ; +} +
I am a little uneasy about this function having the same name as the context_to_sid() in security.c. It could be confusing when debugging. Maybe you could name the security.c function to context_struct_to_sid()?
Quoted 3 lines
security/selinux/ss/sidtab.c +0
-0int 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@@ -305,29 +275,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 295
Quoted 10 lines
security/selinux/ss/sidtab.c +5
-0goto 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);
Do we really need to lock the conversion target here? The (undocumented) contract here was that as long as the conversion is in progress, the target sidtab is "owned" by the master sidtab and any modifications of it would be done under the master's spinlock (the target's spinlock wouldn't be used until it is swapped-in to be the new master). Did this contract change with your patch? I think this nested locking is the cause of the lock warning that Stephen is getting so hopefully you can fix it by simply removing this extra locking.
<snip>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
Quoted 207 lines · Ondrej Mosnacek
Quoted 69 lines · Jeff Vander Stoep
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
ee1a84fdwhich 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 thesid_to_contexttree can also be used for thecontext_to_sidhashtable 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_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.
-Move thehash_add()statement to after thesmp_store_release()to ensure that the contents have been written before the object becomes available in the hashtable.
-The new sidtab hash stats file in selinuxfs has been moved out of the avc dir and into a new "ss" dir.Signed-off-by Jeff Vander Stoep <[email protected]>Reported-by Stephen Smalley <[email protected]>Reported-by Jovana Knezevic <[email protected]>--- 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 +1
-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. +security/selinux/Kconfig config SECURITY_SELINUX_CHECKREQPROT_VALUE · line 98
Quoted 10 lines
security/selinux/Kconfig +10
-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 wills/than/then/
security/selinux/Kconfig config SECURITY_SELINUX_CHECKREQPROT_VALUE · line 99
Quoted 1 line
security/selinux/Kconfig +1
-0+ ensure that lookups times are fast and stable.lookup times are short and stable
<snip>
Quoted 29 lines
security/selinux/ss/sidtab.c +4
-4@@ -17,26 +17,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 ; +hash_init (s->context_to_sid);spin_lock_init (&s->lock);security/selinux/ss/sidtab.c line 46
Quoted 10 lines
security/selinux/ss/sidtab.c +7
-0return 0 ; } +static u32 context_to_sid (struct sidtab *s,struct context *context) +{ +struct sidtab_entry_leaf *entry; + +hash_for_each_possible (s->context_to_sid, entry, list, context->hash) { +if (context_cmp (&entry->context, context)) +return entry->sid;For this to be semantically safe against entries being added, it would need the hlist head -> first member to be read with
smp_load_acquire(). Probably in practice you would always get fresh data when dereferencing a pointer, but I don't think we should rely on that... In fact it looks likehash_for_each_possible()wasn't really written with lockless traversal in mind - I checked a few random places that call it and they all either do it under some lock or expect the table to be immutable. I believe you will need to introduce a new equivalents of hash_add()/hlist_add_head() (that doessmp_store_release()instead ofWRITE_ONCE(), because the 'next' pointer of the node being added must be written before the head's first pointer is set to point to the new node) and hash_for_each_possible()/hlist_for_each_entry() (that loads (head)->first withsmp_load_acquire()).Then again, I'm not an expert on this synchronization stuff, so I might be wrong... But you will have to prove it :)
security/selinux/ss/sidtab.c line 50
Quoted 4 lines
security/selinux/ss/sidtab.c +4
-0+ } +return 0 ; +} +I am a little uneasy about this function having the same name as the
context_to_sid()insecurity.c. It could be confusing when debugging. Maybe you could name thesecurity.cfunction tocontext_struct_to_sid()?Quoted 3 lines
security/selinux/ss/sidtab.c +0
-0int 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@@ -305,29 +275,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 295
Quoted 10 lines
security/selinux/ss/sidtab.c +5
-0goto 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);Do we really need to lock the conversion target here? The (undocumented) contract here was that as long as the conversion is in progress, the target sidtab is "owned" by the master sidtab and any modifications of it would be done under the master's spinlock (the target's spinlock wouldn't be used until it is swapped-in to be the new master). Did this contract change with your patch? I think this nested locking is the cause of the lock warning that Stephen is getting so hopefully you can fix it by simply removing this extra locking.
<snip>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
Quoted 135 lines · Ondrej Mosnacek
Quoted 69 lines · Jeff Vander Stoep
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
ee1a84fdwhich 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 thesid_to_contexttree can also be used for thecontext_to_sidhashtable 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_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.
-Move thehash_add()statement to after thesmp_store_release()to ensure that the contents have been written before the object becomes available in the hashtable.
-The new sidtab hash stats file in selinuxfs has been moved out of the avc dir and into a new "ss" dir.Signed-off-by Jeff Vander Stoep <[email protected]>Reported-by Stephen Smalley <[email protected]>Reported-by Jovana Knezevic <[email protected]>--- 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 +1
-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. +security/selinux/Kconfig config SECURITY_SELINUX_CHECKREQPROT_VALUE · line 98
Quoted 10 lines
security/selinux/Kconfig +10
-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 wills/than/then/
security/selinux/Kconfig config SECURITY_SELINUX_CHECKREQPROT_VALUE · line 99
Quoted 1 line
security/selinux/Kconfig +1
-0+ ensure that lookups times are fast and stable.lookup times are short and stable
<snip>
Quoted 29 lines
security/selinux/ss/sidtab.c +4
-4@@ -17,26 +17,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 ; +hash_init (s->context_to_sid);spin_lock_init (&s->lock);security/selinux/ss/sidtab.c line 46
Quoted 10 lines
security/selinux/ss/sidtab.c +7
-0return 0 ; } +static u32 context_to_sid (struct sidtab *s,struct context *context) +{ +struct sidtab_entry_leaf *entry; + +hash_for_each_possible (s->context_to_sid, entry, list, context->hash) { +if (context_cmp (&entry->context, context)) +return entry->sid;For this to be semantically safe against entries being added, it would need the hlist head -> first member to be read with
smp_load_acquire(). Probably in practice you would always get fresh data when dereferencing a pointer, but I don't think we should rely on that... In fact it looks likehash_for_each_possible()wasn't really written with lockless traversal in mind - I checked a few random
Quoted 8 lines
places that call it and they all either do it under some lock or expect the table to be immutable. I believe you will need to introduce a new equivalents of hash_add()/hlist_add_head() (that does
smp_store_release()instead ofWRITE_ONCE(), because the 'next' pointer of the node being added must be written before the head's first pointer is set to point to the new node) and hash_for_each_possible()/hlist_for_each_entry() (that loads (head)->first withsmp_load_acquire()).
This is a good point; I don't see that you can safely use hash_add() and hash_for_each_possible() safely with a completely lockless read code path. So you either have to create (or find) variants that do the right things here or perform locking on the read path.
Quoted 63 lines
Then again, I'm not an expert on this synchronization stuff, so I might be wrong... But you will have to prove it :)
security/selinux/ss/sidtab.c line 50
Quoted 4 lines
security/selinux/ss/sidtab.c +4
-0+ } +return 0 ; +} +I am a little uneasy about this function having the same name as the
context_to_sid()insecurity.c. It could be confusing when debugging. Maybe you could name thesecurity.cfunction tocontext_struct_to_sid()?Quoted 3 lines
security/selinux/ss/sidtab.c +0
-0int 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@@ -305,29 +275,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 295
Quoted 10 lines
security/selinux/ss/sidtab.c +5
-0goto 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);Do we really need to lock the conversion target here? The (undocumented) contract here was that as long as the conversion is in progress, the target sidtab is "owned" by the master sidtab and any modifications of it would be done under the master's spinlock (the target's spinlock wouldn't be used until it is swapped-in to be the new master). Did this contract change with your patch? I think this nested locking is the cause of the lock warning that Stephen is getting so hopefully you can fix it by simply removing this extra locking.
<snip>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
Quoted 23 lines
security/selinux/ss/sidtab.c line 46
Quoted 7 lines
security/selinux/ss/sidtab.c +7
-0+static u32 context_to_sid (struct sidtab *s,struct context *context) +{ +struct sidtab_entry_leaf *entry; + +hash_for_each_possible (s->context_to_sid, entry, list, context->hash) { +if (context_cmp (&entry->context, context)) +return entry->sid;For this to be semantically safe against entries being added, it would need the hlist head -> first member to be read with
smp_load_acquire(). Probably in practice you would always get fresh data when dereferencing a pointer, but I don't think we should rely on that... In fact it looks likehash_for_each_possible()wasn't really written with lockless traversal in mind - I checked a few random places that call it and they all either do it under some lock or expect the table to be immutable. I believe you will need to introduce a new equivalents of hash_add()/hlist_add_head() (that doessmp_store_release()instead ofWRITE_ONCE(), because the 'next' pointer of the node being added must be written before the head's first pointer is set to point to the new node) and hash_for_each_possible()/hlist_for_each_entry() (that loads (head)->first withsmp_load_acquire()).
Quoted 2 lines
Then again, I'm not an expert on this synchronization stuff, so I might be wrong... But you will have to prove it :)
I spoke with Will Deacon about this and he confirmed your concerns that this cannot be done safely without locking. I'll migrate to the "rcu" hashtable variant.
Quoted 36 lines
security/selinux/selinuxfs.c static int sel_make_avc_files(struct dentry *dir) · line 1657
Quoted 5 lines
security/selinux/selinuxfs.c +4
-0+ } +return 0 ; +} +I am a little uneasy about this function having the same name as the
context_to_sid()insecurity.c. It could be confusing when debugging. Maybe you could name thesecurity.cfunction tocontext_struct_to_sid()?Quoted 3 lines
int
sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context){ struct sidtab_isid_entry *entry;<snip>
Quoted 19 lines
security/selinux/ss/sidtab.c +5
-3@@ -305,29 +275,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); goto out_unlock; } + dst_convert->sid =index_to_sid (count);
Quoted 17 lines
security/selinux/ss/sidtab.c static int sidtab_reverse_lookup(struct sidtab *s, struct context *context, · line 295
Quoted 6 lines
security/selinux/ss/sidtab.c +4
-0/* 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);Do we really need to lock the conversion target here? The (undocumented) contract here was that as long as the conversion is in progress, the target sidtab is "owned" by the master sidtab and any modifications of it would be done under the master's spinlock (the target's spinlock wouldn't be used until it is swapped-in to be the new master). Did this contract change with your patch? I think this nested locking is the cause of the lock warning that Stephen is getting so hopefully you can fix it by simply removing this extra locking.
Some form of locking is necessary. Otherwise there can be concurrent additions to the hashtable, which is not safe. My goal here is to avoid having a single lock which is held for the duration of the conversion because that is what caused issues previously during policy reload.
Quoted 7 lines
<snip>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.