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

[Florian Weimer]

* Collin Funk:

> Florian Weimer <fweimer@redhat.com> writes:
>
>>> 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
>>
>> Does this change really make a difference?  It seems we still run out of
>> memory for ?+?+?+… and similar patterns.
>
> Oops, you are right...
>
> I guess the way to match the current behavior without allocating
> unbounded memory from adjacent duplication symbols is to allow only one
> of each. You could optimize it even further by converting any occurrence
> of "+?" or "?+" into "*" and any sequence of symbols containing "*" into
> only "*".
>
> Let me think about it a bit more and send a v2.

There's also this:

#include <regex.h>
#include <support/check.h>
#include <sys/resource.h>

#include <string>

static int
do_test (void)
{
  struct rlimit stack_limit = { 512 * 1024 * 1024, 512 * 1024 * 1024 };
  setrlimit (RLIMIT_AS, &stack_limit);

  const int count = 512;
  std::string pattern;
  for (int i = 0; i < count; ++i)
    pattern += '(';
  pattern += 'a';
  for (int i = 0; i < count; ++i)
    pattern += ")+";

  regex_t re;
  TEST_VERIFY_EXIT (regcomp (&re, pattern.c_str(), REG_EXTENDED) == 0);
  regfree (&re);

  return 0;
}

#include <support/test-driver.c>

So this is much larger issue, I think.

In your test, you should probably remove the setrlimit check, in case
it's raising the limit and not reducing it.

Thanks,
Florian