[PATCH RFC] selinux: policydb - convert filename trans hash to rhashtable

[PATCH RFC] selinux: policydb - convert filename trans hash to rhashtable

[Lucas Stach]

The current hash is too small for current usages in, e.g. the Fedora standard
policy. On file creates a considerable amount of CPU time is spent walking the
the hash chains. Increasing the number of hash buckets somewhat mitigates the
issue, but doesn't completely get rid of the long hash chains.

This patch does take the bit more invasive route by converting the filename
trans hash to a rhashtable to allow this hash to scale with load.

fs_mark create benchmark on a SSD device, no ramdisk:
Count          Size       Files/sec     App Overhead
before:
10000          512        512.3           147715
after:
10000          512        572.3            75141

filenametr_cmp(), which was the topmost function in the CPU cycle trace before
at ~5% of the overall CPU time, is now down in the noise.

Signed-off-by: Lucas Stach <dev@lynxeye.de>
---
 security/selinux/ss/policydb.c | 140 +++++++++++++++++++++++----------
 security/selinux/ss/policydb.h |  14 ++--
 security/selinux/ss/services.c |  31 +-------
 3 files changed, 109 insertions(+), 76 deletions(-)

diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index e20624a68f5d..d059317c15b6 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -34,6 +34,7 @@
 #include <linux/string.h>
 #include <linux/errno.h>
 #include <linux/audit.h>
+#include <linux/rhashtable.h>
 #include "security.h"
 
 #include "policydb.h"
@@ -334,15 +335,13 @@ static int (*destroy_f[SYM_NUM]) (void *key, void *datum, void *datap) =
 	cat_destroy,
 };
 
-static int filenametr_destroy(void *key, void *datum, void *p)
+static void filenametr_destroy(void *ptr, void *arg)
 {
-	struct filename_trans *ft = key;
+	struct filename_trans *ft = ptr;
 
 	kfree(ft->name);
-	kfree(key);
-	kfree(datum);
+	kfree(ft);
 	cond_resched();
-	return 0;
 }
 
 static int range_tr_destroy(void *key, void *datum, void *p)
@@ -404,9 +403,9 @@ static int roles_init(struct policydb *p)
 	return rc;
 }
 
-static u32 filenametr_hash(struct hashtab *h, const void *k)
+static u32 filenametr_hash(const void *data, u32 len, u32 seed)
 {
-	const struct filename_trans *ft = k;
+	const struct filename_trans *ft = data;
 	unsigned long hash;
 	unsigned int byte_num;
 	unsigned char focus;
@@ -416,13 +415,15 @@ static u32 filenametr_hash(struct hashtab *h, const void *k)
 	byte_num = 0;
 	while ((focus = ft->name[byte_num++]))
 		hash = partial_name_hash(focus, hash);
-	return hash & (h->size - 1);
+
+	return end_name_hash(hash);
 }
 
-static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
+static int filenametr_cmp(struct rhashtable_compare_arg *arg,
+			  const void *obj)
 {
-	const struct filename_trans *ft1 = k1;
-	const struct filename_trans *ft2 = k2;
+	const struct filename_trans *ft1 = arg->key;
+	const struct filename_trans *ft2 = obj;
 	int v;
 
 	v = ft1->stype - ft2->stype;
@@ -441,6 +442,39 @@ static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
 
 }
 
+static const struct rhashtable_params filename_trans_hashparams = {
+	.nelem_hint		= 1024,
+	.head_offset		= offsetof(struct filename_trans, hash_head),
+	.obj_hashfn		= filenametr_hash,
+	.obj_cmpfn		= filenametr_cmp,
+};
+
+void policydb_filename_compute_type(struct policydb *policydb,
+				    struct context *newcontext,
+				    u32 stype, u32 ttype, u16 tclass,
+				    const char *objname)
+{
+	struct filename_trans key, *ft;
+
+	/*
+	 * Most filename trans rules are going to live in specific directories
+	 * like /dev or /var/run.  This bitmap will quickly skip rule searches
+	 * if the ttype does not contain any rules.
+	 */
+	if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
+		return;
+
+	key.stype = stype;
+	key.ttype = ttype;
+	key.tclass = tclass;
+	key.name = objname;
+
+	ft = rhashtable_lookup(&policydb->filename_trans, &key,
+			       filename_trans_hashparams);
+	if (ft)
+		newcontext->type = ft->otype;
+}
+
 static u32 rangetr_hash(struct hashtab *h, const void *k)
 {
 	const struct range_trans *key = k;
@@ -494,12 +528,7 @@ static int policydb_init(struct policydb *p)
 	if (rc)
 		goto out;
 
-	p->filename_trans = hashtab_create(filenametr_hash, filenametr_cmp,
-					   (1 << 10));
-	if (!p->filename_trans) {
-		rc = -ENOMEM;
-		goto out;
-	}
+	rhashtable_init(&p->filename_trans, &filename_trans_hashparams);
 
 	p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, 256);
 	if (!p->range_tr) {
@@ -513,7 +542,7 @@ static int policydb_init(struct policydb *p)
 
 	return 0;
 out:
-	hashtab_destroy(p->filename_trans);
+	rhashtable_destroy(&p->filename_trans);
 	hashtab_destroy(p->range_tr);
 	for (i = 0; i < SYM_NUM; i++) {
 		hashtab_map(p->symtab[i].table, destroy_f[i], NULL);
@@ -831,8 +860,8 @@ void policydb_destroy(struct policydb *p)
 	}
 	kfree(lra);
 
-	hashtab_map(p->filename_trans, filenametr_destroy, NULL);
-	hashtab_destroy(p->filename_trans);
+	rhashtable_free_and_destroy(&p->filename_trans, filenametr_destroy,
+				    NULL);
 
 	hashtab_map(p->range_tr, range_tr_destroy, NULL);
 	hashtab_destroy(p->range_tr);
@@ -1878,7 +1907,6 @@ static int range_read(struct policydb *p, void *fp)
 static int filename_trans_read(struct policydb *p, void *fp)
 {
 	struct filename_trans *ft;
-	struct filename_trans_datum *otype;
 	char *name;
 	u32 nel, len;
 	__le32 buf[4];
@@ -1893,7 +1921,6 @@ static int filename_trans_read(struct policydb *p, void *fp)
 	nel = le32_to_cpu(buf[0]);
 
 	for (i = 0; i < nel; i++) {
-		otype = NULL;
 		name = NULL;
 
 		rc = -ENOMEM;
@@ -1901,11 +1928,6 @@ static int filename_trans_read(struct policydb *p, void *fp)
 		if (!ft)
 			goto out;
 
-		rc = -ENOMEM;
-		otype = kmalloc(sizeof(*otype), GFP_KERNEL);
-		if (!otype)
-			goto out;
-
 		/* length of the path component string */
 		rc = next_entry(buf, fp, sizeof(u32));
 		if (rc)
@@ -1926,14 +1948,14 @@ static int filename_trans_read(struct policydb *p, void *fp)
 		ft->stype = le32_to_cpu(buf[0]);
 		ft->ttype = le32_to_cpu(buf[1]);
 		ft->tclass = le32_to_cpu(buf[2]);
-
-		otype->otype = le32_to_cpu(buf[3]);
+		ft->otype = le32_to_cpu(buf[3]);
 
 		rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
 		if (rc)
 			goto out;
 
-		rc = hashtab_insert(p->filename_trans, ft, otype);
+		rc = rhashtable_insert_fast(&p->filename_trans, &ft->hash_head,
+					    filename_trans_hashparams);
 		if (rc) {
 			/*
 			 * Do not return -EEXIST to the caller, or the system
@@ -1944,15 +1966,12 @@ static int filename_trans_read(struct policydb *p, void *fp)
 			/* But free memory to avoid memory leak. */
 			kfree(ft);
 			kfree(name);
-			kfree(otype);
 		}
 	}
-	hash_eval(p->filename_trans, "filenametr");
 	return 0;
 out:
 	kfree(ft);
 	kfree(name);
-	kfree(otype);
 
 	return rc;
 }
@@ -3323,12 +3342,10 @@ static int range_write(struct policydb *p, void *fp)
 	return 0;
 }
 
