[PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Juraj Marcin]

Currently, filename transitions are stored separately from other type
enforcement rules and only support exact name matching. However, in
practice, the names contain variable parts. This leads to many
duplicated rules in the policy that differ only in the part of the name,
or it is even impossible to cover all possible combinations.

First, this series of patches moves the filename transitions to be part
of the avtab structures. This not only makes the implementation of
prefix/suffix matching and future enhancements easier, but also reduces
the technical debt regarding the filename transitions. Next, the last
patch implements the support for prefix/suffix name matching itself by
extending the structures added in previous patches in this series.

Even though, moving everything to avtab increases the memory usage and
the size of the binary policy itself and thus the loading time, the
ability to match the prefix or suffix of the name will reduce the
overall number of rules in the policy which should mitigate this issue.

This implementation has been successfully tested using the existing and
also new tests in the SELinux Testsuite.

Juraj Marcin (5):
  selinux: move transition to separate structure in avtab_datum
  selinux: move filename transitions to avtab
  selinux: implement new binary format for filename transitions in avtab
  selinux: filename transitions move tests
  selinux: add prefix/suffix matching support to filename type
    transitions

 security/selinux/Kconfig            |  17 +
 security/selinux/Makefile           |   2 +
 security/selinux/include/security.h |   4 +-
 security/selinux/ss/avtab.c         | 814 +++++++++++++++++++++++++++-
 security/selinux/ss/avtab.h         |  16 +-
 security/selinux/ss/avtab_test.c    | 745 +++++++++++++++++++++++++
 security/selinux/ss/conditional.c   |   6 +-
 security/selinux/ss/hashtab.h       |   6 +
 security/selinux/ss/policydb.c      | 421 +-------------
 security/selinux/ss/policydb.h      |  25 +-
 security/selinux/ss/services.c      |  80 ++-
 security/selinux/ss/symtab.c        |   3 +
 12 files changed, 1677 insertions(+), 462 deletions(-)
 create mode 100644 security/selinux/ss/avtab_test.c

-- 
2.40.0

[PATCH 1/5] selinux: move transition to separate structure in avtab_datum

[Juraj Marcin]

This is a preparation to move filename transitions to be part of the
avtab data structure. To do that, we first need to create space for it
in the avtab_datum structure which holds the rule for certain
combination of stype, ttype and tclass.

As only type transitions have a special variant that uses a filename, it
would be suboptimal to add a (mostly empty) pointer to some structure to
all avtab rules.

Therefore, this patch adds a new structure to the union in avtab_datum
and moves the otype of the transition to this structure. In the next
patch, this structure will also hold filename transitions for the
combination of stype, ttype and tclass. As the union already contains a
pointer, the size of avtab_datum does not increase. The only trade-off
is that each transition requires at least 4 more bytes and structure
allocation.

Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
---
 security/selinux/ss/avtab.c    | 60 ++++++++++++++++++++++++++++++----
 security/selinux/ss/avtab.h    |  7 +++-
 security/selinux/ss/services.c |  5 ++-
 3 files changed, 63 insertions(+), 9 deletions(-)

diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 6766edc0fe68..a7f348e4509d 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -24,6 +24,7 @@
 #include "policydb.h"
 
 static struct kmem_cache *avtab_node_cachep __ro_after_init;
+static struct kmem_cache *avtab_trans_cachep __ro_after_init;
 static struct kmem_cache *avtab_xperms_cachep __ro_after_init;
 
 /* Based on MurmurHash3, written by Austin Appleby and placed in the
@@ -71,6 +72,7 @@ avtab_insert_node(struct avtab *h, int hvalue,
 		  const struct avtab_key *key, const struct avtab_datum *datum)
 {
 	struct avtab_node *newnode;
+	struct avtab_trans *trans;
 	struct avtab_extended_perms *xperms;
 	newnode = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
 	if (newnode == NULL)
@@ -85,6 +87,14 @@ avtab_insert_node(struct avtab *h, int hvalue,
 		}
 		*xperms = *(datum->u.xperms);
 		newnode->datum.u.xperms = xperms;
+	} else if (key->specified & AVTAB_TRANSITION) {
+		trans = kmem_cache_zalloc(avtab_trans_cachep, GFP_KERNEL);
+		if (!trans) {
+			kmem_cache_free(avtab_node_cachep, newnode);
+			return NULL;
+		}
+		*trans = *datum->u.trans;
+		newnode->datum.u.trans = trans;
 	} else {
 		newnode->datum.u.data = datum->u.data;
 	}
@@ -289,9 +299,13 @@ void avtab_destroy(struct avtab *h)
 		while (cur) {
 			temp = cur;
 			cur = cur->next;
-			if (temp->key.specified & AVTAB_XPERMS)
+			if (temp->key.specified & AVTAB_XPERMS) {
 				kmem_cache_free(avtab_xperms_cachep,
 						temp->datum.u.xperms);
+			} else if (temp->key.specified & AVTAB_TRANSITION) {
+				kmem_cache_free(avtab_trans_cachep,
+						temp->datum.u.trans);
+			}
 			kmem_cache_free(avtab_node_cachep, temp);
 		}
 	}
@@ -407,6 +421,7 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 	u32 items, items2, val, vers = pol->policyvers;
 	struct avtab_key key;
 	struct avtab_datum datum;
+	struct avtab_trans trans;
 	struct avtab_extended_perms xperms;
 	__le32 buf32[ARRAY_SIZE(xperms.perms.p)];
 	int i, rc;
@@ -473,7 +488,16 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		for (i = 0; i < ARRAY_SIZE(spec_order); i++) {
 			if (val & spec_order[i]) {
 				key.specified = spec_order[i] | enabled;
-				datum.u.data = le32_to_cpu(buf32[items++]);
+				if (key.specified & AVTAB_TRANSITION) {
+					memset(&trans, 0,
+					       sizeof(struct avtab_trans));
+					trans.otype =
+						le32_to_cpu(buf32[items++]);
+					datum.u.trans = &trans;
+				} else {
+					datum.u.data =
+						le32_to_cpu(buf32[items++]);
+				}
 				rc = insertf(a, &key, &datum, p);
 				if (rc)
 					return rc;
@@ -543,6 +567,15 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		for (i = 0; i < ARRAY_SIZE(xperms.perms.p); i++)
 			xperms.perms.p[i] = le32_to_cpu(buf32[i]);
 		datum.u.xperms = &xperms;
+	} else if (key.specified & AVTAB_TRANSITION) {
+		memset(&trans, 0, sizeof(struct avtab_trans));
+		rc = next_entry(buf32, fp, sizeof(u32));
+		if (rc) {
+			pr_err("SELinux: avtab: truncated entry\n");
+			return rc;
+		}
+		trans.otype = le32_to_cpu(*buf32);
+		datum.u.trans = &trans;
 	} else {
 		rc = next_entry(buf32, fp, sizeof(u32));
 		if (rc) {
@@ -551,12 +584,19 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		}
 		datum.u.data = le32_to_cpu(*buf32);
 	}
-	if ((key.specified & AVTAB_TYPE) &&
-	    !policydb_type_isvalid(pol, datum.u.data)) {
-		pr_err("SELinux: avtab: invalid type\n");
-		return -EINVAL;
+	if (key.specified & AVTAB_TRANSITION) {
+		if (!policydb_type_isvalid(pol, datum.u.trans->otype)) {
+			pr_err("SELinux: avtab: invalid transition type\n");
+			return -EINVAL;
+		}
+	} else if (key.specified & AVTAB_TYPE) {
+		if (!policydb_type_isvalid(pol, datum.u.data)) {
+			pr_err("SELinux: avtab: invalid type\n");
+			return -EINVAL;
+		}
 	}
-	return insertf(a, &key, &datum, p);
+	rc = insertf(a, &key, &datum, p);
+	return rc;
 }
 
 static int avtab_insertf(struct avtab *a, const struct avtab_key *k,
@@ -635,6 +675,9 @@ int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
 			buf32[i] = cpu_to_le32(cur->datum.u.xperms->perms.p[i]);
 		rc = put_entry(buf32, sizeof(u32),
 				ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp);
+	} else if (cur->key.specified & AVTAB_TRANSITION) {
+		buf32[0] = cpu_to_le32(cur->datum.u.trans->otype);
+		rc = put_entry(buf32, sizeof(u32), 1, fp);
 	} else {
 		buf32[0] = cpu_to_le32(cur->datum.u.data);
 		rc = put_entry(buf32, sizeof(u32), 1, fp);
@@ -673,6 +716,9 @@ void __init avtab_cache_init(void)
 	avtab_node_cachep = kmem_cache_create("avtab_node",
 					      sizeof(struct avtab_node),
 					      0, SLAB_PANIC, NULL);
+	avtab_trans_cachep = kmem_cache_create("avtab_trans",
+					       sizeof(struct avtab_trans),
+					       0, SLAB_PANIC, NULL);
 	avtab_xperms_cachep = kmem_cache_create("avtab_extended_perms",
 						sizeof(struct avtab_extended_perms),
 						0, SLAB_PANIC, NULL);
diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index d6742fd9c560..6c8eb7c379cf 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -47,6 +47,10 @@ struct avtab_key {
 	u16 specified;	/* what field is specified */
 };
 
+struct avtab_trans {
+	u32 otype;		/* default resulting type of the new object */
+};
+
 /*
  * For operations that require more than the 32 permissions provided by the avc
  * extended permissions may be used to provide 256 bits of permissions.
@@ -69,7 +73,8 @@ struct avtab_extended_perms {
 
 struct avtab_datum {
 	union {
-		u32 data; /* access vector or type value */
+		u32 data; /* access vector, member or change value */
+		struct avtab_trans *trans;	/* transition value */
 		struct avtab_extended_perms *xperms;
 	} u;
 };
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index 78946b71c1c1..8ed12406acba 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1830,7 +1830,10 @@ static int security_compute_sid(u32 ssid,
 
 	if (avdatum) {
 		/* Use the type from the type transition/member/change rule. */
-		newcontext.type = avdatum->u.data;
+		if (avkey.specified & AVTAB_TRANSITION)
+			newcontext.type = avdatum->u.trans->otype;
+		else
+			newcontext.type = avdatum->u.data;
 	}
 
 	/* if we have a objname this is a file trans check so check those rules */
-- 
2.40.0

[PATCH 2/5] selinux: move filename transitions to avtab

[Juraj Marcin]

Currently, filename transitions are stored separately from other type
enforcement rules. This leads to possibly sub-optimal performance and
makes further improvements cumbersome.

This patch adds a symbol table of filename transitions to the transition
structure added to avtab in the previous patch. It also implements
functions required for reading and writing filename transitions in
kernel policy format and updates computation of new type to use filename
transitions embedded in avtab. Last but not least, it updates the
conflict check in the conditional avtab to account for empty transitions
in the non-conditional avtab.

These changes are expected to cause higher memory usage, as now there
needs to be a filename transition structure for every stype. This patch
effectively undoes most of the commit c3a276111ea2 ("selinux: optimize
storage of filename transitions"), but this will be mitigated by
providing support for matching prefix/suffix of the filename for
filename transitions in future patches which will reduce to need to have
so many of them.

On the other hand, the changes do not significantly slow down the
creation of new files.

Kernel     | Mem   | Create test_tty | Create test_tty | osbench [1]
           | usage | (real time)     | (kernel time)   | create_files
-----------+-------+-----------------+-----------------+--------------
reference  | 155MB |  1.3440 ms/file |  1.0071 ms/file | 10.6507 us/file
this patch | 198MB |  1.3912 ms/file |  1.0172 ms/file | 10.5567 us/file

Create test_tty benchmark:

    mknod /dev/test_tty c 4 1
    time for i in `seq 1 10000`; do
        mknod /dev/test_tty$i c 4 1
    done

This benchmark should simulate the worst case scenario as many filename
transitions affect files created in the /dev directory.

[1] https://github.com/mbitsnbites/osbench

Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
---
 security/selinux/ss/avtab.c       | 516 ++++++++++++++++++++++++++++++
 security/selinux/ss/avtab.h       |   7 +
 security/selinux/ss/conditional.c |   6 +-
 security/selinux/ss/hashtab.h     |   6 +
 security/selinux/ss/policydb.c    | 399 +----------------------
 security/selinux/ss/policydb.h    |  25 +-
 security/selinux/ss/services.c    |  54 +---
 7 files changed, 555 insertions(+), 458 deletions(-)

diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index a7f348e4509d..fe921e1586e5 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -22,6 +22,7 @@
 #include <linux/errno.h>
 #include "avtab.h"
 #include "policydb.h"
+#include "hashtab.h"
 
 static struct kmem_cache *avtab_node_cachep __ro_after_init;
 static struct kmem_cache *avtab_trans_cachep __ro_after_init;
@@ -286,6 +287,19 @@ avtab_search_node_next(struct avtab_node *node, int specified)
 	return NULL;
 }
 
+static int avtab_trans_destroy_helper(void *k, void *d, void *args)
+{
+	kfree(k);
+	kfree(d);
+	return 0;
+}
+
+static void avtab_trans_destroy(struct avtab_trans *trans)
+{
+	hashtab_map(&trans->name_trans.table, avtab_trans_destroy_helper, NULL);
+	hashtab_destroy(&trans->name_trans.table);
+}
+
 void avtab_destroy(struct avtab *h)
 {
 	int i;
@@ -303,6 +317,7 @@ void avtab_destroy(struct avtab *h)
 				kmem_cache_free(avtab_xperms_cachep,
 						temp->datum.u.xperms);
 			} else if (temp->key.specified & AVTAB_TRANSITION) {
+				avtab_trans_destroy(temp->datum.u.trans);
 				kmem_cache_free(avtab_trans_cachep,
 						temp->datum.u.trans);
 			}
@@ -587,6 +602,7 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 	if (key.specified & AVTAB_TRANSITION) {
 		if (!policydb_type_isvalid(pol, datum.u.trans->otype)) {
 			pr_err("SELinux: avtab: invalid transition type\n");
+			avtab_trans_destroy(&trans);
 			return -EINVAL;
 		}
 	} else if (key.specified & AVTAB_TYPE) {
@@ -596,6 +612,8 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		}
 	}
 	rc = insertf(a, &key, &datum, p);
+	if (rc && key.specified & AVTAB_TRANSITION)
+		avtab_trans_destroy(&trans);
 	return rc;
 }
 
@@ -656,6 +674,10 @@ int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
 	int rc;
 	unsigned int i;
 
+	if (cur->key.specified & AVTAB_TRANSITION &&
+	    !cur->datum.u.trans->otype)
+		return 0;
+
 	buf16[0] = cpu_to_le16(cur->key.source_type);
 	buf16[1] = cpu_to_le16(cur->key.target_type);
 	buf16[2] = cpu_to_le16(cur->key.target_class);
@@ -723,3 +745,497 @@ void __init avtab_cache_init(void)
 						sizeof(struct avtab_extended_perms),
 						0, SLAB_PANIC, NULL);
 }
+
+/* policydb filename transitions compatibility */
+
+static int avtab_insert_filename_trans(struct avtab *a,
+				       const struct avtab_key *key,
+				       char *name, u32 otype)
+{
+	int rc;
+	struct avtab_node *node;
+	struct avtab_trans new_trans = {0};
+	struct avtab_datum new_datum = {.u.trans = &new_trans};
+	struct avtab_datum *datum;
+	u32 *otype_datum = NULL;
+
+	datum = avtab_search(a, key);
+	if (!datum) {
+		/*
+		 * insert is acctually unique, but with this function we can get
+		 * the inserted node and therefore the datum
+		 */
+		node = avtab_insert_nonunique(a, key, &new_datum);
+		if (!node)
+			return -ENOMEM;
+		datum = &node->datum;
+	}
+
+	if (hashtab_is_empty(&datum->u.trans->name_trans.table)) {
+		rc = symtab_init(&datum->u.trans->name_trans, 1 << 8);
+		if (rc)
+			return rc;
+	}
+
+	otype_datum = kmalloc(sizeof(u32), GFP_KERNEL);
+	if (!otype_datum)
+		return -ENOMEM;
+	*otype_datum = otype;
+
+	rc = symtab_insert(&datum->u.trans->name_trans, name, otype_datum);
+	if (rc)
+		kfree(otype_datum);
+
+	return rc;
+}
+
+static int filename_trans_read_item(struct avtab *a, void *fp)
+{
+	int rc;
+	__le32 buf32[4];
+	u32 len, otype;
+	char *name = NULL;
+	struct avtab_key key;
+
+	/* read length of the name */
+	rc = next_entry(buf32, fp, sizeof(u32));
+	if (rc)
+		return rc;
+	len = le32_to_cpu(buf32[0]);
+
+	/* read the name */
+	rc = str_read(&name, GFP_KERNEL, fp, len);
+	if (rc)
+		return rc;
+
+	/* read stype, ttype, tclass and otype */
+	rc = next_entry(buf32, fp, sizeof(u32) * 4);
+	if (rc)
+		goto bad;
+
+	key.source_type = le32_to_cpu(buf32[0]);
+	key.target_type = le32_to_cpu(buf32[1]);
+	key.target_class = le32_to_cpu(buf32[2]);
+	key.specified = AVTAB_TRANSITION;
+
+	otype = le32_to_cpu(buf32[3]);
+
+	rc = avtab_insert_filename_trans(a, &key, name, otype);
+	if (rc)
+		goto bad;
+
+	return rc;
+
+bad:
+	kfree(name);
+	return rc;
+}
+
+static int filename_trans_comp_read_item(struct avtab *a, void *fp)
+{
+	int rc;
+	__le32 buf32[3];
+	u32 len, ndatum, i, bit, otype;
+	char *name = NULL, *name_copy = NULL;
+	struct avtab_key key;
+	struct ebitmap stypes;
+	struct ebitmap_node *node;
+
+	/* read length of the name */
+	rc = next_entry(buf32, fp, sizeof(u32));
+	if (rc)
+		return rc;
+	len = le32_to_cpu(*buf32);
+
+	/* read the name */
+	rc = str_read(&name, GFP_KERNEL, fp, len);
+	if (rc)
+		goto out;
+
+	/* read target type, target class and number of elements for key */
+	rc = next_entry(buf32, fp, sizeof(u32) * 3);
+	if (rc)
+		goto out;
+
+	key.specified = AVTAB_TRANSITION;
+	key.target_type = le32_to_cpu(buf32[0]);
+	key.target_class = le32_to_cpu(buf32[1]);
+
+	ndatum = le32_to_cpu(buf32[2]);
+	if (ndatum == 0) {
+		pr_err("SELinux:  Filename transition key with no datum\n");
+		rc = -ENOENT;
+		goto out;
+	}
+
+	for (i = 0; i < ndatum; i++) {
+		rc = ebitmap_read(&stypes, fp);
+		if (rc)
+			goto out;
+
+		rc = next_entry(buf32, fp, sizeof(u32));
+		if (rc) {
+			ebitmap_destroy(&stypes);
+			goto out;
+		}
+		otype = le32_to_cpu(*buf32);
+
+		ebitmap_for_each_positive_bit(&stypes, node, bit) {
+			key.source_type = bit + 1;
+
+			name_copy = kmemdup(name, len + 1, GFP_KERNEL);
+			if (!name_copy) {
+				ebitmap_destroy(&stypes);
+				goto out;
+			}
+
+			rc = avtab_insert_filename_trans(a, &key, name_copy,
+							 otype);
+			if (rc) {
+				ebitmap_destroy(&stypes);
+				kfree(name_copy);
+				goto out;
+			}
+		}
+
+		ebitmap_destroy(&stypes);
+	}
+	rc = 0;
+
+out:
+	kfree(name);
+	return rc;
+}
+
+int avtab_filename_trans_read(struct avtab *a, void *fp, struct policydb *p)
+{
+	int rc;
+	__le32 buf[1];
+	u32 nel, i;
+
+	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
+		return 0;
+
+	rc = next_entry(buf, fp, sizeof(u32));
+	if (rc)
+		return rc;
+	nel = le32_to_cpu(buf[0]);
+
+	if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
+		for (i = 0; i < nel; i++) {
+			rc = filename_trans_read_item(a, fp);
+			if (rc)
+				return rc;
+		}
+	} else {
+		for (i = 0; i < nel; i++) {
+			rc = filename_trans_comp_read_item(a, fp);
+			if (rc)
+				return rc;
+		}
+	}
+
+	return 0;
+}
+
+
+struct filenametr_write_args {
+	void *fp;
+	struct avtab_key *key;
+};
+
+static int filenametr_write_helper(void *k, void *d, void *a)
+{
+	char *name = k;
+	u32 *otype = d;
+	struct filenametr_write_args *args = a;
+	int rc;
+	u32 len;
+	__le32 buf32[4];
+
+	len = strlen(name);
+	buf32[0] = cpu_to_le32(len);
+	rc = put_entry(buf32, sizeof(u32), 1, args->fp);
+	if (rc)
+		return rc;
+
+	rc = put_entry(name, sizeof(char), len, args->fp);
+	if (rc)
+		return rc;
+
+	buf32[0] = cpu_to_le32(args->key->source_type);
+	buf32[1] = cpu_to_le32(args->key->target_type);
+	buf32[2] = cpu_to_le32(args->key->target_class);
+	buf32[3] = cpu_to_le32(*otype);
+
+	rc = put_entry(buf32, sizeof(u32), 4, args->fp);
+	if (rc)
+		return rc;
+
+	return 0;
+}
+
+struct filenametr_key {
+	u32 ttype;		/* parent dir context */
+	u16 tclass;		/* class of new object */
+	const char *name;	/* last path component */
+};
+
+struct filenametr_datum {
+	struct ebitmap stypes;	/* bitmap of source types for this otype */
+	u32 otype;		/* resulting type of new object */
+	struct filenametr_datum *next;	/* record for next otype*/
+};
+
+static int filenametr_comp_write_helper(void *k, void *d, void *fp)
+{
+	struct filenametr_key *key = k;
+	struct filenametr_datum *datum = d;
+	__le32 buf[3];
+	int rc;
+	u32 ndatum, len = strlen(key->name);
+	struct filenametr_datum *cur;
+
+	buf[0] = cpu_to_le32(len);
+	rc = put_entry(buf, sizeof(u32), 1, fp);
+	if (rc)
+		return rc;
+
+	rc = put_entry(key->name, sizeof(char), len, fp);
+	if (rc)
+		return rc;
+
+	ndatum = 0;
+	cur = datum;
+	do {
+		ndatum++;
+		cur = cur->next;
+	} while (unlikely(cur));
+
+	buf[0] = cpu_to_le32(key->ttype);
+	buf[1] = cpu_to_le32(key->tclass);
+	buf[2] = cpu_to_le32(ndatum);
+	rc = put_entry(buf, sizeof(u32), 3, fp);
+	if (rc)
+		return rc;
+
+	cur = datum;
+	do {
+		rc = ebitmap_write(&cur->stypes, fp);
+		if (rc)
+			return rc;
+
+		buf[0] = cpu_to_le32(cur->otype);
+		rc = put_entry(buf, sizeof(u32), 1, fp);
+		if (rc)
+			return rc;
+
+		cur = cur->next;
+	} while (unlikely(cur));
+
+	return 0;
+}
+
+static int filenametr_destroy(void *k, void *d, void *args)
+{
+	struct filenametr_key *key = k;
+	struct filenametr_datum *datum = d;
+	struct filenametr_datum *next;
+
+	kfree(key);
+	do {
+		ebitmap_destroy(&datum->stypes);
+		next = datum->next;
+		kfree(datum);
+		datum = next;
+	} while (unlikely(datum));
+	cond_resched();
+	return 0;
+}
+
+static u32 filenametr_hash(const void *k)
+{
+	const struct filenametr_key *ft = k;
+	unsigned long hash;
+	unsigned int byte_num;
+	unsigned char focus;
+
+	hash = ft->ttype ^ ft->tclass;
+
+	byte_num = 0;
+	while ((focus = ft->name[byte_num++]))
+		hash = partial_name_hash(focus, hash);
+	return hash;
+}
+
+static int filenametr_cmp(const void *k1, const void *k2)
+{
+	const struct filenametr_key *ft1 = k1;
+	const struct filenametr_key *ft2 = k2;
+	int v;
+
+	v = ft1->ttype - ft2->ttype;
+	if (v)
+		return v;
+
+	v = ft1->tclass - ft2->tclass;
+	if (v)
+		return v;
+
+	return strcmp(ft1->name, ft2->name);
+}
+
+static const struct hashtab_key_params filenametr_key_params = {
+	.hash = filenametr_hash,
+	.cmp = filenametr_cmp,
+};
+
+struct filenametr_tab_insert_args {
+	struct avtab_key *key;
+	struct hashtab *tab;
+};
+
+static int filenametr_tab_insert(void *k, void *d, void *a)
+{
+	char *name = k;
+	u32 *otype = d;
+	struct filenametr_tab_insert_args *args	= a;
+	struct filenametr_key key, *ft = NULL;
+	struct filenametr_datum *last, *datum = NULL;
+	int rc;
+
+	key.ttype = args->key->target_type;
+	key.tclass = args->key->target_class;
+	key.name = name;
+
+	last = NULL;
+	datum = hashtab_search(args->tab, &key, filenametr_key_params);
+	while (datum) {
+		if (unlikely(ebitmap_get_bit(&datum->stypes,
+					     args->key->source_type - 1))) {
+			/* conflicting/duplicate rules are ignored */
+			datum = NULL;
+			goto bad;
+		}
+		if (likely(datum->otype == *otype))
+			break;
+		last = datum;
+		datum = datum->next;
+	}
+	if (!datum) {
+		rc = -ENOMEM;
+		datum = kmalloc(sizeof(*datum), GFP_KERNEL);
+		if (!datum)
+			goto bad;
+
+		ebitmap_init(&datum->stypes);
+		datum->otype = *otype;
+		datum->next = NULL;
+
+		if (unlikely(last)) {
+			last->next = datum;
+		} else {
+			rc = -ENOMEM;
+			ft = kmemdup(&key, sizeof(key), GFP_KERNEL);
+			if (!ft)
+				goto bad;
+
+			ft->name = kmemdup(key.name, strlen(key.name) + 1,
+					   GFP_KERNEL);
+			if (!ft->name)
+				goto bad;
+
+			rc = hashtab_insert(args->tab, ft, datum,
+					    filenametr_key_params);
+			if (rc)
+				goto bad;
+		}
+	}
+
+	return ebitmap_set_bit(&datum->stypes, args->key->source_type - 1, 1);
+
+bad:
+	if (ft)
+		kfree(ft->name);
+	kfree(ft);
+	kfree(datum);
+	return rc;
+}
+
+int avtab_filename_trans_write(struct policydb *p, struct avtab *a, void *fp)
+{
+	int rc;
+	__le32 buf32[1];
+	u32 i, nel = 0;
+	struct avtab_node *cur;
+	struct hashtab fnts_tab;
+	struct filenametr_tab_insert_args tab_insert_args = {.tab = &fnts_tab};
+	struct filenametr_write_args write_args = {.fp = fp};
+
+	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
+		return 0;
+
+	/* count number of filename transitions */
+	for (i = 0; i < a->nslot; i++) {
+		for (cur = a->htable[i]; cur; cur = cur->next) {
+			if (cur->key.specified & AVTAB_TRANSITION)
+				nel += cur->datum.u.trans->name_trans.table.nel;
+		}
+	}
+
+	if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
+		buf32[0] = cpu_to_le32(nel);
+		rc = put_entry(buf32, sizeof(u32), 1, fp);
+		if (rc)
+			return rc;
+
+		/* write filename transitions */
+		for (i = 0; i < a->nslot; i++) {
+			for (cur = a->htable[i]; cur; cur = cur->next) {
+				if (cur->key.specified & AVTAB_TRANSITION) {
+					write_args.key = &cur->key;
+					rc = hashtab_map(&cur->datum.u.trans->name_trans.table,
+							 filenametr_write_helper,
+							 &write_args);
+					if (rc)
+						return rc;
+				}
+			}
+		}
+
+		return 0;
+	}
+
+	/* init temp filename transition table */
+	rc = hashtab_init(&fnts_tab, nel);
+	if (rc)
+		return rc;
+
+	for (i = 0; i < a->nslot; i++) {
+		for (cur = a->htable[i]; cur; cur = cur->next) {
+			if (cur->key.specified & AVTAB_TRANSITION) {
+				tab_insert_args.key = &cur->key;
+				rc = hashtab_map(&cur->datum.u.trans->name_trans.table,
+						 filenametr_tab_insert,
+						 &tab_insert_args);
+				if (rc)
+					goto out;
+			}
+		}
+	}
+
+	/* write compressed filename transitions */
+	buf32[0] = cpu_to_le32(fnts_tab.nel);
+	rc = put_entry(buf32, sizeof(u32), 1, fp);
+	if (rc)
+		goto out;
+
+	rc = hashtab_map(&fnts_tab, filenametr_comp_write_helper, fp);
+
+out:
+	/* destroy temp filename transitions table */
+	hashtab_map(&fnts_tab, filenametr_destroy, NULL);
+	hashtab_destroy(&fnts_tab);
+
+	return rc;
+}
diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index 6c8eb7c379cf..162ef1be85e7 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -22,6 +22,7 @@
 #define _SS_AVTAB_H_
 
 #include "security.h"
