On Wed, Feb 12, 2020 at 6:23 AM Ondrej Mosnacek <omosnace@xxxxxxxxxx> wrote: > > In these rules, each rule with the same (target type, target class, > filename) values is (in practice) always mapped to the same result type. > Therefore, it is much more efficient to group the rules by (ttype, > tclass, filename). > > Thus, this patch drops the stype field from the key and changes the > datum to be a linked list of one or more structures that contain a > result type and an ebitmap of source types that map the given target to > the given result type under the given filename. The size of the hash > table is also incremented to 2048 to be more optimal for Fedora policy > (which currently has ~2500 unique (ttype, tclass, filename) tuples, > regardless of whether the 'unconfined' module is enabled). > > Not only does this dramtically reduce memory usage when the policy > contains a lot of unconfined domains (ergo a lot of filename based > transitions), but it also slightly reduces memory usage of strongly > confined policies (modeled on Fedora policy with 'unconfined' module > disabled) and significantly reduces lookup times of these rules on > Fedora (roughly matches the performance of the rhashtable conversion > patch [1] posted recently to selinux@xxxxxxxxxxxxxxx). > > An obvious next step is to change binary policy format to match this > layout, so that disk space is also saved. However, since that requires > more work (including matching userspace changes) and this patch is > already beneficial on its own, I'm posting it separately. > > Performance/memory usage comparison: > > Kernel | Policy load | Policy load | Mem usage | Mem usage | openbench > | | (-unconfined) | | (-unconfined) | (createfiles) > -----------------|-------------|---------------|-----------|---------------|-------------- > reference | 1,30s | 0,91s | 90MB | 77MB | 55 us/file > rhashtable patch | 0.98s | 0,85s | 85MB | 75MB | 38 us/file > this patch | 0,95s | 0,87s | 75MB | 75MB | 40 us/file > > (Memory usage is measured after boot. With SELinux disabled the memory > usage was ~60MB on the same system.) > > [1] https://lore.kernel.org/selinux/20200116213937.77795-1-dev@xxxxxxxxxx/T/ > > Signed-off-by: Ondrej Mosnacek <omosnace@xxxxxxxxxx> > --- > security/selinux/ss/policydb.c | 173 ++++++++++++++++++++------------- > security/selinux/ss/policydb.h | 8 +- > security/selinux/ss/services.c | 16 +-- > 3 files changed, 118 insertions(+), 79 deletions(-) ... > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c > index 981797bfc547..d8b72718e793 100644 > --- a/security/selinux/ss/policydb.c > +++ b/security/selinux/ss/policydb.c > @@ -1882,64 +1884,91 @@ out: > > static int filename_trans_read_one(struct policydb *p, void *fp) > { > - struct filename_trans *ft; > - struct filename_trans_datum *otype = NULL; > + struct filename_trans_key key, *ft = NULL; > + struct filename_trans_datum *datum, *last, *newdatum = NULL; > + uintptr_t stype, otype; > char *name = NULL; > u32 len; > __le32 buf[4]; > int rc; > - > - ft = kzalloc(sizeof(*ft), GFP_KERNEL); > - if (!ft) > - return -ENOMEM; > - > - rc = -ENOMEM; > - otype = kmalloc(sizeof(*otype), GFP_KERNEL); > - if (!otype) > - goto out; > + bool already_there; > > /* length of the path component string */ > rc = next_entry(buf, fp, sizeof(u32)); > if (rc) > - goto out; > + return rc; > len = le32_to_cpu(buf[0]); > > /* path component string */ > rc = str_read(&name, GFP_KERNEL, fp, len); > if (rc) > - goto out; > - > - ft->name = name; > + return rc; > > rc = next_entry(buf, fp, sizeof(u32) * 4); > if (rc) > goto out; > > - ft->stype = le32_to_cpu(buf[0]); > - ft->ttype = le32_to_cpu(buf[1]); > - ft->tclass = le32_to_cpu(buf[2]); > + stype = le32_to_cpu(buf[0]); > + key.ttype = le32_to_cpu(buf[1]); > + key.tclass = le32_to_cpu(buf[2]); > + key.name = name; We don't really need the "name" variable anymore do we, we can just use "key.name" instead, right? > > - otype->otype = le32_to_cpu(buf[3]); > + otype = le32_to_cpu(buf[3]); > > - rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1); > - if (rc) > - goto out; > + already_there = false; > + last = NULL; > + datum = hashtab_search(p->filename_trans, &key); > + while (datum) { > + if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) { > + already_there = true; > + break; Considering the "already_there" check below simply jumps to "out", why do we need to add the "already_there" variable, can't we simply jump to the "out" label here? Am I missing something? > + } > + if (likely(datum->otype == otype)) > + break; > + last = datum; > + datum = datum->next; > + } > + if (unlikely(already_there)) > + goto out; /* conflicting/duplicate rules are ignored */ > + if (!datum) { > + rc = -ENOMEM; > + newdatum = kmalloc(sizeof(*newdatum), GFP_KERNEL); > + if (!newdatum) > + goto out; By definition "datum" will be NULL here so we can get rid of "newdatum" and just reuse "datum", yes? I think the only place where we would have to worry about the kfree(datum) in the "out" jump label would be in this (!datum) if block which should be okay ... > - rc = hashtab_insert(p->filename_trans, ft, otype); > - if (rc) { > - /* > - * Do not return -EEXIST to the caller, or the system > - * will not boot. > - */ > - if (rc == -EEXIST) > - rc = 0; > - goto out; > + ebitmap_init(&newdatum->stypes); > + newdatum->otype = otype; > + newdatum->next = NULL; > + > + if (unlikely(last)) { > + last->next = newdatum; > + } else { > + rc = -ENOMEM; > + ft = kzalloc(sizeof(*ft), GFP_KERNEL); > + if (!ft) > + goto out; > + > + *ft = key; Off the top of my head I don't know the answer to this, and I worry it may fall into the category of "undefined behavior", but if we are assigning an entire struct to another dynamically allocated variable using "=" is the kzalloc() necessary? Could we save ourselves a few cycles and safely use kmalloc() for "ft"? > + rc = hashtab_insert(p->filename_trans, ft, newdatum); > + if (rc) > + goto out; > + name = NULL; > + > + rc = ebitmap_set_bit(&p->filename_trans_ttypes, > + key.ttype, 1); > + if (rc) > + return rc; > + } > + datum = newdatum; > } > - return 0; > + kfree(name); > + return ebitmap_set_bit(&datum->stypes, stype - 1, 1); > + > out: > kfree(ft); > kfree(name); > - kfree(otype); > + kfree(newdatum); > return rc; > } -- paul moore www.paul-moore.com
