libselinux: avoid quadratic complexity for many regex specs validation

Commit Message

Christian Göttsche Dec. 30, 2024, 2:03 p.m. UTC

From: Christian Göttsche <[e-mail]>

In the degenerate case of many regular expression specifications in a
single node switch to a n*log(n) algorithm (with allocation) instead of
the default n^2 (without allocation) one.

See 2c7b71db ("libselinux: performance optimization for duplicate detection")
for a predecessor.

Signed-off-by: Christian Göttsche <[e-mail]>
---
 libselinux/src/label_file.c | 85 +++++++++++++++++++++++++++++++++++--
 1 file changed, 82 insertions(+), 3 deletions(-)

Patch

diff --git a/libselinux/src/label_file.c b/libselinux/src/label_file.c
index 56e20949..b1884e80 100644
--- a/libselinux/src/label_file.c
+++ b/libselinux/src/label_file.c
@@ -102,6 +102,38 @@  void sort_spec_node(struct spec_node *node, struct spec_node *parent)
 		sort_spec_node(&node->children[i], node);
 }
 
+static inline int compare_regex_spec(const void *p1, const void *p2)
+{
+	const struct regex_spec *r1 = p1;
+	const struct regex_spec *r2 = p2;
+	size_t regex_len1, regex_len2;
+	int ret;
+
+	/* Order from high prefix length to low */
+	ret = (r1->prefix_len < r2->prefix_len) - (r1->prefix_len > r2->prefix_len);
+	if (ret)
+		return ret;
+
+	/* Order from long total regex length to short */
+	regex_len1 = strlen(r1->regex_str);
+	regex_len2 = strlen(r2->regex_str);
+	ret = (regex_len1 < regex_len2) - (regex_len1 > regex_len2);
+	if (ret)
+		return ret;
+
+	/*
+	 * Order for no-duplicates check.
+	 * Use reverse alphabetically order to retain the Fedora ordering of
+	 * `/usr/(.* /)?lib(/.*)?` before `/usr/(.* /)?bin(/.*)?`.
+	 */
+	ret = strcmp(r1->regex_str, r2->regex_str);
+	if (ret)
+		return -ret;
+
+	/* Order wildcard mode (0) last */
+	return (r1->file_kind < r2->file_kind) - (r1->file_kind > r2->file_kind);
+}
+
 /*
  * Warn about duplicate specifications.
  */
@@ -143,10 +175,18 @@  static int nodups_spec_node(const struct spec_node *node, const char *path)
 	}
 
 	if (node->regex_specs_num > 1) {
-		for (uint32_t i = 0; i < node->regex_specs_num - 1; i++) {
-			for (uint32_t j = i; j < node->regex_specs_num - 1; j++) {
+		if (node->regex_specs_num > 512) {
+			uint32_t num = node->regex_specs_num;
+			struct regex_spec *copy = malloc(num * sizeof(struct regex_spec));
+			if (!copy)
+				goto default_algo;
+
+			memcpy(copy, node->regex_specs, num * sizeof(struct regex_spec));
+			qsort(copy, num, sizeof(struct regex_spec), compare_regex_spec);
+
+			for (uint32_t i = 0; i < node->regex_specs_num - 1; i++) {
 				const struct regex_spec *node1 = &node->regex_specs[i];
-				const struct regex_spec *node2 = &node->regex_specs[j + 1];
+				const struct regex_spec *node2 = &node->regex_specs[i + 1];
 
 				if (node1->prefix_len != node2->prefix_len)
 					continue;
@@ -177,6 +217,45 @@  static int nodups_spec_node(const struct spec_node *node, const char *path)
 							node1->regex_str);
 				}
 			}
+
+			free(copy);
+		} else {
+			default_algo:
+			for (uint32_t i = 0; i < node->regex_specs_num - 1; i++) {
+				for (uint32_t j = i; j < node->regex_specs_num - 1; j++) {
+					const struct regex_spec *node1 = &node->regex_specs[i];
+					const struct regex_spec *node2 = &node->regex_specs[j + 1];
+
+					if (node1->prefix_len != node2->prefix_len)
+						continue;
+
+					if (strcmp(node1->regex_str, node2->regex_str) != 0)
+						continue;
+
+					if (node1->file_kind != LABEL_FILE_KIND_ALL && node2->file_kind != LABEL_FILE_KIND_ALL && node1->file_kind != node2->file_kind)
+						continue;
+
+					rc = -1;
+					errno = EINVAL;
+					if (strcmp(node1->lr.ctx_raw, node2->lr.ctx_raw) != 0) {
+						COMPAT_LOG
+							(SELINUX_ERROR,
+								"%s: Multiple different specifications for %s %s  (%s and %s).\n",
+								path,
+								file_kind_to_string(node1->file_kind),
+								node1->regex_str,
+								node1->lr.ctx_raw,
+								node2->lr.ctx_raw);
+					} else {
+						COMPAT_LOG
+							(SELINUX_ERROR,
+								"%s: Multiple same specifications for %s %s.\n",
+								path,
+								file_kind_to_string(node1->file_kind),
+								node1->regex_str);
+					}
+				}
+			}
 		}
 	}