+#include "symtab.h"
 
 struct avtab_key {
 	u16 source_type;	/* source type */
@@ -49,6 +50,7 @@ struct avtab_key {
 
 struct avtab_trans {
 	u32 otype;		/* default resulting type of the new object */
+	struct symtab name_trans;	/* filename transitions */
 };
 
 /*
@@ -121,5 +123,10 @@ struct avtab_node *avtab_search_node_next(struct avtab_node *node, int specified
 #define MAX_AVTAB_HASH_BITS 16
 #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
 
+/* policydb filename transitions compatibility */
+
+int avtab_filename_trans_read(struct avtab *a, void *fp, struct policydb *p);
+int avtab_filename_trans_write(struct policydb *p, struct avtab *a, void *fp);
+
 #endif	/* _SS_AVTAB_H_ */
 
diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c
index e11219fdf9f7..91392d65563e 100644
--- a/security/selinux/ss/conditional.c
+++ b/security/selinux/ss/conditional.c
@@ -263,6 +263,7 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k,
 	struct policydb *p = data->p;
 	struct cond_av_list *other = data->other;
 	struct avtab_node *node_ptr;
+	struct avtab_datum *existing;
 	u32 i;
 	bool found;
 
@@ -272,7 +273,10 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k,
 	 * cond_te_avtab.
 	 */
 	if (k->specified & AVTAB_TYPE) {
-		if (avtab_search(&p->te_avtab, k)) {
+		existing = avtab_search(&p->te_avtab, k);
+		/* empty transition rule is not a conflict */
+		if (existing && !(k->specified & AVTAB_TRANSITION &&
+				  !existing->u.trans->otype)) {
 			pr_err("SELinux: type rule already exists outside of a conditional.\n");
 			return -EINVAL;
 		}
diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h
index 043a773bf0b7..4d04acf4d5af 100644
--- a/security/selinux/ss/hashtab.h
+++ b/security/selinux/ss/hashtab.h
@@ -145,4 +145,10 @@ int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
 /* Fill info with some hash table statistics */
 void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
 
+/* Checks if the hashtab is empty (its size is zero) */
+static inline int hashtab_is_empty(struct hashtab *h)
+{
+	return !h->size;
+}
+
 #endif	/* _SS_HASHTAB_H */
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 97c0074f9312..928a08835db8 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -323,23 +323,6 @@ static int (*const destroy_f[SYM_NUM]) (void *key, void *datum, void *datap) = {
 	cat_destroy,
 };
 
-static int filenametr_destroy(void *key, void *datum, void *p)
-{
-	struct filename_trans_key *ft = key;
-	struct filename_trans_datum *next, *d = datum;
-
-	kfree(ft->name);
-	kfree(key);
-	do {
-		ebitmap_destroy(&d->stypes);
-		next = d->next;
-		kfree(d);
-		d = next;
-	} while (unlikely(d));
-	cond_resched();
-	return 0;
-}
-
 static int range_tr_destroy(void *key, void *datum, void *p)
 {
 	struct mls_range *rt = datum;
@@ -406,50 +389,6 @@ static int roles_init(struct policydb *p)
 	return rc;
 }
 
-static u32 filenametr_hash(const void *k)
-{
-	const struct filename_trans_key *ft = k;
-	unsigned long hash;
-	unsigned int byte_num;
-	unsigned char focus;
-
-	hash = ft->ttype ^ ft->tclass;
-
-	byte_num = 0;
-	while ((focus = ft->name[byte_num++]))
-		hash = partial_name_hash(focus, hash);
-	return hash;
-}
-
-static int filenametr_cmp(const void *k1, const void *k2)
-{
-	const struct filename_trans_key *ft1 = k1;
-	const struct filename_trans_key *ft2 = k2;
-	int v;
-
-	v = ft1->ttype - ft2->ttype;
-	if (v)
-		return v;
-
-	v = ft1->tclass - ft2->tclass;
-	if (v)
-		return v;
-
-	return strcmp(ft1->name, ft2->name);
-
-}
-
-static const struct hashtab_key_params filenametr_key_params = {
-	.hash = filenametr_hash,
-	.cmp = filenametr_cmp,
-};
-
-struct filename_trans_datum *policydb_filenametr_search(
-	struct policydb *p, struct filename_trans_key *key)
-{
-	return hashtab_search(&p->filename_trans, key, filenametr_key_params);
-}
-
 static u32 rangetr_hash(const void *k)
 {
 	const struct range_trans *key = k;
@@ -531,7 +470,6 @@ static void policydb_init(struct policydb *p)
 	avtab_init(&p->te_avtab);
 	cond_policydb_init(p);
 
-	ebitmap_init(&p->filename_trans_ttypes);
 	ebitmap_init(&p->policycaps);
 	ebitmap_init(&p->permissive_map);
 }
@@ -839,9 +777,6 @@ void policydb_destroy(struct policydb *p)
 	}
 	kfree(lra);
 
-	hashtab_map(&p->filename_trans, filenametr_destroy, NULL);
-	hashtab_destroy(&p->filename_trans);
-
 	hashtab_map(&p->range_tr, range_tr_destroy, NULL);
 	hashtab_destroy(&p->range_tr);
 
@@ -851,7 +786,6 @@ void policydb_destroy(struct policydb *p)
 		kvfree(p->type_attr_map_array);
 	}
 
-	ebitmap_destroy(&p->filename_trans_ttypes);
 	ebitmap_destroy(&p->policycaps);
 	ebitmap_destroy(&p->permissive_map);
 }
@@ -1066,7 +1000,7 @@ static int context_read_and_validate(struct context *c,
  * binary representation file.
  */
 
-static int str_read(char **strp, gfp_t flags, void *fp, u32 len)
+int str_read(char **strp, gfp_t flags, void *fp, u32 len)
 {
 	int rc;
 	char *str;
@@ -1880,220 +1814,6 @@ static int range_read(struct policydb *p, void *fp)
 	return rc;
 }
 
-static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
-{
-	struct filename_trans_key key, *ft = NULL;
-	struct filename_trans_datum *last, *datum = NULL;
-	char *name = NULL;
-	u32 len, stype, otype;
-	__le32 buf[4];
-	int rc;
-
-	/* length of the path component string */
-	rc = next_entry(buf, fp, sizeof(u32));
-	if (rc)
-		return rc;
-	len = le32_to_cpu(buf[0]);
-
-	/* path component string */
-	rc = str_read(&name, GFP_KERNEL, fp, len);
-	if (rc)
-		return rc;
-
-	rc = next_entry(buf, fp, sizeof(u32) * 4);
-	if (rc)
-		goto out;
-
-	stype = le32_to_cpu(buf[0]);
-	key.ttype = le32_to_cpu(buf[1]);
-	key.tclass = le32_to_cpu(buf[2]);
-	key.name = name;
-
-	otype = le32_to_cpu(buf[3]);
-
-	last = NULL;
-	datum = policydb_filenametr_search(p, &key);
-	while (datum) {
-		if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
-			/* conflicting/duplicate rules are ignored */
-			datum = NULL;
-			goto out;
-		}
-		if (likely(datum->otype == otype))
-			break;
-		last = datum;
-		datum = datum->next;
-	}
-	if (!datum) {
-		rc = -ENOMEM;
-		datum = kmalloc(sizeof(*datum), GFP_KERNEL);
-		if (!datum)
-			goto out;
-
-		ebitmap_init(&datum->stypes);
-		datum->otype = otype;
-		datum->next = NULL;
-
-		if (unlikely(last)) {
-			last->next = datum;
-		} else {
-			rc = -ENOMEM;
-			ft = kmemdup(&key, sizeof(key), GFP_KERNEL);
-			if (!ft)
-				goto out;
-
-			rc = hashtab_insert(&p->filename_trans, ft, datum,
-					    filenametr_key_params);
-			if (rc)
-				goto out;
-			name = NULL;
-
-			rc = ebitmap_set_bit(&p->filename_trans_ttypes,
-					     key.ttype, 1);
-			if (rc)
-				return rc;
-		}
-	}
-	kfree(name);
-	return ebitmap_set_bit(&datum->stypes, stype - 1, 1);
-
-out:
-	kfree(ft);
-	kfree(name);
-	kfree(datum);
-	return rc;
-}
-
-static int filename_trans_read_helper(struct policydb *p, void *fp)
-{
-	struct filename_trans_key *ft = NULL;
-	struct filename_trans_datum **dst, *datum, *first = NULL;
-	char *name = NULL;
-	u32 len, ttype, tclass, ndatum, i;
-	__le32 buf[3];
-	int rc;
-
-	/* length of the path component string */
-	rc = next_entry(buf, fp, sizeof(u32));
-	if (rc)
-		return rc;
-	len = le32_to_cpu(buf[0]);
-
-	/* path component string */
-	rc = str_read(&name, GFP_KERNEL, fp, len);
-	if (rc)
-		return rc;
-
-	rc = next_entry(buf, fp, sizeof(u32) * 3);
-	if (rc)
-		goto out;
-
-	ttype = le32_to_cpu(buf[0]);
-	tclass = le32_to_cpu(buf[1]);
-
-	ndatum = le32_to_cpu(buf[2]);
-	if (ndatum == 0) {
-		pr_err("SELinux:  Filename transition key with no datum\n");
-		rc = -ENOENT;
-		goto out;
-	}
-
-	dst = &first;
-	for (i = 0; i < ndatum; i++) {
-		rc = -ENOMEM;
-		datum = kmalloc(sizeof(*datum), GFP_KERNEL);
-		if (!datum)
-			goto out;
-
-		*dst = datum;
-
-		/* ebitmap_read() will at least init the bitmap */
-		rc = ebitmap_read(&datum->stypes, fp);
-		if (rc)
-			goto out;
-
-		rc = next_entry(buf, fp, sizeof(u32));
-		if (rc)
-			goto out;
-
-		datum->otype = le32_to_cpu(buf[0]);
-		datum->next = NULL;
-
-		dst = &datum->next;
-	}
-
-	rc = -ENOMEM;
-	ft = kmalloc(sizeof(*ft), GFP_KERNEL);
-	if (!ft)
-		goto out;
-
-	ft->ttype = ttype;
-	ft->tclass = tclass;
-	ft->name = name;
-
-	rc = hashtab_insert(&p->filename_trans, ft, first,
-			    filenametr_key_params);
-	if (rc == -EEXIST)
-		pr_err("SELinux:  Duplicate filename transition key\n");
-	if (rc)
-		goto out;
-
-	return ebitmap_set_bit(&p->filename_trans_ttypes, ttype, 1);
-
-out:
-	kfree(ft);
-	kfree(name);
-	while (first) {
-		datum = first;
-		first = first->next;
-
-		ebitmap_destroy(&datum->stypes);
-		kfree(datum);
-	}
-	return rc;
-}
-
-static int filename_trans_read(struct policydb *p, void *fp)
-{
-	u32 nel;
-	__le32 buf[1];
-	int rc, i;
-
-	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
-		return 0;
-
-	rc = next_entry(buf, fp, sizeof(u32));
-	if (rc)
-		return rc;
-	nel = le32_to_cpu(buf[0]);
-
-	if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
-		p->compat_filename_trans_count = nel;
-
-		rc = hashtab_init(&p->filename_trans, (1 << 11));
-		if (rc)
-			return rc;
-
-		for (i = 0; i < nel; i++) {
-			rc = filename_trans_read_helper_compat(p, fp);
-			if (rc)
-				return rc;
-		}
-	} else {
-		rc = hashtab_init(&p->filename_trans, nel);
-		if (rc)
-			return rc;
-
-		for (i = 0; i < nel; i++) {
-			rc = filename_trans_read_helper(p, fp);
-			if (rc)
-				return rc;
-		}
-	}
-	hash_eval(&p->filename_trans, "filenametr");
-	return 0;
-}
-
 static int genfs_read(struct policydb *p, void *fp)
 {
 	int i, j, rc;
@@ -2634,7 +2354,7 @@ int policydb_read(struct policydb *p, void *fp)
 		lra = ra;
 	}
 
-	rc = filename_trans_read(p, fp);
+	rc = avtab_filename_trans_read(&p->te_avtab, fp, p);
 	if (rc)
 		goto bad;
 
@@ -3480,119 +3200,6 @@ static int range_write(struct policydb *p, void *fp)
 	return 0;
 }
 
-static int filename_write_helper_compat(void *key, void *data, void *ptr)
-{
-	struct filename_trans_key *ft = key;
-	struct filename_trans_datum *datum = data;
-	struct ebitmap_node *node;
-	void *fp = ptr;
-	__le32 buf[4];
-	int rc;
-	u32 bit, len = strlen(ft->name);
-
-	do {
-		ebitmap_for_each_positive_bit(&datum->stypes, node, bit) {
-			buf[0] = cpu_to_le32(len);
-			rc = put_entry(buf, sizeof(u32), 1, fp);
-			if (rc)
-				return rc;
-
-			rc = put_entry(ft->name, sizeof(char), len, fp);
-			if (rc)
-				return rc;
-
-			buf[0] = cpu_to_le32(bit + 1);
-			buf[1] = cpu_to_le32(ft->ttype);
-			buf[2] = cpu_to_le32(ft->tclass);
-			buf[3] = cpu_to_le32(datum->otype);
-
-			rc = put_entry(buf, sizeof(u32), 4, fp);
-			if (rc)
-				return rc;
-		}
-
-		datum = datum->next;
-	} while (unlikely(datum));
-
-	return 0;
-}
-
-static int filename_write_helper(void *key, void *data, void *ptr)
-{
-	struct filename_trans_key *ft = key;
-	struct filename_trans_datum *datum;
-	void *fp = ptr;
-	__le32 buf[3];
-	int rc;
-	u32 ndatum, len = strlen(ft->name);
-
-	buf[0] = cpu_to_le32(len);
-	rc = put_entry(buf, sizeof(u32), 1, fp);
-	if (rc)
-		return rc;
-
-	rc = put_entry(ft->name, sizeof(char), len, fp);
-	if (rc)
-		return rc;
-
-	ndatum = 0;
-	datum = data;
-	do {
-		ndatum++;
-		datum = datum->next;
-	} while (unlikely(datum));
-
-	buf[0] = cpu_to_le32(ft->ttype);
-	buf[1] = cpu_to_le32(ft->tclass);
-	buf[2] = cpu_to_le32(ndatum);
-	rc = put_entry(buf, sizeof(u32), 3, fp);
-	if (rc)
-		return rc;
-
-	datum = data;
-	do {
-		rc = ebitmap_write(&datum->stypes, fp);
-		if (rc)
-			return rc;
-
-		buf[0] = cpu_to_le32(datum->otype);
-		rc = put_entry(buf, sizeof(u32), 1, fp);
-		if (rc)
-			return rc;
-
-		datum = datum->next;
-	} while (unlikely(datum));
-
-	return 0;
-}
-
-static int filename_trans_write(struct policydb *p, void *fp)
-{
-	__le32 buf[1];
-	int rc;
-
-	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
-		return 0;
-
-	if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
-		buf[0] = cpu_to_le32(p->compat_filename_trans_count);
-		rc = put_entry(buf, sizeof(u32), 1, fp);
-		if (rc)
-			return rc;
-
-		rc = hashtab_map(&p->filename_trans,
-				 filename_write_helper_compat, fp);
-	} else {
-		buf[0] = cpu_to_le32(p->filename_trans.nel);
-		rc = put_entry(buf, sizeof(u32), 1, fp);
-		if (rc)
-			return rc;
-
-		rc = hashtab_map(&p->filename_trans, filename_write_helper, fp);
-	}
-	return rc;
-}
-
 /*
  * Write the configuration data in a policy database
  * structure to a policy database binary representation
@@ -3703,7 +3310,7 @@ int policydb_write(struct policydb *p, void *fp)
 	if (rc)
 		return rc;
 
-	rc = filename_trans_write(p, fp);
+	rc = avtab_filename_trans_write(p, &p->te_avtab, fp);
 	if (rc)
 		return rc;
 
diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
index ffc4e7bad205..2ecb24a1611a 100644
--- a/security/selinux/ss/policydb.h
+++ b/security/selinux/ss/policydb.h
@@ -91,18 +91,6 @@ struct role_trans_datum {
 	u32 new_role;		/* new role */
 };
 
