510319 - Crash [@ array_toString_sub] with huge array

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jesse Ruderman]

void("" + Array(0xB504F332));

Takes about 2 minutes and then crashes [@ array_toString_sub] trying to access 0x81000000.  Tested using the javascript engine shell with JIT disabled.

Comment 1

[Luke Wagner [:luke]]

Attachment: potential fix

Ugh, nice find.  I tested your example input on a variety of sizes in both debug and optimized builds and was unable to get anything but proper  exceptions.  However, on tracing all growth paths for overflow, I found a regression where I do an unchecked addition (I got caught up in "cleaning" up the code).  Is your crash reproducible?  If so, could you see if this patch fixes it?

The patch also adds some comments, gives more helpful identifier names, and factors checking into one place.

Comment 2

[Brendan Eich [:brendan]]

Firefox 3 era js shell, not exactly pure:

js> void("" + Array(0xB504F332));
js(26277) malloc: *** mmap(size=2148061184) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
typein:1: out of memory

/be

Comment 3

[Jesse Ruderman]

The crash is 100% reproducible on my machine.  The patch in comment 1 does not fix it :(

Comment 4

[Luke Wagner [:luke]]

Attachment: see for yourself

I was able to get the reported crash reproducibly on OS X.

So, short story is: pointer subtraction can overflow, and you are actually hitting a GCC (and probably every other compiler) bug that, if fixed, would massively slow down pointer arithmetic, and so should not be fixed.

Allow me to explain.

Normally, the OS fails allocation before a dynamic buffer is big enough that the most significant bit of its size as a word-sized integer is set.  However, OS X seems to allow such allocations to succeed.  Now, if p and q are pointers, (p - q) can either be + or -, so ptrdiff_t must be signed.  The C++ standard says (5.7.6) that the compiler should compute the value of subtracting the indices of the elements in the underlying array, and if this doesn't fit into ptrdiff_t, the result is undefined.  Thus, if I have an array of 2 1.1GB objects, and subtract end - begin, I should get 2.  What GCC does is subtract the pointers as if they were char* (getting byte difference), and then divide by sizeof(T) (with a shift).  Hence, the aformentioned subtraction will overflow (thus turning to a low negative) and then shift (thus giving -1).  You can see each step of this illustrated in the attached demo.

(Note: even with no GCC bug, there is still a bug in my code: a JSTempVector<char> or other 1-byte type can overflow ptrdiff_t.)

For the fix, instead of auditing all subtractions that can overflow (which I did; there are only a few), another idea is to manually fail when growing if future pointer subtraction of (end() - begin()) would overflow (GCC bug included).  This would be good because, maybe I'm just naive, but I think this is an extremely subtle bug and even if JSTempVector doesn't have it, someone using JSTempVector might.  I mean, who asks "could this pointer *subtraction* overflow"?  In fact, it would be nice if we could tweak malloc() to fail in this situation.

Comment 5

[Bob Clary [:bc] (inactive)]

(In reply to comment #2)
> Firefox 3 era js shell, not exactly pure:
> 
> js> void("" + Array(0xB504F332));
> js(26277) malloc: *** mmap(size=2148061184) failed (error code=12)
> *** error: can't allocate region
> *** set a breakpoint in malloc_error_break to debug
> typein:1: out of memory

I have a lot of these type errors on Mac. I thought the abormal exit on out of memory was ok. Should I have been filing bugs on them?

Comment 6

[Brendan Eich [:brendan]]

(In reply to comment #5)
> (In reply to comment #2)
> > Firefox 3 era js shell, not exactly pure:
> > 
> > js> void("" + Array(0xB504F332));
> > js(26277) malloc: *** mmap(size=2148061184) failed (error code=12)
> > *** error: can't allocate region
> > *** set a breakpoint in malloc_error_break to debug
> > typein:1: out of memory
> 
> I have a lot of these type errors on Mac. I thought the abormal exit on out of
> memory was ok. Should I have been filing bugs on them?

No, I misread -- that seems to be a noisy OOM report. Sorry for false alarum!

/be

Comment 7

[Luke Wagner [:luke]]

Attachment: fix

This patch a language exception for both opt and debug builds on OS X.  Does it fix it for you?

I used the strategy of "fail if allocating a buffer big enough to potentially cause the abovementioned ptrdiff_t overflow (including the compiler bug)".

Comment 8

[Jesse Ruderman]

Yes, this patch takes it from crashing to saying "typein:1: InternalError: allocation size overflow" :)

Comment 9

[Luke Wagner [:luke]]

Thanks for testin' ma patches!

Comment 10

[Brendan Eich [:brendan]]

(In reply to comment #4)
> This would be good because, maybe I'm just naive, but I think this
> is an extremely subtle bug and even if JSTempVector doesn't have it, someone
> using JSTempVector might.

Very wise, not naive.

> I mean, who asks "could this pointer *subtraction* overflow"?

JS VM hackers ;-).

> In fact, it would be nice if we could tweak malloc() to fail in this
> situation.

Please file a bug on this, it is a good idea.

/be

Comment 11

[Brendan Eich [:brendan]]

Manly template usage, could we use it elsewhere? Could put it in a separate header included by jsvector.h. WTF = WebKit Template Framework, MTBF = Mozilla Template Base Framework ;-).

The C luddite in me wants to ask whether JS_STATIC_ASSERT is no worse in effect, if not readability (once you wrap your brains around templates).

/be

Comment 12

[Luke Wagner [:luke]]

(In reply to comment #10)
> > In fact, it would be nice if we could tweak malloc() to fail in this
> > situation.
> 
> Please file a bug on this, it is a good idea.

Awesome!  Which component?  JS Engine or Mozilla-wide?

(In reply to comment #11)
> Manly template usage, could we use it elsewhere? Could put it in a separate
> header included by jsvector.h. 

In fact that is already in the JSHashMap patch in bug 506410!

> WTF = WebKit Template Framework, MTBF = Mozilla Template Base Framework ;-).

Nice, MTBF is awesome.  Hehe, what about Mozilla Template Vault?

> The C luddite in me wants to ask whether JS_STATIC_ASSERT is no worse in
> effect, if not readability (once you wrap your brains around templates).

The luddite is right; I forgot about JS_STATIC_ASSERT.  I'll include that the next version of the patch.

Comment 13

[Brendan Eich [:brendan]]

(In reply to comment #12)
> (In reply to comment #10)
> > > In fact, it would be nice if we could tweak malloc() to fail in this
> > > situation.
> > 
> > Please file a bug on this, it is a good idea.
> 
> Awesome!  Which component?  JS Engine or Mozilla-wide?

Core / jemalloc for a start. We don't wrap OS X's malloc, but we might replace it with jemalloc. Need advice and updates from sayrer and others on this.

/be

Comment 14

[Brendan Eich [:brendan]]

(In reply to comment #12)
> > WTF = WebKit Template Framework, MTBF = Mozilla Template Base Framework ;-).
> 
> Nice, MTBF is awesome.  Hehe, what about Mozilla Template Vault?

(Money for nothing, chicks for free.)

/be

Comment 15

[Mike Shaver (:shaver emeritus)]

(In reply to comment #11)
> MTBF = Mozilla Template Base Framework ;-).

Mozilla Framework Built on Templates for MFBT, please.

Comment 16

[Luke Wagner [:luke]]

(In reply to comment #13)
Righto, bug 510691.

(In reply to comment #15)
Did not know that acronym; righteous.

Comment 17

[Jeff Walden [:Waldo]]

Comment on attachment 394598 [details] [diff] [review]
fix

>diff --git a/js/src/jsvector.h b/js/src/jsvector.h
> template <class T, size_t N>
> inline bool
> JSTempVector<T,N>::reserve(size_t request)
> {
>     ReentrancyGuard g(*this);
>     if (usingInlineStorage()) {
>         if (request > sInlineCapacity)
>-            return convertToHeapStorage(request);
>+            return convertToHeapStorage(request - inlineSize());
>     } else {
>         if (request > heapCapacity())
>-            return growHeapCapacityTo(request);
>+            return growHeapStorageBy(request - heapSize());
>     }
>     return true;
> }

This doesn't seem to be used anywhere yet, but shouldn't there be an overflow check on the second subtraction?

Comment 18

[Jeff Walden [:Waldo]]

Comment on attachment 394598 [details] [diff] [review]
fix

Oh, size_t, righto.

Comment 19

[Luke Wagner [:luke]]

http://hg.mozilla.org/tracemonkey/rev/98b5919daa4a

Comment 20

[Luke Wagner [:luke]]

(In reply to comment #12)
> > The C luddite in me wants to ask whether JS_STATIC_ASSERT is no worse in
> > effect, if not readability (once you wrap your brains around templates).
> 
> The luddite is right; I forgot about JS_STATIC_ASSERT.  I'll include that the
> next version of the patch.

So there is a reason: JS_STATIC_ASSERT uses 'extern' if there is no __COUNTER__ #defined, which won't work for in-class assertions.  (Witness my firebombing of the tinderbox this morning.)  Since the assertion involves template parameters, it has to be in-class.

Comment 21

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

(In reply to comment #19)
> http://hg.mozilla.org/tracemonkey/rev/98b5919daa4a

Adding "fixed-in-tracemonkey" to whiteboard.

Comment 22

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/98b5919daa4a

Comment 23

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/96c9e11b8596