1348779 - Crash [@ js::detail::BumpChunk::setBump] with stack space exhaustion involving Worker

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

The following testcase crashes on mozilla-central revision e1576dd8bd9d (build with --enable-posix-nspr-emulation --enable-valgrind --enable-gczeal --disable-tests --enable-stdcxx-compat --disable-profiling --enable-debug --without-intl-api --enable-optimize --target=i686-pc-linux-gnu, run with --fuzzing-safe --ion-offthread-compile=off):

evalInWorker(`
  var N = 10000;
  var left = repeat_str('(1&', N);
  var right = repeat_str(')', N);
  var str = 'actual = '.concat(left, '1', right, ';');
  function repeat_str(str, repeat_count) {
    var arr = new Array(--repeat_count);
    while (repeat_count != 0)
      arr[--repeat_count] = str;
    return str.concat.apply(str, arr);
  }
  str = new RegExp(str);
  str.test('foo');
`);



Backtrace:

 received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xf51ffb40 (LWP 10574)]
0x080e7b68 in js::detail::BumpChunk::setBump (this=0xf4b52000, ptr=0xf4b52390) at js/src/ds/LifoAlloc.h:83
#0  0x080e7b68 in js::detail::BumpChunk::setBump (this=0xf4b52000, ptr=0xf4b52390) at js/src/ds/LifoAlloc.h:83
#1  0x08232730 in js::detail::BumpChunk::tryAlloc (n=56, this=0xf4b52000) at js/src/ds/LifoAlloc.h:140
#2  js::LifoAlloc::allocImpl (this=0xf792d4c0, n=56) at js/src/ds/LifoAlloc.h:222
#3  0x0829b696 in js::LifoAlloc::allocInfallible (this=0xf792d4c0, n=56) at js/src/ds/LifoAlloc.h:291
#4  0x08a2f60c in js::LifoAlloc::newInfallible<js::irregexp::ActionNode, js::irregexp::ActionNode::ActionType, js::irregexp::RegExpNode*&>(js::irregexp::ActionNode::ActionType&&, js::irregexp::RegExpNode*&) (this=0xf792d4c0) at js/src/ds/LifoAlloc.h:455
#5  0x08a191b0 in js::irregexp::ActionNode::StorePosition (on_success=0xf4b52320, is_capture=true, reg=<optimized out>) at js/src/irregexp/RegExpEngine.cpp:665
#6  js::irregexp::RegExpCapture::ToNode (body=0xf4c738d8, index=6616, compiler=0xf51fc6b0, on_success=0xf4b52320) at js/src/irregexp/RegExpEngine.cpp:2219
#7  0x08a1922a in js::irregexp::RegExpCapture::ToNode (this=0xf4c738e8, compiler=0xf51fc6b0, on_success=0xf4b52320) at js/src/irregexp/RegExpEngine.cpp:2208
#8  0x08a14f64 in js::irregexp::RegExpAlternative::ToNode (this=0xf4c73928, compiler=0xf51fc6b0, on_success=0xf4b52320) at js/src/irregexp/RegExpEngine.cpp:2230
#9  0x08a191c8 in js::irregexp::RegExpCapture::ToNode (body=0xf4c73928, index=6615, compiler=0xf51fc6b0, on_success=0xf4b522e8) at js/src/irregexp/RegExpEngine.cpp:2220
#10 0x08a1922a in js::irregexp::RegExpCapture::ToNode (this=0xf4c73938, compiler=0xf51fc6b0, on_success=0xf4b522e8) at js/src/irregexp/RegExpEngine.cpp:2208
[...]
#126 0x08a191c8 in js::irregexp::RegExpCapture::ToNode (body=0xf4c74568, index=6576, compiler=0xf51fc6b0, on_success=0xf4b51a20) at js/src/irregexp/RegExpEngine.cpp:2220
#127 0x08a1922a in js::irregexp::RegExpCapture::ToNode (this=0xf4c74578, compiler=0xf51fc6b0, on_success=0xf4b51a20) at js/src/irregexp/RegExpEngine.cpp:2208
eax	0x38	56
ebx	0x8d0bff4	147898356
ecx	0xf4b52010	-189456368
edx	0xf4b53000	-189452288
esi	0xf4b52358	-189455528
edi	0xf4b52000	-189456384
ebp	0xf50e0028	4111335464
esp	0xf50dffd0	4111335376
eip	0x80e7b68 <js::detail::BumpChunk::setBump(void*)+88>
=> 0x80e7b68 <js::detail::BumpChunk::setBump(void*)+88>:	movl   $0x4d430001,-0x34(%ebp)
   0x80e7b6f <js::detail::BumpChunk::setBump(void*)+95>:	xor    %edx,%edx


This looks like an over-recursion. Marking as fuzzblocker because over-recursions tend to generate hard to match crashes.

Comment 2

[Nicolas B. Pierron [:nbp]]

We probably need some way to check for over recursions under irregexp::CompilePattern, in particular in:
 - js::irregexp::RegExpDisjunction::ToNode
 - js::irregexp::RegExpQuantifier::ToNode
 - js::irregexp::RegExpLookahead::ToNode
 - js::irregexp::RegExpCapture::ToNode
 - js::irregexp::RegExpAlternative::ToNode

Currently we seem to have already 2 different mechanism for avoiding stack overflow:
 - http://searchfox.org/mozilla-central/search?q=symbol:_ZN2js8irregexp19BoyerMooreLookahead17CheckOverRecursedEv&redirect=false
 - http://searchfox.org/mozilla-central/search?q=symbol:_ZN2js8irregexp10RegExpNode13LimitVersionsEPNS0_14RegExpCompilerEPNS0_5TraceE&redirect=false
 & http://searchfox.org/mozilla-central/search?q=symbol:T_RecursionCheck&redirect=false

I guess we could factor the CheckOverRecursed function under the RegExpCompiler, and use it in the ToNode functions, or we could reuse the counter which is already on the RegExpCompiler.

A third option would be to guard for enough space in the CompilePattern function, and check that we do not generate any pattern which would recurse too deeply while we are under the RegExpParser<…>::ParseDisjunction function.

Comment 3

[Brian Hackett [Laid off!]]

The simplest option would be to use CheckOverRecursed and make ToNode infallible.  It's strange this recursion is present, though, as irregexp seems to try to avoid direct recursion wherever possible.

Comment 4

[Nicolas B. Pierron [:nbp]]

Attachment: irregexp: Report JS Errors on stack overflow.

This patch add checks for over recursions, which can happen as the irregexp
parser creates a tree structure of captures & look-ahead bodies.  These
structures are then traversed with a non-tail optimizable recursions, which
consume stack space and cause a stack overflow in the allocator.

On stack overflow, the on_sucess node is returned, and the flag
reg_exp_too_big is checked to return the same error message as
the RegExpCompiler::Assemble function.

Comment 5

[Brian Hackett [Laid off!]]

Comment on attachment 8864243 [details] [diff] [review]
irregexp: Report JS Errors on stack overflow.

Thanks!

Comment 6

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/9273e5b90f29
irregexp: Report JS Errors on stack overflow. r=bhackett

Comment 7

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/9273e5b90f29