Skip to contentSkip to conversation

userspace: Implement new format of filename trans rules

PATCH Superseded Ondrej Mosnacek 2 participants 6 messages Jul 19, 2020 – Jul 22, 2020 SELinux security module

v5 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

v5 cover userspace: Implement new format of filename trans rules

These patches are the userspace side of the following kernel commits:
c3a276111ea2 ("selinux: optimize storage of filename transitions") [1] 430059024389 ("selinux: implement new format of filename transitions") [2].

The first patch changes libsepol's internal representation of filename transition rules in a way similar to the kernel commit.

The second patch then builds upon that and implements reading and writing of the new binary policy format that uses this representation also in the data layout.

See individual patches for more details.

NOTE: This series unfortunately breaks the build of setools. Moreover, when an existing build of setools dynamically links against the new libsepol, it segfaults. Sadly, there doesn't seem to be a nice way of handling this, since setools relies on non-public libsepol policydb API/ABI. I have prepared a preliminary patch to adapt setools to these changes - I'll open a WIP pull request for it soon...

See also this discussion about the setools impact:
https://lore.kernel.org/selinux/[email protected]/

Changes in v5:
- fix comment in filename_trans_read() to not change when being moved
- fix filename_trans_check_datum()
- destroy temporary ebitmaps at return
- actually iterate through datums

Changes in v4:
- rebased on top of latest master branch

Changes in v3:
- fixed the change in dispol.c to match the rest of the code
- renamed the helper functions to use the "_compat" suffix rather than "_old" and "_new"

Changes in v2:
- fixed counting rules when reading the new policy format

[1] https://git.kernel.org/pub/scm/linux/kernel/git/pcmoore/selinux.git/commit/?id=c3a276111ea2572399281988b3129683e2a6b60b
[2] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=4300590243895ac39e8c97a2f5acd004dad8a42f

Ondrej Mosnacek (2):
libsepol,checkpolicy: optimize storage of filename transitions
libsepol: implement POLICYDB_VERSION_COMP_FTRANS

 checkpolicy/policy_define.c                |  52 ++--
 checkpolicy/test/dispol.c                  |  20 +-
 libsepol/cil/src/cil_binary.c              |  29 +-
 libsepol/include/sepol/policydb/policydb.h |  18 +-
 libsepol/src/expand.c                      |  60 +---
 libsepol/src/kernel_to_cil.c               |  24 +-
 libsepol/src/kernel_to_conf.c              |  24 +-
 libsepol/src/policydb.c                    | 306 +++++++++++++++++----
 libsepol/src/write.c                       | 101 +++++--
 9 files changed, 435 insertions(+), 199 deletions(-)
Signature · 1 line
2.26.2
#1 lore raw

PATCH v5 1/2 libsepol,checkpolicy: optimize storage of filename transitions

In preparation to support a new policy format with a more optimal representation of filename transition rules, this patch applies an equivalent change from kernel commit c3a276111ea2 ("selinux: optimize storage of filename transitions").

See the kernel commit's description [1] for the rationale behind this representation. This change doesn't bring any measurable difference of policy build performance (semodule -B) on Fedora.

[1] https://git.kernel.org/pub/scm/linux/kernel/git/pcmoore/selinux.git/commit/?id=c3a276111ea2572399281988b3129683e2a6b60b

---
 checkpolicy/policy_define.c                |  52 +++------
 checkpolicy/test/dispol.c                  |  20 ++--
 libsepol/cil/src/cil_binary.c              |  29 ++---
 libsepol/include/sepol/policydb/policydb.h |  15 ++-
 libsepol/src/expand.c                      |  60 +++--------
 libsepol/src/kernel_to_cil.c               |  24 ++++-
 libsepol/src/kernel_to_conf.c              |  24 ++++-
 libsepol/src/policydb.c                    | 117 +++++++++++++++------
 libsepol/src/write.c                       |  46 ++++----
 9 files changed, 212 insertions(+), 175 deletions(-)
