python/callgraph-dot.py

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