python/callgraph-dot.py

   1 # callgraph json to graphviz generator for FRR
   2 #
   3 # Copyright (C) 2020  David Lamparter for NetDEF, Inc.
   4 #
   5 # This program is free software; you can redistribute it and/or modify it
   6 # under the terms of the GNU General Public License as published by the Free
   7 # Software Foundation; either version 2 of the License, or (at your option)
   8 # any later version.
   9 #
  10 # This program is distributed in the hope that it will be useful, but WITHOUT
  11 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12 # FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  13 # more details.
  14 #
  15 # You should have received a copy of the GNU General Public License along
  16 # with this program; see the file COPYING; if not, write to the Free Software
  17 # Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18
  19 import re
  20 import sys
  21 import json
  22
  23
  24 class FunctionNode(object):
  25     funcs = {}
  26
  27     def __init__(self, name):
  28         super().__init__()
  29         FunctionNode.funcs[name] = self
  30
  31         self.name = name
  32         self.out = []
  33         self.inb = []
  34         self.rank = None
  35         self.defined = False
  36         self.defs = []
  37
  38     def __repr__(self):
  39         return '<"%s()" rank=%r>' % (self.name, self.rank)
  40
  41     def define(self, attrs):
  42         self.defined = True
  43         self.defs.append((attrs["filename"], attrs["line"]))
  44         return self
  45
  46     def add_call(self, called, attrs):
  47         return CallEdge(self, called, attrs)
  48
  49     def calls(self):
  50         for e in self.out:
  51             yield e.o
  52
  53     def calld(self):
  54         for e in self.inb:
  55             yield e.i
  56
  57     def unlink(self, other):
  58         self.out = list([edge for edge in self.out if edge.o != other])
  59         other.inb = list([edge for edge in other.inb if edge.i != other])
  60
  61     @classmethod
  62     def get(cls, name):
  63         if name in cls.funcs:
  64             return cls.funcs[name]
  65         return FunctionNode(name)
  66
  67
  68 class CallEdge(object):
  69     def __init__(self, i, o, attrs):
  70         self.i = i
  71         self.o = o
  72         self.is_external = attrs["is_external"]
  73         self.attrs = attrs
  74
  75         i.out.append(self)
  76         o.inb.append(self)
  77
  78     def __repr__(self):
  79         return '<"%s()" -> "%s()">' % (self.i.name, self.o.name)
  80
  81
  82 def nameclean(n):
  83     if "." in n:
  84         return n.split(".", 1)[0]
  85     return n
  86
  87
  88 def calc_rank(queue, direction):
  89     nextq = queue
  90
  91     if direction == 1:
  92         aggr = max
  93         elem = lambda x: x.calls()
  94     else:
  95         aggr = min
  96         elem = lambda x: x.calld()
  97
  98     currank = direction
  99     cont = True
 100
 101     while len(nextq) > 0 and cont:
 102         queue = nextq
 103         nextq = []
 104
 105         # sys.stderr.write('rank %d\n' % currank)
 106
 107         cont = False
 108
 109         for node in queue:
 110             if not node.defined:
 111                 node.rank = 0
 112                 continue
 113
 114             rank = direction
 115             for other in elem(node):
 116                 if other is node:
 117                     continue
 118                 if other.rank is None:
 119                     nextq.append(node)
 120                     break
 121                 rank = aggr(rank, other.rank + direction)
 122             else:
 123                 cont = True
 124                 node.rank = rank
 125
 126         currank += direction
 127
 128     return nextq
 129
 130
 131 class Graph(dict):
 132     class Subgraph(set):
 133         def __init__(self):
 134             super().__init__()
 135
 136     class NodeGroup(set):
 137         def __init__(self, members):
 138             super().__init__(members)
 139
 140     class Node(object):
 141         def __init__(self, graph, fn):
 142             super().__init__()
 143             self._fn = fn
 144             self._fns = [fn]
 145             self._graph = graph
 146             self._calls = set()
 147             self._calld = set()
 148             self._group = None
 149
 150         def __repr__(self):
 151             return '<Graph.Node "%s()"/%d>' % (self._fn.name, len(self._fns))
 152
 153         def __hash__(self):
 154             return hash(self._fn.name)
 155
 156         def _finalize(self):
 157             for called in self._fn.calls():
 158                 if called.name == self._fn.name:
 159                     continue
 160                 if called.name in self._graph:
 161                     self._calls.add(self._graph[called.name])
 162                     self._graph[called.name]._calld.add(self)
 163
 164         def unlink(self, other):
 165             self._calls.remove(other)
 166             other._calld.remove(self)
 167
 168         @property
 169         def name(self):
 170             return self._fn.name
 171
 172         def calls(self):
 173             return self._calls
 174
 175         def calld(self):
 176             return self._calld
 177
 178         def group(self, members):
 179             assert self in members
 180
 181             pregroups = []
 182             for g in [m._group for m in members]:
 183                 if g is None:
 184                     continue
 185                 if g in pregroups:
 186                     continue
 187
 188                 assert g <= members
 189                 pregroups.append(g)
 190
 191             if len(pregroups) == 0:
 192                 group = self._graph.NodeGroup(members)
 193                 self._graph._groups.append(group)
 194             elif len(pregroups) == 1:
 195                 group = pregroups[0]
 196                 group |= members
 197             else:
 198                 for g in pregroups:
 199                     self._graph._groups.remove(g)
 200                 group = self._graph.NodeGroup(members)
 201                 self._graph._groups.append(group)
 202
 203             for m in members:
 204                 m._group = group
 205             return group
 206
 207         def merge(self, other):
 208             self._fns.extend(other._fns)
 209             self._calls = (self._calls | other._calls) - {self, other}
 210             self._calld = (self._calld | other._calld) - {self, other}
 211             for c in other._calls:
 212                 if c == self:
 213                     continue
 214                 c._calld.remove(other)
 215                 c._calld.add(self)
 216             for c in other._calld:
 217                 if c == self:
 218                     continue
 219                 c._calls.remove(other)
 220                 c._calls.add(self)
 221             del self._graph[other._fn.name]
 222
 223     def __init__(self, funcs):
 224         super().__init__()
 225         self._funcs = funcs
 226         for fn in funcs:
 227             self[fn.name] = self.Node(self, fn)
 228         for node in self.values():
 229             node._finalize()
 230         self._groups = []
 231
 232     def automerge(self):
 233         nodes = list(self.values())
 234
 235         while len(nodes):
 236             node = nodes.pop(0)
 237
 238             candidates = {node}
 239             evalset = set(node.calls())
 240             prevevalset = None
 241
 242             while prevevalset != evalset:
 243                 prevevalset = evalset
 244                 evalset = set()
 245
 246                 for evnode in prevevalset:
 247                     inbound = set(evnode.calld())
 248                     if inbound <= candidates:
 249                         candidates.add(evnode)
 250                         evalset |= set(evnode.calls()) - candidates
 251                     else:
 252                         evalset.add(evnode)
 253
 254             # if len(candidates) > 1:
 255             #    for candidate in candidates:
 256             #        if candidate != node:
 257             #            #node.merge(candidate)
 258             #            if candidate in nodes:
 259             #                nodes.remove(candidate)
 260             node.group(candidates)
 261
 262             for candidate in candidates:
 263                 if candidate in nodes:
 264                     nodes.remove(candidate)
 265
 266     def calc_subgraphs(self):
 267         nodes = list(self.values())
 268         self._subgraphs = []
 269         up = {}
 270         down = {}
 271
 272         self._linear_nodes = []
 273
 274         while len(nodes):
 275             sys.stderr.write("%d\n" % len(nodes))
 276             node = nodes.pop(0)
 277
 278             down[node] = set()
 279             queue = [node]
 280             while len(queue):
 281                 now = queue.pop()
 282                 down[node].add(now)
 283                 for calls in now.calls():
 284                     if calls in down[node]:
 285                         continue
 286                     queue.append(calls)
 287
 288             up[node] = set()
 289             queue = [node]
 290             while len(queue):
 291                 now = queue.pop()
 292                 up[node].add(now)
 293                 for calld in now.calld():
 294                     if calld in up[node]:
 295                         continue
 296                     queue.append(calld)
 297
 298             common = up[node] & down[node]
 299
 300             if len(common) == 1:
 301                 self._linear_nodes.append(node)
 302             else:
 303                 sg = self.Subgraph()
 304                 sg |= common
 305                 self._subgraphs.append(sg)
 306                 for n in common:
 307                     if n != node:
 308                         nodes.remove(n)
 309
 310         return self._subgraphs, self._linear_nodes
 311
 312
 313 with open(sys.argv[1], "r") as fd:
 314     data = json.load(fd)
 315
 316 extra_info = {
 317     # zebra - LSP WQ
 318     ("lsp_processq_add", "work_queue_add"): [
 319         "lsp_process",
 320         "lsp_processq_del",
 321         "lsp_processq_complete",
 322     ],
 323     # zebra - main WQ
 324     ("mq_add_handler", "work_queue_add"): [
 325         "meta_queue_process",
 326     ],
 327     ("meta_queue_process", "work_queue_add"): [
 328         "meta_queue_process",
 329     ],
 330     # bgpd - label pool WQ
 331     ("bgp_lp_get", "work_queue_add"): [
 332         "lp_cbq_docallback",
 333     ],
 334     ("bgp_lp_event_chunk", "work_queue_add"): [
 335         "lp_cbq_docallback",
 336     ],
 337     ("bgp_lp_event_zebra_up", "work_queue_add"): [
 338         "lp_cbq_docallback",
 339     ],
 340     # bgpd - main WQ
 341     ("bgp_process", "work_queue_add"): [
 342         "bgp_process_wq",
 343         "bgp_processq_del",
 344     ],
 345     ("bgp_add_eoiu_mark", "work_queue_add"): [
 346         "bgp_process_wq",
 347         "bgp_processq_del",
 348     ],
 349     # clear node WQ
 350     ("bgp_clear_route_table", "work_queue_add"): [
 351         "bgp_clear_route_node",
 352         "bgp_clear_node_queue_del",
 353         "bgp_clear_node_complete",
 354     ],
 355     # rfapi WQs
 356     ("rfapi_close", "work_queue_add"): [
 357         "rfapi_deferred_close_workfunc",
 358     ],
 359     ("rfapiRibUpdatePendingNode", "work_queue_add"): [
 360         "rfapiRibDoQueuedCallback",
 361         "rfapiRibQueueItemDelete",
 362     ],
 363 }
 364
 365
 366 for func, fdata in data["functions"].items():
 367     func = nameclean(func)
 368     fnode = FunctionNode.get(func).define(fdata)
 369
 370     for call in fdata["calls"]:
 371         if call.get("type") in [None, "unnamed", "thread_sched"]:
 372             if call.get("target") is None:
 373                 continue
 374             tgt = nameclean(call["target"])
 375             fnode.add_call(FunctionNode.get(tgt), call)
 376             for fptr in call.get("funcptrs", []):
 377                 fnode.add_call(FunctionNode.get(nameclean(fptr)), call)
 378             if tgt == "work_queue_add":
 379                 if (func, tgt) not in extra_info:
 380                     sys.stderr.write(
 381                         "%s:%d:%s(): work_queue_add() not handled\n"
 382                         % (call["filename"], call["line"], func)
 383                     )
 384                 else:
 385                     attrs = dict(call)
 386                     attrs.update({"is_external": False, "type": "workqueue"})
 387                     for dst in extra_info[func, tgt]:
 388                         fnode.add_call(FunctionNode.get(dst), call)
 389         elif call["type"] == "install_element":
 390             vty_node = FunctionNode.get("VTY_NODE_%d" % call["vty_node"])
 391             vty_node.add_call(FunctionNode.get(nameclean(call["target"])), call)
 392         elif call["type"] == "hook":
 393             # TODO: edges for hooks from data['hooks']
 394             pass
 395
 396 n = FunctionNode.funcs
 397
 398 # fix some very low end functions cycling back very far to the top
 399 if "peer_free" in n:
 400     n["peer_free"].unlink(n["bgp_timer_set"])
 401     n["peer_free"].unlink(n["bgp_addpath_set_peer_type"])
 402 if "bgp_path_info_extra_free" in n:
 403     n["bgp_path_info_extra_free"].rank = 0
 404
 405 if "zlog_ref" in n:
 406     n["zlog_ref"].rank = 0
 407 if "mt_checkalloc" in n:
 408     n["mt_checkalloc"].rank = 0
 409
 410 queue = list(FunctionNode.funcs.values())
 411 queue = calc_rank(queue, 1)
 412 queue = calc_rank(queue, -1)
 413
 414 sys.stderr.write("%d functions in cyclic set\n" % len(queue))
 415
 416 graph = Graph(queue)
 417 graph.automerge()
 418
 419 gv_nodes = []
 420 gv_edges = []
 421
 422 sys.stderr.write("%d groups after automerge\n" % len(graph._groups))
 423
 424
 425 def is_vnc(n):
 426     return n.startswith("rfapi") or n.startswith("vnc") or ("_vnc_" in n)
 427
 428
 429 _vncstyle = ',fillcolor="#ffffcc",style=filled'
 430 cyclic_set_names = set([fn.name for fn in graph.values()])
 431
 432 for i, group in enumerate(graph._groups):
 433     if len(group) > 1:
 434         group.num = i
 435         gv_nodes.append("\tsubgraph cluster_%d {" % i)
 436         gv_nodes.append("\t\tcolor=blue;")
 437         for gn in group:
 438             has_cycle_callers = set(gn.calld()) - group
 439             has_ext_callers = (
 440                 set([edge.i.name for edge in gn._fn.inb]) - cyclic_set_names
 441             )
 442
 443             style = ""
 444             etext = ""
 445             if is_vnc(gn.name):
 446                 style += _vncstyle
 447             if has_cycle_callers:
 448                 style += ",color=blue,penwidth=3"
 449             if has_ext_callers:
 450                 style += ',fillcolor="#ffeebb",style=filled'
 451                 etext += '<br/><font point-size="10">(%d other callers)</font>' % (
 452                     len(has_ext_callers)
 453                 )
 454
 455             gv_nodes.append(
 456                 '\t\t"%s" [shape=box,label=<%s%s>%s];'
 457                 % (gn.name, "<br/>".join([fn.name for fn in gn._fns]), etext, style)
 458             )
 459         gv_nodes.append("\t}")
 460     else:
 461         for gn in group:
 462             has_ext_callers = (
 463                 set([edge.i.name for edge in gn._fn.inb]) - cyclic_set_names
 464             )
 465
 466             style = ""
 467             etext = ""
 468             if is_vnc(gn.name):
 469                 style += _vncstyle
 470             if has_ext_callers:
 471                 style += ',fillcolor="#ffeebb",style=filled'
 472                 etext += '<br/><font point-size="10">(%d other callers)</font>' % (
 473                     len(has_ext_callers)
 474                 )
 475             gv_nodes.append(
 476                 '\t"%s" [shape=box,label=<%s%s>%s];'
 477                 % (gn.name, "<br/>".join([fn.name for fn in gn._fns]), etext, style)
 478             )
 479
 480 edges = set()
 481 for gn in graph.values():
 482     for calls in gn.calls():
 483         if gn._group == calls._group:
 484             gv_edges.append(
 485                 '\t"%s" -> "%s" [color="#55aa55",style=dashed];' % (gn.name, calls.name)
 486             )
 487         else:
 488
 489             def xname(nn):
 490                 if len(nn._group) > 1:
 491                     return "cluster_%d" % nn._group.num
 492                 else:
 493                     return nn.name
 494
 495             tup = xname(gn), calls.name
 496             if tup[0] != tup[1] and tup not in edges:
 497                 gv_edges.append('\t"%s" -> "%s" [weight=0.0,w=0.0,color=blue];' % tup)
 498                 edges.add(tup)
 499
 500 with open(sys.argv[2], "w") as fd:
 501     fd.write(
 502         """digraph {
 503     node [fontsize=13,fontname="Fira Sans"];
 504 %s
 505 }"""
 506         % "\n".join(gv_nodes + [""] + gv_edges)
 507     )