From: panzhe <[email protected]>
GEAcompile compiled all the backref-free -f patterns as a single
'\n'-separated alternation regex. The regex engine computes an
epsilon closure for every alternation node, so compilation needed
memory quadratic in the number of patterns; with 20000 patterns
from a word list the compile alone used about 1.9 GiB, and grep
aborted with "memory exhausted" when allocation failed.
Compile the patterns in chunks of at most 1024 patterns so that
memory grows linearly. Matching results are unchanged, as
EGexecute already searches each compiled pattern and picks the
leftmost-longest match.
---
src/dfasearch.c | 45 +++++++++++++++++++++++++++++++++++++----
tests/Makefile.am | 1 +
tests/many-f-patterns | 47 +++++++++++++++++++++++++++++++++++++++++++
3 files changed, 89 insertions(+), 4 deletions(-)
create mode 100755 tests/many-f-patterns
diff --git a/src/dfasearch.c b/src/dfasearch.c
index f126117..728ae53 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -187,6 +187,10 @@ regex_compile (struct dfa_comp *dc, char const *p, idx_t
len,
return false;
}
+/* Compile -f patterns in chunks of at most this many, to avoid the
+ quadratic memory use of compiling them all as one regex. */
+enum { PATTERNS_PER_REGEX = 1024 };
+
/* Compile PATTERN, containing SIZE bytes that are followed by '\n'.
SYNTAX_BITS specifies whether PATTERN uses style -G, -E, or -A.
Return a description of the compiled pattern. */
@@ -332,11 +336,44 @@ GEAcompile (char *pattern, idx_t size, reg_syntax_t
syntax_bits,
{
if (exact || !dfasupported (dc->dfa))
{
- dc->patterns--;
- dc->pcount++;
+ char const *b = buf;
+ char const *blim = buf + buflen;
+ do
+ {
+ /* CHUNK_END points at the '\n' after the chunk's last
+ pattern, or at BLIM. */
+ char const *chunk_end = blim;
+ char const *q = b;
+ for (idx_t n = 0; n < PATTERNS_PER_REGEX; n++)
+ {
+ char const *sep = memchr (q, '\n', blim - q);
+ if (!sep)
+ break;
+ chunk_end = sep;
+ q = sep + 1;
+ }
+ idx_t chunklen = chunk_end - b;
+
+ ptrdiff_t shortage = dc->pcount - palloc + 2;
+ if (0 < shortage)
+ {
+ dc->patterns = xpalloc (dc->patterns - 1, &palloc,
+ shortage, -1,
+ sizeof *dc->patterns);
+ dc->patterns++;
+ }
+
+ if (!regex_compile (dc, b, chunklen, dc->pcount, -1,
+ syntax_bits, false))
+ compilation_failed = true;
+ dc->pcount++;
+
+ b = chunk_end < blim ? chunk_end + 1 : blim;
+ }
+ while (b < blim);
- if (!regex_compile (dc, buf, buflen, 0, -1, syntax_bits, false))
- abort ();
+ if (compilation_failed)
+ exit (EXIT_TROUBLE);
}
if (buf != pattern)
diff --git a/tests/Makefile.am b/tests/Makefile.am
index eeb20f0..de4764a 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -130,6 +130,7 @@ TESTS = \
kwset-abuse \
long-line-vs-2GiB-read \
long-pattern-perf \
+ many-f-patterns \
many-regex-performance \
match-lines \
max-count-overread \
diff --git a/tests/many-f-patterns b/tests/many-f-patterns
new file mode 100755
index 0000000..ebbdfcd
--- /dev/null
+++ b/tests/many-f-patterns
@@ -0,0 +1,47 @@
+#!/bin/sh
+# grep -f with many patterns could exhaust memory and abort: all the
+# backref-free patterns were compiled as one '\n'-separated alternation
+# whose compilation needs memory (and time) quadratic in the number of
+# patterns. Check that results are correct and memory stays bounded.
+
+# Copyright 2026 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3, or (at your option)
+# any later version.
+
+# This program 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 General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+. "${srcdir=.}/init.sh"; path_prepend_ ../src
+
+fail=0
+
+# More than one chunk of metacharacter-bearing patterns, so that the
+# patterns are not converted to -F; results must be unaffected.
+seq 3000 | sed 's/$/./' > pat || framework_failure_
+grep -o -f pat pat > out || fail=1
+compare pat out || fail=1
+
+# A backref pattern mixed in with many plain patterns.
+printf 'a\\(b\\)\\1\n' >> pat || framework_failure_
+printf 'ababb\n1.\n2.\n' > in || framework_failure_
+grep -o -f pat in > out || fail=1
+printf 'abb\n1.\n2.\n' > exp || framework_failure_
+compare exp out || fail=1
+
+# With 20000 patterns the single merged regex needed well over 1 GiB
+# and grep aborted with "memory exhausted" under this limit; compiled
+# in bounded chunks it must succeed.
+seq 20000 | sed 's/$/./' > big-pat || framework_failure_
+( ulimit -v 1048576
+ grep -o -f big-pat big-pat > big-out ) || fail=1
+compare big-pat big-out || fail=1
+
+Exit $fail
--
2.27.0
