From: Kornelius Kalnbach <murphy@...>
Date: 2010-02-08T21:29:23+09:00
Subject: [ruby-core:28106] Re: [Bug #2644] memory over-allocation with regexp

On 08.02.10 09:36, Greg Hazel wrote:
> Issue #2644 has been updated by Greg Hazel.
I have a nicer workaround, see below.

> Well, considering other regexp implementations do not have this bug,
>  my guess would be this is either easy or a matter of switching to a
>  better regexp parser, which probably has other benefits.
I think Oniguruma (1.9) is a great Regexp engine. We could redirect the
issue to the author...but that won't fix 1.8. Maybe the problem is on
the Ruby side? JRuby seems to be affected, too:

1
2
Error: Your application used more memory than the safety cap of 500m.
Specify -J-Xmx####m to increase it (#### = cap size in MB).
Specify -w for full OutOfMemoryError stack trace

(The string is only 84 MB.)

On 25.01.10 15:03, Robert Klemme wrote:
> Question is how much the fix costs and how realistic this is.  Even 
> in case there is not a fix, here's an easy workaround for the regular
> expression you presented: avoid backtracking through greediness
> (works on 1.9 and JRuby only): /(\d) (.*+)/
Question is: Why would it backtrack? It doesn't need to. The expressions
are equivalent for this string.

Also, both these expressions need to backtrack, and they work even for
larger strings:

p ' '.*(200_000_000)[/.*?$/].size  #=> 200000000
p ' '.*(200_000_000)[/^.*?$/].size  #=> 200000000

Even this one works:

p ' '.*(200_000_000)[/(.)*/,1].size  #=> 1

All of the above scripts only need about 200 MB of RAM.

Just this breaks it, trying to allocate over 2GiB:

p ' '.*(200_000_000)[/.*/].size
ruby(81051) malloc: *** mmap(size=2348810240) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
test.rb:1:in `[]': Stack overflow in regexp matcher: /.*/ (RegexpError)
	from test.rb:1

Same with + and {0,}. This seems to be a workaround (all Ruby versions):

p ' '.*(200_000_000)[/(?:.)*/].size  #=> 200000000

Ruby is definitely doing something strange here in the background.

> So, I think it should be fixed.
So do I. Actually, how can it be a *Stack overflow*? Quirks like this
tend to hint at bugs or possible optimizations.

Thanks for reading.
[murphy]