]>
git.proxmox.com Git - mirror_frr.git/blob - python/callgraph-dot.py
1 # callgraph json to graphviz generator for FRR
3 # Copyright (C) 2020 David Lamparter for NetDEF, Inc.
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)
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
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
23 class FunctionNode(object):
26 def __init__(self
, name
):
28 FunctionNode
.funcs
[name
] = self
38 return '<"%s()" rank=%r>' % (self
.name
, self
.rank
)
40 def define(self
, attrs
):
42 self
.defs
.append((attrs
['filename'], attrs
['line']))
45 def add_call(self
, called
, attrs
):
46 return CallEdge(self
, called
, attrs
)
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
])
63 return cls
.funcs
[name
]
64 return FunctionNode(name
)
66 class CallEdge(object):
67 def __init__(self
, i
, o
, attrs
):
70 self
.is_external
= attrs
['is_external']
77 return '<"%s()" -> "%s()">' % (self
.i
.name
, self
.o
.name
)
81 return n
.split('.', 1)[0]
84 def calc_rank(queue
, direction
):
89 elem
= lambda x
: x
.calls()
92 elem
= lambda x
: x
.calld()
97 while len(nextq
) > 0 and cont
:
101 #sys.stderr.write('rank %d\n' % currank)
111 for other
in elem(node
):
114 if other
.rank
is None:
117 rank
= aggr(rank
, other
.rank
+ direction
)
131 class NodeGroup(set):
132 def __init__(self
, members
):
133 super().__init
__(members
)
136 def __init__(self
, graph
, fn
):
146 return '<Graph.Node "%s()"/%d>' % (self
._fn
.name
, len(self
._fns
))
149 return hash(self
._fn
.name
)
152 for called
in self
._fn
.calls():
153 if called
.name
== self
._fn
.name
:
155 if called
.name
in self
._graph
:
156 self
._calls
.add(self
._graph
[called
.name
])
157 self
._graph
[called
.name
]._calld
.add(self
)
159 def unlink(self
, other
):
160 self
._calls
.remove(other
)
161 other
._calld
.remove(self
)
172 def group(self
, members
):
173 assert self
in members
176 for g
in [m
._group
for m
in members
]:
185 if len(pregroups
) == 0:
186 group
= self
._graph
.NodeGroup(members
)
187 self
._graph
._groups
.append(group
)
188 elif len(pregroups
) == 1:
193 self
._graph
._groups
.remove(g
)
194 group
= self
._graph
.NodeGroup(members
)
195 self
._graph
._groups
.append(group
)
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
:
208 c
._calld
.remove(other
)
210 for c
in other
._calld
:
213 c
._calls
.remove(other
)
215 del self
._graph
[other
._fn
.name
]
217 def __init__(self
, funcs
):
221 self
[fn
.name
] = self
.Node(self
, fn
)
222 for node
in self
.values():
227 nodes
= list(self
.values())
233 evalset
= set(node
.calls())
236 while prevevalset
!= evalset
:
237 prevevalset
= evalset
240 for evnode
in prevevalset
:
241 inbound
= set(evnode
.calld())
242 if inbound
<= candidates
:
243 candidates
.add(evnode
)
244 evalset |
= set(evnode
.calls()) - candidates
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
)
256 for candidate
in candidates
:
257 if candidate
in nodes
:
258 nodes
.remove(candidate
)
260 def calc_subgraphs(self
):
261 nodes
= list(self
.values())
266 self
._linear
_nodes
= []
269 sys
.stderr
.write('%d\n' % len(nodes
))
277 for calls
in now
.calls():
278 if calls
in down
[node
]:
287 for calld
in now
.calld():
288 if calld
in up
[node
]:
292 common
= up
[node
] & down
[node
]
295 self
._linear
_nodes
.append(node
)
299 self
._subgraphs
.append(sg
)
304 return self
._subgraphs
, self
._linear
_nodes
307 with
open(sys
.argv
[1], 'r') as fd
:
312 ('lsp_processq_add', 'work_queue_add'): [
315 'lsp_processq_complete',
318 ('mq_add_handler', 'work_queue_add'): [
319 'meta_queue_process',
321 ('meta_queue_process', 'work_queue_add'): [
322 'meta_queue_process',
324 # bgpd - label pool WQ
325 ('bgp_lp_get', 'work_queue_add'): [
328 ('bgp_lp_event_chunk', 'work_queue_add'): [
331 ('bgp_lp_event_zebra_up', 'work_queue_add'): [
335 ('bgp_process', 'work_queue_add'): [
339 ('bgp_add_eoiu_mark', 'work_queue_add'): [
344 ('bgp_clear_route_table', 'work_queue_add'): [
345 'bgp_clear_route_node',
346 'bgp_clear_node_queue_del',
347 'bgp_clear_node_complete',
350 ('rfapi_close', 'work_queue_add'): [
351 'rfapi_deferred_close_workfunc',
353 ('rfapiRibUpdatePendingNode', 'work_queue_add'): [
354 'rfapiRibDoQueuedCallback',
355 'rfapiRibQueueItemDelete',
360 for func
, fdata
in data
['functions'].items():
361 func
= nameclean(func
)
362 fnode
= FunctionNode
.get(func
).define(fdata
)
364 for call
in fdata
['calls']:
365 if call
.get('type') in [None, 'unnamed', 'thread_sched']:
366 if call
.get('target') is None:
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
))
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']
388 n
= FunctionNode
.funcs
390 # fix some very low end functions cycling back very far to the top
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
398 n
['zlog_ref'].rank
= 0
399 if 'mt_checkalloc' in n
:
400 n
['mt_checkalloc'].rank
= 0
402 queue
= list(FunctionNode
.funcs
.values())
403 queue
= calc_rank(queue
, 1)
404 queue
= calc_rank(queue
, -1)
406 sys
.stderr
.write('%d functions in cyclic set\n' % len(queue
))
414 sys
.stderr
.write('%d groups after automerge\n' % len(graph
._groups
))
417 return n
.startswith('rfapi') or n
.startswith('vnc') or ('_vnc_' in n
)
419 _vncstyle
= ',fillcolor="#ffffcc",style=filled'
420 cyclic_set_names
= set([fn
.name
for fn
in graph
.values()])
422 for i
, group
in enumerate(graph
._groups
):
425 gv_nodes
.append('\tsubgraph cluster_%d {' % i
)
426 gv_nodes
.append('\t\tcolor=blue;')
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
435 if has_cycle_callers
:
436 style
+= ',color=blue,penwidth=3'
438 style
+= ',fillcolor="#ffeebb",style=filled'
439 etext
+= '<br/><font point-size="10">(%d other callers)</font>' % (len(has_ext_callers
))
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}')
445 has_ext_callers
= set([edge
.i
.name
for edge
in gn
._fn
.inb
]) - cyclic_set_names
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
))
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
))
463 if len(nn
._group
) > 1:
464 return 'cluster_%d' % nn
._group
.num
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
)
472 with
open(sys
.argv
[2], 'w') as fd
:
473 fd
.write('''digraph {
474 node [fontsize=13,fontname="Fira Sans"];
476 }''' % '\n'.join(gv_nodes
+ [''] + gv_edges
))