Adding upstream version 9.1.upstream/9.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 494 insertions, 0 deletions

diff --git a/python/callgraph-dot.py b/python/callgraph-dot.py
new file mode 100644
index 0000000..4e58b19
--- /dev/null
+++ b/python/callgraph-dot.py
@@ -0,0 +1,494 @@
+# SPDX-License-Identifier: GPL-2.0-or-later
+# callgraph json to graphviz generator for FRR
+#
+# Copyright (C) 2020  David Lamparter for NetDEF, Inc.
+
+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)
+    )