checkpolicy/policy_define.c +16 -36
index c6733fa4..01a90438 100644
@@ -3303,10 +3303,9 @@ int define_filename_trans(void)
 	ebitmap_t e_stypes, e_ttypes;
 	ebitmap_t e_tclasses;
 	ebitmap_node_t *snode, *tnode, *cnode;
-	filename_trans_t *ft;
-	filename_trans_datum_t *ftdatum;
 	filename_trans_rule_t *ftr;
 	type_datum_t *typdatum;
+	char *dup_name;
 	uint32_t otype;
 	unsigned int c, s, t;
 	int add, rc;
@@ -3388,40 +3387,21 @@ int define_filename_trans(void)
 	ebitmap_for_each_positive_bit(&e_tclasses, cnode, c) {
 		ebitmap_for_each_positive_bit(&e_stypes, snode, s) {
 			ebitmap_for_each_positive_bit(&e_ttypes, tnode, t) {
-				ft = calloc(1, sizeof(*ft));
-				if (!ft) {
-					yyerror("out of memory");
-					goto bad;
-				}
-				ft->stype = s+1;
-				ft->ttype = t+1;
-				ft->tclass = c+1;
-				ft->name = strdup(name);
-				if (!ft->name) {
-					yyerror("out of memory");
-					goto bad;
-				}
-
-				ftdatum = hashtab_search(policydbp->filename_trans,
-							 (hashtab_key_t)ft);
-				if (ftdatum) {
-					yyerror2("duplicate filename transition for: filename_trans %s %s %s:%s",
-						 name,
-						 policydbp->p_type_val_to_name[s],
-						 policydbp->p_type_val_to_name[t],
-						 policydbp->p_class_val_to_name[c]);
-					goto bad;
-				}
-
-				ftdatum = calloc(1, sizeof(*ftdatum));
-				if (!ftdatum) {
-					yyerror("out of memory");
-					goto bad;
-				}
-				rc = hashtab_insert(policydbp->filename_trans,
-						    (hashtab_key_t)ft,
-						    ftdatum);
-				if (rc) {
+				dup_name = NULL;
+				rc = policydb_filetrans_insert(
+					policydbp, s+1, t+1, c+1, name,
+					&dup_name, otype, NULL
+				);
+				free(dup_name);
+				if (rc != SEPOL_OK) {
+					if (rc == SEPOL_EEXIST) {
+						yyerror2("duplicate filename transition for: filename_trans %s %s %s:%s",
+							name,
+							policydbp->p_type_val_to_name[s],
+							policydbp->p_type_val_to_name[t],
+							policydbp->p_class_val_to_name[c]);
+						goto bad;
+					}
 					yyerror("out of memory");
 					goto bad;
 				}
checkpolicy/test/dispol.c +14 -6
index d72d9fb3..8785b725 100644
@@ -335,17 +335,25 @@ static int filenametr_display(hashtab_key_t key,
 			      hashtab_datum_t datum,
 			      void *ptr)
 {
-	struct filename_trans *ft = (struct filename_trans *)key;
+	struct filename_trans_key *ft = (struct filename_trans_key *)key;
 	struct filename_trans_datum *ftdatum = datum;
 	struct filenametr_display_args *args = ptr;
 	policydb_t *p = args->p;
 	FILE *fp = args->fp;
+	ebitmap_node_t *node;
+	uint32_t bit;
+
+	do {
+		ebitmap_for_each_positive_bit(&ftdatum->stypes, node, bit) {
+			display_id(p, fp, SYM_TYPES, bit, "");
+			display_id(p, fp, SYM_TYPES, ft->ttype - 1, "");
+			display_id(p, fp, SYM_CLASSES, ft->tclass - 1, ":");
+			display_id(p, fp, SYM_TYPES, ftdatum->otype - 1, "");
+			fprintf(fp, " %s\n", ft->name);
+		}
+		ftdatum = ftdatum->next;
+	} while (ftdatum);
 
-	display_id(p, fp, SYM_TYPES, ft->stype - 1, "");
-	display_id(p, fp, SYM_TYPES, ft->ttype - 1, "");
-	display_id(p, fp, SYM_CLASSES, ft->tclass - 1, ":");
-	display_id(p, fp, SYM_TYPES, ftdatum->otype - 1, "");
-	fprintf(fp, " %s\n", ft->name);
 	return 0;
 }
 
libsepol/cil/src/cil_binary.c +10 -19
index 62178d99..bedff628 100644
@@ -1131,13 +1131,13 @@ int __cil_typetransition_to_avtab(policydb_t *pdb, const struct cil_db *db, stru
 	class_datum_t *sepol_obj = NULL;
 	struct cil_list *class_list;
 	type_datum_t *sepol_result = NULL;
-	filename_trans_t *newkey = NULL;
-	filename_trans_datum_t *newdatum = NULL, *otype = NULL;
 	ebitmap_t src_bitmap, tgt_bitmap;
 	ebitmap_node_t *node1, *node2;
 	unsigned int i, j;
+	uint32_t otype;
 	struct cil_list_item *c;
 	char *name = DATUM(typetrans->name)->name;
+	char *dup_name;
 
 	if (name == CIL_KEY_STAR) {
 		struct cil_type_rule trans;
@@ -1176,22 +1176,16 @@ int __cil_typetransition_to_avtab(policydb_t *pdb, const struct cil_db *db, stru
 				rc = __cil_get_sepol_class_datum(pdb, DATUM(c->data), &sepol_obj);
 				if (rc != SEPOL_OK) goto exit;
 
-				newkey = cil_calloc(1, sizeof(*newkey));
-				newdatum = cil_calloc(1, sizeof(*newdatum));
-				newkey->stype = sepol_src->s.value;
-				newkey->ttype = sepol_tgt->s.value;
-				newkey->tclass = sepol_obj->s.value;
-				newkey->name = cil_strdup(name);
-				newdatum->otype = sepol_result->s.value;
-
-				rc = hashtab_insert(pdb->filename_trans,
-						    (hashtab_key_t)newkey,
-						    newdatum);
+				dup_name = NULL;
+				rc = policydb_filetrans_insert(
+					pdb, sepol_src->s.value, sepol_tgt->s.value,
+					sepol_obj->s.value, name, &dup_name,
+					sepol_result->s.value, &otype
+				);
+				free(dup_name);
 				if (rc != SEPOL_OK) {
 					if (rc == SEPOL_EEXIST) {
-						otype = hashtab_search(pdb->filename_trans,
-								(hashtab_key_t)newkey);
-						if (newdatum->otype != otype->otype) {
+						if (sepol_result->s.value!= otype) {
 							cil_log(CIL_ERR, "Conflicting name type transition rules\n");
 						} else {
 							rc = SEPOL_OK;
@@ -1199,9 +1193,6 @@ int __cil_typetransition_to_avtab(policydb_t *pdb, const struct cil_db *db, stru
 					} else {
 						cil_log(CIL_ERR, "Out of memory\n");
 					}
-					free(newkey->name);
-					free(newkey);
-					free(newdatum);
 					if (rc != SEPOL_OK) {
 						goto exit;
 					}
libsepol/include/sepol/policydb/policydb.h +11 -4
index 81b63fef..c3180c61 100644
@@ -162,15 +162,16 @@ typedef struct role_allow {
 } role_allow_t;
 
 /* filename_trans rules */
-typedef struct filename_trans {
-	uint32_t stype;
+typedef struct filename_trans_key {
 	uint32_t ttype;
 	uint32_t tclass;
 	char *name;
-} filename_trans_t;
+} filename_trans_key_t;
 
 typedef struct filename_trans_datum {
-	uint32_t otype;		/* expected of new object */
+	ebitmap_t stypes;
+	uint32_t otype;
+	struct filename_trans_datum *next;
 } filename_trans_datum_t;
 
 /* Type attributes */
@@ -591,6 +592,7 @@ typedef struct policydb {
 
 	/* file transitions with the last path component */
 	hashtab_t filename_trans;
+	uint32_t filename_trans_count;
 
 	ebitmap_t *type_attr_map;
 
@@ -650,6 +652,11 @@ extern int policydb_load_isids(policydb_t * p, sidtab_t * s);
 
 extern int policydb_sort_ocontexts(policydb_t *p);
 
+extern int policydb_filetrans_insert(policydb_t *p, uint32_t stype,
+				     uint32_t ttype, uint32_t tclass,
+				     const char *name, char **name_alloc,
+				     uint32_t otype, uint32_t *present_otype);
+
 /* Deprecated */
 extern int policydb_context_isvalid(const policydb_t * p,
 				    const context_struct_t * c);
libsepol/src/expand.c +14 -46

89 lines not on this page · raw message

libsepol/src/kernel_to_cil.c +19 -5
index 958adc4c..c247b32f 100644
@@ -1841,21 +1841,35 @@ struct map_filename_trans_args {
 
 static int map_filename_trans_to_str(hashtab_key_t key, void *data, void *arg)
 {
-	filename_trans_t *ft = (filename_trans_t *)key;
+	filename_trans_key_t *ft = (filename_trans_key_t *)key;
 	filename_trans_datum_t *datum = data;
 	struct map_filename_trans_args *map_args = arg;
 	struct policydb *pdb = map_args->pdb;
 	struct strs *strs = map_args->strs;
 	char *src, *tgt, *class, *filename, *new;
+	struct ebitmap_node *node;
+	uint32_t bit;
+	int rc;
 
-	src = pdb->p_type_val_to_name[ft->stype - 1];
 	tgt = pdb->p_type_val_to_name[ft->ttype - 1];
 	class = pdb->p_class_val_to_name[ft->tclass - 1];
 	filename = ft->name;
-	new =  pdb->p_type_val_to_name[datum->otype - 1];
+	do {
+		new = pdb->p_type_val_to_name[datum->otype - 1];
+
+		ebitmap_for_each_positive_bit(&datum->stypes, node, bit) {
+			src = pdb->p_type_val_to_name[bit];
+			rc = strs_create_and_add(strs,
+						 "(typetransition %s %s %s %s %s)",
+						 5, src, tgt, class, filename, new);
+			if (rc)
+				return rc;
+		}
+
+		datum = datum->next;
+	} while (datum);
 
-	return strs_create_and_add(strs, "(typetransition %s %s %s %s %s)", 5,
-				   src, tgt, class, filename, new);
+	return 0;
 }
 
 static int write_filename_trans_rules_to_cil(FILE *out, struct policydb *pdb)
libsepol/src/kernel_to_conf.c +19 -5
index 7cc91eb3..62bf706c 100644
@@ -1822,21 +1822,35 @@ struct map_filename_trans_args {
 
 static int map_filename_trans_to_str(hashtab_key_t key, void *data, void *arg)
 {
-	filename_trans_t *ft = (filename_trans_t *)key;
+	filename_trans_key_t *ft = (filename_trans_key_t *)key;
 	filename_trans_datum_t *datum = data;
 	struct map_filename_trans_args *map_args = arg;
 	struct policydb *pdb = map_args->pdb;
 	struct strs *strs = map_args->strs;
 	char *src, *tgt, *class, *filename, *new;
+	struct ebitmap_node *node;
+	uint32_t bit;
+	int rc;
 
-	src = pdb->p_type_val_to_name[ft->stype - 1];
 	tgt = pdb->p_type_val_to_name[ft->ttype - 1];
 	class = pdb->p_class_val_to_name[ft->tclass - 1];
 	filename = ft->name;
-	new =  pdb->p_type_val_to_name[datum->otype - 1];
+	do {
+		new = pdb->p_type_val_to_name[datum->otype - 1];
+
+		ebitmap_for_each_positive_bit(&datum->stypes, node, bit) {
+			src = pdb->p_type_val_to_name[bit];
+			rc = strs_create_and_add(strs,
+						 "type_transition %s %s:%s %s \"%s\";",
+						 5, src, tgt, class, new, filename);
+			if (rc)
+				return rc;
+		}
+
+		datum = datum->next;
+	} while (datum);
 
-	return strs_create_and_add(strs, "type_transition %s %s:%s %s \"%s\";", 5,
-				   src, tgt, class, new, filename);
+	return 0;
 }
 
 static int write_filename_trans_rules_to_conf(FILE *out, struct policydb *pdb)
libsepol/src/policydb.c +83 -34

183 lines not on this page · raw message

libsepol/src/write.c +26 -20

70 lines not on this page · raw message

Signature · 1 line
2.26.2
maintainer
#2 lore raw

Re: [PATCH v5 1/2] libsepol,checkpolicy: optimize storage of filename transitions

Quoted 20 lines · Ondrej Mosnacek

In preparation to support a new policy format with a more optimal representation of filename transition rules, this patch applies an equivalent change from kernel commit c3a276111ea2 ("selinux: optimize storage of filename transitions").

See the kernel commit's description [1] for the rationale behind this representation. This change doesn't bring any measurable difference of policy build performance (semodule -B) on Fedora.

[1] https://git.kernel.org/pub/scm/linux/kernel/git/pcmoore/selinux.git/commit/?id=c3a276111ea2572399281988b3129683e2a6b60b

---

checkpolicy/policy_define.c +0 -0
index c6733fa4..01a90438 100644
@@ -3388,40 +3387,21 @@ int define_filename_trans(void)

<snip>

checkpolicy/policy_define.c int define_filename_trans(void) · line 3395

Quoted 6 lines
checkpolicy/policy_define.c +6 -0
+                               dup_name = NULL;
+                               rc = policydb_filetrans_insert(
+                                       policydbp, s+1, t+1, c+1, name,
+                                       &dup_name, otype, NULL
+                               );
+                               free(dup_name);

The dup_name / name_alloc handling seems rather odd. In every caller except one you follow the pattern above, where we set it to NULL, call policydb_filetrans_insert, and then free it immediately. I'm not sure why you are doing it this way.

#3 lore raw

Re: [PATCH v5 1/2] libsepol,checkpolicy: optimize storage of filename transitions

Quoted 29 lines · Stephen Smalley
Quoted 20 lines · Ondrej Mosnacek

In preparation to support a new policy format with a more optimal representation of filename transition rules, this patch applies an equivalent change from kernel commit c3a276111ea2 ("selinux: optimize storage of filename transitions").

See the kernel commit's description [1] for the rationale behind this representation. This change doesn't bring any measurable difference of policy build performance (semodule -B) on Fedora.

[1] https://git.kernel.org/pub/scm/linux/kernel/git/pcmoore/selinux.git/commit/?id=c3a276111ea2572399281988b3129683e2a6b60b

---

checkpolicy/policy_define.c +0 -0
index c6733fa4..01a90438 100644
@@ -3388,40 +3387,21 @@ int define_filename_trans(void)

<snip>

checkpolicy/policy_define.c int define_filename_trans(void) · line 3395

Quoted 6 lines
checkpolicy/policy_define.c +6 -0
+                               dup_name = NULL;
+                               rc = policydb_filetrans_insert(
+                                       policydbp, s+1, t+1, c+1, name,
+                                       &dup_name, otype, NULL
+                               );
+                               free(dup_name);
Quoted 4 lines

The dup_name / name_alloc handling seems rather odd. In every caller except one you follow the pattern above, where we set it to NULL, call policydb_filetrans_insert, and then free it immediately. I'm not sure why you are doing it this way.

The original intent was to allow a choice between putting the already allocated string into the key (when the caller function owns it) vs. allocating a new string (when the caller gets just a read-only reference to it), while also leaving the string allocated in case such key already exists (so that the caller can use it in an error message, as filename_trans_read_one_compat() used to do). However, after rebasing on top of d27aa22dbeec ("libsepol: drop broken warning on duplicate filename transitions") such function interface seems to be no longer optimal... I'll see if I can simplify it.

Thanks for pointing it out.

Signature · 3 lines
Ondrej Mosnacek
Software Engineer, Platform Security - SELinux kernel
Red Hat, Inc.
#4 lore raw

PATCH v5 2/2 libsepol: implement POLICYDB_VERSION_COMP_FTRANS

In reply to Ondrej Mosnacek

Implement a new, more space-efficient form of storing filename transitions in the binary policy. The internal structures have already been converted to this new representation; this patch just implements reading/writing an equivalent representation from/to the binary policy.

This new format reduces the size of Fedora policy from 7.6 MB to only 3.3 MB (with policy optimization enabled in both cases). With the unconfined module disabled, the size is reduced from 3.3 MB to 2.4 MB.

---
 libsepol/include/sepol/policydb/policydb.h |   3 +-
 libsepol/src/policydb.c                    | 209 +++++++++++++++++----
 libsepol/src/write.c                       |  73 ++++++-
 3 files changed, 242 insertions(+), 43 deletions(-)
libsepol/include/sepol/policydb/policydb.h +2 -1
index c3180c61..9ef43abc 100644
@@ -755,10 +755,11 @@ extern int policydb_set_target_platform(policydb_t *p, int platform);
 #define POLICYDB_VERSION_XPERMS_IOCTL	30 /* Linux-specific */
 #define POLICYDB_VERSION_INFINIBAND		31 /* Linux-specific */
 #define POLICYDB_VERSION_GLBLUB		32
+#define POLICYDB_VERSION_COMP_FTRANS	33 /* compressed filename transitions */
 
 /* Range of policy versions we understand*/
 #define POLICYDB_VERSION_MIN	POLICYDB_VERSION_BASE
-#define POLICYDB_VERSION_MAX	POLICYDB_VERSION_GLBLUB
+#define POLICYDB_VERSION_MAX	POLICYDB_VERSION_COMP_FTRANS
 
 /* Module versions and specific changes*/
 #define MOD_POLICYDB_VERSION_BASE		4
libsepol/src/policydb.c +176 -33

247 lines not on this page · raw message

libsepol/src/write.c +64 -9

93 lines not on this page · raw message

Signature · 1 line
2.26.2
#5 lore raw
In reply to Ondrej Mosnacek
Quoted 11 lines · Ondrej Mosnacek

These patches are the userspace side of the following kernel commits:
c3a276111ea2 ("selinux: optimize storage of filename transitions") [1] 430059024389 ("selinux: implement new format of filename transitions") [2].

The first patch changes libsepol's internal representation of filename transition rules in a way similar to the kernel commit.

The second patch then builds upon that and implements reading and writing of the new binary policy format that uses this representation also in the data layout.

Quoted 8 lines

See individual patches for more details.

NOTE: This series unfortunately breaks the build of setools. Moreover, when an existing build of setools dynamically links against the new libsepol, it segfaults. Sadly, there doesn't seem to be a nice way of handling this, since setools relies on non-public libsepol policydb API/ABI. I have prepared a preliminary patch to adapt setools to these changes - I'll open a WIP pull request for it soon...

And the setools PR is here:
https://github.com/SELinuxProject/setools/pull/50

Quoted 3 lines

See also this discussion about the setools impact:
https://lore.kernel.org/selinux/[email protected]/

Signature · 3 lines
Ondrej Mosnacek
Software Engineer, Platform Security - SELinux kernel
Red Hat, Inc.