686912 - YARR related OOM crash during compilation of JS [@ JSC::Yarr::YarrPatternConstructor::copyDisjunction]

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

The following test causes a crash due to OOM on mozilla-central revision 569a45bfb71c (options -m -n). WARNING: With a 32 bit build this will consume the full 4 GB of memory before crashing, so ensure you use a 32 bit build and a machine with enough memory available.


var r1 = /(?:a(?:b(?:c(?:d(?:e(?:f(?:g(?:h(?:i(?:j(?:k(?:l(?:m(?:n(?:o(?:p(?:q(?:r(?:s(?:t(?:u(?:v(?:w(?:x(?:y(?:z(?:FooBar)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)/;
var r2 = /(?:a(?:b(?:c(?:d(?:e(?:f(?:g(?:h(?:i(?:j(?:k(?:l(?:FooBar){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}/;
var r3 = /(?:a(?:b(?:c(?:d(?:e(?:f(?:g(?:h(?:i(?:j(?:k(?:l(?:FooBar){2}){2}){2}){2}){2}){2}){2}){2}){2}){2}){2}){2}){2}/;
for each ( var r3 in this ) var foo;


The crash looks at first like an infinite recursion due to its large stack, but it isn't as Luke confirmed for me. We rather crash due to OOM inside YARR, causing a null pointer to be dereferenced:

Program received signal SIGSEGV, Segmentation fault.
0x083e0f4c in JSC::Yarr::YarrPatternConstructor::copyDisjunction (this=0xffffb92c, disjunction=0x4d2d7980, filterStartsWithBOL=false)
    at /srv/repos/jaegermonkey/js/src/yarr/YarrPattern.cpp:558
558                         newDisjunction->m_parent = disjunction->m_parent;
(gdb) print newDisjunction
$4 = (JSC::Yarr::PatternDisjunction *) 0x0
(gdb) l
553             for (unsigned alt = 0; alt < disjunction->m_alternatives.size(); ++alt) {
554                 PatternAlternative* alternative = disjunction->m_alternatives[alt];
555                 if (!filterStartsWithBOL || !alternative->m_startsWithBOL) {
556                     if (!newDisjunction) {
557                         newDisjunction = js::OffTheBooks::new_<PatternDisjunction>();
558                         newDisjunction->m_parent = disjunction->m_parent;
559                     }
560                     PatternAlternative* newAlternative = newDisjunction->addNewAlternative();
561                     for (unsigned i = 0; i < alternative->m_terms.size(); ++i)
562                         newAlternative->m_terms.append(copyTerm(alternative->m_terms[i], filterStartsWithBOL));
(gdb) bt
#0  0x083e0f4c in JSC::Yarr::YarrPatternConstructor::copyDisjunction (this=0xffffb92c, disjunction=0x4d2d7980, filterStartsWithBOL=false)
    at /srv/repos/jaegermonkey/js/src/yarr/YarrPattern.cpp:558
#1  0x083e10c6 in JSC::Yarr::YarrPatternConstructor::copyTerm (this=0xffffb92c, term=..., filterStartsWithBOL=false) at /srv/repos/jaegermonkey/js/src/yarr/YarrPattern.cpp:577
#2  0x083e0f96 in JSC::Yarr::YarrPatternConstructor::copyDisjunction (this=0xffffb92c, disjunction=0x4d2d7920, filterStartsWithBOL=false)
    at /srv/repos/jaegermonkey/js/src/yarr/YarrPattern.cpp:562
#3  0x083e10c6 in JSC::Yarr::YarrPatternConstructor::copyTerm (this=0xffffb92c, term=..., filterStartsWithBOL=false) at /srv/repos/jaegermonkey/js/src/yarr/YarrPattern.cpp:577
#4  0x083e0f96 in JSC::Yarr::YarrPatternConstructor::copyDisjunction (this=0xffffb92c, disjunction=0x4d2d68f0, filterStartsWithBOL=false)
...
#54 0x08089bf5 in js::RegExp::compile (this=0x84fecc0, cx=0x84fbb10, ts=0xffffc3c8) at /srv/repos/jaegermonkey/js/src/jsregexpinlines.h:511
...
#74 0x081b8220 in js::Compiler::compileScript (cx=0x84fbb10, scopeChain=0xf7400040, callerFrame=0x0, principals=0x0, tcflags=1073897472, chars=0x84ff0f0, length=581,
    filename=0xffffd20e "min.js", lineno=1, version=JSVERSION_ECMA_5, source=0x0, staticLevel=0) at /srv/repos/jaegermonkey/js/src/jsparse.cpp:1023


So this happens all during compilation, nothing is run yet.

Comment 1

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

decoder, I retried this with --ion-eager on 32-bit js shell on m-c rev 9afe2a1145bd, but I could no longer reproduce.

JM and the type inference option (-n?) have been removed, so perhaps this is no longer an issue, or is a dupe of bug 616491?

Comment 2

[Christian Holler (:decoder)]

This is not a dup of bug 616491 as mentioned in comment 0 (luke confirmed this). I think there is no reason why this issue should be gone, type inference and JM don't have anything to do with this, except that they might influence memory usage.

Someone with more knowledge of the code should probably check this and tell us if this analysis is right.

Comment 3

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(In reply to Christian Holler (:decoder) from comment #2)
> This is not a dup of bug 616491 as mentioned in comment 0 (luke confirmed
> this). I think there is no reason why this issue should be gone, type
> inference and JM don't have anything to do with this, except that they might
> influence memory usage.

Thanks, decoder.

> Someone with more knowledge of the code should probably check this and tell
> us if this analysis is right.

Setting needinfo? from Sean.

Comment 4

[Sean Stangl [:sstangl]]

Regular expressions are now lazily compiled -- you must execute them to trigger pattern compilation. The following modified version still segfaults:

> var r1 = /(?:a(?:b(?:c(?:d(?:e(?:f(?:g(?:h(?:i(?:j(?:k(?:l(?:m(?:n(?:o(?:p(?:q(?:r(?:s(?:t(?:u(?:v(?:w(?:x(?:y(?:z(?:FooBar)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)+)/;
> var r2 = /(?:a(?:b(?:c(?:d(?:e(?:f(?:g(?:h(?:i(?:j(?:k(?:l(?:FooBar){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}){0,2}/;
> var r3 = /(?:a(?:b(?:c(?:d(?:e(?:f(?:g(?:h(?:i(?:j(?:k(?:l(?:FooBar){2}){2}){2}){2}){2}){2}){2}){2}){2}){2}){2}){2}){2}/;
> r1.test("wat");
> r2.test("wat");
> r3.test("wat");

Comment 5

[Chris Peterson [:cpeterson]]

Gary: is this OOM still reproducible in Nightly 33? We replaced YARR with irregexp in Firefox 32 (bug 976446).

Sean's code in comment 4 hangs Firefox 30 on OS X, but Firefox 33 works just fine.

Comment 6

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

No, this issue is no longer reproducible, I've bisected to the irregexp landing: (tested using the testcase in comment 4)

autoBisect shows this is probably related to the following changeset:

The first good revision is:
changeset:   183413:43acd23f5a98
user:        Brian Hackett
date:        Thu May 15 16:48:21 2014 -0700
summary:     Bug 976446 - Add port of irregexp regexp engine, and use by default, r=jandem.