* [PATCH v2] selinux: store role transitions in a hash table
@ 2020-04-07 18:28 Ondrej Mosnacek
2020-04-16 1:40 ` Paul Moore
0 siblings, 1 reply; 5+ messages in thread
From: Ondrej Mosnacek @ 2020-04-07 18:28 UTC (permalink / raw)
To: selinux, Paul Moore; +Cc: Stephen Smalley
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
@@ -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.
--
2.25.2
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v2] selinux: store role transitions in a hash table
2020-04-07 18:28 [PATCH v2] selinux: store role transitions in a hash table Ondrej Mosnacek
@ 2020-04-16 1:40 ` Paul Moore
2020-04-16 9:51 ` Ondrej Mosnacek
0 siblings, 1 reply; 5+ messages in thread
From: Paul Moore @ 2020-04-16 1:40 UTC (permalink / raw)
To: Ondrej Mosnacek; +Cc: selinux, Stephen Smalley
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;
--
paul moore
www.paul-moore.com
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2] selinux: store role transitions in a hash table
2020-04-16 1:40 ` Paul Moore
@ 2020-04-16 9:51 ` Ondrej Mosnacek
2020-04-16 13:20 ` Paul Moore
0 siblings, 1 reply; 5+ messages in thread
From: Ondrej Mosnacek @ 2020-04-16 9:51 UTC (permalink / raw)
To: Paul Moore; +Cc: SElinux list, Stephen Smalley
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.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2] selinux: store role transitions in a hash table
2020-04-16 9:51 ` Ondrej Mosnacek
@ 2020-04-16 13:20 ` Paul Moore
2020-04-17 19:22 ` Paul Moore
0 siblings, 1 reply; 5+ messages in thread
From: Paul Moore @ 2020-04-16 13:20 UTC (permalink / raw)
To: Ondrej Mosnacek; +Cc: SElinux list, Stephen Smalley
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.
--
paul moore
www.paul-moore.com
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2] selinux: store role transitions in a hash table
2020-04-16 13:20 ` Paul Moore
@ 2020-04-17 19:22 ` Paul Moore
0 siblings, 0 replies; 5+ messages in thread
From: Paul Moore @ 2020-04-17 19:22 UTC (permalink / raw)
To: Ondrej Mosnacek; +Cc: SElinux list, Stephen Smalley
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.
--
paul moore
www.paul-moore.com
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2020-04-17 19:23 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-04-07 18:28 [PATCH v2] selinux: store role transitions in a hash table Ondrej Mosnacek
2020-04-16 1:40 ` Paul Moore
2020-04-16 9:51 ` Ondrej Mosnacek
2020-04-16 13:20 ` Paul Moore
2020-04-17 19:22 ` Paul Moore
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).