Last Comment Bug 668855 - add WeakMap support to the cycle collector
: add WeakMap support to the cycle collector
Status: RESOLVED FIXED
[MemShrink:P2]
: mlk
Product: Core
Classification: Components
Component: XPCOM (show other bugs)
: Trunk
: All All
: -- normal (vote)
: mozilla11
Assigned To: Andrew McCreight [:mccr8]
:
Mentors:
Depends on: 681104 686114 688277 698151 704207 707345
Blocks: WeakMap 653248 669240 680937 690970 692226 693527
  Show dependency treegraph
 
Reported: 2011-07-01 11:15 PDT by Andrew McCreight [:mccr8]
Modified: 2012-07-20 14:35 PDT (History)
15 users (show)
continuation: in‑testsuite+
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
part 1: add JS interface for tracing weak maps (7.53 KB, patch)
2011-08-21 11:16 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 1: add JS interface for tracing weak maps (14.54 KB, patch)
2011-08-22 14:00 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 2: add XPConnect to CC WeakMap interface, doesn't do anything (4.18 KB, patch)
2011-08-31 17:22 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 3: hook up CC WeakMap callbacks to JS via XPConnect (3.48 KB, patch)
2011-08-31 17:32 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 4: add weak map nodes to the graph, store the bindings (4.07 KB, patch)
2011-09-02 17:32 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 1: add JS interface for tracing weak maps (14.28 KB, patch)
2011-09-03 12:07 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 3: hook up CC WeakMap callbacks to JS via XPConnect (3.49 KB, patch)
2011-09-03 12:10 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 5: scan WeakMaps (4.31 KB, patch)
2011-09-03 12:27 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 1: add JS friend interface for tracing weak maps (11.24 KB, patch)
2011-10-03 14:21 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 2: add nsCycleCollectionTraversalCallback hook for weak mappings (4.12 KB, patch)
2011-10-03 14:39 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 3: hook up CC WeakMap callbacks to JS via XPConnect (4.32 KB, patch)
2011-10-03 15:20 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 4: store weak mappings in the CC graph (4.26 KB, patch)
2011-10-04 09:09 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 5: scan WeakMaps (3.25 KB, patch)
2011-10-04 12:49 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
A variety of tests of weak map cycle collector interaction (8.62 KB, patch)
2011-10-06 17:51 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 1: add JS friend interface for tracing weak maps (15.06 KB, patch)
2011-10-10 12:59 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 1: add JS friend interface for tracing weak maps (12.88 KB, patch)
2011-10-10 13:00 PDT, Andrew McCreight [:mccr8]
wmccloskey: review+
Details | Diff | Splinter Review
part 2: add nsCycleCollectionTraversalCallback hook for weak mappings (4.11 KB, patch)
2011-10-10 13:02 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 3: hook up CC WeakMap callbacks to JS via XPConnect (5.03 KB, patch)
2011-10-10 13:11 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 4: store weak mappings in the CC graph (4.25 KB, patch)
2011-10-10 13:20 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 5: scan WeakMaps (3.25 KB, patch)
2011-10-10 13:27 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 6: weak map cycle collector tests (8.66 KB, patch)
2011-10-10 14:45 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 6: weak map cycle collector tests (8.71 KB, patch)
2011-10-10 14:54 PDT, Andrew McCreight [:mccr8]
no flags Details | Diff | Splinter Review
part 1: add JS friend interface for tracing weak maps (13.74 KB, patch)
2011-10-17 16:21 PDT, Andrew McCreight [:mccr8]
continuation: review+
Details | Diff | Splinter Review
part 2: add nsCycleCollectionTraversalCallback hook for weak mappings (4.12 KB, patch)
2011-10-17 17:44 PDT, Andrew McCreight [:mccr8]
peterv: review+
Details | Diff | Splinter Review
part 3: hook up CC WeakMap callbacks to JS via XPConnect (5.14 KB, patch)
2011-10-17 17:44 PDT, Andrew McCreight [:mccr8]
peterv: review+
Details | Diff | Splinter Review
part 4: store weak mappings in the CC graph (4.26 KB, patch)
2011-10-17 17:45 PDT, Andrew McCreight [:mccr8]
gal: review+
Details | Diff | Splinter Review
part 5: scan WeakMaps (3.25 KB, patch)
2011-10-17 17:45 PDT, Andrew McCreight [:mccr8]
gal: review+
Details | Diff | Splinter Review
part 6: weak map cycle collector tests (8.69 KB, patch)
2011-10-17 17:49 PDT, Andrew McCreight [:mccr8]
gal: review+
Details | Diff | Splinter Review
part 3: hook up CC WeakMap callbacks to JS via XPConnect (5.16 KB, patch)
2011-11-10 16:09 PST, Andrew McCreight [:mccr8]
continuation: review+
Details | Diff | Splinter Review
part 1: add JS interface for tracing weak maps (13.59 KB, patch)
2011-11-23 11:04 PST, Andrew McCreight [:mccr8]
continuation: review+
Details | Diff | Splinter Review
part 4: store weak mappings in the CC graph (4.32 KB, patch)
2011-11-23 11:14 PST, Andrew McCreight [:mccr8]
continuation: review+
Details | Diff | Splinter Review
part 5: scan WeakMaps (3.17 KB, patch)
2011-11-23 11:17 PST, Andrew McCreight [:mccr8]
continuation: review+
Details | Diff | Splinter Review

