[PATCH v2 0/2] Optimize storage of filename transitions

[PATCH v2 0/2] Optimize storage of filename transitions

[Ondrej Mosnacek]

This series improves the computational and memory efficiency of filename
transition rules in SELinux. The first patch is only cosmetic, see the
second patch for more details about its effects.

Changes in v2:
 - removed unnecessary assigment of 'last'
 - renamed 'exists' variable to 'already_there' which is more clear
 - added more likely/unlikely annotations (there will almost always be
   just one datum per key)

Ondrej Mosnacek (2):
  selinux: factor out loop body from filename_trans_read()
  selinux: optimize storage of filename transitions

 security/selinux/ss/policydb.c | 225 +++++++++++++++++++--------------
 security/selinux/ss/policydb.h |   8 +-
 security/selinux/ss/services.c |  16 ++-
 3 files changed, 146 insertions(+), 103 deletions(-)

-- 
2.24.1

[PATCH v2 1/2] selinux: factor out loop body from filename_trans_read()

[Ondrej Mosnacek]

It simplifies cleanup in the error path. This will be extra useful in
later patch.

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 security/selinux/ss/policydb.c | 122 +++++++++++++++++----------------
 1 file changed, 63 insertions(+), 59 deletions(-)

diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 2aa7f2e1a8e7..981797bfc547 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -1880,88 +1880,92 @@ out:
 	return rc;
 }
 
-static int filename_trans_read(struct policydb *p, void *fp)
+static int filename_trans_read_one(struct policydb *p, void *fp)
 {
 	struct filename_trans *ft;
-	struct filename_trans_datum *otype;
-	char *name;
-	u32 nel, len;
+	struct filename_trans_datum *otype = NULL;
+	char *name = NULL;
+	u32 len;
 	__le32 buf[4];
-	int rc, i;
+	int rc;
 
-	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
-		return 0;
+	ft = kzalloc(sizeof(*ft), GFP_KERNEL);
+	if (!ft)
+		return -ENOMEM;
+
+	rc = -ENOMEM;
+	otype = kmalloc(sizeof(*otype), GFP_KERNEL);
+	if (!otype)
+		goto out;
 
+	/* length of the path component string */
 	rc = next_entry(buf, fp, sizeof(u32));
 	if (rc)
-		return rc;
-	nel = le32_to_cpu(buf[0]);
-
-	for (i = 0; i < nel; i++) {
-		otype = NULL;
-		name = NULL;
-
-		rc = -ENOMEM;
-		ft = kzalloc(sizeof(*ft), GFP_KERNEL);
-		if (!ft)
-			goto out;
-
-		rc = -ENOMEM;
-		otype = kmalloc(sizeof(*otype), GFP_KERNEL);
-		if (!otype)
-			goto out;
-
-		/* length of the path component string */
-		rc = next_entry(buf, fp, sizeof(u32));
-		if (rc)
-			goto out;
-		len = le32_to_cpu(buf[0]);
+		goto out;
+	len = le32_to_cpu(buf[0]);
 
-		/* path component string */
-		rc = str_read(&name, GFP_KERNEL, fp, len);
-		if (rc)
-			goto out;
+	/* path component string */
+	rc = str_read(&name, GFP_KERNEL, fp, len);
+	if (rc)
+		goto out;
 
-		ft->name = name;
+	ft->name = name;
 
-		rc = next_entry(buf, fp, sizeof(u32) * 4);
-		if (rc)
-			goto out;
+	rc = next_entry(buf, fp, sizeof(u32) * 4);
+	if (rc)
+		goto out;
 
-		ft->stype = le32_to_cpu(buf[0]);
-		ft->ttype = le32_to_cpu(buf[1]);
-		ft->tclass = le32_to_cpu(buf[2]);
+	ft->stype = le32_to_cpu(buf[0]);
+	ft->ttype = le32_to_cpu(buf[1]);
+	ft->tclass = le32_to_cpu(buf[2]);
 
-		otype->otype = le32_to_cpu(buf[3]);
+	otype->otype = le32_to_cpu(buf[3]);
 
-		rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
-		if (rc)
-			goto out;
+	rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
+	if (rc)
+		goto out;
 
-		rc = hashtab_insert(p->filename_trans, ft, otype);
-		if (rc) {
-			/*
-			 * Do not return -EEXIST to the caller, or the system
-			 * will not boot.
-			 */
-			if (rc != -EEXIST)
-				goto out;
-			/* But free memory to avoid memory leak. */
-			kfree(ft);
-			kfree(name);
-			kfree(otype);
-		}
+	rc = hashtab_insert(p->filename_trans, ft, otype);
+	if (rc) {
+		/*
+		 * Do not return -EEXIST to the caller, or the system
+		 * will not boot.
+		 */
+		if (rc == -EEXIST)
+			rc = 0;
+		goto out;
 	}
-	hash_eval(p->filename_trans, "filenametr");
 	return 0;
 out:
 	kfree(ft);
 	kfree(name);
 	kfree(otype);
-
 	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]);
