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