From: Christian Göttsche <cgzones@xxxxxxxxxxxxxx>
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 <cgzones@xxxxxxxxxxxxxx>
---
libselinux/src/label_file.c | 85 +++++++++++++++++++++++++++++++++++--
1 file changed, 82 insertions(+), 3 deletions(-)
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);
+ }
+ }
+ }
}
}
--
2.45.2
