Totally ridiculous overkill explanation. It was a late night.

Simplifying GC tracing of Debugger API frames

As part of the Debugger implementation cleanup, we would like to simplify the
relationship between the garbage collector and Debugger API objects. Although
Debugger does have some requirements that preclude a completely straightforward
implementation, there are still some opportunities to simplify the code. This
writeup considers how garbage collection treats JavaScript stack frames, the
Debugger.Frame objects that representing , and the Debugger objects they
belong to.

Desired behavior

The fundamental rule of garbage collection is the “Mikado principle”: objects
are only collected when they would not be missed. GC is an unobservable
optimization, in that it should have no visible effect on the program's
behavior, other than that more memory is available than one would expect.

In that light, we require certain behaviors from the Debugger implementation:

a) If a Debugger is reachable, its live Debugger.Frames must not be
collected. Using the Debugger's getNewestFrame method and the frame's
older accessor, the user can produce Debugger.Frame objects for all live
stack frames. The Debugger API promises to return the same Debugger.Frame
object every time for a given frame, so that the user can store extra
properties on the Debugger.Frame or use it as a key in a weak map. This
means that, if the Debugger is reachable and the stack frames are still
live, any Debugger.Frame objects representing them would be missed if
collected.

b) A live Debugger.Frame with onStep or onPop hooks must not be
collected. Even if its owning Debugger is unreachable, when the
underlying stack frame returns or completes a step of execution, those hooks
must be called, which is an observable effect.

Requirement a) means that the system must behave as if there is an owning edge
from each Debugger to each Debugger.Frame representing a frame on the stack.
This is easy: a Debugger owns a hash table mapping AbstractFramePtrs to
Debugger.Frames; these entries' values are the required edges.

Requirement b) is a bit harder. It means that the system must behave as if there
is an owning edge from each frame on the stack to every Debugger.Frame
representing it that has a hook set, but it's not practical to represent these
edges directly as a pointer in the stack frame: since almost exactly 100% of
stack frames are never debuggees, a nullable pointer in every stack frame would
be a waste of memory and initialization time. Some sort of “rare pointer”
representation, like a hash table that maps a frame's AbstractFramePtr to the
Debugger.Frame representing it, will be necessary in any feasible solution.

There are a few more behaviors we'd like to provide, even though they cannot be
detected by JavaScript:

c) Under the right circumstances, it should be possible to collect a Debugger
even while its debuggee globals are still alive. If a Debugger has no hooks
set, and no breakpoints, and no Debugger.Frames with hooks set, and
JavaScript cannot reach it to add such, then it never would be missed.

d) Under the right circumstances, it should be possible to collect a
Debugger.Frame even while its referent stack frame is still alive. If it
has no hooks set, and JavaScript cannot reach it, then the hooks will never
be set in the future, its properties cannot be inspected, and it cannot be
used as a key in a weak map query, so it never would be missed.

The present implementation

Even accepting that complete simplicity isn't possible, the current
implementation is a bit baroque. (Perhaps it is byzantine, or maybe even
gothic.) At present, marking Debugger.Frames works like this:

• On each pass through the iterative weak map marking cycle, we search the
  runtime for marked global objects.

• For each marked global, we iterate over the Debuggers debugging it, if any.
  (We do not mark these Debuggers at this point.)

• For each such Debugger that is not yet marked, we iterate over its hash
  table mapping AbstractFramePtrs of live stack frames to Debugger.Frames.

• If a Debugger.Frame has a live onPop or onStep hook, then we mark its
  owning Debugger.

• Marking a Debugger marks all Debugger.Frames in its frame table.

• In the process, if we marked any previously unmarked Debuggers, then we go
  around the weak map marking cycle again.

This satisfies the requirements explained above:

a) Marking a Debugger marks its hash table of frames, thus marking the
Debugger.Frames.

b) Every frame on the stack entrains the global in whose scope the frame's code
is running, so those globals will be marked. And if a Debugger.Frame for
that stack frame has any hooks set, the above process will visit the
Debugger, find the Debugger.Frame, and mark it.

c) If a given Debugger has no Debugger.Frames with hooks set, then the above
process will not mark it.

d) If a given Debugger has no Debugger.Frames with hooks set, then the above
process will not mark any of its Debugger.Frames.

A simpler approach

An iterative algorithm like the one described above is generally required
whenever owning edges are represented as reversed pointers. In the ordinary
case, when an owning object holds a pointer to an object it owns, the marking
algorithm can simply follow the pointer to find the object to be marked. But
when there is a weak map, even though the liveness of an entry's key is what
causes the value to be alive, there is no pointer from the key to the entry or
its value; instead, the map entry holds a pointer to the key. In other words,
the pointer represents the converse of the ownership relation. The only way to
discover when the value should be traced is to come back periodically and check
if the key has been marked.

It would seem at first glance that the same treatment is required here: in the
Debugger API, a stack frame effectively co-owns the Debugger.Frames that
represent it, along with the Debugger, so the AbstractFramePtr keys in the
Debugger's frame table are reversed pointers.

But in fact, the iterative treatment is not necessary. Stack frames are not
managed by the GC; rather, they are destroyed at well-defined points, and their
entries are removed from Debuggers' tables promptly. In a Debugger's frame
table, every key is guaranteed to be live. It is never necessary to revisit the
frame table to see if more keys have been marked, or indeed to check keys for
liveness at all.

So instead of the algorithm above, we can take a more direct approach.

• At part of the root marking phase, find all Debuggers, marked or not, that
  have any Debugger.Frames in their AbstractFramePtr-keyed hash tables.

• If any Debugger.Frame has hooks set, mark it.

• As at present, marking a Debugger.Frame marks its owning Debugger.

• As at present, marking a Debugger marks all Debugger.Frames in its live
  frame table.

Like the more complex approach used at present, this simplified version meets
all our requirements:

a) As before, the edges from a Debugger to its Debugger.Frames for live
stack frames are traced.

b) Since we search every Debugger's frame table for Debugger.Frames with
hooks, and every entry in those tables serves a live stack frame, we've
retained all the necessary Debugger.Frames.

c) If a Debugger.Frame has no hooks set, this process does not mark its
Debugger.

d) If a Debugger.Frame has no hooks set, this process does not mark it.

If a Debugger.Frame for a live stack frame has hooks set, it should not be
collected, since the failure to call the hooks would be visible to JS.

The prior code handles tracing Debugger.Frames entirely through an addition to
the iterative weak map marking process: each time through the cycle, we also
check all unmarked Debuggers of marked globals for Debugger.Frames with any
hooks set, and if any such Debugger.Frames exist, we mark the Debugger.

This is a circuitous way to get exactly the same effect as simply marking, once
at the start of GC (like any other root set), all Debugger.Frames for live stack
frames that have hooks set, as if there were an owning edge from each stack
frame to each Debugger.Frame with hooks set.

This patch removes the code from Debugger::hasAnyLiveHooks that checks
Debugger::frames, and adds a new function, DebugAPI::traceFramesWithLiveHooks,
that is called once from root marking.

JS-centric try push: https://treeherder.mozilla.org/#/jobs?repo=try&revision=b1da0d03297840d1e5cd26ffb9a1bb76b184f581

Move odd circumlocution into its own function, to make it clearer what problem
it's trying to address. We'll add another use later in the patch series.

https://hg.mozilla.org/mozilla-central/rev/f771b9571948
https://hg.mozilla.org/mozilla-central/rev/95b92f0cb96e