I've looked over some cycle collector dumps (after the patch in Bug 709160 is applied) and it seems like JS_TraceChildren isn't handling the parent field correctly. It looks like it is being visited repeatedly. I saw one instance that had the same parent edge 65 times. This is pretty common, but doesn't seem to happen 100% of the time. I'm not sure if this is a problem with JS_TraceChildren, a general problem with the marking code, some weird interaction of ObjShrink with the cycle collector, or something else. I'll try hooking up the GC heap dumper today or tomorrow to at least rule out the third possibility. Here's a smaller example of an object and its children: 0x118366140 [gc.marked] JS Function Array > 0x12b652cc0 type_proto > 0x118366140 type_singleton > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b651100 prototype > 0x126c14ca0 join > 0x126c14d00 reverse > 0x126c14d60 sort > 0x126c14dc0 push > 0x126c14e20 pop > 0x126c14e80 shift > 0x126c14ee0 unshift > 0x126c14f40 splice > 0x126c14fa0 concat > 0x11832a040 slice > 0x11832a0a0 indexOf > 0x11832a100 lastIndexOf > 0x11832a160 forEach > 0x11832a1c0 map > 0x11832a220 reduce > 0x11832a280 reduceRight > 0x11832a2e0 filter > 0x11832a340 some > 0x11832a3a0 every > 0x118366700 isArray > 0x12b6988c0 from

I think this is a problem specific to the cycle collector. Reading bug 638316 comment 21 I'm guessing what is happening here is that an object has a pointer to its shape, so when we JS_TraceChildren in the CC, it returns the shape. However, because we don't represent shapes in the CC graph, we have to trace through the entire shape structure to find all non-shapes that it contains, and all of these children are attributed to the object. So I guess there are a bunch of chained shapes, and they all point to the same parent, so they are all added. It seems like ObjShrink has moved a number of things onto shapes, so maybe they should be represented explicitly in the CC graph to prevent this. Either that or we could come up with some kind of hack to not add all of these identical children...

> So I guess there are a bunch of chained shapes One per property that exists on the object.

Ah, right, that makes sense. So we're more or less doubling the number of children of JS objects. Is the parent not always identical for all shapes in the chain? It seems to be the case in the objects I've looked at, but I could believe thanks to the magic of JS that sometimes it isn't true. Side note: as you'd expect, there are other things duplicated on the shape chain besides the parent. 0x12b650190 [gc.marked] JS object (XPC_WN_ModsAllowed_NoCall_Proto_JSClass - Window) > 0x12b650220 type_proto > 0x12b650190 type_singleton > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent > 0x1367854c0 getter > 0x1367854c0 setter > 0x1367854c0 getter > 0x1367854c0 setter > 0x12b655060 parent > 0x12b655060 parent > 0x13677cd60 getter > 0x13677cd60 setter > 0x13677cd60 getter > 0x13677cd60 setter > 0x12b655060 parent > 0x12b655060 parent > 0x12b655060 parent [then many more parents]

The getters and setters are part of the shape itself, so before objshrink you should have been seeing these. I don't think the CC graph should need to keep track of shapes or base shapes. It seems like it would be faster (on an important path!) and still reasonably clean to have a JS_TraceCycleCollectorChildren or something, that is passed a GC thing which the CC cares about and only returns children which the CC cares about. Only one child for the parent would be returned. A shape traversal would still be necessary to find scripted getters/setters on the object, but the callback overhead would be avoided for going from the object through the shape, base shape, and type object (for obj->proto).

