Last Comment Bug 369696 - "Assertion failure: map->depth > 0" in js_LeaveSharpObject
: "Assertion failure: map->depth > 0" in js_LeaveSharpObject
Status: VERIFIED FIXED
[sg:critical?] fixed-in-tracemonkey
: assertion, testcase, verified1.8.1.22, verified1.9.0.11, verified1.9.1
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: -- critical (vote)
: ---
Assigned To: Igor Bukanov
:
Mentors:
Depends on:
Blocks: 326633
  Show dependency treegraph
 
Reported: 2007-02-07 23:09 PST by Jesse Ruderman
Modified: 2012-04-09 11:17 PDT (History)
14 users (show)
sayrer: blocking1.9.1+
dveditz: blocking1.9.0.11+
dveditz: wanted1.9.0.x+
dveditz: blocking1.8.1.next+
dveditz: wanted1.8.1.x+
bob: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
map->depth++ consistency fix (805 bytes, patch)
2007-11-27 10:29 PST, Brian Crowder
no flags Details | Diff | Splinter Review
backtrace, normal and full (12.35 KB, text/plain)
2009-03-08 21:54 PDT, Gary Kwong [:gkw] [:nth10sd]
no flags Details
v1 (1.53 KB, patch)
2009-03-16 10:37 PDT, Igor Bukanov
brendan: review+
Details | Diff | Splinter Review
backported patch to 1.9.0.x (1.60 KB, patch)
2009-03-16 20:42 PDT, Gary Kwong [:gkw] [:nth10sd]
no flags Details | Diff | Splinter Review
backported patch to 1.9.0.x, v2 (1.60 KB, patch)
2009-03-16 20:46 PDT, Gary Kwong [:gkw] [:nth10sd]
igor: review+
samuel.sidler+old: approval1.9.0.11+
Details | Diff | Splinter Review
v1b (1.53 KB, patch)
2009-03-17 01:45 PDT, Igor Bukanov
igor: review+
Details | Diff | Splinter Review
js1_5/extensions/regress-369696-01.js (2.40 KB, text/plain)
2009-03-18 11:19 PDT, Bob Clary [:bc:]
no flags Details
js1_5/extensions/regress-369696-02.js (2.57 KB, text/plain)
2009-03-18 11:19 PDT, Bob Clary [:bc:]
no flags Details
js1_5/extensions/regress-369696-03.js (2.67 KB, text/plain)
2009-03-18 11:20 PDT, Bob Clary [:bc:]
no flags Details
1.8.0 patch (973 bytes, patch)
2009-05-13 03:03 PDT, Martin Stránský
igor: review+
dveditz: approval1.8.1.next+
Details | Diff | Splinter Review
fix bug number in regression tests (2.82 KB, patch)
2010-04-27 21:53 PDT, Gary Kwong [:gkw] [:nth10sd]
bob: review+
Details | Diff | Splinter Review

Description Jesse Ruderman 2007-02-07 23:09:25 PST
Pasting the following into the js shell causes an assertion failure.

q = [];
q.__defineGetter__("0", q.toString);
q[2] = q;
q.toSource();

In opt, I get "InternalError: too much recursion" instead.
Comment 1 Jesse Ruderman 2007-06-02 12:57:08 PDT
crowder, do you want to fix this bug?
Comment 2 Brian Crowder 2007-07-13 12:20:50 PDT
More investigation of this leads me to believe it is a pretty minor bug (or maybe not even a bug at all).  Brendan?
Comment 3 Brendan Eich [:brendan] 2007-07-13 15:46:32 PDT
If it's a bogus assertion, what's the correct condition to assert?

/be
Comment 4 Bob Clary [:bc:] 2007-11-24 18:43:03 PST
also,

native = encodeURIComponent;
n = native.prototype;
n.__defineGetter__("prototype", n.toSource);
p = n.__lookupGetter__("prototype");
n = p;
n["prototype"] = [n];
n = p;
p2 = n["prototype"];
n = p2; 
n.__defineGetter__("0", n.toString);
n = p; 
n();
Comment 5 Brian Crowder 2007-11-27 10:29:01 PST
Created attachment 290411 [details] [diff] [review]
map->depth++ consistency fix

