Static GC Rooting Hazard Analysis

The rooting hazard analysis is a global (whole-program) analysis as opposed to the function-local analysis like the current clang-based static analyses that we're using.

• local: look at one function at a time in isolation
• global: use information gathered from the entire source tree
  • even if the main processing looks at a function at a time

There has been talk about implementating a global analysis infrastructure on top of the clang plugin based analysis setup, but no concrete plans as yet. (Such things have been implemented, eg PhASAR, but I haven't looked at them.)

Some code paths may never be invoked in practice, but the analysis will assume that they might be.

• Any function pointer will be assumed to call something that can GC, unless annotated otherwise.
• Some paths leading to a GC can never be taken.
• Some GC pointer variables will never store a GC pointer (eg JS::Value that only holds undefined or numeric values in practice)

• Analysis relies on the C++ type system
  • if you cast to void* or uintptr_t, the analysis can't see it.
  • Container types (eg hashtables) need to be specifically annotated for the analysis to know that the overall array requires rooting.
    • eg HashMap<T> needs rooting iff T needs rooting
• If you take the address of a GC pointer, the analysis loses track of it.
  • It will not complain if you hold a pointer to a pointer live across a GC.
    • If that pointer is rooted or traced, this is ok.
    • But at the point of the GC, we don't know if it is or not.
• Some interior pointers (eg the pointer to the characters in a string) are not considered to be invalidatable GC pointers.
  • We have classes for managing these more safely, as well as (dynamically enforced) IPromiseIWillNotGC tokens.
    • AutoSuppressGCAnalysis, AutoCheckCannotGC
    • not AutoAssertNoGC (which is a dynamic check that does not disable the static checking)
• Some hard-to-handle cases are annotated away.

• To be fully conservatively correct, callgraph should include an edge through any function pointer invocation to every other function in the program.
  • Executing JS source is assumed to call any native JS function in existence.

• The conversion from C++ to the Sixgill data structures is not perfect.
• gcc lies occasionally
• some rare constructs are not handled and result in that function body being discarded
  • I keep track of how many of these there are
• some correctness fixes find too many false alarms (work is ongoing)
  • Big one: virtual method resolution is incorrect.
• sfink writes buggy code

• nasty awful opaque 'tree' type with unions of structs of unions of unions…
• accessed via macros, some of which typecheck
• newer features reuse old fields and accessors
• it all feels pretty random

bool XIL_IsBaseField(tree field, bool *offset_zero)
{
  if (c_dialect_cxx() && DECL_NAME(field) == NULL) {
    tree type = TREE_TYPE(field);
    tree idnode = TYPE_NAME(type);
    if (TREE_CODE(type) == RECORD_TYPE && idnode &&
        TREE_CODE(idnode) == TYPE_DECL && !XIL_IsAnonymousCxx(idnode)) {
      // figure out if this field is at offset zero.
      tree offset = DECL_FIELD_OFFSET(field);
      tree bit_offset = DECL_FIELD_BIT_OFFSET(field);
      int byte_offset = TREE_UINT(offset) + (TREE_UINT(bit_offset) / 8);

      if (offset_zero)
        *offset_zero = (byte_offset == 0);
      return true;
    }
  }

  return false;
}

Currently expands to __attribute__((annotate("stuff"))).

My apologies for the names. Surprisingly enough, I was not intentionally going for the "I can haz cheezburger" vibe.

• JS_HAZ_GC_POINTER : this type holds a GC pointer, possibly encoded.
• JS_HAZ_ROOTED : this type roots its contained GC pointer.
• JS_HAZ_GC_INVALIDATED : this type contains something that is invalidated during a GC.
• JS_HAZ_ROOTED_BASE : all subclasses will be considered rooted
  • JS_HAZ_ROOTED type subclasses don't get this treatment. Most can't really be subclasses usefully in the first place, and they might add unrooted fields if they were.
• MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS : shared with the clang-based static analyses, indicates that eg HashMap<T,U> is a GC pointer (well, invalidated by GC) iff T or U are GC pointers.

namespace JS {
class JS_HAZ_GC_POINTER Value { ... };

class JS_HAZ_ROOTED Rooted { ... };

class AutoCheckCannotGC : public AutoAssertNoGC {
  ...
} JS_HAZ_GC_INVALIDATED;

class JS_HAZ_ROOTED_BASE AutoRooter { ... }

} /* namespace JS */

class MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS HashMap { ... };

• Resolves virtual method edges to all implementations of that method (based on the static type).
• Assume that we see all relevant source code; no binary extensions allowed.

• Start from the annotations, and trace through inheritance tree.

• The core is a simple reachability analysis in the global callgraph.
• But also handle cases where GC is suppressed within an RAII scope.
  • Function can reach GC but is always called with GC suppressed?
• Nasty case that doesn't matter much: recursive roots
  • A() <–> B(), nothing calls either one, one or the other calls other stuff
• Generic callee any/all properties (any/all paths to F are within the scope where some property holds)
  • TODO: same for caller any/all properties (relative to a root or set of roots)
  • This will be further explained a little later.
• So set canGC to the set of functions that can reach a GC invocation, but are not in all(LIMIT_CANNOT_GC).

Gory details of eliminating suppressed-GC functions from canGC

Consider:

void foo() {
    doSomethingThatMightGC();
}

void indirectGCExceptNot() {
    AutoSuppressGC nogc;
    foo();
}

Assuming no other calls to indirectGCExceptNot(), indirectGCExceptNot is not in canGC because GC is always suppressed when it is called. This is important when locally analyzing a function that calls indirectGCExceptNot with a GC pointer held live, because locally it very much looks like a hazard. (If the suppression is in the same function, then it's easy and it wouldn't matter whether the callee is in canGC or not. But if it's in the caller, local analysis can't see it.)

Iterate over functions and look for unrooted GC pointers held live across a potential GC. Reiterating:

• Unrooted: If a pointer is stored in a Rooted and extracted when needed, then the copy in the Rooted is safe. If a value is extracted, GC happens, and then the value is used again, this is problematic because the extracted value is unrooted.
• GC pointer: it must be a pointer to a GC cell. A pointer to a pointer to a GC cell will not be invalidated. (The pointed-to cell should either be rooted or traced so that it gets updated.)
• held live: an invalidated GC pointer is harmless unless it is used again after the GC.
• live across a potential GC: in static analysis terms, the value is considered to be "live" from the pointer where it was generated to the last time it is used. We are looking for a potential GC within that range.

void foo() {
    doSomethingThatMightGC();
}

void indirectGCExceptNot() {
    AutoSuppressGC nogc;
    foo();
}

void carbon() {
    JSObject* obj = JS::NewObject();
    indirectGCExceptNot();
    use(obj);
}

void main() {
    bar();
    foo();
}

Can foo() GC? Yes, but only in the call from main(). So it will be in canGC. indirectGCExceptNot will not be in the set.

When analyzing carbon(), obj is live across indirectGCExceptNot(), which is fine because it is not in canGC.

Now consider:

void obvious_hazard() {
    JSObject* obj = JS::NewObject();
    doSomethingThatMightGC();
}

void bar2() {
    AutoSuppressGC nogc;
    obvious_hazard();
}

Assume there are no other calls to obvious_hazard() in the program. Should this report a hazard? No! The whole point of AutoSuppressGC is to be able to do stuff without worrying about a GC happening and messing everything up. If there aren't hazards within its scope, either directly or in called functions, then why is AutoSuppressGC there in the first place?

From the analysis's point of view, any(LIMIT_CANNOT_GC) contains both foo and obvious_hazard, while all(LIMIT_CANNOT_GC) contains only obvious_hazard. (any(LIMIT_CANNOT_GC) is never used; it's a currently useless byproduct. Though it ought to be used to suppress warnings of excessive rooting.)

