369696 - "Assertion failure: map->depth > 0" in js_LeaveSharpObject

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jesse Ruderman]

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]

crowder, do you want to fix this bug?

Comment 2

[Brian Crowder]

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]]

If it's a bogus assertion, what's the correct condition to assert?

/be

Comment 4

[Bob Clary [:bc] (inactive)]

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]

Attachment: 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]]

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]

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]

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] (NOT official MoCo now)]

(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] (NOT official MoCo now)]

Attachment: backtrace, normal and full

I'm not sure if this backtrace helps, nonetheless attaching...

Comment 11

[Brian Crowder]

No, sorry I can't own this any longer.

Comment 12

[Brendan Eich [:brendan]]

This code has seen action recently (Firefox 3.1 cycle).

/be

Comment 13

[Brendan Eich [:brendan]]

My comment wasn't meant to suggest a regression, rather to call for volunteers.

/be

Comment 14

[Jim Blandy :jimb]

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]

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]

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]

Nominating as blockers as this is a heap corruption bug.

Comment 18

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

(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]

Attachment: 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]

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]]

(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]]

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] (NOT official MoCo now)]

Attachment: 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] (NOT official MoCo now)]

Attachment: 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]

Attachment: v1b

The new version of the patch addresses the comment nit.

Comment 26

[Igor Bukanov]

landed to TM - http://hg.mozilla.org/tracemonkey/rev/f27eab818608

Comment 27

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/f27eab818608

Comment 28

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/extensions/regress-369696-01.js

Comment 29

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/extensions/regress-369696-02.js

Comment 30

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/extensions/regress-369696-03.js

Comment 31

[Samuel Sidler (old account; do not CC)]

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]

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 - ex-MoCo]]

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] (inactive)]

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ý [:stransky] (ni? me)]

Attachment: 1.8.0 patch

Comment 36

[Martin Stránský [:stransky] (ni? me)]

Comment on attachment 377123 [details] [diff] [review]
1.8.0 patch

Can you please check this one?

Comment 37

[Daniel Veditz [:dveditz]]

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]]

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] (inactive)]

v 1.8.1

Comment 40

[Bob Clary [:bc] (inactive)]

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] (NOT official MoCo now)]

Attachment: fix bug number in regression tests

The bug number is wrong - should be 369696, not 396696.

Comment 42

[Bob Clary [:bc] (inactive)]

Comment on attachment 442021 [details] [diff] [review]
fix bug number in regression tests

thanks!

Comment 43

[Bob Clary [:bc] (inactive)]

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] (inactive)]

nm. the actual revision has the proper author. the pushlog is just being innane.