diff options
| -rw-r--r-- | .gitignore | 4 | ||||
| -rw-r--r-- | Makefile.am | 42 | ||||
| -rw-r--r-- | bgpd/bgp_community.c | 3 | ||||
| -rw-r--r-- | bgpd/bgp_ecommunity.c | 3 | ||||
| -rw-r--r-- | bgpd/bgp_lcommunity.c | 3 | ||||
| -rw-r--r-- | grpc/subdir.am | 2 | ||||
| -rw-r--r-- | ldpd/subdir.am | 1 | ||||
| -rw-r--r-- | lib/hook.h | 2 | ||||
| -rw-r--r-- | lib/subdir.am | 2 | ||||
| -rw-r--r-- | python/callgraph-dot.py | 476 | ||||
| -rw-r--r-- | python/makefile.py | 34 | ||||
| -rw-r--r-- | python/makevars.py | 60 | ||||
| -rw-r--r-- | qpb/subdir.am | 1 | ||||
| -rw-r--r-- | tools/frr-llvm-cg.c | 649 | ||||
| -rw-r--r-- | tools/subdir.am | 12 |
15 files changed, 1273 insertions, 21 deletions
diff --git a/.gitignore b/.gitignore index 4c8370375d..fbbb04b60c 100644 --- a/.gitignore +++ b/.gitignore @@ -55,6 +55,10 @@ *.pb-c.c *.pb.cc *_clippy.c +*.bc +*.cg.json +*.cg.dot +*.cg.svg ### gcov outputs diff --git a/Makefile.am b/Makefile.am index 1e3311fa7b..a959fd9e5a 100644 --- a/Makefile.am +++ b/Makefile.am @@ -89,9 +89,11 @@ clippy-only: Makefile lib/clippy config.h #AUTODERP# endif EXTRA_DIST = +EXTRA_PROGRAMS = BUILT_SOURCES = CLEANFILES = DISTCLEANFILES = +SUFFIXES = examplesdir = $(exampledir) @@ -231,12 +233,48 @@ EXTRA_DIST += \ vrrpd/Makefile \ # end -clean-local: clean-python -.PHONY: clean-python +AM_V_LLVM_BC = $(am__v_LLVM_BC_$(V)) +am__v_LLVM_BC_ = $(am__v_LLVM_BC_$(AM_DEFAULT_VERBOSITY)) +am__v_LLVM_BC_0 = @echo " LLVM.BC " $@; +am__v_LLVM_BC_1 = + +AM_V_LLVM_LD = $(am__v_LLVM_LD_$(V)) +am__v_LLVM_LD_ = $(am__v_LLVM_LD_$(AM_DEFAULT_VERBOSITY)) +am__v_LLVM_LD_0 = @echo " LLVM.LD " $@; +am__v_LLVM_LD_1 = + +SUFFIXES += .lo.bc .o.bc + +.o.o.bc: + $(AM_V_LLVM_BC)$(COMPILE) -emit-llvm -c -o $@ $(patsubst %.o,%.c,$<) +.lo.lo.bc: + $(AM_V_LLVM_BC)$(COMPILE) -emit-llvm -c -o $@ $(patsubst %.lo,%.c,$<) + +%.cg.json: %.bc tools/frr-llvm-cg + tools/frr-llvm-cg -o $@ $< +%.cg.dot: %.cg.json + $(PYTHON) $(top_srcdir)/python/callgraph-dot.py $< $@ +%.cg.svg: %.cg.dot + @echo if the following command fails, you need to install graphviz. + @echo also, the output is nondeterministic. run it multiple times and use the nicest output. + @echo tuning parameters may yield nicer looking graphs as well. + fdp -GK=0.7 -Gstart=42231337 -Gmaxiter=2000 -Elen=2 -Gnodesep=1.5 -Tsvg -o$@ $< +# don't delete intermediaries +.PRECIOUS: %.cg.json %.cg.dot + +# <lib>.la.bc, <lib>.a.bc and <daemon>.bc targets are generated by +# python/makefile.py +LLVM_LINK = llvm-link-$(llvm_version) + +clean-local: clean-python clean-llvm-bitcode +.PHONY: clean-python clean-llvm-bitcode clean-python: find . -name __pycache__ -o -name .pytest_cache | xargs rm -rf find . -name "*.pyc" -o -name "*_clippy.c" | xargs rm -f +clean-llvm-bitcode: + find . -name "*.bc" -o -name "*.cg.json" -o -name "*.cg.dot" -o -name "*.cg.svg" | xargs rm -f + redistclean: $(MAKE) distclean CONFIG_CLEAN_FILES="$(filter-out $(EXTRA_DIST), $(CONFIG_CLEAN_FILES))" diff --git a/bgpd/bgp_community.c b/bgpd/bgp_community.c index 30de84c878..0d60fbf479 100644 --- a/bgpd/bgp_community.c +++ b/bgpd/bgp_community.c @@ -40,6 +40,9 @@ static struct community *community_new(void) /* Free communities value. */ void community_free(struct community **com) { + if (!(*com)) + return; + XFREE(MTYPE_COMMUNITY_VAL, (*com)->val); XFREE(MTYPE_COMMUNITY_STR, (*com)->str); diff --git a/bgpd/bgp_ecommunity.c b/bgpd/bgp_ecommunity.c index 062a6477fa..d13da74b04 100644 --- a/bgpd/bgp_ecommunity.c +++ b/bgpd/bgp_ecommunity.c @@ -59,6 +59,9 @@ void ecommunity_strfree(char **s) /* Allocate ecommunities. */ void ecommunity_free(struct ecommunity **ecom) { + if (!(*ecom)) + return; + XFREE(MTYPE_ECOMMUNITY_VAL, (*ecom)->val); XFREE(MTYPE_ECOMMUNITY_STR, (*ecom)->str); XFREE(MTYPE_ECOMMUNITY, *ecom); diff --git a/bgpd/bgp_lcommunity.c b/bgpd/bgp_lcommunity.c index f47ae91663..5900fcf862 100644 --- a/bgpd/bgp_lcommunity.c +++ b/bgpd/bgp_lcommunity.c @@ -44,6 +44,9 @@ static struct lcommunity *lcommunity_new(void) /* Allocate lcommunities. */ void lcommunity_free(struct lcommunity **lcom) { + if (!(*lcom)) + return; + XFREE(MTYPE_LCOMMUNITY_VAL, (*lcom)->val); XFREE(MTYPE_LCOMMUNITY_STR, (*lcom)->str); if ((*lcom)->json) diff --git a/grpc/subdir.am b/grpc/subdir.am index 048e12a024..045848aee7 100644 --- a/grpc/subdir.am +++ b/grpc/subdir.am @@ -26,6 +26,8 @@ am__v_PROTOC_ = $(am__v_PROTOC_$(AM_DEFAULT_VERBOSITY)) am__v_PROTOC_0 = @echo " PROTOC" $@; am__v_PROTOC_1 = +SUFFIXES += .pb.h .pb.cc .grpc.pb.cc + .proto.pb.cc: $(AM_V_PROTOC)$(PROTOC) -I$(top_srcdir) --cpp_out=$(top_srcdir) $(top_srcdir)/$^ .proto.grpc.pb.cc: diff --git a/ldpd/subdir.am b/ldpd/subdir.am index 09936e5c28..0b38c37872 100644 --- a/ldpd/subdir.am +++ b/ldpd/subdir.am @@ -28,7 +28,6 @@ ldpd_libldp_a_SOURCES = \ ldpd/ldp_vty_conf.c \ ldpd/ldp_vty_exec.c \ ldpd/ldp_zebra.c \ - ldpd/ldpd.c \ ldpd/ldpe.c \ ldpd/log.c \ ldpd/logmsg.c \ diff --git a/lib/hook.h b/lib/hook.h index 3823cebe6a..bef5351e90 100644 --- a/lib/hook.h +++ b/lib/hook.h @@ -145,7 +145,7 @@ extern void _hook_register(struct hook *hook, struct hookent *stackent, */ #define _hook_reg_svar(hook, funcptr, arg, has_arg, module, funcname, prio) \ do { \ - static struct hookent stack_hookent = { .ent_on_heap = 0, }; \ + static struct hookent stack_hookent = {}; \ _hook_register(hook, &stack_hookent, funcptr, arg, has_arg, \ module, funcname, prio); \ } while (0) diff --git a/lib/subdir.am b/lib/subdir.am index 2f8cbe5d52..b2f3e7c5de 100644 --- a/lib/subdir.am +++ b/lib/subdir.am @@ -415,7 +415,7 @@ am__v_CLIPPY_1 = CLIPPY_DEPS = $(CLIPPY) $(top_srcdir)/python/clidef.py -SUFFIXES = _clippy.c .proto .pb-c.c .pb-c.h .pb.h .pb.cc .grpc.pb.cc +SUFFIXES += _clippy.c .c_clippy.c: $(AM_V_CLIPPY) $(CLIPPY) $(top_srcdir)/python/clidef.py -o $@ $< 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 diff --git a/qpb/subdir.am b/qpb/subdir.am index 1864ba7369..80f8f3aca9 100644 --- a/qpb/subdir.am +++ b/qpb/subdir.am @@ -29,6 +29,7 @@ CLEANFILES += \ # end EXTRA_DIST += qpb/qpb.proto +SUFFIXES += .proto .pb-c.c .pb-c.h if HAVE_PROTOBUF diff --git a/tools/frr-llvm-cg.c b/tools/frr-llvm-cg.c new file mode 100644 index 0000000000..84a756a376 --- /dev/null +++ b/tools/frr-llvm-cg.c @@ -0,0 +1,649 @@ +// This is free and unencumbered software released into the public domain. +// +// Anyone is free to copy, modify, publish, use, compile, sell, or +// distribute this software, either in source code form or as a compiled +// binary, for any purpose, commercial or non-commercial, and by any +// means. +// +// In jurisdictions that recognize copyright laws, the author or authors +// of this software dedicate any and all copyright interest in the +// software to the public domain. We make this dedication for the benefit +// of the public at large and to the detriment of our heirs and +// successors. We intend this dedication to be an overt act of +// relinquishment in perpetuity of all present and future rights to this +// software under copyright law. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +// IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR +// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, +// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +// +// For more information, please refer to <http://unlicense.org/> + +/* based on example code: https://github.com/sheredom/llvm_bc_parsing_example + * which came under the above (un-)license. does not depend on any FRR + * pieces, so no reason to change the license. + * + * please note that while included in the FRR sources, this tool is in no way + * supported or maintained by the FRR community. it is provided as a + * "convenience"; while it worked at some point (using LLVM 8 / 9), it may + * easily break with a future LLVM version or any other factors. + * + * 2020-05-04, David Lamparter + */ + +#include <string.h> +#include <strings.h> +#include <stdbool.h> +#include <stdlib.h> +#include <stdio.h> +#include <unistd.h> +#include <errno.h> +#include <assert.h> + +#include <llvm-c/BitReader.h> +#include <llvm-c/BitWriter.h> +#include <llvm-c/Core.h> + +#include <json-c/json.h> + +/* if you want to use this without the special FRRouting defines, + * remove the following #define + */ +#define FRR_SPECIFIC + +static void dbgloc_add(struct json_object *jsobj, LLVMValueRef obj) +{ + unsigned file_len = 0; + const char *file = LLVMGetDebugLocFilename(obj, &file_len); + unsigned line = LLVMGetDebugLocLine(obj); + + if (!file) + file = "???", file_len = 3; + else if (file[0] == '.' && file[1] == '/') + file += 2, file_len -= 2; + + json_object_object_add(jsobj, "filename", + json_object_new_string_len(file, file_len)); + json_object_object_add(jsobj, "line", json_object_new_int64(line)); +} + +static struct json_object *js_get_or_make(struct json_object *parent, + const char *key, + struct json_object *(*maker)(void)) +{ + struct json_object *ret; + + ret = json_object_object_get(parent, key); + if (ret) + return ret; + ret = maker(); + json_object_object_add(parent, key, ret); + return ret; +} + +static bool details_fptr_vars = false; +static bool details_fptr_consts = true; + +enum called_fn { + FN_GENERIC = 0, + FN_NONAME, + FN_INSTALL_ELEMENT, + FN_THREAD_ADD, +}; + +static void walk_const_fptrs(struct json_object *js_call, LLVMValueRef value, + const char *prefix, bool *hdr_written) +{ + LLVMTypeRef type; + LLVMValueKind kind; + + if (LLVMIsAGlobalVariable(value)) { + type = LLVMGlobalGetValueType(value); + value = LLVMGetInitializer(value); + } else { + type = LLVMTypeOf(value); + } + + if (LLVMIsAFunction(value)) { + struct json_object *js_fptrs; + + js_fptrs = js_get_or_make(js_call, "funcptrs", + json_object_new_array); + + size_t fn_len; + const char *fn_name = LLVMGetValueName2(value, &fn_len); + + size_t curlen = json_object_array_length(js_fptrs); + struct json_object *jsobj; + const char *s; + + for (size_t i = 0; i < curlen; i++) { + jsobj = json_object_array_get_idx(js_fptrs, i); + s = json_object_get_string(jsobj); + + if (s && !strcmp(s, fn_name)) + return; + } + + if (details_fptr_consts && !*hdr_written) { + fprintf(stderr, + "%s: calls function pointer from constant or global data\n", + prefix); + *hdr_written = true; + } + if (details_fptr_consts) + fprintf(stderr, "%s- constant: %.*s()\n", + prefix, (int)fn_len, fn_name); + + json_object_array_add(js_fptrs, + json_object_new_string_len(fn_name, + fn_len)); + return; + } + + kind = LLVMGetValueKind(value); + + unsigned len; + char *dump; + + switch (kind) { + case LLVMUndefValueValueKind: + case LLVMConstantAggregateZeroValueKind: + case LLVMConstantPointerNullValueKind: + /* null pointer / array - ignore */ + break; + + case LLVMConstantIntValueKind: + /* integer - ignore */ + break; + + case LLVMConstantStructValueKind: + len = LLVMCountStructElementTypes(type); + for (unsigned i = 0; i < len; i++) + walk_const_fptrs(js_call, LLVMGetOperand(value, i), + prefix, hdr_written); + break; + + case LLVMConstantArrayValueKind: + len = LLVMGetArrayLength(type); + for (unsigned i = 0; i < len; i++) + walk_const_fptrs(js_call, LLVMGetOperand(value, i), + prefix, hdr_written); + return; + + default: + /* to help the user / development */ + if (!*hdr_written) { + fprintf(stderr, + "%s: calls function pointer from constant or global data\n", + prefix); + *hdr_written = true; + } + dump = LLVMPrintValueToString(value); + fprintf(stderr, + "%s- value could not be processed:\n" + "%s- [kind=%d] %s\n", + prefix, prefix, kind, dump); + LLVMDisposeMessage(dump); + return; + } + return; +} + +#ifdef FRR_SPECIFIC +static bool is_thread_sched(const char *name, size_t len) +{ +#define thread_prefix "funcname_" + static const char *const names[] = { + thread_prefix "thread_add_read_write", + thread_prefix "thread_add_timer", + thread_prefix "thread_add_timer_msec", + thread_prefix "thread_add_timer_tv", + thread_prefix "thread_add_event", + thread_prefix "thread_execute", + }; + size_t i; + + for (i = 0; i < sizeof(names) / sizeof(names[0]); i++) { + if (strlen(names[i]) != len) + continue; + if (!memcmp(names[i], name, len)) + return true; + } + return false; +} +#endif + +static void process_call(struct json_object *js_calls, + struct json_object *js_special, + LLVMValueRef instr, + LLVMValueRef function) +{ + struct json_object *js_call, *js_fptrs = NULL; + + LLVMValueRef called = LLVMGetCalledValue(instr); + + if (LLVMIsAConstantExpr(called)) { + LLVMOpcode opcode = LLVMGetConstOpcode(called); + + if (opcode == LLVMBitCast) { + LLVMValueRef op0 = LLVMGetOperand(called, 0); + + if (LLVMIsAFunction(op0)) + called = op0; + } + } + + size_t called_len = 0; + const char *called_name = LLVMGetValueName2(called, &called_len); + unsigned n_args = LLVMGetNumArgOperands(instr); + + bool is_external = LLVMIsDeclaration(called); + enum called_fn called_type = FN_GENERIC; + + js_call = json_object_new_object(); + json_object_array_add(js_calls, js_call); + dbgloc_add(js_call, instr); + json_object_object_add(js_call, "is_external", + json_object_new_boolean(is_external)); + + if (!called_name || called_len == 0) { + called_type = FN_NONAME; + json_object_object_add(js_call, "type", + json_object_new_string("indirect")); + + LLVMValueRef last = called; + + size_t name_len = 0; + const char *name_c = LLVMGetValueName2(function, &name_len); + +#ifdef FRR_SPECIFIC + /* information for FRR hooks is dumped for the registration + * in _hook_typecheck; we can safely ignore the funcptr here + */ + if (strncmp(name_c, "hook_call_", 10) == 0) + return; +#endif + + unsigned file_len = 0; + const char *file = LLVMGetDebugLocFilename(instr, &file_len); + unsigned line = LLVMGetDebugLocLine(instr); + + char prefix[256]; + snprintf(prefix, sizeof(prefix), "%.*s:%d:%.*s()", + (int)file_len, file, line, (int)name_len, name_c); + + while (LLVMIsALoadInst(last) || LLVMIsAGetElementPtrInst(last)) + /* skipping over details for GEP here, but meh. */ + last = LLVMGetOperand(last, 0); + + if (LLVMIsAAllocaInst(last)) { + /* "alloca" is just generically all variables on the + * stack, this does not refer to C alloca() calls + * + * looking at the control flow in the function can + * give better results here, it's just not implemented + * (yet?) + */ + fprintf(stderr, + "%s: call to a function pointer variable\n", + prefix); + + if (details_fptr_vars) { + char *dump = LLVMPrintValueToString(called); + printf("%s- %s\n", prefix, dump); + LLVMDisposeMessage(dump); + } + + json_object_object_add( + js_call, "type", + json_object_new_string("stack_fptr")); + } else if (LLVMIsACallInst(last)) { + /* calling the a function pointer returned from + * another function. + */ + struct json_object *js_indirect; + + js_indirect = js_get_or_make(js_call, "return_of", + json_object_new_array); + + process_call(js_indirect, js_special, last, function); + } else if (LLVMIsAConstant(last)) { + /* function pointer is a constant (includes loading + * from complicated constants like structs or arrays.) + */ + bool hdr_written = false; + walk_const_fptrs(js_call, last, prefix, &hdr_written); + if (details_fptr_consts && !hdr_written) + fprintf(stderr, + "%s: calls function pointer from constant or global data, but no non-NULL function pointers found\n", + prefix); + } else { + char *dump = LLVMPrintValueToString(called); + printf("\t%s\n", dump); + LLVMDisposeMessage(dump); + } + return; +#ifdef FRR_SPECIFIC + } else if (!strcmp(called_name, "install_element")) { + called_type = FN_INSTALL_ELEMENT; + + LLVMValueRef param0 = LLVMGetOperand(instr, 0); + if (!LLVMIsAConstantInt(param0)) + goto out_nonconst; + + long long vty_node = LLVMConstIntGetSExtValue(param0); + json_object_object_add(js_call, "vty_node", + json_object_new_int64(vty_node)); + + LLVMValueRef param1 = LLVMGetOperand(instr, 1); + if (!LLVMIsAGlobalVariable(param1)) + goto out_nonconst; + + LLVMValueRef intlz = LLVMGetInitializer(param1); + assert(intlz && LLVMIsConstant(intlz)); + + LLVMValueKind intlzkind = LLVMGetValueKind(intlz); + assert(intlzkind == LLVMConstantStructValueKind); + + LLVMValueRef funcptr = LLVMGetOperand(intlz, 4); + assert(LLVMIsAFunction(funcptr)); + + size_t target_len = 0; + const char *target; + target = LLVMGetValueName2(funcptr, &target_len); + + json_object_object_add( + js_call, "type", + json_object_new_string("install_element")); + json_object_object_add( + js_call, "target", + json_object_new_string_len(target, target_len)); + return; + + out_nonconst: + json_object_object_add( + js_call, "target", + json_object_new_string("install_element")); + return; + } else if (is_thread_sched(called_name, called_len)) { + called_type = FN_THREAD_ADD; + + json_object_object_add(js_call, "type", + json_object_new_string("thread_sched")); + json_object_object_add( + js_call, "subtype", + json_object_new_string_len(called_name, called_len)); + + LLVMValueRef fparam; + if (strstr(called_name, "_read_")) + fparam = LLVMGetOperand(instr, 2); + else + fparam = LLVMGetOperand(instr, 1); + assert(fparam); + + size_t target_len = 0; + const char *target; + target = LLVMGetValueName2(fparam, &target_len); + + json_object_object_add(js_call, "target", + !target_len ? NULL : + json_object_new_string_len(target, target_len)); + if (!LLVMIsAFunction(fparam)) + json_object_object_add(js_call, "target_unresolved", + json_object_new_boolean(true)); + return; + } else if (!strncmp(called_name, "_hook_typecheck_", + strlen("_hook_typecheck_"))) { + struct json_object *js_hook, *js_this; + const char *hook_name; + + hook_name = called_name + strlen("_hook_typecheck_"); + + json_object_object_add(js_call, "type", + json_object_new_string("hook")); + + LLVMValueRef param0 = LLVMGetOperand(instr, 0); + if (!LLVMIsAFunction(param0)) + return; + + size_t target_len = 0; + const char *target; + target = LLVMGetValueName2(param0, &target_len); + + js_hook = js_get_or_make(js_special, "hooks", + json_object_new_object); + js_hook = js_get_or_make(js_hook, hook_name, + json_object_new_array); + + js_this = json_object_new_object(); + json_object_array_add(js_hook, js_this); + + dbgloc_add(js_this, instr); + json_object_object_add( + js_this, "target", + json_object_new_string_len(target, target_len)); + return; + + /* TODO (FRR specifics): + * - workqueues - not sure we can do much there + * - zclient->* ? + */ +#endif /* FRR_SPECIFIC */ + } else { + json_object_object_add( + js_call, "target", + json_object_new_string_len(called_name, called_len)); + } + + for (unsigned argno = 0; argno < n_args; argno++) { + LLVMValueRef param = LLVMGetOperand(instr, argno); + size_t target_len; + const char *target_name; + + if (LLVMIsAFunction(param)) { + js_fptrs = js_get_or_make(js_call, "funcptrs", + json_object_new_array); + + target_name = LLVMGetValueName2(param, &target_len); + + json_object_array_add(js_fptrs, + json_object_new_string_len( + target_name, target_len)); + } + } +} + +static void process_fn(struct json_object *funcs, + struct json_object *js_special, + LLVMValueRef function) +{ + struct json_object *js_func, *js_calls; + + size_t name_len = 0; + const char *name_c = LLVMGetValueName2(function, &name_len); + char *name; + + name = strndup(name_c, name_len); + + js_func = json_object_object_get(funcs, name); + if (js_func) { + unsigned file_len = 0; + const char *file = LLVMGetDebugLocFilename(function, &file_len); + unsigned line = LLVMGetDebugLocLine(function); + + fprintf(stderr, "%.*s:%d:%s(): duplicate definition!\n", + (int)file_len, file, line, name); + free(name); + return; + } + + js_func = json_object_new_object(); + json_object_object_add(funcs, name, js_func); + free(name); + + js_calls = json_object_new_array(); + json_object_object_add(js_func, "calls", js_calls); + + dbgloc_add(js_func, function); + + for (LLVMBasicBlockRef basicBlock = LLVMGetFirstBasicBlock(function); + basicBlock; basicBlock = LLVMGetNextBasicBlock(basicBlock)) { + + for (LLVMValueRef instr = LLVMGetFirstInstruction(basicBlock); + instr; instr = LLVMGetNextInstruction(instr)) { + + if (LLVMIsAIntrinsicInst(instr)) + continue; + + if (LLVMIsACallInst(instr) || LLVMIsAInvokeInst(instr)) + process_call(js_calls, js_special, instr, + function); + } + } +} + +static void help(int retcode) +{ + fprintf(stderr, + "FRR LLVM bitcode to callgraph analyzer\n" + "\n" + "usage: frr-llvm-cg [-q|-v] [-o <JSONOUTPUT>] BITCODEINPUT\n" + "\n" + "\t-o FILENAME\twrite JSON output to file instead of stdout\n" + "\t-v\t\tbe more verbose\n" + "\t-q\t\tbe quiet\n" + "\n" + "BITCODEINPUT must be a LLVM binary bitcode file (not text\n" + "representation.) Use - to read from stdin.\n" + "\n" + "Note it may be necessary to build this binary tool against\n" + "the specific LLVM version that created the bitcode file.\n"); + exit(retcode); +} + +int main(int argc, char **argv) +{ + int opt; + const char *out = NULL; + const char *inp = NULL; + char v_or_q = '\0'; + + while ((opt = getopt(argc, argv, "hvqo:")) != -1) { + switch (opt) { + case 'o': + if (out) + help(1); + out = optarg; + break; + case 'v': + if (v_or_q && v_or_q != 'v') + help(1); + details_fptr_vars = true; + details_fptr_consts = true; + v_or_q = 'v'; + break; + case 'q': + if (v_or_q && v_or_q != 'q') + help(1); + details_fptr_vars = false; + details_fptr_consts = false; + v_or_q = 'q'; + break; + case 'h': + help(0); + return 0; + default: + help(1); + } + } + + if (optind != argc - 1) + help(1); + + inp = argv[optind]; + + LLVMMemoryBufferRef memoryBuffer; + char *message; + int ret; + + // check if we are to read our input file from stdin + if (!strcmp(inp, "-")) { + inp = "<stdin>"; + ret = LLVMCreateMemoryBufferWithSTDIN(&memoryBuffer, &message); + } else { + ret = LLVMCreateMemoryBufferWithContentsOfFile( + inp, &memoryBuffer, &message); + } + + if (ret) { + fprintf(stderr, "failed to open %s: %s\n", inp, message); + free(message); + return 1; + } + + // now create our module using the memorybuffer + LLVMModuleRef module; + if (LLVMParseBitcode2(memoryBuffer, &module)) { + fprintf(stderr, "%s: invalid bitcode\n", inp); + LLVMDisposeMemoryBuffer(memoryBuffer); + return 1; + } + + // done with the memory buffer now, so dispose of it + LLVMDisposeMemoryBuffer(memoryBuffer); + + struct json_object *js_root, *js_funcs, *js_special; + + js_root = json_object_new_object(); + js_funcs = json_object_new_object(); + json_object_object_add(js_root, "functions", js_funcs); + js_special = json_object_new_object(); + json_object_object_add(js_root, "special", js_special); + + // loop through all the functions in the module + for (LLVMValueRef function = LLVMGetFirstFunction(module); function; + function = LLVMGetNextFunction(function)) { + if (LLVMIsDeclaration(function)) + continue; + + process_fn(js_funcs, js_special, function); + } + + if (out) { + char tmpout[strlen(out) + 5]; + + snprintf(tmpout, sizeof(tmpout), "%s.tmp", out); + ret = json_object_to_file_ext(tmpout, js_root, + JSON_C_TO_STRING_PRETTY | + JSON_C_TO_STRING_PRETTY_TAB | + JSON_C_TO_STRING_NOSLASHESCAPE); + if (ret < 0) { + fprintf(stderr, "could not write JSON to file\n"); + return 1; + } + if (rename(tmpout, out)) { + fprintf(stderr, "could not rename JSON output: %s\n", + strerror(errno)); + unlink(tmpout); + return 1; + } + } else { + ret = json_object_to_fd(1, js_root, + JSON_C_TO_STRING_PRETTY | + JSON_C_TO_STRING_PRETTY_TAB | + JSON_C_TO_STRING_NOSLASHESCAPE); + if (ret < 0) { + fprintf(stderr, "could not write JSON to stdout\n"); + return 1; + } + } + + LLVMDisposeModule(module); + + return 0; +} diff --git a/tools/subdir.am b/tools/subdir.am index c637db6eb1..723a87d100 100644 --- a/tools/subdir.am +++ b/tools/subdir.am @@ -8,6 +8,10 @@ noinst_PROGRAMS += \ tools/gen_yang_deviations \ # end +EXTRA_PROGRAMS += \ + tools/frr-llvm-cg \ + # end + sbin_PROGRAMS += tools/ssd sbin_SCRIPTS += \ tools/frr-reload \ @@ -31,6 +35,14 @@ tools_gen_yang_deviations_LDADD = lib/libfrr.la $(LIBYANG_LIBS) tools_ssd_SOURCES = tools/start-stop-daemon.c +# don't bother autoconf'ing these for a simple optional tool +llvm_version = $(shell echo __clang_major__ | $(CC) -xc -P -E -) +tools_frr_llvm_cg_CFLAGS = $(AM_CFLAGS) `llvm-config-$(llvm_version) --cflags` +tools_frr_llvm_cg_LDFLAGS = `llvm-config-$(llvm_version) --ldflags --libs` +tools_frr_llvm_cg_SOURCES = \ + tools/frr-llvm-cg.c \ + # end + EXTRA_DIST += \ tools/etc \ tools/frr-reload \ |