diff options
Diffstat (limited to 'scripts/maint')
| -rwxr-xr-x | scripts/maint/analyze_callgraph.py | 219 | ||||
| -rw-r--r--[-rwxr-xr-x] | scripts/maint/checkOptionDocs.pl.in (renamed from scripts/maint/checkOptionDocs.pl) | 8 | ||||
| -rwxr-xr-x | scripts/maint/checkSpace.pl | 3 | ||||
| -rwxr-xr-x | scripts/maint/display_callgraph.py | 39 | ||||
| -rwxr-xr-x | scripts/maint/format_changelog.py | 3 | ||||
| -rwxr-xr-x | scripts/maint/generate_callgraph.sh | 14 | ||||
| -rwxr-xr-x | scripts/maint/lintChanges.py | 20 | ||||
| -rwxr-xr-x | scripts/maint/sortChanges.py | 47 | ||||
| -rwxr-xr-x | scripts/maint/updateVersions.pl.in (renamed from scripts/maint/updateVersions.pl) | 6 |
9 files changed, 333 insertions, 26 deletions
diff --git a/scripts/maint/analyze_callgraph.py b/scripts/maint/analyze_callgraph.py new file mode 100755 index 0000000000..b28460489a --- /dev/null +++ b/scripts/maint/analyze_callgraph.py @@ -0,0 +1,219 @@ +#!/usr/bin/python + +import re +import sys +import copy +import cPickle +import os + +class Parser: + def __init__(self): + self.calls = {} + + def enter_func(self, name): + if self.infunc and not self.extern: + self.calls.setdefault(self.infunc, set()).update( self.calledfns ) + + self.calledfns = set() + self.infunc = name + self.extern = False + + def parse_callgraph_file(self, inp): + self.infunc = None + self.extern = False + self.calledfns = set() + for line in inp: + m = re.match(r"Call graph node for function: '([^']+)'", line) + if m: + self.enter_func(m.group(1)) + continue + m = re.match(r" CS<[^>]+> calls external node", line) + if m: + self.extern = True + m = re.match(r" CS<[^>]+> calls function '([^']+)'", line) + if m: + self.calledfns.add(m.group(1)) + self.enter_func(None) + + def extract_callgraph(self): + c = self.calls + self.calls = {} + return c + + +def transitive_closure(g): + passno = 0 + changed = True + g = copy.deepcopy(g) + import random + while changed: + passno += 1 + changed = False + keys = g.keys() + idx = 0 + for k in keys: + idx += 1 + print "Pass %d/?: %d/%d\r" %(passno, idx, len(keys)), + sys.stdout.flush() + newset = g[k].copy() + for fn in g[k]: + newset.update(g.get(fn, set())) + if len(newset) != len(g[k]): + g[k].update( newset ) + changed = True + + print + + 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 + +def biggest_component(sccs): + return max(len(c) for c in sccs) + +def connection_bottlenecks(callgraph): + + callers = {} + for fn in callgraph: + for fn2 in callgraph[fn]: + callers.setdefault(fn2, set()).add(fn) + + components = strongly_connected_components(callgraph) + components.sort(key=len) + big_component_fns = components[-1] + size = len(big_component_fns) + + function_bottlenecks = fn_results = [] + + total = len(big_component_fns) + idx = 0 + for fn in big_component_fns: + idx += 1 + print "Pass 1/3: %d/%d\r"%(idx, total), + sys.stdout.flush() + cg2 = copy.deepcopy(callgraph) + del cg2[fn] + + fn_results.append( (size - biggest_component(strongly_connected_components(cg2)), fn) ) + + print + bcf_set = set(big_component_fns) + + call_bottlenecks = fn_results = [] + result_set = set() + total = len(big_component_fns) + idx = 0 + for fn in big_component_fns: + fn_callers = callers[fn].intersection(bcf_set) + idx += 1 + if len(fn_callers) != 1: + continue + + print "Pass 2/3: %d/%d\r"%(idx, total), + sys.stdout.flush() + + caller = fn_callers.pop() + assert len(fn_callers) == 0 + cg2 = copy.deepcopy(callgraph) + cg2[caller].remove(fn) + + fn_results.append( (size - biggest_component(strongly_connected_components(cg2)), fn, "called by", caller) ) + result_set.add( (caller, fn) ) + + print + + total = len(big_component_fns) + idx = 0 + for fn in big_component_fns: + fn_calls = callgraph[fn].intersection(bcf_set) + idx += 1 + if len(fn_calls) != 1: + continue + + print "Pass 3/3: %d/%d\r"%(idx, total), + sys.stdout.flush() + + callee = fn_calls.pop() + if (fn, callee) in result_set: + continue + + assert len(fn_calls) == 0 + cg2 = copy.deepcopy(callgraph) + cg2[fn].remove(callee) + + fn_results.append( (size - biggest_component(strongly_connected_components(cg2)), callee, "called by", fn) ) + + print + + + return (function_bottlenecks, call_bottlenecks) + +if __name__ == '__main__': + p = Parser() + for fname in sys.argv[1:]: + with open(fname, 'r') as f: + p.parse_callgraph_file(f) + + sys.stdout.flush + + print "Building callgraph" + callgraph = p.extract_callgraph() + + print "Finding strongly connected components" + sccs = strongly_connected_components(callgraph) + + print "Finding the transitive closure of the callgraph.." + closure = transitive_closure(callgraph) + + print "Finding bottlenecks..." + bottlenecks = connection_bottlenecks(callgraph) + + data = { + 'callgraph' : callgraph, + 'sccs' : sccs, + 'closure' : closure, + 'bottlenecks' : bottlenecks } + + with open('callgraph.pkl', 'w') as f: + cPickle.dump(data, f) + + + diff --git a/scripts/maint/checkOptionDocs.pl b/scripts/maint/checkOptionDocs.pl.in index 94307c6cef..1f53adf099 100755..100644 --- a/scripts/maint/checkOptionDocs.pl +++ b/scripts/maint/checkOptionDocs.pl.in @@ -7,7 +7,7 @@ my %torrcSampleOptions = (); my %manPageOptions = (); # Load the canonical list as actually accepted by Tor. -open(F, "./src/or/tor --list-torrc-options |") or die; +open(F, "@abs_top_builddir@/src/or/tor --list-torrc-options |") or die; while (<F>) { next if m!\[notice\] Tor v0\.!; if (m!^([A-Za-z0-9_]+)!) { @@ -34,12 +34,12 @@ sub loadTorrc { 0; } -loadTorrc("./src/config/torrc.sample.in", \%torrcSampleOptions); +loadTorrc("@abs_top_srcdir@/src/config/torrc.sample.in", \%torrcSampleOptions); # Try to figure out what's in the man page. my $considerNextLine = 0; -open(F, "./doc/tor.1.txt") or die; +open(F, "@abs_top_srcdir@/doc/tor.1.txt") or die; while (<F>) { if (m!^(?:\[\[([A-za-z0-9_]+)\]\] *)?\*\*([A-Za-z0-9_]+)\*\*!) { $manPageOptions{$2} = 1; @@ -67,5 +67,3 @@ subtractHashes("Orphaned in torrc.sample.in", \%torrcSampleOptions, \%options); subtractHashes("Not in man page", \%options, \%manPageOptions); subtractHashes("Orphaned in man page", \%manPageOptions, \%options); - - diff --git a/scripts/maint/checkSpace.pl b/scripts/maint/checkSpace.pl index c785d89567..906281112d 100755 --- a/scripts/maint/checkSpace.pl +++ b/scripts/maint/checkSpace.pl @@ -129,7 +129,8 @@ for $fn (@ARGV) { $1 ne "switch" and $1 ne "return" and $1 ne "int" and $1 ne "elsif" and $1 ne "WINAPI" and $2 ne "WINAPI" and $1 ne "void" and $1 ne "__attribute__" and $1 ne "op" and - $1 ne "size_t" and $1 ne "double") { + $1 ne "size_t" and $1 ne "double" and + $1 ne "workqueue_reply_t") { print " fn ():$fn:$.\n"; } } diff --git a/scripts/maint/display_callgraph.py b/scripts/maint/display_callgraph.py new file mode 100755 index 0000000000..211bfda28d --- /dev/null +++ b/scripts/maint/display_callgraph.py @@ -0,0 +1,39 @@ +#!/usr/bin/python + +import cPickle + +data = cPickle.load(open("callgraph.pkl")) + +callgraph = data['callgraph'] +closure = data['closure'] +sccs = data['sccs'] +fn_bottle, call_bottle = data['bottlenecks'] + +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() + +print "\n================================" + +for n, component in c: + if n < 2: + continue + print "Strongly connected component of size %d:"%n + print component + + +print "\n================================" + +print "====== Number of functions pulled into blob, by function in blob." +fn_bottle.sort() +for n, fn in fn_bottle[-30:]: + print "%3d: %s"%(n, fn) + +print "====== Number of functions pulled into blob, by call in blob." +call_bottle.sort() +for n, fn1, _, fn2 in call_bottle[-30:]: + print "%3d: %s -> %s "%(n, fn2, fn1) + diff --git a/scripts/maint/format_changelog.py b/scripts/maint/format_changelog.py index d1b4a3dff3..5e4c8cac9a 100755 --- a/scripts/maint/format_changelog.py +++ b/scripts/maint/format_changelog.py @@ -36,7 +36,6 @@ NO_HYPHENATE=set(""" pf-divert tor-resolve tor-gencert -tor-fw-helper """.split()) LASTLINE_UNDERFLOW_EXPONENT = 1 @@ -59,7 +58,7 @@ def generate_wrapping(words, divisions): w = words[last:i] last = i line = " ".join(w).replace("\xff ","-").replace("\xff","-") - lines.append(line) + lines.append(line.strip()) return lines def wrapping_quality(words, divisions, width1, width2): diff --git a/scripts/maint/generate_callgraph.sh b/scripts/maint/generate_callgraph.sh new file mode 100755 index 0000000000..c6b33c0aea --- /dev/null +++ b/scripts/maint/generate_callgraph.sh @@ -0,0 +1,14 @@ +#!/bin/sh + +C_FILES=`echo src/common/*.c src/or/*.c src/tools/*.c` +CFLAGS="-Isrc/ext/trunnel -Isrc/trunnel -I. -Isrc/ext -Isrc/common -DLOCALSTATEDIR=\"\" -DSHARE_DATADIR=\"\" -Dinline=" + +mkdir -p callgraph/src/common +mkdir -p callgraph/src/or +mkdir -p callgraph/src/tools + +for fn in $C_FILES; do + echo $fn + clang $CFLAGS -S -emit-llvm -fno-inline -o - $fn | \ + opt -analyze -print-callgraph >/dev/null 2> "callgraph/${fn}allgraph" +done diff --git a/scripts/maint/lintChanges.py b/scripts/maint/lintChanges.py index 69963aea28..c2fc01d2bf 100755 --- a/scripts/maint/lintChanges.py +++ b/scripts/maint/lintChanges.py @@ -1,19 +1,22 @@ #!/usr/bin/python +from __future__ import print_function +from __future__ import with_statement import sys import re - +import os def lintfile(fname): have_warned = [] + def warn(s): if not have_warned: have_warned.append(1) - print fname,":" - print "\t",s + print("{}:".format(fname)) + print("\t{}".format(s)) - m = re.search(r'(\d{3,})', fname) + m = re.search(r'(\d{3,})', os.path.basename(fname)) if m: bugnum = m.group(1) else: @@ -23,12 +26,12 @@ def lintfile(fname): contents = f.read() if bugnum and bugnum not in contents: - warn("bug number %s does not appear"%bugnum) + warn("bug number {} does not appear".format(bugnum)) lines = contents.split("\n") isBug = ("bug" in lines[0] or "fix" in lines[0]) - if not re.match(r'^ +o (.*)', contents): + if not re.match(r'^[ ]{2}o (.*)', contents): warn("header not in format expected") contents = " ".join(contents.split()) @@ -44,11 +47,12 @@ def lintfile(fname): if re.search(r'[bB]ug (\d+)', contents): if not re.search(r'[Bb]ugfix on ', contents): warn("bugfix does not say 'bugfix on X.Y.Z'") - elif not re.search('[fF]ixes ([a-z ]*)bug (\d+); bugfix on ', contents): + elif not re.search('[fF]ixes ([a-z ]*)bug (\d+); bugfix on ', + contents): warn("bugfix incant is not semicoloned") -if __name__=='__main__': +if __name__ == '__main__': for fname in sys.argv[1:]: if fname.endswith("~"): continue diff --git a/scripts/maint/sortChanges.py b/scripts/maint/sortChanges.py index ad28c79d9d..7e25cefd53 100755 --- a/scripts/maint/sortChanges.py +++ b/scripts/maint/sortChanges.py @@ -5,8 +5,6 @@ """This script sorts a bunch of changes files listed on its command line into roughly the order in which they should appear in the changelog. - - TODO: collation support. """ import re @@ -19,7 +17,7 @@ def fetch(fn): return s def score(s,fname=None): - m = re.match(r'^ +o (.*)', s) + m = re.match(r'^ +o ([^\n]*)\n(.*)', s, re.M|re.S) if not m: print >>sys.stderr, "Can't score %r from %s"%(s,fname) lw = m.group(1).lower() @@ -38,12 +36,47 @@ def score(s,fname=None): else: score = 100 - return (score, lw, s) + return (score, lw, m.group(1), m.group(2)) + +def splitChanges(s): + this_entry = [] + for line in s.split("\n"): + if line.strip() == "": + continue + if re.match(r" +o ", line): + if len(this_entry) > 2: + yield "".join(this_entry) + curHeader = line + this_entry = [ curHeader, "\n" ] + continue + elif re.match(r" +- ", line): + if len(this_entry) > 2: + yield "".join(this_entry) + this_entry = [ curHeader, "\n" ] + + this_entry.append(line) + this_entry.append("\n") + if len(this_entry) > 2: + yield "".join(this_entry) -changes = [ score(fetch(fn),fn) for fn in sys.argv[1:] if not fn.endswith('~') ] + +changes = [] + +for fn in sys.argv[1:]: + if fn.endswith('~'): + continue + for change in splitChanges(fetch(fn)): + changes.append(score(change,fn)) changes.sort() -for _, _, s in changes: - print s +last_lw = "this is not a header" +for _, lw, header, rest in changes: + if lw == last_lw: + print rest, + else: + print + print " o",header + print rest, + last_lw = lw diff --git a/scripts/maint/updateVersions.pl b/scripts/maint/updateVersions.pl.in index 15c83b80a7..65c51a1f2d 100755 --- a/scripts/maint/updateVersions.pl +++ b/scripts/maint/updateVersions.pl.in @@ -1,8 +1,8 @@ #!/usr/bin/perl -w -$CONFIGURE_IN = './configure.ac'; -$ORCONFIG_H = './src/win32/orconfig.h'; -$TOR_NSI = './contrib/win32build/tor-mingw.nsi.in'; +$CONFIGURE_IN = '@abs_top_srcdir@/configure.ac'; +$ORCONFIG_H = '@abs_top_srcdir@/src/win32/orconfig.h'; +$TOR_NSI = '@abs_top_srcdir@/contrib/win32build/tor-mingw.nsi.in'; $quiet = 1; |