diff options
Diffstat (limited to 'other/analysis')
-rwxr-xr-x | other/analysis/check_recursion | 104 |
1 files changed, 104 insertions, 0 deletions
diff --git a/other/analysis/check_recursion b/other/analysis/check_recursion new file mode 100755 index 00000000..21063527 --- /dev/null +++ b/other/analysis/check_recursion | |||
@@ -0,0 +1,104 @@ | |||
1 | #!/usr/bin/env python | ||
2 | """ | ||
3 | Tool to check for recursive calls in toxcore C code. | ||
4 | |||
5 | Usage: | ||
6 | |||
7 | cat toxav/*.c toxcore/*.c toxencryptsave/*.c \ | ||
8 | | clang `pkg-config --cflags libsodium opus vpx` \ | ||
9 | -Itoxav -Itoxcore -Itoxencryptsave -S -emit-llvm -xc - -o- \ | ||
10 | | opt -analyze -print-callgraph 2>&1 \ | ||
11 | | other/analysis/check_recursion | ||
12 | """ | ||
13 | |||
14 | from __future__ import print_function | ||
15 | |||
16 | import collections | ||
17 | import fileinput | ||
18 | import re | ||
19 | import sys | ||
20 | import time | ||
21 | |||
22 | def load_callgraph(): | ||
23 | """ | ||
24 | Parses the output from opt -print-callgraph from stdin or argv. | ||
25 | |||
26 | Returns graph as dict[str, list[str]] containing nodes with their outgoing | ||
27 | edges. | ||
28 | """ | ||
29 | graph = collections.defaultdict(set) | ||
30 | cur = None | ||
31 | for line in fileinput.input(): | ||
32 | found = re.search("Call graph node for function: '(.*)'", line) | ||
33 | if found: | ||
34 | cur = found.group(1) | ||
35 | if cur: | ||
36 | found = re.search("calls function '(.*)'", line) | ||
37 | if found: | ||
38 | graph[cur].add(found.group(1)) | ||
39 | |||
40 | return {k: sorted(v) for k, v in graph.items()} | ||
41 | |||
42 | def walk(visited, callgraph, cycles, stack, cur): | ||
43 | """ | ||
44 | Detects cycles in the callgraph and adds them to the cycles parameter. | ||
45 | """ | ||
46 | if cur in visited: | ||
47 | return | ||
48 | stack.append(cur) | ||
49 | for callee in callgraph.get(cur, ()): | ||
50 | try: | ||
51 | cycles.add(" -> ".join(stack[stack.index(callee):] + [callee])) | ||
52 | except ValueError: | ||
53 | walk(visited, callgraph, cycles, stack, callee) | ||
54 | visited.add(callee) | ||
55 | stack.pop() | ||
56 | |||
57 | def get_time(): | ||
58 | """ | ||
59 | Return the current time in milliseconds. | ||
60 | """ | ||
61 | return int(round(time.time() * 1000)) | ||
62 | |||
63 | def find_recursion(expected): | ||
64 | """ | ||
65 | Main function: detects cycles and prints them. | ||
66 | |||
67 | Takes a set of expected cycles. If any of the expected cycles was not found, | ||
68 | or any unexpected cycle was found, the program exits with an error. | ||
69 | """ | ||
70 | start = prev = get_time() | ||
71 | print("[+0000=0000] Generating callgraph") | ||
72 | callgraph = load_callgraph() | ||
73 | |||
74 | now = get_time() | ||
75 | print("[+%04d=%04d] Finding recursion" % (now - prev, now - start)) | ||
76 | prev = now | ||
77 | |||
78 | cycles = set() | ||
79 | visited = set() | ||
80 | for func in sorted(callgraph.keys()): | ||
81 | walk(visited, callgraph, cycles, [], func) | ||
82 | |||
83 | now = get_time() | ||
84 | if cycles: | ||
85 | print("[+%04d=%04d] Recursion detected:" % (now - prev, now - start)) | ||
86 | for cycle in sorted(cycles): | ||
87 | if cycle in expected: | ||
88 | print(" - " + cycle + " (expected)") | ||
89 | expected.remove(cycle) | ||
90 | cycles.remove(cycle) | ||
91 | else: | ||
92 | print(" - " + cycle) | ||
93 | else: | ||
94 | print("[+%04d=%04d] No recursion detected" % (now - prev, now - start)) | ||
95 | |||
96 | if expected: | ||
97 | print("Expected recursion no longer present: " + str(list(expected))) | ||
98 | if expected or cycles: | ||
99 | sys.exit(1) | ||
100 | |||
101 | find_recursion(expected={ | ||
102 | "add_to_closest -> add_to_closest", | ||
103 | "add_to_list -> add_to_list", | ||
104 | }) | ||