I now believe that this is just a simple accounting bug, and that I was on crack before.
Comment 6 Brendan Eich [:brendan] 2007-11-27 10:30:50 PST
Comment on attachment 290411 [details] [diff] [review]
map->depth++ consistency fix

Redirecting to igor, I'm under deadlines and could use some help.

/be
Comment 7 Brian Crowder 2007-11-27 11:05:57 PST
Comment on attachment 290411 [details] [diff] [review]
map->depth++ consistency fix

Blah, this regresses bug 44009, back to the drawing-board.
Comment 8 Brian Crowder 2007-11-27 15:12:14 PST
Well.  Here's the problem as I understand it.  We increment map->depth conditionally upon the SHARP_BIT not being set in the sharpid, but -always- decrement it.  There are at least two instances of the SHARP_BIT being set during the run of the original testcase here.  (the new testcase is essentially the same thing as the original, as I understand it.
Comment 9 Gary Kwong [:gkw] [:nth10sd] 2009-03-08 21:53:27 PDT
(js assertions should be critical)

q = [];
q.__defineGetter__("0", q.toString);
q[2] = q;
q.toSource();

Assertion failure: map->depth > 0, at ../jsobj.cpp:562

asserts with TM tip, latest 1.9.0.x branch. I tried finding a regression window for this, besides discovering that this issue has existed since 01-01-2003 debug js shell, I couldn't compile a js shell for anything before that, so this is really ancient.

Brian, still working on this?
Comment 10 Gary Kwong [:gkw] [:nth10sd] 2009-03-08 21:54:17 PDT
Created attachment 366250 [details]
backtrace, normal and full

I'm not sure if this backtrace helps, nonetheless attaching...
Comment 11 Brian Crowder 2009-03-09 14:16:05 PDT
No, sorry I can't own this any longer.
Comment 12 Brendan Eich [:brendan] 2009-03-09 15:27:57 PDT
This code has seen action recently (Firefox 3.1 cycle).

/be
Comment 13 Brendan Eich [:brendan] 2009-03-09 15:28:41 PDT
My comment wasn't meant to suggest a regression, rather to call for volunteers.

/be
Comment 14 Jim Blandy :jimb 2009-03-10 10:07:03 PDT
I think the discussion in this bug covers the underlying problem here:
https://bugzilla.mozilla.org/show_bug.cgi?id=454704, around comment #13.

The object graph being printed is supposed to be traversed twice: the first pass, by MarkSharpObjects, produces a hash table noting multiply-referenced objects and cycles.  The second pass actually does the printing, consulting the hash table to decide where to print #N= labels and #N# references.

I'd guess what's happening here is that MarkSharpObject avoids invoking getters, but the printing traversal does invoke them.  When it does, it leaves the graph that MarkSharpObject scouted out for it, and wanders off into an infinite recursion.


The MarkSharpObjects traversal is supposed to visit all the objects the subsequent "really print this" traveral
Comment 15 Igor Bukanov 2009-03-13 05:10:37 PDT
Part of the troubles with the current implementation of toSource|toString comes from the fact that it stores sharpObjectMap in the JSContext. As such the map is shared between between unrelated invocations of toSource (like toSource invocation from a getter) resulting in violations of various assumptions in the toSource implementation. Another source of problems comes from getters and setters mutating the tree during the traversal (unrelated to this bug). 

I though that a quick way to solve this is to remove the map from JSContext. Then, when the current code call js_ValueToSource to invoke recursively the toSource implementation, the new version will check if the toSource|toString implementation comes from the original native methods. If so, it will call the methods directly passing the map to them.

