714616 - Assertion failure: (ptrBits & 0x7) == 0, at ../../jsval.h:873 or Crash [@ compartment] or [@ js::array_shift]

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

The following test crashes/asserts on mozilla-central revision d98fbf3cbd71 (options -m -n -a):


array1 = new Array();
size   = 10;
for (i = 0; i < size; (array1.length)++)
{
  array1.push(array1.shift());
}


Backtrace of crash on opt64:

Program received signal SIGSEGV, Segmentation fault.
compartment (length=8, this=<value optimized out>) at /srv/repos/mozilla-central/js/src/jsgc.h:948
948         return arenaHeader()->compartment;
(gdb) bt
#0  compartment (length=8, this=<value optimized out>) at /srv/repos/mozilla-central/js/src/jsgc.h:948
#1  writeBarrierPre (length=8, this=<value optimized out>) at ../gc/Barrier-inl.h:123
#2  pre (length=8, this=<value optimized out>) at ../gc/Barrier-inl.h:150
#3  ~HeapValue (length=8, this=<value optimized out>) at ../gc/Barrier-inl.h:99
#4  prepareElementRangeForOverwrite (length=8, this=<value optimized out>) at ../jsobjinlines.h:520
#5  JSObject::setDenseArrayInitializedLength (length=8, this=<value optimized out>) at ../jsobjinlines.h:572
#6  0x000000000042394b in js::array_shift (cx=0x8dd310, argc=<value optimized out>, vp=0x7ffff63fb0a8) at /srv/repos/mozilla-central/js/src/jsarray.cpp:2436
#7  0x0000000000481b39 in CallJSNative (cx=0x8dd310, args=..., construct=<value optimized out>) at ../jscntxtinlines.h:311
#8  js::InvokeKernel (cx=0x8dd310, args=..., construct=<value optimized out>) at /srv/repos/mozilla-central/js/src/jsinterp.cpp:524
#9  0x00000000005eba5b in js::mjit::stubs::SlowCall (f=..., argc=0) at /srv/repos/mozilla-central/js/src/methodjit/InvokeHelpers.cpp:196
#10 0x00007ffff7f42f1f in ?? ()
#11 0x00007ffff7f43186 in ?? ()
#12 0x0000000000000001 in ?? ()
#13 0x0000000000000000 in ?? ()


On 32 bit, the assert is: Assertion failure: addr % Cell::CellSize == 0, at ../../jsgc.h:822

Comment 1

[David Mandelin [:dmandelin]]

What OS is that? I can run for 60 seconds without crashing on a737cc816eec.

Comment 2

[David Mandelin [:dmandelin]]

