* [PATCH v4] selinux: add prefix/suffix matching to filename type transitions
@ 2023-11-21 12:27 Juraj Marcin
2023-11-21 19:24 ` Stephen Smalley
2023-12-06 3:18 ` Paul Moore
0 siblings, 2 replies; 10+ messages in thread
From: Juraj Marcin @ 2023-11-21 12:27 UTC (permalink / raw
To: Paul Moore; +Cc: Stephen Smalley, selinux, Ondrej Mosnacek
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.
This patch changes the filename transition table in the policydb
structure into an array of three tables, where the index determines the
match type for the rules contained (extract, prefix, and suffix match).
Then the patch extends the functions that access the table through the
policydb structure to accompany this change while reusing the majority
of the old filename transitions code.
This patch also updates the code responsible for finding the right
filename transition based on the context and the name. The rules have
the following order of prioriy, if no matching rule is found, the code
moves on to the next category:
- exact filename transitions,
- prefix filename transitions in the order of the longest prefix match,
- suffix filename transitions in the order of the longest suffix match.
This ensures the compatibility with older policies.
Without prefix/suffix rules in the policy, this patch has no impact on
performance or policy loading times. Moreover, with prefix/suffix rules,
the overall number of filename transitions can be reduced, which results
in smaller binary policy size and therefore also slightly lower load
time and memory usage.
Performance tests:
1: Reference kernel (f5bbdeda34c63), Fedora policy (format v33)
2: This patch, Fedora policy (format v33)
3: This patch, Fedora policy without prefix/suffix rules (format v34)
4: This patch, Fefora policy with prefix rules (format v35)
| Mem | Binary | Policy | Create tty [1] | osbench [2]
| Usage | policy | load | | create
| | size | time | (ms/file) | files
| (MiB) | (KiB) | (ms) | real | kernel | (us/file)
---+--------+--------+---------+----------+-----------+-----------
1 | 298.7 | 3682 | 58.626 | 1.0228 | 0.6793 | 8.4916
| sd=4.1 | | sd=0.47 | sd=0.058 | sd=0.0497 | sd=0.131
2 | 296.3 | 3682 | 58.915 | 1.0209 | 0.6752 | 8.5728
| sd=3.9 | | sd=0.28 | sd=0.021 | sd=0.0244 | sd=0.156
3 | 295.7 | 3682 | 56.374 | 1.0160 | 0.6616 | 8.7467
| sd=2.6 | | sd=0.44 | sd=0.008 | sd=0.0141 | sd=0.126
4 | 296.2 | 2585 | 51.434 | 1.0116 | 0.6699 | 8.7467
| sd=4.1 | | sd=0.39 | sd=0.012 | sd=0.0115 | sd=0.126
[1] 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.
[2] https://github.com/mbitsnbites/osbench
Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
---
v4:
- rebased to the latest pcmoore/selinux/next
- fixed non-atomic allocation in atomic section
---
v3:
- reworked the solution from scratch, this time only adding the
prefix/suffix matching feature without moving filename transition
rules to the avtab
---
security/selinux/include/security.h | 3 +-
security/selinux/ss/policydb.c | 96 ++++++++++++++++++++++-------
security/selinux/ss/policydb.h | 12 +++-
security/selinux/ss/services.c | 57 ++++++++++++++---
4 files changed, 134 insertions(+), 34 deletions(-)
diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
index a9de89af8fdc..943dfe7ede83 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_PREFIX_SUFFIX 34 /* prefix/suffix filename transitions */
/* 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_PREFIX_SUFFIX
/* Mask for just the mount related flags */
#define SE_MNTMASK 0x0f
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index bd1e7f26d951..562eaa70fb12 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_PREFIX_SUFFIX,
+ .sym_num = SYM_NUM,
+ .ocon_num = OCON_NUM,
+ },
};
static const struct policydb_compat_info *policydb_lookup_compat(unsigned int version)
@@ -437,10 +442,33 @@ static const struct hashtab_key_params filenametr_key_params = {
.cmp = filenametr_cmp,
};
-struct filename_trans_datum *policydb_filenametr_search(
- struct policydb *p, struct filename_trans_key *key)
+/**
+ * policydb_filenametr_search() - Search for filename transition in policy
+ * @p: policydb structure to search in
+ * @match_type: filename transition match type to search for
+ * @key: key to search for
+ * @stype: source type to search for, when stype is zero, the function will
+ * return head of the linked list with matching key, otherwise it will
+ * traverse the linked list to find the item with matching stype
+ *
+ * Return: head of the linked list of filename transition datums or single item
+ * of the list, based on the stype value
+ */
+struct filename_trans_datum *policydb_filenametr_search(struct policydb *p,
+ unsigned int match_type, struct filename_trans_key *key, u32 stype)
{
- return hashtab_search(&p->filename_trans, key, filenametr_key_params);
+ struct filename_trans_datum *datum = hashtab_search(
+ &p->filename_trans[match_type], key, filenametr_key_params);
+
+ if (stype) {
+ while (datum) {
+ if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
+ return datum;
+ }
+ datum = datum->next;
+ }
+ }
+ return datum;
}
static u32 rangetr_hash(const void *k)
@@ -833,8 +861,10 @@ void policydb_destroy(struct policydb *p)
}
kfree(lra);
- hashtab_map(&p->filename_trans, filenametr_destroy, NULL);
- hashtab_destroy(&p->filename_trans);
+ for (unsigned int i = 0; i < FILENAME_TRANS_MATCH_NUM; i++) {
+ hashtab_map(&p->filename_trans[i], filenametr_destroy, NULL);
+ hashtab_destroy(&p->filename_trans[i]);
+ }
hashtab_map(&p->range_tr, range_tr_destroy, NULL);
hashtab_destroy(&p->range_tr);
@@ -1909,7 +1939,9 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
otype = le32_to_cpu(buf[3]);
last = NULL;
- datum = policydb_filenametr_search(p, &key);
+ // this version does not support other than exact match
+ datum = policydb_filenametr_search(p, FILENAME_TRANS_MATCH_EXACT, &key,
+ 0);
while (datum) {
if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
/* conflicting/duplicate rules are ignored */
@@ -1939,8 +1971,9 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
if (!ft)
goto out;
- rc = hashtab_insert(&p->filename_trans, ft, datum,
- filenametr_key_params);
+ rc = hashtab_insert(
+ &p->filename_trans[FILENAME_TRANS_MATCH_EXACT],
+ ft, datum, filenametr_key_params);
if (rc)
goto out;
name = NULL;
@@ -1961,7 +1994,8 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
return rc;
}
-static int filename_trans_read_helper(struct policydb *p, void *fp)
+static int filename_trans_read_helper(struct policydb *p, void *fp,
+ unsigned int match_type)
{
struct filename_trans_key *ft = NULL;
struct filename_trans_datum **dst, *datum, *first = NULL;
@@ -2028,7 +2062,7 @@ static int filename_trans_read_helper(struct policydb *p, void *fp)
ft->tclass = tclass;
ft->name = name;
- rc = hashtab_insert(&p->filename_trans, ft, first,
+ rc = hashtab_insert(&p->filename_trans[match_type], ft, first,
filenametr_key_params);
if (rc == -EEXIST)
pr_err("SELinux: Duplicate filename transition key\n");
@@ -2050,7 +2084,8 @@ static int filename_trans_read_helper(struct policydb *p, void *fp)
return rc;
}
-static int filename_trans_read(struct policydb *p, void *fp)
+static int filename_trans_read(struct policydb *p, void *fp,
+ unsigned int match_type)
{
u32 nel, i;
__le32 buf[1];
@@ -2067,27 +2102,28 @@ static int filename_trans_read(struct policydb *p, void *fp)
if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
p->compat_filename_trans_count = nel;
- rc = hashtab_init(&p->filename_trans, (1 << 11));
+ rc = hashtab_init(&p->filename_trans[match_type], (1 << 11));
if (rc)
return rc;
for (i = 0; i < nel; i++) {
+ // this version does not support other than exact match
rc = filename_trans_read_helper_compat(p, fp);
if (rc)
return rc;
}
} else {
- rc = hashtab_init(&p->filename_trans, nel);
+ rc = hashtab_init(&p->filename_trans[match_type], nel);
if (rc)
return rc;
for (i = 0; i < nel; i++) {
- rc = filename_trans_read_helper(p, fp);
+ rc = filename_trans_read_helper(p, fp, match_type);
if (rc)
return rc;
}
}
- hash_eval(&p->filename_trans, "filenametr");
+ hash_eval(&p->filename_trans[match_type], "filenametr");
return 0;
}
@@ -2636,9 +2672,17 @@ int policydb_read(struct policydb *p, void *fp)
lra = ra;
}
- rc = filename_trans_read(p, fp);
+ rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_EXACT);
if (rc)
goto bad;
+ if (p->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
+ rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_PREFIX);
+ if (rc)
+ goto bad;
+ rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_SUFFIX);
+ if (rc)
+ goto bad;
+ }
rc = policydb_index(p);
if (rc)
@@ -3569,7 +3613,8 @@ static int filename_write_helper(void *key, void *data, void *ptr)
return 0;
}
-static int filename_trans_write(struct policydb *p, void *fp)
+static int filename_trans_write(struct policydb *p, void *fp,
+ unsigned int match_type)
{
__le32 buf[1];
int rc;
@@ -3583,15 +3628,16 @@ static int filename_trans_write(struct policydb *p, void *fp)
if (rc)
return rc;
- rc = hashtab_map(&p->filename_trans,
+ rc = hashtab_map(&p->filename_trans[match_type],
filename_write_helper_compat, fp);
} else {
- buf[0] = cpu_to_le32(p->filename_trans.nel);
+ buf[0] = cpu_to_le32(p->filename_trans[match_type].nel);
rc = put_entry(buf, sizeof(u32), 1, fp);
if (rc)
return rc;
- rc = hashtab_map(&p->filename_trans, filename_write_helper, fp);
+ rc = hashtab_map(&p->filename_trans[match_type],
+ filename_write_helper, fp);
}
return rc;
}
@@ -3706,9 +3752,17 @@ int policydb_write(struct policydb *p, void *fp)
if (rc)
return rc;
- rc = filename_trans_write(p, fp);
+ rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_EXACT);
if (rc)
return rc;
+ if (p->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
+ rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_PREFIX);
+ if (rc)
+ return rc;
+ rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_SUFFIX);
+ if (rc)
+ return rc;
+ }
rc = ocontext_write(p, info, fp);
if (rc)
diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
index b97cda489753..7bd0ecb8ed69 100644
--- a/security/selinux/ss/policydb.h
+++ b/security/selinux/ss/policydb.h
@@ -235,6 +235,13 @@ struct genfs {
#define OCON_IBENDPORT 8 /* Infiniband end ports */
#define OCON_NUM 9
+enum {
+ FILENAME_TRANS_MATCH_EXACT,
+ FILENAME_TRANS_MATCH_PREFIX,
+ FILENAME_TRANS_MATCH_SUFFIX,
+ FILENAME_TRANS_MATCH_NUM,
+};
+
/* The policy database */
struct policydb {
int mls_enabled;
@@ -269,7 +276,7 @@ struct policydb {
/* quickly exclude lookups when parent ttype has no rules */
struct ebitmap filename_trans_ttypes;
/* actual set of filename_trans rules */
- struct hashtab filename_trans;
+ struct hashtab filename_trans[FILENAME_TRANS_MATCH_NUM];
/* only used if policyvers < POLICYDB_VERSION_COMP_FTRANS */
u32 compat_filename_trans_count;
@@ -325,7 +332,8 @@ 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);
+ struct policydb *p, unsigned int match_type,
+ struct filename_trans_key *key, u32 stype);
extern struct mls_range *policydb_rangetr_search(
struct policydb *p, struct range_trans *key);
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index 1eeffc66ea7d..99200a9490a3 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1661,13 +1661,16 @@ static int compute_sid_handle_invalid_context(
return -EACCES;
}
-static void filename_compute_type(struct policydb *policydb,
+static int 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;
+ size_t name_len = strlen(objname);
+ size_t i;
+ char *name_copy;
/*
* Most filename trans rules are going to live in specific directories
@@ -1675,20 +1678,50 @@ static void filename_compute_type(struct policydb *policydb,
* if the ttype does not contain any rules.
*/
if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
- return;
+ return 0;
ft.ttype = ttype;
ft.tclass = tclass;
+
+ /* Search for exact rules */
ft.name = objname;
+ datum = policydb_filenametr_search(policydb, FILENAME_TRANS_MATCH_EXACT,
+ &ft, stype);
+ if (datum) {
+ newcontext->type = datum->otype;
+ return 0;
+ }
- datum = policydb_filenametr_search(policydb, &ft);
- while (datum) {
- if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
+ /* Search for prefix rules */
+ name_copy = kstrdup(objname, GFP_ATOMIC);
+ if (!name_copy)
+ return -ENOMEM;
+ ft.name = name_copy;
+ for (i = name_len; i > 0; i--) {
+ name_copy[i] = '\0';
+ datum = policydb_filenametr_search(policydb,
+ FILENAME_TRANS_MATCH_PREFIX,
+ &ft, stype);
+ if (datum) {
newcontext->type = datum->otype;
- return;
+ kfree(name_copy);
+ return 0;
}
- datum = datum->next;
}
+ kfree(name_copy);
+
+ /* Search for suffix rules */
+ for (i = 0; i < name_len; i++) {
+ ft.name = &objname[i];
+ datum = policydb_filenametr_search(policydb,
+ FILENAME_TRANS_MATCH_SUFFIX,
+ &ft, stype);
+ if (datum) {
+ newcontext->type = datum->otype;
+ return 0;
+ }
+ }
+ return 0;
}
static int security_compute_sid(u32 ssid,
@@ -1833,9 +1866,13 @@ static int security_compute_sid(u32 ssid,
}
/* 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);
+ if (objname) {
+ rc = filename_compute_type(policydb, &newcontext,
+ scontext->type, tcontext->type,
+ tclass, objname);
+ if (rc)
+ goto out_unlock;
+ }
/* Check for class-specific changes. */
if (specified & AVTAB_TRANSITION) {
--
2.42.0
^ permalink raw reply related [flat|nested] 10+ messages in thread
* Re: [PATCH v4] selinux: add prefix/suffix matching to filename type transitions
2023-11-21 12:27 [PATCH v4] selinux: add prefix/suffix matching to filename type transitions Juraj Marcin
@ 2023-11-21 19:24 ` Stephen Smalley
2023-12-06 3:18 ` Paul Moore
1 sibling, 0 replies; 10+ messages in thread
From: Stephen Smalley @ 2023-11-21 19:24 UTC (permalink / raw
To: Juraj Marcin; +Cc: Paul Moore, selinux, Ondrej Mosnacek
On Tue, Nov 21, 2023 at 7:29 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.
>
> This patch changes the filename transition table in the policydb
> structure into an array of three tables, where the index determines the
> match type for the rules contained (extract, prefix, and suffix match).
> Then the patch extends the functions that access the table through the
> policydb structure to accompany this change while reusing the majority
> of the old filename transitions code.
>
> This patch also updates the code responsible for finding the right
> filename transition based on the context and the name. The rules have
> the following order of prioriy, if no matching rule is found, the code
> moves on to the next category:
> - exact filename transitions,
> - prefix filename transitions in the order of the longest prefix match,
> - suffix filename transitions in the order of the longest suffix match.
> This ensures the compatibility with older policies.
>
> Without prefix/suffix rules in the policy, this patch has no impact on
> performance or policy loading times. Moreover, with prefix/suffix rules,
> the overall number of filename transitions can be reduced, which results
> in smaller binary policy size and therefore also slightly lower load
> time and memory usage.
>
> Performance tests:
>
> 1: Reference kernel (f5bbdeda34c63), Fedora policy (format v33)
> 2: This patch, Fedora policy (format v33)
> 3: This patch, Fedora policy without prefix/suffix rules (format v34)
> 4: This patch, Fefora policy with prefix rules (format v35)
>
> | Mem | Binary | Policy | Create tty [1] | osbench [2]
> | Usage | policy | load | | create
> | | size | time | (ms/file) | files
> | (MiB) | (KiB) | (ms) | real | kernel | (us/file)
> ---+--------+--------+---------+----------+-----------+-----------
> 1 | 298.7 | 3682 | 58.626 | 1.0228 | 0.6793 | 8.4916
> | sd=4.1 | | sd=0.47 | sd=0.058 | sd=0.0497 | sd=0.131
> 2 | 296.3 | 3682 | 58.915 | 1.0209 | 0.6752 | 8.5728
> | sd=3.9 | | sd=0.28 | sd=0.021 | sd=0.0244 | sd=0.156
> 3 | 295.7 | 3682 | 56.374 | 1.0160 | 0.6616 | 8.7467
> | sd=2.6 | | sd=0.44 | sd=0.008 | sd=0.0141 | sd=0.126
> 4 | 296.2 | 2585 | 51.434 | 1.0116 | 0.6699 | 8.7467
> | sd=4.1 | | sd=0.39 | sd=0.012 | sd=0.0115 | sd=0.126
>
> [1] 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.
>
> [2] https://github.com/mbitsnbites/osbench
>
> Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
> Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v4] selinux: add prefix/suffix matching to filename type transitions
2023-11-21 12:27 [PATCH v4] selinux: add prefix/suffix matching to filename type transitions Juraj Marcin
2023-11-21 19:24 ` Stephen Smalley
@ 2023-12-06 3:18 ` Paul Moore
2023-12-20 12:20 ` Juraj Marcin
1 sibling, 1 reply; 10+ messages in thread
From: Paul Moore @ 2023-12-06 3:18 UTC (permalink / raw
To: Juraj Marcin; +Cc: Stephen Smalley, selinux, Ondrej Mosnacek
On Nov 21, 2023 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.
>
> This patch changes the filename transition table in the policydb
> structure into an array of three tables, where the index determines the
> match type for the rules contained (extract, prefix, and suffix match).
> Then the patch extends the functions that access the table through the
> policydb structure to accompany this change while reusing the majority
> of the old filename transitions code.
>
> This patch also updates the code responsible for finding the right
> filename transition based on the context and the name. The rules have
> the following order of prioriy, if no matching rule is found, the code
> moves on to the next category:
> - exact filename transitions,
> - prefix filename transitions in the order of the longest prefix match,
> - suffix filename transitions in the order of the longest suffix match.
> This ensures the compatibility with older policies.
>
> Without prefix/suffix rules in the policy, this patch has no impact on
> performance or policy loading times. Moreover, with prefix/suffix rules,
> the overall number of filename transitions can be reduced, which results
> in smaller binary policy size and therefore also slightly lower load
> time and memory usage.
>
> Performance tests:
>
> 1: Reference kernel (f5bbdeda34c63), Fedora policy (format v33)
> 2: This patch, Fedora policy (format v33)
> 3: This patch, Fedora policy without prefix/suffix rules (format v34)
> 4: This patch, Fefora policy with prefix rules (format v35)
>
> | Mem | Binary | Policy | Create tty [1] | osbench [2]
> | Usage | policy | load | | create
> | | size | time | (ms/file) | files
> | (MiB) | (KiB) | (ms) | real | kernel | (us/file)
> ---+--------+--------+---------+----------+-----------+-----------
> 1 | 298.7 | 3682 | 58.626 | 1.0228 | 0.6793 | 8.4916
> | sd=4.1 | | sd=0.47 | sd=0.058 | sd=0.0497 | sd=0.131
> 2 | 296.3 | 3682 | 58.915 | 1.0209 | 0.6752 | 8.5728
> | sd=3.9 | | sd=0.28 | sd=0.021 | sd=0.0244 | sd=0.156
> 3 | 295.7 | 3682 | 56.374 | 1.0160 | 0.6616 | 8.7467
> | sd=2.6 | | sd=0.44 | sd=0.008 | sd=0.0141 | sd=0.126
> 4 | 296.2 | 2585 | 51.434 | 1.0116 | 0.6699 | 8.7467
> | sd=4.1 | | sd=0.39 | sd=0.012 | sd=0.0115 | sd=0.126
>
> [1] 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.
>
> [2] https://github.com/mbitsnbites/osbench
Hi Juraj, first I want to thank you for your continued persistence on
this patch, I know this has likely been a lot of work. However, I am
a little concerned about the osbench test results. The policy size
and load time improvements are really nice to see but I worry that
those wins might be overshadowed by the runtime performance impacts.
I did see some things which I think might improve that slightly, more
on that below ...
> Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
> Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> ---
> v4:
> - rebased to the latest pcmoore/selinux/next
> - fixed non-atomic allocation in atomic section
> ---
> v3:
> - reworked the solution from scratch, this time only adding the
> prefix/suffix matching feature without moving filename transition
> rules to the avtab
> ---
> security/selinux/include/security.h | 3 +-
> security/selinux/ss/policydb.c | 96 ++++++++++++++++++++++-------
> security/selinux/ss/policydb.h | 12 +++-
> security/selinux/ss/services.c | 57 ++++++++++++++---
> 4 files changed, 134 insertions(+), 34 deletions(-)
As a quick side note, it's a good idea to get in the habit of running
the checkpatch.pl script on your patches before submitting as it can
catch a lot of silly things.
% ./scripts/checkpatch.pl -g HEAD
> diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
> index a9de89af8fdc..943dfe7ede83 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_PREFIX_SUFFIX 34 /* prefix/suffix filename transitions */
>
> /* 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_PREFIX_SUFFIX
>
> /* Mask for just the mount related flags */
> #define SE_MNTMASK 0x0f
> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index bd1e7f26d951..562eaa70fb12 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_PREFIX_SUFFIX,
> + .sym_num = SYM_NUM,
> + .ocon_num = OCON_NUM,
> + },
> };
>
> static const struct policydb_compat_info *policydb_lookup_compat(unsigned int version)
> @@ -437,10 +442,33 @@ static const struct hashtab_key_params filenametr_key_params = {
> .cmp = filenametr_cmp,
> };
>
> -struct filename_trans_datum *policydb_filenametr_search(
> - struct policydb *p, struct filename_trans_key *key)
> +/**
> + * policydb_filenametr_search() - Search for filename transition in policy
> + * @p: policydb structure to search in
> + * @match_type: filename transition match type to search for
> + * @key: key to search for
> + * @stype: source type to search for, when stype is zero, the function will
> + * return head of the linked list with matching key, otherwise it will
> + * traverse the linked list to find the item with matching stype
> + *
> + * Return: head of the linked list of filename transition datums or single item
> + * of the list, based on the stype value
> + */
> +struct filename_trans_datum *policydb_filenametr_search(struct policydb *p,
> + unsigned int match_type, struct filename_trans_key *key, u32 stype)
> {
> - return hashtab_search(&p->filename_trans, key, filenametr_key_params);
> + struct filename_trans_datum *datum = hashtab_search(
> + &p->filename_trans[match_type], key, filenametr_key_params);
> +
> + if (stype) {
> + while (datum) {
> + if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
> + return datum;
> + }
> + datum = datum->next;
> + }
> + }
> + return datum;
I'd be curious if this actually changes any of the compiled code, but
you could tweak the above to return an error quicker (and it tends to
fit kernel coding patterns a bit better):
policydb_filenametr_search(...)
{
datum = hashtab_search(...);
if (!datum || !stype)
return datum;
while (datum) {
/* stuff */
}
return datum;
}
> }
>
> static u32 rangetr_hash(const void *k)
> @@ -833,8 +861,10 @@ void policydb_destroy(struct policydb *p)
> }
> kfree(lra);
>
> - hashtab_map(&p->filename_trans, filenametr_destroy, NULL);
> - hashtab_destroy(&p->filename_trans);
> + for (unsigned int i = 0; i < FILENAME_TRANS_MATCH_NUM; i++) {
> + hashtab_map(&p->filename_trans[i], filenametr_destroy, NULL);
> + hashtab_destroy(&p->filename_trans[i]);
> + }
>
> hashtab_map(&p->range_tr, range_tr_destroy, NULL);
> hashtab_destroy(&p->range_tr);
> @@ -1909,7 +1939,9 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
> otype = le32_to_cpu(buf[3]);
>
> last = NULL;
> - datum = policydb_filenametr_search(p, &key);
> + // this version does not support other than exact match
Please only use C-style comments (/* ... */).
> + datum = policydb_filenametr_search(p, FILENAME_TRANS_MATCH_EXACT, &key,
> + 0);
> while (datum) {
> if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
> /* conflicting/duplicate rules are ignored */
> @@ -1939,8 +1971,9 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
> if (!ft)
> goto out;
>
> - rc = hashtab_insert(&p->filename_trans, ft, datum,
> - filenametr_key_params);
> + rc = hashtab_insert(
> + &p->filename_trans[FILENAME_TRANS_MATCH_EXACT],
> + ft, datum, filenametr_key_params);
> if (rc)
> goto out;
> name = NULL;
> @@ -1961,7 +1994,8 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
> return rc;
> }
>
> -static int filename_trans_read_helper(struct policydb *p, void *fp)
> +static int filename_trans_read_helper(struct policydb *p, void *fp,
> + unsigned int match_type)
> {
> struct filename_trans_key *ft = NULL;
> struct filename_trans_datum **dst, *datum, *first = NULL;
> @@ -2028,7 +2062,7 @@ static int filename_trans_read_helper(struct policydb *p, void *fp)
> ft->tclass = tclass;
> ft->name = name;
>
> - rc = hashtab_insert(&p->filename_trans, ft, first,
> + rc = hashtab_insert(&p->filename_trans[match_type], ft, first,
> filenametr_key_params);
> if (rc == -EEXIST)
> pr_err("SELinux: Duplicate filename transition key\n");
> @@ -2050,7 +2084,8 @@ static int filename_trans_read_helper(struct policydb *p, void *fp)
> return rc;
> }
>
> -static int filename_trans_read(struct policydb *p, void *fp)
> +static int filename_trans_read(struct policydb *p, void *fp,
> + unsigned int match_type)
> {
> u32 nel, i;
> __le32 buf[1];
> @@ -2067,27 +2102,28 @@ static int filename_trans_read(struct policydb *p, void *fp)
> if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> p->compat_filename_trans_count = nel;
>
> - rc = hashtab_init(&p->filename_trans, (1 << 11));
> + rc = hashtab_init(&p->filename_trans[match_type], (1 << 11));
> if (rc)
> return rc;
>
> for (i = 0; i < nel; i++) {
> + // this version does not support other than exact match
See my previous comment on comments :)
> rc = filename_trans_read_helper_compat(p, fp);
> if (rc)
> return rc;
> }
> } else {
> - rc = hashtab_init(&p->filename_trans, nel);
> + rc = hashtab_init(&p->filename_trans[match_type], nel);
> if (rc)
> return rc;
>
> for (i = 0; i < nel; i++) {
> - rc = filename_trans_read_helper(p, fp);
> + rc = filename_trans_read_helper(p, fp, match_type);
> if (rc)
> return rc;
> }
> }
> - hash_eval(&p->filename_trans, "filenametr");
> + hash_eval(&p->filename_trans[match_type], "filenametr");
> return 0;
> }
>
> @@ -2636,9 +2672,17 @@ int policydb_read(struct policydb *p, void *fp)
> lra = ra;
> }
>
> - rc = filename_trans_read(p, fp);
> + rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_EXACT);
> if (rc)
> goto bad;
> + if (p->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
> + rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_PREFIX);
> + if (rc)
> + goto bad;
> + rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_SUFFIX);
> + if (rc)
> + goto bad;
> + }
>
> rc = policydb_index(p);
> if (rc)
> @@ -3569,7 +3613,8 @@ static int filename_write_helper(void *key, void *data, void *ptr)
> return 0;
> }
>
> -static int filename_trans_write(struct policydb *p, void *fp)
> +static int filename_trans_write(struct policydb *p, void *fp,
> + unsigned int match_type)
> {
> __le32 buf[1];
> int rc;
> @@ -3583,15 +3628,16 @@ static int filename_trans_write(struct policydb *p, void *fp)
> if (rc)
> return rc;
>
> - rc = hashtab_map(&p->filename_trans,
> + rc = hashtab_map(&p->filename_trans[match_type],
> filename_write_helper_compat, fp);
> } else {
> - buf[0] = cpu_to_le32(p->filename_trans.nel);
> + buf[0] = cpu_to_le32(p->filename_trans[match_type].nel);
> rc = put_entry(buf, sizeof(u32), 1, fp);
> if (rc)
> return rc;
>
> - rc = hashtab_map(&p->filename_trans, filename_write_helper, fp);
> + rc = hashtab_map(&p->filename_trans[match_type],
> + filename_write_helper, fp);
> }
> return rc;
> }
> @@ -3706,9 +3752,17 @@ int policydb_write(struct policydb *p, void *fp)
> if (rc)
> return rc;
>
> - rc = filename_trans_write(p, fp);
> + rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_EXACT);
> if (rc)
> return rc;
> + if (p->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
> + rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_PREFIX);
> + if (rc)
> + return rc;
> + rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_SUFFIX);
> + if (rc)
> + return rc;
> + }
>
> rc = ocontext_write(p, info, fp);
> if (rc)
> diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> index b97cda489753..7bd0ecb8ed69 100644
> --- a/security/selinux/ss/policydb.h
> +++ b/security/selinux/ss/policydb.h
> @@ -235,6 +235,13 @@ struct genfs {
> #define OCON_IBENDPORT 8 /* Infiniband end ports */
> #define OCON_NUM 9
>
> +enum {
> + FILENAME_TRANS_MATCH_EXACT,
> + FILENAME_TRANS_MATCH_PREFIX,
> + FILENAME_TRANS_MATCH_SUFFIX,
> + FILENAME_TRANS_MATCH_NUM,
> +};
Since we are using the enums above as array indices it might be a
good idea to assign them values explicitly, or just use pre-processor
macros instead of enums. The latter might be preferable here.
> /* The policy database */
> struct policydb {
> int mls_enabled;
> @@ -269,7 +276,7 @@ struct policydb {
> /* quickly exclude lookups when parent ttype has no rules */
> struct ebitmap filename_trans_ttypes;
> /* actual set of filename_trans rules */
> - struct hashtab filename_trans;
> + struct hashtab filename_trans[FILENAME_TRANS_MATCH_NUM];
> /* only used if policyvers < POLICYDB_VERSION_COMP_FTRANS */
> u32 compat_filename_trans_count;
>
> @@ -325,7 +332,8 @@ 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);
> + struct policydb *p, unsigned int match_type,
> + struct filename_trans_key *key, u32 stype);
>
> extern struct mls_range *policydb_rangetr_search(
> struct policydb *p, struct range_trans *key);
> diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> index 1eeffc66ea7d..99200a9490a3 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -1661,13 +1661,16 @@ static int compute_sid_handle_invalid_context(
> return -EACCES;
> }
>
> -static void filename_compute_type(struct policydb *policydb,
> +static int 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;
> + size_t name_len = strlen(objname);
Since the @name_len variable isn't used by the MATCH_EXACT search you
should move it below that policydb_filenametr_search() call so we
don't do unnecessary strlen() computations.
> + size_t i;
> + char *name_copy;
>
> /*
> * Most filename trans rules are going to live in specific directories
> @@ -1675,20 +1678,50 @@ static void filename_compute_type(struct policydb *policydb,
> * if the ttype does not contain any rules.
> */
> if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
> - return;
> + return 0;
>
> ft.ttype = ttype;
> ft.tclass = tclass;
> +
> + /* Search for exact rules */
> ft.name = objname;
> + datum = policydb_filenametr_search(policydb, FILENAME_TRANS_MATCH_EXACT,
> + &ft, stype);
> + if (datum) {
> + newcontext->type = datum->otype;
> + return 0;
> + }
>
> - datum = policydb_filenametr_search(policydb, &ft);
> - while (datum) {
> - if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
> + /* Search for prefix rules */
> + name_copy = kstrdup(objname, GFP_ATOMIC);
> + if (!name_copy)
> + return -ENOMEM;
I'd set @name_len here.
> + ft.name = name_copy;
> + for (i = name_len; i > 0; i--) {
I'm not sure if this intentional or not, but the minimum prefix size
here is two characters '(i == 1)' is that intended? Or am I tired and
simply reading the code wrong ;)
Please note that if you adjust this to go down to a single character
you will likely need to switch @i to a 'ssize_t', and 'int', or
something signed.
I'm also wondering if there is some clever way to limit the number of
times we go through this loop. If we tracked and saved the smallest
prefix size when we are loading the policy, I imagine we could use
that to limit the number of loop iterations as there is no sense in
searching below the length of the smallest prefix, right? Thinking
about it some more, the same logic could be applied to the longest
prefix as well. I'm not sure what the test policy looks like with the
prefix and suffic matches, but hopefully that should improve
performance slightly, especially on long filenames.
> + name_copy[i] = '\0';
> + datum = policydb_filenametr_search(policydb,
> + FILENAME_TRANS_MATCH_PREFIX,
> + &ft, stype);
> + if (datum) {
> newcontext->type = datum->otype;
> - return;
> + kfree(name_copy);
> + return 0;
If you initialize @name_copy to NULL and reset it below, you could
simplify things very slightly by making a 'found' jump target at the
end of the function:
found:
kfree(name_copy);
newcontext->type = datum->otype;
return 0;
> }
> - datum = datum->next;
> }
> + kfree(name_copy);
> +
> + /* Search for suffix rules */
> + for (i = 0; i < name_len; i++) {
I believe you should be able to bound the loop iterations here too.
> + ft.name = &objname[i];
> + datum = policydb_filenametr_search(policydb,
> + FILENAME_TRANS_MATCH_SUFFIX,
> + &ft, stype);
> + if (datum) {
> + newcontext->type = datum->otype;
> + return 0;
> + }
> + }
> + return 0;
> }
>
> static int security_compute_sid(u32 ssid,
> @@ -1833,9 +1866,13 @@ static int security_compute_sid(u32 ssid,
> }
>
> /* 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);
> + if (objname) {
> + rc = filename_compute_type(policydb, &newcontext,
> + scontext->type, tcontext->type,
> + tclass, objname);
> + if (rc)
> + goto out_unlock;
> + }
>
> /* Check for class-specific changes. */
> if (specified & AVTAB_TRANSITION) {
> --
> 2.42.0
--
paul-moore.com
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v4] selinux: add prefix/suffix matching to filename type transitions
2023-12-06 3:18 ` Paul Moore
@ 2023-12-20 12:20 ` Juraj Marcin
2023-12-22 22:46 ` Paul Moore
0 siblings, 1 reply; 10+ messages in thread
From: Juraj Marcin @ 2023-12-20 12:20 UTC (permalink / raw
To: Paul Moore; +Cc: Stephen Smalley, selinux, Ondrej Mosnacek
On 2023-12-05 22:18, Paul Moore wrote:
> On Nov 21, 2023 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.
> >
> > This patch changes the filename transition table in the policydb
> > structure into an array of three tables, where the index determines the
> > match type for the rules contained (extract, prefix, and suffix match).
> > Then the patch extends the functions that access the table through the
> > policydb structure to accompany this change while reusing the majority
> > of the old filename transitions code.
> >
> > This patch also updates the code responsible for finding the right
> > filename transition based on the context and the name. The rules have
> > the following order of prioriy, if no matching rule is found, the code
> > moves on to the next category:
> > - exact filename transitions,
> > - prefix filename transitions in the order of the longest prefix match,
> > - suffix filename transitions in the order of the longest suffix match.
> > This ensures the compatibility with older policies.
> >
> > Without prefix/suffix rules in the policy, this patch has no impact on
> > performance or policy loading times. Moreover, with prefix/suffix rules,
> > the overall number of filename transitions can be reduced, which results
> > in smaller binary policy size and therefore also slightly lower load
> > time and memory usage.
> >
> > Performance tests:
> >
> > 1: Reference kernel (f5bbdeda34c63), Fedora policy (format v33)
> > 2: This patch, Fedora policy (format v33)
> > 3: This patch, Fedora policy without prefix/suffix rules (format v34)
> > 4: This patch, Fefora policy with prefix rules (format v35)
> >
> > | Mem | Binary | Policy | Create tty [1] | osbench [2]
> > | Usage | policy | load | | create
> > | | size | time | (ms/file) | files
> > | (MiB) | (KiB) | (ms) | real | kernel | (us/file)
> > ---+--------+--------+---------+----------+-----------+-----------
> > 1 | 298.7 | 3682 | 58.626 | 1.0228 | 0.6793 | 8.4916
> > | sd=4.1 | | sd=0.47 | sd=0.058 | sd=0.0497 | sd=0.131
> > 2 | 296.3 | 3682 | 58.915 | 1.0209 | 0.6752 | 8.5728
> > | sd=3.9 | | sd=0.28 | sd=0.021 | sd=0.0244 | sd=0.156
> > 3 | 295.7 | 3682 | 56.374 | 1.0160 | 0.6616 | 8.7467
> > | sd=2.6 | | sd=0.44 | sd=0.008 | sd=0.0141 | sd=0.126
> > 4 | 296.2 | 2585 | 51.434 | 1.0116 | 0.6699 | 8.7467
> > | sd=4.1 | | sd=0.39 | sd=0.012 | sd=0.0115 | sd=0.126
> >
> > [1] 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.
> >
> > [2] https://github.com/mbitsnbites/osbench
>
> Hi Juraj, first I want to thank you for your continued persistence on
> this patch, I know this has likely been a lot of work. However, I am
> a little concerned about the osbench test results. The policy size
> and load time improvements are really nice to see but I worry that
> those wins might be overshadowed by the runtime performance impacts.
>
> I did see some things which I think might improve that slightly, more
> on that below ...
>
Hi Paul
thank you for your valuable feedback. I will incorporate your
suggestions to my code. I will then report back with benchmark results
with included optimizations. I suspect, kstrdup() in
filename_compute_type() might also be part of the reason, the patched
kernel is few tenths of microsecond slower, so I will also look into
that.
> > Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
> > Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> > Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
> > ---
> > v4:
> > - rebased to the latest pcmoore/selinux/next
> > - fixed non-atomic allocation in atomic section
> > ---
> > v3:
> > - reworked the solution from scratch, this time only adding the
> > prefix/suffix matching feature without moving filename transition
> > rules to the avtab
> > ---
> > security/selinux/include/security.h | 3 +-
> > security/selinux/ss/policydb.c | 96 ++++++++++++++++++++++-------
> > security/selinux/ss/policydb.h | 12 +++-
> > security/selinux/ss/services.c | 57 ++++++++++++++---
> > 4 files changed, 134 insertions(+), 34 deletions(-)
>
> As a quick side note, it's a good idea to get in the habit of running
> the checkpatch.pl script on your patches before submitting as it can
> catch a lot of silly things.
>
> % ./scripts/checkpatch.pl -g HEAD
>
> > diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
> > index a9de89af8fdc..943dfe7ede83 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_PREFIX_SUFFIX 34 /* prefix/suffix filename transitions */
> >
> > /* 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_PREFIX_SUFFIX
> >
> > /* Mask for just the mount related flags */
> > #define SE_MNTMASK 0x0f
> > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > index bd1e7f26d951..562eaa70fb12 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_PREFIX_SUFFIX,
> > + .sym_num = SYM_NUM,
> > + .ocon_num = OCON_NUM,
> > + },
> > };
> >
> > static const struct policydb_compat_info *policydb_lookup_compat(unsigned int version)
> > @@ -437,10 +442,33 @@ static const struct hashtab_key_params filenametr_key_params = {
> > .cmp = filenametr_cmp,
> > };
> >
> > -struct filename_trans_datum *policydb_filenametr_search(
> > - struct policydb *p, struct filename_trans_key *key)
> > +/**
> > + * policydb_filenametr_search() - Search for filename transition in policy
> > + * @p: policydb structure to search in
> > + * @match_type: filename transition match type to search for
> > + * @key: key to search for
> > + * @stype: source type to search for, when stype is zero, the function will
> > + * return head of the linked list with matching key, otherwise it will
> > + * traverse the linked list to find the item with matching stype
> > + *
> > + * Return: head of the linked list of filename transition datums or single item
> > + * of the list, based on the stype value
> > + */
> > +struct filename_trans_datum *policydb_filenametr_search(struct policydb *p,
> > + unsigned int match_type, struct filename_trans_key *key, u32 stype)
> > {
> > - return hashtab_search(&p->filename_trans, key, filenametr_key_params);
> > + struct filename_trans_datum *datum = hashtab_search(
> > + &p->filename_trans[match_type], key, filenametr_key_params);
> > +
> > + if (stype) {
> > + while (datum) {
> > + if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
> > + return datum;
> > + }
> > + datum = datum->next;
> > + }
> > + }
> > + return datum;
>
> I'd be curious if this actually changes any of the compiled code, but
> you could tweak the above to return an error quicker (and it tends to
> fit kernel coding patterns a bit better):
>
> policydb_filenametr_search(...)
> {
> datum = hashtab_search(...);
> if (!datum || !stype)
> return datum;
> while (datum) {
> /* stuff */
> }
> return datum;
> }
>
> > }
> >
> > static u32 rangetr_hash(const void *k)
> > @@ -833,8 +861,10 @@ void policydb_destroy(struct policydb *p)
> > }
> > kfree(lra);
> >
> > - hashtab_map(&p->filename_trans, filenametr_destroy, NULL);
> > - hashtab_destroy(&p->filename_trans);
> > + for (unsigned int i = 0; i < FILENAME_TRANS_MATCH_NUM; i++) {
> > + hashtab_map(&p->filename_trans[i], filenametr_destroy, NULL);
> > + hashtab_destroy(&p->filename_trans[i]);
> > + }
> >
> > hashtab_map(&p->range_tr, range_tr_destroy, NULL);
> > hashtab_destroy(&p->range_tr);
> > @@ -1909,7 +1939,9 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
> > otype = le32_to_cpu(buf[3]);
> >
> > last = NULL;
> > - datum = policydb_filenametr_search(p, &key);
> > + // this version does not support other than exact match
>
> Please only use C-style comments (/* ... */).
>
> > + datum = policydb_filenametr_search(p, FILENAME_TRANS_MATCH_EXACT, &key,
> > + 0);
> > while (datum) {
> > if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
> > /* conflicting/duplicate rules are ignored */
> > @@ -1939,8 +1971,9 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
> > if (!ft)
> > goto out;
> >
> > - rc = hashtab_insert(&p->filename_trans, ft, datum,
> > - filenametr_key_params);
> > + rc = hashtab_insert(
> > + &p->filename_trans[FILENAME_TRANS_MATCH_EXACT],
> > + ft, datum, filenametr_key_params);
> > if (rc)
> > goto out;
> > name = NULL;
> > @@ -1961,7 +1994,8 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
> > return rc;
> > }
> >
> > -static int filename_trans_read_helper(struct policydb *p, void *fp)
> > +static int filename_trans_read_helper(struct policydb *p, void *fp,
> > + unsigned int match_type)
> > {
> > struct filename_trans_key *ft = NULL;
> > struct filename_trans_datum **dst, *datum, *first = NULL;
> > @@ -2028,7 +2062,7 @@ static int filename_trans_read_helper(struct policydb *p, void *fp)
> > ft->tclass = tclass;
> > ft->name = name;
> >
> > - rc = hashtab_insert(&p->filename_trans, ft, first,
> > + rc = hashtab_insert(&p->filename_trans[match_type], ft, first,
> > filenametr_key_params);
> > if (rc == -EEXIST)
> > pr_err("SELinux: Duplicate filename transition key\n");
> > @@ -2050,7 +2084,8 @@ static int filename_trans_read_helper(struct policydb *p, void *fp)
> > return rc;
> > }
> >
> > -static int filename_trans_read(struct policydb *p, void *fp)
> > +static int filename_trans_read(struct policydb *p, void *fp,
> > + unsigned int match_type)
> > {
> > u32 nel, i;
> > __le32 buf[1];
> > @@ -2067,27 +2102,28 @@ static int filename_trans_read(struct policydb *p, void *fp)
> > if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
> > p->compat_filename_trans_count = nel;
> >
> > - rc = hashtab_init(&p->filename_trans, (1 << 11));
> > + rc = hashtab_init(&p->filename_trans[match_type], (1 << 11));
> > if (rc)
> > return rc;
> >
> > for (i = 0; i < nel; i++) {
> > + // this version does not support other than exact match
>
> See my previous comment on comments :)
>
> > rc = filename_trans_read_helper_compat(p, fp);
> > if (rc)
> > return rc;
> > }
> > } else {
> > - rc = hashtab_init(&p->filename_trans, nel);
> > + rc = hashtab_init(&p->filename_trans[match_type], nel);
> > if (rc)
> > return rc;
> >
> > for (i = 0; i < nel; i++) {
> > - rc = filename_trans_read_helper(p, fp);
> > + rc = filename_trans_read_helper(p, fp, match_type);
> > if (rc)
> > return rc;
> > }
> > }
> > - hash_eval(&p->filename_trans, "filenametr");
> > + hash_eval(&p->filename_trans[match_type], "filenametr");
> > return 0;
> > }
> >
> > @@ -2636,9 +2672,17 @@ int policydb_read(struct policydb *p, void *fp)
> > lra = ra;
> > }
> >
> > - rc = filename_trans_read(p, fp);
> > + rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_EXACT);
> > if (rc)
> > goto bad;
> > + if (p->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
> > + rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_PREFIX);
> > + if (rc)
> > + goto bad;
> > + rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_SUFFIX);
> > + if (rc)
> > + goto bad;
> > + }
> >
> > rc = policydb_index(p);
> > if (rc)
> > @@ -3569,7 +3613,8 @@ static int filename_write_helper(void *key, void *data, void *ptr)
> > return 0;
> > }
> >
> > -static int filename_trans_write(struct policydb *p, void *fp)
> > +static int filename_trans_write(struct policydb *p, void *fp,
> > + unsigned int match_type)
> > {
> > __le32 buf[1];
> > int rc;
> > @@ -3583,15 +3628,16 @@ static int filename_trans_write(struct policydb *p, void *fp)
> > if (rc)
> > return rc;
> >
> > - rc = hashtab_map(&p->filename_trans,
> > + rc = hashtab_map(&p->filename_trans[match_type],
> > filename_write_helper_compat, fp);
> > } else {
> > - buf[0] = cpu_to_le32(p->filename_trans.nel);
> > + buf[0] = cpu_to_le32(p->filename_trans[match_type].nel);
> > rc = put_entry(buf, sizeof(u32), 1, fp);
> > if (rc)
> > return rc;
> >
> > - rc = hashtab_map(&p->filename_trans, filename_write_helper, fp);
> > + rc = hashtab_map(&p->filename_trans[match_type],
> > + filename_write_helper, fp);
> > }
> > return rc;
> > }
> > @@ -3706,9 +3752,17 @@ int policydb_write(struct policydb *p, void *fp)
> > if (rc)
> > return rc;
> >
> > - rc = filename_trans_write(p, fp);
> > + rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_EXACT);
> > if (rc)
> > return rc;
> > + if (p->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
> > + rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_PREFIX);
> > + if (rc)
> > + return rc;
> > + rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_SUFFIX);
> > + if (rc)
> > + return rc;
> > + }
> >
> > rc = ocontext_write(p, info, fp);
> > if (rc)
> > diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> > index b97cda489753..7bd0ecb8ed69 100644
> > --- a/security/selinux/ss/policydb.h
> > +++ b/security/selinux/ss/policydb.h
> > @@ -235,6 +235,13 @@ struct genfs {
> > #define OCON_IBENDPORT 8 /* Infiniband end ports */
> > #define OCON_NUM 9
> >
> > +enum {
> > + FILENAME_TRANS_MATCH_EXACT,
> > + FILENAME_TRANS_MATCH_PREFIX,
> > + FILENAME_TRANS_MATCH_SUFFIX,
> > + FILENAME_TRANS_MATCH_NUM,
> > +};
>
> Since we are using the enums above as array indices it might be a
> good idea to assign them values explicitly, or just use pre-processor
> macros instead of enums. The latter might be preferable here.
>
> > /* The policy database */
> > struct policydb {
> > int mls_enabled;
> > @@ -269,7 +276,7 @@ struct policydb {
> > /* quickly exclude lookups when parent ttype has no rules */
> > struct ebitmap filename_trans_ttypes;
> > /* actual set of filename_trans rules */
> > - struct hashtab filename_trans;
> > + struct hashtab filename_trans[FILENAME_TRANS_MATCH_NUM];
> > /* only used if policyvers < POLICYDB_VERSION_COMP_FTRANS */
> > u32 compat_filename_trans_count;
> >
> > @@ -325,7 +332,8 @@ 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);
> > + struct policydb *p, unsigned int match_type,
> > + struct filename_trans_key *key, u32 stype);
> >
> > extern struct mls_range *policydb_rangetr_search(
> > struct policydb *p, struct range_trans *key);
> > diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
> > index 1eeffc66ea7d..99200a9490a3 100644
> > --- a/security/selinux/ss/services.c
> > +++ b/security/selinux/ss/services.c
> > @@ -1661,13 +1661,16 @@ static int compute_sid_handle_invalid_context(
> > return -EACCES;
> > }
> >
> > -static void filename_compute_type(struct policydb *policydb,
> > +static int 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;
> > + size_t name_len = strlen(objname);
>
> Since the @name_len variable isn't used by the MATCH_EXACT search you
> should move it below that policydb_filenametr_search() call so we
> don't do unnecessary strlen() computations.
>
> > + size_t i;
> > + char *name_copy;
> >
> > /*
> > * Most filename trans rules are going to live in specific directories
> > @@ -1675,20 +1678,50 @@ static void filename_compute_type(struct policydb *policydb,
> > * if the ttype does not contain any rules.
> > */
> > if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
> > - return;
> > + return 0;
> >
> > ft.ttype = ttype;
> > ft.tclass = tclass;
> > +
> > + /* Search for exact rules */
> > ft.name = objname;
> > + datum = policydb_filenametr_search(policydb, FILENAME_TRANS_MATCH_EXACT,
> > + &ft, stype);
> > + if (datum) {
> > + newcontext->type = datum->otype;
> > + return 0;
> > + }
> >
> > - datum = policydb_filenametr_search(policydb, &ft);
> > - while (datum) {
> > - if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
> > + /* Search for prefix rules */
> > + name_copy = kstrdup(objname, GFP_ATOMIC);
> > + if (!name_copy)
> > + return -ENOMEM;
>
> I'd set @name_len here.
>
> > + ft.name = name_copy;
> > + for (i = name_len; i > 0; i--) {
>
> I'm not sure if this intentional or not, but the minimum prefix size
> here is two characters '(i == 1)' is that intended? Or am I tired and
> simply reading the code wrong ;)
No, the minimum prefix size is actually one character. When `i == 1`,
the byte at index 1 is set to zero, so there is only one character in
the zero-terminated string.
>
> Please note that if you adjust this to go down to a single character
> you will likely need to switch @i to a 'ssize_t', and 'int', or
> something signed.
>
> I'm also wondering if there is some clever way to limit the number of
> times we go through this loop. If we tracked and saved the smallest
> prefix size when we are loading the policy, I imagine we could use
> that to limit the number of loop iterations as there is no sense in
> searching below the length of the smallest prefix, right? Thinking
> about it some more, the same logic could be applied to the longest
> prefix as well. I'm not sure what the test policy looks like with the
> prefix and suffic matches, but hopefully that should improve
> performance slightly, especially on long filenames.
>
> > + name_copy[i] = '\0';
> > + datum = policydb_filenametr_search(policydb,
> > + FILENAME_TRANS_MATCH_PREFIX,
> > + &ft, stype);
> > + if (datum) {
> > newcontext->type = datum->otype;
> > - return;
> > + kfree(name_copy);
> > + return 0;
>
> If you initialize @name_copy to NULL and reset it below, you could
> simplify things very slightly by making a 'found' jump target at the
> end of the function:
>
> found:
> kfree(name_copy);
> newcontext->type = datum->otype;
> return 0;
>
> > }
> > - datum = datum->next;
> > }
> > + kfree(name_copy);
> > +
> > + /* Search for suffix rules */
> > + for (i = 0; i < name_len; i++) {
>
> I believe you should be able to bound the loop iterations here too.
>
> > + ft.name = &objname[i];
> > + datum = policydb_filenametr_search(policydb,
> > + FILENAME_TRANS_MATCH_SUFFIX,
> > + &ft, stype);
> > + if (datum) {
> > + newcontext->type = datum->otype;
> > + return 0;
> > + }
> > + }
> > + return 0;
> > }
> >
> > static int security_compute_sid(u32 ssid,
> > @@ -1833,9 +1866,13 @@ static int security_compute_sid(u32 ssid,
> > }
> >
> > /* 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);
> > + if (objname) {
> > + rc = filename_compute_type(policydb, &newcontext,
> > + scontext->type, tcontext->type,
> > + tclass, objname);
> > + if (rc)
> > + goto out_unlock;
> > + }
> >
> > /* Check for class-specific changes. */
> > if (specified & AVTAB_TRANSITION) {
> > --
> > 2.42.0
>
> --
> paul-moore.com
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v4] selinux: add prefix/suffix matching to filename type transitions
2023-12-20 12:20 ` Juraj Marcin
@ 2023-12-22 22:46 ` Paul Moore
2024-03-01 12:53 ` Juraj Marcin
0 siblings, 1 reply; 10+ messages in thread
From: Paul Moore @ 2023-12-22 22:46 UTC (permalink / raw
To: Juraj Marcin; +Cc: Stephen Smalley, selinux, Ondrej Mosnacek
On Wed, Dec 20, 2023 at 7:21 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
>
> Hi Paul
>
> thank you for your valuable feedback. I will incorporate your
> suggestions to my code. I will then report back with benchmark results
> with included optimizations. I suspect, kstrdup() in
> filename_compute_type() might also be part of the reason, the patched
> kernel is few tenths of microsecond slower, so I will also look into
> that.
Thank you. I did look at the dup'd string for a bit, but didn't see a
relatively quick way to do away with the additional string copy; if
you can come up with something that isn't too ugly I think that would
be great.
--
paul-moore.com
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v4] selinux: add prefix/suffix matching to filename type transitions
2023-12-22 22:46 ` Paul Moore
@ 2024-03-01 12:53 ` Juraj Marcin
2024-03-05 17:04 ` [PATCH v5] " Juraj Marcin
0 siblings, 1 reply; 10+ messages in thread
From: Juraj Marcin @ 2024-03-01 12:53 UTC (permalink / raw
To: Paul Moore; +Cc: Stephen Smalley, selinux, Ondrej Mosnacek
On 2023-12-22 17:46, Paul Moore wrote:
> On Wed, Dec 20, 2023 at 7:21 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
> >
> > Hi Paul
> >
> > thank you for your valuable feedback. I will incorporate your
> > suggestions to my code. I will then report back with benchmark results
> > with included optimizations. I suspect, kstrdup() in
> > filename_compute_type() might also be part of the reason, the patched
> > kernel is few tenths of microsecond slower, so I will also look into
> > that.
>
> Thank you. I did look at the dup'd string for a bit, but didn't see a
> relatively quick way to do away with the additional string copy; if
> you can come up with something that isn't too ugly I think that would
> be great.
Hi,
I am sorry for a late reply, I did not have much time during university
exam period and among other duties.
I have managed to get rid of kstrdup() in filename_compute_type() by
saving the length of the name in the filename transition key structure.
This memory allocation for copy of the string was the reason for the
worse osbench results. Reference kernel (case 1) is always the same
setup, I just benchmarked it again as part of the automation I have for
the comparison. Modified kernel refers to prefix/suffix implementation
with optimizations mentioned above each table.
1: Reference kernel (a1fc79343abb), Fedora policy (format v33)
2: Modified kernel, Fedora policy (format v33)
3: Modified kernel, Fedora policy without prefix/suffix rules (format v34)
4: Modified kernel, Fedora policy with generated prefix rules (format v34)
With iteration limits based on min/max prefix/suffix length
| Mem | Binary | Policy | Create | osbench [2]
| Usage | policy | load | tty [1] | create
| | size | time | | files
| (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
---+-------+--------+---------+-----------+-----------
1 | 407 | 3682 | 47.368 | 2.4376 | 43.9488
| sd=20 | | sd=0.39 | sd=0.050 | sd=0.486
2 | 417 | 3682 | 46.979 | 2.4655 | 44.0856
| sd=17 | | sd=0.32 | sd=0.080 | sd=0.476
3 | 430 | 3682 | 46.892 | 2.4605 | 43.6223
| sd=21 | | sd=0.28 | sd=0.042 | sd=0.374
4 | 417 | 2585 | 42.131 | 2.5331 | 48.7980
| sd=21 | | sd=0.29 | sd=0.041 | sd=0.456
Here, cases 2 and 3 are improved compared to the last patch, as the
kstrdup() is also skipped with no prefix rules loaded. Saving the
min/max prefix/suffix length does not slow down policy load, as cases 2
and 3 are pretty much the same as case 1 (reference kernel).
With iteration limits based on min/max prefix/suffix length and
kdstrup() removal
| Mem | Binary | Policy | Create | osbench [2]
| Usage | policy | load | tty [1] | create
| | size | time | | files
| (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
---+-------+--------+---------+-----------+-----------
1 | 430 | 3682 | 46.930 | 2.4569 | 43.4431
| sd= 8 | | sd=0.25 | sd=0.043 | sd=0.434
2 | 410 | 3682 | 46.829 | 2.4623 | 43.4112
| sd=20 | | sd=0.27 | sd=0.053 | sd=0.442
3 | 419 | 3682 | 46.823 | 2.4257 | 43.0575
| sd=14 | | sd=0.18 | sd=0.057 | sd=0.416
4 | 420 | 2585 | 42.044 | 2.5028 | 43.7907
| sd=10 | | sd=0.19 | sd=0.067 | sd=0.382
From these results, it is apparent that removing the string duplication
is effective optimization, as in all four cases the osbench and tty
create results are close together.
Out of curiosity, I also tested the kstrdup() removal alone, without
other optimizations that were proposed.
| Mem | Binary | Policy | Create | osbench [2]
| Usage | policy | load | tty [1] | create
| | size | time | | files
| (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
---+-------+--------+---------+-----------+-----------
1 | 421 | 3682 | 46.941 | 2.4702 | 43.6063
| sd=21 | | sd=0.23 | sd=0.052 | sd=0.388
2 | 422 | 3682 | 46.736 | 2.4655 | 43.7345
| sd=16 | | sd=0.22 | sd=0.059 | sd=0.516
3 | 425 | 3682 | 46.950 | 2.4445 | 43.6280
| sd=15 | | sd=0.25 | sd=0.045 | sd=0.378
4 | 418 | 2585 | 41.582 | 2.4456 | 43.3526
| sd=18 | | sd=0.14 | sd=0.056 | sd=0.365
It seems that string duplication was the culprit, and additional
searches have no measurable impact in the tested cases. However, as
saving min/max prefix/suffix length has no impact on the policy load
times, it might be a good idea to keep the limiting optimization as it
might help with really long filenames.
Best regards
Juraj Marcin
>
> --
> paul-moore.com
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH v5] selinux: add prefix/suffix matching to filename type transitions
2024-03-01 12:53 ` Juraj Marcin
@ 2024-03-05 17:04 ` Juraj Marcin
2024-03-28 1:22 ` Paul Moore
0 siblings, 1 reply; 10+ messages in thread
From: Juraj Marcin @ 2024-03-05 17:04 UTC (permalink / raw
To: Paul Moore; +Cc: Stephen Smalley, selinux, Ondrej Mosnacek
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.
This patch changes the filename transition table in the policydb
structure into an array of three tables, where the index determines the
match type for the rules contained (extract, prefix, and suffix match).
Then the patch extends the functions that access the table through the
policydb structure to accompany this change while reusing the majority
of the old filename transitions code.
This patch also updates the code responsible for finding the right
filename transition based on the context and the name. The rules have
the following order of priority, if no matching rule is found, the code
moves on to the next category:
- exact filename transitions,
- prefix filename transitions in the order of the longest prefix match,
- suffix filename transitions in the order of the longest suffix match.
This ensures the compatibility with older policies.
Lastly, this patch adds an attribute containing the explicit length of
the name string in the filename transition key to allow using only
prefix of a constant string as key.
Without prefix/suffix rules in the policy, this patch has no impact on
performance or policy loading times. Moreover, with prefix/suffix rules,
the overall number of filename transitions can be reduced, which results
in smaller binary policy size and therefore also slightly lower load
time and memory usage.
Performance tests:
1: Reference kernel (a1fc79343abbd), Fedora policy (format v33)
2: This patch, Fedora policy (format v33)
3: This patch, Fedora policy without prefix/suffix rules (format v34)
4: This patch, Fedora policy with prefix rules (format v35)
| Mem | Binary | Policy | Create | osbench [2]
| Usage | policy | load | tty [1] | create
| | size | time | | files
| (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
---+-------+--------+---------+-----------+-----------
1 | 430 | 3682 | 46.930 | 2.4569 | 43.4431
| sd= 8 | | sd=0.25 | sd=0.043 | sd=0.434
2 | 410 | 3682 | 46.829 | 2.4623 | 43.4112
| sd=20 | | sd=0.27 | sd=0.053 | sd=0.442
3 | 419 | 3682 | 46.823 | 2.4257 | 43.0575
| sd=14 | | sd=0.18 | sd=0.057 | sd=0.416
4 | 420 | 2585 | 42.044 | 2.5028 | 43.7907
| sd=10 | | sd=0.19 | sd=0.067 | sd=0.382
[1] 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.
[2] https://github.com/mbitsnbites/osbench
Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
---
v5:
- rebased to the latest pcmoore/selinux/next
- applied suggestions from Paul Moore
- added limit optimization suggested by Paul Moore
- removed string duplication by using explicit string length in
filename trasition key
---
v4:
- rebased to the latest pcmoore/selinux/next
- fixed non-atomic allocation in atomic section
---
v3:
- reworked the solution from scratch, this time only adding the
prefix/suffix matching feature without moving filename transition
rules to the avtab
---
security/selinux/include/security.h | 4 +-
security/selinux/ss/policydb.c | 132 ++++++++++++++++++++++------
security/selinux/ss/policydb.h | 14 ++-
security/selinux/ss/services.c | 72 ++++++++++++---
4 files changed, 178 insertions(+), 44 deletions(-)
diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
index 289bf9233f714..49a043633173c 100644
--- a/security/selinux/include/security.h
+++ b/security/selinux/include/security.h
@@ -46,10 +46,12 @@
#define POLICYDB_VERSION_INFINIBAND 31
#define POLICYDB_VERSION_GLBLUB 32
#define POLICYDB_VERSION_COMP_FTRANS 33 /* compressed filename transitions */
+#define POLICYDB_VERSION_COMP_FTRANS 33 /* compressed filename transitions */
+#define POLICYDB_VERSION_PREFIX_SUFFIX 34 /* prefix/suffix filename transitions */
/* 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_PREFIX_SUFFIX
/* Mask for just the mount related flags */
#define SE_MNTMASK 0x0f
diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
index 3d22d5baa829b..5de22ba840673 100644
--- a/security/selinux/ss/policydb.c
+++ b/security/selinux/ss/policydb.c
@@ -155,6 +155,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 *
@@ -412,7 +417,7 @@ static u32 filenametr_hash(const void *k)
const struct filename_trans_key *ft = k;
unsigned long salt = ft->ttype ^ ft->tclass;
- return full_name_hash((void *)salt, ft->name, strlen(ft->name));
+ return full_name_hash((void *)salt, ft->name, ft->name_len);
}
static int filenametr_cmp(const void *k1, const void *k2)
@@ -429,7 +434,11 @@ static int filenametr_cmp(const void *k1, const void *k2)
if (v)
return v;
- return strcmp(ft1->name, ft2->name);
+ v = strncmp(ft1->name, ft2->name, min(ft1->name_len, ft2->name_len));
+ if (ft1->name_len == ft2->name_len || v)
+ return v;
+ /* if one name is prefix of the other, the longer is greater */
+ return (int)ft1->name_len - (int)ft2->name_len;
}
static const struct hashtab_key_params filenametr_key_params = {
@@ -437,10 +446,34 @@ static const struct hashtab_key_params filenametr_key_params = {
.cmp = filenametr_cmp,
};
+/**
+ * policydb_filenametr_search() - Search for filename transition in policy
+ * @p: policydb structure to search in
+ * @match_type: filename transition match type to search for
+ * @key: key to search for
+ * @stype: source type to search for, when stype is zero, the function will
+ * return head of the linked list with matching key, otherwise it will
+ * traverse the linked list to find the item with matching stype
+ *
+ * Return: head of the linked list of filename transition datums or single item
+ * of the list, based on the stype value
+ */
struct filename_trans_datum *
-policydb_filenametr_search(struct policydb *p, struct filename_trans_key *key)
+policydb_filenametr_search(struct policydb *p, unsigned int match_type,
+ struct filename_trans_key *key, u32 stype)
{
- return hashtab_search(&p->filename_trans, key, filenametr_key_params);
+ struct filename_trans_datum *datum = hashtab_search(
+ &p->filename_trans[match_type], key, filenametr_key_params);
+ if (!datum || !stype)
+ return datum;
+
+ while (datum) {
+ if (ebitmap_get_bit(&datum->stypes, stype - 1))
+ return datum;
+
+ datum = datum->next;
+ }
+ return datum;
}
static u32 rangetr_hash(const void *k)
@@ -520,6 +553,7 @@ struct role_trans_datum *policydb_roletr_search(struct policydb *p,
*/
static void policydb_init(struct policydb *p)
{
+ size_t i;
memset(p, 0, sizeof(*p));
avtab_init(&p->te_avtab);
@@ -528,6 +562,9 @@ static void policydb_init(struct policydb *p)
ebitmap_init(&p->filename_trans_ttypes);
ebitmap_init(&p->policycaps);
ebitmap_init(&p->permissive_map);
+
+ for (i = 0; i < FILENAME_TRANS_MATCH_NUM; i++)
+ p->filename_trans_name_min[i] = U32_MAX;
}
/*
@@ -831,8 +868,10 @@ void policydb_destroy(struct policydb *p)
}
kfree(lra);
- hashtab_map(&p->filename_trans, filenametr_destroy, NULL);
- hashtab_destroy(&p->filename_trans);
+ for (unsigned int i = 0; i < FILENAME_TRANS_MATCH_NUM; i++) {
+ hashtab_map(&p->filename_trans[i], filenametr_destroy, NULL);
+ hashtab_destroy(&p->filename_trans[i]);
+ }
hashtab_map(&p->range_tr, range_tr_destroy, NULL);
hashtab_destroy(&p->range_tr);
@@ -1934,11 +1973,17 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
key.ttype = le32_to_cpu(buf[1]);
key.tclass = le32_to_cpu(buf[2]);
key.name = name;
+ key.name_len = len;
otype = le32_to_cpu(buf[3]);
last = NULL;
- datum = policydb_filenametr_search(p, &key);
+ /*
+ * this version does not support other than exact match,
+ * therefore there is also no need to save name max/min
+ */
+ datum = policydb_filenametr_search(p, FILENAME_TRANS_MATCH_EXACT, &key,
+ 0);
while (datum) {
if (unlikely(ebitmap_get_bit(&datum->stypes, stype - 1))) {
/* conflicting/duplicate rules are ignored */
@@ -1968,8 +2013,9 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
if (!ft)
goto out;
- rc = hashtab_insert(&p->filename_trans, ft, datum,
- filenametr_key_params);
+ rc = hashtab_insert(
+ &p->filename_trans[FILENAME_TRANS_MATCH_EXACT],
+ ft, datum, filenametr_key_params);
if (rc)
goto out;
name = NULL;
@@ -1990,7 +2036,8 @@ static int filename_trans_read_helper_compat(struct policydb *p, void *fp)
return rc;
}
-static int filename_trans_read_helper(struct policydb *p, void *fp)
+static int filename_trans_read_helper(struct policydb *p, void *fp,
+ unsigned int match_type)
{
struct filename_trans_key *ft = NULL;
struct filename_trans_datum **dst, *datum, *first = NULL;
@@ -2010,6 +2057,12 @@ static int filename_trans_read_helper(struct policydb *p, void *fp)
if (rc)
return rc;
+ /* save name len to limit prefix/suffix lookups later */
+ if (len > p->filename_trans_name_max[match_type])
+ p->filename_trans_name_max[match_type] = len;
+ if (len < p->filename_trans_name_min[match_type])
+ p->filename_trans_name_min[match_type] = len;
+
rc = next_entry(buf, fp, sizeof(u32) * 3);
if (rc)
goto out;
@@ -2056,8 +2109,9 @@ static int filename_trans_read_helper(struct policydb *p, void *fp)
ft->ttype = ttype;
ft->tclass = tclass;
ft->name = name;
+ ft->name_len = len;
- rc = hashtab_insert(&p->filename_trans, ft, first,
+ rc = hashtab_insert(&p->filename_trans[match_type], ft, first,
filenametr_key_params);
if (rc == -EEXIST)
pr_err("SELinux: Duplicate filename transition key\n");
@@ -2079,7 +2133,8 @@ static int filename_trans_read_helper(struct policydb *p, void *fp)
return rc;
}
-static int filename_trans_read(struct policydb *p, void *fp)
+static int filename_trans_read(struct policydb *p, void *fp,
+ unsigned int match_type)
{
u32 nel, i;
__le32 buf[1];
@@ -2096,27 +2151,30 @@ static int filename_trans_read(struct policydb *p, void *fp)
if (p->policyvers < POLICYDB_VERSION_COMP_FTRANS) {
p->compat_filename_trans_count = nel;
- rc = hashtab_init(&p->filename_trans, (1 << 11));
+ rc = hashtab_init(&p->filename_trans[match_type], (1 << 11));
if (rc)
return rc;
for (i = 0; i < nel; i++) {
+ /*
+ * this version does not support other than exact match
+ */
rc = filename_trans_read_helper_compat(p, fp);
if (rc)
return rc;
}
} else {
- rc = hashtab_init(&p->filename_trans, nel);
+ rc = hashtab_init(&p->filename_trans[match_type], nel);
if (rc)
return rc;
for (i = 0; i < nel; i++) {
- rc = filename_trans_read_helper(p, fp);
+ rc = filename_trans_read_helper(p, fp, match_type);
if (rc)
return rc;
}
}
- hash_eval(&p->filename_trans, "filenametr");
+ hash_eval(&p->filename_trans[match_type], "filenametr");
return 0;
}
@@ -2676,9 +2734,17 @@ int policydb_read(struct policydb *p, void *fp)
lra = ra;
}
- rc = filename_trans_read(p, fp);
+ rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_EXACT);
if (rc)
goto bad;
+ if (p->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
+ rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_PREFIX);
+ if (rc)
+ goto bad;
+ rc = filename_trans_read(p, fp, FILENAME_TRANS_MATCH_SUFFIX);
+ if (rc)
+ goto bad;
+ }
rc = policydb_index(p);
if (rc)
@@ -3537,17 +3603,17 @@ static int filename_write_helper_compat(void *key, void *data, void *ptr)
void *fp = ptr;
__le32 buf[4];
int rc;
- u32 bit, len = strlen(ft->name);
+ u32 bit;
do {
ebitmap_for_each_positive_bit(&datum->stypes, node, bit)
{
- buf[0] = cpu_to_le32(len);
+ buf[0] = cpu_to_le32(ft->name_len);
rc = put_entry(buf, sizeof(u32), 1, fp);
if (rc)
return rc;
- rc = put_entry(ft->name, sizeof(char), len, fp);
+ rc = put_entry(ft->name, sizeof(char), ft->name_len, fp);
if (rc)
return rc;
@@ -3574,14 +3640,14 @@ static int filename_write_helper(void *key, void *data, void *ptr)
void *fp = ptr;
__le32 buf[3];
int rc;
- u32 ndatum, len = strlen(ft->name);
+ u32 ndatum;
- buf[0] = cpu_to_le32(len);
+ buf[0] = cpu_to_le32(ft->name_len);
rc = put_entry(buf, sizeof(u32), 1, fp);
if (rc)
return rc;
- rc = put_entry(ft->name, sizeof(char), len, fp);
+ rc = put_entry(ft->name, sizeof(char), ft->name_len, fp);
if (rc)
return rc;
@@ -3616,7 +3682,8 @@ static int filename_write_helper(void *key, void *data, void *ptr)
return 0;
}
-static int filename_trans_write(struct policydb *p, void *fp)
+static int filename_trans_write(struct policydb *p, void *fp,
+ unsigned int match_type)
{
__le32 buf[1];
int rc;
@@ -3630,15 +3697,16 @@ static int filename_trans_write(struct policydb *p, void *fp)
if (rc)
return rc;
- rc = hashtab_map(&p->filename_trans,
+ rc = hashtab_map(&p->filename_trans[match_type],
filename_write_helper_compat, fp);
} else {
- buf[0] = cpu_to_le32(p->filename_trans.nel);
+ buf[0] = cpu_to_le32(p->filename_trans[match_type].nel);
rc = put_entry(buf, sizeof(u32), 1, fp);
if (rc)
return rc;
- rc = hashtab_map(&p->filename_trans, filename_write_helper, fp);
+ rc = hashtab_map(&p->filename_trans[match_type],
+ filename_write_helper, fp);
}
return rc;
}
@@ -3754,9 +3822,17 @@ int policydb_write(struct policydb *p, void *fp)
if (rc)
return rc;
- rc = filename_trans_write(p, fp);
+ rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_EXACT);
if (rc)
return rc;
+ if (p->policyvers >= POLICYDB_VERSION_PREFIX_SUFFIX) {
+ rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_PREFIX);
+ if (rc)
+ return rc;
+ rc = filename_trans_write(p, fp, FILENAME_TRANS_MATCH_SUFFIX);
+ if (rc)
+ return rc;
+ }
rc = ocontext_write(p, info, fp);
if (rc)
diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
index 4bba386264a3d..78abb959e7205 100644
--- a/security/selinux/ss/policydb.h
+++ b/security/selinux/ss/policydb.h
@@ -93,6 +93,7 @@ struct filename_trans_key {
u32 ttype; /* parent dir context */
u16 tclass; /* class of new object */
const char *name; /* last path component */
+ u32 name_len; /* length of the last path component */
};
struct filename_trans_datum {
@@ -232,6 +233,11 @@ struct genfs {
#define OCON_IBENDPORT 8 /* Infiniband end ports */
#define OCON_NUM 9
+#define FILENAME_TRANS_MATCH_EXACT 0
+#define FILENAME_TRANS_MATCH_PREFIX 1
+#define FILENAME_TRANS_MATCH_SUFFIX 2
+#define FILENAME_TRANS_MATCH_NUM 3
+
/* The policy database */
struct policydb {
int mls_enabled;
@@ -266,9 +272,12 @@ struct policydb {
/* quickly exclude lookups when parent ttype has no rules */
struct ebitmap filename_trans_ttypes;
/* actual set of filename_trans rules */
- struct hashtab filename_trans;
+ struct hashtab filename_trans[FILENAME_TRANS_MATCH_NUM];
/* only used if policyvers < POLICYDB_VERSION_COMP_FTRANS */
u32 compat_filename_trans_count;
+ /* lenghts of prefix/suffix rules to optimze for long filenames */
+ u32 filename_trans_name_max[FILENAME_TRANS_MATCH_NUM];
+ u32 filename_trans_name_min[FILENAME_TRANS_MATCH_NUM];
/* bools indexed by (value - 1) */
struct cond_bool_datum **bool_val_to_struct;
@@ -322,7 +331,8 @@ 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);
+policydb_filenametr_search(struct policydb *p, unsigned int match_type,
+ struct filename_trans_key *key, u32 stype);
extern struct mls_range *policydb_rangetr_search(struct policydb *p,
struct range_trans *key);
diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index e88b1b6c4adbb..e142c6bdfe2ed 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1672,13 +1672,20 @@ static int compute_sid_handle_invalid_context(
return -EACCES;
}
-static void filename_compute_type(struct policydb *policydb,
+static int 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;
+ size_t prefix_len;
+ size_t suffix_len;
+ size_t prefix_max;
+ size_t suffix_max;
+ size_t prefix_min;
+ size_t suffix_min;
+ size_t objname_len = strlen(objname);
/*
* Most filename trans rules are going to live in specific directories
@@ -1686,20 +1693,55 @@ static void filename_compute_type(struct policydb *policydb,
* if the ttype does not contain any rules.
*/
if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
- return;
+ return 0;
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;
+ ft.name_len = objname_len;
+
+ /* Search for exact rules */
+ datum = policydb_filenametr_search(policydb, FILENAME_TRANS_MATCH_EXACT,
+ &ft, stype);
+ if (datum)
+ goto found;
+
+ /* Search for prefix rules */
+ prefix_max = min(
+ objname_len,
+ policydb->filename_trans_name_max[FILENAME_TRANS_MATCH_PREFIX]);
+ prefix_min =
+ policydb->filename_trans_name_min[FILENAME_TRANS_MATCH_PREFIX];
+ /* filename rule with name length 0 is invalid */
+ for (prefix_len = prefix_max; prefix_len >= prefix_min; prefix_len--) {
+ ft.name_len = prefix_len;
+ datum = policydb_filenametr_search(policydb,
+ FILENAME_TRANS_MATCH_PREFIX,
+ &ft, stype);
+ if (datum)
+ goto found;
+ }
+
+ /* Search for suffix rules */
+ suffix_max = min(
+ objname_len,
+ policydb->filename_trans_name_max[FILENAME_TRANS_MATCH_SUFFIX]);
+ suffix_min =
+ policydb->filename_trans_name_min[FILENAME_TRANS_MATCH_SUFFIX];
+ for (suffix_len = suffix_max; suffix_len >= suffix_min; suffix_len--) {
+ ft.name = &objname[objname_len - suffix_len];
+ ft.name_len = suffix_len;
+ datum = policydb_filenametr_search(policydb,
+ FILENAME_TRANS_MATCH_SUFFIX,
+ &ft, stype);
+ if (datum)
+ goto found;
}
+ return 0;
+
+found:
+ newcontext->type = datum->otype;
+ return 0;
}
static int security_compute_sid(u32 ssid,
@@ -1844,9 +1886,13 @@ static int security_compute_sid(u32 ssid,
}
/* 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);
+ if (objname) {
+ rc = filename_compute_type(policydb, &newcontext,
+ scontext->type, tcontext->type,
+ tclass, objname);
+ if (rc)
+ goto out_unlock;
+ }
/* Check for class-specific changes. */
if (specified & AVTAB_TRANSITION) {
--
2.43.0
^ permalink raw reply related [flat|nested] 10+ messages in thread
* Re: [PATCH v5] selinux: add prefix/suffix matching to filename type transitions
2024-03-05 17:04 ` [PATCH v5] " Juraj Marcin
@ 2024-03-28 1:22 ` Paul Moore
2024-04-02 15:35 ` Juraj Marcin
0 siblings, 1 reply; 10+ messages in thread
From: Paul Moore @ 2024-03-28 1:22 UTC (permalink / raw
To: Juraj Marcin; +Cc: Stephen Smalley, selinux, Ondrej Mosnacek
On Mar 5, 2024 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.
>
> This patch changes the filename transition table in the policydb
> structure into an array of three tables, where the index determines the
> match type for the rules contained (extract, prefix, and suffix match).
> Then the patch extends the functions that access the table through the
> policydb structure to accompany this change while reusing the majority
> of the old filename transitions code.
>
> This patch also updates the code responsible for finding the right
> filename transition based on the context and the name. The rules have
> the following order of priority, if no matching rule is found, the code
> moves on to the next category:
> - exact filename transitions,
> - prefix filename transitions in the order of the longest prefix match,
> - suffix filename transitions in the order of the longest suffix match.
> This ensures the compatibility with older policies.
>
> Lastly, this patch adds an attribute containing the explicit length of
> the name string in the filename transition key to allow using only
> prefix of a constant string as key.
>
> Without prefix/suffix rules in the policy, this patch has no impact on
> performance or policy loading times. Moreover, with prefix/suffix rules,
> the overall number of filename transitions can be reduced, which results
> in smaller binary policy size and therefore also slightly lower load
> time and memory usage.
>
> Performance tests:
>
> 1: Reference kernel (a1fc79343abbd), Fedora policy (format v33)
> 2: This patch, Fedora policy (format v33)
> 3: This patch, Fedora policy without prefix/suffix rules (format v34)
> 4: This patch, Fedora policy with prefix rules (format v35)
I think #4 also uses policy format v34, right?
> | Mem | Binary | Policy | Create | osbench [2]
> | Usage | policy | load | tty [1] | create
> | | size | time | | files
> | (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
> ---+-------+--------+---------+-----------+-----------
> 1 | 430 | 3682 | 46.930 | 2.4569 | 43.4431
> | sd= 8 | | sd=0.25 | sd=0.043 | sd=0.434
> 2 | 410 | 3682 | 46.829 | 2.4623 | 43.4112
> | sd=20 | | sd=0.27 | sd=0.053 | sd=0.442
> 3 | 419 | 3682 | 46.823 | 2.4257 | 43.0575
> | sd=14 | | sd=0.18 | sd=0.057 | sd=0.416
> 4 | 420 | 2585 | 42.044 | 2.5028 | 43.7907
> | sd=10 | | sd=0.19 | sd=0.067 | sd=0.382
Thanks for the updated patchset :)
I like the improvements in #2 and #3, with only one test being slightly
worse than #1, I think we're okay there. However, it looks like there
has been a regression in #4 in terms of runtime performance ... hmmm.
> [1] 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.
>
> [2] https://github.com/mbitsnbites/osbench
>
> Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
Unless Ondrej has specifically reviewed v5, I think we need to drop
his Reviewed-by tag as there have been some significant changes since
he reviewed it last.
> Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> ---
> v5:
> - rebased to the latest pcmoore/selinux/next
> - applied suggestions from Paul Moore
> - added limit optimization suggested by Paul Moore
> - removed string duplication by using explicit string length in
> filename trasition key
> ---
> v4:
> - rebased to the latest pcmoore/selinux/next
> - fixed non-atomic allocation in atomic section
> ---
> v3:
> - reworked the solution from scratch, this time only adding the
> prefix/suffix matching feature without moving filename transition
> rules to the avtab
> ---
> security/selinux/include/security.h | 4 +-
> security/selinux/ss/policydb.c | 132 ++++++++++++++++++++++------
> security/selinux/ss/policydb.h | 14 ++-
> security/selinux/ss/services.c | 72 ++++++++++++---
> 4 files changed, 178 insertions(+), 44 deletions(-)
>
> diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
> index 289bf9233f714..49a043633173c 100644
> --- a/security/selinux/include/security.h
> +++ b/security/selinux/include/security.h
> @@ -46,10 +46,12 @@
> #define POLICYDB_VERSION_INFINIBAND 31
> #define POLICYDB_VERSION_GLBLUB 32
> #define POLICYDB_VERSION_COMP_FTRANS 33 /* compressed filename transitions */
> +#define POLICYDB_VERSION_COMP_FTRANS 33 /* compressed filename transitions */
I think one #define should be enough ;)
> +#define POLICYDB_VERSION_PREFIX_SUFFIX 34 /* prefix/suffix filename transitions */
>
> /* 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_PREFIX_SUFFIX
>
> /* Mask for just the mount related flags */
> #define SE_MNTMASK 0x0f
> diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> index 3d22d5baa829b..5de22ba840673 100644
> --- a/security/selinux/ss/policydb.c
> +++ b/security/selinux/ss/policydb.c
> @@ -429,7 +434,11 @@ static int filenametr_cmp(const void *k1, const void *k2)
> if (v)
> return v;
>
> - return strcmp(ft1->name, ft2->name);
> + v = strncmp(ft1->name, ft2->name, min(ft1->name_len, ft2->name_len));
> + if (ft1->name_len == ft2->name_len || v)
> + return v;
> + /* if one name is prefix of the other, the longer is greater */
> + return (int)ft1->name_len - (int)ft2->name_len;
> }
I'm probably missing some subtlety in the code above, but I think we
might be able to optimize this a bit more:
if (ft1->name_len != ft2->name_len)
return (int)ft1->name_len - (int)ft2->name_len;
return strcmp(ft1->name, ft2->name);
I expect being able to avoid a string comparison in some cases should
result in a small performance bump.
> @@ -437,10 +446,34 @@ static const struct hashtab_key_params filenametr_key_params = {
> .cmp = filenametr_cmp,
> };
>
> +/**
> + * policydb_filenametr_search() - Search for filename transition in policy
> + * @p: policydb structure to search in
> + * @match_type: filename transition match type to search for
> + * @key: key to search for
> + * @stype: source type to search for, when stype is zero, the function will
> + * return head of the linked list with matching key, otherwise it will
> + * traverse the linked list to find the item with matching stype
> + *
> + * Return: head of the linked list of filename transition datums or single item
> + * of the list, based on the stype value
> + */
> struct filename_trans_datum *
> -policydb_filenametr_search(struct policydb *p, struct filename_trans_key *key)
> +policydb_filenametr_search(struct policydb *p, unsigned int match_type,
> + struct filename_trans_key *key, u32 stype)
> {
> - return hashtab_search(&p->filename_trans, key, filenametr_key_params);
> + struct filename_trans_datum *datum = hashtab_search(
> + &p->filename_trans[match_type], key, filenametr_key_params);
> + if (!datum || !stype)
> + return datum;
> +
> + while (datum) {
> + if (ebitmap_get_bit(&datum->stypes, stype - 1))
> + return datum;
> +
> + datum = datum->next;
Nitpicky, but you can probably remove the vertical whitespace above.
> + }
> + return datum;
This could be 'return NULL', right?
> diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> index 4bba386264a3d..78abb959e7205 100644
> --- a/security/selinux/ss/policydb.h
> +++ b/security/selinux/ss/policydb.h
> @@ -232,6 +233,11 @@ struct genfs {
> #define OCON_IBENDPORT 8 /* Infiniband end ports */
> #define OCON_NUM 9
>
> +#define FILENAME_TRANS_MATCH_EXACT 0
> +#define FILENAME_TRANS_MATCH_PREFIX 1
> +#define FILENAME_TRANS_MATCH_SUFFIX 2
> +#define FILENAME_TRANS_MATCH_NUM 3
I think we should probably tweak things to help indicate that the last
macro/define above is not a usable value, how about this renaming it to
FILENAME_TRANS_MATCH_MAX? I'm open to other suggestions too ...
> /* The policy database */
> struct policydb {
> int mls_enabled;
> @@ -266,9 +272,12 @@ struct policydb {
> /* quickly exclude lookups when parent ttype has no rules */
> struct ebitmap filename_trans_ttypes;
> /* actual set of filename_trans rules */
> - struct hashtab filename_trans;
> + struct hashtab filename_trans[FILENAME_TRANS_MATCH_NUM];
> /* only used if policyvers < POLICYDB_VERSION_COMP_FTRANS */
> u32 compat_filename_trans_count;
> + /* lenghts of prefix/suffix rules to optimze for long filenames */
"lengths" and "optimize"
> + u32 filename_trans_name_max[FILENAME_TRANS_MATCH_NUM];
> + u32 filename_trans_name_min[FILENAME_TRANS_MATCH_NUM];
>
> /* 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 e88b1b6c4adbb..e142c6bdfe2ed 100644
> --- a/security/selinux/ss/services.c
> +++ b/security/selinux/ss/services.c
> @@ -1672,13 +1672,20 @@ static int compute_sid_handle_invalid_context(
> return -EACCES;
> }
>
> -static void filename_compute_type(struct policydb *policydb,
> +static int 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;
> + size_t prefix_len;
> + size_t suffix_len;
> + size_t prefix_max;
> + size_t suffix_max;
> + size_t prefix_min;
> + size_t suffix_min;
With the filename length variables being u32 elsewhere in this patch,
you can probably make these u32 and save some space (perf?).
> + size_t objname_len = strlen(objname);
Same here, although you'll likely need a cast to keep the compiler
quiet.
> /*
> * Most filename trans rules are going to live in specific directories
--
paul-moore.com
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v5] selinux: add prefix/suffix matching to filename type transitions
2024-03-28 1:22 ` Paul Moore
@ 2024-04-02 15:35 ` Juraj Marcin
2024-04-02 20:21 ` Paul Moore
0 siblings, 1 reply; 10+ messages in thread
From: Juraj Marcin @ 2024-04-02 15:35 UTC (permalink / raw
To: Paul Moore; +Cc: Stephen Smalley, selinux, Ondrej Mosnacek
Hi Paul
Thank you for your feedback!
On 2024-03-27 21:22, Paul Moore wrote:
> On Mar 5, 2024 Juraj Marcin <juraj@jurajmarcin.com> wrote:
> >
<snip>
> >
> > Performance tests:
> >
> > 1: Reference kernel (a1fc79343abbd), Fedora policy (format v33)
> > 2: This patch, Fedora policy (format v33)
> > 3: This patch, Fedora policy without prefix/suffix rules (format v34)
> > 4: This patch, Fedora policy with prefix rules (format v35)
>
> I think #4 also uses policy format v34, right?
Yes, it's just a typo, I will fix it.
>
> > | Mem | Binary | Policy | Create | osbench [2]
> > | Usage | policy | load | tty [1] | create
> > | | size | time | | files
> > | (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
> > ---+-------+--------+---------+-----------+-----------
> > 1 | 430 | 3682 | 46.930 | 2.4569 | 43.4431
> > | sd= 8 | | sd=0.25 | sd=0.043 | sd=0.434
> > 2 | 410 | 3682 | 46.829 | 2.4623 | 43.4112
> > | sd=20 | | sd=0.27 | sd=0.053 | sd=0.442
> > 3 | 419 | 3682 | 46.823 | 2.4257 | 43.0575
> > | sd=14 | | sd=0.18 | sd=0.057 | sd=0.416
> > 4 | 420 | 2585 | 42.044 | 2.5028 | 43.7907
> > | sd=10 | | sd=0.19 | sd=0.067 | sd=0.382
>
> Thanks for the updated patchset :)
>
> I like the improvements in #2 and #3, with only one test being slightly
> worse than #1, I think we're okay there. However, it looks like there
> has been a regression in #4 in terms of runtime performance ... hmmm.
It might look like a regression but there is some variance between runs,
even though I ran single benchmark many times and cases right after the
previous one. There is a similar difference but in the other direction
between #2 and #3 even though they both run with the same kernel and
basically the same policy (the only difference being explicit zero
counts of prefix and suffix rules in the policy file for #3).
I ran the whole benchmark suite again 2 times with the same reference
and patched kernels and got the following results:
| Mem | Binary | Policy | Create | osbench [2]
| Usage | policy | load | tty [1] | create
| | size | time | | files
| (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
---+-------+--------+---------+-----------+-----------
1 | 436 | 3682 | 48.955 | 2.5037 | 43.7484
| sd=20 | | sd=0.25 | sd=0.048 | sd=0.445
2 | 434 | 3682 | 48.331 | 2.4314 | 43.6714
| sd=16 | | sd=0.25 | sd=0.044 | sd=0.422
3 | 421 | 3682 | 47.592 | 2.4633 | 43.5746
| sd=19 | | sd=0.28 | sd=0.056 | sd=0.375
4 | 413 | 2585 | 41.895 | 2.4608 | 43.7485
| sd=13 | | sd=0.19 | sd=0.063 | sd=0.378
| Mem | Binary | Policy | Create | osbench [2]
| Usage | policy | load | tty [1] | create
| | size | time | | files
| (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
---+-------+--------+---------+-----------+-----------
1 | 442 | 3682 | 48.639 | 2.4741 | 43.4764
| sd=23 | | sd=0.21 | sd=0.059 | sd=0.487
2 | 422 | 3682 | 48.305 | 2.4191 | 43.6313
| sd=10 | | sd=0.21 | sd=0.064 | sd=0.460
3 | 427 | 3682 | 47.524 | 2.4798 | 43.7239
| sd=21 | | sd=0.17 | sd=0.055 | sd=0.590
4 | 416 | 2585 | 41.764 | 2.4272 | 43.6712
| sd= 8 | | sd=0.20 | sd=0.052 | sd=0.376
As can be seen, sometimes one case is the fastest one for the given test
by a few tenths of a millisecond/microsecond, sometimes it is the other
way around. Regression in one test case would result in it being slower
consistently between runs.
>
> > [1] 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.
> >
> > [2] https://github.com/mbitsnbites/osbench
> >
> > Reviewed-by: Ondrej Mosnacek <omosnace@redhat.com>
>
> Unless Ondrej has specifically reviewed v5, I think we need to drop
> his Reviewed-by tag as there have been some significant changes since
> he reviewed it last.
>
> > Signed-off-by: Juraj Marcin <juraj@jurajmarcin.com>
> > ---
> > v5:
> > - rebased to the latest pcmoore/selinux/next
> > - applied suggestions from Paul Moore
> > - added limit optimization suggested by Paul Moore
> > - removed string duplication by using explicit string length in
> > filename trasition key
> > ---
> > v4:
> > - rebased to the latest pcmoore/selinux/next
> > - fixed non-atomic allocation in atomic section
> > ---
> > v3:
> > - reworked the solution from scratch, this time only adding the
> > prefix/suffix matching feature without moving filename transition
> > rules to the avtab
> > ---
> > security/selinux/include/security.h | 4 +-
> > security/selinux/ss/policydb.c | 132 ++++++++++++++++++++++------
> > security/selinux/ss/policydb.h | 14 ++-
> > security/selinux/ss/services.c | 72 ++++++++++++---
> > 4 files changed, 178 insertions(+), 44 deletions(-)
> >
> > diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
> > index 289bf9233f714..49a043633173c 100644
> > --- a/security/selinux/include/security.h
> > +++ b/security/selinux/include/security.h
> > @@ -46,10 +46,12 @@
> > #define POLICYDB_VERSION_INFINIBAND 31
> > #define POLICYDB_VERSION_GLBLUB 32
> > #define POLICYDB_VERSION_COMP_FTRANS 33 /* compressed filename transitions */
> > +#define POLICYDB_VERSION_COMP_FTRANS 33 /* compressed filename transitions */
>
> I think one #define should be enough ;)
>
> > +#define POLICYDB_VERSION_PREFIX_SUFFIX 34 /* prefix/suffix filename transitions */
> >
> > /* 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_PREFIX_SUFFIX
> >
> > /* Mask for just the mount related flags */
> > #define SE_MNTMASK 0x0f
> > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > index 3d22d5baa829b..5de22ba840673 100644
> > --- a/security/selinux/ss/policydb.c
> > +++ b/security/selinux/ss/policydb.c
> > @@ -429,7 +434,11 @@ static int filenametr_cmp(const void *k1, const void *k2)
> > if (v)
> > return v;
> >
> > - return strcmp(ft1->name, ft2->name);
> > + v = strncmp(ft1->name, ft2->name, min(ft1->name_len, ft2->name_len));
> > + if (ft1->name_len == ft2->name_len || v)
> > + return v;
> > + /* if one name is prefix of the other, the longer is greater */
> > + return (int)ft1->name_len - (int)ft2->name_len;
> > }
>
> I'm probably missing some subtlety in the code above, but I think we
> might be able to optimize this a bit more:
>
> if (ft1->name_len != ft2->name_len)
> return (int)ft1->name_len - (int)ft2->name_len;
> return strcmp(ft1->name, ft2->name);
>
> I expect being able to avoid a string comparison in some cases should
> result in a small performance bump.
That optimization would lead to a different ordering than before with
the plain `strcmp()` - it would sort the strings by length first and
only then alphabetically. In fact, the `name_len` comparison could be
removed from the condition entirely without changing the ordering. This
could make it more clear.
However, this change in ordering might not matter as it is only a key
comparator function for the hash table and items from the policy are
inserted one by one. I will also ask Ondrej about this.
>
> > @@ -437,10 +446,34 @@ static const struct hashtab_key_params filenametr_key_params = {
> > .cmp = filenametr_cmp,
> > };
> >
> > +/**
> > + * policydb_filenametr_search() - Search for filename transition in policy
> > + * @p: policydb structure to search in
> > + * @match_type: filename transition match type to search for
> > + * @key: key to search for
> > + * @stype: source type to search for, when stype is zero, the function will
> > + * return head of the linked list with matching key, otherwise it will
> > + * traverse the linked list to find the item with matching stype
> > + *
> > + * Return: head of the linked list of filename transition datums or single item
> > + * of the list, based on the stype value
> > + */
> > struct filename_trans_datum *
> > -policydb_filenametr_search(struct policydb *p, struct filename_trans_key *key)
> > +policydb_filenametr_search(struct policydb *p, unsigned int match_type,
> > + struct filename_trans_key *key, u32 stype)
> > {
> > - return hashtab_search(&p->filename_trans, key, filenametr_key_params);
> > + struct filename_trans_datum *datum = hashtab_search(
> > + &p->filename_trans[match_type], key, filenametr_key_params);
> > + if (!datum || !stype)
> > + return datum;
> > +
> > + while (datum) {
> > + if (ebitmap_get_bit(&datum->stypes, stype - 1))
> > + return datum;
> > +
> > + datum = datum->next;
>
> Nitpicky, but you can probably remove the vertical whitespace above.
>
> > + }
> > + return datum;
>
> This could be 'return NULL', right?
Yes, I will change it.
>
> > diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> > index 4bba386264a3d..78abb959e7205 100644
> > --- a/security/selinux/ss/policydb.h
> > +++ b/security/selinux/ss/policydb.h
> > @@ -232,6 +233,11 @@ struct genfs {
> > #define OCON_IBENDPORT 8 /* Infiniband end ports */
> > #define OCON_NUM 9
> >
> > +#define FILENAME_TRANS_MATCH_EXACT 0
> > +#define FILENAME_TRANS_MATCH_PREFIX 1
> > +#define FILENAME_TRANS_MATCH_SUFFIX 2
> > +#define FILENAME_TRANS_MATCH_NUM 3
>
> I think we should probably tweak things to help indicate that the last
> macro/define above is not a usable value, how about this renaming it to
> FILENAME_TRANS_MATCH_MAX? I'm open to other suggestions too ...
I thought being consistent with other array indices (`SYM_*`, `OCON_*`)
would be better, but I am also open to change the suffix to `_MAX` if
there are no objections.
Then possibly update also `SYM_NUM` and `OCON_NUM` defines in another
patch.
>
> > /* The policy database */
> > struct policydb {
> > int mls_enabled;
> > @@ -266,9 +272,12 @@ struct policydb {
> > /* quickly exclude lookups when parent ttype has no rules */
> > struct ebitmap filename_trans_ttypes;
> > /* actual set of filename_trans rules */
> > - struct hashtab filename_trans;
> > + struct hashtab filename_trans[FILENAME_TRANS_MATCH_NUM];
> > /* only used if policyvers < POLICYDB_VERSION_COMP_FTRANS */
> > u32 compat_filename_trans_count;
> > + /* lenghts of prefix/suffix rules to optimze for long filenames */
>
> "lengths" and "optimize"
>
> > + u32 filename_trans_name_max[FILENAME_TRANS_MATCH_NUM];
> > + u32 filename_trans_name_min[FILENAME_TRANS_MATCH_NUM];
> >
> > /* 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 e88b1b6c4adbb..e142c6bdfe2ed 100644
> > --- a/security/selinux/ss/services.c
> > +++ b/security/selinux/ss/services.c
> > @@ -1672,13 +1672,20 @@ static int compute_sid_handle_invalid_context(
> > return -EACCES;
> > }
> >
> > -static void filename_compute_type(struct policydb *policydb,
> > +static int 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;
> > + size_t prefix_len;
> > + size_t suffix_len;
> > + size_t prefix_max;
> > + size_t suffix_max;
> > + size_t prefix_min;
> > + size_t suffix_min;
>
> With the filename length variables being u32 elsewhere in this patch,
> you can probably make these u32 and save some space (perf?).
>
> > + size_t objname_len = strlen(objname);
>
> Same here, although you'll likely need a cast to keep the compiler
> quiet.
>
> > /*
> > * Most filename trans rules are going to live in specific directories
>
> --
> paul-moore.com
Best regards
Juraj Marcin
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v5] selinux: add prefix/suffix matching to filename type transitions
2024-04-02 15:35 ` Juraj Marcin
@ 2024-04-02 20:21 ` Paul Moore
0 siblings, 0 replies; 10+ messages in thread
From: Paul Moore @ 2024-04-02 20:21 UTC (permalink / raw
To: Juraj Marcin; +Cc: Stephen Smalley, selinux, Ondrej Mosnacek
On Tue, Apr 2, 2024 at 11:35 AM Juraj Marcin <juraj@jurajmarcin.com> wrote:
>
> Hi Paul
>
> Thank you for your feedback!
Thank you for the patch :)
> On 2024-03-27 21:22, Paul Moore wrote:
> > On Mar 5, 2024 Juraj Marcin <juraj@jurajmarcin.com> wrote:
...
> > > | Mem | Binary | Policy | Create | osbench [2]
> > > | Usage | policy | load | tty [1] | create
> > > | | size | time | | files
> > > | (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
> > > ---+-------+--------+---------+-----------+-----------
> > > 1 | 430 | 3682 | 46.930 | 2.4569 | 43.4431
> > > | sd= 8 | | sd=0.25 | sd=0.043 | sd=0.434
> > > 2 | 410 | 3682 | 46.829 | 2.4623 | 43.4112
> > > | sd=20 | | sd=0.27 | sd=0.053 | sd=0.442
> > > 3 | 419 | 3682 | 46.823 | 2.4257 | 43.0575
> > > | sd=14 | | sd=0.18 | sd=0.057 | sd=0.416
> > > 4 | 420 | 2585 | 42.044 | 2.5028 | 43.7907
> > > | sd=10 | | sd=0.19 | sd=0.067 | sd=0.382
> >
> > Thanks for the updated patchset :)
> >
> > I like the improvements in #2 and #3, with only one test being slightly
> > worse than #1, I think we're okay there. However, it looks like there
> > has been a regression in #4 in terms of runtime performance ... hmmm.
>
> It might look like a regression but there is some variance between runs,
> even though I ran single benchmark many times and cases right after the
> previous one. There is a similar difference but in the other direction
> between #2 and #3 even though they both run with the same kernel and
> basically the same policy (the only difference being explicit zero
> counts of prefix and suffix rules in the policy file for #3).
>
> I ran the whole benchmark suite again 2 times with the same reference
> and patched kernels and got the following results:
>
> | Mem | Binary | Policy | Create | osbench [2]
> | Usage | policy | load | tty [1] | create
> | | size | time | | files
> | (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
> ---+-------+--------+---------+-----------+-----------
> 1 | 436 | 3682 | 48.955 | 2.5037 | 43.7484
> | sd=20 | | sd=0.25 | sd=0.048 | sd=0.445
> 2 | 434 | 3682 | 48.331 | 2.4314 | 43.6714
> | sd=16 | | sd=0.25 | sd=0.044 | sd=0.422
> 3 | 421 | 3682 | 47.592 | 2.4633 | 43.5746
> | sd=19 | | sd=0.28 | sd=0.056 | sd=0.375
> 4 | 413 | 2585 | 41.895 | 2.4608 | 43.7485
> | sd=13 | | sd=0.19 | sd=0.063 | sd=0.378
>
> | Mem | Binary | Policy | Create | osbench [2]
> | Usage | policy | load | tty [1] | create
> | | size | time | | files
> | (MiB) | (KiB) | (ms) | (ms/file) | (us/file)
> ---+-------+--------+---------+-----------+-----------
> 1 | 442 | 3682 | 48.639 | 2.4741 | 43.4764
> | sd=23 | | sd=0.21 | sd=0.059 | sd=0.487
> 2 | 422 | 3682 | 48.305 | 2.4191 | 43.6313
> | sd=10 | | sd=0.21 | sd=0.064 | sd=0.460
> 3 | 427 | 3682 | 47.524 | 2.4798 | 43.7239
> | sd=21 | | sd=0.17 | sd=0.055 | sd=0.590
> 4 | 416 | 2585 | 41.764 | 2.4272 | 43.6712
> | sd= 8 | | sd=0.20 | sd=0.052 | sd=0.376
>
> As can be seen, sometimes one case is the fastest one for the given test
> by a few tenths of a millisecond/microsecond, sometimes it is the other
> way around. Regression in one test case would result in it being slower
> consistently between runs.
In all three reported results, test #4 is slower than test #1 in every
case, although it is within 0.001 in one result. While I agree there
does appear to be variation in the tests, the fact that none of the
results show #4 as being faster than #1 does seem to indicate a
performance regression in test #4.
> > > diff --git a/security/selinux/ss/policydb.c b/security/selinux/ss/policydb.c
> > > index 3d22d5baa829b..5de22ba840673 100644
> > > --- a/security/selinux/ss/policydb.c
> > > +++ b/security/selinux/ss/policydb.c
> > > @@ -429,7 +434,11 @@ static int filenametr_cmp(const void *k1, const void *k2)
> > > if (v)
> > > return v;
> > >
> > > - return strcmp(ft1->name, ft2->name);
> > > + v = strncmp(ft1->name, ft2->name, min(ft1->name_len, ft2->name_len));
> > > + if (ft1->name_len == ft2->name_len || v)
> > > + return v;
> > > + /* if one name is prefix of the other, the longer is greater */
> > > + return (int)ft1->name_len - (int)ft2->name_len;
> > > }
> >
> > I'm probably missing some subtlety in the code above, but I think we
> > might be able to optimize this a bit more:
> >
> > if (ft1->name_len != ft2->name_len)
> > return (int)ft1->name_len - (int)ft2->name_len;
> > return strcmp(ft1->name, ft2->name);
> >
> > I expect being able to avoid a string comparison in some cases should
> > result in a small performance bump.
>
> That optimization would lead to a different ordering than before with
> the plain `strcmp()` - it would sort the strings by length first and
> only then alphabetically. In fact, the `name_len` comparison could be
> removed from the condition entirely without changing the ordering. This
> could make it more clear.
>
> However, this change in ordering might not matter as it is only a key
> comparator function for the hash table and items from the policy are
> inserted one by one. I will also ask Ondrej about this.
With hashtab_search() exiting early on a negative result from
filenametr_cmp() it may look like the ordering within the bucket
matters, but so long as we use the same sorting order when
accessing/inserting entries it shouldn't matter. The important thing
is that we can search through the bucket entries as fast as possible,
and performing integer comparisons/math is going to be a lot faster
than performing a string comparison.
> > > diff --git a/security/selinux/ss/policydb.h b/security/selinux/ss/policydb.h
> > > index 4bba386264a3d..78abb959e7205 100644
> > > --- a/security/selinux/ss/policydb.h
> > > +++ b/security/selinux/ss/policydb.h
> > > @@ -232,6 +233,11 @@ struct genfs {
> > > #define OCON_IBENDPORT 8 /* Infiniband end ports */
> > > #define OCON_NUM 9
> > >
> > > +#define FILENAME_TRANS_MATCH_EXACT 0
> > > +#define FILENAME_TRANS_MATCH_PREFIX 1
> > > +#define FILENAME_TRANS_MATCH_SUFFIX 2
> > > +#define FILENAME_TRANS_MATCH_NUM 3
> >
> > I think we should probably tweak things to help indicate that the last
> > macro/define above is not a usable value, how about this renaming it to
> > FILENAME_TRANS_MATCH_MAX? I'm open to other suggestions too ...
>
> I thought being consistent with other array indices (`SYM_*`, `OCON_*`)
> would be better, but I am also open to change the suffix to `_MAX` if
> there are no objections.
Ugh, yes, you're right. We should change those other #defines, but
let's leave that for another time. Stick with _NUM.
> Then possibly update also `SYM_NUM` and `OCON_NUM` defines in another
> patch.
Yes, that's the right approach as far as I'm concerned, but that's
something for later.
--
paul-moore.com
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2024-04-02 20:21 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-11-21 12:27 [PATCH v4] selinux: add prefix/suffix matching to filename type transitions Juraj Marcin
2023-11-21 19:24 ` Stephen Smalley
2023-12-06 3:18 ` Paul Moore
2023-12-20 12:20 ` Juraj Marcin
2023-12-22 22:46 ` Paul Moore
2024-03-01 12:53 ` Juraj Marcin
2024-03-05 17:04 ` [PATCH v5] " Juraj Marcin
2024-03-28 1:22 ` Paul Moore
2024-04-02 15:35 ` Juraj Marcin
2024-04-02 20:21 ` Paul Moore
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).