(In reply to Andrew McCreight [:mccr8] from comment #3) > Is the parent not always identical for all shapes in the chain? It seems to > be the case in the objects I've looked at, but I could believe thanks to the > magic of JS that sometimes it isn't true. There are some situations where this is possible, but it should be safe for the CC to ignore this possibility. Technical details: Each shape has an associated object parent (stored in its BaseShape), but for a given JSObject the only shape where that parent is actually relevant is the last property. If an object O initially has parent P1 and has shapes S1 and S2 added to it (in that order), both shapes will have object parent P1. If the object has its parent changed to P2, then its last property S2 is replaced with a different one S3 which is identical to S2 except for having a different parent P2. S3->previous() will still point to S1 though, which still has the stale parent; S1 still describes some property which O has, but its information about the object itself will never again be used. From the cycle collector's perspective, the parent stored in S1 is a dead link *unless* there is a second object O2 whose shape is S1 (shapes being shared and immutable, not withstanding dictionary shapes). If there is such an O2, then when doing JS_TraceCycleCollectorChildren (or whatever) the parent P1 will be traced through.

Thanks for the detailed explanation! It sounds like your suggestion will fit in fairly well with the existing code.

One concern I have with your approach is that if A has a shape S1 with parent P1, then adds another shape S2, then switches its parent to P2, A will retain a path from A to P1. If we then create a path from P1 through DOM back to A, we'll leak A (and everything it holds on to), because we haven't told the CC about the path from A to P1. Maybe the more hacky approach of remembering the last parent we reported, and not reporting a new one if it is the same, is needed. If there was some mechanism for obliterating unused parents that could be avoided, but that's probably more complex.

There will be a path from A to P1 through the heap, yeah (and the regular GC needs to account for this, when scanning S1), but that path will never actually be accessed anytime later on in the life of A. Only the last property of A is used to access its parent, and S1 will never again be the last property of A (there is a way to rewind the last property of an object, but when doing so we watch for changes to the parent / other object attributes and convert to dictionary instead in such cases, which will not reuse S1). It is, of course, safe to mark such old parents anyways, and wouldn't hurt things so much seeing as the shapes already need to be scanned for scripted getters/setters.

I understand that, but unfortunately if that path is enough for the GC to keep P1 alive (and looking over the marking code I don't see any special case for unreachable parents), then the CC needs to know about it or the CC will keep things alive that are dead in bizarre circumstances. The GC could probably be made to not mark those unreachable parents, but that would leave around dangling pointers which seems a little dangerous given how little it probably would buy you in practice.

I wrote a simple script to calculate the number of edges called 'parent' beyond 1. This is a pretty crude measure, as there are probably some false positives. The number on the left of the : is the number of extra parents, and the number on the right is the number of objects with that many dups. This is before my patch. As you can see, there are a lot of dups. (The ones with 0 parents are probably not JS.) {0: 48111, 1: 1554, 2: 542, 3: 461, 4: 229, 5: 129, 6: 684, 7: 47, 8: 274, 9: 152, 10: 40, 11: 20, 12: 21, 13: 28, 14: 64, 15: 12, 16: 56, 17: 12, 18: 10, 19: 12, 20: 7, 21: 20, 22: 12, 23: 12, 24: 9, 25: 30, 26: 2, 27: 4, 28: 8, 29: 2, 30: 3, 31: 5, 32: 5, 33: 4, 34: 2, 35: 4, 36: 5, 37: 2, 38: 3, 39: 4, 40: 7, 41: 1, 43: 1, 44: 1, 45: 2, 47: 1, 49: 2, 50: 2, 51: 1, 53: 1, 58: 1, 66: 1, 69: 1, 73: 1, 74: 2, 76: 1, 77: 1, 78: 10, 80: 1, 82: 2, 84: 1, 85: 3, 86: 7, 87: 1, 88: 4, 89: 1, 91: 1, 104: 1, 107: 15, 108: 1, 110: 2, 111: 1, 113: 1, 114: 3, 115: 1, 116: 2, 118: 1, 119: 2, 121: 3, 122: 1, 127: 1, 130: 2, 131: 1, 134: 1, 136: 2, 137: 4, 143: 1, 146: 1, 160: 1, 178: 1, 193: 1, 206: 14, 208: 5, 214: 1, 219: 1, 250: 1} After a simple patch that just caches the parent of an object and doesn't revisit it under any circumstances the duplicates look like this: {0: 62237, 1: 542, 20: 1, 5: 2} There are a handful of duplicates, probably resulting from nodes where the parent changed, but not really enough to worry about. The two objects with 5 duplicate parents look like this: 0x11a18fee0 [gc] JS Object (RegExp) > 0x11a202060 parent > 0x11a202060 parent > 0x11a202060 parent > 0x11a202060 parent > 0x11a202060 parent > 0x11a202060 parent I'm not sure why the dup elimination isn't catching this. Could those possibly be a different kind of parent? There are many RegExps without duplicated parents like that. For the ones with 20 duplicate parents (and I see 1 to 4 in each CC), they are all JS Object (XPC_WN_ModsAllowed_NoCall_Proto_JSClass - Window), and it looks like the parent just changed. The duplicate fields are all identical.

I'm still not a huge fan of this because it requires an additional equality check for every child of a JS Object, but I think we have to do a bunch of indirect calls anyways, so it probably gets lost in the noise. A nicer solution, in some sense, would be to write a custom shape marker for the cycle collector, but that would probably require duplicating a lot of code so I'm not sure how great it would be. But then we could only do the equality checks for parent pointers. Just for funsies I looked at what happens if we make everything but strings into CC things. In one graph I looked at, there were 15.4k objects, 23.3k shapes, 6.8k base shapes and 985 type objects. The shapes, base shapes and type objects didn't have many fields, so representing them directly on the object seems sensible.

(In reply to Andrew McCreight [:mccr8] from comment #13) > I'm still not a huge fan of this because it requires an additional equality > check for every child of a JS Object, but I think we have to do a bunch of > indirect calls anyways, so it probably gets lost in the noise. The JS_TraceCycleCollectorChildren approach would not make the indirect calls at all for the shapes or other CC-irrelevant children of the object, and should be a good deal faster and cleaner. I can put together a patch for that, unless you want to look into it.

Were you thinking of something along these lines, Brian? I guess this could even be pushed to a higher level and run on objects.

Cleaned up the previous version a little bit. Try run looks fine, except M1 is a little crashy on Linux debug.

Comment on attachment 582637 [details] [diff] [review] special shape marker for the cycle collector In the end, I think I just got unlucky with some known M1 crashes. I ran it 5 more times without any orange. https://tbpl.mozilla.org/?tree=Try&rev=616c0a848196 This patch removes MarkShapeChildrenAcyclic and replaces it with a special shape marker for the cycle collector that traces through shapes and base shapes without marking them, and without bouncing back to XPConnect. Other non-CCkind things will still bounce back, but avoiding that would require creating some kind of JSID marking variant that doesn't mark strings, which seems like overkill for the moment. It uses bounded stack space, and caches the value of the last parent field encountered during the traversal, in order to skip duplicate parents.

Comment on attachment 582637 [details] [diff] [review] special shape marker for the cycle collector Review of attachment 582637 [details] [diff] [review]: ----------------------------------------------------------------- Looks good. It would be possible to optimize this even more if JS_TraceCycleCollectorChildren took a JSObject instead and NoteJSChild only ever saw JSTRACE_SHAPE for shapes rooted on the stack, but fixing this would duplicate a fair bit of code and should wait for bug 712022 I think. ::: js/src/jsgcmark.cpp @@ +984,5 @@ > + * marked only if it isn't the same as prevParent, which will be > + * updated to the current shape's parent. > + */ > +void > +MarkCycleCollectorChildren(JSTracer *trc, BaseShape *base, JSObject **prevParent) This function should be inline. @@ +999,5 @@ > + if (!base->isOwned()) > + return; > + > + base = base->baseUnowned(); > + } The loop here is not needed, as an owned base shape has the same parent, getter and setter as its baseUnowned(). @@ +1015,5 @@ > +MarkCycleCollectorChildren(JSTracer *trc, const Shape *shape) > +{ > + JSObject *prevParent = NULL; > + do { > + if (BaseShape *base = shape->base()) shape->base() will always be non-NULL, no NULL check needed here.

Thanks. Addressed review comments, added some assertions to verify that a base shape matches its unowned base shape. Carrying forward bhackett's review. I'm going to let this bake a little bit on try before I upload it. Assertions were okay when I browsed with it for a few minutes.

> The loop here is not needed, as an owned base shape has the same parent, getter and setter as its baseUnowned(). This would imply to me that the loop can also be removed from ScanBaseShape. Although with a moving collector we'd still need to visit the baseUnowned() to update pointers, so maybe it is better to just leave it alone.

I accidentally uploaded an empty patch.