20810a2469
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 ee1a84fdfe ("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.
Signed-off-by: Jeff Vander Stoep <jeffv@google.com>
Reported-by: Stephen Smalley <sds@tycho.nsa.gov>
Reported-by: Jovana Knezevic <jovanak@google.com>
Reviewed-by: Stephen Smalley <sds@tycho.nsa.gov>
Tested-by: Stephen Smalley <sds@tycho.nsa.gov>
[PM: subj tweak, removed changelog from patch description]
Signed-off-by: Paul Moore <paul@paul-moore.com>
(cherry picked from commit 66f8e2f03c02e812002f8e9e465681cc62edda5b)
Bug: 140252993
Change-Id: Iead2a1d90731ae24fefec2a40af5ffdc457ac916
Signed-off-by: Jeff Vander Stoep <jeffv@google.com>
45 lines
1.1 KiB
C
45 lines
1.1 KiB
C
/* SPDX-License-Identifier: GPL-2.0 */
|
|
/*
|
|
* Implementation of the security services.
|
|
*
|
|
* Author : Stephen Smalley, <sds@tycho.nsa.gov>
|
|
*/
|
|
#ifndef _SS_SERVICES_H_
|
|
#define _SS_SERVICES_H_
|
|
|
|
#include "policydb.h"
|
|
#include "context.h"
|
|
|
|
/* Mapping for a single class */
|
|
struct selinux_mapping {
|
|
u16 value; /* policy value for class */
|
|
unsigned int num_perms; /* number of permissions in class */
|
|
u32 perms[sizeof(u32) * 8]; /* policy values for permissions */
|
|
};
|
|
|
|
/* Map for all of the classes, with array size */
|
|
struct selinux_map {
|
|
struct selinux_mapping *mapping; /* indexed by class */
|
|
u16 size; /* array size of mapping */
|
|
};
|
|
|
|
struct selinux_ss {
|
|
struct sidtab *sidtab;
|
|
struct policydb policydb;
|
|
rwlock_t policy_rwlock;
|
|
u32 latest_granting;
|
|
struct selinux_map map;
|
|
struct page *status_page;
|
|
struct mutex status_lock;
|
|
};
|
|
|
|
void services_compute_xperms_drivers(struct extended_perms *xperms,
|
|
struct avtab_node *node);
|
|
|
|
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_ */
|