| Message ID | 20200407182858.1149087-1-omosnace@redhat.com (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [v2] selinux: store role transitions in a hash table | expand |
On Tue, Apr 7, 2020 at 2:29 PM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > Currently, they are stored in a linked list, which adds significant > overhead to security_transition_sid(). On Fedora, with 428 role > transitions in policy, converting this list to a hash table cuts down > its run time by about 50%. This was measured by running 'stress-ng --msg > 1 --msg-ops 100000' under perf with and without this patch. > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > --- > > v2: > - fix typo scontext->tcontext in security_compute_sid() > - suggest a better command for testing in the commit msg > > security/selinux/ss/policydb.c | 138 ++++++++++++++++++++++----------- > security/selinux/ss/policydb.h | 8 +- > security/selinux/ss/services.c | 21 +++-- > 3 files changed, 107 insertions(+), 60 deletions(-) ... > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c > index 70ecdc78efbd..4f0cfffd008d 100644 > --- a/security/selinux/ss/policydb.c > +++ b/security/selinux/ss/policydb.c > @@ -458,6 +465,30 @@ static int rangetr_cmp(struct hashtab *h, const void *k1, const void *k2) > return v; > } > > +static u32 role_trans_hash(struct hashtab *h, const void *k) > +{ > + const struct role_trans_key *key = k; > + > + return (key->role + (key->type << 3) + (key->tclass << 5)) & > + (h->size - 1); > +} > + > +static int role_trans_cmp(struct hashtab *h, const void *k1, const void *k2) > +{ > + const struct role_trans_key *key1 = k1, *key2 = k2; > + int v; > + > + v = key1->role - key2->role; > + if (v) > + return v; > + > + v = key1->type - key2->type; > + if (v) > + return v; > + > + return key1->tclass - key2->tclass; Why just a simple boolean statement? return key1->role != key2->role || \ key1->type != key2->type || \ key1->tclass != key2->tclass;
On Thu, Apr 16, 2020 at 3:41 AM Paul Moore <paul@paul-moore.com> wrote: > On Tue, Apr 7, 2020 at 2:29 PM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > Currently, they are stored in a linked list, which adds significant > > overhead to security_transition_sid(). On Fedora, with 428 role > > transitions in policy, converting this list to a hash table cuts down > > its run time by about 50%. This was measured by running 'stress-ng --msg > > 1 --msg-ops 100000' under perf with and without this patch. > > > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > > --- > > > > v2: > > - fix typo scontext->tcontext in security_compute_sid() > > - suggest a better command for testing in the commit msg > > > > security/selinux/ss/policydb.c | 138 ++++++++++++++++++++++----------- > > security/selinux/ss/policydb.h | 8 +- > > security/selinux/ss/services.c | 21 +++-- > > 3 files changed, 107 insertions(+), 60 deletions(-) > > ... > > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c > > index 70ecdc78efbd..4f0cfffd008d 100644 > > --- a/security/selinux/ss/policydb.c > > +++ b/security/selinux/ss/policydb.c > > @@ -458,6 +465,30 @@ static int rangetr_cmp(struct hashtab *h, const void *k1, const void *k2) > > return v; > > } > > > > +static u32 role_trans_hash(struct hashtab *h, const void *k) > > +{ > > + const struct role_trans_key *key = k; > > + > > + return (key->role + (key->type << 3) + (key->tclass << 5)) & > > + (h->size - 1); > > +} > > + > > +static int role_trans_cmp(struct hashtab *h, const void *k1, const void *k2) > > +{ > > + const struct role_trans_key *key1 = k1, *key2 = k2; > > + int v; > > + > > + v = key1->role - key2->role; > > + if (v) > > + return v; > > + > > + v = key1->type - key2->type; > > + if (v) > > + return v; > > + > > + return key1->tclass - key2->tclass; > > Why just a simple boolean statement? > > return key1->role != key2->role || \ > key1->type != key2->type || \ > key1->tclass != key2->tclass; Because hashtab sorts the entries in each bucket, so it needs a proper sort function. Other such functions (rangetr_cmp(), filenametr_cmp()) do a similar thing. -- Ondrej Mosnacek <omosnace at redhat dot com> Software Engineer, Security Technologies Red Hat, Inc.
On Thu, Apr 16, 2020 at 5:51 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > On Thu, Apr 16, 2020 at 3:41 AM Paul Moore <paul@paul-moore.com> wrote: > > On Tue, Apr 7, 2020 at 2:29 PM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > > > Currently, they are stored in a linked list, which adds significant > > > overhead to security_transition_sid(). On Fedora, with 428 role > > > transitions in policy, converting this list to a hash table cuts down > > > its run time by about 50%. This was measured by running 'stress-ng --msg > > > 1 --msg-ops 100000' under perf with and without this patch. > > > > > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > > > --- > > > > > > v2: > > > - fix typo scontext->tcontext in security_compute_sid() > > > - suggest a better command for testing in the commit msg > > > > > > security/selinux/ss/policydb.c | 138 ++++++++++++++++++++++----------- > > > security/selinux/ss/policydb.h | 8 +- > > > security/selinux/ss/services.c | 21 +++-- > > > 3 files changed, 107 insertions(+), 60 deletions(-) > > > > ... > > > > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c > > > index 70ecdc78efbd..4f0cfffd008d 100644 > > > --- a/security/selinux/ss/policydb.c > > > +++ b/security/selinux/ss/policydb.c > > > @@ -458,6 +465,30 @@ static int rangetr_cmp(struct hashtab *h, const void *k1, const void *k2) > > > return v; > > > } > > > > > > +static u32 role_trans_hash(struct hashtab *h, const void *k) > > > +{ > > > + const struct role_trans_key *key = k; > > > + > > > + return (key->role + (key->type << 3) + (key->tclass << 5)) & > > > + (h->size - 1); > > > +} > > > + > > > +static int role_trans_cmp(struct hashtab *h, const void *k1, const void *k2) > > > +{ > > > + const struct role_trans_key *key1 = k1, *key2 = k2; > > > + int v; > > > + > > > + v = key1->role - key2->role; > > > + if (v) > > > + return v; > > > + > > > + v = key1->type - key2->type; > > > + if (v) > > > + return v; > > > + > > > + return key1->tclass - key2->tclass; > > > > Why just a simple boolean statement? > > > > return key1->role != key2->role || \ > > key1->type != key2->type || \ > > key1->tclass != key2->tclass; > > Because hashtab sorts the entries in each bucket, so it needs a proper > sort function. Other such functions (rangetr_cmp(), filenametr_cmp()) > do a similar thing. Ooops, yep, of course you're correct. Sorry about the noise :) I'll send a note later today when it's merged, but this looks good to me.
On Thu, Apr 16, 2020 at 9:20 AM Paul Moore <paul@paul-moore.com> wrote: > On Thu, Apr 16, 2020 at 5:51 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > On Thu, Apr 16, 2020 at 3:41 AM Paul Moore <paul@paul-moore.com> wrote: > > > On Tue, Apr 7, 2020 at 2:29 PM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > > > > > > > Currently, they are stored in a linked list, which adds significant > > > > overhead to security_transition_sid(). On Fedora, with 428 role > > > > transitions in policy, converting this list to a hash table cuts down > > > > its run time by about 50%. This was measured by running 'stress-ng --msg > > > > 1 --msg-ops 100000' under perf with and without this patch. > > > > > > > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > > > > --- > > > > > > > > v2: > > > > - fix typo scontext->tcontext in security_compute_sid() > > > > - suggest a better command for testing in the commit msg > > > > > > > > security/selinux/ss/policydb.c | 138 ++++++++++++++++++++++----------- > > > > security/selinux/ss/policydb.h | 8 +- > > > > security/selinux/ss/services.c | 21 +++-- > > > > 3 files changed, 107 insertions(+), 60 deletions(-) > > > > > > ... > > > > > > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c > > > > index 70ecdc78efbd..4f0cfffd008d 100644 > > > > --- a/security/selinux/ss/policydb.c > > > > +++ b/security/selinux/ss/policydb.c > > > > @@ -458,6 +465,30 @@ static int rangetr_cmp(struct hashtab *h, const void *k1, const void *k2) > > > > return v; > > > > } > > > > > > > > +static u32 role_trans_hash(struct hashtab *h, const void *k) > > > > +{ > > > > + const struct role_trans_key *key = k; > > > > + > > > > + return (key->role + (key->type << 3) + (key->tclass << 5)) & > > > > + (h->size - 1); > > > > +} > > > > + > > > > +static int role_trans_cmp(struct hashtab *h, const void *k1, const void *k2) > > > > +{ > > > > + const struct role_trans_key *key1 = k1, *key2 = k2; > > > > + int v; > > > > + > > > > + v = key1->role - key2->role; > > > > + if (v) > > > > + return v; > > > > + > > > > + v = key1->type - key2->type; > > > > + if (v) > > > > + return v; > > > > + > > > > + return key1->tclass - key2->tclass; > > > > > > Why just a simple boolean statement? > > > > > > return key1->role != key2->role || \ > > > key1->type != key2->type || \ > > > key1->tclass != key2->tclass; > > > > Because hashtab sorts the entries in each bucket, so it needs a proper > > sort function. Other such functions (rangetr_cmp(), filenametr_cmp()) > > do a similar thing. > > Ooops, yep, of course you're correct. Sorry about the noise :) > > I'll send a note later today when it's merged, but this looks good to me. A day later than expected, but I just merged this into selinux/next, thanks.
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c index 70ecdc78efbd..4f0cfffd008d 100644 --- a/security/selinux/ss/policydb.c +++ b/security/selinux/ss/policydb.c @@ -352,6 +352,13 @@ static int range_tr_destroy(void *key, void *datum, void *p) return 0; } +static int role_tr_destroy(void *key, void *datum, void *p) +{ + kfree(key); + kfree(datum); + return 0; +} + static void ocontext_destroy(struct ocontext *c, int i) { if (!c) @@ -458,6 +465,30 @@ static int rangetr_cmp(struct hashtab *h, const void *k1, const void *k2) return v; } +static u32 role_trans_hash(struct hashtab *h, const void *k) +{ + const struct role_trans_key *key = k; + + return (key->role + (key->type << 3) + (key->tclass << 5)) & + (h->size - 1); +} + +static int role_trans_cmp(struct hashtab *h, const void *k1, const void *k2) +{ + const struct role_trans_key *key1 = k1, *key2 = k2; + int v; + + v = key1->role - key2->role; + if (v) + return v; + + v = key1->type - key2->type; + if (v) + return v; + + return key1->tclass - key2->tclass; +} + /* * Initialize a policy database structure. */ @@ -728,7 +759,6 @@ void policydb_destroy(struct policydb *p) struct genfs *g, *gtmp; int i; struct role_allow *ra, *lra = NULL; - struct role_trans *tr, *ltr = NULL; for (i = 0; i < SYM_NUM; i++) { cond_resched(); @@ -775,12 +805,8 @@ void policydb_destroy(struct policydb *p) cond_policydb_destroy(p); - for (tr = p->role_tr; tr; tr = tr->next) { - cond_resched(); - kfree(ltr); - ltr = tr; - } - kfree(ltr); + hashtab_map(p->role_tr, role_tr_destroy, NULL); + hashtab_destroy(p->role_tr); for (ra = p->role_allow; ra; ra = ra->next) { cond_resched(); @@ -2251,7 +2277,8 @@ out: int policydb_read(struct policydb *p, void *fp) { struct role_allow *ra, *lra; - struct role_trans *tr, *ltr; + struct role_trans_key *rtk = NULL; + struct role_trans_datum *rtd = NULL; int i, j, rc; __le32 buf[4]; u32 len, nprim, nel; @@ -2416,39 +2443,50 @@ int policydb_read(struct policydb *p, void *fp) if (rc) goto bad; nel = le32_to_cpu(buf[0]); - ltr = NULL; + + p->role_tr = hashtab_create(role_trans_hash, role_trans_cmp, nel); + if (!p->role_tr) + goto bad; for (i = 0; i < nel; i++) { rc = -ENOMEM; - tr = kzalloc(sizeof(*tr), GFP_KERNEL); - if (!tr) + rtk = kmalloc(sizeof(*rtk), GFP_KERNEL); + if (!rtk) goto bad; - if (ltr) - ltr->next = tr; - else - p->role_tr = tr; + + rc = -ENOMEM; + rtd = kmalloc(sizeof(*rtd), GFP_KERNEL); + if (!rtd) + goto bad; + rc = next_entry(buf, fp, sizeof(u32)*3); if (rc) goto bad; rc = -EINVAL; - tr->role = le32_to_cpu(buf[0]); - tr->type = le32_to_cpu(buf[1]); - tr->new_role = le32_to_cpu(buf[2]); + rtk->role = le32_to_cpu(buf[0]); + rtk->type = le32_to_cpu(buf[1]); + rtd->new_role = le32_to_cpu(buf[2]); if (p->policyvers >= POLICYDB_VERSION_ROLETRANS) { rc = next_entry(buf, fp, sizeof(u32)); if (rc) goto bad; - tr->tclass = le32_to_cpu(buf[0]); + rtk->tclass = le32_to_cpu(buf[0]); } else - tr->tclass = p->process_class; + rtk->tclass = p->process_class; rc = -EINVAL; - if (!policydb_role_isvalid(p, tr->role) || - !policydb_type_isvalid(p, tr->type) || - !policydb_class_isvalid(p, tr->tclass) || - !policydb_role_isvalid(p, tr->new_role)) + if (!policydb_role_isvalid(p, rtk->role) || + !policydb_type_isvalid(p, rtk->type) || + !policydb_class_isvalid(p, rtk->tclass) || + !policydb_role_isvalid(p, rtd->new_role)) + goto bad; + + rc = hashtab_insert(p->role_tr, rtk, rtd); + if (rc) goto bad; - ltr = tr; + + rtk = NULL; + rtd = NULL; } rc = next_entry(buf, fp, sizeof(u32)); @@ -2536,6 +2574,8 @@ int policydb_read(struct policydb *p, void *fp) out: return rc; bad: + kfree(rtk); + kfree(rtd); policydb_destroy(p); goto out; } @@ -2653,39 +2693,45 @@ static int cat_write(void *vkey, void *datum, void *ptr) return 0; } -static int role_trans_write(struct policydb *p, void *fp) +static int role_trans_write_one(void *key, void *datum, void *ptr) { - struct role_trans *r = p->role_tr; - struct role_trans *tr; + struct role_trans_key *rtk = key; + struct role_trans_datum *rtd = datum; + struct policy_data *pd = ptr; + void *fp = pd->fp; + struct policydb *p = pd->p; __le32 buf[3]; - size_t nel; int rc; - nel = 0; - for (tr = r; tr; tr = tr->next) - nel++; - buf[0] = cpu_to_le32(nel); - rc = put_entry(buf, sizeof(u32), 1, fp); + buf[0] = cpu_to_le32(rtk->role); + buf[1] = cpu_to_le32(rtk->type); + buf[2] = cpu_to_le32(rtd->new_role); + rc = put_entry(buf, sizeof(u32), 3, fp); if (rc) return rc; - for (tr = r; tr; tr = tr->next) { - buf[0] = cpu_to_le32(tr->role); - buf[1] = cpu_to_le32(tr->type); - buf[2] = cpu_to_le32(tr->new_role); - rc = put_entry(buf, sizeof(u32), 3, fp); + if (p->policyvers >= POLICYDB_VERSION_ROLETRANS) { + buf[0] = cpu_to_le32(rtk->tclass); + rc = put_entry(buf, sizeof(u32), 1, fp); if (rc) return rc; - if (p->policyvers >= POLICYDB_VERSION_ROLETRANS) { - buf[0] = cpu_to_le32(tr->tclass); - rc = put_entry(buf, sizeof(u32), 1, fp); - if (rc) - return rc; - } } - return 0; } +static int role_trans_write(struct policydb *p, void *fp) +{ + struct policy_data pd = { .p = p, .fp = fp }; + __le32 buf[1]; + int rc; + + buf[0] = cpu_to_le32(p->role_tr->nel); + rc = put_entry(buf, sizeof(u32), 1, fp); + if (rc) + return rc; + + return hashtab_map(p->role_tr, role_trans_write_one, &pd); +} + static int role_allow_write(struct role_allow *r, void *fp) { struct role_allow *ra; diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h index 72e2932fb12d..d3adb522d3f3 100644 --- a/security/selinux/ss/policydb.h +++ b/security/selinux/ss/policydb.h @@ -81,12 +81,14 @@ struct role_datum { struct ebitmap types; /* set of authorized types for role */ }; -struct role_trans { +struct role_trans_key { u32 role; /* current role */ u32 type; /* program executable type, or new object type */ u32 tclass; /* process class, or new object class */ +}; + +struct role_trans_datum { u32 new_role; /* new role */ - struct role_trans *next; }; struct filename_trans_key { @@ -261,7 +263,7 @@ struct policydb { struct avtab te_avtab; /* role transitions */ - struct role_trans *role_tr; + struct hashtab *role_tr; /* file transitions with the last path component */ /* quickly exclude lookups when parent ttype has no rules */ diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c index 8ad34fd031d1..1252d8fa2038 100644 --- a/security/selinux/ss/services.c +++ b/security/selinux/ss/services.c @@ -1731,7 +1731,6 @@ static int security_compute_sid(struct selinux_state *state, struct class_datum *cladatum = NULL; struct context *scontext, *tcontext, newcontext; struct sidtab_entry *sentry, *tentry; - struct role_trans *roletr = NULL; struct avtab_key avkey; struct avtab_datum *avdatum; struct avtab_node *node; @@ -1864,16 +1863,16 @@ static int security_compute_sid(struct selinux_state *state, /* Check for class-specific changes. */ if (specified & AVTAB_TRANSITION) { /* Look for a role transition rule. */ - for (roletr = policydb->role_tr; roletr; - roletr = roletr->next) { - if ((roletr->role == scontext->role) && - (roletr->type == tcontext->type) && - (roletr->tclass == tclass)) { - /* Use the role transition rule. */ - newcontext.role = roletr->new_role; - break; - } - } + struct role_trans_datum *rtd; + struct role_trans_key rtk = { + .role = scontext->role, + .type = tcontext->type, + .tclass = tclass, + }; + + rtd = hashtab_search(policydb->role_tr, &rtk); + if (rtd) + newcontext.role = rtd->new_role; } /* Set the MLS attributes.
Currently, they are stored in a linked list, which adds significant overhead to security_transition_sid(). On Fedora, with 428 role transitions in policy, converting this list to a hash table cuts down its run time by about 50%. This was measured by running 'stress-ng --msg 1 --msg-ops 100000' under perf with and without this patch. Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> --- v2: - fix typo scontext->tcontext in security_compute_sid() - suggest a better command for testing in the commit msg security/selinux/ss/policydb.c | 138 ++++++++++++++++++++++----------- security/selinux/ss/policydb.h | 8 +- security/selinux/ss/services.c | 21 +++-- 3 files changed, 107 insertions(+), 60 deletions(-)