-struct filename_trans_key {
-	u32 ttype;		/* parent dir context */
-	u16 tclass;		/* class of new object */
-	const char *name;	/* last path component */
-};
-
-struct filename_trans_datum {
-	struct ebitmap stypes;	/* bitmap of source types for this otype */
-	u32 otype;		/* resulting type of new object */
-	struct filename_trans_datum *next;	/* record for next otype*/
-};
-
 struct role_allow {
 	u32 role;		/* current role */
 	u32 new_role;		/* new role */
@@ -265,14 +253,6 @@ struct policydb {
 	/* role transitions */
 	struct hashtab role_tr;
 
-	/* file transitions with the last path component */
-	/* quickly exclude lookups when parent ttype has no rules */
-	struct ebitmap filename_trans_ttypes;
-	/* actual set of filename_trans rules */
-	struct hashtab filename_trans;
-	/* only used if policyvers < POLICYDB_VERSION_COMP_FTRANS */
-	u32 compat_filename_trans_count;
-
 	/* bools indexed by (value - 1) */
 	struct cond_bool_datum **bool_val_to_struct;
 	/* type enforcement conditional access vectors and transitions */
@@ -324,9 +304,6 @@ 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);
 
-extern struct filename_trans_datum *policydb_filenametr_search(
-	struct policydb *p, struct filename_trans_key *key);
-
 extern struct mls_range *policydb_rangetr_search(
 	struct policydb *p, struct range_trans *key);
 
@@ -379,6 +356,8 @@ static inline int put_entry(const void *buf, size_t bytes, int num, struct polic
 	return 0;
 }
 
+extern int str_read(char **strp, gfp_t flags, void *fp, u32 len);
+
 static inline char *sym_name(struct policydb *p, unsigned int sym_num, unsigned int element_nr)
 {
 	return p->sym_val_to_name[sym_num][element_nr];
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index 8ed12406acba..131647e7ec68 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1661,36 +1661,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_key ft;
-	struct filename_trans_datum *datum;
-
-	/*
-	 * 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.ttype = ttype;
-	ft.tclass = tclass;
-	ft.name = objname;
-
-	datum = policydb_filenametr_search(policydb, &ft);
-	while (datum) {
-		if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
-			newcontext->type = datum->otype;
-			return;
-		}
-		datum = datum->next;
-	}
-}
-
 static int security_compute_sid(u32 ssid,
 				u32 tsid,
 				u16 orig_tclass,
@@ -1711,6 +1681,7 @@ static int security_compute_sid(u32 ssid,
 	u16 tclass;
 	int rc = 0;
 	bool sock;
+	u32 *otype;
 
 	if (!selinux_initialized()) {
 		switch (orig_tclass) {
@@ -1830,17 +1801,24 @@ static int security_compute_sid(u32 ssid,
 
 	if (avdatum) {
 		/* Use the type from the type transition/member/change rule. */
-		if (avkey.specified & AVTAB_TRANSITION)
-			newcontext.type = avdatum->u.trans->otype;
-		else
+		if (avkey.specified & AVTAB_TRANSITION) {
+			/*
+			 * use default otype if not empty and then to try to
+			 * find more specific rule using objname
+			 */
+			if (avdatum->u.trans->otype)
+				newcontext.type = avdatum->u.trans->otype;
+			if (objname) {
+				otype = symtab_search(&avdatum->u.trans->name_trans,
+						      objname);
+				if (otype)
+					newcontext.type = *otype;
+			}
+		} else {
 			newcontext.type = avdatum->u.data;
+		}
 	}
 
-	/* 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);
-
 	/* Check for class-specific changes. */
 	if (specified & AVTAB_TRANSITION) {
 		/* Look for a role transition rule. */
-- 
2.40.0

[PATCH 3/5] selinux: implement new binary format for filename transitions in avtab

[Juraj Marcin]

Implement a new binary policy format that closely matches the new
internal representation introduced in the previous patch.

This patch bumps the maximum kernel policy version and implements
reading/writing functions such that kernel binary policy structure
matches internal representation.

These changes cause the binary policy to grow in size due to effectively
undoing the benefits of the commit 430059024389 ("selinux: implement new
format of filename transitions"), as well as increase its loading time,
but this will be mitigated by adding the prefix/suffix support as
described in the previous patch.

Kernel     | Policy file  |  Policy size | Policy load
           | version      |              | time
-----------+--------------+--------------+-------------
reference  |           33 |       3.5 MB |       78 ms
prev patch |           33 |       3.5 MB |      230 ms
this patch |           34 |       5.5 MB |      113 ms

Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
---
 security/selinux/include/security.h |   3 +-
 security/selinux/ss/avtab.c         | 189 ++++++++++++++++++++++++++--
 security/selinux/ss/policydb.c      |  21 +++-
 3 files changed, 195 insertions(+), 18 deletions(-)

diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
index 8746fafeb778..c483680fe22e 100644
--- a/security/selinux/include/security.h
+++ b/security/selinux/include/security.h
@@ -46,10 +46,11 @@
 #define POLICYDB_VERSION_INFINIBAND		31
 #define POLICYDB_VERSION_GLBLUB		32
 #define POLICYDB_VERSION_COMP_FTRANS	33 /* compressed filename transitions */
+#define POLICYDB_VERSION_AVTAB_FTRANS	34 /* filename transitions moved to avtab */
 
 /* Range of policy versions we understand*/
 #define POLICYDB_VERSION_MIN   POLICYDB_VERSION_BASE
-#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_COMP_FTRANS
+#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_AVTAB_FTRANS
 
 /* Mask for just the mount related flags */
 #define SE_MNTMASK	0x0f
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index fe921e1586e5..2cd9eabf796c 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -426,6 +426,95 @@ static const uint16_t spec_order[] = {
 	AVTAB_XPERMS_DONTAUDIT
 };
 
+static int avtab_trans_read_name_trans(struct policydb *pol,
+					   struct symtab *target, void *fp)
+{
+	int rc;
+	__le32 buf32[2];
+	u32 nfnts, i, len, *fnt_otype = NULL;
+	char *name = NULL;
+
+	/* read number of name transitions */
+	rc = next_entry(buf32, fp, sizeof(u32));
+	if (rc)
+		return rc;
+	nfnts = le32_to_cpu(buf32[0]);
+
+	rc = symtab_init(target, nfnts);
+	if (rc)
+		return rc;
+
+	/* read name transitions */
+	for (i = 0; i < nfnts; i++) {
+		rc = -ENOMEM;
+		fnt_otype = kmalloc(sizeof(u32), GFP_KERNEL);
+		if (!fnt_otype)
+			goto exit;
+
+		/* read name transition otype and name length */
+		rc = next_entry(buf32, fp, sizeof(u32) * 2);
+		if (rc)
+			goto exit;
+		*fnt_otype = le32_to_cpu(buf32[0]);
+		len = le32_to_cpu(buf32[1]);
+		if (!policydb_type_isvalid(pol, *fnt_otype)) {
+			pr_err("SELinux: avtab: invalid filename transition type\n");
+			rc = -EINVAL;
+			goto exit;
+		}
+
+		/* read the name */
+		rc = str_read(&name, GFP_KERNEL, fp, len);
+		if (rc)
+			goto exit;
+
+		/* insert to the table */
+		rc = symtab_insert(target, name, fnt_otype);
+		if (rc)
+			goto exit;
+		name = NULL;
+		fnt_otype = NULL;
+	}
+
+exit:
+	kfree(fnt_otype);
+	kfree(name);
+	return rc;
+}
+
+static int avtab_trans_read(void *fp, struct policydb *pol,
+			    struct avtab_trans *trans)
+{
+	int rc;
+	__le32 buf32[1];
+
+	if (pol->policyvers < POLICYDB_VERSION_AVTAB_FTRANS) {
+		rc = next_entry(buf32, fp, sizeof(u32));
+		if (rc) {
+			pr_err("SELinux: avtab: truncated entry\n");
+			return rc;
+		}
+		trans->otype = le32_to_cpu(*buf32);
+		return 0;
+	}
+
+	/* read default otype */
+	rc = next_entry(buf32, fp, sizeof(u32));
+	if (rc)
+		return rc;
+	trans->otype = le32_to_cpu(buf32[0]);
+
+	rc = avtab_trans_read_name_trans(pol, &trans->name_trans, fp);
+	if (rc)
+		goto bad;
+
+	return 0;
+
+bad:
+	avtab_trans_destroy(trans);
+	return rc;
+}
+
 int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		    int (*insertf)(struct avtab *a, const struct avtab_key *k,
 				   const struct avtab_datum *d, void *p),
@@ -433,7 +522,7 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 {
 	__le16 buf16[4];
 	u16 enabled;
-	u32 items, items2, val, vers = pol->policyvers;
+	u32 otype, items, items2, val, vers = pol->policyvers;
 	struct avtab_key key;
 	struct avtab_datum datum;
 	struct avtab_trans trans;
@@ -584,12 +673,9 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		datum.u.xperms = &xperms;
 	} else if (key.specified & AVTAB_TRANSITION) {
 		memset(&trans, 0, sizeof(struct avtab_trans));
-		rc = next_entry(buf32, fp, sizeof(u32));
-		if (rc) {
-			pr_err("SELinux: avtab: truncated entry\n");
+		rc = avtab_trans_read(fp, pol, &trans);
+		if (rc)
 			return rc;
-		}
-		trans.otype = le32_to_cpu(*buf32);
 		datum.u.trans = &trans;
 	} else {
 		rc = next_entry(buf32, fp, sizeof(u32));
@@ -600,11 +686,24 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		datum.u.data = le32_to_cpu(*buf32);
 	}
 	if (key.specified & AVTAB_TRANSITION) {
-		if (!policydb_type_isvalid(pol, datum.u.trans->otype)) {
+		/* if otype is set (non-zero), it must by a valid type */
+		otype = datum.u.trans->otype;
+		if (otype && !policydb_type_isvalid(pol, otype)) {
 			pr_err("SELinux: avtab: invalid transition type\n");
 			avtab_trans_destroy(&trans);
 			return -EINVAL;
 		}
+		/*
+		 * also each transition entry must meet at least one condition
+		 * to be considered non-empty:
+		 *  - set (non-zero) otype
+		 *  - non-empty filename transitions table
+		 */
+		if (!otype && !datum.u.trans->name_trans.table.nel) {
+			pr_err("SELinux: avtab: empty transition\n");
+			avtab_trans_destroy(&trans);
+			return -EINVAL;
+		}
 	} else if (key.specified & AVTAB_TYPE) {
 		if (!policydb_type_isvalid(pol, datum.u.data)) {
 			pr_err("SELinux: avtab: invalid type\n");
@@ -667,6 +766,59 @@ int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
 	goto out;
 }
 
+static int avtab_trans_write_helper(void *k, void *d, void *fp)
+{
+	char *name = k;
+	u32 *otype = d;
+	int rc;
+	__le32 buf32[2];
+	u32 len;
+
+	/* write filename transition otype and name length */
+	len = strlen(name);
+	buf32[0] = cpu_to_le32(*otype);
+	buf32[1] = cpu_to_le32(len);
+	rc = put_entry(buf32, sizeof(u32), 2, fp);
+	if (rc)
+		return rc;
+
+	/* write filename transition name */
+	rc = put_entry(name, sizeof(char), len, fp);
+	if (rc)
+		return rc;
+
+	return 0;
+}
+
+static int avtab_trans_write(struct policydb *p, struct avtab_trans *cur,
+			     void *fp)
+{
+	int rc;
+	__le32 buf32[2];
+
+	if (p->policyvers >= POLICYDB_VERSION_AVTAB_FTRANS) {
+		/* write otype and number of filename transitions */
+		buf32[0] = cpu_to_le32(cur->otype);
+		buf32[1] = cpu_to_le32(cur->name_trans.table.nel);
+		rc = put_entry(buf32, sizeof(u32), 2, fp);
+		if (rc)
+			return rc;
+
+		/* write filename transitions */
+		rc = hashtab_map(&cur->name_trans.table,
+				 avtab_trans_write_helper, fp);
+		if (rc)
+			return rc;
+	} else if (cur->otype) {
+		buf32[0] = cpu_to_le32(cur->otype);
+		rc = put_entry(buf32, sizeof(u32), 1, fp);
+		if (rc)
+			return rc;
+	}
+
+	return 0;
+}
+
 int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
 {
 	__le16 buf16[4];
@@ -674,7 +826,8 @@ int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
 	int rc;
 	unsigned int i;
 
-	if (cur->key.specified & AVTAB_TRANSITION &&
+	if (p->policyvers < POLICYDB_VERSION_AVTAB_FTRANS &&
+	    cur->key.specified & AVTAB_TRANSITION &&
 	    !cur->datum.u.trans->otype)
 		return 0;
 
@@ -698,8 +851,7 @@ int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
 		rc = put_entry(buf32, sizeof(u32),
 				ARRAY_SIZE(cur->datum.u.xperms->perms.p), fp);
 	} else if (cur->key.specified & AVTAB_TRANSITION) {
-		buf32[0] = cpu_to_le32(cur->datum.u.trans->otype);
-		rc = put_entry(buf32, sizeof(u32), 1, fp);
+		rc = avtab_trans_write(p, cur->datum.u.trans, fp);
 	} else {
 		buf32[0] = cpu_to_le32(cur->datum.u.data);
 		rc = put_entry(buf32, sizeof(u32), 1, fp);
@@ -715,8 +867,23 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp)
 	int rc = 0;
 	struct avtab_node *cur;
 	__le32 buf[1];
+	u32 nel;
 
-	buf[0] = cpu_to_le32(a->nel);
+	nel = a->nel;
+	if (p->policyvers < POLICYDB_VERSION_AVTAB_FTRANS) {
+		/*
+		 * in older version, skip entries with only filename transition,
+		 * as these are written out separately
+		 */
+		for (i = 0; i < a->nslot; i++) {
+			for (cur = a->htable[i]; cur; cur = cur->next) {
+				if (cur->key.specified & AVTAB_TRANSITION &&
+				    !cur->datum.u.trans->otype)
+					nel--;
+			}
+		}
+	}
+	buf[0] = cpu_to_le32(nel);
 	rc = put_entry(buf, sizeof(u32), 1, fp);
 	if (rc)
 		return rc;
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 928a08835db8..96b8d5bd8e4e 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -157,6 +157,11 @@ static const struct policydb_compat_info policydb_compat[] = {
 		.sym_num	= SYM_NUM,
 		.ocon_num	= OCON_NUM,
 	},
+	{
+		.version	= POLICYDB_VERSION_AVTAB_FTRANS,
+		.sym_num	= SYM_NUM,
+		.ocon_num	= OCON_NUM,
+	},
 };
 
 static const struct policydb_compat_info *policydb_lookup_compat(int version)
@@ -2354,9 +2359,11 @@ int policydb_read(struct policydb *p, void *fp)
 		lra = ra;
 	}
 
-	rc = avtab_filename_trans_read(&p->te_avtab, fp, p);
-	if (rc)
-		goto bad;
+	if (p->policyvers < POLICYDB_VERSION_AVTAB_FTRANS) {
+		rc = avtab_filename_trans_read(&p->te_avtab, fp, p);
+		if (rc)
+			goto bad;
+	}
 
 	rc = policydb_index(p);
 	if (rc)
@@ -3310,9 +3317,11 @@ int policydb_write(struct policydb *p, void *fp)
 	if (rc)
 		return rc;
 
-	rc = avtab_filename_trans_write(p, &p->te_avtab, fp);
-	if (rc)
-		return rc;
+	if (p->policyvers < POLICYDB_VERSION_AVTAB_FTRANS) {
+		rc = avtab_filename_trans_write(p, &p->te_avtab, fp);
+		if (rc)
+			return rc;
+	}
 
 	rc = ocontext_write(p, info, fp);
 	if (rc)
-- 
2.40.0

[PATCH 4/5] selinux: filename transitions move tests

[Juraj Marcin]

This patch adds a set of simple tests that test if the functions for
reading and writing filename transitions in avtab work properly.

Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
---
 security/selinux/Kconfig         |  17 +
 security/selinux/Makefile        |   2 +
 security/selinux/ss/avtab.c      |  20 +
 security/selinux/ss/avtab_test.c | 729 +++++++++++++++++++++++++++++++
 security/selinux/ss/symtab.c     |   3 +
 5 files changed, 771 insertions(+)
 create mode 100644 security/selinux/ss/avtab_test.c

diff --git a/security/selinux/Kconfig b/security/selinux/Kconfig
index 95a186ec0fcb..78cdc8d4232d 100644
--- a/security/selinux/Kconfig
+++ b/security/selinux/Kconfig
@@ -68,3 +68,20 @@ config SECURITY_SELINUX_SID2STR_CACHE_SIZE
 	  conversion.  Setting this option to 0 disables the cache completely.
 
 	  If unsure, keep the default value.
+
+config SECURITY_SELINUX_KUNIT_TEST
+	tristate "Tests for SELinux" if !KUNIT_ALL_TESTS
+	depends on KUNIT && SECURITY_SELINUX
+	default KUNIT_ALL_TESTS
+	help
+	  This builds the SELinux KUnit tests.
+
+	  KUnit tests run during boot and output the results to the debug log
+	  in TAP format (https://testanything.org/). Only useful for kernel devs
+	  running KUnit test harness and are not for inclusion into a
+	  production build.
+
+	  For more information on KUnit and unit tests in general please refer
+	  to the KUnit documentation in Documentation/dev-tools/kunit/.
+
+	  If unsure, say N.
diff --git a/security/selinux/Makefile b/security/selinux/Makefile
index ab8c3093d5fd..d3d63b28edcf 100644
--- a/security/selinux/Makefile
+++ b/security/selinux/Makefile
@@ -27,3 +27,5 @@ quiet_cmd_genhdrs = GEN     $(addprefix $(obj)/,$(genhdrs))
 targets += $(genhdrs)
 $(addprefix $(obj)/,$(genhdrs)) &: scripts/selinux/genheaders/genheaders FORCE
 	$(call if_changed,genhdrs)
+
+obj-$(CONFIG_SECURITY_SELINUX_KUNIT_TEST) += ss/avtab_test.o
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 2cd9eabf796c..db7123670ef8 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -223,6 +223,9 @@ struct avtab_datum *avtab_search(struct avtab *h, const struct avtab_key *key)
 	return NULL;
 }
 
+/* Export for avtab KUnit tests */
+EXPORT_SYMBOL_GPL(avtab_search);
+
 /* This search function returns a node pointer, and can be used in
  * conjunction with avtab_search_next_node()
  */
@@ -331,6 +334,9 @@ void avtab_destroy(struct avtab *h)
 	h->mask = 0;
 }
 
+/* Export for avtab KUnit tests */
+EXPORT_SYMBOL_GPL(avtab_destroy);
+
 void avtab_init(struct avtab *h)
 {
 	h->htable = NULL;
@@ -378,6 +384,9 @@ int avtab_alloc(struct avtab *h, u32 nrules)
 	return 0;
 }
 
+/* Export for avtab KUnit tests */
+EXPORT_SYMBOL_GPL(avtab_alloc);
+
 int avtab_alloc_dup(struct avtab *new, const struct avtab *orig)
 {
 	return avtab_alloc_common(new, orig->nslot);
@@ -766,6 +775,9 @@ int avtab_read(struct avtab *a, void *fp, struct policydb *pol)
 	goto out;
 }
 
+/* Export for avtab KUnit tests */
+EXPORT_SYMBOL_GPL(avtab_read);
+
 static int avtab_trans_write_helper(void *k, void *d, void *fp)
 {
 	char *name = k;
@@ -900,6 +912,9 @@ int avtab_write(struct policydb *p, struct avtab *a, void *fp)
 	return rc;
 }
 
+/* Export for avtab KUnit tests */
+EXPORT_SYMBOL_GPL(avtab_write);
+
 void __init avtab_cache_init(void)
 {
 	avtab_node_cachep = kmem_cache_create("avtab_node",
@@ -1105,6 +1120,8 @@ int avtab_filename_trans_read(struct avtab *a, void *fp, struct policydb *p)
 	return 0;
 }
 
+/* Export for avtab KUnit tests */
+EXPORT_SYMBOL_GPL(avtab_filename_trans_read);
 
 struct filenametr_write_args {
 	void *fp;
@@ -1406,3 +1423,6 @@ int avtab_filename_trans_write(struct policydb *p, struct avtab *a, void *fp)
 
 	return rc;
 }
+
+/* Export for avtab KUnit tests */
+EXPORT_SYMBOL_GPL(avtab_filename_trans_write);
diff --git a/security/selinux/ss/avtab_test.c b/security/selinux/ss/avtab_test.c
new file mode 100644
index 000000000000..daa8e4cfaeb2
--- /dev/null
+++ b/security/selinux/ss/avtab_test.c
@@ -0,0 +1,729 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * KUnit tests for access vector table type Implementation
+ *
+ * Author: Juraj Marcin <juraj@jurajmarcin.com>
+ */
+
+#include <kunit/test.h>
+#include "policydb.h"
+#include "security.h"
+#include "avtab.h"
+
+static void filename_trans_read__pre_filename_trans(struct kunit *test)
+{
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_FILENAME_TRANS - 1,
+	};
+	struct policy_file fp = {
+		.data = NULL,
+		.len = 0,
+	};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+
+	KUNIT_EXPECT_EQ(test, 0,
+			avtab_filename_trans_read(&p.te_avtab, &fp, &p));
+	KUNIT_EXPECT_EQ(test, 0, p.te_avtab.nel);
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+}
+
+static void filename_trans_read__empty(struct kunit *test)
+{
+	char data[] = {0, 0, 0, 0};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_FILENAME_TRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+
+	KUNIT_EXPECT_EQ(test, 0,
+			avtab_filename_trans_read(&p.te_avtab, &fp, &p));
+	KUNIT_EXPECT_EQ(test, 0, p.te_avtab.nel);
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+}
+
+static void filename_trans_read__comp_empty(struct kunit *test)
+{
+	char data[] = {0, 0, 0, 0};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_COMP_FTRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+
+	KUNIT_EXPECT_EQ(test, 0,
+			avtab_filename_trans_read(&p.te_avtab, &fp, &p));
+	KUNIT_EXPECT_EQ(test, 0, p.te_avtab.nel);
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+}
+
+static void filename_trans_read__simple(struct kunit *test)
+{
+	char data[] = {
+		3, 0, 0, 0,	/* count */
+
+		5, 0, 0, 0,			/* entry 1 name len */
+		'f', 'i', 'l', 'e', '1',	/* entry 1 name */
+		42, 0, 0, 0,			/* entry 1 stype */
+		43, 0, 0, 0,			/* entry 1 ttype */
+		44, 0, 0, 0,			/* entry 1 tclass */
+		45, 0, 0, 0,			/* entry 1 otype */
+
+		5, 0, 0, 0,			/* entry 2 name len */
+		'f', 'i', 'l', 'e', '2',	/* entry 2 name */
+		46, 0, 0, 0,			/* entry 2 stype */
+		47, 0, 0, 0,			/* entry 2 ttype */
+		48, 0, 0, 0,			/* entry 2 tclass */
+		49, 0, 0, 0,			/* entry 2 otype */
+
+		5, 0, 0, 0,			/* entry 3 name len */
+		'f', 'i', 'l', 'e', '3',	/* entry 3 name */
+		46, 0, 0, 0,			/* entry 3 stype */
+		47, 0, 0, 0,			/* entry 3 ttype */
+		48, 0, 0, 0,			/* entry 3 tclass */
+		53, 0, 0, 0,			/* entry 3 otype */
+	};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_FILENAME_TRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+	struct avtab_key key;
+	struct avtab_datum *node;
+	u32 *otype;
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+	KUNIT_ASSERT_EQ(test, 0, avtab_alloc(&p.te_avtab, 3));
+
+	KUNIT_ASSERT_EQ(test, 0,
+			avtab_filename_trans_read(&p.te_avtab, &fp, &p));
+	KUNIT_EXPECT_EQ(test, 2, p.te_avtab.nel);
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+
+	key = (struct avtab_key){42, 43, 44, AVTAB_TRANSITION};
+	node = avtab_search(&p.te_avtab, &key);
+	KUNIT_ASSERT_NOT_NULL(test, node);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->otype);
+	KUNIT_EXPECT_EQ(test, 1, node->u.trans->name_trans.table.nel);
+
+	otype = symtab_search(&node->u.trans->name_trans, "file1");
+	KUNIT_ASSERT_NOT_NULL(test, otype);
+	KUNIT_EXPECT_EQ(test, 45, *otype);
+
+	key = (struct avtab_key){46, 47, 48, AVTAB_TRANSITION};
+	node = avtab_search(&p.te_avtab, &key);
+	KUNIT_ASSERT_NOT_NULL(test, node);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->otype);
+	KUNIT_EXPECT_EQ(test, 2, node->u.trans->name_trans.table.nel);
+
+	otype = symtab_search(&node->u.trans->name_trans, "file2");
+	KUNIT_ASSERT_NOT_NULL(test, otype);
+	KUNIT_EXPECT_EQ(test, 49, *otype);
+
+	otype = symtab_search(&node->u.trans->name_trans, "file3");
+	KUNIT_ASSERT_NOT_NULL(test, otype);
+	KUNIT_EXPECT_EQ(test, 53, *otype);
+
+	avtab_destroy(&p.te_avtab);
+}
+
+static void filename_trans_read__comp_simple(struct kunit *test)
+{
+	char data[] = {
+		3, 0, 0, 0,	/* count */
+
+		5, 0, 0, 0,			/* entry 1 name len */
+		'f', 'i', 'l', 'e', '1',	/* entry 1 name */
+		43, 0, 0, 0,			/* entry 1 ttype */
+		44, 0, 0, 0,			/* entry 1 tclass */
+		1, 0, 0, 0,			/* entry 1 ndatum */
+		64, 0, 0, 0,			/* entry 1 datum 1 stypes */
+		64, 0, 0, 0,
+		1, 0, 0, 0,
+		0, 0, 0, 0,
+		0, 0, 0, 0, 0, 2, 0, 0,
+		45, 0, 0, 0,			/* entry 1 otype */
+
+		5, 0, 0, 0,			/* entry 2 name len */
+		'f', 'i', 'l', 'e', '2',	/* entry 2 name */
+		47, 0, 0, 0,			/* entry 2 ttype */
+		48, 0, 0, 0,			/* entry 2 tclass */
+		1, 0, 0, 0,			/* entry 2 ndatum */
+		64, 0, 0, 0,			/* entry 2 datum 1 stypes */
+		64, 0, 0, 0,
+		1, 0, 0, 0,
+		0, 0, 0, 0,
+		0, 0, 0, 0, 0, 32, 0, 0,
+		49, 0, 0, 0,			/* entry 2 otype */
+
+		5, 0, 0, 0,			/* entry 3 name len */
+		'f', 'i', 'l', 'e', '3',	/* entry 3 name */
+		47, 0, 0, 0,			/* entry 3 ttype */
+		48, 0, 0, 0,			/* entry 3 tclass */
+		1, 0, 0, 0,			/* entry 2 ndatum */
+		64, 0, 0, 0,			/* entry 2 datum 1 stypes */
+		64, 0, 0, 0,
+		1, 0, 0, 0,
+		0, 0, 0, 0,
+		0, 0, 0, 0, 0, 32, 0, 0,
+		53, 0, 0, 0,			/* entry 3 otype */
+	};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_COMP_FTRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+	struct avtab_key key;
+	struct avtab_datum *node;
+	u32 *otype;
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+	KUNIT_ASSERT_EQ(test, 0, avtab_alloc(&p.te_avtab, 3));
+
+	KUNIT_ASSERT_EQ(test, 0,
+			avtab_filename_trans_read(&p.te_avtab, &fp, &p));
+	KUNIT_EXPECT_EQ(test, 2, p.te_avtab.nel);
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+
+	key = (struct avtab_key){42, 43, 44, AVTAB_TRANSITION};
+	node = avtab_search(&p.te_avtab, &key);
+	KUNIT_ASSERT_NOT_NULL(test, node);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->otype);
+	KUNIT_EXPECT_EQ(test, 1, node->u.trans->name_trans.table.nel);
+
+	otype = symtab_search(&node->u.trans->name_trans, "file1");
+	KUNIT_ASSERT_NOT_NULL(test, otype);
+	KUNIT_EXPECT_EQ(test, 45, *otype);
+
+	key = (struct avtab_key){46, 47, 48, AVTAB_TRANSITION};
+	node = avtab_search(&p.te_avtab, &key);
+	KUNIT_ASSERT_NOT_NULL(test, node);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->otype);
+	KUNIT_EXPECT_EQ(test, 2, node->u.trans->name_trans.table.nel);
+
+	otype = symtab_search(&node->u.trans->name_trans, "file2");
+	KUNIT_ASSERT_NOT_NULL(test, otype);
+	KUNIT_EXPECT_EQ(test, 49, *otype);
+
+	otype = symtab_search(&node->u.trans->name_trans, "file3");
+	KUNIT_ASSERT_NOT_NULL(test, otype);
+	KUNIT_EXPECT_EQ(test, 53, *otype);
+
+	avtab_destroy(&p.te_avtab);
+}
+
+static void filename_trans_write__pre_filename_trans(struct kunit *test)
+{
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_FILENAME_TRANS - 1,
+	};
+	struct policy_file fp = {
+		.data = NULL,
+		.len = 0,
+	};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+
+	KUNIT_EXPECT_EQ(test, 0,
+			avtab_filename_trans_write(&p, &p.te_avtab, &fp));
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+}
+
+static void filename_trans_write__empty(struct kunit *test)
+{
+	char expected_data[] = {0, 0, 0, 0};
+	char data[sizeof(expected_data)] = {0};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_FILENAME_TRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+
+	KUNIT_ASSERT_EQ(test, 0,
+			avtab_filename_trans_write(&p, &p.te_avtab, &fp));
+
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+	KUNIT_EXPECT_TRUE(test,
+			  !memcmp(expected_data, data, sizeof(expected_data)));
+}
+
+static void filename_trans_write__comp_empty(struct kunit *test)
+{
+	char expected_data[] = {0, 0, 0, 0};
+	char data[sizeof(expected_data)] = {0};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_COMP_FTRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+
+	KUNIT_ASSERT_EQ(test, 0,
+			avtab_filename_trans_write(&p, &p.te_avtab, &fp));
+
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+	KUNIT_EXPECT_TRUE(test,
+			  !memcmp(expected_data, data, sizeof(expected_data)));
+}
+
+static void filename_trans_write__simple(struct kunit *test)
+{
+	char expected_data[] = {
+		3, 0, 0, 0,	/* count */
+
+		5, 0, 0, 0,			/* entry 1 name len */
+		'f', 'i', 'l', 'e', '1',	/* entry 1 name */
+		42, 0, 0, 0,			/* entry 1 stype */
+		43, 0, 0, 0,			/* entry 1 ttype */
+		44, 0, 0, 0,			/* entry 1 tclass */
+		45, 0, 0, 0,			/* entry 1 otype */
+
+		5, 0, 0, 0,			/* entry 2 name len */
+		'f', 'i', 'l', 'e', '2',	/* entry 2 name */
+		46, 0, 0, 0,			/* entry 2 stype */
+		47, 0, 0, 0,			/* entry 2 ttype */
+		48, 0, 0, 0,			/* entry 2 tclass */
+		49, 0, 0, 0,			/* entry 2 otype */
+
+		5, 0, 0, 0,			/* entry 3 name len */
+		'f', 'i', 'l', 'e', '3',	/* entry 3 name */
+		46, 0, 0, 0,			/* entry 3 stype */
+		47, 0, 0, 0,			/* entry 3 ttype */
+		48, 0, 0, 0,			/* entry 3 tclass */
+		53, 0, 0, 0,			/* entry 3 otype */
+	};
+	char data[sizeof(expected_data)] = {0};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_FILENAME_TRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+	u32 otypes[] = {45, 49, 53};
+	struct hashtab_node nhnodes[] = {
+		{"file1", &otypes[0], NULL},
+		{"file2", &otypes[1], &nhnodes[2]},
+		{"file3", &otypes[2], NULL},
+	};
+	struct hashtab_node *nhtable[] = {&nhnodes[0], &nhnodes[1]};
+	struct avtab_trans transs[] = {
+		{0, {{&nhtable[0], 1, 1}, 0}},
+		{0, {{&nhtable[1], 1, 2}, 0}},
+	};
+	struct avtab_node nodes[] = {
+		{{42, 43, 44, AVTAB_TRANSITION},
+			{.u.trans = &transs[0]}, NULL},
+		{{46, 47, 48, AVTAB_TRANSITION},
+			{.u.trans = &transs[1]}, NULL},
+	};
+	struct avtab_node *htable[] = {&nodes[0], &nodes[1]};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+	p.te_avtab.htable = htable;
+	p.te_avtab.nslot = 2;
+	p.te_avtab.nel = 2;
+
+	KUNIT_ASSERT_EQ(test, 0,
+			avtab_filename_trans_write(&p, &p.te_avtab, &fp));
+
+	KUNIT_ASSERT_EQ(test, 0, fp.len);
+	KUNIT_EXPECT_TRUE(test,
+			  !memcmp(expected_data, data, sizeof(expected_data)));
+}
+
+static void filename_trans_write__comp_simple(struct kunit *test)
+{
+	char expected_data[] = {
+		3, 0, 0, 0,	/* count */
+
+		5, 0, 0, 0,			/* entry 1 name len */
+		'f', 'i', 'l', 'e', '1',	/* entry 1 name */
+		43, 0, 0, 0,			/* entry 1 ttype */
+		44, 0, 0, 0,			/* entry 1 tclass */
+		1, 0, 0, 0,			/* entry 1 ndatum */
+		64, 0, 0, 0,			/* entry 1 datum 1 stypes */
+		64, 0, 0, 0,
+		1, 0, 0, 0,
+		0, 0, 0, 0,
+		0, 0, 0, 0, 0, 2, 0, 0,
+		45, 0, 0, 0,			/* entry 1 otype */
+
+		5, 0, 0, 0,			/* entry 2 name len */
+		'f', 'i', 'l', 'e', '2',	/* entry 2 name */
+		47, 0, 0, 0,			/* entry 2 ttype */
+		48, 0, 0, 0,			/* entry 2 tclass */
+		1, 0, 0, 0,			/* entry 2 ndatum */
+		64, 0, 0, 0,			/* entry 2 datum 1 stypes */
+		64, 0, 0, 0,
+		1, 0, 0, 0,
+		0, 0, 0, 0,
+		0, 0, 0, 0, 0, 32, 0, 0,
+		49, 0, 0, 0,			/* entry 2 otype */
+
+		5, 0, 0, 0,			/* entry 3 name len */
+		'f', 'i', 'l', 'e', '3',	/* entry 3 name */
+		47, 0, 0, 0,			/* entry 3 ttype */
+		48, 0, 0, 0,			/* entry 3 tclass */
+		1, 0, 0, 0,			/* entry 2 ndatum */
+		64, 0, 0, 0,			/* entry 2 datum 1 stypes */
+		64, 0, 0, 0,
+		1, 0, 0, 0,
+		0, 0, 0, 0,
+		0, 0, 0, 0, 0, 32, 0, 0,
+		53, 0, 0, 0,			/* entry 3 otype */
+	};
+	char data[sizeof(expected_data)] = {0};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_COMP_FTRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+	u32 otypes[] = {45, 49, 53};
+	struct hashtab_node nhnodes[] = {
+		{"file1", &otypes[0], NULL},
+		{"file2", &otypes[1], &nhnodes[2]},
+		{"file3", &otypes[2], NULL},
+	};
+	struct hashtab_node *nhtable[] = {&nhnodes[0], &nhnodes[1]};
+	struct avtab_trans transs[] = {
+		{0, {{&nhtable[0], 1, 1}, 0}},
+		{0, {{&nhtable[1], 1, 2}, 0}},
+	};
+	struct avtab_node nodes[] = {
+		{{42, 43, 44, AVTAB_TRANSITION},
+			{.u.trans = &transs[0]}, NULL},
+		{{46, 47, 48, AVTAB_TRANSITION},
+			{.u.trans = &transs[1]}, NULL},
+	};
+	struct avtab_node *htable[] = {&nodes[0], &nodes[1]};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+	p.te_avtab.htable = htable;
+	p.te_avtab.nslot = 2;
+	p.te_avtab.nel = 2;
+
+	KUNIT_ASSERT_EQ(test, 0,
+			avtab_filename_trans_write(&p, &p.te_avtab, &fp));
+
+	KUNIT_ASSERT_EQ(test, 0, fp.len);
+	KUNIT_EXPECT_TRUE(test,
+			  !memcmp(expected_data, data, sizeof(expected_data)));
+}
+
+static void read__pre_avtab_ftrans(struct kunit *test)
+{
+	char data[] = {
+		2, 0, 0, 0,	/* nel */
+
+		42, 0,			/* entry 1 source type */
+		43, 0,			/* entry 1 target type */
+		44, 0,			/* entry 1 target class */
+		AVTAB_TRANSITION, 0,	/* entry 1 specified */
+		45, 0, 0, 0,		/* entry 1 otype */
+
+		46, 0,			/* entry 2 source type */
+		47, 0,			/* entry 2 target type */
+		48, 0,			/* entry 2 target class */
+		AVTAB_TRANSITION, 0,	/* entry 2 specified */
+		49, 0, 0, 0,		/* entry 2 otype */
+	};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_COMP_FTRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+	struct avtab_key key;
+	struct avtab_datum *node;
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+	KUNIT_ASSERT_EQ(test, 0,
+			avtab_read(&p.te_avtab, &fp, &p));
+	KUNIT_EXPECT_EQ(test, 2, p.te_avtab.nel);
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+
+	key = (struct avtab_key){42, 43, 44, AVTAB_TRANSITION};
+	node = avtab_search(&p.te_avtab, &key);
+	KUNIT_ASSERT_NOT_NULL(test, node);
+	KUNIT_EXPECT_EQ(test, 45, node->u.trans->otype);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->name_trans.table.nel);
+
+	key = (struct avtab_key){46, 47, 48, AVTAB_TRANSITION};
+	node = avtab_search(&p.te_avtab, &key);
+	KUNIT_ASSERT_NOT_NULL(test, node);
+	KUNIT_EXPECT_EQ(test, 49, node->u.trans->otype);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->name_trans.table.nel);
+
+	avtab_destroy(&p.te_avtab);
+}
+
+static void read__simple(struct kunit *test)
+{
+	char data[] = {
+		2, 0, 0, 0,	/* nel */
+
+		42, 0,			/* entry 1 source type */
+		43, 0,			/* entry 1 target type */
+		44, 0,			/* entry 1 target class */
+		AVTAB_TRANSITION, 0,	/* entry 1 specified */
+		41, 0, 0, 0,		/* entry 1 otype */
+		1, 0, 0, 0,		/* entry 1 nfnts */
+		45, 0, 0, 0,			/* entry 1 fnt 1 otype */
+		5, 0, 0, 0,			/* entry 1 fnt 1 name len */
+		'f', 'i', 'l', 'e', '1',	/* entry 1 fnt 1 name */
+
+		46, 0,			/* entry 2 source type */
+		47, 0,			/* entry 2 target type */
+		48, 0,			/* entry 2 target class */
+		AVTAB_TRANSITION, 0,	/* entry 2 specified */
+		40, 0, 0, 0,		/* entry 2 otype */
+		2, 0, 0, 0,		/* entry 2 nfnts */
+		49, 0, 0, 0,			/* entry 2 fnt 1 otype */
+		5, 0, 0, 0,			/* entry 2 fnt 1 name len */
+		'f', 'i', 'l', 'e', '2',	/* entry 2 fnt 1 name */
+		50, 0, 0, 0,			/* entry 2 fnt 2 otype */
+		5, 0, 0, 0,			/* entry 2 fnt 2 name len */
+		'f', 'i', 'l', 'e', '3',	/* entry 2 fnt 2 name */
+	};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_AVTAB_FTRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+	struct avtab_key key;
+	struct avtab_datum *node;
+	u32 *otype;
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+	KUNIT_ASSERT_EQ(test, 0,
+			avtab_read(&p.te_avtab, &fp, &p));
+	KUNIT_EXPECT_EQ(test, 2, p.te_avtab.nel);
+	KUNIT_EXPECT_EQ(test, 0, fp.len);
+
+	key = (struct avtab_key){42, 43, 44, AVTAB_TRANSITION};
+	node = avtab_search(&p.te_avtab, &key);
+	KUNIT_ASSERT_NOT_NULL(test, node);
+	KUNIT_EXPECT_EQ(test, 41, node->u.trans->otype);
+	KUNIT_EXPECT_EQ(test, 1, node->u.trans->name_trans.table.nel);
+
+	otype = symtab_search(&node->u.trans->name_trans, "file1");
+	KUNIT_ASSERT_NOT_NULL(test, otype);
+	KUNIT_EXPECT_EQ(test, 45, *otype);
+
+	key = (struct avtab_key){46, 47, 48, AVTAB_TRANSITION};
+	node = avtab_search(&p.te_avtab, &key);
+	KUNIT_ASSERT_NOT_NULL(test, node);
+	KUNIT_EXPECT_EQ(test, 40, node->u.trans->otype);
+	KUNIT_EXPECT_EQ(test, 2, node->u.trans->name_trans.table.nel);
+
+	otype = symtab_search(&node->u.trans->name_trans, "file2");
+	KUNIT_ASSERT_NOT_NULL(test, otype);
+	KUNIT_EXPECT_EQ(test, 49, *otype);
+
+	otype = symtab_search(&node->u.trans->name_trans, "file3");
+	KUNIT_ASSERT_NOT_NULL(test, otype);
+	KUNIT_EXPECT_EQ(test, 50, *otype);
+
+	avtab_destroy(&p.te_avtab);
+}
+
+static void write__pre_avtab_ftrans(struct kunit *test)
+{
+	char expected_data[] = {
+		1, 0, 0, 0,	/* nel */
+
+		46, 0,			/* entry 2 source type */
+		47, 0,			/* entry 2 target type */
+		48, 0,			/* entry 2 target class */
+		AVTAB_TRANSITION, 0,	/* entry 2 specified */
+		40, 0, 0, 0,		/* entry 2 otype */
+	};
+	char data[sizeof(expected_data)] = {0};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_COMP_FTRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+	u32 otypes[] = {45, 49, 53};
+	struct hashtab_node nhnodes[] = {
+		{"file1", &otypes[0], NULL},
+		{"file2", &otypes[1], &nhnodes[2]},
+		{"file3", &otypes[2], NULL},
+	};
+	struct hashtab_node *nhtable[] = {&nhnodes[0], &nhnodes[1]};
+	struct avtab_trans transs[] = {
+		{0, {{&nhtable[0], 1, 1}, 0}},
+		{40, {{&nhtable[1], 1, 2}, 0}},
+	};
+	struct avtab_node nodes[] = {
+		{{42, 43, 44, AVTAB_TRANSITION},
+			{.u.trans = &transs[0]}, NULL},
+		{{46, 47, 48, AVTAB_TRANSITION},
+			{.u.trans = &transs[1]}, NULL},
+	};
+	struct avtab_node *htable[] = {&nodes[0], &nodes[1]};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+	p.te_avtab.htable = htable;
+	p.te_avtab.nslot = 2;
+	p.te_avtab.nel = 2;
+
+	KUNIT_ASSERT_EQ(test, 0, avtab_write(&p, &p.te_avtab, &fp));
+
+	KUNIT_ASSERT_EQ(test, 0, fp.len);
+	KUNIT_EXPECT_TRUE(test,
+			  !memcmp(expected_data, data, sizeof(expected_data)));
+}
+
+static void write__simple(struct kunit *test)
+{
+	char expected_data[] = {
+		2, 0, 0, 0,	/* nel */
+
+		42, 0,			/* entry 1 source type */
+		43, 0,			/* entry 1 target type */
+		44, 0,			/* entry 1 target class */
+		AVTAB_TRANSITION, 0,	/* entry 1 specified */
+		41, 0, 0, 0,		/* entry 1 otype */
+		1, 0, 0, 0,		/* entry 1 nfnts */
+		45, 0, 0, 0,			/* entry 1 fnt 1 otype */
+		5, 0, 0, 0,			/* entry 1 fnt 1 name len */
+		'f', 'i', 'l', 'e', '1',	/* entry 1 fnt 1 name */
+
+		46, 0,			/* entry 2 source type */
+		47, 0,			/* entry 2 target type */
+		48, 0,			/* entry 2 target class */
+		AVTAB_TRANSITION, 0,	/* entry 2 specified */
+		40, 0, 0, 0,		/* entry 2 otype */
+		2, 0, 0, 0,		/* entry 2 nfnts */
+		49, 0, 0, 0,			/* entry 1 fnt 1 otype */
+		5, 0, 0, 0,			/* entry 1 fnt 1 name len */
+		'f', 'i', 'l', 'e', '2',	/* entry 1 fnt 1 name */
+		50, 0, 0, 0,			/* entry 1 fnt 1 otype */
+		5, 0, 0, 0,			/* entry 1 fnt 1 name len */
+		'f', 'i', 'l', 'e', '3',	/* entry 1 fnt 1 name */
+	};
+	char data[sizeof(expected_data)] = {0};
+	struct policydb p = {
+		.te_avtab = {0},
+		.policyvers = POLICYDB_VERSION_AVTAB_FTRANS,
+	};
+	struct policy_file fp = {
+		.data = data,
+		.len = sizeof(data),
+	};
+	u32 otypes[] = {45, 49, 50};
+	struct hashtab_node nhnodes[] = {
+		{"file1", &otypes[0], NULL},
+		{"file2", &otypes[1], &nhnodes[2]},
+		{"file3", &otypes[2], NULL},
+	};
+	struct hashtab_node *nhtable[] = {&nhnodes[0], &nhnodes[1]};
+	struct avtab_trans transs[] = {
+		{41, {{&nhtable[0], 1, 1}, 0}},
+		{40, {{&nhtable[1], 1, 2}, 0}},
+	};
+	struct avtab_node nodes[] = {
+		{{42, 43, 44, AVTAB_TRANSITION},
+			{.u.trans = &transs[0]}, NULL},
+		{{46, 47, 48, AVTAB_TRANSITION},
+			{.u.trans = &transs[1]}, NULL},
+	};
+	struct avtab_node *htable[] = {&nodes[0], &nodes[1]};
+
+	p.p_types.nprim = 54;
+	p.p_classes.nprim = 49;
+	p.te_avtab.htable = htable;
+	p.te_avtab.nslot = 2;
+	p.te_avtab.nel = 2;
+
+	KUNIT_ASSERT_EQ(test, 0, avtab_write(&p, &p.te_avtab, &fp));
+
+	KUNIT_ASSERT_EQ(test, 0, fp.len);
+	KUNIT_EXPECT_TRUE(test,
+			  !memcmp(expected_data, data, sizeof(expected_data)));
+}
+
+static struct kunit_case avtab_test_cases[] = {
+	KUNIT_CASE(filename_trans_read__pre_filename_trans),
+	KUNIT_CASE(filename_trans_read__empty),
+	KUNIT_CASE(filename_trans_read__comp_empty),
+	KUNIT_CASE(filename_trans_read__simple),
+	KUNIT_CASE(filename_trans_read__comp_simple),
+
+	KUNIT_CASE(filename_trans_write__pre_filename_trans),
+	KUNIT_CASE(filename_trans_write__empty),
+	KUNIT_CASE(filename_trans_write__comp_empty),
+	KUNIT_CASE(filename_trans_write__simple),
+	KUNIT_CASE(filename_trans_write__comp_simple),
+
+	KUNIT_CASE(read__pre_avtab_ftrans),
+	KUNIT_CASE(read__simple),
+
+	KUNIT_CASE(write__pre_avtab_ftrans),
+	KUNIT_CASE(write__simple),
+	{0},
+};
+
+static struct kunit_suite avtab_test_suite = {
+	.name = "security-selinux-avtab",
+	.test_cases = avtab_test_cases,
+};
+
+kunit_test_suite(avtab_test_suite);
+
+MODULE_LICENSE("GPL");
diff --git a/security/selinux/ss/symtab.c b/security/selinux/ss/symtab.c
index c42a6648a07d..c53863d5ed40 100644
--- a/security/selinux/ss/symtab.c
+++ b/security/selinux/ss/symtab.c
@@ -52,3 +52,6 @@ void *symtab_search(struct symtab *s, const char *name)
 {
 	return hashtab_search(&s->table, name, symtab_key_params);
 }
+
+/* Export for avtab KUnit tests */
+EXPORT_SYMBOL_GPL(symtab_search);
-- 
2.40.0

[PATCH 5/5] selinux: add prefix/suffix matching support to filename type transitions

[Juraj Marcin]

Currently, filename type transitions support only exact name matching.
However, in practice, the names contain variable parts. This leads to
many duplicated rules in the policy that differ only in the part of the
name, or it is even impossible to cover all possible combinations.

This patch extends the filename type transitions structures to include
new types of filename transitions - prefix and suffix filename
transitions. It also implements the reading and writing of those rules
in the kernel binary policy format together with increasing its version.
Last, it updates the function responsible for determining the new
context to also include the prefix and suffix filename transitions in
the process. It does that by first checking for the exact match, then
the longest matching prefix and then the longest matching suffix, in
that order. That way the exact match rules have precedence before new
rules, to ensure compatibility with older policies.

Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
---
 security/selinux/include/security.h |  3 +-
 security/selinux/ss/avtab.c         | 53 +++++++++++++++++++--
 security/selinux/ss/avtab.h         |  2 +
 security/selinux/ss/avtab_test.c    | 16 +++++++
 security/selinux/ss/policydb.c      |  5 ++
 security/selinux/ss/services.c      | 71 ++++++++++++++++++++++++-----
 6 files changed, 133 insertions(+), 17 deletions(-)

diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
index c483680fe22e..0cf0767d061b 100644
--- a/security/selinux/include/security.h
+++ b/security/selinux/include/security.h
@@ -47,10 +47,11 @@
 #define POLICYDB_VERSION_GLBLUB		32
 #define POLICYDB_VERSION_COMP_FTRANS	33 /* compressed filename transitions */
 #define POLICYDB_VERSION_AVTAB_FTRANS	34 /* filename transitions moved to avtab */
+#define POLICYDB_VERSION_PREFIX_SUFFIX	35 /* prefix/suffix support for filename transitions */
 
 /* Range of policy versions we understand*/
 #define POLICYDB_VERSION_MIN   POLICYDB_VERSION_BASE
-#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_AVTAB_FTRANS
+#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_PREFIX_SUFFIX
 
 /* Mask for just the mount related flags */
 #define SE_MNTMASK	0x0f
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index db7123670ef8..f58707930189 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -301,6 +301,12 @@ static void avtab_trans_destroy(struct avtab_trans *trans)
 {
 	hashtab_map(&trans->name_trans.table, avtab_trans_destroy_helper, NULL);
 	hashtab_destroy(&trans->name_trans.table);
+	hashtab_map(&trans->prefix_trans.table, avtab_trans_destroy_helper,
+		    NULL);
+	hashtab_destroy(&trans->prefix_trans.table);
+	hashtab_map(&trans->suffix_trans.table, avtab_trans_destroy_helper,
+		    NULL);
+	hashtab_destroy(&trans->suffix_trans.table);
 }
 
 void avtab_destroy(struct avtab *h)
