On Wed, 8 Jan 2025 at 22:51, James Carter <jwcart2@xxxxxxxxx> wrote:
>
> On Mon, Dec 30, 2024 at 9:03 AM Christian Göttsche
> <cgoettsche@xxxxxxxxxxxxx> wrote:
> >
> > 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);
> > +}
> > +
>
> This function was just deleted when the fix was applied to restore
> regex spec ordering. I am a little worried about breaking that
> ordering again.
Only a temporary copied array is sorted, not the original data.
> I am also wondering if this is addressing an actual problem. A quick
> test on my system shows a max value for node->regex_specs_num of 347
> and only eight instances of it being more than 100.
True, but I tried to avoid reports like this one:
https://lore.kernel.org/selinux/20230209114253.120485-1-wanghuizhao1@xxxxxxxxxx/
>
> Thanks,
> Jim
>
> > /*
> > * 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];
This should be `©[i]` and `©[i + 1]` instead of `
&node->regex_specs[i]` and `&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
> >
> >
