Closed Bug 672736 (findReferences) Opened 8 years ago Closed 8 years ago

JavaScript tests should be able to directly check GC edges

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla8

People

(Reporter: jimb, Assigned: jimb)

References

Details

Attachments

(1 file, 3 obsolete files)

No description provided.
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.
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.
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)
Depends on: 672728
Alias: findReferences
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>
Attachment #547001 - Attachment is obsolete: true
Attachment #549202 - Flags: review?(jorendorff)
Added some more tests.
Attachment #549202 - Attachment is obsolete: true
Attachment #549282 - Flags: review?(jorendorff)
Attachment #549202 - Flags: review?(jorendorff)
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);
Added test for cross-compartment references; add 'wrap' call to code.
Assignee: general → jimb
Attachment #549282 - Attachment is obsolete: true
Status: NEW → ASSIGNED
Attachment #549305 - Flags: review?(jorendorff)
Attachment #549282 - Flags: review?(jorendorff)
Unfortunately, JS_TraceRuntime doesn't run the iterative marking loop, so findReferences doesn't work on weak maps or Debugger objects.
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 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.
Attachment #549305 - Flags: review?(jorendorff) → review+
(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.
http://hg.mozilla.org/mozilla-central/rev/65617cb216fa
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla8
(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!
Status: RESOLVED → UNCONFIRMED
Ever confirmed: false
Resolution: FIXED → ---
Target Milestone: mozilla8 → ---
I'm assuming you didn't mean to change it from RESOLVED-FIXED, so I'm flipping it back.
Status: UNCONFIRMED → RESOLVED
Closed: 8 years ago8 years ago
OS: Linux → All
Hardware: x86_64 → All
Resolution: --- → FIXED
Whiteboard: [inbound]
Target Milestone: --- → mozilla8
Version: unspecified → Trunk
(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.
(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! :(
(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.
Depends on: 677796
Depends on: 1071001
You need to log in before you can comment on or make changes to this bug.