The full set of functions that can GC is all functions that can reach a GC invocation through the callee graph, but are not in the all(LIMIT_CANNOT_GC) set. This is the canGC set.

Note that when analyzing bar2, we don't need to consider all(LIMIT_CANNOT_GC) or canGC at all – even if obvious_hazard were in canGC, we only call it within AutoSuppressGC so it wouldn't produce a hazard anyway. all(LIMIT_CANNOT_GC) is for the benefit of the local analysis of called functions, not callers, a fact that I repeatedly forget.

• Look at a single function (processBodies())
• Loop over all variables in the function (parameters, locals, this, return value)
  • If the variable is unrooted, look at every edge in every body (variableLiveAcrossGC())
    • if the edge is just clobbering a previous value, ignore the edge
    • if the edge uses the variable's value, look for a GC before the use (findGCBeforeValueUse())

findGCBeforeValueUse(start_point):

• start a backwards DFS through the body, starting at start_point
• record whether or not a GC was seen yet at every point in the traversal
  • or rather, a function in canGC
• if an edge "kills" the variable's value (in reverse search order, so it's really generating the value that is live across the GC), stop the search
  • examples:
    • obj = foo()
    • obj = aObj
    • MyClass c(...)
  • this is the beginning of the variable's live range
  • report the hazard if we've found a GC by now
• if an edge uses the variable's value, same as above but don't terminate the search if a GC hasn't been found
  • dump traversal of the sixigll ~Exp~ression datatype to find references to the variable
  • as a usability hack, don't terminate the search even if a GC has been found; continue backwards until a "better" use is encountered.
    • obj = foo(); use1(obj); GC(); use2(obj);
• funky special case: some edges can "invalidate" a variable, which means "whoops you thought it was live but it really wasn't"
  • examples:
    • UniquePtr.reset()
    • obj = nullptr
    • foo(std::move(obj))
• if a loop is encountered, propagate into it (to the exit point of the loop)
• if we revisit a point, terminate the search if the earlier visitor in the backwards scan already found a GC call by this point
• when processing a loop body and its entry point is reached, propagate to the predecessors in the "caller"
• also propagate to the end of this loop (for the previous iteratiom)

I'm honestly not sure why the scan goes backwards.

The ability to compute any/all sets for arbitrary properties is potentially very useful. Here are some possibilities: