Last Comment Bug 341956 - GC hazards in jsarray.c: unrooted atoms for large index
: GC hazards in jsarray.c: unrooted atoms for large index
Status: VERIFIED FIXED
[sg:critical]
: verified1.8.0.5, verified1.8.1
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: -- critical (vote)
: mozilla1.8.1beta2
Assigned To: Igor Bukanov
:
:
Mentors:
Depends on:
Blocks: 344320
  Show dependency treegraph
 
Reported: 2006-06-18 14:59 PDT by Igor Bukanov
Modified: 2007-02-08 21:36 PST (History)
5 users (show)
dveditz: blocking1.7.14?
dveditz: blocking‑aviary1.0.9?
darin.moz: blocking1.8.1+
dveditz: blocking1.8.0.5+
bob: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Fix (14.17 KB, patch)
2006-06-28 15:09 PDT, Igor Bukanov
mrbkap: review+
brendan: review+
Details | Diff | Splinter Review
Fix for 1.8.1, 1.8.0 branches (13.55 KB, patch)
2006-06-29 01:32 PDT, Igor Bukanov
no flags Details | Diff | Splinter Review
Fix v2 (13.62 KB, patch)
2006-06-29 12:03 PDT, Igor Bukanov
no flags Details | Diff | Splinter Review
Fix v2b (13.62 KB, patch)
2006-06-29 12:20 PDT, Igor Bukanov
mrbkap: review+
brendan: superreview+
Details | Diff | Splinter Review
Fix v2c (13.62 KB, patch)
2006-06-30 11:32 PDT, Igor Bukanov
no flags Details | Diff | Splinter Review
Minimal fix (12.62 KB, patch)
2006-06-30 16:03 PDT, Igor Bukanov
mrbkap: review+
brendan: superreview+
Details | Diff | Splinter Review
Minimal fix (patch to commit with shrinked comments) (11.24 KB, patch)
2006-07-01 09:05 PDT, Igor Bukanov
no flags Details | Diff | Splinter Review
Minimal fix - version for 1.8.0 and 1.8.1 branches (11.36 KB, patch)
2006-07-01 09:32 PDT, Igor Bukanov
dveditz: approval1.8.0.5+
mtschrep: approval1.8.1+
Details | Diff | Splinter Review
js1_5/GC/regress-341956.js (3.11 KB, text/plain)
2006-07-06 08:52 PDT, Bob Clary [:bc:]
no flags Details
js1_5/GC/regress-341956-01.js (3.18 KB, text/plain)
2006-07-06 12:44 PDT, Bob Clary [:bc:]
no flags Details
js1_5/GC/regress-341956-02.js (2.92 KB, text/plain)
2006-07-06 12:45 PDT, Bob Clary [:bc:]
no flags Details
js1_5/GC/regress-341956-03.js (3.24 KB, text/plain)
2006-07-06 12:45 PDT, Bob Clary [:bc:]
no flags Details
1.0.x backport (5.62 KB, patch)
2006-08-08 08:17 PDT, Alexander Sack
no flags Details | Diff | Splinter Review

Description Igor Bukanov 2006-06-18 14:59:55 PDT
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 2006-06-28 15:09:40 PDT
Created attachment 227465 [details] [diff] [review]
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 2006-06-28 15:16:16 PDT
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 2006-06-29 01:18:19 PDT
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 2006-06-29 01:32:03 PDT
Created attachment 227518 [details] [diff] [review]
Fix for 1.8.1, 1.8.0 branches

This a fix version for 1.8.1 branch.
Comment 5 Igor Bukanov 2006-06-29 01:34:45 PDT
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 2006-06-29 01:37:56 PDT
(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 2006-06-29 01:39:44 PDT
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 2006-06-29 03:16:45 PDT
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] 2006-06-29 09:01:20 PDT
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 2006-06-29 09:25:37 PDT
(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] 2006-06-29 09:33:27 PDT
(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) 2006-06-29 10:13:12 PDT
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 2006-06-29 11:20:13 PDT
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 2006-06-29 12:03:18 PDT
Created attachment 227578 [details] [diff] [review]
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 2006-06-29 12:20:19 PDT
Created attachment 227583 [details] [diff] [review]
Fix v2b

Fixing mistypes in the new comments.
Comment 16 Igor Bukanov 2006-06-29 15:10:30 PDT
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) 2006-06-30 11:26:30 PDT
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 2006-06-30 11:32:19 PDT
Created attachment 227711 [details] [diff] [review]
Fix v2c

Patch to commit with the last spelling fixes.
Comment 19 Daniel Veditz [:dveditz] 2006-06-30 15:40:22 PDT
Comment on attachment 227711 [details] [diff] [review]
Fix v2c

approved for 1.8.0 branch, a=dveditz for drivers
Comment 20 Igor Bukanov 2006-06-30 16:03:47 PDT
Created attachment 227749 [details] [diff] [review]
Minimal fix

Here is a minimal patch without IndexToId optimization.
Comment 21 Igor Bukanov 2006-06-30 16:08:27 PDT
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] 2006-06-30 17:59:20 PDT
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 2006-07-01 09:05:41 PDT
Created attachment 227818 [details] [diff] [review]
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 2006-07-01 09:32:57 PDT
Created attachment 227820 [details] [diff] [review]
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] 2006-07-01 10:51:00 PDT
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 2006-07-01 12:30:31 PDT
I committed the patch from commnet 24 to the trunk.
Comment 27 Igor Bukanov 2006-07-01 18:06:04 PDT
Please note that until 2006-07-25 I would not be able to commit anything - vacation time.
Comment 28 Daniel Veditz [:dveditz] 2006-07-01 21:41:55 PDT
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) 2006-07-01 21:46:27 PDT
Fix chcked into the 1.8.0 branch.
Comment 30 Bob Clary [:bc:] 2006-07-06 08:52:22 PDT
Created attachment 228293 [details]
js1_5/GC/regress-341956.js
Comment 31 Igor Bukanov 2006-07-06 12:23:32 PDT
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:] 2006-07-06 12:44:25 PDT
Created attachment 228332 [details]
js1_5/GC/regress-341956-01.js

Sorry, I missed that.
Comment 33 Bob Clary [:bc:] 2006-07-06 12:45:06 PDT
Created attachment 228333 [details]
js1_5/GC/regress-341956-02.js
Comment 34 Bob Clary [:bc:] 2006-07-06 12:45:38 PDT
Created attachment 228334 [details]
js1_5/GC/regress-341956-03.js
Comment 35 Bob Clary [:bc:] 2006-07-06 23:40:16 PDT
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:] 2006-07-11 20:17:14 PDT
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] 2006-07-21 00:54:12 PDT
Not sure if this problem applies to the aviary/1.7 branch or not.
Comment 38 Igor Bukanov 2006-07-21 01:45:33 PDT
(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:] 2006-07-22 20:01:57 PDT
no longer crash in 1.8.1
verified fixed 1.8.1 win/mac(tel|ppc)/linux
Comment 40 Alexander Sack 2006-08-08 08:17:56 PDT
Created attachment 232727 [details] [diff] [review]
1.0.x backport

maybe incomplete .. though I hope not.
Comment 41 Bob Clary [:bc:] 2007-02-08 21:36:22 PST
/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

Note You need to log in before you can comment on or make changes to this bug.