• Michael Lippautz's avatar
    cppgc-js: Add snapshot for C++ objects · 02849fd9
    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: 's avatarUlan Degenbaev <ulan@chromium.org>
    Reviewed-by: 's avatarOmer Katz <omerkatz@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#70567}
    02849fd9
Name
Last commit
Last update
..
api Loading commit data...
asmjs Loading commit data...
ast Loading commit data...
base Loading commit data...
builtins Loading commit data...
codegen Loading commit data...
common Loading commit data...
compiler Loading commit data...
compiler-dispatcher Loading commit data...
d8 Loading commit data...
date Loading commit data...
debug Loading commit data...
deoptimizer Loading commit data...
diagnostics Loading commit data...
execution Loading commit data...
extensions Loading commit data...
flags Loading commit data...
handles Loading commit data...
heap Loading commit data...
ic Loading commit data...
init Loading commit data...
inspector Loading commit data...
interpreter Loading commit data...
json Loading commit data...
libplatform Loading commit data...
libsampler Loading commit data...
logging Loading commit data...
numbers Loading commit data...
objects Loading commit data...
parsing Loading commit data...
profiler Loading commit data...
protobuf Loading commit data...
regexp Loading commit data...
roots Loading commit data...
runtime Loading commit data...
sanitizer Loading commit data...
snapshot Loading commit data...
strings Loading commit data...
tasks Loading commit data...
third_party Loading commit data...
torque Loading commit data...
tracing Loading commit data...
trap-handler Loading commit data...
utils Loading commit data...
wasm Loading commit data...
zone Loading commit data...
DEPS Loading commit data...
OWNERS Loading commit data...