+
+	for (i = 0; i < nel; i++) {
+		rc = filename_trans_read_one(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;
-- 
2.24.1

[PATCH v2 2/2] selinux: optimize storage of filename transitions

[Ondrej Mosnacek]

In these rules, each rule with the same (target type, target class,
filename) values is (in practice) always mapped to the same result type.
Therefore, it is much more efficient to group the rules by (ttype,
tclass, filename).

Thus, this patch drops the stype field from the key and changes the
datum to be a linked list of one or more structures that contain a
result type and an ebitmap of source types that map the given target to
the given result type under the given filename. The size of the hash
table is also incremented to 2048 to be more optimal for Fedora policy
(which currently has ~2500 unique (ttype, tclass, filename) tuples,
regardless of whether the 'unconfined' module is enabled).

Not only does this dramtically reduce memory usage when the policy
contains a lot of unconfined domains (ergo a lot of filename based
transitions), but it also slightly reduces memory usage of strongly
confined policies (modeled on Fedora policy with 'unconfined' module
disabled) and significantly reduces lookup times of these rules on
Fedora (roughly matches the performance of the rhashtable conversion
patch [1] posted recently to selinux@vger.kernel.org).

An obvious next step is to change binary policy format to match this
layout, so that disk space is also saved. However, since that requires
more work (including matching userspace changes) and this patch is
already beneficial on its own, I'm posting it separately.

Performance/memory usage comparison:

Kernel           | Policy load | Policy load   | Mem usage | Mem usage     | openbench
                 |             | (-unconfined) |           | (-unconfined) | (createfiles)
-----------------|-------------|---------------|-----------|---------------|--------------
reference        |       1,30s |         0,91s |      90MB |          77MB | 55 us/file
rhashtable patch |       0.98s |         0,85s |      85MB |          75MB | 38 us/file
this patch       |       0,95s |         0,87s |      75MB |          75MB | 40 us/file

(Memory usage is measured after boot. With SELinux disabled the memory
usage was ~60MB on the same system.)

[1] https://lore.kernel.org/selinux/20200116213937.77795-1-dev@lynxeye.de/T/

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
 security/selinux/ss/policydb.c | 173 ++++++++++++++++++++-------------
 security/selinux/ss/policydb.h |   8 +-
 security/selinux/ss/services.c |  16 +--
 3 files changed, 118 insertions(+), 79 deletions(-)

diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 981797bfc547..d8b72718e793 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -336,11 +336,17 @@ static int (*destroy_f[SYM_NUM]) (void *key, void *datum, void *datap) =
 
 static int filenametr_destroy(void *key, void *datum, void *p)
 {
-	struct filename_trans *ft = key;
+	struct filename_trans_key *ft = key;
+	struct filename_trans_datum *next, *d = datum;
 
 	kfree(ft->name);
 	kfree(key);
-	kfree(datum);
+	do {
+		ebitmap_destroy(&d->stypes);
+		next = d->next;
+		kfree(d);
+		d = next;
+	} while (unlikely(d));
 	cond_resched();
 	return 0;
 }
@@ -406,12 +412,12 @@ out:
 
 static u32 filenametr_hash(struct hashtab *h, const void *k)
 {
-	const struct filename_trans *ft = k;
+	const struct filename_trans_key *ft = k;
 	unsigned long hash;
 	unsigned int byte_num;
 	unsigned char focus;
 
-	hash = ft->stype ^ ft->ttype ^ ft->tclass;
+	hash = ft->ttype ^ ft->tclass;
 
 	byte_num = 0;
 	while ((focus = ft->name[byte_num++]))
@@ -421,14 +427,10 @@ static u32 filenametr_hash(struct hashtab *h, const void *k)
 
 static int filenametr_cmp(struct hashtab *h, const void *k1, const void *k2)
 {
-	const struct filename_trans *ft1 = k1;
-	const struct filename_trans *ft2 = k2;
+	const struct filename_trans_key *ft1 = k1;
+	const struct filename_trans_key *ft2 = k2;
 	int v;
 
-	v = ft1->stype - ft2->stype;
-	if (v)
-		return v;
-
 	v = ft1->ttype - ft2->ttype;
 	if (v)
 		return v;
@@ -495,7 +497,7 @@ static int policydb_init(struct policydb *p)
 		goto out;
 
 	p->filename_trans = hashtab_create(filenametr_hash, filenametr_cmp,
-					   (1 << 10));
+					   (1 << 11));
 	if (!p->filename_trans) {
 		rc = -ENOMEM;
 		goto out;
@@ -1882,64 +1884,91 @@ out:
 
 static int filename_trans_read_one(struct policydb *p, void *fp)
 {
-	struct filename_trans *ft;
-	struct filename_trans_datum *otype = NULL;
+	struct filename_trans_key key, *ft = NULL;
+	struct filename_trans_datum *datum, *last, *newdatum = NULL;
+	uintptr_t stype, otype;
 	char *name = NULL;
 	u32 len;
 	__le32 buf[4];
 	int rc;
-
-	ft = kzalloc(sizeof(*ft), GFP_KERNEL);
-	if (!ft)
-		return -ENOMEM;
-
-	rc = -ENOMEM;
-	otype = kmalloc(sizeof(*otype), GFP_KERNEL);
-	if (!otype)
-		goto out;
+	bool already_there;
 
 	/* length of the path component string */
 	rc = next_entry(buf, fp, sizeof(u32));
 	if (rc)
-		goto out;
+		return rc;
 	len = le32_to_cpu(buf[0]);
 
 	/* path component string */
 	rc = str_read(&name, GFP_KERNEL, fp, len);
 	if (rc)
-		goto out;
-
-	ft->name = name;
+		return rc;
 
 	rc = next_entry(buf, fp, sizeof(u32) * 4);
 	if (rc)
 		goto out;
 
-	ft->stype = le32_to_cpu(buf[0]);
-	ft->ttype = le32_to_cpu(buf[1]);
-	ft->tclass = le32_to_cpu(buf[2]);
+	stype = le32_to_cpu(buf[0]);
+	key.ttype = le32_to_cpu(buf[1]);
+	key.tclass = le32_to_cpu(buf[2]);
+	key.name = name;
 
-	otype->otype = le32_to_cpu(buf[3]);
+	otype = le32_to_cpu(buf[3]);
 
-	rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
-	if (rc)
-		goto out;
+	already_there = false;
+	last = NULL;
+	datum = hashtab_search(p->filename_trans, &key);
+	while (datum) {
+		if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
+			already_there = true;
+			break;
+		}
+		if (likely(datum->otype == otype))
+			break;
+		last = datum;
+		datum = datum->next;
+	}
+	if (unlikely(already_there))
+		goto out; /* conflicting/duplicate rules are ignored */
+	if (!datum) {
+		rc = -ENOMEM;
+		newdatum = kmalloc(sizeof(*newdatum), GFP_KERNEL);
+		if (!newdatum)
+			goto out;
 
-	rc = hashtab_insert(p->filename_trans, ft, otype);
-	if (rc) {
-		/*
-		 * Do not return -EEXIST to the caller, or the system
-		 * will not boot.
-		 */
-		if (rc == -EEXIST)
-			rc = 0;
-		goto out;
+		ebitmap_init(&newdatum->stypes);
+		newdatum->otype = otype;
+		newdatum->next = NULL;
+
+		if (unlikely(last)) {
+			last->next = newdatum;
+		} else {
+			rc = -ENOMEM;
+			ft = kzalloc(sizeof(*ft), GFP_KERNEL);
+			if (!ft)
+				goto out;
+
+			*ft = key;
+
+			rc = hashtab_insert(p->filename_trans, ft, newdatum);
+			if (rc)
+				goto out;
+			name = NULL;
+
+			rc = ebitmap_set_bit(&p->filename_trans_ttypes,
+					     key.ttype, 1);
+			if (rc)
+				return rc;
+		}
+		datum = newdatum;
 	}
-	return 0;
+	kfree(name);
+	return ebitmap_set_bit(&datum->stypes, stype - 1, 1);
+
 out:
 	kfree(ft);
 	kfree(name);
-	kfree(otype);
+	kfree(newdatum);
 	return rc;
 }
 
@@ -1957,6 +1986,8 @@ static int filename_trans_read(struct policydb *p, void *fp)
 		return rc;
 	nel = le32_to_cpu(buf[0]);
 
+	p->filename_trans_count = nel;
+
 	for (i = 0; i < nel; i++) {
 		rc = filename_trans_read_one(p, fp);
 		if (rc)
@@ -3334,50 +3365,52 @@ static int range_write(struct policydb *p, void *fp)
 
 static int filename_write_helper(void *key, void *data, void *ptr)
 {
-	__le32 buf[4];
-	struct filename_trans *ft = key;
-	struct filename_trans_datum *otype = data;
+	struct filename_trans_key *ft = key;
+	struct filename_trans_datum *datum = data;
 	void *fp = ptr;
+	__le32 buf[4];
 	int rc;
-	u32 len;
+	u32 len, bit;
 
-	len = strlen(ft->name);
-	buf[0] = cpu_to_le32(len);
-	rc = put_entry(buf, sizeof(u32), 1, fp);
-	if (rc)
-		return rc;
+	do {
+		struct ebitmap_node *node;
 
-	rc = put_entry(ft->name, sizeof(char), len, fp);
-	if (rc)
-		return rc;
+		ebitmap_for_each_positive_bit(&datum->stypes, node, bit) {
+			len = strlen(ft->name);
+			buf[0] = cpu_to_le32(len);
+			rc = put_entry(buf, sizeof(u32), 1, fp);
+			if (rc)
+				return rc;
 
-	buf[0] = cpu_to_le32(ft->stype);
-	buf[1] = cpu_to_le32(ft->ttype);
-	buf[2] = cpu_to_le32(ft->tclass);
-	buf[3] = cpu_to_le32(otype->otype);
+			rc = put_entry(ft->name, sizeof(char), len, fp);
+			if (rc)
+				return rc;
 
-	rc = put_entry(buf, sizeof(u32), 4, 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_trans_write(struct policydb *p, void *fp)
 {
-	u32 nel;
 	__le32 buf[1];
 	int rc;
 
 	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
 		return 0;
 
-	nel = 0;
-	rc = hashtab_map(p->filename_trans, hashtab_cnt, &nel);
-	if (rc)
-		return rc;
-
-	buf[0] = cpu_to_le32(nel);
+	buf[0] = cpu_to_le32(p->filename_trans_count);
 	rc = put_entry(buf, sizeof(u32), 1, fp);
 	if (rc)
 		return rc;
diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
index 69b24191fa38..a947642816b0 100644
--- a/security/selinux/ss/policydb.h
+++ b/security/selinux/ss/policydb.h
@@ -89,15 +89,16 @@ struct role_trans {
 	struct role_trans *next;
 };
 
-struct filename_trans {
-	u32 stype;		/* current process */
+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 {
-	u32 otype;		/* expected of new object */
+	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 {
@@ -267,6 +268,7 @@ struct policydb {
 	struct ebitmap filename_trans_ttypes;
 	/* actual set of filename_trans rules */
 	struct hashtab *filename_trans;
+	u32 filename_trans_count;
 
 	/* bools indexed by (value - 1) */
 	struct cond_bool_datum **bool_val_to_struct;
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index e310f8ee21a1..83878c3d43a0 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1692,8 +1692,8 @@ static void filename_compute_type(struct policydb *policydb,
 				  u32 stype, u32 ttype, u16 tclass,
 				  const char *objname)
 {
-	struct filename_trans ft;
-	struct filename_trans_datum *otype;
+	struct filename_trans_key ft;
+	struct filename_trans_datum *datum;
 
 	/*
 	 * Most filename trans rules are going to live in specific directories
@@ -1703,14 +1703,18 @@ static void filename_compute_type(struct policydb *policydb,
 	if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
 		return;
 
-	ft.stype = stype;
 	ft.ttype = ttype;
 	ft.tclass = tclass;
 	ft.name = objname;
 
-	otype = hashtab_search(policydb->filename_trans, &ft);
-	if (otype)
-		newcontext->type = otype->otype;
+	datum = hashtab_search(policydb->filename_trans, &ft);
+	while (datum) {
+		if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
+			newcontext->type = datum->otype;
+			return;
+		}
+		datum = datum->next;
+	}
 }
 
 static int security_compute_sid(struct selinux_state *state,
-- 
2.24.1

Re: [PATCH v2 1/2] selinux: factor out loop body from filename_trans_read()

[Stephen Smalley]

On 2/12/20 6:22 AM, Ondrej Mosnacek wrote:
> It simplifies cleanup in the error path. This will be extra useful in
> later patch.
> 
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>

Acked-by: Stephen Smalley <sds@tycho.nsa.gov>

> ---
>   security/selinux/ss/policydb.c | 122 +++++++++++++++++----------------
>   1 file changed, 63 insertions(+), 59 deletions(-)
> 
> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index 2aa7f2e1a8e7..981797bfc547 100644
> --- a/security/selinux/ss/policydb.c
> +++ b/security/selinux/ss/policydb.c
> @@ -1880,88 +1880,92 @@ out:
>   	return rc;
>   }
>   
> -static int filename_trans_read(struct policydb *p, void *fp)
> +static int filename_trans_read_one(struct policydb *p, void *fp)
>   {
>   	struct filename_trans *ft;
> -	struct filename_trans_datum *otype;
> -	char *name;
> -	u32 nel, len;
> +	struct filename_trans_datum *otype = NULL;
> +	char *name = NULL;
> +	u32 len;
>   	__le32 buf[4];
> -	int rc, i;
> +	int rc;
>   
> -	if (p->policyvers < POLICYDB_VERSION_FILENAME_TRANS)
> -		return 0;
> +	ft = kzalloc(sizeof(*ft), GFP_KERNEL);
> +	if (!ft)
> +		return -ENOMEM;
> +
> +	rc = -ENOMEM;
> +	otype = kmalloc(sizeof(*otype), GFP_KERNEL);
> +	if (!otype)
> +		goto out;
>   
> +	/* length of the path component string */
>   	rc = next_entry(buf, fp, sizeof(u32));
>   	if (rc)
> -		return rc;
> -	nel = le32_to_cpu(buf[0]);
> -
> -	for (i = 0; i < nel; i++) {
> -		otype = NULL;
> -		name = NULL;
> -
> -		rc = -ENOMEM;
> -		ft = kzalloc(sizeof(*ft), GFP_KERNEL);
> -		if (!ft)
> -			goto out;
> -
> -		rc = -ENOMEM;
> -		otype = kmalloc(sizeof(*otype), GFP_KERNEL);
> -		if (!otype)
> -			goto out;
> -
> -		/* length of the path component string */
> -		rc = next_entry(buf, fp, sizeof(u32));
> -		if (rc)
> -			goto out;
> -		len = le32_to_cpu(buf[0]);
> +		goto out;
> +	len = le32_to_cpu(buf[0]);
>   
> -		/* path component string */
> -		rc = str_read(&name, GFP_KERNEL, fp, len);
> -		if (rc)
> -			goto out;
> +	/* path component string */
> +	rc = str_read(&name, GFP_KERNEL, fp, len);
> +	if (rc)
> +		goto out;
>   
> -		ft->name = name;
> +	ft->name = name;
>   
> -		rc = next_entry(buf, fp, sizeof(u32) * 4);
> -		if (rc)
> -			goto out;
> +	rc = next_entry(buf, fp, sizeof(u32) * 4);
> +	if (rc)
> +		goto out;
>   
> -		ft->stype = le32_to_cpu(buf[0]);
> -		ft->ttype = le32_to_cpu(buf[1]);
> -		ft->tclass = le32_to_cpu(buf[2]);
> +	ft->stype = le32_to_cpu(buf[0]);
> +	ft->ttype = le32_to_cpu(buf[1]);
> +	ft->tclass = le32_to_cpu(buf[2]);
>   
> -		otype->otype = le32_to_cpu(buf[3]);
> +	otype->otype = le32_to_cpu(buf[3]);
>   
> -		rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
> -		if (rc)
> -			goto out;
> +	rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
> +	if (rc)
> +		goto out;
>   
> -		rc = hashtab_insert(p->filename_trans, ft, otype);
> -		if (rc) {
> -			/*
> -			 * Do not return -EEXIST to the caller, or the system
> -			 * will not boot.
> -			 */
> -			if (rc != -EEXIST)
> -				goto out;
> -			/* But free memory to avoid memory leak. */
> -			kfree(ft);
> -			kfree(name);
> -			kfree(otype);
> -		}
> +	rc = hashtab_insert(p->filename_trans, ft, otype);
> +	if (rc) {
> +		/*
> +		 * Do not return -EEXIST to the caller, or the system
> +		 * will not boot.
> +		 */
> +		if (rc == -EEXIST)
> +			rc = 0;
> +		goto out;
>   	}
> -	hash_eval(p->filename_trans, "filenametr");
>   	return 0;
>   out:
>   	kfree(ft);
>   	kfree(name);
>   	kfree(otype);
> -
>   	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]);
> +
> +	for (i = 0; i < nel; i++) {
> +		rc = filename_trans_read_one(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;
> 

Re: [PATCH v2 2/2] selinux: optimize storage of filename transitions

[Stephen Smalley]

On 2/12/20 6:22 AM, Ondrej Mosnacek wrote:
> In these rules, each rule with the same (target type, target class,
> filename) values is (in practice) always mapped to the same result type.
> Therefore, it is much more efficient to group the rules by (ttype,
> tclass, filename).
> 
> Thus, this patch drops the stype field from the key and changes the
> datum to be a linked list of one or more structures that contain a
> result type and an ebitmap of source types that map the given target to
> the given result type under the given filename. The size of the hash
> table is also incremented to 2048 to be more optimal for Fedora policy
> (which currently has ~2500 unique (ttype, tclass, filename) tuples,
> regardless of whether the 'unconfined' module is enabled).
> 
> Not only does this dramtically reduce memory usage when the policy
> contains a lot of unconfined domains (ergo a lot of filename based
> transitions), but it also slightly reduces memory usage of strongly
> confined policies (modeled on Fedora policy with 'unconfined' module
> disabled) and significantly reduces lookup times of these rules on
> Fedora (roughly matches the performance of the rhashtable conversion
> patch [1] posted recently to selinux@vger.kernel.org).
> 
> An obvious next step is to change binary policy format to match this
> layout, so that disk space is also saved. However, since that requires
> more work (including matching userspace changes) and this patch is
> already beneficial on its own, I'm posting it separately.
> 
> Performance/memory usage comparison:
> 
> Kernel           | Policy load | Policy load   | Mem usage | Mem usage     | openbench
>                   |             | (-unconfined) |           | (-unconfined) | (createfiles)
> -----------------|-------------|---------------|-----------|---------------|--------------
> reference        |       1,30s |         0,91s |      90MB |          77MB | 55 us/file
> rhashtable patch |       0.98s |         0,85s |      85MB |          75MB | 38 us/file
> this patch       |       0,95s |         0,87s |      75MB |          75MB | 40 us/file
> 
> (Memory usage is measured after boot. With SELinux disabled the memory
> usage was ~60MB on the same system.)
> 
> [1] https://lore.kernel.org/selinux/20200116213937.77795-1-dev@lynxeye.de/T/
> 
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>

Acked-by: Stephen Smalley <sds@tycho.nsa.gov>

[...]

Re: [PATCH v2 1/2] selinux: factor out loop body from filename_trans_read()

[Paul Moore]

On Wed, Feb 12, 2020 at 6:23 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>
> It simplifies cleanup in the error path. This will be extra useful in
> later patch.
>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
>  security/selinux/ss/policydb.c | 122 +++++++++++++++++----------------
>  1 file changed, 63 insertions(+), 59 deletions(-)

Merged into selinux/next.

-- 
paul moore
www.paul-moore.com

Re: [PATCH v2 2/2] selinux: optimize storage of filename transitions

[Paul Moore]

On Wed, Feb 12, 2020 at 6:23 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>
> In these rules, each rule with the same (target type, target class,
> filename) values is (in practice) always mapped to the same result type.
> Therefore, it is much more efficient to group the rules by (ttype,
> tclass, filename).
>
> Thus, this patch drops the stype field from the key and changes the
> datum to be a linked list of one or more structures that contain a
> result type and an ebitmap of source types that map the given target to
> the given result type under the given filename. The size of the hash
> table is also incremented to 2048 to be more optimal for Fedora policy
> (which currently has ~2500 unique (ttype, tclass, filename) tuples,
> regardless of whether the 'unconfined' module is enabled).
>
> Not only does this dramtically reduce memory usage when the policy
> contains a lot of unconfined domains (ergo a lot of filename based
> transitions), but it also slightly reduces memory usage of strongly
> confined policies (modeled on Fedora policy with 'unconfined' module
> disabled) and significantly reduces lookup times of these rules on
> Fedora (roughly matches the performance of the rhashtable conversion
> patch [1] posted recently to selinux@vger.kernel.org).
>
> An obvious next step is to change binary policy format to match this
> layout, so that disk space is also saved. However, since that requires
> more work (including matching userspace changes) and this patch is
> already beneficial on its own, I'm posting it separately.
>
> Performance/memory usage comparison:
>
> Kernel           | Policy load | Policy load   | Mem usage | Mem usage     | openbench
>                  |             | (-unconfined) |           | (-unconfined) | (createfiles)
> -----------------|-------------|---------------|-----------|---------------|--------------
> reference        |       1,30s |         0,91s |      90MB |          77MB | 55 us/file
> rhashtable patch |       0.98s |         0,85s |      85MB |          75MB | 38 us/file
> this patch       |       0,95s |         0,87s |      75MB |          75MB | 40 us/file
>
> (Memory usage is measured after boot. With SELinux disabled the memory
> usage was ~60MB on the same system.)
>
> [1] https://lore.kernel.org/selinux/20200116213937.77795-1-dev@lynxeye.de/T/
>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
>  security/selinux/ss/policydb.c | 173 ++++++++++++++++++++-------------
>  security/selinux/ss/policydb.h |   8 +-
>  security/selinux/ss/services.c |  16 +--
>  3 files changed, 118 insertions(+), 79 deletions(-)

...

> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index 981797bfc547..d8b72718e793 100644
> --- a/security/selinux/ss/policydb.c
> +++ b/security/selinux/ss/policydb.c
> @@ -1882,64 +1884,91 @@ out:
>
>  static int filename_trans_read_one(struct policydb *p, void *fp)
>  {
> -       struct filename_trans *ft;
> -       struct filename_trans_datum *otype = NULL;
> +       struct filename_trans_key key, *ft = NULL;
> +       struct filename_trans_datum *datum, *last, *newdatum = NULL;
> +       uintptr_t stype, otype;
>         char *name = NULL;
>         u32 len;
>         __le32 buf[4];
>         int rc;
> -
> -       ft = kzalloc(sizeof(*ft), GFP_KERNEL);
> -       if (!ft)
> -               return -ENOMEM;
> -
> -       rc = -ENOMEM;
> -       otype = kmalloc(sizeof(*otype), GFP_KERNEL);
> -       if (!otype)
> -               goto out;
> +       bool already_there;
>
>         /* length of the path component string */
>         rc = next_entry(buf, fp, sizeof(u32));
>         if (rc)
> -               goto out;
> +               return rc;
>         len = le32_to_cpu(buf[0]);
>
>         /* path component string */
>         rc = str_read(&name, GFP_KERNEL, fp, len);
>         if (rc)
> -               goto out;
> -
> -       ft->name = name;
> +               return rc;
>
>         rc = next_entry(buf, fp, sizeof(u32) * 4);
>         if (rc)
>                 goto out;
>
> -       ft->stype = le32_to_cpu(buf[0]);
> -       ft->ttype = le32_to_cpu(buf[1]);
> -       ft->tclass = le32_to_cpu(buf[2]);
> +       stype = le32_to_cpu(buf[0]);
> +       key.ttype = le32_to_cpu(buf[1]);
> +       key.tclass = le32_to_cpu(buf[2]);
> +       key.name = name;

We don't really need the "name" variable anymore do we, we can just
use "key.name" instead, right?

>
> -       otype->otype = le32_to_cpu(buf[3]);
> +       otype = le32_to_cpu(buf[3]);
>
> -       rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
> -       if (rc)
> -               goto out;
> +       already_there = false;
> +       last = NULL;
> +       datum = hashtab_search(p->filename_trans, &key);
> +       while (datum) {
> +               if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
> +                       already_there = true;
> +                       break;

Considering the "already_there" check below simply jumps to "out", why
do we need to add the "already_there" variable, can't we simply jump
to the "out" label here?  Am I missing something?

> +               }
> +               if (likely(datum->otype == otype))
> +                       break;
> +               last = datum;
> +               datum = datum->next;
> +       }
> +       if (unlikely(already_there))
> +               goto out; /* conflicting/duplicate rules are ignored */
> +       if (!datum) {
> +               rc = -ENOMEM;
> +               newdatum = kmalloc(sizeof(*newdatum), GFP_KERNEL);
> +               if (!newdatum)
> +                       goto out;

By definition "datum" will be NULL here so we can get rid of
"newdatum" and just reuse "datum", yes?  I think the only place where
we would have to worry about the kfree(datum) in the "out" jump label
would be in this (!datum) if block which should be okay ...

> -       rc = hashtab_insert(p->filename_trans, ft, otype);
> -       if (rc) {
> -               /*
> -                * Do not return -EEXIST to the caller, or the system
> -                * will not boot.
> -                */
> -               if (rc == -EEXIST)
> -                       rc = 0;
> -               goto out;
> +               ebitmap_init(&newdatum->stypes);
> +               newdatum->otype = otype;
> +               newdatum->next = NULL;
> +
> +               if (unlikely(last)) {
> +                       last->next = newdatum;
> +               } else {
> +                       rc = -ENOMEM;
> +                       ft = kzalloc(sizeof(*ft), GFP_KERNEL);
> +                       if (!ft)
> +                               goto out;
> +
> +                       *ft = key;

Off the top of my head I don't know the answer to this, and I worry it
may fall into the category of "undefined behavior", but if we are
assigning an entire struct to another dynamically allocated variable
using "=" is the kzalloc() necessary?  Could we save ourselves a few
cycles and safely use kmalloc() for "ft"?

> +                       rc = hashtab_insert(p->filename_trans, ft, newdatum);
> +                       if (rc)
> +                               goto out;
> +                       name = NULL;
> +
> +                       rc = ebitmap_set_bit(&p->filename_trans_ttypes,
> +                                            key.ttype, 1);
> +                       if (rc)
> +                               return rc;
> +               }
> +               datum = newdatum;
>         }
> -       return 0;
> +       kfree(name);
> +       return ebitmap_set_bit(&datum->stypes, stype - 1, 1);
> +
>  out:
>         kfree(ft);
>         kfree(name);
> -       kfree(otype);
> +       kfree(newdatum);
>         return rc;
>  }

-- 
paul moore
www.paul-moore.com

Re: [PATCH v2 2/2] selinux: optimize storage of filename transitions

[Ondrej Mosnacek]

On Fri, Feb 14, 2020 at 1:35 AM Paul Moore <paul@paul-moore.com> wrote:
> On Wed, Feb 12, 2020 at 6:23 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> >
> > In these rules, each rule with the same (target type, target class,
> > filename) values is (in practice) always mapped to the same result type.
> > Therefore, it is much more efficient to group the rules by (ttype,
> > tclass, filename).
> >
> > Thus, this patch drops the stype field from the key and changes the
> > datum to be a linked list of one or more structures that contain a
> > result type and an ebitmap of source types that map the given target to
> > the given result type under the given filename. The size of the hash
> > table is also incremented to 2048 to be more optimal for Fedora policy
> > (which currently has ~2500 unique (ttype, tclass, filename) tuples,
> > regardless of whether the 'unconfined' module is enabled).
> >
> > Not only does this dramtically reduce memory usage when the policy
> > contains a lot of unconfined domains (ergo a lot of filename based
> > transitions), but it also slightly reduces memory usage of strongly
> > confined policies (modeled on Fedora policy with 'unconfined' module
> > disabled) and significantly reduces lookup times of these rules on
> > Fedora (roughly matches the performance of the rhashtable conversion
> > patch [1] posted recently to selinux@vger.kernel.org).
> >
> > An obvious next step is to change binary policy format to match this
> > layout, so that disk space is also saved. However, since that requires
> > more work (including matching userspace changes) and this patch is
> > already beneficial on its own, I'm posting it separately.
> >
> > Performance/memory usage comparison:
> >
> > Kernel           | Policy load | Policy load   | Mem usage | Mem usage     | openbench
> >                  |             | (-unconfined) |           | (-unconfined) | (createfiles)
> > -----------------|-------------|---------------|-----------|---------------|--------------
> > reference        |       1,30s |         0,91s |      90MB |          77MB | 55 us/file
> > rhashtable patch |       0.98s |         0,85s |      85MB |          75MB | 38 us/file
> > this patch       |       0,95s |         0,87s |      75MB |          75MB | 40 us/file
> >
> > (Memory usage is measured after boot. With SELinux disabled the memory
> > usage was ~60MB on the same system.)
> >
> > [1] https://lore.kernel.org/selinux/20200116213937.77795-1-dev@lynxeye.de/T/
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> > ---
> >  security/selinux/ss/policydb.c | 173 ++++++++++++++++++++-------------
> >  security/selinux/ss/policydb.h |   8 +-
> >  security/selinux/ss/services.c |  16 +--
> >  3 files changed, 118 insertions(+), 79 deletions(-)
>
> ...
>
> > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > index 981797bfc547..d8b72718e793 100644
> > --- a/security/selinux/ss/policydb.c
> > +++ b/security/selinux/ss/policydb.c
> > @@ -1882,64 +1884,91 @@ out:
> >
> >  static int filename_trans_read_one(struct policydb *p, void *fp)
> >  {
> > -       struct filename_trans *ft;
> > -       struct filename_trans_datum *otype = NULL;
> > +       struct filename_trans_key key, *ft = NULL;
> > +       struct filename_trans_datum *datum, *last, *newdatum = NULL;
> > +       uintptr_t stype, otype;
> >         char *name = NULL;
> >         u32 len;
> >         __le32 buf[4];
> >         int rc;
> > -
> > -       ft = kzalloc(sizeof(*ft), GFP_KERNEL);
> > -       if (!ft)
> > -               return -ENOMEM;
> > -
> > -       rc = -ENOMEM;
> > -       otype = kmalloc(sizeof(*otype), GFP_KERNEL);
> > -       if (!otype)
> > -               goto out;
> > +       bool already_there;
> >
> >         /* length of the path component string */
> >         rc = next_entry(buf, fp, sizeof(u32));
> >         if (rc)
> > -               goto out;
> > +               return rc;
> >         len = le32_to_cpu(buf[0]);
> >
> >         /* path component string */
> >         rc = str_read(&name, GFP_KERNEL, fp, len);
> >         if (rc)
> > -               goto out;
> > -
> > -       ft->name = name;
> > +               return rc;
> >
> >         rc = next_entry(buf, fp, sizeof(u32) * 4);
> >         if (rc)
> >                 goto out;
> >
> > -       ft->stype = le32_to_cpu(buf[0]);
> > -       ft->ttype = le32_to_cpu(buf[1]);
> > -       ft->tclass = le32_to_cpu(buf[2]);
> > +       stype = le32_to_cpu(buf[0]);
> > +       key.ttype = le32_to_cpu(buf[1]);
> > +       key.tclass = le32_to_cpu(buf[2]);
> > +       key.name = name;
>
> We don't really need the "name" variable anymore do we, we can just
> use "key.name" instead, right?

It is possible, but there is a slight obstacle in that "key.name" is
"const char *" and "name" is "char *" (and str_read() expects a
reference to "char *"). We could change the type in the
filename_trans_key struct, but is it really worth it?

I like to have a separate variable for the name, since it is easier to
spot that it is something we allocate and need to take care not to
leak it. It is easier to forget that there is that one member of key
that you need to free in the error path.

I'll be foolish enough to hope that I convinced you so I'll wait for
your reaction for now, but I'm willing to do the change if you still
want it :)

>
> >
> > -       otype->otype = le32_to_cpu(buf[3]);
> > +       otype = le32_to_cpu(buf[3]);
> >
> > -       rc = ebitmap_set_bit(&p->filename_trans_ttypes, ft->ttype, 1);
> > -       if (rc)
> > -               goto out;
> > +       already_there = false;
> > +       last = NULL;
> > +       datum = hashtab_search(p->filename_trans, &key);
> > +       while (datum) {
> > +               if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
> > +                       already_there = true;
> > +                       break;
>
> Considering the "already_there" check below simply jumps to "out", why
> do we need to add the "already_there" variable, can't we simply jump
> to the "out" label here?  Am I missing something?

Indeed we can... I think I originally expected some more complex logic
under if(already_there) (e.g. reporting warning) so that's why my
brain insisted on having a bool variable... Thanks for spotting it,
I'll simplify it in the next respin.

>
> > +               }
> > +               if (likely(datum->otype == otype))
> > +                       break;
> > +               last = datum;
> > +               datum = datum->next;
> > +       }
> > +       if (unlikely(already_there))
> > +               goto out; /* conflicting/duplicate rules are ignored */
> > +       if (!datum) {
> > +               rc = -ENOMEM;
> > +               newdatum = kmalloc(sizeof(*newdatum), GFP_KERNEL);
> > +               if (!newdatum)
> > +                       goto out;
>
> By definition "datum" will be NULL here so we can get rid of
> "newdatum" and just reuse "datum", yes?  I think the only place where
> we would have to worry about the kfree(datum) in the "out" jump label
> would be in this (!datum) if block which should be okay ...

Well, yes, if we remember to set datum to NULL in the "already_there"
case (and of course at the beginning of the function), then it happens
to work out. It feels a bit unsafe to me, since we should never free
any datum we get from the hashtable, as opposed to the one we
allocate, and using the same variable for both could be error-prone...
but my objection isn't strong, so I'll just do it.

>
> > -       rc = hashtab_insert(p->filename_trans, ft, otype);
> > -       if (rc) {
> > -               /*
> > -                * Do not return -EEXIST to the caller, or the system
> > -                * will not boot.
> > -                */
> > -               if (rc == -EEXIST)
> > -                       rc = 0;
> > -               goto out;
> > +               ebitmap_init(&newdatum->stypes);
> > +               newdatum->otype = otype;
> > +               newdatum->next = NULL;
> > +
> > +               if (unlikely(last)) {
> > +                       last->next = newdatum;
> > +               } else {
> > +                       rc = -ENOMEM;
> > +                       ft = kzalloc(sizeof(*ft), GFP_KERNEL);
> > +                       if (!ft)
> > +                               goto out;
> > +
> > +                       *ft = key;
>
> Off the top of my head I don't know the answer to this, and I worry it
> may fall into the category of "undefined behavior", but if we are
> assigning an entire struct to another dynamically allocated variable
> using "=" is the kzalloc() necessary?  Could we save ourselves a few
> cycles and safely use kmalloc() for "ft"?

Good point. Actually, we can even use kmemdup() to make it a one-step
operation. I don't think there is any issue with undefined behavior,
it is just copying the contents of a struct.


>
> > +                       rc = hashtab_insert(p->filename_trans, ft, newdatum);
> > +                       if (rc)
> > +                               goto out;
> > +                       name = NULL;
> > +
> > +                       rc = ebitmap_set_bit(&p->filename_trans_ttypes,
> > +                                            key.ttype, 1);
> > +                       if (rc)
> > +                               return rc;
> > +               }
> > +               datum = newdatum;
> >         }
> > -       return 0;
> > +       kfree(name);
> > +       return ebitmap_set_bit(&datum->stypes, stype - 1, 1);
> > +
> >  out:
> >         kfree(ft);
> >         kfree(name);
> > -       kfree(otype);
> > +       kfree(newdatum);
> >         return rc;
> >  }
>
> --
> paul moore
> www.paul-moore.com
>


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

Re: [PATCH v2 2/2] selinux: optimize storage of filename transitions

[Paul Moore]

On Fri, Feb 14, 2020 at 4:12 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> On Fri, Feb 14, 2020 at 1:35 AM Paul Moore <paul@paul-moore.com> wrote:
> > On Wed, Feb 12, 2020 at 6:23 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:

...

> > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > > index 981797bfc547..d8b72718e793 100644
> > > --- a/security/selinux/ss/policydb.c
> > > +++ b/security/selinux/ss/policydb.c
> > > @@ -1882,64 +1884,91 @@ out:
> > >
> > >  static int filename_trans_read_one(struct policydb *p, void *fp)
> > >  {
> > > -       struct filename_trans *ft;
> > > -       struct filename_trans_datum *otype = NULL;
> > > +       struct filename_trans_key key, *ft = NULL;
> > > +       struct filename_trans_datum *datum, *last, *newdatum = NULL;
> > > +       uintptr_t stype, otype;
> > >         char *name = NULL;
> > >         u32 len;
> > >         __le32 buf[4];
> > >         int rc;
> > > -
> > > -       ft = kzalloc(sizeof(*ft), GFP_KERNEL);
> > > -       if (!ft)
> > > -               return -ENOMEM;
> > > -
> > > -       rc = -ENOMEM;
> > > -       otype = kmalloc(sizeof(*otype), GFP_KERNEL);
> > > -       if (!otype)
> > > -               goto out;
> > > +       bool already_there;
> > >
> > >         /* length of the path component string */
> > >         rc = next_entry(buf, fp, sizeof(u32));
> > >         if (rc)
> > > -               goto out;
> > > +               return rc;
> > >         len = le32_to_cpu(buf[0]);
> > >
> > >         /* path component string */
> > >         rc = str_read(&name, GFP_KERNEL, fp, len);
> > >         if (rc)
> > > -               goto out;
> > > -
> > > -       ft->name = name;
> > > +               return rc;
> > >
> > >         rc = next_entry(buf, fp, sizeof(u32) * 4);
> > >         if (rc)
> > >                 goto out;
> > >
> > > -       ft->stype = le32_to_cpu(buf[0]);
> > > -       ft->ttype = le32_to_cpu(buf[1]);
> > > -       ft->tclass = le32_to_cpu(buf[2]);
> > > +       stype = le32_to_cpu(buf[0]);
> > > +       key.ttype = le32_to_cpu(buf[1]);
> > > +       key.tclass = le32_to_cpu(buf[2]);
> > > +       key.name = name;
> >
> > We don't really need the "name" variable anymore do we, we can just
> > use "key.name" instead, right?
>
> It is possible, but there is a slight obstacle in that "key.name" is
> "const char *" and "name" is "char *" (and str_read() expects a
> reference to "char *"). We could change the type in the
> filename_trans_key struct, but is it really worth it?
>
> I like to have a separate variable for the name, since it is easier to
> spot that it is something we allocate and need to take care not to
> leak it. It is easier to forget that there is that one member of key
> that you need to free in the error path.
>
> I'll be foolish enough to hope that I convinced you so I'll wait for
> your reaction for now, but I'm willing to do the change if you still
> want it :)

Heh ;)

Okay, I'm convinced, let's keep "name".

-- 
paul moore
www.paul-moore.com