-
Michael Lippautz authored
The following implements a snapshotting algorithm for C++ objects that also filters strongly-connected components (SCCs) of only "hidden" objects that are not (transitively) referencing any non-hidden objects. C++ objects come in two versions. a. Named objects that have been assigned a name through NameProvider. b. Unnamed objects, that are potentially hidden if the build configuration requires Oilpan to hide such names. Hidden objects have their name set to NameProvider::kHiddenName. The main challenge for the algorithm is to avoid blowing up the final object graph with hidden nodes that do not carry information. For that reason, the algorithm filters SCCs of only hidden objects, e.g.: ... -> (object) -> (object) -> (hidden) -> (hidden) In this case the (hidden) objects are filtered from the graph. The trickiest part is maintaining visibility state for objects referencing other objects that are currently being processed. Main algorithm idea (two passes): 1. First pass marks all non-hidden objects and those that transitively reach non-hidden objects as visible. Details: - Iterate over all objects. - If object is non-hidden mark it as visible and also mark parent as visible if needed. - If object is hidden, traverse children as DFS to find non-hidden objects. Post-order process the objects and mark those objects as visible that have child nodes that are visible themselves. - Maintain an epoch counter (StateStorage::state_count_) to allow deferring the visibility decision to other objects in the same SCC. This is similar to the "lowlink" value in Tarjan's algorithm for SCC. - After the first pass it is guaranteed that all deferred visibility decisions can be resolved. 2. Second pass adds nodes and edges for all visible objects. - Upon first checking the visibility state of an object, all deferred visibility states are resolved. For practical reasons, the recursion is transformed into an iteration. We do not use plain Tarjan's algorithm to avoid another pass over all nodes to create SCCs. Follow ups: 1. Adding wrapper nodes for cpp objects that are wrappables for V8 wrappers. 2. Adding detachedness information. Change-Id: I6e127d2c6d65e77defe08e39295a2594f463b962 Bug: chromium:1056170 Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2467854 Commit-Queue: Michael Lippautz <mlippautz@chromium.org> Reviewed-by: Ulan Degenbaev <ulan@chromium.org> Reviewed-by: Omer Katz <omerkatz@chromium.org> Cr-Commit-Position: refs/heads/master@{#70567}
02849fd9