[gjs: 10/11] heapgraph: Add an argument to print out unreachable nodes

[Philip Chimento <pchimento src gnome org>]

commit 8639bf43f3e3097386181912304eaf20a9353f20
Author: Philip Chimento <philip chimento gmail com>
Date:   Sat Aug 10 21:46:55 2019 -0700

    heapgraph: Add an argument to print out unreachable nodes
    
    In any given heap dump there seem to be a bunch of nodes that are
    printed out as a result of visiting arenas, that are not reachable from
    any root. For these nodes the breadth-first search returns no path.
    
    It's a bit confusing to see, for example, that 25 nodes of type
    GObject_Object were found in the heap dump but only 8 are printed out.
    The others are unreachable. This adds a --show-unreachable (-u) switch
    that prints out the unreachable ones at the end of the tree. In the case
    of dot output, it prints them with a dotted border.
    
    I think mostly this switch is not going to be very useful, but it
    happens to be useful for me right now because I'm augmenting the graphs
    with GObject reference information from C.

 tools/heapdot.py   |  11 ++++++
 tools/heapgraph.py | 100 +++++++++++++++++++++++++++++++++--------------------
 2 files changed, 74 insertions(+), 37 deletions(-)
---
diff --git a/tools/heapdot.py b/tools/heapdot.py
index 660e2401..3d6d9f77 100644
--- a/tools/heapdot.py
+++ b/tools/heapdot.py
@@ -18,18 +18,24 @@ priv_regex = re.compile(r'([^ ]+) (\(nil\)|0x[a-fA-F0-9]+$)')
 ###############################################################################
 
 dot_graph_paths = []
+unreachable = set()
 
 
 def add_dot_graph_path(path):
     dot_graph_paths.append(path)
 
 
+def add_dot_graph_unreachable(node):
+    unreachable.add(node)
+
+
 def output_dot_file(args, graph, targs, fname):
     # build the set of nodes
     nodes = set([])
     for p in dot_graph_paths:
         for x in p:
             nodes.add(x)
+    nodes.update(unreachable)
 
     # build the edge map
     edges = {}
@@ -127,6 +133,11 @@ def output_dot_file(args, graph, targs, fname):
             style = 'bold'
 
         node_label = label
+
+        if addr in unreachable:
+            style += ',dotted'
+            node_label = 'Unreachable\\n' + node_label
+
         if not args.no_addr:
             node_label += '\\njsobj@' + addr
             if priv:
diff --git a/tools/heapgraph.py b/tools/heapgraph.py
index b7c20d7b..820806a9 100755
--- a/tools/heapgraph.py
+++ b/tools/heapgraph.py
@@ -15,8 +15,8 @@ import re
 import sys
 
 try:
-    from heapdot import output_dot_file
-    from heapdot import add_dot_graph_path
+    from heapdot import (output_dot_file, add_dot_graph_path,
+                         add_dot_graph_unreachable)
 except ImportError:
     sys.stderr.write('DOT graph output not available\n')
 
@@ -75,6 +75,9 @@ filt_opts.add_argument('--no-gray-roots', '-ng', dest='no_gray_roots',
                        action='store_true', default=False,
                        help='Don\'t show gray roots (marked to be collected)')
 
+filt_opts.add_argument('--show-unreachable', '-u', action='store_true',
+                       help="Show objects that have no path to a root but are not collected yet")
+
 filt_opts.add_argument('--no-weak-maps', '-nwm', dest='no_weak_maps',
                        action='store_true', default=False,
                        help='Don\'t show WeakMaps')
@@ -312,6 +315,7 @@ def load_graph(fname):
 ###############################################################################
 
 tree_graph_paths = {}
+tree_graph_unreachables = set()
 
 
 class style:
@@ -370,20 +374,51 @@ def get_node_annotation(graph, addr):
     return graph.annotations.get(addr, None)
 
 
+def format_node(graph, addr, parent=''):
+    node = get_node_label(graph, addr)
+    annotation = get_node_annotation(graph, addr)
+    has_priv = priv_regex.match(node)
+
+    # Color/Style
+    if os.isatty(1):
+        orig = style.UNDERLINE + 'jsobj@' + addr + style.END
+
+        if has_priv:
+            node = style.BOLD + has_priv.group(1) + style.END
+            orig += ' ' + style.UNDERLINE + 'priv@' + has_priv.group(2) + style.END
+        else:
+            node = style.BOLD + node + style.END
+    else:
+        orig = 'jsobj@' + addr
+
+        if has_priv:
+            node = has_priv.group(1)
+            orig += ' priv@' + has_priv.group(2)
+
+    # Add the annotation
+    if annotation:
+        if os.isatty(1):
+            node += ' "' + style.PURPLE + annotation + style.END + '"'
+        else:
+            node += ' "' + annotation + '"'
+
+    if args.no_addr:
+        return node
+    return node + ' ' + orig
+
+
 def output_tree_graph(graph, data, base='', parent=''):
     while data:
         addr, children = data.popitem()
 
+        node = format_node(graph, addr, base)
+
         # Labels
         if parent:
             edge = get_edge_label(graph, parent, addr)
         else:
             edge = graph.root_labels[addr]
 
-        node = get_node_label(graph, addr)
-        annotation = get_node_annotation(graph, addr)
-        has_priv = priv_regex.match(node)
-
         # Color/Style
         if os.isatty(1):
             if parent:
@@ -391,39 +426,11 @@ def output_tree_graph(graph, data, base='', parent=''):
             else:
                 edge = style.BOLD + edge + style.END
 
-            orig = style.UNDERLINE + 'jsobj@' + addr + style.END
-
-            if has_priv:
-                node = style.BOLD + has_priv.group(1) + style.END
-                orig += ' ' + style.UNDERLINE + 'priv@' + has_priv.group(2) + style.END
-            else:
-                node = style.BOLD + node + style.END
-        else:
-            orig = 'jsobj@' + addr
-
-            if has_priv:
-                node = has_priv.group(1)
-                orig += ' priv@' + has_priv.group(2)
-
-        # Add the annotation
-        if annotation:
-            if os.isatty(1):
-                node += ' "' + style.PURPLE + annotation + style.END + '"'
-            else:
-                node += ' "' + annotation + '"'
-
-
         # Print the path segment
-        if args.no_addr:
-            if data:
-                print('{0}├─[{1}]─➤ [{2}]'.format(base, edge, node))
-            else:
-                print('{0}╰─[{1}]─➤ [{2}]'.format(base, edge, node))
+        if data:
+            print('{0}├─[{1}]─➤ [{2}]'.format(base, edge, node))
         else:
-            if data:
-                print('{0}├─[{1}]─➤ [{2} {3}]'.format(base, edge, node, orig))
-            else:
-                print('{0}╰─[{1}]─➤ [{2} {3}]'.format(base, edge, node, orig))
+            print('{0}╰─[{1}]─➤ [{2}]'.format(base, edge, node))
 
         # Print child segments
         if children:
@@ -438,6 +445,13 @@ def output_tree_graph(graph, data, base='', parent=''):
                 print(base + '  ')
 
 
+def output_tree_unreachables(graph, data):
+    while data:
+        addr = data.pop()
+        node = format_node(graph, addr)
+        print(' • Unreachable: [{}]'.format(node))
+
+
 def add_tree_graph_path(owner, path):
     o = owner.setdefault(path.pop(0), {})
     if path:
@@ -451,6 +465,13 @@ def add_path(args, graph, path):
         add_tree_graph_path(tree_graph_paths, path)
 
 
+def add_unreachable(args, node):
+    if args.dot_graph:
+        add_dot_graph_unreachable(node)
+    else:
+        tree_graph_unreachables.add(node)
+
+
 ###############################################################################
 # Breadth-first shortest path finding.
 ###############################################################################
@@ -544,6 +565,10 @@ def find_roots_bfs(args, edges, graph, target):
             path.pop()
             path.reverse()
             add_path(args, graph, path)
+        elif args.show_unreachable:
+            # No path to a root. This object is eligible for collection on the
+            # next GC, but is still in an arena.
+            add_unreachable(args, target)
 
 
 ########################################################
@@ -685,4 +710,5 @@ if __name__ == "__main__":
         output_dot_file(args, graph, targets, args.heap_file + ".dot")
     else:
         output_tree_graph(graph, tree_graph_paths)
+        output_tree_unreachables(graph, tree_graph_unreachables)