Description Andrew McCreight [:mccr8] 2011-07-01 11:15:07 PDT
The current cycle collector support for WeakMaps doesn't really work in a number of circumstances.  WeakMaps are weird because a value is alive only if both the map and the key are live.  Normal CC things are live if anything holds onto them.

Properly integrating them into the CC has a few parts:
1. fix GC WeakMap grey marking (see bug 653248)
2. teach the CC to understand WeakMaps
3. add a bunch of tests for various combos of black/grey maps/keys/values
4. expand support for graph dumping to include WeakMaps

This bug will cover 2 (and maybe 3) on this list.  We need 3 to ensure that we actually did the right thing.  It may require adding additional capabilities to testing, as WeakMaps are hard to observe.  I can probably throw together some tests that use the cycle collector graph dumping facilities (if 4 is implemented) to do initial testing, but we should have standard tests to prevent regressions.

Igor's idea for WeakMaps in the CC is to not add any edges to the CC graph for WeakMaps, then after the basic CC scan is done, look over the WeakMap list and do additional flooding of white or black as needed.  Repeat until a fixed point is reached.  There are some corner cases to cover (must ensure that the value is added to the graph even if it is only reachable via the weak map, don't need to worry about the value if it is marked by the GC, etc.) but it seems generally reasonable.

This is generally how the JS GC handles WeakMaps, and should be doable without having to expand the CC graph.
Comment 1 Andrew McCreight [:mccr8] 2011-07-08 10:02:41 PDT
Here's my general game plan for how this can be fixed on the CC side.  The big picture idea is that we first run the CC while ignoring WeakMaps entirely.  We then use the color information to decide how WeakMap values should be marked.  Iterate until we get no more changes.

We don't represent edges from maps/keys to values in the graph, because that would require patching in new edges which is awful, and because these edges don't behave like normal graph edges anyways.

Another wrinkle is that the CC needs to reason about maps or keys that may be marked, and thus may not be represented in the graph itself.  To deal with this, we probably need to have a CC-friendly representation of WeakMaps, containing every map-key-value triple.  If an object is marked or not represented in the graph, we store NULL.  Otherwise, we have a pointer to the PtrInfo, or something like that.

Anyways, here's the kind of steps we need to take, I think:

- Clear the gcWeakMapList at the start of a GC, not the end, so the CC can use it.

- The basic JS scan done during CC graph building should not do anything at all for WeakMap key-value pairs.  (Currently, it creates edges from the map to the key and value.)

- After the standard markRoots (graph construction) is done, mark WeakMaps.

During this scan, we say a JS object is "marked" if it isn't in the graph, or is an object with MAXINT references (eg a standard non-grey JS object).

