On Fri, Oct 20, 2023 at 10:00 AM Stephen Smalley <stephen.smalley.work@xxxxxxxxx> wrote: > > On Wed, Oct 18, 2023 at 1:58 PM Jacob Satterfield > <jsatterfield.linux@xxxxxxxxx> 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 slot indexing into it rather than a pointer, then > > this results in only 2 additional kvcalloc() calls and the complete > > removal of the kmem_cache itself. > > > > Due to how conditional rules are written in the binary policy, the > > code responsible for loading does not know how many conditional rules > > there are before creating the avtab structure. Instead, it was using the > > number of elements in the non-conditional avtab as a hint and allocates > > the hash table based on it. Therefore, a two-pass algorithm is now used > > to calculate the rule count before allocating the avtab nodes array. > > With the current refpolicy and default Fedora policy, this causes the > > number of hash slots for the conditional array to become 4096 instead of > > 32768. This results in a savings of 224KB of heap memory. > > > > The caching characteristics of iterating a single array are better due > > to locality of reference. 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. > > > > Signed-off-by: Jacob Satterfield <jsatterfield.linux@xxxxxxxxx> > > Assuming you fix the previous patch, > Reviewed-by: Stephen Smalley <stephen.smalley.work@xxxxxxxxx> > Thanks for the review. However after running this patch through clang-analyzer, I have discovered this patch creates an edge-case that results in a null pointer dereference within avtab_destroy(). The patch is simple and will be included within the next spin. diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c index eb69fda4f504..cdc509e715ea 100644 --- a/security/selinux/ss/avtab.c +++ b/security/selinux/ss/avtab.c @@ -222,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++) { > > --- > > security/selinux/ss/avtab.c | 47 ++++++++++++++++++++----------- > > security/selinux/ss/avtab.h | 4 ++- > > security/selinux/ss/conditional.c | 37 ++++++++++++++++-------- > > security/selinux/ss/conditional.h | 2 +- > > 4 files changed, 59 insertions(+), 31 deletions(-) > > > > diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c > > index f0d448e7807a..aabe04fc4d04 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 { > > @@ -235,11 +232,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; > > @@ -248,20 +247,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; > > @@ -277,7 +284,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; > > } > > @@ -288,7 +295,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 > > @@ -337,7 +344,7 @@ static const uint16_t spec_order[] = { > > int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, > > int (*insertf)(struct avtab *a, const struct avtab_key *k, > > const struct avtab_datum *d, void *p), > > - void *p) > > + void *p, u32 *nrules) > > { > > __le16 buf16[4]; > > u16 enabled; > > @@ -411,6 +418,10 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, > > if (val & spec_order[i]) { > > key.specified = spec_order[i] | enabled; > > datum.u.data = le32_to_cpu(buf32[items++]); > > + if (nrules) { > > + (*nrules)++; > > + continue; > > + } > > rc = insertf(a, &key, &datum, p); > > if (rc) > > return rc; > > @@ -489,6 +500,11 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, > > pr_err("SELinux: avtab: invalid type\n"); > > return -EINVAL; > > } > > + > > + if (nrules) { > > + (*nrules)++; > > + return 0; > > + } > > return insertf(a, &key, &datum, p); > > } > > > > @@ -522,7 +538,7 @@ int avtab_read(struct avtab *a, void *fp, struct policydb *pol) > > goto bad; > > > > for (i = 0; i < nel; i++) { > > - rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL); > > + rc = avtab_read_item(a, fp, pol, avtab_insertf, NULL, NULL); > > if (rc) { > > if (rc == -ENOMEM) > > pr_err("SELinux: avtab: out of memory\n"); > > @@ -602,9 +618,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 3c3904bf02b0..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 */ > > @@ -104,7 +106,7 @@ struct policydb; > > int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol, > > int (*insert)(struct avtab *a, const struct avtab_key *k, > > const struct avtab_datum *d, void *p), > > - void *p); > > + void *p, u32 *nrules); > > > > int avtab_read(struct avtab *a, void *fp, struct policydb *pol); > > int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp); > > diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c > > index 81ff676f209a..bbd35b35b79d 100644 > > --- a/security/selinux/ss/conditional.c > > +++ b/security/selinux/ss/conditional.c > > @@ -140,7 +140,7 @@ void cond_policydb_init(struct policydb *p) > > static void cond_node_destroy(struct cond_node *node) > > { > > kfree(node->expr.nodes); > > - /* the avtab_ptr_t nodes are destroyed by the avtab */ > > + /* the actual nodes were destroyed by avtab_destroy() */ > > kfree(node->true_list.nodes); > > kfree(node->false_list.nodes); > > } > > @@ -323,7 +323,8 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k, > > > > static int cond_read_av_list(struct policydb *p, void *fp, > > struct cond_av_list *list, > > - struct cond_av_list *other) > > + struct cond_av_list *other, > > + u32 *nrules) > > { > > int rc; > > __le32 buf[1]; > > @@ -347,7 +348,7 @@ static int cond_read_av_list(struct policydb *p, void *fp, > > for (i = 0; i < len; i++) { > > data.dst = &list->nodes[i]; > > rc = avtab_read_item(&p->te_cond_avtab, fp, p, cond_insertf, > > - &data); > > + &data, nrules); > > if (rc) { > > kfree(list->nodes); > > list->nodes = NULL; > > @@ -373,7 +374,8 @@ static int expr_node_isvalid(struct policydb *p, struct cond_expr_node *expr) > > return 1; > > } > > > > -static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp) > > +static int cond_read_node(struct policydb *p, struct cond_node *node, > > + void *fp, u32 *nrules) > > { > > __le32 buf[2]; > > u32 i, len; > > @@ -407,16 +409,17 @@ static int cond_read_node(struct policydb *p, struct cond_node *node, void *fp) > > return -EINVAL; > > } > > > > - rc = cond_read_av_list(p, fp, &node->true_list, NULL); > > + rc = cond_read_av_list(p, fp, &node->true_list, NULL, nrules); > > if (rc) > > return rc; > > - return cond_read_av_list(p, fp, &node->false_list, &node->true_list); > > + return cond_read_av_list(p, fp, &node->false_list, &node->true_list, nrules); > > } > > > > -int cond_read_list(struct policydb *p, void *fp) > > +int cond_read_list(struct policydb *p, struct policy_file *fp) > > { > > __le32 buf[1]; > > - u32 i, len; > > + struct policy_file tmp_fp; > > + u32 i, len, nrules; > > int rc; > > > > rc = next_entry(buf, fp, sizeof(buf)); > > @@ -428,15 +431,25 @@ int cond_read_list(struct policydb *p, void *fp) > > p->cond_list = kcalloc(len, sizeof(*p->cond_list), GFP_KERNEL); > > if (!p->cond_list) > > return -ENOMEM; > > + p->cond_list_len = len; > > + > > + /* first pass to only calculate the avrule count */ > > + tmp_fp = *fp; > > + nrules = 0; > > + for (i = 0; i < len; i++) { > > + rc = cond_read_node(p, &p->cond_list[i], &tmp_fp, &nrules); > > + if (rc) > > + goto err; > > + cond_node_destroy(&p->cond_list[i]); > > + } > > > > - rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel); > > + rc = avtab_alloc(&(p->te_cond_avtab), nrules); > > if (rc) > > goto err; > > > > - p->cond_list_len = len; > > - > > + /* second pass to read in the conditional nodes */ > > for (i = 0; i < len; i++) { > > - rc = cond_read_node(p, &p->cond_list[i], fp); > > + rc = cond_read_node(p, &p->cond_list[i], fp, NULL); > > if (rc) > > goto err; > > } > > diff --git a/security/selinux/ss/conditional.h b/security/selinux/ss/conditional.h > > index 5a7b51278dc6..62a12d00cac9 100644 > > --- a/security/selinux/ss/conditional.h > > +++ b/security/selinux/ss/conditional.h > > @@ -70,7 +70,7 @@ int cond_destroy_bool(void *key, void *datum, void *p); > > int cond_index_bool(void *key, void *datum, void *datap); > > > > int cond_read_bool(struct policydb *p, struct symtab *s, void *fp); > > -int cond_read_list(struct policydb *p, void *fp); > > +int cond_read_list(struct policydb *p, struct policy_file *fp); > > int cond_write_bool(void *key, void *datum, void *ptr); > > int cond_write_list(struct policydb *p, void *fp); > > > > -- > > 2.41.0 > >