selinux: optimize storage of filename transitions

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

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

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

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

Performance/memory usage comparison:

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

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

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

Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
Acked-by: Stephen Smalley <sds@tycho.nsa.gov>
Signed-off-by: Paul Moore <paul@paul-moore.com>

1 files changed, 10 insertions, 6 deletions

diff --git a/security/selinux/ss/services.c b/security/selinux/ss/services.c
index 57b2c6252799..f90e6550eec8 100644
--- a/security/selinux/ss/services.c
+++ b/security/selinux/ss/services.c
@@ -1692,8 +1692,8 @@ static void filename_compute_type(struct policydb *policydb,
 				  u32 stype, u32 ttype, u16 tclass,
 				  const char *objname)
 {
-	struct filename_trans ft;
-	struct filename_trans_datum *otype;
+	struct filename_trans_key ft;
+	struct filename_trans_datum *datum;
 
 	/*
 	 * Most filename trans rules are going to live in specific directories
@@ -1703,14 +1703,18 @@ static void filename_compute_type(struct policydb *policydb,
 	if (!ebitmap_get_bit(&policydb->filename_trans_ttypes, ttype))
 		return;
 
-	ft.stype = stype;
 	ft.ttype = ttype;
 	ft.tclass = tclass;
 	ft.name = objname;
 
-	otype = hashtab_search(policydb->filename_trans, &ft);
-	if (otype)
-		newcontext->type = otype->otype;
+	datum = hashtab_search(policydb->filename_trans, &ft);
+	while (datum) {
+		if (ebitmap_get_bit(&datum->stypes, stype - 1)) {
+			newcontext->type = datum->otype;
+			return;
+		}
+		datum = datum->next;
+	}
 }
 
 static int security_compute_sid(struct selinux_state *state,