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 19import re 20import sys 21import json 22 23class 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 66class 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 79def nameclean(n): 80 if '.' in n: 81 return n.split('.', 1)[0] 82 return n 83 84def 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 126class 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 307with open(sys.argv[1], 'r') as fd: 308 data = json.load(fd) 309 310extra_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 360for 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 388n = FunctionNode.funcs 389 390# fix some very low end functions cycling back very far to the top 391if 'peer_free' in n: 392 n['peer_free'].unlink(n['bgp_timer_set']) 393 n['peer_free'].unlink(n['bgp_addpath_set_peer_type']) 394if 'bgp_path_info_extra_free' in n: 395 n['bgp_path_info_extra_free'].rank = 0 396 397if 'zlog_ref' in n: 398 n['zlog_ref'].rank = 0 399if 'mt_checkalloc' in n: 400 n['mt_checkalloc'].rank = 0 401 402queue = list(FunctionNode.funcs.values()) 403queue = calc_rank(queue, 1) 404queue = calc_rank(queue, -1) 405 406sys.stderr.write('%d functions in cyclic set\n' % len(queue)) 407 408graph = Graph(queue) 409graph.automerge() 410 411gv_nodes = [] 412gv_edges = [] 413 414sys.stderr.write('%d groups after automerge\n' % len(graph._groups)) 415 416def is_vnc(n): 417 return n.startswith('rfapi') or n.startswith('vnc') or ('_vnc_' in n) 418 419_vncstyle = ',fillcolor="#ffffcc",style=filled' 420cyclic_set_names = set([fn.name for fn in graph.values()]) 421 422for 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 456edges = set() 457for 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 472with 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)) 477