But that is not so simple as using js_GetMethod for toSource|toString queries may invoke a getter for the method and mutate the object. So the implementation would need to take effectively a snapshot of the object to record all its properties before calling any js_GetMethod. This is doable, but is rather complex and is not for this bug where we need a simple safe fix that can be trivially backported to 1.9.0.
Comment 16 Igor Bukanov 2009-03-16 10:16:43 PDT
The exact reason for this bug is that js_LeaveSharpObject must only be called when js_EnterSharpObject returns non-sharp entry. Yet array_join_sub checks for sharp objects only when op == TO_SOURCE missing the fact that Array.prototype.toString can be called recursively from the toSource implementation. This can be used to make more calls to js_LeaveSharpObject than js_EnterSharpObject making JSContext.sharpObjectMap.depth negative.

I initially though that due to defensive programming this is not exploitable and at at worst can lead to leaks (not even segfaults due to null pointer derefs). But this is not the case as the GC marks objects in the sharpObjectMap only when map's depth is positive. So an evil script can make depth negative with JSContext.sharpObjectMap containing unreachable entries, trigger the GC leaving JSContext.sharpObjectMap with garabage, then it can create another custom toSource structure that would trigger another GC when JSContext.sharpObjectMap.depth is positive. This second GC will dereference the garbage.

Here is an example that demonstrates this with an optimized build of js shell:

@watson-32~/s> cat ~/s/x.js
var x = [[[ { toSource: function() { gc();  }}]]];

var a = [];
a[0] = a;
a.toSource = a.toString;
Array.prototype.toSource.call(a);

//cx->sharpObjectMap.depth == -2

(function() {
    var tmp = [];
    for (var i = 0; i != 30*1000; ++i) {
        var tmp2 = [];
        tmp.push(tmp2);
        tmp2.toSource();
    }
})();

// cx->sharpObjectMap.depth == -2 and table exists with many unreachable arrays

