672736 - (findReferences) JavaScript tests should be able to directly check GC edges

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Comment 1

[Jim Blandy :jimb]

There should be a way for JavaScript shell tests to find all the GC graph edges referring to a given object, labelled according to the names provided by the tracing code. This would let tests directly exercise custom tracers, at least when SpiderMonkey is built with debugging enabled.

Comment 2

[Jim Blandy :jimb]

Attachment: Implement the 'findReferences' shell function.

findReferences(thing)

  Walk the entire heap, looking for references to |thing|, and return a
  "references object" describing what we found.

  Each property of the references object describes one kind of reference. The
  property's name is the label supplied to MarkObject, JS_CALL_TRACER, or what
  have you. The property's value is an array of things that refer to |thing|
  via that kind of reference. References from one object to another are named
  after the property name.

  Note that the references object does record references from objects that are
  only reachable via |thing| itself, not just the references reachable
  themselves from roots that keep |thing| from being collected. (We could make
  this distinction if it is useful.)

  If any references are found by the conservative scanner, the references
  object will have a property named "machine stack"; its value is the empty
  array.

js> var o = { x: { y: { z: {} } }}
js> findReferences(o)
({'machine stack':[], o:[{o:{x:{y:{z:{}}}}}], 'ReferenceFinder::target':[]})
js> o = { get x() { return 42 } }
({get x () {return 42;}})
js> findReferences(Object.getOwnPropertyDescriptor(o, 'x').get)
({'machine stack':[], 'shape; x getter':[{get x () {return 42;}}], get:[{configurable:true, enumerable:true, get:#1=(function () {return 42;}), set:(void 0)}], constructor:[{}], 'ReferenceFinder::target':[]})
js> findReferences(Math.atan2)
({'machine stack':[], atan2:[Math], 'ReferenceFinder::target':[]})
js> findReferences(o)
({'machine stack':[], o:[{o:{get x () {return 42;}}}], 'ReferenceFinder::target':[]})
js> 

TODO: consider using TempAllocPolicy and just checking for a pending execption.

Comment 3

[Jim Blandy :jimb]

That first example was supposed to be:

js> var o = { x: { y: { z: {} } }}
js> findReferences(o.x.y.z)
findReferences(o.x.y.z)
({z:[{z:{}}], 'machine stack':[], 'ReferenceFinder::target':[]})

(time to go to sleep)

Comment 4

[Jim Blandy :jimb]

Attachment: Implement the 'findReferences' shell function.

Here's an implementation that actually works. I think I know a more beautiful (and less memory-hungry) algorithm, but I've been wrong about that twice before, so here's the brute-force approach.

findReferences(thing)

  Walk the entire heap, looking for references to |thing|, and return a
  "references object" describing what we found.

  Each property of the references object describes one kind of reference. The
  property's name is the label supplied to MarkObject, JS_CALL_TRACER, or what
  have you. The property's value is an array of things that refer to |thing|
  via that kind of reference. References from one object to another are named
  after the property name.

  Note that the references object does record references from objects that are
  only reachable via |thing| itself, not just the references reachable
  themselves from roots that keep |thing| from being collected. (We could make
  this distinction if it is useful.)

  If any references are found by the conservative scanner, the references
  object will have a property named "machine stack"; its value is the empty
  array.

js> var o = { x: { y: { z: {} } }}
js> findReferences(o.x.y.z)
({'edge: z':[{z:{}}], 'edge: machine stack':[null, null, null, null, null]})
js> o = { get x() { return 42 } }
({get x () {return 42;}})
js> findReferences(Object.getOwnPropertyDescriptor(o, 'x').get)
({'edge: shape; x getter':[{get x () {return 42;}}],
  'edge: constructor':[{}],
  'edge: machine stack':[null, null, null, null, null],
  'edge: get':[{configurable:true,
                enumerable:true,
                get:#1=(function () {return 42;}),
                set:(void 0)}]})
js> findReferences(Math.atan2)
({'edge: atan2':[Math], 'edge: machine stack':[null, null, null, null, null]})
js> findReferences(o)
({'edge: o':[{o:{get x () {return 42;}}}], 'edge: machine stack':[null, null, null, null, null]})
js>

Comment 5

[Jim Blandy :jimb]

Attachment: Implement the 'findReferences' shell function.

Added some more tests.

Comment 6

[Jim Blandy :jimb]

findReferences as written isn't very happy with cross-compartment references. The following causes an assertion:

var global = newGlobal('new-compartment');
var o = ({});
global.o = o;

// Don't trip a cross-compartment reference assertion.
findReferences(o);

Comment 7

[Jim Blandy :jimb]

Attachment: Implement the 'findReferences' shell function.

Added test for cross-compartment references; add 'wrap' call to code.

Comment 8

[Jim Blandy :jimb]

Unfortunately, JS_TraceRuntime doesn't run the iterative marking loop, so findReferences doesn't work on weak maps or Debugger objects.

Comment 9

[Jason Orendorff [:jorendorff]]

js> m = []; for (var i = 0; i < 100000; i++) m = [m]; findReferences(m); 0;
Segmentation fault

Stack overflow in HeapReverser, I presume. This would be a pain to fix;
you need an explicit stack or queue. I guess just paper over it with
JS_CHECK_RECURSION.

I think ReferenceFinder::visit wants JS_CHECK_RECURSION too, even though
it seems very unlikely that that recursion would go this deep.

It would be nice to put this stuff in its own .cpp file under
js/shell. Some of the other heap inspection functions could go in there
too, perhaps.

In tests/js1_8_5/extensions/findReferences-03.js:
>+function makeGenerator(c) { eval(c); yield function generatorClosure() { return x; }; }
>+var generator = makeGenerator('var x = 42');
>+var closure = generator.next();
>+referencesVia(closure, 'parent; generator object', generator);

What aspect of findReferences is this testing?

In tests/js1_8_5/extensions/shell.js:
>+function SkipTestIfFunctionAbsent(name) {
>+    if (typeof this[name] != "function") {
>+        reportCompare(true, true, "Skipping test; function '" + name + "' not present");
>+        quit();
>+    }
>+}

quit() seems to be defined as a no-op in js/src/tests/browser.js.

>+    // Be nice: make it easy to fix if the edge name has just changed.

You are so nice!

In js.cpp, HeapReverser::traverseEdge:
>+    /*
>+     * Since we have no way to return a 'stop traversal' status, the best we
>+     * can do is just refuse to traverse any deeper once an error has
>+     * occurred.
>+     */
>+    if (JS_IsExceptionPending(context))
>+        return;

Out of memory isn't treated as an exception, though. It's an uncatchable
error; it leaves no state in the context. You'll have to keep an error flag
or something.

>+            JSClass *clasp = JS_GetClass(context, object);

JS_GET_CLASS.

In ReferenceFinder::visit:
>+        char *name = path->computeName(context);
>+        if (!name)
>+            return false;
>+        bool ok = addReferrer(JSVAL_NULL, name);
>+        free(name);
>+        /* No need to traverse further. */
>+        return ok;
>[...]
>+            char *name = path->computeName(context);
>+            if (!name)
>+                return false;
>+            bool ok = addReferrer(representation, name);
>+            free(name);
>+            /* No need to traverse further. */
>+            return ok;

Common these up; and put a blank line before a comment (unless it's on
the first line within a block).

In ReferenceFinder::Path::computeName:
>+    strcpy(path, "edge: ");
>+    char *next = path + 6;
>+    for (Path *l = this; l; l = l->next) {
>+        strcpy(next, l->edge.name);
>+        next += strlen(next);
>+        if (l->next) {
>+            strcpy(next, "; ");
>+            next += 2;

Seems like we could be using JS_ConcatStrings (and then JS_DefinePropertyById) but I'm not picky.

In ReferenceFinder::addReferrer:
>+        if (!JS_SetProperty(context, result, path, &v))
>+            return false;
>+        return true;

Suggestion: could just return JS_SetProperty(...) here.

Or I guess !!JS_SetProperty(...) to avoid the MSVC warning about int values being implicitly converted to bool.

>+    if (!JS_GetArrayLength(context, array, &length) ||
>+        !JS_SetElement(context, array, length, &referrer))
>+        return false;
>+
>+    return true;

Same here (switching the || to &&, not that I have to remind you!) But if not, you're supposed to put {} around the "return false;" since the if-head is multi-line.

In js/src/shell/js.cpp, comment on FindReferences:
>+ * Each property of the references object describes one kind of reference. The
>+ * property's name is the label supplied to MarkObject, JS_CALL_TRACER, or what
>+ * have you. [...]

Not anymore: now it starts with "edge:". (Also in the commit message.)

Comment 10

[Jason Orendorff [:jorendorff]]

Comment on attachment 549305 [details] [diff] [review]
Implement the 'findReferences' shell function.

r=me with the comments addressed; JS_CHECK_RECURSION is the most important thing.

Comment 11

[Jim Blandy :jimb]

(In reply to comment #9)
> js> m = []; for (var i = 0; i < 100000; i++) m = [m]; findReferences(m); 0;
> Segmentation fault
> 
> Stack overflow in HeapReverser, I presume. This would be a pain to fix;
> you need an explicit stack or queue. I guess just paper over it with
> JS_CHECK_RECURSION.
> 
> I think ReferenceFinder::visit wants JS_CHECK_RECURSION too, even though
> it seems very unlikely that that recursion would go this deep.

Okay. I'll address these.

> It would be nice to put this stuff in its own .cpp file under
> js/shell. Some of the other heap inspection functions could go in there
> too, perhaps.

Okay.

> In tests/js1_8_5/extensions/findReferences-03.js:
> >+function makeGenerator(c) { eval(c); yield function generatorClosure() { return x; }; }
> >+var generator = makeGenerator('var x = 42');
> >+var closure = generator.next();
> >+referencesVia(closure, 'parent; generator object', generator);
> 
> What aspect of findReferences is this testing?

Well, none, really. I just wanted to exercise every kind of edge I could find. Those are more like tests for scope chain references than tests for findReferences. Should I skip them?

> In tests/js1_8_5/extensions/shell.js:
> >+function SkipTestIfFunctionAbsent(name) {
> >+    if (typeof this[name] != "function") {
> >+        reportCompare(true, true, "Skipping test; function '" + name + "' not present");
> >+        quit();
> >+    }
> >+}
> 
> quit() seems to be defined as a no-op in js/src/tests/browser.js.

Oh dear. What is the best way to skip the test in this case?

> >+    // Be nice: make it easy to fix if the edge name has just changed.
> 
> You are so nice!

The data is right there, so... :)

> In js.cpp, HeapReverser::traverseEdge:
> >+    /*
> >+     * Since we have no way to return a 'stop traversal' status, the best we
> >+     * can do is just refuse to traverse any deeper once an error has
> >+     * occurred.
> >+     */
> >+    if (JS_IsExceptionPending(context))
> >+        return;
> 
> Out of memory isn't treated as an exception, though. It's an uncatchable
> error; it leaves no state in the context. You'll have to keep an error flag
> or something.

Uh oh.

> >+            JSClass *clasp = JS_GetClass(context, object);
> 
> JS_GET_CLASS.

Okay.

> Common these up; and put a blank line before a comment (unless it's on
> the first line within a block).

Okay.

> In ReferenceFinder::Path::computeName:
> >+    strcpy(path, "edge: ");
> >+    char *next = path + 6;
> >+    for (Path *l = this; l; l = l->next) {
> >+        strcpy(next, l->edge.name);
> >+        next += strlen(next);
> >+        if (l->next) {
> >+            strcpy(next, "; ");
> >+            next += 2;
> 
> Seems like we could be using JS_ConcatStrings (and then
> JS_DefinePropertyById) but I'm not picky.

If you think it would be significantly easier to take care of, I'll do this. I like slinging bytes, but I shouldn't inflict that on others.

> In ReferenceFinder::addReferrer:
> >+        if (!JS_SetProperty(context, result, path, &v))
> >+            return false;
> >+        return true;
> 
> Suggestion: could just return JS_SetProperty(...) here.
> 
> Or I guess !!JS_SetProperty(...) to avoid the MSVC warning about int values
> being implicitly converted to bool.

Okay.

> >+    if (!JS_GetArrayLength(context, array, &length) ||
> >+        !JS_SetElement(context, array, length, &referrer))
> >+        return false;
> >+
> >+    return true;
> 
> Same here (switching the || to &&, not that I have to remind you!) But if
> not, you're supposed to put {} around the "return false;" since the if-head
> is multi-line.

Sure.

> In js/src/shell/js.cpp, comment on FindReferences:
> >+ * Each property of the references object describes one kind of reference. The
> >+ * property's name is the label supplied to MarkObject, JS_CALL_TRACER, or what
> >+ * have you. [...]
> 
> Not anymore: now it starts with "edge:". (Also in the commit message.)

Fixed.

Comment 12

[Jim Blandy :jimb]

http://hg.mozilla.org/integration/mozilla-inbound/rev/65617cb216fa

Comment 13

[Marco Bonardo [:mak]]

http://hg.mozilla.org/mozilla-central/rev/65617cb216fa

Comment 14

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

FYI: http://weblogs.mozillazine.org/gerv/archives/2010/02/mpl_initial_developer_for_mozilla_employ.html

Comment 15

[Jim Blandy :jimb]

(In reply to comment #14)
> FYI:
> http://weblogs.mozillazine.org/gerv/archives/2010/02/
> mpl_initial_developer_for_mozilla_employ.html

Oh, thanks for pointing that out!

Comment 16

[Andrew McCreight [:mccr8]]

I'm assuming you didn't mean to change it from RESOLVED-FIXED, so I'm flipping it back.

Comment 17

[Jim Blandy :jimb]

(In reply to comment #15)
> (In reply to comment #14)
> > FYI:
> > http://weblogs.mozillazine.org/gerv/archives/2010/02/
> > mpl_initial_developer_for_mozilla_employ.html
> 
> Oh, thanks for pointing that out!

Actually, I'm not sure this is correct. The test files are in the public domain, not under the MPL. This was worked out with Mitchell a few years ago.

Comment 18

[Jim Blandy :jimb]

(In reply to comment #16)
> I'm assuming you didn't mean to change it from RESOLVED-FIXED, so I'm
> flipping it back.

No, I didn't mean to at all! :(

Comment 19

[:Gavin Sharp [email: [e-mail]]]

(In reply to comment #17)
> Actually, I'm not sure this is correct. The test files are in the public
> domain, not under the MPL. This was worked out with Mitchell a few years ago.

Ms2ger was referring to the MPL-licensed CPP files in that changeset, presumably - they list "Mozilla Corporation" in the header where they should list "the Mozilla Foundation". I'm not sure that this distinction actually really matters in practice.