Skip to contentSkip to conversation

selinux: policydb - convert filename trans hash to rhashtable

RFC PATCH In review Lucas Stach 3 participants 6 messages Jan 16, 2020 – Feb 12, 2020 SELinux security module

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 selinux: policydb - convert filename trans hash to rhashtable

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.

---
 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(-)
security/selinux/ss/policydb.c +97 -43
index e20624a68f5d..d059317c15b6 100644
@@ -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;
 
security/selinux/ss/policydb.h +9 -5
index bc56b14e2216..f1d2f5166af2 100644
@@ -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
security/selinux/ss/services.c +3 -28
index a5813c7629c1..60a98d900dd3 100644
@@ -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) {
Signature · 1 line
2.24.1
#1 lore raw
Quoted 15 lines · 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

Quoted 2 lines

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.

Quoted 399 lines
---
  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(-)
security/selinux/ss/policydb.c +97 -43
index e20624a68f5d..d059317c15b6 100644
@@ -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;
 
security/selinux/ss/policydb.h +9 -5
index bc56b14e2216..f1d2f5166af2 100644
@@ -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
security/selinux/ss/services.c +3 -28
index a5813c7629c1..60a98d900dd3 100644
@@ -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 lore raw
Quoted 39 lines · Stephen Smalley
Quoted 15 lines · 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

Quoted 2 lines

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

Quoted 8 lines

# 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.

Quoted 71 lines
Quoted 71 lines
---
  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(-)
security/selinux/ss/policydb.c +12 -11
index e20624a68f5d..d059317c15b6 100644
@@ -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;
 
Quoted 8 lines

security/selinux/ss/policydb.c static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2) · line 447

Quoted 8 lines
security/selinux/ss/policydb.c +3 -0
      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.

Quoted 322 lines
Quoted 321 lines
security/selinux/ss/policydb.c +82 -32
+     .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;
 
security/selinux/ss/policydb.h +9 -5
index bc56b14e2216..f1d2f5166af2 100644
@@ -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
security/selinux/ss/services.c +3 -28
index a5813c7629c1..60a98d900dd3 100644
@@ -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) {
Signature · 3 lines
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
#3 lore raw
Quoted 61 lines · Ondrej Mosnacek
Quoted 39 lines · Stephen Smalley
Quoted 15 lines · 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

Quoted 2 lines

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

Quoted 8 lines

# 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>

Quoted 7 lines

security/selinux/ss/policydb.c static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2) · line 447

Quoted 7 lines
security/selinux/ss/policydb.c +3 -0
@@ -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:

Quoted 4 lines

+.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.

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
security/selinux/ss/policydb.c +3 -0
+     .obj_hashfn             = filenametr_hash,
+     .obj_cmpfn              = filenametr_cmp,
+};
#4 lore raw
Quoted 62 lines · Stephen Smalley
Quoted 61 lines · Ondrej Mosnacek
Quoted 39 lines · Stephen Smalley
Quoted 15 lines · 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

Quoted 2 lines

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

Quoted 8 lines

# 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>

Quoted 7 lines

security/selinux/ss/policydb.c static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2) · line 447

Quoted 7 lines
security/selinux/ss/policydb.c +3 -0
@@ -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:

Quoted 7 lines
Quoted 4 lines

+.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.

Quoted 6 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
security/selinux/ss/policydb.c +3 -0
+     .obj_hashfn             = filenametr_hash,
+     .obj_cmpfn              = filenametr_cmp,
+};
Signature · 3 lines
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
#5 lore raw
In reply to Lucas Stach

Hi Lucas,

Quoted 18 lines · 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.

Quoted 7 lines
---
 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/[email protected]/T/

Signature · 3 lines
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.