| Message ID | 20200417081157.606789-2-omosnace@redhat.com (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
| Series | Hash context structures directly | expand |
On Fri, Apr 17, 2020 at 10:12 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > Always hashing the string representation is inefficient. Just hash the > contents of the structure directly (using jhash). If the context is > invalid (str & len are set), then hash the string as before, otherwise > hash the structured data. > > Since the context hashing function is now faster (about 10 times), this > patch decreases the overhead of security_transition_sid(), which is > called from many hooks. > > The jhash function seemed as a good choice, since it is used as the > default hashing algorithm in rhashtable. Testing this on Android (Pixel 3) confirms this as well. Before: blueline:/ # cat /sys/fs/selinux/ss/sidtab_hash_stats entries: 1900 buckets used: 454/512 longest chain: 10 After: blueline:/ # cat /sys/fs/selinux/ss/sidtab_hash_stats entries: 1971 buckets used: 458/512 longest chain: 10 > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > --- > security/selinux/Makefile | 2 +- > security/selinux/ss/context.c | 32 +++++++++++++++++++++++++++++++ > security/selinux/ss/context.h | 6 ++++-- > security/selinux/ss/ebitmap.c | 14 ++++++++++++++ > security/selinux/ss/ebitmap.h | 1 + > security/selinux/ss/mls.h | 11 +++++++++++ > security/selinux/ss/policydb.c | 7 ++----- > security/selinux/ss/services.c | 35 ++++------------------------------ > security/selinux/ss/services.h | 3 --- > 9 files changed, 69 insertions(+), 42 deletions(-) > create mode 100644 security/selinux/ss/context.c > > diff --git a/security/selinux/Makefile b/security/selinux/Makefile > index 0c77ede1cc11..4d8e0e8adf0b 100644 > --- a/security/selinux/Makefile > +++ b/security/selinux/Makefile > @@ -8,7 +8,7 @@ obj-$(CONFIG_SECURITY_SELINUX) := selinux.o > selinux-y := avc.o hooks.o selinuxfs.o netlink.o nlmsgtab.o netif.o \ > netnode.o netport.o status.o \ > ss/ebitmap.o ss/hashtab.o ss/symtab.o ss/sidtab.o ss/avtab.o \ > - ss/policydb.o ss/services.o ss/conditional.o ss/mls.o > + ss/policydb.o ss/services.o ss/conditional.o ss/mls.o ss/context.o > > selinux-$(CONFIG_SECURITY_NETWORK_XFRM) += xfrm.o > > diff --git a/security/selinux/ss/context.c b/security/selinux/ss/context.c > new file mode 100644 > index 000000000000..fac6f92b3e99 > --- /dev/null > +++ b/security/selinux/ss/context.c > @@ -0,0 +1,32 @@ > +// SPDX-License-Identifier: GPL-2.0 > +/* > + * Implementations of the security context functions. > + * > + * Author: Ondrej Mosnacek <omosnacek@gmail.com> > + * Copyright (C) 2020 Red Hat, Inc. > + */ > + > +#include <linux/jhash.h> > + > +#include "context.h" > +#include "mls.h" > + > +u32 context_compute_hash(const struct context *c) > +{ > + u32 hash = 0; > + > + /* > + * If a context is invalid, it will always be represented by a > + * context struct with only the len & str set (and vice versa) > + * under a given policy. Since context structs from different > + * policies should never meet, it is safe to hash valid and > + * invalid contexts differently. The context_cmp() function > + * already opearates under the same assumption. operates > + */ > + if (c->len) > + return full_name_hash(NULL, c->str, c->len); > + > + hash = jhash_3words(c->user, c->role, c->type, hash); > + hash = mls_range_hash(&c->range, hash); > + return hash; > +} > diff --git a/security/selinux/ss/context.h b/security/selinux/ss/context.h > index 3ba044fe02ed..e7ae7e21449b 100644 > --- a/security/selinux/ss/context.h > +++ b/security/selinux/ss/context.h > @@ -196,9 +196,11 @@ static inline int context_cmp(struct context *c1, struct context *c2) > mls_context_cmp(c1, c2)); > } > > -static inline unsigned int context_compute_hash(const char *s) > +u32 context_compute_hash(const struct context *c); > + > +static inline void context_add_hash(struct context *context) > { > - return full_name_hash(NULL, s, strlen(s)); > + context->hash = context_compute_hash(context); > } > > #endif /* _SS_CONTEXT_H_ */ > diff --git a/security/selinux/ss/ebitmap.c b/security/selinux/ss/ebitmap.c > index c8c3663111e2..14bedc95c6dc 100644 > --- a/security/selinux/ss/ebitmap.c > +++ b/security/selinux/ss/ebitmap.c > @@ -19,6 +19,7 @@ > #include <linux/kernel.h> > #include <linux/slab.h> > #include <linux/errno.h> > +#include <linux/jhash.h> > #include <net/netlabel.h> > #include "ebitmap.h" > #include "policydb.h" > @@ -542,6 +543,19 @@ int ebitmap_write(struct ebitmap *e, void *fp) > return 0; > } > > +u32 ebitmap_hash(const struct ebitmap *e, u32 hash) > +{ > + struct ebitmap_node *node; > + > + /* need to change hash even if ebitmap is empty */ > + hash = jhash_1word(e->highbit, hash); > + for (node = e->node; node; node = node->next) { > + hash = jhash_1word(node->startbit, hash); > + hash = jhash(node->maps, sizeof(node->maps), hash); > + } > + return hash; > +} > + > void __init ebitmap_cache_init(void) > { > ebitmap_node_cachep = kmem_cache_create("ebitmap_node", > diff --git a/security/selinux/ss/ebitmap.h b/security/selinux/ss/ebitmap.h > index 9a23b81b8832..9eb2d0af2805 100644 > --- a/security/selinux/ss/ebitmap.h > +++ b/security/selinux/ss/ebitmap.h > @@ -131,6 +131,7 @@ int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value); > void ebitmap_destroy(struct ebitmap *e); > int ebitmap_read(struct ebitmap *e, void *fp); > int ebitmap_write(struct ebitmap *e, void *fp); > +u32 ebitmap_hash(const struct ebitmap *e, u32 hash); > > #ifdef CONFIG_NETLABEL > int ebitmap_netlbl_export(struct ebitmap *ebmap, > diff --git a/security/selinux/ss/mls.h b/security/selinux/ss/mls.h > index 7954b1e60b64..15cacde0ff61 100644 > --- a/security/selinux/ss/mls.h > +++ b/security/selinux/ss/mls.h > @@ -22,7 +22,10 @@ > #ifndef _SS_MLS_H_ > #define _SS_MLS_H_ > > +#include <linux/jhash.h> > + > #include "context.h" > +#include "ebitmap.h" > #include "policydb.h" > > int mls_compute_context_len(struct policydb *p, struct context *context); > @@ -101,5 +104,13 @@ static inline int mls_import_netlbl_cat(struct policydb *p, > } > #endif > > +static inline u32 mls_range_hash(const struct mls_range *r, u32 hash) > +{ > + hash = jhash_2words(r->level[0].sens, r->level[1].sens, hash); > + hash = ebitmap_hash(&r->level[0].cat, hash); > + hash = ebitmap_hash(&r->level[1].cat, hash); > + return hash; > +} > + > #endif /* _SS_MLS_H */ > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c > index 70ecdc78efbd..ac6c0a214fc5 100644 > --- a/security/selinux/ss/policydb.c > +++ b/security/selinux/ss/policydb.c > @@ -836,11 +836,8 @@ int policydb_load_isids(struct policydb *p, struct sidtab *s) > if (!name) > continue; > > - rc = context_add_hash(p, &c->context[0]); > - if (rc) { > - sidtab_destroy(s); > - goto out; > - } > + context_add_hash(&c->context[0]); > + > rc = sidtab_set_initial(s, sid, &c->context[0]); > if (rc) { > pr_err("SELinux: unable to load initial SID %s.\n", > diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c > index 8ad34fd031d1..e4ee6d5ed825 100644 > --- a/security/selinux/ss/services.c > +++ b/security/selinux/ss/services.c > @@ -1490,38 +1490,13 @@ out: > return rc; > } > > -int context_add_hash(struct policydb *policydb, > - struct context *context) > -{ > - int rc; > - char *str; > - int len; > - > - if (context->str) { > - context->hash = context_compute_hash(context->str); > - } else { > - rc = context_struct_to_string(policydb, context, > - &str, &len); > - if (rc) > - return rc; > - context->hash = context_compute_hash(str); > - kfree(str); > - } > - return 0; > -} > - > static int context_struct_to_sid(struct selinux_state *state, > struct context *context, u32 *sid) > { > - int rc; > struct sidtab *sidtab = state->ss->sidtab; > - struct policydb *policydb = &state->ss->policydb; > > - if (!context->hash) { > - rc = context_add_hash(policydb, context); > - if (rc) > - return rc; > - } > + if (!context->hash) > + context_add_hash(context); > > return sidtab_context_to_sid(sidtab, context, sid); > } > @@ -2120,9 +2095,7 @@ static int convert_context(struct context *oldc, struct context *newc, void *p) > goto bad; > } > > - rc = context_add_hash(args->newp, newc); > - if (rc) > - goto bad; > + context_add_hash(newc); > > return 0; > bad: > @@ -2133,7 +2106,7 @@ bad: > context_destroy(newc); > newc->str = s; > newc->len = len; > - newc->hash = context_compute_hash(s); > + context_add_hash(newc); > pr_info("SELinux: Context %s became invalid (unmapped).\n", > newc->str); > return 0; > diff --git a/security/selinux/ss/services.h b/security/selinux/ss/services.h > index e9bddf33e53d..a06f3d835216 100644 > --- a/security/selinux/ss/services.h > +++ b/security/selinux/ss/services.h > @@ -8,7 +8,6 @@ > #define _SS_SERVICES_H_ > > #include "policydb.h" > -#include "context.h" > > /* Mapping for a single class */ > struct selinux_mapping { > @@ -37,6 +36,4 @@ void services_compute_xperms_drivers(struct extended_perms *xperms, > void services_compute_xperms_decision(struct extended_perms_decision *xpermd, > struct avtab_node *node); > > -int context_add_hash(struct policydb *policydb, struct context *context); > - > #endif /* _SS_SERVICES_H_ */ > -- > 2.25.2 > Reviewed-by: Jeff Vander Stoep <jeffv@google.com> Tested-by: Jeff Vander Stoep <jeffv@google.com>
On Fri, Apr 17, 2020 at 4:12 AM Ondrej Mosnacek <omosnace@redhat.com> wrote: > > Always hashing the string representation is inefficient. Just hash the > contents of the structure directly (using jhash). If the context is > invalid (str & len are set), then hash the string as before, otherwise > hash the structured data. > > Since the context hashing function is now faster (about 10 times), this > patch decreases the overhead of security_transition_sid(), which is > called from many hooks. > > The jhash function seemed as a good choice, since it is used as the > default hashing algorithm in rhashtable. > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > --- > security/selinux/Makefile | 2 +- > security/selinux/ss/context.c | 32 +++++++++++++++++++++++++++++++ > security/selinux/ss/context.h | 6 ++++-- > security/selinux/ss/ebitmap.c | 14 ++++++++++++++ > security/selinux/ss/ebitmap.h | 1 + > security/selinux/ss/mls.h | 11 +++++++++++ > security/selinux/ss/policydb.c | 7 ++----- > security/selinux/ss/services.c | 35 ++++------------------------------ > security/selinux/ss/services.h | 3 --- > 9 files changed, 69 insertions(+), 42 deletions(-) > create mode 100644 security/selinux/ss/context.c Merged into selinux/next, with the spelling correction ;)
diff --git a/security/selinux/Makefile b/security/selinux/Makefile index 0c77ede1cc11..4d8e0e8adf0b 100644 --- a/security/selinux/Makefile +++ b/security/selinux/Makefile @@ -8,7 +8,7 @@ obj-$(CONFIG_SECURITY_SELINUX) := selinux.o selinux-y := avc.o hooks.o selinuxfs.o netlink.o nlmsgtab.o netif.o \ netnode.o netport.o status.o \ ss/ebitmap.o ss/hashtab.o ss/symtab.o ss/sidtab.o ss/avtab.o \ - ss/policydb.o ss/services.o ss/conditional.o ss/mls.o + ss/policydb.o ss/services.o ss/conditional.o ss/mls.o ss/context.o selinux-$(CONFIG_SECURITY_NETWORK_XFRM) += xfrm.o diff --git a/security/selinux/ss/context.c b/security/selinux/ss/context.c new file mode 100644 index 000000000000..fac6f92b3e99 --- /dev/null +++ b/security/selinux/ss/context.c @@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Implementations of the security context functions. + * + * Author: Ondrej Mosnacek <omosnacek@gmail.com> + * Copyright (C) 2020 Red Hat, Inc. + */ + +#include <linux/jhash.h> + +#include "context.h" +#include "mls.h" + +u32 context_compute_hash(const struct context *c) +{ + u32 hash = 0; + + /* + * If a context is invalid, it will always be represented by a + * context struct with only the len & str set (and vice versa) + * under a given policy. Since context structs from different + * policies should never meet, it is safe to hash valid and + * invalid contexts differently. The context_cmp() function + * already opearates under the same assumption. + */ + if (c->len) + return full_name_hash(NULL, c->str, c->len); + + hash = jhash_3words(c->user, c->role, c->type, hash); + hash = mls_range_hash(&c->range, hash); + return hash; +} diff --git a/security/selinux/ss/context.h b/security/selinux/ss/context.h index 3ba044fe02ed..e7ae7e21449b 100644 --- a/security/selinux/ss/context.h +++ b/security/selinux/ss/context.h @@ -196,9 +196,11 @@ static inline int context_cmp(struct context *c1, struct context *c2) mls_context_cmp(c1, c2)); } -static inline unsigned int context_compute_hash(const char *s) +u32 context_compute_hash(const struct context *c); + +static inline void context_add_hash(struct context *context) { - return full_name_hash(NULL, s, strlen(s)); + context->hash = context_compute_hash(context); } #endif /* _SS_CONTEXT_H_ */ diff --git a/security/selinux/ss/ebitmap.c b/security/selinux/ss/ebitmap.c index c8c3663111e2..14bedc95c6dc 100644 --- a/security/selinux/ss/ebitmap.c +++ b/security/selinux/ss/ebitmap.c @@ -19,6 +19,7 @@ #include <linux/kernel.h> #include <linux/slab.h> #include <linux/errno.h> +#include <linux/jhash.h> #include <net/netlabel.h> #include "ebitmap.h" #include "policydb.h" @@ -542,6 +543,19 @@ int ebitmap_write(struct ebitmap *e, void *fp) return 0; } +u32 ebitmap_hash(const struct ebitmap *e, u32 hash) +{ + struct ebitmap_node *node; + + /* need to change hash even if ebitmap is empty */ + hash = jhash_1word(e->highbit, hash); + for (node = e->node; node; node = node->next) { + hash = jhash_1word(node->startbit, hash); + hash = jhash(node->maps, sizeof(node->maps), hash); + } + return hash; +} + void __init ebitmap_cache_init(void) { ebitmap_node_cachep = kmem_cache_create("ebitmap_node", diff --git a/security/selinux/ss/ebitmap.h b/security/selinux/ss/ebitmap.h index 9a23b81b8832..9eb2d0af2805 100644 --- a/security/selinux/ss/ebitmap.h +++ b/security/selinux/ss/ebitmap.h @@ -131,6 +131,7 @@ int ebitmap_set_bit(struct ebitmap *e, unsigned long bit, int value); void ebitmap_destroy(struct ebitmap *e); int ebitmap_read(struct ebitmap *e, void *fp); int ebitmap_write(struct ebitmap *e, void *fp); +u32 ebitmap_hash(const struct ebitmap *e, u32 hash); #ifdef CONFIG_NETLABEL int ebitmap_netlbl_export(struct ebitmap *ebmap, diff --git a/security/selinux/ss/mls.h b/security/selinux/ss/mls.h index 7954b1e60b64..15cacde0ff61 100644 --- a/security/selinux/ss/mls.h +++ b/security/selinux/ss/mls.h @@ -22,7 +22,10 @@ #ifndef _SS_MLS_H_ #define _SS_MLS_H_ +#include <linux/jhash.h> + #include "context.h" +#include "ebitmap.h" #include "policydb.h" int mls_compute_context_len(struct policydb *p, struct context *context); @@ -101,5 +104,13 @@ static inline int mls_import_netlbl_cat(struct policydb *p, } #endif +static inline u32 mls_range_hash(const struct mls_range *r, u32 hash) +{ + hash = jhash_2words(r->level[0].sens, r->level[1].sens, hash); + hash = ebitmap_hash(&r->level[0].cat, hash); + hash = ebitmap_hash(&r->level[1].cat, hash); + return hash; +} + #endif /* _SS_MLS_H */ diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c index 70ecdc78efbd..ac6c0a214fc5 100644 --- a/security/selinux/ss/policydb.c +++ b/security/selinux/ss/policydb.c @@ -836,11 +836,8 @@ int policydb_load_isids(struct policydb *p, struct sidtab *s) if (!name) continue; - rc = context_add_hash(p, &c->context[0]); - if (rc) { - sidtab_destroy(s); - goto out; - } + context_add_hash(&c->context[0]); + rc = sidtab_set_initial(s, sid, &c->context[0]); if (rc) { pr_err("SELinux: unable to load initial SID %s.\n", diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c index 8ad34fd031d1..e4ee6d5ed825 100644 --- a/security/selinux/ss/services.c +++ b/security/selinux/ss/services.c @@ -1490,38 +1490,13 @@ out: return rc; } -int context_add_hash(struct policydb *policydb, - struct context *context) -{ - int rc; - char *str; - int len; - - if (context->str) { - context->hash = context_compute_hash(context->str); - } else { - rc = context_struct_to_string(policydb, context, - &str, &len); - if (rc) - return rc; - context->hash = context_compute_hash(str); - kfree(str); - } - return 0; -} - static int context_struct_to_sid(struct selinux_state *state, struct context *context, u32 *sid) { - int rc; struct sidtab *sidtab = state->ss->sidtab; - struct policydb *policydb = &state->ss->policydb; - if (!context->hash) { - rc = context_add_hash(policydb, context); - if (rc) - return rc; - } + if (!context->hash) + context_add_hash(context); return sidtab_context_to_sid(sidtab, context, sid); } @@ -2120,9 +2095,7 @@ static int convert_context(struct context *oldc, struct context *newc, void *p) goto bad; } - rc = context_add_hash(args->newp, newc); - if (rc) - goto bad; + context_add_hash(newc); return 0; bad: @@ -2133,7 +2106,7 @@ bad: context_destroy(newc); newc->str = s; newc->len = len; - newc->hash = context_compute_hash(s); + context_add_hash(newc); pr_info("SELinux: Context %s became invalid (unmapped).\n", newc->str); return 0; diff --git a/security/selinux/ss/services.h b/security/selinux/ss/services.h index e9bddf33e53d..a06f3d835216 100644 --- a/security/selinux/ss/services.h +++ b/security/selinux/ss/services.h @@ -8,7 +8,6 @@ #define _SS_SERVICES_H_ #include "policydb.h" -#include "context.h" /* Mapping for a single class */ struct selinux_mapping { @@ -37,6 +36,4 @@ void services_compute_xperms_drivers(struct extended_perms *xperms, void services_compute_xperms_decision(struct extended_perms_decision *xpermd, struct avtab_node *node); -int context_add_hash(struct policydb *policydb, struct context *context); - #endif /* _SS_SERVICES_H_ */
Always hashing the string representation is inefficient. Just hash the contents of the structure directly (using jhash). If the context is invalid (str & len are set), then hash the string as before, otherwise hash the structured data. Since the context hashing function is now faster (about 10 times), this patch decreases the overhead of security_transition_sid(), which is called from many hooks. The jhash function seemed as a good choice, since it is used as the default hashing algorithm in rhashtable. Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> --- security/selinux/Makefile | 2 +- security/selinux/ss/context.c | 32 +++++++++++++++++++++++++++++++ security/selinux/ss/context.h | 6 ++++-- security/selinux/ss/ebitmap.c | 14 ++++++++++++++ security/selinux/ss/ebitmap.h | 1 + security/selinux/ss/mls.h | 11 +++++++++++ security/selinux/ss/policydb.c | 7 ++----- security/selinux/ss/services.c | 35 ++++------------------------------ security/selinux/ss/services.h | 3 --- 9 files changed, 69 insertions(+), 42 deletions(-) create mode 100644 security/selinux/ss/context.c