[PATCH] posix: Don't unnecessarily duplicate the parse tree in regcomp [BZ #20095]

[Collin Funk]

Currently regcomp duplicates the the parse tree for each repetition
operator. This patch avoids the duplication when the previous repetition
operator is the same as the current operator. This prevents you from
quickly exhausting the system's memory. Here is an example with GNU grep
before and after this change:

    $ (ulimit -v 10000000 \
       && grep -Ec 'a++++++++++++++++++++++++' COPYING)
    grep: Memory exhausted
    $ (ulimit -v 10000000 \
       && ./src/grep -Ec 'a++++++++++++++++++++++++' COPYING)
    509

-- 8< --

If this one is okay for glibc then I will commit it to Gnulib as well.
It would be nice for grep and other programs who use regex functions
from Gnulib to handle input like this without running out of memory.

---
 posix/Makefile            |  1 +
 posix/regcomp.c           |  8 +++++++
 posix/tst-regex-bz20095.c | 49 +++++++++++++++++++++++++++++++++++++++
 3 files changed, 58 insertions(+)
 create mode 100644 posix/tst-regex-bz20095.c

diff --git a/posix/Makefile b/posix/Makefile
index f6421e5379..2d7c60c2fe 100644
--- a/posix/Makefile
+++ b/posix/Makefile
@@ -308,6 +308,7 @@ tests := \
   tst-regcomp-bracket-free \
   tst-regcomp-truncated \
   tst-regex \
+  tst-regex-bz20095 \
   tst-regex2 \
   tst-regexloc \
   tst-rxspencer \
diff --git a/posix/regcomp.c b/posix/regcomp.c
index f7278bb852..b4a9561b37 100644
--- a/posix/regcomp.c
+++ b/posix/regcomp.c
@@ -2442,6 +2442,7 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
     }
   fetch_token (token, regexp, syntax);
 
+  re_token_type_t prev_type = token->type;
   while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS
 	 || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)
     {
@@ -2464,6 +2465,13 @@ parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
 	  *err = REG_BADRPT;
 	  return NULL;
 	}
+      /* Don't exhaust memory when given a pattern like "a+++++++".  */
+      if (prev_type != OP_OPEN_DUP_NUM)
+	{
+	  while (prev_type == token->type)
+	    fetch_token (token, regexp, syntax);
+	}
+      prev_type = token->type;
     }
 
   return tree;
diff --git a/posix/tst-regex-bz20095.c b/posix/tst-regex-bz20095.c
new file mode 100644
index 0000000000..7faee12f46
--- /dev/null
+++ b/posix/tst-regex-bz20095.c
@@ -0,0 +1,49 @@
+/* Test for that "a++++" doesn't exhaust memory by duplicating the tree.
+   Copyright (C) 2025 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <https://www.gnu.org/licenses/>.  */
+
+#include <regex.h>
+#include <string.h>
+#include <support/test-driver.h>
+#include <support/check.h>
+#include <sys/resource.h>
+
+/* Pattern size.  */
+#define SIZE 4096
+
+/* This would exhaust memory on glibc 2.42 and earlier.  */
+#define MAX_MEMORY (512 * 1024 * 1024)
+
+static int
+do_test (void)
+{
+  struct rlimit stack_limit = { MAX_MEMORY, MAX_MEMORY };
+  TEST_VERIFY_EXIT (setrlimit (RLIMIT_AS, &stack_limit) == 0);
+  char pattern[SIZE];
+  regex_t re;
+
+  /* "a++++++".  */
+  pattern[0] = 'a';
+  memset (pattern + 1, '+', sizeof pattern - 2);
+  pattern[sizeof pattern - 1] = '\0';
+  TEST_VERIFY_EXIT (regcomp (&re, pattern, REG_EXTENDED) == 0);
+  regfree (&re);
+
+  return 0;
+}
+
+#include <support/test-driver.c>
-- 
2.51.0