Global cycle detection analysis.

tools/clang/blink_gc_plugin/process-graph.py

Index: tools/clang/blink_gc_plugin/process-graph.py
diff --git a/tools/clang/blink_gc_plugin/process-graph.py b/tools/clang/blink_gc_plugin/process-graph.py
new file mode 100755
index 0000000000000000000000000000000000000000..9bb5dd8fcb41da0c807fc461d2fb687bf39e19bc
--- /dev/null
+++ b/tools/clang/blink_gc_plugin/process-graph.py
@@ -0,0 +1,283 @@
+#!/usr/bin/env python
+# Copyright 2014 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+import argparse, os, sys, json, subprocess
+
+parser = argparse.ArgumentParser(
+  description =
+    "Process the Blink points-to graph generated by the Blink GC plugin.")
+
+parser.add_argument(
+  '-', dest='use_stdin', action='store_true',
+  help='Read JSON graph files from stdin')
+
+parser.add_argument(
+  '-v', '--verbose', action='store_true',
+  help='Verbose output')
+
+parser.add_argument(
+  '-c', '--detect-cycles', action='store_true', default=True,
+  help='Detect cycles containing GC roots')
+
+parser.add_argument(
+  'files', metavar='FILE', nargs='*', default=[],
+  help='JSON graph files or directories containing them')
+
+# command line args after parsing.

[Mads Ager (chromium), 2014/03/21 11:45:57]

Start comments with a capital letter?

+args = None
+
+# map from node labels to nodes.
+graph = {}
+
+# set of root nodes.
+roots = []
+
+# global flag to determine exit code.
+global_reported_error = False
+
+def set_reported_error(value):
+  global global_reported_error
+  global_reported_error = value
+
+def reported_error():
+  return global_reported_error
+
+def log(msg):
+  if args.verbose:
+    print msg
+
+global_inc_copy = 0
+def inc_copy():
+  global global_inc_copy
+  global_inc_copy += 1
+
+def get_node(name):
+  return graph.setdefault(name, Node(name))
+
+# Representation of graph nodes. Basically a map of directed edges.
+class Node:
+  def __init__(self, name):
+    self.name = name
+    self.edges = {}
+    self.reset()
+  def __repr__(self):
+    return "%s(%s) %s" % (self.name, self.visited, self.edges)
+  def update_node(self, decl):
+    # Currently we don't track any node info besides its edges.
+    pass
+  def update_edge(self, e):
+    new_edge = Edge(**e)
+    edge = self.edges.get(new_edge.key)
+    if edge:
+      # If an edge exist, its kind is the strongest of the two.
+      edge.kind = max(edge.kind, new_edge.kind)
+    else:
+      self.edges[new_edge.key] = new_edge
+  def super_edges(self):
+    return [ e for e in self.edges.itervalues() if e.is_super() ]
+  def reset(self):
+    self.cost = sys.maxint
+    self.visited = False
+    self.path = None
+
+# Representation of directed graph edges.
+class Edge:
+  def __init__(self, **decl):
+    self.src = decl['src']
+    self.dst = decl['dst']
+    self.lbl = decl['lbl']
+    self.kind = decl['kind'] # 0 = weak, 1 = strong, 2 = root
+    self.loc = decl['loc']
+    # The label does not uniquely determine an edge from a node. We
+    # define the semi-unique key to be the concatenation of the
+    # label and dst name. This is sufficient to track the strongest
+    # edge to a particular type. For example, if the field A::m_f
+    # has type HashMap<WeakMember<B>, Member<B>> we will have a one

[Mads Ager (chromium), 2014/03/21 11:45:57]

a one -> a

+    # strong edge with key m_f#B from A to B.
+    self.key = '%s#%s' % (self.lbl, self.dst)
+  def copy(self):
+    return Edge(
+      lbl = self.lbl,
+      kind = self.kind,
+      src = self.src,
+      dst = self.dst,
+      loc = self.loc)
+  def __repr__(self):
+    return '%s (%s) => %s' % (self.src, self.lbl, self.dst)
+  def is_root(self):
+    return self.kind == 2
+  def is_weak(self):
+    return self.kind == 0
+  def keeps_alive(self):
+    return self.kind > 0
+  def is_subclass(self):
+    return self.lbl.startswith('<subclass>')
+  def is_super(self):
+    return self.lbl.startswith('<super>')
+
+def parse_file(filename):
+  obj = json.load(open(filename))
+  return obj
+
+def build_graphs_in_dir(dirname):
+  files = subprocess.check_output(
+    ['find', dirname, '-name', '*.graph.json']).split('\n')

[Mads Ager (chromium), 2014/03/21 11:45:57]

We might want to use python APIs for this at some point to avoid making this
script platform specific. Not important now (maybe add a TODO)?