If either key or map is unmarked, and the value is not in the graph and is grey, add the value to the graph, and do a full CC-building traversal from the value.  (If both key and map are marked, then value must also be marked, so we don't have to add it.)

Repeat this for all key-value pairs, and all WeakMaps, until a fixed point is reached.

- After the standard scanRoots is done, scan WeakMaps.

During this scan, we say an object is "black" if it isn't in the graph, or is marked black in the CC graph.

If the value is black, do nothing.  Otherwise, if both map and key are black, flood black onto the value.  If either map or key aren't black, then flood white onto the value.

- Freeing white objects doesn't need to change, because we don't do anything to JS objects.
Comment 2 Andreas Gal :gal 2011-07-08 10:05:01 PDT
Andrew, if we add weak map treatment to the paper we should have quite some meat.
Comment 3 Andrew McCreight [:mccr8] 2011-07-08 10:07:36 PDT
One thing that I am somewhat concerned about is WeakMaps that are allocated in between GCs, as they won't be in the WeakMap list.  I think that probably UnmarkGrey will ensure that nothing in these new WeakMaps or reachable from the new WeakMaps will be grey, which means that the CC can ignore them safely.
Comment 4 Andrew McCreight [:mccr8] 2011-07-12 15:16:05 PDT
GC/CC WeakMap interface
-----------------------

One thing that I need to work out is the GC/CC interface for WeakMaps.  The easiest way is for the CC to just crawl over the existing list of WeakMaps, gcWeakMapList, which could somehow be exported.  Code to do that in the CC would probably end up being pretty grungy.  In this model, the normal JS traverse wouldn't say anything about weak map children.  This saves us from having to create a new CC-side data structure to represent WeakMaps, but this interface could still support one, by building it during a traversal at the start of the CC.

Another approach that fits in a bit more with the existing interface would be to add a NoteWeakMapChild function to the nsCycleCollectionTraversalCallback interface, akin to NoteXPCOMChild.  This function would take a pointer to the key and value.  So a traverse on a WeakMap would spit out all of the normal children, plus all of the weak map bindings.


CC WeakMap representation
-------------------------

We have to represent the WeakMap bindings somehow in the cycle collector, as a structure separate from the existing cycle collector graph.  We can use the existing list of WeakMaps, but that will require that all of the phases of the CC have to deal with the original heap representation.  Creating a new data structure will preserve the nice property of the current algorithm that we can build our model, then examine it in isolation from the rest of the world.  We could also optimize the representation a bit (ie don't bother representing key value bindings when the value is marked).  Creating a new structure does have the drawback of adding complexity.

Probably the easiest way to implement this would be as a list of HashMaps, though I don't know if we actually need random access.
Comment 5 Jim Blandy :jimb 2011-08-10 13:16:27 PDT
(In reply to Andrew McCreight [:mccr8] from comment #0)
> This bug will cover 2 (and maybe 3) on this list.  We need 3 to ensure that
> we actually did the right thing.  It may require adding additional
> capabilities to testing, as WeakMaps are hard to observe.

By the way, you mind find the 'findReferences' function I added to the JavaScript shell in bug 672736 interesting.

http://hg.mozilla.org/mozilla-central/file/e44dad2d2745/js/src/shell/jsheaptools.cpp#l513

It was intended for exactly this purpose: to expose the edges the GC knows about for the sake of testing. It does not support WeakMaps at the moment: it's built on the JSTracer API, which doesn't handle the iterative marking phase of GC at all. But I think I know how to extend it to do so.

You might consider adding a similar primitive to xpcshell (or whatever you use for CC tests), to directly expose the edges the CC sees.
Comment 6 Andrew McCreight [:mccr8] 2011-08-10 13:31:10 PDT
Yeah, I saw that, but I wasn't thinking about how I might be able to use it for testing, I'll have to look into that.
Comment 7 Andrew McCreight [:mccr8] 2011-08-21 11:16:54 PDT
Created attachment 554740 [details] [diff] [review]
part 1: add JS interface for tracing weak maps

Work in progress.

This adds support needed for a new function JS_TraceWeakMaps that traces all weak maps that were live at the last GC.  To support this, I added a new tracer, with a new callback type.

The callback is defined like this:
typedef void
(* JSWeakMapTraceCallback)(JSWeakMapTracer *trc, void *m, void *k,
                           void *v, uint32 vkind);

m is the weak map, k is the key, v is the value.  We only need to give the kind for v because m and k must be objects.

We cannot use the existing tracing infrastructure, because the CC needs to know about bindings in marked weak maps, ie weak maps that it will not reach during a normal traversal.

In the case of a weak map where the map, key and value are all grey we need to tell the CC about all 3 things, so it can compute whether or not they are in cycles.

I want to iterate over the weak maps using gcWeakMapList from the runtime, but that is just a list of the inner WeakMapBase, not the JSObjects themselves, which is what we need to tell the CC about.  I guess I'll have to remove the "next" pointer from WeakMapBase, and add an explicit list to the runtime.

Hopefully that won't mess with other users of WeakMaps, like the debugger.  I'm still not clear how or if they interact with the GC and CC.  Maybe they never store XPConnect wrapped things, in which case the JS GC is enough.  But then they would rely on the GC to be part of the WeakMapBase linked list I guess?
Comment 8 Andrew McCreight [:mccr8] 2011-08-22 09:03:44 PDT
(In reply to Andrew McCreight [:mccr8] from comment #7)
> I want to iterate over the weak maps using gcWeakMapList from the runtime,
> but that is just a list of the inner WeakMapBase, not the JSObjects
> themselves, which is what we need to tell the CC about.  I guess I'll have
> to remove the "next" pointer from WeakMapBase, and add an explicit list to
> the runtime.

I've solved this instead by adding a JSObject pointer to WeakMapBase that holds a pointer to the enclosing object, if any.  In this way, other uses of WeakMaps that aren't in objects won't be affected.
Comment 9 Andrew McCreight [:mccr8] 2011-08-22 14:00:24 PDT
Created attachment 554959 [details] [diff] [review]
part 1: add JS interface for tracing weak maps

complete, but untested.
- adds a new function JS_TraceWeakMaps that traces every binding in every weak map live at the end of the last GC
- the weak map tracing call back gets the map, key, value, and trace kind of the value.  The map and key must be objects, so no trace kind.  Technically this prevents a new WeakMap instantiation where the key is something aside from Object*, but hopefully that isn't a problem.  The map can be NULL if it is something not contained in an object.  I'm not sure if that makes sense to do or not, but it covers the case where a weak map is being used outside of JS, but is still being traced by the JS GC.  The idea is that CC will just treat these as though the map is marked black by the GC.
- The weak map list is reset at the start of a GC, not the end, so it can be used JS_TraceWeakMaps.
- I added a "DefaultTracePolicy" that handles how the binding tracing is done.
- The marking for a WeakMap no longer visits any of the bindings.  This could probably be cleaned up a bit.
Comment 10 Andrew McCreight [:mccr8] 2011-08-31 17:22:31 PDT
Created attachment 557379 [details] [diff] [review]
part 2: add XPConnect to CC WeakMap interface, doesn't do anything
Comment 11 Andrew McCreight [:mccr8] 2011-08-31 17:32:02 PDT
Created attachment 557381 [details] [diff] [review]
part 3: hook up CC WeakMap callbacks to JS via XPConnect

these patches compile, but are otherwise untested.

this adds two new tracers.  The main trick is that a value can be something that we don't represent in the CC graph, but has a bunch of children.  In this case, we have to add a new binding to our CC weak map representation for every child of the value.  EG if value v has children c1 and c2, then instead of adding a single binding (m, k, v), we have to add (m, k, c1) and (m, k, c2).

Next maybe I'll add some dummy code to the CC callback that prints out what it gets, and see what happens when I run some tests that involve WeakMaps, as I have yet to test this whole JS->XPC->CC chain.

Then I'll throw together some kind of crude structure to hold the WeakMaps.
Comment 12 Andrew McCreight [:mccr8] 2011-09-02 17:32:46 PDT
Created attachment 558001 [details] [diff] [review]
part 4: add weak map nodes to the graph, store the bindings
Comment 13 Andrew McCreight [:mccr8] 2011-09-03 12:07:53 PDT
Created attachment 558085 [details] [diff] [review]
part 1: add JS interface for tracing weak maps
Comment 14 Andrew McCreight [:mccr8] 2011-09-03 12:10:06 PDT
Created attachment 558086 [details] [diff] [review]
part 3: hook up CC WeakMap callbacks to JS via XPConnect
Comment 15 Andrew McCreight [:mccr8] 2011-09-03 12:27:11 PDT
Created attachment 558089 [details] [diff] [review]
part 5: scan WeakMaps

In this part, I add a WeakMap scanning phase to ScanRoots.  After the main scanning from roots is done, we scan over the WeakMaps.  If the map and key are both black, we flood black on the value.  Otherwise, if the map and key are non-grey, we flood white on the value.  If we changed the color of anything while scanning the WeakMaps, we have to rescan them all, as in the GC.

With all 5 of these patches in this bug, the patch that makes values marked grey, and a yet-to-be-written patch to mark WrappedNatives grey, we shouldn't leak WeakMaps any more.  I haven't tested anything, beyond confirming that the browser will run for a few minutes with the patches in this bug applied, which is not surprising, given that there are probably no weak maps.

I think my next step will be to get the two support patches for key and value marking applied or written, then see if Jesse's example gets collected or not.

(Parts 1 and 3 were just rebased due to the trace kind change.  Nothing major.)
Comment 16 Andrew McCreight [:mccr8] 2011-09-03 12:43:22 PDT
Changing this to [MemShrink:P2] because it is blocking a [MemShrink:P2] bug.
Comment 17 Andrew McCreight [:mccr8] 2011-09-09 06:30:38 PDT
My full patch stack came back with a clean try run on Linux 64 debug, and Jesse's example in Bug 653248 doesn't leak.  I need to write more tests.

I haven't uploaded the latest version of the patches yet.
https://tbpl.mozilla.org/?usebuildbot=1&tree=Try&rev=b23bcd4b8e94
Comment 18 Andrew McCreight [:mccr8] 2011-10-03 14:21:49 PDT
Created attachment 564331 [details] [diff] [review]
part 1: add JS friend interface for tracing weak maps

This patch adds a new callback-based WeakMapTracer.  This is used by the new function TraceWeakMaps to visit all weak map bindings (henceforth "weak mappings" to avoid confusion with DOM bindings) of all of the weak maps found by the last garbage collection.  A weak map binding has three parts: the map, the key and the value.  The map and key are always objects.

We must visit every weak map found by the last GC, rather than weak maps we happen to find during the cycle collection traversal, because the CC does not traverse black objects, but still must know about bindings in black weak maps with gray keys, as these can contain cycles we want to collect.  This is in contrast to a standard heap traversal, where we only care about the contents of weak maps we reach during our traversal.

To support this, the head of the weak map list gcWeakMapList is reset at the beginning of a garbage collection instead of at the end.  Because the next pointers of the weak map list are stored in the weak maps themselves this does not cost any additional memory.

This may look disturbing because weak maps allocated since the last garbage collection are not included in the list.  However, the CC only cares about non-gray values.  New weak maps will be white, and any values placed into those maps must have been manipulated since the last garbage collection, and thus must also be non-gray.  Therefore, new weak maps and their contents will all be non-gray, so it is safe to not include them.

Another wrinkle here is that the linked list of weak maps is not a list of JS object weak maps, but of their C++ guts.  Even worse, some weak maps, such as in the debugger, and more and more clients all the time, are not even part of JS Objects!  How do we reconcile this with the fact that the cycle collector only wants to deal with JS Object and DOM objects, and that it is possible that cycles will pass through these C++ weak maps that have their contents managed by the GC?

Fortunately, we can solve all of these problem at once, by adding a field memberOf to each weak map that points to the JS Object that contains the current weak map.  memberOf is set during construction, with an implicit argument of NULL, so callsites outside of jsweakmap.cpp do not need to be changed.  If the memberOf of a weak map is NULL, then we treat the weak map as though it is marked, under the assumption that these C++ weak maps will have their lifetimes explicitly managed by some other mechanism, and will not themselves be involved in DOM-JS cycles (but their bindings still can be).

To support the various cycle collection behavior that is needed for each instantiation of the WeakMap template, I added the notion of a "default trace policy" which is used to map the actual types of the keys and values onto the callback proper.
Comment 19 Andrew McCreight [:mccr8] 2011-10-03 14:39:07 PDT
Created attachment 564341 [details] [diff] [review]
part 2: add nsCycleCollectionTraversalCallback hook for weak mappings

Add a method NoteWeakMapping to nsCycleCollectionTraversalCallback.  This is how XPConnect will tell the cycle collector about all of the bindings it finds when it invokes the JS engine weak map tracing callback we added in part 1.

Leave the GCGraphBuilder as a dummy implementation for now.
Comment 20 Andrew McCreight [:mccr8] 2011-10-03 15:20:57 PDT
Created attachment 564351 [details] [diff] [review]
part 3: hook up CC WeakMap callbacks to JS via XPConnect

In this third patch, we connect the JS weak mapping callback of part 1 to the CC weak mapping callback of part 2.  The bulk of this patch is constructing a WeakMapTracer.

This layer filters out a number of standard cases where the weak map binding can't be part of a garbage cycle.  These are based on properties of the value, not the map or keys.  If the value in the mapping is a string, or is non-gray, we do not report the binding to the CC.

In the cycle collector, if there's an edge from an object A to an object B, and B is of a kind we don't represent in the CC graph, then we instead add edges from A to any C such that there is a path from B to C that does not pass through anything that has a GC kind that we do represent in the CC graph.  This also arises for weak maps: if we have a mapping with map m, key k, and value v, if v is a non-CC kind, then for any other value v' that is reachable from v without passing through a thing with non-CC kind, we add a binding with map m, key k, and value v' to the CC.  This requires the use of a conventional JSTracer, using TraceWeakMappingChild, inside the weak map tracer.  

Once the weak map tracer is constructed, we invoke js::TraceWeakMaps in BeginCycleCollection, after the call to AddXPConnectRoots.

The final piece of this patch disables eager weak map tracing for the cycle collector (I added this flag in Bug 681104), because as I said in the notes for part 1, we care about weak maps the GC encountered, not the ones the CC encounters.
Comment 21 Andrew McCreight [:mccr8] 2011-10-04 09:09:50 PDT
Created attachment 564573 [details] [diff] [review]
part 4: store weak mappings in the CC graph

This patch implements a new cycle collector data structure to store weak mappings.  This is the simplest possible structure: it is a list of triples (map, key, value).  We only ever iterate over every triple, so this isn't too terrible.*

There's a variant of AddNode used that handles null objects, and filters out non-gray things, etc.  It isn't clear that the current division is quite right.  We can probably do some more testing of the grayness of map and key in XPC, then not check that in the cycle collector (well, add some asserts).  That would reduce some checks.  I'm also not sure where null can creep in.  The map can be null, due to "naked" weak maps, but can the key be null?

* We could save some time and space by making an array of arrays of pairs, where the arrays of pairs represent an individual weak map, but I prefer to add additional complexity in a later patch.  Another optimization that can be done is that if either the map or value is marked then we can add them to a special list where only one thing needs to be checked.  I suspect the quadratic weak map scanning algorithm will be a larger impediment to the heavy use of weak maps than the weak map data structure I am using in the CC.
Comment 22 Andrew McCreight [:mccr8] 2011-10-04 12:49:04 PDT
Created attachment 564643 [details] [diff] [review]
part 5: scan WeakMaps

This patch adds a new function ScanWeakMaps() to the cycle collector, which is run in ScanRoots() after the main graph coloring is complete.

The function wmpiColor returns the color of a weak map ptr info.  We need this additional bit of null checking because for maps and keys we use null to represent a marked object that is not in the cycle collector graph.  (This is a bit of a micro-optimization, and we could just represent them as marked nodes with no successors.)

The actual weak map scanning algorithm is iterative, like the GC.  We iterate over all weak map bindings.  For each binding, we get the color of the map, key and value.  If the map and key are both black (ie reachable), then we flood black on the value, if it isn't already black.

Otherwise, we don't need to do anything for a binding.  Because weak mappings (maps, keys and values) are all cycle collector roots (in the sense of WalkFromRoots, not in the sense of keeping objects alive) they will all be colored either black or white by WalkFromRoots() by the time we get to ScanWeakMaps().  For instance, if a value is reachable only via a weak map binding, it will end up getting colored white prior to ScanWeakMaps().  As in the standard CC scanning algorithm, and object that is white can become black.
Comment 23 Andrew McCreight [:mccr8] 2011-10-06 17:51:19 PDT
Created attachment 565416 [details] [diff] [review]
A variety of tests of weak map cycle collector interaction

This adds a number of test of weak map cycle collector integration.  One test is Jesse's example from Bug 653248.

There's also a series of basic tests, that checks out every combination of {black weak map, gray live weak map, gray dead weak map} and {black key, gray live key, gray dead key}, making sure that things that should be alive are alive, and that those that should be dead are dead.

I also have chained entries in a chained weak map, starting from a live gray key (where all entries should be preserved) and one where the entries form a dead loop that should be collected.

There's also a test of XPCWrappedNative keys, but they don't work currently (this patch stack needs another stack for those), so the test is a todo test.

I confirmed that these tests all pass on top of this patch stack, and the ones I expect to fail actually fail on trunk.
Comment 24 Andrew McCreight [:mccr8] 2011-10-07 09:02:27 PDT
I did a try run for this:  https://tbpl.mozilla.org/?tree=Try&rev=c9e426f7a0a1

It looks okay so far.  There are permaoranges on two of the tests, but these seem to be known (bug 692605), though I don't know why they'd affect my old trunk.  Next up, I'm going to rebase, as there have been a lot of refactoring kind of changes since I last did that.
Comment 25 Andrew McCreight [:mccr8] 2011-10-10 12:59:44 PDT
Created attachment 566002 [details] [diff] [review]
part 1: add JS friend interface for tracing weak maps

Most of the changes here compared to the last version were generalizing the callback interface to handle the weak maps in the debugger that now use js::Cells as keys instead of JSObjects.  There was also a bit of minor rebasing.
Comment 26 Andrew McCreight [:mccr8] 2011-10-10 13:00:41 PDT
Created attachment 566003 [details] [diff] [review]
part 1: add JS friend interface for tracing weak maps

Uploaded wrong version of the patch before.
Comment 27 Andrew McCreight [:mccr8] 2011-10-10 13:02:12 PDT
Created attachment 566004 [details] [diff] [review]
part 2: add nsCycleCollectionTraversalCallback hook for weak mappings
Comment 28 Andrew McCreight [:mccr8] 2011-10-10 13:11:35 PDT
Created attachment 566008 [details] [diff] [review]
part 3: hook up CC WeakMap callbacks to JS via XPConnect

As in part 1, I had to generalize the interface a bit to support weak maps with js::Cells as keys.  This is slightly scary, because if the Cell does not have an AddToCCKind, then it won't be represented in the CC graph, and thus the CC can't reason about whether it is really live or not.  This is okay for now, because the only uses of this are in the debugger, and if I understand jimb correctly, these keys can only be scripts or objects, which are both (now) CC kinds.

To make sure things don't fall apart if this changes (as this probably feels like a fairly obscure requirement for somebody who is working in the JS engine), I added an assert that the key must have a CC kind.  As an emergency fallback for opt builds, I added a dynamic check.  If it turns out the key doesn't have a CC kind, then we treat the key as being marked.  This can cause leaks, but if we instead ignore the weak map edge, we can end up freeing objects that are live.
Comment 29 Andrew McCreight [:mccr8] 2011-10-10 13:20:09 PDT
Created attachment 566010 [details] [diff] [review]
part 4: store weak mappings in the CC graph
Comment 30 Andrew McCreight [:mccr8] 2011-10-10 13:27:52 PDT
Created attachment 566015 [details] [diff] [review]
part 5: scan WeakMaps
Comment 31 Andrew McCreight [:mccr8] 2011-10-10 14:45:19 PDT
Created attachment 566040 [details] [diff] [review]
part 6: weak map cycle collector tests

Peter, I don't know if you are the right person to look over these.

These patches are intended to be run on top of the rest of the patches in this bug, plus the patch I just uploaded for Bug 653248.  Note that even with these patches, we still leak with XPCWrappedNative WeakMap keys.  These keys are currently marked black to avoid the GC's wrapper optimizations.   Instead, they should be marked gray, and further work of some sort needs to be done to avoid the CC's wrapper optimization.  See Bug 680937.
Comment 32 Andrew McCreight [:mccr8] 2011-10-10 14:54:54 PDT
Created attachment 566041 [details] [diff] [review]
part 6: weak map cycle collector tests
Comment 33 Bill McCloskey (:billm) 2011-10-10 17:16:45 PDT
Comment on attachment 566003 [details] [diff] [review]
part 1: add JS friend interface for tracing weak maps

Review of attachment 566003 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsweakmap.cpp
@@ +82,5 @@
> +inline void
> +WeakMapBase::traceAllMappings(WeakMapTracer *tracer)
> +{
> +    JSRuntime *rt = tracer->context->runtime;
> +    for (WeakMapBase *m = rt->gcWeakMapList; m; m = m->next) {

No braces needed here.

@@ +88,5 @@
> +    }
> +}
> +
> +void
> +TraceWeakMaps(WeakMapTracer *trc)

We're trying to keep API stuff like this contained in jsfriendapi.cpp, so could you move it there?

::: js/src/jsweakmap.h
@@ +132,5 @@
>  // A policy template holding default marking algorithms for common type combinations. This
>  // provides default types for WeakMap's MarkPolicy template parameter.
>  template <class Key, class Value> class DefaultMarkPolicy;
>  
> +// A policy template holding default tracing algorithms for common type combinations.  This

One space after the period or Brendan will murder us.

@@ +175,5 @@
>      // Remove entries whose keys are dead from all weak maps marked as live in this
>      // garbage collection.
>      static void sweepAll(JSTracer *tracer);
>  
> +    // Trace all delayed weak map bindings.  Used by the cycle collector.

Space thing again.

@@ +359,5 @@
> +};
> +
> +// Only gc::Cells that are represented directly in the cycle collector graph should
> +// be used as keys, so the cycle collector can reason about whether they are alive
> +// or not.  See AddToCCKind in nsXPConnect.cpp.

Again, one space after the period. What happens if you use a weak map on some GC that's not represented in the CC graph? Bad things? Can you assert against this in the cycle collector?
Comment 34 Andrew McCreight [:mccr8] 2011-10-10 18:06:38 PDT
Thanks for the quick review.
(In reply to Bill McCloskey (:billm) from comment #33)
> What happens if you use a weak map on
> some GC that's not represented in the CC graph? Bad things? Can you assert
> against this in the cycle collector?

Yeah, I do deal with this in TraceWeakMapping in nsXPConnect.cpp in my third patch.  I have an assert, and then a back-up because I'm concerned about what kind of badness might happen.

+    // The cycle collector can only properly reason about weak maps if it can
+    // reason about the liveness of their keys, which in turn requires that
+    // the key can be represented in the cycle collector graph.  All existing
+    // uses of weak maps use either objects or scripts as keys, which are okay.
+    JS_ASSERT(AddToCCKind(kkind));
+
+    // As an emergency fallback for non-debug builds, if the key is not
+    // representable in the cycle collector graph, we treat it as marked.  This
+    // can cause leaks, but is preferable to ignoring the binding, which could
+    // cause the cycle collector to free live objects.
+    if(!AddToCCKind(kkind))
+        k = nsnull;

Because you can't precisely compute whether the key is alive or dead, you have to make an assumption one way or the other.  If you assume the key is live, and it is actually dead, then you'll end up leaking.  If you assume the key is dead, and it is actually alive, then you can end up freeing things you shouldn't, because the only path from a root to the weak map value could be through the weak map binding, so the CC doesn't realize it should be alive.  It seems safer to leak.  "Tis better to have lived and leaked" or something.

To implement assuming the key is live, we treat it as marked.  It isn't a real CC node, subject to the black-GC-marking optimization, so that should be okay.  Implementing assuming that the key is dead would just mean ignoring the binding.
Comment 35 :Ms2ger (⌚ UTC+1/+2) 2011-10-11 04:39:34 PDT
Comment on attachment 566008 [details] [diff] [review]
part 3: hook up CC WeakMap callbacks to JS via XPConnect

>--- a/js/src/xpconnect/src/nsXPConnect.cpp
>+++ b/js/src/xpconnect/src/nsXPConnect.cpp
>+TraceWeakMappingChild(JSTracer* trc, void *thing, JSGCTraceKind kind)

>+    NoteWeakMapChildrenTracer *tracer =
>+        static_cast<NoteWeakMapChildrenTracer*>(trc);
>+    if(kind == JSTRACE_STRING)
>+        return;

Really minor nit: maybe move this if up two lines?
Comment 36 :Ms2ger (⌚ UTC+1/+2) 2011-10-11 04:41:43 PDT
Comment on attachment 566015 [details] [diff] [review]
part 5: scan WeakMaps

>--- a/xpcom/base/nsCycleCollector.cpp
>+++ b/xpcom/base/nsCycleCollector.cpp

>+        anyChanged = PR_FALSE;
>+                anyChanged = PR_TRUE;

true/false in new code please.
Comment 37 Andrew McCreight [:mccr8] 2011-10-11 10:10:44 PDT
(In reply to Ms2ger from comment #35)
> Really minor nit: maybe move this if up two lines?

Sure, seems reasonable to me.

(In reply to Ms2ger from comment #36)
> true/false in new code please.

Ehsan was going to run a script to change everything to true/false at some point, so I was going to leave it as PR_TRUE/PR_FALSE until then for consistency.  Though maybe at this point my patch will probably land after that...
Comment 38 Andrew McCreight [:mccr8] 2011-10-17 16:21:44 PDT
Created attachment 567613 [details] [diff] [review]
part 1: add JS friend interface for tracing weak maps

Addressed Bill's review comments, carrying forward his r+.
Comment 39 Andrew McCreight [:mccr8] 2011-10-17 17:44:01 PDT
Created attachment 567632 [details] [diff] [review]
part 2: add nsCycleCollectionTraversalCallback hook for weak mappings
Comment 40 Andrew McCreight [:mccr8] 2011-10-17 17:44:33 PDT
Created attachment 567633 [details] [diff] [review]
part 3: hook up CC WeakMap callbacks to JS via XPConnect
Comment 41 Andrew McCreight [:mccr8] 2011-10-17 17:45:14 PDT
Created attachment 567634 [details] [diff] [review]
part 4: store weak mappings in the CC graph
Comment 42 Andrew McCreight [:mccr8] 2011-10-17 17:45:54 PDT
Created attachment 567635 [details] [diff] [review]
part 5: scan WeakMaps
Comment 43 Andrew McCreight [:mccr8] 2011-10-17 17:49:14 PDT
Created attachment 567639 [details] [diff] [review]
part 6: weak map cycle collector tests

These updated files should basically be the same as before.  I updated to deal with the XPConnect moving and syntax cleanup, the removal of PR_TRUE/PR_FALSE in the 2 places I used it, and did some additional minor fussing with style.

Try servering it: https://tbpl.mozilla.org/?tree=Try&rev=3d49d40b0d05

I did a try run before that looked okay, but I think I have a few changes in the final scanner since then.
Comment 44 Peter Van der Beken [:peterv] 2011-10-26 13:41:41 PDT
Comment on attachment 567633 [details] [diff] [review]
part 3: hook up CC WeakMap callbacks to JS via XPConnect

Review of attachment 567633 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/xpconnect/src/nsXPConnect.cpp
@@ +528,5 @@
> +    if (AddToCCKind(vkind)) {
> +        tracer->mCb.NoteWeakMapping(m, k, v);
> +    } else {
> +        NoteWeakMapChildrenTracer ctrc(tracer->mCb, m, k);
> +        JS_TRACER_INIT(&ctrc, tracer->context, TraceWeakMappingChild);

I wonder if it would make sense to put these two lines in BeginCycleCollection too, and just update mMap and mKey here. It might save some cycles?
Comment 45 Andrew McCreight [:mccr8] 2011-10-27 09:13:44 PDT
(In reply to Peter Van der Beken [:peterv] from comment #44)
> I wonder if it would make sense to put these two lines in
> BeginCycleCollection too, and just update mMap and mKey here. It might save
> some cycles?
That's a good idea.  I was wondering about that myself.  Probably the easiest way to do this is to add a NoteWeakMapChildrenTracer as a field of a NoteWeakMapsTracer.
Comment 46 Andrew McCreight [:mccr8] 2011-10-27 16:15:09 PDT
One test is failing now.  I'm not sure when that started.  I'm investigating.
Comment 47 Andrew McCreight [:mccr8] 2011-10-28 07:20:11 PDT
Oh, I forgot to add that the test that is failing is a cycle that passes through both weak maps and DOM that is not being collected.  The intriguing part is that from my preliminary investigation this does not appear to be a problem with my patches: there's a JS object that is part of the cycle, but not a weak map key or value, that is being marked, so I'm not sure how my patches could be causing it.  It is possible this is related to the GC badness we're seeing.
Comment 48 Andrew McCreight [:mccr8] 2011-11-07 17:52:47 PST
Test seems to pass when done with other tests, but fails when run by itself.  An object that is part of the cycle is somehow marked as being on the C++ stack by the GC, which causes the cycle to be held alive.  It also appears that the GC frees the cycle, which doesn't make any sense, as it passes through DOM.
Comment 49 Andrew McCreight [:mccr8] 2011-11-10 16:01:04 PST
I investigated the failure, but never really came up with an explanation as to why a random object was being found by the conservative stack scanner.  I updated to m-c tip today and the error is gone, so I guess there was some bug elsewhere that was introduced and then fixed in the last month.
Comment 50 Andrew McCreight [:mccr8] 2011-11-10 16:09:24 PST
Created attachment 573686 [details] [diff] [review]
part 3: hook up CC WeakMap callbacks to JS via XPConnect

Hoisted initialization of the child tracer to the main tracer.  Carrying forward peterv's r+.
Comment 51 Andrew McCreight [:mccr8] 2011-11-10 17:30:13 PST
https://tbpl.mozilla.org/?tree=Try&rev=c7dabe919139
Comment 52 Andrew McCreight [:mccr8] 2011-11-11 09:15:06 PST
Try run looks good.  I ran Moth a number of times to try to see if I introduced any intermittent problems, as that's where the new WeakMap tests are.  There's one small leak that showed up once, but that looks like a known one.
Comment 53 Andrew McCreight [:mccr8] 2011-11-20 09:31:44 PST
review ping
Comment 54 Andreas Gal :gal 2011-11-20 12:45:09 PST
Comment on attachment 567634 [details] [diff] [review]
part 4: store weak mappings in the CC graph

Review of attachment 567634 [details] [diff] [review]:
-----------------------------------------------------------------

::: xpcom/base/nsCycleCollector.cpp
@@ +1829,5 @@
> +GCGraphBuilder::AddWeakMapNode(void *node)
> +{
> +    nsCycleCollectionParticipant *cp;
> +
> +    if (!node)

Why would node ever be null here?
Comment 55 Andrew McCreight [:mccr8] 2011-11-20 12:50:35 PST
(In reply to Andreas Gal :gal from comment #54)
> Why would node ever be null here?
If the map or key are marked black by the GC, we pass in NULL for them so we don't have to represent them in the CC graph.  The CC treats NULL maps or keys as black nodes, as reflected in wmpiColor.

This can happen if the map, but not the key, is marked black (or vice versa).  In this case, the edge really just acts like a normal extra edge for the non-black key or value, but inserting additional edges into the graph is annoying so they come along for the ride in the full weak map iteration.
Comment 56 Andrew McCreight [:mccr8] 2011-11-20 12:51:46 PST
I guess I should add a comment to that effect, maybe near the definition of struct WeakMapping.
Comment 57 Andreas Gal :gal 2011-11-20 12:52:11 PST
Comment on attachment 567635 [details] [diff] [review]
part 5: scan WeakMaps

wmpiColor is a pretty bad name. Use something descriptive and CamelCase.

Also, get a pointer to mWeakMaps in the loop instead of indexing with i all the time.
Comment 58 Andreas Gal :gal 2011-11-20 12:53:10 PST
Comment on attachment 567639 [details] [diff] [review]
part 6: weak map cycle collector tests

Nice test.
Comment 59 Andreas Gal :gal 2011-11-20 12:57:08 PST
Comment on attachment 567634 [details] [diff] [review]
part 4: store weak mappings in the CC graph

AddWeakMapNode shouldn't be called if node is null. Assert and fix the caller.
Comment 60 Andreas Gal :gal 2011-11-20 12:58:58 PST
We should have peterv look this over as well, but in the meantime lets land this.
Comment 61 Andrew McCreight [:mccr8] 2011-11-20 13:03:45 PST
Thanks for the reviews!  I went over a slightly older version with Peter at All-Hands, so he's at least looked at it a little.  I'll land it today or tomorrow.
Comment 62 Andrew McCreight [:mccr8] 2011-11-21 15:42:10 PST
I need to figure out how to update this for write barriers and I'm travelling tomorrow so I may not get a chance to land this for a few more days.
Comment 63 Andrew McCreight [:mccr8] 2011-11-23 11:04:55 PST
Created attachment 576550 [details] [diff] [review]
part 1: add JS interface for tracing weak maps

The only change here is some type changes and value unwrapping in DefaultTracePolicy to deal with the write barriers.  The CC doesn't write to JS objects in weak maps, so there's no substantive change.  Carrying forward billm's review, though I'm going to get him to double check my changes before I commit it.
Comment 64 Andrew McCreight [:mccr8] 2011-11-23 11:14:14 PST
Created attachment 576558 [details] [diff] [review]
part 4: store weak mappings in the CC graph

Addressed gal's review comments, changed the map, key and val fields to mMap, mKey, mVal to match the rest of the file.  Carrying forward gal's review.
Comment 65 Andrew McCreight [:mccr8] 2011-11-23 11:17:21 PST
Created attachment 576560 [details] [diff] [review]
part 5: scan WeakMaps

Addressed gal's review comments by factoring out the mWeakMaps indexing.  Once I did that, wmpiColor seemed pointless, so I just inlined it and removed it, adding a comment about the null weirdness.  Carrying forward gal's review.

Another (hopefully final) try run: https://tbpl.mozilla.org/?tree=Try&rev=0cd03f2c416f

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