]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | # SPDX-License-Identifier: GPL-2.0-or-later |
3d62176b DL |
2 | # callgraph json to graphviz generator for FRR |
3 | # | |
4 | # Copyright (C) 2020 David Lamparter for NetDEF, Inc. | |
3d62176b DL |
5 | |
6 | import re | |
7 | import sys | |
8 | import json | |
9 | ||
701a0192 | 10 | |
3d62176b DL |
11 | class FunctionNode(object): |
12 | funcs = {} | |
13 | ||
14 | def __init__(self, name): | |
15 | super().__init__() | |
16 | FunctionNode.funcs[name] = self | |
17 | ||
18 | self.name = name | |
19 | self.out = [] | |
20 | self.inb = [] | |
21 | self.rank = None | |
22 | self.defined = False | |
23 | self.defs = [] | |
24 | ||
25 | def __repr__(self): | |
26 | return '<"%s()" rank=%r>' % (self.name, self.rank) | |
27 | ||
28 | def define(self, attrs): | |
29 | self.defined = True | |
701a0192 | 30 | self.defs.append((attrs["filename"], attrs["line"])) |
3d62176b DL |
31 | return self |
32 | ||
33 | def add_call(self, called, attrs): | |
34 | return CallEdge(self, called, attrs) | |
35 | ||
36 | def calls(self): | |
37 | for e in self.out: | |
38 | yield e.o | |
39 | ||
40 | def calld(self): | |
41 | for e in self.inb: | |
42 | yield e.i | |
43 | ||
44 | def unlink(self, other): | |
45 | self.out = list([edge for edge in self.out if edge.o != other]) | |
46 | other.inb = list([edge for edge in other.inb if edge.i != other]) | |
47 | ||
48 | @classmethod | |
49 | def get(cls, name): | |
50 | if name in cls.funcs: | |
51 | return cls.funcs[name] | |
52 | return FunctionNode(name) | |
53 | ||
701a0192 | 54 | |
3d62176b DL |
55 | class CallEdge(object): |
56 | def __init__(self, i, o, attrs): | |
57 | self.i = i | |
58 | self.o = o | |
701a0192 | 59 | self.is_external = attrs["is_external"] |
3d62176b DL |
60 | self.attrs = attrs |
61 | ||
62 | i.out.append(self) | |
63 | o.inb.append(self) | |
64 | ||
65 | def __repr__(self): | |
66 | return '<"%s()" -> "%s()">' % (self.i.name, self.o.name) | |
67 | ||
701a0192 | 68 | |
3d62176b | 69 | def nameclean(n): |
701a0192 | 70 | if "." in n: |
71 | return n.split(".", 1)[0] | |
3d62176b DL |
72 | return n |
73 | ||
701a0192 | 74 | |
3d62176b DL |
75 | def calc_rank(queue, direction): |
76 | nextq = queue | |
77 | ||
78 | if direction == 1: | |
79 | aggr = max | |
80 | elem = lambda x: x.calls() | |
81 | else: | |
82 | aggr = min | |
83 | elem = lambda x: x.calld() | |
84 | ||
85 | currank = direction | |
86 | cont = True | |
87 | ||
88 | while len(nextq) > 0 and cont: | |
89 | queue = nextq | |
90 | nextq = [] | |
91 | ||
701a0192 | 92 | # sys.stderr.write('rank %d\n' % currank) |
3d62176b DL |
93 | |
94 | cont = False | |
95 | ||
96 | for node in queue: | |
97 | if not node.defined: | |
98 | node.rank = 0 | |
99 | continue | |
100 | ||
101 | rank = direction | |
102 | for other in elem(node): | |
103 | if other is node: | |
104 | continue | |
105 | if other.rank is None: | |
106 | nextq.append(node) | |
107 | break | |
108 | rank = aggr(rank, other.rank + direction) | |
109 | else: | |
110 | cont = True | |
111 | node.rank = rank | |
112 | ||
113 | currank += direction | |
114 | ||
115 | return nextq | |
116 | ||
701a0192 | 117 | |
3d62176b DL |
118 | class Graph(dict): |
119 | class Subgraph(set): | |
120 | def __init__(self): | |
121 | super().__init__() | |
122 | ||
123 | class NodeGroup(set): | |
124 | def __init__(self, members): | |
125 | super().__init__(members) | |
126 | ||
127 | class Node(object): | |
128 | def __init__(self, graph, fn): | |
129 | super().__init__() | |
130 | self._fn = fn | |
131 | self._fns = [fn] | |
132 | self._graph = graph | |
133 | self._calls = set() | |
134 | self._calld = set() | |
135 | self._group = None | |
136 | ||
137 | def __repr__(self): | |
138 | return '<Graph.Node "%s()"/%d>' % (self._fn.name, len(self._fns)) | |
139 | ||
140 | def __hash__(self): | |
141 | return hash(self._fn.name) | |
142 | ||
143 | def _finalize(self): | |
144 | for called in self._fn.calls(): | |
145 | if called.name == self._fn.name: | |
146 | continue | |
147 | if called.name in self._graph: | |
148 | self._calls.add(self._graph[called.name]) | |
149 | self._graph[called.name]._calld.add(self) | |
150 | ||
151 | def unlink(self, other): | |
152 | self._calls.remove(other) | |
153 | other._calld.remove(self) | |
154 | ||
155 | @property | |
156 | def name(self): | |
157 | return self._fn.name | |
158 | ||
159 | def calls(self): | |
160 | return self._calls | |
701a0192 | 161 | |
3d62176b DL |
162 | def calld(self): |
163 | return self._calld | |
164 | ||
165 | def group(self, members): | |
166 | assert self in members | |
167 | ||
168 | pregroups = [] | |
169 | for g in [m._group for m in members]: | |
170 | if g is None: | |
171 | continue | |
172 | if g in pregroups: | |
173 | continue | |
174 | ||
175 | assert g <= members | |
176 | pregroups.append(g) | |
177 | ||
178 | if len(pregroups) == 0: | |
179 | group = self._graph.NodeGroup(members) | |
180 | self._graph._groups.append(group) | |
181 | elif len(pregroups) == 1: | |
182 | group = pregroups[0] | |
183 | group |= members | |
184 | else: | |
185 | for g in pregroups: | |
186 | self._graph._groups.remove(g) | |
187 | group = self._graph.NodeGroup(members) | |
188 | self._graph._groups.append(group) | |
189 | ||
190 | for m in members: | |
191 | m._group = group | |
192 | return group | |
193 | ||
194 | def merge(self, other): | |
195 | self._fns.extend(other._fns) | |
196 | self._calls = (self._calls | other._calls) - {self, other} | |
197 | self._calld = (self._calld | other._calld) - {self, other} | |
198 | for c in other._calls: | |
199 | if c == self: | |
200 | continue | |
201 | c._calld.remove(other) | |
202 | c._calld.add(self) | |
203 | for c in other._calld: | |
204 | if c == self: | |
205 | continue | |
206 | c._calls.remove(other) | |
207 | c._calls.add(self) | |
208 | del self._graph[other._fn.name] | |
209 | ||
210 | def __init__(self, funcs): | |
211 | super().__init__() | |
212 | self._funcs = funcs | |
213 | for fn in funcs: | |
214 | self[fn.name] = self.Node(self, fn) | |
215 | for node in self.values(): | |
216 | node._finalize() | |
217 | self._groups = [] | |
218 | ||
219 | def automerge(self): | |
220 | nodes = list(self.values()) | |
221 | ||
222 | while len(nodes): | |
223 | node = nodes.pop(0) | |
224 | ||
225 | candidates = {node} | |
226 | evalset = set(node.calls()) | |
227 | prevevalset = None | |
228 | ||
229 | while prevevalset != evalset: | |
230 | prevevalset = evalset | |
231 | evalset = set() | |
232 | ||
233 | for evnode in prevevalset: | |
234 | inbound = set(evnode.calld()) | |
235 | if inbound <= candidates: | |
236 | candidates.add(evnode) | |
237 | evalset |= set(evnode.calls()) - candidates | |
238 | else: | |
239 | evalset.add(evnode) | |
240 | ||
701a0192 | 241 | # if len(candidates) > 1: |
3d62176b DL |
242 | # for candidate in candidates: |
243 | # if candidate != node: | |
244 | # #node.merge(candidate) | |
245 | # if candidate in nodes: | |
246 | # nodes.remove(candidate) | |
247 | node.group(candidates) | |
248 | ||
249 | for candidate in candidates: | |
250 | if candidate in nodes: | |
251 | nodes.remove(candidate) | |
252 | ||
253 | def calc_subgraphs(self): | |
254 | nodes = list(self.values()) | |
255 | self._subgraphs = [] | |
256 | up = {} | |
257 | down = {} | |
258 | ||
259 | self._linear_nodes = [] | |
260 | ||
261 | while len(nodes): | |
701a0192 | 262 | sys.stderr.write("%d\n" % len(nodes)) |
3d62176b DL |
263 | node = nodes.pop(0) |
264 | ||
265 | down[node] = set() | |
266 | queue = [node] | |
267 | while len(queue): | |
268 | now = queue.pop() | |
269 | down[node].add(now) | |
270 | for calls in now.calls(): | |
271 | if calls in down[node]: | |
272 | continue | |
273 | queue.append(calls) | |
274 | ||
275 | up[node] = set() | |
276 | queue = [node] | |
277 | while len(queue): | |
278 | now = queue.pop() | |
279 | up[node].add(now) | |
280 | for calld in now.calld(): | |
281 | if calld in up[node]: | |
282 | continue | |
283 | queue.append(calld) | |
284 | ||
285 | common = up[node] & down[node] | |
286 | ||
287 | if len(common) == 1: | |
288 | self._linear_nodes.append(node) | |
289 | else: | |
290 | sg = self.Subgraph() | |
291 | sg |= common | |
292 | self._subgraphs.append(sg) | |
293 | for n in common: | |
294 | if n != node: | |
295 | nodes.remove(n) | |
296 | ||
297 | return self._subgraphs, self._linear_nodes | |
298 | ||
299 | ||
701a0192 | 300 | with open(sys.argv[1], "r") as fd: |
3d62176b DL |
301 | data = json.load(fd) |
302 | ||
303 | extra_info = { | |
304 | # zebra - LSP WQ | |
701a0192 | 305 | ("lsp_processq_add", "work_queue_add"): [ |
306 | "lsp_process", | |
307 | "lsp_processq_del", | |
308 | "lsp_processq_complete", | |
3d62176b DL |
309 | ], |
310 | # zebra - main WQ | |
00f0c399 DL |
311 | ("mq_add_handler", "work_queue_add"): [ |
312 | "meta_queue_process", | |
313 | ], | |
314 | ("meta_queue_process", "work_queue_add"): [ | |
315 | "meta_queue_process", | |
316 | ], | |
3d62176b | 317 | # bgpd - label pool WQ |
00f0c399 DL |
318 | ("bgp_lp_get", "work_queue_add"): [ |
319 | "lp_cbq_docallback", | |
320 | ], | |
321 | ("bgp_lp_event_chunk", "work_queue_add"): [ | |
322 | "lp_cbq_docallback", | |
323 | ], | |
324 | ("bgp_lp_event_zebra_up", "work_queue_add"): [ | |
325 | "lp_cbq_docallback", | |
326 | ], | |
3d62176b | 327 | # bgpd - main WQ |
00f0c399 DL |
328 | ("bgp_process", "work_queue_add"): [ |
329 | "bgp_process_wq", | |
330 | "bgp_processq_del", | |
331 | ], | |
332 | ("bgp_add_eoiu_mark", "work_queue_add"): [ | |
333 | "bgp_process_wq", | |
334 | "bgp_processq_del", | |
335 | ], | |
3d62176b | 336 | # clear node WQ |
701a0192 | 337 | ("bgp_clear_route_table", "work_queue_add"): [ |
338 | "bgp_clear_route_node", | |
339 | "bgp_clear_node_queue_del", | |
340 | "bgp_clear_node_complete", | |
3d62176b DL |
341 | ], |
342 | # rfapi WQs | |
00f0c399 DL |
343 | ("rfapi_close", "work_queue_add"): [ |
344 | "rfapi_deferred_close_workfunc", | |
345 | ], | |
701a0192 | 346 | ("rfapiRibUpdatePendingNode", "work_queue_add"): [ |
347 | "rfapiRibDoQueuedCallback", | |
348 | "rfapiRibQueueItemDelete", | |
3d62176b DL |
349 | ], |
350 | } | |
351 | ||
352 | ||
701a0192 | 353 | for func, fdata in data["functions"].items(): |
3d62176b DL |
354 | func = nameclean(func) |
355 | fnode = FunctionNode.get(func).define(fdata) | |
356 | ||
701a0192 | 357 | for call in fdata["calls"]: |
358 | if call.get("type") in [None, "unnamed", "thread_sched"]: | |
359 | if call.get("target") is None: | |
3d62176b | 360 | continue |
701a0192 | 361 | tgt = nameclean(call["target"]) |
3d62176b | 362 | fnode.add_call(FunctionNode.get(tgt), call) |
701a0192 | 363 | for fptr in call.get("funcptrs", []): |
3d62176b | 364 | fnode.add_call(FunctionNode.get(nameclean(fptr)), call) |
701a0192 | 365 | if tgt == "work_queue_add": |
3d62176b | 366 | if (func, tgt) not in extra_info: |
701a0192 | 367 | sys.stderr.write( |
368 | "%s:%d:%s(): work_queue_add() not handled\n" | |
369 | % (call["filename"], call["line"], func) | |
370 | ) | |
3d62176b DL |
371 | else: |
372 | attrs = dict(call) | |
701a0192 | 373 | attrs.update({"is_external": False, "type": "workqueue"}) |
3d62176b DL |
374 | for dst in extra_info[func, tgt]: |
375 | fnode.add_call(FunctionNode.get(dst), call) | |
701a0192 | 376 | elif call["type"] == "install_element": |
377 | vty_node = FunctionNode.get("VTY_NODE_%d" % call["vty_node"]) | |
378 | vty_node.add_call(FunctionNode.get(nameclean(call["target"])), call) | |
379 | elif call["type"] == "hook": | |
3d62176b DL |
380 | # TODO: edges for hooks from data['hooks'] |
381 | pass | |
382 | ||
383 | n = FunctionNode.funcs | |
384 | ||
385 | # fix some very low end functions cycling back very far to the top | |
701a0192 | 386 | if "peer_free" in n: |
387 | n["peer_free"].unlink(n["bgp_timer_set"]) | |
388 | n["peer_free"].unlink(n["bgp_addpath_set_peer_type"]) | |
389 | if "bgp_path_info_extra_free" in n: | |
390 | n["bgp_path_info_extra_free"].rank = 0 | |
3d62176b | 391 | |
701a0192 | 392 | if "zlog_ref" in n: |
393 | n["zlog_ref"].rank = 0 | |
394 | if "mt_checkalloc" in n: | |
395 | n["mt_checkalloc"].rank = 0 | |
3d62176b DL |
396 | |
397 | queue = list(FunctionNode.funcs.values()) | |
398 | queue = calc_rank(queue, 1) | |
399 | queue = calc_rank(queue, -1) | |
400 | ||
701a0192 | 401 | sys.stderr.write("%d functions in cyclic set\n" % len(queue)) |
3d62176b DL |
402 | |
403 | graph = Graph(queue) | |
404 | graph.automerge() | |
405 | ||
406 | gv_nodes = [] | |
407 | gv_edges = [] | |
408 | ||
701a0192 | 409 | sys.stderr.write("%d groups after automerge\n" % len(graph._groups)) |
410 | ||
3d62176b DL |
411 | |
412 | def is_vnc(n): | |
701a0192 | 413 | return n.startswith("rfapi") or n.startswith("vnc") or ("_vnc_" in n) |
414 | ||
3d62176b DL |
415 | |
416 | _vncstyle = ',fillcolor="#ffffcc",style=filled' | |
417 | cyclic_set_names = set([fn.name for fn in graph.values()]) | |
418 | ||
419 | for i, group in enumerate(graph._groups): | |
420 | if len(group) > 1: | |
421 | group.num = i | |
701a0192 | 422 | gv_nodes.append("\tsubgraph cluster_%d {" % i) |
423 | gv_nodes.append("\t\tcolor=blue;") | |
3d62176b DL |
424 | for gn in group: |
425 | has_cycle_callers = set(gn.calld()) - group | |
701a0192 | 426 | has_ext_callers = ( |
427 | set([edge.i.name for edge in gn._fn.inb]) - cyclic_set_names | |
428 | ) | |
3d62176b | 429 | |
701a0192 | 430 | style = "" |
431 | etext = "" | |
3d62176b DL |
432 | if is_vnc(gn.name): |
433 | style += _vncstyle | |
434 | if has_cycle_callers: | |
701a0192 | 435 | style += ",color=blue,penwidth=3" |
3d62176b DL |
436 | if has_ext_callers: |
437 | style += ',fillcolor="#ffeebb",style=filled' | |
701a0192 | 438 | etext += '<br/><font point-size="10">(%d other callers)</font>' % ( |
439 | len(has_ext_callers) | |
440 | ) | |
441 | ||
442 | gv_nodes.append( | |
443 | '\t\t"%s" [shape=box,label=<%s%s>%s];' | |
444 | % (gn.name, "<br/>".join([fn.name for fn in gn._fns]), etext, style) | |
445 | ) | |
446 | gv_nodes.append("\t}") | |
3d62176b DL |
447 | else: |
448 | for gn in group: | |
701a0192 | 449 | has_ext_callers = ( |
450 | set([edge.i.name for edge in gn._fn.inb]) - cyclic_set_names | |
451 | ) | |
3d62176b | 452 | |
701a0192 | 453 | style = "" |
454 | etext = "" | |
3d62176b DL |
455 | if is_vnc(gn.name): |
456 | style += _vncstyle | |
457 | if has_ext_callers: | |
458 | style += ',fillcolor="#ffeebb",style=filled' | |
701a0192 | 459 | etext += '<br/><font point-size="10">(%d other callers)</font>' % ( |
460 | len(has_ext_callers) | |
461 | ) | |
462 | gv_nodes.append( | |
463 | '\t"%s" [shape=box,label=<%s%s>%s];' | |
464 | % (gn.name, "<br/>".join([fn.name for fn in gn._fns]), etext, style) | |
465 | ) | |
3d62176b DL |
466 | |
467 | edges = set() | |
468 | for gn in graph.values(): | |
469 | for calls in gn.calls(): | |
470 | if gn._group == calls._group: | |
701a0192 | 471 | gv_edges.append( |
472 | '\t"%s" -> "%s" [color="#55aa55",style=dashed];' % (gn.name, calls.name) | |
473 | ) | |
3d62176b | 474 | else: |
701a0192 | 475 | |
3d62176b DL |
476 | def xname(nn): |
477 | if len(nn._group) > 1: | |
701a0192 | 478 | return "cluster_%d" % nn._group.num |
3d62176b DL |
479 | else: |
480 | return nn.name | |
701a0192 | 481 | |
3d62176b DL |
482 | tup = xname(gn), calls.name |
483 | if tup[0] != tup[1] and tup not in edges: | |
484 | gv_edges.append('\t"%s" -> "%s" [weight=0.0,w=0.0,color=blue];' % tup) | |
485 | edges.add(tup) | |
486 | ||
701a0192 | 487 | with open(sys.argv[2], "w") as fd: |
488 | fd.write( | |
489 | """digraph { | |
3d62176b DL |
490 | node [fontsize=13,fontname="Fira Sans"]; |
491 | %s | |
701a0192 | 492 | }""" |
493 | % "\n".join(gv_nodes + [""] + gv_edges) | |
494 | ) |