-static int filename_write_helper(void *key, void *data, void *ptr)
+static int filename_write_helper(struct filename_trans *ft,
+				 struct policy_file *fp)
 {
 	__le32 buf[4];
-	struct filename_trans *ft = key;
-	struct filename_trans_datum *otype = data;
-	void *fp = ptr;
 	int rc;
 	u32 len;
 
@@ -3345,7 +3362,7 @@ static int filename_write_helper(void *key, void *data, void *ptr)
 	buf[0] = cpu_to_le32(ft->stype);
 	buf[1] = cpu_to_le32(ft->ttype);
 	buf[2] = cpu_to_le32(ft->tclass);
-	buf[3] = cpu_to_le32(otype->otype);
+	buf[3] = cpu_to_le32(ft->otype);
 
 	rc = put_entry(buf, sizeof(u32), 4, fp);
 	if (rc)
@@ -3356,15 +3373,34 @@ static int filename_write_helper(void *key, void *data, void *ptr)
 
 static int filename_trans_write(struct policydb *p, void *fp)
 {
-	u32 nel;
+	u32 nel = 0;
 	__le32 buf[1];
-	int rc;
+	int rc = 0;
+	struct rhashtable_iter iter;
 
 	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
 		return 0;
 
-	nel = 0;
-	rc = hashtab_map(p->filename_trans, hashtab_cnt, &nel);
+	rhashtable_walk_enter(&p->filename_trans, &iter);
+	rhashtable_walk_start(&iter);
+	for(;;) {
+		struct filename_trans *trans;
+
+		trans = rhashtable_walk_next(&iter);
+		if (!trans)
+			break;
+		if (IS_ERR(trans)) {
+			if (PTR_ERR(trans) == -EAGAIN) {
+				nel = 0;
+				continue;
+			}
+			rc = PTR_ERR(trans);
+			break;
+		}
+		nel++;
+	};
+	rhashtable_walk_stop(&iter);
+	rhashtable_walk_exit(&iter);
 	if (rc)
 		return rc;
 
@@ -3373,7 +3409,25 @@ static int filename_trans_write(struct policydb *p, void *fp)
 	if (rc)
 		return rc;
 
-	rc = hashtab_map(p->filename_trans, filename_write_helper, fp);
+	rhashtable_walk_enter(&p->filename_trans, &iter);
+	rhashtable_walk_start(&iter);
+	for(;;) {
+		struct filename_trans *trans;
+
+		trans = rhashtable_walk_next(&iter);
+		if (!trans)
+			break;
+		if (IS_ERR(trans)) {
+			if (PTR_ERR(trans) == -EAGAIN) {
+				continue;
+			}
+			rc = PTR_ERR(trans);
+			break;
+		}
+		filename_write_helper(trans, fp);
+	};
+	rhashtable_walk_stop(&iter);
+	rhashtable_walk_exit(&iter);
 	if (rc)
 		return rc;
 
diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
index bc56b14e2216..f1d2f5166af2 100644
--- a/security/selinux/ss/policydb.h
+++ b/security/selinux/ss/policydb.h
@@ -29,6 +29,7 @@
 #include "mls_types.h"
 #include "context.h"
 #include "constraint.h"
+#include <linux/rhashtable.h>
 
 /*
  * A datum type is defined for each kind of symbol
@@ -90,16 +91,14 @@ struct role_trans {
 };
 
 struct filename_trans {
+	struct rhash_head hash_head;
+	u32 otype;
 	u32 stype;		/* current process */
 	u32 ttype;		/* parent dir context */
 	u16 tclass;		/* class of new object */
 	const char *name;	/* last path component */
 };
 
-struct filename_trans_datum {
-	u32 otype;		/* expected of new object */
-};
-
 struct role_allow {
 	u32 role;		/* current role */
 	u32 new_role;		/* new role */
@@ -266,7 +265,7 @@ struct policydb {
 	/* quickly exclude lookups when parent ttype has no rules */
 	struct ebitmap filename_trans_ttypes;
 	/* actual set of filename_trans rules */
-	struct hashtab *filename_trans;
+	struct rhashtable filename_trans;
 
 	/* bools indexed by (value - 1) */
 	struct cond_bool_datum **bool_val_to_struct;
@@ -318,6 +317,11 @@ extern int policydb_role_isvalid(struct policydb *p, unsigned int role);
 extern int policydb_read(struct policydb *p, void *fp);
 extern int policydb_write(struct policydb *p, void *fp);
 
+void policydb_filename_compute_type(struct policydb *policydb,
+				    struct context *newcontext,
+				    u32 stype, u32 ttype, u16 tclass,
+				    const char *objname);
+
 #define PERM_SYMTAB_SIZE 32
 
 #define POLICYDB_CONFIG_MLS    1
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index a5813c7629c1..60a98d900dd3 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1607,32 +1607,6 @@ static int compute_sid_handle_invalid_context(
 	return -EACCES;
 }
 
-static void filename_compute_type(struct policydb *policydb,
-				  struct context *newcontext,
-				  u32 stype, u32 ttype, u16 tclass,
-				  const char *objname)
-{
-	struct filename_trans ft;
-	struct filename_trans_datum *otype;
-
-	/*
-	 * Most filename trans rules are going to live in specific directories
-	 * like /dev or /var/run.  This bitmap will quickly skip rule searches
-	 * if the ttype does not contain any rules.
-	 */
-	if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
-		return;
-
-	ft.stype = stype;
-	ft.ttype = ttype;
-	ft.tclass = tclass;
-	ft.name = objname;
-
-	otype = hashtab_search(policydb->filename_trans, &ft);
-	if (otype)
-		newcontext->type = otype->otype;
-}
-
 static int security_compute_sid(struct selinux_state *state,
 				u32 ssid,
 				u32 tsid,
@@ -1770,8 +1744,9 @@ static int security_compute_sid(struct selinux_state *state,
 
 	/* if we have a objname this is a file trans check so check those rules */
 	if (objname)
-		filename_compute_type(policydb, &newcontext, scontext->type,
-				      tcontext->type, tclass, objname);
+		policydb_filename_compute_type(policydb, &newcontext,
+					       scontext->type, tcontext->type,
+					       tclass, objname);
 
 	/* Check for class-specific changes. */
 	if (specified & AVTAB_TRANSITION) {
-- 
2.24.1

Re: [PATCH RFC] selinux: policydb - convert filename trans hash to rhashtable

[Stephen Smalley]

On 1/16/20 4:39 PM, Lucas Stach wrote:
> The current hash is too small for current usages in, e.g. the Fedora standard
> policy. On file creates a considerable amount of CPU time is spent walking the
> the hash chains. Increasing the number of hash buckets somewhat mitigates the
> issue, but doesn't completely get rid of the long hash chains.
> 
> This patch does take the bit more invasive route by converting the filename
> trans hash to a rhashtable to allow this hash to scale with load.
> 
> fs_mark create benchmark on a SSD device, no ramdisk:
> Count          Size       Files/sec     App Overhead
> before:
> 10000          512        512.3           147715
> after:
> 10000          512        572.3            75141
> 
> filenametr_cmp(), which was the topmost function in the CPU cycle trace before
> at ~5% of the overall CPU time, is now down in the noise.

Thank you for working on this.  IMHO, Fedora overuses name-based type 
transitions but that's another topic. I haven't yet investigated the 
root cause but with your patch applied, I see some test failures related 
to name-based transitions:

[...]
#   Failed test at overlay/test line 439.
overlay/test ................ 114/119 # Looks like you failed 1 test of 119.
[...]
filesystem/test ............. 3/70 File context error, expected:
	test_filesystem_filenametranscon1_t
got:
	test_filesystem_filetranscon_t

#   Failed test at filesystem/test line 279.
File context error, expected:
	test_filesystem_filenametranscon2_t
got:
	test_filesystem_filetranscon_t

#   Failed test at filesystem/test line 286.
filesystem/test ............. 68/70 # Looks like you failed 2 tests of 70.

You can reproduce by cloning the selinux-testsuite from 
https://github.com/SELinuxProject/selinux-testsuite, applying the 
filesystem tests patch from
https://patchwork.kernel.org/patch/11337659/,
and following the README.md instructions.

> 
> Signed-off-by: Lucas Stach <dev@lynxeye.de>
> ---
>   security/selinux/ss/policydb.c | 140 +++++++++++++++++++++++----------
>   security/selinux/ss/policydb.h |  14 ++--
>   security/selinux/ss/services.c |  31 +-------
>   3 files changed, 109 insertions(+), 76 deletions(-)
> 
> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index e20624a68f5d..d059317c15b6 100644
> --- a/security/selinux/ss/policydb.c
> +++ b/security/selinux/ss/policydb.c
> @@ -34,6 +34,7 @@
>   #include <linux/string.h>
>   #include <linux/errno.h>
>   #include <linux/audit.h>
> +#include <linux/rhashtable.h>
>   #include "security.h"
>   
>   #include "policydb.h"
> @@ -334,15 +335,13 @@ static int (*destroy_f[SYM_NUM]) (void *key, void *datum, void *datap) =
>   	cat_destroy,
>   };
>   
> -static int filenametr_destroy(void *key, void *datum, void *p)
> +static void filenametr_destroy(void *ptr, void *arg)
>   {
> -	struct filename_trans *ft = key;
> +	struct filename_trans *ft = ptr;
>   
>   	kfree(ft->name);
> -	kfree(key);
> -	kfree(datum);
> +	kfree(ft);
>   	cond_resched();
> -	return 0;
>   }
>   
>   static int range_tr_destroy(void *key, void *datum, void *p)
> @@ -404,9 +403,9 @@ static int roles_init(struct policydb *p)
>   	return rc;
>   }
>   
> -static u32 filenametr_hash(struct hashtab *h, const void *k)
> +static u32 filenametr_hash(const void *data, u32 len, u32 seed)
>   {
> -	const struct filename_trans *ft = k;
> +	const struct filename_trans *ft = data;
>   	unsigned long hash;
>   	unsigned int byte_num;
>   	unsigned char focus;
> @@ -416,13 +415,15 @@ static u32 filenametr_hash(struct hashtab *h, const void *k)
>   	byte_num = 0;
>   	while ((focus = ft->name[byte_num++]))
>   		hash = partial_name_hash(focus, hash);
> -	return hash & (h->size - 1);
> +
> +	return end_name_hash(hash);
>   }
>   
> -static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
> +static int filenametr_cmp(struct rhashtable_compare_arg *arg,
> +			  const void *obj)
>   {
> -	const struct filename_trans *ft1 = k1;
> -	const struct filename_trans *ft2 = k2;
> +	const struct filename_trans *ft1 = arg->key;
> +	const struct filename_trans *ft2 = obj;
>   	int v;
>   
>   	v = ft1->stype - ft2->stype;
> @@ -441,6 +442,39 @@ static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
>   
>   }
>   
> +static const struct rhashtable_params filename_trans_hashparams = {
> +	.nelem_hint		= 1024,
> +	.head_offset		= offsetof(struct filename_trans, hash_head),
> +	.obj_hashfn		= filenametr_hash,
> +	.obj_cmpfn		= filenametr_cmp,
> +};
> +
> +void policydb_filename_compute_type(struct policydb *policydb,
> +				    struct context *newcontext,
> +				    u32 stype, u32 ttype, u16 tclass,
> +				    const char *objname)
> +{
> +	struct filename_trans key, *ft;
> +
> +	/*
> +	 * Most filename trans rules are going to live in specific directories
> +	 * like /dev or /var/run.  This bitmap will quickly skip rule searches
> +	 * if the ttype does not contain any rules.
> +	 */
> +	if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
> +		return;
> +
> +	key.stype = stype;
> +	key.ttype = ttype;
> +	key.tclass = tclass;
> +	key.name = objname;
> +
> +	ft = rhashtable_lookup(&policydb->filename_trans, &key,
> +			       filename_trans_hashparams);
> +	if (ft)
> +		newcontext->type = ft->otype;
> +}
> +
>   static u32 rangetr_hash(struct hashtab *h, const void *k)
>   {
>   	const struct range_trans *key = k;
> @@ -494,12 +528,7 @@ static int policydb_init(struct policydb *p)
>   	if (rc)
>   		goto out;
>   
> -	p->filename_trans = hashtab_create(filenametr_hash, filenametr_cmp,
> -					   (1 << 10));
> -	if (!p->filename_trans) {
> -		rc = -ENOMEM;
> -		goto out;
> -	}
> +	rhashtable_init(&p->filename_trans, &filename_trans_hashparams);
>   
>   	p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, 256);
>   	if (!p->range_tr) {
> @@ -513,7 +542,7 @@ static int policydb_init(struct policydb *p)
>   
>   	return 0;
>   out:
> -	hashtab_destroy(p->filename_trans);
> +	rhashtable_destroy(&p->filename_trans);
>   	hashtab_destroy(p->range_tr);
>   	for (i = 0; i < SYM_NUM; i++) {
>   		hashtab_map(p->symtab[i].table, destroy_f[i], NULL);
> @@ -831,8 +860,8 @@ void policydb_destroy(struct policydb *p)
>   	}
>   	kfree(lra);
>   
> -	hashtab_map(p->filename_trans, filenametr_destroy, NULL);
> -	hashtab_destroy(p->filename_trans);
> +	rhashtable_free_and_destroy(&p->filename_trans, filenametr_destroy,
> +				    NULL);
>   
>   	hashtab_map(p->range_tr, range_tr_destroy, NULL);
>   	hashtab_destroy(p->range_tr);
> @@ -1878,7 +1907,6 @@ static int range_read(struct policydb *p, void *fp)
>   static int filename_trans_read(struct policydb *p, void *fp)
>   {
>   	struct filename_trans *ft;
> -	struct filename_trans_datum *otype;
>   	char *name;
>   	u32 nel, len;
>   	__le32 buf[4];
> @@ -1893,7 +1921,6 @@ static int filename_trans_read(struct policydb *p, void *fp)
>   	nel = le32_to_cpu(buf[0]);
>   
>   	for (i = 0; i < nel; i++) {
> -		otype = NULL;
>   		name = NULL;
>   
>   		rc = -ENOMEM;
> @@ -1901,11 +1928,6 @@ static int filename_trans_read(struct policydb *p, void *fp)
>   		if (!ft)
>   			goto out;
>   
> -		rc = -ENOMEM;
> -		otype = kmalloc(sizeof(*otype), GFP_KERNEL);
> -		if (!otype)
> -			goto out;
> -
>   		/* length of the path component string */
>   		rc = next_entry(buf, fp, sizeof(u32));
>   		if (rc)
> @@ -1926,14 +1948,14 @@ static int filename_trans_read(struct policydb *p, void *fp)
>   		ft->stype = le32_to_cpu(buf[0]);
>   		ft->ttype = le32_to_cpu(buf[1]);
>   		ft->tclass = le32_to_cpu(buf[2]);
> -
> -		otype->otype = le32_to_cpu(buf[3]);
> +		ft->otype = le32_to_cpu(buf[3]);
>   
>   		rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
>   		if (rc)
>   			goto out;
>   
> -		rc = hashtab_insert(p->filename_trans, ft, otype);
> +		rc = rhashtable_insert_fast(&p->filename_trans, &ft->hash_head,
> +					    filename_trans_hashparams);
>   		if (rc) {
>   			/*
>   			 * Do not return -EEXIST to the caller, or the system
> @@ -1944,15 +1966,12 @@ static int filename_trans_read(struct policydb *p, void *fp)
>   			/* But free memory to avoid memory leak. */
>   			kfree(ft);
>   			kfree(name);
> -			kfree(otype);
>   		}
>   	}
> -	hash_eval(p->filename_trans, "filenametr");
>   	return 0;
>   out:
>   	kfree(ft);
>   	kfree(name);
> -	kfree(otype);
>   
>   	return rc;
>   }
> @@ -3323,12 +3342,10 @@ static int range_write(struct policydb *p, void *fp)
>   	return 0;
>   }
>   
> -static int filename_write_helper(void *key, void *data, void *ptr)
> +static int filename_write_helper(struct filename_trans *ft,
> +				 struct policy_file *fp)
>   {
>   	__le32 buf[4];
> -	struct filename_trans *ft = key;
> -	struct filename_trans_datum *otype = data;
> -	void *fp = ptr;
>   	int rc;
>   	u32 len;
>   
> @@ -3345,7 +3362,7 @@ static int filename_write_helper(void *key, void *data, void *ptr)
>   	buf[0] = cpu_to_le32(ft->stype);
>   	buf[1] = cpu_to_le32(ft->ttype);
>   	buf[2] = cpu_to_le32(ft->tclass);
> -	buf[3] = cpu_to_le32(otype->otype);
> +	buf[3] = cpu_to_le32(ft->otype);
>   
>   	rc = put_entry(buf, sizeof(u32), 4, fp);
>   	if (rc)
> @@ -3356,15 +3373,34 @@ static int filename_write_helper(void *key, void *data, void *ptr)
>   
>   static int filename_trans_write(struct policydb *p, void *fp)
>   {
> -	u32 nel;
> +	u32 nel = 0;
>   	__le32 buf[1];
> -	int rc;
> +	int rc = 0;
> +	struct rhashtable_iter iter;
>   
>   	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
>   		return 0;
>   
> -	nel = 0;
> -	rc = hashtab_map(p->filename_trans, hashtab_cnt, &nel);
> +	rhashtable_walk_enter(&p->filename_trans, &iter);
> +	rhashtable_walk_start(&iter);
> +	for(;;) {
> +		struct filename_trans *trans;
> +
> +		trans = rhashtable_walk_next(&iter);
> +		if (!trans)
> +			break;
> +		if (IS_ERR(trans)) {
> +			if (PTR_ERR(trans) == -EAGAIN) {
> +				nel = 0;
> +				continue;
> +			}
> +			rc = PTR_ERR(trans);
> +			break;
> +		}
> +		nel++;
> +	};
> +	rhashtable_walk_stop(&iter);
> +	rhashtable_walk_exit(&iter);
>   	if (rc)
>   		return rc;
>   
> @@ -3373,7 +3409,25 @@ static int filename_trans_write(struct policydb *p, void *fp)
>   	if (rc)
>   		return rc;
>   
> -	rc = hashtab_map(p->filename_trans, filename_write_helper, fp);
> +	rhashtable_walk_enter(&p->filename_trans, &iter);
> +	rhashtable_walk_start(&iter);
> +	for(;;) {
> +		struct filename_trans *trans;
> +
> +		trans = rhashtable_walk_next(&iter);
> +		if (!trans)
> +			break;
> +		if (IS_ERR(trans)) {
> +			if (PTR_ERR(trans) == -EAGAIN) {
> +				continue;
> +			}
> +			rc = PTR_ERR(trans);
> +			break;
> +		}
> +		filename_write_helper(trans, fp);
> +	};
> +	rhashtable_walk_stop(&iter);
> +	rhashtable_walk_exit(&iter);
>   	if (rc)
>   		return rc;
>   
> diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> index bc56b14e2216..f1d2f5166af2 100644
> --- a/security/selinux/ss/policydb.h
> +++ b/security/selinux/ss/policydb.h
> @@ -29,6 +29,7 @@
>   #include "mls_types.h"
>   #include "context.h"
>   #include "constraint.h"
> +#include <linux/rhashtable.h>
>   
>   /*
>    * A datum type is defined for each kind of symbol
> @@ -90,16 +91,14 @@ struct role_trans {
>   };
>   
>   struct filename_trans {
> +	struct rhash_head hash_head;
> +	u32 otype;
>   	u32 stype;		/* current process */
>   	u32 ttype;		/* parent dir context */
>   	u16 tclass;		/* class of new object */
>   	const char *name;	/* last path component */
>   };
>   
> -struct filename_trans_datum {
> -	u32 otype;		/* expected of new object */
> -};
> -
>   struct role_allow {
>   	u32 role;		/* current role */
>   	u32 new_role;		/* new role */
> @@ -266,7 +265,7 @@ struct policydb {
>   	/* quickly exclude lookups when parent ttype has no rules */
>   	struct ebitmap filename_trans_ttypes;
>   	/* actual set of filename_trans rules */
> -	struct hashtab *filename_trans;
> +	struct rhashtable filename_trans;
>   
>   	/* bools indexed by (value - 1) */
>   	struct cond_bool_datum **bool_val_to_struct;
> @@ -318,6 +317,11 @@ extern int policydb_role_isvalid(struct policydb *p, unsigned int role);
>   extern int policydb_read(struct policydb *p, void *fp);
>   extern int policydb_write(struct policydb *p, void *fp);
>   
> +void policydb_filename_compute_type(struct policydb *policydb,
> +				    struct context *newcontext,
> +				    u32 stype, u32 ttype, u16 tclass,
> +				    const char *objname);
> +
>   #define PERM_SYMTAB_SIZE 32
>   
>   #define POLICYDB_CONFIG_MLS    1
> diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> index a5813c7629c1..60a98d900dd3 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -1607,32 +1607,6 @@ static int compute_sid_handle_invalid_context(
>   	return -EACCES;
>   }
>   
> -static void filename_compute_type(struct policydb *policydb,
> -				  struct context *newcontext,
> -				  u32 stype, u32 ttype, u16 tclass,
> -				  const char *objname)
> -{
> -	struct filename_trans ft;
> -	struct filename_trans_datum *otype;
> -
> -	/*
> -	 * Most filename trans rules are going to live in specific directories
> -	 * like /dev or /var/run.  This bitmap will quickly skip rule searches
> -	 * if the ttype does not contain any rules.
> -	 */
> -	if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
> -		return;
> -
> -	ft.stype = stype;
> -	ft.ttype = ttype;
> -	ft.tclass = tclass;
> -	ft.name = objname;
> -
> -	otype = hashtab_search(policydb->filename_trans, &ft);
> -	if (otype)
> -		newcontext->type = otype->otype;
> -}
> -
>   static int security_compute_sid(struct selinux_state *state,
>   				u32 ssid,
>   				u32 tsid,
> @@ -1770,8 +1744,9 @@ static int security_compute_sid(struct selinux_state *state,
>   
>   	/* if we have a objname this is a file trans check so check those rules */
>   	if (objname)
> -		filename_compute_type(policydb, &newcontext, scontext->type,
> -				      tcontext->type, tclass, objname);
> +		policydb_filename_compute_type(policydb, &newcontext,
> +					       scontext->type, tcontext->type,
> +					       tclass, objname);
>   
>   	/* Check for class-specific changes. */
>   	if (specified & AVTAB_TRANSITION) {
> 

Re: [PATCH RFC] selinux: policydb - convert filename trans hash to rhashtable

[Ondrej Mosnacek]

On Fri, Jan 17, 2020 at 8:11 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> On 1/16/20 4:39 PM, Lucas Stach wrote:
> > The current hash is too small for current usages in, e.g. the Fedora standard
> > policy. On file creates a considerable amount of CPU time is spent walking the
> > the hash chains. Increasing the number of hash buckets somewhat mitigates the
> > issue, but doesn't completely get rid of the long hash chains.
> >
> > This patch does take the bit more invasive route by converting the filename
> > trans hash to a rhashtable to allow this hash to scale with load.
> >
> > fs_mark create benchmark on a SSD device, no ramdisk:
> > Count          Size       Files/sec     App Overhead
> > before:
> > 10000          512        512.3           147715
> > after:
> > 10000          512        572.3            75141
> >
> > filenametr_cmp(), which was the topmost function in the CPU cycle trace before
> > at ~5% of the overall CPU time, is now down in the noise.
>
> Thank you for working on this.  IMHO, Fedora overuses name-based type
> transitions but that's another topic. I haven't yet investigated the
> root cause but with your patch applied, I see some test failures related
> to name-based transitions:
>
> [...]
> #   Failed test at overlay/test line 439.
> overlay/test ................ 114/119 # Looks like you failed 1 test of 119.
> [...]
> filesystem/test ............. 3/70 File context error, expected:
>         test_filesystem_filenametranscon1_t
> got:
>         test_filesystem_filetranscon_t
>
> #   Failed test at filesystem/test line 279.
> File context error, expected:
>         test_filesystem_filenametranscon2_t
> got:
>         test_filesystem_filetranscon_t
>
> #   Failed test at filesystem/test line 286.
> filesystem/test ............. 68/70 # Looks like you failed 2 tests of 70.
>
> You can reproduce by cloning the selinux-testsuite from
> https://github.com/SELinuxProject/selinux-testsuite, applying the
> filesystem tests patch from
> https://patchwork.kernel.org/patch/11337659/,
> and following the README.md instructions.

I think I figured out what's wrong - see below.

>
> >
> > Signed-off-by: Lucas Stach <dev@lynxeye.de>
> > ---
> >   security/selinux/ss/policydb.c | 140 +++++++++++++++++++++++----------
> >   security/selinux/ss/policydb.h |  14 ++--
> >   security/selinux/ss/services.c |  31 +-------
> >   3 files changed, 109 insertions(+), 76 deletions(-)
> >
> > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > index e20624a68f5d..d059317c15b6 100644
> > --- a/security/selinux/ss/policydb.c
> > +++ b/security/selinux/ss/policydb.c
> > @@ -34,6 +34,7 @@
> >   #include <linux/string.h>
> >   #include <linux/errno.h>
> >   #include <linux/audit.h>
> > +#include <linux/rhashtable.h>
> >   #include "security.h"
> >
> >   #include "policydb.h"
> > @@ -334,15 +335,13 @@ static int (*destroy_f[SYM_NUM]) (void *key, void *datum, void *datap) =
> >       cat_destroy,
> >   };
> >
> > -static int filenametr_destroy(void *key, void *datum, void *p)
> > +static void filenametr_destroy(void *ptr, void *arg)
> >   {
> > -     struct filename_trans *ft = key;
> > +     struct filename_trans *ft = ptr;
> >
> >       kfree(ft->name);
> > -     kfree(key);
> > -     kfree(datum);
> > +     kfree(ft);
> >       cond_resched();
> > -     return 0;
> >   }
> >
> >   static int range_tr_destroy(void *key, void *datum, void *p)
> > @@ -404,9 +403,9 @@ static int roles_init(struct policydb *p)
> >       return rc;
> >   }
> >
> > -static u32 filenametr_hash(struct hashtab *h, const void *k)
> > +static u32 filenametr_hash(const void *data, u32 len, u32 seed)
> >   {
> > -     const struct filename_trans *ft = k;
> > +     const struct filename_trans *ft = data;
> >       unsigned long hash;
> >       unsigned int byte_num;
> >       unsigned char focus;
> > @@ -416,13 +415,15 @@ static u32 filenametr_hash(struct hashtab *h, const void *k)
> >       byte_num = 0;
> >       while ((focus = ft->name[byte_num++]))
> >               hash = partial_name_hash(focus, hash);
> > -     return hash & (h->size - 1);
> > +
> > +     return end_name_hash(hash);
> >   }
> >
> > -static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
> > +static int filenametr_cmp(struct rhashtable_compare_arg *arg,
> > +                       const void *obj)
> >   {
> > -     const struct filename_trans *ft1 = k1;
> > -     const struct filename_trans *ft2 = k2;
> > +     const struct filename_trans *ft1 = arg->key;
> > +     const struct filename_trans *ft2 = obj;
> >       int v;
> >
> >       v = ft1->stype - ft2->stype;
> > @@ -441,6 +442,39 @@ static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
> >
> >   }
> >
> > +static const struct rhashtable_params filename_trans_hashparams = {
> > +     .nelem_hint             = 1024,
> > +     .head_offset            = offsetof(struct filename_trans, hash_head),

You need to add:

+.hashfn = filenametr_hash,

here so that the key is correctly hashed on lookup. After applying
this fix, the selinux-testuite passes for me with this patch.

> > +     .obj_hashfn             = filenametr_hash,
> > +     .obj_cmpfn              = filenametr_cmp,
> > +};
> > +
> > +void policydb_filename_compute_type(struct policydb *policydb,
> > +                                 struct context *newcontext,
> > +                                 u32 stype, u32 ttype, u16 tclass,
> > +                                 const char *objname)
> > +{
> > +     struct filename_trans key, *ft;
> > +
> > +     /*
> > +      * Most filename trans rules are going to live in specific directories
> > +      * like /dev or /var/run.  This bitmap will quickly skip rule searches
> > +      * if the ttype does not contain any rules.
> > +      */
> > +     if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
> > +             return;
> > +
> > +     key.stype = stype;
> > +     key.ttype = ttype;
> > +     key.tclass = tclass;
> > +     key.name = objname;
> > +
> > +     ft = rhashtable_lookup(&policydb->filename_trans, &key,
> > +                            filename_trans_hashparams);
> > +     if (ft)
> > +             newcontext->type = ft->otype;
> > +}
> > +
> >   static u32 rangetr_hash(struct hashtab *h, const void *k)
> >   {
> >       const struct range_trans *key = k;
> > @@ -494,12 +528,7 @@ static int policydb_init(struct policydb *p)
> >       if (rc)
> >               goto out;
> >
> > -     p->filename_trans = hashtab_create(filenametr_hash, filenametr_cmp,
> > -                                        (1 << 10));
> > -     if (!p->filename_trans) {
> > -             rc = -ENOMEM;
> > -             goto out;
> > -     }
> > +     rhashtable_init(&p->filename_trans, &filename_trans_hashparams);
> >
> >       p->range_tr = hashtab_create(rangetr_hash, rangetr_cmp, 256);
> >       if (!p->range_tr) {
> > @@ -513,7 +542,7 @@ static int policydb_init(struct policydb *p)
> >
> >       return 0;
> >   out:
> > -     hashtab_destroy(p->filename_trans);
> > +     rhashtable_destroy(&p->filename_trans);
> >       hashtab_destroy(p->range_tr);
> >       for (i = 0; i < SYM_NUM; i++) {
> >               hashtab_map(p->symtab[i].table, destroy_f[i], NULL);
> > @@ -831,8 +860,8 @@ void policydb_destroy(struct policydb *p)
> >       }
> >       kfree(lra);
> >
> > -     hashtab_map(p->filename_trans, filenametr_destroy, NULL);
> > -     hashtab_destroy(p->filename_trans);
> > +     rhashtable_free_and_destroy(&p->filename_trans, filenametr_destroy,
> > +                                 NULL);
> >
> >       hashtab_map(p->range_tr, range_tr_destroy, NULL);
> >       hashtab_destroy(p->range_tr);
> > @@ -1878,7 +1907,6 @@ static int range_read(struct policydb *p, void *fp)
> >   static int filename_trans_read(struct policydb *p, void *fp)
> >   {
> >       struct filename_trans *ft;
> > -     struct filename_trans_datum *otype;
> >       char *name;
> >       u32 nel, len;
> >       __le32 buf[4];
> > @@ -1893,7 +1921,6 @@ static int filename_trans_read(struct policydb *p, void *fp)
> >       nel = le32_to_cpu(buf[0]);
> >
> >       for (i = 0; i < nel; i++) {
> > -             otype = NULL;
> >               name = NULL;
> >
> >               rc = -ENOMEM;
> > @@ -1901,11 +1928,6 @@ static int filename_trans_read(struct policydb *p, void *fp)
> >               if (!ft)
> >                       goto out;
> >
> > -             rc = -ENOMEM;
> > -             otype = kmalloc(sizeof(*otype), GFP_KERNEL);
> > -             if (!otype)
> > -                     goto out;
> > -
> >               /* length of the path component string */
> >               rc = next_entry(buf, fp, sizeof(u32));
> >               if (rc)
> > @@ -1926,14 +1948,14 @@ static int filename_trans_read(struct policydb *p, void *fp)
> >               ft->stype = le32_to_cpu(buf[0]);
> >               ft->ttype = le32_to_cpu(buf[1]);
> >               ft->tclass = le32_to_cpu(buf[2]);
> > -
> > -             otype->otype = le32_to_cpu(buf[3]);
> > +             ft->otype = le32_to_cpu(buf[3]);
> >
> >               rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
> >               if (rc)
> >                       goto out;
> >
> > -             rc = hashtab_insert(p->filename_trans, ft, otype);
> > +             rc = rhashtable_insert_fast(&p->filename_trans, &ft->hash_head,
> > +                                         filename_trans_hashparams);
> >               if (rc) {
> >                       /*
> >                        * Do not return -EEXIST to the caller, or the system
> > @@ -1944,15 +1966,12 @@ static int filename_trans_read(struct policydb *p, void *fp)
> >                       /* But free memory to avoid memory leak. */
> >                       kfree(ft);
> >                       kfree(name);
> > -                     kfree(otype);
> >               }
> >       }
> > -     hash_eval(p->filename_trans, "filenametr");
> >       return 0;
> >   out:
> >       kfree(ft);
> >       kfree(name);
> > -     kfree(otype);
> >
> >       return rc;
> >   }
> > @@ -3323,12 +3342,10 @@ static int range_write(struct policydb *p, void *fp)
> >       return 0;
> >   }
> >
> > -static int filename_write_helper(void *key, void *data, void *ptr)
> > +static int filename_write_helper(struct filename_trans *ft,
> > +                              struct policy_file *fp)
> >   {
> >       __le32 buf[4];
> > -     struct filename_trans *ft = key;
> > -     struct filename_trans_datum *otype = data;
> > -     void *fp = ptr;
> >       int rc;
> >       u32 len;
> >
> > @@ -3345,7 +3362,7 @@ static int filename_write_helper(void *key, void *data, void *ptr)
> >       buf[0] = cpu_to_le32(ft->stype);
> >       buf[1] = cpu_to_le32(ft->ttype);
> >       buf[2] = cpu_to_le32(ft->tclass);
> > -     buf[3] = cpu_to_le32(otype->otype);
> > +     buf[3] = cpu_to_le32(ft->otype);
> >
> >       rc = put_entry(buf, sizeof(u32), 4, fp);
> >       if (rc)
> > @@ -3356,15 +3373,34 @@ static int filename_write_helper(void *key, void *data, void *ptr)
> >
> >   static int filename_trans_write(struct policydb *p, void *fp)
> >   {
> > -     u32 nel;
> > +     u32 nel = 0;
> >       __le32 buf[1];
> > -     int rc;
> > +     int rc = 0;
> > +     struct rhashtable_iter iter;
> >
> >       if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> >               return 0;
> >
> > -     nel = 0;
> > -     rc = hashtab_map(p->filename_trans, hashtab_cnt, &nel);
> > +     rhashtable_walk_enter(&p->filename_trans, &iter);
> > +     rhashtable_walk_start(&iter);
> > +     for(;;) {
> > +             struct filename_trans *trans;
> > +
> > +             trans = rhashtable_walk_next(&iter);
> > +             if (!trans)
> > +                     break;
> > +             if (IS_ERR(trans)) {
> > +                     if (PTR_ERR(trans) == -EAGAIN) {
> > +                             nel = 0;
> > +                             continue;
> > +                     }
> > +                     rc = PTR_ERR(trans);
> > +                     break;
> > +             }
> > +             nel++;
> > +     };
> > +     rhashtable_walk_stop(&iter);
> > +     rhashtable_walk_exit(&iter);
> >       if (rc)
> >               return rc;
> >
> > @@ -3373,7 +3409,25 @@ static int filename_trans_write(struct policydb *p, void *fp)
> >       if (rc)
> >               return rc;
> >
> > -     rc = hashtab_map(p->filename_trans, filename_write_helper, fp);
> > +     rhashtable_walk_enter(&p->filename_trans, &iter);
> > +     rhashtable_walk_start(&iter);
> > +     for(;;) {
> > +             struct filename_trans *trans;
> > +
> > +             trans = rhashtable_walk_next(&iter);
> > +             if (!trans)
> > +                     break;
> > +             if (IS_ERR(trans)) {
> > +                     if (PTR_ERR(trans) == -EAGAIN) {
> > +                             continue;
> > +                     }
> > +                     rc = PTR_ERR(trans);
> > +                     break;
> > +             }
> > +             filename_write_helper(trans, fp);
> > +     };
> > +     rhashtable_walk_stop(&iter);
> > +     rhashtable_walk_exit(&iter);
> >       if (rc)
> >               return rc;
> >
> > diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> > index bc56b14e2216..f1d2f5166af2 100644
> > --- a/security/selinux/ss/policydb.h
> > +++ b/security/selinux/ss/policydb.h
> > @@ -29,6 +29,7 @@
> >   #include "mls_types.h"
> >   #include "context.h"
> >   #include "constraint.h"
> > +#include <linux/rhashtable.h>
> >
> >   /*
> >    * A datum type is defined for each kind of symbol
> > @@ -90,16 +91,14 @@ struct role_trans {
> >   };
> >
> >   struct filename_trans {
> > +     struct rhash_head hash_head;
> > +     u32 otype;
> >       u32 stype;              /* current process */
> >       u32 ttype;              /* parent dir context */
> >       u16 tclass;             /* class of new object */
> >       const char *name;       /* last path component */
> >   };
> >
> > -struct filename_trans_datum {
> > -     u32 otype;              /* expected of new object */
> > -};
> > -
> >   struct role_allow {
> >       u32 role;               /* current role */
> >       u32 new_role;           /* new role */
> > @@ -266,7 +265,7 @@ struct policydb {
> >       /* quickly exclude lookups when parent ttype has no rules */
> >       struct ebitmap filename_trans_ttypes;
> >       /* actual set of filename_trans rules */
> > -     struct hashtab *filename_trans;
> > +     struct rhashtable filename_trans;
> >
> >       /* bools indexed by (value - 1) */
> >       struct cond_bool_datum **bool_val_to_struct;
> > @@ -318,6 +317,11 @@ extern int policydb_role_isvalid(struct policydb *p, unsigned int role);
> >   extern int policydb_read(struct policydb *p, void *fp);
> >   extern int policydb_write(struct policydb *p, void *fp);
> >
> > +void policydb_filename_compute_type(struct policydb *policydb,
> > +                                 struct context *newcontext,
> > +                                 u32 stype, u32 ttype, u16 tclass,
> > +                                 const char *objname);
> > +
> >   #define PERM_SYMTAB_SIZE 32
> >
> >   #define POLICYDB_CONFIG_MLS    1
> > diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> > index a5813c7629c1..60a98d900dd3 100644
> > --- a/security/selinux/ss/services.c
> > +++ b/security/selinux/ss/services.c
> > @@ -1607,32 +1607,6 @@ static int compute_sid_handle_invalid_context(
> >       return -EACCES;
> >   }
> >
> > -static void filename_compute_type(struct policydb *policydb,
> > -                               struct context *newcontext,
> > -                               u32 stype, u32 ttype, u16 tclass,
> > -                               const char *objname)
> > -{
> > -     struct filename_trans ft;
> > -     struct filename_trans_datum *otype;
> > -
> > -     /*
> > -      * Most filename trans rules are going to live in specific directories
> > -      * like /dev or /var/run.  This bitmap will quickly skip rule searches
> > -      * if the ttype does not contain any rules.
> > -      */
> > -     if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
> > -             return;
> > -
> > -     ft.stype = stype;
> > -     ft.ttype = ttype;
> > -     ft.tclass = tclass;
> > -     ft.name = objname;
> > -
> > -     otype = hashtab_search(policydb->filename_trans, &ft);
> > -     if (otype)
> > -             newcontext->type = otype->otype;
> > -}
> > -
> >   static int security_compute_sid(struct selinux_state *state,
> >                               u32 ssid,
> >                               u32 tsid,
> > @@ -1770,8 +1744,9 @@ static int security_compute_sid(struct selinux_state *state,
> >
> >       /* if we have a objname this is a file trans check so check those rules */
> >       if (objname)
> > -             filename_compute_type(policydb, &newcontext, scontext->type,
> > -                                   tcontext->type, tclass, objname);
> > +             policydb_filename_compute_type(policydb, &newcontext,
> > +                                            scontext->type, tcontext->type,
> > +                                            tclass, objname);
> >
> >       /* Check for class-specific changes. */
> >       if (specified & AVTAB_TRANSITION) {
> >
>

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

Re: [PATCH RFC] selinux: policydb - convert filename trans hash to rhashtable

[Stephen Smalley]

On 2/4/20 10:01 AM, Ondrej Mosnacek wrote:
> On Fri, Jan 17, 2020 at 8:11 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
>> On 1/16/20 4:39 PM, Lucas Stach wrote:
>>> The current hash is too small for current usages in, e.g. the Fedora standard
>>> policy. On file creates a considerable amount of CPU time is spent walking the
>>> the hash chains. Increasing the number of hash buckets somewhat mitigates the
>>> issue, but doesn't completely get rid of the long hash chains.
>>>
>>> This patch does take the bit more invasive route by converting the filename
>>> trans hash to a rhashtable to allow this hash to scale with load.
>>>
>>> fs_mark create benchmark on a SSD device, no ramdisk:
>>> Count          Size       Files/sec     App Overhead
>>> before:
>>> 10000          512        512.3           147715
>>> after:
>>> 10000          512        572.3            75141
>>>
>>> filenametr_cmp(), which was the topmost function in the CPU cycle trace before
>>> at ~5% of the overall CPU time, is now down in the noise.
>>
>> Thank you for working on this.  IMHO, Fedora overuses name-based type
>> transitions but that's another topic. I haven't yet investigated the
>> root cause but with your patch applied, I see some test failures related
>> to name-based transitions:
>>
>> [...]
>> #   Failed test at overlay/test line 439.
>> overlay/test ................ 114/119 # Looks like you failed 1 test of 119.
>> [...]
>> filesystem/test ............. 3/70 File context error, expected:
>>          test_filesystem_filenametranscon1_t
>> got:
>>          test_filesystem_filetranscon_t
>>
>> #   Failed test at filesystem/test line 279.
>> File context error, expected:
>>          test_filesystem_filenametranscon2_t
>> got:
>>          test_filesystem_filetranscon_t
>>
>> #   Failed test at filesystem/test line 286.
>> filesystem/test ............. 68/70 # Looks like you failed 2 tests of 70.
>>
>> You can reproduce by cloning the selinux-testsuite from
>> https://github.com/SELinuxProject/selinux-testsuite, applying the
>> filesystem tests patch from
>> https://patchwork.kernel.org/patch/11337659/,
>> and following the README.md instructions.
> 
> I think I figured out what's wrong - see below.
> <snip>
>>> @@ -441,6 +442,39 @@ static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
>>>
>>>    }
>>>
>>> +static const struct rhashtable_params filename_trans_hashparams = {
>>> +     .nelem_hint             = 1024,
>>> +     .head_offset            = offsetof(struct filename_trans, hash_head),
> 
> You need to add:
> 
> +.hashfn = filenametr_hash,
> 
> here so that the key is correctly hashed on lookup. After applying
> this fix, the selinux-testuite passes for me with this patch.

Hmm..does that then make the .obj_hashfn assignment below unnecessary or 
is that required too?  I'm unclear on the difference.

> 
>>> +     .obj_hashfn             = filenametr_hash,
>>> +     .obj_cmpfn              = filenametr_cmp,
>>> +};

Re: [PATCH RFC] selinux: policydb - convert filename trans hash to rhashtable

[Ondrej Mosnacek]

On Tue, Feb 4, 2020 at 4:39 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> On 2/4/20 10:01 AM, Ondrej Mosnacek wrote:
> > On Fri, Jan 17, 2020 at 8:11 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> >> On 1/16/20 4:39 PM, Lucas Stach wrote:
> >>> The current hash is too small for current usages in, e.g. the Fedora standard
> >>> policy. On file creates a considerable amount of CPU time is spent walking the
> >>> the hash chains. Increasing the number of hash buckets somewhat mitigates the
> >>> issue, but doesn't completely get rid of the long hash chains.
> >>>
> >>> This patch does take the bit more invasive route by converting the filename
> >>> trans hash to a rhashtable to allow this hash to scale with load.
> >>>
> >>> fs_mark create benchmark on a SSD device, no ramdisk:
> >>> Count          Size       Files/sec     App Overhead
> >>> before:
> >>> 10000          512        512.3           147715
> >>> after:
> >>> 10000          512        572.3            75141
> >>>
> >>> filenametr_cmp(), which was the topmost function in the CPU cycle trace before
> >>> at ~5% of the overall CPU time, is now down in the noise.
> >>
> >> Thank you for working on this.  IMHO, Fedora overuses name-based type
> >> transitions but that's another topic. I haven't yet investigated the
> >> root cause but with your patch applied, I see some test failures related
> >> to name-based transitions:
> >>
> >> [...]
> >> #   Failed test at overlay/test line 439.
> >> overlay/test ................ 114/119 # Looks like you failed 1 test of 119.
> >> [...]
> >> filesystem/test ............. 3/70 File context error, expected:
> >>          test_filesystem_filenametranscon1_t
> >> got:
> >>          test_filesystem_filetranscon_t
> >>
> >> #   Failed test at filesystem/test line 279.
> >> File context error, expected:
> >>          test_filesystem_filenametranscon2_t
> >> got:
> >>          test_filesystem_filetranscon_t
> >>
> >> #   Failed test at filesystem/test line 286.
> >> filesystem/test ............. 68/70 # Looks like you failed 2 tests of 70.
> >>
> >> You can reproduce by cloning the selinux-testsuite from
> >> https://github.com/SELinuxProject/selinux-testsuite, applying the
> >> filesystem tests patch from
> >> https://patchwork.kernel.org/patch/11337659/,
> >> and following the README.md instructions.
> >
> > I think I figured out what's wrong - see below.
> > <snip>
> >>> @@ -441,6 +442,39 @@ static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
> >>>
> >>>    }
> >>>
> >>> +static const struct rhashtable_params filename_trans_hashparams = {
> >>> +     .nelem_hint             = 1024,
> >>> +     .head_offset            = offsetof(struct filename_trans, hash_head),
> >
> > You need to add:
> >
> > +.hashfn = filenametr_hash,
> >
> > here so that the key is correctly hashed on lookup. After applying
> > this fix, the selinux-testuite passes for me with this patch.
>
> Hmm..does that then make the .obj_hashfn assignment below unnecessary or
> is that required too?  I'm unclear on the difference.

No, they serve different purposes - hashfn is used to hash the key you
pass when you do the lookup, while obj_hashfn is used to hash the full
objects stored in the hash table. In general, these can be different
types, but here we use the same type for both, so the same function
can be reused for both callbacks.

>
> >
> >>> +     .obj_hashfn             = filenametr_hash,
> >>> +     .obj_cmpfn              = filenametr_cmp,
> >>> +};
>

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

Re: [PATCH RFC] selinux: policydb - convert filename trans hash to rhashtable

[Ondrej Mosnacek]

Hi Lucas,

On Thu, Jan 16, 2020 at 10:48 PM Lucas Stach <dev@lynxeye.de> wrote:
> The current hash is too small for current usages in, e.g. the Fedora standard
> policy. On file creates a considerable amount of CPU time is spent walking the
> the hash chains. Increasing the number of hash buckets somewhat mitigates the
> issue, but doesn't completely get rid of the long hash chains.
>
> This patch does take the bit more invasive route by converting the filename
> trans hash to a rhashtable to allow this hash to scale with load.
>
> fs_mark create benchmark on a SSD device, no ramdisk:
> Count          Size       Files/sec     App Overhead
> before:
> 10000          512        512.3           147715
> after:
> 10000          512        572.3            75141
>
> filenametr_cmp(), which was the topmost function in the CPU cycle trace before
> at ~5% of the overall CPU time, is now down in the noise.
>
> Signed-off-by: Lucas Stach <dev@lynxeye.de>
> ---
>  security/selinux/ss/policydb.c | 140 +++++++++++++++++++++++----------
>  security/selinux/ss/policydb.h |  14 ++--
>  security/selinux/ss/services.c |  31 +-------
>  3 files changed, 109 insertions(+), 76 deletions(-)
>

FYI, I posted a related patch series [1] that should have a similar
effect on the file create performance, plus it also reduces memory
taken up by the file transition rules. It would be great if you could
test it vs. your (fixed) patch to see if it works for you.

Thanks!

[1] https://lore.kernel.org/selinux/20200212112255.105678-1-omosnace@redhat.com/T/

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