+  log("Found %d files" % len(files))
+  for f in files:
+    f.strip()
+    if len(f) < 1:
+      continue
+    build_graph(f)
+
+def build_graph(filename):
+  for decl in parse_file(filename):
+    if decl.has_key('name'):
+      # Add/update a node entry
+      name = decl['name']
+      node = get_node(name)
+      node.update_node(decl)
+    else:
+      # Add/update an edge entry
+      name = decl['src']
+      node = get_node(name)
+      node.update_edge(decl)
+
+# Copy all edges from a super classes to their subclasses.
+
+# This causes all fields of a super to be considered fields of a
+# derived class without tranitively relating derived classes with
+# each other. For example, if B <: A, C <: A, and for some D, D => B,
+# we don't want that to entail that D => C.
+def copy_super_edges(edge):
+  if edge.is_weak() or not edge.is_super():
+    return
+  inc_copy()
+  # make the super-class edge weak (prohibits processing twice).
+  edge.kind = 0
+  # if the super class is not in our graph exit early.
+  super_node = graph.get(edge.dst)
+  if super_node is None: return
+  # recursively copy all super-class edges.
+  for e in super_node.super_edges():
+    copy_super_edges(e)
+  # copy strong super-class edges (ignoring sub-class edges) to the sub class.
+  sub_node = graph[edge.src]
+  for e in super_node.edges.itervalues():
+    if e.keeps_alive() and not e.is_subclass():
+      new_edge = e.copy()
+      new_edge.src = sub_node.name
+      new_edge.lbl = '%s <: %s' % (super_node.name, e.lbl)
+      sub_node.edges[new_edge.key] = new_edge
+  # add a strong sub-class edge.
+  sub_edge = edge.copy()
+  sub_edge.kind = 1
+  sub_edge.lbl = '<subclass>'
+  sub_edge.src = super_node.name
+  sub_edge.dst = sub_node.name
+  super_node.edges[sub_edge.key] = sub_edge
+
+def complete_graph():
+  for node in graph.itervalues():
+    for edge in node.super_edges():
+      copy_super_edges(edge)
+    for edge in node.edges.itervalues():
+      if edge.is_root():
+        roots.append(edge)
+  log("Copied edges down <super> edges for %d graph nodes" % global_inc_copy)
+
+def reset_graph():
+  for n in graph.itervalues():
+    n.reset()
+
+def shortest_path(start, end):
+  start.cost = 0
+  minlist = [start]
+  while len(minlist) > 0:
+    minlist.sort(key=lambda n: -n.cost)
+    current = minlist.pop()
+    current.visited = True
+    if current == end or current.cost >= end.cost + 1:
+      return
+    for e in current.edges.itervalues():
+      if not e.keeps_alive():
+        continue
+      dst = graph.get(e.dst)
+      if dst is None or dst.visited:
+        continue
+      if current.cost < dst.cost:
+        dst.cost = current.cost + 1
+        dst.path = e
+      minlist.append(dst)
+
+def detect_cycles():
+  for root_edge in roots:
+    reset_graph()
+    src = graph[root_edge.src]
+    dst = graph.get(root_edge.dst)
+    if dst is None:
+      print "\nPersistent root to incomplete destination object:"
+      print root_edge
+      set_reported_error(True)
+      continue
+    # Find the shortest path from the root target (dst) to its host (src)
+    shortest_path(dst, src)
+    if src.cost < sys.maxint:
+      report_cycle(root_edge)
+
+def report_cycle(root_edge):
+  dst = graph[root_edge.dst]
+  print "\nFound a potentially leaking cycle starting from a GC root:"
+  path = []
+  edge = root_edge
+  dst.path = None
+  while edge:
+    path.append(edge)
+    edge = graph[edge.src].path
+  path.append(root_edge)
+  path.reverse()
+  # Find the max loc length for pretty printing.
+  max_loc = 0
+  for p in path:
+    if len(p.loc) > max_loc:
+      max_loc = len(p.loc)
+  for p in path[:-1]:
+    print (p.loc + ':').ljust(max_loc + 1), p
+  set_reported_error(True)
+
+def main():
+  global args
+  args = parser.parse_args()
+  if not args.detect_cycles:
+    print "Please select an operation to perform (eg, -c to detect cycles)"
+    parser.print_help()
+    return 1
+  if args.use_stdin:
+    log("Reading files from stdin")
+    for f in sys.stdin:
+      build_graph(f.strip())
+  else:
+    log("Reading files and directories from command line")
+    if len(args.files) == 0:
+      print "Please provide files or directores for building the graph"
+      parser.print_help()
+      return 1
+    for f in args.files:
+      if os.path.isdir(f):
+        log("Building graph from files in directory: " + f)
+        build_graphs_in_dir(f)
+      else:
+        log("Building graph from file: " + f)
+        build_graph(f)
+  log("Completing graph construction (%d graph nodes)" % len(graph))
+  complete_graph()
+  if args.detect_cycles:
+    log("Detecting cycles containg GC roots")
+    detect_cycles()
+  if reported_error():
+    return 1
+  return 0
+
+if __name__ == '__main__':
+  sys.exit(main())