diff options
Diffstat (limited to 'python')
| -rw-r--r-- | python/callgraph-dot.py | 476 | ||||
| -rw-r--r-- | python/makefile.py | 34 | ||||
| -rw-r--r-- | python/makevars.py | 60 |
3 files changed, 554 insertions, 16 deletions
diff --git a/python/callgraph-dot.py b/python/callgraph-dot.py new file mode 100644 index 0000000000..4faf1dae16 --- /dev/null +++ b/python/callgraph-dot.py @@ -0,0 +1,476 @@ +# callgraph json to graphviz generator for FRR +# +# Copyright (C) 2020 David Lamparter for NetDEF, Inc. +# +# This program is free software; you can redistribute it and/or modify it +# under the terms of the GNU General Public License as published by the Free +# Software Foundation; either version 2 of the License, or (at your option) +# any later version. +# +# This program is distributed in the hope that it will be useful, but WITHOUT +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +# FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for +# more details. +# +# You should have received a copy of the GNU General Public License along +# with this program; see the file COPYING; if not, write to the Free Software +# Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + +import re +import sys +import json + +class FunctionNode(object): + funcs = {} + + def __init__(self, name): + super().__init__() + FunctionNode.funcs[name] = self + + self.name = name + self.out = [] + self.inb = [] + self.rank = None + self.defined = False + self.defs = [] + + def __repr__(self): + return '<"%s()" rank=%r>' % (self.name, self.rank) + + def define(self, attrs): + self.defined = True + self.defs.append((attrs['filename'], attrs['line'])) + return self + + def add_call(self, called, attrs): + return CallEdge(self, called, attrs) + + def calls(self): + for e in self.out: + yield e.o + + def calld(self): + for e in self.inb: + yield e.i + + def unlink(self, other): + self.out = list([edge for edge in self.out if edge.o != other]) + other.inb = list([edge for edge in other.inb if edge.i != other]) + + @classmethod + def get(cls, name): + if name in cls.funcs: + return cls.funcs[name] + return FunctionNode(name) + +class CallEdge(object): + def __init__(self, i, o, attrs): + self.i = i + self.o = o + self.is_external = attrs['is_external'] + self.attrs = attrs + + i.out.append(self) + o.inb.append(self) + + def __repr__(self): + return '<"%s()" -> "%s()">' % (self.i.name, self.o.name) + +def nameclean(n): + if '.' in n: + return n.split('.', 1)[0] + return n + +def calc_rank(queue, direction): + nextq = queue + + if direction == 1: + aggr = max + elem = lambda x: x.calls() + else: + aggr = min + elem = lambda x: x.calld() + + currank = direction + cont = True + + while len(nextq) > 0 and cont: + queue = nextq + nextq = [] + + #sys.stderr.write('rank %d\n' % currank) + + cont = False + + for node in queue: + if not node.defined: + node.rank = 0 + continue + + rank = direction + for other in elem(node): + if other is node: + continue + if other.rank is None: + nextq.append(node) + break + rank = aggr(rank, other.rank + direction) + else: + cont = True + node.rank = rank + + currank += direction + + return nextq + +class Graph(dict): + class Subgraph(set): + def __init__(self): + super().__init__() + + class NodeGroup(set): + def __init__(self, members): + super().__init__(members) + + class Node(object): + def __init__(self, graph, fn): + super().__init__() + self._fn = fn + self._fns = [fn] + self._graph = graph + self._calls = set() + self._calld = set() + self._group = None + + def __repr__(self): + return '<Graph.Node "%s()"/%d>' % (self._fn.name, len(self._fns)) + + def __hash__(self): + return hash(self._fn.name) + + def _finalize(self): + for called in self._fn.calls(): + if called.name == self._fn.name: + continue + if called.name in self._graph: + self._calls.add(self._graph[called.name]) + self._graph[called.name]._calld.add(self) + + def unlink(self, other): + self._calls.remove(other) + other._calld.remove(self) + + @property + def name(self): + return self._fn.name + + def calls(self): + return self._calls + def calld(self): + return self._calld + + def group(self, members): + assert self in members + + pregroups = [] + for g in [m._group for m in members]: + if g is None: + continue + if g in pregroups: + continue + + assert g <= members + pregroups.append(g) + + if len(pregroups) == 0: + group = self._graph.NodeGroup(members) + self._graph._groups.append(group) + elif len(pregroups) == 1: + group = pregroups[0] + group |= members + else: + for g in pregroups: + self._graph._groups.remove(g) + group = self._graph.NodeGroup(members) + self._graph._groups.append(group) + + for m in members: + m._group = group + return group + + def merge(self, other): + self._fns.extend(other._fns) + self._calls = (self._calls | other._calls) - {self, other} + self._calld = (self._calld | other._calld) - {self, other} + for c in other._calls: + if c == self: + continue + c._calld.remove(other) + c._calld.add(self) + for c in other._calld: + if c == self: + continue + c._calls.remove(other) + c._calls.add(self) + del self._graph[other._fn.name] + + def __init__(self, funcs): + super().__init__() + self._funcs = funcs + for fn in funcs: + self[fn.name] = self.Node(self, fn) + for node in self.values(): + node._finalize() + self._groups = [] + + def automerge(self): + nodes = list(self.values()) + + while len(nodes): + node = nodes.pop(0) + + candidates = {node} + evalset = set(node.calls()) + prevevalset = None + + while prevevalset != evalset: + prevevalset = evalset + evalset = set() + + for evnode in prevevalset: + inbound = set(evnode.calld()) + if inbound <= candidates: + candidates.add(evnode) + evalset |= set(evnode.calls()) - candidates + else: + evalset.add(evnode) + + #if len(candidates) > 1: + # for candidate in candidates: + # if candidate != node: + # #node.merge(candidate) + # if candidate in nodes: + # nodes.remove(candidate) + node.group(candidates) + + for candidate in candidates: + if candidate in nodes: + nodes.remove(candidate) + + def calc_subgraphs(self): + nodes = list(self.values()) + self._subgraphs = [] + up = {} + down = {} + + self._linear_nodes = [] + + while len(nodes): + sys.stderr.write('%d\n' % len(nodes)) + node = nodes.pop(0) + + down[node] = set() + queue = [node] + while len(queue): + now = queue.pop() + down[node].add(now) + for calls in now.calls(): + if calls in down[node]: + continue + queue.append(calls) + + up[node] = set() + queue = [node] + while len(queue): + now = queue.pop() + up[node].add(now) + for calld in now.calld(): + if calld in up[node]: + continue + queue.append(calld) + + common = up[node] & down[node] + + if len(common) == 1: + self._linear_nodes.append(node) + else: + sg = self.Subgraph() + sg |= common + self._subgraphs.append(sg) + for n in common: + if n != node: + nodes.remove(n) + + return self._subgraphs, self._linear_nodes + + +with open(sys.argv[1], 'r') as fd: + data = json.load(fd) + +extra_info = { + # zebra - LSP WQ + ('lsp_processq_add', 'work_queue_add'): [ + 'lsp_process', + 'lsp_processq_del', + 'lsp_processq_complete', + ], + # zebra - main WQ + ('mq_add_handler', 'work_queue_add'): [ + 'meta_queue_process', + ], + ('meta_queue_process', 'work_queue_add'): [ + 'meta_queue_process', + ], + # bgpd - label pool WQ + ('bgp_lp_get', 'work_queue_add'): [ + 'lp_cbq_docallback', + ], + ('bgp_lp_event_chunk', 'work_queue_add'): [ + 'lp_cbq_docallback', + ], + ('bgp_lp_event_zebra_up', 'work_queue_add'): [ + 'lp_cbq_docallback', + ], + # bgpd - main WQ + ('bgp_process', 'work_queue_add'): [ + 'bgp_process_wq', + 'bgp_processq_del', + ], + ('bgp_add_eoiu_mark', 'work_queue_add'): [ + 'bgp_process_wq', + 'bgp_processq_del', + ], + # clear node WQ + ('bgp_clear_route_table', 'work_queue_add'): [ + 'bgp_clear_route_node', + 'bgp_clear_node_queue_del', + 'bgp_clear_node_complete', + ], + # rfapi WQs + ('rfapi_close', 'work_queue_add'): [ + 'rfapi_deferred_close_workfunc', + ], + ('rfapiRibUpdatePendingNode', 'work_queue_add'): [ + 'rfapiRibDoQueuedCallback', + 'rfapiRibQueueItemDelete', + ], +} + + +for func, fdata in data['functions'].items(): + func = nameclean(func) + fnode = FunctionNode.get(func).define(fdata) + + for call in fdata['calls']: + if call.get('type') in [None, 'unnamed', 'thread_sched']: + if call.get('target') is None: + continue + tgt = nameclean(call['target']) + fnode.add_call(FunctionNode.get(tgt), call) + for fptr in call.get('funcptrs', []): + fnode.add_call(FunctionNode.get(nameclean(fptr)), call) + if tgt == 'work_queue_add': + if (func, tgt) not in extra_info: + sys.stderr.write('%s:%d:%s(): work_queue_add() not handled\n' % ( + call['filename'], call['line'], func)) + else: + attrs = dict(call) + attrs.update({'is_external': False, 'type': 'workqueue'}) + for dst in extra_info[func, tgt]: + fnode.add_call(FunctionNode.get(dst), call) + elif call['type'] == 'install_element': + vty_node = FunctionNode.get('VTY_NODE_%d' % call['vty_node']) + vty_node.add_call(FunctionNode.get(nameclean(call['target'])), call) + elif call['type'] == 'hook': + # TODO: edges for hooks from data['hooks'] + pass + +n = FunctionNode.funcs + +# fix some very low end functions cycling back very far to the top +if 'peer_free' in n: + n['peer_free'].unlink(n['bgp_timer_set']) + n['peer_free'].unlink(n['bgp_addpath_set_peer_type']) +if 'bgp_path_info_extra_free' in n: + n['bgp_path_info_extra_free'].rank = 0 + +if 'zlog_ref' in n: + n['zlog_ref'].rank = 0 +if 'mt_checkalloc' in n: + n['mt_checkalloc'].rank = 0 + +queue = list(FunctionNode.funcs.values()) +queue = calc_rank(queue, 1) +queue = calc_rank(queue, -1) + +sys.stderr.write('%d functions in cyclic set\n' % len(queue)) + +graph = Graph(queue) +graph.automerge() + +gv_nodes = [] +gv_edges = [] + +sys.stderr.write('%d groups after automerge\n' % len(graph._groups)) + +def is_vnc(n): + return n.startswith('rfapi') or n.startswith('vnc') or ('_vnc_' in n) + +_vncstyle = ',fillcolor="#ffffcc",style=filled' +cyclic_set_names = set([fn.name for fn in graph.values()]) + +for i, group in enumerate(graph._groups): + if len(group) > 1: + group.num = i + gv_nodes.append('\tsubgraph cluster_%d {' % i) + gv_nodes.append('\t\tcolor=blue;') + for gn in group: + has_cycle_callers = set(gn.calld()) - group + has_ext_callers = set([edge.i.name for edge in gn._fn.inb]) - cyclic_set_names + + style = '' + etext = '' + if is_vnc(gn.name): + style += _vncstyle + if has_cycle_callers: + style += ',color=blue,penwidth=3' + if has_ext_callers: + style += ',fillcolor="#ffeebb",style=filled' + etext += '<br/><font point-size="10">(%d other callers)</font>' % (len(has_ext_callers)) + + 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)) + gv_nodes.append('\t}') + else: + for gn in group: + has_ext_callers = set([edge.i.name for edge in gn._fn.inb]) - cyclic_set_names + + style = '' + etext = '' + if is_vnc(gn.name): + style += _vncstyle + if has_ext_callers: + style += ',fillcolor="#ffeebb",style=filled' + etext += '<br/><font point-size="10">(%d other callers)</font>' % (len(has_ext_callers)) + gv_nodes.append('\t"%s" [shape=box,label=<%s%s>%s];' % (gn.name, '<br/>'.join([fn.name for fn in gn._fns]), etext, style)) + +edges = set() +for gn in graph.values(): + for calls in gn.calls(): + if gn._group == calls._group: + gv_edges.append('\t"%s" -> "%s" [color="#55aa55",style=dashed];' % (gn.name, calls.name)) + else: + def xname(nn): + if len(nn._group) > 1: + return 'cluster_%d' % nn._group.num + else: + return nn.name + tup = xname(gn), calls.name + if tup[0] != tup[1] and tup not in edges: + gv_edges.append('\t"%s" -> "%s" [weight=0.0,w=0.0,color=blue];' % tup) + edges.add(tup) + +with open(sys.argv[2], 'w') as fd: + fd.write('''digraph { + node [fontsize=13,fontname="Fira Sans"]; +%s +}''' % '\n'.join(gv_nodes + [''] + gv_edges)) diff --git a/python/makefile.py b/python/makefile.py index 9af397d373..948d3f7391 100644 --- a/python/makefile.py +++ b/python/makefile.py @@ -11,6 +11,7 @@ import subprocess import re import argparse from string import Template +from makevars import MakeReVars argp = argparse.ArgumentParser(description = 'FRR Makefile extensions') argp.add_argument('--dev-build', action = 'store_const', const = True, @@ -20,13 +21,9 @@ args = argp.parse_args() with open('Makefile', 'r') as fd: before = fd.read() -nolinecont = before.replace('\\\n', '') -m = re.search('^clippy_scan\s*=([^#]*)(?:#.*)?$', nolinecont, flags=re.MULTILINE) -if m is None: - sys.stderr.write('failed to parse Makefile.in\n') - sys.exit(2) +mv = MakeReVars(before) -clippy_scan = m.group(1).strip().split() +clippy_scan = mv['clippy_scan'].strip().split() for clippy_file in clippy_scan: assert clippy_file.endswith('.c') @@ -57,6 +54,7 @@ ${target}: ${clippybase}_clippy.c lines = before.splitlines() autoderp = '#AUTODERP# ' out_lines = [] +bcdeps = [] make_rule_re = re.compile('^([^:\s]+):\s*([^:\s]+)\s*($|\n)') while lines: @@ -80,6 +78,12 @@ while lines: out_lines.append(line) continue + target, dep = m.group(1), m.group(2) + + if target.endswith('.lo') or target.endswith('.o'): + if not dep.endswith('.h'): + bcdeps.append('%s.bc: %s' % (target, target)) + bcdeps.append('\t$(AM_V_LLVM_BC)$(COMPILE) -emit-llvm -c -o $@ %s' % (dep)) if m.group(2) in clippy_scan: out_lines.append(clippyauxdep.substitute(target=m.group(1), clippybase=m.group(2)[:-2])) @@ -88,6 +92,24 @@ while lines: out_lines.append('# clippy{\n# main clippy targets') for clippy_file in clippy_scan: out_lines.append(clippydep.substitute(clippybase = clippy_file[:-2])) + +out_lines.append('') +out_lines.extend(bcdeps) +out_lines.append('') +bc_targets = [] +for varname in ['bin_PROGRAMS', 'sbin_PROGRAMS', 'lib_LTLIBRARIES', 'module_LTLIBRARIES', 'noinst_LIBRARIES']: + bc_targets.extend(mv[varname].strip().split()) +for target in bc_targets: + amtgt = target.replace('/', '_').replace('.', '_').replace('-', '_') + objs = mv[amtgt + '_OBJECTS'].strip().split() + objs = [obj + '.bc' for obj in objs] + deps = mv.get(amtgt + '_DEPENDENCIES', '').strip().split() + deps = [d + '.bc' for d in deps if d.endswith('.a')] + objs.extend(deps) + out_lines.append('%s.bc: %s' % (target, ' '.join(objs))) + out_lines.append('\t$(AM_V_LLVM_LD)$(LLVM_LINK) -o $@ $^') + out_lines.append('') + out_lines.append('# }clippy') out_lines.append('') diff --git a/python/makevars.py b/python/makevars.py index e0e2031a0d..1a85fbd6f5 100644 --- a/python/makevars.py +++ b/python/makevars.py @@ -4,14 +4,33 @@ import os import subprocess +import re -class MakeVars(object): +class MakeVarsBase(object): ''' - makevars['FOO_CFLAGS'] gets you "FOO_CFLAGS" from Makefile + common code between MakeVars and MakeReVars ''' def __init__(self): self._data = dict() + def __getitem__(self, k): + if k not in self._data: + self.getvars([k]) + return self._data[k] + + def get(self, k, defval = None): + if k not in self._data: + self.getvars([k]) + return self._data.get(k) or defval + +class MakeVars(MakeVarsBase): + ''' + makevars['FOO_CFLAGS'] gets you "FOO_CFLAGS" from Makefile + + This variant works by invoking make as a subprocess, i.e. Makefile must + be valid and working. (This is sometimes a problem if depfiles have not + been generated.) + ''' def getvars(self, varlist): ''' get a batch list of variables from make. faster than individual calls. @@ -39,12 +58,33 @@ class MakeVars(object): v = v[1:-1] self._data[k] = v - def __getitem__(self, k): - if k not in self._data: - self.getvars([k]) - return self._data[k] +class MakeReVars(MakeVarsBase): + ''' + makevars['FOO_CFLAGS'] gets you "FOO_CFLAGS" from Makefile - def get(self, k, defval = None): - if k not in self._data: - self.getvars([k]) - return self._data[k] or defval + This variant works by regexing through Makefile. This means the Makefile + does not need to be fully working, but on the other hand it doesn't support + fancy complicated make expressions. + ''' + var_re = re.compile(r'^([^=#\n\s]+)[ \t]*=[ \t]*([^#\n]*)(?:#.*)?$', flags=re.MULTILINE) + repl_re = re.compile(r'\$(?:([A-Za-z])|\(([^\)]+)\))') + + def __init__(self, maketext): + super().__init__() + self._vars = dict(self.var_re.findall(maketext.replace('\\\n', ''))) + + def replacevar(self, match): + varname = match.group(1) or match.group(2) + return self._vars.get(varname, '') + + def getvars(self, varlist): + for varname in varlist: + if varname not in self._vars: + continue + + val, prevval = self._vars[varname], None + while val != prevval: + prevval = val + val = self.repl_re.sub(self.replacevar, val) + + self._data[varname] = val |