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