On Fri, Apr 17, 2020 at 10:12 AM Ondrej Mosnacek <omosnace@xxxxxxxxxx> 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@xxxxxxxxxx>
> ---
> 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@xxxxxxxxx>
> + * 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@xxxxxxxxxx>
Tested-by: Jeff Vander Stoep <jeffv@xxxxxxxxxx>
