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"): ["meta_queue_process",],
 325     ("meta_queue_process", "work_queue_add"): ["meta_queue_process",],
 326     # bgpd - label pool WQ
 327     ("bgp_lp_get", "work_queue_add"): ["lp_cbq_docallback",],
 328     ("bgp_lp_event_chunk", "work_queue_add"): ["lp_cbq_docallback",],
 329     ("bgp_lp_event_zebra_up", "work_queue_add"): ["lp_cbq_docallback",],
 330     # bgpd - main WQ
 331     ("bgp_process", "work_queue_add"): ["bgp_process_wq", "bgp_processq_del",],
 332     ("bgp_add_eoiu_mark", "work_queue_add"): ["bgp_process_wq", "bgp_processq_del",],
 333     # clear node WQ
 334     ("bgp_clear_route_table", "work_queue_add"): [
 335         "bgp_clear_route_node",
 336         "bgp_clear_node_queue_del",
 337         "bgp_clear_node_complete",
 338     ],
 339     # rfapi WQs
 340     ("rfapi_close", "work_queue_add"): ["rfapi_deferred_close_workfunc",],
 341     ("rfapiRibUpdatePendingNode", "work_queue_add"): [
 342         "rfapiRibDoQueuedCallback",
 343         "rfapiRibQueueItemDelete",
 344     ],
 345 }
 346
 347
 348 for func, fdata in data["functions"].items():
 349     func = nameclean(func)
 350     fnode = FunctionNode.get(func).define(fdata)
 351
 352     for call in fdata["calls"]:
 353         if call.get("type") in [None, "unnamed", "thread_sched"]:
 354             if call.get("target") is None:
 355                 continue
 356             tgt = nameclean(call["target"])
 357             fnode.add_call(FunctionNode.get(tgt), call)
 358             for fptr in call.get("funcptrs", []):
 359                 fnode.add_call(FunctionNode.get(nameclean(fptr)), call)
 360             if tgt == "work_queue_add":
 361                 if (func, tgt) not in extra_info:
 362                     sys.stderr.write(
 363                         "%s:%d:%s(): work_queue_add() not handled\n"
 364                         % (call["filename"], call["line"], func)
 365                     )
 366                 else:
 367                     attrs = dict(call)
 368                     attrs.update({"is_external": False, "type": "workqueue"})
 369                     for dst in extra_info[func, tgt]:
 370                         fnode.add_call(FunctionNode.get(dst), call)
 371         elif call["type"] == "install_element":
 372             vty_node = FunctionNode.get("VTY_NODE_%d" % call["vty_node"])
 373             vty_node.add_call(FunctionNode.get(nameclean(call["target"])), call)
 374         elif call["type"] == "hook":
 375             # TODO: edges for hooks from data['hooks']
 376             pass
 377
 378 n = FunctionNode.funcs
 379
 380 # fix some very low end functions cycling back very far to the top
 381 if "peer_free" in n:
 382     n["peer_free"].unlink(n["bgp_timer_set"])
 383     n["peer_free"].unlink(n["bgp_addpath_set_peer_type"])
 384 if "bgp_path_info_extra_free" in n:
 385     n["bgp_path_info_extra_free"].rank = 0
 386
 387 if "zlog_ref" in n:
 388     n["zlog_ref"].rank = 0
 389 if "mt_checkalloc" in n:
 390     n["mt_checkalloc"].rank = 0
 391
 392 queue = list(FunctionNode.funcs.values())
 393 queue = calc_rank(queue, 1)
 394 queue = calc_rank(queue, -1)
 395
 396 sys.stderr.write("%d functions in cyclic set\n" % len(queue))
 397
 398 graph = Graph(queue)
 399 graph.automerge()
 400
 401 gv_nodes = []
 402 gv_edges = []
 403
 404 sys.stderr.write("%d groups after automerge\n" % len(graph._groups))
 405
 406
 407 def is_vnc(n):
 408     return n.startswith("rfapi") or n.startswith("vnc") or ("_vnc_" in n)
 409
 410
 411 _vncstyle = ',fillcolor="#ffffcc",style=filled'
 412 cyclic_set_names = set([fn.name for fn in graph.values()])
 413
 414 for i, group in enumerate(graph._groups):
 415     if len(group) > 1:
 416         group.num = i
 417         gv_nodes.append("\tsubgraph cluster_%d {" % i)
 418         gv_nodes.append("\t\tcolor=blue;")
 419         for gn in group:
 420             has_cycle_callers = set(gn.calld()) - group
 421             has_ext_callers = (
 422                 set([edge.i.name for edge in gn._fn.inb]) - cyclic_set_names
 423             )
 424
 425             style = ""
 426             etext = ""
 427             if is_vnc(gn.name):
 428                 style += _vncstyle
 429             if has_cycle_callers:
 430                 style += ",color=blue,penwidth=3"
 431             if has_ext_callers:
 432                 style += ',fillcolor="#ffeebb",style=filled'
 433                 etext += '<br/><font point-size="10">(%d other callers)</font>' % (
 434                     len(has_ext_callers)
 435                 )
 436
 437             gv_nodes.append(
 438                 '\t\t"%s" [shape=box,label=<%s%s>%s];'
 439                 % (gn.name, "<br/>".join([fn.name for fn in gn._fns]), etext, style)
 440             )
 441         gv_nodes.append("\t}")
 442     else:
 443         for gn in group:
 444             has_ext_callers = (
 445                 set([edge.i.name for edge in gn._fn.inb]) - cyclic_set_names
 446             )
 447
 448             style = ""
 449             etext = ""
 450             if is_vnc(gn.name):
 451                 style += _vncstyle
 452             if has_ext_callers:
 453                 style += ',fillcolor="#ffeebb",style=filled'
 454                 etext += '<br/><font point-size="10">(%d other callers)</font>' % (
 455                     len(has_ext_callers)
 456                 )
 457             gv_nodes.append(
 458                 '\t"%s" [shape=box,label=<%s%s>%s];'
 459                 % (gn.name, "<br/>".join([fn.name for fn in gn._fns]), etext, style)
 460             )
 461
 462 edges = set()
 463 for gn in graph.values():
 464     for calls in gn.calls():
 465         if gn._group == calls._group:
 466             gv_edges.append(
 467                 '\t"%s" -> "%s" [color="#55aa55",style=dashed];' % (gn.name, calls.name)
 468             )
 469         else:
 470
 471             def xname(nn):
 472                 if len(nn._group) > 1:
 473                     return "cluster_%d" % nn._group.num
 474                 else:
 475                     return nn.name
 476
 477             tup = xname(gn), calls.name
 478             if tup[0] != tup[1] and tup not in edges:
 479                 gv_edges.append('\t"%s" -> "%s" [weight=0.0,w=0.0,color=blue];' % tup)
 480                 edges.add(tup)
 481
 482 with open(sys.argv[2], "w") as fd:
 483     fd.write(
 484         """digraph {
 485     node [fontsize=13,fontname="Fira Sans"];
 486 %s
 487 }"""
 488         % "\n".join(gv_nodes + [""] + gv_edges)
 489     )