| Message ID | 20231102154524.12006-4-jsatterfield.linux@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | Paul Moore |
| Headers | show |
| Series | selinux: avtab arrays and refactors | expand |
On Thu, Nov 2, 2023 at 11:45 AM Jacob Satterfield <jsatterfield.linux@gmail.com> wrote: > > The current avtab hashtable employs a separate chaining collision > resolution strategy where each bucket/chain holds an ordered linked list > of pointers to kmem_cache allocated avtab_node elements. > > On Fedora 38 (x86_64) using the default policy, avtab_node_cachep > uses 573 slabs each containing 170 objects totaling 2,337,840 bytes. > A call to kmem_cache_zalloc() is required for every single rule, which > in the default policy is currently 96,730 and continually rising. > > When both sets of avtab_node (regular and cond.) are turned into arrays > with the hash table chain heads pointing into it, this results in only > two additional kvcalloc() calls and the complete removal of the > kmem_cache itself and its memory and runtime overheads. > > Running "perf stat -r 100 -d load_policy" has shown a runtime reduction > of around 10% on a Fedora 38 x86_64 VM with this single patch. Future > patches focused on improving the hash table's collision resolution > strategy and array layout (struct-of-arrays vs. array-of-structs) may > elicit even more caching and therefore runtime performance improvements. > > To prevent the conditional table from under-allocating the avtab_node > array, which creates a heap-overflow bug, the two-pass algorithm in the > patch "selinux: fix conditional avtab slot hint" is required. > > Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com> > --- This patch doesn't apply cleanly via git am; it will apply manually with fuzz via patch but that suggests you sent the wrong version of the patch rather than one based on the latest series.
On Thu, Nov 2, 2023 at 1:34 PM Stephen Smalley <stephen.smalley.work@gmail.com> wrote: > > On Thu, Nov 2, 2023 at 11:45 AM Jacob Satterfield > <jsatterfield.linux@gmail.com> wrote: > > > > The current avtab hashtable employs a separate chaining collision > > resolution strategy where each bucket/chain holds an ordered linked list > > of pointers to kmem_cache allocated avtab_node elements. > > > > On Fedora 38 (x86_64) using the default policy, avtab_node_cachep > > uses 573 slabs each containing 170 objects totaling 2,337,840 bytes. > > A call to kmem_cache_zalloc() is required for every single rule, which > > in the default policy is currently 96,730 and continually rising. > > > > When both sets of avtab_node (regular and cond.) are turned into arrays > > with the hash table chain heads pointing into it, this results in only > > two additional kvcalloc() calls and the complete removal of the > > kmem_cache itself and its memory and runtime overheads. > > > > Running "perf stat -r 100 -d load_policy" has shown a runtime reduction > > of around 10% on a Fedora 38 x86_64 VM with this single patch. Future > > patches focused on improving the hash table's collision resolution > > strategy and array layout (struct-of-arrays vs. array-of-structs) may > > elicit even more caching and therefore runtime performance improvements. > > > > To prevent the conditional table from under-allocating the avtab_node > > array, which creates a heap-overflow bug, the two-pass algorithm in the > > patch "selinux: fix conditional avtab slot hint" is required. > > > > Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com> > > --- > > This patch doesn't apply cleanly via git am; it will apply manually > with fuzz via patch but that suggests you sent the wrong version of > the patch rather than one based on the latest series. This is my fault. When I dropped a patch from the series, I did it after git format-patch not realising the following hashes wouldn't align. (I'm still learning this workflow...) I will resend the patch series with the correct hashes. My apologies for the spam.
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index f437bd588b04..50c8db8eb511 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -24,7 +24,6 @@ #include "avtab.h" #include "policydb.h" -static struct kmem_cache *avtab_node_cachep __ro_after_init; static struct kmem_cache *avtab_xperms_cachep __ro_after_init; #define avtab_chain_for_each(pos, tab, slot) \ @@ -79,17 +78,15 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst, { struct avtab_node *newnode; struct avtab_extended_perms *xperms; - newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL); - if (newnode == NULL) + if (h->nel == h->nnodes) return NULL; + newnode = &h->nodes[h->nel]; newnode->key = *key; if (key->specified & AVTAB_XPERMS) { xperms = kmem_cache_zalloc(avtab_xperms_cachep, GFP_KERNEL); - if (xperms == NULL) { - kmem_cache_free(avtab_node_cachep, newnode); + if (xperms == NULL) return NULL; - } *xperms = *(datum->u.xperms); newnode->datum.u.xperms = xperms; } else { @@ -225,7 +222,7 @@ void avtab_destroy(struct avtab *h) u32 i; struct avtab_node *cur, *temp; - if (!h) + if (!h || !h->htable) return; for (i = 0; i < h->nslot; i++) { @@ -236,11 +233,13 @@ void avtab_destroy(struct avtab *h) if (temp->key.specified & AVTAB_XPERMS) kmem_cache_free(avtab_xperms_cachep, temp->datum.u.xperms); - kmem_cache_free(avtab_node_cachep, temp); } } kvfree(h->htable); + kvfree(h->nodes); h->htable = NULL; + h->nodes = NULL; + h->nnodes = 0; h->nel = 0; h->nslot = 0; h->mask = 0; @@ -249,20 +248,28 @@ void avtab_destroy(struct avtab *h) void avtab_init(struct avtab *h) { h->htable = NULL; + h->nodes = NULL; + h->nnodes = 0; h->nel = 0; h->nslot = 0; h->mask = 0; } -static int avtab_alloc_common(struct avtab *h, u32 nslot) +static int avtab_alloc_common(struct avtab *h, u32 nslot, u32 nrules) { if (!nslot) return 0; - h->htable = kvcalloc(nslot, sizeof(void *), GFP_KERNEL); + h->htable = kvcalloc(nslot, sizeof(*h->htable), GFP_KERNEL); if (!h->htable) return -ENOMEM; - + h->nodes = kvcalloc(nrules, sizeof(*h->nodes), GFP_KERNEL); + if (!h->nodes) { + kvfree(h->htable); + h->htable = NULL; + return -ENOMEM; + } + h->nnodes = nrules; h->nslot = nslot; h->mask = nslot - 1; return 0; @@ -278,7 +285,7 @@ int avtab_alloc(struct avtab *h, u32 nrules) if (nslot > MAX_AVTAB_HASH_BUCKETS) nslot = MAX_AVTAB_HASH_BUCKETS; - rc = avtab_alloc_common(h, nslot); + rc = avtab_alloc_common(h, nslot, nrules); if (rc) return rc; } @@ -289,7 +296,7 @@ int avtab_alloc(struct avtab *h, u32 nrules) int avtab_alloc_dup(struct avtab *new, const struct avtab *orig) { - return avtab_alloc_common(new, orig->nslot); + return avtab_alloc_common(new, orig->nslot, orig->nel); } #ifdef CONFIG_SECURITY_SELINUX_DEBUG @@ -614,9 +621,6 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp) void __init avtab_cache_init(void) { - avtab_node_cachep = kmem_cache_create("avtab_node", - sizeof(struct avtab_node), - 0, SLAB_PANIC, NULL); avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms", sizeof(struct avtab_extended_perms), 0, SLAB_PANIC, NULL); diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h index 86fb6f793eec..5e465be6f057 100644 --- a/security/selinux/ss/avtab.h +++ b/security/selinux/ss/avtab.h @@ -82,6 +82,8 @@ struct avtab_node { struct avtab { struct avtab_node **htable; + struct avtab_node *nodes; + u32 nnodes; /* number of nodes */ u32 nel; /* number of elements */ u32 nslot; /* number of hash slots */ u32 mask; /* mask to compute hash func */
The current avtab hashtable employs a separate chaining collision resolution strategy where each bucket/chain holds an ordered linked list of pointers to kmem_cache allocated avtab_node elements. On Fedora 38 (x86_64) using the default policy, avtab_node_cachep uses 573 slabs each containing 170 objects totaling 2,337,840 bytes. A call to kmem_cache_zalloc() is required for every single rule, which in the default policy is currently 96,730 and continually rising. When both sets of avtab_node (regular and cond.) are turned into arrays with the hash table chain heads pointing into it, this results in only two additional kvcalloc() calls and the complete removal of the kmem_cache itself and its memory and runtime overheads. Running "perf stat -r 100 -d load_policy" has shown a runtime reduction of around 10% on a Fedora 38 x86_64 VM with this single patch. Future patches focused on improving the hash table's collision resolution strategy and array layout (struct-of-arrays vs. array-of-structs) may elicit even more caching and therefore runtime performance improvements. To prevent the conditional table from under-allocating the avtab_node array, which creates a heap-overflow bug, the two-pass algorithm in the patch "selinux: fix conditional avtab slot hint" is required. Signed-off-by: Jacob Satterfield <jsatterfield.linux@gmail.com> --- security/selinux/ss/avtab.c | 36 ++++++++++++++++++++---------------- security/selinux/ss/avtab.h | 2 ++ 2 files changed, 22 insertions(+), 16 deletions(-)