| Message ID | 20200406163556.997001-1-omosnace@redhat.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | selinux: store role transitions in a hash table | expand |
On Mon, Apr 6, 2020 at 6:35 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 -t 30 > --metrics-brief --msg 0' under perf with and without this patch. > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > --- > 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 > @@ -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..3cb8ec7b09a3 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 = scontext->type, I just spotted a copy-paste bug here - the type should come from tcontext, not scontext... Will send a fixed version tomorrow. > + .tclass = tclass, > + }; > + > + rtd = hashtab_search(policydb->role_tr, &rtk); > + if (rtd) > + newcontext.role = rtd->new_role; > } > > /* Set the MLS attributes. > -- > 2.25.1 >
On Mon, Apr 6, 2020 at 3:42 PM Ondrej Mosnacek <omosnace@redhat.com> wrote: > On Mon, Apr 6, 2020 at 6:35 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 -t 30 > > --metrics-brief --msg 0' under perf with and without this patch. > > > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > > --- > > 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(-) ... > I just spotted a copy-paste bug here - the type should come from > tcontext, not scontext... Will send a fixed version tomorrow. No rush, while we can obviously review it at any point in time, the earliest it could be merged would be next week (assuming the merge window closes this Sunday).
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..3cb8ec7b09a3 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 = scontext->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 -t 30 --metrics-brief --msg 0' under perf with and without this patch. Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> --- 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(-)