[PATCH 0/2] Hash context structures directly

[PATCH 0/2] Hash context structures directly

[Ondrej Mosnacek]

Converting a valid context to string and hashing that is inefficient
because the conversion is slow. Instead we can hash the stucture
contents directly, which is about 10 times faster.

After that, it is possible to move the hashing under sidtab.c, which
avoids the complexity of calling context_add_hash() all over the place.

Ondrej Mosnacek (2):
  selinux: hash context structure directly
  selinux: move context hashing under sidtab

 security/selinux/Makefile      |  2 +-
 security/selinux/ss/context.c  | 28 +++++++++++
 security/selinux/ss/context.h  | 11 +----
 security/selinux/ss/ebitmap.c  | 14 ++++++
 security/selinux/ss/ebitmap.h  |  1 +
 security/selinux/ss/policydb.c |  5 --
 security/selinux/ss/services.c | 86 ++++++++++------------------------
 security/selinux/ss/services.h |  3 --
 security/selinux/ss/sidtab.c   | 32 ++++++++-----
 security/selinux/ss/sidtab.h   |  1 +
 10 files changed, 92 insertions(+), 91 deletions(-)
 create mode 100644 security/selinux/ss/context.c

-- 
2.25.2

[PATCH 1/2] selinux: hash context structure directly

[Ondrej Mosnacek]

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. Any context that is valid under the given
policy should always be structured, and also any context that is invalid
should be never structured, so the hashes should always match for the
same context. The fact that context_cmp() also follows this logic
further reinforces this assumption.

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  | 28 ++++++++++++
 security/selinux/ss/context.h  |  6 ++-
 security/selinux/ss/ebitmap.c  | 14 ++++++
 security/selinux/ss/ebitmap.h  |  1 +
 security/selinux/ss/policydb.c |  7 +--
 security/selinux/ss/services.c | 80 ++++++++++++++--------------------
 security/selinux/ss/services.h |  3 --
 8 files changed, 82 insertions(+), 59 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..7ca32683056d
--- /dev/null
+++ b/security/selinux/ss/context.c
@@ -0,0 +1,28 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Implementations of the security context functions.
+ *
+ * Author: Ondrej Mosnacek <omosnacek@gmail.com>
+ * Copyright (C) 2018 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 (c->len)
+		return full_name_hash(NULL, c->str, c->len);
+
+	hash = jhash_3words(c->user, c->role, c->type, hash);
+	hash = jhash_2words(c->range.level[0].sens,
+			    c->range.level[1].sens, hash);
+	hash = ebitmap_hash(&c->range.level[0].cat, hash);
+	hash = ebitmap_hash(&c->range.level[1].cat, 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/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..2099355e9a7d 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1490,38 +1490,11 @@ out:
 	return rc;
 }
 
-int context_add_hash(struct policydb *policydb,
-		     struct context *context)
+static int context_struct_to_sid(struct sidtab *sidtab, struct context *context,
+				 u32 *sid)
 {
-	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);
 }
@@ -1580,7 +1553,7 @@ static int security_context_to_sid_core(struct selinux_state *state,
 		str = NULL;
 	} else if (rc)
 		goto out_unlock;
-	rc = context_struct_to_sid(state, &context, sid);
+	rc = context_struct_to_sid(sidtab, &context, sid);
 	context_destroy(&context);
 out_unlock:
 	read_unlock(&state->ss->policy_rwlock);
@@ -1891,7 +1864,7 @@ static int security_compute_sid(struct selinux_state *state,
 			goto out_unlock;
 	}
 	/* Obtain the sid for the context. */
-	rc = context_struct_to_sid(state, &newcontext, out_sid);
+	rc = context_struct_to_sid(sidtab, &newcontext, out_sid);
 out_unlock:
 	read_unlock(&state->ss->policy_rwlock);
 	context_destroy(&newcontext);