gc();
x.toSource();
@watson-32~/s> ~/build/js32.tm.opt/js ~/s/x.js
before 1290284, after 20480, break 08487000
Segmentation fault
Comment 17 Igor Bukanov 2009-03-16 10:19:05 PDT
Nominating as blockers as this is a heap corruption bug.
Comment 18 Gary Kwong [:gkw] [:nth10sd] 2009-03-16 10:28:49 PDT
(In reply to comment #17)
> Nominating as blockers as this is a heap corruption bug.

(removing wanted1.9.0.x? and adding blocking1.9.0.8? for parity)
Comment 19 Igor Bukanov 2009-03-16 10:37:49 PDT
Created attachment 367612 [details] [diff] [review]
v1

The fix makes sure that js_LeaveSharpObject is only called when the result of js_EnterSharpObject is not sharp. With the patch the result of toSource in the original example from the comment 0,

q = [];
q.__defineGetter__("0", q.toString);
q[2] = q;
print(q.toSource());

becomes:

#1=["#1#", , #1#]

Note that the first #1# is double-quoted. This is expected as the toString is called as a getter producing string result which is than double-quoted in js_ValueToSource. An alternative would be to return an empty string, but that would add more code for no apparent benefits.
Comment 20 Igor Bukanov 2009-03-16 10:52:13 PDT
This bug demonstrates one more time that an assert must not be declared as a harmless debug-only nuisance until there is clear understanding of what triggers it and what are the consequences.
Comment 21 Brendan Eich [:brendan] 2009-03-16 14:21:01 PDT
(In reply to comment #20)
> This bug demonstrates one more time that an assert must not be declared as a
> harmless debug-only nuisance until there is clear understanding of what
> triggers it and what are the consequences.

Absolutely.

http://weblogs.mozillazine.org/roadmap/archives/2005/01/assertions_shou.html

We're still struggling to get assertion/debug-build testerboxes up, IIUC. But it will happen.

/be
Comment 22 Brendan Eich [:brendan] 2009-03-16 14:44:27 PDT
Comment on attachment 367612 [details] [diff] [review]
v1

>+     * We must check for the sharp bit and skip js_LeaveSharpObject when it
>+     * set even when op is not TO_SOURCE. A script can overwrite the default

s/set/is set,/

r=me with that, thanks!

/be
Comment 23 Gary Kwong [:gkw] [:nth10sd] 2009-03-16 20:42:36 PDT
Created attachment 367714 [details] [diff] [review]
backported patch to 1.9.0.x

Here's the patch backport to the 1.9.0.x branch.

$ diff tm-patch.diff 190patch.diff 
1c1
< Index: tm/js/src/jsarray.cpp
---
> Index: js/src/jsarray.c
3,5c3,8
< --- tm.orig/js/src/jsarray.cpp        2009-03-16 15:17:58.000000000 +0100
< +++ tm/js/src/jsarray.cpp     2009-03-16 18:28:39.000000000 +0100
< @@ -1312,29 +1312,35 @@ array_join_sub(JSContext *cx, JSObject *
---
> RCS file: /cvsroot/mozilla/js/src/jsarray.c,v
> retrieving revision 3.180
> diff -u -8 -p -r3.180 jsarray.c
> --- js/src/jsarray.c  3 Feb 2009 23:21:10 -0000       3.180
> +++ js/src/jsarray.c  17 Mar 2009 03:37:19 -0000
> @@ -1217,29 +1217,35 @@ array_join_sub(JSContext *cx, JSObject *

With patch:

$ ./js
js> q = [];

js> q.__defineGetter__("0", q.toString);
js> q[2] = q;
,,
js> q.toSource();
#1=["#1#", , #1#]
js> 
js> 

Without patch:

$ ./js
js> q = [];

js> q.__defineGetter__("0", q.toString);
js> q[2] = q;
,,
js> q.toSource();
Assertion failure: map->depth > 0, at jsobj.c:555
Trace/BPT trap
Comment 24 Gary Kwong [:gkw] [:nth10sd] 2009-03-16 20:46:54 PDT
Created attachment 367715 [details] [diff] [review]
backported patch to 1.9.0.x, v2

Forgot the nit-fix.

$ diff tm-patch.diff 190patchv2.diff 
1c1
< Index: tm/js/src/jsarray.cpp
---
> Index: js/src/jsarray.c
3,5c3,8
< --- tm.orig/js/src/jsarray.cpp        2009-03-16 15:17:58.000000000 +0100
< +++ tm/js/src/jsarray.cpp     2009-03-16 18:28:39.000000000 +0100
< @@ -1312,29 +1312,35 @@ array_join_sub(JSContext *cx, JSObject *
---
> RCS file: /cvsroot/mozilla/js/src/jsarray.c,v
> retrieving revision 3.180
> diff -u -8 -p -r3.180 jsarray.c
> --- js/src/jsarray.c  3 Feb 2009 23:21:10 -0000       3.180
> +++ js/src/jsarray.c  17 Mar 2009 03:44:06 -0000
> @@ -1217,29 +1217,35 @@ array_join_sub(JSContext *cx, JSObject *
18c21
< +     * set even when op is not TO_SOURCE. A script can overwrite the default
---
> +     * is set, even when op is not TO_SOURCE. A script can overwrite the default

Interdiff:

$ diff 190patch 190patchv2.diff 
7c7
< +++ js/src/jsarray.c  17 Mar 2009 03:37:19 -0000
---
> +++ js/src/jsarray.c  17 Mar 2009 03:44:06 -0000
21c21
< +     * set even when op is not TO_SOURCE. A script can overwrite the default
---
> +     * is set, even when op is not TO_SOURCE. A script can overwrite the default
Comment 25 Igor Bukanov 2009-03-17 01:45:23 PDT
Created attachment 367739 [details] [diff] [review]
v1b

The new version of the patch addresses the comment nit.
Comment 26 Igor Bukanov 2009-03-17 01:53:56 PDT
landed to TM - http://hg.mozilla.org/tracemonkey/rev/f27eab818608
Comment 28 Bob Clary [:bc:] 2009-03-18 11:19:00 PDT
Created attachment 368059 [details]
js1_5/extensions/regress-369696-01.js
Comment 29 Bob Clary [:bc:] 2009-03-18 11:19:44 PDT
Created attachment 368060 [details]
js1_5/extensions/regress-369696-02.js
Comment 30 Bob Clary [:bc:] 2009-03-18 11:20:24 PDT
Created attachment 368061 [details]
js1_5/extensions/regress-369696-03.js
Comment 31 Samuel Sidler (old account; do not CC) 2009-04-10 15:28:43 PDT
Comment on attachment 367715 [details] [diff] [review]
backported patch to 1.9.0.x, v2

Approved for 1.9.0.10. a=ss
Comment 32 Igor Bukanov 2009-04-18 00:58:16 PDT
landed to 1.9.0:

Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.181; previous revision: 3.180
done
Comment 33 Al Billings [:abillings] 2009-05-11 15:10:52 PDT
Bob, I'm not seeing the assertions anymore with my debug 1.9.0.11 build but can you verify this? I wouldn't want to make a mistake with this for 1.9.0.
Comment 34 Bob Clary [:bc:] 2009-05-11 19:15:44 PDT
verified fixed 1.9.0, 1.9.1, 1.9.2

fixed in 1.9.1 by http://hg.mozilla.org/releases/mozilla-1.9.1/rev/9ab67913c351
Comment 35 Martin Stránský 2009-05-13 03:03:49 PDT
Created attachment 377123 [details] [diff] [review]
1.8.0 patch
Comment 36 Martin Stránský 2009-05-13 03:05:30 PDT
Comment on attachment 377123 [details] [diff] [review]
1.8.0 patch

Can you please check this one?
Comment 37 Daniel Veditz [:dveditz] 2009-05-29 10:59:53 PDT
Comment on attachment 377123 [details] [diff] [review]
1.8.0 patch

Approved for 1.8.1.22, a=dveditz for release-drivers
Comment 38 Daniel Veditz [:dveditz] 2009-05-31 13:52:57 PDT
Checked into the 1.8(.1) branch

Checking in jsarray.c;
/cvsroot/mozilla/js/src/jsarray.c,v  <--  jsarray.c
new revision: 3.58.2.27; previous revision: 3.58.2.26
done
Comment 39 Bob Clary [:bc:] 2009-06-07 21:35:21 PDT
v 1.8.1
Comment 40 Bob Clary [:bc:] 2009-08-18 01:35:07 PDT
http://hg.mozilla.org/tracemonkey/rev/304c738d2622

/cvsroot/mozilla/js/tests/js1_5/extensions/regress-369696-01.js,v  <--  regress-369696-01.js
initial revision: 1.1

/cvsroot/mozilla/js/tests/js1_5/extensions/regress-369696-02.js,v  <--  regress-369696-02.js
initial revision: 1.1

/cvsroot/mozilla/js/tests/js1_5/extensions/regress-369696-03.js,v  <--  regress-369696-03.js
initial revision: 1.1
Comment 41 Gary Kwong [:gkw] [:nth10sd] 2010-04-27 21:53:55 PDT
Created attachment 442021 [details] [diff] [review]
fix bug number in regression tests

The bug number is wrong - should be 369696, not 396696.
Comment 42 Bob Clary [:bc:] 2010-04-27 21:59:10 PDT
Comment on attachment 442021 [details] [diff] [review]
fix bug number in regression tests

thanks!
Comment 43 Bob Clary [:bc:] 2010-04-28 00:04:02 PDT
http://hg.mozilla.org/tracemonkey/rev/d8423a37c0ad

I messed up the user in the commit. It just listed "Gary". Sorry, I'll do better next time. Thanks again. 

I did hg qnew -u "Gary Kwong" bug-369696.patch and it seemed right in the patch. Then hg qfinish and hg push. Anyone know what I did wrong?
Comment 44 Bob Clary [:bc:] 2010-04-28 00:05:10 PDT
nm. the actual revision has the proper author. the pushlog is just being innane.

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