On 11/4/19 2:15 PM, Jeff Vander Stoep wrote:
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.
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
done
Splat:
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
-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 <jeffv@xxxxxxxxxx>
Reported-by: Stephen Smalley <sds@xxxxxxxxxxxxx>
Reported-by: Jovana Knezevic <jovanak@xxxxxxxxxx>
---
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>
