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

RESOLVED FIXED in Firefox 55

Status

()

Core
JavaScript Engine
--
critical
RESOLVED FIXED
a year ago
8 months ago

People

(Reporter: decoder, Assigned: nbp)

Tracking

(Blocks: 1 bug, 4 keywords)

Trunk
mozilla55
x86
Linux
crash, jsbugmon, regression, testcase
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox52 unaffected, firefox-esr52 unaffected, firefox53 unaffected, firefox54 unaffected, firefox55 fixed)

Details

(Whiteboard: [jsbugmon:update,bisect][fuzzblocker], crash signature)

Attachments

(1 attachment)

(Reporter)

Description

a year ago
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.

Updated

a year ago
status-firefox52: --- → unaffected
status-firefox53: --- → unaffected
status-firefox54: --- → unaffected
Flags: needinfo?(nicolas.b.pierron)
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.
Flags: needinfo?(nicolas.b.pierron) → needinfo?(bhackett1024)
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.
Flags: needinfo?(bhackett1024)
Assignee: nobody → nicolas.b.pierron
Status: NEW → ASSIGNED
Created attachment 8864243 [details] [diff] [review]
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.
Attachment #8864243 - Flags: review?(bhackett1024)
Comment on attachment 8864243 [details] [diff] [review]
irregexp: Report JS Errors on stack overflow.

Thanks!
Attachment #8864243 - Flags: review?(bhackett1024) → review+

Comment 6

a year ago
Pushed by npierron@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/9273e5b90f29
irregexp: Report JS Errors on stack overflow. r=bhackett

Comment 7

a year ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/9273e5b90f29
Status: ASSIGNED → RESOLVED
Last Resolved: a year ago
status-firefox55: affected → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
status-firefox-esr52: --- → unaffected
Depends on: 1382449
You need to log in before you can comment on or make changes to this bug.