@@ -517,6 +523,14 @@ static int avtab_trans_read(void *fp, struct policydb *pol,
 	if (rc)
 		goto bad;
 
+	if (pol->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
+		rc = avtab_trans_read_name_trans(pol, &trans->prefix_trans, fp);
+		if (rc)
+			goto bad;
+		rc = avtab_trans_read_name_trans(pol, &trans->suffix_trans, fp);
+		if (rc)
+			goto bad;
+	}
 	return 0;
 
 bad:
@@ -706,9 +720,14 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
 		 * also each transition entry must meet at least one condition
 		 * to be considered non-empty:
 		 *  - set (non-zero) otype
-		 *  - non-empty filename transitions table
+		 *  - non-empty full name transitions table
+		 *  - non-empty prefix name transitions table
+		 *  - non-empty suffix name transitions table
 		 */
-		if (!otype && !datum.u.trans->name_trans.table.nel) {
+		if (!otype &&
+		    !datum.u.trans->name_trans.table.nel &&
+		    !datum.u.trans->prefix_trans.table.nel &&
+		    !datum.u.trans->suffix_trans.table.nel) {
 			pr_err("SELinux: avtab: empty transition\n");
 			avtab_trans_destroy(&trans);
 			return -EINVAL;
@@ -809,18 +828,44 @@ static int avtab_trans_write(struct policydb *p, struct avtab_trans *cur,
 	__le32 buf32[2];
 
 	if (p->policyvers >= POLICYDB_VERSION_AVTAB_FTRANS) {
-		/* write otype and number of filename transitions */
+		/* write otype and number of name transitions */
 		buf32[0] = cpu_to_le32(cur->otype);
 		buf32[1] = cpu_to_le32(cur->name_trans.table.nel);
 		rc = put_entry(buf32, sizeof(u32), 2, fp);
 		if (rc)
 			return rc;
 
-		/* write filename transitions */
+		/* write name transitions */
 		rc = hashtab_map(&cur->name_trans.table,
 				 avtab_trans_write_helper, fp);
 		if (rc)
 			return rc;
+
+		if (p->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
+			/* write number of prefix transitions */
+			buf32[0] = cpu_to_le32(cur->prefix_trans.table.nel);
+			rc = put_entry(buf32, sizeof(u32), 1, fp);
+			if (rc)
+				return rc;
+
+			/* write prefix transitions */
+			rc = hashtab_map(&cur->prefix_trans.table,
+					 avtab_trans_write_helper, fp);
+			if (rc)
+				return rc;
+
+			/* write number of suffix transitions */
+			buf32[0] = cpu_to_le32(cur->suffix_trans.table.nel);
+			rc = put_entry(buf32, sizeof(u32), 1, fp);
+			if (rc)
+				return rc;
+
+			/* write suffix transitions */
+			rc = hashtab_map(&cur->suffix_trans.table,
+					 avtab_trans_write_helper, fp);
+			if (rc)
+				return rc;
+		}
 	} else if (cur->otype) {
 		buf32[0] = cpu_to_le32(cur->otype);
 		rc = put_entry(buf32, sizeof(u32), 1, fp);
diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index 162ef1be85e7..929e322715d1 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -51,6 +51,8 @@ struct avtab_key {
 struct avtab_trans {
 	u32 otype;		/* default resulting type of the new object */
 	struct symtab name_trans;	/* filename transitions */
+	struct symtab prefix_trans;	/* prefix filename transitions */
+	struct symtab suffix_trans;	/* prefix filename transitions */
 };
 
 /*
diff --git a/security/selinux/ss/avtab_test.c b/security/selinux/ss/avtab_test.c
index daa8e4cfaeb2..7e63204629fd 100644
--- a/security/selinux/ss/avtab_test.c
+++ b/security/selinux/ss/avtab_test.c
@@ -124,6 +124,8 @@ static void filename_trans_read__simple(struct kunit *test)
 	KUNIT_ASSERT_NOT_NULL(test, node);
 	KUNIT_EXPECT_EQ(test, 0, node->u.trans->otype);
 	KUNIT_EXPECT_EQ(test, 1, node->u.trans->name_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->prefix_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->suffix_trans.table.nel);
 
 	otype = symtab_search(&node->u.trans->name_trans, "file1");
 	KUNIT_ASSERT_NOT_NULL(test, otype);
@@ -134,6 +136,8 @@ static void filename_trans_read__simple(struct kunit *test)
 	KUNIT_ASSERT_NOT_NULL(test, node);
 	KUNIT_EXPECT_EQ(test, 0, node->u.trans->otype);
 	KUNIT_EXPECT_EQ(test, 2, node->u.trans->name_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->prefix_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->suffix_trans.table.nel);
 
 	otype = symtab_search(&node->u.trans->name_trans, "file2");
 	KUNIT_ASSERT_NOT_NULL(test, otype);
@@ -213,6 +217,8 @@ static void filename_trans_read__comp_simple(struct kunit *test)
 	KUNIT_ASSERT_NOT_NULL(test, node);
 	KUNIT_EXPECT_EQ(test, 0, node->u.trans->otype);
 	KUNIT_EXPECT_EQ(test, 1, node->u.trans->name_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->prefix_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->suffix_trans.table.nel);
 
 	otype = symtab_search(&node->u.trans->name_trans, "file1");
 	KUNIT_ASSERT_NOT_NULL(test, otype);
@@ -223,6 +229,8 @@ static void filename_trans_read__comp_simple(struct kunit *test)
 	KUNIT_ASSERT_NOT_NULL(test, node);
 	KUNIT_EXPECT_EQ(test, 0, node->u.trans->otype);
 	KUNIT_EXPECT_EQ(test, 2, node->u.trans->name_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->prefix_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->suffix_trans.table.nel);
 
 	otype = symtab_search(&node->u.trans->name_trans, "file2");
 	KUNIT_ASSERT_NOT_NULL(test, otype);
@@ -493,12 +501,16 @@ static void read__pre_avtab_ftrans(struct kunit *test)
 	KUNIT_ASSERT_NOT_NULL(test, node);
 	KUNIT_EXPECT_EQ(test, 45, node->u.trans->otype);
 	KUNIT_EXPECT_EQ(test, 0, node->u.trans->name_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->prefix_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->suffix_trans.table.nel);
 
 	key = (struct avtab_key){46, 47, 48, AVTAB_TRANSITION};
 	node = avtab_search(&p.te_avtab, &key);
 	KUNIT_ASSERT_NOT_NULL(test, node);
 	KUNIT_EXPECT_EQ(test, 49, node->u.trans->otype);
 	KUNIT_EXPECT_EQ(test, 0, node->u.trans->name_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->prefix_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->suffix_trans.table.nel);
 
 	avtab_destroy(&p.te_avtab);
 }
@@ -555,6 +567,8 @@ static void read__simple(struct kunit *test)
 	KUNIT_ASSERT_NOT_NULL(test, node);
 	KUNIT_EXPECT_EQ(test, 41, node->u.trans->otype);
 	KUNIT_EXPECT_EQ(test, 1, node->u.trans->name_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->prefix_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->suffix_trans.table.nel);
 
 	otype = symtab_search(&node->u.trans->name_trans, "file1");
 	KUNIT_ASSERT_NOT_NULL(test, otype);
@@ -565,6 +579,8 @@ static void read__simple(struct kunit *test)
 	KUNIT_ASSERT_NOT_NULL(test, node);
 	KUNIT_EXPECT_EQ(test, 40, node->u.trans->otype);
 	KUNIT_EXPECT_EQ(test, 2, node->u.trans->name_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->prefix_trans.table.nel);
+	KUNIT_EXPECT_EQ(test, 0, node->u.trans->suffix_trans.table.nel);
 
 	otype = symtab_search(&node->u.trans->name_trans, "file2");
 	KUNIT_ASSERT_NOT_NULL(test, otype);
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 96b8d5bd8e4e..db759ec3e1ce 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -162,6 +162,11 @@ static const struct policydb_compat_info policydb_compat[] = {
 		.sym_num	= SYM_NUM,
 		.ocon_num	= OCON_NUM,
 	},
+	{
+		.version	= POLICYDB_VERSION_PREFIX_SUFFIX,
+		.sym_num	= SYM_NUM,
+		.ocon_num	= OCON_NUM,
+	},
 };
 
 static const struct policydb_compat_info *policydb_lookup_compat(int version)
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index 131647e7ec68..2faf92bf12da 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1661,6 +1661,60 @@ static int compute_sid_handle_invalid_context(
 	return -EACCES;
 }
 
+static int security_compute_type_trans_otype(struct avtab_trans *trans,
+					     const char *name, u32 *res_type)
+{
+	u32 *otype;
+	size_t len;
+	char *namedup = NULL;
+	size_t i;
+
+	/*
+	 * use default otype if not empty and then try to find more specific
+	 * rule using name
+	 */
+	if (trans->otype)
+		*res_type = trans->otype;
+	if (!name)
+		return 0;
+
+	/* try to find full name */
+	otype = symtab_search(&trans->name_trans, name);
+	if (otype) {
+		*res_type = *otype;
+		return 0;
+	}
+
+	/* copy name for shortening */
+	len = strlen(name);
+	namedup = kmemdup(name, len + 1, GFP_KERNEL);
+	if (!namedup)
+		return -ENOMEM;
+
+	/* try to find possible prefixes of name starting from the longest */
+	for (i = len; i > 0; i--) {
+		namedup[i] = '\0';
+		otype = symtab_search(&trans->prefix_trans, namedup);
+		if (otype) {
+			kfree(namedup);
+			*res_type = *otype;
+			return 0;
+		}
+	}
+	kfree(namedup);
+
+	/*try to find possible suffixes of name starting from the longest */
+	for (i = 0; i < len; i++) {
+		otype = symtab_search(&trans->suffix_trans, &name[i]);
+		if (otype) {
+			*res_type = *otype;
+			return 0;
+		}
+	}
+
+	return 0;
+}
+
 static int security_compute_sid(u32 ssid,
 				u32 tsid,
 				u16 orig_tclass,
@@ -1802,18 +1856,11 @@ static int security_compute_sid(u32 ssid,
 	if (avdatum) {
 		/* Use the type from the type transition/member/change rule. */
 		if (avkey.specified & AVTAB_TRANSITION) {
-			/*
-			 * use default otype if not empty and then to try to
-			 * find more specific rule using objname
-			 */
-			if (avdatum->u.trans->otype)
-				newcontext.type = avdatum->u.trans->otype;
-			if (objname) {
-				otype = symtab_search(&avdatum->u.trans->name_trans,
-						      objname);
-				if (otype)
-					newcontext.type = *otype;
-			}
+			rc = security_compute_type_trans_otype(avdatum->u.trans,
+							       objname,
+							       &newcontext.type);
+			if (rc)
+				goto out_unlock;
 		} else {
 			newcontext.type = avdatum->u.data;
 		}
-- 
2.40.0

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Paul Moore]

On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
>
> Currently, filename transitions are stored separately from other type
> enforcement rules and only support exact name matching. However, in
> practice, the names contain variable parts. This leads to many
> duplicated rules in the policy that differ only in the part of the name,
> or it is even impossible to cover all possible combinations.
>
> First, this series of patches moves the filename transitions to be part
> of the avtab structures. This not only makes the implementation of
> prefix/suffix matching and future enhancements easier, but also reduces
> the technical debt regarding the filename transitions. Next, the last
> patch implements the support for prefix/suffix name matching itself by
> extending the structures added in previous patches in this series.
>
> Even though, moving everything to avtab increases the memory usage and
> the size of the binary policy itself and thus the loading time, the
> ability to match the prefix or suffix of the name will reduce the
> overall number of rules in the policy which should mitigate this issue.
>
> This implementation has been successfully tested using the existing and
> also new tests in the SELinux Testsuite.
>
> Juraj Marcin (5):
>   selinux: move transition to separate structure in avtab_datum
>   selinux: move filename transitions to avtab
>   selinux: implement new binary format for filename transitions in avtab
>   selinux: filename transitions move tests
>   selinux: add prefix/suffix matching support to filename type
>     transitions

Just a quick comment as I haven't had a chance to properly review this
series yet; you show some memory usage and performance measurements in
some of the intermediate patches, that's good, but I don't see the
same measurements taken when the full patchset is applied.  Please
provide the same memory usage and performance comparisons with the
full patchset applied.

-- 
paul-moore.com

Re: [PATCH 2/5] selinux: move filename transitions to avtab

[Christian Göttsche]

On Wed, 31 May 2023 at 13:32, Juraj Marcin <juraj@jurajmarcin.com> wrote:
>
> Currently, filename transitions are stored separately from other type
> enforcement rules. This leads to possibly sub-optimal performance and
> makes further improvements cumbersome.
>
> This patch adds a symbol table of filename transitions to the transition
> structure added to avtab in the previous patch. It also implements
> functions required for reading and writing filename transitions in
> kernel policy format and updates computation of new type to use filename
> transitions embedded in avtab. Last but not least, it updates the
> conflict check in the conditional avtab to account for empty transitions
> in the non-conditional avtab.
>
> These changes are expected to cause higher memory usage, as now there
> needs to be a filename transition structure for every stype. This patch
> effectively undoes most of the commit c3a276111ea2 ("selinux: optimize
> storage of filename transitions"), but this will be mitigated by
> providing support for matching prefix/suffix of the filename for
> filename transitions in future patches which will reduce to need to have
> so many of them.
>
> On the other hand, the changes do not significantly slow down the
> creation of new files.
>
> Kernel     | Mem   | Create test_tty | Create test_tty | osbench [1]
>            | usage | (real time)     | (kernel time)   | create_files
> -----------+-------+-----------------+-----------------+--------------
> reference  | 155MB |  1.3440 ms/file |  1.0071 ms/file | 10.6507 us/file
> this patch | 198MB |  1.3912 ms/file |  1.0172 ms/file | 10.5567 us/file
>
> Create test_tty benchmark:
>
>     mknod /dev/test_tty c 4 1
>     time for i in `seq 1 10000`; do
>         mknod /dev/test_tty$i c 4 1
>     done
>
> This benchmark should simulate the worst case scenario as many filename
> transitions affect files created in the /dev directory.
>
> [1] https://github.com/mbitsnbites/osbench
>
> Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
> Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> ---
>  security/selinux/ss/avtab.c       | 516 ++++++++++++++++++++++++++++++
>  security/selinux/ss/avtab.h       |   7 +
>  security/selinux/ss/conditional.c |   6 +-
>  security/selinux/ss/hashtab.h     |   6 +
>  security/selinux/ss/policydb.c    | 399 +----------------------
>  security/selinux/ss/policydb.h    |  25 +-
>  security/selinux/ss/services.c    |  54 +---
>  7 files changed, 555 insertions(+), 458 deletions(-)
>
> diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
> index a7f348e4509d..fe921e1586e5 100644
> --- a/security/selinux/ss/avtab.c
> +++ b/security/selinux/ss/avtab.c
> @@ -22,6 +22,7 @@
>  #include <linux/errno.h>
>  #include "avtab.h"
>  #include "policydb.h"
> +#include "hashtab.h"
>
>  static struct kmem_cache *avtab_node_cachep __ro_after_init;
>  static struct kmem_cache *avtab_trans_cachep __ro_after_init;
> @@ -286,6 +287,19 @@ avtab_search_node_next(struct avtab_node *node, int specified)
>         return NULL;
>  }
>
> +static int avtab_trans_destroy_helper(void *k, void *d, void *args)
> +{
> +       kfree(k);
> +       kfree(d);
> +       return 0;
> +}
> +
> +static void avtab_trans_destroy(struct avtab_trans *trans)
> +{
> +       hashtab_map(&trans->name_trans.table, avtab_trans_destroy_helper, NULL);
> +       hashtab_destroy(&trans->name_trans.table);
> +}
> +
>  void avtab_destroy(struct avtab *h)
>  {
>         int i;
> @@ -303,6 +317,7 @@ void avtab_destroy(struct avtab *h)
>                                 kmem_cache_free(avtab_xperms_cachep,
>                                                 temp->datum.u.xperms);
>                         } else if (temp->key.specified & AVTAB_TRANSITION) {
> +                               avtab_trans_destroy(temp->datum.u.trans);
>                                 kmem_cache_free(avtab_trans_cachep,
>                                                 temp->datum.u.trans);
>                         }
> @@ -587,6 +602,7 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
>         if (key.specified & AVTAB_TRANSITION) {
>                 if (!policydb_type_isvalid(pol, datum.u.trans->otype)) {
>                         pr_err("SELinux: avtab: invalid transition type\n");
> +                       avtab_trans_destroy(&trans);
>                         return -EINVAL;
>                 }
>         } else if (key.specified & AVTAB_TYPE) {
> @@ -596,6 +612,8 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
>                 }
>         }
>         rc = insertf(a, &key, &datum, p);
> +       if (rc && key.specified & AVTAB_TRANSITION)
> +               avtab_trans_destroy(&trans);
>         return rc;
>  }
>
> @@ -656,6 +674,10 @@ int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
>         int rc;
>         unsigned int i;
>
> +       if (cur->key.specified & AVTAB_TRANSITION &&
> +           !cur->datum.u.trans->otype)
> +               return 0;
> +
>         buf16[0] = cpu_to_le16(cur->key.source_type);
>         buf16[1] = cpu_to_le16(cur->key.target_type);
>         buf16[2] = cpu_to_le16(cur->key.target_class);
> @@ -723,3 +745,497 @@ void __init avtab_cache_init(void)
>                                                 sizeof(struct avtab_extended_perms),
>                                                 0, SLAB_PANIC, NULL);
>  }
> +
> +/* policydb filename transitions compatibility */
> +
> +static int avtab_insert_filename_trans(struct avtab *a,
> +                                      const struct avtab_key *key,
> +                                      char *name, u32 otype)
> +{
> +       int rc;
> +       struct avtab_node *node;
> +       struct avtab_trans new_trans = {0};
> +       struct avtab_datum new_datum = {.u.trans = &new_trans};
> +       struct avtab_datum *datum;
> +       u32 *otype_datum = NULL;
> +
> +       datum = avtab_search(a, key);
> +       if (!datum) {
> +               /*
> +                * insert is acctually unique, but with this function we can get
> +                * the inserted node and therefore the datum
> +                */
> +               node = avtab_insert_nonunique(a, key, &new_datum);
> +               if (!node)
> +                       return -ENOMEM;
> +               datum = &node->datum;
> +       }
> +
> +       if (hashtab_is_empty(&datum->u.trans->name_trans.table)) {
> +               rc = symtab_init(&datum->u.trans->name_trans, 1 << 8);
> +               if (rc)
> +                       return rc;
> +       }
> +
> +       otype_datum = kmalloc(sizeof(u32), GFP_KERNEL);
> +       if (!otype_datum)
> +               return -ENOMEM;
> +       *otype_datum = otype;
> +
> +       rc = symtab_insert(&datum->u.trans->name_trans, name, otype_datum);
> +       if (rc)
> +               kfree(otype_datum);
> +
> +       return rc;
> +}
> +
> +static int filename_trans_read_item(struct avtab *a, void *fp)
> +{
> +       int rc;
> +       __le32 buf32[4];
> +       u32 len, otype;
> +       char *name = NULL;
> +       struct avtab_key key;
> +
> +       /* read length of the name */
> +       rc = next_entry(buf32, fp, sizeof(u32));
> +       if (rc)
> +               return rc;
> +       len = le32_to_cpu(buf32[0]);
> +
> +       /* read the name */
> +       rc = str_read(&name, GFP_KERNEL, fp, len);
> +       if (rc)
> +               return rc;
> +
> +       /* read stype, ttype, tclass and otype */
> +       rc = next_entry(buf32, fp, sizeof(u32) * 4);
> +       if (rc)
> +               goto bad;
> +
> +       key.source_type = le32_to_cpu(buf32[0]);
> +       key.target_type = le32_to_cpu(buf32[1]);
> +       key.target_class = le32_to_cpu(buf32[2]);
> +       key.specified = AVTAB_TRANSITION;
> +
> +       otype = le32_to_cpu(buf32[3]);
> +
> +       rc = avtab_insert_filename_trans(a, &key, name, otype);
> +       if (rc)
> +               goto bad;
> +
> +       return rc;
> +
> +bad:
> +       kfree(name);
> +       return rc;
> +}
> +
> +static int filename_trans_comp_read_item(struct avtab *a, void *fp)
> +{
> +       int rc;
> +       __le32 buf32[3];
> +       u32 len, ndatum, i, bit, otype;
> +       char *name = NULL, *name_copy = NULL;
> +       struct avtab_key key;
> +       struct ebitmap stypes;
> +       struct ebitmap_node *node;
> +
> +       /* read length of the name */
> +       rc = next_entry(buf32, fp, sizeof(u32));
> +       if (rc)
> +               return rc;
> +       len = le32_to_cpu(*buf32);
> +
> +       /* read the name */
> +       rc = str_read(&name, GFP_KERNEL, fp, len);
> +       if (rc)
> +               goto out;
> +
> +       /* read target type, target class and number of elements for key */
> +       rc = next_entry(buf32, fp, sizeof(u32) * 3);
> +       if (rc)
> +               goto out;
> +
> +       key.specified = AVTAB_TRANSITION;
> +       key.target_type = le32_to_cpu(buf32[0]);
> +       key.target_class = le32_to_cpu(buf32[1]);
> +
> +       ndatum = le32_to_cpu(buf32[2]);
> +       if (ndatum == 0) {
> +               pr_err("SELinux:  Filename transition key with no datum\n");
> +               rc = -ENOENT;
> +               goto out;
> +       }
> +
> +       for (i = 0; i < ndatum; i++) {
> +               rc = ebitmap_read(&stypes, fp);
> +               if (rc)
> +                       goto out;
> +
> +               rc = next_entry(buf32, fp, sizeof(u32));
> +               if (rc) {
> +                       ebitmap_destroy(&stypes);
> +                       goto out;
> +               }
> +               otype = le32_to_cpu(*buf32);
> +
> +               ebitmap_for_each_positive_bit(&stypes, node, bit) {
> +                       key.source_type = bit + 1;
> +
> +                       name_copy = kmemdup(name, len + 1, GFP_KERNEL);
> +                       if (!name_copy) {
> +                               ebitmap_destroy(&stypes);
> +                               goto out;
> +                       }
> +
> +                       rc = avtab_insert_filename_trans(a, &key, name_copy,
> +                                                        otype);
> +                       if (rc) {
> +                               ebitmap_destroy(&stypes);
> +                               kfree(name_copy);
> +                               goto out;
> +                       }
> +               }
> +
> +               ebitmap_destroy(&stypes);
> +       }
> +       rc = 0;
> +
> +out:
> +       kfree(name);
> +       return rc;
> +}
> +
> +int avtab_filename_trans_read(struct avtab *a, void *fp, struct policydb *p)
> +{
> +       int rc;
> +       __le32 buf[1];
> +       u32 nel, i;
> +
> +       if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> +               return 0;
> +
> +       rc = next_entry(buf, fp, sizeof(u32));
> +       if (rc)
> +               return rc;
> +       nel = le32_to_cpu(buf[0]);
> +
> +       if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> +               for (i = 0; i < nel; i++) {
> +                       rc = filename_trans_read_item(a, fp);
> +                       if (rc)
> +                               return rc;
> +               }
> +       } else {
> +               for (i = 0; i < nel; i++) {
> +                       rc = filename_trans_comp_read_item(a, fp);
> +                       if (rc)
> +                               return rc;
> +               }
> +       }
> +
> +       return 0;
> +}
> +
> +
> +struct filenametr_write_args {
> +       void *fp;
> +       struct avtab_key *key;
> +};
> +
> +static int filenametr_write_helper(void *k, void *d, void *a)
> +{
> +       char *name = k;
> +       u32 *otype = d;
> +       struct filenametr_write_args *args = a;
> +       int rc;
> +       u32 len;
> +       __le32 buf32[4];
> +
> +       len = strlen(name);
> +       buf32[0] = cpu_to_le32(len);
> +       rc = put_entry(buf32, sizeof(u32), 1, args->fp);
> +       if (rc)
> +               return rc;
> +
> +       rc = put_entry(name, sizeof(char), len, args->fp);
> +       if (rc)
> +               return rc;
> +
> +       buf32[0] = cpu_to_le32(args->key->source_type);
> +       buf32[1] = cpu_to_le32(args->key->target_type);
> +       buf32[2] = cpu_to_le32(args->key->target_class);
> +       buf32[3] = cpu_to_le32(*otype);
> +
> +       rc = put_entry(buf32, sizeof(u32), 4, args->fp);
> +       if (rc)
> +               return rc;
> +
> +       return 0;
> +}
> +
> +struct filenametr_key {
> +       u32 ttype;              /* parent dir context */
> +       u16 tclass;             /* class of new object */
> +       const char *name;       /* last path component */
> +};
> +
> +struct filenametr_datum {
> +       struct ebitmap stypes;  /* bitmap of source types for this otype */
> +       u32 otype;              /* resulting type of new object */
> +       struct filenametr_datum *next;  /* record for next otype*/
> +};
> +
> +static int filenametr_comp_write_helper(void *k, void *d, void *fp)
> +{
> +       struct filenametr_key *key = k;
> +       struct filenametr_datum *datum = d;
> +       __le32 buf[3];
> +       int rc;
> +       u32 ndatum, len = strlen(key->name);
> +       struct filenametr_datum *cur;
> +
> +       buf[0] = cpu_to_le32(len);
> +       rc = put_entry(buf, sizeof(u32), 1, fp);
> +       if (rc)
> +               return rc;
> +
> +       rc = put_entry(key->name, sizeof(char), len, fp);
> +       if (rc)
> +               return rc;
> +
> +       ndatum = 0;
> +       cur = datum;
> +       do {
> +               ndatum++;
> +               cur = cur->next;
> +       } while (unlikely(cur));
> +
> +       buf[0] = cpu_to_le32(key->ttype);
> +       buf[1] = cpu_to_le32(key->tclass);
> +       buf[2] = cpu_to_le32(ndatum);
> +       rc = put_entry(buf, sizeof(u32), 3, fp);
> +       if (rc)
> +               return rc;
> +
> +       cur = datum;
> +       do {
> +               rc = ebitmap_write(&cur->stypes, fp);
> +               if (rc)
> +                       return rc;
> +
> +               buf[0] = cpu_to_le32(cur->otype);
> +               rc = put_entry(buf, sizeof(u32), 1, fp);
> +               if (rc)
> +                       return rc;
> +
> +               cur = cur->next;
> +       } while (unlikely(cur));
> +
> +       return 0;
> +}
> +
> +static int filenametr_destroy(void *k, void *d, void *args)
> +{
> +       struct filenametr_key *key = k;
> +       struct filenametr_datum *datum = d;
> +       struct filenametr_datum *next;
> +
> +       kfree(key);

The member `name` should be free'd as well.
I am seeing a lot of the following reports:


unreferenced object 0xffff888135042130 (size 16):
  comm "audit2allow", pid 522, jiffies 4294901631 (age 736.956s)
  hex dump (first 16 bytes):
    67 72 6f 75 70 2e 65 64 69 74 00 6b 6b 6b 6b a5  group.edit.kkkk.
  backtrace:
    [<0000000000000000>] __kmalloc_node_track_caller+0x52/0x1a0
    [<0000000000000000>] kmemdup+0x1e/0x40
    [<0000000000000000>] filenametr_tab_insert+0x6c5/0x11e0
    [<0000000000000000>] hashtab_map+0xe4/0x160
    [<0000000000000000>] avtab_filename_trans_write+0x4ab/0x760
    [<0000000000000000>] policydb_write+0x895/0xc20
    [<0000000000000000>] security_read_policy+0x150/0x290
    [<0000000000000000>] sel_open_policy+0x24b/0x510
    [<0000000000000000>] do_dentry_open+0x5cf/0xfb0
    [<0000000000000000>] do_open+0x418/0xf30
    [<0000000000000000>] path_openat+0x23e/0x660
    [<0000000000000000>] do_filp_open+0x1f2/0x430
    [<0000000000000000>] do_sys_openat2+0x143/0x410
    [<0000000000000000>] __x64_sys_openat+0x11f/0x1d0
    [<0000000000000000>] do_syscall_64+0x35/0x80
    [<0000000000000000>] entry_SYSCALL_64_after_hwframe+0x63/0xcd


> +       do {
> +               ebitmap_destroy(&datum->stypes);
> +               next = datum->next;
> +               kfree(datum);
> +               datum = next;
> +       } while (unlikely(datum));
> +       cond_resched();
> +       return 0;
> +}
> +
> +static u32 filenametr_hash(const void *k)
> +{
> +       const struct filenametr_key *ft = k;
> +       unsigned long hash;
> +       unsigned int byte_num;
> +       unsigned char focus;
> +
> +       hash = ft->ttype ^ ft->tclass;
> +
> +       byte_num = 0;
> +       while ((focus = ft->name[byte_num++]))
> +               hash = partial_name_hash(focus, hash);
> +       return hash;
> +}
> +
> +static int filenametr_cmp(const void *k1, const void *k2)
> +{
> +       const struct filenametr_key *ft1 = k1;
> +       const struct filenametr_key *ft2 = k2;
> +       int v;
> +
> +       v = ft1->ttype - ft2->ttype;
> +       if (v)
> +               return v;
> +
> +       v = ft1->tclass - ft2->tclass;
> +       if (v)
> +               return v;
> +
> +       return strcmp(ft1->name, ft2->name);
> +}
> +
> +static const struct hashtab_key_params filenametr_key_params = {
> +       .hash = filenametr_hash,
> +       .cmp = filenametr_cmp,
> +};
> +
> +struct filenametr_tab_insert_args {
> +       struct avtab_key *key;
> +       struct hashtab *tab;
> +};
> +
> +static int filenametr_tab_insert(void *k, void *d, void *a)
> +{
> +       char *name = k;
> +       u32 *otype = d;
> +       struct filenametr_tab_insert_args *args = a;
> +       struct filenametr_key key, *ft = NULL;
> +       struct filenametr_datum *last, *datum = NULL;
> +       int rc;
> +
> +       key.ttype = args->key->target_type;
> +       key.tclass = args->key->target_class;
> +       key.name = name;
> +
> +       last = NULL;
> +       datum = hashtab_search(args->tab, &key, filenametr_key_params);
> +       while (datum) {
> +               if (unlikely(ebitmap_get_bit(&datum->stypes,
> +                                            args->key->source_type - 1))) {
> +                       /* conflicting/duplicate rules are ignored */
> +                       datum = NULL;
> +                       goto bad;
> +               }
> +               if (likely(datum->otype == *otype))
> +                       break;
> +               last = datum;
> +               datum = datum->next;
> +       }
> +       if (!datum) {
> +               rc = -ENOMEM;
> +               datum = kmalloc(sizeof(*datum), GFP_KERNEL);
> +               if (!datum)
> +                       goto bad;
> +
> +               ebitmap_init(&datum->stypes);
> +               datum->otype = *otype;
> +               datum->next = NULL;
> +
> +               if (unlikely(last)) {
> +                       last->next = datum;
> +               } else {
> +                       rc = -ENOMEM;
> +                       ft = kmemdup(&key, sizeof(key), GFP_KERNEL);
> +                       if (!ft)
> +                               goto bad;
> +
> +                       ft->name = kmemdup(key.name, strlen(key.name) + 1,
> +                                          GFP_KERNEL);
> +                       if (!ft->name)
> +                               goto bad;
> +
> +                       rc = hashtab_insert(args->tab, ft, datum,
> +                                           filenametr_key_params);
> +                       if (rc)
> +                               goto bad;
> +               }
> +       }
> +
> +       return ebitmap_set_bit(&datum->stypes, args->key->source_type - 1, 1);
> +
> +bad:
> +       if (ft)
> +               kfree(ft->name);
> +       kfree(ft);
> +       kfree(datum);
> +       return rc;
> +}
> +
> +int avtab_filename_trans_write(struct policydb *p, struct avtab *a, void *fp)
> +{
> +       int rc;
> +       __le32 buf32[1];
> +       u32 i, nel = 0;
> +       struct avtab_node *cur;
> +       struct hashtab fnts_tab;
> +       struct filenametr_tab_insert_args tab_insert_args = {.tab = &fnts_tab};
> +       struct filenametr_write_args write_args = {.fp = fp};
> +
> +       if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> +               return 0;
> +
> +       /* count number of filename transitions */
> +       for (i = 0; i < a->nslot; i++) {
> +               for (cur = a->htable[i]; cur; cur = cur->next) {
> +                       if (cur->key.specified & AVTAB_TRANSITION)
> +                               nel += cur->datum.u.trans->name_trans.table.nel;
> +               }
> +       }
> +
> +       if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> +               buf32[0] = cpu_to_le32(nel);
> +               rc = put_entry(buf32, sizeof(u32), 1, fp);
> +               if (rc)
> +                       return rc;
> +
> +               /* write filename transitions */
> +               for (i = 0; i < a->nslot; i++) {
> +                       for (cur = a->htable[i]; cur; cur = cur->next) {
> +                               if (cur->key.specified & AVTAB_TRANSITION) {
> +                                       write_args.key = &cur->key;
> +                                       rc = hashtab_map(&cur->datum.u.trans->name_trans.table,
> +                                                        filenametr_write_helper,
> +                                                        &write_args);
> +                                       if (rc)
> +                                               return rc;
> +                               }
> +                       }
> +               }
> +
> +               return 0;
> +       }
> +
> +       /* init temp filename transition table */
> +       rc = hashtab_init(&fnts_tab, nel);
> +       if (rc)
> +               return rc;
> +
> +       for (i = 0; i < a->nslot; i++) {
> +               for (cur = a->htable[i]; cur; cur = cur->next) {
> +                       if (cur->key.specified & AVTAB_TRANSITION) {
> +                               tab_insert_args.key = &cur->key;
> +                               rc = hashtab_map(&cur->datum.u.trans->name_trans.table,
> +                                                filenametr_tab_insert,
> +                                                &tab_insert_args);
> +                               if (rc)
> +                                       goto out;
> +                       }
> +               }
> +       }
> +
> +       /* write compressed filename transitions */
> +       buf32[0] = cpu_to_le32(fnts_tab.nel);
> +       rc = put_entry(buf32, sizeof(u32), 1, fp);
> +       if (rc)
> +               goto out;
> +
> +       rc = hashtab_map(&fnts_tab, filenametr_comp_write_helper, fp);
> +
> +out:
> +       /* destroy temp filename transitions table */
> +       hashtab_map(&fnts_tab, filenametr_destroy, NULL);
> +       hashtab_destroy(&fnts_tab);
> +
> +       return rc;
> +}
> diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
> index 6c8eb7c379cf..162ef1be85e7 100644
> --- a/security/selinux/ss/avtab.h
> +++ b/security/selinux/ss/avtab.h
> @@ -22,6 +22,7 @@
>  #define _SS_AVTAB_H_
>
>  #include "security.h"
> +#include "symtab.h"
>
>  struct avtab_key {
>         u16 source_type;        /* source type */
> @@ -49,6 +50,7 @@ struct avtab_key {
>
>  struct avtab_trans {
>         u32 otype;              /* default resulting type of the new object */
> +       struct symtab name_trans;       /* filename transitions */
>  };
>
>  /*
> @@ -121,5 +123,10 @@ struct avtab_node *avtab_search_node_next(struct avtab_node *node, int specified
>  #define MAX_AVTAB_HASH_BITS 16
>  #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
>
> +/* policydb filename transitions compatibility */
> +
> +int avtab_filename_trans_read(struct avtab *a, void *fp, struct policydb *p);
> +int avtab_filename_trans_write(struct policydb *p, struct avtab *a, void *fp);
> +
>  #endif /* _SS_AVTAB_H_ */
>
> diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c
> index e11219fdf9f7..91392d65563e 100644
> --- a/security/selinux/ss/conditional.c
> +++ b/security/selinux/ss/conditional.c
> @@ -263,6 +263,7 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k,
>         struct policydb *p = data->p;
>         struct cond_av_list *other = data->other;
>         struct avtab_node *node_ptr;
> +       struct avtab_datum *existing;
>         u32 i;
>         bool found;
>
> @@ -272,7 +273,10 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k,
>          * cond_te_avtab.
>          */
>         if (k->specified & AVTAB_TYPE) {
> -               if (avtab_search(&p->te_avtab, k)) {
> +               existing = avtab_search(&p->te_avtab, k);
> +               /* empty transition rule is not a conflict */
> +               if (existing && !(k->specified & AVTAB_TRANSITION &&
> +                                 !existing->u.trans->otype)) {
>                         pr_err("SELinux: type rule already exists outside of a conditional.\n");
>                         return -EINVAL;
>                 }
> diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h
> index 043a773bf0b7..4d04acf4d5af 100644
> --- a/security/selinux/ss/hashtab.h
> +++ b/security/selinux/ss/hashtab.h
> @@ -145,4 +145,10 @@ int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
>  /* Fill info with some hash table statistics */
>  void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
>
> +/* Checks if the hashtab is empty (its size is zero) */
> +static inline int hashtab_is_empty(struct hashtab *h)
> +{
> +       return !h->size;
> +}
> +
>  #endif /* _SS_HASHTAB_H */
> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index 97c0074f9312..928a08835db8 100644
> --- a/security/selinux/ss/policydb.c
> +++ b/security/selinux/ss/policydb.c
> @@ -323,23 +323,6 @@ static int (*const destroy_f[SYM_NUM]) (void *key, void *datum, void *datap) = {
>         cat_destroy,
>  };
>
> -static int filenametr_destroy(void *key, void *datum, void *p)
> -{
> -       struct filename_trans_key *ft = key;
> -       struct filename_trans_datum *next, *d = datum;
> -
> -       kfree(ft->name);
> -       kfree(key);
> -       do {
> -               ebitmap_destroy(&d->stypes);
> -               next = d->next;
> -               kfree(d);
> -               d = next;
> -       } while (unlikely(d));
> -       cond_resched();
> -       return 0;
> -}
> -
>  static int range_tr_destroy(void *key, void *datum, void *p)
>  {
>         struct mls_range *rt = datum;
> @@ -406,50 +389,6 @@ static int roles_init(struct policydb *p)
>         return rc;
>  }
>
> -static u32 filenametr_hash(const void *k)
> -{
> -       const struct filename_trans_key *ft = k;
> -       unsigned long hash;
> -       unsigned int byte_num;
> -       unsigned char focus;
> -
> -       hash = ft->ttype ^ ft->tclass;
> -
> -       byte_num = 0;
> -       while ((focus = ft->name[byte_num++]))
> -               hash = partial_name_hash(focus, hash);
> -       return hash;
> -}
> -
> -static int filenametr_cmp(const void *k1, const void *k2)
> -{
> -       const struct filename_trans_key *ft1 = k1;
> -       const struct filename_trans_key *ft2 = k2;
> -       int v;
> -
> -       v = ft1->ttype - ft2->ttype;
> -       if (v)
> -               return v;
> -
> -       v = ft1->tclass - ft2->tclass;
> -       if (v)
> -               return v;
> -
> -       return strcmp(ft1->name, ft2->name);
> -
> -}
> -
> -static const struct hashtab_key_params filenametr_key_params = {
> -       .hash = filenametr_hash,
> -       .cmp = filenametr_cmp,
> -};
> -
> -struct filename_trans_datum *policydb_filenametr_search(
> -       struct policydb *p, struct filename_trans_key *key)
> -{
> -       return hashtab_search(&p->filename_trans, key, filenametr_key_params);
> -}
> -
>  static u32 rangetr_hash(const void *k)
>  {
>         const struct range_trans *key = k;
> @@ -531,7 +470,6 @@ static void policydb_init(struct policydb *p)
>         avtab_init(&p->te_avtab);
>         cond_policydb_init(p);
>
> -       ebitmap_init(&p->filename_trans_ttypes);
>         ebitmap_init(&p->policycaps);
>         ebitmap_init(&p->permissive_map);
>  }
> @@ -839,9 +777,6 @@ void policydb_destroy(struct policydb *p)
>         }
>         kfree(lra);
>
> -       hashtab_map(&p->filename_trans, filenametr_destroy, NULL);
> -       hashtab_destroy(&p->filename_trans);
> -
>         hashtab_map(&p->range_tr, range_tr_destroy, NULL);
>         hashtab_destroy(&p->range_tr);
>
> @@ -851,7 +786,6 @@ void policydb_destroy(struct policydb *p)
>                 kvfree(p->type_attr_map_array);
>         }
>
> -       ebitmap_destroy(&p->filename_trans_ttypes);
>         ebitmap_destroy(&p->policycaps);
>         ebitmap_destroy(&p->permissive_map);
>  }
> @@ -1066,7 +1000,7 @@ static int context_read_and_validate(struct context *c,
>   * binary representation file.
>   */
>
> -static int str_read(char **strp, gfp_t flags, void *fp, u32 len)
> +int str_read(char **strp, gfp_t flags, void *fp, u32 len)
>  {
>         int rc;
>         char *str;
> @@ -1880,220 +1814,6 @@ static int range_read(struct policydb *p, void *fp)
>         return rc;
>  }
>
> -static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
> -{
> -       struct filename_trans_key key, *ft = NULL;
> -       struct filename_trans_datum *last, *datum = NULL;
> -       char *name = NULL;
> -       u32 len, stype, otype;
> -       __le32 buf[4];
> -       int rc;
> -
> -       /* length of the path component string */
> -       rc = next_entry(buf, fp, sizeof(u32));
> -       if (rc)
> -               return rc;
> -       len = le32_to_cpu(buf[0]);
> -
> -       /* path component string */
> -       rc = str_read(&name, GFP_KERNEL, fp, len);
> -       if (rc)
> -               return rc;
> -
> -       rc = next_entry(buf, fp, sizeof(u32) * 4);
> -       if (rc)
> -               goto out;
> -
> -       stype = le32_to_cpu(buf[0]);
> -       key.ttype = le32_to_cpu(buf[1]);
> -       key.tclass = le32_to_cpu(buf[2]);
> -       key.name = name;
> -
> -       otype = le32_to_cpu(buf[3]);
> -
> -       last = NULL;
> -       datum = policydb_filenametr_search(p, &key);
> -       while (datum) {
> -               if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
> -                       /* conflicting/duplicate rules are ignored */
> -                       datum = NULL;
> -                       goto out;
> -               }
> -               if (likely(datum->otype == otype))
> -                       break;
> -               last = datum;
> -               datum = datum->next;
> -       }
> -       if (!datum) {
> -               rc = -ENOMEM;
> -               datum = kmalloc(sizeof(*datum), GFP_KERNEL);
> -               if (!datum)
> -                       goto out;
> -
> -               ebitmap_init(&datum->stypes);
> -               datum->otype = otype;
> -               datum->next = NULL;
> -
> -               if (unlikely(last)) {
> -                       last->next = datum;
> -               } else {
> -                       rc = -ENOMEM;
> -                       ft = kmemdup(&key, sizeof(key), GFP_KERNEL);
> -                       if (!ft)
> -                               goto out;
> -
> -                       rc = hashtab_insert(&p->filename_trans, ft, datum,
> -                                           filenametr_key_params);
> -                       if (rc)
> -                               goto out;
> -                       name = NULL;
> -
> -                       rc = ebitmap_set_bit(&p->filename_trans_ttypes,
> -                                            key.ttype, 1);
> -                       if (rc)
> -                               return rc;
> -               }
> -       }
> -       kfree(name);
> -       return ebitmap_set_bit(&datum->stypes, stype - 1, 1);
> -
> -out:
> -       kfree(ft);
> -       kfree(name);
> -       kfree(datum);
> -       return rc;
> -}
> -
> -static int filename_trans_read_helper(struct policydb *p, void *fp)
> -{
> -       struct filename_trans_key *ft = NULL;
> -       struct filename_trans_datum **dst, *datum, *first = NULL;
> -       char *name = NULL;
> -       u32 len, ttype, tclass, ndatum, i;
> -       __le32 buf[3];
> -       int rc;
> -
> -       /* length of the path component string */
> -       rc = next_entry(buf, fp, sizeof(u32));
> -       if (rc)
> -               return rc;
> -       len = le32_to_cpu(buf[0]);
> -
> -       /* path component string */
> -       rc = str_read(&name, GFP_KERNEL, fp, len);
> -       if (rc)
> -               return rc;
> -
> -       rc = next_entry(buf, fp, sizeof(u32) * 3);
> -       if (rc)
> -               goto out;
> -
> -       ttype = le32_to_cpu(buf[0]);
> -       tclass = le32_to_cpu(buf[1]);
> -
> -       ndatum = le32_to_cpu(buf[2]);
> -       if (ndatum == 0) {
> -               pr_err("SELinux:  Filename transition key with no datum\n");
> -               rc = -ENOENT;
> -               goto out;
> -       }
> -
> -       dst = &first;
> -       for (i = 0; i < ndatum; i++) {
> -               rc = -ENOMEM;
> -               datum = kmalloc(sizeof(*datum), GFP_KERNEL);
> -               if (!datum)
> -                       goto out;
> -
> -               *dst = datum;
> -
> -               /* ebitmap_read() will at least init the bitmap */
> -               rc = ebitmap_read(&datum->stypes, fp);
> -               if (rc)
> -                       goto out;
> -
> -               rc = next_entry(buf, fp, sizeof(u32));
> -               if (rc)
> -                       goto out;
> -
> -               datum->otype = le32_to_cpu(buf[0]);
> -               datum->next = NULL;
> -
> -               dst = &datum->next;
> -       }
> -
> -       rc = -ENOMEM;
> -       ft = kmalloc(sizeof(*ft), GFP_KERNEL);
> -       if (!ft)
> -               goto out;
> -
> -       ft->ttype = ttype;
> -       ft->tclass = tclass;
> -       ft->name = name;
> -
> -       rc = hashtab_insert(&p->filename_trans, ft, first,
> -                           filenametr_key_params);
> -       if (rc == -EEXIST)
> -               pr_err("SELinux:  Duplicate filename transition key\n");
> -       if (rc)
> -               goto out;
> -
> -       return ebitmap_set_bit(&p->filename_trans_ttypes, ttype, 1);
> -
> -out:
> -       kfree(ft);
> -       kfree(name);
> -       while (first) {
> -               datum = first;
> -               first = first->next;
> -
> -               ebitmap_destroy(&datum->stypes);
> -               kfree(datum);
> -       }
> -       return rc;
> -}
> -
> -static int filename_trans_read(struct policydb *p, void *fp)
> -{
> -       u32 nel;
> -       __le32 buf[1];
> -       int rc, i;
> -
> -       if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> -               return 0;
> -
> -       rc = next_entry(buf, fp, sizeof(u32));
> -       if (rc)
> -               return rc;
> -       nel = le32_to_cpu(buf[0]);
> -
> -       if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> -               p->compat_filename_trans_count = nel;
> -
> -               rc = hashtab_init(&p->filename_trans, (1 << 11));
> -               if (rc)
> -                       return rc;
> -
> -               for (i = 0; i < nel; i++) {
> -                       rc = filename_trans_read_helper_compat(p, fp);
> -                       if (rc)
> -                               return rc;
> -               }
> -       } else {
> -               rc = hashtab_init(&p->filename_trans, nel);
> -               if (rc)
> -                       return rc;
> -
> -               for (i = 0; i < nel; i++) {
> -                       rc = filename_trans_read_helper(p, fp);
> -                       if (rc)
> -                               return rc;
> -               }
> -       }
> -       hash_eval(&p->filename_trans, "filenametr");
> -       return 0;
> -}
> -
>  static int genfs_read(struct policydb *p, void *fp)
>  {
>         int i, j, rc;
> @@ -2634,7 +2354,7 @@ int policydb_read(struct policydb *p, void *fp)
>                 lra = ra;
>         }
>
> -       rc = filename_trans_read(p, fp);
> +       rc = avtab_filename_trans_read(&p->te_avtab, fp, p);
>         if (rc)
>                 goto bad;
>
> @@ -3480,119 +3200,6 @@ static int range_write(struct policydb *p, void *fp)
>         return 0;
>  }
>
> -static int filename_write_helper_compat(void *key, void *data, void *ptr)
> -{
> -       struct filename_trans_key *ft = key;
> -       struct filename_trans_datum *datum = data;
> -       struct ebitmap_node *node;
> -       void *fp = ptr;
> -       __le32 buf[4];
> -       int rc;
> -       u32 bit, len = strlen(ft->name);
> -
> -       do {
> -               ebitmap_for_each_positive_bit(&datum->stypes, node, bit) {
> -                       buf[0] = cpu_to_le32(len);
> -                       rc = put_entry(buf, sizeof(u32), 1, fp);
> -                       if (rc)
> -                               return rc;
> -
> -                       rc = put_entry(ft->name, sizeof(char), len, fp);
> -                       if (rc)
> -                               return rc;
> -
> -                       buf[0] = cpu_to_le32(bit + 1);
> -                       buf[1] = cpu_to_le32(ft->ttype);
> -                       buf[2] = cpu_to_le32(ft->tclass);
> -                       buf[3] = cpu_to_le32(datum->otype);
> -
> -                       rc = put_entry(buf, sizeof(u32), 4, fp);
> -                       if (rc)
> -                               return rc;
> -               }
> -
> -               datum = datum->next;
> -       } while (unlikely(datum));
> -
> -       return 0;
> -}
> -
> -static int filename_write_helper(void *key, void *data, void *ptr)
> -{
> -       struct filename_trans_key *ft = key;
> -       struct filename_trans_datum *datum;
> -       void *fp = ptr;
> -       __le32 buf[3];
> -       int rc;
> -       u32 ndatum, len = strlen(ft->name);
> -
> -       buf[0] = cpu_to_le32(len);
> -       rc = put_entry(buf, sizeof(u32), 1, fp);
> -       if (rc)
> -               return rc;
> -
> -       rc = put_entry(ft->name, sizeof(char), len, fp);
> -       if (rc)
> -               return rc;
> -
> -       ndatum = 0;
> -       datum = data;
> -       do {
> -               ndatum++;
> -               datum = datum->next;
> -       } while (unlikely(datum));
> -
> -       buf[0] = cpu_to_le32(ft->ttype);
> -       buf[1] = cpu_to_le32(ft->tclass);
> -       buf[2] = cpu_to_le32(ndatum);
> -       rc = put_entry(buf, sizeof(u32), 3, fp);
> -       if (rc)
> -               return rc;
> -
> -       datum = data;
> -       do {
> -               rc = ebitmap_write(&datum->stypes, fp);
> -               if (rc)
> -                       return rc;
> -
> -               buf[0] = cpu_to_le32(datum->otype);
> -               rc = put_entry(buf, sizeof(u32), 1, fp);
> -               if (rc)
> -                       return rc;
> -
> -               datum = datum->next;
> -       } while (unlikely(datum));
> -
> -       return 0;
> -}
> -
> -static int filename_trans_write(struct policydb *p, void *fp)
> -{
> -       __le32 buf[1];
> -       int rc;
> -
> -       if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> -               return 0;
> -
> -       if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> -               buf[0] = cpu_to_le32(p->compat_filename_trans_count);
> -               rc = put_entry(buf, sizeof(u32), 1, fp);
> -               if (rc)
> -                       return rc;
> -
> -               rc = hashtab_map(&p->filename_trans,
> -                                filename_write_helper_compat, fp);
> -       } else {
> -               buf[0] = cpu_to_le32(p->filename_trans.nel);
> -               rc = put_entry(buf, sizeof(u32), 1, fp);
> -               if (rc)
> -                       return rc;
> -
> -               rc = hashtab_map(&p->filename_trans, filename_write_helper, fp);
> -       }
> -       return rc;
> -}
> -
>  /*
>   * Write the configuration data in a policy database
>   * structure to a policy database binary representation
> @@ -3703,7 +3310,7 @@ int policydb_write(struct policydb *p, void *fp)
>         if (rc)
>                 return rc;
>
> -       rc = filename_trans_write(p, fp);
> +       rc = avtab_filename_trans_write(p, &p->te_avtab, fp);
>         if (rc)
>                 return rc;
>
> diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> index ffc4e7bad205..2ecb24a1611a 100644
> --- a/security/selinux/ss/policydb.h
> +++ b/security/selinux/ss/policydb.h
> @@ -91,18 +91,6 @@ struct role_trans_datum {
>         u32 new_role;           /* new role */
>  };
>
> -struct filename_trans_key {
> -       u32 ttype;              /* parent dir context */
> -       u16 tclass;             /* class of new object */
> -       const char *name;       /* last path component */
> -};
> -
> -struct filename_trans_datum {
> -       struct ebitmap stypes;  /* bitmap of source types for this otype */
> -       u32 otype;              /* resulting type of new object */
> -       struct filename_trans_datum *next;      /* record for next otype*/
> -};
> -
>  struct role_allow {
>         u32 role;               /* current role */
>         u32 new_role;           /* new role */
> @@ -265,14 +253,6 @@ struct policydb {
>         /* role transitions */
>         struct hashtab role_tr;
>
> -       /* file transitions with the last path component */
> -       /* quickly exclude lookups when parent ttype has no rules */
> -       struct ebitmap filename_trans_ttypes;
> -       /* actual set of filename_trans rules */
> -       struct hashtab filename_trans;
> -       /* only used if policyvers < POLICYDB_VERSION_COMP_FTRANS */
> -       u32 compat_filename_trans_count;
> -
>         /* bools indexed by (value - 1) */
>         struct cond_bool_datum **bool_val_to_struct;
>         /* type enforcement conditional access vectors and transitions */
> @@ -324,9 +304,6 @@ 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);
>
> -extern struct filename_trans_datum *policydb_filenametr_search(
> -       struct policydb *p, struct filename_trans_key *key);
> -
>  extern struct mls_range *policydb_rangetr_search(
>         struct policydb *p, struct range_trans *key);
>
> @@ -379,6 +356,8 @@ static inline int put_entry(const void *buf, size_t bytes, int num, struct polic
>         return 0;
>  }
>
> +extern int str_read(char **strp, gfp_t flags, void *fp, u32 len);
> +
>  static inline char *sym_name(struct policydb *p, unsigned int sym_num, unsigned int element_nr)
>  {
>         return p->sym_val_to_name[sym_num][element_nr];
> diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> index 8ed12406acba..131647e7ec68 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -1661,36 +1661,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_key ft;
> -       struct filename_trans_datum *datum;
> -
> -       /*
> -        * 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.ttype = ttype;
> -       ft.tclass = tclass;
> -       ft.name = objname;
> -
> -       datum = policydb_filenametr_search(policydb, &ft);
> -       while (datum) {
> -               if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
> -                       newcontext->type = datum->otype;
> -                       return;
> -               }
> -               datum = datum->next;
> -       }
> -}
> -
>  static int security_compute_sid(u32 ssid,
>                                 u32 tsid,
>                                 u16 orig_tclass,
> @@ -1711,6 +1681,7 @@ static int security_compute_sid(u32 ssid,
>         u16 tclass;
>         int rc = 0;
>         bool sock;
> +       u32 *otype;
>
>         if (!selinux_initialized()) {
>                 switch (orig_tclass) {
> @@ -1830,17 +1801,24 @@ static int security_compute_sid(u32 ssid,
>
>         if (avdatum) {
>                 /* Use the type from the type transition/member/change rule. */
> -               if (avkey.specified & AVTAB_TRANSITION)
> -                       newcontext.type = avdatum->u.trans->otype;
> -               else
> +               if (avkey.specified & AVTAB_TRANSITION) {
> +                       /*
> +                        * use default otype if not empty and then to try to
> +                        * find more specific rule using objname
> +                        */
> +                       if (avdatum->u.trans->otype)
> +                               newcontext.type = avdatum->u.trans->otype;
> +                       if (objname) {
> +                               otype = symtab_search(&avdatum->u.trans->name_trans,
> +                                                     objname);
> +                               if (otype)
> +                                       newcontext.type = *otype;
> +                       }
> +               } else {
>                         newcontext.type = avdatum->u.data;
> +               }
>         }
>
> -       /* 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);
> -
>         /* Check for class-specific changes. */
>         if (specified & AVTAB_TRANSITION) {
>                 /* Look for a role transition rule. */
> --
> 2.40.0
>

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Juraj Marcin]

On 2023-05-31 18:24, Paul Moore wrote:
> On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> >
> > Currently, filename transitions are stored separately from other type
> > enforcement rules and only support exact name matching. However, in
> > practice, the names contain variable parts. This leads to many
> > duplicated rules in the policy that differ only in the part of the name,
> > or it is even impossible to cover all possible combinations.
> >
> > First, this series of patches moves the filename transitions to be part
> > of the avtab structures. This not only makes the implementation of
> > prefix/suffix matching and future enhancements easier, but also reduces
> > the technical debt regarding the filename transitions. Next, the last
> > patch implements the support for prefix/suffix name matching itself by
> > extending the structures added in previous patches in this series.
> >
> > Even though, moving everything to avtab increases the memory usage and
> > the size of the binary policy itself and thus the loading time, the
> > ability to match the prefix or suffix of the name will reduce the
> > overall number of rules in the policy which should mitigate this issue.
> >
> > This implementation has been successfully tested using the existing and
> > also new tests in the SELinux Testsuite.
> >
> > Juraj Marcin (5):
> >   selinux: move transition to separate structure in avtab_datum
> >   selinux: move filename transitions to avtab
> >   selinux: implement new binary format for filename transitions in avtab
> >   selinux: filename transitions move tests
> >   selinux: add prefix/suffix matching support to filename type
> >     transitions
> 
> Just a quick comment as I haven't had a chance to properly review this
> series yet; you show some memory usage and performance measurements in
> some of the intermediate patches, that's good, but I don't see the
> same measurements taken when the full patchset is applied.  Please
> provide the same memory usage and performance comparisons with the
> full patchset applied.

Of course, here are the measurements with the whole patchset applied.

I also included measurements with new policy (based on the Fedora
policy) that uses prefix filename transitions where possible. This new
policy has been generated by merging existing filename transitions into
prefix ones if it would reduce the number of transitions overall while
keeping the resulting type same.


[1] Reference kernel (c52df19e3759), Fedora policy (format v33)
[2] This patchset, Fedora policy (format v33)
[3] This patchset, Fedora policy without prefix/suffix rules (format v35)
[4] This patchset, Fedora policy with prefix rules (format v35)


 Test | Mem   | Binary | Policy | Create tty      | osbench
      | Usage | policy | load   |                 | create
      |       | size   | time   | (ms/file)       | files 
      | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
------+-------+--------+--------+--------+--------+-----------
 [1]  |   157 |    3.4 |     78 | 1.1021 | 0.7586 | 7.8277
 [2]  |   200 |    3.4 |    206 | 1.1193 | 0.7724 | 8.2711
 [3]  |   169 |    5.8 |    106 | 1.1021 | 0.7724 | 8.0304
 [4]  |   164 |    3.8 |     86 | 1.1029 | 0.7586 | 7.9609


> 
> -- 
> paul-moore.com

-- 
Juraj Marcin

Re: [PATCH 2/5] selinux: move filename transitions to avtab

[Christian Göttsche]

On Wed, 31 May 2023 at 13:32, Juraj Marcin <juraj@jurajmarcin.com> wrote:
>
> Currently, filename transitions are stored separately from other type
> enforcement rules. This leads to possibly sub-optimal performance and
> makes further improvements cumbersome.
>
> This patch adds a symbol table of filename transitions to the transition
> structure added to avtab in the previous patch. It also implements
> functions required for reading and writing filename transitions in
> kernel policy format and updates computation of new type to use filename
> transitions embedded in avtab. Last but not least, it updates the
> conflict check in the conditional avtab to account for empty transitions
> in the non-conditional avtab.
>
> These changes are expected to cause higher memory usage, as now there
> needs to be a filename transition structure for every stype. This patch
> effectively undoes most of the commit c3a276111ea2 ("selinux: optimize
> storage of filename transitions"), but this will be mitigated by
> providing support for matching prefix/suffix of the filename for
> filename transitions in future patches which will reduce to need to have
> so many of them.
>
> On the other hand, the changes do not significantly slow down the
> creation of new files.
>
> Kernel     | Mem   | Create test_tty | Create test_tty | osbench [1]
>            | usage | (real time)     | (kernel time)   | create_files
> -----------+-------+-----------------+-----------------+--------------
> reference  | 155MB |  1.3440 ms/file |  1.0071 ms/file | 10.6507 us/file
> this patch | 198MB |  1.3912 ms/file |  1.0172 ms/file | 10.5567 us/file
>
> Create test_tty benchmark:
>
>     mknod /dev/test_tty c 4 1
>     time for i in `seq 1 10000`; do
>         mknod /dev/test_tty$i c 4 1
>     done
>
> This benchmark should simulate the worst case scenario as many filename
> transitions affect files created in the /dev directory.
>
> [1] https://github.com/mbitsnbites/osbench
>
> Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
> Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> ---
>  security/selinux/ss/avtab.c       | 516 ++++++++++++++++++++++++++++++
>  security/selinux/ss/avtab.h       |   7 +
>  security/selinux/ss/conditional.c |   6 +-
>  security/selinux/ss/hashtab.h     |   6 +
>  security/selinux/ss/policydb.c    | 399 +----------------------
>  security/selinux/ss/policydb.h    |  25 +-
>  security/selinux/ss/services.c    |  54 +---
>  7 files changed, 555 insertions(+), 458 deletions(-)
>
> diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
> index a7f348e4509d..fe921e1586e5 100644
> --- a/security/selinux/ss/avtab.c
> +++ b/security/selinux/ss/avtab.c
> @@ -22,6 +22,7 @@
>  #include <linux/errno.h>
>  #include "avtab.h"
>  #include "policydb.h"
> +#include "hashtab.h"
>
>  static struct kmem_cache *avtab_node_cachep __ro_after_init;
>  static struct kmem_cache *avtab_trans_cachep __ro_after_init;
> @@ -286,6 +287,19 @@ avtab_search_node_next(struct avtab_node *node, int specified)
>         return NULL;
>  }
>
> +static int avtab_trans_destroy_helper(void *k, void *d, void *args)
> +{
> +       kfree(k);
> +       kfree(d);
> +       return 0;
> +}
> +
> +static void avtab_trans_destroy(struct avtab_trans *trans)
> +{
> +       hashtab_map(&trans->name_trans.table, avtab_trans_destroy_helper, NULL);
> +       hashtab_destroy(&trans->name_trans.table);
> +}
> +
>  void avtab_destroy(struct avtab *h)
>  {
>         int i;
> @@ -303,6 +317,7 @@ void avtab_destroy(struct avtab *h)
>                                 kmem_cache_free(avtab_xperms_cachep,
>                                                 temp->datum.u.xperms);
>                         } else if (temp->key.specified & AVTAB_TRANSITION) {
> +                               avtab_trans_destroy(temp->datum.u.trans);
>                                 kmem_cache_free(avtab_trans_cachep,
>                                                 temp->datum.u.trans);
>                         }
> @@ -587,6 +602,7 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
>         if (key.specified & AVTAB_TRANSITION) {
>                 if (!policydb_type_isvalid(pol, datum.u.trans->otype)) {
>                         pr_err("SELinux: avtab: invalid transition type\n");
> +                       avtab_trans_destroy(&trans);
>                         return -EINVAL;
>                 }
>         } else if (key.specified & AVTAB_TYPE) {
> @@ -596,6 +612,8 @@ int avtab_read_item(struct avtab *a, void *fp, struct policydb *pol,
>                 }
>         }
>         rc = insertf(a, &key, &datum, p);
> +       if (rc && key.specified & AVTAB_TRANSITION)
> +               avtab_trans_destroy(&trans);
>         return rc;
>  }
>
> @@ -656,6 +674,10 @@ int avtab_write_item(struct policydb *p, const struct avtab_node *cur, void *fp)
>         int rc;
>         unsigned int i;
>
> +       if (cur->key.specified & AVTAB_TRANSITION &&
> +           !cur->datum.u.trans->otype)
> +               return 0;
> +
>         buf16[0] = cpu_to_le16(cur->key.source_type);
>         buf16[1] = cpu_to_le16(cur->key.target_type);
>         buf16[2] = cpu_to_le16(cur->key.target_class);
> @@ -723,3 +745,497 @@ void __init avtab_cache_init(void)
>                                                 sizeof(struct avtab_extended_perms),
>                                                 0, SLAB_PANIC, NULL);
>  }
> +
> +/* policydb filename transitions compatibility */
> +
> +static int avtab_insert_filename_trans(struct avtab *a,
> +                                      const struct avtab_key *key,
> +                                      char *name, u32 otype)
> +{
> +       int rc;
> +       struct avtab_node *node;
> +       struct avtab_trans new_trans = {0};
> +       struct avtab_datum new_datum = {.u.trans = &new_trans};
> +       struct avtab_datum *datum;
> +       u32 *otype_datum = NULL;
> +
> +       datum = avtab_search(a, key);
> +       if (!datum) {
> +               /*
> +                * insert is acctually unique, but with this function we can get
> +                * the inserted node and therefore the datum
> +                */
> +               node = avtab_insert_nonunique(a, key, &new_datum);
> +               if (!node)
> +                       return -ENOMEM;
> +               datum = &node->datum;
> +       }
> +
> +       if (hashtab_is_empty(&datum->u.trans->name_trans.table)) {
> +               rc = symtab_init(&datum->u.trans->name_trans, 1 << 8);
> +               if (rc)
> +                       return rc;
> +       }
> +
> +       otype_datum = kmalloc(sizeof(u32), GFP_KERNEL);
> +       if (!otype_datum)
> +               return -ENOMEM;
> +       *otype_datum = otype;
> +
> +       rc = symtab_insert(&datum->u.trans->name_trans, name, otype_datum);
> +       if (rc)
> +               kfree(otype_datum);
> +
> +       return rc;
> +}
> +
> +static int filename_trans_read_item(struct avtab *a, void *fp)
> +{
> +       int rc;
> +       __le32 buf32[4];
> +       u32 len, otype;
> +       char *name = NULL;
> +       struct avtab_key key;
> +
> +       /* read length of the name */
> +       rc = next_entry(buf32, fp, sizeof(u32));
> +       if (rc)
> +               return rc;
> +       len = le32_to_cpu(buf32[0]);
> +
> +       /* read the name */
> +       rc = str_read(&name, GFP_KERNEL, fp, len);
> +       if (rc)
> +               return rc;
> +
> +       /* read stype, ttype, tclass and otype */
> +       rc = next_entry(buf32, fp, sizeof(u32) * 4);
> +       if (rc)
> +               goto bad;
> +
> +       key.source_type = le32_to_cpu(buf32[0]);
> +       key.target_type = le32_to_cpu(buf32[1]);
> +       key.target_class = le32_to_cpu(buf32[2]);
> +       key.specified = AVTAB_TRANSITION;
> +
> +       otype = le32_to_cpu(buf32[3]);
> +
> +       rc = avtab_insert_filename_trans(a, &key, name, otype);
> +       if (rc)
> +               goto bad;
> +
> +       return rc;
> +
> +bad:
> +       kfree(name);
> +       return rc;
> +}
> +
> +static int filename_trans_comp_read_item(struct avtab *a, void *fp)
> +{
> +       int rc;
> +       __le32 buf32[3];
> +       u32 len, ndatum, i, bit, otype;
> +       char *name = NULL, *name_copy = NULL;
> +       struct avtab_key key;
> +       struct ebitmap stypes;
> +       struct ebitmap_node *node;
> +
> +       /* read length of the name */
> +       rc = next_entry(buf32, fp, sizeof(u32));
> +       if (rc)
> +               return rc;
> +       len = le32_to_cpu(*buf32);
> +
> +       /* read the name */
> +       rc = str_read(&name, GFP_KERNEL, fp, len);
> +       if (rc)
> +               goto out;
> +
> +       /* read target type, target class and number of elements for key */
> +       rc = next_entry(buf32, fp, sizeof(u32) * 3);
> +       if (rc)
> +               goto out;
> +
> +       key.specified = AVTAB_TRANSITION;
> +       key.target_type = le32_to_cpu(buf32[0]);
> +       key.target_class = le32_to_cpu(buf32[1]);
> +
> +       ndatum = le32_to_cpu(buf32[2]);
> +       if (ndatum == 0) {
> +               pr_err("SELinux:  Filename transition key with no datum\n");
> +               rc = -ENOENT;
> +               goto out;
> +       }
> +
> +       for (i = 0; i < ndatum; i++) {
> +               rc = ebitmap_read(&stypes, fp);
> +               if (rc)
> +                       goto out;
> +
> +               rc = next_entry(buf32, fp, sizeof(u32));
> +               if (rc) {
> +                       ebitmap_destroy(&stypes);
> +                       goto out;
> +               }
> +               otype = le32_to_cpu(*buf32);
> +
> +               ebitmap_for_each_positive_bit(&stypes, node, bit) {
> +                       key.source_type = bit + 1;
> +
> +                       name_copy = kmemdup(name, len + 1, GFP_KERNEL);
> +                       if (!name_copy) {
> +                               ebitmap_destroy(&stypes);
> +                               goto out;
> +                       }
> +
> +                       rc = avtab_insert_filename_trans(a, &key, name_copy,
> +                                                        otype);
> +                       if (rc) {
> +                               ebitmap_destroy(&stypes);
> +                               kfree(name_copy);
> +                               goto out;
> +                       }
> +               }
> +
> +               ebitmap_destroy(&stypes);
> +       }
> +       rc = 0;
> +
> +out:
> +       kfree(name);
> +       return rc;
> +}
> +
> +int avtab_filename_trans_read(struct avtab *a, void *fp, struct policydb *p)
> +{
> +       int rc;
> +       __le32 buf[1];
> +       u32 nel, i;
> +
> +       if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> +               return 0;
> +
> +       rc = next_entry(buf, fp, sizeof(u32));
> +       if (rc)
> +               return rc;
> +       nel = le32_to_cpu(buf[0]);
> +
> +       if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> +               for (i = 0; i < nel; i++) {
> +                       rc = filename_trans_read_item(a, fp);
> +                       if (rc)
> +                               return rc;
> +               }
> +       } else {
> +               for (i = 0; i < nel; i++) {
> +                       rc = filename_trans_comp_read_item(a, fp);
> +                       if (rc)
> +                               return rc;
> +               }
> +       }
> +
> +       return 0;
> +}
> +
> +
> +struct filenametr_write_args {
> +       void *fp;
> +       struct avtab_key *key;
> +};
> +
> +static int filenametr_write_helper(void *k, void *d, void *a)
> +{
> +       char *name = k;
> +       u32 *otype = d;
> +       struct filenametr_write_args *args = a;
> +       int rc;
> +       u32 len;
> +       __le32 buf32[4];
> +
> +       len = strlen(name);
> +       buf32[0] = cpu_to_le32(len);
> +       rc = put_entry(buf32, sizeof(u32), 1, args->fp);
> +       if (rc)
> +               return rc;
> +
> +       rc = put_entry(name, sizeof(char), len, args->fp);
> +       if (rc)
> +               return rc;
> +
> +       buf32[0] = cpu_to_le32(args->key->source_type);
> +       buf32[1] = cpu_to_le32(args->key->target_type);
> +       buf32[2] = cpu_to_le32(args->key->target_class);
> +       buf32[3] = cpu_to_le32(*otype);
> +
> +       rc = put_entry(buf32, sizeof(u32), 4, args->fp);
> +       if (rc)
> +               return rc;
> +
> +       return 0;
> +}
> +
> +struct filenametr_key {
> +       u32 ttype;              /* parent dir context */
> +       u16 tclass;             /* class of new object */
> +       const char *name;       /* last path component */
> +};
> +
> +struct filenametr_datum {
> +       struct ebitmap stypes;  /* bitmap of source types for this otype */
> +       u32 otype;              /* resulting type of new object */
> +       struct filenametr_datum *next;  /* record for next otype*/
> +};
> +
> +static int filenametr_comp_write_helper(void *k, void *d, void *fp)
> +{
> +       struct filenametr_key *key = k;
> +       struct filenametr_datum *datum = d;
> +       __le32 buf[3];
> +       int rc;
> +       u32 ndatum, len = strlen(key->name);
> +       struct filenametr_datum *cur;
> +
> +       buf[0] = cpu_to_le32(len);
> +       rc = put_entry(buf, sizeof(u32), 1, fp);
> +       if (rc)
> +               return rc;
> +
> +       rc = put_entry(key->name, sizeof(char), len, fp);
> +       if (rc)
> +               return rc;
> +
> +       ndatum = 0;
> +       cur = datum;
> +       do {
> +               ndatum++;
> +               cur = cur->next;
> +       } while (unlikely(cur));
> +
> +       buf[0] = cpu_to_le32(key->ttype);
> +       buf[1] = cpu_to_le32(key->tclass);
> +       buf[2] = cpu_to_le32(ndatum);
> +       rc = put_entry(buf, sizeof(u32), 3, fp);
> +       if (rc)
> +               return rc;
> +
> +       cur = datum;
> +       do {
> +               rc = ebitmap_write(&cur->stypes, fp);
> +               if (rc)
> +                       return rc;
> +
> +               buf[0] = cpu_to_le32(cur->otype);
> +               rc = put_entry(buf, sizeof(u32), 1, fp);
> +               if (rc)
> +                       return rc;
> +
> +               cur = cur->next;
> +       } while (unlikely(cur));
> +
> +       return 0;
> +}
> +
> +static int filenametr_destroy(void *k, void *d, void *args)
> +{
> +       struct filenametr_key *key = k;
> +       struct filenametr_datum *datum = d;
> +       struct filenametr_datum *next;
> +
> +       kfree(key);
> +       do {
> +               ebitmap_destroy(&datum->stypes);
> +               next = datum->next;
> +               kfree(datum);
> +               datum = next;
> +       } while (unlikely(datum));
> +       cond_resched();
> +       return 0;
> +}
> +
> +static u32 filenametr_hash(const void *k)
> +{
> +       const struct filenametr_key *ft = k;
> +       unsigned long hash;
> +       unsigned int byte_num;
> +       unsigned char focus;
> +
> +       hash = ft->ttype ^ ft->tclass;
> +
> +       byte_num = 0;
> +       while ((focus = ft->name[byte_num++]))
> +               hash = partial_name_hash(focus, hash);
> +       return hash;
> +}
> +
> +static int filenametr_cmp(const void *k1, const void *k2)
> +{
> +       const struct filenametr_key *ft1 = k1;
> +       const struct filenametr_key *ft2 = k2;
> +       int v;
> +
> +       v = ft1->ttype - ft2->ttype;
> +       if (v)
> +               return v;
> +
> +       v = ft1->tclass - ft2->tclass;
> +       if (v)
> +               return v;
> +
> +       return strcmp(ft1->name, ft2->name);
> +}
> +
> +static const struct hashtab_key_params filenametr_key_params = {
> +       .hash = filenametr_hash,
> +       .cmp = filenametr_cmp,
> +};
> +
> +struct filenametr_tab_insert_args {
> +       struct avtab_key *key;
> +       struct hashtab *tab;
> +};
> +
> +static int filenametr_tab_insert(void *k, void *d, void *a)
> +{
> +       char *name = k;
> +       u32 *otype = d;
> +       struct filenametr_tab_insert_args *args = a;
> +       struct filenametr_key key, *ft = NULL;
> +       struct filenametr_datum *last, *datum = NULL;
> +       int rc;
> +
> +       key.ttype = args->key->target_type;
> +       key.tclass = args->key->target_class;
> +       key.name = name;
> +
> +       last = NULL;
> +       datum = hashtab_search(args->tab, &key, filenametr_key_params);
> +       while (datum) {
> +               if (unlikely(ebitmap_get_bit(&datum->stypes,
> +                                            args->key->source_type - 1))) {
> +                       /* conflicting/duplicate rules are ignored */
> +                       datum = NULL;
> +                       goto bad;
> +               }
> +               if (likely(datum->otype == *otype))
> +                       break;
> +               last = datum;
> +               datum = datum->next;
> +       }
> +       if (!datum) {
> +               rc = -ENOMEM;
> +               datum = kmalloc(sizeof(*datum), GFP_KERNEL);
> +               if (!datum)
> +                       goto bad;
> +
> +               ebitmap_init(&datum->stypes);
> +               datum->otype = *otype;
> +               datum->next = NULL;
> +
> +               if (unlikely(last)) {
> +                       last->next = datum;
> +               } else {
> +                       rc = -ENOMEM;
> +                       ft = kmemdup(&key, sizeof(key), GFP_KERNEL);
> +                       if (!ft)
> +                               goto bad;
> +
> +                       ft->name = kmemdup(key.name, strlen(key.name) + 1,
> +                                          GFP_KERNEL);
> +                       if (!ft->name)
> +                               goto bad;
> +
> +                       rc = hashtab_insert(args->tab, ft, datum,
> +                                           filenametr_key_params);
> +                       if (rc)
> +                               goto bad;
> +               }
> +       }
> +
> +       return ebitmap_set_bit(&datum->stypes, args->key->source_type - 1, 1);
> +
> +bad:
> +       if (ft)
> +               kfree(ft->name);
> +       kfree(ft);
> +       kfree(datum);
> +       return rc;
> +}
> +
> +int avtab_filename_trans_write(struct policydb *p, struct avtab *a, void *fp)
> +{
> +       int rc;
> +       __le32 buf32[1];
> +       u32 i, nel = 0;
> +       struct avtab_node *cur;
> +       struct hashtab fnts_tab;
> +       struct filenametr_tab_insert_args tab_insert_args = {.tab = &fnts_tab};
> +       struct filenametr_write_args write_args = {.fp = fp};
> +
> +       if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> +               return 0;
> +
> +       /* count number of filename transitions */
> +       for (i = 0; i < a->nslot; i++) {
> +               for (cur = a->htable[i]; cur; cur = cur->next) {
> +                       if (cur->key.specified & AVTAB_TRANSITION)
> +                               nel += cur->datum.u.trans->name_trans.table.nel;
> +               }
> +       }
> +
> +       if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> +               buf32[0] = cpu_to_le32(nel);
> +               rc = put_entry(buf32, sizeof(u32), 1, fp);
> +               if (rc)
> +                       return rc;
> +
> +               /* write filename transitions */
> +               for (i = 0; i < a->nslot; i++) {
> +                       for (cur = a->htable[i]; cur; cur = cur->next) {
> +                               if (cur->key.specified & AVTAB_TRANSITION) {
> +                                       write_args.key = &cur->key;
> +                                       rc = hashtab_map(&cur->datum.u.trans->name_trans.table,
> +                                                        filenametr_write_helper,
> +                                                        &write_args);
> +                                       if (rc)
> +                                               return rc;
> +                               }
> +                       }
> +               }
> +
> +               return 0;
> +       }
> +
> +       /* init temp filename transition table */
> +       rc = hashtab_init(&fnts_tab, nel);
> +       if (rc)
> +               return rc;
> +
> +       for (i = 0; i < a->nslot; i++) {
> +               for (cur = a->htable[i]; cur; cur = cur->next) {
> +                       if (cur->key.specified & AVTAB_TRANSITION) {
> +                               tab_insert_args.key = &cur->key;
> +                               rc = hashtab_map(&cur->datum.u.trans->name_trans.table,
> +                                                filenametr_tab_insert,
> +                                                &tab_insert_args);
> +                               if (rc)
> +                                       goto out;
> +                       }
> +               }
> +       }
> +
> +       /* write compressed filename transitions */
> +       buf32[0] = cpu_to_le32(fnts_tab.nel);
> +       rc = put_entry(buf32, sizeof(u32), 1, fp);
> +       if (rc)
> +               goto out;
> +
> +       rc = hashtab_map(&fnts_tab, filenametr_comp_write_helper, fp);
> +
> +out:
> +       /* destroy temp filename transitions table */
> +       hashtab_map(&fnts_tab, filenametr_destroy, NULL);
> +       hashtab_destroy(&fnts_tab);
> +
> +       return rc;
> +}
> diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
> index 6c8eb7c379cf..162ef1be85e7 100644
> --- a/security/selinux/ss/avtab.h
> +++ b/security/selinux/ss/avtab.h
> @@ -22,6 +22,7 @@
>  #define _SS_AVTAB_H_
>
>  #include "security.h"
> +#include "symtab.h"
>
>  struct avtab_key {
>         u16 source_type;        /* source type */
> @@ -49,6 +50,7 @@ struct avtab_key {
>
>  struct avtab_trans {
>         u32 otype;              /* default resulting type of the new object */
> +       struct symtab name_trans;       /* filename transitions */

What about using a bare hashtab to save the 4 bytes for the unused
nprim member (+padding)?

Also what about instead of storing an extra allocated u32 in the
tables use the pointer itself as value?

>  };
>
>  /*
> @@ -121,5 +123,10 @@ struct avtab_node *avtab_search_node_next(struct avtab_node *node, int specified
>  #define MAX_AVTAB_HASH_BITS 16
>  #define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
>
> +/* policydb filename transitions compatibility */
> +
> +int avtab_filename_trans_read(struct avtab *a, void *fp, struct policydb *p);
> +int avtab_filename_trans_write(struct policydb *p, struct avtab *a, void *fp);
> +
>  #endif /* _SS_AVTAB_H_ */
>
> diff --git a/security/selinux/ss/conditional.c b/security/selinux/ss/conditional.c
> index e11219fdf9f7..91392d65563e 100644
> --- a/security/selinux/ss/conditional.c
> +++ b/security/selinux/ss/conditional.c
> @@ -263,6 +263,7 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k,
>         struct policydb *p = data->p;
>         struct cond_av_list *other = data->other;
>         struct avtab_node *node_ptr;
> +       struct avtab_datum *existing;
>         u32 i;
>         bool found;
>
> @@ -272,7 +273,10 @@ static int cond_insertf(struct avtab *a, const struct avtab_key *k,
>          * cond_te_avtab.
>          */
>         if (k->specified & AVTAB_TYPE) {
> -               if (avtab_search(&p->te_avtab, k)) {
> +               existing = avtab_search(&p->te_avtab, k);
> +               /* empty transition rule is not a conflict */
> +               if (existing && !(k->specified & AVTAB_TRANSITION &&
> +                                 !existing->u.trans->otype)) {
>                         pr_err("SELinux: type rule already exists outside of a conditional.\n");
>                         return -EINVAL;
>                 }
> diff --git a/security/selinux/ss/hashtab.h b/security/selinux/ss/hashtab.h
> index 043a773bf0b7..4d04acf4d5af 100644
> --- a/security/selinux/ss/hashtab.h
> +++ b/security/selinux/ss/hashtab.h
> @@ -145,4 +145,10 @@ int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
>  /* Fill info with some hash table statistics */
>  void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
>
> +/* Checks if the hashtab is empty (its size is zero) */
> +static inline int hashtab_is_empty(struct hashtab *h)
> +{
> +       return !h->size;
> +}
> +
>  #endif /* _SS_HASHTAB_H */
> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index 97c0074f9312..928a08835db8 100644
> --- a/security/selinux/ss/policydb.c
> +++ b/security/selinux/ss/policydb.c
> @@ -323,23 +323,6 @@ static int (*const destroy_f[SYM_NUM]) (void *key, void *datum, void *datap) = {
>         cat_destroy,
>  };
>
> -static int filenametr_destroy(void *key, void *datum, void *p)
> -{
> -       struct filename_trans_key *ft = key;
> -       struct filename_trans_datum *next, *d = datum;
> -
> -       kfree(ft->name);
> -       kfree(key);
> -       do {
> -               ebitmap_destroy(&d->stypes);
> -               next = d->next;
> -               kfree(d);
> -               d = next;
> -       } while (unlikely(d));
> -       cond_resched();
> -       return 0;
> -}
> -
>  static int range_tr_destroy(void *key, void *datum, void *p)
>  {
>         struct mls_range *rt = datum;
> @@ -406,50 +389,6 @@ static int roles_init(struct policydb *p)
>         return rc;
>  }
>
> -static u32 filenametr_hash(const void *k)
> -{
> -       const struct filename_trans_key *ft = k;
> -       unsigned long hash;
> -       unsigned int byte_num;
> -       unsigned char focus;
> -
> -       hash = ft->ttype ^ ft->tclass;
> -
> -       byte_num = 0;
> -       while ((focus = ft->name[byte_num++]))
> -               hash = partial_name_hash(focus, hash);
> -       return hash;
> -}
> -
> -static int filenametr_cmp(const void *k1, const void *k2)
> -{
> -       const struct filename_trans_key *ft1 = k1;
> -       const struct filename_trans_key *ft2 = k2;
> -       int v;
> -
> -       v = ft1->ttype - ft2->ttype;
> -       if (v)
> -               return v;
> -
> -       v = ft1->tclass - ft2->tclass;
> -       if (v)
> -               return v;
> -
> -       return strcmp(ft1->name, ft2->name);
> -
> -}
> -
> -static const struct hashtab_key_params filenametr_key_params = {
> -       .hash = filenametr_hash,
> -       .cmp = filenametr_cmp,
> -};
> -
> -struct filename_trans_datum *policydb_filenametr_search(
> -       struct policydb *p, struct filename_trans_key *key)
> -{
> -       return hashtab_search(&p->filename_trans, key, filenametr_key_params);
> -}
> -
>  static u32 rangetr_hash(const void *k)
>  {
>         const struct range_trans *key = k;
> @@ -531,7 +470,6 @@ static void policydb_init(struct policydb *p)
>         avtab_init(&p->te_avtab);
>         cond_policydb_init(p);
>
> -       ebitmap_init(&p->filename_trans_ttypes);
>         ebitmap_init(&p->policycaps);
>         ebitmap_init(&p->permissive_map);
>  }
> @@ -839,9 +777,6 @@ void policydb_destroy(struct policydb *p)
>         }
>         kfree(lra);
>
> -       hashtab_map(&p->filename_trans, filenametr_destroy, NULL);
> -       hashtab_destroy(&p->filename_trans);
> -
>         hashtab_map(&p->range_tr, range_tr_destroy, NULL);
>         hashtab_destroy(&p->range_tr);
>
> @@ -851,7 +786,6 @@ void policydb_destroy(struct policydb *p)
>                 kvfree(p->type_attr_map_array);
>         }
>
> -       ebitmap_destroy(&p->filename_trans_ttypes);
>         ebitmap_destroy(&p->policycaps);
>         ebitmap_destroy(&p->permissive_map);
>  }
> @@ -1066,7 +1000,7 @@ static int context_read_and_validate(struct context *c,
>   * binary representation file.
>   */
>
> -static int str_read(char **strp, gfp_t flags, void *fp, u32 len)
> +int str_read(char **strp, gfp_t flags, void *fp, u32 len)
>  {
>         int rc;
>         char *str;
> @@ -1880,220 +1814,6 @@ static int range_read(struct policydb *p, void *fp)
>         return rc;
>  }
>
> -static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
> -{
> -       struct filename_trans_key key, *ft = NULL;
> -       struct filename_trans_datum *last, *datum = NULL;
> -       char *name = NULL;
> -       u32 len, stype, otype;
> -       __le32 buf[4];
> -       int rc;
> -
> -       /* length of the path component string */
> -       rc = next_entry(buf, fp, sizeof(u32));
> -       if (rc)
> -               return rc;
> -       len = le32_to_cpu(buf[0]);
> -
> -       /* path component string */
> -       rc = str_read(&name, GFP_KERNEL, fp, len);
> -       if (rc)
> -               return rc;
> -
> -       rc = next_entry(buf, fp, sizeof(u32) * 4);
> -       if (rc)
> -               goto out;
> -
> -       stype = le32_to_cpu(buf[0]);
> -       key.ttype = le32_to_cpu(buf[1]);
> -       key.tclass = le32_to_cpu(buf[2]);
> -       key.name = name;
> -
> -       otype = le32_to_cpu(buf[3]);
> -
> -       last = NULL;
> -       datum = policydb_filenametr_search(p, &key);
> -       while (datum) {
> -               if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
> -                       /* conflicting/duplicate rules are ignored */
> -                       datum = NULL;
> -                       goto out;
> -               }
> -               if (likely(datum->otype == otype))
> -                       break;
> -               last = datum;
> -               datum = datum->next;
> -       }
> -       if (!datum) {
> -               rc = -ENOMEM;
> -               datum = kmalloc(sizeof(*datum), GFP_KERNEL);
> -               if (!datum)
> -                       goto out;
> -
> -               ebitmap_init(&datum->stypes);
> -               datum->otype = otype;
> -               datum->next = NULL;
> -
> -               if (unlikely(last)) {
> -                       last->next = datum;
> -               } else {
> -                       rc = -ENOMEM;
> -                       ft = kmemdup(&key, sizeof(key), GFP_KERNEL);
> -                       if (!ft)
> -                               goto out;
> -
> -                       rc = hashtab_insert(&p->filename_trans, ft, datum,
> -                                           filenametr_key_params);
> -                       if (rc)
> -                               goto out;
> -                       name = NULL;
> -
> -                       rc = ebitmap_set_bit(&p->filename_trans_ttypes,
> -                                            key.ttype, 1);
> -                       if (rc)
> -                               return rc;
> -               }
> -       }
> -       kfree(name);
> -       return ebitmap_set_bit(&datum->stypes, stype - 1, 1);
> -
> -out:
> -       kfree(ft);
> -       kfree(name);
> -       kfree(datum);
> -       return rc;
> -}
> -
> -static int filename_trans_read_helper(struct policydb *p, void *fp)
> -{
> -       struct filename_trans_key *ft = NULL;
> -       struct filename_trans_datum **dst, *datum, *first = NULL;
> -       char *name = NULL;
> -       u32 len, ttype, tclass, ndatum, i;
> -       __le32 buf[3];
> -       int rc;
> -
> -       /* length of the path component string */
> -       rc = next_entry(buf, fp, sizeof(u32));
> -       if (rc)
> -               return rc;
> -       len = le32_to_cpu(buf[0]);
> -
> -       /* path component string */
> -       rc = str_read(&name, GFP_KERNEL, fp, len);
> -       if (rc)
> -               return rc;
> -
> -       rc = next_entry(buf, fp, sizeof(u32) * 3);
> -       if (rc)
> -               goto out;
> -
> -       ttype = le32_to_cpu(buf[0]);
> -       tclass = le32_to_cpu(buf[1]);
> -
> -       ndatum = le32_to_cpu(buf[2]);
> -       if (ndatum == 0) {
> -               pr_err("SELinux:  Filename transition key with no datum\n");
> -               rc = -ENOENT;
> -               goto out;
> -       }
> -
> -       dst = &first;
> -       for (i = 0; i < ndatum; i++) {
> -               rc = -ENOMEM;
> -               datum = kmalloc(sizeof(*datum), GFP_KERNEL);
> -               if (!datum)
> -                       goto out;
> -
> -               *dst = datum;
> -
> -               /* ebitmap_read() will at least init the bitmap */
> -               rc = ebitmap_read(&datum->stypes, fp);
> -               if (rc)
> -                       goto out;
> -
> -               rc = next_entry(buf, fp, sizeof(u32));
> -               if (rc)
> -                       goto out;
> -
> -               datum->otype = le32_to_cpu(buf[0]);
> -               datum->next = NULL;
> -
> -               dst = &datum->next;
> -       }
> -
> -       rc = -ENOMEM;
> -       ft = kmalloc(sizeof(*ft), GFP_KERNEL);
> -       if (!ft)
> -               goto out;
> -
> -       ft->ttype = ttype;
> -       ft->tclass = tclass;
> -       ft->name = name;
> -
> -       rc = hashtab_insert(&p->filename_trans, ft, first,
> -                           filenametr_key_params);
> -       if (rc == -EEXIST)
> -               pr_err("SELinux:  Duplicate filename transition key\n");
> -       if (rc)
> -               goto out;
> -
> -       return ebitmap_set_bit(&p->filename_trans_ttypes, ttype, 1);
> -
> -out:
> -       kfree(ft);
> -       kfree(name);
> -       while (first) {
> -               datum = first;
> -               first = first->next;
> -
> -               ebitmap_destroy(&datum->stypes);
> -               kfree(datum);
> -       }
> -       return rc;
> -}
> -
> -static int filename_trans_read(struct policydb *p, void *fp)
> -{
> -       u32 nel;
> -       __le32 buf[1];
> -       int rc, i;
> -
> -       if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> -               return 0;
> -
> -       rc = next_entry(buf, fp, sizeof(u32));
> -       if (rc)
> -               return rc;
> -       nel = le32_to_cpu(buf[0]);
> -
> -       if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> -               p->compat_filename_trans_count = nel;
> -
> -               rc = hashtab_init(&p->filename_trans, (1 << 11));
> -               if (rc)
> -                       return rc;
> -
> -               for (i = 0; i < nel; i++) {
> -                       rc = filename_trans_read_helper_compat(p, fp);
> -                       if (rc)
> -                               return rc;
> -               }
> -       } else {
> -               rc = hashtab_init(&p->filename_trans, nel);
> -               if (rc)
> -                       return rc;
> -
> -               for (i = 0; i < nel; i++) {
> -                       rc = filename_trans_read_helper(p, fp);
> -                       if (rc)
> -                               return rc;
> -               }
> -       }
> -       hash_eval(&p->filename_trans, "filenametr");
> -       return 0;
> -}
> -
>  static int genfs_read(struct policydb *p, void *fp)
>  {
>         int i, j, rc;
> @@ -2634,7 +2354,7 @@ int policydb_read(struct policydb *p, void *fp)
>                 lra = ra;
>         }
>
> -       rc = filename_trans_read(p, fp);
> +       rc = avtab_filename_trans_read(&p->te_avtab, fp, p);
>         if (rc)
>                 goto bad;
>
> @@ -3480,119 +3200,6 @@ static int range_write(struct policydb *p, void *fp)
>         return 0;
>  }
>
> -static int filename_write_helper_compat(void *key, void *data, void *ptr)
> -{
> -       struct filename_trans_key *ft = key;
> -       struct filename_trans_datum *datum = data;
> -       struct ebitmap_node *node;
> -       void *fp = ptr;
> -       __le32 buf[4];
> -       int rc;
> -       u32 bit, len = strlen(ft->name);
> -
> -       do {
> -               ebitmap_for_each_positive_bit(&datum->stypes, node, bit) {
> -                       buf[0] = cpu_to_le32(len);
> -                       rc = put_entry(buf, sizeof(u32), 1, fp);
> -                       if (rc)
> -                               return rc;
> -
> -                       rc = put_entry(ft->name, sizeof(char), len, fp);
> -                       if (rc)
> -                               return rc;
> -
> -                       buf[0] = cpu_to_le32(bit + 1);
> -                       buf[1] = cpu_to_le32(ft->ttype);
> -                       buf[2] = cpu_to_le32(ft->tclass);
> -                       buf[3] = cpu_to_le32(datum->otype);
> -
> -                       rc = put_entry(buf, sizeof(u32), 4, fp);
> -                       if (rc)
> -                               return rc;
> -               }
> -
> -               datum = datum->next;
> -       } while (unlikely(datum));
> -
> -       return 0;
> -}
> -
> -static int filename_write_helper(void *key, void *data, void *ptr)
> -{
> -       struct filename_trans_key *ft = key;
> -       struct filename_trans_datum *datum;
> -       void *fp = ptr;
> -       __le32 buf[3];
> -       int rc;
> -       u32 ndatum, len = strlen(ft->name);
> -
> -       buf[0] = cpu_to_le32(len);
> -       rc = put_entry(buf, sizeof(u32), 1, fp);
> -       if (rc)
> -               return rc;
> -
> -       rc = put_entry(ft->name, sizeof(char), len, fp);
> -       if (rc)
> -               return rc;
> -
> -       ndatum = 0;
> -       datum = data;
> -       do {
> -               ndatum++;
> -               datum = datum->next;
> -       } while (unlikely(datum));
> -
> -       buf[0] = cpu_to_le32(ft->ttype);
> -       buf[1] = cpu_to_le32(ft->tclass);
> -       buf[2] = cpu_to_le32(ndatum);
> -       rc = put_entry(buf, sizeof(u32), 3, fp);
> -       if (rc)
> -               return rc;
> -
> -       datum = data;
> -       do {
> -               rc = ebitmap_write(&datum->stypes, fp);
> -               if (rc)
> -                       return rc;
> -
> -               buf[0] = cpu_to_le32(datum->otype);
> -               rc = put_entry(buf, sizeof(u32), 1, fp);
> -               if (rc)
> -                       return rc;
> -
> -               datum = datum->next;
> -       } while (unlikely(datum));
> -
> -       return 0;
> -}
> -
> -static int filename_trans_write(struct policydb *p, void *fp)
> -{
> -       __le32 buf[1];
> -       int rc;
> -
> -       if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> -               return 0;
> -
> -       if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> -               buf[0] = cpu_to_le32(p->compat_filename_trans_count);
> -               rc = put_entry(buf, sizeof(u32), 1, fp);
> -               if (rc)
> -                       return rc;
> -
> -               rc = hashtab_map(&p->filename_trans,
> -                                filename_write_helper_compat, fp);
> -       } else {
> -               buf[0] = cpu_to_le32(p->filename_trans.nel);
> -               rc = put_entry(buf, sizeof(u32), 1, fp);
> -               if (rc)
> -                       return rc;
> -
> -               rc = hashtab_map(&p->filename_trans, filename_write_helper, fp);
> -       }
> -       return rc;
> -}
> -
>  /*
>   * Write the configuration data in a policy database
>   * structure to a policy database binary representation
> @@ -3703,7 +3310,7 @@ int policydb_write(struct policydb *p, void *fp)
>         if (rc)
>                 return rc;
>
> -       rc = filename_trans_write(p, fp);
> +       rc = avtab_filename_trans_write(p, &p->te_avtab, fp);
>         if (rc)
>                 return rc;
>
> diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> index ffc4e7bad205..2ecb24a1611a 100644
> --- a/security/selinux/ss/policydb.h
> +++ b/security/selinux/ss/policydb.h
> @@ -91,18 +91,6 @@ struct role_trans_datum {
>         u32 new_role;           /* new role */
>  };
>
> -struct filename_trans_key {
> -       u32 ttype;              /* parent dir context */
> -       u16 tclass;             /* class of new object */
> -       const char *name;       /* last path component */
> -};
> -
> -struct filename_trans_datum {
> -       struct ebitmap stypes;  /* bitmap of source types for this otype */
> -       u32 otype;              /* resulting type of new object */
> -       struct filename_trans_datum *next;      /* record for next otype*/
> -};
> -
>  struct role_allow {
>         u32 role;               /* current role */
>         u32 new_role;           /* new role */
> @@ -265,14 +253,6 @@ struct policydb {
>         /* role transitions */
>         struct hashtab role_tr;
>
> -       /* file transitions with the last path component */
> -       /* quickly exclude lookups when parent ttype has no rules */
> -       struct ebitmap filename_trans_ttypes;
> -       /* actual set of filename_trans rules */
> -       struct hashtab filename_trans;
> -       /* only used if policyvers < POLICYDB_VERSION_COMP_FTRANS */
> -       u32 compat_filename_trans_count;
> -
>         /* bools indexed by (value - 1) */
>         struct cond_bool_datum **bool_val_to_struct;
>         /* type enforcement conditional access vectors and transitions */
> @@ -324,9 +304,6 @@ 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);
>
> -extern struct filename_trans_datum *policydb_filenametr_search(
> -       struct policydb *p, struct filename_trans_key *key);
> -
>  extern struct mls_range *policydb_rangetr_search(
>         struct policydb *p, struct range_trans *key);
>
> @@ -379,6 +356,8 @@ static inline int put_entry(const void *buf, size_t bytes, int num, struct polic
>         return 0;
>  }
>
> +extern int str_read(char **strp, gfp_t flags, void *fp, u32 len);
> +
>  static inline char *sym_name(struct policydb *p, unsigned int sym_num, unsigned int element_nr)
>  {
>         return p->sym_val_to_name[sym_num][element_nr];
> diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> index 8ed12406acba..131647e7ec68 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -1661,36 +1661,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_key ft;
> -       struct filename_trans_datum *datum;
> -
> -       /*
> -        * 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.ttype = ttype;
> -       ft.tclass = tclass;
> -       ft.name = objname;
> -
> -       datum = policydb_filenametr_search(policydb, &ft);
> -       while (datum) {
> -               if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
> -                       newcontext->type = datum->otype;
> -                       return;
> -               }
> -               datum = datum->next;
> -       }
> -}
> -
>  static int security_compute_sid(u32 ssid,
>                                 u32 tsid,
>                                 u16 orig_tclass,
> @@ -1711,6 +1681,7 @@ static int security_compute_sid(u32 ssid,
>         u16 tclass;
>         int rc = 0;
>         bool sock;
> +       u32 *otype;
>
>         if (!selinux_initialized()) {
>                 switch (orig_tclass) {
> @@ -1830,17 +1801,24 @@ static int security_compute_sid(u32 ssid,
>
>         if (avdatum) {
>                 /* Use the type from the type transition/member/change rule. */
> -               if (avkey.specified & AVTAB_TRANSITION)
> -                       newcontext.type = avdatum->u.trans->otype;
> -               else
> +               if (avkey.specified & AVTAB_TRANSITION) {
> +                       /*
> +                        * use default otype if not empty and then to try to
> +                        * find more specific rule using objname
> +                        */
> +                       if (avdatum->u.trans->otype)
> +                               newcontext.type = avdatum->u.trans->otype;
> +                       if (objname) {
> +                               otype = symtab_search(&avdatum->u.trans->name_trans,
> +                                                     objname);
> +                               if (otype)
> +                                       newcontext.type = *otype;
> +                       }
> +               } else {
>                         newcontext.type = avdatum->u.data;
> +               }
>         }
>
> -       /* 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);
> -
>         /* Check for class-specific changes. */
>         if (specified & AVTAB_TRANSITION) {
>                 /* Look for a role transition rule. */
> --
> 2.40.0
>

Re: [PATCH 2/5] selinux: move filename transitions to avtab

[Ondrej Mosnacek]

On Fri, Jun 2, 2023 at 3:13 PM Christian Göttsche
<cgzones@googlemail.com> wrote:
>
> On Wed, 31 May 2023 at 13:32, Juraj Marcin <juraj@jurajmarcin.com> wrote:
> >
> > Currently, filename transitions are stored separately from other type
> > enforcement rules. This leads to possibly sub-optimal performance and
> > makes further improvements cumbersome.
> >
> > This patch adds a symbol table of filename transitions to the transition
> > structure added to avtab in the previous patch. It also implements
> > functions required for reading and writing filename transitions in
> > kernel policy format and updates computation of new type to use filename
> > transitions embedded in avtab. Last but not least, it updates the
> > conflict check in the conditional avtab to account for empty transitions
> > in the non-conditional avtab.
> >
> > These changes are expected to cause higher memory usage, as now there
> > needs to be a filename transition structure for every stype. This patch
> > effectively undoes most of the commit c3a276111ea2 ("selinux: optimize
> > storage of filename transitions"), but this will be mitigated by
> > providing support for matching prefix/suffix of the filename for
> > filename transitions in future patches which will reduce to need to have
> > so many of them.
> >
> > On the other hand, the changes do not significantly slow down the
> > creation of new files.
> >
> > Kernel     | Mem   | Create test_tty | Create test_tty | osbench [1]
> >            | usage | (real time)     | (kernel time)   | create_files
> > -----------+-------+-----------------+-----------------+--------------
> > reference  | 155MB |  1.3440 ms/file |  1.0071 ms/file | 10.6507 us/file
> > this patch | 198MB |  1.3912 ms/file |  1.0172 ms/file | 10.5567 us/file
> >
> > Create test_tty benchmark:
> >
> >     mknod /dev/test_tty c 4 1
> >     time for i in `seq 1 10000`; do
> >         mknod /dev/test_tty$i c 4 1
> >     done
> >
> > This benchmark should simulate the worst case scenario as many filename
> > transitions affect files created in the /dev directory.
> >
> > [1] https://github.com/mbitsnbites/osbench
> >
> > Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
> > Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> > ---

<snip>

> > diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
> > index 6c8eb7c379cf..162ef1be85e7 100644
> > --- a/security/selinux/ss/avtab.h
> > +++ b/security/selinux/ss/avtab.h
> > @@ -22,6 +22,7 @@
> >  #define _SS_AVTAB_H_
> >
> >  #include "security.h"
> > +#include "symtab.h"
> >
> >  struct avtab_key {
> >         u16 source_type;        /* source type */
> > @@ -49,6 +50,7 @@ struct avtab_key {
> >
> >  struct avtab_trans {
> >         u32 otype;              /* default resulting type of the new object */
> > +       struct symtab name_trans;       /* filename transitions */
>
> What about using a bare hashtab to save the 4 bytes for the unused
> nprim member (+padding)?

That would mean losing the symtab_search()/symtab_insert() helpers
specialized for string keys. But it may be worth refactoring them down
into hashtab itself as an optimization.

> Also what about instead of storing an extra allocated u32 in the
> tables use the pointer itself as value?

That's possible, although quite hacky... But I guess if the casts are
hidden behind some helpers it could work... The same optimization
could be used for existing role_trans_datum.

<snip>

-- 
Ondrej Mosnacek
Senior Software Engineer, Linux Security - SELinux kernel
Red Hat, Inc.

Re: [PATCH 2/5] selinux: move filename transitions to avtab

[Juraj Marcin]

On 2023-06-02 15:13, Christian Göttsche wrote:
> On Wed, 31 May 2023 at 13:32, Juraj Marcin <juraj@jurajmarcin.com> wrote:
> >
> > Currently, filename transitions are stored separately from other type
> > enforcement rules. This leads to possibly sub-optimal performance and
> > makes further improvements cumbersome.
> >
> > This patch adds a symbol table of filename transitions to the transition
> > structure added to avtab in the previous patch. It also implements
> > functions required for reading and writing filename transitions in
> > kernel policy format and updates computation of new type to use filename
> > transitions embedded in avtab. Last but not least, it updates the
> > conflict check in the conditional avtab to account for empty transitions
> > in the non-conditional avtab.
> >
> > These changes are expected to cause higher memory usage, as now there
> > needs to be a filename transition structure for every stype. This patch
> > effectively undoes most of the commit c3a276111ea2 ("selinux: optimize
> > storage of filename transitions"), but this will be mitigated by
> > providing support for matching prefix/suffix of the filename for
> > filename transitions in future patches which will reduce to need to have
> > so many of them.
> >
> > On the other hand, the changes do not significantly slow down the
> > creation of new files.
> >
> > Kernel     | Mem   | Create test_tty | Create test_tty | osbench [1]
> >            | usage | (real time)     | (kernel time)   | create_files
> > -----------+-------+-----------------+-----------------+--------------
> > reference  | 155MB |  1.3440 ms/file |  1.0071 ms/file | 10.6507 us/file
> > this patch | 198MB |  1.3912 ms/file |  1.0172 ms/file | 10.5567 us/file
> >
> > Create test_tty benchmark:
> >
> >     mknod /dev/test_tty c 4 1
> >     time for i in `seq 1 10000`; do
> >         mknod /dev/test_tty$i c 4 1
> >     done
> >
> > This benchmark should simulate the worst case scenario as many filename
> > transitions affect files created in the /dev directory.
> >
> > [1] https://github.com/mbitsnbites/osbench
> >
> > Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
> > Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> > ---

<snip>

> > diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
> > index 6c8eb7c379cf..162ef1be85e7 100644
> > --- a/security/selinux/ss/avtab.h
> > +++ b/security/selinux/ss/avtab.h
> > @@ -22,6 +22,7 @@
> >  #define _SS_AVTAB_H_
> >
> >  #include "security.h"
> > +#include "symtab.h"
> >
> >  struct avtab_key {
> >         u16 source_type;        /* source type */
> > @@ -49,6 +50,7 @@ struct avtab_key {
> >
> >  struct avtab_trans {
> >         u32 otype;              /* default resulting type of the new object */
> > +       struct symtab name_trans;       /* filename transitions */
> 
> What about using a bare hashtab to save the 4 bytes for the unused
> nprim member (+padding)?
> 
> Also what about instead of storing an extra allocated u32 in the
> tables use the pointer itself as value?

Hi

I have implemented both optimizations to see the gain in performance and
memory usage, here are the results:


[1] Fedora policy (format v33)
[2] Fedora policy without prefix/suffix rules (format v35)
[3] Fedora policy with prefix rules (format v35)
before - before optimizations
opt1   - replace symtab with hashtab
opt2   - storing u32 value in the hashtab directly instead of a pointer

 Test || Mem usage            || Policy load time
      || (MiB)                || (ms)  
      || before | opt1 | opt2 || before | opt1 | opt2
------++--------+------+------++----------------------
 [1]  ||    202 |  198 |  199 ||    228 |  227 |  208
 [2]  ||    170 |  171 |  167 ||    120 |  114 |  107
 [3]  ||    164 |  161 |  161 ||     91 |  94  |   92

(Average values from 5 runs, measured 15 seconds after boot.)


As can be seen from the table, replacing the symtab with bare hashtab
does not seem to provide real world difference, but could be done easily
by adding helper functions to hashtab.c.

With Fedora policy, there were around 16.7k (combinations of src, tgt,
class) symtab tables, so replacing them with hashtab saves around 65 KiB
(+padding for each) in total.


However, even though storing the u32 value directly shows some small
difference in the loading time, I am not sure if it is worth it
considering the hacky nature of the optimization.

This optimization should in theory save around 900 KiB without prefix
rules [1][2] or 350 KiB with prefix rules [3] with Fedora policy.

> 
> >  };
> >
> >  /*

<snip>


-- 
Juraj Marcin

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Paul Moore]

On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> On 2023-05-31 18:24, Paul Moore wrote:
> > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > >
> > > Currently, filename transitions are stored separately from other type
> > > enforcement rules and only support exact name matching. However, in
> > > practice, the names contain variable parts. This leads to many
> > > duplicated rules in the policy that differ only in the part of the name,
> > > or it is even impossible to cover all possible combinations.
> > >
> > > First, this series of patches moves the filename transitions to be part
> > > of the avtab structures. This not only makes the implementation of
> > > prefix/suffix matching and future enhancements easier, but also reduces
> > > the technical debt regarding the filename transitions. Next, the last
> > > patch implements the support for prefix/suffix name matching itself by
> > > extending the structures added in previous patches in this series.
> > >
> > > Even though, moving everything to avtab increases the memory usage and
> > > the size of the binary policy itself and thus the loading time, the
> > > ability to match the prefix or suffix of the name will reduce the
> > > overall number of rules in the policy which should mitigate this issue.
> > >
> > > This implementation has been successfully tested using the existing and
> > > also new tests in the SELinux Testsuite.
> > >
> > > Juraj Marcin (5):
> > >   selinux: move transition to separate structure in avtab_datum
> > >   selinux: move filename transitions to avtab
> > >   selinux: implement new binary format for filename transitions in avtab
> > >   selinux: filename transitions move tests
> > >   selinux: add prefix/suffix matching support to filename type
> > >     transitions
> >
> > Just a quick comment as I haven't had a chance to properly review this
> > series yet; you show some memory usage and performance measurements in
> > some of the intermediate patches, that's good, but I don't see the
> > same measurements taken when the full patchset is applied.  Please
> > provide the same memory usage and performance comparisons with the
> > full patchset applied.
>
> Of course, here are the measurements with the whole patchset applied.
>
> I also included measurements with new policy (based on the Fedora
> policy) that uses prefix filename transitions where possible. This new
> policy has been generated by merging existing filename transitions into
> prefix ones if it would reduce the number of transitions overall while
> keeping the resulting type same.
>
> [1] Reference kernel (c52df19e3759), Fedora policy (format v33)
> [2] This patchset, Fedora policy (format v33)
> [3] This patchset, Fedora policy without prefix/suffix rules (format v35)
> [4] This patchset, Fedora policy with prefix rules (format v35)
>
>
>  Test | Mem   | Binary | Policy | Create tty      | osbench
>       | Usage | policy | load   |                 | create
>       |       | size   | time   | (ms/file)       | files
>       | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
> ------+-------+--------+--------+--------+--------+-----------
>  [1]  |   157 |    3.4 |     78 | 1.1021 | 0.7586 | 7.8277
>  [2]  |   200 |    3.4 |    206 | 1.1193 | 0.7724 | 8.2711
>  [3]  |   169 |    5.8 |    106 | 1.1021 | 0.7724 | 8.0304
>  [4]  |   164 |    3.8 |     86 | 1.1029 | 0.7586 | 7.9609

Thanks for performing those measurements.

I apologize that I haven't had an opportunity to review your patcheset
in detail just yet (I've been struggling with some self-inflicted
networking issues this week), but looking strictly at the numbers
above it appears that by every metric in the table this patchset
results in a policy that is larger (both on-disk and in-memory) as
well as performance that is at best the same (although in most cases,
it is worse).  Are there any improvements expected beyond test
configuration [4] (above)?

-- 
paul-moore.com

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Juraj Marcin]

On 2023-06-15 22:04, Paul Moore wrote:
> On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > On 2023-05-31 18:24, Paul Moore wrote:
> > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > >
> > > > Currently, filename transitions are stored separately from other type
> > > > enforcement rules and only support exact name matching. However, in
> > > > practice, the names contain variable parts. This leads to many
> > > > duplicated rules in the policy that differ only in the part of the name,
> > > > or it is even impossible to cover all possible combinations.
> > > >
> > > > First, this series of patches moves the filename transitions to be part
> > > > of the avtab structures. This not only makes the implementation of
> > > > prefix/suffix matching and future enhancements easier, but also reduces
> > > > the technical debt regarding the filename transitions. Next, the last
> > > > patch implements the support for prefix/suffix name matching itself by
> > > > extending the structures added in previous patches in this series.
> > > >
> > > > Even though, moving everything to avtab increases the memory usage and
> > > > the size of the binary policy itself and thus the loading time, the
> > > > ability to match the prefix or suffix of the name will reduce the
> > > > overall number of rules in the policy which should mitigate this issue.
> > > >
> > > > This implementation has been successfully tested using the existing and
> > > > also new tests in the SELinux Testsuite.
> > > >
> > > > Juraj Marcin (5):
> > > >   selinux: move transition to separate structure in avtab_datum
> > > >   selinux: move filename transitions to avtab
> > > >   selinux: implement new binary format for filename transitions in avtab
> > > >   selinux: filename transitions move tests
> > > >   selinux: add prefix/suffix matching support to filename type
> > > >     transitions
> > >
> > > Just a quick comment as I haven't had a chance to properly review this
> > > series yet; you show some memory usage and performance measurements in
> > > some of the intermediate patches, that's good, but I don't see the
> > > same measurements taken when the full patchset is applied.  Please
> > > provide the same memory usage and performance comparisons with the
> > > full patchset applied.
> >
> > Of course, here are the measurements with the whole patchset applied.
> >
> > I also included measurements with new policy (based on the Fedora
> > policy) that uses prefix filename transitions where possible. This new
> > policy has been generated by merging existing filename transitions into
> > prefix ones if it would reduce the number of transitions overall while
> > keeping the resulting type same.
> >
> > [1] Reference kernel (c52df19e3759), Fedora policy (format v33)
> > [2] This patchset, Fedora policy (format v33)
> > [3] This patchset, Fedora policy without prefix/suffix rules (format v35)
> > [4] This patchset, Fedora policy with prefix rules (format v35)
> >
> >
> >  Test | Mem   | Binary | Policy | Create tty      | osbench
> >       | Usage | policy | load   |                 | create
> >       |       | size   | time   | (ms/file)       | files
> >       | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
> > ------+-------+--------+--------+--------+--------+-----------
> >  [1]  |   157 |    3.4 |     78 | 1.1021 | 0.7586 | 7.8277
> >  [2]  |   200 |    3.4 |    206 | 1.1193 | 0.7724 | 8.2711
> >  [3]  |   169 |    5.8 |    106 | 1.1021 | 0.7724 | 8.0304
> >  [4]  |   164 |    3.8 |     86 | 1.1029 | 0.7586 | 7.9609
> 
> Thanks for performing those measurements.
> 
> I apologize that I haven't had an opportunity to review your patcheset
> in detail just yet (I've been struggling with some self-inflicted
> networking issues this week), but looking strictly at the numbers
> above it appears that by every metric in the table this patchset
> results in a policy that is larger (both on-disk and in-memory) as
> well as performance that is at best the same (although in most cases,
> it is worse).  Are there any improvements expected beyond test
> configuration [4] (above)?

The main goal of this patchset is to bring the possibility to use prefix
or suffix matching in filename transitions, as now it is not possible to
cover files that have fixed prefix and variable part after it. For
example devices in /dev (the policy now enumerates all possible number
suffixes) or files with random suffix/prefix (not possible at all).

The next goal is to make future improvements easier, for example
supporting filename transitions in conditional policies or inherent
support for type attributes.

As for performance, the goal is to implement previous goals while not
killing the performance by them. Christian suggested some possible
optimizations [1], but after trying them out [2] they either not provide
much measurable difference or the difference is small and the
implementation hacky.

[1]: https://lore.kernel.org/selinux/CAJ2a_DfHubNBa46kcGCsTfY2OmOCJkNMstFebERU3mXeEMajng@mail.gmail.com/
[2]: https://lore.kernel.org/selinux/20230608155951.osvhubn3zyqzx4ep@jmarcin-t14s-01/


-- 
Juraj Marcin


> 
> -- 
> paul-moore.com

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Paul Moore]

On Sun, Jun 18, 2023 at 5:41 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
>
> On 2023-06-15 22:04, Paul Moore wrote:
> > On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > On 2023-05-31 18:24, Paul Moore wrote:
> > > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > > >
> > > > > Currently, filename transitions are stored separately from other type
> > > > > enforcement rules and only support exact name matching. However, in
> > > > > practice, the names contain variable parts. This leads to many
> > > > > duplicated rules in the policy that differ only in the part of the name,
> > > > > or it is even impossible to cover all possible combinations.
> > > > >
> > > > > First, this series of patches moves the filename transitions to be part
> > > > > of the avtab structures. This not only makes the implementation of
> > > > > prefix/suffix matching and future enhancements easier, but also reduces
> > > > > the technical debt regarding the filename transitions. Next, the last
> > > > > patch implements the support for prefix/suffix name matching itself by
> > > > > extending the structures added in previous patches in this series.
> > > > >
> > > > > Even though, moving everything to avtab increases the memory usage and
> > > > > the size of the binary policy itself and thus the loading time, the
> > > > > ability to match the prefix or suffix of the name will reduce the
> > > > > overall number of rules in the policy which should mitigate this issue.
> > > > >
> > > > > This implementation has been successfully tested using the existing and
> > > > > also new tests in the SELinux Testsuite.
> > > > >
> > > > > Juraj Marcin (5):
> > > > >   selinux: move transition to separate structure in avtab_datum
> > > > >   selinux: move filename transitions to avtab
> > > > >   selinux: implement new binary format for filename transitions in avtab
> > > > >   selinux: filename transitions move tests
> > > > >   selinux: add prefix/suffix matching support to filename type
> > > > >     transitions
> > > >
> > > > Just a quick comment as I haven't had a chance to properly review this
> > > > series yet; you show some memory usage and performance measurements in
> > > > some of the intermediate patches, that's good, but I don't see the
> > > > same measurements taken when the full patchset is applied.  Please
> > > > provide the same memory usage and performance comparisons with the
> > > > full patchset applied.
> > >
> > > Of course, here are the measurements with the whole patchset applied.
> > >
> > > I also included measurements with new policy (based on the Fedora
> > > policy) that uses prefix filename transitions where possible. This new
> > > policy has been generated by merging existing filename transitions into
> > > prefix ones if it would reduce the number of transitions overall while
> > > keeping the resulting type same.
> > >
> > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33)
> > > [2] This patchset, Fedora policy (format v33)
> > > [3] This patchset, Fedora policy without prefix/suffix rules (format v35)
> > > [4] This patchset, Fedora policy with prefix rules (format v35)
> > >
> > >
> > >  Test | Mem   | Binary | Policy | Create tty      | osbench
> > >       | Usage | policy | load   |                 | create
> > >       |       | size   | time   | (ms/file)       | files
> > >       | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
> > > ------+-------+--------+--------+--------+--------+-----------
> > >  [1]  |   157 |    3.4 |     78 | 1.1021 | 0.7586 | 7.8277
> > >  [2]  |   200 |    3.4 |    206 | 1.1193 | 0.7724 | 8.2711
> > >  [3]  |   169 |    5.8 |    106 | 1.1021 | 0.7724 | 8.0304
> > >  [4]  |   164 |    3.8 |     86 | 1.1029 | 0.7586 | 7.9609
> >
> > Thanks for performing those measurements.
> >
> > I apologize that I haven't had an opportunity to review your patcheset
> > in detail just yet (I've been struggling with some self-inflicted
> > networking issues this week), but looking strictly at the numbers
> > above it appears that by every metric in the table this patchset
> > results in a policy that is larger (both on-disk and in-memory) as
> > well as performance that is at best the same (although in most cases,
> > it is worse).  Are there any improvements expected beyond test
> > configuration [4] (above)?
>
> The main goal of this patchset is to bring the possibility to use prefix
> or suffix matching in filename transitions, as now it is not possible to
> cover files that have fixed prefix and variable part after it. For
> example devices in /dev (the policy now enumerates all possible number
> suffixes) or files with random suffix/prefix (not possible at all).
>
> The next goal is to make future improvements easier, for example
> supporting filename transitions in conditional policies or inherent
> support for type attributes.
>
> As for performance, the goal is to implement previous goals while not
> killing the performance by them. Christian suggested some possible
> optimizations [1], but after trying them out [2] they either not provide
> much measurable difference or the difference is small and the
> implementation hacky.

I understand performance improvements were not the main motivation
behind this patchset, but I'm somewhat concerned that policy load time
*almost* triples in the case of an unmodified policy with this patch
applied.  Since that will be most everyone as soon as this patch is
applied, that regression does concern me ... I'm not sure just yet how
much it concerns me, but it isn't trivial.

-- 
paul-moore.com

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Juraj Marcin]

On 2023-06-19 17:53, Paul Moore wrote:
> On Sun, Jun 18, 2023 at 5:41 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> >
> > On 2023-06-15 22:04, Paul Moore wrote:
> > > On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > > On 2023-05-31 18:24, Paul Moore wrote:
> > > > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > > > >
> > > > > > Currently, filename transitions are stored separately from other type
> > > > > > enforcement rules and only support exact name matching. However, in
> > > > > > practice, the names contain variable parts. This leads to many
> > > > > > duplicated rules in the policy that differ only in the part of the name,
> > > > > > or it is even impossible to cover all possible combinations.
> > > > > >
> > > > > > First, this series of patches moves the filename transitions to be part
> > > > > > of the avtab structures. This not only makes the implementation of
> > > > > > prefix/suffix matching and future enhancements easier, but also reduces
> > > > > > the technical debt regarding the filename transitions. Next, the last
> > > > > > patch implements the support for prefix/suffix name matching itself by
> > > > > > extending the structures added in previous patches in this series.
> > > > > >
> > > > > > Even though, moving everything to avtab increases the memory usage and
> > > > > > the size of the binary policy itself and thus the loading time, the
> > > > > > ability to match the prefix or suffix of the name will reduce the
> > > > > > overall number of rules in the policy which should mitigate this issue.
> > > > > >
> > > > > > This implementation has been successfully tested using the existing and
> > > > > > also new tests in the SELinux Testsuite.
> > > > > >
> > > > > > Juraj Marcin (5):
> > > > > >   selinux: move transition to separate structure in avtab_datum
> > > > > >   selinux: move filename transitions to avtab
> > > > > >   selinux: implement new binary format for filename transitions in avtab
> > > > > >   selinux: filename transitions move tests
> > > > > >   selinux: add prefix/suffix matching support to filename type
> > > > > >     transitions
> > > > >
> > > > > Just a quick comment as I haven't had a chance to properly review this
> > > > > series yet; you show some memory usage and performance measurements in
> > > > > some of the intermediate patches, that's good, but I don't see the
> > > > > same measurements taken when the full patchset is applied.  Please
> > > > > provide the same memory usage and performance comparisons with the
> > > > > full patchset applied.
> > > >
> > > > Of course, here are the measurements with the whole patchset applied.
> > > >
> > > > I also included measurements with new policy (based on the Fedora
> > > > policy) that uses prefix filename transitions where possible. This new
> > > > policy has been generated by merging existing filename transitions into
> > > > prefix ones if it would reduce the number of transitions overall while
> > > > keeping the resulting type same.
> > > >
> > > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33)
> > > > [2] This patchset, Fedora policy (format v33)
> > > > [3] This patchset, Fedora policy without prefix/suffix rules (format v35)
> > > > [4] This patchset, Fedora policy with prefix rules (format v35)
> > > >
> > > >
> > > >  Test | Mem   | Binary | Policy | Create tty      | osbench
> > > >       | Usage | policy | load   |                 | create
> > > >       |       | size   | time   | (ms/file)       | files
> > > >       | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
> > > > ------+-------+--------+--------+--------+--------+-----------
> > > >  [1]  |   157 |    3.4 |     78 | 1.1021 | 0.7586 | 7.8277
> > > >  [2]  |   200 |    3.4 |    206 | 1.1193 | 0.7724 | 8.2711
> > > >  [3]  |   169 |    5.8 |    106 | 1.1021 | 0.7724 | 8.0304
> > > >  [4]  |   164 |    3.8 |     86 | 1.1029 | 0.7586 | 7.9609
> > >
> > > Thanks for performing those measurements.
> > >
> > > I apologize that I haven't had an opportunity to review your patcheset
> > > in detail just yet (I've been struggling with some self-inflicted
> > > networking issues this week), but looking strictly at the numbers
> > > above it appears that by every metric in the table this patchset
> > > results in a policy that is larger (both on-disk and in-memory) as
> > > well as performance that is at best the same (although in most cases,
> > > it is worse).  Are there any improvements expected beyond test
> > > configuration [4] (above)?
> >
> > The main goal of this patchset is to bring the possibility to use prefix
> > or suffix matching in filename transitions, as now it is not possible to
> > cover files that have fixed prefix and variable part after it. For
> > example devices in /dev (the policy now enumerates all possible number
> > suffixes) or files with random suffix/prefix (not possible at all).
> >
> > The next goal is to make future improvements easier, for example
> > supporting filename transitions in conditional policies or inherent
> > support for type attributes.
> >
> > As for performance, the goal is to implement previous goals while not
> > killing the performance by them. Christian suggested some possible
> > optimizations [1], but after trying them out [2] they either not provide
> > much measurable difference or the difference is small and the
> > implementation hacky.
> 
> I understand performance improvements were not the main motivation
> behind this patchset, but I'm somewhat concerned that policy load time
> *almost* triples in the case of an unmodified policy with this patch
> applied.  Since that will be most everyone as soon as this patch is
> applied, that regression does concern me ... I'm not sure just yet how
> much it concerns me, but it isn't trivial.

I also understand your concern. That higher load time (and also memory
usage) is the cost of doing the conversion from the older binary policy
format in the kernel during load.

However, to reduce both load time and memory usage to the values in the
third test, the only action needed is recompiling the policy with newer
checkpolicy/libsepol, patches to which I also proposed.

-- 
Juraj Marcin

Re: [PATCH 5/5] selinux: add prefix/suffix matching support to filename type transitions

[Stephen Smalley]

On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
>
> Currently, filename type transitions support only exact name matching.
> However, in practice, the names contain variable parts. This leads to
> many duplicated rules in the policy that differ only in the part of the
> name, or it is even impossible to cover all possible combinations.
>
> This patch extends the filename type transitions structures to include
> new types of filename transitions - prefix and suffix filename
> transitions. It also implements the reading and writing of those rules
> in the kernel binary policy format together with increasing its version.
> Last, it updates the function responsible for determining the new
> context to also include the prefix and suffix filename transitions in
> the process. It does that by first checking for the exact match, then
> the longest matching prefix and then the longest matching suffix, in
> that order. That way the exact match rules have precedence before new
> rules, to ensure compatibility with older policies.
>
> Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
> Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> ---
>  security/selinux/include/security.h |  3 +-
>  security/selinux/ss/avtab.c         | 53 +++++++++++++++++++--
>  security/selinux/ss/avtab.h         |  2 +
>  security/selinux/ss/avtab_test.c    | 16 +++++++
>  security/selinux/ss/policydb.c      |  5 ++
>  security/selinux/ss/services.c      | 71 ++++++++++++++++++++++++-----
>  6 files changed, 133 insertions(+), 17 deletions(-)
>

> diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> index 131647e7ec68..2faf92bf12da 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -1661,6 +1661,60 @@ static int compute_sid_handle_invalid_context(
>         return -EACCES;
>  }
>
> +static int security_compute_type_trans_otype(struct avtab_trans *trans,
> +                                            const char *name, u32 *res_type)
> +{
> +       u32 *otype;
> +       size_t len;
> +       char *namedup = NULL;
> +       size_t i;
> +
> +       /*
> +        * use default otype if not empty and then try to find more specific
> +        * rule using name
> +        */
> +       if (trans->otype)
> +               *res_type = trans->otype;
> +       if (!name)
> +               return 0;
> +
> +       /* try to find full name */
> +       otype = symtab_search(&trans->name_trans, name);
> +       if (otype) {
> +               *res_type = *otype;
> +               return 0;
> +       }
> +
> +       /* copy name for shortening */
> +       len = strlen(name);
> +       namedup = kmemdup(name, len + 1, GFP_KERNEL);

This is called in various contexts that cannot sleep; hence, the
allocation must be GFP_ATOMIC here. With the proper config options
(CONFIG_DEBUG_ATOMIC_SLEEP=y) you would have seen repeated warnings
about this in the kernel messages, ala:

[  219.944942] BUG: sleeping function called from invalid context at
include/linux/sched/mm.h:306
[  219.944951] in_atomic(): 0, irqs_disabled(): 0, non_block: 0, pid:
1, name: systemd
[  219.944956] preempt_count: 0, expected: 0
[  219.944959] RCU nest depth: 1, expected: 0
[  219.944963] INFO: lockdep is turned off.
[  219.944967] CPU: 0 PID: 1 Comm: systemd Tainted: G    B   W
 6.5.0-rc1+ #32
[  219.944979] Call Trace:
[  219.944982]  <TASK>
[  219.944986]  dump_stack_lvl+0x75/0x90
[  219.944997]  __might_resched+0x1e1/0x310
[  219.945008]  ? security_compute_sid.part.0+0x9d8/0xe50
[  219.945017]  __kmem_cache_alloc_node+0x343/0x380
[  219.945026]  ? security_compute_sid.part.0+0x9d8/0xe50
[  219.945033]  ? rcu_is_watching+0x23/0x50
[  219.945046]  ? security_compute_sid.part.0+0x9d8/0xe50
[  219.945054]  __kmalloc_node_track_caller+0x52/0x160
[  219.945068]  kmemdup+0x22/0x50
[  219.945078]  security_compute_sid.part.0+0x9d8/0xe50
[  219.945093]  ? __pfx_security_compute_sid.part.0+0x10/0x10
[  219.945101]  ? rcu_is_watching+0x23/0x50
[  219.945110]  ? lock_release+0xa0/0x380
[  219.945116]  ? avc_has_perm_noaudit+0xb4/0x250
[  219.945127]  ? __pfx_lock_release+0x10/0x10
[  219.945134]  ? rcu_is_watching+0x23/0x50
[  219.945143]  ? lock_acquire+0xb5/0x390
[  219.945148]  ? __filename_parentat+0x282/0x350
[  219.945160]  ? avc_has_perm_noaudit+0xcc/0x250
[  219.945178]  security_transition_sid+0x63/0xa0
[  219.945191]  may_create+0x16a/0x1c0
[  219.945201]  ? __pfx_may_create+0x10/0x10
[  219.945207]  ? selinux_inode_permission+0x1c6/0x290
[  219.945216]  ? __pfx_selinux_inode_permission+0x10/0x10
[  219.945226]  ? kernfs_iop_permission+0x84/0xa0
[  219.945238]  security_inode_mkdir+0x61/0x80
[  219.945251]  vfs_mkdir+0x226/0x380
[  219.945262]  do_mkdirat+0x1a8/0x1d0
[  219.945272]  ? __pfx_do_mkdirat+0x10/0x10
[  219.945280]  ? getname_flags.part.0+0xc6/0x250
[  219.945290]  __x64_sys_mkdir+0x78/0xa0
[  219.945300]  do_syscall_64+0x3c/0x90
[  219.945308]  entry_SYSCALL_64_after_hwframe+0x6e/0xd8
[  219.945317] RIP: 0033:0x7ff080322d6b
[  219.945337] Code: 8b 05 a1 30 0d 00 bb ff ff ff ff 64 c7 00 16 00
00 00 e9 62 ff ff ff e8 e3 1b 02 00 0f 1f 00 f3 0f 1e fa b8 53 00 00
00 0f 05 <48> 3d 00 f0 ff ff 77 05 c3 0f 1f 40 00 48 8b 15 69 30 0d 00
f7 d8
[  219.945343] RSP: 002b:00007ffe3fbd6cd8 EFLAGS: 00000246 ORIG_RAX:
0000000000000053
[  219.945350] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007ff080322d6b
[  219.945355] RDX: 0000000000000000 RSI: 00000000000001ed RDI: 000055a4731c2a10
[  219.945360] RBP: 00007ffe3fbd6d10 R08: 00000000ffffff9c R09: 00007ffe3fbd6b60
[  219.945364] R10: 0000000000000000 R11: 0000000000000246 R12: 00007ff0806af143
[  219.945368] R13: 000055a47311ce20 R14: 0000000000000001 R15: 00000000000003a0
[  219.945382]  </TASK>

> +       if (!namedup)
> +               return -ENOMEM;
> +
> +       /* try to find possible prefixes of name starting from the longest */
> +       for (i = len; i > 0; i--) {
> +               namedup[i] = '\0';
> +               otype = symtab_search(&trans->prefix_trans, namedup);
> +               if (otype) {
> +                       kfree(namedup);
> +                       *res_type = *otype;
> +                       return 0;
> +               }
> +       }
> +       kfree(namedup);
> +
> +       /*try to find possible suffixes of name starting from the longest */
> +       for (i = 0; i < len; i++) {
> +               otype = symtab_search(&trans->suffix_trans, &name[i]);
> +               if (otype) {
> +                       *res_type = *otype;
> +                       return 0;
> +               }
> +       }
> +
> +       return 0;
> +}
> +
>  static int security_compute_sid(u32 ssid,
>                                 u32 tsid,
>                                 u16 orig_tclass,
> @@ -1802,18 +1856,11 @@ static int security_compute_sid(u32 ssid,
>         if (avdatum) {
>                 /* Use the type from the type transition/member/change rule. */
>                 if (avkey.specified & AVTAB_TRANSITION) {
> -                       /*
> -                        * use default otype if not empty and then to try to
> -                        * find more specific rule using objname
> -                        */
> -                       if (avdatum->u.trans->otype)
> -                               newcontext.type = avdatum->u.trans->otype;
> -                       if (objname) {
> -                               otype = symtab_search(&avdatum->u.trans->name_trans,
> -                                                     objname);
> -                               if (otype)
> -                                       newcontext.type = *otype;
> -                       }
> +                       rc = security_compute_type_trans_otype(avdatum->u.trans,
> +                                                              objname,
> +                                                              &newcontext.type);
> +                       if (rc)
> +                               goto out_unlock;
>                 } else {
>                         newcontext.type = avdatum->u.data;
>                 }
> --
> 2.40.0
>

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Stephen Smalley]

On Tue, Jun 20, 2023 at 3:51 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
>
> On 2023-06-19 17:53, Paul Moore wrote:
> > On Sun, Jun 18, 2023 at 5:41 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > >
> > > On 2023-06-15 22:04, Paul Moore wrote:
> > > > On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > > > On 2023-05-31 18:24, Paul Moore wrote:
> > > > > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > > > > >
> > > > > > > Currently, filename transitions are stored separately from other type
> > > > > > > enforcement rules and only support exact name matching. However, in
> > > > > > > practice, the names contain variable parts. This leads to many
> > > > > > > duplicated rules in the policy that differ only in the part of the name,
> > > > > > > or it is even impossible to cover all possible combinations.
> > > > > > >
> > > > > > > First, this series of patches moves the filename transitions to be part
> > > > > > > of the avtab structures. This not only makes the implementation of
> > > > > > > prefix/suffix matching and future enhancements easier, but also reduces
> > > > > > > the technical debt regarding the filename transitions. Next, the last
> > > > > > > patch implements the support for prefix/suffix name matching itself by
> > > > > > > extending the structures added in previous patches in this series.
> > > > > > >
> > > > > > > Even though, moving everything to avtab increases the memory usage and
> > > > > > > the size of the binary policy itself and thus the loading time, the
> > > > > > > ability to match the prefix or suffix of the name will reduce the
> > > > > > > overall number of rules in the policy which should mitigate this issue.
> > > > > > >
> > > > > > > This implementation has been successfully tested using the existing and
> > > > > > > also new tests in the SELinux Testsuite.
> > > > > > >
> > > > > > > Juraj Marcin (5):
> > > > > > >   selinux: move transition to separate structure in avtab_datum
> > > > > > >   selinux: move filename transitions to avtab
> > > > > > >   selinux: implement new binary format for filename transitions in avtab
> > > > > > >   selinux: filename transitions move tests
> > > > > > >   selinux: add prefix/suffix matching support to filename type
> > > > > > >     transitions
> > > > > >
> > > > > > Just a quick comment as I haven't had a chance to properly review this
> > > > > > series yet; you show some memory usage and performance measurements in
> > > > > > some of the intermediate patches, that's good, but I don't see the
> > > > > > same measurements taken when the full patchset is applied.  Please
> > > > > > provide the same memory usage and performance comparisons with the
> > > > > > full patchset applied.
> > > > >
> > > > > Of course, here are the measurements with the whole patchset applied.
> > > > >
> > > > > I also included measurements with new policy (based on the Fedora
> > > > > policy) that uses prefix filename transitions where possible. This new
> > > > > policy has been generated by merging existing filename transitions into
> > > > > prefix ones if it would reduce the number of transitions overall while
> > > > > keeping the resulting type same.
> > > > >
> > > > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33)
> > > > > [2] This patchset, Fedora policy (format v33)
> > > > > [3] This patchset, Fedora policy without prefix/suffix rules (format v35)
> > > > > [4] This patchset, Fedora policy with prefix rules (format v35)
> > > > >
> > > > >
> > > > >  Test | Mem   | Binary | Policy | Create tty      | osbench
> > > > >       | Usage | policy | load   |                 | create
> > > > >       |       | size   | time   | (ms/file)       | files
> > > > >       | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
> > > > > ------+-------+--------+--------+--------+--------+-----------
> > > > >  [1]  |   157 |    3.4 |     78 | 1.1021 | 0.7586 | 7.8277
> > > > >  [2]  |   200 |    3.4 |    206 | 1.1193 | 0.7724 | 8.2711
> > > > >  [3]  |   169 |    5.8 |    106 | 1.1021 | 0.7724 | 8.0304
> > > > >  [4]  |   164 |    3.8 |     86 | 1.1029 | 0.7586 | 7.9609
> > > >
> > > > Thanks for performing those measurements.
> > > >
> > > > I apologize that I haven't had an opportunity to review your patcheset
> > > > in detail just yet (I've been struggling with some self-inflicted
> > > > networking issues this week), but looking strictly at the numbers
> > > > above it appears that by every metric in the table this patchset
> > > > results in a policy that is larger (both on-disk and in-memory) as
> > > > well as performance that is at best the same (although in most cases,
> > > > it is worse).  Are there any improvements expected beyond test
> > > > configuration [4] (above)?
> > >
> > > The main goal of this patchset is to bring the possibility to use prefix
> > > or suffix matching in filename transitions, as now it is not possible to
> > > cover files that have fixed prefix and variable part after it. For
> > > example devices in /dev (the policy now enumerates all possible number
> > > suffixes) or files with random suffix/prefix (not possible at all).
> > >
> > > The next goal is to make future improvements easier, for example
> > > supporting filename transitions in conditional policies or inherent
> > > support for type attributes.
> > >
> > > As for performance, the goal is to implement previous goals while not
> > > killing the performance by them. Christian suggested some possible
> > > optimizations [1], but after trying them out [2] they either not provide
> > > much measurable difference or the difference is small and the
> > > implementation hacky.
> >
> > I understand performance improvements were not the main motivation
> > behind this patchset, but I'm somewhat concerned that policy load time
> > *almost* triples in the case of an unmodified policy with this patch
> > applied.  Since that will be most everyone as soon as this patch is
> > applied, that regression does concern me ... I'm not sure just yet how
> > much it concerns me, but it isn't trivial.
>
> I also understand your concern. That higher load time (and also memory
> usage) is the cost of doing the conversion from the older binary policy
> format in the kernel during load.
>
> However, to reduce both load time and memory usage to the values in the
> third test, the only action needed is recompiling the policy with newer
> checkpolicy/libsepol, patches to which I also proposed.

I'm also struggling a bit with the justification here. If the runtime
and memory usage is worse or no better in every dimension even with a
policy rewritten to use the new prefix/suffix matching feature, it
seems hard to justify the change.

I'd be curious to see what results you would get if you simply added
the new feature (prefix/suffix matching) without moving the name-based
transitions into the avtab.

Also wondering whether you considered the simpler approach of just
augmenting the kernel to recognize and support use of wildcards at the
beginning and/or end of the existing name field to signify a prefix or
suffix match. That seems more amenable to extensions beyond just
prefix or suffix match.

Re: [PATCH 5/5] selinux: add prefix/suffix matching support to filename type transitions

[Stephen Smalley]

On Mon, Jul 17, 2023 at 2:33 PM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> >
> > Currently, filename type transitions support only exact name matching.
> > However, in practice, the names contain variable parts. This leads to
> > many duplicated rules in the policy that differ only in the part of the
> > name, or it is even impossible to cover all possible combinations.
> >
> > This patch extends the filename type transitions structures to include
> > new types of filename transitions - prefix and suffix filename
> > transitions. It also implements the reading and writing of those rules
> > in the kernel binary policy format together with increasing its version.
> > Last, it updates the function responsible for determining the new
> > context to also include the prefix and suffix filename transitions in
> > the process. It does that by first checking for the exact match, then
> > the longest matching prefix and then the longest matching suffix, in
> > that order. That way the exact match rules have precedence before new
> > rules, to ensure compatibility with older policies.
> >
> > Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
> > Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> > ---
> >  security/selinux/include/security.h |  3 +-
> >  security/selinux/ss/avtab.c         | 53 +++++++++++++++++++--
> >  security/selinux/ss/avtab.h         |  2 +
> >  security/selinux/ss/avtab_test.c    | 16 +++++++
> >  security/selinux/ss/policydb.c      |  5 ++
> >  security/selinux/ss/services.c      | 71 ++++++++++++++++++++++++-----
> >  6 files changed, 133 insertions(+), 17 deletions(-)
> >
>
> > diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> > index 131647e7ec68..2faf92bf12da 100644
> > --- a/security/selinux/ss/services.c
> > +++ b/security/selinux/ss/services.c
> > @@ -1661,6 +1661,60 @@ static int compute_sid_handle_invalid_context(
> >         return -EACCES;
> >  }
> >
> > +static int security_compute_type_trans_otype(struct avtab_trans *trans,
> > +                                            const char *name, u32 *res_type)
> > +{
> > +       u32 *otype;
> > +       size_t len;
> > +       char *namedup = NULL;
> > +       size_t i;
> > +
> > +       /*
> > +        * use default otype if not empty and then try to find more specific
> > +        * rule using name
> > +        */
> > +       if (trans->otype)
> > +               *res_type = trans->otype;
> > +       if (!name)
> > +               return 0;
> > +
> > +       /* try to find full name */
> > +       otype = symtab_search(&trans->name_trans, name);
> > +       if (otype) {
> > +               *res_type = *otype;
> > +               return 0;
> > +       }
> > +
> > +       /* copy name for shortening */
> > +       len = strlen(name);
> > +       namedup = kmemdup(name, len + 1, GFP_KERNEL);
>
> This is called in various contexts that cannot sleep; hence, the
> allocation must be GFP_ATOMIC here. With the proper config options
> (CONFIG_DEBUG_ATOMIC_SLEEP=y) you would have seen repeated warnings
> about this in the kernel messages, ala:
>
> [  219.944942] BUG: sleeping function called from invalid context at
> include/linux/sched/mm.h:306
> [  219.944951] in_atomic(): 0, irqs_disabled(): 0, non_block: 0, pid:
> 1, name: systemd
> [  219.944956] preempt_count: 0, expected: 0
> [  219.944959] RCU nest depth: 1, expected: 0
> [  219.944963] INFO: lockdep is turned off.
> [  219.944967] CPU: 0 PID: 1 Comm: systemd Tainted: G    B   W
>  6.5.0-rc1+ #32
> [  219.944979] Call Trace:
> [  219.944982]  <TASK>
> [  219.944986]  dump_stack_lvl+0x75/0x90
> [  219.944997]  __might_resched+0x1e1/0x310
> [  219.945008]  ? security_compute_sid.part.0+0x9d8/0xe50
> [  219.945017]  __kmem_cache_alloc_node+0x343/0x380
> [  219.945026]  ? security_compute_sid.part.0+0x9d8/0xe50
> [  219.945033]  ? rcu_is_watching+0x23/0x50
> [  219.945046]  ? security_compute_sid.part.0+0x9d8/0xe50
> [  219.945054]  __kmalloc_node_track_caller+0x52/0x160
> [  219.945068]  kmemdup+0x22/0x50
> [  219.945078]  security_compute_sid.part.0+0x9d8/0xe50
> [  219.945093]  ? __pfx_security_compute_sid.part.0+0x10/0x10
> [  219.945101]  ? rcu_is_watching+0x23/0x50
> [  219.945110]  ? lock_release+0xa0/0x380
> [  219.945116]  ? avc_has_perm_noaudit+0xb4/0x250
> [  219.945127]  ? __pfx_lock_release+0x10/0x10
> [  219.945134]  ? rcu_is_watching+0x23/0x50
> [  219.945143]  ? lock_acquire+0xb5/0x390
> [  219.945148]  ? __filename_parentat+0x282/0x350
> [  219.945160]  ? avc_has_perm_noaudit+0xcc/0x250
> [  219.945178]  security_transition_sid+0x63/0xa0
> [  219.945191]  may_create+0x16a/0x1c0
> [  219.945201]  ? __pfx_may_create+0x10/0x10
> [  219.945207]  ? selinux_inode_permission+0x1c6/0x290
> [  219.945216]  ? __pfx_selinux_inode_permission+0x10/0x10
> [  219.945226]  ? kernfs_iop_permission+0x84/0xa0
> [  219.945238]  security_inode_mkdir+0x61/0x80
> [  219.945251]  vfs_mkdir+0x226/0x380
> [  219.945262]  do_mkdirat+0x1a8/0x1d0
> [  219.945272]  ? __pfx_do_mkdirat+0x10/0x10
> [  219.945280]  ? getname_flags.part.0+0xc6/0x250
> [  219.945290]  __x64_sys_mkdir+0x78/0xa0
> [  219.945300]  do_syscall_64+0x3c/0x90
> [  219.945308]  entry_SYSCALL_64_after_hwframe+0x6e/0xd8
> [  219.945317] RIP: 0033:0x7ff080322d6b
> [  219.945337] Code: 8b 05 a1 30 0d 00 bb ff ff ff ff 64 c7 00 16 00
> 00 00 e9 62 ff ff ff e8 e3 1b 02 00 0f 1f 00 f3 0f 1e fa b8 53 00 00
> 00 0f 05 <48> 3d 00 f0 ff ff 77 05 c3 0f 1f 40 00 48 8b 15 69 30 0d 00
> f7 d8
> [  219.945343] RSP: 002b:00007ffe3fbd6cd8 EFLAGS: 00000246 ORIG_RAX:
> 0000000000000053
> [  219.945350] RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007ff080322d6b
> [  219.945355] RDX: 0000000000000000 RSI: 00000000000001ed RDI: 000055a4731c2a10
> [  219.945360] RBP: 00007ffe3fbd6d10 R08: 00000000ffffff9c R09: 00007ffe3fbd6b60
> [  219.945364] R10: 0000000000000000 R11: 0000000000000246 R12: 00007ff0806af143
> [  219.945368] R13: 000055a47311ce20 R14: 0000000000000001 R15: 00000000000003a0
> [  219.945382]  </TASK>

Also recommend enabling CONFIG_DEBUG_KMEMLEAK and
CONFIG_DEBUG_KMEMLEAK_AUTO_SCAN - seeing kernel: kmemleak: 2634 new
suspected memory leaks (see /sys/kernel/debug/kmemleak) in kernel
messages and a lot of these warnings in /sys/kernel/debug/kmemleak:

unreferenced object 0xffff8881b05d6ea8 (size 8):
  comm "systemd", pid 1, jiffies 4294785029 (age 2050.052s)
  hex dump (first 8 bytes):
    6d 64 33 00 cc cc cc cc                          md3.....
  backtrace:
    [<ffffffff9f54d692>] __kmalloc_node_track_caller+0x52/0x160
    [<ffffffff9f5388d2>] kmemdup+0x22/0x50
    [<ffffffff9fac9702>] filenametr_tab_insert+0x332/0x650
    [<ffffffff9fac5634>] hashtab_map+0x84/0xc0
    [<ffffffff9fac8adb>] avtab_filename_trans_write+0x2fb/0x3a0
    [<ffffffff9fad3838>] policydb_write+0x508/0x1220
    [<ffffffff9fae0a10>] security_read_state_kernel+0xe0/0x1c0
    [<ffffffff9fae7343>] selinux_ima_measure_state_locked+0x643/0x7b0
    [<ffffffff9fadad35>] selinux_policy_commit+0x315/0x470
    [<ffffffff9fac125d>] sel_write_load+0xd6d/0xfa0
    [<ffffffff9f69560e>] vfs_write+0x18e/0x720
    [<ffffffff9f6960e7>] ksys_write+0xb7/0x140
    [<ffffffffa07dc29c>] do_syscall_64+0x3c/0x90
    [<ffffffffa0a000aa>] entry_SYSCALL_64_after_hwframe+0x6e/0xd8

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Juraj Marcin]

On 2023-07-17 14:44, Stephen Smalley wrote:
> On Tue, Jun 20, 2023 at 3:51 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> >
> > On 2023-06-19 17:53, Paul Moore wrote:
> > > On Sun, Jun 18, 2023 at 5:41 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > >
> > > > On 2023-06-15 22:04, Paul Moore wrote:
> > > > > On Thu, Jun 1, 2023 at 1:03 PM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > > > > On 2023-05-31 18:24, Paul Moore wrote:
> > > > > > > On Wed, May 31, 2023 at 7:32 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > > > > > > >
> > > > > > > > Currently, filename transitions are stored separately from other type
> > > > > > > > enforcement rules and only support exact name matching. However, in
> > > > > > > > practice, the names contain variable parts. This leads to many
> > > > > > > > duplicated rules in the policy that differ only in the part of the name,
> > > > > > > > or it is even impossible to cover all possible combinations.
> > > > > > > >
> > > > > > > > First, this series of patches moves the filename transitions to be part
> > > > > > > > of the avtab structures. This not only makes the implementation of
> > > > > > > > prefix/suffix matching and future enhancements easier, but also reduces
> > > > > > > > the technical debt regarding the filename transitions. Next, the last
> > > > > > > > patch implements the support for prefix/suffix name matching itself by
> > > > > > > > extending the structures added in previous patches in this series.
> > > > > > > >
> > > > > > > > Even though, moving everything to avtab increases the memory usage and
> > > > > > > > the size of the binary policy itself and thus the loading time, the
> > > > > > > > ability to match the prefix or suffix of the name will reduce the
> > > > > > > > overall number of rules in the policy which should mitigate this issue.
> > > > > > > >
> > > > > > > > This implementation has been successfully tested using the existing and
> > > > > > > > also new tests in the SELinux Testsuite.
> > > > > > > >
> > > > > > > > Juraj Marcin (5):
> > > > > > > >   selinux: move transition to separate structure in avtab_datum
> > > > > > > >   selinux: move filename transitions to avtab
> > > > > > > >   selinux: implement new binary format for filename transitions in avtab
> > > > > > > >   selinux: filename transitions move tests
> > > > > > > >   selinux: add prefix/suffix matching support to filename type
> > > > > > > >     transitions
> > > > > > >
> > > > > > > Just a quick comment as I haven't had a chance to properly review this
> > > > > > > series yet; you show some memory usage and performance measurements in
> > > > > > > some of the intermediate patches, that's good, but I don't see the
> > > > > > > same measurements taken when the full patchset is applied.  Please
> > > > > > > provide the same memory usage and performance comparisons with the
> > > > > > > full patchset applied.
> > > > > >
> > > > > > Of course, here are the measurements with the whole patchset applied.
> > > > > >
> > > > > > I also included measurements with new policy (based on the Fedora
> > > > > > policy) that uses prefix filename transitions where possible. This new
> > > > > > policy has been generated by merging existing filename transitions into
> > > > > > prefix ones if it would reduce the number of transitions overall while
> > > > > > keeping the resulting type same.
> > > > > >
> > > > > > [1] Reference kernel (c52df19e3759), Fedora policy (format v33)
> > > > > > [2] This patchset, Fedora policy (format v33)
> > > > > > [3] This patchset, Fedora policy without prefix/suffix rules (format v35)
> > > > > > [4] This patchset, Fedora policy with prefix rules (format v35)
> > > > > >
> > > > > >
> > > > > >  Test | Mem   | Binary | Policy | Create tty      | osbench
> > > > > >       | Usage | policy | load   |                 | create
> > > > > >       |       | size   | time   | (ms/file)       | files
> > > > > >       | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
> > > > > > ------+-------+--------+--------+--------+--------+-----------
> > > > > >  [1]  |   157 |    3.4 |     78 | 1.1021 | 0.7586 | 7.8277
> > > > > >  [2]  |   200 |    3.4 |    206 | 1.1193 | 0.7724 | 8.2711
> > > > > >  [3]  |   169 |    5.8 |    106 | 1.1021 | 0.7724 | 8.0304
> > > > > >  [4]  |   164 |    3.8 |     86 | 1.1029 | 0.7586 | 7.9609
> > > > >
> > > > > Thanks for performing those measurements.
> > > > >
> > > > > I apologize that I haven't had an opportunity to review your patcheset
> > > > > in detail just yet (I've been struggling with some self-inflicted
> > > > > networking issues this week), but looking strictly at the numbers
> > > > > above it appears that by every metric in the table this patchset
> > > > > results in a policy that is larger (both on-disk and in-memory) as
> > > > > well as performance that is at best the same (although in most cases,
> > > > > it is worse).  Are there any improvements expected beyond test
> > > > > configuration [4] (above)?
> > > >
> > > > The main goal of this patchset is to bring the possibility to use prefix
> > > > or suffix matching in filename transitions, as now it is not possible to
> > > > cover files that have fixed prefix and variable part after it. For
> > > > example devices in /dev (the policy now enumerates all possible number
> > > > suffixes) or files with random suffix/prefix (not possible at all).
> > > >
> > > > The next goal is to make future improvements easier, for example
> > > > supporting filename transitions in conditional policies or inherent
> > > > support for type attributes.
> > > >
> > > > As for performance, the goal is to implement previous goals while not
> > > > killing the performance by them. Christian suggested some possible
> > > > optimizations [1], but after trying them out [2] they either not provide
> > > > much measurable difference or the difference is small and the
> > > > implementation hacky.
> > >
> > > I understand performance improvements were not the main motivation
> > > behind this patchset, but I'm somewhat concerned that policy load time
> > > *almost* triples in the case of an unmodified policy with this patch
> > > applied.  Since that will be most everyone as soon as this patch is
> > > applied, that regression does concern me ... I'm not sure just yet how
> > > much it concerns me, but it isn't trivial.
> >
> > I also understand your concern. That higher load time (and also memory
> > usage) is the cost of doing the conversion from the older binary policy
> > format in the kernel during load.
> >
> > However, to reduce both load time and memory usage to the values in the
> > third test, the only action needed is recompiling the policy with newer
> > checkpolicy/libsepol, patches to which I also proposed.
> 

Hi Stephen

Sorry for late reply, but before replying, I wanted to finish the
prototype of an alternative solution to this feature, which I was
already working on, but I got stuck on other tasks. The performance
metrics of this solution can be found below.


> I'm also struggling a bit with the justification here. If the runtime
> and memory usage is worse or no better in every dimension even with a
> policy rewritten to use the new prefix/suffix matching feature, it
> seems hard to justify the change.

The main reasons to move filename transitions to avtab were to solve
issues that arise due to the separation of filename type transitions
from other type enforcement rules, which Ondrej also mentioned to me in
person while discussing this idea. By moving the filename transitions
closer to other rules, we can:

- reduce the technical debt in the code,
- support type attributes as other rules do (this could also reduce
  number of required rules),
- make other improvements easier, namely prefix/suffix matching or
  supporting filename transitions in conditional avtab as proposed by
  Christian [1].

These improvements come at a price. However, much of the performance
loss is reclaimed by simply converting the policy to the new format.
Only its size on the disk stays the same without modifying the rules.


[1]: https://lore.kernel.org/selinux/20230602135427.33897-1-cgzones@googlemail.com/


> 
> I'd be curious to see what results you would get if you simply added
> the new feature (prefix/suffix matching) without moving the name-based
> transitions into the avtab.

Here are the performance metrics of a prototype solution, where the
filename transition key is extended with match_type and match is found
by shortening the name from the end or the beginning if a full match is
not found.

[2] Reference kernel (447a5688005e), Fedora policy (format v33)
[3] This patchset, Fedora policy (format v33)
[4] This patchset, Fedora policy without prefix/suffix rules (format v34)
[5] This patchset, Fedora policy with prefix rules (format v34)


 Test | Mem   | Binary | Policy | Create tty      | osbench
      | Usage | policy | load   |                 | create
      |       | size   | time   | (ms/file)       | files
      | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
------+-------+--------+--------+--------+--------+-----------
 [2]  |   157 |    3.4 |     76 |  1.256 |  0.871 | 9.4492
 [3]  |   156 |    3.4 |     77 |  1.208 |  0.869 | 9.6160
 [4]  |   157 |    3.4 |     71 |  1.239 |  0.893 | 9.6297
 [5]  |   156 |    2.4 |     71 |  1.211 |  0.838 | 9.8305


> 
> Also wondering whether you considered the simpler approach of just
> augmenting the kernel to recognize and support use of wildcards at the
> beginning and/or end of the existing name field to signify a prefix or
> suffix match. That seems more amenable to extensions beyond just
> prefix or suffix match.

I had not considered this approach in the beginning, but as I thought
about it, it did not seem as simple.

For example, along with adding the wildcard character, we also need to
add the ability to escape it; otherwise, it would be a weird edge case
of an unsupported filename. Also, possibly to escape the escape
character itself. This adds more complexity to the solution.

In addition to this, extending such solution to support wildcards
anywhere in the filename would also require reimplementing the filename
transitions structures or moving rules with wildcards away from current
filename transitions. Currently, the filename is part of the hashtab key
and prefix/suffix could work by checking all prefixes and suffixes of a
filename, which there are not that many. However, with a wildcard at any
position, this is not feasible.


Best regards

Juraj Marcin

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Stephen Smalley]

On Thu, Jul 27, 2023 at 12:43 PM Juraj Marcin <juraj@jurajmarcin.com> wrote:
>
> On 2023-07-17 14:44, Stephen Smalley wrote:
> >
> > I'd be curious to see what results you would get if you simply added
> > the new feature (prefix/suffix matching) without moving the name-based
> > transitions into the avtab.
>
> Here are the performance metrics of a prototype solution, where the
> filename transition key is extended with match_type and match is found
> by shortening the name from the end or the beginning if a full match is
> not found.
>
> [2] Reference kernel (447a5688005e), Fedora policy (format v33)
> [3] This patchset, Fedora policy (format v33)
> [4] This patchset, Fedora policy without prefix/suffix rules (format v34)
> [5] This patchset, Fedora policy with prefix rules (format v34)
>
>
>  Test | Mem   | Binary | Policy | Create tty      | osbench
>       | Usage | policy | load   |                 | create
>       |       | size   | time   | (ms/file)       | files
>       | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
> ------+-------+--------+--------+--------+--------+-----------
>  [2]  |   157 |    3.4 |     76 |  1.256 |  0.871 | 9.4492
>  [3]  |   156 |    3.4 |     77 |  1.208 |  0.869 | 9.6160
>  [4]  |   157 |    3.4 |     71 |  1.239 |  0.893 | 9.6297
>  [5]  |   156 |    2.4 |     71 |  1.211 |  0.838 | 9.8305

This looks more promising to me - little-to-no impact on existing
users with old policy/userspace, reduced memory usage once fully
transitioned. Still some degradation in runtime for osbench but not
sure what the variance/stddev is for those numbers.

> > Also wondering whether you considered the simpler approach of just
> > augmenting the kernel to recognize and support use of wildcards at the
> > beginning and/or end of the existing name field to signify a prefix or
> > suffix match. That seems more amenable to extensions beyond just
> > prefix or suffix match.
>
> I had not considered this approach in the beginning, but as I thought
> about it, it did not seem as simple.
>
> For example, along with adding the wildcard character, we also need to
> add the ability to escape it; otherwise, it would be a weird edge case
> of an unsupported filename. Also, possibly to escape the escape
> character itself. This adds more complexity to the solution.
>
> In addition to this, extending such solution to support wildcards
> anywhere in the filename would also require reimplementing the filename
> transitions structures or moving rules with wildcards away from current
> filename transitions. Currently, the filename is part of the hashtab key
> and prefix/suffix could work by checking all prefixes and suffixes of a
> filename, which there are not that many. However, with a wildcard at any
> position, this is not feasible.

Fair enough. That said, I do wonder if users will immediately start
asking for wildcards at any position, then file globbing or regexes,
etc, and would like to allow for future extensibility in a less
disruptive manner.

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[James Carter]

On Fri, Jul 28, 2023 at 9:29 AM Stephen Smalley
<stephen.smalley.work@gmail.com> wrote:
>
> On Thu, Jul 27, 2023 at 12:43 PM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> >
> > On 2023-07-17 14:44, Stephen Smalley wrote:
> > >
> > > I'd be curious to see what results you would get if you simply added
> > > the new feature (prefix/suffix matching) without moving the name-based
> > > transitions into the avtab.
> >
> > Here are the performance metrics of a prototype solution, where the
> > filename transition key is extended with match_type and match is found
> > by shortening the name from the end or the beginning if a full match is
> > not found.
> >
> > [2] Reference kernel (447a5688005e), Fedora policy (format v33)
> > [3] This patchset, Fedora policy (format v33)
> > [4] This patchset, Fedora policy without prefix/suffix rules (format v34)
> > [5] This patchset, Fedora policy with prefix rules (format v34)
> >
> >
> >  Test | Mem   | Binary | Policy | Create tty      | osbench
> >       | Usage | policy | load   |                 | create
> >       |       | size   | time   | (ms/file)       | files
> >       | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
> > ------+-------+--------+--------+--------+--------+-----------
> >  [2]  |   157 |    3.4 |     76 |  1.256 |  0.871 | 9.4492
> >  [3]  |   156 |    3.4 |     77 |  1.208 |  0.869 | 9.6160
> >  [4]  |   157 |    3.4 |     71 |  1.239 |  0.893 | 9.6297
> >  [5]  |   156 |    2.4 |     71 |  1.211 |  0.838 | 9.8305
>
> This looks more promising to me - little-to-no impact on existing
> users with old policy/userspace, reduced memory usage once fully
> transitioned. Still some degradation in runtime for osbench but not
> sure what the variance/stddev is for those numbers.
>

It does look promising.

Does this new prototype change the kernel policy format and the userspace parts.
If it does, then I will go ahead and revert the previous userspace
patches and wait for the new ones.

> > > Also wondering whether you considered the simpler approach of just
> > > augmenting the kernel to recognize and support use of wildcards at the
> > > beginning and/or end of the existing name field to signify a prefix or
> > > suffix match. That seems more amenable to extensions beyond just
> > > prefix or suffix match.
> >
> > I had not considered this approach in the beginning, but as I thought
> > about it, it did not seem as simple.
> >
> > For example, along with adding the wildcard character, we also need to
> > add the ability to escape it; otherwise, it would be a weird edge case
> > of an unsupported filename. Also, possibly to escape the escape
> > character itself. This adds more complexity to the solution.
> >
> > In addition to this, extending such solution to support wildcards
> > anywhere in the filename would also require reimplementing the filename
> > transitions structures or moving rules with wildcards away from current
> > filename transitions. Currently, the filename is part of the hashtab key
> > and prefix/suffix could work by checking all prefixes and suffixes of a
> > filename, which there are not that many. However, with a wildcard at any
> > position, this is not feasible.
>
> Fair enough. That said, I do wonder if users will immediately start
> asking for wildcards at any position, then file globbing or regexes,
> etc, and would like to allow for future extensibility in a less
> disruptive manner.

If anyone knows of any cases where a prefix or suffix match would not
work, it would be nice to hear about those cases now.
Jim

Re: [PATCH 0/5] selinux: add prefix/suffix matching to filename type transitions

[Juraj Marcin]

On 2023-07-28 13:52, James Carter wrote:
> On Fri, Jul 28, 2023 at 9:29 AM Stephen Smalley
> <stephen.smalley.work@gmail.com> wrote:
> >
> > On Thu, Jul 27, 2023 at 12:43 PM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> > >
> > > On 2023-07-17 14:44, Stephen Smalley wrote:
> > > >
> > > > I'd be curious to see what results you would get if you simply added
> > > > the new feature (prefix/suffix matching) without moving the name-based
> > > > transitions into the avtab.
> > >
> > > Here are the performance metrics of a prototype solution, where the
> > > filename transition key is extended with match_type and match is found
> > > by shortening the name from the end or the beginning if a full match is
> > > not found.
> > >
> > > [2] Reference kernel (447a5688005e), Fedora policy (format v33)
> > > [3] This patchset, Fedora policy (format v33)
> > > [4] This patchset, Fedora policy without prefix/suffix rules (format v34)
> > > [5] This patchset, Fedora policy with prefix rules (format v34)
> > >
> > >
> > >  Test | Mem   | Binary | Policy | Create tty      | osbench
> > >       | Usage | policy | load   |                 | create
> > >       |       | size   | time   | (ms/file)       | files
> > >       | (MiB) | (MiB)  | (ms)   | real   | kernel | (us/file)
> > > ------+-------+--------+--------+--------+--------+-----------
> > >  [2]  |   157 |    3.4 |     76 |  1.256 |  0.871 | 9.4492
> > >  [3]  |   156 |    3.4 |     77 |  1.208 |  0.869 | 9.6160
> > >  [4]  |   157 |    3.4 |     71 |  1.239 |  0.893 | 9.6297
> > >  [5]  |   156 |    2.4 |     71 |  1.211 |  0.838 | 9.8305
> >
> > This looks more promising to me - little-to-no impact on existing
> > users with old policy/userspace, reduced memory usage once fully
> > transitioned. Still some degradation in runtime for osbench but not
> > sure what the variance/stddev is for those numbers.
> >
> 
> It does look promising.
> 
> Does this new prototype change the kernel policy format and the userspace parts.
> If it does, then I will go ahead and revert the previous userspace
> patches and wait for the new ones.

It does as I tried to keep the kernel policy format as close to the
internal representation as possible.

> 
> > > > Also wondering whether you considered the simpler approach of just
> > > > augmenting the kernel to recognize and support use of wildcards at the
> > > > beginning and/or end of the existing name field to signify a prefix or
> > > > suffix match. That seems more amenable to extensions beyond just
> > > > prefix or suffix match.
> > >
> > > I had not considered this approach in the beginning, but as I thought
> > > about it, it did not seem as simple.
> > >
> > > For example, along with adding the wildcard character, we also need to
> > > add the ability to escape it; otherwise, it would be a weird edge case
> > > of an unsupported filename. Also, possibly to escape the escape
> > > character itself. This adds more complexity to the solution.
> > >
> > > In addition to this, extending such solution to support wildcards
> > > anywhere in the filename would also require reimplementing the filename
> > > transitions structures or moving rules with wildcards away from current
> > > filename transitions. Currently, the filename is part of the hashtab key
> > > and prefix/suffix could work by checking all prefixes and suffixes of a
> > > filename, which there are not that many. However, with a wildcard at any
> > > position, this is not feasible.
> >
> > Fair enough. That said, I do wonder if users will immediately start
> > asking for wildcards at any position, then file globbing or regexes,
> > etc, and would like to allow for future extensibility in a less
> > disruptive manner.
> 
> If anyone knows of any cases where a prefix or suffix match would not
> work, it would be nice to hear about those cases now.
> Jim

-- 
Juraj Marcin