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