[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [tor/master] Update callgraph code to find and output strongly connected components
commit def5883bbb744727d797558da07c490f6578aff9
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
Date: Mon Aug 10 12:11:34 2015 -0400
Update callgraph code to find and output strongly connected components
---
scripts/maint/analyze_callgraph.py | 51 +++++++++++++++++++++++++++++++++---
scripts/maint/display_callgraph.py | 17 ++++++++++--
2 files changed, 63 insertions(+), 5 deletions(-)
diff --git a/scripts/maint/analyze_callgraph.py b/scripts/maint/analyze_callgraph.py
index afafe14..69ae128 100755
--- a/scripts/maint/analyze_callgraph.py
+++ b/scripts/maint/analyze_callgraph.py
@@ -32,7 +32,7 @@ class Parser:
self.extern = True
m = re.match(r" CS<[^>]+> calls function '([^']+)'", line)
if m:
- self.calledfns.add(m.group(1))
+ self.calledfns.add(m.group(1))
self.enter_func(None)
def extract_callgraph(self):
@@ -56,6 +56,46 @@ def transitive_closure(g):
changed = True
return g
+def strongly_connected_components(g):
+ # From https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm, done stupidly.
+ index_of = {}
+ index = [ 0 ]
+ lowlink = {}
+ S = []
+ onStack = set()
+
+ all_sccs = []
+
+ def strongconnect(fn):
+ index_of[fn] = index[0]
+ lowlink[fn] = index[0]
+ index[0] += 1
+ S.append(fn)
+ onStack.add(fn)
+
+ for w in g.get(fn, []):
+ if w not in index_of:
+ strongconnect(w)
+ lowlink[fn] = min(lowlink[fn], lowlink[w])
+ elif w in onStack:
+ lowlink[fn] = min(lowlink[fn], index_of[w])
+
+ if lowlink[fn] == index_of[fn]:
+ this_scc = []
+ all_sccs.append(this_scc)
+ while True:
+ w = S.pop()
+ onStack.remove(w)
+ this_scc.append(w)
+ if w == fn:
+ break
+
+ for v in g.keys():
+ if v not in index_of:
+ strongconnect(v)
+
+ return all_sccs
+
if __name__ == '__main__':
p = Parser()
for fname in sys.argv[1:]:
@@ -63,10 +103,15 @@ if __name__ == '__main__':
p.parse_callgraph_file(f)
callgraph = p.extract_callgraph()
+ sccs = strongly_connected_components(callgraph)
+
closure = transitive_closure(callgraph)
- with open('callgraph.cp', 'w') as f:
+ with open('callgraph.pkl', 'w') as f:
cPickle.dump(callgraph, f)
- with open('callgraph_closure.cp', 'w') as f:
+ with open('callgraph_closure.pkl', 'w') as f:
cPickle.dump(closure, f)
+
+ with open('callgraph_sccs.pkl', 'w') as f:
+ cPickle.dump(sccs, f)
diff --git a/scripts/maint/display_callgraph.py b/scripts/maint/display_callgraph.py
index 4e4ea63..9ead56c 100755
--- a/scripts/maint/display_callgraph.py
+++ b/scripts/maint/display_callgraph.py
@@ -2,8 +2,21 @@
import cPickle
-callgraph = cPickle.load(open("callgraph.cp"))
-closure = cPickle.load(open("callgraph_closure.cp"))
+callgraph = cPickle.load(open("callgraph.pkl"))
+closure = cPickle.load(open("callgraph_closure.pkl"))
+sccs = cPickle.load(open("callgraph_sccs.pkl"))
for n_reachable, fn in sorted(list((len(r), fn) for fn, r in closure.iteritems())):
print "%s can reach %s other functions." %(fn, n_reachable)
+
+
+c = [ (len(component), component) for component in sccs ]
+c.sort()
+
+for n, component in c:
+ if n < 2:
+ continue
+ print n, component
+
+
+
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits