diff options
Diffstat (limited to 'python')
| -rw-r--r-- | python/callgraph-dot.py | 476 | ||||
| -rw-r--r-- | python/firstheader.py | 30 | ||||
| -rw-r--r-- | python/makefile.py | 122 | ||||
| -rw-r--r-- | python/makevars.py | 90 |
4 files changed, 718 insertions, 0 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/firstheader.py b/python/firstheader.py new file mode 100644 index 0000000000..19a85b63e5 --- /dev/null +++ b/python/firstheader.py @@ -0,0 +1,30 @@ +# +# check that the first header included in C files is either +# zebra.h or config.h +# + +import sys, os, re, subprocess + +include_re = re.compile('^#\s*include\s+["<]([^ ">]+)[">]', re.M) + +errors = 0 + +files = subprocess.check_output(['git', 'ls-files']).decode('ASCII') +for fn in files.splitlines(): + if not fn.endswith('.c'): + continue + if fn.startswith('tools/'): + continue + with open(fn, 'r') as fd: + data = fd.read() + m = include_re.search(data) + if m is None: + #sys.stderr.write('no #include in %s?\n' % (fn)) + continue + if m.group(1) in ['config.h', 'zebra.h', 'lib/zebra.h']: + continue + sys.stderr.write('%s: %s\n' % (fn, m.group(0))) + errors += 1 + +if errors: + sys.exit(1) diff --git a/python/makefile.py b/python/makefile.py new file mode 100644 index 0000000000..948d3f7391 --- /dev/null +++ b/python/makefile.py @@ -0,0 +1,122 @@ +#!/usr/bin/python3 +# +# FRR extended automake/Makefile functionality helper +# +# This script is executed on/after generating Makefile to add some pieces for +# clippy. + +import sys +import os +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, + help = 'run additional developer checks') +args = argp.parse_args() + +with open('Makefile', 'r') as fd: + before = fd.read() + +mv = MakeReVars(before) + +clippy_scan = mv['clippy_scan'].strip().split() +for clippy_file in clippy_scan: + assert clippy_file.endswith('.c') + +# check for files using clippy but not listed in clippy_scan +if args.dev_build: + basepath = os.path.dirname(os.path.dirname(os.path.abspath(__file__))) + if os.path.exists(os.path.join(basepath, '.git')): + clippy_ref = subprocess.check_output([ + 'git', '-C', basepath, 'grep', '-l', '-P', '^#\s*include.*_clippy.c', '--', '**.c']).decode('US-ASCII') + + clippy_ref = set(clippy_ref.splitlines()) + missing = clippy_ref - set(clippy_scan) + + if len(missing) > 0: + sys.stderr.write('error: files seem to be using clippy, but not listed in "clippy_scan" in subdir.am:\n\t%s\n' % ('\n\t'.join(sorted(missing)))) + sys.exit(1) + +clippydep = Template(''' +${clippybase}.$$(OBJEXT): ${clippybase}_clippy.c +${clippybase}.lo: ${clippybase}_clippy.c +${clippybase}_clippy.c: $$(CLIPPY_DEPS)''') + +clippyauxdep = Template('''# clippy{ +# auxiliary clippy target +${target}: ${clippybase}_clippy.c +# }clippy''') + +lines = before.splitlines() +autoderp = '#AUTODERP# ' +out_lines = [] +bcdeps = [] +make_rule_re = re.compile('^([^:\s]+):\s*([^:\s]+)\s*($|\n)') + +while lines: + line = lines.pop(0) + if line.startswith(autoderp): + line = line[len(autoderp):] + + if line == '# clippy{': + while lines: + line = lines.pop(0) + if line == '# }clippy': + break + continue + + if line.startswith('#'): + out_lines.append(line) + continue + + m = make_rule_re.match(line) + if m is None: + 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])) + + out_lines.append(line) + +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('') + +after = '\n'.join(out_lines) +if after == before: + sys.exit(0) + +with open('Makefile.pyout', 'w') as fd: + fd.write(after) +os.rename('Makefile.pyout', 'Makefile') diff --git a/python/makevars.py b/python/makevars.py new file mode 100644 index 0000000000..1a85fbd6f5 --- /dev/null +++ b/python/makevars.py @@ -0,0 +1,90 @@ +# +# helper class to grab variables from FRR's Makefile +# + +import os +import subprocess +import re + +class MakeVarsBase(object): + ''' + 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. + ''' + rdfd, wrfd = os.pipe() + + shvars = ['shvar-%s' % s for s in varlist] + make = subprocess.Popen(['make', '-s', 'VARFD=%d' % wrfd] + shvars, pass_fds = [wrfd]) + os.close(wrfd) + data = b'' + + rdf = os.fdopen(rdfd, 'rb') + while True: + rdata = rdf.read() + if len(rdata) == 0: + break + data += rdata + + del rdf + make.wait() + + data = data.decode('US-ASCII').strip().split('\n') + for row in data: + k, v = row.split('=', 1) + v = v[1:-1] + self._data[k] = v + +class MakeReVars(MakeVarsBase): + ''' + makevars['FOO_CFLAGS'] gets you "FOO_CFLAGS" from Makefile + + 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 |