summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authoriphydf <iphydf@users.noreply.github.com>2018-08-27 15:51:41 +0000
committeriphydf <iphydf@users.noreply.github.com>2018-09-08 22:08:34 +0000
commit93cc178cfedb281ad05f988850d601e600361d9a (patch)
tree095e8bb867b153fe363dd49b10ab512e2ac58ccf
parentab4477d9315d6d62a449920a32099503c656f43a (diff)
Add tool to find directly recursive calls in toxcore.
We should avoid recursion, as it makes reasoning about stack growth harder. This tool shows (currently) 4 (non-tail) recursive functions, at least 2 of which are easy to fix.
-rw-r--r--.travis.yml1
-rwxr-xr-x.travis/bazel-linux7
-rwxr-xr-x.travis/cmake-linux7
-rwxr-xr-xother/analysis/check_recursion104
4 files changed, 116 insertions, 3 deletions
diff --git a/.travis.yml b/.travis.yml
index 119228aa..ae7e7fa2 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -24,6 +24,7 @@ matrix:
24 - libgtest-dev # For unit tests. 24 - libgtest-dev # For unit tests.
25 - libvpx-dev # For toxav. 25 - libvpx-dev # For toxav.
26 - portaudio19-dev # For av_test. 26 - portaudio19-dev # For av_test.
27 - pylint
27 install: .travis/$JOB install 28 install: .travis/$JOB install
28 script: .travis/$JOB script 29 script: .travis/$JOB script
29 after_script: .travis/upload-coverage 30 after_script: .travis/upload-coverage
diff --git a/.travis/bazel-linux b/.travis/bazel-linux
index b157437d..5594ff8c 100755
--- a/.travis/bazel-linux
+++ b/.travis/bazel-linux
@@ -16,9 +16,10 @@ travis_install() {
16} 16}
17 17
18travis_script() { 18travis_script() {
19 bazel test //c-toxcore:license_test 19 bazel test \
20 bazel test //c-toxcore:readme_test 20 //c-toxcore:license_test \
21 bazel test //c-toxcore:yamllint_test 21 //c-toxcore:readme_test \
22 //c-toxcore:yamllint_test
22 23
23 # TODO(iphydf): Make tests have a chance to succeed. 24 # TODO(iphydf): Make tests have a chance to succeed.
24 # Run the tests, but if they fail, at least we should be able to build. 25 # Run the tests, but if they fail, at least we should be able to build.
diff --git a/.travis/cmake-linux b/.travis/cmake-linux
index fe5de10a..541eb014 100755
--- a/.travis/cmake-linux
+++ b/.travis/cmake-linux
@@ -53,8 +53,15 @@ travis_install() {
53} 53}
54 54
55run_static_analysis() { 55run_static_analysis() {
56 pylint -E other/analysis/check_recursion
57
56 export CPPFLAGS="-isystem $CACHEDIR/include" 58 export CPPFLAGS="-isystem $CACHEDIR/include"
57 export LDFLAGS="-L $CACHEDIR/lib" 59 export LDFLAGS="-L $CACHEDIR/lib"
60 cat toxav/*.c toxcore/*.c toxencryptsave/*.c \
61 | clang `pkg-config --cflags libsodium opus vpx` \
62 -Itoxav -Itoxcore -Itoxencryptsave -S -emit-llvm -xc - -o- \
63 | opt -analyze -print-callgraph 2>&1 \
64 | other/analysis/check_recursion
58 other/analysis/run-clang 65 other/analysis/run-clang
59 other/analysis/run-clang-analyze 66 other/analysis/run-clang-analyze
60} 67}
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"""
3Tool to check for recursive calls in toxcore C code.
4
5Usage:
6
7cat 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
14from __future__ import print_function
15
16import collections
17import fileinput
18import re
19import sys
20import time
21
22def 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
42def 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
57def get_time():
58 """
59 Return the current time in milliseconds.
60 """
61 return int(round(time.time() * 1000))
62
63def 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
101find_recursion(expected={
102 "add_to_closest -> add_to_closest",
103 "add_to_list -> add_to_list",
104})