linux-kernel - [RFC PATCH] selinux: optimize ebitmap

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [day] [month] [year] [list]

Message-Id: <20230728155937.41580-1-cgzones@googlemail.com>
Date:   Fri, 28 Jul 2023 17:59:36 +0200
From:   Christian Göttsche <cgzones@...glemail.com>
To:     selinux@...r.kernel.org
Cc:     Paul Moore <paul@...l-moore.com>,
        Stephen Smalley <stephen.smalley.work@...il.com>,
        Eric Paris <eparis@...isplace.org>,
        linux-kernel@...r.kernel.org
Subject: [RFC PATCH] selinux: optimize ebitmap_and()

Iterate on nodes instead of single bits to save node resolution for each
single bit.

Similar to userspace patch efcd00814879 ("libsepol: optimize
ebitmap_and").

Signed-off-by: Christian Göttsche <cgzones@...glemail.com>
---
 security/selinux/ss/ebitmap.c | 48 ++++++++++++++++++++++++++++++-----
 1 file changed, 41 insertions(+), 7 deletions(-)

diff --git a/security/selinux/ss/ebitmap.c b/security/selinux/ss/ebitmap.c
index 77875ad355f7..5ac8acacf873 100644
--- a/security/selinux/ss/ebitmap.c
+++ b/security/selinux/ss/ebitmap.c
@@ -81,18 +81,52 @@ int ebitmap_cpy(struct ebitmap *dst, const struct ebitmap *src)
 
 int ebitmap_and(struct ebitmap *dst, const struct ebitmap *e1, const struct ebitmap *e2)
 {
-	struct ebitmap_node *n;
-	int bit, rc;
+	const struct ebitmap_node *n1, *n2;
+	struct ebitmap_node *new = NULL, **prev;
 
 	ebitmap_init(dst);
 
-	ebitmap_for_each_positive_bit(e1, n, bit) {
-		if (ebitmap_get_bit(e2, bit)) {
-			rc = ebitmap_set_bit(dst, bit, 1);
-			if (rc < 0)
-				return rc;
+	prev = &dst->node;
+	n1 = e1->node;
+	n2 = e2->node;
+	while (n1 && n2) {
+		if (n1->startbit == n2->startbit) {
+			unsigned long testmap[EBITMAP_UNIT_NUMS];
+			unsigned int i;
+			bool match = false;
+
+			for (i = 0; i < sizeof(testmap); i++) {
+				testmap[i] = n1->maps[i] & n2->maps[i];
+				if (testmap[i] != 0)
+					match = true;
+			}
+
+			if (match) {
+				new = kmem_cache_zalloc(ebitmap_node_cachep, GFP_ATOMIC);
+				if (!new) {
+					ebitmap_destroy(dst);
+					return -ENOMEM;
+				}
+				new->startbit = n1->startbit;
+				memcpy(new->maps, testmap, EBITMAP_SIZE / 8);
+				new->next = NULL;
+
+				*prev = new;
+				prev = &(new->next);
+			}
+
+			n1 = n1->next;
+			n2 = n2->next;
+		} else if (n1->startbit > n2->startbit) {
+			n2 = n2->next;
+		} else {
+			n1 = n1->next;
 		}
 	}
+
+	if (new)
+		dst->highbit = new->startbit + EBITMAP_SIZE;
+
 	return 0;
 }
 
-- 
2.40.1