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
> >
