src/tools/clang/blink_gc_plugin/process-graph.py

   1 #!/usr/bin/env python
   2 # Copyright 2014 The Chromium Authors. All rights reserved.
   3 # Use of this source code is governed by a BSD-style license that can be
   4 # found in the LICENSE file.
   5
   6 import argparse, os, sys, json, subprocess, pickle, StringIO
   7
   8 parser = argparse.ArgumentParser(
   9   description =
  10     "Process the Blink points-to graph generated by the Blink GC plugin.")
  11
  12 parser.add_argument(
  13   '-', dest='use_stdin', action='store_true',
  14   help='Read JSON graph files from stdin')
  15
  16 parser.add_argument(
  17   '-v', '--verbose', action='store_true',
  18   help='Verbose output')
  19
  20 parser.add_argument(
  21   '-c', '--detect-cycles', action='store_true', default=True,
  22   help='Detect cycles containing GC roots')
  23
  24 parser.add_argument(
  25   '-i', '--ignored-cycles', default=None,
  26   help='File with cycles to ignore')
  27
  28 parser.add_argument(
  29   '-p', '--pickle-graph', default=None,
  30   help='File to read/save the graph from/to')
  31
  32 parser.add_argument(
  33   'files', metavar='FILE', nargs='*', default=[],
  34   help='JSON graph files or directories containing them')
  35
  36 # Command line args after parsing.
  37 args = None
  38
  39 # Map from node labels to nodes.
  40 graph = {}
  41
  42 # Set of root nodes.
  43 roots = []
  44
  45 # List of cycles to ignore.
  46 ignored_cycles = []
  47
  48 # Global flag to determine exit code.
  49 global_reported_error = False
  50
  51 def set_reported_error(value):
  52   global global_reported_error
  53   global_reported_error = value
  54
  55 def reported_error():
  56   return global_reported_error
  57
  58 def log(msg):
  59   if args.verbose:
  60     print msg
  61
  62 global_inc_copy = 0
  63 def inc_copy():
  64   global global_inc_copy
  65   global_inc_copy += 1
  66
  67 def get_node(name):
  68   return graph.setdefault(name, Node(name))
  69
  70 # Representation of graph nodes. Basically a map of directed edges.
  71 class Node:
  72   def __init__(self, name):
  73     self.name = name
  74     self.edges = {}
  75     self.reset()
  76   def __repr__(self):
  77     return "%s(%s) %s" % (self.name, self.visited, self.edges)
  78   def update_node(self, decl):
  79     # Currently we don't track any node info besides its edges.
  80     pass
  81   def update_edge(self, e):
  82     new_edge = Edge(**e)
  83     edge = self.edges.get(new_edge.key)
  84     if edge:
  85       # If an edge exist, its kind is the strongest of the two.
  86       edge.kind = max(edge.kind, new_edge.kind)
  87     else:
  88       self.edges[new_edge.key] = new_edge
  89   def super_edges(self):
  90     return [ e for e in self.edges.itervalues() if e.is_super() ]
  91   def reset(self):
  92     self.cost = sys.maxint
  93     self.visited = False
  94     self.path = None
  95
  96 # Representation of directed graph edges.
  97 class Edge:
  98   def __init__(self, **decl):
  99     self.src = decl['src']
 100     self.dst = decl['dst']
 101     self.lbl = decl['lbl']
 102     self.kind = decl['kind'] # 0 = weak, 1 = strong, 2 = root
 103     self.loc = decl['loc']
 104     # The label does not uniquely determine an edge from a node. We
 105     # define the semi-unique key to be the concatenation of the
 106     # label and dst name. This is sufficient to track the strongest
 107     # edge to a particular type. For example, if the field A::m_f
 108     # has type HashMap<WeakMember<B>, Member<B>> we will have a
 109     # strong edge with key m_f#B from A to B.
 110     self.key = '%s#%s' % (self.lbl, self.dst)
 111   def copy(self):
 112     return Edge(
 113       lbl = self.lbl,
 114       kind = self.kind,
 115       src = self.src,
 116       dst = self.dst,
 117       loc = self.loc)
 118   def __repr__(self):
 119     return '%s (%s) => %s' % (self.src, self.lbl, self.dst)
 120   def is_root(self):
 121     return self.kind == 2
 122   def is_weak(self):
 123     return self.kind == 0
 124   def keeps_alive(self):
 125     return self.kind > 0
 126   def is_subclass(self):
 127     return self.lbl.startswith('<subclass>')
 128   def is_super(self):
 129     return self.lbl.startswith('<super>')
 130
 131 def parse_file(filename):
 132   obj = json.load(open(filename))
 133   return obj
 134
 135 def build_graphs_in_dir(dirname):
 136   # TODO: Use plateform independent code, eg, os.walk
 137   files = subprocess.check_output(
 138     ['find', dirname, '-name', '*.graph.json']).split('\n')
 139   log("Found %d files" % len(files))
 140   for f in files:
 141     f.strip()
 142     if len(f) < 1:
 143       continue
 144     build_graph(f)
 145
 146 def build_graph(filename):
 147   for decl in parse_file(filename):
 148     if decl.has_key('name'):
 149       # Add/update a node entry
 150       name = decl['name']
 151       node = get_node(name)
 152       node.update_node(decl)
 153     else:
 154       # Add/update an edge entry
 155       name = decl['src']
 156       node = get_node(name)
 157       node.update_edge(decl)
 158
 159 # Copy all non-weak edges from super classes to their subclasses.
 160 # This causes all fields of a super to be considered fields of a
 161 # derived class without tranitively relating derived classes with
 162 # each other. For example, if B <: A, C <: A, and for some D, D => B,
 163 # we don't want that to entail that D => C.
 164 def copy_super_edges(edge):
 165   if edge.is_weak() or not edge.is_super():
 166     return
 167   inc_copy()
 168   # Make the super-class edge weak (prohibits processing twice).
 169   edge.kind = 0
 170   # If the super class is not in our graph exit early.
 171   super_node = graph.get(edge.dst)
 172   if super_node is None: return
 173   # Recursively copy all super-class edges.
 174   for e in super_node.super_edges():
 175     copy_super_edges(e)
 176   # Copy strong super-class edges (ignoring sub-class edges) to the sub class.
 177   sub_node = graph[edge.src]
 178   for e in super_node.edges.itervalues():
 179     if e.keeps_alive() and not e.is_subclass():
 180       new_edge = e.copy()
 181       new_edge.src = sub_node.name
 182       new_edge.lbl = '%s <: %s' % (super_node.name, e.lbl)
 183       sub_node.edges[new_edge.key] = new_edge
 184   # Add a strong sub-class edge.
 185   sub_edge = edge.copy()
 186   sub_edge.kind = 1
 187   sub_edge.lbl = '<subclass>'
 188   sub_edge.src = super_node.name
 189   sub_edge.dst = sub_node.name
 190   super_node.edges[sub_edge.key] = sub_edge
 191
 192 def complete_graph():
 193   for node in graph.itervalues():
 194     for edge in node.super_edges():
 195       copy_super_edges(edge)
 196     for edge in node.edges.itervalues():
 197       if edge.is_root():
 198         roots.append(edge)
 199   log("Copied edges down <super> edges for %d graph nodes" % global_inc_copy)
 200
 201 def reset_graph():
 202   for n in graph.itervalues():
 203     n.reset()
 204
 205 def shortest_path(start, end):
 206   start.cost = 0
 207   minlist = [start]
 208   while len(minlist) > 0:
 209     minlist.sort(key=lambda n: -n.cost)
 210     current = minlist.pop()
 211     current.visited = True
 212     if current == end or current.cost >= end.cost + 1:
 213       return
 214     for e in current.edges.itervalues():
 215       if not e.keeps_alive():
 216         continue
 217       dst = graph.get(e.dst)
 218       if dst is None or dst.visited:
 219         continue
 220       if current.cost < dst.cost:
 221         dst.cost = current.cost + 1
 222         dst.path = e
 223       minlist.append(dst)
 224
 225 def detect_cycles():
 226   for root_edge in roots:
 227     reset_graph()
 228     src = graph[root_edge.src]
 229     dst = graph.get(root_edge.dst)
 230     if root_edge.dst == "WTF::String":
 231       continue
 232     if dst is None:
 233       print "\nPersistent root to incomplete destination object:"
 234       print root_edge
 235       set_reported_error(True)
 236       continue
 237     # Find the shortest path from the root target (dst) to its host (src)
 238     shortest_path(dst, src)
 239     if src.cost < sys.maxint:
 240       report_cycle(root_edge)
 241
 242 def is_ignored_cycle(cycle):
 243   for block in ignored_cycles:
 244     if block_match(cycle, block):
 245       return True
 246
 247 def block_match(b1, b2):
 248   if len(b1) != len(b2):
 249     return False
 250   for (l1, l2) in zip(b1, b2):
 251     if l1 != l2:
 252       return False
 253   return True
 254
 255 def report_cycle(root_edge):
 256   dst = graph[root_edge.dst]
 257   path = []
 258   edge = root_edge
 259   dst.path = None
 260   while edge:
 261     path.append(edge)
 262     edge = graph[edge.src].path
 263   path.append(root_edge)
 264   path.reverse()
 265   # Find the max loc length for pretty printing.
 266   max_loc = 0
 267   for p in path:
 268     if len(p.loc) > max_loc:
 269       max_loc = len(p.loc)
 270   out = StringIO.StringIO()
 271   for p in path[:-1]:
 272     print >>out, (p.loc + ':').ljust(max_loc + 1), p
 273   sout = out.getvalue()
 274   if not is_ignored_cycle(sout):
 275     print "\nFound a potentially leaking cycle starting from a GC root:\n", sout
 276     set_reported_error(True)
 277
 278 def load_graph():
 279   global graph
 280   global roots
 281   log("Reading graph from pickled file: " + args.pickle_graph)
 282   dump = pickle.load(open(args.pickle_graph, 'rb'))
 283   graph = dump[0]
 284   roots = dump[1]
 285
 286 def save_graph():
 287   log("Saving graph to pickle file: " + args.pickle_graph)
 288   dump = (graph, roots)
 289   pickle.dump(dump, open(args.pickle_graph, 'wb'))
 290
 291 def read_ignored_cycles():
 292   global ignored_cycles
 293   if not args.ignored_cycles:
 294     return
 295   log("Reading ignored cycles from file: " + args.ignored_cycles)
 296   block = []
 297   for l in open(args.ignored_cycles):
 298     line = l.strip()
 299     if not line:
 300       if len(block) > 0:
 301         ignored_cycles.append(block)
 302       block = []
 303     else:
 304       block += l
 305   if len(block) > 0:
 306     ignored_cycles.append(block)
 307
 308 def main():
 309   global args
 310   args = parser.parse_args()
 311   if not args.detect_cycles:
 312     print "Please select an operation to perform (eg, -c to detect cycles)"
 313     parser.print_help()
 314     return 1
 315   if args.pickle_graph and os.path.isfile(args.pickle_graph):
 316     load_graph()
 317   else:
 318     if args.use_stdin:
 319       log("Reading files from stdin")
 320       for f in sys.stdin:
 321         build_graph(f.strip())
 322     else:
 323       log("Reading files and directories from command line")
 324       if len(args.files) == 0:
 325         print "Please provide files or directores for building the graph"
 326         parser.print_help()
 327         return 1
 328       for f in args.files:
 329         if os.path.isdir(f):
 330           log("Building graph from files in directory: " + f)
 331           build_graphs_in_dir(f)
 332         else:
 333           log("Building graph from file: " + f)
 334           build_graph(f)
 335     log("Completing graph construction (%d graph nodes)" % len(graph))
 336     complete_graph()
 337     if args.pickle_graph:
 338       save_graph()
 339   if args.detect_cycles:
 340     read_ignored_cycles()
 341     log("Detecting cycles containg GC roots")
 342     detect_cycles()
 343   if reported_error():
 344     return 1
 345   return 0
 346
 347 if __name__ == '__main__':
 348   sys.exit(main())