@@ -2120,9 +2093,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 +2104,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;
@@ -2350,12 +2321,14 @@ int security_port_sid(struct selinux_state *state,
 		      u8 protocol, u16 port, u32 *out_sid)
 {
 	struct policydb *policydb;
+	struct sidtab *sidtab;
 	struct ocontext *c;
 	int rc = 0;
 
 	read_lock(&state->ss->policy_rwlock);
 
 	policydb = &state->ss->policydb;
+	sidtab = state->ss->sidtab;
 
 	c = policydb->ocontexts[OCON_PORT];
 	while (c) {
@@ -2368,7 +2341,7 @@ int security_port_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(state, &c->context[0],
+			rc = context_struct_to_sid(sidtab, &c->context[0],
 						   &c->sid[0]);
 			if (rc)
 				goto out;
@@ -2393,12 +2366,14 @@ int security_ib_pkey_sid(struct selinux_state *state,
 			 u64 subnet_prefix, u16 pkey_num, u32 *out_sid)
 {
 	struct policydb *policydb;
+	struct sidtab *sidtab;
 	struct ocontext *c;
 	int rc = 0;
 
 	read_lock(&state->ss->policy_rwlock);
 
 	policydb = &state->ss->policydb;
+	sidtab = state->ss->sidtab;
 
 	c = policydb->ocontexts[OCON_IBPKEY];
 	while (c) {
@@ -2412,7 +2387,7 @@ int security_ib_pkey_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(state,
+			rc = context_struct_to_sid(sidtab,
 						   &c->context[0],
 						   &c->sid[0]);
 			if (rc)
@@ -2437,12 +2412,14 @@ int security_ib_endport_sid(struct selinux_state *state,
 			    const char *dev_name, u8 port_num, u32 *out_sid)
 {
 	struct policydb *policydb;
+	struct sidtab *sidtab;
 	struct ocontext *c;
 	int rc = 0;
 
 	read_lock(&state->ss->policy_rwlock);
 
 	policydb = &state->ss->policydb;
+	sidtab = state->ss->sidtab;
 
 	c = policydb->ocontexts[OCON_IBENDPORT];
 	while (c) {
@@ -2457,7 +2434,7 @@ int security_ib_endport_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(state, &c->context[0],
+			rc = context_struct_to_sid(sidtab, &c->context[0],
 						   &c->sid[0]);
 			if (rc)
 				goto out;
@@ -2480,12 +2457,14 @@ int security_netif_sid(struct selinux_state *state,
 		       char *name, u32 *if_sid)
 {
 	struct policydb *policydb;
+	struct sidtab *sidtab;
 	int rc = 0;
 	struct ocontext *c;
 
 	read_lock(&state->ss->policy_rwlock);
 
 	policydb = &state->ss->policydb;
+	sidtab = state->ss->sidtab;
 
 	c = policydb->ocontexts[OCON_NETIF];
 	while (c) {
@@ -2496,11 +2475,11 @@ int security_netif_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0] || !c->sid[1]) {
-			rc = context_struct_to_sid(state, &c->context[0],
+			rc = context_struct_to_sid(sidtab, &c->context[0],
 						   &c->sid[0]);
 			if (rc)
 				goto out;
-			rc = context_struct_to_sid(state, &c->context[1],
+			rc = context_struct_to_sid(sidtab, &c->context[1],
 						   &c->sid[1]);
 			if (rc)
 				goto out;
@@ -2541,12 +2520,14 @@ int security_node_sid(struct selinux_state *state,
 		      u32 *out_sid)
 {
 	struct policydb *policydb;
+	struct sidtab *sidtab;
 	int rc;
 	struct ocontext *c;
 
 	read_lock(&state->ss->policy_rwlock);
 
 	policydb = &state->ss->policydb;
+	sidtab = state->ss->sidtab;
 
 	switch (domain) {
 	case AF_INET: {
@@ -2588,7 +2569,7 @@ int security_node_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(state,
+			rc = context_struct_to_sid(sidtab,
 						   &c->context[0],
 						   &c->sid[0]);
 			if (rc)
@@ -2682,7 +2663,7 @@ int security_get_user_sids(struct selinux_state *state,
 						 &usercon))
 				continue;
 
-			rc = context_struct_to_sid(state, &usercon, &sid);
+			rc = context_struct_to_sid(sidtab, &usercon, &sid);
 			if (rc)
 				goto out_unlock;
 			if (mynel < maxnel) {
@@ -2753,6 +2734,7 @@ static inline int __security_genfs_sid(struct selinux_state *state,
 				       u32 *sid)
 {
 	struct policydb *policydb = &state->ss->policydb;
+	struct sidtab *sidtab = state->ss->sidtab;
 	int len;
 	u16 sclass;
 	struct genfs *genfs;
@@ -2787,7 +2769,7 @@ static inline int __security_genfs_sid(struct selinux_state *state,
 		goto out;
 
 	if (!c->sid[0]) {
-		rc = context_struct_to_sid(state, &c->context[0], &c->sid[0]);
+		rc = context_struct_to_sid(sidtab, &c->context[0], &c->sid[0]);
 		if (rc)
 			goto out;
 	}
@@ -2829,6 +2811,7 @@ int security_genfs_sid(struct selinux_state *state,
 int security_fs_use(struct selinux_state *state, struct super_block *sb)
 {
 	struct policydb *policydb;
+	struct sidtab *sidtab;
 	int rc = 0;
 	struct ocontext *c;
 	struct superblock_security_struct *sbsec = sb->s_security;
@@ -2837,6 +2820,7 @@ int security_fs_use(struct selinux_state *state, struct super_block *sb)
 	read_lock(&state->ss->policy_rwlock);
 
 	policydb = &state->ss->policydb;
+	sidtab = state->ss->sidtab;
 
 	c = policydb->ocontexts[OCON_FSUSE];
 	while (c) {
@@ -2848,7 +2832,7 @@ int security_fs_use(struct selinux_state *state, struct super_block *sb)
 	if (c) {
 		sbsec->behavior = c->v.behavior;
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(state, &c->context[0],
+			rc = context_struct_to_sid(sidtab, &c->context[0],
 						   &c->sid[0]);
 			if (rc)
 				goto out;
@@ -3096,7 +3080,7 @@ int security_sid_mls_copy(struct selinux_state *state,
 			goto out_unlock;
 		}
 	}
-	rc = context_struct_to_sid(state, &newcon, new_sid);
+	rc = context_struct_to_sid(sidtab, &newcon, new_sid);
 out_unlock:
 	read_unlock(&state->ss->policy_rwlock);
 	context_destroy(&newcon);
@@ -3689,7 +3673,7 @@ int security_netlbl_secattr_to_sid(struct selinux_state *state,
 		if (!mls_context_isvalid(policydb, &ctx_new))
 			goto out_free;
 
-		rc = context_struct_to_sid(state, &ctx_new, sid);
+		rc = context_struct_to_sid(sidtab, &ctx_new, sid);
 		if (rc)
 			goto out_free;
 
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

Re: [PATCH 1/2] selinux: hash context structure directly

[Paul Moore]

On Thu, Apr 9, 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. Any context that is valid under the given
> policy should always be structured, and also any context that is invalid
> should be never structured, so the hashes should always match for the
> same context. The fact that context_cmp() also follows this logic
> further reinforces this assumption.
>
> 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  | 28 ++++++++++++
>  security/selinux/ss/context.h  |  6 ++-
>  security/selinux/ss/ebitmap.c  | 14 ++++++
>  security/selinux/ss/ebitmap.h  |  1 +
>  security/selinux/ss/policydb.c |  7 +--
>  security/selinux/ss/services.c | 80 ++++++++++++++--------------------
>  security/selinux/ss/services.h |  3 --
>  8 files changed, 82 insertions(+), 59 deletions(-)
>  create mode 100644 security/selinux/ss/context.c

...

> diff --git a/security/selinux/ss/context.c b/security/selinux/ss/context.c
> new file mode 100644
> index 000000000000..7ca32683056d
> --- /dev/null
> +++ b/security/selinux/ss/context.c
> @@ -0,0 +1,28 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * Implementations of the security context functions.
> + *
> + * Author: Ondrej Mosnacek <omosnacek@gmail.com>
> + * Copyright (C) 2018 Red Hat, Inc.

I think your clock is a bit off ... ;)

Joking aside, copyright dates are important so please fix this (also
because it is a copyright related issue, it isn't something I want to
fix during the merge).

> + */
> +
> +#include <linux/jhash.h>
> +
> +#include "context.h"
> +#include "mls.h"
> +
> +u32 context_compute_hash(const struct context *c)
> +{
> +       u32 hash = 0;
> +
> +       if (c->len)
> +               return full_name_hash(NULL, c->str, c->len);
> +
> +       hash = jhash_3words(c->user, c->role, c->type, hash);
> +       hash = jhash_2words(c->range.level[0].sens,
> +                           c->range.level[1].sens, hash);
> +       hash = ebitmap_hash(&c->range.level[0].cat, hash);
> +       hash = ebitmap_hash(&c->range.level[1].cat, hash);

Most other places we try to abstract away the mls_range details by
having an associated mls_XXX(...) function, it seems like that would
be a good idea here too.  How about adding a mls_context_hash(), or
similarly named function and calling it here.

> +       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/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..2099355e9a7d 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -1490,38 +1490,11 @@ out:
>         return rc;
>  }
>
> -int context_add_hash(struct policydb *policydb,
> -                    struct context *context)
> +static int context_struct_to_sid(struct sidtab *sidtab, struct context *context,
> +                                u32 *sid)

Since you need to respin this patchset anyway, and patch 2/2 deals
with the move to sidtab, I think it might be better to keep the
context_struct_to_sid() arguments the same and not swap the first
argument for the sidtab.  If you keep the first argument as the state
it makes this patch much more focused on the change at hand and leaves
patch 2/2 dedicated to just the sidtab move.

>  {
> -       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);
>  }

-- 
paul moore
www.paul-moore.com

Re: [PATCH 1/2] selinux: hash context structure directly

[Ondrej Mosnacek]

On Thu, Apr 16, 2020 at 2:56 AM Paul Moore <paul@paul-moore.com> wrote:
> On Thu, Apr 9, 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. Any context that is valid under the given
> > policy should always be structured, and also any context that is invalid
> > should be never structured, so the hashes should always match for the
> > same context. The fact that context_cmp() also follows this logic
> > further reinforces this assumption.
> >
> > 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  | 28 ++++++++++++
> >  security/selinux/ss/context.h  |  6 ++-
> >  security/selinux/ss/ebitmap.c  | 14 ++++++
> >  security/selinux/ss/ebitmap.h  |  1 +
> >  security/selinux/ss/policydb.c |  7 +--
> >  security/selinux/ss/services.c | 80 ++++++++++++++--------------------
> >  security/selinux/ss/services.h |  3 --
> >  8 files changed, 82 insertions(+), 59 deletions(-)
> >  create mode 100644 security/selinux/ss/context.c
>
> ...
>
> > diff --git a/security/selinux/ss/context.c b/security/selinux/ss/context.c
> > new file mode 100644
> > index 000000000000..7ca32683056d
> > --- /dev/null
> > +++ b/security/selinux/ss/context.c
> > @@ -0,0 +1,28 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +/*
> > + * Implementations of the security context functions.
> > + *
> > + * Author: Ondrej Mosnacek <omosnacek@gmail.com>
> > + * Copyright (C) 2018 Red Hat, Inc.
>
> I think your clock is a bit off ... ;)
>
> Joking aside, copyright dates are important so please fix this (also
> because it is a copyright related issue, it isn't something I want to
> fix during the merge).

Ah, I copy-pasted the boilerplate from elsewhere and forgot to fix the
year... No problem, I'll send a fixed patch.

>
> > + */
> > +
> > +#include <linux/jhash.h>
> > +
> > +#include "context.h"
> > +#include "mls.h"
> > +
> > +u32 context_compute_hash(const struct context *c)
> > +{
> > +       u32 hash = 0;
> > +
> > +       if (c->len)
> > +               return full_name_hash(NULL, c->str, c->len);
> > +
> > +       hash = jhash_3words(c->user, c->role, c->type, hash);
> > +       hash = jhash_2words(c->range.level[0].sens,
> > +                           c->range.level[1].sens, hash);
> > +       hash = ebitmap_hash(&c->range.level[0].cat, hash);
> > +       hash = ebitmap_hash(&c->range.level[1].cat, hash);
>
> Most other places we try to abstract away the mls_range details by
> having an associated mls_XXX(...) function, it seems like that would
> be a good idea here too.  How about adding a mls_context_hash(), or
> similarly named function and calling it here.

Good point... I'm a little wary of adding yet another nested function
call to something that should be fast (and that will do only a few
operations on its own), but I suppose I can just make it an inline
function.

>
> > +       return hash;
> > +}
[...]
> > diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> > index 8ad34fd031d1..2099355e9a7d 100644
> > --- a/security/selinux/ss/services.c
> > +++ b/security/selinux/ss/services.c
> > @@ -1490,38 +1490,11 @@ out:
> >         return rc;
> >  }
> >
> > -int context_add_hash(struct policydb *policydb,
> > -                    struct context *context)
> > +static int context_struct_to_sid(struct sidtab *sidtab, struct context *context,
> > +                                u32 *sid)
>
> Since you need to respin this patchset anyway, and patch 2/2 deals
> with the move to sidtab, I think it might be better to keep the
> context_struct_to_sid() arguments the same and not swap the first
> argument for the sidtab.  If you keep the first argument as the state
> it makes this patch much more focused on the change at hand and leaves
> patch 2/2 dedicated to just the sidtab move.

Also a good point. I wanted to emphasize that the computation no
longer depends on policydb, but I agree that it adds an unnecessary
churn to this patch. I'll amend it as you suggest.

Thanks,

--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.

[PATCH 2/2] selinux: move context hashing under sidtab

[Ondrej Mosnacek]

Now that context hash computation no longer depends on policydb, we can
simplify things by moving the context hashing completely under sidtab.
The hash is still cached in sidtab entries, but not for the in-flight
context structures.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 security/selinux/ss/context.h  | 11 +--------
 security/selinux/ss/policydb.c |  2 --
 security/selinux/ss/services.c | 44 ++++++++++------------------------
 security/selinux/ss/sidtab.c   | 32 +++++++++++++++----------
 security/selinux/ss/sidtab.h   |  1 +
 5 files changed, 34 insertions(+), 56 deletions(-)

diff --git a/security/selinux/ss/context.h b/security/selinux/ss/context.h
index e7ae7e21449b..62990aa1ec9e 100644
--- a/security/selinux/ss/context.h
+++ b/security/selinux/ss/context.h
@@ -31,7 +31,6 @@ struct context {
 	u32 len;        /* length of string in bytes */
 	struct mls_range range;
 	char *str;	/* string representation if context cannot be mapped. */
-	u32 hash;	/* a hash of the string representation */
 };
 
 static inline void mls_context_init(struct context *c)
@@ -169,13 +168,12 @@ static inline int context_cpy(struct context *dst, struct context *src)
 		kfree(dst->str);
 		return rc;
 	}
-	dst->hash = src->hash;
 	return 0;
 }
 
 static inline void context_destroy(struct context *c)
 {
-	c->user = c->role = c->type = c->hash = 0;
+	c->user = c->role = c->type = 0;
 	kfree(c->str);
 	c->str = NULL;
 	c->len = 0;
@@ -184,8 +182,6 @@ static inline void context_destroy(struct context *c)
 
 static inline int context_cmp(struct context *c1, struct context *c2)
 {
-	if (c1->hash && c2->hash && (c1->hash != c2->hash))
-		return 0;
 	if (c1->len && c2->len)
 		return (c1->len == c2->len && !strcmp(c1->str, c2->str));
 	if (c1->len || c2->len)
@@ -198,10 +194,5 @@ static inline int context_cmp(struct context *c1, struct context *c2)
 
 u32 context_compute_hash(const struct context *c);
 
-static inline void context_add_hash(struct context *context)
-{
-	context->hash = context_compute_hash(context);
-}
-
 #endif	/* _SS_CONTEXT_H_ */
 
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index ac6c0a214fc5..f00f5851638f 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -836,8 +836,6 @@ int policydb_load_isids(struct policydb *p, struct sidtab *s)
 		if (!name)
 			continue;
 
-		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 2099355e9a7d..512cee09ee10 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1490,15 +1490,6 @@ out:
 	return rc;
 }
 
-static int context_struct_to_sid(struct sidtab *sidtab, struct context *context,
-				 u32 *sid)
-{
-	if (!context->hash)
-		context_add_hash(context);
-
-	return sidtab_context_to_sid(sidtab, context, sid);
-}
-
 static int security_context_to_sid_core(struct selinux_state *state,
 					const char *scontext, u32 scontext_len,
 					u32 *sid, u32 def_sid, gfp_t gfp_flags,
@@ -1553,7 +1544,7 @@ static int security_context_to_sid_core(struct selinux_state *state,
 		str = NULL;
 	} else if (rc)
 		goto out_unlock;
-	rc = context_struct_to_sid(sidtab, &context, sid);
+	rc = sidtab_context_to_sid(sidtab, &context, sid);
 	context_destroy(&context);
 out_unlock:
 	read_unlock(&state->ss->policy_rwlock);
@@ -1864,7 +1855,7 @@ static int security_compute_sid(struct selinux_state *state,
 			goto out_unlock;
 	}
 	/* Obtain the sid for the context. */
-	rc = context_struct_to_sid(sidtab, &newcontext, out_sid);
+	rc = sidtab_context_to_sid(sidtab, &newcontext, out_sid);
 out_unlock:
 	read_unlock(&state->ss->policy_rwlock);
 	context_destroy(&newcontext);
@@ -2016,7 +2007,6 @@ static int convert_context(struct context *oldc, struct context *newc, void *p)
 			context_init(newc);
 			newc->str = s;
 			newc->len = oldc->len;
-			newc->hash = oldc->hash;
 			return 0;
 		}
 		kfree(s);
@@ -2093,8 +2083,6 @@ static int convert_context(struct context *oldc, struct context *newc, void *p)
 			goto bad;
 	}
 
-	context_add_hash(newc);
-
 	return 0;
 bad:
 	/* Map old representation to string and save it. */
@@ -2104,7 +2092,6 @@ bad:
 	context_destroy(newc);
 	newc->str = s;
 	newc->len = len;
-	context_add_hash(newc);
 	pr_info("SELinux:  Context %s became invalid (unmapped).\n",
 		newc->str);
 	return 0;
@@ -2341,7 +2328,7 @@ int security_port_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(sidtab, &c->context[0],
+			rc = sidtab_context_to_sid(sidtab, &c->context[0],
 						   &c->sid[0]);
 			if (rc)
 				goto out;
@@ -2387,7 +2374,7 @@ int security_ib_pkey_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(sidtab,
+			rc = sidtab_context_to_sid(sidtab,
 						   &c->context[0],
 						   &c->sid[0]);
 			if (rc)
@@ -2434,7 +2421,7 @@ int security_ib_endport_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(sidtab, &c->context[0],
+			rc = sidtab_context_to_sid(sidtab, &c->context[0],
 						   &c->sid[0]);
 			if (rc)
 				goto out;
@@ -2475,11 +2462,11 @@ int security_netif_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0] || !c->sid[1]) {
-			rc = context_struct_to_sid(sidtab, &c->context[0],
+			rc = sidtab_context_to_sid(sidtab, &c->context[0],
 						   &c->sid[0]);
 			if (rc)
 				goto out;
-			rc = context_struct_to_sid(sidtab, &c->context[1],
+			rc = sidtab_context_to_sid(sidtab, &c->context[1],
 						   &c->sid[1]);
 			if (rc)
 				goto out;
@@ -2569,7 +2556,7 @@ int security_node_sid(struct selinux_state *state,
 
 	if (c) {
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(sidtab,
+			rc = sidtab_context_to_sid(sidtab,
 						   &c->context[0],
 						   &c->sid[0]);
 			if (rc)
@@ -2653,17 +2640,12 @@ int security_get_user_sids(struct selinux_state *state,
 		usercon.role = i + 1;
 		ebitmap_for_each_positive_bit(&role->types, tnode, j) {
 			usercon.type = j + 1;
-			/*
-			 * The same context struct is reused here so the hash
-			 * must be reset.
-			 */
-			usercon.hash = 0;
 
 			if (mls_setup_user_range(policydb, fromcon, user,
 						 &usercon))
 				continue;
 
-			rc = context_struct_to_sid(sidtab, &usercon, &sid);
+			rc = sidtab_context_to_sid(sidtab, &usercon, &sid);
 			if (rc)
 				goto out_unlock;
 			if (mynel < maxnel) {
@@ -2769,7 +2751,7 @@ static inline int __security_genfs_sid(struct selinux_state *state,
 		goto out;
 
 	if (!c->sid[0]) {
-		rc = context_struct_to_sid(sidtab, &c->context[0], &c->sid[0]);
+		rc = sidtab_context_to_sid(sidtab, &c->context[0], &c->sid[0]);
 		if (rc)
 			goto out;
 	}
@@ -2832,7 +2814,7 @@ int security_fs_use(struct selinux_state *state, struct super_block *sb)
 	if (c) {
 		sbsec->behavior = c->v.behavior;
 		if (!c->sid[0]) {
-			rc = context_struct_to_sid(sidtab, &c->context[0],
+			rc = sidtab_context_to_sid(sidtab, &c->context[0],
 						   &c->sid[0]);
 			if (rc)
 				goto out;
@@ -3080,7 +3062,7 @@ int security_sid_mls_copy(struct selinux_state *state,
 			goto out_unlock;
 		}
 	}
-	rc = context_struct_to_sid(sidtab, &newcon, new_sid);
+	rc = sidtab_context_to_sid(sidtab, &newcon, new_sid);
 out_unlock:
 	read_unlock(&state->ss->policy_rwlock);
 	context_destroy(&newcon);
@@ -3673,7 +3655,7 @@ int security_netlbl_secattr_to_sid(struct selinux_state *state,
 		if (!mls_context_isvalid(policydb, &ctx_new))
 			goto out_free;
 
-		rc = context_struct_to_sid(sidtab, &ctx_new, sid);
+		rc = sidtab_context_to_sid(sidtab, &ctx_new, sid);
 		if (rc)
 			goto out_free;
 
diff --git a/security/selinux/ss/sidtab.c b/security/selinux/ss/sidtab.c
index a308ce1e6a13..8012a6f7ef89 100644
--- a/security/selinux/ss/sidtab.c
+++ b/security/selinux/ss/sidtab.c
@@ -54,14 +54,15 @@ int sidtab_init(struct sidtab *s)
 	return 0;
 }
 
-static u32 context_to_sid(struct sidtab *s, struct context *context)
+static u32 context_to_sid(struct sidtab *s, struct context *context, u32 hash)
 {
 	struct sidtab_entry *entry;
 	u32 sid = 0;
 
 	rcu_read_lock();
-	hash_for_each_possible_rcu(s->context_to_sid, entry, list,
-				   context->hash) {
+	hash_for_each_possible_rcu(s->context_to_sid, entry, list, hash) {
+		if (entry->hash != hash)
+			continue;
 		if (context_cmp(&entry->context, context)) {
 			sid = entry->sid;
 			break;
@@ -74,6 +75,7 @@ static u32 context_to_sid(struct sidtab *s, struct context *context)
 int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context)
 {
 	struct sidtab_isid_entry *isid;
+	u32 hash;
 	int rc;
 
 	if (sid == 0 || sid > SECINITSID_NUM)
@@ -90,15 +92,18 @@ int sidtab_set_initial(struct sidtab *s, u32 sid, struct context *context)
 #endif
 	isid->set = 1;
 
+	hash = context_compute_hash(context);
+
 	/*
 	 * Multiple initial sids may map to the same context. Check that this
 	 * context is not already represented in the context_to_sid hashtable
 	 * to avoid duplicate entries and long linked lists upon hash
 	 * collision.
 	 */
-	if (!context_to_sid(s, context)) {
+	if (!context_to_sid(s, context, hash)) {
 		isid->entry.sid = sid;
-		hash_add(s->context_to_sid, &isid->entry.list, context->hash);
+		isid->entry.hash = hash;
+		hash_add(s->context_to_sid, &isid->entry.list, hash);
 	}
 
 	return 0;
@@ -259,12 +264,12 @@ int sidtab_context_to_sid(struct sidtab *s, struct context *context,
 			  u32 *sid)
 {
 	unsigned long flags;
-	u32 count;
+	u32 count, hash = context_compute_hash(context);
 	struct sidtab_convert_params *convert;
 	struct sidtab_entry *dst, *dst_convert;
 	int rc;
 
-	*sid = context_to_sid(s, context);
+	*sid = context_to_sid(s, context, hash);
 	if (*sid)
 		return 0;
 
@@ -272,7 +277,7 @@ int sidtab_context_to_sid(struct sidtab *s, struct context *context,
 	spin_lock_irqsave(&s->lock, flags);
 
 	rc = 0;
-	*sid = context_to_sid(s, context);
+	*sid = context_to_sid(s, context, hash);
 	if (*sid)
 		goto out_unlock;
 
@@ -292,6 +297,7 @@ int sidtab_context_to_sid(struct sidtab *s, struct context *context,
 		goto out_unlock;
 
 	dst->sid = index_to_sid(count);
+	dst->hash = hash;
 
 	rc = context_cpy(&dst->context, context);
 	if (rc)
@@ -316,10 +322,11 @@ int sidtab_context_to_sid(struct sidtab *s, struct context *context,
 			goto out_unlock;
 		}
 		dst_convert->sid = index_to_sid(count);
+		dst_convert->hash = context_compute_hash(&dst_convert->context);
 		convert->target->count = count + 1;
 
 		hash_add_rcu(convert->target->context_to_sid,
-			     &dst_convert->list, dst_convert->context.hash);
+			     &dst_convert->list, dst_convert->hash);
 	}
 
 	if (context->len)
@@ -330,7 +337,7 @@ int sidtab_context_to_sid(struct sidtab *s, struct context *context,
 
 	/* write entries before updating count */
 	smp_store_release(&s->count, count + 1);
-	hash_add_rcu(s->context_to_sid, &dst->list, dst->context.hash);
+	hash_add_rcu(s->context_to_sid, &dst->list, dst->hash);
 
 	rc = 0;
 out_unlock:
@@ -346,10 +353,9 @@ static void sidtab_convert_hashtable(struct sidtab *s, u32 count)
 	for (i = 0; i < count; i++) {
 		entry = sidtab_do_lookup(s, i, 0);
 		entry->sid = index_to_sid(i);
+		entry->hash = context_compute_hash(&entry->context);
 
-		hash_add_rcu(s->context_to_sid, &entry->list,
-			     entry->context.hash);
-
+		hash_add_rcu(s->context_to_sid, &entry->list, entry->hash);
 	}
 }
 
diff --git a/security/selinux/ss/sidtab.h b/security/selinux/ss/sidtab.h
index 3311d9f236c0..f2a84560b8b3 100644
--- a/security/selinux/ss/sidtab.h
+++ b/security/selinux/ss/sidtab.h
@@ -19,6 +19,7 @@
 
 struct sidtab_entry {
 	u32 sid;
+	u32 hash;
 	struct context context;
 #if CONFIG_SECURITY_SELINUX_SID2STR_CACHE_SIZE > 0
 	struct sidtab_str_cache __rcu *cache;
-- 
2.25.2