Crash [@ array_toString_sub] with huge array

RESOLVED FIXED

Status

()

Core
JavaScript Engine
--
critical
RESOLVED FIXED
8 years ago
5 years ago

People

(Reporter: Jesse Ruderman, Assigned: luke)

Tracking

(Blocks: 1 bug, {crash, testcase})

Trunk
x86
Mac OS X
crash, testcase
Points:
---
Bug Flags:
wanted1.9.2 +
in-testsuite -

Firefox Tracking Flags

(status1.9.2 beta1-fixed)

Details

(Whiteboard: [sg:critical?] fixed-in-tracemonkey, crash signature)

Attachments

(2 attachments, 1 obsolete attachment)

(Reporter)

Description

8 years ago
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.
(Assignee)

Comment 1

8 years ago
Created attachment 394428 [details] [diff] [review]
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.
Assignee: general → lw
Status: NEW → ASSIGNED
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
(Reporter)

Comment 3

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

Comment 4

8 years ago
Created attachment 394558 [details]
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

8 years ago
(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?
(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
(Assignee)

Comment 7

8 years ago
Created attachment 394598 [details] [diff] [review]
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)".
Attachment #394428 - Attachment is obsolete: true
(Reporter)

Comment 8

8 years ago
Yes, this patch takes it from crashing to saying "typein:1: InternalError: allocation size overflow" :)
(Assignee)

Comment 9

8 years ago
Thanks for testin' ma patches!
(Assignee)

Updated

8 years ago
Attachment #394598 - Flags: review?(jwalden+bmo)
(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
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
(Assignee)

Comment 12

8 years ago
(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.
(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
(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
(In reply to comment #11)
> MTBF = Mozilla Template Base Framework ;-).

Mozilla Framework Built on Templates for MFBT, please.
(Assignee)

Comment 16

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

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

Updated

8 years ago
Whiteboard: [sg:critical?]
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 on attachment 394598 [details] [diff] [review]
fix

Oh, size_t, righto.
Attachment #394598 - Flags: review?(jwalden+bmo) → review+
(Assignee)

Comment 19

8 years ago
http://hg.mozilla.org/tracemonkey/rev/98b5919daa4a
(Assignee)

Comment 20

8 years ago
(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.
(In reply to comment #19)
> http://hg.mozilla.org/tracemonkey/rev/98b5919daa4a

Adding "fixed-in-tracemonkey" to whiteboard.
Whiteboard: [sg:critical?] → [sg:critical?] fixed-in-tracemonkey

Comment 22

8 years ago
http://hg.mozilla.org/mozilla-central/rev/98b5919daa4a
Status: ASSIGNED → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED

Comment 23

8 years ago
http://hg.mozilla.org/releases/mozilla-1.9.2/rev/96c9e11b8596
status1.9.2: --- → beta1-fixed
Flags: wanted1.9.2+
Crash Signature: [@ array_toString_sub]
Group: core-security
Flags: in-testsuite-
You need to log in before you can comment on or make changes to this bug.