Bug 138118 – Assert that Array elements not copied when changing shape to ArrayStorage type are indeed holes

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Mark Lam]

When we convert a dense holey array into the ArrayStorage shape, the new holes in the new array gets garbage.

The following test is run with Heap::tryAllocateStorage() modified to scribble all over newly allocated buffers with the value 0xbaddda4a.  The test basically sets up a hole DoubleShape array, and then runs Array.unshift() on it to force it to change to the ArrayStorage shape.  Thereafter, the test dumps the values of the array again to look for the holes.

The test code:
=============
function doubleArray() {
    var arr = [];
    arr[0] = 0.1;
    arr[1] = 1.1;
    arr[2] = 2.1;
    arr[3] = 3.1;
    // arr[4] = hole;
    // arr[5] = hole;
    arr[6] = 6.1;
    arr[7] = 7.1;
    arr[8] = 8.1;
    return arr;
}

function test(name, arr, newElement) {
    print(name + " BEFORE unshift:");
    for (var i = 0; i < arr.length; i++)
        print("   arr[" + i + "] = " + arr[i]);

    arr.unshift(newElement);
    print(name + " AFTER unshift:");
    for (var i = 0; i < arr.length; i++)
        print("   arr[" + i + "] = " + arr[i]);
}
test("double array", doubleArray(), 100.5);

The output:
==========
double array BEFORE unshift:
   arr[0] = 0.1
   arr[1] = 1.1
   arr[2] = 2.1
   arr[3] = 3.1
   arr[4] = undefined
   arr[5] = undefined
   arr[6] = 6.1
   arr[7] = 7.1
   arr[8] = 8.1
   arr[9] = undefined
double array AFTER unshift:
   arr[0] = 100.5
   arr[1] = 0.1
   arr[2] = 1.1
   arr[3] = 2.1
   arr[4] = 3.1
   arr[5] = -3.7291244322514128e-25
   arr[6] = -3.7291244322514128e-25
   arr[7] = 6.1
   arr[8] = 7.1
   arr[9] = 8.1

Note that the resultant arr[5] and arr[6] which should be undefined (because of the holes) now contain junk.

[Radar WebKit Bug Importer]

<rdar://problem/18791403>

[Mark Lam]

Created attachment 240528 [details]
the patch.

[Mark Hahnenberg]

Comment on attachment 240528 [details]
the patch.

R=me

[Mark Hahnenberg]

Is there a test you could add that would reliably trigger the bug without having to make the tryAllocateStorage modification?

[Mark Lam]

(In reply to comment #4)
> Is there a test you could add that would reliably trigger the bug without
> having to make the tryAllocateStorage modification?

Maybe, but it will require a lot of allocations and GCs to create allocatable memory filled with junk that we can allocate from.  Such a test will probably not be short running, and is flaky at best.

The test will also have to rely on operations like Array.unshift() to trigger the conversion to ArrayStorage shape.  Hence, the test is not general and will only be testing this specific case that has been fixed, and therefore have limited utility.  We’re also not likely to regress this specific piece of code.  Hence, I’m going to forego the test and land this without it for now.

[Mark Lam]

Thanks for the review.  Landed in r175249: <http://trac.webkit.org/r175249>.

[Mark Hahnenberg]

(In reply to comment #5)
> (In reply to comment #4)
> > Is there a test you could add that would reliably trigger the bug without
> > having to make the tryAllocateStorage modification?
> 
> Maybe, but it will require a lot of allocations and GCs to create
> allocatable memory filled with junk that we can allocate from.  Such a test
> will probably not be short running, and is flaky at best.

Is it even possible to create a storage allocation with uninitialized memory? I thought it was guaranteed that any CopiedSpace allocation was already pre-zeroed.

There's an invariant with array backing stores that requires they be zeroed when they're allocated. If it's possible to get random garbage in your array backing store, that sounds like a bug in the storage allocator.

[Mark Lam]

(In reply to comment #7)
> There's an invariant with array backing stores that requires they be zeroed
> when they're allocated. If it's possible to get random garbage in your array
> backing store, that sounds like a bug in the storage allocator.

Interesting.  I’ll double check this in the code.

[Geoffrey Garen]

Seems like you should be able to test this with a double array, since a zero-initialized double array will see zeros instead of holes.

[Mark Lam]

(In reply to comment #9)
> Seems like you should be able to test this with a double array, since a
> zero-initialized double array will see zeros instead of holes.

That won't work.  The scenario here requires a conversion of the double array to an ArrayStorage array.  In the ArrayStorage array, 0s are holes.

[WebKit Commit Bot]

Re-opened since this is blocked by bug 138138

[Geoffrey Garen]

If zero is hole in ArrayStorage, and the GC zero-initializes ArrayStorage, then this patch is wrong and you should roll it out.

An alternative patch, which might be fine, would ASSERT that all indices that were holes in the input are holes in the output.

[Mark Lam]

For the record, the patch was causing some JS test failures because the assertion I added in JSObject::convertUndecidedToArrayStorage() was firing.  Looks like the publicLength is not 0 even though JSObject::convertUndecidedToArrayStorage() does not copy any array elements.  I may have misunderstood how Undecided arrays work.  Will investigate further.

[Filip Pizlo]

(In reply to comment #13)
> For the record, the patch was causing some JS test failures because the
> assertion I added in JSObject::convertUndecidedToArrayStorage() was firing. 
> Looks like the publicLength is not 0 even though
> JSObject::convertUndecidedToArrayStorage() does not copy any array elements.
> I may have misunderstood how Undecided arrays work.  Will investigate
> further.

Undecided can come into play when you do something like:

var a = []; // It's IsArray + Undecided because you haven't stored anything into it.
a.length = 42; // It's still IsArray + Undecided because you still haven't stored anything into it, and the publicLength is 42.

[Mark Lam]

I was wrong about heap memory not being zeroed out on allocation.  The backing store for Arrays are allocated from the CopiedSpace (aka storage space), and those allocations are zero filled.  Changing this patch to assert that the expected holes are holes.

[Mark Lam]

Created attachment 243639 [details]
updated patch

[Michael Saboff]

Comment on attachment 243639 [details]
updated patch

View in context: https://bugs.webkit.org/attachment.cgi?id=243639&action=review

> Source/JavaScriptCore/runtime/JSObject.cpp:853
> +        if (value == value) {

Shouldn't this always be true?  Seems like a bug.

[Michael Saboff]

Comment on attachment 243639 [details]
updated patch

View in context: https://bugs.webkit.org/attachment.cgi?id=243639&action=review

r=me

>> Source/JavaScriptCore/runtime/JSObject.cpp:853
>> +        if (value == value) {
> 
> Shouldn't this always be true?  Seems like a bug.

So this is a not a NaN check.

[WebKit Commit Bot]

Comment on attachment 243639 [details]
updated patch

Clearing flags on attachment: 243639

Committed r177657: <http://trac.webkit.org/changeset/177657>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.