(In reply to David Mandelin from comment #1)
> What OS is that? I can run for 60 seconds without crashing on a737cc816eec.

Duh, forgot to say what OS I'm using: Win 7, 32-bit JS shell debug build.

Comment 3

[Christian Holler (:decoder)]

I tested this on Linux using 32/64 bit debug shells (opt64 also crashes as shown above).

Comment 4

[Daniel Veditz [:dveditz]]

decoder: is this a regression?

Comment 5

[Christian Holler (:decoder)]

(In reply to Daniel Veditz from comment #4)
> decoder: is this a regression?

Pretty sure it is, yes.

Comment 6

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

> > decoder: is this a regression?
> 
> Pretty sure it is, yes.

I can also reproduce the assertion on 32-bit js debug shell on Mac 10.7 m-c changeset c713003d3226.

autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   82124:66d577078bb1
user:        Bill McCloskey
date:        Tue Dec 06 14:27:50 2011 -0800
summary:     Bug 707750 - Invoke write barrier for setDenseArrayInitializedLength (r=bhackett)

Comment 7

[David Mandelin [:dmandelin]]

Looked at this for a bit. We end up calling the write barrier on bogus memory off the end of the array. It's somehow caused by the sequence of length changes that happen with the pushes, shifts, and length-sets.

Comment 8

[David Mandelin [:dmandelin]]

Attachment: WIP

Got this with a lot of help from Bill. This gets us most of the way there, but I still need some advice wrt the methodjit.

Cause: The bug is basically in array_shift, where it first moves elements down, then sets the array length. Let's say that at first, the array has initializedLength=3, length=4, and capacity=6, so that the elements are like this:

 v1 v2 v3 xx   // xx is uninitialized memory

In the current code, we move |length| elements down, giving this:

 v2 v3 xx xx   // xx is uninitialized memory

Next we decrement initializedLength to 2. This activates the write barrier for the element at index 2, but that's |xx|, so it potentially crashes.

But even more fundamentally, moving |length| elements is just wrong, because if |capacity < length|, the move could crash right away. We can fix this by instead moving |initializedLength-1| elements.

Methodjit question: So far, so good, but Bill further recommended asserting in moveDenseArrayElements that we aren't moving elements from beyond initializedLength, to make sure nothing like this happens elsewhere. 

It turns out the assert trips on JM+TI's ArrayShift when called for shift. The problem is that the jitcode decrements initializedLength and after that calls the stub ArrayShift, which calls moveDenseArrayElements. In the example above, on entry to ArrayShift initializedLength is 2 and length is 3. ArrayShift calls moveDenseArrayElements(dest=0, start=1, len=2). That's the correct set of elements to move, but it trips the assert, even though it's actually safe because "really" we still have 3 elements initialized.

If we want to keep the strengthened assert, what's the best way to handle this in the methodjit? One thing I'm wondering about is why we have the jitcode for |shift| if it has to call a stub anyway. Should we just not use the jitcode for shift? Or should we not decrement in the jitcode. I think one way to paper over would be to increment initializedLength in ArrayShift before the move, then decrement it, which should work but is kind of ugly. Brian?

Comment 9

[Brian Hackett [Laid off!]]

(In reply to David Mandelin from comment #8)
> If we want to keep the strengthened assert, what's the best way to handle
> this in the methodjit? One thing I'm wondering about is why we have the
> jitcode for |shift| if it has to call a stub anyway. Should we just not use
> the jitcode for shift? Or should we not decrement in the jitcode. I think
> one way to paper over would be to increment initializedLength in ArrayShift
> before the move, then decrement it, which should work but is kind of ugly.
> Brian?

The stub used for shift is basically just a memmove, and even though a call is required there is a good savings from doing all the array maintenance in jitcode (numbers in bug 692847).  Updating the initialized length before the call is good because it makes shift() very similar to pop(), and faster since the registers holding the object/elements/etc. are clobbered by the call.

I think it might be better to just call a moveDenseArrayElementsForArrayShift or something which skips the assert, and comment on why it is needed.

Comment 10

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

I just noticed that we bail out of mjit::Compiler::compileArrayPopShift if write barriers are enabled. So we're wasting time by dealing with barriers at all in this call. Perhaps the best thing would be to add moveDenseArrayElementsUnbarriered. It would assert that write barriers aren't needed in the current compartment and then just do a memmove. Then the ArrayShift stub would call this. It fixes the bug and it's a speedup.

Comment 11

[David Mandelin [:dmandelin]]

Attachment: Patch

Comment 12

[David Mandelin [:dmandelin]]

Attachment: Patch v2 (had to remove a couple of ctrl+Ms)

Thanks for the hints.

Comment 13

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Comment on attachment 592947 [details] [diff] [review]
Patch v2 (had to remove a couple of ctrl+Ms)

Review of attachment 592947 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks, seems good.

::: js/src/jsobjinlines.h
@@ +628,5 @@
>  
> +inline void
> +JSObject::moveDenseArrayElementsUnbarriered(uintN dstStart, uintN srcStart, uintN count)
> +{
> +    JS_ASSERT(!compartment()->needsBarrier());

Could you put the original assertions from moveDenseArrayElements here (about the capacity)?

Comment 14

[David Mandelin [:dmandelin]]

http://hg.mozilla.org/integration/mozilla-inbound/rev/47a3904d3523

Oops, forgot to add those asserts, I'll push a followup later.

Comment 15

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/47a3904d3523

Leaving open for comment 14.

Comment 16

[David Mandelin [:dmandelin]]

Attachment: Followup patch (adds assertions)

Comment 17

[David Mandelin [:dmandelin]]

http://hg.mozilla.org/integration/mozilla-inbound/rev/18df24d8df7e

Merging this to m-c fixes the bug.

Comment 18

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

http://hg.mozilla.org/mozilla-central/rev/18df24d8df7e

Comment 19

[Christian Holler (:decoder)]

A testcase for this bug was automatically identified at js/src/jit-test/tests/basic/bug714616.js.